無線傳感器網絡中的節能路由算法研究

李 平，戴 勁

(長沙理工大學計算機與通信工程學院，湖南 長沙 410114)

1 引言

無線傳感器網絡WSN(Wireless Sensor Network)是由多個節點組成的面向任務的無線自組織網絡，它主要由感知單元、傳輸單元、存儲單元和電源組成，在完成感知對象的信息采集、存儲和簡單的計算后，通過傳輸網絡傳送給遠端的監控中心。無線傳感器網絡由一組微型傳感器通過Ad Hoc方式組成，網絡中的傳感器監控區域的感知對象的信息及數據可以協作地感知、采集和處理，并發送給使用一定形式終端設備的用戶。無線傳感器網絡屬于Ad Hoc網絡，“Ad Hoc”在拉丁語中的意思是“專用的、特定的”，因此Ad Hoc網絡通常也被稱為無固定設施的網絡或自組織網絡，它能夠快速、靈活和方便地自動組網。傳感器網絡具有集中式數據收集、多跳數據傳輸、多對一流量模式等特征[1,2]。

無線傳感器網絡中的節點多采用能量有限的電池供電，因此，降低節點能量消耗在整個網絡的設計中需要重點考慮[3]。一些路由算法(如泛洪路由協議、定向擴散路由、自適應路由算法、基于地理位置信息的路由[4,5])雖然降低了整個網絡的能耗，但網絡生存時間卻縮短了，這是因為在這些算法中某幾個中轉節點因承擔了過多的數據傳輸任務而過早耗盡自身的能量而失效。因此，本文在最小跳數的基礎上提出一種保護節點能量的路由算法。該算法通過建立最小跳數和對節點剩余能量的保護，使得數據包沿著能耗最優的路徑向Sink節點發送。在MATLAB環境下對該機制進行了仿真實驗，實驗結果表明，該算法能降低能耗，均衡和延長網絡生存時間。

2 相關工作

目前，國內外學者對選擇性轉發攻擊的研究取得了一定的成果。Jain等人[6]提出的能量多路徑路由EAMR(Energy-Aware Multi-path Routing)機制是在源節點到目的節點間建立的多條路徑，在多條路徑上傳輸數據的多個拷貝或把數據分成多個相等部分并發傳輸，使得數據傳輸均衡消耗整個網絡的能量，延長整個網絡生存期。文獻[7]提出了一種根據建立虛擬簇，實現延長了網絡生存期和多媒體數據的節能傳輸，但是并沒有減少多媒體數據傳輸量。文獻[8]對多媒體節點活躍期與休眠期劃分的方法是通過數據分組的具體內容來實現。文獻[9]提出了一種多媒體傳感器網絡分布式能量管理算法CDPM(Computer Distributed Power Management)利用鄰居信息通信代價，并通過逐幀比較減少了傳感開銷，但該算法無法保證能耗均衡。文獻[10]探討無線傳感器網絡中采用節點非均勻分布策略的能量空洞問題。

本文在上述基礎上，構建了一種節約能量的無線傳感器網絡，通過建立最小跳數和對節點剩余能量的保護，使得數據包沿著能耗最優的路徑向Sink節點發送，從而能降低能耗和延長網絡生存時間。

3 生存網絡模型

假設傳感器網絡中的節點隨機分布在一個正方形監測區域內，該網絡具有以下特性：

(1)無線傳感器網絡的環境以匯聚節點為中心，節點隨機而稠密地分布在一個區域內，每個節點在網絡中有唯一的標識號ID，并且其發射功率為固定值。為便于表示，做如下定義：

設Pj表示標識號ID為j的節點；P={Pj|Pj表示標識號ID為j的節點}，則P為有限集合，其元素個數為網絡節點數n；Ej為Pj的現存能量；根據節點能量消耗和通信模型，每個節點的初始能量是ε且大于0，Sink沒有能量限制，節點發送和接收k比特數據的能耗分別為：

Er(k，d)=kEelec+kEampd2

(1)

Er(k)=kEelec

(2)

其中，Eelec為收發數據時電路電子能耗；Eamp為信號放大器電路的能耗；d為發送節點與接收節點之間的距離。顯然,每個節點發送1 bit數據的能耗大于接收1bit數據的能耗。

(2) 設節點之間的通信半徑為R，如果物理距離|Pi-Pj|≤R,則稱Pi和Pj為鄰居節點，記Si={Pj|Pj∈P,且|Pi-Pj|≤R}。

(3) 所有傳感器節點部署后靜止不動, 所有節點都具有相同的性質(如初始能量值、通信半徑、能耗值)，地位是對稱平等的。

(4) 數據從源節點傳輸到Sink節點所用的時間稱為傳輸時延；所有數據包傳輸時延的平均值稱為平均時延，在上述假設下，同一數據包的傳輸時延僅僅與數據傳輸所經歷的節點數目有關。

根據上述定義和假設，源節點Q向Sink節點發送數據時，無線傳感器網絡可看做是一個有向圖。

設H={Hk|Hk表示所有源節點Q到Sink節點的路徑}，其元素個數為鏈路的總數r，Zk表示路徑Hk所包含的節點的數目。fij為Pi發送到Pj的數據流，因此節點Pi發送的數據流總和為：

(3)

從而可以得出節點的生存時間為：

(4)

4 最小跳數建立

協議中的節點都有唯一的標識號ID，初始化匯聚節點的跳數(hop設置為0)，其余節點的跳數設為極大值。Sink節點根據需要向網絡廣播數據查詢消息，當鄰居節點接收到數據包時，將數據包中的hop值加1作為新值與自身存儲的hop值相比較，若新的hop值小于原來存儲的hop值，則用新值替換原存儲值；將數據包中的hop值換為新值，并替換原來節點的標識號ID。在自己的鄰居列表中為Sink節點中添加一個信息，并根據查詢消息修改表項中的neighborre_energy(即鄰居節點的剩余能量)、neighborhops值(即鄰居節點的最小跳數)和neighborID(即鄰居節點的ID)。然后根據節點信息修改查詢消息的內容，將信息包中的hop值加1并將剩余能量和其自身ID寫入消息包，繼續廣播此查詢消息。若新的hop值大于原來存儲的hop值，則不作處理。

其它節點接收到數據包時做上述同樣的處理，這樣的過程一直持續下去，這樣每個節點均建立了到Sink節點的多條最小跳數路徑并記憶了各條路徑的最小節點能量。

最后數據沿著查詢消息的反向路徑向匯聚節點傳送，匯聚節點將每個節點的最小跳數和最小節點能量保存在本地節點信息中。

4.1 節點選擇階段

將符合條件的鄰居節點的ID和需要轉發的數據信息保存在本地中，若選擇的接收數據節點在鄰居節點中找不到合適的轉發節點，則放棄本次鄰居節點的選擇，返回上一個節點，重新從本地中查看并選擇另一個符合條件的鄰居節點進行數據轉發。

若有多個鄰居節點到Sink節點的跳數相同，就選擇剩余能量最多的鄰居節點作為中繼節點來轉發數據包。

4.2 保護節點能量

在數據轉發階段，某些節點因承擔較多的數據轉發任務，從而消耗過多的能量，根據式(3)和式(4)，若某個節點的剩余生存時間小于某個閾值時，它向其它節點發送esc消息，聲明該節點將不再作為轉發節點，鄰居節點收到該消息后，從本地信息中刪除該節點的信息。同時，選擇其鄰居節點中能量最多的節點承擔該節點相應的傳輸任務，承擔傳輸任務的節點向周圍的鄰居節點發送work消息。如此一來，經過該低能量節點的路徑將會被刪除，節點的負荷處理能力也將降低。當在節點周圍沒有感興趣的事件時，通信與計算模塊就屬于閑置模塊，把這些模塊調到低功率的狀態或者關掉，即休眠狀態。這種能量保護策略可以有效地降低節點的能量消耗，延長節點的生存時間，從而延長了網絡的生命周期。

5 仿真實驗

通過仿真實驗，本文對基于能量均衡的路由算法的性能進行了驗證，并將其與定向擴散協議在網絡生存期和傳輸時延等方面進行了對比分析。

仿真實驗條件設置：網絡中所有節點隨機分布在一個500 m×500 m的正方形監測區域內，平面中隨機分布500個傳感器節點，節點初始能量ε=200 J，Eelec=0.05 nJ/bit，Eamp=0.001 pJ/(bit·m2)，通信半徑R=15 m，數據包長度L=160 bit。

圖1是兩種方法下的網絡生存時間。定義僅當網絡節點數目低于設定閾值時(本文仿真定義的閾值為30%)，網絡失效。其中根據式(4)，當傳感器節點的生存時間小于某一閾值時，我們認為它是失效的。從圖1可以看出，由于靠近匯聚節點的區域出現能量空洞問題，導致系統的生命周期提早結束；而本文改進后，在路由選擇時充分考慮路徑中節點的剩余能量，遇到剩余能量較小的路徑可以有效地避開，使得網絡中的節點達到能耗均衡，只有當系統中剩余能量很少時，網絡的生命周期才結束。

Figure 1 Survival time of the network graph圖1 網絡生存時間圖

圖2是兩種協議的平均傳輸時延對比。節點傳輸半徑增大時，傳輸所需的跳數減少，數據包傳輸時間將減少，兩種算法的傳輸時延都呈遞減的趨勢。在定向擴散算法中，最優路徑的建立是通過泛洪方式，需要的時間長，從而增加了網絡時延。而本算法中，通過建立最小跳數來建立路徑，從而能較快地找到最優路徑，減少了網絡時延。

Figure 2 Transmission delay圖2 傳輸時延

6 結束語

無線傳感器網絡之所以引發網絡能耗增加、生命周期縮短的不利影響，是由于網絡中的一些節點負載過重而能源快速耗盡，網絡傳播路徑的通信半徑增大。本文提出了一種節能的路由算法，算法以均衡網絡節點能耗為目的，優化路由選擇的標準采用預測的結果，在路徑建立過程中，下一跳節點選取鄰居節點中剩余能量較多的節點。實驗仿真結果表明，此算法有效防止了在路由建立時進行泛洪傳播而造成大量的能量消耗，同時更好地均衡網絡的能量消耗，最大限度地延長了網絡的壽命。但是，此方法未必是能量節省的最優方法，如何能使網絡生存時間更長，是今后需要研究的工作。

[1] Xiao R Y, Wu G. A survey on routing in wireless sensor networks [J]. Progress in Natural Science, 2007, 17(3):261-269.

[2] Wang J, Howitt I. Optimal traffic distribution in minimum energy wireless sensor networks[C]∥Proc of 2005 IEEE Global Telecommunications Conference, 2005:3274-3278.

[3] Liang W, Liu Y. Online data gathering for maximizing network lifetime in sensor networks [J]. IEEE Transactions on Mobile Computing, 2007, 6(1):2-11.

[4] Cheng Z, Perillo M, Heinzelman W B. General network lifetime and cost models for evaluating sensor network deployment straregies [J]. IEEE Transactions on Mobile Computing, 2008, 7(4):484-497.

[5] Zhao Ye-fei, Yang Zong-yuan, Xie Jin-kui. Pi-calculus based assembly mechanism of UML state diagram and validation of model refinement [C]∥Proc of International Conference on Electronic Computer Technology, 2009:604-609.

[6] Cai Jing-ming,Sun Ji-feng.Adaptive routing algorithm in wireless sensor networks [J]. Computer Engineering, 2009, 35(18):263-265. (in Chinese)

[7] Navratis S,Aahishek R,Jitae S.A QOS-based energy-aware MAC protocol for wireless mulitimedia sensor networks[C]∥Proc of Vehicular Technology Conference, 2008:183-187.

[8] Zhang Q, Xie Z P, Ling B. A maximum lifetime data gather-

ing algorithm for wireless sensor networks [J]. Journal of Software, 2005, 16(11):1946-1957.

[9] Nuran T, Wenye W. Self-orienting wireless multimedia sensor networks for maximizing multimedia coverage[C]∥Proc of IEEE International Conference, 2008:2206-2210.

[10] Wu Xiao-bing, Chen Gui-hai. The energy hole problem of non-uniform node distribution in wireless sensor networks[J]. Chinese Journal of Computers, 2008, 31(2):253-261. (in Chinese)

附中文參考文獻：

[6] 蔡景明, 孫季豐. 無線傳感器網絡中的自適應路由算法[J]. 計算機工程, 2009，35(18):263-265.

[10] 吳小兵, 陳貴海. 無線傳感器網絡中節點非均勻分布的能量空洞問題[J]. 計算機學報, 2008,31(2):253-261.