朱容波, 李媛麗, 丁千傲, 虞脈

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

能耗始終是制約無線傳感器網(wǎng)絡(luò)性能的主要因素之一.傳感器節(jié)點能耗主要由計算模塊、通信模塊、傳感模塊和電源模塊四部分構(gòu)成[1,2].研究表明，傳感器節(jié)點間的傳輸能耗是影響網(wǎng)絡(luò)生命周期的主要因素[3].隨著無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜及逐漸朝大規(guī)模方向轉(zhuǎn)變，科學(xué)、高效地解決傳感網(wǎng)內(nèi)的海量數(shù)據(jù)冗余及巨大能量消耗問題變得十分重要[4].

傳感器網(wǎng)絡(luò)數(shù)據(jù)去冗余技術(shù)則為解決上述問題提供了可能[5,6].近幾年，數(shù)據(jù)去冗余的研究主要集中在統(tǒng)計學(xué)、數(shù)據(jù)壓縮和機器學(xué)習(xí)三方面.在基于統(tǒng)計學(xué)的數(shù)據(jù)去冗余方面，GANJEWAR等[7]使用分層式最小二乘法縮減數(shù)據(jù)傳輸技術(shù)，傳輸Sink節(jié)點要求的數(shù)據(jù)，從而延長網(wǎng)絡(luò)壽命.文獻[8]提出了一種自適應(yīng)時空相關(guān)預(yù)測算法，通過時間相關(guān)性與空間相關(guān)性預(yù)測感知數(shù)據(jù)，減少數(shù)據(jù)傳輸.DIAS等[9]通過數(shù)據(jù)傳輸協(xié)議(DaT)，減少冗余數(shù)據(jù)，降低數(shù)據(jù)傳輸能耗.

為減少傳輸數(shù)據(jù)量與降低數(shù)據(jù)傳輸能耗[10],LIAZID等采用歷史數(shù)據(jù)表來更新模型參數(shù)的方式[11]，考慮傳輸率的情況，提高預(yù)測模型的精確度.SALMAN等[12]提出雙向預(yù)測和數(shù)據(jù)采集的感知模型.RUSSO等[13]提出時間序列模型和基于非監(jiān)督類型的機器學(xué)習(xí)預(yù)測分析算法.

基于數(shù)據(jù)壓縮的去冗余方法在節(jié)省數(shù)據(jù)傳輸能耗方面具有良好的性能.李鵬等[14]的壓縮感知高能效數(shù)據(jù)收集方案，將壓縮感知應(yīng)用于路由樹協(xié)議，然而造成網(wǎng)絡(luò)能耗不均衡.楊浩等[15]設(shè)計的區(qū)域化壓縮感知數(shù)據(jù)收集方法，有效降低了數(shù)據(jù)傳輸量，且保留了數(shù)據(jù)原始特征.

盡管基于統(tǒng)計學(xué)、機器學(xué)習(xí)的數(shù)據(jù)去冗余算法能較好地提高數(shù)據(jù)壓縮性能，但缺少對去冗余數(shù)據(jù)與原始數(shù)據(jù)間的關(guān)聯(lián)性分析，在一定程度上降低了算法性能，導(dǎo)致高能耗與低生命周期的問題.基于壓縮的方法能很好地減少數(shù)據(jù)，但存在數(shù)據(jù)精確度低的不足.雖然上述三類方法在降低數(shù)據(jù)傳輸能耗方面效果明顯，但在一定程度上導(dǎo)致了部分重要特征數(shù)據(jù)的缺失，影響了傳感器接入點決策的準(zhǔn)確性.

為解決上述方法的不足，本文提出一種基于最大時間閾值與自適應(yīng)步長的時間相關(guān)性感知數(shù)據(jù)去冗余算法(TCDA).TCDA針對數(shù)據(jù)波動平穩(wěn)型的情況，引入最大時間閾值T_max控制數(shù)據(jù)相似閾值Th失效的問題，減少局部特征值的誤差，實現(xiàn)通過部分特征數(shù)據(jù)準(zhǔn)確獲取感知數(shù)據(jù)的關(guān)鍵信息.針對計算能耗問題，TCDA采用自適應(yīng)步長機制，結(jié)合數(shù)據(jù)相似距離計算規(guī)則的特點，控制數(shù)據(jù)相似比較步長，進而減少數(shù)據(jù)計算量，降低計算能耗.

1 去冗余算法TCDA

1.1 問題描述

傳感器網(wǎng)絡(luò)中包含一個匯聚節(jié)點(Sink)與N個傳感器節(jié)點，匯聚節(jié)點位于探測區(qū)域外部，傳感器節(jié)點隨機分布在監(jiān)測區(qū)域.系統(tǒng)模型如圖1所示.系統(tǒng)主要由3個簇組成，每個簇中包含一個簇頭(CHi)和一些簇內(nèi)節(jié)點(SNi)，SNi負責(zé)采集自身感知數(shù)據(jù)，CHi負責(zé)采集自身感知數(shù)據(jù)的同時收集簇內(nèi)各個節(jié)點的數(shù)據(jù).Sink主要負責(zé)將各個簇頭CHi收集的數(shù)據(jù)匯聚起來，然后發(fā)送給用戶.TCDA算法涉及的符號如表1所示.

圖1 系統(tǒng)模型圖

表1 符號表

無線傳感器網(wǎng)絡(luò)中各個節(jié)點均以相同的頻率對事件進行數(shù)據(jù)采集(如圖2所示).

圖2 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集模式

CHi節(jié)點采集的數(shù)據(jù)集DCHi為：

DCHi={DSN1,DSN2,DSN3,…,DSNn}，

(1)

DSNi={x0,x1,x2,x3,x4,…,xn}，

(2)

RSNi=f(DSNi)，

(3)

RCHi={RSN1,RSN2,RSN3,…,RSNn}，

(4)

其中DSNi表示SNi節(jié)點在時間T={t0,t1,t2,t3,t4,…,tn}時，所采集的感知數(shù)據(jù)集合；RSNi表示SNi節(jié)點感知的數(shù)據(jù)DSNi經(jīng)過冗余處理函數(shù)f(DSNi)處理后的結(jié)果數(shù)據(jù)；RCHi表示CHi最終經(jīng)過冗余處理后的結(jié)果數(shù)據(jù).由于存在SNi節(jié)點在時間T集合內(nèi)對同一事件連續(xù)多次感知的情況，并且感知數(shù)據(jù)彼此間差異甚小，因此將{x1,x2,x3,x4}視為冗余數(shù)據(jù)去除，同時將非冗余數(shù)據(jù)傳輸給簇頭CHi.

1.2 TCDA算法詳細介紹

無線傳感器網(wǎng)絡(luò)采集數(shù)據(jù)具有時序性、有效性以及冗余度高的特點，同時已有方法存在冗余度高和計算量大的問題，TCDA算法不僅對無線傳感器網(wǎng)絡(luò)的時序性與有序性加以考慮，而且解決了冗余度高和計算量大的問題.TCDA算法如下所示.

Input: DSN1Output:RSN1,RTWHILE (sensor is lived)Do m←1;j←0 IF(i==0) RSN1←RSN1∪x0{} RT←RT∪t0{} ELSE FOR (j←j+m To n←len(Temp_Data))Do m←1?len(Temp_Data)2」{,?len(Temp_Data)2」=0,?len(Temp_Data)2」≠0 δi,j←xi-xj|; IF(δi,j≤Th AND t≤T_max) Temp_Data←Temp_Data∪{xi} END IF IF(δi,j>Th AND t>T_max) RSN1←RSN1∪{xi} RT←RT∪{ti} Temp_Data←Null END IF END FOR END ELSE i←i+1; Return RSN1, RTEND WHILE

去冗余算法的具體步驟如下:

Step1：獲取傳感器的感知數(shù)據(jù)，對冗余數(shù)據(jù)進行初步處理.

如圖2中節(jié)點SN1傳感器在時間集合T={t0,t1,t2,t3,…,tn}不同時間對應(yīng)的感知數(shù)據(jù)為集合DSN1={x0,x1,x2,x3,x4,…,xn}，將首次感知的數(shù)據(jù)作為非冗余數(shù)據(jù)保存?zhèn)鬏擱SN1={x0},RT={t0}.

Step2：計算當(dāng)前采集的感知數(shù)據(jù)與冗余數(shù)據(jù)集的數(shù)據(jù)相似距離矩陣S為:

S為對稱矩陣，且對角線的元素為0.

ti與tj時刻的感知數(shù)據(jù)xi與xj的相似距離δi,j=|xi-xj|,0

Step3：設(shè)置相似距離閾值Th和最大時間閾值T_max，將數(shù)據(jù)相似距離δi,j和最大時間差t分別與Th和T_max的比較作為冗余條件；同時在去冗余的過程中，引入自適應(yīng)步長m降低計算復(fù)雜性.

自適應(yīng)步長m為：

其中，len(Temp_Data)為暫存冗余數(shù)據(jù)集的長度，即連續(xù)冗余數(shù)據(jù)量；每個冗余周期內(nèi)的步長自適應(yīng)更新，動態(tài)地改變δi,j=|xi-xj|中xi與xj兩個數(shù)據(jù)的j=i,i=i+m索引位置.

每個周期內(nèi)連續(xù)冗余感知數(shù)據(jù)的最遠時間差t=ti-t0，其中ti表示第i次感知時間，t0表示每個周期內(nèi)首個感知數(shù)據(jù)的時間.

冗余數(shù)據(jù)判斷方法為,如果δij≤Th且t≤T_max，標(biāo)記為冗余感知數(shù)據(jù)，進行去冗余操作;如果δi,j>Th且t>T_max，將ti時刻感知的數(shù)據(jù)，視為非冗余感知數(shù)據(jù)，進行保存?zhèn)鬏擱SN1=RSN1∪{xi},RT=RT∪{ti}.

Step4：輸出時間相關(guān)性去冗余后感知數(shù)據(jù)，作為最終處理結(jié)果傳輸給CH1.

1.3 算法性能分析

假定一個冗余周期判別中的冗余數(shù)據(jù)量為n，TCDA算法的時間復(fù)雜度分析如下：第1步，獲取感知數(shù)據(jù)的時間復(fù)雜度為O(n)，輸出首次感知的非冗余數(shù)據(jù)的時間復(fù)雜度為O(1)；第2步，計算冗余數(shù)據(jù)相似距離矩陣的時間復(fù)雜度為O(n(n-1)/2)；第3步，在計算數(shù)據(jù)相似距離矩陣中加入自適應(yīng)步長來調(diào)整比較步長后的時間復(fù)雜度為O(n2/m)；第4步，返回非冗余數(shù)據(jù)的時間復(fù)雜度為O(1).TCDA算法在第3步對非冗余數(shù)據(jù)進行了臨時存儲，空間復(fù)雜度為O(len(RSNi)).因此，TCDA算法的時間復(fù)雜度為O(n2/m)；空間復(fù)雜度為O(len(RSNi))，消息復(fù)雜度為O(len(RSNi)).

1.4 能耗分析

針對節(jié)點感知數(shù)據(jù)在時間相關(guān)性方面進行分析，僅討論冗余數(shù)據(jù)與能耗的關(guān)系和算法性能對計算能耗的影響.

去冗余前的總能耗Et_f=Eut×Num_all，其中Eut是發(fā)送一單位數(shù)據(jù)的能耗，Num_all為去冗余前的總數(shù)據(jù)量：

去冗余后的總能耗Eall_b=Et_b+Ec，其中Et_b為去冗余后的傳輸能耗：

Et_b=Eut×(Num_all-Num_exist)，

其中Num_exist是去冗余后的數(shù)據(jù)量：

求解數(shù)據(jù)相似距離的計算能耗Ec=Eac×Com_num，其中Com_num為數(shù)據(jù)計算量.

2 仿真實驗

2.1 實驗環(huán)境

實驗借助Anaconda中的函數(shù)工具包和Intel Berkeley研究室[16]測得的溫度數(shù)據(jù)，由Python3.6平臺實現(xiàn).實驗的主要參數(shù)設(shè)置如表2所示.

表2 仿真實驗的參數(shù)設(shè)置

為了驗證TCDA算法的有效性，實驗中以數(shù)據(jù)丟失量Dnum、去冗余率r、傳輸能耗Et和計算能耗Ec作為評價指標(biāo)，并與DaT算法[9]進行對比分析.

數(shù)據(jù)丟失量Dnum=(ti-ti-1)/0.5，其中ti表示第i個數(shù)據(jù)感知時間，ti-1表示第i-1個數(shù)據(jù)感知時間，0.5表示采集時間間隔(單位：min).

實驗場景共有54個傳感器，每個傳感器0.5min采集一次數(shù)據(jù)，數(shù)據(jù)量包含一個月的感知數(shù)據(jù)，數(shù)據(jù)量達2×106條.實驗對節(jié)點1的前3000條數(shù)據(jù)進行分析，如圖3所示.

圖3 節(jié)點1的原始數(shù)據(jù)

圖3中x軸表示時間，y軸表示溫度.隨著時間的增加，溫度緩慢下降，在380min溫度達到17.5℃；隨著時間繼續(xù)增加，溫度得以回升，在750min達到最高24.9℃；隨后，溫度呈現(xiàn)出先快后慢的下降趨勢，在1830min降到最低17.3℃；在2220min時達到21.6℃，又開始下滑.在溫度變化的整個過程中，用戶最關(guān)注的是380、750、1830和2220min感知的峰值數(shù)據(jù).因此，在數(shù)據(jù)去冗余過程中，需要著重分析這4個特殊位置的數(shù)據(jù)去冗余情況.

2.2 感知數(shù)據(jù)丟失情況分析

在數(shù)據(jù)傳輸過程中，存在大量數(shù)據(jù)丟失，若忽略該問題，去冗余過程中，面對感知數(shù)據(jù)變化平穩(wěn)的情況，數(shù)據(jù)相似閾值Th控制失效，將會導(dǎo)致冗余范圍更大，使得去冗余結(jié)果誤差更大，進而影響Sink節(jié)點對數(shù)據(jù)的決策.因此，為解決以上問題，對感知數(shù)據(jù)的丟失情況做進一步的分析，如圖4所示.

圖4 數(shù)據(jù)丟失情況

從圖4可以看出，數(shù)據(jù)丟失在數(shù)據(jù)采集過程中普遍存在，若不改進算法，會導(dǎo)致更多的數(shù)據(jù)被去除，Sink節(jié)點無法及時獲取感知數(shù)據(jù)，將影響Sink節(jié)點對感知數(shù)據(jù)的最終決策.因此，通過加入最大時間閾值T_max解決相似距離閾值失效的問題.

2.3 算法的性能

以下從5個方面對算法的有效性與可行性進行分析：(1)最大時間控制T_max對去冗余率r的影響；(2)T_max=100，數(shù)據(jù)相似閾值Th對r的影響；(3)T_max=100，Th={0,0.25,0.5,1}對數(shù)據(jù)時效性的影響；(4)T_max=100，Th=0.5對傳輸能耗Et的影響；(5)T_max=100，Th=0.5對計算能耗Ec的影響.

最大時間閾值T_max對數(shù)據(jù)去冗余率r的影響如圖5所示.

圖5 T_max與r的關(guān)系

從圖5可知，在T_max=0的時，T_max對算法不起作用，此時去冗余率r為0.96；隨著T_max增加到10時，r急劇減小到0.84，表明T_max在0～10的范圍內(nèi)對去冗余率產(chǎn)生抑制作用；隨后從10～100開始對去冗余率產(chǎn)生促進作用，然后在T_max=100之后，開始逐漸穩(wěn)定，去冗余率維持在0.96左右，由此可以得出，在不影響去冗余率同時又可以解決數(shù)據(jù)時效性問題的情況下，最大時間閾值T_max=100可獲得較優(yōu)的性能.

當(dāng)T_max=100時，隨著Th的變化，去冗余率r的變化情況如圖6所示.

圖6 Th與r的關(guān)系

從圖6可知，當(dāng)Th=0時，對冗余控制不產(chǎn)生影響；隨著閾值Th的增大，去冗余率的變化幅度由急劇轉(zhuǎn)為緩慢再到保持平穩(wěn).當(dāng)Th=0.1時，去冗余率受Th的影響很大，在0.1～0.2的范圍內(nèi)，開始變得緩慢，在0.2～0.5的范圍內(nèi)，變化更為緩慢，最后趨于平穩(wěn)，說明Th越大對去冗余率的影響越小.因此，選擇Th=0.5，對冗余數(shù)據(jù)的合理性與有效性進行分析.

當(dāng)T_max=100，Th={0,0.25,0.5,1}時，對去冗余前后的數(shù)據(jù)時效性進行分析，如圖7所示.圖7中局部位置展示依次為圖8(a)、(b)、(c)、(d)所示.

圖7 加入T_max的結(jié)果對比

圖8 圖7局部數(shù)據(jù)放大圖

引入時間間隔的T_max=100后，4個特殊位置的數(shù)據(jù)去冗余后的結(jié)果分析，如表3所示.

表3 去冗余情況

在數(shù)據(jù)相似距離閾值Th分別為1、0.5、0.25時，非冗余數(shù)據(jù)分別為59、74、116；圖8中，380、750、1830和2220 min的位置，數(shù)據(jù)誤差平均值大約為0.1，說明可以在保證去冗余率的情況下，降低重要位置數(shù)據(jù)的誤差.在誤差值均為0.1的情況下，Th=0.5時，傳輸數(shù)據(jù)量僅為74，減少了96%的數(shù)據(jù)量，同時又可以用盡量少的重要特征數(shù)據(jù)代表原始數(shù)據(jù).然而，在數(shù)據(jù)波動比較細微的情況下，去冗余后的數(shù)據(jù)無法精細地展現(xiàn)出來，因此，如何在保證數(shù)據(jù)去冗余率的情況下，更加精細地描述數(shù)據(jù)的變化，有待進一步深入探索.

當(dāng)T_max=100，Th=0.5時，TCDA與DaT算法的傳輸能耗與計算能耗如圖9與圖10所示.

圖9 傳輸能耗提升率

圖10 計算能耗使用率

圖9顯示，TCDA算法與DaT算法的傳輸能耗，隨著節(jié)點規(guī)模的增大存在輕微的波動，在節(jié)點規(guī)模為0～10的范圍內(nèi)，兩種算法的傳輸能耗提升率均大致表現(xiàn)為先升高再降低的趨勢，最高分別達到97%與94.5%.隨后兩種算法的傳輸能耗均趨于平穩(wěn)的狀態(tài)，分別穩(wěn)定在96%與93%.TCDA算法比DaT算法節(jié)省了3%的傳輸能耗.

如圖10所示，TCDA算法與DaT算法的計算能耗隨著節(jié)點規(guī)模的增大而增大.然而，DaT的計算能耗增加的幅度是TCDA的2～3倍.TCDA算法同DaT算法相比，節(jié)省了50%～60%的計算能耗.

上述實驗結(jié)果表明，TCDA算法在傳輸能耗與計算能耗方面明顯比DaT算法更具有優(yōu)勢.同時，在數(shù)據(jù)去冗余過程中，TCDA算法還考慮了數(shù)據(jù)丟失的情況，這更符合真實情景.

3 結(jié)論

針對傳感器網(wǎng)絡(luò)感知數(shù)據(jù)去冗余問題，提出了一種基于最大時間閾值及自適應(yīng)步長的時間相關(guān)性感知數(shù)據(jù)去冗余算法(TCDA).實驗結(jié)果表明：在不同規(guī)模的網(wǎng)絡(luò)下，與DaT算法相比，TCDA降低了3%的傳輸能耗和50%的計算能耗，在確保感知數(shù)據(jù)特征的前提下，傳感器網(wǎng)絡(luò)生命周期得到顯著的提升.下一步將對局部數(shù)據(jù)的精確度作深入研究.