entry in the help queue is a request message which gives location of the target is v17.Then vertex v will be selected. the identifications of searcher and target,also the timestamp because it is the nearest neighbor of v3 to the vertex v17. of this message.This request message was firstly posted by However.three reasons make us do not use the above simple the searcher,then other users carry and forward this message method to select the next vertex to move.The first reason is without changing the timestamp of it.We use a positive time that the trace with latest timestamp may be far away.There threshold 0:to decide whether to discard outdated requests. should be a tradeoff between the timestamp of the trace and distance.The second reason is that the target is a moving C.Management of RFID tags object whose motion is a continuous process.The third reason Because the memory size of RFID tag is limited,we is that the movement behavior of the target has locality in the should make full use of these storage resources.Under the real world.We use Algorithm 2 to select the next neighbor navigation framework,post operation will write messages to to move and guide the searcher to be close to a target region tags.Therefore,a reasonable writing and replacing strategy rather than a single point. should be used.Now,considering the following situations. Algorithm 2 Navigation Algorithm Situation 1.Normal Mode 2(b)Each tag maintains at most A event messages of each user Hi.If the number of event Input:tnow;Us;d, V=(y,2,,m月 messages is less than A,then E(Hi,vj,t)will be written to U=(u1,2,,n）;T=(t1,t2,,tn） vj.Otherwise,the oldest event message of Hi stored on vj Output:next neighbor inext to move will be replaced with E(Hi,vi,t). Calculate all vertices pairs'shortest path length on graph G using algorithm such as Floyd-Warshall or Situation 2.Normal Mode 3(a)Each tag maintains at Dijistra;and store these values in matrix d. most one request message of searcher S and target T.If there 2:for each ui∈Udo already exists a request message R(S.T,t)on vk and t'<t. 3: then the timestamp t'will be updated to t.No extra memory Qi-Inow-ti 4:end for space will be used.Besides,we take the same strategy in Searcher Mode step 2. 5a=∑1a 6:for each neighbor v;V of vs do Situation 3.Normal Mode 3(b)Because there are many helpers in the system,if all of them post messages to a vertex fy)=do,lyl+∑=告×dylu 8:end for as soon as they pass by it,the memory space of the tag will 9:Select the smallest value f(vmin)from f(v1),...,f(vm); be reduced rapidly.Therefore,we use a posting probability Vnert Vmin; p=s/si,(0<p <1)to adjust users'post operations,where si is the total memory size of vk,and s,is the memory size In Algorithm 2,tnow is the current time;v is the current which has not been used of vertex vk.When a helper passes location of the searcher S;d is a shortest path matrix which by a vertex,he will post messages to the vertex with a posting can be precalculated;each element dlv]l']d is the shortest probability p. path length between vertex v and v';all vertices in collection V=(v1,v2,..,Um)are the neighbors of vertex vs.Besides, D.Navigation Algorithm we use the trace table of searcher S to predict the current Our goal is to find the optimal vertex sequence,so as to location of the target.Let n (n<)is the event messages navigate searcher S to a moving target T with minimum time number of the target T.Arrange these event messages in cost.At the beginning of the above navigation framework. descending order according to the timestamp.Represent the if there is no priori knowledge of the target's movement, arrangement with the list E(T,u1,t1),E(T,u2,t2),.... searcher S can only randomly select a place to move without E(T,un,tn).Correspondingly,I=(t1,t2,...,tn)is the list any guidance.After a period of time,the searcher collects of timestamps,and U=(u,u2,.,un)is the list of vertices. some event messages of the target which states that the target Vertices in list U compose the target region. appears at some places.The more traces searcher collects, For each neighbor vj of va,we define a cost function f(v) the better searcher will know about the target's movement. to predict whether the searcher is close to the target or far If history data of the target's movement can be obtained,the from the target.We assign a normalized weight oi/a for each searcher can even predict the current location of the target vertex u;in the target region according to the timestamp.The according to those traces he gets now.At least,searcher S has weight of vertex with latest traces will have higher value than some instructive guidance at this time. that of other vertices.Cost function f(v)is defined below: When searcher S has collected some event messages of the target T,the searcher could use these traces as the guidance fy)=wlyl+∑g×dylu (4) to select the next neighbor vertex to move.A simple way 1 to do this is selecting the neighbor vertex which is nearest The neighbor vertex which has the lowest cost will be selected to the latest appearance location of the target.For example, as the next intermediate vertex.For example,in Figure 2,we suppose the weight of all edges are equal in Figure 1(b).The assume that all the edges between two vertices on the graph current location of the searcher is vs,and the latest appearance equals to1n=3,V=(2,v4,v11,v21）,U=(w17,v18,v1g,entry in the help queue is a request message which gives the identifications of searcher and target, also the timestamp of this message. This request message was firstly posted by the searcher, then other users carry and forward this message without changing the timestamp of it. We use a positive time threshold θt to decide whether to discard outdated requests. C. Management of RFID tags Because the memory size of RFID tag is limited, we should make full use of these storage resources. Under the navigation framework, post operation will write messages to tags. Therefore, a reasonable writing and replacing strategy should be used. Now, considering the following situations. Situation 1. Normal Mode 2(b) Each tag maintains at most λ event messages of each user Hi . If the number of event messages is less than λ, then E hHi , vj , ti will be written to vj . Otherwise, the oldest event message of Hi stored on vj will be replaced with E hHi , vj , ti. Situation 2. Normal Mode 3(a) Each tag maintains at most one request message of searcher S and target T. If there already exists a request message R hS, T, t′ i on vk and t ′ < t, then the timestamp t ′ will be updated to t. No extra memory space will be used. Besides, we take the same strategy in Searcher Mode step 2. Situation 3. Normal Mode 3(b) Because 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, we use a posting probability p = s ′ i /si ,(0 ≤ p ≤ 1) to adjust users’ post operations, where si is the total memory size of vk, and s ′ 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. D. 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 traces searcher collects, the better 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 are equal in Figure 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ν1, ν2, ..., νmi; U = hu1, u2, ..., uni; Γ = ht1, t2, ..., tni; 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 ∈ U do 3: αi = 1 tnow−ti ; 4: end for 5: α = Pn i=1 αi ; 6: for each neighbor νj ∈ V 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][v ′ ] ∈ d is the shortest path length between vertex v and v ′ ; all vertices in collection V = hν1, ν2, ..., νmi are the neighbors of vertex vs. Besides, we use the trace table of searcher S to predict the current location of the target. Let n (n ≤ θ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 hT, u1, t1i, E hT, u2, t2i, ... , E hT, un, tni. Correspondingly, Γ = ht1, t2, ..., tni is the list of timestamps, and U = hu1, u2, ..., uni 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 ] (4) The neighbor vertex which has the lowest cost will be selected as the next intermediate vertex. For example, in Figure 2, we assume that all the edges between two vertices on the graph equals to 1; n = 3; V = hv2, v4, v11, v21i, U = hv17, v18, v19i