李 平，戴 勁

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

1 引言

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

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

2 相關(guān)工作

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

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

3 生存網(wǎng)絡(luò)模型

假設(shè)傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)分布在一個正方形監(jiān)測區(qū)域內(nèi)，該網(wǎng)絡(luò)具有以下特性：

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

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

Er(k，d)=kEelec+kEampd2

(1)

Er(k)=kEelec

(2)

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

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

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

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

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

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

(3)

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

(4)

4 最小跳數(shù)建立

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

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

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

4.1 節(jié)點(diǎn)選擇階段

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

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

4.2 保護(hù)節(jié)點(diǎn)能量

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

5 仿真實(shí)驗(yàn)

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

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

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

Figure 1 Survival time of the network graph圖1 網(wǎng)絡(luò)生存時間圖

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

Figure 2 Transmission delay圖2 傳輸時延

6 結(jié)束語

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

[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)

附中文參考文獻(xiàn)：

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

[10] 吳小兵, 陳貴海. 無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問題[J]. 計(jì)算機(jī)學(xué)報(bào), 2008,31(2):253-261.