电 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 to the searcher mode.The searcher mode is an escalation state of next neighbor vertex to move.Because S may be a helper for other the normal mode. users at the same time,he also needs to do steps 2 and 3 in the normal mode. Algorithm 1.The framework for mobile navigation. Normal Mode 4.2.Event table and request queue 1.If user Hi is looking for target T then Jump to Searcher Mode. Under the above navigation framework,each user maintains an 2.When user H is passing by vertex v at time t. event table to record other users'event messages.Each entry in (a)Hi queries all event messages stored on v and adds these the event table is a key-value pair.The key of the entry is user_id event messages (E(*,vj.)to Hi's event table: which is the identification of a user.The value of the entry is an event message list which records the top 6 most recent traces of (b)Hi posts an event message E(Hi.vj.t)to vj: the user_id,where is a positive threshold predefined. (c)H queries all request messages stored on v and adds In addition,each user also maintains a request queue to record these request messages (R(S,T.*)to Hi's request queue. request messages of searchers under the framework.Each entry in 3.For each R(S,T,t)in Hi's request queue the request queue is a request message which gives the identi- fications of searcher and target,also the timestamp of this dequeue R(S,T,t); if tnow-t<0 then message.This request message was firstly posted by the searcher, then other users carry and forward this message without changing T=0R: the timestamp of it.We use a positive time threshold 6 to decide repeat: whether to discard outdated requests. when H is passing by vertex v T=T-1: 4.3.Management of tag storage (a)Hi posts a request message R(S,T,t)to vk: (b)Hi selects event messages (E(T,**)of the target T Ideally.users'trace event messages should be stored on tags as from H's event table;then many as possible.However,the memory size of RFID tag is limited, Hi posts these event messages to vk. we should make full use of these storage resources.Under the until =0. navigation framework,the post operation will write messages to tags Searcher Mode Therefore,a reasonable writing and replacing strategy for post 1.Execute Steps 2 and 3 in the Normal Mode operation should be used.We divide the memory space of tag into 2.When passing by vertex vy at time t,searcher S posts a two segments.Each segment consists of many storage units and the request message R(S,T,t)to v size of each unit is equal to the size of each event message or request 3.Call Algorithm 2 to select the next neighbor vertex. message.Event messages and request messages are stored from 4.When searcher S finds target T, either end of the tag memory space.There are a lot of page Jump to Normal Mode. replacement algorithms in traditional operating system memory management,such as first in first out(FIFO).least recently used (LRU),and optimal page replacement(OPT).In this paper,we pay attention to the consumption rates of tag memory under a different In the normal mode,when a user is passing by a vertex,he will writing and replacing strategy.According to the number of request do three things.First,he queries all event messages stored on the message and event message stored on a tag,the writing and vertex and adds them to his event table,so as to detect other replacing strategy can be divided into the following four categories: users'traces.Second,he posts an event message to the vertex,so as to leave traces of himself for potential searchers.Third,he 1.One Request One Event (OROE):For any request message queries all request messages stored on the vertex and adds them R(S,T,t)on a tag.there is no other request message R(S,T,t') to his request queue,so as to detect searchers'request messages. stored on the same tag which satisfies tt'.In other words,for For each request message R(S,T,t)in user Hi's request queue,user each pair of searcher S and target T,only one request message Hi will make a decision whether to help the searcher S to look for can be stored on a tag.Similarly.for any event message the target T.If the current time thow minus the timestamp of the E(Hi.vi,t)stored on a tag.there is no other event message request message t exceeding a given threshold (r>0).H E(Hi,vi,t')stored on the same tag which satisfies tt'.In other discards the request and does nothing.Otherwise H decides to words,for each pair of user Hi and tag v.only one event help the searcher.We define for each pair of searcher S and message of Hi can be stored on the tag vi. target T.At first,is initialized to a given positive threshold As 2.One Request Many Event (ORME):ORME is similar to OROE.For time goes on,H will carry and forward this request message each pair of searcher S and target T,only one request message R(S,T.t)and event messages of the target to vertices he passes by. can be stored on a tag.However,ORME permits more than one We call this process as the forwarding process.When t is reduced event message E(Hi.vj.*)of Hi to be stored on tag vj. to zero,user H stops this forwarding process,and discards the 3.Many Request One Event(MROE):Different from OROE,MROE request message. permits more than one request message of searcher S and In the searcher mode,when a searcher is passing by a vertex, target T to be stored on a tag.For each pair of user Hi and tag vj he will post a request messages R(S,T,t)to the vertex.Once other only one event message of H can be stored on the tag v users pass by the same vertex,they will detect this request 4.Many Request Many Event(MRME):MRME is the combination of message,and know that the searcher S is looking for the target ORME and MROE.It not only permits more than one request T.If event tables of these"helpers"contain the T's trace,they will message of searcher S and target T to be stored on a tag.but forward T's traces to surrounding RFID tags.Using this way. also permits more than one event message E(Hi.vj.*)of Hi to searcher S gets help from other users.By sufficiently leveraging be stored on tag vj. the "store-and-forward"properties,"crowdsourcing"capabilities can be obtained for navigation.Once the searcher S has collected The choice of writing and replacing strategy is related to many some event message of T.S would use Algorithm 2 to select the factors,such as the tag density in the environment,the number ofto the searcher mode. The searcher mode is an escalation state of 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) Hi queries all event messages stored on vj and adds these event messages fE n; vj; n
g to Hi's event table; (b) Hi posts an event message E Hi; vj;t
to vj; (c) Hi queries all request messages stored on vj and adds these request messages fR Sh ig ; T; n to Hi's request queue. 3. For each R Sh i ; T;t in Hi's request queue dequeue R Sh i ; T;t ; if tnow toθt then τ ¼ θR; repeat: when Hi is passing by vertex vk, τ ¼ τ1; (a) Hi posts a request message R Sh i ; T;t to vk; (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. until τ ¼ 0. Searcher Mode 1. Execute Steps 2 and 3 in the Normal Mode. 2. When passing by vertex vj at time t, searcher S posts a request message R Sh i ; T;t to vj. 3. Call Algorithm 2 to select the next neighbor vertex. 4. When searcher S finds target T, Jump to 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 event 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 request queue, so as to detect searchers' request messages. For each request message R Sh i ; T;t in user Hi's request 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 Z0), 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 a given positive threshold θR. As time goes on, Hi will carry and forward this request message R Sh i ; T;t and event messages of the target to vertices he passes by. We call this process as 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 Sh i ; T;t 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. If event tables of these “helpers” contain the T's trace, they will forward T's traces to surrounding RFID tags. Using this way, searcher S gets help from other users. By sufficiently leveraging the “store-and-forward” properties, “crowdsourcing” capabilities can be obtained for navigation. Once the searcher S has collected some event message of T, S would use Algorithm 2 to select the next neighbor vertex to move. Because S may be a helper for other users at the same time, he also needs to do steps 2 and 3 in the normal mode. 4.2. Event table and request queue Under the above navigation framework, each user maintains an event table to record other users' event messages. Each entry in the event 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 request queue to record request messages of searchers under the framework. Each entry in the request queue is a request message which gives the identi- fications 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. 4.3. Management of tag storage Ideally, users' trace event messages should be stored on tags as many as possible. However, the memory size of RFID tag is limited, we should make full use of these storage resources. Under the navigation framework, the post operation will write messages to tags. Therefore, a reasonable writing and replacing strategy for post operation should be used. We divide the memory space of tag into two segments. Each segment consists of many storage units and the size of each unit is equal to the size of each event message or request message. Event messages and request messages are stored from either end of the tag memory space. There are a lot of page replacement algorithms in traditional operating system memory management, such as first in first out (FIFO), least recently used (LRU), and optimal page replacement (OPT). In this paper, we pay attention to the consumption rates of tag memory under a different writing and replacing strategy. According to the number of request message and event message stored on a tag, the writing and replacing strategy can be divided into the following four categories: 1. One Request One Event (OROE): For any request message R Sh i ; T;t on a tag, there is no other request message R S; T;t 0 h i stored on the same tag which satisfies tat 0 . In other words, for each pair of searcher S and target T, only one request message can be stored on a tag. Similarly, for any event message E Hi; vj;t
stored on a tag, there is no other event message E Hi; vj;t 0
stored on the same tag which satisfies tat 0 . In other words, for each pair of user Hi and tag vj, only one event message of Hi can be stored on the tag vj. 2. One Request Many Event (ORME): ORME is similar to OROE. For each pair of searcher S and target T, only one request message can be stored on a tag. However, ORME permits more than one event message E Hi; vj; n
of Hi to be stored on tag vj. 3. Many Request One Event (MROE): Different from OROE, MROE permits more than one request message of searcher S and target T to be stored on a tag. For each pair of user Hi and tag vj, only one event message of Hi can be stored on the tag vj. 4. Many Request Many Event (MRME): MRME is the combination of ORME and MROE. It not only permits more than one request message of searcher S and target T to be stored on a tag, but also permits more than one event message E Hi; vj; n
of Hi to be stored on tag vj. The choice of writing and replacing strategy is related to many factors, such as the tag density in the environment, the number of 82 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89