劉鋼　郭晗

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

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

1、引言

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

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

2、車載Ad hoc路由算法研究進展

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

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

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

3、EGPRS路由算法

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

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

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

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

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

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

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

if 節(jié)點m是源節(jié)點 then

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

else

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

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

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

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

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

m的下一跳指向n

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

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

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

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

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

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

4、結(jié)束語

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

參考文獻：

[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