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

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

Ad Hoc 網(wǎng)絡(luò)是由一組帶有無線收發(fā)裝置的移動終端組成的一個臨時性的多跳的自治系統(tǒng),具有組網(wǎng)快速靈活、不依賴基礎(chǔ)設(shè)施等優(yōu)點,在民用和軍用領(lǐng)域具有廣泛的應(yīng)用前景.路由協(xié)議是Ad Hoc 網(wǎng)絡(luò)核心支撐技術(shù),主要解決數(shù)據(jù)分組實時、可靠傳輸?shù)膯栴}.Ad Hoc 網(wǎng)絡(luò)節(jié)點高速移動導(dǎo)致網(wǎng)絡(luò)拓撲的高動態(tài)變化,加之無線鏈路的帶寬、能量限制,為實現(xiàn)高性能的路由協(xié)議帶來了挑戰(zhàn).研究者提出的Ad Hoc 網(wǎng)絡(luò)路由協(xié)議可以分為主動路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議這3 種.3 種路由協(xié)議中,按需路由協(xié)議因為路由開銷小、不需要維護全網(wǎng)絡(luò)信息等優(yōu)點,倍受國內(nèi)外研究者關(guān)注.

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

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

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

1 相關(guān)工作

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

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

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

2 考慮邊界影響的節(jié)點度的估計算法

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

Fig.1 Geographic division of the erea圖1 網(wǎng)絡(luò)場景區(qū)域劃分

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

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

2.1 節(jié)點處于S1區(qū)域

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

此時,節(jié)點的平均鄰居個數(shù)可以估算為

2.2 節(jié)點處于S2區(qū)域

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

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

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

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

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

Fig.2 Node beside borderline圖2 節(jié)點靠近邊界區(qū)域

2.3 節(jié)點處于S3區(qū)域

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

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

Fig.3 Node in a corner圖3 節(jié)點靠近在角區(qū)域

(2) 當dO3D＜R的情況.

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

Fig.4 Node in a corner圖4 節(jié)點靠近在角區(qū)域

同理可估算節(jié)點處在網(wǎng)絡(luò)場景左上角、左下角和右下角時的節(jié)點度.

3 基于節(jié)點度估計和靜態(tài)博弈轉(zhuǎn)發(fā)策略的Ad Hoc 網(wǎng)絡(luò)路由協(xié)議NGRP

3.1 節(jié)點度估計

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

· 當節(jié)點處于網(wǎng)絡(luò)場景的中心區(qū)域時,依據(jù)公式(5)獲得節(jié)點度;

· 當節(jié)點處于網(wǎng)絡(luò)場景的邊區(qū)域時,運用公式(11)計算節(jié)點度;

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

· 當節(jié)點處于角區(qū)域且dOD

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

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

3.2 靜態(tài)博弈轉(zhuǎn)發(fā)策略

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

其中,

·NO代表參與轉(zhuǎn)發(fā)路由請求分組的節(jié)點,其數(shù)量可以由公式(31)計算得出;

·A代表策略集合,包含轉(zhuǎn)發(fā)和不轉(zhuǎn)發(fā)兩個元素;

·U代表效益函數(shù),見表1.

Table 1 Forwarding dilemma game表1 轉(zhuǎn)發(fā)困境博弈

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

靜態(tài)博弈分組轉(zhuǎn)發(fā)的納什均衡點為:當前節(jié)點轉(zhuǎn)發(fā)分組時的收益與當前節(jié)點不轉(zhuǎn)發(fā)分組,其他NO-1 個節(jié)點至少一個轉(zhuǎn)發(fā)分組時的收益相等.即:

3.3 分組結(jié)構(gòu)

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

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

NGRP 的路由表、路由回復(fù)分組和AODV 的路由表和路由回復(fù)分組一樣.

3.4 路由發(fā)現(xiàn)流程

NGRP 協(xié)議的路由發(fā)現(xiàn)過程采用靜態(tài)博弈轉(zhuǎn)發(fā)策略,轉(zhuǎn)發(fā)概率由公式(35)得出,具體步驟為:

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

· Step2:中間節(jié)點接收到路由請求分組后,判斷是否重復(fù)接收:如果重復(fù)接收,轉(zhuǎn)Step7;否則,轉(zhuǎn)Step3;

· Step3:如果中間節(jié)點是目的節(jié)點,發(fā)送路由回復(fù)分組;如果中間節(jié)點不是目的節(jié)點,但是中間節(jié)點有到目的節(jié)點的路由,發(fā)送路由回復(fù)分組;

· Step4:中間節(jié)點不是目的節(jié)點,且沒有到目的節(jié)點的路由,采用靜態(tài)博弈轉(zhuǎn)發(fā)策略,根據(jù)公式(35)計算出轉(zhuǎn)發(fā)概率P;

· Step5:產(chǎn)生[0,1]之間的隨機數(shù)m;

· Step6:如果m

· Step7:丟棄分組.

NGRP 的路由發(fā)現(xiàn)過程在AODV 路由發(fā)現(xiàn)過程的基礎(chǔ)上實現(xiàn).NGRP 的路由回復(fù)、路由修復(fù)過程繼承了AODV 的路由回復(fù)、路由修復(fù)過程.

4 仿真分析

4.1 仿真環(huán)境

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

表3 給出了兩組仿真的公共參數(shù).

Table 3 Simulation parameters表3 仿真參數(shù)

4.2 評價指標

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

(1) 平均端對端延遲Avdelay

其中,N表示成功傳輸?shù)臄?shù)據(jù)分組數(shù),Rtime(i)表示第i個分組到達目的節(jié)點的時間,Stime(i)表示第i個分組的發(fā)送時間.

(2) 分組投遞率Pdelivery

其中,PR表示成功到達目的地的數(shù)據(jù)分組數(shù),PS表示源節(jié)點發(fā)送的數(shù)據(jù)分組總數(shù).

(3) 路由開銷Nload

其中,PC表示節(jié)點網(wǎng)絡(luò)層發(fā)送的控制分組的總數(shù)量,PD表示目的節(jié)點接收的數(shù)據(jù)分組總數(shù).

(4) MAC 層路由開銷Mload

其中,PM表示節(jié)點MAC 層發(fā)送的控制分組的總數(shù)量,PD表示目的節(jié)點接收的數(shù)據(jù)分組總數(shù).

(5) 吞吐率Th

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

4.3 仿真結(jié)果

(1) 驗證網(wǎng)絡(luò)密度對協(xié)議性能的影響.

仿真方法:改變網(wǎng)絡(luò)中節(jié)點的數(shù)量,得到性能隨網(wǎng)絡(luò)密度變化的情況.移動節(jié)點數(shù)量分別為275,300,…,450,源節(jié)點的分組發(fā)送速率為1 個分組/秒.仿真結(jié)果如圖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 顯示了平均端對端延遲性能隨網(wǎng)絡(luò)密度變化的情況.從圖中可以看出:隨著網(wǎng)絡(luò)密度的增加,NGRP 和AODV+FDG 兩種協(xié)議的延遲性能保持穩(wěn)定,而AODV with Hello 和AODV without Hello 兩種協(xié)議的延遲性能出現(xiàn)波動.NGRP 和AODV+FDG 協(xié)議的平均端對端延遲性能明顯優(yōu)于AODV with Hello 和AODV without Hello 協(xié)議.原因在于:網(wǎng)絡(luò)密度大時,NGRP 和AODV+FDG 采用概率的方式轉(zhuǎn)發(fā)分組,抑制了網(wǎng)絡(luò)擁塞,減少了節(jié)點間的競爭和沖突.

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

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

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

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

(2) 驗證網(wǎng)絡(luò)負載對協(xié)議性能的影響.

仿真方法:改變網(wǎng)絡(luò)中源節(jié)點發(fā)送數(shù)據(jù)分組的發(fā)包率,得到性能隨網(wǎng)絡(luò)負載變化的情況.移動節(jié)點數(shù)量為275 個,源節(jié)點每秒發(fā)送的數(shù)據(jù)包數(shù)量分別為1,2,4,8,16,仿真結(jié)果如圖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 顯示了平均端對端延遲性能隨網(wǎng)絡(luò)負載變化的情況.從圖中可以看出:隨著網(wǎng)絡(luò)負載的增加,4 種協(xié)議的延遲逐漸變大.NGRP 和AODV without Hello 的延遲性能要優(yōu)于AODV+FDG 和AODV with Hello.原因是:網(wǎng)絡(luò)負載的增加,導(dǎo)致網(wǎng)絡(luò)競爭、沖突加劇,路由請求分組的重傳次數(shù)逐漸增加,源節(jié)點重啟路由發(fā)現(xiàn)過程的數(shù)量增加,因而延遲性能逐漸增加.NGRP 采用概率轉(zhuǎn)發(fā)策略,不需要節(jié)點周期性發(fā)送Hello 消息,在一定程度上緩解了網(wǎng)絡(luò)擁塞.

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

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

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

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

5 結(jié)論及下一步工作

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