FCM-DAFSA的无线传感器网络多目标跟踪节点任务分配方法

王艳春，尚晓丽，李 会

(1.齐齐哈尔大学通信与电子工程学院，黑龙江 齐齐哈尔 161006;2.绥化大学计算机学院，黑龙江 绥化 152061)

1 引言

无线传感器网络WSN(Wireless Sensor Networks)多目标跟踪节点任务分配是研究如何选择和分配传感器节点构成多个监测联盟进行协同工作，以实现对多个目标的高性能跟踪[1]。其核心问题是根据WSN多目标跟踪的主要性能指标，建立相应的目标函数，通过优化目标函数，确定工作的传感器节点及工作模式，从而达到任务分配的目的。

在近期的多目标跟踪节点任务分配中，文献[2]等采用目标误差协方差矩阵的迹、均方根误差、最大信息增量作为指标构建目标函数，目的是提高跟踪精度。文献[3]利用基本粒子群算法，将粒子群算法离散化后，直接应用于节点任务分配，效果一般。文献[4]选择距离目标最近的三个传感器节点组合对目标定位跟踪，该方法适用于单体目标跟踪，对于节点随机分布和通信能耗问题没有多加考虑。文献[5]提出集中式任务分配的信号处理方式，该方法探测联盟相对固定，容易出现探测联盟能量消耗过大导致网络瘫痪的情况。文献[6,7]综合考虑目标跟踪准确度和网络能耗，根据节点空间相关性构造能耗函数进行节点优化。文献[8]采用最小能量准则建立目标函数，以弹性神经网络实现对多目标节点任务进行优化分配，由于系统能耗降低过大，导致任务分配时间较长。

本文利用离散人工鱼群算法结合模糊C均值聚类，对WSN多目标跟踪节点任务分配进行仿真实验；该方法首先利用类间距阈值的模糊C均值聚类算法，估计监测区域可能出现的目标数量和目标位置；再根据目标函数改进了基本人工鱼群算法，使得该方法更适合对目标函数进行快速优化；最后根据任务分配的目标函数，使用改进的离散人工鱼群算法优化目标函数，得到任务分配方案。实验结果表明，同最近邻法、MEM(Multiple Elastic Modules)[9]、粒子群算法比较，该方法综合性能比较优越。

2 WSN多目标跟踪节点任务分配数学描述及目标函数

WSN多目标跟踪节点任务分配是一个资源分配满足不同约束的过程，不同时刻任务的分配可能不同，所以具有一定的动态性[10]。当对多个目标进行跟踪时，要对多个目标一一建立其监测联盟。存在的问题是，当被跟踪的目标距离比较近的时候可能发生资源争夺，在这种情况下，必须调整分配方案，分配关键性的节点资源以合适任务，从而达到优化的目的。因为任务分配具有动态性，任务分配算法必须在不同的时刻根据跟踪的目标调整分配方案。当跟踪目标出现时，任务节点把自己探测到的信息传给汇聚节点，汇聚节点构建目标监测数据矩阵，再根据任务分配算法选择目标监测联盟，确定盟主，由盟主对监测到的数据进行预处理并且进行状态预测，并把结果传送到汇聚节点。当跟踪目标离开当前联盟的范围时，由汇聚节点根据各目标下一时刻的预测状态和任务分配算法，选择合适节点组成新的监测联盟继续进行检测。

2.1 数学描述

假设监测区域均匀随机分布N个传感器节点，M个被跟踪目标，N≥3M，保证每个目标周围至少有三个节点可以探测到目标。在T0时刻，用bmn(m=1,2,3,…,M;n=1,2,3,…,N)表示第n个WSN节点能否观测到第m个目标，bmn=1表示第n个WSN节点能观测到第m个目标，否则bmn=0。则WSN节点监测目标的情况可用如下监测数据矩阵来描述：

(1)

用Cm={sm1,sm2,sm3}(m=1,2,3,…,M)表示第m个目标的监测联盟，smi(i=1,2,3)为联盟内节点，M个目标需要建立M个联盟集合：Ω={C1,C2,C3,…,CM}，用amn=1 (m=1,2,3,…,M;n=1,2,3,…,N)表示第n个WSN节点加入第m个监测联盟来监测第m个目标，否则amn=0。M个目标的任务分配矩阵描述如下：

(2)

同时，A矩阵中的元素还应该满足：

(3)

节点任务分配就是要确定任务分配矩阵A中每个元素amn的值。式(2)、式(3)构成了WSN多目标跟踪节点任务分配问题数学模型。

2.2 目标函数

为了提高目标跟踪系统的总体性能，节点任务分配要保证跟踪精度，同时尽量降低网络能耗。通信能耗主要由发送能耗ETx和数据接收能耗ERx两部分组成，是距离d的函数。监测M个目标的通信能耗模型可表示为：

(4)

其中，dmn表示监测节点n与被监测目标m之间的欧氏距离，dn1n2表示联盟内任意两个节点n1、n2之间的欧氏距离。

为了提高跟踪精度，要求节点与目标之间的距离之和尽量小，即：

(5)

综合考虑，节点任务分配目标函数为：

E=α1E1+α2E2

(6)

其中，α1、α2为权重值，且有：α1,α2∈[0,1]；α1+α2=1。

任务分配就是根据给定的α1和α2值，求得式(6)的最小值，从而得到联盟的组合。

3 WSN基于类间距阈值的FCM算法

WSN基于类间距阈值的模糊C均值FCM(Fuzzy C-Means)算法实现步骤：

(2)设监测数据集合X={x1,x2,x3,…,xN}，聚类中心集合V={v1,v2,v3,…,vC}，数据xi(i=1,2,…,N)对vk(k=1,2,…,C)的隶属度uik，U={uik}(i=1,2,…,N;k=1,2,…,C)，设定模糊权重因子β，那么WSN监测数据zk(k=1,2,…,C)与聚类中心vk(k=1,2,…,C)的带权距离平方和为：

(7)

得到数据集最佳划分满足式(8)：

(8)

通过迭代运算，调整聚类中心，计算对各类中心的隶属度，估算出节点目标位置，此时目标函数达到较小值。

4 基于FCM-DAFSA的节点任务分配

人工鱼群算法是一种新型的基于集群智能优化算法[11]。其思想是：在鱼生活的水域中，鱼往往能自行或尾随其它鱼找到食物多的地方。人工鱼群算法就是根据这一特点，通过模拟鱼群的行为动作，结合动物自制体模式，来对问题进行优化。基本人工鱼群算法AFSA(Artificial Fish Swarm Algorithm)针对连续问题进行求解，而WSN多目标跟踪节点任务分配问题是一个离散问题[12]。因此，必须对该算法及相关个体鱼的行为重新进行定义。

4.1 离散人工鱼群算法DAFSA(Discrete Artificial Fish Swarm Algorithm)原理

定义个体鱼位状态X，即X={x1,x2,…,xn}，其中xi∈{0,1}(i=1,2,…,n)为寻优变量；人工鱼当前位置的食物浓度为Y=f(X)，Y表示目标函数值；个体鱼之间的距离d2ij为Xi与Xj的海明距离；Visual表示感知范围，Step表示个体鱼的运动步长，取值均为整数；δ表示拥挤度因子。下面简述鱼群的行为[10]:

(1)觅食行为。设第i个人工鱼当前状态为Xi={xi1,xi2,…,xin}，在其视野范围内随机选择一个状态Xj，如果该状态周围的食物浓度大于当前状态时，则向该方向前进一步，使得Xi与Xj的海明距离缩小；如果该状态周围的食物浓度小于当前状态时，则重新在其视野范围内随机选择状态Xj，判断当前状态是否满足前进条件。试探try_number次后，如果仍不满足前进条件，则执行随机行为。

(2)聚群行为。设人工鱼当前状态为Xi，在其可视范围内的同伴的个数为Nf，中心位置为Xc；如果伙伴中心有较多食物且不太拥挤，即YcNf<δYi，则人工鱼Xi向中心位置Xc的方向前进一步，使得Xi与Xc的海明距离缩小；否则执行觅食行为。

(3)追尾行为。设人工鱼在其可视范围内寻找状态最优的邻居，设为Xmax，如果它附近有较高的食物浓度且不太拥挤，则向Xmax的位置前进一步，使得Xi与Xmax的海明距离缩小；否则，执行觅食行为。

(4)随机行为。人工鱼在视野中随机选择一个状态，然后向该方向移动。

(5)行为选择。选择其中的最优者来实际执行，缺省的行为方式为觅食行为。

(6)公告板。记录最优人工鱼个体状态的地方，即为所求的最优值和个体鱼的位置。

4.2 DAFSA的改进

根据个体鱼自适应值与整个鱼群的平均自适应值作比较，将人工鱼群分为三组，并动态调整每组鱼的视野范围和步长。具体实现如下：

Visual=Visual-(Visual-

(9)

其中,Visual_end是预先设定的最小视野范围值。

(3)将适应值Yi次于Yavg的人工鱼分为第三组，动态调整其视野为：

(10)

第一组人工鱼是较优秀的人工鱼，因为已经接近全局最优解，所以赋予较小的视野范围，能够达到强化局部搜索能力的效果；第二组人工鱼为一般人工鱼，将其视野范围固定为某一常数，可以实现在全局搜索和局部搜索之间的平衡；第三组人工鱼为较差的人工鱼，借鉴自适应调整遗传算法控制参数的方法进行调整。k1、k2和Δ为控制参数，若Δ较大，则人工鱼群分布较为分散，Visual较小；算法能够加强局部搜索能力使群体趋于收敛；若Δ较小，则人工鱼群分布较为集中，Visual较大，算法具有较强的全局搜索能力，从而有效地跳出局部极值。

4.3 基于FCM-DAFSA的节点任务分配算法过程

基于FCM-DAFSA的节点任务分配过程如下：

(1)人工鱼群初始化：人工鱼群初始化的数据以WSN目标估计位置为依据，选取与目标估计位置最近三个节点构成初始监测联盟，避免搜索空间过大。定义个体鱼位置X代表一种任务分配方案，即X={X1,X2,…,Xj,…,XM}，1≤j≤M；Xj={xj1,xj2,…,xji,…,xjn}，1≤i≤N。其中xji=1表示第i个节点分配跟踪目标j。初始化Step、Visual、拥挤度因子δ。最大迭代次数Gmax，试探try_number次。

(2)计算目标函数值，找出最小值及其对应的人工鱼个体，并赋给公告板，判断是否满足结束条件，如果满足结束条件，则输出公告板；否则执行(3)；

(4)根据分组情况，利用式(9)、式(10)确定视野范围及步长。

(5)根据情况选择追尾行为、聚群行为、觅食行为、随机行为。

(7)产生新一代人工鱼群，执行(2)。

5 仿真实验与结果分析

5.1 实验环境

软件环境：MATLAB 7.8；操作系统：Windows XP；硬件环境：Intel Core2，CPU主频1.60 GHz，1 GB内存；设在[0,100] m×[0,100] m监测区域内随机均匀布置60个传感器节点，节点可以获得自身位置信息，通讯半径为20 m，监测半径为20 m。

5.2 能耗分析

在实验过程中，以三个目标连续运动20 s的节点任务分配所需能耗进行比较,并假设节点之间传送数据通信量相同，以通信距离作为能耗近似衡量指标。图1是最近邻法、MEM、粒子群算法和FCM-DAFSA在三个目标上的平均能耗比较曲线图。由图1的仿真结果可见，最近邻法的能耗最高，MEM方法次之，粒子群算法再次之，而本文提出的FCM-DAFSA算法能耗最低。四种方法在20 s的平均通信距离分别为139.87 m、154.60 m、160.01 m和162.18 m，本文提出的算法通信距离最大。与其他三种方法比较，FCM-DAFSA算法的能耗平均降低8.61%、5.52%和1.08%。

FCM-DAFSA算法能耗降低的原因在于它把能耗最小化作为节点任务分配目标函数，在改进DAFSA算法中以目标函数作为适应值函数，对基本人工鱼群算法做了较大的改进，使得在寻找目标函数最优值时，能够更快地找到目标函数的最优值，同时将不必要的解滤除掉，从而实现快速节点任务的最优分配。而文献[3]是直接采用了基本粒子群算法，所以要比文本的算法稍差一些。本文的方法能够在原理上确保WSN多目标跟踪节点任务分配低能耗的要求。

Figure 1 Energy consumption curve compared with the nearest neighbor method,MEM method, and particle swarm algorithm图1 与最近邻分配方法、MEM方法、粒子群算法的能耗比较曲线

5.3 分配时间分析

图2是MEM法、粒子群法、FCM-DAFSA法和最近邻法任务分配所需时间比较曲线。在20 s内任务分配平均时间分别为0.338 2 s、0.193 9 s、0.177 3 s和0.082 s。从数据上看，FCM-DAFSA方法的任务分配时间比MEM方法平均减少了19.7%，比粒子群算法平均减少4.21%。

Figure 2 Allocation time curve compared with the nearest neighbor method,MEM method,and particle swarm algorithm图2 与最近邻分配方法、MEM方法、粒子群算法的分配时间比较曲线

最近邻法由于直接选用最靠近目标节点组成监测联盟，几乎不消耗节点分配时间。FCM-DAFSA算法选择与各聚类中心位置最近的三个节点位置作为监测联盟，而MEM法在监测区域内随机产生节点作为监测联盟，所以FCM-DAFSA搜索区域较小，迭代次数也少，因此能缩短任务分配时间。基本粒子群算法任务分配时间比MEM方法也减少较多，这也是因此粒子群算法采用了利用目标函数优化的方法，将不可能的分配方式过早地丢弃掉，因为也能够减少任务的分配时间。但是，本文提出的算法在基本人工鱼群算法上改进较大，因而，算法执行速度比粒子群算法要快，所以，任务分配时间也较少。由此实验可知，利用FCM-DAFSA方法更能满足跟踪系统实时性要求。

5.4 目标跟踪误差分析

表1是选择某一目标进行真实位置与算法测试的位置之间的误差分析。由表1数据可知，最大误差值为2.5 m，平均值为1.65 m，可以满足实际应用的要求。

Table 1 Target tracking error表1 目标的跟踪误差 m

6 结束语

首先，分析了WSN多目标跟踪节点任务分配的国内外学者的工作，根据该研究领域的趋势，提出了自己的研究方法；其次，利用FCM方法对WSN的节点进行聚类，估计出监测区域可能出现的目标数量和目标位置；再次，对人工鱼群算法进行离散化，将离散人工鱼群算法进行了改进，使得该方法能够使用在无线传感器节点任务分配上；最后，将本文方法与最近邻方法、粒子群算法和MEM方法进行比较，从仿真实验结果可以看出，本文方法能够提高WSN的综合性能，也适合实际的应用。

[1] Zhao Feng,Shin J, Reich J. Information-driven dynamic sensor collaboration[J]. Signal Processing Magazine, 2002, 19(2):61-72.

[2] Liu Xian-xing, Zhou Lin, Du Xiao-yu. A method of sensor management based on target priority and information gain[J]. Acta Electronica Sinica, 2005,33(9):1683-1687.(in Chinese)

[3] Liu Mei, Xu Xiao-ling, Huang Dao-ping. Using PSO to realize nodes task allocation of muti-target tracking in WSN[J].Chinese Journal of Sensors and Actuators,2010,23(9):1334-1339.(in Chinese)

[4] Tseng Yu-Chee, Kuo Sheng-po, Lee Hung-wei, et al. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies[J] . Computer Journal, 2004, 47(4):448-460.

[5] Chen Guo-long, Guo Wen-zhong, Chen Yu-zhong. Research on dynamic alliance of task allocation and its algorithm in wireless sensor network[J]. Journal on Communications, 2009,30(11):48-55. (in Chinese)

[6] Shen Yan, Guo Bing, Ding jie-xiong, et al. Energy-efficient dynamic task allocation in wireless sensor networks [J]. Journal of Sichuan University, 2008,40(4):143-147. (in Chinese)

[7] Kang Hui,Li Xiao-lin.Power-aware sensor selection in wireless sensor networks[C]∥Proc of VTC’09,2009:1-5.

[8] Liu Mei,Li Hai-hao,Shen Yi. Research on task allocation technique for aerial target tracking based on wireless sensor network[J]. Journal of Astronautics,2007, 28(4):960- 971. (in Chinese)

[9] Zhao Li-ping. Application of MEM models in locking and tracking multiple random passive targets [J]. Journal of East China University of Science and Technology,2001,27(5):527-532.(in Chinese)

[10] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]∥Proc of the Hawaii International Conference System Sciences, 2000:1.

[11] Wang Chuang.The analysis and improvement of artificial fish-swarm algorithm [D].Dalian:Dalian Maritime University, 2008. (in Chinese)

[12] Eren T, Whiteley W, Belhumeur P N. Further results on sensor network localization using rigidity[C]∥Proc of European Workshop on Wireless Sensor Networks ( EWSN ), 2005:405-409.

附中文参考文献：

[2] 刘先省，周林，杜晓玉.基于目标权重和信息增量的传感器管理方法[J].电子学报,2005,33(9):1683-1687.

[3] 刘美，徐小玲，黄道平.应用粒子群优化分配WSN多目标跟

踪节点任务[J].传感技术学报,2010,23(9):1334-1339.

[5] 陈国龙，郭文忠，陈羽中.无线传感器网络任务分配动态联盟模型与算法研究[J].通信学报,2009,30(11):48-55.

[6] 沈艳，郭兵，丁杰雄,等.无线传感器网络节能动态任务分配[J].四川大学学报,2008,40(4):143-147.

[8] 刘梅，李海昊，沈毅.无线传感器网络空中目标跟踪任务分配技术的研究[J].宇航学报, 2007, 28(4):960-971.

[9] 赵莉萍. MEM模型在多传感器多目标无源定位与跟踪中的应用[J].华东理工大学学报,2001,27(5):527-532.

[11] 王闯.人工鱼群算法的分析及改进[D].大连：大连海事大学，2008.