基于分布搜索的传感器指示交接协商机制*

杨涛，许蕴山，唐书娟，罗文涛

（空军工程大学航空航天工程学院，西安710038）

基于分布搜索的传感器指示交接协商机制*

杨涛，许蕴山，唐书娟，罗文涛

（空军工程大学航空航天工程学院，西安710038）

针对传感器指示交接技术中“指示任务怎样执行”的问题，根据指示交接的实际过程，研究了多传感器针对多个协作任务怎样进行更好调度的问题，提出了基于分布搜索的多维协商机制。通过协商函数的迭代更新，不断寻找综合效用最大的传感器调度策略，优化了指示交接过程中多传感器多任务调度过程。实例仿真结果表明，所提方法合理、有效，提高了传感器协作的效率，为指示交接的深入研究奠定了基础。

传感器指示交接，分布搜索，传感器协作，协商函数，综合效用

0 引言

大型预警机平台上配置有多种异类传感器，为了完成多传感器协同探测任务，存在传感器间指示和交接目标的军事需求。传感器指示交接是传感器管理的一个重要组成部分，对其研究可以丰富传感器管理的内容，完善传感器管理的功能。所谓传感器“指示”就是利用来自于一种传感器的探测信息去引导另一种传感器来对准同一个目标或事件。当传感器A向传感器B移交监测目标，或者传感器A引导传感器B进行不同的参数测量时，就出现了“交接”。当满足交接条件时，指示其他传感器提前在目标来袭空域搜索，缩短截获目标的时间，保证尽可能连续跟踪以及交接平滑。

国内外关于传感器指示交接技术的研究还相对较少。文献［1］针对雷达/红外复合制导系统，分析和推导了雷达对红外进行角度成功指示概率的解析表达式变化规律，研究同地配置下异类传感器的指示引导问题。文献［2-4］研究了同地配置下ESM对2D雷达以及IRST对3D雷达的指示引导概率并对其进行了解析表达，同时讨论了成功指示概率的性质。文献［8］研究分析了同地配置下一维测向和二维测向ESM对3D雷达成功指示引导的概率，同时对ESM引导3D雷达截获目标所需的搜索时间进行了分析，得出在ESM引导下，雷达截获目标所需的搜索次数大大减少。文献［6-7］研究了异地配置下ESM对2D雷达以及IRST对3D雷达的指示引导，推导了指示引导方程，分析了指示引导误差。从目前的研究来看，现有文献只研究了如何解决异类传感器间的指示引导问题，提出了相关的算法，对于在指示交接中多传感器针对多任务的调度策略尚未讨论。

本文针对指示交接问题的本质，研究分析了多传感器针对多个协作任务怎样进行更好调度的问题，针对“指示任务怎样执行”提出了基于分布搜索的多维协商机制，优化了指示交接中多传感器多任务调度过程。

1 基于分布搜索的多维协商机制

发起传感器和响应传感器对总任务及子任务的协商执行可分为两种情况［8-13］：

一是发起传感器将自身不能执行的某些任务需要分配给响应传感器协作执行。包括：①由于目标任务的类型改变，使发起传感器不能执行改变后的目标任务；②当目标离开发起传感器的探测区时，需进行任务交接；③发起传感器将已有任务分解为多个子任务后，若自身无法执行，则需由其他传感器执行。

二是发起传感器对于自身可以执行的某些任务无法达到性能要求，需要和其他传感器协作以提高性能指标。

发起传感器和响应传感器在协作时针对目标任务的多维属性进行协商，通过局部效能增益Eleg和局部效能代价Elec构建一种分布搜索策略。多维属性主要包括任务完成的时间（开始、结束）和质量。

发起传感器首先建立一个包含对该协作任务的时间要求和质量要求的发起提议，时间要求是由协作任务能够开始执行的最早可能时间和协作任务需要完成的最迟时间所确定的一个时间范围。发起传感器在这个时间范围之内获得最大局部效用增益。

图1和图2描述了传感器指示交接中发起传感器和响应传感器之间基于分布搜索的多维协商机制进行协商的有限状态图，令发起传感器为S，响应传感器为R。其基本流程如下：

图1 传感器协商的有限状态图（发起）

图2 传感器协商的有限状态图（响应）

S首先建立提议，并且发送该提议给R开始协商。R接收提议并开始评价提议（对于多个协作任务需分别计算其效用和代价），如果局部效用增益大于局部效用代价（即综合效用＞0），那么R接受这个提议并给S发送接受消息，S接收接受消息并重新评价提议，如果综合效用大于0且综合效用的解或协商次数/时间达到要求时，那么协商终止并且告知R确定哪一个提议；否则，S基于它先前的提议和当前的提议产生一个新的提议，并且开始新的一个协商循环。如果R对接收的提议进行评价后的局部效用增益小于局部效用代价，那么R拒绝这个提议，然后建立一个反提议并把这个反提议发送给S，S获得这个反提议并评价这个反提议，如果综合效用大于0且针对一个S的多个协作任务不是所有的R对先前的提议都产生了反提议，那么S需对先前提议以及R产生的反提议进行重新评价，否则判断综合效用的解或协商次数/时间是否达到要求，如果达到要求，那么协商终止并且告知R确定哪一个提议。如果S对获得的反提议进行评价后的综合效用小于0，那么S基于它先前的提议和当前的提议产生一个新的提议，并且开始新的一个协商循环。

根据发起传感器和响应传感器协商的次（步）数可将协商机制分为以下三种：

（1）单步：发起传感器发送一个提议给响应传感器，若综合效用大于0，响应传感器接受该提议；否则，拒绝该提议，并且协商以失败而终止。

（2）多步：发起传感器和响应传感器执行协商系列“建立提议，产生反提议，产生新提议……”，直到找到满足综合效用的解。

（3）循环：发起传感器和响应传感器执行协商系列“建立提议，产生反提议，产生新提议……”，直到达到某一循环限制。

上述协议不是在所有的可能选择中搜索，而是采用启发式方法放弃了部分搜索空间，因为可行解的搜索空间非常大并且一个完全的搜索太昂贵，所以协商机制并不执行一个完全的搜索。

2 协商机制中的综合效用计算模型

发起传感器和响应传感器协商时通过使用调度S执行任务，获得的综合效用E（S）是计算局部效用增益和局部效用代价的基础，可用一个多属性效用函数表示［14］，它是任务完成的质量、花费代价和持续时间的加权函数，可表示为：

wq、wc、wt表示任务完成质量、代价和持续时间相对重要性的权重；q（S）、c（S）、t（S）分别是执行任务调度S所达到的质量、花费的代价和时间；qthreshold的值指定传感器打算从其任务执行中达到的质量，可根据传感器执行所有原有任务和协作任务的质量总和确定，计算时设定的值通常比质量总和稍小一些，以增加任务完成质量的权重；climit、tlimit的值指定传感器打算花费在其任务执行上的代价和时间，可根据传感器执行所有原有任务和协作任务的代价总和、持续时间总和确定，计算时设定的值通常比代价总和、持续时间总和稍大些，以保证在调度S中cg（S）、tg（S）的值大于0。

3 协商函数

根据发起传感器和响应传感器协商机制的有限状态图可知，两种传感器主要通过3个函数进行协商［14］：一是发起传感器建立提议函数；二是响应传感器产生反提议函数；三是发起传感器产生新提议以响应这个反提议，即产生新提议函数。

3.1 建立提议函数

建立提议函数用于发起传感器建立一个初始提议。发起传感器针对每一个协作的任务，通过分析确定对协作任务要求的最早开始时间和最迟完成时间。最早开始时间和最迟完成时间定义为一个最大化局部效用增益的时间范围，其长度依赖于协作任务和其他任务之间的关系，以及对其他任务的时间约束。除此之外，这个初始提议也指定执行协作任务所要求的质量［8］。

3.2 产生反提议函数

产生反提议函数用于响应传感器产生一个反提议以响应一个不可接受的提议。如果没有先前的反提议，响应传感器将通过改变时间范围和质量要求建立第一个反提议，并且找到一个以最小局部效用代价执行这个任务的调度。这个反提议有最小的局部效用代价，因为它仅仅考虑自身的约束并且选择最佳的任务执行时间和方式，因此，它更可能是一个可接受的提议；如果存在一个先前的反提议，响应传感器通过交替地松弛时间约束和降低要求质量精炼发起传感器当前的提议。并且这个过程是重复的直到找到一个可接受（综合效用大于0）的反提议。

3.3 产生新提议函数

产生新提议函数用于发起传感器基于其先前的提议而建立一个新的提议。如果先前的提议对响应传感器是可接受的，那么当前提议实际上是发起传感器先前提议带有详细执行信息（比如开始时间，完成时间以及任务质量）的提议。如果先前的提议不可接受，当前的提议是一个来自响应传感器的反提议。

4 应用实例分析

文献［8，15］给出了发起传感器中的协作任务分配给单个响应传感器单独执行时相互协商的情形，但还需要考虑：

（1）当一个发起传感器中多个协作任务分配给多个响应传感器执行时，对发起传感器中局部效用增益的计算时应把协作任务看作一个整体，而局部效用代价应记为协作任务在不同的响应传感器执行的局部效用代价总和，其中响应传感器局部效用代价的计算不包括协作任务获得的质量，而应存在于发起传感器局部效用增益计算时的总质量中。

（2）对于发起传感器自身能够执行已有的某些任务或未进行分解的任务，但是达不到性能要求，需要和其他传感器协作执行的情形，发起传感器和响应传感器应分别计算其执行同一任务所获得的质量、消耗的代价和时间。

图3 发起传感器的任务结构

下面举例说明协商机制的工作过程。假设图3为发起传感器的任务结构。它有2个任务T1和T2。可将T1分解成3个子任务，均有9个单位的处理时间（t：9），10个单位的代价（c：10），能产生10个单位的质量（q：10）。可将T2分解成2个子任务M4、M5，M5的最终期限指该任务必须在60个单位时间范围内完成。M4和M2间存在着使能关系，表示M2成功完成之后才能执行M4。同样，M4成功完成之后才能执行M5。假定M4可以再分解为M41、M42、M43，其中M41可由发起传感器执行，M42、M43不能被发起传感器执行，需要分配给其他传感器。假定响应传感器1执行协作任务，响应传感器2执行协作任务。响应传感器1、响应传感器2的局部任务结构如图4和图5所示。

在这个例子中，对发起传感器定义综合效用计算模型中的参数如下：qthreshold=80，climit=80，tlimit=70，

wq=0.7，wc=0.15，wt=0.15。对响应传感器1定义：qthreshold=50，climit=50，tlimit=55，wq=0.7，wc=0.2，wt=0.1。对响应传感器2定义：qthreshold=45，climit=45，tlimit=50，wq=0.7，wc=0.2，wt=0.1。

图4 响应传感器1的任务结构

图5 响应传感器2的任务结构

其协商详细过程描述如下：

4.11 步协议的协商

第一步：建立提议

假设发起传感器不执行M42、M43，并实现下述调度S1：

又假设响应传感器1、2分别能够执行M42、M43时，发起传感器实现调度S2：

其中，M42、M43执行结果的有效时刻是37。

q（S2）=82，c（S2）=58，t（S2）=47，E（S2）=0.8080，局部效用增益Eleg=E（S2）-E（S1）=0.808 0-0.509 5=0.298 5。则于调度S2，发起传感器对M42、M43建立提议PC0-1、PC0-2，对于协作任务M42、M43可由不同的传感器同时执行，因此，2个任务在时间上相互不受影响，因M2使能M4，则使能M4的子任务M42、M43，所以协作任务M42、M43最早开始时间是9，最终期限是37，实际上协作任务的最终期限还可后延（M5的最迟开始时间是60-10=50），这将在以后产生新提议的时候再考虑。对于M42，给定的时间区间28（37-9）远大于估计的持续时间（（12+9+6）/3=9），因此，质量要求值可设置为高于估计质量平均值（（18+12+6）/3=12）的15。对于M43，与M42类似，故质量要求值也设为15。

根据以上分析，发起传感器分别向响应传感器1、2发送以下提议：

PC0-1：［M42，最早开始时间：9，最终完成时间：37，质量要求：15］

PC0-2：［M43，最早开始时间：9，最终完成时间：37，质量要求：15］

第二步:评价提议

响应传感器1找到满足提议PC0-1的调度S3-1：

在此需要说明的是，调度S3-1获得的质量不包括协作任务M421达到的质量，因为它已计入发起传感器调度S2的总质量中。

根据M421和B1、B2、B4的最终期限约束以及B3、B4的使能关系，不能找到满足PC0-1且执行响应传感器1的任务结构下所有任务的调度，只能尽量减小局部效能代价，找出效能最大的调度。除以上调度，还有以下可能的调度：

计算可知，调度效用一样。

相比较响应传感器1没有执行协作任务M42的调度S4-1：

响应传感器1局部效用代价为：

由于2个响应传感器执行2个协作任务，因此，还需计算响应传感器2的局部效能代价。

响应传感器2找到满足提议PC0-2的调度S3-2：

根据M431和C1、C2的最终期限以及C1和C2的使能关系，不能找到满足PC0-2且执行响应传感器2任务结构下所有任务的调度，只能找出效用最大的所有可能调度，除以上调度，还有可能的调度如下：

计算可知，调度效用一样。

相比较响应传感器2没有执行协作任务M43的调度S4-2：

响应传感器2局部效用代价为：

总的效用代价为响应传感器1和响应传感器2局部效用代价的总和：

所以PC0-1、PC0-2是一个不可接受的提议。那么响应传感器需生成反提议函数，以响应被拒绝的提议。这里首先只考虑由响应传感器2生成一个反提议，经过分析得出，由于高质量要求的协作任务的执行持续时间较长，限制了响应传感器2自身原有任务的执行，因此，导致先前提议的失败。所以要寻找以更少持续时间完成M43并保证原任务得以执行的方式建立反提议，而减少时间会导致质量降低，则建立反提议时应降低质量要求。

第三步:产生反提议

假定响应传感器2建立一个反提议：

PC’0-2：［M43，最早开始时间：9，最终完成时间：37，质量要求：8］，仅考虑自身约束找到执行任务的时间和方式均最佳的调度S’3-2：

这个反提议具有最小的局部效能代价，故更可能被接受。响应传感器2把反提议PC’0-2发送给发起传感器。

第四步:评价反提议

发起传感器根据PC’0-2及PC0-1:

PC0-1:［M42，最早开始时间：9，最终完成时间：37，质量要求：15］

PC’0-2:［M43，最早开始时间：9，最终完成时间：37，质量要求：8］

找到调度S5:

（M42、M43执行结果的有效时刻是37并分别达到15、8的质量）

响应传感器1基于提议PC0-1的调度为：

响应传感器2基于提议PC’0-2的调度为：

计算综合效用代价为：

故PC0-1、PC’0-2可被接受。

由于响应传感器1未对之前的提议生成反提议，因此，发起传感器还要再评价提议，响应传感器1、2分别向发起传感器发送以下提议：

PC’1-1：［M42，开始时间：9，完成时间：21，质量要求：18］

PC’1-2：［M43，开始时间：10，完成时间：15，质量要求：8］

第五步:再评价提议

发起传感器对PC’1-1、PC’1-2进一步评价，因为接收到的提议质量要求更高、完成时间更早，且得到响应传感器更早的完成时间：

q=84、c=58；响应传感器的最迟完成时间为21，则总持续时间t=47、E=0.825 5。

局部效用增益为：

故PC’1-1、PC’1-2可被接受。此方案中综合效用为0.316 0-0.220 0=0.096 0，若在单步协商中，发起传感器将停止协商，采纳方案PC’1-1、PC’1-2，但在二步或三步协商中，发起传感器会继续协商以尝试找到更好的方案。

4.22 步协议的协商

第六步:产生新提议

对于协作任务M42，先前的提议是可接受的，由于当前提议PC’1-1的质量18大于平均的质量12，那么新提议将要求具有初始时间区间和更低的质量要求（假设为6），以更好的降低局部效能代价；对于M43，先前提议是可被接受的，由于当前提议PC’1-2的质量8小于平均质量12，那么新提议需把最早开始时间9延后为14（增加5个单位时间），并且降低质量要求以减少局部效能代价。根据以上分析，发起传感器建立新提议PC2-1、PC2-2：

PC2-1：［M42，最早开始时间：9，最终完成时间：37，质量要求：6］

PC2-2：［M43，最早开始时间：14，最终完成时间：37，质量要求：7］

发起传感器评价新提议并找到调度S7：

M42、M43执行结果的有效时刻是37并且分别达到6、7的质量。

发起传感器发送PC2-1、PC2-2和Eleg（PC2-1、PC2-2）=0.202 3给响应传感器1、响应传感器2。

第七步：评价提议

响应传感器1找到满足提议PC2-1的调度S8-1：

响应传感器2找到满足提议PC2-2的调度S8-2：

总的效用代价：

故PC2-1、PC2-2可以被接受，那么响应传感器1、2分别向发起传感器发送以下提议：

PC’2-1：［M42，开始时间：18，完成时间：24，质量要求：6］

PC’2-2：［M43，开始时间：20，完成时间：25，质量要求：8］

第八步:再评价提议

发起传感器对提议PC’2-1、PC’2-2进一步评价，因为接收到的提议质量要求更高、完成时间更早：

PC’2-1：［M42，开始时间：18，完成时间：24，质量要求：6］

PC’2-2：［M43，开始时间：20，完成时间：25，质量要求：8］

q=72、c=58;响应传感器的最迟完成时间为25，则总持续时间t=47、E=0.720 5。

局部效用增益

故PC’2-1、PC’2-2可被接受，综合效用为0.130 5，而且这是一个比之前更好的方案。在三步协议中，发起传感器继续协商并且尝试找到一个更好的方案，由于篇幅有限这里不再赘述。

5 结论

根据传感器指示交接问题的本质，研究分析了指示交接中多个传感器针对多个协作任务怎样协商以进行更好的任务调度的问题，提出了基于分布搜索的多维协商机制，并通过一个实例分析了多传感器指示交接的任务调度过程，有效地解决了多个传感器针对多个协作任务怎样调度的问题，使“指示任务怎样执行”的难题得到合理的解决。

［1］孙殿星，王学伟，周晓东，等.雷达/红外复合制导系统雷达对红外引导评估［J］.舰船电子工程，2010，30（4）: 33-35.

［2］王国宏.分布式检测、跟踪及异类传感器数据关联与引导研究［D］.北京:北京航空航天大学，2002.

［3］王国宏，毛士艺.ESM对2D雷达引导性能分析［J］.航空学报，2002，23（4）:298-301.

［4］王国宏，何友，毛士艺.IRST对3D雷达引导性能分析［J］.电子学报，2002，30（12）:1737-1740.

［5］王建明，刘国朝.舰载雷达与ESM协同探测方法研究［J］.舰船电子对抗，2007，30（6）:11-15.

［6］彭锐晖，王树宗，吕永胜，等.异地配置下ESM对2D雷达的引导分析［J］.现代雷达，2009，31（1）:13-16.

［7］吕永胜，王树宗，彭锐晖，等.异地配置下IRST对3D雷达的引导分析［J］.红外与激光工程，2008，37（5）: 911-915.

［8］Zhang X Q，Lesser V，Podorozhny R.New Result on Cooperative，Multi-Step Negotiation over a Multi–Dimensional U-tility Function［C］//AAAI Fall Symposium on negotiation Methods for Autonomous Cooperative Systems，Falmouth MA USA，Nov.2001:3-6.

［9］Charles L O，Rauenbusch T.Dynamic Negotiateon［EB/OL］. http://www.ai.sri.com/～rauenbus/papers/aaai02-edmonton. pdf，2002.7:1-5.

［10］Soh L K，Tsatsoulis C.Allocation Algorithms in Dynamic Negotiation-Based Coalition Formation［EB/OL］.http: //www.isi.edu/～szekely/antsebook/ebook/institutions/kansas/ Soh_AAMAS02.pdf，2002:2-3.

［11］Soh L K.A Negotiation-Based Coalition Formation Model for Agents with Incomplete Information and Time Constraints［EB/OL］.http://www.dodreports.com/ada461997. 2002.1:3-7.

［12］Lesser V，Ortiz Jr.，Charles，et al.Distributed Sensor Networks:A Multiagent Perspective［M］.Kluwer Academic Publishers，2003:56-81.

［13］Ravindran B，Devarasetty R K，Shirazi B.Aaptive Resource Management Algorithms for Periodic Tasks in Dynamic Real-Time Distributed Systems［J］.Joural of Parallel and Distributed Computing，2002，62（10）:1527-1547.

［14］Lopez J M M，Rodriguez F J J，Corredera J R C.Cooperative Management of Netted Surveillance Sensors［C］//1997 IEEE International Conference on Computational Cybernetics and Simulation，1997（1）:845-850.

［15］黄树彩.区域防空传感器资源优化分配算法研究［D］.西安:空军工程大学，2005.

Negotiation Mechanism of Sensor Indication and Handover Based on Distributed Search

YANG Tao，XU Yun-shan，TANG Shu-juan，LUO Wen-tao
（School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China）

Aiming at the problem of“How the indication task should be executed”，on the basis of the actual process of indication and handover，the scheduling policy of multi-sensor in the scenario of multi-tasks cooperative is been researched and the negotiation mechanism of sensor indication and handover based on distributed search is been presented.The algorithm keeps looking for the scheduling policy which provides the largest aggregate utility and optimizes the scheduling process of multisensor，multi-tasks indication and handover by iterating and updating of consultation function.Finally，the simulation result verifies the rationality and effectiveness of the proposed method，the efficiency of sensor cooperation has been improved，and what have been done in this paper lay the foundation of research on the indication and handover.

sensor indication and handover，distributed search，sensor cooperation，consultation function，comprehensive utility

TP273

A

1002-0640（2015）01-0042-07

2013-12-15

2014-02-19

空军工程大学科研创新基金资助项目（XS1101011）

杨涛（1990-），男，陕西西安人，硕士研究生。研究方向：探测预警与指挥引导。