基于復(fù)雜網(wǎng)絡(luò)的車載自組網(wǎng)拓?fù)涮匦苑治?/h1>
2021-07-03 08:12:56周貝貝周鵬
湖北汽車工業(yè)學(xué)院學(xué)報 2021年2期
周貝貝，周鵬
（湖北汽車工業(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ò)特征進行研究。認(rèn)識車載自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)及其演化規(guī)律，從而研究影響VANET 信息傳輸能力的關(guān)鍵特性，是優(yōu)化網(wǎng)絡(luò)路由策略的理論基礎(chǔ)［2］。
目前VANET 拓?fù)涮匦允菍W(xué)者們研究的熱點。張麗麗通過上海市4000多輛出租車的GPS數(shù)據(jù)對VANET 網(wǎng)的一些參數(shù)進行統(tǒng)計分析，發(fā)現(xiàn)VANET網(wǎng)具有無標(biāo)度特性，同時網(wǎng)絡(luò)的局部和整體均具有較高的聚類特性［3］。高天智結(jié)合圖論和復(fù)雜網(wǎng)絡(luò)理論，得出城市軌道網(wǎng)絡(luò)具有無標(biāo)度及小世界特性的結(jié)論［4］。黃加增基于復(fù)雜網(wǎng)絡(luò)理論，利用相關(guān)參數(shù)對城市公交網(wǎng)絡(luò)進行了分析，得出城市公交網(wǎng)絡(luò)具有無標(biāo)度特性的結(jié)論［5］。Zheng 分析了VANET網(wǎng)絡(luò)瞬時拓?fù)涮匦裕l(fā)現(xiàn)VANET 網(wǎng)不具有無標(biāo)度特性，而當(dāng)通信半徑足夠大時，顯示出小世界特性［6］。Zhang 對城市環(huán)境下VANET 的動態(tài)拓?fù)涮匦赃M行了分析，發(fā)現(xiàn)通信半徑是影響網(wǎng)絡(luò)連通性的主要參數(shù)［7］。
網(wǎng)絡(luò)拓?fù)浣Y(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ò)拓?fù)浣Y(jié)構(gòu)和節(jié)點隊列長度，Ling提出了新的全局動態(tài)路由［10］。雖然VANET網(wǎng)拓?fù)涮匦苑治黾巴ㄐ艆f(xié)議的研究取得了不少成果，但仍然存在一些亟需解決的難題，比如VANET 是否具有無標(biāo)度與小世界特性，在什么條件下會具有這些特性。在現(xiàn)有的文獻資料中，關(guān)于這個問題的結(jié)論并不一致,甚至得出的結(jié)論截然相反。
當(dāng)VANET 具有無標(biāo)度特性時，在雙對數(shù)坐標(biāo)下，其度分布的概率密度函數(shù)為一條直線，為檢驗網(wǎng)絡(luò)是否具有無標(biāo)度特性提供了經(jīng)驗的檢驗方法。目前在對網(wǎng)絡(luò)無標(biāo)度特性的驗證問題上，許多文獻采用最小二乘法在雙對數(shù)坐標(biāo)下對網(wǎng)絡(luò)的度分布進行直線擬合，從而計算縮放參數(shù)，但是使用這種方法時往往會產(chǎn)生較大系統(tǒng)誤差［11-12］。主要原因在于，冪律分布屬于肥尾分布，度分布的尾部取值較多且分散，此時采用標(biāo)準(zhǔn)線性回歸方法對度分布進行擬合，會得到幾種不同的解，并且這些解往往較真實參數(shù)偏低。Clauset 等曾將參數(shù)γ的極大似然估計和基于線性回歸的最小二乘估計作比較，發(fā)現(xiàn)極大似然估計遠(yuǎn)比最小二乘估計精確［12］。實際應(yīng)用中，最小二乘法在雙對數(shù)坐標(biāo)下度分布尾部擬合為直線可作為判定冪律分布的必要條件，需采用KS 檢驗和極大似然估計法對VANET 是否具有無標(biāo)度特性進一步驗證。
文中基于成都滴滴實際數(shù)據(jù)集和實驗仿真數(shù)據(jù)集，分析了城市環(huán)境下VANET的拓?fù)涮匦裕沂玖司W(wǎng)絡(luò)演化的規(guī)律。
1 VANET拓?fù)涮匦苑治?/h2>
城市環(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ù)。無標(biāo)度網(wǎng)絡(luò)的顯著特點是其節(jié)點度服從冪律分布，因此度分布可近似表示為冪函數(shù)：
式中：γ為縮放參數(shù)，取值2～3。節(jié)點連接度沒有明顯特征長度的網(wǎng)絡(luò)，稱為無標(biāo)度網(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ò)是否具有無標(biāo)度特性。
文中采用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為度值大?。粁min為冪律下界。使D值達(dá)到最小的點即xmin。離散冪律分布其縮放參數(shù)的極大似然估計表示為［12］
式中：xi為節(jié)點i的度值。
圖1為指數(shù)分布在雙對數(shù)坐標(biāo)下的度分布圖，可以看出，度分布的變化規(guī)律可用直線擬合，在最小二乘法中，網(wǎng)絡(luò)度分布服從冪律分布。利用式（3）～（4）計算得γ為9.9，說明網(wǎng)絡(luò)度分布不服從冪律分布，網(wǎng)絡(luò)不具有無標(biāo)度特性。因此在雙對數(shù)坐標(biāo)下，度分布尾部擬合為直線是判定冪律分布的必要條件，而不是充分條件。
圖1 指數(shù)分布y = e-x的對數(shù)擬合圖
1.2 連通分支數(shù)
連通性對網(wǎng)絡(luò)的通信具有至關(guān)重要的作用，當(dāng)網(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ù)對通信的可達(dá)性和整體網(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之間的最短路徑長度。當(dāng)1 個網(wǎng)絡(luò)同時具有較大聚類系數(shù)和較小平均路徑長度時，稱該網(wǎng)絡(luò)具有小世界特性。平均路徑長度是從全局角度描述網(wǎng)絡(luò)中任意兩節(jié)點間距離的特征參數(shù)，L越小車輛之間的通信越暢通，VANET 的可通達(dá)性越好。檢查1 個網(wǎng)絡(luò)是否為小世界網(wǎng)絡(luò)，可以將L和平均聚類系數(shù)C與相同規(guī)模（具有相同的N和總邊數(shù)K）的隨機圖的值Lrand和Crand進行比較，當(dāng)L與Lrand為等階量，C遠(yuǎn)大于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拓?fù)涮匦詫嵶C研究
基于成都滴滴數(shù)據(jù)集GPS數(shù)據(jù)，首先根據(jù)經(jīng)緯度和時刻的不同將數(shù)據(jù)集劃分成小的數(shù)據(jù)集，具體劃分情況見表1，然后利用復(fù)雜網(wǎng)絡(luò)理論，對城市環(huán)境下VANET的拓?fù)涮匦赃M行實證研究。
表1 實際數(shù)據(jù)集的劃分
2.1 無標(biāo)度特性分析
圖2 R=300時實際數(shù)據(jù)集的度分布示意圖
表2 實際數(shù)據(jù)集冪律參數(shù)
標(biāo)度特性。為了驗證結(jié)論的正確性，基于實際數(shù)據(jù)集中其他日期的GPS 數(shù)據(jù)也進行了度分布的γ計算，γ均大于3。由實驗結(jié)果可以得到，在組網(wǎng)方式為通信半徑范圍內(nèi)全連接，R從300 m增長到1000 m時，VANET不具有無標(biāo)度特性。
為了進一步探究道路約束條件對VANET無標(biāo)度特性的影響，在一定節(jié)點坐標(biāo)范圍內(nèi)，隨機取點生成了10 個仿真數(shù)據(jù)集文件，在相同的通信半徑與組網(wǎng)方式下分析無道路約束條件下網(wǎng)絡(luò)的無標(biāo)度特性。仿真數(shù)據(jù)集中的節(jié)點數(shù)目在100～1000以每次增長100 個節(jié)點數(shù)遞增，節(jié)點坐標(biāo)范圍為3000×3000，節(jié)點在區(qū)域內(nèi)均勻分布。
圖3a是仿真數(shù)據(jù)集6～10在R為300、連接方式為全連接時的度分布圖，在雙對數(shù)坐標(biāo)下，由相應(yīng)數(shù)據(jù)所組成網(wǎng)絡(luò)的累計度分布如圖3b 所示，其尾部分布近似于直線，符合無標(biāo)度網(wǎng)絡(luò)的度分布在雙對數(shù)坐標(biāo)下的變化趨勢，但VANET 是否具有無標(biāo)度特性還需進一步分析。由仿真數(shù)據(jù)集1～5 的GPS數(shù)據(jù)所組成的網(wǎng)絡(luò)，在相同的半徑和組網(wǎng)方式下，可得到與圖3分布及走勢類似的度分布圖。
圖3 R=300時仿真數(shù)據(jù)集的度分布示意圖
采用與上述相同的方式計算冪律參數(shù)，如表3所示。從表3 可以看出，網(wǎng)絡(luò)不具有無標(biāo)度特性，說明無論是否具有道路約束條件，在全連接的組網(wǎng)方式下，VANET不具有無標(biāo)度特性。
表3 仿真數(shù)據(jù)集冪律參數(shù)
2.2 連通性和小世界特性分析
從圖4 可知，連通分支數(shù)隨著R的增加而下降，當(dāng)R達(dá)到400 m 時，連通分支數(shù)變化率下降速度顯著加快，當(dāng)R達(dá)到一定值后，連通分支數(shù)的下降速度逐漸平緩。由此可以通過分析連通分支數(shù)而選擇適當(dāng)?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遠(yuǎn)大于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 的基本拓?fù)涮匦?。通過仿真驗證得出，在通信半徑內(nèi)全連接的組網(wǎng)方式下，VANET 不具有無標(biāo)度特性和小世界特性；網(wǎng)絡(luò)整體具有高聚類特性；連通分支數(shù)隨通信半徑的增加而減少，當(dāng)通信半徑增加到一定值時，連通分支數(shù)變化率急速下降。結(jié)論為實際通信協(xié)議設(shè)計提供了支撐。例如在路由協(xié)議設(shè)計時，采用全連接方式得到的鄰居節(jié)點不具有顯著的度分布差異，因此節(jié)點度不適于用作選擇下一跳路由節(jié)點的判據(jù)；在構(gòu)造網(wǎng)絡(luò)時，如果通過優(yōu)先連接方式，可能會使得網(wǎng)絡(luò)拓?fù)涮卣靼l(fā)生變化；如果網(wǎng)絡(luò)具有無標(biāo)度性，則可基于節(jié)點度數(shù)來設(shè)計路由協(xié)議。在優(yōu)先連接方式下，網(wǎng)絡(luò)具有何種拓?fù)涮匦?，是后續(xù)要研究的內(nèi)容。
猜你喜歡
層次分析法中兩種標(biāo)度的對比分析玉溪師范學(xué)院學(xué)報(2023年3期)2023-08-31 14:11:56 偏序集的序連通關(guān)系及其序連通分支高校應(yīng)用數(shù)學(xué)學(xué)報A輯(2022年3期)2022-09-29 06:53:22 關(guān)于圖的距離無符號拉普拉斯譜半徑的下界華中師范大學(xué)學(xué)報(自然科學(xué)版)(2021年3期)2021-06-10 05:28:44 四川地區(qū)降水冪律指數(shù)研究高原山地氣象研究(2016年1期)2016-11-10 06:05:57 冪律流底泥的質(zhì)量輸移和流場浙江大學(xué)學(xué)報(工學(xué)版)(2016年9期)2016-06-05 09:20:57 加權(quán)無標(biāo)度網(wǎng)絡(luò)上SIRS 類傳播模型研究河北工業(yè)大學(xué)學(xué)報(2016年6期)2016-04-16 02:54:19 對抗冪律意林原創(chuàng)版(2015年10期)2015-05-30 10:48:04 一個圖論問題的簡單證明新課程(下)(2015年9期)2015-04-12 09:23:30 交換環(huán)的素譜與極大譜的連通性純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)(2014年2期)2014-07-19 13:54:52 創(chuàng)新孵化網(wǎng)絡(luò)演化無標(biāo)度特征仿真分析技術(shù)經(jīng)濟(2014年10期)2014-02-28 01:30:01
周貝貝，周鵬
（湖北汽車工業(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ò)特征進行研究。認(rèn)識車載自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)及其演化規(guī)律，從而研究影響VANET 信息傳輸能力的關(guān)鍵特性，是優(yōu)化網(wǎng)絡(luò)路由策略的理論基礎(chǔ)［2］。
目前VANET 拓?fù)涮匦允菍W(xué)者們研究的熱點。張麗麗通過上海市4000多輛出租車的GPS數(shù)據(jù)對VANET 網(wǎng)的一些參數(shù)進行統(tǒng)計分析，發(fā)現(xiàn)VANET網(wǎng)具有無標(biāo)度特性，同時網(wǎng)絡(luò)的局部和整體均具有較高的聚類特性［3］。高天智結(jié)合圖論和復(fù)雜網(wǎng)絡(luò)理論，得出城市軌道網(wǎng)絡(luò)具有無標(biāo)度及小世界特性的結(jié)論［4］。黃加增基于復(fù)雜網(wǎng)絡(luò)理論，利用相關(guān)參數(shù)對城市公交網(wǎng)絡(luò)進行了分析，得出城市公交網(wǎng)絡(luò)具有無標(biāo)度特性的結(jié)論［5］。Zheng 分析了VANET網(wǎng)絡(luò)瞬時拓?fù)涮匦裕l(fā)現(xiàn)VANET 網(wǎng)不具有無標(biāo)度特性，而當(dāng)通信半徑足夠大時，顯示出小世界特性［6］。Zhang 對城市環(huán)境下VANET 的動態(tài)拓?fù)涮匦赃M行了分析，發(fā)現(xiàn)通信半徑是影響網(wǎng)絡(luò)連通性的主要參數(shù)［7］。
網(wǎng)絡(luò)拓?fù)浣Y(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ò)拓?fù)浣Y(jié)構(gòu)和節(jié)點隊列長度，Ling提出了新的全局動態(tài)路由［10］。雖然VANET網(wǎng)拓?fù)涮匦苑治黾巴ㄐ艆f(xié)議的研究取得了不少成果，但仍然存在一些亟需解決的難題，比如VANET 是否具有無標(biāo)度與小世界特性，在什么條件下會具有這些特性。在現(xiàn)有的文獻資料中，關(guān)于這個問題的結(jié)論并不一致,甚至得出的結(jié)論截然相反。
當(dāng)VANET 具有無標(biāo)度特性時，在雙對數(shù)坐標(biāo)下，其度分布的概率密度函數(shù)為一條直線，為檢驗網(wǎng)絡(luò)是否具有無標(biāo)度特性提供了經(jīng)驗的檢驗方法。目前在對網(wǎng)絡(luò)無標(biāo)度特性的驗證問題上，許多文獻采用最小二乘法在雙對數(shù)坐標(biāo)下對網(wǎng)絡(luò)的度分布進行直線擬合，從而計算縮放參數(shù)，但是使用這種方法時往往會產(chǎn)生較大系統(tǒng)誤差［11-12］。主要原因在于，冪律分布屬于肥尾分布，度分布的尾部取值較多且分散，此時采用標(biāo)準(zhǔn)線性回歸方法對度分布進行擬合，會得到幾種不同的解，并且這些解往往較真實參數(shù)偏低。Clauset 等曾將參數(shù)γ的極大似然估計和基于線性回歸的最小二乘估計作比較，發(fā)現(xiàn)極大似然估計遠(yuǎn)比最小二乘估計精確［12］。實際應(yīng)用中，最小二乘法在雙對數(shù)坐標(biāo)下度分布尾部擬合為直線可作為判定冪律分布的必要條件，需采用KS 檢驗和極大似然估計法對VANET 是否具有無標(biāo)度特性進一步驗證。
文中基于成都滴滴實際數(shù)據(jù)集和實驗仿真數(shù)據(jù)集，分析了城市環(huán)境下VANET的拓?fù)涮匦裕沂玖司W(wǎng)絡(luò)演化的規(guī)律。
1 VANET拓?fù)涮匦苑治?/h2>
城市環(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ù)。無標(biāo)度網(wǎng)絡(luò)的顯著特點是其節(jié)點度服從冪律分布，因此度分布可近似表示為冪函數(shù)：
式中：γ為縮放參數(shù)，取值2～3。節(jié)點連接度沒有明顯特征長度的網(wǎng)絡(luò)，稱為無標(biāo)度網(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ò)是否具有無標(biāo)度特性。
文中采用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為度值大?。粁min為冪律下界。使D值達(dá)到最小的點即xmin。離散冪律分布其縮放參數(shù)的極大似然估計表示為［12］
式中：xi為節(jié)點i的度值。
圖1為指數(shù)分布在雙對數(shù)坐標(biāo)下的度分布圖，可以看出，度分布的變化規(guī)律可用直線擬合，在最小二乘法中，網(wǎng)絡(luò)度分布服從冪律分布。利用式（3）～（4）計算得γ為9.9，說明網(wǎng)絡(luò)度分布不服從冪律分布，網(wǎng)絡(luò)不具有無標(biāo)度特性。因此在雙對數(shù)坐標(biāo)下，度分布尾部擬合為直線是判定冪律分布的必要條件，而不是充分條件。
圖1 指數(shù)分布y = e-x的對數(shù)擬合圖
1.2 連通分支數(shù)
連通性對網(wǎng)絡(luò)的通信具有至關(guān)重要的作用，當(dāng)網(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ù)對通信的可達(dá)性和整體網(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之間的最短路徑長度。當(dāng)1 個網(wǎng)絡(luò)同時具有較大聚類系數(shù)和較小平均路徑長度時，稱該網(wǎng)絡(luò)具有小世界特性。平均路徑長度是從全局角度描述網(wǎng)絡(luò)中任意兩節(jié)點間距離的特征參數(shù)，L越小車輛之間的通信越暢通，VANET 的可通達(dá)性越好。檢查1 個網(wǎng)絡(luò)是否為小世界網(wǎng)絡(luò)，可以將L和平均聚類系數(shù)C與相同規(guī)模（具有相同的N和總邊數(shù)K）的隨機圖的值Lrand和Crand進行比較，當(dāng)L與Lrand為等階量，C遠(yuǎn)大于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拓?fù)涮匦詫嵶C研究
基于成都滴滴數(shù)據(jù)集GPS數(shù)據(jù)，首先根據(jù)經(jīng)緯度和時刻的不同將數(shù)據(jù)集劃分成小的數(shù)據(jù)集，具體劃分情況見表1，然后利用復(fù)雜網(wǎng)絡(luò)理論，對城市環(huán)境下VANET的拓?fù)涮匦赃M行實證研究。
表1 實際數(shù)據(jù)集的劃分
2.1 無標(biāo)度特性分析
圖2 R=300時實際數(shù)據(jù)集的度分布示意圖
表2 實際數(shù)據(jù)集冪律參數(shù)
標(biāo)度特性。為了驗證結(jié)論的正確性，基于實際數(shù)據(jù)集中其他日期的GPS 數(shù)據(jù)也進行了度分布的γ計算，γ均大于3。由實驗結(jié)果可以得到，在組網(wǎng)方式為通信半徑范圍內(nèi)全連接，R從300 m增長到1000 m時，VANET不具有無標(biāo)度特性。
為了進一步探究道路約束條件對VANET無標(biāo)度特性的影響，在一定節(jié)點坐標(biāo)范圍內(nèi)，隨機取點生成了10 個仿真數(shù)據(jù)集文件，在相同的通信半徑與組網(wǎng)方式下分析無道路約束條件下網(wǎng)絡(luò)的無標(biāo)度特性。仿真數(shù)據(jù)集中的節(jié)點數(shù)目在100～1000以每次增長100 個節(jié)點數(shù)遞增，節(jié)點坐標(biāo)范圍為3000×3000，節(jié)點在區(qū)域內(nèi)均勻分布。
圖3a是仿真數(shù)據(jù)集6～10在R為300、連接方式為全連接時的度分布圖，在雙對數(shù)坐標(biāo)下，由相應(yīng)數(shù)據(jù)所組成網(wǎng)絡(luò)的累計度分布如圖3b 所示，其尾部分布近似于直線，符合無標(biāo)度網(wǎng)絡(luò)的度分布在雙對數(shù)坐標(biāo)下的變化趨勢，但VANET 是否具有無標(biāo)度特性還需進一步分析。由仿真數(shù)據(jù)集1～5 的GPS數(shù)據(jù)所組成的網(wǎng)絡(luò)，在相同的半徑和組網(wǎng)方式下，可得到與圖3分布及走勢類似的度分布圖。
圖3 R=300時仿真數(shù)據(jù)集的度分布示意圖
采用與上述相同的方式計算冪律參數(shù)，如表3所示。從表3 可以看出，網(wǎng)絡(luò)不具有無標(biāo)度特性，說明無論是否具有道路約束條件，在全連接的組網(wǎng)方式下，VANET不具有無標(biāo)度特性。
表3 仿真數(shù)據(jù)集冪律參數(shù)
2.2 連通性和小世界特性分析
從圖4 可知，連通分支數(shù)隨著R的增加而下降，當(dāng)R達(dá)到400 m 時，連通分支數(shù)變化率下降速度顯著加快，當(dāng)R達(dá)到一定值后，連通分支數(shù)的下降速度逐漸平緩。由此可以通過分析連通分支數(shù)而選擇適當(dāng)?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遠(yuǎn)大于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 的基本拓?fù)涮匦?。通過仿真驗證得出，在通信半徑內(nèi)全連接的組網(wǎng)方式下，VANET 不具有無標(biāo)度特性和小世界特性；網(wǎng)絡(luò)整體具有高聚類特性；連通分支數(shù)隨通信半徑的增加而減少，當(dāng)通信半徑增加到一定值時，連通分支數(shù)變化率急速下降。結(jié)論為實際通信協(xié)議設(shè)計提供了支撐。例如在路由協(xié)議設(shè)計時，采用全連接方式得到的鄰居節(jié)點不具有顯著的度分布差異，因此節(jié)點度不適于用作選擇下一跳路由節(jié)點的判據(jù)；在構(gòu)造網(wǎng)絡(luò)時，如果通過優(yōu)先連接方式，可能會使得網(wǎng)絡(luò)拓?fù)涮卣靼l(fā)生變化；如果網(wǎng)絡(luò)具有無標(biāo)度性，則可基于節(jié)點度數(shù)來設(shè)計路由協(xié)議。在優(yōu)先連接方式下，網(wǎng)絡(luò)具有何種拓?fù)涮匦?，是后續(xù)要研究的內(nèi)容。
猜你喜歡
玉溪師范學(xué)院學(xué)報(2023年3期)2023-08-31 14:11:56
高校應(yīng)用數(shù)學(xué)學(xué)報A輯(2022年3期)2022-09-29 06:53:22
華中師范大學(xué)學(xué)報(自然科學(xué)版)(2021年3期)2021-06-10 05:28:44
高原山地氣象研究(2016年1期)2016-11-10 06:05:57
浙江大學(xué)學(xué)報(工學(xué)版)(2016年9期)2016-06-05 09:20:57
河北工業(yè)大學(xué)學(xué)報(2016年6期)2016-04-16 02:54:19
意林原創(chuàng)版(2015年10期)2015-05-30 10:48:04
新課程(下)(2015年9期)2015-04-12 09:23:30
純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)(2014年2期)2014-07-19 13:54:52
技術(shù)經(jīng)濟(2014年10期)2014-02-28 01:30:01
