无线传感器网络测距定位求精算法的研究
|
摘要
无线传感器网络(Wireless Sensor Network,WSN)融合了计算机、微机电、通信和传感器等多领域技术,是极有潜力的研究方向。无线传感器网络由数量众多的传感器节点构成,节点在感知信号的同时需要获取自身位置信息,从而感知的数据才具有实际意义,确定传感器节点位置的技术称为定位技术,是无线传感器网络的关键技术之一。
本文主要研究无线传感器网络基于测距的定位技术,并提出自己的求精定位算法。常用的测距技术有四种,在综合考虑传感器节点体积、功耗、成本等因素的基础上,采用RSSI(接收信号强度指示)技术作为节点间的距离测量方法,并通过实验建立起基于RSSI的测距模型。
本文提出两种新的求精定位算法,这两种定位算法都依靠测距技术,并需要对信标节点进行定位,通过估算的信标节点位置对未知节点位置进行补偿求精。第一种算法为混合定位求精算法,先采用MAX-MIN算法初次定位,距离补偿之后采用极大似然估计法进行二次定位,可以提高算法的定位精度。第二种算法为位置修正求精定位算法,在初步估算未知节点位置之后,对未知节点坐标位置进行补偿,改善算法定位精度。仿真实验与室外实验证明,这两种求精定位算法在不增加额外硬件设备的条件下,提高了无线传感器网络的定位精度。
本文最后通过仿真实验讨论了信标节点密度、通信半径和网络区域面积对定位算法的影响,这些参数在一定范围内变化,可以得出结论：信标节点密度越大、通信半径越大、网络区域面积越小,传感器节点的定位算法精度越高。
Wireless sensor networks (WSNs), which integrate technologies of computer, micro-electro-mechanism, communication and sensor, is a potential research field. The wireless sensor networks consist of a large number of sensor nodes. When the sensor nodes sense the environment around, they need to know their own position to make the sensing signal useful. To locate the sensor nodes is called localization technology, which is one of the key technologies in wireless sensor networks.
The paper researched on the localization technology ranging-based in wireless sensor networks and presented new refinement algorithm. There are four kinds of common ranging technology. After comprehensive consideration of cubage, power-consumption and cost of the sensor nodes, RSSI (Receive Signal Strength Indication) technology is used to measure distance between nodes. The distance-RSSI model is set up through experiments.
Two new refinement algorithms are presented in the paper. Both of them are based on the ranging technology and need to locate their anchor nodes. The estimated position of the anchor nodes is used to compensate and refine the position of the unknown nodes. One is called hybrid localization-refined algorithm. To locate the unknown nodes using MAX-MIN algorithm first, then to locate them the second time using Maximum Likelihood Estimation algorithm (MLE) after distance compensation. The strategy improves the localization precision. Another one is called position-corrected refinement algorithm. After locating the unknown nodes, to compensate the position is done to increase the localization precision. The simulation and outdoor experiments show that the two refinement algorithms improve the localization precision without additional equipments.
Finally, the effect of the anchor node density, the communication radius and the area of network for the localization algorithm is discussed through simulation experiments. To control these parameters in some scope, if the more the anchor node density and the communication radius are and the smaller the area of network is, then the higher the localization precision of the sensor nodes is.
本文主要研究无线传感器网络基于测距的定位技术,并提出自己的求精定位算法。常用的测距技术有四种,在综合考虑传感器节点体积、功耗、成本等因素的基础上,采用RSSI(接收信号强度指示)技术作为节点间的距离测量方法,并通过实验建立起基于RSSI的测距模型。
本文提出两种新的求精定位算法,这两种定位算法都依靠测距技术,并需要对信标节点进行定位,通过估算的信标节点位置对未知节点位置进行补偿求精。第一种算法为混合定位求精算法,先采用MAX-MIN算法初次定位,距离补偿之后采用极大似然估计法进行二次定位,可以提高算法的定位精度。第二种算法为位置修正求精定位算法,在初步估算未知节点位置之后,对未知节点坐标位置进行补偿,改善算法定位精度。仿真实验与室外实验证明,这两种求精定位算法在不增加额外硬件设备的条件下,提高了无线传感器网络的定位精度。
本文最后通过仿真实验讨论了信标节点密度、通信半径和网络区域面积对定位算法的影响,这些参数在一定范围内变化,可以得出结论：信标节点密度越大、通信半径越大、网络区域面积越小,传感器节点的定位算法精度越高。
Wireless sensor networks (WSNs), which integrate technologies of computer, micro-electro-mechanism, communication and sensor, is a potential research field. The wireless sensor networks consist of a large number of sensor nodes. When the sensor nodes sense the environment around, they need to know their own position to make the sensing signal useful. To locate the sensor nodes is called localization technology, which is one of the key technologies in wireless sensor networks.
The paper researched on the localization technology ranging-based in wireless sensor networks and presented new refinement algorithm. There are four kinds of common ranging technology. After comprehensive consideration of cubage, power-consumption and cost of the sensor nodes, RSSI (Receive Signal Strength Indication) technology is used to measure distance between nodes. The distance-RSSI model is set up through experiments.
Two new refinement algorithms are presented in the paper. Both of them are based on the ranging technology and need to locate their anchor nodes. The estimated position of the anchor nodes is used to compensate and refine the position of the unknown nodes. One is called hybrid localization-refined algorithm. To locate the unknown nodes using MAX-MIN algorithm first, then to locate them the second time using Maximum Likelihood Estimation algorithm (MLE) after distance compensation. The strategy improves the localization precision. Another one is called position-corrected refinement algorithm. After locating the unknown nodes, to compensate the position is done to increase the localization precision. The simulation and outdoor experiments show that the two refinement algorithms improve the localization precision without additional equipments.
Finally, the effect of the anchor node density, the communication radius and the area of network for the localization algorithm is discussed through simulation experiments. To control these parameters in some scope, if the more the anchor node density and the communication radius are and the smaller the area of network is, then the higher the localization precision of the sensor nodes is.
引文
[1]谭励.无线传感器网络理论与技术应用[M].北京：机械工业出版社,2011.
[2]李文锋.无线传感器网络与移动机器人控制[M].北京：科学出版社,2009.
[3]Akyildiz Ian F, Su W L, Sankarasubramaniam Y, et al. A survey on sensor networks [J], IEEE Communications Magazine,2002,40(8):102-114.
[4]朱俊.无线传感器网络定位算法的研究与实现[D]：(硕士学位论文).南京：南京理工大学,2005.
[5]杨旸.传感器网络节点定位技术研究[D]：(硕士学位论文).浙江：浙江大学计算机科学与技术学院,2006.
[6]李晓维.无线传感器网络技术[M].北京：北京理工大学出版社,2007.
[7]Oliveira H.A.B.F, Boukerche A, Nakamura E F, et al. An efficient directed localization recursion protocol for wireless sensor networks [J]. IEEE TRANSACTIONS on COMPUTERS,2009, 58(5):677-691.
[8]Stoleru R, Stankovic A J, Sang H S. On Composability of Localization Protocols for Wireless Sensor Networks [J]. IEEE Network,2008,22(4):21-25.
[9]Priyantha N B, Chakraborty A, Balakrishnan H. The Cricket Location-Support System [C]. In: Proceedings of 6th ACM International Conference on Mobile Computing and Networking(ACM MOBICOM), Boston, MA, USA. ACM Press.2000:32-43.
[10]Want R, Hopper A, Falcao V, et al. The active badge location system [J]. ACM Trans, on Information Systems,1992,10(1):91-102.
[11]Harter A, Hopper A. A distributed location system for the active office [J]. IEEE Network,1994. 8(1):62-70.
[12]Harter A, Hopper A, Steggles P, et al. The anatomy of a context-aware application [C]. In:Proc. of the 5th Annual ACM/IEEE Intel Conf. on Mobile Computing and Networking. Seattle:ACM Press,1999:59-68.
[13]Bah1 P, Padmanabhan VN. RADAR:An in-building RF-based user location and tracking system [J]. In:Proc. of the IEEE INFOCOM 2000. Tel Aviv:IEEE Computer and Communications Societies,2000,2:775-784.
[14]Hightower J, Boriello G, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength [J]. Technical Report UW CSE 2000-02-02. Seattle:Department of Computer Science and Engineering, University of Washington,2000.
115] Jeffrey Hightower. SpotON:Ad hoc Location Sensing using Radio Signal Strength [J]. Feb. 2001.
[16]Castro P, Chiu P. Kremenek T, et al. A probabilistic room location service for wireless networked environments [J]. In Ubicomp,2001:18-34.
[17]Savvides A, Han C C, Srivastava M B. Dynamic Fine-Grained Localization in Ad-Hoc Wireless Sensor Networks [C]. The International Conference on Mobile Computing and Networking (MobiCom), Italy,2001:166-179.
[18]Songhwai 0, Chen P, Manzo M, et al. Instrumenting Wireless Sensor Networks for Real-time Surveillance [C]. In:Proc. of the International Conference on Robotics and Automation (ICRA), Orlando, FL, May 2006:3128-3133.
[19]Moore D, Leonard J, Rus D, et al. Robust distributed network localization with noisy range measurements [C]. In:Proceedings of the Sensys'04, San Diego, CA,2004:50-61.
[20]ITU-T Y.1541. Network performance objectives for IP-based services [EB/OL]. http://www.itu.org,2002.
[21]Lim J G, Rao S V. Mobility-enhanced positioning in ad hoc networks [C]. In:Proceedings of IEEE Wireless Communications and Networking Conference 2003, New Orleans, USA,2003,3: 1832-1837.
[22]Chung T. H. S., Liu Z, Marcelo H. Ang Jr., et al. Multi-robot mobility enhanced hop-count based localization in ad hoc networks [J]. Robotics and Autonomous Systems,2007,55(3):244-252.
[23]Srinivasan A, Wu J. A survey on secure localization in wireless sensor networks [C]. In:B. Furht (Ed.), Wireless and Mobile Communications, CRC Press/Taylor and Francis Group, Boca Raton/London,2007.
[24]周启明.水下无线传感器网络定位算法分析与研究[J].湖南工程学院学报,2011,21(2)：4952.
[25]Stutters L, Liu H, Tillman C. Navigation technologies for autonomous underwater vehicles [J]. IEEE transactions on system man and cybernetics part C-applications and reviews.2008.38(4): 581-589.
[26]Melike E, Hussein T M, Sema O. A Survey of Architectures and Localization Techniques for Underwater Acoustic Sensor Networks [J]. IEEE Communications surveys and tutorials,2011, 13(3):487-502.
[27]Xie P, Lao L, Cui J H. VBF:Vector based Forwarding Protocol for Underwater Sensor Networks [C], In Proceedings of IFIP Networking, Lecture notes in computer science,2006, 3976:1216-1221.
[28]Zhou Z, Jun H C, Amvrossios B. Scalable Localization with Mobility Prediction for Underwater Sensor Networks [C]. INFOCOM 2008. The 27th Conference on Computer Communications. 2008:211-215.
[29]王建刚,王福豹,段渭军.加权最小二乘估计在无线传感器网络定位中的应用[J].计算机应用研究,2006,(9)：41-43.
[30]周全,朱红松,徐勇军,等.基于最小包含圆的无线传感器网络定位算法[J].通信学报,2008,29(11)：8490.
[31]包志华,周晖,邵世煌,等.基于智能估计的无线传感器网络定位算法[J].传感技术学报,2008,21([0)：17651769.
[32]万江文,吴佳灵,冯仁剑.卡尔曼滤波在无线传感器网络节点定位中的应用[J].高技术通讯,2009,19(2)：151-156.
[33]冯贤文,于宁.基于多维定标的无线传感器网络定位算法研究.仪器仪表化与计量,2007,(6)：13-16.
[34]田金鹏.无线传感器网络节点定位技术研究[D](博士学位论文).上海：上海大学,2008.
[35]王珊珊.基于RSSI的无线传感器网络定位算法研究[D](硕士学位论文).湖南长沙：国防科学技术大学,2007.
[36]王殊,阎毓杰,胡富平,等.无线传感器网络的理论与应用[M].北京：北京航空航天大学出版社,2007.
[37]雷海卫.无线传感器网络自身定位算法研究[D]：(硕士学位论文).山西太原：中北大学,2008.
[38]孙利民,李建中,陈渝,等.无线传感器网络[M].北京：清华大学出版社,2005.
[39]Romer K, Mattern F. The design space of wireless sensor networks [J]. IEEE Wireless Communications,2004,11(6):54-61.
[40]于宏毅,李鸥,张效义.无线传感器网络理论、技术与实现[M].国防工业出版社,2008.
[41]Avvides S, Park H, Srivastava MB. The bits and flops of the N-hop multilateration primitive for node localization problems [C]. In:Proc. of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications. Atlanta:ACM Press,2002:112-121.
[42]Niculescu D, Nath B. Ad hoc positioning system (APS) [C]. Conference Record/IEEE Global Telecommunications Conference,2001,5:2926-2931.
[43]Bulusu N, Heidemann J, Estrin D. GPS-less low-cost outdoor localization for very small devices [J]. IEEE Personal Communications Magazine,2000,7(5):28-34.
[44]He T, Huang C D, Brian M B, et al. Range-free localization schemes for large scale sensor networks [C]. In ACM MobiCom'03, San Diego, California, USA,2003:81-95.
[45]Chong C Y, Kumar S P. Sensor networks:Evolutions, opportunities and challenges [J]. Proceedings of the IEEE,2003,91(8):1247-1256.
[46]Huang H C, Huang Y M, Ding J W. An implementation of batten-aware wireless sensor network using ZigBee for multimedia service [C]. In:proceedings of 2006 International Conference on Consumer Electronics, Digest of Technical Papers,2006:369-370.
[47]Priyantha N B, Miu A K L, Balakrishnan H, et al. The cricket compass for context-aware mobile applications [C]. In:Proc.of the 7th Annual International Conference on Mobile Computing and Networking. Rome:ACM Press,2001:1-14.
[48]Niculescu D, Nath B. Ad hoc positioning system (APS) using AOA [C]. In:Proc.of the IEEE INFOCOM 2003. San Francisco:IEEE Computer and Communications Societies,2003: 1734-1743.
[49]Mao G Q, Fidan B, Brian D.O. A. Wireless sensor network localization techniques [J]. Computer Networks,2007,51(10):2529-2553.
[50]Rappaport T S. Wireless communications:Principles and practice [M]. New Jersey:Prentice Hall,1996.
[51]Yedavalli K, Krishnamachari B, Ravula S, et al. Ecolocation:A Sequence Based Technique for RF Localization in Wireless Sensor Networks [C].2005 Fourth International Symposium on Information Processing in Sensor Networks,2005:285-292.
[52]Fall K, Varadhan K. The ns Manual [M]. A collaboration between researchers at UC Berkeley. 2003.
[53]TI. CC2420 Preliminary Datasheet.2006.
[54]Chipcon:CC2420 802.15.4 compliant radio, http://www.chipcon.com.
[55]Dijkstra E W. A note on two problems in connexion with graphs [J]. Numerische Mathematics, 1959:269-271.
[56]刘少飞,赵清华,王华奎.基于平均跳距估计和位置修正的DV-Hop定位算法[J].传感技术学报,2009,22(8)：11541158.
[2]李文锋.无线传感器网络与移动机器人控制[M].北京：科学出版社,2009.
[3]Akyildiz Ian F, Su W L, Sankarasubramaniam Y, et al. A survey on sensor networks [J], IEEE Communications Magazine,2002,40(8):102-114.
[4]朱俊.无线传感器网络定位算法的研究与实现[D]：(硕士学位论文).南京：南京理工大学,2005.
[5]杨旸.传感器网络节点定位技术研究[D]：(硕士学位论文).浙江：浙江大学计算机科学与技术学院,2006.
[6]李晓维.无线传感器网络技术[M].北京：北京理工大学出版社,2007.
[7]Oliveira H.A.B.F, Boukerche A, Nakamura E F, et al. An efficient directed localization recursion protocol for wireless sensor networks [J]. IEEE TRANSACTIONS on COMPUTERS,2009, 58(5):677-691.
[8]Stoleru R, Stankovic A J, Sang H S. On Composability of Localization Protocols for Wireless Sensor Networks [J]. IEEE Network,2008,22(4):21-25.
[9]Priyantha N B, Chakraborty A, Balakrishnan H. The Cricket Location-Support System [C]. In: Proceedings of 6th ACM International Conference on Mobile Computing and Networking(ACM MOBICOM), Boston, MA, USA. ACM Press.2000:32-43.
[10]Want R, Hopper A, Falcao V, et al. The active badge location system [J]. ACM Trans, on Information Systems,1992,10(1):91-102.
[11]Harter A, Hopper A. A distributed location system for the active office [J]. IEEE Network,1994. 8(1):62-70.
[12]Harter A, Hopper A, Steggles P, et al. The anatomy of a context-aware application [C]. In:Proc. of the 5th Annual ACM/IEEE Intel Conf. on Mobile Computing and Networking. Seattle:ACM Press,1999:59-68.
[13]Bah1 P, Padmanabhan VN. RADAR:An in-building RF-based user location and tracking system [J]. In:Proc. of the IEEE INFOCOM 2000. Tel Aviv:IEEE Computer and Communications Societies,2000,2:775-784.
[14]Hightower J, Boriello G, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength [J]. Technical Report UW CSE 2000-02-02. Seattle:Department of Computer Science and Engineering, University of Washington,2000.
115] Jeffrey Hightower. SpotON:Ad hoc Location Sensing using Radio Signal Strength [J]. Feb. 2001.
[16]Castro P, Chiu P. Kremenek T, et al. A probabilistic room location service for wireless networked environments [J]. In Ubicomp,2001:18-34.
[17]Savvides A, Han C C, Srivastava M B. Dynamic Fine-Grained Localization in Ad-Hoc Wireless Sensor Networks [C]. The International Conference on Mobile Computing and Networking (MobiCom), Italy,2001:166-179.
[18]Songhwai 0, Chen P, Manzo M, et al. Instrumenting Wireless Sensor Networks for Real-time Surveillance [C]. In:Proc. of the International Conference on Robotics and Automation (ICRA), Orlando, FL, May 2006:3128-3133.
[19]Moore D, Leonard J, Rus D, et al. Robust distributed network localization with noisy range measurements [C]. In:Proceedings of the Sensys'04, San Diego, CA,2004:50-61.
[20]ITU-T Y.1541. Network performance objectives for IP-based services [EB/OL]. http://www.itu.org,2002.
[21]Lim J G, Rao S V. Mobility-enhanced positioning in ad hoc networks [C]. In:Proceedings of IEEE Wireless Communications and Networking Conference 2003, New Orleans, USA,2003,3: 1832-1837.
[22]Chung T. H. S., Liu Z, Marcelo H. Ang Jr., et al. Multi-robot mobility enhanced hop-count based localization in ad hoc networks [J]. Robotics and Autonomous Systems,2007,55(3):244-252.
[23]Srinivasan A, Wu J. A survey on secure localization in wireless sensor networks [C]. In:B. Furht (Ed.), Wireless and Mobile Communications, CRC Press/Taylor and Francis Group, Boca Raton/London,2007.
[24]周启明.水下无线传感器网络定位算法分析与研究[J].湖南工程学院学报,2011,21(2)：4952.
[25]Stutters L, Liu H, Tillman C. Navigation technologies for autonomous underwater vehicles [J]. IEEE transactions on system man and cybernetics part C-applications and reviews.2008.38(4): 581-589.
[26]Melike E, Hussein T M, Sema O. A Survey of Architectures and Localization Techniques for Underwater Acoustic Sensor Networks [J]. IEEE Communications surveys and tutorials,2011, 13(3):487-502.
[27]Xie P, Lao L, Cui J H. VBF:Vector based Forwarding Protocol for Underwater Sensor Networks [C], In Proceedings of IFIP Networking, Lecture notes in computer science,2006, 3976:1216-1221.
[28]Zhou Z, Jun H C, Amvrossios B. Scalable Localization with Mobility Prediction for Underwater Sensor Networks [C]. INFOCOM 2008. The 27th Conference on Computer Communications. 2008:211-215.
[29]王建刚,王福豹,段渭军.加权最小二乘估计在无线传感器网络定位中的应用[J].计算机应用研究,2006,(9)：41-43.
[30]周全,朱红松,徐勇军,等.基于最小包含圆的无线传感器网络定位算法[J].通信学报,2008,29(11)：8490.
[31]包志华,周晖,邵世煌,等.基于智能估计的无线传感器网络定位算法[J].传感技术学报,2008,21([0)：17651769.
[32]万江文,吴佳灵,冯仁剑.卡尔曼滤波在无线传感器网络节点定位中的应用[J].高技术通讯,2009,19(2)：151-156.
[33]冯贤文,于宁.基于多维定标的无线传感器网络定位算法研究.仪器仪表化与计量,2007,(6)：13-16.
[34]田金鹏.无线传感器网络节点定位技术研究[D](博士学位论文).上海：上海大学,2008.
[35]王珊珊.基于RSSI的无线传感器网络定位算法研究[D](硕士学位论文).湖南长沙：国防科学技术大学,2007.
[36]王殊,阎毓杰,胡富平,等.无线传感器网络的理论与应用[M].北京：北京航空航天大学出版社,2007.
[37]雷海卫.无线传感器网络自身定位算法研究[D]：(硕士学位论文).山西太原：中北大学,2008.
[38]孙利民,李建中,陈渝,等.无线传感器网络[M].北京：清华大学出版社,2005.
[39]Romer K, Mattern F. The design space of wireless sensor networks [J]. IEEE Wireless Communications,2004,11(6):54-61.
[40]于宏毅,李鸥,张效义.无线传感器网络理论、技术与实现[M].国防工业出版社,2008.
[41]Avvides S, Park H, Srivastava MB. The bits and flops of the N-hop multilateration primitive for node localization problems [C]. In:Proc. of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications. Atlanta:ACM Press,2002:112-121.
[42]Niculescu D, Nath B. Ad hoc positioning system (APS) [C]. Conference Record/IEEE Global Telecommunications Conference,2001,5:2926-2931.
[43]Bulusu N, Heidemann J, Estrin D. GPS-less low-cost outdoor localization for very small devices [J]. IEEE Personal Communications Magazine,2000,7(5):28-34.
[44]He T, Huang C D, Brian M B, et al. Range-free localization schemes for large scale sensor networks [C]. In ACM MobiCom'03, San Diego, California, USA,2003:81-95.
[45]Chong C Y, Kumar S P. Sensor networks:Evolutions, opportunities and challenges [J]. Proceedings of the IEEE,2003,91(8):1247-1256.
[46]Huang H C, Huang Y M, Ding J W. An implementation of batten-aware wireless sensor network using ZigBee for multimedia service [C]. In:proceedings of 2006 International Conference on Consumer Electronics, Digest of Technical Papers,2006:369-370.
[47]Priyantha N B, Miu A K L, Balakrishnan H, et al. The cricket compass for context-aware mobile applications [C]. In:Proc.of the 7th Annual International Conference on Mobile Computing and Networking. Rome:ACM Press,2001:1-14.
[48]Niculescu D, Nath B. Ad hoc positioning system (APS) using AOA [C]. In:Proc.of the IEEE INFOCOM 2003. San Francisco:IEEE Computer and Communications Societies,2003: 1734-1743.
[49]Mao G Q, Fidan B, Brian D.O. A. Wireless sensor network localization techniques [J]. Computer Networks,2007,51(10):2529-2553.
[50]Rappaport T S. Wireless communications:Principles and practice [M]. New Jersey:Prentice Hall,1996.
[51]Yedavalli K, Krishnamachari B, Ravula S, et al. Ecolocation:A Sequence Based Technique for RF Localization in Wireless Sensor Networks [C].2005 Fourth International Symposium on Information Processing in Sensor Networks,2005:285-292.
[52]Fall K, Varadhan K. The ns Manual [M]. A collaboration between researchers at UC Berkeley. 2003.
[53]TI. CC2420 Preliminary Datasheet.2006.
[54]Chipcon:CC2420 802.15.4 compliant radio, http://www.chipcon.com.
[55]Dijkstra E W. A note on two problems in connexion with graphs [J]. Numerische Mathematics, 1959:269-271.
[56]刘少飞,赵清华,王华奎.基于平均跳距估计和位置修正的DV-Hop定位算法[J].传感技术学报,2009,22(8)：11541158.