基于跨層設計的傳感器網絡路由協議

摘要：根據MANET中的AODV路由協議，采用跨層設計的方法，通過節點距離估計模塊、延時發送模塊和高效廣播模塊對AODV路由協議進行了改進，提出一種適用于傳感器網絡的CAODV路由協議。計算機仿真證明CAODV在保證網絡數據成功傳送率不下降的情況下，能在降低網絡開銷、減少路由建立時間等方面取得良好的性能。

關鍵詞：路由協議； 跨層設計； 傳感器網絡

中圖分類號：TN929.5文獻標志碼：A

文章編號：1001－3695(2008)03－0851－04

0引言

無線傳感器網絡(wireless sensor networks， WSN)是由具有傳感、數據處理和短距離無線通信功能的傳感器組成。在戰場、環境監測、搶險救災以及商業應用等領域具有廣闊的應用前景。從某種意義上來講，WSN是移動自組織網絡(mobile Ad hoc networks，MANET)的一種特殊形式。WSN具有一些顯著的特點，如節點不移動或很少移動、數據包更為短小、節點的計算、存儲、通信能力較低、節點數量和節點密度較高等。WSN的這些固有特性使得傳統網絡以及MANET 的路由協議不能有效地應用于WSN。

AODV（Ad hoc ondemand distance vector routing）[1]是MANET一種成熟度較高的按需路由協議，有較好的性能表現。在AODV協議中，每個節點均維護路由表，AODV包括路由發現過程和路由維護過程。在路由發現過程，AODV使用洪泛機制實現；在路由維護過程，若源節點或路由上游節點移動使路由斷鏈，則由源節點重新發起路由發現過程；如果路由下游節點移動使路由斷鏈，則由斷鏈鏈路的端點進行局域路由修復。由于WSN的節點密度大以及AODV在路由發現過程中使用洪泛機制，若直接使用AODV協議會造成網絡的開銷很大，RREQ（route request）報文的沖突幾率高等問題。針對WSN的特點，提出一種采用跨層設計的高效AODV路由協議（crosslayer AODV，CAODV）來解決上述問題。

1研究現狀

目前，已存在數十種以WSN為網絡環境的路由協議，對于已提出的路由協議，可以從不同的角度進行分類。根據發現路由策略，可以將其分為主動路由協議和按需路由協議；根據源節點和目的節點之間的路由采用的路徑數的不同，可將其分為單徑路由協議、替代路徑路由協議和多徑路由協議；根據網絡邏輯結構，可以將其分為平面路由和分級路由；根據是否使用節點位置信息，可將其分為位置輔助的路由和無位置輔助的路由等。WSN中的路由協議分類如圖1所示[2]。

平面路由中較有代表性的有GBA（gossipbased Ad hoc routing）[3]和SPIN（sensor protocols for information via negotiation）[4，5]等。GBA的核心思想是通過GOSSIP法則實現，GOSSIP（ρ1，k；ρ2，n）代表在k跳內節點以概率1轉發報文，在k跳外以ρ1（節點鄰居數量小于n）或ρ2（節點鄰居數量大于n）概率轉發報文。GBA能降低路由洪泛報文，但由于是基于概率轉發機制，性能與網絡節點的分布情況密切相關，不能得到有效保障。SPIN是WSN中的一種重要路由協議，SPIN采用協商的方法來提高網絡的傳遞效率，SPIN采用元數據（metadata）的方法對需要傳送的數據進行描述。SPIN有三種格式的消息：ADV消息，用于數據傳送前的廣播，使用元數據來區分不同的數據包；REQ消息，ADV的應答消息，表明該節點需要此數據；DATA消息，使用元數據作為頭部的數據包。SPIN中，節點可根據自身資源和應用信息決定是否進行ADV通告，能在一定程度上避免盲目傳播，但當網絡節點中的sink節點較少時，數據傳送較為困難。

分級路由中較有代表性的有LEACH（low energy adaptive clustering hierarchy）[6]、PEGASIS (powerefficient gathering in sensor information systems)[7]、TEEN (thresholdsensitive energy efficient sensor network protocol)[8]、TTDD (twotier data dissemination)[9]等。LEACH是一個采用了數據聚合的分級路由協議，通過周期性按輪隨機選舉簇頭去平衡節點的能耗，節點將數據傳送給簇頭，簇頭將聚合后的數據傳送給sink節點。LEACH中采用的分層聚合機制提高了數據傳輸的效率，但要求節點具備一跳通信的能力。PEGASIS是對LEACH的拓展，降低了選取簇頭的開銷，利用令牌控制數據的傳輸。TEEN也采用類似于LEACH的分層結構，其特點是在數據傳輸時使用了過濾機制，通過設置硬門限和軟門限來控制是否傳送數據，提高了數據傳送效率。TTDD采用網格的思想解決數據的查詢和傳遞，支持接收節點移動。

位置輔助的路由協議中有代表性的有GAF(geographic adaptive fidelity)[10]、GEAR(geographic and energy aware routing)[11]等。GAF預先將網絡分區以形成虛擬的網格，每個區域內的節點相互協作以完成任務。節點通過自身GPS以及虛擬網格指針來指示當前的位置。為了節能，GAF中的節點有三種狀態，即發現狀態—探測網格中的鄰居、激活狀態—路由響應和睡眠狀態—關掉發射器。GEAR根據數據查詢通常包括地理屬性這一特性，在分發查詢信息時使用地理信息，并采用漸進的方式將數據傳送到目的節點。GEAR的關鍵思想在于通過位置輔助信息，限定了興趣包的傳播范圍，可取得較好的性能。

2基于跨層設計的AODV路由協議

目前，在無線網絡設計中主要是基于傳統的協議分層和功能分層機制，每一層分別設計并且相互獨立。層間接口是靜態并且獨立于個別的網絡約束和應用。這種體系結構模型在互聯網中極大地簡化了網絡設計并且可以得到具有良好魯棒性和擴展性的協議[12]。但在WSN中，網絡的每一個協議層都是相互關聯的，傳統的分層模型將限制網絡的性能。例如MAC層的功率調整會改變網絡拓撲，從而影響到路由協議的運行效果；IP層的分包大小會影響到MAC的效率；應用層需要利用其下面任意一層的狀態以實現高質量的服務。傳統分層協議在目標優化上通常只能在某一層進行，總體協調能力較差，而跨層設計可以支持多層的聯合優化和自適應。

WSN的網絡拓撲結構有星狀網、網狀網、混合網(分層網)三種，如圖2所示。星狀網拓撲結構是單跳(singlehop) 結構，如同傳統的GSM網絡中，所有終端節點直接與基站進行雙向通信，而彼此之間并不建立連接；網狀網拓撲結構是多跳的結構，網絡中的所有無線傳感器節點可以直接通信，通過一定的算法，網絡選擇一條或多條路由進行多跳數據傳輸；混合網網絡結構兼具星狀網的簡潔以及網狀網的抗毀性。星狀網是一跳可達，無須路由協議，數據發送可以設置為定時發送。網狀網和混合網中數據的傳遞往往需要多跳才能實現，需要路由協議支持。本文主要解決網狀網和混合網中的路由建立問題。

2．1CAODV協議設計框架

AODV是MANET網絡中的一種按需路由協議，由于節點處于非活動狀態時不需要維護路由，可以獲得較小的網絡開銷。AODV在路由發現中使用洪泛機制，每個節點在第一次收到路由RREQ報文時都需要進行轉發。這種機制在MANET是可行的，因為MANET網絡的節點數量多數在幾百個之內，但WSN網絡中的節點數量巨大，若直接使用AODV路由協議，會造成很大的網絡開銷，且RREQ報文的沖突幾率高，以至于過多浪費節點的能量。針對上述問題，提出一種跨層設計的CAODV協議，設計框架見圖3，實現方案如下：

a)降低網絡開銷。降低網絡開銷通過高效廣播模塊實現。高效廣播模塊的實現機制是在節點轉發RREQ報文前，通過節點的兩跳鄰居信息，判斷其鄰居是否都已經收到相應RREQ報文，若均已收到，則丟棄該數據包；否則對該RREQ報文進行轉發。

b)降低RREQ報文的沖突幾率。降低RREQ報文的沖突通過延時發送模塊實現。由于WSN中節點密度大，在節點的一跳范圍內會有較多的鄰居，當節點發送RREQ報文時，其鄰居幾乎會同時收到該報文，這就可能會造成這些鄰居幾乎同時轉發該報文，引起RREQ報文的沖突。筆者計劃在MAC層通過對接收信號強度的估計，判斷節點間的距離遠近，然后通過跨層信息交互，在路由層對RREQ報文的轉發引入延時機制，并使距離較遠的節點先轉發RREQ報文。

2．2CAODV實現機制

MANET中的AODV路由協議在廣播RREQ報文時，其鄰居將收到這個報文并一一進行轉發。顯然其中許多報文的轉發都是不必要的，這種情況在MANET中是可以容忍的，但對比MANET更加缺乏資源的WSN，網絡的代價就會相當可觀。CAODV的實現機制如圖4所示，節點i為源節點；節點m和n均為目的節點（j）方向上的節點，且n較m更遠離源節點（i）。若n已較早地轉發了RREQ報文，則節點m盡可能地不轉發該報文。

圖3CAODV協議設計框架圖4CAODV中RREQ報文轉發規則

要實現上述的這種情況，需要對AODV路由協議中RREQ報文轉發的規則進行優化：a)使遠離源節點的中間節點能較早地轉發報文；b)若鄰居節點均已收到該RREQ報文，則丟棄該報文。

2．3CAODV協議的實現

基于前面提到的報文轉發規則，CAODV中需要解決兩個問題：a)需要對不同的節點設置不同的廣播報文退避時間；b)節點要能判斷自身鄰居接收廣播報文的情況。在CAODV中，廣播報文退避時間設計為節點間距離的減函數，使距離較遠的節點能較早地轉發報文，保證RREQ報文在網內快速轉發。節點鄰居接收廣播報文的狀態是通過鄰居列表信息的交換實現，節點可判斷自身的鄰居是否均已收到RREQ報文，從而決定是否轉發RREQ報文，可減少RREQ報文重復轉發的數量，降低網絡的開銷。

2．3．1節點RREQ報文退避時間的設置

1）節點距離的獲得

節點間距d的獲取通常有兩種方式：a)基于GPS輔助的相對距離計算;b)基于接收信號強度的相對距離估計。基于GPS輔助的距離計算需要在節點中增加GPS接收模塊來提高對WSN節點的硬件能力的要求，并且GPS對應用環境要求無阻擋，該方法目前不太適宜于WSN網絡；基于接收信號強度的相對距離估計方法是根據發射功率、接收功率以及無線信道模型等參數計算出節點間的相對距離，該方法無須在節點處增加其他硬件設備，較為適用于WSN網絡。CAODV中采用基于接收信號強度的相對距離估計方法完成節點間相對距離的估計。

基于接收信號強度的相對距離估計實現方法如下：若節點的最大發射功率為Pmax，接收到的信號強度為Preceived，接收門限為Pthreshold，根據無線傳輸模型，有Preceived=KPmax/(dn)。其中：K為常數；n對應于傳播模型中的距離衰減指數。節點間的距離可以通過下式得到：

d=nK1Pmax/Preceived=KnPmax/Preceived(1)

其中：K=nK1。

2）廣播退避函數設計

節點廣播的RREQ報文，受其覆蓋半徑、目的節點所處位置以及鄰居節點的分布情況等因素的制約，所能到達的區域是不同的。為了便于后面的分析，CAODV中對節點的前向有效覆蓋區域如圖5所示，作如下定義：在報文傳送的目的節點方向上，若節點i轉發報文所能到達的最遠節點是節點n，則將節點i到節點n間的區域（圖4中的填充區域部分）定義為節點i的前向有效覆蓋區域。

圖5中是網絡中的某條路徑的等效情況。其中：S為源節點；D為目的節點；其他為中間節點；節點的最大覆蓋半徑為Rmax；region 1，region 2，…region i， …是路徑上以節點S為起點的前向有效覆蓋區域劃分。在靜態條件下，為了保證路徑上任意前向有效覆蓋區域內的節點實現由遠及近地廣播，在設計廣播函數時需要滿足以下要求：a)在某個特定的前向有效覆蓋區域內，隨著距離的增加，廣播退避函數值呈下降趨勢；b)滿足上述要求最為簡單的廣播退避函數在當前有效覆蓋區內的取值與其他有效覆蓋區無關。根據上述分析，將靜態條件下的廣播退避(broadcast backoff )函數設計為

TBBO=Tmax(Rmax-d)/Rmax(2)

其中：Tmax為廣播退避時間的最大取值；d是節點間的距離。

若在網絡中的節點存在弱移動性（CAODV中定義為節點運動速率小于3 m/s）的情況下，則式(2)需要進行修正。這是因為若路由協議總是選擇每跳中的最遠節點來作為中繼節點，會使路由斷鏈的幾率大大增加以至于導致路由重選，故將式(2)修正為

T′BBO=Tmax[int(d0-d)]/Rmax

這里d0的取值與節點的運動速率相關。在CAODV中，只考慮節點弱移動的情況下，將d0取定為0.8 Rmax。

3）退避時間設置

為了保證廣播報文在網內有序地前傳，廣播退避時間的設定遵循以下準則：當節點第一次接收到廣播報文時，根據節點間的等效距離計算出相應的退避時間，并將該值寫入到計時器；當收到重復報文時，不重新設定退避時間。

2．3．2節點鄰居信息交互

CAODV中為了節點交互鄰居信息，增加了一個HN（hello neighbor）報文，用于節點在一跳范圍內廣播其鄰居的增（減）量信息。

HN 消息格式如下:

Type1的定義與AODV路由消息一致，用來區分消息類別。在CADOV中，Type1設定為6。

Type－2用來區分HN是增量還是減量報文。

在CADOV中，Type－2為0時代表HN為增量報文；為1時代表HN為減量報文。

Body部分的長度可變，為8~240 bit。每個節點用8 bit長的編碼來區分，當增加或減少的鄰居數量超過30個時，鄰居增（減）量信息分段發送。

節點通過構建鄰居信息列表，判斷其鄰居是否已經接收過相應RREQ報文來降低RREQ報文的被轉發次數。節點構建鄰居信息列表有兩種，一種是節點一跳范圍內的鄰居廣播狀態列表；另一種是兩跳鄰居列表。表的形式如表1和2所示。

注：廣播標志位為1時表示節點收到過該廣播；為0時表示未收到過該廣播。

HN消息采用周期性發送的方式，但只有在其鄰居節點發生變化時才會進行發送。CAODV中節點通過兩種方式獲得其一跳鄰居信息，即監聽網絡數據交換和鄰居節點的信標（beacon）信息。

2．3．3高效廣播

為了進一步分析CAODV協議的有效性，有如下假設：

a）在節點i廣播退避這個時間段內，與節點i相關的兩跳以內的鄰居保持靜止狀態；

b）RREQ報文的接收沒有沖突。

用{Ni}表示節點i的一跳鄰居集合，當節點i第一次收到來自鄰居j的RREQ報文后，首先根據估計距離設置廣播退避時間，并將鄰居廣播狀態列表中與節點j相應廣播標志位設置為1。然后節點i計算和節點j的共同鄰居集{Ni， j}={Ni}∩{Nj}；接下來將節點i和j共同鄰居的廣播標志位也設置為1。在廣播退避時間減少到零前，若節點i又接收到相同的RREQ報文，則節點i需對鄰居廣播狀態列表進行重復上述操作。當廣播退避時間減少到零時，節點i檢查其一跳鄰居節點相應的廣播標志位是否均為1，若是，則丟棄該廣播報文；反之，轉發該報文。基于上述準則，有如下定理：

定理若節點i發送了一個RREQ報文，n是節點i的任一兩跳鄰居，則n定能收到i的廣播信息。

證明因為n是i的兩跳鄰居，則網絡中必有i的一個（至少1個）鄰居（記為j）是n的鄰居。在節點j的退避時間結束時，若其鄰居廣播標志位全為1，則節點n已經收到過該報文；若有部分標志位為0，節點 j將轉發該報文，在該情況下，若節點n的標志位已經為1，則n將重復收到該報文，不然，n將第一次收到該報文。由此可見，n定能收到i的廣播信息。

3CAODV仿真性能分析

為了評價CAODV路由協議的性能， 對CAODV的數據包成功發送率、路由請求報文平均副本數、平均路由建立時間、路由協議開銷總比特數四項指標進行了檢驗，其定義分別為

數據包成功發送率——successful data packet delivery rate(％)：該參數統計的是網絡中成功接收到的數據包與發送的數據包的比值，它反映了網絡對于數據業務的承載能力；

路由請求報文平均副本數——average copy of RREQ=網絡中RREQ報文的總個數/ RREQ源報文數，它反映了廣播報文的洪泛抑制情況；

平均路由建立時間: 該參數是在接收數據時由路由層統計的， 其統計的是一個數據包從源節點網絡層成功到達目的節點網絡層所平均經過的時間，該參數能反映網絡是否通暢， 時延越小證明網絡越通暢;

路由協議開銷——routing overhead（bit）=路由報文總比特數。

仿真場景設置：120個節點隨機分布在2 000 m×1 500 m的矩形區域內， 每個節點的無線傳輸半徑為300 m ， 信道容量為1 Mbps， 網絡中的每個節點都是數據業務源， 業務分組的長度為1 024 bit， 分組產生時間間隔服從均值為1/0.5 s泊松分布。選擇隨機行走(random walk)模型作為節點的移動模型， 單個直線運動的速率服從0~vmax的均勻分布。其中：vmax分別取0、1和2 m/s 三個值； 單個直線運動的時間服從參數為10 s的指數分布；單個直線運動的方向服從(0，2π)的均勻分布， 每個分組目的節點隨機選擇， 仿真時間為10 min。圖6~8分別對應vmax為0、1和2 m/s的情況。

從圖6~8可以看出，CAODV與AODV相比，能保持接近于100%的數據成功傳遞率。但在RREQ報文平均副本數和網絡的總體開銷比特上明顯優于AODV。由于CAODV對路由廣播報文進行了抑制，降低了廣播報文的沖突，在靜止狀態情況下路由的平均建立時間明顯優于AODV。但隨著節點運動速率的上升，性能改善效果有所下降。總體來講，在大規模和高節點密度的WSN網絡中，CAODV的性能表現是值得肯定的。

(a) 數據包成功發送率(b) RREQ報文平均副本數

(c) 平均路由建立時間(d) 路由開銷比特數

圖6仿真性能曲線（vmax=0）

(a) 數據包成功發送率(b) RREQ報文平均副本數

(c) 平均路由建立時間(d) 路由開銷比特數

圖7仿真性能曲線（vmax=1 m/s）

(a) 數據包成功發送率(b) RREQ報文平均副本數

(c) 平均路由建立時間(d) 路由開銷比特數圖8仿真性能曲線（vmax=2 m/s）4結束語

CAODV路由協議采用了跨層設計的方法，通過距離估計模塊、延時發送模塊和高效廣播模塊，使MANET中的AODV協議能有效地應用于WSN網絡。計算機仿真證明CAODV在保證網絡數據成功傳送率不下降的情況下，能在降低網絡開銷、減少路由建立時間等方面取得良好的性能。CAODV中的廣播控制思想還可以用于傳感器網絡的管理中，能以較小的管理開銷實現網絡管理命令的執行。

參考文獻：

[1]PERKINS C E， ROYER E， DAS S.RFC 3561， Ad hoc ondemand distance vector (AODV) routing[S]. 2003.

[2]JAMAL N， KARAKI A， AHMED E. Routing techniques in wireless sensor networks: a survey[J].IEEE Wireless Communications， 2004，11(6):6－28.

[3]HAAS Z J， HALPERN J Y， LI L. Gossipbased Ad hoc routing[C]//Proc of the IEEE INFOCOM. New York: IEEE Communications Society， 2002:1707－1716.

[4]HEINZELMAN W， KULIK J， BALAKRISHNAN H. Adaptive protocols for information dissemination in wireless sensor networks[C]//Proc of the 5th ACM/IEEE MOBICOM. Seattle:[s.n.]，1999:174－185.

[5]KULIK J， HEINZELMAN W R， BALAKRISHNAN H. Negotiationbased protocols for disseminating information in wireless sensor networks[J]. Wireless Networks， 2002， 8(8):169－185.

[6]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Hawaii Int’l Conf Sys Sci. 2000.

[7]LINDSEY S， RAGHAVENDRA C S. PEGASIS: powerefficient gathe￣ring in sensor information systems[C]//Proc of IEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society， 2002:1125－1130.

[8]MANJESHWAR A， AGRAWAL D P. TEEN: a protocol for enhanced efficiency in wireless sensor networks[C]//Int’l Proc of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society， 2001:2009－2015.

[9]YE F， LUO H， CHENG J， et al. A twotier data dissemination model for largescale wireless sensor networks[C]//Proc ofthe 8th Annual Int’l Conf on Mobile Computing and Networking. Atlanta: ACM Press，2002:148－159.

[10]XU Y， HEIDEMANN J， ESTRIN D. Geography informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual ACM/IEEE Int’l Conf Mobile Comp and Net. 2001:70－84.

[11]YU Y， ESTRIN D， GOVINDAN R. Geographical and energyaware routing: a recursive data dissemination protocol for wireless sensor networks， UCLACSD TR－010023[R].[S.l.]: UCLA Comp Sci Dept，2001.

[12]STARK W ，WANG H， WORTHEN A ， et al.Lowenergy wireless communication network design[J].IEEE Wireless Communications， 2001， 9(4):60－72.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”