V18 office rooms 22d A:searcher;B:torget;H_C,H_D:helper;:RFID tog (a)A simplified single floor plan of the indoor environment (b)Graph of the RFID-based dealy tolerant network network Fig.1.An overview of the indoor navigation scheme using RFID-based delay tolerant network walking trail.The user's trail is periodically reported to for the target T.As time goes on,when a helper H detects escort server.To correct user's position diverging from his the request message,the helper will know S is looking for T. actual location,audio beacons are placed in the building as a The helper H has two ways to help the searcher.One way reference frame.Encounter between two mobile phones,and is to post this request message to surrounding tags which he encounter between the mobile phone and the beacon will both will pass by.Thus more users may detect the request and give be reported to the escort server.Escort server utilizes user's help to the searcher,The other way is to post event messages walking trail and encounters to compute the current position of the target T detected by H to more tags.The searcher S of each user and routing directions.Being different from the continuously detects event messages about the target T,and previous works,we focus on the problem of navigating to a adjusts his movement direction until he meets the target at moving target using RFID-based delay tolerant network. some place. Our goal is to design a time efficient approach to navigate III.SYSTEM OVERVIEW a searcher to a moving target in indoor environment.There Figure la shows the envisioned application scenario for our are two challenges in the problem.One is that the target is RFID-based delay tolerant network navigation scheme.The in the movement.In the RFID-based delay tolerant network. mobile users can actively interrogate the surrounding tags with there is no central server which can record each user's position tiny devices like smart phones and leave messages to the tags.in real time.The target's position information is stored in Those tags act as landmarks for localization,so the placement tags which are distributed in the environment.This is the of them are very important.In order to save labor costs of tag main difference between our navigation scheme and the escort deployment without reducing the quality of navigation,we can [14].The other challenge is that the storage capacity of RFID deploy RFID tags in key locations,such as door of each office tags is limited.The operation of posting message needs to be room,meeting room and washing room.In addition,some managed reasonably. public locations also need to be deployed with tags,such as corners of corridor,elevators and entrances of building. IV.PROBLEM ANALYSIS Each interrogator carried by the user in our scheme has two kinds of operations:post and query.Interrogator uses post We analyse the problem of locating and navigating to a specified mobile user within the indoor environment on a operation to write messages to tags,and uses query operation to read messages from tags.For example,when a user reaches undirected graph G=(V,E).The undirected graph is an an office room,the user can post an event message to the abstraction of the RFID tag location reference frame,for surrounding tags through the interrogator.This event message example,Figure 1b.V is the set of vertices.Each vertex viE V represents a tag in the frame.Each vertex vi carries states that the user has been here before.At the same time, the user can also query other users'event messages from the a positive value si which is the memory size of the tag.E surrounding tags,so as to detect other users'traces. is the set of edges.If two vertices viV and vj EV are There exist three types of roles in our scheme:searcher, adjacent in physical space,there is an edge (v;,v;)between farget and helper.Each user is a helper for others.Specially, vertex v:and vertex vj.Each edge (vi,vj)carries a positive a user can also be a searcher if he or she is looking for another value wv]which is the distance between the two vertices user.Coincidentally,if he or she is also a target of others,the connected by the edge. user will have the third role as a target. On the graph G,we want to find the optimal vertex sequence Suppose a searcher S is looking for a target T.At first, (i,2,,n),(,+1)∈E,1≤i≤n-1 (1) the searcher doesn't know the position of target.Searcher S queries the surrounding tags to detect the target T's event where vf is the current location of the searcher S,and v is messages.Besides,searcher S also posts request message to the finally location where the searcher found the target T,so the surrounding tags which states that searcher S is looking as to minimize the total distance of the vertex sequence.Let(a) A simplified single floor plan of the indoor environment (b) Graph of the RFID-based dealy tolerant network network Fig. 1. An overview of the indoor navigation scheme using RFID-based delay tolerant network walking trail. The user’s trail is periodically reported to escort server. To correct user’s position diverging from his actual location, audio beacons are placed in the building as a reference frame. Encounter between two mobile phones, and encounter between the mobile phone and the beacon will both be reported to the escort server. Escort server utilizes user’s walking trail and encounters to compute the current position of each user and routing directions. Being different from the previous works, we focus on the problem of navigating to a moving target using RFID-based delay tolerant network. III. SYSTEM OVERVIEW Figure 1a 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 operation 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 doesn’t 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 S is looking for T. The helper H has two ways to help the searcher. One way is to post this request message to surrounding 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 movement. 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 [14]. The other challenge is that the storage capacity of RFID tags is limited. The operation of posting message needs to be managed reasonably. IV. PROBLEM ANALYSIS We analyse the problem of locating and navigating to a specified mobile user within the indoor environment on a undirected graph G = (V, E). The undirected graph is an abstraction of the RFID tag location reference frame, for example, Figure 1b. V is the set of vertices. Each vertex vi ∈ V 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 ∈ V and vj ∈ V 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 distance between the two vertices connected by the edge. On the graph G, we want to find the optimal vertex sequence hv ′ 1 , v′ 2 , ..., v′ n i, (v ′ i , v′ i+1) ∈ E, 1 ≤ i ≤ n − 1 (1) where v ′ 1 is the current location of the searcher S, and v ′ n is the finally location where the searcher found the target T, so as to minimize the total distance of the vertex sequence. Let