无线传感器网络中Schnyder路由算法的优化与实现

doi:10.3969/j.issn.1006-2475.2014.10.019

计算机与现代化

无线传感器网络中Schnyder路由算法的优化与实现

南京航空航天大学计算机科学与技术学院,江苏南京210016

收稿日期:2014-07-23 出版日期:2014-11-03 发布日期:2014-11-05
作者简介:孙权(1990-),男,江苏高邮人,南京航空航天大学计算机科学与技术学院硕士研究生,研究方向:航空电子,软件工程,分布式计算; 王立松(1969-),男,副教授,博士,研究方向:航空电子,软件工程,分布式计算,操作系统。
基金资助:
国家重点基础研究发展计划项目(2014CB744900)

Improvement and Implementation on Schnyder Routing Algorithm on Wireless Sensor Networks

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received:2014-07-23 Online:2014-11-03 Published:2014-11-05

摘要/Abstract

摘要： 基于节点虚拟位置的几何路由协议是无线传感器网络研究的一个重要方向。目前，Schnyder路由算法中，当网络拓扑中节点失效时，Schnyder wood的结构被破坏，贪婪条件满足的概率将随着节点失效率的升高而急剧降低，算法已不能保证消息的可达。受现实生活中指南针的启发，本文针对这一问题提出一种新的算法，采用计算源节点分别与下一跳节点和目的节点形成的角度作为选择下一跳节点的依据，称为贪婪指南针双模型路由算法，可以在节点失效较高时仍保证消息的可达。最后，通过实验验证该改进算法可以有效改善几何路由算法中由于节点失效而导致的消息不可达问题。


关键词: 无线传感器网络, 几何路由算法, Schnyder算法, 节点失效

Abstract: The virtual coordinate-based geometric routing protocol is an important direction of research on wireless sensor networks. At present, when the nodes in the network topology failure, the algorithm is no longer applicable because the structure of Schnyder wood was destroyed and the probability of greed condition will decrease sharply with the increasing of node failure rate. Inspired by the compass in real life, a novel algorithm called Greedy-Compass Double Model Routing Algorithm is proposed in order to solve the problem of node failure. The angle is the basic of choice by calculating the source nodes with neighbor nodes and destination node. Finally, an experiment demonstrated that the improved algorithm can effectively solve the node failure problem in geometric routing algorithm.


Key words: wireless sensor networks, geometric routing algorithm, Schnyder algorithm, node failure

中图分类号:

TP301.6

孙权,王立松. 无线传感器网络中Schnyder路由算法的优化与实现[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2014.10.019.

SUN Quan, WANG Li-song. Improvement and Implementation on Schnyder Routing Algorithm on Wireless Sensor Networks[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.10.019.

参考文献

［1］郑锴,童利标,陆文骏. 基于地理位置的无线传感器网络路由协议［J］. 中兴通讯技术, 2008,14(6):37-41.
［2］崔莉,鞠海玲,苗勇,等. 无线传感器网络研究进展［J］. 计算机研究与发展, 2005,42(1):163-174.
［3］张衡阳,李莹莹,刘云辉. 基于地理位置的无线传感器网络路由协议研究进展［J］. 计算机应用研究, 2008,25(1):18-21.
［4］ Karp B, Kung H T. GPSR: Greedy perimeter stateless routing for wireless networks［C］// Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking. Boston, Massachusetts, USA, 2000:243-254.
［5］ Goodrich M T, Strash D. Succinct Greedy Geometric Routing in the Euclidean Plane［EB/OL］. http://arxiv.org/abs/0812.3893, 2009-10-02.
［6］ Takagi H, Kleinrock L. Optimal transmission ranges for randomly 〖JP〗distributed packet radio terminals［J］. IEEE Transactions on Communications,1984,32(3):246-257.［7］刘亮,秦小麟，刘亚丽,等. 顽健的无线传感器网络K近邻查询处理算法［J］. 通信学报. 2010,31(11):171-179.
［8］ Kuhn F, Wattenhofer R, Zhang Y, et al. Geometric Ad-hoc fouting: Of theory and practice［C］// Proceedings of the 22nd ACM Symposium on the Principles on Distributed Computing. 2003:63-72.
［9］胡淼,李剑峰. 车载自组织网络中基于贪婪算法的地理位置路由［J］. 中兴通讯技术, 2011,17(3):24-28.
［10］He Xin, Zhang Huaming. On succinct convex greedy drawing of 3-connected plane graphs［C］// Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 2011:1477-1486.
［11］Dhandapani R. Greedy Drawings of Triangulations［C］// Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 2008:102-111.
［12］Leighton T, Moitra A. Some results on greedy embeddings in metric spaces［C］// Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. 2008:337-346.
［13］Badent M, Brandes U, Cornelsen S. More canonical ordering［J］. Journal of Graph Algorithm and Applications, 2011,15(1):97-126.
［14］Papadimitriou C H, Ratajczak D. On a conjecture related to geometric routing［J］. Theoretical Computer Science, 2005,344(1):3-14.
［15］Angelini P, Battista G D, Frati F. Succinct greedy drawings do not always exist［J］. Networks, 2012,59(3):267-274.
［16］He Xin, Zhang Huaming. Schnyder greedy routing algorithm［C］// Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation. 2010:271-283.
［17］袁正午,李军. 基于虚拟力的无线传感器网络地理位置路由算法［J］. 计算机应用研究, 2009,26(6):2235-2237.
［18］张磊. 基于图嵌入的无线传感器网络几何路由算法研究［D］. 南京:南京航空航天大学, 2011.
［19］Zorzi M, Rao R R. Geographic random forwarding (GeRaF) for Ad hoc and sensor networks: Multihop performance［J］. IEEE Transactions on Mobile Computing, 2003,2(4):337-348.

[1]	赵继业. 基于云安全模型的簇状树形无线传感器网络路由协议 [J]. 计算机与现代化, 2021, 0(08): 6-10.
[2]	张彦虎, 鄢丽娟, 孔淑梅. 一种适用于凹陷型山地地形的无线传感器网络路由算法[J]. 计算机与现代化, 2021, 0(06): 86-90.
[3]	张彦虎, 鄢丽娟. 一种通过剩余能量过滤进行簇头选举的低能耗无线路由算法[J]. 计算机与现代化, 2021, 0(05): 83-87.
[4]	徐家冰, 朱浩辰, 杨丽. 一种基于纠删码的多节点失效修复算法[J]. 计算机与现代化, 2021, 0(03): 18-23.
[5]	马媛, 杜秀娟 . 基于NS3的水下LEER协议优化与分析[J]. 计算机与现代化, 2021, 0(03): 35-40.
[6]	蔡文鹏, 鞠时光. 三维曲面多移动节点的传感器网络部署算法[J]. 计算机与现代化, 2020, 0(11): 70-76.
[7]	张蕾, 崔娟娟, 李晶晶. WSN中基于压缩感知的分簇数据收集算法[J]. 计算机与现代化, 2020, 0(09): 1-5.
[8]	鄢丽娟, 张彦虎. 一种基于平均剩余能量的无线传感器网络分簇路由算法[J]. 计算机与现代化, 2020, 0(07): 16-20.
[9]	孙宗星，蔡丽萍，李世宝. 基于蚁群优化的无线传感器网络最适路由算法[J]. 计算机与现代化, 2017, 0(8): 13-.
[10]	陈芳，赵阳. 基于云计算的移动医疗监控系统[J]. 计算机与现代化, 2017, 0(7): 68-71+90.
[11]	朱世照，薛善良. WSN中一种基于可控能耗的源位置隐私保护协议[J]. 计算机与现代化, 2017, 0(7): 95-100+123.
[12]	董军1，杨秀娟1，付喜辉1，刘付刚2，谢子殿3，张洋3. 无线传感器网络DV-hop定位算法的改进[J]. 计算机与现代化, 2017, 0(5): 15-18,23.
[13]	朱世照，薛善良. 一种WSN中多幻影节点源位置隐私保护协议[J]. 计算机与现代化, 2017, 0(2): 98-104+108.
[14]	董袁泉1，王浩2. 基于离散鸡群压缩感知的WSNs多目标定位[J]. 计算机与现代化, 2017, 0(12): 23-27.
[15]	张岱臣，周丹. 无线传感器网络中基于往返时间的失效节点探测算法[J]. 计算机与现代化, 2016, 0(8): 79-85.

无线传感器网络中Schnyder路由算法的优化与实现

Improvement and Implementation on Schnyder Routing Algorithm on Wireless Sensor Networks

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价