周 鵬,肖曉強,寧偉勛

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

基于車輛軌跡社會屬性的VANETs路由算法

周 鵬,肖曉強,寧偉勛

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

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

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

r>

(1)

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

Δt

(2)

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

(3)

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

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

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

D=(R,O)

(4)

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

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

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

3 路由算法設(shè)計

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

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

3.1基于中心性的路由算法

由于之前已經(jīng)計算了節(jié)點的中心性，所以在設(shè)計路由時，中心性可以作為先驗知識。中繼節(jié)點在選擇下一跳節(jié)點時，需要比較其鄰居節(jié)點的中心性大小。選擇一個中心性值最大的節(jié)點作為下一跳，如果沒有任何節(jié)點的中心性值比自己大，該節(jié)點不進(jìn)行轉(zhuǎn)發(fā)，仍將消息存儲在本節(jié)點?；谥行男缘乃惴ㄈ缢惴?所示。

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

3.2基于偏好性的路由算法

根據(jù)上文的分析，每個車輛節(jié)點都有其“偏好區(qū)”。顯然當(dāng)兩個節(jié)點的“偏好區(qū)”重合率越高，兩個節(jié)點相遇的可能性越大?；谏鲜鲈?，“偏好區(qū)”的重合率可以作為路由算法設(shè)計時選擇下一跳節(jié)點的依據(jù)。當(dāng)重合率越高，則被選為下一中繼節(jié)點的可能性越大。

網(wǎng)絡(luò)中每個節(jié)點的偏好屬于先驗知識，雖然目標(biāo)節(jié)點的位置會改變，但是其偏好是社會屬性，在設(shè)計路由算法時可以認(rèn)為它是不變的?；谄眯缘穆酚赏瑯邮窃谂c其他節(jié)點相遇時獲取鄰居節(jié)點的“偏好區(qū)”，再結(jié)合目標(biāo)節(jié)點的“偏好區(qū)”，從而確定下一個中繼節(jié)點。路由算法如下：

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

arccos(d/2R)

(5)

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

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

3.3綜合性路由算法

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

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

(6)

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

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

4 性能評價

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

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

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

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

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

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

圖2 對比結(jié)果

從圖中可以看出，TDSAR路由的開銷和FirstContact路由的開銷基本相同，但是其消息的投遞成功率隨著TTL的增大逐漸增加?？梢灶A(yù)見，在特定的場景下，取合理的TTL值，可以使得TDSAR算法在使用時以極小的開銷獲得較理想的投遞成功率。

5 結(jié)束語

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

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

[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] 王 翔,冷甦鵬,張 可,等.車聯(lián)社會網(wǎng)絡(luò)綜述[J].通信學(xué)報,2015,36(1):199-210.

[13] 宋志華,暴建民,謝元發(fā),等.一種基于聯(lián)絡(luò)歷史的車載容遲網(wǎng)絡(luò)路由算法[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ò)出版時間

時間：2017-08-01

國家自然科學(xué)基金資助項目(61272485)

周 鵬(1993-)，男，碩士研究生，通信作者，研究方向為車載網(wǎng)絡(luò)及其性能評價；肖曉強，博士，教授，研究方向為無線網(wǎng)絡(luò)與移動計算。

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