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

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

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

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

無線傳感器網(wǎng)絡(luò)；生命周期；時(shí)延需求；數(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ù)是收集從各個(gè)監(jiān)控點(diǎn)采集到的信息，并最終傳輸給基站.但由于無線傳感器節(jié)點(diǎn)體積微小、能量非常有限，通常運(yùn)行在人無法接近的惡劣、甚至危險(xiǎn)的遠(yuǎn)程環(huán)境中，通過更換電池的方式補(bǔ)充節(jié)點(diǎn)的能量是不現(xiàn)實(shí)的.此外，在一些諸如森林火警監(jiān)視、戰(zhàn)場監(jiān)控等持續(xù)性的監(jiān)視應(yīng)用中，除了要求網(wǎng)絡(luò)能保存能量長期地工作，還要求網(wǎng)絡(luò)在收集到數(shù)據(jù)后能盡快地將數(shù)據(jù)傳送給用戶進(jìn)行處理.因此，在WSNs中，如何在滿足用戶時(shí)延需求的情況下，提高能量的使用效率，從而延長網(wǎng)絡(luò)壽命，已成為目前研究的熱點(diǎn)之一.

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

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

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

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

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

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

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

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

1.2能量消耗模型

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

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

1.3相關(guān)定義

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

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

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

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

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

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

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

1.4問題描述

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

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

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

2 DCMLGT算法

2.1DCMLGT算法描述

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

輸入：圖G，時(shí)延約束△

輸出：滿足時(shí)延約束△的最大生命周期樹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）≤△ {

計(jì)算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}；

計(jì)算delay（add_node,sink）

}

else return false

until Q=0

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

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

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

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

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

圖2　算法的計(jì)算時(shí)間曲線圖

3　結(jié)語

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

[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é)報(bào),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-），男，講師，碩士，研究方向?yàn)闊o線網(wǎng)絡(luò)通信、算法優(yōu)化、交通組織與交通控制

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

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