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-t0).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 Event E Request R -----E current tag:vi current tag:v2 current time:tu R current time:t2 d Event Table Request Queue Helper H--- -E Helper H- R Event Table Movement direction E Event E Event E EEvent EEvent RRequest Tag v2 ag v Memory space of tag v2 Memory space of tag vi E E current tag:v2 current tag:vi current time:t4 current time:t3 R e Request●ueue Memory space of tag vi Helper H----------- Unit Number of -R Storage 1 E E Movement direction EA,,t正 4 Event E 6 Memory space of tag v3 E E current tag:v3 3 current time:t与 R 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
84 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 helper H will also get the event message E(B.v2,t2)and add it to selecting the neighbor vertex which is nearest to the latest his event table.In Fig.2(d).when helper H passes by tag v at time appearance location of the target.For example,suppose the t4.helper H posts an event message E(H,vi,t4)to tag v1.Besides. weight of all edges is equal in Fig.1(b).The current location of helper H will also get the event message E(A.vi,ti)and the the searcher is v3.and the latest appearance location of the target request message R(A,B,t1)of A,and add them to helper H's event is v7.Then vertex vn will be selected,because it is the nearest table and request queue.Then helper H posts the event message neighbor of v3 to the vertex v17.However,three reasons make us E(B,v2,t2)to tag v.In Fig.2(e).helper H posts the event message do not use the above simple method to select the next vertex to E(B,v2,t2)and request message R(A,B,t1)to tag v3.thus to attract move.The first reason is that the trace with latest timestamp may more helpers to find B.In Fig.2(f).the memory space of tag is be far away.There should be a tradeoff between the timestamp of divided into two segments:event message segment and request the trace and distance.The second reason is that the target is a message segment.We will discuss more on the management of moving object whose motion is a continuous process.The third the memory space in the following: reason is that the movement behavior of the target has locality in Situation 1.Normal Mode 2(b): the real world.We use Algorithm 2 to select the next neighbor to user Hi posts an event message E(Hi.vj.t)to vj: move and guide the searcher to be close to a target region rather than a single point. Using the One Request Many Event (ORME)writing and repla cing strategy,each tag maintains at most A event messages of each Algorithm 2.Navigation algorithm. user Hi.A is a predefined parameter of ORME which is used to adjust the ratio between request messages and event messages. Input:tnow;Vs:d:V=v1.V2.....m): When the value A equals to 1,the ORME strategy is reduced to U=(u1.u2....un):=(t1.t2.....tn): OROE strategy.If the number of event messages is less than A.then Output:next neighbor Unext to move E(Hi.vj.t)will be written to vj.The oldest event message of H 1:Calculate all vertices pairs'shortest path length on graph G stored on v will be replaced with E(Hi.vj.t).Thus the size of event using algorithm such as Floyd-Warshall or Dijistra;and message segment is A times as many as the size of request store these values in matrix d. message segment. 2:for each u;∈Udo Situation 2.Normal Mode 3(a): 1 Hi posts a request message R(S,T,t)to vy: ai=Enow-ti 4:end for Using the One Request Many Event (ORME)writing and repla- 5:a=∑i-1a: cing strategy,each tag maintains at most one request message of 6:for each neighbor vie V of vs do searcher S and target T.If there already exists a request message fy)=d[v;llvj+∑-1告×dylu R(S,T.t')on vk and t'<t,then the timestamp t'will be updated to 8:end for t.We take the same writing and replacing method in Searcher 9:Select the smallest value f(Umin)from f(v1),....f(Um): Mode step 2. Situation 3.Normal Mode 3(b): Unext Umin Hi selects event messages (E(T,*,*)of the target T from H's event table:then Hi posts these event messages to vk. In Algorithm 2,thow is the current time;Us is the current location In general,there are many helpers in the system.If all of them of the searcher S:d is a shortest path matrix which can be precalculated;each element div]v]ed is the shortest path length post messages to a vertex as soon as they pass by it,the memory space of the tag will be reduced rapidly.Therefore.when the between vertices v and v:all vertices in collection V=v1.v2.....m) are the neighbors of vertex vs.Besides,we use the event table of available memory space size is reduced to a certain range,say 10%, searcher S to predict the current location of the target.Let n(n < we use a posting probability p=i/oi,(0sp s 1)to further reduce is the event messages number of the target T.Arrange these event the number of posting events messages.o,is the total memory size messages in descending order according to the timestamp.Represent of vk,and 6;is the memory size which has not been used of vertex the arrangement with the list E(T,u1,t),E(T,u2,t2)....,E(T,un,tn). Vk.When a helper passes by a vertex,he will post messages to the vertex with a posting probability p. Correspondingly,=(t1,t2....,tn)is the list of timestamps,and U=(u.u2..u)is the list of vertices.Vertices in list U compose the target region. 4.4.Navigation algorithm For each neighbor vi of vs.we define a cost function f(vi)to predict whether the searcher is close to the target or far from the Our goal is to find the optimal vertex sequence,so as to navigate target.We assign a normalized weight ai/a for each vertex u in searcher S to a moving target T with minimum time cost.At the the target region according to the timestamp.The weight of vertex beginning of the above navigation framework,if there is no priori with latest traces will have higher value than that of other vertices. knowledge of the target's movement,searcher S can only randomly Cost function f(;)is defined below: select a place to move without any guidance.After a period of time, the searcher collects some event messages of the target which f(vj)=w[vs][vi]+ (1) states that the target appears at some places.The more the traces searcher collects,the better the searcher will know about the target's movement.If history data of the target's movement can The neighbor vertex which has the lowest cost will be selected as be obtained,the searcher can even predict the current location of the next intermediate vertex.For example,in Fig.3,we assume the target according to those traces he gets now.At least,searcher S that all the edges between two vertices on the graph are equal to has some instructive guidance at this time. 1:n=3:V=w2,V4,V11,21》.U=(w17,18,V19.T=(4,3,1.the When searcher S has collected some event messages of the current time tnow=5.Then vertex vn will be selected as the next target T,the searcher could use these traces as the guidance to intermediate vertex.Because the cost of vn is 7.57 which is less select the next neighbor vertex to move.A simple way to do this is than the cost of v2.va or v21
helper H will also get the event message E Bh i ; v2;t2 and add it to his event table. In Fig. 2(d), when helper H passes by tag v1 at time t4, helper H posts an event message E Hh i ; v1;t4 to tag v1. Besides, helper H will also get the event message E A; v1;t1 and the request message R A; B;t1 of A, and add them to helper H's event table and request queue. Then helper H posts the event message E Bh i ; v2;t2 to tag v1. In Fig. 2(e), helper H posts the event message E Bh i ; v2;t2 and request message R A; B;t1 to tag v3, thus to attract more helpers to find B. In Fig. 2(f), the memory space of tag is divided into two segments: event message segment and request message segment. We will discuss more on the management of the memory space in the following: Situation 1. Normal Mode 2(b): user Hi posts an event message E Hi; vj;t to vj; Using the One Request Many Event (ORME) writing and replacing strategy, each tag maintains at most λ event messages of each user Hi. λ is a predefined parameter of ORME which is used to adjust the ratio between request messages and event messages. When the value λ equals to 1, the ORME strategy is reduced to OROE strategy. If the number of event messages is less than λ, then E Hi; vj;t will be written to vj. The oldest event message of Hi stored on vj will be replaced with E Hi; vj;t . Thus the size of event message segment is λ times as many as the size of request message segment. Situation 2. Normal Mode 3(a): Hi posts a request message R Sh i ; T;t to vk; Using the One Request Many Event (ORME) writing and replacing strategy, each tag maintains at most one request message of searcher S and target T. If there already exists a request message R S; T;t0 h i on vk and t0 ot, then the timestamp t0 will be updated to t. We take the same writing and replacing method in Searcher Mode step 2. Situation 3. Normal Mode 3(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: In general, 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, when the available memory space size is reduced to a certain range, say 10%, we use a posting probability p ¼ δ0 i =δi; ð0rpr1Þ to further reduce the number of posting events messages. δi is the total memory size of vk, and δ0 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. 4.4. 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 the traces searcher collects, the better the 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 is equal in Fig. 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 i ν1; ν2; …; νm ; U ¼ h i u1; u2; …; un ; Γ ¼ h i t1;t2; …;tn ; 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 AU do 3: αi ¼ 1 tnow ti ; 4: end for 5: α ¼ Pn i ¼ 1 αi; 6: for each neighbor νj AV 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½v0 Ad is the shortest path length between vertices v and v0 ; all vertices in collection V ¼ h i ν1; ν2; …; νm are the neighbors of vertex vs. Besides, we use the event table of searcher S to predict the current location of the target. Let n (nrθ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 Th i ; u1;t1 , E Th i ; u2;t2 , … , E Th i ; un;tn . Correspondingly, Γ ¼ h i t1;t2; …;tn is the list of timestamps, and U ¼ h i u1; u2; …; un 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 ð1Þ The neighbor vertex which has the lowest cost will be selected as the next intermediate vertex. For example, in Fig. 3, we assume that all the edges between two vertices on the graph are equal to 1; n¼3; V ¼ h i v2; v4; v11; v21 , U ¼ h i v17; v18; v19 , Γ ¼ h i 4; 3; 1 , 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. 84 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 85 The larger the number of people N is,the larger the tag density p is.Because more users means more event messages need to be stored on tags which leads to appropriate number of tags need to be deployed. The faster the speed of users'movement 9 and the larger the range of users'activity area y are,the larger the tag density p is. Because more event messages and request messages are generated in the same time which leads to more tags that are V30 needed in the system. The tag density p is also related to which kind of writing and V29 replacing strategy is chosen.For example,MRME strategy needs more tags than OROE strategy. V24 V25 V26 V27 V28 Fig.3.Select the next position (vertex)and move to a target region 4.6.Discussion on practical issues 4.5.Analysis In realistic settings of the applications,several practical issues like the tag collisions and the localization accuracy might impact In the field of large-scale wireless ad hoc networks research, the actual performance of our indoor navigation solution.We thus previous works (Dousse et al.,2004:Kong and Yeh,2008;Zhao provide a detailed discussion on these issues as follows: et al.,2011)have already showed the relationship between In regard to the issue of tag collisions in MAC layer,since in our transmission delay and distance from source to destination. application settings,the RFID tags are not deployed in a rather However,our problem is different from the above problems dense approach,i.e.,one tag is deployed for every 4-10 m,as we studied in previous works.The focus of our problem is locating suppose to use a mobile reader(like smart phone)to continuously and navigating to a mobile user.We analyze our distributed scan the surrounding tags,the scanning range is usually less than solution on the undirected graph G=(V,E)which is an abstraction 3 m,the possibility of tag collision is very low in our application of the RFID-based delay tolerant network.On the graph,we want scenarios.Therefore,we mainly consider the performance in terms to find the optimal vertex sequence (vi.v2.....vn).((vi.v)EE. of application layer,the collision in physical layer will not have a 1sisn-1),where v is the current location of the searcher S. great effect on the system performance. and v is the finally location where the searcher found the target T. In regard to the issue of localization accuracy,our main goal is so as to minimize the total distance of the vertex sequence.Let L to conduct efficient indoor navigation instead of indoor localiza- be the total distance and our goal is to tion based on RFID systems.In our application settings,we deploy at least one tag for every 4-10 m,each tag is labeled with an exact minL÷min∑wv+i] (2) position,the scanning range of a mobile reader is less than 3 m, hence the localization error is at most 3 m.As our indoor subject to the memory size si for each vertex v. navigation solution is designed towards a large scale application Since the memory size of each RFID tag is limited,in order to scenario,for example,indoor navigation in a shopping mall or a ensure the locating and navigating performance in the RFID-based large office building.this localization scheme is accurate enough delay tolerant network,appropriate number of tags should be for our application scenarios. deployed.We use tag density p as the guide to deploy tags in the system.Let s2 be the volume of the indoor environment and be the average memory size of tag Obviously.we have. 5.Performance evaluation To determine the value of p,we introduce a new concept steady- 5.1.Large-scale experiment under classical human mobility model state.Considering an ideal situation,the memory size of each RFID tag is infinity.as the navigation system running.the total occupied We implement a simulator in Java to simulate the navigation memory size of tags (t)changes as well.We define that the system process,thus to evaluate the performance of our solution.We reaches its steady-state when the value (t)no longer increases. conduct the experiment based on a 30 x 30 grid-graph.Each Then,if the system can reach its steady-state,the following condi- vertex on the graph represents a tag in the RFID-based delay tions must be satisfied: tolerant network.Except the boundary vertices,each vertex has 6≥mx0 (3) four neighbor vertices.We consider the simulation as an event- 斯eV driven scenario,that is.when a user is approaching the vertex (tag)within a distance of less than 1 m,we allow the user to leave Then we obtain a trace or send a query to the surrounding tags.To simulate the p≥maxo≤so movement behaviors of users on the graph,we use two classical (4) human mobility models (Camp et al.,2002;Lee et al.,2009). 2*6 We compare the performance of our solution with the follow- However,it still remains as an open problem how maxo(t) ing solutions in regard to the average searching time: varies in accordance with network parameters,such as the number of people N in the network,the movement speed of each person 9, Blind navigation:The searcher randomly selects a vertex on the and the range of each person'activity area y.Theoretically analyzing graph and moves to the vertex with the shortest path length.If the exact relationship between them is very difficult.In Section 5,we the searcher does not find the target on the path,then the use experiment result to reveal the above quantitative relation.In searcher will repeat the above process until he finds the target. this paper,average searching time will be used to measure the Centralized navigation:The searcher can obtain the target's performance of our solution.Intuitively.we can qualitatively describe current position in real time.The searcher always moves to the relationship between them as follows: the neighbor vertex which is nearest to the target
4.5. Analysis In the field of large-scale wireless ad hoc networks research, previous works (Dousse et al., 2004; Kong and Yeh, 2008; Zhao et al., 2011) have already showed the relationship between transmission delay and distance from source to destination. However, our problem is different from the above problems studied in previous works. The focus of our problem is locating and navigating to a mobile user. We analyze our distributed solution on the undirected graph G ¼ ðV; EÞ which is an abstraction of the RFID-based delay tolerant network. On the graph, we want to find the optimal vertex sequence v0 1; v0 2; …; v0 n ;ð ðv0 i ; v0 iþ1ÞAE; 1rirn1Þ, where v0 1 is the current location of the searcher S, and v0 n is the finally location where the searcher found the target T, so as to minimize the total distance of the vertex sequence. Let L be the total distance and our goal is to min L3min n X1 i ¼ 1 w½v0 i ½v0 iþ1 ð2Þ subject to the memory size rδi for each vertex v0 i . Since the memory size of each RFID tag is limited, in order to ensure the locating and navigating performance in the RFID-based delay tolerant network, appropriate number of tags should be deployed. We use tag density ρ as the guide to deploy tags in the system. Let Ω be the volume of the indoor environment and δ be the average memory size of tag. Obviously, we have ρnΩnδ ¼ P vi AV δi. To determine the value of ρ, we introduce a new concept steadystate. Considering an ideal situation, the memory size of each RFID tag is infinity, as the navigation system running, the total occupied memory size of tags ϕðtÞ changes as well. We define that the system reaches its steady-state when the value ϕðtÞ no longer increases. Then, if the system can reach its steady-state, the following conditions must be satisfied: X vi AV δiZ max 0ot o1ϕðtÞ ð3Þ Then we obtain ρZmax0ot o1ϕðtÞ Ωnδ ð4Þ However, it still remains as an open problem how max0ot o1ϕðtÞ varies in accordance with network parameters, such as the number of people N in the network, the movement speed of each person ϑ, and the range of each person' activity area γ. Theoretically analyzing the exact relationship between them is very difficult. In Section 5, we use experiment result to reveal the above quantitative relation. In this paper, average searching time will be used to measure the performance of our solution. Intuitively, we can qualitatively describe the relationship between them as follows: The larger the number of people N is, the larger the tag density ρ is. Because more users means more event messages need to be stored on tags which leads to appropriate number of tags need to be deployed. The faster the speed of users' movement ϑ and the larger the range of users' activity area γ are, the larger the tag density ρ is. Because more event messages and request messages are generated in the same time which leads to more tags that are needed in the system. The tag density ρ is also related to which kind of writing and replacing strategy is chosen. For example, MRME strategy needs more tags than OROE strategy. 4.6. Discussion on practical issues In realistic settings of the applications, several practical issues like the tag collisions and the localization accuracy might impact the actual performance of our indoor navigation solution. We thus provide a detailed discussion on these issues as follows: In regard to the issue of tag collisions in MAC layer, since in our application settings, the RFID tags are not deployed in a rather dense approach, i.e., one tag is deployed for every 4–10 m, as we suppose to use a mobile reader (like smart phone) to continuously scan the surrounding tags, the scanning range is usually less than 3 m, the possibility of tag collision is very low in our application scenarios. Therefore, we mainly consider the performance in terms of application layer, the collision in physical layer will not have a great effect on the system performance. In regard to the issue of localization accuracy, our main goal is to conduct efficient indoor navigation instead of indoor localization based on RFID systems. In our application settings, we deploy at least one tag for every 4–10 m, each tag is labeled with an exact position, the scanning range of a mobile reader is less than 3 m, hence the localization error is at most 3 m. As our indoor navigation solution is designed towards a large scale application scenario, for example, indoor navigation in a shopping mall or a large office building, this localization scheme is accurate enough for our application scenarios. 5. Performance evaluation 5.1. Large-scale experiment under classical human mobility model We implement a simulator in Java to simulate the navigation process, thus to evaluate the performance of our solution. We conduct the experiment based on a 30 30 grid-graph. Each vertex on the graph represents a tag in the RFID-based delay tolerant network. Except the boundary vertices, each vertex has four neighbor vertices. We consider the simulation as an eventdriven scenario, that is, when a user is approaching the vertex (tag) within a distance of less than 1 m, we allow the user to leave a trace or send a query to the surrounding tags. To simulate the movement behaviors of users on the graph, we use two classical human mobility models (Camp et al., 2002; Lee et al., 2009). We compare the performance of our solution with the following solutions in regard to the average searching time: Blind navigation: The searcher randomly selects a vertex on the graph and moves to the vertex with the shortest path length. If the searcher does not find the target on the path, then the searcher will repeat the above process until he finds the target. Centralized navigation: 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. Fig. 3. Select the next position (vertex) and move to a target region. H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89 85
86 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 .Intuitive navigation:The searcher leverages the RFID-based While the average searching time of blind navigation or centralized delay tolerant network to search the target,once the searcher navigation is essentially unchanged.This is consistent with our gets one record of the target from the surrounding tags,he goes intuition that more users means more helpers for the searcher. to the corresponding position directly.If he does not find the Specifically,the blind navigation just randomly chooses a way to target at the specified position,he then further queries the find the target,which is irrelevant to the number of users and leads surrounding tags for the target. to stable average searching time.The centralized navigation always .Escort (Constandache et al,2010):Once a user meets other achieves the least searching time,since it is always close to the users,they will exchange their own information with each other optimal solution.With the number of users increasing,the average to help find the target.As the number of users increases,the searching time of CrowdSensing,Escort and Intuitive Navigation are probability to meet the target increases,this helps the searcher all reduced gradually.Escort suffers from rare users at first,which to quickly collect enough information to search the target. leads to long searching time.However,as the number of user increases,the number of users is close to the intersections in the Here,in the following we call our solution as CrowdSensing.we graph,which leads to close searching time of CrowdSensing.The regard the centralized navigation as the approximate optimal solu- intuitive navigation can only follow the one historical record of the tion and the blind navigation as the worst solution.The intuitive target,which leads to relatively high searching time in RW model, navigation is usually proposed in recent literatures for adaptive because the target keeps on moving.However,in RWP model,the navigation,which is greedy by focusing on the present record,and target will not move so often,which makes the searching time usually efficient to find a target moving regularly.The Escort should smaller than the RW model.Since CrowdSensing can make use of all be efficient in searching when the number of users is fairly large. the crowd-sourcing information,it achieves better performance than the above two solutions. 5.1.1.Experiment settings In Fig.4(c)and (d),we plot the average searching time of Crowd- At the beginning of the experiment,we randomly select a vertex Sensing under two mobility models with different values of dg and d on the 30 x 30 grid-graph for each user as the user's initial position. When the value of o is small,the average searching time is large. All the users are limited to move on the edges of the grid-graph.The Because only a few number of users could receive request messages length of each edge is 4 m.In order to avoid situation that searcher and the searcher gets little help from others.When increasing the never catches up with the target,we assign the movement speed of value of e from 10s to 200 s,the average searching time is reduced the searcher to 2 m/s and other users'to 1 m/s.If searcher and more than 30%.Different from 6g.the impact of is little.When the target happen to be on the same edge,we think that the searcher values of are 1,2,6.and 8 under RW or 1,3 and 4 under RWP,the has found the target. average searching time is slightly smaller than others To simulate the movement behaviors of users,we use a simplified In Fig.4(e),we plot the average searching time of CrowdSensing Random Walk(RW)Mobility Model and a Random Way-Point(RWP) under RWP with different localities of users'movement behaviors. Mobility Model.Under the Random Walk Mobility Model,whenever a When the value of u is less than 12,users move in a small region. user reaches a vertex,the user will randomly select a neighbor vertex The request messages of searcher spread slowly.Thus it takes a to move.Under the random way-point mobility model,each user long time for the searcher to detect the target's traces,and the randomly selects a vertex within a local region on the graph and average searching time is large.When the locality of users'move- moves to the vertex with the shortest path length.When arriving at ments is weak,sayμ≥30，the movement region of the target is the vertex,the user will stay on the vertex for a period of time,then large.So,it is also difficult for the searcher to find the target.We repeat the above process.We use a circular region to describe such a find that when w is 20 the average searching time is the smallest. local region.The center of the circle is the user's initial position and the Number of messages:In Fig.4(f).we plot the average number of radius of the circle obeys a normal distribution N(,6),where u is the messages stored in the delay tolerant network as time grows.The expectation of radius.The stay time of each user obeys a truncated number of request messages under RWP is sightly smaller than RW. power-law distribution p(t)=Cxt-25(s).(5sts60).Parameters When the time is about 200s,the number of request messages used in the experiment are shown in Table 1.For all figures presented, reaches its maximum.The number decreases as the request mes- we run the experiment 1000 times to get average values,and provide sage's time to live is reduced to zero.The number of event messages the 95%confidence interval of the experiment results grows fast between 150 s and 350 s.After 400 s,the number of event messages is essentially unchanged.Because no more request mes- 5.1.2.Experiments result sages are generated after that. Average searching time:In Fig.4(a)and (b),we plot the average searching time of three solutions under two mobility models with 5.2.Realistic experiment under shopping mall mobility model different numbers of users.We guarantee that the inputs of users' movement behaviors for each solution are the same.As we can see To evaluate the performance of CrowdSensing under real world from these 2 figures,with the number of users increasing.the environment,we conduct our experiment using a mobility model average searching time of CrowdSensing is reduced gradually.When for shopping mall environments founded on real-world human increasing the number of users from 50 to 500,CrowdSensing's traces which is presented by Galati et al.(2013).They ran a field average searching time is reduced from 722/499 s to 216/230 s. trial to collect Bluetooth contact data from shop employees and clerks in a shopping mall over six days.The field trial started on Monday the 15th of June 2009 and went on till Saturday the 20th Table 1 of June 2009.The traceset can be accessed from community Parameters used in the experiment resource for archiving wireless data at Dartmouth (CRAWDAD) (Galati and Greenhalgh,2013).They analyzed the collected contact Description Value traces and designed the shopping mall mobility model. Number of users 50...500 B (s) Time to live of request message [10.,200 5.2.1.Shopping mall mobility model Number of event message 1,.,10 4(m) Expectation of region radius 6..,60 In the shopping mall environment,there are twenty-five mobile devices running symbianOS and using Bluetooth,eighteen of which
Intuitive navigation: The searcher leverages the RFID-based delay tolerant network to search the target, once the searcher gets one record of the target from the surrounding tags, he goes to the corresponding position directly. If he does not find the target at the specified position, he then further queries the surrounding tags for the target. Escort (Constandache et al., 2010): Once a user meets other users, they will exchange their own information with each other to help find the target. As the number of users increases, the probability to meet the target increases, this helps the searcher to quickly collect enough information to search the target. Here, in the following we call our solution as CrowdSensing, we regard the centralized navigation as the approximate optimal solution and the blind navigation as the worst solution. The intuitive navigation is usually proposed in recent literatures for adaptive navigation, which is greedy by focusing on the present record, and usually efficient to find a target moving regularly. The Escort should be efficient in searching when the number of users is fairly large. 5.1.1. Experiment settings At the beginning of the experiment, 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 to 2 m/s and other users' to 1 m/s. If searcher and target happen to be on the same edge, we think that the searcher has found the target. To simulate the movement behaviors of users, we use a simplified Random Walk (RW) Mobility Model and a Random Way-Point (RWP) Mobility Model. 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 the shortest path length. 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ðμ; 62 Þ, 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Þ, ð5rtr60Þ. Parameters used in the experiment are shown in Table 1. For all figures presented, we run the experiment 1000 times to get average values, and provide the 95% confidence interval of the experiment results. 5.1.2. Experiments result Average searching time: In Fig. 4(a) and (b), 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 figures, with the number of users increasing, the average searching time of CrowdSensing is reduced gradually. When increasing the number of users from 50 to 500, CrowdSensing's average searching time is reduced from 722/499 s to 216/230 s. 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. Specifically, the blind navigation just randomly chooses a way to find the target, which is irrelevant to the number of users and leads to stable average searching time. The centralized navigation always achieves the least searching time, since it is always close to the optimal solution. With the number of users increasing, the average searching time of CrowdSensing, Escort and Intuitive Navigation are all reduced gradually. Escort suffers from rare users at first, which leads to long searching time. However, as the number of user increases, the number of users is close to the intersections in the graph, which leads to close searching time of CrowdSensing. The intuitive navigation can only follow the one historical record of the target, which leads to relatively high searching time in RW model, because the target keeps on moving. However, in RWP model, the target will not move so often, which makes the searching time smaller than the RW model. Since CrowdSensing can make use of all the crowd-sourcing information, it achieves better performance than the above two solutions. In Fig. 4(c) and (d), we plot the average searching time of CrowdSensing 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 s to 200 s, the average searching time is reduced more than 30%. Different from θR, the impact of θk is little. When the values of θk are 1, 2, 6, and 8 under RW or 1, 3 and 4 under RWP, the average searching time is slightly smaller than others. In Fig. 4(e), we plot the average searching time of CrowdSensing 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 weak, say μZ30, 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. Number of messages: In Fig. 4(f), 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 and 350 s. After 400 s, the number of event messages is essentially unchanged. Because no more request messages are generated after that. 5.2. Realistic experiment under shopping mall mobility model To evaluate the performance of CrowdSensing under real world environment, we conduct our experiment using a mobility model for shopping mall environments founded on real-world human traces which is presented by Galati et al. (2013). They ran a field trial to collect Bluetooth contact data from shop employees and clerks in a shopping mall over six days. The field trial started on Monday the 15th of June 2009 and went on till Saturday the 20th of June 2009. The traceset can be accessed from community resource for archiving wireless data at Dartmouth (CRAWDAD) (Galati and Greenhalgh, 2013). They analyzed the collected contact traces and designed the shopping mall mobility model. 5.2.1. Shopping mall mobility model In the shopping mall environment, there are twenty-five mobile devices running symbianOS and using Bluetooth, eighteen of which Table 1 Parameters used in the experiment. 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 86 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 87 9 b 20 1800 巴mad 1600 00 200 1400 1200 350 150 100 300 100 400 250 200 INiHnt 100150200250300350400450 200 50 0 50 100 150200250300350400450500 20 60 80100120140180180200 Number of user m Number of user m Time to live of request message (s) d e 270 340 50 260 320 3000 age (RW 300 2500 280 2000 230 260 1500 220 240 1000 o 500 220 200 0 1 234567891011 20 40 50 60 100 200300400500600700 Number of event messages Expe nt region radiusμ(m Time(s) Fig.4.Comparison of the average searching time under Random Walk(RW)Mobility Model and Random Way-Point(RWP)Mobility Model with different parameters (number of users m:time to live of request message 0g:number of event messages a:expectation of movement region radius )(a)RW.ag=200 s.=10.(b)RWP r=200s.0=10.μ=18m.(c)m=450.=10.4=18m.(d)m=450.R=200s.=18m(e)RWP.m=450.R=200s.a=10.(0m=450.0R=200s.a=10.a=18m Table 2 Parameters of shopping mall mobility model (Galati et aL,2013). Entity Distribution Parameters K-S test distance Sellers within their workplace Lognorm 4=7.086.a=1.876 0.1405 Sellers out of their workplace Lognorm 4=6.504.a=0.51 0.1902 Customers'interarrival time Exponential B=1.771e-03 0.1144 Customers within the mall Weibull a=0.935,B=2.579e+03 0.0639 Customers within a single shop Weibull a=1.002.B=3.059e+02 0.3519 were carried by the shopkeepers and shop employees and seven of 5.2.2.Experiment result which were static,placed in fixed locations (Galati et al.2013).All of Average searching time:In Fig.5(a).we plot the average the shop employees working in two large stores,eleven smaller shops searching time of three solutions under the shopping mall mobi- and one bar.The surface area of the shopping center is 10,880 m2. lity model.We guarantee that the inputs of users'movement During the six-days'experiment,749 customers were detected by the behaviors for each solution are the same.As we can see the figures. phones carried by sellers.The shopping mall mobility model uses under the shopping mall mobility model,Crowdsensing can exponential,lognormal and Weibull probability density function to significantly reduce the average searching time than the blind mathematically model the movement of individuals in a shopping navigation.The result falls in line with the previous experiment mall.The optimal parameters for the empirical distribution were result under classical human mobility model RW and RWP.The inferred by the Maximum-Likelihood Method for each distribution average searching time of CrowdSensing is 126s which is 20%of (Galati et al,2013).Table 2 is the parameters of shopping mall blind navigation 694 s. mobility model.In our experiment,we set the speed of searcher to In Fig.5(b),we plot the average searching time of CrowdSensing 2 m/s.The speed and the pause of individuals were randomly under shopping mall mobility models with different values of og. generated according to a uniform distribution respectively between Similar results have been seen in classical mobility model,when 1.65-1.15 m/s and 0-2 s.Similarly,in the experiment we consider the the value of Og is small,the average searching time is large. simulation as an event-driven scenario,that is,when a user is Because only a few number of users could receive request approaching the vertex (tag)within a distance of less than 1 m,we messages and the searcher gets little help from others.When allow the user to leave a trace or send a query to the surrounding increasing the value of dg from 5s to 100 s,the average searching tags.For all figures presented,we run the experiment 1000 times to time is reduced from 220s to 137 s. get average values,and provide the 95%confidence interval of the Number of messages:In Fig.5(c),we plot the average number of experiment results. messages stored in the delay tolerant network as time grows
were carried by the shopkeepers and shop employees and seven of which were static, placed in fixed locations (Galati et al., 2013). All of the shop employees working in two large stores, eleven smaller shops and one bar. The surface area of the shopping center is 10,880 m2 . During the six-days' experiment, 749 customers were detected by the phones carried by sellers. The shopping mall mobility model uses exponential, lognormal and Weibull probability density function to mathematically model the movement of individuals in a shopping mall. The optimal parameters for the empirical distribution were inferred by the Maximum-Likelihood Method for each distribution (Galati et al., 2013). Table 2 is the parameters of shopping mall mobility model. In our experiment, we set the speed of searcher to 2 m/s. The speed and the pause of individuals were randomly generated according to a uniform distribution respectively between 1.65–1.15 m/s and 0–2 s. Similarly, in the experiment we consider the simulation as an event-driven scenario, that is, when a user is approaching the vertex (tag) within a distance of less than 1 m, we allow the user to leave a trace or send a query to the surrounding tags. For all figures presented, we run the experiment 1000 times to get average values, and provide the 95% confidence interval of the experiment results. 5.2.2. Experiment result Average searching time: In Fig. 5(a), we plot the average searching time of three solutions under the shopping mall mobility model. We guarantee that the inputs of users' movement behaviors for each solution are the same. As we can see the figures, under the shopping mall mobility model, CrowdSensing can significantly reduce the average searching time than the blind navigation. The result falls in line with the previous experiment result under classical human mobility model RW and RWP. The average searching time of CrowdSensing is 126 s which is 20% of blind navigation 694 s. In Fig. 5(b), we plot the average searching time of CrowdSensing under shopping mall mobility models with different values of θR. Similar results have been seen in classical mobility model, 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 5 s to 100 s, the average searching time is reduced from 220 s to 137 s. Number of messages: In Fig. 5(c), we plot the average number of messages stored in the delay tolerant network as time grows. 0 50 100 150 200 250 300 350 400 450 500 0 500 1000 1500 2000 2500 Number of user m Average searching time(s) 0 50 100 150 200 250 300 350 400 450 500 0 200 400 600 800 1000 1200 1400 1600 1800 Number of user m Average searching time(s) 0 20 40 60 80 100 120 140 160 180 200 200 250 300 350 400 Time to live of request message θR (s) Average searching time (s) 0 1 2 3 4 5 6 7 8 9 10 11 200 210 220 230 240 250 260 270 Number of event messages θ Average searching time (s) 10 20 30 40 50 60 220 240 260 280 300 320 340 Expectation of movement region radius μ (m) Average searching time (s) 0 100 200 300 400 500 600 700 0 500 1000 1500 2000 2500 3000 3500 Time (s) Number of messages Fig. 4. Comparison of the average searching time under Random Walk (RW) Mobility Model and Random Way-Point (RWP) Mobility Model with different parameters (number of users m; time to live of request message θR; number of event messages θk; expectation of movement region radius μ). (a) RW, θR ¼ 200 s, θk ¼ 10. (b) RWP, θR ¼ 200 s, θk ¼ 10, μ ¼ 18 m. (c) m¼450, θk ¼ 10, μ ¼ 18 m. (d) m¼450, θR ¼ 200 s, μ ¼ 18 m. (e) RWP, m¼450, θR ¼ 200 s, θk ¼ 10. (f) m¼450, θR ¼ 200 s, θk ¼ 10, μ ¼ 18 m. Table 2 Parameters of shopping mall mobility model (Galati et al., 2013). Entity Distribution Parameters K–S test distance Sellers within their workplace Lognorm μ ¼ 7:086, σ ¼ 1:876 0.1405 Sellers out of their workplace Lognorm μ ¼ 6:504, σ ¼ 0:51 0.1902 Customers' interarrival time Exponential β ¼ 1:771e03 0.1144 Customers within the mall Weibull α ¼ 0:935, β ¼ 2:579eþ03 0.0639 Customers within a single shop Weibull α ¼ 1:002, β ¼ 3:059eþ02 0.3519 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89 87
H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 a C 800 240 。m95 220 700 -event message (SM) 600 600 500 200 500 400 180 400 160 300 200 200 0 100 120 0 0 102030405060.708090100 100200300400500600 Time to live of request message 0(s) Time(s) Fig.5.Evaluation under shopping mall mobility model (SM)with different parameters.(a)SM.25 sellers,&=200(s).&=10.(b)SM,25 sellers.ORME,=10.(c)SM. 25 sellers.@g=200(s).&=10. When the time is about 200 s,the number of request messages peak number of event messages is 3 times as many as the peak reaches its maximum 162.The number decreases as the request number of request messages.The parameter A used in writing and message's time to live is reduced to zero.The number of event replacing strategy One Request Many Event(ORME)is in fact 3. messages grows fast between 50s to 250 s.After 350s,the number of event messages is essentially unchanged.Because no 6.Conclusion more request messages are generated after that. This paper proposes a framework called CrowdSensing,using 5.3.Discussion RFID-based delay tolerant network for indoor navigation.By suffi- ciently leveraging the "store-forward"properties of delay tolerant From the above large-scale experiment under classical human network,CrowdSensing provides an effective mechanism for indoor mobility model and the realistic experiment under shopping mall navigation.Experiment results show that CrowdSensing can effi- mobility model,we find that the number of users and the time to ciently reduce the average searching time of navigation.While live of request message are two critical factors affecting the comparing with recent approaches like Escort(Constandache et al., performance of CrowdSensing.In order to reduce the average 2010)and Intuitive Navigation,CrowdSensing can effectively reduce searching time,appropriate number of tags and value of time to the average search time by 24%and 31%respectively.Furthermore live of request message should be given in the environment.The CrowdSensing is very effective in controlling the number of event experimental results can be summarized in more detail as follows: and request messages by sufficiently leveraging the RFID tags limited memory space. Tag density should adjust with the degree of user's movement activity and user scale:The degree of user's movement activity reflects the speed of generating event messages and request Acknowledgment messages of each user.The user scale reflects the speed of generating messages of all users.Tag density must be qualified This work is partially supported by National Natural Science for the storage requirement of these messages.For example,in Foundation of China under Grant nos.61100196,61472185 our experiments,with the number of users increasing.the 61321491.91218302,61373129:Jiangsu Natural Science Founda- average searching time of our navigation solution is reduced tion under Grant no.BK2011559;Key Project of Jiangsu Research gradually.But when the number of users increased to one-third Program under Grant no.BE2013116:EU FP7 IRSES MobileCloud of the number of tags,the decrease of average searching time is Project under Grant no.612212. not obvious.Thus increasing the tag density is a method to improve the performance of navigation,but it may not drama- References tically reduce the average searching time. .Appropriate value of time to live of request message should be set: Azizyan M,Constandache L Roy Choudhury R.SurroundSense:mobile phone Time to live of request message has great influence on system localization via ambience fingerprinting.In:Proceedings of ACM MobiCom: performance of average searching time.But the value of time to 2009.p.261-72 Biswas I.Veloso M.WiFi localization and navigation for autonomous indoor mobile live of request message is not as bigger as better,because too robots.In:Proceedings of IEEE international conference on robotics and large time to live of request message will lead to longer survival automation (ICRA):2010.p.4379-84. time of messages in the system and require a much larger Bogo F.Peserico E.Optimal throughput and delay in delay-tolerant networks with ballistic mobility.In:Proceedings of ACM MobiCom:2013.p.303-14. storage space.On the contrary,too small time to live of request Camp T,Boleng J.Davies V.A survey of mobility models for ad hoc network message will lead to few helpers who can receive request research.Wirel Commun Mob Comput 2002:2(5):483-502. messages and the average searching time increases.For exam- Constandache I.Bao X.Azizyan M.Choudhury RR.Did you see bob?:human localization using mobile phones.In:Proceedings of ACM MobiCom:2010 ple,in our experiments,the value of time to live of request 0.149-60 message should not be less than 40 s. Dousse O.Mannersalo P.Thiran P.Latency of wireless sensor networks with .The proportion of memory space for event messages and request uncoordinated power saving mechanisms.In:Proceedings of ACM MobiHoc: 2004.p.109-20. messages is determined by writing and replacing strategy of tags: Fischer G.Dietrich B.Winkler F.Bluetooth indoor localization system.In:Proceed- For example,in our experiments,at the beginning,the number of ings of workshop on positioning.navigation and communication:2004 event messages is less than the number of request messages.But p.147-56. the number of event messages increases quickly after 50s in Galati A.Greenhalgh C.Crawdad data set Nottingham/mall (v.2013-02-05):2013. Galati A,Djemame K,Greenhalgh C.A mobility model for shopping mall environ- realistic experiment under shopping mall mobility model.The ments founded on real traces.Netw Sci 2013:2(1-2):1-11
When the time is about 200 s, the number of request messages reaches its maximum 162. The number decreases as the request message's time to live is reduced to zero. The number of event messages grows fast between 50 s to 250 s. After 350 s, the number of event messages is essentially unchanged. Because no more request messages are generated after that. 5.3. Discussion From the above large-scale experiment under classical human mobility model and the realistic experiment under shopping mall mobility model, we find that the number of users and the time to live of request message are two critical factors affecting the performance of CrowdSensing. In order to reduce the average searching time, appropriate number of tags and value of time to live of request message should be given in the environment. The experimental results can be summarized in more detail as follows: Tag density should adjust with the degree of user's movement activity and user scale: The degree of user's movement activity reflects the speed of generating event messages and request messages of each user. The user scale reflects the speed of generating messages of all users. Tag density must be qualified for the storage requirement of these messages. For example, in our experiments, with the number of users increasing, the average searching time of our navigation solution is reduced gradually. But when the number of users increased to one-third of the number of tags, the decrease of average searching time is not obvious. Thus increasing the tag density is a method to improve the performance of navigation, but it may not dramatically reduce the average searching time. Appropriate value of time to live of request message should be set: Time to live of request message has great influence on system performance of average searching time. But the value of time to live of request message is not as bigger as better, because too large time to live of request message will lead to longer survival time of messages in the system and require a much larger storage space. On the contrary, too small time to live of request message will lead to few helpers who can receive request messages and the average searching time increases. For example, in our experiments, the value of time to live of request message should not be less than 40 s. The proportion of memory space for event messages and request messages is determined by writing and replacing strategy of tags: For example, in our experiments, at the beginning, the number of event messages is less than the number of request messages. But the number of event messages increases quickly after 50 s in realistic experiment under shopping mall mobility model. The peak number of event messages is 3 times as many as the peak number of request messages. The parameter λ used in writing and replacing strategy One Request Many Event (ORME) is in fact 3. 6. Conclusion This paper proposes a framework called CrowdSensing, using RFID-based delay tolerant network for indoor navigation. By suffi- ciently leveraging the “store-forward” properties of delay tolerant network, CrowdSensing provides an effective mechanism for indoor navigation. Experiment results show that CrowdSensing can effi- ciently reduce the average searching time of navigation. While comparing with recent approaches like Escort (Constandache et al., 2010) and Intuitive Navigation, CrowdSensing can effectively reduce the average search time by 24% and 31% respectively. Furthermore, CrowdSensing is very effective in controlling the number of event and request messages by sufficiently leveraging the RFID tags' limited memory space. Acknowledgment This work is partially supported by National Natural Science Foundation of China under Grant nos. 61100196, 61472185, 61321491, 91218302, 61373129; Jiangsu Natural Science Foundation under Grant no. BK2011559; Key Project of Jiangsu Research Program under Grant no. BE2013116; EU FP7 IRSES MobileCloud Project under Grant no. 612212. References Azizyan M, Constandache I, Roy Choudhury R. SurroundSense: mobile phone localization via ambience fingerprinting. In: Proceedings of ACM MobiCom; 2009. p. 261–72. Biswas J, Veloso M. WiFi localization and navigation for autonomous indoor mobile robots. In: Proceedings of IEEE international conference on robotics and automation (ICRA); 2010. p. 4379–84. Bogo F, Peserico E. Optimal throughput and delay in delay-tolerant networks with ballistic mobility. In: Proceedings of ACM MobiCom; 2013. p. 303–14. Camp T, Boleng J, Davies V. A survey of mobility models for ad hoc network research. Wirel Commun Mob Comput 2002;2(5):483–502. Constandache I, Bao X, Azizyan M, Choudhury RR. Did you see bob?: human localization using mobile phones. In: Proceedings of ACM MobiCom; 2010. p. 149–60. Dousse O, Mannersalo P, Thiran P. Latency of wireless sensor networks with uncoordinated power saving mechanisms. In: Proceedings of ACM MobiHoc; 2004. p. 109–20. Fischer G, Dietrich B, Winkler F. Bluetooth indoor localization system. In: Proceedings of workshop on positioning, navigation and communication; 2004. p. 147–56. Galati A, Greenhalgh C. Crawdad data set Nottingham/mall (v. 2013-02-05); 2013. Galati A, Djemame K, Greenhalgh C. A mobility model for shopping mall environments founded on real traces. Netw Sci 2013;2(1–2):1–11. 0 100 200 300 400 500 600 700 800 Average searching time (s) 0 10 20 30 40 50 60 70 80 90 100 120 140 160 180 200 220 240 Time to live of request message θR (s) Average searching time (s) 0 100 200 300 400 500 600 0 100 200 300 400 500 600 700 Time (s) Number of messages Fig. 5. Evaluation under shopping mall mobility model (SM) with different parameters. (a) SM, 25 sellers, θR ¼ 200ðsÞ, θk ¼ 10. (b) SM, 25 sellers, ORME, θk ¼ 10. (c) SM, 25 sellers, θR ¼ 200ðsÞ, θk ¼ 10. 88 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89