||Data Localization Correction and Obstacle Tolerant Path Planning Algorithms for Sensor Networks
||Institute of Manufacturing Information and Systems
underwater wireless sensor networks
在感測網路的許多應用中，定位是一個重要的技術之一，許多應用都必須仰賴定位技術的支持，像是資料匯集，目標追蹤，路由協定等。本論文的研究可分為兩個部分：(1)資料定位校正以及(2)路徑規劃。相比於陸地上的感測網路，海底無線感測網路(UWSNs)存在更多的限制與挑戰，水下的感測器是動態的，感測器位置不斷的變化，為靜態感測網路設計的定位方法不能應用於UWSNs。本文提出了一種採用資料位置校正的定位方法，稱為Data Localization Correction Approach（DLCA），可不需要額外耗費通訊成本和感測器電力的情況下定位。在不失一般性的情況下，我們基於kinematic model和meandering current mobility model來模擬海洋的環境，實驗結果表明，DLCA可以顯著地降低通訊成本，同時保持較高的定位精準度。然而，為了降低佈署成本以及環境上的限制，Mobile-Anchor-Node-Assisted Localization（MANAL）是一種可行的網路架構。移動錨節點（mobile-anchor-node, MAN）提供其自己的位置資訊以幫助感測器定位。然而，在現實的環境中，因為障礙物阻擋了MAN所經過的路徑，使得感測器不能從MAN接收足夠的三個位置資訊。我們提出了obstacle tolerant path planning (OTPP)方法來解決由於障礙物導致的感測器無法定位的問題。OTPP近似最佳化信標點的數量和路徑規劃，確保所有感測器可以從MAN接收三個位置資訊並減少MAN廣播的次數。實驗結果顯示，OTPP比Z-curve 表現更好，因為它使用較少的信標點總數，因此更適合於存在障礙物的環境。與Z-curve相比，OTPP可以減少定位誤差並提高定位覆蓋率。
In many applications of sensor networks, localization is an important technology. Many applications rely on localization technologies, such as data aggregation, target tracking, and routing protocols. This thesis can be divided into two parts: (1) data localization correction and (2) path planning. Underwater wireless sensor networks (UWSNs) demonstrate more limitations and challenges than terrestrial sensing networks. Underwater sensors are dynamic, and sensor positions are changing constantly. Localization schemes designed for static sensor networks cannot be applied to UWSNs. This thesis presents a hybrid localization approach with data-location correction, called Data Localization Correction Approach (DLCA), which positions data without additional communication overhead and power consumption on sensors. Without loss of generality, we simulate the ocean environment based on a kinematic model and meandering current mobility model. Our results show that DLCA can significantly reduce communication costs, while maintaining relatively high localization accuracy. However, to reduce deployment costs and environmental constraints, Mobile-Anchor-Node-Assisted Localization is a viable network architecture. A mobile anchor node (MAN) provides its own location information to assist the localization of sensor nodes. However, in a realistic environment, sensor nodes generally cannot be located because the obstacles block the path traversed by the MAN, thereby rendering the sensor incapable of receiving sufficient three location information from the MAN. We proposed the obstacle tolerant path planning (OTPP) approach to solve the problem of sensor not being located owing to obstacle blocking. OTPP can approximate the optimum beacon point number and path planning, thereby ensuring that all the unknown nodes can receive the three location information from the MAN and reduce the number of MAN broadcast packet times. Based on the experiment results, OTPP performs better than Z-curve because it uses less total number of beacon points and is thus more suitable in an obstacle-present environment. Compared with the Z-curve, OTPP can reduce localization error and improve localization coverage.
TABLE OF CONTENTS IV
CHAPTER 1 INTRODUCTION 1
1.1 Localization and Challenges in Underwater Sensor Networks 1
1.2 Path Planning and Challenges for Mobile Anchor Node Assisted Localization 4
1.3 Localization Schemes 7
1.3.1 Centralized Localization and Distributed Localization 7
1.3.2 Anchor Based versus Anchorless 7
1.3.3 Range Based versus Range Free 8
1.4 Distance Estimation Technologies 12
CHAPTER 2 RELATED WORKS 16
2.1 Localization Algorithms 17
2.1.1 Stationary Localization Algorithms 17
2.1.2 Mobile Localization Algorithms 22
2.1.3 Mixed Localization Algorithms 28
2.2 Path Planning Algorithm 35
2.2.1 Offline Path Planning 36
2.2.2 Online Path Planning 44
CHAPTER 3 DESIGN OF DLCA 49
3.1 Network Topology 49
3.2 Overview of DLCA 50
3.2.1 Node Localization 51
3.2.2 Data Packet Format for Data-Location Correction 51
3.2.3 Data Structure of DLCA 53
3.2.4 DLCA Table Initialization 54
3.3 Recursive Correcting Data Packet Localization 56
3.3.1 Find Victim Node 56
3.3.2 Compute Location of Victim Node by Shift Vectors 58
3.3.3 Recursively Correct Data Locations 60
3.4 Summary 60
CHAPTER 4 DESIGN OF OTPP 62
4.1 Preliminary 63
4.2 Problem Description 64
4.3 Obstacle-Tolerant Path Planning Algorithm 67
4.3.1 Deployment of Beacon Points in OTPP 67
4.3.2 Path Planning in OTPP 73
4.4 Summary 75
CHAPTER 5 SIMULATION RESULTS 76
5.1 DLCA Performance Evaluation 76
5.1.1 Simulation Settings 76
5.2 Results and Analysis 80
5.2.1. Performance with Varying Average Moving Speed 80
5.2.2. Performance with Varying Times of Pd 81
5.2.3. Performance with Varying Anchor Percentage 83
5.3 OTPP Performance Evaluation 85
5.3.1 Simulation Setup 87
5.4 Results and Analysis 88
5.4.1 Impact of Blocking Rate 88
5.4.2 Impact of Resolution 92
5.4.3 OTPP versus Online Path Planning Algorithms 94
CHAPTER 6 CONCLUSION AND FUTURE WORKS 96
 H.-P. Tan, R. Diamant, W. K. G. Seah, and M. Waldmeyer, “A survey of techniques and challenges in underwater localization,” Ocean Engineering, vol. 38, no. 14-15, pp. 1663–1676, 2011.
 M. Beniwal and R. Singh, “Localization techniques and their challenges in underwater wireless sensor networks,” International Journal of Computer Science and Information Technologies, vol. 5, pp. 4706–4710, 2014.
 G. Han, J. Jiang, L. Shu, Y. Xu, and F. Wang, “Localization algorithms of underwater wireless sensor networks: a survey,” Sensors, vol. 12, no. 2, pp. 2026–2061, 2012.
 M. Erol-Kantarci, H. T. Mouftah, and S. Oktug, “A survey of architectures and localization techniques for underwater acoustic sensor networks,” IEEE Communications Surveys & Tutorials, vol. 13, no. 3, pp. 487–502, 2011.
 V. Garg and M. Jhamb, “A review of wireless sensor network on localization techniques,” International Journal of Engineering Trends and Technology, vol. 4, pp. 1049–1053, 2013.
 T. J. S. Chowdhury, C. Elkin, V. Devabhaktuni, D. B. Rawat, and J. Oluoch, “Advances on localization techniques for wireless sensor networks: a survey,” Computer Networks, vol. 110, pp. 284–305, 2016.
 G. Han, H. Xu, T. Q. Duong, J. Jiang, and T. Hara, “Localization algorithms of wireless sensor networks: a survey,” Telecommunication Systems, vol. 52, pp. 1–18, 2011.
 J. Chen, X. Wu and G. Chen, “REBAR:A reliable and energy balanced routing algorithm for UWSNs,” International Conference on Grid and Cooperative Computing (GCC), pp. 349-355, 2008.
 G. Isbitiren and O. B. Akan, “Three-Dimensional Underwater Target Tracking With Acoustic Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 60, pp. 3897-3906, 2011.
 M. T. Isik and O. B. Akan, “A three-dimensional localization algorithm for underwater acoustic sensor networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 9, pp. 4457–4463, 2009.
 P. H. Tsai, R. G. Tsai, and S. S. Wang, “Hybrid localization approach for underwater sensor networks,” Journal of Sensors, vol. 2017, 2017.
 I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol.40, no.8, pp. 102-114, 2002.
 G. Han, J. Jiang, C. Zhang, T. Duong, M. Guizani and G. Karagiannidis, “A survey on mobile anchor node assisted localization in wireless sensor networks,” IEEE communication surveys & Tutorials, vol. 18, no. 3, pp. 2220–2243, 2016.
 J. Rezazadeh, M. Moradi, A.S. Ismail, E. Dutkiewicz, “Superior path planning mechanism for mobile beacon-assisted localization in wireless sensor networks,” IEEE Sensors Journal, vol.14, no.9, pp.3052-3064, 2014.
 Z. Guo et al., “Perpendicular intersection: Locating wireless sensors with mobile beacon,” IEEE Transactions on Vehicular Technology, vol. 59, no. 7, pp. 3501–3509, 2010.
 C. Ou and W. He, “Path planning algorithm for mobile anchor-based localization in wireless sensor networks,” IEEE Sensors Journal, vol. 13, no. 2, pp. 466–475, 2013.
 M. DeLeon, “A study of sufficient conditions for Hamiltonian cycles,” Rose-Hulman Undergraduate Math Journal, vol. 1, no. 1, 2000.
 M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W.H. Freeman, ISBN 0-7167-1045-5, 1979.
 M. R. Garey, D. S. Johnson, L. Stockmeyer, “Some simplified NP-complete problems,” in Proceedings of 6th ACM Symposium on Theory of Computing (STOC’74), pp. 47-63, 1974.
 R.G. Tsai and P.H. Tsai, “An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization,” Sensors, vol. 18, no. 3, 2018.
 S. Lee and K. Kim, “Localization with a mobile beacon in underwater sensor networks,” in Proceedings of the IEEE/IFIP 8th International Conference on Embedded and Ubiquitous Computing, EUC ’10, pp. 316–319, December 2010.
 J. Blumenthal, R. Grossmann, F. Golatowski, and D. Timmermann, “Weighted centroid localization in zigbee-based sensor networks,” in Proceedings of IEEE International Symposium on Intelligent Signal Processing, Oct. 2007, pp. 1–6.
 H. Xiong, Z. Chen, W. An, and B. Yang, “Robust TDoA localization algorithm for asynchronous wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 2015, pp. 1-10, 2015.
 H. Shao, X. Zhang, and Z. Wang, “Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables,” IEEE Transactions on Signal Processing, vol. 62, no. 10, pp. 2580–2594, Apr. 2014.
 S. A. Golden and S. S. Bateman, “Sensor measurements for Wi-Fi location with emphasis on time-of-arrival ranging,” IEEE Transactions on Mobile Computing, vol. 6, no. 10, pp. 1185–1198, 2007.
 H. Xiong, Z. Chen, W. An, and B. Yang, “Robust TDOA localization algorithm for asynchronous wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 2015, 2015.
 K. K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Ad-hoc localization using ranging and sectoring,” in Proceedings of the IEEE INFOCOM2004 - Conference on Computer Communications -Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 2662–2672, March 2004.
 J. Liu, Z. Zhou, Z. Peng, J.-H. Cui, M. Zuba, and L. Fiondella, “Mobi-sync: efficient time synchronization for mobile underwater sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 2, pp. 406–416, 2013.
 J. Liu, Z. Wang, M. Zuba, Z. Peng, J.-H. Cui, and S. Zhou, “DA-Sync: a doppler-assisted time-synchronization scheme for mobile underwater sensor networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 3, pp. 582–595, 2014.
 Z. Li, Z. Guo, F. Hong, and L. Hong, “E2DTS: an energy efficiency distributed time synchronization algorithm for underwater acoustic mobile sensor networks,” Ad Hoc Networks, vol. 11, no. 4, pp. 1372–1380, 2013.
 J. Liu, Z. Wang, J.-H. Cui, S. Zhou, and B. Yang, “A joint time synchronization and localization design for mobile underwater sensor networks,” IEEE Transactions on Mobile Computing, vol. 15, no. 3, pp. 530–543, 2016.
 K. Chen, M. Ma, E. Cheng, F. Yuan, and W. Su, “A survey on MAC protocols for underwater wireless sensor networks,” IEEE Communications Surveys Tutoials, vol. 16, pp. 1433–1447, 2014.
 H. Ramezani, F. Fazel, M. Stojanovic, and G. Leus, “Collision tolerant and collision free packet scheduling for underwater acoustic localization,” IEEE Transactions on Wireless Communications, vol. 14, no. 5, pp. 2584–2595, 2015.
 V. Chandrasekhar and W. K. G. Seah, “An area localization scheme for underwater sensor networks,” in Proceedings of IEEE Oceans Asia Pacific Conference, pp. 1–8, 2007.
 Z. Zhou, J.-H. Cui, and S. Zhou, “Efficient localization for largescale underwater sensor networks,” Ad Hoc Networks, vol. 8, no. 3, pp. 267–279, 2010.
 X. Cheng, H. Shu, Q. Liang, “A range-difference based self-positioning scheme for underwater acoustic sensor networks,” in Proceedings of the International Conference on Wireless Algorithms, Systems and Applications (WASA), pp. 38–43, 2007.
 W. Cheng, A.Y. Teymorian, L. Ma, X. Cheng, X. Lu, Z. Lu, “Underwater localization in sparse 3D acoustic sensor networks,” in Proceedings of the IEEE INFOCOM, 2008.
 A. Y. Teymorian, W. Cheng, L. Ma, X. Cheng, X. Lu, and Z. Lu, “3D underwater sensor network localization,” IEEE Transactions on Mobile Computing, vol. 8, no. 12, pp. 1610–1621, 2009.
 W. Cheng, A. Thaeler, X. Cheng, F. Liu, X. Lu, “Time-synchronization free localization in large scale underwater acoustic sensor networks,” in Proceedings of 29th IEEE International Conference on Distributed Computing System Workshops, pp. 80–87, 2009.
 N. H. Kussat, C. D. Chadwell, Rosa Zimmerman, “Absolute positioning of an autonomous underwater vehicle using GPS and acoustic measurements,” IEEE Journal of Oceanic Engineering, vol. 30, pp. 153-164, 2005.
 D. Mirza and C. Schurgers, “Energy-efficient ranging for post-facto self-localization in mobile underwater networks,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 9, pp. 1697–1707, 2008.
 D. Mirza and C. Schurgers, “Motion-aware self-localization for underwater networks,” in Proceedings of the 3rd ACM International Workshop on Underwater Networks, pp. 51–58, 2008.
 D. Mirza and C. Schurgers, “Collaborative localization for fleets of underwater drifters,” in Proceedings of the OCEANS, pp. 1–6, Vancouver, Canada, October 2007.
 M. Erol, L. F. M. Vieira, and M. Gerla, “Localization with Dive‘N’Rise (DNR) beacons for underwater acoustic sensor networks,” in Proceedings of the 2007 International Conference on Mobile Computing and Networking, MobiCom ’07 – Second Workshop on Underwater Networks, WUWNet’07, pp. 97–100, September 2007.
 M. Erol, L. F. M. Vieira, A. Caruso, F. Paparella, M. Gerla, and S. Oktug, “Multi stage underwater sensor localization using mobile beacons,” in Proceedings of the 2nd International Conference on Sensor Technologies and Applications, pp. 710–714, Cap Esterel, France, August 2008.
 M. Erol, L. F. M. Vieira, and M. Gerla, “AUV-aided localization for underwater sensor networks,” in Proceedings of the Proceeding of the 2nd Annual International Conference on Wireless Algorithms, Systems, and Applications (WASA ’07), pp. 44–54, Chicago, Ill, USA, August 2007.
 M. Waldmeyer, H.-P. Tan, and W. K. G. Seah, “Multi-stage AUV aided localization for underwater wireless sensor networks,” in Proceedings of the IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA’11), pp. 908–913, March 2011.
 Z. Zhou, Z. Peng, J.-H. Cui, Z. Shi, and A. Bagtzoglou, “Scalable localization with mobility prediction for underwater sensor networks,” IEEE Transactions on Mobile Computing, vol. 10, no. 3, pp. 335–348, 2011.
 J. Callmer, M. Skoglund, and F. Gustafsson, “Silent localization of underwater sensors using magnetometers” EURASIP Journal on Advances in Signal Processing, vol. 2010, 8 pages, 2010.
 Y. Zhang, J. Liang, S. Jiang, and W. Chen, “A localization method for underwater wireless sensor networks based on mobility prediction and particle swarm optimization algorithms,” Sensors, vol. 16, no. 2, 2016.
 M. Liu, X. Guo, and S. Zhang, “Localization based on best spatial correlation distance mobility prediction for underwater wireless sensor networks,” in Proceedings of the 34th Chinese Control Conference, CCC ’15, pp. 7827–7832, July 2015.
 G. Zhu, R. Jiang, L. Xie, and Y. Chen, “A distributed localization scheme based on mobility prediction for underwater wireless sensor networks,” in Proceedings of the 26th Chinese Control and Decision Conference, CCDC ’14, pp. 4863–4867, June 2014.
 Y. Zhou, B. Gu, K. Chen, J. Chen, H. Guan, “An range-free localization scheme for large scale underwater wireless sensor networks,” Journal of Shanghai Jiaotong University (Science), vol. 14, no.5, pp. 562-568, 2009.
 H. Luo, Y. Zhao, Z. Guo, S. Liu, P. Chen, and L. M. Ni, “UDB: using directional beacons for localization in underwater sensor networks,” in Proceedings of 14th IEEE International Conference on Parallel and Distributed Systems, ICPADS ’08, pp. 551–558, December 2008.
 H. Luo, Z. Guo, W. Dong, F. Hong, and Y. Zhao, “LDB: localization with directional beacons for sparse 3D underwater acoustic sensor networks,” Journal of Networks, vol. 5, no. 1, pp. 28–38, 2010.
 D. Koutsonikolas, S. M. Das, and Y. C. Hu, “Path planning of mobile landmarks for localization in wireless sensor networks,” Computer Communications, vol. 30, no. 13, pp. 2577–2593, 2007.
 Y. L. Yang and L. H. Zhang, “Dynamic path planning of mobile beacon for localization in wireless sensor network,” in Proceedings of International Conference on Wireless Communications & Signal Processing (WCSP), 2013.
 J. Li and K. Yang, “Improvement of path planning in mobile beacon assisted positioning,” in 7th International Conference on Intelligent Computing, Springer, Heidelberg, pp. 309–316, 2011.
 F. Zhao, H. Luo, and Q. Lin, “A mobile beacon-assisted localization algorithm based on network-density clustering for wireless sensor networks,” In Proceedings of 5th International Conference on Mobile Ad-hoc and Sensor Networks, 2009, pp. 304–310.
 K. Kim and W. Lee, “MBAL: A mobile beacon-assisted localization scheme for wireless sensor networks,” in Proceedings of 16th International Conference on Computer Communications and Networks, 2007, pp. 57–62.
 X. Li, N. Mitton, I. Simplot-Ryl, and D. Simplot-Ryl, “Dynamic beacon mobility scheduling for sensor localization,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 8, pp. 1439–1452, Aug. 2012.
 A. T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna, “Path planning with obstacle avoidance based on visibility binary tree algorithm,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1440–1449, Dec. 2013.
 H. Li, J. Wang, X. Li, and H. Ma, “Real-time path planning of mobile anchor node in localization for wireless sensor networks,” in Proceedings of International Conference on Information and Automation, Jun. 2008, pp. 384–389.
 S. M. Mazinani and F. Farnia, “Localization in wireless sensor network using a mobile anchor in obstacle environment,” International Journal of Computer and Communication Engineering, vol. 2, no. 4, pp. 438–441, Jul. 2013.
 Y. Ding, C. Wang, and L. Xiao, “Using mobile beacons to locate sensors in obstructed environments,” Journal of Parallel and Distributed Computing, vol. 70, no. 6, pp. 644–656, Jun. 2010.
 R. Huang and G. V. Za ruba, “Static path planning for mobile beacons to localize sensor networks,” in proceedings of 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2007, pp. 323–330.
 Z. Hu, D. Gu, Z. Song, and H. Li, “Localization in wireless sensor networks using a mobile anchor node,” in proceedings of IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 2008, pp. 602–607.
 B. Zhang, F. Yu, and Z. Zhang, “Collaborative localization algorithm for wireless sensor networks using mobile anchors,” in Proceedings of the 2nd Asia-Pacific Conference on Computational Intelligence and Industrial Applications (PACIIA '09), 2009, pp. 309–312.
 G. Han, H. Xu, J. Jiang, L. Shu, T. Hara, and S. Nishio, “Path planning using a mobile anchor node based on trilateration in wireless sensor networks,” Wireless Communications and Mobile Computing, vol. 14. no. 14, pp. 1324–1336, 2011.
 K. F. Ssu, C. H. Ou, and H. C. Jiau, “Localization with mobile anchor points in wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol. 54, no. 3, pp. 1187–1197, 2005.
 T. Ojha and S. Misra, “MobiL: a 3-dimensional localization scheme for Mobile Underwater Sensor Networks,” in Proceedings of 2013 National Conference on Communications, NCC ’13, February 2013.
 V. K. Chaurasiya, N. Jain, and G. C. Nandi, “A novel distance estimation approach for 3D localization in wireless sensor network using multi dimensional scaling,” Information Fusion, vol. 15, pp. 5–18, Jan. 2014.
 C. Bechaz and H. Thomas, “GIB System: the underwater GPS solution,” in Proceedings of the 5th Europe Conference on Underwater Acoustics, 2000.
 T. C. Austin, R. P. Stokey, and K. M. Sharp, “PARADIGM: A buoy-based system for AUV navigation and tracking,” Oceans Conference Record (IEEE), vol. 2, pp. 935–938, 2000.
 S. P. Beerens, H. Ridderinkhof, and J. T. F. Zimmerman, “An analytical study of chaotic stirring in tidal areas,” Chaos, Solitons & Fractals, vol. 4, no. 6, pp. 1011–1029, 1994.
 A. Caruso, F. Paparella, L. F. M. Vieira, M. Erol, and M. Gerla, “The meandering current mobility model and its impact on underwater mobile sensor networks,” in Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM ’08), pp. 221–225, Phoenix, Ariz, USA, 2008.
 G. Han, A. Qian, C. Zhang, Y. Wang, and J. J. P. C. Rodrigues, “Localization algorithms in large-scale underwater acoustic sensor networks: a quantitative comparison,” International Journal of Distributed Sensor Networks, vol. 2014, Article ID 379382, 11 pages, 2014.
 D. Niculescu and B. Nath, “Ad hoc positioning system (APS) using AOA,” in Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM’03), vol. 3, pp. 1734–1743, San Francisco, Calif, USA, 2003.
 J. Albowicz, A. Chen, and L. Zhang, “Recursive position estimation in sensor networks,” in Proceedings of the 2001 International Conference on Network Protocols ICNP, pp. 35–41, 2001.
 T. S. Rappaport, “Wireless Communications: Principles and Practice,” 2nd ed. Upper Saddle River, NJ, USA: Prentice-Hall, 2001.