基于自適應(yīng)加權(quán)與LZW的WSNs層次式數(shù)據(jù)融合算法*

張志偉，王新才，吉愛國，謝 磊

(1.青島理工大學(xué)理學(xué)院，山東青島2660332.青島理工大學(xué) 通信學(xué)院，山東 青島266033)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)中，傳感器節(jié)點具有的能量、處理能力、存儲能力和通信能力等都十分有限，需要整個網(wǎng)絡(luò)具有較高覆蓋密度來保證魯棒性和信息的準(zhǔn)確收集［1］。相鄰節(jié)點間收集的數(shù)據(jù)存在一定的冗余，浪費了通信帶寬和整個網(wǎng)絡(luò)的能量，降低了信息收集的效率。為了降低整個網(wǎng)絡(luò)的能耗，提高數(shù)據(jù)收集的準(zhǔn)確性和效率，傳感器節(jié)點需要在網(wǎng)絡(luò)內(nèi)部協(xié)同地處理所收集的數(shù)據(jù)。數(shù)據(jù)融合技術(shù)(Data Aggregation)很好的解決了上述問題［2－3］。

自適應(yīng)加權(quán)算法具有實現(xiàn)簡單、精度高的特點，被用于各種數(shù)據(jù)采集儀器、儀表和監(jiān)測系統(tǒng)中，在無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合應(yīng)用中所見不多。LZW是一種無損的，基于詞典的壓縮算法，由Lemple-Ziv-Welch三人共同創(chuàng)造。數(shù)據(jù)壓縮(Data Compression)是另一類減少傳感器節(jié)點采集數(shù)據(jù)傳輸量的技術(shù)［4］。LZW壓縮算法在PC中得到廣泛的應(yīng)用，但是在無線傳感器網(wǎng)絡(luò)中應(yīng)用很少。根據(jù)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)多跳逐層上傳的特點［5］，本文在前人工作基礎(chǔ)上提出了一種層次式數(shù)據(jù)融合算法，從不同的角度對數(shù)據(jù)進(jìn)行融合處理。

1 基本理論

1.1 自適應(yīng)加權(quán)算法

從含有噪聲的大量測量數(shù)據(jù)中估計一個非隨機(jī)量，由于測量的數(shù)據(jù)中存在噪聲，那么依據(jù)這些測量數(shù)據(jù)得到的估計值也存在估計誤差，該估計誤差也是一個隨機(jī)量，我們用均方誤差作為評價一個估計算法好壞的指標(biāo)。自適應(yīng)加權(quán)估計算法只需依靠各傳感器節(jié)點提供的采集數(shù)據(jù)，就可以自適應(yīng)的尋找其對應(yīng)的權(quán)數(shù)估計出均方誤差最小的值。

根據(jù)自適應(yīng)加權(quán)算法［6］，設(shè)n個傳感器采集數(shù)據(jù)的方差分別為所需估計的真值為X，各傳感器采集數(shù)據(jù)的測量值分別為 X1，X2，…，Xn。它們彼此相互獨立，并且是X的無偏估計;各傳感器采集數(shù)據(jù)的加權(quán)因子分別為W1，W2，…，Wn則估計后的值和加權(quán)因子滿足以下兩式:

總均方差為:

根據(jù)多元函數(shù)求極值的相關(guān)理論，可以求出總均方誤差最小時所對應(yīng)的加權(quán)因子為:

此時所對應(yīng)的最小均方誤差為:

1.2 LZW算法

LZW壓縮算法［7－10］是基于字典的無損壓縮方法，在編碼過程中動態(tài)生成編碼字典，該字典不需要通信線路傳給解碼器，在解碼過程中，動態(tài)生成編碼過程完全一致的解碼字典。

1.3 層次式數(shù)據(jù)融合算法

n個傳感器節(jié)點采集的數(shù)據(jù)值分別為X1，X2，…，Xn，數(shù)據(jù)值對應(yīng)的方差分別為簇頭節(jié)點接受n個傳感器節(jié)點采集的數(shù)據(jù)值和對應(yīng)的方差后，根據(jù)式(4)計算出各傳感器節(jié)點對應(yīng)的權(quán)值并為各個傳感器節(jié)點分配相應(yīng)的權(quán)值;簇頭節(jié)點根據(jù)式(1)計算出估計值并存儲。

當(dāng)簇頭節(jié)點存儲的估計值到一定的信息量時，簇頭節(jié)點調(diào)用LZW壓縮算法，對輸入的數(shù)據(jù)流進(jìn)行分析，在對存儲的數(shù)據(jù)進(jìn)行編碼的同時自適應(yīng)地生成一個串表，此串表記錄了所有在此前出現(xiàn)過的不重復(fù)的字符串。通過將當(dāng)前的輸入數(shù)據(jù)流與該串表中字符串的比較來確定輸出值并完成對串表的更新。簇頭節(jié)點將數(shù)據(jù)壓縮后再在網(wǎng)內(nèi)傳輸，減少了網(wǎng)內(nèi)傳輸?shù)臄?shù)據(jù)量。

層次式數(shù)據(jù)融合算法在提高數(shù)據(jù)采集精度的前提下，減少了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆窂?，簇頭節(jié)點將數(shù)據(jù)壓縮后再傳輸減少了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)臄?shù)據(jù)量，從而降低了網(wǎng)絡(luò)的整體能耗。

2 層次式數(shù)據(jù)融合算法建模

2.1 WSNs簇狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

當(dāng)前無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合方案可以分為:集中式融合［3］、基于樹的融合［11］、靜態(tài)分簇融合［12］和動態(tài)分簇融合［13］。從網(wǎng)內(nèi)數(shù)據(jù)融合處理、數(shù)據(jù)采集的精度、網(wǎng)絡(luò)數(shù)據(jù)采集的效率綜合考慮，本文采用靜態(tài)分簇的融合方案。無線傳感器簇狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［14］如圖1所示。

圖1 無線傳感器簇狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2.2 LZW算法性能測試

目前，針對無線傳感器網(wǎng)絡(luò)的無損數(shù)據(jù)壓縮研究還處于探索和起步階段，壓縮率是衡量算法好壞的根本標(biāo)志，但是在無線傳感器網(wǎng)絡(luò)中，能量要作為衡量算法的最重要因素?？紤]到數(shù)據(jù)壓縮對壓縮節(jié)點本身能耗及網(wǎng)絡(luò)路由節(jié)點所產(chǎn)生的影響，本文對現(xiàn)有的成熟的壓縮算法 LZW、LZO、LZSS、Zlib在IAR EW8051集成開發(fā)環(huán)境下進(jìn)行測試，設(shè)定IAR的芯片開發(fā)目標(biāo)是CC2430并對其他參數(shù)做配置，將各算法在IAR中進(jìn)行調(diào)試，找到Debug目錄下的List目錄，List目錄下的*.map文件詳細(xì)的描述了算法運行時占用的ROM、RAM及其他參數(shù)。各算法基于 CC2430［15－16］平臺測試結(jié)果如圖 2、圖 3 所示，圖2為各個數(shù)據(jù)壓縮算法運行時所需要的RAM，圖3為不同的算法壓縮528 B的數(shù)據(jù)計算的次數(shù)。從圖2和圖3可以直觀的看出，從算法運行時占用的RAM和壓縮相同數(shù)據(jù)量時計算的次數(shù)綜合考慮，LZW壓縮算法適合資源受限的傳感器節(jié)點使用。根據(jù)實驗測試，當(dāng)系統(tǒng)的詞典為512 B，一個壓縮的數(shù)據(jù)包為410 B時，壓縮算法的壓縮率可以到達(dá)1.28，具有較好的壓縮性能。512個條目的詞典大約占用2 618 B的RAM和1 262 B的Flash Memory，適合無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)融合的應(yīng)用。

圖2 不同算法使用RAM值

圖3 不同算法等價的計算次數(shù)

2.3 自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合應(yīng)用模型

根據(jù)自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合算法的原理，為了消除疏失誤差的影響，提高測量精度，無線傳感器節(jié)點每1 s進(jìn)行一次采樣，采集8個數(shù)據(jù)作算術(shù)平均并計算出方差后發(fā)送給簇頭節(jié)點，簇頭節(jié)點對接收到的多個無線傳感器節(jié)點數(shù)據(jù)去除最大值與最小值，然后根據(jù)自適應(yīng)算法進(jìn)行數(shù)據(jù)估計，再以410 B打包壓縮后以多跳通信的方式發(fā)送給匯聚節(jié)點，其應(yīng)用模型如圖4所示。

圖4 自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合應(yīng)用模型

3 算法仿真分析

3.1 測試過程

本算法用MATLAB以圖1簇狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的簇頭節(jié)點A為仿真對象，測試簇頭節(jié)點A采用自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合算法時以簇頭A為中心所組成的網(wǎng)絡(luò)的整體能耗。

編程實現(xiàn)簇頭節(jié)點A內(nèi)八個傳感器節(jié)點(a1、a2、a3、a4、a5、a6、a7、a8)間隔1 s采集數(shù)據(jù)八次，在傳感器節(jié)點內(nèi)分別對采集的數(shù)據(jù)計算平均值、方差;傳感器節(jié)點將均值和方差傳遞給A，A收到八個點的數(shù)據(jù)后去掉最大值與最小值，然后依據(jù)自適應(yīng)加權(quán)算法對數(shù)據(jù)進(jìn)行融合處理;A簇內(nèi)的節(jié)點不斷的給簇頭A發(fā)送數(shù)據(jù)，簇頭A接收到數(shù)據(jù)進(jìn)行融合處理后，以410 B為單位進(jìn)行打包壓縮，然后以多跳通信的方式，將采集的信息傳遞到匯聚節(jié)點。

3.2 實驗仿真與分析

仿真測試結(jié)果如圖5所示。

圖5 算法仿真效果圖

圖5中，◇表示不采用融合算法時整個網(wǎng)絡(luò)的能耗，網(wǎng)絡(luò)的總體能耗約為2.4×106nJ;☆表示采用自適應(yīng)加權(quán)算法時整個網(wǎng)絡(luò)的能耗，網(wǎng)絡(luò)的總體能耗約為1.1×106nJ;*表示采用自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合算法時整個網(wǎng)絡(luò)的能耗，網(wǎng)絡(luò)的總體能耗約為0.9×106nJ。由仿真結(jié)果知，采用自適應(yīng)加權(quán)算法，整個網(wǎng)絡(luò)的能耗降低了約54%;采用自適應(yīng)加權(quán)與LZW層次式數(shù)據(jù)融合算法，整個網(wǎng)絡(luò)的能耗降低了約62%。因此，本文提出的算法能有效的降低無線傳感器網(wǎng)絡(luò)整個網(wǎng)絡(luò)的能耗。

簇頭節(jié)點一次采集的數(shù)據(jù)如表1所示，對表1數(shù)據(jù)分別進(jìn)行層次式數(shù)據(jù)融合算法和算術(shù)平均處理。

表1 傳感器簇頭節(jié)點一次采集的數(shù)據(jù)

計算融合值:^X1=25.1143，此時方差為0.165 5;8個傳感節(jié)點采集數(shù)據(jù)的算術(shù)平均值為25.080 0，方差為0.298 5。將數(shù)據(jù)融合算法處理后的值、方差分別與各個傳感器節(jié)點采集的數(shù)據(jù)、方差及算術(shù)平均后的值、方差進(jìn)行對比。

從以上數(shù)據(jù)分析知，多個無線傳感器節(jié)點采用自適應(yīng)加權(quán)與LZW層次式融合算法得出的估計值比單個傳感器節(jié)點和多個傳感器節(jié)點采集的數(shù)據(jù)算術(shù)平均估計的方差都要小，本算法提高了無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集的精度。

4 結(jié)論

本文提出了基于自適應(yīng)加權(quán)與LZW的層次數(shù)據(jù)融合算法:終端數(shù)據(jù)采集節(jié)點將采集的數(shù)據(jù)算術(shù)平均后傳遞給簇頭節(jié)點;簇頭節(jié)點將各個傳感器節(jié)點送來的數(shù)據(jù)以自適應(yīng)加權(quán)進(jìn)行融合處理，再將融合后的數(shù)據(jù)以410 B進(jìn)行打包，用LZW壓縮算法壓縮后以多跳通信的方式傳遞到網(wǎng)關(guān)節(jié)點。

仿真結(jié)果表明，應(yīng)用基于自適應(yīng)加權(quán)與LZW的層次式數(shù)據(jù)融合算法可以有效地降低整個網(wǎng)絡(luò)的能耗、提高數(shù)據(jù)采集的精度及網(wǎng)絡(luò)數(shù)據(jù)采集的效率，有一定的實用價值。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:3－4，74.

［2］Heidemann J.Building Efficient Wireless Sensor Networks with Low-Level Naming［C］//18th ACM Symposium on Operating Systems Principles，October 2001:21－24.

［3］張強(qiáng)，盧瀟，崔曉臣.基于分簇的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合方案研究［J］.傳感技術(shù)學(xué)報，2010，(12):1778－1779.

［4］于宏毅，李鷗，張效義.無線傳感器網(wǎng)絡(luò)理論、技術(shù)與實現(xiàn)［M］.國防工業(yè)出版社，2008:203－207.

［5］Zhang Zhiwei，Wang Xincai，Ji Aiguo，et al.Design of Embedded Gateway of Wireless Sensor Networks Based on Dual-MCU［C］//ICIIE 2011:V1－57.

［6］周益明.基于無線傳感器網(wǎng)絡(luò)的溫室群監(jiān)測與控制系統(tǒng)的關(guān)鍵技術(shù)研究與實現(xiàn)［D］.杭州:浙江大學(xué)，2009:69－72.

［7］Mark Nelson.The Data Compression Book［M］.America:IDG Books Worldwide，Inc:181－194.

［8］Terry Welch.A Technique for High-Performance Data Compression［J］.IEEE Computer，1984，9(17): － .

［9］Ziv J，Lempel A.A Universal Algorithm for Sequential Data Compression［J］.IEEE Transactions on Information Theory，May 1977:337－343.

［10］DuncanBarclay.LZW_compression［EB/OL］.http://www.mathworks.com/matlabcentral/fileexchange/15428，2007.

［11］Bhaskar Krishnamachari，Deborah Estrin，Stephen B Wicker.The Impact of Data Aggregation in Wireless Sensor networks［C］//ICDCSW’02:Proceedings of the 22nd International Conference on Distributed Computing Systems，2002，575－578.

［12］Ghiasi S，Srivastava A，Yang X J，et al.Optimal Energy Aware Clustering in sensor Networks［J］.Special Issue:Special Section on Sensor Network Technology and Sensor Data Management，July 2004，2:258－269.

［13］WeiPeng Chen，Jennifer C Hou，Lui Sha.Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks［J］.IEEE Transactions on Mobile Computing，July－Aug 2004，3:258－271.

［14］張品，姜亞光，陳磊.基于加權(quán)優(yōu)化選擇兩級簇頭的WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報，2011，(3):448－449.

［15］Texas Instruments.System on Chip Solution for 2.4GHzIEEE802.15.4/ZigBee［S］.2007.

［16］Texas Instruments.Texas Instruments ZStack－1.4.3－1.2.1 Documents［S］.2008.