机载公共设备综合管理系统任务分配算法研究
2004年 9月
第 3O卷 第 9期
北 京 航 空 航 天 大 学 学 报
Journal of Beijing University of Aeronautics and Astronautics
September 2004
V01．3O No．9
机载公 共设备综合 管理 系统任务分配算法研 究
马保 海 裘 丽华
(北 京航空 航天大学 自动 化科学 与电气工 程学 院 ，北京 100083)
摘 要 ：机 载 公 共 设 备 的 综 合 管理 是 机 载 系 统 发 展 的 必 然 方 向 ，为 解 决 机
载公 共 设 备 综合 管 理 系统 中任 务 分 配 问题 ，进 行 了任 务 划 分 ．根 据 周 期 任 务 和 非 周 期
任 务 对 系统 风 险 系数 的贡 献 不 同 ，提 出 了两 层 任 务 分 配 策 略 ；以单 机 风 险 系 数 均 衡 为
目标 函数，设计 了基于蚁群算 法的周期任务分配算法 ．对蚁群算 法进行 了模糊 自适应
参数 调 整 的 改进 ，仿 真结 果 表 明 改进 算 法 能 够 有 效 地 使 蚁 群 算 法 从 局 部 最 优 点 中逃
脱 ，解 决 任 务 分 配 问题 ．
关 键 词 ：机 载 计 算机 ；分 配 问题 ；调度 算 法 ；公 共 设 备 综 合 管 理 系 统 ；蚁 群
算 法
中 图 分 类号 ：V 247．2：TP 302．1
文 献标 识码 ：A 文 章 编 号 ：1001—5965(2004)09—0893—04
Research of task assignment in aircraft utility management system
Ma Baohai Qiu Lihua
(School of Automation Science and Electrical Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100083，China)
Abstract：The airborne utility management system is the inevitable developing trend of airborn e system ．Th e
tasks of the airborn e utility manag ement system were partitioned for solving the task assignment problem ．Th e two—
level tasks allocation strategy of cycle tasks an d un--cycle tasks was put forward because their contributions are differ--
ence for the risk coeffi cient of system ．Taking the balance of risk coeffi cient among the computers as the goal func—
tion，the cycle tas k allocation arithmetic based on the ant colony optimization arithmetic was design ed．Th e ant colo—
ny arithmetic was improved by fuzzy—adaptive parameter regulation．Th e simulative results show that the improved
arithmetic can efficiently make it escaped from the local extremum and resolve the UMS task assign ment problem of
utility manag ement system ．
Key words： airborne computers ； assign ment problems； scheduling algorithm ；utility manag ement system
(UMS)；ant colony optimization(ACO)
1 问题 描述
由四 台综合处理机(SMP)对 多个机 电子系统
进行分布式 管理 的机 载公 共设 备综 合 管 理 系统
(UMS，Utility Management System)是下 一 代战 斗机
的 必 然 发展 方 向 ，图 1所 示 为 全 透 明 的 UMS体 系
结构n ．如何把 子系统 控制 和管理 的任 务合 理 的
分配到 四台 SMP中 ，以保 持飞 机 UMS性能最佳 。
是 一个 关 键 的问 题 ，这 就 是 所 谓 的任务 分 配 问
题 ．
任务分 配问题 由分 配域 、目标域 、分 配算 子 、
目标 函数 四个 要 素 组 成 ．
分 配域 T{t。，t ，? ，t }：指 被 分 配 对 象 的 矢
量集合 ；
目标 域 M：由
处理机节点的集合 ；J是 指通 过航 空 总线连 接 的
综合处理机的分布式拓扑结构 ；
收稿 日期 ：2003．06．12
基金 项 目：国家 自然科 学基金 资助项 目(50075005)
作者 简介 ：马保 海 (1975一)，男 ，河 北邯郸 人 ，博士 生 ，mbhbuaa@yahoo．corn．cn
维普资讯 http://www.cqvip.com
894 北 京 航 空 航 天 大 学 学 报 2004年
SM P SMP SM P SM P
公 设备子 系统
图 1 UMS拓 扑结构
分配算子 ：所谓 的任 务分配算 子是从分配
域 到 目标 域 的 映 射 ；
目标 函数 ：所 谓 的 目标 函数 是 指 任 务 分 配
结 果 要 达 到 的 目标 ．
对 于 UMS来讲 ，任 务 分配 问题 可 以表 示 为 ：
按 照分 配 算 子 ，把 分 配 域 {t ，t：，? ，t }的 所
有元素划分为 四个子集合 ，在满足 目标 函数 月的
条件下 ，分别 分配到 目标域 中的四台处理 机 中执
行 ．
任务分配是一个 组合优 化 问题 ．目前 的方法
主 要 是 启 发 式 的 进 化 算 法 或 几 种 进 化 算 法 的 综
合 ，其共 同点是单 个种群 的进 化或多种 群无 协作
的进 化 ．而基 于 蚁 群 算 法 有 效 地 利 用 了 种 群 之
间地协作 ，能够取得较好 的效果 J．
2 任 务分 析 与任 务分 配 目标 函数
2．1 UIⅥS任 务分 析 与 划 分
分 配 域 包 括 两 个 方 面 ：① 所 控 制 的多 个 子 系
统 的 控 制 、检 测 功 能 、各 子 系 统 的 参 数 多 功 能 显
示 ；②针对 四台 SMP的相互 检测 和总线 管理等任
务 ．
根据公共设备 的特点 ，可知 UMS中任 务具有
余度 、周期与非周期任务与风险性等特点 ，风险性
是 指 子 系统 功 能 失 效 对 飞 行 的 生 存 力 的 影 响 ，风
险 系 数 用 G，表示 ．
根据上述任务的特点 ，可 以对任务进行 划分 ，
划 分 的原 则 为 ：
1)任务分为周期和非 周期任 务两类 ；
2)同一功 能 的任 务 的不 同余度 的子系统 划
分为不 同的任务 ，即具有 3余度 的刹 车控制 系统
划 分 为 3个 相 互 独 立 的任 务 ；
3)同一 子 系统 的控 制任 务或 检测 任 务划 为
一 个子任务 以尽 量减少 任务 之间 的数 据交 联 ，这
样把 UMS所有 的任务划分为若 干子任 务 ．
2．2 UMS任 务分 配 的 目标 函数
从提高公共设 备 的可靠性 与生存 力 出发 ，选
择 UMS任 务分配 的 目标 为使 每一个 处理机 的失
效对整机的影响最小 ，即当一个处理机失效时 ，其
上的任 务要转 移(动态 的分配 )到其它 的节点处理
机中以保证公 共设备 的正 常功能 ，在 考虑转 移过
程 的风险 的情况 下 ，如何使 分配 失效 的风险 降至
最低 ．因此本文引入单机风险系数 的概念 ]．
单机风 险 系数 ：在 UMS中单 节点 MsM 承 担
的任务集合为 T(t ，? ，t )，节点 。脓 的风险 系
数 为
5 = 0·n+ (b·G。+ c·L + d·S)
(1)
其 中，n为节点 承担 的任务数 ；G 为单个 任
务 t 的风 险 系 数 ；L。为 处 理 机 的 能 力 (因 为 系 统
为同构系统 ，因此将 不再 考虑这 一 因素 )；s为 飞
行状态 ；a，b，c，d为各 因素的加权系数 ．
因为对 于 UMS来讲 ，任务的总数 和飞行状 态
以及处理机的能力 都是 固定 的 ，系统总 的任 务 风
险系 数 基 本 不 变 ，因此 各 处 理 机 的 风 险 系数 均 衡
时 ，单机 的风险系数最小 ，即单机失效 时对整个飞
行的影 响最小 ．若 把多 台处理 机 的风 险系数 看作
一 个随机变量 ，则 可选 随机变量 的方 差最小 作为
任务分 配的 目标 函数 ，即
? in
一
其 中 ，Ⅳ为总的处理机 节点数 目．
3 UMS的任务 分 配 策略
对于周期任务来讲 ，每个任 务对 UMS的风 险
是 一 直 存 在 的 ，因此 可 以认 为 周 期 任 务 对 SMP的
风 险 系 数 的 贡 献 是 静 态 不 变 的 ；而 对 于 非 周 期 的
任务 ，由于每个任务仅仅执行一次或几次 ，因此其
对 SMP的 风 险 系 数 的 贡 献 是 瞬 时 的 ．因 此 ，UMS
任务分配 ，可以分 为两个 层 次 ，首先 是对 UMS任
务集中的周期 任务进 行任 务 的分 配 ，然后对 非周
期 的任务集进行分配 ．这样就 构成 了 UMS的两层
任务分配策略 ：第一层周期任务 的分配 ；第二层非
周期任 务的分 配 ．UMS整体 任务 分配 策 略如 图 2
所示 ．在 UMS中非 周期任 务数 量较 少 ，采 用通 用
的启 发式 方法即可 ，本文不再讨论 ，仅仅讨论对于
周期 任 务 的 分 配 问题 ．
3．1 基 于 蚁 群 算 法 的 周 期 任 务 的 设计
1992年 Marco Dorigo根 据 自然 界 蚂 蚁 觅 食 的
维普资讯 http://www.cqvip.com
第 9期 马保海 等 ：机 载公共 设备 综合 管理 系统任 务分 配算 法研 究 895
周 期任务
任 务排序
—T一
周期仃 务
分配
工
分配结 果
— —
t从 当前 的处理机转移 到另外一个 处理机 的概率
任务划分I 为
非蒯期任 务
非周 期任务
排序
t
非周 期任务
分配算法
l静态任务调 l。_J
l度最终结果 l
图 2 UMS两层 任务 分配 策略
行为 ，提出 了蚁群 算 法 (ACO，Ant Colony Optimiza．
tion)，在旅行商问题 、负载平衡 、车辆调度 、可靠性
分 配等优化领域 中取得 了较好的效果 ．
在算法 的设计之前 ，首先 引入符号 ：
Ⅳ—— 处 理 机 节 点 的 数 量
r —— 任务 t 对节点 岍之间 的信息素
，
— — 节 点 处 理 机 ， 之 间 的 目标 函 数 之
差
— — 蚂 蚁 的 数 量
— — 蚂 蚁 在 节 点 与 之 间 的可 视 度
ID——信息素 的蒸发系数
a — — 信 息素在蚂蚁搜索 中的权重 ，a≥0
卢—— 局部搜寻在蚂蚁搜索中的权重 ，卢≥0
Pi,j—— 节点 向节点 岍转移 的概率
￡— — 循 环 寻 优 的 步数
p— — 正 常 数
1)路 径 的设 计
定义 任务矢 量 ：T(t。，t ，t3，? ，t )是具 有
一 定顺序的子任 务矢量 ，其 顺序是 任务 的开始执
行时 间早的任务 排在前 面 ；相 同开 始时 间的任 务
按照单个 任 务 的风 险 性 G 的大 小排 列 ，风 险性
G 大 的任务排在前面 ；余 度任务相互之 间没有顺
序 的约束 ．这样 ，我们就把要分配的任 务排 成了一
个具有一定顺 序 的矢量 ，寻 优的路径 为每 只蚂蚁
按照任务矢量 的顺序移动 ．
2)蚂蚁 的设 计
在 ACO中 ，每只蚂蚁的一次完全 的路 径循环
相 当于 问题 一 个 解 ，我 们 设 定 蚂 蚁 的一 个 循 环 为 ：
按照任务矢量 的顺 序 ，每只 蚂蚁 根据 不 同的转移
概率 ，把任务依次分给不 同的处理机 SMP．
3)转移概率的设计
在 ACO中转移概率是关键 ，蚂蚁把一个 任务
P(f．，)(m)： (3)
∑ r · m)
其 中 m∈[1，M]，为蚂蚁 的序号 ．
(m)为任务 t 从 当前 的处 理机 到处 理机
的启发值
c ‘ ㈩
当二者之 间 的 目标 函数差 越大 ， ，，(m)越 大 ，对
蚂蚁 移 动 目标 的指 示 作 用 越 大 ．
由此 ，可以得 到基于 ACO的任务 分配算法 的
基本步骤 ：每个蚂蚁 首先 随机分布在各处理机上 ，
按照任务矢量 的顺序 依次把每个任 务迁移至处理
机节点 ．每个 蚂蚁 的迁移过程构成 系统 的一个解 ，
从 所 有 的 蚂 蚁 中选 择 目标 函数 最 优 蚂 蚁 ，根 据 最
优蚂蚁的迁 移 过程 更新 任 务 与节 点 之 间 的信 息
素 ，然后 重新开始任务 的迁移 ，直到 目标 函数 收敛
为止 ，算法框架如 图 3所 示 ．
丌始
I--O，参数初始化 ，将所有的蚂
蚁随机 地放置 存 Ⅳ 个节点 ·I-
是
I 荔
蚁并计算信 l
息素增量l 亍
更 瓿
间信息素 l
n=0 l
，+l l
设定蚂蚁 的 Tab
，＼ ：
l否
< ：
＼ ／
i
对所有 的蚂蚁 计
算移动 到 一 个
城 市节点的概率
更 新 _rab
／／=／／+l
l在得到的 竺
— ．{解中选取
I最佳路径
结 束
图 3 基 于 ACO的周 期 任务分 配算 法框 图
3．2 基于模糊参数调整 的 ACO算 法
对于 ACO算法 ，并没有一个成熟 的参数选 取
法则 ．文献[6]通过 仿真 和参数 回归分 析 ，认 为对
系统影响最大 的参数为 R 、卢、a．
R 是 由算法 本身决定 的 ，无 法调 整 ．卢、a反
映在算法中即是转移 概率的计算 问题 ，因此 ，本文
从转 移 概 率 人 手进 行 改进 ．
从 式(3)中看出 ，转 移概率 由信息 素 r 与启
维普资讯 http://www.cqvip.com
896 北 京 航 空 航 天 大 学 学 报 2004年
发式信息 决定 ，二者的权重 由 a与 调整 ．z-
是种群之间的信 息素 的正反馈 作用 ，其 作用是 加
快结果收敛 ； ，，的作用是一种启发式 局部搜 寻信
息 ．a与 值 的相 对大 小标 志 了协 作正 反馈 与启
发式局部搜寻的权重 ．因此 如何调整 a与 值 的
大 小 是 一个 关 键 的 问 题 ，如 果 选 择 不 当 会 造 成 早
熟 现 象 或 不 收 敛 ．
设 a=k·a。， =(1一k)· ．其 中 ，a。为 信 息
素权重的最大值 ； 为启发式 局部搜寻权 重 的最
大值 ；k∈[0，1]为调 节系数 ．k的大小 表示信息素
和启发式局部搜寻规则两者在选择概率 中的作用
的大 小 ．
为 此 ，引入 模 糊 语 言 输 入 变 量 ：迭 代 次 数 、目
标 函数变化率 以及输 出变量——调节 系数 k．
迭代定义为 目前迭代寻优 次数 z与总 的寻优
次数 之 比，迭代 的论域为 [0，1]；目标 函数 变化
率定义为 当前 目标 函数值 在一定的邻域 内保持稳
定的迭代次数 与 总的迭代 次数 的 比，表示 了 目标
函数 的收敛程度 ，其论域为 [0，1]；调节 系数 k，其
论域为 [0，1]．各变量 的模糊子集合与相应 的模糊
推理规则 如表 1所示 ．通 过选择模糊 变量合 适 的
隶属 函数 ，可 以在 算 法 中 实时 调 整 k，达 到 ACO
算法 的模糊 自适应 参数调 整 ．
表 1 模 糊推 理规 则
4 仿真 试 验
选定 50个子任 务 进行仿 真试验 ．在没有模
糊 自适应参数调整情况下的 目标 函数 的变化 曲线
如 图 4所示 ．
图 5为在模糊 自适应参数调整后 目标 函数 的
1 50
100
旧
了 50
0 1 2 3 4 5 6 7 8 9 10
寻优 次 数 ／10
图 4 基 于 ACO算 法 的 UMS任务分 配
变化 曲线 ．可 以看 出 ，应 用模 糊动 态调 整 改进 的
ACO算法能够有效地从 局部 最优点 逃脱 ，其 寻优
过程 明显好 于没有模糊调整前 的仿真结果 ．
图 5 模 糊 自适应 参数调 整 ACO算法 UMS任 务分 配
5 结 束 语
本文对 UMS的任务进行 了分析和划分 ，并针
对 UMS的特点 ，把任务划分为周期任 务和非周期
任务的两层 ，根据 这两 层任务对 系统 节点 风险 系
数 的贡献不 同，采用两层任务分配策略 ，并设计 了
基于风险系数 均衡 的任务 分配 目标 函数 ．采 用基
于模糊 自适应 参数调 整方法 对 ACO算 法进行 了
改进 ，仿真结果证 明这种方 法能够 有效 地使 ACO
逃脱局部最优点 ，解决 了 UMS任务分 配问题 ．
参 考 文 献 (References)
[1]Moir I，Seabridge A G．Management of utility system in the experi—
mental aircraft programmer[J]．Aerospace，1996，9：28～35
[2]陈显锋 ．机载机 电 系统 综合控 制管理 实时 仿真 平 台系统 研究
[D]，北京 ：北 京航空航 天大 学 自动控 制系 ，1999
Chen Xianfeng．Research on the real time simulation platform of air—
craft multi—electromechanical integrated management systems【D J，
Beijing：Dept，of Automatic Control，Beijing University of Aeronau—
tics and Astronautics，1999(in Chinese)
[3]钟求 喜 ，谢 涛 ，陈火 旺 ，任 务 分 配 与调 度 的 共 同进 化 方 法
[J]，计 算机 学报 ，2001，24(3)：308～314
Zhong Qi ，Xie Tao，Chen Huowang．Task allocation scheduling by
computational modd of coevolution[J]．Chinese Journal of Comput—
ers，2001，24(3)：308～314(in Chinese)
[4]Marco D．The ant system：optimization by a colony of cooperating
agents[J]．IEEE Transactions on Sy~teme Man and Cybernetics，
1996，26(1)：1～13
[5]李 杨 ．飞 机机载机 电设 备综合控 制管理 系 统仿 真平 台研 究
[D]，北京 ：北京航 空航天 大学 自动控制 系 ，1998
Li Yang．Research on the simulation platform of aircraft utilities
management and control system[D]．Beijlng：Dept．of Automatic
Control，BeOing University of Aeronautics and Astronautics，1998(in
Chinese)
[6]Ricardo M，Ramalho G L，Ant system for the set covering problem
[A]．Prooeding of IEEE International Conference on System~Man
and Cybernetics【C J，2001．3129～3133
维普资讯 http://www.cqvip.com
机载公共设备综合管理系统任务分配算法研究.pdf
