无线传感器网络多目标跟踪中协同任务分配

文莎，蔡自兴，刘丽珏，任孝平

(中南大学 信息科学与工程学院，湖南 长沙，410083)

摘要：采用动态联盟机制进行多目标跟踪协同任务分配，并对自组织动态联盟进行研究，重点探讨盟员选择机制；分析能量消耗情况，给出改进的能耗模型；介绍三点定位法原理，分析其定位精度，提出基于面积和法以限制节点选择，建立精度模型。将能耗模型与精度模型结合，构造出综合性能指标函数，指导盟员的选择，并运用遗传算法实现此选择。仿真试验结果表明：综合性能指标函数使能耗和精度2个指标都更趋优化，证明了运用遗传算法进行盟员选择的有效性。

关键词：无线传感器网络；多目标跟踪；协同任务分配；动态联盟；综合性能指标函数

中图分类号：TP393          文献标志码：A         文章编号：1672-7207(2012)08-3031-08

Cooperative task allocation for multi-target tracking in wireless sensor networks

WEN Sha, CAI Zi-xing, LIU Li-jue, REN Xiao-ping

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: Dynamic clusters mechanism was adopted to carry out cooperative task allocation for multi-target tracking, the self-organization process of dynamic clusters was discoursed, and cluster members selection mechanism was described. The situation of energy consumption was analyzed, and the improved energy consumption model was given; then the principle of three-point location was introduced, the location accuracy, the area-sum method to restrict the selection of nodes was proposed, and location accuracy model was constructed. Combining the energy consumption model and the location accuracy model, the comprehensive performance index function was created to guide the selection of cluster members, and genetic algorithm was used to implement the selection of cluster members. The simulation results show that the comprehensive performance index function makes both the energy consumption and location accuracy more optimal, and the results indicate the validity of using genetic algorithm to implement the selection of cluster members.

Key words: wireless sensor networks; multi-target tracking; cooperative task allocation; dynamic clusters; comprehensive performance index function

近年来，随着嵌入式系统、微传感技术以及无线通信技术的发展，无线传感器网络(WSN)在民用和军事领域得到广泛的应用^[1]。而目标跟踪作为无线传感器网络的热点研究领域，一直备受关注^[2]。在现有的无线传感器网络协同跟踪移动目标的任务分配研究成果中，Tseng等^[3]只针对跟踪1个目标和传感器呈特殊的等边三角形分布的情形，没有考虑存在多目标和传感器随机分布的情形以及能量消耗的因素。Kaplan^[4]虽然考虑能耗因素，但是也没有考虑多目标跟踪任务和资源竞争冲突问题。Zhu等^[5]考虑传感器节点随机分布情形，也考虑了多目标跟踪任务，但只试图使系统能耗最低，没有考虑精度因素。由此可知，WSN目标跟踪技术仍不完善，有许多内容亟待研究。本文采用动态联盟机制^[6-7]进行协同任务分配，除考虑系统能耗外，还考虑定位精度，提出兼顾能耗和精度的综合性能指标函数^[8]，对目标跟踪系统进行建模。并运用遗传算法，以综合性能指标函数为目标函数指导搜索，实现动态联盟中盟主盟员的选择，最终实现各指标平衡、综合性能优化的协同任务分配。

1  动态联盟协同任务分配机制

采用动态联盟机制^[6-7]进行任务分配，动态联盟机制执行过程可用形式化语言描述如下：

(1) 当目标T从感知区域以外进入到感知区域内部时，原则上选出第一个感测到它的节点作为盟主H^[9]，H立即广播消息“Coming Target”, 唤醒其通信范围内的邻节点。

(2) 设为被唤醒的N个节点构成的集合，各节点根据任务信息和自身当前状态给出回复信息，盟主根据回复信息选取一定数量的节点作为盟员，构成盟员集合 。此盟员集合与盟主H一起构成1个动态联盟。

在第2步中，盟主如何选取一定数量的节点，构成盟员集合，即为本文的研究重点——动态联盟自组织算法^[2]。假设：1个动态联盟需要3个传感器节点组成。考虑到传感器节点的能力限制，1个节点只能加入1个动态联盟实现对1个目标的跟踪。当监视区域内有多个目标时，需要多个动态联盟，这时，不同的联盟也许选中同样的节点作为其成员，即会产生节点资源竞争冲突的现象^[10]。在这种情况下，必须优化分配关键性的节点给合适的联盟，如果关键资源无策略地随机分配，其结果可能会导致网络总性能降低。

2  能耗模型

以文献[10]的模型为基础，根据节点能量消耗情况，结合具体定位法，给出本文的网络能耗模型。

节点的能量消耗一般由感应、数据处理、节点间的通信3方面构成^[10]。其中，占能量消耗主体的是节点间的通信，而通信能耗主要取决于通信距离。因此，控制通信距离能有效地节约网络能量。

设有M个目标：T₁，T₂，…，T_m，…，T_M，因此有M个盟主：H₁，H₂，…，H_m，…，H_M。任取1个目标T_m为例(1≤m≤M)，它的盟主节点是H_m，被唤醒的节点是(共N个)。d_mn为盟主节点H_m与被唤醒节点(1≤n≤N)之间的距离；α_mn为指示数，当α_mn=1时，盟主H_m选择被唤醒节点作为联盟成员；当α_mn=0时，盟主H_m不选择被唤醒节点作联盟成员。

为使网络的总通信能耗最少，任务分配须有如下目标函数：

            (1)

约束条件如下。

(1) 1个传感器节点只能加入1个联盟，或者休眠。可解决跟踪多目标时节点资源竞争冲突问题。

；n=1，2，…，N

(2) 1个盟主需要选择2个节点作为联盟成员。保证了每个联盟由3个节点组成。

；m=1，2，…，M

(3) 所有α_mn之和应满足如下条件，以保证每个目标都得到分配。

；m=1，2，…，M；n=1，2，…，N

3  精度模型

3.1  三点定位法及定位精度分析

本文采用三点定位法^[11]对目标进行定位。三点定位法计算简单、需要已知坐标的节点数目少，适应于传感器节点计算和存储能力有限的特点。其基本原理为：已知节点A，B，C的位置以及它们与目标的距离，以3个节点为圆心，以它们到目标的距离为半径画圆，若测量精确，3个圆应该交于1个点，则点就是目标的估计位置。但是，由于测量存在误差，3个圆产生重叠区域，如图1所示。这时，任意2圆的交点可定义1条直线，其中任两条直线的交点就作为目标的估计位置。图1中点P为最后确定的目标估计位置。

三点定位法是一种基于测距技术的定位^[12]，而它的定位精度除与节点到目标的距离有关外，还与3个节点相对目标的位置有关，即在一定的距离范围内，3个节点把目标包围在它们组成的三角形之内时，定位精度更高^[13]。可通过仿真试验来证明此结论。

取目标估计位置与实际位置的距离为定位误差：

          (2)

图1  三点定位法原理示意图

Fig.1  Principle of three-point location

不妨给出如图2所示的试验场景，取目标T的坐标(x₀，y₀)为(0,0)，盟主H的坐标(x₁，y₁)为(4,7)，2个盟员的初始位置是和盟主无限接近的(三点距离几乎为0)，2个盟员各沿着2条直线向下移动，3个节点间距离(简称节点间距)越来越大，并慢慢将目标围在其中，直至终点a′，b′。

以节点间距为横坐标，定位误差为纵坐标，可得结果如图3所示。由图3可见：随着节点间距由0渐渐增大，3个节点渐渐将目标包围，误差不断减小。当2节点移动到a*和b*时(对应节点间距为5.145 6)，定位误差最小。2节点再继续向下移动，3个节点距目标的距离已较远了，此时，由于测量数据随距离增加受到的干扰增大，准确度降低，定位误差又开始增大。可见：在一定的距离范围内，限定3节点将目标围住，确实能减小定位误差，提高定位精度。

3.2  基于面积和法的节点选择

本节的节点选择即选取3个节点将目标包围在其中(目标在3点确定的三角形内)。如图4所示，若ΔPAB，ΔPAC和ΔPBC的面积之和与ΔABC的面积相等，则可判定点P在ΔABC内(包括在3条边上的情况)。

图2  试验场景

Fig.2  Experimental scene

图3  定位误差与节点位置的关系

Fig.3  Relationship between location error and position of nodes

图4  面积和法示意图

Fig.4  Schematic diagram of Area-sum Method

设(x_A，y_A)，(x_B，y_B)和(x_C，y_C)分别为3顶点A，B和C的坐标，ΔABC的面积可用下式计算：

       (3)

因此，面积和法可表示为：

(4)

令：

  (5)

则当δ=0时，点P在ΔABC内；当δ＞0时，点P不在ΔABC内，且δ越大，点P离ΔABC越远。若δ无限接近于0，即δ=0，则盟员选择的精度指标为：

 (M为目标个数)       (6)

4  协同任务分配模型

4.1  盟员选择规则

综合以上对能耗和精度的分析，可总结出盟员选择的一般规则。

节点相对于目标的位置如图5所示，H为已选定的盟主， (各边长4次方之和)是所有选择中最小的，然而a，b和H在目标的同一侧，没有包围目标，此时定位精度较低。对于节点c和d，虽稍大于，但H，c和d不在目标的同一侧，而是将目标围在3个节点组成的三角形之内，尽管此时c和d点距盟主的距离更远，但定位精度却更高。综合考虑能耗与精度的情况下，应选择节点c和d，而不选择节点a和b。即在图5中，

(1) 若与相当，或略大于，则选择c和d作盟员；

(2) 若远大于，则选择a和b作盟员。因为当很大时，不但通信能耗大，且测距误差大了，导致定位误差也增大，故不能选择c和d，仍然选择a和b较好。

图5  节点相对于目标的位置

Fig.5  Node Location to target

4.2  综合性能指标函数

将能耗指标与精度指标进行加权，从而得到综合性能指标函数。设：

             (7)

                 (8)

综合性能指标目标函数为：

0≤α₁≤1，0≤α₂≤1            (9)

其中：α₁和α₂分别为J₁和J₂的权重，调节权重可达到最佳的跟踪效果。在实际应用中，也可根据能耗或精度的偏重，通过调节权重，达到应用要求。

5  仿真试验分析

盟主盟员的选择是一个寻找最优解的过程。采用遗传算法来实现此寻优过程，并在MATLAB中对多目标跟踪和盟主盟员选择过程进行仿真。

5.1  仿真参数设置

取100个采样时刻，2个随机运动的目标，运动场地长×宽为100 m×100 m的矩形场地，共随机分布256个节点。

遗传算法中，设初始种群个体(即染色体)数为100个，迭代次数为100代。每个节点采用8个2进制位编码，那么每条染色体(个体)有32个2进制位。设交叉概率为0.9，变异概率为0.01。

5.2  仿真结果及分析

图6~9所示分别为仅考虑能耗、仅考虑精度及综合考虑能耗和精度3种情况下的跟踪轨迹图、定位误差图、各代联盟能量消耗图、遗传操作中每代最优适应值变化图。在计算各代联盟消耗的能量时，各节点消耗的能量计算公式参见文献[10]。

综合考虑能耗和精度时，由试验可得：α₁取0.6，α₂取0.4，β取10，跟踪效果最佳，且在能耗与定位精度上取得较好的平衡。

比较图6可知：不使用面积和法约束时，目标估测轨迹不光滑，某些估测点偏离实际点较远，可认为是错误点，跟踪效果较差；运用面积和法后，跟踪效果有很大提高，而加权(图6(c2))又比硬性约束 (图6(b2))的跟踪效果更好。比较图6(b1)和(c1)可见：图6(b1)中的盟员比较发散，尤其是在运动轨迹的尾部，主要原因就在于硬性约束3个节点将目标围住使得选择过程中可能舍弃较近的不能围住目标的点，而选择远很多的能围住目标的点。在这种情况下，目标的定位精度不但没有加大，反而减小，这也可从图7(b)和7(c)看出。

在图6中，出现了1个节点有2个联盟选中的标记“ ”和“” ，这不是这个节点同一时刻被2个联盟选中，而是在不同的时刻，被2个联盟分别选中。由表1和2可知：跟踪目标0的联盟(简称联盟0)在第30时刻选中节点(21.523，37.3078)，而联盟1在第15时刻又选中这个节点。此外，联盟0在第32时刻选中节点(46.4622，44.6903)，联盟1在第22时刻也选中这个节点。

图6  盟主盟员选择及目标轨迹图

Fig.6  Selection of cluster head and member and tracks of targets

比较图7中的3个子图，不使用面积和法约束时，定位误差较大；使用面积和法后，定位误差明显减小，而加权(图7(c))又比硬性约束(图7(b))的误差更小。这一规律与图6所示的轨迹图规律相符。

图7  目标0定位误差

Fig.7  Location error for target 0

图8所示是任选某一时刻(本文选定第100时刻)各代联盟能量消耗图，即进化的每一代中，具有最大适应值的染色体对应的4个节点作盟员，与各自的盟主组成联盟，传感器网络消耗的总能量。从图8可见：经过遗传操作选出来的盟员，所对应的联盟消耗的能量越来越小，而且减小量非常显著，大大减小了网络能耗，证明综合性能指标函数的合理性，及用遗传算法进行盟员选择的有效性。

表1  不同联盟的盟员(目标0)

Table 1  Members of different clusters (target 0)

图8  第100时刻各代联盟消耗能量图

Fig.8  Energy consumption of every generation of cluster at 100th time

图9  第30和60时刻每代最优适应值变化图

Fig.9  Change of every generation of best adaptive value at 30th and 60th time

同样，比较图8中的3个子图可知：图8(a)中由于不使用面积和法的限制，只考虑使节点间距4次方最小时，所消耗的能量非常少(不超过2.5×10⁵ J)。而将面积和法作为1个硬性约束条件时，能耗大大增加(几乎达到15×10⁵ J)，是前者的6倍多。加权形式(图8(c)是较好的折中形式，虽然能耗与不使用面积和法时的相比有所增加，但比硬性约束时减少很多。这一规律也与图6和图7所示的规律一致。可见：将“3个节点将目标围住”作为1个子目标函数，与能耗指标进行加权，构造出综合性能指标函数，指导盟员的选择，能达到既减小能耗又提高精度的目的，从而证明了本文综合性能指标函数设定的合理性。

表2  不同联盟的盟员(目标1)

Table 2  Members of different clusters (target 1)

图9所示是任选2个时刻(第30和60时刻)，在3种情况下遗传操作中每代最优适应值的变化图。从图9可见：随着进化代数的增加，每代的最优适应值都呈上升趋势，直至找到最优的4个节点，此时最优适应值达到最大，并不再上升。这一规律与图7中各代联盟消耗能量逐渐减少的规律相符，进一步证明了运用遗传算法选择盟员的有效性，也证明了仿真中所选得盟员的正确性和最优性。

6  结论

(1) 采用动态联盟机制进行协同任务分配，论述了自组织动态联盟。分析能量消耗情况，建立能耗模型；介绍了3点定位法原理，分析了定位精度，建立精度模型。在此基础上，将能耗模型与精度模型结合，构造出综合性能指标函数，指导盟员的选择。最后，运用遗传算法实现了盟员选择。

(2) 在进一步研究工作中，可采用不同的定位法，研究如何建立更合理的精度模型，且进一步优化能耗模型，以获得更好的网络综合性能。

参考文献：

[1] CUI Li, JU Hai-ling, MIAO Yong, et al. Research development of wireless sensor networks[J]. Journal of Computer Research and Development, 2005, 42: 11-13.

[2] 王永才. 传感器网络目标跟踪系统协同设计理论研究与应用[D]. 北京: 清华大学自动化系, 2006: 1-5, 24-31.
WANG Yong-cai. Cooperative design of wireless sensor network target tracking system: A theoretical study and applications[D]. Beijing: Tsinghua University. Department of Automation, 2006: 1-5, 24-31.

[3] Tseng Y C, Kuo S P, Lee H W, et al. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies[J]. The Computer Journal, 2004, 47(4): 448-460.

[4] Kaplan L M. Transmission range control during autonomous node selection for wireless sensor networks[C]//2004 IEEE Aerospace Conference Proceedings, 2004: 2072-2087.

[5] ZHU Jing-hua, GAO Hong. An energy efficient algorithm for task allocation in wireless sensor networks[J]. Journal of Software, 2007, 18(5): 1198-1207.

[6] 陈剑霞, 臧传治, 梁韡, 等. 无线传感器网络动态协同任务分配机制[J]. 信息与控制, 2006, 35(2): 189-199.
CHEN Jian-xia, ZANG Chuan-zhi, LIANG Wei, et al. A dynamic task allocation scheme for wireless sensor networks[J]. Information and Control, 2006, 35(2): 189-199.

[7] 陈剑霞. 基于动态联盟机制的无线传感器网络任务分配问题研究[D]. 沈阳: 中国科学院沈阳自动化研究所, 2009: 88-98.
CHEN Jian-xia. Research on task allocation in wireless sensor networks based on dynamic coalition mechanism[D]. Shenyang: Shenyang Institute of Automation Chinese Academy of Sciences, 2009: 88-98.

[8] 王睿, 梁彦, 潘泉, 等. 无线传感器网络信息感知中的自组织算法[J]. 自动化学报, 2006(5): 829-833.
WANG Rui, LIANG Yan, PAN Quan, et al. A self-organization algorithm in wireless sensor net-works[J]. Acta Automatica Sinica, 2006(5): 829-833.

[9] Baek J, An S K, Fisher P. Dynamic cluster header selection and conditional re-clustering for wireless sensor networks[J]. Consumer Electronics, IEEE Transactions on, 2010, 56(4): 2249-2257.

[10] LI Hai-hao, LIU Mei, SHEN Yi, et al. Research on task allocation technique for multi-target tracking in wireless sensor network[C]//Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation, 2007: 360-365.

[11] 孙利明. 无线传感器网络[M]. 北京: 清华大学出版社, 2005: 393-394.
SUN Li-ming. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005: 393-394.

[12] He T, Huang C D, Blum B M, et al. Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proc of the 9th Annual Int’l Conf on Mobile Computing and Networking. San Diego: ACM Press, 2003: 81-95.

[13] 文莎. 无线传感器网络多目标智能跟踪算法研究[D]. 广州: 广东工业大学自动化学院, 2010: 20-31.
WEN Sha. Multi-target intelligent tracking algorithm in wireless sensor network[D]. Guangzhou: Guangdong University of Technology. School of Automation, 2010: 20-31.

(编辑 邓履翔)

收稿日期：2011-08-29；修回日期：2011-10-29

基金项目：国家教育部博士点基金资助项目(200805330005)；湖南省科技计划项目(2010FJ4029)

通信作者：刘丽珏(1973-)，女，湖南长沙人，博士，副教授，从事无线传感器定位技术研究；电话：15973113084；E-mail：wensha0103@163.com