基于多选项二次联合背包的态势感知资源分配算法Resource.PDFVIP

第 37 卷第 12 期 通 信 学 报 Vol.37 No.12 2016 年 12 月 Journal on Communications December 2016 doi:10.11959/j.issn.1000-436x.2016272 基于多选项二次联合背包的态势感知资源分配算法 孙岩炜 1 ，郭云川 1 ，张玲翠 1 ，方滨兴 2 (1. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093 ； 2. 东莞电子科技大学电子信息工程研究院，广东 东 523808) 摘 要：为了有效应对潜在网络威胁，通过合理利用资源达到最大化提升当前环境安全态势的目的，研究了有限 资源的最优分配方案。网络态势的整体性特点使针对某一指标的改善可能会间接影响其他指标，并且投入力度不 同，影响程度也有所差异。针对上述特性，将问题抽象成多选项二次联合背包模型，通过二次背包特性表示态势 评估指标项之间的相互影响，通过多选项背包特性来表示单个指标项的多种投入可能。最后对其做半定规划松弛， 采用分支定界法对问题进行求解。实验证明了算法的准确性和高效性。 关键词：资源分配；态势感知；多选项二次联合背包；半定松弛 中图分类号：TP301 文献标识码：A Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack 1 1 1 2 SUN Yan-wei , GUO Yun-chuan , ZHANG Ling-cui , FANG Bin-xing (1.State Key Laboratory of Information Security, Institute of Information Engineering, CAS, Beijing 100093, China; 2. Institute of Electronic and Information Engineering, University of Electronic Science and Technology of China in Dongguan, Dongguan 523808, China) Abstract: In order to deal with the potential cyber-threat and improve the security situation by using limited resource properly, the optimal allocation of resource focused on cyber security situation. The coherence of network situation lead to the fact that the enhancement of certain item may also affect some other items, and different amount of investment may also result in different degree of impact, therefore, the problem was extracted into the multiple-choice quadratic knapsack problem. T