首页期刊导航|中国科学F辑
期刊信息/Journal information
中国科学F辑
中国科学杂志社
中国科学F辑

中国科学杂志社

月刊

1674-5973

informatics@scichina.org

100717

北京东黄城根北街16号

中国科学F辑/Journal Science in China(Information Sciences)CSCD北大核心CSTPCD
查看更多>>本刊是中国科学院和国家自然科学基金委员会共同主办、《中国科学》杂志社出版的学术刊物，本刊力求及时报道计算机科学与技术、控制科学与控制工程、通信与信息系统、电子科学与技术、生物信息学等领域基础及应用研究方面的原创性成果；月刊，中文版每月20日出版，英文版每月1日出版。
正式出版
收录年代

    超图上最大独立集问题的精确算法

    白天肖鸣宇
    2709-2726页
    查看更多>>摘要：最大独立集问题是计算机科学中最基础且重要的NP完全问题之一。本文研究了超图上最大独立集问题(MISH)和超图上带惩罚的最大独立集问题(PC-MISH)的精确算法。给定一个超图，MISH问题旨在寻找图中最大的独立集，其中，超图中的独立集是一些两两不包含在同一超边的顶点构成的点子集。而PC-MISH问题是MISH问题的松弛化变体。在PC-MISH问题中，仍然寻找一个点集X，但是它允许违背"独立"的性质，也就是说，允许超边包含X中的多个顶点。这个集合X的价值定义为X的大小减去包含至少两个X中的顶点的超边数量。而PC-MISH问题旨在找到一个价值最大的点集。本文研究MISH和PC-MISH问题以n以及ℓ=n+m为参数的精确算法，其中n是超图中顶点的个数，m是超图中超边的条数。通过利用最大独立集问题在一般无向图上的精确算法可以直接得到MISH问题O*(1。1996n)时间的算法。此外，本文证明了 PC-MISH问题可以在O*(1。9548n)时间内求解，打破了穷举搜索的2n时间复杂度。进一步，本文重点给出MISH问题一个O(1。1520ℓ)时间的算法和PC-MISH问题一个O(1。3982ℓ)时间的算法，分别改进之前时间为O(1。1550ℓ)和1。5ℓ2o(ℓ)的精确算法。

    精确算法最大独立集问题带惩罚最大独立集问题超图最小子集反馈集问题

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    格上唯一最短向量问题的细粒度复杂性

    金保隆薛锐
    2727-2742页
    查看更多>>摘要：唯一最短向量问题(unique shortest vector problem，uSVP)的困难性是一些流行的格密码方案的安全基础，对其在不同参数下的复杂性的研究也是格密码体系的重要组成部分，然而这方面的研究进展十分缓慢，同时对uSVP的细粒度复杂性的研究也十分欠缺。本文改进了一个从最短向量问题(shortest vector problem，SVP)到uSVP的归约算法，提高了其成功概率，调整了参数限制，从而允许建立不同参数条件下从SVP到uSVP的细粒度归约。利用这个归约，得以证明以下结果:(1)在超多项式时间下，得到了一个参数更大的从SVP到uSVP的归约;(2)在强指数时间假设(gap strong exponential time hypothesis，GapSETH)下，构建了从常数参数的SVP到常数参数的uSVP的亚指数时间归约，从而证明了 uSVP在GapSETH下的困难性;(3)以上结果都可以转化成有界距离译码(bounded distance decoding，BDD)的相应结论:在对应条件下求解参数小于1的BDD也是困难的;(4)结合稳定格中的格点个数上界，得到了参数远超常数的从SVP到uSVP的归约。

    最短向量问题唯一最短向量问题计算复杂性细粒度复杂性复杂性归约

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    保证延迟敏感型任务服务质量的情况下利用流处理器内所有并行性以最大化系统吞吐

    赵涵邓俊骁崔炜皞陈全...
    2743-2760页
    查看更多>>摘要：为了应对越来越高的算力需求，GPU在流处理器内集成了多种通用计算单元及专用计算单元(FP32 Core，INT32 Core，FP64 Core，Tensor Core，RT Core)。任意一种 GPU 内可能包含以上计算单元中的部分单元。尽管GPU的流处理器内存在着多种计算单元，它们之间的计算并行性无法从硬件设计白皮书中获知。与此同时，现有调度接口无法支持使用不同计算单元的核函数并行利用这些计算资源，更无法支持运行时的精细调度以最大化系统吞吐。面对以上问题，我们提出了硬件感知吞吐导向的核函数调度方法Hato。Hato首先设计了一个硬件并行性感知工具，支持为任意GPU定位出所有的流处理器内并行性。其次，Hato提出了一个核函数混跑建模方法，通过核函数混跑利用到流处理器内并行性，并支持核函数在混跑情况下的执行时间精准预测。最后，Hato提出了一个吞吐导向的调度策略，支持在保证延迟敏感型应用服务质量的同时，利用到所有可能的流处理器内并行性，以最大化整体系统吞吐。实验结果表明，Hato相比最新调度系统Tacker提升了平均19。2％，最高54。1％的系统吞吐。

    GPU流处理器内并行性吞吐提升运行时系统

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    支持大属性集合的抗泄露属性基加密机制

    周彦伟徐然乔子芮杨坤伟...
    2761-2777页
    查看更多>>摘要：现实环境中各种泄露攻击的存在，使得攻击者能够获得用户秘密信息的部分泄露，导致密码算法的传统安全性在有泄露攻击的环境下不再成立。为进一步防止泄露攻击对数据安全性的危害，密码学研究者提出了一系列具有抗泄露攻击能力的密码算法。属性基加密(attribute-based encryption，ABE)机制由于其能为数据提供细粒度的访问控制能力，在现实环境中得到了广泛的关注和应用。然而，在现有抗泄露ABE机制的构造中，其系统公开参数的尺寸与其所能支持属性集合的大小成正比，导致其无法在大属性集环境中使用。为进一步增强抗泄露ABE机制的实用性和适用性，本文提出了支持大属性集合的抗泄露ABE机制的新型构造方法。为获得更优的计算效率，本文首先在素数阶群上提出了支持大属性集合的抗泄露ABE机制的构造方法，并基于判定的并行双线性Diffie-Hellman指数假设证明了该方案的安全性，同时通过性能分析表明该方案具有较优的计算、存储和通信效率。为获得更紧致的形式化安全性证明过程，本文随后在合数阶群上提出了支持大属性集合的抗泄露ABE机制的构造方法，并基于合数阶群上改进的子群判定假设证明了该方案的安全性。此外，本文还对上述两种抗泄露ABE机制的基本性能进行了对比和分析

    泄露容忍性属性基加密机制大属性集合辅助输入泄露

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    面向多源自主导航的智能学习方法研究

    王巍陈巍孟凡琛
    2778-2793页
    查看更多>>摘要：智能多源自主导航系统以北斗导航为基石、以惯性导航为支撑，旨在提供高度智能化的定位导航与授时服务，通过实现即插即入、无缝衔接、无感切换、可信完备等功能，以满足复杂多变的场景需求。采用以深度学习、强化学习为代表的智能学习方法，从复杂性与多尺度视角出发，探索智能多源自主导航中的优化与协同理论，建立以精准稳定、可信安全、可泛化、可解释、内嵌动力学机理为关键要素的智能学习方法，推动构建弹性、健壮、动态、可控与可信的精准智能多源自主导航模型与方法体系，从而有力支撑国家综合定位导航与授时体系的创新发展和先进导航技术的规模化应用。

    智能多源自主导航内嵌动力学机理可泛化可解释可信性完备性

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    基于流速场预测的水下机器人编队包围算法

    曹文强闫敬杨睍陈彩莲...
    2794-2810页
    查看更多>>摘要：水下目标编队包围控制旨在通过水下机器人环绕运动，可实现对目标的近距离全方位监测。然而，未知流速场与水下机器人模型不确定等约束，导致水下机器人难以形成可靠、稳定的编队队形。为此，研究了基于流速场预测的水下机器人编队包围问题。首先，根据水下机器人真实轨迹与估计轨迹，设计了分布式流速场参数估计器，以实现流速场实时预测。基于此，结合水下机器人状态与环境信息，提出了动力学模型神经网络估计器，设计了基于导航向量场的目标编队包围算法，以在避障同时对移动目标实现包围控制。最后，给出导航向量场和模型估计器权重更新率的理论推导过程。仿真与实验结果表明，所提流速场预测方法可摆脱对划分栅格的依赖，同时，所提算法能在障碍物与未知流速场环境下完成目标包围任务。

    流速场水下机器人包围导航向量场

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    深度嵌入适应度评估分配策略的约束多目标进化优化方法

    左明成巩敦卫
    2811-2827页
    查看更多>>摘要：很多实际问题可以归结为约束多目标优化问题。尽管已有多种求解约束多目标优化问题的方法，但是，在全局搜索空间中高效分配适应度评估资源，实现解方案可行性、收敛性和多样性的平衡仍然是个挑战。鉴于此，本文提出深度嵌入适应度评估分配策略的约束多目标进化优化方法，识别搜索空间中的重点区域，引导种群高效进化。该方法首先采用去噪自编码器设计进化种群的降维模型，获取种群在低维空间的流形;然后，在低维空间中聚类种群数据，获得每类种群约束违反度的方差，辅助感知适合每一种群个体的低维全局和局部搜索范围;最后，基于去噪自编码器获得种群个体的原始空间搜索范围，准确分配适应度评估资源。该方法可嵌入已有的进化算法，能不同程度地提升这些进化算法的性能。将所提方法应用于33个基准测试问题和15个矿山综合能源系统运行优化问题，实验结果表明了所提方法求解约束多目标优化问题的有效性。

    约束多目标优化适应度评估分配深度嵌入进化优化矿山综合能源系统

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    混合攻击下基于带宽感知型事件触发机制的负荷频率控制

    丁瑞森杨飞生付远超潘泉...
    2828-2840页
    查看更多>>摘要：针对混合攻击下的一类新型电力系统，本文提出了一种负荷频率安全控制方案，实现在欺骗与拒绝服务(denial of service，DoS)攻击下的闭环稳定与安全运行。首先，基于确认字符(acknowledgement character，ACK)技术提出了一种针对非周期性DoS攻击的"阴阳"检测机制。其次，为保持系统控制性能并节约网络通信资源，提出了一种新颖的带宽感知事件触发机制。再次，建立了一个混合攻击下包含风力发电机组与电池储能系统的多区域电力系统切换模型。利用Lyapunov-Krasovskii泛函(Lyapunov-Krasovskii functional，LKF)理论与线性矩阵不等式(linear matrix inequality，LMI)技术，给出满足H∞性能的系统指数均方稳定充分条件，并导出了事件触发负荷频率安全控制器的设计准则。最后，通过仿真实验验证了所提DoS攻击检测机制和事件触发安全控制器的有效性与优越性。

    欺骗攻击非周期性DoS攻击带宽感知事件触发机制攻击检测负荷频率控制

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    智能超表面辅助的雷达通信一体化系统恒模发射波形与无源波束形成联合设计

    陈胜垚何煦冯起席峰...
    2841-2857页
    查看更多>>摘要：本文研究一种智能超表面(reconfigurable intelligent surface，RIS)辅助的雷达通信一体化(dual-functional radar and communication，DFRC)系统，在进行多用户通信的同时实现杂波环境下的非视距区域目标探测。为了同时优化雷达和通信性能，本文以雷达接收机的输出信干噪比和通信用户接收信号的均方误差为度量，联合设计DFRC基站的发射波形、RIS反射系数和雷达接收滤波器。由于发射波形和RIS反射系数均受到恒模约束，该问题是一个复杂的非凸约束高阶分式规划问题。为此，本文基于分式规划和交替最小化技术，提出了一种有效的交替优化求解算法。其中，发射波形设计是恒模约束二次函数最小化问题，本文采用二阶黎曼牛顿法快速求解;而RIS反射系数设计是恒模约束四次函数最小化问题，本文利用一致交替方向乘子法技术，通过引入辅助变量将其分解为恒模约束二次函数最小化子问题迭代求解，并采用二阶黎曼牛顿法求解。仿真结果表明，RIS辅助的DFRC系统可以在杂波环境下有效探测非视距目标，且能够显著改善多用户通信性能。

    智能超表面雷达通信一体化流形优化黎曼牛顿法交替方向乘子法

      原文链接:
    • NETL
    • NSTL
    • 万方数据

    新型光纤同沟智能识别算法及试验

    李允博张德朝刘或聪杨辉...
    2858-2867页
    查看更多>>摘要：主备路由光纤同沟是一种高风险事件，光纤选用的随机性导致主备业务可能共享同一沟槽，出现故障会导致主备业务同时中断。当前仅仅依靠人工识别同沟难度大、效率低，给通信网络服务安全性带来了重大风险。为了提升通信网络生存性，本研究提出并验证了一种集成学习检测架构，采用人工智能手段对光纤同沟进行识别。该架构可以在通信网络中实现高准确率的同沟光纤在线识别，无需在线路上人工敲击配合检测。本文采用基于光纤振动动态特性的曲线相似度对比学习器对同沟光纤进行识别，并首次对同沟光纤识别进行了现网试验。对现网中采集到的动态光纤振动数据预处理，基于混淆矩阵中的准确率、F1-score等指标进行评价。本文提出的曲线相似度集成学习算法相比次优非集成学习模型准确度提升6。1％，实验结果验证了所提出架构的可靠性和先进性。

    光纤同沟识别集成学习曲线相似度人工智能网络生存性

      原文链接:
    • NETL
    • NSTL
    • 万方数据