具有移动节点的无线传感器网络定位算法研究
|
摘要
无线传感器网络中,节点定位具有极其重要的地位。在大多数应用中,节点知道自己的坐标位置可以带来许多便捷。一般情况下,无线传感器网络中的节点是通过飞机撒播等方式随机部署在危险地带或者人类难以到达的区域。随机部署的方式和数量庞大的节点数注定了其位置无法事先确定,需要通过定位算法获得。节点获得正确的坐标位置不仅可以为实际应用提供有效地服务,如目标实时跟踪和监测、兴趣事件汇报、目标的轨迹预测等等,还可以协助路由,提高路由的效率,进一步实现网络的负载均衡,延长网络的生命周期。因此,无线传感器网络节点定位算法非常重要,在无线传感器网络实际应用中起着关键的作用。
本文研究具有移动节点的无线传感器网络定位算法,即引入一个可移动的信标节点,主动的提供未知节点适当的虚拟信标节点坐标。这样不仅可以减少部署较多的昂贵的静止信标节点,而且移动信标节点可以直接同未知节点通信,从而提高定位精度。
本文提出了两种具有移动节点的无线传感器网络定位算法,一种是基于改进的Random Waypoint移动模型的无线传感器网络定位算法。在改进的Random Waypoint移动模型中,我们对移动模型的每次移动的时间进行了限制,预先设定了移动时间阈值tth。我们分别比较了不同的未知节点数、移动信标节点速度、移动时间阈值tth对LARW定位算法精度的影响。另一种是基于空间填充曲线的移动信标节点定位算法。本文在对应章节对这两种算法做了详细的介绍。
In recent years, with the progress of radio and microelectronics technology, miniature sensor industry has also developed rapidly. Meanwhile, the research about wireless sensor network (WSN) attracts extensive attention. The WSN can be arranged in a broad area and be used to monitor the environmental parameter, for example, pressure, temperature, humidity and so on. But if we don't know the position corresponding to these parameters, it will be meaningless to obtain these parameters. So node positioning technology itself becomes one of the keying technologies of wireless sensor network.
Localization is very important for wireless sensor networks. Since the surveillance area is usually a dangerous area or a hostile area, node location is usually random and unknown. Sensor node must clear their own position in order to provide the incident occurred sites, and target tracking, real-time monitoring and forecast goal line, realizing such external locus of localization and tracking targets.
On the other hand, sensor node location information can also assist routing and improve the efficiency of routing and so on. Therefore, node location is rather important.
This master research localization algorithm based on mobile node for wireless sensor networks. Mobile node can provide virtual anchor coordinates, which is not only decrease the number of static anchors, but also increase localization accuracy. This master proposes two localization algorithms. One is a Localization Algorithm for Wireless Sensor Networks based on Improved Random Waypoint Mobility Model; the other is a Mobile Anchor Localization Algorithm based on Hilbert Space Filling Curve. This master describes these algorithms in detail in corresponding sections.
本文研究具有移动节点的无线传感器网络定位算法,即引入一个可移动的信标节点,主动的提供未知节点适当的虚拟信标节点坐标。这样不仅可以减少部署较多的昂贵的静止信标节点,而且移动信标节点可以直接同未知节点通信,从而提高定位精度。
本文提出了两种具有移动节点的无线传感器网络定位算法,一种是基于改进的Random Waypoint移动模型的无线传感器网络定位算法。在改进的Random Waypoint移动模型中,我们对移动模型的每次移动的时间进行了限制,预先设定了移动时间阈值tth。我们分别比较了不同的未知节点数、移动信标节点速度、移动时间阈值tth对LARW定位算法精度的影响。另一种是基于空间填充曲线的移动信标节点定位算法。本文在对应章节对这两种算法做了详细的介绍。
In recent years, with the progress of radio and microelectronics technology, miniature sensor industry has also developed rapidly. Meanwhile, the research about wireless sensor network (WSN) attracts extensive attention. The WSN can be arranged in a broad area and be used to monitor the environmental parameter, for example, pressure, temperature, humidity and so on. But if we don't know the position corresponding to these parameters, it will be meaningless to obtain these parameters. So node positioning technology itself becomes one of the keying technologies of wireless sensor network.
Localization is very important for wireless sensor networks. Since the surveillance area is usually a dangerous area or a hostile area, node location is usually random and unknown. Sensor node must clear their own position in order to provide the incident occurred sites, and target tracking, real-time monitoring and forecast goal line, realizing such external locus of localization and tracking targets.
On the other hand, sensor node location information can also assist routing and improve the efficiency of routing and so on. Therefore, node location is rather important.
This master research localization algorithm based on mobile node for wireless sensor networks. Mobile node can provide virtual anchor coordinates, which is not only decrease the number of static anchors, but also increase localization accuracy. This master proposes two localization algorithms. One is a Localization Algorithm for Wireless Sensor Networks based on Improved Random Waypoint Mobility Model; the other is a Mobile Anchor Localization Algorithm based on Hilbert Space Filling Curve. This master describes these algorithms in detail in corresponding sections.
引文
[1]Mark Weiser. The Computer for the Twenty-First Century. Scientific American,1991, 94～10
[2]王帅.无线传感器网络测距无关的节点定位算法研究[D].山东：山东大学,2010.
[3]Akyildiz F, et al. Wireless sensor networks:a survey. Computer Networks,2002,38(1): 393-422
[4]孙利明,李建中等.无线传感器网络.北京：清华大学出版社,2005,9-20
[5]Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):1148～1157
[6]陈希军.一类无线传感器网络嵌入式操作系统及其节点定位的关键技术研究[D].安徽：中国科技大学,2010.
[7]陈娟.基于移动信标的无线传感器网络定位算法研究[D].湖南：中南大学,2009.
[8]Xu N, Sumit R W, Chintalapudi, K K, et al. A wireless sensor network for structural monitoring. In:Proceedings of 2nd International Conference on Embedded Networked Sensor Systems,2004,13-24.
[9]郑国强,李建东,李红艳等.多跳无线传感器网络的高效中继节点快速选择算法[J].通信学报,2010,31(11)：158-170.
[10]Ong K G, Yang X P, Niloy M, et al. A wireless sensor network for long-term monitoring of aquatic environments:desgn and implementation.2004,2(1):48～57
[11]Ossama Y, Marwan K, Srinivasan R. Node clustering in wireless sensor networks: recent developments and deployment challenges, IEEE Network,2006
[12]Sanchez M, Manzoni P. Anejos:a java based simulator for ad-hoc networks. Future Generation Computer Systems,2001,17(5):573～583
[13]Davies V. Evaluating mobility models within an ad hoc network:[Master master]. USA:Colorado School of Mines,2000
[14]Weisstein E W. The CRC concise encyclopedia of mathematics. CRC Press,1998
[15]Bar-Noy A, Kessler I, Sidi M. Mobile users:to update or not to update? In: Proceedings of the Joint Conference of IEEE Computer and Communications Societies, 1994,570～576
[16]Garcia-Luna-Aceves JJ, Madrga E L. A multicast routing protocol for ad hoc networks. In:Proceedings of the Joint Conference of IEEE Computer and Communications Societies. 1999,784～792
[17]Rubin I, Choi C. Impact of the location area structure on the performance of signaling channels in wireless cellular networks. IEEE Communications Magazine,1997,108～115
[18]Zonoozi M, Dasanayake P. User mobility modeling and characterization of mobility pattern. IEEE Journal on Selected Areas in Communications,1997,15(7):1239～1252
[19]Johnson D, Maltz D. Dynamic source routing in ad hoc wireless networks. Mobile Computing, Kluwer Academic Publishers,1996,153～181
[20]Broch J, Maltz D, Johnson D, et al. Multi-hop wireless ad hoc network routing protocols. In:Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking,1998,85～97
[21]Chiang C, Gerla M. On-demand multicast in mobile wireless networks. In: Proceedings of IEEE International Conference on Network Protocols,1998
[22]Garcia-Luna-Aceves J J, Spohn M. Source-tree routing in wireless networks. In: Proceedings of 7th International Conference on Network Protocols,1999
[23]Johansson P, Larsson T, Hedman N, et al. Routing protocols for mobile ad hoc networks:a comparative performance analysis. In:Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking,1999,195～206
[24]Royer E, Melliar-Smith P M, Moser L. An analysis of the optimum node density for ad hoc mobile networks. In:Proceedings of IEEE International Conference on Communications,2001
[25]Haas Z. A new routing protocol for reconfigurable wireless networks. In:Proceedings of IEEE International Conference on Universal Personal Communications,1997,562～565
[26]Liang B, Haas Z. Predictive distance-based mobility management for PCS networks. In:Proceedings of the Joint Conference of IEEE Computer and Communications Societies, 1999
[27]Tolety V. Load reuction in ad hoc networks using mobile servers. Master's thesis, Colorodo School of Mines,1999
[28]Davies V. Evaluating mobility models within an ad hoc network. Master's thesis, Colorado School of Mines,2000
[29]范嘉携.基于无线传感器网络的声源定位系统的设计与实现[D].上海：上海交通大学,2010.
[30]黄大庆,诸燕平.一种无线传感器网络自身节点定位算法[J].华中科技大学学报(自然科学版),2010,38(10)：80-84.
[31]张晓平,刘桂雄,周松斌.利用最小二乘支持向量机实现无线传感器网络的目标定位[J].光学精密工程,2010,18(9)：2060-2068.
[32]袁风鹏.无需测距的无线传感器网络定位算法研究[D].上海：上海交通大学,2010.
[33]Savvides A, Park H, Srivastava M. The bits and flops of the N-hop multilateration primitive for node localization problems. In:Proceedings of 1st ACM International Workshop on Wireless Sensor Networks and Application.2002,112～121
[34]刑明彦.基于粒子群优化的无线传感器网络节点定位算法研究[D].武汉：武汉理工大学,2010
[35]李辉.无线传感器网络节点定位技术的研究[D].武汉：武行理工大学,2010.
[36]Savarese C, Rabaey J M, Beutel J. Locationing in istributed ad-hoc wireless sensor network. In:Proceedings of IEEE International Conference on Acoustics, Speech, and Signal.2001,2037～2040
[37]赵丽娜.无线传感器网络中基于三边算法的气体源定位研究[D].黑龙江：黑龙江大学,2010.
[38]刘继旺.井下复杂环境中无线传感器网络节点定位算法的研究[D].安徽：安徽大学,2010.
[39]刘影,钱志鸿,刘丹等.基于几何学的无线传感器网络定位算法[J].光电子激光,2010,21(10)：1435-1438.
[40]Bergamo P, Mazzini G. Localization in sensor networks with fading and mobility. In: Proceedings of the 13th IEEE International Conference on Personal, Indoor and Mobile Radio Communications.2002,2:7(5):0～7
[41]郭海琦.基于ZigBee的无线传感器网络定位算法的研究与应用[D].成都：西南交通大学,2010.
[42]杨斌.基于RSSI值的无线传感器网络三维定位算法的研究[D].山东：山东大学,2010.
[43]He T, Huang C, Blum B M, et al. Range-free localization schemes for large scale sensor networks. In:Proceedings of IEEE on Mobile Ad Hoc Networking & Computing, 2003,81～95
[44]Nagpal R. Organizing a global coordinate system from local information on an amporphous computer. AI Memo 1666, MIT AI Laboratory, August 1999
[45]石为人,许磊,徐扬生.一种基于移动信标节点的静态无线传感器网络定位算法.仪器仪表学报,2007,28(3)：385-393
[46]张正勇,孙智,王刚等.基于移动信标节点的无线传感器网络节点定位.清华大学学报(自然科学版),2007,47(4)：534-537
[47]邓宏彬,贾云得,刘书华等.一种基于无线传感器网络的星球漫游机器人定位算法.机器人(ROBOT).2007,29(4)：384-388
[48]赵欢,马颖,罗娟等.无线传感器网络的移动节点定位算法研究[J].湖南大学学报(自然科学版).2007,34(8：74-77
[49]沙超,王汝传,孙力娟等.无线传感器网络中一种信标节点可迁移的协作定位方法[J].电子学报,2010,38(11)：2625-2629
[50]曾明,危阜胜,陈冠升等.面向目标跟踪的WSN协同调度策略及定位[J].华南理工大学学报(自然科学版),2010,38(6)：60-65.
[51]喻钦.基于协作模式的移动无线传感器网络节点定位方法研究[D].武汉：武行理工大学,2010.
[52]孙言强,王晓东,周兴铭.无线传感器网络中基于几何覆盖的Jamming攻击定位算法[J].2010,31(11)：10-16.
[53]孙燕,尚军亮,刘三阳.基于采样优化的蒙特卡洛移动节点定位算法[J].2010,32(9)：2001-2004.
[54]朱剑,赵海,徐久强等.WSNs中一种新颖的模糊识别定位技术研究[J].电子学报,2010,38(8)：1845-1851.
[55]梁甲金.基于移动锚节点的无线传感器网络定位技术研究[D].成都：西南交通大学,2010.
[56]张怀坤.基于传送树的无线传感器网络移动目标定位跟踪技术研究[D].成都：西南交通大学,2010.
[57]Niculescu D, Nath B. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems.2003,22(4):267-280.
[58]张倩.基于TinyOS的无线传感器网路路由协议设计与实现[D].西北：西北工业大学,2006,3
[59]李磬,叶明等.OPNET Modeler网络建模与仿真.西安：西安电子科技大学出版社,2006
[60]孙屹,孟晨.OPNET通信仿真开发手册.北京：国防工业出版社,2005
[61]Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering properties of the Hilbert space filling curve. IEEE Transactions on Knowledge and Data Engineering.2001, 13(1):124～141
[62]Jensen C S, Lin D, Ooi B C. Query and update efficient B+tree based indexing of moving objects. In:Proceedings of international conference on Very large data bases,2004, 768～779
[63]Lawder J K, King P J H. Using space filling curves for multi-dimensional indexing. Lectures in Computer Science,2000,1832(11):20-35
[64]Sichitiu M L, Ramadurai V. Localization of wireless sensor networks with a mobile anchor. In:Proceedings of the 1st IEEE Conference on Mobile Ad-hoc and Sensor Systems. 2004
[2]王帅.无线传感器网络测距无关的节点定位算法研究[D].山东：山东大学,2010.
[3]Akyildiz F, et al. Wireless sensor networks:a survey. Computer Networks,2002,38(1): 393-422
[4]孙利明,李建中等.无线传感器网络.北京：清华大学出版社,2005,9-20
[5]Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):1148～1157
[6]陈希军.一类无线传感器网络嵌入式操作系统及其节点定位的关键技术研究[D].安徽：中国科技大学,2010.
[7]陈娟.基于移动信标的无线传感器网络定位算法研究[D].湖南：中南大学,2009.
[8]Xu N, Sumit R W, Chintalapudi, K K, et al. A wireless sensor network for structural monitoring. In:Proceedings of 2nd International Conference on Embedded Networked Sensor Systems,2004,13-24.
[9]郑国强,李建东,李红艳等.多跳无线传感器网络的高效中继节点快速选择算法[J].通信学报,2010,31(11)：158-170.
[10]Ong K G, Yang X P, Niloy M, et al. A wireless sensor network for long-term monitoring of aquatic environments:desgn and implementation.2004,2(1):48～57
[11]Ossama Y, Marwan K, Srinivasan R. Node clustering in wireless sensor networks: recent developments and deployment challenges, IEEE Network,2006
[12]Sanchez M, Manzoni P. Anejos:a java based simulator for ad-hoc networks. Future Generation Computer Systems,2001,17(5):573～583
[13]Davies V. Evaluating mobility models within an ad hoc network:[Master master]. USA:Colorado School of Mines,2000
[14]Weisstein E W. The CRC concise encyclopedia of mathematics. CRC Press,1998
[15]Bar-Noy A, Kessler I, Sidi M. Mobile users:to update or not to update? In: Proceedings of the Joint Conference of IEEE Computer and Communications Societies, 1994,570～576
[16]Garcia-Luna-Aceves JJ, Madrga E L. A multicast routing protocol for ad hoc networks. In:Proceedings of the Joint Conference of IEEE Computer and Communications Societies. 1999,784～792
[17]Rubin I, Choi C. Impact of the location area structure on the performance of signaling channels in wireless cellular networks. IEEE Communications Magazine,1997,108～115
[18]Zonoozi M, Dasanayake P. User mobility modeling and characterization of mobility pattern. IEEE Journal on Selected Areas in Communications,1997,15(7):1239～1252
[19]Johnson D, Maltz D. Dynamic source routing in ad hoc wireless networks. Mobile Computing, Kluwer Academic Publishers,1996,153～181
[20]Broch J, Maltz D, Johnson D, et al. Multi-hop wireless ad hoc network routing protocols. In:Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking,1998,85～97
[21]Chiang C, Gerla M. On-demand multicast in mobile wireless networks. In: Proceedings of IEEE International Conference on Network Protocols,1998
[22]Garcia-Luna-Aceves J J, Spohn M. Source-tree routing in wireless networks. In: Proceedings of 7th International Conference on Network Protocols,1999
[23]Johansson P, Larsson T, Hedman N, et al. Routing protocols for mobile ad hoc networks:a comparative performance analysis. In:Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking,1999,195～206
[24]Royer E, Melliar-Smith P M, Moser L. An analysis of the optimum node density for ad hoc mobile networks. In:Proceedings of IEEE International Conference on Communications,2001
[25]Haas Z. A new routing protocol for reconfigurable wireless networks. In:Proceedings of IEEE International Conference on Universal Personal Communications,1997,562～565
[26]Liang B, Haas Z. Predictive distance-based mobility management for PCS networks. In:Proceedings of the Joint Conference of IEEE Computer and Communications Societies, 1999
[27]Tolety V. Load reuction in ad hoc networks using mobile servers. Master's thesis, Colorodo School of Mines,1999
[28]Davies V. Evaluating mobility models within an ad hoc network. Master's thesis, Colorado School of Mines,2000
[29]范嘉携.基于无线传感器网络的声源定位系统的设计与实现[D].上海：上海交通大学,2010.
[30]黄大庆,诸燕平.一种无线传感器网络自身节点定位算法[J].华中科技大学学报(自然科学版),2010,38(10)：80-84.
[31]张晓平,刘桂雄,周松斌.利用最小二乘支持向量机实现无线传感器网络的目标定位[J].光学精密工程,2010,18(9)：2060-2068.
[32]袁风鹏.无需测距的无线传感器网络定位算法研究[D].上海：上海交通大学,2010.
[33]Savvides A, Park H, Srivastava M. The bits and flops of the N-hop multilateration primitive for node localization problems. In:Proceedings of 1st ACM International Workshop on Wireless Sensor Networks and Application.2002,112～121
[34]刑明彦.基于粒子群优化的无线传感器网络节点定位算法研究[D].武汉：武汉理工大学,2010
[35]李辉.无线传感器网络节点定位技术的研究[D].武汉：武行理工大学,2010.
[36]Savarese C, Rabaey J M, Beutel J. Locationing in istributed ad-hoc wireless sensor network. In:Proceedings of IEEE International Conference on Acoustics, Speech, and Signal.2001,2037～2040
[37]赵丽娜.无线传感器网络中基于三边算法的气体源定位研究[D].黑龙江：黑龙江大学,2010.
[38]刘继旺.井下复杂环境中无线传感器网络节点定位算法的研究[D].安徽：安徽大学,2010.
[39]刘影,钱志鸿,刘丹等.基于几何学的无线传感器网络定位算法[J].光电子激光,2010,21(10)：1435-1438.
[40]Bergamo P, Mazzini G. Localization in sensor networks with fading and mobility. In: Proceedings of the 13th IEEE International Conference on Personal, Indoor and Mobile Radio Communications.2002,2:7(5):0～7
[41]郭海琦.基于ZigBee的无线传感器网络定位算法的研究与应用[D].成都：西南交通大学,2010.
[42]杨斌.基于RSSI值的无线传感器网络三维定位算法的研究[D].山东：山东大学,2010.
[43]He T, Huang C, Blum B M, et al. Range-free localization schemes for large scale sensor networks. In:Proceedings of IEEE on Mobile Ad Hoc Networking & Computing, 2003,81～95
[44]Nagpal R. Organizing a global coordinate system from local information on an amporphous computer. AI Memo 1666, MIT AI Laboratory, August 1999
[45]石为人,许磊,徐扬生.一种基于移动信标节点的静态无线传感器网络定位算法.仪器仪表学报,2007,28(3)：385-393
[46]张正勇,孙智,王刚等.基于移动信标节点的无线传感器网络节点定位.清华大学学报(自然科学版),2007,47(4)：534-537
[47]邓宏彬,贾云得,刘书华等.一种基于无线传感器网络的星球漫游机器人定位算法.机器人(ROBOT).2007,29(4)：384-388
[48]赵欢,马颖,罗娟等.无线传感器网络的移动节点定位算法研究[J].湖南大学学报(自然科学版).2007,34(8：74-77
[49]沙超,王汝传,孙力娟等.无线传感器网络中一种信标节点可迁移的协作定位方法[J].电子学报,2010,38(11)：2625-2629
[50]曾明,危阜胜,陈冠升等.面向目标跟踪的WSN协同调度策略及定位[J].华南理工大学学报(自然科学版),2010,38(6)：60-65.
[51]喻钦.基于协作模式的移动无线传感器网络节点定位方法研究[D].武汉：武行理工大学,2010.
[52]孙言强,王晓东,周兴铭.无线传感器网络中基于几何覆盖的Jamming攻击定位算法[J].2010,31(11)：10-16.
[53]孙燕,尚军亮,刘三阳.基于采样优化的蒙特卡洛移动节点定位算法[J].2010,32(9)：2001-2004.
[54]朱剑,赵海,徐久强等.WSNs中一种新颖的模糊识别定位技术研究[J].电子学报,2010,38(8)：1845-1851.
[55]梁甲金.基于移动锚节点的无线传感器网络定位技术研究[D].成都：西南交通大学,2010.
[56]张怀坤.基于传送树的无线传感器网络移动目标定位跟踪技术研究[D].成都：西南交通大学,2010.
[57]Niculescu D, Nath B. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems.2003,22(4):267-280.
[58]张倩.基于TinyOS的无线传感器网路路由协议设计与实现[D].西北：西北工业大学,2006,3
[59]李磬,叶明等.OPNET Modeler网络建模与仿真.西安：西安电子科技大学出版社,2006
[60]孙屹,孟晨.OPNET通信仿真开发手册.北京：国防工业出版社,2005
[61]Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering properties of the Hilbert space filling curve. IEEE Transactions on Knowledge and Data Engineering.2001, 13(1):124～141
[62]Jensen C S, Lin D, Ooi B C. Query and update efficient B+tree based indexing of moving objects. In:Proceedings of international conference on Very large data bases,2004, 768～779
[63]Lawder J K, King P J H. Using space filling curves for multi-dimensional indexing. Lectures in Computer Science,2000,1832(11):20-35
[64]Sichitiu M L, Ramadurai V. Localization of wireless sensor networks with a mobile anchor. In:Proceedings of the 1st IEEE Conference on Mobile Ad-hoc and Sensor Systems. 2004
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |