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

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

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

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

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

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

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

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é)點(diǎn)廣播路由請(qǐng)求分組,導(dǎo)致廣播風(fēng)暴問題,嚴(yán)重降低了網(wǎng)絡(luò)的整體性能.此外,AODV 協(xié)議有兩種運(yùn)行模式,周期性廣播Hello 消息和不廣播Hello 消息,即便是廣播Hello 消息可以獲得鄰居節(jié)點(diǎn)的相關(guān)信息,AODV 協(xié)議并沒有充分利用.DSR 協(xié)議與AODV 協(xié)議的不同之處是在轉(zhuǎn)發(fā)路由請(qǐng)求分組時(shí),節(jié)點(diǎn)將自己的信息添加到路由請(qǐng)求分組中,這樣路由請(qǐng)求分組中就包含了路徑信息,但是DSR 協(xié)議并不能克服路由發(fā)現(xiàn)過程中的廣播風(fēng)暴問題.

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

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

2 考慮邊界影響的節(jié)點(diǎn)度的估計(jì)算法

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

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

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

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

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

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

此時(shí),節(jié)點(diǎn)的平均鄰居個(gè)數(shù)可以估算為

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

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

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

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

三角形O2CA的面積可以計(jì)算為

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

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

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

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

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

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

(2) 當(dāng)dO3D＜R的情況.

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

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

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

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

3.1 節(jié)點(diǎn)度估計(jì)

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

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

· 當(dāng)節(jié)點(diǎn)處于網(wǎng)絡(luò)場景的邊區(qū)域時(shí),運(yùn)用公式(11)計(jì)算節(jié)點(diǎn)度;

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

· 當(dāng)節(jié)點(diǎn)處于角區(qū)域且dOD

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

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

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

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

其中,

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

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

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

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

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

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

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

NGRP 的路由請(qǐng)求分組結(jié)構(gòu)見表2,其中,節(jié)點(diǎn)度信息被添加到路由請(qǐng)求分組中,源節(jié)點(diǎn)地址和廣播ID 唯一標(biāo)識(shí)一個(gè)路由請(qǐng)求分組.

Table 2 Routing request packet表2 路由請(qǐng)求分組

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é)點(diǎn)有數(shù)據(jù)需要發(fā)送,但是源節(jié)點(diǎn)沒有到目的節(jié)點(diǎn)的路由,此時(shí)開啟路由發(fā)現(xiàn)過程.源節(jié)點(diǎn)獲取自己的地理位置信息,根據(jù)公式(31)估算自己的節(jié)點(diǎn)度NO,并在路由請(qǐng)求分組中添加NO信息;

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

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

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

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

· Step6:如果m

· Step7:丟棄分組.

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

4 仿真分析

4.1 仿真環(huán)境

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

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

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

4.2 評(píng)價(jià)指標(biāo)

本文用以下5 個(gè)指標(biāo)對(duì)協(xié)議性能進(jìn)行評(píng)估.

(1) 平均端對(duì)端延遲Avdelay

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

(2) 分組投遞率Pdelivery

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

(3) 路由開銷Nload

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

(4) MAC 層路由開銷Mload

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

(5) 吞吐率Th

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

4.3 仿真結(jié)果

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

仿真方法:改變網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量,得到性能隨網(wǎng)絡(luò)密度變化的情況.移動(dòng)節(jié)點(diǎn)數(shù)量分別為275,300,…,450,源節(jié)點(diǎn)的分組發(fā)送速率為1 個(gè)分組/秒.仿真結(jié)果如圖5～圖9 所示.

Fig.5 Average end to end delay圖5 平均端對(duì)端延遲

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

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

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

Fig.9 Throughput圖9 吞吐率

圖5 顯示了平均端對(duì)端延遲性能隨網(wǎng)絡(luò)密度變化的情況.從圖中可以看出:隨著網(wǎng)絡(luò)密度的增加,NGRP 和AODV+FDG 兩種協(xié)議的延遲性能保持穩(wěn)定,而AODV with Hello 和AODV without Hello 兩種協(xié)議的延遲性能出現(xiàn)波動(dòng).NGRP 和AODV+FDG 協(xié)議的平均端對(duì)端延遲性能明顯優(yōu)于AODV with Hello 和AODV without Hello 協(xié)議.原因在于:網(wǎng)絡(luò)密度大時(shí),NGRP 和AODV+FDG 采用概率的方式轉(zhuǎn)發(fā)分組,抑制了網(wǎng)絡(luò)擁塞,減少了節(jié)點(diǎn)間的競爭和沖突.

圖6 顯示了分組投遞率性能隨網(wǎng)絡(luò)密度變化的情況.從圖中可以看出:隨著網(wǎng)絡(luò)密度的逐漸增加,NGRP 協(xié)議的性能保持穩(wěn)定,AODV+FDG,AODV with Hello 和AODV without Hello 這3 種協(xié)議的性能均出現(xiàn)了不同程度的抖動(dòng).NGRP 的分組投遞率明顯優(yōu)于其他3 種協(xié)議,原因在于:NGRP 采用靜態(tài)博弈轉(zhuǎn)發(fā)策略,采用考慮邊界影響的節(jié)點(diǎn)度估計(jì)算法獲得節(jié)點(diǎn)度信息,避免了廣播Hello 消息帶來的擁塞和開銷.AODV+FDG 和AODV with Hello 兩種協(xié)議的性能明顯不如NGRP 和AODV without Hello,是因?yàn)榍皟煞N協(xié)議周期性廣播Hello 消息,導(dǎo)致網(wǎng)絡(luò)沖突增加,進(jìn)而導(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é)點(diǎn)周期性地廣播Hello 消息,增加了路由開銷;而NGRP 采用靜態(tài)博弈轉(zhuǎn)發(fā)策略,減少了網(wǎng)絡(luò)密集情況下,參與轉(zhuǎn)發(fā)路由請(qǐng)求分組的節(jié)點(diǎn)的數(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é)點(diǎn)周期性地廣播Hello 消息,導(dǎo)致MAC 層控制分組數(shù)量;而NGRP 采用靜態(tài)博弈轉(zhuǎn)發(fā)策略,減少了網(wǎng)絡(luò)密集情況下參數(shù)轉(zhuǎn)發(fā)路由請(qǐng)求節(jié)點(diǎn)的數(shù)量,進(jìn)而減少了MAC 層控制分組的數(shù)量.

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

(2) 驗(yàn)證網(wǎng)絡(luò)負(fù)載對(duì)協(xié)議性能的影響.

仿真方法:改變網(wǎng)絡(luò)中源節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組的發(fā)包率,得到性能隨網(wǎng)絡(luò)負(fù)載變化的情況.移動(dòng)節(jié)點(diǎn)數(shù)量為275 個(gè),源節(jié)點(diǎn)每秒發(fā)送的數(shù)據(jù)包數(shù)量分別為1,2,4,8,16,仿真結(jié)果如圖10～圖14 所示.

Fig.10 Average end to end delay圖10 平均端對(duì)端延遲

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

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

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

Fig.14 Throughput圖14 吞吐率

圖10 顯示了平均端對(duì)端延遲性能隨網(wǎng)絡(luò)負(fù)載變化的情況.從圖中可以看出:隨著網(wǎng)絡(luò)負(fù)載的增加,4 種協(xié)議的延遲逐漸變大.NGRP 和AODV without Hello 的延遲性能要優(yōu)于AODV+FDG 和AODV with Hello.原因是:網(wǎng)絡(luò)負(fù)載的增加,導(dǎo)致網(wǎng)絡(luò)競爭、沖突加劇,路由請(qǐng)求分組的重傳次數(shù)逐漸增加,源節(jié)點(diǎn)重啟路由發(fā)現(xiàn)過程的數(shù)量增加,因而延遲性能逐漸增加.NGRP 采用概率轉(zhuǎn)發(fā)策略,不需要節(jié)點(diǎn)周期性發(fā)送Hello 消息,在一定程度上緩解了網(wǎng)絡(luò)擁塞.

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

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

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

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

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

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