基于VANETs下的決策樹多副本機會路由協議

劉輝元，董春陽，黃 瓊

(1.重慶市工業學校，重慶 40043; 2.重慶郵電大學信息產業部移動通信技術重點實驗室，重慶400065)

基于VANETs下的決策樹多副本機會路由協議

劉輝元1,2，董春陽2，黃 瓊2

(1.重慶市工業學校，重慶 40043; 2.重慶郵電大學信息產業部移動通信技術重點實驗室，重慶400065)

在車載自組織網絡(vehicular Ad hoc networks, VANETs)中，當節點緩存和消息副本數目被限制的情況下，如何合理地選擇車載網絡的路由節點是實現VANETs高效轉發和投遞的關鍵問題。為此提出了一種基于學習方法的決策樹理論的多副本VANETs機會路由協議(D-Tree)。D-Tree將VANETs中節點間的傳輸和連接因素看做多個屬性的集合，并與決策樹方法得到一個消息轉發規則，同時結合多副本路由與機會路由的“存儲─攜帶─轉發”優勢進行消息投遞。真實數據集上的實驗結果表明，在場景密集的情況下，D-Tree相比于Bubble和S&W路由算法投遞成功率提高了近10%，同時在投遞延遲等方面也具有明顯優勢。

車載自組織網絡(VANETs)；機會路由；路由算法；決策樹；多副本

0 引 言

車載自組織網絡(vehicular Ad hoc networks, VANETs)[1]是專門為了車輛之間通信而設計的自組織網絡，它屬于移動Ad-hoc網絡(mobile Ad-hoc network, MANET)的子集，其主要目標是建立一個普通的通信平臺去支持車輛之間各種類型的智能傳輸應用。車聯網是以車際網、車內網和車載移動互聯網為基礎，按照約定的通信協議和數據交互標準，支持車輛─車輛(vehicle 2 vehicle, V2V)、車輛─通信設施(vehicle 2 infrastructure, V2I)之間的通信[2]。

在VANETs應用中，每個車輛節點分布稀疏不均、網絡拓撲變化快以及移動速度快或障礙物造成信號衰減等多種原因都可能導致網絡中大多數節點處于中斷狀態。這種網絡環境中，傳統的MANET通信模式無法有效運行，因此，車載網絡路由協議通常采用“存儲─攜帶─轉發”的機會路由[3]機制或者車載容延容斷網絡(vehicular delay tolerant network, VDTN)[4]進行消息投遞。同時，因為VANETs中的節點在車主的控制下具有一定的人類社會網絡屬性。如公交車沿著固定線路行進，出租車會因車上乘客的需求而進行隨機運動[5]，私家車主們購物、上下班等基本都在一些特定區域，組成的網絡呈現出社會網絡學中“小世界，大世界”現象[5]。

為改善容斷連接VANETs網絡性能，同時提高資源利用率, 需要節點在網絡拓撲信息未知的情況下，充分感知網絡在移動過程中的邏輯結構。因此，車載機會網絡路由的核心問題是一個利用相關知識進行最優化計算選擇合適的下一跳路由節點的決策性問題。因此，一些基于社區的路由算法[6-9]被研究者們提出，它們只是簡單地將社會屬性選擇出來，然后依照選出的社會屬性建立一個效用函數或者采用一種單一的社會屬性值進行數據的下一跳轉發；在此種情形下有可能由于當前網絡情況和副本數限制而錯失綜合性能更高的節點。同時，文獻[10]以節點信任度為基礎，將節點信任度分為以過程基礎和關系基礎的信任方式來進行數據傳輸，并通過結合入侵檢測機制的方式來提高網絡的QoP(quality-of-protection)和用戶QoE(quality of experience)等。

通過對上述問題的分析，本文提出一種基于學習方法的決策樹理論的機會VANETs路由決策算法(D-Tree)，以便能夠更全面地綜合考慮社會屬性之間的影響并進行折衷，優化網絡綜合性能。該算法將VANETs中節點間傳輸和連接的因素看做多個屬性的集合，根據該屬性集合與決策樹方法得到一個消息轉發的決策規則，預測節點的下一個路由能否成功接收數據包，能有效提高網絡性能的指標，降低了節點的路由開銷和投遞延遲等。

1 相關工作

目前，VANETs路由協議可以分為單副本(single copy)和多副本 (multi-copy)路由協議。在單副本路由協議[6]中，每條消息只含有唯一副本；而在多副本協議中，每條消息可以存在多個副本，但又不同于Epidemic算法中每個節點都可以持有該消息副本，只是可以同時有多個節點持有該消息副本。下面主要介紹多副本路由協議。

Spray and Wait[11]算法分為2個階段，Spray階段和Wait階段。在Spray階段，源節點向網絡投入特定數目的L個數據包副本，然后進入Wait階段，若數據包副本在Spray階段沒有發現目的節點，那么攜帶數據包副本的節點將通過Direct Delivery[12-16]方式把數據包副本傳送到目的節點。但是由于沒有考慮到鄰居節點的數量問題，當鄰居節點過多時，會由于源節點過多的“噴灑”造成節點快速死亡。因此,該算法在不考慮鄰居節點選擇的情況下，不能取得較好的效果。

Bubble Rap[8]路由算法也是一種基于社會屬性的路由算法。該算法將轉發策略依賴于2個社團特征(社區和中心度)。消息轉發的2個階段都是基于網絡中心性的轉發。在轉發階段中，當目標節點所有鄰居的網絡中心性都較低，那么消息轉發將失敗，從而導致消息在傳輸過程中的時延急劇增加。

社會屬性感知的數據轉發策略[7](social attributes aware date forwarding strategy,SADFS)路由協議利用節點水平和垂直的社會關系，考慮節點之間的社會關系并以分布式方式估計其自身及其他節點的社會屬性，進而確定攜帶節點與目的節點的關系以進行數據轉發。文獻[12]通過建立時序圖模型預測節點鏈接態勢，為消息分布式的選擇最佳中繼節點進行數據包的轉發。

2 基本定義

通常VANETs包含以下幾個主要元素：車輛節點、路邊設施和車載網絡鏈路。其中， VANETs鏈路是指在所有車輛之間建立起的連接。同時在VANETs中，車載社會網絡與人類社會關系之間存在一定的相互映射等特性。因此，通過利用這些類社會屬性之間的關系，可以更好地為車輛間的通信提供有力的保障。為了方便研究上述現象，本文對這樣的車輛網絡進行了數學抽象并作出了如下定義。

定義1車輛網絡。把車輛網絡定義為一個含有節點和鏈路的連通圖G=(V,E)，其中，V代表車輛節點集合，E為在通信范圍內車輛節點之間的鏈路集合。

對于每個車輛節點vi,vi∈V,i={1,2,…,n}，用集合A描述車輛節點屬性為

(1)

定義3為了能夠在VANETs中對屬性的分類能力進行度量，在此引入車輛網絡信息增益(VehicleGain(A,aj))，即由于使用這個屬性分割樣例而導致的期望熵降低。更精確的講，一種屬性aj相對于樣例集合A在VANETs中的車輛網絡信息增益VehicleGain(A,aj)定義為

(2)

(2)式中：Values(aj)是屬性aj所有可能值的集合；Av是A中屬性aj的值為v的子集(也就是Av={a∈A|aj(a)=v})。需要注意的是(2)式右邊的第2項描述的期望熵就是每個子集的熵的加權和。

定義4為避免車輛信息增益在分類時過度偏袒具有較多值的屬性，引入車輛網絡信息增益比率為

(3)

3 基于D-Tree的路由協議

3.1 VANETs屬性

在機會VANETs中，節點的移動產生了終端之間的直接相遇機會，從而使節點之間可以實現點對點的數據通信。但這種通信鏈路建立的時間不夠確定，鏈路生存時間短，中斷時間長，通信能力受限。常用于描述和表征機會VANETs屬性鏈路特征的術語如下。

1)節點新近度(node recency)。它是基于最近多長時間車輛B遇到網絡中任意車輛x，為車輛之間最近一次建立連接的時間間隔比例。如果將來接觸的概率越高，則說明當前聯系時間與下一次聯系間隔的間隔越短。

2)節點活躍因子[7](node active factor)。節點活躍因子表示車輛節點的活動能力，車輛遇見的其他車輛越頻繁，鄰居列表信息變化越劇烈，說明該車輛越活躍，能夠成功轉發到目的地的機會越大。本文節點活躍因子通過節點在最近一段時間內平均鄰居節點個數來衡量。

3)節點度(node degree)。車輛節點在車輛網絡圖中的度。描述了車載用戶在網絡中的流行程度。車輛之間進行信息傳遞時，車輛節點的度將是路由選擇的一個重要度量值。

4)接近中心度(closeness centrality)。接近中心度表示與其他所有節點具有最短路徑的節點。描述了最高效的路徑和網絡可視性，選取接近中心度最高的節點作為信息分發和擴散的節點，可以有效減少信息擴散時延和網絡開銷。

5)中介中間性(betweenness centrality)。在車輛網絡中，節點作為2個相鄰節點的中間橋梁節點的度量。連接2個車輛節點的中間節點會具有很高的中介中間性，這個中間節點在車輛節點之間信息交互過程中，起到了很關鍵的作用。

6)網絡密度(density)。車載用戶之間的連接密度。描述了網絡中節點之間連接密度的分布。

在上述幾種屬性鏈路特征中，節點新近度和節點活躍因子反應了節點在一定時期內車輛節點自身“活動”能力情況的大小，而節點度、接近中心度等反應了車輛節點在區域性社區或者局部網絡架構中節點相互作用的屬性特征。在同時考慮車輛節點自身與車輛網絡結構的情況下，能夠更加合理地選取下一條路由。

3.2 D-Tree協議

D-Tree主要包括2個階段：擴散階段和轉發階段。在擴散階段，源節點持有的消息副本數量為L(L>1)，如果遇到一個不含該消息的節點，則根據決策規則和二分法擴散副本。在之后的過程中，當節點持有的消息副本數為1且與不含該副本的節點相遇時,則進入轉發階段。在轉發階段，節點只根據決策規則向相遇節點轉發此消息副本。當遇到的節點如果是目的節點，無論是在擴散階段還是轉發階段，都直接向其轉發該消息 。D-Tree協議流程如圖1所示。

3.2.1 基于C4.5的VANETs規則樹算法

在數據收集及預處理后，進行決策樹建立階段。根據3.1節中對機會VANETs屬性概念的定義，并且依照屬性特征值對整個網絡系統的數據進行收集、處理。然后將處理的屬性特征值按照定義3與定義4的過程分別進行處理、計算，并將其按照機器學習算法C4.5[17]對各屬性的重要度進行評級和劃分，學習算法偽代碼如下。

圖1 D-Tree協議流程Fig.1 D-Tree Protocol Processing

算法:Generate_Decision_Tree

算法輸入：訓練樣本samples,候選屬性的集合Attribute-List

算法輸出：決策樹

/* C:類別屬性; test_attribute:測試屬性; */

Create node N

If samples are all in class C Then

return N as leaf node and label it as class C

If Attribute-List Null ThenL return N as leaf node and label it as normal node in samples

Choose the attribute with the highest VehicleGainRatio in Attribute-List

Label node N as Attribute-List

For each aiin Attribute-List

If test-attribute=aithen create branch after node N

set sias another sample with test-attribute=ai

If siis NULL Then

add a leaf node and label it as the most normal class

Else add the node by the return value of

Generate_decision_tree(si,attribute_list,test_attribute)

對計算出的各屬性值，每次選取車輛網絡信息增益比率(VehicleGainRatio(A,aj))最大且獲取的車輛網絡信息增益(VehicleGain(A,aj))又不低于所有屬性平均值的屬性作為樹的節點，每一個分支都是一個可能值，依此遞歸的形成決策樹，直到子集中的數據記錄在主屬性上取值都相同，或沒有屬性可再供劃分使用。

3.2.2 擴散階段

VANETs中的節點通過對網絡屬性的收集和處理，依據建立的決策樹對多副本的消息進行“有向擴散”。對與本節點相遇的節點副本數的副本分配方法采用經典的“二分法”。

3.2.3 轉發階段

消息從源到目的節點轉發延遲取決于搜索樹的延遲、擴散延遲和轉發延遲之和。為降低投遞時延，提高消息投遞成功率。持有單個副本的節點在轉發階段，將按照決策規則向未持有相同消息的節點轉發此消息。

因為持有消息節點與目標在同一個網絡環境中，則只要相遇節點不是目的節點，就按決策規則轉發，這樣更容易將消息傳遞到目標節點區域附近，如果遇到目的節點則直接轉發。因此，在轉發階段采用決策規則轉發，在整個消息的轉發過程中避免盲目轉發，能有效降低消息向目標節點的投遞時延。

3.2.4 算法設計

通過模型分析以及上述擴散階段與轉發階段的分析，可以對D-Tree建立一個算法，算法的偽代碼如下。

算法輸入：消息的源節點S，目標節點D，且當前網絡中所有節點都含有決策樹準則R，消息副本數Copies，下一路由節點Ns，當前消息msg。

If Copies > 1 Then

Copies = Copies/2

Else If Copies = 1 Then

Exit;

For Ns in Ns1,Ns2,…Nsn Do

If (S,Ns) match R Then

Else If Ns is D Then

Break;

End If;

End For;

While Ns carries the msg Do

For Ns’ in Ns1’,Ns2’,…Nsn’Do

If (Ns,Ns’) match R Then

Else If Ns meets with D Then

End If;

End For;

End While;

3.3 規則分析

對于每個攜帶數據包狀態的車輛節點，每個階段的狀態與選擇的轉發決策將影響下一階段的決策。設共有N+1個階段，標記為n=0,1,…,N，其中將開始階段標記為0。設系統在階段n+1時的狀態為Tn(i,a)∈Sn+1(稱Tn為n時的狀態轉移函數)。因此，數據包選擇何種決策規則進行轉發的決策問題可以規劃為如下的模型形式

{Sn,(An(i),i∈Sn),rn(i,a),Tn(i,a),n=

1,2,3,…,N,V}

(4)

目標函數V的常見形式是使各個階段的報酬之和達到最大。

定義階段n時的決策函數為映射

(5)

且滿足條件f(i)∈An(i),i∈Sn。階段n時的決策函數全體記為Fn。f∈Fn的含義是：若系統處于狀態i，且在階段n，則選擇決策f(i)。

因此，策略就是一個決策函數序列

π=(f0,f1,…,fN),f∈Fn,

n=0,1,…,N

(6)

對n=0,1,…,N，fn在階段n時使用。使用策略π是指：若系統在階段n處于狀態i(i∈Sn)，則選擇決策fn(i)(fn(i)∈An(i))。記策略的全體為Π。

下面論述通過C4.5算法生成的決策樹中的規則，一定存在著最優策略。

設決策樹生成的策略π∈Π,且初始狀態為i0∈S0，則可以確定各個階段的狀態in與所選擇的決策an，它們可由in+1=Tn(in,an),an+1=fn+1(in+1),n=0,1,…,N-1遞推得到，從而可以得到階段n的報酬rn(in,an)，進而確定各個階段的報酬之和(稱之為總報酬)。由于這個總報酬值依賴于所選擇的策略，以及初始狀態，因此，我們記為V(π,i0)，即

(7)

(7)式只與所使用的策略π及初始狀態i0有關。稱V(π,i0)為系統在策略π下從初始狀態i0出發時的總報酬。且定義

(8)

(8)式表示初始狀態為i時，所可能獲得的最大總報酬，稱V為決策問題的最優值函數。且在決策規則中，對所有的初始狀態i∈S0一定都成立，即取到(10)式的上確界。根據Bellman最優性原理[19]，則策略π是最優策略，且Vn(π,i)=V(i),i∈S0。即對于車輛節點在每個階段n轉發數據包時，根據決策規則的選擇轉發，一定存在一個最優策略在當前階段進行轉發，使系統的綜合性能得到保障。

4 數據仿真及分析

通過在真實數據集Cambridge的Haggle項目[20]提供校園相遇軌跡數據集和Cabspotting項目[21]提供出租車軌跡的數據集上仿真D-Tree路由協議的性能，與現有的基于社會網絡的多副本路由算法Bubble Rap和多副本路由算法Spray and Wait(S&W)進行了對比。

本文采用機會網絡(opportunistic network environment，ONE)[22]仿真平臺進行性能評估工作。對比了3種路由性能指標：消息投遞成功率，消息被目標節點成功接收的數量與產生的總消息數量之比；平均投遞時延，從消息生成到投遞到目標節點所需要的時間；路由開銷率，所有節點成功轉發數據分組總數與目的節點收到數據分組總數的差和目的節點收到數據分組總數之比。

4.1 參數設置

在Cambridge的Haggle項目中，節點是基于校園終端設備的社會網絡的跟蹤數據采集。車聯網中的社會屬性可以類比于在人類社會生活中，并以此情景模擬移動情況。因此，在基于ONE的仿真平臺下，將速度范圍增大到車輛行駛下的速度大小，同時將運動范圍增大以便模擬車輛在基于社會網絡下的移動場景。在仿真實驗中，場景參數設置情況如表1所示。

Cabspotting項目提供跟蹤出租車軌跡的數據集，該數據集記錄了500個節點的軌跡情況，數據采集時長為 30 天(如果考慮車輛網絡的實際場景，則還存在其他車輛對這個數據集車輛間數據投遞的影響，在本實驗中排出這些因素的影響)。在仿真實驗中，場景參數設置情況與表1相同，只需對仿真時間、網絡區域及節點數進行更改。同時，因為在同一個數據集上重復完整長度的實驗沒有意義，也為了模擬多次隨機實驗，我們將整個數據集依時間分成多段進行模擬。

表1 Haggle參數設置

4.2 生存時間(TTL)對性能的影響

圖2和圖3中分別對比了在Haggle項目和Cabspotting項目數據集下，在不同TTL(time-to-live)限制條件下評估D-Tree的性能，以Spray and Wait等協議作為參考。

圖2 不同TTL的D-Tree的性能對比(Haggle項目)Fig.2 Performance Comparison of different TTL of D-Tree

圖3 不同TTL的D-Tree的性能對比(Cabspotting項目)Fig.3 Performance Comparison of different TTL of D-Tree

從圖2中可以看出，在相同條件下，D-Tree具有較好的性能。Bubble Rap在投遞率方面和D-Tree較為相近，但路由開銷率比D-Tree高了接近20%～30%，這是因為在轉發階段，Bubble Rap轉發的中繼節點比D-Tree多，即轉發的盲目型要比D-Tree大。而Spra yand Wait比兩者都低，是因為Spray and Wait的轉發階段是被動等待，消息副本只會忠實的等待目的節點的到來。同時，在圖2中隨著TTL的增加，由于網絡密度的影響和 Bubble Rap只考慮單社會屬性節點中心度會導致在某一階段節點鄰居中心度無法計算或者都較低，且又因TTL未過期，不能將數據包丟棄，轉發的次數會增多，因此，隨著TTL的增加，Bubble Rap協議的開銷會出現先減小后增大的趨勢。

從圖3中可以看出，在網絡規模大幅增加的情況下，D-Tree仍然具有較好的性能。D-Tree的性能和Spray and Wait較為相近，但投遞率比Spray and Wait略高。D-Tree和Spray and Wait的路由開銷率都比Bubble Rap低分別是因為：D-Tree比Bubble具有較準確的轉發性，而Spray and Wait是因為Wait階段不會對網絡產生較大開銷。且在網絡密度較大的情況下，對于D-Tree和Bubble Rap的社會屬性值會相對較好采集，根據路由開銷的定義，在圖3b中隨著TTL的增加，開銷是遞減的趨勢。

4.3 副本數對性能的影響

圖4和圖5中分別對比了在不同副本數限制條件下評估D-Tree的性能，從圖4中可以看出：隨著副本數的增加，D-Tree的性能在投遞率和投遞延遲都優于Bubble Rap和Spray and Wait，但路由開銷隨著副本數的增加而增加，且明顯高于Spray and Wait。

圖4 不同副本數的D-Tree的性能對比(Haggle項目)Fig.4 Performance Comparison of different copies of D-Tree

在圖4b中，D-Tree與Spray and Wait隨著副本數的增加，投遞時延都呈下降的趨勢，因為副本數的增加會增加攜帶消息節點與網絡中其他節點的相遇機會，這樣更有機會到達目的節點。而Bubble Rap在只計算節點中心度的情況下，雖然副本數增加，但依然會因為鄰居節點中心度較低而進行多次無效的轉發，因此增加了延時，只有當副本數目增加到一定程度時，即消息的覆蓋面積足夠大時，投遞延時才會出現下降的趨勢。

在圖5中，D-Tree由于避免了盲目的消息轉發，而且優勢隨著網絡規模的增加而增加，這種潛在的“Wait-遇到更優”轉發機制的節點的可能性越大，因此性能優勢越明顯。

圖5 不同副本數的D-Tree的性能對比(Cabspotting項目)Fig.5 Performance Comparison of different copies of D-Tree

5 結束語

利用VANETs中節點的社會屬性特征，本文提出了一種基于決策樹的多副本VANETs機會路由協議D-Tree。這種算法根據車載網中節點間的社會屬性和節點自身屬性，并通過決策樹算法對這些屬性進行分類、評級，依照級別高低建立決策樹，然后建立決策規則對數據包進行投遞轉發。這種算法克服了消息的盲目轉發性，提高了數據包的投遞成功率，降低了傳輸中的延遲，還通過對副本數量的有效限制達到了控制網絡開銷的目的，取得相對較好的綜合性能。在對決策規則更新的問題上，本文將在今后繼續深入研究，以便在更新問題上給予一個準確性的理論支持。

[1] FALL K. A delay-tolerant network architecture for challenged internets[C]// Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. Seattle: ACM Press, 2003:27-34.

[2] HUANG C,LIN S.An early collision warning algorithm for vehicles based on V2V communication[J].International Journal of Communication Systems,2012,25(6):779-795.

[3] 熊永平，孫利民，牛建偉. 機會網絡[J]. 軟件學報, 2009, 20(1):124-137. XIONG Y P,SUN L M,NIU J W,et al.Opportunistic networks[J].Journal of Software,2009,20(1):124-137.

[4] ISENTO J, RODRIGUES J, DISA J, et al. Vehicular delay-tolerant networks-a novel solution for vehicular communications[J]. IEEE Intelligent Transportation Systems Magazine, 2013, 5(4):10-19.

[5] HUANG J, WANG S, CHENG X, et al. Mobility-Assisted routing in intermittently connected mobile cognitive radio networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(11):2956-2968.

[6] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs[C]// ACM Interational Symposium on Mobile Ad Hoc NETWORKING and Computing. Seattle: ACM Press, 2010:32-40.

[7] 吳大鵬,孔曉龍,張洪沛,等.社會屬性感知的間斷連接無線網絡數據轉發策略[J].通信學報,2015,15(1):38-47. WU Dapeng, KONG Xiaolong, ZHANG Hongpei, et al. Social attributes aware data forwarding strategy in intermittently connected wireless networks[J]. Journal on Communication, 2015,15(1):38-47.

[8] HUI P, CROWCROFET J, YONEKI E. BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks[J]. IEEE Transactions on Mobile Computing, 2010, 10(11):1576-1589.

[9] 吉福生, 王燕燕, 徐明玉,等. 社會化機會網絡中節點歸屬位置感知的路由機制[J]. 重慶郵電大學學報:自然科學版, 2015, 27(3):404-410. JI Fusheng, WANG Yanyan, XU Mingyu, et al. Node home location aware routing mechanism for social opportunistic network[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2015, 27(3):404-410.

[10] WU D, ZHANG H, WANG H, et al. Quality-of-protection-driven data forwarding for intermittently connected wireless networks[J]. IEEE Wireless Communications, 2015, 22(4):66-73.

[11] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[J]. Sigcomm, 2005, 5(4):252-259.

[12] 吳大鵬, 張普寧, 王汝言. 節點連接態勢感知的低開銷機會網絡消息傳輸策略[J]. 通信學報, 2013, 34 (3):44-52. WU Dapeng, ZHANG Puning, WANG Ruyan. Connection status aware cost efficient message transmission mechanism in opportunistic networks[J]. Journal on Communication, 2013, 34(3):44-52.

[13] JINDAL A, PSOUNIS K. Contention-aware analysis of routing schemes for mobile opportunistic networks[C]// Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking. Seattle: ACM Press, 2007:1-8.

[14] LIU B, FIROIU V, KUROSE J, et al. Capacity of Cache Enabled Content Distribution Wireless Ad Hoc Networks[C]// Mobile Ad Hoc and Sensor Systems (MASS), 2014 IEEE 11th International Conference on. Seattle: IEEE Press, 2014:309-317.

[15] Jones E, Ward P. Routing strategies for delay-tolerant networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2006, 25(11):2636-2653.

[16] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges[J]. Communications Surveys & Tutorials IEEE, 2006, 8(1):24-37.

[17] MITCHELL T, CARBONELL J, MICHALSKI R. Machine learning [M].Machine Learning. Springer US, 1986:417-433.

[18] LI Z, SHEN H. SEDUM: Exploiting Social Networks in Utility-Based Distributed Routing for DTNs[J]. Computers IEEE Transactions on, 2013, 62(1):83-97.

[19] BELLMAN R. Dynamic Programming[J]. Science, 1966, 153(3731):352-352.

[20] RAWDAD.A Community Resource for Archiving Wireless Data At Dartmouth[EB/OL].(2012-12-19)[2015-04-15]. http://crawdad.org/cambridge/haggle/.

[21] RAWDAD.Exploratorium Cabspotting project 2012[EB/OL]. (2013-12-19)[2015-04-15].http://cabspotting.org/index.html/.

[22] VINICIUS M.Helsinki University of Technology. The opportunistic network environment simulator 2012[EB/OL]. (2010-12-19)[2014-04-15]. http://www.netlab.tkk.fi/tutkimus/dtn/theone/.

劉輝元 (1971-)，重慶人，高級講師，主要研究方向為無線網絡通信。Email：307519688@qq.com。

董春陽(1989-)，男，四川人，碩士研究生，主要研究方向為車載網絡路由協議。E-mail：dasyang@foxmail.com。

(編輯：田海江)

Multiple copies of VANETs based on decision-tree for opportunistic routing protocol

LIU Huiyuan1，2, DONG Chunyang2, HUANG Qiong2

(1. Chongqing School of Industry, Chongqing 400043,P.R.China； 2. Chongqing Key Lab of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065,P.R.China)

In order to effectively forward and deliver the messages in the Vehicle Ad Hoc Networks (VANETs), the selection of routing node is the key issue in the Vehicle Networks in the case of fixed node buffer and limited number of message copy. Therefore, in this paper, we propose an effective opportunistic routing protocol for the multiple copies of VANETs based on the decision tree theory (D-Tree). The proposed scheme takes the intermediate node’s transmission and connection as the set of multiple attributes, and then we can obtain a rule of message forwarding based on the attributes and D-Tree. Furthermore, we can combining the advantages of multiple copies routing scheme and adopting the storage-carry-forwarding of opportunistic routing to deliver the messages. Simulation results confirm that our proposed D-Tree network model, decision rule procedure and calculating method improve the success rate of delivery compared with the conventional Bubble routing algorithm by 10% under the case of density environment. The proposed scheme also demonstrates better performance in delivery delay.

vehicular Ad hoc networks(VANETs); opportunistic routing; routing algorithm; decision tree; multiple copies

10.3979/j.issn.1673-825X.2016.06.004

2015-12-21

2016-06-12

董春陽 409105807@qq.com

國家自然科學基金項目(61171111)；重慶市自然科學基金(CSTC2011jjA40046)

Foundation Items：The National Natural Science Foundation of China (61171111)；The Natural Science Foundation Project of CQ CSTC(CSTC2011jjA40046)

TN914.53

A

1673-825X(2016)06-0769-08