馮慧芳，王俊霞

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070)

(*通信作者電子郵箱hffeng@nwnu.edu.cn)

車載自組織網(wǎng)絡(luò)動(dòng)態(tài)中心性分析

馮慧芳*，王俊霞

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070)

(*通信作者電子郵箱hffeng@nwnu.edu.cn)

針對(duì)車載自組織網(wǎng)絡(luò)(VANET)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)性特征，基于車輛換道功能的智能駕駛移動(dòng)模型，應(yīng)用VanetMobiSim仿真軟件詳細(xì)研究車載自組織網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)中心性。構(gòu)建VANET時(shí)序網(wǎng)絡(luò)模型，建立基于衰落因子和信息存儲(chǔ)轉(zhuǎn)發(fā)指數(shù)的動(dòng)態(tài)中心性評(píng)價(jià)方法，該方法不僅能夠描述當(dāng)前網(wǎng)絡(luò)拓?fù)渑c歷史網(wǎng)絡(luò)拓?fù)渲g的聯(lián)系，而且能夠刻畫VANET中信息的存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制；最后，通過(guò)仿真實(shí)驗(yàn)分析了VANET動(dòng)態(tài)中心性。結(jié)果表明雖然VANET拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)中心性隨著衰落因子和信息存儲(chǔ)轉(zhuǎn)發(fā)指數(shù)的變化而變化，但重要節(jié)點(diǎn)整體的排名基本保持相對(duì)穩(wěn)定的狀態(tài)。該結(jié)論有助于更好地確定信息傳播的中繼節(jié)點(diǎn)，實(shí)現(xiàn)信息的成功投遞，而且為VANET拓?fù)浣Y(jié)構(gòu)的抗毀性提供指導(dǎo)。

車載自組織網(wǎng)絡(luò); 動(dòng)態(tài)中心性; 重要節(jié)點(diǎn); 排名; 仿真

0 引言

車載自組織網(wǎng)絡(luò)(Vehicle Ad hoc Network，VANET)[1]作為一種特殊的移動(dòng)Ad Hoc網(wǎng)絡(luò)，它是在車輛環(huán)境中實(shí)現(xiàn)的動(dòng)態(tài)轉(zhuǎn)發(fā)數(shù)據(jù)的移動(dòng)網(wǎng)絡(luò)。在VANET中，在一定的區(qū)域內(nèi)使用無(wú)線網(wǎng)絡(luò)通信技術(shù)將車輛與車輛以及車輛與固定基礎(chǔ)設(shè)施連接在一起，從而能快速地在現(xiàn)有的道路上建立一個(gè)車輛間多跳通信的動(dòng)態(tài)網(wǎng)絡(luò)，且該網(wǎng)絡(luò)具有自組織、分布式控制的特點(diǎn)。美國(guó)聯(lián)邦通信委員會(huì)(Federal Communications Commission，F(xiàn)CC)于1999年將從5.85 GHz到5.925 GHz的共75 MHz頻段劃分出來(lái)用于車輛環(huán)境下的專用短距離通信頻段(Dedicated Short Range Communications, DSRC)[2]。DSRC通信范圍擴(kuò)展到1 000 m，數(shù)據(jù)傳輸速率也提高到6～27 Mb/s。之后DSRC發(fā)展成為車載無(wú)線接入(Wireless Access in Vehicular Environments， WAVE)系統(tǒng)[3]。2009年，國(guó)際互聯(lián)網(wǎng)工程任務(wù)組(Internet Engineering Task Force，IETF)制定了由802.11標(biāo)準(zhǔn)擴(kuò)充的WAVE，又稱IEEE 802.11p，這不僅為行車環(huán)境下的無(wú)線接入提供便利，而且為未來(lái)智能交通系統(tǒng)的諸多應(yīng)用提供了技術(shù)支持。由于VANET在社會(huì)和經(jīng)濟(jì)方面的巨大價(jià)值,已成為學(xué)術(shù)界、工業(yè)界和各國(guó)職能部門的熱點(diǎn)研究領(lǐng)域[4]。

由于車輛的高速運(yùn)動(dòng)，無(wú)線通信設(shè)備通信距離有限，且無(wú)線信道易受道路上各類障礙物阻攔，都會(huì)導(dǎo)致VANET的網(wǎng)絡(luò)拓?fù)潆S時(shí)間劇烈變化。因此，如果能夠掌握VANET拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)特性，就可以設(shè)計(jì)高效的拓?fù)淇刂扑惴?，?yōu)化網(wǎng)絡(luò)連通性，使網(wǎng)絡(luò)能夠持續(xù)穩(wěn)定提供可靠的服務(wù)。中心性是評(píng)價(jià)網(wǎng)絡(luò)拓?fù)涮卣鞯闹饕笜?biāo)之一，通過(guò)中心性的研究可以挖掘網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，從而可以采取一系列有效的措施來(lái)提高網(wǎng)絡(luò)的性能，優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，保證網(wǎng)絡(luò)的穩(wěn)定的通信能力，這對(duì)拓?fù)鋭?dòng)態(tài)變化的VANET協(xié)議開發(fā)和網(wǎng)絡(luò)管理有著重要的意義。

目前，對(duì)VANET拓?fù)浣Y(jié)構(gòu)的研究主要是基于復(fù)雜網(wǎng)絡(luò)理論分析其度分布、聚類系數(shù)、路徑長(zhǎng)度等。文獻(xiàn)[5]以多Agent微觀交通仿真器為仿真工具，研究了車載自組織網(wǎng)絡(luò)的瞬時(shí)特性，研究結(jié)果表明網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)服從參數(shù)冪律分布,VANET不存在小世界特性。文獻(xiàn)[6]中利用出租車全球定位系統(tǒng)(Global Positioning System，GPS)數(shù)據(jù)分析了城市環(huán)境下VANET的度分布、聚類系數(shù)、特征路徑長(zhǎng)度等拓?fù)涮匦?。文獻(xiàn)[7]應(yīng)用Barabasi和Albert提出的BA(Barabasi-Albert)無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)VANET拓?fù)溥M(jìn)行建模分析，認(rèn)為VANET具有小世界特性。相比之下，VANET中心性的研究比較少。文獻(xiàn)[8]研究了德國(guó)科隆的交通網(wǎng)絡(luò)的瞬時(shí)拓?fù)浣Y(jié)構(gòu)，其主要刻畫參數(shù)包括最大連通分支、度及介數(shù)中心性等，分析結(jié)果表明VANET不具有小世界特性。文獻(xiàn)[9]以城市道路交通仿真軟件為仿真工具研究了VANET的中心性。但是，這些中心性的研究?jī)H僅考慮了VANET靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)或瞬時(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，沒(méi)有考慮網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性。事實(shí)上，VANET為含有時(shí)間的復(fù)雜網(wǎng)絡(luò)，即時(shí)序復(fù)雜網(wǎng)絡(luò)(temporal complex network)[10]。一方面，靜態(tài)網(wǎng)絡(luò)數(shù)據(jù)的不全面性會(huì)導(dǎo)致實(shí)際的動(dòng)態(tài)網(wǎng)絡(luò)丟失大量有價(jià)值信息，因此有必要對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)變化深入研究；另一方面，瞬時(shí)網(wǎng)絡(luò)拓?fù)浔硎緞?dòng)態(tài)網(wǎng)絡(luò)中當(dāng)前時(shí)刻拓?fù)浣Y(jié)構(gòu)與上一個(gè)時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)完全無(wú)關(guān)，雖然瞬時(shí)網(wǎng)絡(luò)拓?fù)涮卣鞯难芯磕軌蚍治鰟?dòng)態(tài)網(wǎng)絡(luò)隨時(shí)間的一些變化趨勢(shì)，但是割裂了當(dāng)前時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與歷史時(shí)刻網(wǎng)絡(luò)拓?fù)渲g的某種內(nèi)在的聯(lián)系。本文研究VANET動(dòng)態(tài)中心性問(wèn)題，評(píng)價(jià)VANET中節(jié)點(diǎn)的重要性，特別研究關(guān)鍵節(jié)點(diǎn)隨時(shí)間的演化特征，期望能夠利用這一特征更好地確定信息傳播中的中繼節(jié)點(diǎn)，從而實(shí)現(xiàn)信息的成功投遞，為開發(fā)新的VANET路由算法提供指導(dǎo)。

1 VANET時(shí)序網(wǎng)絡(luò)建模

1)基本靜態(tài)圖G=(V,E)；

2)T是時(shí)間軸；

3)邊存在函數(shù)ρ:E×ΔT→{0,1}，在給定的時(shí)間窗內(nèi)給定一個(gè)邊是否存在。

其中：V是網(wǎng)絡(luò)的節(jié)點(diǎn)集，E是網(wǎng)絡(luò)的邊集。將時(shí)間軸T離散為時(shí)間點(diǎn)的0≤t1

圖1 VANET時(shí)序網(wǎng)絡(luò)

2 動(dòng)態(tài)中心性研究方法

目前，中心性研究領(lǐng)域已有很多成熟的算法[12]，包括Katzstatusscore、α-中心性(α-centrality)、介數(shù)中心性(betweenness centrality)、接近度中心性(closeness centrality)、PageRank算法及一些基于隨機(jī)游走的中心性算法，其中最著名的是谷歌的評(píng)價(jià)頁(yè)面重要性的PageRank算法，這些中心性算法僅適用于靜態(tài)網(wǎng)絡(luò)。本文采用動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)序中心性[13]研究VANET的動(dòng)態(tài)拓?fù)涮卣鳌?/p>

2.1 α-中心性

α-中心性定義為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間任意長(zhǎng)度的衰落路徑的總數(shù),具體的計(jì)算公式如下：

Cs(α,β)=βA+βαA2+…+βαnAn+1

(1)

其中:A為網(wǎng)絡(luò)的鄰接矩陣，α指的是在一條路徑中沿著無(wú)向邊的衰落因子，β指的是在一條路徑中沿著有向邊的衰落因子。式(1)中的第一項(xiàng)表示的是從節(jié)點(diǎn)i到節(jié)點(diǎn)j之間長(zhǎng)度為1的路徑總數(shù)，第二項(xiàng)表示的是從節(jié)點(diǎn)i到j(luò)之間長(zhǎng)度為2的路徑總數(shù)，其他項(xiàng)以此類推。

在動(dòng)態(tài)網(wǎng)絡(luò)中，當(dāng)前時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)與歷史時(shí)刻的狀態(tài)有某種內(nèi)在的聯(lián)系。對(duì)于歷史時(shí)刻的網(wǎng)絡(luò)而言，與當(dāng)前時(shí)刻的時(shí)間距離越遠(yuǎn)，則對(duì)當(dāng)前時(shí)刻的影響力越小。用參數(shù)α刻畫當(dāng)前網(wǎng)絡(luò)拓?fù)涫艿綒v史網(wǎng)絡(luò)影響的大小。當(dāng)α=0時(shí)，α-中心性衰減為權(quán)重為β的度中心性。隨著α的增長(zhǎng)，α-中心性逐漸演化成一個(gè)更全局的測(cè)量指標(biāo)，因?yàn)楫?dāng)α越大時(shí)，說(shuō)明當(dāng)前網(wǎng)絡(luò)拓?fù)涫艿綒v史網(wǎng)絡(luò)拓?fù)溆绊懙臅r(shí)間長(zhǎng)度越長(zhǎng)。

2.2 無(wú)記憶的動(dòng)態(tài)中心性

設(shè)假設(shè)網(wǎng)絡(luò)的未來(lái)狀態(tài)Gtk+1只取決于當(dāng)前網(wǎng)絡(luò)Gtk，與過(guò)去的網(wǎng)絡(luò)狀態(tài)都沒(méi)有關(guān)系。此時(shí)，在網(wǎng)絡(luò)中建立的信息傳播模型可以作為一個(gè)無(wú)記憶的動(dòng)態(tài)過(guò)程。假設(shè)：1)一個(gè)節(jié)點(diǎn)在tk時(shí)刻給鄰居節(jié)點(diǎn)發(fā)送信息的概率是βtk；2)一個(gè)節(jié)點(diǎn)將它在tk時(shí)刻收到的信息在tk+1時(shí)刻發(fā)送給鄰居節(jié)點(diǎn)的概率為αtk+1。為簡(jiǎn)單起見，假設(shè)αti=α,βti=β。則節(jié)點(diǎn)i在t1時(shí)刻開始發(fā)送信息到節(jié)點(diǎn)j在tn時(shí)刻收到信息的平均信息量可以通過(guò)動(dòng)態(tài)中心矩陣表示，即：

(2)

即信息在tk(1≤k≤n)時(shí)刻從任意節(jié)點(diǎn)i開始傳播在tn時(shí)刻到達(dá)任意的節(jié)點(diǎn)j。則在時(shí)間段T內(nèi)從節(jié)點(diǎn)i發(fā)送到節(jié)點(diǎn)j的總的信息量可以由累積動(dòng)態(tài)中心矩陣來(lái)表示，即

(3)

2.3 有記憶的動(dòng)態(tài)中心性

在許多動(dòng)態(tài)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的未來(lái)狀態(tài)Gtk+1不僅僅取決于它的當(dāng)前狀態(tài)Gtk，也有可能取決于它過(guò)去的狀態(tài)Gti(i

R(tn,γ)=

(4)

由式(2)可以得到信息存儲(chǔ)動(dòng)態(tài)中心矩陣的計(jì)算公式為：

(5)

那么，信息存儲(chǔ)累積動(dòng)態(tài)中心矩陣為：

(6)

2.4 動(dòng)態(tài)網(wǎng)絡(luò)中重要節(jié)點(diǎn)的度量

(7)

其中：DCi代表在時(shí)間T內(nèi)節(jié)點(diǎn)i動(dòng)態(tài)中心性的值，該值刻畫了在過(guò)去T時(shí)間段內(nèi)，節(jié)點(diǎn)i與網(wǎng)絡(luò)中其他節(jié)點(diǎn)信息的傳輸能力。DCi的值越大，節(jié)點(diǎn)i越重要。因此，用該指標(biāo)能夠確定在過(guò)去一段時(shí)間內(nèi)網(wǎng)絡(luò)中最具影響力的節(jié)點(diǎn)。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 VANET仿真環(huán)境

本文采用VanetMobisim[14]軟件建立VANET環(huán)境，仿真中車輛的移動(dòng)采用移動(dòng)模型刻畫。文獻(xiàn)[15]和[16]對(duì)各類移動(dòng)模型的性能作了詳細(xì)比較，移動(dòng)模型主要分為以下五類：1)隨機(jī)移動(dòng)模型，該模型沒(méi)有任何限制條件；2)時(shí)間依賴模型，節(jié)點(diǎn)當(dāng)前時(shí)刻的移動(dòng)受到以往時(shí)刻移動(dòng)的影響，比如平滑移動(dòng)模型(SmoothMobilityModel，SMM)；3)空間依賴模型，移動(dòng)受到周圍節(jié)點(diǎn)的影響，比如車流交通模型(FluidTrafficModel,FTM)；4)地理限制模型，移動(dòng)位置受到地圖的限制, 比如基于圖的移動(dòng)模型(Graph-BasedMobilityModel，GBMM)；5)混合移動(dòng)模型，即將時(shí)間依賴、空間依賴和地理限制相結(jié)合的模型,比如智能駕駛員模型(IntelligentDriverModelwithLaneChanges，IDM-LC)[17]。表1給出了各移動(dòng)模型的宏觀和微觀移動(dòng)特性，√表示模型具有該屬性，×表示模型不具備該屬性。鑒于這些模型中IDM-LC最能準(zhǔn)確刻畫車輛的移動(dòng)特征，因此，本文采用IDM-LC研究VANET動(dòng)態(tài)拓?fù)涮卣鳌?/p>

表1 移動(dòng)模型性能比較

IDM-LC模型是一種微觀交通流模型，是在IDM的基礎(chǔ)上增加了車輛在十字路口的管理及車輛換道功能的智能移動(dòng)模型，使得其更加符合真實(shí)的交通場(chǎng)景。IDM-LC移動(dòng)模型中車輛長(zhǎng)度為5m，加速度a和減速度b分別為0.6m/s2和0.9m/s2，禮貌參數(shù)p為0.5，其他參數(shù)設(shè)置如表2所示。

表2 IDM-LC移動(dòng)模型仿真參數(shù)

3.2 VANET動(dòng)態(tài)中心性分析

VANET時(shí)序網(wǎng)絡(luò)建模過(guò)程中，假設(shè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在每個(gè)時(shí)間窗Δti內(nèi)保持相對(duì)穩(wěn)定。由于車載自組織網(wǎng)絡(luò)中車輛移動(dòng)速度比較快，拓?fù)浣Y(jié)構(gòu)變化較快，因此Δti的值越小，得出的研究結(jié)論越精確，仿真實(shí)驗(yàn)中假設(shè)時(shí)間窗Δti=1 s。節(jié)點(diǎn)動(dòng)態(tài)中心性評(píng)價(jià)模型中包括了四個(gè)參數(shù)α、β、γ和m，每個(gè)節(jié)點(diǎn)中心性的值通過(guò)式(7)得到。由于β的值不影響重要節(jié)點(diǎn)的排名，不失一般性，令β=1。衰落因子α描述了當(dāng)前網(wǎng)絡(luò)拓?fù)渑c歷史網(wǎng)絡(luò)拓?fù)渲g的聯(lián)系。信息存儲(chǔ)概率γ和存儲(chǔ)時(shí)間長(zhǎng)度m能夠刻畫VANET中信息的存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制，這兩個(gè)參數(shù)也體現(xiàn)了信息在網(wǎng)絡(luò)中的記憶性，即信息存儲(chǔ)概率γ和存儲(chǔ)時(shí)間長(zhǎng)度m越大，信息被記憶和保留的時(shí)間越長(zhǎng)，成功轉(zhuǎn)發(fā)的概率越大。下面研究節(jié)點(diǎn)動(dòng)態(tài)中心性與這些參數(shù)之間的關(guān)系。

圖2為衰落因子α對(duì)VANET動(dòng)態(tài)中心性(DC)的影響，其中信息存儲(chǔ)概率γ=0，信息保留時(shí)間m=50 s。由圖2可知，隨著α的增加，網(wǎng)絡(luò)中各節(jié)點(diǎn)動(dòng)態(tài)中心性的值也在逐漸增大，相應(yīng)的各節(jié)點(diǎn)的排名情況也發(fā)生變化。如節(jié)點(diǎn)16，當(dāng)α=0.2時(shí)，DC16=551.141，且它在整個(gè)網(wǎng)絡(luò)中的排名最高；當(dāng)α=0.4, 0.6, 0.8時(shí)，DC16的值分別為： 64 460.341、 142 811 257 731 289、 3.604 089 454 264 42e+25，節(jié)點(diǎn)16對(duì)應(yīng)的排名分別為1、5、4、4，由此也可知，盡管隨著α的變化，節(jié)點(diǎn)16的動(dòng)態(tài)中心性也發(fā)生了變化，但它在整個(gè)網(wǎng)絡(luò)中的重要性排名仍然靠前。由于樣本較少，用Lilliefors檢驗(yàn)方法檢驗(yàn)DC的統(tǒng)計(jì)特征，檢驗(yàn)結(jié)果表明不同α?xí)r，DC并不具有正態(tài)性。

圖2 衰落因子α對(duì)VANET動(dòng)態(tài)中心性的影響

圖3為α不同時(shí)VANET中重要節(jié)點(diǎn)排名隨時(shí)間變化的情況，選取排名前五位的重要節(jié)點(diǎn)。由圖3(a)知，當(dāng)α=0.2時(shí)，網(wǎng)絡(luò)中重要節(jié)點(diǎn)的排名隨時(shí)間的變化波動(dòng)比較大，如節(jié)點(diǎn)42，在前30s排名第一，而到了后面排名逐漸降低，但它仍是網(wǎng)絡(luò)中比較重要的節(jié)點(diǎn)。由圖3(b)可知，當(dāng)α=0.4時(shí)，重要節(jié)點(diǎn)排名情況相較于α=0.2時(shí)有細(xì)微變化，排名前五位的重要節(jié)點(diǎn)由42、16、27、35、20變化為42、17、48、8、16。圖3(c)和圖3(d)相比較可發(fā)現(xiàn)，當(dāng)α≥0.6時(shí)，網(wǎng)絡(luò)中重要節(jié)點(diǎn)的動(dòng)態(tài)中心性排名整體上基本趨于穩(wěn)定，重要節(jié)點(diǎn)排序不變，依次為42、8、35、16、27。在VANET中，這些節(jié)點(diǎn)表示的車輛在信息傳送時(shí)起著至關(guān)重要的作用，如果某個(gè)重要節(jié)點(diǎn)受到干擾或破壞，整個(gè)網(wǎng)絡(luò)的連通性和數(shù)據(jù)傳輸效率都會(huì)受到較大的影響，因此，在真實(shí)的VANET中，為了提高網(wǎng)絡(luò)效率，可以加強(qiáng)對(duì)這些節(jié)點(diǎn)的保護(hù)措施。由于這些相對(duì)重要的節(jié)點(diǎn)趨于網(wǎng)絡(luò)的中心地位，在網(wǎng)絡(luò)的信息傳播中也起著關(guān)鍵的作用，所以在信息傳送時(shí)，也可以盡可能地將一些比較重要的信息傳送給這些節(jié)點(diǎn)，由此來(lái)提高網(wǎng)絡(luò)信息傳送的效率。如果遇到緊急情況時(shí)，提高網(wǎng)絡(luò)信息傳送效率也可以避免一些不必要的損失。

圖3 衰落因子α對(duì)VANET重要節(jié)點(diǎn)排名的影響

圖4表示的是在衰落因子α=0、信息保留時(shí)間m=50時(shí)，信息存儲(chǔ)概率γ對(duì)VANET動(dòng)態(tài)中心性的影響。由圖4可知，隨著信息存儲(chǔ)概率γ的增加，網(wǎng)絡(luò)的動(dòng)態(tài)中心性也逐漸增大，但網(wǎng)絡(luò)各節(jié)點(diǎn)的排名趨勢(shì)基本是一致的，節(jié)點(diǎn)的重要性沒(méi)有發(fā)生變化。從圖4中可以看出，在整個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)42排名最高，相對(duì)重要的節(jié)點(diǎn)依次還有35、16、20、27。用Lilliefors檢驗(yàn)方法檢驗(yàn)不同γ時(shí)DC的正態(tài)性，檢驗(yàn)結(jié)果表明DC服從正態(tài)分布，γ為0、0.5和1時(shí)，其正態(tài)分布的均值的置信區(qū)間(95%)分別為[41.425，59.855]、[81.153，117.527]和[932.139,1 344.340]。方差的置信區(qū)間(95%)分別為[27.086,40.406]、[53.457,79.745]和[605.787,903.699]。

圖4 信息存儲(chǔ)概率對(duì)VANET動(dòng)態(tài)中心性的影響(α=0)

圖5為γ分別為0、0.5和1時(shí)重要節(jié)點(diǎn)排名。仿真結(jié)果表明雖然γ的值不同，但重要節(jié)點(diǎn)的排名次序沒(méi)有發(fā)生任何變化(不同γ值的曲線完全重合)。由此可見，節(jié)點(diǎn)重要性具有穩(wěn)定性，且信息存儲(chǔ)概率γ對(duì)其沒(méi)有影響。

圖6是衰落因子α=1和信息存儲(chǔ)概率γ=1時(shí)，信息存儲(chǔ)時(shí)間m對(duì)VANET動(dòng)態(tài)中心性的影響。由圖6可知：信息存儲(chǔ)時(shí)間m越大，網(wǎng)絡(luò)的動(dòng)態(tài)中心性也越大；當(dāng)信息存儲(chǔ)時(shí)間超過(guò)整個(gè)網(wǎng)絡(luò)的時(shí)間時(shí)，動(dòng)態(tài)中心性的值不再發(fā)生變化。盡管節(jié)點(diǎn)動(dòng)態(tài)中心性的值隨著m的增加逐漸增大，但網(wǎng)絡(luò)中各節(jié)點(diǎn)的排名情況沒(méi)有發(fā)生變化，即信息存儲(chǔ)時(shí)間對(duì)VANET中重要節(jié)點(diǎn)排名影響不大。由圖6中可以看出節(jié)點(diǎn)42的排名還是最高的，相對(duì)重要的節(jié)點(diǎn)依次還有8、27、16、35。

圖5 信息存儲(chǔ)概率對(duì)VANET重要節(jié)點(diǎn)排名的影響(γ=0,0.5,1)

圖6 信息存儲(chǔ)時(shí)間對(duì)VANET動(dòng)態(tài)中心性的影響(α=1， γ=1)

上述實(shí)驗(yàn)研究了衰落因子、車輛間信息存儲(chǔ)概率以及車輛間信息存儲(chǔ)時(shí)間等因素對(duì)VANET的動(dòng)態(tài)中心性的影響，實(shí)驗(yàn)結(jié)果表明，與其他社會(huì)網(wǎng)絡(luò)(比如引文網(wǎng)[12])不同, 隨時(shí)間的演化，VANET中的重要節(jié)點(diǎn)保持相對(duì)穩(wěn)定的狀態(tài)，利用該特征可有效提高VANET數(shù)據(jù)包的傳輸效率。

4 結(jié)語(yǔ)

動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是車載自組織網(wǎng)絡(luò)的重要特點(diǎn)之一。本文主要介紹VANET動(dòng)態(tài)中心性的研究方法，給出了VANET動(dòng)態(tài)中心性測(cè)度指標(biāo)，應(yīng)用VanetMobisim車輛仿真軟件研究了衰落因子、車輛間信息存儲(chǔ)概率以及車輛間信息存儲(chǔ)時(shí)間等因素對(duì)VANET動(dòng)態(tài)中心性的影響。通過(guò)對(duì)VANET動(dòng)態(tài)中心性的研究，我們發(fā)現(xiàn)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)具有良好的穩(wěn)定性，一方面，利用這一特征能更好地確定信息傳播中的中繼節(jié)點(diǎn)，從而實(shí)現(xiàn)信息的成功投遞，為開發(fā)新VANET的路由算法提供指導(dǎo)；另一方面，通過(guò)加強(qiáng)對(duì)這些重要節(jié)點(diǎn)的保護(hù)措施，可以提高VANET的網(wǎng)絡(luò)生存性和抗毀性。

References)

[1] IEEE.IEEE Std.802.11p Draft amendment： Wireless LAN Medium Access Control (MAC) and PHYsical layer (PHY) specifications: Wireless Access in Vehicular Environments (WAVE) [S].Piscataway: IEEE, 2005.

[2] Dedicated short range communications [EB/OL].[2016- 09- 21].http://www.wirelesscommunication.nl/reference/chaptr01/dtmmsyst/dsrc/dssr.htm.

[4] AL-SULTAN S, AL-DOORI M M, AL-BAYATTI A H, et al.A comprehensive survey on vehicular Ad Hoc network [J].Journal of Network and Computer Applications, 2014, 37: 380-392.

[5] PALLIS G, KATAROS D, DIKAIAKOS M D, et al.On the structure and evolution of vehicular networks [C]// Proceedings of 17th Annual Meeting of the International Symposium on Modelling， Analysis and Simulation of Computer and Telecommunication Systems.New York： ACM， 2009： 502-511.

[6] 張麗麗,陳浩,李臣明,等.城市環(huán)境下基于拓?fù)涮匦缘能囕v自組網(wǎng)建模[J].軟件學(xué)報(bào),2013,24(S1):51-61.(ZHANG L L, CHEN H, LI C M, et al.Modeling the vehicular Ad Hoc networks based on topology characteristics in urban scenario [J].Journal of Software, 2013, 24(S1): 51-61.)

[7] ZHANG H, LI J.Modeling and dynamical topology properties of VANET based on complex networks theory [J].AIP Advances, 2015, 5(1): 017150.

[8] NABOULSI D, FIORE M.On the instantaneous topology of a large-scale urban vehicular network: the cologne case [C]// MobiHoc ’13: Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York: ACM, 2013: 167-176.

[9] DO Y, BUCHEGGER S, ALPCAN T, et al.Centrality analysis in vehicular Ad Hoc networks, Technical Report T-Labs/EPFL [R/OL].EPFL, 2008 [2016- 04- 08].https://infoscience.epfl.ch/record/131211/files/vanet_report.pdf.

[10] HOLME P, SARAMAKI J.Temporal networks[J].Physics Reports， 2012, 519(3): 97-125.

[11] CASTEIGTS A, FLOCCHINI P, QUATTROCIOCCHI S, et al.Time-varying graphs and dynamic networks [J].International Journal of Parallel, Emergent and Distributed Systems,2012,27(5):387-408.

[12] MARRA M, EMROUZNEJAD A, HO W, et al.The value of indirect ties in citation networks: SNA analysis with OWA operator weights [J].Information Sciences, 2015, 314(1): 135-151.

[13] LERMAN K, GHOSH R, KANG J H.Centrality metric for dynamic networks [C]// Proceedings of the the 8th Workshop on Mining and Learning with Graphs.New York: ACM, 2010: 70-77.

[14] VanetMobiSim Project [EB/OL].[2016- 09- 21].http://vanet.eurecom.fr.

[16] 魏達(dá),王沿錫,王健,等.車載自組網(wǎng)移動(dòng)模型綜述[J].計(jì)算機(jī)學(xué)報(bào),2013,36(4):677-700.(WEI D, WANG Y X, WANG J, et al.A survey on mobility models of vehicular Ad Hoc networks[J].Chinese Journal of Computers, 2013, 36(4): 677-700.)

[17] TRIEBER M, HELBING D.Realistische Mikrosimulation von Straβenverkehr mit einem einfachen Modell [C]// Proceedings of Symposium Simulations Technik.Rostock, Germany： ASIM, 2002: 514-520.

This work is partially supported by the National Natural Science Foundation of China (61363081, 71561024), the Fundamental Research Funds for the Gansu Universities, the Natural Science Foundation of Gansu Province (1506RJZA121).

FENG Huifang, born in 1971, Ph.D., professor.Her research interests include wireless mobile network, network performance analysis, complex network.

WANG Junxia, born in 1993, M.S.candidate.Her research interests include vehicular Ad Hoc network.

Dynamic centrality analysis of vehicle Ad Hoc networks

FENG Huifang*, WANG Junxia

(CollegeofMathematicsandStatistics,NorthwestNormalUniversity,LanzhouGansu730070,China)

Dynamic network topology is one of the important characteristics of vehicle Ad Hoc networks (VANET).Based on Intelligent Driver Model with Lane Changes (IDM-LC), the VanetMobiSim was used to study the dynamic centrality of topology for VANET in detail.The temporal network model of VANET was built.The evaluation method of dynamic centrality based on the attenuation factor and information store-and-forward index was established, which not only can describe the relation between the current network topology and the historical one, but also can depict the store-and-forward mechanism of information transmission in VANET.Finally, the dynamic centrality of VANET was analyzed through the simulation experiment.The results show that although the dynamic centrality of VANET topology varies with time and parameters, the ranking of important nodes remains relatively stable.This conclusion not only can help us identify the relay nodes of information transmission better to achieve the successful delivery of information, but also provides guidance for invulnerability of VANET topology.

Vehicle Ad hoc Network (VANET); dynamic centrality; important node; ranking; simulation

2016- 08- 03;

2016- 09- 28。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61363081, 71561024)；甘肅省高等學(xué)?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目；甘肅省自然科學(xué)基金資助項(xiàng)目(1506RJZA121)。

馮慧芳(1971—)，女，甘肅古浪人，教授，博士，CCF會(huì)員，主要研究方向：移動(dòng)無(wú)線網(wǎng)絡(luò)、網(wǎng)絡(luò)性能分析、復(fù)雜網(wǎng)絡(luò)； 王俊霞(1993—)，女，甘肅平?jīng)鋈?，碩士研究生，主要研究方向：車載自組織網(wǎng)絡(luò)。

1001- 9081(2017)02- 0445- 05

10.11772/j.issn.1001- 9081.2017.02.0445

TP

A