葉禮邦,郭新海,齊偉偉
(中國(guó)洛陽(yáng)電子裝備試驗(yàn)中心,河南 洛陽(yáng) 471003)
基于節(jié)點(diǎn)度約束的無(wú)線通信網(wǎng)拓?fù)淠P?/p>
葉禮邦,郭新海,齊偉偉
(中國(guó)洛陽(yáng)電子裝備試驗(yàn)中心,河南 洛陽(yáng) 471003)
為了解決無(wú)線通信網(wǎng)拓?fù)淠P蜕蓡?wèn)題,分析了現(xiàn)有網(wǎng)絡(luò)拓?fù)淠P偷牟蛔?結(jié)合無(wú)線通信網(wǎng)的特點(diǎn),提出了一種基于最大度約束的無(wú)線通信網(wǎng)拓?fù)溲莼P?。研究了網(wǎng)絡(luò)拓?fù)淠P偷难莼绞胶退惴ú襟E,解析計(jì)算了模型的度分布。對(duì)網(wǎng)絡(luò)的度分布和網(wǎng)絡(luò)效率等網(wǎng)絡(luò)特性進(jìn)行了仿真分析,仿真結(jié)果表明:模型生成的網(wǎng)絡(luò)具有小世界特性和近似冪律分布,能夠充分體現(xiàn)無(wú)線通信網(wǎng)的拓?fù)浣Y(jié)構(gòu)特性。
無(wú)線通信網(wǎng);復(fù)雜網(wǎng)絡(luò);拓?fù)淠P?節(jié)點(diǎn)度;連接模式
郭新海(1981-),男,碩士,工程師。
齊偉偉(1986-),男,碩士,工程師。
無(wú)線通信網(wǎng)絡(luò)的應(yīng)用范圍廣泛,結(jié)構(gòu)復(fù)雜,其拓?fù)浣Y(jié)構(gòu)是影響無(wú)線通信網(wǎng)網(wǎng)絡(luò)性能的關(guān)鍵因素。建立無(wú)線通信網(wǎng)絡(luò)的拓?fù)淠P?在此基礎(chǔ)上通過(guò)仿真試驗(yàn)方式,對(duì)網(wǎng)絡(luò)性能、網(wǎng)絡(luò)協(xié)議進(jìn)行分析,開(kāi)展網(wǎng)絡(luò)結(jié)構(gòu)改進(jìn)和方案優(yōu)化研究,可以促進(jìn)網(wǎng)絡(luò)性能的提升。因此,建立真實(shí)反映網(wǎng)絡(luò)結(jié)構(gòu)特性的網(wǎng)絡(luò)拓?fù)淠P鸵恢笔菬o(wú)線通信網(wǎng)絡(luò)研究的熱點(diǎn)。
由于無(wú)線通信網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜,傳統(tǒng)的星形網(wǎng)絡(luò)、環(huán)形網(wǎng)絡(luò)或柵格網(wǎng)絡(luò)無(wú)法真實(shí)反映網(wǎng)絡(luò)結(jié)構(gòu)特性,而隨機(jī)網(wǎng)絡(luò)(如ER隨機(jī)網(wǎng)絡(luò)模型)雖然可以反映一定的網(wǎng)絡(luò)復(fù)雜性,但是并不能體現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)。隨著復(fù)雜網(wǎng)絡(luò)科學(xué)的發(fā)展,大量的研究實(shí)證,通信網(wǎng)絡(luò)結(jié)構(gòu)滿(mǎn)足“無(wú)標(biāo)度”特性,即網(wǎng)絡(luò)節(jié)點(diǎn)的度分布服從“冪律”分布[1-3]。目前,現(xiàn)有的研究提出了許多滿(mǎn)足冪律分布的網(wǎng)絡(luò)模型,其中最著名的是Balabasi等提出的BA模型[4]。BA模型采用網(wǎng)絡(luò)增長(zhǎng)和擇優(yōu)連接方式,演化出符合冪律分布的網(wǎng)絡(luò)。針對(duì)網(wǎng)絡(luò)的某些特性,在BA模型的基礎(chǔ)上,許多具有特定約束條件的網(wǎng)絡(luò)拓?fù)淠P拖嗬^被提出,如考慮局域世界的“陳-李模型”,該模型新增加的節(jié)點(diǎn)偏好選擇局域世界內(nèi)的節(jié)點(diǎn)建立連接[5];同時(shí)還有兼顧全局和局域世界連接的演化模型,在演化過(guò)程中,新增加的節(jié)點(diǎn)按照概率p按度優(yōu)先連接,按概率(1-p)連接到最近的節(jié)點(diǎn)[6]。
復(fù)雜網(wǎng)絡(luò)理論提出后,很快應(yīng)用到了無(wú)線通信網(wǎng)絡(luò)的拓?fù)浣V?并結(jié)合無(wú)線通信網(wǎng)絡(luò)特性,研究出不同的網(wǎng)絡(luò)拓?fù)淠P?。包括考慮網(wǎng)絡(luò)有線和無(wú)線傳輸條件[7],網(wǎng)絡(luò)節(jié)點(diǎn)的分類(lèi)和連接規(guī)則[8],網(wǎng)絡(luò)的節(jié)點(diǎn)類(lèi)型[9],網(wǎng)絡(luò)的空間特性和鏈路連接特性[10-11],以及網(wǎng)絡(luò)的節(jié)點(diǎn)和鏈路的不同特性[12],分別建立了相應(yīng)的網(wǎng)絡(luò)拓?fù)淠P?并開(kāi)展了試驗(yàn)驗(yàn)證,大大促進(jìn)了復(fù)雜網(wǎng)絡(luò)技術(shù)在無(wú)線通信網(wǎng)建模上的應(yīng)用。網(wǎng)絡(luò)拓?fù)浣jP(guān)鍵是要分析網(wǎng)絡(luò)拓?fù)涮匦?然后根據(jù)網(wǎng)絡(luò)拓?fù)涮匦越⑾鄳?yīng)的網(wǎng)絡(luò)模型,從而得出更加符合實(shí)際網(wǎng)絡(luò)或者更體現(xiàn)研究者關(guān)注特征的網(wǎng)絡(luò)拓?fù)淠P?。本文特別針對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的不同接入能力,提出了一種基于節(jié)點(diǎn)度約束的無(wú)線通信網(wǎng)網(wǎng)絡(luò)拓?fù)淠P?并對(duì)網(wǎng)絡(luò)的度分布進(jìn)行了計(jì)算和仿真驗(yàn)證,結(jié)果表明,該模型能夠充分體現(xiàn)無(wú)線通信網(wǎng)絡(luò)的拓?fù)涮匦?為后續(xù)的網(wǎng)絡(luò)性能研究提供了理論支撐。
無(wú)線通信網(wǎng)絡(luò)的通信節(jié)點(diǎn)包括各類(lèi)無(wú)線接收設(shè)備,這些節(jié)點(diǎn)相互連接,構(gòu)成一個(gè)多手段、多層次、立體化的通信網(wǎng)絡(luò)。但是這些節(jié)點(diǎn)的度有一個(gè)最大的接入能力,下面根據(jù)這一特點(diǎn),建立具有節(jié)點(diǎn)度約束條件下的網(wǎng)絡(luò)拓?fù)淠P汀?/p>
1.1 模型設(shè)置
BA模型隨著時(shí)間的增長(zhǎng),某些點(diǎn)的度也在不斷增長(zhǎng),體現(xiàn)馬太效應(yīng),即“富者愈富”,這是BA模型體現(xiàn)的一種現(xiàn)象,對(duì)于一些網(wǎng)絡(luò),可能會(huì)出現(xiàn)這種現(xiàn)象。但對(duì)于無(wú)線通信網(wǎng)來(lái)說(shuō),一個(gè)節(jié)點(diǎn)的連接數(shù)受到設(shè)備和空間的限制,不可無(wú)限制的增長(zhǎng)。這一特性說(shuō)明無(wú)線通信網(wǎng)的網(wǎng)絡(luò)節(jié)點(diǎn)度增長(zhǎng)到一定程度后,增長(zhǎng)趨勢(shì)會(huì)趨于緩慢,甚至零增長(zhǎng)。這種特征是BA模型不能模擬的,因此我們引進(jìn)新的參數(shù):節(jié)點(diǎn)接入限制數(shù)kmax,對(duì)BA模型的擇優(yōu)選擇概率進(jìn)行改進(jìn)。擴(kuò)展模型的演化方式如下:
1)增長(zhǎng):初始網(wǎng)絡(luò)有m0個(gè)節(jié)點(diǎn)與e0條邊,在每一時(shí)間步增加一個(gè)新的節(jié)點(diǎn),同時(shí)這個(gè)新節(jié)點(diǎn)連接到網(wǎng)絡(luò)中m(m≤m0)個(gè)已經(jīng)存在的節(jié)點(diǎn)上。
2)傾向性選擇:一個(gè)新的節(jié)點(diǎn)選擇連接節(jié)點(diǎn)仍然是有偏好的,但它選擇某個(gè)節(jié)點(diǎn)i的概率∏(ki)與節(jié)點(diǎn)的度不再成正比,因此,將模型的選擇概率乘以一個(gè)與網(wǎng)絡(luò)節(jié)點(diǎn)度和最大接入限制數(shù)kmax有關(guān)的因子β(ki),即
(1)
為了控制網(wǎng)絡(luò)節(jié)點(diǎn)度的增長(zhǎng),β(ki)是單調(diào)遞減函數(shù),且當(dāng)ki=0時(shí),β(ki)=1;ki=kmax時(shí),β(ki)=0,滿(mǎn)足上述規(guī)則的函數(shù)有很多,為了推導(dǎo)方便,這里將β(ki)取為一種直線遞減型函數(shù)
(2)
按此偏好連接概率進(jìn)行連接,當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度都遠(yuǎn)遠(yuǎn)小于kmax時(shí),β(ki)≈1,此時(shí),模型等價(jià)于BA模型。當(dāng)ki增大并趨近最大度kmax時(shí),β(ki)取值逐漸減小,此時(shí)就可以控制節(jié)點(diǎn)i的度數(shù)增長(zhǎng),使其增長(zhǎng)到一定的度數(shù)就呈現(xiàn)零增長(zhǎng)。
1.2 算法步驟
步驟1:初始狀態(tài)。網(wǎng)絡(luò)初始有m0個(gè)節(jié)點(diǎn)和e0條邊,m0均勻分布于L×L的平面上,并設(shè)定網(wǎng)絡(luò)e0條邊連接關(guān)系。
步驟2:節(jié)點(diǎn)增加。每次新加入1個(gè)節(jié)點(diǎn),新加點(diǎn)的位置在L×L的平面上服從均勻分布。
步驟3:按概率優(yōu)先連接m條邊。連接過(guò)程如下:
1)按照公式(1)計(jì)算各節(jié)點(diǎn)的連接概率;
2)在現(xiàn)有節(jié)點(diǎn)中按照概率選擇m個(gè)節(jié)點(diǎn),新增加節(jié)點(diǎn)與所選擇的m個(gè)現(xiàn)有節(jié)點(diǎn)相連。
步驟4:重復(fù)步驟2和步驟3,直到產(chǎn)生N個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。
令網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)的度ki為一個(gè)連續(xù)的實(shí)變量,則ki的變化率與∏(ki)成正比。因此,ki應(yīng)滿(mǎn)足下面的動(dòng)態(tài)方程:
(3)
其中,β(ki)為網(wǎng)絡(luò)節(jié)點(diǎn)連接因子,是節(jié)點(diǎn)度的函數(shù),如式(2)所示;kj為第j(1≤j≤m) 個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度。
假設(shè)網(wǎng)絡(luò)中只有少數(shù)點(diǎn)的度數(shù)接近甚至等于kmax,大部分節(jié)點(diǎn)的度還是比較低。為了簡(jiǎn)化后面的分析過(guò)程,不妨作下面的平均假設(shè):
(4)
(5)
將式(5)代入式(4)得到
(6)
將式(6)代入式(3),可以得到
(7)
每個(gè)時(shí)間步加一個(gè)新節(jié)點(diǎn)i,增加m度,因此初始條件ki(ti)=m,于是得到
(8)
當(dāng)t→∞時(shí),某些少數(shù)點(diǎn)的度數(shù)接近于kmax,顯然符合我們的模擬結(jié)果。
由式(8)可以得出節(jié)點(diǎn)連接度ki小于某一定指k的概率為
(9)
假設(shè)是以相等時(shí)間間隔增加節(jié)點(diǎn),那么ti的概率密度函數(shù)為
(10)
將式(10)代入式(9)可以得到
(11)
所有模型度值的分布函數(shù)p(k)為
(12)
當(dāng)t→∞時(shí),式(12)可以簡(jiǎn)化為
(13)
由式(13)可見(jiàn),模型的度分布并不是服從冪律分布,只有當(dāng)kmax?m時(shí),式(13)的第2項(xiàng)可以忽略,此時(shí)網(wǎng)絡(luò)的度分布接近冪律分布p(k)∝k-3。
按照上述的模型設(shè)置,通過(guò)仿真試驗(yàn)方式產(chǎn)生網(wǎng)絡(luò)拓?fù)淠P?并分析網(wǎng)絡(luò)拓?fù)湫阅?。在仿真?500個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在100km×100km 的范圍內(nèi),m0=4,e0=6,新加入節(jié)點(diǎn)的連接邊數(shù)為m=2,分別設(shè)置網(wǎng)絡(luò)的節(jié)點(diǎn)接入限制數(shù)為50、30和10,產(chǎn)生3個(gè)網(wǎng)絡(luò)模型,并對(duì)3個(gè)網(wǎng)絡(luò)模型的特性進(jìn)行分析。
3.1 度分布特性
為了分析不同節(jié)點(diǎn)接入限制數(shù)的情況,對(duì)上述仿真的3種模型的度分布進(jìn)行分析,不同網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)度分布對(duì)比如圖1所示。
圖1 不同節(jié)點(diǎn)接入限制數(shù)度分布
從圖1中可以看出:當(dāng)網(wǎng)絡(luò)中最大接入限制數(shù)為50和30時(shí),由于網(wǎng)絡(luò)節(jié)點(diǎn)并未達(dá)到其限制連接的最大值,因此,網(wǎng)絡(luò)的節(jié)點(diǎn)度分布情況基本一致。當(dāng)最大節(jié)點(diǎn)限制數(shù)為10時(shí),大量的節(jié)點(diǎn)達(dá)到最大節(jié)點(diǎn)限制數(shù),使得節(jié)點(diǎn)度為5-10的節(jié)點(diǎn)大幅增加。
圖2 不同節(jié)點(diǎn)接入限制數(shù)度概率分布
從圖2可以看出,網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)為50時(shí),網(wǎng)絡(luò)的度分布曲線(對(duì)數(shù))還基本保持為直線,而當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)為10時(shí),網(wǎng)絡(luò)的度分布曲線(對(duì)數(shù))明顯在下降后明顯向上彎曲,表明有較多的節(jié)點(diǎn)具有較大的節(jié)點(diǎn)度,這個(gè)節(jié)點(diǎn)度就是網(wǎng)絡(luò)限制的最大節(jié)點(diǎn)度10。
3.2 網(wǎng)絡(luò)效率
(14)
其中,N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。特別的當(dāng)dij=∞時(shí),即節(jié)點(diǎn)i和j之間沒(méi)有鏈路連接時(shí),εij=0。
仿真分析了初始條件為m0=4,e0=6,新增節(jié)點(diǎn)連接數(shù)m分別為1、2、3和4條件下,網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)變化情況下,網(wǎng)絡(luò)效率變化情況如圖3所示。從圖中可以看出:
1)網(wǎng)絡(luò)效率隨著網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)的增大而呈現(xiàn)緩慢增大趨勢(shì),說(shuō)明網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)增加,網(wǎng)絡(luò)中節(jié)點(diǎn)度大的節(jié)點(diǎn)增多,更多的鏈路通過(guò)這些節(jié)點(diǎn)進(jìn)行傳輸,使得網(wǎng)絡(luò)效率增加。
2)網(wǎng)絡(luò)效率隨著新增加節(jié)點(diǎn)的連接數(shù)的增加而顯著增加,說(shuō)明網(wǎng)絡(luò)節(jié)點(diǎn)的連接度是影響網(wǎng)絡(luò)效率的重要條件。
圖3 網(wǎng)絡(luò)效率與網(wǎng)絡(luò)節(jié)點(diǎn)接入限制數(shù)關(guān)系
本文針對(duì)無(wú)線通信網(wǎng)網(wǎng)絡(luò)的特點(diǎn),網(wǎng)絡(luò)節(jié)點(diǎn)接入能力限制,對(duì)網(wǎng)絡(luò)增長(zhǎng)和擇優(yōu)連接進(jìn)行改進(jìn),建立了基于節(jié)點(diǎn)度約束的無(wú)線通信網(wǎng)拓?fù)淠P?并開(kāi)展了仿真驗(yàn)證。仿真結(jié)果表明:模型生成的網(wǎng)絡(luò)具有小世界特性和近似冪律分布,能夠充分體現(xiàn)無(wú)線通信網(wǎng)的拓?fù)浣Y(jié)構(gòu)特性。
[1] 熊金石,李建華,楊迎輝.軍事通信網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性實(shí)證分析[J].軍事運(yùn)籌與系統(tǒng)工程,2012,26(2):77-80.
[2] 邢寧哲.電力光纖通信網(wǎng)的復(fù)雜網(wǎng)絡(luò)特性實(shí)證分析[J].光通信技術(shù),2014,38(3):1-4.
[3] 梅丹,王公寶,胡偉文,等.艦船通信網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性實(shí)證分析[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)術(shù)互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)淠P偷难芯縖J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(7): 108-109+113.
[8] 張明科,陳政,于長(zhǎng)軍,等.網(wǎng)絡(luò)化戰(zhàn)爭(zhēng)中的復(fù)雜網(wǎng)絡(luò)拓?fù)浣J].航天控制,2007,25(4):3-6+12.
[9] 李俊,呂欣,譚躍進(jìn).基于空間結(jié)構(gòu)的戰(zhàn)術(shù)通信網(wǎng)絡(luò)建模[J].系統(tǒng)工程與電子技術(shù),2010,32(7):1456-1461.
[10] 梁廣民,邵丹.基于屬性演化和空間影響的路由級(jí)拓?fù)浣J].計(jì)算機(jī)工程,2012,38(2):106-108.
[11] 葉禮邦,王滿(mǎn)喜,張玉靈,等.基于多連接方式的無(wú)線通信網(wǎng)絡(luò)拓?fù)淠P脱芯縖J].現(xiàn)代電子技術(shù),2016,39(7):1-4.
[12] 吳朔桐,馬天旭.多約束的戰(zhàn)術(shù)互聯(lián)網(wǎng)拓?fù)淠P脱芯縖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-),男,江西贛州人,碩士,工程師,研究方向?yàn)橥ㄐ藕屯ㄐ畔到y(tǒng)試驗(yàn)技術(shù)。