WSN中基于线性规划的多类别目标覆盖算法

于广州



WSN中基于线性规划的多类别目标覆盖算法

于广州

(广东海洋大学网络与教育技术中心，广东 湛江 524025)

多类别目标覆盖问题是目前无线传感器网络中的研究热点。针对现有目标覆盖算法在时间效率、网络生命周期等方面的不足，将多类别目标覆盖问题建模为基于线性规划的网络生命周期最大化问题，提出一种基于分簇的目标覆盖算法。该算法依据节点的剩余能量和感应能力，在每个簇结构内求解最优覆盖集的基础上得到接近于最优解的全局覆盖集，进而调度节点相应的感应模块去覆盖其感知范围内同属性的目标。实验结果表明，该算法是有效的，在网络生命周期和时间效率等方面均优于CWGC方案，接近于线性规划最优值。

无线传感器网络；目标覆盖；线性规划；分簇；最优解；网络生命周期

1 概述

无线传感器网络(Wireless Sensor Networks, WSN)综合了无线通信技术、传感器技术、嵌入式计算技术和分布式信息处理技术，是目前国际上前沿热点的研究领域。其中，传感器网络的目标覆盖问题[1]是指保证目标覆盖质量的条件下，如何调度传感器节点的状态，减少节点的能量消耗，最大化网络生存周期。在大规模无线传感器网络中，需要被覆盖的目标经常是多样化、多类别的，如何有效地对这些目标进行覆盖控制，并通过空间资源的优化分配来满足用户的感知需求，将直接反映无线传感器网络对外界环境的感知服务质量。因此，本文主要针对无线异构传感器网络中多类型目标覆盖问题[2-3]进行研究，寻求以最少的传感器节点数及最佳的节点部署位置，实现目标的监测和数据传输，优化网络成本。

2 相关工作

目标覆盖问题一直是WSN中的一大研究热点。相继有众多的学者提出了一系列方法用于无线传感网中目标覆盖的方法，如文献[4]分析了目标覆盖中的连通性问题,首次提出针对目标全覆盖与维护节点集连通性关系的连通临界条件。并针对连通性条件无法满足的情况，提出了一个维护连通性的优化部署方案。最后的实验表明，该方案既能实现对目标集的全覆盖，又维护了连通性；文献[5]提出一种能量有效的优化覆盖算法。该算法将目标覆盖区域节点能量构建成正态分布的网络模型，通过采集和检索数据选择最优子集以及对节点状态调度机制动态转换，可以有效地降低网络能耗，在提高节点覆盖性能的同时优化了节点的数量。该算法能够以较小的代价延长整个网络的生存周期，具有更好的适应性和稳定性；文献[6]针对有向传感器网络的全目标覆盖问题，提出一种基于免疫算法的有向传感器网络目标覆盖方案。该方案采用免疫算法寻找最少数量的传感器，覆盖某一区域内全部的目标点；文献[7]针对视觉传感器网络目标覆盖过程中因覆盖冗余、节点剩余能量不均等原因导致网络寿命过短的问题，设计一种视觉传感器网络目标覆盖算法。该算法基于节点与目标的覆盖关联关系，利用关系矩阵及相关运算对覆盖频繁目标集进行挖掘，进而对工作节点进行动态选举，以此延长网络的生存时间。该算法在保证网络覆盖质量的前提下能够高效地调度工作节点，均衡节点耗能，有效延长网络寿命。

此外，文献[8]通过使用最少数量的传感器节点，设计了一个临界正方形网络覆盖算法以覆盖关键网格。算法是基于节点加权的Stenier树而选择网格点集合，在选择的网络点上部署节点而形成一个连通的无线网络，从而达到覆盖全部的关键网格；文献[9]针对普通传感器节点与网关节点之间的多跳覆盖和连通问题，设计了一个基于整数线性规划的优化方法，它用于最小化节点部署代价和能量消耗。同时该文也提出了一个适合于大规模部署的异构传感器网络环境的启发式算法；文献[10]针对最大化网络覆盖时间问题，提出了一个随机部署节点环境下网络覆盖时间最优化算法，该算法利用线性规划方法[11]最优化计算网络节点分簇和节点之间的路由构建，在线性时间内解决了最大化网络覆盖时间问题。本文在现有工作的基础上，提出一种改进的目标覆盖算法，并通过仿真实验验证该方法的有效性。

3 问题建模

3.1 网络模型

为了方便描述，首先给出如下的定义：

定义1(目标覆盖)任务区域的目标至少被一个活跃节点所感知，则称目标被覆盖。

定义2(网络生存周期)从网络正常工作运行开始，直到存在某一个监测目标不能被任何部署的节点所监测覆盖，这个时间段称为网络生存周期。

本文针对异构传感器网络的覆盖问题展开研究，并基于如下的假设：

(1)传感器节点安装有多个感知单元模块，这些模块能够分别监测不同类型的目标信息。部署后的网络采用分簇结构的管理模式，网络的拓扑结构如图1所示。

图1 分簇结构的网络拓扑

(3)为平衡节点之间的能量消耗，本文采用时间离散化思想将网络运行时间划分成若干个长短相等的间隔，每一个时间时隔称为了一个时间“轮”。每一个时间由初始阶段和感知阶段组成；在初始阶段由簇头节点随机决定其成员节点的初始状态，假如节点满足覆盖要求则进入工作状态进行监测目标。网络运行的时间线结构如图2所示。

图2 网络运行时间划分

3.2 问题描述

(1)全部目标能够被每个覆盖集所覆盖；

(2)值最大化；

(3)覆盖集中的每个节点所消耗的能量不能大于其初始能量。

依据上述定义，MTTC问题可被建模为：

式(4)中各个变量含义如表1所示。

表1 MTTC问题参数描述

为描述节点与目标之间的覆盖关系，本文给出一个示例(包含4个节点和7个目标)，如图3所示。图中每个节点安装了2~3个不同功能的感知单元(模块)，每个模块能够感知一种类型的目标。

图3 覆盖示例

在这个示例中，节点与监测目标之间的覆盖映射关系为：1＝{1,5}，2＝{1,4,6}，3＝{2,3,6}，4＝{1,2,3,5,7}，图4表示了图3所示例子的覆盖映射关系。

图4 图3示例对应的覆盖映射关系

4 目标覆盖算法

4.1 算法基本思路

由于节点最优覆盖集求解是一个NP难问题[12]，不能直接求解MTTC问题。因此，本文给出一个基于分簇结构的目标覆盖求解算法，将寻找全局最优覆盖解转化为寻找簇内最优覆盖解，从而使全局解接近最优解，降低了解决问题的难度，其基本思想如下：

(2)簇头节点的剩余能量和节点的感知能力的大小将其成员节点在其链表中位置由高到低排序，排在前面的成员节点具有更高的优先覆盖权。簇头节点则根据监测目标是否被节点覆盖由前到后查找其存储的链表，并将符合条件的成员节点标记。

4.2 算法实现步骤

为了描述方便，先给出算法中所使用的变量的说明，如表2所示。

表2 本文算法中的变量描述

算法的主要实现步骤如下：

(4)簇头节点在完成步骤(3)的工作之后，簇头节点根据监测目标是否被节点覆盖由前到后查找其存储的链表，并将符合条件的成员节点标记。它包含3个子步骤：

3)当链表被遍历完成后，簇头节点会调度最佳的成员节点覆盖其监测范围内的目标。否则，转到本步骤的第一个子步骤，以完成全部的覆盖集节点选择。

通过以上步骤的执行，可以实现对网络中所有的目标的最优覆盖，覆盖算法描述如下：

算法最优覆盖集构造算法

j++;

} }

Step5While ( j< i){

Step6 While (k

If (CL[k].data包含在CL[j].data内){

将重复覆盖信息CL[k].data从CL中删除;

}

j++;}

j++;}}

4.3 算法性能分析

定理1本文算法在最坏情况下以(n)的时间复杂度完成构造覆盖集对目标覆盖，其中，为感知区域中节点数量。

以下采用图5所给出的覆盖场景为例，通过节点的剩余能量变化更直观地反映网络利用最优覆盖集构造算法构造最优覆盖集的过程。在这个例子中，节点安装有多个感知单元模块，分别表示为u、u和u；在一个时间“轮”内，这3种模块工作时的能量消耗分别为3、4和5；节点的初始能量为50。此时，4个节点的感应能力分别为：

在仅考虑节点感应能量消耗的情况下，利用算法1，在每一轮中所构造的覆盖集如图5所示。节点在每一轮中所消耗的能量和剩余能量变化如表3所示。从表3中可以看出该网络能够运行5个时间“轮”长的生命期。

图5 利用最优覆盖集构造算法形成的5个覆盖集

表3 图2示例中节点剩余能量变化(节点初始能量为50)

5 实验结果与分析

为测试本文方案的性能，以Matlab2012为工具进行了仿真实验，实验环境参数设置如表4所示。

表4 实验环境中的参数设置

本文分别从传感器节点个数变化、目标个数变化以及节点所拥有的感知单元类型数量变化等3种情况分析目标覆盖算法的性能，通过实验对比本文算法与线性规划理论值(LP)、CWGC算法[1]在网络生存期和算法执行时间方面的性能。实验结果为50次独立实验结果的均值。

(1)不同节点个数下网络生命周期比较

该组实验中部署了20个待监测目标，3种方案都采用表4所示的实验参数，实验结果如图6所示。

图6 不同节点数目下的网络生命周期比较

可以看到，随着节点数量的增加，网络生命周期也呈线性增加，这是由于网络有更多的节点用于轮流调度去覆盖目标，从而延长了节点的寿命。其中，LP方案是最优的，这是因为LP方案是一个利用全局网络信息的集中式方案，而本文方案的生命周期接近于LP，相比于CWGC，本文方案的生命周期延长了8%。这主要是因为，本文方案通过使用节点覆盖能力的高低作为调度的依据，并依据簇头节点的剩余能量和节点感知能力的大小来对目标覆盖指定优先级，降低了同时处于活跃状态节点的数量，延长了网络生命周期。

(2)不同目标个数下网络生命周期比较

该组实验中部署了120个传感器节点，3种方案都采用表4所示的实验参数，实验结果如图7所示。

图7 不同目标个数下的网络生命周期比较

可以看到，随着待监测目标数量的增加，网络生命周期也呈下降的趋势。对比3种方案可知，本文方案的性能要明显好于CWGC算法，而与最优的LP方案差别不大。

(3)不同感知单元属性数量下的网络生命周期比较

该组实验考察了不同节点感知模块数量对网络生命周期的影响，实验中节点数量为120个，待监测目标数量为20个，实验结果如图8所示。

图8 不同感知单元个数下的网络生命周期比较

可以看到，随着节点的感知单元模块数量的增加，3种方案下网络的生命周期生存期不断递减，这主要是由于增加的感知消耗更多的能量。与前述2个实验结果类似，本文方案的性能介于CWGC算法和LP方案之间，与最优的LP方案差别不大。

(4)算法的执行时间对比

设置传感器节点数量为120个，感知单元为4个，对不同目标个数下的覆盖算法执行时间效率进行了对比，实验结果如图9所示。

图9 不同方案的时间效率比较

可以看到，随着待监测目标数量的增加，3种方案的执行时间都呈上升的趋势。其中，LP的时间效率最低，这主要是因为，LP需要利用网络的全局信息来实现，需要进行大量的信息传递，因此其执行时间最长；而CWGC采用贪婪法来寻找最优的覆盖集合，算法的迭代次数随着目标个数的增加而增加，当网络中目标个数较多或目标分布不均匀时，CWGC的收敛性较差，执行时间较长；而本文方案采用分簇技术降低了问题求解的难度，并基于整数规划的思想，只依据成员节点的感应能力和剩余能量大小来进行最优覆盖，因此，在一个时间轮中的执行时间是最短的，提高了算法的效率。

6 结束语

本文主要研究的内容是异构传感器网络的多类型目标覆盖算法。针对本文所提出的MTTC问题，采用分簇结构和线性规划相结合来求解。针对MTTC问题在全局求解方面存在的困难，提出了一种基于分簇结构的目标覆盖算法；该算法依据节点的剩余能量和感应能力，在每个簇结构内得到接近于最优解的全局覆盖集，并能覆盖其感知范围内同属性的目标。最后通过实验方法比较了在不同评价标准条件下所提本文算法的性能。算法能够有效提高网络节点的能量利用效率，从而延长了网络生命周期。下一步研究工作的重点主要是利用压缩感知理论，研究无线传感网中的目标覆盖问题、连通性问题与可靠性问题。

[1] Zhao Qun, Gurusamy M. Lifetime Maximization for Connected Target Coverage in Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking, 2008, 16(6): 1378-1391.

[2] Liao Zhuofan, Zhang Shigeng, Cao Jiannong, et al. Minimizing Movement for Target Coverage in Mobile Sensor Networks[C]// Proc. of the 32nd International Conference on Distributed Computing Systems Workshops. Macau, China: [s. n.], 2012: 194-200.

[3] Kim C, Kim Y, Kang I, et al. A Scheduling Algorithm for Connected Target Coverage Under Probabilistic Coverage Model[C]//Proc. of 2012 International Conference on Information Networking. Bali, Indonesia: [s. n.], 2012: 86-91.

[4] 桂小林, 何 欣, 尹 柯. 基于目标覆盖的无线传感器网络的连通性优化部署方法[J]. 小型微型计算机系统, 2011, 32(9): 1821-1826.

[5] 孙泽宇, 丁国强, 张永胜. 基于能量有效WSN优化覆盖算法的研究[J]. 计算机应用研究, 2011, 28(6): 2261-2264.

[6] 毕晓君, 董 超, 王鹏宇. 基于免疫算法的有向传感器网络目标覆盖研究[J]. 计算机工程, 2011, 37(24): 83-85.

[7] 向 辉, 彭 力, 闻继伟. 高效节能的视觉传感器网络目标覆盖算法[J]. 计算机工程, 2012, 38(16): 113-116.

[8] Ke W, Liu B, Tsai M. Efficient Algorithm for Constructing Minimum Size Wireless Sensor Networks to Fully Cover Critical Square Grids[J]. IEEE Transactions on Wireless Com- munications, 2011, 10(4): 1154-1164.

[9] Capone A, Cesana M, Donno D, et al. Deploying Multiple Interconnected Gateways in Heterogeneous Wireless Sensor Networks: An Optimization Approach[J]. Computer Com- munications, 2010, 33(10): 1151-1161.

[10] Shu T, Krunz M. Coverage-time Optimization for Clustered Wireless Sensor Networks: A Power-balancing Approach[J]. IEEE/ACM Transactions on Networks, 2010, 18(1): 202-215.

[11] Torshizi E S, Yousefi S, Bagherzadeh J, et al. Life Time Maximization for Connected Target Coverage in Wireless Sensor Networks with Sink Mobility[C]//Proc. of the 6th International Symposium on Telecommunications. Manchester, UK: [s. n.], 2012: 743-748.

[12] 贾 杰, 陈 剑, 常桂然, 等. 无线传感器网络中最优覆盖节点集的求解算法[J]. 东北大学学报: 自然科学版, 2007, 28(11): 1560-1563.

编辑 金胡考

Multi-class Target Coverage Algorithm Based on Linear Programming in Wireless Sensor Networks

YU Guang-zhou

(Network and Educational Technology Center, Guangdong Ocean University, Zhanjiang 524025, China)

The multi-class target coverage problem is currently research hot in Wireless Sensor Networks(WSN). Aiming at the disadvantage of the existing target coverage algorithms, the multi-class target coverage problem is modeled as a maximization lifetime problem based on the Linear Programming(LP). This paper proposes a target coverage algorithm based on the clustering. According to the residual energy and sensing capability of nodes, the global coverage set is obtained on the basis of solving optimal solution within the each cluster structure, which is close to the optimal solution, moreover, the algorithm dispatches the corresponding sensing module to cover the target of having the same attributes within its sensing range. Experimental results show that the performance of this algorithm is superior to the CWGC algorithms in terms of the lifetime of network and time efficiency, close to the optimal value of LP.

Wireless Sensor Networks(WSN); target coverage; Linear Programming(LP); clustering; optimal solution; lifetime of network

1000-3428(2014)03-0152-06

A

TP393

于广州(1981－)，男，实验师、硕士，主研方向：无线传感器网络，神经网络。

2012-12-20

2013-04-08 E-mail：1552327495@qq.com

10.3969/j.issn.1000-3428.2014.03.031