基于合同网的分布式卫星系统任务优化分配研究

Research on Task Optimal Allocation for Distributed Satellites System Based on Contract Net Protocol

面向未来分布式卫星系统(DSS)自主协作运行模式,对DSS任务协作中的优化分配问题进行了分析和描述,提出了基于协商的任务优化分配体系结构,并由此给出任务组的概念,通过集覆盖理论将任务分配问题转化为集覆盖问题。从而引入合同网协议,以系统完成任务目标的总耗能最少为原则,加入限定卫星可回应任务数的约束后,提出了一种基于合同网的严格启发式优化分配算法对问题进行求解。同时,证明了算法搜索结果的上确界;分析了算法的收敛性和时间复杂度。该算法具有分布性,搜索空间缩减快,适合于中小规模问题的任务分配。

Considering the characteristics of autonomous operation cooperatively for distributed satellites system （DSS） in future, the task optimal allocation architecture model for DSS based on negotiation was put forward by analyzing and describing the problem of task allocation for DSS. Based on it, the concept of task coalition was defined and the task allocation was described as a set-covering problem by set-covering theory. Consequently, with the principle of lowest general energy-consumption for completing task, a greedy heuristic algorithm for task allocation was proposed, which conformed to the contract net protocol and limited the number of bidding sub-tasks. At same time, the convergence and supremum of the algorithm were proved, and the asymptotic time complexity was analyzed. At last, a simple example was give. With the property of the distributed calculation and quick reduction of the search space, the algorithm is suitable for task distributed problem solving for small and middle scale problem of task allocation.