一種基于路徑信息的WSN路由協議*

韓江洪 ，江 月 ，馬學森 ，官駿鳴 ,3

（1.合肥工業大學計算機與信息學院 合肥 230009；2.安全關鍵工業測控技術教育部工程研究中心 合肥 230009；3.黃山學院信息工程學院 黃山 245021）

1 引言

WSN（wireless sensor network，無線傳感器網絡）是一種無基礎設施的網絡，它由一組具備無線收發能力的傳感器節點以自組織方式構成，其目的是協作感知和處理網絡覆蓋地理區域中感知對象的信息，并將這些信息傳送給需要的用戶。MANET（mobile Ad Hoc network，移動 Ad Hoc 網絡）是由一組無線移動節點組成的一種不需要依靠現有固定通信網絡基礎設施的、能夠迅速展開使用的、具有自組織功能的網絡。就網絡傳輸技術而言，WSN和MANET沒有太大的本質區別，在MANET終端上配置傳感器處理單元就是WSN，因此WSN和MANET被統稱為自組織網絡。但從路由的角度看，WSN并不完全等同于MANET，它有自己的特點：如節點不移動或很少移動，節點的能量有限、通信能力較弱等[1,2]。WSN的固有特性使得MANET的路由協議并不完全適用于WSN。

AODV（Ad Hoc on-demanding distance vector，Ad Hoc 按需距離矢量）是MANET中應用最廣泛的按需路由協議。它定義了路由請求（RREQ）、路由應答（RREP）和路由錯誤（RERR）3種控制消息。當一個源節點需要一條路由到達某個目的節點，但是沒有現成可用路由或者以前到達該目的節點的有效路由為無效的時候，該源節點就廣播一個RREQ分組。如果在限定的等待時間內沒有收到相應的RREP分組，那么源節點重新廣播RREQ分組，直到找到一條新路由或者重復尋找的次數達到限定的最大值。節點接收到RREQ分組后，首先確定自己是否已經接收過這樣的RREQ分組，如果是，就丟棄該RREQ分組；否則，在路由表中創建一個到達源節點的反向路由條目，并繼續廣播該RREQ分組。如果該節點本身就是所請求的目的節點，或者該節點是一個中間節點且有一條“足夠新”的路由到達所請求的目的節點，那么它將產生一個RREP分組，并以單播方式將該RREP分組發送給源節點。源節點在收到RREP分組后開始向目的節點發送數據[2～5]。

AODV協議在多種不同的拓撲和環境下經歷了嚴格的測試，具有較高的正確性和強壯性。與其他協議相比，AODV協議提供對動態鏈路狀況的快速自適應，處理開銷和存儲開銷較低，因此在WSN的研究中常常借用AODV協議[1,6]。但是，AODV協議在路由查找過程中采用洪泛方式向全網廣播RREQ分組，若在節點密度大、能量有限的WSN中直接使用，則會造成網絡開銷過大、平均端到端時延過長等問題。針對WSN的特點，本文提出了一種基于路徑信息的WSN路由協議——IAODV（improved AODV），該協議可以有效地解決上述問題。

2 IAODV協議的設計

IAODV協議的設計目標是在保留AODV協議的強壯性、高效性和良好的自組織性等優點的前提下，對其基于洪泛的路由查找機制進行改進，使其成為適合WSN的低開銷、低時延的路由協議。

WSN中的節點在部署完成之后大部分不會再移動，雖然部分節點因調度機制或失效等原因而出現網絡拓撲改變的情況，但這些變化具有明顯的周期性和間歇性，所以WSN的拓撲可以認為是準靜態的。此外，WSN的工作模式通常是網絡中的所有節點將數據匯聚到Sink節點，即多對一的通信，節點之間幾乎不會發生消息交換[1]。

針對WSN的特性，研究人員提出了很多AODV協議改進方案，LAR（location-aided routing，位置輔助路由）協議就是典型的代表。LAR協議使用地理位置信息為AODV限定了一個路由請求區域，稱為尋找域，只有位于尋找域內的節點才可以轉發RREQ分組，從而有效地減少了路由尋找開銷。在LAR中，當源節點向目的節點發起路由請求時，先將一個以源節點和目的節點之間的連線為對角線的矩形區域定義為尋找域 （另一種常用的算法是將距離目的節點較近的節點所在的區域定義為尋找域），如果在限定的生存時間內沒有找到新的路由，源節點將進一步擴大尋找域，重新發起路由搜索[1,7]。在WSN中，由于節點不移動或很少移動，使用GPS能夠很容易地確定節點自身的位置，并且目的節點大多數情況下是惟一固定的，這就免除了對目的節點位置信息的維護，因此LAR協議可以較好地運用在WSN中。但是，由于WSN的節點分布情況根據不同的應用復雜多樣，源節點到目的節點的路徑走向及其范圍難以控制，用LAR協議源節點往往需要多次增大尋找域，重新進行查找嘗試，從而大大增加了時延和網絡開銷。因此，如何較快地確定適合具體應用的尋找域，是提高協議性能的關鍵。IAODV協議的設計就是著眼于這一關鍵問題。

基于WSN準靜態的拓撲和多對一的工作模式，不但可以認為WSN的目的節點是惟一、固定的，而且源節點到這一固定目的節點的傳輸路徑也可以視作準靜態的，因此IAODV協議考慮利用路徑信息對AODV協議基于洪泛的路由查找機制進行改進。先用AODV協議尋找路由進行數據傳輸，當原先的路由走不通或路由期滿失效時，基于WSN的準靜態性，新的路由和原來的路由應該相差不大，可以原來的路由為基準進行新的路由查找。具體地說，就是將原傳輸路徑近似看作一條基準傳輸路徑，并將其附近的一個特定范圍定義為尋找域，將路由查找限制在該尋找域內，即在路由查找過程中，只有位于該尋找域內的節點才可以廣播RREQ分組。例如，將查找控制在基準傳輸路徑的最大傳輸范圍內，如圖1所示，S為源節點，D為目的節點，實心節點代表基準傳輸路徑中包含的節點，實線代表基準傳輸路徑，虛線圓表示相應圓心節點的最大傳輸范圍，相鄰圓的重疊區域即為尋找域。為了擺脫對GPS的依賴，IAODV協議采用跳數作為尋找域大小的計量單位，即將距離基準傳輸路徑K跳的范圍定義為尋找域，其中K值在源節點第一次發起路由查找時設置為某一固定的經驗值。當路由查找超時，需要重新發起路由查找時，源節點可以通過增大K值很方便地擴大尋找域，而不需要任何復雜的算法。

圖1 以基準傳輸路徑的最大傳輸范圍為尋找域

將保存在節點中的原路由信息定義為基準路徑信息Pstd，為了在路由查找過程中利用基準路徑信息Pstd，可以借鑒 DSR（dynamic source routing protocol，源動態路由協議），采用在RREQ分組中攜帶完整的基準傳輸路徑信息的方式。這樣做雖然能夠方便地利用路徑信息，但是增加了RREQ分組長度，大大增加了網絡開銷[8,9]。為了節省網絡開銷，IAODV協議借鑒有線網絡中虛電路的分組交換實現方式，用特定的目的節點和虛電路號來標識相應的基準路徑信息Pstd。當所請求的目的節點接收到RREQ分組時，該目的節點通過將已有的最大虛電路號加1的方式生成一個新的虛電路號，并將其標識在RREP分組中，再按照單播的方式將該RREP分組發送給源節點。如果產生RREP分組的節點是中間節點，則將該中間節點到達所請求的目的節點的虛電路號直接標識在RREP分組中。當一個中間節點收到該RREP分組時，先讀出RREP分組中的虛電路號，并將其同對應的目的節點記錄下來，作為一條基準路徑信息Pstd保存在節點中。當源節點再次發起到目的節點的路由查找時，只要在RREQ分組中攜帶到達該目的節點的虛電路號，就可以方便地在路由查找過程中利用路徑信息。由于虛電路號是一個unsigned型的整數，僅一個字節的虛電路號就可以標識255條不同的路徑 （預留0號標識尚未建立基準路徑的情況），已經基本可以滿足一般規模的WSN的應用要求，因此在具體實現時可以通過重新定義原RREQ和RREP分組中的保留字段來標識相應的虛電路號，從而既達到了攜帶所需的路徑信息的目的，又不會增加控制分組長度。

相比于LAR利用節點的位置信息確定尋找域的方式，IAODV協議利用路徑信息確定尋找域的方式依據WSN的具體應用中節點和路徑分布的情況，能夠更快地獲得符合具體應用的合適的尋找域，并且擺脫了對GPS的依賴，免除了相關的額外開銷，具體實現算法也更簡單，從而更加有效地限制AODV路由查找的范圍，加快路由算法的收斂速度，減少網絡的開銷，實現低開銷、低時延的設計目標。

3 IAODV協議的實現

根據上述設計方案，IAODV協議在AODV協議的基礎上進行了以下改進。

（1）在每個節點中存儲一張路徑列表，記錄其到各個目的節點的虛電路號即基準路徑信息Pstd以及定義尋找域的K值

顯然，這里的路徑列表長度等于WSN中Sink節點的個數。由于WSN采用多對一的工作模式，通常即使是一個覆蓋范圍很廣、節點數量眾多的WSN，其中Sink節點的數量都是相當有限的，因此路徑列表所占存儲空間很少，且搜索列表所需時間在計算傳輸時延中基本可以忽略不計。

（2）對RREQ分組和RREP分組進行擴展，并在路由查找過程中增加與之相關的處理

對RREQ分組進行擴展，增加Standard Path、Threshold和Counter字段。Standard Path字段用于記錄到達所請求的目的節點的虛電路號；Threshold字段用于記錄定義尋找域的K值；Counter字段用于記錄新路由距離基準傳輸路徑的跳數。當節點需要發起路由查找時，如果本地路徑列表中有到所請求的目的節點的表項，則將該表項中的虛電路號和K值分別填入RREQ分組中的Standard Path字段和Threshold字段，Counter字段置為0，并且源節點每進行一次路由尋找嘗試，Threshold加1；否則，將Standard Path字段置為0，表示尚未建立起相應的基準傳輸路徑，此時Threshold字段和Counter字段的值無效。當節點接收到RREQ分組時，如果其中的Standard Path字段為0，則不做任何變動，否則根據其中的目的節點地址和Standard Path字段搜索本地路徑列表，通過查找包含相同基準路徑信息Pstd的表項來判斷本節點是否在基準傳輸路徑上。如果在，則將RREQ分組中的Counter字段歸零，否則將Counter字段值加1。如果Counter字段數值不大于Threshold字段數值，則繼續廣播該RREQ分組，否則將該RREQ分組丟棄。

對RREP分組進行擴展，增加一個Standard Path字段，用于記錄建立的虛電路號。當所請求的目的節點或具有一條“足夠新”的路由到達所請求的目的節點的一個中間節點接收到RREQ分組，如果該RREQ分組中的Standard Path字段不為0，則將其填入RREP分組中的Standard Path字段；否則考慮以下兩種情況：如果該節點是所請求的目的節點，則將現有的到該目的節點的最大虛電路號加1作為新路徑的虛電路號，然后填入RREP分組的Standard Path字段；如果該節點是一個有一條“足夠新”的路由到達所請求的目的節點的中間節點，則將其路徑列表中到達所請求的目的節點的虛電路號填入RREP分組的Standard Path字段。

4 仿真及分析

4.1 仿真場景設置

通過在NS2[10]仿真軟件中對由30個源節點和3個Sink節點構成的WSN進行多次模擬實驗來比較AODV和IAODV兩種協議的性能。為了對比在不同業務量條件下兩種協議的性能，分別對由不同的源節點數據采集上傳周期構成的業務模型進行了測試。業務模型的主要參數如下：業務類型為CBR；數據采集上傳周期分別為 0.5 s、1 s、2 s、3 s、4 s、5 s、6 s；仿真時間為 100 s；網絡范圍為 90 m×50 m。所有仿真數據均為3次不同種子條件所得到的平均值。

4.2 性能評價參數

通過分組投遞率、平均端到端時延和標準路由開銷3個參數來比較IAODV和AODV協議的性能。分組投遞率定義為交付到目的節點的數據分組數量與源節點發送的數據分組數量之比；平均端到端時延定義為一個數據分組成功到達目的節點所需的時間平均值；標準路由開銷定義為每接收到一個數據分組需要傳遞的路由分組的數目[11]。

4.3 仿真結果及分析

（1）分組投遞率

圖2顯示了IAODV協議和AODV協議分別在源節點數據采集上傳周期為 0.5 s、1 s、2 s、3 s、4 s、5 s和 6 s情況下的分組投遞率，可以看出IAODV協議能夠獲得比AODV協議更高的分組投遞率，并且隨著源節點數據采集上傳周期的減小，IAODV協議的分組投遞率下降幅度小于AODV協議。這是因為隨著源節點數據采集上傳周期的減小，網絡負載漸漸加大，網絡擁塞逐步加劇。IAODV協議限制了RREQ分組廣播范圍，有效節省了帶寬，緩解了網絡擁塞情況，因此IAODV協議可以在網絡負載較大的情況下取得較高的分組投遞率。

圖2 IAODV和AODV協議在不同數據采集上傳周期下的分組投遞率

（2）平均端到端時延

圖3顯示了IAODV協議和AODV協議在不同情況下的數據分組平均端到端時延，可以看出IAODV協議的分組平均時延比AODV協議小很多，并且隨著網絡負載的減小，IAODV協議的分組平均時延下降幅度遠遠大于AODV協議。因為IAODV協議的路由查找收斂速度大于AODV協議，因此分組平均時延會大大降低。另外，IAODV協議在數據采集上傳周期為3 s時，平均時延達到最小，然后隨著周期的繼續增大，平均時延開始增大。這是由于數據采集上傳周期過大，當源節點再次要求向Sink節點上傳數據時，原路由已經期滿失效，必須查找一條新的路由。

圖3 IAODV和AODV協議在不同數據采集上傳周期下的平均端到端時延

（3）標準路由開銷

圖4顯示了IAODV協議和AODV協議在不同情況下的標準路由開銷，可以看出，不論網絡負載大小，IAODV協議的標準路由開銷都明顯小于AODV協議。IAODV協議通過限制RREQ分組的廣播范圍大大減少了路由分組數量，減小了路由開銷。

圖4 IAODV和AODV協議在不同數據采集上傳周期下的標準路由開銷

5 結束語

AODV協議在路由發現時選擇短路徑，IAODV協議將AODV尋找到的傳輸路徑作為基準傳輸路徑的做法可以滿足對實時性要求比較高的應用的需求，但是對于具有較高的節能要求的應用就需要選擇一條平均每跳距離較短的路徑作為基準傳輸路徑，以盡可能降低節點的能耗，因此下一步的工作重點是研究如何找到一條能夠同時滿足實時性和節能性要求的路徑作為IAODV協議的基準傳輸路徑。

1 李曉維.無線傳感器網絡技術.北京：北京理工大學出版社，2007

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

3 王斌.無線傳感器網絡AODV路由協議的實現.計算機與現代化，2009（1）:86～89

4 IETF RFC 3561.Ad hoc on-demand distance vector(AODV)routing,2003

5 Chen Canfeng,Ma Jian.Simulation study of AODV performance over IEEE 802.15.4 MAC in WSN with mobile sinks.In:21st International Conference on Advanced Information Networking and Applications Workshops,2007（2）:159～164

6 鄭凱，王能，劉愛芳.一個基于AODV的漸進式分簇路由策略.通信學報，2006，27（1）:132～139

7 Ko Y B,Vaidya N H.Location-aided routing (LAR)in mobile ad hoc networks.Wireless Networks,2000,6（4）:307～321

8 喻勇，劉凱歌，胡軍.可自擴展的DSR路由協議的性能分析與仿真.計算機工程與設計，2007，28（19）:4652～4654

9 Johnson D B,Maltz D A,Hu Yinchun.The dynamic source routing protocol for mobile Ad Hoc networks,http://www.ietf.org/internet-drafts/draft-ieft-manet-dsr-10.txt

10 徐雷鳴，龐博，趙耀.NS與網絡模擬.北京：人民郵電出版社,2003

11 官駿鳴，陸陽，盛鋒等.基于節點接入能力的Ad Hoc網絡按需路由協議.通信學報,2007,28（10）:32～37