2024, 35(11):4949-4972. DOI: 10.13328/j.cnki.jos.007001 CSTR:
摘要:数据作为一种新型生产要素, 需要在不同主体间流通以发挥价值. 在这一过程中, 数据需要确保其完整性, 避免受到未经授权的篡改, 否则可能导致极为严重的后果. 现有工作通过将分布式账本与数据加密、校验技术结合实现数据存证以证明待流通数据在传输、存储等环节中未受篡改, 保障数据的完整性. 然而, 此类工作难以确认数据供方所提供数据本身的完整性, 一旦数据供方主动或被动提供了伪造数据, 后续完整性保障工作将失去意义. 为此, 提出一种基于远程证明的数据服务完整性验证方法, 所提方法以可信执行环境作为信任锚, 对特定数据服务静态代码、执行过程和执行结果的完整性进行多维度量与验证, 并通过程序切片优化对特定数据服务的完整性验证, 从而将数据完整性保障的范围延伸至数据供方提供数据的环节. 通过在3个真实Java信息系统中25个数据服务上的一系列实验验证了所提出方法的有效性.
2024, 35(11):4973-4992. DOI: 10.13328/j.cnki.jos.007005 CSTR:
摘要:深度神经网络目前已被广泛应用于自动驾驶、医疗诊断、语音识别、人脸识别等安全攸关领域, 因此深度神经网络测试对于保证其质量非常关键. 然而, 为判断DNN模型预测是否正确而对测试用例进行标注的成本很高. 因此, 筛选出能够揭示DNN模型错误行为的测试用例并优先对其进行标注, 能够尽快修复模型缺陷, 从而提升DNN测试的效率、保证DNN模型质量. 提出一种基于数据变异的测试用例选择方法DMS. 该方法设计并实现数据变异算子生成变异模型, 以模拟模型缺陷并捕获测试用例揭错时的动态模式, 从而评估测试用例的揭错能力. 在25个深度学习测试集和模型的组合上进行实验, 结果表明, 无论是筛选出的样本中揭错用例的比例还是揭错方向的多样性, DMS都要显著优于现有的测试用例选择方法. 具体来说, 以原始测试集作为候选集时, 在选择10%的测试用例时, DMS能够筛选出候选集中53.85%–99.22%的揭错用例, 在选择5%的测试用例时, DMS筛选出的测试用例已经几乎能覆盖所有的揭错方向. 相较于8种对比方法, DMS平均多找出12.38%–71.81%的揭错用例, 证明了DMS在测试用例选择任务中的显著有效性.
2024, 35(11):4993-5015. DOI: 10.13328/j.cnki.jos.007031 CSTR:
摘要:物联网设备的使用范围正在不断扩张. 模型检测是提升这类设备可靠性和安全性的有效手段, 但常用的模型检测方法不能很好地刻画这类设备常见的跨空间移动和通信行为. 为此, 提出一种面向物联网设备移动与通信行为的建模及验证方法, 以实现对这类设备时空相关性质的验证. 通过将推拉动作和全局通信机制融入ambient calculus, 提出全局通信移动环境演算(ACGC)并给出了ACGC对ambient logic的模型检测算法; 在此基础上, 提出描述物联网设备移动和通信行为的移动通信建模语言(MLMC), 并给出将MLMC描述转换为ACGC模型的方法; 进一步地, 实现模型检测工具ACGCCk以验证物联网设备的性质是否得到满足, 并通过一些优化加快检测速度; 最后, 通过案例研究和实验分析阐明所提方法的有效性.
2024, 35(11):5016-5039. DOI: 10.13328/j.cnki.jos.007034 CSTR:
摘要:基于机器定理证明的形式化验证技术不受状态空间限制, 是保证软件正确性、避免因潜在软件缺陷带来严重损失的重要方法. LLRB (left-leaning red-black trees)是一种二叉搜索树变体, 其结构比传统的红黑树添加了额外的左倾约束条件, 在验证时无法使用常规的证明策略, 需要更多的人工干预和努力, 其正确性验证是一个公认的难题. 为此, 基于二叉搜索树类算法Isabelle验证框架, 对其附加性质部分进行细化, 并给出具体化的验证方案. 在Isabelle中对LLRB插入和删除操作进行函数式建模, 对其不变量进行模块化处理, 并验证函数的正确性. 这是首次在Isabelle中对函数式LLRB插入和删除算法进行机械化验证, 相较于目前LLRB算法的Dafny验证, 定理数由158减少至84, 且无需构造中间断言, 减轻了验证的负担; 同时, 为复杂树结构算法的函数式建模及验证提供了一定的参考价值.
2024, 35(11):5040-5064. DOI: 10.13328/j.cnki.jos.007043 CSTR:
摘要:应用程序图形用户界面 (graphical user interface, GUI/UI) 为应用程序与其终端用户提供了一座可视化的桥梁, 用户可以通过交互操作使用应用程序. 随着移动应用程序的发展, 兼具美学与交互设计的图形用户界面也变得越来越复杂, 用户也更加关注应用程序的可访问性和可用性. 然而图形用户界面的复杂性也对其设计与实现带来巨大的挑战. 由于用户对于移动设备的自定义设置以及不同的设备型号和屏幕分辨率导致用户界面显示问题频繁发生. 例如由于软件或硬件兼容性, 在不同设备上进行界面渲染时总会出现文本交叠、组件遮挡、图像丢失等显示问题. 它们对应用程序的可用性和可访问性产生负面影响, 导致用户体验不佳. 不幸的是, 对于移动应用程序用户界面显示问题的成因知之甚少. 为了应对这一挑战, 收集来自百度众测平台上的6729张具有用户界面显示缺陷的应用程序截图和GitHub中1016个缺陷报告提供的应用程序截图, 采用主题分析方法识别出9类用户界面显示缺陷, 然后对GitHub中1016个缺陷报告和其对应的缺陷代码进行分析, 总结出用户界面显示缺陷本质成因. 研究发现: (1) 在众测数据集中用户界面显示缺陷截图占总截图的62.1%; (2) 导致界面显示缺陷的原因中字体的缩放设置与组件的自适应设置不适配所占的比例较大; (3) 界面的布局设置会导致界面显示缺陷产生; (4) 硬件加速未开启会影响界面的正常显示.
2024, 35(11):5065-5082. DOI: 10.13328/j.cnki.jos.007047 CSTR:
摘要:随着开源人工智能系统规模的扩大, 软件的开发与维护也变得困难. GitHub是开源社区最重要的开源项目托管平台之一, 通过GitHub提供的拉取请求系统, 开发者可以方便地参与到开源项目的开发. 拉取请求的描述可以帮助项目核心团队理解拉取请求的内容和开发者的意图, 促进拉取请求被接受. 当前, 存在可观比例的开发者没有为拉取请求提供描述, 既增加了核心团队的工作负担, 也不利于项目日后的维护工作. 提出一种自动为拉取请求生成描述的方法PRSim. 所提方法提取拉取请求包含的提交说明、注释更新和代码改动等特征, 建立语法改动树, 使用树结构自编码器编码以检索代码改动相似的其他拉取请求, 参照相似拉取请求的描述, 使用编码器-解码器网络概括提交说明和注释更新, 生成新拉取请求的描述. 实验结果表明, PRSim的生成效果在Rouge-1、Rouge-2和Rouge-L这3个指标的F1分数上分别达到36.47%、27.69%和35.37%, 与现有方法LeadCM相比分别提升了34.3%、75.2%和55.3%, 与方法Attn+PG+RL相比分别提升了16.2%、22.9%和16.8%, 与方法PRHAN相比分别提升了23.5%、72.0%和24.8%.
2024, 35(11):5083-5097. DOI: 10.13328/j.cnki.jos.007002 CSTR:
摘要:时序知识图谱推理旨在补充知识图谱中缺失的链接(事实), 其中每个事实都与时间戳进行绑定. 基于变分自动编码器的动态变分框架在这项任务中显示出独特的优势. 通过将实体和关系基于高斯分布进行联合建模, 该方法不仅具备很强的可解释性, 而且解决了复杂的概率分布问题. 然而, 传统的变分自动编码器方法在训练过程中容易出现过拟合问题, 从而不能精确捕捉实体语义的演化过程. 为了解决这个问题, 提出基于扩散概率分布的时序知识图谱推理模型. 具体来讲, 建立一个双向的迭代过程, 将实体语义建模过程分为多个子模块. 其中, 每个子模块通过一个正向的加噪变换和反向的高斯采样组成, 负责建模实体语义的一个微小演变过程. 相对基于变分自动编码器的方法, 通过多个子模块联合建模显示地学习度量空间中实体语义随时间的动态表示, 能够得到更为精确的建模. 与基于变分自动编码器的方法相比, 对于评估指标 $ MRR $, 模型在Yago11k数据集和Wikidata12k数据集分别提高4.18%和1.87%, 在ICEWS14和ICEWS05-15数据集上分别提高1.63%和2.48%.
2024, 35(11):5098-5115. DOI: 10.13328/j.cnki.jos.007007 CSTR:
摘要:在当前数据来源多样化且人工标记难度大的现实生活中, 半监督场景下多视角数据的分类算法在各个领域中都具有重要的研究意义. 近年来, 基于图神经网络的半监督多视角分类算法研究已经取得了很大的进展. 但是现有的图神经网络算法大多是在分类阶段进行多视角互补信息的融合, 反而忽略了训练阶段同一样本不同视角间互补信息的交互. 针对上述问题, 提出半监督场景下多视角信息交互的图卷积神经网络算法MIGCN (multi-view interaction graph convolutional network). 该方法通过在不同视角上训练的图卷积层之间引入Transformer Encoder模块, 使得同一样本在训练阶段都可以通过注意力机制自适应的在不同视角间获取互补性信息, 进而加强自身的训练; 除此之外, 还通过引入一致性约束损失让不同视角最终特征表达的相似关系尽可能一样, 促使图卷积神经网络在分类阶段更加合理的利用多视角特征之间的一致性和互补性信息, 进一步提升多视角融合特征的鲁棒性. 最后, 在多个真实世界多视角数据集上的实验表明, 相比于基于图的半监督多视角分类模型, MIGCN可以更好地学习到多视角数据的本质特征, 进而提升半监督多视角分类的准确性.
2024, 35(11):5116-5132. DOI: 10.13328/j.cnki.jos.007033 CSTR:
摘要:自然场景中的实体标志, 如商标、交通标志等, 易受拍摄角度、所依附物体形变、尺度变化等影响, 导致检测精度降低. 为此, 提出一种注意力引导的标志检测与识别网络(attention guided logo detection and recognition network, AGLDN), 联合优化模型对多尺度变化和复杂形变的鲁棒性. 首先通过标志模板图像搜集及掩码生成、标志背景图像选取和标志图像生成创建标志合成数据集; 然后基于RetinaNet和FPN提取多尺度特征并形成高级语义特征映射; 最后利用注意力机制引导网络关注标志区域, 克服目标变形对特征鲁棒性的影响, 实现标志检测与识别. 实验结果表明, 所提方法可以有效降低尺度变化、非刚性形变的影响, 提高标志检测准确率.
2024, 35(11):5133-5148. DOI: 10.13328/j.cnki.jos.007035 CSTR:
摘要:检测社交媒体文本中的潜在主题是一项有意义的任务. 由于帖子具有表达简短、非正规的特点, 其将带来严重的数据稀疏问题. 不仅如此, 基于变分自编码器(variational auto-encoder, VAE)的模型在主题推断过程中还忽视了用户间的社交关系, 考虑VAE假设输入的数据点间是相互独立的. 这导致了推断的潜在主题变量间缺少了相关性信息, 进而导致主题不够连贯. 社交网络结构信息不仅聚合上下文信息的线索, 还暗示了用户间的主题相关性. 因此, 提出基于消息传递和图先验分布的微博主题模型, 其借助图卷积网络(graph convolution network, GCN)编码更加丰富的上下文信息, 并且在变分自编码器推断主题的过程中, 通过图先验分布整合用户交互关系以促进对多数据点复杂关系的理解, 从而更好地挖掘社交媒体主题信息. 在3个真实微博数据集上的实验证明了所提方法的有效性.
2024, 35(11):5149-5162. DOI: 10.13328/j.cnki.jos.007040 CSTR:
摘要:命名实体识别任务是信息抽取领域中的一个基础任务, 旨在定位句子中实体所在位置的边界, 并对该实体进行分类. 针对现有基于跨度检测的模型存在的嵌套实体边界模糊问题, 提出一种基于跨度边界感知的嵌套命名实体识别模型. 首先, 利用双仿射注意力机制, 捕获词元间的语义相关性, 进而生成跨度语义表示矩阵; 其次, 通过设计一种二阶对角邻域差分算子, 建立跨度语义差分机制, 以提取跨度间的语义差异信息. 此外, 引入一种跨度边界感知机制, 利用滑动窗口的局部特征提取能力, 强化跨度的边界语义差异, 从而准确定位实体跨度位置. 为验证模型的有效性, 在3个基准数据集上进行测试, 包括ACE04、ACE05和Genia数据集. 实验结果表明, 提出的模型在实体识别准确率的表现优于相关工作. 此外, 还设计消融实验和案例分析以验证提出的语义差分机制和跨度边界感知机制的有效性, 为进一步研究命名实体识别问题提供新的思路和实验证据.
2024, 35(11):5163-5178. DOI: 10.13328/j.cnki.jos.007044 CSTR:
摘要:由于多视图数据特征复杂, 多视图离群检测已经成为离群点检测中一个极具挑战性的研究课题. 多视图数据中存在3种类型的离群点, 分别为类离群点、属性离群点和类-属性离群点. 早期多视图离群点检测方法大多基于聚类假设, 当数据中没有聚类结构时很难检测出离群点. 近年来, 许多多视图离群点检测方法使用多视图一致的近邻假设来代替聚类假设, 但仍存在新增数据检测效率低的问题. 此外, 大多数现有的多视图离群点检测方法都是无监督的, 在模型学习过程中会受到离群点的影响, 处理高离群率的数据集时效果不佳. 为了解决这些问题, 提出一种用于高效多视图离群点检测的视图内重建和跨视图生成网络来检测3种类型的离群点, 所提方法包含视图内重建和跨视图生成两个模块. 通过使用正常数据训练, 所提方法可以充分捕捉正常数据中每个视图的特征, 并较好地重建和生成相应的视图. 此外, 还提出一个新的离群值计算方法, 为每一个样本计算相应的离群值得分, 从而高效地检测新增数据. 大量的实验结果表明, 所提出的方法明显优于现有的方法. 这是将基于生成对抗网络的深度模型应用于多视图离群点检测的工作.
2024, 35(11):5179-5195. DOI: 10.13328/j.cnki.jos.007051 CSTR:
摘要:异构图是一种具有多种类型节点或边的图, 也称异构信息网络, 其常被用来建模现实世界中具有丰富特征和关联模式的系统. 异构节点间的链接预测是网络分析领域的一个基本任务. 近年来, 异构图神经网络技术的发展极大地促进了链接预测任务的进步, 其通常将此任务当作节点间的特征相似性分析或基于成对节点特征的二分类问题. 然而, 现有的异构图神经网络技术在进行节点特征表示学习时, 往往仅关注相邻节点间的关联或基于元路径的结构信息. 这使得其不仅难以捕捉异构图中固有的环结构所蕴含的语义信息, 也忽视了不同层次的结构信息之间的互补性. 为解决上述问题, 设计一种基于多层次图结构的级联图卷积网络CGCN-MGS, 其由基于邻居、元路径和环3种不同层次图结构的图神经网络组成, 能从多层次特征中挖掘出丰富、互补的信息, 提高所学节点特征对节点语义和结构信息的表征能力. 多个基准数据集上的实验结果表明, CGCN-MGS在异构图的链接预测任务上能够取得目前最优的性能结果.
2024, 35(11):5196-5209. DOI: 10.13328/j.cnki.jos.007054 CSTR:
摘要:目前, 深度学习广泛应用于各个领域并取得了优异的表现, 这通常需要大量标注数据的支持, 而大量标注数据的获取往往意味着高昂的成本与苛刻的应用条件. 因此, 随着深度学习的发展, 如何在实际场景下突破数据限制, 成为目前重要的研究目标, 而半监督学习正是其中一大研究方向. 半监督学习通过利用大量的未标记数据辅助少量的标记数据进行学习, 很好地减轻了深度学习的数据需求压力. 伪标签生成方法是当前半监督学习的重要组成部分, 所生成的伪标签质量的优劣会很大程度影响半监督学习的最终效果. 聚焦半监督学习中的伪标签生成问题, 提出基于最优传输理论的伪标签生成方法. 所提方法在将有标签信息作为生成过程引导的同时引入类别均衡约束, 在此基础上将半监督学习的伪标签生成过程转换成最优传输优化问题, 给出新的求解伪标签生成问题的形式. 为求解该优化问题, 引入Sinkhorn-Knopp算法进行近似快速求解, 避免不可计算问题. 所提伪标签生成方法作为半监督学习中的独立过程可结合当前一致性正则等半监督学习技巧构成完整的半监督学习过程. 最终, 在CIFAR-10、SVHN、MNIST、FashionMNIST这4大公共经典图像分类数据集上进行实验, 验证方法的有效性. 实验结果显示, 所提方法与当前先进的半监督学习方法相比, 均取得更优异的结果, 尤其是在标签情况较少的情况下提升显著.
2024, 35(11):5210-5227. DOI: 10.13328/j.cnki.jos.007056 CSTR:
摘要:时间序列预测模型已广泛应用于日常生活中的各个行业, 针对这些预测模型的对抗攻击关系到各行业数据的安全性. 目前, 时间序列的对抗攻击多在全局范围内进行大规模扰动, 导致对抗样本易被感知. 同时, 对抗攻击的效果会随着扰动幅度的降低而明显下降. 因此, 如何在生成不易察觉的对抗样本的同时保持较好的攻击效果, 是当前时间序列预测对抗攻击领域亟需解决的问题之一. 首先提出一种基于滑动窗口的局部扰动策略, 缩小对抗样本的扰动区间; 其次, 使用差分进化算法寻找最优攻击点位, 并结合分段函数分割扰动区间, 进一步降低扰动范围, 完成半白盒攻击. 和已有的对抗攻击方法在多个不同深度模型上的对比实验表明, 所提出的方法能够生成不易感知的对抗样本, 并有效改变模型的预测趋势, 在股票交易、电力消耗、太阳黑子观测和气温预测这4个具有挑战性的任务中均取得了较好的攻击效果.
2024, 35(11):5228-5248. DOI: 10.13328/j.cnki.jos.007003 CSTR:
摘要:在网络安全领域, 由域名生成算法(domain generation algorithm, DGA)产生的虚假域名被称为DGA域名. 与正常域名类似的是, DGA域名通常是字母或数字的随机组合, 这使得DGA域名具有较强的伪装性. 网络黑客利用DGA域名的伪装性实施网络攻击, 以达到绕过安全检测的目的. 如何有效地对DGA域名进行检测, 进而维护信息系统安全, 成为当前的研究热点. 传统的统计机器学习检测方法需要人工构建域名字符特征集合. 然而, 人工或者半自动化方式构建的域名特征存在质量参差不齐的情况, 进而影响检测的准确性. 鉴于深度神经网络强大的特征自动化抽取和表示能力, 提出一种基于多视角对比学习的DGA域名检测方法(MCL4DGA). 与现有方法不同的是, 所提方法结合了注意力神经网络、卷积神经网络和循环神经网络, 能够有效地捕获域名字符序列中的全局、局部和双向多视角特征依赖关系. 除此之外, 通过多视角表示向量之间的对比学习而产生的自监督信号, 能够增强模型的学习能力, 进而提高检测的准确性. 通过在真实数据集上与当前DGA域名检测方法实验对比验证了所提方法的有效性.
2024, 35(11):5249-5262. DOI: 10.13328/j.cnki.jos.007032 CSTR:
摘要:联邦学习因能解决数据孤岛问题而被广泛关注, 但也存在用户隐私泄露风险和非独立同分布数据下模型异构导致性能下降的问题. 针对该问题, 提出基于Bregman散度和差分隐私的个性化联邦学习方法(FedBDP). 所提方法采用Bregman散度衡量本地参数与全局参数的差异, 并将其作为正则化项更新损失函数, 以减小模型差异来提升模型准确率. 同时, 采用自适应差分隐私技术对本地模型参数进行扰动, 通过定义衰减系数动态调整每轮差分隐私噪声的大小, 以合理分配隐私噪声大小并提升模型可用性. 理论分析表明FedBDP在强凸和非凸光滑函数下满足收敛条件. 实验结果验证该方法在满足差分隐私的前提下, FedBDP模型在MNIST和CIFAR10数据集下能够保证模型准确率.
2024, 35(11):5263-5278. DOI: 10.13328/j.cnki.jos.007049 CSTR:
摘要:在白盒攻击环境下, 攻击者可以访问密码算法的实现过程, 观测算法运行的动态执行和内部细节, 并任意修改. 2002年Chow等人首次提出了白盒密码的概念, 利用查找表技术提出了AES算法和DES算法的白盒实现, 所采用的方法称为CEJO框架. 白盒实现将已有的密码算法进行编码混淆, 在白盒攻击环境下以软件的形式达到保护密钥的目的, 同时保证算法结果的正确性. SIMON算法是一种轻量级分组密码算法, 因其良好的软硬件实现性能被广泛应用于物联网设备中, 研究该算法的白盒实现具有重要现实意义. 给出SIMON算法的两种白盒实现. 第1种方案(SIMON-CEJO)采用经典的CEJO框架, 利用网络化编码对查找表进行保护, 从而混淆密钥. 该方案占用内存为369.016 KB, 安全性分析表明SIMON-CEJO方案可以抵抗BGE攻击和仿射等价算法攻击, 但不能抵抗差分计算分析. 第2种方案(SIMON-Masking)采用Battistello等人提出的编码方式, 对明文信息和密钥信息进行编码, 利用编码的同态性, 将异或运算和与运算转化为模乘运算和表查找操作; 最后进行解码, 得到对应的密文结果. 在算法运行过程中, 对与运算添加布尔掩码, 编码的随机性保护了真实密钥信息, 提高了方案抵抗差分计算分析和其他攻击的能力. SIMON-Masking占用内存空间为655.81 KB, 基于勒让德符号的二阶差分计算分析的时间复杂度为O(n2klog2p). 这两种方案的对比结果表明, 经典的CEJO框架无法有效防御差分计算分析, 运用新型编码并添加掩码是一种有效的白盒实现方法.
2024, 35(11):5279-5305. DOI: 10.13328/j.cnki.jos.007050 CSTR:
摘要:图式区块链采用有向无环图(directed acyclic graph, DAG)的并行拓扑结构, 相较于基于串行拓扑结构的传统链式区块链, 能够显著提升系统性能, 已受到业界广泛关注. 然而, 现有图式区块链的共识协议与存储模型高度耦合, 缺乏灵活性, 难以适应多元化应用需求. 同时, 大部分图式区块链在共识协议层面上缺乏灵活性, 局限于概率性共识协议, 难以兼顾确认延迟和安全性, 尤其对于延迟敏感型应用很不友好. 为此, 提出弹性图式区块链系统ElasticDAG, 其核心思想是将存储模型和共识协议进行解耦, 让两者并行、独立地运行, 从而灵活适配多元化应用. 针对提升系统吞吐量和活性的需求, 为存储模型设计自适应区块确认策略和基于划分的确认区块排序算法; 针对降低交易确认延迟的需求, 设计低延迟DAG区块链混合共识协议. 实验结果表明, ElasticDAG原型系统在广域网下的吞吐量高达11 Mb/s, 并具有10秒级确认性能. 与OHIE相比, ElasticDAG在实现同等吞吐量的情况下, 可将确认延迟降低17倍; 与Haootia相比, ElasticDAG在实现同等共识延迟的情况下, 可将安全性从91.04%提升到99.999914%.
2024, 35(11):5306-5318. DOI: 10.13328/j.cnki.jos.007036 CSTR:
摘要:间歇实时任务的分区DM (deadline-monotonic)调度是一个经典的研究问题, 针对约束截止期间歇任务, 提出一种具有更高处理器利用率的多核分区调度算法PDM-FFD (partitioned deadline-monotonic first-fit decrease). 在PDM-FFD中, 首先将任务按照其相对截止期以非递减顺序进行排序, 然后采用first-fit策略选择处理器核分配任务, 且在各处理器核上采用DM调度策略进行任务调度. 最后通过对任务干扰时间的分析, 得出一种更为紧凑的可调度性判定方法, 并通过该可调度性方法来判定任务的可调度性. 证明PDM-FFD的加速因子为$3 - (3{\mathit\Delta} + 1)/(m + {\mathit\Delta} )$, 时间复杂度为${\rm{O}}({n^2}) + {\rm{O}}(nm)$, 其中${\mathit\Delta} =\displaystyle{\sum }_{{\tau }_{j}\in \tau }{C}_{j} \times {u}_{j}/{D}_{{\rm{max}}}$, ${\tau _j}$为任务集$\tau $中的任务, ${C_j}$为该任务最差执行时间, ${u_j}$为该任务利用率, ${D_{{\rm{max}}}}$为$\tau $中的最大相对截止期, n为$\tau $的任务数, m为处理器核数. 该加速因子严格小于$3 - 1/m$, 优于已有多核分区调度算法FBB-FFD. 实验表明, PDM-FFD算法在4核处理器上的处理器利用率比其他算法提高了18.5%, 且PDM-FFD的性能优势随着处理器核数、任务集利用率和任务数的增加而进一步扩大. 由于PDM-FFD算法具有高性能特性, 因此该算法可以广泛应用于资源受限的航天器、自动驾驶汽车、工业机器人等典型实时系统中.
2024, 35(11):5319-5340. DOI: 10.13328/j.cnki.jos.007037 CSTR:
摘要:面向人机物融合的泛在计算正成为软件发展的新需求和新趋势, 基于这种新形态计算模式的人机物融合应用将软件技术进一步拓展至对线下资源, 包括物理设备和人力资源的有效利用. 作为典型的人机物融合场景, 物理世界中设备资源与人力资源间的协作具有资源可选性、任务高频性、工人动态性的特点, 传统的资源调度技术无法有效应对该类型任务(简称为DHRC任务)中的调度需求. 为此, 提出一种面向设备与人力资源协作任务的优化调度方法, 所提方法分为设备资源调度和人力资源调度两个阶段. 在设备资源调度阶段, 提出基于NSGA-II 的设备资源调度算法, 在综合考虑任务距离、设备负载和设备位置周边工人人数等因素情况下实现任务对资源的优化选择. 在人力资源调度阶段, 提出基于DPSO的人力资源调度算法, 根据工人位置和协作依赖等因素实现对工人的优化选择以及相应的路径规划. 在模拟环境内的实验结果表明, 所提方法第1阶段的算法在效率上与对比算法相当, 在效用性上优于对比算法(离散粒子群优化算法). 第2阶段的算法在效率上与效用性上均优于对比算法(使用锦标赛机制改进的遗传算法).