一種改進的移動無線自組織網絡路由算法

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

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

1 引言

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

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

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

當地理位置可用的時候，下一跳選擇主要依賴兩個指標：有效度量和穩定度量。下面分別給出有效度量和穩定度量的相關定義。

2.1 有效度量

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

圖1 二維前程策略

=(+(1-))

(1)

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

(2)

(3)

(4)

其中表示節點和節點之間的距離。

(5)

(6)

(7)

2.2 穩定度量

當地理位置可用的時候，下一跳節點應選取穩定的鄰居節點，這樣鏈路更穩定，路徑不易斷開，網絡更加健壯。穩定度量 (如式(8))使用三個指標：此節點和下一跳節點的相對速度、下一跳節點與鄰居節點的平均相對速度以及下一跳節點與鄰居節點的歷史平均相對速度。其中下一跳節點與鄰居節點的平均相對速度和下一跳節點與鄰居節點的歷史平均相對速度是為了避免路由下一跳選擇陷入局部最優。

=-(·()+

·()+·())

(8)

其中++=1。

221 相對速度

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

(9)

222 平均相對速度

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

(10)

其中代表節點鄰居節點的總數，代表第個節點。

223 歷史平均相對速度

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

+1(，)=

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

(11)

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

(12)

3 GQ-AODV算法的設計與實現

3.1 數據包結構的修改

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

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

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

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

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

313 定義鄰居表和路由表數據結構

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

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

3.2 GQ-AODV算法的實現流程

321 下一跳節點選取策略

GQ-AODV算法是在AODV的基礎上進行改進。加入了節點坐標和節點速度的地理位置信息。GQ-AODV算法改進了鄰居表和路由表，當地理位置不可用時使用原AODV洪泛請求目的節點位置信息。當地理位置可用的時候使用Q學習轉發策略，其下一跳選取應滿足以下條件：

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

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

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

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

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

GQ-AODV算法使用地理位置信息以及節點間相對速度作為下一跳選擇的度量，考慮到下一跳節點位置能夠在目的節點方向上更靠近目的節點，同時考慮到節點移動性對網絡拓撲穩定性的影響，當地理位置可用的時候，下一跳選取主要依賴兩個指標：有效度量和穩定度量。使用學習選擇最優下一跳，如式(13)所示。

+1(，)=

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

(13)

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

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

(14)

其中∈(0，1)。

3.2.2 HELLO包的發送與接收

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

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

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

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

3.2.3 RREQ包的發送與接收

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

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

圖4 發送RREQ包流程

圖5 接收RREQ包流程

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

4 NS3仿真與對比分析

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

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

表1 仿真場景參數

4.1 節點數量對網絡性能的影響

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

表2 實驗變量

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

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

圖6 不同節點數量對兩路由協議性能影響

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

4.2 節點最大移動速度對網絡性能的影響

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

表3 實驗變量

對比分析：圖7(a)顯示了平均端到端時延與節點最大移動速度的關系。圖7(b)顯示了網絡抖動與最大移動速度的關系。由圖7(a)(b)可知，GQ-AODV協議的時延和抖動遠低于AODV協議，且隨著節點最大移動速度的增加而緩慢增大。這是因為當地理位置可用時，節點選擇最優下一跳，鏈路不易斷開，更穩定，端到端時延和抖動主要來自于隊列分組等待和重傳機制，所以GQ-AODV協議的端到端時延和抖動遠小于AODV協議，但是隨著節點最大移動速度的增加，鏈路中斷的概率增大，所以其隨著節點最大移動速度的增大而緩慢增大。

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

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

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

5 結論

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