應可珍,鄔錦彬,戴國勇苗春雨,范聰玲,陳慶章*

(1.浙江工業(yè)大學計算機科學與技術學院,杭州 310014;2.浙江財經(jīng)大學東方學院,浙江 海寧 314408)

?

一種基于線性時間概率計數(shù)算法的數(shù)據(jù)聚集技術*

應可珍1,2,鄔錦彬1,戴國勇1苗春雨1,范聰玲1,陳慶章1*

(1.浙江工業(yè)大學計算機科學與技術學院,杭州 310014;2.浙江財經(jīng)大學東方學院,浙江 海寧 314408)

無線傳感器網(wǎng)絡中,通過數(shù)據(jù)聚集操作在中間節(jié)點預先對數(shù)據(jù)進行處理,可去除大量冗余,減少數(shù)據(jù)傳輸,實現(xiàn)節(jié)能。針對多路徑路由下數(shù)據(jù)聚集操作的重復計數(shù)問題,研究對副本不敏感的概要結構并優(yōu)化某些特性,在線性時間概率計數(shù)算法的數(shù)學模型基礎上提出一種新的數(shù)據(jù)聚集技術FA(Fan Aggregation)技術,實現(xiàn)高能效的數(shù)據(jù)聚集。理論分析和仿真實驗均表明,FA技術相較于FM(Flajolet Martin)技術和LC(Linear Counting)技術在存儲空間和準確率上均有更好的性能體現(xiàn)。

無線傳感器網(wǎng)絡;數(shù)據(jù)聚集;概要結構;重復計數(shù)

無線傳感器網(wǎng)絡為人類提供了一種新的感知世界的方式[1]。人類可以在軍事、醫(yī)療、環(huán)境監(jiān)測等領域方便地開展各項活動。這些活動中,對各項數(shù)據(jù)的收集、傳輸、存儲和分析至關重要。其中數(shù)據(jù)收集模式[2-3]主要包括基于查詢、周期匯報和事件匯報等?；诓樵冃问降臄?shù)據(jù)收集僅當查詢下令時,網(wǎng)絡中的節(jié)點才會執(zhí)行數(shù)據(jù)收集工作,并將數(shù)據(jù)收集的結果反饋給基站或用戶。而數(shù)據(jù)聚集查詢則是基于查詢模式的其中一種數(shù)據(jù)收集方式,這里統(tǒng)一用“數(shù)據(jù)聚集技術”來描述。在查詢過程中直接將所有原始數(shù)據(jù)傳到基站集中處理,此時各節(jié)點大量的冗余數(shù)據(jù)不僅使傳輸效率低下且更為耗能。為了降低數(shù)據(jù)傳輸量,一種方式是在數(shù)據(jù)采集時即進行壓縮處理,如壓縮感知技術[4];另外一種方式是在數(shù)據(jù)傳輸時對數(shù)據(jù)進行處理,減少數(shù)據(jù)的傳輸量。如在路由的同時由中間節(jié)點先對數(shù)據(jù)進行聚集操作,過濾冗余數(shù)據(jù),再將結果轉發(fā)給父節(jié)點,這種也稱為網(wǎng)內(nèi)聚集[5-7]。聚集操作主要包括求和(SUM)、計數(shù)(COUNT)、最大值(MAX)、最小值(MIN)、求平均(AVERAGE)乃至求中位數(shù)(MEDIAN)等。目前對于數(shù)據(jù)聚集技術的研究是無線傳感器網(wǎng)絡的研究熱點之一[2]。

1 數(shù)據(jù)聚集技術概述

在進行聚集操作時,Madden[8]等人研究了基于樹型拓撲結構的高效數(shù)據(jù)聚集算法,聚集計算由葉節(jié)點沿著路由樹傳遞給父節(jié)點,逐層向上進行,最后由根節(jié)點計算出整個網(wǎng)絡的聚集值。但是由于節(jié)點間通信的不穩(wěn)定性,丟包時有發(fā)生,因而導致聚集結果不準確。為了避免這種情況,多路徑路由[9]技術應運而生,事件區(qū)域的數(shù)據(jù)可以在算法所形成的多路徑上進行數(shù)據(jù)包的發(fā)送[10-11]。各節(jié)點將中間結果發(fā)給多個鄰居節(jié)點,使得節(jié)點讀數(shù)的多個副本在網(wǎng)絡中傳輸,造成部分節(jié)點數(shù)據(jù)被重復計算。對于某些對副本敏感的操作(如SUM、COUNT、AGERAGE等)會使得最后的聚集結果不準確。為了避免副本的影響,文獻[9]及文獻[12-14]提出一種對副本不敏感的概要結構,采用這種結構可避免節(jié)點值被重復計算,即為擴散性概要聚集技術(Synopsis Diffusion)。這些技術主要包括兩類,一是Flajolet和Martin等人在1985年提出的概率計數(shù)算法[15]基礎上產(chǎn)生的數(shù)據(jù)聚集技術,此種記為FM技術。二是在Whang等人于1990年提出的線性時間概率計數(shù)算法[16]基礎上產(chǎn)生的線性計算(Linear Counting)技術,此種記為LC技術。采用以上技術均可從多重數(shù)據(jù)集中估算出不重復的數(shù)據(jù)集的個數(shù)。

對FM技術,需同時使用多個獨立的概要結構,再對其取平均值從而產(chǎn)生較為精確的估計值。精確度與概要結構的數(shù)量成正比。然而多個概要結構增加了各節(jié)點的存儲空間需求,而少量的概要結構卻導致精度不高的問題。LC技術只適合小數(shù)據(jù)聚集。它通過線性的方式將各元素映射到LC概要結構上,每一次聚集均會產(chǎn)生相應長度的位相量,如果是大數(shù)據(jù)的聚集,會占用大量的存儲空間,因而不適用。

針對這種情況,本文在線性時間概率計數(shù)算法的數(shù)學模型以及基于該模型的現(xiàn)有的LC技術基礎上提出一種新的對副本不敏感的技術即FA(Fan Aggregation)技術,利用FA概要結構來表示節(jié)點值和中間聚集值,并用于聚集操作和計算。

2 FA技術

2.1 網(wǎng)絡定義和問題描述

本研究的網(wǎng)絡模型如圖1所示,假定為由一個基站和一組傳感器組成。該網(wǎng)絡具有如下特征:①每個節(jié)點都有足夠的處理能力和存儲空間;②網(wǎng)絡同步性高,無通信延遲;③節(jié)點間逐層偵聽,第i層節(jié)點偵聽i+1層節(jié)點發(fā)送的信息直至基站。

圖1 環(huán)形拓撲結下的Synopsis Diffusion

假設傳感網(wǎng)絡S由k個節(jié)點組成,用{ui|1≤i≤k}表示,在每個時間戳里,各節(jié)點ui從整數(shù)值域為[D]={0,…,D-1}里讀取一次數(shù)值vi;用以聚集操作的聚集函數(shù)是可分解的f如Sum,Avg和Count;精度由一對參數(shù)(ε,δ),0≤ε≤1,0≤δ≤1來保證,即聚集操作的近似誤差在ε內(nèi)的概率是1-δ。

2.2 FA的數(shù)據(jù)結構和基本操作

如下定義1針對FA概要結構進行了具體定義。

定義1FA概要結構由一對參數(shù)(ε,δ)保證精度,由d個長度為li的數(shù)組FA[i]組成:

FA[0][0],…,FA[0][l1-1]

FA[1][0],…,FA[1][l2-1]

?

FA[d-1][0],…,FA[d-1][ld-1]

①FA結構中的傳感器讀值表示

對于一個傳感器節(jié)點u,其讀值v用二進制數(shù)來表示,其中最右邊末位標記為第0比特位。對于i=0,…,d-1,若有FA[i]=1,則節(jié)點u在[0,li-1]內(nèi)相應產(chǎn)生一個整數(shù)j,并有FA[i][j]=1。圖2中,v=11,用二進制表示為(1011)2,那么就在FA[0]、FA[1]、FA[3]3個比特位里分別隨機設置一個1位。

圖2 節(jié)點讀值表示

用FA概要結構來表示節(jié)點的讀值可以使節(jié)點值在FA概要模式下具備對副本不敏感性,即反復計算一個副本并不影響聚集結果。因此,雖然多路徑路由技術會增加網(wǎng)絡中同一數(shù)據(jù)的副本數(shù),但在最終的聚集結果里,每個讀值vi都只會被計算一次。同時用此結構來近似表示一個節(jié)點的讀值,則原來的精確值即不再使用。

②求和操作

若有兩個概要結構FA1和FA2,則其可能的求和操作將包括如下3種情況:

(i)若FA2=0,則FA[i]=FA1[i]。

(ii)若FA1=0,則FA[i]=FA2[i]。

(iii)FA[i]=FA1[i][j]∨FA2[i][j],j=0,…,li-1。

③網(wǎng)內(nèi)聚集

用相應元素按位或表示兩個FA概要結構的加法操作。比如FA1[0]=(10011),FA2[0]=(10100),那么FA1[0]=(10111),以此類推,將所有相應元素位執(zhí)行此操作即可產(chǎn)生一個新的FA概要結構,從而可計算出v1+v2個不重復記錄值。這種性質(zhì)使得用概要形式表示的節(jié)點讀值可用于網(wǎng)內(nèi)聚集操作。每個中間節(jié)點在收到其子節(jié)點的FA概要結構后,與自身的FA結構進行按位或操作,并將結果傳給高層節(jié)點。

2.3 FA聚集方案

在執(zhí)行聚集操作之前首先需要構建一個層次型拓撲結構的無線傳感網(wǎng)絡。步驟如下:基站廣播一個請求報文給周邊的節(jié)點;接收到請求的節(jié)點把自己的層數(shù)值設為1,這個值就是該節(jié)點距離基站的跳數(shù),它們構成了第1層節(jié)點;接著,第1層節(jié)點繼續(xù)廣播請求給周邊節(jié)點;周邊的節(jié)點接收到請求后,先查看層數(shù)值是否已經(jīng)被設置,若已設置則不做處理,若沒有就在廣播的層數(shù)上繼續(xù)加1即i+1,層數(shù)值為2;層數(shù)值為2的節(jié)點構成了第2層節(jié)點;以此循環(huán)往復就構建成了一個層次型的無線傳感網(wǎng)絡,如圖3所示。

圖3 層次型網(wǎng)絡拓撲結構

FA技術由構建階段和聚集階段組成。在構建階段,由基站沿著路有拓撲廣播一個具體的聚集查詢請求。各節(jié)點收到這個聚集查詢請求后,產(chǎn)生一個FA概要結構用于表示自身的讀值。聚集階段從葉節(jié)點開始,逐層往上進行,在每個i+1層上的節(jié)點廣播各自的FA概要結構給i層上的節(jié)點;i層的節(jié)點把接收到的FA概要結構與自身的FA概要結構做聚集操作,并將聚集結果繼續(xù)發(fā)給i-1層上的節(jié)點;最后由基站計算出最終的聚集值FAfinal。

2.4 FA估計值

當聚集數(shù)據(jù)匯聚到基站時,由基站計算出整個網(wǎng)絡的最終聚集值FAfinal。用式(1)來表示的n的估計值:

(1)

其中Vi是FAfinal[i]中0比特位所占的比例。式(1)記為FA—估計,其基本思路如下:

首先,FA技術可以看成由d個單獨的LC概要結構組成,即各FA[i]大小為li,而i=0,…,d-1。用Di表示映射到FA[i]上的數(shù)目,每一映射到FA[i]上的位都用值2i表示,那么FA[i]的總大小就是2iDi。因此,n就可以通過對各FA[i]求和獲得,即有式(2):

(2)

2.5 d和l的設置

最終估計值必須在精度(ε,δ)要求范圍內(nèi)才有效。因此在使用FA技術之前,需要對參數(shù)d和l的值進行正確地設置,使得使用FA概要結構表示節(jié)點值和聚集值能夠滿足精度要求。

首先,需要最大的傳感器讀數(shù)用以確定可能形成的FA元素的個數(shù)。然而,最大的傳感器讀數(shù)通常不可用,那么這里用最大的可能讀值Z來代替,Z始終大于傳感器讀數(shù)的最大值,令d=log2Z。

接著驗證,在上述參數(shù)的設定下,FA估計計算出的n的近似值滿足(ε,δ)約束條件。

引理1 在每個FA[i]結構里,至多有k個映射,i=0,…,d-1。

接著,驗證FA—估計是否滿足(ε,δ)精度要求。

(3)

(4)

(5)

然后,

(6)

(7)

2.6 算法實例

假定一個傳感器網(wǎng)絡由一個基站和3個節(jié)點A1,A2,A3組成,讀值分別為v1=8,v2=11,v3=5,如圖4所示。

以Sum聚集為例,假定所有FA結構里的元素長度都是8位。聚集計算過程具體為:首先,每個節(jié)點構建一個初始化各元素為0的FA概要結構;然后,在FA概要結構里,節(jié)點的讀值都用二進制來表示;如圖4所示,v2=11=(1011)2,在FA2[0],FA2[1]和FA2[3]上隨機選取一位設置為1。

聚集過程仍從葉節(jié)點開始,如圖5所示。在本例中,由A1節(jié)點發(fā)送其自身的概要結構給上層節(jié)點即節(jié)點A2和節(jié)點A3。值得注意的是,只有當FA元素里的所有成員都不全為0時,該FA[i]元素才會被發(fā)送。圖4中,對于A1節(jié)點就只有FA1[3]不全為0,因此,只發(fā)送FA1[3]=[00000010]給上層節(jié)點。中間節(jié)點收到子節(jié)點的FA概要結構后,與本地節(jié)點進行按位或的聚集操作,并把聚集結果發(fā)給更高層的節(jié)點。如圖6所示,節(jié)點A2就會把FA1+FA2的聚集結果{FA2[0]=[00000010],FA2[1]=[00100000],FA2[3]=[10000010]}發(fā)給基站。同樣的,節(jié)點A3也會把FA1+FA3的聚集結果發(fā)給基站。

圖4 FA概要結構

圖5 FA聚集過程

圖6 FA聚集傳輸

圖7 FA最終聚集值的近似估計過程

3 理論分析與仿真實驗

3.1 性能分析

①聚集技術所占空間大小

基于FM技術的算法[9,13,15]利用多路徑路由方案,采用多個FM概要結構和PCSA技術進行聚集操作?；贚C技術的算法[12,16]創(chuàng)建一個LC概要結構用于聚集計算。FA技術用FA概要結構表示讀值和聚集操作,并用FA估計作最終的聚集估計操作。

②概要結構圖比較

圖8 概要結構圖

圖8分別是FM技術、LC技術和FA技術的概要結構圖的設計思想,FA技術可以更精確的表示節(jié)點的感知值,有多數(shù)個元素則是出于可擴展性的考慮;FM技術表示節(jié)點感知值不夠精確,因此需要數(shù)百個FM概要求取平均值的方式以提高聚集估計計算的精確性。

表1 聚集技術與空間大小

③概要結構大小與n的關系

取ε=0.1,δ=0.1,k=50時,各聚集技術所需空間大小與n的關系如圖9所示。當n<50 000時,LC技術確實比FM技術占用更少的空間并且當n<4 000時,也比FA技術占用更少的空間。從圖中很明顯可以看出,FA技術相較于FM和LC技術,其概要結構遠遠占用更少的空間。

圖9 概要結構大小與n的關系

3.2 仿真實驗

仿真采用MATLAB作為仿真平臺,同時將FA技術與FM技術和LC技術作比較。這些技術都采用多路徑路由技術以提高聚集的健壯性并且均是對副本不敏感的概要結構。本例中以Sum聚集為例來比較概要結構和聚集查詢的性能。

圖10 7×7網(wǎng)絡的路由拓撲圖

①實驗參數(shù)設計

②性能衡量指標

為衡量數(shù)據(jù)聚集的性能,選取3個指標:傳輸功耗、相對誤差率和置信度。傳輸功耗即某一節(jié)點的平均數(shù)據(jù)傳輸量,顯然功耗越低越節(jié)能,在此用平均傳輸比特數(shù)來表示傳輸功耗。相對誤差率是指聚集技術計算的近似估計值與真實值的偏差程度,聚集相對誤差定義為:

(8)

對于置信度,本仿真實驗只取精度約束條件(ε,δ)中的δ作為自變量,因δ值的大小直接影響概要結構的大小,并會對傳輸功耗造成影響。

③仿真結果與分析

按照實驗參數(shù)設計和性能衡量指標,這里選取FM技術和LC技術作為比較對象,下面分別從仿真結果的3個角度進行說明。仿真結果如圖11和圖12所示。

圖11比較各聚集技術中的節(jié)點數(shù)對節(jié)點傳輸功耗的影響情況,節(jié)點數(shù)越多,網(wǎng)絡規(guī)模越大。圖中x軸表示節(jié)點數(shù),y軸表示相應的節(jié)點平均數(shù)據(jù)傳輸量,即傳輸功耗。仿真結果顯示FM、FA技術的傳輸功耗受網(wǎng)絡中的節(jié)點數(shù)目影響并不大,而LC則相對變化較大,因為當節(jié)點數(shù)目增大時,聚集值n也會隨之變得較大。

圖11 節(jié)點對傳輸功耗影響

圖12 約束條件對傳輸功耗的影響

圖12比較各聚集技術的約束條件對傳輸功耗的影響。通過改變精度約束條件(ε,δ)中的δ大小來觀察傳輸功耗的變化情況。圖中x軸表示置信度δ,y軸表示相應的節(jié)點平均數(shù)據(jù)傳輸量,即傳輸功耗。仿真結果顯示,由于FM技術的概要結構里有乘法因子Ω(1/ε2),因此其性能明顯比較差;而FA技術也優(yōu)于LC技術,因其相較前兩者花費更少的概要結構存儲空間。

4 結束語

對于多路徑路由下的無線傳感器網(wǎng)絡的重復計數(shù)問題,本文在線性概率時間計數(shù)算法的基礎上提出了一種新的數(shù)據(jù)聚集技術即FA技術。其具有副本不敏感、相對占用空間小、傳輸功耗小的特征。并且通過仿真比較,在同樣精度條件下,FA技術在空間占用和傳輸功耗上優(yōu)于同類的FM技術和LC技術。在FA技術的基礎上,如何抑制那些對聚集結果影響較小的數(shù)據(jù)的傳輸是下一步的研究重點。

[1]尚鳳軍.無線傳感器網(wǎng)絡通信協(xié)議[M].北京:電子工業(yè)出版社,2011.

[2]Bista R,Chang J W.Privacy-Preserving Data Aggregation Protocols for Wireless Sensor Networks:A Survey[J].Sensors,2010,10(5):4577-4601.

[3]錢志鴻,王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡綜述[J].電子與信息學報,2013,35(1):215-227.

[4]呂方旭,張金成,石洪君,等.WSN中的分布式壓縮感知[J].傳感技術學報,2013,26(10):1446-1452.

[5]于博,李建中.無線傳感器網(wǎng)絡上數(shù)據(jù)聚集及調(diào)度研究綜述[J].智能計算機與應用,2013,3(4):5-9.

[6]Li X Y,Wang Y,Wang Y.Complexity of Data Collection,Aggrega-tion and Selection for Wireless Sensor Networks[J].Computers,IEEE Transactions on,2011,60(3):386-399.

[7]Bagaa M,Challal Y,Ksentini A,et al.Data Aggregation Scheduling Algorithms in Wireless Sensor Networks:Solutions and Challenges[J].Communications Surveys and Tutorials,IEEE,2014,16(3):1339-1368.

[8]Madden S,Franklin M J,Hellerstein J M,et al.TAG:A Tiny Aggregation Service for Ad Hoc Sensor Networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.

[9]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.ACM,2004:250-262.

[10]童孟軍,李光輝,徐小良.基于分簇的能量有效多路徑路由協(xié)議的研究[J].傳感技術學報,2013,26(8):1126-1134.

[11]Mohammad Hossein Anisi,Abdul Hanan Abdullah,Shukor Abd Razak.Energy-Efficient Data Collection in Wireless Sensor Networks[J].Wireless Sensor Network,2011(3):329-333.

[12]黃萬德.無線傳感器網(wǎng)絡中采用線性技術的數(shù)據(jù)融合算法研究[D].浙江工業(yè)大學,2012.

[13]Considine J,Hadjieleftheriou M,Li F,et al.Robust Approximate Aggregation in Sensor Data Management Systems[J].ACM Transactions on Database Systems(TODS),2009,34(1):1-35.

[14]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.ACM,2005:287-298.

[15]Flajolet P,Nigel Martin G.Probabilistic Counting Algorithms for Data Base Applications[J].Journal of Computer and System Sciences,1985,31(2):182-209.

[16]Whang K Y,Vander Zanden B T,Taylor H M.A Linear Time Probabilistic Counting Algorithm for Database Applications[J].ACM Transactions on Database Systems(TODS),1990,15(2):208-229.

A Kind of Data Aggregation Technology Based on Linear Time Probabilistic Counting Algorithm*

YINGKezhen1,2,WUJinbin1,DAIGuoyoong1,MIAOChunyu1,FANCongling1,CHENQingzhang1*

(1.Department of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310014,China;2.DongFAng College,Zhejiang University of Finance and Economics,Haining Zhejiang 314408,China)

Using data aggregation technique to pre-processing the data on intermediate nodes in the wireless sensor networks can remove a lot of redundant information,reduce data transmission and save energy.But sensor readings will be over-counted through multipath aggregation computing.To solve this problem,a new data aggregation technique named FA(Fan Aggregation)is proposed.Basing on the mathematical model of linear time probabilistic counting algorithm,FA optimizes the specific properties of the duplicate-insensitive synopsis.Theory analysis and simulation results show that FA technique performances better both in storage space and accuracy than FM(Flajolet Martin)and LC(Linear Counting)techniques.

wireless sensor network;data aggregation;synopsis;over-counting

應可珍(1978-),女,講師,在讀博士,主要研究方向是無線傳感器網(wǎng)絡;

陳慶章(1956-),男,教授,博士生導師,主要研究方向是無線傳感器網(wǎng)絡、分布式處理與協(xié)同工作等。

項目來源:國家自然科學基金項目(61379023)

2014-09-26 修改日期:2014-11-14

C:6150P

10.3969/j.issn.1004-1699.2015.01.018

TP393

A

1004-1699(2015)01-0099-08