论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

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

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

　　Minimumenergymobilestrategyofmobilesensornetworksin3Dscene

　　WuYuefei，XuXianghua

　　（CollegeofComputerScienceandTechnology，HangzhouDianziUniversity，ZhejiangProvincialKeyLabofDataStorageandTransmissionTechnology，Hangzhou，Zhejiang310037，China）

　　Abstract：Combinedwiththeenergyconsumptionmodelandthesight-probabilisticsensormodelofmobilesensornetworksin3Dscene，theminimummobileenergyconsumptioninmobilesensornetworksaftermeetingthetargetcoveragerequirementsisstudied.Theexhaustivemethod，greedyalgorithmandsimulatedannealingalgorithmareanalyzedfortherespectiveadvantagesanddisadvantages.Thesimulationresultsshowthattheapproximateoptimalsolutioncanbeobtainedwithinanacceptabletime.

　　Keywords：mobilesensornetwork；sightsensingmodel；probabilisticsensingmodel；3Dscene

　　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问题。当传感网络更为复杂，如一个目标可以同时被多个传感器共同检测时，最优解的求解也会变得更加复杂。

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

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

　　2.2.1穷举法

　　穷举法会穷举出所有可行解，并通过比较，得出能耗最小的解。我们也可以对它进行剪枝：如果目前搜索得到的部分解，其能耗不可能低于当前的最优解，则不再继续搜索这个部分解，而是直接跳过它，重新搜索其他解。

　　2.2.2贪心算法

　　贪心算法在求解的每个阶段，都会选择当前的局部最优解。但是它不会从全局最优进行考虑，因此不能保证能得出全局最优解。贪心算法的步骤为：①从所有未使用的传感器和待检测的目标中挑选出一对满足覆盖条件时，移动能耗最小的传感器与目标，令这个传感器检测选中的目标；②重复步骤①，直到所有目标都被覆盖。

　　2.2.3模拟退火算法

　　模拟退火算法类似于固体退火的原理，当温度逐渐降低时，解也逐渐趋于稳定，最终得出一个近似最优的可行解。模拟退火算法的步骤为：①初始化一个足够大的温度Temp，从原问题状态S得到初始解状态S0，每个Temp值的迭代次数L；②对k=1，2…，L，执行步骤③到⑤；③产生新解S1，并计算新解的能耗变化t=E（S，S1）-E（S，S0）；④若t<0则接受S1为新的当前解，否则以概率e-t/Temp接受S1为新的当前解；⑤若连续COUNT个新解都没有被接受，则输出当前解，并结束算法，否则执行步骤⑥；⑥逐渐减少Temp，返回步骤②。

　　3实验

　　3.1实验参数

　　实验中，移动传感网络模型中的参数如表1所示，模拟退火算法的参数如表2所示，地理信息及传感器与目标的数目如表3所示。模拟退火算法的结果是执行20次之后的统计值。

　　3.2移动能耗

　　实验结果如表4所示。穷举法可以得到最优解。贪心算法会得到局部最优解。模拟退火算法所得出的平均结果介于穷举法和贪心算法之间。

　　3.3算法耗时

　　传感器与目标的个数增大时，直接求解算法耗时相当巨大，因此，不将其与另外两种算法进行比较。贪心算法和模拟退火算法的进一步比较如表5所示，时间消耗的单位为秒。分析可知，随着问题规模增大，贪心算法的耗时不会显著增加，但模拟退火算法的耗时会逐渐增加。

　　4结束语

　　本文提出了移动传感网络中，考虑了许多如检测距离、视线遮挡、地形起伏等因素时，整个传感网络的移动能耗模型。研究了在满足目标检测要求的同时，最小化传感网络总能耗的问题。我们分析了解决该问题的多种方法，并通过模拟实验对比了这些方法的优缺点。

　　本文的研究还存在一些不足之处。从建模的角度，我们可以在模型中加入信号传播等因素，使模型更加丰满；从算法的角度，还有许多可以选用的搜索算法，它们或许能得出更加优秀的结果。并且，以本文为基础，未来可以进一步研究包括异构传感器、多重目标覆盖等问题。

　　参考文献（References）：

　　[1]CarterB，RagadeR.Aprobabilisticmodelforthe

　　deploymentofsensors[C]，2009：7-12

　　[2]QianqianY，ShiboH，JunkunL，etal.Energy-Efficient

　　ProbabilisticAreaCoverageinWirelessSensorNetworks[J].VehicularTechnology，IEEETransactionson，2015.64（1）：367-377

　　[3]AkbarzadehV，GagneC，ParizeauM，etal.Probabilistic

　　SensingModelforSensorPlacementOptimizationBasedonLine-of-SightCoverage[J].InstrumentationandMeasurement，IEEETransactionson，2013.62（2）：293-303

　　[4]LiaoZ，WangJ，ZhangS，etal.MinimizingMovementfor

　　TargetCoverageandNetworkConnectivityinMobileSensorNetworks[C]，2014：1

　　[5]YongguoM，Yung-HsiangL，HuYC，etal.Deployment

　　StrategyforMobileRobotswithEnergyandTimingConstraints[C]，2005：2816-2821

　　[6]YiZ，ChakrabartyK.DistributedMobilityManagementfor

　　TargetTrackinginMobileSensorNetworks[J].MobileComputing，IEEETransactionson，2007.6（8）：872-887