无线传感器网络自定位技术研究
摘要
随着无线通信技术、传感器技术以及嵌入式技术的飞速发展,无线传感器网络应运而生,成为目前国内外研究的重点课题。
传感器节点的定位技术是无线传感器网络的关键技术之一,对传感器网络应用的有效性起着重要作用。目前国内外已经研究出许多种节点的定位算法,但各有各的特点,同时有各自适用的场合。
本文首先对目前研究较为普遍的几种定位算法进行综合分析,了解各自的特点。考虑到算法的复杂性和精确性,深入研究了一种DV-Hop (Distance Vector-Hop)定位算法。给出了算法的基本原理,并分析了该算法的不足之处。其次,为了提高定位的精度,对DV-Hop算法进行了改进,并通过仿真进行验证。仿真结果表明,平均每跳距离计算方法的改进以及质心算法的引入,实现了更精确的节点定位。
最后对论文的工作进行了总结,并对下一步的工作进行了展望。
With the rapid development of wireless communication technology,sensor technology and embedded technology,wireless sensor networks have emerged as the focus of research topics all over the world recently.
The sensor nodes localization technology is one of the key technologies of wireless sensor networks,and plays an important role in the application's effectiveness.Recently,there are many kinds of nodes localization algorithms which have been studied all over the world already,but each has its own characteristics, simultaneously has its own suitable situation.
This thesis firstly makes a comprehensive analysis of several common localization algorithms recently,and undstands each characteristics of their own. Considering the complexity and accuracy of the algorithm, a DV-Hop(Distance Vector-Hop) localization algorithm is studied in detail. The basic principle of algorithm is given, and the shortcomings of the algorithm is also analyzed.Secondly, in order to improve the localization accuracy,the DV-Hop algorithm is improved, and tested by simulation. The simulation results show that with the improvement of calculation method on average size for one hop and the introduction of the centroid algorithm,a more accurate nodes localization is achieved.
Finally, the work of the thesis are summarized, and future work is prospected.
传感器节点的定位技术是无线传感器网络的关键技术之一,对传感器网络应用的有效性起着重要作用。目前国内外已经研究出许多种节点的定位算法,但各有各的特点,同时有各自适用的场合。
本文首先对目前研究较为普遍的几种定位算法进行综合分析,了解各自的特点。考虑到算法的复杂性和精确性,深入研究了一种DV-Hop (Distance Vector-Hop)定位算法。给出了算法的基本原理,并分析了该算法的不足之处。其次,为了提高定位的精度,对DV-Hop算法进行了改进,并通过仿真进行验证。仿真结果表明,平均每跳距离计算方法的改进以及质心算法的引入,实现了更精确的节点定位。
最后对论文的工作进行了总结,并对下一步的工作进行了展望。
With the rapid development of wireless communication technology,sensor technology and embedded technology,wireless sensor networks have emerged as the focus of research topics all over the world recently.
The sensor nodes localization technology is one of the key technologies of wireless sensor networks,and plays an important role in the application's effectiveness.Recently,there are many kinds of nodes localization algorithms which have been studied all over the world already,but each has its own characteristics, simultaneously has its own suitable situation.
This thesis firstly makes a comprehensive analysis of several common localization algorithms recently,and undstands each characteristics of their own. Considering the complexity and accuracy of the algorithm, a DV-Hop(Distance Vector-Hop) localization algorithm is studied in detail. The basic principle of algorithm is given, and the shortcomings of the algorithm is also analyzed.Secondly, in order to improve the localization accuracy,the DV-Hop algorithm is improved, and tested by simulation. The simulation results show that with the improvement of calculation method on average size for one hop and the introduction of the centroid algorithm,a more accurate nodes localization is achieved.
Finally, the work of the thesis are summarized, and future work is prospected.
引文
[1]Edgar H. Callaway, Jr. Wireless Sensor Networks-Architectures and Protlcols[M].2004. CRC Press.
[2]Holger Karl, Andreas Willig. PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS[M].2005. John Wiley&Sons, Ltd.
[3]张品,徐智福,孙岩.一种新的机遇簇头优化的WSN路由协议[J].传感技术学报.第22卷,第7期：1013-1017.2009年7月.
[4]罗光春,李炯.基于多层极小支配集聚类的WSN路由算法研究[J].通信学报.第28卷,第8期：128-132.2007年8月.
[5]董杨,郭拯危,王青正.一种基于非均匀分簇的WSN路由协议[J].郑州轻工业学院学报(自然科学版).第24卷,第6期：70-74.2009年12月.
[6]杭海存,郭爱煌,舒文杰.基于LEACH与蚁群算法的WSN路由机制及性能分析[J].传感技术学报.第21卷,第10期：1735-1738.2008年10月.
[7]Kiran Yedavalli and Bhaskar Krishnamachari. Sequence-Based Lo-calization in Wireless Sensor Networks[J]. IEEE TRANSACTIONS ON MOBILE COMPUTING. VOL.7, NO.1. pp:1-14. JANUARY 2008.
[8]Neal Patwari, Alfred 0. Hero Ⅲ, Matt Perkins, Neiyer S. Correal and Robert J.0' Dea. Relative location estimation in wireless sensor networks [J].IEEE Trans on Sig Proc,2003,51(8):2137-2148.
[9]Wanming Chen, Tao Mei.Qinghu Meng,et al.A Localization Algorithm Based on Discrete Imprecision Range Measurement in Wireless Sensor Networks[C]. Proceedings of the 2006 IEEE International Conference on Information Acquisition. August 20-23,2006:644-648.
[10]向敏,石为人,蒋畅江,罗志勇.基于簇头预测的无线传感器网络节能算法[J].计算机工程.第34卷,第18期：27-29.2008年9月.
[11]胡鹏,洪佩琳,李津生,覃振权.一种结合路由转发与拓扑管理的节能算法[J].中国科学技术大学学报.第36卷,第11期：1202-1207.2006年11月.
[12]Nagamachi M. Kansei Engineering. A New Ergonomic Consumer-oriented Technology for Product Development[J]. Internationa Journal of Industrial Ergonomics,1995,15(1):3-11.
[13]Perrig A, Szewczyk R, Wen V, et al. SPINS:security protocolsfor sensor networks[C]. Seventh Annual ACM International Conference on Mobile Computing and Networks(Mobicom2001). July.2001:189-199.
[14]Das M L, Saxena A, Gulati V P. A dynamic ID-based remote user authentication scheme[J]. IEEE Transactions on Consumer Elec-tronics,2004,50(2):629-631
[15]徐春青,张曦煌.基于WSN安全的用户认证协议[J].计算机工程与设计.第28卷,第23期：5640-5642(5808).2007年12月.
[16]http://www.xbow.com.cn/wsn/homepage/default.html
[17]孙利民,李建中等.无线传感器网络[M].2005.清华大学出版社.
[18]Paramvir Bahl and Venkata N. Padmamabhan. RADAR:An In-Building RF-based User Location and Tracking System[C]. Proc. IEEE INFOCOM 2000,Vol.2, pp:775-784
[19]吉长东,乔仰文.“GPS定位原理与应用”课程建设与教学改革[J].GEOMATICS&SPATIAL INFORMATION TECHNOLOGY[J]. Vol 32, No.6:222-224. Dec,2009
[20]Hing Cheung SO and Shun Ping HUI, Nonmembers. Constrained Location Algorithm Using TDOA Measurements[J]. IEICE TRANS. FUNDAMENTALS, VOL. E86-A,N0.12:3291-3293 DECEMBER 2003
[21]D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AoA. In proceedings of IEEE INFOCOM 2003, pages 1734-1743, April 2003.
[22]WANG Lei, GAO Jun, WANG Xiaojia, Johannes Eckstein, Peter Ott. Fundamental Uncertainty Rotationally Symmetric and Anamorphic Laser Triangulation[J]. CHINESE OF JOURNAL ELECTRONICS.Vol.17, No.1: 8-11.2008.
[23]陈维克,李文锋,首珩,袁兵.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报(交通科学与工程版).第30卷,第2期： 265-268.2006年4月.
[24]Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, Tarek Abdelzaher. Range-Free Localization Schemess for Large Scale Sensor Networks[J].MobiCom' 03, September 14-19,2003, San Diego, Califor-nia, USA.
[25]GAO Lei, ZHENG Xiangquan,ZHANG Hong. A Node-Localization Algorithm for Wireless Sensor Network Based on Trilateration and Centroid Algorithm[J]. Journal of Chongqing Institute of Technology (Natural Science). Vol.23 No.7:138-141. Jul.2009.
[26]Jacques M. Bahi, Abdallah Makhoul, Ahmed Mostefaoui.A Mobile Beacon Based Approach for Sensor Network Localization[C]. Third IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2007) pp.44. October 08-10,2007.
[27]L. Doherty. Algorithms for Position and Data Recovery in Wireless Sensor Networks. Master's Thesis. University of California Berkeley, 2000.6
[28]Yi Shang, Wheeler Rmnl, Ying Zhang fourth ACM international symposium on ACM Press.2003.6.201-212 Mark. P. J. Fromherz. Localization from mere connectivity. (Proceedings of the Mobile ad hoc networking &computing (MOBIHOC 2003), Annapolis, Maryland, USA
[29]http://cir.nus.edu.sg/research/sensor/
[30]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C]. In:Proc 6th Annual Int'1 Conf on Mobile Computing and Networks(MobiCOM 2000), Boston MA, August 2000.
[31]Priyantha N, Chakraborthy A, Balakrishnan H. The cricket location-support system[C]. In:Proc Int'1 Conf on Mobile Computing and Networking, August6-11,2000, Boston,MA,32-43
[32]高雷,郑相全,张鸿.无线传感器网络中一种基于三边测量法和质心算法 的节点定位算法[J].重庆工学院学报(自然科学版).第23卷,第7期：138-141.2009年7月.
[33]Sundaram N, Ramanathan P. Connectivity based location estimation scheme for wireless ad hoc networks [A]. Proc of the 2002 IEEE Global Telecommunications Conference[C]. Taipei;IEEE Communications Society,2002,143-147
[34]D. Niculescu and B. Nath. Ad hoc Positioning System (APS)[C]. CLOBECOM, San Antonio November 2001:2926-2931
[35]丁江鹏,陈曙.一种基于跳数比的无线传感器网络定位算法[J].传感技术学报,2009,22(12)：1823-1827.
[36]Poggi C, Mazzini G. Collinearity for Sensor Network Localization [C]//Proceedings of 2003 IEEE 58th Vehicular Technology Conference Piscataway NJ, USA:IEEE,2004:3040-3044.
[37]吴凌飞,孟庆虎,梁华为.一种基于共线度的无线传感器网络定位算法[J].传感器技术学报,2009,22(5)：722-727.
[2]Holger Karl, Andreas Willig. PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS[M].2005. John Wiley&Sons, Ltd.
[3]张品,徐智福,孙岩.一种新的机遇簇头优化的WSN路由协议[J].传感技术学报.第22卷,第7期：1013-1017.2009年7月.
[4]罗光春,李炯.基于多层极小支配集聚类的WSN路由算法研究[J].通信学报.第28卷,第8期：128-132.2007年8月.
[5]董杨,郭拯危,王青正.一种基于非均匀分簇的WSN路由协议[J].郑州轻工业学院学报(自然科学版).第24卷,第6期：70-74.2009年12月.
[6]杭海存,郭爱煌,舒文杰.基于LEACH与蚁群算法的WSN路由机制及性能分析[J].传感技术学报.第21卷,第10期：1735-1738.2008年10月.
[7]Kiran Yedavalli and Bhaskar Krishnamachari. Sequence-Based Lo-calization in Wireless Sensor Networks[J]. IEEE TRANSACTIONS ON MOBILE COMPUTING. VOL.7, NO.1. pp:1-14. JANUARY 2008.
[8]Neal Patwari, Alfred 0. Hero Ⅲ, Matt Perkins, Neiyer S. Correal and Robert J.0' Dea. Relative location estimation in wireless sensor networks [J].IEEE Trans on Sig Proc,2003,51(8):2137-2148.
[9]Wanming Chen, Tao Mei.Qinghu Meng,et al.A Localization Algorithm Based on Discrete Imprecision Range Measurement in Wireless Sensor Networks[C]. Proceedings of the 2006 IEEE International Conference on Information Acquisition. August 20-23,2006:644-648.
[10]向敏,石为人,蒋畅江,罗志勇.基于簇头预测的无线传感器网络节能算法[J].计算机工程.第34卷,第18期：27-29.2008年9月.
[11]胡鹏,洪佩琳,李津生,覃振权.一种结合路由转发与拓扑管理的节能算法[J].中国科学技术大学学报.第36卷,第11期：1202-1207.2006年11月.
[12]Nagamachi M. Kansei Engineering. A New Ergonomic Consumer-oriented Technology for Product Development[J]. Internationa Journal of Industrial Ergonomics,1995,15(1):3-11.
[13]Perrig A, Szewczyk R, Wen V, et al. SPINS:security protocolsfor sensor networks[C]. Seventh Annual ACM International Conference on Mobile Computing and Networks(Mobicom2001). July.2001:189-199.
[14]Das M L, Saxena A, Gulati V P. A dynamic ID-based remote user authentication scheme[J]. IEEE Transactions on Consumer Elec-tronics,2004,50(2):629-631
[15]徐春青,张曦煌.基于WSN安全的用户认证协议[J].计算机工程与设计.第28卷,第23期：5640-5642(5808).2007年12月.
[16]http://www.xbow.com.cn/wsn/homepage/default.html
[17]孙利民,李建中等.无线传感器网络[M].2005.清华大学出版社.
[18]Paramvir Bahl and Venkata N. Padmamabhan. RADAR:An In-Building RF-based User Location and Tracking System[C]. Proc. IEEE INFOCOM 2000,Vol.2, pp:775-784
[19]吉长东,乔仰文.“GPS定位原理与应用”课程建设与教学改革[J].GEOMATICS&SPATIAL INFORMATION TECHNOLOGY[J]. Vol 32, No.6:222-224. Dec,2009
[20]Hing Cheung SO and Shun Ping HUI, Nonmembers. Constrained Location Algorithm Using TDOA Measurements[J]. IEICE TRANS. FUNDAMENTALS, VOL. E86-A,N0.12:3291-3293 DECEMBER 2003
[21]D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AoA. In proceedings of IEEE INFOCOM 2003, pages 1734-1743, April 2003.
[22]WANG Lei, GAO Jun, WANG Xiaojia, Johannes Eckstein, Peter Ott. Fundamental Uncertainty Rotationally Symmetric and Anamorphic Laser Triangulation[J]. CHINESE OF JOURNAL ELECTRONICS.Vol.17, No.1: 8-11.2008.
[23]陈维克,李文锋,首珩,袁兵.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报(交通科学与工程版).第30卷,第2期： 265-268.2006年4月.
[24]Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, Tarek Abdelzaher. Range-Free Localization Schemess for Large Scale Sensor Networks[J].MobiCom' 03, September 14-19,2003, San Diego, Califor-nia, USA.
[25]GAO Lei, ZHENG Xiangquan,ZHANG Hong. A Node-Localization Algorithm for Wireless Sensor Network Based on Trilateration and Centroid Algorithm[J]. Journal of Chongqing Institute of Technology (Natural Science). Vol.23 No.7:138-141. Jul.2009.
[26]Jacques M. Bahi, Abdallah Makhoul, Ahmed Mostefaoui.A Mobile Beacon Based Approach for Sensor Network Localization[C]. Third IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2007) pp.44. October 08-10,2007.
[27]L. Doherty. Algorithms for Position and Data Recovery in Wireless Sensor Networks. Master's Thesis. University of California Berkeley, 2000.6
[28]Yi Shang, Wheeler Rmnl, Ying Zhang fourth ACM international symposium on ACM Press.2003.6.201-212 Mark. P. J. Fromherz. Localization from mere connectivity. (Proceedings of the Mobile ad hoc networking &computing (MOBIHOC 2003), Annapolis, Maryland, USA
[29]http://cir.nus.edu.sg/research/sensor/
[30]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C]. In:Proc 6th Annual Int'1 Conf on Mobile Computing and Networks(MobiCOM 2000), Boston MA, August 2000.
[31]Priyantha N, Chakraborthy A, Balakrishnan H. The cricket location-support system[C]. In:Proc Int'1 Conf on Mobile Computing and Networking, August6-11,2000, Boston,MA,32-43
[32]高雷,郑相全,张鸿.无线传感器网络中一种基于三边测量法和质心算法 的节点定位算法[J].重庆工学院学报(自然科学版).第23卷,第7期：138-141.2009年7月.
[33]Sundaram N, Ramanathan P. Connectivity based location estimation scheme for wireless ad hoc networks [A]. Proc of the 2002 IEEE Global Telecommunications Conference[C]. Taipei;IEEE Communications Society,2002,143-147
[34]D. Niculescu and B. Nath. Ad hoc Positioning System (APS)[C]. CLOBECOM, San Antonio November 2001:2926-2931
[35]丁江鹏,陈曙.一种基于跳数比的无线传感器网络定位算法[J].传感技术学报,2009,22(12)：1823-1827.
[36]Poggi C, Mazzini G. Collinearity for Sensor Network Localization [C]//Proceedings of 2003 IEEE 58th Vehicular Technology Conference Piscataway NJ, USA:IEEE,2004:3040-3044.
[37]吴凌飞,孟庆虎,梁华为.一种基于共线度的无线传感器网络定位算法[J].传感器技术学报,2009,22(5)：722-727.