Measurement Node Selecting Method Based on Improved Greedy Algorithm

Abstract

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

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.

References ［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]	LUO Lan-hua, YUAN Shu-dan, HE Qiao-ping. An ICN Cooperative Cache Strategy Based on Node Centrality Approximation Algorithm [J]. Computer and Modernization, 2021, 0(04): 85-90.
[2]	WAN Ke. A Carousel Greedy Algorithm for Positive Influence Dominating Set Problem in Social Network [J]. Computer and Modernization, 2020, 0(09): 49-53.
[3]	CHEN Ting， YU Xiao-ping， CHEN Jun-feng， DENG Peng， GONG Dai-ping, DENG Xiao-hong. Path Planning Based on Plane Unclosed Graphic Cutting [J]. Computer and Modernization, 2019, 0(08): 39-.
[4]	REN Jing-min， PAN Da-zhi. Solving 0-1 Knapsack Problem Based on Weighted Greedy Firefly Algorithm [J]. Computer and Modernization, 2019, 0(05): 86-.
[5]	WANG Gang, WANG Zhi-cheng. Transmission Channel Selection Method Based on Medium & Long-term #br# Transaction Electricity Quantity Checking [J]. Computer and Modernization, 2019, 0(04): 38-.
[6]	CAO Xue-xue. Intelligent Dormitory Allocation Method Based on Greedy Algorithm [J]. Computer and Modernization, 2018, 0(01): 23-26.
[7]	CHEN Jue-zhi;ZHANG Gui-rong;ZHOU Yu-huan. A Method of Speaker Acoustic Features Optimal Selection Based on Greedy Strategy [J]. Computer and Modernization, 2013, 1(5): 201-205.