加权质心和DV-Hop混合算法研究
|
摘要
随着无线通讯技术、电子技术以及计算技术的迅速发展,传感器网络作为获取信息的新方式出现并得到广泛应用。无线传感器网络主要的功能是将传感器节点采集的有用数据进行处理并使用无线通信网络传输给计算机,实现对传感器网络覆盖区域的检测。在传感器网络的许多应用中,传感器节点的位置对整个应用起着至关重要的作用,如将传感器网络应用于消防警报中,当传感器网络节点通过无线网络向消防局发出消防警报时,必须同时告知自身位置,这样消防局根据提供的位置信息才能尽快采取措施,传感器网络提供的信息才是有用的信息。
本论文综合加权质心定位算法和DV-Hop定位算法两种算法在对待定位节点进行定位时存在的优势,并对其不足的地方进行改进。论文算法首先将传感器网络中信标节点进行虚拟网格划分,然后根据质心定位算法与DV-Hop定位算法的特点,分情况对网络中的待定位节点进行定位。当虚拟网格中的信标节点达到门限值时,使用质心定位算法对虚拟网格中的待定位节点进行定位,反之,则使用DV-Hop定位算法对虚拟网格中待定位节点进行定位。
加权质心算法在定位待定位节点时由于信标节点比例较低且分布不均匀而导致定位精度较低的问题,论文将加权质心定位算法的定位分为两个阶段,在第一个阶段中使用加权质心定位算法形成质心区域,在第二阶段中,对得到的质心再次使用加权质心定位算法,通过这样的改进以期加权质心定位算法在实际应用中能取到更好的定位效果。
通过分析对DV-Hop定位算法在定位待定位节点时误差产生的原因,并针对DV-Hop定位算法产生误差的主要原因是平均每跳距离值的计算误差,提出改进方案,使DV-Hop定位算法在定位待定位节点时能够更加精确。
最后论文使用Matlab平台进行仿真测试,该算法与文献[27]所述算法相比,无论是在节点总数固定、信标节点比例可变的情况下,还是在信标节点比例固定、节点总数可变的情况下,本文算法均减小了定位待定位节点时产生的误差,提高了定位精度。
With the rapid development of wireless communication technology, electronic technology and computing technology, wireless sensor networks is a new means to get information, and widely used. The main function of wireless sensor networks is to process the useful datas collected by sensor nodes and transmit those data using wireless communication network to a computer to detect of sensor network coverage area. In many applications of sensor network, the position of sensor node plays a vital role in the entire application, such as sensor network is used in fire alarm, when a sensor node of sensor network sends out a fire alarm through wireless network to the Fire Department, it must also inform the its position, so Fire Department can take measures as soon as possible based on the provided position information, and the information provided by sensor networks is useful information.
This paper integrats the advantage of weighted centroid localization algorithm and DV-Hop localization algorithm, nextly makes up for their deficiencies. The algorithm put forward in thesis firstly partitions beacon nodes by virtual grids, then locates sensor nodes using centroid location algorithm or DV-Hop localization algorithm based on the number of beacon nodes in virtual grid. When the number of beacon nodes in a virtual grid reachs the threshold, the algorithm uses centroid localization algorithm to locate the node in the virtual grid, otherwise, it uses DV-Hop localization algorithm to locate the node in the virtual grid.
Beasuse of the low accuracy of weighted centroid algorithm caused by the low ratio and uneven distribution beacon nodes, the paper devides weighted centroid location algorithm into two stages, in the first phase of is to form the centroid region using weighted centroid location algorithm, in the second stage, unknown node uses weighted centroid localization algorithm in centroid region, such improvements of weighted centroid localization algorithm in applications can take to better results.
Through analyzing the orientation of when DV-Hop localization algorithm locates the nodes, it can be found that localization error of DV-Hop localization algorithm is mainly due to the calculation error of hop-size, so improvement program is proposed in the paper to make the location of node using DV-Hop localization Algorithm more precise.
Finally, the algorithm proposes in article is tested by Matlab, compared with the algorithm of Bai J al. [27], both in the situtation that the total number of nodes is fixed, the ratio of beacon nodes is variable, and the situtation that the percentage of beacon nodes is fixed, the total number of nodes is variable, the proposed algorithm reduces the localization error and increases the positioning accuracy.
本论文综合加权质心定位算法和DV-Hop定位算法两种算法在对待定位节点进行定位时存在的优势,并对其不足的地方进行改进。论文算法首先将传感器网络中信标节点进行虚拟网格划分,然后根据质心定位算法与DV-Hop定位算法的特点,分情况对网络中的待定位节点进行定位。当虚拟网格中的信标节点达到门限值时,使用质心定位算法对虚拟网格中的待定位节点进行定位,反之,则使用DV-Hop定位算法对虚拟网格中待定位节点进行定位。
加权质心算法在定位待定位节点时由于信标节点比例较低且分布不均匀而导致定位精度较低的问题,论文将加权质心定位算法的定位分为两个阶段,在第一个阶段中使用加权质心定位算法形成质心区域,在第二阶段中,对得到的质心再次使用加权质心定位算法,通过这样的改进以期加权质心定位算法在实际应用中能取到更好的定位效果。
通过分析对DV-Hop定位算法在定位待定位节点时误差产生的原因,并针对DV-Hop定位算法产生误差的主要原因是平均每跳距离值的计算误差,提出改进方案,使DV-Hop定位算法在定位待定位节点时能够更加精确。
最后论文使用Matlab平台进行仿真测试,该算法与文献[27]所述算法相比,无论是在节点总数固定、信标节点比例可变的情况下,还是在信标节点比例固定、节点总数可变的情况下,本文算法均减小了定位待定位节点时产生的误差,提高了定位精度。
With the rapid development of wireless communication technology, electronic technology and computing technology, wireless sensor networks is a new means to get information, and widely used. The main function of wireless sensor networks is to process the useful datas collected by sensor nodes and transmit those data using wireless communication network to a computer to detect of sensor network coverage area. In many applications of sensor network, the position of sensor node plays a vital role in the entire application, such as sensor network is used in fire alarm, when a sensor node of sensor network sends out a fire alarm through wireless network to the Fire Department, it must also inform the its position, so Fire Department can take measures as soon as possible based on the provided position information, and the information provided by sensor networks is useful information.
This paper integrats the advantage of weighted centroid localization algorithm and DV-Hop localization algorithm, nextly makes up for their deficiencies. The algorithm put forward in thesis firstly partitions beacon nodes by virtual grids, then locates sensor nodes using centroid location algorithm or DV-Hop localization algorithm based on the number of beacon nodes in virtual grid. When the number of beacon nodes in a virtual grid reachs the threshold, the algorithm uses centroid localization algorithm to locate the node in the virtual grid, otherwise, it uses DV-Hop localization algorithm to locate the node in the virtual grid.
Beasuse of the low accuracy of weighted centroid algorithm caused by the low ratio and uneven distribution beacon nodes, the paper devides weighted centroid location algorithm into two stages, in the first phase of is to form the centroid region using weighted centroid location algorithm, in the second stage, unknown node uses weighted centroid localization algorithm in centroid region, such improvements of weighted centroid localization algorithm in applications can take to better results.
Through analyzing the orientation of when DV-Hop localization algorithm locates the nodes, it can be found that localization error of DV-Hop localization algorithm is mainly due to the calculation error of hop-size, so improvement program is proposed in the paper to make the location of node using DV-Hop localization Algorithm more precise.
Finally, the algorithm proposes in article is tested by Matlab, compared with the algorithm of Bai J al. [27], both in the situtation that the total number of nodes is fixed, the ratio of beacon nodes is variable, and the situtation that the percentage of beacon nodes is fixed, the total number of nodes is variable, the proposed algorithm reduces the localization error and increases the positioning accuracy.
引文
[1]陈维克,李文锋,首珩等,基于RSSI的无线传感器网络加权质心定位算法[J],武汉理工大学学报,2006.
[2]白进京,严新平,张存保等,基于加权质心和DV-Hop混合算法WSN定位算法研究[J],计算机应用,2009,2248-2250.
[3]Girod L, Bychovskiy V, Elson J, Estrin D, Locating tiny sensors in time and space:A case study, In:Proc. of the 2002 IEEE Int'l Conf, on Computer Design:VLSI in Computers and Processors, Freiburg:IEEE Computer Society,2002,214-219.
[4]Harter A, Hopper A, Steggles P, Ward A, Webster P, The anatomy of a context-aware application, In:Proc. of the 5th Annual ACM/IEEE Int'l Conf, on Mobile Computing and Networking, Seattle,1999,59-68.
[5]Girod L, Estrin D, Robust range estimation using acoustic and multimodal sensing, In: Proc.of the IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems (IROS 01), Maui:IEEE Robotics and Automation Society,2001,1312-1320.
[6]Priyantha NB, Miu AKL, Balakrishnan H, Teller S. The cricket compass for context-aware mobile applications, In:Proc. of the 7th Annual Int'l Conf. on Mobile Computing and Networking, Rome,2001,1-14.
[7]Niculescu D, Nath B. Ad hoc positioning system (APS) using AoA, In:Proc. of the IEEE INFOCOM 2003, San Francisco:IEEE Computer and Communications Societies,2003,1734-1743.
[8]A.Savvides, C.C.Han, M.B.Srivastava, Dynamic finge-grained localization in ad-hoc networks of sensors, In Proceedings of 7th Annual International Conference, on Mobile Computing and Networking,2001,166-179.
[9]Bahl P, Venkata N, Padmanabhan, RADAR:An in-Building RF-based User Localization and Tracking System, In Proceeding of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies(InfoCom2000), 2000,775-784.
[10]Priyantha N B, Chakraborty A, Balakrishnan H, The cricket localization-support system, Proceedings of the 6th Annual Int'l Conf, on Mobile Computing and Networking. Boston,2000,32-43.
[11]D.Niculescu, B.Nath 2001, Ad Hoc Positioning System (APS), In Proceedings of the IEEE GLOBECOM, San Antonio,2001,2926-2931.
[12]R. Behnke, D.Timmermann, adaptive weighted centroid localization as an efficient improvement of coarse grained localization, In proceedings of the 5th workshop on positioning, Navigation and Communication,2008,243-250.
[13]Tian He, Chengdu Huang, Brian M. Blum, Range-Free Localization Schemes for Large Scale Sensor Networks, MobiCom'03,2003.
[14]L.Doherty, K.S.J.pister, L.El Ghaoui. Convex position estimation in wireless sensor networks, In INFOCOM 2001, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings. IEEE,2001,1655-1663.
[15]Doherty L, Algorithms for position and data recovery in wireless sensor networks, Berkeley:University of California,2000.
[16]Shang Y, Ruml W, Zhang Y, Fromherz MPJ, Localization from mere connectivity, In: Proc. of the 4th ACM Int'l Symp, on Mobile Ad Hoc Networking & Computing. Annapolis,2003,201-212.
[17]Avvides A, Park H, Srivastava MB, The bits and flops of the N-hop multilateration primitive for node localization problems, In:Proc. of the 1st ACM Int'l Workshop, on Wireless Sensor Networks and Applications, Atlanta,2002.
[18]Priyantha N B, Balakrishnam H, Demaine E, Teller S, Anchor-free distributed localization in sensor networks, Technical Report MIT-LCS-TR-892, MIT Lab for Computer Science,2003.
[19]孙利民,李建中,陈渝,朱红松,无线传感器网络,清华大学出版社,2005.
[20]N. Bulusu, J.Heidemann, and D. Estrin, GPS-less low-cost outdoor localization for very small devices, IEEE Personal Communications,2000,28-34.
[21]D.Niculescu, B.Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems,2003.
[22]R.Nagpa, Organizing a Global Coordinate System from Local Information on an Amorphous Computer, A.I. Memo 1666, MIT A.I. Laboratory,1999.
[23]Feldmann, S.An indoor Bluetooth-based positioning system:concept, implementa-tion and experimental evaluation, ICWN'03, Las Vegas, USA, Institute of Communi-cations Engineering, Hanover,2003,23-26.
[24]Tschumi, S. Positioning in mobile ad hoc networks, Semester Thesis, ETH Zurich, Switzerland,2002.
[25]Spec:Smartdust chip with integrated RF communications.2001. http://www. jlhlabs.com/jhill_cs/spec/.
[26]A. Ahmed, H. Shi, and Y. Shang, Sharp:A new approach to relative localization in wireless sensor network,25th IEEE International Conference on Distributed Computing Systems Workshop, ICDCSW,2006,892-898.
[27]白进京,严新平,张存保等,基于加权质心和DV-Hop混合算法WSN定位算法研究[J],计算机应用,2009,2248-2250.
[28]Doherty L, Algorithms for position and data recovery in wireless sensor networks, Berkeley:University of California,2000.
[29]陈维克,李文锋,首 珩等,基于RSSI的无线传感器网络加权质心定位算法[J],武汉理工大学学报：交通科学与工程版,2006.
[30]Jan Blumenthal, J. Minimal Transmission Power as Distance Estimation for Precise Localization in Sensor Networks, IWCMC'06, Vancouver, ACM,2006,3-6.
[31]王福豹,史龙,任丰原,无线传感器网络中的自身定位系统和算法[J],软件学报,2005.
[32]李建中,李金宝,石胜飞,传感器网络及其数据管理的概念、问题与进展[J],软件学报,2003,1717-1725.
[33]P.Bahl, V.N.Padmanabhan, RADAR:An in-building RF-based user location and tracking system, In IEEE INFOCOM, Tel Aviv, Isr,2000,775-784.
[34]N.B.Priyantha, A.Chakraborty, H.Balakrishnan, The cricket location-support system, In proceedings of the 6th Annual International Conference on Mobile Computing and Networking,2000,32-43.
[35]XF.Shen, Z.Wang, P.Jiang, Connectivity and RSSI based localization scheme for wireless sensor networks, In Lecture Notes in Computer Science, Hefei, China, 2005,578-587.
[36]T.He, C.Huang, B.Blum, Range-Free Localization Schemes for Large Scale Sensor Networks, In proceedings of the 9th Annual International Conference, on Mobile Computing and Networking,2003,81-95.
[37]C.Laurendeau, M. Barbeau, Centroid Localization of Uncooperative Nodes in Wireless Networks Using a Relative Span Weighting Method, EURASIP Journal on Wireless Communications and Networking,2010,1155-1164.
[38]Xu Y, Heidemann J, Estrin D, Geography-informed energy conservation for ad hoc routing, Proc 7th Annual Int'l Conf on Mobile Computing and Networking, Rome, Italy,2001,70-84.
[39]Want R, Hopper A, Falcao V, Gibbons J, The active badge location system, ACM Trans. on Information Systems,1992,91-102.
[40]Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S, picorodio supports ad hocultra-low power wireless networking,2000,42-48.
[41]Savarese C, Rabaey JM, Beutel J, Locationing in distributed ad-hoc wireless sensor network, In:Proc. of the 2001 IEEE Int'l Conf.on Acoustics, Speech, and Signal. Vol.4, Salt Lake:IEEE Signal Processing Society,2001,2037-2040.
[42]Capkun S, Hamdi M, Hubaux J-P, GPS-Free positioning in mobile ad-hoc networks, Cluster Computing,2002,157-167.
[43]N. Bulusu, J. Heidemann and D. Estrin, Density Adaptive Algorithms for Beacon Placement in Wireless Sensor Networks, In IEEE ICDCS'01, Phoenix, AZ, April 2001.
[44]J. Caffery, Jr. A New Approach to the Geometry of TOA Location, In IEEE Vehicular Technology Conference, Boston,2000.
[2]白进京,严新平,张存保等,基于加权质心和DV-Hop混合算法WSN定位算法研究[J],计算机应用,2009,2248-2250.
[3]Girod L, Bychovskiy V, Elson J, Estrin D, Locating tiny sensors in time and space:A case study, In:Proc. of the 2002 IEEE Int'l Conf, on Computer Design:VLSI in Computers and Processors, Freiburg:IEEE Computer Society,2002,214-219.
[4]Harter A, Hopper A, Steggles P, Ward A, Webster P, The anatomy of a context-aware application, In:Proc. of the 5th Annual ACM/IEEE Int'l Conf, on Mobile Computing and Networking, Seattle,1999,59-68.
[5]Girod L, Estrin D, Robust range estimation using acoustic and multimodal sensing, In: Proc.of the IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems (IROS 01), Maui:IEEE Robotics and Automation Society,2001,1312-1320.
[6]Priyantha NB, Miu AKL, Balakrishnan H, Teller S. The cricket compass for context-aware mobile applications, In:Proc. of the 7th Annual Int'l Conf. on Mobile Computing and Networking, Rome,2001,1-14.
[7]Niculescu D, Nath B. Ad hoc positioning system (APS) using AoA, In:Proc. of the IEEE INFOCOM 2003, San Francisco:IEEE Computer and Communications Societies,2003,1734-1743.
[8]A.Savvides, C.C.Han, M.B.Srivastava, Dynamic finge-grained localization in ad-hoc networks of sensors, In Proceedings of 7th Annual International Conference, on Mobile Computing and Networking,2001,166-179.
[9]Bahl P, Venkata N, Padmanabhan, RADAR:An in-Building RF-based User Localization and Tracking System, In Proceeding of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies(InfoCom2000), 2000,775-784.
[10]Priyantha N B, Chakraborty A, Balakrishnan H, The cricket localization-support system, Proceedings of the 6th Annual Int'l Conf, on Mobile Computing and Networking. Boston,2000,32-43.
[11]D.Niculescu, B.Nath 2001, Ad Hoc Positioning System (APS), In Proceedings of the IEEE GLOBECOM, San Antonio,2001,2926-2931.
[12]R. Behnke, D.Timmermann, adaptive weighted centroid localization as an efficient improvement of coarse grained localization, In proceedings of the 5th workshop on positioning, Navigation and Communication,2008,243-250.
[13]Tian He, Chengdu Huang, Brian M. Blum, Range-Free Localization Schemes for Large Scale Sensor Networks, MobiCom'03,2003.
[14]L.Doherty, K.S.J.pister, L.El Ghaoui. Convex position estimation in wireless sensor networks, In INFOCOM 2001, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings. IEEE,2001,1655-1663.
[15]Doherty L, Algorithms for position and data recovery in wireless sensor networks, Berkeley:University of California,2000.
[16]Shang Y, Ruml W, Zhang Y, Fromherz MPJ, Localization from mere connectivity, In: Proc. of the 4th ACM Int'l Symp, on Mobile Ad Hoc Networking & Computing. Annapolis,2003,201-212.
[17]Avvides A, Park H, Srivastava MB, The bits and flops of the N-hop multilateration primitive for node localization problems, In:Proc. of the 1st ACM Int'l Workshop, on Wireless Sensor Networks and Applications, Atlanta,2002.
[18]Priyantha N B, Balakrishnam H, Demaine E, Teller S, Anchor-free distributed localization in sensor networks, Technical Report MIT-LCS-TR-892, MIT Lab for Computer Science,2003.
[19]孙利民,李建中,陈渝,朱红松,无线传感器网络,清华大学出版社,2005.
[20]N. Bulusu, J.Heidemann, and D. Estrin, GPS-less low-cost outdoor localization for very small devices, IEEE Personal Communications,2000,28-34.
[21]D.Niculescu, B.Nath, DV Based Positioning in Ad hoc Networks, In Journal of Telecommunication Systems,2003.
[22]R.Nagpa, Organizing a Global Coordinate System from Local Information on an Amorphous Computer, A.I. Memo 1666, MIT A.I. Laboratory,1999.
[23]Feldmann, S.An indoor Bluetooth-based positioning system:concept, implementa-tion and experimental evaluation, ICWN'03, Las Vegas, USA, Institute of Communi-cations Engineering, Hanover,2003,23-26.
[24]Tschumi, S. Positioning in mobile ad hoc networks, Semester Thesis, ETH Zurich, Switzerland,2002.
[25]Spec:Smartdust chip with integrated RF communications.2001. http://www. jlhlabs.com/jhill_cs/spec/.
[26]A. Ahmed, H. Shi, and Y. Shang, Sharp:A new approach to relative localization in wireless sensor network,25th IEEE International Conference on Distributed Computing Systems Workshop, ICDCSW,2006,892-898.
[27]白进京,严新平,张存保等,基于加权质心和DV-Hop混合算法WSN定位算法研究[J],计算机应用,2009,2248-2250.
[28]Doherty L, Algorithms for position and data recovery in wireless sensor networks, Berkeley:University of California,2000.
[29]陈维克,李文锋,首 珩等,基于RSSI的无线传感器网络加权质心定位算法[J],武汉理工大学学报：交通科学与工程版,2006.
[30]Jan Blumenthal, J. Minimal Transmission Power as Distance Estimation for Precise Localization in Sensor Networks, IWCMC'06, Vancouver, ACM,2006,3-6.
[31]王福豹,史龙,任丰原,无线传感器网络中的自身定位系统和算法[J],软件学报,2005.
[32]李建中,李金宝,石胜飞,传感器网络及其数据管理的概念、问题与进展[J],软件学报,2003,1717-1725.
[33]P.Bahl, V.N.Padmanabhan, RADAR:An in-building RF-based user location and tracking system, In IEEE INFOCOM, Tel Aviv, Isr,2000,775-784.
[34]N.B.Priyantha, A.Chakraborty, H.Balakrishnan, The cricket location-support system, In proceedings of the 6th Annual International Conference on Mobile Computing and Networking,2000,32-43.
[35]XF.Shen, Z.Wang, P.Jiang, Connectivity and RSSI based localization scheme for wireless sensor networks, In Lecture Notes in Computer Science, Hefei, China, 2005,578-587.
[36]T.He, C.Huang, B.Blum, Range-Free Localization Schemes for Large Scale Sensor Networks, In proceedings of the 9th Annual International Conference, on Mobile Computing and Networking,2003,81-95.
[37]C.Laurendeau, M. Barbeau, Centroid Localization of Uncooperative Nodes in Wireless Networks Using a Relative Span Weighting Method, EURASIP Journal on Wireless Communications and Networking,2010,1155-1164.
[38]Xu Y, Heidemann J, Estrin D, Geography-informed energy conservation for ad hoc routing, Proc 7th Annual Int'l Conf on Mobile Computing and Networking, Rome, Italy,2001,70-84.
[39]Want R, Hopper A, Falcao V, Gibbons J, The active badge location system, ACM Trans. on Information Systems,1992,91-102.
[40]Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S, picorodio supports ad hocultra-low power wireless networking,2000,42-48.
[41]Savarese C, Rabaey JM, Beutel J, Locationing in distributed ad-hoc wireless sensor network, In:Proc. of the 2001 IEEE Int'l Conf.on Acoustics, Speech, and Signal. Vol.4, Salt Lake:IEEE Signal Processing Society,2001,2037-2040.
[42]Capkun S, Hamdi M, Hubaux J-P, GPS-Free positioning in mobile ad-hoc networks, Cluster Computing,2002,157-167.
[43]N. Bulusu, J. Heidemann and D. Estrin, Density Adaptive Algorithms for Beacon Placement in Wireless Sensor Networks, In IEEE ICDCS'01, Phoenix, AZ, April 2001.
[44]J. Caffery, Jr. A New Approach to the Geometry of TOA Location, In IEEE Vehicular Technology Conference, Boston,2000.