0 引言

    移動自組織網絡（Mobile Ad hoc network,，MANET）是一種節(jié)點可以自由移動的自組織網絡,，與傳統(tǒng)的有基站的無線網絡相比，此類網絡沒有中心,，不需要基礎設施配合,，網絡組建靈活，建設成本低,，非常適用于資源受限的場合,，譬如軍事偵察和搶險救災等領域^[1-3]。常用的移動自組織網絡路由協(xié)議主要包括AODV和DSR兩類,，這兩類路由協(xié)議的突出特點是按需構建路由，適用范圍很廣^[4-7],。但對于移動自組織網絡而言,，解決負載不平衡節(jié)點之間的能量有效利用問題是一個非常關鍵的技術難題。在移動自組織網絡中,，共享過載和空閑的節(jié)點之間的負載是非常必要的^[8],。因此，在構建移動自組織網絡的路由時應當關注負載均衡問題,。而經典的AODV和DSR路由協(xié)議沒有考慮這一問題,。文獻[9]對經典的AODV路由協(xié)議進行改進，在構建路由時關注節(jié)點的能量損耗情況,，以節(jié)點的剩余能量作為中繼節(jié)點選取的重要參考,，這在一定程度上均衡了負載，增強了網絡的穩(wěn)定性,。文獻[10]提出一種面向戰(zhàn)術移動自組織網絡的基于節(jié)點可用帶寬接入門限及負載均衡的QoS路由算法,，該方法借鑒蟻群優(yōu)化的思想，通過設計改進的蟻群算法搜索出滿足各QoS約束且耗費最小的路徑,，在網絡參數(shù)動態(tài)變化的情況下,，實現(xiàn)了源節(jié)點到目的節(jié)點滿足各QoS約束條件路徑的有效尋找。但總的來說,，目前在解決移動自組織網絡的動態(tài)負載均衡問題上,，還有很多待提高的地方。

    本文借鑒遺傳算法的思想,，提出了一種基于遺傳算法的最優(yōu)路由生成方法,，用于解決移動自組織網絡的動態(tài)負載均衡問題。本文方法的關鍵是依據(jù)節(jié)點的能量和距離來構建遺傳算法的適應度函數(shù),，并結合記憶強化和精英移民機制解決移動自組織網絡中的動態(tài)負載均衡問題,，通過選擇,、交叉和變異操作求解最優(yōu)路由，目標是在保證報文送達率和端到端平均延時等基本網絡通信指標的前提下,，大幅提高網絡的吞吐量,。

1 本文方法

    在移動自組織網絡中，網絡的拓撲結構經常變化,，這使得維持負載均衡變得非常困難,。本文首先將移動自組織網絡的動態(tài)負載均衡問題轉換為一個動態(tài)優(yōu)化問題。然后,，結合記憶強化遺傳算法和精英移民遺傳算法來解決移動自組織網絡中的動態(tài)負載均衡問題,。其中，本文依據(jù)節(jié)點的能量和距離來構建遺傳算法的適應度函數(shù),，遺傳算法中的每一個個體用于表示一個可行的聚類結構,，聚類的簇頭依據(jù)聚類參數(shù)來選擇。移民遺傳算法用于保持各種群的多樣性層次,，記憶強化遺傳算法用于存儲歷史拓撲結構的相關信息,，通過結合兩類遺傳算法得到高效的聚類結構，以便適應移動自組織網絡拓撲結構的變化,。

1.1 網絡模型表示

    通常,，移動自組織網絡可以用一個無向圖模型G(V，E)來表示,，其中,，V表示無線節(jié)點的集合，E表示兩個鄰居節(jié)點之間的無線鏈路的集合,。

    對于無向圖頂點集合中的任一節(jié)點m,，與處在其通信范圍內的所有鄰居節(jié)點組成一個聚類集合，表示為：

    對于任一聚類集合N_m,，本文選取對應能量方差最小的節(jié)點作為聚類集合Nm的簇頭,。該簇頭綜合考慮了節(jié)點剩余能量和節(jié)點距離兩個指標，能有效反映節(jié)點傳輸能力的強弱,。后續(xù)將依據(jù)簇頭來設計適應度函數(shù),。

1.2 遺傳算法配置

    遺傳算法是解決多目標最優(yōu)化問題的有效途徑之一，該方法將一定數(shù)量的候選解抽象表示為種群,，通過種群的遺傳進化來選擇最優(yōu)的候選解,。通常，遺傳算法隨機產生初始種群,，然后通過選擇,、交叉和變異操作逐代進化，得到適應度最優(yōu)的個體,，實現(xiàn)流程如圖1所示^[11],。

    本文采用遺傳算法求解移動自組織網絡的最優(yōu)路由,，通過遺傳算法的適應能力來解決移動自組織網絡中的動態(tài)負載均衡問題。下面結合最優(yōu)路由求解問題來配置遺傳算法,，具體描述如下,。

    （1）基因表示

    本文將移動自組織網絡中的節(jié)點集合看作一個種群，表示為：

其中,，A表示節(jié)點集合中的節(jié)點總數(shù),。

    這樣，種群P中的每一個元素都可以表示一個基因,，也即,，移動自組織網絡中的每一個節(jié)點都可以表示為一個基因。

    通過多個節(jié)點的排列組合,，可以構建遺傳算法中的染色體,。染色體反映了數(shù)據(jù)傳輸?shù)穆酚桑慈旧w的第一個節(jié)點為源節(jié)點,，最后一個節(jié)點為目的節(jié)點,，中間的所有節(jié)點都對應著每一跳的中繼節(jié)點。

    長度為r（也即染色體中包含r個節(jié)點）的染色體數(shù)量可以表示為：

    這樣,，本文從所有的染色體集合中通過遺傳算法選出最優(yōu)的染色體，該染色體所對應的節(jié)點排列組合即為最優(yōu)的數(shù)據(jù)傳輸路由,。

    （2）適應度函數(shù)計算

    適應度函數(shù)用于準確評價種群的質量,，本文依據(jù)聚類集合簇頭的篩選準則構建適應度函數(shù)，當前染色體的適應度值可以表示為：

    在遺傳算法的每一輪迭代過程中,，簇頭依據(jù)聚類集合中擁有最小能量方差的節(jié)點擔任,，通過選擇簇頭進行數(shù)據(jù)傳輸來實現(xiàn)網絡的負載均衡。如果當前簇頭耗費了大量能量,，染色體的適應度值也將改變,。當計算完所有染色體的適應度值之后，選擇適應度值最大的染色體作為最優(yōu)的簇頭,。

    （3）選擇操作

    本文采用不放回的對偶錦標賽選擇機制來提高種群的質量,，將適應度值大的染色體傳遞給下一代。該策略選擇下一代的父節(jié)點時,，每次從種群中隨機選擇兩個染色體,，然后依據(jù)適應度值從中選出一個最優(yōu)的染色體（也即適應度值最大的染色體），作為下一代的父節(jié)點,。同時,，選出的染色體不放回，也即各個染色體只能被選擇一次,。

    （4）交叉和變異操作

    交叉和變異基因操作用于生成子節(jié)點,。經典遺傳算法通過選擇和變異來衍生下一個種群,，然后通過從現(xiàn)有種群中選擇合適的最佳個體來生成新的種群，再采用交叉和變異操作生成新的子節(jié)點,。兩個父染色體的交叉操作可以得到兩個子染色體,。本文采用X-Order1方法來表示每一個子染色體的基因，這些基因都是繼承于兩個父染色體^[12],。變異操作通過交換某一個父染色體的部分基因來生成一個子染色體,。交叉和變異按照一定的概率進行，通過交叉和變異操作可以返回最佳的適應度值對應的染色體,。

    （5）精英移民機制

    本文采用精英移民機制^[13]來處理移動自組織網絡中的負載均衡問題,，依據(jù)前一種群的精英來指導適應當前網絡拓撲結構的最優(yōu)個體選擇。具體地,，假設前一代的精英為E(t-1),，在生成當前代的個體時，在滿足交叉概率的條件下通過交叉精英E(t-1)生成新的個體,。

    （6）記憶強化機制

    在數(shù)據(jù)傳輸過程中,，本文將當前網絡拓撲結構的相關的最新信息存儲在記憶點，以便后續(xù)拓撲結構變化到類似的結構時重復利用已存儲在記憶點的路由,，提高路由生成效率,。該機制設計的基本原理是，盡管移動自組織網絡的拓撲結構經常變化,，但是在整體拓撲結構的變化過程中,，網絡中還存在部分甚至大量節(jié)點的局部拓撲結構不變或者變化不大，這樣,，這些局部拓撲結構內的數(shù)據(jù)傳輸可能在記憶點找到最優(yōu)的路由,，而不是重新計算來尋找最優(yōu)路由。另外,，網絡的整體或者局部拓撲結構可能存在周期性變化,，這種情況下更適合從記憶點中尋找最優(yōu)的數(shù)據(jù)傳輸路由。本文采用替換策略來更新記憶點,，在刪除舊的記憶點時用該記憶點的種群中的適應度最大的個體來替換,。本文采用隨機周期的記憶更新策略，具體是按一個隨機的時間周期來檢測新的個體,，如果該個體優(yōu)于記憶點中存儲的個體,，則用新個體替換記憶點中存儲的個體。

1.3 實現(xiàn)流程

    本文方法的實現(xiàn)流程：首先,，初始化一個包含n個節(jié)點的種群,，這些節(jié)點是從移動自組織網絡的無線節(jié)點集合中隨機選取的。然后,，采用精英移民遺傳算法,，從中選擇最優(yōu)的個體集合,，也即數(shù)據(jù)傳輸?shù)囊粭l路由。接著計算適應度值,。如果檢測到網絡拓撲結構變化,，存儲當前種群到記憶點，并選擇當前種群的精英構建新的種群,。然后,，采用交叉和變異操作來生成新的個體。同時,，記憶點保持不變,。生成一個隨機整數(shù)來表示下一個記憶點更新的時間，即使拓撲結構不再變化也要按隨機周期進行記憶點更新,。本文所用的記憶點數(shù)量為m=0.1×n,。當檢測到網絡拓撲結構改變時，重新評價每一代,，存入對應的記憶點,。當網絡拓撲結構改變且檢測到記憶點的某一個個體時，對應的適應度值也跟著改變,。然后,，記憶點與當前種群和選為臨時種群的最佳的n-m個個體相融合。當記憶點保持不變時,，通過執(zhí)行基因操作得到新的個體,，并挑選前一個種群中的精英替換當前種群中的最差個體,。

    本文方法實現(xiàn)流程偽代碼：

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

            最大迭代次數(shù)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(適應度改變)

        依據(jù)P(t)和M(t)選取最優(yōu)個體構建新種群,；

       End if

       If(t=tM)

        if(適應度改變)

            從精英E(t-1)選取最優(yōu)的個體B_p(t)；

        else 

            從種群P(t)選取最優(yōu)的個體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

    輸出：最優(yōu)染色體所代表的路由。

2 仿真實驗與分析

2.1 實驗說明

    本文選用的實驗仿真平臺為Network Simulator,，這是網絡仿真常用的實驗平臺,。仿真實驗涉及的相關參數(shù)如表1所示。

    下面將本文方法得到的路由與文獻[9],、[10]所述方法得到的路由進行定量對比,，綜合報文送達率、端到端平均延時和網絡吞吐量3個指標評價本文方法的性能,。

2.2 性能對比

    圖2給出了節(jié)點數(shù)量不同時3種方法的報文送達率指標對比情況,。很明顯，盡管隨著節(jié)點數(shù)量的增加,，3種方法的報文送達率指標都有不同程度的降低,，但是，在相同節(jié)點數(shù)量的情況下,，本文方法的報文送達率指標明顯高于其他兩種方法,，這是因為本文方法通過遺傳算法選取的路由的穩(wěn)定性更好。

    圖3給出了節(jié)點數(shù)量不同時3種方法的端到端平均延時指標的對比情況,?？梢姡葪l件下本文方法的端到端平均延時要小于其他兩種方法,，且節(jié)點數(shù)量越大,，本文方法的端到端平均延時指標優(yōu)勢越明顯。究其原因,，主要是本文在構建路由時采用了記憶強化遺傳算法,，這樣，可以通過記憶點快速生成最優(yōu)路由,，降低了延時,。

    圖4給出了節(jié)點數(shù)量不同時3種方法的網絡吞吐量指標的對比情況。由圖4可見,，本文方法的網絡吞吐量指標與其他兩種方法相比其優(yōu)勢非常明顯,。這是因為本文方法在構建路由時專門針對移動自組織網絡拓撲結構動態(tài)變化的特性，有針對性地設計了遺傳算法架構,，結合能量和距離構建適應度函數(shù),，可以很好地適應網絡拓撲結構的動態(tài)變化，實現(xiàn)動態(tài)負載均衡,，因此,，本文方法可以大幅提高網絡的吞吐量指標。

3 結束語

    本文提出了一種基于遺傳算法的最優(yōu)路由生成方法，可以有效解決移動自組織網絡的動態(tài)負載均衡問題,。該方法將移動自組織網絡的動態(tài)負載均衡問題轉換為一個動態(tài)優(yōu)化問題,，采用遺傳算法來解決該動態(tài)優(yōu)化問題。具體是將移動自組織網絡中的節(jié)點集合看作一個種群,，將各節(jié)點看作基因,，將節(jié)點的排列組合看作染色體。然后,，依據(jù)節(jié)點的能量和距離來構建遺傳算法的適應度函數(shù),，并結合記憶強化和精英移民機制解決移動自組織網絡中的動態(tài)負載均衡問題，通過選擇,、交叉和變異操作求解最優(yōu)路由,。精英移民機制用于保持各種群的多樣性層次，記憶強化機制可以利用已存儲的信息快速生成最優(yōu)路由,，通過結合這兩種機制構建的遺傳算法可以很好地適應移動自組織網絡拓撲結構的變化,。實驗結果表明，本文方法在保證高報文送達率和低端到端平均延時的前提下,，可以大幅提高網絡的吞吐量,。

參考文獻

[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，F(xiàn)AHMY 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協(xié)議[J].傳感器與微系統(tǒng),，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擁塞節(jié)點自適應回避路由協(xié)議[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] 楊緒彬，張文強,，鄭翔,，等.一種戰(zhàn)術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．廣東農工商職業(yè)技術學院 網絡中心,，廣東 廣州510507；

2.鐵道警察學院 公安技術系,，河南 鄭州450000,；3．華南理工大學 軟件學院，廣東 廣州510006）