WSNs中基于雙層抑制數據冗余算法

趙夢龍，李 斌

(1.貴州職業技術學院 信息工程學院， 貴陽 550023； 2.福建師范大學 協和學院， 福州 350117)

隨著通信技術的快速發展，移動終端設備所產生的數據量越來越大。這些數據來自社會媒體、智能手機、多媒體和物聯網等網絡應用。而無線傳感網絡(Wireless Sensor Networks, WSNs)[2]是有效收集數據的網絡平臺。

目前，WSNs在各類領域得到廣泛應用，如環境監測、戰場勘察、農業監測。WSNs由大量的傳感節點構成，且通常WSNs部署于偏遠地區。通過傳感節點實時地感測環境數據，并周期地將感測數據傳輸至信宿，進而實現數據的收集。

在這些應用中，WSNs每天收集澤字節量級的數據[3]，但這些海量數據一定存在冗余，有些數據是相同或相似的，存在壓縮的空間。并且存儲這些海量數據對節點設備性能提出了挑戰。因此，減少數據收集量是擴展WSNs應用的關鍵技術之一。

然而，不可忽略問題：WSNs中傳感節點的能量有限，且多數節點不具有再充電能力。這些特性限制了WSNs的網絡壽命。而節點的能量消耗與傳輸的數據量密切相關[4]。這就要求減少數據傳輸量，將冗余數據消除，從而降低能耗。而數據壓縮和數據聚類成為降低數據傳輸量的關鍵技術。通過數據壓縮和數據聚類消除數據的冗余量，減少不必要的數據量，這有利于降低能耗，提高網絡壽命。

為此，針對WSNs的大數據收集問題，采用雙層抑制數據冗余算法(Two-level-based suppressing data redundancy algorithm,TSDR)。第一層，傳感節點采用數據壓縮模型，壓縮所收集的數據，然后再傳輸至融合節點，便進入第二層。在第二層，融合節點就采用K均值算法，允許每個融合節點消除數據冗余。通過這兩層控制數據冗余，減少總體的數據傳輸量。仿真結果表明，提出的TSDR算法能夠有效地壓縮數據，減少數據冗余量。

1 TSDR算法

1.1 網絡模型

考慮如圖1所示的網絡模型。引用簇類算法，將傳感節點劃分為傳感節點和融合節點。融合節點類似于簇首。傳感節點將已壓縮的數據傳輸至融合節點，然后，融合節點再引用數據聚類算法將數據進行聚類，減少鄰居節點間數據的冗余。最終，由融合節點將數據傳輸到信宿。

圖1 網絡模型

1.2 數據壓縮

在傳感網絡中，若傳感節點實時地將感測數據傳輸至信宿，這增加傳感節點了的能耗。因此，TSDR算法引用周期地數據收集模式[5]。即每個傳感節點周期地向信宿傳輸數據，在每個周期內，傳感節點感測數據，當周期結束后，傳感節點就將數據傳輸至信宿。

假定傳感節點si收集τ個時隙的數據。每個周期由τ個時隙構成。傳感節點si將每個周期所收集的數據構成一個數據矢量Ri=[r1,r2,…,rτ]。圖2顯示了τ=5的周期數據收集模型。

通常，數據矢量R可能存在一定的冗余量。例如，當環境變化緩慢或時隙間隔短時[6]，相鄰時隙間所收集的數據可能沒有區別，甚至相同。因此，從數據價值的角度，數據矢量R存在壓縮的空間。為此，TSDR算法引用皮爾森相關(Pearson Correlation)[7-8]算法壓縮數據。

圖2 周期地收集數據模型

兩個數據集間的皮爾森系數ρ反映了這兩個數據集的相關性。若ρ=1，表示這兩個數據集正相關；若ρ=0，表示這兩個數據集不相關。假定傳感節點si、sj的所感測的數據集分別表示為Ri、Rj。它們間的皮爾森系數ρ(Ri,Rj)定義如式(1)所示：

(1)

其中n表示周期內的時隙數，且ri∈Ri，rj∈Rj。

用tp表示皮爾森系數閾值。如果ρ(Ri,Rj)小于tp，則表明Ri、Rj密切相關。

每個傳感節點執行算法1，將原始的數據集Ri進行壓縮，構成數據集VR。TSDR算法引用二分法(DIVIDE)將數據集Ri劃分為兩個子集，即DIVIDE(Ri)→{Ri1,Ri2}。

1.3 數據聚類算法

數據壓縮是解決單個傳感節點所感測數據的冗余問題。而數據聚類算法就是解決傳感節點與傳感節點間的數據冗余問題[10]。由融合節點執行數據聚類算法，即將相鄰區域傳感節點所感測的數據進行聚類，最終，將這些數據傳輸至信宿。

1.3.1K均值算法

K均值的主要思想就是建立K個重心，每個重心表示一個簇。最初，隨機選擇K個點。然后，這些傳感節點所感測的數據集盡量逼近這些點。當有新的簇加入后，再重新計算K個重心。一旦有新的重心[11]，就安排新的數據集靠近這個重心。如此循環，直到沒有新的簇加入。

然而，K均值算法高度依賴于隨機的初始的K個重心。為此，在K均值算法引用歐式距離。將數據集安排于離簇重心最近位置是K均值算法的基本過程。因此，用歐式距離計算兩個數據集間的距離。

對于兩個數據集Ri、Rj，它們間的歐式距離Ed:

(2)

其中ri∈Ri、rj∈Rj。

1.3.2基于歐式距離的K均值

融合節點在每個周期結束后，接收感測數據。隨后，進入簇聚類階段，如算法2所示。首先，隨機選擇K個數據集作為簇的中心，如算法的4-6步所示。在每次迭代時，融合節點依據歐式距離，將離簇中心最近的集進行聚類，如算法2的8-10步所示。隨后，再計算每個簇的簇心，直到每個簇成員不再變化，如算法2的11-13步所示。算法2如下：

2 性能仿真

2.1 仿真環境

引用自定義的Java仿真器建立測試平臺，并采用中國農業大學農林溫室數據分析TSDR算法的性能。實驗室部署了54個Mica2Dot傳感節點，實時地感測環境的溫度數據。共計收集了約2.3百萬數據。假定融合節點位于實驗室中心，所有傳感節點將感測數據傳輸至融合中心。

為了更好地分析TSDR算法性能，選擇文獻[12]的數據壓縮算法S-LEC和文獻[13]提出的數據降冗余算法PFF進行比較，并分析它們的性能。仿真參數值如表1所示。每次仿真獨立重復50次，取平均值作為最終的實驗數據。

表1 仿真參數值

2.2 數據分析

2.2.1數據壓縮率

首先分析TSDR算法的數據壓縮率。壓縮率越低，說明數據冗余率越低，性能越好。TSDR和S-LEC算法的壓縮率如圖3所示。圖3(a)、圖3(b)分別顯示了在{tp=0.5,τ=100,200,500,1 000}、{tp=0.4,0.5,0.6,0.7,τ=200}兩種情況下的數據壓縮率。

相比于S-LEC算法，TSDR算法能夠有效降低數據冗余量。原因在于：每個節點能夠在每個時隙壓縮數據，減少了數據冗余。從圖3(a)可知，TSDR算法的壓縮率遠低于S-LEC算法，比它降低了89%。而圖3(b)的數據顯示，TSDR算法的壓縮率比S-LEC算法平均降低了近75%。

此外，從圖3可知，τ值的增加，提高了數據壓縮率。原因在于：τ值越大，一個周期內感測的數據越多。

圖3 數據壓縮率

2.2.2數據聚類性能

在每個時期結束，融合節點從所有傳感節點中收集具有代表性的數據。TSDR算法利用K均值算法將感測數據進行分簇，將每個簇的中心數據作為數據集，然后將數據集傳輸至信宿。傳輸的數據集越少，數據聚類性能越好。

圖4顯示了TSDR算法和PFF算法的數據聚類性能。圖4分別顯示了3類情況：

1)tp=0.5,K=6,τ=100,200,500,1 000;

2)τ=100,K=6,tp=0.4,0.5,0.6,0.7;

3)τ=100,tp=0.5,K=4,6,8,10。

從圖4可知，提出的TSDR算法的數據聚類性能遠優于PFF算法。相比于PFF算法，TSDR算法的數據集平均降低了近85%。

圖4 融合節點向信宿發送的數據集

此外，對比于圖4(a)、圖4(b)和圖4(c)分析可知，時隙數的增加對數據集數的影響并不大，而簇數K值對TSDR算法的數據集影響較大，且隨著K值的增加而上升。

3 結論

TSDR算法分別從傳感節點和鄰近區域的兩項數據入手，壓縮數據的冗余。實驗數據證實，提出的TSDR算法極大地降低了數據冗余，減少路徑所傳輸的數據量。

目前，只分析了算法的壓縮數據的性能，并沒有分析因引入這兩個算法所帶來能耗，即算法的復雜性。后期，將分析算法的復雜性，優化算法。