无线传感器网络定位算法研究及改进
|
摘要
随着无线传感器网络（Wireless Sensor Network，WSN）技术的发展，从工业生产、军事应用、环境监测到人们的日常生活，都能日益见到它的应用。作为无线传感器网络技术的一个分支，无线传感器网络定位已成为了一个研究热点，受到了越来越多的关注。对于无线传感器网络，传感器节点是网络的组成部分，而在许多情况下，需要知道传感器节点的位置，尤其是应用到医疗护理、环境监测、矿井人员定位等领域的无线传感器网络，更加需要节点的准确信息，这便给无线传感器网络定位的研究带来了现实上的意义。
如今，各种定位系统和定位算法层出不穷。对于国内外关于无线传感器网络定位的研究现状，本文进行了大量研究，针对基于测距的经典三边定位算法和基于非测距的经典DV-Hop定位算法定位精度不高的缺点，分别提出了改进的三边定位算法和改进的DV-Hop定位算法。本文的主要研究内容如下：
1.改进的三边定位算法。因为当参考节点呈正三角形摆放时，具有最高的定位精度，基于这一理论，本文提出了改进的加权三边定位算法。通过分析参考节点的位置与参考节点所围成的三角形的形状之间的关系，本文将参考节点系数矩阵的条件数作为加权因子，引入到三边定位算法中，以此来反应参考节点所围成的三角形与正三角形之间的差异。通过MATALAB仿真验证，由不同参考节点组合得到的不同的三边定位结果，加权因子的引入修正了整体误差，提高了定位精度。
2.改进的DV-Hop定位算法。DV-Hop是基于非测距的定位算法，依赖网络的连通度进行定位，存在定位精度差的缺点。本文分析了网络拓扑与定位精度之间的关系，为提高定位精度，对未知节点与参考节点之间的跳数进行修正，以使未知节点与参考节点之间的距离误差更小，与真实值更为接近。通过仿真显示，该改进算法提高了定位精度。
As the development of Wireless Sensor Network technology, from industrial production, militaryapplication, environmental monitoring to people’s daily life, it’s application is increasingly becomingprofound. As a branch of WSN technology, WSN localization technology has become a research hotspot,drawing much more people’s attention day by day. As for WSN, the network is made up of sensor nodes.And, in many situations, the location of sensor nodes needs to be known, especially in the fields such asmedical care, environmental monitoring, miner localization and so on where the nodes information is muchmore important. Then, this brings a practical meaning to the research of WSN localization.
Nowadays, all kinds of localization systems and algorithms are emerging continually. This paperanalyzed the present research situation of WSN localization home and abroad. In the light of drawback oflow localization precision faced by the range-based Three–Laterations localization algorithm and DV-Hoplocalization algorithm, this paper put forward improved algorithms respectively.
1） Improved Three-Laterations localization algorithm. On the basis of the theory that theequilateral triangle conformation of refer nodes will result in the largest localization precision,this paper put forward weighted Three-Laterations localization algorithm. Through analysis ofthe relation between refer nodes location and the shape of the triangle surrounded by refernodes, this paper brought the coefficient matrix of the refer nodes to Three-Laterationslocalization algorithm as weight factor to reflect the difference of the triangle surrounded byrefer nodes and equilateral triangle. Through MATLAB simulation verification, in the situationof different refer nodes group, the introduction of weight factor corrected the whole error of the different Three-Laterations results and increased localization precision.
2） Improved DV-Hop localization algorithm. As a range-free localization algorithm., DV-Hoprelies on network connectivity for localization and is low in localization precision. On the basisof the analysis of the relation between network topology and localization precision, in order toenhance localization precision, this paper modified the number of the hops between theunknown node and the refer node to get the distance between the unknown node and the refernode much closer to the real value. MATLAB simulation showed that the improved algorithmimproved localization precision.
如今，各种定位系统和定位算法层出不穷。对于国内外关于无线传感器网络定位的研究现状，本文进行了大量研究，针对基于测距的经典三边定位算法和基于非测距的经典DV-Hop定位算法定位精度不高的缺点，分别提出了改进的三边定位算法和改进的DV-Hop定位算法。本文的主要研究内容如下：
1.改进的三边定位算法。因为当参考节点呈正三角形摆放时，具有最高的定位精度，基于这一理论，本文提出了改进的加权三边定位算法。通过分析参考节点的位置与参考节点所围成的三角形的形状之间的关系，本文将参考节点系数矩阵的条件数作为加权因子，引入到三边定位算法中，以此来反应参考节点所围成的三角形与正三角形之间的差异。通过MATALAB仿真验证，由不同参考节点组合得到的不同的三边定位结果，加权因子的引入修正了整体误差，提高了定位精度。
2.改进的DV-Hop定位算法。DV-Hop是基于非测距的定位算法，依赖网络的连通度进行定位，存在定位精度差的缺点。本文分析了网络拓扑与定位精度之间的关系，为提高定位精度，对未知节点与参考节点之间的跳数进行修正，以使未知节点与参考节点之间的距离误差更小，与真实值更为接近。通过仿真显示，该改进算法提高了定位精度。
As the development of Wireless Sensor Network technology, from industrial production, militaryapplication, environmental monitoring to people’s daily life, it’s application is increasingly becomingprofound. As a branch of WSN technology, WSN localization technology has become a research hotspot,drawing much more people’s attention day by day. As for WSN, the network is made up of sensor nodes.And, in many situations, the location of sensor nodes needs to be known, especially in the fields such asmedical care, environmental monitoring, miner localization and so on where the nodes information is muchmore important. Then, this brings a practical meaning to the research of WSN localization.
Nowadays, all kinds of localization systems and algorithms are emerging continually. This paperanalyzed the present research situation of WSN localization home and abroad. In the light of drawback oflow localization precision faced by the range-based Three–Laterations localization algorithm and DV-Hoplocalization algorithm, this paper put forward improved algorithms respectively.
1） Improved Three-Laterations localization algorithm. On the basis of the theory that theequilateral triangle conformation of refer nodes will result in the largest localization precision,this paper put forward weighted Three-Laterations localization algorithm. Through analysis ofthe relation between refer nodes location and the shape of the triangle surrounded by refernodes, this paper brought the coefficient matrix of the refer nodes to Three-Laterationslocalization algorithm as weight factor to reflect the difference of the triangle surrounded byrefer nodes and equilateral triangle. Through MATLAB simulation verification, in the situationof different refer nodes group, the introduction of weight factor corrected the whole error of the different Three-Laterations results and increased localization precision.
2） Improved DV-Hop localization algorithm. As a range-free localization algorithm., DV-Hoprelies on network connectivity for localization and is low in localization precision. On the basisof the analysis of the relation between network topology and localization precision, in order toenhance localization precision, this paper modified the number of the hops between theunknown node and the refer node to get the distance between the unknown node and the refernode much closer to the real value. MATLAB simulation showed that the improved algorithmimproved localization precision.
引文
[1] GREGORY T.FRENCH.UNDERSTANDING THE GPS[M].Bethesta：GeoResearch,Inc，1996.
[2] Ruixue Li, Zhiyi FANG, Baocong HAO, Fengjie YANG..Research on Indoor Wireless LocalizationSystem for Radioactive Sources Based on Zigbee[C].2010International Conference OnComputing,control and Industrial Engineering.359-361.
[3]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.
[4]原羿，苏鸿根.基于ZigBee技术的无线网络应用研究.计算机应用与软件.2004,21（6）：89-91.
[5] Angela Song-Ie Noh, Woong Jae Lee, Jin Young Ye. Comparison of the mechanisms of the Zigbee'sindoor localization algorithm. Ninth ACIS International Conference on Software Engineering,Artificial Intelligence, Networking, and Parallel/Distributed Computing.2008：13-18.
[6]杨巨辉，许东来，王晓亮.基于ZigBee系统研究与应用[J].自动化与仪表.2011,12:38-41.
[7] Robin Wentao Ouyang，Albert Kai-Sun Wong，Chin-Tau Lea. Received Signal Strength-BasedWireless Localization via Semidefinite Programming:Noncooperative and Cooperative Schemes.IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY.2010：1307-1318.
[8]胡加艳，陈秀万，陶迎春，王炜婷.基于室内外定位的校园LBS研究.计算机工程.2010,36（8）:23-27.
[9]王华，杨祥龙，李琦，曹泓，王立人.冷库氨气无线监测系统与泄漏点定位方法[J].传感器与微系统.2012,21（3）:25-28.
[10]刘彬.煤矿瓦斯监测网格型无线传感器网络的实现.北京交通大学硕士学位论文.2001
[11] Mo Li，Yun hao Liu, Chen L．Nonthreshold-based event detection for3D environment monitoring insensor networks．In：Proc．of IEEE ICDCS，Canada，June2007，9：1699-1711.
[12]崔璐，蔡觉平，赵博超，王鑫.基于ZigBee技术的井下人员定位安全监测系统[J].大连理工大学学报.2011,51(4)：102-106.
[13]林权，赵方，海勇，康一梅.基于图谱分解的无线定位算法[J].自动化学报.2011,37（3）：316-321.
[14]杨清.基于指纹的无线室内精确定位方法研究.浙江大学硕士学位论文.2011.
[15] Sidharth，Arnon，Andrew G.Dempster. Indoor Positioning Using Fingerpnting with Locata Signals.International Global Navigation Satellite Systems Society IGNSS Symposium.2007:1-14.
[16]赵军，李鸿斌，王智.无线网络室内定位系统研究[J].信息与控制.2008,37（4）：465-471.
[17] Want R，Hopper A，Falcao V，et al. The active badge location system[J].ACM Transactions OnInformation Systems，1992,10（1）:92-102.
[18] NB.Printha,A．Chakraborty，HBalakrishnan．The cricket location support System.In:Proc.Of the6thAnnual Int'l Conf. on Mobile Computing and Networking.1999:32-43.
[19]王鸿鹏，王耀宽.基于Cricket传感器网络室内定位系统的设计与实现[J].计算机工程与应用.2008,44（2）:211-214.
[20]贺远华，黎洪生.距离几何TOA无线定位算法[J].计算机工程与应用.2010,12（4）:112-114.
[21]王洪雁，陈黎霞,裴炳南.NLOS环境下TDOA/AOA混合定位算法研究[J].计算机应用.2007,27（5）:1099-1102.
[22]韩霜，罗海勇，陈颖，丁玉珍.基于TDOA的超声波室内定位系统的设计与实现[J].传感技术学报.2010,23（3）:347-353.
[23]何艳丽.无线传感器网络质心定位算法研究.计算机仿真.2011,28（5）:163-166.
[24]江禹生，冯砚毫.一种新的DV-Hop定位算法[J].传感技术学报.2010,23（12）:1816-1819.
[25]周勇，夏士雄，丁世飞，张磊，熬欣.基于三角形重心扫描的改进APIT无线传感器网络定位算法[J].计算机研究与发展.2009,46（4）：566-574.
[26]张翰，刘锋.无线传感器网络基于凸规划的改进定位算法：Convex-PIT[J].传感技术学报.2007，20（5）：1129-1133.
[27]吕振，谭鹏立.一种基于RSSI校正的三角形质心定位算法[J].传感器与微系统.2010,29（5）：122-124.
[28]朱建新，高蕾娜，张新访.基于距离几何约束的二次加权质心定位算法[J].计算机应用.2009,29（2）：480-483.
[29]朱勇，王苹，张昕明.基于WSN的加权组合三边气体源定位算法研究[J].电子测量技术.2009,32（8）：12-14.
[30]罗维，姜秀柱，盛蒙蒙.无线传感器网络选择性DV-Hop定位算法[J].传感器与微系统.2012,31（3）：71-77.
[31]刘文远，王恩爽，陈子军.无线传感器网络DV-Hop定位算法的改进[J].小型微型计算机系统.2011,6(32):1071-1074.
[32] Zhu Minghui，Zhang Huiqing. Research on Model of Indoor Distance Measurement Based ReceivingSignal Strength[C]//2010International Conference On Computer Design And Applications.(Iccda2010).Qinhuangdao,[S.1.]:[s.n.],2010:54-58.
[33]于宁，万江文，冯仁剑.无线传感器网络定位求精方法[J].高技术通讯.2008,10:543-548.
[34]葛文涛，陈俊杰.基于三边定位的WSN锚节点加权补偿算法[J].测控技术.2010,29（9）:92-95.
[35]石琴琴，霍宏，方涛，李德仁.使用最速下降算法提高极大似然估计算法的节点定位精度[J].计算机应用研究.2008,25(7):124-127.
[36]任维政，徐连明，邹德君，邓中亮.基于RSSI差分似然估计的WSN节点定位算法[J].2009,6(24).
[37] Angelo Coluccia, Fabio Ricciato. On ML estimation for automatic RSS-based indoor localization.20105th International Symposium on wireless Pervasive Computing:495-502.
[38]顾宗海.基于RSSI测距的室内定位算法研究.郑州大学硕士学位论文.2011.
[39]毛永毅，周康磊.基于BP神经网络的定位跟踪算法[J].计算机工程与应用.2011,47（20）：238-240.
[40] Neal Patwari，Joshua N. Ash，Spyros Kyperountas，et al.Locating the Nodes：Cooperative localizationin wireless sensor networks.2005：55-68.
[41] Chao Yang, Lijun Chen, Daoxu Chen, Li Xie. Topology Optimization for Target localization InWireless Sensor Networks.2009International on Networks Security, Wireless communications andtrusted computing:481-484.
[42] Binwei Deng, Guangming Huang, Lei Zhang, Hao Liu. Improved Centroid Localization Algorithm inWSNS. Proceedings of20083rd International Conference on Intelligent System and KnowledgeEngineering:1260-1264.
[43]王振杰.测量中不适定问题的正规化解法[M].科学出版设,2006.
[44]孙佩刚，赵海，韩光洁，张希元，朱剑.混沌三角形定位参考点选择算法[J].计算机研究与发展.2007,12（44）:1987-1995.
[45]黄浩，卢文科.无线传感器网络中基于锚节点反馈的多跳测距定位算法改进[J].传感技术学报.2009,22（2）：269-272.
[46]彭刚，曹元大，孙利民.无线传感器网络节点定位机制的研究[J].计算机工程与应用.2004,40（35）：27-29.
[47]肖美华，周之平.无线传感器节点加权平均跳距定位算法[J].计算机工程与应用.2010,31（1）：78-85.
[48]嵇伟伟，刘中.DV-Hop定位算法在随机传感器网络中的应用研究[J].电子与信息学报.2008,3（04）：970-974.
[49] Xiao Yi, Yu Liu, Lu Deng, You He. An improved DV-Hop positioning algorithm with modifieddistance error for wireless sensor networks.2009Second International Symposium on KnowledgeAcquisition and Modeling:216-218.
[50]赵灵锴，洪志全.基于无线传感器网络的DV-Hop定位算法的改进[J].计算机应用.2011，31（5）：1189-1192.
[51]林今朝，刘海波，李国军.无线传感器网络中DV-HOP节点定位改进算法研究[J].计算机应用研究.2009,26（4）：1272-1275.
[2] Ruixue Li, Zhiyi FANG, Baocong HAO, Fengjie YANG..Research on Indoor Wireless LocalizationSystem for Radioactive Sources Based on Zigbee[C].2010International Conference OnComputing,control and Industrial Engineering.359-361.
[3]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.
[4]原羿，苏鸿根.基于ZigBee技术的无线网络应用研究.计算机应用与软件.2004,21（6）：89-91.
[5] Angela Song-Ie Noh, Woong Jae Lee, Jin Young Ye. Comparison of the mechanisms of the Zigbee'sindoor localization algorithm. Ninth ACIS International Conference on Software Engineering,Artificial Intelligence, Networking, and Parallel/Distributed Computing.2008：13-18.
[6]杨巨辉，许东来，王晓亮.基于ZigBee系统研究与应用[J].自动化与仪表.2011,12:38-41.
[7] Robin Wentao Ouyang，Albert Kai-Sun Wong，Chin-Tau Lea. Received Signal Strength-BasedWireless Localization via Semidefinite Programming:Noncooperative and Cooperative Schemes.IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY.2010：1307-1318.
[8]胡加艳，陈秀万，陶迎春，王炜婷.基于室内外定位的校园LBS研究.计算机工程.2010,36（8）:23-27.
[9]王华，杨祥龙，李琦，曹泓，王立人.冷库氨气无线监测系统与泄漏点定位方法[J].传感器与微系统.2012,21（3）:25-28.
[10]刘彬.煤矿瓦斯监测网格型无线传感器网络的实现.北京交通大学硕士学位论文.2001
[11] Mo Li，Yun hao Liu, Chen L．Nonthreshold-based event detection for3D environment monitoring insensor networks．In：Proc．of IEEE ICDCS，Canada，June2007，9：1699-1711.
[12]崔璐，蔡觉平，赵博超，王鑫.基于ZigBee技术的井下人员定位安全监测系统[J].大连理工大学学报.2011,51(4)：102-106.
[13]林权，赵方，海勇，康一梅.基于图谱分解的无线定位算法[J].自动化学报.2011,37（3）：316-321.
[14]杨清.基于指纹的无线室内精确定位方法研究.浙江大学硕士学位论文.2011.
[15] Sidharth，Arnon，Andrew G.Dempster. Indoor Positioning Using Fingerpnting with Locata Signals.International Global Navigation Satellite Systems Society IGNSS Symposium.2007:1-14.
[16]赵军，李鸿斌，王智.无线网络室内定位系统研究[J].信息与控制.2008,37（4）：465-471.
[17] Want R，Hopper A，Falcao V，et al. The active badge location system[J].ACM Transactions OnInformation Systems，1992,10（1）:92-102.
[18] NB.Printha,A．Chakraborty，HBalakrishnan．The cricket location support System.In:Proc.Of the6thAnnual Int'l Conf. on Mobile Computing and Networking.1999:32-43.
[19]王鸿鹏，王耀宽.基于Cricket传感器网络室内定位系统的设计与实现[J].计算机工程与应用.2008,44（2）:211-214.
[20]贺远华，黎洪生.距离几何TOA无线定位算法[J].计算机工程与应用.2010,12（4）:112-114.
[21]王洪雁，陈黎霞,裴炳南.NLOS环境下TDOA/AOA混合定位算法研究[J].计算机应用.2007,27（5）:1099-1102.
[22]韩霜，罗海勇，陈颖，丁玉珍.基于TDOA的超声波室内定位系统的设计与实现[J].传感技术学报.2010,23（3）:347-353.
[23]何艳丽.无线传感器网络质心定位算法研究.计算机仿真.2011,28（5）:163-166.
[24]江禹生，冯砚毫.一种新的DV-Hop定位算法[J].传感技术学报.2010,23（12）:1816-1819.
[25]周勇，夏士雄，丁世飞，张磊，熬欣.基于三角形重心扫描的改进APIT无线传感器网络定位算法[J].计算机研究与发展.2009,46（4）：566-574.
[26]张翰，刘锋.无线传感器网络基于凸规划的改进定位算法：Convex-PIT[J].传感技术学报.2007，20（5）：1129-1133.
[27]吕振，谭鹏立.一种基于RSSI校正的三角形质心定位算法[J].传感器与微系统.2010,29（5）：122-124.
[28]朱建新，高蕾娜，张新访.基于距离几何约束的二次加权质心定位算法[J].计算机应用.2009,29（2）：480-483.
[29]朱勇，王苹，张昕明.基于WSN的加权组合三边气体源定位算法研究[J].电子测量技术.2009,32（8）：12-14.
[30]罗维，姜秀柱，盛蒙蒙.无线传感器网络选择性DV-Hop定位算法[J].传感器与微系统.2012,31（3）：71-77.
[31]刘文远，王恩爽，陈子军.无线传感器网络DV-Hop定位算法的改进[J].小型微型计算机系统.2011,6(32):1071-1074.
[32] Zhu Minghui，Zhang Huiqing. Research on Model of Indoor Distance Measurement Based ReceivingSignal Strength[C]//2010International Conference On Computer Design And Applications.(Iccda2010).Qinhuangdao,[S.1.]:[s.n.],2010:54-58.
[33]于宁，万江文，冯仁剑.无线传感器网络定位求精方法[J].高技术通讯.2008,10:543-548.
[34]葛文涛，陈俊杰.基于三边定位的WSN锚节点加权补偿算法[J].测控技术.2010,29（9）:92-95.
[35]石琴琴，霍宏，方涛，李德仁.使用最速下降算法提高极大似然估计算法的节点定位精度[J].计算机应用研究.2008,25(7):124-127.
[36]任维政，徐连明，邹德君，邓中亮.基于RSSI差分似然估计的WSN节点定位算法[J].2009,6(24).
[37] Angelo Coluccia, Fabio Ricciato. On ML estimation for automatic RSS-based indoor localization.20105th International Symposium on wireless Pervasive Computing:495-502.
[38]顾宗海.基于RSSI测距的室内定位算法研究.郑州大学硕士学位论文.2011.
[39]毛永毅，周康磊.基于BP神经网络的定位跟踪算法[J].计算机工程与应用.2011,47（20）：238-240.
[40] Neal Patwari，Joshua N. Ash，Spyros Kyperountas，et al.Locating the Nodes：Cooperative localizationin wireless sensor networks.2005：55-68.
[41] Chao Yang, Lijun Chen, Daoxu Chen, Li Xie. Topology Optimization for Target localization InWireless Sensor Networks.2009International on Networks Security, Wireless communications andtrusted computing:481-484.
[42] Binwei Deng, Guangming Huang, Lei Zhang, Hao Liu. Improved Centroid Localization Algorithm inWSNS. Proceedings of20083rd International Conference on Intelligent System and KnowledgeEngineering:1260-1264.
[43]王振杰.测量中不适定问题的正规化解法[M].科学出版设,2006.
[44]孙佩刚，赵海，韩光洁，张希元，朱剑.混沌三角形定位参考点选择算法[J].计算机研究与发展.2007,12（44）:1987-1995.
[45]黄浩，卢文科.无线传感器网络中基于锚节点反馈的多跳测距定位算法改进[J].传感技术学报.2009,22（2）：269-272.
[46]彭刚，曹元大，孙利民.无线传感器网络节点定位机制的研究[J].计算机工程与应用.2004,40（35）：27-29.
[47]肖美华，周之平.无线传感器节点加权平均跳距定位算法[J].计算机工程与应用.2010,31（1）：78-85.
[48]嵇伟伟，刘中.DV-Hop定位算法在随机传感器网络中的应用研究[J].电子与信息学报.2008,3（04）：970-974.
[49] Xiao Yi, Yu Liu, Lu Deng, You He. An improved DV-Hop positioning algorithm with modifieddistance error for wireless sensor networks.2009Second International Symposium on KnowledgeAcquisition and Modeling:216-218.
[50]赵灵锴，洪志全.基于无线传感器网络的DV-Hop定位算法的改进[J].计算机应用.2011，31（5）：1189-1192.
[51]林今朝，刘海波，李国军.无线传感器网络中DV-HOP节点定位改进算法研究[J].计算机应用研究.2009,26（4）：1272-1275.