IONavi: An Indoor-Outdoor Navigation Service via Mobile Crowdsensing

Abstract

The proliferation of mobile computing has prompted navigation to be one of the most attractive and promising applications. Conventional designs of navigation systems mainly focus on either indoor or outdoor navigation. However, people have a strong need for navigation from a large open indoor environment to an outdoor destination in real life. This article presents IONavi, a joint navigation solution, which can enable passengers to easily deploy indoor-outdoor navigation service for subway transportation systems in a crowdsourcing way. Any self-motivated passenger records and shares individual walking traces from a location inside a subway station to an uncertain outdoor destination within a given range, such as one kilometer. IONavi further extracts navigation traces from shared individual traces, each of which is not necessary to be accurate. A subsequent following user achieves indoor-outdoor navigation services by tracking a recommended navigation trace. Extensive experiments are conducted on a subway transportation system. The experimental results indicate that IONavi exhibits outstanding navigation performance from an uncertain location inside a subway station to an outdoor destination. Although IONavi is to enable indoor-outdoor navigation for subway transportation systems, the basic idea can naturally be extended to joint navigation from other open indoor environments to outdoor environments.

References

1. Moustafa Alzantot and Moustafa Youssef. 2012. Crowdinside: Automatic construction of indoor floorplans. In Proc. of SIGSPATIAL.
2. Paramvir Bahl and Venkata N. Padmanabhan. 2000. RADAR: An in-building RF-based user location and tracking system. In Proc. of IEEE Infocom.
3. Si Chen, Muyuan Li, Kui Ren, and Chunming Qiao. 2015. CrowdMap: Accurate reconstruction of indoor floor plans from crowdsourced sensor-rich videos. In Proc. of IEEE ICDCS.
4. Tao Chen, Deke Guo, Yuan He, Honghui Chen, Xue Liu, and Xueshan Luo. 2013. A bloom filters based dissemination protocol in wireless sensor networks. Ad Hoc Networks 11, 4 (2013), 1359--1371.
5. Tao Chen, Zheng Yang, Yunhao Liu, Deke Guo, and Xueshan Luo. 2011. Localization in non-localizable sensor and ad-hoc networks: A localizability-aided approach. In Proc. of IEEE Infocom.
6. Jiang Dong, Yu Xiao, Marius Noreikis, Zhonghong Ou, and Antti Yla-Jaaski. 2015. iMoon: Using smartphones for image-based indoor navigation. In Proc. of ACM SenSys.
7. Dan Feldman, Cynthia R. Sung, Andrew Sugaya, and Daniela Rus. 2015. iDiary: From GPS signals to a text-searchable diary. ACM Transactions on Sensor Networks. 11, 4 (2015), 60.
8. Nivan Ferreira, James T. Klosowski, Carlos Eduardo Scheidegger, and Cláudio T. Silva. 2013. Vector field k-means: Clustering trajectories by fitting multiple vector fields. Eurographics Conference on Visualization. 32, 3 (2013), 201--210.
9. Dieter Fox, Jeffrey Hightower, Lin Liao, Dirk Schulz, and Gaetano Borriello. 2003. Bayesian filtering for location estimation. IEEE Pervasive Computing. 2, 3 (2003), 24--33.
10. Ruipeng Gao, Yang Tian, Fan Ye, Luo Guojie, Kaigui Bian, Yizhou Wang, Tao Wang, and Xiaoming Li. 2014a. Sextant: Towards ubiquitous indoor localization service by photo-taking of the environment. IEEE Transactions on Mobile Computing. 13, 9 (2014), 1--14.
11. Ruipeng Gao, Mingmin Zhao, Tao Ye, Fan Ye, Yizhou Wang, Kaigui Bian, Tao Wang, and Xiaoming Li. 2014b. Jigsaw: Indoor floor plan reconstruction via mobile crowdsensing. In Proc. of ACM MobiCom.
12. Gerald Glanzer and Ulrich Walder. 2010. Self-contained indoor pedestrian navigation by means of human motion analysis and magnetic field mapping. In Proc. of IEEE WPNC.
13. Robert Harle. 2013. A survey of indoor inertial positioning systems for pedestrians. IEEE Communications Surveys. 15, 3 (2013), 1281--1293.
14. Yiqing Hu, Yan Xiong, Wenchao Huang, Xiangyang Li, Yanan Zhang, Xufei Mao, and Caimei Wang. 2015. Lightitude: Indoor positioning using ubiquitous visible lights and COTS devices. In Proc. of IEEE ICDCS.
15. Lee Inje, Giwan Yoon, and Dongsoo Han. 2011. Nerimi: WiFi-based subway navigation system. In Intelligent Radio for Future Personal Terminals.
16. Yifei Jiang, Xiang Yun, Xin Pan, Kun Li, Qin Lv, Robert P. Dick, Li Shang, and Michael Hannigan. 2013. Hallway based automatic indoor floorplan construction using room fingerprints. In Proc. of ACM UbiComp.
17. Daniel Keysers, Thomas Deselaers, and Hermann Ney. 2004. Pixel-to-pixel matching for image recognition using Hungarian graph matching. DAGM-Symposium (2004), 154--162.
18. Ye-Sheng Kuo, Pat Pannuto, Ko-Jen Hsiao, and Prabal Dutta. 2014. Luxapose: Indoor positioning with mobile phones and visible light. In Proc. of ACM MobiCom.
19. Jae-Gil Lee, Jiawei Han, Xiaolei Li, and Hector Gonzalez. 2008. TraClass: Trajectory classification using hierarchical region-based and trajectory-based clustering. In Proc. of ACM PVLDB.
20. Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. 2007. Trajectory clustering: A partition-and-group framework. In Proc. of ACM SIGMOD.
21. Fan Li, Chunshui Zhao, Guanzhong Ding, Jian Gong, Chenxing Liu, and Feng Zhao. 2012. A reliable and accurate indoor localization method using phone inertial sensors. In Proc. of ACM UbiComp.
22. Haochao Li, Kaishun Wu, Qian Zhang, and Lionel M. Ni. 2014c. CUTS: Improving channel utilization in both time and spatial domain in WLANs. IEEE Transactions on Parallel and Distributed Systems 25, 6 (2014), 1413--1423.
23. Liqun Li, Pan Hu, Chunyi Peng, Guobin Shen, and Feng Zhao. 2014a. Epsilon: A visible light based positioning system. In Proc. of USENIX NSDI. Seattle, WA.
24. Liqun Li, Guobin Shen, Chunshui Zhao, Thomas Moscibroda, Jyh-Han Lin, and Feng Zhao. 2014b. Experiencing and handling the diversity in data density and environmental locality in an indoor positioning service. In Proc. of ACM MobiCom.
25. Mo Li, Pengfei Zhou, Yuanqing Zheng, Zhenjiang Li, and Guobin Shen. 2015. IODetector: A generic service for indoor/outdoor detection. ACM Transactions on Sensor Networks. 11, 21 (2015), 28.
26. Hongbo Liu, Yu Gan, Jie Yang, Simon Sidhom, Yan Wang, Yingying Chen, and Fan Ye. 2012. Push the limit of Wi-Fi based localization for smartphones. In Proc. of ACM MobiCom.
27. Tie Luo, Salil S. Kanhere, Hwee-Pink Tan, Fan Wu, and Hongyi Wu. 2015. Crowdsourcing with tullock contests: A new perspective. In Proc. of IEEE INFOCOM.
28. Alessandro Mulloni, Daniel Wagner, István Barakonyi, and Dieter Schmalstieg. 2009. Indoor positioning and navigation with camera phones. IEEE Pervasive Computing. 8, 2 (2009), 22--31.
29. Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial optimization: Algorithms and complexity. Dover Publications.
30. Damian Philipp, Patrick Baier, Christoph Dibak, Frank Dürr, Kurt Rothermel, Susanne Becker, Michael Peter, and Dieter Fritsch. 2014. Mapgenie: Grammar-enhanced indoor map construction from crowd-sourced data. In Proc. of IEEE PerCom.
31. Jothi V. Prakash and Dr LM Nithya. 2014. A survey on semi-supervised learning techniques. In arXiv preprint arXiv:1402.4645.
32. Valentin Radu, Panagiota Katsikouli, Rik Sarkar, and Mahesh K. Marina. 2014. A semi-supervised learning approach for robust indoor-outdoor detection with smartphones. In Proc. of ACM Sensys.
33. Anshul Rai, Krishna Kant Chintalapudi, Venkata N. Padmanabhan, and Rijurekha Sen. 2012. Zee: Zero-effort crowdsourcing for indoor localization. In Proc. of ACM MobiCom.
34. Alex Rodriguez and Alessandro Laio. 2014. Clustering by fast search and find of density peaks. Science 344, 6191 (2014), 1492--1496.
35. Sarta Sahni and Teofilo Gonzalez. 1976. P-complete approximation problems. J. ACM. 23, 3 (1976), 555--565.
36. Muhammad N. Sakib, Junaed Bin Halim, and Chin-Tser Huang. 2014. Determining location and movement pattern using anonymized WiFi access point BSSID. In Proc. of IEEE SecTech.
37. Guobin Shen, Zhuo Chen, Peichao Zhang, Thomas Moscibroda, and Yongguang Zhang. 2013. Walkie-Markie: Indoor pathway mapping made easy. In Proc. of USENIX NSDI.
38. Yuanchao Shu, Kang G. Shin, Tian He, and Jiming Chen. 2015. Last-Mile navigation using smartphones. In Proc. of ACM MobiCom.
39. S. Skiena. 1990. Dijkstra’s algorithm. In Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Addison-Wesley, Reading, MA, 225--227.
40. Chun-Jung Sun, Hong-Yi Kuo, and Chin E. Lin. 2010. A sensor based indoor mobile localization and navigation using unscented kalman filter. In Proc. of IEEE LPLANS. I
41. Jorma Tarhio and Esko Ukkonen. 1993. Approximate Boyer-Moore string matching. Society for Industrial and Applied Mathematics. 22, 2 (1993), 243--260.
42. Xiaoqiang Teng, Deke Guo, Xiaolei Zhou, and Zhong Liu. 2015. Poster: An indoor-outdoor navigation service for subway transportation systems. In Proc. of ACM SenSys.
43. Guanhua Wang, Shanfeng Zhang, Kaishun Wu, Qian Zhang, and Lionel M. Ni. 2016. Tim: Fine-grained rate adaptation in WLANs. IEEE Transactions on Mobile Computing 15, 3 (2016), 748--761.
44. He Wang, Souvik Sen, Ahmed Elgohary, Moustafa Farid, Moustafa Youssef, and Romit Roy Choudhury. 2012. No need to war-drive: Unsupervised indoor localization. In Proc. of ACM MobiSys.
45. Shenlong Wang, Sanja Fidler, and Raquel Urtasun. 2015. Lost shopping! Monocular localization in large indoor spaces. In Proc. of IEEE ICCV.
46. Kaishun Wu, Haochao Li, Lu Wang, Youwen Yi, Yunhuai Liu, Dihu Chen, Xiaonan Luo, Qian Zhang, and Lionel M. Ni. 2013. hJam: Attachment transmission in WLANs. IEEE Transactions on Mobile Computing 12, 12 (2013), 2334--2345.
47. Bo Xie, Guang Tan, and Tian He. 2015. Spinlight: A high accuracy and robust light positioning system for indoor applications. In Proc. of ACM SenSys. Seoul, Korea.
48. Dejun Yang, Guoliang Xue, Xi Fang, and Jian Tang. 2012b. Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing. In Proc. of ACM MobiCom.
49. Zheng Yang, Chenshu Wu, and Yunhao Liu. 2012a. Locating in fingerprint space: Wireless indoor localization with little human intervention. In Proc. of ACM MobiCom.
50. Xiang Zhang, Guoliang Xue, Ruozhou Yu, Dejun Yang, and Jian Tang. 2015. Truthful incentive mechanisms for crowdsourcing. In Proc. of IEEE INFOCOM.
51. Yuanqing Zheng, Guobin Shen, Liqun Li, Chunshui Zhao, Mo Li, and Feng Zhao. 2014. Travi-Navi: Self-deployable indoor navigation system. In Proc. of ACM MobiCom.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Robotics

• Networks

  • Network properties

    • Network reliability