| 摘要: |
| 分布式仿真系统中，如何使计算节点彼此间通信量尽可能小，是实体节点分配问题研究的内容。针对该问题提出一种基于规则的启发式两阶段实时求解算法。第一阶段构建最小期望事件数量的目标分配模型并进行求解，即根据连通图理论将原问题分解为多个子问题，结合缓存、分治和过滤优选策略，设计递归算法求解子问题，最后得到覆盖所有实体的事件最小集。第二阶段实现分箱算法，将最小集中单个事件关联的实体尽量分配至相同计算节点，最终得到实体节点分配关系。实际应用表明，相比常见的顺序分配策略，该算法能显著减小分布式仿真系统的跨节点网络通信，从而提升仿真效率。该算法还能在秒级耗时生成分配方案，特别适用于包含大量实体的复杂场景分布式仿真。 |
| 关键词: 分布式仿真 实体节点分配 实时求解 |
| DOI： |
|
| 基金项目:中国航天科技集团自主研发项目 |
|
| Real-Time Solving Algorithm for Entity Node Assignment Problem in Distributed Simulation System |
| WANG Hongsen,LUO Rubin,LIU Zhaoyang |
| (Beijing Institute of Astronautical Systems Engineering, Beijing 100076, China) |
| Abstract: |
| In distributed simulation systems, how to minimize communications between computing nodes is the research topic of entity node assignment. A rule-based heuristic two-stage real-time algorithm for this problem is proposed. In the first stage, an optimization model with minimum expected event number is constructed and solved. Firstly, the original problem is decomposed into multiple subproblems according to the connected graph theory. Secondly, combined with caching, divided and conquer, filter and selection strategies, a recursive algorithm is designed to solve the subproblems. Then, a minimum event set covering all entities is obtained. In the second stage, a binning algorithm is proposed with the goal of trying to allocate entities connected with the same event to the same computing node, ultimately obtaining the entity node assignment solution. Practical applications show that compared to common sequential assignment policy, this algorithm can significantly reduce network communications between computing nodes in distributed simulation systems, thereby improving simulation efficiency. This algorithm can also generate an assignment solution in seconds, making it particularly suitable for distributed simulations of complex scenes containing a large number of entities. |
| Key words: Distributed simulation Entity node assignment Real-time solving |