趙凱，李瑋瑤

（1.平頂山學(xué)院 教務(wù)處，河南 平頂山　467000；2.平頂山學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，河南 平頂山　467000）

基于3G的VANETs數(shù)據(jù)傳輸?shù)募夹g(shù)研究

趙凱1，李瑋瑤2

（1.平頂山學(xué)院 教務(wù)處，河南 平頂山467000；2.平頂山學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，河南 平頂山467000）

在車載自組織VANETs中，為解決車輛間通信數(shù)據(jù)傳輸不流暢的問題。提出采用3G輔助VANETs的數(shù)據(jù)傳輸技術(shù)。在無法利用VANETs多跳通信傳輸數(shù)據(jù)時，啟動3G傳輸，將此方案命名為3GDD，首先建立數(shù)據(jù)傳輸率和數(shù)據(jù)傳輸時延的效用函數(shù)，利用3G輔助VANETs數(shù)據(jù)傳輸實現(xiàn)最大化效用；其次，為了避開優(yōu)化問題的復(fù)雜性，將原始的優(yōu)化問題變換成整數(shù)線性規(guī)范問題ILP（integer linear programming problem）；最后通過解決ILP，在不同時刻分配3G預(yù)算，并選擇最不可能通過VANETs傳輸?shù)臄?shù)據(jù)用于3G傳輸。實驗結(jié)果表明，提出的3GDD與同類的方案相比具有良好的性能。

3G；效用函數(shù)；整數(shù)線性規(guī)劃；數(shù)據(jù)傳輸率；VANETs

近期，車載自組織網(wǎng)（Vehicle Ad hoc Networks，VANETs）得到極大的關(guān)注。在VANETs中，裝備傳感設(shè)備［1-3］，每個車輛就成為強大的移動傳感設(shè)備，并在其通信范圍內(nèi)其他車輛交互信息。許多應(yīng)用和服務(wù)隨VANETs技術(shù)不斷發(fā)展而提出，如交通事故預(yù)警、道路安全［4-5］以及智能交通［6］。數(shù)據(jù)傳輸在VANETs中扮演著重要的作用，因為幾乎所有應(yīng)用都需要有效的數(shù)據(jù)傳輸。數(shù)據(jù)傳輸性能包括，數(shù)據(jù)傳輸率，傳輸時延以及吞吐量［7］。本文針對VANETs的數(shù)據(jù)采集［8］展開分析。在VANETs中，每個車輛產(chǎn)生數(shù)據(jù)包，并向服務(wù)中心CS（Central server）傳遞?？紤]VANETs基礎(chǔ)設(shè)施的路邊接入點APs（Roadside access points）。通過AP接入Internet，服務(wù)中心也可接入Internet，保證每個車輛能向Aps傳遞數(shù)據(jù)包。

文中提出采用3G輔助VANETs數(shù)據(jù)傳輸，為VANETs內(nèi)車輛提供3G數(shù)據(jù)通道。同時，存在3G流量的預(yù)算限制，并通過3G預(yù)算限制從而控制通過3G傳輸?shù)臄?shù)據(jù)包數(shù)量，其目的在于最大化數(shù)據(jù)傳輸率同時最小化傳輸時延。實現(xiàn)這個目標(biāo)有兩個問題：第一，通過3G傳輸時如何平衡數(shù)據(jù)傳輸率與數(shù)據(jù)傳輸時延。應(yīng)當(dāng)鼓勵所有的數(shù)據(jù)包首選免費的多跳傳輸，僅當(dāng)數(shù)據(jù)包在其TTL內(nèi)未能成功傳輸?shù)臄?shù)據(jù)包再選擇通過3G傳輸。通過這種方式，降低因使用3G所帶來的費用成本。然而，使用3G傳輸增加數(shù)據(jù)傳輸時延。第二，很難決定從所有的數(shù)據(jù)包中選擇哪些數(shù)據(jù)包、什么時候用3G傳輸。

1　系統(tǒng)模型

本節(jié)，首先分析網(wǎng)絡(luò)模型，并定義3G輔助VANETs數(shù)據(jù)傳輸模型。

基于基礎(chǔ)設(shè)施的VANETs主要由3部分組成：移動車輛集V，接入點AP集Φ以及服務(wù)中心CS（Central server）。AP間通過有線網(wǎng)絡(luò)連接。系統(tǒng)中的每輛車均能產(chǎn)生數(shù)據(jù)包，且數(shù)據(jù)包的有效時限TTL（Time-to-live）被標(biāo)識為T。假定所有的數(shù)據(jù)包具有相同的TTL。數(shù)據(jù)包的大小均相等。網(wǎng)絡(luò)需傳輸?shù)臄?shù)據(jù)包集為P=｛p1，p2，…，pm｝。

系統(tǒng)中所有車輛均配備3G和短距離專用通信技術(shù)DSRC，因此，每個車輛能直接通過3G或多跳傳輸向AP點傳輸數(shù)據(jù)包。當(dāng)兩個節(jié)點在彼此的通信范圍內(nèi)，就用短距離通信（Short-range communication）。使用3G傳輸數(shù)據(jù)時，由于傳遞時延甚小，可忽略不計。如果采用多跳傳輸，必須要考慮其傳輸時延?？紤]到3G流量（traffic）費用，假定3G流量預(yù)算，并標(biāo)識為B。設(shè)定VANETs網(wǎng)絡(luò)模型為聯(lián)系圖contact graph G（V，E），其中V表示網(wǎng)絡(luò)中的節(jié)點集，邊eij∈E表示兩節(jié)點i、j間連接線。依據(jù)文獻［8］的研究，兩節(jié)點i、j間連接過程服從以連接率λ的泊松分布，連接時間服從指數(shù)分布。

此外，系統(tǒng)中的服務(wù)中心SC不僅從網(wǎng)絡(luò)中收集數(shù)據(jù)，還分配3G預(yù)算。為此，SC需通過附加的3G通信從車輛獲取當(dāng)前網(wǎng)絡(luò)信息。通過這些信息，決策每個數(shù)據(jù)包的傳遞概率或在每個時隙內(nèi)（time slot）3G預(yù)算的分配（budget allocation）。假定這些信息遠(yuǎn)小于數(shù)據(jù)的尺寸，因此，可不考慮因收集這些信息所消耗3G流量。

2　3GDD的設(shè)計

文中提出3GDD方案，以解決數(shù)據(jù)傳輸問題。3GDD的主要思想如下：首先依據(jù)VANET的contact graph模型，估計的期望值。將原始的優(yōu)化問題在簡化成整數(shù)規(guī)劃ILP（Integer linear programming）問題。通過解決ILP問題，在不同的時隙分配SG預(yù)算，然后3GDD選擇那些不能通過VANET的多跳傳輸?shù)臄?shù)據(jù)包，并用3G進行傳輸。

2.1ILP

本小節(jié)首先分析在每個時隙如何估計通過VANET多跳傳輸數(shù)據(jù)包的期望值E［Zi］=zi，然后給出ILP的表達式。

為了估計zi，必須去簡化網(wǎng)絡(luò)模型。假定任何兩節(jié)點i、j的連接率服從平均連接率λ的泊松分布。

Lemma 1：給定接入點集Φ，節(jié)點與某接入點AP∈Φ的連接服從|Φ|λ的泊松分布，其中|Φ|表示網(wǎng)絡(luò)中所有AP的個數(shù)。

假定m′i表示直到時隙ti內(nèi)仍未傳輸?shù)臄?shù)據(jù)包的期望值，不包括通過在時隙ti內(nèi)3G傳輸?shù)臄?shù)據(jù)包。依據(jù)Lemma 1，m′i與接點AP連接服從|Φ|λm′i的泊松分布。在時隙ti內(nèi)傳輸?shù)臄?shù)據(jù)包期望值zi為|Φ|λm′iτ。顯然m′1=m-n1，E［Z1］=Z1=m′1|Φ|λτ。為此，m′i可依據(jù)式（1）進行更新：

通過z1可以推導(dǎo)zi，i∈｛1，2，…，s｝。通過這種方式，能夠獲取U的期望值表達式，其是僅關(guān)于ni的函數(shù)。ni僅是整數(shù)，為此，需將3G輔助數(shù)據(jù)傳輸問題定義為整數(shù)規(guī)劃問題：

Definition 3（ILP formulation of 3G-assisted data delivery problem）:依據(jù)Definition 2，簡化的ILP可表述如下：

文中提出3G輔助數(shù)據(jù)傳輸問題的根本目的在于決定什么時候以及哪些數(shù)據(jù)包應(yīng)當(dāng)被3G傳輸，以致獲取最大的數(shù)據(jù)傳輸率以及最小的數(shù)據(jù)傳輸時延。為此，將此問題歸納為整數(shù)規(guī)劃問題，并通過分枝定界法（Branch and Bound）解決。

2.2啟發(fā)式算法

為了處理Definition 3定義的ILP表達式，提出基于Tabu search算法［6］的啟發(fā)式算法。啟發(fā)式算法的核心思想：從一個可行的初始方法開始，尋找鄰居或局部潛在方法，獲取優(yōu)化的方法提高整體的效用U。在描述該算法前，先定義鄰居的概念。

Definition 4（neighbor）：兩個整數(shù)a、b，如果|b-a|＜dmin，則整數(shù)a、b稱為鄰居。dmin為給定距離門限值。對于矢量v，u，如果u中的任何元素v與相對應(yīng)的元素是鄰居，則矢量v，u稱為鄰居矢量。

啟發(fā)式算法的具體過程如圖1所示。從初始方法開始并從局部候選方法搜索。最初，假定是最優(yōu)的，其具有較高的效用。接下來，更優(yōu)化的方法被開發(fā)。方法不斷迭代，直到在最大的迭代數(shù)到達前，返回當(dāng)前最佳的3G預(yù)測分配方案。為了提高性能以及避免已使用過的方法，采用清單tablist記錄已遍歷的方法。

圖1　啟發(fā)式算法Fig.1　Heuristic algorithms

2.33G傳輸數(shù)據(jù)包的選擇

通過解決ILP，可以在每個時隙內(nèi)指定3G預(yù)算。依據(jù)3G預(yù)算，可建立通過3G傳輸?shù)臄?shù)據(jù)包集。顯然，選擇那些在VANET中最不可能被傳輸?shù)臄?shù)據(jù)包是合理的。因此，數(shù)據(jù)包選擇的一個關(guān)鍵問題在于在每個時隙前估計數(shù)據(jù)包傳輸?shù)母怕?。本小?jié)，介紹在時刻t如何估計每個數(shù)據(jù)包傳輸?shù)母怕?。為了描述簡單，假定?shù)據(jù)包產(chǎn)生的時刻為0。

節(jié)點i、j一跳連接率為λi，連接時長服從指數(shù)分布，因此，數(shù)據(jù)包在時間x內(nèi)能成功從節(jié)點i傳輸?shù)絡(luò)的概率pij（x）= λije-λijx，x＞0。對于從節(jié)點 i到 j的 r跳路由 Υ，定義一跳路徑＜e1，…，er＞，其相應(yīng)的連接概率為＜λ1…λr＞，在時間t的傳遞概率為：

假定φ表示節(jié)點i、j間所有可能路由集，那以數(shù)據(jù)包在時間t從節(jié)點i傳遞到j(luò)的傳輸概率為：

3　性能分析與仿真

1）仿真參數(shù) 在仿真過程使用真實的GPS數(shù)據(jù)。這些數(shù)據(jù)來自內(nèi)蒙古自治區(qū)內(nèi)的士公司的500輛移動數(shù)據(jù)。每天的平均連接率（average contact rate）約0.58。車輛通信范圍R= 300米。產(chǎn)生的數(shù)據(jù)包數(shù)為500個。對于每個數(shù)據(jù)包，隨機地選擇源節(jié)點。AP數(shù)為50，TTL為2個小時。

采用Network Simulator 2.35作為仿真平臺來驗證3GDD的性能，并用Matlab（R2009b）繪制圖，Network Simulator 2.35的具體的仿真參數(shù)如表1所示。

表1　仿真參數(shù)Tab.1 Simulation parameters

2）影響因素α首先，分析數(shù)據(jù)傳輸率的權(quán)值α對效用的影響。在仿真過程中，隨機選擇400的士，α的變化范圍為0.4 至0.8，步長為0.2。

圖2顯示了效用隨α的變化情況。從圖可知，3GDD在α整個變化范圍內(nèi)具有高的效用Utility。而其他的方案在不同α情況，效用呈現(xiàn)不穩(wěn)定性。

3）3G預(yù)算（3G預(yù)算）的影響 在這次仿真中，隨機選擇400的士，3G預(yù)算從100變化至200，步長25。α=0.6。仿真結(jié)果如圖3，4，5所示。

圖2　效用隨α的變化情況Fig.2　The utility changes with α

圖3　數(shù)據(jù)傳輸時延率隨3G budget的影響Fig.3　Delay of data transmission rate with 3G budget

圖4　數(shù)據(jù)傳輸時延隨3G budget的影響Fig.4　Effect of time delay for data transmission with 3G budget

從圖6可知，E_Random具有最高的數(shù)據(jù)傳輸率，這是因為E_Random總是用3G傳輸數(shù)據(jù)包，最大化地使用3G。而S_Random的數(shù)據(jù)傳輸率最低。3GDD的數(shù)據(jù)傳輸率與M_Average和M_Random相類似。這也表明在總的預(yù)算一定的情況下，平均分配或隨機分布對數(shù)據(jù)傳輸率性能影響不大。圖6顯示了數(shù)據(jù)傳輸時延的性能曲線。從圖6可知，E_Random的傳輸時延最高，這是因為其所有的數(shù)據(jù)包均采用3G傳輸時。而S_Random的數(shù)據(jù)傳輸時延最低。圖6與圖7進一步證實數(shù)據(jù)傳輸率和數(shù)據(jù)傳輸時延兩性能的關(guān)系：通過3G傳輸可以提高數(shù)據(jù)傳輸率，但增加了數(shù)據(jù)傳輸時延。圖7描述兩個性能的綜合效用Utility。從圖7可知，提出3GDD在整個預(yù)算變化范圍（100，200）內(nèi)，具有最好的效用Utility。

圖5　效用Utility隨3G budget的影響Fig.5　Effect of Utility with the 3G budget utility

圖6　數(shù)據(jù)傳輸率隨節(jié)點數(shù)目的影響Fig.6　Data transmission rate with the number of nodes affected

圖7　數(shù)據(jù)傳輸時延隨節(jié)點數(shù)目的影響Fig.7　Effect of data transmission delay with the number of nodes

為了評估車輛數(shù)目對系統(tǒng)性能的影響，改變網(wǎng)絡(luò)車輛數(shù)目，使其從100至300變化，步長為50，3G的預(yù)測為150，α=0.6。仿真結(jié)果如圖6～圖8所示。

圖8　效用Utility隨節(jié)點數(shù)目的影響Fig.8　Effect of Utility with the node number effect

從圖6可知，隨著車輛數(shù)目的增加，數(shù)據(jù)傳輸率呈上升趨勢。這是因為車輛數(shù)目增加，提高了車輛相遇的概率，車輛間的連接率上升。仿真結(jié)果與圖5類似，E_Random具有最高的數(shù)據(jù)傳輸率，而S_Random的數(shù)據(jù)傳輸率最低。圖7顯示的結(jié)果與圖6相似，進一步表明不論在什么環(huán)境下，采用3G傳輸增加了數(shù)據(jù)傳輸時延。不出所料，3GDD的效用在整個變化范圍內(nèi)Utility最好，如圖8所示。當(dāng)車輛數(shù)目為450時，S_Random的Utility高于3GDD不超過0.013%。

4　結(jié)　論

數(shù)據(jù)有效傳遞對VANETs的應(yīng)用起到重要作用。然而，VANETs有很多數(shù)據(jù)未能得到有效的傳輸。為此，提出3GDD方案，在VANETs中采用3G輔助數(shù)據(jù)的傳輸，從而提高VANETs的數(shù)據(jù)傳輸性能。3GDD通過解決ILP問題，先分配每個時隙的3G預(yù)算，再從選擇那些難以通過VANETs多跳傳輸?shù)臄?shù)據(jù)，將這些數(shù)據(jù)用3G傳輸。在每個時隙開始，啟動數(shù)據(jù)包的選擇，同時依據(jù)網(wǎng)絡(luò)的實時狀態(tài)選擇數(shù)據(jù)包。通過真實的車輛數(shù)據(jù)仿真表明，與其他方案相比，3GDD方案具有良好整體Utility。

［1］Li M，Liu Y.Rendered path:Range-free localization in anisotropic sensor networks with holes［J］.IEEE/ACM Trans.Netw.，2010，18（1）:320-332.

［2］Wu K，Tan H，Ngan H，et al.Chip error pattern analysis in IEEE 802.15.4［J］.IEEE Trans.Mobile Comput.，2012，11 （4）:543-552.

［3］Miao F，Jiang L，Li Y，et al.Biometrics based novel key distribution solution for body sensor networks［J］.Conf.Eng. Med.Biol.Soc.，2009:2458-2461.

［4］Farnoud F，Valaee S.Reliable broadcast of safety messages in vehicular ad hoc networks［J］.IEEE INFOCOM，2009:226-234.

［5］Taleb T，Benslimane A，Ben Letaief K.Toward an effective riskconscious and collaborative vehicular collision avoidance system［J］.IEEE Trans.Veh.Technol.，2010，59（3）:1474-1486.

［6］Liu N，Liu M，Cao J，et al.When transportation meets communication:V2P over VANETs［J］.30th IEEE Int.Conf. Distrib.Comput.Syst.，2010:567-576.

［7］Bai F，Stancil D，Krishnan H.Toward understanding characteristics of dedicated short range communications（DSRC）from a perspective of vehicular network engineers［J］.Mobile Comput.Netw.，2010:329-340.

［8］Zhu Y，Bao Y，Li B.On maximizing delay-constrained coverage of urban vehicular networks［J］.IEEE J.Sel.Areas Commun.，2012，30（4）:804-817.

Research on data delivery in VANETs 3G-assisted

ZHAO Kai1，LI Wei-yao2
（1.Teaching Affairs Division，Pingdingshan University，Pingdingshan 467000，China；2.College of Computer Science and Technology，Pingdingshan University，Pingdingshan 467000，China）

Data delivery is significant impact on application of a vehicular ad hoc network（VANET）.In this paper，we explore the problem of 3G-assisted data delivery in a VANET with a budget constraint of 3G traffic.A packet can either be delivered via multi-hop transmissions in the VANET or via 3G.We propose an approach called 3GDD for 3G-assisted data delivery in a VANET.Firstly，we construct a utility function to explore the tradeoff between delivery ratio and delivery delay，which provides a unified framework to reflect the two factors.We formulate the 3G-assisted data delivery as an optimization problem in which the objective is to maximize the overall utility under the 3G budget constraint.Secondly，to circumvent the high complexity of this optimization problem，we further transition the original optimization problem as an integer linear programming problem（ILP）.Finally，solving this ILP，we derive the 3G allocation over different time stages.Given the 3G budget at each time stage，those packets that are most unlikely delivered via the VANET are selected for 3G transmissions. Evaluation results show that our approach outperforms other schemes.

3G；utility function；integer linear programming；data delivery delay；VANETs

TN915.11

A

1674－6236（2016）05-0130-04

2015-03-26稿件編號：201503362

趙 凱（1982—），男，河南平頂山人，碩士，講師。研究方向：向量機、工作流引擎。