无线传感器网络部分覆盖和数据收集算法
2020-10-20魏博垚唐晓岚陈文龙
魏博垚，唐晓岚，陈文龙
(首都师范大学 信息工程学院，北京 100048)
1 引 言
随着物联网技术不断发展，人们对数据收集和感知的需求越来越迫切.在无线传感器网络(Wireless Sensor Networks，WSNs)中，部署在监测区域中的众多传感器节点协作地感知、采集和处理信息并发送给基站，其成本低、灵活多样且能够在恶劣的自然环境(如深海和战场等环境)中工作，因此WSNs成为广泛使用的无线数据收集方式[1].由于传感器节点携带电池能量有限，并且在某些情况下更换电池极其困难，能耗问题成为无线传感器网络研究的重点.如何激活少量传感器节点，在保证数据收集质量的前提下，使尽可能多的节点进入休眠状态，节省数据采集和传输的能耗，从而延长网络寿命，是无线传感器网络面临的重要挑战之一.
无线传感器网络的覆盖模型按照覆盖比例分为完全覆盖和部分覆盖，完全覆盖要求感知节点对目标场景100%覆盖，而部分覆盖只需要对目标场景达到特定比例的覆盖，例如环境温湿度监测通常只需要覆盖目标区域的一部分即可达到监测要求.针对部分覆盖的网络应用，选择尽可能少的传感器节点做为感知节点达到覆盖率要求，同时保证网络连通性，令其他节点进入休眠状态，有助于节约网络能耗.无线传感器网络的覆盖模型按照节点部署方式又分为固定覆盖模型和随机覆盖模型，固定覆盖模型根据预先设定好的节点位置来激活部分节点满足覆盖要求；而随机覆盖模型则是在节点位置随机分布的情况下，依据特定策略激活部分节点，完成对目标区域的覆盖.随机覆盖模型更为灵活，应用更广，因此本文关注于随机部署下的部分覆盖问题.
本文将目标场景划分为若干个区域，在区域内使用基于最大独立集的部分覆盖算法，选择尽可能少的感知节点用于数据采集.然后针对所有区域的感知节点，构建树结构，通过最少跳数将数据从感知节点传输到sink节点，同时尽可能均衡同层节点的子节点个数，实现传输能耗分摊；对于不连通的区域，激活辅助传输节点，实现数据收集.
2 相关工作
近年来，无线传感器网络的覆盖控制和数据收集问题得到一定的研究，提出了一系列算法.本文主要在两个方向进行探索，第一针对部分覆盖问题，寻找满足覆盖要求且激活节点数少的解决方案，从而降低能耗；第二确保网络连通性，建立从感知节点到sink节点的数据收集路径.
在无线传感器网络的覆盖研究中，文献[2]提出了动态覆盖优化算法，把目标区域划分成N个目标点，采用蚁群算法，解决覆盖与网络寿命两个问题，但是未对节点冗余覆盖进行深入探究.文献[3]提出的PCLA算法利用学习自动机实现节点的休眠调度，激活较少的节点满足部分覆盖需求.此方法仍然存在监测冗余，尤其是当覆盖限制条件苛刻时，算法性能受影响，同时文章未指出如何计算覆盖面积.文献[4]较早提出了多重覆盖问题，针对不同子区域具有不同覆盖需求的场景，提出集中式和分布式的算法来选择较少的节点实现p-percent覆盖.一些研究以感知范围不重叠的节点集合建立独立集，从而将无线传感器网络的覆盖问题转化为图的最大独立集问题，该问题是一个 NP难问题[5]，目前主流的解决方案是运用启发式算法求解.文献[6]提出了基于粒子群的优化算法，但是该算法时间复杂度高，参数的配置仍然是一个问题.文献[7]提出一种基于网格划分的无线传感器网络多重覆盖算法，采用布尔模型对节点进行冗余判断，使冗余节点进入休眠状态.
针对节点能量有限以及能耗不均衡的问题，部分研究关注于无线传感器网络中的节点调度.文献[8]设计一种考虑节点剩余能量、信息传输成功率以及节点到基站之间距离的效用函数，构建博弈模型，提出基于势博弈的非均匀拓扑控制算法，但是该研究未考虑节点之间的路由选择.文献[9]提出一种与节点位置无关的休眠调度算法，通过节点与 sink 节点交换数据信息，计算出各个节点的坐标，但是该算法仅考虑2跳之内的冗余，未对所有节点之间的冗余程度对网络性能产生的影响进行分析.文献[10]提出了一种基于最优跳数的非均匀分簇算法UCOH，首先计算数据直线传输到基站的理想路径，依据该路径形成的热区调整簇半径，均衡簇内和簇间通信能耗，但是在分簇的过程中并未考虑部分覆盖问题.
有关无线传感器网络中的数据传输，文献[11，12]提出了在有限传输半径下建立连通集的问题及其应用.文献[13，14]提出了一种可靠的数据传输模型，对于优化传感器网络的路由转发具有较高参考价值.文献[15]对网络路由进行等级划分，使得网络安全性大大提高.文献[16]针对目前主流的无线传感网络拓扑修复算法进行了大量调研，对网络节点的路由选择和修复等研究有较高的借鉴意义.
本文采用了与文献[3]中贪婪法类似的算法来避免监测冗余，激活尽可能少的感知节点；进而适当激活辅助传输节点来保证网络连通性，实现数据从感知节点到sink节点的收集.
3 网络模型
在密集部署的无线传感器网络中，每个传感器节点具有唯一的标识ID，且具有位置感知能力，已知自己的地理位置坐标.通过位置通告，节点获知其通信范围内其他节点(称为邻居节点)的位置信息.假设所有传感器节点的传输半径相同，感知半径可以不同.为了降低感知节点选择算法的计算复杂度，将目标场景划分为若干个大小相等的区域，在每个区域内依据最大独立集计算满足覆盖要求的感知节点集；然后建立由sink节点到各个区域内感知节点的传输路径，本文以最少跳数和子节点数均衡为目标建立树状结构实现数据收集.
为简化感知节点的监测面积计算，本文使用网格模型，即将区域划分为若干个面积为b×b的小网格，依据节点对网格交叉点的覆盖情况得到节点的监测面积，进而计算所有感知节点对区域的覆盖率.
定义1.(节点监测面积) 区域内部署的传感器节点集合记为S={s1，s2，…，sn}，任意传感器节点sn的感知范围是以sn为圆心、以感知半径r为半径的圆形区域，若此范围内包含m个网格交叉点，则称节点sn的监测面积为m个单位.
定义2.(监测冗余) 对于任意两个传感器节点，若其感知范围存在共同包含的网格交叉点，则称这两个传感器节点的监测区域有重叠，该重叠区域称为监测冗余.
定义3.(监测贡献面积) 节点sn的监测贡献面积是指针对区域内尚未被已选择节点感知的部分，节点sn的感知范围能够覆盖的面积.
若对于区域内任意网格交叉点p，都存在节点sn∈S使得sn的感知范围覆盖p，则称集合S是对区域的完全覆盖.部分覆盖应用所要求的感知节点对目标场景的最低覆盖率记为η.
在本文中使用A(S′)表示节点集合S′的监测面积，以S′中所有节点的感知范围所覆盖的网格交叉点个数计算.使用E(si，sj)表示节点si与sj是否存在监测冗余，若节si与sj存在监测冗余，则E(si，sj)=1，否则E(si，sj)=0.用int(si)表示与si存在监测冗余的其他节点集合，N(si)=|int(si)|表示此集合的节点个数，称为节点si的相交节点个数.
图1 覆盖模型图Fig.1 Coverage model diagram
如图1所示，实线圆表示节点的感知范围，阴影部分表示节点s1和s2的监测冗余.节点s1与s2的感知范围分别包含4个交叉点，共同包含7个交叉点，故A({s1})=4，A({s1，s2})=7.s1与s2存在监测冗余，故E(s1，s2)=1；s2与s3不存在监测冗余，故E(s2，s3)=0.因此，int(s2)={s1}，N(s2)=1.若s1的监测贡献面积为其感知范围，则s2的监测贡献面积为其感知范围中除阴影部分以外的区域.
本文使用网格模型是因为直接计算存在监测冗余的多个节点的监测贡献面积，计算复杂度过高.网格模型既能用于节点覆盖面积计算，又能通过调节网格粒度来有效地计算最大独立集，从而找到满足覆盖要求的感知节点集合.网格粗细粒度影响着感知节点的监测面积和监测冗余的计算.网格粒度越大，则监测面积的计算精度越小，面积较小的监测冗余越难以判断；反之，当网格粒度较小时，虽然会提高覆盖面积的计算精度，但是对监测冗余的判断过于敏感，生成的最大独立集中元素个数过少，迭代过程中节点集更新频繁，增加算法的时间复杂度.本文通过实验，得出网格粒度的合理取值区间.
无线传感器网络的节点能量消耗主要包括数据感知的能量消耗和数据传输的能量消耗，本文采用文献[6]的能量消耗模型.根据公式，数据传输能量消耗较大，依据相关文献，节点发送q比特的消息，且传输距离为d时，所消耗的能量表示为.
(1)
式中Ee和Ete均为数据传输的能量消耗参数.相应地，接收q比特数据的能量消耗公式为.
Erx(q)=qEe.
(2)
当节点能量耗尽，则不能继续感知或传输数据.若sink节点收集到数据的感知节点的覆盖面积不能满足网络覆盖率要求，则网络失效.
4 基于最大独立集的部分覆盖算法
若一个节点集中任意两个节点都不存在监测冗余，则称该节点集为独立集.在区域内传感器节点集合S的所有子集中，节点个数最多的独立集称为最大独立集.举例来看，图2的最大独立集为C={s1，s3，s7}，此集合内节点之间存在监测冗余且节点个数最多.
图2 最大独立集示例Fig.2 An example of maximum independent set
由于寻找最大独立集是NP难问题，本文提出基于贪心策略的最大独立集计算方法，称为最大独立集生成算法，旨在相对快速地找到最大独立集.进而以最大独立集为基础，通过增加和删除一些节点，最终激活较少的节点来满足部分覆盖要求.
4.1 最大独立集生成算法
最大独立集生成算法的伪代码见算法1.初始化候选独立集C0，0=Ø，禁忌排序表P0，0=Q.若禁忌排序表Pk，i不为空集，则依次从Pk，i中选择能够与候选独立集中至少一个节点连通的节点sj加入候选独立集Ck，i，并从Pk，i中删除sj和int(sj)中的节点.若Pk，i中待选择的两个节点的相交节点个数相同，即N(sj)=N(sj+1)，并且这两个节点不存在监测冗余，即E(sj，sj+1)=0，则Ck，i=Ck，i∪{si，sj+1}，更新Pk，i；否则产生分支Ck，i和Ck，i+1，分别将节点sj和sj+1加入独立集，并更新每个分支对应的禁忌排序表Pk，i和Pk，i+1，直到对应的禁忌排序表为空时结束此分支.如果最终得到多个元素个数相同的最大独立集，则随机选择一个输出，不属于此集合的节点加入剩余节点集C’.
算法1.最大独立集生成算法
输入：S，N(si)
输出：maximum independent setC
initialize：C0，0=Ø，P0，0=Q；
whilePk，i!=Ødo
select the first two nodessjandsj+1inPk，i；
if(N(sj)==N(sj+1)&&E(sj，sj+1)==0)then
Ck，i=Ck，i∪{sj，sj+1}；
Pk，i=Pk，i-sj-sj+1-int(sj)-int(sj+1)；
else
ifN(sj)==N(sj+1)then
Ck，i+1=Ck，i∪{sj+1}；
Pk，i+1=Pk，i-sj+1-int(sj+1)；
endif
Ck，i=Ck，i∪{sj}；
Pk，i=Pk，i-sj-int(sj)；
endif
endwhile
returnCwith max(|Ck，i|)；
4.2 基于最大独立集的部分覆盖算法
基于最大独立集的部分覆盖算法(MISA)的伪代码见算法2.由最大独立集生成算法计算出最大独立集C后，初始化感知节点集为C，计算感知节点的覆盖率，即C中所有节点的监测贡献面积之和A(C)占区域面积A(R)=b×b的比例.若覆盖率达不到部分覆盖要求，则从剩余节点集C′中选择监测贡献面积最大且和C中至少一个节点连通的节点逐个加入感知节点集，直到覆盖率达到要求.在满足覆盖要求后，对感知节点集进行冗余判定，在保证感知节点集连通的前提下，删除其中监测贡献面积最小的节点，直到删除任意节点都无法满足覆盖要求，则输出感知节点集Ψ.不属于感知节点集的节点进入休眠状态，从而节省网络能量消耗.
算法2.基于最大独立集的部分覆盖算法
输入：C，η
输出：sensing node set Ψ
initialize：Ψ=C；
whilesihas the smallest sensing contributing area in Ψ and
Ψ=Ψ-{si}；
endwhile
else
Ψ=Ψ+{si} wheresihas the largest sensing contributing area inC′；
C′=C′-{si}；
endwhile
endif
returnΨ；
举例来看，在图2所示的7个传感器节点构成的区域中，表征节点之间是否存在监测冗余的矩阵M如下：
计算每个节点的相交节点个数N(sj)，从小到大排序，得到排序表Q=
5 树结构的数据收集机制
在目标场景中，每个区域内依据基于最大独立集的部分覆盖算法选择感知节点，这些感知节点彼此连通.为进一步实现数据向sink节点的传输，本文构建从sink节点到各感知节点的树结构，并为不能连通的区域激活辅助传输节点，实现数据收集.
树结构的建立过程由sink节点启动，记sink节点为第0层，即Lsink=0.sink节点发送建树探测报文JOIN_TREE_REQUEST，其中记录层次值为0，接收到该消息的节点向sink节点发送建树应答报文JOIN_TREE_REPLY，选择sink节点为父节点加入树中，其层次值设为1.进一步地，树上第一层节点发送建树探测报文JOIN_TREE_REQUEST，其中记录层次值为1，接收到该消息且未加入树中的节点选择该节点为父节点，并将自身的层次值设为2.以此类推，所有能够与sink节点连通的感知节点都加入树中，且层次值尽可能小，保证了数据传输跳数最少，传输开销最小.
在树结构建立过程中，若一个节点收到多个上层节点的建树探测报文，则选择已有子节点个数较少的上层节点为父节点，从而使得上层节点的能耗尽量均衡，避免一个节点有过多的子节点，传输能耗大而过早死亡.
对于没有加入树中的感知节点，其所在区域gu内的感知节点不能与周围区域的感知节点通信，因此需要激活部分休眠节点来辅助数据收集.位于该区域gu边界的感知节点sn向其邻居节点发送辅助传输请求报文HELP_TRANS_REQUEST，其通信范围内的休眠节点定期接收请求并处理.对于休眠节点hv，若其通信范围内存在其他区域(例如gu+1)的感知节点sw(树上层次值为Lw)，则hv向sn发送辅助传输应答报文HELP_TRANS_REPLY，其中记录预期层数为RL=Lw+2.否则，即hv的通信范围内不存在其他区域的感知节点，则hv再向其周围休眠节点发送辅助传输请求报文HELP_TRANS_REQUEST，以此类推，直到hv通过x跳找到已加入树中的其他区域的感知节点sw，则以预期层次RL=Lw+x+1向sn发送辅助传输应答报文HELP_TRANS_REPLY.接下来，sn从收到的多个应答报文中选择预期层次RL最小的一个邻居休眠节点，向其发送辅助传输确认报文HELP_TRANS_OK，并以该节点为其在树上的父节点.该休眠节点接收到辅助传输确认报文HELP_TRANS_OK，即从休眠状态调整为工作状态，并建立到邻居区域感知节点的传输路径，从而将该区域gu内的数据多跳转发到sink节点.
以图3为例，目标场景划分为四个区域，sink节点位于场景左上方.以sink为根，构建包含尽可能多感知节点的树结构.区域g2中的感知节点因为与其他区域感知节点的距离大于通信半径，不能加入树中，故激活g2中的休眠节点h1，使得g2中的感知节点通过h1与邻居区域g1中的感知节点通信，进而将数据传输到sink节点.在该示例中，休眠节点h2也能够将g2中的感知节点与邻居区域g4中的感知节点连通，但通过h2加入树中的预期层次数大于通过h1加入树中的预期层次数，即通过h2的数据传输跳数大于通过h1的数据传输跳数，因此g2中的感知节点选择h1做为辅助传输节点.
6 仿真实验
6.1 实验参数配置
本文使用C++与MATLAB进行无线传感器网络仿真实验，目标场景400m×400m，随机抛洒100个节点，感知半径为70m，传输半径是感知半径的两倍.网格粒度b为20m，部分覆盖的覆盖率要求η设为80%和60%，节点初始能量为 5 J，能量参数Ee=100 nJ/bit，Eet=20nJ/(bit·m2).
6.2 实验结果与分析
1)工作节点比率.对比方法选择文献[11]所提出的CDS算法和文献[4]提出的DFS算法.在覆盖率η分别取80%和60%时，本文所提出的MISA算法和对比方法的工作节点比率如图4所示.
图4 工作节点比率Fig.4 Working node proportion
如图4所示，与 CDS和 DFS算法相比，本文提出的MISA算法在η=80%和η=60%的情况下，工作节点(包括感知节点和辅助传输节点)的数量较少，从而使得更多的节点进入休眠状态，节省能量消耗.这是因为相较于CDS与DFS，MISA算法以最大独立集为基础，选择监测贡献面积大的节点加入感知节点集，从而尽可能少地激活感知节点来满足最小覆盖要求.
2)感知节点计算过程中各类节点比率.图5展示了在感知节点集计算过程中，最大独立集的节点、增加节点和删除节点占所有节点的比率.由图5可见，在生成最大独立集后，MISA仅需要增加或者删除少量的节点就能满足覆盖要求.
图5 感知节点计算过程中各类节点比率Fig.5 Proportions of different kinds of nodes in sensing node calculation process
6.3 参数分析
1)网络规模分析.令目标场景中的传感器节点个数从100到400递增，在覆盖率要求80%时，选择文献[7]的GPSA算法做为对比方法，本文算法的感知节点数和辅助传输节点数以及GPSA算法的工作节点数见图6.
由图6可见，网络规模变化对本算法的感知节点和辅助传输节点选择无明显影响.覆盖率要求80%时，虽然感知节点数和辅助传输节点数随网络规模的变化略有差异，但是其差异变化不大，均在合理范围内.在部署节点数量一致的情况下，MISA算法明显优于GPSA算法.当感知节点较多时，需要的辅助传输节点较少，这是因为大量的感知节点使得其彼此之间的连通性更强.
图6 不同网络规模的工作节点数量Fig.6 Number of working nodes with different numbers of sensor nodes in the scenario
图7 不同粒度比的最大独立集节点比率Fig.7 MIS node proportion with different B
由图7可见，随着粒度比B变大，区域中的网格交叉点变少，两个传感器节点重叠的监测区域覆盖网格交叉点的概率变小，从而计算出的监测冗余变少，被选到最大独立集中的节点变多.当粒度比B较小时，最大独立集节点较少，通常需要增加额外的节点以满足覆盖要求；当粒度比B较大时，计算误差较大，同时最大独立集节点个数偏多，需要对超出覆盖要求的多余节点进行删除，也会增加运算时间与能量开销.总体来看，粒度比取0.3左右效果较佳.
7 总 结
本文讨论了无线传感器网络的部分覆盖问题，节点随机部署导致监测区域相互重叠，产生监测冗余.为了激活较少的节点满足区域内的部分覆盖需求，本文提出了MISA算法，首先依据相交节点信息，计算最大独立集，以此为初始感知节点集；然后针对不同覆盖率要求，依据监测贡献面积，增删少量节点以达到覆盖要求.接着通过构成以sink节点为根的树结构，将感知节点加入树中，实现数据收集；针对不能连通的区域，激活辅助传输节点来完成数据收集.实验表明，本文所提出的方法能够有效降低工作节点数，使得更多节点进入休眠状态，从而延长网络生命期.
