一種改進的移動無線自組織網(wǎng)絡路由算法

滕艷平，周浩令，王海珍，李麗麗

(齊齊哈爾大學計算機與控制工程學院，黑龍江 齊齊哈爾 161006)

1 引言

移動無線自組織網(wǎng)絡(Mobile Ad Hoc Network，MANET)是一組帶有無線收發(fā)裝置的移動節(jié)點組成的無線通信網(wǎng)絡，無需固定基礎設施，網(wǎng)絡中的節(jié)點利用自身的收發(fā)裝置交換信息，MANET因組網(wǎng)靈活使其在軍事和民用領域都得到了廣泛的應用。但隨著網(wǎng)絡規(guī)模越來越大，節(jié)點的高速移動導致網(wǎng)絡拓撲頻繁變化，路由協(xié)議的研究已成為MANET最重要的核心內(nèi)容。

按需距離矢量路由算法(Ad Hoc On-Demand Distance Vector，AODV)是一種專為MANET設計的路由協(xié)議，AODV路由協(xié)議結合了DSR路由協(xié)議和DSDV路由協(xié)議的優(yōu)點，對高速移動的環(huán)境適應性高，但是其在路由請求時直接使用洪泛廣播RREQ，且直接選擇路由跳數(shù)最少的鏈路，并沒有考慮到網(wǎng)絡拓撲的頻繁變化導致鏈路中斷，以及在節(jié)點數(shù)量較多時，由于網(wǎng)絡洪泛導致的廣播風暴對網(wǎng)絡性能的影響。選擇穩(wěn)定性高的路由是提高網(wǎng)絡性能的一個有效措施。文中提出了一種基于GPS信息和Q學習相結合的AODV改進算法，即GQ-AODV。該算法同時考慮了節(jié)點位置和節(jié)點速度，采用節(jié)點位置計算偏差角度和前程值，節(jié)點與下一跳節(jié)點的相對速度來確定鏈路穩(wěn)定度，最優(yōu)下一跳選取可通過下一跳節(jié)點與其鄰居節(jié)點的平均相對速度以及Q學習訓練的下一跳節(jié)點與其鄰居節(jié)點的歷史平均相對速度來確定，從而提高了網(wǎng)絡的整體性能。

2 基于距離和速度的度量定義

當?shù)乩砦恢每捎玫臅r候，下一跳選擇主要依賴兩個指標：有效度量和穩(wěn)定度量。下面分別給出有效度量和穩(wěn)定度量的相關定義。

2.1 有效度量

下一跳節(jié)點選取在目的節(jié)點方向上具備較大前程量并且偏差角度較小的鄰居節(jié)點。文獻[5]提出了二維前程策略，如圖1所示，為當前節(jié)點，為目的節(jié)點，為的某鄰居節(jié)點。有效度量如式(1)所示。其中前程值(如式(3))為節(jié)點在直線上的投影長度，偏差量(如式(4))為節(jié)點到直線的距離。由于∈(-，)，∈(0，)(其中為節(jié)點通信半徑)，所以對其做(0，1)標準化(如式(5))，前程值和偏差量(0，1)標準化的結果如式(6)和式(7)。

圖1 二維前程策略

=(+(1-))

(1)

其中∈(0，1)，式中及下文中的sigmoid函數(shù)(如式(2))，主要是為了歸一化各項數(shù)據(jù)，便于各項指標的疊加。

(2)

(3)

(4)

其中表示節(jié)點和節(jié)點之間的距離。

(5)

(6)

(7)

2.2 穩(wěn)定度量

當?shù)乩砦恢每捎玫臅r候，下一跳節(jié)點應選取穩(wěn)定的鄰居節(jié)點，這樣鏈路更穩(wěn)定，路徑不易斷開，網(wǎng)絡更加健壯。穩(wěn)定度量 (如式(8))使用三個指標：此節(jié)點和下一跳節(jié)點的相對速度、下一跳節(jié)點與鄰居節(jié)點的平均相對速度以及下一跳節(jié)點與鄰居節(jié)點的歷史平均相對速度。其中下一跳節(jié)點與鄰居節(jié)點的平均相對速度和下一跳節(jié)點與鄰居節(jié)點的歷史平均相對速度是為了避免路由下一跳選擇陷入局部最優(yōu)。

=-(·()+

·()+·())

(8)

其中++=1。

221 相對速度

相對速度指此節(jié)點和下一跳節(jié)點的相對速度，見圖1，當節(jié)點在鄰居節(jié)點中選取下一跳節(jié)點時，相對于的速度，見式(9)，下一跳選取相對速度越小的節(jié)點，則鏈路越穩(wěn)定，越不容易中斷，網(wǎng)絡越健壯。

(9)

222 平均相對速度

平均相對速度指下一跳節(jié)點與鄰居節(jié)點的平均相對速度，見式(10)。當鄰居節(jié)點與其所有鄰居節(jié)點的平均相對速度越小，則節(jié)點越穩(wěn)定；選取穩(wěn)定的節(jié)點作為下一跳節(jié)點，鏈路不易斷開，其網(wǎng)絡性能越好。

(10)

其中代表節(jié)點鄰居節(jié)點的總數(shù)，代表第個節(jié)點。

223 歷史平均相對速度

歷史平均相對速度指下一跳節(jié)點與鄰居節(jié)點的相對穩(wěn)定程度，見式(11)，通過接收HELLO包采用強化學習中的Q學習來訓練QB。

+1(，)=

((，)+(+1+max(+1，)))

(11)

其中是學習因子，且∈(0，1)。是折扣因子，且∈(0，1)。+1是+1時刻的獎賞，見式(12)。當節(jié)點收到包時，獲取其當前平均相對速度+1，然后與上一時刻的作差，當時刻的平均相對速度和+1時刻的平均相對速度相差較小時，其相對穩(wěn)定程度越大；同時，接收包越頻繁，其穩(wěn)定程度越大。

(12)

3 GQ-AODV算法的設計與實現(xiàn)

3.1 數(shù)據(jù)包結構的修改

為了使用節(jié)點的位置和速度信息，在原有包結構的基礎上，對RREQ和RREP兩個包結構進行了修改，增加了位置和速度等相關信息。

3.1.1 定義路由請求(RREQ)包數(shù)據(jù)結構

為了降低網(wǎng)絡開銷，避免網(wǎng)絡擁塞，在路由請求()包消息格式中增加目的節(jié)點坐標和速度信息(、、、、)、源節(jié)點坐標和速度信息(、、、、)以及路由度量值(、)16個字節(jié)的信息。

312 定義路由回復()包數(shù)據(jù)結構

在路由請求()包消息格式中增加目的節(jié)點坐標和速度信息(、、、)、鄰居節(jié)點的平均相對速度(NeighborAverageRelativeSpeed)和路由度量值(、)11個字節(jié)的信息。消息格式被包復用。

313 定義鄰居表和路由表數(shù)據(jù)結構

當接收到包時，新增的信息格式有鄰居節(jié)點的位置及速度信息、平均相對速度和歷史平均相對速度，為了存儲這些信息，鄰居表增加、、、、平均相對速度和歷史平均相對速度。

當接收到包和包時，新增的信息格式有節(jié)點的位置及速度信息，為了存儲這些信息，路由表新增、、、和變量。

3.2 GQ-AODV算法的實現(xiàn)流程

321 下一跳節(jié)點選取策略

GQ-AODV算法是在AODV的基礎上進行改進。加入了節(jié)點坐標和節(jié)點速度的地理位置信息。GQ-AODV算法改進了鄰居表和路由表，當?shù)乩砦恢貌豢捎脮r使用原AODV洪泛請求目的節(jié)點位置信息。當?shù)乩砦恢每捎玫臅r候使用Q學習轉發(fā)策略，其下一跳選取應滿足以下條件：

1) 在目的節(jié)點方向上較小偏差角度；

2) 在目的節(jié)點方向上較大前程值；

3) 在所有鄰居節(jié)點中此節(jié)點和下一跳節(jié)點的相對速度較??；

4) 下一跳節(jié)點與其鄰居節(jié)點的當前平均速度較??；

5) 下一跳節(jié)點與其鄰居節(jié)點的歷史平均速度較小(Q值)。

GQ-AODV算法使用地理位置信息以及節(jié)點間相對速度作為下一跳選擇的度量，考慮到下一跳節(jié)點位置能夠在目的節(jié)點方向上更靠近目的節(jié)點，同時考慮到節(jié)點移動性對網(wǎng)絡拓撲穩(wěn)定性的影響，當?shù)乩砦恢每捎玫臅r候，下一跳選取主要依賴兩個指標：有效度量和穩(wěn)定度量。使用學習選擇最優(yōu)下一跳，如式(13)所示。

+1(，)=

((，)+(+1+max(+1，)))

(13)

其中是學習因子，且∈(0，1)。是折扣因子，且∈(0，1)。為路由度量，在生成時初始化為0。+1是+1時刻的獎賞，見式(14)。

+1=(·+(1-)·)

(14)

其中∈(0，1)。

3.2.2 HELLO包的發(fā)送與接收

位置和速度信息的獲取主要依賴HELLO包，同時RREQ和RREP兩數(shù)據(jù)包也會攜帶位置和速度信息。所有節(jié)點間隔HELLO＿INTERVAL定時廣播一跳HELLO包，HELLO包中攜帶節(jié)點的位置和速度等信息廣播到鄰居節(jié)點。

節(jié)點監(jiān)測上一個HELLO＿INTERVAL內(nèi)是否發(fā)送HELLO包廣播，如果沒有，節(jié)點會廣播TTL=1的RREP，即HELLO消息。節(jié)點獲取自身的GPS信息，并通過式(11)計算平均相對速度ARS，由于NS3緩存寫入和讀取不支持有符號類型，所以在這里對其做一個拆解，使用字段Sign記錄符號類型。廣播HELLO包的流程如圖2所示。

當節(jié)點接收到HELLO包時，首先對包中的無符號類型整合還原成原有符號類型。然后節(jié)點查找自己的鄰居表，若存在此節(jié)點的鄰居條目，則通過原條目中平均相對速度ARS與本次平均相對速度ARS計算出獎勵值，并通過Q學習訓練歷史平均相對速度QB；否則直接更新鄰居表和路由表。接收HELLO包的流程如圖3所示。

圖2 廣播包流程 圖3 接收HELLO包流程

3.2.3 RREQ包的發(fā)送與接收

當需要發(fā)送數(shù)據(jù)時，沒有到達目的節(jié)點的有效路由，就需要發(fā)起路由請求。在AODV的基礎上保留了原RREQ洪泛模式，當目的節(jié)點GPS信息不可用的時候，采用原AODV路由請求洪泛，尋找目的節(jié)點，并通過RREP帶回目的節(jié)點的GPS信息。

發(fā)送RREQ消息流程如圖4所示。當需要發(fā)送RREQ包時，首先獲取節(jié)點自身的GPS信息；當不存在目的節(jié)點GPS信息時，節(jié)點采用原AODV 洪泛模式尋找目的節(jié)點；當目的節(jié)點GPS信息可用時，根據(jù)式(1)選擇最優(yōu)下一跳，調(diào)用SendRequest()，初始化RREQ并發(fā)送。

圖4 發(fā)送RREQ包流程

圖5 接收RREQ包流程

當節(jié)點接收到RREQ包時，其流程如圖5所示。首先更新路由表和鄰居表。若此節(jié)點是目的節(jié)點或者存在到目的節(jié)點的路由時，回復RREP；否則，判斷RREQ消息中目的節(jié)點GPS信息是否有效，如果無效，則收到的RREQ是原始AODV洪泛的消息，則采取原AODV洪泛時的路由策略；若RREQ消息中目的節(jié)點的GPS信息有效，則根據(jù)式(1)選擇最優(yōu)下一跳，轉發(fā)RREQ消息。

4 NS3仿真與對比分析

為了驗證GQ-AODV算法與AODV性能優(yōu)劣，在Ubuntu18.04下使用Network Simulator 3(3.29)仿真平臺。對兩種算法進行仿真及對比分析。仿真場景參數(shù)如表1所示。

無線網(wǎng)絡協(xié)議性能評價指標使用平均端到端延時、抖動、平均分組投遞率、平均吞吐量和歸一化路由開銷。

表1 仿真場景參數(shù)

4.1 節(jié)點數(shù)量對網(wǎng)絡性能的影響

本節(jié)仿真主要觀察節(jié)點數(shù)量對路由協(xié)議性能的影響，實驗變量設置如表2所示。在表1仿真場景下進行的實驗。仿真結果如圖6所示。

表2 實驗變量

對比分析：圖6(a)顯示了平均端到端時延與節(jié)點數(shù)量的關系。圖6(b)顯示了網(wǎng)絡抖動與節(jié)點數(shù)量的關系。由圖6(a)(b)可知，隨著節(jié)點數(shù)量的增加，AODV協(xié)議抖動和端到端時延都隨之增加，GQ-AODV協(xié)議抖動和端到端時延基本保持平穩(wěn)，且GQ-AODV的端到端時延和抖動遠低于AODV。這是因為隨著節(jié)點密度的增大，路由請求洪泛會造成鏈路占用率高，可能會造成擁塞，增加端到端時延和抖動。而GQ-AODV選擇最優(yōu)下一跳節(jié)點，避免洪泛引起的擁塞。GQ-AODV算法在選擇下一跳時，其跳數(shù)并不會隨著節(jié)點密度的增加而增加，在節(jié)點密集時，路由下一跳可選擇的節(jié)點多，會選擇出更優(yōu)的下一跳節(jié)點，所以其端到端時延和抖動基本保持平穩(wěn)并且低于AODV。

圖6(c)顯示了平均分組投遞率與節(jié)點數(shù)量的關系。圖6(d)顯示了平均吞吐量與節(jié)點數(shù)量的關系。由圖6(c)(d)可知，隨著節(jié)點數(shù)量的增加，兩種協(xié)議分組投遞率和吞吐量都會隨著減少，其中GQ-AODV的分組投遞率和吞吐量基本高于AODV。相比AODV的洪泛機制，GQ-AODV在選擇下一跳節(jié)點時，考慮了與下一跳節(jié)點的相對速度、下一跳節(jié)點與其鄰居節(jié)點的平均相對速度以及下一跳節(jié)點與其鄰居節(jié)點的歷史平均相對速度，所以其鏈路穩(wěn)定性更強，不容易中斷，可以維持一個比較好的分組投遞率和吞吐量。

圖6 不同節(jié)點數(shù)量對兩路由協(xié)議性能影響

圖6(e)顯示了歸一化路由開銷與節(jié)點數(shù)量的關系。由圖6(e)可知，AODV協(xié)議的歸一化路由開銷遠大于GQ-AODV協(xié)議，且隨著節(jié)點數(shù)量的增加，AODV歸一化開銷的增長速度原大于GQ-AODV協(xié)議。隨著節(jié)點數(shù)量的增加，節(jié)點密度隨著增大，節(jié)點的鄰居節(jié)點也會增加，AODV協(xié)議路由請求時采用洪泛機制，鄰居節(jié)點廣播導致了其路由包數(shù)量也隨著增加。而GQ-AODV協(xié)議在地理位置可用時，避免使用廣播，直接選擇最優(yōu)下一跳節(jié)點，這就有效降低了歸一化路由開銷。

4.2 節(jié)點最大移動速度對網(wǎng)絡性能的影響

本節(jié)仿真主要觀察節(jié)點最大移動速度對路由協(xié)議性能的影響，實驗變量設置如表3所示。在表1仿真場景下進行的實驗。仿真結果如圖7所示。

表3 實驗變量

對比分析：圖7(a)顯示了平均端到端時延與節(jié)點最大移動速度的關系。圖7(b)顯示了網(wǎng)絡抖動與最大移動速度的關系。由圖7(a)(b)可知，GQ-AODV協(xié)議的時延和抖動遠低于AODV協(xié)議，且隨著節(jié)點最大移動速度的增加而緩慢增大。這是因為當?shù)乩砦恢每捎脮r，節(jié)點選擇最優(yōu)下一跳，鏈路不易斷開，更穩(wěn)定，端到端時延和抖動主要來自于隊列分組等待和重傳機制，所以GQ-AODV協(xié)議的端到端時延和抖動遠小于AODV協(xié)議，但是隨著節(jié)點最大移動速度的增加，鏈路中斷的概率增大，所以其隨著節(jié)點最大移動速度的增大而緩慢增大。

圖7 不同節(jié)點最大移動速度對兩路由協(xié)議性能影響

圖7(c)顯示了平均分組投遞率與節(jié)點最大移動速度的關系。圖7(d)顯示了平均吞吐量與節(jié)點最大移動速度的關系。由圖7(c)(d)可知，GQ-AODV協(xié)議的平均投遞率和吞吐量均大于AODV協(xié)議，這是因為AODV在路由請求階段采用了洪泛，而GQ-AODV使用GPS信息選取穩(wěn)定的最優(yōu)下一跳，所以其平均分組投遞率和吞吐量要大于AODV協(xié)議。

圖7(e)顯示了歸一化路由開銷與節(jié)點最大移動速度的關系。由圖7(e)可知，GQ-AODV協(xié)議的歸一化路由開銷遠小于AODV協(xié)議，這是因為AODV協(xié)議在路由請求階段采用洪泛，而GQ-AODV協(xié)議使用GPS信息選取最優(yōu)下一跳，這樣就會省去很多的開銷，而且GQ-AODV協(xié)議通過節(jié)點與其下一跳節(jié)點的相對速度、下一跳節(jié)點與其鄰居節(jié)點的平均相對速度以及下一跳節(jié)點與其鄰居節(jié)點間的歷史平均相對速度選取最穩(wěn)定的鏈路，這樣鏈路穩(wěn)定性增大，鏈路斷開的可能性減小，避免了頻繁的路由請求，從而使得GQ-AODV協(xié)議的歸一化路由開銷低于AODV協(xié)議。

5 結論

在對現(xiàn)有的AODV路由算法分析和研究基礎上，本文提出了一種基于GPS信息和Q學習相結合的AODV改進方案。GQ-AODV算法使用有效度量和穩(wěn)定度量來選擇最優(yōu)下一跳節(jié)點，對接收的HELLO包通過Q學習訓練鄰居節(jié)點的歷史平均相對速度，以便在發(fā)送RREQ包時可獲取最優(yōu)路由。NS3仿真結果表明，隨著節(jié)點數(shù)量的增加以及節(jié)點最大移動速度的增大，GQ-AODV算法比AODV算法能更好的適應移動無線自組織網(wǎng)絡的各種場景，其網(wǎng)絡性能各項指標均有很大提升。