基于競爭轉(zhuǎn)發(fā)的Adhoc網(wǎng)絡(luò)路由算法

劉鋼　郭晗

摘要：移動Ad hoc網(wǎng)絡(luò)是通過無線通信技術(shù)，結(jié)合相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)從而能夠?qū)崿F(xiàn)群組內(nèi)各個節(jié)點(diǎn)的通信。是若干帶有無線接收和發(fā)射裝置的移動終端所組成的具有多跳能力的臨時自治系統(tǒng)。GPSR是一種比較典型且健壯的地理路由協(xié)議，但是當(dāng)遇到有較多的分組同時傳遞給同一個目的節(jié)點(diǎn)的情況時，由其周邊轉(zhuǎn)發(fā)模式產(chǎn)生的較多跳數(shù)的路由，會成為一個難以解決的問題，本文由此提出了一個改進(jìn)優(yōu)化的路由算法——EGPSR路由算法。

關(guān)鍵詞：Ad hoc；路由協(xié)議；競爭轉(zhuǎn)發(fā)；自組織

1、引言

在以往的研究過程中，典型的基于地理位置信息的路由協(xié)議有LAR[1]協(xié)議、GPSR[2]協(xié)議和TB協(xié)議等，這類協(xié)議具有更好的可擴(kuò)展性和對無線網(wǎng)絡(luò)更好的適應(yīng)性。

本文針對車載Ad hoc網(wǎng)絡(luò)所具有的特點(diǎn)提出了一種新的基于競爭轉(zhuǎn)發(fā)方式的路由算法，算法核心思路是通過特定的競爭轉(zhuǎn)發(fā)策略來確定合適的下一跳節(jié)點(diǎn)。數(shù)據(jù)包會沿著最終選定的序列進(jìn)行路由操作，并在岔路口區(qū)域進(jìn)行確定下一個岔路口的計算，從而減少數(shù)據(jù)包中攜帶完整岔路口序列信息的數(shù)據(jù)量，提高了工作效率。

2、車載Ad hoc路由算法研究進(jìn)展

GPSR是采用貪婪轉(zhuǎn)發(fā)策略和面遍歷算法的路由協(xié)議，它的缺點(diǎn)是性能在節(jié)點(diǎn)分布不均衡時惡化。

已經(jīng)比較成熟的確定路由的算法，主要有兩種，一種是基于已經(jīng)選定的結(jié)點(diǎn)的路由選擇，是找出一系列數(shù)據(jù)包轉(zhuǎn)發(fā)過程中必須經(jīng)過的地理位置，并在選定結(jié)點(diǎn)之間，使用特定的轉(zhuǎn)發(fā)策略進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。另一種是空間感知路由算法，是利用空間地理信息計算得到一個數(shù)據(jù)包轉(zhuǎn)發(fā)的確定路徑。

此外，還有一些利用實(shí)際環(huán)境因素進(jìn)行路由選擇的算法。其中基于街路和通信量信息感知路由算法是利用地理位置信息和道路交通信息確定選定點(diǎn)路徑。而基于位置的路由協(xié)議是以道路交叉點(diǎn)岔路口為選定點(diǎn)，基于網(wǎng)絡(luò)拓?fù)渑c車輛交通信息的路由協(xié)議。數(shù)據(jù)包擺渡是一種是控制移動節(jié)點(diǎn)的移動以輔助節(jié)點(diǎn)轉(zhuǎn)發(fā)。

3、EGPRS路由算法

根據(jù)已有的研究可知，包括移動Ad hoc網(wǎng)絡(luò)在內(nèi)的很多無線網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都具有一定的易變性，某些時刻某些節(jié)點(diǎn)對之間已經(jīng)建立的通路會中斷，同時，較多的路由跳數(shù)會增加特定路由上傳輸分組丟失的可能性，并能夠增加分組的傳輸時間延遲，從而降低網(wǎng)絡(luò)的性能。僅從路由跳數(shù)的角度來考慮，可以看出GPSR協(xié)議選擇的路由并不是最佳路由。

基于以上原因，本文借助某些路由節(jié)點(diǎn)上存儲的少量路由狀態(tài)信息提出了一種增強(qiáng)的策略和與之相對應(yīng)的路由算法。新的路由算法能夠在一定程度上減少GPSR協(xié)議在周邊轉(zhuǎn)發(fā)模式中由于繞道產(chǎn)生的跳數(shù)。當(dāng)多個分組傳到相同的目的節(jié)點(diǎn)時，新的路由算法能夠在傳遞完第一個分組后，以最快的速度確定一條較短的路由，以便在進(jìn)行后續(xù)分組的信息傳遞時經(jīng)過盡量少的跳數(shù)。所以節(jié)點(diǎn)能夠確定某一分組曾經(jīng)是否轉(zhuǎn)發(fā)過，并且能從分組的頭部包含的信息確定分組到達(dá)當(dāng)前發(fā)送節(jié)點(diǎn)所經(jīng)過的跳數(shù)。

3.1 競爭轉(zhuǎn)發(fā)策略

所有數(shù)據(jù)包中持有節(jié)點(diǎn)廣播的數(shù)據(jù)包都會給它的直接鄰接節(jié)點(diǎn)，這個數(shù)據(jù)包頭部包含持有節(jié)點(diǎn)的位置信息、當(dāng)前交叉節(jié)點(diǎn)的位置信息和數(shù)據(jù)包的編號。競爭節(jié)點(diǎn)接收數(shù)據(jù)包并臨時存儲數(shù)據(jù)包到本地緩存區(qū)，并且每個參與競爭的節(jié)點(diǎn)根據(jù)本節(jié)點(diǎn)、上一跳節(jié)點(diǎn)以及當(dāng)前交叉節(jié)點(diǎn)、前一岔路口的位置，為每個數(shù)據(jù)包設(shè)置一個計時器。若計時器超時，當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)包會以廣播方式轉(zhuǎn)發(fā)出去。在這個過程中，地理位置越靠近當(dāng)前交叉節(jié)點(diǎn)，其計時器超時的數(shù)值就會越小，滿足這個條件的時候，當(dāng)前節(jié)點(diǎn)會把本地緩存中的相應(yīng)數(shù)據(jù)包刪除。

3.2 EGPSR算法的路由發(fā)現(xiàn)

EGPSR算法采用與GPSR算法相類似的思路為信息序列的第一個分組找到路由，然后構(gòu)成無線網(wǎng)絡(luò)的節(jié)點(diǎn)會遵循下列路由算法進(jìn)行信息傳遞的分組，算法如下：

if節(jié)點(diǎn)m正在持有分組數(shù)據(jù)包p then

if 節(jié)點(diǎn)m是源節(jié)點(diǎn) then

節(jié)點(diǎn)m所經(jīng)歷的跳數(shù)為0

else

節(jié)點(diǎn)m的跳數(shù)為分組數(shù)據(jù)包p的跳數(shù)加1，同時把p的跳數(shù)改為與m的跳數(shù)一致。

if 節(jié)點(diǎn)m不是目的節(jié)點(diǎn)d then

m向前移動到m的下一個節(jié)點(diǎn)

if 節(jié)點(diǎn) m 監(jiān)聽到一個屬于鄰接節(jié)點(diǎn)n

把這個相同的節(jié)點(diǎn)p進(jìn)行發(fā)送，m的跳數(shù)加1

m的下一跳指向n

當(dāng)相同連接的數(shù)據(jù)包通過m發(fā)送數(shù)據(jù)時，m重新路由操作

在與GPSR算法相比較時，改進(jìn)的EGPSR算法有以下優(yōu)點(diǎn)：

a）一定程度的減少了路由的跳數(shù)；

b）任意一個節(jié)點(diǎn)在一跳傳輸范圍內(nèi)，有明確的下一跳信息；

c）進(jìn)行適當(dāng)?shù)膬?yōu)化后，第二個分組以及后續(xù)分組的路由是收斂的；

d）在一定程度上降低了路由的復(fù)雜度；

4、結(jié)束語

本文研究了以往的路由算法，并提出EGPSR算法，通過增加路由探測的方法達(dá)到了優(yōu)化信息傳遞路徑的目的。通過實(shí)驗(yàn)可以看出EGPSR算法在協(xié)議資源的開銷方面比GPSR算法大，但在分組丟失率、分組傳輸時延以及網(wǎng)絡(luò)吞吐量等方面都要好于GPSR算法，從而得知EGPSR算法改善了以往路由算法的網(wǎng)絡(luò)性能。（作者單位：1.吉林建筑大學(xué)；2.長春工業(yè)大學(xué)）

參考文獻(xiàn)：

[1]MarioGerla，Kennmg，RajiveBagrodia.TCpperformanceinwirolessmulti一hopnetworks.ProeeedingSoftheSecondIEEEWbrkshoPon MobileComPutersystemsandAPPlieations.NewOrleans，Louisiana：1999.41一5

[2]K.CHuang，K.C.Chen.Interferene analysis of nonPersistentCSMAwithhiddentenninalsinmultieellwirelessdatanebork.ProeeedingsoftheIEEEPIMRC.Toronto，Canada：1995，2.907 91