韓江洪 ，江 月 ，馬學(xué)森 ，官駿鳴 ,3

（1.合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院 合肥 230009；2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心 合肥 230009；3.黃山學(xué)院信息工程學(xué)院 黃山 245021）

1 引言

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

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

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

2 IAODV協(xié)議的設(shè)計

IAODV協(xié)議的設(shè)計目標(biāo)是在保留AODV協(xié)議的強(qiáng)壯性、高效性和良好的自組織性等優(yōu)點(diǎn)的前提下，對其基于洪泛的路由查找機(jī)制進(jìn)行改進(jìn)，使其成為適合WSN的低開銷、低時延的路由協(xié)議。

WSN中的節(jié)點(diǎn)在部署完成之后大部分不會再移動，雖然部分節(jié)點(diǎn)因調(diào)度機(jī)制或失效等原因而出現(xiàn)網(wǎng)絡(luò)拓?fù)涓淖兊那闆r，但這些變化具有明顯的周期性和間歇性，所以WSN的拓?fù)淇梢哉J(rèn)為是準(zhǔn)靜態(tài)的。此外，WSN的工作模式通常是網(wǎng)絡(luò)中的所有節(jié)點(diǎn)將數(shù)據(jù)匯聚到Sink節(jié)點(diǎn)，即多對一的通信，節(jié)點(diǎn)之間幾乎不會發(fā)生消息交換[1]。

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

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

圖1 以基準(zhǔn)傳輸路徑的最大傳輸范圍為尋找域

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

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

3 IAODV協(xié)議的實(shí)現(xiàn)

根據(jù)上述設(shè)計方案，IAODV協(xié)議在AODV協(xié)議的基礎(chǔ)上進(jìn)行了以下改進(jìn)。

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

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

（2）對RREQ分組和RREP分組進(jìn)行擴(kuò)展，并在路由查找過程中增加與之相關(guān)的處理

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

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

4 仿真及分析

4.1 仿真場景設(shè)置

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

4.2 性能評價參數(shù)

通過分組投遞率、平均端到端時延和標(biāo)準(zhǔn)路由開銷3個參數(shù)來比較IAODV和AODV協(xié)議的性能。分組投遞率定義為交付到目的節(jié)點(diǎn)的數(shù)據(jù)分組數(shù)量與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組數(shù)量之比；平均端到端時延定義為一個數(shù)據(jù)分組成功到達(dá)目的節(jié)點(diǎn)所需的時間平均值；標(biāo)準(zhǔn)路由開銷定義為每接收到一個數(shù)據(jù)分組需要傳遞的路由分組的數(shù)目[11]。

4.3 仿真結(jié)果及分析

（1）分組投遞率

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

圖2 IAODV和AODV協(xié)議在不同數(shù)據(jù)采集上傳周期下的分組投遞率

（2）平均端到端時延

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

圖3 IAODV和AODV協(xié)議在不同數(shù)據(jù)采集上傳周期下的平均端到端時延

（3）標(biāo)準(zhǔn)路由開銷

圖4顯示了IAODV協(xié)議和AODV協(xié)議在不同情況下的標(biāo)準(zhǔn)路由開銷，可以看出，不論網(wǎng)絡(luò)負(fù)載大小，IAODV協(xié)議的標(biāo)準(zhǔn)路由開銷都明顯小于AODV協(xié)議。IAODV協(xié)議通過限制RREQ分組的廣播范圍大大減少了路由分組數(shù)量，減小了路由開銷。

圖4 IAODV和AODV協(xié)議在不同數(shù)據(jù)采集上傳周期下的標(biāo)準(zhǔn)路由開銷

5 結(jié)束語

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

1 李曉維.無線傳感器網(wǎng)絡(luò)技術(shù).北京：北京理工大學(xué)出版社，2007

2 陳林星，曾曦，曹毅.移動Ad Hoc網(wǎng)絡(luò)：自組織分組無線網(wǎng)絡(luò)技術(shù).北京：電子工業(yè)出版社，2006

3 王斌.無線傳感器網(wǎng)絡(luò)AODV路由協(xié)議的實(shí)現(xiàn).計算機(jī)與現(xiàn)代化，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的漸進(jìn)式分簇路由策略.通信學(xué)報，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 喻勇，劉凱歌，胡軍.可自擴(kuò)展的DSR路由協(xié)議的性能分析與仿真.計算機(jī)工程與設(shè)計，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與網(wǎng)絡(luò)模擬.北京：人民郵電出版社,2003

11 官駿鳴，陸陽，盛鋒等.基于節(jié)點(diǎn)接入能力的Ad Hoc網(wǎng)絡(luò)按需路由協(xié)議.通信學(xué)報,2007,28（10）:32～37