移动传感网络在3D场景中的最小耗能移动策略

吴月菲+徐向华

DOI：10.16644/j.cnki.cn33-1094/tp.2016.07.003

摘 要： 结合3D场景中移动传感网络的能耗模型和视距概率传感器模型，研究了在满足目标覆盖要求时移动传感网络的最小能耗移动问题，分析了穷举法、贪心算法和模拟退火算法各自的优劣。模拟实验结果表明，近似最优解可以在可接受的时间内得到。

关键词： 移动传感网络； 视距传感模型； 概率传感模型； 3D场景

中图分类号：TP393.0 文献标志码：A 文章编号：1006-8228（2016）07-08-04

Minimum energy mobile strategy of mobile sensor networks in 3D scene

Wu Yuefei， Xu Xianghua

（College of Computer Science and Technology， Hangzhou Dianzi University， Zhejiang Provincial Key Lab of Data Storage and Transmission Technology， Hangzhou， Zhejiang 310037， China）

Abstract： Combined with the energy consumption model and the sight-probabilistic sensor model of mobile sensor networks in 3D scene， the minimum mobile energy consumption in mobile sensor networks after meeting the target coverage requirements is studied. The exhaustive method， greedy algorithm and simulated annealing algorithm are analyzed for the respective advantages and disadvantages. The simulation results show that the approximate optimal solution can be obtained within an acceptable time.

Key words： mobile sensor network； sight sensing model； probabilistic sensing model； 3D scene

0 引言

无线传感网络广泛应用于军事、智能交通、环境监控等多个领域。其中，传感器的能量是一个亟待解决的问题。如果要使无线传感网络的工作时间最大化，就必须减少无线传感网络的能量消耗。虽然，目前已经有很多关于概率传感器的模型[1-3]，但是，考虑实际应用时传感网络产生移动能耗的文章并不多。文献[4-6]研究了移动传感器在二维平面下的移动能耗问题，但是没有考虑到在实际中传感器移动时重力势能的影响。

本文结合视线传感器的探测特性和实际的地理情况，提出了一种在能够保证目标检测要求的同时，使得移动传感网络的总能耗最小的移动方案。

1 问题模型

1.1 问题场景模型

本文研究的问题是，初始给定N个随机部署的可移动的视距概率传感器，移动它们，从而对M个目标进行检测。并且，在保证对目标的检测率不小于预设值θ时，使得移动传感网络的总能耗E最小。

假定，所使用的视线传感器都安装在可移动设备（如履带小车）上，它们距离地面有一定高度zs。我们使用符号Si（xi，yi，zi+zs）表示第i个传感器的信息，其中（xi，yi，zi+zs）为第i个传感器的三维坐标位置。S={S1，S2，…，Sn}表示传感网络中所有传感器的集合。Tj（xj，yj，zj）表示第j个目标的信息，其中（xj，yj，zj）为第T个目标的实际位置。T={T1，T2，...，Tm}表示所有目标的集合。

2 解决方案

2.1 两点间的最小能耗

我们为地理模型建立一张有向加权图：①为每一个数据点建立一个顶点；②为每对相邻的数据点之间添加一对有向边；③每条有向边的权值为从一个数据点移动到另一个数据点的移动能耗。那么，从一个区域移动到另一个区域所需的最小移动能耗问题，就转化为有向加权图中的最短路径的问题。本文使用Dijkstra算法求解这个问题。

2.2 求近似最优解

当整个区域中存在一些目标时，根据式⑸，可以计算出区域中每个数据点对这些目标的检测概率。

若考虑一个目标只被一个传感器检测的情况，由上一小节的计算结果和式⑸所解得的传感器所处位置对目标的检测概率的大小，可以求出传感器Si在保证对目标Tj的检测概率不低于预设值θj时，所需的移动最小能耗MinEij。那么，我们可以得到一个N行M列的能耗矩阵，行列号分别代表传感器和目标的序号。

使用能耗矩阵求解最优解时，需要从n个传感器中选取m个，来分别覆盖m个不同的目标。因此，求解的复杂度为。这是一个无法在多项式时间内得到最优解的NP问题。当传感网络更为复杂，如一个目标可以同时被多个传感器共同检测时，最优解的求解也会变得更加复杂。

因此，在问题规模较小时，本文求出最优解，但当问题规模较大时，则选择求出移动能耗尽量小的近似解。另外，本文只考虑在传感器与目标一一对应时的情况。

本文提出三种求可行解的方案：①穷举所有可行解，得出最优解；②使用贪心算法得出可行解；③使用模拟退火算法求近似解。