基于可靠信标和节点度估计距离的无线传感器网络定位算法
|
摘要
针对经典的DV-Hop、Amorphous等免测距无线传感器网络(WSN)定位算法信标节点选择不可靠、距离模糊和距离估计不准确等问题导致定位精度低,难以适应传感器节点分布不均匀应用的情况,提出了基于可靠信标和节点度估计距离的无线传感器网络定位算法(RDLA)。首先,通过跳数阈值和定位三角可靠度计算来选择引入误差小的信标节点;然后,利用节点度感知的距离估计方法计算单跳距离以解决距离模糊问题,在累积最小跳数路径(SHP)距离并修正使估计的最小跳数路径距离更准确;最后用双曲线定位方法提高定位精度。Matlab R2012a仿真结果表明:在节点均匀分布的应用中,RDLA的平均定位误差(ALE)比DV-Hop算法及其改进算法小;在节点非均匀和具有覆盖洞的C型分布的应用中,与DV-Hop算法及其改进算法相比,RDLA的ALE显著降低,几乎控制在28%以下。
Traditional DV-Hop localization algorithm and Amorphous algorithm for Wireless Sensor Network(WSN) can not meet practical application with lower localization accuracy due to defects of colinearity of beacons, range ambiguity and the distance error caused by path deviation. Especially, in the node heterogeneously distributed application scenario, the problem becomes more serious. So, a Reliable beacon-based and Density-aware distance Localization Algorithm for WSN(RDLA) was proposed to improve localization accuracy. Firstly, hop threshold and reliability function of approximate equilateral triangle were employed to select the beacon nodes with small error to avoid collinear problem. Secondly, node density-aware hop distance estimation method was used to solve range ambiguity problem, and distances were cumulatived along the Shortest Hop Path(SHP) from unknown node to three beacons. This distance was amended to straight-line distance. Finally, two-dimensional hyperbolic calculation method was adopted to determine locations of unknown nodes and improve node location accuracy. The extensive simulation results by Matlab R2012 a show that the Average Localization Error(ALE) of RDLA is lower than that of DV-Hop algorithm and its improvement algorithms in node uniform distribution network. Remarkably, RDLA is tremendously superior to the others with the lowest ALE in node non-uniform distribution network and C shape network, in which, the ALE is almost controlled below 28%.
Traditional DV-Hop localization algorithm and Amorphous algorithm for Wireless Sensor Network(WSN) can not meet practical application with lower localization accuracy due to defects of colinearity of beacons, range ambiguity and the distance error caused by path deviation. Especially, in the node heterogeneously distributed application scenario, the problem becomes more serious. So, a Reliable beacon-based and Density-aware distance Localization Algorithm for WSN(RDLA) was proposed to improve localization accuracy. Firstly, hop threshold and reliability function of approximate equilateral triangle were employed to select the beacon nodes with small error to avoid collinear problem. Secondly, node density-aware hop distance estimation method was used to solve range ambiguity problem, and distances were cumulatived along the Shortest Hop Path(SHP) from unknown node to three beacons. This distance was amended to straight-line distance. Finally, two-dimensional hyperbolic calculation method was adopted to determine locations of unknown nodes and improve node location accuracy. The extensive simulation results by Matlab R2012 a show that the Average Localization Error(ALE) of RDLA is lower than that of DV-Hop algorithm and its improvement algorithms in node uniform distribution network. Remarkably, RDLA is tremendously superior to the others with the lowest ALE in node non-uniform distribution network and C shape network, in which, the ALE is almost controlled below 28%.
引文
[1]AKYILDZ I.F,SU W,SANKARASUBRAMANIAM Y,et al.Asurvey on sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.
[2]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-867.(WANG F B,SHI L,REN F Y.Self-localization systems and algorithms for wireless sensor networks[J].Journal of Software,2005,16(5):857-867.)
[3]曾凡仔,孙正章,罗娟,等.无线传感器网络的节点定位方法[J].通信学报,2008,29(11):62-66.(ZENG F Z,SUN Z Z,LUO J,et al.Improved node localization algorithm for wireless sensor network[J].Journal on Communications,2008,29(11):62-66.)
[4]ZHONG Z,HE T.Achieving range-free localization beyond connectivity[C]//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems.New York:ACM,2009:281-294.
[5]PATWARI N,HERO A O,PERKINS M,et al.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,2003,51(8):2137-2148.
[6]GIROD L,ESTRIN D.Robust range estimation using acoustic and multimodal sensing[C]//Proceedings of the 2001 International Conference on Intelligent Robots and Systems.Piscataway,NJ:IEEE,2001:1312-1320.
[7]LAZOS L,POOVENDRAN R.ROPE:robust position estimation in wireless sensor networks[C]//Proceedings of the 2005 International Symposium on Information Processing in Sensor Networks.Piscataway,NJ:IEEE,2005:323-331.
[8]NICULESCU D,NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1/2/3/4):267-280.
[9]JI W W,LIU Z.An improvement of DV-Hop algorithm in wireless sensor networks[C]//Proceedings of the 2006 International Conference on Wireless Communications,Networking and Mobile Computing.Piscataway,NJ:IEEE,2006:1-4.
[10]张爱清,叶新荣,胡海峰.无线传感器网络质心定位新算法及性能分析[J].计算机应用,2012,32(9):2429-2431.(ZHANG AQ,YE X R,HU H F.Performance analysis of new centroid localization algorithm in wireless sensor network[J].Journal of Computer Applications,2012,32(9):2429-2431.)
[11]HE T,HUANG C,BLUM B M,et al.Range-free localization and its impact on large scale sensor networks[J].ACM Transactions on Embedded Computing Systems,2005,4(4):877-906.
[12]石为人,贾传江,梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报,2011,24(1):83-87.(SHI W R,JIA C J,LIANG H H.An improved DV-Hop localization algorithm for wireless sensor networks[J].Chinese Journal of Sensors and Actuators,2011,24(1):83-87.)
[13]刘锋,张翰,杨骥.一种基于加权处理的无线传感器网络平均跳距离估计算法[J].电子与信息学报,2008,30(5):1222-1225.(LIU F,ZHANG H,YANG J.An average one-hop distance estimation algorithm based on weighted disposal in wireless sensor network[J].Journal of Electronics and Information Technology,2008,30(5):1222-1225.)
[14]林金朝,陈晓冰,刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法[J].通信学报,2009,30(10):107-113.(LIN J Z,CHEN X B,LIU H B.Iterative algorithm for locating nodes in WSN based on modifying average hopping distances[J].Journal on Communications,2009,30(10):107-113.)
[15]景路路,张玲华.基于跳距优化的改进型DV-Hop定位算法[J].传感技术学报,2017,30(4):582-586.(JING L L,ZHANGL H.An improved DV-Hop location algorithm based on hop-distance optimization[J].Chinese Journal of Sensors and Actuators,2017,30(4):582-586.)
[16]赵芝璞,吴栋,王艳,等.基于平均跳距和位置优化的改进DV-Hop定位算法[J].系统仿真学报,2016,28(6):1273-1280.(ZHAO Z P,WU D,WANG Y,et al.Improved DV-Hop localization algorithm based on average hopping distance and position optimization[J].Journal of System Simulation,2016,28(6):1273-1280.)
[17]WU G,WANG S,WANG B,et al.A novel range-free localization based on regulated neighborhood distance for wireless Ad Hoc and sensor networks[J].Computer Networks,2012,56(16):3581-3593.
[18]GUI L,VAL T,WEI A,et al.Improvement of range-free localization technology by a novel DV-Hop protocol in wireless sensor networks[J].Ad Hoc Networks,2015,24:55-73.
[19]LI M,LIU Y H.Rendered path:range-free localization in anisotropic sensor networks with holes[J].IEEE/ACM Transactions on Networking,2007,18(1):320-332.
[20]GAO B,ZHAO X,WANG J,et al.Decomposition based localization for anisotropic sensor networks[J].International Journal of Distributed Sensor Networks,2015,2015:Article No.8.
[21]SONG G,TAM D.Two novel DV-Hop localization algorithms for randomly deployed wireless sensor networks[J].International Journal of Distributed Sensor Networks,2015,2015:Article ID187670.
[22]SABALE K,MINI S.Anchor node path planning for localization in wireless sensor networks[J].Wireless Networks,2017(8):1-13.
[23]HUANG B,YU C,ANDERSON G,et al.Connectivity-based distance estimation in wireless sensor networks[C]//Proceedings of the 2010 Global Telecommunications Conference.Piscataway,NJ:IEEE,2010:1-5.
[24]HAN G,CHOI D,LIM W.Reference node placement and selection algorithm based on trilateration for indoor sensor networks[J].Wireless Communications&Mobile Computing,2009,9(8):1017-1027.
[25]SARRATR J,PALAU J,HUERTA A.Numerical representation of the quality measures of triangles and triangular meshes[J].International Journal for Numerical Methods in Biomedical Engineering,2003,19(7):551-561.
[26]KLEIN L,SILEVESTR J.Optimum transmission radii for packet radio networks or why six is a magic number[C]//Proceedings of the 1978 IEEE National Telecommunication Conference.Piscataway,NJ:IEEE,1978:431-435.
[2]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-867.(WANG F B,SHI L,REN F Y.Self-localization systems and algorithms for wireless sensor networks[J].Journal of Software,2005,16(5):857-867.)
[3]曾凡仔,孙正章,罗娟,等.无线传感器网络的节点定位方法[J].通信学报,2008,29(11):62-66.(ZENG F Z,SUN Z Z,LUO J,et al.Improved node localization algorithm for wireless sensor network[J].Journal on Communications,2008,29(11):62-66.)
[4]ZHONG Z,HE T.Achieving range-free localization beyond connectivity[C]//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems.New York:ACM,2009:281-294.
[5]PATWARI N,HERO A O,PERKINS M,et al.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,2003,51(8):2137-2148.
[6]GIROD L,ESTRIN D.Robust range estimation using acoustic and multimodal sensing[C]//Proceedings of the 2001 International Conference on Intelligent Robots and Systems.Piscataway,NJ:IEEE,2001:1312-1320.
[7]LAZOS L,POOVENDRAN R.ROPE:robust position estimation in wireless sensor networks[C]//Proceedings of the 2005 International Symposium on Information Processing in Sensor Networks.Piscataway,NJ:IEEE,2005:323-331.
[8]NICULESCU D,NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1/2/3/4):267-280.
[9]JI W W,LIU Z.An improvement of DV-Hop algorithm in wireless sensor networks[C]//Proceedings of the 2006 International Conference on Wireless Communications,Networking and Mobile Computing.Piscataway,NJ:IEEE,2006:1-4.
[10]张爱清,叶新荣,胡海峰.无线传感器网络质心定位新算法及性能分析[J].计算机应用,2012,32(9):2429-2431.(ZHANG AQ,YE X R,HU H F.Performance analysis of new centroid localization algorithm in wireless sensor network[J].Journal of Computer Applications,2012,32(9):2429-2431.)
[11]HE T,HUANG C,BLUM B M,et al.Range-free localization and its impact on large scale sensor networks[J].ACM Transactions on Embedded Computing Systems,2005,4(4):877-906.
[12]石为人,贾传江,梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报,2011,24(1):83-87.(SHI W R,JIA C J,LIANG H H.An improved DV-Hop localization algorithm for wireless sensor networks[J].Chinese Journal of Sensors and Actuators,2011,24(1):83-87.)
[13]刘锋,张翰,杨骥.一种基于加权处理的无线传感器网络平均跳距离估计算法[J].电子与信息学报,2008,30(5):1222-1225.(LIU F,ZHANG H,YANG J.An average one-hop distance estimation algorithm based on weighted disposal in wireless sensor network[J].Journal of Electronics and Information Technology,2008,30(5):1222-1225.)
[14]林金朝,陈晓冰,刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法[J].通信学报,2009,30(10):107-113.(LIN J Z,CHEN X B,LIU H B.Iterative algorithm for locating nodes in WSN based on modifying average hopping distances[J].Journal on Communications,2009,30(10):107-113.)
[15]景路路,张玲华.基于跳距优化的改进型DV-Hop定位算法[J].传感技术学报,2017,30(4):582-586.(JING L L,ZHANGL H.An improved DV-Hop location algorithm based on hop-distance optimization[J].Chinese Journal of Sensors and Actuators,2017,30(4):582-586.)
[16]赵芝璞,吴栋,王艳,等.基于平均跳距和位置优化的改进DV-Hop定位算法[J].系统仿真学报,2016,28(6):1273-1280.(ZHAO Z P,WU D,WANG Y,et al.Improved DV-Hop localization algorithm based on average hopping distance and position optimization[J].Journal of System Simulation,2016,28(6):1273-1280.)
[17]WU G,WANG S,WANG B,et al.A novel range-free localization based on regulated neighborhood distance for wireless Ad Hoc and sensor networks[J].Computer Networks,2012,56(16):3581-3593.
[18]GUI L,VAL T,WEI A,et al.Improvement of range-free localization technology by a novel DV-Hop protocol in wireless sensor networks[J].Ad Hoc Networks,2015,24:55-73.
[19]LI M,LIU Y H.Rendered path:range-free localization in anisotropic sensor networks with holes[J].IEEE/ACM Transactions on Networking,2007,18(1):320-332.
[20]GAO B,ZHAO X,WANG J,et al.Decomposition based localization for anisotropic sensor networks[J].International Journal of Distributed Sensor Networks,2015,2015:Article No.8.
[21]SONG G,TAM D.Two novel DV-Hop localization algorithms for randomly deployed wireless sensor networks[J].International Journal of Distributed Sensor Networks,2015,2015:Article ID187670.
[22]SABALE K,MINI S.Anchor node path planning for localization in wireless sensor networks[J].Wireless Networks,2017(8):1-13.
[23]HUANG B,YU C,ANDERSON G,et al.Connectivity-based distance estimation in wireless sensor networks[C]//Proceedings of the 2010 Global Telecommunications Conference.Piscataway,NJ:IEEE,2010:1-5.
[24]HAN G,CHOI D,LIM W.Reference node placement and selection algorithm based on trilateration for indoor sensor networks[J].Wireless Communications&Mobile Computing,2009,9(8):1017-1027.
[25]SARRATR J,PALAU J,HUERTA A.Numerical representation of the quality measures of triangles and triangular meshes[J].International Journal for Numerical Methods in Biomedical Engineering,2003,19(7):551-561.
[26]KLEIN L,SILEVESTR J.Optimum transmission radii for packet radio networks or why six is a magic number[C]//Proceedings of the 1978 IEEE National Telecommunication Conference.Piscataway,NJ:IEEE,1978:431-435.