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

應(yīng)可珍,鄔錦彬,戴國(guó)勇苗春雨,范聰玲,陳慶章*

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

?

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

應(yīng)可珍1,2,鄔錦彬1,戴國(guó)勇1苗春雨1,范聰玲1,陳慶章1*

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

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

無(wú)線傳感器網(wǎng)絡(luò);數(shù)據(jù)聚集;概要結(jié)構(gòu);重復(fù)計(jì)數(shù)

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

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

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

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

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

2 FA技術(shù)

2.1 網(wǎng)絡(luò)定義和問(wèn)題描述

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

圖1 環(huán)形拓?fù)浣Y(jié)下的Synopsis Diffusion

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

2.2 FA的數(shù)據(jù)結(jié)構(gòu)和基本操作

如下定義1針對(duì)FA概要結(jié)構(gòu)進(jìn)行了具體定義。

定義1FA概要結(jié)構(gòu)由一對(duì)參數(shù)(ε,δ)保證精度,由d個(gè)長(zhǎng)度為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é)構(gòu)中的傳感器讀值表示

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

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

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

②求和操作

若有兩個(gè)概要結(jié)構(gòu)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)聚集

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

2.3 FA聚集方案

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

圖3 層次型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

2.4 FA估計(jì)值

當(dāng)聚集數(shù)據(jù)匯聚到基站時(shí),由基站計(jì)算出整個(gè)網(wǎng)絡(luò)的最終聚集值FAfinal。用式(1)來(lái)表示的n的估計(jì)值:

(1)

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

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

(2)

2.5 d和l的設(shè)置

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

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

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

引理1 在每個(gè)FA[i]結(jié)構(gòu)里,至多有k個(gè)映射,i=0,…,d-1。

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

(3)

(4)

(5)

然后,

(6)

(7)

2.6 算法實(shí)例

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

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

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

圖4 FA概要結(jié)構(gòu)

圖5 FA聚集過(guò)程

圖6 FA聚集傳輸

圖7 FA最終聚集值的近似估計(jì)過(guò)程

3 理論分析與仿真實(shí)驗(yàn)

3.1 性能分析

①聚集技術(shù)所占空間大小

基于FM技術(shù)的算法[9,13,15]利用多路徑路由方案,采用多個(gè)FM概要結(jié)構(gòu)和PCSA技術(shù)進(jìn)行聚集操作。基于LC技術(shù)的算法[12,16]創(chuàng)建一個(gè)LC概要結(jié)構(gòu)用于聚集計(jì)算。FA技術(shù)用FA概要結(jié)構(gòu)表示讀值和聚集操作,并用FA估計(jì)作最終的聚集估計(jì)操作。

②概要結(jié)構(gòu)圖比較

圖8 概要結(jié)構(gòu)圖

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

表1 聚集技術(shù)與空間大小

③概要結(jié)構(gòu)大小與n的關(guān)系

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

圖9 概要結(jié)構(gòu)大小與n的關(guān)系

3.2 仿真實(shí)驗(yàn)

仿真采用MATLAB作為仿真平臺(tái),同時(shí)將FA技術(shù)與FM技術(shù)和LC技術(shù)作比較。這些技術(shù)都采用多路徑路由技術(shù)以提高聚集的健壯性并且均是對(duì)副本不敏感的概要結(jié)構(gòu)。本例中以Sum聚集為例來(lái)比較概要結(jié)構(gòu)和聚集查詢的性能。

圖10 7×7網(wǎng)絡(luò)的路由拓?fù)鋱D

①實(shí)驗(yàn)參數(shù)設(shè)計(jì)

②性能衡量指標(biāo)

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

(8)

對(duì)于置信度,本仿真實(shí)驗(yàn)只取精度約束條件(ε,δ)中的δ作為自變量,因δ值的大小直接影響概要結(jié)構(gòu)的大小,并會(huì)對(duì)傳輸功耗造成影響。

③仿真結(jié)果與分析

按照實(shí)驗(yàn)參數(shù)設(shè)計(jì)和性能衡量指標(biāo),這里選取FM技術(shù)和LC技術(shù)作為比較對(duì)象,下面分別從仿真結(jié)果的3個(gè)角度進(jìn)行說(shuō)明。仿真結(jié)果如圖11和圖12所示。

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

圖11 節(jié)點(diǎn)對(duì)傳輸功耗影響

圖12 約束條件對(duì)傳輸功耗的影響

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

4 結(jié)束語(yǔ)

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

[1]尚鳳軍.無(wú)線傳感器網(wǎng)絡(luò)通信協(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ú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào),2013,35(1):215-227.

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

[5]于博,李建中.無(wú)線傳感器網(wǎng)絡(luò)上數(shù)據(jù)聚集及調(diào)度研究綜述[J].智能計(jì)算機(jī)與應(yīng)用,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].傳感技術(shù)學(xué)報(bào),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àn)德.無(wú)線傳感器網(wǎng)絡(luò)中采用線性技術(shù)的數(shù)據(jù)融合算法研究[D].浙江工業(yè)大學(xué),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

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

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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(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