面向目标跟踪的传感器调度技术研究

安 雷,吉 兵,李召瑞

(陆军工程大学石家庄校区,河北 石家庄 050051)

随着合成孔径雷达、相控阵雷达、敌我识别器、前视红外雷达、电子支持测量等先进传感器在军事领域的大量应用,如何有效提高传感器利用效率,实现对传感器的快速、自动管理,实现对观测数据的高效集成和处理成为了传感器管理和传感器调度研究的热点。传感器调度作为传感器管理的一个重要组成部分,指在确定的时间区间内,在遵循各类约束条件的前提下,根据传感器资源可用情况和目标探测需求,为各探测目标分配适当的传感器资源和探测时间区间,生成每个传感器在该时间区间内的工作计划,从而达到某项或某些指标的综合最优。传感器管理研究主要关注的是优化方法、制定策略,与控制论、统计学、信息论、信号处理等学科密切相关[1],相比之下,传感器调度则更偏向于对传感器每一时刻状态的管理和控制,例如控制传感器定时开关机、按照既定策略选择工作模式、根据目标运动状态确定机动方向等。

1 部分可观马尔可夫决策过程

结合已有文献,可以将传感器调度简要描述为一个决策过程，即以雷达等为终端的传感器系统在一定的约束条件下,依据k时刻追踪目标所得到的测量信息zk,制定传感器下一步控制动作,以达到使回报期望最大化或风险函数最小化的目的。这个过程实际上就是马尔可夫决策过程(Markov Decision Process,MDP)[2],这里假设了k+1时刻传感器的控制动作仅由k时刻对跟踪目标的观测值zk决定,而且所跟踪目标的状态是完全可以被传感器观测到的。但实际上由于敌方干扰以及使用代价影响等因素,目标状态的观测是不完全的,测量得到的信息存在一定的不确定性,由此便引入了部分可观马尔可夫决策过程(Partially Observed MDP,POMPD)[3],通过利用POMDP对传感器调度问题进行建模,可以在测量得到的不完全信息的基础上,仅凭历史调度策略集和当前调度动作反馈效果进行决策,为有效改善动态不确定情况下的调度性能,提供了可靠的理论基础和可行的解决方案,其基本架构如图1所示。

该图可利用六元组〈S,A,Z,T,R,O〉来表示,其中,S表示状态集,为所有可能环境状态的集合;A表示行动集,为系统所有可选调度动作的集合;Z表示观测集,为系统所有观测结果的集合;T为状态转移函数,指系统在状态s的情况下执行动作a后转移到状态s′的概率,表示为T(s,a,s′);R为回报函数,表示在状态s的情况下执行动作a之后得到反馈结果,其值满足Rmin≤R≤Rmax;O为观察函数,指在上一时刻系统采取动作a后,由状态s转移到状态s′,观察得到z的概率,表示为O(s′,a,z)[4-5]。其具体的运行流程为:在已知状态sk和观测值zk的情况下,从行动集A中选取调度动作ak,产生单步收益R,则状态sk在状态转移函数T的作用下变为sk+1,同时根据观测函数O,得到观测值zk+1,并依次反复循环。

2 传感器调度基本模型

面向目标跟踪的传感器调度,主要以目标跟踪为应用场景、以跟踪精度和使用代价综合效能最佳为优化指标,创建目标函数、求解调度方案,实施传感器资源选择和分配,使传感器系统达到最优的工作状态,其基本模型如图2所示。

基于图2,可以将调度过程视为一个“跟踪—调度—反馈”的闭环回路,能够有效克服目标跟踪中存在的动态变化问题,具备根据传感器观测数据更新目标和环境状态,依据使用代价预测和跟踪精度预测进行未来传感器调度规划,分配传感器继续完成跟踪目标任务的功能。其基本流程为:在某一k时刻,系统以自身传感器的相关参数、作战目标机动状态、战场环境特点、作战任务需要等已有信息为决策依据,对下一步或多步决策时长内各备选调度方案所产生的跟踪精度和使用代价进行预测,以综合效能达到最优为目标,结合约束条件建立目标函数,选取适当的寻优算法求解得到k+1时刻的最优调度方案,执行后测量得到新的目标信息,完成对目标状态的更新。

2.1 相关规则

1)一定的跟踪精度。跟踪精度直接反映了传感器的工作性能,但在实际应用中,越高的跟踪精度意味着更多的数据和更大的能量消耗,所以跟踪精度通常只要求满足任务需求即可,常用的衡量指标有协方差矩阵的迹、互信息量、后验克拉美罗下界等[6-7]。

2)适当的使用代价。使用代价指传感器在使用或调度中所产生的损耗,包括能量损耗、辐射代价以及响应延迟等,能量损耗主要存在于无线传感器网络(Wireless Sensor Network,WSN)中,由于传感器能量有限,导致在跟踪过程中必然存在通信、探测和计算等产生能量消耗的问题,常用的量化模型有常数模型、路径能耗模型[8]和自由空间传播模型。辐射代价是指主动传感器在工作时向外辐射电磁波导致位置暴露的问题,常采用固定常数、截获概率[9]和辐射度影响进行量化。响应延迟是传感器在调度中由于频繁切换工作模式或传感器性能不足、通信质量一般等导致调度效果达不到预期目标的问题,通常描述为固定常数[10]。

3)较强的系统鲁棒性。当跟踪目标在进行复杂机动或针对传感器的观测采取干扰措施的情况下,传感器调度必须要能够保证稳定的跟踪精度以及综合效能的有效平衡。

4)实时的数据反馈。军事应用中的目标跟踪对观测数据的获取、调度方案的求解以及调度动作的展开有严格的时效性要求,必须充分考虑时延问题,平衡好算法复杂度和跟踪精度、跟踪时效之间的矛盾。

2.2 约束条件

1)实际任务需要。主动传感器在考虑辐射风险的条件下开展目标跟踪时,在已设置跟踪精度阈值的前提下,必须以辐射代价最小或者不超过一定值为优化目标创建目标函数,求解调度方案,在确保跟踪任务完成的同时,降低传感器辐射风险[11]。

2)传感器性能局限。在制定目标函数时,必须充分考虑传感器的最小可检测信号、最大作用距离、波束宽度等基本参数,确保目标能被观测到。

3)环境因素影响。在不同的作战条件下,传感器的工作性能不尽相同,在实际调度中,必须充分考虑地理环境等对传感器机动性能的影响和对探测目标的遮蔽等因素,确保对目标的准确跟踪。

3 传感器调度的决策指标

基于POMDP的理念,根据决策执行后所带来回报的时间尺度,可将传感器调度划分为短时调度和长时调度两种。传感器短时调度的过程可简单描述为一个单步的最优化决策过程,一般以单个调度动作所产生的短期收益作为决策依据,以传感器对目标的单步侦察效能(收益与代价的综合)为优化指标集,构建管理算法、建立调度模型,进而求得最优解。Kreucher[12]针对多目标跟踪问题,以单步Rényi信息增量最大化为决策依据,提出一种基于信息论的传感器短期调度方法。文献[13]基于高斯混合多目标滤波器(GM-MTF),利用巴氏距离和Rényi散度作为评价指标函数,提出了以单步最优为控制准则的传感器控制策略。

传感器长时调度则以一段时域内的调度序列所产生的累积收益为决策依据,在性能上要优于短时调度。实际应用中,主动传感器由于存在基于辐射量的跟踪代价,为有效平衡各类指标,一般在建立目标函数时采取长时调度的方式,将其决策信息定为一段时域内的所有时刻侦察收益和辐射代价的综合[14-15]。针对空基预警探测系统特点,唐书娟[16]采取长期调度和动态调度相结合的分配策略,提出了一种基于任务控制思想的传感器分配方案,降低了传感器调度频次。文献[17]结合空天高速目标跟踪任务,提出了多源异构传感器调度多目标优化模型和柔性果蝇算法,设计了“目标-时间-传感器”三维编码方式,解决了传感器调度时间碎片化和局部最优的问题。

传感器短时调度仅以一步收益为决策依据,计算复杂度低,易于实现,但调度效果往往不理想,不适用于对跟踪精度等战术指标收益要求极高的任务。传感器长时调度虽然在调度性能方面优于短时调度,但随着决策步长的增加,其可行解的数量呈现出指数上升的态势,极大增加了目标函数求解的计算复杂度,不易于实际工程实现。

4 传感器调度的优化方式

传感器调度必须严格以实际任务的需要为决策依据,要具备一定的跟踪精度,能够有效控制使用代价。但要获得更高的跟踪精度,势必会产生更大的使用代价,这就限制了调度策略的制定必须始终围绕处理跟踪精度与使用代价之间相互矛盾的关系展开,根据传感器调度效果的评价内容是跟踪精度最大化或是使用代价最小化或是两者平衡,可以将传感器调度分为平衡优化调度和约束优化调度。

平衡优化调度以多个指标的平衡为优化目标,通过权衡回报期望和使用代价的综合效能,使得一定时域范围内的回报期望和使用代价达到最佳平衡的状态。针对多传感器数据融合中的系统资源消耗问题,文献[18]按照平衡消耗代价的思路,提出了一种以能量消耗和信息熵增量加权值为效用的线性规划的传感器管理算法,有效提高了跟踪效能。文献[19]为降低空中目标威胁评估结果不准确及传感器辐射等潜在风险,基于POMPD建立传感器调度模型,以两种风险的加权和最小为优化目标建立长期目标函数,实现了对风险的准确预测。约束优化调度以单个指标的最优为优化目标,通过单纯对回报期望或者使用代价进行优化,充分利用有限的传感器资源,在规定的调度时间内,实现最佳的单方面性能,这种调度方式一般更加适用于目标跟踪场景。Kaplan[20]针对分布式WSN调度问题,以目标跟踪精度的几何稀释因子为准则,采取全局节点选择算法,提出传感器分配方案。针对主/被动传感器调度问题,文献[21]以跟踪精度为约束、以系统辐射代价最小为优化目标建立目标函数,改进了分布式拍卖算法,有效降低了目标跟踪时传感器系统的辐射风险。

总的来说,相比约束优化调度,平衡优化调度需要考虑的因素更多,模型设计和运算求解最优调度方案更加复杂,为满足时效性的要求,一般需要借助寻优求解算法获得最优调度方案。

5 传感器调度的寻优算法

实际应用中,传感器调度为提高跟踪精度、降低使用代价,采取了一系列技术及算法,导致普遍存在求解过程复杂和计算量巨大的问题。如何在最短的时间内正确选择各时刻的调度方案及控制动作,以达到满足调度策略或任务要求的最优状态,必须依赖于各类寻优算法。

5.1 动态规划方法

动态规划方法(Dynamic Programming Method,DPM)主要用于求解多阶段决策过程最优化问题,其应用贝尔曼原理,将原本的多阶段过程转换成较为简单但相互之间又有密切关联的子问题,并根据各阶段递推关系进行快速求解,能够有效实现当前利益和未来效益的综合考量[22],一般适用于平衡优化问题且调度效果与基策略选取相关。运用该方法求解决策的前提在于问题是否满足无后效性原则,即未来状态与历史状态无关,只与当前状态有关。在传感器调度中,下一时刻调度动作的产生,仅由当前时刻传感器的观测值决定,满足无后效性原则,但由于节点状态和路径代价取决于历史调度序列,导致了经典动态规划方法的应用效果并不理想,基于此,Bertsekas[23]提出了rollout算法,通过实时计算仿真Q值来获得次优传感器调度序列;Cheng[24]则使用基于树的结构作为调度算法输入,区分树内、树外进行冲突处理,提出了一种WSN最短路径算法。

5.2 智能优化算法

智能优化算法(Intelligent Optimization Algorithm,IOA)主要包括遗传算法、蚁群算法、人工蜂群算法、布谷鸟算法、模拟退火算法等一系列基于生物学、物理学原理的算法。此类算法实现了复杂非线性问题次优解的快速求取,具有较强的搜索能力、较优的适应性和较好的稳健性,且计算量不随传感器数目的增加而剧烈变化,在传感器管理中常用于求解多传感器目标分配问题,经过合理的迭代能够接近最优解。根据验证[25],当决策时长和传感器数目较大时,智能优化算法容易陷入局部最优,导致搜索性能降低。

1)遗传算法(Genetic Algorithm,GA)是对生物基因遗传和进化原理的计算机仿真应用,包含编码和解码两个过程,在求解计算中,首先从包含若干已编码个体的初始种群开始,按照适者生存的原理,以适应度大小为依据筛选个体进行交叉和变异,产生新一代种群,实现近似解的逐代优化,并依次类推,最终获得的末代种群解码后即为近似最优解。由于遗传算法是在搜索空间对编码集进行多点求解,能够有效避免限制条件的约束,便于复杂问题的求解,同时也方便代入已有的调度模型,扩展性较强。Milton L.Cone[26]针对传感器调度技术选择问题,建立了一套评估准则,首次对遗传算法应用于调度方案求解的实际效果进行评价,并提出了相关修改意见。为解决遗传算法进化缓慢、易早熟,局部寻优能力差等问题,文献[27]基于广义邻域搜索算法的统一结构,将遗传算法和模拟退火算法有效结合,构造遗传模拟退火算法(GASA),实现优势互补,在满足传感器调度实时性要求的同时,提高了算法的寻优特性。文献[28]以WSN节点调度问题为研究对象,基于适应度比例的选择,采取优化的轮盘赌方法筛选适应度较高的个体进行交叉变异,更加符合“适者生存”的原则。

2)人工蜂群算法(Artificial Bee Colony,ABC),由Karaboga[29]于2005年首次提出,其将当前问题的潜在解用蜜源位置来表示,通过模拟蜜蜂采蜜当中引领蜂对蜜源的搜索,引领蜂对蜜源信息的共享,跟随蜂以相同概率对蜜源的搜索,引领蜂转变为侦查蜂后在相应空间内进行的随机搜索等一系列操作,来解决科研和生活中的多维多模优化问题,在目标跟踪、数据收集、工程实践等多个领域得到了广泛应用,具有求解操作简便、控制变量少、方法易于实现等特点,存在的不足是容易陷入局部最优。为进一步提高ABC的寻优性能,Karaboga[30]于2014年对该算法进行了修改,通过改进新蜜源搜索公式vij=xij+φij(xij-xkj),找到当前开采蜜源附近(假定为半径r的圆)最好的蜜源进行开采,提出了快速人工蜂群算法(qABC);文献[31]则在新蜜源搜索公式中引入振动频率M和振动幅度S,将新蜜源搜索维度由1调整为M,将随机数φij的取值范围由[-1,+1]调整为[-S,+S],有效提高了收敛速度;文献[32]通过采取双向轮盘赌的方式选择引领蜂,推动种群朝着极大、极小两个方向进化,保证了种群多样性的延续,改善了ABC的寻优能力和计算速度。

5.3 决策树搜索算法

决策树(Decision Tree,DT)是一种树状结构的分类算法,主要用于处理、求解多阶段和多种可能性的决策问题,进而获取最优方案。在实际运算中,主要根据树节点上训练数据的最优特征进行划分,运用概率方法计算各方案损益值,并按照决策原则进行优选,最优特征选择的度量指标有信息增益、信息增益比和基尼指数等。决策树搜索算法被广泛运用于人工智能和运筹学领域,例如单路径寻优问题、约束满足问题和车辆路径问题。在传感器调度应用中,一般先将调度问题构建成决策树,然后采用合适的搜索技术进行求解。

图3 决策树示意图

1)穷举搜索法(Exhaustive Search Method,ESM)是进行决策树搜索的常用方法,在求取最优方案时,从树的根节点出发至最底层节点,对初始状态到目标状态的每一种可能状态都进行搜索,不进行剪支、不作取舍,可以视为一种无启发信息的盲目搜索,主要包括标准代价搜索(Uniform Cost Search,UCS)、宽度优先搜索(Breadth First Search,BFS)和深度优先搜索(Depth First Search,DFS),由于UCS算法在打开节点时不考虑其所在深度,优先打开代价最小的节点,故其节点打开比最低。穷举搜索法的最主要特点是求解过程简单,但计算量大,处理时间长,难以满足传感器调度实时性的要求。

2)基于阈值的方法(Threshold Based Method,TBM),为降低传感器调度方案的求解计算复杂度,Huber M F引入分支剔除的思想[33],设置信息增量阈值参数∂(∂≥1),将某一深度H上达不到∂值的传感器组合序列排除在最优调度序列之外,并依此对决策树分支进行裁剪,在不丢失最优传感器序列的前提下,有效减少了搜索时间。文献[34]将长时调度增量模型描述为信息决策树,并采取基于阈值的分支剔除技术搜索最优解,有效降低了长时信息增量最优搜索的运算量。随着∂值的增大,裁剪的条件逐渐降低,进行决策树搜索时会有更多的分支被删除,进而加快搜索速度,但同时也会导致最优解和部分次优解所在分支被剔除,影响调度性能。

3)分支定界法(Branch and Bound Method,BBM)是一种构造性的搜索算法,主要用于求解组合最优问题,通过逐层剖析最优解的各项可行域,证明解的最优性,原则是进行反复分支,每次分支都对子集合计算最优解的界,通过逐代分支搜索,直至子集合仅含有一个解时为止。其中,剖析并分解可行域的过程称为分支过程,在可行域中选择目标函数上下界的过程称为定界过程[35]。针对相控阵雷达调度问题,文献[36]提出了一种基于分支定界法的传感器调度算法,通过对已有调度结果采取“分支”、“删减”等操作,实现对空间范围的有效控制。文献[37]按照节点间互相优化定位的思路,通过精确裁剪待定位节点的蒙特卡洛盒,增加节点的粒子滤波条件,实现了移动WSN节点的精确定位。文献[38]根据先见优化的思想,借助精度收益及辐射代价将调度问题转化成决策树问题,并采用分枝定界方法求解,使综合跟踪效能达到了最佳平衡。

6 结束语

随着数据融合技术的不断发展,以及应用环境实际调度模型等的逐步完善,基于能量消耗、网络通信、体系寿命、有效覆盖等多指标的传感器调度逐渐成为研究的热点。结合当前国内外参考文献,如何科学设计传感器工作和调度模型,优化改进目标函数、跟踪算法、寻优算法,从而克服实际应用场景对传感器系统感知、通信、机动能力的削弱,降低环境杂波和电磁干扰对跟踪精度的影响,平衡各类使用代价,高效完成目标检测、识别、跟踪和威胁评估及火力打击等各项任务,还需要深一步的研究。