基于邻居拓扑的网络编码感知路由算法研究

论文摘要

局部网络编码作为实用网络编码的一种策略,可观的网络性能增益以及在无线网络中的实用性使其成为当前的研究热点。本文概述了实用网络编码的研究现状,总结了实用网络编码中典型的局部网络编码策略,以及局部网络编码感知路由算法的研究,并对现存路由算法的优势和不足做了比较分析。现存的局部网络编码感知路由算法大多数都采用类似于局部网络编码COPE的贪婪算法来寻找可编码数据包数最多的编码机会。针对局部网络编码,本文分析了规则拓扑中两个及多个数据包的可编码概率。理论分析和模拟结果表明,即使在非常稠密的网络环境中,任意节点上三个以上数据包的可编码概率极低,并且远远低于两个数据包的可编码概率。基于局部网络编码的编码机会分析,以及两个数据包的编码机会与拓扑结构的依赖关系,本文提出了一种无线网络中基于拓扑编码感知的路由算法TCAR (Topology Based Coding Aware Routing)。TCAR仅考虑两个数据包的编码机会,并且不再采用COPE中根据邻居节点传输信息来判断编码机会的方法,而是依据两个数据包的可编码拓扑关系,利用已有数据流的方向和流量来判断编码机会,结合编码机会和路径长度选择路径。模拟结果显示,TCAR相比于COPE,在网络吞吐量和平均端到端延迟等性能上得到了有效改善。针对TCAR优先选择编码机会最大的节点进行转发,可能导致节点共享信道竞争出现拥塞的问题,本文引入了负载均衡的编码感知路由算法LBTCAR (Load Balanced and Topology Based Coding Aware Routing)。该算法基于跨层设计思想,将节点上MAC层接口队列速率作为负载信息,结合编码机会和链路可靠性进行选路。模拟结果表明,相比于TCAR, LBTCAR路由机制能够在编码机会、链路可靠性、链路负载之间进行有效地折衷,进一步提高了网络吞吐量。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究意义和主要研究内容
• 1.3 论文的组织
• 第二章 局部网络编码与编码感知路由算法研究
• 2.1 实用网络编码概述
• 2.1.1 实用网络编码在无线网络中的研究
• 2.1.2 实用网络编码的两种常见策略
• 2.2 典型的局部网络编码算法
• 2.2.1 贪婪网络编码
• 2.2.2 二分组网络编码
• 2.2.3 协同网络编码
• 2.3 局部网络编码感知路由算法
• 2.3.1 集中式编码感知路由
• 2.3.2 分布式编码感知路由
• 2.4 现存算法优点和不足的比较
• 2.5 本章小结
• 第三章 局部网络编码的编码机会分析
• 3.1 概述
• 3.2 局部网络编码模型
• 3.3 与拓扑结构相关的编码约束条件
• 3.3.1 两个数据包的可编码条件
• 3.3.2 多个数据包的可编码条件
• 3.4 可编码概率分析
• 3.4.1 四邻居概率分析
• 3.4.2 六邻居概率分析
• 3.4.3 十二邻居概率分析
• 3.5 编码机会的模拟分析
• 3.6 本章小结
• 第四章 TCAR:基于拓扑编码感知的路由算法
• 4.1 TCAR基本思想
• 4.2 建立可编码映射表
• 4.3 路由表的保存
• 4.4 路由判据
• 4.5 路径的建立
• 4.5.1 路由请求阶段
• 4.5.2 路由回复阶段
• 4.5.3 路由维护阶段
• 4.5.4 数据传输阶段
• 4.6 模拟结果分析
• 4.7 本章小结
• 第五章 LBTCAR:负载均衡的编码感知路由算法
• 5.1 LBTCAR基本思想
• 5.2 路由判据
• 5.2.1 结合编码机会和链路可靠性的度量
• 5.2.2 节点负载拥塞度量
• 5.2.3 综合路由度量
• 5.3 路径的建立
• 5.4 模拟结果分析
• 5.5 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 进一步的研究工作
• 参考文献
• 致谢
• 攻读硕士期间科研项目和研究成果