艦船通信網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性實證分析?

梅 丹 王公寶 胡偉文 張建軍

（海軍工程大學(xué)應(yīng)用數(shù)學(xué)系 武漢 430033）

1 引言

艦船通信網(wǎng)絡(luò)是為保障作戰(zhàn)指揮、武器控制、協(xié)同動作、后方勤務(wù)、警報和情報報知、裝備保障等信息的傳輸與交換而建立的網(wǎng)絡(luò)體系，是信息系統(tǒng)的重要組成部分［1］。艦船通信網(wǎng)絡(luò)日趨呈現(xiàn)復(fù)雜性的特點，對其進(jìn)行研究是否可以采取復(fù)雜網(wǎng)絡(luò)的研究思路呢？由此而生成的網(wǎng)絡(luò)結(jié)構(gòu)模型是否符合復(fù)雜網(wǎng)絡(luò)的基本特征？復(fù)雜性特征對現(xiàn)實艦船通信系統(tǒng)建設(shè)又有何幫助？本文針對上述問題，從復(fù)雜網(wǎng)絡(luò)角度出發(fā)，用鄰接矩陣表示某艦船通信網(wǎng)絡(luò)拓?fù)淠Ｐ?，并仿真計算了該網(wǎng)絡(luò)的平均路徑長度、聚類系數(shù)等統(tǒng)計特性指標(biāo)，驗證了該通信網(wǎng)絡(luò)的小世界特性。該結(jié)論為將復(fù)雜網(wǎng)絡(luò)的研究成果運用到未來軍事系統(tǒng)建設(shè)中提供了積極的理論啟示和參考價值。

2 復(fù)雜網(wǎng)絡(luò)理論

2.1 復(fù)雜系統(tǒng)網(wǎng)絡(luò)模型

現(xiàn)實世界中大多數(shù)復(fù)雜系統(tǒng)可以用網(wǎng)絡(luò)模型來描述，例如規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)［2］。規(guī)則網(wǎng)絡(luò)所能描述的系統(tǒng)范圍極其有限；隨機(jī)網(wǎng)絡(luò)的隨機(jī)性十分符合真實網(wǎng)絡(luò)中連接的某些特性，但是對動態(tài)演化系統(tǒng)所表示出來的一些特性卻無法予以說明。1998年，Watts和Strogatz通過以某個很小的概率p切斷規(guī)則網(wǎng)絡(luò)中原始的邊，并隨機(jī)選擇新的節(jié)點重新連接，構(gòu)造出一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò)［3］。小世界網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一種重要模型。此外，復(fù)雜網(wǎng)絡(luò)模型還包括無標(biāo)度網(wǎng)絡(luò)、局部演化網(wǎng)絡(luò)等。關(guān)于復(fù)雜網(wǎng)絡(luò)更為詳細(xì)的描述參見文獻(xiàn)［4］。

2.2 復(fù)雜網(wǎng)絡(luò)的特征參數(shù)

對于一個無向無權(quán)網(wǎng)絡(luò)G＝（V，E），其中V表示節(jié)點的集合，E表示邊的集合。經(jīng)典復(fù)雜網(wǎng)絡(luò)理論中定義了以下四個重要參數(shù)［5］來描述網(wǎng)絡(luò)特性：

1）平均路徑長度L

在一個網(wǎng)絡(luò)中，兩個節(jié)點i、j間的最短距離dij定義為連接這兩個節(jié)點的最短路徑上的邊數(shù)。對所有節(jié)點對的最短距離求平均值，就得到了該網(wǎng)絡(luò)的平均路徑長度：

它是以邊長作為長度單位進(jìn)行度量的拓?fù)渚嚯x。路徑長度的分布是所有節(jié)點對之間最短路徑的統(tǒng)計分布特性。平均路徑長度是網(wǎng)絡(luò)的特征尺度，可以表征網(wǎng)絡(luò)的連通性。

2）聚類系數(shù)C

復(fù)雜網(wǎng)絡(luò)具有高度的集團(tuán)性，網(wǎng)絡(luò)的聚類系數(shù)C是專門用來衡量網(wǎng)絡(luò)節(jié)點集聚程度的一個重要參數(shù)。在網(wǎng)絡(luò)中，每個節(jié)點的聚類系數(shù)可表示為

式中，ai為連接節(jié)點i的三角形的個數(shù)，bi為連接節(jié)點i的三元組的個數(shù)。比較直觀的定義方法為：假設(shè)節(jié)點i有ki個近鄰節(jié)點，則ki個近鄰節(jié)點之間至多存在ki（ki－1）／2條邊，而ki個近鄰節(jié)點之間實際存在ti條邊，則節(jié)點i的聚類系數(shù)為

聚類系數(shù)表征了近鄰節(jié)點聯(lián)系的緊密程度，進(jìn)一步對所有節(jié)點的聚類系數(shù)求均值就可以得到網(wǎng)絡(luò)的聚類系數(shù)：

3）度數(shù)及度分布

節(jié)點i的度定義為與該節(jié)點連接的其他節(jié)點的數(shù)目，即與節(jié)點i關(guān)聯(lián)的邊的數(shù)目，記為ki。

網(wǎng)絡(luò)中所有節(jié)點的度的平均值稱為網(wǎng)絡(luò)的平均度，記為〈k〉。對于一個邊數(shù)為M，節(jié)點數(shù)為N的網(wǎng)絡(luò)，其平均度數(shù)為〈k〉＝2 M／N。

分析度分布的傳統(tǒng)方法是直接畫出頂點度數(shù)的直方圖，這種方法的缺點是直方圖的寬度平滑，會使得落入同一直方內(nèi)的數(shù)據(jù)點的值間差異全部喪失?，F(xiàn)在使用較多的考察復(fù)雜網(wǎng)絡(luò)節(jié)點度分布的一個可行方法是采用累積分布函數(shù)法。這里，定義p（k）表示度數(shù)為k的節(jié)點個數(shù)n（k）占節(jié)點總數(shù)N的百分比，易知度數(shù)概率分布具有完備性：

其中，kmin和kmax分別表示網(wǎng)絡(luò)中節(jié)點度數(shù)的最小值和最大值。同時定義節(jié)點度數(shù)累積分布函數(shù)（Cumulative Degree Distribution Function）Pc（k），用P（k≥K）表示度不小于K的節(jié)點的概率分布，常數(shù)K∈［kmin，kmax］，則節(jié)點度數(shù)的累積概率就可以表示為

根據(jù)隨機(jī)網(wǎng)絡(luò)理論，復(fù)雜網(wǎng)絡(luò)的度分布服從二項分布或大N極限下的泊松分布，其特征是網(wǎng)絡(luò)中絕大多數(shù)節(jié)點的度值分布在均值附近，在此意義下，復(fù)雜網(wǎng)絡(luò)是均質(zhì)網(wǎng)絡(luò)。

4）介數(shù)及介數(shù)分布

Holme和Kim在研究網(wǎng)絡(luò)演化所導(dǎo)致的過負(fù)荷時，假設(shè)網(wǎng)絡(luò)中任意兩節(jié)點之間信息或能量的交換都通過最短路徑進(jìn)行，選擇用介向中心性（Betweennes Centrality）來評估網(wǎng)絡(luò)中的節(jié)點和邊的網(wǎng)絡(luò)流量［6～8］，其后介向中心性也被簡單地稱為介數(shù)（betweenness）。節(jié)點v的介數(shù)B（v）和邊e的介數(shù)B（e）表達(dá)式類似，可分別定義為

式中，對于w≠w′且w，w′≠v的所有節(jié)點對，σww′為節(jié)點w、w′之間的最短路徑數(shù)目，σww′（v）為 w、w′之間經(jīng)過v的最短路徑數(shù)目；σvw（e）為節(jié)點v、w之間包含邊e的最短路徑數(shù)目，σvw為節(jié)點v、w之間的最短路徑數(shù)目。

定義節(jié)點（邊）介數(shù)累積分布函數(shù)（Cumulative Betweenness Distribution Function）為 Pc（B），用P（B≥B′）表示介數(shù)不小于B′的節(jié)點（邊）的概率分布，Bmax表示網(wǎng)絡(luò)中節(jié)點（邊）介數(shù)的最大值，常數(shù)B′∈［Bmin，Bmax］，節(jié)點（邊）介數(shù)的累積概率就可表示為

3 艦船通信網(wǎng)絡(luò)結(jié)構(gòu)及其拓?fù)淠Ｐ?/h2>

采用復(fù)雜網(wǎng)絡(luò)理論研究艦船通信系統(tǒng)特性，要將通信網(wǎng)絡(luò)簡化為拓?fù)淠Ｐ?。在這里，各個通信實體簡化為節(jié)點；由于通信實體之間存在信息的傳輸與交換，連線代表兩個通信實體之間有直接的通信聯(lián)系。圖1為某艦船通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，出于保密要求，該圖為經(jīng)過適當(dāng)處理后的部分拓?fù)浣Y(jié)構(gòu)圖。

為了方便計算機(jī)進(jìn)行處理，用鄰接矩陣A對網(wǎng)絡(luò)拓?fù)淠Ｐ瓦M(jìn)行表示，A中元素aij規(guī)定為：aij＝1，當(dāng)節(jié)點i與j相鄰；aij＝0，當(dāng)節(jié)點i與j不相鄰。

圖1 某艦船通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖（部分）

4 艦船通信網(wǎng)絡(luò)復(fù)雜性分析

在Watts和Strogatz關(guān)于復(fù)雜網(wǎng)絡(luò)的小世界現(xiàn)象的研究，以及Barabasi和Albert關(guān)于復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性的工作之后，人們對不同領(lǐng)域的大量實際網(wǎng)絡(luò)的拓?fù)涮匦赃M(jìn)行了廣泛的實證性研究，得到了各個領(lǐng)域、各種實際網(wǎng)絡(luò)的各項基本統(tǒng)計數(shù)據(jù)［9］。如社會領(lǐng)域中電子郵件網(wǎng)絡(luò)的平均路徑長度L＝2.0，聚類系數(shù)C＝0.16；信息領(lǐng)域 WWW（nd.edu）網(wǎng)絡(luò)的平均路徑長度L＝2.4，聚類系數(shù)C＝0.29。這兩種網(wǎng)絡(luò)具有類似于規(guī)則網(wǎng)絡(luò)的較高聚類系數(shù)和類似于隨機(jī)網(wǎng)絡(luò)的較小平均路徑長度，即小世界特性。

由式（1）和式（2）可以計算出某艦船通信網(wǎng)絡(luò)的平均路徑長度L＝2.4318和聚類系數(shù)C＝0.1934。通過與電子郵件網(wǎng)絡(luò)和信息領(lǐng)域網(wǎng)絡(luò)的平均路徑長度值和聚類系數(shù)值進(jìn)行比較，發(fā)現(xiàn)某艦船信息化網(wǎng)絡(luò)的統(tǒng)計數(shù)據(jù)與上述兩種網(wǎng)絡(luò)的數(shù)據(jù)接近。進(jìn)一步驗證了某艦船通信網(wǎng)絡(luò)也具有小世界特性?？梢钥吹?，某艦船通信網(wǎng)絡(luò)具有較短的平均路徑長度，說明網(wǎng)絡(luò)中信息的流動比較順利。這也使得軍事網(wǎng)絡(luò)為各作戰(zhàn)單元提供迅速、準(zhǔn)確、有效的通信支撐。

通過計算，上述某艦船通信網(wǎng)絡(luò)節(jié)點的度分布如圖2所示。在這里，節(jié)點的度即為通信實體直接進(jìn)行信息交換的通信實體數(shù)目。

由圖2可見，第14號節(jié)點的度為4，在整個網(wǎng)絡(luò)中最大。這意味著該節(jié)點與其他節(jié)點的聯(lián)系比較緊密，十分重要。也就是說該節(jié)點受到攻擊或者損害會造成網(wǎng)絡(luò)的級聯(lián)故障，甚至造成整個網(wǎng)絡(luò)的癱瘓［10］。通信節(jié)點的重要性還可以從介數(shù)指標(biāo)上得到驗證。如圖3所示，14號節(jié)點的介數(shù)最大。節(jié)點的介數(shù)值越高，說明該節(jié)點的影響力越大，地位也越重要。

圖2 某艦船通信網(wǎng)絡(luò)節(jié)點度分布

圖3 某艦船通信網(wǎng)絡(luò)節(jié)點介數(shù)

5 結(jié)語

本文首先介紹了復(fù)雜網(wǎng)絡(luò)理論，重點闡述了復(fù)雜網(wǎng)絡(luò)的四個度量參數(shù)：平均路徑長度、聚類系數(shù)、度數(shù)、介數(shù)；然后將某艦船通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了抽象表示，并用鄰接矩陣表示了各通信實體之間的通信聯(lián)絡(luò)關(guān)系；最后通過仿真計算了該通信網(wǎng)的各項基本參數(shù)。計算結(jié)果表明，某艦船通信網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的小世界特性。復(fù)雜網(wǎng)絡(luò)提供了一種全新的視角，幫助我們從整體上把握軍事通信網(wǎng)絡(luò)的復(fù)雜性，更好地認(rèn)識其拓?fù)浣Y(jié)構(gòu)及相應(yīng)的動力學(xué)特征。

［1］李德毅，王新政，胡剛鋒.網(wǎng)絡(luò)化戰(zhàn)爭與復(fù)雜網(wǎng)絡(luò)［J］.中國軍事科學(xué)，2006，19（3）：111－119.

［2］Erdos P，Renyi A L.On the evolution of random graphs.Publ［J］.Math.Inst.Hung.Acad.Sci.，1960，5：17－60.

［3］Watts D J，Strogatz S H.Collective dynamics of‘small－world’networks［J］.Nature，1998，393（6684）：440－442.

［4］Albert R，Barabasi A L.Statistical mechanics of complex networks［J］.Review of Modern Physics，2002，74（1）：47－97.

［5］汪小帆.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［6］Holme P.Edge overload breakdown in evolving networks［J］.Physical Review E，2002，66（2）：036119.

［7］Holme P，Kim B J.Vertex breakdown in evolving networks［J］.Physical Review E，2002，65（1）：066109.

［8］Holme P，Kim B J，et al.Attack vulnerability of complex networks［J］.Physical Review E，2002，65（1）：056109.

［9］Newman M E J.The structure and Function of Com－plex Networks［J］.SIAM Review，2003（45）：167－256.

［10］Crucitti P，Latora V，Marchiori M.Model for cascading failures in complex networks［J］.Physics Review E，2004（69）：045104.