贪婪协议路由代数及其应用  

Greedy Routing Algebra and its Applications

作　　者：侯孟书[1] 李玉军[1] 卢显良[1] 任立勇[1] 屈鸿[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《小型微型计算机系统》2011年第9期1827-1831,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60905037)资助;电子科技大学校青年重点基金项目(L08010601JX0808)资助

摘　　要：在无线网络路由协议中,错误地使用路由尺度会降低网络的路由性能,甚至会导致某些节点之间根本无法正常通信,称为路由尺度的兼容性问题.基于路由代数理论,分析了贪婪协议中路由尺度的兼容性问题,推导出了贪婪算法用作数据分组的转发机制时贪婪协议具有可达性的充分必要条件,并以4个路由尺度实例说明了分析结论在贪婪协议设计中的具体应用,为贪婪协议的设计提供了重要的技术依据.For wireless routing protocols, the arbitrary design of routing metric may greatly degrade network performance and even create routing loops, which is called the compatibilities between routing metrics and routing protocols. Based on routing algebra theory, this paper investigates the compatibilities between routing metrics and greedy routing. The necessary and sufficient conditions for delivery-guaranteed are derived when greedy algorithm serves as a packet forwarding scheme, and four routing metrics are used as examples to illustrate the applications of the theoretical result. Our work provides essential criteria for evaluating and designing greedy routing protocol.

关 键 词：无线网络 贪婪协议 路由代数 路由尺度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]