基于代数连通度优化的空间信息网络分布式拓扑控制方法

doi:10.3969/j.issn.0372-2112.2020.06.017

电子学报 ›› 2020, Vol. 48 ›› Issue (6): 1162-1168.DOI: 10.3969/j.issn.0372-2112.2020.06.017

基于代数连通度优化的空间信息网络分布式拓扑控制方法

张泰江¹, 李勇军¹, 赵尚弘¹, 郑永兴², 辛宁³

1. 空军工程大学信息与导航学院, 陕西西安 710077;
2. 西安科诺网络与信息安全技术研究所, 陕西西安 710068:;
3. 中国空间技术研究院通信卫星事业部, 北京 100094

收稿日期:2019-05-20 修回日期:2019-09-17 出版日期:2020-06-25
- 通讯作者:
- 李勇军
- 作者简介:
- 张泰江 男,1994年生于江西萍乡.现为空军工程大学信息与导航学院硕士研究生.主要研究方向为卫星光通信与网络,空间信息网络拓扑控制. E-mail:taijiangzhang@163.com
  赵尚弘 男,1964年生于甘肃兰州.现为空军工程大学信息与导航学院教授、博士生导师.主要研究方向为激光原理技术,卫星光通信与网络,空间微波光子技术. E-mail:zhaoshangh@aliyun.com
  郑永兴 男,1982年生于江西永新.现为西安科诺网络与信息安全技术研究所研究员.主要研究方向为卫星光通信与网络,分布式星群拓扑控制,网络资源优化. E-mail:zhengyx_afeu@hotmail.com
  辛宁 男,1982年生于山东烟台,现为中国空间技术研究院通信卫星事业部高级工程师,主要方向为天基信息网络架构设计. E-mail:xinning7@sina.cm
- 基金资助:
- 国家自然科学基金重大研究计划培育项目 (No.91638101）; 国家自然科学基金青年科学基金项目 (No.61701522）; 陕西省自然科学基金项目 (No.2018JM6069）

Distributed Topology Control Method Based on the Algebraic Connectivity Optimization in Space Information Networks

ZHANG Tai-jiang¹, LI Yong-jun¹, ZHAO Shang-hong¹, ZHENG Yong-xing², XIN Ning³

1. Institute of Information and Navigation, Air Force Engineering University, Xi'an, Shaanxi 710077, China;
2. Xi'an Kono Network and Information Security Technology Research Institute, Xi'an, Shaanxi 710068, China;
3. Institute of Telecommunication Satellite, China Academy of Space Technology, Beijing 100094, China

Received:2019-05-20 Revised:2019-09-17 Online:2020-06-25 Published:2020-06-25

摘要/Abstract

摘要： 针对空间信息网络中节点高速运动导致的网络拓扑结构难以长期稳定的问题，本文提出了基于代数连通度优化的网络动态拓扑控制方法，通过少量链路调整来维持网络拓扑的稳定性.为减小空间信息网络节点持续相对运动对网络拓扑结构稳定性造成的不利影响，针对网络初始化和网络重构场景，采用图论中的拉普拉斯矩阵特征值优化思想，构建了星上资源约束条件下的加权代数连通度最大化模型.为降低计算复杂度来实现网络拓扑的捷变控制，提出了基于连通矩阵弱摄动的动态网络拓扑控制策略.研究结果表明，提出的算法能够通过内点法，可高效地得到次优解，且次优解与全局最优解十分接近.

关键词: 空间信息网络, 图论, 分布式算法, 代数连通度, 凸优化, 拓扑控制

Abstract: Aiming at the problem of long-term stability of the network topology caused by high-speed movement of nodes in a space information network,a dynamic topology control method based on the algebraic connectivity optimization is proposed to reduce the number of links so as to maintain the stability of the network topology.In order to reduce the adverse effect of the continuous relative motion of the space information network nodes on the stability of the network topology,according to the network initialization and network reconstruction scenarios,the Laplacian eigenvalue optimization in graph theory is used to construct the algebraic connectivity optimization model with resource constraints.To reduce the computational complexity and achieve agile control of network topology,a dynamic network topology control strategy based on weak perturbation of connectivity matrix is proposed.The results show that the proposed algorithm can obtain suboptimal solutions very efficiently through the interior point method,and the suboptimal solution is very close to the global optimal solution.

Key words: space information networks, graph theory, distributed algorithm, algebraic connectivity, convex optimization, topology control

中图分类号:

TN927

张泰江, 李勇军, 赵尚弘, 郑永兴, 辛宁. 基于代数连通度优化的空间信息网络分布式拓扑控制方法[J]. 电子学报, 2020, 48(6): 1162-1168.

ZHANG Tai-jiang, LI Yong-jun, ZHAO Shang-hong, ZHENG Yong-xing, XIN Ning. Distributed Topology Control Method Based on the Algebraic Connectivity Optimization in Space Information Networks[J]. Acta Electronica Sinica, 2020, 48(6): 1162-1168.

参考文献

[1] M Fiedler.Algebraic connectivity of graphs[J].Journal of Czechoslovak Mathematics,1973,23(2):298-305.
[2] Abreu N.Old and new results on algebraic connectivity of graphs[J].Linear Algebra and Its Applications,2007,423(1):53-73.
[3] Moskaoyama D.Maximum algebraic connectivity augmentation is NP-hard[J].Operations Research Letters,2008,36(6):677-679.
[4] Cuomo F,Cianfrani A,Polverini M,et al.Network pruning for energy saving in the Internet[J].Computer Networks,2012,56(10):2355-2367.
[5] Wei P,Chen L,Sun D.Algebraic connectivity maximization of an air transportation network:The flight routes' addition/deletion problem[J].IEEE Transactions on Intelligent Transportation Systems,2014,15(2):685-698.
[6] Abbagnale A,Cuomo F.Leveraging the algebraic connectivity of a cognitive network for routing design[J].IEEE Transactions on Mobile Computing,2012,11(99):1-1.
[7] Simonetto A,Keviczky,Tamás.Constrained distributed algebraic connectivity maximization in robotic networks[J].Automatica,2013,49(5):1348-1357.
[8] Fax J A,Murray R M.Information flow and cooperative control of vehicle formations[J].IFAC Proceedings Volumes,2002,35(1):115-120.
[9] Alexander Bertrand,Marc Moonen.Seeing the bigger picture:How nodes can learn their place within a complex ad hoc network topology[J].IEEE Signal Processing Magazine,2013,30(3):71-82.
[10] Kim Y,Mesbahi M.On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian[J].IEEE Transactions on Automatic Control,2006,51(1):116-120.
[11] Kim Y.Bisection algorithm of increasing algebraic connectivity by adding an edge[J].Automatic Control IEEE Transactions on,2009,55(1):170-174.
[12] Xiao L,Boyd S.Fast linear iterations for distributed averaging[J].Systems & Control Letters,2004,53(1):65-78.
[13] Ghosh A,Boyd S.Upper bounds on algebraic connectivity via convex optimization[J].Linear Algebra and Its Applications,2006,418(2-3):693-707.
[14] Sun J,Boyd S,Diaconis X P.The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem[J].SIAM Review,2006,48(4):681-699.
[15] Ogiwara K,Fukami T,Takahashi N.Maximizing algebraic connectivity in the space of graphs with fixed number of vertices and edges[J].IEEE Transactions on Control of Network Systems,2017,4(2):359-368.
[16] Sydney A,et al.Optimizing algebraic connectivity by edge rewiring[J].Applied Mathematics and Computation,2013,219(10):5465-5479.
[17] Bunch J R.Rank-one modification of the symmetric eigenproblem[J].Numerische Mathematic,1978,31(1):31-48.

基于代数连通度优化的空间信息网络分布式拓扑控制方法

Distributed Topology Control Method Based on the Algebraic Connectivity Optimization in Space Information Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陇盛, 陶蔚, 张泽东, 陶卿. 非光滑强凸情形Adam型算法的最优收敛速率[J]. 电子学报, 2022, 50(9): 2049-2059.
[2]	窦子铮, 姚铮, 陆明泉. 无线电区域定位系统的分布式空间基准自主建立技术[J]. 电子学报, 2022, 50(4): 841-848.
[3]	史宏强, 李岳衡, 黄平, 谭跃跃, 刘陕陕, 居美艳. 基于APD与PIN接收机的UWOC系统误码率性能优化研究[J]. 电子学报, 2022, 50(2): 446-454.
[4]	赵雄文, 张钰, 秦鹏, 王晓晴, 耿绥燕, 宋俊元, 刘瑶, 李思峰. 空天地一体化无线光通信网络关键技术及其发展趋势[J]. 电子学报, 2022, 50(1): 1-17.
[5]	王蔚龙, 李勇军, 赵尚弘, 辛宁, 赵海燕, 张泰江. 基于两阶段帕累托优化的卫星下行链路功率分配方法[J]. 电子学报, 2021, 49(6): 1101-1107.
[6]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[7]	王蔚龙, 赵尚弘, 李勇军. 基于能量效率的分布式星群下行链路功率分配方法研究[J]. 电子学报, 2020, 48(6): 1177-1181.
[8]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[9]	李玮, 邓维波, 杨强, Marco Donald Migliore. 基于随机扰动技术的共形阵列失效单元非凸压缩感知近场诊断方法[J]. 电子学报, 2019, 47(12): 2449-2456.
[10]	谷允捷, 胡宇翔, 丁悦航, 谢记超. 基于流量演化感知的服务功能链在线弹性编排策略[J]. 电子学报, 2019, 47(10): 2192-2201.
[11]	蒋婵, 李陶深, 梁俊斌. 低占空比传感网中分布式的环状流水线工作调度研究[J]. 电子学报, 2018, 46(7): 1732-1736.
[12]	王星宇, 李勇军, 赵尚弘, 曹桂兴, 谭庆贵, 郑永兴, 姜勇. 基于IEEE802.11的星间链路最短接入时延退避算法[J]. 电子学报, 2018, 46(12): 2936-2941.
[13]	杨晶, 刘颜回, 白晶晶, 柳清伙, 聂在平. 交叉极化及副瓣约束的任意阵列最优方向性综合[J]. 电子学报, 2017, 45(3): 712-718.
[14]	陈白, 辛敏洁, 刘伟静, 姚宁, 郝晓辰, 汝小月. 一种基于链路质量的自维护拓扑控制博弈算法[J]. 电子学报, 2016, 44(9): 2227-2234.
[15]	解虎, 冯大政, 袁明冬. 一种基于稀疏约束的稳健波束形成方法[J]. 电子学报, 2016, 44(9): 2276-2281.