计算机工程与科学

2022年第7期目录

2022, 44(07): 0-0. doi:

摘要 ( 49 )

PDF (246KB) ( 58 ) 　　

面向Flink的负载均衡任务调度算法的研究与实现

李文佳, 史岚, 季航旭, 罗意彭

2022, 44(07): 1141-1151. doi:

摘要 ( 113 )

PDF (1192KB) ( 83 ) 　　

Apache Flink是现在主流的大数据分布式计算引擎之一，其中任务调度问题是分布式计算系统中的关键问题。由于集群的异构性以及不同算子复杂度不同，大数据计算系统Flink中不可避免地会出现负载不均的情况，针对这种问题，提出了基于资源反馈的负载均衡任务调度算法RFTS。通过实时资源监控、区域划分和基于人工萤火虫优化的任务调度算法3个模块，把负载过重的机器中处于等待状态的任务分配给负载较轻的机器，来实现集群的负载均衡，提高系统集群利用率和执行效率。最后通过基于TPC-C和TPC-H数据集的实验结果表明，RFTS算法从执行时间和吞吐量2个方面有效提升了Apache Flink计算系统的性能。

基于MPI的并行大数据集生成器

葛旭冉, 刘洋, 陈志广, 肖侬

2022, 44(07): 1152-1161. doi:

摘要 ( 107 )

PDF (1763KB) ( 59 ) 　　

大数据处理分析算法在优化研究过程中，速度常常受限于数据集的规模。在数据集体量不足时，算法的通信时间往往要高于真正的计算时间，无法验证真实的效果。故设计实现了一个大数据集生成器，为运行在超级计算机上的并行大数据处理分析算法提供基准测试数据集。首先，使用MPI并行编程技术构造了一个并行随机数生成器，在此基础上设计实现了可控制规模及复杂性的人工数据集，主要包括：分类和聚类数据集、回归数据集、流形学习数据集和因子分解数据集等。其次，设计了大数据集生成器的I/O系统，提供MPI-I/O并行读、写数据集的接口，并设置了数据集在不同进程间的分发、映射规则，通过点对点通信实现不同节点之间的数据交互。实验结果表明，并行大数据集生成器有效提高了数据生成效率和生成规模，为并行大数据处理分析算法提供了高质量、大体量的测试数据集。

国产通用处理器密码算法指令实现研究

陈子钰, 何军, 郭翔宇

2022, 44(07): 1162-1170. doi:

摘要 ( 83 )

PDF (932KB) ( 53 ) 　　

介绍了国际主流密码算法AES和SHA，综述了当前主流通用处理器架构的密码算法指令发展现状。为提高国产通用处理器在密码安全领域的性能，设计了面向国产通用处理器的AES和SHA密码算法扩展指令集，实现了能全流水执行的AES和SHA密码算法指令执行部件，并进行了实现评估和优化。该密码算法指令执行部件的工作频率达2.0 GHz，总面积为17 644 μm2，总功耗为59.62 mW，相比软件采用原有通用指令实现，对AES密码算法的最小加速比为8.90倍，对SHA密码算法的最小加速比为4.47倍，在指令全流水执行时可达19.30倍，显著地改善了处理器执行AES和SHA密码算法的性能，有望应用于国产通用处理器并进一步提升国产通用处理器芯片在密码安全应用领域的竞争力。此外，该密码算法指令部件还可以封装成专门用于支持密码算法的IP，应用在密码安全领域的专用芯片中。

多路系统Cache一致性验证中的错误追踪定位技术

李辉, 巨鹏锦, 计永兴

2022, 44(07): 1171-1180. doi:

摘要 ( 82 )

PDF (1495KB) ( 52 ) 　　

以某国产多路系统的验证为例，基于事务级验证TBV技术，提出并实现了一种可以应用于模拟验证的自动错误追踪定位技术，通过在验证环境中对处理器的特定功能流程、相关各种请求响应、访存地址和数据流等信息进行事务级建模，记录并生成了验证环境运行产生的事务级信息库，基于上述信息实现了错误的自动追踪定位，显著缩短了错误定位时间，提升了多路系统模拟验证的查错效率。同时，基于事务级的模型，也使得验证人员可以在比设计部件更高的层次描述复杂流程的Cache一致性覆盖点，这种事务级维度的覆盖率描述弥补了原有代码覆盖率和功能覆盖率局限于模块和部件级的不足，是对全面性和充分性验证的有益补充。

基于NR-Transformer的集群作业运行时间预测

陈奉贤

2022, 44(07): 1181-1190. doi:

摘要 ( 83 )

PDF (1140KB) ( 58 ) 　　

高性能集群的作业调度通常使用作业调度系统来实现，准确填写作业运行时间能在很大程度上提升作业调度效率。现有的研究通常使用机器学习的预测方式，在预测精度和实用性上还存在一定的提升空间。为了进一步提高集群作业运行时间预测的准确率，考虑先对集群作业日志进行聚类，将作业类别信息添加到作业特征中，再使用基于注意力机制的NR-Transformer网络对作业日志数据建模和预测。在数据处理上，根据与预测目标的相关性、特征的完整性和数据的有效性，从历史日志数据集中筛选出7维特征，并按作业运行时间的长度将其划分为多个作业集，再对各作业集分别进行训练和预测。实验结果表明，相比于传统机器学习和BP神经网络，时序神经网络结构有更好的预测性能，其中NR-Transformer在各作业集上都有较好的性能。

一种面向分布式深度学习的轻量级聚合通信库

王笑雨, 董德尊

2022, 44(07): 1191-1198. doi:

摘要 ( 98 )

PDF (924KB) ( 69 ) 　　

聚合通信操作在分布式训练中应用广泛，特别是AllReduce操作被用于同步每个节点上模型的参数。为了获得更高的精度，数据集和神经网络模型的规模越来越大，节点间的通信开销在训练过程中占比很大且已成为训练加速的瓶颈。目前已有许多针对这一场景下聚合操作的优化工作，但都聚焦于操作的合理使用而不是其本身，例如通信调度和梯度量化。事实上，聚合操作与分布式训练应用之间存在许多不相匹配的地方，比如后者不要求所有节点同时同步梯度，而前者却需要。这使得针对分布式训练中聚合通信的研究是有必要的。然而发现目前分布式训练中的通信框架结构复杂、代码量大，对开展相关工作来说是不合适的。为了解决这一问题，设计并实现了一个轻量级的聚合通信库，以方便分析和改进分布式训练中的聚合操作。它支持主流框架和网络，并且架构简洁。这便于研究人员实现自定义通信操作，并能应用到主流的实验环境中以产生较广的影响。在多种情况下分别通过纯聚合操作和分布式深度学习应用来评估所设计的聚合通信库。实验结果显示，该库可以实现与MPI相近的性能，可以作为分析和研究分布式训练中梯度同步的聚合通信库。

小信号放大电路任意波形THD全自动测量系统研究

桂丹, 喻宗杰

2022, 44(07): 1199-1206. doi:

摘要 ( 88 )

PDF (2008KB) ( 56 ) 　　

总谐波失真THD是衡量信道非线性程度的重要指标，应用于音频小信号放大电路的任意输出波形识别和总谐波失真的全自动测量系统成为检测信号放大性能的有效手段。为准确计算放大后的波形总谐波失真度，采用了快速傅里叶变换FFT技术。从提高系统效率角度，使用高频率采样并半数提取的技术方案。通过动态控制继电器、阻容元件及多级放大等手段，合理调整放大系统静态工作点的位置和输入波形大小，实现不同类型的失真波形输出。基于stm32f103c6单片机，联动开关一键式完成任意波形采集、识别、计算和显示，极大提升了小信号放大电路失真度测量的工作效率。Matlab运算仿真、Multisim电路仿真及实物测试表明，多级晶体管放大一致性调节电路和单片机FFT运算组成的小信号放大电路任意波形THD全自动测量系统，可准确、实时识别波形并计算出总谐波失真，一键式切换设计操作方便、节约成本，颇具实用价值。

一种基于聚类与噪声的网络流量分类方法

庞兴龙, 朱国胜, 杨少龙, 李修远

2022, 44(07): 1207-1215. doi:

摘要 ( 77 )

PDF (1303KB) ( 53 ) 　　

在标注现实网络流量数据的过程中难免会造成标签错误标记的情况，导致标签数据不可避免地受到噪声污染，即样本的观测标签与真实标签存在差异。为降低噪声标签对分类器分类准确率的负面影响，考虑引入噪声的2种情况，即正确标签类型错误标记和标签类型错误拼写，并提出一种基于标签噪声纠正的网络流量分类方法，该方法利用聚类和权重划分来对观测样本进行评估和修复。在2个网络流量数据集上的实验结果表明，与3种标签噪声修复算法STC、CC和ADE相比，提出的修复算法在不同噪声比例干扰下对最终的分类结果都有一定的提升。在NSL-KDD数据集上，标签平均修复率分别提高23.00％,7.58%和2.05％左右；在MOORE数据集上，标签平均修复率分别提高35.12％,10.40%和471％左右，在最终分类模型上有较好的分类稳定性。

无人机辅助的无线传感网络AoI最小化方案研究

赵玉华, 贾向东, 胡海霞, 敬乐天

2022, 44(07): 1216-1222. doi:

摘要 ( 87 )

PDF (952KB) ( 60 ) 　　

针对无线传感器网络中海量数据处理过程中信息新鲜度问题，基于无人机飞行速度、高度、避碰和可靠传输等约束，以系统信息年龄AoI为考核参数提出了一种联合采集点选择、轨迹优化及无人机工作时间权衡的AoI最小化非凸优化方案。以一个多无人机在同频段条件下为多个传感器节点传输能量并收集传感数据为场景，对多架无人机在三维空间中的信息采集过程进行模拟验证。通过SCA优化算法将建立的非凸问题转化为一个凸优化问题进行求解，最终得到无人机飞行过程中的最优采集点、最优飞行策略及能量输送时间与信息传输时间分配权衡指数，使系统性能达到最优，实验结果表明，所提方案求得的最优解可有效实现系统AoI最小化。

基于多智能体的海外反恐运输投送模型研究

董鹏, 石怀斌, 史博元, 张其霄

2022, 44(07): 1223-1231. doi:

摘要 ( 58 )

PDF (2026KB) ( 43 ) 　　

针对海外物资运输投送中存在的成本高、不及时和不充足等问题，为有效规划海外反恐编队海上供应保障方案,探索运输投送高效保障模式，建立了对某地区基地反恐行动进行海外投送的模型。紧密结合海外运输投送特点，并利用Anylogic多智能体对其进行模拟仿真，对2种海外投送方案进行对比的结果表明，该模型对于海外物资运输投放具有较好的适用性，能够降低投放成本，并且对海外投送模式探寻也具有一定的参考意义。

基于雾计算面向停车服务的隐私保护方案

寇邦艳, 曹素珍, 吕佳

2022, 44(07): 1232-1238. doi:

摘要 ( 70 )

PDF (711KB) ( 46 ) 　　

停车服务为司机提供了寻找空闲停车位的便利，但现有的大多数停车方案将停车请求上传至云服务器进行处理和分析，易导致通信延迟和用户隐私泄露等问题。针对上述问题，提出了一种基于雾计算面向停车服务的隐私保护方案，通过雾节点实现司机与停车位的匹配，使用基于椭圆曲线的签名技术实现身份认证；利用布隆过滤器和模糊提取器，在不公开用户隐私信息的情况下实现空闲停车位的查询；采用TA签名的电子钱包实现支付功能。此外，通过安全性分析和仿真可知，该方案不仅满足安全性和隐私性，而且计算成本较低。

基于特征通道和空间位置注意力的三维点云特征学习网络

吴亦奇, 韩放, 张德军, 何发智, 陈壹林

2022, 44(07): 1239-1246. doi:

摘要 ( 135 )

PDF (704KB) ( 87 ) 　　

点云模型的分类与部件分割是三维点云数据处理的基本任务，其核心在于获取可以有效表示三维模型的点云特征。提出一个引入注意力机制的三维点云特征学习网络。该网络采用多层次点云特征提取方法，首先使用特征通道注意力模块获取各通道间的关联，增强关键通道信息; 接着引入空间位置注意力机制，基于点的空间位置信息获取各点的注意力权重；然后结合以上2种注意力机制获取增强的点云特征;最后基于该特征继续进行多层次特征提取，获得面向下游任务的点云特征。分别在ModelNet40和ShapeNet数据集上进行形状分类与部件分割实验，结果表明，使用所提方法可以实现高精度、具有鲁棒性的三维点云形状分类与分割。

面向点云三维重建的空间感知对抗神经网络

卢林鹏, 关柏良, 林淑金

2022, 44(07): 1247-1255. doi:

摘要 ( 74 )

PDF (1567KB) ( 80 ) 　　

为了解决由原始点云数据局部密度稀疏、不均匀或者法向量错误等制约因素引起的重建网格质量问题,利用对抗神经网络中权重共享的特性和对抗的训练过程,提出一种基于对抗网络的点云三维重建方法。首先，利用预测器对网格模型边的偏移量进行预测，从而得到每一个顶点的位移，并进行拓扑保持的顶点重定向，得到新的网格模型。然后，利用判别器中的点云分类器，提取原始点云数据和网格模型表面采样点集的高维特征，并基于高维特征进行空间感知的判别，用于区分原始点云与采样点集数据。最后，使用对抗的训练方式将预测器与判别器的输出数据关联起来，通过多次迭代优化网络模型，从而得到满足点云空间特征的三维网格模型。在不同的点云数据集上进行实验，并使用MeshLab软件进行效果展示，结果表明，该方法能够重建出满足点云空间信息的三维网格模型，同时能够解决粗劣的点云数据引起的网格质量问题。

基于区域划分和四元数的彩色图像复制粘贴篡改检测

魏伟一, 王婉茹, 赵毅凡, 陈帼

2022, 44(07): 1256-1264. doi:

摘要 ( 61 )

PDF (1442KB) ( 46 ) 　　

现有的篡改检测方法中特征点提取不充分会导致篡改检测精度不高，特征点描述符识别率差，针对该问题提出一种基于颜色矩的区域划分和四元数Hu矩的彩色图像复制粘贴篡改检测算法。首先，使用自适应形态重建算法对图像进行超像素分割，通过密度聚类算法对图像自适应划分区域；其次，提出一种关键点提取方法得到均匀的SIFT特征点；然后，在一种新颖的彩色图像四元数表示方法中构建局部高斯金字塔提取Hu矩特征；最后，利用2NN进行特征匹配后，结合Delaunay三角形算法定位出复制粘贴篡改区域。在公共数据集上的实验结果表明，该算法可以更有效地定位篡改区域。

基于轻量级神经网络的目标检测研究

黄志强, 李军, 张世义

2022, 44(07): 1265-1272. doi:

摘要 ( 69 )

PDF (1042KB) ( 104 ) 　　

由于以CSPDarknet53为主干的YOLOv4神经网络参数量巨大，将其移植至手机等小型设备上时会降低其检测精度和速度，为了提高检测速度同时将检测精度控制在合理范围内，提出将原有的53层神经网络改为15层，并对其中的聚类算法进行优化，引入K-means++聚类算法对数据集进行分析，生成满足检测条件的Anchor Box；使用在负区间带有一定斜率的LeakyReLU激活函数代替存在梯度消失问题的Sigmoid激活函数，从而增强浅层网络的学习能力；同时考虑到Bounding Box与Anchor Box之间的中心距和宽高比具有一定的相关性，提出在原有损失函数的基础上增加相应的惩罚项生成LCIoU损失函数，使损失函数在反向传播时梯度下降的方向性更好。实验结果表明，改进后的CSPDarknet15神经网络在VOC2007数据集上检测的平均精度达到83.94%，检测一幅图像的时间为3 625 ms，与CSPDarknet53神经网络相比，检测速度提高了54.43%，能满足小型设备实时检测的速度和精度要求。

基于改进A*算法和动态窗口法的机器人路径规划

郭园园, 袁杰, 赵克刚

2022, 44(07): 1273-1281. doi:

摘要 ( 189 )

PDF (1518KB) ( 117 ) 　　

针对移动机器人在复杂环境下(包含静态和动态环境)的路径规划效率低的问题，提出了一种改进的A*算法与动态窗口法相结合的混合算法。针对传统A*算法安全性不足的问题，采用障碍规避策略，优化节点的选择方式，增加路径的安全性；针对转折点多的问题，采用递归二分法优化策略，去除冗余节点，减少转弯次数；针对静态环境下路径平滑性不足的问题，采用动态内切圆平滑策略将折线角优化成弧度角，以增加路径的平滑性。对于传统动态窗口法的目标点附近存在障碍物时规划效果不好和容易在凹型槽类障碍物中陷入局部最优的问题，在原有的评价函数中引入了距离偏差和轨迹偏差。最后，对所提的改进A*算法和混合算法分别在静态和动态环境下与其他算法进行仿真比较。从结果可以看出，与传统混合算法相比，临时障碍环境下，路径长度和运行时间分别缩短了13.2%和65.8%；移动障碍环境下，路径长度和运行时间分别缩短了13.9%和44.9%，所提的算法提高了在复杂环境中规划路径的效率。

多文字可满足SAT问题的相变点上界

芦磊, 王晓峰, 梁晨, 张九龙

2022, 44(07): 1282-1290. doi:

摘要 ( 80 )

PDF (664KB) ( 34 ) 　　

可满足（SAT）问题是指：是否存在一组布尔变元赋值，使得随机合取范式（CNF）公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值，使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比，对该问题的相变点上界α*进行了研究。如果α>α*，则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断，可以证明α*=-ln 2/ln(1-(k+1)/2k)，当k=3时，α*=1。利用Kirousis等人的局部最大值技术，提升了多文字可满足3-SAT问题的相变点上界α*=0.7193。最后，选择了大量数据进行实验验证,结果表明，理论结果与实验结果相吻合。

面向公平保障的共乘定价与匹配算法

林彦佳, 武继刚, 吴嘉鑫, 陈龙

2022, 44(07): 1291-1301. doi:

摘要 ( 72 )

PDF (1326KB) ( 42 ) 　　

在共乘场景中，具有相似行程和时间安排的多名乘客一同出行，可降低出行成本、提高车辆上座率和缓解交通拥堵。现有研究忽略了共乘收费标准不统一和司机恶意竞价对乘客共乘体验的影响。在同时考虑费用约束、车辆容量约束和绕路距离约束的的情况下，提出最大化匹配结果公平性的方案，并将共乘的定价与匹配过程建模为一个两阶段的主从博弈。针对上述方案，提出了一个基于K-means++的请求划分算法,以缩小司乘匹配范围，提高匹配效率；在满足所有参与者约束的前提下，设计了基于两阶段主从博弈的迭代算法DPMA，并从理论上证明了其收敛性。在纽约出租车数据集上进行了仿真实验，通过不同的参数设置验证了DPMA的收敛性。与已有的2个算法相比，DPMA在保障司机收益的同时，在公平指数上分别提高了34.03%和24.42%。实验结果表明所设计机制可以有效避免司机间的恶意竞价，且提高了共乘匹配的公平性。

一种基于CSI的高鲁棒性步态识别方法

郝占军, 乔志强, 党小超, 段渝

2022, 44(07): 1302-1312. doi:

摘要 ( 81 )

PDF (1848KB) ( 75 ) 　　

针对目前的室内人员步态识别方法存在计算量大、设备成本高、鲁棒性低等问题，提出一种基于信道状态信息的高鲁棒性室内人员步态识别方法WiKown。通过快速傅里叶变换设置能量指示器监测人员行走行为，将采集的CSI步态数据经滤波与降噪处理后以滑动窗口的方式提取特征值，得到人员步态的CSI信息后建立观测序列，最后通过高斯分布叠加拟合后引入隐马尔科夫模型计算观测序列概率，生成步态参数模型。在走廊、实验室和大厅真实多人环境中，WiKown方法对单人步态的平均识别率达到92.71%。实验结果表明，与决策树、动态时间规整和长短时记忆网络方法相比较，该方法能有效地识别出人员的步态信息，提升了识别精度和鲁棒性。

基于多重相关信息交互的文本相似度计算方法

袁野, 廖薇

2022, 44(07): 1313-1320. doi:

摘要 ( 94 )

PDF (827KB) ( 64 ) 　　

文本相似度计算是自然语言处理的核心任务之一，传统的文本相似度计算方法只考虑文本的结构或者语义等单方面特征，缺少对文本多特征的深度分析，导致性能较低。提出一种基于多重相关信息交互的文本相似度计算方法，在文本嵌入矩阵中增加余弦相关性特征,使用自注意力机制考虑文本自身的相关性和词语依赖关系，进而使用交替协同注意力机制提取文本之间的语义交互信息，从不同角度获得更深层、更丰富的文本表征。实验结果表明,所提方法在2个数据集上的F1值分别为0.916 1和0.769 5，其性能优于基准方法的。

随机约束满足问题相变研究综述

牛鹏飞, 王晓峰, 芦磊, 张九龙

2022, 44(07): 1321-1330. doi:

摘要 ( 87 )

PDF (604KB) ( 57 ) 　　

随机约束满足问题是经典的NP完全问题，在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象，近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手，从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。

当期目录

作者中心

审稿中心

在线期刊