基于方向预测的移动自组网概率转发算法
2022-06-09
0引言
移动自组织网络（MobileAdHocNETwork，MANET）是由平等的移动节点组成的一种特殊的无线网络，具有无中心、自组织、动态拓扑的特点[1]，既可以独立地组成一个网络运行，也可以作为固定设施网络的一种补充，在战场通信、紧急抢险等领域应用前景广阔。但MANET节点的移动性引起网络拓扑的动态变化，从而导致现有的路由协议不再适用，因此如何设计高效的路由协议成为MANET的重点研究问题之一[2]。
MANET路由技术的核心是以最小的代价快速地找到一条通往目的节点的路径，洪泛是最经典的路由策略，源节点向全网络广播路由查询包，网络中的所有节点都会参与每一次寻路过程，当网络规模较大时，洪泛会带来巨大的路由开销，严重时甚至会引起广播风暴[3]。因此如何有效地降低路由协议的开销，优化路由算法性能成为亟待解决的关键问题。本文针对传统路由算法的不足，以按需距离矢量（AdHocOndemandDistanceVector，AODV）路由协议[4]为基础，
提出一种基于方向预测的改进路由算法（DirectionalPredictionroutingProtocolbasedonAODV，DPPAODV），以降低路由开销，提高网络性能。
1相关研究
洪泛的缺点在于搜索的无节制，致使每一次路由过程都要波及整个网络。针对这一问题，扩展环算法[5]提出了一种逐步扩大搜索范围的思路，一旦找到目的节点则搜索停止，这样搜索过程就不会波及整个网络。但当目的节点较远时，源节点需要多次重复发送路由请求包，仍会带来较大的路由开销。
路由开销取决于参与转发的节点数量，在密度较大的网络中只需部分节点参与转发即可覆盖整个网络，概率转发算法[6-7]的核心思想即是减少路由查询过程中参与转发的节点数量。网络中的节点通过选取某种概率P来决定是否转发，P的大小取决于不同的网络环境，这样在转发信号仍要覆盖整个网络的前提下，降低了参与转发的节点密度，如图1所示。概率转发算法减少了查询请求包被转发的次数，降低了网络开销。不难看出，概率转发算法的重点是转发概率的确定。
文献[8]考虑了网络节点的密度对转发概率的影响，利用hello包获取周边邻居节点的个数，以此为标准衡量局部节点密度，密度大，则转发概率小；
反之，转发概率大。文献[9]则通过对收到的邻居节点发送的相同的查询请求包进行计数，来判断节点密度。文献[10]认为只获得一跳邻居节点的信息是不够的，应该搜集尽量多的节点信息，包括邻居节点所能够传输到的节点。文献[11]考虑了节点的剩余能量，并结合了局部网络节点的密度，剩余能量多的节点转发概率大，反之转发概率小。文献[12]利用信号强度估测目标节点的距离，进一步减少转发节点数量，降低路由开销。
概率转发算法的优点是在保证整个网络无缝覆盖的基础上，减少了参与转发的节点数量，从而降低了路由开销。但是现有概率转发算法存在以下问题：1）同洪泛一样，概率转发算法仍然力求全网络覆盖，而实际上在某一次路由开始的时刻，目的节点只能位于一个确定的地点，路由过程只有一个正确的方向，在其他方向的搜索即使设定了转发概率，也都是无效的；2）为所有或者部分节点设计一个统一的转发概率，忽略了不同节点的个体差异。针对以上问题，本文提出了一种基于方向预测的概率转发算法，通过将路由过程限制在指向目的节点的方向上，进一步降低路由开销。
2基于方向预测的概率转发算法设计
基于方向预测的概率转发算法（DPPAODV）的基本思想是：如果能够知道目的节点的方位信息，使得路由过程只是沿着目的节点所在方向进行，而不必覆盖整个网络，那么自然可以大幅度地降低路由开销。如图2所示，路由搜索只需覆盖部分网络，但已经可以找到目的节点。与经典概率转发算法的图1相比较，在通向目的节点的方向上的节点以概率参与转发，而其他方向的节点则并不转发，图2中灰色的节点数目即为减少的路由开销。
3实验分析
实验采用仿真软件NS2[14]，在1000m×1000m的区域内分布100个节点，采用随机路点移动模型（RandomWaypointModel，RWP）[15]。节点均使用相同参数的射频单元，无线接口为IEEE802.11，全向天线，覆盖半径为250m，信道容量为2Mb/s。采用固定码率（ConstantBitRate，CBR）数据流模型。修改最大移动速度的值模拟不同的场景，每种场景运行实验20次，每次1000s，取所有实验结果的平均值。路由协议均在AODV路由协议基础上修改实现，从归一化路由开销、平均端到端时延和数据包投递率三个方面，对比了洪泛算法、扩展环算法、经典概率转发算法和本文提出的DPPAODV算法的不同。
3.1归一化路由开销
归一化路由开销指发送一个数据信息包所需要的控制消息包个数，该参数反映了网络路由效率。由图4可以看出，基于方向预测的概率转发算法的路由开销最小，比洪泛算法降低了70%，比扩展环算法降低了50%，比经典概率转发算法降低了20%左右。随着节点最大速度的增加，各算法的路由开销均有所增加，但是DPPAODV算法的性能仍然最优，说明算法能够适应场景的变化，自适应地确定转发概率的方法有效，总体上DPPAODV算法有效地减小了路由发现过程的盲目性，降低了路由开销。
3.2平均端到端时延
平均端到端时延指整个仿真过程中所有成功到达目的地的数据包的平均时延，包含所有可能的延迟时间，如路由发现时间、数据包传递时间等。该参数从时间的角度反映了所选路由的质量。如图5所示，在四种算法的平均端到端时延中，总体来看DPPAODV算法的时延最小，主要是因为在路由发现节点减少了转发数据包数量，降低了网络中的信道竞争，从而缩短了端到端时延。随着节点移动速率的增加，各算法的平均端到端时延有变大的趋势。