程洪玮,唐宏斌,李 骏,王 博

(1.国防科技大学电子科学与工程学院,湖南长沙 410073;2.北京跟踪与通信技术研究所,北京 100094;3.国防科技大学训练部,湖南长沙 410073)

由于低轨星座传感器动态组网、高速运动及空间广域分布,探测目标全球随机出现且时空跨度大等原因,通常少量传感器不可能完成对高速运动目标的全程连续跟踪[1].这种情况下,系统需要较多传感器之间彼此协同、相互接力才能完成对目标的全程连续跟踪,而解决跟踪交接问题的关键就是传感器资源调度技术.

传感器调度就是依据一段时间内的代价函数最优化,对未来的可用传感器资源进行科学而合理的分配.其最基本的目的[2]就是在合适的时候选择合适的传感器对合适的目标做合适的服务.传统的实时调度方法多是短时(Myopic)调度,即根据一步前向预测信息进行调度.这种方法运算量小,但其调度结果对应的跟踪系统性能在时间上稳定性较差.而长时(Non-Myopic)调度方法有效解决了这一问题,但其可选择传感器序列数随着步长的增大而呈指数增长,相应的运算量也呈指数增长.显然,当步长较大时,运算量成为长时调度方法要重点解决的问题.本文针对高速运动目标连续跟踪问题,在分析传感器调度约束条件的基础上,建立了基于长时信息增益的传感器实时调度模型,并提出了基于决策树分支剔除(Pruning)[3-4]的优化求解算法.仿真实验表明,本文所提出的调度模型和求解算法可有效进行低轨星座的传感器资源调度.

1 传感器调度约束条件分析

低轨星座传感器调度需考虑的约束因素主要有资源约束,任务约束和时间约束.

1.1 资源约束

1)单个传感器性能

单个传感器性能约束是指单个传感器可同时处理的最大目标个数,记为τimax.也就是说,系统要求第i个传感器同时处理目标个数τi满足τi≤τimax,i=1,2,…,N,N为传感器数量.

2)全星座传感器综合能力

全星座传感器综合能力包括星座可观测能力和全系统处理负荷.低轨星座对特定目标的覆盖情况称为星座可观测能力,传感器实现对目标跟踪要首先保证目标处于所选传感器的探测视场内.也就是说,为第j个目标选择的传感器组合是对其可实现有效覆盖的传感器集合的子集,即.全系统处理负荷是指整个星座传感器系统可同时处理的最大目标个数,记为τsmax.

1.2 任务约束

1)单任务约束

单任务约束包括完成单个处理任务所需的最小传感器数量和系统分给单个处理任务的最大传感器数量限制,分别记为γjmin,γjmax.则系统为单个处理任务所分配的传感器个数γj需满足γjmin≤γj≤γjmax,j=1,2,…,M,M为系统任务数量.

2)全系统任务约束

全系统任务约束包括多任务处理优先级和多任务处理冲突.整个星座传感器系统通常要处理多个任务,而多个任务处理的重要性、紧迫性的不同,导致对其处理要有一定的先后次序,该次序称为多任务处理优先级,记为cj.多任务同时对同一资源的需求会导致需求冲突,称为多任务处理冲突.此时需要依据任务的优先级等因素对冲突资源进行分配,优先满足重要任务.

1.3 时间约束

时间约束包括调度算法运算延迟、传感器交接延迟和交接次数.调度算法运算延迟是指传感器调度算法对目标和传感器进行决策分配所消耗的计算时间,记为tcmp.传感器交接延迟是指从地面信息处理中心作出传感器调度决策到相关传感器重新捕获到目标所消耗时间,记为tsch,主要包括指令和引导信息传输延迟、传感器指向偏转延迟及目标捕获延迟3部分.因此,两次传感器交接之间的时间间隔tint应满足tint＞tcmp+tsch.交接次数是对目标全程处理的衡量参数.目标全程处理过程中,过多的交接次数会导致传感器之间频繁进行指向偏转和重新捕获,可能导致丢失目标;交接次数过少,或者说,只有在目标运动即将离开传感器视场时才进行调度,由于部分时段所选传感器可能不是最优处理传感器,会降低系统处理效果.

2 传感器调度信息决策树模型

2.1 信息增量模型

对于目标跟踪来说,信息增量定义为一次量测前后的信息熵差值[5].由于信息熵是对目标状态不确定性的度量,因此信息增量反映了量测前后目标状态不确定性的变化,也就是目标跟踪所获得的信息量.根据文献[5]的分析,由于目标预测误差矢量X和目标估计误差矢量均服从目标真实状态矢量为中心的高斯分布,则量测前后的信息增量可表示为:

误差协方差矩阵的每个元素是状态向量的一个特定元素不确定性的度量,或两个元素间联合不确定性的度量,因而式(1)的信息增量可以作为传感器调度的优化准则,通常选择状态更新产生信息增量最大的一个目标优先进行跟踪.为避免复杂计算,可去掉对数运算,这样处理虽然会影响协方差阵范数的相对增幅,但不影响它们的增幅趋势,仍可以利用增幅单调性趋势实现优化搜索.因而,可以用协方差阵范数变化表示信息增量,即:

由于只需要一个相对值来比较信息增量的大小,而并不需要求出一个绝对的信息增量值,因此为便于计算,可用矩阵的迹代替矩阵范数运算[5],即:

但是式(3)为短时信息增量,只能反映当前时刻最优的跟踪传感器选择,不能反映长期最优的跟踪传感器选择,尤其对于高速运动的低轨星座和目标.因此,本文以一个步长step内的长时信息增量作为传感器调度的优化目标函数.假定系统要处理目标数为N,第n个目标可选择传感器个数为Mn,则第l个传感器组合对第n个目标的长时信息增量Inl定义为:

式中:Inl,k+i为第k+i时刻第l个传感器组合对第n个目标跟踪的信息增量,通过多步预测得到;Ln为第n个目标可选择传感器组合数.对于多目标情况,采用联合信息增量作为传感器调度的优化目标函数,这里的联合信息增量IU定义为目标优先级对各目标信息增量的加权和.因此,多目标条件下的优化目标函数为:

式中:cn为第n个目标的优先级;Inl为第l个传感器组合对第n个目标跟踪获得的长时信息增量;L为所有目标可选择传感器组合数.

低轨星座实时传感器优化调度实际上是一个约束最优化问题.根据第1节对约束条件的分析和式(5)的优化目标函数,本文建立如下调度模型:

式中:xnm为传感器分配情况,xnm=1为第m个传感器分配给第n个目标,否则xnm=0.

2.2 信息决策树的建立

当实时传感器调度算法的步长取step＞1时,由一个步长内各时刻可观测传感器组合可以构成如图1所示的深度p=step的决策树[6].决策树每个深度(p,p=1,2,…,p)上任一结点表示一种传感器组合选择st+p-1,实际上,每个深度层次(即每时刻)的可观测传感器组合个数是不同的,为简便起见,图1中假定每时刻可观测的传感器组合个数均为3,则决策树各个深度层次的结点个数依次为30,31,…,3p,…,3p-1,也就是说,深度为p=step的决策树所对应的一个步长内所有可能的传感器组合选择方式有3p-1种.决策树各树枝的权重为采用该传感器组合跟踪目标的信息增量,因此称所建立的决策树为信息决策树.因而传感器调度问题就转化为对信息决策树的最优搜索问题,搜索的目标是最大化信息增量(也就是优化目标函数).

图1 信息决策树Fig.1 Information decision tree

信息决策树的建立主要有两个优点[6]:

1)加速了调度过程,不需要每一时刻都进行一次优化调度;

2)一旦深度为p的信息决策树建立,则任何深度p＜P的子树同样可以用来进行传感器的调度,且步长变为子树的深度,即step=p.

3 基于决策树分支剔除的传感器调度

为克服短时调度方法对应的跟踪系统性能在时间上稳定性较差的缺点,本文采用长时调度方法对低轨星座传感器资源进行调度,并引入分支剔除技术搜索最优传感器组合序列.

根据文献[4]的分析,分支剔除搜索技术可以在不丢失最优传感器序列的前提下,减少搜索时间,因此可以应用于实时传感器调度.常用的分支剔除方法主要有平滑窗法和阈值法[4].平滑窗法类似于Viterbi算法的伪实时形式;而阈值法实际上是直觉地认为任意深度上过小信息增量对应的传感器组合序列不可能是整个步长内生成最大信息增量的传感器组合序列的一部分,并引入取舍参数η(η≥1)剔除掉过小信息增量对应的结点.

本文针对目标跟踪传感器优化调度问题的特征,引入基于阈值的分支剔除搜索技术(其步骤如图2所示),进一步减少搜索结点数.其中,阈值的设定如下:

2)设定一个步长内传感器交接次数阈值为1,若搜索的传感器组合序列存在超过该阈值次数的交接,则认为搜索失败,其后的所有结点均认为失败.

Step1:从根结点开始搜索,代价函数初始值为0.

Step2:从当前结点向下一深度搜索所有路径;计算直到这一深度的最大信息增量;剔除代价值小于η倍最大信息增量的分支;对于保留的分支,记录信息增量值和与之对应的搜索路径.

Step3:将下一深度的每一结点作为根结点并重复Step2的分支剔除.

Step4:当搜索到深度p,或搜索足够时间时,输出直到该深度的最大信息增量对应的最优传感器组合序列.

4 仿真实验分析

星座轨道参数取28/4/2/1596/77.8[7].两个目标不同时不同地发射,其相关参数分别为:1)目标1:发射点E143.000°,N37.000°,落点E113°,N40°,远地点高度1 770 km;2)目标2:发射点E76°,N21°,落点E111°,N38°,远地点高度1 473 km.传感器观测间隔为1 s,视线测量误差90 μ rad.式(6)中优化模型的参数取值分别为τimax=1,γjmin=1,γjmax=Nj,c1=1,c2=2,其中Nj为对第j个目标可覆盖的传感器个数,由可见性分析[8]得到.在CPU为Cuo2 E8400内存4 GB的台式机进行仿真(50次Monte Carlo实验)实现本文基于信息决策树分支剔除的传感器调度算法(IDTA),步长取step=5 s,并与基于短时信息增量的调度算法(MIA,也就是step=1 s)的仿真结果进行比较.两种方法调度传感器跟踪目标的误差如图2所示;而传感器调度结果如表1所示.

图2 两种方法的跟踪误差Fig.2 Tracking error of the two methods

表1 两种方法的调度结果Tab.1 Scheduling results of the two methods

由图2和表1可见:IDTA方法引入长时调度对系统的跟踪性能有一定改善;IDTA方法的最小调度间隔较大,有利于传感器之间的实时跟踪交接;决策树分支剔除的引入大大减少了长时调度算法的搜索路径数,降低了运算量.

5 结 论

本文在分析低轨星座对多目标跟踪应用背景的基础上,引入传感器实时调度的长时信息增量模型,提出基于信息决策树分支剔除的优化求解算法.仿真实验充分显示了本文算法相对于短时调度方法的优越性,以及分支剔除搜索在运算量上的优势.

[1] 王博,安玮,谢恺,等.基于多模型的低轨星座多目标跟踪传感器资源调度[J].航空学报,2010,31(5):946-957.WANG Bo,AN Wei,XIE Kai,et al.Multi-object tracking sensor scheduling for low earth orbit constellation based on multi-model[J].ACTA Aeronautica ET Astronautica Sinica,2010,31(5):946-957.(In Chinese)

[2] XIONG N,SVENSSON P.Multi-sensor management for information fusion:issues and approaches[J].Information Fusion,2002,3(2):163-186.

[3] WILLIAMS J L.Information theoretic sensor management[D].Massachusetts,USA:Massachusetts Institute of Technology,2007.

[4] HUBER M F,HANEBECK U D.Priority list sensor scheduling using optimal pruning[C]//Proceedings of the 11th International Conference on Information Fusion.Cologne,Germany:International Society of Information Fusion,2008:1-8.

[5] 刘先省,周林,杜晓玉.基于目标权重和信息增量的传感器管理方法[J].电子学报,2005,33(9):1683-1687.LIU Xian-xing,ZHO U 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)

[6] CHHET RI A,M ORRELL D.A papandreou-suppappola energy efficient target tracking in a sensor network using non-myopic sensor scheduling[C]//Proceedings of 8th International Conference on Information Fusion.F ranklin Plaza,Philadelphia,USA:International Society ofInformation Fusion,2005:558-565.

[7] BUDIANTO I A,O LDS J R.A collaborative optimization approach to design and deployment of a space based infrared system constellation[C]∥Proceedings of the IEEE National Aerospace and Electronics Conference.Dayton,Ohio,USA:Institute of Electrical and Electronics Engineers,2000:385-393.

[8] 王博,许丹,陈延军,等.低轨星座红外凝视传感器覆盖性能分析[J].湖南大学学报:自然科学版,2009,36(10):68-74.WANG Bo,XU Dan,CHEN Yan-jun,et al.Analysis of the coverage of LEO constellation based on infrared staring sensors[J].Journal of Hunan University:Natural Sciences,2009,36(10):68-74.(In Chinese)