面向目标跟踪的物联网感知层节点部署优化研究

吕立新　阮进军

摘 要：针对目标跟踪物联网感知层节点动态部署的特点，在人工鱼群算法和虚拟力算法的基础上，设计了融入虚拟力影响的人工鱼群控制算法，给出了算法的参数自适应调整策略，该算法利用节点间的虚拟力来影响人工鱼的觅食行为和追尾行为，指导人工鱼群的进化过程，加快算法的收敛性。仿真实验结果显示，算法能快速有效地实现无线传感器网络节点的部署优化，与人工鱼群算法和虚拟力算法相比，该算法不仅全局寻优能力强，且收敛速度快，可有效提高网络覆盖率，优化网络性能。

关键词：物联网；感知层节点；虚拟力；人工鱼群算法；部署策略

Abstract：This paper proposes a virtual force-directed artificial fish swarm algorithm， and applied this algorithm to Sensor Layer nodes deployment of Target tracking IOT. In this algorithm， the virtual force influence the foraging behavior and rear-end behavior of artificial fish， direct the moving and updating status of artificial fish for improving the convergence speed. Simulation results show that virtual force-directed artificial fish swarm algorithm has better performance on regional convergence and global searching ability than virtual force algorithm and artificial fish swarm algorithm， and it can implement dynamic sensor nodes deployment efficiently and rapidly.

Key words：Internet of things；Sensor Layer Node；Virtual Force；Artificial fish-swarm algorithm；Deployment strategy

1 引言

物联网（The Internet of things）是利用现代通信技术把传感器、人员和物体等通过新的方式联在一起，形成信息化、智能化的一种网络，从结构上可分为感知层、网络层、中间层和应用层四层。感知层是连接物理世界和信息世界的桥梁，是整个物联网的底层，它将各种设备上的传感器通过有线或无线的方式连接起来形成一个信息采集与控制的网络，并把采集到的信息传递给物联网的上层。在面向目标跟踪的物联网应用中（如生态环境监测、战场环境侦察等），要求对于在监测区域内沿着任意路径运动的目标都能被感知层节点发现，由于目标的跟踪必须由多个节点协同工作来完成，这就要求感知层节点部署必须有较高的覆盖率和良好的节点通信，同时在目标跟踪的过程中，还要根据目标的位置和重要程度自动调整网络节点的布局，以优化目标跟踪效果。因此，设计有效的感知层节点部署控制算法，根据监测区域合理动态地实现感知层节点的部署，提高无线传感器网络覆盖率和目标检测概率，同时降低网络耗能，最大化地延长网络寿命，是物联网在目标跟踪领域应用首先要解决的重要问题。

文献[1]通过在固定节点中加入移动节点的方法，使用遗传算法来进行节点的部署优化，虽然遗传算法有较强的全局搜索能力，但在最优解附近收敛速度较慢，无法满足节点部署的实时性要求。文献[2]中Howard等人首度将场势理论应用于传感器网络的覆盖控制，通过假设的虚拟势场和虚拟受力，使用物理学中的受力平衡定律来指导网络节点的动态部署。文献[3-4]将群智能算法应用到传感器节点的部署优化中，提出了一种基于粒子群算法的节点部署算法，但粒子群算法在空间搜索时容易过早收敛，使优化结果达不到要求，同时粒子群算法无法实现在节点部署的过程中对监测区域中的障碍物自动避让和根据跟踪目标的重要程度自动调整网络布局的能力。

针对虚拟力算法、遗传算法、粒子群算法在感知层节点部署控制中的不足，本文提出了一种利用虚拟力来指导人工鱼的觅食行为和随机行为来加快算法的收敛速度的节点部署控制算法，同时利用传感器节点与热区和障碍物之间的虚拟力来实现对热点区域的重点监测和对障碍物的有效规避。针对人工鱼群寻优精度底的问题，在算法中采取了自适应参数修正的方法，使算法能自动识别优化过程中的不同阶段，能根据寻优的不同阶段自动修正人工鱼的移动步长，从而提高算法的寻优精度。

2 感知层节点部署问题描述

针对目标跟踪物联网的节点部署特点，将移动节点放置在由固定节点随机部署的网络中，利用移动节点的可移动性，对网络中的节点部署作一定范围的动态调整，用来改善网络的覆盖率和通信连通的目的。在实现高质量的区域覆盖和通信连通性要求的同时，通过移动节点的可移动性来实现对重点监测区域的监测和对监测区域中的障碍物进行有效避让。

设在目标监测区域所部署的所有感知层节点的集合为S={Si，i=1，2，，…，n}，其中移动节点的个数为k，固定节点数为n-k，设网络当前状态下所有节点的位置向量为Z=[Xk，Xn-k，Yk，Yn-k]，其中Xk={x1，x2，…xk}为移动节点的横坐标向量，Yk={y1，y2，…yk}为移动节点的纵坐标向量；Xn-k={xk+1，xk+2，…xn}和Yn-k={yk+1，yk+2，…yn}为固定节点的横、纵坐标向量。感知层节点的感知模型采用文献[5]中的改进概率感知模型（I-PSM），节点S对目标T的感知概率P（s，t）可描述为：

其中d（s，t）为节点与目标之间的距离为，r为节点的感知半径， ，λ，β是d（s，t）在r-re与r+re环状范围内变化时传感器的感应衰减系数。感知层节点的覆盖率采用文献[6]提出的联合覆盖率：

其中Scov-t为同时监测目标T的节点集合，P（si，t）满足式（1），是传感器节点Si对目标T的监测概率。在现实应用中通常根据不同的应用需求设定一个目标监测点被监测概率的阈值Pth，当目标的联合监测概率满足式（3）时，认为该目标点被监测。

在考虑点对目标区域的覆盖时，首先把目标监测区域用长度为d的方格离散化，方格的长度d称为离散化的粒度。用每个小方格的中心点来代表这个方格区域，若中心点被覆盖，则表示这个小方格区域便被节点覆盖。假设目标监测区域被离散化为m×n个方格区域，每个方格是否被传感器节点覆盖，根据方格中心点的联合监测概率来衡量，则无线传感器网络的区域覆盖率可用式4来表示：

面向目标跟踪的物联网感知层节点部署优化问题可抽象为以Z为输入向量，以式（4）为目标函，求f（Z）最大极值问题。

3 虚拟力导向的人工鱼群算法设计

3.1 虚拟力算法

虚拟力算法（Target Involved Virtual Force Algorithm，TIVFA）[7]，通过计算传感器节点之间、传感器与重点探测区域以及传感器与障碍物之间的虚拟力，为各节点寻找受力平衡，引导结点移动到新位置，从而实现传感器网络节点的部署优化。考虑到节点间的通信距离存在上限的情况，在虚拟力模型中引入通信门限Cth，用于控制不能相互通信节点间的虚拟力，即当两节点间的距离大于通信门限时节点间的作用为力零，基于上述假设传感器节点j对节点i的虚拟力模型如式（5）所示：

其中：Fij表示节点i对节点j的作用力；dij为两节点间的直线距离；θij为节点i到节点j的方位角；Wa，Wr分别表示虚拟力的引力系数和斥力系数，用于调节虚拟力算法布局后节点的疏密程度。

在节点部署过程中，一旦综合受力计算完毕，节点将根据综合受力的大小和方向移动到一个新的位置。假设节点单步移动的最大距离为MaxStep，节点每次移动的距离与所受合力的大小正相关且不超过MaxStep。计算公式如式6和式7所示：

其中： 分别表示传感器节点在x轴方向和y轴方向上的移动步长；Fxy为节点受到的虚拟力合力；Fx和Fy分别是节点在x轴方向和y轴方向上所受的分力；Fth是一个常量代表节点受力所预设的门限值，当某个节点的合力小于Fth时，表示该节点已达到一个稳定状态，该节点不需再移动，当所有节点均不移动时，整个网络就达到了稳定状态。

3.2 虚拟力导向下的人工鱼群算法

人工鱼群算法（artificial fish-swarm algorithm，AfSA）[8]是一种基于模拟鱼群行为的优化算法，通过鱼群中各个体的觅食、聚群和追尾行行为进行解空间的搜索，具有良好的全局极值搜索能力。设鱼群的规模为m，第i条人工鱼个体的状态向量Xi由传感器网络中所有移动节点的位置向量构成，即 Xi={xi1，xi2，…，xik，yi1，yi2，…，yik}，其中（xij，yij）（j=1，2，…，k）即表示传感器网络中的第j个移动节点的坐标。人工鱼个体xi和xj间的距离定义为向量间的欧氏距离，即 ，人工鱼的感知距离用Visual表示，人工鱼移动的步长用Step表示，δ为鱼群的拥挤度因子。

在虚拟力导向鱼群算法中人工鱼的觅食行为可定义为：假定人工鱼的当前状态为Xi，在 范围内，随机地选择一个状态Xj，如果f（Xj）大于f（Xi），则按式（8）更新自己的状态，否则重新随机选择状态Xj，再次判断是否满足上述条件，反复尝试一定次数后，如果仍不满足前进条件，则按（9）式随机移动一步。

其中：c1和c2为可调整的权重系数，分别表示鱼群算法和虚拟力算法在虚拟导向鱼群算法中的影响程度。

人工鱼的聚群行为可描述为：假定人工鱼的当前状态为Xi，在其可感知的范围内有nf个人工鱼，则形成一个鱼群集合 ，如果 ，且鱼群中心的食物浓度f（Xc），满足 表示鱼群中心有较多的食物，则人工鱼由按式10更新自己的状态，向鱼群中心位置前进一步，否则，人工鱼执行觅食行为。

人工鱼的追尾行为可描述为：假定人工鱼的当前状态为Xi，在其可感知的范围内的nf个人工鱼中，Xmax状态的人工鱼的食物浓度f（Xmax）最大，如果满足 ，则人工鱼由当前的位置按式11更新自己的状态，向Xmax方向前进一步，否则执行觅食行为。

为了提高算法的全局极值域搜索精度，使用最优值变化率K作为是否进行参数调整的依据，使算法在执行过程中根据极值变化率自适应的调整寻优参数，K的定义如下：

f（t）表示算法演化到第t代时的目标函数值，f（t-n）是第t-n代的目标函数值，n是一个间隔常量，K的意义是算法在演化n代内最优值的相对变化率，当K的值小于某个即定值Kth时，表示算法在n代的计算过程中目标函数值没发生太大的变化，意味着进入满意解域，需要改变人工鱼的移动步长Step和鱼群的拥度因子δ，以提高搜索精度，步长和拥挤度用式13和14进行更新。

其中：α，β分别为步长和拥挤度的缩减因子，本文取α=0.6，β=0.5；Stepmin，δmin为步长和拥挤度的最低门限值。

虚拟力导向鱼群算发的总流程如图1所示

4 仿真实验与分析

假设在一个长度L为100米的正方形区域内部署物联网感知层节点，用于对这一区域中的移动目标进行实时地监测、跟踪。节点总数为100个，其中固定节点50个，移动节点数k=50个，监测区域离散化粒度d为8cm，所有传感器节点的感知半径为r=6m，通信半径R=3r=18m，监测可靠性参数re=0.5r=3，概率监测阈值Pth=0.8；节点的概率感知模型参数分别为λ1=1，λ2=0，β1=1.5，β2=1.0；虚拟力算法参数分别为Wa=1，Wr=5，MaxStep=0.5r=3m，通信门限Cth=R=18m，引力斥力变换门限dth=2r=12m；人工鱼群算法参数为Visual=R=3r=18m，Step=r=6m，δ=0.6，虚拟力导向鱼群算法参数为c1=c2=0.5，最优值变化率间距n=10，最优值变化率门限值Kth=0.05，步长和拥挤度缩小因子分别α=0.6，β=0.5，最小步长和最小拥挤度Stepmin，δmin分别为3m和0.3m。

为了比较虚拟力算法、人工鱼群算法和本文设计的带有自适应策略的虚拟力导向鱼群算法的节点部署优化效果，在随机生成初始化网络部署后，别使用这三种算法对节点部署进行优化，计算迭代次数均为200代，完成200次迭代的计算后在Matlab下编程进行仿真，仿真结果如图2-图5所示。

虚拟力导向鱼群算法迭代至约80代时已经收敛到最优值附近，而虚拟力算法和人工鱼群算法在运算到200代时还未完全收敛。在有效监测面积上虚拟力算法为84.49%，人工鱼群算法为90.48%，带有自适应策略的虚拟力导向鱼群算法为96.83%。从仿真结果上可见，虚拟力导向的鱼群算法的优化效果在网络覆盖率、节点的通信连通性和寻优精度三方面均优于虚拟力算法和人工鱼群算法，而且能实现存在热点区域和障碍区域环境下的节点部署，这是其它2种算法所不能实现的。

5 结束语

本文根据目标跟踪物联网感知层节点的部署特点，设计了一种带有自适应策略的虚拟力导向鱼群算法的节点动态部署策略，该方法利用虚拟力来指导人工鱼的觅食行为和随机行为来加快算法的收敛速度，同时利用传感器节点与热区和障碍物之间的虚拟力来实现对热点区域的重点监测和对障碍物的有效规避，与传统的优化算法相比，该算法收敛速度更快，优化效果更好，为物联网感知层节点的部署问题提供了一种有效的解决方案。

[参考文献]

[1]贾杰，陈剑，常桂然，等.无线传感器网络中基于遗传算法的优化覆盖机制[J].控制与决策，2007，22（11）：1289-1292.

[2]Howard M A，G S Sukhatme.Mobile sensor network deployment using potential Fields：a distributed，scalable solution to the area coverage p roblem[A].Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka：SPR INGER2VERLAG TOKYO，2010.299-308.

[3]Wang X，Wang S，Ma J.Dynamic deployment optimization in wireless sensor networks[J].Lecture Notes in Control and Information Sciences，2006，344：182-187.

[4]王雪，王晟，马俊杰，等.无线传感网络移动节点位置并行微粒群优化策略[J].计算机学报，2007，30（4）：563-568.

[5]S Li，C Xu，W Pan，Y Pan.Sensor Deployment Optimization for Detecting Maneuvering Targets[C].2005 7th International Conference on Information Fusion，2005.1-7.

[6]王雪，王晟，马俊杰.无线传感器网络布局的虚拟力导向微粒群优化策略[J].电子学报，2007，35（11）：2038-2042.

[7]李石坚，徐从富，吴朝晖，等.面向目标跟踪的传感器网络布局优化及保护策略[J].电子学报，2006，34（1）：71-76.

[8]李晓磊.一种新型的智能优化方法一人工鱼群算法：[学位论文].杭州：浙江大学博士论文，2003.1.

为了比较虚拟力算法、人工鱼群算法和本文设计的带有自适应策略的虚拟力导向鱼群算法的节点部署优化效果，在随机生成初始化网络部署后，别使用这三种算法对节点部署进行优化，计算迭代次数均为200代，完成200次迭代的计算后在Matlab下编程进行仿真，仿真结果如图2-图5所示。

虚拟力导向鱼群算法迭代至约80代时已经收敛到最优值附近，而虚拟力算法和人工鱼群算法在运算到200代时还未完全收敛。在有效监测面积上虚拟力算法为84.49%，人工鱼群算法为90.48%，带有自适应策略的虚拟力导向鱼群算法为96.83%。从仿真结果上可见，虚拟力导向的鱼群算法的优化效果在网络覆盖率、节点的通信连通性和寻优精度三方面均优于虚拟力算法和人工鱼群算法，而且能实现存在热点区域和障碍区域环境下的节点部署，这是其它2种算法所不能实现的。

5 结束语

本文根据目标跟踪物联网感知层节点的部署特点，设计了一种带有自适应策略的虚拟力导向鱼群算法的节点动态部署策略，该方法利用虚拟力来指导人工鱼的觅食行为和随机行为来加快算法的收敛速度，同时利用传感器节点与热区和障碍物之间的虚拟力来实现对热点区域的重点监测和对障碍物的有效规避，与传统的优化算法相比，该算法收敛速度更快，优化效果更好，为物联网感知层节点的部署问题提供了一种有效的解决方案。

[参考文献]

[1]贾杰，陈剑，常桂然，等.无线传感器网络中基于遗传算法的优化覆盖机制[J].控制与决策，2007，22（11）：1289-1292.

[2]Howard M A，G S Sukhatme.Mobile sensor network deployment using potential Fields：a distributed，scalable solution to the area coverage p roblem[A].Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka：SPR INGER2VERLAG TOKYO，2010.299-308.

[3]Wang X，Wang S，Ma J.Dynamic deployment optimization in wireless sensor networks[J].Lecture Notes in Control and Information Sciences，2006，344：182-187.

[4]王雪，王晟，马俊杰，等.无线传感网络移动节点位置并行微粒群优化策略[J].计算机学报，2007，30（4）：563-568.

[5]S Li，C Xu，W Pan，Y Pan.Sensor Deployment Optimization for Detecting Maneuvering Targets[C].2005 7th International Conference on Information Fusion，2005.1-7.

[6]王雪，王晟，马俊杰.无线传感器网络布局的虚拟力导向微粒群优化策略[J].电子学报，2007，35（11）：2038-2042.

[7]李石坚，徐从富，吴朝晖，等.面向目标跟踪的传感器网络布局优化及保护策略[J].电子学报，2006，34（1）：71-76.

[8]李晓磊.一种新型的智能优化方法一人工鱼群算法：[学位论文].杭州：浙江大学博士论文，2003.1.

为了比较虚拟力算法、人工鱼群算法和本文设计的带有自适应策略的虚拟力导向鱼群算法的节点部署优化效果，在随机生成初始化网络部署后，别使用这三种算法对节点部署进行优化，计算迭代次数均为200代，完成200次迭代的计算后在Matlab下编程进行仿真，仿真结果如图2-图5所示。

虚拟力导向鱼群算法迭代至约80代时已经收敛到最优值附近，而虚拟力算法和人工鱼群算法在运算到200代时还未完全收敛。在有效监测面积上虚拟力算法为84.49%，人工鱼群算法为90.48%，带有自适应策略的虚拟力导向鱼群算法为96.83%。从仿真结果上可见，虚拟力导向的鱼群算法的优化效果在网络覆盖率、节点的通信连通性和寻优精度三方面均优于虚拟力算法和人工鱼群算法，而且能实现存在热点区域和障碍区域环境下的节点部署，这是其它2种算法所不能实现的。

5 结束语

本文根据目标跟踪物联网感知层节点的部署特点，设计了一种带有自适应策略的虚拟力导向鱼群算法的节点动态部署策略，该方法利用虚拟力来指导人工鱼的觅食行为和随机行为来加快算法的收敛速度，同时利用传感器节点与热区和障碍物之间的虚拟力来实现对热点区域的重点监测和对障碍物的有效规避，与传统的优化算法相比，该算法收敛速度更快，优化效果更好，为物联网感知层节点的部署问题提供了一种有效的解决方案。

[参考文献]

[1]贾杰，陈剑，常桂然，等.无线传感器网络中基于遗传算法的优化覆盖机制[J].控制与决策，2007，22（11）：1289-1292.

[2]Howard M A，G S Sukhatme.Mobile sensor network deployment using potential Fields：a distributed，scalable solution to the area coverage p roblem[A].Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka：SPR INGER2VERLAG TOKYO，2010.299-308.

[3]Wang X，Wang S，Ma J.Dynamic deployment optimization in wireless sensor networks[J].Lecture Notes in Control and Information Sciences，2006，344：182-187.

[4]王雪，王晟，马俊杰，等.无线传感网络移动节点位置并行微粒群优化策略[J].计算机学报，2007，30（4）：563-568.

[5]S Li，C Xu，W Pan，Y Pan.Sensor Deployment Optimization for Detecting Maneuvering Targets[C].2005 7th International Conference on Information Fusion，2005.1-7.

[6]王雪，王晟，马俊杰.无线传感器网络布局的虚拟力导向微粒群优化策略[J].电子学报，2007，35（11）：2038-2042.

[7]李石坚，徐从富，吴朝晖，等.面向目标跟踪的传感器网络布局优化及保护策略[J].电子学报，2006，34（1）：71-76.

[8]李晓磊.一种新型的智能优化方法一人工鱼群算法：[学位论文].杭州：浙江大学博士论文，2003.1.