張志偉，王新才，吉愛(ài)國(guó)，謝 磊

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

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

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

1 基本理論

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

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

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

總均方差為:

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

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

1.2 LZW算法

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

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

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

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

層次式數(shù)據(jù)融合算法在提高數(shù)據(jù)采集精度的前提下，減少了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆窂?，簇頭節(jié)點(diǎn)將數(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ú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合方案可以分為:集中式融合［3］、基于樹(shù)的融合［11］、靜態(tài)分簇融合［12］和動(dòng)態(tài)分簇融合［13］。從網(wǎng)內(nèi)數(shù)據(jù)融合處理、數(shù)據(jù)采集的精度、網(wǎng)絡(luò)數(shù)據(jù)采集的效率綜合考慮，本文采用靜態(tài)分簇的融合方案。無(wú)線傳感器簇狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［14］如圖1所示。

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

2.2 LZW算法性能測(cè)試

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

圖2 不同算法使用RAM值

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

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

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

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

3 算法仿真分析

3.1 測(cè)試過(guò)程

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

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

3.2 實(shí)驗(yàn)仿真與分析

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

圖5 算法仿真效果圖

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

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

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

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

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

4 結(jié)論

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

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

［1］孫利民，李建中，陳渝，等.無(wú)線傳感器網(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ú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合方案研究［J］.傳感技術(shù)學(xué)報(bào)，2010，(12):1778－1779.

［4］于宏毅，李鷗，張效義.無(wú)線傳感器網(wǎng)絡(luò)理論、技術(shù)與實(shí)現(xiàn)［M］.國(guó)防工業(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ú)線傳感器網(wǎng)絡(luò)的溫室群監(jiān)測(cè)與控制系統(tǒng)的關(guān)鍵技術(shù)研究與實(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)化選擇兩級(jí)簇頭的WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，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.