H.Ji et al Journal of Network and Computer Applications 52 (2015)79-89 81 b V15 V17 office rooms V HC 4“ 0. office rooms d V22 29 V26 A:searcher;B:target;H_C,H_D:helper;:RFID tag Fig.1.An overview of the indoor navigation scheme using RFID-based delay tolerant network.(a)A simplified single floor plan of the indoor environment.(b)Graph of the RFID-based delay tolerant network. and integrity of position.Client node detects object's location challenges in the problem.One is that the target is in the move- information and periodically reports it to a center server node.They ment.In the RFID-based delay tolerant network,there is no central can monitor the whole objects'locations and movement behaviors in server which can record each user's position in real time.The real-time.In fact,the cost of constructing such a centralized naviga- target's position information is stored in tags which are distributed tion architecture system is always high.Communication between in the environment.This is the main difference between our client node and server node is highly energy-consuming.In order to navigation scheme and the escort (Constandache et al..2010) overcome the above drawbacks,we propose a novel distributed The other challenge is that the storage capacity of RFID tags is indoor navigation architecture which uses RFID-based delay tolerant limited.The operation of posting message needs to be managed network.Objects'location information are stored on surrounding reasonably. tags and no centralized server exists in the system. Figure 1(a)shows the envisioned application scenario for our RFID-based delay tolerant network navigation scheme.The mobile users can actively interrogate the surrounding tags with tiny 4.Distributed solution devices like smart phones and leave messages to the tags.Those 4.1.The framework for mobile navigation tags act as landmarks for localization,so the placement of them are very important.In order to save labor costs of tag deployment without reducing the quality of navigation,we can deploy RFID tags We define a undirected graph G=(V.E)which is an abstraction in key locations,such as door of each office room,meeting room of the RFID tag location reference frame,for example,Fig.1(b).V is and washing room.In addition,some public locations also need to the set of vertices.Each vertex v;e V represents a tag in the frame. Each vertex v carries a positive value s which is the memory size of be deployed with tags,such as corners of corridor,elevators and entrances of building. the tag.E is the set of edges.If two vertices viev and viev are Each interrogator carried by the user in our scheme has two adjacent in physical space,there is an edge (vi.vj)between vertex vi kinds of operations:post and query.Interrogator uses post opera- and vertex v.Each edge (vi.v)carries a positive value w[villvi] tion to write messages to tags,and uses query operation to read which is the physical distance between the two vertices connected messages from tags.For example,when a user reaches an office by the edge. room,the user can post an event message to the surrounding tags We describe the framework of mobile navigation on the through the interrogator.This event message states that the user undirected graph G as shown in Algorithm 1.Each user moves has been here before.At the same time,the user can also query from one vertex to another vertex on the graph.Our task is to other users'event messages from the surrounding tags,so as to navigate a searcher S to a moving target T.There exist two kinds of detect other users'traces. messages in the framework:event message and request message. There exist three types of roles in our scheme:searcher,target Each of them is a three tuple.We use E(Hi,vi,t)to represent an and helper.Each user is a helper for others.Specially,a user can event message,and R(S.T,t)to represent a request message.The also be a searcher if he or she is looking for another user. meaning of these two messages is defined as follows: Coincidentally,if he or she is also a target of others,the user will have the third role as a target. 1.E(Hi,vi,t):Hi represents a user:v represents a vertex on the Suppose a searcher s is looking for a target T.At first,the graph G;t represents the time when the event took place.It searcher does not know the position of target.Searcher S queries states that user H passed by vertex v,at time t. the surrounding tags to detect the target T's event messages. 2.R(S,T,t):S represents a searcher;T represents a target;t Besides,searcher s also posts request message to the surrounding represents the time when the request was generated.It states tags which states that searcher S is looking for the target T.As time that S wants to look for T at time t. goes on,when a helper H detects the request message,the helper will know that S is looking for T.The helper H has two ways to help Combining two operations,post,query with these two kinds of the searcher.One way is to post this request message to surround- messages,users get four ways to communicate with the surround- ing tags which he will pass by.Thus more users may detect the ing RFID tags.They are post event,post request,query event and request and give help to the searcher.The other way is to post event query request.Users use post operations to write event or request messages of the target T detected by H to more tags.The searcher S messages to the surrounding tags,and query operations to read continuously detects event messages about the target T,and adjusts messages from the surrounding tags. his movement direction until he meets the target at some place. Each user has two modes:normal mode and searcher mode. Our goal is to design a time efficient approach to navigate a At first,all the users and the potential targets are working in the searcher to a moving target in indoor environment.There are two normal mode.When the user is looking for a target,he will jumpand integrity of position. Client node detects object's location information and periodically reports it to a center server node. They can monitor the whole objects' locations and movement behaviors in real-time. In fact, the cost of constructing such a centralized naviga￾tion architecture system is always high. Communication between client node and server node is highly energy-consuming. In order to overcome the above drawbacks, we propose a novel distributed indoor navigation architecture which uses RFID-based delay tolerant network. Objects' location information are stored on surrounding tags and no centralized server exists in the system. Figure 1(a) shows the envisioned application scenario for our RFID-based delay tolerant network navigation scheme. The mobile users can actively interrogate the surrounding tags with tiny devices like smart phones and leave messages to the tags. Those tags act as landmarks for localization, so the placement of them are very important. In order to save labor costs of tag deployment without reducing the quality of navigation, we can deploy RFID tags in key locations, such as door of each office room, meeting room and washing room. In addition, some public locations also need to be deployed with tags, such as corners of corridor, elevators and entrances of building. Each interrogator carried by the user in our scheme has two kinds of operations: post and query. Interrogator uses post opera￾tion to write messages to tags, and uses query operation to read messages from tags. For example, when a user reaches an office room, the user can post an event message to the surrounding tags through the interrogator. This event message states that the user has been here before. At the same time, the user can also query other users' event messages from the surrounding tags, so as to detect other users' traces. There exist three types of roles in our scheme: searcher, target and helper. Each user is a helper for others. Specially, a user can also be a searcher if he or she is looking for another user. Coincidentally, if he or she is also a target of others, the user will have the third role as a target. Suppose a searcher S is looking for a target T. At first, the searcher does not know the position of target. Searcher S queries the surrounding tags to detect the target T's event messages. Besides, searcher S also posts request message to the surrounding tags which states that searcher S is looking for the target T. As time goes on, when a helper H detects the request message, the helper will know that S is looking for T. The helper H has two ways to help the searcher. One way is to post this request message to surround￾ing tags which he will pass by. Thus more users may detect the request and give help to the searcher. The other way is to post event messages of the target T detected by H to more tags. The searcher S continuously detects event messages about the target T, and adjusts his movement direction until he meets the target at some place. Our goal is to design a time efficient approach to navigate a searcher to a moving target in indoor environment. There are two challenges in the problem. One is that the target is in the move￾ment. In the RFID-based delay tolerant network, there is no central server which can record each user's position in real time. The target's position information is stored in tags which are distributed in the environment. This is the main difference between our navigation scheme and the escort (Constandache et al., 2010). The other challenge is that the storage capacity of RFID tags is limited. The operation of posting message needs to be managed reasonably. 4. Distributed solution 4.1. The framework for mobile navigation We define a undirected graph G ¼ ðV; EÞ which is an abstraction of the RFID tag location reference frame, for example, Fig. 1(b). V is the set of vertices. Each vertex vi AV represents a tag in the frame. Each vertex vi carries a positive value si which is the memory size of the tag. E is the set of edges. If two vertices vi AV and vj AV are adjacent in physical space, there is an edge ðvi; vjÞ between vertex vi and vertex vj. Each edge ðvi; vjÞ carries a positive value w½vi½vj which is the physical distance between the two vertices connected by the edge. 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 Hi; vj;t
to represent an event message, and R Sh i ; T;t to represent a request message. The meaning of these two messages is defined as follows: 1. E Hi; vj;t
: 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 Sh i ; T;t : 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 surround￾ing 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 Fig. 1. An overview of the indoor navigation scheme using RFID-based delay tolerant network. (a) A simplified single floor plan of the indoor environment. (b) Graph of the RFID-based delay tolerant network. H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89 81