能量高效的WSNs分簇數據融合算法*

孫 超， 楊曉峰， 彭 力

(江南大學 物聯網工程學院，江蘇 無錫 214122)

能量高效的WSNs分簇數據融合算法*

孫 超， 楊曉峰， 彭 力

(江南大學 物聯網工程學院，江蘇 無錫 214122)

針對無線傳感器網絡(WSNs)中多跳通信造成的“熱區(qū)”以及數據冗余問題，提出了一種能量高效的分簇數據融合算法(EECDA)。該算法在分簇階段綜合考慮節(jié)點的剩余能量、到基站的距離和鄰居節(jié)點的數目,周期性地選擇簇首和劃分不同規(guī)模的簇；對簇內數據進行融合，利用辛普森積分法則計算預測接收數據，在保證采集數據實時性和準確性的前提下,降低數據的冗余性，減少通信負載，提高網絡的能量利用率。仿真結果表明:該算法能夠對數據進行高效預測，減少網絡通信量，相較已有的算法，能夠有效延長網絡的生存周期。

無線傳感器網絡； 非均勻分簇； 數據融合； 能量高效

0 引 言

路由技術是無線傳感器網絡(WSNs)的核心技術之一。在連續(xù)復雜的WSNs監(jiān)測環(huán)境中，大量散布的無線傳感器節(jié)點一般由有限能量的電池供電，而節(jié)點電池更換困難。因此需要能量高效的WSNs路由協(xié)議，以均衡網絡能耗同時延長網絡生命周期。利用分簇技術[1]可以對采集的數據進行融合以降低網絡的能量消耗，但是分簇路由協(xié)議會造成經典的“熱區(qū)”問題。

針對“熱區(qū)”問題，國內外許多專家學者提出了非均勻分簇的概念，其中心思想是將網絡劃分成大小不一的簇，靠近基站的簇小于遠離基站的簇。文獻[2]中的UHEED算法在HEED算法的基礎上綜合了節(jié)點到基站的距離因素進行非均勻的分簇，這樣可以很好地均衡網絡能耗。文獻[3]提出的WCF-UC算法，采用基于權值的局部競選簇首策略，簇首根據距離信息等構建大小不均的多個簇，有效均衡簇內通信能耗。但上述文獻都是采用非均勻分簇對簇內數據進行簡單的融合，沒有對數據的關聯性進行相應的分析處理，也沒有剔除重復、無效或不正確的數據，不能最大限度地延長網絡生存周期。

能量消耗是影響WSNs生存周期的主要因素，為了將網絡中的能量消耗降到最低，所以在非均勻分簇路由算法中引入數據融合技術[4，5]。近些年，很多技術被提出以改善WSNs中的數據融合機制。文獻[6]提出一種基于預測機制的數據采集協(xié)議用以消除冗余數據傳輸。該算法根據先前感知信息的數據量預測下一個時段基站和傳感器節(jié)點的數據。將預測數據與實際數據的誤差與設定的預測閾值作比較，當預測誤差大于設定的預測閾值，傳感器節(jié)點則傳送數據到基站。該算法一定程度上提高了預測數據的準確性。文獻[7]提出了在WSNs中使用一種自適應采樣算法收集數據。該算法使用三種機制，包括簇的構建、采樣節(jié)點的選擇和時間序列報表保證傳送數據的有效性。通過自適應數據采集和模型預測最大限度減少從網絡中提取數據的信息量，但無法更準確地預測數據。

本文在非均勻分簇的同時，利用辛普森法則對數據進行預測融合，提出了一種能量高效的分簇數據融合算法(energy-efficient clustering data aggregation,EECDA)。本文提出的算法與上述文獻相比，提高了預測數據的準確性，最大限度減少獲得預測數據的計算量。

1 WSNs采用的模型

1.1 網絡模型

在本文，對WSNs模型作如下假設：1)N個傳感器節(jié)點隨機分布在M×M的監(jiān)測區(qū)域內；2)所有節(jié)點都是同質的，有且僅有一個標識ID；3)所有節(jié)點和基站都是靜止的；4)所有節(jié)點都能根據距離調節(jié)它們的發(fā)射功率；5)基站位于監(jiān)測區(qū)域外，它能跟所有節(jié)點通信且有足夠的能量；6)簇首能夠執(zhí)行數據融合和數據壓縮。

1.2 能量消耗模型

本文采用的無線電模型與LEACH協(xié)議[8]中使用的相同。發(fā)送l bit的信息量到距離d處需要消耗的能量為

(1)

式中 εfs為自由空間模型的能耗系數，εamp為多路徑放大電路的能耗系數，dl1為節(jié)點可以直接與基站通信的距離。為了接收lbit的信息量，消耗的能量為

ERx(l)=l×Eelec

(2)

此外，對網絡中的其他能量消耗作如下假設：1)節(jié)點感知環(huán)境信息的能量消耗為Es；2)簇首消耗Eagg用于數據融合。

2 EECDA設計

EECDA是以輪為周期運行的，每一輪是由簇的建立階段和數據通信階段組成。根據節(jié)點的剩余能量、鄰居節(jié)點的數目和節(jié)點到基站的距離完成簇的建立，該階段又可細分為5個子過程，依次為鄰居節(jié)點發(fā)現(NND)、簇首競爭(CHC)、成簇(CF)、簇的優(yōu)化(CO)和確定數據傳輸路徑(PC)。在數據通信階段，簇首利用之前接收到的簇成員數據，運用辛普森3/8積分法則[9]計算下一時刻的預測接收數據，然后與接收到的真實數據作差值運算，如果差值大于系統(tǒng)設置的預測閾值，簇首將接收到的實際數據發(fā)送到基站，反之則不發(fā)送數據。EECDA每一輪的運行如圖1。

圖1 EECDA示意圖

2.1 簇的建立

如上所述，簇的建立可以由5個子階段組成，每個階段都分別需要一個特定的時間段完成，所以完成簇的建立需要花費時間T(T=T1+T2+…+T5)。在鄰居節(jié)點發(fā)送過程，每個節(jié)點在通信半徑范圍內廣播Neighbor_Msg，同時接收來自其他節(jié)點的Neighbor_Msg，然后更新自己的Neighbor_List。

鄰居節(jié)點發(fā)現T1結束后，簇首競爭開始。每個節(jié)點si需要接收來自其他節(jié)點Head_Msg，等待接收時間Tw，即

(3)

式中 Einit和Erem分別為節(jié)點si的初始能量和剩余能量，α為節(jié)點si已成為簇首的次數，NL(si)為節(jié)點si鄰居節(jié)點數目，R為0.1～0.2之間的隨機數。

如果在Tw內沒有接收到來自其他節(jié)點的Head_Msg，該節(jié)點自動成為簇首并在競爭半徑Rc范圍內廣播Head_Msg。競爭半徑Rc為

(4)

式中Rmax為節(jié)點的最大競爭半徑，dmax和dmin分別為節(jié)點到基站的最大和最小距離，c為0～1之間的權值系數。

節(jié)點在接收Head_Msg后更新自己的Head_List，尋找距離自己最近的簇首。簇首競爭T2結束后，節(jié)點根據自己的Head_List找到最近的簇首并向其發(fā)送JionCluster_Msg。簇首在收到其他節(jié)點的JionCluster_Msg后更新自己的Member_List。成簇時間T3結束，簇的優(yōu)化過程開始，那些只有一個簇首沒有簇成員或有且只有一個簇成員的簇需要解散，就近加入其他簇。簇的優(yōu)化完成后，簇首需要在T5時間內尋找一條與基站的通信路徑。簇首同樣在競爭半徑內根據自己的Node_ID廣播Route_Msg，接收到Route_Msg的簇首更新自己的ALL_PATH_List并發(fā)送自己的Route_Msg。每個簇首等待接收Route_Msg的時間TW2計算，即

(5)

等待時間TW2一到，簇首將Route_Rp_Msg發(fā)送到最近的簇首。簇首接收到來自其他簇首的Route_Rp_Msg更新自己的F_PATH_List。

2.2 數據通信階段

在簇的建立階段完成以后，數據通信階段開始。簇首將準備好的TDMA序列表發(fā)送給自己的簇成員，簇成員在屬于自己的時隙將監(jiān)測數據發(fā)送給簇首。此外，簇首采用辛普森3/8積分法則融合數據。數據融合由2個階段組成，分別是預測階段和決策階段。

預測階段采用辛普森積分法則，使用先前時間序列0,1,2,3…,t接收到的數值集合X(t)={x(0),x(1),x(2),x(3),…,x(t)}，根據公式計算下一時間序列t+1的預測數值X＇p(t+1)為

x(9)+…)+3(x(1)+x(2)+x(4)+…)]

(6)

式中 h為數值集合的平均誤差，c為用來和h相加改善預測準確性的常量，經過實驗，c取0.024可以獲得最佳的預測準確性。

簇首收到簇成員在下一時間序列t+1發(fā)送的實際數值X＇a(t+1)以后，決策階段開始。將預測數值X＇p(t+1)與實際數值X＇a(t+1)作差值運算，得到的預測誤差與系統(tǒng)設置的預測閾值ε比較，決定是否將實際數值X＇a(t+1)發(fā)送到基站，即

|actual-predicted|<ε

(7)

決策階段，簇首根據關系式判定接收到的數值X＇a(t+1)是不是多余的，剔除多余數據來減少網絡的通信量，最大限度減少網絡的通信負載，延長傳感器網絡的生存周期。使用辛普森3/8積分法則進行數據融合的流程圖如圖2。

圖2 辛普森3/8積分法則數據融合流程圖

3 算法仿真與性能分析

3.1 仿真參數

本文算法在Matlab平臺下進行仿真實驗，100個相同的傳感器節(jié)點隨機分布在100 m×100 m的矩形區(qū)域內，基站設置在(50,150)m處。仿真實驗需要的其他相關參數:節(jié)點初始能量為2 J，數據包大小為1 000 bytes，c為0.024，Eelec為50 nJ/bit，εfs為10 pJ/(bit m2)，εamp為0.001 3 pJ/(bit m4)，Eagg為5 nJ/(bit signal)，Es為0.5 nJ/(bit signal)。

3.2 數據融合性能分析

仿真實驗以實際環(huán)境監(jiān)測系統(tǒng)獲取的溫度值數據庫為測試樣本，對比文獻[7]提出的ASAP算法，通過定性定量分析，評估本文算法在數據融合方面的性能。

由表1中可以看出，當預設置閾值ε相同時，EECDA預測數據的準確性要明顯高于ASAP算法，這是因為EECDA在預測數據時以先前收集的監(jiān)測數據為樣本，采用辛普森積分法則對下一時刻的實時數據進行預測，保證了較高的預測準確性。而ASAP算法是根據建立的模型和數據相關性來預測數據，忽略了實際監(jiān)測環(huán)境的特殊性，所以準確性較低。

表1 監(jiān)測數據與預測數據對比

由圖3中可以看出，預設置閾值ε的大小將直接影響預測數據的準確性，預設置閾值ε越小，成功預測數據的概率越低。當預設置閾值ε在區(qū)間內變化時，EECDA成功預測數據的概率要明顯高于ASAP算法。當預設置閾值大于0.18時，EECDA和ASAP算法的成功預測數據的概率相當。這也從側面驗證了EECDA具有較高的預測準確性。

圖3 成功預測數據概率與預設置閾值ε的關系

3.3 網絡生存周期

圖4展示了是否采用數據融合的本文算法網絡存活節(jié)點數隨輪數變化的性能差異。如果以存活50 %節(jié)點數作為網絡的生存周期，那么采用數據融合的本文算法的網絡生存周期比未采用時提高了7.1 %。這是因為采用數據融合的本文算法通過準確地預測數據，減少了簇首與基站之間的網絡通信量，降低了節(jié)點的能量消耗，網絡生存周期得以延長。

圖4 存活節(jié)點數隨輪數變化

由圖5中可以看出，LEACH算法的網絡生存周期性能最差，這主要因為LEACH算法采用隨機概率模型選擇簇首，并未考慮節(jié)點的剩余能量等因素，導致節(jié)點能耗不均，造成“熱點”問題。UHEED算法的網絡生存周期要明顯好于LEACH算法，但EECDA要比UHEED算法提高41.3 %。

UHEED算法雖然在分簇階段綜合考慮節(jié)點的剩余能量及到基站的距離，但該算法多次使用迭代，造成較大的能量開銷且沒有采用數據融合減少數據量，所以性能不及EECDA。

圖5 網絡生存周期對比

4 結 論

EECDA具有較高的數據預測準確性，可以有效地降低簇首與基站的網絡通信量，網絡生存周期得以延長。仿真表明，在EECDA平衡了節(jié)點能耗之后，使用辛普森3/8積分法預測數據可以減少數據通信延長網絡的生存周期，所以下一步將研究使用其他數值預測方法提高預測的準確性，以減少冗余數據通信。

[1] 王瑞錦,秦志光,王佳昊.無線傳感器網絡分簇路由協(xié)議分析[J].電子科技大學學報,2013(3):81-86.

[2]EverE,LuchmunR,MostardaL,etal.UHEED—anunequalclusteringalgorithmforwirelesssensornetworks[J].AcademiaEdu,2012(12):185-193.

[3] 董國勇,彭 力,吳 凡,等.基于權值和代價函數的WSNs非均勻分簇路由算法[J].傳感器與微系統(tǒng),2015,34(3):134-136，143.

[4]SolisI,ObraczkaK.In-networkaggregationtrade-offsfordatacollectioninwirelesssensornetworks[J].InternationalJournalofSensorNetworks,2006,1(3-4):200-212.

[5] 陳偉琦,胡斌杰.基于高斯隸屬度的融合算法在改進LEACH中的應用[J].傳感器與微系統(tǒng),2011,30(2):135-138.

[6]WeiG,LingY,GuoB,etal.Prediction-baseddataaggregationinwirelesssensornetworks:CombininggreymodelandKalmanFilter[J].ComputerCommunications,2011,34(6):793-802.

[7]GedikB,LiuL,YuPS.ASAP:Anadaptivesamplingapproachtodatacollectioninsensornetworks[J].IEEETransactionsonParallelandDistributedSystems,2007,18(12):1766-1783.

[8]HeinzelmanW,ChandrakasanA,BalakrishnanH.Energy-efficientcommunicationprotocolsforwirelessmicrosensornetwork-s[C]∥Proceedingsofthe33rdAnnualHawaiiInternationalConferenceonSystemSciences,2000:3005-3014.

[9]MatthewsJH.Simpson's3/8rulefornumericalintegration:Numericalanalysis-numericalmethods[D].Fullerton:CaliforniaStateUniversity,2004.

Energy-efficient WSNs clustering data fusion algorithm*

SUN Chao, YANG Xiao-feng, PENG Li

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

In order to mitigate the“hot spot”problem in wireless sensor networks(WSNs),which is caused by the multi-hop transmission mode,an energy-efficient clustering data aggregation algorithm (EECDA)is proposed.The clustering algorithm(EECDA)for WSNs considering the residual energy of nodes,distance to base station and number of neighbor nodes periodically select cluster heads and divide into different size clusters;data in cluster are fused,using Simpson’s rule to predict receiving data premise of ensuring real-time and accuracy of data acquisition, reduce redundant of data,reduce traffic load and improve energy efficiency of the network.The simulation results show that the algorithm can efficiently predict the data to reduce the traffic data,compared to existing algorithms,it can effectively extend lifetime of the network.

wireless sensor networks(WSNs); uneven clustering; data aggregation; energy-efficient

10.13873/J.1000—9787(2017)04—0143—03

2016—04—28

國家自然科學基金資助項目(61502204)

TP 393

A

1000—9787(2017)04—0143—03

孫 超(1991-)，男，碩士研究生，主要研究方向為無線傳感器網絡。

彭 力(1967-),男,教授, 博士, 主要從事方向視覺傳感器網絡、人工智能工作。