无线传感器网络节点的伪三维定位算法研究
|
摘要
节点定位技术作为无线传感器网络主要支撑技术之一,成为传感器网络领域近年来的一个研究热点。节点自身位置的准确定位是提供监测事件位置信息的基础和前提,对于大多数应用来说,没有位置信息的监测数据是无效的,因此开展无线传感器网络节点定位技术的研究具有十分重要的现实意义。
现有传感器网络三维定位算法一般根据节点间的相对距离、角度及其它相关信息,直接求得节点的三维坐标。这些算法大都存在锚节点密度高、定位精度低和定位覆盖率低的问题。为此本文提出了基于电子地图的伪三维定位算法,具体内容如下:
1)本文将定位过程分为网络初始化时的全局定位和后期部分节点重定位两个阶段,针对这两个阶段提出了两种伪三维定位算法,不同于传统意义上的三维定位算法,伪三维定位算法首先将三维空间内定位问题简化成二维平面内定位问题,从而降低算法的计算复杂度,求得二维坐标后借助电子地图,获得最终三维定位。高精度电子地图的普及为算法的实现提供了保证。
2)在初始的全局定位阶段,本文提出了一种基于地形信息的伪三维定位算法。该算法在对复杂三维环境下网络节点定位时,引入了电子地图和一个移动锚节点,并对锚节点的移动路径进行了规划。仿真结果表明该算法具有锚节点密度低、定位精度高和定位覆盖率高的优点。
3)在移动节点重定位阶段,本文提出了基于APIT的移动节点重定位算法。该算法不需要外部设备的辅助,仅仅利用网络自身已定位节点就可以实现移动节点的重定位。在计算节点可能存在的交集区域时,本文提出了电子地图优化方法。仿真结果表明基于APIT的移动节点重定位算法具有定位时间短和定位成本低的优点。
As a main support technology of wireless sensor network, node localization technology for wireless sensor network has become a hot research topic in recent years. Accurate localization of nodes is basis and premise to provide monitoring events positional information, for most applications, the monitored information without positional information is meaningless, thus the research on wireless sensor network node localization technology is necessary and very important.
The existing three-dimensional localization algorithm for wireless sensor network always compute node’s three-dimensional coordinates directly according to the relative distance, angle and other relevant information between the nodes. Most of them suffer from high computational complexity, low localization precision and error accumulation problems. Thus this thesis proposes electronic map based pseudo three-dimensional localization algorithm for wireless sensor networks, the main content of this thesis are summarized as follows:
1) this thesis divides the process of localization into initial stage of the global positioning and later mobile node re-localization stage, aimed at this two stage this thesis proposes two kinds of pseudo three-dimensional localization algorithm, different from the traditional three-dimensional localization algorithm, pseudo three-dimensional localization algorithm first simplifies a three-dimensional space positioning problem to a 2d in-plane positioning problem, thereby reduces computational complexity of algorithm, calculates two-dimensional coordinate, then completes three-dimensional localization with electronic map. The popularity of high-precision electronic map ensures the implementation of algorithm.
2) In the initial stage of the global positioning, this thesis proposes Topographic Information Based Pseudo Three-Dimensional Localization Algorithm (TIBPTDLA) for wireless sensor networks. In order to realize the complex three-dimensional environment network node localization, TIBPTDLA introduces electronic maps and a mobile anchor node, and plans the moving track of the anchor node. Simulation results show that TIBPTDLA has the advantages of low computational complexity and high localization precision.
3) In the mobile node re-localization stage, this thesis proposes APIT Based Mobile Node Re-localization Algorithm (APITBMNRA) for wireless sensor networks. APITBMNRA does not need external devices auxiliary, just uses the know nodes of the network to achieve re-localization of the mobile node. During the process of calculating intersection regional that the node may exist, this thesis proposes the electronic map optimal method. Simulation results show that APITBMNRA has the advantages of short positioning time, small communication overhead and high localization precision.
现有传感器网络三维定位算法一般根据节点间的相对距离、角度及其它相关信息,直接求得节点的三维坐标。这些算法大都存在锚节点密度高、定位精度低和定位覆盖率低的问题。为此本文提出了基于电子地图的伪三维定位算法,具体内容如下:
1)本文将定位过程分为网络初始化时的全局定位和后期部分节点重定位两个阶段,针对这两个阶段提出了两种伪三维定位算法,不同于传统意义上的三维定位算法,伪三维定位算法首先将三维空间内定位问题简化成二维平面内定位问题,从而降低算法的计算复杂度,求得二维坐标后借助电子地图,获得最终三维定位。高精度电子地图的普及为算法的实现提供了保证。
2)在初始的全局定位阶段,本文提出了一种基于地形信息的伪三维定位算法。该算法在对复杂三维环境下网络节点定位时,引入了电子地图和一个移动锚节点,并对锚节点的移动路径进行了规划。仿真结果表明该算法具有锚节点密度低、定位精度高和定位覆盖率高的优点。
3)在移动节点重定位阶段,本文提出了基于APIT的移动节点重定位算法。该算法不需要外部设备的辅助,仅仅利用网络自身已定位节点就可以实现移动节点的重定位。在计算节点可能存在的交集区域时,本文提出了电子地图优化方法。仿真结果表明基于APIT的移动节点重定位算法具有定位时间短和定位成本低的优点。
As a main support technology of wireless sensor network, node localization technology for wireless sensor network has become a hot research topic in recent years. Accurate localization of nodes is basis and premise to provide monitoring events positional information, for most applications, the monitored information without positional information is meaningless, thus the research on wireless sensor network node localization technology is necessary and very important.
The existing three-dimensional localization algorithm for wireless sensor network always compute node’s three-dimensional coordinates directly according to the relative distance, angle and other relevant information between the nodes. Most of them suffer from high computational complexity, low localization precision and error accumulation problems. Thus this thesis proposes electronic map based pseudo three-dimensional localization algorithm for wireless sensor networks, the main content of this thesis are summarized as follows:
1) this thesis divides the process of localization into initial stage of the global positioning and later mobile node re-localization stage, aimed at this two stage this thesis proposes two kinds of pseudo three-dimensional localization algorithm, different from the traditional three-dimensional localization algorithm, pseudo three-dimensional localization algorithm first simplifies a three-dimensional space positioning problem to a 2d in-plane positioning problem, thereby reduces computational complexity of algorithm, calculates two-dimensional coordinate, then completes three-dimensional localization with electronic map. The popularity of high-precision electronic map ensures the implementation of algorithm.
2) In the initial stage of the global positioning, this thesis proposes Topographic Information Based Pseudo Three-Dimensional Localization Algorithm (TIBPTDLA) for wireless sensor networks. In order to realize the complex three-dimensional environment network node localization, TIBPTDLA introduces electronic maps and a mobile anchor node, and plans the moving track of the anchor node. Simulation results show that TIBPTDLA has the advantages of low computational complexity and high localization precision.
3) In the mobile node re-localization stage, this thesis proposes APIT Based Mobile Node Re-localization Algorithm (APITBMNRA) for wireless sensor networks. APITBMNRA does not need external devices auxiliary, just uses the know nodes of the network to achieve re-localization of the mobile node. During the process of calculating intersection regional that the node may exist, this thesis proposes the electronic map optimal method. Simulation results show that APITBMNRA has the advantages of short positioning time, small communication overhead and high localization precision.
引文
[1] D. Cullar, D. Estrin, M. Strvastava. Overview of Sensor Networks. Computer, 2004, 37(8): page 41-49
[2] http://www.sewing.mixdes.org
[3] http://www.eyes.eu.org
[4]汪炀。无线传感器网络定位技术研究。中国科技大学博士论文。2007年
[5]孙利民,李建中,陈渝等。无线传感器网络(第一版)。清华大学出版社,2005年5月
[6]谢处方,饶克瑾。电磁场与电磁波(第四版),高等教育出版社,2006-1
[7] Seapahn Meguerdichian, Vahag Karayan, Sasa Slijepcevic, et al. Localized Algorithms In Wireless Ad-Hoc Networks: Location Discovery And Sensor Exposure. Published In: MobiHoc '01 Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing , ACM New York, USA 2001
[8] L. Cong, Weihua Zhuang. Non-line-of-sight Error Mitigation In TDOA Mobile Location. Published In: Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE. Vol.1:680-684
[9] Localization in Wireless Sensor Networks. Master's Degree Project Stockholm, Sweden 2005, IR-RT-EX-0523
[10] L. Chong, W. Kui, H. Tian. Sensor Localization With ring Overlapping Based On Comparison of Received Signal Strength Indicator, Published In: Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on. Page: 516-518
[11] Howard Shrobe, Radhika Nagpal and Jonathan Bachrach. Organizing A Global Coordinate System From Local Information On An Ad Hoc Sensor Network. Published in: IPSN'03 Proceedings of the 2nd international conference on Information processing in sensor networks. Berlin, Heidelberg 2003
[12] Wei-Wei Ji, Zhong Liu. An Improvement of DV-Hop Algorithm in Wireless Sensor Networks. Published in: WiCOM 2006 (Wireless Communications Networking and Mobile Computing 2006) International Conference on. 2006. 9. Page: 1
[13] Ning Yu, Jiangwen Wan, Qing Song, et al. An Improved DV-Hop Localization Algorithm inWireless Sensor Networks. Published in: Information Acquisition, 2006 IEEE International Conference on. 2006.8
[14] Jayashree. L. S, Arumugam. S, Anusha. M, et al. On the Accuracy of Centroid Based Multilateration Procedure for Location Discovery in Wireless Sensor Networks. Published in: Wireless and Optical Communications Networks, 2006 IFIP International Conference on. Bangalore. 2006. 8
[15] Kyker. R. Local Positioning System. Published in: Microelectronics Communications Technology Producing Quality Products Mobile and Portable Power Emerging Technologies. WESCON/'95. Conference record
[16] S. Capkun, M. Hamdi, J. Hubaux. GPS-Free Positioning in Mobile ad-hoc Networks. Published in: Proceedings of the 34th HICSS(Annual Hawaii International Conference on System Sciences). Vol. 9. Washington. DC. USA. 2001
[17] Gaetano Borriello, Jeffrey Hightower, Chris Vakili, et al. SpotON: Ad-hoc Location Sensing.
[18] Roy Want, Veronica Falcao, Jon Gibbons. The Active Badge Location System. ACM Transactions on Information Systems
[19] Bahl. P, Padmanabhan. V. N. RADAR: an in-building RF-based user location and tracking system. Published in: Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. INFOCOM 2000. Tel Aviv, Israel. 2000. Vol.2: 775-784
[20] Robert J. Orr, Gregory D. Abowd. The smart floor: A Mechanism for Natural User Identification and Tracking. Published in: CHI '00 extended abstracts on Human factors in computing systems. ACM New York, NY. USA
[21] Guoqiang Mao, Bar?s Fidan and Brian D. O. Anderson. Published in: The International Journal of Computer and Telecommunications Networking. New York, NY, USA. Vol 51. 2007. 9
[22]吕良彬,曹阳,高洵等。基于球壳交集的传感器网络三维定位算法。北京邮电大学学报2006
[23] Gang gang Yu; Fengqi Yu; Lei Feng. A Three Dimensional Localization Algorithm Using a Mobile Anchor Node under Wireless Channel. Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on. 2008 , Page(s): 477 - 483
[24] D. A. Holland, D. S. Boyd, P. Marshall. Updating Topographic Mapping in Great BritainUsing Imagery from High-resolution Satellite Sensors. ISPRS Journal of Photogrammetry and Remote Sensing. Vol.60: 212-223
[25] K Kim, W Lee. MBAL: A Mobile Beacon-assisted Localization Scheme for Wireless Sensor Networks. Proceeding of the l6th International Conference on Computer Communications and Networks. Hawaii. 2007.Page: 57-62
[26] Sichitiu, M. L, Ramadurai. V. Localization of Wireless Sensor Networks with a Mobile Beacon. Published in: Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on. Page: 174-183
[27] Kuo-Feng Ssu, Chia-Ho Ou, Jiau H. C. Localization with mobile anchor points in wireless sensor networks, Vehicular Technology. Published in: Vehicular Technology, IEEE Transactions on. Vol .54: 1187 - 1197
[28] Koutsonilas D, Das S. M, Hu Y. C. Path planning of mobile landmarks for localization in wireless sensor networks. Published in: Distributed Computing Systems Workshops, 2006. ICDCS Workshops 2006. 26th IEEE International Conference on. Page(s): 86
[29] T. He, C. Huang, B. M. Blum, et all. Range-free localization schemes for large scale sensor networks. Published in: Proceedings of the ninth annual international conference on Mobile computing and networking, San Diego, California, September 2003, Pages 81-95
[2] http://www.sewing.mixdes.org
[3] http://www.eyes.eu.org
[4]汪炀。无线传感器网络定位技术研究。中国科技大学博士论文。2007年
[5]孙利民,李建中,陈渝等。无线传感器网络(第一版)。清华大学出版社,2005年5月
[6]谢处方,饶克瑾。电磁场与电磁波(第四版),高等教育出版社,2006-1
[7] Seapahn Meguerdichian, Vahag Karayan, Sasa Slijepcevic, et al. Localized Algorithms In Wireless Ad-Hoc Networks: Location Discovery And Sensor Exposure. Published In: MobiHoc '01 Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing , ACM New York, USA 2001
[8] L. Cong, Weihua Zhuang. Non-line-of-sight Error Mitigation In TDOA Mobile Location. Published In: Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE. Vol.1:680-684
[9] Localization in Wireless Sensor Networks. Master's Degree Project Stockholm, Sweden 2005, IR-RT-EX-0523
[10] L. Chong, W. Kui, H. Tian. Sensor Localization With ring Overlapping Based On Comparison of Received Signal Strength Indicator, Published In: Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on. Page: 516-518
[11] Howard Shrobe, Radhika Nagpal and Jonathan Bachrach. Organizing A Global Coordinate System From Local Information On An Ad Hoc Sensor Network. Published in: IPSN'03 Proceedings of the 2nd international conference on Information processing in sensor networks. Berlin, Heidelberg 2003
[12] Wei-Wei Ji, Zhong Liu. An Improvement of DV-Hop Algorithm in Wireless Sensor Networks. Published in: WiCOM 2006 (Wireless Communications Networking and Mobile Computing 2006) International Conference on. 2006. 9. Page: 1
[13] Ning Yu, Jiangwen Wan, Qing Song, et al. An Improved DV-Hop Localization Algorithm inWireless Sensor Networks. Published in: Information Acquisition, 2006 IEEE International Conference on. 2006.8
[14] Jayashree. L. S, Arumugam. S, Anusha. M, et al. On the Accuracy of Centroid Based Multilateration Procedure for Location Discovery in Wireless Sensor Networks. Published in: Wireless and Optical Communications Networks, 2006 IFIP International Conference on. Bangalore. 2006. 8
[15] Kyker. R. Local Positioning System. Published in: Microelectronics Communications Technology Producing Quality Products Mobile and Portable Power Emerging Technologies. WESCON/'95. Conference record
[16] S. Capkun, M. Hamdi, J. Hubaux. GPS-Free Positioning in Mobile ad-hoc Networks. Published in: Proceedings of the 34th HICSS(Annual Hawaii International Conference on System Sciences). Vol. 9. Washington. DC. USA. 2001
[17] Gaetano Borriello, Jeffrey Hightower, Chris Vakili, et al. SpotON: Ad-hoc Location Sensing.
[18] Roy Want, Veronica Falcao, Jon Gibbons. The Active Badge Location System. ACM Transactions on Information Systems
[19] Bahl. P, Padmanabhan. V. N. RADAR: an in-building RF-based user location and tracking system. Published in: Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. INFOCOM 2000. Tel Aviv, Israel. 2000. Vol.2: 775-784
[20] Robert J. Orr, Gregory D. Abowd. The smart floor: A Mechanism for Natural User Identification and Tracking. Published in: CHI '00 extended abstracts on Human factors in computing systems. ACM New York, NY. USA
[21] Guoqiang Mao, Bar?s Fidan and Brian D. O. Anderson. Published in: The International Journal of Computer and Telecommunications Networking. New York, NY, USA. Vol 51. 2007. 9
[22]吕良彬,曹阳,高洵等。基于球壳交集的传感器网络三维定位算法。北京邮电大学学报2006
[23] Gang gang Yu; Fengqi Yu; Lei Feng. A Three Dimensional Localization Algorithm Using a Mobile Anchor Node under Wireless Channel. Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on. 2008 , Page(s): 477 - 483
[24] D. A. Holland, D. S. Boyd, P. Marshall. Updating Topographic Mapping in Great BritainUsing Imagery from High-resolution Satellite Sensors. ISPRS Journal of Photogrammetry and Remote Sensing. Vol.60: 212-223
[25] K Kim, W Lee. MBAL: A Mobile Beacon-assisted Localization Scheme for Wireless Sensor Networks. Proceeding of the l6th International Conference on Computer Communications and Networks. Hawaii. 2007.Page: 57-62
[26] Sichitiu, M. L, Ramadurai. V. Localization of Wireless Sensor Networks with a Mobile Beacon. Published in: Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on. Page: 174-183
[27] Kuo-Feng Ssu, Chia-Ho Ou, Jiau H. C. Localization with mobile anchor points in wireless sensor networks, Vehicular Technology. Published in: Vehicular Technology, IEEE Transactions on. Vol .54: 1187 - 1197
[28] Koutsonilas D, Das S. M, Hu Y. C. Path planning of mobile landmarks for localization in wireless sensor networks. Published in: Distributed Computing Systems Workshops, 2006. ICDCS Workshops 2006. 26th IEEE International Conference on. Page(s): 86
[29] T. He, C. Huang, B. M. Blum, et all. Range-free localization schemes for large scale sensor networks. Published in: Proceedings of the ninth annual international conference on Mobile computing and networking, San Diego, California, September 2003, Pages 81-95