《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 基于改進(jìn)的遺傳算法的MANET最優(yōu)路由生成方法
基于改進(jìn)的遺傳算法的MANET最優(yōu)路由生成方法
2017年電子技術(shù)應(yīng)用第8期
李 梅1,,武海燕2,,奚建清3,,蔡建軒1
1.廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)中心,,廣東 廣州510507; 2.鐵道警察學(xué)院 公安技術(shù)系,,河南 鄭州450000,;3.華南理工大學(xué) 軟件學(xué)院,廣東 廣州510006
摘要: 為解決移動(dòng)自組織網(wǎng)絡(luò)的動(dòng)態(tài)負(fù)載均衡問(wèn)題,,提出了一種基于遺傳算法的最優(yōu)路由生成方法,。首先,將移動(dòng)自組織網(wǎng)絡(luò)中的節(jié)點(diǎn)集合看作一個(gè)種群,,將各節(jié)點(diǎn)看作基因,,將節(jié)點(diǎn)的排列組合看作染色體。然后,,依據(jù)節(jié)點(diǎn)的能量和距離來(lái)構(gòu)建遺傳算法的適應(yīng)度函數(shù),,并結(jié)合記憶強(qiáng)化和精英移民機(jī)制解決移動(dòng)自組織網(wǎng)絡(luò)中的動(dòng)態(tài)負(fù)載均衡問(wèn)題。最終通過(guò)選擇,、交叉和變異操作求解最優(yōu)路由,。實(shí)驗(yàn)結(jié)果表明,該方法在保證高報(bào)文送達(dá)率和低端到端平均延時(shí)的前提下,,可以大幅提高網(wǎng)絡(luò)的吞吐量,。
中圖分類(lèi)號(hào): TN915;TP391
文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.166557
中文引用格式: 李梅,,武海燕,,奚建清,等. 基于改進(jìn)的遺傳算法的MANET最優(yōu)路由生成方法[J].電子技術(shù)應(yīng)用,,2017,,43(8):119-122,126.
英文引用格式: Li Mei,,Wu Haiyan,,Xi Jianqing,,et al. An optimal routing generation method for MANET based on genetic algorithm[J].Application of Electronic Technique,2017,,43(8):119-122,,126.
An optimal routing generation method for MANET based on genetic algorithm
Li Mei1,Wu Haiyan2,,Xi Jianqing3,Cai Jianxuan1
1.Network Center,,Guangdong AIB Polytechnic,,Guangzhou 510507,China,; 2.Department of Public Security technology,,Railway Police College,Zhengzhou 450000,,China,; 3.School of Software Engineering,South China University of Technology,,Guangzhou 510006,,China
Abstract: For solving the dynamic load balancing problem of mobile ad hoc network,an optimal routing generation method based on genetic algorithm is proposed. First, it takes the collection of nodes in mobile ad hoc network as a population, each node as a gene, and nodes permutation and combination as a chromosome. Then, it builds the fitness function of genetic algorithm according to the energy and distance of nodes, to solve the dynamic load balancing problem of mobile ad hoc network by combining with memory-enhancer and elite migration mechanism. Finally,,it finds the optimal routing through selection, crossover and mutation operations. Experimental results show that the method can significantly increase network throughput on the premise of high packet delivery rate and low average end-to-end delay.
Key words : routing protocols,;genetic algorithm;mobile ad hoc network,;undirected graph,;topology

0 引言

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

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

1 本文方法

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

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

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

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

jsj2-gs1-3.gif

jsj2-gs4-5.gif

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

1.2 遺傳算法配置

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

jsj2-t1.gif

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

    (1)基因表示

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

    jsj2-gs6.gif

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

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

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

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

    jsj2-gs7.gif

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

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

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

    jsj2-gs8.gif

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

    (3)選擇操作

    本文采用不放回的對(duì)偶錦標(biāo)賽選擇機(jī)制來(lái)提高種群的質(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)典遺傳算法通過(guò)選擇和變異來(lái)衍生下一個(gè)種群,然后通過(guò)從現(xiàn)有種群中選擇合適的最佳個(gè)體來(lái)生成新的種群,,再采用交叉和變異操作生成新的子節(jié)點(diǎn),。兩個(gè)父染色體的交叉操作可以得到兩個(gè)子染色體。本文采用X-Order1方法來(lái)表示每一個(gè)子染色體的基因,,這些基因都是繼承于兩個(gè)父染色體[12],。變異操作通過(guò)交換某一個(gè)父染色體的部分基因來(lái)生成一個(gè)子染色體。交叉和變異按照一定的概率進(jìn)行,,通過(guò)交叉和變異操作可以返回最佳的適應(yīng)度值對(duì)應(yīng)的染色體,。

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

    本文采用精英移民機(jī)制[13]來(lái)處理移動(dòng)自組織網(wǎng)絡(luò)中的負(fù)載均衡問(wèn)題,依據(jù)前一種群的精英來(lái)指導(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í),,在滿(mǎn)足交叉概率的條件下通過(guò)交叉精英E(t-1)生成新的個(gè)體,。

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

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

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

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

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

    初始化:初始迭代t=0,;

            最大迭代次數(shù)tmax

            隨機(jī)周期tM=rand(5,,10),;

            初始種群P(0);

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

    過(guò)程:

       While(t<tmax)

       評(píng)價(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è)體Bp(t);

        else 

            從種群P(t)選取最優(yōu)的個(gè)體Bp(t),;

        end if 

        從記憶點(diǎn)選取距離Bp(t)最近的BM(t),;

        If(f(Bp(t))>f(BM(t)))

            用Bp(t)更新記憶點(diǎn)BM(t);

       End if

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

       tM=t+rand(5,,10);

     End if

    End while

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

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

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

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

jsj2-b1.gif

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

2.2 性能對(duì)比

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

jsj2-t2.gif

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

jsj2-t3.gif

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

jsj2-t4.gif

3 結(jié)束語(yǔ)

    本文提出了一種基于遺傳算法的最優(yōu)路由生成方法,,可以有效解決移動(dòng)自組織網(wǎng)絡(luò)的動(dòng)態(tài)負(fù)載均衡問(wèn)題,。該方法將移動(dòng)自組織網(wǎng)絡(luò)的動(dòng)態(tài)負(fù)載均衡問(wèn)題轉(zhuǎn)換為一個(gè)動(dòng)態(tài)優(yōu)化問(wèn)題,采用遺傳算法來(lái)解決該動(dòng)態(tài)優(yōu)化問(wèn)題,。具體是將移動(dòng)自組織網(wǎng)絡(luò)中的節(jié)點(diǎn)集合看作一個(gè)種群,將各節(jié)點(diǎn)看作基因,,將節(jié)點(diǎn)的排列組合看作染色體,。然后,依據(jù)節(jié)點(diǎn)的能量和距離來(lái)構(gòu)建遺傳算法的適應(yīng)度函數(shù),,并結(jié)合記憶強(qiáng)化和精英移民機(jī)制解決移動(dòng)自組織網(wǎng)絡(luò)中的動(dòng)態(tài)負(fù)載均衡問(wèn)題,,通過(guò)選擇、交叉和變異操作求解最優(yōu)路由,。精英移民機(jī)制用于保持各種群的多樣性層次,,記憶強(qiáng)化機(jī)制可以利用已存儲(chǔ)的信息快速生成最優(yōu)路由,通過(guò)結(jié)合這兩種機(jī)制構(gòu)建的遺傳算法可以很好地適應(yīng)移動(dò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] 黃瓊,,尹鵬飛,,陽(yáng)小龍,等.一種基于仿生學(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)

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載,。