傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合技術(shù)研究

程文靜??

摘 要：在傳感器網(wǎng)絡(luò)中，數(shù)據(jù)通信消耗了網(wǎng)絡(luò)的大部分能量。因此，如何使數(shù)據(jù)在本地進行計算或各種方式的聚合以減少數(shù)據(jù)通信量成為無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)處理工作的核心技術(shù)之一。討論了幾種不同的數(shù)據(jù)聚合方法以及其中涉及的路由協(xié)議和聚合函數(shù)，并通過一系列定義的參數(shù)把它們比較和總結(jié)。

關(guān)鍵字：傳感器網(wǎng)絡(luò)；數(shù)據(jù)聚合；路由協(xié)議；聚合函數(shù)

中圖分類號：TB 文獻標(biāo)識碼：A doi：10.19311/j.cnki.16723198.2017.21.096

傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合技術(shù)旨在把源節(jié)點或者中間節(jié)點上的多個數(shù)據(jù)合并在一起，形成高質(zhì)量的信息，以此盡量減少網(wǎng)絡(luò)中的通信量。在較早的研究中，網(wǎng)內(nèi)聚合技術(shù)的著重于通信協(xié)議的設(shè)計，通過選擇合并數(shù)據(jù)包的最優(yōu)路徑來實現(xiàn)。最近的研究中，出現(xiàn)了一些更高效的方法，提出了新的數(shù)據(jù)表達方式，并且能夠支持更復(fù)雜的聚合功能。

1 影響網(wǎng)內(nèi)聚合的因素

網(wǎng)內(nèi)聚合方法的主要性能指標(biāo)包括生存時間、數(shù)據(jù)準確率和延遲時間。

網(wǎng)絡(luò)生存時間指定了直到a%的傳感器節(jié)點死亡為止的數(shù)據(jù)傳輸?shù)妮啍?shù)，a由應(yīng)用需求決定。總體來說，網(wǎng)絡(luò)生存時間和能源效率是一致的，因此能效的提高可以延長網(wǎng)絡(luò)生存周期。

數(shù)據(jù)準確率取決于具體的應(yīng)用，即網(wǎng)絡(luò)設(shè)計的目的，路由方案和聚合算法的效率。

延遲描述了數(shù)據(jù)傳輸和聚合過程中的延遲狀況。它可以由數(shù)據(jù)包到達基站及在源節(jié)點產(chǎn)生數(shù)據(jù)的時間延遲來定義。

網(wǎng)內(nèi)聚合技術(shù)和三方面有關(guān)：路由協(xié)議、聚合函數(shù)和數(shù)據(jù)結(jié)構(gòu)。在傳感器網(wǎng)絡(luò)中，網(wǎng)內(nèi)聚合技術(shù)和路由方案是緊密結(jié)合在一起的，在目前已經(jīng)開發(fā)出來的一系列協(xié)議中，“以數(shù)據(jù)為中心”的路由協(xié)議是比較重要的一種類型。該協(xié)議是基于查詢的，由被查詢數(shù)據(jù)的命名決定。它通過減少冗余、最小化消息的尺寸和數(shù)量來實現(xiàn)不同傳感器節(jié)點之間的數(shù)據(jù)聚合，以此來節(jié)省網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)生存時間。

數(shù)據(jù)聚合函數(shù)是網(wǎng)內(nèi)聚合技術(shù)的另一個重要方面。它決定了如何根據(jù)具體需求來合并數(shù)據(jù)。這些函數(shù)包括去除冗余、求最大值max、求最小值min、求平均值average和一些復(fù)雜的函數(shù)，如求中間值median和整體值holistic。在本文中，通過兩種主要的范例來考慮對這些函數(shù)的分類：

無損耗和有損耗的聚合：無損耗聚合允許把單個數(shù)據(jù)項在一個較大數(shù)據(jù)包中連接起來，發(fā)送之后在基站可以把這些數(shù)據(jù)元素恢復(fù)出來，也就是說，沒有數(shù)據(jù)會丟失。相反，對于有損耗聚合，在路由過程中存在數(shù)據(jù)值的合并，因此之后在基站中無法重建原始的數(shù)據(jù)元素。例如，對于大多數(shù)方法來說，min，count和average是有損耗的，因為數(shù)據(jù)值在路由過程中被進行了聚合操作，因此在整個查詢過程中，聚合的數(shù)據(jù)元素的尺寸始終和原始數(shù)據(jù)的尺寸是一致的。也就是說，整體數(shù)據(jù)的尺寸大大的減小了。相反，函數(shù)median是無損耗的，因為數(shù)據(jù)聚合只有在所有原始數(shù)據(jù)都到達基站之后才能進行，因此在每個中間節(jié)點，多個小數(shù)據(jù)包中的數(shù)據(jù)元素被混合在一個較大的數(shù)據(jù)包中，沒有數(shù)據(jù)尺寸的減小。

冗余敏感性：對冗余不敏感的聚合如min和max不受冗余數(shù)據(jù)的影響，而對冗余敏感的聚合如sum和count，它們的最終結(jié)果受冗余數(shù)據(jù)個數(shù)的影響。

除了上述提到的常見的聚合函數(shù)之外，還有一些關(guān)于旨在發(fā)掘傳感數(shù)據(jù)相關(guān)性的其他聚合算法的研究。相關(guān)性為網(wǎng)內(nèi)聚合的發(fā)展帶來了重要的效率。

影響網(wǎng)內(nèi)聚合的第三個因素是存儲、聚合或者傳輸數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。一個數(shù)據(jù)結(jié)構(gòu)的詳細設(shè)計取決于應(yīng)用程序的需要，目的在于用合適的方式表達不同傳感器節(jié)點上的數(shù)據(jù)對于網(wǎng)內(nèi)聚合技術(shù)來說，這三個因素都得考慮到。然而較早的研究主要集中在開發(fā)基于傳感器節(jié)點特征、結(jié)構(gòu)和應(yīng)用需求的路由協(xié)議上。近期的研究更多地集中在聚合函數(shù)和數(shù)據(jù)結(jié)構(gòu)上。

2 兩種典型的數(shù)據(jù)聚合方式

2.1 基于水平路由的數(shù)據(jù)聚合

Directed Diffusion是數(shù)據(jù)聚合和“以數(shù)據(jù)為中心”的路由思想發(fā)展的里程碑。在這種方法里，數(shù)據(jù)以屬性-數(shù)值對來命名。它提供了一個對應(yīng)用程序有意識的路由方案，尤其適用于以下情況：有一個或多個下沉節(jié)點（注入查詢的節(jié)點）將查詢（任務(wù)）傳播到網(wǎng)絡(luò)中的所有節(jié)點，來獲取特定信息（事件）。例如，“在接下來的T秒時間內(nèi)，每I毫秒?yún)R報一次區(qū)域R中的所有四條腿動物的估計位置”。

一個傳感任務(wù)的“興趣”定義為一個屬性-數(shù)據(jù)對的列表，包括如對象的名稱、時間間隔、持續(xù)時間和地理位置。在本方法中，下沉節(jié)點在網(wǎng)絡(luò)中注入一個興趣，并沿著它的鄰居節(jié)點傳播下去。在傳播過程中會建立多條候選路徑，這些路徑也是之后傳感器節(jié)點至下沉節(jié)點的數(shù)據(jù)返回路徑。產(chǎn)生滿足興趣的事件的節(jié)點被稱為源節(jié)點，它產(chǎn)生的數(shù)據(jù)包沿著之前形成的候選路徑傳送到下沉節(jié)點。當(dāng)一個中間節(jié)點收到一個數(shù)據(jù)包時，它先檢查自己產(chǎn)生的包是否包含可能來自相同事件的相似的數(shù)據(jù)，來進行聚合，然后新產(chǎn)生的數(shù)據(jù)包被傳回下沉節(jié)點。當(dāng)所有節(jié)點都到達下沉節(jié)點后，網(wǎng)絡(luò)會加強一條或幾條路徑。其他路徑被忽略，因此冗余數(shù)據(jù)包會減少。之后下沉節(jié)點會沿著加強路徑重新發(fā)送一個修正過的興趣到節(jié)點，這個興趣的數(shù)據(jù)匯報時間間隔變短。如此，源節(jié)點會以一個較高的速率發(fā)送數(shù)據(jù)包。選擇加強路徑的規(guī)則由應(yīng)用程序本身的特點決定，比如需要低延遲率或者需要接收到較多的數(shù)據(jù)包。

在水平路由的網(wǎng)絡(luò)中，所有的節(jié)點角色相同，而在層次結(jié)構(gòu)網(wǎng)絡(luò)中，節(jié)點被進行了分組，屬于不同的層次，被分配了不同的任務(wù)，接下來介紹其中的一種結(jié)構(gòu)。

2.2 基于樹結(jié)構(gòu)的數(shù)據(jù)聚合

在一個基于樹形結(jié)構(gòu)的傳感器網(wǎng)絡(luò)中，節(jié)點被組織成一個樹形結(jié)構(gòu)，其中基站是根節(jié)點，傳感數(shù)據(jù)從葉子節(jié)點傳輸?shù)礁?jié)點，并且可能在中途節(jié)點進行聚合。最具有代表性的樹形聚合方法為TAG（Tiny AGregation）。

TAG方法集成于TinyDB系統(tǒng)中，是為監(jiān)控應(yīng)用設(shè)計的，采用了“以數(shù)據(jù)為中心”協(xié)議方式，它為聚合查詢提供了一個類似于SQL的接口。TAG的實現(xiàn)包括兩個階段：“分配”和“收集”。在“分配”階段，聚合查詢在全網(wǎng)內(nèi)傳播，一個節(jié)點被選為根，它通過廣播消息告訴其它節(jié)點組成一棵路由樹，建立一個樹形路由方案。每個節(jié)點產(chǎn)生的消息包含自己的節(jié)點ID和舉例根的層數(shù)。當(dāng)一個沒被標(biāo)識層數(shù)的節(jié)點收到一條消息，它就把自己的層數(shù)標(biāo)識為該消息中的層數(shù)加1，并且把該消息來源的節(jié)點看作自己的父節(jié)點。通過這種方法，所有節(jié)點就組成了一棵樹，之后的查詢就沿著這棵樹進行。在“收集”階段，收集的數(shù)據(jù)沿路進行適當(dāng)?shù)木奂?，最終傳送到根。除了常見的幾種聚集函數(shù)，TAG還支持另外四種對傳感器網(wǎng)絡(luò)來說很重要的函數(shù)，如單調(diào)性和局部狀態(tài)。endprint

除了TAG之外還有一些基于樹形的路由協(xié)議也各具特色。但是這些所有的方法都和TAG相似，缺點在于路由結(jié)構(gòu)的健壯性較弱。

3 結(jié)論

本文介紹了傳感器網(wǎng)絡(luò)中最重要的數(shù)據(jù)處理技術(shù)，即網(wǎng)內(nèi)聚合的相關(guān)研究。根據(jù)影響網(wǎng)內(nèi)聚合的因素，總結(jié)了兩種最典型的數(shù)據(jù)聚合方式，及基于水平路由的聚合和基于樹型結(jié)構(gòu)的聚合。前者的優(yōu)點在于事先不需要了解網(wǎng)絡(luò)拓撲的全局知識，因為節(jié)點之間可以通過建立候選路徑和加強路徑來很好地彼此交互。另外，由于建立了多條傳輸路徑，通信的健壯性很可靠，顯著地降低了數(shù)據(jù)丟失率。因此，這種方式適用于頻繁動態(tài)變換的網(wǎng)絡(luò)，比如追蹤應(yīng)用，而不適合于需要持續(xù)傳輸數(shù)據(jù)的環(huán)境監(jiān)控應(yīng)用。后者的優(yōu)點在于使用了類SQL接口。用戶不需要了解數(shù)據(jù)是如何進行聚合的，而只需要在查詢時調(diào)用相應(yīng)的聚合函數(shù)即可。另外，同步機制使用的傳感器狀態(tài)轉(zhuǎn)換模式也可以節(jié)省能量。然而，缺點在于一個失敗的節(jié)點可能導(dǎo)致其整個子樹和其父節(jié)點的失聯(lián)。因此，在頻繁的節(jié)點失敗或者拓撲變化的狀況下，TAG不是一個高效的方法，因為頻繁的路由樹重組會消耗大量的能量。

參考文獻

[1]R. Rajagopalan. Data aggregation techniques in sensor networks： A survey[J]. IEEE Communications Surveys & Tutorials， vol. 8， no. 4， pp. 4863， 2010.

[2]E. Fasolo. In-network aggregation techniques for wireless sensor networks： A survey[J]. IEEE Wireless Communication Magazine， vol. 14， no. 2， pp. 7087， April 2012.

[3]I. Solis. The impact of timing in data aggregation for sensor networks[C]// In Proceedings of IEEE International Conference on Communications， vol. 6， pp. 36403645， June 2010.

[4]T. Abdelzaher. Feedback control of data aggregation in sensor networks[C]// In Proceedings of IEEE Conference on Decision and Control， pp. 14901495， December 2012.

[5]S. Madden. TAG： a tiny aggregation service for ad-hoc sensor networks[C]// In ACM SIGOPS Operating Systems Review， vol. 36， pp. 131146， December 2010.

[6]C. Intanagonwiwat. Directed Diffusion： a scalable and robust communication paradigm for sensor networks[C]// In Proceedings of the 6th annual ACM/IEEE international conference on Mobile computing and networking， pp. 5657， August 2010.endprint