Cluster-based route convergence method based on network state graph model

PAN Chengsheng; LU Huangjie; SHI Huaifeng; WANG Yingzhi

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

您当前的位置：

首页 >

文章列表页 >

Cluster-based route convergence method based on network state graph model

Papers | 更新时间：2025-01-14

- Cluster-based route convergence method based on network state graph model
- Journal on Communications Vol. 45, Issue 12, Pages: 95-110(2024)
- 作者机构：
  
  1.南京信息工程大学复杂环境智能保障技术教育部重点实验室，江苏南京 210044
  2.国防科技大学第六十三研究所，江苏南京 210007
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61931004;B2202401)
- DOI：10.11959/j.issn.1000-436x.2024267
  CLC： TN92
- Received：10 July 2024，
  
  Revised：2024-12-05，
  
  Published：25 December 2024
- 稿件说明：
移动端阅览
潘成胜,陆煌杰,石怀峰等.基于网络状态图模型的分簇式路由收敛方法[J].通信学报,2024,45(12):95-110.

PAN Chengsheng,LU Huangjie,SHI Huaifeng,et al.Cluster-based route convergence method based on network state graph model[J].Journal on Communications,2024,45(12):95-110.
潘成胜,陆煌杰,石怀峰等.基于网络状态图模型的分簇式路由收敛方法[J].通信学报,2024,45(12):95-110. DOI： 10.11959/j.issn.1000-436x.2024267.

PAN Chengsheng,LU Huangjie,SHI Huaifeng,et al.Cluster-based route convergence method based on network state graph model[J].Journal on Communications,2024,45(12):95-110. DOI： 10.11959/j.issn.1000-436x.2024267.

摘要

针对强对抗高机动作战条件下战术通信网络中的节点连接关系时变、链路故障频发，导致路由收敛频繁、业务有效传输时间短的问题，提出了一种基于网络状态图模型的分簇式路由收敛方法（OSPF-CSG）。首先，依据Hello报文统计特征获取链路状态，基于链路状态聚合特征刻画节点状态，构建网络状态图模型。其次，改进邻居状态机状态转移触发条件，构建2种新型OSPF报文，并据此设计完全邻接关系主动/被动关联机制。最后，在此基础上，设计簇头自举算法、节点入簇算法和簇间连接算法实现基于簇的路由收敛。仿真结果表明，在8种不同规模的网络拓扑中，针对不同链路损毁程度，OSPF-CSG相较于传统OSPF协议的路由收敛算法，其路由收敛总次数平均减少82%，路由开销平均降低70%，分组投递率平均提升60%。

Abstract

To address the challenges of time-varying node connectivity and frequent link failures in tactical communication networks under conditions of strong adversarial and high-mobility operations

which result in frequent route convergence and short effective transmission times

a cluster-based route convergence method based on network state graph model (OSPF-CSG) was proposed. Firstly

link states were obtained based on the statistical characteristics of Hello messages

and node states were characterized using aggregated link state features to construct the network state graph model. Secondly

the neighbor state machine’s state transition triggers were improved

and two new OSPF message types were developed to design an active/passive association mechanism for complete adjacency relationships. Finally

on this basis

a cluster head bootstrap algorithm

node clustering algorithm

and inter-cluster connection algorithm were proposed to achieve cluster-based routing convergence. Simulation results show that

in eight different network topologies and under different link damage conditions

OSPF-CSG achieves an average reduction of 82% in the total number of route convergences

a reduction in routing overhead by 70% on average

and an improvement in packet delivery rate by 60% on average compared to the traditional OSPF protocol’s route convergence algorithm.

关键词

Keywords

references

孙盛智 , 刘玉 , 盛碧琦 , 等 . “马赛克”战运行机制及制胜机理研究 [J ] . 指挥控制与仿真 , 2023 , 45 ( 2 ): 150 - 154 .

SUN S Z , LIU Y , SHENG B Q , et al . Research on the operation mechanism and winning mechanism of mosaic warfare [J ] . Command Control & Simulation , 2023 , 45 ( 2 ): 150 - 154 .

胡志强 , 刘永普 , 姜松 , 等 . 分布式智能化作战的概念、内涵与未来发展 [J ] . 指挥信息系统与技术 , 2023 , 14 ( 5 ): 62 - 68 .

HU Z Q , LIU Y P , JIANG S , et al . Concept, connotation and future development of distributed intelligent operations [J ] . Command Information System and Technology , 2023 , 14 ( 5 ): 62 - 68 .

张志华 , 王凡 . 第五代指挥信息系统总体及其智能化技术设想 [J ] . 指挥控制与仿真 , 2021 , 43 ( 5 ): 1 - 7 .

ZHANG Z H , WANG F . The fifth generation command information system and its intelligent technology [J ] . Command Control & Simulation , 2021 , 43 ( 5 ): 1 - 7 .

COLTUN R , FERGUSON D , MOY J , et al . RFC 5340: OSPF for ipv6 [R ] . 2008 .

MOY J , SAFARI A O M C . OSPF: anatomy of an Internet routing protocol [M ] . Array Addison-Wesley Professional , 1998 .

MOY J . RFC 2328: OSPF version 2 [R ] . 1998 .

潘成胜 , 曹康宁 , 石怀峰 , 等 . 基于深度强化学习的战术通信网络路径优选算法 [J ] . 中国电子科学研究院学报 , 2024 , 19 ( 2 ): 138 - 148 .

PAN C S , CAO K N , SHI H F , et al . Tactical communication network path selection algorithm based on deep reinforcement learning [J ] . Journal of China Academy of Electronics and Information Technology , 2024 , 19 ( 2 ): 138 - 148 .

KATZ D , WARD D . Bidirectional forwarding detection (BFD) [R ] . 2010 .

TALAULIKAR K , PSENAK P , FU A , et al . OSPF bidirectional forwarding detection (BFD) strict-mode [J ] . RFC , 2023 , 9355 : 1 - 10 .

KHAN N , BIN SALLEH R , KOUBAA A , et al . Data plane failure and its recovery techniques in SDN: a systematic literature review [J ] . Journal of King Saud University-Computer and Information Sciences , 2023 , 35 ( 3 ): 176 - 201 .

俞成康 . 面向LEO网络的OSPF路由协议增强技术研究 [D ] . 北京 : 北京邮电大学 , 2023 .

YU C K . Research on OSPF routing protocol enhancement technology for LEO networks [D ] . Beijing : Beijing University of Posts and Telecommunications , 2023 .

邢川 , 陈二虎 , 韩笑冬 . 基于动静结合方法的卫星网络路由方法研究 [J ] . 空间控制技术与应用 , 2020 , 46 ( 3 ): 55 - 59 .

XING C , CHEN E H , HAN X D . Static-dynamic routing algorithm in satellite constellation network [J ] . Aerospace Control and Application , 2020 , 46 ( 3 ): 55 - 59 .

徐明伟 , 夏安青 , 杨芫 , 等 . 天地一体化网络域内路由协议OSPF+ [J ] . 清华大学学报(自然科学版) , 2017 , 57 ( 1 ): 12 - 17 .

XU M W , XIA A Q , YANG Y , et al . Intra-domain routing protocol OSPF+for integrated terrestrial and space networks [J ] . Journal of Tsinghua University (Science and Technology) , 2017 , 57 ( 1 ): 12 - 17 .

WAQAS M , MALIK S U R , AKBAR S , et al . Convergence time analysis of OSPF routing protocol using social network metrics [J ] . Future Generation Computer Systems , 2019 , 94 : 62 - 71 .

MACCARI L , GHIRO L , GUERRIERI A , et al . Exact distributed load centrality computation: algorithms, convergence, and applications to distance vector routing [J ] . IEEE Transactions on Parallel and Distributed Systems , 2020 , 31 ( 7 ): 1693 - 1706 .

MACCARI L , CIGNO R L . Improving routing convergence with centrality: theory and implementation of pop-routing [J ] . IEEE/ACM Transactions on Networking , 2018 , 26 ( 5 ): 2216 - 2229 .

JAIN N , PAYAL A , JAIN A . Effect of data packet size on the performance of RIP and OSPF routing protocols in hybrid networks [J ] . International Journal of Pervasive Computing and Communications , 2021 , 17 ( 4 ): 361 - 376 .

LIU G , DENG Y , CHEONG K H . Network immunization strategy by eliminating fringe nodes: a percolation perspective [J ] . IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2023 , 53 ( 3 ): 1862 - 1871 .

RAMANATHAN R , REDI J . A brief overview of ad hoc networks: challenges and directions [J ] . IEEE Communications Magazine , 2002 , 40 ( 5 ): 20 - 22 .

MACKTOOBIAN M , SHU Z , ZHAO Q . Topology recoverability prediction for ad-hoc robot networks: a data-driven fault-tolerant approach [J ] . IEEE Transactions on Signal and Information Processing Over Networks , 2023 , 9 : 786 - 799 .

GOYAL M , SOPERI M , BACCELLI E , et al . Improving convergence speed and scalability in OSPF: a survey [J ] . IEEE Communications Surveys & Tutorials , 2012 , 14 ( 2 ): 443 - 463 .

MICHEL O , BIFULCO R , RÉTVÁRI G , et al . The programmable data plane: abstractions, architectures, algorithms, and applications [J ] . ACM Computing Surveys , 2021 , 54 ( 4 ): 1 - 36 .

PARIZOTTO R , COELHO B L , NUNES D C , et al . Offloading machine learning to programmable data planes: a systematic survey [J ] . ACM Computing Surveys , 2024 , 56 ( 1 ): 1 - 34 .

RYBOWSKI N , BONAVENTURE O . Evaluating OSPF convergence with ns-3 DCE [C ] // Proceedings of the 2022 Workshop on ns-3 . New York : ACM Press , 2022 : 120 - 126 .

JORIO A , FKIHI S E , ELBHIRI B , et al . An energy-efficient clustering routing algorithm based on geographic position and residual energy for wireless sensor network [J ] . Journal of Computer Networks and Communications , 2015 , 2015 : 170138 .

RIZKY R , HAKIM Z , SETIYOWATI S , et al . Development of the multi-channel clustering hierarchy method for increasing performance in wireless sensor network [J ] . MATRIK: Jurnal Manajemen, Teknik Informatika Dan Rekayasa Komputer , 2024 , 23 ( 3 ): 603 - 614 .

PATHAK S , JAIN S , BORAH S . Clustering algorithms for MANETs: a review on design and development [C ] // Advances in Intelligent Systems and Computing . Berlin : Springer , 2020 : 563 - 578 .

VENKATASUBRAMANIAN S , SUHASINI D A , VENNILA D C . An energy efficient clustering algorithm in mobile adhoc network using ticket ID based clustering manager [J ] . International Journal of Computer Science & Network Security , 2021 .

HAMZA F , VIGILA S M C . Cluster head selection algorithm for MANETs using hybrid particle swarm optimization-genetic algorithm [J ] . International Journal of Computer Networks and Applications , 2021 , 8 ( 2 ): 119 - 129 .

AHMAD M , HAMEED A , ULLAH F , et al . A bio-inspired clustering in mobile adhoc networks for Internet of things based on honey bee and genetic algorithm [J ] . Journal of Ambient Intelligence and Humanized Computing , 2020 , 11 ( 11 ): 4347 - 4361 .

KALIAPPAN M , MARIAPPAN E , PRAKASH M V , et al . Load balanced clustering technique in MANET using genetic algorithms [J ] . Defence Science Journal , 2016 , 66 ( 3 ): 251 .

HUSNAIN G , ANWAR S . An intelligent cluster optimization algorithm based on whale optimization algorithm for VANETs (WOACNET) [J ] . PLoS One , 2021 , 16 ( 4 ): e0250271 .

ASAAMONING G , MENDES P , MAGAIA N . A dynamic clustering mechanism with load-balancing for flying ad hoc networks [J ] . IEEE Access , 2021 , 9 : 158574 - 158586 .

KHEDR A M , SALIM A , RAJ P V P , et al . MWCRSF: mobility-based weighted cluster routing scheme for FANETs [J ] . Vehicular Communications , 2023 , 41 : 100603 .

HOSSEINZADEH M , TANVEER J , RAHMANI A M , et al . A Q-learning-based smart clustering routing method in flying ad hoc networks [J ] . Journal of King Saud University-Computer and Information Sciences , 2024 , 36 ( 1 ): 101894 .

KHEDR A M , PRAVIJA R P V . A hybrid MGO-JAYA based clustered routing for FANETs [J ] . Vehicular Communications , 2024 , 45 : 100729 .

SU Y S , XU Y N , PANG Z F , et al . HCAR: a hybrid-coding-aware routing protocol for underwater acoustic sensor networks [J ] . IEEE Internet of Things Journal , 2023 , 10 ( 12 ): 10790 - 10801 .

尹婷 . 面向5G端到端的协同定位技术研究 [D ] . 西安 : 中国科学院大学(中国科学院国家授时中心) , 2022 .

YIN T . Research on cooperative localization technologies for 5G device to device [D ] . Xi’an : University of Chinese Academy of Sciences (National Timing Center, Chinese Academy of Sciences) , 2022 .

齐晓鑫 . 低轨卫星网络路由算法与拓扑控制策略研究 [D ] . 西安 : 西安电子科技大学 , 2022 .

QI X X . Research on routing algorithm and topology control strategy of LEO satellite network [D ] . Xi’an : Xidian University , 2022 .

AMOUR B S , JAEKEL A . Data rate selection strategies for periodic transmission of safety messages in VANET [J ] . Electronics , 2023 , 12 ( 18 ): 3790 .

于全 . 战术通信理论与技术 [M ] . 北京 : 人民邮电出版社 , 2020 .

YU Q . Tactical communications theory and technology [M ] . Beijing : Posts and Telecommunications Press , 2020 .

Views

962

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Scalable overlay multicast algorithm with high stability

Related Author

Ye SHEN

Jing FENG

Zhan-feng WANG

Related Institution

Institute of Meteorology and Oceanography,PLA University of Science and Technology

The 95871 Troop of PLA

The 93615 Troop of PLA

AI问答

⁰