论文部分内容阅读
广播是Ad Hoc网络中的重要操作,其目的是将源节点发送的消息传送给网络中所有的通信节点。多种Ad Hoc网络路由协议(如AODV、OLSR、ODMDP等)使用广播进行路由选择并在网络节点之间更新路由信息,一个高效的广播算法将直接对Ad Hoc网络通讯协议栈的性能产生影响。实现广播的最常见方式是简单泛洪,但该种方法将导致严重的广播信息冗余、信道竞争和碰撞等广播风暴问题。为避免Ad Hoc网络中产生广播风暴,需要减少网络中广播包的数量,在广播算法中体现为选择尽可能少的节点转发广播包。现有广播算法可分为确定性广播算法和非确定性广播算法。由于非确定性广播算法的覆盖性欠佳,理论上不能确保网络中所有节点均能收到广播包,所以本文选用确定性广播算法进行研究。
本研究将图论中的支配集理论运用于Ad Hoc网络后,广播算法中试图寻找尽可能少的转发节点这一问题转化为寻找网络中的近似最小连通支配集的问题。因此,确定性广播算法的实质就是网络中连通支配集(Connected Dominating Set,CDS)的构造算法,可分为基于自裁减策略、基于极大独立集、基于邻节点选择等三类CDS构造算法。由于基于邻节点选择的CDS构造算法具有即时生成CDS的特点,其算法流程较前两类更为简单,适应于带宽有限且网络拓扑动态变化的Ad Hoc网络,所以本文进一步选取该类算法进行研究。在基于邻节点选择的CDS构造算法中,因为区域裁减算法(Dominant Pruning,DP)具有较好的性能,所以该类CDS构造算法的后续研究中很多都是针对DP算法进行优化。但这些优化算法都没有考虑本地支配节点和同级支配节点的关联关系对下一跳支配节点选择结果的影响,同时忽略了网络前一时刻状态对后续支配节点选择结果的影响。因此,本文从以上两个角度对DP算法进行优化:利用同级支配节点代替本地支配节点完成其后续覆盖过程,以减少本地支配节点所选择的下一跳支配节点的数量,从而在CDS构造过程中选择更少的支配节点;考虑网络前一时刻状态对支配节点选择结果的影响,进一步压缩本地支配节点两跳范围内需要被支配节点覆盖、但暂未被覆盖的节点数量,从而在CDS构造的过程中选择更少的支配节点。在此基础上,本文设计了改进型区域裁减算法(Impoved DominantPruning,IDP),拟减少CDS构造过程中被选择的支配节点数量,抑制冗余广播包的产生。最后,证明了IDP算法的正确性和可靠性,并对IDP算法和DP算法进行仿真。两个算法在不同网络节点密度和不同节点最大移动速度的场景下,分别对广播包的到达率、选择的转发节点数和产生的网络开销进行了仿真比较,以验证IDP算法的可靠性和有效性。