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

劉之濱，趙欣然

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

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

1 蟻群算法

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

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

圖1 信息選取原則

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

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

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

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

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

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

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

圖2 路由避障示意圖

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

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

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

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

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

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

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

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

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

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

圖3 螞蟻最優(yōu)路徑示意圖

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

5 實驗研究

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

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

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

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

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

6 結(jié)束語

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