乔建华，张雪英

(1.太原理工大学信息工程学院，太原030024; 2.太原科技大学电子信息工程学院，太原030024)(*通信作者电子邮箱tyzhangxy@163.com)

0 引言

无线传感器网络(Wireless Sensor Network，WSN)的首要制约因素就是能源问题，如何降低能耗是WSN需要重点考虑的问题。WSN中大部分能量消耗在通信部分，在发送和接收状态下能耗最大。将压缩感知(Compressed Sensing，CS)理论应用在WSN的数据收集中，可以大大减少传送数据量，从而降低能耗，延长网络寿命。

Bajwa等［1］最早将CS理论应用于无线传感器网络的数据采集。文献［2］阐述了基于CS的WSN数据采集的实现过程，指出CS具有普适的采样和分散的编码的特征，并给出了从网络节点到融合中心通过无线方式传送随机投影值的两种方法:直传式和路由中转式。

文献［3］首次提出大规模 WSN的压缩数据收集(Compressive Data Gathering，CDG)方案，不再采用文献［2］的每个节点各自传送的方式，而是由汇聚节点(Sink)得到所有读数的加权和。CDG的示意图如图1所示。

图1 多跳路由的压缩数据收集示意图Fig.1 Schematic diagram of compressive data gathering in a multi-hop routing

CDG基于CS理论，对M×N 维测量矩阵的每一行系数在N个传感器节点上进行投影，每个节点有M个投影系数{ Φi，j}Mi=1，然后与本地采集的数据进行加权传输。例如传感器节点s1将它的采集数据d1和投影系数1的乘积v1传送给下一个节点s2，s2将它的d2和投影系数2的乘积v2再加上v1传给下一个节点s3，沿路由不断进行下去，最后Sink得到一个加权和测量值。每个节点经过M次传送后，Sink就能得到M个测量值。然后利用重构算法得到原始信号。基于CS的压缩数据收集将Sink所需的N个采样值转化为收集M(M N)个本地采样值的加权和。减少了传输的数据量，降低了能耗，延长了网络寿命。因此，该收集方案成为多跳路由收集的基本方案。

如果测量矩阵是稀疏随机投影矩阵，则每行系数会出现若干0，与节点采样值的乘积也为0，这时无需进行传输，因此对于稀疏测量矩阵，只需要传送非0系数对应的节点的加权结果。所以，随机投影传输的数据量更少，从而更加延长了网络寿命。Haupt等［4］最早就指出一个相对较小的信号的随机投影数可以包含其大部分显著的信息;因此，如果一个信号在某些正交基上是可压缩的，则可以非常精确地从随机投影得到重建，因而，稀疏随机矩阵成为CS在WSN中应用的首选矩阵。文献［5］利用稀疏随机矩阵降低通信成本来恢复在信道衰落下由WSN观测的稀疏信号，但重点研究的是信号恢复所需的测量次数。文献［6］提出了一种大规模WSN的自适应稀疏随机投影算法，主要考虑随机投影的稀疏性对均方误差和系统时延的影响，以更好地实现均方误差和系统延迟之间的权衡。文献［7］利用稀疏随机测量矩阵的优点来减少能量消耗，提出基于簇的加权压缩数据采集方法，采用最小生成树投影来减少能量消耗，减少传感器节点数。但是仅针对空间相关的数据收集，也没有考虑收集器的最优位置。文献［8］综述了基于CS的WSN压缩数据收集的不同方法。这些文献都用到了稀疏随机投影矩阵，但都没有说明采集数据的具体收集过程。

文献［9－10］提出了一种采用随机投影的压缩数据收集方法，即在网络中随机选择M个节点称为投影节点以收集M个加权和。投影节点相当于簇头，测量矩阵Φ的每一行非0元素对应的节点分配给一个投影节点。每个投影节点通过最小生成树路由收集相应这一行数据的加权和，并发送给Sink，从而完成全部数据收集，形成M个测量值。该方案存在的一个主要问题就是投影节点的选择是根据M/N的概率随机选出的。由于其随机性，选出的投影节点无任何规律可言，不能保证选择出位置合适、能量较高、数量精确的理想的投影节点。但显然，投影节点在网络中的位置会影响聚合算法的效率。其次，由于测量矩阵每行的非0系数的位置也是随机的，一组远近不等的节点将加权和传送到位置不定的投影节点，这样的网络耗能势必会很不均衡。而且由非0节点到投影节点通过树结构建立路由，开销也较大，另外也没有说明在网络运行过程中出现节点死亡后的情形。

针对随机选择投影节点产生的问题，本文提出均衡投影节点的压缩数据收集方法。根据WSN节点分布是否均匀提出基于空间位置和基于节点分布密度的均衡分簇法，然后再进行压缩数据收集，并通过与随机投影节点方法的比较，验证了本文方法能够有效平衡网络能耗、延长网络寿命。

1 均衡分簇原理

1.1 压缩感知基本理论

压缩感知［11－12］理论指出［13］:对于稀疏信号或可压缩信号，可以以远低于Nyquist频率的采样频率对数据采样，然后通过非线性重建算法完美地重建信号。设N维信号x，在某N×N维的稀疏变换矩阵Ψ下可以表示为:

其中:θ是K稀疏的N×1的列向量，即θ中只有K个非零项，且K N。然后在M×N维测量矩阵(或称投影矩阵、观测矩阵)Φ下投影，得M个观测值y，且M N，即:

其中:T称为传感矩阵;y为M×1的列向量，即为测量值。

压缩感知理论指出，式(2)存在确定解的充分条件是T满足有限等距性质(Restricted Isometry Property，RIP)［14］，即存在δ∈(0，1)使得全部K稀疏信号θ均满足:

则可以通过求解以下凸优化问题得到重建信号^θ［12－13］:

式(4)可以采用基追踪或贪婪算法等方法重构原始信号^x。

1.2 均衡分簇原理

根据CS理论，设测量矩阵Φ是M×N维的矩阵，x为N×1维的列向量，则有:

其中:Xj是将N个x分成L段的各分段，每段长度设为Nj(j=1，2，…，L);每个Φj为M × Nj(j=1，2，…，L) 维矩阵。这样，每段x就可以称为一个簇，每个簇可以选择一个投影节点作为簇头。簇头收集每个簇的数据传到Sink，Sink将所有簇的数

从式(5)可以看出，对于N个节点xj(j=1，2，…，N)，可以将Φ中每行与x乘加的结果一次算出来，得M个测量值。也可以把N个节点分段来处理，假设将N个节点分成L段，每段可以是不同的点数量。测量矩阵Φ，也可以对应分成L块，每块为M行的矩阵，列数与对应x各分段的点数相等。每个分块矩阵与对应的x的每段相乘便得到M×1的列向量，然后L个列向量再进行相加，得M个测量值。用公式表示为:据对应相加，就得到了最终的测量值。用这个测量值及传感矩阵，就可以进行数据重构。若只对某些区域感兴趣，也可以只取其中某些段，由于测量矩阵具有随机性，部分随机矩阵仍满足RIP，仍可恢复信号，由于测量比增加，会得到更高的重构性能。

在每个分段选择一个投影节点，可使投影节点分布均衡;而且，依据一定条件来选择，可以选出能量较高，位置更优越的投影节点。本文根据网络节点分布是否均匀，提出了两种均衡分簇的方法。

2 基于空间位置的均衡分簇法

针对节点分布密度均匀的网络，提出基于空间位置的均衡分簇法。为了使投影节点分布均匀，将监测区域划分成大小相等的网格，在每个网格内选举性能最优的节点作为投影节点。然后投影节点收集所在簇的加权和数据，再传送到Sink。具体的实施过程如下。

1)选择第一轮的投影节点及成簇:

a)确定分簇数量及网格数。

b)以相同尺寸划分整个监测区域为所计算的网格数。

c)在每个网格选择网格中心周围位置且能量较高的节点作投影节点。

d)发送投影节点信息给每个网格的投影节点。

e)每个传感器节点依据距离最近(跳步最少)选择它相应的投影节点。

2)在一轮簇建立以后，就可以进行数据收集了，簇内数据通过传感节点经路由传送到簇内投影节点。全部簇的投影节点所收集数据经一定路由传至汇聚节点，再将其对应相加，就是全部测量值，然后通过重构就可以恢复原始数据。

3)接着就可以进行下一轮投影节点的选择和新簇的建立，其过程为:

a)簇内节点将其剩余能量值传送给投影节点。

b)投影节点选择簇中心能量较大者作为新投影节点。c)每个原来的投影节点将其信息传给新投影节点。d)每个传感节点寻找它的新投影节点，形成新簇。

2.1 簇头数目的确定

由于能量问题是WSN中路由算法需要考虑的首要问题，本文采用了简化的网络信道损耗模型［15］，如图2所示。

图2 信道损耗模型Fig.2 Channel loss model

假设有N个传感器节点随机分布在半径为R的区域内，其中簇头个数为h，则簇头节点的平均覆盖面积为πR2/h。假设簇头节点每跳的传输距离为D，每个簇头的能量消耗在三方面:接收所有簇成员的信息、融合这些数据、把融合后的信息传送给Sink节点［16］。则在一帧中簇头节点消耗的能量为:

其中:k为每个数据的信息位数;Eelect为每比特数据在发射电路或接收电路中所消耗的能量;EDA为数据融合的消耗;Efs为耗散能量，与所采用的传输信号模型有关，为自由空间传输常数;D是簇头节点发送数据的距离。

假设簇内传感器节点离簇头的距离不超过自由空间模型的临界值［16］，则一个非簇头节点的能量消耗为:

发送一帧中一个簇的能量消耗为:

在R区域每个簇发送一帧(忽略数据转发的能量消耗)的总能量消耗为:

由式(9)～(11)整理化简得:

对Etotal求导，得到最优簇头数为:

若设定监测区域大小为100 m×100 m的空间，部署有100个传感器节点，每跳的传输距离D为槡50 2 m，半径R设为方形区域的半边长50 m，则根据式(13)得h≈17。为方便计可将区域划分为16个网格。

2.2 节点的网格坐标

空间投影节点均衡划分通过网格来实现，首先考虑节点分布密度恒定的场合。一个网格选择一个投影节点，因此100 m×100 m的区域划分成4×4的16个网格，如图3所示，邻近网格内的节点都可以互相传输信息，并且呈对角线分布的两个网格在对角线的两端的节点都在通信范围内。设这些网格的边长是d，节点可以传输的最远距离是Rs，则两个节点之间互相传输信息的距离是Rs≤ 2d。

图3 节点分布密度均匀的网格划分Fig.3 Grid partition with uniform node distribution density

在划分好的网格下，首先要确定节点的网格坐标。假设Sink位于区域中心，根据节点地理位置计算其在区域内的网格坐标:

其中:Tx表示节点的网格横坐标;Ty表示节点的网格纵坐标;S(i).xd和S(i).yd分别表示节点本身的横坐标和纵坐标;Xm和Ym是监测区域的长和宽;L1是区域长度的等分数;L2是区域宽度的等分数;floor(x)表示不大于x的整数。网格坐标一样的节点视为一组。例如在图3中，根据式(14)可得每个节点所属网格的坐标，并给每个网格设置一个编号，分别对应从1到16。

2.3 簇头选举及成簇

在每个网格中，先根据每个节点的剩余能量和该节点到数据收集中心的距离来选择簇头。簇头选择节点竞争半径较大的。竞争半径公式为:

其中:b是(0，1)范围的一个随机数字，保证结果在一定范围内;dmax表示该网格内节点与Sink最远的距离;dmin表示该网格内节点与Sink最近的距离;dbs表示当前节点到Sink的距离;E0表示节点初始能量;Ed表示节点能否传输信息的临界能量;S(i).E表示节点当前所拥有的能量;D表示最大的传感半径。竞争半径考虑了节点的剩余能量以及该节点与Sink的距离两个方面，竞争半径大的节点当选簇头对这个网格内的所有节点是最有利的。

在每个网格中，将该网格中的每个节点计算出来的竞争半径进行比较，将竞争半径最大的节点选为簇头。所有网格内都选出一个簇头之后，整个网络中的除簇头以外的其他节点找到与之距离最近的簇头，向其发送要加入该簇头所创建簇的请求，簇头收到距离它较近的节点发来的加入簇请求之后，要向这些节点发送同意其加入簇的信息。等所有节点都有了归属的簇之后，就组成了无线传感器网络。

2.4 仿真研究

仿真实验中，先对WSN和传感器节点作如下的假设:

1)Sink节点位置固定在区域中央;

2)传感器节点都是静止的;

3)传感器节点不能获知其自身的位置信息;

4)簇头融合单位数据消耗的能量相同;

5)网络中单位面积的区域需要检测的数据量相同;

6)每个节点的覆盖面积相同;

7)无线信道对称。

对基于空间位置的均衡分簇法，并假设传感器节点均匀分布在监测区域。仿真参数如见表1所示。

表1 仿真相关参数Tab.1 Simulation related parameters

图4(a)是节点均匀网络基于位置方法选举的簇头和成簇效果，可以看出，通过网格划分，节点分布密度均匀的网络簇头选举也很均匀。图4(b)所示为该网络在300轮时的节点分布和成簇情况，圆点为死亡的节点。可见在网络运行过程中的成簇仍然是均衡的，每个网格选择一个投影节点。

基于位置和基于随机投影节点的两种方法的剩余节点数的比较如图5所示。

由图5可以看出:在网络开始运行阶段，基于位置分簇的效果要差一些，死亡节点出现比较早，剩余节点数较少，但不影响网络运行;当运行到剩余节点数为80%的时候，基于随机投影的死亡节点迅速增加，并很快超过了基于位置分簇的死亡节点数，剩余节点数迅速降低:在385轮时剩余节点数由20点瞬间将为0，网络瘫痪，但此轮时基于位置分簇的网络仍有近40%的节点存活，网络仍能运行。以剩余节点数为20点时作为网络正常运行的临界点来考虑，低于20点网络无法联通，基于位置分簇的网络比基于随机投影节点分簇的网络生存期延长了约35%。

图5 基于位置和随机分簇的节点均匀WSN的剩余节点数比较Fig.5 Comparison of remaining nodes of WSN with node even distribution based on location and random clustering

3 基于节点分布密度的均衡分簇法

针对节点分布不均的WSN，每个网格的节点数量多少不等，如果采用第2章的基于位置的分簇法在每个网格选择一个投影节点，节点少的网格的投影节点能量会很快耗尽，为了适应节点不均的网络，本文提出基于节点密度的均衡分簇法。

3.1 基于分布密度的均衡分簇

对于节点分布密度不均的WSN，节点数较多的网格组成一个簇之后可以较好地进行节点与节点、节点与簇头、簇头与Sink的数据传输，还可以使收集同一种信息的部分节点进入休眠，节省能量消耗。而节点数较少的网格形成一个簇之后，簇头只能在这几个节点之间轮换，加快了该网格的能量消耗，使这些区域的节点过早地死亡，造成网络耗能的不均衡。

节点分布密度的衡量通过网格来得到，网格内节点数量少的，说明密度小;反之说明密度大。因此首先进行网格内节点的调整，计算每个网格中的节点的数量。如果网格的节点的数量少于等于p，这些网格中的节点就被归到节点数量大于p的其他邻近网格。所有节点数量小于等于p的网格中的节点都归到指定网格中之后，就形成了一个新的网格划分格局。这样，就可以避免节点不均衡的能量消耗，从而提高整个网络的存活周期。接下来，就可进行簇头选举和形成簇。

3.2 仿真分析

仿真实验中，对WSN和传感器节点的假设同2.4节。对基于节点分布密度的均衡分簇法，并假设传感器节点随机非均匀分布在监测区域。为了研究比较，分别在两个场景中进行了仿真，具体参数如表2所示。对场景2，监测区域大小为200 m×200 m的空间，部署有400个传感器节点，传感器节点的通信半径D为槡50 2 m，监测区域半径R相当于为100 m，则根据式(13)得h≈68。为仿真方便可将区域划分为64个网格。

表2 仿真相关参数(场景1、场景2)Tab.2 Simulation related parameters(scene 1 and scene 2)

下面就用同样节点布置的网络来测试基于节点分布密度分簇法和文献［9］采用随机投影节点方法的性能。

场景1的基于节点分布密度均衡分簇法的成簇效果如图6所示。图6(a)是第一轮成簇的示意图，可见节点密度小的网格，其节点进行了网格的重新分配，加入到了距离邻近的簇，不再进行投影节点的选择。图6(b)是第300轮时的成簇效果，仍有约60%的节点存活，可见网络仍然运行良好。

图7(a)是文献［9］采用随机投影节点的方法，它的投影节点是随机产生的，从中可以看出，投影节点的位置很随机，形成的簇大小也不均衡。图7(b)是其300轮时的成簇效果，比图6(b)的节点数明显减少，而且边远的节点大部分死亡，只有Sink附近的网络在运行，信息的获取已经失衡。

图6 基于密度分簇的节点不均匀分布WSN的成簇特性(场景1)Fig.6 Clustering characteristics of WSN with node uneven distribution based on density clustering(scene 1)

本文方法和随机投影节点方法的剩余节点数在场景1下的对比如图8所示。从图8可以看出，随机投影节点方法的死亡节点出现比较晚，但节点死亡的速度下降比较快，在剩20个节点的时候骤然瘫痪。而基于节点密度分簇的方法的死亡节点数下降比较缓慢，使得网络的运行时间增长，而且网络也没有突然终止。以剩余20个节点为网络正常运行状态的临界值来考虑，随机投影方法寿命接近400轮，基于密度分簇的网络寿命约为550轮，基于密度分簇法的网络生存期延长了约27%，而且在未瘫痪前，剩余节点数也较随机投影方法的节点数多约20%，运行状态优良。

另外由图8与图5比较可见，基于随机投影节点方法在不同节点分布的网络节点死亡的速度都比较快，在还有约20个存活节点数的时候，都会骤然瘫痪，而本文方法的死亡节点数下降都比较缓慢，网络可以维持较长的时间。

对于场景2，应用基于密度分簇法和随机投影节点法对同样布置的非均匀节点进行分簇。基于节点密度分簇法的簇头分布和成簇效果如图9所示。同样可见，节点数少的网格不再选择投影节点，而是与邻近网格合并形成一个簇，从而均衡了能耗。

基于密度分簇法和随机投影节点方法的剩余节点数在场景2下的对比如图10所示。由图10可以看出，基于随机投影节点的方法的剩余节点数随轮数增加迅速下降，同样在剩20个节点时骤然为0，网络停止运行。而本文方法在每轮的剩余节点数都比随机分簇方法的多，在网络运行中期，可以达到2倍左右的数量。而在随机分簇网络瘫痪后，本文的均衡分簇网络仍可运行，寿命延长了约25%。

图8 基于密度和随机投影节点两种分簇方法的剩余节点数对比(场景1)Fig.8 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 1)

从图5、图8和图10中本文方法与基于随机投影节点方法的比较来看，在整个网络的正常运行期间，相比随机投影节点方法，本文方法的剩余节点数明显较多，网络运行时间长，运行状态优良，耗能均衡。

图9 基于节点密度分簇法的WSN簇头分布和成簇效果(场景2)Fig.9 Cluster head distribution and clustering effect of WSN based on node density clustering method(scene 2)

图10 基于密度和随机投影节点两种分簇方法的剩余节点数对比(场景2)Fig.10 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 2)

3.3 均衡投影的压缩数据收集

基于均衡投影的压缩数据收集方法的具体实施环节包括以下几点:

1)根据网络参数，确定划分网格的数量，并以此划分网格。

2)均衡选择投影节点并建簇。采用基于空间位置或节点密度的均衡分簇法，选择投影节点，并以投影节点为中心建立一个簇。

3)M×N维测量矩阵的每行非零系数对应的节点统一编为一个号 S(S ∈ {1，2，…，M})。

4)根据CS理论，每个投影节点收集相同编号的节点的加权和并一跳或多跳传给Sink。若是多跳传输，在传输过程中将相同编号的数据相加，再传给Sink。

5)经过M次传输，Sink将收集的所有相同编号的数据相加，就可得M个测量值。应用重构算法，就可重构原始数据。

采用均衡分簇法，保证了投影节点的均衡分布，也均衡了网络的整体能耗。由于采用了稀疏随机投影矩阵，只需传送非0节点的加权数据，使得整个网络的能耗降低;而且，如果测量矩阵的每一列只有一个非0元素，这样每一行的非0系数的节点互不干扰，就可以同时进行M个测量值的传送，不必间隔时隙完成，这样的传送速度更快，实时性更强。

而且，基于网格的建簇较之一般的分簇方法并没有增加开销，由于划分好了网格，只需要在网格中选择出投影节点，就可以形成一个簇。由于网格内节点数量有限，所以投影节点的选择比一般分簇的簇头的选择速度要快;而且对基于密度的均衡分簇，当网格内节点数少于某阈值就不需要选择投影节点了，开销更为减少。因此，本文建簇的方法更为节能。

4 结语

针对投影节点随机选择、位置不均衡的问题，本文提出了基于均衡投影的压缩数据收集方法，并针对均匀分布节点WSN，提出基于空间位置的均衡分簇法，以大小相同的网格划分来实现，保证了投影节点的位置均衡;针对不均匀节点分布WSN，提出基于节点密度的均衡分簇法，同时考虑了位置和密度因素，减少了孤立点的能耗，均衡了能量，延长了网络寿命。通过与随机投影节点方法的仿真比较，本文方法运行状态优良，网络生存期显著延长。但对于非均匀WSN，按密度分簇的阈值需要根据实际应用中网络规模、节点整体分布密度和应用需求等综合因素来选择，并需要先进行实验和验证。