分布式仿真系统实体节点分配问题实时求解算法.pdf

第8卷 第2期2 0 2 4年3月宇航总体技术A s t r o n a u t i c a lS y s t e m sE n g i n e e r i n gT e c h n o l o g yV o l.8N o.2M a r.2 0 2 4收稿日期:2 0 2 3-1 1-0 1 修订日期:2 0 2 4-0 2-2 9基金项目:中国航天科技集团自主研发项目作者简介:王虹森(1 9 8 9),男,博士,工程师,主要研究方向离散事件仿真、体系仿真。通信作者简介:罗汝斌(1 9 8 1),男,硕士,研究员,主要研究方向为体系仿真。刘朝阳(1 9 9 1),男,硕士,高级工程师,主要研究方向为分布式仿真、软件工程化。分布式仿真系统实体节点分配问题实时求解算法王虹森,罗汝斌,刘朝阳(北京宇航系统工程研究所,北京1 0 0 0 7 6)摘 要:分布式仿真系统中,如何使计算节点彼此间通信量尽可能小,是实体节点分配问题研究的内容。针对该问题提出一种基于规则的启发式两阶段实时求解算法。第一阶段构建最小期望事件数量的目标分配模型并进行求解,即根据连通图理论将原问题分解为多个子问题,结合缓存、分治和过滤优选策略,设计递归算法求解子问题,最后得到覆盖所有实体的事件最小集。第二阶段实现分箱算法,将最小集中单个事件关联的实体尽量分配至相同计算节点,最终得到实体节点分配关系。实际应用表明,相比常见的顺序分配策略,该算法能显著减小分布式仿真系统的跨节点网络通信,从而提升仿真效率。该算法还能在秒级耗时生成分配方案,特别适用于包含大量实体的复杂场景分布式仿真。关键词:分布式仿真;实体节点分配;实时求解 中图分类号:V 5 5 7文献标志码:A文章编号:2 0 9 6-4 0 8 0(2 0 2 4)0 2-0 0 2 4-0 8R e a l-T i m eS o l v i n gA l g o r i t h mf o rE n t i t yN o d eA s s i g n m e n tP r o b l e mi nD i s t r i b u t e dS i m u l a t i o nS y s t e mWAN G H o n g s e n,L UOR u b i n,L I UZ h a o y a n g(B e i j i n gI n s t i t u t eo fA s t r o n a u t i c a lS y s t e m sE n g i n e e r i n g,B e i j i n g1 0 0 0 7 6,C h i n a)A b s t r a c t:I nd i s t r i b u t e ds i m u l a t i o ns y s t e m s,h o wt om i n i m i z e c o mm u n i c a t i o n sb e t w e e nc o m p u t i n gn o d e s i s t h er e s e a r c ht o p i co fe n t i t yn o d ea s s i g n m e n t.Ar u l e-b a s e dh e u r i s t i ct w o-s t a g er e a l-t i m ea l g o r i t h mf o r t h i sp r o b l e mi sp r o p o s e d.I nt h ef i r s ts t a g e,a no p t i m i z a t i o nm o d e lw i t hm i n i m u me x p e c t e de v e n tn u m b e r i s c o n s t r u c t e da n ds o l v e d.F i r s t l y,t h eo r i g i n a l p r o b l e mi sd e c o m p o s e d i n t om u l t i p l es u b p r o b l e m s a c c o r d i n g t o t h e c o n n e c t e dg r a p ht h e o r y.S e c o n d l y,c o m b i n e dw i t hc a c h i n g,d i v i d e da n dc o n q u e r,f i l t e ra n ds e l e c t i o ns t r a t e g i e s,ar e c u r s i v ea l g o r i t h mi sd e s i g n e dt os o l v et h es u b p r o b l e m s.T h e n,am i n i m u me v e n t s e t c o v e r i n ga l l e n t i t i e s i so b t a i n e d.I nt h es e c o n ds t a g e,ab i n n i n ga l g o r i t h mi sp r o p o s e dw i t h t h eg o a l o f t r y i n g t oa l l o c a t e e n t i t i e s c o n n e c t e dw i t h t h e s a m e e-v e n t t o t h es a m ec o m p u t i n gn o d e,u l t i m a t e l yo b t a i n i n gt h ee n t i t yn o d ea s s i g n m e n t s o l u t i o n.P r a c-t i c a l a p p l i c a t i o n ss h o wt h a t c o m p a r e dt oc o mm o ns e q u e n t i a l a s s i g n m e n tp o l i c y,t h i sa l g o r i t h mc a ns i g n i f i c a n t l yr e d u c en e t w o r kc o mm u n i c a t i o n sb e t w e e nc o m p u t i n gn o d e si nd i s t r i b u t e ds i m u l a t i o ns y s t e m s,t h e r e b y i m p r o v i n gs i m u l a t i o ne f f i c i e n c y.T h i s a l g o r i t h mc a na l s og e n e r a t ea na s s i g n m e n ts o l u t i o n i ns e c o n d s,m a k i n gi tp a r t i c u l a r l ys u i t a b l ef o rd i s t r i b u t e ds i m u l a t i o n so fc o m p l e xs c e n e sc o n t a i n i n ga l a r g en u m b e ro f e n t i t i e s.K e yw o r d s:D i s t r i b u t e ds i m u l a t i o n;E n t i t yn o d ea s s i g n m e n t;R e a l-t i m es o l v i n g 第2期分布式仿真系统实体节点分配问题实时求解算法0 引言基于离散事件的多主体仿真系统广泛应用于灾害救援、物资配送、安防反恐和在轨服务1等社会经济生活的多个领域。该类仿真系统仿真引擎的核心是调度离散事件,离散事件不仅驱动系统运行,也完成实体间的交互2。随着研究问题规模变大和实体执行逻辑愈发复杂,这类问题对计算性能的要求越来越高。使用单台计算机仿真复杂场景通常需要花费大量时间,而采用分布式仿真技术在多个计算节点开展并行仿真可以显著提升仿真效率。在分布式仿真系统中,同一计算节点内的事件交互通常采用方法调用,跨计算节点的事件交互则需通过网络通信。网络通信涉及离散事件的封装、发送、传输、接收和解析,加上网络路由不确定性时延和操作系统进程调度等不确定性因素,对分布式仿真效率的影响巨大3。一个复杂仿真场景包含成百上千的实体,如何制定实体和计算节点的分配方案,以减少跨节点网络通信是值得研究的问题。特别是在想定方案分析、大样本仿真等业务中,还要求实时给出分配方案。该问 题 属 于 一 种 扩 展 的 二 次 多 背 包 问 题(Q u a d r a t i cM u l t i p l eK n a p s a c kP r o b l e m,QMK P)。QMK P研究4给定多个物品,每个物品i的利润为pi,权重为wi,并给定多个背包,每个背包K的容量为WK,目标为将物品放入每个背包且放入背包物品的利润值总和最大,该利润除了每个物品的单独利润pi,还包括任两个物品间的二次利润(或联合利润)pi j。对应实体节点分配问题,计算节点即是背包,实体即是物品,二次利润为实体间离散事件期望交互次数。该问题属于N P完全组合优化决策问题,当实体和节点的数量增多时,计算复杂度呈指数规模增长。文献 4最早在背包问题的基础上开展了QMK P研究,并提出3种元启发式求解算法。此后,学者们往往也采用元启发式算法在合理的时间内为QMK P求得近似解。代表性算法包括改进的遗传算法5-6、蜂群算法7、贪婪算法8和迭代响应搜索9等。目前,QMK P相关研究不多,尚未有文献提出某种精确型算法。当决策变量规模变大时,元启发式算法可能需要花费很长时间。在实际工程应用中,为满足实时性要求,分布式仿真系统实体节点分配常常采用随机分配或顺序分配策略1 0。本研究针分布式仿真,结合实体和节点分配约束特点,提出一种基于规则的启发式两阶段实时求解算法,显著提升了复杂场景的分布式仿真推演效率。1 模型建立结合大型分布式仿真系统实体节点分配应用背景,设定实体节点分配问题如下。1)所给定实体为一个仿真想定所包含的多个实体。任两个实体间可能存在事件交互关系,该交互关系是仿真模型构建阶段确定的,是已知的。2)所给定节点为多个分布式计算节点。为充分利用处理器性能,单个节点分配实体数不超过节点处理器线程数,即节点实体容量等于处理器线程数。此时,不同的分配方案不太影响节点上实体计算速度,主要影响网络通信量。3)最终分配方案需将所有实体分配到节点,使得单个节点内实体事件交互次数尽可能多,跨节点的实体事件交互次数尽可能少。在启动仿真之前无法预知每类事件的实际交互次数,所以设每类事件的产生和响应概率相等,则分配目标等价于使得单个节点内实体尽量处理相同类别事件,跨节点实体尽量处理不同类别事件。该问题相比经典的QMK P放松了部分约束条件,为达到实时性要求,设计基于规则的启发式两阶段求解算法。第一阶段,将原问题提取并抽象为一类静态目标分配问题1 1,为事件分配实体,根据事件和实体的处理关联关系构建最小期望成本1 2最优化模型,求解覆盖所有实体的事件最小集。最优化模型为m i nmi=1f(xi j)f(xi j)=1,nj=1xi j10,nj=1xi j=0s t.Am a t r i x=ai jmn,ai j=0,1 i=1,2,m j=1,2,nnj=1ai jxi jb,i=1,2,mmi=1ai jxi j1,j=1,2,nxi j=0,1(1)其中,事件总数为m,实体总数为n,节点实体容量为b,决策变量为xi j。xi j=0表示事件i处理关系不覆盖实体j,xi j=1表示事件i处理关系覆盖实体j。Am a t r i x为已知的事件和实体处理关联矩52 宇航总体技术2 0 2 4年3月阵,其中元素ai,j=0表示实体j不会处理事件i,ai,j=1表示实体j会处理事件i。目标函数实际是最小化事件数量,最优解中单个事件所关联实体是尽可能多的。一般而言,该问题最优解有多个。第二阶段是实现分箱算法,将最小集中单个事件关联的实体尽量分配至同一节点,最终得到实体节点分配关系。2 模型求解2.1 总体计算流程第一阶段的目标分配问题也属于N P完全组合优化决策问题1 3,所以为同时满足大型应用规模和秒级计算速度的要求,提出一种基于规则的启发式算法。总体计算流程如图1所示,共涉及5个关键算法。在第一阶段,采用分治策略进行求解。首先根据连通图理论将原问题分解为多个子问题,然后对每个子问题单独求解后合并得到原问题的解。在求解子问题的过程中会构建和求解孙问题,再优选孙问题的解。在第二阶段,采用分箱算法求解实体节点分配方案。图1 总体计算流程F i g.1 G e n e r a l c a l c u l a t i o np r o c e s s后续算法使用关联二元组数组表示关联矩阵。如果关联矩阵中ai,j=1,则二元组数组存在元素(i,j),两者一一对应并可相互转换。例如有关联矩阵 (1,0),(0,1),则对应二元组数组为(0,0),(1,1)。2.2 生成子问题关联二元组数组在第一阶段目标分配问题中,事件实体的关联关系实际上构成二部图(B i p a r t i t eG r a p h)。二部图中顶点集可分为两个不相交子集,仅不同子集中的顶点间存在边。考虑到大规模场景的事件实体关联矩阵一般是稀疏的,那么将原始二部图分解为多个连通子图,从而构建子问题。分解示意如图2所示,事件13和实体12构成连通子图,事件45和实体34构成连通子图,两个连通子图间无边连接。显然各连通子图的可行解无交叉,所以将连通子图对应的子问题最优解合并后,得到的解一定是原问题的最优解。图2 连通子图划分示意F i g.2 C o n n e c t e ds u b g r a p hd i v i s i o ns a m p l e后续算法关键符号及含义如表1所示。表1 关键符号及含义T a b.1 K e ys y m b o l sa n dm e a n i n g s符号含义 s e t集合 v e c t o r数组,通过索引号i取值为v e c t o rim a p键值对,键为m a p.k e y,值为m a p.v a l u e(,)t u p l e二元组,前后值为t u p l e.f i r s t,t u p l e.s e c o n ds i z e(x)求x的元素数量,x为集合、数组或键值对I N T_MA X极大正整数实体事件关联二元组数组分解算法如下所示。算法1:实体事件关联二元组数组分解算法输入:事件实体关联二元组数组A,事件总数m,实体总数n输出:多个事件实体子关联二元组数组Sl,l=1,2,1 初始化每个事件关联实体集合Ti=,i=0,1,m-12 循环迭代k=0,1,s i z e(A)-13 向TAk.f i r s t添加TAk.s e c o n d4 初始化实体连通集合的数组L=,元素为 5 循环迭代i=0,1,m-16 初始化合并索引数组M=7 循环迭代k=0,1,s i z e(L)-18 如果Ti与Lk有交集9 向M添加k62 第2期分布式仿真系统实体节点分配问题实时求解算法1 0 如果M为空1 1 向L中添加Ti1 2 否则1 3 向LM0 中添加Ti1 4 循环迭代k=s i z e(M)-1,2,11 5 向LM0 中 添 加LMk ,并 从L删除LMk 1 6 初始化二元组数组Sl=,元素为(),l=0,1,s i z e(L)-11 7 循环迭代k=0,1,s i z e(A)-11 8 循环迭代l=0,1,s i z e(L)-11 9 如果Ll包含Ak.s e c o n d2 0 向Sl中添加Ak2.3 化简子问题关联二元组数组为松弛单个节点的分配实体不能超过数目b的约束,对关联二元组数组进行转换:如果某个事件i的关联实体总数为di,且di大于b,则去除事件i,新建Cbdi个虚拟事件,每个虚拟事件的关联实体为从di个实体中挑选b个不同元素形成的组合。然后,精简子问题关联二元组数组。如果一个事件i的关联实体是另一个事件j关联实体的子集或者相同,则仅保留事件j,删除事件i。显然,如果最优解包含事件i,则将事件i替换为j,目标函数值不变,仍然是最优解。以上两步对关联二元组数组的处理算法比较简单,此处不再赘述。由此得到单个子问题的模型为m i npi=1f(xi j)f(xi j)=1,qj=1xi j10,qj=1xi j=0s t.Sm a t r i x=si jpq,si j=0,1i=1,2,p j=1,2,qpi=1si jxi j1,j=1,2,qxi j=0,1(2)其中,事件总数为p,实体总数为q。一般而言,pm,qn。2.4 求解子问题对于该子问题,目标函数为非线性函数,无法采用经典的匈牙利算法求解。结合缓存、分治和过滤优选策略,设计快速递归迭代算法,如下所示。算法2:递归求解算法输入:事件实体关联二元组数组S,已分配事件数组X=,事件总数p,实体总数q输出:已分配事件数组X全局变量:缓存键值对H=,H.k e y为关联二元组数组,H.v a l u e为分配事件数组最优解预置参数:孙问题关联二元组数组规模阈值1 如果S为空2 返回3 如果H的键包含当前输入的S4 X赋值对应H.v a l u e,并返回5 初始化实体所能关联事件数组Wj=,j=0,1,q-16 循环迭代k=0,1,s i z e(S)-17 向WSk.s e c o n d添加Sk.f i r s t8 初始化事件最少数量wm i n=I N T_MA X9 循环迭代j=0,1,q-11 0如果s i z e(Wj)小于wm i n1 1 wm i n=s i z e(Wj)1 2 初始化孙问题的关联二元组数组G=,元素为()1 3 循环迭代j=0,1,q-11 4如果s i z e(Wj)等于wm i n1 5 循环迭代k=0,1,wm i n-11 6 向G中添加(Wjk,j)1 7 如果s i z e(G)大于1 8 跳出循环1 9 求解G关联孙问题,得到其所有可行解XG(见算法3)2 0 对XG进行过滤优选,形成较优解XP(见算法4)2 1 初始化事件最少数量wm i n=I N T_MA X2 2 循环迭代i=0,1,s i z e(XP)-12 3复制XPi为XI2 4如果s i z e(XI)大于等于wm i n2 5 继续循环2 6 初始化XI能关联的实体集合V=2 7 循环迭代k=0,1,s i z e(S)-12 8 如果XI包含Sk.f i r s t2 9 向V中添加Sk.s e c o n d3 0 初始化递归迭代的关联二元组数组SR3 1 循环迭代k=0,1,s i z e(S)-13 2 如果XI不包含Sk.f i r s t并且V不包含Sk.s e c o n d3 3 向SR中添加Sk3 4 将SR,XR=作为输入,递归调用算法2,输出XR3 5 向XI中添加XR所有元素3 6 如果s i z e(XI)小于wm i n3 7 wm i n=s i z e(XI),X=XI3 8 向H中添加键值对算法2中,缓存策略体现在第3、4和3 8步。在组合遍历迭代时,某个关联二元组数组对应的最优解可能在前序迭代中已经算出,将其缓存为键值对,直接查询以加速计算。分治策略体现在第1 21 9步,构建和求解决策变量规模较小的孙问题。过滤优选策略体现在第2 0步,优选孙问题可 行解。所构建孙问题与子问题模型(2)相同,72 宇航总体技术2 0 2 4年3月但决策变量更少。孙问题的关联二元组数组G是子问题S的子集。G的特征是其完全包含了G中实体相关的事件实体关联关系,即差集S-G不会包含G中的实体。在迭代遍历孙问题所有可行解的基础上可以求得子问题的最优解基于以下结论。G关联孙问题的所有可行解中至少有一个是S关联子问题最优解的子集。若G关联孙问题的所有可行解都不是S关联子问题最优解的子集,那么S关联子问题最优解不是G关联孙问题的可行解,由于差集S-G不会包含G中的实体,那么S关联子问题最优解不是S关联子问题的可行解,因此矛盾,结论可证。在构建关联二元组数组G时,优先选择关联事件数目最小的那些关键实体,以减少外层迭代的循环次数,提升计算效率。例如,有7条与4个实体相关的关联关系:实体1与事件1,2关联,实体2与事件2,3关联,实体3与事件1,3,4关联。那么实体1和实体2关联的事件数是2,实体3关联事件数是3。根据规则,关联事件数最小为2,则提取实体1和实体2相关的关联关系构成G。孙问题的求解算法如下所示。该求解算法与算法2相似,主要区别是算法2的关键实体是多个,算法3的关键实体是1个。算法3从一个关键实体开始递归迭代,找到孙问题所有的可行解。算法3:算法2第1 9步关联孙问题求解算法输入:事件实体关联二元组数组G,所有可行解 数组XG=,元素为 ,事件总数u,实体总数v输出:所有可行解数组XG全局变量:最小事件数量w*=I N T_MA X1 如果G为空2 返回3 初始化实体所能关联事件数组Wj=,j=0,1,v-14 循环迭代k=0,1,s i z e(G)-15 向WGk.s e c o n d添加Gk.f i r s t6 初始化事件最少数量wm i n=I N T_MA X,事件集合Y=7 循环迭代j=0,1,v-18 如果s i z e(Wj)小于wm i n9 wm i n=s i z e(Wj),Y=Wj1 0 循环迭代i=0,1,s i z e(Y)-11 1 复制XG为X,并向X中添加Yi1 2 初始化关联实体集合V=1 3 循环迭代k=0,1,s i z e(G)-11 4 如果X包含Gk.f i r s t1 5 向V中添加Gk.s e c o n d1 6 如果s i z e(V)等于实体总数v1 7 如果s i z e(X)小于w*1 8 w*=s i z e(X)1 9 向XG添加X2 0 继续循环2 1 初始化递归迭代的关联二元组数组GR=2 2 循环迭代k=0,1,s i z e(G)-12 3 如果X不包含Gk.f i r s t,并且V不包含Gk.s e c o n d2 4 向GR中添加Gk2 5 将GR和X作为输入参数,递归调用算法3,输出X孙问题的可行解非常多,全部遍历非常耗时,采用过滤优选是保证实时返回局部最优解的关键。孙问题可行解过滤优选算法如下所示。算法4:算法2第2 0步孙问题可行解过滤优选算法输入:事件实体关联二元组数组G,所有可行解数组XG,事件总数u,实体总数v输出:优选可行解数组XP预置参数:1,2,3,4分别对应不同长度解的挑选个数1 如果XG为空2 返回3 如果s i z e(XG)等于14 XP=XG,返回5 初 始 化 实 体 所 能 关 联 事 件 数 组Wj=,j=0,1,v-16 循环迭代k=0,1,s i z e(G)-17 向WGk.s e c o n d添加Gk.f i r s t8 初始化每个事件关联实体集合Ti=,i=0,1,u-19 初始化每个实体能关联事件数wj=0,j=0,1,v-11 0 循环迭代k=0,1,s i z e(G)-11 1 向TGk.f i r s t添加Gk.s e c o n d,WGk.s e c o n d加11 2 初始化可行解覆盖的实体集合数组Z=,元素为 1 3 初始化事件最少数量wm i n=I NT_MA X1 4 循环迭代i=0,1,s i z e(XG)-11 5 向Z添加空集合 1 6 循环迭代k=0,1,s i z e(XGi)-11 7 向Z的最后一个集合元素中添加TXGi k1 8 如果s i z e(XGi)小于wm i n1 9 wm i n=s i z e(XGi)2 0 初始化过滤控制器D=,键为事件数量,值为 2 1 初始化每个可行解的得分元组数组C=,元素为()2 2 循环迭代k=0,1,s i z e(XG)-12 3 如果D.k e y为s i z e(XGk)的集合中包含Zk2 4 继续循环2 5 向D.k e y为s i z e(XGk)的集合中添加Zk2 6 初始化得分e为0.02 7 循环遍历l=0,1,s i z e(Zk)-12 8 e加上1.0/wZk l2 9 向C中添加元组(k,e)3 0 对数组C照元组的后值进行降序排列,形成数组F3 1 循环迭代k=0,1,s i z e(F)-13 2 如果1大于0,并且s i z e(XGFk.f i r s t)等于wm i n3 3 向XP添加XGFk.f i r s t,1减13 4 循环迭代k=0,1,s i z e(F)-182 第2期分布式仿真系统实体节点分配问题实时求解算法3 5 如果2大于0,并且s i z e(XGFk.f i r s t)等于wm i n+13 6 向XP添加XGFk.f i r s t,2减13 7 循环迭代k=0,1,s i z e(F)-13 8 如果3大于0,并且s i z e(XGFk.f i r s t)等于wm i n+23 9 向XP添加XGFk.f i r s t,3减14 0 循环迭代k=0,1,s i z e(F)-14 1 如果4大于0,并且s i z e(XGFk.f i r s t)大于wm i n+24 2 向XP添加XGFk.f i r s t,4减1过滤优选算法核心有两点:过滤和优选。过滤是指对于拥有相同事件数量且相同实体覆盖范围的多个可行解,只保留一个。体现在算法中第2 02 5步,具体由D实现。例如,有4个解,事件分别 是 1,2,3,4,1,5,6,3,7,8 ,事件 1,2覆盖实体 1,2,3,4,事件 3,4覆盖实体 1,2,3,4,事件1,5,6 覆 盖 实 体 1,2,3,4,5,事 件3,7,8覆 盖 实 体 1,2,3,5,6。那 么,先判断拥有2个事件的解,1,2和 3,4覆盖实体相同,则保留事件 1,2,删除事件 3,4,显然,如 果 最 优 解 包 含 3,4,则 将 3,4换为 1,2一定也是最优解。再判断拥有3个事件的解,1,5,6和 3,7,8覆盖实体不同,则两者都保留。优选是指对过滤后的解进行统一打分排序,再挑选得分较高的解参与后续迭代。体现在算法中第2 1和第2 64 2步。打分规则是(第2 72 8步):该解覆盖的每个实体的关联事件数量倒数之和。例如,有2个解,事件 1和 3,4,事件1覆盖实体 1,2,事 件 3,4覆盖实 体1,3,实体1在关联二元组数组中涉及3个事件,实体2涉及4个事件,实体3涉及5个事件。那么,解 1得分是1/3+1/4=7/1 2,解 3,4得分是1/3+1/5=8/1 5,由于7/1 28/1 5,所以解 1排在解 3,4前面。该打分策略采用加法是基于:若解覆盖实体越多,该解越有可能靠近最优解,那么这时加项越多,分值越大。采用倒数是基于:若解覆盖实体数目相同,这时加项数量相同,选择拥有较小关联事件数目的实体更可能靠近最优解,通过采用取倒数的方式,该解得分越高。算法4中有4个预置参数1、2、3和4,分别对应不同长度解的挑选个数,不同的预置参数设置影响计算耗时。2.5 合并子问题的解对每个子问题分别求解,合并子问题的解就得到原问题的最优解。设最优解事件数组为X*,数组元素为事件编号,X*覆盖的实体集合的数组为T*,数组元素为实体的集合,与X*顺序对应。2.6 求解分配方案在事件最小集的基础上,执行分箱算法如下,将每个实体分配至特定的节点,得到最终分配方案。算法5:求解分配方案的分箱算法输入:最优解事件数组X*,X*覆盖的实体集合的数组T*,节点总数t,单个节点实体容量b输出:每个节点中实体编号集合的数组E=,元素为 1 为E中添加t个空集合 2 初始化剩余实体数组R=3 循环迭代s i z e(T*)大于04 初始化布尔标记变量f为假5 循环迭代i=0,1,t-16 如果Ei 为空,或Ei 与T*0 并集元素总数为b7 将T*0所有元素添加至Ei8 将f设置为真9 跳出循环1 0 如果f为假1 1 循环迭代j=0,1,s i z e(T*0)-11 2 向R中添加T*0 j1 3 循环迭代i=1,2,s i z e(T*)-11 4 循环迭代j=0,1,s i z e(T*0)-11 5 如果T*i包含T*0 j1 6 从T*i删除T*0 j1 7 从T*中移除T*01 8 对T*按照元素长度降序排序1 9 循环迭代s i z e(R)大于02 0 循环迭代i=t-1,1,02 1 如果s i z e(Ei)小于b2 2 初始化个数变量n为b-s i z e(Ei)2 3 如果n大于s i z e(R)2 4 n=s i z e(R)2 5 循环迭代j=0,1,n-12 6 向Ei中添加Rj2 7 循环迭代j=0,1,n-12 8 在R中移除R03 应用试验结合实际应用需求在分布式仿真平台上编制仿真想定,共包含1 3 0个事件和1 0 5个实体。梳理仿真模型得到共5 0 0条事件实体处理关联关系。关联11 5个实体的事件数分别是 2 8,2 2,1 7,1 7,1 9,9,6,2,5,3,0,1,0,0,1。关联11 5个事件的实体数分别是 0,7,2 6,2 9,1 3,1 1,8,1,4,1,1,1,1,0,1。92 宇航总体技术2 0 2 4年3月设单个节点实体容量b=6,松弛该约束后,形成了4 28 0 2条事件实体关联关系,再化简后形成3 67 6 5条关联关系。采用C+语言实现第一阶段算法,并设置3组预置参数,如表2所示。其中F A S T组和M E D I组得到局部最优解,S L OW组实际上得到全局最优解。计算节点C P U使用I n t e l酷睿i 7-7 7 0 0K,实际运行对比结果如表3所示。3个组的最优解和最表2 第一阶段3个组预置参数设置T a b.2 T h r e ep r e s e tp a r a m e t e rg r o u p s i nt h e f i r s t s t a g e组名预置参数设置F A S T=2 0 0,1=1,2=1,3=0,4=0ME D I=2 0 0,1=4,2=2,3=1,4=0S L OW=2 0 0,1=2=3=4=1 0 00 0 0优值都 相 同,说 明 都 找 到 了 全 局 最 优 解,而 且F A S T组仅耗时0.4 2s。对最优解的覆盖实体进行检验,最优解能完全覆盖1 0 5个实体。表3 第一阶段3个组计算结果T a b.3 R e s u l t so f t h r e eg r o u p s i nt h e f i r s t s t a g e组名最优解最优值耗时F A S T1 0,1 4,1 8,2 7,3 2,4 2,4 6,5 0,5 4,5 7,5 9,6 3,6 4,6 9,7 5,8 0,8 7,9 2,1 0 2,1 1 5,1 2 1,1 3 02 20.4 2sME D I1 0,1 4,1 8,2 7,3 2,4 2,4 6,5 0,5 4,5 7,5 9,6 3,6 4,6 9,7 5,8 0,8 7,9 2,1 0 2,1 1 5,1 2 1,1 3 02 27.0 7sS L OW1 0,1 4,1 8,2 7,3 2,4 2,4 6,5 0,5 4,5 7,5 9,6 3,6 4,6 9,7 5,8 0,8 7,9 2,1 0 2,1 1 5,1 2 1,1 3 02 213 7 3.6 8s 采用C+语言实现第二阶段算法,其中计算节点总数t=1 8,单个节点实体容量b=6。算法共耗时0.0 8s,最终求得每个计算节点分配实体编号为:3 7,7 1,2 0,2 3,2 4,9 4,3,1 0 4,1 0,4 4,6 2,3 1,1 1,4 5,5 5,5 9,6 0,9 3,5,3 8,8,2 5,2 6,9 2,3 3,6 8,6,1 0 5,4 9,5 0,3 2,1 2,1 3,5 6,5 7,5 8,1 4,1 5,1 6,4 6,4 7,4 8,6 4,2,7 3,4 3,1 8,8 2,6 5,1 0 2,4 2,7 6,8 5,8 6,1,1 0 1,7 7,5 3,8 7,8 8,9 9,1 0 0,4 1,8 9,9 0,2 9,3 4,4,6 9,8 1,1 9,9 6,9 7,4 0,7 8,2 8,3 5,6 7,7,8 0,5 1,6 6,3 9,7 9,2 7,9 5,7 0,9,7 5,8 3,8 4,6 1,9 8,1 0 3,7 4,2 1,9 1,3 0,3 6,7 2,5 2,5 4,2 2,6 3。接下来对比本算法和顺序分配策略的仿真效率。在相同软硬件环境的分布式仿真平台分别运行所编制的仿真想定,计算节点间采用开源的基于数据分发服务1 4实现通信。仿真开始为想定时间0s,结束为想定时间1 00 0 0s。两种策略想定时间向 前 推 进 的 真 实 世 界 实 际 耗 时 变 化 如 图3所示。图3中,曲线出现拐点是因为在该想定时间部分实体结束任务并退出仿真。拐点前的时间段,实体数目较多,本算法相比顺序分配的推演效率提升约2 2%,拐点后的时间段,实体数目较少,本算图3 仿真推演效率对比F i g.3 C o m p a r i s o no f s i m u l a t i o nd e d u c t i o n s法推演效率提升约6%。实体间事件交互次数越多,本算法提升效率越明显。想定推进到1 00 0 0s结束时,本算法实际耗时6 1 7s,顺序分配实际耗时7 4 8s,仿真推演效率综合提升约1 7%。4 结束语本研究针对分布式仿真系统的实体节点分配问题,提出了一种基于规则的启发式两阶段实时求解算法。第一阶段将原问题提取并抽象为一类静态目标分配问题,构建了最小期望事件数的最优化模型,得到覆盖所有实体的事件最小集。第二阶段利用事件最小集进行分箱操作,得到最终分配方案。应用试验表明,该算法能显著减小分03 第2期分布式仿真系统实体节点分配问题实时求解算法布式仿真系统的网络通信,提升仿真推演效率,并能在秒级耗时内生成分配方案,特别适用于包含大量实体的复杂场景分布式仿真。参考文献1 杨自鹏,胡声超,周佑君,等.多任务在轨服务模块化智能航天器技术研究J.宇航总体技术,2 0 1 9,3(4):1 5-2 0.2 郭勇陈,沈洋.基于离散事件仿真原理的多主体仿真控制方法J.计算机仿真,2 0 1 5,3 2(6):3 4 9-3 5 5.3 王鹏,刘东玲,杨辉,等.分布式仿真系统的网络通信问题 研 究 C/第 三 十 三 届 中 国 仿 真 大 会,北京,2 0 2 1.4H i l e yA,J u l s t r o mBA.T h eq u a d r a t i cm u l t i p l ek n a p-s a c kp r o b l e m a n dt h r e eh e u r i s t i ca p p r o a c h e st oi tC/P r o c e e d i n g so f t h e8t ha n n u a l c o n f e r e n c eo nG e-n e t i ca n de v o l u t i o n a r yc o m p u t a t i o n.S e a t t l e,W a s h-i n g t o n,U