通信受限下分布式多传感器协同跟踪算法*

赵 猛，左 燕，李明地，郭宝峰

（杭州电子科技大学通信信息传输与融合技术国防重点学科实验室，杭州 310018）

通信受限下分布式多传感器协同跟踪算法*

赵 猛，左 燕，李明地，郭宝峰

（杭州电子科技大学通信信息传输与融合技术国防重点学科实验室，杭州 310018）

在分布式多传感器目标跟踪系统中，由于局部融合中心（LFC）的物理限制（如：有限的频率信道、处理器容量有限等），只能接收有限个传感器的传送数据。此外，信息传输的方式也将影响传感网的使用寿命，因此，研究了通信受限下的分布式多传感器目标协同跟踪问题。首先对监视区内分布的传感器进行聚类分簇形成若干个子网，接着从通信能耗的角度出发，对传感器采集信息的传递路径进行最优路径规划；进而对子网局部状态进行估计，在子网信息融合中，分别采用最大距离和、最大化信息增量两种准则进行最佳传感器选择，最后通过各子网全局航迹融合实现分布式多传感器协同跟踪。仿真验证了算法的有效性。

分布式，通信受限，最短路径规划，聚类分簇，航迹融合

0 引言

利用空间分布的多个传感器（雷达、红外、激光测距仪、声呐等）来协同跟踪目标是未来网络化作战的特点［1］。在网络化协同跟踪系统中，地域分散的多个传感器协同工作，获得目标的精确运动。在多传感网信息融合系统中，集中式与分布式融合结构是最基本和最重要的两种结构。目前，关于集中式融合结构的相关理论已经比较成熟。基于此，从分布式的角度来考虑传感器组网协同跟踪问题是必然的。

在多源信息融合系统中，传感器管理是必然要考虑的问题。传感器资源的相对不足，目标环境机动性增强，不确定性增加，这些都加剧了传感器对目标的有效分配难度［2］。当多个传感器同时用于多个目标的检测、跟踪和识别时，必须解决传感器与目标之间以及检测、跟踪和识别之间的资源调度问题，也就是如何在一定条件下，合理充分利用传感器资源且满足系统最优性能的要求。在分布式多传感器跟踪系统中，由于局部融合中心（LFC）的物理限制（如：有限的频率信道、处理器容量有限等），只能接收有限个传感器的传送数据［3］。因此，在由大量传感器组成的传感器网络中，必须要考虑传感器的选择问题。目前，国内外关于传感器管理的方法主要有：协方差、信息论、规划论以及智能方法［4］。而在诸多传感器管理方法中，既具有科学性又具有可行性的方法应当建立在信息论与规划论基础之上，这类方法对一般的传感器管理才更具有普遍意义。所以，本文传感器选择算法是基于信息增益和距离和的方法；另外需要考虑的一个问题就是传感器的使用寿命，影响传感器使用寿命的因素有很多，而很重要的一个原因就是传感器的通信能耗。因此，本文从信息传输方式的角度出发，进行最优传输路径规划，进而达到减少能耗，延长传感器使用寿命的目的。

1 问题描述

1.1 聚类分簇

本文考虑的是大量传感器，将监视区域内的传感器聚类分簇并进行分布式处理，这不仅有助于降低系统的通信负担，也能提高系统的容错性［5］。本文采用C均值算法进行聚类分簇，将所给的随机传感器聚类分成k簇，其中k值的大小根据最小化误差平方和Je（k）获得［6］。具体的算法步骤如下：

①初始根据经验分为k1个聚类，选择前k1个传感器作为初始聚类的核心；

②根据距核心距离最小原则将其余的样本划分到各初始类中；

1.2 LFC选定

在分布式结构中，局部中心（LFC）个数有给定和随变两种。本文选择的是LFC个数随变即有几个簇就有几个LFC，相比个数给定的优点是能够根据环境的实时性做出调整，节约资源。对于每个子网中LFC的选定原则是Di最小。用到如下公式：

式中，Di表示第i个子网的平均距离，Ni表示第i个子网中传感器个数，Xi，j表示第i个子网第j个传感器的位置，Xi，ni表示第i个子网中选定的局部融合中心传感器ni的位置。

1.3 能耗模型及处理算法

传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块4部分组成。传感器模块负责监视区域内信息采集和数据转换；处理器模块负责控制整个传感器节点的操作，存储和处理本身采集数据以及其他节点发来的数据；无线通信模块负责与其他传感器节点进行无线通信，交换控制消息和收发采集数据；能量供应模块为传感器节点提供所需的能量［7］。这些模块中，通信模块耗能最高，它通常由通信双方节点的位置和传输时间决定。通信模块为一阶系统，传感器发送r bit数据到距离d所耗的能量为：

式中，eie是发射电路能耗，εa为功率放大能耗，rimax为该传感器的最大通信距离，r为要发送的bit数据。相应地，传感器接收r bit数据所耗的能量为：

式中，ere是接收电路能耗。通信模块的参数通常采 用 的 设 置 如 下 ：eie=50 nJ/bit，εa=100 pJ/m2/bit，ere=50 nJ/bit。

由式（1）可知，信息传递能耗随着两个传感器间距离的增加而急剧上升，即相距较远的两个传感器进行直接通信比多跳通信能耗大，所以采用多跳路径理论上可以有效地节约能量。所以对每个子网中传感器向LFC的传递路径进行最优路径规划，在这里采用的是Dijkstra算法获得［8］。该方法是图论中寻求最优路径的有效方法，可求每簇中LFC到各传感器的最短路径即最低能耗路径。关于Dijkstra的算法步骤如下：

①初始化。设置权值矩阵W，考虑传感器的通信范围，超过通信的最大值代价设为+∞。将起始点设置为已标记点visit，其他所有点设为未标记点；

②计算所有已标记的点visit到其直接连接且未标记的点j的距离，并记录，其中，lkj是从点k到点j的直接连接距离；

④找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，并记录i=j*；

⑤标记点i。如果所有点均已标记，则算法完成。

2 子网传感器选择

2.1 基于最大距离和的传感器管理算法

由信息融合理论可知，为了获得更高的跟踪精度，往往可以采取选择更多传感器参与目标跟踪的方法来实现。但是每个LFC能够处理数据的能力是有限的，因此，要对每个子网中所采用的传感器进行选择。在已有的认识中可知，对于每个传感器而言，距离目标近的传感器测得的精度总是要相对高的。因此，对每个子网中要选择的传感器采用的代价函数是最大距离和，即所选择的传感器到LFC的距离和最大，公式如下：

Di表示第i个子网的平均距离，Ni表示第i个子网中传感器个数，Xi，j表示第i个子网第j个传感器的位置，Xi，ni表示第i个子网中选定的局部融合中心传感器的位置。

2.2 基于最大信息增量的传感器管理算法

根据信息论的观点，传感器探测的目的就是与目标环境相互作用以减少目标环境的不确定性。传感器选择的任务是产生一个合理的传感器使用序列尽可能在每一次观测中最大程度获取信息［9］。对于目标跟踪而言，通过改善已跟踪目标的跟踪精度能够产生信息增量，而信息增量由跟踪目标状态向量的不确定性决定。这种不确定性可以用信息熵来定量描述，通过一个测量行为执行前后信息熵的减少可以求得信息增量，然后根据使信息增量最大的准则能够对传感器资源进行科学合理的分配。

Shannon认为某个事件的信息可以用发生概率倒数描述。假设事件中每一种情况i（i=1，…，n）出现的概率为pi，则信息熵描述为：

若有一离散有限集合T，其状态t（t=0，…，T）互斥，其中 q（t）、p（t）都是关于状态 t的概率密度函数，区别在于两者分别表示量测前和量测后，则用先验信息熵减去后验信息熵来定义的信息增量可描述为：

其中 r表述某一正数，当 p（t）=q（t）时，表示本次测量没有带来新的信息，当 p（t）≠q（t）时，表示本次测量带来了新的信息。

假设随机变量x的概率密度分布p（x）可描述为：

则信息增量可以定义为量测前后信息熵之差：

其中，P（k|k）和 P（k|k-1）可由滤波算法得出。在传感器管理中，通过计算目标状态在前后第k次观测前后的熵，然后计算得到信息增量I，最大化I完成传感器的选择。

3 分布式航迹融合

本文共同噪声和共同先验估计误差均忽略，只考虑局部节点的估计状态及方差且相互独立，并且不考虑全局节点的先验估计与方差。在此前提条件下，凸组合融合算法的效果是最优的［10-11］。因此，从LFC到中心融合节点的航迹融合，本文采用的是凸组合融合算法。

根据文献［4］可知，分布式融合系统中的航迹融合方程如下：

4 仿真

假设监视区域内随机分布着20个传感器，每个传感器都可以被当成局部融合中心（LFC）来处理其他传感器传来的数据，但是其所接受的最大传感器数目是6，另外每个传感器的量测噪声协方差也是不同的，而目标采用是CV模型，并且是单目标。仿真结果，每簇以最大化距离和代价函数进行局部状态估计，进而给出全局跟踪状态估计如图1，以及最大化信息增量为代价函数的跟踪效果如图2，均方根误差（RMSE）如图3，聚类分簇及局部融合中心（LFC）选择图 4。

图1 基于最大距离和跟踪效果

图2 基于最大化信息增量跟踪效果

图3 跟踪均方根误差值（RMSE）

由上图的仿真结果可以看出，跟踪效果很好接近于重合，产生这种结果的原因主要是对目标跟踪的传感器很多。由信息论可知，传感器越多，跟踪的精度越高。另外，由RMSE图分析，可以看出两种代价函数的跟踪效果差不多。但事实上，基于距离和为代价函数实际上的可行性并不高，首先是因为计算量太大；其次，牵扯到目标运动模型未知时，此种算法跟踪精度太低。

5 总结与展望

本文给出了一种通信受限情况下的分布式多传感器目标跟踪算法，并且从减少能耗提高传感器使用寿命的角度给出了最短路径规划。本文针对分布式多传感器目标跟踪问题给出了一种结构框架即分簇、子网融合、全局融合；给出了两种代价函数即最大化距离和以及最大化信息增量。从单目标的仿真效果来看，证明了其有效性。因此，考虑到实际应用，多目标动态传感器跟踪问题可以在此基础上进一步探索。

［1］刘先省，申石磊，潘泉.传感器管理及方法综述［J］.电子学报，2002，30（3）：394-398.

［2］罗开平，姜维，李一军.传感器管理评述［J］.电子学报，2010，38（8）：1900-1907.

［3］THARMARASA R，KIRUBARAJAN T，SINHA A，et al.Decentralized sensor selection for large-scale multisensor-multitarget tracking［J］.In IEEE Transactions on Aerospace and Electronic Systems，2011，47（2）：1307-1324.

［4］刘先省.传感器管理方法研究［D］.西安：西北工业大学，2000.

［5］唐东明.聚类分析及其应用研究［D］.成都：电子科技大学，2010.

［6］杨德刚.基于模糊C均值聚类的网络入侵检测算法［J］.计算机科学,2005，31（1）：86-87，91.

［7］刘钦.多传感器组网协同跟踪方法研究［D］.西安：西安电子科技大学，2013.

［8］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14（7）：1282-1291.

［9］李学明，李海瑞，薛亮，等.基于信息增益与信息熵的TFIDF 算法［J］.计算机工程，2012，38（8）：37-40.

［10］刘卫东,刘洋，高立娥.基于凸组合和Bar-Shalom-Campo的航迹融合算法研究［J］.计算机工程与应用，2014，51（2）：49-53.

［11］李洋，杜立夫，禹春梅.一种基于复合模型的机动目标跟踪算法［J］.四川兵工学报，2015，36（5）：127-132.

Distributed Multi-sensor Target Collaborative Tracking Algorithm under Communication Constraints

ZHAO Meng，ZUO Yan，LI Ming-di，GUO Bao-feng
（Institute of Information and Control，Hangzhou Dianzi University，Hangzhou 310018，China）

In a distributed multi-sensor target tracking system，the physical limitation of the local fusion center（LFC）（limited frequency channel，limited processor capacity）is considered，which can only receive the transmission data of a finite number of sensors.In addition，the way of information transmission will affect the service life of the sensor network，so this paper studies the distributed multi-sensor target tracking problem under communication constraints.In this paper，the distributed sensors in the monitoring area are firstly combined to a number of sub-networks，and then the optimal transmission path of sensor data is determined by minimizing the communication consumption costs.Moreover the local state of each sub-network is estimated.In the local fusion center，the sensor is selected based on the maximum distance and the maximum information increment.Finally the multisensor collaborative tracking is implemented by the global track fusion.Simulation results show the effectiveness of the proposed algorithm.

distributed，limited communication，shortest path planning，cluster，track fusion

TN953；E96

：A

10.3969/j.issn.1002-0640.2017.06.002

2016-05-08

：2016-06-09

国家自然科学基金（61004119，61174024，61375011）；浙江省自然科技基金资助项目（LY16F030009）

赵 猛（1990- ），男，河南息县人，硕士研究生。研究方向：目标跟踪和传感器资源管理。

1002-0640（2017）06-0006-04