一種移動Ad Hoc網絡路由協議的設計與實現＊

李紅衛

（廣州海格通信集團股份有限公司 廣州 510663）

1 引言

Ad Hoc網絡是由一組無線移動節點組成、不需要依靠現有固定通信網絡基礎設施的自組織、自創造、自愈和自管理網絡。Ad Hoc網絡的多跳性使得借鑒固定網絡的路由協議成為可能，但在網絡拓撲結構快速變化的情況下，固定網絡路由協議無法及時收斂，產生大量的不可靠路由和路由環路，而且路由開銷過大［1］。另外，無線帶寬有限、單向鏈路的存在等原因也使得在Ad Hoc網絡中不能直接使用固定網絡路由協議，而需要根據自身特點設計新的路由協議。

2 Ad Hoc路由協議的分類

根據網絡節點發現路由的驅動模式的不同對移動Ad Hoc網絡的路由算法進行分類其大致可以分為兩大類：一類稱作表驅動路由協議，一類稱作按需路由協議［2］。

表驅動路由協議的路由發現策略與傳統的路由協議類似，各節點需要周期性地在網絡中傳播路由更新消息，以維護路由表的一致性和正確性，它的優點是系統尋徑時延小，缺點是周期性的路由更新消息對網絡帶寬的占用較大，不適合于移動性較大的通信系統，如DSDV、WRP、HSR等［3］。

按需路由協議在有數據需要發送的時候再向網絡中廣播路由發現請求信息，等待目的節點回送路由應答信息，其優點是不需要周期性的路由信息廣播，因而節約網絡帶寬，適合于快速移動的通信系統，缺點是尋徑時間較長，如AODV、DSR等［4］。

3 Ad Hoc路由協議工作原理

3.1 協議概述

本路由協議適用于移動Ad Hoc網絡，最大支持6跳，采用可優化鏈路狀態協議，該協議是一種反映鏈路質量的混合路由協議，其主要指導思想是基于按需進行路由操作的原理，在保證路由的基礎上盡可能地減少路由控制信息的廣播，提高實際數據傳輸率?？紤]到使用的物理設備的無線信道傳輸可靠性較低，在分組傳遞中采用了逐跳確認數據分組、超時重發和報文序號等機制，為了彌補在相對靜止的條件下，按需路由協議存在的反映速度比主動路由協議慢的缺陷，增加了定時或事件觸發方式向鄰居節點進行路由公告的機制來進行路由的維護。

3.2 路徑發現

1）路由請求的發送

圖1 網絡拓撲結構圖

如圖1所示，當 Ad Hoc網絡內的源節點S需要向目的節點D發送數據時，如果同時滿足以下兩個條件，S發起一個路由請求：（1）S的路由表中沒有到D的路由；（2）距離上次S發起到D的路由請求的時間大于協議所規定的最小相同路由請求間隔。

條件（1）是顯而易見，條件（2）是為了防止源節點頻繁地發起到同一目的節點的路由請求的限制條件，即源節點對于同一目的節點的路由請求必須至少間隔一段時間。此時S生成一個到D的路由請求分組，其中包括目的節點地址、用于區分不同路由請求分組的唯一標志（ID）、源路由列表等（在開始時源路由列表中只有S自己），然后將此路由請求分組在網絡內部進行泛洪。

2）路由請求的處理

如圖1所示，收到路由請求分組的節點B要對該分組進行判斷處理，算法如下：

（1）每個節點都有一個接收到的路由請求分組的緩存隊列，用于存放最近收到的路由請求分組的標志和目的地址［5］。收到路由請求分組后，B首先查看該路由請求是否已在本節點的路由請求分組隊列中，如果在，則說明曾經收到過該分組，丟棄該分組；

（2）否則，查看本節點是否已在該路由請求分組的源路由列表中，若在則說明這是一個通過環路過來的分組，丟棄該分組；

（3）否則，查看本節點的路由緩存中是否有到D的路由，如果有，則B構造一個路由應答分組，其中攜帶從S到B的路由和從B到D的路由，此時應避免出現路由環路；

（4）否則，查看本節點是否是該路由請求分組所請求的目的節點，如果是，則說明在該分組中已經包含了從源節點到目的節點的完整路由，提取該分組中的夾帶選項進行處理，并將該分組中的源路由復制到路由應答分組中，構造一個路由應答分組，并將該路由應答分組發送給S；

（5）否則，B在路由表中加入從S到本節點的路由信息（路由學習），將本節點的地址加入該路由請求分組的源路由列表中，繼續廣播該分組；

（6）為了限制路由請求分組在網絡中的傳播范圍，在分組中設置了TTL，接收節點在處理該分組時將TTL減1，當TTL為0時，丟棄該分組。

3）路由請求的應答

由于路由請求采用廣播方式傳輸，目的節點D可能收到經過多個不同路徑發來的路由請求分組，如圖1所示，這些分組最終都到達了D，因此這些路徑都是有效路徑，但未必是最佳路徑，因此D需要對它們進行選擇，即D只對那些更短的或者等長的路徑構造路由應答分組，而舍棄更長的路徑。

如果目的節點D的路由表中沒有到源節點S的路由，D發起一個路由請求，其過程與上文描述的相同，但是D在所構造的路由請求分組中攜帶一個路由應答選項，可稱之為夾帶，其原因是：

（1）在雙向信道的情況下，路由應答分組按照路由請求分組的相反方向返回S，但由于無線信道可能存在的單向信道，逆向路由可能不存在，如果按照路由發現的一般過程先發送從D到S的路由請求，等待S的路由應答建立這段路由，然后利用源路由分組發送從D到S的路由應答的話，將會導致從D到S的路由應答時間較長，并且會在網絡中增加大量的路由請求和路由應答分組，增大網絡開銷；

（2）當D請求到S的路由時，S還沒有到D的路由，則S和D之間將出現死循環的路由請求過程。因此，可以通過夾帶機制在路由請求分組中夾帶路由應答、路由確認以及不同優先級的數據分組，從而避免路由請求中的死循環，并且加快路由協議對網絡拓撲變化的反應速度。

中間節點在收到夾帶路由應答選項的路由請求分組時，不但從路由請求分組中學習從D到本節點的路由，而且從夾帶的路由應答選項中學習其中包含的從S到D的路由，以維護本節點的路由表。

源節點S在收到D發送的路由應答分組后，從路由應答選項中提取所發現的源路由，復制到本節點的路由表中，然后開始發送從S到D的數據分組。

節點在發送或者轉發路由請求分組時采用廣播方式發送給所有鄰居節點，如果很多鄰居節點都具有到該請求節點的路由，那么所有這些鄰居節點都將試圖進行路由應答，這種情況下路由應答將浪費大量的帶寬并增加共享無線信道的沖突機率，這種問題又稱“路由應答風暴”［6］。

因此，可以利用無線信道的廣播特性對路由應答分組隨機延遲一段時間后再判斷是否進行傳輸，以減少不同節點同時發送路由應答的機率。

4）在路由請求中使用擴展環搜索

在路由請求的傳播過程中，Ad Hoc網絡內的所有節點都可能收到并傳播任何節點的路由請求，這種情況將大大造成網絡的擁塞。為了減少這種網絡開銷，源節點應當采取一定措施限制對路由請求的傳播的最大值，例如擴展環搜索，算法如下：（1）源節點在進行路由請求時，首先發送一個限制傳播范圍在一跳之內的路由請求，稱為非傳播型路由請求；（2）如果在協議規定的時間參數內沒有收到對非傳播型路由請求的路由應答，源節點再發送一個傳播范圍限制在6跳之內的路由請求。

因此，當S試圖請求到D的路由時，它有可能發送兩次路由請求：一次是非傳播型路由請求，一次是限制傳播范圍在6跳之內的路由請求。由于非傳播型路由請求要求所有與本節點在一跳范周之內的節點進行路由應答，那么如果D在本節點的一跳范圍內，D可以立即進行路由應答；否則，如果本節點的鄰居中有節點具有到D的路由，那么它們可以進行路由應答，相當于本節點有效地利用了鄰居節點的路由表對自己的路由表進行擴展。在這種情況下，S不必在兩次發送路由請求之間進行規避。由于非傳播型路由請求限制在一跳范圍內，其超時的時間設置應當取一個很小的值。

3.3 路徑維護

由于網絡節點具有較強的移動性，Ad Hoc網絡在拓撲結構發生變化后，源節點S到目的節點D的路由可能因為該路由中的某一跳失敗而不再有效，此時必須依靠路由維護機制使S及時檢測到該變化。當路由維護機制檢測到一條路由變壞時，S可以嘗試使用它偶然學習到的其它到D的路由，或者啟動路由發現尋找一條新的路由。

路由維護提供一種機制來維護S和D之間路由的連通性。Ad Hoc網絡中的每個節點都維護一張路由表，用來維護本節點到其它節點的路由。當網絡拓撲發生變化時，節點根據收到的信息更新自己的路由表，使它與網絡拓撲保持一致。

路由維護有三種基本手段：（1）定期發送路由公告，在節點之間交換路由信息，以維護路由；（2）通過路由應答獲取和維護路由；（3）通過路由學習獲取和維護路由。

1）路由公告

當AdHoc網絡處于相對靜止的使用環境中，如果采用按需路由協議，在第一次發送數據分組時，往往由于沒有去往目的節點的路由，需要啟動路由發現過程；如果采用主動路由協議，通過相鄰節點周期性地相互交換路由信息，可以在發送數據分組之前知道去往目的節點的路由，分組到達目的節點的時間比采用按需路由協議要短，但這種速度優勢是以消耗信道帶寬為代價的［7］。

為了彌補按需路由協議在相對靜止網絡環境下的不足，本協議適當地采用了主動路由協議中的鄰邊維護機制，即：網絡中所有節點每隔一定時間向相鄰節點發送路由公告分組，且令該分組的TTL＝l，路由公告分組中包含本節點的路由表等內容，鄰居節點根據收到的路由公告分組更新本節點的路由表。

2）拓撲結構獲取

在Ad Hoc網絡中，網絡拓撲結構信息的獲取有兩種方法：一是各個節點周期性或事件觸發的路由公告，二是各個節點發送的數據分組。

路由公告用于報告本節點的路由信息、它根據所收到的鄰居節點和一跳以外其它節點的信息，節點周期性地將自己的路由表通過路由公告的形式向相鄰節點廣播，主要目的：一是報告自己的存在；二是與相鄰節點交換路由表。通過路由公告，各個節點可以得到網絡的拓撲信息。

節點收到一個分組時，首先判斷該分組的類型。如果該分組不是路由公告，則提取分組頭部，處理其中的路由信息，同時根據該分組的數據類型對分組進行相應處理；如果當該分組是路由公告，則提取并處理其中的路由信息，處理完畢后如果發現網絡拓撲發生了變化，則更新本節點的路由表，并發送路由公告［8］。路由公告中包含節點的路由表內容，路由表以二維矩陣的形式表示。RouteTable［m，n］表示節點m到節點n的單向信道的邊權值。

（1）當節點通過收到的路由請求分組、路由應答分組、數據分組中的路由信息更新路由表的時候，將相關矩陣元素值初始化為MaxLifeValue；

（2）與路由錯誤分組中的路由信息對應的相關矩陣元素值初始化為－MaxLifeValue；

（3）節點每隔TimeRefreshInterval對路由矩陣中的鏈路權值減少LifeShortScale，鏈路邊權值越大說明鏈路越可靠；

（4）收到相鄰節點的路由公告后，節點將路由公告的路由表中的邊權值和自己路由表中的邊權值進行比較并進行更新，然后節點根據新的路由表采用最短路徑算法得到更新后的路由表：（IfNew［i，j］＞Old［i，j］，則用新的權值更新路由表；（IfNew［i，j］＜Old［i，j］，則保留本節點的權值。

Ad Hoc網絡中的節點可以自由入網或者退網，因此將會產生新的無線鏈路，鏈路質量的變化或者節點的入網與退網將觸發路由公告。路由公告的觸發機制為：（1）將失效鏈路的權值設為0；（2）將新的鏈路的權值設為 MaxLifeValue；（3）修改自己的路由表，并構造一個路由公告分組，廣播最新的鏈路狀態信息。

3）鄰邊維護

在本路由協議中，將網內任何兩個節點之間的有向鏈路定義為一條“邊”。由于無線信道的傳輸質量較差，在進行路由選擇時不僅要考慮源節點和目的節點之間的距離（即跳數），而且還要結合不同路由的邊權值，以便更好地反應鏈路的當前通信狀態。在每個節點的路由表中都保存有到其它節點的邊的權值，進行路由公告時每個節點將本地路由表與鄰居節點進行交換，這樣一來不僅能夠維護自己的路由，而且可對邊和權值進行更新。當邊權值發生變化時，相應地觸發路由公告，將此信息通知鄰居節點，從而實現鄰邊維護功能。

鄰邊維護的規則如下：（1）如果一個分組從源路由重傳到泛洪重傳都是失敗的，沒有任何形式的分組確認，則認為源節點到目的節點的邊的可信度降低，例如將可信度減半；（2）如果收到一個分組，則發送該分組的源節點和本節點的邊的可信度設為最大值；（3）如果收到一個泛洪分組，該分組前面已經采用源路由發送過，則分組的源節點和本節點之間的雙向邊的可信度減半；（4）對于源路由分組，本機作為中間節點如果轉發成功，則本節點和下一跳節點之間的雙向邊的可信度設為最大值。

3.4 選路算法

當S需要在本地路由表中尋找一條到D的最優路由時，可以采用多種算法，如果考慮鏈路的權值，則最優路由是從S到D的所有鏈路的權值或者代價總和最小的一條路由。在本路由協議中，結合邊的權值作為路由選擇的依據。源節點采用Dijkstra算法。

Dijkstra算法用于計算一個頂點到其他所有頂點間的最短路徑，其能得出最短路徑的最優解，是典型的單源最短路徑算法。為了求得這些最短路徑，Dijkstra按路徑長度遞增，逐次產生源點到其他頂點間的最短路徑。首先求出長度最短的一條路徑，然后參照它求出長度次短的一條最短路徑，以此類推，直到從頂點到其他頂點的最短路徑全部求出為止［9］。該算法的具體描述如下：

集合S：存放已經求出最短路徑的終點，初始狀態下，S中只有一個源節點v0。以后每求得一條最短路徑（v0，…，vk），就將vk加入到集合S中。直到全部頂點都加入到集合S中，算法結束。

使用數組dist存儲當前找到的從源節點v0到其他節點的最短路徑長度，每個頂點對應該數組中的一個元素dist［i］，這個元素存放當前源點到該頂點的最短路徑長度，如果路徑不存在的話便是無窮大。dist的初始狀態是：若從源節點v0到終點vi有邊，則dist［i］為該邊上的權值；若從源點到終點沒有邊，則dist［i］為＋∞。此時的路徑指示當前結果，并不一定是最終的最短路徑。隨著集合S的變化，其他節點不斷地加入到集合中，可能以這些新加入的頂點為“橋梁”產生比以前路徑更短的路徑，dist數組元素的值是動態變化的。

1）設第一條最短路徑為（v0，vk），其中k滿足：dist［k］＝min｛dist［i］｜vi∈V－v0｝（V為所有頂點集合）。

2）求下一條最短路徑：假設下次最短路徑的終點是vj，則可想而知，它或者是（v0，vj），或者是（v0，vk，vj）。其長度或者是從v0到vj邊上的權值，或者是dist［k］與從vk到vj邊上的權值之和［10］。

一般情況下，假設S為已經求得最短路徑的頂點集合，則可以證明：下一條最短路徑必然是從v0出發，中間只經過S中的頂點便可到達的那些頂點vx（vx∈V－S）的路徑中的一條。因此在一般情況下，下一條次短的最短路徑的長度必是：

3）在每一次求得一條最短路徑之后，其終點vk加入集合S，然后對所有的vi∈V－S，修改其dist［i］：dist［i］＝min｛dist［i］，dist［k］＋edge［k］［i］｝，其中，edge［k］［i］為邊（vk，vi）上的權值。

4 協議的編程實現層次模型

本路由協議在實現上分為五層：物理層、數據鏈路層、網絡層、運輸層、應用和服務層。網絡應用程序不直接與網絡硬件交互，應用于協議軟件交互，在設計無線網絡協議棧時，除了必須考慮固有的無線信道問題、移動性問題以外，還需要考慮能量效率問題［11］。協議的編程層次模型如圖2所示。

圖2 協議層次模型圖

1）應用和服務層

應用和服務層負責信源編碼、數字信號處理、移動環境下的自適應。應用和服務層提供的服務是變化的、面向具體應用的。

2）傳輸層

運輸層實現端對端的數據傳送功能。負責提供網絡端點之間的高效、可靠的IP數據傳輸，而與使用的物理網絡無關。

3）網絡層

網絡層完成區域內所有站點上的區域內路由選擇和區域出口站點上的區域間路由選擇，維護網絡拓撲結構信息；負責給分組尋找傳輸路由、建立網絡服務類型、傳輸層與數據鏈路層之間的分組傳遞。在移動Ad Hoc網絡環境中，網絡層還要負責分組的轉發路由，以及移動性管理。

4）數據鏈路控制

數據鏈路控制層負責在不可靠無線鏈上建立可靠、安全的邏輯鏈；負責無線鏈的差錯控制、安全、將網絡層分組映射為幀、分組重傳；實現共享信道的多重訪問控制和依據信道質量進行的發送速率控制，以及站點間相鄰關系和信道質量信息的維護。

5）物理層

物理層包含射頻RF電路、調制、信道編碼系統。完成二進制數據與跳頻信號間的調制／解調功能，并且包含設備保密單元對跳頻信號序列的加密和解密，保證只有配備相同設備保密單元的站點間可進行數據傳送。

5 結語

根據產品實際需求，本文提出了一種反映鏈路質量的混合路由協議。該協議主要包括主動路由和按需部分，主動路由是基于鏈路－狀態法思想，體現在相鄰節點之間鏈路狀態信息的交換；按需路由是在現有按需路由策略中的路由請求／回答的交互過程基礎上增加了信道指標信息的傳播。經產品長時間使用驗證，該協議尋徑時間較短，路由協議開銷較小，能對鏈路狀態的變化做出快速反應，使用效果良好。

［1］趙迪，陳向東.Ad Hoc網絡兩種按需路由協議性能仿真分析［J］.通信技術，2010，43（4）：2－3.

［2］陳林星，曾曦，曹毅.移動Ad Hoc網絡－自組織分組無線網絡技術［M］.北京：電子工業出版社，2006：20－21.

［3］Hong X Y，Xu K X，Gerla M.Scalable routing protocols for mobile ad hoc networks［J］.IEEE Network，2002，16（4）：11－22.

［4］劉凱，李維英，李建東.支持多媒體業務的自組織無線網絡協議［J］.西安電子科技大學學報，2000，27（2）：190－194.

［5］周海剛，肖軍模.Ad Hoc網絡的安全問題和安全策略［J］.電信科學，2001，17（12）：39－42.

［6］矣昕寶，全海燕，董會升.一種用于Ad hoc網絡的精簡路由協議設計與實現［J］.科學技術與工程，2011，11（35）：40－41.

［7］米志超，鮑民權，鄭少仁.一種基于多跳Ad Hoc網絡的路由協議的設計與實現［J］.西安電子科技大學學報（自然科學版），2001，28（6）：707－710.

［8］鄭少仁，王海濤，趙志峰，等.Ad Hoc網絡技術［M］.北京：人民郵電出版社，2005：32－33.

［9］周滿元，周力為.基于不同源節點數目的AODV路由協議的性能比較研究［J］.計算機工程與應用，2007，43（18）：94－96.

［10］Akyildiz l F.A Survey on Wireless Mesh Networks［J］.IEEE Communications Magazine，2005，43（9）：23－30.

［11］Wolfgang kiess，Martin Mauve.A Survey on realworld Implementations of Mobile Ad－Hoc Networks［J］.Ad Hoc Networks，2007，5（3）：324－339.