84 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 helper H will also get the event message E(B.v2,t2)and add it to selecting the neighbor vertex which is nearest to the latest his event table.In Fig.2(d).when helper H passes by tag v at time appearance location of the target.For example,suppose the t4.helper H posts an event message E(H,vi,t4)to tag v1.Besides. weight of all edges is equal in Fig.1(b).The current location of helper H will also get the event message E(A.vi,ti)and the the searcher is v3.and the latest appearance location of the target request message R(A,B,t1)of A,and add them to helper H's event is v7.Then vertex vn will be selected,because it is the nearest table and request queue.Then helper H posts the event message neighbor of v3 to the vertex v17.However,three reasons make us E(B,v2,t2)to tag v.In Fig.2(e).helper H posts the event message do not use the above simple method to select the next vertex to E(B,v2,t2)and request message R(A,B,t1)to tag v3.thus to attract move.The first reason is that the trace with latest timestamp may more helpers to find B.In Fig.2(f).the memory space of tag is be far away.There should be a tradeoff between the timestamp of divided into two segments:event message segment and request the trace and distance.The second reason is that the target is a message segment.We will discuss more on the management of moving object whose motion is a continuous process.The third the memory space in the following: reason is that the movement behavior of the target has locality in Situation 1.Normal Mode 2(b): the real world.We use Algorithm 2 to select the next neighbor to user Hi posts an event message E(Hi.vj.t)to vj: move and guide the searcher to be close to a target region rather than a single point. Using the One Request Many Event (ORME)writing and repla cing strategy,each tag maintains at most A event messages of each Algorithm 2.Navigation algorithm. user Hi.A is a predefined parameter of ORME which is used to adjust the ratio between request messages and event messages. Input:tnow;Vs:d:V=v1.V2.....m): When the value A equals to 1,the ORME strategy is reduced to U=(u1.u2....un):=(t1.t2.....tn): OROE strategy.If the number of event messages is less than A.then Output:next neighbor Unext to move E(Hi.vj.t)will be written to vj.The oldest event message of H 1:Calculate all vertices pairs'shortest path length on graph G stored on v will be replaced with E(Hi.vj.t).Thus the size of event using algorithm such as Floyd-Warshall or Dijistra;and message segment is A times as many as the size of request store these values in matrix d. message segment. 2:for each u;∈Udo Situation 2.Normal Mode 3(a): 1 Hi posts a request message R(S,T,t)to vy: ai=Enow-ti 4:end for Using the One Request Many Event (ORME)writing and repla- 5:a=∑i-1a: cing strategy,each tag maintains at most one request message of 6:for each neighbor vie V of vs do searcher S and target T.If there already exists a request message fy)=d[v;llvj+∑-1告×dylu R(S,T.t')on vk and t'<t,then the timestamp t'will be updated to 8:end for t.We take the same writing and replacing method in Searcher 9:Select the smallest value f(Umin)from f(v1),....f(Um): Mode step 2. Situation 3.Normal Mode 3(b): Unext Umin Hi selects event messages (E(T,*,*)of the target T from H's event table:then Hi posts these event messages to vk. In Algorithm 2,thow is the current time;Us is the current location In general,there are many helpers in the system.If all of them of the searcher S:d is a shortest path matrix which can be precalculated;each element div]v]ed is the shortest path length post messages to a vertex as soon as they pass by it,the memory space of the tag will be reduced rapidly.Therefore.when the between vertices v and v:all vertices in collection V=v1.v2.....m) are the neighbors of vertex vs.Besides,we use the event table of available memory space size is reduced to a certain range,say 10%, searcher S to predict the current location of the target.Let n(n < we use a posting probability p=i/oi,(0sp s 1)to further reduce is the event messages number of the target T.Arrange these event the number of posting events messages.o,is the total memory size messages in descending order according to the timestamp.Represent of vk,and 6;is the memory size which has not been used of vertex the arrangement with the list E(T,u1,t),E(T,u2,t2)....,E(T,un,tn). Vk.When a helper passes by a vertex,he will post messages to the vertex with a posting probability p. Correspondingly,=(t1,t2....,tn)is the list of timestamps,and U=(u.u2..u)is the list of vertices.Vertices in list U compose the target region. 4.4.Navigation algorithm For each neighbor vi of vs.we define a cost function f(vi)to predict whether the searcher is close to the target or far from the Our goal is to find the optimal vertex sequence,so as to navigate target.We assign a normalized weight ai/a for each vertex u in searcher S to a moving target T with minimum time cost.At the the target region according to the timestamp.The weight of vertex beginning of the above navigation framework,if there is no priori with latest traces will have higher value than that of other vertices. knowledge of the target's movement,searcher S can only randomly Cost function f(;)is defined below: select a place to move without any guidance.After a period of time, the searcher collects some event messages of the target which f(vj)=w[vs][vi]+ (1) states that the target appears at some places.The more the traces searcher collects,the better the searcher will know about the target's movement.If history data of the target's movement can The neighbor vertex which has the lowest cost will be selected as be obtained,the searcher can even predict the current location of the next intermediate vertex.For example,in Fig.3,we assume the target according to those traces he gets now.At least,searcher S that all the edges between two vertices on the graph are equal to has some instructive guidance at this time. 1:n=3:V=w2,V4,V11,21》.U=(w17,18,V19.T=(4,3,1.the When searcher S has collected some event messages of the current time tnow=5.Then vertex vn will be selected as the next target T,the searcher could use these traces as the guidance to intermediate vertex.Because the cost of vn is 7.57 which is less select the next neighbor vertex to move.A simple way to do this is than the cost of v2.va or v21.helper H will also get the event message E Bh i ; v2;t2 and add it to his event table. In Fig. 2(d), when helper H passes by tag v1 at time t4, helper H posts an event message E Hh i ; v1;t4 to tag v1. Besides, helper H will also get the event message E A; v1;t1
and the request message R A; B;t1
of A, and add them to helper H's event table and request queue. Then helper H posts the event message E Bh i ; v2;t2 to tag v1. In Fig. 2(e), helper H posts the event message E Bh i ; v2;t2 and request message R A; B;t1
to tag v3, thus to attract more helpers to find B. In Fig. 2(f), the memory space of tag is divided into two segments: event message segment and request message segment. We will discuss more on the management of the memory space in the following: Situation 1. Normal Mode 2(b): user Hi posts an event message E Hi; vj;t
to vj; Using the One Request Many Event (ORME) writing and repla￾cing strategy, each tag maintains at most λ event messages of each user Hi. λ is a predefined parameter of ORME which is used to adjust the ratio between request messages and event messages. When the value λ equals to 1, the ORME strategy is reduced to OROE strategy. If the number of event messages is less than λ, then E Hi; vj;t
will be written to vj. The oldest event message of Hi stored on vj will be replaced with E Hi; vj;t
. Thus the size of event message segment is λ times as many as the size of request message segment. Situation 2. Normal Mode 3(a): Hi posts a request message R Sh i ; T;t to vk; Using the One Request Many Event (ORME) writing and repla￾cing strategy, each tag maintains at most one request message of searcher S and target T. If there already exists a request message R S; T;t0 h i on vk and t0 ot, then the timestamp t0 will be updated to t. We take the same writing and replacing method in Searcher Mode step 2. Situation 3. Normal Mode 3(b): Hi selects event messages fE Th ig ; n; n of the target T from H0 i s event table; then Hi posts these event messages to vk: In general, there are many helpers in the system. If all of them post messages to a vertex as soon as they pass by it, the memory space of the tag will be reduced rapidly. Therefore, when the available memory space size is reduced to a certain range, say 10%, we use a posting probability p ¼ δ0 i =δi; ð0rpr1Þ to further reduce the number of posting events messages. δi is the total memory size of vk, and δ0 i is the memory size which has not been used of vertex vk. When a helper passes by a vertex, he will post messages to the vertex with a posting probability p. 4.4. Navigation algorithm Our goal is to find the optimal vertex sequence, so as to navigate searcher S to a moving target T with minimum time cost. At the beginning of the above navigation framework, if there is no priori knowledge of the target's movement, searcher S can only randomly select a place to move without any guidance. After a period of time, the searcher collects some event messages of the target which states that the target appears at some places. The more the traces searcher collects, the better the searcher will know about the target's movement. If history data of the target's movement can be obtained, the searcher can even predict the current location of the target according to those traces he gets now. At least, searcher S has some instructive guidance at this time. When searcher S has collected some event messages of the target T, the searcher could use these traces as the guidance to select the next neighbor vertex to move. A simple way to do this is selecting the neighbor vertex which is nearest to the latest appearance location of the target. For example, suppose the weight of all edges is equal in Fig. 1(b). The current location of the searcher is v3, and the latest appearance location of the target is v17. Then vertex v11 will be selected, because it is the nearest neighbor of v3 to the vertex v17. However, three reasons make us do not use the above simple method to select the next vertex to move. The first reason is that the trace with latest timestamp may be far away. There should be a tradeoff between the timestamp of the trace and distance. The second reason is that the target is a moving object whose motion is a continuous process. The third reason is that the movement behavior of the target has locality in the real world. We use Algorithm 2 to select the next neighbor to move and guide the searcher to be close to a target region rather than a single point. Algorithm 2. Navigation algorithm. Input: tnow; vs; d; V ¼ h i ν1; ν2; …; νm ; U ¼ h i u1; u2; …; un ; Γ ¼ h i t1;t2; …;tn ; Output: next neighbor νnext to move 1: Calculate all vertices pairs' shortest path length on graph G using algorithm such as Floyd–Warshall or Dijistra; and store these values in matrix d. 2: for each ui AU do 3: αi ¼ 1 tnow ti ; 4: end for 5: α ¼ Pn i ¼ 1 αi; 6: for each neighbor νj AV of vs do 7: fðνjÞ ¼ d½vs½νjþ Pn i ¼ 1 αi α  d½νj½ui; 8: end for 9: Select the smallest value fðνminÞ from fðν1Þ;…; fðνmÞ; νnext ¼ νmin; In Algorithm 2, tnow is the current time; vs is the current location of the searcher S; d is a shortest path matrix which can be precalculated; each element d½v½v0 Ad is the shortest path length between vertices v and v0 ; all vertices in collection V ¼ h i ν1; ν2; …; νm are the neighbors of vertex vs. Besides, we use the event table of searcher S to predict the current location of the target. Let n (nrθk) is the event messages number of the target T. Arrange these event messages in descending order according to the timestamp. Represent the arrangement with the list E Th i ; u1;t1 , E Th i ; u2;t2 , … , E Th i ; un;tn . Correspondingly, Γ ¼ h i t1;t2; …;tn is the list of timestamps, and U ¼ h i u1; u2; …; un is the list of vertices. Vertices in list U compose the target region. For each neighbor νj of vs, we define a cost function fðνjÞ to predict whether the searcher is close to the target or far from the target. We assign a normalized weight αi=α for each vertex ui in the target region according to the timestamp. The weight of vertex with latest traces will have higher value than that of other vertices. Cost function fðνjÞ is defined below: fðνjÞ ¼ w½vs½νjþ Xn i ¼ 1 αi α  d½νj½ui ð1Þ The neighbor vertex which has the lowest cost will be selected as the next intermediate vertex. For example, in Fig. 3, we assume that all the edges between two vertices on the graph are equal to 1; n¼3; V ¼ h i v2; v4; v11; v21 , U ¼ h i v17; v18; v19 , Γ ¼ h i 4; 3; 1 , the current time tnow ¼ 5. Then vertex v11 will be selected as the next intermediate vertex. Because the cost of v11 is 7.57 which is less than the cost of v2, v4 or v21. 84 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89