基于分簇的無線傳感器網絡數據聚合方案研究

張 強,盧 瀟,崔曉臣

(空軍工程大學電訊工程學院,西安 710077)

無線傳感器網絡是由部署在監測區域內的大量傳感器節點組成,通過無線通信形成一個多跳的自組織的網絡系統,其目的是協作地感知、采集和處理網絡覆蓋區域中被感知對象的信息,并發送給觀察者。如圖 1所示。其出色的實時檢測能力使得人們可以從更為細微的角度了解周圍環境或個體現象所出現的現象、所處的狀態,并根據物理環境變化采取措施實行反向控制,為人類與客觀物理世界的交互提供了一種新的有效手段[1]。隨著研究的深入,WSN能夠廣泛應用于軍事、環境監測和預報、健康護理、智能家居、建筑物狀態監控等領域。

圖1 無線傳感器網絡體系結構

大量節點密集部署的特點導致大部分數據是冗余的,數據的重復傳輸必然消耗節點能量,同時也必將引起無線通信的帶寬擁擠,增加信道協商或競爭過程造成的能量開銷。而且傳感器節點的絕大部分能量消耗在無線通信模塊,實驗表明傳輸 1 bit信息100m需要消耗的能量大約相當于執行 3 000條計算指令消耗的能量。因此在無線傳感器網絡中采用數據聚合機制,刪除冗余數據,同時將來自不同節點的信息進行聚合處理,減少網絡數據傳輸的數據量,就可以減少網絡能量消耗。數據聚合利用的是節點的計算資源和存儲資源,只要將增加計算量的能量消耗控制在小于降低通信量的能量消耗,就可以達到節省能量延長網絡壽命的目的。

數據聚合可以減少 WSN網絡中傳輸的分組數量,減少分組的沖突概率,減小 Sink節點接收到重復分組的概率以及提高監測結果的準確性。它是目前WSN的一個研究熱點,其中包括聚合點的選擇、聚合時機的選擇和數據聚合策略等三個問題[2]。目前已提出了很多數據聚合策略算法。文獻[3]提出一種數據融合樹算法,即匯聚節點作為樹的根節點,通過反向組播樹的形式從分散的傳感器節點逐步將監測數據收集,樹上的每個中間節點都對收到的數據進行融合處理。而樹的建立時間復雜度為 O(n3),n為傳感器節點個數。文獻[4]中提出了一種基于移動代理的數據融合方法,監測數據保留在本地節點,當移動代理遷移到數據處進行融合處理。文獻[5]中提出自適應的數據融合算法,匯聚節點根據節點的可靠度建立控制信息,網絡中數據的傳輸則建立在控制信息的可靠度 P基礎上,可靠度 P則反映了匯聚節點收到節點數據包的個數。而大量節點所帶來的控制信息將造成網絡性能降低。文獻[6]提出一種使用模糊邏輯推論方法用于分簇網絡拓撲結構以達到數據融合的算法,算法分為四個步驟：模糊化、規則評定、規則融合和去模糊化。文獻[7]提出了基于主元分析的神經數據融合算法。文獻[8]提出了一種基于信息熵的分簇網絡數據融合方案。在數據聚合的聚合時機研究方面,文獻[9]對周期性檢測應用中的周期性簡單數據聚合時機模型、周期性逐跳數據聚合時機模型和周期性逐跳調整數據聚合時機模型等三種數據聚合時機模型進行了比較研究。文獻[10]為事件觸發類數據回傳提出了一種確定數據時機的協議——MFS,當 WSN中發生某個事件時,事件附近區域的多個傳感器節點將采集數據并報告給匯聚節點。在本文中,筆者主要在分簇網絡拓撲結構的基礎上討論數據聚合技術,并結合分簇路由協議提出了一種新的數據聚合方案。

1 數據聚合概念

數據聚合或數據融合是指利用傳感器節點的本地處理能力,先對采集到的或接收到的其他傳感器節點發送的多個數據進行網內處理,消除冗余信息,然后再傳輸處理后的數據。如圖 2所示。這與傳統的多傳感器數據融合有所不同,同樣是在軍事應用背景中,后者是指對空間分布的多源信息,對所關心的目標進行檢測、關聯、跟蹤、估計和綜合等多級多功能處理,以更高的概率或置信度得到所需要的目標狀態和身份估計以及完整的及時的態勢和威脅評估,為指揮員提供有用的決策信息。它的數據源主要是具有不同體制和功能的雷達。而 WSN數據融合或數據聚合主要是指單種傳感器為了減少網絡內的數據傳輸量,達到減少能源消耗、延長網絡壽命的目的。它的數據源主要是同類的傳感器節點。為區別傳統的多傳感器數據融合,本文使用數據聚合一詞。這里的數據聚合也不同于信息融合,信息融合是對來自不同來源、不同模式、不同媒質、不同時間、不同地點、不同表示形式的信息進行綜合處理,從而獲得更為準確、可靠的結論。融合的信息來源可能是數據庫或知識庫中的先驗信息;也可能是人機交互中的人工輸入信息。它是對人腦綜合處理復雜問題能力的一種較全面的、高水平的模仿。而 WSN數據聚合指中間節點對采集或接收到的多個數據進行合并,具體處理有：幾個數據任選一個,計算數據的平均值、最大值或最小值等[2]。

圖2 數據聚合處理圖

2 數據聚合方案

本文中數據聚合的研究建立在 WSN分簇的網絡拓撲結構上,聚合點將選擇簇頭節點,并且結合分簇路由協議建立的路由回傳數據;聚合時機主要考慮周期性數據回傳應用模型。如果數據聚合只在監測節點進行,數據的準確性將受到較大影響;同樣如果數據聚合只在匯聚節點進行,監測節點在發送數據時能量消耗較大,同時將造成無線信道擁擠。在分簇網絡中,共有三類節點,分別是簇內節點、簇頭節點和同時擔任中轉其它簇頭數據的簇頭節點。因此,筆者考慮在三類節點上各自采用不同的數據聚合策略,確保數據準確性和能量高效的平衡。

2.1 網絡模型

本文中 WSN采用分簇網絡拓撲結構,分簇算法將整個傳感器網絡劃分為若干個簇,每個簇包含一個簇頭和多個簇成員節點。簇成員節點只需將采集到的數據發送至簇頭,簇頭負責管理簇內成員節點,收集簇成員的監測數據,并將收集到的數據進行聚合處理后通過多跳方式報告至匯聚節點。LEACH協議中所做的假設將同樣適用本文中的研究,另外還有如下假設：

(1)網絡中監測區域內部署著同種類型的大量傳感器節點;

(2)相鄰節點間的監測數據具有相似性,節點分布冗余并且檢測得到的數據存在冗余信息,可進行數據聚合處理;

(3)各個節點周期性收集監測區域的數據,周期結束節點處理監測數據并決定是否轉發;匯聚節點同樣采用周期性地收集各個節點的數據。

(4)WSN所要監測的物理量可以由部分傳感器節點的監測數據聚合得到,而并非必須網絡中全部傳感器節點。

2.2 簇內節點聚合策略

WSN內節點部署高度冗余,監測數據也具有冗余性,通過減少數據發送量的方法可以達到數據聚合的目的。簇內節點減少監測數據發送的方法可以采用相應的 MAC協議根據時間片輪轉來關閉部分節點,也可以降低節點收集數據頻率。在本文中,筆者采用相對信息熵的方法,各簇內節點都將保留前一次向簇頭節點發送的監測數據,當節點再次得到新的監測數據時,計算兩個數據的相對信息熵值,當比較值具有明顯差異時才向簇頭節點發送,同時更新保留的數據。否則不發送新的檢測數據。

信息熵是 Shannon在 1948年提出,并作為一個隨機變量的不確定性或信息量的度量。如果某事物X具有的獨立可能的結果為 x1,x2,…,xn,并且每一種可能出現的概率分別為 p(x1),p(x2),…,p(xn),則該事物的信息熵為：信息熵的物理意義是在 X中所包含的信息的量。

假設 P和 Q是 2個概率分布函數,P相對于 Q的信息距離即相對信息熵[11]為：相對信息熵的物理意義是信息獲取量,表征了 2組概率分布之間的差異性程度,因而對于 2組不同的概率分布 P和 Q,計算其相對信息熵D(P‖Q)以及 D(Q‖P),如果這 2個值越小,表明 2組概率分布越近似,數據冗余則越大。因此,對于簇內節點 ni新舊得到的監測數據 yi和 yi′,如果其相對信息熵 D(yi‖yi′)和 D(yi′‖yi)滿足條件max(D(yiyi′),D(yi′‖yi))≤ε,其中 ε根據實際應用設定為足夠小的常量,則認為兩組數據間存在較大冗余,也即所監測的物理量沒有顯著變化,所以節點可以不發送最新收集到的監測數據。否則按照該簇內節點的路由表,將新的監測數據發送給該簇的簇頭節點,同時更新該簇內節點的監測數據值。

2.3 簇頭節點聚合策略

在本文的分簇網絡拓撲結構中,基于能量節省的角度考慮,簇頭節點與匯聚節點間采用多跳通信方式。因此在聚合策略上,普通簇頭節點只負責聚合本地監測數據和其簇內成員節點發送的數據,而擔當轉發簇頭數據的簇頭節點不僅負責普通簇頭節點聚合的數據,同時還需將其他簇頭節點發送過來的數據進行聚合。兩種簇頭節點的聚合策略為此有所不同。下面先介紹普通簇頭節點的聚合策略。

普通簇頭節點處理的監測數據包括自身傳感器模塊監測的數據和簇內各成員節點所發送的數據。每個簇頭節點保存前一次轉發的監測數據作為反饋比較值 E,初始值為零。當簇頭節點接收到其成員節點的新數據或是當其自身傳感器模塊得到新數據時,該值的作用是決定新數據是否轉發出去。實際監測環境中存在噪聲誤差,并且聚合多個傳感器節點的數據存在著不確定性。在本文中節點傳感器模塊得到的測量值采用對稱三角模糊數來表示,節點nk的自身監測數據經過模糊化處理為 Vk=(vk,vsk),其中 vk為對稱三角模糊數 Vk的中心值,vsk為Vk的模糊寬度,該值與測量誤差相關。同樣估計值E也為模糊數,表示為 Ei=(ei,esi),而這些模糊數值都將在匯聚節點處去模糊化。簇頭包含多個成員節點,分別采用 TDMA方式通信。當成員節點 ni發送的數據 Vi到來時,nk進行數據聚合。輸入由三部分組成,分別是自身傳感器得到的 Vk、Vi和 nk維持的回饋比較值 Ek。聚合輸出得到新值 nEk取代舊的 Ek。新值 nEk將與聚合表中的值進行比較,兩者的絕對差值如果大于預先設定的閾值,閾值取聚合表中所獲得兩組數據間之差的最大值,則說明監測區域出現異常變化需立即轉發 nEk,則依據路由表中的路由發送數據到下一簇頭節點。否則將新值nEk存入聚合表中。簇內通信一輪完成后,簇頭將對聚合表中所有的比較值 nEk進行平均值計算,同時將結果轉發。節點的傳感器模塊能耗較低,因此可以將其數據采集周期設為與簇內成員節點的工作周期一致,這樣將確保數據聚合處理不用等待某一輸入數據的到來。簇頭節點 nk的聚合算法流程圖如圖 3。

圖3 簇頭節點nk聚合流程圖

2.3.1 數據聚合模塊

數據聚合在簇頭節點進行,聚合的數據包括Vk(vk,vsk)、Vi(vi,vsi)和 Ek(ek,esk),得 到新值nEk(nek,nesk)。下面的計算中用 I(i,is)表示Vk(vk,vsk)和 Vi(vi,vsi)。nEk的取值同時還取決于WSN所監測數據的物理量,分為下面情況討論[14]。

(1)、I∩ Ek=φ。如果監測數據取最小值,則nEk=min(I,Ek);而如果監測數據取最大值,則 nEk=max(I,Ek);

(2)、I∩ Ek≠φ。 nEk的計算如下,引入加權和計算。

從上述計算可以看出,如果 Vk和 Vi與估計值Ek不相關,新估計值則與監測數據值的實際應用有關,否則引入加權和來計算新估計值 nEk,其權值與兩個對稱三角模糊數的模糊寬度(幅度)成反比。因為模糊數的不確定性越少,聚合處理越相關,則說明數據之間的冗余性也越大。

2.3.2 聚合表

簇頭節點除了建立路由表,在進行數據聚合處理時還需建立聚合表,表的更新也隨著簇的變化簇頭的轉換而動態建立。當簇頭接收到簇內成員節點的數據后進行數據聚合處理,表中記錄下該次聚合的輸出值 nEi(nei,nesi)的記錄項,其中包括節點標識、簇內節點號、監測數據值、計數值和有效標志。其中節點標識為該簇內成員節點的節點號,監測數據值是由簇頭每進行一次聚合處理的輸出值,與成員節點標識一一對應;計數值初始值都為 0,簇頭節點每向其下一跳節點發送一次數據時,該值加 1,而當簇頭收到成員節點 ni的數據時,ci清 0;有效標志bi初始值都為 1,當 ci大于預定值 cmax時 bi清 0,cmax取該簇的成員節點數。當節點死亡或是無法與簇頭通信時,ci的值將大于 cmax,所以 bi和 ci可以用來作為判斷成員節點能否與簇頭正常通信的標志位。如表 1所示。

表1 簇頭節點聚合表

擔任中轉數據的簇頭節點的聚合策略算法同上,不同之處在于此類簇頭節點還要接收其它簇頭的數據,將其存入聚合表并將參與該簇頭的轉發決定。為了區分簇內成員節點和簇頭發送的消息,規定消息如表 2。

表2 消息結構

當中轉簇頭接收到其簇內成員節點的數據,處理過程同普通簇頭節點;當接收到其它簇頭節點的數據時,根據消息中的簇號和簇內標識即可判定是否是簇頭轉發數據。聚合表與前不同,將增加一列簇頭數據標志位,初始都為 0,當接收到簇頭數據變為 1,簇內節點號將存入該簇頭的簇號,其它列數據不變。當中轉簇頭每完成一次數據聚合處理,得出的新估計值不僅與聚合表中所有的簇內成員節點對應的值進行比較,還將與其它簇頭的數據值比較,同理,在中轉簇頭完成一輪簇內通信時,其它簇頭的數據也將參與周期轉發數據的平均值計算。

3 仿真實驗

本文采用 NS2+NRL-SENSORSIM作為仿真平臺,通過仿真環境來分析本文提出的數據聚合機制的性能。網絡拓撲為 100個節點隨機部署在 100m×100m的范圍內,匯聚節點位于(50,150),采用IEEE802.1b作為 MAC協議,節點初始能量為 1 J,ε分別取值 0.5和 1。每 10 s計算一次網絡平均能耗(測量節點剩余能量)。在 NRL-SENSORSIM中,傳感器網絡事件由大量的 PHENOM節點來模擬,每秒8個事件在監測范圍內隨機產生,且事件持續時間為 1 s,假定用戶對監測數據的最大值感興趣。圖 4和圖 5分別為網絡節點平均能量消耗圖及網絡壽命圖。從圖中可以看出本文提出的基于分簇數據聚合機制的網絡平均能耗較 LEACH協議有明顯的改進,當所監測區域數據沒有明顯變化時,節點減少了轉發的數據量,網絡平均能耗也有顯著減少。隨著ε的增大,節點轉發的數據量增加,能量消耗也隨著增大。節點死亡率隨時間增加有效降低,網絡壽命得到明顯延長。

圖4 網絡節點平均能量消耗

圖5 網絡壽命

4 結束語

分簇算法和數據聚合是 WSN中節省能量的兩種有效方法,本文在分簇網絡拓撲的基礎上,提出了一種新的數據聚合機制。在仿真實驗中將新方法與LEACH協議進行對比分析,結果表明新方法在降低節點的數據傳輸量,節省能量消耗和延長網絡壽命等方面都有明顯改進。而數據聚合帶來的延遲代價和魯棒性問題,則是筆者下一步研究的重點。

[1]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京：清華大學出版社,2005：1-10.

[2]于宏毅,李鷗,張效義,等.無線傳感器網絡理論、技術與實現[M].北京：,國防工業出版社,2008：190-193.

[3]Kalpakis K,Dasgupta K,Nam joshi P.An Efficient Clustering based Heuristic for Data Gathering and Aggregation in Sensor Networks[C]//IEEE Wireless Communications and Networking,2003：1948-1953.

[4]王殊,閻毓杰,陳帥,等.傳感器網絡中基于移動代理的數據融合方法研究[J].傳感技術學報,2006,19：926-932.

[5]So J,K im J,Gupta I.Cushion：Autonomically Adaptive Data Fusion in Wireless Sensor Networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems,2005：1-3.

[6]Weilian SU,Theodoros C.Bougiouklis.Data Fusion Algorithms in Cluster-Based Wireless Sensor Networks Using Fuzzy Logic Theory[C]//Proceedings of the 11th Conference on 11th WSEAS International Conference on Communications,2007：291-299.

[7]馮秀芳,高戰強.無線傳感器網絡中基于 PCA神經網絡的數據融合[J].計算機科學,2007,34：372-375.

[8]唐晨,王汝傳,黃海平,等.基于信息熵的無線傳感器網絡數據融合方案[J].東南大學學報,2008,38：276-279.

[9]Ignacio Solis,Katia Obraczka.The Impact of Timing in Data Aggregation for Sensor Networks[C]//IEEE International Conference on Communications,2004：3640-3645.

[10]YuanW,Krishnamachari S V,Tripathi S K.Synchronization of Multiple Levels of Data Fusion in Wireless Sensor Networks[C]//IEEE Global Telecommunications Conference,2003：221-225.

[11]Yager RR.On the Entropy of Fuzzy Measures[J].IEEE Transactions on Fuzzy Systems,2000,8(4)：453-461.

[12]Silvio Croce,Francesco Marcelloni,Massimo Vecchio.Reducing Power Consumption in Wireless Sensor Networks Using a Novel Approach to Data Aggregation[J].The Computer Journal,2008,51(2)：226-239.