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).6=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 drama￾tically 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 exam￾ple, 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 Founda￾tion 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: Proceed￾ings 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 environ￾ments 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