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

doi:10.3969/j.issn.1006-2475.2014.10.019

Abstract

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

CLC Number:

TP301.6

SUN Quan, WANG Li-song. Improvement and Implementation on Schnyder Routing Algorithm on Wireless Sensor Networks[J]. Computer and Modernization, 2014, 0(10): 81-84,91.

References

［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]	JI Ping, GUO Ying. Underwater Localization Algorithm of Range Correction Based on Long Short-Term Memory [J]. Computer and Modernization, 2022, 0(02): 52-57.
[2]	ZHANG Yan-hu, YAN Li-juan, KONG Shu-mei. A Routing Algorithm for Wireless Sensor Networks in Concave Mountain Terrain [J]. Computer and Modernization, 2021, 0(06): 86-90.
[3]	XU Jia-bing, ZHU Hao-chen, YANG Li. Multi-node Failure Repair Algorithm Based on Erasure Code [J]. Computer and Modernization, 2021, 0(03): 18-23.
[4]	YAN Li-juan, ZHANG Yan-hu. An Average Residual Energy Based Clustering Routing Algorithm for Wireless Sensor Networks [J]. Computer and Modernization, 2020, 0(07): 16-20.
[5]	YI Wen-zhou. Improved WSN Coverage Algorithms Based on Differential Evolution #br# and Particle Swarm Optimization [J]. Computer and Modernization, 2019, 0(08): 33-.
[6]	SUN Zongxing， CAI Liping， LI Shibao. An Optimum Routing Algorithm for Wireless Sensor Networks #br# Based on Ant Colony Optimization [J]. Computer and Modernization, 2017, 0(8): 13-.
[7]	WANG Liuqing， NI Wei， WANG Wei， ZHONG Qun. An Acetone Gas Monitoring System Based on ZigBee Wireless Sensor Network [J]. Computer and Modernization, 2017, 0(3): 106-.
[8]	DONG Yuan-quan1, WANG Hao2. Multiple Target Localizationin WSNs via CS Reconstruction Method Based on Discrete CSO Algorithm [J]. Computer and Modernization, 2017, 0(12): 23-27.
[9]	LIANG Chuan， TENG Cui. Efficient Secure Data Aggregation Protocol on Wireless Sensor Networks [J]. Computer and Modernization, 2016, 0(5): 122-126.
[10]	LI Peiyu, ZHANG Zhixue. A Scalable Encryption Routing Protocol for Privacy Preserving on Sensor Networks [J]. Computer and Modernization, 2015, 0(7): 34-.
[11]	XU Jian-zhen, CAO Huan-huan, SONG Ai-ling. Linked Hierarchical Routing Protocol Based on Access Control [J]. Computer and Modernization, 2015, 0(4): 14-19.
[12]	ZHANG Hui. An Improved GAPSO Algorithm for Wireless Sensor Network Routing [J]. Computer and Modernization, 2015, 0(12): 31-.
[13]	LI Qun. Hardware Dynamic Behavior Assessing of WSN and Semi-passive RFID Tags in Temperature Monitoring System [J]. Computer and Modernization, 2015, 0(10): 83-87.
[14]	LI Chang-ying1, ZHENG Yong-meng2, GU Yu-kui3. A Novel Wireless Sensor Networks Architecture Based on Mobile P2P Platform [J]. Computer and Modernization, 2014, 0(6): 22-26.
[15]	ZHENG Bo， CUI Bao-tong. A Routing Protocol for Wireless Sensor Networks Based on CPSO-z [J]. Computer and Modernization, 2014, 0(6): 36-39,48.