0 引言

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

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

1 本文方法

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

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

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

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

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

1.2 遺傳算法配置

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

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

    （1）基因表示

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

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

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

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

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

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

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

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

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

    （3）選擇操作

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

    （4）交叉和變異操作

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

    （5）精英移民機(jī)制

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

    （6）記憶強(qiáng)化機(jī)制

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

1.3 實(shí)現(xiàn)流程

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

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

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

            最大迭代次數(shù)t_max；

            隨機(jī)周期t_M=rand(5，10)；

            初始種群P(0)；

            初始記憶點(diǎn)M(0)；

    過程：

       While(t<tmax)

       評價(jià)種群P(t)和記憶點(diǎn)M(t)；

       從P(t-1)中選出精英E(t-1)；

       用E(t-1)替換P(t)中的最差個(gè)體；

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

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

       End if

       If(t=tM)

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

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

        else 

            從種群P(t)選取最優(yōu)的個(gè)體B_p(t)；

        end if 

        從記憶點(diǎn)選取距離B_p(t)最近的B_M(t)；

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

            用B_p(t)更新記憶點(diǎn)B_M(t)；

       End if

       將B_p(t)作為新的種群進(jìn)行交叉變異操作；

       t_M=t+rand(5，10)；

     End if

    End while

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

2 仿真實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)說明

    本文選用的實(shí)驗(yàn)仿真平臺為Network Simulator，這是網(wǎng)絡(luò)仿真常用的實(shí)驗(yàn)平臺。仿真實(shí)驗(yàn)涉及的相關(guān)參數(shù)如表1所示。

    下面將本文方法得到的路由與文獻(xiàn)[9]、[10]所述方法得到的路由進(jìn)行定量對比，綜合報(bào)文送達(dá)率、端到端平均延時(shí)和網(wǎng)絡(luò)吞吐量3個(gè)指標(biāo)評價(jià)本文方法的性能。

2.2 性能對比

    圖2給出了節(jié)點(diǎn)數(shù)量不同時(shí)3種方法的報(bào)文送達(dá)率指標(biāo)對比情況。很明顯，盡管隨著節(jié)點(diǎn)數(shù)量的增加，3種方法的報(bào)文送達(dá)率指標(biāo)都有不同程度的降低，但是，在相同節(jié)點(diǎn)數(shù)量的情況下，本文方法的報(bào)文送達(dá)率指標(biāo)明顯高于其他兩種方法，這是因?yàn)楸疚姆椒ㄍㄟ^遺傳算法選取的路由的穩(wěn)定性更好。

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

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

3 結(jié)束語

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

參考文獻(xiàn)

[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é)點(diǎn)自適應(yīng)回避路由協(xié)議[J].電子學(xué)報(bào)，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] 楊緒彬，張文強(qiáng)，鄭翔，等.一種戰(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）