一种基于空间相关性的WSNs 节点睡眠调度算法*

程明月，马娅婕，赵 蕾，肖 凡

(1.武汉科技大学 信息科学与工程学院，湖北 武汉430081;2.武汉科技大学 冶金工业过程系统科学湖北省重点实验室，湖北 武汉430081)

0 引 言

为了有效地分析大气污染的分布与地理环境、人类活动、天气变化之间的关系，有必要将传感器节点密集分布，但这种部署会带来采样数据的急剧增长［1］。由于庞大的采样数据在同一时间传送至汇聚节点而导致网络拥塞、数据延时等问题。同时，由于传感器节点的电池能量有限，更换电池困难，这就使节能成为无线传感器网络(WSNs)中需要考虑的重要因素。基于以上考虑，需要建立一个完善的节点调度机制来避免拥塞并延长网络的寿命。

影响节点调度策略的因素众多，国内外研究学者在这个领域进行了一系列的研究，其中，最早、最典型的分簇调度算法之一是一种低功耗自适应分簇路由协议，即LEACH算法［2］。LEACH 算法减小了节点能量消耗，但是在簇头选举时忽略了节点自身的能量，容易出现低能量簇头节点而引发数据传输中断、传感器网络数据失真等缺点。文献［3］提出PEGASIS 算法，核心思想是尽量减少直接与Sink 节点进行通信的节点，这种算法需要清楚所有节点的地理位置信息，严重提高了网络开销。为此，文献［4］基于“1∶1 双簇容错技术”和“层次簇头概率”等技术及概念提出了ECHNL(equal cluster head distribution based on network level)算法，并在分层的网络区域内对网络的信息采集过程进行优化。该算法在簇头分布合理的情况下最大限度降低了网络能耗，但是忽略了网络的通信质量这一重要指标，在实际应用中的效果并不太理想。

本文基于WSNs 中的流量和能耗问题，设计了一种基于空间相关性的节点睡眠调度算法(spatial correlationbased algorithm for node sleeping scheduling，SCASS)。该算法使用空间相关性和节点剩余能量组成权值函数来选择最优节点作为监测区域的代表节点进行数据传送，未被选中节点则处于睡眠状态，以此来降低节点能耗，延长网络寿命，提高通信性能。

1 SCASS 描述

1.1 大气污染物等级划分

根据国家环境局研究分析，大气污染具有极其明显的时空相关性。污染物的浓度变化是一个微小而缓慢持续的过程，在时间上，相对较短时间内大气污染物浓度的变化几乎为零;在空间上，空间距离越相近的节点数据更具有相似性。首先将污染物浓度转换为API 指数(污染标准指数)［5］，并进一步将污染程度划分如表1 所示的7 个等级。

表1 污染标准指数等级划分Tab 1 Pollution standard index grade partition

1.2 节点睡眠调度算法

1.2.1 节点状态转换

本算法利用传感器节点感知数据的空间相关性除去冗余节点，同时减少数据量的传送，避免过重的信道竞争，在保证满足用户需求的前提下，延长网络寿命，同时提高服务质量。

SCASS 中节点的状态转换模型如图1 所示。

图1 节点状态转换图Fig 1 Node state transform diagram

1)睡眠状态:处于睡眠状态的节点只进行数据采集，而不进行数据传输。经过延时Δt 后，转入半睡眠状态。

2)半睡眠状态:处于半睡眠状态的节点基于调度算法选举出最具有代表性的节点，该代表节点进入活动状态，否则，回到睡眠状态。

3)活动状态:处于活动状态的节点进行数据采集，并将采集到的数据传送至Sink 节点。工作一定时间Δt 后转入睡眠状态，且不参与下一轮的选举。

处于半睡眠状态的各个传感器节点采集污染数据，并判断出本节点所处的污染等级，则其通信半径内的区域都属于该等级区域块。若相邻节点处于同一等级，则其所在的区域将可以合并为同一等级区域块。针对每一个独立的区域，选择最具有代表性的节点进入活动状态，并将采集到的数据作为该区域污染浓度的采样值发送至Sink 节点;而其他节点则都回到睡眠状态。

1.2.2 空间相关性的计算

根据表1 所示的污染标准指数等级划分，对于其中某一块区域A，V 是该区域内的节点集合，i∈V。

定义1 邻居节点集:假设每个传感器节点的通信半径相等且为r，则以该节点为圆心，半径为r 的圆内所有节点都可以与该节点建立通信连接。这些点组成的集合即为该节点的邻居节点集。

定义2 根据表1 所示的污染标准指数等级划分，若N 是i∈V 的邻居节点集，j∈N 是i 的某邻居节点。在连续t 个采样时间点内，节点i 的采样数据为X=［x1，x2，…，xt］，j 的采样数据为Y=［y1，y2，…，yt］。

X 的期望表示为

X 的方差表示为

同理

X 与Y 的协方差表示为

其中，pij为X 取值xi和Y 取值yj时的联合分布概率。

X 与Y 的空间相关系数表示为

利用上述算法过程，将节点i 与其邻居节点集的每一个邻居节点进行相关系数的运算，则该节点的平均空间相关系数ρxi(0≤ρxi≤1)可以表示为

其中，|N(j)|表示i 的邻居节点集的个数。

根据实际给定门限值ρ0和ρ'0，有两种情况:

1)若ρXi∈(0，ρ0)，说明该节点具有相对较强的空间相关性，则可以得到候选节点集S;

2)若ρXi≥ρ'0，说明该节点所处环境特殊或者其他情况，则将此节点作为特殊代表节点单独列出，所采集数据直接发送至Sink 节点。

1.2.3 基于能量的权值计算

由于每个传感器节点的能量有限，为了均衡网络能耗，本算法基于剩余能量在候选节点集S 中选择最终的代表节点。

定义3 假设每个传感器节点的初始能量都相同，记为Ein;无线传感器网络工作一段时间以后的剩余能量为Ese，则节点i 在进行代表节点选举过程中的权重wi为

对每一个候选代表节点做如式(8)所示的权重处理，空间相关系数越大，权重越大，所采集到的数据越具有代表性;剩余能量比例越大，权重也会越大，通过均衡节点剩余能量，从而达到延长WSNs 寿命的目的。最终所选取代表节点为

在区域A 中满足条件ρXi≥ρ'0和式(9)的节点，即为最终的代表节点。

被选择的代表节点从半睡眠态转为活跃状态，未被选择的节点则由半睡眠态转换为睡眠态。待整个系统网络稳定工作Δt 时间后，进行新一轮的代表节点的选举。其中，上一轮被选中的代表节点将直接转为睡眠态，其余节点由睡眠态进入半睡眠态，并参与新一轮的代表节点的选举。

2 算法性能分析

2.1 复杂度分析

在对区域中每个节点进行空间相关性运算的时间复杂度是O(n2)，在根据每个节点的空间相关性进行代表节点选举阶段的时间复杂度是O(n)。因此，整个算法的时间复杂度是O(n2)。假设WSNs 在该区域最大拓扑的节点个数为|V|，该算法在根据各个节点的空间相关性进行代表节点的选举时有信息交换，因此，该睡眠调度算法的消息复杂度是O|V|。

2.2 仿真实验

2.2.1 仿真环境

仿真实验采用Omnet++作为仿真平台，版本为4.3。仿真实验所使用的数据选择的是伦敦东区某区域中所采集到的大气污染数据，每个节点均可采集到NO，NO2，SO2，O3四种污染物的浓度，采集的数据单位是PPM。每个采样点从早上8:00 到下午18:00，每隔1 min 对四种污染物的浓度进行一次采样。由于，大气污染物浓度15 min 内的变化较小，因此，本文中Δt 的值选取为15 min，采样频率为1 次/min。实际地理环境和节点分布如图2 所示。

图2 实验数据采样地点图Fig 2 Experimental data sampling location map

2.2.2 实验结果分析

通过运行SCASS 对网络节点的平均剩余能量、稳定工作一段时间后的活跃节点数，以及网络通信中所产生的时延进行了仿真，并与文献［4］中的算法进行了对比。其中，仿真使用10×14 的方格拓扑结构，采用CGD 路由协议［6］。节点初始化能量为100 J，带宽为20 kbps，侦听功率0.02 W，接收功率为0.1 W，传输功率为0.3 W。

节点剩余能量随时间变化仿真结果如图3 所示。从图3所示的仿真结果可以看出:随着时间的推移，节点剩余能量逐渐减小，总体而言，SCASS的剩余能量值始终比ECHNL 的高，并且时间越长，显示差距越大。

图3 节点剩余能量与时间关系Fig 3 Relationship between node residual energy and time

从图4 所示的仿真结果可以看出:随着网络稳定工作时间的延续，网络死亡节点数不断增多，这是由于部分节点因能量消耗过多，不能维持传感器节点的持续工作而死亡。并且由图4 明显看到，SCASS 的死亡节点数低于ECHNL 算法。

图4 死亡节点数与时间关系Fig 4 Relationship between node numders and time of death

从图5 所示的仿真结果可以看出:随着节点数的增多，网络数据量和负载也随之增加，导致网络时延不断增大，二者算法差距并不大，但是SCASS 始终优于ECHNL 算法，并且随着节点数的增多，优势越来越明显。

图5 数据包延迟与节点数量关系Fig 5 Relationship between data packet delay and number of nodes

3 结 论

本文基于传感器节点的空间相关性，并综合考虑节点的剩余能量，提出了针对高密度部署的WSNs 的节点调度算法。该算法与ECHNL 算法相比，在一定程度上减少了网络平均能量消耗，同时缓解了数据量过大而造成的网络拥塞。通过仿真实验可知:本文算法在节省网络能耗，延长网络寿命的同时，还降低了数据传输的时延。

［1］ Ezovski G M，Watkins E V.The electronic sensor node and the future of government－issued RFID－Based Identification［C］∥IEEE International Conference，United states，IEEE Press，2007:15－22.

［2］ Ma Y，Richards M，Ghanem M，et al.Air pollution monitoring and mining based on sensor grid in London［J］.Sensors，2008，11(2):3601－3623.

［3］ Li B P，Zhang X Q.Research and improvement of LEACH protocol for wireless sensor networks［C］∥International Conference on Information Engineering(ICIE)Singapore，2012:234－239.

［4］ 王爱美.基于LEACH 协议的无线传感器网络分簇算法研究［D］.兰州:兰州交通大学，2013.

［5］ Reddy A，Kumar A，Janakiram D.Wireless sensor networks operating systems:A survey［J］.International Journal of Sensor Networks，2009，5(4):236－255.

［6］ Mamidisetty K K，Duan M L，Sastry S.Multipath dissemination in regular mesh topologies［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(8):1188－1201.