两段探测目标的传感器任务调度问题规划模型及算法摘要.docxVIP

两段探测目标的传感器任务调度问题规划模型及算法李建平，张晗1，罗永1，朱承2，何文涛2(1. 国防科学技术大学理学院，湖南长沙 41073； 2. 国防科学技术大学信息系统工程重点实验室，湖南长沙 41073)摘要：研究了一类特殊的传感器资源调度问题，其中传感器对一个目标进行跟踪时需要有先后两段探测。分析了跟踪目标的探测次数、时间间隔和传感器资源等约束条件，用跟踪目标的重要程度之和作为目标函数，建立了一个规划的数学模型。再利用变换将其转化为线性整数规划模型。利用割平面法求解得出最优调度策略，能在工作量饱和的情况下合理调度传感器资源。为提高求解速度，提出了对应的模拟退火算法。通过对一些不同规模实例的求解，在资源利用率和算法的求解速度等指标上，与割平面法及遗传算法进行对比分析，验证了模型的有效性和模拟退火算法求解的高效性。关键词：传感器；任务调度；0-1规划；模拟退火算法；遗传算法中国分类号：O221. 4 文献标志码：文章编号：The 0-1 Programming Model and Algorithm for The Problem of Sensor Task Scheduling for Double DetectionLI Jian-ping1, ZHANG Han1, LUO Yong1, ZHU Cheng2, HE Wen-tao2(1.Institute of Science, National university of defense technology, Changsha 41073, china; 2. Science and Technology on Information Systems Engineering Laboratory, National university of defense technology, Changsha 41073, china)Abstract:This paper focuses on a special sensor scheduling problem which a target need to be detected two times in sequence and analyzes the constraint conditions including detected times, the interval between two detections, and the resource restrict of sensor. A 0-1 programming model is established and transformed to a 0-1 liner integer model whose objective function is the sum of degree of importance. The optimal solution is obtained by cutting plane algorithm. We propose a corresponding simulated annealing algorithm to improve the speed of solving and use it to solve some examples.We compareit with cutting plane algorithm and genetic algorithm by resource utilization and the speed of solving. It proves that the model is valid and the simulated annealing algorithm is high-efficiency.Key words:sensor; Task scheduling；0-1 Programming；Simulated annealing algorithm；Genetic algorithm传感器的任务调度是根据一定优化准则，在确定的时间区间内，为传感器网络中的传感器资源安排跟踪任务，以满足对多个移动目标的跟踪要求，从而达到某项或某些指标最优。传感器资源调度能够有效地提高资源利用效率。在军事问题中，合理的传感器调度，例如雷达，可以提高军方的防御能力。在研究的问题中，传感器对目标进行跟踪时需要先后进行两段探测，每段都有最短时长，若一个目标两段探测由不同的传感器完成，则两段探测之间有最短时间间隔。不同移动方向的目标有不同的重要程度，由于传感器资源的限制，当目标过多时，必须有选择地跟踪重要目标，由此产生了这种两段探测目标的传感器资源调度问题。目前，许多传感器资源调度问题主要