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

计 算 机 与 现 代 化 2014年第 10期 JISUANJIYUXIANDAIHUA 总第230期 文章编号 ：1006—2475(2014)10-0081-04 无线传感器网络中Sehnyder路 由算法的优化与实现 孙 权 ，王立松 (南京航空航天大学计算机科学与技术学院，江苏 南京 210016) 摘要：基于节点虚拟位置的几何路 由协议是无线传感器网络研究的一个重要方向。目前，Schnyder路 由算法中，当网络 拓扑中节点失效时，Sehnyderwood的结构被破坏 ，贪婪条件满足的概率将随着节点失效率的升高而急剧降低，算法已不 能保证消息的可达。受现实生活中指南针的启发，本文针对这一问题提 出一种新的算法，采用计算源节点分别与下一跳 节点和 目的节点形成的角度作为选择下一跳节点的依据，称为贪婪指南针双模型路由算法，可以在节点失效较 高时仍保 证消息的可达。最后，通过实验验证该改进算法可以有效改善几何路由算法中由于节点失效而导致的消息不可达问题。 关键词 ：无线传感器网络；几何路由算法；Schnyder算法；节点失效 中图分类号：FP301．6 文献标识码：A doi：10．3969／j．issn．1006-2475．2014．10．019 Improvementand ImplementationonSchnyderRoutingAlgorithm onW irelessSensorNetworks SUNQ．an，WANGLi—song (Collegeoi’ComputerScieneeandTechnology，NanjingUniversityofAeronauticsandAstronautics，Nanjing210016；China) Abstract：Thevirtualcoordinate—based geometricroutingprotocolisanimportantdirection ofresearchonwirelesssensornet- works．Atpresent，whenthenodesinthenetworktopologyfailure，thealgorithm isnolongerapplicablebecausethestructureof Schnyderwoodwasdestroyedandtheprobabilityofgreedconditionwi11decreasesharplywiththeincreasingofnodefailurerate． Inspiredbythecompassinreallife，anovelalgorithm calledGreedy—CompassDoubleModelRoutingAlgorithm isproposedinor- dertosolvetheproblem ofnodefailure．Theangleisthebasicofclmicebycalculatingthesourcenodeswithneighbornodesand destinationnode．Finally，anexperimentdemnnstratedthattheimprovedalgorithm caneffectivelysolvethenodefailureproblem ingeometricroutingalgorithm． Keywords：wirelesssensornetworks；geometricroutingalgorithm；Schnyderalgorithm；nodefailure 多挑战中，节能算法和路由协议的设计至关重要。 0 引 言 目前对于无线传感器网络几何路由研究可按照 无 线 传 感