聶文梅，劉宏英

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西 大同 037009）

節(jié)能的基于EM分簇與壓縮感知的數(shù)據(jù)收集方法

聶文梅，劉宏英

（山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西 大同 037009）

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

無線傳感網(wǎng)；數(shù)據(jù)收集；壓縮感知；分簇；能量有效；EM算法

0 引言

近年來無線傳感網(wǎng)在軍事、民用和商業(yè)上得到了廣泛應(yīng)用。無線傳感網(wǎng)中的一個重要操作是數(shù)據(jù)收集，即從傳感器節(jié)點收集感知數(shù)據(jù)并將其傳輸給匯聚節(jié)點。各種應(yīng)用都依賴于有效的數(shù)據(jù)收集，例如戰(zhàn)場監(jiān)測、生活習(xí)性監(jiān)測和環(huán)境監(jiān)測等等。

無線傳感網(wǎng)數(shù)據(jù)收集的一個重要挑戰(zhàn)是延長網(wǎng)絡(luò)壽命。首先，作為傳感器節(jié)點的微電子設(shè)備的能源是有限的，而且在許多應(yīng)用中不便充電；其次，多對一的無線傳輸方式使得數(shù)據(jù)收集產(chǎn)生熱點問題，即越接近匯聚節(jié)點的傳感器節(jié)點能量消耗越快。

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

1 相關(guān)工作

1.1 相關(guān)研究分析

在稠密無線傳感網(wǎng)中，傳感器節(jié)點的感知數(shù)據(jù)通常采取多跳的方式發(fā)送給匯聚節(jié)點，由于傳感器

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

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

1.2 EM分簇算法

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

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

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

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

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

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

1.3 壓縮感知

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

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

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

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

2 EM分簇與壓縮感知結(jié)合的數(shù)據(jù)收集方法

2.1 能量模型

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

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

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

2.2 最優(yōu)簇數(shù)分析

假設(shè)N個傳感器隨機均勻分布在方形的感知區(qū)域，每個簇形成半徑為R的圓，簇的個數(shù)為k，每個簇內(nèi)節(jié)點個數(shù)相同，則每個簇內(nèi)節(jié)點個數(shù)為N/k。

隨機稀疏測量矩陣的稀疏度為s，每個簇內(nèi)有m個傳感器節(jié)點在發(fā)送數(shù)據(jù)，其余節(jié)點處于休眠狀態(tài)，E(m)sN/k=。

簇內(nèi)通信能耗主要包括簇內(nèi)傳感器節(jié)點將數(shù)據(jù)發(fā)送到簇頭的能耗和簇頭接收數(shù)據(jù)的能耗。以理想狀態(tài)分析單次數(shù)據(jù)收集簇內(nèi)的平均能耗Eintra為：

其中m=s.N/k為單次數(shù)據(jù)收集簇內(nèi)發(fā)送數(shù)據(jù)的節(jié)點數(shù)目。id為節(jié)點i到簇頭的距離。

為解決WSN中的網(wǎng)絡(luò)熱區(qū)問題，本文使用了移動Sink來從各個簇頭收集數(shù)據(jù)，因此總的主要能耗即為簇內(nèi)能耗：

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

最佳簇數(shù)可以由以下公式定義：

2.3 算法步驟

我們的目的是提出一種基于EM分簇和CS相結(jié)合的最小能量消耗的數(shù)據(jù)收集算法，該方法適用于密集分布的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

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

3 仿真分析

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

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

4 總結(jié)

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

圖1 (左)100個點的隨機網(wǎng)絡(luò)；(右)采用EM算法分簇的動態(tài)分簇結(jié)構(gòu)Fig.1 (left) the network with 100 random nodes; (right) the structure of cluster by EM algorithm

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

圖3 EM分簇與EM和CS相結(jié)合的死亡點數(shù)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] 夏季文, 馬福昌, 喬學(xué)工. 節(jié)能的無線傳感器網(wǎng)絡(luò)分簇路由算法的研究[J]. 新型工業(yè)化, 2011, 1(8): 56-63.

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

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

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

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

[13] 夏娜, 馮如吉, 蔣建國. WSNs 中基于SPSA的數(shù)據(jù)包長優(yōu)化算法[J]. 新型工業(yè)化, 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

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

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

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