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

doi:10.11959/j.issn.1000-436x.2016272

Abstract

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. The characteristics of quadratic knapsack problem was used to model the interactions among the situation indi-cator items, meanwhile used the multiple choice knapsack problem to model the multiple investment choice for each item. A branch and bound algorithm was conducted by using the semi-definite relaxation. The experiment results show the ac-curacy and efficiency of proposed algorithm.

Key words: resource allocation, situation awareness, multiple-choice quadratic knapsack, semi-definite relaxation

Yan-wei SUN,Yun-chuan GUO,Ling-cui ZHANG,Bin-xing FANG. Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack[J]. Journal on Communications, 2016, 37(12): 56-66.

Figures/Tables 11

References 39

[1]	ENDSLEY M R . Toward a theory of situation awareness in dynamic systems[J]. Human Factors: The Journal of the Human Factors and Ergonomics Society, 1995,37(1):32-64.
[2]	DIETTERICH T G , BAO X , KEISER V , et al. Machine learning methods for high level cyber situation awareness[M]// Cyber Situ-ational Awareness. Springer US, 2010:227-247.
[3]	LIU P , JIA X , ZHANG S , et al. Cross-layer damage assessment for cyber situational awareness[J]. Advances in Information Security, 2010,46:155-176.
[4]	PREDEN J , MOTUS L , MERISTE M , et al. Situation awareness for networked systems[C]// 2011 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Deci-sion Support (CogSIMA). IEEE. 2011:123-130.
[5]	BRANNON N G , SEIFFERTT J E , DRAELOS T J , et al. Coordinated machine learning and decision support for situation awareness[J]. Neural Networks, 2009,22(3):316-325.
[6]	TAMASSIA R , PALAZZI B , PAPAMANTHOU C . Graph drawing for security visualization[C]// International Symposium on Graph Drawing. Springer Berlin Heidelberg, 2008:2-13.
[7]	TADDA G P , SALERNO J S . Overview of cyber situation aware-ness[M]. Cyber Situational Awareness. Springer US, 2010:15-35.
[8]	WEBB J , AHMAD A , MAYNARD S B , et al. A situation awareness model for information security risk management[J]. Computers ＆ Se-curity, 2014,44:1-15.
[9]	Federal Office for Information Security: 13 EL: Cross-reference tables of the IT-grundschutz catalogues: 13th version (2013)[EB/OL]. .
[10]	GREITZER F L , FRINCKE D A . Combining traditional cyber security audit data with psychosocial data: towards predictive modeling for in-sider threat mitigation[M]// Insider Threats in Cyber Security. Springer US, 2010:85-113.
[11]	SCHILLING A , WERNERS B . Optimizing information systems secu-rity design based on existing security knowledge[C]// International Conference on Advanced Information Systems Engineering. Springer International Publishing, 2015:447-458.
[12]	DU J , COOK W D , LIANG L , et al. Fixed cost and resource allocation based on DEA cross-efficiency[J]. European Journal of Operational Research, 2014,235(1):206-214.
[13]	AISOPOS F , TSERPES K , VARVARIGOU T . Resource management in software as a service using the knapsack problem model[J]. Interna-tional Journal of Production Economics, 2013,141(2):465-477.
[14]	XIAO Z , SONG W , CHEN Q . Dynamic resource allocation using virtual machines for cloud computing environment[J]. IEEE Transac-tions on Parallel and Distributed Systems, 2013,24(6):1107-1117.
[15]	HAJIAGHAJANI F , RASTI M . Downlink resource reuse for de-vice-to-device communication underlying cellular networks using a generalized knapsack framework[C]// 2016 13th IEEE Annual Con-sumer Communications ＆ Networking Conference (CCNC). IEEE, 2016:171-176.
[16]	FERDOSIAN N , OTHMAN M , ALI B M , et al. Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks[J]. Wireless Networks, 2015:1-14.
[17]	SHEU J P , KAO C C , YANG S R , et al. A resource allocation scheme for scalable video multicast in WiMAX relay networks[J]. IEEE Transactions on Mobile Computing, 2013,12(1):90-104.
[18]	FIELDER A , PANAOUSIS E , MALACARIA P , et al. Decision sup-port approaches for cyber security investment[J]. Decision Support Systems, 2016,86:13-23.
[19]	KHOUZANI M H R , MALACARIA P , HANKIN C , et al. Efficient numerical frameworks for multi-objective cyber security plan-ning[C]// European Symposium on Research in Computer Security. Springer International Publishing, 2016:179-197.
[20]	OJAMAA A , TYUGU E , KIVIMAA J . Pareto-optimal situation analy-sis for selection of security measures[C]// MILCOM 2008-2008 IEEE Military Communications Conference. IEEE, 2008:1-7.
[21]	WANG F , XU C , SONG L , et al. Energy-efficient resource allocation for device-to-device underlay communication[J]. IEEE Transactions on Wireless Communications14.4. 2015:2082-2092.
[22]	HASAN M , HOSSAIN E . Distributed resource allocation in D2D-enabled multi-tier cellular networks: an auction approach[C]// 2015 IEEE International Conference on Communications (ICC). IEEE, 2015.
[23]	ZHANG H , JIANG H , LI B , et al. A framework for truthful online auctions in cloud computing with heterogeneous user demands[J]. IEEE Transactions on Computers, 2016,65(3):805-818.
[24]	GUPTA M , REES J , CHATURVEDI A , et al. Matching information security vulnerabilities to organizational security profiles: a genetic algorithm approach[J]. Decision Support Systems, 2006,41(3):592-603.
[25]	VIDUTO V , MAPLE C , HUANG W , et al. A novel risk assessment and optimization model for a multi-objective network security coun-termeasure selection problem[J]. Decision Support Systems, 2012,53(3):599-610.
[26]	REES L P , DEANE J K , RAKES T R , et al. Decision support for cyber security risk planning[J]. Decision Support Systems, 2011,51(3):493-505.
[27]	SAWIK T . Selection of optimal countermeasure portfolio in IT secu-rity planning[J]. Decision Support Systems, 2013,55(1):156-164.
[28]	MUKHOPADHYAY A , CHATTERJEE S , SAHA D , et al. Cyber-risk decision models: to insure IT or not?[J]. Decision Support Systems, 2013,56:11-26.
[29]	GORDON L A , LOEB M P . The economics of information security investment[M]// Economics of Information Security. Springer US, 2004:105-125.
[30]	LéTOCART L , PLATEAU M C , PLATEAU G . An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack prob-lem[J]. Pesquisa Operacional, 2014,34(1):49-72.
[31]	SHENG H , SUN J , SUN X . A Rigorous method for solving 0-1 poly-nomial knapsack problem[J]. Journal of Shanghai University (Natural Science Edition), 2006,4:012.
[32]	BRETTHAUER K M , SHETTY B . Quadratic resource allocation with generalized upper bounds[J]. Operations Research Letters, 1997,20(2):51-57.
[33]	HAHN P , GRANT T . Lower bounds for the quadratic assignment problem based upon a dual formulation[J]. Operations Research, 1998,46(6):912-922.
[34]	HAHN P M , KIM B J , GUIGNARD M , et al. An algorithm for the generalized quadratic assignment problem[J]. Computational Optimi-zation and Applications, 2008,40(3):351-372.
[35]	BILLIONNET A , ELLOUMI S , PLATEAU M C . Improving the per-formance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method[J]. Discrete Applied Mathe-matics, 2009,157(6):1185-1197.
[36]	CAPRARA A , PISINGER D , TOTH P . Exact solution of the quadratic knapsack problem[J]. Informs Journal on Computing, 1999,11(2):125-137.
[37]	ANDERSON R H , FELDMAN P M , GERWEHR S , et al. Securing the US defense information infrastructure: a proposed approach[R]. Rand Corp Santa Monica CA, 1999.
[38]	KELLERER H , PFERSCHY U , PISINGER D . Introduction to NP-completeness of knapsack problems[M]. Springer Berlin Heidel-berg, 2004.
[39]	BRETTHAUER K M , SHETTY B . The nonlinear knapsack prob-lem–algorithms and applications[J]. European Journal of Operational Research, 2002,138(3):459-472.

Metrics

Recommended 0

No Suggested Reading articles found!

防护措施	针对威胁个数	负面影响个数
增加网络异构化	5	2
对网络冗余备份	6	1
加入诱导性欺骗	8	3
分散隔离管理网络	10	3
加入应急响应模块	11	1
集中管理信息资源	3	4

n	半定规划松弛度	CPLEX松弛度
10	12.5%	75.1%
15	28.3%	86.9%
20	22.5%	75.4%
25	16.7%	68.8%
30	13.4%	89.8%
35	36.8%	72.5%
40	19.3%	90.2%
45	28.6%	88.5%

Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 39

Related Articles 15

Metrics

Recommended 0

[1]	Li WANG, Aiguo FEI, Ping ZHANG, Lianming XU. Research on new frameworks and key technologies for intelligent emergency command communication networks [J]. Journal on Communications, 2023, 44(6): 1-11.
[2]	Zaijian WANG, Huimin GU. Network slicing resource allocation strategy based on joint optimization [J]. Journal on Communications, 2023, 44(5): 234-245.
[3]	Xueyong YU, Lixiang QIU, Jianing SONG, Hongbo ZHU. Security communication and energy efficiency optimization strategy in UAV-aided edge computing [J]. Journal on Communications, 2023, 44(3): 45-54.
[4]	Guojun LI, Xu HOU, Changrong YE, Yiping LUO. Wide area cooperative resource allocation algorithm for shortwave communication access network [J]. Journal on Communications, 2023, 44(2): 112-121.
[5]	Long LONG, Zichen LIU, Zaiwang LU, Yucheng ZHANG, Lei LI. Joint optimization strategy of service cache and resource allocation in mobile edge network [J]. Journal on Communications, 2023, 44(1): 64-74.
[6]	Xiaorong ZHU, Kang CHEN. Research on elastic handover algorithm of 6G network based on fine-grained slicing [J]. Journal on Communications, 2022, 43(9): 148-156.
[7]	Shaoshuai FAN, Jianbo WU, Hui TIAN. Federated learning resource management for energy-constrained industrial IoT devices [J]. Journal on Communications, 2022, 43(8): 65-77.
[8]	Li WANG, Qing WEI, Lianming XU, Yuan SHEN, Ping ZHANG, Aiguo FEI. Research on low-energy-consumption deployment of emergency UAV network for integrated communication-navigating-sensing [J]. Journal on Communications, 2022, 43(7): 1-20.
[9]	Peng QIN, Haoting HE, Xiongwen ZHAO, Yang FU, Yu ZHANG, Miao WANG, Shuo WANG, Xue WU. Efficient resource allocation with context-awareness for parked car road side unit-based Internet of vehicles [J]. Journal on Communications, 2022, 43(7): 113-125.
[10]	Damin ZHANG, Yi WANG, Chengcheng ZOU, Peiwen ZHAO, Linna ZHANG. Resource allocation strategies for improved mayfly algorithm in cognitive heterogeneous cellular network [J]. Journal on Communications, 2022, 43(6): 156-167.
[11]	Weijing QI, Qingyang SONG, Lei GUO. Dual time scale resource allocation for RAN slicing in software-defined oriented polymorphic IoV [J]. Journal on Communications, 2022, 43(4): 60-70.
[12]	Zhengyu ZHU, Gengwang HOU, Chongwen HUANG, Gangcan SUN, Wanming HAO, Jing LIANG. Systems resource allocation algorithm for RIS-assisted D2D secure communication based on parallel CNN [J]. Journal on Communications, 2022, 43(3): 172-179.
[13]	Wei SUN, Qingyang SONG, Lei GUO. Resource allocation algorithm for intelligent reflecting surface-aided SWIPT networks [J]. Journal on Communications, 2022, 43(2): 34-43.
[14]	Yan SUN, Ao XIONG, Chengling JIANG, Wei WANG, Dongxiao YU, Shaoyong GUO. Blockchain-based computing and wireless communication resource joint management double auction model [J]. Journal on Communications, 2022, 43(11): 14-25.
[15]	Geng CHEN, Shuhu QI, Fei SHEN, Qingtian ZENG. Dual time scale network slicing algorithm based on D3QN for B5G multi-service scenarios [J]. Journal on Communications, 2022, 43(11): 213-224.