無線傳感器網絡上數據聚集及調度研究綜述

第3卷第4期2013年8月智 能 計 算 機 與 應 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.4Aug.2013

收稿日期：2013-04-24

基金項目：國家自然科學基金重點項目（61033015）。

作者簡介：于博（1985-），男，黑龍江黑河人，博士研究生，主要研究方向：無線傳感器網絡、算法設計；

李建中（1950-），男，黑龍江哈爾濱人，教授、博士生導師，主要研究方向：數據庫、無線傳感器網絡、海量數據計算等。

無線傳感器網絡上數據聚集及調度研究綜述

于博， 李建中（哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001）摘要：無線傳感器網絡是近年來倍受關注的熱點研究領域，綜合了無線通信技術、微電子技術、嵌入式技術、傳感器技術等，具有廣闊的應用前景。數據聚集是無線傳感器網絡上一項基礎而重要的操作，被研究者們所廣泛關注，也涌現出了很多研究工作?？偨Y了近年來無線傳感器網絡上的數據聚集以及數據聚集調度方向的研究工作，討論了現有工作的內容和需要進一步研究的方向，并提供了廣泛的參考文獻。

關鍵詞：無線傳感器網絡； 數據聚集； 調度

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）04-0005-05

Survey on Data Aggregation and Scheduling in Wireless Sensor Networks

YU Bo， LI Jianzhong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）

Abstract：Wireless sensor network is a research area with many hot research topics， which is widely concerned in recent years. Wireless sensor network integrates the technology of wireless communication， microelectronics， embedded system， sensing etc.， and provides significant application perspective. Data aggregation is an essential and important operation in wireless sensor networks， which is widely concerned by researchers， and there are also large amounts of research work on data aggregation. This paper introduces and summarizes the research work on data aggregation and aggregation scheduling in wireless sensor networks. This paper also discusses the existing solutions and the possible future work， and provides with plenty of references.

Key words：Wireless Sensor Networks； Data Aggregation； Scheduling

1無線傳感器網絡的背景和意義

無線傳感器網絡是近年來引起國內外廣泛關注的新興前沿熱點研究領域，綜合了無線通信技術、微電子技術、嵌入式計算技術、傳感器技術等。無線傳感器網絡通過各種低成本、低功耗、多功能的微型傳感器協調工作、有效感知并收集監測環境或監測對象的信息，再通過無線自組織通信網絡以多跳傳輸方式將信息傳送到基站或終端用戶，從而形成了一種新的信息獲取及處理模式。這是信息感知和采集的一場革命，是繼互聯網后將會對二十一世紀人類生活方式產生重大影響的熱點技術?；ヂ摼W構成了邏輯上的信息世界，改變了人類的溝通和交流的方式，而無線傳感器網絡則是將邏輯上的信息世界與客觀上的物理世界融合在一起，徹底改變了人類與自然界的交互方式。

無線傳感器網絡具有十分光明的前景，因為其應用背景是極為廣闊的。在環境監測領域，無線傳感器網絡可以用于收集環境信息方面的參數，比如溫度、濕度、光強、二氧化碳濃度等。在軍事領域，無線傳感器網絡可以應用于戰地監測，用以對敵方軍事目標的跟蹤和定位、偵查敵方地形和布防等。在醫療衛生領域，無線傳感器網絡可以安裝在病人身上，用于監測病人的健康指標，比如心率和血壓等，以隨時了解被監護病人的病情。無線傳感器網絡還可以應用在工農業生產、建筑物健康監測、交通管理等眾多領域。如上所述，由于無線傳感器網絡的巨大應用價值，許多國家的軍事部門、工業界以及學術界都對無線傳感器網絡給予了高度關注，使其成為當前計算機網絡領域的一個重要的研究熱點。

在無線傳感器網絡的許多應用中，網絡中的傳感器節點獲取的感知數據需要進行收集并加以分析。然而，大量的感知數據全部都傳輸到無線傳感器網絡的基站則會消耗巨大的能量，在實際應用中是無法做到的。因此，研究者們提出了數據聚集的策略，旨在削減網絡中通過無線傳輸的數據量，同時獲得無線傳感器網絡覆蓋區域的某些物理屬性的聚集值，這是對物理世界的一個粗粒度的簡約描述。數據聚集是無線傳感器網絡上的一項重要操作，近年來也受到了研究者們廣泛的關注[1]。無線傳感器網絡上的數據聚集不同于傳統的有線和無線網絡上的數據聚集，原因在于無線傳感器節點的能量、帶寬、計算及存儲能力都非常有限，所以基于其上的數據聚集更注重考慮能量的節省和通信的開銷，這些都為無線傳感器網絡上的聚集研究帶來了新的挑戰。因此，無線傳感器網絡上數據聚集策略的研究是一個帶有挑戰性的前沿研究領域，具有重要的理論和實際意義。

1.1無線傳感器網絡概述

無線傳感器網絡是由一組低成本、低功耗的無線傳感器節點通過自組織的方式形成的無線網絡，其目的是協同感知、采集和處理無線傳感器網絡覆蓋區域范圍內感知對象的信息，并發布給觀察者[2-4]。通常每個傳感器節點是由電源、感知部件、嵌入式處理器、存儲器、通信部件和軟件等幾個部分組成。其中，電源可為傳感器節點提供正常工作所必需的能源。感知部件用于感知和獲取物理世界的屬性信息，并將其轉化為數字信號。嵌入式處理器部件負責協調傳感器節點各部分的有序工作，比如對感知部件獲取的信息進行處理、控制感知部件以及電源的工作模式等。存儲器負責存放傳感器節點需要用到的程序和數據。通信部件負責與其他傳感器節點或用戶進行通信。軟件則是為傳感器節點提供軟件支持，包括嵌入式操作系統、嵌入式數據管理系統等。

無線傳感器節點、感知對象和觀察者是無線傳感器網絡的三個基本要素[5]。傳感器網絡是傳感器節點之間、傳感器節點與觀察者之間的通信方式，用于在傳感器節點與觀察者之間建立通信路徑。協同感知、采集、處理及發布感知信息是無線傳感器網絡的基本功能。觀察者是無線傳感器網絡的用戶，是感知信息的接受者和應用者。觀察者可以是人、計算機或其他設備，觀察者可以主動地收集、查詢傳感器網絡獲取的感知信息，也可以被動地接收傳感器網絡發布的感知信息。

具體地講，一個典型的無線傳感器網絡是由多個無線傳感器節點、一個或多個基站、互聯網或通信衛星、任務管理節點等部分有機組成。無線傳感器節點依靠無線方式與其他節點進行通信，節點可以通過多次無線傳輸 （又稱多跳傳輸） 將感知數據送達目標節點。無線傳感器節點以此方式形成了一個自組織的無線網絡，同時網絡中的基站也可以通過多跳傳輸的方式將數據和控制信息傳送到各個傳感器節點上，而基站又可以通過互聯網或外部網絡將感知數據傳輸至任務管理節點 （即觀察者）。在數據聚集中，無線傳感器網絡中的所有或者部分傳感器節點將感知數據首先在網內進行聚集，然后再以多跳傳輸的方式將聚集結果傳送到基站。第4期于博，等：無線傳感器網絡上數據聚集及調度研究綜述智能計算機與應用第3卷

1.2無線傳感器網絡的特點與挑戰

與傳統的網絡不同，無線傳感器網絡具有很多鮮明的特點，而這些特點也相應地帶來了一系列的挑戰性問題，在此可簡要總結為以下幾個方面。

（1）節點能量有限。目前現有的大多數無線傳感器節點通過電池供電，而有限的電源能量則限制了節點的生命周期，網絡中的傳感器由于電源能量的原因經常失效或廢棄，這已經成為阻礙無線傳感器網絡實際應用的一個重大問題[2]。無線傳感器節點傳輸信息比執行計算操作更消耗電能，據研究，無線傳感器傳輸1位信息所需的電能足以執行3 000條計算指令[5]。因此，可以認為傳感器節點的主要能耗在于無線通信，而執行計算的能耗則可以忽略不計。

（2）節點的計算和存儲能力有限。無線傳感器網絡中的節點都具有嵌入式處理器和存儲器。這些傳感器節點都具有計算能力，可以完成一些信息處理工作。然而，由于嵌入式處理器和存儲器的能力和容量都十分有限，傳感器的計算能力也很有限。因此，如何利用大量的能力有限的無線傳感器節點進行協同分布式信息處理，也成為一個重要挑戰。

（3）節點的通信能力有限。由于無線傳感器節點之間以無線方式通信，無線傳感器網絡覆蓋區域內的自然環境將嚴重影響節點間的通信質量。無線傳感器節點之間的常用通信頻段高、帶寬窄，致使通信半徑一般只有幾十米，且數據傳輸速率比其他高速無線網絡更低。同時，由于傳感器節點采用無線通信技術，常常會出現信號碰撞的情況，這也會消耗網絡的能量。因此，無線通信的干擾對感知數據計算的影響也是研究中需要考慮的。在考慮無線干擾的情況下，設計分布式感知數據的無沖突計算策略又是一個挑戰。

（4）網絡規模巨大。傳感器網絡中傳感器節點密集，數量巨大，可能達到幾百、幾千甚至更多。此外，傳感器網絡可以分布在廣袤的地理區域。傳感器數量大、分布廣的特點使得網絡的維護將十分困難，那么如何在大規模傳感器網絡背景下完成分布式感知數據的計算值得加大力度認真研究。

（5）網絡動態性強。在某些應用背景下，傳感器網絡會具有很強的動態性。無線傳感器網絡中的傳感器、感知對象和觀察者這三要素都可能具有移動性，并且經常有新節點加入或已有節點失效，也或者是鏈路失效。針對這種網絡動態性，傳感器網絡上的感知數據計算機制必須具有自調整和自恢復性，比如失效節點和新加入節點的處理，移動節點參與計算機制等問題。

（6）以數據為中心，感知數據流巨大。在無線傳感器網絡的現實應用中，每個傳感器節點需要對感知對象進行實時監測并產生感知數據。隨著時間的累積，大規模的傳感器網絡中常常會產生巨大的數據流匯聚到基站。因此，不同于傳統網絡“以傳輸數據為目的”的特點，無線傳感器網絡的特點是以數據為中心[4]。基于此，高效的分布式流數據處理、查詢和分析方法已然成為研究者們面臨的一大重要挑戰。

2無線傳感器網絡上數據聚集的研究工作

數據聚集是無線傳感器網絡上的一個重要的基本操作，包括簡單的聚集操作如 MAX （最大值）、MIN （最小值）、SUM （求和）、COUNT （計數）、LOGIC AND （邏輯與）、LOGIC OR （邏輯或） 等，也包括復雜的聚集操作如AVERAGE （平均值）、MEDIAN （中位數）等。由于無線傳感器網絡的能源有限，網內聚集[6]技術得到了研究者們的高度重視和普遍研究。網內聚集指的是在網絡內部傳輸數據的過程中同時進行聚集操作，并不斷地傳輸中間聚集結果，再將最終的聚集結果傳輸到基站。由此可以極大地減少網絡中傳輸的數據量，節省了能量，同時減輕了網絡的數據傳輸負擔，降低了數據的傳輸延遲。下面，介紹無線傳感器網絡上有關數據聚集的代表性研究工作。

文獻[7]最早提出了無線傳感器網絡上的數據聚集操作，允許用戶向網絡提出簡單的、陳述性的查詢，并在網內高效執行。文獻[8]提出了一種數據聚集新機制，不僅支持簡單聚集查詢，而且支持復雜聚集查詢，如中位數等。

在無線傳感器網絡上數據聚集的研究工作絕大部分都可分為基于樹結構和基于聚簇兩種聚集模式。文獻[6-10]等皆是基于樹結構進行數據聚集，也是最常見的方式。文獻[11]研究了傳感器網絡上基于樹結構的聚集中如何提高數據采集率的問題。文獻[12]考察了傳感器網絡上最小化能量的聚集樹構造問題的復雜性并提出了相應的算法。基于聚簇的聚集模式則有以下重點成果。LEACH協議[13]基于聚簇實現網內的數據收集，每個簇頭負責收集本簇中所有節點的數據并將數據聚集后傳送到基站。文獻[14]針對LEACH協議的缺點，提出了PEGASIS協議。在該協議中，所有傳感器節點作為一個簇，全部節點的數據被傳送到簇頭，簇頭執行聚集操作并把結果傳輸到基站。為了保證負載平衡，PEGASIS協議輪轉地選擇簇頭。文獻[15]在聚簇模式的傳感器網絡上研究了自適應的數據聚集機制。文獻[16]為傳感器網絡上的數據聚集與收集提出了一種分級的聚簇協議DEEG，通過優化能量消耗和平衡網內節點間的能量負載延長網絡生命周期。文獻[17]考慮了聚簇模式傳感器網絡上數據收集過程中簇間的負載平衡，以避免通信熱點的形成。

除了樹結構和聚簇兩種模式以外的數據聚集則有如下的矚目性工作成果。文獻[18]為無線傳感器網絡提出了新的網內聚集的策略Tributary-Delta，同時結合了樹結構和多路徑結構的優點。文獻[19]提出了無線傳感器網絡上的無結構數據聚集方法。

研究者們在傳感器網絡的數據聚集方面也開展了一些理論性研究工作。文獻[20]研究了無線傳感器網絡的密度對數據聚集的影響。文獻[21]研究了以數據為中心的路由對數據聚集的影響，并且從理論上給出了最優數據聚集問題的復雜性。文獻[22]給出了無線傳感器網絡上數據聚集、收集、選擇操作的復雜性分析。文獻[23]研究了無線傳感器網絡中有延遲約束的數據聚集，通過調度數據包傳輸來最小化數據聚集樹中節點的能量消耗，并考察了能量消耗與延遲之間的折中問題。

在無線傳感器網絡上數據聚集的算法技術研究方面，有如下坐標式的工作成果。文獻[24]為傳感器網絡上的數據聚集提出了一種啟發式算法，旨在降低時間延遲和能量消耗。文獻[25]為傳感器網絡上的數據聚集提出了一種基于位置信息的路由策略。文獻[26]研究了在大規模無線傳感器網絡中節點稀疏的情況下如何處理數據聚集問題，提出了傳感器節點自發建立優化傳輸路徑的方法，而且節省了聚集過程所用的能量。文獻[10]提出了模型驅動的數據獲取技術，并研究了如何平衡數據置信度與網絡中數據獲取開銷的方法。文獻[27]為避免重復計數，利用 synopsis 技術實現了傳感器網絡上的數據聚集。

無線傳感器網絡中數據聚集的評價性能指標一般包括能量開銷、網絡生命周期、聚集時間延遲、數據質量等，有很多研究工作考慮對上述的某項或某些項性能指標進行優化或平衡。文獻[28]從理論上給出了無線傳感器網絡上數據聚集時網絡的最大生命周期。文獻[29]將數據聚集和路由結合在一起提出了一種聚集機制，目標是最大化傳感器網絡生命周期。文獻 [30]研究了傳感器網絡上連續數據聚集時如何延長網絡生命周期的問題，考察了數據質量和能量開銷的基本平衡。文獻[31]為傳感器網絡上的分布式聚集操作提出了一種隨機策略，并考慮了能量開銷和聚集時間延遲的平衡。文獻[32]為節省傳感器網絡的能量，并針對低數據速率的傳感器網絡上的數據收集與聚集而設計了能量有效的協議。

無線傳感器網絡上數據聚集還有一些研究工作考慮了不同的應用需求和技術策略。例如，文獻[33]考慮了無線傳感器網絡中移動用戶收集數據的需求，通過動態更新數據收集樹結構給出了一種數據收集方法。文獻[34]考察了無線傳感器網絡上數據聚集的安全問題。文獻[35]研究了大規模無線傳感器網絡上的壓縮數據聚集問題，由此降低了網絡整體的通信開銷。

3無線傳感器網絡上數據聚集調度的研究工作

本節詳細介紹無線傳感器網絡上數據聚集調度方面的研究工作如下。

文獻[9]提出了一種同時支持傳感器網絡上廣播和聚集的啟發式算法。文獻[36]為由n個節點組成的傳感器網絡提出了一種分布式的隨機算法，其期望的延遲是O（logn）。該模型中有兩個假設，第一個是假設每個傳感器節點在發送數據后能夠檢測到是否發生沖突，第二個是假設傳感器節點可以無限制地調整其傳輸半徑。這兩個假設對硬件設計增加了很大的難度，而且第二個假設在大網絡規模下并不成立。文獻[37]為數據收集提出了一個無沖突的調度方法，目標是優化能量開銷和可靠性。

無線傳感器網絡上的數據聚集調度問題是指給定一個無線傳感器網絡的拓撲結構圖，為網絡中的所有節點產生相關的調度，每個節點的調度指定了該節點在哪個時間片將其數據傳輸給哪個節點，并且保證在數據聚集時所有節點均按照此調度進行數據傳輸，而不會發生沖突，同時最小化聚集時間。文獻[38]證明最小化聚集時間的數據聚集調度問題是NP-難的，并且提出了一個近似算法，基本思想是采用最短的路徑進行數據聚集。該算法的近似比為 （Δ-1），其中，Δ是網絡拓撲圖的最大頂點度。文獻[39]為解決最小化時間數據聚集調度問題給出了一個調度算法，聚集時間延遲的上界為23R+Δ-18，其中，R是網絡拓撲圖的半徑，Δ仍然是網絡拓撲圖的最大頂點度。然而，該算法不能保證返回的結果是網絡的一個無沖突的調度。文獻[40]給出了解決無線傳感器網絡上最小化時間的數據聚集調度問題的第一個分布式算法，之前的算法均是集中式的，而且在網絡拓撲變化的網絡中具有一定的局限性，同時也給出了聚集時間的理論上界。

文獻[41]為了進一步降低數據聚集調度問題的聚集時間延遲，給出了幾個集中式算法。這幾個算法的聚集時間上界分別為 15R+Δ-4，2R + O（logR） + Δ 和 （1 + O（logR/3√R））R，其中， R是關于基站的網絡半徑。文獻[42]提出了一種新的分布式數據聚集調度算法，改進了之前的工作，其聚集時間為16R +Δ-14。文獻[43]為最小化時間的數據聚集調度問題提出了一個分布式算法，進一步改進了之前工作的聚集時間，該算法的聚集時間不超過4R + Δ-2。文獻[44-46]研究了在物理干擾模型 （Physical Interference Model） 下無線傳感器網絡上最小化時間延遲的數據聚集調度問題，并給出了相應的算法。文獻[47]提出了最小化時間的分布式的數據收集調度算法，而數據收集要求傳感器網絡內的所有節點將數據傳輸到基站，并且數據包不能在網絡內部完成合并，因此在N個節點構成的傳感器網絡中數據收集的時間延遲下界是N 個時間片 （因為基站需要至少 N 個時間片來接收網絡中的 N個數據包）。文獻[47]提出的算法的時間延遲上界為max{3nk-1， N}，其中，nk是最大一跳子樹中的節點個數。注意，該算法是數據收集的調度算法，而非數據聚集的調度。

在無線傳感器網絡上的聚集調度問題還可以考慮一些特殊類型的無線傳感器網絡環境，比如周期輪轉模式的無線傳感器網絡、異構的混合無線傳感器網絡等，也可以將聚集調度工作延展到普通的無線網絡上，這些都是未來可以考慮的研究方向。

4結束語

目前，無線傳感器網絡已引起了研究者們前所未有的廣泛關注與重視，而數據聚集作為無線傳感器網絡中最基本、且最重要的操作則得到了深入的研究，得到了為數眾多的研究成果。在本文中，歸納并總結了數據聚集方向以及數據聚集調度方向已有的研究，并對可能的研究方向進行了簡要分析和闡述，希望能夠借此推動國內對數據聚集問題更大范圍和規模的研究。

參考文獻：

[1]RAJAGOPALAN R， VARSHNEY P K. Data-aggregation techniques in sensor networks： a survey[J]. Communications Surveys Tutorials， IEEE， 2006，8（4）：48–63.

[2]孫利民， 李建中， 陳渝， 等. 無線傳感器網絡[M]. 北京：清華大學出版社， 2005-07.

[3]李建中，高宏. 無線傳感器網絡的研究進展[J]. 計算機研究與發展， 2008，45（1）：1-15.

[4]崔莉， 鞠海玲， 苗勇， 等. 無線傳感器網絡研究進展[J]. 計算機研究與發展， 2005， 42（1）：163-174.

[5]李建中， 李金寶， 石勝飛. 傳感器網絡及其數據管理的概念、問題與進展[J]. 軟件學報， 2003， 14（10）：1717–1727.

[6]SHARAF M A， BEAVER J， LABRINIDIS A， et al. TiNA： a scheme for temporal coherency-aware in-network aggregation. MobiDe ’03， New York， NY， USA， ACM.2003： 69–76.

[7]MADDEN S， FRANKLIN M J， HELLERSTEIN J M， et al. Tag： A tiny aggregation service for ad-hoc sensor networks. ACM SIGOPS Operating Systems Review， 2002， 36（SI）：131–146.

[8]SHRIVASTAVA N， BURAGOHAIN C， AGRAWAL D， et al. Medians and beyond： new aggregation techniques for sensor networks. Sensys， New York，NY， USA， ACM， 2004： 239–249.

[9]ANNAMALAI V， GUPTA S K S， SCHWIEBERT L. On tree-based convergecasting in wireless sensor networks. WCNC， Washington， DC， USA， IEEE. 2003， 3：1942–1947.

[10]DESHPANDE A， GUESTRIN C， MADDEN S R， et al. Model-driven data acquisition in sensor networks. VLDB Endowment， 2004.

[11]INCEL O， KRISHNAMACHARI B. Enhancing the data collection rate of tree-based aggregation in wireless sensor networks. SECON’08. Washington， DC， USA， IEEE. 2008： 569–577.

[12]KUO T W， TSAI M J. On the construction of data aggregation tree with minimum energy cost in wireless sensor networks： Np-completeness and approximation algorithms. [C]∥INFOCOM， 2012 Proceedings IEEE，IEEE， 2012： 2591–2595.

[13]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks. HICSS ’00， Washington， DC， USA， IEEE Computer Society. 2000： 8020–8029.

[14]LINDSEY S， RAGHAVENDRA C S. PEGASIS： Power-efficient gathering in sensor information systems[C]∥ Proceedings of the IEEE Aerospace Conference， 2002， 3：1125–1130.

[15]CHEN H， MINENO H， MIZUNO T. Adaptive data aggregation scheme in clustered wireless sensor networks[J]. Computer Communications， 2008，31（15）：3579–3585.

[16]LIU M， CAO J， ZHENG Y， et al. An energy-efficient protocol for data gathering and aggregation in wireless sensor networks[J]. The Journal of Supercomputing， 2008， 43（2）：107–125.

[17]MANDALA D， DU X， DAI F， et al. Load balance and energy efficient data gathering in wireless sensor networks[J]. Wireless Communications and Mobile Computing， 2008，8（5）：645–659.

[18]MANJHI A， NATH S， GIBBONS P B. Tributaries and deltas： efficient and robust aggregation in sensor network streams[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data， SIGMOD ’05， New York， NY， USA， ACM. 2005： 287–298.

[19]KAI WeiFan， LIU Sha， SINHA P. Structure-free data aggregation in sensor networks[J]. Mobile Computing， IEEE Transactions on， 2007，6（8）：929–942.

[20]INTANAGONWIWAT C， ESTRIN D， GOVINDAN R， et al. Impact of network density on data aggregation in wireless sensor networks[C]//Distributed Computing Systems， 2002. Proceedings. 22nd International Conference on， Washington， DC， USA， IEEE. 2002： 457–458.

[21]KRISHNAMACHARI B， ESTRIN D， WICKER S B. The impact of data aggregation in wireless sensor networks. In ICDCS Workshops， Washington， DC， USA， IEEE.2002： 575–578.

[22]LI X Y， WANG Y， WANG Y. Complexity of data collection， aggregation， and selection for wireless sensor networks[J]. IEEE Transactions on Computers， 2011，60（3）：386–399.

[23]YU Y， KRISHNAMACHARI B， PRASANNA V K. Energy-latency tradeoffs for data gathering in wireless sensor networks. IEEE INFOCOM， Washington，DC， USA， 2004 ，1：244–255.

[24]UPADHYAYULA S， ANNAMALAI V， GUPTA S K S. A low-latency and energy-efficient algorithm for convergecast in wireless sensor networks[C]//IEEE Global Telecommunications Conference–GLOBECOM， Washington， DC， USA， IEEE. 2003 ，6：3525–3530.

[25]BEAVER J， SHARAF M A， LABRINIDIS A， et al. Location-aware routing for data aggregation in sensor networks. Geosensor Networks， 2004：189–209.

[26]GAO J， GUIBAS L， MILOSAVLJEVIC N， et al. Sparse data aggregation in sensor networks[C]// Proceedings of the 6th international conference on Information processing in sensor networks， New York， NY， USA， ACM. 2007： 430–439.

[27]NATH S， GIBBONS P B， SESHAN S， et al. Synopsis diffusion for robust aggregation in sensor networks[C]//Proceedings of the 2nd international conference on Embedded networked sensor systems， New York， NY， USA， ACM. 2004： 250–262.

[28]KALPAKIS K， DASGUPTA K， NAMJOSHI P. Maximum lifetime data gathering and aggregation in wireless sensor networks[C]//Proceedings of IEEE Networks， 2002，2：685–696.

[29]HUA Cunqing， YUM T SP. Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks[J]. IEEE/ACM Transactions on Networking， 2008，16（4）：892–903.

[30]TANG X， XU J. Optimizing lifetime for continuous data aggregation with precision guarantees in wireless sensor networks[J]. IEEE/ACM Transactions on Networking （TON）， 2008，16（4）：904–917.

[31]YE Z， ABOUZEID A A， AI J. Optimal stochastic policies for distributed data aggregation in wireless sensor networks[J]. IEEE/ACM Transactions on Networking， 2009，17（5）：1494–1507.

[32]WU Y， LI X Y， LIU Y， et al. Energy-efficient wake-up scheduling for data collection and aggregation[J]. IEEE Transactions on Parallel and Distributed Systems， 2010，21（2）：275–287.

[33]LI Z， LI M， WANG J， et al. Ubiquitous data collection for mobile users in wireless sensor networks[C]//INFOCOM， 2011 Proceedings IEEE， Washington， DC， USA， IEEE. 2011： 2246–2254.

[34]OZDEMIR S， XIAO Y. Secure data aggregation in wireless sensor networks： A comprehensive overview[J]. Computer Networks， 2009，53（12）：2022–2037.

[35]LUO C， WU F， SUN J， et al.Compressive data gathering for large-scale wireless sensor networks[C]//Proceedings of the 15th annual international conference on Mobile computing and networking， New York， NY， USA ACM， 2009： 145–156.

[36]KESSELMAN A， KOWALSKI D R. Fast distributed algorithm for convergecast in ad hoc geometric radio networks[J]. Journal of Parallel and Distributed Computing， 2006，66（4）：578–585.

[37]LEE H， KESHAVARZIAN A. Towards energy-optimal and reliable data collection via collision-free scheduling in wireless sensor networks[C]//The 27th Conference on Computer Communications. IEEE INFOCOM 2008.， Washington， DC， USA， 2008： 2029–2037.

[38]CHEN Xujin， HU Xiaodong， ZHU Jianming. Minimum data aggregation time problem in wireless sensor networks[C]//Proceedings of the First international conference on Mobile Ad-hoc and Sensor Networks， MSN’05， Berlin， Heidelberg， Springer-Verlag. 2005： 133–142.

[39]HUANG S C H， WAN P J， VU C T， et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C]// Proceedings of the 26th IEEE International Conference on Computer Communications. IEEE INFOCOM， 2007：366–372.

[40]YU B， LI J， LI Y. Distributed data aggregation scheduling in wireless sensor networks[C]// INFOCOM， 2009.

[41]WAN P J， HUANG S C H， WANG L， et al. Minimum-latency aggregation scheduling in multihop wireless networks[C]// Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing， MobiHoc ’09， New York， NY， USA， ACM. 2009： 185–193.

[42]XU X， WANG S， MAO X， et al. An improved approximation algorithm for data aggregation in multi-hop wireless sensor networks[C]// Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing， New York， NY， USA， ACM. 2009： 47–56.

[43]LI Y， GUO L， PRASAD S K. An energy-efficient distributed algorithm for minimum-latency aggregation scheduling in wireless sensor networks[C]// Proceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems， ICDCS ’10， Washington， DC， USA， IEEE Computer Society. 2010： 827–836.

[44]LI X Y， XU X， WANG S， et al. Efficient data aggregation in multi-hop wireless sensor networks under physical interference model[C]// Mobile Ad hoc and Sensor Systems， 2009. MASS’09. IEEE 6th International Conference on， Washington， DC， USA， IEEE. 2009： 353–362.

[45]LI H， HUA Q S， WU C， et al. Minimum-latency aggregation scheduling in wireless sensor networks under physical interference model[C]// Proceedings of the 13th ACM international conference on Modeling， analysis， and simulation of wireless and mobile systems， New York， NY， USA， ACM. 2010： 360–367.

[46]LI H， WU C， HUA Q S， et al. Latency-minimizing data aggregation in wireless sensor networks under physical interference model. Ad Hoc Networks， 2011.

[47]GANDHAM S， ZHANG Y， HUANG Q. Distributed minimal time convergecast scheduling in wireless sensor networks[C]//26th IEEE International Conference on Distributed Computing Systems. ICDCS 2006.，Washington， DC， USA， IEEE. 2006： 50-59.

[48]任豐原， 黃海寧， 林闖. 無線傳感器網絡[J]. 軟件學報， 2003：14（7）：1282–1291.

（上接第4頁）