节能的基于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