计算机工程与科学

2022年第2期目录

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

摘要 ( 110 )

PDF (282KB) ( 218 ) 　　

面向大规模图计算的连通分量算法分析与优化

白皓, 甘新标, 杨文祥, 贾孟涵, 涂旭平, 张一鸣, 郭敏, 来乐, 张意, 朱春平

2022, 44(02): 191-198. doi:

摘要 ( 257 )

PDF (803KB) ( 286 ) 　　

近年来，图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法，可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历Graph500标准测试，对连通分量算法进行了算法和数据结构优化。主要有以下创新：（1）对并查集提出了捷径向量算法，并测试了算法和数据结构的配合程度；
（2）利用多线程迭代轮转对算法实现并行加速；（3）从多个维度比较了不同实现方法的优缺点。基于优化方法，对性能进行了评估分析，当scale=25（包含225个节点）时，捷径向量算法对基于二维向量和链表的按秩合并算法的加速比分别是1.38倍和1.40倍，对BFS和DFS的加速比分别为4.76倍和4.70倍，且空间占用为该2
个算法的4.1%~4.6%，此外，并行对串行的加速比为1.57倍。

硅转接层高带宽存储互连通道信号完整性设计及仿真

李川, 郑浩, 王彦辉

2022, 44(02): 199-206. doi:

摘要 ( 208 )

PDF (2150KB) ( 241 ) 　　

HBM存储器由于超高的存储带宽在大数据、智能计算等领域具有广阔的应用前景。支持超细线宽的硅转接板是实现存储器与芯片间HBM信号互连的主要载体，从HBM1.0到HBM2E，信号速率达到3.2 Gbps，信号完整性问题不容忽视。从HBM颗粒管脚阵列结构出发，分析信号布线和线宽间距极值。建立2层信号线传输模型，提炼频域阻抗分析方法和总串扰计算方法，从频域角度分析结构参数对电性能传输参数的影响，并从时域进行验证。结果显示：HBM信号线宽间距和应小于6.8 μm；在应用频点范围内，远硅层信号线阻抗比近硅层信号线阻抗高6~8 Ω，3 μm线宽的阻抗值更接近于50 Ω；线宽和线长是插入损耗敏感参数，间距和布线层对损耗影响较小。针对低频区的固有损耗，线宽影响占主导，针对高频区线损耗，线长影响较大。间距是串扰敏感因素，但受空间限制，间距优化有限，引入地屏蔽线是有效的解决办法。

一种基于Chiplet集成技术的超高阶路由器设计

梁崇山, 戴艺, 徐炜遐

2022, 44(02): 207-213. doi:

摘要 ( 197 )

PDF (1034KB) ( 214 ) 　　

高带宽、低延迟的高阶路由器对于构建大规模可扩展的互连网络有着重要的作用,但是受限于单个路由芯片设计复杂度的不断增加以及摩尔定律、登纳德缩放定律的放缓与停滞,在单个路由芯片上扩展更多的端口数将变得越来越难。Chiplet将多个裸片以特定的方式集成在一个高级封装内,形成具有特定功能的大芯片,以此解决芯片设计中涉及的规模、研制成本和周期等方面的问题。根据Chiplet集成技术的思想,利用已有的路由芯片,提出了一种基于Chiplet的128端口高阶路由器,这种高阶路由器内部是一个由多个Switch Die以二层胖树拓扑构成的网络。通过实际的RTL级代码仿真测试,对比于单芯片的高阶路由器设计方式,所设计的路由器在扩展了更多端口数的同时,还能够达到较好的性能。

一种CDC信号滑动窗口时序分析方法

马驰远, 雷国庆

2022, 44(02): 214-219. doi:

摘要 ( 120 )

PDF (875KB) ( 139 ) 　　

异步时钟域设计中CDC信号的时序分析及收敛是超大规模高频数字电路设计功能正确的重要保证。为了减少设计面积，提出了一种CDC信号滑动窗口时序分析方法，该方法在每种corner的每条CDC通路上单独设置适当的时序约束窗口进行时序计算与分析，有效避免了常用的固定约束分析方法由于约束条件过严导致的虚假时序违反及不必要的时序修复，而使设计面积增大的问题，减轻了CDC电路的后端设计工作量。在16 nm工艺下的实验结果表明，该方法在时钟树偏差较大时与固定约束分析方法相比显著节省了设计面积。

基于聚合的FlowRadar网络数据采集加速模型设计

吕高锋, 王玉鹏, 杨鎔嘉, 唐竹

2022, 44(02): 220-226. doi:

摘要 ( 162 )

PDF (918KB) ( 178 ) 　　

网络大数据采集是研究网络行为的基础，可为理解网络行为特征提供真实有效的数据基础。已有的FlowRadar测量方法可针对所有流实现流量编码和解码，且占用较小内存和具备恒定的计数更新时间，但却需要对每个报文进行哈希计算，存在内存访问次数多和计算开销高的问题。针对该问题，基于协议无关交换架构（PISA），采用P4语言设计实现了报文聚合模块和流逐出模块，并通过仿真实验验证了加速模型在吞吐量和网络延时等方面的性能优化。

基于软件定义的WSNs非均匀分簇QoS路由算法

苟平章, 原晨, 张芬

2022, 44(02): 227-236. doi:

摘要 ( 134 )

PDF (846KB) ( 181 ) 　　

针对传统无线传感器网络非均匀分簇QoS路由中节点资源受限，无法动态管理等问题，提出一种基于软件定义的无线传感器网络非均匀分簇QoS路由算法(SDNUCQS)。控制器考虑节点能量、节点间距离和QoS指标，采用熵权法竞选出高质量簇头，并对网络进行非均匀分簇。利用交叉分类法将所要传输的数据通过时延和丢失率分成不同类型。在簇间路由中，控制器以链路QoS指标和节点负载度为参数，采用集中式方式分别计算QoS数据和普通数据传输的最佳路径。仿真实验结果表明，SDNUCQS算法能显著降低网络时延和丢失率，与LEACH、EEUC、CRIPSO和tPSOEB算法比较，能降低簇头能耗且延长了网络生命周期。

基于角色管理的实用拜占庭容错共识算法

李腾, 程哲, 贾东立, 贾耀清

2022, 44(02): 237-243. doi:

摘要 ( 166 )

PDF (540KB) ( 200 ) 　　

针对目前存在的应用于联盟链的实用拜占庭容错（PBFT）共识算法扩展性差、能耗高、效率低和主节点选取方式简单的问题，提出一种基于角色管理的拜占庭容错(RPBFT)共识算法。首先，将系统中的节点划分为管理者、候选者和普通节点3类具有不同职责的角色节点。其次，候选节点具有投票权，投票选举相应的候选节点为管理者；普通节点在满足条件后可以转化为候选节点。最后，通过奖励机制管理不同类型的角色节点之间的转化；不同角色节点的数量能够在网络节点总数发生变化时动态调整，使得算法可以适应动态网络。通过实验得出RPBFT共识算法具有高可靠性、低时延、低能耗和较好的扩展性。

基于深度学习的GPS轨迹去匿名研究

卜冠华, 周礼亮, 李昊, 张敏

2022, 44(02): 244-250. doi:

摘要 ( 146 )

PDF (624KB) ( 187 ) 　　

移动互联网和LBS技术的高速发展使得位置服务提供商可以轻松收集到大量用户位置轨迹数据，近期研究表明，深度学习方法能够从轨迹数据集中提取出用户身份标识等隐私信息。然而现有工作主要针对社交网络采集的签到点轨迹，针对GPS轨迹的去匿名研究则较为缺乏。因此，对基于深度学习的GPS轨迹去匿名技术开展研究。首先提出一种GPS轨迹数据预训练方法，经过子轨迹划分、位置点转化和位置点嵌入，原始GPS轨迹中的空间距离和上下文信息被嵌入到定长向量中，使得GPS轨迹数据能够作为神经网络的输入。其次提出一种基于深度神经网络训练的GPS轨迹去匿名方法，基于预训练得到的向量序列，采用LSTM、GRU等神经网络作为编码器训练拟合用户标识，实现匿名轨迹数据的用户关联。最后基于Geolife轨迹数据集对上述方法进行验证，实验中轨迹去匿名的准确率和Top5准确率分别达到了56.73%和73.48%，实验结果表明，基于深度学习的GPS轨迹去匿名方法能够从匿名轨迹数据中较为准确地识别出用户标识。

基于谱聚类的社交网络差分隐私保护算法研究

袁泉, 晏飞扬, 文志云, 张振康,

2022, 44(02): 251-256. doi:

摘要 ( 142 )

PDF (1165KB) ( 172 ) 　　

针对权重社交网络差分隐私保护算法中噪声添加量过大以及隐私保护不均衡问题，提出了一种结合谱聚类算法与差分隐私保护模型的隐私保护算法SCDP。首先针对传统差分隐私保护算法直接向社交网络边权重添加噪声方式带来的噪声添加量过大的问题，结合谱聚类算法，将权重社交网络聚类成为不同的簇，对不同的簇采取随机添加噪声的方式，降低噪声的添加量，提高数据的可用性；其次设计新的隐私预算参数，根据社交网络边权重的大小决定噪声的添加量，实现更均衡的隐私保护；最后通过理论推导和实验证明了SCDP算法处理后的数据可用性更高。

基于代理辅助多目标萤火虫算法的软件缺陷预测方法研究

曹良林, 贲可荣, 张献

2022, 44(02): 257-265. doi:

摘要 ( 104 )

PDF (697KB) ( 166 ) 　　

针对软件缺陷预测中数据维度的复杂化和类不平衡问题，提出一种基于代理辅助模型的多目标萤火虫算法(SMO-MSFFA)的软件缺陷预测方法。该方法采用了多组策略萤火虫算法（MSFFA），以最小化数据的特征选择比率和最大化模型评测AUC值为多目标目标函数，分别以随机森林(RF)、支持向量机(SVM)和K近邻分类算法(KNN)为分类器构建软件缺陷预测模型。考虑到进化算法自身的迭代特点，嵌入代理模型离线完成部分个体评价函数的计算，以缩短计算耗时。在公开数据集NASA中的PC1、KC1和MC1项目上进行实验验证，与NSGA-II方法相比，在项目PC1、KC1和MC1上模型AUC均值分别提升0.17、降低0.01和提升0.09，平均特征选择比率分别降低0.08,0.17和0.05，平均耗时分别增加131 s,降低了199 s和降低了431 s。实验结果表明，提出的方法在提高模型性能、降低特征选择比率和缩短计算耗时方面具有明显的优势。

基于模糊决策过程的模糊计算树逻辑模型检测

李召恺, 马占有, 李健祥, 郭昊

2022, 44(02): 266-275. doi:

摘要 ( 150 )

PDF (689KB) ( 199 ) 　　

针对由数据表述产生的不确定性模糊系统的模型检测问题，给出模糊计算树逻辑模型检测算法。首先，引入模糊决策过程作为此类系统的模型，其最大特点是在迁移过程中对动作的不确定性选择和状态表述的模糊性。然后，在模糊决策过程基础上，给出模糊计算树逻辑的语法和语义。最后，给出模糊计算树逻辑模型检测算法，该算法是将模糊计算树逻辑模型检测问题转换为模糊矩阵的合成运算，其优势是时间复杂度低、计算过程较为简洁。

基于混合注意力机制的目标跟踪算法

冯琪堯, 张惊雷,

2022, 44(02): 276-282. doi:

摘要 ( 196 )

PDF (854KB) ( 256 ) 　　

针对全卷积孪生网络目标跟踪算法(SiamFC)在目标形变、遮挡和快速运动等复杂场景中易导致跟踪失败的问题，提出一种利用混合注意力机制增强网络识别能力的算法(SiamMA)。首先，在训练阶段提出堆叠裁剪法构建自对抗训练样本对，以模拟实际跟踪时的复杂场景，使训练的网络模型具有更强的泛化性。其次提出混合注意力机制，在网络不同分支融合使用空间注意力和通道注意力网络模块，有效抑制了特征图中的背景干扰，提升算法的鲁棒性。采用GOT-10k、UAV123等4种数据集进行算法性能评测实验，结果表明本文算法的跟踪成功率、精度等主要性能指标较SiamFC和KCF等6种经典算法均有提升，平均速度达到60 fps。

基于特征聚类的大视差图像拼接算法

许光宇, 丁健

2022, 44(02): 283-290. doi:

摘要 ( 201 )

PDF (1162KB) ( 226 ) 　　

针对大视差图像拼接过程中出现的错位、重影等问题，提出一种基于特征聚类的图像拼接算法。首先，以已匹配的特征点分布为依据在目标图像重叠区域构造泰森多边形。然后使用改进的AGNES层次聚类算法对特征点聚类,合并对应组内特征点所代表的泰森多边形，得到目标图像重叠区域的各个子平面。最后，求解对应子平面的单应性矩阵，并采取就近原则分配非重叠区域的单应性矩阵，对目标图像进行投影变换，得到拼接图像。实验结果表明，所提算法具有较高的配准精度，可有效改善大视差图像拼接过程中出现的误配准和局部失真问题。

改进标签一致KSVD字典学习的人脸识别算法

严春满, 张昱瑶, 张迪

2022, 44(02): 291-297. doi:

摘要 ( 127 )

PDF (611KB) ( 187 )

PDF（mobile） (611KB) ( 6 ) 　　

针对噪声污染、光照变化等复杂环境下人脸图像识别问题，提出一种改进标签一致KSVD字典学习的人脸识别算法。该算法通过改变标签一致KSVD算法的字典更新方式，用主成分分析算法分解误差项，用最大特征值对应的特征向量修改字典原子。通过字典学习过程得到原子与类别标签对应的判别性字典。目标函数综合了重建误差、稀疏编码误差和分类误差。最后，在分类阶段利用学习到的字典和分类器参数对测试样本进行分类。在有光照变化的Extend Yale B人脸库、表情变化以及遮挡影响的AR人脸库上分别取得了99.01%和97.94%的平均识别率。同时，在有噪声存在的情况下，该算法具有较好的鲁棒性。

WiFi环境下基于CGRU-ELM混合模型的手势识别

张鑫, 冯秀芳

2022, 44(02): 298-305. doi:

摘要 ( 142 )

PDF (1669KB) ( 174 ) 　　

针对传统手势识别方法存在的耗能大、部署困难等问题，提出了一种基于WiFi的手势识别方法。通过从WiFi信号中收集到的信道状态信息中抽取多普勒频移组件，解决无线手势识别方法中提取的统计特征与具体手势动作映射关系不明确的问题。同时，提出了一种CGRU-ELM的深度混合模型，对提取到的多普勒频移组件进行特征提取和分类，并对常用的6种人机交互手势进行了识别。实验结果表明，该方法对于以WiFi信号为输入参数的手势识别平均准确度达到了93.4%。

一种基于GN算法的动态图划分方法

罗晓霞, 王佳, 罗香玉, 李嘉楠

2022, 44(02): 306-311. doi:

摘要 ( 142 )

PDF (593KB) ( 199 ) 　　

随着图规模的急剧增长，对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的，直接用其处理动态图会带来较大的通信开销。针对该问题，提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点；然后，利用GN算法对这些新加入的顶点进行预划分，产生若干个内部联系紧密的社区；最后，将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较，结果表明，
在公开数据集上，该方法的交叉边数降低了13%，负载均衡度减少了42.3%。由此可见，该方法的划分质量明显优于传统的流式划分方法。

用于人体检测的YOLOv3改进及压缩算法的研究

张玉杰, 董蕊

2022, 44(02): 312-320. doi:

摘要 ( 132 )

PDF (961KB) ( 242 ) 　　

针对Yolov3算法应用于人体检测中的准确率低，参数量、计算量和模型体积大难以在资源有限的嵌入式平台上实现等问题，提出了YOLOv3改进及其模型压缩算法。在YOLOv3中通过引入密集连接与多分支结构，增加网络宽度和多尺度感受野，加强特征重用，提高了模型的检测精度；对改进的YOLOv3通过联合优化权重损失函数和BN层缩放因子的L1正则项等方式进行通道剪枝，从而减小了参数量和计算量，模型体积得到了大幅压缩。实验结果表明，改进后YOLOv3算法的检测精度提升了601%，模型体积减小了38.46%；经过压缩后，模型的检测精度虽然降低了3.16%，但模型体积仅为原来的3.31%，只有4.77 MB。
因此,通过改进和压缩后的YOLOv3仍然保持较高的检测精度，而且模型体积得到大幅度的压缩，为YOLOv3模型在嵌入式平台上实现人体检测提供了支撑。

多源图像融合方法的研究综述

张丽霞, 曾广平, 宣兆成

2022, 44(02): 321-334. doi:

摘要 ( 650 )

PDF (1038KB) ( 788 ) 　　

由于成像机理不同，多源图像有本质区别，使得其在融合过程中存在差异。在参阅了大量中外文献的基础上，对融合方法进行分类，并重点论述了各类融合方法的融合过程和典型算法，详细阐述了其关键技术。同时，深入评述了当前的评价指标和分类。最后，结合关键技术的影响因素和技术的发展状况，从数据特征、时间效率、信息提取、评估角度和方法的普适性5个方面对融合图像领域的未来发展趋势进行了展望。

图自编码器推荐研究综述

李方, 吴国栋, 涂立静, 刘玉良, 查志康, 李景霞

2022, 44(02): 335-344. doi:

摘要 ( 513 )

PDF (805KB) ( 483 ) 　　

图自编码器GAE是一种源自图神经网络的学习框架，在编码器中引入聚合邻域节点的思想，解码器对图结构数据进行解码，重构图结构数据；在模型中引入监督模块，可以提高图结构数据在模型中的嵌入完整性和数据生成的准确性；编解码可以采用不同的神经网络，从而利用不同神经网络的优点。近年来GAE推荐逐渐成为推荐系统研究的热点。从无监督学习与半监督学习方面分析了已有GAE推荐研究取得的进展；探讨了已有GAE推荐模型存在用户冷启动问题、可解释性差、模型复杂度高和难以处理数据的多源异构性等方面的问题；并从跨领域推荐，结合传统推荐方法，引入注意力机制，融合各类场景等研究方向对未来GAE推荐进行展望。

区间值广义正交模糊Frank算子及群决策方法

万本庭, 方地长

2022, 44(02): 345-354. doi:

摘要 ( 104 )

PDF (548KB) ( 177 ) 　　

基于区间值广义正交模糊环境和Frank算子，定义了区间值广义正交模糊Frank算子的运算法则，提出了区间值广义正交模糊Frank加权平均算子（IVq-ROFFWA）和加权几何算子（IVq-ROFFWG），并研究了它们的幂等性、有界性和单调性。然后提出了基于IVq-ROFFWA算子的多属性群决策方法（MAGDM），该方法通过选取满足条件的q值，使用IVq-ROFFWA算子集结得到目标区间值模糊数，比较它们的得分得到最优方案，还得出了不同q值不影响最优方案排序的结论。最后通过实际案例验证了基于IVq-ROFFWA算子的多属性群决策方法的可行性和有效性，验证了不同q值不影响最优方案排序的结论。经过比较分析，基于IVq-ROFFWA算子和IVq-ROFFWG算子的群决策方法与基于其他算子的群决策方法运算结果一致。

基于混合反向学习策略的鲸鱼优化算法

耿召里, 李目, 曹淑睿, 刘昶忻

2022, 44(02): 355-363. doi:

摘要 ( 226 )

PDF (804KB) ( 291 ) 　　

针对鲸鱼优化算法(WOA)在解决高维复杂问题时存在收敛速度慢、全局搜索能力不足的问题，提出一种最优最差个体混合反向学习的WOA（MWOA）。首先，引入一种自适应惯性权重，用于调节寻优前期的步长和寻优后期的种群多样性；其次，提出一种混合反向学习策略并将其融入WOA，以提高算法的收敛精度；最后，引入一种参数非线性衰减策略，以提高其在高维度以及复杂问题上的探索开发能力和收敛速度。将MWOA与WOA、MS-WOA、IWOA对10个基准函数的优化效果进行比较，结果表明MWOA在收敛速度、优化精度上相较对比算法均有所提升。另外，将MWOA与CODE、CPSO、EGWO和DIHS进行比较，结果表明MWOA具有较好的收敛精度。

几类带空转移的n元伪加权自动机的关系

赵路瑶, 王海辉, 李平

2022, 44(02): 364-371. doi:

摘要 ( 100 )

PDF (493KB) ( 127 ) 　　

引入了n元伪加权有穷自动机——带有n个有限字符集的伪加权有穷自动机、分明型n元伪加权有穷自动机和确定型n元伪加权有穷自动机的概念。根据状态转移函数在每个字符集上是否带空转移, 将以上自动机分为4类:带r-型空转移的n元伪加权有穷自动机和带空转移的n元伪加权有穷自动机和带r-型空转移的分明型n元伪加权有穷自动机和带空转移的分明型n元伪加权有穷自动机。给出了以上自动机所识别语言的定义并探究了它们之间的关系,讨论了状态转移函数在每个字符集上是否带空转移对其接受语言的影响。

基于密度和中心指标的Canopy二分K-均值算法优化

沈郭鑫, 蒋中云

2022, 44(02): 372-380. doi:

摘要 ( 148 )

PDF (961KB) ( 179 ) 　　

针对二分K-均值算法由于随机选取初始中心及人为定义聚类数而造成的聚类结果不稳定问题，提出了基于密度和中心指标的Canopy二分K-均值算法SDC_Bisecting K-Means。首先计算样本中数据密度及其邻域半径；然后选出密度最小的数据并结合Canopy算法的思想进行聚类，将得到的簇的个数及其中心作为二分K-均值算法的输入参数；最后在二分K-均值算法的基础上引入指数函数和中心指标对原始样本进行聚类。利用UCI数据集和自建数据集进行模拟实验对比，结果表明SDC_Bisecting K-Means不仅使得聚类结果更精确，同时算法的运行速度更快、稳定性更好。

当期目录

作者中心

审稿中心

在线期刊