Ad hoc网络^[1]是一种无需任何固定设施的分布式无线多跳网络.随着网络节点发送数据量的增大，路由维护将给节点带来极大的负担.为了解决这个问题采用一种分层路由协议^[2]，协议中一些中间节点同源节点以及目的节点被选作上层节点，而其他节点为下层节点，分别运行各自层内路由协议.这里上层协议为DSR，下层协议为AODV，称作DSR over AODV(DOA协议).这种分层路由协议主要特点就是结合了DSR和AODV的各自优势，互相弥补不足之处，并且在路由修复过程中，减少了全局路由修复的次数，提高了局部路由修复的比例，大大减少了开销.

目前，国内外研究者对多种分级协议进行了研究.文献^[3]提出一种区域路由协议ZRP，它是第一个利用分级结构混合使用按需和主动路由策略的自组网路由协议.但是ZRP采用预置固定区域半径值决定算法性能，这无疑限制它的可适应性.文献^[4]提出的CGSR是在DSDV协议基础上结合分级路由机制设计的,此协议采用最小簇变化LCC(least cluster change)算法形成分级结构.文献^[5]提出的CEDAR协议目标是在ad hoc网络环境中构建一个稳定的虚拟核心结构用来可靠有效地扩散路由信息.但随着网络规模增大，路由更新带来的协议开销急剧增加，可扩展性不好.

针对上述研究工作面临的问题，本文提出了LSP-DOA路由协议，协议继承了DSR和AODV协议的优点，通过大量进行局部路由修复来减少网络的控制开销.再结合链路稳定性预测，在链路中断发生前，找到新的路径及时替换即将中断的链路，可以最大限度地保证稳定的数据传输.此算法可以改善控制开销、时延、分组投递率等多种性能.

网络规模不断增大所带来的开销使得节点的性能急剧下降.因此，分级路由协议被发展来解决这个问题.DOA利用AODV路由协议的局部路由修复机制^[6]，通过分层建立和维护活跃的路由，无论路径的中断发生在哪里都可以进行局部的修复，从而减少了源节点的路由发现次数.DOA协议可以降低路由开销，并且表现出更好的稳定性和其他性能指标.

在DOA路由协议中，提出一种路点路由模型WPR(way point routing)，它是一种稳定的路由模型，主要目的是为了分层地维护活跃的路由.这种路点路由模型的突出优势在于当网络中某链路中断时，路由协议不会寻找一条完整的从源节点到目的节点新路径，而是寻找该链路上下游的两个上层节点间的新路径.利用这种方式可以降低路由开销，降低端到端延时，而且上、下层节点可以运行不同的路由协议.

DOA协议与CGSR和ZRP等分级路由协议相比，区别在于上、下层节点是在活跃的路径上，并且活跃路径的分层更容易进行维护.DOA中的分层也可以说是WPR的分层，更为简单化，如图 1所示.此外，在DOA中，由于节点会根据不同的路径有所不同，但是节点的功能是一致的.也就是说，一个节点在一条路径上是上层节点(up-node)，那么它在另一条路径上则是下层节点(down-node)，所以并没有把某些节点特殊化.这样使得网络中节点资源消耗更趋于一致化.

图 1(Figure 1)

Fig. 1

图1 路由的分段 Fig. 1 A route divided into segments

在WPR分层结构中，上层节点运行DSR路由协议，并且只有上层节点被列入数据包的头文件作为源路由选项，而下层节点运行AODV路由协议.因此，把这种协议称作DSR and AODV路由协议，简称DOA.通过分层结合DSR和AODV，使DSR运行在大型网络中，并限制了AODV局部修复的开销.存在两种特殊情况：一是当Up-node间跳数为1时，DOA工作在DSR模式下；二是当Up-node间的距离是一个大数字(大于网络覆盖直径)时，DOA工作在AODV模式下.

在DOA协议中，通过选择一些高级节点(up-node)，将一条路径划分为若干段(segment)，利用这种方式获得分层结构，高级节点(up-node)运行全局路由协议，而低级节点(下层节点)在段内运行局部路由协议.Up-node也包括源节点和目的节点，而路径上的其他节点称作转发节点(F-node).每一段都起始于上层节点，称为起始节点(S-node)，相对的终止于另一上层节点，称为结束节点(E-node).相邻的段会有同一个Up-node，在上游段是作为E-node，在下游段作为S-node.

图 1给出了节点A1到D1的路径划分结果，图中选择了节点B1和C1为上层节点，加上源节点A1和目的节点D1，把路径分为3个段：A1—a2—a3—B1，B1—b2—b3—C1，C1—c2—c3—D1.一个段可以用它的起始节点和结束节点简记为segment XX.DOA 工作在按需的基础上，类似于其他的按需路由协议，DOA协议的核心内容主要是四部分：路由发现、数据转发、路由维护、环处理.

根据上一节介绍的DOA协议的基本理论，得知DOA可以迅速修复中断路径，继而减少控制开销.但是网络中只要出现链路中断现象，无论局部修复或全局修复是否成功，都会导致一段时间内传输数据包的缓存.因此为了避免传输中断，引入了预测机制^[7]，可提前获知链路的稳定性.在链路中断发生前，找到新的路径及时替换即将中断的链路，基于以上分析，提出了LSP-DOA路由协议.

假设t，r是网络中1条链路的2个节点，d是它们间的距离.节点采用同一类型，即有效的通信范围(半径d₀)一致.如果用S_tr表示节点t，r之间的链路稳定性，它与间距和有效范围有关，定义为

当d≥d₀时，t，r不可以直接通信，S_tr=0;反之，可以直接通信，S_tr介于0和1之间.链路稳定性的预判断是基于无线传播模型的，无线传播模型围绕无线电波的发射功率、接受功率和节点间距之间的关系，来选择无线传播模型.如果2个节点比较接近，采用Friss模型.一般情况下，无线通信的节点间距较远，使用Two-Ray模型更加贴切，则有一个收发功率关于装置的水平距离和装置高度的关系式：

设最小接收功率为P_min，其所对应的距离是d₀，那么P_mind₀ ⁴ = CP_t ，将P_t带回式(3)中，得到

最后将式(4)带回式(1)，得到链路稳定性计算公式：

得到稳定度计算公式后，下面将进行链路稳定性的预测.当链路剩余时间^[8]小于启动一轮新的路由发现所需时间时，就认为链路不稳定，将会出现中断，需要启动新一轮路由发现，而稳定性临界点即为链路稳定性的阈值.换言之，稳定性的预测机制的重点就是各链路的稳定性与该阈值的比较和判断.

设一轮路由发现需要的时间是T，包括向源节点送警告、路由请求、路由响应等三个环节，考虑最坏的情况^[9]，上述环节都经历了所有节点(节点个数为N)，再根据ad hoc网络情况，测得平均每跳用时T_hop，那么T=3×N×T_hop.设阈值功率为P_th，响应的距离为d_th，节点最大移动速度为v_max，再把ad hoc网络的参数P_min和d₀代入式(4)得到

再把得到的P_th代入式(5)得到链路稳定性阈值S_th：

最后比较S_tr和S_th，其中S_tr表示某条链路的稳定性，S_th表示稳定性的阈值.当S_tr≤S_th时，判为链路不稳定，于是该链路的上游节点向路径的前向节点发送路由不稳定警告.收到警告后启动新一轮路由发现，反之则认为链路稳定.

LSP-DOA协议的路由发现、数据转发以及环的检测处理过程与DOA协议是相同的，不同之处在于路由维护过程.在LSP-DOA协议中，节点周期性的发送探测包，邻居节点根据接收到的探测包确定接收功率P_r，通过固定的最小发射功率P_min，算出即时的链路稳定性S_tr，再与链路稳定性阈值S_th进行比较，判断链路当前是否稳定. 如果不稳定(S_tr≤S_th)，此链路的上游节点会准备进行路由发现过程，来找寻新的路径替换即将中断的链路.在LSP-DOA协议中，链路稳定性阈值S_th的选值依据是段内路由修复，也就是说当链路剩余时间小于一次段内路由修复的时间时，认为链路不稳定.一次段内路由修复的时间T=3×DSL×T_hop.路由发现过程分为段内路由发现(或称下层路由发现)和上层路由发现.与DOA协议中的路由修复相似，段内路由发现的目的是寻找一条从本段的S-node到E-node的新路径，替换之前的即将损坏的路径.而上层路由发现是寻找从本段的S-node到下一段的E-node的新路径，替换即将损坏的路径.两个发现过程同样有更新上游一段或两段的功能.

首先判断此链路的上游节点是否为本段的S-node，如果不是，沿着逆向路径单播警告数据包，直到本段的S-node收到警告消息时，启动段内路由发现；否则，直接启动段内路由发现.如果段内路由发现成功，替换损坏路径，节点更新路由表，继续传输缓存的数据包；如果失败，启动上层路由发现.段内路由发现同时可以更新上游段，如同段内路由修复.

仿真过程中，CBR的大小不会随着网络拓扑的变化发生改变.设源节点仍以每秒发4个512bit的数据包的速度发送报文，节点的移动速度在0~30m/s间自由选择，考虑在网络规模不同情况下分析协议的性能指标：控制开销、分组投递率、端到端延时以及修复成功率.

表1

Table 1

表1(Table 1)

表1 仿真环境参数 Table 1 Parameters of simulation circumstance 参数 值 参数 值 带宽 2Mb/s 传播模型 Two-RayGround 信道 WirelessChannel 时间间隔 30s 传播距离 250m 业务类型 CBR

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

网络节点个数从0增加到1400.从图 2四种协议路由开销随网络规模变化趋势可以看出，LSP-DOA路由协议的控制开销略高于DOA协议，但却不明显.原因是LSP-DOA算法中增加了两种局部路由发现，虽然减少了全局路由发现的次数，可还是需要周期性的发送探测包，从而增加了控制开销.

图 2(Figure 2)

Fig. 2

图2 LSP-DOA的控制开销 Fig. 2 Control overhead of LSP-DOA

LSP-DOA路由协议的分组投递率仿真图如图 3所示，LSP-DOA的分组投递率平均高于DOA协议1.5 % ，随着网络规模的增加，LSP-DOA的分组投递率一直维持在95 % 上下.其原因是LSP-DOA协议在大部分时间里都维持着高效稳定的活跃路径，几乎不存在缓存的或积压的数据包.

图 3(Figure 3)

Fig. 3

图3 LSP-DOA的分组投递率 Fig. 3 Packet delivery ratio of LSP-DOA

从图 4可以看出，LSP-DOA的端到端延时比DOA和AODV还要低约0.1s.由于预测机制的采用，维持了高效稳定的活跃路径，最大程度地减少了链路中断的发生，使缓存的数据包数量大幅度降低，而缓存的数据包是造成延时的主要原因，预测机制很好地防止了中断，更进一步减少了全局路由发现的次数.

图 4(Figure 4)

Fig. 4

图4 LSP-DOA的端到端延时 Fig. 4 End-to-end delay of LSP-DOA

本文结合链路稳定性预测机制和DOA分层路由协议，提出了LSP-DOA预测算法.通过大量局部路由修复来减少网络的控制开销，利用链路稳定性预测，在节点通信链路将要中断前，寻找新路径及时替换即将中断的链路，用局部发现替代了多数的局部路由修复，可以最大限度地保证可靠的路由来传输数据.本文还有很多地方可以改进，如可以依据其他信息计算稳定性，节点的地理位置、节点的移动速度、节点的剩余电量等，此外将路由判据应用到机会路由也是将来研究的方向.