摘  要： 深入研究移动自组网中的多播路由问题，提出一种适用于移动自组网的基于遗传算法的QoS多播路由算法。通过引入探测时间限制，有效减少了路由结点和链路的寻找范围，同时降低了选择无效结点和链路的可能性。通过证明，该方法满足带宽、延迟、延迟抖动、剩余能量约束的要求。在此基础上，提出了一种基于遗传算法的QoS路由选择优化算法。仿真试验表明，该算法是可行的，且延时性要优于MAODV。

　　关键词： 移动自组网；多播；遗传算法；服务质量；路由算法

0 引言

　　移动自组网[1]（Mobile Ad Hoc Networks，MANET）是由移动通信主机临时组成的无线多跳网络。当任何一个移动主机加入或离开其他移动主机的通信范围时，无线连接也会相应地形成或断开。网络中的任何一个节点既充当主机又充当路由器。无线网络的拓扑结构也会随机地发生变化。由于移动自组网的动态性，使得网络中的多播路由成为一个具有挑战性的问题[2]。

　　服务质量（Quality-of-Service，QoS）的基本功能是基于QoS约束[3]，找到一个好的路由。QoS约束包括：端到端的延迟、带宽保证、抖动、丢包率等。随着移动自组网对数据传输稳定性要求的提高，提供QoS保证已经成为MANET网络研究中的一个重要领域[4]。尽管多约束可以更准确地模仿网络和应用，但是基于MANET网络的QoS多播路由问题是一个多约束的NP完全问题[5]。这就意味着移动自组网中QoS多播路由问题不能在合理的时间范畴内优化解决，这对于普通的应用主体，尤其是对延迟敏感的应用是非常关键的。遗传算法是仿真生物遗传学和自然选择机理通过人工方式所构造的一种新型优化算法[6]，它能够进行自适应群体寻优，并行搜索，产生最优解集，已广泛应用于解决各种NP完全问题。本文提出了一种基于遗传算法的多约束多播路由，达到按需优化的目的。

1 QoS多播路由问题及改进

　　QoS多播路由的约束有以下属性：（1）可加性：total_metric=∑imetrici，即总度量=各节点度量的和，路径延迟和跳数是这类属性的代表。（2）凹性：min_metric=mini{metrici}，它可以表示为：最小的度量=各节点度量的最小值，带宽和剩余能量是这类属性的代表，它们可以描述成可用带宽的最小值或路径上所有的链接和结点的剩余能量。（3）乘性：mul_metric=∏imetrici，即复合度量=各节点度量的积，包传送率是这类属性的代表。

　　寻找多播路由可以表示为寻找一棵从根节点到一系列接收节点的树。假定网络可表示为一个带权图G=（V，E），V是点集，表示一系列移动主机，E是边集，表示连接移动主机间的链路，连接节点u和v的边e∈E，e也可以表示为（u，v），其中u，v∈V。一棵树的根节点是s，s∈V，必须满足以下各种约束。

2 探测时间限制机制

　　采用探测时间限制机制建立路由，当建立一条新路由时，接收节点不在发送节点的邻居节点列表中，发送节点发送一个路由请求包，该请求包包括请求的延迟抖动最大值、可用带宽的最小值、剩余电池能量的最小值以及端到端的延迟最大值。当收到该请求包时，各接收节点对照自己和发送节点间的约束关系，判断是否满足，如果接收节点i满足约束关系，主机i将在自己的路由表中添加一条临时路由，并且再次向下一跳节点发送路由请求包。主机i将在T内保持探测状态，T=2D-D（e），表示从发送节点s到接收节点i的总延迟。如果在T时间内s没有收到来自i的回应，则临时路由将被删除。网络中的多播路由探测时间限制机制采用连通性和状态发现机制实现。因此，它增加了移动主机生成满足约束条件路由的机率。

　　多播树新成员加入的主要过程如下。其中，每个节点的请求信息由search.request，build.request，reply组成。链路e的带宽、延迟、延迟抖动和剩余电池能量分别表示为B（e）、D（e）、J（e）和P（e）。

　　switch（请求信息）

　　case search.request（i）

　　if（节点i不在发送节点的邻居节点列表中and min{P（e）}>P）then发送

　　search.request给网络中的所有节点

　　if（r.packet[i].b≥B and r.packet[i].d≤D and r.packet[i].j≤J）

　　then send build.request（）to next；

　　break

　　case build.request（B，D，J，P）

　　if（b（e）≥B and d（e）≤D and j（e）≤J and min{P（e）}>P）then

　　path.temp=r.packet[i].path；

　　send build（B，D，J，P，path.temp）to next；

　　break

　　case reply（新加入节点i的应答时间t）

　　if（t≤T）then

　　path.permanent=path.temp；

　　else删除path.temp

　　break

3 性能分析

　　3.1 正确性

　　定理1 采用探测时间限制机制构造的多播树TM能满足带宽、延迟、延迟抖动、剩余能量约束的要求。

　　设在多播树TM中，L（s，v）表示从s到v的路径，V表示L（s，v）上的点集，t表示新加入节点到s的应答时间。

　　证明定理1等价于：

　　证明：

　　（1）根据探测时间限制机制，协议是依据（delay（L）=（delay（v0，*）+delay（vm，vn）≤D）∧（jitter（L）=（jitter（v0，*）+jitter（vm，vn）≤（J）∧bandwidth（v0，vn）≥B）∧（t≤T）来计算delay和jitter。因此，对于L（s，v）TM，bandwidth（L（s，v））≥B。

　　（2）根据探测时间限制机制，当且仅当delay（L（s，v））≤D且jitter（L（s，v））≤J时，节点才发出加入请求，新加入节点i的探测应答时间t≤T，其中T=2D- D（e）。这就保证了从节点s到i，再从i到s的总延迟时间2×delay（s，i）≤D（e）+T=2D，也即从源节点到目的节点的延迟时间小于延迟上限D。所以，对于L（s，v）TM，有L（s，v）必满足延迟和延迟抖动的要求。

　　（3）根据探测时间限制机制，当min{P（e）}>P时，节点才发出加入请求，所以对于?坌L（s，v）TM，有minP（u）＞P。

　　结合上述（1），（2），（3）的证明可知，依据探测时间限制机制所构造的多播树必能满足带宽、延迟、延迟抖动和剩余能量的约束。

　　定理2 根据探测时间限制机制所构造的多播树TM搜索的可行路径是没有回路的。

　　证明 在r.packet路由表中只存在一个输入端，一个或多个输出端，从输入端到输出端的路径是一种树形结构，当新节点加入时，各节点间仍然构成一棵多播树。树是连通无回路的，所以TM搜索的可行路径是没有回路的。

　　3.2 复杂性

　　定理3 探测时间限制机制的时间复杂度是O（|N|2×  |V|2）

　　证明：由于探测时间限制机制的计算复杂度由加入请求、加入和退出操作3部分组成，如果QoS的特征值是延迟、带宽和剩余能量，则其复杂度是O（|V|×|E|×   |V|），其中|V|是网络节点数，|E|是网络链路数，其复杂度记为O（|V|2）。对于一个具有|N|个成员的多播树，其计算复杂度O（|N|2×|V|2）。

　　4 遗传算法在QoS多播路由中的应用

　　4.1 优化目标

　　基于上述说明，QoS路由的优化目标就是在探测时间限制机制构造的多播树中，选择一条合适的路径，使得：

　　优化的目标是希望找到一条路径使得该路径的延迟最小、抖动最小、可用带宽最大、剩余电池能量最大。这几个目标的优化中，找到最优解或次优解。采用改进的遗传算法实现QoS路由问题。为此，构造目标函数F：

　接收器到发射器距离为S[7]，则从发射器发送的每比特的能量消耗为Eelec+EampS2。假设每个发射器的发送功率相同，发送距离同为S，设节点的最大能量为Efull（n），节点消耗的能量为Econsume（n），则节点的剩余能量量化百分比为E（n）=[Efull（n）-Econsume（n）]/Efull（n）。多播树的最大生命周期由一个带有最低电池能量的节点n所限制。

　　综上，通过最大化适应度值，最小化延迟时间，最大化剩余电池能量，来选择最好的路由。

　　4.2 编码机制

　　在遗传算法中最重要的步骤就是制定编码策略，本文采用二进制编码，结合深度优先遍历树的每个节点，每个染色体的解由一个二进制串表示，每个染色体的长度都为图中节点的个数n，用G（V，E）代表染色体的解s，设函数b（s，i）代表s的第i位。

　　如果b（s，i）=1，则vi∈V；

　　如果b（s，i）=0，则viV；

　　如果vi∈V，vj∈V，且（vi，vj）∈E，则eij∈E。

　　4.3 选择操作

　　本文中的遗传算法采用赌轮选择机制，将当前代的解群中适应度最高的两个个体结构完整地复制到下一代群体中。若变异概率为Pm∈（0，1），交叉概率Pc∈（0，1），且在选择前保留当前最优解的遗传算法可收敛于全局最优解[8]。可知该遗传算法可以收敛于全局最优解。

　　4.4交叉和变异操作

　　在遗传算法中的交叉算子使用单点交叉算法，变异算子使用位变异算法，交叉概率为Pc，变异概率为Pm，交叉时随机选定一个交叉点，对该点前或后的两个个体的结构进行互换，生成两个新个体，位变异算法中低能量节点被高能量节点所代替。

5 仿真与实验

　　本实验基于NS-2仿真工具，在仿真中，使100个节点随机分布在1 000 m×1 000 m的矩形区域内，每个节点的接口带宽为2 Mb/s，无线直接通信的距离为250 m，数据包大小为512 B，在实验中指定一个节点为源节点，向其他节点发送数据，每次实验执行300 s，模拟结果为多次实验的平均值。

　　组播自组网按需距离矢量路由协议MAODV（Multicast Adhoc On-demand Distance VectorRouting Protocol）是一种基于树的组播路由协议，这种按需的路由技术有效地减轻了网络信道中协议控制包的负载，提高了信道利用率[9]。将新算法与MAODV进行比较，结果如下。

　　随着节点移动速度的提高，路由更新次数增多，网络拓扑变化频繁，分组转发时间变长，端到端的平均延时也逐渐增大。仿真结果如图1所示。

　　新算法的延时性要优于MAODV，因为新算法采用了探测时间限制机制，避免了无限路由的生成，缩小了QoS优化路由的范围。

6 结论

　　本文设计了一种基于遗传算法的QoS多播路由，通过引入探测时间限制有效减少路由节点和链路的寻找范围，同时降低了选择无效节点和链路的可能性。这使得在利用遗传算法对路由问题优化时，变为对多播约束树的优化，优化目标是使得多播约束树具有低延迟时间和高的剩余电池能量，采用基于树结构的编码机制，编码和解码过程易于实现。仿真结果表明，本方法是可行和有效的，且延时性要优于MAODV。

参考文献

　　[1] SUZUKI H， KOYAMA A， Implementation and evaluation of a real object-oriented communication method for ad-hoc networks[C]. Proc. of 26th IEEE International Conference on Advanced Information Networking and Application （AINA 2012）， 2012：906-911.

　　[2] BIRADAR R C， MANVI S S. Neighbor supported reliable multipath multicast routing in MANETs[J]. Journal of Network and Computer Applications， 2012，35（3）： 1074-1085.

　　[3] VALLS M G， ALONSO A， ANTONIO J. A dual-band priority assignment algorithm for dynamic QoS resource management[J]. Future Generation Computer Systems， 2012， 28（6）：902-912.

　　[4] SRIDHAR S， BASKARAN R， CHANDRASEKAR P. Energy supported AODV（EN-AODV） for QoS routing in MANET[J]. Procedia-Social and Behavioral Sciences， 2013，73（2）：294-301.

　　[5] 倪云竹，李志蜀，刘一静.基于蚁群遗传算法的QoS多播路由研究[J].计算机应用研究，2011，28（10）：3865-3868.

　　[6] ONETY R E， TADEI R， NETO O M， et al. Multiobjective optimization of MPLS-IP networks with a variable neighborhood genetic algorithm[J]. Applied Soft Computing， 2013， 13（11）：4403-4412.

　　[7] 张毅，张秀梅，陈炜，等.移动自组织网络中基于移动Agent的多约束QoS多播路由算法[J].信息与控制，2010，39（1）：47-53.

　　[8] Huang Jun， Liu Yanbing. MOEAQ： a QoS-aware multicast routing algorithm for MANET[J]. Expert Systems with Applications， 2010， 37（2）：1391-1399.

　　[9] 樊彪，施荣华.基于移动Ad-Hoc无线网络MAODV组播路由协议研究[J].计算机工程与设计，2010，31（1）：48-51.