基于边生命周期的短波IP网络随机图模型*

2013-06-27黄国策陈延文叶向阳

电讯技术 2013年11期

关键词：度值短波生命周期

景渊,黄国策,陈延文,叶向阳,徐斌

(1.空军工程大学信息与导航学院,西安710077;2.解放军93246部队,长春130051;3.解放军93534部队,河北唐山063000)

基于边生命周期的短波IP网络随机图模型*

景渊1,**,黄国策1,陈延文2,叶向阳1,徐斌3

(1.空军工程大学信息与导航学院,西安710077;2.解放军93246部队,长春130051;3.解放军93534部队,河北唐山063000)

针对短波IP网络中物理连接存在生命周期和接收节点选择方式不同对网络拓扑结构和性能产生的影响,提出了一种基于边生命周期和接收节点多种选择方式的随机图模型。模型中节点之间边生命周期服从正态分布,而新边建立的节点选择方式按照随机选择、度值择优选择和度值反择优选择的方式,用来模拟短波IP网络不同的通信过程。理论分析和仿真也发现,接收节点选择方式的不同将会对网络的度分布、平均最短距离、网络总的度值和节点最大度值及聚集系数都产生影响,而小的连接生命周期将显著减少网络中总的度值和节点的最大度值,减少对物理层资源的占用,提升网络的效能。

短波IP网络;随机图模型;生命周期;度分布;聚集系数

1 引言

复杂网络在无线通信网络拓扑结构研究中发挥着重要的作用,主要是因为其可以通过对网络节点特性进行研究得到网络的统计拓扑特性。文献[1]通过计算无线传感器网络的度分布、聚集系数、平均路径长度和网络连通性等拓扑性质,分析了网络的节点数、通信半径和连通率等特性。文献[2]通过小世界现象对无线传感器网络进行拓扑优化。文献[3]在无线自组织网络中结合复杂网络理论分析了移动场景下平均最短距离、聚类系数和度分布特性。而文献[4]以复杂网络为基础构建卫星信息支援下的联合作战网络拓扑结构和效能评估模型。通过使用不同的复杂网络模型可以很好地表征不同类型无线通信网络的拓扑特性,为此,本文将这一方法使用到短波IP网络中进行研究。

传统的短波通信网络,拓扑结构一般为树状或者星型等规则网络,网络拓扑固定。但随着短波IP网络的出现,用户行为将影响着网络的拓扑结构生成,使得短波IP网络的拓扑结构呈现出高动态特性。本文提出在考虑边(物理链路)生命周期的基础上建立短波IP网络的随机图模型,并分析在不同的链路建立准则下网络所呈现出不同的拓扑特性。

2 短波IP网络

在使用随机图模型对通信网络进行研究时,短波IP网络与一般的通信网络具有两个明显的区别。

首先是网络中节点之间的边并不是长期存在的,一旦节点之间的数据传输完毕,需要对有限的物理层资源进行释放,那么网络中的拓扑结构就会因为连接的建立和释放呈现出变化的特性,同时为了使网络正常运行,可以得到网络在运行过程中所需的物理层资源的数量(如频率等)。

其次是网络中不同的业务类型对接收节点的选择方式不同会影响网络的拓扑特性。假设连接建立时,接收节点的选择具有多种不同的规则,那么每种规则对网络的拓扑产生的影响并不相同。

3 建模研究

3.1 模型分析

图1显示的是短波IP网络结构示意图。可以看到,无线链路的建立具有一定的随机性,而图中显示的只是某一个时刻网络的拓扑情况。不同短波IP网络中可能会使用不同的MAC协议,网络的瞬时拓扑结构可能会有差异,但是网络中边都具有生命周期,而且在通信网络中边的建立可以通过3种节点选择方式的概率混合进行模拟,因此网络具有一定的通用性,能够模拟短波IP网络的通用性能。

从图1可以看出,由于短波的超视距通信特性,网络中任意节点之间都可以建立连接,网络是一个全联通的网络。

图1 短波IP网络结构图Fig.1 The HF IP network structure

这里假设网络中共有N个成员,在每一个时间步内产生n个通信需求。需要分别建立短波链路进行数据的传输,而每个通信需求的数据量大小按照所需的传输时间步来衡量。假设一个通信需求的大小为t′,即需要t′个时间步之后该数据将传输完毕,物理链路(网络的连接)将拆除,也即连接的生命周期为t′。假设网络中连接的生命周期大小相互独立,且服从均值为tmean的正态分布。

网络中节点在建立连接过程中,发送节点随机选择,接收节点按照一定规则选择,已经具有连接的两个节点之间不能重复建立连接。每一个时间步内,任意节点在新建连接中只能作一次发送节点。

3.2 度分布

度值反映的是网络中单个节点的连接特性,而度分布表示节点度值出现的概率。度和度分布都是网络的重要特性。在短波IP网络中,通过研究网络中节点的度值及其分布,可以了解网络中不同节点建立无线连接的情况,以及无线连接在网络中的分布情况,进而可以计算网络中的无线连接主要集中在哪些节点中,更好地对网络进行频谱资源的支配,尽量避免某些节点由于连接建立数量较大导致的物理层设备短缺和信道资源限制的问题,合理支配网络资源,同时可以实现对网络拓扑结构的预估计。

任意时间步内,节点的度值变化可以分为三部分:作为发送节点建立连接、作为接收节点建立连接、已经建立的连接达到生命周期而消失。

3.2.1 场景A:接收节点随机选择

由此可以得到节点度值的变化率方程为

式中,P1(t)表示节点i在t时刻的任意一个连接的生命周期结束,假设网络中节点的生命周期的最大值为tmax。

式中,p1(x)表示一个连接的生命周期为x的概率,则有

式中,tmean为x的均值,σ2＞0表示x的方差。

由式(2)可知,P1(t)的大小与时刻t没有关系,那么可以通过平均场理论[5-6]计算得到节点的度分布。

首先对式(1)的一阶线性微分方程求解:

并且ki(0)=0,可以得到

由于t≫tmax,有可以得到

3.2.2 场景B:接收节点依照度值择优

当接收节点按照度值最优的方式进行选择时,会出现“富者更富”的情况,网络中会出现某几个点的度值非常大,而大部分节点的度值则比较小。

式中,S(t)表示网络中总度数。得到S(t)的递推公式为

当t≫tmax时,网络的变化达到稳定状态,即

那么有

与场景A同理,可通过平均场理论得到网络度分布:

令

得到

可以通过μ(k)函数修正得到一个全微分方程

解全微分方程,可以得到ki(t):

可以得到

将式(11)代入式(15)中可得到网络度分布结果。

3.2.3 场景C:接收节点依照度值择优和择劣的混合比

其中,p表示在进行连接对象选择时,依照择优选择的概率∏(ki),那么1-p表示按照择劣选择的概率∏′(ki)。

式(17)可以转化为

令

任意节点的度值变化率微分方程式(18)可以转变为式(11)。将式(19)代入到式(15)中可以得到场景C中节点的度分布Pc(k)结果。

通过以上计算可以得到接收节点的选择机制不同情况下网络的度分布结果,这一结果将成为后面对网络其他特性的研究和计算的基础。

仿真中选择100个节点,在接收节点混合选择时混合比为0.5,以下仿真结果均为100次仿真的平均值(仿真次数对网络中结果产生影响,仿真是在2 000时间步之后进行平均)。

图2显示的是当网络中瞬时承载的连接数量较少时网络的度分布情况,其中单位时间内新建10个连接,而连接的平均生命周期为10个时间步。从图中可以看出,在度值较小时接收节点按照混合比选择时具有较大的概率,而度值择优选择则具有较小的概率,随机选择居中。这主要是因为度值混合选择时有一半的概率选择了度值较小的节点。此外,在使用度值择优选择和混合选择时网络中的最大度值明显大于随机选择方式,主要是因为其中都包含了度值择优选择的成分,而度值择优选择时最大度值的概率大于混合选择方式。

图2 网络的度分布Fig.2 The degree distribution of the network

图3 和图4显示的是网络中承载的连接数量较多时(单位时间建立20个连接),连接的平均生命周期对网络度分布的影响,可以看到随着连接平均生命周期的增加,网络中最大概率度值变大,网络的最大度值也显著增加。因此,减少网络中的业务传输量或者提高节点的数据处理能力(即降低连接的生命周期)可以明显减少网络中高度值节点的概率,减少对物理层资源的占用。

图3 连接平均生命周期为10时的度分布Fig.3 The degree distribution of the network when tmeanis 10

图4 连接平均生命周期为20时的度分布Fig.4 The degree distribution of the network when tmeanis 20

从仿真结果中可以看出,网络在发展过程中,不同的接收节点选择方式对节点的度分布情况产生影响。在接收节点随机选择时,网络中度值较大的节点和度值较小的节点所占的比例明显高于其他两种方式,会造成网络中连接建立较为集中。那么对于短波IP网络来说,单个节点如果建立连接过多,一旦频率使用不当会造成同址干扰等情况,此外较多连接使得节点的连接管理复杂度提高。

由于网络中有多种业务需要进行传输,不同业务对网络度分布的贡献是不同的,根据网络中业务出现的概率、接收节点的选择方式以及业务在物理连接中的平均生命周期可以得到网络在稳定状态下度分布情况,对网络的拓扑管理具有积极意义。

3.3 最大度值和网络总的度值

在短波IP网络中分析节点的最大度值,了解节点的最大连接数可以提前确定网络中节点需要设置的物理层设备传输容量,使得网络在运行过程中能够确保用户需求的连接能够正常建立。网络中最大度值由网络的规模以及度值分布决定。

文献[7]给出了一种通过计算不同k值作为网络最大度值时的概率,并进行统计平均,得到一般网络模型中最大度值的计算方法,使得k满足式(20)[8]时得到网络最大度值。

通过将第3.2节中的度分布代入到式(20)中就可以分别得到kmax,a、kmax,b和kmax,c。通过计算发现,在相同网络规模和网络参数条件下满足kmax,a＜kmax,c＜kmax,b关系。

网络总的度值可以表征网络在平衡态时总的连接数量,由此可以了解网络在运行过程中需要的无线信道资源。由网络建立的不同原理(这里选择三种接收节点的确定方式)、网络规模及实际需求来合理配置无线信道资源。网络中总的度值在3.2节中已经进行了分析,通过式(7)～(9)已经得到,为网络资源的总体规划提供了依据。

图5显示的是在连接生命周期不同的的情况下,网络的平均最大节点度值和总的度值。

图5 连接的平均生命周期对网络中最大度值和总度值影响Fig.5 The influence of tmeanon the kmaxand〈k〉

从图中可以看出,网络的平均最大度值和总的度值随着连接的平均生命周期的增加而不断增加。但曲线的二阶导数小于0,使得增加的速度逐渐变缓。而在相同连接生命周期情况下,接收节点择优选择将带来更大的平均最大度值。网络中平均最大度值和总的度值越大,意味着节点建立的连接越多,占用的物理层资源将越多,因此有必要减少连接的生命周期。同时,多样化接收节点的选择方式使网络中连接建立越均匀。对于业务类型和平均业务量一定的情况下可以通过提高节点的数据处理能力和链路的数据传输效率来降低连接的生命周期。

3.4 最短路径长度

短波IP网络中任意需要通信的两个节点之间可以直接建立无线链路。而研究最短路径长度是为了研究网络中数据多跳传输的延时,因此在本网络中最短路径长度研究的意义不大,在这里不做重点研究。对网络处于稳态时网络最短路径进行仿真分析,仿真选择网络在稳态状态时某一时刻网络的平均最短距离。如图6所示,当接收节点使用度值择优方式时,相比较其他方式具有更小的平均最短距离。

图6 连接生命周期对网络平均最短距离影响Fig.6 The influence of tmeanon the average shortest distance

3.5 聚集系数

网络的聚集系数表征的是网络中任意节点a所连接的邻居节点中相互连接的概率[9],一般用C来表示。文献[10]给出了网络通过度值分布特性得到聚集系数的一般表达式:

其中:

由图7可以看出,随着连接的平均生命周期的增加,网络的聚集系数也在逐渐增加,但增加的趋势在减缓。网络的最大聚集系数在0.1左右。当网络中连接的平均生命周期较小时,网络中连接建立和消失的速度非常快,网络中总的连接的数量较少,网络的拓扑结构变化较快,出现邻居节点互联的概率较小。这也与小世界网络中当边的重连概率较大时聚集系数也较小的特点相近。而随着连接的生命周期增加,网络中总的连接的数量增加,邻居节点中相互连接的概率增加。

图7 连接的生命周期对网络聚集系数的影响Fig.7 The influence of tmeanon the clustering coefficient

通信网络中聚集系数较高说明网络中社团结构较为明显,网络中连接的数量较多。但是在短波IP网络中,当业务的传输量和大小一定时瞬时总的连接数量越少越好,说明网络在对业务传输的处理能力上越强,对连接的管理越高效。

4 结论

本文通过对短波IP网络中物理连接生命周期和接收节点选择方式不同对网络特性的研究,提出了一种基于边生命周期和多种接收节点选择方式的短波IP网络随机图模型。通过模型分析发现网络中连接的生命周期越小网络的拓扑变化越快,对业务传输的效率越高。而接收节点选择方式种类越多网络中节点的最大度值出现概率越小,网络中连接建立越均匀。

文献[11-12]也证明了确定性选择方式在现代网络中普遍存在性,但本文中还没有进行考虑。下一步将在节点选择方式中增加确定性选择方式。

[1] 张成才,齐小刚.基于复杂网络理论的无线传感器网络特征度量分析[J].计算机科学,2010,37(11):44-47. ZHANG Cheng-cai,QI Xiao-gang.Analysis of Wireless Seneor Network Characteristics Measurement Based on Complex Network Theory[J].Computer Sicence,2010, 37(11):44-47.(in Chinese)

[2] 叶秀彩,许力,林力伟.基于小世界现象的无线传感器网络拓扑优化[J].福建师范大学学报(自然科学版),2008,24(5):37-40. YE Xiu-cai,XU Li,LIN Li-wei.Topology Optimization Based on Small-world Phenomenon in Wireless Sensor Networks[J].Journal of Fujian Normal University(Natural Science Edition),2008,24(5):37-40.(in Chinese)

[3] 童超,龙翔,高小鹏.基于随机路径点模型的Ad hoc网络复杂统计特性[J].北京航空航天大学学报, 2008,34(10):1236-1242. TONG Chao,LONG Xiang,GAO Xiao-peng.Complexity Statistical Characteristics for Ad hoc Network Based on Random Waypoint Model[J].Journal of Beijing University of Aeronautics and Astronautics,2008,34(10): 1236-1242.(in Chinese)

[4] 曹士信,金鑫.卫星信息支援影响度排序模型[J].系统工程与电子技术,2009,31(7):1672-1676. CAO Shi-xin,JIN Xin.Ranking Model on Different Importance of Militery Satellite Information Supporting to Operations[J].Systems Engineering and Electronics, 2009,31(7):1672-1676.(in Chinese)

[5] Albert L B,Reka A.Emergence of Scaling in Random Networks[J].Science,1999,286:509-512.

[6] Albert L B,Reka A,Hawoong J.Mean-field Theory for Scale-Free Random Networks[J].Physica Review A, 1999,272(1-2):173-187.

[7] Adamic L A,Lukose R M,Puniyani A R,et al.Search in power-law networks[J].Physical Review E,2001,64 (4):046135.

[8] Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[9] 郑耿忠,刘三阳,齐小刚.基于小世界网络模型的无线传感器网络拓扑研究综述[J].控制与决策,2010,25 (12):1761-1768. ZHENG Geng-zhong,LIU San-yang,QI Xiao-gang. Survey on Topology of Wireless Sensor Networks Based on Small World Network Model[J].Control and Decision, 2010,25(12):1761-1768.(in Chinese)

[10] Ebel H,Mielsch L I,Bornholdt S.Scale-free topolog of e-mail networks[J].Physical Review E,2002,66(3): 035103.

[11] 方锦清,毕桥,李永,等.复杂动态网络的一种和谐统一的混合择优模型及其普适特性[J].中国科学(G辑),2007,37(2):230-249. FANG Jin-qing,BI Qiao,LI Yong,et al.A Harmonious and Unified Hybrid Preferential Model for Complex Dynamic Network and its Universality Analysis[J].Science in China(Series G),2007,37(2):230-249.(in Chinese)

[12] 方锦清,李永.网络科学中统一混合理论模型的若干研究进展[J].力学进展,2008,38(6):633-678. FANG Jin-qing,LI Yong.Advances in Unified Hybrid Theoretical Model of Network Science[J].Advances in Mechanics,2008,38(6):663-678.(in Chinese)

JING Yuan was born in Yan′an,Shaanxi Province,in 1986.He is currently working toward the Ph.D.degree.His research direction is wireless communication network.

Email:gmt_jingyuan@163.com

黄国策(1962—),男,陕西高陵人,空军工程大学教授,主要研究方向为无线通信网;

HUANG Guo-ce was born in Gaoling,Shaanxi Province,in 1962.He is now a professor.His research direction is wireless communication network.

陈延文(1971—),男,山东高密人,解放军93246部队工程师,主要研究方向为指挥自动化;

CHEN Yan-wen was born in Gaomi,Shandong Province,in 1971.He is now an engineer.His research direction is command automation.

叶向阳(1970—),男,湖北英山人,空军工程大学高级实验师,主要研究方向为无线通信组网;

YE Xiang-yang was born in Yingshan,Hubei Province,in 1970.He is now a senior experimentalist.His research direction is wireless communication network.

徐斌(1972—),男,河北唐山人,解放军93534部队工程师,主要研究方向为指挥自动化。

XU Bin was born in Tangshan,Hebei Province,in 1972.He is now an engineer.His research direction is command automation.

Random Graphics Model for HF IP Network Based on Edge Life Cycle

JING Yuan1,HUANG Guo-ce1,CHEN Yan-wen2,YE Xiang-yang1,XU Bin3
(1.School of Information and Navigation,Air Force Engineering University,Xi′an 710077,China; 2.Unit 93246 of PLA,Changchun 130051,China;3.Unit 93534 of PLA,Tangshan 063000,China)

In HF IP network,the life cycle of physical connection and the different selection method of the receiving node will have an impact on the network topology and performance.A random graphics model is proposed based on the edge life cycle and different

node selection methods.The life cycle of the edge obeys the normal distribution.What is more,three node selection methods are presented including random selection,preferred selection based on the node degree or the bottom of the node degree.Theoretical analysis and simulation demonstrate that differences of the receiving node selection method will affect the network degree distribution,the average shortest length,the total value of network degree,the maximum degree for a node and the clustering coefficient.At the same time,reducing the edge life cycle will decrease the total degree of the network and the value of maximum degree of a node,and also optimize the physical resource utilization and increase network efficiency.

HF IP network;random graphics model;edge life cycle;degree distribution;clustering coefficient

The National Natural Science Foundation of China(No.61202490);National Defense Science and Technology Key Laboratory Fund(9140C020102110C0207)

TN915

1001-893X(2013)11-1487-07