Journal of Network and Computer Applications 52(2015)79-89 Contents lists available at ScienceDirect Journal of Network and Computer Applications ELSEVIER journal homepage:www.elsevier.com/locate/jnca CrowdSensing:A crowd-sourcing based indoor navigation rossMark using RFID-based delay tolerant network Hao Ji,Lei Xie*,Chuyu Wang,Yafeng Yin,Sanglu Lu State Key Laboratory for Novel Software Technology.Nanjing University.Nanjing.China ARTICLE INFO ABSTRACT Article history: As a supporting technology for most pervasive applications,indoor localization and navigation has Received 20 April 2014 attracted extensive attention in recent years.Conventional solutions mainly leverage techniques like Received in revised form WiFi and cellular network to effectively locate the user for indoor localization and navigation.In this 17 November 2014 Accepted 16 February 2015 paper.we investigate the problem of indoor navigation by using the RFID-based delay tolerant network. Available online 12 March 2015 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.As the low-cost RFID tags are widely Keywords: deployed inside the indoor environment and acting as landmarks,the mobile users can actively Indoor localization interrogate the surrounding tags with devices like smart phones and leave messages or traces to the Indoor navigation tags.These messages or traces can be carried and forwarded to more tags by other mobile users.In this REID Delay-tolerant network way.the RFID-based infrastructure forms a delay tolerant network.By using the crowd-sourcing Crowd-sourcing technology in RFID-based delay tolerant network,we respectively propose a framework,namely CrowdSensing.to schedule the tasks and manage the resources in the network.We further propose a navigation algorithm to locate and navigate to the moving target.We verify the performance of proposed framework and navigation algorithm on mobility model built on real-world human traceset.Experiment results show that our solution can efficiently reduce the average searching time for indoor navigation. 2015 Elsevier Ltd.All rights reserved. 1.Introduction indoor environment and act as landmarks for localization.Since current smart phones can be equipped with near field communica- As the rapid proliferation of pervasive applications in indoor tion (NFC)or bluetooth modules,which can effectively commu- environment,a lot of location-based services and context-aware nicate with the active/passive tags,the mobile users can actively services are put forward in which location is viewed as one of the interrogate the surrounding tags with tiny devices like smart most significant factors.For most applications,it is required to phones and leave messages or traces to the tags.In this way,the provide an accurate location for the specified objects.However,the RFID-based infrastructure forms a delay tolerant network.As the current mature technology like global position system(GPS)can only scanning range of RFID system is usually no more than 5 m.the be used in the outdoor environment for localization,several issues system can effectively locate the users by limiting the positioning like the multi-path effect and severe path loss make the indoor error to at most 5 m. localization a lot more complicated than the outdoor situation. In conventional indoor applications,the users are continuously Therefore,a lot of research works have focused on localization and moving within the indoor environment.Then,one important navigation schemes for indoor environment (Priyantha et al.,2001: problem is how to locate and navigate to a specified mobile user. Minami et al.,2004:Fischer et al,2004:Azizyan et al.,2009:Biswas For example,when a baby or a dog is lost in a shopping mall,how and Veloso,2010:Jiang et al,2011.2012).Most of the solutions are to quickly locate and navigate to the mobile target?Obviously,the rather complicated and fairly expensive. mobile target can only passively leave some traces in the environ- Recent technological advances have enabled the development ment through the equipped NFC or bluetooth modules.It cannot of low-cost and low-powered devices (Xie et al,2010,2013).RFID, actively propagate its current position directly to the searchers. as a novel technology for automatic identification,provides us Besides,time-efficiency is very critical to the searchers,since the with a new opportunity for indoor localization and navigation.For less time to use,the more opportunities to find the target. example,the low-cost RFID tags can be widely deployed inside the 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 .Corresponding author. manage the resources in this network.Furthermore,we propose a E-mail address:Ixie@nju.edu.cn (L Xie). navigation algorithm to locate and navigate to the moving target. http://dx.doi.org/10.1016/jjnca.2015.02.010 1084-8045/2015 Elsevier Ltd.All rights reserved
CrowdSensing: A crowd-sourcing based indoor navigation using RFID-based delay tolerant network Hao Ji, Lei Xie n , Chuyu Wang, Yafeng Yin, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China article info Article history: Received 20 April 2014 Received in revised form 17 November 2014 Accepted 16 February 2015 Available online 12 March 2015 Keywords: Indoor localization Indoor navigation RFID Delay-tolerant network Crowd-sourcing 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 and cellular network to effectively locate the user for indoor localization and navigation. In this paper, we investigate the problem of indoor navigation by using the RFID-based delay tolerant network. 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. As the low-cost RFID tags are widely deployed inside the indoor environment and acting as landmarks, the mobile users can actively interrogate the surrounding tags with devices like smart phones and leave messages or traces to the tags. These messages or traces can be carried and forwarded to more tags by other mobile users. In this way, the RFID-based infrastructure forms a delay tolerant network. By using the crowd-sourcing technology in RFID-based delay tolerant network, we respectively propose a framework, namely CrowdSensing, to schedule the tasks and manage the resources in the network. We further propose a navigation algorithm to locate and navigate to the moving target. We verify the performance of proposed framework and navigation algorithm on mobility model built on real-world human traceset. Experiment results show that our solution can efficiently reduce the average searching time for indoor navigation. & 2015 Elsevier Ltd. All rights reserved. 1. Introduction As the rapid proliferation of pervasive applications in indoor environment, a lot of location-based services and context-aware 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 (Priyantha et al., 2001; Minami et al., 2004; Fischer et al., 2004; Azizyan et al., 2009; Biswas and Veloso, 2010; Jiang et al., 2011, 2012). Most of the solutions are rather complicated and fairly expensive. Recent technological advances have enabled the development of low-cost and low-powered devices (Xie et al., 2010, 2013). 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 5 m, the system can effectively locate the users by limiting the positioning error to at most 5 m. In conventional indoor applications, the users are continuously moving within the indoor environment. Then, one 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. Contents lists available at ScienceDirect journal homepage: www.elsevier.com/locate/jnca Journal of Network and Computer Applications http://dx.doi.org/10.1016/j.jnca.2015.02.010 1084-8045/& 2015 Elsevier Ltd. All rights reserved. n Corresponding author. E-mail address: lxie@nju.edu.cn (L. Xie). Journal of Network and Computer Applications 52 (2015) 79–89
80 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 A preliminary version of this work appeared in Ji et al.(2013),the LANDMARC approach largely depends on the density of reference main differences of this paper are three folds.First,we conduct an in- tags and the high cost of RFID readers,Zou et al.(2013)propose depth study on the storage management of RFID tags,we propose four two localization algorithms,namely weighted path loss(WPL)and strategies of writing and replacing tag storage memory and their extreme learning machine (ELM),to overcome these drawbacks. corresponding usage scenarios (Section 4.3).Second,we conduct Ng et al.(2011)apply Radial Basis Function Neural Network detailed analysis on the relationship between tag density and network (RBFNN)to estimate location of objects based on RFID signal parameters,such as the number of users,the movement speed of each strengths.Tong and Wang (2014)propose a novel RFID indoor user and the range of each users'activity area.It provides a funda- positioning system based on Doppler Effect of moving RFID mental guidance for the deployment of RFID-based delay tolerant antenna.The Doppler frequency of RFID signal is recorded to network (Section 4.5).Third,we conduct the experiments with real- compute the relative velocity between the antenna and target tags. world human traces under shopping mall mobility model,illustrate By comparing the antenna movement with the relative velocity some novel observations from the experiment results,and further data,the position of the target is estimated using triangulation. verify the rationality of our navigation solution in practical situations Escort (Constandache et al.,2010)is an office environment (Section 5.1.1). localization and navigation system which uses client/server archi- The main contributions of this paper are summarized as tecture.The client running on the user-carried mobile phones follows: periodically measures the value of accelerometer and compass of the user's walking trail,and reports it to escort server.Encounter We propose a framework leveraging RFID-based delay tolerant between two mobile phones,and encounter between a mobile network for localization and navigation.By sufficiently lever- phone and an audio beacon placed in the building will both be aging the "store-and-forward"properties of the delay tolerant reported to escort server.Escort server utilizes users'walking trail network,our solution provides an effective mechanism for and encounters to compute the current position of each user and navigation using "crowdsourcing"capabilities.By effectively routing directions. scheduling the tasks and managing the limited resources in the In the theoretical research of delay tolerant network,a lot of work tags,the system can provide navigation services for a large have been done to reveal the relationship between latency and number of users. network parameters,such as node density,connectivity range,node We propose a time-efficient scheme to locate and navigate to a and movement speed.Dousse et al.(2004)prove that under certain mobile target who is continuously moving.According to the assumptions the message sent by a sensing node reaches the sink latest obtained spots of appearance,our solution navigates the node with a fixed asymptotic speed that does not depend on the searcher to the most possible region of the target,which random location of the nodes,but only on the network parameters. achieves a good performance in terms of the time-efficiency. Kong and Yeh(2008)use percolation theory to analyze the latency for .We conduct two kinds of experiments:large-scale experiment information dissemination in large-scale mobile wireless networks. through simulation and fairly small-scale experiment using They show that under a constrained mobility model,the scaling realistic human traces.In the large-scale simulation experi- behavior of the latency falls into two regimes.When the network is ments,we investigate the relationships among number of not percolated,the latency scales linearly with the initial Euclidean users,tag density and performance of navigation.In the distance between the sender and the receiver:when the network is small-scale experiments.we strive to accurately reconstruct percolated,the latency scales sub-linearly with the distance.Zhao the movement scenes of a shopping mall founded on real- et al(2011)present fundamental relationship between node density world human traces to verify our navigation framework and and transmission delay in large-scale wireless ad hoc networks with scheme. unreliable links from percolation perspective.Yang et al.focus on the problem of rostering in intermittently connected passive RFID net- The rest of this paper is organized as follows.Section 2 presents works.They propose a rostering algorithm that employs a dynamic the related work.Section 3 provides an overview of the system. space-efficient coding scheme to construct hypothetic packet candi- Section 4 introduces the distributed solution for indoor navigation. dates (Yang et al,2013).Bogo and Peserico (2013)study delay and Section 5 shows the performance evaluation.Section 6 concludes throughput achievable in delay tolerant networks with ballistic this paper. mobility.They show that,under some very mild and natural hypo- theses,as the number of nodes grows,(a)per-node throughput does not become vanishingly small and (b)communication delay does not 2.Related work become infinitely large.Kim et al.(2014)propose an efficient DTN routing scheme by using a node's social relation where each node Many research works use RFID technology for indoor localiza- chooses a proper relay node based on its contact history. tion.LANDMARC (Ni et al.,2004)is a tag localization prototype in Greatly different from previous works,in this paper we focus indoor environment.By utilizing extra fixed location reference on the problem of navigating to a moving target in indoor tags to help location calibration,it can increase location accuracy environment.The localization and navigation service are provided without deploying large numbers of RFID readers.Lee and Lee based on a RFID-based delay tolerant network.There is no central (2006)construct an absolute positioning system based on RFID server in the system which can record all users'positions in real- and investigate how localization technique can be enhanced by time.The size of each RFID tag's memory space is small.By RFID through experiment to measure the location of a mobile sufficiently leveraging the "store-and-forward"properties of the robot.Saad and Nakad (2011)present a standalone indoor posi- delay tolerant network and the 'crowdsourcing"capabilities tioning system using RFID technology.The concept is based on an brought by encounters between users and tags,we propose a object carrying an RFID reader module,which reads low-cost time-efficient scheme to locate and navigate to a mobile target. passive tags installed next to the object path.The positioning system uses Kalman filter to iteratively estimate the location of the reader.Zhu et al.(2012)propose a fault-tolerant RFID reader 3.System overview localization approach to solve the problem of frequently occurred RFID faults.Moreover,they also propose the index to measure the Most of the previous indoor positioning and navigation systems quality of a localization result.Since the localization accuracy of are centralized architecture which have the advantages of timeliness
A preliminary version of this work appeared in Ji et al. (2013), the main differences of this paper are three folds. First, we conduct an indepth study on the storage management of RFID tags, we propose four strategies of writing and replacing tag storage memory and their corresponding usage scenarios (Section 4.3). Second, we conduct detailed analysis on the relationship between tag density and network parameters, such as the number of users, the movement speed of each user and the range of each users' activity area. It provides a fundamental guidance for the deployment of RFID-based delay tolerant network (Section 4.5). Third, we conduct the experiments with realworld human traces under shopping mall mobility model, illustrate some novel observations from the experiment results, and further verify the rationality of our navigation solution in practical situations (Section 5.1.1). 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. We conduct two kinds of experiments: large-scale experiment through simulation and fairly small-scale experiment using realistic human traces. In the large-scale simulation experiments, we investigate the relationships among number of users, tag density and performance of navigation. In the small-scale experiments, we strive to accurately reconstruct the movement scenes of a shopping mall founded on realworld human traces to verify our navigation framework and scheme. The rest of this paper is organized as follows. Section 2 presents the related work. Section 3 provides an overview of the system. Section 4 introduces the distributed solution for indoor navigation. Section 5 shows the performance evaluation. Section 6 concludes this paper. 2. Related work Many research works use RFID technology for indoor localization. LANDMARC (Ni et al., 2004) 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. Lee and Lee (2006) construct an absolute positioning system based on RFID and investigate how localization technique can be enhanced by RFID through experiment to measure the location of a mobile robot. Saad and Nakad (2011) present a standalone indoor positioning system using RFID technology. The concept is based on an object carrying an RFID reader module, which reads low-cost passive tags installed next to the object path. The positioning system uses Kalman filter to iteratively estimate the location of the reader. Zhu et al. (2012) propose a fault-tolerant RFID reader localization approach to solve the problem of frequently occurred RFID faults. Moreover, they also propose the index to measure the quality of a localization result. Since the localization accuracy of LANDMARC approach largely depends on the density of reference tags and the high cost of RFID readers, Zou et al. (2013) propose two localization algorithms, namely weighted path loss (WPL) and extreme learning machine (ELM), to overcome these drawbacks. Ng et al. (2011) apply Radial Basis Function Neural Network (RBFNN) to estimate location of objects based on RFID signal strengths. Tong and Wang (2014) propose a novel RFID indoor positioning system based on Doppler Effect of moving RFID antenna. The Doppler frequency of RFID signal is recorded to compute the relative velocity between the antenna and target tags. By comparing the antenna movement with the relative velocity data, the position of the target is estimated using triangulation. Escort (Constandache et al., 2010) 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 walking trail, and reports it to escort server. Encounter between two mobile phones, and encounter between a mobile phone and an audio beacon placed in the building will both be reported to escort server. Escort server utilizes users' walking trail and encounters to compute the current position of each user and routing directions. In the theoretical research of delay tolerant network, a lot of work have been done to reveal the relationship between latency and network parameters, such as node density, connectivity range, node and movement speed. Dousse et al. (2004) prove that under certain assumptions the message sent by a sensing node reaches the sink node with a fixed asymptotic speed that does not depend on the random location of the nodes, but only on the network parameters. Kong and Yeh (2008) use percolation theory to analyze the latency for information dissemination in large-scale mobile wireless networks. They show that under a constrained mobility model, the scaling behavior of the latency falls into two regimes. When the network is not percolated, the latency scales linearly with the initial Euclidean distance between the sender and the receiver; when the network is percolated, the latency scales sub-linearly with the distance. Zhao et al. (2011) present fundamental relationship between node density and transmission delay in large-scale wireless ad hoc networks with unreliable links from percolation perspective. Yang et al. focus on the problem of rostering in intermittently connected passive RFID networks. They propose a rostering algorithm that employs a dynamic space-efficient coding scheme to construct hypothetic packet candidates (Yang et al., 2013). Bogo and Peserico (2013) study delay and throughput achievable in delay tolerant networks with ballistic mobility. They show that, under some very mild and natural hypotheses, as the number of nodes grows, (a) per-node throughput does not become vanishingly small and (b) communication delay does not become infinitely large. Kim et al. (2014) propose an efficient DTN routing scheme by using a node's social relation where each node chooses a proper relay node based on its contact history. Greatly different from previous works, in this paper we focus on the problem of navigating to a moving target in indoor environment. The localization and navigation service are provided based on a RFID-based delay tolerant network. There is no central server in the system which can record all users' positions in realtime. The size of each RFID tag's memory space is small. By sufficiently leveraging the “store-and-forward” properties of the delay tolerant network and the ‘crowdsourcing” capabilities brought by encounters between users and tags, we propose a time-efficient scheme to locate and navigate to a mobile target. 3. System overview Most of the previous indoor positioning and navigation systems are centralized architecture which have the advantages of timeliness 80 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89
H.Ji et al Journal of Network and Computer Applications 52 (2015)79-89 81 b V15 office rooms HC 4“ 0. office rooms V22 29 3 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 jump
and 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 navigation 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 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 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 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 (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 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 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
电 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 of
to 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
H.Ji et al.Journal of Network and Computer Applications 52 (2015)79-89 83 users,and the movement speed of users.If the tag density is small mainly use One Request Many Event(ORME)writing and replacing which means storage resource is very precious in the system,we strategy in the experiment to verify our navigation framework. should choose One Request One Event(OROE)strategy to ensure Figure 2(a)-(e)shows the message interaction diagram when that users can get a fair chance to store at least one event message users pass by tags.In Fig.2(a).when searcher A passes by tag vi at and one request message on tags.If the tag density is large,we time t1.searcher A posts an event message E(A,vi,t1)to tag v. should choose Many Request Many Event(MRME)strategy to store Because searcher A wants to find target B.he also posts a request users'event messages and request messages as many as possible.If message R(A,B,t)to tag v.The event messages and request the movement speed of users is high and the searcher wants to messages are stored from both ends to middle.In Fig.2(b),target B spread out the request message to as many helpers as possible in a posts an event message E(B,v2,t2)to tag v2 when he passes by tag short time,maybe he should choose Many Request One Event vz at time t2.In Fig.2(c).when helper H passes by tag vz at time ts. (MROE)strategy to show the request is urgent.In this paper,we helper H posts an event message E(H,v2.t3)to tag v2.Besides, ⊙ b Searcher A Target B Movement direction Movement direction Event E<A,vi,ti> Event E<B,v2,ta> Request R<A,B,tis Memory space of tag vi Memory space of tag vz ---EA,V1,1> -----E<B,v2,2> current tag:vi current tag:v2 current time:tu R<A,B,ti> current time:t2 d Event Table Request Queue Helper H--- -E<B,v2,t2> Helper H- R<A,B,ti> Event Table Movement direction E<B,v2,2 Movement direction EcA,vI,t> Event E<H,v2,t3> Event E<H,vi,t4> E<A,vi,ti>Event E<B,v2,t2>Event R<A,B,ti>Request Tag v2 ag v Memory space of tag v2 Memory space of tag vi E<B,v2,t23 --E2A,n,> E<H,V2,t32 E<B,v2,t2> current tag:v2 current tag:vi current time:t4 current time:t3 R<A,B,ti> e Request●ueue Memory space of tag vi Helper H----------- Unit Number of -R<A,B,ti> Storage 1 E<A,vI,tis Event Message Event Table E<H,vi,t4> E<B,v2,t2> Movement direction EA,,t正 4 Event E<H,v3,t5> 6 Memory space of tag v3 E<H,3,t5> E<B,v2,t2> current tag:v3 3 current time:t与 R<A,B,t1> Message R<A,B,ti Segment Fig.2.Management of tag storage space using One Request Many Event(ORME)strategy.(a)-(e)Message interaction diagrams when searcher A.target B and helper H pass by a tag:(f)memory space of a tag(N1/N2=).(a)when searcher A passes by tag v1 at time t1.(b)when target B passes by tag v2 at time t2.(c)when helper H passes by tag v2 at time t3.(d)when searcher H passes by tag vI at time t4.(e)when searcher H passes by a new tag v3 at time t5 and (f)storage layout of two message segments
users, and the movement speed of users. If the tag density is small which means storage resource is very precious in the system, we should choose One Request One Event (OROE) strategy to ensure that users can get a fair chance to store at least one event message and one request message on tags. If the tag density is large, we should choose Many Request Many Event (MRME) strategy to store users' event messages and request messages as many as possible. If the movement speed of users is high and the searcher wants to spread out the request message to as many helpers as possible in a short time, maybe he should choose Many Request One Event (MROE) strategy to show the request is urgent. In this paper, we mainly use One Request Many Event (ORME) writing and replacing strategy in the experiment to verify our navigation framework. Figure 2(a)–(e) shows the message interaction diagram when users pass by tags. In Fig. 2(a), when searcher A passes by tag v1 at time t1, searcher A posts an event message E A; v1;t1 to tag v1. Because searcher A wants to find target B, he also posts a request message R A; B;t1 to tag v1. The event messages and request messages are stored from both ends to middle. In Fig. 2(b), target B posts an event message E Bh i ; v2;t2 to tag v2 when he passes by tag v2 at time t2. In Fig. 2(c), when helper H passes by tag v2 at time t3, helper H posts an event message E Hh i ; v2;t3 to tag v2. Besides, Fig. 2. Management of tag storage space using One Request Many Event (ORME) strategy. (a)–(e) Message interaction diagrams when searcher A, target B and helper H pass by a tag; (f) memory space of a tag (N1=N2 ¼ λ). (a) when searcher A passes by tag v1 at time t1, (b) when target B passes by tag v2 at time t2, (c)when helper H passes by tag v2 at time t3, (d) when searcher H passes by tag v1 at time t4, (e) when searcher H passes by a new tag v3 at time t5 and (f) storage layout of two message segments. H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89 83