基于复杂图论的光通信网络节点部署研究_朱赖红.pdf

第 44 卷 第 4 期2023 年 4 月 激光杂志LASER JOURNALVol.44,No.4April,2023http /收稿日期:2022-08-27基金项目:陕西省科研计划项目(No.21JK0554)作者简介:朱赖红(1975-),男,硕士,讲师,主要研究方向:计算机软件及系统集成。基于复杂图论的光通信网络节点部署研究朱赖红,王 娟陕西科技大学镐京学院,西安 712046摘 要:为避免光通信网络中不同类别用户的通信碰撞,研究基于复杂图论的光通信网络节点部署方法。分析光通信网络中节点之间的复杂关联性,基于图论构建网络节点部署模型,获取极大全连通子图并确定初始中心点位置;利用该位置优化粒子群算法的粒子的初始位置,获取全局的最优解;采用对称位移对优化粒子群算法,求解得到光通信网络节点在静、动两种环境的最佳部署结果。测试结果显示:该方法可实现节点的均匀部署;以最小的节点数量完成网络动态变化时的节点部署调整,且最大荷载达到 107.6 MBIT/s,不同类别用户的碰撞率低于 0.22%。关键词:复杂图论;光通信;网络节点部署;全连通子图;初始中心点;通信碰撞;二维平面;动态变化中图分类号:TN929 文献标识码:A doi:10.14016/ki.jgzz.2023.04.140Research on node deployment of optical communication 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 communication 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 position 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 in 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 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 引言光通信指的是依据光波完成通信的一种方式,依据光源的特性可对光通信实行分类,整体可划分成两种,分别为大气激光通信和光纤通信;按照传输波段可分为可见光、红外光和紫外光三种光通信类别1。光通信具备高频率、宽频带、通信容量大以及抗干扰能力强等优势。光网络通信在使用过程中,其节点的部署直接影响网络的通信结果2。网络节点指的是网络中的任意连接点,该节点能够实现信号的再分发。在网络理论或者图论中,节点表示网络拓扑中的相交点或者分支点3。网络节点具备三个显著的特点,一是度中心性、二是紧密中心性、三是中介中心性,三个特点分别表示任一节点直接连接其他节点的http /数量、任一节点与其他所有节点之间最短距离的总和、任一节点位于两两连接的节点上的最短距离数量4。图论是一种分析事物之间关联或者特定关系的一种方法,其是通过数个给定的点、两个点之间的连线组成图像的方式完成,因此,该方法适用于复杂的事物结构中。为保证光通信的通信效果,有学者提出了相关方法。文献5提出了基于可靠性的光网络路由算法,通过接收光信号强度和中断概率构建可靠性模型,然后计算直传和中继链路的距离阈值,以网络能耗均衡为目标构建了路由算法。该方法可以均衡网络能耗,延长网络生命周期。文献6提出将最短路径敏感度作为网络效能测度,以跳数最少、时延最短和可靠性最高为目标构建了光网络关键链路。该方法得到的通信链路最短,通信速度较快。文献7提出利用光-电-光转换器将路径划分为子光路径,选择距离最短节点最少的路径,构成光网络通信。该方法同样可以得到较短的通信路径,增加了通信速度。但上述方法在应用到动态网络环境中时,通信效果不够理想。以光纤网络为例,为实现在网络在静、动两种环境下的网络通信效果,提出基于复杂图论的光通信网络节点部署方法。分析光通信网络中的各个节点的应用情况,依据各类节点之间存在的复杂关联性,基于图论构建网络节点部署模型,获取模型中的光纤网路的拓扑图的二维平面,划分平面获取全连通子图,在此基础上得出极大全连通子图并确定初始中心点位置;利用该位置优化粒子群算法的粒子的初始位置,获取全局的最优解;为保证光通信网络节点在静、动两种环境中均为最佳部署结果,采用对称位移对二次优化粒子群算法,形成基于对称位移映射的中心双子种群粒子算法,优化求解网关节点部署结果。通过实验验证了本方法可以在动静态下实现高荷载、低能耗的节点部署。2 光通信网络节点部署2.1 光纤网络结构光纤网络是光通信中的一种使用极为广泛的网络,其是利用光波在光导纤维中的传输完成通信,利用交换机等终端设备,将网络转换至计算机上。光纤网络作为一种无线多跳网络,网络中的大部分流量均会聚于网关节点之内,因此,网关节点的部署合理性对于网络的性能存在直接影响。光纤网络中各个节点的部署直接影响网络的通信应用效果,其中上限吞吐量则是光纤网络中的一个衡量通信效果的标准。上限吞吐量中,可依据碰撞域完成干扰构建干扰,并估计网络的上限吞吐量。碰撞域成功完成通信的前提是在任一区域内,仅可存在一个单一的活跃连接。如果 MRx和 MRy分别表示两个光纤网络路由节点,并且前者是后者的父节点,两者之间的链路称为无序和有序对,用 ln,m和 lx,y表示。ln,m碰撞域则用所有链路的集合表示,集合中的所有链路在 ln,m通信过程中,均处于不活跃状态,以此保证通信的成功。每一个光纤网络中的网关节点均尝试获取碰撞域中的更多的流量,通过多跳的方式传送至最右侧的接收器节点或者网关节点,每一个网关节点只可实现与其相邻节点之间的通信。并且通信过程中,存在上行和下行两种,下行时,网关节点必须发送其自身的碰撞域流量,与此同时,完成上行网关节点流量的转发8;将网关节点发送自身碰撞域的流量称为该节点的潜在流量,用(n)表示;lx,y中必须携带的流量用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)依据上述公式,即可得出光纤网络的瓶颈碰撞域的公式:BDC=CDlmax(3)式中:BDC 即表示瓶颈碰撞域。其流量用 T(BDC)表示,如果光纤网络的理论最大吞吐量用 TMT 表示;光纤网络中的各个网关节点的最大吞吐量以及网络的拥塞情况10,可依据两者计算得出:C=TMTT(BDC)(4)结合上述分析得出,光纤网络中网关节点对于网络的通信存在直接影响,并且光纤网络中的各网关节点之间、网关节点和其他之间的关联较为复杂11,因此,避免不必要节点的部署,实现最小节点的部署数量、保证光纤网络在静、动两种环境下的最佳通信效果12,是光纤网络中网关节点部署的核心目的。141朱赖红,等:基于复杂图论的光通信网络节点部署研究http /2.2 光通信网络节点部署2.2.1 节点部署模型依据上述小节中分析的光纤网络中网关节点部署的重要性和各类节点之间存在的复杂关联性13,并结合实际的使用环境和需求,采用图论完成光纤网络的网关节点部署。设 G(V,E)表示光纤网路的拓扑图,网络中全部网关节点构成的点集用 V(G)表示,vi表示其中的任意节点,其位置坐标用(xi,yi)表示,节点 vi和 vj之间的距离用 lij表示,如果两者时间的通信半径不小于该距离,则两者为相邻节点14,相邻节点之间的连线无向边,其权重等于 1,称为相邻节点之间的一跳连接,则图 G 的边集 E(G)由全部的无向边组成。如果光纤网络 G 的规模为 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的非网络节点上,也可部署在网络节点上15。网关节点部署在 R2上的位置差异会导致其网络连接存在差异,因此,需依据该平面区的划分结果获取全连通子图,在此基础上获取极大全连通子图并确定初始中心点位置后,采用改进的粒子群算法对其寻优,获取最优解16,即得出光纤网络节点部署最佳位置。由于光纤网络中,各个光网关节点之间会存在多个全连通子图,其中,部分子图具备其他子图的功能,因此,需降低子图的数量,删除不必要的子图,即表示删除多余的节点17。如果 v1、v2、v3表示光纤网络中的三个节点,如果三者覆盖范围之间存在一定重叠现象,则可形成多个全连通子图,分别用 Z1、Z2、Z3、Z4表示,且 Z1=v1,v3、Z2=v2,v3、Z3=v1,v3、Z4=v1,v2,v3,因此,Z4具备前三个全连通子图的功能,称为极大全连通子图。基于此,如果 Z1,Z2,Z3,Zm表示 R2中的全部全连通子图,Zp则不包含其中,属于 Zk的组成部分,此时 Zk则为 R2中的极大全连通子图。获取极大全连通子图后,定义中心点,将v1,v2,v3坐标均值处的节点作为中心点,用 c 表示;一个v1,v2,v3仅存在一个 c,且 c 的不是固定的,其可出在三个网关节点重叠的阴影部分,也可出现在其他位置。如果出现在阴影部分,此时 c 可替代阴影区域,且位于 c 处的网关节点即可与无法直接通信的节点连接;如果出现在两个网关的重叠阴影部分,位于 c处的网关节点即无法与光纤网络通信中的节点连接。因此,c 可以出现在三个网关节点重叠的阴影部分,也可出现在两个网关的重叠阴影部分。在此情况下,可确定极大全连通子图的中心点。2.3 基于改进粒子群算法的网关节点优化部署确定好中心点后,采用粒子群优化算法求解光纤网络中的网关部署,但是在求解过程中,算法受到初值的影响导致求解结果存在局部最优,因此,为保证光纤网络中网关节点部署的最佳效果,采用 2.2.2 小节确定的中心点优化粒子的初始位置,获取全局的最优解,实现部署优化求解。并且,在此基础上,为保证网关在静、动两种环境中,均为最佳部署结果,在上述的优化基础上,采用对称位移对其实行二次优化,形成基于对称位移映射的中心双子种群粒子算法,完成网关节点部署求解。设光纤网络的网关节点部署解集的空间维度为M,当前最优解用 p 表示,种群遍历后的最优解用 g 表示,粒子自身的位置和速度两种向量分别用 i和 si表示。算法在运算初期对种群实行划分,形成主、次两个子群,两个子群的位置和速度的更新公式为st+1i,d=cwsti,d+a1r1(tp,d-ti,d)+a2r2(tg,d-ti,d)t+1i,d=c(ti,d+st+1i,d)(6)st+1i,d=c wsti,d+sgn(rand-0.5)a1r1(tp,d-ti,d)+a2r2(tg,d-ti,d)()sgn=-1t0|(7)式中:a1和 a2表示学习因子;r1和 r2表示随机变量;241朱赖红,等:基于复杂图论的光通信网络节点部署研究http /w 表示权重。在 D 种群进化过程中,次子群的进化通过差异策略完成,其与全局最优粒子实行吸引或者排斥的概率为二分之一;主子群则一直被全局最优粒子吸引。当光纤网络发生变化后,需对当下的网关节点部署情况实行分析,判断其是否满足应用需求,如果不满足,则采用对称位移映射方法对主子群的空间位置分布实行调整,获取新的网关节点部署方案,删除多余的节点。算法步骤如下所述:(1)采用随机的方式对粒子群实行初始化处理,完成粒子群的划分,形成主、次两个子群;同时依据中心点的结果,优化粒子群,完成粒子速度和位置的更新。(2)分析当前种群的最优解和全局最优解。(3)更新两个子群的速度和位置。(4)判断当下的网关节点部署是否满足应用需求,采用对称位移映射方法对不满足需求的节点部署实行调整。(5)判断算法是否达到停止的迭代次数,如果满足结束算法,反之转至(2)。(6)输出最优的光纤网络网关节点部署结果。3 测试分析为测试本方法的应用结果,采用 NS2 网络仿真工具模拟光通信网络环境,模拟过程中总结点模拟数量100 个,网络的传输速度 0 12 Mbit/s,信道数量 15条,网络接口 6 个,部署范围为直径 270 m 的场景;路由节点通信最大范围 70 m,终端节点最大通信距离55 m,网络中的用户存在主、次两种用户,且图节点最大连接长度为 8,仿真时间 360 s。为衡量采用本方法完成静态网络环境中光通信节点部署的效果,以部署后的节点均衡性作为衡量标准,以最小节点数量、最佳覆盖率为目标,获取本方法的节点部署结果,如图 1 所示。图 1 光通信网络中节点部署结果依据图 1 可知:在网络的部署范围内,本方法具备节点部署能力,并且部署后的节点分布均匀性良好,不存在明显的节点重复部署现象,且部署的各个节点之间距离几乎均等,差距较小,并且部署后,在部署范围内不存在无法覆盖的区域。其是由于本方法通过获取极大全连通子图的中心点,完成节点部署,因此,本方法具备良好的节点部署性能,在最小节点数量、最佳覆盖率下,完成节点的均匀部署。为分析本方法的节点部署优化效果,在光通信网络发生变化的动态场景下,采用本方法对光通信网络中的节点部署实行调整,获取调整前、后网络中节点的部署结果,结果如图 2 所示。(a)动态环境下调整前节点部署情况(b)动态环境下调整后节点部署情况图 2 不同网络环境下节点部署情况依据图 2 可知:网络发生动态变化后,本方法可完成对网络中节点部署的重新调整,删除动态变化前网络中的多余节点,以最小的节点数量完成网络节点部署调整。是由于本方法采用二次优化方式完成光通信网络节点的部署优化求解,可在最少节点数量下,实现动态环境中节点的部署调整。由于光通信网络中各个节点之间存在吸引力,节点数量越多吸引力越大,因此,会导致网关节点中的有效荷载增加,该荷载越大表示算法的性能越佳,获取本方法在静、动两种网络环境中,在不同的节点数量下,部署的网关节点的有效荷载结果,并将该结果与理想的网关节点最低荷载效果标准实行对比,如表1 所示。341朱赖红,等:基于复杂图论的光通信网络节点部署研究http /表 1 网关节点荷载测试结果(MBIT/s)节点数量/个静态环境理想结果实际结果动态环境理想结果实际结果109.7811.227.6411.192018.8420.9412.8219.963029.0433.4922.9132.894037.7239.5530.1838.845044.2146.7136.6346.026055.4758.0145.5257.597062.7664.8757.7164.118077.9480.3664.4979.889085.6988.8476.6188.2210094.72107.688.85106.7依据表 1 可知:随着节点数量的逐渐增加,两种环境中的荷载结果呈现逐渐上升趋势,并且均高于最低荷载效果标准。动态环境中的理想的网关节点最低荷载效果标准低于静态环境中的标准,但是本方法部署后,动态环境中网关节点荷载结果与静态环境中结果差距较小,最大荷载达到 107.6(MBIT/s)。因此,表明本方法具备良好的优势,其部署后的网关节点即便在动态环境中也可达到静态环境中的应用效果。采用本方法完成光通信网络节点部署后,测试其应用性,在网络空间内模拟数据接收中心、终端节点、路由节点,并且网络中主、次用户的通信分别用一级通信和二级通信表示,以图节点最大长度范围为标准,完成网关节点部署,获取节点部署后一级通信和二级通信的区分结果,如图 3 所示。图 3 一级和二级的通信测试结果依据图 3 可知:本方法部署的图节点数量为 5,即表示采用 5 个网关节点完成整个光通信网络的部署,实现网络的正常使用;并且在部署后的网络中,实现主、次用户的一级通信和二级通信,该结果表示本文方法可实现不同用户的通信连接,并且各类用户在通信过程中,能够在图节点连接最大长度在标准范围内,完成不同类型用户的通信连接,应用性良好。为衡量本方法的应用效果,以方法应用后主、次两种用户在网络中发生的碰撞率(通信成功时发生碰撞占据接入次数的比值)作为评价指标,其公式为R=1LLuuu(8)式中:L 表示程序执行次数;次用户在第 u 次通信时,发生的碰撞次数为 u、信道接入的次数为 u表示。依据公式(8)获取本方法应用,在网络中主次用户比例不同时,在不同的通信次数下,两种用户的碰撞率结果,如表 2 所示。期望标准低于 0.25%。表 2 碰撞率测试结果比例通信次数/次515251 100.170.180.192 100.180.20.183 100.180.190.184 100.190.210.215 100.170.220.26 100.180.190.197 100.20.170.228 100.190.190.219 100.210.210.2依据表 2 可知:网络主、次两种用户比例的不同时,通信数量的逐渐增加,两种用户的碰撞率发生一定的波动变化,最高碰撞率为 0.22%,最低碰撞率仅为 0.17%。该结果表明本方法应用后,即便网络中各类用户的通信需求不同,但是网络在部署过程中充分考虑碰撞域与瓶颈碰撞域,因此,可避免发生通信拥塞,使用户在通信过程中的碰撞率降低。为进一步验证本文方法的性能,将文献5、文献6、文献7作为对比方法,在动态环境中部署节点后,测试构建的光通信网络节点传输时延,得到结果如表 3 所示:表 3 不同方法的传输时延/ms节点数量/个 文献5方法 文献6方法 文献7方法本方法105884514311532059446646215530601470465164406124734711695062248847717160631491489184706445105131878065752652418890669544533205100682587557211441朱赖红,等:基于复杂图论的光通信网络节点部署研究http /根据表 3 可知,采用文献5、文献6、文献7方法布置的光通信网络在传输时延上最高达到682 ms、587 ms、557 ms,而本方法布置的光通信网络传输时延最高仅为 211 ms。该结果表明本方法应用后,能够在动态网络的条件下,自适应进行网络节点部署,实现均匀性较好的通信节点连接,从而大大提高通信速度,减少传输时延。4 结论由于光通信网络具备显著的优势,因此,在多个领域中被广泛应用,但是该网络应用过程中节点的部署结果直接影响其网络整体的通信效果。为实现该网络的最佳通信效果,研究基于复杂图论的光通信网络节点部署方法,并对该方法实行相关测试。结果显示:所研究方法能够保证节点部署的均匀性,并且可在网络环境发生动态变化下,调整节点的部署结果;除此之外,本方法部署后的光通信网路能够在应用过程中完成不同用户的区分通信,保证用户碰撞率最低。参考文献1 方菲,刘焕淋,陈勇,等.空分复用弹性光网络中基于频谱集中度的频谱冲突解决算法J.光通信技术,2020,44(07):32-35.2 赵雄文,张钰,秦鹏,等.空天地一体化无线光通信网络关键技术及其发展趋势J.电子学报,2022,50(1):1-17.3 刘文楷,王海瑞,武梦龙.基于深度学习的屏幕通信定位跟踪算法研究J.光通信研究,2020,(02):7-10+60.4 秦浩然,解志斌,翁智辉.水下无线光通信传感器网络路由算法的研究J.激光与光电子学进展,2021,58(11):161-167.5 尹荣荣,刘蕾,杨绸绸,等.基于可靠性的自由空间光网络路由算法J.高技术通讯,2020,30(05):451-460.6 田云飞,彭玲艳,程紫运,等.基于最短路径敏感度的光网络关键链路识别J.光通信研究,2020,(02):11-15.7 李娜娜,宿纪松,包博文,等.基于最少节点的多跳路由和频谱分配算法J.光通信技术,2020,44(09):13-17.8 聂敏,郭建伟,卫容宇,等.基于两端纠缠交换的量子卫星网络路由协议仿真J.激光与光电子学进展,2021,58(03):133-142.9 王永进,傅康,王林宁.一种基于可见光通信技术的光互联方案J.南京邮电大学学报(自然科学版),2020,40(05):134-140.10 周杨,董玉辉,姚旭,等.空间激光通信网络拓扑算法设计与仿真研究J.计算机工程与科学,2022,44(1):68-74.11 赵太飞,林亚茹,马倩文,等.无人机编队中无线紫外光隐秘通信的能耗均衡算法J.电子与信息学报,2020,42(12):2969-2975.12 王杨,赵红东.基于智能手机的 VLC/IPDR 粒子滤波融合室内定位J.中国激光,2020,47(07):365-373.13 梁赫西,沈天浩,王振亚,等.双光源水下无线光通信系统的研究与实现J.红外与激光工程,2021,50(9):312-320.14 杨海宁,李昆,初大平.硅基液晶技术与可重构全光通信网络J.液晶与显示,2021,36(06):772-788.15 郭瑛,徐艳红,秦岭,等.基于 DHPIM 调制可见光通信系统的研究J.计算机仿真,2020,37(04):147-150.16 徐文艳,唐涛,段田东,等.可见光通信网络节能资源分配策略研究J.光学精密工程,2020,28(7):1577-1587.17 牟迪,蒙文,赵尚弘,等.基于 Wasserstein 生成对抗网络的智能光通信J.中国激光,2020,47(11):224-230.541朱赖红,等:基于复杂图论的光通信网络节点部署研究