一种基于遗传算法的通信网拓扑优化方法*

尹梦梦，王 磊，姚昌华，童 玮

（1.陆军工程大学，江苏 南京 210001；2.南京信息工程大学，江苏 南京 210044）

0 引言

通信网[1]的网络结构（即网络拓扑）是泛指网络节点和传输线路的几何连接形状，关系着网络连通性问题[2]。从网络的内部结构属性出发，探究具有较高可靠性的通信网，在各种实际应用中是一项重要需求。

目前，关于通信网可靠性的研究已取得了不少成果。文献[3]提出了实现导航共享的通信网络拓扑优化方法，为寻找不同条件下具有最小通信连接数（Minimum of Communication Connections Number，MCCN）的通信网络拓扑建立了导航共享的MCCN 拓扑模型，并设计了相应方法，理论上证明了算法的有效性。文献[4]提出了一种基于服务特性和节点可靠性的电力通信网络故障恢复算法，通过与传统算法的比较，验证了该算法提高了电力通信网络的故障恢复率和收益，具有很大的实际应用价值。文献[5]利用FCM 算法对电力通信网的关键资源进行识别和备份，从而提升了电力通信网的可靠性。文献[6]以复杂网络为研究对象，建立了基于冗余度的网络可靠性及节点重要度评估模型。结果表明，该模型算法能为一定约束成本限制下高可靠性网络的构造问题提供解决方案。

本文从通信网拓扑结构的角度构建可靠性优化模型。该模型属于NP-hard 问题，直接求解难度大。本文针对目标函数设计了改进的遗传算法求解该模型，是一种启发式方法。编码过程即网络转化为邻接矩阵的过程，设计的优化变量是以图的邻接矩阵形式进行编码。……