基于节点度约束的无线通信网拓扑模型

叶礼邦,郭新海,齐伟伟

(中国洛阳电子装备试验中心,河南 洛阳 471003)

基于节点度约束的无线通信网拓扑模型

叶礼邦,郭新海,齐伟伟

(中国洛阳电子装备试验中心,河南 洛阳 471003)

为了解决无线通信网拓扑模型生成问题,分析了现有网络拓扑模型的不足,结合无线通信网的特点,提出了一种基于最大度约束的无线通信网拓扑演化模型。研究了网络拓扑模型的演化方式和算法步骤,解析计算了模型的度分布。对网络的度分布和网络效率等网络特性进行了仿真分析,仿真结果表明:模型生成的网络具有小世界特性和近似幂律分布,能够充分体现无线通信网的拓扑结构特性。

无线通信网;复杂网络;拓扑模型;节点度;连接模式

郭新海(1981-),男,硕士,工程师。

齐伟伟(1986-),男,硕士,工程师。

无线通信网络的应用范围广泛,结构复杂,其拓扑结构是影响无线通信网网络性能的关键因素。建立无线通信网络的拓扑模型,在此基础上通过仿真试验方式,对网络性能、网络协议进行分析,开展网络结构改进和方案优化研究,可以促进网络性能的提升。因此,建立真实反映网络结构特性的网络拓扑模型一直是无线通信网络研究的热点。

由于无线通信网网络结构复杂,传统的星形网络、环形网络或栅格网络无法真实反映网络结构特性,而随机网络(如ER随机网络模型)虽然可以反映一定的网络复杂性,但是并不能体现网络结构特点。随着复杂网络科学的发展,大量的研究实证,通信网络结构满足“无标度”特性,即网络节点的度分布服从“幂律”分布[1-3]。目前,现有的研究提出了许多满足幂律分布的网络模型,其中最著名的是Balabasi等提出的BA模型[4]。BA模型采用网络增长和择优连接方式,演化出符合幂律分布的网络。针对网络的某些特性,在BA模型的基础上,许多具有特定约束条件的网络拓扑模型相继被提出,如考虑局域世界的“陈-李模型”,该模型新增加的节点偏好选择局域世界内的节点建立连接[5];同时还有兼顾全局和局域世界连接的演化模型,在演化过程中,新增加的节点按照概率p按度优先连接,按概率(1-p)连接到最近的节点[6]。

复杂网络理论提出后,很快应用到了无线通信网络的拓扑建模中,并结合无线通信网络特性,研究出不同的网络拓扑模型。包括考虑网络有线和无线传输条件[7],网络节点的分类和连接规则[8],网络的节点类型[9],网络的空间特性和链路连接特性[10-11],以及网络的节点和链路的不同特性[12],分别建立了相应的网络拓扑模型,并开展了试验验证,大大促进了复杂网络技术在无线通信网建模上的应用。网络拓扑建模关键是要分析网络拓扑特性,然后根据网络拓扑特性建立相应的网络模型,从而得出更加符合实际网络或者更体现研究者关注特征的网络拓扑模型。本文特别针对网络节点的不同接入能力,提出了一种基于节点度约束的无线通信网网络拓扑模型,并对网络的度分布进行了计算和仿真验证,结果表明,该模型能够充分体现无线通信网络的拓扑特性,为后续的网络性能研究提供了理论支撑。

1 网络拓扑演化模型

无线通信网络的通信节点包括各类无线接收设备,这些节点相互连接,构成一个多手段、多层次、立体化的通信网络。但是这些节点的度有一个最大的接入能力,下面根据这一特点,建立具有节点度约束条件下的网络拓扑模型。

1.1 模型设置

BA模型随着时间的增长,某些点的度也在不断增长,体现马太效应,即“富者愈富”,这是BA模型体现的一种现象,对于一些网络,可能会出现这种现象。但对于无线通信网来说,一个节点的连接数受到设备和空间的限制,不可无限制的增长。这一特性说明无线通信网的网络节点度增长到一定程度后,增长趋势会趋于缓慢,甚至零增长。这种特征是BA模型不能模拟的,因此我们引进新的参数:节点接入限制数kmax,对BA模型的择优选择概率进行改进。扩展模型的演化方式如下:

1)增长:初始网络有m0个节点与e0条边,在每一时间步增加一个新的节点,同时这个新节点连接到网络中m(m≤m0)个已经存在的节点上。

2)倾向性选择:一个新的节点选择连接节点仍然是有偏好的,但它选择某个节点i的概率∏(ki)与节点的度不再成正比,因此,将模型的选择概率乘以一个与网络节点度和最大接入限制数kmax有关的因子β(ki),即

(1)

为了控制网络节点度的增长,β(ki)是单调递减函数,且当ki=0时,β(ki)=1;ki=kmax时,β(ki)=0,满足上述规则的函数有很多,为了推导方便,这里将β(ki)取为一种直线递减型函数

(2)

按此偏好连接概率进行连接,当网络中所有节点的度都远远小于kmax时,β(ki)≈1,此时,模型等价于BA模型。当ki增大并趋近最大度kmax时,β(ki)取值逐渐减小,此时就可以控制节点i的度数增长,使其增长到一定的度数就呈现零增长。

1.2 算法步骤

步骤1:初始状态。网络初始有m0个节点和e0条边,m0均匀分布于L×L的平面上,并设定网络e0条边连接关系。

步骤2:节点增加。每次新加入1个节点,新加点的位置在L×L的平面上服从均匀分布。

步骤3:按概率优先连接m条边。连接过程如下:

1)按照公式(1)计算各节点的连接概率;

2)在现有节点中按照概率选择m个节点,新增加节点与所选择的m个现有节点相连。

步骤4:重复步骤2和步骤3,直到产生N个网络节点。

2 模型度分布计算

令网络中第i个节点的度ki为一个连续的实变量,则ki的变化率与∏(ki)成正比。因此,ki应满足下面的动态方程:

(3)

其中,β(ki)为网络节点连接因子,是节点度的函数,如式(2)所示;kj为第j(1≤j≤m) 个节点的节点度。

假设网络中只有少数点的度数接近甚至等于kmax,大部分节点的度还是比较低。为了简化后面的分析过程,不妨作下面的平均假设：

(4)

(5)

将式(5)代入式(4)得到

(6)

将式(6)代入式(3),可以得到

(7)

每个时间步加一个新节点i,增加m度,因此初始条件ki(ti)=m,于是得到

(8)

当t→∞时,某些少数点的度数接近于kmax,显然符合我们的模拟结果。

由式(8)可以得出节点连接度ki小于某一定指k的概率为

(9)

假设是以相等时间间隔增加节点,那么ti的概率密度函数为

(10)

将式(10)代入式(9)可以得到

(11)

所有模型度值的分布函数p(k)为

(12)

当t→∞时,式(12)可以简化为

(13)

由式(13)可见,模型的度分布并不是服从幂律分布,只有当kmax≫m时,式(13)的第2项可以忽略,此时网络的度分布接近幂律分布p(k)∝k-3。

3 仿真试验

按照上述的模型设置,通过仿真试验方式产生网络拓扑模型,并分析网络拓扑性能。在仿真中,500个网络节点随机分布在100km×100km 的范围内,m0=4,e0=6,新加入节点的连接边数为m=2,分别设置网络的节点接入限制数为50、30和10,产生3个网络模型,并对3个网络模型的特性进行分析。

3.1 度分布特性

为了分析不同节点接入限制数的情况,对上述仿真的3种模型的度分布进行分析,不同网络拓扑节点度分布对比如图1所示。

图1 不同节点接入限制数度分布

从图1中可以看出:当网络中最大接入限制数为50和30时,由于网络节点并未达到其限制连接的最大值,因此,网络的节点度分布情况基本一致。当最大节点限制数为10时,大量的节点达到最大节点限制数,使得节点度为5-10的节点大幅增加。

图2 不同节点接入限制数度概率分布

从图2可以看出,网络节点接入限制数为50时,网络的度分布曲线(对数)还基本保持为直线,而当网络节点接入限制数为10时,网络的度分布曲线(对数)明显在下降后明显向上弯曲,表明有较多的节点具有较大的节点度,这个节点度就是网络限制的最大节点度10。

3.2 网络效率

(14)

其中,N为网络节点数。特别的当dij=∞时,即节点i和j之间没有链路连接时,εij=0。

仿真分析了初始条件为m0=4,e0=6,新增节点连接数m分别为1、2、3和4条件下,网络节点接入限制数变化情况下,网络效率变化情况如图3所示。从图中可以看出:

1)网络效率随着网络节点接入限制数的增大而呈现缓慢增大趋势,说明网络节点接入限制数增加,网络中节点度大的节点增多,更多的链路通过这些节点进行传输,使得网络效率增加。

2)网络效率随着新增加节点的连接数的增加而显著增加,说明网络节点的连接度是影响网络效率的重要条件。

图3 网络效率与网络节点接入限制数关系

4 结束语

本文针对无线通信网网络的特点,网络节点接入能力限制,对网络增长和择优连接进行改进,建立了基于节点度约束的无线通信网拓扑模型,并开展了仿真验证。仿真结果表明:模型生成的网络具有小世界特性和近似幂律分布,能够充分体现无线通信网的拓扑结构特性。

[1] 熊金石,李建华,杨迎辉.军事通信网络结构复杂性实证分析[J].军事运筹与系统工程,2012,26(2):77-80.

[2] 邢宁哲.电力光纤通信网的复杂网络特性实证分析[J].光通信技术,2014,38(3):1-4.

[3] 梅丹,王公宝,胡伟文,等.舰船通信网络结构复杂性实证分析[J].舰船电子工程,2014,34(8):53-55+94.

[4] Barabasi,Albert.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[5] LI xiang,CHEN Guanrong.A local-world evolving network model[J].Physica A,2003,328(1-2):274-286.

[6] LI Baoqiang,TIAN Shurong,SI Shoukui,et al.On the simulation of the network topology generator and robustness of the constructed network[C]∥proceedings of 2011 2nd international conference on intelligent control and information processing.Harbin,China:IEEE,2011: 725-728.

[7] 闵雪娇,慕晓冬,张娟.战术互联网网络拓扑模型的研究[J].计算机技术与发展,2007,17(7): 108-109+113.

[8] 张明科,陈政,于长军,等.网络化战争中的复杂网络拓扑建模[J].航天控制,2007,25(4):3-6+12.

[9] 李俊,吕欣,谭跃进.基于空间结构的战术通信网络建模[J].系统工程与电子技术,2010,32(7):1456-1461.

[10] 梁广民,邵丹.基于属性演化和空间影响的路由级拓扑建模[J].计算机工程,2012,38(2):106-108.

[11] 叶礼邦,王满喜,张玉灵,等.基于多连接方式的无线通信网络拓扑模型研究[J].现代电子技术,2016,39(7):1-4.

[12] 吴朔桐,马天旭.多约束的战术互联网拓扑模型研究[J].信息安全与通信保密,2013(11):80-83,88.

Topology-generation Model of Wireless Communication NetworkBased on Node Degree Constraint

YE Li-bang,GUO Xin-hai,QI Wei-wei

(Luoyang Electric Equipment Test Center of China,Luoyang 471003,China)

To solve the topological model generating problem of wireless communication network,the existing methods for topological construction are analyzed.A topological evolving model of wireless communication network with the node degree constraint is proposed according to the characteristic of wireless communication network.The evolving method and the flow of algorithm on the wireless communication network are studied,and the degree distribution of the model is analyzed and calculated.The degree distribution and network efficiency of the network are simulated.The simulation results indicate that the network generated by the model has the small-world characteristics and power-law distribution approximately,which can well satisfy the topological structure of wireless communication network.

wireless communication networks; complex networks; topological model; node degree; connection mode

E96；TN92

A

10.3969/j.issn.1673-3819.2017.05.008

1673-3819(2017)05-0037-04

2017-05-03

2017-06-08

叶礼邦(1981-),男,江西赣州人,硕士,工程师,研究方向为通信和通信系统试验技术。