基于動態分簇路由的網內數據聚集

謝雙雙，管有慶

(南京郵電大學 物聯網學院，江蘇 南京 210003)

0 引 言

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

在分簇結構的網絡[7-8]中，檢測到同一事件的節點組成簇。在簇內，按照一定規則選舉產生簇頭節點。各個節點采集的數據在簇頭節點進行聚集，再由簇頭節點與聚集節點進行通信。LEACH[9]是一種低功耗自適應聚集路由算法，該類算法有效處理簇內信息收集，但缺點在于其網絡結構不利于簇間的數據傳遞。在基于樹的方法中，首先構造一個路由樹，用于數據收集或響應匯聚節點的數據查詢。基于樹的方案的主要任務之一是構建能量高效的數據聚集樹[10-11]。預先構造的樹是靜態的，所以大多數基于樹的方案只能適用于已知源節點的應用。

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

1 基于動態分簇路由的網內數據聚集模型

1.1 網絡模型

文中的一個事件驅動傳感器網絡[12]由n個節點組成。如圖1所示，將節點定義為五種角色，分別是：

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

(2)簇頭節點(Cluster-head)：用于收集和聚集簇內所有節點的數據信息；

(3)轉發節點(Relay)：簇頭節點數據經轉發節點轉發至Sink節點；

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

(5)Sink節點：用于接收和處理網內數據，可以通過網關與Internet連接。

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

圖1 網絡模型

1.2 動態分簇路由

假設網絡檢測到一個事件，網絡構建一個多跳的路由，在最小傳輸跳數的條件下實現最大化數據聚集。提出的IDADCR算法，目的在于建立一個從成員節點到Sink節點的最短路徑路由樹，同時最大化數據聚集。該算法的執行步驟為簇頭選擇、建立路由和數據聚集。

(1)簇頭選擇。

在IDADCR算法中，檢測到同一事件的多個成員節點會形成一個簇，并從簇中選擇一個成員節點作為簇頭節點，其他成員節點向簇頭節點發送數據,最后簇頭節點將數據經聚集節點和轉發節點傳輸至Sink節點。

該算法將節點與Sink節點的距離、剩余能量、節點密度作為簇頭選擇的條件。簇頭與Sink節點的距離越短，數據從簇頭傳輸到Sink節點的跳數越少。節點非等概率擔任簇頭，而是與剩余能量成正比，剩余能量越多，擔任簇頭的概率越大。

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

ditoSink=

(1)

根據成員節點狀態向量來判斷成員節點是否當選為簇頭：

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

(2)

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

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

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

(3)

其中，w1、w2、w3為加權系數。

成員節點根據當選簇頭的評分值，進行分布式簇頭選擇，詳細過程見算法1。

算法1：簇頭選擇。

Input:S// 成員節點集合

Output:Cluster-head // 從S中選出簇頭節點

1 For eachsi∈Sdo

2si←Collaborator//節點檢測到事件，并廣播包含Score的數據包

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

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)改進的最短路徑樹。

簇頭選擇后，采用洪泛的方式告知每個節點。簇頭在尋找下一跳轉發節點時，考慮在最大化數據聚集的情況下，盡可能減小數據傳輸的跳數。有如下定義：

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

distance(vi,Sink)

(4)

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

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

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

Input:Cluster-head //當前待轉發的節點

Output:Relay //下一跳轉發節點

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

2v←Cluster-head

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

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//聚集距離最小的節點只有一個

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節點較近的作為轉發節點

13 Updatevwithn

14 If Sink?Nvthen

15 Go to step 3

16 Else

17 Sink←Relay

18 end

2 性能評估

2.1 仿真實驗環境

通過仿真分析IDADCR、EFAT[13]、SPT[14]的網絡性能。性能指標包括：

(1)網絡流量：網絡中傳輸數據包的數量，包括事件信息的數據包和維護路由的數據包；

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

聚集率越小,則網絡中的數據聚集操作越多。其中，成員節點發送的事件信息的數據量為：

(5)

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

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

表1 參數設置

2.2 仿真實驗分析

(1)網絡流量。

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

圖2 網絡流量與時間的關系

(2)聚集率。

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

圖3 聚集率與節點個數的關系

3 結束語

提出了一種反應式的事件驅動網內數據聚集方法。該方法可擴展性好，根據檢測到的新事件，動態改變數據聚集結構實現最大數據聚集。實驗結果表明，該方法可以有效減少網絡中傳輸的數據量。在未來的工作中，將繼續研究新的數據聚集策略，主要考慮降低簇頭選擇的數據交換開銷和事件更新的數據交換開銷。

[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] 王 亞,肖明軍.一種延遲容忍網絡數據聚集算法[J].小型微型計算機系統,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] 王廣澤,馬志晟,喬佩利.自組織網絡中基于動態路由樹的網內數據聚集算法[J].信息技術,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] 劉 壯，馮 欣，王雁龍，等.基于雙簇頭聚類分簇和數據融合的無線傳感器網絡路由算法[J].吉林大學學報:理學版,2015,53(5):1013-1017.

[8] 季瑩瑩,章堅武.基于簇的無線傳感器網絡路由協議改進方案[J].傳感技術學報,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] 馮 誠,李治軍,姜守旭.無線移動多信道感知網絡上的數據聚集傳輸規劃[J].計算機學報,2016,39(5):931-945.

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

[12] 沈永增,陳宣揚,賈蓮蓮.一種事件驅動型無線傳感器網絡的分層路由算法[J].計算機系統應用,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.