節點度估計和靜態博弈轉發策略的Ad Hoc 網絡路由協議*

王慶文 , 戚 茜 , 程 偉 , 李 冬

1(西安建筑科技大學,陜西 西安 710055)2(通信網信息傳輸與分發技術重點實驗室,河北 石家莊 050081)3(火箭軍工程大學,陜西 西安 710025)4(西北工業大學,陜西 西安 710072)

Ad Hoc 網絡是由一組帶有無線收發裝置的移動終端組成的一個臨時性的多跳的自治系統,具有組網快速靈活、不依賴基礎設施等優點,在民用和軍用領域具有廣泛的應用前景.路由協議是Ad Hoc 網絡核心支撐技術,主要解決數據分組實時、可靠傳輸的問題.Ad Hoc 網絡節點高速移動導致網絡拓撲的高動態變化,加之無線鏈路的帶寬、能量限制,為實現高性能的路由協議帶來了挑戰.研究者提出的Ad Hoc 網絡路由協議可以分為主動路由協議、按需路由協議和混合路由協議這3 種.3 種路由協議中,按需路由協議因為路由開銷小、不需要維護全網絡信息等優點,倍受國內外研究者關注.

在按需路由協議中,當源節點沒有到目的節點的路由時,需要采用廣播路由請求的方式開啟路由發現過程,而路由發現過程的效率嚴重影響路由協議的整體性能.最簡單的廣播是洪泛,其思想是:節點接收到非重復的廣播分組,隨即重新廣播分組.按需路由協議的路由發現過程中采用洪泛機制,容易導致廣播風暴問題:大量的冗余、競爭和沖突浪費了網絡帶寬,消耗了節點的能量,嚴重影響了Ad Hoc 網絡的性能.為了緩解廣播風暴問題,科研人員提出了多種廣播方案,這些廣播方案可以分為確定廣播方案和概率廣播方案[1].確定廣播方案在接收到廣播分組的節點中選取一部分節點轉發分組,該方案的不足是:一部分節點可能會因為多次承擔廣播任務而耗盡能量,導致網絡連通性下降;另一方面,由于Ad Hoc 網絡拓撲的高動態變化,給轉發節點的選取帶來了困難.概率廣播方案中,網絡中的所有節點以概率的方式轉發分組.相比確定廣播方案,概率廣播方案在路由失敗、網絡攻擊和動態拓撲條件下表現出更好的魯棒性.概率廣播方案中,節點轉發概率如何獲取?是Ad Hoc 廣播協議亟需解決的關鍵問題之一.利用節點的節點度,即節點的鄰居數量來計算轉發概率,是一種有效的方式,文獻[2-6]進行了這方面的研究.然而,上述研究需要節點需要周期性廣播Hello 消息獲取節點度,既消耗了節點的能量和信道的帶寬,又增加了網絡開銷.

為此,本文提出一種基于節點度和靜態轉發博弈的Ad Hoc 網絡路由協議NGRP(node degree and static game forwarding based routing protocol for ad hoc networks).NGRP 的貢獻主要包括兩個方面:一方面,NGRP 考慮網絡場景邊界區域的影響,將網絡場景分為中間、邊和角這3 種區域,采用分段函數的思想,分別計算節點在網絡場景的中間、邊和角區域的節點度,從而避免了節點周期性廣播Hello 消息導致的能量消耗和網絡性能下降;另一方面,NGRP 在轉發路由請求分組時采用靜態博弈轉發策略,用節點度估算博弈轉發的參加節點數量,將轉發分組與不轉發分組作為策略集合,設計效益函數,通過納什均衡獲得轉發概率,提升了路由請求分組在路由發現過程中的廣播效率.運用NS-2 進行大規模的仿真,仿真結果證明了NGRP 在分組投遞率、吞吐量、路由開銷和MAC 層路由開銷等指標上的優越性.

本文第1 節介紹相關工作.第2 節論述考慮邊界影響的節點度估計算法.NGRP 協議及其實現過程將在第3節闡述.第4 節運用NS-2 對NGRP 協議的性能進行仿真分析,并與幾種典型的路由協議的性能進行比較.最后,對全文進行總結并對下一步的研究進行展望.

1 相關工作

在按需路由協議研究方面.經典的按需路由協議有 AODV(ad hoc on-demand distance vector)[7],DSR(dynamic source routing)[8]等等.AODV 協議的路由發現過程需要節點廣播路由請求分組,導致廣播風暴問題,嚴重降低了網絡的整體性能.此外,AODV 協議有兩種運行模式,周期性廣播Hello 消息和不廣播Hello 消息,即便是廣播Hello 消息可以獲得鄰居節點的相關信息,AODV 協議并沒有充分利用.DSR 協議與AODV 協議的不同之處是在轉發路由請求分組時,節點將自己的信息添加到路由請求分組中,這樣路由請求分組中就包含了路徑信息,但是DSR 協議并不能克服路由發現過程中的廣播風暴問題.

在基于節點度的廣播方案方面.文獻[2]提出了一種基于博弈論的概率轉發策略,運用節點度信息獲得轉發概率,并將其運用在AODV 協議中,實現了AODV+FDG 協議,仿真結果證明了該協議在路由開銷、分組投遞率和平均端對端延遲等性能優于AODV 協議.文獻[6]設定了轉發概率的最大值和最小值,并根據節點度調節轉發概率,使得轉發概率在最大值和最小值范圍內,仿真結果證明了提出協議在轉發節省率和沖突數量指標上顯示出優勢.文獻[5]將節點度的倒數與常數因子的乘積作為轉發概率,提升了廣播節省率,該方案常數因子的選取還有優化空間.文獻[3,4]也做了類似的工作.文獻[9]利用兩跳節點度信息(即鄰居節點的節點度)來計算轉發概率,當兩跳節點度相對大時,轉發概率減少;當兩跳節點度相對小時,轉發概率增加.仿真結果表明,該方案在分組投遞率和路由開銷兩項指標顯示了優越性.文獻[2-6,9]提出了基于節點度的廣播方案,并運用在具體的協議中,雖然提升了網絡協議的性能,但是這些協議需要節點周期性廣播Hello 消息來獲取節點度信息,消耗節點能量和無線帶寬的同時,也增加了網絡擁塞和路由開銷,影響了網絡性能的進一步提升.文獻[10]提出了一種基于鄰居覆蓋的概率廣播協議,通過設計新的廣播延遲和廣播概率方案,提高了廣播效率.文獻[11]提出了一種基于估計距離的路由協議,該協議在網絡密度大或者是網絡拓撲變化劇烈的情況下顯著提高了路由性能.

為了克服廣播Hello 消息獲得節點度的不足,科研人員提出了不依賴Hello 消息獲得節點度的方法,其中具有代表性的是文獻[12-14].文獻[12]利用節點在空間的分布函數,計算出節點之間存在通信鏈路的概率,然后利用概率和網絡中節點的數量得出節點度信息,不足之處是沒有考慮到網絡邊界的影響.文獻[13,14]在計算節點度信息時考慮了網絡邊界的影響,通過節點在網絡區域的位置獲得了節點度的期望值.該方法的不足在于:(1) 節點位置在任何區域時,節點度都是相同的,實際上節點位置在網絡區域的邊、角和中間區域節點度差異大;(2) 該方法并沒有獲得解析解,難以在協議中使用.此外,文獻[15,16]研究了車載自組織網絡的數據分發問題,對本文的研究具有參考價值.

2 考慮邊界影響的節點度的估計算法

本文采用分段函數的思想,提出了考慮邊界影響的節點度估計算法.假設節點的通信半徑為R,n個節點分布在長寬分別為H,L的場景區域(其中,H>>R,L>>R),節點的地理位置服從均勻分布.將場景分成為中間、邊、角這3 個區域,分別用S1,S2和S3表示,如圖1 所示.

Fig.1 Geographic division of the erea圖1 網絡場景區域劃分

以網絡場景左下角為原點,分別以場景左邊界和下邊界為y軸和x軸建立直角坐標系,可得:

其中,(x,y)代表節點的二維坐標.從圖1 中可以看出:依據節點所處的地理位置,考慮邊界影響情況下的節點的通信范圍可以分為3 種情況來分析.

2.1 節點處于S1區域

當節點處于S1區域時,節點擁有完整的通信范圍,如圖1 中圓O1所示,節點的通信范圍為

此時,節點的平均鄰居個數可以估算為

2.2 節點處于S2區域

當節點處在S2區域時,由于網絡場景有4 個邊界,因而節點靠近邊界區域可以分為4 種情況.圖2 中,圓O2顯示了節點靠近網絡場景右邊界的情況,其中,B為A,C的中點,O2B⊥AC.

則,O2A和O2B之間的夾角θ可以計算為

那么,扇形區域O2CDA的面積可以計算為

三角形O2CA的面積可以計算為

那么,節點O2在場景之外的面積可以計算為

Fig.2 Node beside borderline圖2 節點靠近邊界區域

2.3 節點處于S3區域

節點處于網絡場景中角區域,可以分為節點在網絡場景的左上角、左下角、右上角和右下角這4 種情況.以節點處在網絡場景的右上角為例,該場景又可以分為兩種情況.令dO3D代表節點O3的圓心到右上角D的距離,根據dO3D與節點通信半徑R的大小,可以分為兩種情況.

(1) 當dO3D≥R的情況.當節點處于S3區域時,節點的通信范圍被兩個邊界所截,如圖3 所示.根據公式(9),此時,節點O3的受邊界影響無效的通信覆蓋范圍分別為

Fig.3 Node in a corner圖3 節點靠近在角區域

(2) 當dO3D＜R的情況.

此時,根據公式(9),節點O3的受邊界影響無效的通信覆蓋范圍SABCDK為

Fig.4 Node in a corner圖4 節點靠近在角區域

同理可估算節點處在網絡場景左上角、左下角和右下角時的節點度.

3 基于節點度估計和靜態博弈轉發策略的Ad Hoc 網絡路由協議NGRP

3.1 節點度估計

NGRP 假設網絡中的節點攜帶定位裝置,知道自己的地理位置信息以及網絡區域信息.網絡中任意節點O首先利用自己的地理位置信息和網絡區域信息,依據公式(1)～公式(3)確定自己在網絡場景中的位置區域;然后根據節點在網絡場景中所屬區域情況,分別計算節點度如下.

· 當節點處于網絡場景的中心區域時,依據公式(5)獲得節點度;

· 當節點處于網絡場景的邊區域時,運用公式(11)計算節點度;

· 當節點處于角區域且dOD≥R時,依據公式(16)獲得節點度;

· 當節點處于角區域且dOD

綜上,結合公式(5)、公式(11)、公式(16)和公式(30),在場景范圍內的節點O的節點度可以估算為

NGRP 采用上一節提出的考慮邊界影響的節點度估計算法獲得節點度信息:一方面,考慮網絡場景邊界區域的影響,提高了算法獲得節點度信息的準確性;另一方面,相比節點廣播Hello 消息獲得節點度信息,避免了不必要的開銷.

3.2 靜態博弈轉發策略

NGRP 本質上是一種按需路由協議,當源節點有數據要發送而沒有到目的節點的路由時,發起路由發現過程.NGRP 將路由發現過程中路由請求分組的轉發過程看成一個靜態博弈過程,即參與轉發路由請求的節點,在做出決策時,并不知道其他節點的策略,參與博弈轉發的節點之間沒有關于博弈信息的交換.一旦節點做出決策后,對博弈的發展不能再產生任何影響.靜態轉發博弈可以定義為

其中,

·NO代表參與轉發路由請求分組的節點,其數量可以由公式(31)計算得出;

·A代表策略集合,包含轉發和不轉發兩個元素;

·U代表效益函數,見表1.

Table 1 Forwarding dilemma game表1 轉發困境博弈

表1 中,u≥v>0.從表中可知:當NO個節點作為靜態轉發博弈的參與者,選取其中任何一個節點作為當前節點進行分析.當前節點和其他NO-1 都不轉發分組時,當前節點的收益為0;當前節點不轉發分組,由其他NO-1 個節點中至少有一個節點轉發分組,當前節點的收益為u;當前節點轉發分組,其他NO-1 個節點不轉發分組,當期節點的收益為u-v;當前節點和其他NO-1 個節點都轉發分組時,當前節點的收益仍然為u-v.假設參與博弈的節點以固定概率P轉發分組,那么,其他NO-1 個節點至少有一個節點轉發分組的概率為

靜態博弈分組轉發的納什均衡點為:當前節點轉發分組時的收益與當前節點不轉發分組,其他NO-1 個節點至少一個轉發分組時的收益相等.即:

3.3 分組結構

NGRP 的路由請求分組結構見表2,其中,節點度信息被添加到路由請求分組中,源節點地址和廣播ID 唯一標識一個路由請求分組.

Table 2 Routing request packet表2 路由請求分組

NGRP 的路由表、路由回復分組和AODV 的路由表和路由回復分組一樣.

3.4 路由發現流程

NGRP 協議的路由發現過程采用靜態博弈轉發策略,轉發概率由公式(35)得出,具體步驟為:

· Step1:源節點有數據需要發送,但是源節點沒有到目的節點的路由,此時開啟路由發現過程.源節點獲取自己的地理位置信息,根據公式(31)估算自己的節點度NO,并在路由請求分組中添加NO信息;

· Step2:中間節點接收到路由請求分組后,判斷是否重復接收:如果重復接收,轉Step7;否則,轉Step3;

· Step3:如果中間節點是目的節點,發送路由回復分組;如果中間節點不是目的節點,但是中間節點有到目的節點的路由,發送路由回復分組;

· Step4:中間節點不是目的節點,且沒有到目的節點的路由,采用靜態博弈轉發策略,根據公式(35)計算出轉發概率P;

· Step5:產生[0,1]之間的隨機數m;

· Step6:如果m

· Step7:丟棄分組.

NGRP 的路由發現過程在AODV 路由發現過程的基礎上實現.NGRP 的路由回復、路由修復過程繼承了AODV 的路由回復、路由修復過程.

4 仿真分析

4.1 仿真環境

仿真環境是帶有CMU 無線擴展的NS-2(Version 2.34),仿真場景為2200m×600m 的矩形區域,此場景為常用場景,節點的無線傳輸半徑為250m,網絡帶寬為2 兆比特/秒,C取值為106.仿真分兩組進行:(1) 驗證網絡密度對協議性能的影響;(2) 驗證網絡負載對協議性能的影響.仿真協議:(1) NGRP;(2) AODV+FDG;(3) AODV with Hello;(4) AODV without Hello.3 個源節點的地理位置為(220,60),(220,300),(220,540),對應的目的節點地理位置分別為(1980,540),(1980,300),(1980,60).仿真結果均為10 次仿真的平均值.

表3 給出了兩組仿真的公共參數.

Table 3 Simulation parameters表3 仿真參數

4.2 評價指標

本文用以下5 個指標對協議性能進行評估.

(1) 平均端對端延遲Avdelay

其中,N表示成功傳輸的數據分組數,Rtime(i)表示第i個分組到達目的節點的時間,Stime(i)表示第i個分組的發送時間.

(2) 分組投遞率Pdelivery

其中,PR表示成功到達目的地的數據分組數,PS表示源節點發送的數據分組總數.

(3) 路由開銷Nload

其中,PC表示節點網絡層發送的控制分組的總數量,PD表示目的節點接收的數據分組總數.

(4) MAC 層路由開銷Mload

其中,PM表示節點MAC 層發送的控制分組的總數量,PD表示目的節點接收的數據分組總數.

(5) 吞吐率Th

其中,Rbytes(i)表示成功到達目的地的第i個分組的字節數,N表示目的地接收的總的分組數量,TRend表示網絡中的數據分組結束接收的時間,TRstart表示網絡中開始有數據分組接收的時間.

4.3 仿真結果

(1) 驗證網絡密度對協議性能的影響.

仿真方法:改變網絡中節點的數量,得到性能隨網絡密度變化的情況.移動節點數量分別為275,300,…,450,源節點的分組發送速率為1 個分組/秒.仿真結果如圖5～圖9 所示.

Fig.5 Average end to end delay圖5 平均端對端延遲

Fig.6 Packet delivery fraction圖6 分組投遞率

Fig.7 Normalized routing load圖7 路由開銷

Fig.8 Normalized MAC load圖8 MAC 層路由開銷

Fig.9 Throughput圖9 吞吐率

圖5 顯示了平均端對端延遲性能隨網絡密度變化的情況.從圖中可以看出:隨著網絡密度的增加,NGRP 和AODV+FDG 兩種協議的延遲性能保持穩定,而AODV with Hello 和AODV without Hello 兩種協議的延遲性能出現波動.NGRP 和AODV+FDG 協議的平均端對端延遲性能明顯優于AODV with Hello 和AODV without Hello 協議.原因在于:網絡密度大時,NGRP 和AODV+FDG 采用概率的方式轉發分組,抑制了網絡擁塞,減少了節點間的競爭和沖突.

圖6 顯示了分組投遞率性能隨網絡密度變化的情況.從圖中可以看出:隨著網絡密度的逐漸增加,NGRP 協議的性能保持穩定,AODV+FDG,AODV with Hello 和AODV without Hello 這3 種協議的性能均出現了不同程度的抖動.NGRP 的分組投遞率明顯優于其他3 種協議,原因在于:NGRP 采用靜態博弈轉發策略,采用考慮邊界影響的節點度估計算法獲得節點度信息,避免了廣播Hello 消息帶來的擁塞和開銷.AODV+FDG 和AODV with Hello 兩種協議的性能明顯不如NGRP 和AODV without Hello,是因為前兩種協議周期性廣播Hello 消息,導致網絡沖突增加,進而導致分組投遞率下降.

圖7 顯示了路由開銷性能隨網絡密度變化的情況.從圖中可以看出:網絡密度的逐漸增加,NGRP 和AODV without Hello 的路由開銷保持穩定,AODV+FDG 和AODV with Hello 的路由開銷隨網絡密度的增加而增加.原因在于:AODV+FDG 和AODV with Hello 需要節點周期性地廣播Hello 消息,增加了路由開銷;而NGRP 采用靜態博弈轉發策略,減少了網絡密集情況下,參與轉發路由請求分組的節點的數量,因而減少了路由層控制分組的數量.

圖8 顯示了MAC 路由開銷性能隨網絡密度變化的情況.從圖中可以看出:NGRP 和AODV without Hello 的路由開銷隨著網絡密度的增加基本保持穩定,AODV+FDG 和AODV with Hello 的MAC 路由開銷隨網絡密度的增加而增加.原因在于:AODV+FDG 和AODV with Hello 需要節點周期性地廣播Hello 消息,導致MAC 層控制分組數量;而NGRP 采用靜態博弈轉發策略,減少了網絡密集情況下參數轉發路由請求節點的數量,進而減少了MAC 層控制分組的數量.

圖9 顯示了吞吐率性能隨網絡密度變化的情況.從圖中可以看出:隨著網絡密度的不斷增加,NGRP 協議的性能保持穩定,其他3 種協議的性能均出現了不同程度的抖動,NGRP 協議的性能明顯優于其他3 種協議.原因在于:NGRP 采用博弈轉發策略,應用考慮邊界影響的節點度估計算法,不依靠Hello 消息獲得節點度,擁有高性能的分組投遞率和延遲性能,因而吞吐率性能顯示出優越性.

(2) 驗證網絡負載對協議性能的影響.

仿真方法:改變網絡中源節點發送數據分組的發包率,得到性能隨網絡負載變化的情況.移動節點數量為275 個,源節點每秒發送的數據包數量分別為1,2,4,8,16,仿真結果如圖10～圖14 所示.

Fig.10 Average end to end delay圖10 平均端對端延遲

Fig.11 Packet delivery fraction圖11 分組投遞率

Fig.12 Normalized routing load圖12 路由開銷

Fig.13 Normalized MAC load圖13 MAC 層路由開銷

Fig.14 Throughput圖14 吞吐率

圖10 顯示了平均端對端延遲性能隨網絡負載變化的情況.從圖中可以看出:隨著網絡負載的增加,4 種協議的延遲逐漸變大.NGRP 和AODV without Hello 的延遲性能要優于AODV+FDG 和AODV with Hello.原因是:網絡負載的增加,導致網絡競爭、沖突加劇,路由請求分組的重傳次數逐漸增加,源節點重啟路由發現過程的數量增加,因而延遲性能逐漸增加.NGRP 采用概率轉發策略,不需要節點周期性發送Hello 消息,在一定程度上緩解了網絡擁塞.

圖11 顯示了分組投遞率性能隨網絡負載變化的情況.從圖中可以看出,NGRP 協議的分組投遞率明顯優于其他3 種協議.當源節點的發包率小于每秒8 個時,4 種協議的性能均呈現出先增加后減少的趨勢,原因在于:隨著網絡負載的增加,到達目的節點的數據分組數量逐漸增加,網絡負載成倍增加,而到達目的節點的分組數量沒有網絡負載增加快.當源節點的發包率大于每秒8 個時,4 種協議的分組投遞率劇烈下降,原因在于:網絡負載劇烈增加,4 種協議廣播路由請求分組導致的劇烈的競爭和沖突.NGRP 的轉發策略和不廣播Hello 消息,在此種情況下,對網絡性能起到了緩解作用.

圖12 顯示了路由開銷性能隨網絡負載變化的情況.從圖中可以看出:網絡負載的逐漸增加,4 種協議的路由開銷總體呈現先減少后增加的趨勢.原因在于:隨著網絡負載增加,到達目的節點的數據分組數量逐漸增加,當網絡負載增加到一定程度,網絡競爭沖突加劇,分組投遞率逐漸減少.NGRP 和AODV without Hello 的路由開銷性能要明顯優于AODV+FDG 和AODV with Hello,原因在于:NGRP 協議緩解了路由發現過程中廣播路由請求分組導致的廣播風暴問題,減少了網絡中的冗余、競爭和沖突.

圖13 顯示了MAC 層路由開銷性能隨網絡負載變化的情況.從圖中可以看出:網絡負載的逐漸增加,4 種協議的MAC 層路由開銷總體呈現先減少后增加的趨勢.原因在于:隨著網絡負載增加,到達目的節點的數據分組數量逐漸增加,當網絡負載增加到一定程度,網絡競爭沖突加劇,分組投遞率逐漸減少.NGRP 和AODV without Hello 的路由開銷性能要明顯優于AODV+FDG 和AODV with Hello,原因在于:NGRP 協議緩解了路由發現過程中廣播路由請求分組導致的廣播風暴問題,減少了MAC 層控制分組的數量.

圖14 顯示了吞吐率性能隨網絡負載變化的情況.可以看出,4 種協議的吞吐率均呈現出先增加后減少的趨勢.當源節點的發包率小于每秒8 個時,隨著網絡負載的增加,4 種協議的吞吐率逐漸增加.當源節點的發包率大于每秒8 個時,網絡擁塞程度加劇,競爭沖突劇烈,導致到達目的節點的數據分組數量有所降低.盡管如此,NGRP協議的吞吐率仍然優于其他3 種協議,原因在于:NGRP 的路由發現過程緩解了廣播路由請求帶來的廣播風暴問題,減少了網絡中的競爭和沖突.

5 結論及下一步工作

本文提出了一種基于節點度估計和靜態博弈轉發策略的Ad Hoc 網絡路由協議NGRP.NGRP 采用考慮邊界影響的節點度估計算法獲得節點度信息,避免了廣播Hello 消息導致的網絡消耗;采用靜態博弈轉發策略抑制路由發現過程中廣播路由請求分組導致的廣播風暴問題.運用NS-2,從驗證網絡密度和網絡負載對協議性能影響兩個方面,對NGRP 協議性能進行驗證.仿真結果表明:NGRP 協議的分組投遞率、路由開銷、MAC 層路由開銷和吞吐率這4 項指標均優于AODV+FDG,AODV with Hello 和AODV with Hello 協議.下一步的工作是將節點度估計算法和靜態博弈轉發策略引入到其他按需路由協議中.NGRP 目前適用于網絡節點數量較多且網絡中節點分布均勻的場景,還需要進一步改進協議,才能適用于網絡節點數量稀疏和節點分布不均勻的場景.