移动自组网中QoS多播路由的研究

郭慧（山西大学商务学院　信息学院，山西　太原 030031）

移动自组网中QoS多播路由的研究

郭慧
（山西大学商务学院信息学院，山西太原 030031）

深入研究移动自组网中的多播路由问题，提出一种适用于移动自组网的基于遗传算法的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　探测时间限制机制

多播树新成员加入的主要过程如下。其中，每个节点的请求信息由 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）对于∀L（s，v）⊆TM，有bandwidth（L（s，v））≥B；

（2）对于∀L（s，v）⊆TM，delay（L（s，v））≤D，jitter（L （s，v））≤J；

（3）对于∀L（s，v）⊆TM，有min P（u）＞P。

证明：

（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。

（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路由的优化目标就是在探测时间限制机制构造的多播树中，选择一条合适的路径，使得：

（3）min｛B（e）｝＞B

（4）min｛P（e）｝＞P

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

F=fc×fy×fx

fc是惩罚函数，用来惩罚不易解决的方案。

当σ＜0时，Δσ=1；当σ＞0时，Δσ=λ。

σ是惩罚度，通常 0.01＜σ＜0.5。当 fc=1时，寻找到的QoS路径可行；当0≤fc＜1时，QoS路由不易寻找。

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

4.2编码机制

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

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

如果b（s，i）=0，则vi∉V；

如果 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优化路由的范围。

图1　平均延时比较

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.EnergysupportedAODV（EN-AODV）forQoSroutingin 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.MultiobjectiveoptimizationofMPLS-IPnetworkswithavariable neighborhood genetic algorithm［J］.Applied Soft Computing，2013，13（11）：4403-4412.

［7］张毅，张秀梅，陈炜，等.移动自组织网络中基于移动 A-gent的多约束 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.

Research of QoS multicast routing in mobile Ad Hoc networks

Guo Hui
（Information Faculty，Business College of Shanxi University，Taiyuan 030031，China）

Though studying the multicast routing problem in mobile Ad Hoc networks，the paper proposed a QoS multicast routing algorithm based on genetic algorithm suitable mobile ad hoc networks.By limiting the detected-time，reduced the search scope of routing nodes and links，moreover，reduce the possibilities of selecting invalid nodes and links.The test provied that the method satisfies the requirements of bandwidth，delay，delay jitter，and residual energy constraint.Proposed a genetic algorithmbased optimization algorithm for QoS routing.Simulation result shows that the algorithm is feasible，and the latency is better than MAODV.

mobile Ad Hoc networks；multicast；genetic algorithm；ouality-of-service；routing algorithm

TP393.0

A

1674-7720（2015）05-0057-03

（2014-11-07）

郭慧（1980-），女，研究生，讲师，主要研究方向：网络及信息安全。