能量感知的ＷＳＮ自適應數(shù)據(jù)融合路由算法

摘 要:針對傳感器節(jié)點以能量有效的方式收集相關性數(shù)據(jù)問題，提出了一種能量感知的自適應數(shù)據(jù)融合路由算法EAAF(energy-aware adaptive data fusion routing algorithm for wireless sensor networks)。算法選擇路由時，根據(jù)數(shù)據(jù)傳輸和數(shù)據(jù)融合能量開銷及節(jié)能增益，對數(shù)據(jù)遷移到每個傳感器節(jié)點是否進行數(shù)據(jù)融合作自適應選擇，從而實現(xiàn)在信息收集過程中提高網(wǎng)絡的能效。仿真結果表明，能量感知的自適應數(shù)據(jù)融合路由算法的能效大幅度優(yōu)于SPT、MST和SLT算法。

關鍵詞:無線傳感器網(wǎng)絡; 能量感知; 數(shù)據(jù)融合; 節(jié)能增益; 路由算法

中圖分類號:TP393.04文獻標志碼:A

文章編號:1001-3695(2009)09-3481-03

doi:10.3969/j.issn.1001-3695.2009.09.079

Energy-aware adaptive data fusion routing algorithm for wireless sensor networks

TIAN Feng， XING Er-qing

(College of Computer Science， Shenyang Institute of Aeronautical Engineering， Shenyang 110036， China)

Abstract:This paper proposed an energy-aware adaptive data fusion routing algorithm in order to solve the problem of sensor nodes collecting correlated data with energy validity. When selecting the data fusion routing， adaptively adjusted sensor node receiving the data that shall perform fusion according to data transmission cost， data fusion cost and energy gain. The simulation results indicate that the energy-aware adaptive data fusion routing algorithm has better performance than SPT(shortest paths tree)， MST(minimum spanning tree) and SLT(shallow light tree) in terms of energy validity.

Key words:wireless sensor network(WSN); energy-aware; data fusion; energy gain; routing algorithm

隨著傳感器技術、嵌入式技術以及低功耗無線通信技術的發(fā)展，生產(chǎn)具備感應、無線通信、處理能力的微型無線傳感器已成為現(xiàn)實。這些廉價的、低功耗的傳感器節(jié)點共同組織成無線傳感器網(wǎng)絡。通過節(jié)點間的相互協(xié)作，把監(jiān)測和感應的多種環(huán)境信息傳送到基站進行處理。以能量有效的方式收集相關性數(shù)據(jù)是WSN的重要應用之一，但此應用中存在著能量有限、相鄰節(jié)點數(shù)據(jù)存在冗余信息等特點。這些特點決定中間節(jié)點不僅要負責轉發(fā)數(shù)據(jù)分組，而且要按照一定的規(guī)則處理數(shù)據(jù)。數(shù)據(jù)融合可以消除冗余信息，減少數(shù)據(jù)傳輸量，從而有效地節(jié)省能量，延長網(wǎng)絡生命。

數(shù)據(jù)融合算法通常分為兩種，即路由驅動算法和融合驅動算法，但這兩類算法常常忽略數(shù)據(jù)融合的能量問題。隨著傳感器監(jiān)測對象的擴大以及復雜性的增強，所需融合能量也相應增加。例如，隨著加、解密算法復雜度的增強，在逐跳安全網(wǎng)絡中對節(jié)點進行加密和解密的融合能耗可達到nJ/bit能量級;又如信號融合的聲音波束成形算法和圖像融合的矢量數(shù)據(jù)融合算法[1]，其數(shù)據(jù)融合能耗具有與傳輸相同的能量級。

文獻[2，3]證明了對于一個節(jié)點任意放置的傳感器網(wǎng)絡，數(shù)據(jù)傳輸次數(shù)最小的DC路由可以轉換為最小Steiner樹，構造這樣的路由是一個NP難問題。于是文獻[2]提及了三種實用的次優(yōu)方案。其中最短路徑樹(shortest paths tree， SPT)要求每個數(shù)據(jù)源數(shù)據(jù)沿著到達匯聚節(jié)點的最短路徑進行傳送，路徑交疊部分的每個節(jié)點都進行數(shù)據(jù)融合。這種方案保證了數(shù)據(jù)最快地傳送到sink節(jié)點，但是在路徑選擇上沒有考慮到節(jié)點的能耗問題，容易導致最短路徑上的節(jié)點提前死亡，從而影響整個網(wǎng)絡壽命。文獻[4]中通過對PEGASIS協(xié)議[5]擴展提出了PEDAP協(xié)議，其核心思想是基站把傳感器網(wǎng)絡中所有節(jié)點構造成一棵最小生成樹(minimum spanning tree， MST)，保證數(shù)據(jù)在傳遞路徑之和最短來有效控制能耗問題。然而PEDAP是集中式算法，難以及時排除樹中意外死亡的節(jié)點，導致網(wǎng)絡魯棒性不強。此外，由于最小生成樹只能保證任意兩節(jié)點間的連通性，數(shù)據(jù)在傳輸過程中延遲性較大。而文獻[6，7]分析了SPT和MST的優(yōu)缺點問題后提出了淺輕樹(shallow light tree， SLT)算法。該算法可以有效地平衡數(shù)據(jù)在路由上的融合與延遲問題，但是隨著數(shù)據(jù)相關性的遞減，該算法不能自適應地判斷是否進行融合操作，因而會引入不必要的能耗問題。

本文基于文獻[2～8]提出了一種能量感知的自適應數(shù)據(jù)融合路由算法(energy-aware adaptive data fusion routing algorithm for wireless sensor networks， EAAF)。算法根據(jù)節(jié)點間的數(shù)據(jù)量、剩余能量選擇中間節(jié)點，而中間節(jié)點根據(jù)數(shù)據(jù)融合的節(jié)能增益情況，自適應地判定是否進行數(shù)據(jù)融合，從而可以優(yōu)化數(shù)據(jù)聚合過程，達到延長網(wǎng)絡生命期的目的。

1 EAAF算法

1.1 網(wǎng)絡模型

假定無線傳感器網(wǎng)絡為圖G=(V，E)。其中V是節(jié)點集合，E是任意兩個節(jié)點間鏈路集合。

定義1 設任意節(jié)點v∈V的權重為傳輸數(shù)據(jù)量w(v)，邊e=(u，v)∈E的權重等于它起始節(jié)點的權重，所以w(e)=w(u)。其中u為起點，v為終點。

定義2 設t(e)為傳輸能量，c(e)為單位傳輸能量，則邊e的傳輸能量為t(e)=c(e)w(e)。

定義3 設f(e)為在節(jié)點v進行數(shù)據(jù)融合的能耗，q(e)為單位融合能量，w(#8226;)為數(shù)據(jù)融合前的權重，w(#8226;)為數(shù)據(jù)融合后的權重，節(jié)點u的數(shù)據(jù)在節(jié)點v進行融合消耗的能量為

f(e)=q(e)(w(u)+w(v))(1)

數(shù)據(jù)融合率σuv是數(shù)據(jù)融合的關鍵因素之一，由此在節(jié)點v進行數(shù)據(jù)融合后的權重為

w(v)=(w(u)+w(v))(1-σuv)(2)

綜合后得節(jié)點v的融合方程為

w(v)=(w(u)+w(v))(1-σuvxuv)(3)

其中:xuv∈{0，1}表示為e是否發(fā)生數(shù)據(jù)融合。

1.2 EAAF算法描述

在無線傳感器網(wǎng)絡的數(shù)據(jù)融合操作中，由于中間節(jié)點(center)需要接收和聚合相鄰節(jié)點的感知數(shù)據(jù)，其能耗遠大于普通節(jié)點。為了均衡節(jié)點的能量負載，中間節(jié)點的選擇應該按照一定規(guī)則在配對節(jié)點間擇優(yōu)選擇。為了方便參考，表1中列出了本算法中節(jié)點的所有狀態(tài)和控制消息以及其相應的描述信息。

表1 狀態(tài)和消息描述

statedescriptionmessagedescription

nodenode for competion centerS_MsgTuple(selfid， self residual energy， weight)

centeraggregationC_MsgTuple(selfid)

在EAAF算法中，網(wǎng)絡G中節(jié)點的ID用來標志該節(jié)點在網(wǎng)絡中的惟一身份。數(shù)據(jù)傳輸前每個節(jié)點首先以半徑rc廣播消息S_Msg，S_Msg包括節(jié)點的ID、剩余能量以及數(shù)據(jù)量。每個節(jié)點根據(jù)所有鄰居節(jié)點發(fā)送來的S_Msg更新鄰居表，更新鄰居表后，每個節(jié)點根據(jù)式(4)求出其配對的節(jié)點間最小通信代價路徑。

M(u，v)=q(e)#8226;(w(u)+w(v))+w(u)c(e)(4)

配對節(jié)點的最小通信代價路徑選擇好后，根據(jù)式(5)在兩節(jié)點間選擇center節(jié)點。

(((w(u)+w(v))C(u，t))/Eu>(((w(u)+w(v))C(v，t))/Ev(5)

其中:C(x，t)(x為假定的聚集節(jié)點)表示節(jié)點x的數(shù)據(jù)傳輸?shù)絪ink節(jié)點t的過程中單位傳輸代價之和;Ex表示節(jié)點x的剩余能量。

當式(5)成立，則v充當center節(jié)點;反之，u充當center節(jié)點。另外，當其中一個節(jié)點為sink節(jié)點t時，t為center節(jié)點，然后節(jié)點的數(shù)據(jù)被傳輸?shù)絚enter節(jié)點，center節(jié)點根據(jù)式(6)計算融合的節(jié)能增益情況，進而判斷在center節(jié)點是否進行數(shù)據(jù)融合操作。

Δu，v=((w(u)+w(v))C(v，t)-w(v)C(v，t)-q(v，t)(w(u)+w(v))(6)

如果節(jié)點間的增益Δu，v<0，則節(jié)點間不進行數(shù)據(jù)融合，添加邊到En={e|e∈E，xe=0}中。根據(jù)數(shù)據(jù)從源節(jié)點到sink節(jié)點的融合過程數(shù)據(jù)相關性為非增函數(shù)，所以數(shù)據(jù)融合中qe為非減函數(shù)，σe為非增函數(shù)，可以證明數(shù)據(jù)在隨后的傳輸過程中數(shù)據(jù)融合增益為非增函數(shù)，所以該數(shù)據(jù)在傳遞過程中不再判斷是否進行數(shù)據(jù)融合操作，而是根據(jù)改進的最短路徑樹算法[6，7]選擇下一跳路由將數(shù)據(jù)直接轉發(fā)。此時的路由選擇可以有效地避免引入更多能耗和減少數(shù)據(jù)傳輸時間延遲問題。反之，當節(jié)點間的增益Δu，v>0，則節(jié)點可以進行數(shù)據(jù)融合，添加邊到Ef={e|e∈E，xe=1}中并進行融合操作。融合后的center節(jié)點作為新的源節(jié)點，繼續(xù)進行上述操作，直到數(shù)據(jù)傳輸?shù)絪ink節(jié)點。

據(jù)此本文在圖G中得到了能量感知的自適應數(shù)據(jù)融合路由算法的最優(yōu)子圖:

G=arg minG∑e∈Ef(f(e)+t(e))+∑e∈Ent(e)

2 仿真結果與性能分析

2.1 仿真環(huán)境

利用OMNeT++仿真平臺將100個傳感器節(jié)點均勻地分布在一個50 m×50 m區(qū)域內，設每個節(jié)點產(chǎn)生一個400 Byte的數(shù)據(jù)包，然后發(fā)送數(shù)據(jù)到sink節(jié)點，sink節(jié)點被布置在底部右邊角。假定節(jié)點的最大通信半徑為rc，通過調整rc的大小可以控制網(wǎng)絡的連通性。定義單位比特傳輸能量c(e)=βdn+ε[10]。其中d為節(jié)點間的歐式距離;無線通信的可調參數(shù)β=100 pJ/(bit#8226;m2)及n=2;發(fā)送與接收單位比特能量為ε=100 nJ/bit[1]。

相關節(jié)點的數(shù)據(jù)相關性可由數(shù)據(jù)融合率σ來表示為節(jié)點，rs為節(jié)點間的相關范圍。當d≤rs，σ=1-d/rs;反之，σ=0。于是在節(jié)點v進行數(shù)據(jù)融合有w(v)=(w(u)+w(v))(1-σuv)。假定q(#8226;)是一個常量，用ω表示在每個節(jié)點數(shù)據(jù)的單位平均融合代價。

2.2 仿真結果分析

下面通過一系列實驗測試本文提出的數(shù)據(jù)融合算法的性能。圖1中設ω=80 nJ/bit，rs=50 m。隨著通信半徑的增大，網(wǎng)絡連通性也隨之增強。正如在圖1(a)中看到的，MST當融合率降低后，浪費有限的能量在數(shù)據(jù)的融合上，同時還引入了更多的能耗。相反，SPT選擇最短路徑到達sink節(jié)點，所以在融合數(shù)據(jù)傳輸上消耗過多的能量。而SLT算法有效地平衡了MST和SPT的特點。但是由于算法的內在限制，使得能耗依然相對很高。EAAF算法可以根據(jù)數(shù)據(jù)之間的相關性，自適應地根據(jù)網(wǎng)絡節(jié)能增益結果判定是否進行數(shù)據(jù)融合操作，從而有效地避免不必要的能量消耗。所以EAAF算法在通信范圍內能耗持遞減。圖1(b)表示其他算法與EAAF算法的能量消耗之比。當連通性很強時，EAAF與MST相比節(jié)省了48%的能耗;與SPT相比最大節(jié)省38%的能耗;與SLT相比節(jié)省15%的能耗。

單位融合能量的高低影響融合能量開銷，從而影響在中間節(jié)點是否進行數(shù)據(jù)融合。圖2中相關范圍rs=2~64 m，對應σ=0～1。圖2(a)中當數(shù)據(jù)相關性較弱時，EAAF中中間節(jié)點不進行數(shù)據(jù)融合，其能量消耗接近于此時的最優(yōu)解SPT-NF的能耗;當數(shù)據(jù)相關性較強時，進行數(shù)據(jù)融合有利于減少能量消耗，EAAF自適應調整中間節(jié)點是否進行數(shù)據(jù)融合，其能耗在所有算法中最優(yōu)。

比較圖2(a)和(b)可見，當單位融合代價為(ω=50 nJ/bit)時，進行數(shù)據(jù)融合非常有益，但當單位融合代價為(ω=120 nJ/bit)時，進行數(shù)據(jù)融合反而會增加能量消耗。圖2(b)中SPT和SLT因單位融合能量較高使得融合能量大于節(jié)省的傳輸能量，所以它們的能量消耗大于SPT-NF的能量消耗;但EAAF算法通過比較融合能量與節(jié)省的傳輸能量，自適應地決定center節(jié)點是否進行數(shù)據(jù)融合操作，減少了融合能量消耗而優(yōu)于SPT-NF，因而在上述兩種情況下EAAF算法性能幾乎平穩(wěn)最優(yōu)。

3 結束語

在EAAF算法中，每一次傳輸融合后其節(jié)點集合的大小至少減半。根據(jù)轉發(fā)的數(shù)據(jù)融合操作結果，后邊的center節(jié)點可以很快地判斷是否進行節(jié)能增益計算，進而決定中間節(jié)點在數(shù)據(jù)轉發(fā)過程中路由選擇問題。據(jù)此，EAAF算法可以有效地平衡了節(jié)點間的能耗問題，延長網(wǎng)絡工作壽命。此外，EAAF算法的路由是基于二叉反向組播樹的，所以在數(shù)據(jù)融合過程中可以有效地減少數(shù)據(jù)收集過程的延遲等待時間。下一步的工作將對數(shù)據(jù)傳輸延遲作進一步分析來改進EAAF算法，使其具有更實用的應用價值。

參考文獻:

[1]WANG A， HEINZELMAN W B， CHANDRAKASAN A P. Energy-scalable protocols for battery-operated microsensor networks[J]. Journal of VLSI Signal Processing， 2001，29(3): 223-237.

[2]KRISHNAMACHARI B， ESTRIN D，WICKER S. The impact of data aggregation in wireless sensor networks[C]//Proc of the 22nd International Conference on Distributed Computing Systems. 2002: 575-578.

[3]KRISHNAMACHARI B， ESTRIN D，WICKER S. Modelling data-centric routing in wireless sensor networks[C]//Proc of IEEE INFOCOM. New York: IEEE Computer Society，2002: 2-14.

[4]TAN H O. Power efficient data gathering and aggregation in wireless sensor networks [J]. SIGMOD Record，2003， 32(4):67-71.

[5]LINDSEY S， RAGHAVENDRA C S. PEGASIS: power efficient gathering in sensor information systems[C]//Proc of IEEE Aerospace Confe-rence.2002.

[6]GOEL A， MUNAGALA K. Balancing steiner trees and shortest path trees online[C]// Proc of the 11th ACM-SIAM Symposium on Discrete Algorithms. 2000.

[7]RAGHAVACHARI B， KHULLER S， YOUNG N. Balancing minimum spanning and shortest path trees[C]// Proc of the 4th ACM-SIAM Symposium on Discrete Algorithms. 1993.

[8]CHOI W， DAS S K. Trade-off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks[C]// HUBAUX J P， MAKKI K， ZHOU C， et al. Proc of IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS 2004). San Francisco: IEEE Computer Society Press， 2004: 503-512.

[9]LIU Ming， GONG Hai-gang， CHEN Lin-jun， et al. EADEEG: an energy-aware data gathering protocol for wireless sensor networks[J]. Journal of Software， 2007， 18(5):1092-1109.

[10]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks[C]// Proc of the 33rd Annual Hawaii International Conference on System Sciences. 2000.