基于蟻群算法的移動(dòng)自組網(wǎng)AODV 路由協(xié)議動(dòng)態(tài)優(yōu)化

劉之濱，趙欣然

（1.國(guó)家電網(wǎng)公司華北分部，北京 100053；2.中國(guó)核電工程有限公司，北京 100840）

移動(dòng)自組網(wǎng)是一種具有多結(jié)構(gòu)的無(wú)線網(wǎng)絡(luò)，可以在沒有基礎(chǔ)設(shè)備的情況下正常運(yùn)行，常常應(yīng)用在搶險(xiǎn)救災(zāi)、地勢(shì)復(fù)雜等環(huán)境中，其網(wǎng)絡(luò)的散布點(diǎn)較為均勻，但是會(huì)受到通信線路的信號(hào)數(shù)據(jù)限制。需要具有穩(wěn)定的協(xié)議改變通信線路動(dòng)態(tài)信道，才能實(shí)現(xiàn)更高效率的移動(dòng)自組網(wǎng)AODV 路由協(xié)議運(yùn)行狀態(tài)。平面距離向量在一定自組網(wǎng)中可以按照路由協(xié)議進(jìn)行規(guī)定的數(shù)據(jù)傳輸，收集網(wǎng)絡(luò)節(jié)點(diǎn)中的緩存數(shù)據(jù)。當(dāng)路由協(xié)議產(chǎn)生異常時(shí)，故障節(jié)點(diǎn)將依照某些算法建立通信環(huán)境。文獻(xiàn)[1]中提出一種樹形移動(dòng)自組網(wǎng)SODV 路由協(xié)議，實(shí)現(xiàn)了數(shù)據(jù)節(jié)點(diǎn)與數(shù)據(jù)節(jié)點(diǎn)之間的跳數(shù)傳輸，避免了通信線路干擾，但是在節(jié)點(diǎn)與節(jié)點(diǎn)之間數(shù)據(jù)感應(yīng)的同時(shí)，需要大量的能量作為支撐，且傳輸后的節(jié)點(diǎn)不可再用。為此，該文提出移動(dòng)自組網(wǎng)AODV 路由協(xié)議動(dòng)態(tài)優(yōu)化方法，從節(jié)點(diǎn)的數(shù)據(jù)獲取到路由協(xié)議動(dòng)態(tài)頻率的閾值設(shè)定，再到最后的實(shí)驗(yàn)結(jié)果證明，蟻群算法在路由協(xié)議優(yōu)化中具有優(yōu)勢(shì)，提升了數(shù)據(jù)包在協(xié)議中的動(dòng)態(tài)交付率。

1 蟻群算法

蟻群算法主要通過一組螞蟻在一定的空間中進(jìn)行最優(yōu)解探索，探索出的最短路徑可以是蟻群算法在路由中的標(biāo)準(zhǔn)動(dòng)態(tài)協(xié)議。蟻群開始探索要具備完整的起始網(wǎng)絡(luò)節(jié)點(diǎn)，再應(yīng)用概率模型決定螞蟻在信道中的出發(fā)點(diǎn)，出發(fā)后每尋找到一個(gè)節(jié)點(diǎn)便會(huì)對(duì)數(shù)據(jù)進(jìn)行收斂，收斂公式如下：

式中，t代表信息素，α代表算法在協(xié)議中的驗(yàn)證信息，該信息具有強(qiáng)化路徑的作用，β代表每個(gè)節(jié)點(diǎn)中剩余的信息素，p(t)代表螞蟻探索過程中向下一節(jié)點(diǎn)的探索概率。信息選取原則如圖1 所示。

圖1 信息選取原則

每只螞蟻在進(jìn)行路徑探尋過程中均會(huì)利用目標(biāo)節(jié)點(diǎn)設(shè)置自身的相關(guān)信息，達(dá)到目標(biāo)節(jié)點(diǎn)對(duì)路徑信息求解的作用，還可以實(shí)現(xiàn)路徑數(shù)據(jù)的反向計(jì)算，獲取信息素在路徑中的衰減程度和信息素累積量[2]。螞蟻對(duì)獨(dú)立數(shù)據(jù)環(huán)境會(huì)留下更高質(zhì)量的信息素，體現(xiàn)數(shù)據(jù)的重要程度，后續(xù)的蟻群將會(huì)在衰減程度較低的方向跟進(jìn)，這種方法體現(xiàn)在局部最優(yōu)解較為適合[3-4]。該文將蟻群算法中的實(shí)施界面更換為二維平面拓?fù)洌奖銛?shù)據(jù)節(jié)點(diǎn)的集合，還可以在平面中進(jìn)行任意移動(dòng)自組網(wǎng)的通信線路建立，每條線路均具有獨(dú)立的延時(shí)、帶寬等通信參數(shù)，方便螞蟻算法在路由協(xié)議中的動(dòng)態(tài)數(shù)據(jù)傳輸，并將信息素同時(shí)投入多條節(jié)點(diǎn)路徑中[5-6]。

2 移動(dòng)自組網(wǎng)AODV路由信息選取

蟻群算法在移動(dòng)自組網(wǎng)AODV 路由中首先要進(jìn)行路徑信息的選擇，建立路徑信息選擇規(guī)則，利用單元網(wǎng)格的形式設(shè)定目標(biāo)路徑信息的位置，防止大數(shù)據(jù)環(huán)境下的障礙數(shù)據(jù)干擾[7-8]。路由協(xié)議中的路徑信息為數(shù)字格式，采用坐標(biāo)手法對(duì)路徑信息進(jìn)行空間內(nèi)標(biāo)定與信息轉(zhuǎn)換。采用的坐標(biāo)法可以將路徑信息內(nèi)的節(jié)點(diǎn)位置建設(shè)在預(yù)期目標(biāo)環(huán)境中，針對(duì)關(guān)鍵信息再次制定可以融入信息素的信息選取規(guī)則[9]。假設(shè)單元網(wǎng)格可以儲(chǔ)存三維空間數(shù)據(jù)，則引入的二維空間數(shù)據(jù)要根據(jù)序號(hào)進(jìn)行分類，如下所示為二維空間中一條路徑信息在三維空間顯示的內(nèi)容：

式（2）中，l代表單元網(wǎng)格數(shù)量，x、y分別代表線路信息在單元網(wǎng)格中的橫、縱坐標(biāo)，a代表每個(gè)單元網(wǎng)格邊長(zhǎng)，b代表螞蟻對(duì)路徑信息的獲取方向[10-11]。當(dāng)單元網(wǎng)格中的路徑信息較多時(shí)，還需要應(yīng)用蟻群算法設(shè)置關(guān)鍵路徑節(jié)點(diǎn)數(shù)據(jù)，設(shè)置方式如下所示：

式（3）中，λ代表兩個(gè)相鄰節(jié)點(diǎn)之間的信息素濃度，h代表信息素的啟發(fā)因子，λ(s)代表信息濃度啟發(fā)函數(shù)，h(s)代表信息素啟發(fā)函數(shù)，R代表在單元網(wǎng)格空間內(nèi)的全部信息選規(guī)則。綜上所述，對(duì)移動(dòng)自組網(wǎng)AODV 路由信息的選取，可以通過建立單元網(wǎng)格的方式，引入蟻群算法作為信息傳輸?shù)倪x取方式，確保算法的后續(xù)計(jì)算具備穩(wěn)定的數(shù)據(jù)環(huán)境。

3 設(shè)置路由頻率動(dòng)態(tài)移動(dòng)規(guī)則

路由在完成數(shù)據(jù)選取后，第一時(shí)間將數(shù)據(jù)上傳至蟻群算法結(jié)構(gòu)中，在數(shù)據(jù)輸送過程中會(huì)有節(jié)點(diǎn)障礙，需要在路由中設(shè)置避障規(guī)則，使目標(biāo)節(jié)點(diǎn)與數(shù)據(jù)節(jié)點(diǎn)信道距離最短[12]。當(dāng)數(shù)據(jù)從數(shù)據(jù)節(jié)點(diǎn)進(jìn)入信道后，躲避的障礙數(shù)據(jù)有一定幾率延長(zhǎng)干擾信號(hào)、增加數(shù)據(jù)信道距離，因此在設(shè)置路由避障規(guī)則的同時(shí)要選擇最近線路完成傳輸。路由避障示意圖如圖2所示。

圖2 路由避障示意圖

可以參考蟻群算法的避障路徑實(shí)現(xiàn)數(shù)據(jù)傳輸線路的拓展，假設(shè)路由的初始頻率為n，在數(shù)據(jù)信道中每次遇見障礙節(jié)點(diǎn)都會(huì)調(diào)節(jié)頻率，且每次調(diào)節(jié)的頻率不同，將第一次頻率調(diào)節(jié)計(jì)為1，第二次頻率調(diào)節(jié)計(jì)為2，以此類推，逐漸尋找信道中的最佳路徑，后續(xù)跟進(jìn)傳輸?shù)穆窂侥J(rèn)選擇已知的最佳調(diào)節(jié)頻率。

不同頻率的動(dòng)態(tài)移動(dòng)規(guī)則也對(duì)應(yīng)著不同的數(shù)據(jù)傳輸路徑，但是每條路徑都是由螞蟻開發(fā)的[13-14]。因此每條路徑中的信息素在蟻群算法中均可以應(yīng)用，相似的兩條路徑可以同時(shí)應(yīng)用，擴(kuò)大信息素，增加螞蟻對(duì)傳輸數(shù)據(jù)的感知能力，使蟻群算法在路由動(dòng)態(tài)協(xié)議中進(jìn)行信息素濃度疊加，從而加強(qiáng)路由頻率動(dòng)態(tài)移動(dòng)規(guī)則的規(guī)范性。設(shè)置路由頻率動(dòng)態(tài)移動(dòng)規(guī)則總體不變，在蟻群算法控制下隨時(shí)出現(xiàn)傳輸數(shù)據(jù)方向改變、路徑轉(zhuǎn)移等情況，因此需要設(shè)置穩(wěn)定的頻率規(guī)則。

4 移動(dòng)自組網(wǎng)AODV路由協(xié)議動(dòng)態(tài)優(yōu)化

基于蟻群算法的移動(dòng)自組網(wǎng)AODV 路由協(xié)議動(dòng)態(tài)優(yōu)化主要根據(jù)路由頻率動(dòng)態(tài)設(shè)置和移動(dòng)規(guī)則進(jìn)行路徑規(guī)劃。路由在進(jìn)行數(shù)據(jù)通信傳輸過程中，會(huì)受到所在環(huán)境的干擾，干擾或障礙的存在位置具有不確定性。因此，需要利用蟻群算法對(duì)移動(dòng)自組網(wǎng)AODV 路由協(xié)議動(dòng)態(tài)進(jìn)行路徑規(guī)劃和規(guī)則設(shè)置[15]。

將路由的出發(fā)點(diǎn)設(shè)為初始節(jié)點(diǎn)，確定目標(biāo)節(jié)點(diǎn)的位置所在，路由向著目標(biāo)節(jié)點(diǎn)方向出發(fā)，途中受到干擾或障礙會(huì)避開，形成符合當(dāng)下環(huán)境的動(dòng)態(tài)路徑[16]。由于遇到障礙物會(huì)重新規(guī)劃路徑，新的路線繞開障礙物會(huì)延長(zhǎng)數(shù)據(jù)通信的傳輸路程，因此也會(huì)使數(shù)據(jù)通信傳輸?shù)臅r(shí)間延長(zhǎng)。為了達(dá)到優(yōu)化路徑同時(shí)保障通信效率的目的，需要對(duì)障礙物躲避規(guī)則進(jìn)行重新設(shè)定，對(duì)于不會(huì)對(duì)通信信號(hào)造成較大影響的障礙或干擾，設(shè)置為無(wú)需躲避問題，當(dāng)通信路由遇到這一類的障礙時(shí)，不用再重新規(guī)劃其他路線，盡可能縮減通信路徑的距離。

將通信環(huán)境中的多個(gè)路徑節(jié)點(diǎn)和障礙節(jié)點(diǎn)表現(xiàn)在蟻群算法中，路徑節(jié)點(diǎn)數(shù)據(jù)整合為X=(x1,x2…xn)，障礙節(jié)點(diǎn)表示為集合Y=(y1,y2…yn)，將數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑和躲避障礙后的路徑表達(dá)出來，a代表螞蟻，D表示螞蟻經(jīng)過的路徑線路，然后能夠?qū)硐胱顑?yōu)路徑和實(shí)際最優(yōu)路徑進(jìn)行計(jì)算，分析出蟻群對(duì)不同障礙物的躲避情況：

式（4）中，q指蟻群對(duì)障礙物的識(shí)別參數(shù)，f表示對(duì)不同節(jié)點(diǎn)的識(shí)別函數(shù)，u、v是對(duì)不同節(jié)點(diǎn)坐標(biāo)的識(shí)別結(jié)果，ε表示識(shí)別出的關(guān)鍵信息數(shù)量，σ表示參與路徑識(shí)別規(guī)劃的總節(jié)點(diǎn)信息數(shù)量。經(jīng)過上述公式運(yùn)算能夠得到蟻群對(duì)該環(huán)境中障礙和路線的識(shí)別能力。得到識(shí)別能力具體數(shù)值，可以對(duì)蟻群的避障規(guī)則進(jìn)行調(diào)整，增強(qiáng)蟻群對(duì)關(guān)鍵路徑節(jié)點(diǎn)和重要障礙節(jié)點(diǎn)的信息素選取能力。

確定路由的初始節(jié)點(diǎn)，根據(jù)蟻群對(duì)所有節(jié)點(diǎn)的信息素識(shí)別能力，劃分節(jié)點(diǎn)的蟻群吸引力等級(jí)，增強(qiáng)主要障礙物節(jié)點(diǎn)的吸引等級(jí)，同時(shí)增強(qiáng)繞開關(guān)鍵障礙節(jié)點(diǎn)的最近路徑節(jié)點(diǎn)的吸引等級(jí)。調(diào)高路由對(duì)關(guān)鍵節(jié)點(diǎn)的識(shí)別敏感度，使最優(yōu)路徑范圍縮小，路由對(duì)最優(yōu)路徑的識(shí)別感知能力隨之增強(qiáng)，并且在關(guān)鍵節(jié)點(diǎn)信息素增強(qiáng)后，信息素濃度會(huì)在原來的基礎(chǔ)上進(jìn)行疊加，根據(jù)疊加后的信息素濃度數(shù)值計(jì)算各節(jié)點(diǎn)的濃度變化差值：

式（5）中，Δk是信息素濃度差值，η為信息素的發(fā)散系數(shù)，α為蟻群路徑的誤差值域，h為計(jì)算路徑的總長(zhǎng)度，Eij表示蟻群感知到的信息素疊加后的總值。根據(jù)上式計(jì)算所得信息對(duì)最優(yōu)路徑進(jìn)行判定：

式（6）中，L表示所得路徑結(jié)果，Lij為初始規(guī)劃的參照路徑。根據(jù)計(jì)算結(jié)果，若滿足要求，則計(jì)算路徑為最優(yōu)路徑，如果計(jì)算結(jié)果為0，則不是最優(yōu)路徑。螞蟻?zhàn)顑?yōu)路徑示意圖如圖3 所示。

圖3 螞蟻?zhàn)顑?yōu)路徑示意圖

以此能夠得到更加科學(xué)合理的路由傳輸路徑[17-18]，實(shí)現(xiàn)了移動(dòng)路由協(xié)議動(dòng)態(tài)的優(yōu)化。

5 實(shí)驗(yàn)研究

以計(jì)算機(jī)Matlab 程序?yàn)閷?shí)驗(yàn)軟件，對(duì)路由數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)識(shí)別效率、節(jié)點(diǎn)間平均傳輸時(shí)間、傳輸速率、路徑失效率等指標(biāo)進(jìn)行了監(jiān)測(cè)。仿真實(shí)驗(yàn)采用NS2 系統(tǒng)，在550 m×550 m 網(wǎng)絡(luò)拓?fù)浞秶鷥?nèi)隨機(jī)分布20個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的最大移動(dòng)速度為10 m/s。

傳統(tǒng)路由通信在傳輸數(shù)據(jù)保持不變的情況下，路由從初始節(jié)點(diǎn)出發(fā)到范圍內(nèi)所有節(jié)點(diǎn)的速度受網(wǎng)絡(luò)速度的快慢影響。不同傳輸路徑的數(shù)據(jù)包傳輸節(jié)點(diǎn)間平均傳輸時(shí)間不變，路由的數(shù)據(jù)包發(fā)送率和接收率呈反比，網(wǎng)絡(luò)速度不變，數(shù)據(jù)發(fā)送率提高，會(huì)造成區(qū)域內(nèi)網(wǎng)絡(luò)環(huán)境擁擠，占用網(wǎng)絡(luò)資源，容易導(dǎo)致不必要的線路競(jìng)爭(zhēng)或資源混亂，加劇網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)荷，降低數(shù)據(jù)傳輸?shù)乃俣群托省?shù)據(jù)平均時(shí)延實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 數(shù)據(jù)傳輸平均時(shí)延實(shí)驗(yàn)結(jié)果

從圖4 數(shù)據(jù)傳輸時(shí)延實(shí)驗(yàn)結(jié)果來看，該文方法通過蟻群算法優(yōu)化了路徑規(guī)劃，平均時(shí)延保持在0.3～0.45 s，而傳統(tǒng)方法的平均時(shí)延高于0.7 s。因?yàn)樵撐姆椒▽?duì)不同任務(wù)的傳輸線路進(jìn)行了優(yōu)化，降低了網(wǎng)絡(luò)擁堵和節(jié)點(diǎn)負(fù)載量，從而提高了數(shù)據(jù)包的傳輸速度。

在同一網(wǎng)絡(luò)環(huán)境下，對(duì)不同數(shù)據(jù)發(fā)送率的節(jié)點(diǎn)數(shù)據(jù)包接收率進(jìn)行了監(jiān)測(cè)分析。當(dāng)數(shù)據(jù)發(fā)送率提高，網(wǎng)絡(luò)擁堵程度增加時(shí)，傳統(tǒng)通信方式的路由拓?fù)溟_銷增加，維護(hù)路由的拓?fù)湫畔?shù)據(jù)需求量增加，使通信網(wǎng)絡(luò)的不穩(wěn)定性增加，通信傳輸失敗率大大提高。而該文方法基于蟻群算法優(yōu)化了傳輸路徑，降低了通信受阻概率，使路由拓?fù)溟_銷保持在一個(gè)較低的水平，通信節(jié)點(diǎn)的變化情況比較穩(wěn)定，數(shù)據(jù)包的接收成功率較高，通信傳輸?shù)男Ч容^理想。

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

基于蟻群算法優(yōu)化后的移動(dòng)自組網(wǎng)AODV 路由在通信傳輸工作方面具有更高的工作效率，優(yōu)化后的傳輸路徑更加流暢穩(wěn)定，數(shù)據(jù)傳輸時(shí)間減少，速度有所提高。此外，網(wǎng)絡(luò)擁堵程度比傳統(tǒng)方法有所減輕，通信環(huán)境更加穩(wěn)定，節(jié)點(diǎn)變動(dòng)率下降，使信息數(shù)據(jù)的傳輸與接收成功率有明顯提升。