彭玉顏，陳春良，陳新

(福州大學 物理與信息工程學院，福州 350108)

?

彭玉顏，陳春良，陳新

(福州大學 物理與信息工程學院，福州 350108)

針對無線自組織網(wǎng)絡(Ad-Hoc)中DSR路由算法在路由查詢時產(chǎn)生的洪泛廣播問題，介紹了網(wǎng)關動態(tài)源路由協(xié)議(Gateway Dynamic Source Routing，GDSR)，著重闡述了該算法的新節(jié)點入網(wǎng)路由查詢機制、節(jié)點路徑查詢機制、基于優(yōu)先級的對數(shù)函數(shù)退避算法等。本文實現(xiàn)了該路由算法，并在實際環(huán)境中測試驗證了該路由協(xié)議。

Ad-Hoc；DSR；GDSR；CC1110

引　言

無線自組織網(wǎng)絡(Ad-Hoc)主要用于不便使用現(xiàn)有網(wǎng)絡或者通信基礎設施的情況，比如臨時會議、應急服務、災難緊急通信、信息采集、軍事通信等[1]。如今物聯(lián)網(wǎng)已起步，無線自組織網(wǎng)絡將能很好地運用于物聯(lián)網(wǎng)中。無線自組織網(wǎng)絡的路由協(xié)議很多，DSR是常見的一種協(xié)議[2]。使用路由協(xié)議的網(wǎng)絡，系統(tǒng)收斂性效果好，但是容易引起不必要的退避和沖突，如果該網(wǎng)絡非常龐大，還會導致網(wǎng)絡堵塞、效率低。因此，研究以及優(yōu)化該路由協(xié)議和相應沖突退避算法非常有必要。

1　DSR網(wǎng)絡協(xié)議

DSR協(xié)議幀格式為：固定頭部+幀類型+數(shù)據(jù)+固定尾部。幀類型有路由發(fā)現(xiàn)請求幀RREQ、路由應答幀RREP、路由維護幀RRER、應答請求幀ASKP、確認幀ASK、數(shù)據(jù)幀DATA。DSR的路由發(fā)現(xiàn)請求幀RREQ、路由應答幀RREP、路由維護幀RRER主要應用于路由發(fā)現(xiàn)維護階段。

DSR路由協(xié)議主要包括路由發(fā)現(xiàn)、路由維護、退避策略3部分。其中，路由發(fā)現(xiàn)的過程主要是節(jié)點發(fā)現(xiàn)和尋找通信路徑的過程[3]。網(wǎng)絡中要通信的節(jié)點通過向網(wǎng)絡廣播路由請求幀RREQ，來尋找到目的節(jié)點的路由信息，把經(jīng)過的中間節(jié)點寫入自身地址并一跳一跳地廣播出去，直至目的節(jié)點收到該分組為止，路由發(fā)現(xiàn)幀RREQ分組傳播過程如圖1所示。目的節(jié)點計算最佳路由之后，反饋路由應答幀RREP分組至源節(jié)點，源節(jié)點收到目的節(jié)點反饋回來的RREP分組之后，將路由信息保存在自身路由表中，然后就可以與目的節(jié)點進行通信[4]。

圖1　路由發(fā)現(xiàn)幀RREQ分組傳播過程

DSR路由協(xié)議的特點使其較為適用于移動性不強的網(wǎng)絡，又由于DSR網(wǎng)絡中不需要維護路由表，導致其路由表內(nèi)容簡單，其節(jié)點內(nèi)存可以選擇較小容量，所以可選用較為廉價的硬件實現(xiàn)，大大降低了在實際應用過程中的系統(tǒng)成本。DSR的不足在于會出現(xiàn)洪泛式廣播、可能存在陳舊路由、重建路由，將增大系統(tǒng)響應時延、節(jié)點容易失去與網(wǎng)絡的聯(lián)系，并且DSR協(xié)議的網(wǎng)絡規(guī)模不能過于龐大[5]。

2　GDSR路由算法

2.1GDSR路由協(xié)議的概述

網(wǎng)關動態(tài)源路由協(xié)議(Gateway Dynamic Source Routing，GDSR)是在DSR路由協(xié)議的基礎上，增加網(wǎng)關節(jié)點、劃分廣播沖突區(qū)域，使得區(qū)域中廣播只在網(wǎng)關內(nèi)部轉(zhuǎn)發(fā)，其他沖突區(qū)域的節(jié)點可以通過網(wǎng)關來訪問目的節(jié)點所在區(qū)域的網(wǎng)關，進而獲得前往目的節(jié)點的路徑，同時網(wǎng)絡還可以通過網(wǎng)關定時查詢和維護節(jié)點。在GDSR網(wǎng)絡中，節(jié)點維護的數(shù)據(jù)結(jié)構有兩個表：入網(wǎng)路由表(表驅(qū)動路由協(xié)議)和通信路由表(按需路由協(xié)議)，這使得其擁有入網(wǎng)路由請求和通信路徑發(fā)現(xiàn)請求兩種路由請求方式，因此GDSR路由協(xié)議更加可靠。節(jié)點在入網(wǎng)時采用入網(wǎng)路由請求應答機制尋找最佳節(jié)點作為入網(wǎng)網(wǎng)關(上游節(jié)點)；節(jié)點在通信路由發(fā)現(xiàn)時，采用有限貪婪路徑發(fā)現(xiàn)機制尋找路徑，即通過入網(wǎng)網(wǎng)關節(jié)點以及鄰居節(jié)點查找路徑。

GDSR網(wǎng)絡選擇處于網(wǎng)絡中心或者起始狀況時的節(jié)點作為集中節(jié)點，也就是最初的網(wǎng)關節(jié)點，新節(jié)點通過上游節(jié)點或者網(wǎng)關節(jié)點進入網(wǎng)絡，能在網(wǎng)關所在域進行廣播。由于網(wǎng)關節(jié)點將網(wǎng)絡劃分成不同的沖突域，使DSR路由洪泛得到有效控制。圖2為GDSR網(wǎng)絡示意圖。

圖2　GDSR網(wǎng)絡示意圖

2.2GDSR網(wǎng)絡的建立

GDSR屬于分級式體系結(jié)構，適用于有集中節(jié)點的網(wǎng)絡或者層級型網(wǎng)絡，對于采集數(shù)據(jù)型、通信接口匯聚型、命令控制型網(wǎng)絡非常實用。GDSR路由協(xié)議在網(wǎng)絡建立之初為最初的一個節(jié)點，沒有其他網(wǎng)絡接入，于是選擇為網(wǎng)絡集中節(jié)點，也就是最初的網(wǎng)關節(jié)點。有了網(wǎng)絡的核心，后續(xù)通過該節(jié)點接入網(wǎng)絡的節(jié)點也稱為網(wǎng)關節(jié)點。與集中節(jié)點相連的上游節(jié)點如果頻度增加(其下游節(jié)點變多)，則升級為網(wǎng)關節(jié)點。圖2中，網(wǎng)絡最初的網(wǎng)關節(jié)點D為集中節(jié)點，網(wǎng)絡最初只有B、E、G、F時無其他網(wǎng)關節(jié)點，當有A、C通過B加入網(wǎng)絡時，B的頻度增加，于是，D賦予B為網(wǎng)關節(jié)點，A、B、C為單獨的一個域，整個網(wǎng)絡從星狀網(wǎng)變成2級層次星狀網(wǎng)。其他新節(jié)點通過入網(wǎng)路由請求應答機制選擇最佳路徑接入網(wǎng)絡，使得網(wǎng)絡不斷變大。當工程應用不同時，集中節(jié)點可以自動或者人工選擇節(jié)點。

2.3GDSR入網(wǎng)路由請求應答機制

新節(jié)點加入網(wǎng)絡時，根據(jù)GDSR入網(wǎng)路由請求應答機制，需要廣播入網(wǎng)路由請求包RREQ,接收RREQ對象為上游節(jié)點，也就是已經(jīng)通過的網(wǎng)關節(jié)點或者其他已加入網(wǎng)絡的上游節(jié)點。路由應答時，接收到路由請求包RREQ的上游節(jié)點不再進行轉(zhuǎn)發(fā)，而是發(fā)回路由反饋包RREP。

發(fā)送RREQ之后的新節(jié)點將接收到一條乃至多條路由反饋包RREP，將所有RREP包存入路由緩存表中；然后將根據(jù)各個RREP中的網(wǎng)絡號、路由頻度、時延等情況進行對比和計算最優(yōu)路徑，將該節(jié)點存入路由表中，并向該節(jié)點發(fā)送路由確認幀RREPP；接著把緩存表直接復制進入鄰居節(jié)點表，最后新節(jié)點填充路由確認幀RREPP，發(fā)送給最佳路徑。

由于新節(jié)點有計算最佳路徑的過程，使得網(wǎng)絡可以避免有兩個沖突域的子網(wǎng)絡之間同時產(chǎn)生最優(yōu)節(jié)點，GDSR入網(wǎng)路由請求應答的示意圖如圖3所示。

圖3　GDSR入網(wǎng)路由請求應答的示意圖

2.4GDSR路由維護和節(jié)點退出機制

路由維護的目的是確定下游節(jié)點是否還在搜索網(wǎng)絡，避免有限貪婪轉(zhuǎn)發(fā)時浪費轉(zhuǎn)發(fā)機會、集中節(jié)點失去其鏈接的下游節(jié)點等問題，同時，也可以及時了解到節(jié)點是否非主動退出網(wǎng)絡。GDSR采用網(wǎng)關節(jié)點定期查詢維護機制。網(wǎng)關節(jié)點對所在網(wǎng)絡區(qū)域的節(jié)點進行定期輪詢單播查詢，如果有節(jié)點沒有及時回復，那么需要再次廣播該節(jié)點，在確認該節(jié)點已經(jīng)退出網(wǎng)絡時，及時通知客戶端。

節(jié)點退出機制：當有終端節(jié)點主動退出(即需要報停或者某些原因需要拆除)時，如果沒有退出機制，會造成所在路徑失效，導致上下游節(jié)點鏈路問題，因此在該節(jié)點退出網(wǎng)絡時，會發(fā)出廣播退出幀。接收到退出幀的上游節(jié)點在收到退出請求后，將本地路由表中該請求節(jié)點的路由信息清空，并向路由節(jié)點匯報。

2.5GDSR有限貪婪路徑發(fā)現(xiàn)機制

在DSR路由協(xié)議中，在和目的節(jié)點通信時，源節(jié)點需要知道數(shù)據(jù)包發(fā)往目的節(jié)點的路徑，此時，源節(jié)點根據(jù)DSR路由協(xié)議的路由發(fā)現(xiàn)機制洪泛廣播路徑發(fā)現(xiàn)幀，每個節(jié)點收到轉(zhuǎn)發(fā)廣播之后，如果不是目標節(jié)點，則把自己的節(jié)點地址加入路徑發(fā)現(xiàn)幀的路徑中，TTL加1，然后轉(zhuǎn)發(fā)該幀。采用洪泛廣播轉(zhuǎn)發(fā)機制的DSR路由協(xié)議在路徑發(fā)現(xiàn)、網(wǎng)絡收斂性方面效果較好，但由于接收到轉(zhuǎn)發(fā)幀的節(jié)點會繼續(xù)轉(zhuǎn)發(fā)，造成洪泛的同時還可能引起路由環(huán)路。

在GDSR路由協(xié)議中，節(jié)點在通信路徑發(fā)現(xiàn)時，采用有限貪婪路徑發(fā)現(xiàn)機制尋找路徑，即通過鄰居節(jié)點或者網(wǎng)關節(jié)點發(fā)現(xiàn)路徑。每次向上查詢時，路徑中就加入該節(jié)點地址，當查詢完畢就有了完整路徑。路徑發(fā)現(xiàn)機制處理流程圖如圖4所示。

圖4　GDSR有限貪婪路徑發(fā)現(xiàn)機制流程圖

2.6MAC協(xié)議退避策略

當網(wǎng)絡比較大時，無線節(jié)點數(shù)量也會很大。由于采用的是同頻傳輸，所以眾多節(jié)點在路由建立、數(shù)據(jù)轉(zhuǎn)發(fā)時會造成碰撞。利用CSMA/CA機制對信道檢測往往會造成連續(xù)的退避，增加時延。同時，隱藏終端和暴露終端的存在也增加了沖突的概率[6]：

① 當一個節(jié)點重復收到一個分組k次后，若k>4再進行廣播，則該報文所能覆蓋新區(qū)域的期望值小于5%。隨著k的值增大，轉(zhuǎn)播分組后所能覆蓋的區(qū)域就會迅速減小。設定一個門限值，在未轉(zhuǎn)發(fā)幀之前若是收到超過門限值C的相同的廣播分組，則取消轉(zhuǎn)發(fā),此處C設置為4。

② 當接收節(jié)點距離發(fā)射節(jié)點越近，進行廣播轉(zhuǎn)發(fā)時所能覆蓋的額外范圍越小，相反，距離越遠，增加的額外范圍就越大，能夠到達新節(jié)點的概率就越大，通過以上觀察，對中間節(jié)點的廣播轉(zhuǎn)發(fā)的隨機退避時間進行了優(yōu)先級劃分，即距離發(fā)射節(jié)點近的退避時間長，距離越遠退避的時間越短，這樣就增加了距離遠的終端節(jié)點的發(fā)送機會，減少了近處節(jié)點的發(fā)送機會。并且由于退避時間長，很可能在退避過程中收到C個重復的廣播分組后而不再進行廣播轉(zhuǎn)發(fā)[7]。

對于同樣的節(jié)點數(shù)，將退避時間進行分段不但不會增加碰撞的概率，反而使其減小[8]。廣播退避流程如圖5所示。

圖5　節(jié)點轉(zhuǎn)發(fā)退避流程

2.7GDSR數(shù)據(jù)中繼轉(zhuǎn)發(fā)

GDSR網(wǎng)絡節(jié)點數(shù)據(jù)中轉(zhuǎn)能力與DSR網(wǎng)絡的節(jié)點類似[9]，故不贅述。只是在對比收到的數(shù)據(jù)幀時，會比較路由表項的源地址和網(wǎng)關地址是否是自己的地址，或者網(wǎng)關地址是否與自己的網(wǎng)關地址相同，以確認是否轉(zhuǎn)發(fā)。

2.8負載均衡

網(wǎng)絡可能會由于路由多跳建立導致節(jié)點負載不均衡，使某些節(jié)點比較優(yōu)秀，頻繁作為上游節(jié)點，在數(shù)據(jù)抄收、數(shù)據(jù)傳輸階段這些節(jié)點頻繁轉(zhuǎn)發(fā)數(shù)據(jù)，會造成數(shù)據(jù)不準確、網(wǎng)絡延遲甚至癱瘓，而有些卻很少使用，造成資源浪費[10]。因此有必要加入負載均衡機制[11]。

根據(jù)網(wǎng)絡中上游節(jié)點的使用頻度Freque來間接衡量路徑負載，每個節(jié)點維護一個使用頻度Freque。在路由建立階段，上游節(jié)點接收到新節(jié)點的路由請求包RREQ時，將自身的頻度填充進入路由應答幀RREP，然后發(fā)送。新節(jié)點收到RREP之后，經(jīng)過對比和計算，選擇頻度小或者跳數(shù)小的上游節(jié)點作為最佳路徑，相對小的作為次佳路徑，并向最佳路徑發(fā)送RREPP。上游節(jié)點收到RREPP之后，將下游節(jié)點存入路由表中，并且自身頻度Frequ加1，同時向自身上游節(jié)點通告增加了1節(jié)點，讓其頻度自加1。自動負載均衡選擇最佳路徑的步驟、跳數(shù)頻度負載均衡示意圖略——編者注。

3　GDSR路由協(xié)議實現(xiàn)

GDSR路由協(xié)議應用于CC1110組成的網(wǎng)絡時，網(wǎng)絡中的單個節(jié)點采用CC1110無線單片機。本系統(tǒng)CC1110中心頻率設置為433.000 MHz，調(diào)制方式采用GFSK，串口數(shù)據(jù)傳輸速率設置為57 600 bps，數(shù)據(jù)速率為250 Kbps，發(fā)射功率設置為10 dBm[12-13]。

3.1GDSR路由協(xié)議幀結(jié)構

在使用GDSR路由協(xié)議并采用CC1110無線單片機收發(fā)數(shù)據(jù)時，需要統(tǒng)一的數(shù)據(jù)幀格式，如下所示：

同步字幀長度N目的地址源地址路由標識序列號數(shù)據(jù)CRC2字節(jié)1字節(jié)2字節(jié)2字節(jié)1字節(jié)1字節(jié)N字節(jié)2字節(jié)

網(wǎng)絡中的節(jié)點在發(fā)送和接收信息時都需要填寫或者讀取通信幀內(nèi)的信息。

3.2GDSR路由協(xié)議標識

新節(jié)點在填充路由請求包RREQ時，其幀中的路由標識為0x01，為廣播標識；所得到的回應為RREP，路由標識為0x22，為單播標識；收到回復RREP之后發(fā)送的反饋RREPP為0x63，為廣播標識。貪婪獲取路徑時，源節(jié)點填充路徑查詢幀CPRQ，其幀中的路由標識為0x60，為廣播標識；收到的路徑反饋幀CPRP為0x62，為單播標識。數(shù)據(jù)幀的路由標識DATA為0x88，為單播標識。

3.3GDSR路由表

GDSR是基于網(wǎng)關節(jié)點的分級式設計的路由協(xié)議，所以在節(jié)點的路由表中有網(wǎng)關地址與網(wǎng)絡號。GDSR路由表中擁有兩種類型，即入網(wǎng)路由表項和通信路徑路由表項。信息數(shù)據(jù)記載了通信路徑路由表項的路徑。CC1110無線節(jié)點的路由表結(jié)構如下所示：

節(jié)點地址網(wǎng)絡號網(wǎng)關地址跳數(shù)信息數(shù)組頻度狀態(tài)2字節(jié)2字節(jié)2字節(jié)1字節(jié)1字節(jié)1字節(jié)1字節(jié)

4　性能分析

采用9個CC1110無線單片機作為網(wǎng)絡節(jié)點，分別建立DSR和GDSR網(wǎng)絡，網(wǎng)絡節(jié)點拓撲與跳數(shù)頻度負載均衡示意圖相同。實際網(wǎng)絡測試容易受到環(huán)境、硬件節(jié)點的影響，導致統(tǒng)計時個別參數(shù)的數(shù)據(jù)會有偏差，故需要多次做兩個網(wǎng)絡的滿負荷數(shù)據(jù)包投遞實驗。根據(jù)PC客戶端收到的數(shù)據(jù)包的時間和數(shù)量作為參數(shù)統(tǒng)計數(shù)據(jù)，從以下3個參數(shù)來討論GDSR路由協(xié)議在無線自組織網(wǎng)絡中的性能[14]：

① 數(shù)據(jù)包傳送成功率：當網(wǎng)絡穩(wěn)定后，GDSR網(wǎng)絡的數(shù)據(jù)包發(fā)送成功率比DSR的高，這是由于GDSR建立的是有可靠網(wǎng)關、有效退避、雙重路由表的網(wǎng)絡；但是DSR路由協(xié)議的路由收斂能力比GDSR好，所以GDSR成功率不會比DSR高多少。兩種協(xié)議的數(shù)據(jù)包傳送成功率圖略——編者注。

② 網(wǎng)絡平均延遲：DSR網(wǎng)絡中的節(jié)點要通信時，按需發(fā)送洪泛路由請求使得網(wǎng)絡經(jīng)常擁塞，造成網(wǎng)絡延遲；如果退避策略不優(yōu)秀，那么容易使得MAC層多次重發(fā)的延遲時間更長、網(wǎng)絡更堵等。GDSR協(xié)議在網(wǎng)絡的初期延遲高，但是當網(wǎng)絡穩(wěn)定后，延遲更低，這是由于新協(xié)議采用了“區(qū)域管理”限制洪泛濫、區(qū)分路由入網(wǎng)和路徑查詢、有效的退避策略的緣故。兩種協(xié)議的網(wǎng)絡平均延遲略——編者注。

③ 路由開銷：GDSR網(wǎng)絡由于修改了路由查詢機制，使得路由開銷明顯降低。兩種協(xié)議的網(wǎng)絡路由開銷略——編者注。

結(jié)　語

GDSR路由協(xié)議從修改路由選擇機制、退避策略、路徑查找機制等方面入手，明顯改善了網(wǎng)絡的擁堵情況，減小了路由開銷，縮短了節(jié)點的傳輸延遲，提高了數(shù)據(jù)包傳遞的效率。

編者注：本文為期刊縮略版，全文見本刊網(wǎng)站www.mesnet.com.cn。

[1] 程偉明.無線移動自組網(wǎng)及其關鍵技術[J].數(shù)據(jù)通信,2002(3):56- 58．

[2] 陳林星,曾曦,曹毅.移動Ad Hoc網(wǎng)絡[M].北京:電子工業(yè)出版社,2012:4- 11．

[3] 矣昕寶,全海燕,董會升.一種用于Ad-Hoc網(wǎng)絡的精簡路由協(xié)議設計與實現(xiàn)[J].科學技術與工程,2011,12 (11):35.

[4] 鮑傳山.Ad Hoc網(wǎng)絡DSR路由協(xié)議的研究與改進[D].南京:南京郵電大學,2011:1- 42.

[5] 王進,李克.無線Ad Hoc網(wǎng)絡DSR協(xié)議的優(yōu)化策略[J].湖南廣播電視大學學報,2010(2):66- 57.

[6] 陳國先.PIC單片機原理與接口技術[M].北京:電子工業(yè)出版社,2004:109- 117.

[7] 雷占勃,陳新,徐藝文.無線電力抄表系統(tǒng)的傳輸中繼站設計[J].單片機與嵌入式系統(tǒng)應用,2013(8).

[8] 徐磊,方紅雨,李曉輝.基于對數(shù)函數(shù)的Ad Hoc網(wǎng)絡MAC退避算法[J].計算機應用,2009,29(1).

[9] 蔡宜飛,陳新.無線抄表系統(tǒng)中繼技術的研究與改進[J].通信技術,2013,46(2):45- 47.

[10] 李梅,周繼鵬.基于負載均衡的DSR路由協(xié)議改進[J].計算機應用,2011,28(1).

[11] YANG Qin,WEN Y Y,ANG H Y.A routing protocol with energy and traffic balance awareness in wireless Ad hoc networks[C]//Proc of the 6th International Conference on Information,Communications&Signal Processing,2007:1- 5.

[12] Texas Instruments.CC1110f32 Data Sheet,2008.

[13] 王振宇,劉清.基于CC1110無線自動抄表方案[J].電腦知識與技術,2008(17).

[14] 王亮,朱秋萍,馬麗霞.Ad-Hoc網(wǎng)絡DSR路由協(xié)議的優(yōu)化[J].武漢大學學報:理學版,2005,3(51):361- 364.

[15] 周敬祥,李臘元.Ad Hoc網(wǎng)絡DSR路由協(xié)議的優(yōu)化[J].計算機應用研究,2006(12):292- 293.

Peng Yuyan,Chen Chunliang,Chen Xin

(College of Physics and Information Engineering,Fuzhou University,Fuzhou 350108,China)

Aiming at the problem of DSR routing algorithm in Ad-Hoc that will generate the flood broadcast in the routing query,the gateway dynamic source routing protocol(GDSR) is introduced.The algorithm of the new node network routing query mechanism,the node path query mechanism and the backoff algorithm based on the priority of logarithmic function are introduced.In the real environment,the routing algorithm is verified.

Ad-Hoc;DSR;GDSR;CC1110

TN92

A

(責任編輯：薛士然2015-11-04)