基于位置感知和代理的WSN多徑路由方案

湯 震，藺 莉

(黃淮學院 信息工程學院，河南 駐馬店 463000)

基于位置感知和代理的WSN多徑路由方案

湯 震，藺 莉

(黃淮學院 信息工程學院，河南 駐馬店 463000)

針對無線傳感器網絡(WSN)中多徑路由的可靠性和能量效率問題，提出了一種基于代理和位置感知的多徑路由發現方案(LABMR)。事件節點根據位置信息，動態尋找其到Sink節點之間的特殊中間節點，來構建多徑路由。利用移動代理來收集多徑路由的局部拓撲結構信息，Sink節點根據代理收集的路由參數來計算路徑權值，以此選擇最優不相交路徑。同時，對于信息的重要性差異，Sink節點選擇單條或多條路徑來傳輸數據，在保證傳輸可靠性的同時減少能耗。與現有的基于代理的多徑路由(ABMR)方法相比，LABMP在數據包投遞率、能量消耗、額外開銷和延遲方面具有更好的性能。

無線傳感器網絡；多徑路由；網絡代理；位置感知

無線傳感器網絡(Wireless Sensor Network，WSN)是由多個靜態傳感器組成，通過無線介質連接，執行物理世界的分布式感知、數據處理和決策[1]。在傳統的WSN中，傳感器節點周期性地收集數據，并通過使用多跳通信方式報告給Sink節點。使用傳統數據收集和處理方法可能會導致一些額外能量消耗、冗余的數據傳輸、增加延遲和帶寬開銷等現象。WSN的關鍵問題是網絡的生命周期和傳輸可靠性，這主要是依賴于傳感器節點的能量和通信機制[2]。

由于WSN中節點資源異構性、通信鏈路不對稱等因素，導致數據鏈路容易發生斷裂。為了保證可靠的數據傳輸，多徑路由機制被廣泛應用，其利用數據鏈路冗余方式傳輸數據，有效地提高了通信可靠性[3]。

1 相關工作

文獻[4]描述了一種基于代理的多徑路由(Agent Based Multipath Routing，ABMR)發現方案。ABMR考慮了傳感器節點的一些參數，如剩余能量、距離、信道可靠性來計算從源節點到Sink節點的多徑路由。從源節點觸發移動代理，在傳感參數的基礎上，在網絡中移動直到到達目的節點。每個節點上的移動代理都會移動到鄰居節點來收集信息，用來在鄰居節點中選擇出最好的節點。一旦從鄰居中選擇出了最好節點，則這個最好鄰居節點觸發自身的移動代理到它的鄰居，重復執行上述任務，選擇最佳節點直到到達Sink節點。Sink節點根據代理帶來的路徑信息來計算多徑路由。然而其存在著一些缺陷，要計算多徑路由，源節點需要同時發出多個代理，ABMR中的代理從源節點到目的節點的過程中，要收集很多節點的信息，幾乎遍歷了整個網絡。這就導致大量的額外能量消耗。

對于一些現有的多徑路由技術存在的缺點，如在路徑發現和路徑建立過程中缺乏智能，中繼節點選擇機制的靈活性較小，計算多徑路由的能量消耗較大，對關鍵信息的傳輸缺乏魯棒性機制等。本文提出一種基于位置感知的代理的智能多徑路由發現機制(Location aware and Agent Based Multipath Routing，LABMR)。利用傳感器位置信息尋找特殊中間節點來構建多徑路由，并觸發代理在路徑上移動，來收集多徑路由的局部拓撲結構信息，Sink節點根據這些信息，計算出最優不相交路徑。并根據事件重要性，選擇一條或多條路徑傳輸數據。

提出的LABMP和ABMR的根本區別如下：1)LABMP只使用局部拓撲信息來尋找從源到Sink節點的多條路徑；2)建立了完善的代理機構，Sink節點能夠根據代理收集的信息尋找最優路徑，可靠傳輸關鍵信息；3)使用基于GPS(全球定位系統)的位置信息，能夠更準確地計算多條路徑。通過實驗，與ABMR方法相比，LABMP在數據包投遞率、能量消耗、額外開銷和延遲方面具有更好的性能。

傳感器節點位置信息的獲取是通過內置GPS模塊實現。為了盡可能減少成本，本文只在少量傳感器節點上使用GPS定位模塊，其他節點通過節點之間的通信來估計自己的位置。相比于GPS模塊的成本，位置信息對整體網絡性能更具價值。

2 提出的LABMR方案

2.1 相關概念

提出的LABMP方案中的主要名詞如下：

事件節點(Event node)，即在事件影響區域，用來檢測事件的傳感器節點。事件節點能夠觸發到Sink節點的路由發現過程。節點會向其他鄰居節點宣布自己為一個事件節點，防止其他節點去事件影響區域重復檢測事件[5]。

中點(Midpoint)，是連接事件節點和Sink節點直線(X軸)上的中間位置點。若不存在嚴格中點，可將離中間位置最近的節點為中點。

特殊中間節點(Special intermediate nodes)，在事件和Sink節點之間，近似位于中點垂直上方和下方的節點。

上升角度(Rising Angle)，是指事件節點和X軸上方的特殊中間節點之間的連線與X軸的角度。

下降角度(Falling angle)，是指事件節點和X軸下方的特殊中間節點之間的連線與X軸的角度。

跳數(Hop count)，是指事件節點到Sink節點路徑的中繼節點總數。

2.2 網絡環境

本文中的網絡環境如圖1所示，由多個具有數據感知能力的微小傳感器節點和Sink節點組成。當傳感器節點檢測到一個事件時，它們會將數據通過無線多跳通信方式發送到Sink節點[6]。本文假設網絡中的所有節點(傳感器節點和Sink節點)都是靜態的，且在初始部署階段，所有的傳感器節點具有相同的能量。在本文所提出的LABMP中，假設只有少量傳感器節點具有GPS功能，其余節點根據具有GPS節點的位置，使用定位算法來估算自己的位置，以此來降低系統的成本。每個傳感器節點都具有一個代理機構。

圖1 WSN網絡結構

2.3 多徑路由發現

2.3.1 路徑參數

本節描述了本文方案中所用到的路徑參數，包括鏈接和路徑的效率、能量比率和跳距離因子。

設C是離散信道的容量，B是信道的比特率，Ei是在鏈路i上傳輸1 bit數據消耗的總能量，SNR是信噪比。信道i的容量計算公式為[7]

Ci=Blb(1+SNR)

(1)

設定Et為1 bit數據每傳輸d距離所消耗的能量，則Ei可用下式計算

Ei=Et×d

(2)

鏈接效率(Leffi)計算公式為

(3)

路徑效率(Peff)為整條路徑上的n個鏈接效率的最低值，表達式如

Peff=min{Leff1,Leff2,…,Leffn}

(4)

路徑能量比率(Eeff)為每條從事件節點到Sink節點路徑中節點最小剩余能量和最大剩余能量之比。設定ER(1)到ER(n)為路徑上n個中間節點的剩余能量。路徑上n個節點的最小(ERmin)和最大(ERmax)剩余能量表達式如式(5)，式(6)所示，Eeff表達式如式(7)所示。

ERmin=min{ER(1),ER(2),…,ER(n)}

(5)

ERmax=max{ER(1),ER(2),…,ER(n)}

(6)

(7)

一條路徑的跳距離因子(Hdf)表達式如式(8)所示，其中，事件節點到Sink節點路徑的歐式距離為Pd，路徑上跳數的總和為Phc

(8)

2.3.2 局部拓撲結構發現

圖2顯示了從事件節點到Sink節點的多徑局部拓撲結構發現過程。S1和S7分別是事件節點和Sink節點。以S1和S7的直線連接為X軸，S2，S4和S6節點近似位于X軸上。根據GPS位置信息，設定以(xe,ye)和(xs,ys)分別作為事件節點和Sink節點的位置坐標，根據式(9)、式(10)找出S1到S7直線上的中間位置點(中點)為節點S4，其坐標為(xmid,ymid)。

(9)

(10)

S11,S22：特殊中間節點 S7：Sink節點 ?r1～?r11:上升角度 S1：事件節點 S2～S6：傳感器節點 ?f1～?f11：下降角度圖2 WSN中局部多徑發現模型

(11)

y″mid=ymid-n×R

(12)

式中：n和R分別是中點的節點度和傳輸范圍。

每個節點處的上升和下降的角度計算公式如

(13)

式中：θr1是上升角度，同理可得下降角度θf1表達式為

(14)

在下面的描述中，代理會在這3條路徑上移動只到Sink節點，以此來收集路徑節點和鄰居的參數信息，這些信息將被Sink節點用來構建局部拓撲結構和發現多路徑。

2.4 代理機構

本文方案中，為路徑發現和路徑計算設置了一組靜態和動態代理，并為普通傳感器節點和Sink節點的構建代理機構。本節介紹了提出的代理機構和相應的代理。

2.4.1 普通節點代理機構

本文中普通節點代理機構是由節點管理者代理(NMA)、路徑發現代理(PDA)和多徑路由知識庫(MKRB)組成，其中NMA是靜態代理，PDA是移動代理。節點代理機構和它們之間的相互作用如圖3所示。

圖3 普通節點代理機構

節點管理者代理(NMA)：是一個靜態代理，用來檢測可有信息，如信號強度、傳輸范圍、剩余能量，并計算鏈路效率，最小和最大剩余能量比和跳距離等參數。當檢測到事件時，NMA開始根據位置信息，計算中點和特殊中間節點(SINs)。然后，NMA創建PDA和MKRB，使用MKRB更新路徑信息。運行過程中，NMA會根據節點剩余能量，使節點進入睡眠或活動模式。NMA會和鄰居節點的NMA進行交流，以此得到鄰居節點信息，如節點ID、位置，并更新MKRB。

路徑發現代理(PDA)：一旦檢測到事件，事件節點的NMA會創建一個事件節點的PDA(移動代理)，并復制成3個。3個PDA在3條路徑上移動，第1個PDA幾乎在X軸上移動，直到到達Sink節點；第2個PDA先以上升角度移動，到達SIN節點后，再以下降角度遷移，直到到達Sink節點。第3個PDA先以下降角度移動，到達SIN節點后以上升角度遷移。最后，PADs將收集的局部拓撲信息傳遞給Sink節點。

多徑路由知識庫(MKRB)：是基于網絡路徑相關信息建立的知識庫，通過代理可以讀取和更新。它包括節點ID、活動/睡眠模式、剩余能量、鄰居節點之間的距離、Sink節點ID、SINs的ID、Sink節點和SINs的位置信息、事件感知時間、信號強度、可用帶寬、自身和Sink節點之間的距離、上升和下降的角度等信息。它也保存著鄰居節點的信息，如節點的ID和位置信息。

2.4.2 Sink節點代理機構

Sink節點代理機構由Sink管理者代理(SMA)、路徑設置代理(PSA)和Sink知識庫(SKB)組成。Sink節點代理機構的組成以及之間的相互作用如圖4所示。

圖4 Sink節點代理機構

Sink知識庫(SKB)：是用于Sink節點計算路徑的信息知識庫，能夠被SMA、PDA和PSA讀取和更新。它存儲了與網絡有關的信息，包括路徑長度、跳總數、剩余能量、每條路徑剩余能量的最小和最大值、可用帶寬、信道容量、到事件節點的可用路徑數量、路徑權重因子等。

Sink管理者代理(SMA)：是存在于Sink節點中的一個靜態代理，檢測網絡相關信息。基于收集的信息，如剩余能量、可用帶寬、每條路徑的跳總數和路徑距離，SMA能夠計算出從Sink節點到事件節點的不相交路徑。同時計算每條路徑的路徑權重因子，根據事件的重要性，決定選擇一條或多條路徑進行傳輸。根據路徑權重因子決定路徑的優先級，如果事件是重要的，則選擇出多條路徑，并使PSAs在這些路徑上移動到事件節點。為了減少開銷，本文考慮最多選擇3條最優不相交路徑。如果事件是不重要的，則只選擇一條最優路徑給PSA移動，當事件節點收到PSA時，開始傳輸信息數據。

路徑設置代理(PSA)：是通過SMA構建的移動代理，其從Sink節點的SKB獲得路徑信息，從Sink節點移動到事件節點來檢查路徑上的節點。在到達事件節點后，它根據路徑信息更新事件節點的MKRB。

2.4.3 示例場景

本文方案的一個應用示例場景如圖5所示。圖中數字表示的本文方法步驟的序號，執行步驟如下：

1)傳感器節點S1檢測到一個事件時，事件節點的NMA啟動到Sink節點的路徑發現過程。

2)NMA產生PDA，PDA產生3個PDA復制品，并計算得出特殊中間節點(S11和S12)和移動的角度；3個PDA按3條路徑移動，直到它們分別到達Sink節點、S11和S12，在遷移過程中，它們收集路徑信息。

3)PDA的兩個復制品在S11和S12處分別改變移動的角度，只到Sink節點并傳遞路徑信息給Sink節點。

4)Sink節點的SMA計算到事件節點的不相交多路徑，根據每條不相交路徑的權重因子來設定優先級。

5)根據事件的重要性，SMA觸發單條或多條最佳路徑上的PSA，并移動到事件節點。

圖5 LABMP網絡示例場景

3 實驗及分析

為了評估本文算法的有效性，利用MATLAB仿真各種網絡環境，將本文方案與現有的基于代理多徑路由的ABMR方案進行比較。

3.1 仿真模型

網絡模型：本文考慮一個l×b(平方米)區域的WSN網絡，由N個隨機布置的靜態節點組成。設定以一跳距離相互連接的節點的信道帶寬為BWsingle-hop，本文假設所有信道都是可用的。仿真網絡參數如表1所示。

表1 仿真參數

傳播模式：本文使用一個傳播常數為β的自由空間傳播模型，WSN節點的傳輸范圍為R。假設在任何給定的時間上，節點傳輸一個數據包所需的能量為Eu(焦耳)，節點的R正比于Eu，R=CEu，其中比例常數C取決于傳輸介質常數β[9]。

3.2 性能參數

本文通過以下幾種性能參數來比較本文方法和ABMR算法。

數據包投遞率(PDR)：指接收和發送的數據包的比例。

能耗(EC)：指在網絡中路徑發現、路徑設置和事件節點向Sink節點發送數據包所消耗的總能量，以毫焦耳(mJ)表示。

延遲(Delay)：從事件節點傳輸數據到Sink節點的總時間，以毫秒(ms)表示。

額外開銷(Overhead)：指獲得可用的通信路徑所需的能量開銷。

3.3 實驗結果

3.3.1 數據包投遞率和能量消耗

圖6顯示了在給定數量節點和傳輸范圍下，兩種算法的數據包投遞率(PDR)。在ABMR和LABMP中，PDR都隨著節點數量的增加而減小，隨著通信范圍的增加而增加。然而，相比于ABMR，LABMP具有更好的PDR。當節點數量增加時，節點信息數據的量也隨之增加，這就導致需要更多的帶寬，因此，可用帶寬可能不足以來成功傳輸數據，使得PDR下降。LABMP方案提供較好的可用帶寬，這是因為它在可用路徑計算中考慮了鏈接效率，均衡了信道帶寬。LABMP在較高傳輸范圍下的PDR表現更好，這是因為減少了孤立節點的數量。

圖6 不同節點數量和傳輸范圍下的數據包投遞率

圖7描述了在給定數量節點和傳輸范圍下，網絡運行單位時間的總能量消耗。隨著節點數量和傳輸范圍的增加，ABMR和LABMP的能量消耗都會增加，然而LABMP具有較好的性能。能量消耗主要由收集局部拓撲結構信息、路徑計算、路徑信息發送和接收形成。提出的LABMP方案具有較少的能量消耗，這是因為它在計算路徑時，考慮了局部拓撲、跳距離因素和能量信息。而ABMR只使用基本拓撲信息來計算路徑。

圖7 不同節點數量和傳輸范圍下的能量消耗

3.3.2 延遲和額外開銷

圖8描述了在給定節點數量和通信范圍下的延遲。由于節點數量和通信范圍的增加，收集和計算多條不相交路徑的時間需求也增加。LABMP比ABMR需要較少的時間，因為LABMP只利用局部拓撲結構信息來尋找路徑，而ABMR則利用全局拓撲結構信息，需要更多時間來收集信息。

圖8 不同節點數量和傳輸范圍下延遲

圖9和圖10顯示了在給定節點數量和通信范圍下，傳輸關鍵和非關鍵數據時的額外開銷。開銷隨著通信范圍和節點數量的增加而增加。LABMP比ABMR具有較少的開銷，因為LABMP對于關鍵信息通信，選擇多徑路由來實現可靠傳輸，而對于非關鍵信息通信，只選擇具有最高權值因子的單一路徑來傳輸信息。由于LABMP利用代理在設定的方向上移動來獲得局部拓撲結構信息，尋找多徑路由所需的通信量比ABMR少。

圖9 不同節點數量下的開銷(關鍵信息)

圖10 不同節點數量下的開銷(非關鍵信息)

4 小結

本文提出了一種基于代理和位置感知，由事件驅動的多徑路由發現方案。事件節點根據位置信息，動態尋找事件節點和Sink節點之間的特殊中間節點，來構建多徑路由。并利用移動代理來收集多徑路由的的局部拓撲結構信息，并發送給Sink節點，Sink節點根據鏈接效率、能量比率和跳距離因子來計算路徑權值，以此選擇最優不相交路徑。對于關鍵信息，Sink節點通過多條較優路徑發送信息給事件節點，保證傳輸可靠性；對于非關鍵信息，Sink節點只利用具有最大權值的單路徑發送信息。由于LABMP只利用局部拓撲信息構建路由，不需要了解全局節點的信息，從而節省了帶寬和能量。與現有的ABMR方法相比，本文提出的LABMP在數據包投遞率、能量消耗、開銷和延遲方面具有更好的性能。

[1] 楊銀堂，高翔，柴常春，等. 一種 WSN 中的能耗優化動態路由算法[J].西安電子科技大學學報，2010，37(5)：777-782.

[2] 劉新華，李方敏，曠海蘭，等. 基于能量異構的無線傳感器網絡分布式成簇算法[J].小型微型計算機系統，2010，34(1)：26-31.

[3] 盧莉萍，黃飛，張宏，等. 基于網絡編碼的傳感器網絡多徑路由模型能量分析[J].南京理工大學學報：自然科學版，2010，34(4)：124-130.

[4] RAMADAN R A. Agent based multipath routing in wireless sensor networks[J].IEEE Wireless Communications，2009，11(6)：63-69.

[5] 馮江，茅曉榮，吳春春.一種能量均衡有效的WSN分簇路由算法[J].計算機工程，2012，38(23)：88-91.

[6] LUO R C，CHEN O. Mobile sensor node deployment and asynchronous power management for wireless sensor networks[J]. IEEE Trans. Industrial Electronics，2012，59(5)：2377-2385.

[7] KATIYAR V，CHAND N，SONI S. A survey on clustering algorithms for heterogeneous wireless sensor networks[J].International Journal of Advanced Networking & Applications，2011，2(4)：122-129.

[8] 王建生，曹葉文. 基于動態組播代理的移動組播協議[J].計算機工程，2010，36(1)：87-90.

[9] MIAO G W，HIMAYAT N，LI G Y. Energy efficient link adaptation in frequency-selective channels[J].IEEE Trans. Commun，2010，58(2)：146-152.

[10] DI C G，DORIGO M. AntNet: distributed stigmergetic control for communications networks[J]. Journal of Artificial Intelligence Research，2011，19(3)：317-365.

湯 震(1983— )，碩士，講師，主要從事軟件工程開發、數據挖掘等研究；

藺 莉(1982— )女，講師，碩士，主要從事軟件工程開發、數據挖掘等研究。

責任編輯：許 盈

Location Aware and Agent Based Multipath Routing Scheme in WSN

TANG Zhen, LIN Li

(DepartmentofInformationEngineering,HuanghuaiUniversity,HenaZhumadian463000,China)

To solve the problem of the reliability and energy efficiency of multipath routing in WSN, a multipath routing scheme based on location aware and Agent (LABMR) is proposed. The event node searches for special intermediate nodes between Sink node and event node according to location information, in order to build multipath routing. LABMR uses the mobile agents to collect the partial topology information of multipath routing, which will be used by Sink node to compute the path weight, so as to find out the optimal disjoint paths. Meanwhile, Sink node selects a single path or multiple paths to transmit information according to its importance, to ensure transmission reliability as well as reduce energy consumption. Compared with ABMR scheme, LABMP has better performance in packet delivery ratio, energy consumption, overhead and latency.

wireless sensor network; multipath routing; network agent; location aware

【本文獻信息】湯震，藺莉.基于位置感知和代理的WSN多徑路由方案[J].電視技術,2015，39(11).

河南省教育廳科學技術研究重點項目(14B520036)

TP39

A

10.16280/j.videoe.2015.11.031

2014-12-20