基于節(jié)點度約束的無線通信網(wǎng)拓撲模型

葉禮邦,郭新海,齊偉偉

(中國洛陽電子裝備試驗中心,河南 洛陽 471003)

基于節(jié)點度約束的無線通信網(wǎng)拓撲模型

葉禮邦,郭新海,齊偉偉

(中國洛陽電子裝備試驗中心,河南 洛陽 471003)

為了解決無線通信網(wǎng)拓撲模型生成問題,分析了現(xiàn)有網(wǎng)絡拓撲模型的不足,結合無線通信網(wǎng)的特點,提出了一種基于最大度約束的無線通信網(wǎng)拓撲演化模型。研究了網(wǎng)絡拓撲模型的演化方式和算法步驟,解析計算了模型的度分布。對網(wǎng)絡的度分布和網(wǎng)絡效率等網(wǎng)絡特性進行了仿真分析,仿真結果表明:模型生成的網(wǎng)絡具有小世界特性和近似冪律分布,能夠充分體現(xiàn)無線通信網(wǎng)的拓撲結構特性。

無線通信網(wǎng);復雜網(wǎng)絡;拓撲模型;節(jié)點度;連接模式

郭新海(1981-),男,碩士,工程師。

齊偉偉(1986-),男,碩士,工程師。

無線通信網(wǎng)絡的應用范圍廣泛,結構復雜,其拓撲結構是影響無線通信網(wǎng)網(wǎng)絡性能的關鍵因素。建立無線通信網(wǎng)絡的拓撲模型,在此基礎上通過仿真試驗方式,對網(wǎng)絡性能、網(wǎng)絡協(xié)議進行分析,開展網(wǎng)絡結構改進和方案優(yōu)化研究,可以促進網(wǎng)絡性能的提升。因此,建立真實反映網(wǎng)絡結構特性的網(wǎng)絡拓撲模型一直是無線通信網(wǎng)絡研究的熱點。

由于無線通信網(wǎng)網(wǎng)絡結構復雜,傳統(tǒng)的星形網(wǎng)絡、環(huán)形網(wǎng)絡或柵格網(wǎng)絡無法真實反映網(wǎng)絡結構特性,而隨機網(wǎng)絡(如ER隨機網(wǎng)絡模型)雖然可以反映一定的網(wǎng)絡復雜性,但是并不能體現(xiàn)網(wǎng)絡結構特點。隨著復雜網(wǎng)絡科學的發(fā)展,大量的研究實證,通信網(wǎng)絡結構滿足“無標度”特性,即網(wǎng)絡節(jié)點的度分布服從“冪律”分布[1-3]。目前,現(xiàn)有的研究提出了許多滿足冪律分布的網(wǎng)絡模型,其中最著名的是Balabasi等提出的BA模型[4]。BA模型采用網(wǎng)絡增長和擇優(yōu)連接方式,演化出符合冪律分布的網(wǎng)絡。針對網(wǎng)絡的某些特性,在BA模型的基礎上,許多具有特定約束條件的網(wǎng)絡拓撲模型相繼被提出,如考慮局域世界的“陳-李模型”,該模型新增加的節(jié)點偏好選擇局域世界內(nèi)的節(jié)點建立連接[5];同時還有兼顧全局和局域世界連接的演化模型,在演化過程中,新增加的節(jié)點按照概率p按度優(yōu)先連接,按概率(1-p)連接到最近的節(jié)點[6]。

復雜網(wǎng)絡理論提出后,很快應用到了無線通信網(wǎng)絡的拓撲建模中,并結合無線通信網(wǎng)絡特性,研究出不同的網(wǎng)絡拓撲模型。包括考慮網(wǎng)絡有線和無線傳輸條件[7],網(wǎng)絡節(jié)點的分類和連接規(guī)則[8],網(wǎng)絡的節(jié)點類型[9],網(wǎng)絡的空間特性和鏈路連接特性[10-11],以及網(wǎng)絡的節(jié)點和鏈路的不同特性[12],分別建立了相應的網(wǎng)絡拓撲模型,并開展了試驗驗證,大大促進了復雜網(wǎng)絡技術在無線通信網(wǎng)建模上的應用。網(wǎng)絡拓撲建模關鍵是要分析網(wǎng)絡拓撲特性,然后根據(jù)網(wǎng)絡拓撲特性建立相應的網(wǎng)絡模型,從而得出更加符合實際網(wǎng)絡或者更體現(xiàn)研究者關注特征的網(wǎng)絡拓撲模型。本文特別針對網(wǎng)絡節(jié)點的不同接入能力,提出了一種基于節(jié)點度約束的無線通信網(wǎng)網(wǎng)絡拓撲模型,并對網(wǎng)絡的度分布進行了計算和仿真驗證,結果表明,該模型能夠充分體現(xiàn)無線通信網(wǎng)絡的拓撲特性,為后續(xù)的網(wǎng)絡性能研究提供了理論支撐。

1 網(wǎng)絡拓撲演化模型

無線通信網(wǎng)絡的通信節(jié)點包括各類無線接收設備,這些節(jié)點相互連接,構成一個多手段、多層次、立體化的通信網(wǎng)絡。但是這些節(jié)點的度有一個最大的接入能力,下面根據(jù)這一特點,建立具有節(jié)點度約束條件下的網(wǎng)絡拓撲模型。

1.1 模型設置

BA模型隨著時間的增長,某些點的度也在不斷增長,體現(xiàn)馬太效應,即“富者愈富”,這是BA模型體現(xiàn)的一種現(xiàn)象,對于一些網(wǎng)絡,可能會出現(xiàn)這種現(xiàn)象。但對于無線通信網(wǎng)來說,一個節(jié)點的連接數(shù)受到設備和空間的限制,不可無限制的增長。這一特性說明無線通信網(wǎng)的網(wǎng)絡節(jié)點度增長到一定程度后,增長趨勢會趨于緩慢,甚至零增長。這種特征是BA模型不能模擬的,因此我們引進新的參數(shù):節(jié)點接入限制數(shù)kmax,對BA模型的擇優(yōu)選擇概率進行改進。擴展模型的演化方式如下:

1)增長:初始網(wǎng)絡有m0個節(jié)點與e0條邊,在每一時間步增加一個新的節(jié)點,同時這個新節(jié)點連接到網(wǎng)絡中m(m≤m0)個已經(jīng)存在的節(jié)點上。

2)傾向性選擇:一個新的節(jié)點選擇連接節(jié)點仍然是有偏好的,但它選擇某個節(jié)點i的概率∏(ki)與節(jié)點的度不再成正比,因此,將模型的選擇概率乘以一個與網(wǎng)絡節(jié)點度和最大接入限制數(shù)kmax有關的因子β(ki),即

(1)

為了控制網(wǎng)絡節(jié)點度的增長,β(ki)是單調遞減函數(shù),且當ki=0時,β(ki)=1;ki=kmax時,β(ki)=0,滿足上述規(guī)則的函數(shù)有很多,為了推導方便,這里將β(ki)取為一種直線遞減型函數(shù)

(2)

按此偏好連接概率進行連接,當網(wǎng)絡中所有節(jié)點的度都遠遠小于kmax時,β(ki)≈1,此時,模型等價于BA模型。當ki增大并趨近最大度kmax時,β(ki)取值逐漸減小,此時就可以控制節(jié)點i的度數(shù)增長,使其增長到一定的度數(shù)就呈現(xiàn)零增長。

1.2 算法步驟

步驟1:初始狀態(tài)。網(wǎng)絡初始有m0個節(jié)點和e0條邊,m0均勻分布于L×L的平面上,并設定網(wǎng)絡e0條邊連接關系。

步驟2:節(jié)點增加。每次新加入1個節(jié)點,新加點的位置在L×L的平面上服從均勻分布。

步驟3:按概率優(yōu)先連接m條邊。連接過程如下:

1)按照公式(1)計算各節(jié)點的連接概率;

2)在現(xiàn)有節(jié)點中按照概率選擇m個節(jié)點,新增加節(jié)點與所選擇的m個現(xiàn)有節(jié)點相連。

步驟4:重復步驟2和步驟3,直到產(chǎn)生N個網(wǎng)絡節(jié)點。

2 模型度分布計算

令網(wǎng)絡中第i個節(jié)點的度ki為一個連續(xù)的實變量,則ki的變化率與∏(ki)成正比。因此,ki應滿足下面的動態(tài)方程:

(3)

其中,β(ki)為網(wǎng)絡節(jié)點連接因子,是節(jié)點度的函數(shù),如式(2)所示;kj為第j(1≤j≤m) 個節(jié)點的節(jié)點度。

假設網(wǎng)絡中只有少數(shù)點的度數(shù)接近甚至等于kmax,大部分節(jié)點的度還是比較低。為了簡化后面的分析過程,不妨作下面的平均假設：

(4)

(5)

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

(6)

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

(7)

每個時間步加一個新節(jié)點i,增加m度,因此初始條件ki(ti)=m,于是得到

(8)

當t→∞時,某些少數(shù)點的度數(shù)接近于kmax,顯然符合我們的模擬結果。

由式(8)可以得出節(jié)點連接度ki小于某一定指k的概率為

(9)

假設是以相等時間間隔增加節(jié)點,那么ti的概率密度函數(shù)為

(10)

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

(11)

所有模型度值的分布函數(shù)p(k)為

(12)

當t→∞時,式(12)可以簡化為

(13)

由式(13)可見,模型的度分布并不是服從冪律分布,只有當kmax?m時,式(13)的第2項可以忽略,此時網(wǎng)絡的度分布接近冪律分布p(k)∝k-3。

3 仿真試驗

按照上述的模型設置,通過仿真試驗方式產(chǎn)生網(wǎng)絡拓撲模型,并分析網(wǎng)絡拓撲性能。在仿真中,500個網(wǎng)絡節(jié)點隨機分布在100km×100km 的范圍內(nèi),m0=4,e0=6,新加入節(jié)點的連接邊數(shù)為m=2,分別設置網(wǎng)絡的節(jié)點接入限制數(shù)為50、30和10,產(chǎn)生3個網(wǎng)絡模型,并對3個網(wǎng)絡模型的特性進行分析。

3.1 度分布特性

為了分析不同節(jié)點接入限制數(shù)的情況,對上述仿真的3種模型的度分布進行分析,不同網(wǎng)絡拓撲節(jié)點度分布對比如圖1所示。

圖1 不同節(jié)點接入限制數(shù)度分布

從圖1中可以看出:當網(wǎng)絡中最大接入限制數(shù)為50和30時,由于網(wǎng)絡節(jié)點并未達到其限制連接的最大值,因此,網(wǎng)絡的節(jié)點度分布情況基本一致。當最大節(jié)點限制數(shù)為10時,大量的節(jié)點達到最大節(jié)點限制數(shù),使得節(jié)點度為5-10的節(jié)點大幅增加。

圖2 不同節(jié)點接入限制數(shù)度概率分布

從圖2可以看出,網(wǎng)絡節(jié)點接入限制數(shù)為50時,網(wǎng)絡的度分布曲線(對數(shù))還基本保持為直線,而當網(wǎng)絡節(jié)點接入限制數(shù)為10時,網(wǎng)絡的度分布曲線(對數(shù))明顯在下降后明顯向上彎曲,表明有較多的節(jié)點具有較大的節(jié)點度,這個節(jié)點度就是網(wǎng)絡限制的最大節(jié)點度10。

3.2 網(wǎng)絡效率

(14)

其中,N為網(wǎng)絡節(jié)點數(shù)。特別的當dij=∞時,即節(jié)點i和j之間沒有鏈路連接時,εij=0。

仿真分析了初始條件為m0=4,e0=6,新增節(jié)點連接數(shù)m分別為1、2、3和4條件下,網(wǎng)絡節(jié)點接入限制數(shù)變化情況下,網(wǎng)絡效率變化情況如圖3所示。從圖中可以看出:

1)網(wǎng)絡效率隨著網(wǎng)絡節(jié)點接入限制數(shù)的增大而呈現(xiàn)緩慢增大趨勢,說明網(wǎng)絡節(jié)點接入限制數(shù)增加,網(wǎng)絡中節(jié)點度大的節(jié)點增多,更多的鏈路通過這些節(jié)點進行傳輸,使得網(wǎng)絡效率增加。

2)網(wǎng)絡效率隨著新增加節(jié)點的連接數(shù)的增加而顯著增加,說明網(wǎng)絡節(jié)點的連接度是影響網(wǎng)絡效率的重要條件。

圖3 網(wǎng)絡效率與網(wǎng)絡節(jié)點接入限制數(shù)關系

4 結束語

本文針對無線通信網(wǎng)網(wǎng)絡的特點,網(wǎng)絡節(jié)點接入能力限制,對網(wǎng)絡增長和擇優(yōu)連接進行改進,建立了基于節(jié)點度約束的無線通信網(wǎng)拓撲模型,并開展了仿真驗證。仿真結果表明:模型生成的網(wǎng)絡具有小世界特性和近似冪律分布,能夠充分體現(xiàn)無線通信網(wǎng)的拓撲結構特性。

[1] 熊金石,李建華,楊迎輝.軍事通信網(wǎng)絡結構復雜性實證分析[J].軍事運籌與系統(tǒng)工程,2012,26(2):77-80.

[2] 邢寧哲.電力光纖通信網(wǎng)的復雜網(wǎng)絡特性實證分析[J].光通信技術,2014,38(3):1-4.

[3] 梅丹,王公寶,胡偉文,等.艦船通信網(wǎng)絡結構復雜性實證分析[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] 閔雪嬌,慕曉冬,張娟.戰(zhàn)術互聯(lián)網(wǎng)網(wǎng)絡拓撲模型的研究[J].計算機技術與發(fā)展,2007,17(7): 108-109+113.

[8] 張明科,陳政,于長軍,等.網(wǎng)絡化戰(zhàn)爭中的復雜網(wǎng)絡拓撲建模[J].航天控制,2007,25(4):3-6+12.

[9] 李俊,呂欣,譚躍進.基于空間結構的戰(zhàn)術通信網(wǎng)絡建模[J].系統(tǒng)工程與電子技術,2010,32(7):1456-1461.

[10] 梁廣民,邵丹.基于屬性演化和空間影響的路由級拓撲建模[J].計算機工程,2012,38(2):106-108.

[11] 葉禮邦,王滿喜,張玉靈,等.基于多連接方式的無線通信網(wǎng)絡拓撲模型研究[J].現(xiàn)代電子技術,2016,39(7):1-4.

[12] 吳朔桐,馬天旭.多約束的戰(zhàn)術互聯(lián)網(wǎng)拓撲模型研究[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-),男,江西贛州人,碩士,工程師,研究方向為通信和通信系統(tǒng)試驗技術。