基于多路徑機制的無線傳感器網絡動態路由算法

齊小剛，王東方

(西安電子科技大學數學科學系 西安 710071; 西安電子科技大學綜合業務網國家重點實驗室 西安 710071)

基于多路徑機制的無線傳感器網絡動態路由算法

齊小剛，王東方

(西安電子科技大學數學科學系 西安 710071; 西安電子科技大學綜合業務網國家重點實驗室 西安 710071)

傳統網絡的路由機制往往選擇源節點到匯聚節點之間跳數最小的路徑傳輸數據，但是在無線傳感器網絡中，如果頻繁使用同一條路徑傳輸，就會造成該路徑上節點應能量消耗過快而過早失效。本文提出了一種基于多路徑機制的動態路由算法，主要步驟為找到源節點和匯聚節點的多條路徑，選擇一條節點最小能量最大的路徑進行數據傳遞。與單路徑的路由算法相比，多路徑算法在節點生存期和數據傳輸的性能方面有了顯著的提高。

多路徑; 網絡生存期; 路由; 無線傳感器網絡

無線傳感器網絡是由大量具有特定功能的傳感器節點通過自組織的無線通信方式，相互傳遞信息，協同地完成特定功能的智能專用網絡[1]。它具有體積小、價格低等良好性質，在工業、農業、交通、軍事、安全、醫療、空間探測，以及家庭和辦公環境等眾多領域都有著廣泛的應用[2-5]。與傳統Ad hoc網絡相比，無線傳感器網絡的每個傳感器節點電源能量有限、通信能力有限以及計算和存儲能量有限，是無線傳感器網絡最大的缺點，也是制約路由協議的主要因素[6-7]。因此，無線傳感器網絡路由協議設計上以節約能源為主要目標，要求路由算法實現簡單、占用資源少，以提高網絡的生存周期。

目前，傳統網絡的路由機制往往選擇源節點到匯聚節點之間跳數最小的路徑傳輸數據，但是在無線傳感器網絡中，如果頻繁使用同一條路徑傳輸，就會造成該路徑上節點能量消耗過快而過早失效，從而使整個網絡被分割成互不相連的孤立部分，縮短了整個網路的生存期[2]。因此，多路徑算法的提出成為一種趨勢。文獻[3]提出了一種能量多路徑路由算法。該算法在源節點和匯聚節點之間建立多條路徑，根據路徑上節點的通信能量消耗以及節點的剩余能量情況，為每條路徑賦予一定的選擇概率，使得數據傳輸均衡消耗整個網絡的能量，延長整個網絡的生存期。然而該算法的概率計算過于復雜，使得計算復雜度過高。

1 基于多路徑機制的動態路由算法

1.1 算法基礎

由于節點的移動和拓撲結構的不斷變化，很難維護一個持續穩定、有效的端到端的路由。多路徑的路由[8]最近引起了極大的關注。在傳統的Ad hoc網絡中，多路徑路由相對于單路徑路由能獲得更好的性能。在Internet傳輸時，多路徑是有效減少數據包丟失的方式。為此，在無線傳感器網絡中，每次選擇多條路徑進行數據傳輸，使節點不會在較短時間內死亡，從而數據傳輸可以均衡地消耗整個網絡的能量，不會因為某一節點的死亡而使整個網絡不連通，使網絡有較好的吞吐性和整體性，最大限度地延長網絡的使用壽命。

1.2 算法假設

在傳感器網絡的實際應用中，各節點靠電池供電，大量的節點都保持靜止狀態或很少移動，只有當少量節點“失效”時，網絡拓撲才會發生變化。因此，本文的算法提出以下假設：(1) 每個節點都是靜止的，匯聚節點固定在傳感器網絡的中心，接受其余各點傳輸的數據包；(2) 傳感器網絡的各個節點的初始能量是相同的，匯聚節點的能量無限大；(3) 每一輪通信結束后，計算當前各個節點的剩余能量；(4) 所有的節點有相同的計算能力支持信號處理和計算路由，并且地位平等。

1.3 相關符號說明

num_point：網絡中的節點數目；xi：節點的橫坐標；yi：節點的縱坐標；R：連通半徑；wij：權值矩陣；dead_point：死亡節點終止數。

1.4 算法描述及流程圖

為了增加多路徑路由的健壯性，本文將構造最大不相連的多條路徑，即盡量在每條路徑中不包括相同的節點，以此來阻止在某些共用的節點上的擁塞以及能量的大量消耗，從而做到更加有效地利用整個網絡資源。另外的一個好處是當某條路徑崩潰時，其他的路徑將不會受到影響。

在節點和路徑的壽命有一定限制的條件下，本文提出了最大不相交的多路徑的路由發現過程，描述如下：

(1) 建立網絡。由于無線傳感器網絡節點的隨機性，因此建立網絡時，在某一個區域內隨機分布傳感器節點，得到每一個節點i的坐標(xi,yi)。其中匯聚節點的坐標固定，為網絡區域中心。

(2) 確定各點的連通性。確定適當的半徑R，距離在R范圍內的即確定為兩點連通，即：

考慮到節點的動態性，wij的取值是在節點之間距離的基礎上進行了一個隨機波動，其中rand(0,r)為波動范圍。

(3) 尋找兩點之間的多條不相交路徑。根據Dijkstra最短路徑算法，找到兩點之間的第一條最短路徑，同時將路徑上的所有點做標記，使得下一條路徑不與該路徑相交，然后再用Dijkstra最短路徑算法找到第二條路徑，依次按照以上步驟找到這兩點之間的3條路徑；如果在網絡不連通的情況下找不到3條路徑，這種情況只要求找到最多3條路徑。

(4) 算法結束條件。若存在兩點之間都找不到路徑，則網絡不連通，算法終止；當循環dead_point時，程序也終止。

(5) 數據傳輸階段。在源節點以及源節點到匯聚節點之間的多條路徑中隨機選一條進行數據傳輸。

程序流程圖如圖1所示。

圖1 算法運行流程圖

2 算法仿真與分析

本文采用節點隨機生成的網絡進行計算機仿真。在兩個網絡規模下比較了多路徑與單路徑算法的無線傳感器網絡生命周期、節點生存期以及網絡節點的死亡頻率。

(1) 在50 m×50 m的網絡范圍內，隨機地放置50個傳感器節點，并設定傳感節點的通信半徑為20 m，節點能量為15 J；匯聚節點的坐標為(25, 25)。

(2) 在100 m×100 m的網絡范圍內，隨機放置100個傳感器節點，并設定傳感器節點的通信半徑為30 m，節點能量為15 J；匯聚節點的坐標為(50, 50)。

仿真結果如表1所示。

表1 節點死亡時網絡經歷通信輪數

從表1中可以看出，多路徑算法能有效地提高網絡的生命周期。在50 m×50 m的區域中，基于多路徑算法的網絡的周期比單路徑算法下網絡的壽命提高了16%；而在100 m×100 m的區域中，提高了407%。

圖2 分布區域不同條件下20個節點的死亡頻率對比

圖2為單路徑與多路徑算法的網絡節點死亡時間的對比圖，其中橫軸代表死亡頻率，即節點死亡之前的通信輪數，縱軸代表網絡中的剩余節點數。根據圖2可以得出以下結論：

(1) 分布區域為50 m×50 m時多路徑算法的效果沒有區域為100 m×100 m的效果顯著；

(2) 在網絡區域增大為100 m×100 m時，多路徑算法節點的生存期比單路徑算法有了較大的延長；更顯著的是前幾個死亡節點的生存期都有了較大的延后。

因此，本文提出的基于多路徑選擇的無線傳感器網絡動態路由選擇算法具有較優越的性能，特別是網絡節點數不變而網絡分布區域增大時更具顯著優勢。

3 結 束 語

無線傳感器網絡的動態路由算法是無線傳感器網絡研究中的熱點問題[9]。本文給出了一種基于多路徑的無線傳感器網絡動態路由算法，通過尋找源節點和匯聚節點的多條路徑均衡地使用整個網絡節點的能量，從而有效地減緩了節點的死亡頻率，提高了網絡的生命周期，提供了較好的網絡性能。但在實際應用中無線傳感器網絡節點的移動和拓撲結構不斷變化，很難維持一個穩定的、端到端的路由技術，還需要在動態條件下對無線傳感器網絡路由問題進行進一步研究。

[1] 任豐原, 黃海寧, 林 闖. 無線傳感器網絡[J]. 軟件學報,2003, 14(2): 1148-1157.

REN Feng-yuan, Huang Hai-ning, LING Chuang. Wireless sensor networks[J]. Journal of Software, 2003, 14(7):1282-1291.

[2] 崔 莉, 鞠海玲, 苗 勇, 等. 無線傳感器網絡研究進展[J]. 計算機研究與發展, 2005, 42(1):163-174.

CUN Li, JU Hai-ling, MIAO Yong, et al. Overview of wireless sensor networks[J]. Computer Research and Development, 2005, 42(1): 163-174.

[3] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 392-422.

[4] ELSON J, ESTRIN D. Sensor networks: a bridge to the physical world[M]. Norwell: Kluwer Academic Publishers,2004.

[5] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks: a survey[J]. IEEE Wireless Communications, 2004, 11(6): 6-28.

[6] JOONGSEOK P, SARTAJ S. An online heuristic for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Computers, 2006, 55(8): 1048-1056.

[7] SHAH R C, RABAEY J M. Energy aware routing for low energy ad hoc sensor networks[C]//Proc IEEE Wireless Communication and Networking Conference (WCNC’02).[S.l.]: IEEE, 2002.

[8] 安輝耀, 盧錫城, 彭 偉, 等. MANET中基于動態拓撲的多路徑自適應流量分配算法[J]. 通信學報, 2006, 27(7):20-26.

AN Hui-yao, LU Xi-cheng, PENG Wei, et al. Adaptive traffic distributing bases on dynamic topology for multipath routing in MANET[J]. Journal on Communications, 2006,27(7): 20-26.

[9] PAOLO S. Topology control in wireless Ad hoc and sensor networks[M]. West Sussex, England: John Wiley & Sons Ltd, 2005.

An Algorithm for Dynamic Routing Based on
Multi-Paths in Wireless Sensor Networks

QI Xiao-gang and WANG Dong-fang

(Department of Applied Mathematics, Xidian University Xi’an 710071;State Key Laboratory of Integrated Service Networks, Xidian University Xi’an 710071)

According to the traditional network routing mechanisms, the path with the minimal hops is often chosen to transmit data from source node to destination node. However, frequent communication requests along one path in wireless sensor network result a fact that the nodes on the path prematurely fail with its’ energy exhaustion. In this paper, a routing algorithm based on the multi-path mechanism is proposed, its main idea is to find a path among multi-paths from source node to sink node, This path has the maximized minimal remaining node energy. Compared to single-path routing algorithm, the proposed routing algorithm improves the networks’performance on the nodes’ life time and the data transmission.

multi-path; network survival period; routing; wireless sensor network(WSN)

TP918.91

A

10.3969/j.issn.1001-0548.2010.z1.019

2009 ? 11 ? 15

國家自然科學基金( 60703118、60674108)；陜西省自然科學基金(2007A01)；ISN國家重點實驗室專項基金

齊小剛(1973 ? )，男，副教授，主要從事圖論與組合最優化、網絡優化理論與方法以及路由與交換方面的研究.

編 輯 稅 紅