基于復(fù)雜網(wǎng)絡(luò)的車載自組網(wǎng)拓撲特性分析

周貝貝，周鵬

（湖北汽車工業(yè)學(xué)院 電氣與信息工程學(xué)院，湖北 十堰442002）

車載自組網(wǎng)（vehicular ad hoc network，VANET）是以實現(xiàn)車輛間的正常通信為目的、由人工搭建的自組織網(wǎng)絡(luò)［1］。為了實現(xiàn)對交通信息的有效管理和利用，將每輛汽車作為互聯(lián)和通信的信息源接入到互聯(lián)網(wǎng)中，每輛車都為1 個節(jié)點，車輛之間的通信關(guān)系為連邊，在一定范圍內(nèi)的通信關(guān)系構(gòu)成VANET。與傳統(tǒng)的靜態(tài)通信網(wǎng)絡(luò)相比，VANET 具備節(jié)點多樣性，連接多樣性等復(fù)雜網(wǎng)絡(luò)的特征，所以可用復(fù)雜網(wǎng)絡(luò)理論對其網(wǎng)絡(luò)特征進行研究。認識車載自組網(wǎng)的拓撲結(jié)構(gòu)及其演化規(guī)律，從而研究影響VANET 信息傳輸能力的關(guān)鍵特性，是優(yōu)化網(wǎng)絡(luò)路由策略的理論基礎(chǔ)［2］。

目前VANET 拓撲特性是學(xué)者們研究的熱點。張麗麗通過上海市4000多輛出租車的GPS數(shù)據(jù)對VANET 網(wǎng)的一些參數(shù)進行統(tǒng)計分析，發(fā)現(xiàn)VANET網(wǎng)具有無標度特性，同時網(wǎng)絡(luò)的局部和整體均具有較高的聚類特性［3］。高天智結(jié)合圖論和復(fù)雜網(wǎng)絡(luò)理論，得出城市軌道網(wǎng)絡(luò)具有無標度及小世界特性的結(jié)論［4］。黃加增基于復(fù)雜網(wǎng)絡(luò)理論，利用相關(guān)參數(shù)對城市公交網(wǎng)絡(luò)進行了分析，得出城市公交網(wǎng)絡(luò)具有無標度特性的結(jié)論［5］。Zheng 分析了VANET網(wǎng)絡(luò)瞬時拓撲特性，發(fā)現(xiàn)VANET 網(wǎng)不具有無標度特性，而當通信半徑足夠大時，顯示出小世界特性［6］。Zhang 對城市環(huán)境下VANET 的動態(tài)拓撲特性進行了分析，發(fā)現(xiàn)通信半徑是影響網(wǎng)絡(luò)連通性的主要參數(shù)［7］。

網(wǎng)絡(luò)拓撲結(jié)構(gòu)與網(wǎng)絡(luò)通信協(xié)議的設(shè)計密切相關(guān)。韋世紅提出了一種基于小世界網(wǎng)絡(luò)模型的層次型路由算法［8］，熊云艷基于度序列構(gòu)造了復(fù)雜網(wǎng)絡(luò)模型，并在此基礎(chǔ)上對3種路由策略進行了分析對比［9］，基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)和節(jié)點隊列長度，Ling提出了新的全局動態(tài)路由［10］。雖然VANET網(wǎng)拓撲特性分析及通信協(xié)議的研究取得了不少成果，但仍然存在一些亟需解決的難題，比如VANET 是否具有無標度與小世界特性，在什么條件下會具有這些特性。在現(xiàn)有的文獻資料中，關(guān)于這個問題的結(jié)論并不一致,甚至得出的結(jié)論截然相反。

當VANET 具有無標度特性時，在雙對數(shù)坐標下，其度分布的概率密度函數(shù)為一條直線，為檢驗網(wǎng)絡(luò)是否具有無標度特性提供了經(jīng)驗的檢驗方法。目前在對網(wǎng)絡(luò)無標度特性的驗證問題上，許多文獻采用最小二乘法在雙對數(shù)坐標下對網(wǎng)絡(luò)的度分布進行直線擬合，從而計算縮放參數(shù)，但是使用這種方法時往往會產(chǎn)生較大系統(tǒng)誤差［11-12］。主要原因在于，冪律分布屬于肥尾分布，度分布的尾部取值較多且分散，此時采用標準線性回歸方法對度分布進行擬合，會得到幾種不同的解，并且這些解往往較真實參數(shù)偏低。Clauset 等曾將參數(shù)γ的極大似然估計和基于線性回歸的最小二乘估計作比較，發(fā)現(xiàn)極大似然估計遠比最小二乘估計精確［12］。實際應(yīng)用中，最小二乘法在雙對數(shù)坐標下度分布尾部擬合為直線可作為判定冪律分布的必要條件，需采用KS 檢驗和極大似然估計法對VANET 是否具有無標度特性進一步驗證。

文中基于成都滴滴實際數(shù)據(jù)集和實驗仿真數(shù)據(jù)集，分析了城市環(huán)境下VANET的拓撲特性，揭示了網(wǎng)絡(luò)演化的規(guī)律。

1 VANET拓撲特性分析

城市環(huán)境下由車輛之間的通信關(guān)系組成的自組織網(wǎng)絡(luò)是典型的復(fù)雜網(wǎng)絡(luò)，可以借鑒復(fù)雜網(wǎng)絡(luò)理論度分布、平均路徑長度、聚類系數(shù)和連通分支數(shù)。對其進行分析。在刻畫復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計特性時，通常使用度分布、平均路徑長度、聚類系數(shù)和連通分支數(shù)對其進行描述。

1.1 度分布

網(wǎng)絡(luò)中度為x的節(jié)點與網(wǎng)絡(luò)中節(jié)點總數(shù)目的比值即節(jié)點的度分布，常用分布函數(shù)P（x）來描述［13］，即

式中：N為網(wǎng)絡(luò)中節(jié)點的總數(shù)；n（x）為度為x的節(jié)點數(shù)。無標度網(wǎng)絡(luò)的顯著特點是其節(jié)點度服從冪律分布，因此度分布可近似表示為冪函數(shù)：

式中：γ為縮放參數(shù)，取值2～3。節(jié)點連接度沒有明顯特征長度的網(wǎng)絡(luò)，稱為無標度網(wǎng)絡(luò)，在這類網(wǎng)絡(luò)中，大部分節(jié)點的度相對較低，少量節(jié)點的度相對較高，因此又稱為非均勻網(wǎng)絡(luò)，而具有相對很高度的節(jié)點稱為網(wǎng)絡(luò)的“樞紐”［14］。因此可通過判斷網(wǎng)絡(luò)的度分布函數(shù)是否符合冪律形式、縮放參數(shù)是否位于2～3來判定網(wǎng)絡(luò)是否具有無標度特性。

文中采用KS檢驗和極大似然估計來進行縮放參數(shù)的計算。KS統(tǒng)計量即數(shù)據(jù)的分布函數(shù)與擬合模型之間的最大距離［12］：

式中：S（x）為落在區(qū)域x≥xmin上實際數(shù)據(jù)所對應(yīng)的累積分布函數(shù)；P（x）為落在區(qū)域x≥xmin上實際數(shù)據(jù)所擬合的冪律分布函數(shù)；x為度值大??；xmin為冪律下界。使D值達到最小的點即xmin。離散冪律分布其縮放參數(shù)的極大似然估計表示為［12］

式中：xi為節(jié)點i的度值。

圖1為指數(shù)分布在雙對數(shù)坐標下的度分布圖，可以看出，度分布的變化規(guī)律可用直線擬合，在最小二乘法中，網(wǎng)絡(luò)度分布服從冪律分布。利用式（3）～（4）計算得γ為9.9，說明網(wǎng)絡(luò)度分布不服從冪律分布，網(wǎng)絡(luò)不具有無標度特性。因此在雙對數(shù)坐標下，度分布尾部擬合為直線是判定冪律分布的必要條件，而不是充分條件。

圖1 指數(shù)分布y = e-x的對數(shù)擬合圖

1.2 連通分支數(shù)

連通性對網(wǎng)絡(luò)的通信具有至關(guān)重要的作用，當網(wǎng)絡(luò)中出現(xiàn)分區(qū)或其他網(wǎng)絡(luò)整體連通性被破壞的情形，網(wǎng)絡(luò)中消息傳遞的整體覆蓋性會被降低，從而極大影響其通信效率。通常情況下，網(wǎng)絡(luò)連通性能的好壞可以通過連通分支的數(shù)目來反映。

1.3 聚類系數(shù)

網(wǎng)絡(luò)的聚類系數(shù)是網(wǎng)絡(luò)中局部聚集特征的反映。在VANET 中，聚類系數(shù)的數(shù)值往往和網(wǎng)絡(luò)的密集程度以及局域連通性成正比，聚類系數(shù)對通信的可達性和整體網(wǎng)絡(luò)的穩(wěn)定性至關(guān)重要。將1 個節(jié)點的鄰居節(jié)點之間實際存在的連邊數(shù)與網(wǎng)絡(luò)中可能存在的所有連邊總數(shù)的比值定義為此節(jié)點的聚類系數(shù)［13］，即

式中：Ci為節(jié)點i的聚類系數(shù)；xi為節(jié)點i的鄰居節(jié)點的數(shù)量；ti為節(jié)點i的xi個鄰居節(jié)點之間實際存在的連邊數(shù)。

1.4 平均路徑長度

平均路徑長度為網(wǎng)絡(luò)中任意兩節(jié)點間距離的平均值［13］，即

式中：N為網(wǎng)絡(luò)中節(jié)點總數(shù)；dij為節(jié)點i、j之間的最短路徑長度。當1 個網(wǎng)絡(luò)同時具有較大聚類系數(shù)和較小平均路徑長度時，稱該網(wǎng)絡(luò)具有小世界特性。平均路徑長度是從全局角度描述網(wǎng)絡(luò)中任意兩節(jié)點間距離的特征參數(shù)，L越小車輛之間的通信越暢通，VANET 的可通達性越好。檢查1 個網(wǎng)絡(luò)是否為小世界網(wǎng)絡(luò)，可以將L和平均聚類系數(shù)C與相同規(guī)模（具有相同的N和總邊數(shù)K）的隨機圖的值Lrand和Crand進行比較，當L與Lrand為等階量，C遠大于Crand，即計算結(jié)果滿足式（7）時，這個網(wǎng)絡(luò)為小世界網(wǎng)絡(luò)［14］。

式中：Lrand和Crand分別為相同規(guī)模的隨機網(wǎng)絡(luò)的平均路徑長度和聚類系數(shù)。Lrand、Crand、網(wǎng)絡(luò)平均度＜k＞、網(wǎng)絡(luò)節(jié)點數(shù)N有如下關(guān)系：

2 VANET拓撲特性實證研究

基于成都滴滴數(shù)據(jù)集GPS數(shù)據(jù)，首先根據(jù)經(jīng)緯度和時刻的不同將數(shù)據(jù)集劃分成小的數(shù)據(jù)集，具體劃分情況見表1，然后利用復(fù)雜網(wǎng)絡(luò)理論，對城市環(huán)境下VANET的拓撲特性進行實證研究。

表1 實際數(shù)據(jù)集的劃分

2.1 無標度特性分析

圖2 R=300時實際數(shù)據(jù)集的度分布示意圖

表2 實際數(shù)據(jù)集冪律參數(shù)

標度特性。為了驗證結(jié)論的正確性，基于實際數(shù)據(jù)集中其他日期的GPS 數(shù)據(jù)也進行了度分布的γ計算，γ均大于3。由實驗結(jié)果可以得到，在組網(wǎng)方式為通信半徑范圍內(nèi)全連接，R從300 m增長到1000 m時，VANET不具有無標度特性。

為了進一步探究道路約束條件對VANET無標度特性的影響，在一定節(jié)點坐標范圍內(nèi)，隨機取點生成了10 個仿真數(shù)據(jù)集文件，在相同的通信半徑與組網(wǎng)方式下分析無道路約束條件下網(wǎng)絡(luò)的無標度特性。仿真數(shù)據(jù)集中的節(jié)點數(shù)目在100～1000以每次增長100 個節(jié)點數(shù)遞增，節(jié)點坐標范圍為3000×3000，節(jié)點在區(qū)域內(nèi)均勻分布。

圖3a是仿真數(shù)據(jù)集6～10在R為300、連接方式為全連接時的度分布圖，在雙對數(shù)坐標下，由相應(yīng)數(shù)據(jù)所組成網(wǎng)絡(luò)的累計度分布如圖3b 所示，其尾部分布近似于直線，符合無標度網(wǎng)絡(luò)的度分布在雙對數(shù)坐標下的變化趨勢，但VANET 是否具有無標度特性還需進一步分析。由仿真數(shù)據(jù)集1～5 的GPS數(shù)據(jù)所組成的網(wǎng)絡(luò)，在相同的半徑和組網(wǎng)方式下，可得到與圖3分布及走勢類似的度分布圖。

圖3 R=300時仿真數(shù)據(jù)集的度分布示意圖

采用與上述相同的方式計算冪律參數(shù)，如表3所示。從表3 可以看出，網(wǎng)絡(luò)不具有無標度特性，說明無論是否具有道路約束條件，在全連接的組網(wǎng)方式下，VANET不具有無標度特性。

表3 仿真數(shù)據(jù)集冪律參數(shù)

2.2 連通性和小世界特性分析

從圖4 可知，連通分支數(shù)隨著R的增加而下降，當R達到400 m 時，連通分支數(shù)變化率下降速度顯著加快，當R達到一定值后，連通分支數(shù)的下降速度逐漸平緩。由此可以通過分析連通分支數(shù)而選擇適當?shù)腞。

圖4 實際數(shù)據(jù)集連通分支數(shù)與通信半徑之間的關(guān)系

圖5為實際數(shù)據(jù)集1～6的VANET中，聚類系數(shù)隨R變化的曲線，組網(wǎng)方式為通信半徑范圍內(nèi)全連接。實際數(shù)據(jù)集1～3的R增加時，聚類系數(shù)略有波動，實際數(shù)據(jù)集4～6 的R增加時，聚類系數(shù)略有下降，但總體都維持在0.6左右，說明網(wǎng)絡(luò)具有高聚類特性。取實際數(shù)據(jù)集其他日期的GPS 數(shù)據(jù)進行聚類系數(shù)的計算，計算結(jié)果雖然在數(shù)值上有一定差別，但總體維持在0.5左右。綜上所述，在全連接組網(wǎng)方式下，R從300 m 增加到1000 m，VANET 的聚類系數(shù)總體維持在0.5左右，具有較高的聚類特性。

圖5 實際數(shù)據(jù)集聚類系數(shù)與通信半徑之間的關(guān)系

從圖4 可以看出，實際數(shù)據(jù)集1 在R增長到600 m 時，連通分支數(shù)變?yōu)?，由不連通變?yōu)檫B通。實際數(shù)據(jù)集1 在組網(wǎng)方式為通信半徑范圍內(nèi)全連接，R從600 m增長到1000 m時，運用networkx包計算網(wǎng)絡(luò)的L、C、＜k＞，利用式（8）計算Lrand、Crand、L/Lrand和C/Crand。計算結(jié)果如表4 所示，L/Lrand均在2 左右，C/Crand遠大于1，不完全滿足式（7），所以在組網(wǎng)方式為通信半徑范圍內(nèi)全連接，R從600 m 增長到1000 m時，VANET不具有小世界特性。

表4 不同通信半徑下的小世界特性分析表

3 結(jié)論

基于復(fù)雜網(wǎng)絡(luò)，以成都市滴滴數(shù)據(jù)集組成的VANET 為例，利用實際GPS數(shù)據(jù)分析了VANET 的基本拓撲特性。通過仿真驗證得出，在通信半徑內(nèi)全連接的組網(wǎng)方式下，VANET 不具有無標度特性和小世界特性；網(wǎng)絡(luò)整體具有高聚類特性；連通分支數(shù)隨通信半徑的增加而減少，當通信半徑增加到一定值時，連通分支數(shù)變化率急速下降。結(jié)論為實際通信協(xié)議設(shè)計提供了支撐。例如在路由協(xié)議設(shè)計時，采用全連接方式得到的鄰居節(jié)點不具有顯著的度分布差異，因此節(jié)點度不適于用作選擇下一跳路由節(jié)點的判據(jù)；在構(gòu)造網(wǎng)絡(luò)時，如果通過優(yōu)先連接方式，可能會使得網(wǎng)絡(luò)拓撲特征發(fā)生變化；如果網(wǎng)絡(luò)具有無標度性，則可基于節(jié)點度數(shù)來設(shè)計路由協(xié)議。在優(yōu)先連接方式下，網(wǎng)絡(luò)具有何種拓撲特性，是后續(xù)要研究的內(nèi)容。