无线传感器网络节点的三维定位算法研究
|
摘要
在无线传感器网络应用中,为了关联监测事件和其发生位置,需要进行节点定位。现有无线传感器网络节点定位算法大都假设所有节点在一个二维平面上,基本思路是利用距离、角度等关系建立多个方程组或一个大型方程组,求解得到节点位置坐标,这样的算法我们称为二维定位算法。在实际应用中,无线传感器网络节点应在一个三维空间中,节点的定位是在三维空间中定位,也就是说我们应该研究三维定位算法。在三维定位算法中,由于每一个节点增加了一个未知数且测量值精度受各种因素的影响,导致方程组解的唯一性和稳定性受到影响,因此目前少见使用的三维定位算法。本文的主要思想是通过引入已知的地形信息作为约束,改善三维定位算法的准确性,由于电子地形图已相当普及,所以此思路有其实际意义。
我们首先根据特点不同将定位过程分为两个阶段:一、网络初始化后的全局定位阶段,这一阶段已知少量锚节点信息,需对大量未知节点进行初始定位;二、在网络稳定后节点的移动重定位阶段,这一阶段中已知大部分参考节点信息,仅需对个别移动节点进行重定位。
1、在初始的全局定位阶段,本文改进了基于锚节点推广的无线传感器网络节点定位算法。首先设计了三维定位满足的几何关系,提出新的节点误差判断标准和参考节点选择标准。本文在方程组求解过程中引入地形信息进行优化,并提出了两种算法改进策略减少定位误差。此方法的优点是仅需要少量的锚节点就能达到节点的全局定位。
2、在节点移动重定位阶段,本文推广了APIT算法并设计相关协议完成定位。首先设计了利用APIT进行三维移动重定位协议,此协议规定了具体的节点行为、记录表项设计等,并为后续计算收集必要信息。然后对APIT算法进行三维推广。在具体的节点定位时,采用了结合地形信息的最优化方法,兼顾定位效率及准确率。这一方法的优点是定位简单,能较快完成定位。
文中提出的算法均在Windows平台下利用Matlab进行了仿真,从仿真结果可以看出,在两种定位情况下,所提出的无线传感器网络三维定位方法都取得了令人满意的结果,验证了算法的有效性。本文所提出的算法因为更有针对性,从而在地形复杂或者大范围节点定位情况下能够较好适用。
With the development of sensor technology, detection technology, and the wireless network technologies, Wireless Sensor Network technology is playing an increasingly important role in scientific researches. The positioning algorithms of WSN are needed in order to connect the detection information of sensors to the real locations. The current positioning algorithms of wireless sensor network are mostly under the two-dimensional assumption, and they can perform well in small regions or flat areas. When under the three-dimensional assumptions, errors introduced by many factors such as communication barriers and higher dimensions will reduce the accuracy of positioning algorithms. Therefore, it is a very practical and significant project to promote the mature two-dimensional positioning algorithms to three-dimensional fields.
According to the different targets of positioning, this issue of wireless sensor network can be divided into two stages. The first stage is to identify the entire network after the initial layout of sensors. The latter stage is to locate individual node after the entire network has been identified. According to the different objectives of two phases, this paper uses two customized WSN (Wireless Sensor Network) three-dimensional location methods for the two conditions.
In the initial phase of the global positioning, we improved a two-dimensional algorithm based on anchor promotions. The advantage of the method is that it only requires a small amount of anchors to locate all unknown nodes in the network. Its drawback is when the anchor nodes are too rare and their distribution is relatively concentrated, the errors will increases rapidly away from the region of anchors. In extended to three-dimensional process, this paper finds the geometric relationship between nodes firstly and introduces new reference node selection criterion and new targets of optimization. As the electronic map information has been very popular at the present, so this paper introduces the map information in the optimal design to reduce the positioning errors. In addition, we propose two improved strategies to find the right location: dynamic optimization of threshold and improved anchor node selection strategy.
If some individual nodes need to move after the completion of global positioning, it is necessary to design new strategy to relocate them. This paper promotes the APIT algorithm to complete the positioning under this case. The advantage of this approach is that it is fast and simple. This paper designs a protocol using the three-dimensional positioning APIT algorithm firstly, and this protocol specifies the actions of nodes and the information collected for the computing stage. Then we introduce the three-dimensional extension of APIT algorithm. First extend the geometric relationship between the regions and nodes to three-dimensional, and then introduces the map information to its optimization stages to make the method both efficiency and accuracy.
Both methods above are simulated by Matlab in windows platform. The simulating results show that both algorithm and protocol can provide considerable location performance under different conditions. The proposed algorithm is more close to the actual situation because of the three-dimensional assumption, which can be applied in complex terrain or under a wide range of Wireless Sensor Networks.
我们首先根据特点不同将定位过程分为两个阶段:一、网络初始化后的全局定位阶段,这一阶段已知少量锚节点信息,需对大量未知节点进行初始定位;二、在网络稳定后节点的移动重定位阶段,这一阶段中已知大部分参考节点信息,仅需对个别移动节点进行重定位。
1、在初始的全局定位阶段,本文改进了基于锚节点推广的无线传感器网络节点定位算法。首先设计了三维定位满足的几何关系,提出新的节点误差判断标准和参考节点选择标准。本文在方程组求解过程中引入地形信息进行优化,并提出了两种算法改进策略减少定位误差。此方法的优点是仅需要少量的锚节点就能达到节点的全局定位。
2、在节点移动重定位阶段,本文推广了APIT算法并设计相关协议完成定位。首先设计了利用APIT进行三维移动重定位协议,此协议规定了具体的节点行为、记录表项设计等,并为后续计算收集必要信息。然后对APIT算法进行三维推广。在具体的节点定位时,采用了结合地形信息的最优化方法,兼顾定位效率及准确率。这一方法的优点是定位简单,能较快完成定位。
文中提出的算法均在Windows平台下利用Matlab进行了仿真,从仿真结果可以看出,在两种定位情况下,所提出的无线传感器网络三维定位方法都取得了令人满意的结果,验证了算法的有效性。本文所提出的算法因为更有针对性,从而在地形复杂或者大范围节点定位情况下能够较好适用。
With the development of sensor technology, detection technology, and the wireless network technologies, Wireless Sensor Network technology is playing an increasingly important role in scientific researches. The positioning algorithms of WSN are needed in order to connect the detection information of sensors to the real locations. The current positioning algorithms of wireless sensor network are mostly under the two-dimensional assumption, and they can perform well in small regions or flat areas. When under the three-dimensional assumptions, errors introduced by many factors such as communication barriers and higher dimensions will reduce the accuracy of positioning algorithms. Therefore, it is a very practical and significant project to promote the mature two-dimensional positioning algorithms to three-dimensional fields.
According to the different targets of positioning, this issue of wireless sensor network can be divided into two stages. The first stage is to identify the entire network after the initial layout of sensors. The latter stage is to locate individual node after the entire network has been identified. According to the different objectives of two phases, this paper uses two customized WSN (Wireless Sensor Network) three-dimensional location methods for the two conditions.
In the initial phase of the global positioning, we improved a two-dimensional algorithm based on anchor promotions. The advantage of the method is that it only requires a small amount of anchors to locate all unknown nodes in the network. Its drawback is when the anchor nodes are too rare and their distribution is relatively concentrated, the errors will increases rapidly away from the region of anchors. In extended to three-dimensional process, this paper finds the geometric relationship between nodes firstly and introduces new reference node selection criterion and new targets of optimization. As the electronic map information has been very popular at the present, so this paper introduces the map information in the optimal design to reduce the positioning errors. In addition, we propose two improved strategies to find the right location: dynamic optimization of threshold and improved anchor node selection strategy.
If some individual nodes need to move after the completion of global positioning, it is necessary to design new strategy to relocate them. This paper promotes the APIT algorithm to complete the positioning under this case. The advantage of this approach is that it is fast and simple. This paper designs a protocol using the three-dimensional positioning APIT algorithm firstly, and this protocol specifies the actions of nodes and the information collected for the computing stage. Then we introduce the three-dimensional extension of APIT algorithm. First extend the geometric relationship between the regions and nodes to three-dimensional, and then introduces the map information to its optimization stages to make the method both efficiency and accuracy.
Both methods above are simulated by Matlab in windows platform. The simulating results show that both algorithm and protocol can provide considerable location performance under different conditions. The proposed algorithm is more close to the actual situation because of the three-dimensional assumption, which can be applied in complex terrain or under a wide range of Wireless Sensor Networks.
引文
[1]崔莉,鞠海玲等.无线传感器网络研究进展.计算机研究与发展,2005,42(1),p163~174
[2] D. Cullar, D. Estrin, M. Strvastava. Overview of sensor network. Computer, 2004, 37(8):p 41~49
[3] Warneke B, Last M, Liebowitz B, Pister KSJ. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer Magazine, 2001, 34(1): 44-51
[4]石为人,张杰,唐云建,黄超.无线传感器网络嵌入式网关的设计与实现.计算机应用,2006,Vol. 26,No. 11, p2524~2535
[5]徐增友. WSN无线传感网络定位技术的研究,山东大学硕士学位论文,2009
[6] L. Cui,F. Wang,H. Luo, et al. A pervasive sensor node architecture. The IFIP NPC’04 Workshop on Building Intelligent Sensor Networks(BISON,04), Wuhan,2004
[7] Cui L,Ju HL,Miao Y,Li TP,LiuW, Zhao Z. Overview of wireless sensor networks. Journal of Computer Research and Development,2005,42(l): 163-174
[8]高学彬,张志强,叶世伟,吴健康.无线传感器网络中的被动式红外传感器模型研究.计算机应用, 2007, vol.27, No.5, p1086~1108
[9] Randolph L. Moses, Dushyanth Krishnamurthy, and Robert Patterson. A Self-Localization Method for Wireless Sensor Networks. EURASIP Journal on Applied Signal Processing, Volume 2003, Issue 4, pp. 348-358, March 15, 2003.
[10] Wei Wang, Vikram Srinivasan, Bang Wang, KeeChaing Chua. Coverage for Target Localization in Wireless Sensor Networks
[11] Yi Shang, Wheeler Ruml, Ying Zhang. Localization from Mere Connectivity. MobiHoc’03, June 1–3, 2003, Annapolis, Maryland, USA
[12] Masoomeh Rudafshani and Suprakash Datta. Localization in Wireless Sensor Networks. IPSN’07, April 25-27, 2007, Cambridge, Massachusetts, USA.
[13] Yawen Wei, Zhen Yu, Yong Guan. Location Verification Algorithms for Wireless Sensor Networks. 27th International Conference on Distributed Computing Systems (ICDCS'07)
[14] Loukas Lazos and RadhaPoovendran. SeRLoc: Robust Localization for Wireless Sensor Networks. ACM Transactions on Sensor Networks, Vol. 1, No. 1, August 2005, Pages 73–100.付军,戴志诚,汪秉文.无线传感器网络与传统Ad Hoc网络的比较研究,信息技术,2007,Vol. 11, p25~28
[15] C Savarese, J Rabaey, K Langendoen. Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks. USENIX Annual Technical Conference, 2002
[16]程大伟,赵海,孙佩刚,张希元,朱剑,丁玉官,陆育惠,王进雷.能量高效的无线传感器网络传输可靠性研究.计算机应用, 2008, Vol. 1, p25~28
[17]吴光斌,梁长垠.无线传感器网络能量有效性的研究.传感器技术,2004,Vol. 23,第七期,p74~76, p80
[18]匡林爱,蔡自兴.一种无线传感器网络的节点自定位方法.计算机应用, 2008, Vol. 28,第二期,p382~384
[19] Radu Stoleru, John A. Stankovic, Sang Son. Robust Node Localization for Wireless Sensor Networks. EmNets'07, June 25-26, 2007, Cork, Ireland
[20] A Perrig, J Stankovic, D Wagner. Security in wireless sensor networks. Communications of the ACM, 2004
[21] Adrian Perrig1, Robert Szewczyk1, J.D. Tygar1, Victor Wen1 and David E. Culler1. SPINS: Security Protocols for Sensor Networks. Wireless Networks, 2002, Volume 8, No.5, p521~534
[22] Ya. R. Faizulkhakov. Time synchronization methods for wireless sensor networks : -SUBTITLE- A survey. Programming and Computing Software,2007,Vol. 33,No.4,p214~226
[23] Azzedine Boukerche, Horacio A. B. F. Oliveira, Eduardo F. Nakamura, Antonio A. F. Loureiro, Secure Localization Algorithms for Wireless Sensor Networks. IEEE Communications Magazine, April 2008
[24] Cesare Alippi,Giovanni Vanini.Wireless Sensor Networks and Radio Localization:a Metorlogical Analysis of the MICA2 received signal strength indicator[C].29th Annual IEEE Intemationfl Conference on Local Computer Networks(LCN’04),Tampa,Florida,USA:November 2004:p579~582.
[25] Caffery J . A new approach to the geometry of TOA location[C] Stuart Lipoff . IEEE Vehicular Technology Conference (VTC) .Boston : IEEE Press , 2000 :194321949.
[26] J.M.Delosme,M.Morf,and B.Friedlander.A Linear Equmion Approach to Locating Sources from Time-Difference-of-Arrival Measurements[C].Proc.IEEE Int.Conf. Acoust,Speech,and Signal Processing, 1980.
[27] D.Niculescu and B.Nath.Ad hoc Positioning System(APS)Using AOA[C].INFOCOM,San Francisco,CA:April 2003:p1734~1743.
[28]陈维克,李文锋,首珩,袁兵.基于RSSI的无线传感器网络加权质心定位算法.武汉理工大学学报:交通科学与工程版. 2006, Vol.30, No. 2, p265~268
[29] T He, C Huang, BM Blum, JA Stankovic, T Abdelzaher. Range-free localization schemes for large scale sensor networks. International Conference on Mobile Computing and Networking, Proceedings of the 9th annual international conference, 2003, San Diego, USA
[30] D.Niculescu and B.Nath.Ad hoc Positioning System(APS)[C].GLOBECOM,San Antonio:November 2001:p2926~2931.
[31]王秉旻,石晓军.无线传感器网络基于测距定位算法的实现.科技资讯, 2006, Vol. 2, p143~144
[32]史龙,王福豹,段渭军,任丰厚.无线传感器网络Range-Free自身定位机制与算法.计算机工程与应用,2004,Vol. 40, No.23, p127~130, p150
[33] Hightower J , Want R , Borriello G. SpotON : an indoor 3D location sensing technology based on RF signal strength [EBPOL ] . 2000 [ 2005212212 ] .
[34]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报,2004,Vol. 25,No.4,p114~124
[35] Z.~Chaczko, R.~Klempous, J.~Nikodem, et. al,“Methods of Sensors Localization in Wireless Sensor Networks”, Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS'07), 2007
[36]赵军,裴庆祺,徐展琦.无线传感器网络近似三角形内点测试定位算法.计算机工程,2007,Vol.33, No. 5, p109~111
[37]吕良彬,曹阳,高洵,罗卉.基于球壳交集的传感器网络三维定位算法.北京邮电大学学报,2006,Vol. 29 Sup. p48~51
[2] D. Cullar, D. Estrin, M. Strvastava. Overview of sensor network. Computer, 2004, 37(8):p 41~49
[3] Warneke B, Last M, Liebowitz B, Pister KSJ. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer Magazine, 2001, 34(1): 44-51
[4]石为人,张杰,唐云建,黄超.无线传感器网络嵌入式网关的设计与实现.计算机应用,2006,Vol. 26,No. 11, p2524~2535
[5]徐增友. WSN无线传感网络定位技术的研究,山东大学硕士学位论文,2009
[6] L. Cui,F. Wang,H. Luo, et al. A pervasive sensor node architecture. The IFIP NPC’04 Workshop on Building Intelligent Sensor Networks(BISON,04), Wuhan,2004
[7] Cui L,Ju HL,Miao Y,Li TP,LiuW, Zhao Z. Overview of wireless sensor networks. Journal of Computer Research and Development,2005,42(l): 163-174
[8]高学彬,张志强,叶世伟,吴健康.无线传感器网络中的被动式红外传感器模型研究.计算机应用, 2007, vol.27, No.5, p1086~1108
[9] Randolph L. Moses, Dushyanth Krishnamurthy, and Robert Patterson. A Self-Localization Method for Wireless Sensor Networks. EURASIP Journal on Applied Signal Processing, Volume 2003, Issue 4, pp. 348-358, March 15, 2003.
[10] Wei Wang, Vikram Srinivasan, Bang Wang, KeeChaing Chua. Coverage for Target Localization in Wireless Sensor Networks
[11] Yi Shang, Wheeler Ruml, Ying Zhang. Localization from Mere Connectivity. MobiHoc’03, June 1–3, 2003, Annapolis, Maryland, USA
[12] Masoomeh Rudafshani and Suprakash Datta. Localization in Wireless Sensor Networks. IPSN’07, April 25-27, 2007, Cambridge, Massachusetts, USA.
[13] Yawen Wei, Zhen Yu, Yong Guan. Location Verification Algorithms for Wireless Sensor Networks. 27th International Conference on Distributed Computing Systems (ICDCS'07)
[14] Loukas Lazos and RadhaPoovendran. SeRLoc: Robust Localization for Wireless Sensor Networks. ACM Transactions on Sensor Networks, Vol. 1, No. 1, August 2005, Pages 73–100.付军,戴志诚,汪秉文.无线传感器网络与传统Ad Hoc网络的比较研究,信息技术,2007,Vol. 11, p25~28
[15] C Savarese, J Rabaey, K Langendoen. Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks. USENIX Annual Technical Conference, 2002
[16]程大伟,赵海,孙佩刚,张希元,朱剑,丁玉官,陆育惠,王进雷.能量高效的无线传感器网络传输可靠性研究.计算机应用, 2008, Vol. 1, p25~28
[17]吴光斌,梁长垠.无线传感器网络能量有效性的研究.传感器技术,2004,Vol. 23,第七期,p74~76, p80
[18]匡林爱,蔡自兴.一种无线传感器网络的节点自定位方法.计算机应用, 2008, Vol. 28,第二期,p382~384
[19] Radu Stoleru, John A. Stankovic, Sang Son. Robust Node Localization for Wireless Sensor Networks. EmNets'07, June 25-26, 2007, Cork, Ireland
[20] A Perrig, J Stankovic, D Wagner. Security in wireless sensor networks. Communications of the ACM, 2004
[21] Adrian Perrig1, Robert Szewczyk1, J.D. Tygar1, Victor Wen1 and David E. Culler1. SPINS: Security Protocols for Sensor Networks. Wireless Networks, 2002, Volume 8, No.5, p521~534
[22] Ya. R. Faizulkhakov. Time synchronization methods for wireless sensor networks : -SUBTITLE- A survey. Programming and Computing Software,2007,Vol. 33,No.4,p214~226
[23] Azzedine Boukerche, Horacio A. B. F. Oliveira, Eduardo F. Nakamura, Antonio A. F. Loureiro, Secure Localization Algorithms for Wireless Sensor Networks. IEEE Communications Magazine, April 2008
[24] Cesare Alippi,Giovanni Vanini.Wireless Sensor Networks and Radio Localization:a Metorlogical Analysis of the MICA2 received signal strength indicator[C].29th Annual IEEE Intemationfl Conference on Local Computer Networks(LCN’04),Tampa,Florida,USA:November 2004:p579~582.
[25] Caffery J . A new approach to the geometry of TOA location[C] Stuart Lipoff . IEEE Vehicular Technology Conference (VTC) .Boston : IEEE Press , 2000 :194321949.
[26] J.M.Delosme,M.Morf,and B.Friedlander.A Linear Equmion Approach to Locating Sources from Time-Difference-of-Arrival Measurements[C].Proc.IEEE Int.Conf. Acoust,Speech,and Signal Processing, 1980.
[27] D.Niculescu and B.Nath.Ad hoc Positioning System(APS)Using AOA[C].INFOCOM,San Francisco,CA:April 2003:p1734~1743.
[28]陈维克,李文锋,首珩,袁兵.基于RSSI的无线传感器网络加权质心定位算法.武汉理工大学学报:交通科学与工程版. 2006, Vol.30, No. 2, p265~268
[29] T He, C Huang, BM Blum, JA Stankovic, T Abdelzaher. Range-free localization schemes for large scale sensor networks. International Conference on Mobile Computing and Networking, Proceedings of the 9th annual international conference, 2003, San Diego, USA
[30] D.Niculescu and B.Nath.Ad hoc Positioning System(APS)[C].GLOBECOM,San Antonio:November 2001:p2926~2931.
[31]王秉旻,石晓军.无线传感器网络基于测距定位算法的实现.科技资讯, 2006, Vol. 2, p143~144
[32]史龙,王福豹,段渭军,任丰厚.无线传感器网络Range-Free自身定位机制与算法.计算机工程与应用,2004,Vol. 40, No.23, p127~130, p150
[33] Hightower J , Want R , Borriello G. SpotON : an indoor 3D location sensing technology based on RF signal strength [EBPOL ] . 2000 [ 2005212212 ] .
[34]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报,2004,Vol. 25,No.4,p114~124
[35] Z.~Chaczko, R.~Klempous, J.~Nikodem, et. al,“Methods of Sensors Localization in Wireless Sensor Networks”, Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS'07), 2007
[36]赵军,裴庆祺,徐展琦.无线传感器网络近似三角形内点测试定位算法.计算机工程,2007,Vol.33, No. 5, p109~111
[37]吕良彬,曹阳,高洵,罗卉.基于球壳交集的传感器网络三维定位算法.北京邮电大学学报,2006,Vol. 29 Sup. p48~51