Globecom 2013-Ad Hoc and Sensor Networking Symposium An Efficient Indoor Navigation Scheme Using RFID-based Delay Tolerant Network Hao Ji,Lei Xie,Yafeng Yin,Sanglu Lu State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing,China Email:jiqiusheng@dislab.nju.edu.cn,Ixie@nju.edu.cn,yyf@dislab.nju.edu.cn,sanglu@nju.edu.cn Abstract-As a supporting technology for most pervasive important problem is how to locate and navigate to a specified applications,indoor localization and navigation has attracted mobile user.For example,when a baby or a dog is lost in extensive attention in recent years.Conventional solutions mainly a shopping mall,how to quickly locate and navigate to the leverage techniques like WiFi,cellular network etc.to effectively locate the user for indoor localization and navigation.In this mobile target?Obviously,the mobile target can only passively paper,we investigate into the problem of indoor navigation by leave some traces in the environment through the equipped using the RFID-based delay tolerant network.Being different NFC or bluetooth modules.It cannot actively propagate its cur- from the previous work,we aim to efficiently locate and navigate rent position directly to the searchers.Besides,time-efficiency to a specified mobile user who is continuously moving within the indoor environment.We respectively propose a framework is very critical to the searchers,since the less time to use,the to schedule the tasks and manage the resources in the network more opportunities to find the target. and a navigation algorithm to locate and navigate to the moving Therefore,it is essential to devise a time-efficient navigation target.Experiment results show that our solution can efficiently scheme by using the RFID-based delay tolerant network.In reduce the average searching time for indoor navigation. this paper,we first propose a framework to schedule the I.INTRODUCTION tasks and manage the resources in this network.Furthermore, we propose a navigation algorithm to locate and navigate to As the rapid proliferation of pervasive applications in indoor environment,a lot of location-based services and context- the moving target.The main contributions of this paper are aware services are put forward,in which location is viewed summarized as follows: as one of the most significant factors.For most applications, We propose a framework leveraging RFID-based de- it is required to provide an accurate location for the specified lay tolerant network for localization and navigation.By objects.However,the current mature technology like global sufficiently leveraging the"store-and-forward"properties position system (GPS)can only be used in the outdoor of the delay tolerant network,our solution provides an environment for localization,several issues like the multi-path effective mechanism for navigation using "crowdsourc- effect and severe path loss make the indoor localization a lot ing"capabilities.By effectively scheduling the tasks and more complicated than the outdoor situation.Therefore,a lot managing the limited resources in the tags,the system can of research works have focused on localization and navigation provide navigation services for a large number of users. schemes for indoor environment [1-7].Most of the solutions We propose a time-efficient scheme to locate and navigate are rather complicated and fairly expensive. to a mobile target who is continuously moving.According Recent technological advances have enabled the develop- to the latest obtained spots of appearance,our solution ment of low-cost,low-power devices [8-9].RFID,as a novel navigates the searcher to the most possible region of the technology for automatic identification,provides us with a target,which achieves a good performance in terms of new opportunity for indoor localization and navigation.For the time-efficiency. example,the low-cost RFID tags can be widely deployed II.RELATED WORK inside the indoor environment and act as landmarks for lo- calization.Since current smart phones can be equipped with Many research works use RFID technology for indoor near field communication (NFC)or bluetooth modules,which localization [10-13].LANDMARC [10]is a tag localization prototype in indoor environment.By utilizing extra fixed can effectively communicate with the active/passive tags,the mobile users can actively interrogate the surrounding tags with location reference tags to help location calibration,it can tiny devices like smart phones and leave messages or traces increase location accuracy without deploying large numbers to the tags.In this way,the RFID-based infrastructure forms a of RFID readers.Zhu et al.propose an fault-tolerant RFID delay tolerant network.As the scanning range of RFID system reader localization approach to solve the problem of frequent is usually no more than 5m.the system can effectively locate occurred RFID faults [13].Moreover,they also propose the index to measure the quality of a localization result. the users by limiting the positioning error to at most 5m. Escort [14]is an office environment localization and navi- In conventional indoor applications,the users are contin- uously moving within the indoor environment.Then.one gation system which uses client/server architecture.The client running on the user-carried mobile phones periodically mea- Corresponding Author:Dr.Lei Xie,Ixie@nju.edu.cn sures the value of accelerometer and compass of the user's 978-1-4799-1353-4/13/$31.00©20131EEE 183
An Efficient Indoor Navigation Scheme Using RFID-based Delay Tolerant Network Hao Ji, Lei Xie, Yafeng Yin, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Email: jiqiusheng@dislab.nju.edu.cn, lxie@nju.edu.cn, yyf@dislab.nju.edu.cn, sanglu@nju.edu.cn Abstract—As a supporting technology for most pervasive applications, indoor localization and navigation has attracted extensive attention in recent years. Conventional solutions mainly leverage techniques like WiFi, cellular network etc. to effectively locate the user for indoor localization and navigation. In this paper, we investigate into the problem of indoor navigation by using the RFID-based delay tolerant network. Being different from the previous work, we aim to efficiently locate and navigate to a specified mobile user who is continuously moving within the indoor environment. We respectively propose a framework to schedule the tasks and manage the resources in the network and a navigation algorithm to locate and navigate to the moving target. Experiment results show that our solution can efficiently reduce the average searching time for indoor navigation. I. INTRODUCTION As the rapid proliferation of pervasive applications in indoor environment, a lot of location-based services and contextaware services are put forward, in which location is viewed as one of the most significant factors. For most applications, it is required to provide an accurate location for the specified objects. However, the current mature technology like global position system (GPS) can only be used in the outdoor environment for localization, several issues like the multi-path effect and severe path loss make the indoor localization a lot more complicated than the outdoor situation. Therefore, a lot of research works have focused on localization and navigation schemes for indoor environment [1-7]. Most of the solutions are rather complicated and fairly expensive. Recent technological advances have enabled the development of low-cost, low-power devices [8-9]. RFID, as a novel technology for automatic identification, provides us with a new opportunity for indoor localization and navigation. For example, the low-cost RFID tags can be widely deployed inside the indoor environment and act as landmarks for localization. Since current smart phones can be equipped with near field communication (NFC) or bluetooth modules, which can effectively communicate with the active/passive tags, the mobile users can actively interrogate the surrounding tags with tiny devices like smart phones and leave messages or traces to the tags. In this way, the RFID-based infrastructure forms a delay tolerant network. As the scanning range of RFID system is usually no more than 5m, the system can effectively locate the users by limiting the positioning error to at most 5m. In conventional indoor applications, the users are continuously moving within the indoor environment. Then, one Corresponding Author: Dr. Lei Xie, lxie@nju.edu.cn important problem is how to locate and navigate to a specified mobile user. For example, when a baby or a dog is lost in a shopping mall, how to quickly locate and navigate to the mobile target? Obviously, the mobile target can only passively leave some traces in the environment through the equipped NFC or bluetooth modules. It cannot actively propagate its current position directly to the searchers. Besides, time-efficiency is very critical to the searchers, since the less time to use, the more opportunities to find the target. Therefore, it is essential to devise a time-efficient navigation scheme by using the RFID-based delay tolerant network. In this paper, we first propose a framework to schedule the tasks and manage the resources in this network. Furthermore, we propose a navigation algorithm to locate and navigate to the moving target. The main contributions of this paper are summarized as follows: • We propose a framework leveraging RFID-based delay tolerant network for localization and navigation. By sufficiently leveraging the “store-and-forward” properties of the delay tolerant network, our solution provides an effective mechanism for navigation using “crowdsourcing” capabilities. By effectively scheduling the tasks and managing the limited resources in the tags, the system can provide navigation services for a large number of users. • We propose a time-efficient scheme to locate and navigate to a mobile target who is continuously moving. According to the latest obtained spots of appearance, our solution navigates the searcher to the most possible region of the target, which achieves a good performance in terms of the time-efficiency. II. RELATED WORK Many research works use RFID technology for indoor localization [10-13]. LANDMARC [10] is a tag localization prototype in indoor environment. By utilizing extra fixed location reference tags to help location calibration, it can increase location accuracy without deploying large numbers of RFID readers. Zhu et al. propose an fault-tolerant RFID reader localization approach to solve the problem of frequent occurred RFID faults [13]. Moreover, they also propose the index to measure the quality of a localization result. Escort [14] is an office environment localization and navigation system which uses client/server architecture. The client running on the user-carried mobile phones periodically measures the value of accelerometer and compass of the user’s Globecom 2013 - Ad Hoc and Sensor Networking Symposium 978-1-4799-1353-4/13/$31.00 ©2013 IEEE 183
Globecom 2013-Ad Hoc and Sensor Networking Symposium 4 W12 V otfice rooms 0 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 operation to write messages to tags,and uses query operation specified mobile user within the indoor environment on a undirected graph G =(V,E).The undirected graph is an to read messages from tags.For example,when a user reaches 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 vi V and vj EV are There exist three types of roles in our scheme:searcher. adjacent in physical space,there is an edge (vi,vj)between target and helper.Each user is a helper for others.Specially, vertex vi and vertex vj.Each edge (v,vj)carries a positive a user can also be a searcher if he or she is looking for another value wvlv 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. On the graph G,we want to find the optimal vertex sequence user will have the third role as a target. Suppose a searcher S is looking for a target T.At first, (,2,,vn),(,+1)∈E,1≤i≤n-1(I) 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 184
(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 Globecom 2013 - Ad Hoc and Sensor Networking Symposium 184
Globecom 2013-Ad Hoc and Sensor Networking Symposium L be the total distance which is defined below: on,Hi will carry and forward this request message R(S,T,t) and event messages of the target to vertices he passes by.We L w[vi][v2]wlv2][vs]+...+wlvn]vn] (2) call this process is the forwarding process.Whenr is reduced Formally,our goal is to to zero,user Hi stops this forwarding process,and discards the request message. minL台min w[+] (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. 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 H;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. Hi'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=8R: 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 v: 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 vj. 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 tnou user id 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 most given threshold 0(0),Hi discards the request and does recent traces of the user id,where 0k is a positive threshold nothing.Otherwise H;decides to help the searcher.We define predefined. T 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 0R.As time goes request messages of searchers under the framework.Each 185
L 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 Globecom 2013 - Ad Hoc and Sensor Networking Symposium 185
Globecom 2013-Ad Hoc and Sensor Networking Symposium entry in the help queue is a request message which gives location of the target is v17.Then vertex v11 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;vs:d; V=(M,2,,Vm: messages is less than A,then E(Hi,vj,t)will be written to U=(1,u2,,un:T=(t1,t2,,tn） vj.Otherwise,the oldest event message of Hi stored on v; Output:next neighbor inert to move 1: will be replaced with E (Hi,vi,t). Calculate all vertices pairs'shortest path length Situation 2.Normal Mode 3(a)Each tag maintains at on graph G using algorithm such as Floyd-Warshall or 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, then the timestamp t'will be updated to t.No extra memory 3:Qi Tnow- 4:end for space will be used.Besides,we take the same strategy in Searcher Mode step 2. 5a==1 6:for each neighbor vV of vs do Situation 3.Normal Mode 3(b)Because there are many 7: helpers in the system,if all of them post messages to a vertex fy)=dlyl+∑g×dlv;llui 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,tno is the current time;vs 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 dlvllv']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<0)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,1,ti）,E(T,2,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=(u1,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 vs,we define a cost function f(vj) 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 ai/o 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)=wuyl+∑a4 ×d[yllu (4) to select the next neighbor vertex to move.A simple way i=la 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 v3,and the latest appearance equals to1;n=3:V=(2,v4,v11,21）,U=(17,U18,19 186
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, Globecom 2013 - Ad Hoc and Sensor Networking Symposium 186
Globecom 2013-Ad Hoc and Sensor Networking Symposium I=(4,3,1),the current time tno=5.Then vertex v11 will region.The center of the circle is the user's initial position and be selected as the next intermediate vertex.Because the cost the radius of the circle obeys a normal distribution N(μ，62)， of v is 7.57 which is less than the cost of v2,v4 or v21. where u is the expectation of radius.The stay time of each user obeys a truncated power-law distribution p(t)=Cxt-2.5(s). (5 <t 60).Parameters used in the experiments are showed in Table 1.For all figures presented,we run the simulation 1,000 times to get average values. Table 1.Parameters used in the simulation Parameter Description Value m number of users 50..,500 8R(S) time to live of request message 10,.,200 k number of event message 1,.,10 4(m) expectation of region radius 6..,60 Fig.2.Select the next position (vertex)and move to a target region B.Experiments Result VI.PERFORMANCE EVALUATION 1)Average Searching Time:In Figure 3a,3b,we plot the average searching time of three solutions under two mobility We implement a simulator in Java to simulate the navigation models with different numbers of users.We guarantee that process,thus to evaluate the performance of our solution.We the inputs of users'movement behaviors for each solution are conduct the simulation based on a 30 x 30 grid-graph.Each the same.As we can see from these 2 subfigures,with the vertex on the graph represents a tag in the RFID-based delay number of users increasing,the average searching time of our tolerant network.In addition to the boundary vertices,each solution is reduced gradually.When increasing the number of vertex has four neighbor vertices.To simulate the movement users from 50 to 500,our solution's average searching time behaviors of users on the graph,we use two classical human is reduced from 742/487 seconds to 226/234 seconds.While mobility models [15.161. the average searching time of blind navigation or centralized We compare the performance of our solution with two other navigation is essentially unchanged.This is consistent with our solutions:blind navigation solution and centralized navigation intuition that more users means more helpers for the searcher. solution by the average searching time.In blind navigation In Figure 3c,3d,we plot the average searching time of solution,searcher randomly selects a vertex on the graph our solution under two mobility models with different values and moves to the vertex with shortest path.If the searcher of 0r and 0.When the value of 0R is small,the average doesn't find the target on the path,then the searcher will searching time is large.Because only a few number of users repeat the above process until he finds the target.In centralized could receive request messages and the searcher gets little help solution,we suppose that the searcher can obtain the target's from others.When increasing the value of og from 10 seconds current position in real time.The searcher always moves to the to 200 seconds,the average searching time is reduced more neighbor vertex which is nearest to the target.In this paper, than 30%.Different from 0R,the impact of is little.When we regard the centralized solution as the approximate optimal the value of is 1,5 under RW or 1,3,9 under RWP,the solution and the blind navigation solution as the worst solution. average searching time is slightly smaller than others. In Figure 3e,we plot the average searching time of our so- A.Experiments Settings lution under RWP with different localities of users'movement At the beginning of the simulation,we randomly select a behaviors.When the value of u is less than 12,users move vertex on the 30 x 30 grid-graph for each user as the user's in a small region.The request messages of searcher spread initial position.All the users are limited to move on the edges slowly.Thus it takes a long time for the searcher to detect the of the grid-graph.The length of each edge is 4 m.In order to target's traces,and the average searching time is large.When avoid situation that searcher never catches up with the target, the locality of users'movements is week,sayμ≥30，the we assign the movement speed of the searcher is 2 m/s and movement region of the target is large.So.it is also difficult other users'are 1 m/s.If searcher and the target happen to be for the searcher to find the target.We find that when u is 20 on the same edge,we think the searcher has found the target.the average searching time is the smallest. To simulate the movement behaviors of users,we use a 2)Number of Messages:In Figure 3f,we plot the average simplified Random Walk Mobility Model(RW)and a Random number of messages stored in the delay tolerant network as Way-Point Mobility Model(RWP).Under the random walk time grows.The number of request messages under RWP is mobility model,whenever a user reaches a vertex,the user sightly smaller than RW.When the time is about 200(s), will randomly select a neighbor vertex to move.Under the the number of request messages reaches its maximum.The random way-point mobility model,each user randomly selects number decreases as the request message's time to live is a vertex within a local region on the graph and moves to the reduced to zero.The number of event messages grows fast vertex with shortest path.When arriving at the vertex,the user between 150(s)to 350(s).After 400(s),the number of event will stay on the vertex for a period of time,then repeat the messages is essentially unchanged.Because no more request above process.We use a circular region to describe such a local messages are generated after that. 187
Γ = h4, 3, 1i, the current time tnow = 5. Then vertex v11 will be selected as the next intermediate vertex. Because the cost of v11 is 7.57 which is less than the cost of v2, v4 or v21. Fig. 2. Select the next position (vertex) and move to a target region VI. PERFORMANCE EVALUATION We implement a simulator in Java to simulate the navigation process, thus to evaluate the performance of our solution. We conduct the simulation based on a 30 × 30 grid-graph. Each vertex on the graph represents a tag in the RFID-based delay tolerant network. In addition to the boundary vertices, each vertex has four neighbor vertices. To simulate the movement behaviors of users on the graph, we use two classical human mobility models [15, 16]. We compare the performance of our solution with two other solutions: blind navigation solution and centralized navigation solution by the average searching time. In blind navigation solution, searcher randomly selects a vertex on the graph and moves to the vertex with shortest path. If the searcher doesn’t find the target on the path, then the searcher will repeat the above process until he finds the target. In centralized solution, we suppose that the searcher can obtain the target’s current position in real time. The searcher always moves to the neighbor vertex which is nearest to the target. In this paper, we regard the centralized solution as the approximate optimal solution and the blind navigation solution as the worst solution. A. Experiments Settings At the beginning of the simulation, we randomly select a vertex on the 30 × 30 grid-graph for each user as the user’s initial position. All the users are limited to move on the edges of the grid-graph. The length of each edge is 4 m. In order to avoid situation that searcher never catches up with the target, we assign the movement speed of the searcher is 2 m/s and other users’ are 1 m/s. If searcher and the target happen to be on the same edge, we think the searcher has found the target. To simulate the movement behaviors of users, we use a simplified Random Walk Mobility Model (RW) and a Random Way-Point Mobility Model(RWP). Under the random walk mobility model, whenever a user reaches a vertex, the user will randomly select a neighbor vertex to move. Under the random way-point mobility model, each user randomly selects a vertex within a local region on the graph and moves to the vertex with shortest path. When arriving at the vertex, the user will stay on the vertex for a period of time, then repeat the above process. We use a circular region to describe such a local region. The center of the circle is the user’s initial position and the radius of the circle obeys a normal distribution N(µ, 6 2 ), where µ is the expectation of radius. The stay time of each user obeys a truncated power-law distribution p(t) = C ×t −2.5 (s), (5 ≤ t ≤ 60). Parameters used in the experiments are showed in Table 1. For all figures presented, we run the simulation 1,000 times to get average values. Table 1. Parameters used in the simulation Parameter Description Value m number of users [50, ..., 500] θR (s) time to live of request message [10, ..., 200] θk number of event message [1, ..., 10] µ (m) expectation of region radius [6, ..., 60] B. Experiments Result 1) Average Searching Time: In Figure 3a, 3b, we plot the average searching time of three solutions under two mobility models with different numbers of users. We guarantee that the inputs of users’ movement behaviors for each solution are the same. As we can see from these 2 subfigures, with the number of users increasing, the average searching time of our solution is reduced gradually. When increasing the number of users from 50 to 500, our solution’s average searching time is reduced from 742/487 seconds to 226/234 seconds. While the average searching time of blind navigation or centralized navigation is essentially unchanged. This is consistent with our intuition that more users means more helpers for the searcher. In Figure 3c, 3d, we plot the average searching time of our solution under two mobility models with different values of θR and θk. When the value of θR is small, the average searching time is large. Because only a few number of users could receive request messages and the searcher gets little help from others. When increasing the value of θR from 10 seconds to 200 seconds, the average searching time is reduced more than 30%. Different from θR, the impact of θk is little. When the value of θk is 1, 5 under RW or 1, 3, 9 under RWP, the average searching time is slightly smaller than others. In Figure 3e, we plot the average searching time of our solution under RWP with different localities of users’ movement behaviors. When the value of µ is less than 12, users move in a small region. The request messages of searcher spread slowly. Thus it takes a long time for the searcher to detect the target’s traces, and the average searching time is large. When the locality of users’ movements is week, say µ ≥ 30, the movement region of the target is large. So, it is also difficult for the searcher to find the target. We find that when µ is 20 the average searching time is the smallest. 2) Number of Messages: In Figure 3f, we plot the average number of messages stored in the delay tolerant network as time grows. The number of request messages under RWP is sightly smaller than RW. When the time is about 200 (s), the number of request messages reaches its maximum. The number decreases as the request message’s time to live is reduced to zero. The number of event messages grows fast between 150 (s) to 350 (s). After 400 (s), the number of event messages is essentially unchanged. Because no more request messages are generated after that. Globecom 2013 - Ad Hoc and Sensor Networking Symposium 187
Globecom 2013-Ad Hoc and Sensor Networking Symposium 250 2500 400 0c0 280 20 2 大 220 101020m20t30a040o0450 20 (aRW,0r=200(s）,0k=10 (b)RWP,0r=200(s).0k=10.4=18(m) (c)m=450.0k=10.u=18(m) 30 -Random Walk (RW) ent message(W的 300 20d 21 1000 210 20 0 200 2 100 200 309e00 500 600 00 (dm=450.0R=200(s),4=18(m) (e)RWPm=450.0R=200(s),0k=10 (①m=450,0R=200(s),0k=10.4=18(m) Fig.3.Comparison of the average searching time under Random Walk Mobility Model(RW)and Random Way-Point Mobility Model(RWP)with differen parameters (number of users m:time to live of request message 6R:number of event messages 6:expectation of movement region radius u). VII.CONCLUSION [5]J.Biswas.and M.Veloso,"Wifi localization and navigation for au- tonomous indoor mobile robots,"In Proc./CRA,Anchorage,Alaska, This paper proposes a framework using RFID-based delay USA.May2010,Pp.4379-4384. tolerant network for indoor navigation.By sufficiently leverag- [6]X.Jiang,C.-J.M.Liang,F.Zhao,K.Chen,J.Hsu,B.Zhang,and J. ing the store-forward properties of delay tolerant network,our Liu."Demo:Creating interactive virtual zones in physical space with magnetic-induction,"in Proc.SenSys.Seattle,WA.USA.Nov.2011.pp. solution provides an effective mechanism for indoor naviga- 431.432. tion.Simulation results show that our solution can efficiently [7]X.Jiang.C.-J.M.Liang,K.Chen,B.Zhang,J.Hsu,J.Liu,B.Cao,and reduce the average searching time of navigation.We discuss F.Zhao,"Design and evaluation of a wireless magnetic-based proximity detection platform for indoor applications,"in Proc.IPSN,Beijing the influences of different mobility parameters in the end. China,April 2012,pp.221-232. [8]L.Xie,B.Sheng,C.Tan,H.Han,Q.Li and D.X.Chen,"Efficient VIII.ACKNOWLEDGEMENT tag identification in mobile RFID systems,"in Proc.INFOCOM,San Diego,CA.USA.March 2010.pp.1-9. This work is partially supported by the National Ba- [9]L.Xie.Q.Li.X.Chen,S.L.Lu and D.X.Chen."Continuous Scanning sic Research Program of China (973)under Grant No. with Mobile Reader in RFID Systems:an Experimental Study,"in MobiHoc,Bangalore,India,Aug.2013. 2009CB320705;the National Natural Science Foundation [10]L.M.Ni,Y.Liu,Y.C.Lau,and A.P.Patil."LANDMARC:indoor of China under Grant No.61100196.61073028.61021062. location sensing using active RFID,"Wireless Nerworks,vol.10,no.6, Pp.701-710,Nov.2004. 91218302;the JiangSu Natural Science Foundation under [11]H.J.Lee and M.C.Lee,"Localization of mobile robot based on Grant No.BK2011559. radio frequency identification devices,"in International Joint Conference S/CE-/CASE,Busan,Korea,Oct.2006.pp.5934-5939. [12]S.S.Saad and Z.S.Nakad,"A standalone RFID indoor positioning ReFeRENcES system using passive tags,"IEEE Trans.Industrial Electronics,vol.58. no.5,pp.1961-1970,2011. [1]N.B.Priyantha.A.K.Miu,H.Balakrishnan,and S.Teller,"The cricket [13]W.Zhu,J.Cao,Y.Xu,L.Yang.and J.Kong,"Fault-tolerant RFID compass for context-aware mobile applications,"in Proc.MobiCom, reader localization based on passive RFID tags,"in Proc.INFOCOM, Rome.Italy.July 2001,pp.1-14. [2]M.Minami,Y.Fukuju,K.Hirasawa,S.Yokoyama,M.Mizumachi, Orlando,Florida USA,March 2012,pp.2183-2191. H.Morikawa,and T.Aoyama."DOLPHIN:a practical approach for [14]I.Constandache.X.Bao,M.Azizyan and R.R.Choudhury,"Did you see Bob?:human localization using mobile phones,"in Proc.MobiCom, implementing a fully distributed indoor ultrasonic positioning system," in UbiComp 2004:Ubiguitous Computing,Tokyo,Japan,Sept.2004, Chicago.Illinois,USA.Sept.2010.pp.149-160. [15]T.Camp,J.Boleng and V.Davies,"A survey of mobility models for ad pp.347-365. hoc network research,"Wireless communications and mobile computing, [3]G.Fischer,B.Dietrich,and F.Winkler,"Bluetooth indoor localization system,"in Proc.WPNC,Hanover,Germany,March 2004,pp.147-156. vol2,no.5,pp.483-502,2002. [16]K.Lee,S.Hong.S.J.Kim,I.Rhee and S.Chong,"Slaw:A new [4]M.Azizyan,I.Constandache,and R.Roy Choudhury,"SurroundSense: mobility model for human walks,"in Proc.INFOCOM,Rio de Janeiro, mobile phone localization via ambience fingerprinting,"in Proc.Mobi- Brazil,April 2009,pp.855-863. Com,Beijing.China,Sept.2009,pp.261-272. 188
50 100 150 200 250 300 350 400 450 500 0 500 1000 1500 2000 2500 Number of users m Average searching time (s) blind navigation solution our navigation solution centralized navigation solution (a) RW, θR = 200(s), θk = 10 50 100 150 200 250 300 350 400 450 500 0 500 1000 1500 2000 2500 Number of users m Average searching time (s) blind navigation solution our navigation solution centralized navigation solution (b) RWP, θR = 200(s), θk = 10, µ = 18(m) 0 50 100 150 200 200 220 240 260 280 300 320 340 360 380 400 Time to live of request message θ R (s) Average searching time (s) Random Walk (RW) Random Waypoint (RWP) (c) m = 450, θk = 10, µ = 18(m) 1 2 3 4 5 6 7 8 9 10 200 205 210 215 220 225 230 235 240 245 250 Number of event messages θ k Average searching time (s) Random Walk (RW) Random Waypoint (RWP) (d) m = 450, θR = 200(s), µ = 18(m) 0 10 20 30 40 50 60 220 240 260 280 300 320 340 360 380 Expectation of movement region radius µ (m) Average searching time (s) (e) RWP, m = 450, θR = 200(s), θk = 10 0 100 200 300 400 500 600 700 0 500 1000 1500 2000 2500 3000 3500 Time (s) Number of messages event message (RW) event message (RWP) request message (RW) request message (RWP) (f) m = 450, θR = 200(s), θk = 10, µ = 18(m) Fig. 3. Comparison of the average searching time under Random Walk Mobility Model (RW) and Random Way-Point Mobility Model (RWP) with different parameters (number of users m; time to live of request message θR; number of event messages θk; expectation of movement region radius µ). VII. CONCLUSION This paper proposes a framework using RFID-based delay tolerant network for indoor navigation. By sufficiently leveraging the store-forward properties of delay tolerant network, our solution provides an effective mechanism for indoor navigation. Simulation results show that our solution can efficiently reduce the average searching time of navigation. We discuss the influences of different mobility parameters in the end. VIII. ACKNOWLEDGEMENT This work is partially supported by the National Basic Research Program of China (973) under Grant No. 2009CB320705; the National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61021062, 91218302; the JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] N. B. Priyantha, A. K. Miu, H. Balakrishnan, and S. Teller, “The cricket compass for context-aware mobile applications,” in Proc. MobiCom, Rome, Italy, July 2001, pp. 1-14. [2] M. Minami, Y. Fukuju, K. Hirasawa, S. Yokoyama, M. Mizumachi, H. Morikawa, and T. Aoyama, “DOLPHIN: a practical approach for implementing a fully distributed indoor ultrasonic positioning system,” in UbiComp 2004: Ubiquitous Computing, Tokyo, Japan, Sept. 2004, pp. 347-365. [3] G. Fischer, B. Dietrich, and F. Winkler, “Bluetooth indoor localization system,” in Proc. WPNC, Hanover, Germany, March 2004, pp. 147-156. [4] M. Azizyan, I. Constandache, and R. Roy Choudhury, “SurroundSense: mobile phone localization via ambience fingerprinting,” in Proc. MobiCom, Beijing, China, Sept. 2009, pp. 261-272. [5] J. Biswas, and M. Veloso, “Wifi localization and navigation for autonomous indoor mobile robots,” In Proc. ICRA, Anchorage, Alaska, USA, May 2010, pp. 4379-4384. [6] X. Jiang, C.-J. M. Liang, F. Zhao, K. Chen, J. Hsu, B. Zhang, and J. Liu, “Demo: Creating interactive virtual zones in physical space with magnetic-induction,” in Proc. SenSys, Seattle, WA, USA, Nov. 2011, pp. 431-432. [7] X. Jiang, C.-J. M. Liang, K. Chen, B. Zhang, J. Hsu, J. Liu, B. Cao, and F. Zhao, “Design and evaluation of a wireless magnetic-based proximity detection platform for indoor applications,” in Proc. IPSN, Beijing, China, April 2012, pp. 221-232. [8] L. Xie, B. Sheng, C. Tan, H. Han, Q. Li and D. X. Chen, “Efficient tag identification in mobile RFID systems,” in Proc. INFOCOM, San Diego, CA, USA, March 2010, pp. 1-9. [9] L. Xie, Q. Li, X. Chen, S. L. Lu and D. X. Chen, “Continuous Scanning with Mobile Reader in RFID Systems: an Experimental Study,” in MobiHoc, Bangalore, India, Aug. 2013. [10] L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, “LANDMARC: indoor location sensing using active RFID,” Wireless Networks, vol. 10, no. 6, pp. 701-710, Nov. 2004. [11] H. J. Lee and M. C. Lee, “Localization of mobile robot based on radio frequency identification devices,” in International Joint Conference SICE-ICASE, Busan, Korea, Oct. 2006, pp. 5934-5939. [12] S. S. Saad and Z. S. Nakad, “A standalone RFID indoor positioning system using passive tags,” IEEE Trans. Industrial Electronics, vol. 58, no. 5, pp. 1961-1970, 2011. [13] W. Zhu, J. Cao, Y. Xu, L. Yang, and J. Kong, “Fault-tolerant RFID reader localization based on passive RFID tags,” in Proc. INFOCOM, Orlando, Florida USA, March 2012, pp. 2183-2191. [14] I. Constandache, X. Bao, M. Azizyan and R. R. Choudhury, “Did you see Bob?: human localization using mobile phones,” in Proc. MobiCom, Chicago, Illinois, USA, Sept. 2010, pp. 149-160. [15] T. Camp, J. Boleng and V. Davies, “A survey of mobility models for ad hoc network research,” Wireless communications and mobile computing, vol. 2, no. 5, pp. 483-502, 2002. [16] K. Lee, S. Hong, S. J. Kim, I. Rhee and S. Chong, “Slaw: A new mobility model for human walks,” in Proc. INFOCOM, Rio de Janeiro, Brazil, April 2009, pp. 855-863. Globecom 2013 - Ad Hoc and Sensor Networking Symposium 188