L be the total distance which is defined below. on,Hi will carry and forward this request message R(S,T,t) L w[vi][v2]+wlv]lvs]+...+w[vn_][vn] and event messages of the target to vertices he passes by.We (2) call this process is the forwarding process.When T is reduced Formally,our goal is to to zero,user Hi stops this forwarding process,and discards the request message. minL台min wlvv+] (3) In the searcher mode,when a searcher is passing by a vertex, he will post a request messages R(S,T,t)to the vertex. i✉1 Once other users pass by the same vertex,they will detect subject to the memory size si for each vertex v.In this this request message,and know that the searcher S is looking paper,we use the average searching time to measure the for the target T.Using this way,searcher S gets helps from performance of our solution other users.The searcher uses Algorithm 2 to select the next V.DISTRIBUTED SOLUTION neighbor vertex to move.Because S may be a helper for others, he also needs to do step 2,3 in the normal mode. A.The Framework for Mobile Navigation We describe the framework of mobile navigation on the Algorithm 1 The Framework for Mobile Navigation undirected graph G as shown in Algorithm 1.Each user Normal Mode moves from one vertex to another vertex on the graph.Our 1.If user Hi is looking for target T then task is to navigate a searcher S to a moving target T. Jump to Searcher Mode. There exist two kinds of messages in the framework:event 2.When user Hi is passing by vertex vj at time t, message and request message.Each of them is a three tuple. (a).user H;queries all event messages stored on vj, We use E(Hi,vj,t)to represent an event message,and and adds these event messages [E(*,vj,*)to R(S,T,t)to represent a request message,respectively.The Hi's trace table; meaning of these two messages is defined as follows: (b).user Hi posts an event message E (Hi,vj,t)to vj; 1.E (Hi,vj,t):Hi represents a user;vj represents a vertex (c).user Hi queries all request messages stored on vj, on the graph G;t represents the time when the event took and adds these request messages {R(S,T,*)to place.It states that user Hi passed by vertex vj at time t. H,'s help queue. 2.R(S,T,t):S represents a searcher;T represents a target; 3.For each R(S,T,t)in Hi's help queue t represents the time when the request was generated.It states dequeue R(S,T,t); that S wants to look for T at time t. if tnow-t<0t then Combining two operations:post,query with these two kinds T-OR; of messages,users get four ways to communicate with the repeat surrounding RFID tags.They are post event,post request, when Hi is passing by vertex vk, query event and query request.Users use post operations to T=T-1: write event or request messages to the surrounding tags,and (a).Hi posts a request message R(S,T,t)to vk; query operations to read messages from the surrounding tags. (b).Hi selects event messages [E (T,*,*)of Each user has two modes:normal mode and searcher the target T from H!s trace table:then mode.At first,all the users and the potential targets are Hi posts these event messages to vk. working in the normal mode.When the user is looking for a untilT =0. target,he will jump to the searcher mode.The searcher mode Searcher Mode is an escalation state of the normal mode. 1.Step 2,3 in the Normal Mode. In the normal mode,when a user is passing by a vertex,he 2.When passing by vertex vj at time t,searcher S posts will do three things.First,he queries all event messages stored a request message R(S,T,t)to vi. on the vertex and adds them to his trace table,so as to detect 3.Call Algorithm 2 to select the next neighbor vertex. other users'traces.Second,he posts an event message to the 4.When searcher S finds target T, vertex,so as to leave traces of himself for potential searchers Jump to Normal Mode. Third,he queries all request messages stored on the vertex and adds them to his help queue,so as to detect searchers' B.Trace Table and Help Queue request messages. Under the above navigation framework,each user maintains For each request message R(S,T,t)in user Hi's help a trace table to record other users'event messages.Each entry queue,user Hi will make a decision whether to help the in the trace table is a key-value pair.The key of the entry is searcher S to look for the target T.If the current time tno userid which is the identification of a user.The value of the minus the timestamp of the request message t exceeding a entry is an event message list which records the top 0 most given threshold 0(>0),Hi discards the request and does recent traces of the user id,where 0 is a positive threshold nothing.Otherwise H;decides to help the searcher.We define predefined. r for each pair of searcher S and target T.At first,r is In addition,each user also maintains a help queue to record initialized to an given positive threshold 0.As time goes request messages of searchers under the framework.EachL be the total distance which is defined below: L = w[v ′ 1 ][v ′ 2 ] + w[v ′ 2 ][v ′ 3 ] + ... + w[v ′ n−1 ][v ′ n ] (2) Formally, our goal is to min L ⇔ min nX−1 i=1 w[v ′ i ][v ′ i+1] (3) subject to the memory size ≤ si for each vertex v ′ i . In this paper, we use the average searching time to measure the performance of our solution. V. DISTRIBUTED SOLUTION A. The Framework for Mobile Navigation We describe the framework of mobile navigation on the undirected graph G as shown in Algorithm 1. Each user moves from one vertex to another vertex on the graph. Our task is to navigate a searcher S to a moving target T. There exist two kinds of messages in the framework: event message and request message. Each of them is a three tuple. We use E hHi , vj , ti to represent an event message, and R hS, T, ti to represent a request message, respectively. The meaning of these two messages is defined as follows: 1. E hHi , vj , ti: Hi represents a user; vj represents a vertex on the graph G; t represents the time when the event took place. It states that user Hi passed by vertex vj at time t. 2. R hS, T, ti: S represents a searcher; T represents a target; t represents the time when the request was generated. It states that S wants to look for T at time t. Combining two operations: post, query with these two kinds of messages, users get four ways to communicate with the surrounding RFID tags. They are post event, post request, query event and query request. Users use post operations to write event or request messages to the surrounding tags, and query operations to read messages from the surrounding tags. Each user has two modes: normal mode and searcher mode. At first, all the users and the potential targets are working in the normal mode. When the user is looking for a target, he will jump to the searcher mode. The searcher mode is an escalation state of the normal mode. In the normal mode, when a user is passing by a vertex, he will do three things. First, he queries all event messages stored on the vertex and adds them to his trace table, so as to detect other users’ traces. Second, he posts an event message to the vertex, so as to leave traces of himself for potential searchers. Third, he queries all request messages stored on the vertex and adds them to his help queue, so as to detect searchers’ request messages. For each request message R hS, T, ti in user Hi’s help queue, user Hi will make a decision whether to help the searcher S to look for the target T. If the current time tnow minus the timestamp of the request message t exceeding a given threshold θt (θt ≥ 0), Hi discards the request and does nothing. Otherwise Hi decides to help the searcher. We define τ for each pair of searcher S and target T. At first, τ is initialized to an given positive threshold θR. As time goes on, Hi will carry and forward this request message R hS, T, ti and event messages of the target to vertices he passes by. We call this process is the forwarding process. When τ is reduced to zero, user Hi stops this forwarding process, and discards the request message. In the searcher mode, when a searcher is passing by a vertex, he will post a request messages R hS, T, ti to the vertex. Once other users pass by the same vertex, they will detect this request message, and know that the searcher S is looking for the target T. Using this way, searcher S gets helps from other users. The searcher uses Algorithm 2 to select the next neighbor vertex to move. Because S may be a helper for others, he also needs to do step 2, 3 in the normal mode. Algorithm 1 The Framework for Mobile Navigation Normal Mode 1. If user Hi is looking for target T then Jump to Searcher Mode. 2. When user Hi is passing by vertex vj at time t, (a). user Hi queries all event messages stored on vj , and adds these event messages {E h∗, vj , ∗i} to Hi’s trace table; (b). user Hi posts an event message E hHi , vj , ti to vj ; (c). user Hi queries all request messages stored on vj , and adds these request messages {R hS, T, ∗i} to Hi’s help queue. 3. For each R hS, T, ti in Hi’s help queue dequeue R hS, T, ti; if tnow − t < θt then τ = θR; repeat : when Hi is passing by vertex vk, τ = τ − 1; (a). Hi posts a request message R hS, T, ti to vk; (b). Hi selects event messages {E hT, ∗, ∗i} of the target T from H′ i s trace table; then Hi posts these event messages to vk. until τ = 0 . Searcher Mode 1. Step 2, 3 in the Normal Mode. 2. When passing by vertex vj at time t, searcher S posts a request message R hS, T, ti to vj . 3. Call Algorithm 2 to select the next neighbor vertex. 4. When searcher S finds target T, Jump to Normal Mode. B. Trace Table and Help Queue Under the above navigation framework, each user maintains a trace table to record other users’ event messages. Each entry in the trace table is a key-value pair. The key of the entry is user id which is the identification of a user. The value of the entry is an event message list which records the top θk most recent traces of the user id, where θk is a positive threshold predefined. In addition, each user also maintains a help queue to record request messages of searchers under the framework. Each