基于Q学习的多目标耦合协同任务分配算法

柏茂羽 ,　丁　勇,b,　胡忠旺

(南京航空航天大学,a.自动化学院; b.江苏省物联网与控制技术重点实验室,南京　211106)

0　引言

现今的多目标跟踪研究普遍基于无线传感器网络(WSN)[1]，网络中的无线传感器节点具有独立的探测、计算及通信能力，但是由于节点个体存在能量有限、资源有限和计算能力有限的缺陷，传感器节点独立对目标进行跟踪往往无法获得预期的效果[2]。所以，如何有效协调无线传感器网络中的节点，使其具有持续跟踪目标的能力成为一个热门的研究课题[3-4]。现有的WSN协同跟踪普遍采用跟踪目标附近传感器节点开启而其他节点休眠的工作形式，此种方法使得目标附近的节点连接成簇，通过协同工作完成目标信息的采集与传输，所以，如何在保证跟踪精度的前提下尽可能降低网络能量消耗成为了此类研究的关键问题，尤其在多个目标相近或相遇时，如何解决节点的任务分配竞争冲突问题，也是WSN目标跟踪研究的难点。

在当前无线传感器网络多目标协同跟踪研究中，文献[5]基于信息驱动传感器查询算法(Information Driven Sensor Query,IDSQ)提出一种自适应动态协同自组织算法，能根据给定的精度自适应地选择簇首和簇成员，有效控制了任务节点的数量并减少了网络能量消耗，但是该算法没有考虑网络能耗的均衡性问题。文献[6]针对多目标协同跟踪问题提出了基于面积和法限制节点的选择，避免了节点资源竞争冲突问题，并用遗传算法实现动态联盟成员选择，但是算法能耗较大。文献[7]提出了一种能量有效的动态协同自组织算法，该算法设计了更加全面的性能指标函数，并能够根据精度阈值自适应地选取任务节点。由于考虑了剩余能量，有效避免了能耗集中在部分节点而导致节点过早死亡，但算法不适用于节点分布密度高的情况。文献[8]提出了一种融合了模糊聚类的多弹性子模自组织神经网络节点任务分配方法，适用于多目标节点任务分配的竞争冲突中系统能耗增加的问题。算法提高了多目标耦合情况下的跟踪精度，但是神经网络算法增加了计算的复杂度。

针对多目标耦合时节点任务分配竞争冲突的问题，提出了一种多目标协同任务分配算法，在多目标相遇或相近时刻，打破了传统的N个目标必须构建N个簇的思想，优选能够同时探测到多个目标的节点，组成单个簇，负责跟踪耦合状态的多个目标，同时采用Q学习方法，得出最佳的合簇时机，利用兼顾能耗与精度的综合性能指标，确定簇首与簇成员，最终实现多目标跟踪的协同任务分配。

1　Q学习方法

自然启发式算法、博弈论方法和强化学习方法均适用于在协同任务分配中兼顾跟踪精度与能量消耗最优解[9]，本文用到的Q学习是强化学习的一种，其模型如图1所示。

图1　强化学习模型Fig.1　Reinforcement learning model

其原理可以理解为，如果Agent的某个行为策略导致环境对Agent正的奖赏，则Agent以后采取这个策

略的趋势会加强[9-10]。其具体实现步骤是，设环境是一个有限状态的离散马尔可夫过程，每个时刻Agent可在有限行为集合中选取某个行为，环境接受该动作后状态发生转移，同时给出评价[11]。例如，在时刻t选择行为at,环境由状态st转移到st+1，给出评价rt。rt及st+1的概率分布取决于at及st。单步Q学习方法的Q值更新公式为

(1)

式中：α∈[0,1]为学习率；γ∈[0,1]为折扣因子；Qt(st,at)表示在状态st时Agent选择动作at的Q函数值；rt为Agent在t时刻执行动作at的立即奖赏值；A为所有可供选择的动作集合。Watkins证明了在一定条件下，Q学习方法具有收敛性，而且必然收敛到最优解。下文将综合考虑跟踪精度与网络能耗，将Q学习方法运用到无线传感器网络成簇动作的决策中以寻求最优解。

2　基于Q学习的多目标耦合协同任务分配算法

利用成簇机制进行网络节点任务分配的过程[12]可以描述为，当目标T移动到传感器网络内，首个感知到目标信息的节点成为簇首P，通过广播唤醒其通信范围内的相邻节点集Hs={s1,s2,…，sn}，各节点根据任务信息和自身状态给出回复信息，簇首根据回复信息选出簇成员集Hm={sm1,sm2,…,smn}·(Hm∈Hs)。随着目标T的移动，激活目标附近的节点构建新的簇，通过动态成簇跟踪目标。

当多个目标在较小范围内移动时，常会遇到多个目标距离较近的情形(例如在相近时刻的轨迹交叉或轨迹相近等情形，简称为耦合情形)，此时存在节点sc可同时探测到多个目标，不同的簇可能会同时选用节点sc为簇成员，即节点任务分配存在竞争冲突，如不加以处理，节点sc很可能在短时间内被频繁征用，造成网络关键资源的损耗。传统的解决方法是优化分配关键性的节点给合适的簇，避免竞争冲突的出现，但是此种方法遵循的约束条件是一个传感器节点只能分配跟踪定位一个目标[13]，在目标距离很近，如簇H1成员节点的选择集合可以与簇H2重合时，即(H1∈Ho)&(H2∈Ho)，仍采用此种方法很可能会造成局部区域内多数节点均被调用，局部区域内节点的可选择性会大大降低，选择范围的缩小会直接导致任务分配难以同时兼顾跟踪精度和节点能耗，间接对传感器网络的生命周期产生不利影响。

在实际应用中，随着硬件技术的发展，传感器节点的探测范围RD越来越大，多数传感器节点可以做到同时探测到范围内多个目标的信息，并且多是以被动形式接收移动目标的反射信息数据(如超声波传感器、红外线传感器等)，考虑到这些，提出了一种新的适用于多目标耦合状态的任务分配算法，该算法舍弃一个传感器只能分配跟踪定位一个目标的约束条件，提出单个节点可以同时探测多个目标的思想，运用Q学习方法选取合适的时刻tc将服务于多个目标的多个簇ΩH={H1,H2,…,Hn}，合并转化为单簇HC，由于簇内节点可以探测到多个目标的跟踪信息，对整体网络而言，意在减少耦合时刻局部网络内所需激活的节点数量，达到节省能耗的目的。

将多目标的耦合过程描述为“多目标的相遇”、“多目标的并行”和“多目标的分离”3个阶段，图2所示为3个阶段的无线传感器网络场景。图2a表示在无线传感器网络中存在3个移动目标，每个目标由4个传感器节点组成的簇负责跟踪，3个目标即将做互相靠拢的运动；图2b表示“多目标的相遇”阶段，3个移动目标距离足够近，以致3个跟踪单目标的动态簇合并为单簇，由7个传感器节点组成的簇HC负责跟踪所有目标；图2c表示“多目标的并行”阶段，多目标以团体的模式向同一个方向运动，虽然目标之间会出现小范围的相聚或远离运动，但仍然不超出单簇模式探测能力之外；图2d表示“多目标的分离”阶段，即单个目标或者多个目标开始脱离团体，使得难以维持单簇HC继续跟踪多目标，直至完全分离出单簇的探测范围的阶段。

图2　WSN下多目标耦合场景Fig.2　Scene for multi-target coupling in WSN

然而采用此种方法带来了2个问题：1) 如何选择合簇时机和确定单簇HC簇首及簇成员；2) 如何在单簇HC采集的多目标位置信息中筛选出指定目标信息。前者采用Q学习方法进行解决，后者采用赋予目标标签的方法进行目标信息筛选。

2.1　能量模型建立

首先，根据节点能量消耗情况与跟踪精度约束建立网络能耗模型。根据使用形式不同，消耗能量可以分为4类：节点进行数据融合消耗的能量Em，节点发射数据消耗的能量El，节点接收数据消耗的能量Er以及传感器探测消耗的能量Es。Em与参与数据融合的数据量大小有关，当融合x比特的数据时，消耗能量可以表示为

(2)

(3)

Er(sk)=λrx

(4)

式中：sl表示数据发射节点；sr表示数据接收节点；λl表示射频能耗系数；λd表示电路放大系数；Slr表示节点sl与节点sr之间的欧氏距离；θ表示路径衰减系数；λr表示射频消耗系数。Es与使用传感器进行探测的次数有关，每进行一次探测消耗的能量为一个常数。设多目标类型相同，探测概率门限为β0。为了保证跟踪精度满足要求，k时刻探测概率β(k)需要满足

β(k)≤β0。

(5)

2.2　多目标相遇

在无线传感器网络多目标跟踪过程中，将簇Hn的簇首Pn唤醒的目标附近的簇成员备选节点集设为Hcn，在k时刻，如果存在节点sc,sc∈{Hc1,Hc2…，Hcn}，则可称此时n个目标“相遇”。多目标相遇阶段节点任务分配主要需要确定的内容有，簇合并的时机，单簇HC成员个数，和簇首与簇成员的选择，具体过程如下。

2.2.1簇成员个数选择

假设执行跟踪工作节点数目为N，HC所需最小节点数为nmin，估计相遇目标数目为m，负责跟踪单个目标的所需节点数最小为Nmin，每个节点的探测概率均设为pν。簇成员个数的选择与探测概率β(k)有关。此时的探测概率可以表示为

β(k)=1-(1-pν)N

(6)

由式(5)和式(6)可得簇成员个数为

(7)

可知，在满足探测概率门限的情况下，簇成员个数最少为

(8)

(9)

为了保证无线传感器网络能够对覆盖区域内的目标进行跟踪，每个簇内成员节点数目应不小于nmin。为了保证能量消耗最小，在成簇时成员节点数目均选择为nmin。

2.2.2设定簇首与簇成员

首先设定单簇HC的簇首与簇成员，本文在簇首选择时所采用的思想是：将多簇内每个节点的当前剩余能量与网络平均能量进行比较，若节点的当前剩余能量大于网络平均能量，并且节点的通讯半径RD大于节点与各目标间的欧氏距离Si，则将该节点放入候选节点集ξ中，使之成为候选节点，然后在候选节点集中设跟踪效用最优的节点成为簇头。

(10)

(11)

当簇首节点候选集不为空集时，在簇首候选集中选择信息效用函数值最大的节点，设为簇首节点。在簇首节点通讯半径覆盖的区域内选择信息效用最大的nmin个节点作为簇成员。

2.2.3判断是否合簇

因为是否需要合并多簇为单簇HC是属于最优搜索问题，本文采用Q学习方法对其进行研究，需要对簇首及其簇成员的动作以及回报函数加以定义。可以定义Q函数为

(12)

式中：st表示当前多簇的工作模式；at表示对应的动作，具有保持与合并两种形式。当选择保持动作时，st=0，多簇保持原工作状态；当选择合并动作时，st=1，多簇进行合并。最终，可以得到最优选择策略

(13)

式中，At表示at所能选取的动作的集合。式(13)表示获取最大Q值时，选取动作at的过程。当采用此策略时，获得是否合簇选择为最优方案。

为了保证动态感知簇能够对运动目标进行有效跟踪，可以定义如下回报函数

(14)

式中：n为跟踪范围内的目标数目；Ni为多簇跟踪模式下负责跟踪目标i的簇内成员个数；ECi_Nj表示跟踪目标i的簇内第j个簇成员所消耗的能量，可由

(15)

得出。式中：ηj为第j个节点对运动目标进行探测的次数；Sjh表示节点j与簇首间的欧氏距离。ECi_s表示跟踪目标i的簇首的能量消耗，可由

(16)

得出。EH_K表示单簇HC跟踪模式下簇成员的能量消耗，EHS表示其簇首的能量消耗。由式(14)可知，当合簇后总体消耗能量小于合簇前跟踪网络消耗能量时，保持多簇工作模式的动作将会得到消极回报，从而触发合簇动作。如果判断不需要合簇行为，则继续采用传统多目标任务分配方法处理节点竞争冲突问题[8]，继续进行多目标跟踪。

2.3　多目标并行

如果簇首因为能量消耗问题，使得剩余能量低于存活能量下限与簇首切换消耗能量之和，或者在当前任意簇成员探测范围内的目标数减少了，保持当前簇工作的动作应该得到消极回报，将会触发簇首切换动作。但此处的簇首切换是以单簇跟踪模式下的簇首切换，簇首切换后重新选取簇成员即可形成新簇。可以定义 Q 值函数为

(17)

式中：sk表示当前簇首的工作模式；ak表示簇首采用的动作，具有保持与切换两种形式。当选择保持动作时，sk=0，簇首保持原工作模式；当选择切换动作时，sk=1，切换簇首，可以得到最优选择策略

(18)

式中，Ak表示ak所能选取的动作的集合。式(18)表示获取最大Q值时，选取动作ak的过程。当采用此策略时，获得的簇首切换时间为最优。

为了保证动态感知簇能够对运动目标进行有效跟踪，可以定义如下回报函数

(19)

(20)

式中，xbh表示簇首任命指令的比特数，而簇成员任命指令比特数设为xbc。根据式(19)可知，当簇首剩余能量小于存活能量底线与簇首切换消耗能量之和或任意多目标团体内的目标超出当前簇任意簇成员探测半径时，保持当前簇工作的动作将会得到消极回报，将会触发簇首切换动作。如果函数判定k时刻簇首需要切换，则按照2.2.2节方法建立簇首备选集，选择节点作为新的簇首，并且选择簇首探测半径内的节点信息效用函数计算，选择值最大的nmin个节点作为簇成员。

2.4　多目标分离

2.5　目标信息分离

在单簇HC同时探测多个目标的过程中，部分簇成员节点负责跟踪定位单个目标，部分节点是负责跟踪定位多个目标，后者采集的信息需要进一步地筛选出直观的各目标的信息，此步骤属于网络终端数据分析处理的工作。考虑传统的任务分配算法在目标耦合的情形下单个节点跟踪定位单个目标时，节点同样会被动探测到探测半径RD范围内其他目标的信息，只是此类信息被终端数据分析处理时删除了，仅保留了单个目标的信息，此处利用类似的方法，在簇合并时，赋予目标Tn标签tagn，当终端遍历到此节点输入数据流中存在单个tag时，即按照传统数据筛选方法进行操作；如果分析到数据流中存在nt个tag时，即复制此段数据流nt次，同时在第i次复制的数据流中，仅保留带有tagi标签的目标数据，删除其他数据。最终便可筛选出此传感器节点采集到的各目标信息，具体流程如图3所示。

图3　目标信息分离Fig.3　Target information separation

3　仿真实验与分析

取3个随机运动的目标，运动在长、宽均为500 m的正方形场地，共随机分布256个节点。仿真实验在AMD FX-7500 2.10 GHz处理器、1024 MB内存的PC上，使用Matlab R2012b平台实现。采用本文算法作为节点任务分配算法，同时采用扩展卡尔曼滤波算法作为目标跟踪算法，目标的运动模型为

(21)

式中：F为状态转移矩阵；φk为过程噪声，取高斯白噪声，即φk～N(0,Q)，协方差矩阵为Qk；γk为量测噪声，也取高斯白噪声，其协方差矩阵为Gk；h(Xk)表示目标量测矩阵。其中，

为0.8，探测概率门限为0.99，跟踪误差门限为10。跟踪精度评价指标选择位置估计均方根误差，定义为

(22)

图4中，无线传感器网络协同跟踪的仿真场景图显示了传感器节点部署与运动轨迹，3个目标自上往下运动，轨迹交叉后又分离，图中标记了目标在3个不同时刻的簇首和簇成员，在目标未相遇的时刻每个目标由4个节点负责跟踪，相遇时刻由6个节点组成的单簇负责跟踪3个目标，后1个目标脱离群体由4个节点继续跟踪，另外2个目标并行前进，由5个节点组成的单簇负责跟踪，仿真结果说明了多目标耦合情形下任务分配算法的有效性。

图4　WSN协同跟踪仿真场景图Fig.4　Collaborative tracking simulation scene in WSN

图5中，采用最近邻算法、文献[6]算法与本文算法做仿真比较。3种算法分别对同一个情形的3个运动目标进行跟踪，通过计算位置估计均方根误差可以看出，本文算法的跟踪误差与前两者相比，基本显示出了较优的效果，从而证明了本文算法在跟踪精度方面的有效性。

图5　跟踪误差比较Fig.5　Comparison of tracking errors

仿真采用的节点能量参数设置如表1所示。

表1　节点能量参数设置

表2中，对最近邻算法、文献[6]算法及本文算法在跟踪过程中的能量消耗加以分析，可以看出，本文算法的能量消耗小于前两者，这是由于该算法通过合并簇减少了目标耦合情形的簇成员数量，降低了网络能量的消耗，从而证明了本文提出算法对降低网络消耗的有效性。

表2算法能耗对比

Table2EnergyconsumptioncomparisonJ

协同策略能量消耗最近邻算法0．06098文献[6]算法0．01208本文算法0．00893

4　结论

针对WSN多目标协同跟踪中存在的多目标耦合问题，提出了一种基于Q学习的节点任务分配算法。该算法在簇成员的任务分配竞争冲突问题上，提出了合并多簇为单簇进行多目标跟踪的方法，采用Q学习方法，得出了目标相遇时合簇时机的最优选择和目标并行时最优簇首切换方案。同时，综合考虑剩余能量和信息效用给出了最优簇首及簇成员的选择，最后，根据目标特征标签分离了目标信息。仿真结果表明，本文提出的基于Q学习的多目标耦合任务分配算法能够满足多目标跟踪采集信息的需求，同时有效降低网络能量消耗。

但本文所述的方法仅适用于同时段轨迹相近或交叉的一般目标耦合情形，实际应用中还存在很多本文未分析到的耦合情形，并且特殊传感器节点的探测模式也会导致算法难以适用，这些都需要进行下一步的研究。

[1]王永才.传感器网络目标跟踪系统协同设计理论研究与应用[D].北京:清华大学,2006.

[2]LIU J,CHU M,REICH J E.Multitarget tracking in distributed sensor networks[J].IEEE Signal Processing Magazine,2007,24(3):36- 46.

[3]MA H,NG B W-H.Collaborative data and information processing for target tracking in wireless sensor networks[C]//The 4th International Conference on Industrial Informatics,IEEE,2006:647-652.

[4]OKA A,LAMPE L.Energy efficient distributed filtering with wireless sensor networks[J].IEEE Transactions on Signal Processing,2008,56(5):2062-2075.

[5]陈延军,潘泉,梁彦,等.基于IDSQ的自适应动态协同自组织算法[J].控制与决策，2011,26(3):393-396,401.

[6]文莎,蔡自兴,刘丽珏,等.无线传感器网络多目标跟踪中协同任务分配[J].中南大学学报:自然科学版,2012,43(8):3031-3038.

[7]于春娣.基于无线传感器网络的目标跟踪技术研究[D].南京:南京航空航天大学,2013.

[8]刘美,黄道平.WSN中传感器节点的弹性神经网络任务分配方法[J].华南理工大学学报:自然科学版,2010,38(6):66-72.

[9]WATKINS J C H,DYANA P.Q-learning[J].Machine Learning,1992(8):279-294.

[10]PIGGOTT P,SATTAR A.Reinforcement learning of iterative behavior with multiple sensors[J].Journal of Applied Intelligence,1994(4):351-365.

[11]王雪松,朱美强,程玉虎.强化学习原理及其应用[M].北京：科学出版社,2014.

[12]陈剑霞,臧传治,梁韡,等.无线传感器网络动态协同任务分配机制[J].信息与控制,2006,35(2):189-199.

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