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 timelinessA preliminary version of this work appeared in Ji et al. (2013), the main differences of this paper are three folds. First, we conduct an in￾depth 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 funda￾mental guidance for the deployment of RFID-based delay tolerant network (Section 4.5). Third, we conduct the experiments with real￾world 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 lever￾aging 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 experi￾ments, 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 real￾world 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 localiza￾tion. 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 posi￾tioning 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 archi￾tecture. 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 net￾works. They propose a rostering algorithm that employs a dynamic space-efficient coding scheme to construct hypothetic packet candi￾dates (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 hypo￾theses, 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 real￾time. 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