蔣鵬，吳建峰,，吳斌，董林璽，王達(dá)

（1.杭州電子科技大學(xué) 信息與控制研究所，浙江 杭州 310018；2.杭州電子科技大學(xué) 射頻電路與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310018；3.杭州市質(zhì)量技術(shù)監(jiān)督檢測院，浙江 杭州 310018）

1 引言

在無線傳感器網(wǎng)絡(luò)(WSN, wireless sensor network)中，傳感器節(jié)點(diǎn)所采集的原始數(shù)據(jù)存在著大量的冗余信息，包括同一節(jié)點(diǎn)在相鄰時(shí)刻所采集數(shù)據(jù)在時(shí)間上的冗余以及地理區(qū)域上鄰近節(jié)點(diǎn)所采集數(shù)據(jù)在空間上的冗余，如果傳送攜帶了大量冗余信息的數(shù)據(jù)，將浪費(fèi)通信帶寬、增加網(wǎng)絡(luò)延時(shí)和節(jié)點(diǎn)能耗，進(jìn)而會(huì)影響整個(gè)傳感器網(wǎng)絡(luò)系統(tǒng)的穩(wěn)定性和壽命，傳輸原始數(shù)據(jù)前對(duì)冗余信息進(jìn)行壓縮是一種能有效降低節(jié)點(diǎn)能耗的機(jī)制[1]。

近年來，研究人員提出了許多面向無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)壓縮算法?；跁r(shí)間相關(guān)性的數(shù)據(jù)壓縮算法是一類典型的壓縮算法，它常常借助一些經(jīng)典編碼技術(shù)，如Huffman[2]、LZW[3]、RLE[4]等，側(cè)重于挖掘數(shù)據(jù)時(shí)間相關(guān)性，去除數(shù)據(jù)的時(shí)間冗余。基于空間相關(guān)性的數(shù)據(jù)壓縮算法也是一類典型的壓縮算法，它往往與分簇機(jī)制相結(jié)合[5～7]，力求充分挖掘數(shù)據(jù)空間相關(guān)性，降低并平衡網(wǎng)絡(luò)各節(jié)點(diǎn)的能耗。近年來，基于時(shí)間和空間相關(guān)性的數(shù)據(jù)壓縮算法受到越來越多的關(guān)注，如Ciancio和Donoho等人提出的算法[8,9]不但涉及去除數(shù)據(jù)的時(shí)間冗余，還探討了如何建立一條最優(yōu)的路徑，使得數(shù)據(jù)在沿著這條路徑傳遞時(shí)能夠最大限度地去除空間冗余。

在無線傳感器網(wǎng)絡(luò)中，差分機(jī)制（difference mechanism）常常被應(yīng)用在數(shù)據(jù)壓縮中[10～12]。結(jié)合差分機(jī)制的數(shù)據(jù)壓縮算法相同之處在于通過選擇一個(gè)參考數(shù)據(jù)，單個(gè)傳感器節(jié)點(diǎn)只需要傳送原始感知數(shù)據(jù)與參考數(shù)據(jù)之間的差值，從而去除時(shí)間冗余，或者地理區(qū)域上相鄰的傳感器節(jié)點(diǎn)只需要傳輸各自原始感知數(shù)據(jù)與參考數(shù)據(jù)之間的差值，從而去除空間冗余，而不同之處在于對(duì)差值編碼的選擇。一種較為簡單的差分編碼壓縮算法（DCCM, differential code compression method）是對(duì)差值進(jìn)行二進(jìn)制編碼[12]，然而DCCM算法存在以下不足之處。

1) DCCM 算法沒有充分考慮參考數(shù)據(jù)與感知數(shù)據(jù)序列相關(guān)性之間的關(guān)系，往往只是簡單地將感知數(shù)據(jù)序列的平均值作為參考數(shù)據(jù)，缺乏合理性。

2) DCCM 算法只是簡單地對(duì)感知數(shù)據(jù)序列和參考數(shù)據(jù)進(jìn)行一次性求差并對(duì)差值進(jìn)行二進(jìn)制編碼，無法充分有效地挖掘數(shù)據(jù)相關(guān)性。

受到 DCCM 算法的啟發(fā)，本文提出了一種新的基于自適應(yīng)最優(yōu)消零的傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮（AOZS）算法，AOZS算法首先對(duì)遞增排列的感知數(shù)據(jù)序列進(jìn)行相關(guān)位和位數(shù)因子分析，以尋找一個(gè)最優(yōu)位數(shù)因子，然后利用該最優(yōu)位數(shù)因子對(duì)數(shù)據(jù)序列進(jìn)行消零運(yùn)算和二進(jìn)制編碼。AOZS算法屬于無損壓縮算法，能夠?qū)鞲衅骶W(wǎng)絡(luò)的數(shù)據(jù)進(jìn)行有效地壓縮，減少網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，降低節(jié)點(diǎn)能耗，減小網(wǎng)絡(luò)延時(shí)。

2 自適應(yīng)最優(yōu)消零壓縮方法

下面給出自適應(yīng)最優(yōu)消零壓縮算法所涉及的相關(guān)術(shù)語。

相關(guān)位corr，表示數(shù)據(jù)序列中相等的數(shù)據(jù)。在遞增排列的數(shù)據(jù)序列（Z1,Z2,…,Zn）中，若 Zk(1＜k≤n)的相關(guān)位為1，則Zk與Zk?1相等，若相關(guān)位為0，則Zk與Zk?1不相等，其中，Z1的相關(guān)位始終為0。

編碼因子 d，指每階消零運(yùn)算中數(shù)據(jù)序列所減去的整數(shù)值，算法將根據(jù)可選位數(shù)因子對(duì)其進(jìn)行二進(jìn)制編碼。

最大編碼因子Di，指位數(shù)因子Ci可以表示的最大數(shù)值，Di反映了相鄰數(shù)據(jù)間可允許的最大差值，如果相鄰數(shù)據(jù)變化過大，則可以相應(yīng)地增大位數(shù)因子，以擴(kuò)大編碼的適用范圍。

位數(shù)因子Ci，指用來對(duì)編碼因子進(jìn)行二進(jìn)制編碼的位數(shù)。

本文采用3位二進(jìn)制來表示位數(shù)因子，000～111分別表示用2～9位二進(jìn)制對(duì)編碼因子d進(jìn)行編碼，稱之為C2～C9編碼，Ci(i=2,3,…,9)相應(yīng)的最大編碼因子為Di(i=2,3,…,9)。位數(shù)因子Ci，Ci編碼和最大編碼因子Di之間的關(guān)系如表1所示。

表1 Ci、Ci編碼和Di之間的關(guān)系

自適應(yīng)最優(yōu)消零壓縮算法的原理如圖1所示。

圖1 自適應(yīng)最優(yōu)消零壓縮算法的原理

自適應(yīng)最優(yōu)消零壓縮算法原理:給定一組遞增排列的整數(shù)數(shù)據(jù)序列（Z1,Z2,…,Zn），首先對(duì)其進(jìn)行相關(guān)位和位數(shù)因子分析，求出所有可選的位數(shù)因子Cx，并計(jì)算相應(yīng)的編碼長度 Qx，將最短編碼長度Qmin對(duì)應(yīng)的位數(shù)因子作為該數(shù)據(jù)序列的最優(yōu)位數(shù)因子Coptimal，然后基于該最優(yōu)位數(shù)因子執(zhí)行消零運(yùn)算和編碼，即在每階消零運(yùn)算下將數(shù)據(jù)序列中的非零數(shù)據(jù)減去一個(gè)編碼因子d，使得數(shù)據(jù)序列從小到大依次被消為零，最后，對(duì)該數(shù)據(jù)序列的相關(guān)位corr、最優(yōu)位數(shù)因子Coptimal以及編碼因子d進(jìn)行二進(jìn)制編碼。

下面詳細(xì)闡述可選的位數(shù)因子 Cx，編碼長度Qx，最優(yōu)位數(shù)因子Coptimal，最短編碼長度Qmin以及編碼因子d的計(jì)算原理。

位數(shù)因子Ci(i=2,3,…,9)的選擇會(huì)影響數(shù)據(jù)最終的編碼長度，若選擇過小，則很難恢復(fù)原始數(shù)據(jù)，若選擇過大，則導(dǎo)致最終編碼過長。設(shè)有M個(gè)遞增排列的整數(shù)數(shù)據(jù)（Z1,Z2,…,ZM），其中，有N個(gè)數(shù)據(jù)是互不相等的，最小值為α，相鄰數(shù)據(jù)間最大差值為β。設(shè) Cx為消零編碼運(yùn)算的可選位數(shù)因子，則Cx滿足以下條件

若Tα=0或Tβ=0，則表明數(shù)據(jù)大小或變化幅值超出了位數(shù)因子Ci所能編碼的范圍，此時(shí)需要用3位以上的二進(jìn)制來表示位數(shù)因子Ci，以擴(kuò)大編碼的適用范圍。

設(shè)可選位數(shù)因子Cx的最大編碼因子為Dx，則數(shù)據(jù)序列最終的編碼長度Qx為

給定一組遞增排列的整數(shù)數(shù)據(jù)序列，最優(yōu)位數(shù)因子為Coptimal，Coptimal的最大編碼因子為Doptimal，且在第 i(i=1,2,…)階消零運(yùn)算時(shí)數(shù)據(jù)序列中最小非零數(shù)據(jù)為Zmin，則第i階消零運(yùn)算的編碼因子d為

例如，有一組遞增排列的整數(shù)數(shù)據(jù)序列{15,18,18, 24,26,26}，容易得到corr=001001，M=6，N=4，α=15，β=6，由式(2)、式(3)可得Tα=4，Tβ=3，因此可選位數(shù)因子Cx∈[3,4]。由式(4)得到Qx|(Cx=3)=27，Qx|(Cx=4)=25，因此最優(yōu)位數(shù)因子Coptimal=C4，接著執(zhí)行消零運(yùn)算，第一階消零運(yùn)算中，由式(5)得到編碼因子 d=15，原始數(shù)據(jù)序列減去編碼因子15后，得到一階數(shù)據(jù)序列{0,3,3,9,11,11}；第二階消零運(yùn)算中，由式(5)得到編碼因子d=3，一階數(shù)據(jù)序列中非零數(shù)據(jù)減去編碼因子3后，得到二階數(shù)據(jù)序列{0,0,0,6,8,8}；如此反復(fù)運(yùn)算直到數(shù)據(jù)序列中各數(shù)據(jù)均被消為零，最后，對(duì)相關(guān)位corr和最優(yōu)位數(shù)因子C4進(jìn)行編碼，此外，因?yàn)镃4=4，所以采用4位二進(jìn)制對(duì)各階編碼因子{15,3,6,2}進(jìn)行編碼，C4編碼的壓縮流程如表2所示。

表2 C4編碼壓縮流程

由表 2可得，編碼為 100, 001001, 11110011,0110, 0010。其中，編碼的1～3bit是最優(yōu)位數(shù)因子C4的二進(jìn)制編碼，4～9bit是相關(guān)位 corr編碼，10～25bit是編碼因子d的4位二進(jìn)制編碼。

通常，傳感器節(jié)點(diǎn)所采集的為非整數(shù)數(shù)據(jù)，因此需要對(duì)上述自適應(yīng)最優(yōu)消零壓縮算法做相應(yīng)改進(jìn)。給定一組遞增排列的數(shù)據(jù)序列，數(shù)據(jù)的最小精度為 k(k＜1)，最小數(shù)據(jù)為 Zmin，相鄰數(shù)據(jù)間最大差值為λ，引入一個(gè)消整因子η，minZη=，其中，為向下取整符號(hào)，設(shè)

本文采用8位二進(jìn)制對(duì)消整因子η進(jìn)行編碼，則數(shù)據(jù)序列最終編碼長度Qx的計(jì)算公式為

例如，有一組遞增排列的數(shù)據(jù)序列{21.7,21.8,22.4,22.4,22.5,23.0}，容易得到corr=000100，M=6，N=5，Zmin=21.7，k=0.1，λ=0.6，η=21，由式(6)、式(7)可以得到α=7，β=6，由式(2)、式(3)可得Tα=Tβ=3，可選位數(shù)因子 Cx=C3，由式(8)得到Qx|(Cx=3)=32，因此最優(yōu)位數(shù)因子 Coptimal=C3。首先，將原始數(shù)據(jù)序列減去消整因子η，得到數(shù)據(jù)序列{0.7,0.8,1.4,1.4,1.5,2.0}，再乘以最小精度的倒數(shù)1/ k，得到數(shù)據(jù)序列{7,8,14,14,15,20}，然后執(zhí)行消零運(yùn)算，第一階消零運(yùn)算中，由式(5)得到編碼因子 d=7，數(shù)據(jù)序列減去編碼因子7后，得到一階數(shù)據(jù)序列{0,1,7,7,8,13}；第二階消零運(yùn)算中，由式(5)得到編碼因子 d=1，一階數(shù)據(jù)序列中非零數(shù)據(jù)減去編碼因子1后，得到二階數(shù)據(jù)序列{0,0,6,6,7,12}；如此反復(fù)運(yùn)算直到數(shù)據(jù)序列中各數(shù)據(jù)均被消為零，最后，對(duì)消整因子η、相關(guān)位corr和最優(yōu)位數(shù)因子 C3進(jìn)行編碼，此外，因?yàn)镃3=3，所以采用 3位二進(jìn)制對(duì)各階編碼因子{7,1,6,1,5}進(jìn)行編碼，C3編碼的壓縮流程如表 3所示。

表3 C3編碼壓縮流程

由表3可得，編碼為00010101, 011, 000100, 111,001, 110, 001, 101。其中，編碼的1～8bit是消整因子η的二進(jìn)制編碼，9～11bit是最優(yōu)位數(shù)因子 C3的二進(jìn)制編碼，12～17bit是相關(guān)位corr編碼，18～32bit是編碼因子d的3位二進(jìn)制編碼。

3 算法描述

大規(guī)模的傳感器網(wǎng)絡(luò)通常被劃分為多個(gè)簇，簇內(nèi)各傳感器節(jié)點(diǎn)將采集數(shù)據(jù)發(fā)送到簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給上一層節(jié)點(diǎn)，層層遞進(jìn)，直到基站為止，從而形成一個(gè)樹形分簇結(jié)構(gòu)，在這種樹形分簇結(jié)構(gòu)下，基于AOZS的傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法流程描述如下。

1) 簇內(nèi)傳感器節(jié)點(diǎn)將在時(shí)刻{t1,t2,…,tn}采集到的n個(gè)數(shù)據(jù){d1,d2,…,dn}進(jìn)行遞增排序，同時(shí)也對(duì)采集時(shí)刻進(jìn)行相應(yīng)排序，根據(jù)自適應(yīng)最優(yōu)消零壓縮算法原理計(jì)算數(shù)據(jù)序列的最小編碼長度 Qmin_d，并求出相應(yīng)的最優(yōu)位數(shù)因子 Coptimal_d，然后基于最優(yōu)位數(shù)因子對(duì)數(shù)據(jù)序列進(jìn)行消零運(yùn)算和編碼，去除時(shí)間冗余，得到壓縮后的數(shù)據(jù)。

2) 傳感器節(jié)點(diǎn)將壓縮后的數(shù)據(jù)傳送到簇頭節(jié)點(diǎn)，數(shù)據(jù)分組格式為{node_id, ＜time_stamp＞,data_ code}，其中，node_id為傳感器節(jié)點(diǎn)的ID號(hào)，＜time_ stamp＞為遞增排列后各數(shù)據(jù)所對(duì)應(yīng)的時(shí)間槽，data_code為數(shù)據(jù)序列的編碼，前8位表示消整因子。

3) 簇頭節(jié)點(diǎn)接收簇內(nèi)各傳感器節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組后，分別提取 data_code中消整因子η的二進(jìn)制編碼并轉(zhuǎn)換為十進(jìn)制數(shù)，得到消整因子序列，然后對(duì)消整因子序列進(jìn)行遞增排序，同時(shí)也根據(jù)消整因子序列的順序?qū)Ω鞴?jié)點(diǎn)的數(shù)據(jù)分組進(jìn)行相應(yīng)排序，并根據(jù)自適應(yīng)最優(yōu)消零壓縮算法原理計(jì)算其最小編碼長度Qmin_s，求出相應(yīng)的最優(yōu)位數(shù)因子Coptimal_s，然后基于最優(yōu)位數(shù)因子對(duì)消整因子序列進(jìn)行消零運(yùn)算和編碼，去除空間冗余，得到再壓縮后的數(shù)據(jù)。

4) 簇頭節(jié)點(diǎn)將再壓縮后的數(shù)據(jù)發(fā)送到上一層節(jié)點(diǎn)，數(shù)據(jù)分組格式為{s_code, ＜cluster_code＞}，其中，s_code為消整因子序列的編碼，＜cluster_ code＞為遞增排列后的消整因子序列所對(duì)應(yīng)的傳感器節(jié)點(diǎn)數(shù)據(jù)分組{node_id, ＜time_stamp＞, data_ code}，但此時(shí)data_code中的消整因子編碼已被提取。

5) 上一層節(jié)點(diǎn)直接將已經(jīng)去除了時(shí)間和空間冗余的數(shù)據(jù)分組{s_code, ＜cluster_code＞}路由至基站。

基于AOZS的傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法流程如圖2所示。

4 仿真算例

本節(jié)首先介紹了幾項(xiàng)傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法的性能評(píng)價(jià)指標(biāo)，然后通過 NS2仿真實(shí)驗(yàn)對(duì)AOZS算法和DCCM算法進(jìn)行了比較。

圖2 基于AOZS的傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法流程

4.1 性能評(píng)價(jià)指標(biāo)

1) 壓縮比(CR, compression ratio)

其中，SCP為壓縮后的數(shù)據(jù)量，SOR為原始數(shù)據(jù)量。CR越小，則壓縮后的數(shù)據(jù)量占原始數(shù)據(jù)量的比例越小，壓縮性能越好。

2) 節(jié)點(diǎn)平均能耗(AEC, average energy consumption)

采用一階無線模型(first order radio model)[13]來計(jì)算節(jié)點(diǎn)能耗

其中，Ep和 Ec分別為節(jié)點(diǎn)的計(jì)算能耗和無線通信能耗，無線通信能耗Ec可以分為無線發(fā)射能耗ETx和無線接收能耗 ERx，由于傳感器節(jié)點(diǎn)的計(jì)算能耗相對(duì)于無線通信能耗而言可以忽略不計(jì)，因而有

節(jié)點(diǎn)的能耗與節(jié)點(diǎn)發(fā)送或者接收數(shù)據(jù)分組的時(shí)間有關(guān)，數(shù)據(jù)分組越長則節(jié)點(diǎn)發(fā)送或者接收的時(shí)間越長能耗也越大，所以節(jié)點(diǎn)的發(fā)送能耗ETx可由節(jié)點(diǎn)發(fā)射功率PTx與數(shù)據(jù)發(fā)送所用時(shí)間TTx的乘積表示，節(jié)點(diǎn)的接收能耗ERx可由節(jié)點(diǎn)接收功率PRx與數(shù)據(jù)接收所用時(shí)間TRx的乘積表示，即

所以節(jié)點(diǎn)能耗為

本文對(duì)無線發(fā)射能耗 ETx和無線接收能耗 ERx的計(jì)算建立在基于ZigBee協(xié)議的CC2430硬件平臺(tái)上。CC2430微控器的內(nèi)核運(yùn)行在32MHz，無線發(fā)射電流為 25mA，無線接收電流為 27mA，供電電壓為3.3V，因此無線發(fā)射功率PTx=0.0825W，無線接收功率PRx=0.0891W。本文將根據(jù)式(14)計(jì)算傳感器節(jié)點(diǎn)的能耗，并將節(jié)點(diǎn)的平均能耗作為壓縮算法的性能評(píng)價(jià)指標(biāo)。

3) 網(wǎng)絡(luò)延時(shí)(ND, network delay)

本文對(duì)網(wǎng)絡(luò)延時(shí)的計(jì)算建立在基于 ZigBee協(xié)議的CC2430硬件平臺(tái)上，CC2430一個(gè)指令周期為1/32μs，網(wǎng)絡(luò)延時(shí)（DNTD）由2部分組成:從采集節(jié)點(diǎn)發(fā)送數(shù)據(jù)到接收節(jié)點(diǎn)收到數(shù)據(jù)的傳輸延時(shí)(DTTD)，節(jié)點(diǎn)運(yùn)行數(shù)據(jù)壓縮算法產(chǎn)生的計(jì)算延時(shí)(DCTD)，即

4.2 仿真結(jié)果與分析

本文所采用的仿真工具為ns-allinone-2.34，數(shù)據(jù)計(jì)算處理工具為 GNU Awk-3.1.5，作圖工具為gnuplot-4.3。仿真中節(jié)點(diǎn)的屬性設(shè)置如下:所有節(jié)點(diǎn)均為靜止?fàn)顟B(tài)，節(jié)點(diǎn)的無線傳播模型為雙徑地面(two ray ground)反射方式，節(jié)點(diǎn)的傳輸距離為40m，載波偵聽范圍為 88m，天線采用 Omni Antenna，發(fā)射頻率為2.4GHz；物理層和MAC層協(xié)議采用IEEE 802.15.4，路由層協(xié)議采用AODV，流量發(fā)生器采用CBR；節(jié)點(diǎn)每秒采集發(fā)送一次數(shù)據(jù)分組，發(fā)送速率為40kbit/s。

圖3 網(wǎng)絡(luò)場景

仿真時(shí)，網(wǎng)絡(luò)場景如圖3所示，整個(gè)傳感器網(wǎng)絡(luò)由101個(gè)節(jié)點(diǎn)組成，橫向與縱向相鄰的節(jié)點(diǎn)相距75m，對(duì)角相鄰的節(jié)點(diǎn)相距5m。網(wǎng)絡(luò)中包含1個(gè)基站（節(jié)點(diǎn)號(hào)為0）、3個(gè)分簇以及每個(gè)分簇內(nèi)的7個(gè)采集節(jié)點(diǎn)（簇頭節(jié)點(diǎn)號(hào)和采集節(jié)點(diǎn)號(hào)如表4所示）。節(jié)點(diǎn)采集的每個(gè)數(shù)據(jù)長度均為2byte，實(shí)驗(yàn)數(shù)據(jù)來源于Intel-伯克利大學(xué)聯(lián)合研究實(shí)驗(yàn)室利用無線傳感器節(jié)點(diǎn)采集的溫度數(shù)據(jù)，整個(gè)仿真運(yùn)行1000s。接下來本文將分析和比較當(dāng)節(jié)點(diǎn)數(shù)據(jù)采集量從 10～100之間變化時(shí)AOZS算法和DCCM算法的各項(xiàng)性能指標(biāo)。

表4 簇頭和分簇內(nèi)采集節(jié)點(diǎn)號(hào)

由圖4可以看到，在節(jié)點(diǎn)數(shù)據(jù)采集量相同的條件下，AOZS算法的壓縮比低于DCCM算法，壓縮性能更優(yōu)，這是因?yàn)锳OZS算法能很好地挖掘了數(shù)據(jù)間的相關(guān)性，基于最優(yōu)位數(shù)因子的編碼最大程度地去除了冗余信息，本文采用8位二進(jìn)制對(duì)DCCM算法的均值和差值進(jìn)行編碼，因此DCCM算法的壓縮比始終高于0.5。隨著節(jié)點(diǎn)采集數(shù)據(jù)量的增加，數(shù)據(jù)的時(shí)間相關(guān)性越來越高，AOZS算法的編碼因子能夠描述越來越多的原始數(shù)據(jù)，充分挖掘了數(shù)據(jù)的時(shí)間相關(guān)性，因此壓縮比越來越小，逐漸趨于平穩(wěn)。

圖4 AOZS、DCCM算法壓縮比對(duì)比

節(jié)點(diǎn)能耗是衡量傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法性能的一個(gè)關(guān)鍵指標(biāo)，引入數(shù)據(jù)壓縮算法后加節(jié)點(diǎn)的計(jì)算能耗，但相對(duì)于節(jié)點(diǎn)的無線通信能耗而言，計(jì)算能耗可忽略不計(jì)，因此，仿真中的能耗只需考慮節(jié)點(diǎn)的無線通信能耗，可通過NS2自帶的能量模型獲取，仿真程序運(yùn)行之前設(shè)定節(jié)點(diǎn)的初始能量、收發(fā)功率、數(shù)據(jù)收發(fā)速率，根據(jù)數(shù)據(jù)分組長度便可計(jì)算出每次活動(dòng)后節(jié)點(diǎn)的剩余能量，并將其保存至trace文件，仿真結(jié)束后通過GNU Awk-3.1.5工具從 trace文件中提取所有節(jié)點(diǎn)的剩余能量信息并累加即可得網(wǎng)絡(luò)的剩余能量。此外，根據(jù)節(jié)點(diǎn)的初始能量以及節(jié)點(diǎn)總數(shù)可算出網(wǎng)絡(luò)的初始總能量，其與網(wǎng)絡(luò)的剩余能量的差值即為網(wǎng)絡(luò)運(yùn)行過程中總能耗，將總能耗與網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)相除即可得出節(jié)點(diǎn)的平均能耗。本仿真中，節(jié)點(diǎn)總數(shù)為101個(gè)，各節(jié)點(diǎn)的初始能量為 1J，節(jié)點(diǎn)收發(fā)功率計(jì)算基于CC2430硬件平臺(tái)，發(fā)射功率PTx=0.0825W，無線接收功率PRx=0.0891W。

由圖5可以看到，在節(jié)點(diǎn)數(shù)據(jù)采集量相同的條件下，AOZS算法的節(jié)點(diǎn)平均能耗明顯低于DCCM算法，這是因?yàn)锳OZS算法能夠更好地挖掘數(shù)據(jù)的相關(guān)性，最大程度地去除冗余信息。隨著節(jié)點(diǎn)采集數(shù)據(jù)量的增加，2種算法的節(jié)點(diǎn)平均能耗均會(huì)提升，這是由于節(jié)點(diǎn)數(shù)據(jù)采集量增加時(shí)，網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量必然增加，從而導(dǎo)致節(jié)點(diǎn)能耗上升。

圖5 AOZS、DCCM算法節(jié)點(diǎn)平均能耗對(duì)比

仿真中的延時(shí)可通過NS2的trace文件和模擬計(jì)算獲取，trace文件可記錄發(fā)送節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組的時(shí)間與接收節(jié)點(diǎn)接收數(shù)據(jù)分組的時(shí)間，仿真結(jié)束后通過GNU Awk-3.1.5從trace文件中提取并計(jì)算各個(gè)數(shù)據(jù)分組從發(fā)送節(jié)點(diǎn)傳輸至接收節(jié)點(diǎn)的延時(shí)，并記錄傳輸次數(shù)，將各次延時(shí)累加并除以總傳輸次數(shù)即可得傳輸延時(shí)DTTD。節(jié)點(diǎn)的計(jì)算延時(shí)通過模擬計(jì)算獲得，算法運(yùn)行的硬件平臺(tái)基于CC2430，一條指令執(zhí)行周期為1/32μs，AOZS算法的指令為200條，DCCM算法的指令為50條[12]，通過計(jì)算即可得計(jì)算延時(shí)DCTD。DTTD與DCTD相加即可得網(wǎng)絡(luò)延時(shí)DNTD。

由圖6可以看到，2種算法的網(wǎng)絡(luò)延時(shí)均隨著節(jié)點(diǎn)采集數(shù)據(jù)量的增加而增加。當(dāng)節(jié)點(diǎn)數(shù)據(jù)采集量較小時(shí)，DCCM算法的延時(shí)略小于AOZS算法，因?yàn)榇藭r(shí)影響網(wǎng)絡(luò)延時(shí)的決定性因素是對(duì)數(shù)據(jù)進(jìn)行壓縮的計(jì)算延時(shí)，而 DCCM 算法的計(jì)算延時(shí)要小于AOZS算法。隨著節(jié)點(diǎn)采集數(shù)據(jù)量的增加，DCCM算法的延時(shí)明顯大于AOZS算法，因?yàn)榇藭r(shí)的決定性因素已不是計(jì)算延時(shí)，而是數(shù)據(jù)傳輸引起的延時(shí)，AOZS算法大大降低了網(wǎng)絡(luò)中需要傳輸?shù)臄?shù)據(jù)量，從而減小了網(wǎng)絡(luò)延時(shí)。

圖6 AOZS、DCCM算法網(wǎng)絡(luò)延時(shí)對(duì)比

5 結(jié)束語

無線傳感器網(wǎng)絡(luò)采集的數(shù)據(jù)中存在著大量時(shí)間和空間冗余信息，本文針對(duì)該問題提出了一種自適應(yīng)最優(yōu)消零壓縮（AOZS）算法，AOZ算法能夠自適應(yīng)地尋找最優(yōu)位數(shù)因子，對(duì)遞增排列的原始數(shù)據(jù)序列進(jìn)行消零運(yùn)算和編碼，使得其最終編碼長度最短，從而達(dá)到數(shù)據(jù)壓縮的目的。仿真結(jié)果表明，AOZS算法的總體性能比DCCM算法更優(yōu)，能夠有效地去除傳感器網(wǎng)絡(luò)采集數(shù)據(jù)中存在的冗余信息，減少了網(wǎng)絡(luò)的數(shù)據(jù)傳輸量和延時(shí)，降低了節(jié)點(diǎn)功耗。

[1]JENNIFER Y, BISWANATH M, DIAK G.Wireless sensor network survey[J].Computer Networks, 2008, 52(12):2292-2330.

[2]CAPO-CHICHI E P, GUYENNET H, FRIEDT J M.K-RLE:a new data compression algorithm for wireless sensor network[A].International Conference on Sensor Technologies and Applications[C].Glyfada, Athens, 2009.502-507.

[3]ZHANG H, FAN X P, LIU S Q, et al.Design and realization of improved LZW algorithm for wireless sensor networks[A].International Conference on Information Science and Technology(ICIST)[C].Changsha, China, 2011.671-675.

[4]MO Y B, QIU Y B, LIU J Z, et al.A data compression algorithm based on adaptive huffman code for wireless sensor networks[A].International Conference on Intelligent Computation Technology and Automation (ICICTA) [C].Nanjing, China, 2011.3-6.

[5]XIE L, CHEN L J, CHEN D X.Clustering-based approximate scheme for data aggregation over sensor networks[J].Journal of Software,2009, 20(4):1023-1037.

[6]HU J, SHEN L F.Novel clustering algorithm for wireless sensor networks[J].Journal on Communications, 2008, 29(7):20-29.

[7]ZHU X R, SHEN L F, TAK-SHING P Y.Hausdorff clustering and minimum energy routing for wireless sensor networks[J].IEEE Transactions on Vehicular Technology, 2009,58(2):990-997.

[8]CIANCIO A, PATTEM S, ORTEGA A, et al.Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm[A].The Fifth International Conference on Information Processing in Sensor Networks[C].Palo Alto, CA, USA, 2006.309-316.

[9]DONOHO D L.Message passing algorithms for compressed sensing:I.motivation and construction[A].IEEE Information Theory Workshop 2010[C].Cairo, Egypt, 2010.1289-1306.

[10]MARCELLONI F, VECCHIO M.A simple algorithm for data compression in wireless sensor networks[J].IEEE Communications Letters,2008, 12(6):411-413.

[11]范祥輝，李士寧，杜鵬雷等.WSN中一種自適應(yīng)無損數(shù)據(jù)壓縮機(jī)制[J].計(jì)算機(jī)測量與控制, 2010, 18(2):463-465.FAN X H, LI S N, DU P L, et al.Simple algorithm for self-adapting lossless data compression in WSN[J].Computer Measurement & Control, 2010, 18(2):463-465.

[12]夏永成，陳黎黎，陳曦.無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)壓縮研究結(jié)合小波提升算法和差分機(jī)制[J].計(jì)算機(jī)工程與應(yīng)用, 2010, 46(2):109-112.XIA Y C, CHEN L L, CHEN X.Research on data compression in wireless sensor networks-with wavelet lifting algorithm and difference mechanism[J].Computer Engineering and Applications, 2010,46(2):109-112.

[13]WANG A, CHANDRAKSAN A.Energy-efficient DSPs for wireless sensor networks[J].IEEE Signal Processing Magazine, 2002, 19(4):68-78.