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

劉文彬（湖南財政經濟學院信息管理系，湖南長沙410205）

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

劉文彬
（湖南財政經濟學院信息管理系，湖南長沙410205）

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

無線傳感器網絡；生命周期；時延需求；數據收集

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

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

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

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

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

1　系統模型和問題的陳述

1.1網絡模型

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

此外，無線傳感器網絡具有如下的性質：

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

1.2能量消耗模型

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

其中Eelec表示發射電路損耗的能量，Eamp表示功率放大所需的能量.節點接收k bit的數據消耗的能量為：

1.3相關定義

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

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

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

其中m是節點v在樹上的孩子數.

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

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

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

1.4問題描述

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

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

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

2 DCMLGT算法

2.1DCMLGT算法描述

DCMLGT算法起始于只包含Sink節點的生成樹T，然后每次將生命周期估計值最大、且其對應的節點滿足端對端時延約束的邊加入到生成樹，直到所有的節點加入到生成樹為止.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算法中，每次將一個節點加入生成樹的主要步驟為：對于每條邊（u,v）∈E，且u為生成樹T上的節點，v為非生成樹的節點，首先計算節點v經節點 u到 Sink的時延 delay（v,Sink）.如果delay（v,Sink）≤Δ，則計算邊（u,v）的權值.邊（u,v）的權值設為該邊兩端節點的生命周期估計值中的最小值，即：w（u,v）=min（LE（u）,LE（v）），其中 LE（u）=E0（u）/（（m+1）×Erx（k）+Etx（k,d））表示節點u的生命周期的估計值（m為節點u在當前生成樹上孩子節點的個數）；LE（v）=E0（v）/（Etx（k,d））表示節點v的生命周期的估計值.最后，在所有連接生成樹T上的節點和非生成樹上的節點的邊中，取權值最大、且其對應的節點滿足端對端時延約束的邊加入到生成樹上.

2.2仿真實驗

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

圖1是網絡的生命周期隨網絡節點員數目變化時的曲線圖，圖2是網絡大小變化時各種算法的計算時間曲線圖.從圖中可以看出，DCMLGT算法在網絡的生命周期上優于DB－MDST算法而劣于MILD算法，在計算時間上優于DB－MDST和MILD算法.

圖1　網絡生命周期對比圖

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

3　結語

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

[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]梁俊斌,王建新,陳建二.在傳感器網絡中構造延遲限定的最大化生命周期樹［J］.電子學報,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-），男，講師，碩士，研究方向為無線網絡通信、算法優化、交通組織與交通控制

網絡出版時間：2015-03-23 16：48網絡出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20150323.1648.001.html

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