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）