一種受時延約束的最大化生命周期數(shù)據(jù)收集算法

劉文彬（湖南財政經(jīng)濟學(xué)院信息管理系，湖南長沙410205）

一種受時延約束的最大化生命周期數(shù)據(jù)收集算法

劉文彬
（湖南財政經(jīng)濟學(xué)院信息管理系，湖南長沙410205）

在無線傳感器網(wǎng)絡(luò)中，構(gòu)造一棵網(wǎng)絡(luò)生命周期最大化、滿足用戶時延需求的數(shù)據(jù)收集樹，是一個NP完全問題.提出一種新的啟發(fā)式算法，該算法起始于Sink節(jié)點，然后每次將生命周期估計值最大、且其對應(yīng)的節(jié)點滿足用戶延時需求的邊加入到樹中，直到所有的節(jié)點加入到樹中為止.仿真實驗表明：與現(xiàn)有算法相比，該算法在滿足用戶時延的需求下，能有效地延長樹的生命周期.

無線傳感器網(wǎng)絡(luò)；生命周期；時延需求；數(shù)據(jù)收集

LiuWB.ADelay-Constrained Maximum-Lifetime Data Gathering Algorithm[J].Journal of Yibin University,2015,15 （6）：86-88.

無線傳感器網(wǎng)絡(luò)（WSNs）具有十分廣闊的應(yīng)用前景，包括在軍事監(jiān)視、森林火警監(jiān)視、野外考察、地形探測或建筑監(jiān)控等方面[1].這些應(yīng)用的基本任務(wù)是收集從各個監(jiān)控點采集到的信息，并最終傳輸給基站.但由于無線傳感器節(jié)點體積微小、能量非常有限，通常運行在人無法接近的惡劣、甚至危險的遠程環(huán)境中，通過更換電池的方式補充節(jié)點的能量是不現(xiàn)實的.此外，在一些諸如森林火警監(jiān)視、戰(zhàn)場監(jiān)控等持續(xù)性的監(jiān)視應(yīng)用中，除了要求網(wǎng)絡(luò)能保存能量長期地工作，還要求網(wǎng)絡(luò)在收集到數(shù)據(jù)后能盡快地將數(shù)據(jù)傳送給用戶進行處理.因此，在WSNs中，如何在滿足用戶時延需求的情況下，提高能量的使用效率，從而延長網(wǎng)絡(luò)壽命，已成為目前研究的熱點之一.

目前，學(xué)界已提出了大量基于樹結(jié)構(gòu)的數(shù)據(jù)收集方法.有些算法以最小生成樹算法為基礎(chǔ)，開始時建立一棵只包括Sink節(jié)點的數(shù)據(jù)收集樹，然后依次選擇一條權(quán)值最小的邊（邊的一個節(jié)點在樹上，另一個節(jié)點不在樹）加入到樹中，直到所有的傳感器節(jié)點加入到樹為止，如PEDAP算法[2]、PEDAP-PA算法[2]、MNL算法[3]、MLT算法[4]、ECRT算法[5]、MLDGA算法[6]等.還有一些算法初始于一棵任意的樹，然后采取不同的方法或手段，不斷地改進或改善樹的生命周期，直到不能改進為止，如LOCAL_OPT算法[5]、MDST算法[5]、IAA算法[7-8]與文獻［9］提出的算法等.

上述這些算法能做到生成樹上節(jié)點負載均衡，樹的生命周期達到近似最優(yōu).但是，樹的高度無法控制，難以應(yīng)用于對實時要求很高的環(huán)境中.為了滿足用戶的時延需求，DB-MDST算法[10]改進了MDST算法，其主要思想是在限制樹的高度的情況下，反復(fù)利用“加入－刪除”邊的操作減少節(jié)點的度，從而達到優(yōu)化樹的生命周期.DCML算法[11]和MILD算法[12]在IAA算法的基礎(chǔ)上考慮時延約束，它開始于最小跳數(shù)樹，然后在保證時延約束的條件下，反復(fù)將非樹上的一條邊去替代樹中的一條邊，以降低某一瓶頸結(jié)點或次瓶頸結(jié)點的度.

盡管DB-MDST算法、DCML算法和MILD算法能保證在時延受限的情況下構(gòu)造負載均衡的最大生命周期數(shù)據(jù)收集樹，但它們只將節(jié)點的跳數(shù)作為時延約束條件，而沒有考慮節(jié)點發(fā)送、接收、處理數(shù)據(jù)等方面所產(chǎn)生的時延，如子節(jié)點數(shù)多的節(jié)點產(chǎn)生的時延比子節(jié)點數(shù)少的節(jié)點產(chǎn)生的時延大.另外，反復(fù)優(yōu)化的過程需要大量的運行時間，從而造成算法具有較高的時間復(fù)雜性.因此，本文提出一種新的受時延約束的最大化生命周期數(shù)據(jù)收集樹算法（a Delay-Constrained Maximum-Lifetime data Gathering Tree algorithm，簡記為DCMLGT算法），旨在滿足用戶時延需求的情況下，提高能量的使用效率從而延長網(wǎng)絡(luò)壽命.

1　系統(tǒng)模型和問題的陳述

1.1網(wǎng)絡(luò)模型

假設(shè)用一個連通的無向圖G=（V,E）表示一個由n個無線傳感器和1個Sink節(jié)點組成的網(wǎng)絡(luò)，其中V={v0,v1,v2,…,vn},||V=n+1,v0表示Sink節(jié)點，v1, v2,…,vn表示n個無線傳感器且隨機分布在一個正方形區(qū)域A內(nèi)，邊（u,v）∈E是指傳感器u和傳感器v相互處于對方的通信范圍內(nèi)， ||E=m為邊的數(shù)量.

此外，無線傳感器網(wǎng)絡(luò)具有如下的性質(zhì)：

①網(wǎng)絡(luò)是連通的靜態(tài)網(wǎng)絡(luò)，節(jié)點部署后不再移動，即節(jié)點是固定的.②每個傳感器節(jié)點的初始能量有限，并且不能補充；Sink節(jié)點的能量是無限的.③除Sink節(jié)點外，所有節(jié)點具有相似的能力（處理/通信），并且地位平等.④采用數(shù)據(jù)聚合的方式進行通信，即每個傳感器節(jié)點接收其鄰居節(jié)點發(fā)來的m個大小為k bits的數(shù)據(jù)包，與自己產(chǎn)生的k bits數(shù)據(jù)進行聚合后，發(fā)送一個大小也為k bits的數(shù)據(jù)包給與自己的相鄰節(jié)點或Sink.

1.2能量消耗模型

本文采用與文獻[13]相同的無線通信能量消耗模型.節(jié)點發(fā)射k bit的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即：

其中Eelec表示發(fā)射電路損耗的能量，Eamp表示功率放大所需的能量.節(jié)點接收k bit的數(shù)據(jù)消耗的能量為：

1.3相關(guān)定義

為了方便描述在WSNs中如何構(gòu)造受時延約束最大化生命周期的數(shù)據(jù)收集樹，先將一些常用的術(shù)語和概念作定義.

定義1輪（Round）：是從所有傳感器節(jié)點收集一次數(shù)據(jù)，并傳送到Sink節(jié)點的過程.

定義2在一輪中，一個節(jié)點在樹上的能量消耗定義為：

其中m是節(jié)點v在樹上的孩子數(shù).

定義3節(jié)點的生命周期（Node lifetime）：是節(jié)點v在一棵樹中能存活的輪數(shù).存活指節(jié)點v的能量Eo（v）＞0，節(jié)點v在一棵樹中的生命周期可定義為：

定義4樹的生命周期（Tree lifetime）：是樹T中第一個節(jié)點死亡時，該節(jié)點存活的輪數(shù)，定義為：

定義5數(shù)據(jù)時延：如果節(jié)點u和節(jié)點v之間存在一條連通的路徑（用P（u,v）表示），那么，數(shù)據(jù)時延是指數(shù)據(jù)從節(jié)點u傳送到節(jié)點v的累計時延，即數(shù)據(jù)在路徑P（u,v）上所有節(jié)點的數(shù)據(jù)處理時延與數(shù)據(jù)在鏈路上的傳送時延之和，即：

1.4問題描述

無線傳感器網(wǎng)絡(luò)的重要目標就是在滿足應(yīng)用需求的前提下，盡可能長時間地對周圍環(huán)境進行監(jiān)測.這樣本文要解決的問題可描述為：①數(shù)據(jù)收集樹的生命周期最大化；②滿足數(shù)據(jù)收集的最大時延小于上限.

對于上述問題，可用公式（7）表示：

其中T是網(wǎng)絡(luò)G中任意一棵生成樹，Ts（G）是無向圖G中所有生成樹的集合，Δ為應(yīng)用需求的時延上限（或時延約束）.

2 DCMLGT算法

2.1DCMLGT算法描述

DCMLGT算法起始于只包含Sink節(jié)點的生成樹T，然后每次將生命周期估計值最大、且其對應(yīng)的節(jié)點滿足端對端時延約束的邊加入到生成樹，直到所有的節(jié)點加入到生成樹為止.DCMLGT算法的偽代碼如下：

輸入：圖G，時延約束△

輸出：滿足時延約束△的最大生命周期樹T

VT={sink}；

Q=V-{sink}；

Repeat

Maxlife=0

for each v∈Q{

If（u,v）∈E and u∈VT{

if delay（u,sink）+delay（u,v）≤△ {

計算w（u,v）

if maxlife≤w（u,v）{

maxlife=w（u,v）

add_edge=（u,v）

add_node=v

}

}

}

}

If maxlife＞0{

VT=VT∪{add_node}；

T=T∪{add_edge}；

Q=Q-{add_node}；

計算delay（add_node,sink）

}

else return false

until Q=0

在DCMLGT算法中，每次將一個節(jié)點加入生成樹的主要步驟為：對于每條邊（u,v）∈E，且u為生成樹T上的節(jié)點，v為非生成樹的節(jié)點，首先計算節(jié)點v經(jīng)節(jié)點 u到 Sink的時延 delay（v,Sink）.如果delay（v,Sink）≤Δ，則計算邊（u,v）的權(quán)值.邊（u,v）的權(quán)值設(shè)為該邊兩端節(jié)點的生命周期估計值中的最小值，即：w（u,v）=min（LE（u）,LE（v）），其中 LE（u）=E0（u）/（（m+1）×Erx（k）+Etx（k,d））表示節(jié)點u的生命周期的估計值（m為節(jié)點u在當前生成樹上孩子節(jié)點的個數(shù)）；LE（v）=E0（v）/（Etx（k,d））表示節(jié)點v的生命周期的估計值.最后，在所有連接生成樹T上的節(jié)點和非生成樹上的節(jié)點的邊中，取權(quán)值最大、且其對應(yīng)的節(jié)點滿足端對端時延約束的邊加入到生成樹上.

2.2仿真實驗

假設(shè)網(wǎng)絡(luò)中所有節(jié)點隨機地分布在一個200× 200平方米的正方形區(qū)域.每個節(jié)點的初始能量在［1J,1.5J］之間隨機分布，節(jié)點的數(shù)據(jù)產(chǎn)生率為1 000 bits/round，Erx=50 nJ/bit.所有節(jié)點的最大通信半徑為50m.在每一個隨機網(wǎng)絡(luò)中，Sink節(jié)點的位置位于區(qū)域的中心.為了測試DCMLGT算法的性能，本文選擇DB－MDST和MILD算法進行對比，且網(wǎng)絡(luò)結(jié)點數(shù)在50～400之間變化，時延約束條件Δ在［10，40］ms之間變化.一般來說，數(shù)據(jù)在鏈路上的傳送時延與結(jié)點之間的距離成正比，節(jié)點處理數(shù)據(jù)的時延與該節(jié)點及其子節(jié)點的個數(shù)相關(guān).但本文為了便于與DB－MDST和MILD算法進行比較，在仿真實驗中，將數(shù)據(jù)在鏈路上的傳送時延設(shè)置為1ms，節(jié)點處理節(jié)點本身或每個子節(jié)點的數(shù)據(jù)時延為0.1ms.實驗結(jié)果均是執(zhí)行50次后的平均結(jié)果.

圖1是網(wǎng)絡(luò)的生命周期隨網(wǎng)絡(luò)節(jié)點員數(shù)目變化時的曲線圖，圖2是網(wǎng)絡(luò)大小變化時各種算法的計算時間曲線圖.從圖中可以看出，DCMLGT算法在網(wǎng)絡(luò)的生命周期上優(yōu)于DB－MDST算法而劣于MILD算法，在計算時間上優(yōu)于DB－MDST和MILD算法.

圖1　網(wǎng)絡(luò)生命周期對比圖

圖2　算法的計算時間曲線圖

3　結(jié)語

在無線傳感器網(wǎng)絡(luò)中，構(gòu)造一棵網(wǎng)絡(luò)生命周期最大化、滿足用戶延時需求的數(shù)據(jù)收集樹，是一個NP完全問題.針對目前一些算法沒有考慮節(jié)點發(fā)送、接收、處理數(shù)據(jù)等方面所產(chǎn)生的時延，提出一種新的啟發(fā)式算法，該算法起始于Sink節(jié)點，然后每次將生命周期估計值最大、且其對應(yīng)的節(jié)點滿足用戶延時需求的邊加入到樹中，直到所有的節(jié)點加入到樹中為止.仿真實驗表明：與現(xiàn)有算法相比，該算法在時延受限的情況下，能有效地延長樹的生命周期.

[1]Akyildiz IF,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks：a survey［J］.Computer Networks,2002,38（4）：393-422.

[2]Korpeoglu I,Tan H O.Power efficient data gathering and aggrega?tion in wireless sensor networks［J］.SIGMOD Record,2003,32（4）：66-71.

[3]LiangW F,Liu Y Z.Online data gathering formaximizing network lifetime in sensor networks［J］.IEEE Transactions on Mobile Com?puting,2007,6（1）：1-10.

[4]Badrinath G S,Gupta P,Das SK.Maximum lifetime tree construc?tion for wireless sensor networks［J］.Lecture Notes in Computer Science,2007：158-165.

[5]Buragohain C,Agrawal D,Suri S.Power aware routing for sensor databases［C］.Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM 2005）, Miami,2005：1747-1757.

[6]Zhang Q,Xie ZP,Ling B,etal.Amaximum lifetime data gathering algorithm for wireless sensor networks［J］.Journal of Software, 2005,16（11）：1946-1957.

[7]Yan W,Sonia F,Shroff N B.On the construction of a maximumlifetime data gathering tree in sensor networks：NP-completeness and approximation algorithm［C］.Proc of the 27th IEEE Confer? ence on Computer Communications（INFOCOM2008）,Phoenix, 2008：356-360.

[8]YanW,Mao Z J,Sonia F,etal.Constructingmaximum-lifetime da?ta-gathering forests in sensor networks［J］.IEEE/ACM Transac?tionson Networking,2010,18（5）：1571-1584.

[9]Lin H C,Li F J,Wang K Y.Constructingmaximum-lifetime data gathering trees in sensor networkswith data aggregation［C］.Proc of IEEE International Conference on Communications（ICC）,Cape Town,2010：1-6.

[10]Kwon S,Kim JG,Kim C.An efficient tree structure for delay sensi?tive data gathering in wireless sensor networks［C］.Proc of the 22nd IEEE International Conference on Advanced Information Net?workingand Applications,Okinawa,2008：738-743.

[11]Liang JB,Wang JX,Chen JN.A delay-constrained andmaximum lifetime data gathering algorithm for wireless sensor networks［C］.Proc of the 5th International Conference on Mobile Ad-hoc and Sensor Networks（MSN'09）,WuyiMountain,2009：148-155.

[12]梁俊斌,王建新,陳建二.在傳感器網(wǎng)絡(luò)中構(gòu)造延遲限定的最大化生命周期樹［J］.電子學(xué)報,2010,38（2）：345-351.

[13]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-effi?cient communication strategies for wireless sensor networks［C］.Proceedingsof the 33rd Hawail International Conference on System Science,Hawaii,2000.

（編校：王露）

A Delay-Constrained Maximum-Lifetime Data Gathering Algorithm

LIUWenbin
（Departmentof Information and Management,Hunan University ofFinanceand Economics,Changsha,Hunan 410205,China）

The problem of constructing a data gathering treewhichmaximizes the network lifetime and satisfies the user's delay requirements inWSNs（Wireless Sensor Networks）is NP-complete.A new heuristics is proposed to solve this prob?lem.Starting from the Sink,this heuristics selects an edgewithmaximum estimation of lifetime and ability to satisfy the user's delay requirements to join the tree iteratively.It repeats this procedure untilallnodesare added to the tree.Simula?tion results show that the heuristics can constructa tree thathas longer lifetime than previous algorithms under the need ofuser'sdelay.

wirelesssensornetworks；lifetime；delay requirements；data gathering

TP393

A

1671-5365（2015）06-0086-03

2015-01-29修回：2015-03-18

劉文彬（1975-），男，講師，碩士，研究方向為無線網(wǎng)絡(luò)通信、算法優(yōu)化、交通組織與交通控制

網(wǎng)絡(luò)出版時間：2015-03-23 16：48網(wǎng)絡(luò)出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20150323.1648.001.html

引用格式：劉文彬.一種受時延約束的最大化生命周期數(shù)據(jù)收集算法[J].宜賓學(xué)院學(xué)報,2015,15（6）：86-88.