Ad Hoc网络中Wardrop路由模型及算法研究

摘要

无线AdHoc网络是一个复杂的分布式网络系统,是一种自组织和自管理网络,由一组带有无线收发装置的移动节点组成。这些移动节点既可以作为终端接收来自其他节点的数据信息,又可以作为路由器转发其他节点的数据信息。目前应用比较广泛的无线AdHoc网络路由协议主要有三类:典型表驱动路由协议(DSDV,OLSR等);典型按需路由协议(DSR,AODV等);典型混合式路由协议(DDR,ZRP等)。 由于网络节点的分布不均,且在路由选择的时候是以最短路径为选择标准,AdHoc网络容易造成数据分组经过多跳转发而导致某条链路局部拥塞,造成经过此链路转发的数据分组的时延和丢包率增大,使得网络的整体性能降低。随着网络的快速发展,用户希望路由能够自适应的调节链路上的负载均衡,也希望通过利用多路径获取更多的吞吐量。Wardrop均衡理论是研究交通网络均衡的原理之一,在公路规划、交通流量分配等领域被广泛应用,并产生了深远的影响。由于交通网络经常会出现部分路段拥堵的情况,用户在出行的时候会根据经验选择本身代价最小(近似为时间最短)的路径,整个网络最终达到Wardrop均衡状态。如果用户出行时选择的是整个网络代价最小的路径,整个网络会达到另一种Wardrop均衡状态——系统最优状态。近年来,通信网络研究开始关注这一领域,希望依据Wardrop理论开拓一个新的方向。 本文介绍了AdHoc网络的特点、关键技术和应用领域,重点描述无线AdHoc网络的DSR路由协议,并根据国内外的研究分析了其不足的地方。本文分析了Wardrop均衡理论在通信网络中的应用,并在AdHoc网络中引入了Wardrop均衡理论,提出了UE-DSR(UserEquilibrium-DSR)路由模型和SO-DSR(SystemOptimization-DSR)路由模型。两个路由模型均以最小代价作为路由选择下一跳的条件,实现了流量按照最小代价近似均匀的分布在传输路径上,缓解了DSR路由模型由路由选择带来的局部拥塞问题,使网络通过不同的方式达到Wardrop均衡状态。本文在NS2模拟环境中通过对DSR、UE-DSR和SO-DSR路由模型进行实验,比较了三者分别在10节点、30节点、100节点的性能。在较少节点数时,DSR、SO-DSR和UE-DSR路由模型的性能相差无几,随着节点数目增加,SO-DSR和UE-DSR路由模型的优势开始体现。在节点数足够多的时候,SO-DSR的性能整体要好于UE-DSR路由模型的性能,远远好于DSR路由模型性能。 本文针对大规模无线AdHoc网络引入了分层路由树的概念,利用最高连通性分群算法构建了新的分层路由树模型RT-DSR(RootTree-DSR),提高了网络的可扩展能力,有效地解决了吞吐量随着网络节点数增大迅速下降的问题。本文将分层路由树模型RT-DSR的根节点层面近似为平面路由协议,并在其选择路由下一跳时以最小代价为条件,在分层树的根节点层次上应用了UE-DSR路由算法和SO-DSR路由算法,使其满足了Wardrop均衡的要求,缓解根节点的拥塞状况。改进后的路由协议采用NS2进行网络仿真,并跟DSR路由协议进行比较。通过分析结果,改进后的路由协议能够更好地适应较大规模的网络,有效缓解了由于根节点大量转发数据分组造成的网络拥塞问题,提高网络的传输性能。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 研究背景

1.2 Ad Hoc网络的应用

1.3 Ad Hoc网络概述

1.4 本文的创新及其结构安排

1.5 本章小结

第二章 无线路由协议与Wardrop均衡

2.1 DSR路由协议概述

2.2Wardrop均衡

2.3 本章小结

第三章Wardrop均衡下的DSR路由模型研究

3.1模型假设

3.2UE-DSR路由算法研究

3.3SO-DSR路由模型研究

3.4 模拟实验比较

3.5 本章小结

第四章 分层路由树模型及应用

4.1分层树路由模型描述

4.2 构造分层路由树模型

4.3分层路由树维护

4.4 根节点的Wardrop均衡路由算法

4.5 模拟实验比较

4.6 本章小结

第五章 总结及其展望

5.1 本文的主要工作

5.2 进一步研究

参考文献

攻读硕士学位期间发表的论文

致谢