基于目标覆盖感知的WSNs节点部署算法

符 春

(长沙民政职业技术学院，湖南 长沙 410004)

0 引 言

无线传感网络(Wireless Sensor Networks, WSNs)[1]已在多个领域内广泛使用，如环境监测、战场勘察、物联网。WSNs是由微型的、对周围环境具有感测能力的传感节点组成。这些传感节点先感测数据，然后将数据传输至信宿(Sink)。传统的WSNs网络采用静态的Sink。然而，若采用的静态Sink方式，则位于Sink邻近的节点需要不断的转发数据，这就加剧它们的能量消耗[2]。一旦能量消耗殆尽，就形成网络分裂。为此，研究人员引用动态Sink方式，即每隔一段时期，Sink就移动它的位置[3]。

此外，目标覆盖和网络连通是WSNs的两个研究热点。前者保证目标区域被传感节点实时地监控，而后者提供通信质量，即保证数据传输的有效性。针对这两个热点，研究人员提出不同策略。这些策略可分为两类：1)优化部署传感节点位置；2)优化Sink位置。

目前多数算法是通过优化部署传感节点位置，提高目标覆盖率和连通率。在文献[4]中，作者将优化部署传感节点问题转化成Steiner 最小树问题，再利用Heuristic算法求解。此外，文献[5]将节点部署问题分解成多个子问题，再“分而治之”。然而，这些算法只是针对静态Sink网络。

目前，针对动态Sink的WSNs，优化部署节点问题的研究较少。为此，本文分析了面向动态Sink的WSNs，节点部署问题，即如何以最少的节点数实现最大的网络覆盖和连通率。

具体而言，将节点部署问题化成两个子问题：目标覆盖(Target Covering, TC)问题和网络连通(Network Connectivity, NC)问题。TC问题是指如何以最少的传感节点数覆盖所有目标；而NC问题是指如何以最少的转发节点，连通动态的Sink。对于TC问题，采用k-means簇算法求解，即先将多个目标划分成簇，然后在每个簇内，部署传感节点实现簇覆盖；对于NC问题，提出贪婪算法求解。实验数据表明，提出的基于目标覆盖感知的节点部署算法(Target Coverage Aware-based Node Placement, TCA-NP)算法有效地解决节点部署问题和连通问题。

1 TCA-NP算法

1.1 概述

假定所有的传感节点具有相同的感测半径Rs和通信半径Rc，且Rs≠Rc。并且感测区域和通信区域为圆形结构，如图1所示。图1假定Rs>Rc。

图1 传感节点感测和通信范围模型

TCA-NP算法主要解决TC问题和NC问题，并且用k-means算法解决TC问题，然后用贪婪算法求解NC问题。

本文是从两个角度分析节点部署问题，一个是从覆盖目标角度，优化部署节点，使这些节点能有效地覆盖目标；另一个是从连通Sink角度，部署中继节点，使网络连通。这个两个问题的本质均是部署传感节点。解决TC问题有利于NC问题解决。换而言之，解决TC问题是优化NC问题的基础。因此，本文先解决TC问题。

1.2 基于k-means的求解TC问题

本小节，分析如何用最少的传感节点数覆盖所有目标。将目标看成一点。如果目标间的距离不超过2倍的感测半径Rs时，可用同一个传感节点覆盖这些目标。

为此，将目标划分多个簇，致使邻近的目标构成一个簇。据此，引用k-means簇算法[6]。k-means簇算法目的就是使簇内的节点间的平方距离差最小，而使簇间的节点间平方距离差最大。

(1)

如果d小于Rs，则可以中心位置Oi上部署一个传感节点sr，仅通过这个传感节点，就可以覆盖Li内目标。因此，将sr置于Oi。

(2)

(3)

此外，引用传感节点集Si，其表示在Li内部署的传感节点。确定了传感节点sr位置后，就将sr加入Si。

一旦部署了传感节点后(假定为节点sr)，就计算簇Li内所有的目标节点与节点sr的距离。如果d(sr,Tj)小于Rs，则将它从簇Li内删除。删除后，簇内只剩下节点sr不能覆盖的目标[8]。然后，再重新计算中心位置，继续部署传感节点，直到簇Li内无目标。最终，就形成部署传感节点集Si。整个算法的伪代码如算法1所示。

图2显示了部署传感节点过程。在图2(a)中，先计算簇内中心位置，然后再寻找离中心位置最远的目标节点；在图2(b)中，部署一个传感节点，然后，再将此传感节点所覆盖的目标从簇内删除。最后，再重复上述过程。

图2 部署传感节点的过程

1.3 基于贪婪算法的NC问题

假定在数据收集次数n

令G=(V,E)，其中V表示顶点集，E为边集。将图G转化为子图，且每个子图表示一个连通图，并引用R={C1,…,Cm}表示这些连通图的元素。本小节的目的就是通过添加新的中继节点使得所有连通元素均能在第j次数据收集时，连通至Sink。

令C(1)表示在第j次数据收集时还未连通至Sink的元素集合，而C(2)表示在第j次数据收集时，由所有信宿和连通节点所构成的集合。显然，在初始状态时，C(1)初始为R，而C(2)初始化为所有信宿。通过执行Greedy算法，直到C(1)为空。

(1)寻找两个元素间的最小距离，一个元素属于C(1)，另一个元素属于C(2)。假定X、Y为这两个元素，且X∈C(1)、Y∈C(2)。然后，将中继节点部署于连通X与Y的连线上；

(2)将X内的所有元素移动C(2)，再将X从C(1)内删除。

图3 部署中继节点示例

图3显示了部署中继节点的示例。图3(a)显示了C(1)内几个连通的元素集，现从C1和C(2)中寻找X、Y，使它们连线长度最短。然后，在它们的连线上部署中继节点，使这两个元素集连通，如图3(b)所示。最后，再将C(1)内所有节点移到C(2)中，这表明C(1)内所有节点已连通到了Sink，如图3(c)所示。

2 性能仿真及分析

2.1 仿真参数

利用MATLAB软件建立仿真平台。考虑2000 m×2000 m的网络拓扑，所有传感节点具有相同的感测半径，且为15 m，而通信半径为30 m。为了更好地体现TCA-NP算法的性能，进行三个实验。同时选择文献[10]的SMT-MSP算法和文献[11]的SGA算法进行比较，主要分析所需要的传感节点数(Total Number of Required Nodes, TNRN)、运行时间。每次实验独立重复30次，取平均值作为最终的实验数据。

2.2 实验一

本次实验分析Sink数对所需的传感节点数TNRN的影响，其中目标数为200，数据收集次数k=5，Sink数从10至60变化。实验数据如图4所示。

图4 TNRN随Sink数的变化曲线

从图4可知，提出的TCA-NP算法的TNRN最少，并且随着Sink数的增加而下降。原因在于：当信宿数的增加，信宿与传感节点间的距离就减少，因此，所需的中继节点数得到下降。

然而，与TCA-NP算法相比，SMT-MSP算法的TNRN并没有数随Sink数增加而下降。这主要有两点原因：一方面，Sink数的增加降低Sink与传感节点间的距离，降低了部署中继节点数；另一方面，在SMT-MSP算法中，在每次数据收集时，必须保证所有传感节点与Sink连通，因此，Sink数数的增加添加对中继节点的需求。

2.3 实验二

本次实验分析数据收集次数对TNRN的影响，其中目标数为200，Sink数为10，数据收集次数从5变化至25，实验数据如图5所示。

图5 TNRN数随数据收集次数的变化曲线

从图5可知，当SMT-MSP算法的TNRN随数据收集次数的增加上升得最快，而本文提出的TCA-NP算法上升最慢，几乎不变，原因在于：在SMT-MSP算法中，要求部署中继节点，进而保证在每次数据收集时是连通的。而SGA算法随数据收集次数变化很慢，但它所需的TNRN数远高于TCA-NP算法。

2.4 实验三

本次实验分析目标数对TNRN的影响，其中Sink数为10，数据收集次数为5，其中目标数从10至250变化。实验数据如图6所示。

图6 目标数对TNRN的影响

从图6可知，TNRNs数随目标数的增加而上升。原因在于：目标数越多，就需要更多的传感节点覆盖目标。因此，需要部署更多的中继节点才能连通Sink。此外，从图6可知，TCA-NP算法的TNRN最低，但随着目标数的增加，TCA-NP算法性能与SGA算法逐渐相近。

2.5 实验四

本次实验分析算法的执行时间。执行时间越长，算法越复杂。执行算法的PC参数为：Intel Core i7-5500U、RAM 8GB。此外，Sink数为10，数据收集次数为5，其中目标数从10至250变化，实验数据如图7所示。

图7 执行时间随目标数的影响

从图7可知，执行时间随目标数的增加而上升。原因很容易理解：目标数越多，需要部署更多节点才能覆盖目标，这必然增加执行时间。此外，与SMT-MSP算法、SGA算法相比，提出的TCA-NP算法的执行时间最多，且随着目标数呈增加趋势。这也说明，TCA-NP算法是以增加复杂度换取低的TNRN数，但是增加的复杂度并不高，例如，当目标数为250时，TCA-NP算法的执行时间比SGA算法增加了不到50 ms。

3 结 语

针对无线传感网络的目标覆盖和网络连通问题，展开分析，并提出基于目标覆盖感知的节点部署算法TCA-NP。TCA-NP算法分别引用k-means算法、Greedy算法求解目标覆盖问题、网络连通问题，进而优化节点部署，实现对目标的全覆盖。实验数据表明，提出的TCA-NP在覆盖目标时，所需的传感节点数最少。