李 平，戴 勁

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

1 引言

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

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

2 相關工作

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

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

3 生存網絡模型

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

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

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

Er(k，d)=kEelec+kEampd2

(1)

Er(k)=kEelec

(2)

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

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

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

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

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

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

(3)

從而可以得出節(jié)點的生存時間為：

(4)

4 最小跳數(shù)建立

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

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

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

4.1 節(jié)點選擇階段

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

若有多個鄰居節(jié)點到Sink節(jié)點的跳數(shù)相同，就選擇剩余能量最多的鄰居節(jié)點作為中繼節(jié)點來轉發(fā)數(shù)據(jù)包。

4.2 保護節(jié)點能量

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

5 仿真實驗

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

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

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

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

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

Figure 2 Transmission delay圖2 傳輸時延

6 結束語

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

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