謝雙雙，管有慶

(南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

0 引 言

無線傳感網(wǎng)絡(luò)是由具有感知、計算和通信能力的微型傳感器以Ad-hoc[1]方式構(gòu)成的無線網(wǎng)絡(luò)，通過大量節(jié)點間的分工協(xié)作、實時監(jiān)測、感知以及采集分布區(qū)域內(nèi)的各種環(huán)境數(shù)據(jù)進行處理，獲得詳盡而準確的信息并傳送給用戶[2-3]。無線傳感器網(wǎng)絡(luò)是典型的事件驅(qū)動系統(tǒng)，當(dāng)普通的傳感器節(jié)點檢測到事件時，作為數(shù)據(jù)源向Sink節(jié)點發(fā)送相關(guān)數(shù)據(jù)。網(wǎng)內(nèi)數(shù)據(jù)聚集技術(shù)可以與無線傳感器網(wǎng)絡(luò)的多個協(xié)議層進行結(jié)合，在網(wǎng)絡(luò)層,很多路由協(xié)議結(jié)合了數(shù)據(jù)聚集機制，用于減少數(shù)據(jù)傳輸量[3-6]。這些路由協(xié)議包括分簇路由協(xié)議和基于樹的路由協(xié)議。

在分簇結(jié)構(gòu)的網(wǎng)絡(luò)[7-8]中，檢測到同一事件的節(jié)點組成簇。在簇內(nèi)，按照一定規(guī)則選舉產(chǎn)生簇頭節(jié)點。各個節(jié)點采集的數(shù)據(jù)在簇頭節(jié)點進行聚集，再由簇頭節(jié)點與聚集節(jié)點進行通信。LEACH[9]是一種低功耗自適應(yīng)聚集路由算法，該類算法有效處理簇內(nèi)信息收集，但缺點在于其網(wǎng)絡(luò)結(jié)構(gòu)不利于簇間的數(shù)據(jù)傳遞。在基于樹的方法中，首先構(gòu)造一個路由樹，用于數(shù)據(jù)收集或響應(yīng)匯聚節(jié)點的數(shù)據(jù)查詢?；跇涞姆桨傅闹饕蝿?wù)之一是構(gòu)建能量高效的數(shù)據(jù)聚集樹[10-11]。預(yù)先構(gòu)造的樹是靜態(tài)的，所以大多數(shù)基于樹的方案只能適用于已知源節(jié)點的應(yīng)用。

為了解決上述問題，提出了一種基于動態(tài)分簇的網(wǎng)內(nèi)數(shù)據(jù)聚集算法(In-network Data Aggregation based on Dynamic-Clustering Routing,IDADCR)。目的是建立一個最大數(shù)據(jù)聚集路徑樹，從成員節(jié)點到Sink節(jié)點的最短路徑路由樹，同時最大化數(shù)據(jù)聚集。

1 基于動態(tài)分簇路由的網(wǎng)內(nèi)數(shù)據(jù)聚集模型

1.1 網(wǎng)絡(luò)模型

文中的一個事件驅(qū)動傳感器網(wǎng)絡(luò)[12]由n個節(jié)點組成。如圖1所示，將節(jié)點定義為五種角色，分別是：

(1)成員節(jié)點(Collaborator)：檢測到事件的普通節(jié)點，一定條件下，可以被選作簇頭；

(2)簇頭節(jié)點(Cluster-head)：用于收集和聚集簇內(nèi)所有節(jié)點的數(shù)據(jù)信息；

(3)轉(zhuǎn)發(fā)節(jié)點(Relay)：簇頭節(jié)點數(shù)據(jù)經(jīng)轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)至Sink節(jié)點；

(4)聚集節(jié)點(Aggregator)：用于聚集來自兩個或者多個節(jié)點的數(shù)據(jù)信息，通過多跳傳輸至Sink節(jié)點；

(5)Sink節(jié)點：用于接收和處理網(wǎng)內(nèi)數(shù)據(jù)，可以通過網(wǎng)關(guān)與Internet連接。

事件驅(qū)動的無線傳感器網(wǎng)絡(luò)可以表示為圖G=(V,E)，其中V是網(wǎng)絡(luò)中所有節(jié)點的集合，E是連接兩個節(jié)點的邊的集合。假設(shè)：V={v1,v2,…,vn}是傳感器網(wǎng)絡(luò)節(jié)點的集合；S={s1,s2,…,sn}是成員節(jié)點集合，S?V。

圖1 網(wǎng)絡(luò)模型

1.2 動態(tài)分簇路由

假設(shè)網(wǎng)絡(luò)檢測到一個事件，網(wǎng)絡(luò)構(gòu)建一個多跳的路由，在最小傳輸跳數(shù)的條件下實現(xiàn)最大化數(shù)據(jù)聚集。提出的IDADCR算法，目的在于建立一個從成員節(jié)點到Sink節(jié)點的最短路徑路由樹，同時最大化數(shù)據(jù)聚集。該算法的執(zhí)行步驟為簇頭選擇、建立路由和數(shù)據(jù)聚集。

(1)簇頭選擇。

在IDADCR算法中，檢測到同一事件的多個成員節(jié)點會形成一個簇，并從簇中選擇一個成員節(jié)點作為簇頭節(jié)點，其他成員節(jié)點向簇頭節(jié)點發(fā)送數(shù)據(jù),最后簇頭節(jié)點將數(shù)據(jù)經(jīng)聚集節(jié)點和轉(zhuǎn)發(fā)節(jié)點傳輸至Sink節(jié)點。

該算法將節(jié)點與Sink節(jié)點的距離、剩余能量、節(jié)點密度作為簇頭選擇的條件。簇頭與Sink節(jié)點的距離越短，數(shù)據(jù)從簇頭傳輸?shù)絊ink節(jié)點的跳數(shù)越少。節(jié)點非等概率擔(dān)任簇頭，而是與剩余能量成正比，剩余能量越多，擔(dān)任簇頭的概率越大。

首先，Sink節(jié)點以洪泛的方式發(fā)送鄰居節(jié)點發(fā)現(xiàn)信息(Information of Neighbors Discovery,IND)。IND包括當(dāng)前節(jié)點的ID(節(jié)點標識符)、位置信息CoordSender和Sink節(jié)點位置CoordSink(X,Y,Z)。節(jié)點利用鄰域信息表(Neighborhood)來存儲鄰居節(jié)點ID、位置信息和Sink節(jié)點位置信息。當(dāng)節(jié)點接收到一個IND包，更新自身的鄰域信息表和待轉(zhuǎn)發(fā)的IND包。當(dāng)所有的節(jié)點都已轉(zhuǎn)發(fā)IND包，Sink位置和鄰居節(jié)點發(fā)現(xiàn)結(jié)束。所有節(jié)點都已獲得Sink節(jié)點的位置信息，成員節(jié)點與Sink節(jié)點的距離為：

ditoSink=

(1)

根據(jù)成員節(jié)點狀態(tài)向量來判斷成員節(jié)點是否當(dāng)選為簇頭：

x(si)=(ditoSink(si),re(si),ρ(si))

(2)

其中，x(si)為成員節(jié)點的狀態(tài)向量；re(si)為剩余能量；ρ(si)為節(jié)點密度，等于鄰居節(jié)點個數(shù)。

提出一種綜合考慮節(jié)點與Sink節(jié)點的距離、節(jié)點密度、剩余能量的評分機制。各節(jié)點當(dāng)選簇頭的評分如下：

Scorei=w1/ditoSink+w2re(si)+w3ρ(si)

(3)

其中，w1、w2、w3為加權(quán)系數(shù)。

成員節(jié)點根據(jù)當(dāng)選簇頭的評分值，進行分布式簇頭選擇，詳細過程見算法1。

算法1：簇頭選擇。

Input:S// 成員節(jié)點集合

Output:Cluster-head // 從S中選出簇頭節(jié)點

1 For eachsi∈Sdo

2si←Collaborator//節(jié)點檢測到事件，并廣播包含Score的數(shù)據(jù)包

3 For eachsj∈Nsi∩Sdo//Nsi為節(jié)點si的鄰居節(jié)點集合

4 if Score(sj)<=Score(si) then

5si←Cluster-head candidate

6 Addsiinto the set of Cluster-head candidates

7 end

8 For each Cluster-head candidate do

9 if Score(si)=max{Score(Cluster-head candidates)} then

10si←Cluster-head

11 end

12 end

(2)改進的最短路徑樹。

簇頭選擇后，采用洪泛的方式告知每個節(jié)點。簇頭在尋找下一跳轉(zhuǎn)發(fā)節(jié)點時，考慮在最大化數(shù)據(jù)聚集的情況下，盡可能減小數(shù)據(jù)傳輸?shù)奶鴶?shù)。有如下定義：

定義1：對任意節(jié)點vi∈V，與所有簇頭和Sink節(jié)點的最小跳數(shù)之和定義為聚集距離。

distance(vi,Sink)

(4)

其中，distance(vi,u)表示節(jié)點vi與u之間的最小跳數(shù)；Cluster-heads表示所有簇頭節(jié)點的集合；distance(vi,Sink)表示節(jié)點vi與Sink節(jié)點之間的最小跳數(shù)。

從鄰居節(jié)點中選擇聚集距離最小的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。當(dāng)多個鄰居節(jié)點的聚集距離相等時，選擇距離Sink節(jié)點較近的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。路由建立的詳細過程見算法2。

算法2：改進的最短路徑樹。

Input:Cluster-head //當(dāng)前待轉(zhuǎn)發(fā)的節(jié)點

Output:Relay //下一跳轉(zhuǎn)發(fā)節(jié)點

1 The Cluster-head claim to be Cluster-head by flooding

2v←Cluster-head

3 For eachn∈Nv∩(V-S) do //Nv為當(dāng)前節(jié)點v的鄰居節(jié)點

4 Calculating thedaggr(n)

5 Ifdaggr(n)=min{daggr(NV∩(V-S))} then

6n←Relay candidate

7 Addninto the set of Relay candidates

8 If the size of Relay candidates is 1 then//聚集距離最小的節(jié)點只有一個

9n←Relay

10 Else if the size of Relay candidates is larger than 1 then

11 If Distanceto Sink(n)=min{DistancetoSink

(Relay candidates)}

12 thenn←Relay//選擇距離Sink節(jié)點較近的作為轉(zhuǎn)發(fā)節(jié)點

13 Updatevwithn

14 If Sink?Nvthen

15 Go to step 3

16 Else

17 Sink←Relay

18 end

2 性能評估

2.1 仿真實驗環(huán)境

通過仿真分析IDADCR、EFAT[13]、SPT[14]的網(wǎng)絡(luò)性能。性能指標包括：

(1)網(wǎng)絡(luò)流量：網(wǎng)絡(luò)中傳輸數(shù)據(jù)包的數(shù)量，包括事件信息的數(shù)據(jù)包和維護路由的數(shù)據(jù)包；

(2)聚集率：Sink節(jié)點接收的事件信息的數(shù)據(jù)量和成員節(jié)點發(fā)送的事件信息的數(shù)據(jù)量之比。

聚集率越小,則網(wǎng)絡(luò)中的數(shù)據(jù)聚集操作越多。其中，成員節(jié)點發(fā)送的事件信息的數(shù)據(jù)量為：

(5)

其中，EDi為事件i的持續(xù)周期；NRi為事件通知速率；EV為事件數(shù)量。

利用NS-2仿真平臺對IDADCR進行仿真，并在仿真的基礎(chǔ)上對算法的性能進行分析。實驗仿真參數(shù)設(shè)置基于IEEE 802.15.4標準，相應(yīng)的參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

2.2 仿真實驗分析

(1)網(wǎng)絡(luò)流量。

在網(wǎng)絡(luò)流量隨時間變化的仿真分析中，設(shè)置100個節(jié)點分布在1 000 m*1 000 m的區(qū)域，仿真時間段內(nèi)相繼有三個事件發(fā)生，事件從零時刻開始，持續(xù)時間900 s。EFAT算法周期性地重建路由樹，重建周期為200 s。如圖2所示，IDADCR和REFAT明顯優(yōu)于EFAT。因為，周期性的路由樹重建伴隨著周期性的數(shù)據(jù)傳輸開銷。對比IDADCR與REFAT，IDADCR在檢測到事件發(fā)生階段，由于簇頭選擇和路由建立帶來的數(shù)據(jù)傳輸開銷，IDADCR的網(wǎng)絡(luò)流量大于SPT。但是，在IDADCR中，網(wǎng)絡(luò)實現(xiàn)了最大化數(shù)據(jù)聚集，所以在300 s后，IDADCR中的網(wǎng)絡(luò)流量小于EFAT，有效彌補了事件發(fā)生階段帶來的流量開銷。

圖2 網(wǎng)絡(luò)流量與時間的關(guān)系

(2)聚集率。

通過聚集率隨節(jié)點個數(shù)的變化關(guān)系展示了IDADCR的節(jié)點可擴展性。從圖3可以觀察到，所有算法的聚集率隨節(jié)點數(shù)量的增加而降低。因為隨節(jié)點密集度增加，節(jié)點鄰居的平均數(shù)量增加，從而網(wǎng)絡(luò)中發(fā)生的數(shù)據(jù)聚集操作越多。IDADCR中發(fā)生的數(shù)據(jù)聚集操作最多，因為數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，一直尋找全局最優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點，使得空間和時間上相關(guān)的數(shù)據(jù)在聚集節(jié)點發(fā)生數(shù)據(jù)聚集。

圖3 聚集率與節(jié)點個數(shù)的關(guān)系

3 結(jié)束語

提出了一種反應(yīng)式的事件驅(qū)動網(wǎng)內(nèi)數(shù)據(jù)聚集方法。該方法可擴展性好，根據(jù)檢測到的新事件，動態(tài)改變數(shù)據(jù)聚集結(jié)構(gòu)實現(xiàn)最大數(shù)據(jù)聚集。實驗結(jié)果表明，該方法可以有效減少網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量。在未來的工作中，將繼續(xù)研究新的數(shù)據(jù)聚集策略，主要考慮降低簇頭選擇的數(shù)據(jù)交換開銷和事件更新的數(shù)據(jù)交換開銷。

[1] CHANG J H,TASSIULAS L. Energy conserving routing in wireless ad-hoc networks[C]//Nineteenth joint conference of the IEEE computer and communications societies.[s.l.]:IEEE,2000:22-31.

[2] BORGES L M,VELEZ F J,LEBRES A S.Survey on the characterization and classification of wireless sensor network applications[J].IEEE Communications Surveys & Tutorials,2014,16(4):1860-1890.

[3] 王 亞,肖明軍.一種延遲容忍網(wǎng)絡(luò)數(shù)據(jù)聚集算法[J].小型微型計算機系統(tǒng),2013,34(6):1212-1215.

[4] TALELE A K,PATIL S G,CHOPADE N B.A survey on data routing and aggregation techniques for wireless sensor networks[C]//International conference on pervasive computing.[s.l.]:[s.n.],2015:1-5.

[5] 王廣澤,馬志晟,喬佩利.自組織網(wǎng)絡(luò)中基于動態(tài)路由樹的網(wǎng)內(nèi)數(shù)據(jù)聚集算法[J].信息技術(shù),2010(7):69-71.

[6] GUO W,HONG W,ZHANG B,et al.Reliable adaptive data aggregation route strategy for a trade-off between energy and lifetime in WSNS[J].Sensors,2014,14(9):16972-16993.

[7] 劉 壯，馮 欣，王雁龍，等.基于雙簇頭聚類分簇和數(shù)據(jù)融合的無線傳感器網(wǎng)絡(luò)路由算法[J].吉林大學(xué)學(xué)報:理學(xué)版,2015,53(5):1013-1017.

[8] 季瑩瑩,章堅武.基于簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議改進方案[J].傳感技術(shù)學(xué)報,2008,21(6):1052-1054.

[9] CHANDRAKASAN A P,SMITH A C,HEINZELMAN W B,et al.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[10] 馮 誠,李治軍,姜守旭.無線移動多信道感知網(wǎng)絡(luò)上的數(shù)據(jù)聚集傳輸規(guī)劃[J].計算機學(xué)報,2016,39(5):931-945.

[11] 李 宏,于宏毅,劉阿娜.一種基于樹的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J].電子與信息學(xué)報,2007,29(7):1633-1637.

[12] 沈永增,陳宣揚,賈蓮蓮.一種事件驅(qū)動型無線傳感器網(wǎng)絡(luò)的分層路由算法[J].計算機系統(tǒng)應(yīng)用,2011,20(8):81-85.

[13] NAKAMURA E F,FIGUEIREDO C M S,LOUREIRO A A F.Information fusion for data dissemination in self-organizing wireless sensor networks[C]//International conference on networking.[s.l.]:Springer-Verlag,2005:585-593.

[14] INTANAGONWIWAT C,ESTRIN D,GOVINDAN R,et al.Impact of network density on data aggregation in wireless sensor networks[C]//International conference on distributed computing systems.[s.l.]:IEEE,2002:457-458.