支持ＱｏＳ的無線傳感器網(wǎng)絡數(shù)據(jù)聚合技術研究

摘要：結合數(shù)據(jù)聚合技術的特點，通過分析現(xiàn)有無線傳感器網(wǎng)絡的QoS研究，提出了數(shù)據(jù)聚合的三個QoS度量指標，即網(wǎng)絡生命周期、數(shù)據(jù)時延、數(shù)據(jù)質量，討論并分析了保證這些數(shù)據(jù)聚合QoS指標的關鍵技術，對于進一步深入研究無線傳感器網(wǎng)絡的數(shù)據(jù)聚合技術具有比較重要的參考價值。

關鍵詞：無線傳感器網(wǎng)絡；數(shù)據(jù)聚合；能耗；時延；數(shù)據(jù)質量；服務質量

中圖分類號：TP393； TP212； TP301.6文獻標志碼：A

文章編號：1001－3695(2008)01－0064－04

0引言

數(shù)據(jù)聚合是無線傳感器網(wǎng)絡中一種重要的節(jié)能技術[1，2]，即利用傳感器節(jié)點的本地計算和存儲處理能力，先對采集到的或接收到的其他傳感器節(jié)點發(fā)送的多個數(shù)據(jù)進行網(wǎng)內處理，消除冗余信息，然后再傳輸處理后的數(shù)據(jù)[3]。數(shù)據(jù)聚合技術可以減少無線傳感器網(wǎng)絡中傳輸?shù)姆纸M數(shù)量，減少分組的沖突概率，提高回傳探測結果的準確性，是目前無線傳感器網(wǎng)絡的一個研究熱點。

數(shù)據(jù)聚合技術最初的研究目標是如何節(jié)省能量，使網(wǎng)絡生命周期最大化。但是隨著圖像及視頻傳感器節(jié)點在無線傳感器網(wǎng)絡中的應用，如移動目標的實時跟蹤、緊急事件的實時觸發(fā)等，如何為這類應用提供一定的QoS支持[4，5]，保證回傳數(shù)據(jù)的時延、質量等，也逐漸成為數(shù)據(jù)聚合研究必須重點考慮的問題。由于無線傳感器網(wǎng)絡中的數(shù)據(jù)回傳通過節(jié)點間的協(xié)作完成，需要將多個節(jié)點采集到的數(shù)據(jù)回傳至sink節(jié)點，數(shù)據(jù)間存在大量的冗余，并且無線傳感器網(wǎng)絡用戶不關心單個傳感器節(jié)點采集到的數(shù)據(jù)，傳統(tǒng)網(wǎng)絡的端到端QoS協(xié)議和度量指標已不再適用。現(xiàn)有的數(shù)據(jù)聚合QoS研究大多是在無線傳感器網(wǎng)絡的能耗和數(shù)據(jù)傳輸時延或無線傳感器網(wǎng)絡的能耗和數(shù)據(jù)準確性上進行折中[6~10]，缺乏對支持QoS數(shù)據(jù)聚合技術的全面研究。對于什么是以數(shù)據(jù)為中心的數(shù)據(jù)聚合QoS度量指標，目前也沒有文獻給出準確定義。

1數(shù)據(jù)聚合的QoS度量指標

從網(wǎng)絡體系結構的角度看，數(shù)據(jù)聚合是一種介于應用層和網(wǎng)絡層之間的技術。因此希望從應用層和網(wǎng)絡層QoS度量指標的研究中，提出數(shù)據(jù)聚合的QoS度量指標。目前對如何度量無線傳感器網(wǎng)絡的QoS指標缺乏統(tǒng)一、明確的定義[4，5，11]。文獻[4]中提出使用四個集合性指標，即共同時延(collective latency）、共同丟包率(collective packet loss)、共同帶寬(collective bandwidth)及信息吞吐量(information throughput)，來度量無線傳感器網(wǎng)絡的QoS指標；雖然其體現(xiàn)了以數(shù)據(jù)為中心的特點，但并沒有給出每個指標的確切定義。文獻[5]分析了無線傳感器網(wǎng)絡支持QoS存在的難點問題，介紹了路由和MAC協(xié)議支持QoS的現(xiàn)狀，但是也沒有明確給出無線傳感器網(wǎng)絡QoS的度量指標。文獻[11]從用戶的角度提出四個QoS指標來描述無線傳感器網(wǎng)絡的性能，它們分別是節(jié)點密度、數(shù)據(jù)在空間/時間上的準確性/真實性、事件從產(chǎn)生到遞交至sink的時延、網(wǎng)絡的生命周期。通過綜合分析并結合數(shù)據(jù)聚合技術本身的特點，本文使用網(wǎng)絡生命周期、數(shù)據(jù)時延及數(shù)據(jù)質量三個以數(shù)據(jù)為中心的指標，作為度量無線傳感器網(wǎng)絡數(shù)據(jù)聚合QoS的指標。

1)網(wǎng)絡生命周期網(wǎng)絡生命周期是指無線傳感器網(wǎng)絡從部署到不能為用戶提供滿足要求數(shù)據(jù)的時間，與具體的無線傳感器網(wǎng)絡應用相關。該指標主要取決于系統(tǒng)的能耗，具體包括通信能耗、控制能耗（路由、拓撲及定位信息等的維護）、計算能耗（如聚合處理）等。數(shù)據(jù)聚合技術研究的主要目標就是節(jié)省能耗，使無線傳感網(wǎng)絡的生命周期最大化。由于無線傳感器網(wǎng)絡中節(jié)點通信的能耗比計算的能耗高幾個數(shù)量級[2]，數(shù)據(jù)聚合研究中通常使用網(wǎng)絡中總的通信次數(shù)來衡量無線傳感器網(wǎng)絡的總能耗。通過減少無線傳感器網(wǎng)絡中的通信次數(shù)來延長網(wǎng)絡的生命周期。

2)數(shù)據(jù)時延數(shù)據(jù)時延在不同的應用中有不同的定義，這里根據(jù)無線傳感器網(wǎng)絡中的不同數(shù)據(jù)傳遞模式來進行說明。無線傳感器網(wǎng)絡主要有基于用戶查詢的、事件觸發(fā)的及周期性數(shù)據(jù)采集三種數(shù)據(jù)傳遞模式[4]。數(shù)據(jù)時延在基于用戶查詢的應用中是指從用戶發(fā)出請求，至sink接收到無線傳感器網(wǎng)絡采集數(shù)據(jù)的時延；在事件觸發(fā)應用中是指從事件發(fā)生，至sink接收到事件相關數(shù)據(jù)的時延；在周期性數(shù)據(jù)采集中是指采集到數(shù)據(jù)，到將數(shù)據(jù)回傳至sink的時延。例如對于事件觸發(fā)類數(shù)據(jù)傳遞，數(shù)據(jù)時延可以是關于某事件的第一個數(shù)據(jù)產(chǎn)生，到最后一個數(shù)據(jù)回傳至sink的時延。數(shù)據(jù)時延對時間敏感型應用比較關鍵，主要由分組的傳輸時延、數(shù)據(jù)聚合前等待時延、數(shù)據(jù)聚合處理等時延組成。

3)數(shù)據(jù)質量數(shù)據(jù)質量是指sink接收到無線傳感器網(wǎng)絡采集數(shù)據(jù)的準確性，包括時間和空間上的粒度、發(fā)生事件后監(jiān)測到的概率等，與具體的無線傳感器網(wǎng)絡應用相關。數(shù)據(jù)質量受傳感器節(jié)點采集數(shù)據(jù)的精度、時間及位置信息等影響，還受數(shù)據(jù)傳輸中的錯誤及丟失分組、數(shù)據(jù)聚合中損失的信息等影響。

上述三個QoS指標雖然可以比較全面地反映應用對數(shù)據(jù)聚合的要求，但是鑒于無線傳感器網(wǎng)絡應用的多樣性，在實際中需要根據(jù)具體應用的特點靈活使用。另外，這三個指標不可能同時達到最優(yōu)，需要在應用中進行折中考慮。

2數(shù)據(jù)聚合支持QoS的關鍵技術

2．1網(wǎng)絡生命周期

為了使網(wǎng)絡生命周期最大化，數(shù)據(jù)聚合技術需要盡量降低無線傳感器網(wǎng)絡中的能耗。根據(jù)現(xiàn)有數(shù)據(jù)聚合技術在OSI模型中的不同層次，以下分別從應用層、網(wǎng)絡層和其他層的角度，說明數(shù)據(jù)聚合技術降低無線傳感器網(wǎng)絡能耗的方法。但需要說明的是，這種劃分不是絕對的，有的數(shù)據(jù)聚合技術也具有跨層的特點，需要根據(jù)應用的特點靈活使用。

2．1．1應用層數(shù)據(jù)聚合技術

無線傳感器網(wǎng)絡中的數(shù)據(jù)聚合一般是與應用相關的，應用層需要知道轉發(fā)數(shù)據(jù)分組的內容，從而判斷是否對相關的數(shù)據(jù)分組進行聚合及如何聚合。TAG[7]是無線傳感器網(wǎng)絡應用層數(shù)據(jù)聚合研究的一個典型實例。它是一種為TinyOS設計的通用聚合服務，支持周期性的數(shù)據(jù)查詢。用戶可以使用簡單的、描述性的方法發(fā)布查詢，系統(tǒng)則自動發(fā)布和高效執(zhí)行相關的查詢命令。TAG中執(zhí)行數(shù)據(jù)聚合的過程為傳感器節(jié)點采集的數(shù)據(jù)沿以sink為根的樹回傳，對流經(jīng)中間傳感器節(jié)點的數(shù)據(jù)，根據(jù)具體查詢的聚合函數(shù)及數(shù)據(jù)屬性等要求執(zhí)行相關的數(shù)據(jù)聚合操作，丟棄與查詢不相關的數(shù)據(jù)，將相關的查詢數(shù)據(jù)盡可能地合并為更緊湊的分組。例如一個計算網(wǎng)絡中節(jié)點個數(shù)的查詢，首先將該查詢分發(fā)到網(wǎng)絡中；然后每個葉節(jié)點均向父節(jié)點報告計數(shù)值1，中間節(jié)點計算自己的孩子節(jié)點總數(shù)，加1后再向自己的父節(jié)點報告計數(shù)值；如此循環(huán)，直至計數(shù)值傳送至sink節(jié)點。此時的計數(shù)值為網(wǎng)絡中所有的傳感器節(jié)點。2．1．2網(wǎng)絡層數(shù)據(jù)聚合技術

為了降低無線傳感器網(wǎng)絡的能耗，使其生命周期最大化，根據(jù)傳感器節(jié)點采集數(shù)據(jù)的回傳是否依賴于一定的數(shù)據(jù)結構，可以將網(wǎng)絡層的數(shù)據(jù)聚合技術分為存在數(shù)據(jù)聚合結構和不存在數(shù)據(jù)聚合結構兩種。如果是周期性數(shù)據(jù)采集等固定流量業(yè)務模型的應用，一般采用基于數(shù)據(jù)聚合結構的網(wǎng)絡層數(shù)據(jù)聚合技術；對于事件觸發(fā)等具有動態(tài)特性業(yè)務模型的應用，一般適合采用無聚合結構的網(wǎng)絡層數(shù)據(jù)聚合技術。

1）存在數(shù)據(jù)聚合結構為了完成數(shù)據(jù)聚合或部分聚合，傳感器節(jié)點采集到的數(shù)據(jù)一般沿樹狀結構（稱為數(shù)據(jù)聚合樹）回傳。當所有的數(shù)據(jù)分組大小相等，數(shù)據(jù)聚合操作將多個分組合并為一個大小不變的數(shù)據(jù)分組時，為數(shù)據(jù)回傳形成一棵包括所有源傳感器節(jié)點和sink節(jié)點的最優(yōu)數(shù)據(jù)聚合樹是一個NP問題[12]，只能尋找多項式時間的近似最優(yōu)解。三種典型近似最優(yōu)數(shù)據(jù)聚合算法的主要思想為[12]：a）Center at nearest source (CNS)。在CNS協(xié)議中，所有傳感器節(jié)點首先都把采集到的信息傳送至離sink節(jié)點最近的傳感器節(jié)點，由該傳感器節(jié)點完成信息的聚合并最終傳遞至sink節(jié)點。b）Shortest path tree(SPT)。每個傳感器節(jié)點均沿自己至sink節(jié)點的最短路徑發(fā)送數(shù)據(jù)分組，在多個傳感器節(jié)點至sink節(jié)點的最短路徑交叉點進行數(shù)據(jù)聚合，形成一棵以sink節(jié)點為根的數(shù)據(jù)聚合樹。c)Greedy incremental tree(GIT)。首先建立sink節(jié)點至與之距離最近傳感器節(jié)點的一條路徑，然后依次將下一個最近的傳感器節(jié)點加入當前樹。

為了進一步降低無線傳感器網(wǎng)絡的能耗，在網(wǎng)絡層進行數(shù)據(jù)聚合時，可以根據(jù)傳感器節(jié)點采集數(shù)據(jù)的時間相關性，沿數(shù)據(jù)聚合結構對數(shù)據(jù)進行基于時間相關性的聚合。例如，Pittsburgh大學的研究人員提出一種具有時間敏感性的數(shù)據(jù)聚合機制——TiNA (temporal coherency aware in network aggregation)[13]，其目的是減少網(wǎng)絡中傳輸?shù)男畔⒖偭浚岣邤?shù)據(jù)回傳至sink的準確性。該機制的工作原理如下：用戶發(fā)送每個查詢請求時，附帶一個時間相關性允許度tcr(temporal coherency tolerance)參數(shù)；該參數(shù)確定傳感器節(jié)點的當前探測值比前一次探測值有多大的變化時才將結果報告至sink節(jié)點。這樣只有變化超過tcr的數(shù)據(jù)才向上一級報告。

為了進一步降低無線傳感器網(wǎng)絡的能耗，在網(wǎng)絡層進行數(shù)據(jù)聚合時，還可以根據(jù)傳感器節(jié)點采集數(shù)據(jù)的空間相關性對數(shù)據(jù)進行基于空間相關性的聚合。一般來講，存在三種基于空間相關性的數(shù)據(jù)聚合方法[14]，即路由驅動的壓縮(RDC)、壓縮驅動的路由(CDR)和分布式源節(jié)點壓縮（DSC）。在RDC中，數(shù)據(jù)沿著傳感器節(jié)點各自至sink節(jié)點的最短路徑傳送，在路徑的交叉點進行數(shù)據(jù)聚合，在源節(jié)點空間相關性較低時性能好；在CDR中，數(shù)據(jù)沿盡可能大的聚合方向路由，但可能導致較長的路徑，在源節(jié)點空間相關性較高時性能好；在DSC中，數(shù)據(jù)在各個源節(jié)點處執(zhí)行分布式壓縮，然后各自沿至sink節(jié)點的最短路徑傳遞。如果忽略不計獲取傳感器節(jié)點相關性信息的代價，DSC應該最為理想。文獻[14]通過使用聯(lián)合信息熵的概念度量源節(jié)點產(chǎn)生的不相關信息的總量，提出一種靜態(tài)的、基于局部信息的分群數(shù)據(jù)聚合思想，將鄰近的節(jié)點劃分為群。首先在群內執(zhí)行CDR，然后沿著至sink節(jié)點的最短路徑傳輸聚合后的數(shù)據(jù)，并在各群路徑的交叉點執(zhí)行RDC方法。RDC及CDR方法實質是每群一個源節(jié)點及群內包含所有源節(jié)點兩種極端情況。

2）不存在數(shù)據(jù)聚合結構對于周期性數(shù)據(jù)采集，基于數(shù)據(jù)聚合結構的聚合技術雖然可以有效減少通信次數(shù)，節(jié)省無線傳感器網(wǎng)絡的能耗，但是對于事件觸發(fā)類及動態(tài)性強的網(wǎng)絡場景，維護這些數(shù)據(jù)聚合結構的能耗開銷很高[15，16]。在動態(tài)網(wǎng)絡環(huán)境下，建立和維護數(shù)據(jù)聚合結構的能耗開銷可能大于使用數(shù)據(jù)聚合技術帶來的好處。如果使用集中式的方法建立數(shù)據(jù)聚合結構，計算所需的通信開銷很大。而且使用數(shù)據(jù)聚合技術的性能與中間節(jié)點的等待時間也有關系，中間節(jié)點等待時間短，數(shù)據(jù)聚合的概率較低；中間接點的等待時間長，將增加數(shù)據(jù)回傳的時延，最優(yōu)等待時間的確定將依賴于中間節(jié)點在數(shù)據(jù)聚合結構中的位置。這在事件觸發(fā)類應用和動態(tài)網(wǎng)絡環(huán)境中是很難確定的。

文獻[16]對動態(tài)網(wǎng)絡環(huán)境中的事件觸發(fā)類應用進行了研究，探討了無聚合結構的高效數(shù)據(jù)聚合方法，給出了不依賴數(shù)據(jù)聚合結構的高效節(jié)能數(shù)據(jù)聚合技術及協(xié)議。基于數(shù)據(jù)可以在空間和時間上進行聚合，提出了兩種相關的機制，即MAC層的DAA（data aware anycast）機制和網(wǎng)絡層的RW（randomized waiting）機制。DAA機制是一種數(shù)據(jù)敏感的任意播機制，對數(shù)據(jù)在空間上進行聚合；RW機制則在時間上對數(shù)據(jù)進行聚合。這兩種機制的設計目標是盡可能早地進行數(shù)據(jù)聚合，以適應動態(tài)變化的事件發(fā)生區(qū)域，克服不穩(wěn)定信道及某些節(jié)點失效的影響。DAA機制的工作原理為：每個節(jié)點的MAC層可以從多個節(jié)點中選擇下一跳節(jié)點；當有數(shù)據(jù)發(fā)送時，節(jié)點首先發(fā)送帶有數(shù)據(jù)可聚合標志的RTS消息，收到該消息的鄰節(jié)點根據(jù)優(yōu)先級的不同以不同的時延回復CTS消息。CTS消息優(yōu)先級的確定方法為：鄰接點中是否有可以聚合的數(shù)據(jù)，是否比RTS消息的發(fā)送節(jié)點離sink節(jié)點近，前者的優(yōu)先級大于后者，以盡可能進行數(shù)據(jù)聚合。如果一個鄰接點既沒有可以聚合的數(shù)據(jù)，又不比RTS節(jié)點離sink節(jié)點近，則不回復CTS消息。優(yōu)先級高的節(jié)點以短的時延回復CTS消息；其他節(jié)點如果偵聽到該CTS消息，將取消自己CTS消息的發(fā)送。這樣，數(shù)據(jù)發(fā)送節(jié)點選擇CTS消息的發(fā)送節(jié)點作為自己的下一跳節(jié)點。DAA機制雖然可以對鄰接點的數(shù)據(jù)進行有效聚合，但是對兩跳以上或位于同一條數(shù)據(jù)回傳路徑上的節(jié)點，當交互RTS和CTS消息的時間遠小于數(shù)據(jù)分組的傳輸時延時，不能進行有效的數(shù)據(jù)聚合。這時需要使用RW機制。其工作原理為：每個節(jié)點在(0，max_waitingtime)之間隨機選擇一個等待時間作為數(shù)據(jù)發(fā)送前的等待時延，對在等待期間接收到的可聚合分組進行數(shù)據(jù)聚合。DAA與RW機制結合起來可以有效地增加動態(tài)環(huán)境中的數(shù)據(jù)聚合次數(shù)，降低無線傳感器網(wǎng)絡的能耗。

2．1．3其他層數(shù)據(jù)聚合技術

數(shù)據(jù)聚合技術的研究一般都是基于應用層或網(wǎng)絡層的，但是為了節(jié)省無線傳感器網(wǎng)絡的能耗，很多方法也需要MAC層的支持。2.1.2節(jié)中的方法就需要MAC層的支持，AIDA[17]也需要MAC層支持。AIDA是一種與應用無關的自適應數(shù)據(jù)聚合方法，具有時間敏感性；數(shù)據(jù)聚合模塊位于MAC層和網(wǎng)絡層之間，無須對現(xiàn)有的MAC層與網(wǎng)絡層協(xié)議進行修改。AIDA利用分組的排隊時延及無線網(wǎng)絡的廣播本質，采用一種自適應的動態(tài)反饋控制機制，將小的數(shù)據(jù)分組合并為一個聚合后的MAC分組進行發(fā)送。數(shù)據(jù)聚合模塊負責完成網(wǎng)絡數(shù)據(jù)分組的聚合和去聚合。AIDA產(chǎn)生四種類型的聚合分組：unicast分組（無聚合）、manycast分組(被聚合的分組，下一跳相同)、multicast分組（被聚合的分組，下一跳不同）及broadcast分組（被聚合的分組，全部為廣播分組）。采用多種分組格式是為了減少分組頭部開銷。在網(wǎng)絡負載高時，AIDA可以降低數(shù)據(jù)時延及網(wǎng)絡能耗，可以和其他與應用相關的數(shù)據(jù)聚合算法一起使用。2．2數(shù)據(jù)時延

為了保證應用對數(shù)據(jù)時延的要求，同時又能夠進行有效的數(shù)據(jù)聚合，一次事件相關的數(shù)據(jù)采集中涉及的所有傳感器節(jié)點需要協(xié)作以達到某種同步；中間節(jié)點需要知道等待多長時間、合并哪些下游節(jié)點傳來的數(shù)據(jù)。由于無線傳感器網(wǎng)絡是一個Ad hoc網(wǎng)絡，節(jié)點隨機分布，且受能量、計算及存儲空間等能力的限制，不可能維護動態(tài)變化的全局信息，解決上述問題是一個難點。中間節(jié)點需要對盡可能多的數(shù)據(jù)進行聚合。但是等待時間過短，可能造成沒有進行或僅進行了部分數(shù)據(jù)的聚合；等待時間過長，又可能造成數(shù)據(jù)回傳至sink節(jié)點的時延過長，所以需要在聚合與數(shù)據(jù)時延之間進行折中。本文分別從有數(shù)據(jù)聚合結構和無數(shù)據(jù)聚合結構兩個角度來說明保證數(shù)據(jù)時延的數(shù)據(jù)聚合技術。

當數(shù)據(jù)聚合樹建立后，節(jié)點如何選擇數(shù)據(jù)聚合時機才能使數(shù)據(jù)在回傳時盡量聚合并滿足時延要求呢？文獻[6]提出了三種數(shù)據(jù)聚合時機模型并進行了比較。它們分別是周期性簡單數(shù)據(jù)聚合時機模型、周期性逐跳數(shù)據(jù)聚合時機模型及周期性逐跳調整數(shù)據(jù)聚合時機模型。第一種模型是節(jié)點等待一個固定長度的時間，對已經(jīng)接收到的數(shù)據(jù)執(zhí)行數(shù)據(jù)聚合，然后向下一跳發(fā)送聚合后的數(shù)據(jù)分組；第二種模型與第一種相似，不同之處在于當節(jié)點收到所有孩子的數(shù)據(jù)后，立即進行數(shù)據(jù)聚合并發(fā)送聚合后的結果；第三種模型根據(jù)節(jié)點在數(shù)據(jù)聚合樹中的位置確定數(shù)據(jù)聚合時機。與前兩種模型相比，第三種模型能夠在保證數(shù)據(jù)時延的情況下，使所有傳感器節(jié)點采集的數(shù)據(jù)在沿已知數(shù)據(jù)聚合樹回傳時能最大程度地聚合，有效節(jié)省了無線傳感器網(wǎng)絡的能耗。文獻[7~9]均屬于該種模型，級聯(lián)超時法（cascading timeouts）[6]也屬于第三種模型。級聯(lián)超時法無須傳感器節(jié)點間的時間同步，根據(jù)節(jié)點在數(shù)據(jù)聚合樹中的位置確定數(shù)據(jù)聚合時機，距離sink節(jié)點近的節(jié)點等待時間長，距離sink節(jié)點遠的節(jié)點等待時間短，所有節(jié)點的等待時間形成一種級聯(lián)效應。

對于無聚合結構的數(shù)據(jù)聚合方法，文獻[16]提出的RW機制通過與MAC層任意播機制相結合，既可以避免采用根據(jù)節(jié)點位置確定等待時間所帶來的網(wǎng)絡時延，尤其是在網(wǎng)絡規(guī)模較大時，這種時延將不能忍受；又可以增加數(shù)據(jù)聚合的概率，降低網(wǎng)絡中的總能耗。從仿真結果來看[16]，這種方法比沒有等待時延的方法能夠增加數(shù)據(jù)聚合的概率，降低網(wǎng)絡中總的分組傳輸次數(shù)，同時增加的時延有限。

2．3數(shù)據(jù)質量

在無線傳感器網(wǎng)絡的數(shù)據(jù)回傳中，如果應用對數(shù)據(jù)質量提出一定的要求，則需要在保證回傳數(shù)據(jù)質量的前提下，盡量減少網(wǎng)絡的能耗。

文獻[10]為周期性數(shù)據(jù)聚合應用提出一種分布式估計算法，用戶可在數(shù)據(jù)的準確性與節(jié)能之間進行折中。傳統(tǒng)的數(shù)據(jù)聚合運算是快照(snapshot)類型，是一種精確運算。這種技術是一種近似運算，其主要思想是每個節(jié)點傳遞的不是采集的數(shù)據(jù)值或聚合后的精確數(shù)據(jù)值，而是一個二元組，即（數(shù)據(jù)，數(shù)據(jù)的變化范圍）。每個節(jié)點處保留一個全局估計值。當接收到鄰節(jié)點的估計值或采集到新數(shù)據(jù)值后，首先計算出本地新的全局估計值。如果該值使鄰節(jié)點的估計值超過根據(jù)應用對準確性要求所確定的數(shù)據(jù)變化門限值，將廣播本節(jié)點的估計值；否則不發(fā)送數(shù)據(jù)。另外，節(jié)點估計值的變化范圍將隨著時間的推移使范圍變大。具體是否發(fā)送新估計值的決策過程如下：每個節(jié)點保存其鄰節(jié)點的最新估計值；當它得到一個新的估計值后將進行計算。如果與鄰節(jié)點的估計值合并后，使鄰節(jié)點的估計值與原來值的差別大于某個門限，則廣播自己的新估計值；否則不發(fā)送。數(shù)據(jù)變化門限值決定了數(shù)據(jù)回傳的精度，也決定了網(wǎng)絡中的能耗，需要根據(jù)用戶的需求進行折中設定。

文獻[18]對周期性數(shù)據(jù)采集，提出一種讓用戶對查詢精度和能量消耗進行折中的技術，數(shù)據(jù)的回傳基于數(shù)據(jù)聚合樹。研究認為，sink節(jié)點得到的數(shù)據(jù)因為需要經(jīng)過多跳傳遞及預處理，所以相對于傳感器節(jié)點來說總是陳舊的。用戶可以在查詢中說明對數(shù)據(jù)允許出錯范圍的要求。每個節(jié)點都對采集到的數(shù)據(jù)進行預測，只有當實際采集到的數(shù)據(jù)超過允許出錯的范圍時，才向父節(jié)點回傳采集到的數(shù)據(jù)。

文獻[19]為周期性監(jiān)測應用提出一種基于數(shù)據(jù)聚合樹的、回傳一定質量無線傳感器網(wǎng)絡數(shù)據(jù)的方法。Sink節(jié)點接收由各個節(jié)點采集并進行數(shù)據(jù)聚合后的一個數(shù)據(jù)值，該值有一個最大錯誤允許門限。網(wǎng)絡中所有節(jié)點的錯誤門限值之和等于這個最大錯誤門限。其核心內容是剩余操作模型。對某個節(jié)點來說，當下游節(jié)點的累積變化不超過該節(jié)點的錯誤門限值時，該節(jié)點可以不向sink節(jié)點回傳聚合后的結果。每個節(jié)點的錯誤門限值可以根據(jù)本地統(tǒng)計的潛在增益值進行自適應地調整，以使網(wǎng)絡中總的數(shù)據(jù)回傳次數(shù)最小。這種方法可以顯著減少網(wǎng)絡中的總數(shù)據(jù)回傳次數(shù)。在實際使用中需要在最大錯誤允許門限值的選擇與網(wǎng)絡能耗之間折中。

3存在的問題及研究方向

鑒于無線傳感器網(wǎng)絡支持QoS數(shù)據(jù)聚合研究的復雜性，本文雖然為支持QoS的數(shù)據(jù)聚合研究提出了網(wǎng)絡生命周期、數(shù)據(jù)時延和數(shù)據(jù)質量三個度量指標，但是隨著實時無線傳感器網(wǎng)絡應用的發(fā)展[20]，今后還應考慮時延抖動等QoS指標。現(xiàn)有支持QoS的數(shù)據(jù)聚合技術大多局限在僅支持部分QoS指標，還應該進一步考慮如何在支持網(wǎng)絡生命周期、數(shù)據(jù)時延及數(shù)據(jù)質量之間進行折中。另外，支持QoS的數(shù)據(jù)聚合技術的可擴展性、支持QoS的數(shù)據(jù)聚合技術與支持QoS的路由及應用層技術等之間的關系等，都是今后的研究方向。

參考文獻：

［1］AKYILDIZ I，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4):393－422.

[2]POTTIE G，KAISER W.Wireless sensor networks [J].Communications of the ACM，2000，43(5):51－58.

[3]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks[C]//Proc of ACM/IEEE International Conference on Mobile Computing and Networks.New York:ACM Press，2000:56－67.

[4]CHEN D，VARSHNEY P K．QoS support in wireless sensor networks：a survey[C]//Proc of International Conference on Wireless Networks.Las Vegas:[s.n.]，2004:227－233．

[5]YOUNIS M，AKKAYA K，ELTOWEISSY M，et al．On handling QoS traffic in wireless sensor networks[C]//Proc of the 37th Hawaii International Conference of System Sciences.2004:4653－4662.

[6]SOLIS I，OBRACZKA K.The impact of timing in data aggregation for sensor networks [C]//Proc of IEEE International Conference on Communications (ICC).2004:3640－3645.

[7]MADDEN S，F(xiàn)RANKLIN M J，HELLERSTEIN J M，et al.TAG:a tiny aggregation service for Ad hoc sensor networks [C]//Proc of the 5th Symposium on Operating Systems Design and Implementation.New York:ACM Press，2002:131 146.

[8]ANNAMALAI V，GUPTA S K S，SCHWIEBERT L.On tree based convergecasting in wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference.Tempe:ASU Libra ries，2003:1942 1947.

[9]FLORENS C，McELIECE R.Packets distribution algorithms for sensor networks[C]//Proc ofthe 22nd Annual Joint Conference on the IEEE Computer and Communications Societies，2003.

[10]BOULIS A，GANERIWAL S，SRIVASTAVA M B.Aggregation in sensor networks:an energy accuracy trade off sensor network protocols and applications[C]//Proc of the 1st IEEE Int Workshop on Sensor Network Protocols and Applications.2003:128 138.

[11]ADLAKHA S，GANERIWAL S，SCHURGERS C，et al.Density，accuracy，delay and lifetime tradeoffs in wireless sensor networks:a multidimensional design perspective[C]//Proc of the 1st International Conference on Embedded Networked Sensor System.New York:ACM Press，2003:296－297.

[12]KRISHNAMACHARI B，ESTRIN D，WICKER S.Modeling data centric routing in wireless sensor networks Technical Report CENG[R].[S.l.]:USC Computer Engineering，2002:2 14.

[13]SHARAF M A，BEAVER J，LABRINIDIS A，et al.TiNA:a scheme for temporal coherency aware in network aggregation[C]//Proc of the 3rd ACM International Workshop on Data Engineering for Wireless and Mobile Access.New York:ACM Press，2003:69 76.

[14]PATTEM S，KRISHNAMACHARI B，GOVINDAN R.The impact of spatial correlation on routing with compression in wireless sensor networks[C]//Proc of the 3rd International Symposium on Information Processing in Sensor Networks.New York:ACM Press，2004:28－35.

[15]ZHANG Wen sheng，CAO Guo hong.Optimizing tree reconfiguration for mobile target tracking in sensor networks[J].ACM SIGMOBILE Mobile Computing and Communications Review，2003，7(3):1559 1662.

[16]FAN Kai wei，LIU Sha，SINHA P.On the potential of structure free data aggregation in sensor networks [C]//Proc of Trans on Mobile Computing.Piscataway，NJ:IEEE Educational Activities Department，2007:927 942.

[17]HE T，BLUM B M，STANKOVIC J A，et al.AIDA:adaptive application independent aggregation in sensor networks[J].ACM Trans on Embedded Computing System，2003，3(2):426－457.

[18]EMEKCI F，YU H，AGRAWAL D，et al.Energy conscious data aggregation over large scale sensor networks [EB/OL].(2003).http://www.cs.ucsb.edu/ research /tech_reports/2003 32.pdf.

[19]DELIGIANNAKIS A，KOTIDIS Y，ROUSSOPOULOS N.Hierarchical in network data aggregation with quality guarantees[C]//Proc of the 9th International Conference on Extending Database Technology.2004:658－675.

[20]馬華東，陶丹.多媒體傳感器網(wǎng)絡及其研究進展[J].軟件學報，2006，17(9):2013－2028.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”