艦船通信網絡結構復雜性實證分析?

梅 丹 王公寶 胡偉文 張建軍

（海軍工程大學應用數學系 武漢 430033）

1 引言

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

2 復雜網絡理論

2.1 復雜系統網絡模型

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

2.2 復雜網絡的特征參數

對于一個無向無權網絡G＝（V，E），其中V表示節點的集合，E表示邊的集合。經典復雜網絡理論中定義了以下四個重要參數［5］來描述網絡特性：

1）平均路徑長度L

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

它是以邊長作為長度單位進行度量的拓撲距離。路徑長度的分布是所有節點對之間最短路徑的統計分布特性。平均路徑長度是網絡的特征尺度，可以表征網絡的連通性。

2）聚類系數C

復雜網絡具有高度的集團性，網絡的聚類系數C是專門用來衡量網絡節點集聚程度的一個重要參數。在網絡中，每個節點的聚類系數可表示為

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

聚類系數表征了近鄰節點聯系的緊密程度，進一步對所有節點的聚類系數求均值就可以得到網絡的聚類系數：

3）度數及度分布

節點i的度定義為與該節點連接的其他節點的數目，即與節點i關聯的邊的數目，記為ki。

網絡中所有節點的度的平均值稱為網絡的平均度，記為〈k〉。對于一個邊數為M，節點數為N的網絡，其平均度數為〈k〉＝2 M／N。

分析度分布的傳統方法是直接畫出頂點度數的直方圖，這種方法的缺點是直方圖的寬度平滑，會使得落入同一直方內的數據點的值間差異全部喪失。現在使用較多的考察復雜網絡節點度分布的一個可行方法是采用累積分布函數法。這里，定義p（k）表示度數為k的節點個數n（k）占節點總數N的百分比，易知度數概率分布具有完備性：

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

根據隨機網絡理論，復雜網絡的度分布服從二項分布或大N極限下的泊松分布，其特征是網絡中絕大多數節點的度值分布在均值附近，在此意義下，復雜網絡是均質網絡。

4）介數及介數分布

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

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

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

3 艦船通信網絡結構及其拓撲模型

采用復雜網絡理論研究艦船通信系統特性，要將通信網絡簡化為拓撲模型。在這里，各個通信實體簡化為節點；由于通信實體之間存在信息的傳輸與交換，連線代表兩個通信實體之間有直接的通信聯系。圖1為某艦船通信網絡拓撲結構圖，出于保密要求，該圖為經過適當處理后的部分拓撲結構圖。

為了方便計算機進行處理，用鄰接矩陣A對網絡拓撲模型進行表示，A中元素aij規定為：aij＝1，當節點i與j相鄰；aij＝0，當節點i與j不相鄰。

圖1 某艦船通信網絡拓撲結構圖（部分）

4 艦船通信網絡復雜性分析

在Watts和Strogatz關于復雜網絡的小世界現象的研究，以及Barabasi和Albert關于復雜網絡的無標度特性的工作之后，人們對不同領域的大量實際網絡的拓撲特性進行了廣泛的實證性研究，得到了各個領域、各種實際網絡的各項基本統計數據［9］。如社會領域中電子郵件網絡的平均路徑長度L＝2.0，聚類系數C＝0.16；信息領域 WWW（nd.edu）網絡的平均路徑長度L＝2.4，聚類系數C＝0.29。這兩種網絡具有類似于規則網絡的較高聚類系數和類似于隨機網絡的較小平均路徑長度，即小世界特性。

由式（1）和式（2）可以計算出某艦船通信網絡的平均路徑長度L＝2.4318和聚類系數C＝0.1934。通過與電子郵件網絡和信息領域網絡的平均路徑長度值和聚類系數值進行比較，發現某艦船信息化網絡的統計數據與上述兩種網絡的數據接近。進一步驗證了某艦船通信網絡也具有小世界特性。可以看到，某艦船通信網絡具有較短的平均路徑長度，說明網絡中信息的流動比較順利。這也使得軍事網絡為各作戰單元提供迅速、準確、有效的通信支撐。

通過計算，上述某艦船通信網絡節點的度分布如圖2所示。在這里，節點的度即為通信實體直接進行信息交換的通信實體數目。

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

圖2 某艦船通信網絡節點度分布

圖3 某艦船通信網絡節點介數

5 結語

本文首先介紹了復雜網絡理論，重點闡述了復雜網絡的四個度量參數：平均路徑長度、聚類系數、度數、介數；然后將某艦船通信網絡的拓撲結構進行了抽象表示，并用鄰接矩陣表示了各通信實體之間的通信聯絡關系；最后通過仿真計算了該通信網的各項基本參數。計算結果表明，某艦船通信網絡具有復雜網絡的小世界特性。復雜網絡提供了一種全新的視角，幫助我們從整體上把握軍事通信網絡的復雜性，更好地認識其拓撲結構及相應的動力學特征。

［1］李德毅，王新政，胡剛鋒.網絡化戰爭與復雜網絡［J］.中國軍事科學，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］汪小帆.復雜網絡理論及其應用［M］.北京：清華大學出版社，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.