節能的基于EM分簇與壓縮感知的數據收集方法

聶文梅，劉宏英

（山西大同大學數學與計算機科學學院，山西 大同 037009）

節能的基于EM分簇與壓縮感知的數據收集方法

聶文梅，劉宏英

（山西大同大學數學與計算機科學學院，山西 大同 037009）

在稠密無線傳感網進行數據收集的過程中，網絡壽命的延長一直是人們重點關注的問題。為了減少能耗延長網絡壽命，從考慮網絡數據傳輸距離和數據傳輸量兩個角度，提出一種基于EM分簇與壓縮感知相結合的數據收集方法。本文在分簇之前從能耗角度對最優簇數進行了分析。仿真實驗表明該方法能極大地減少數據收集能耗，從而延長無線傳感網絡壽命。

無線傳感網；數據收集；壓縮感知；分簇；能量有效；EM算法

0 引言

近年來無線傳感網在軍事、民用和商業上得到了廣泛應用。無線傳感網中的一個重要操作是數據收集，即從傳感器節點收集感知數據并將其傳輸給匯聚節點。各種應用都依賴于有效的數據收集，例如戰場監測、生活習性監測和環境監測等等。

無線傳感網數據收集的一個重要挑戰是延長網絡壽命。首先，作為傳感器節點的微電子設備的能源是有限的，而且在許多應用中不便充電；其次，多對一的無線傳輸方式使得數據收集產生熱點問題，即越接近匯聚節點的傳感器節點能量消耗越快。

為了延長網絡壽命，在數據收集過程中，采用高效節能的算法成為必需的。設計高效節能的算法需要考慮兩大主要問題，一個是數據傳輸距離；另一個是數據傳輸量。針對這兩大問題，本文將分簇和壓縮感知相結合，提出了基于EM分簇與壓縮感知相結合的數據收集方法。EM分簇算法可以使數據傳輸距離平方和最小化[1]，壓縮感知可以有效減少數據傳輸量，從而達到節能的目的。

1 相關工作

1.1 相關研究分析

在稠密無線傳感網中，傳感器節點的感知數據通常采取多跳的方式發送給匯聚節點，由于傳感器

LEACH[2]是無線傳感網中最著名的分簇算法，每個傳感器節點執行該算法，交換剩余能量信息，有較高剩余能量的節點將更可能成為下一個簇頭，通過周期性的重新分簇，每個節點消耗的能量接近于平均。然而LEACH是基于每個節點都能與其他節點相互通信的假設，因此，部署在大范圍的WSNs是不適合使用該算法的。KOCA[3]和k-CONID[4]都是分布式分簇的典型算法，KOCA重點關注重疊分簇，K-CONID節點互相交換它們的隨機ID，有最小ID的節點被選為簇頭。然而在WSNS中對分布式分簇算法最小化數據傳輸很難。為了實現最小能量的分簇，需采用集中分簇算法。PEGASIS[5]和KAT mobility[6]是常用的集中分簇算法，PEGASIS基于位置構建鏈簇，并且重復選擇簇頭，它考慮了通信范圍的限制，實現了能量消耗均勻化，然而仍然不能實現能耗最小化。K-CONID通過采用K-MEANS算法進行分簇，這樣的分簇結果接近整體最優，然而該算法沒有考慮通信范圍限制，因此sink可能不能從所有傳感器節點收集信息。為了實現最小化數據傳輸和從所有節點收集數據我們需要采用同時考慮節點位置和通信范圍的集中式算法。EM算法就是一種既考慮了節點位置又考慮了通信范圍的分簇算法。文獻[1]中使用EM分簇算法對稠密無線傳感網進行了數據收集，但收集過程只考慮了縮短傳輸距離，但沒有考慮傳輸量。文獻[7]提出了一個新穎的使用壓縮感知進行數據收集的算法方案，該方案只需要少數壓縮測量值，極大的減少了能量消耗。

傳統的數據收集[8-13]模式都假設基站靜止不動，節點通過多跳的方式向基站傳輸數據，這樣基站周圍的節點由于負載大而成為網絡性能的瓶頸，這些節點將會快速死亡，從而縮短網絡壽命。采用移動匯聚節點（Mobile Sink，以下簡稱MS）收集數據可以均衡網絡能量消耗，剔除網絡熱點問題。同時為減少延遲可以利用TSP算法[14]。

1.2 EM分簇算法

EM算法是一種典型的迭代分簇算法，其假設節點遵循高斯混合分布。

k指簇數，kπ表示第k簇的混合系數。定義如下：

X是所有節點的位置向量，μk和∑k是簇參數，分別代表第k簇的中心向量和第k簇的協方差矩陣。

EM算法計算每個節點的依賴度值，第n個節點對第k簇的依賴度計算公式如下：

EM算法利用如下公式計算極大似然估計：

EM算法重復迭代，直到極大似然值收斂。

1.3 壓縮感知

假設X=[x1,x2,…,xn]，T為稀疏或可壓縮信號，其中x∈RN,N∈R.Ψ=［Ψ1,Ψ2,…,ΨN］是信號X的系數表示基，如果X本身為稀疏信號，則Ψ可以看作是單位矩陣。根據表示基Ψ，X可以轉換為K稀疏信號S如下：

2006年，Donoho等人提出對于稀疏信號或可壓縮信號而言，只要獲取其少量的線性組合值就足夠對壓縮信號進行精確恢復。

信號壓縮如下：y=φX=φΨS

其中φ為M*N的矩陣而且M＜＜N，稱之為測量矩陣，y為壓縮后的信號，稱為測量值向量（M*1維）Ψ為N*N的表示基。

2 EM分簇與壓縮感知結合的數據收集方法

2.1 能量模型

WSN中能量的消耗與傳輸距離d有極大的關系，當距離d的值小于閾值時，我們可以用自由空間模型來計算能量消耗，否則用多信道衰減模型。節點傳送或接收L比特的數據所需能量公式如下：

其中ET（L,d）指傳感器節點向距離為d的節點傳送L比特的數據所需要消耗的能量，ER（L）指節點接收L比特數據的能耗。

Etotal為總的能量消耗，它主要包括簇內能耗Eintra和簇間能耗Einter。

2.2 最優簇數分析

假設N個傳感器隨機均勻分布在方形的感知區域，每個簇形成半徑為R的圓，簇的個數為k，每個簇內節點個數相同，則每個簇內節點個數為N/k。

隨機稀疏測量矩陣的稀疏度為s，每個簇內有m個傳感器節點在發送數據，其余節點處于休眠狀態，E(m)sN/k=。

簇內通信能耗主要包括簇內傳感器節點將數據發送到簇頭的能耗和簇頭接收數據的能耗。以理想狀態分析單次數據收集簇內的平均能耗Eintra為：

其中m=s.N/k為單次數據收集簇內發送數據的節點數目。id為節點i到簇頭的距離。

為解決WSN中的網絡熱區問題，本文使用了移動Sink來從各個簇頭收集數據，因此總的主要能耗即為簇內能耗：

其中M表示每一個簇中所收集的單個測量值得個數，由CS來決定。

最佳簇數可以由以下公式定義：

2.3 算法步驟

我們的目的是提出一種基于EM分簇和CS相結合的最小能量消耗的數據收集算法，該方法適用于密集分布的WSN。下面Algorithm 1是我們提出的EM首輪分簇算法。

EM Algorithm

Initialize s

Calculate optk

Initialize cluster centroids μ

Calculate clusters’ parameters π and ∑

Calculate nkγand P

While new

|PP-＜∈do

For nk∈

Calculate nth node’s responsibility value nkγ.

Calculate number of nodes belong to cluster, Nk

Update the clusters’ parameters π, μ and ∑

Endfor

Evaluate the log likelihood new

P.

Endwhile

Return cluster centroids, μ, ∑ and Nk

簇內單個測量值的收集算法的整體過程為：首先，根據能量公式和具體場景移動sink計算最優簇數optk；其次，根據上面的算法Algorithm1 EM對傳感器節點進行分簇；然后，在每個簇內使用CS進行數據的收集；最后移動sink用最短路徑移動算法對簇頭的數據進行收集。

3 仿真分析

通過使用C++編程語言并結合MATLAB對EM分簇算法進行了仿真。考慮場景為N=100個節點隨機分布在100 m×100 m的區域的無線傳感網。該區域中的節點分布如圖1所示。不失一般性，假設基站在傳感區域的中心。首先，將EM分簇與其它的分簇算法如KMeans分簇相比較。如圖2所示，顯然可以看出，EM算法的穩定時間要比KMeans算法的穩定時間明顯延后很多，而且EM算法的死亡點數的增長要更緩慢些。

之后我們又在使用EM算法分簇后的簇內節點進行數據傳輸時采用壓縮感知CS后的情況進行了實驗分析。從圖3可以看出，采用CS 后可以使簇內節點的能耗均勻分布，很大程度的避免了個別節點的提前死亡。

4 總結

本文提出的EM分簇與CS相結合的算法適用于密集型大規模網絡。EM分簇算法采用最小化數據傳輸距離平方和的方法使簇內節點數據傳輸時達到能耗最小。采用CS后可以使簇內節點的能耗均勻分布，很大程度的避免了個別節點的提前死亡。仿真實驗表明EM分簇與CS相結合的算法性能良好，可以很大程度的延長網絡壽命。

圖1 (左)100個點的隨機網絡；(右)采用EM算法分簇的動態分簇結構Fig.1 (left) the network with 100 random nodes; (right) the structure of cluster by EM algorithm

圖2 EM分簇與KMeans分簇的死亡點數Fig.2 the death nodes number of EM cluster and KMeans cluster

圖3 EM分簇與EM和CS相結合的死亡點數Fig.3 the death nodes number of EM cluster and the scheme based EM and CS

[1] Takaishi D, Nishiyama H, Kato N, et al. Toward Energy Efficient Big Data Gathering in Densely Distributed Sensor Networks[J]. IEEE Transactions on Emerging Topics in Computing, 2014, 2(3): 388-397.

[2] W Heinzelman, A Chandrakasan H Balakrishnan. Energyefficient communication protocol for wireless microsensor networks[J]. Proc. 33rd Annu. Hawaii Int. Conf. Syst. Sci., Jan. 2000, vol. 2.

[3] M Youssef, A Youssef M Younis. Overlapping multihop clustering for wireless sensor networks[J]. IEEE Trans. Parallel Distrib. Syst. , vol. 20, no. 12: 1844-1856, Dec. 2009.

[4] T Khac C Hyunseung. Connectivity-based clustering scheme for mobile and hoc networks[J]. IEEE Int. Conf. RIVF, Jul. 2008: 191-197.

[5] S Lindsey C Raghavendra. PEGASIS: Power-efficient gathering in sensor information systems[J]. IEEE Aerosp. Conf. , Mar. 2002: 1125-1130.

[6] H Nakayama, N Ansari, A Jamalipour, N Kato. Fault- resilient sensing in wireless sensor networks[J]. Comput. Commun., vol. 30, nos. 11-12: 2375-2384, Sep. 2007.

[7] Xiao-Yang Liu, Yanmin Zhu, et al. Compressive Data Collection for Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 8: 2188-2197, August 2015.

[8] 夏季文, 馬福昌, 喬學工. 節能的無線傳感器網絡分簇路由算法的研究[J]. 新型工業化, 2011, 1(8): 56-63.

[9] 杜彥敏. 無線傳感器網絡(WSN)安全綜述[J]. 軟件, 2015, 36(3): 127-131.

[10] 聶文梅, 劉宏英, 張葉娥等. 基于大數據的醫療信息平臺建設研究[J]. 山西大同大學學報, 2016, 32(2): 8-12.

[11] 杜淑穎. 基于大型數據集的聚類算法研究[J]. 軟件, 2016, 37(01): 132-135.

[12] 呂占偉, 陶崢. 重傳下的無線傳感器網絡的生命周期分析[J]. 軟件, 2015, 36(1): 116-121.

[13] 夏娜, 馮如吉, 蔣建國. WSNs 中基于SPSA的數據包長優化算法[J]. 新型工業化, 2011, 1(3): 1-14.

[14] L Zhu, Z Pan, Y Liu, A Zhan. Analysis of cluster wireless sensor network based on energy harvesting[J]. International Conference on Wireless Communications, 2014: 468-472.

Energy-efficient Data Gathering Scheme Based on EM Clustering and Compressed Sensing

NIE Wen-mei, LIU Hong-ying
(School of Mathematics and Computer Science, Shanxi Datong University, Datong 037009, China)

In the process of data collection in dense wireless sensor network, extending the network lifetime is the focused problem. In order to reduce energy consumption and prolong the network lifetime, a data collection scheme based on EM clustering and compressed sensing is put forward. This scheme considers the network data transmission distance and data transmission quantity. Before clustering, the optimal number of clusters is analyzed considering the energy consumption. Experimental results show that the scheme can greatly reduce the energy consumption of data collection and extend the lifetime of the wireless sensor network.

Wireless sensor networks; Data gathering; Compressed sensing; Clustering; EM algorithm

TP301.6

A

10.3969/j.issn.1003-6970.2017.05.008

山西大同大學博士科研啟動基金(2015-B-05)；山西大同大學科研項目(2014K4)

聶文梅(1975-)，女，講師，主要研究方向：大數據和無線傳感器網絡。劉宏英(1977-)，女，講師，主要研究方向：大數據和無線傳感器網絡。節點數目眾多，如采用傳統的樹形路由策略會造成大量無需參與計算的節點參與測量值的收集。在數據收集過程中，如果參與單個測量值的節點數目過多將產生以下問題：（1）單個測量傳輸代價太大，導致整個網絡性能提高有限；（2）參與單個測量值收集的節點越多測量值越容易出錯。采用分簇路由不能減少數據收集過程中的采樣數目，但可以減少單個測量值收集過程中參與的節點數目。分簇路由數據收集主要的兩個挑戰：（1）簇內簇頭如何分布，簇內傳輸代價最優；（2）網絡分成幾個簇，數據收集代價最優。

本文著錄格式：聶文梅，劉宏英. 節能的基于EM分簇與壓縮感知的數據收集方法[J]. 軟件，2017，38（5）：39-42