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

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

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；數(shù)據(jù)聚合；能耗；時(shí)延；數(shù)據(jù)質(zhì)量；服務(wù)質(zhì)量

中圖分類號(hào)：TP393； TP212； TP301.6文獻(xiàn)標(biāo)志碼：A

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

0引言

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

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

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

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

1)網(wǎng)絡(luò)生命周期網(wǎng)絡(luò)生命周期是指無(wú)線傳感器網(wǎng)絡(luò)從部署到不能為用戶提供滿足要求數(shù)據(jù)的時(shí)間，與具體的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用相關(guān)。該指標(biāo)主要取決于系統(tǒng)的能耗，具體包括通信能耗、控制能耗（路由、拓?fù)浼岸ㄎ恍畔⒌鹊木S護(hù)）、計(jì)算能耗（如聚合處理）等。數(shù)據(jù)聚合技術(shù)研究的主要目標(biāo)就是節(jié)省能耗，使無(wú)線傳感網(wǎng)絡(luò)的生命周期最大化。由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)通信的能耗比計(jì)算的能耗高幾個(gè)數(shù)量級(jí)[2]，數(shù)據(jù)聚合研究中通常使用網(wǎng)絡(luò)中總的通信次數(shù)來(lái)衡量無(wú)線傳感器網(wǎng)絡(luò)的總能耗。通過(guò)減少無(wú)線傳感器網(wǎng)絡(luò)中的通信次數(shù)來(lái)延長(zhǎng)網(wǎng)絡(luò)的生命周期。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

文獻(xiàn)[18]對(duì)周期性數(shù)據(jù)采集，提出一種讓用戶對(duì)查詢精度和能量消耗進(jìn)行折中的技術(shù)，數(shù)據(jù)的回傳基于數(shù)據(jù)聚合樹(shù)。研究認(rèn)為，sink節(jié)點(diǎn)得到的數(shù)據(jù)因?yàn)樾枰?jīng)過(guò)多跳傳遞及預(yù)處理，所以相對(duì)于傳感器節(jié)點(diǎn)來(lái)說(shuō)總是陳舊的。用戶可以在查詢中說(shuō)明對(duì)數(shù)據(jù)允許出錯(cuò)范圍的要求。每個(gè)節(jié)點(diǎn)都對(duì)采集到的數(shù)據(jù)進(jìn)行預(yù)測(cè)，只有當(dāng)實(shí)際采集到的數(shù)據(jù)超過(guò)允許出錯(cuò)的范圍時(shí)，才向父節(jié)點(diǎn)回傳采集到的數(shù)據(jù)。

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

3存在的問(wèn)題及研究方向

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

參考文獻(xiàn)：

［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)絡(luò)及其研究進(jìn)展[J].軟件學(xué)報(bào)，2006，17(9):2013－2028.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”