基于自適應加權與LZW的WSNs層次式數據融合算法*

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

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

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

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

1 基本理論

1.1 自適應加權算法

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

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

總均方差為:

根據多元函數求極值的相關理論，可以求出總均方誤差最小時所對應的加權因子為:

此時所對應的最小均方誤差為:

1.2 LZW算法

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

1.3 層次式數據融合算法

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

當簇頭節點存儲的估計值到一定的信息量時，簇頭節點調用LZW壓縮算法，對輸入的數據流進行分析，在對存儲的數據進行編碼的同時自適應地生成一個串表，此串表記錄了所有在此前出現過的不重復的字符串。通過將當前的輸入數據流與該串表中字符串的比較來確定輸出值并完成對串表的更新。簇頭節點將數據壓縮后再在網內傳輸，減少了網內傳輸的數據量。

層次式數據融合算法在提高數據采集精度的前提下，減少了網絡數據傳輸的路徑，簇頭節點將數據壓縮后再傳輸減少了網絡數據傳輸的數據量，從而降低了網絡的整體能耗。

2 層次式數據融合算法建模

2.1 WSNs簇狀網絡拓撲結構

當前無線傳感器網絡的數據融合方案可以分為:集中式融合［3］、基于樹的融合［11］、靜態分簇融合［12］和動態分簇融合［13］。從網內數據融合處理、數據采集的精度、網絡數據采集的效率綜合考慮，本文采用靜態分簇的融合方案。無線傳感器簇狀網絡拓撲結構［14］如圖1所示。

圖1 無線傳感器簇狀網絡拓撲結構

2.2 LZW算法性能測試

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

圖2 不同算法使用RAM值

圖3 不同算法等價的計算次數

2.3 自適應加權與LZW層次式數據融合應用模型

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

圖4 自適應加權與LZW層次式數據融合應用模型

3 算法仿真分析

3.1 測試過程

本算法用MATLAB以圖1簇狀網絡拓撲結構中的簇頭節點A為仿真對象，測試簇頭節點A采用自適應加權與LZW層次式數據融合算法時以簇頭A為中心所組成的網絡的整體能耗。

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

3.2 實驗仿真與分析

仿真測試結果如圖5所示。

圖5 算法仿真效果圖

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

簇頭節點一次采集的數據如表1所示，對表1數據分別進行層次式數據融合算法和算術平均處理。

表1 傳感器簇頭節點一次采集的數據

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

從以上數據分析知，多個無線傳感器節點采用自適應加權與LZW層次式融合算法得出的估計值比單個傳感器節點和多個傳感器節點采集的數據算術平均估計的方差都要小，本算法提高了無線傳感器網絡數據采集的精度。

4 結論

本文提出了基于自適應加權與LZW的層次數據融合算法:終端數據采集節點將采集的數據算術平均后傳遞給簇頭節點;簇頭節點將各個傳感器節點送來的數據以自適應加權進行融合處理，再將融合后的數據以410 B進行打包，用LZW壓縮算法壓縮后以多跳通信的方式傳遞到網關節點。

仿真結果表明，應用基于自適應加權與LZW的層次式數據融合算法可以有效地降低整個網絡的能耗、提高數據采集的精度及網絡數據采集的效率，有一定的實用價值。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，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］張強，盧瀟，崔曉臣.基于分簇的無線傳感器網絡數據聚合方案研究［J］.傳感技術學報，2010，(12):1778－1779.

［4］于宏毅，李鷗，張效義.無線傳感器網絡理論、技術與實現［M］.國防工業出版社，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］周益明.基于無線傳感器網絡的溫室群監測與控制系統的關鍵技術研究與實現［D］.杭州:浙江大學，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］張品，姜亞光，陳磊.基于加權優化選擇兩級簇頭的WSN路由協議［J］.傳感技術學報，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.