無線自組織網絡GDSR的路由算法研

彭玉顏，陳春良，陳新

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

?

彭玉顏，陳春良，陳新

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

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

Ad-Hoc；DSR；GDSR；CC1110

引　言

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

1　DSR網絡協議

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

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

圖1　路由發現幀RREQ分組傳播過程

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

2　GDSR路由算法

2.1GDSR路由協議的概述

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

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

圖2　GDSR網絡示意圖

2.2GDSR網絡的建立

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

2.3GDSR入網路由請求應答機制

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

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

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

圖3　GDSR入網路由請求應答的示意圖

2.4GDSR路由維護和節點退出機制

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

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

2.5GDSR有限貪婪路徑發現機制

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

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

圖4　GDSR有限貪婪路徑發現機制流程圖

2.6MAC協議退避策略

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

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

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

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

圖5　節點轉發退避流程

2.7GDSR數據中繼轉發

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

2.8負載均衡

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

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

3　GDSR路由協議實現

GDSR路由協議應用于CC1110組成的網絡時，網絡中的單個節點采用CC1110無線單片機。本系統CC1110中心頻率設置為433.000 MHz，調制方式采用GFSK，串口數據傳輸速率設置為57 600 bps，數據速率為250 Kbps，發射功率設置為10 dBm[12-13]。

3.1GDSR路由協議幀結構

在使用GDSR路由協議并采用CC1110無線單片機收發數據時，需要統一的數據幀格式，如下所示：

同步字幀長度N目的地址源地址路由標識序列號數據CRC2字節1字節2字節2字節1字節1字節N字節2字節

網絡中的節點在發送和接收信息時都需要填寫或者讀取通信幀內的信息。

3.2GDSR路由協議標識

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

3.3GDSR路由表

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

節點地址網絡號網關地址跳數信息數組頻度狀態2字節2字節2字節1字節1字節1字節1字節

4　性能分析

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

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

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

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

結　語

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

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

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

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

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

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

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

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

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

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

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

[10] 李梅,周繼鵬.基于負載均衡的DSR路由協議改進[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網絡DSR路由協議的優化[J].武漢大學學報:理學版,2005,3(51):361- 364.

[15] 周敬祥,李臘元.Ad Hoc網絡DSR路由協議的優化[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)