第 38 卷 第 3 期 自 动 化 学 报 Vol. 38, No. 3
2012 年 3 月 ACTA AUTOMATICA SINICA March, 2012
移动传感器网络中目标跟踪与监测的同步优化
涂志亮
1
王 强
1
沈 毅
1
摘 要 针对移动传感器网络 (Mobile sensor networks, MSNs) 中动态目标 (事件源) 的监测优化问题, 为提高网络覆盖质
量, 建立基于 Voronoi 剖分的监测性能 (Quality of monitoring, QoM) 评价函数, 提出基于群集控制的传感器节点部署分布式
控制算法. 每个节点在本地结合最小二乘法和一致性算法来估计目标相对位置. 相比传统算法, 本文算法只需本地和单跳通信
(可观测) 邻居的信息, 从而减小通信时长和能耗. 算法在提高以目标为中心的一定区域监测性能的同时, 使全体传感器速度趋
于一致, 从而在尽量保持网络拓扑结构的同时减少了整体移动能耗. 在目标匀速或目标加速度信息全网可知的情况下, 全体传
感器速度渐进收敛到目标速度, 且监测性能收敛至局部最优. 所采用的目标位置估计滤波算法计算简单、切实可行.
关键词 群集控制, 传感器部署, 覆盖优化, 移动传感器网络, Voronoi 剖分
DOI 10.3724/SP.J.1004.2012.00452
A Distributed Simultaneous Optimization Algorithm for Tracking and
Monitoring of Moving Target in Mobile Sensor Networks
TU Zhi-Liang
1
WANG Qiang
1
SHEN Yi
1
Abstract To improve the quality of coverage for the problem of monitoring a moving target (event) in mobile sensor
networks (MSNs), this paper first formulates a monitoring evaluation criterion based on Voronoi partition, then proposes
a distributed flocking based control algorithm. This paper adopts an algorithm which combines the least square method
with the consensus algorithm to estimate the relative position of the target. Compared to traditional methods, only
lo cal and 1-hop (measurable) neighborhood information is required, hence it reduces the communication time and energy
consumption. While optimizing the quality of monitoring (QoM), it also regulates all sensors
0
velocities to the target
velocity, hence the topology of the network is kept better and the total energy consumption on movement of sensors is
reduced. With the assumption that the target is moving at a constant velocity or its acceleration is available to all sensors,
the velocities of all sensors would be asymptotically aligned with the target velocity and QoM would converge to a local
maximum. The estimation algorithm for the relative position to the target is simple and effective.
Key words Flocking control, sensor deployment, coverage optimization, mobile sensor network (MSN), Voronoi parti-
tion
移 动 传 感 器 网 络 (Mobile sensor networks,
MSNs) 是一类由具备移动能力的传感器节点组成
的特殊无线传感器网络, 从而具备感知、计算、通信
和移动能力. 在一些危险场合和动态环境中, 如灾
难现场紧急救援、建筑物内危险品泄漏等, 由于传
统的静态无线传感器网络部署起来将十分困难甚至
失效, 而 MSNs 利用其机动能力能迅速顺利地解决
问题. 同时微机电系统 (Micro-electro-mechanical
systems, MEMS) 的发展也使得结构紧凑、造价低
廉的移动节点成为可能. 因此, MSNs 已引起广泛关
注. 在监测区域内, 针对复杂动态环境, 如何部署移
动节点, 使得 MSNs 有效地覆盖监测区域或目标是
收稿日期 2011-04-13 录用日期 2011-10-08
Manuscript received April 13, 2011; accepted October 8, 2011
国家自然科学基金 (60874054, 61174016) 资助
Supported by National Natural Science Foundation of China
(60874054, 61174016)
本文责任编委 刘成林
Recommended by Associate Editor LIU Cheng-Lin
1. 哈尔滨工业大学航天学院 哈尔滨 150001
1. School of Astronautics, Harbin Institute of Technology,
Harbin 150001
一个重要的研究方向
[1−2]
.
移动传感器网络的初始部署一般采用随机布撒
或者人工部署. 随机布撒方式容易产生覆盖漏洞和
覆盖冗余, 而人工部署应用环境有限, 且难以满足
动态环境的有效监测要求. 因此 MSNs 时常需要自
动调整部署结构以提高监测质量和节省能耗. 目前
解决 MSNs 部署问题的方法主要分为集中式和分
布式两种. 由于集中式算法往往要求网络的全局信
息 (如位置信息) 而应用有限且不适合动态环境
[3]
,
近年来的研究大多集中在分布式算法上. 分布式方
法主要有两类: 基于计算几何法
[4−5]
和基于虚拟力
法
[6−8]
. 基于 Voronoi 图的部署方法是计算几何法
的一个重要方向. Wang 等基于 Voronoi 图提出三
种分布式节点移动方法
[4]
, 实现监测区的无漏洞覆
盖. Cort´es 研究在节点通信半径可调时的覆盖性能
优化算法, 通过 Voronoi 剖分, 得到在性能评价下的
最优配置为节点位于其 Voronoi 剖分的质心处. 在
Cort´es 的工作基础上, Pimenta 等假设节点能获取
所有 Voronoi 邻居的位置信息, 提出针对环境动态变