0 引言

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

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

1 本文方法

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

1.1 網(wǎng)絡(luò)模型表示

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

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

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

1.2 遺傳算法配置

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

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

    （1）基因表示

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

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

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

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

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

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

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

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

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

    （3）選擇操作

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

    （4）交叉和變異操作

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

    （5）精英移民機制

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

    （6）記憶強化機制

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

1.3 實現(xiàn)流程

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

    本文方法實現(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(適應(yīng)度改變)

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

       End if

       If(t=tM)

        if(適應(yīng)度改變)

            從精英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，這是網(wǎng)絡(luò)仿真常用的實驗平臺。仿真實驗涉及的相關(guān)參數(shù)如表1所示。

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

2.2 性能對比

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

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

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

3 結(jié)束語

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

參考文獻

[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] 黃瓊，尹鵬飛，陽小龍，等.一種基于仿生學(xué)的MANET擁塞節(jié)點自適應(yīng)回避路由協(xié)議[J].電子學(xué)報，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)術(shù)MANET中QoS路由算法BLQRA[J].通信技術(shù)，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．廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)中心，廣東 廣州510507；

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