1、第 44 卷 第 4 期2023 年 4 月 激光杂志LASER JOURNALVol.44,No.4April,2023http /收稿日期:2022-08-27基金项目:陕西省科研计划项目(No.21JK0554)作者简介:朱赖红(1975-),男,硕士,讲师,主要研究方向:计算机软件及系统集成。基于复杂图论的光通信网络节点部署研究朱赖红,王 娟陕西科技大学镐京学院,西安 712046摘 要:为避免光通信网络中不同类别用户的通信碰撞,研究基于复杂图论的光通信网络节点部署方法。分析光通信网络中节点之间的复杂关联性,基于图论构建网络节点部署模型,获取极大全连通子图并确定初始中心点位置;利用该位
2、置优化粒子群算法的粒子的初始位置,获取全局的最优解;采用对称位移对优化粒子群算法,求解得到光通信网络节点在静、动两种环境的最佳部署结果。测试结果显示:该方法可实现节点的均匀部署;以最小的节点数量完成网络动态变化时的节点部署调整,且最大荷载达到 107.6 MBIT/s,不同类别用户的碰撞率低于 0.22%。关键词:复杂图论;光通信;网络节点部署;全连通子图;初始中心点;通信碰撞;二维平面;动态变化中图分类号:TN929 文献标识码:A doi:10.14016/ki.jgzz.2023.04.140Research on node deployment of optical communica
3、tion network based oncomplex Graph TheoryZHU Laihong,WANG JuanHaojing College of Shaanxi University of Science and Technology,Xian 712046,ChinaAbstract:In order to avoid communication collision between different types of users in optical communication net-work,the node deployment method of optical c
4、ommunication network based on complex graph theory is studied.Ana-lyze the complex correlation between nodes in optical communication network,build a network node deployment model based on graph theory,obtain maximal fully connected subgraph and determine the initial center position;The initial posi
5、tion of particles in particle swarm optimization algorithm is optimized by this position to obtain the global optimal solution.The symmetric displacement pair optimization particle swarm optimization algorithm is used to obtain the opti-mal deployment results of optical communication network nodes i
6、n static and dynamic environments.The test results show that this method can realize the uniform deployment of nodes;With the minimum number of nodes,the node de-ployment adjustment is completed when the network changes dynamically,and the maximum load reaches 107.6 MBIT/s,and the collision rate of
7、different types of users is lower than 0.22%.Key words:complex graph theory;optical communication;network node deployment;fully connected subgraph;initial central point;communication collision;two-dimensional plane;dynamic change1 引言光通信指的是依据光波完成通信的一种方式,依据光源的特性可对光通信实行分类,整体可划分成两种,分别为大气激光通信和光纤通信;按照传输波段
8、可分为可见光、红外光和紫外光三种光通信类别1。光通信具备高频率、宽频带、通信容量大以及抗干扰能力强等优势。光网络通信在使用过程中,其节点的部署直接影响网络的通信结果2。网络节点指的是网络中的任意连接点,该节点能够实现信号的再分发。在网络理论或者图论中,节点表示网络拓扑中的相交点或者分支点3。网络节点具备三个显著的特点,一是度中心性、二是紧密中心性、三是中介中心性,三个特点分别表示任一节点直接连接其他节点的http /数量、任一节点与其他所有节点之间最短距离的总和、任一节点位于两两连接的节点上的最短距离数量4。图论是一种分析事物之间关联或者特定关系的一种方法,其是通过数个给定的点、两个点之间的连
9、线组成图像的方式完成,因此,该方法适用于复杂的事物结构中。为保证光通信的通信效果,有学者提出了相关方法。文献5提出了基于可靠性的光网络路由算法,通过接收光信号强度和中断概率构建可靠性模型,然后计算直传和中继链路的距离阈值,以网络能耗均衡为目标构建了路由算法。该方法可以均衡网络能耗,延长网络生命周期。文献6提出将最短路径敏感度作为网络效能测度,以跳数最少、时延最短和可靠性最高为目标构建了光网络关键链路。该方法得到的通信链路最短,通信速度较快。文献7提出利用光-电-光转换器将路径划分为子光路径,选择距离最短节点最少的路径,构成光网络通信。该方法同样可以得到较短的通信路径,增加了通信速度。但上述方法
10、在应用到动态网络环境中时,通信效果不够理想。以光纤网络为例,为实现在网络在静、动两种环境下的网络通信效果,提出基于复杂图论的光通信网络节点部署方法。分析光通信网络中的各个节点的应用情况,依据各类节点之间存在的复杂关联性,基于图论构建网络节点部署模型,获取模型中的光纤网路的拓扑图的二维平面,划分平面获取全连通子图,在此基础上得出极大全连通子图并确定初始中心点位置;利用该位置优化粒子群算法的粒子的初始位置,获取全局的最优解;为保证光通信网络节点在静、动两种环境中均为最佳部署结果,采用对称位移对二次优化粒子群算法,形成基于对称位移映射的中心双子种群粒子算法,优化求解网关节点部署结果。通过实验验证了本
11、方法可以在动静态下实现高荷载、低能耗的节点部署。2 光通信网络节点部署2.1 光纤网络结构光纤网络是光通信中的一种使用极为广泛的网络,其是利用光波在光导纤维中的传输完成通信,利用交换机等终端设备,将网络转换至计算机上。光纤网络作为一种无线多跳网络,网络中的大部分流量均会聚于网关节点之内,因此,网关节点的部署合理性对于网络的性能存在直接影响。光纤网络中各个节点的部署直接影响网络的通信应用效果,其中上限吞吐量则是光纤网络中的一个衡量通信效果的标准。上限吞吐量中,可依据碰撞域完成干扰构建干扰,并估计网络的上限吞吐量。碰撞域成功完成通信的前提是在任一区域内,仅可存在一个单一的活跃连接。如果 MRx和
12、MRy分别表示两个光纤网络路由节点,并且前者是后者的父节点,两者之间的链路称为无序和有序对,用 ln,m和 lx,y表示。ln,m碰撞域则用所有链路的集合表示,集合中的所有链路在 ln,m通信过程中,均处于不活跃状态,以此保证通信的成功。每一个光纤网络中的网关节点均尝试获取碰撞域中的更多的流量,通过多跳的方式传送至最右侧的接收器节点或者网关节点,每一个网关节点只可实现与其相邻节点之间的通信。并且通信过程中,存在上行和下行两种,下行时,网关节点必须发送其自身的碰撞域流量,与此同时,完成上行网关节点流量的转发8;将网关节点发送自身碰撞域的流量称为该节点的潜在流量,用(n)表示;lx,y中必须携带的
13、流量用V(l(x,y)表示,描述 lx,y的值。如果光纤网络中存在的干扰范围为两跳,则链路 l(d,c)的碰撞域 CDdc即为多个链路的集合,用l(b,a),l(c,b),l(d,c),l(e,d),l(f,e)表示。CDdc承载的通信流量用 T(CDdc)表示,其由碰撞域中各个链路的承载流量总和形成,该流量的公式为T(CDdc)=l(m,n)CDxyV(l(m,n)(1)除上述分析的碰撞域之外,还存在瓶颈碰撞域,其由最大通信流量的碰撞域组成9。ET表示网关节点链路集合,其中含有最大流量的通信链路公式为lmax=argmaxl(x,y)(T(CD(l(x,y)l(x,y)ET(2)依据上述公式
14、,即可得出光纤网络的瓶颈碰撞域的公式:BDC=CDlmax(3)式中:BDC 即表示瓶颈碰撞域。其流量用 T(BDC)表示,如果光纤网络的理论最大吞吐量用 TMT 表示;光纤网络中的各个网关节点的最大吞吐量以及网络的拥塞情况10,可依据两者计算得出:C=TMTT(BDC)(4)结合上述分析得出,光纤网络中网关节点对于网络的通信存在直接影响,并且光纤网络中的各网关节点之间、网关节点和其他之间的关联较为复杂11,因此,避免不必要节点的部署,实现最小节点的部署数量、保证光纤网络在静、动两种环境下的最佳通信效果12,是光纤网络中网关节点部署的核心目的。141朱赖红,等:基于复杂图论的光通信网络节点部署
15、研究http /2.2 光通信网络节点部署2.2.1 节点部署模型依据上述小节中分析的光纤网络中网关节点部署的重要性和各类节点之间存在的复杂关联性13,并结合实际的使用环境和需求,采用图论完成光纤网络的网关节点部署。设 G(V,E)表示光纤网路的拓扑图,网络中全部网关节点构成的点集用 V(G)表示,vi表示其中的任意节点,其位置坐标用(xi,yi)表示,节点 vi和 vj之间的距离用 lij表示,如果两者时间的通信半径不小于该距离,则两者为相邻节点14,相邻节点之间的连线无向边,其权重等于 1,称为相邻节点之间的一跳连接,则图 G 的边集 E(G)由全部的无向边组成。如果光纤网络 G 的规模为
16、 n,部署的网关数量为k,k 的相邻矩阵用 A=(eij)nn表示,其中 eijE(G);矩阵的最小距离用 D=(dij)nn表示,其中 dij表示最小跳数。假如 d(vi,uj)d(vi,ul),其中,j,lk,jl,此时路由节点 vi选择 uj作为其网关节点,此时 uj中的服务集 Uj包含 vi。uj和 Uj之间的最大距离用maxviUjd(uj,vi)表示,其也表示 uj的覆盖半径。网关集用uik表示,其覆盖半径用 max1jKmaxviUjd(uj,vi)表示,其值越小表示光纤网络的通信质量越佳。因此,路由节点部署的好坏,可通过 max1jKmaxviUjd(uj,vi)值衡量。光纤网路由节点部署则以 max1jKmaxviUjd(uj,vi)最小值为目的,其公式为minmax1jKmaxviUjd(uj,vi)s.tuikR2(5)式中:R2表示 G 所在的二维平面。2.2.2 网关部署初始中心点位置确定光纤网络在网关节点在部署过程中,可从已有的节点中获取其中 K 个节点作为网关节点,即为节点 K中心问题。在该过程中,该节点可部署在平面 R2的非网络节点上,也可部署在网络节点