目前，ad hoc网络中的路由算法^[1]研究的热点主要集中在分簇、拓扑变化等问题.由于网络中节点的快速移动会造成网络拓扑的动态变化，从而引起丢包和网络传输时延的增加，因此如何寻找一条高效、高质量的路由路径是解决问题的关键.国内外许多学者已经对该课题进行了一些深入研究，提出了多种路由判据^[2]，如基于跳计数判据^[3](hop count)：它的重点就是找到跳数最少的路径来转发数据;它的缺点是在某些节点上可能出现拥塞和能量消耗，也没有考虑到不同链路的性能差异.基于往返时延的路由选择方法或算法^[4](RTT ：per-hop round trip time)：RTT的设计主要是针对高负载的链路，缺点是没有考虑数据的传输速率和链路间的干扰.期望传输次数判据^[5](ETX ：expected transmission count)：ETX判据考虑了包的丢失速率和路径的长度，因此对于长的有损耗的路径有更大的ETX值.ETX判据的主要缺点是没有考虑到流内和流间干扰，更没有考虑不同链路上包的传输速率差异的影响.基于期望传输时间判据(ETT ：expected transmission time)^[6]：在ETX基础上考虑了数据传输速率和链路的容量对路径性能的影响，但是，ETT路由判据的缺点是没有全面考虑到网络中的流内和流间干扰.基于干扰感知期望传输时间判据^[7](iETT ：interference-aware expected transmission time)：它分析了普通ETT判据的缺点，在iETT判据中，研究了单独链路高丢包率对整个路径性能的影响，也考虑用MAC层的开销来计算数据传输时间.综合以上路由判据的特点，这些路由判据都不同程度地缺乏对网络中路径的长度、丢包率、数据传输速率和干扰等因素的考虑，造成网络性能低下.

针对上述研究工作面临的问题，本文提出了一种基于节点地理位置信息预测的路由算法，本算法将DSR路由算法的最短跳数判据替换为iETT判据，从丢包率、数据传输速率等多个角度综合考虑链路的性能差异.而且为了寻找一条高质量的路径，考虑节点移动引起的拓扑变化，本文引入了基于地理位置预测的ARIMA(auto regressive integrated moving average)模型，ARIMA ^[8] 模型也称为差分自回归移动平均模型，是由统计学家Box和Jenkins提出的.通过预测模型的计算，可以获得下一时刻两个节点的运动位置，通过判断下一时刻两个节点运动的位置关系来决定是否使用iETT判据.本算法优化了路由选择，提高了网络的总体性能.

在iETT路由判据的设计中，需要知道每条链路的期望传输次数ETX、丢包率P、数据传输速率R就能实现iETT的计算.已知在IEEE 802. 11b的多速率环境中，发射功率一定时数据传输速率和传输范围有密切的关系，这样只要知道两节点之间的距离就可以找到最佳的数据传输速率.节点间链路ETX、丢包率P通过d_f和d_r获得，而d_f,d_r和 节点的位置距离都可以通过相邻节点间的信息获得，这样就使得iETT路由判据的实现成为可能.下面计算前向和反向转发成功率.

前向转发成功率d_f和反向转发成功率d_r的计算方式是通过每个探测包以最高0.1Δ的抖动周期发送广播链路探测包.每个节点发送一个广播探测包周期为Δ=1s.发送探测包的时间每次可在0.9Δ~1.1Δ间任意选取.由于在网络中链路探测包的发送采用广播方式，不会有ACK确认信息，因此如果发生丢包现象，节点也不会再重新发送探测包.网络中的每个节点记录在过去的Γ时间(在本文中值为10s)内所接收到的探测包数量.因此，在任意t时刻计算发送端的传送率的计算公式如下所示：

如图1所示的链路中，采用式(1)的计算方法，节点X会计算出d_r，节点I(J或K)可以计算出d_f.其中，d_r=从邻居接收到路由探测包的数目/10；d_f=邻居接收到路由探测包的数目/10.例如：计算节点X和节点I的丢包率P.取周期Γ=10s，在10s的周期内，统计到节点X接收到发自节点I的路由探测包数为10个，而节点I接收到发自节点X的路由探测包数为7个，然后，节点X等待节点I以单播的方式回复此信息给自己，节点X收到此信息后，会计算由节点X传送到 节点I的丢包率P：P=1－(1－0.3)×(1－0)=0.3，则转发成功率为0.7.再计算ETX的值为1/0.7= 1.43.这样以此类推，按照这种算法可以计算出每条链路的ETX和P的值.

图 1(Figure 1)

Fig. 1

图 1 探测包发送示意图 Fig. 1 Diagram of probe sending

本文采用DSR路由算法，但是节点在选择路由时不是根据最短跳数和ETT判据，而是依据iETT值来选择更优的路径，并且选择iETT值小的路径.假设拓扑结构中节点A是源节点，节点B,C是转发节点，D是目的节点.节点A与目的节点D的通信需要选择一条路径进行传输，可供选择的路径是A-B-D和A-C-D两条路径.若t时刻两条路径的干扰感知期望传输时间iETT的大小关系是：iETT_A-B-D＜iETT_ACD，则会选择A-B-D这条路径进行转发数据.但是节点B的运动方向是远离节点A.所以在t+1时刻(下一时刻)，节点B已经不在节点A的通信范围之内，而节点C仍然处于节点A和节点D的通信范围内.在这种情况下，A-B链路已经断开，选择A-B-D路径就不能进行通信了.

为了避免这种现象，可以提前预测节点下一时刻的地理位置，预测运动趋势.判断节点在下一时刻是否能够运动到彼此的通信范围内，若在通信范围内，则选择iETT值小的链路；否则，iETT判据不再适用.本文采用ARIMA地理位置预测模型，根据节点过去的地理位置信息预测t+1时刻节点的地理位置，可以提前预知节点的运动趋势，确定位置关系；然后再计算iETT的值，选择在通信范围内的iETT值小的链路，节点选择路由的方法流程图如图2所示.

图 2(Figure 2)

Fig. 2

图 2 L-iETT判据流程图 Fig. 2 Flow chart of L-iETT criterion

在路由建立之前，位置信息预测模块、探测包模块等模块都要初始化，还有路由表的初始化.在各部分初始化后，开始广播发送探测包，邻节点提取有用的信息并储存.探测包发送的程序为

路由更新时，当节点收到RREQ时，节点启动ARIMA地理位置预测，判断下一时刻该节点与上一跳转发节点是否在通信范围内，如果在通信范围，则更新路由，计算与上一跳转发节点链路的丢包率P、链路数据传输速率R，并且将计算结果及该中转节点地址存入RREQ的节点信息路由表中.当RREQ到达目的节点时，进行iETT的计算，并将其值加入RREP返回源节点，选择iETT值最小的RREP作为建立起一条通往目的节点的最优路径.

3.1 仿真环境描述

本文使用NS2^[9]进行仿真，节点随机分布在500m×500m的矩形区域，节点使用相同的无线收发设备，采用单一增益的全向天线，默认无线通信传输半径为250m，无线接口带宽为2Mb/s.每个CBR数据包大小为512byte，移动速度在1~5m/s内随机选取.在实验结果中，每个数据点表示10次实验的平均值.表1给出了仿真中所使用的主要技术参数.

表 1

Table 1

表 1(Table 1)

表 1 仿真环境参数 Table 1 Parameter of simulation circumstance 参数 值 参数 值 路由算法 L-iETT 传播模型 TwoRayGround 移动模型 RWP 业务类型 CBR 接口队列 PriQueue 队列长度 50 节点数 20 全向天线 OmniAntenna 仿真时间/s 300 发包速率/(kb·s-1) 20

表 1 仿真环境参数 Table 1 Parameter of simulation circumstance

为了能够较全面地比较算法的性能，本文从平均吞吐量、平均端到端时延、路由开销3个性能度量标准进行了分析.

图3显示了吞吐量和节点停留时间之间的关系.从图中可以看出，改进的算法明显比DSR路由算法吞吐量高，这是因为iETT判据综合考虑了各种因素对整个路径性能的影响，因此它能够主动选择吞吐量高的链路进行数据传输.而且本文引入的ARIMA模型可以提前预测节点运动趋势，可提前得知节点是否运动出通信范围，然后选择下一时刻能够运动到通信范围内的节点进行路由，由此减少了链路断裂和丢包.结果表明，采用L-iETT比DSR吞吐量提高6 % ~9 % .

图 3(Figure 3)

Fig. 3

图 3 平均吞吐量-停留时间 Fig. 3 Average throughout-pause time

由图4可知，L-iETT路由算法的时延比DSR路由算法降低2 % ~6 % .这是因为本文运用的预测模型可以选择下一时刻稳定的链路进行路由，减少了路由中断次数，进而减少了路由重建的等待时延，使目的节点不可达现象减少，从而减少了发送数据的等待时间.

图 4(Figure 4)

Fig. 4

图 4 平均端到端时延-停留时间 Fig. 4 Average end-to-end delay-pause time

路由开销与节点停留时间的关系如图5所示.随着节点停留时间的增加，两个协议的路由开销都在减少.这是因为随着节点停留时间的增加，链路中断次数减少，重建路由的次数就减少，需要的开销就较小.当停留时间达到一定值时，两个协议的路由开销趋于稳定.由图可见，L-iETT的开销要大于DSR，这是因为L-iETT加入了周期为1s的广播探测包机制，所以造成了网络中的广播开销增大.

图 5(Figure 5)

Fig. 5

图 5 路由开销-停留时间 Fig. 5 Route overload-pause time

本文提出了基于ARIMA预测模型的L-iETT路由算法，利用干扰感知期望传输时间判据改进原始DSR算法，能够减少丢包，提高网络吞吐量，而且运用预测模型也可以减少链路中断，提高传输时延.L-iETT算法虽然在吞吐量和时延方面有明显的性能提升，但增加了广播开销，今后可在控制开销方面作进一步的改进.