基于車(chē)輛軌跡社會(huì)屬性的VANETs路由算法

周 鵬,肖曉強(qiáng),寧偉勛

(國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

基于車(chē)輛軌跡社會(huì)屬性的VANETs路由算法

周 鵬,肖曉強(qiáng),寧偉勛

(國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

出租車(chē)的GPS軌跡數(shù)據(jù)在發(fā)展智慧交通方面有很大的潛力。通過(guò)分析這些數(shù)據(jù)可以發(fā)現(xiàn)車(chē)輛之間存在的社會(huì)關(guān)系或?qū)傩裕@些發(fā)掘出來(lái)的信息對(duì)于設(shè)計(jì)出性能更優(yōu)的VANETs路由算法可以進(jìn)行更好的指導(dǎo)。通過(guò)對(duì)GPS軌跡數(shù)據(jù)進(jìn)行分析，獲得了車(chē)輛節(jié)點(diǎn)的中心性和偏好活動(dòng)區(qū)域；依據(jù)節(jié)點(diǎn)的這些屬性，設(shè)計(jì)了基于中心性的路由和基于偏好性的路由，并進(jìn)一步設(shè)計(jì)了同時(shí)考慮兩者的路由，即TDSAR(Trace Data’s Social Attribute Routing，基于真實(shí)軌跡社會(huì)屬性的路由)；最后借助ONE作為平臺(tái)，模擬路由算法并對(duì)算法的性能進(jìn)行了評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明，在測(cè)試場(chǎng)景下，TDSAR算法可以在保持較小開(kāi)銷(xiāo)并保證傳輸延時(shí)不提高的前提下，獲得較高的投遞成功率。通過(guò)深入的挖掘車(chē)輛間的社會(huì)關(guān)系，有助于更好地選擇中繼節(jié)點(diǎn)，從而促進(jìn)VANETs的發(fā)展。

GPS軌跡數(shù)據(jù)；車(chē)載自組織網(wǎng)絡(luò)；社會(huì)屬性；路由算法；模擬

0 引 言

MANETs(Mobile Ad hoc NETworks，移動(dòng)自組織網(wǎng)絡(luò))是由可以自由移動(dòng)且能夠自主管理路由信息的無(wú)線節(jié)點(diǎn)組成。而當(dāng)網(wǎng)絡(luò)中的通信發(fā)生在車(chē)輛之間或者車(chē)與路邊設(shè)施之間時(shí)，稱之為VANETs(Vehicular Ad hoc NETworks，車(chē)載自組織網(wǎng)絡(luò))[1]。機(jī)會(huì)網(wǎng)絡(luò)是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)網(wǎng)絡(luò)通信的自組織網(wǎng)絡(luò)。在機(jī)會(huì)網(wǎng)絡(luò)中，數(shù)據(jù)的傳輸也是多跳的，消息由中間節(jié)點(diǎn)作為路由轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)。機(jī)會(huì)路由的一大特點(diǎn)就是“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”機(jī)制[2]。VANETs具有網(wǎng)絡(luò)拓?fù)渥兓臁⒕W(wǎng)絡(luò)容量有限等特點(diǎn)，其通信鏈路的建立也是隨機(jī)的，因此VANETs也是一種典型的機(jī)會(huì)網(wǎng)絡(luò)。然而一些傳統(tǒng)的路由算法無(wú)法滿足這類(lèi)網(wǎng)絡(luò)的通信，一些新的路由協(xié)議應(yīng)運(yùn)而生[3]。

現(xiàn)階段已經(jīng)有很多通過(guò)對(duì)出租車(chē)GPS信息的分析而在智慧交通方面取得進(jìn)展的項(xiàng)目。當(dāng)VANETs的節(jié)點(diǎn)只有出租車(chē)時(shí)，就可以通過(guò)對(duì)出租車(chē)的GPS軌跡信息進(jìn)行分析，然后結(jié)合社會(huì)關(guān)系根據(jù)分析得到的結(jié)論對(duì)路由算法進(jìn)行合理的設(shè)計(jì)，提高網(wǎng)絡(luò)的通信性能[4-5]。

文中通過(guò)對(duì)一個(gè)城市的出租車(chē)GPS軌跡數(shù)據(jù)進(jìn)行分析處理，提取出租車(chē)之間的社會(huì)關(guān)系。然后根據(jù)這些關(guān)系，借鑒現(xiàn)有的路由算法，設(shè)計(jì)出基于社會(huì)關(guān)系的路由算法。通過(guò)模擬器對(duì)路由算法進(jìn)行模擬，并與其他的路由算法的結(jié)果進(jìn)行比較，評(píng)價(jià)新的路由算法的性能。

1 相關(guān)工作

目前已有一些協(xié)議通過(guò)分析網(wǎng)絡(luò)中節(jié)點(diǎn)之間的社會(huì)關(guān)系，預(yù)測(cè)節(jié)點(diǎn)的移動(dòng)、相遇等信息，設(shè)計(jì)出旨在提高報(bào)文投遞成功率和節(jié)省網(wǎng)絡(luò)開(kāi)銷(xiāo)的路由算法[6-7]。BubbleRap算法[8]提出了分布式的方法來(lái)探測(cè)網(wǎng)絡(luò)中的社區(qū)，然后用節(jié)點(diǎn)中心度的概念對(duì)節(jié)點(diǎn)排序，從而選擇更好的轉(zhuǎn)發(fā)節(jié)點(diǎn)。SimBet算法[9]是基于社會(huì)互動(dòng)的轉(zhuǎn)發(fā)協(xié)議，利用中心性和社會(huì)相似性的概念來(lái)定義節(jié)點(diǎn)與目的地發(fā)生聯(lián)系的概率。PeopleRank算法[10]是基于Google的PageRank算法，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)按照其重要性排序，當(dāng)節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)時(shí)，會(huì)選擇排在更靠前的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。類(lèi)似的算法還有SREP[2]。因?yàn)榭紤]到成本等因素，大多數(shù)路由協(xié)議的提出是通過(guò)對(duì)節(jié)點(diǎn)社會(huì)行為進(jìn)行分析并通過(guò)模擬器來(lái)對(duì)算法進(jìn)行評(píng)價(jià)的。而在機(jī)會(huì)路由中，3R[11]的提出是基于對(duì)真實(shí)軌跡的觀察，通過(guò)分析一百多部手機(jī)的移動(dòng)軌跡，總結(jié)出節(jié)點(diǎn)相遇的規(guī)律，并基于真實(shí)的軌跡驗(yàn)證該算法。

城市車(chē)輛的軌跡能夠反映車(chē)輛較頻繁的聚集地，這些數(shù)據(jù)可以較精確地指示大多數(shù)人們想要去的地區(qū)—即城市的熱點(diǎn)地區(qū)，從而方便城市的規(guī)劃。人們通過(guò)定義“擁擠度”的概念，通過(guò)比較不同地域“擁擠度”的大小來(lái)確定城市的熱點(diǎn)地區(qū)[5]。根據(jù)從車(chē)輛真實(shí)軌跡數(shù)據(jù)發(fā)掘出來(lái)的車(chē)輛間的社會(huì)關(guān)系，可以對(duì)路由協(xié)議的設(shè)計(jì)起到一定的指導(dǎo)作用。在VANETs路由的研究中，由于3R算法利用的節(jié)點(diǎn)軌跡規(guī)律顯然無(wú)法適用于車(chē)載網(wǎng)絡(luò)，所以可以先結(jié)合車(chē)輛的GPS軌跡數(shù)據(jù)分析車(chē)輛的移動(dòng)規(guī)律，然后根據(jù)其規(guī)律提出相應(yīng)的路由算法，再對(duì)算法進(jìn)行驗(yàn)證。

2 GPS軌跡數(shù)據(jù)分析

考慮車(chē)輛的社會(huì)關(guān)系時(shí)，不可避免地要考慮到車(chē)輛的“中心性”。這里的“中心性”是從社會(huì)網(wǎng)絡(luò)引申而來(lái)的概念，它與車(chē)輛和其他出租車(chē)“相遇”的次數(shù)相關(guān)。“相遇”在機(jī)會(huì)網(wǎng)絡(luò)中是指兩個(gè)節(jié)點(diǎn)達(dá)到能夠建立通信的距離內(nèi)，例如同向而行的兩個(gè)節(jié)點(diǎn)一直保持著距離d，而車(chē)輛通信范圍是r(d

r>

(1)

其中，r表示車(chē)輛的通信范圍；x、y、θ分別表示節(jié)點(diǎn)的X、Y坐標(biāo)以及運(yùn)動(dòng)方向；v表示節(jié)點(diǎn)的速度；Δt表示兩個(gè)節(jié)點(diǎn)GPS記錄的時(shí)間差。根據(jù)相遇的概念，顯然此處的Δt是一個(gè)較小的值，因此Δt需要滿足如下條件：

Δt

(2)

當(dāng)滿足上述兩個(gè)公式時(shí)，表示兩節(jié)點(diǎn)相遇。通過(guò)計(jì)算與當(dāng)前節(jié)點(diǎn)相遇的節(jié)點(diǎn)數(shù)，可以確定節(jié)點(diǎn)的“中心性”，計(jì)算方式如下：

(3)

其中，Ck表示節(jié)點(diǎn)k的“中心性”；n表示出租車(chē)的采樣總數(shù)，此次用到的出租車(chē)數(shù)量為453；ek表示k節(jié)點(diǎn)與其他節(jié)點(diǎn)相遇的次數(shù)。

根據(jù)上面的公式，可以編寫(xiě)程序?qū)PS軌跡數(shù)據(jù)進(jìn)行處理，得到每輛車(chē)的“中心性”。

在社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)具有“偏好性”，即節(jié)點(diǎn)偏好于在某一塊區(qū)域運(yùn)動(dòng)。同樣，通過(guò)分析車(chē)輛GPS軌跡數(shù)據(jù)，可以找到車(chē)輛節(jié)點(diǎn)的“偏好性”。出租車(chē)的運(yùn)動(dòng)是具有偏向性的，即車(chē)輛會(huì)經(jīng)常性在某一個(gè)區(qū)域內(nèi)活動(dòng)，這個(gè)區(qū)域定義如式(4)，為節(jié)點(diǎn)的“偏好區(qū)”。

D=(R,O)

(4)

其中，R表示“偏好區(qū)半徑”；O表示區(qū)域的圓心。

出租車(chē)的起步價(jià)是為了促進(jìn)司機(jī)選擇更近的路徑到達(dá)目的地，起步公里數(shù)的選取主要依據(jù)是車(chē)輛載客活動(dòng)距離大多在該范圍內(nèi)。所以，此處車(chē)輛節(jié)點(diǎn)的“偏好區(qū)”半徑的選擇就是以此為依據(jù)。而深圳市起步公里數(shù)為2 km，最終確定“偏好區(qū)”半徑R的值為2 000 m。

在確定了偏好半徑后，就需要找到圓心O。由于只需要找到一個(gè)偏好區(qū)域的圓心，所以根據(jù)基于密度的聚類(lèi)算法，分別以該節(jié)點(diǎn)各個(gè)時(shí)間的位置為圓心，計(jì)算以此為圓心的偏好區(qū)域的節(jié)點(diǎn)散落密度。當(dāng)某個(gè)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)散落密度最大時(shí)，該點(diǎn)就是“偏好區(qū)”的中心O。

3 路由算法設(shè)計(jì)

車(chē)輛的社會(huì)屬性能夠體現(xiàn)車(chē)輛的運(yùn)動(dòng)規(guī)律，從而指導(dǎo)路由算法的設(shè)計(jì)[12-13]。通過(guò)之前對(duì)車(chē)輛GPS軌跡數(shù)據(jù)的分析，得到了車(chē)輛的“中心性”和“偏好區(qū)”。路由算法設(shè)計(jì)的原則就是要盡可能地節(jié)省開(kāi)銷(xiāo)和降低傳輸延時(shí)。對(duì)VANETs來(lái)說(shuō)，消息的傳遞必然要是多跳的，所以中繼節(jié)點(diǎn)的選擇對(duì)算法的效率有很大影響。而節(jié)點(diǎn)的“中心性”和“偏好性”能夠幫助節(jié)點(diǎn)在轉(zhuǎn)發(fā)時(shí)更好地選擇下一跳節(jié)點(diǎn)。

對(duì)于由出租車(chē)組成的VANETs來(lái)說(shuō)，目標(biāo)節(jié)點(diǎn)的位置并不是固定的，其快速變化的網(wǎng)絡(luò)拓?fù)涞忍攸c(diǎn)決定了基于位置、拓?fù)洹⒓旱穆酚伤惴ǘ际遣缓线m的。因此，當(dāng)考慮節(jié)點(diǎn)之間的社會(huì)關(guān)系時(shí)，會(huì)發(fā)現(xiàn)節(jié)點(diǎn)的某些屬性使得相互之間的相遇具有一定的可預(yù)測(cè)性。所以，面對(duì)可能正在移動(dòng)著的目標(biāo)節(jié)點(diǎn)，這種可預(yù)測(cè)性能夠幫助消息更快地傳遞到目標(biāo)節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)的兩種屬性，可以分別針對(duì)其中一種設(shè)計(jì)路由算法，還可以將兩者結(jié)合起來(lái)設(shè)計(jì)路由。

3.1基于中心性的路由算法

由于之前已經(jīng)計(jì)算了節(jié)點(diǎn)的中心性，所以在設(shè)計(jì)路由時(shí)，中心性可以作為先驗(yàn)知識(shí)。中繼節(jié)點(diǎn)在選擇下一跳節(jié)點(diǎn)時(shí)，需要比較其鄰居節(jié)點(diǎn)的中心性大小。選擇一個(gè)中心性值最大的節(jié)點(diǎn)作為下一跳，如果沒(méi)有任何節(jié)點(diǎn)的中心性值比自己大，該節(jié)點(diǎn)不進(jìn)行轉(zhuǎn)發(fā)，仍將消息存儲(chǔ)在本節(jié)點(diǎn)。基于中心性的算法如算法1所示。

算法1：

Input List(neighbors),Ck,n

Output Relay

Variablei，max_C,index;

max_C=Ck；

for(i=0;i

if(max_C

max_C=List[i].GetCentre();

index=i;

}

}

Relay=List[index];

當(dāng)前節(jié)點(diǎn)k與其他節(jié)點(diǎn)相遇之后，其他節(jié)點(diǎn)作為鄰居，會(huì)被當(dāng)前節(jié)點(diǎn)存入到鄰居列表中。List(neighbors)表示當(dāng)前節(jié)點(diǎn)的鄰居列表，在建立鄰居列表時(shí)，鄰居節(jié)點(diǎn)的中心性也被當(dāng)前節(jié)點(diǎn)獲取。List[i].GetCentre()是獲取節(jié)點(diǎn)的中心性，通過(guò)遍歷鄰居列表中n個(gè)節(jié)點(diǎn)的中心性，與自身的中心性比較，然后返回包括自己在內(nèi)的中心性最大的點(diǎn)，以該點(diǎn)作為下一跳節(jié)點(diǎn)，如果返回值是自己，則不轉(zhuǎn)發(fā)。

3.2基于偏好性的路由算法

根據(jù)上文的分析，每個(gè)車(chē)輛節(jié)點(diǎn)都有其“偏好區(qū)”。顯然當(dāng)兩個(gè)節(jié)點(diǎn)的“偏好區(qū)”重合率越高，兩個(gè)節(jié)點(diǎn)相遇的可能性越大。基于上述原因，“偏好區(qū)”的重合率可以作為路由算法設(shè)計(jì)時(shí)選擇下一跳節(jié)點(diǎn)的依據(jù)。當(dāng)重合率越高，則被選為下一中繼節(jié)點(diǎn)的可能性越大。

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的偏好屬于先驗(yàn)知識(shí)，雖然目標(biāo)節(jié)點(diǎn)的位置會(huì)改變，但是其偏好是社會(huì)屬性，在設(shè)計(jì)路由算法時(shí)可以認(rèn)為它是不變的。基于偏好性的路由同樣是在與其他節(jié)點(diǎn)相遇時(shí)獲取鄰居節(jié)點(diǎn)的“偏好區(qū)”，再結(jié)合目標(biāo)節(jié)點(diǎn)的“偏好區(qū)”，從而確定下一個(gè)中繼節(jié)點(diǎn)。路由算法如下：

算法2：

Input List(neighbors),Dk,Dd,n

Output Relay

Variablei，max_L,index;

max_L=Calculate_lap(Dk,Dd)；

for(i=0;i

if(max_L

max_L=Calculate_lap(Dd，List[i].GetD());

index=i;

}

}

Relay=List[index];

重疊區(qū)域的計(jì)算函數(shù)為Calculate_lap(Dk,Dd)。該函數(shù)的返回值為重合率L，輸入是節(jié)點(diǎn)的“偏好區(qū)”—D，包含了兩個(gè)節(jié)點(diǎn)的圓心和偏好半徑，根據(jù)解析幾何可以算出重疊區(qū)域Z，然后返回Z與兩個(gè)重疊后面積之比即為重合率。重合率L的計(jì)算方法如式(5)所示。

arccos(d/2R)

(5)

其中，d為兩個(gè)節(jié)點(diǎn)偏好中心的距離，它可以由偏好中心的坐標(biāo)求得；R為偏好半徑。

當(dāng)前節(jié)點(diǎn)通過(guò)遍歷鄰居列表并計(jì)算出鄰居節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的“偏好區(qū)”重合率后，同樣要比較重合率的大小，如果當(dāng)前節(jié)點(diǎn)k的重合率高于所有鄰居節(jié)點(diǎn)，則不轉(zhuǎn)發(fā)消息；否則，選擇鄰居節(jié)點(diǎn)中重合率最高的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。

3.3綜合性路由算法

如果在設(shè)計(jì)路由算法時(shí)將節(jié)點(diǎn)的中心性和偏好性同時(shí)考慮，則需要考慮兩種屬性在選擇中繼節(jié)點(diǎn)時(shí)各自所占的比重。所以可以定義一個(gè)占比因子α(α<1)，從而根據(jù)式(6)來(lái)確定節(jié)點(diǎn)的中繼度R。

R=α*C+(1-α)*L

(6)

根據(jù)中繼度的概念，當(dāng)前節(jié)點(diǎn)可以遍歷其鄰居列表，從而獲得鄰居節(jié)點(diǎn)的中繼度。類(lèi)似的，如果當(dāng)前節(jié)點(diǎn)自身的中繼度比鄰居節(jié)點(diǎn)都大，則不進(jìn)行消息轉(zhuǎn)發(fā)；否則，選擇中繼度最大的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。

對(duì)于占比因子α的確定在路由算法設(shè)計(jì)階段沒(méi)有好的方法，所以需要在性能評(píng)價(jià)階段取不同的α值，通過(guò)比較不同值下路由算法的性能來(lái)確定α的值。實(shí)際上，基于中心性和基于偏好性的路由算法是綜合性算法中α分別取1和0得到的。

4 性能評(píng)價(jià)

本節(jié)主要對(duì)上文提出的三種路由算法的性能進(jìn)行評(píng)價(jià)，從而了解新的路由算法在VANETs通信中的性能相比于其他的路由協(xié)議是否有提升。評(píng)價(jià)方法是建立一個(gè)模擬器分別對(duì)不同的路由算法進(jìn)行模擬，得到相應(yīng)的消息傳輸延時(shí)和數(shù)據(jù)分發(fā)成功率。

由于路由算法是通過(guò)分析GPS軌跡數(shù)據(jù)后設(shè)計(jì)出來(lái)的，建立模擬器時(shí)，節(jié)點(diǎn)的移動(dòng)模型就不能隨意選擇。為了更準(zhǔn)確地評(píng)價(jià)算法的性能，模擬器中節(jié)點(diǎn)的移動(dòng)仍然由GPS軌跡確定。ONE是一個(gè)專業(yè)的適用于DTN的網(wǎng)絡(luò)模擬器，對(duì)于VANETs來(lái)說(shuō)，它能夠更好地模擬移動(dòng)和通信場(chǎng)景，更具有真實(shí)性，同樣也更加便于使用。

由于模擬場(chǎng)景是由GPS軌跡數(shù)據(jù)決定的，因此通過(guò)OpenStreetMap獲取深圳市的地圖，并將其轉(zhuǎn)換成WKT格式導(dǎo)入模擬器中。模擬器的場(chǎng)景是20 000 m*40 000 m的區(qū)域，節(jié)點(diǎn)數(shù)量為450。節(jié)點(diǎn)的移動(dòng)軌跡是將兩天的GPS軌跡數(shù)據(jù)轉(zhuǎn)換成ONE可以導(dǎo)入的WKT數(shù)據(jù)。首先取不同的α值來(lái)模擬路由算法，這樣上文所述的三種路由算法都可以完成模擬。α的取值分別為0，0.2，0.4，0.6，0.8，1。因?yàn)樗惴ㄊ腔谵D(zhuǎn)發(fā)的路由，所以數(shù)據(jù)傳輸?shù)拈_(kāi)銷(xiāo)是接近的，模擬后發(fā)現(xiàn)節(jié)點(diǎn)的傳輸時(shí)延也是相近的，出現(xiàn)這種現(xiàn)象可能是因?yàn)橥哆f成功率較低，延遲受消息的生存時(shí)間影響較大。不同TTL下模擬后的數(shù)據(jù)投遞率如圖1所示。

圖1 數(shù)據(jù)投遞成功率

根據(jù)圖1可知，TTL對(duì)消息的投遞成功率有較大的影響。在α值為0.4時(shí)，算法的性能更好一些。從這一點(diǎn)可以看出，在文中采用的數(shù)據(jù)中，由于中心性的相似性較大，所以偏好性對(duì)路由的影響更大一些。

然后，選取FirstContact、Epidemic和Prophet這幾種經(jīng)典的DTN路由協(xié)議進(jìn)行模擬，將模擬結(jié)果同α等于0.4時(shí)的綜合性路由協(xié)議進(jìn)行比較，結(jié)果如圖2所示。

圖2 對(duì)比結(jié)果

從圖中可以看出，TDSAR路由的開(kāi)銷(xiāo)和FirstContact路由的開(kāi)銷(xiāo)基本相同，但是其消息的投遞成功率隨著TTL的增大逐漸增加。可以預(yù)見(jiàn)，在特定的場(chǎng)景下，取合理的TTL值，可以使得TDSAR算法在使用時(shí)以極小的開(kāi)銷(xiāo)獲得較理想的投遞成功率。

5 結(jié)束語(yǔ)

通過(guò)分析出租車(chē)GPS軌跡數(shù)據(jù)，提出了基于社會(huì)屬性的VANETs路由協(xié)議。首先考慮GPS軌跡數(shù)據(jù)的潛在價(jià)值，通過(guò)統(tǒng)計(jì)、聚類(lèi)等方式分析GPS軌跡數(shù)據(jù)，得到了車(chē)輛節(jié)點(diǎn)的兩種社會(huì)屬性——“中心性”和“偏好區(qū)”；然后根據(jù)這兩種屬性分別設(shè)計(jì)了基于中心性和偏好性的以及綜合考慮兩種屬性的路由算法；接著通過(guò)ONE模擬器對(duì)新設(shè)計(jì)的路由算法進(jìn)行了模擬，并找到合適的α值。在對(duì)其他經(jīng)典的路由算法進(jìn)行模擬后，通過(guò)比較發(fā)現(xiàn)，文中路由算法在該場(chǎng)景下的性能有顯著提升。

未來(lái)的研究方向是讓節(jié)點(diǎn)可以根據(jù)其前一段時(shí)間的移動(dòng)軌跡來(lái)自我分析，更新其中心性和偏好中心。

[1] Gutiérrez D,García-Campos J M,Sánchez-García J,et al.An evaluation methodology for reliable simulation based studies of routing protocols in VANETs[J].Simulation Modelling Practice & Theory,2016,66:139-165.

[2] Xie X, Zhang Y, Dai C,et al.Social relationship enhanced predicable routing in opportunistic network[C]//International conference on mobile ad-hoc & sensor networks.[s.l.]:IEEE,2011:268-275.

[3] Bonola M, Bracciale L, Loreti P, et al. Opportunistic communication in smart city:experimental insight with small-scale taxi fleets as data carriers[J].Ad Hoc Networks,2016,43:43-55.

[4] Feng H,Xu Y.An empirical study on evolution of the connectivity for VANETs based on taxi GPS traces[J].International Journal of Distributed Sensor Networks,2016(3):1-11.

[5] Castro P S,Zhang D,Chen C,et al.From taxi GPS traces to social and community dynamics:a survey[J].ACM Computing Surveys,2013,46(2):1167-1182.

[6] Vegni A M,Loscri V.A survey on vehicular social networks[J].IEEE Communications Surveys & Tutorials,2015,17(4):2397-2419.

[7] Mota V F S,Cunha F D,Macedo D F,et al.Protocols,mobility models and tools in opportunistic networks:a survey[J].Computer Communications,2014,48(8):5-19.

[8] Pan H,Crowcroft J,Yoneki E.BUBBLE rap:social-based forwarding in delay-tolerant networks[J].IEEE Transactions on Mobile Computing,2011,10(11):1576-1589.

[9] Daly E,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs[C]//Proceedings of the 8th ACM international symposium on mobile ad hoc networking and computing.[s.l.]:ACM,2007:32-40.

[10] Mtibaa A,May M,Diot C,et al.Peoplerank:social opportunistic forwarding[C]//Proceedings of IEEE INFOCOM.[s.l.]:IEEE,2010:111-115.

[11] Long V,Do Q,Nahrstedt K.3R:fine-grained encounter-based routing in delay tolerant networks[C]//IEEE international symposium on a world of wireless mobile & multimedia networks.[s.l.]:IEEE,2011:1-6.

[12] 王 翔,冷甦鵬,張 可,等.車(chē)聯(lián)社會(huì)網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2015,36(1):199-210.

[13] 宋志華,暴建民,謝元發(fā),等.一種基于聯(lián)絡(luò)歷史的車(chē)載容遲網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(7):196-199.

AVANETsRoutingAlgorithmBasedonTraceData’sSocialAttribute

ZHOU Peng，XIAO Xiao-qiang，NING Wei-xun

(School of Computer，National University of Defense Technology，Changsha 410073，China)

The GPS trace data for taxi has great potential in the development of intelligent transportation.By analysis of the data,the social relations or attributes between vehicles can be found,which could play a guiding role in design of VANETs routing with greater performance.The vehicle nodes’ centricity and preference are obtained through analysis of the GPS trace data,and based on these properties,the routing algorithms are designed based on both centricity and preference,as well as both of them,which is named TDSAR(Trace Data’s Social Attribute Routing).Finally,with the ONE as the platform,the routing algorithm is simulated and its performance is evaluated.The results show that TDASR could get high delivery ratio on the premise of lower occupancy and stable delay.Through the in-depth mining of the vehicular relationships,the VANETs could get a better development when the better relay nodes are chosen.

GPS trace data;vehicular ad hoc networks;social attributes;routing algorithm;simulation

2017-01-11

2017-05-17 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272485)

周 鵬(1993-)，男，碩士研究生，通信作者，研究方向?yàn)檐?chē)載網(wǎng)絡(luò)及其性能評(píng)價(jià)；肖曉強(qiáng)，博士，教授，研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)與移動(dòng)計(jì)算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1600.086.html

TP393

A

1673-629X(2017)11-0028-05

10.3969/j.issn.1673-629X.2017.11.006