基于VANETs下的決策樹(shù)多副本機(jī)會(huì)路由協(xié)議

劉輝元，董春陽(yáng)，黃 瓊

(1.重慶市工業(yè)學(xué)校，重慶 40043; 2.重慶郵電大學(xué)信息產(chǎn)業(yè)部移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶400065)

基于VANETs下的決策樹(shù)多副本機(jī)會(huì)路由協(xié)議

劉輝元1,2，董春陽(yáng)2，黃 瓊2

(1.重慶市工業(yè)學(xué)校，重慶 40043; 2.重慶郵電大學(xué)信息產(chǎn)業(yè)部移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶400065)

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

車載自組織網(wǎng)絡(luò)(VANETs)；機(jī)會(huì)路由；路由算法；決策樹(shù)；多副本

0 引 言

車載自組織網(wǎng)絡(luò)(vehicular Ad hoc networks, VANETs)[1]是專門(mén)為了車輛之間通信而設(shè)計(jì)的自組織網(wǎng)絡(luò)，它屬于移動(dòng)Ad-hoc網(wǎng)絡(luò)(mobile Ad-hoc network, MANET)的子集，其主要目標(biāo)是建立一個(gè)普通的通信平臺(tái)去支持車輛之間各種類型的智能傳輸應(yīng)用。車聯(lián)網(wǎng)是以車際網(wǎng)、車內(nèi)網(wǎng)和車載移動(dòng)互聯(lián)網(wǎng)為基礎(chǔ)，按照約定的通信協(xié)議和數(shù)據(jù)交互標(biāo)準(zhǔn)，支持車輛─車輛(vehicle 2 vehicle, V2V)、車輛─通信設(shè)施(vehicle 2 infrastructure, V2I)之間的通信[2]。

在VANETs應(yīng)用中，每個(gè)車輛節(jié)點(diǎn)分布稀疏不均、網(wǎng)絡(luò)拓?fù)渥兓煲约耙苿?dòng)速度快或障礙物造成信號(hào)衰減等多種原因都可能導(dǎo)致網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)處于中斷狀態(tài)。這種網(wǎng)絡(luò)環(huán)境中，傳統(tǒng)的MANET通信模式無(wú)法有效運(yùn)行，因此，車載網(wǎng)絡(luò)路由協(xié)議通常采用“存儲(chǔ)─攜帶─轉(zhuǎn)發(fā)”的機(jī)會(huì)路由[3]機(jī)制或者車載容延容斷網(wǎng)絡(luò)(vehicular delay tolerant network, VDTN)[4]進(jìn)行消息投遞。同時(shí)，因?yàn)閂ANETs中的節(jié)點(diǎn)在車主的控制下具有一定的人類社會(huì)網(wǎng)絡(luò)屬性。如公交車沿著固定線路行進(jìn)，出租車會(huì)因車上乘客的需求而進(jìn)行隨機(jī)運(yùn)動(dòng)[5]，私家車主們購(gòu)物、上下班等基本都在一些特定區(qū)域，組成的網(wǎng)絡(luò)呈現(xiàn)出社會(huì)網(wǎng)絡(luò)學(xué)中“小世界，大世界”現(xiàn)象[5]。

為改善容斷連接VANETs網(wǎng)絡(luò)性能，同時(shí)提高資源利用率, 需要節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)湫畔⑽粗那闆r下，充分感知網(wǎng)絡(luò)在移動(dòng)過(guò)程中的邏輯結(jié)構(gòu)。因此，車載機(jī)會(huì)網(wǎng)絡(luò)路由的核心問(wèn)題是一個(gè)利用相關(guān)知識(shí)進(jìn)行最優(yōu)化計(jì)算選擇合適的下一跳路由節(jié)點(diǎn)的決策性問(wèn)題。因此，一些基于社區(qū)的路由算法[6-9]被研究者們提出，它們只是簡(jiǎn)單地將社會(huì)屬性選擇出來(lái)，然后依照選出的社會(huì)屬性建立一個(gè)效用函數(shù)或者采用一種單一的社會(huì)屬性值進(jìn)行數(shù)據(jù)的下一跳轉(zhuǎn)發(fā)；在此種情形下有可能由于當(dāng)前網(wǎng)絡(luò)情況和副本數(shù)限制而錯(cuò)失綜合性能更高的節(jié)點(diǎn)。同時(shí)，文獻(xiàn)[10]以節(jié)點(diǎn)信任度為基礎(chǔ)，將節(jié)點(diǎn)信任度分為以過(guò)程基礎(chǔ)和關(guān)系基礎(chǔ)的信任方式來(lái)進(jìn)行數(shù)據(jù)傳輸，并通過(guò)結(jié)合入侵檢測(cè)機(jī)制的方式來(lái)提高網(wǎng)絡(luò)的QoP(quality-of-protection)和用戶QoE(quality of experience)等。

通過(guò)對(duì)上述問(wèn)題的分析，本文提出一種基于學(xué)習(xí)方法的決策樹(shù)理論的機(jī)會(huì)VANETs路由決策算法(D-Tree)，以便能夠更全面地綜合考慮社會(huì)屬性之間的影響并進(jìn)行折衷，優(yōu)化網(wǎng)絡(luò)綜合性能。該算法將VANETs中節(jié)點(diǎn)間傳輸和連接的因素看做多個(gè)屬性的集合，根據(jù)該屬性集合與決策樹(shù)方法得到一個(gè)消息轉(zhuǎn)發(fā)的決策規(guī)則，預(yù)測(cè)節(jié)點(diǎn)的下一個(gè)路由能否成功接收數(shù)據(jù)包，能有效提高網(wǎng)絡(luò)性能的指標(biāo)，降低了節(jié)點(diǎn)的路由開(kāi)銷和投遞延遲等。

1 相關(guān)工作

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

Spray and Wait[11]算法分為2個(gè)階段，Spray階段和Wait階段。在Spray階段，源節(jié)點(diǎn)向網(wǎng)絡(luò)投入特定數(shù)目的L個(gè)數(shù)據(jù)包副本，然后進(jìn)入Wait階段，若數(shù)據(jù)包副本在Spray階段沒(méi)有發(fā)現(xiàn)目的節(jié)點(diǎn)，那么攜帶數(shù)據(jù)包副本的節(jié)點(diǎn)將通過(guò)Direct Delivery[12-16]方式把數(shù)據(jù)包副本傳送到目的節(jié)點(diǎn)。但是由于沒(méi)有考慮到鄰居節(jié)點(diǎn)的數(shù)量問(wèn)題，當(dāng)鄰居節(jié)點(diǎn)過(guò)多時(shí)，會(huì)由于源節(jié)點(diǎn)過(guò)多的“噴灑”造成節(jié)點(diǎn)快速死亡。因此,該算法在不考慮鄰居節(jié)點(diǎn)選擇的情況下，不能取得較好的效果。

Bubble Rap[8]路由算法也是一種基于社會(huì)屬性的路由算法。該算法將轉(zhuǎn)發(fā)策略依賴于2個(gè)社團(tuán)特征(社區(qū)和中心度)。消息轉(zhuǎn)發(fā)的2個(gè)階段都是基于網(wǎng)絡(luò)中心性的轉(zhuǎn)發(fā)。在轉(zhuǎn)發(fā)階段中，當(dāng)目標(biāo)節(jié)點(diǎn)所有鄰居的網(wǎng)絡(luò)中心性都較低，那么消息轉(zhuǎn)發(fā)將失敗，從而導(dǎo)致消息在傳輸過(guò)程中的時(shí)延急劇增加。

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

2 基本定義

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

定義1車輛網(wǎng)絡(luò)。把車輛網(wǎng)絡(luò)定義為一個(gè)含有節(jié)點(diǎn)和鏈路的連通圖G=(V,E)，其中，V代表車輛節(jié)點(diǎn)集合，E為在通信范圍內(nèi)車輛節(jié)點(diǎn)之間的鏈路集合。

對(duì)于每個(gè)車輛節(jié)點(diǎn)vi,vi∈V,i={1,2,…,n}，用集合A描述車輛節(jié)點(diǎn)屬性為

(1)

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

(2)

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

定義4為避免車輛信息增益在分類時(shí)過(guò)度偏袒具有較多值的屬性，引入車輛網(wǎng)絡(luò)信息增益比率為

(3)

3 基于D-Tree的路由協(xié)議

3.1 VANETs屬性

在機(jī)會(huì)VANETs中，節(jié)點(diǎn)的移動(dòng)產(chǎn)生了終端之間的直接相遇機(jī)會(huì)，從而使節(jié)點(diǎn)之間可以實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)通信。但這種通信鏈路建立的時(shí)間不夠確定，鏈路生存時(shí)間短，中斷時(shí)間長(zhǎng)，通信能力受限。常用于描述和表征機(jī)會(huì)VANETs屬性鏈路特征的術(shù)語(yǔ)如下。

1)節(jié)點(diǎn)新近度(node recency)。它是基于最近多長(zhǎng)時(shí)間車輛B遇到網(wǎng)絡(luò)中任意車輛x，為車輛之間最近一次建立連接的時(shí)間間隔比例。如果將來(lái)接觸的概率越高，則說(shuō)明當(dāng)前聯(lián)系時(shí)間與下一次聯(lián)系間隔的間隔越短。

2)節(jié)點(diǎn)活躍因子[7](node active factor)。節(jié)點(diǎn)活躍因子表示車輛節(jié)點(diǎn)的活動(dòng)能力，車輛遇見(jiàn)的其他車輛越頻繁，鄰居列表信息變化越劇烈，說(shuō)明該車輛越活躍，能夠成功轉(zhuǎn)發(fā)到目的地的機(jī)會(huì)越大。本文節(jié)點(diǎn)活躍因子通過(guò)節(jié)點(diǎn)在最近一段時(shí)間內(nèi)平均鄰居節(jié)點(diǎn)個(gè)數(shù)來(lái)衡量。

3)節(jié)點(diǎn)度(node degree)。車輛節(jié)點(diǎn)在車輛網(wǎng)絡(luò)圖中的度。描述了車載用戶在網(wǎng)絡(luò)中的流行程度。車輛之間進(jìn)行信息傳遞時(shí)，車輛節(jié)點(diǎn)的度將是路由選擇的一個(gè)重要度量值。

4)接近中心度(closeness centrality)。接近中心度表示與其他所有節(jié)點(diǎn)具有最短路徑的節(jié)點(diǎn)。描述了最高效的路徑和網(wǎng)絡(luò)可視性，選取接近中心度最高的節(jié)點(diǎn)作為信息分發(fā)和擴(kuò)散的節(jié)點(diǎn)，可以有效減少信息擴(kuò)散時(shí)延和網(wǎng)絡(luò)開(kāi)銷。

5)中介中間性(betweenness centrality)。在車輛網(wǎng)絡(luò)中，節(jié)點(diǎn)作為2個(gè)相鄰節(jié)點(diǎn)的中間橋梁節(jié)點(diǎn)的度量。連接2個(gè)車輛節(jié)點(diǎn)的中間節(jié)點(diǎn)會(huì)具有很高的中介中間性，這個(gè)中間節(jié)點(diǎn)在車輛節(jié)點(diǎn)之間信息交互過(guò)程中，起到了很關(guān)鍵的作用。

6)網(wǎng)絡(luò)密度(density)。車載用戶之間的連接密度。描述了網(wǎng)絡(luò)中節(jié)點(diǎn)之間連接密度的分布。

在上述幾種屬性鏈路特征中，節(jié)點(diǎn)新近度和節(jié)點(diǎn)活躍因子反應(yīng)了節(jié)點(diǎn)在一定時(shí)期內(nèi)車輛節(jié)點(diǎn)自身“活動(dòng)”能力情況的大小，而節(jié)點(diǎn)度、接近中心度等反應(yīng)了車輛節(jié)點(diǎn)在區(qū)域性社區(qū)或者局部網(wǎng)絡(luò)架構(gòu)中節(jié)點(diǎn)相互作用的屬性特征。在同時(shí)考慮車輛節(jié)點(diǎn)自身與車輛網(wǎng)絡(luò)結(jié)構(gòu)的情況下，能夠更加合理地選取下一條路由。

3.2 D-Tree協(xié)議

D-Tree主要包括2個(gè)階段：擴(kuò)散階段和轉(zhuǎn)發(fā)階段。在擴(kuò)散階段，源節(jié)點(diǎn)持有的消息副本數(shù)量為L(zhǎng)(L>1)，如果遇到一個(gè)不含該消息的節(jié)點(diǎn)，則根據(jù)決策規(guī)則和二分法擴(kuò)散副本。在之后的過(guò)程中，當(dāng)節(jié)點(diǎn)持有的消息副本數(shù)為1且與不含該副本的節(jié)點(diǎn)相遇時(shí),則進(jìn)入轉(zhuǎn)發(fā)階段。在轉(zhuǎn)發(fā)階段，節(jié)點(diǎn)只根據(jù)決策規(guī)則向相遇節(jié)點(diǎn)轉(zhuǎn)發(fā)此消息副本。當(dāng)遇到的節(jié)點(diǎn)如果是目的節(jié)點(diǎn)，無(wú)論是在擴(kuò)散階段還是轉(zhuǎn)發(fā)階段，都直接向其轉(zhuǎn)發(fā)該消息 。D-Tree協(xié)議流程如圖1所示。

3.2.1 基于C4.5的VANETs規(guī)則樹(shù)算法

在數(shù)據(jù)收集及預(yù)處理后，進(jìn)行決策樹(shù)建立階段。根據(jù)3.1節(jié)中對(duì)機(jī)會(huì)VANETs屬性概念的定義，并且依照屬性特征值對(duì)整個(gè)網(wǎng)絡(luò)系統(tǒng)的數(shù)據(jù)進(jìn)行收集、處理。然后將處理的屬性特征值按照定義3與定義4的過(guò)程分別進(jìn)行處理、計(jì)算，并將其按照機(jī)器學(xué)習(xí)算法C4.5[17]對(duì)各屬性的重要度進(jìn)行評(píng)級(jí)和劃分，學(xué)習(xí)算法偽代碼如下。

圖1 D-Tree協(xié)議流程Fig.1 D-Tree Protocol Processing

算法:Generate_Decision_Tree

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

算法輸出：決策樹(shù)

/* C:類別屬性; test_attribute:測(cè)試屬性; */

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)

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

3.2.2 擴(kuò)散階段

VANETs中的節(jié)點(diǎn)通過(guò)對(duì)網(wǎng)絡(luò)屬性的收集和處理，依據(jù)建立的決策樹(shù)對(duì)多副本的消息進(jìn)行“有向擴(kuò)散”。對(duì)與本節(jié)點(diǎn)相遇的節(jié)點(diǎn)副本數(shù)的副本分配方法采用經(jīng)典的“二分法”。

3.2.3 轉(zhuǎn)發(fā)階段

消息從源到目的節(jié)點(diǎn)轉(zhuǎn)發(fā)延遲取決于搜索樹(shù)的延遲、擴(kuò)散延遲和轉(zhuǎn)發(fā)延遲之和。為降低投遞時(shí)延，提高消息投遞成功率。持有單個(gè)副本的節(jié)點(diǎn)在轉(zhuǎn)發(fā)階段，將按照決策規(guī)則向未持有相同消息的節(jié)點(diǎn)轉(zhuǎn)發(fā)此消息。

因?yàn)槌钟邢⒐?jié)點(diǎn)與目標(biāo)在同一個(gè)網(wǎng)絡(luò)環(huán)境中，則只要相遇節(jié)點(diǎn)不是目的節(jié)點(diǎn)，就按決策規(guī)則轉(zhuǎn)發(fā)，這樣更容易將消息傳遞到目標(biāo)節(jié)點(diǎn)區(qū)域附近，如果遇到目的節(jié)點(diǎn)則直接轉(zhuǎn)發(fā)。因此，在轉(zhuǎn)發(fā)階段采用決策規(guī)則轉(zhuǎn)發(fā)，在整個(gè)消息的轉(zhuǎn)發(fā)過(guò)程中避免盲目轉(zhuǎn)發(fā)，能有效降低消息向目標(biāo)節(jié)點(diǎn)的投遞時(shí)延。

3.2.4 算法設(shè)計(jì)

通過(guò)模型分析以及上述擴(kuò)散階段與轉(zhuǎn)發(fā)階段的分析，可以對(duì)D-Tree建立一個(gè)算法，算法的偽代碼如下。

算法輸入：消息的源節(jié)點(diǎn)S，目標(biāo)節(jié)點(diǎn)D，且當(dāng)前網(wǎng)絡(luò)中所有節(jié)點(diǎn)都含有決策樹(shù)準(zhǔn)則R，消息副本數(shù)Copies，下一路由節(jié)點(diǎn)Ns，當(dāng)前消息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 規(guī)則分析

對(duì)于每個(gè)攜帶數(shù)據(jù)包狀態(tài)的車輛節(jié)點(diǎn)，每個(gè)階段的狀態(tài)與選擇的轉(zhuǎn)發(fā)決策將影響下一階段的決策。設(shè)共有N+1個(gè)階段，標(biāo)記為n=0,1,…,N，其中將開(kāi)始階段標(biāo)記為0。設(shè)系統(tǒng)在階段n+1時(shí)的狀態(tài)為T(mén)n(i,a)∈Sn+1(稱Tn為n時(shí)的狀態(tài)轉(zhuǎn)移函數(shù))。因此，數(shù)據(jù)包選擇何種決策規(guī)則進(jìn)行轉(zhuǎn)發(fā)的決策問(wèn)題可以規(guī)劃為如下的模型形式

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

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

(4)

目標(biāo)函數(shù)V的常見(jiàn)形式是使各個(gè)階段的報(bào)酬之和達(dá)到最大。

定義階段n時(shí)的決策函數(shù)為映射

(5)

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

因此，策略就是一個(gè)決策函數(shù)序列

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

n=0,1,…,N

(6)

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

下面論述通過(guò)C4.5算法生成的決策樹(shù)中的規(guī)則，一定存在著最優(yōu)策略。

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

(7)

(7)式只與所使用的策略π及初始狀態(tài)i0有關(guān)。稱V(π,i0)為系統(tǒng)在策略π下從初始狀態(tài)i0出發(fā)時(shí)的總報(bào)酬。且定義

(8)

(8)式表示初始狀態(tài)為i時(shí)，所可能獲得的最大總報(bào)酬，稱V為決策問(wèn)題的最優(yōu)值函數(shù)。且在決策規(guī)則中，對(duì)所有的初始狀態(tài)i∈S0一定都成立，即取到(10)式的上確界。根據(jù)Bellman最優(yōu)性原理[19]，則策略π是最優(yōu)策略，且Vn(π,i)=V(i),i∈S0。即對(duì)于車輛節(jié)點(diǎn)在每個(gè)階段n轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，根據(jù)決策規(guī)則的選擇轉(zhuǎn)發(fā)，一定存在一個(gè)最優(yōu)策略在當(dāng)前階段進(jìn)行轉(zhuǎn)發(fā)，使系統(tǒng)的綜合性能得到保障。

4 數(shù)據(jù)仿真及分析

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

本文采用機(jī)會(huì)網(wǎng)絡(luò)(opportunistic network environment，ONE)[22]仿真平臺(tái)進(jìn)行性能評(píng)估工作。對(duì)比了3種路由性能指標(biāo)：消息投遞成功率，消息被目標(biāo)節(jié)點(diǎn)成功接收的數(shù)量與產(chǎn)生的總消息數(shù)量之比；平均投遞時(shí)延，從消息生成到投遞到目標(biāo)節(jié)點(diǎn)所需要的時(shí)間；路由開(kāi)銷率，所有節(jié)點(diǎn)成功轉(zhuǎn)發(fā)數(shù)據(jù)分組總數(shù)與目的節(jié)點(diǎn)收到數(shù)據(jù)分組總數(shù)的差和目的節(jié)點(diǎn)收到數(shù)據(jù)分組總數(shù)之比。

4.1 參數(shù)設(shè)置

在Cambridge的Haggle項(xiàng)目中，節(jié)點(diǎn)是基于校園終端設(shè)備的社會(huì)網(wǎng)絡(luò)的跟蹤數(shù)據(jù)采集。車聯(lián)網(wǎng)中的社會(huì)屬性可以類比于在人類社會(huì)生活中，并以此情景模擬移動(dòng)情況。因此，在基于ONE的仿真平臺(tái)下，將速度范圍增大到車輛行駛下的速度大小，同時(shí)將運(yùn)動(dòng)范圍增大以便模擬車輛在基于社會(huì)網(wǎng)絡(luò)下的移動(dòng)場(chǎng)景。在仿真實(shí)驗(yàn)中，場(chǎng)景參數(shù)設(shè)置情況如表1所示。

Cabspotting項(xiàng)目提供跟蹤出租車軌跡的數(shù)據(jù)集，該數(shù)據(jù)集記錄了500個(gè)節(jié)點(diǎn)的軌跡情況，數(shù)據(jù)采集時(shí)長(zhǎng)為 30 天(如果考慮車輛網(wǎng)絡(luò)的實(shí)際場(chǎng)景，則還存在其他車輛對(duì)這個(gè)數(shù)據(jù)集車輛間數(shù)據(jù)投遞的影響，在本實(shí)驗(yàn)中排出這些因素的影響)。在仿真實(shí)驗(yàn)中，場(chǎng)景參數(shù)設(shè)置情況與表1相同，只需對(duì)仿真時(shí)間、網(wǎng)絡(luò)區(qū)域及節(jié)點(diǎn)數(shù)進(jìn)行更改。同時(shí)，因?yàn)樵谕粋€(gè)數(shù)據(jù)集上重復(fù)完整長(zhǎng)度的實(shí)驗(yàn)沒(méi)有意義，也為了模擬多次隨機(jī)實(shí)驗(yàn)，我們將整個(gè)數(shù)據(jù)集依時(shí)間分成多段進(jìn)行模擬。

表1 Haggle參數(shù)設(shè)置

4.2 生存時(shí)間(TTL)對(duì)性能的影響

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

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

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

從圖2中可以看出，在相同條件下，D-Tree具有較好的性能。Bubble Rap在投遞率方面和D-Tree較為相近，但路由開(kāi)銷率比D-Tree高了接近20%～30%，這是因?yàn)樵谵D(zhuǎn)發(fā)階段，Bubble Rap轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)比D-Tree多，即轉(zhuǎn)發(fā)的盲目型要比D-Tree大。而Spra yand Wait比兩者都低，是因?yàn)镾pray and Wait的轉(zhuǎn)發(fā)階段是被動(dòng)等待，消息副本只會(huì)忠實(shí)的等待目的節(jié)點(diǎn)的到來(lái)。同時(shí)，在圖2中隨著TTL的增加，由于網(wǎng)絡(luò)密度的影響和 Bubble Rap只考慮單社會(huì)屬性節(jié)點(diǎn)中心度會(huì)導(dǎo)致在某一階段節(jié)點(diǎn)鄰居中心度無(wú)法計(jì)算或者都較低，且又因TTL未過(guò)期，不能將數(shù)據(jù)包丟棄，轉(zhuǎn)發(fā)的次數(shù)會(huì)增多，因此，隨著TTL的增加，Bubble Rap協(xié)議的開(kāi)銷會(huì)出現(xiàn)先減小后增大的趨勢(shì)。

從圖3中可以看出，在網(wǎng)絡(luò)規(guī)模大幅增加的情況下，D-Tree仍然具有較好的性能。D-Tree的性能和Spray and Wait較為相近，但投遞率比Spray and Wait略高。D-Tree和Spray and Wait的路由開(kāi)銷率都比Bubble Rap低分別是因?yàn)椋篋-Tree比Bubble具有較準(zhǔn)確的轉(zhuǎn)發(fā)性，而Spray and Wait是因?yàn)閃ait階段不會(huì)對(duì)網(wǎng)絡(luò)產(chǎn)生較大開(kāi)銷。且在網(wǎng)絡(luò)密度較大的情況下，對(duì)于D-Tree和Bubble Rap的社會(huì)屬性值會(huì)相對(duì)較好采集，根據(jù)路由開(kāi)銷的定義，在圖3b中隨著TTL的增加，開(kāi)銷是遞減的趨勢(shì)。

4.3 副本數(shù)對(duì)性能的影響

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

圖4 不同副本數(shù)的D-Tree的性能對(duì)比(Haggle項(xiàng)目)Fig.4 Performance Comparison of different copies of D-Tree

在圖4b中，D-Tree與Spray and Wait隨著副本數(shù)的增加，投遞時(shí)延都呈下降的趨勢(shì)，因?yàn)楦北緮?shù)的增加會(huì)增加攜帶消息節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的相遇機(jī)會(huì)，這樣更有機(jī)會(huì)到達(dá)目的節(jié)點(diǎn)。而B(niǎo)ubble Rap在只計(jì)算節(jié)點(diǎn)中心度的情況下，雖然副本數(shù)增加，但依然會(huì)因?yàn)猷従庸?jié)點(diǎn)中心度較低而進(jìn)行多次無(wú)效的轉(zhuǎn)發(fā)，因此增加了延時(shí)，只有當(dāng)副本數(shù)目增加到一定程度時(shí)，即消息的覆蓋面積足夠大時(shí)，投遞延時(shí)才會(huì)出現(xiàn)下降的趨勢(shì)。

在圖5中，D-Tree由于避免了盲目的消息轉(zhuǎn)發(fā)，而且優(yōu)勢(shì)隨著網(wǎng)絡(luò)規(guī)模的增加而增加，這種潛在的“Wait-遇到更優(yōu)”轉(zhuǎn)發(fā)機(jī)制的節(jié)點(diǎn)的可能性越大，因此性能優(yōu)勢(shì)越明顯。

圖5 不同副本數(shù)的D-Tree的性能對(duì)比(Cabspotting項(xiàng)目)Fig.5 Performance Comparison of different copies of D-Tree

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

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

[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ī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 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] 吳大鵬,孔曉龍,張洪沛,等.社會(huì)屬性感知的間斷連接無(wú)線網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)策略[J].通信學(xué)報(bào),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] 吉福生, 王燕燕, 徐明玉,等. 社會(huì)化機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)歸屬位置感知的路由機(jī)制[J]. 重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版, 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] 吳大鵬, 張普寧, 王汝言. 節(jié)點(diǎn)連接態(tài)勢(shì)感知的低開(kāi)銷機(jī)會(huì)網(wǎng)絡(luò)消息傳輸策略[J]. 通信學(xué)報(bào), 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-)，重慶人，高級(jí)講師，主要研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)通信。Email：307519688@qq.com。

董春陽(yáng)(1989-)，男，四川人，碩士研究生，主要研究方向?yàn)檐囕d網(wǎng)絡(luò)路由協(xié)議。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

董春陽(yáng) 409105807@qq.com

國(guó)家自然科學(xué)基金項(xiàng)目(61171111)；重慶市自然科學(xué)基金(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