基于改进贪婪算法的测量节点选择优化方法

计算机与现代化 ›› 2021, Vol. 0 ›› Issue (04): 79-84.

基于改进贪婪算法的测量节点选择优化方法

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京100190;2.中国科学院大学，北京100049)

出版日期:2021-04-22 发布日期:2021-04-25
作者简介:吴上(1994—),男,河南郑州人,硕士研究生，研究方向：网络测量，图神经网络，E-mail: marsws@foxmail.com; 通信作者：盛益强（1978—），男，研究员，博士，研究方向：图论及优化算法，机器学习，E-mail: shengyq@dsp.ac.cn; 邓浩江（1971—），男，研究员，博士，研究方向：多媒体通信和模式识别，E-mail: denghj@dsp.ac.cn。
基金资助:
中国科学院战略性先导科技专项课题(XDC02070100)

Measurement Node Selecting Method Based on Improved Greedy Algorithm

(1. National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences,

Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

Online:2021-04-22 Published:2021-04-25

摘要/Abstract

摘要： 未来应用场景对名字解析系统有着确定性时延保障的需求，如何有效选择测量节点，为确定时延名字解析提供支撑是本文着力解决的问题。本文将网络测量节点部署问题映射成为最小点覆盖问题，并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法，从优化贪婪算法迭代周期和针对实际场景特点改进排序算法2个方面进行优化。实验结果表明，基于改进贪婪算法的求解方式比传统贪婪算法的求解方式，平均耗时减少了90%以上。

关键词: 名字解析系统, 信息中心网络, 贪婪算法, 最小点覆盖

Abstract: In the future application scenarios, there is a need of deterministic delay guarantee for the name resolution system. How to effectively select measurement nodes and provide support for exact delay name resolution is the problem this article focuses on. This paper maps the network measurement scheduling deployment problem to the minimum vertex cover problem and proposes an improved greedy algorithm which mainly optimizes the greedy algorithm iteration cycle and improves the sorting algorithm in certain scenarios. The experimental results show that the improved greedy algorithm is more than 900% faster than traditional greedy algorithm.

Key words: name resolution system, information centric networking, greedy algorithm, minimum vertex cover

吴上, 盛益强, 邓浩江, . 基于改进贪婪算法的测量节点选择优化方法[J]. 计算机与现代化, 2021, 0(04): 79-84.

WU Shang, SHENG Yi-qiang, DENG Hao-jiang, . Measurement Node Selecting Method Based on Improved Greedy Algorithm[J]. Computer and Modernization, 2021, 0(04): 79-84.

参考文献［27］

［1］	XYLOMENOS G, VERVERIDIS C N, SIRIS V A, et al. A survey of information-centric networking research［J］. IEEE Communications Surveys and Tutorials, 2014,16(2):1024-1049.
［2］	HAMPEL G, LI C, LI J Y. 5G ultra-reliable low-latency communications in factory automation leveraging licensed and unlicensed bands［J］. IEEE Communications Magazine, 2019,57(5):117-123.
［3］	Recommendation ITU-T Y.3072-2019, Requirements and Capabilities of Name Mapping and Resolution for Information Centric Networking in IMT-2020［S］.
［4］	LIAO Y, SHENG Y Q, WANG J L. A temporally hierarchical deployment architecture for an enhanced name resolution system［J］. Applied Sciences, 2019,9(14): Article No. 2891. DOI: 10.3390/app9142891.
［5］	任婧,李乐民,王晟. 针对内容中心网络中名字解析系统的DoS攻击建模与分析［J］. 计算机应用研究, 2016,33(2):495-497.
［6］	任婧. 内容中心网络架构及相关技术研究［D］. 成都:电子科技大学, 2015.
［7］	郝斌斌,吕斌,陈京荣. 基于最小点覆盖的共享单车投放点选取方法［J］. 交通信息与安全, 2018,36(5):147-152.
［8］	乌寅戎. 基于子图分解的多运动目标视频跟踪算法研究［D］. 广州:华南理工大学, 2017.
［9］	冯昊. 基于网络表示学习的动态网络异常检测技术研究［D］. 郑州:战略支援部队信息工程大学, 2019.
［10］	王力,穆东旭. 最小权点覆盖的扫描测试向量生成算法［J］. 计算机仿真, 2019,36(7):251-256.
［11］	FAYAZ M, ARSHAD S. Clever steady strategy algorithm: A simple and efficient approximation algorithm for minimum vertex cover problem［C］// Proceedings of the 2015 13th International Conference on Frontiers of Information Technology (FIT). 2015:277-282.
［12］	KARP R M. Reducibility among combinatorial problems［M］// Complexity of Computer Computations. Springer, 1972:85-103.
［13］	CHVATAL V. A greedy heuristic for the set-covering problem［J］. Mathematics of Operations Research, 1979,4(3):233-235.
［14］	CLARKSON K L. A modification of the greedy algorithm for vertex cover［J］. Information Processing Letters, 1983,16(1):23-25.
［15］	KHAN I, KHAN H. Modified vertex support algorithm: A new approach for approximation of minimum vertex cover［J］. Research Journal of Computer and Information Technology Sciences, 2013,1:7-11.
［16］	FAYAZ M, ARSHAD S, ZAMAN U, et al. A simple, fast and near optimal approximation algorithm for optimization of un-weighted minimum vertex cover［C］// Proceedings of the 2016 International Conference on Frontiers of Information Technology (FIT). 2016:176-180.
［17］	DORIGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem［J］. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.
［18］	郝航,金跃辉,杨谈. 基于并行化蚁群算法的网络测量节点选取算法［J］. 网络新媒体技术, 2018,7(1):7-15.
［19］	HOLLAND J H. Outline for a logical theory of adaptive systems［J］. Journal of the ACM, 1962,9(3):297-314.
［20］	GUO P, QUAN C S, CHEN H Z. MEAMVC: A membrane evolutionary algorithm for solving minimum vertex cover problem［J］. IEEE Access, 2019,7:60774-60784.
［21］	ZHANG L X, AFANASYEV A, BURKE J, et al. Named data networking［J］. ACM SIGCOMM Computer Communication Review, 2014,44(3):66-73.
［22］	JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content［J］. Communications of the ACM, 2012,55(1):117-124.
［23］	KOPONEN T, CHAWLA M, CHUN B-G, et al. A data-oriented (and beyond) network architecture［J］. ACM SIGCOMM Computer Communication Review, 2007,37(4):181-192.
［24］	LAGUTIN D, VISALA K, TARKOMA S. Publish/subscribe for Internet: PSIRP perspective［M］// Towards the Future Internet: Emerging Trends from European Research. IOS Press, 2010:75-84.
［25］	DONG L J, WANG G Q. A hybrid approach for name resolution and producer selection in information centric network［C］// Proceedings of the 2018 International Conference on Computing, Networking and Communications (ICNC). 2018:574-580.
［26］	DONG L J, WANG G Q. A robust and lightweight name resolution approach for IoT data in ICN［C］// Proceedings of the 2017 9th International Conference on Ubiquitous and Future Networks (ICUFN). 2017:61-65.
［27］	BARABASI A L, ALBERT R. Emergence of scaling in random networks［J］. Science, 1999,286(5439):509-512.

[1]	杨昊, 高全力, 李雪花, 赵辉, 金帅, 徐国梁. 基于缓存价值的命名数据网络缓存优化策略[J]. 计算机与现代化, 2022, 0(10): 95-99.
[2]	罗兰花, 袁淑丹, 何巧萍. 一种基于节点中心性近似算法的ICN协作缓存策略[J]. 计算机与现代化, 2021, 0(04): 85-90.
[3]	陈婷，余小平，陈俊凤，邓鹏，龚代平，邓小红. 基于平面不封闭图形切割的路径规划[J]. 计算机与现代化, 2019, 0(08): 39-.
[4]	陈觉之;张贵荣;周宇欢. 一种基于贪婪策略的说话人语音特征优选方法[J]. 计算机与现代化, 2013, 1(5): 201-205.