郭龍江,任美睿,李金寶,范文彬

(1.黑龍江大學 計算機科學技術(shù)學院,哈爾濱 150080;2.黑龍江省數(shù)據(jù)庫與并行計算重點實驗室,哈爾濱 150001)

0 引 言

在無線傳感器網(wǎng)絡(luò)中,最小化數(shù)據(jù)聚集延遲問題 (MDAL,Minimum Data Aggregation Latency)是個非常重要的研究課題[1-2]。例如,在一個森林火災(zāi)監(jiān)控系統(tǒng)中,需要把監(jiān)測到的數(shù)據(jù)及時地進行數(shù)據(jù)聚集,以便發(fā)現(xiàn)異常,避免遲報火災(zāi)。因此,最小化數(shù)據(jù)聚集延遲問題(MDAL)對于及時獲取監(jiān)視區(qū)域內(nèi)的異常,避免災(zāi)害發(fā)生或降低災(zāi)害損失都有著舉足輕重的意義。

MDAL問題可以通過獲得數(shù)據(jù)聚集調(diào)度的方法來解決[1-2]。對于給定的一個由若干個傳感器節(jié)點組成的傳感器網(wǎng)絡(luò),假設(shè)每個節(jié)點都有一個需要聚集的數(shù)據(jù),數(shù)據(jù)聚集調(diào)度是由所有節(jié)點所形成的l個不相交的調(diào)度集合,每個調(diào)度集合中的節(jié)點可以同時傳輸數(shù)據(jù)而相互之間不沖突,l×T為整個網(wǎng)絡(luò)中數(shù)據(jù)聚集完成所花費的時間,這里T是傳感器節(jié)點傳輸一個數(shù)據(jù)包所要花費的時間。顯然,T是固定的,為研究方便,理論上就將l作為整個網(wǎng)絡(luò)中數(shù)據(jù)聚集完成所花費的時間。本文研究的問題就是通過減少傳輸調(diào)度集合的個數(shù)l,從而使數(shù)據(jù)聚集延遲減少。

近年來,數(shù)據(jù)聚集調(diào)度問題被廣泛研究。最早,由文獻 [1]給出一個延遲上界為(Δ-1)R的算法,這里的Δ為網(wǎng)絡(luò)中的節(jié)點最大度 (即一個通信半徑內(nèi)鄰居節(jié)點的最大個數(shù)),R為網(wǎng)絡(luò)半徑(網(wǎng)絡(luò)中每個節(jié)點都有一個到Sink的最小跳數(shù),網(wǎng)絡(luò)中必有一個節(jié)點u使得其到Sink的最小跳數(shù)最大,則稱節(jié)點u到Sink的最小跳數(shù)為網(wǎng)絡(luò)半徑)。文獻[2]給出一個延遲上界為23R+Δ-18的算法,但是文獻 [2]給出的沖突定義有誤,本文給予糾正。本文給出一個最大延遲為15R+Δ-15的算法并與文獻 [1]的算法和文獻 [2]的糾正算法進行比較,驗證了不論R和Δ如何變化,本文算法都要優(yōu)于文獻 [1]和文獻 [2]的算法。

1 問題描述

本文與文獻 [1],文獻 [2]的背景完全相同,考慮的是布置在一個平面上的靜態(tài)無線傳感器網(wǎng)絡(luò),即該網(wǎng)絡(luò)由n個固定的傳感器節(jié)點和一個Sink構(gòu)成,網(wǎng)絡(luò)拓撲不隨時間變化。如果網(wǎng)絡(luò)拓撲隨時間動態(tài)變化,則應(yīng)該研究分布式的降低傳感器網(wǎng)絡(luò)數(shù)據(jù)聚集延遲的調(diào)度算法,這是另一個研究課題,不在本文的討論范圍之內(nèi)。

本文假設(shè)每個節(jié)點具備時間同步能力且知道自己在網(wǎng)絡(luò)中的位置,Sink知道所有節(jié)點的位置和ID,所有節(jié)點的通信半徑相同。網(wǎng)絡(luò)的拓撲圖用G (V,E)表示,V是網(wǎng)絡(luò)中節(jié)點的集合,E為邊集合。如果E中存在邊(u,υ),那么當且僅當節(jié)點u與節(jié)點υ可以通信。

定義1.傳輸調(diào)度 u→υ稱為一個傳輸調(diào)度,表示 u可以發(fā)送數(shù)據(jù)到v,這里 u稱為發(fā)送者(Sender),v稱為接收者 (Receiver)。

定義2.傳輸調(diào)度的發(fā)送者集合 設(shè)S是一個傳輸調(diào)度集合,S={u1→υ1,u2→υ2,…,un→υn},則Sender(S)={u1,u2,…,un}稱為傳輸調(diào)度集合S的發(fā)送者集合,記為Sender(S)。

本文假設(shè)網(wǎng)絡(luò)采用單信道進行通信,即在一個固定時刻,每個節(jié)點不能同時接收和發(fā)送,節(jié)點要么接收,要么發(fā)送。傳感器節(jié)點可以與以它為中心、通信半徑內(nèi)的所有鄰居節(jié)點通信。當節(jié)點u與向它的一個鄰居節(jié)點υ發(fā)送數(shù)據(jù)時,這一數(shù)據(jù)也會同時發(fā)送到節(jié)點u的所有鄰居節(jié)點。在同一時刻如果有兩個或兩個以上的發(fā)送者發(fā)送的數(shù)據(jù)同時到達一個節(jié)點u,那么節(jié)點 u就不能接收到這些數(shù)據(jù),這叫做沖突。圖 1顯示了兩種可能的沖突。圖1 (a)中,u→v和x→v在同一時刻發(fā)生,則v就不能接收到u和x同時發(fā)送給v的數(shù)據(jù);圖1(b)中,u→v和x→y在同一時刻發(fā)生,由于v是x的鄰居,當x把數(shù)據(jù)發(fā)給y的同時,v也接收到了x發(fā)給y的數(shù)據(jù),則v就不能接收到u同時發(fā)送給v的數(shù)據(jù)。圖1(b)中的虛線表示v和x能通信。

圖1 兩種沖突Fig.1 Two kinds of conflicts

定義3.沖突 u→υ和x→y發(fā)生沖突當且僅當(v,x)∈E or(y,u)∈E,這里E為網(wǎng)絡(luò)拓撲的邊集合。

定義4.數(shù)據(jù)聚集調(diào)度 數(shù)據(jù)聚集調(diào)度就是傳輸調(diào)度集合的集合。M={S1,S2,…,Sl}稱為一個數(shù)據(jù)聚集調(diào)度,Si(i=1,2,…,l)是一個傳輸調(diào)度集合,且滿足:

1)Si(i=1,2,…,l)中的任何兩個傳輸調(diào)度是不沖突的。

2)Sender(Si)∩Sender(Sj)=?,?i≠j,這里Sender(Si)表示Si的發(fā)送者集合。

最小化數(shù)據(jù)聚集調(diào)度問題(MDAL)描述如下:給定一個無線傳感器網(wǎng)絡(luò)的拓撲圖G=(V, E)以及一個Sink節(jié)點s∈V,找到一個數(shù)據(jù)聚集調(diào)度M={S1,S2,…,Sl},使得l最小。

這個問題已經(jīng)被證明為NP難問題[1]。本文給出一個近似算法,數(shù)據(jù)聚集延遲上界為15R+Δ-15。Δ是網(wǎng)絡(luò)的最大度,R是網(wǎng)絡(luò)半徑。

2 相關(guān)工作

在無線傳感器網(wǎng)絡(luò)中,廣播(Broadcast)和數(shù)據(jù)聚集 (Data aggregation)是最常用和最基本的操作。在上世紀80年代,人們對廣播算法進行了廣泛研究[3-14]。相比之下,數(shù)據(jù)聚集的重要意義一直沒有得到重視。在傳感器網(wǎng)絡(luò)中,數(shù)據(jù)聚集是每個節(jié)點的數(shù)據(jù)作為輸入,在網(wǎng)內(nèi)經(jīng)過計算得到一個或一些信息然后傳送到Sink的操作。近年來,有很多人在研究數(shù)據(jù)聚集[15-25],在研究中人們更關(guān)注如何節(jié)省能量。在文獻 [24],文獻 [25]中提出了用模型驅(qū)動來減少能量消耗的方法;文獻 [26]權(quán)衡了能量消耗和時間延遲,給出了一個均衡的算法;文獻 [27]給出一種啟發(fā)式算法,可以廣播和數(shù)據(jù)聚合;文獻 [28]為了節(jié)省能量和減少延遲給出了另一種啟發(fā)式算法,但是這些算法只給出了實驗結(jié)果,并沒有給出理論分析;文獻 [29]提出了一種隨機分布式數(shù)據(jù)聚集算法,時間延遲為O(log(n)),在這個模型中,他們假設(shè)傳感器節(jié)點的傳輸半徑可以不受任何限制地進行改變。這個假設(shè)對于傳感器節(jié)點的硬件設(shè)計是一個很大的挑戰(zhàn),而且后者在網(wǎng)絡(luò)規(guī)模很大時是不可能實現(xiàn)的。文獻 [30]給出了一種使能量消耗和傳輸可靠性最優(yōu)化的數(shù)據(jù)收集調(diào)度算法。以上的所有工作都沒有討論最小化數(shù)據(jù)聚集延遲問題。

與數(shù)據(jù)聚集調(diào)度最相關(guān)的工作是文獻 [1]和文獻 [2]。文獻 [1]證明了最小化數(shù)據(jù)聚集延遲問題為NP難問題并且給出了一個(Δ-1)-近似算法,Δ為網(wǎng)絡(luò)最大度。這個算法采用了計算最短路徑的方法將數(shù)據(jù)聚集到Sink。文獻 [2]給出另一個數(shù)據(jù)聚集調(diào)度算法,時間延遲為23R+Δ-18。R是網(wǎng)絡(luò)半徑,Δ為網(wǎng)絡(luò)最大度。這個算法引入了白點、黑點、藍點的概念,采用按照顏色傳輸?shù)恼{(diào)度方法,這些算法都存在很高的數(shù)據(jù)聚集延遲。本文給出一個時間延遲上界為15R+Δ-15的算法。

3 本文提出的算法

本節(jié)描述本文給出的算法,這個算法的時間延遲為15R+Δ-15。Δ是網(wǎng)絡(luò)的最大度;R是網(wǎng)絡(luò)半徑,比目前最好的算法[2]給出的23R+Δ-18能更有效地縮短數(shù)據(jù)聚集時間。相對于文獻 [1]給出的(Δ-1)R來說,當Δ很小時,本文提出的算法接近于文獻 [1],當Δ逐漸增大時,本文算法能更有效的縮短數(shù)據(jù)聚集延遲。

本文算法分為:①創(chuàng)建數(shù)據(jù)聚集樹(Data Aggregation Tree,簡稱DAT);②消減藍點;③生成傳輸調(diào)度集合;④生成數(shù)據(jù)聚集調(diào)度。②～④是本文核心。

3.1 創(chuàng)建數(shù)據(jù)聚集樹

本節(jié)采用文獻 [2]的思想來創(chuàng)建數(shù)據(jù)聚集樹(為敘述方便,以下簡稱DAT)。首先采用廣度優(yōu)先搜索策略來建立廣度優(yōu)先搜索樹 (Breadth First Search T ree,以下簡稱BFST),然后在此基礎(chǔ)上建立DAT。

首先,建立BFST。對于給定的網(wǎng)絡(luò)拓撲圖G (V,E)以及Sink節(jié)點s∈V,從s開始用廣度優(yōu)先搜索策略建立BFST,并對BFST分層,s節(jié)點為第0層,與第0層相連的為第1層,依此類推,直至V中的所有節(jié)點都掃描完,以s為根的BFST就建立完成。例如,圖2給出一個網(wǎng)絡(luò)拓撲圖G的實例,節(jié)點0為Sink節(jié)點。圖3給出了一個基于圖2的以節(jié)點0為根的BFST,每個節(jié)點頭上的數(shù)字表示該節(jié)點在BFST中的層數(shù),虛線表示兩個節(jié)點在圖G中的邊。

接下來,在BFST的基礎(chǔ)上建立DAT,這一階段分兩步:

1)從 BFST的根 s開始,按層的升序掃描BFST的所有節(jié)點,在第 i層中求出最大獨立集BL ACKi,并把獨立集中的節(jié)點涂成黑色,要求BL ACKi與BL ACKi-1相互獨立。初始時,根節(jié)點s涂成黑色,BLACK0={s},直至BFST的所有層都掃描完畢。例如,圖4是基于圖3的BFST建立的DAT,按層掃描完畢后產(chǎn)生的黑點集合(最大獨立集)為:BL ACK0={0},BLACK1={}, BL ACK2={7,8,9,10,11,12,13},BL ACK3 ={},BLACK4={20},BLACK5={22}。

2)按層的升序,從第2層開始掃描每一層的黑點集合,對于BLACKi中的一個節(jié)點v,找到v在BFST中的父親節(jié)點p(v),并將p(v)涂為藍色,對于藍點p(v),在它的同層或上層找一個與它相連的黑點dp(v)作為p(v)的父親節(jié)點,然后把邊(v,p(v))和(p(v),dp(v))加入到DAT中,直至BFST的所有層都掃描完畢。最后,所有沒有涂上顏色的節(jié)點稱為白點,為白點找一個黑點作為父親節(jié)點。例如,圖4是基于圖3的BFST建立的DAT。文獻[2]給出了建立DAT的詳細算法,限于篇幅這里不再贅述。

圖4 一個數(shù)據(jù)聚集樹(DAT)實例Fig.4 An example of DAT

3.2 消減藍點

文獻 [2]把生成數(shù)據(jù)聚集調(diào)度分為3個階段:①白點到黑點的聚集;②黑點到藍點的聚集;③藍點到黑點的聚集。通過對這3個階段的數(shù)據(jù)聚集延遲的分析,得出數(shù)據(jù)聚集延遲上界為23R+Δ-18。文獻 [2]數(shù)據(jù)聚集延遲的分析依賴對一個黑點一跳范圍內(nèi)藍點數(shù)目的估計,該藍點數(shù)目的估計越小,算法的數(shù)據(jù)聚集延遲越小。文獻 [2]證明了一個黑點一跳范圍內(nèi)最多有21個藍點,本文算法的核心思想就是通過減少一個黑點一跳范圍內(nèi)藍點數(shù)目來減少時延。本節(jié)通過定理2證明了一個黑點一跳范圍內(nèi)最多保留12個藍點就足夠了。

引理1[2].一個黑點兩跳范圍內(nèi)最多有21個黑點。

證明:詳見文獻[2]。

定理1[2].一個黑點一跳范圍內(nèi)最多有21個藍點。

證明:由引理1可知,一個黑點兩跳范圍內(nèi)最多有21個黑點,每個黑點有一個藍父親,當這21個黑點與該黑點相連的藍父親都不相同時,該黑點一跳范圍內(nèi)最多有21個藍點。定理1得證。

定義5.不相交 設(shè)與同一黑點S通過藍點間接相連的任意兩個黑點為x,y,x在DAT中的藍父親為p(x),y在DAT中的藍父親為p(y),如果x與p(y)不能通信且y與p(x)不能通信,則x與y不相交。

如圖5(a)所示,x與p(y)不能通信且y與p(x)不能通信,則黑點x與黑點y不相交。圖5(b)中y與p(x)能通信,則黑點x與黑點y相交。虛線表示y與p(x)在網(wǎng)絡(luò)拓撲中有邊相連,但是該邊不是DAT中的邊。

圖5 兩個黑點不相交與相交的情況Fig.5 Joint and disjoint black nodes

引理2.對于一個黑點S的兩跳范圍內(nèi)的任意兩個黑點x、y,如果x與y不相交,那么夾角xSy＞arccos(7/8)。

證明:為證明方便,假設(shè)一個傳感器節(jié)點的通信半徑為1。黑點S的兩跳范圍內(nèi)的任意兩個黑點一定在以黑點S為圓心,半徑為2的圓中,為敘述方便稱該圓為DS2。以黑點S為圓心,1為半徑的圓稱為DS1。

證明前先做一些準備工作:①如圖6(a)在DS2內(nèi)任選一個黑點 x,作一直線 xS,并延長xS與DS2交于一點A,與DS1交于一點F;②以 A點為圓心,1為半徑做一圓周與相交于兩點B和B′;③作直線BS與交于一點E。AB=1,AS =BS=2,根據(jù)余弦定理:

AB2=AS2+BS2-2AS×BS×cos∠ASB計算得∠ASB=arcos(7/8)。從S出發(fā)向以A為圓心的圓做切線(由于切線與SB,圖6(a)中沒有畫該切線),切線與AS夾角為30°,BS與AS夾角∠ASB=arcos(7/8)＜30°,因此BS必與DS2相交于兩點,無妨設(shè)離S最近的點為C;④做直線AC,AC=1,并且做平行于AB的直線CD交AS于D點。

現(xiàn)只需證明:圖6(a)中的扇形區(qū)域ASB內(nèi)不存在與x不相交的黑點。

反證法:假設(shè)在扇形區(qū)域ASB內(nèi)存在一個黑點y與x不相交?！鰽BC和△ABS都是等腰三角形,而且這兩個三角形有一個公共角∠ABS,因此△ABC和△ABS是相似三角形。AC=AB=1,AS =BS=2,根據(jù)比例BC/AB=AC/AS=0.5,因此BC=0.5,所以SC=SB-BC=1.5。DC是AB的平行線,所以△DSC是等腰三角形,DS=DC= 1.5,AD=AS-DS=0.5=BC,因此四邊形ABCD是等腰梯形。由AC=1可知,梯形區(qū)域ABCD內(nèi)任意兩點的最大距離為1。

圖6 兩個不相交黑點的夾角估計Fig.6 Angle estimation for two disjoint black nodes

DC和AB是平行線,所以△DSC和△ASB是相似三角形,DC/AB=SC/SB=3/4,因此,DC =3/4,CE=SC-SE=1.5-1=0.5。在△DCE中,由余弦定理知:

DE2=DC2+CE2-2DC×CE×cos∠DCE

又因為DC是AB的平行線,∠DCE=∠ABS,在△ABS中,由余弦定理知:

因此,DE=10/4＜AC=1,梯形區(qū)域CDFE內(nèi)的任意兩點的最大距離＜1。

綜合以上討論,梯形區(qū)域CDFE和梯形區(qū)域ABCD內(nèi)各自只能存在一個黑點,黑點 x在區(qū)域ABCD內(nèi),且在 AD上,那么黑點y一定在區(qū)域CDFE內(nèi)。因為黑點 x的合理區(qū)域是DS1之外和DS2之內(nèi),所以1＜xS≤2。

以下分兩種情況討論:xS≤1.75和 xS＞ 1.75。

1)當xS≤1.75時,根據(jù)余弦定理:

推出xE≤1。

E是區(qū)域CDFE內(nèi)距離x點最遠的點。因此,區(qū)域CDFE內(nèi)的所有點到x的距離≤1,這時y在區(qū)域CDFE的任何位置,x與y都能夠通信,與x與y是黑點矛盾,所以當xS≤1.75時,扇形區(qū)域ASB內(nèi)不存在與黑點x不相交的其他黑點。

2)當xS＞1.75時,設(shè)b為連接黑點x與黑點S的藍點,無妨設(shè)b在直線SA左側(cè),見圖6(b)。bx≤1且Sb≤1。以 x為圓心,1為半徑做一圓(該圓為黑點x的最大覆蓋范圍,為敘述方便稱此圓為Dx1)交DS2于點H,連接HS(如圖6(b)中所示的虛線)。以b為圓心,1為半徑做一圓(該圓為藍點b的最大覆蓋范圍,為敘述方便稱此圓為Db1)與圓Dx1交于P點(見圖6(b),注意P點不一定在虛線SH上)。

如果H點和P點不在圖6(a)中的扇形區(qū)域ASB內(nèi)部(可以在SB邊上),說明圖6(a)中的扇形區(qū)域ASB全部處在Dx1與Db1內(nèi)部,而Dx1與Db1內(nèi)部不存在與 x點不相交的黑點。這時y在區(qū)域CDFE的任何位置,x與y都能夠通信,這就與x與y是黑點矛盾。因此,當 xS＞1.75時,(圖6 (a)中)扇形區(qū)域ASB內(nèi)不存在與x點不相交的其他黑點。如圖6(b)所示,現(xiàn)只需證明:H點和P點不在圖6(a)中的扇形區(qū)域ASB內(nèi)部 (可以在SB邊上),就可得出結(jié)論:當xS＞1.75時,(圖6(a)中)扇形區(qū)域ASB內(nèi)不存在與x點不相交的其他黑點。

(I)首先證明:H點不在圖6(a)中的扇形區(qū)域ASB內(nèi)部(可以在SB邊上)。已知S H=2, 1.75＜xS≤2,xH=1,根據(jù)余弦定理:

得:cos∠ASH≤7/8,∠AS H≥arccos(7/8)=∠ASB。這就證明了H點不在如圖6(a)所示的扇形區(qū)域ASB內(nèi)部,但H點可以在直線SB上。

(II)接著證明:P點不在圖6(a)中的扇形區(qū)域ASB內(nèi)部(可以在SB邊上)。證明思路是:當∠ASP取最小值時,∠ASP＞∠ASB成立。

藍點b的合理活動區(qū)域為如圖6(b)所示的直線 AS左側(cè)的陰影區(qū)域內(nèi) (陰影區(qū)域是DS1與Dx1相交區(qū)域)。當 x點固定且b點在DS1與Dx1的交點上時 (該交點在直線AS左側(cè)),b距離邊xS最遠,此時xb=1,bS=1且∠ASP最小。根據(jù)余弦定理:

△xbP為等邊三角形,因此有:

由xb=1,bS=1得:cos∠bxS=xS/2。

綜合式(4)和式(6)得:

將式(7)代入式(3),再將式(3)代入式(2)得:

由式 (7)和cos∠bxS=xS/2得出xS=cos(60 -∠S xp),代入式 (8)∠Sxp被削去得出cos∠ASP=3/2,所以 ∠ASP=arcos(3/2)＞arcos(7/8)=∠ASB。這就證明了P點不在如圖6(a)所示的扇形區(qū)域ASB內(nèi)部。

綜合(I)(II)的討論得出結(jié)論:H點和P點不在圖6(a)中的扇形區(qū)域ASB內(nèi)部(可以在SB邊上),從而當xS＞1.75時,(圖6(a)中)扇形區(qū)域 ASB內(nèi)不存在與x點不相交的其他黑點。

綜上所述,無論xS≤1.75還是xS＞1.75,黑點y一定在區(qū)域CDFE內(nèi)都得出矛盾,因此假設(shè)在扇形區(qū)域ASB內(nèi)存在一個黑點y與x不相交是錯誤的。得證。

定義6.覆蓋 對于DAT=(Vd,Ed)中的一個藍點 x以及一個黑點y,如果x與y能通信且x.level＜y.level(level表示節(jié)點層數(shù)),則稱藍點x覆蓋黑點y。

定理2.在DAT=(Vd,Ed)中,最多12個藍點就可以把一個黑點兩跳范圍內(nèi)間接相連的所有黑點全部覆蓋。

證明:定理2的證明等價于證明一個黑點兩跳范圍內(nèi)最多有12個互不相交的黑點。采用反證法:假設(shè)在DAT=(Vd,Ed)中,一個黑點s兩跳范圍內(nèi)有13個互不相交的黑點。如圖7所示,對于黑點s兩跳范圍內(nèi)的某一個黑點A,連接 AS順時針旋轉(zhuǎn) arccos(7/8)到B點,逆時針旋轉(zhuǎn)arccos (7/8)°到C點,于是∠BSC=2arccos(7/8)＞57.9°,根據(jù)引理2小圓弧BC(從B點逆時針旋轉(zhuǎn)到C點形成的圓弧)內(nèi)不存在與A不相交的黑點。對大圓弧BC(從B點順時針旋轉(zhuǎn)到C點形成的圓弧)分成11等份,每份的弧度b=(360-∠BSC)/11＜27.46＜arccos(7/8)。把剩下的12個黑點分到11個相等的扇形內(nèi),根據(jù)鴿巢原理,至少有兩個黑點落到同一個扇形區(qū)域內(nèi),根據(jù)引理2,這兩個黑點必相交,這與13個黑點是互不相交的假設(shè)矛盾。

圖7 兩跳范圍內(nèi)的黑點覆蓋Fig.7 Black node coverage in two hops away

定義7.消減 給定一個DAT以及DAT中的一個黑點集合BLACK,與BL ACK中黑點相連的下級藍點集合記為BL={bl1,bl2,…,bln},BL中所有藍點覆蓋的黑點 (不包括BLACK中的節(jié)點)集合記為B={b1,b2,…,bm},如果存在藍點集合MB?BL,且MB中的藍點可以覆蓋B中所有的黑點,那么稱BL可以消減為MB。

在DAT中,由定理1知:一個黑點兩跳范圍內(nèi)的所有黑點,最多用21個藍點就可以覆蓋。而由定理2知:一個黑點的兩跳范圍內(nèi)與其間接相連的所有黑點,最多用12個藍點就可以覆蓋。本文的核心思想就是通過減少黑點一跳范圍內(nèi)藍點的數(shù)目來減少延遲。下面本文給出一個貪心算法 Reduce-Blue-Node來消減藍點。

Reduce-Blue-Node算法以DAT樹作為輸入,對DAT樹由Sink節(jié)點開始逐層向外掃描,對于第i層的黑點集合BL ACKi,得到與其相連的下級藍點集合BLi。Bi為被集合BLi覆蓋的黑點集合(不包括BL ACKi中的黑點)。Reduce-Blue-Node算法為BLi中每個藍點計算一個權(quán)值 (算法中的count變量),用來表示該藍點覆蓋集合Bi中黑點的個數(shù);接著在BLi集合中找count值最大的藍點b,這時集合Bi中被藍點b所覆蓋的所有黑點都變成b的孩子,也就是去除這些黑點與原來藍父親之間的邊,并連接到藍點b上。在集合BLi中去除藍點b,以及在Bi中去除被藍點b覆蓋的黑點,更新BLi中剩余藍點的 count值。依此方法做下去,直到Bi集合空為止,把BLi中剩余藍點變成白色,第i層消減完畢。當掃描完DAT中的所有的層,算法結(jié)束,返回消減后的數(shù)據(jù)聚集樹RDAT。Reduce-Blue-Node算法的偽代碼如Algorithm -1所示。

以圖4為例,首先對第0層進行消減, BLACK0={0},BL0={1,2,3,4,5,6},B0= {7,8,9,10,11,12,13},選擇count值最大的5號藍點,其 count值為3,5號藍點覆蓋黑點10, 11,12。黑點10,11,12變?yōu)?號藍點的孩子,即在算法中斷開 (v3,v10)、(v4,v11),連接 (v5, v10)、(v5,v11)。在BL0中去掉5號節(jié)點BL0更新為BL0={1,2,3,4,6},在B0中去掉被5號節(jié)點覆蓋的10,11,12節(jié)點更新為B0={7,8,9, 13}。在 BL0中選擇 count值最大的 6號藍點, count值為2,斷開 (v1,v7),連接 (v6,v7),更新BL0={1,2,3,4},B0={8,9},選擇count值為2的2號藍點,邊不變,更新BL0={1,3, 4},B0={},B0為空,把1,3,4號藍點變?yōu)榘c,第0層消減完畢。接下來以此方法對第1～5層進行消減,當所有層都消減完,算法結(jié)束,得到如圖8所示的數(shù)據(jù)聚集樹。

Algorithm-1 Reduce-Blue-Node Input:Network topology G=(V,E),Data Aggregation T ree DA T=(VDAT,EDAT),Sink node s. Output:Reduced Data Aggregation T ree RDAT=(VRDAT, ERDAT) 1.Procedure Reduce-Blue-Node(G,DAT,s) 2.VRDAT←V;ERDAT←EDAT 3.FOR i←0 to l DO 4.BLACKi←{The Black node in level i} 5.BLi←{Blue nodes which are children of BL ACKi} 6.Bi←{Black node covered by BLi} 7.FOR all blue node b in BLiDO 8.b.count←the number of nodes in Bicovered by b. 9.END FOR 10.WHILE Bi≠? DO 11.find a node b such that b.count is maximum in BLi 12.FOR all black j covered by b in BiDO //pDAT(j)is node j's father in DA T 13.remove(j,pDAT(j))from ERDAT; 14.add(b,j)into ERDAT; 15.remove j from Bi; 16.END FOR 17.remove b from BLi 18.update Blue nodes'count of BLi 19.END WHILE 20.Color Blue nodes of BLito White 21.END FOR 22.RET URN RDAT=(VRDAT,ERDAT) END

圖8 消減藍點后的數(shù)據(jù)聚集樹(RDAT)Fig.8 An example of RDAT after blue nodes are reduced

3.3 生成傳輸調(diào)度集合

RDAT建立成功后,接下來本節(jié)首先指出文獻[2]中的沖突定義是如何錯誤的,并給予糾正,然后給出Mini-Slot算法生成傳輸調(diào)度集合。

對于給定G=(V,E),節(jié)點u,vV,(u,p (u)),(v,p(v))E,p(u)、p(v)分別為u和v在RDAT中的父親節(jié)點,如果(p(u),v)E且(p(v),u)E,那么u,v不沖突。如圖9(a)、(b)所示,u和v分別向p(u)、p(v)發(fā)送數(shù)據(jù)包會產(chǎn)生沖突,因為(a)中u和v同時向p(u)和p (v)發(fā)數(shù)據(jù)包時,p(u)會同時收到u,v的數(shù)據(jù)包,產(chǎn)生沖突。同理(b)中u和v同時向p(u)和p(v)發(fā)數(shù)據(jù)包時,p(v)也會同時收到u,v的數(shù)據(jù)包。如果u,v沖突,那么他們不能在同一個調(diào)度集合中。而文獻[2]中只考慮了(p(u),v) E和(p(v),u)E其中的一種條件。例如在文獻[2]的算法中,對于某一傳輸調(diào)度集合S,假設(shè)u最先進入集合S中。當掃描到v時該算法只判斷是否滿足(p(u),v)E這個條件,那么對于圖9 (a),v不會加入S中,此時文獻 [2]的算法能得到正確的調(diào)度。但是對于圖9(b),由于(p(u), v)E,則v被加入了傳輸調(diào)度集合S,但實際上u與v是沖突的,所以發(fā)生了錯誤。文獻 [2]采用的是分層聚集策略產(chǎn)生數(shù)據(jù)聚集調(diào)度,由于文獻[2]的沖突定義出現(xiàn)錯誤,導致理論分析時白點聚集數(shù)據(jù)到黑點不能在 Δ-1個時刻內(nèi)完成。例如在圖10(a)給出的數(shù)據(jù)聚集樹中(實線表示數(shù)據(jù)聚集樹中的邊,虛線表示兩個節(jié)點能夠通信),這棵樹的 Δ=5,按照文獻 [2]的沖突定義和理論分析應(yīng)該在Δ-1=4個時刻內(nèi)完成。然而,根據(jù)本文給出的正確沖突定義并采用文獻 [2]給出的算法,白點向黑點傳輸聚集數(shù)據(jù)的傳輸調(diào)度集合為:S1= {9→6,10→7},S2={11→7,12→6},S3={13→8},S4={14→8},S5={15→8},S6={16→8},即需要6個時刻完成聚集。同理,在分析藍點到黑點和黑點到藍點的延遲上界時有同樣的錯誤。本文下面將給出一個Mini-Slot算法(Algorithm-2)來糾正這個錯誤。

圖9 沖突演示Fig.9 Demo for conflicts

Mini-Slot算法輸入包括3部分:候選發(fā)送節(jié)點集合Leaf,消減后的數(shù)據(jù)聚集樹RDAT和網(wǎng)絡(luò)的拓撲G=(V,E)。Mini-Slot算法返回一個由若干個傳輸調(diào)度集合組成的數(shù)據(jù)聚集調(diào)度M。

Mini-Slot算法中的Father集合為候選發(fā)送節(jié)點的父親節(jié)點集合。Other集合由RDAT中且不在Leaf集合內(nèi)的其他葉子節(jié)點構(gòu)成。對于該算法生成的第i個傳輸調(diào)度集合Si={}(i初值為1),對于Father集合中每個節(jié)點j(j作為接收者),算法從Leaf中選一個節(jié)點k使得k→j與Si中的傳輸調(diào)度不沖突,將k→j加入到Si中,把節(jié)點 k從Leaf中去掉;如果Leaf中不存在這樣的節(jié)點k,且節(jié)點j與Si中的所有發(fā)送節(jié)點不能通信,說明節(jié)點j的孩子與Si中的接收者能夠通信,那么把節(jié)點j的孩子變成這些接收者的孩子。

當節(jié)點j在Leaf集合中沒有孩子時,把j從Father集合中去掉,如果 j是當前RDAT的葉子,則把j加入Other集合;當Father集合掃描一遍后,得到Si,然后掃描一遍Other集合,對其中的節(jié)點m,如果滿足m→pRDAT(m)與Si不沖突,m→pRDAT(m)加入到Si中。對Other集合操作完畢,把 Si加入M中。算法重復上述過程,直到Leaf集合為空時算法結(jié)束。Mini-Slot算法運行結(jié)束,相當于把RDAT的所有葉子 (即Leaf中的節(jié)點)裁剪掉。Algorithm-2中給出了Mini-Slot的偽代碼。

例如圖10(a)所示,當前候選發(fā)送節(jié)點集合為:

首先對于節(jié)點6,9號節(jié)點可以發(fā)送,9→6加入S1中,然后是節(jié)點7,10→7號節(jié)點加入S1,節(jié)點8與當前發(fā)送者9和10沒有邊相連,則節(jié)點8可以接收,但是8號節(jié)點的孩子都不能發(fā),那么8號節(jié)點的孩子就更改其父親。8號節(jié)點的孩子為13,14,15,16,其中13,14與7號相連,15,16與6號相連,那么父子關(guān)系變成圖10(b)所示,9和10從Leaf中去掉,8由于沒有孩子,也從Father中去掉,第一遍掃描完Father得到S1={9→6,10→7}。然后對于 Leaf={11,12,13,14, 15,16},Father={6,7},重復上述過程,直到Leaf為空算法結(jié)束。最后得到,S2={11→7,12→6},S3={13→7,14→6},S4={15→6,16→7}。圖11顯示了以圖10(a)作為輸入Mini-Slot算法運行結(jié)束后裁剪完葉子的RDAT。

圖11 以圖10(a)作為輸入Mini-Slot算法運行后的RDATFig.11 A RDAT after running Mini-Slot using 10(a)as input

定理3.給定一個候選發(fā)送節(jié)點集合Leaf= {l1,l2,…,ln},Leaf中所有節(jié)點的父親集合為Father={f1,f2,…,fm},Father集合中節(jié)點通信范圍內(nèi)的候選節(jié)點的個數(shù)為 {d1,d2,…, dm}。令Max{d1,d2,…,dm}=D,則Leaf中的節(jié)點作為發(fā)送者,Father中的節(jié)點作為接收者,通過Mini-Slot算法所形成的不沖突的傳輸調(diào)度集合最多有D個。

證明:首先,對于 Father={f1,f2,…, fm},d1,d2,…,dm分別是 f1,f2,…,fm的通信范圍內(nèi)的候選發(fā)送節(jié)點的個數(shù)。Max{d1,d2,…,dm}=D。根據(jù)Mini-Slot算法的描述,掃描一遍Father集合生成一個傳輸調(diào)度集合。

Algorithm-2 Mini-Slot Input:Candidate Sender Set Leaf,Topology of Network G= (V,E),Reduced Data Aggregation Tree RDA T=(VRDAT, ERDAT) Output:Data Aggregation Schedule M. 1.Procedure Mini-Slot(Leaf,G,RDA T) 2.i←1,M←?,Father←? 3.FOR l Leaf DO 4.add pRDAT(l)to Father;//pRDAT(l)is l's father in RDAT 5.END FOR 6.WHILE Lea f≠? T HEN 7.Si←? 8.Other←{Leaves of RDA T but not in Leaf}; 9.FOR j Father DO 10.find a node k from Leaf which a child of j such that k→j conflict-free with all transmission schedule in Si 11.IF k exists in Leaf THEN 12.add k←j to Si; 13.remove k from Leaf; 14.remove(k,j)from ERDAT; 15.ELSE//k does not exist in Leaf 16.IF does not exist node t which in Sender(Si)can connect with j//T his means j can receive data 17.THEN 18.remove j from Father 19.FOR each j's child t in Lea f DO 20.find a node x from Father can connect with t 21.add(x,t)into ERDAT; 22.remove(t,j)from ERDAT; 23.END FOR 24.IF j's all children are not in Leaf 25.THEN remove j from Father 26.IF j is a leaf in RDA T 27.THEN add j to Other 28.END FOR//corresponds to FOR j Father DO 29.FOR m Father DO 30.IF m→pRDAT(m)conflict-free with all transmission schedule in Si 31.THEN 32.add m→pRDAT(m)to Si; 33.remove(m,pRDAT(m))from ERDAT;

34.END FOR 35.add Siinto M 36.i→i+1 37.END WHILE 38.RETU RN M END

對于Father中的fk:(1)如果fk與Si中的至少一個發(fā)送節(jié)點有邊相連,并且該發(fā)送節(jié)點已從Leaf中刪除,那么 fk對應(yīng)的dk在這次掃描中至少減少1;(2)如果fk與當前調(diào)度集合Si的發(fā)送者無邊相連,那么在 fk的孩子節(jié)點中找一個與調(diào)度集合Si不沖突的發(fā)送節(jié)點lj:(2.1)如果Leaf中存在這樣的lj,把lj→fk加入到Si中,并把lj從Leaf中刪除,那么dk減1;(2.2)如果Leaf中不存在這樣的lj,說明 fk任意孩子節(jié)點都與Si的某個接受者有邊相連,那么把 fk從Father中去除,dk置0,并為 fk的孩子節(jié)點在集合Father中重新找一個父親節(jié)點,該操作并不改變 d1,d2,的值。

綜合(1)(2),經(jīng)過一遍掃描Father集合產(chǎn)生一個調(diào)度集合,{d1,d2,…,dm}中的每個值都至少減1。而Max{d1,d2,…,dm}=D,所以最多掃描Father集合D次就可以把 {d1,d2,…,dm}的所有值都置0。當 {d1,d2,…,dm}的值全部置0時,說明Leaf當前為空。每掃描一次Father集合產(chǎn)生一個傳輸調(diào)度集合,因此以Leaf中的節(jié)點作為發(fā)送者,Father集合中的節(jié)點作為接收者所形成的不沖突的傳輸調(diào)度集合最多有D個。證畢。

例如,圖10(a)所示的樹其中Leaf={9, 10,11,12,13,14,15,16},Father={f1=6, f2=7,f3=8},相應(yīng)的d1=4,d2=4,d3=4。根據(jù)Mini-Slot算法最多用4個傳輸調(diào)度集合把Leaf集合中節(jié)點信息聚集到Father集合中。

3.4 數(shù)據(jù)聚集調(diào)度生成算法

本節(jié)首先基于Mini-Slot算法給出數(shù)據(jù)聚集調(diào)度生成算法Data-Aggregation-Schedule,然后給出該算法的時間延遲理論分析。

Data-Aggregation-Schedule算法在 RDAT的基礎(chǔ)上生成數(shù)據(jù)聚集調(diào)度,主要分為以下兩個步驟:

1)原始RDAT樹的所有葉子節(jié)點(包括白色節(jié)點和黑色葉子節(jié)點)作為候選發(fā)送節(jié)點集合,應(yīng)用Mini-Slot算法把數(shù)據(jù)聚集到RDAT樹的內(nèi)層。

2)對經(jīng)過1)裁剪過后的RDAT樹按層從外向內(nèi)聚集,先把最外層的藍色葉子節(jié)點作為候選發(fā)送節(jié)點應(yīng)用Mini-Slot算法產(chǎn)生數(shù)據(jù)聚集調(diào)度,把信息聚集到內(nèi)層,然后再把外層的黑色葉子節(jié)點作為候選發(fā)送節(jié)點Mini-Slot算法產(chǎn)生聚集調(diào)度,把信息聚集到內(nèi)層。重復2),直到所有節(jié)點的信息都聚集到Sink節(jié)點為止。

Algorithm-3給出了 Data-Aggregation-Schedule算法。對于圖8所示的RDAT產(chǎn)生數(shù)據(jù)聚集調(diào)度,第一輪得到S1={1→0,8→2,12→5, 15→9,16→10,19→11},從RDAT中裁剪掉S1中的所有發(fā)送節(jié)點,進行第二輪聚集調(diào)度生成S2= {3→0,7→6,11→5,22→21},依此律推一共進行7輪數(shù)據(jù)聚集調(diào)度過程:S3={4→0,17→6,13→10,21→20},S4={6→0,18→10,20→14},S5= {10→5,14→9},S6={5→0,9→2},S7={2→0}。最后得到7個調(diào)度集合,所以該例用7個時刻就能完成數(shù)據(jù)聚集。

Algorithm-3 Data-Aggregation-Schedule Input:Topology of Network G=(V,E), Output:Data Aggregation Schedule M. 1.Construct Breadth First Search T ree BFST; 2.Construct Data Aggregation Tree DAT; 3.RDA T←Reduce-Blue-Node(G,DAT,s); 4.Leaf←{i|i is a leaf of RDAT}; 5.M←M∪Mini-Slot(Leaf,G,RDAT); 6.FOR j←deep to 1 DO 7.Leaf←{i|i is RDA T's blue node which is a leaf}; 8.M←M∪Mini-Slot(Leaf,G,RDAT); 9.Leaf←{i|i is RDAT's black node which is a leaf}; 10.M←M∪Mini-Slot(Leaf,G,RDAT); 11.END FOR End

4 數(shù)據(jù)聚集調(diào)度生成算法的理論分析

本節(jié)對Data-Aggregation-Schedule算法的時間延遲進行理論分析。

引理3.一個藍點的通信半徑內(nèi),以該藍點為頂點的任意兩個黑點的夾角＞60°。

證明:如圖12所示,不妨設(shè)S為藍點,通信半徑為1,A,B為S通信范圍內(nèi)的黑點,A與B通過S的夾角為θ。那么根據(jù)余弦定理:cosθ=因為A和B都是黑點,相互獨立,c＞1。所以又因A,B都在S的通信范圍內(nèi),所以a≤1,b≤1。不妨設(shè)a≤b,令,f所以a=b是f(a)取最大值,b≤1,所以 f(a)≤60°,S通信半徑內(nèi)的任意兩個黑點通過S的夾角＞60°。證畢。

圖12 兩個黑點的最小夾角Fig.12 Minimum angle between two black nodes

定理4.一個藍點的通信半徑內(nèi)最多有5個黑點。

圖13 一跳范圍內(nèi)黑點分布Fig.13 Black nodes distribution in one hop away

證明:反正法:假設(shè)一個藍點的通信范圍內(nèi)可以有6個黑點。如圖13(a)所示,對于S通信半徑內(nèi)的某個黑點A,以S為圓心順時針、逆時針各旋轉(zhuǎn)60°,使得 x1SA,ASx2=60°;根據(jù)引理1, x1Sx2這段扇形區(qū)域內(nèi)不能有其他黑點;把剩下的扇形x1x3x4x5x2區(qū)域 (圖13(b))平均分成4份,則每個扇形區(qū)域的夾角為60°。除去黑點 A,剩下的5個黑點必落入這4個扇形中,根據(jù)鴿巢原理,必然有兩個黑點落入一個小扇形區(qū)域內(nèi),由于每個小扇形的夾角＜60°,與引理3矛盾,所以一個藍點的通信范圍內(nèi)的黑點個數(shù)要＜6個,與假設(shè)矛盾,定理4得證。

下面分析一下本文的 Data-Aggregation-Schedule算法在最壞情況下的時間延遲上界為15R +Δ-15。

根據(jù)Algorithm-3,已知圖G的最大度為Δ,那么RDAT最外層的葉子節(jié)點的父親的通信范圍內(nèi)的候選節(jié)點的個數(shù)不會超過 Δ-1,因為這些父親節(jié)點(除了Sink之外)都有一個父親節(jié)點,那么應(yīng)用Mini-Slot算法根據(jù)定理3最多用Δ-1個時刻就能把這些節(jié)點的數(shù)據(jù)聚集到內(nèi)層。所有的葉子節(jié)點(包括所有白色節(jié)點和部分黑色節(jié)點)被裁剪之后,RDAT中只剩下藍點和黑點。根據(jù)Algorithm-3,R是網(wǎng)絡(luò)半徑,先從藍點到黑點進行數(shù)據(jù)聚集,再從黑點到藍點進行數(shù)據(jù)聚集。根據(jù)定理2,任意一個黑點b一跳范圍內(nèi)最多有12個藍點,每個黑點都需要與一個藍父親相連,那么需要向黑點b聚集的藍點最多有11個 (向Sink節(jié)點聚集的藍點最多可以有12個)。根據(jù)定理3,藍點聚到黑點b最多需要11個時刻。根據(jù)定理4,藍點1跳范圍內(nèi)最多有5個黑點,去掉與上層相連的一個黑點,需要向藍點聚集的黑點最多4個,根據(jù)定理3,黑點聚集到藍點最多需要4個時刻。由RDAT可知,只有第2到R層可能存在黑點,第1到R-1層可能存在藍點,那么RDAT中最多有(R-1)層需要將數(shù)據(jù)聚集到黑點,最多有(R-1)層需要將數(shù)據(jù)聚集到藍點,最后Sink周圍最多有12個藍點,需要12個時刻,再加上白點向內(nèi)層聚集的Δ-1個時刻,最多需要Δ-1+(R-2)11+12+(R -1)4=15R+Δ-15個時刻。

定理5.Data-Aggregation-Schedule算法的近似比為16。

證明:對給定的網(wǎng)絡(luò)拓撲G=(V,E),網(wǎng)絡(luò)半徑為R,網(wǎng)絡(luò)的最大度為 Δ,那么最優(yōu)聚集延遲Latency滿足:Latency max(R,Δ),則近似比r =(15R+Δ-15)/Latency

當R時,r 15

當Δ時,r 1

當R,Δ時,r 16證畢

5 實 驗

本文算法將與文獻 [1],文獻 [2](糾正沖突定義后)所提出的算法在各種不同的拓撲結(jié)構(gòu)下的數(shù)據(jù)聚集延遲進行比較,主要針對節(jié)點個數(shù)變化、通信半徑變化、網(wǎng)絡(luò)的度變化和網(wǎng)絡(luò)半徑變化,在這些不同的拓撲圖中比較數(shù)據(jù)聚集延遲,衡量標準為數(shù)據(jù)聚集調(diào)度集合的個數(shù),調(diào)度集合個數(shù)越少,說明聚集延遲越小。

首先,考察節(jié)點個數(shù)變化對聚集延遲的影響。把傳感器節(jié)點隨機的布置在200 m×200 m的范圍內(nèi),每個節(jié)點的通信半徑相同。3種算法在同樣的網(wǎng)絡(luò)拓撲結(jié)構(gòu)下進行比較,節(jié)點變化范圍從500個增長到1 900個,增幅為100,每個節(jié)點的通信半徑為25 m,Sink節(jié)點在矩形區(qū)域的頂點位置。對于節(jié)點數(shù)n=500,600,…,1 900,每個n本文隨機生成30個拓撲圖,延遲分別取30個不同的拓撲圖的聚集延遲的平均值,實驗結(jié)果如圖14。

圖14 節(jié)點個數(shù)變化對聚集延遲的影響Fig.14 Effect of number of nodes

如圖14所示,在200 m×200 m區(qū)域內(nèi)節(jié)點個數(shù)不斷增加的情況下,網(wǎng)絡(luò)半徑不變,網(wǎng)絡(luò)的最大度不斷增加。本文算法的聚集延遲要比更正的Huang算法平均快2～3倍,在節(jié)點比較密時,比Chen算法要快得多,所以本文算法在節(jié)點個數(shù)變化的條件下延遲要比目前的算法要快。

接著,考察通信半徑變化對數(shù)據(jù)聚集延遲的影響,下面,在 200 m×200 m區(qū)域內(nèi),隨機放置2 000個節(jié)點,節(jié)點的通信半徑從20 m到62 m變化,同第一個實驗一樣,每組30個隨機圖,延遲分別取30個不同的拓撲圖的聚集延遲的平均值。實驗結(jié)果見圖15。

圖15 通信半徑變化對聚集延遲的影響Fig.15 Effect of radio range

當通信半徑增加時,節(jié)點密度增加,網(wǎng)絡(luò)的度也隨著增加,網(wǎng)絡(luò)半徑減少,本文算法比Huang算法要快2倍左右,比Chen算法要快2～3倍。

單獨考察網(wǎng)絡(luò)的最大度變化對數(shù)據(jù)聚集延遲的影響。顯然,在固定范圍內(nèi)隨機布置節(jié)點,網(wǎng)絡(luò)半徑是保持不變的,當節(jié)點數(shù)不斷增加,網(wǎng)絡(luò)的度隨之增加。同樣,把節(jié)點隨機布置在200 m×200 m范圍內(nèi),節(jié)點個數(shù)不斷增加,然后以網(wǎng)絡(luò)的度最大值為基準,在每個網(wǎng)絡(luò)度的固定值取30個圖,然后延遲取平均值,實驗結(jié)果見圖16。實驗結(jié)果與第一個實驗類似。

最后本文考察網(wǎng)絡(luò)半徑變化對數(shù)據(jù)聚集延遲的影響。要保證網(wǎng)絡(luò)半徑變化,而網(wǎng)絡(luò)的度不變,通信半徑不變,那么節(jié)點個數(shù)和節(jié)點所布置的區(qū)域必須同時變化。因為是隨機布置節(jié)點,所以本文可以給出一個近似公式,來表示網(wǎng)絡(luò)半徑R、網(wǎng)絡(luò)最大度Δ、通信半徑r、區(qū)域面積S(矩形區(qū)域)、節(jié)點個數(shù)n之間的關(guān)系:

根據(jù)這個關(guān)系,本文考察當Δ=12,r=25 m, R從10～20 m變化,實驗結(jié)果見圖17。

由圖17可見,Chen算法和 Huang算法都趨于線性增長,因為他們的算法根據(jù)分層的思想,本文提出的算法上界是15R+Δ-15,但是一般情況下延遲遠遠小于這個值,這是因為對于給定的拓撲建立一棵RDAT樹且采用Mini-Slot算法,將盡可能多的減少數(shù)據(jù)聚集延遲。

6 結(jié) 語

本文糾正了文獻 [2]的錯誤,并且提出一個新的降低數(shù)據(jù)聚集延遲的調(diào)度算法,通過消減藍點和Mini-Slot算法,給出一個近似比為16的近似算法。大大地降低了在傳感器網(wǎng)絡(luò)中數(shù)據(jù)聚集延遲,理論分析表明本文的算法的時間延遲上界為15R+Δ-15。通過實驗驗證了本文算法優(yōu)于當前的算法。

[1]X.H.X.Chen,and J.Zhu.Minimum data aggregation time problem in wireless sensor networks[C]// Proceedings of the 1st Int' l Conference on Mobile Adhoc and Sensor Networks,Beijing,China.2005:133-142.

[2]P.-J.W.S.C.-H.Huang,C.T.Vu,Y.Li,et al.Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C]//Proceedings of the IEEE INFOCOM'07,Anchorage,Alaska, USA.2007:366-372.

[3]N.Alon,A.Bar-Noy,N.Linial,et al.A lower bound for radio broadcast[J].Journal of Computer and System Sciences,1991,43(2):290-298.

[4]R.Bar-Yehuda,O.Goldreich,and A.Itai.On the time-complexity of broadcast in multi-hop radio networks:An exponential gap between determinism and randomization[J].Journal of Computer and System Sciences,1992,45(1):104-126.

[5]D.Bruschi and M.Del Pinto.Lower bounds for the broadcast problem in mobile radio networks[J].Distributed Computing,1997,10(3):129-135.

[6]I.Chlamtac and S.Kutten.On broadcasting in radio networks-problem analysis and protocol design[J]. IEEE Transactionson Communications,1985,33 (12):1 240-1 246.

[7]I.Chlamtac and O.Weinstein.The wave expansion approach to broadcasting in multihop radio networks[J]. IEEE T ransactions on Communications,1991,39(3): 426-433.

[8]M.Elkin and G.Kortsarz.Logarithmic inapproximability of the radio broadcast problem[J].Journal of Algorithms,2004,52(1):8-25.

[9]M.Elkin and G.Kortsarz.Polylogarithmic additive inapproximability of the radio broadcast problem[C]// Proceedings of The 7th Int'l Workshop on Approximation Algorithms for Combinatorial Optimization Problems-APPROX'04,Rome,Italy.2004:105-116.

[10]M.Elkin and G.Kortsarz.An improved algorithm for radio broadcast[J].Journal ACM Transactions on Algorithms,2007,3(1):810-818.

[11]I.Gaber and Y.Mansour.Centralized broadcast in multihop radio networks[J].Journal of Algorithms, 2003,46(1):1-20.

[12]R.Gandhi,S.Parthasarathy,and A.Mishra.Minimizing broadcast latency and redundancy in ad hoc networks[C]//Proceedings of ACM M obiHoc'03,Annapolis,MD,USA.2003:222-232.

[13]D.R.Kowalski and A.Pelc.Centralized deterministic broadcasting in undirected multi-hop radio networks [C]//Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems-APPROX-RANDOM'04,Rome,Italy.2004:171-182.

[14]E.Kushilevitz and Y.M ansour.An Ω(Dlog(N/ D))lower bound for broadcast in radio networks[J]. SIAM Journal on Computing,1998,27:702-712.

[15]S.Madden,M.J.Franklin,J.M.Hellerstein,et al.Tag:a tiny aggregation service for ad-hoc sensor networks[C]//Proceedings of OSDI'02,Boston, Massachusetts,USA.2002:36-50.

[16]J.Beaver,M.A.Sharaf,A.Labrinidis,et al.Location aware routing for data aggregation for sensor networks[C]// Proceeding of Geo Sensor Networks Workshop'03,Portland,Maine.2003:1-22.

[17]C.Intanagonwiwat,D.Estrin,R.Govindan,et al. Impact of network density on data aggregation in wireless sensor networks[C]//Proceedings of the 22nd Int'l Conference on Distributed Computing Systems, Vienna,Austria.2002:1-16

[18]A.Silberstein,R.Braynard,and J.Yang.Constraint-chaining:On energy-efficient continuous monitoring in sensor networks[C]//Proceedings of SIGMOD'06,Chicago,Illinois.2006:1-12.

[19]M.Greenwald and S.Khanna.Power-conserving computation of order-statistics over sensor networks [C]//Proceedings of PODS'04,Paris,France.2004: 275-285.

[20]J.Zhao,R.Govindan,and D.Estrin.Computing aggregates for monitoring wireless sensor networks[C] //Proceedings of the First IEEE.2003 IEEE International Workshop on Sensor Network Protocols and Applications,Los Angeles,CA,USA,2003:139-148.

[21]A.Deligiannakis,V.Stoumpos,Y.Kotidis,et al. Outlier-aware data aggregation in sensor networks[C] //Proceedings of ICDE'08,Cancún,Mé xico.2008: 1 448-1 450.

[22]N.Shrivastava,C.Buragohain,D.Agrawal,et al. Medians and beyond:New aggregation techniques for sensor networks[C]//Proceedings of Sensys04,Baltimore,MD,USA.2004:239-249.

[23]J.Considine,F.Li,G.Kollios,et al.Approximate aggregation techniques for sensor databases[C]// Proceedings of ICDE'04,Boston,M A,USA.2004: 449-460.

[24]D.Chu,A.Deshpande,J.Hellerstein,et al.Approximate data collection in sensornetworks using probabilistic models[C]//Proceedings of ICDE'06, Atlanta,GA,USA.2006:48-60.

[25]A.Deshpande,C.Guestrin,W.Hong,et al.Exploiting correlated attributes in acquisitional query processing[C]//Proceedings of ICDE'05,Tokyo,Japan. 2005:143-154.

[26]B.K.Y.Yu and V.K.Prasanna.Energy-latency tradeoffs for data gathering in wireless sensor networks[C]//Proceedings of INFOCOM'04,Hong Kong,China.2004:6-18.

[27]V.Annamalai,S.K.S.Gupta,et al.On tree-based convergecasting in wireless sensor networks[C]// Proceedings of IEEE Wireless Communications and Networking-WCNC,2003,3:1 942-1 947.

[28]S.Upadhyayula,V.Annamalai,and S.K.S.Gupta.A lowlatency and energy-efficient algorithm for convergecast in wireless sensor networks[C]//Proceedings of IEEE Global Telecommunications Conference-GLOBECOM,2003:3 525-3 530.

[29]A.Kesselman and D.Kowalski.Fast distributed algorithm for convergecast in ad hoc geometric radio networks[C]//Proceedings of the 2nd Annual Conference on Wireless On-demand Network Systems and Services-WONS,2005:119-124.

[30]H.Lee and A.Keshavarzian.Towards energy-optimal and reliable data collection via collision-free scheduling in wireless sensor networks[C]//Proceedings of INFOCOM'08,Phoenix,AZ,USA.2008:2 029-2 037 .