0 引言

    移动自组织网络（Mobile Ad hoc network，MANET）是一种节点可以自由移动的自组织网络，与传统的有基站的无线网络相比，此类网络没有中心，不需要基础设施配合，网络组建灵活，建设成本低，非常适用于资源受限的场合，譬如军事侦察和抢险救灾等领域^[1-3]。常用的移动自组织网络路由协议主要包括AODV和DSR两类，这两类路由协议的突出特点是按需构建路由，适用范围很广^[4-7]。但对于移动自组织网络而言，解决负载不平衡节点之间的能量有效利用问题是一个非常关键的技术难题。在移动自组织网络中，共享过载和空闲的节点之间的负载是非常必要的^[8]。因此，在构建移动自组织网络的路由时应当关注负载均衡问题。而经典的AODV和DSR路由协议没有考虑这一问题。文献[9]对经典的AODV路由协议进行改进，在构建路由时关注节点的能量损耗情况，以节点的剩余能量作为中继节点选取的重要参考，这在一定程度上均衡了负载，增强了网络的稳定性。文献[10]提出一种面向战术移动自组织网络的基于节点可用带宽接入门限及负载均衡的QoS路由算法，该方法借鉴蚁群优化的思想，通过设计改进的蚁群算法搜索出满足各QoS约束且耗费最小的路径，在网络参数动态变化的情况下，实现了源节点到目的节点满足各QoS约束条件路径的有效寻找。但总的来说，目前在解决移动自组织网络的动态负载均衡问题上，还有很多待提高的地方。

    本文借鉴遗传算法的思想，提出了一种基于遗传算法的最优路由生成方法，用于解决移动自组织网络的动态负载均衡问题。本文方法的关键是依据节点的能量和距离来构建遗传算法的适应度函数，并结合记忆强化和精英移民机制解决移动自组织网络中的动态负载均衡问题，通过选择、交叉和变异操作求解最优路由，目标是在保证报文送达率和端到端平均延时等基本网络通信指标的前提下，大幅提高网络的吞吐量。

1 本文方法

    在移动自组织网络中，网络的拓扑结构经常变化，这使得维持负载均衡变得非常困难。本文首先将移动自组织网络的动态负载均衡问题转换为一个动态优化问题。然后，结合记忆强化遗传算法和精英移民遗传算法来解决移动自组织网络中的动态负载均衡问题。其中，本文依据节点的能量和距离来构建遗传算法的适应度函数，遗传算法中的每一个个体用于表示一个可行的聚类结构，聚类的簇头依据聚类参数来选择。移民遗传算法用于保持各种群的多样性层次，记忆强化遗传算法用于存储历史拓扑结构的相关信息，通过结合两类遗传算法得到高效的聚类结构，以便适应移动自组织网络拓扑结构的变化。

1.1 网络模型表示

    通常，移动自组织网络可以用一个无向图模型G(V，E)来表示，其中，V表示无线节点的集合，E表示两个邻居节点之间的无线链路的集合。

    对于无向图顶点集合中的任一节点m，与处在其通信范围内的所有邻居节点组成一个聚类集合，表示为：

    对于任一聚类集合N_m，本文选取对应能量方差最小的节点作为聚类集合Nm的簇头。该簇头综合考虑了节点剩余能量和节点距离两个指标，能有效反映节点传输能力的强弱。后续将依据簇头来设计适应度函数。

1.2 遗传算法配置

    遗传算法是解决多目标最优化问题的有效途径之一，该方法将一定数量的候选解抽象表示为种群，通过种群的遗传进化来选择最优的候选解。通常，遗传算法随机产生初始种群，然后通过选择、交叉和变异操作逐代进化，得到适应度最优的个体，实现流程如图1所示^[11]。

    本文采用遗传算法求解移动自组织网络的最优路由，通过遗传算法的适应能力来解决移动自组织网络中的动态负载均衡问题。下面结合最优路由求解问题来配置遗传算法，具体描述如下。

    （1）基因表示

    本文将移动自组织网络中的节点集合看作一个种群，表示为：

其中，A表示节点集合中的节点总数。

    这样，种群P中的每一个元素都可以表示一个基因，也即，移动自组织网络中的每一个节点都可以表示为一个基因。

    通过多个节点的排列组合，可以构建遗传算法中的染色体。染色体反映了数据传输的路由，即染色体的第一个节点为源节点，最后一个节点为目的节点，中间的所有节点都对应着每一跳的中继节点。

    长度为r（也即染色体中包含r个节点）的染色体数量可以表示为：

    这样，本文从所有的染色体集合中通过遗传算法选出最优的染色体，该染色体所对应的节点排列组合即为最优的数据传输路由。

    （2）适应度函数计算

    适应度函数用于准确评价种群的质量，本文依据聚类集合簇头的筛选准则构建适应度函数，当前染色体的适应度值可以表示为：

    在遗传算法的每一轮迭代过程中，簇头依据聚类集合中拥有最小能量方差的节点担任，通过选择簇头进行数据传输来实现网络的负载均衡。如果当前簇头耗费了大量能量，染色体的适应度值也将改变。当计算完所有染色体的适应度值之后，选择适应度值最大的染色体作为最优的簇头。

    （3）选择操作

    本文采用不放回的对偶锦标赛选择机制来提高种群的质量，将适应度值大的染色体传递给下一代。该策略选择下一代的父节点时，每次从种群中随机选择两个染色体，然后依据适应度值从中选出一个最优的染色体（也即适应度值最大的染色体），作为下一代的父节点。同时，选出的染色体不放回，也即各个染色体只能被选择一次。

    （4）交叉和变异操作

    交叉和变异基因操作用于生成子节点。经典遗传算法通过选择和变异来衍生下一个种群，然后通过从现有种群中选择合适的最佳个体来生成新的种群，再采用交叉和变异操作生成新的子节点。两个父染色体的交叉操作可以得到两个子染色体。本文采用X-Order1方法来表示每一个子染色体的基因，这些基因都是继承于两个父染色体^[12]。变异操作通过交换某一个父染色体的部分基因来生成一个子染色体。交叉和变异按照一定的概率进行，通过交叉和变异操作可以返回最佳的适应度值对应的染色体。

    （5）精英移民机制

    本文采用精英移民机制^[13]来处理移动自组织网络中的负载均衡问题，依据前一种群的精英来指导适应当前网络拓扑结构的最优个体选择。具体地，假设前一代的精英为E(t-1)，在生成当前代的个体时，在满足交叉概率的条件下通过交叉精英E(t-1)生成新的个体。

    （6）记忆强化机制

    在数据传输过程中，本文将当前网络拓扑结构的相关的最新信息存储在记忆点，以便后续拓扑结构变化到类似的结构时重复利用已存储在记忆点的路由，提高路由生成效率。该机制设计的基本原理是，尽管移动自组织网络的拓扑结构经常变化，但是在整体拓扑结构的变化过程中，网络中还存在部分甚至大量节点的局部拓扑结构不变或者变化不大，这样，这些局部拓扑结构内的数据传输可能在记忆点找到最优的路由，而不是重新计算来寻找最优路由。另外，网络的整体或者局部拓扑结构可能存在周期性变化，这种情况下更适合从记忆点中寻找最优的数据传输路由。本文采用替换策略来更新记忆点，在删除旧的记忆点时用该记忆点的种群中的适应度最大的个体来替换。本文采用随机周期的记忆更新策略，具体是按一个随机的时间周期来检测新的个体，如果该个体优于记忆点中存储的个体，则用新个体替换记忆点中存储的个体。

1.3 实现流程

    本文方法的实现流程：首先，初始化一个包含n个节点的种群，这些节点是从移动自组织网络的无线节点集合中随机选取的。然后，采用精英移民遗传算法，从中选择最优的个体集合，也即数据传输的一条路由。接着计算适应度值。如果检测到网络拓扑结构变化，存储当前种群到记忆点，并选择当前种群的精英构建新的种群。然后，采用交叉和变异操作来生成新的个体。同时，记忆点保持不变。生成一个随机整数来表示下一个记忆点更新的时间，即使拓扑结构不再变化也要按随机周期进行记忆点更新。本文所用的记忆点数量为m=0.1×n。当检测到网络拓扑结构改变时，重新评价每一代，存入对应的记忆点。当网络拓扑结构改变且检测到记忆点的某一个个体时，对应的适应度值也跟着改变。然后，记忆点与当前种群和选为临时种群的最佳的n-m个个体相融合。当记忆点保持不变时，通过执行基因操作得到新的个体，并挑选前一个种群中的精英替换当前种群中的最差个体。

    本文方法实现流程伪代码：

    初始化：初始迭代t=0；

            最大迭代次数t_max；

            随机周期t_M=rand(5，10)；

            初始种群P(0)；

            初始记忆点M(0)；

    过程：

       While(t<tmax)

       评价种群P(t)和记忆点M(t)；

       从P(t-1)中选出精英E(t-1)；

       用E(t-1)替换P(t)中的最差个体；

       If(适应度改变)

        依据P(t)和M(t)选取最优个体构建新种群；

       End if

       If(t=tM)

        if(适应度改变)

            从精英E(t-1)选取最优的个体B_p(t)；

        else 

            从种群P(t)选取最优的个体B_p(t)；

        end if 

        从记忆点选取距离B_p(t)最近的B_M(t)；

        If(f(B_p(t))>f(B_M(t)))

            用B_p(t)更新记忆点B_M(t)；

       End if

       将B_p(t)作为新的种群进行交叉变异操作；

       t_M=t+rand(5，10)；

     End if

    End while

    输出：最优染色体所代表的路由。

2 仿真实验与分析

2.1 实验说明

    本文选用的实验仿真平台为Network Simulator，这是网络仿真常用的实验平台。仿真实验涉及的相关参数如表1所示。

    下面将本文方法得到的路由与文献[9]、[10]所述方法得到的路由进行定量对比，综合报文送达率、端到端平均延时和网络吞吐量3个指标评价本文方法的性能。

2.2 性能对比

    图2给出了节点数量不同时3种方法的报文送达率指标对比情况。很明显，尽管随着节点数量的增加，3种方法的报文送达率指标都有不同程度的降低，但是，在相同节点数量的情况下，本文方法的报文送达率指标明显高于其他两种方法，这是因为本文方法通过遗传算法选取的路由的稳定性更好。

    图3给出了节点数量不同时3种方法的端到端平均延时指标的对比情况。可见，同等条件下本文方法的端到端平均延时要小于其他两种方法，且节点数量越大，本文方法的端到端平均延时指标优势越明显。究其原因，主要是本文在构建路由时采用了记忆强化遗传算法，这样，可以通过记忆点快速生成最优路由，降低了延时。

    图4给出了节点数量不同时3种方法的网络吞吐量指标的对比情况。由图4可见，本文方法的网络吞吐量指标与其他两种方法相比其优势非常明显。这是因为本文方法在构建路由时专门针对移动自组织网络拓扑结构动态变化的特性，有针对性地设计了遗传算法架构，结合能量和距离构建适应度函数，可以很好地适应网络拓扑结构的动态变化，实现动态负载均衡，因此，本文方法可以大幅提高网络的吞吐量指标。

3 结束语

    本文提出了一种基于遗传算法的最优路由生成方法，可以有效解决移动自组织网络的动态负载均衡问题。该方法将移动自组织网络的动态负载均衡问题转换为一个动态优化问题，采用遗传算法来解决该动态优化问题。具体是将移动自组织网络中的节点集合看作一个种群，将各节点看作基因，将节点的排列组合看作染色体。然后，依据节点的能量和距离来构建遗传算法的适应度函数，并结合记忆强化和精英移民机制解决移动自组织网络中的动态负载均衡问题，通过选择、交叉和变异操作求解最优路由。精英移民机制用于保持各种群的多样性层次，记忆强化机制可以利用已存储的信息快速生成最优路由，通过结合这两种机制构建的遗传算法可以很好地适应移动自组织网络拓扑结构的变化。实验结果表明，本文方法在保证高报文送达率和低端到端平均延时的前提下，可以大幅提高网络的吞吐量。

参考文献

[1] JAIN S，AGRAWAL K.A survey on multicast routing protocols for Mobile Ad Hoc networks[J].International Journal of Computer Applications，2014，96(1)：27-32.

[2] ABDEL-HALIM I T，FAHMY H M A，BAHAA-ELDIN A M.Agent-based trusted on-demand routing protocol for mobile ad-hoc networks[J].Wireless Networks，2015，21(2)：467-483.

[3] SIVANESAN P，THANGAVEL S.HMM based resource allocation and fuzzy based rate adaptation technique for MANET[J].Optik-International Journal for Light and Electron Optics，2015，126(3)：331-336.

[4] PATNAIK A，RANA K，RAO R S，et al.An efficient route repairing technique of Aodv protocol in Manet[J].Smart Innovation Systems & Technologies，2014，2(28)：113-121.

[5] 李向丽，李超超.基于小世界理论和QoS支持的DSR协议[J].传感器与微系统，2014，33(2)：43-46.

[6] YASSEIN M B，KHALAF M B，AL-DUBAI A Y.A new probabilistic broadcasting scheme for mobile ad hoc ondemand distance vector(AODV) routed networks[J].Journal of Supercomputing，2014，53(1)：196-211.

[7] KHEMCHANDANI M A，BALKHANDE B W.Comparative analysis of AntHocNet，AODV，DSR routing protocols for improvising loss packet delivery factor[J].International Journal of Computer Science & Information Technolo，2014，17(3)：235-246.

[8] 黄琼，尹鹏飞，阳小龙，等.一种基于仿生学的MANET拥塞节点自适应回避路由协议[J].电子学报，2012，40(4)：710-716.

[9] ZHAN G，SHI W，DENG J.Design and implementation of TARF：A trust-aware routing framework for WSNs[J].IEEE Transactions on Dependable & Secure Computing，2012，9(2)：184-197.

[10] 杨绪彬，张文强，郑翔，等.一种战术MANET中QoS路由算法BLQRA[J].通信技术，2016，49(3)：318-324.

[11] RAUWOLF G A，COVERSTONECARROLL V L.Nearoptimal low-thrust orbit transfers generated by a genetic algorithm[J].Journal of Spacecraft & Rockets，2015，33(6)：859-862.

[12] ZHAO X，HUNG W N N，YANG Y，et al.Optimizing communication in mobile ad hoc network clustering[J].Computers in Industry，2013，64(7)：849-853.

[13] ZHANG Y，YANG J，LU Y.The novel adaptive genetic algorithms based on the elitist and immigration strategy[J].Computer Applications in Engineering Education，2014，46(31)：36-38.

作者信息：

李  梅1，武海燕2，奚建清3，蔡建轩1

（1．广东农工商职业技术学院 网络中心，广东 广州510507；

2.铁道警察学院 公安技术系，河南 郑州450000；3．华南理工大学 软件学院，广东 广州510006）