無線傳感器網絡中分布式延遲受限低能耗數據收集算法

陳零，奎曉燕，張士庚，王建新

?

無線傳感器網絡中分布式延遲受限低能耗數據收集算法

陳零，奎曉燕，張士庚，王建新

(中南大學信息科學與工程學院，湖南長沙，410083)

集中式數據收集算法難以實際應用于外部環境惡劣、實時性要求高的無線傳感器網絡場景中。為解決此問題，采用分布式思想來構造算法，從而提出一種易于實現且有效的算法DBEGA(distributed delay-bounded energy-efficient data gathering algorithm)。DBEGA算法的基本步驟是：先生成1棵最少跳數的數據收集樹來滿足特定應用中延遲受限的要求；在此基礎上，借用時間復用的方法，將一特定長度的時間段分割成個等長的獨立時間片，然后將這些時間片唯一地分配給每個節點，每個節點就能互不干擾地對已生成的數據收集樹進行調整，使得各個節點的負載盡量均衡，從而達到延長網絡生命周期的目的。研究結果表明：與隨機路由和分布式算法LMST相比，DBEGA所構造的數據收集樹能夠在滿足延遲受限要求的同時將網絡生命周期提高20%以上。

無線傳感器網絡；數據收集；數據收集生成樹

近幾年來，對無線傳感器網絡的研究一直是熱點。其最基本的應用是通過部署好的無線傳感器節點對某塊區域進行特定目的監測，并將感知的特定信息通過無線方式傳送到遠程基站(Sink)進行后續處理。一般來說，部署在監測區域的無線傳感器節點由于各種原因，其能量無法補充，當自身能源耗盡時就意味著節點死亡：因此，如何在監測過程中盡量降低節點能耗，從而延長網絡的整體生命周期，是無線傳感器網絡協議設計的主要目標之一。相關研究表明，傳感器節點的能量主要消耗在各種通信上，而對感知數據的傳輸是通信開銷的主要來源，所以，設計能量高效的數據收集算法，對于延長無線傳感器網的生命周期具有重要意義[1]。另一方面，在一些需要快速反應的監測應用場景如森林火災監視、礦坑瓦斯預警、戰場信息監控中，不僅要盡可能地延長無線傳感器網絡的生命周期，而且需要盡快地將感知信息傳遞到基站進行分析和處理[2]。這就要求數據收集算法不僅要考慮網絡生存周期延長，而且需要使得網絡延遲盡可能短。如何構建滿足網絡延遲限制的數據收集樹也是目前無線傳感器網絡領域的一個重要研究問題。在多跳無線傳感器網中，網絡延遲與感知節點到達基站節點所經過的跳數有直接關系，跳數越少，延遲越短。而根據圖的相關理論，跳數可以轉化為數據收集生成樹的高度，所以，生成1棵最低高度的數據收集生成樹可以讓多跳傳感器網的延遲大大縮短。算法DB-MDST[3]和MILD[4]等都是針對延遲受限提出的基于樹的集中式數據收集算法。其中，MILD是DB-MDST的改進算法，它利用一種均衡最少跳數收集樹中節點度的方法，在保證網絡延遲較短的情況下，能有效延長網絡的生命周期。然而，在某些延遲受限的特定應用如戰場信息監控、火山監測預警中，由于客觀環境的極端不確定性，傳感器節點很容易被損毀，為有效監測某一區域，需布撒大量節點進行冗余覆蓋[5?8]。從成本上考慮，傳感器節點的運算和存儲能力將十分受限，基站節點也不能部署在監測區域之內(因基站成本較高，不能經常損毀)，這樣就會要求各個節點輪流擔任臨時基站的角色，而集中式算法對節點的運算和存儲要求較高，已不適用于這種情形。為此，本文作者提出一種新的分布式數據收集算法DBEGA(distributed delay-bounded energy-efficient data gathering algorithm)，其通信開銷小，對節點運算能力要求低，特別適用于上述應用場景。

1 相關工作

目前，基于樹的數據收集算法在保證網絡連通性和可靠性方面具有天然的優勢，而且具有保證QoS、便于實現高效的能量管理等優點，是目前研究的熱點。在早期的典型樹收集算法中，重點關注的是網絡整體的生命周期，對于網絡延遲基本忽略。下面簡要介紹幾種方法。

PEDAP-PA[9]從1棵只包含Sink節點的樹出發，以樹外節點和樹上節點間的通信代價作為權值，不斷挑選權值最小的節點加入樹，直至網絡中所有節點加入樹為止。MNL是對PEDAP-PA的改進[10]，設計了更合理的權值來挑選節點加入樹。然而，PEDAP-PA和MNL在構造生成樹的過程中，樹外節點是作為葉子節點被考慮并加入樹，在樹沒有最終建立前無法確定1個節點最終在樹上擁有多少孩子，因此，它們的生成樹往往存在節點負載不均衡、樹的高度無法控制等情況。IAA從1棵任意樹出發，迭代地選擇1條能使“瓶頸節點”包含在1個圈中的任意邊加入樹，然后，刪除該“瓶頸節點”在圈中關聯的任意1條邊以使“瓶頸節點”的度減少１并打破圈[11]。IAA能做到生成樹上節點負載均衡，樹的生命周期達到近似最優。但是，樹的高度也無法控制。

比較典型的以網絡延遲受限為前提要求的算法有DB-MDST和MILD。MILD是對DB-MDST的改進，它通過限定樹的高度來滿足延遲要求，然后通過使樹上“瓶頸節點”的度最小化來延長樹的生命周期。

上面所述算法均為集中式算法，其對節點運算能力要求高，通信開銷大，不適用于客觀環境極為惡劣的應用場景。而分布式算法的運算復雜度低，其通信開銷遠比集中式算法低，適用于網絡動態性很高的應用場景。隨機路由[12]和最近提出的LMST[13]是2種典型的分布式數據收集算法。

隨機路由的基本思想如下。首先由Sink節點廣播建樹消息。鄰居節點接收到此消息后，將消息內容重設，然后繼續廣播修改過的建樹消息。依此類推，只要網絡是連通的，則在建樹消息傳播一段時間后，1棵數據收集樹便建立起來。通過建樹消息中的控制參數，隨機路由可以構建最少跳數的數據收集樹。然而，其沒有對各個節點進行均衡控制，很容易產生能耗瓶頸節點，會明顯縮短網絡的整體生命周期。

LMST(local minimum spanning tree)算法是1個基于隨機路由的分布式改進算法。它利用節點間距離和通信能耗之間的關系對數據收集樹進行調整，以達到減少能量開銷進而延長網絡生命周期的目的。此算法在建立局部最小生成樹時，節點間至少需要進行2次消息交換，其后還要進行多次控制交互，所以，其通信開銷比較大。并且由于需要獲取各節點間鏈路能耗，必須知道各節點的坐標信息，這必然也會增大通信開銷。雖然LMST算法可以使得收集樹節點的度接近最小，從而在節點能對感知數據完全聚合的情形下，達到傳感器網絡的生命周期理論上界。這里的度是指節點在樹中的孩子數。但LMST算法網絡延遲性能很差，完全無法保證感知數據傳輸的實時性要求。

針對上述問題，本文作者提出1種DBEGA算法。其基本過程是：先隨機選擇1個節點作為臨時基站，再以此節點為根節點隨機生成1顆最少跳數的初始數據收集樹，然后，利用分布式方法對每個節點的度進行優化調整，在網絡延遲和生命周期間取得一個較好的平衡。算法在運行過程中的計算和通信開銷都較小，適用于網絡拓撲因客觀環境的影響而經常變化的應用場景。

2 網絡模型和問題描述

2.1 網絡模型

在1個面積為×的正方形區域內隨機布撒個傳感器節點，這樣形成的傳感器網絡可以用1個連通的無向圖()來表示。其中：為節點集合，{1,2, …,v}；；1,2, …,v為傳感器節點；為中邊的集合。假如節點v和v都在對方的通信半徑之內，則邊(vv)∈，為邊的數量。假設網絡具備如下性質：

1) 整體網絡是連通的，節點在部署后不再移動。

2) 節點無法進行能源補充，且初始能量可以互不相同。

3) 節點之間利用已有的同步算法進行了毫秒級精度的時間同步[14]。

不失一般性，假設節點在發射和接收數據時的功率固定，用t表示發射1 bit數據需要的能量，r表示接收1 bit數據需要的能量。同時假定網絡擁有較好的擁塞控制策略，可避免數據在傳輸過程中發生擁塞和重傳。

2.2 相關定義

本文所研究的無線傳感器網絡中，節點會對感知數據進行完全聚合(fully aggregate)[15?16]，即在1輪數據收集過程中，每個非葉節點會接收多個來自孩子節點的長度為bit的數據包，然后與自己產生的bit數據進行聚合，最終生成1個長度也為bit的聚合數據包發送給父親節點。參考文獻[4]，給出以下定義。

定義1 輪。是指所有傳感器節點收集1次數據，并將數據傳送到Sink節點所要耗費的時間，不管此時間要持續多久。

定義2 節點生命周期。是指節點v在1棵收集樹中存活的輪數。用(v)表示節點剩余能量，用表示1個給定的閥值。當節點能量小于時，將無法完成1輪的數據收集任務，因此，可以用(v)＞來判斷節點是否存活(若(v)＞，則節點存活，反之，則節點死亡)。節點生命周期可用下式計算：

其中：為節點每輪感知數據的平均長度(單位為bit)；(v)表示節點v在樹中的度數。

定義3 樹的生命周期。是指在數據收集過程中，第1個死亡的節點所經歷的輪數，就是樹的生命周期。可用下式表示：

樹的生命周期可等同為網絡的生命周期。

定義4 最優樹。就是所有數據收集生成樹中生命周期最長的那棵樹，可表示為

式中：為指網絡中任意1棵生成樹；S()為中生成樹的集合。

定義5 瓶頸節點。是指收集樹中最早耗盡能量的節點，其生命周期就相當于樹的生命周期。

2.3 問題描述

多跳無線傳感器網絡的延遲主要受樹的深度和樹中節點的孩子數量等因素的影響，其中樹深對延遲的影響最大[4]，因此，在基于樹的數據收集算法中，生成1棵深度最小的數據收集樹，會使網絡整體延遲近似于最短。網絡中節點數等于樹中各層節點孩子的總和，即

由于r和t是固定的，只有(v)可以調節，因此，可以將其作為主要的優化目標。為了簡化表達，對式(5)進行等價變換：

其中：=t/r?1。根據式(6)，在完全聚合的情況下，節點在生成樹中的度數直接與整個網絡的生命周期相關，即節點的平均度數越小，網絡生命周期越大。然而，根據式(3)，當數據收集樹的節點平均度數最小時，網絡生命周期最大，同時樹的深度也最大。所以，網絡延遲的縮短和生命周期的延長是互相矛盾的，不可能同時實現。

本文針對上述問題，提出1種分布式的算法DBEGA，在保證延遲受限的前提下，盡可能地平衡各節點的度數，使得網絡生命周期盡可能地延長。此外，DBEGA具有運算和通信開銷低的特點，在客觀環境極端惡劣的應用場景中，相比于集中式算法，具有更好的綜合性能。

3 DBEGA的設計和分析

分布式算法只能利用局部信息來達到優化目標，同時要盡量減少通信開銷。所以，需要找到合適的網絡參數和控制方法來進行有效平衡。

3.1 DBEGA算法的描述

文獻[4]指出，在聚合收集情形下，節點在收集樹中的度數與節點能耗成正比關系，即收集樹中的節點平均度數越小，樹的生命周期越長。可以用節點孩子數代替度數，作為算法運行的控制參數。在這種情況下，本文算法所要解決的問題實際上是在1棵已生成的最少跳數數據收集樹中，通過一定的優化調整使每個節點的度盡量地小，從而達到延長網絡生命周期的目的。

這里采用1種時間片輪轉的方法來減少算法運行過程中節點間的通信開銷。其基本思想是：為每個節點分配唯一的時間片，使得各節點在運行算法時不會互相干擾，如此能大大減少控制消息的發送和接收，從而達到降低通信開銷的目的。為了保證每個節點分配到的時間片是唯一的，可以在節點布撒之前，為每個節點設定1個唯一的整數(若為100個節點，則整數范圍為0~99，以此類推)，通過這個整數來保證每個節點分配到的時間片的唯一性。

目前無線傳感器節點的理論傳輸速度普遍可達250 kbit/s[17?21]。對于中等規模的無線傳感器網絡，節點地址可用16 bit的短地址表示，加上一些必要的標志位和網絡參數信息，協議控制幀的長度可控制在32~64 bit之間，如此可保證節點間控制幀的交互可在1 ms內完成。所以，在本文算法中，將時間片長度設定為1 ms。

用1個例子直觀地說明DBEGA算法的效果。圖1所示為數據收集算法生成樹的例子示意圖，其中：圖1(a)所示為1棵隨機路由生成樹，三角形灰色點為Sink節點，灰色圓點為瓶頸(負載)節點，因為其度數最大(度數為7)；圖1(b)所示為經由算法DBEGA優化后的生成樹。從圖1可以看出：灰色圓點的度數已降低為4，則根據定義2和定義3，圖1(b)所示的生命周期為圖1(a)所示生命周期的2倍。由此可知：優化的關鍵是要將瓶頸節點的孩子節點合理調整到非瓶頸節點上。

(a) 隨機路由生成樹；(b) 優化后的生成樹

DBEGA算法的基本步驟如下。

1)隨機選取1個節點作為臨時基站，同時，每個節點收集其鄰居節點信息，然后利用隨機路由，以臨時基站作為根節點，構造最少跳數的初始數據收集樹。各節點要獲取其所有鄰居節點的編號、每個鄰居節點的孩子數以及自身在樹中的層數。

2) 除初始樹的第1層節點外，為剩下的每個節點分配互不干擾的時間片。

3) 在每個時間片內，節點運行優化調整算法。具體過程為：在上層鄰居節點中，選取孩子數(可以將鄰居節點數也同時考慮)最小(這個值要比當前父節點的孩子數至少小2)的那個節點作為新的父親節點。若選取了新的父親節點，則向新舊父親節點發送確認信息；若新舊父親節點收到了確認信息，則要廣播1個更改信息，通知其鄰居節點修改與其相關的孩子數量。

4) 當每個節點的調整時間片運行完畢時，1顆優化后的數據收集樹構造完成，開始進行數據收集工作。

5) 當有節點死亡或經過幾輪數據收集后，重啟算法過程。

3.2 DBEGA算法分析

對于DBEGA的時間開銷，把它分為3個階段進行分析：一是鄰居信息收集階段，設節點數為，此階段所花時間一般會預設為1個常數T，大小與呈線性正比關系(復雜度為())，單位為秒級；二是隨機路由階段，所花時間S與呈線性正比關系(復雜度為())，單位也為秒級；三是樹調整階段，時間片長度為1 ms。由算法過程可知，此階段所用時間為(?1)(為數據收集樹的高度)，將其除以1 000，單位也化為ms級。綜上所述，算法的整體時間消耗為()。

DBEGA的通信開銷相當小，根據其算法過程，每個節點只需要收集1跳內的鄰居節點信息，然后只需有限的幾次控制交互就能達到算法運行的目的。完成這些動作所需能耗與節點在一輪數據收集中所用能耗相比，可以忽略不計。

為了進行比較，這里分析集中式算法MILD的通信開銷。MILD的算法過程分為2個階段：首先為信息收集階段。在此階段中，各節點是沿初始收集樹將所需信息傳送到Sink節點。假設d-表示節點的子孫節點數，地址和相關信息數據包長度為64 bit，則節點通信開銷為64rd+64t(d+1)。第2個階段是Sink節點進行運算后，要將優化樹傳播到各節點。假設優化樹用數組形式存儲，數組單元長度為16 bit，代表節點數量，則在此過程中，各節點的通信開銷為16(?1)(r+t)。可見：在MILD的整個算法運行過程中，節點的通信能耗與網絡節點數量成正比關系，其遠大于DBEGA算法中的節點通信能耗。此外，可推知MILD算法中，Sink節點的通信能耗為64r+16(?1)t。可見：Sink節點的通信開銷也與網絡節點數呈正比關系，在客觀環境極為惡劣的應用場景中，由各節點輪流擔任臨時Sink。若使用MILD算法，則過高的通信開銷會使擔任臨時Sink的節點過早耗盡能量而死亡，而使用本文提出的DBEGA算法能很好地解決這個問題。

3.3 DBEGA與LMST的對比分析

在感知數據完全聚合的情況下，LMST算法的網絡生命周期性能已接近理論最優上界，但這是以增大網絡延遲性能為代價的。

圖2所示為算法DBEGA和LMST的生成樹示例。圖2(b)所示為LMST算法的數據收集生成樹，與圖2(a)所示的DBEGA數據收集生成樹相比，其節點最大度數為2，后者的節點最大度數為4。由定義2和3可知：在圖2中，LMST算法的網絡生命周期為DBEGA網絡生命周期的3倍；然而，LMST算法生成樹的深度也為DBEGA的3倍。由前面分析，無線傳感器網絡延遲與數據收集樹的深度呈正比關系，所以，LMST的網絡延遲大大高于DBEGA的網絡延遲。

(a)DBEGA生成樹；(b) LMST生成樹

LMST算法是專為相關數據收集而設計的，它的側重點是盡量減少每個節點的度數，并不對數據收集生成樹的深度進行任何限制。雖然它的網絡生命周期性能很理想，但會導致網絡延遲較高，不適用于對實時性有要求的應用場景。

4 模擬實驗

基于NS2(版本號2.33)進行仿真以評價所提出算法的性能。為了驗證算法的擴展性和有效性，以節點密度和Sink節點的位置為可變參數對實驗場景進行設置，具體如下所示：區域面積為100 m×100 m；節點數量為100，200，300和400個；節點最大通信距離為20 m。節點的數據產生率為 1 000 bit/輪。為了使所有算法能進行公平對比，節點均采用固定發射功率，發送能耗t大約是接收能耗r的 2倍，即t=2r，r=50 nJ/bit[4]。因為路由構造和網絡調整時的控制通信開銷可以獨立分析，所以，進行模擬實驗時，只關注數據收集時的通信能耗和樹的生命周期。此外，節點對感知數據進行完全聚合。實驗結果是算法執行20次后的平均值。

4.1 選取中心節點作為臨時Sink的各算法對比

圖3所示為臨時基站處于區域中央時各算法在不同節點數情況下的網絡生命周期對比曲線。在模擬實驗中，DBEGA算法的生命周期無論在何種節點密度下都比隨機路由的長，平均生命周期提高27%。MILD是梁俊斌等[4]提出的較優秀的延遲受限集中式算法，它的生命周期要高于DBEGA，大約為DBEGA的1.6倍。但MILD算法的時間復雜度要遠比DBEGA的復雜度高[4]，在節點運算能力受限以及網絡拓撲經常變化的情況下，MILD算法難以得到實際應用，此時，DBEGA可以作為MILD的理想替代算法。

算法：1—MILD；2—DBEGA；3—Random；4—LMST

從圖3可見：LMST算法的生命周期提高，優于MILD算法，而且當節點密度變化時，其性能損失也很小，基本上已達理論最優上界。但LMST是通過增大網絡延遲來獲得生命周期性能的最優化，圖4所示曲線很好地說明了這一點。數據收集樹的深度越大，網絡延遲也就越大。從圖4可看出：LMST算法生成樹的深度要明顯比其他3種算法的深度高，而且隨著節點密度的增加，這種差距也顯著增大；當區域內節點數量為400時，LMST的數據收集樹深度為其他3種算法的6倍，所以，它完全不適用于延遲受限的應用場景。

圖4所示為不同算法生成樹的深度對比曲線。從圖4可見：DBEGA算法的數據收集樹深度相對最低，因為它是以最少跳數為控制參數來構造數據收集樹，這能最優化樹深。所以，綜合來說，在延遲受限的應用場景中，DBEGA是一種適用性和實用性都很強的算法。

1—MILD；2—DBEGA；3—Random；4—LMST

4.2 選取邊緣節點作為臨時Sink的各算法對比

為驗證算法的有效性和擴展性，從區域邊緣選取臨時Sink節點進行模擬實驗。

圖5所示為臨時基站處于區域邊緣時各算法在不同節點數情況下的網絡生命周期對比曲線。當臨時Sink處于區域邊緣時，與隨機路由相比，DBEGA的生命周期增加得更加明顯，其平均增長比達33%。這是因為在區域的邊緣，節點自身的鄰居節點數較少，對于沒有任何負載均衡機制的隨機路由更容易產生度數很大的瓶頸節點，從而使其生命周期進一步降低。在此情況下，MILD算法的生命周期也受到影響，使得DBEGA的周期接近于MILD算法的65%。

算法：1—MILD；2—DBEGA；3—Random；4—LMST

圖6所示為不同算法生成樹的深度對比曲線，LMST算法的生命周期性仍是最長的。但從圖6可看出：其數據收集樹的深度依然很大，且隨著節點密度的增加而呈線性增加，平均高出其他3種算法的4倍以上。

算法：1—MILD；2—DBEGA；3—Random；4—LMST

Fig .6 Comparison of different algorithms spanning tree heights when sink node is in edge region

綜上所述，DBEGA算法在網絡延遲和生命周期間取得了有效平衡，且時間復雜度低，通信開銷小，與其他算法相比，特別適用于延遲受限、Sink節點能力受限且網絡拓撲動態變化大的應用場景。

5 結論

1) 所提出的分布式數據收集算法(DBEGA)能很好地應用于戰場監控、惡劣環境監測等網絡動態性高的場景中。DBEGA通過為每個節點分配單獨時間片，大大減少了節點間通信開銷，同時也大大降低了算法復雜度，易于在計算性能有限的無線傳感器節點上進行部署。

2) DBEGA算法是基于最少跳數生成樹對網絡生命周期進行優化，能有效抑制網絡延遲，滿足某些實時性要求高的應用場景。

3) DBEGA在保證網絡延遲受限的前提下，與隨機路由相比，網絡生命周期提高20%以上。

[1] Rezaei Z, Mobininejad S. Energy saving in wireless sensor networks[J]. International Journal of Computer Science & Engineering Survey, 2012, 3(1): 23?37.

[2] Jr Simplfcio M A, Barreto P S L M, Margi C B, et al. A survey on key management mechanisms for distributed wireless sensor networks[J]. Computer Networks, 2010, 54(15): 2591?2612.

[3] Kwon S, Kim J, Kim C. An efficient tree structure for delay sensitive data gathering in wireless sensor networks[C]// O’Conner L. Proceedings of the IEEE 22nd International Conference on Advanced Information Networking and Applications. Washington D C, USA: IEEE Computer Society, 2008: 738?743.

[4] 梁俊斌, 王建新, 陳建二. 在傳感器網絡中構造延遲限定的最大化生命周期樹[J]. 電子學報, 2010, 38(2): 345?351. LIANG Junbin, WANG Jianxin, CHEN Jianer. On the construction of a delay-constrained maximum lifetime tree in wireless sensor networks[J]. Acta Electronic Sinica, 2010, 38(2): 345?351.

[5] Goyal D, Tripathy M R. Routing protocols in wireless sensor networks: A survey[C]// Guerrero J E. 2012 Second International Conference on Rohtak. Haryana, India: IEEE Computer Society, 2012: 474?480.

[6] Shih E, Cho S H, Ickes N, et al. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks[C]// Rose C. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. New York, USA: ACM, 2001: 272?287.

[7] Akyildiz I F, Su W Y, Sankarasubramaniam Y, et al. Wireless sensor networks: A survey[J]. Computer Networks, 2002, 38(4): 393?422.

[8] Oliveira L M, Rodrigues J J. Wireless sensor networks: A survey on environmental monitoring[J]. Journal of Communications, 2011, 6(2): 143?151.

[9] Tan H O, Korpeoglu I. Power efficient data gathering and aggregation in wireless sensor networks[J]. SIGMOD Record, 2003, 2(4): 66?71.

[10] LIANG Weifa, LIU Ruzhen. Online data gathering for maximizing network lifetime in sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(1): 2?11.

[11] Wu Y, Fahmy S, Shroff N B. On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm[C]// Meril D. The 27th Conference on Computer Communications. Phoenix, AZ, USA: IEEE, 2008: 1013?1021.

[12] Han K H, Ko Y B, Kim J H. A novel gradient approach for efficient data dissemination in wireless sensor networks[C]// Matsunaga S. Vehicular Technology Conference 2004. Los Angeles, USA, 2005: 2979?2983.

[13] Tan H O, Korpeoglu I, Stojmenovic I. Computing localized power-efficient data aggregation trees for sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(3): 489?500.

[14] Sami M L, James M C. Time synchronization in wireless sensor networks: A survey[C]// Conrad J. IEEE SoutheastCon 2010. Concord: NC, USA: IEEE, 2010: 242?245.

[15] Ozdemir S, Xiao Y. Secure data aggregation in wireless sensor networks: A comprehensive overview[J]. Computer Networks, 2009, 53(12): 2022?2037.

[16] JI Shouling, HE Jing, PAN Yi. Continuous data aggregation and capacity in probabilistic wireless sensor networks[J]. Journal of Parallel and Distributed Computing, 2013, 73(6): 729?745.

[17] Francesco M D, Anastasi G, Conti M. Reliability and energy-efficiency in IEEE 802.15.4/ZigBee sensor networks: An adaptive and cross-layer approach[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(8): 1508?1524.

[18] Martalo M,Buratti C, Ferrari G, et al. Clustered IEEE 802.15.4 sensor networks with data aggregation: Energy consumption and probability of error[J]. Wireless Communications Letters, IEEE, 2013, 2(1): 70?73.

[19] Hagkighi M S, YANG Xiang, Varadharajan V, et al. A stochastic time-domain model for burst data aggregation in EEE 802.15.4 wireless sensor networks[J]. IEEE Transactions on Computers, 2015, 64(3): 627?639.

[20] Wang L H, Chen T Y, Lin K H. Implementation of a wireless eca acquisition soc for IEEE 802.15.4 (ZigBee) application[J]. IEEE Journal of Biomedical and Health Informatics, 2015, 19(1): 247?255.

[21] Amaro J P, Cortes?o R, Ferreira F J T E, et al. Device and operation mechanism for non-beacon IEEE 802.15.4/ZigBee nodes running on harvested energy[J]. Ad Hoc Networks, 2015, 26(1): 50?68.

Distributed delay-bounded energy-efficient algorithm for data gathering in wireless sensor networks

CHEN Ling, KUI Xiaoyan, ZHANG Shigeng, WANG Jianxin

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

The centralized data gathering algorithms are difficult to be used in the high dynamic wireless sensor networks. For solving the problem, a distributed delay-bounded energy-efficient data gathering algorithm (DBEGA) was proposed, and a delay-bounded data gathering tree was constructed. DBEGA algorithm involves two steps. In the first step, the minimum hop count tree was constructed in a distributed manner for meeting the requirements of being delay-bounded. In the second step, DBEGA divided a specific length of time intoequal-length independent time slices and these time slices were uniquely assigned to each node. So an undisturbed environment was created for every node to adjust the load of nodes in the generated tree to balance energy consumption of different nodes, which effectively extended the lifetime of the network. In the adjustment, both the number of children of a node and their residual energy were considered. The results show that DBEGA achieves better tradeoff between delay and network lifetime than LMST algorithm, and it can prolong the lifetime by 20%.

wireless sensor networks; data gathering; spanning tree

10.11817/j.issn.1672-7207.2015.05.013

TP301

A

1672?7207(2015)05?1655?08

2014?06?12；

2014?08?21

國家自然科學基金重點資助項目(61232001)；國家自然科學基金面上資助項目(61472449)；國家留學基金資助項目(2015[3012])；湖南省自然科學基金資助項目(2015JJ4077) (Project(61232001) supported by the Key National Natural Science Foundation of China; Project(61472449) supported by the General Program of the National Natural Science Foundation of China; Project(2015[3012])supported by China Scholarship Council; Project(2015JJ4077) supported by the Natural Science Foundation of Hunan Province, China)

奎曉燕，博士，副教授，碩士研究生導師，從事無線傳感器網絡數據收集協議的研究；E-mail: xykui@csu.edu.cn

(編輯 陳燦華)