论文导读：在AdHoc组播路由分段模型中。采用了分段模型和LET预测模型。对每个分段进行分别管理。提前进行路由重建。分段，基于移动预测的分段AdHoc网络组播路由重建模型。
关键词：AdHoc，组播路由，LET预测模型，分段，路由重建
（一） 引言
节点移动预测算法是通过对相邻节点的监控，预测其下一时刻的行为，如果相邻节点要离开节点间的有效通信范围，那么节点预先启动新的路由发现过程[1]。论文格式，分段。移动预测算法是基于无线传播数学模型的。通过合适的无线传播模型，可以估计节点间的距离。通过估算距离和时间间隔这两个参数，可以估计相邻节点的相对运动已经运动的速度等参数。
为了减少网络拓扑结构的变化带来的重路由操作，寻找一条最为稳定的路径就成了关键[2]，因而首先要确定各个链路的稳定性。如何利用节点现有的运动信息预测节点在将来某个时刻的运动状况就成了预测链路稳定性的关键。链路预测包含两个阶段节点运动状态信息的获取和运用链路预测方法进行链路状态计算。
（二）一种基于移动预测的分段Ad Hoc组播路由重建模型
根据当前网络节点分布情况，将距离较远的通信节点之间的节点分成若干分段，对每个分段进行分别管理，当某分段路由失败时可以只针对这一分段进行路由重建，而不需要整个网络都参与，降低了路由维护的开销。每一个分段都用LET预测模型预测本分段中两个节点之间的连接保持时间，以便在路由发现阶段寻找较为稳定的路由，同时可以预测本段路由的失效时间，在本分段路由接近失效的时候，提前进行路由重建，使上层应用尽量不受路由断裂的影响，保持上层业务的持续性。
1.分段模型
对于本文给出的分段模型，根据当前Ad Hoc网络节点分布情况，将距离较远的通信节点之间的节点分成若干分段，组成员存在于分段内，如图1中的Seg1，Seg2 ，…，Segi 。这样，对每个分段分别管理，当某分段路由失效时可以只针对这一分段进行路由重建，而不需要整个网络都参与重建，从而降低了Ad Hoc网络组播路由维护的开销。
图1 基于移动预测的分段Ad Hoc网络组播路由重建模型
在Ad Hoc组播路由分段模型中，节点分为源节点、目的节点、中间节点和普通节点四种：(1)源节点为某一路由的开始节点，如图1中的节点S；(2)目的节点为某一路由的目标节点，如图1中的节点D1，D2，D3，…，Dj；(3)中间节点为某一路由中相连两个分段的公共节点，如图1中的节点M1 ，M2 ，…，Ml ；4)普通节点为某分段除了中间节点以外的节点，如图1中的节点C1，C2，C3，…，Ck。论文格式，分段。
在某次路由中，如果某分段内的普通节点是路由接收者时，这些普通节点就变为目的节点。为了使Ad Hoc路由协议在有效性和效率之间取得平衡，该模型每一分段中设两个主节点，一般把每段的中间节点设置为主节点，例如图1中的Seg2分段的两个主节点为M1 和M2。分段中的主节点主要用于对组成员的管理与维护，主节点的路由表上应维护该分段内的组成员节点的信息。分段内某一组成员脱离或者加入组，都需要在主节点的路由表中得到体现。
2. 分段的确定
将网络划分成若干分段时，协议需要以下主要信息。分段列表（SList），中间节点列表（MList）。分段列表保存所有分段的信息，中间节点列表保存所有中间节点的信息。论文格式，分段。分段Ad Hoc网络组播路由重建模型中分段列表和中间节点列表如图2所示。
图2 基于移动预测的分段Ad Hoc网络组播路由模型的分段列表和中间节点列表
3. 基于移动预测的分段Ad Hoc组播路由的建立过程
基于移动预测的分段Ad Hoc组播路由的建立过程和标准的组播路由协议一样，主要分为路由请求，路由转发和路由应答三个阶段，但是在基于移动预测的分段Ad Hoc组播路由协议中，采用了分段模型和LET预测模型，需要对这三个阶段进行改进。
（1）路由请求
路由的发起过程是由源节点发起Join-Query分组开始的。如果源节点一直有数据需要发送，它将会周期性地发起Join-Query分组，以更新网络路由。当源节点为中间节点时，它首先检查中间节点路由表中是否有目的节点，如果有，就将Join-Query消息直接广播给该分段内的目的节点，然后将Join-Query分组广播给该分段中另一个中间节点，并由该中间节点向后面的分段转发Join-Query分组。当源节点为非中间节点时，它会先把请求包传播给源节点所在分段的中间节点，再由该中间节点来进行发送。
（2）路由转发
当某一分组要从某一分段的一个中间节点转发到另一个中间节点的时候，就可以通过 来发现更为稳定即RET值更高的路由。
基于移动预测的分段Ad Hoc网络组播路由的转发过程如图3所示。
图3 基于移动预测的分段Ad Hoc网络组播路由的中转流程
（3）路由应答
接收到Join-Query消息的组播组的成员节点，它会将数据保存下Join-Query消息的反向路径记录，选择一个前向路径，创建Join-Reply分组，如果该成员节点是中间节点，它会直接将Join-Reply分组广播到同分段中的另一个中间节点，否则，它会先把Join-Reply分组广播给该分组的中间节点。收到Join-Reply分组的所有节点检查它是否是重复分组，如果是则丢弃；否则，当一个任何中间节点接收到一个非重复的Join-Reply，它检查是否路由缓冲中下一个节点的ID是它自己的ID，如果是，则该节点处于通往源节点的路径上，如果不是，则转发，直至到达源节点为止。
4. 性能分析
标准ODMRP协议为了建立转发组和维护转发组成员，发送节点必须周期性发送路由请求包，同时该路由请求包是以洪泛的形式发送，这将对网络造成不小的负担。尤其是在网络规模扩大或网络的负载较大的时候，协议的性能将由于频繁的洪泛包而急剧下降。论文格式，分段。而在基于移动预测的分段组播路由重建模型中，将网络分成若干个分段，只有中间节点才对接收到的洪泛包进行处理，分段内其他普通节点对这些洪泛包并不做出反应，从而有效地减少了分组的洪泛，并有效减少了协议的控制开销。
下面以图4为例，分析比较基于移动预测的分段组播路由重建模型与标准ODMRP协议路由重建模型的性能。
 
图4 基于移动预测的分段组播路由重建模型与标准ODMRP协议路由重建模型的对比
该路由链路如图4所示，从源节点S出发，经过C1，C2，M1，C3，M2，…，Mi到达目的节点D，假设节点C2因故要离开该组播组，那么从C1到C2的链路将出现断路，此时就需要进行路由重建。
标准ODMRP组播路由协议进行路由重建过程如下：
（1）源节点S在节点C2离开组播组以后才进行路由重建；
（2）源节点S广播路由请求Join-Query，每个节点都将收到路由请求，并转发；
（3）目的节点D收到路由请求后，发送路由应答Join-Reply，并按照向前路径中最短路由建立反向转发组；
（4）路由重建后的路径：C1，C4，M1，C3，M2，…，Mi。
基于移动预测的分段组播路由重建模型重建路由的过程是：
（1）在节点C2所在的链路失效前，M1开始进行路由重建；
（2）源节点S广播路由请求Join-Query，在seg1段中的每个节点都将收到路由请求，并转发；
（3）公共节点M1收到路由请求后，将不再转发，而是发送路由应答Join-Reply，并按照向前路径中最短路由建立反向转发组；
（4）路由重建后的路径：C1，C4，M1，C3，M2，…，Mi。
通过分析上述两个重建路由的过程，可以发现路由重建后的节点路径是一样的，但是在效率方面：(1) 标准ODMDRP协议在路由失效后才进行路由重建，而基于移动预测的分段组播路由重建模型在路由失效前已经开始进行重建了；(2)源节点S发送路由请求Join-Query时，标准ODMRP协议需要网络中的每个节点都转发该请求包，而基于移动预测的分段组播路由重建模型只需要在失效的节点所在段的区域内转发请求包；(3)标准ODMRP协议需要路由请求包到达目的节点后才进行路由应答，而基于移动预测的分段组播路由重建模型只需要路由请求包到达了失效节点所在段的公共节点后就可以进行路由应答。由此，我们发现对于基于移动预测的分段组播路由重建模型，通过检查各条路由对应的保持时间RETi，可以在路由失败之前进行路由重建，使上层业务保持连续性；当某分段的链路断开时只需要针对这一分段进行链路重建，而不需要整个网络都参与，减少了路由的重建时间，降低了包丢失率，提高了整个网络的数据传输效率。
此外，在标准ODMRP协议的路由算法中，当某条链路断开需要重新建立路由时，时间复杂度为O（2h）= O（h），其中h为该条路由的链路数量。论文格式，分段。而在基于分段和预测的Ad Hoc网络组播路由重建模型中，由于采用了分段的思想，当某条链路断开需要重新建立路由时，时间复杂度为O（2l）=O（l），l为路由中某一分段内的链路数量，当网络分为m段时，l ≈ h/m，故时间复杂度又可表示为O（2 h/m）=O（h/m）。由于m大于1，所以本模型建立转发组的时间比标准ODMRP协议时间要短。论文格式，分段。
三 小结
鉴于组播的路由建立需要大量的洪泛控制信息，本文考虑Ad Hoc网络中节点的移动性因素，提出了基于移动预测的分段路由重建模型，利用链路连接保持时间模型在路由失效前，分段进行路由重建，以减少控制信息的数量，降低节点能量的消耗，提高了整个网络的数据传输效率；但是由于中间节点的出现，所以使得本文提出的分段路由模型的管理成本有所增加。
参考文献
[1]吴东亚，侯紫峰，侯朝桢等．移动自组网按需机制路由协议路径失效预测和局部修复算法[J]．计算机工程，2004，30(3)：102-103
[2]郑少仁，王海涛，赵志峰等．Ad Hoc网络技术[M]．北京：人民邮电出版社，2005
[3]E.R.Inn，K.G.S.Winston．Distributed steiner-likemulticast path setup for mesh-based multicast routing in ad-hoc networks[C]．in：Proceedings IEEEInternational Conference on Sensor Networks，Ubiquitous and Trustworthy Computing，2006：192-197
|
