异构传感器网络多目标多重覆盖策略

罗 旭 柴 利 杨 君



异构传感器网络多目标多重覆盖策略

罗 旭 柴 利*杨 君

(武汉科技大学冶金自动化与检测技术教育部工程研究中心 武汉 430081)

在传感器网络环境监测应用中，常存在多种监测对象。此类应用中，每个异构网络节点搭配不同类型的传感器，要求网络部署可多重覆盖监测区以监测各个子对象。针对节点随机分布的传感器网络，该文提出一种平均子网寿命模型以评价网络中某子对象的监测寿命。在给定成本预算与各子对象的基本覆盖率需求下，采用一种基于整数向量规划的多目标多重覆盖算法权衡成本、网络覆盖性能以及网络中不同子对象的监测寿命。该算法分两部分，首先确定监测不同子对象的传感器数量，然后基于平均子网寿命模型，确定不同类型的异构节点数量。针对向量规划问题，文中给出两种不同次优解法。在仿真实验部分，将不同次优解法进行了对比，并分析了算法计算复杂度。仿真示例验证了该文的覆盖算法在多对象监测应用中的有效性。

传感器网络；多对象监测；平均子网寿命；向量规划；异构节点

1 引言

覆盖问题是传感器网络中的基础研究问题之一，一直以来都是研究热点[1,2]。覆盖性能常作为传感器网络部署效果的主要参考指标[2]，合理覆盖策略的主要目的是为了提高网络的感知能力[3]，达到预定的节点覆盖率，面积覆盖率，侦测能力[4]或其它覆盖目标。为了延长网络寿命，覆盖策略常考虑网络能耗[5,6]。按照网络监测对象的动静态类型划分，覆盖问题可分为针对静态环境的网络覆盖问题和针对动态事件的网络覆盖问题[4]。在节点随机分布的传感器网络静态监测应用中，面积覆盖率由于具有显式评价模型，常作为覆盖性能评价标准。

在许多监测应用中，监测区内常存在多种监测对象。例如，水环境监测中需监测水域温度，盐度，酸碱值等，工厂污染预警需监测多种化学扩散物。由于目前采用的传感器节点硬件成本较高，多对象监测应用中，每个节点装配多种不同类型的传感器，即节点异构。当节点能量一定时，携带的传感器越多，节点寿命越短。在多对象监测网络覆盖部署中有两个重要问题需考虑，即如何以较小的网络成本投入获得理想的网络覆盖性能，以及如何根据不同子对象的重要性权衡网络中不同子对象的监测寿命。

综合考虑分布在监测区域内监测某子对象的各节点工作寿命，本文提出一种子网寿命模型，并以平均子网寿命评价某子对象的监测寿命。在给定不同子对象的面积覆盖率基本需求与网络成本预算的情况下，针对节点随机分布的传感器网络多对象监测应用中的多重覆盖部署，本文提出了一种基于整数向量规划的多目标多重覆盖算法，并给出了相应解法。本文提出的多目标多重覆盖策略可同时解决异构传感器网络多对象监测应用中的投入成本与各子对象覆盖性能之间的权衡问题，以及网络中不同子对象的监测寿命权衡问题。

针对多对象监测应用中的多重覆盖策略研究，本文的主要贡献为：

(1)提出多目标多重覆盖算法，该算法分为两个部分，首先以网络成本与各子对象有效面积覆盖率为目标建立整数向量规划模型，确定监测不同子对象的传感器数目，权衡网络投入成本与不同子对象的覆盖性能。而后，已知监测不同子对象的传感器数目，以各子对象平均子网寿命为目标建立整数向量规划模型，搭配异构网络节点，确定相应异构节点数目，权衡不同子对象的监测寿命。

(2)针对提出的向量规划问题，给出有效次优解法，并给出算法复杂度分析。

(3)通过仿真示例验证了本文所提多目标多重覆盖算法的有效性，比较了不同次优解法的仿真性能，并分析了算法的求解复杂度。

2 基本知识与问题描述

为了具体描述问题，本文首先引入如下记号：

2.1相关定义与假设

假设2 单个节点最大能量供给为定值，节点寿命与其携带的传感器数量成反比。

假设3 每个节点至少装配1个传感器，且监测某子对象的传感器仅携带1个。

2.2 问题描述

传感器总成本目标 传感器投入成本最小：

有效覆盖率目标 投入的传感器个数越多面积覆盖率越大，有效覆盖率目标等价为

传感器数量约束 基于式(9)模型解得的不同类型传感器的投入个数，列出传感器数量约束：

3 多目标规划次优解法

3.1 基本次优解法

(1)偏差评价：

3.2 加速次优解法

4 覆盖策略求解全流程

5 仿真示例

令子网寿命：

依据式(10)，式(11)，列出约束条件如式(25)：

对比上述示例结果如表1，有如下推断：(1)从表1目标值栏可看出，尽管加速次优求解可减少有效变量个数，降低问题复杂度，但可能使得最小化问题的最优目标值变大。(2)对比情况1，情况2下的各子对象平均子网寿命，平方评价相比于偏差评价，增大了高权值对象的权重，即增大了对象的平均子网寿命。

表1方案对比

目标值平均子网寿命评价方式 ABCD 情况10.52000.47470.45370.43590.5625偏差评价 0.27190.47470.47220.43590.5208平方评价 情况20.53560.55560.37960.33330.5625偏差评价 0.29410.54040.41670.33330.4792平方评价

从表2可知，二次整数规划，在相同的模型复杂度下，其求解复杂度要远远高于线性规划；有效变量个数的减少可缩短规划解求取时间。

表2计算复杂度对比

变量个数偏差评价计算时间(s)平方评价计算时间(s) 情况1102340.733015517.5513 情况296828.165615314.9287 情况384820.14654928.4693 情况463810.63574138.7291

6 结束语

在节点异构的传感器网络多对象监测应用中，评价某子对象的监测寿命，提出平均子网寿命模型。为了权衡投入成本与各子对象的覆盖性能，以及权衡网络中不同子对象的监测寿命，本文在相关约束下提出的基于整数向量规划的多目标多重覆盖算法分为两部分，首先确定监测不同子对象的传感器数量，然后确定不同类型的异构节点数量。文中给出了向量规划问题的次优解法，仿真示例部分表明本文的异构传感器网络多目标多重覆盖策略适用于多对象监测。

[1] Karl H and Willig A. Protocols and Architectures for Wireless Sensor Network[M]. New York: John Wiley & Sons, 2005: 316-328.

[2] 刘丽萍, 王智, 孙优贤. 无线传感器网络部署及其覆盖问题研究[J]. 电子与信息学报, 2006, 28(9): 1752-1757.

Liu Li-ping, Wang Zhi, and Sun You-xian. Survey on coverage in wireless sensor networks deployment[J].&, 2006, 28(9): 1752-1757.

[3] Tan R. Exploiting data fusion to improve the coverage of wireless sensor networks[J]./, 2012, 20(2): 450-462.

[4] Liu B and Towsley D. A study of the coverage of large-scale sensor networks[C]. Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Florida, 2004: 475-483.

[5] Aziz N A, Mohemmed A W, Alias M Y,. Coverage maximization and energy conservation for mobile wireless sensor networks: a two phase particle swarm optimization algorithm[C]. Proceedings of Sixth International Conference on Bio-Inspired Computing: Theories and Applications, Penang, 2011: 64-69.

[6] Huang C F and Tseng Y C. The coverage problem in a wireless sensor network[J]., 2005, 10(4): 519-528.

[7] Wang Q, Yan W J, and Shen Y.-person card game approach for solving SET-COVER problem in wireless sensor networks[J]., 2012, 61(5): 1522-1535.

[8] Ashouri M, Zali Z, Mousavi S R,. New optimal solutions to disjoint set-coverage for lifetime extension in wireless sensor networks[J].,2012, 2(1): 31-39.

[9] Ammari H M and Das S K. A study of-coverage and measures of connectivity in 3D wireless sensor network[J]., 2010, 59(2): 243-257.

[10] Chakrabarty K, Lyengar S S, and Qi H R. Grid coverage for surveillance and target location in distributed sensor networks[J]., 2002, 51(12): 1448-1453.

[11] Cohon J L. Multiobjective Programming and Planning[M]. North Chelmsford: Courier Dover Publications, 2004: 17-200.

[12] Gass S I. Linear Programming: Methods and Applications [M]. North Chelmsford: Courier Dover Publications, 2010: 249-280.

[13] 郭亚军. 线性无量纲化的方法的性质分析[OL]. http://www. docin.com/p-186656653.html, 2013.5.

Guo Ya-jun. Character analysis of linear dimensionless methods[OL]. http://www.docin.com/p-186656653.html, 2013. 5.

[14] 陈志平, 卻峰. 求解中大规模复杂凸二次整数规划问题的新型分枝定界算法[J]. 计算数学, 2004, 26(4): 445-458.

Cheng Zhi-ping and Que Feng. A new branch-and-bound algorithm for solving large complex integer convex quadratic programs[J]., 2004, 26(4): 445-458.

罗 旭： 男，1986年生，博士生，研究方向为无线传感器网络.

柴 利： 男，1972年生，博士生导师，研究方向为控制理论应用、信号处理与无线通信等.

杨 君： 女，1977年生，副教授，研究方向为无线传感器网络、无线通信等.

Multi-objective Strategy of Multiple Coverage in Heterogeneous Sensor Networks

Luo Xu Chai Li Yang Jun

(,,,430081,)

In environmental monitoring applications, there are often various objects to be monitored by sensor networks. In this scenario, each heterogeneous node carries some different sensors, and the coverage of multiple areas is required in order to monitor every different subobject. In sensor networks with random distributed nodes, an average subnet lifetime model is proposed to evaluate the average lifetime of nodes sensing one subobject. Given the constraints of cost budget and area coverage of different objects, a multi-objective multi-coverage algorithm based on integer vector programming is proposed to balance the cost and coverage performance, as well as the monitoring life of different subobjects. The algorithm is divided into two steps. The first step is to compute the number of each type of sensors used to monitor one subobject, and the second step is to determine the number of different kinds of heterogeneous nodes based on the average subnet life model. To solve the proposed vector programming issues, two suboptimal methods are given. In the simulation experiments, different suboptimal methods are compared, and the computational complexity of the proposed algorithm is analysed. Simulation examples verify the effectiveness of the proposed algorithm in the multi-objects monitoring applications.

Sensor network; Multi-objects monitoring; Average subnets life; Vector programming; Heterogeneous nodes

TP393

A

1009-5896(2014)03-0690-06

10.3724/SP.J.1146.2013.00667

2013-05-13收到，2013-07-29改回

国家自然科学基金(60974012, 61171160)资助课题

柴利 chaili@wust.edu.cn