文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2016.08.031
中文引用格式: 黃欣,趙志剛,,萬榮澤. BDNC:基于網(wǎng)絡(luò)編碼的車載網(wǎng)商業(yè)消息傳輸協(xié)議[J].電子技術(shù)應(yīng)用,,2016,42(8):125-129.
英文引用格式: Huang Xin,,Zhao Zhigang,Wan Rongze. BDNC: Network coding-based message transmission protocol in VANETs business application[J].Application of Electronic Technique,,2016,42(8):125-129.
0 引言
車載網(wǎng)VANETs(Vehicle Ad hoc Networks)被認(rèn)為是實現(xiàn)智能交通最有前景的技術(shù)之一[1-3]。在VANETs中,,道路上的車輛組成分布式網(wǎng)絡(luò),,車輛與車輛進(jìn)行通信,并交互信息,,為此,,VANETs在各類應(yīng)用中得到廣泛使用,包括輔助駕駛類,、信息共享類以及商務(wù)娛樂類,。然而,部署車聯(lián)網(wǎng)VANET的根本目的在于提高交通應(yīng)用,,但隨著無線技術(shù)的發(fā)展,,VANET在輔助駕駛、信息共享和商務(wù)方面廣泛應(yīng)用,,包括廣告,、促銷等通知類消息以及天氣預(yù)報等[1]。
商業(yè)應(yīng)用與安全應(yīng)用的最主要區(qū)別在于它們對于消息響應(yīng)時間的要求,。顯然,,安全應(yīng)用有很苛刻的時間要求,,而商業(yè)應(yīng)用對時間要求相對寬裕[2-3],。但是,商業(yè)應(yīng)用需要更寬的帶寬,。
例如,,酒店和加油站兩個商家都向道路行駛?cè)藛T傳輸各自商業(yè)信息。酒店分為促銷信息,,而加油站宣稱營業(yè)時間以及實時優(yōu)惠油價,。這兩個商家服務(wù)的對象均是道路上的行駛者,即它們有共同的興趣區(qū)域。在這種情況下,,提高帶寬利用率,、減少網(wǎng)絡(luò)堵塞以及降低數(shù)據(jù)包被重播的次數(shù)成為需要解決的問題。
網(wǎng)絡(luò)編碼是提高帶寬利用率的有效技術(shù)之一[4],。網(wǎng)絡(luò)編碼允許轉(zhuǎn)發(fā)節(jié)點對數(shù)據(jù)進(jìn)行簡單的操作,,進(jìn)而降低重轉(zhuǎn)的數(shù)據(jù)包數(shù)。網(wǎng)絡(luò)編碼技術(shù)受到廣泛關(guān)注,。NGUYEN D等[5]分析了網(wǎng)絡(luò)編碼在單跳無線網(wǎng)絡(luò)的應(yīng)用特性,。隨后,LI L等[6]提出基于網(wǎng)絡(luò)編碼的廣播協(xié)議,。在多跳網(wǎng)絡(luò)中,,利用鄰居節(jié)點間的協(xié)作提高網(wǎng)絡(luò)傳輸性能,但是文獻(xiàn)[5-6]并沒有考慮這點,。此外,,文獻(xiàn)[7]提出面向VANET的基于秩的網(wǎng)絡(luò)編碼算法。節(jié)點依據(jù)鄰居節(jié)點的競爭接收狀態(tài),,自適應(yīng)地向網(wǎng)絡(luò)輸入數(shù)據(jù)包,。而文獻(xiàn)[8]也提出隨機(jī)編碼方案。然而,,這些基于網(wǎng)絡(luò)編碼方案并不是針對多跳廣播應(yīng)用,,它們均沒有考慮節(jié)點間的協(xié)作性。
為了提高帶寬利用率,,在消息轉(zhuǎn)發(fā)前對其進(jìn)行網(wǎng)絡(luò)編碼,。然而,網(wǎng)絡(luò)編碼會額外增加消息傳輸時延,。這就存在帶寬利用率和傳輸時延的權(quán)衡問題,。即當(dāng)轉(zhuǎn)發(fā)節(jié)點接收了一條消息后,它面臨一個主要問題:是直接轉(zhuǎn)發(fā)消息,,降低時延,,還是等待接收到其他消息,然后進(jìn)行編碼,,提高帶寬利用率,。為此,本文以VANETs的商業(yè)消息傳輸為研究對象,,考慮兩個商家具有多跳共同的興趣區(qū)域,,它們均分道路車輛分發(fā)消息,為了提高帶寬利率和降低傳輸時延,,提出面向帶寬和基于網(wǎng)絡(luò)編碼時延的消息傳輸協(xié)議(Bandwidth and Delay-Network Coding,,BDNC),。
1 系統(tǒng)模型及問題描述
以圖1為研究場景,兩個商家分別位于道路兩側(cè),,它們服務(wù)對象是由一跳或多跳長的道路區(qū)域構(gòu)成,,均在這兩個商家信號覆蓋區(qū)域內(nèi)[9]。
圖1 VANETs的商用場景模型
考慮兩個源節(jié)點(RSU1,、RSU2)代表兩個商家,,并且假定RSU1的傳輸速率快于RSU2。每個轉(zhuǎn)發(fā)節(jié)點有緩存區(qū)域,,能夠儲存消息,。若來自兩個商家的消息包被同一個轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā),那在轉(zhuǎn)發(fā)前,,采用網(wǎng)絡(luò)編碼,,提高帶寬利用率。然而,,在網(wǎng)絡(luò)內(nèi)使用網(wǎng)絡(luò)編碼技術(shù)具有隨機(jī)性和交通流量的不對稱性,。由于消息到達(dá)時間的隨機(jī)性,來自不同商家的消息不可能同時到達(dá)轉(zhuǎn)發(fā)節(jié)點,。因此,,轉(zhuǎn)發(fā)節(jié)點接收了一個消息后有兩種處理方式:(1)若需要編碼,它需要等待一段時間,,直到接收到另一條消息,;(2)不進(jìn)行編碼,直接轉(zhuǎn)發(fā)消息,,降低了時延,。顯然,若采用第一種方式,,等待時間增加了消息傳輸時延,,多數(shù)應(yīng)用是難以接受的。
當(dāng)轉(zhuǎn)發(fā)節(jié)點從快的源節(jié)點(RSU1)接收了消息Mes,,則查詢緩存區(qū)域,。如果區(qū)域不是空的,那么將剛接收的消息Mes與緩存域單元內(nèi)的第一個消息Mes進(jìn)行編碼,。反之,,若緩存區(qū)域是空的,則立即轉(zhuǎn)發(fā)消息Mes,。
然而,,如果是從慢的源節(jié)點(RSU2)接收了消息Mes,,那么轉(zhuǎn)發(fā)節(jié)點可等待機(jī)會進(jìn)行編碼或立即轉(zhuǎn)發(fā)消息Mes,。
為此,,提出BDNC協(xié)議,并考慮兩種策略降低因網(wǎng)絡(luò)編碼所增加的額外時延,,即緩沖區(qū)域控制(Buffer Size Control,,BSC)和時間控制(Time Control,TC)兩種策略,。BSC策略是通過控制緩沖區(qū)域大小降低因編碼所帶來的額外時延,,而TC策略是通過設(shè)定定時器來控制時延。
2 BDNC協(xié)議
2.1 編碼規(guī)則
采用簡單的基于或操作網(wǎng)絡(luò)編碼規(guī)則,,如圖2所示,。節(jié)點X需要向節(jié)點Z轉(zhuǎn)發(fā)消息包P0,而節(jié)點Z正在向節(jié)點X轉(zhuǎn)發(fā)消息包P1,。那么,,節(jié)點Y需要向節(jié)點X和Z轉(zhuǎn)發(fā)消息。傳統(tǒng)路由中,,節(jié)點Y分別向節(jié)點X,、Z轉(zhuǎn)發(fā)數(shù)據(jù)包。若使用網(wǎng)絡(luò)編碼,,節(jié)點Y將需要轉(zhuǎn)發(fā)的消息包P0,、P1進(jìn)行或操作,然后向X,、Z轉(zhuǎn)發(fā),。X、Z節(jié)點接收被編碼后的消息包后,,進(jìn)行或操作,,就能恢復(fù)原來的消息包。通過簡單的網(wǎng)絡(luò)編碼,,帶寬利用率提高了50%,。
圖2 網(wǎng)絡(luò)編碼示例
2.2 BSC策略
BSC策略目的在于通過控制緩存區(qū)大小,降低時延,。通常,,隊列內(nèi)消息數(shù)越多,每條消息的時延就長[10],。為此,,在BSC策略中,轉(zhuǎn)發(fā)節(jié)點依據(jù)隊列內(nèi)消息的條數(shù)決定是否儲存消息,。換而言之,,儲存的概率p與當(dāng)時隊列的大小成正比。
其中表示隊列的大小,。
然而,,這樣簡單的操作會導(dǎo)致最新到達(dá)的消息被立即轉(zhuǎn)發(fā),,而之前的消息仍在隊列內(nèi)等待編碼機(jī)會。這就顛倒了消息次序,,加大了隊列內(nèi)的消息時延,。因此,轉(zhuǎn)發(fā)節(jié)點以概率p對新接收的消息編入隊列,,而以概率1-p釋放隊列內(nèi)的第一條消息,。
2.3 TC策略
盡管商業(yè)應(yīng)用對消息的傳輸沒有嚴(yán)厲的時間要求,但長的傳輸時延也是難以接受的[11],。因此,,從時延角度選擇TC策略。轉(zhuǎn)發(fā)節(jié)點將來自慢速率源節(jié)點的消息緩存于隊列中,,且保留于隊列中的時間不超過Tmax,。當(dāng)轉(zhuǎn)發(fā)節(jié)點從源節(jié)點接收了一條消息,直接緩存于隊列,,并設(shè)置一個定時器,,定時時長為Tmax。在定時器計時完畢后,,若該條消息仍在隊列中,,則立即轉(zhuǎn)發(fā)消息,且不進(jìn)行編碼,。
2.4 消息傳輸流程
提出的BDNC協(xié)議流程如圖3所示,,當(dāng)一旦接收了新的消息,就判斷是否來自快節(jié)點,,若是就進(jìn)一步判斷緩存區(qū)域是否為空,,若是就直接轉(zhuǎn)發(fā),否則就與區(qū)域內(nèi)第一條消息進(jìn)行或編碼,,再轉(zhuǎn)發(fā)已編碼的消息,。如果是來自慢節(jié)點,有兩種選擇,,一種是采用BSC策略,,另一種是TC策略。
圖3 BDNC協(xié)議消息傳輸流程圖
3 性能分析
3.1 仿真場景
考慮圖1所示的仿真場景,,利用NS3進(jìn)行模擬仿真,,仿真參數(shù)如表1所示。兩個源節(jié)點隨機(jī)地產(chǎn)生消息,,且產(chǎn)生消息的間隔服從泊松分布,,即利用泊松分布計算兩條相鄰消息之間的間隔[12-13]。在仿真過程中,,假定 而
是變化的,。而車輛的速度從36~54 km/h變化,。在仿真初期,250輛車隨機(jī)分布于長為4 km的雙向車道,,20 s后,,兩個源節(jié)點開始發(fā)送消息包,。
在仿真過程中,,分析兩個不同策略的平均每跳時延、消息傳輸成功率以及未編碼消息數(shù),。其中,,未編碼消息條數(shù)表示在所接收的已編碼消息中因各種原因,不能解碼的消息數(shù),。
兩個策略目的在于提高帶寬利用率,,并控制因編碼所導(dǎo)致的時延。因此,,選擇每跳時延,、帶寬節(jié)省率、消息傳輸成功率和未解碼的消息條數(shù)作為評估協(xié)議的性能指標(biāo),。其中,,每跳時延表示消息在傳輸過程中每跳的平均時延;消息傳輸成功率表示消息被成功傳輸?shù)膸茁?,?shù)值等于節(jié)點所收到的消息條數(shù)與兩個源節(jié)點所廣播的消息數(shù)之比,;而未解碼的消息數(shù)表示節(jié)點收到已編碼消息后而不能解碼的消息條數(shù)。
為了更好地分析BSC,、TC策略性能,,選擇一個參照策略進(jìn)行對比分析,其中參照策略是指:轉(zhuǎn)發(fā)節(jié)點對所有消息均進(jìn)行編碼再轉(zhuǎn)發(fā),,不考慮兩個源節(jié)點的傳輸速度率,,也不控制編碼時延[10]。在仿真中,,將參照方案記為純網(wǎng)絡(luò)編碼(Pure Network Code,,PNC)。
此外,,在仿真過程中,,同時考慮兩種場景:靜態(tài)的源節(jié)點和動態(tài)移動的源節(jié)點,在下列仿真圖中標(biāo)記為Staionary和Mobile,。將基于BSC策略,、TC策略的BDNC協(xié)議分別記為BDNC-BSC、BDNC-TC,。
3.2 Tmax參數(shù)
為了確認(rèn)TC策略的Tmax參數(shù),,評估了它對吞吐量的影響,,如圖4所示。從圖可知,,隨著Tmax的增加,,帶寬節(jié)省率也隨之增加,這有利于更合適地設(shè)置Tmax,。當(dāng)Tmax=0.3時,,帶寬節(jié)省率增加緩慢,為此,,在下面仿真中,,設(shè)定Tmax=0.3。
圖4 BDNC-TC的帶寬節(jié)省率隨Tmax的變化曲線
3.3 數(shù)值分析
3.3.1 時延
圖5顯示了由源節(jié)點RSU2發(fā)送的消息每跳的平均傳輸時延,,其中圖5(a)表示靜態(tài)的源節(jié)點場景,,而圖5(b)表示動態(tài)的源節(jié)點場景。從圖中可知,,在=1 packet/s時, PNC策略會導(dǎo)致大的時延,,而BSC和TC策略有效地控制了時延。隨著
的增加,,BSC和PNC時延下降,。當(dāng)
=1.5時,BSC和PNC策略的時延分別為1 s,、2 s,。而當(dāng)
=2.5時,這兩個策略的時延約為0.75 s,。原因在于
是反映隊列的釋放數(shù)據(jù)概率,,隨著
的增加,隊列的平均時延就下降,。此外,,TC策略的時延最低,若從時延角度,,TC策略是不錯的選擇,,TC策略的時延維持在0.3 s,與Tmax持平,。
當(dāng)轉(zhuǎn)發(fā)節(jié)點移動時,,轉(zhuǎn)發(fā)節(jié)點動態(tài)的特性影響了網(wǎng)絡(luò)的穩(wěn)定性。從圖5(b)可知,,PNC方案的時延波嚴(yán)重,,但是BSCS方案和TCS方案時延均低于PNC。這也進(jìn)一步說明,BSCS和TCS方案能夠有效地控制因編碼所帶來的時延,。
(a)靜態(tài)場景
(b)動態(tài)場景
圖5 基于3種不同策略的BDNC協(xié)議每跳傳輸時延
3.3.2 帶寬節(jié)省率
從圖6(a)可知,,當(dāng)=1時,NC方案的帶寬節(jié)省率近50%,,但是這是以高的時延為代價的(見圖5(a)),。而BSCS方案的帶寬節(jié)省率了近28%,遠(yuǎn)優(yōu)于TCS方案的13%,。然而,,隨著
的增加,NC和BSCS方案的性能帶寬節(jié)省率性能相近,,且緩慢下降,。而TCS方案的帶寬節(jié)省率的改善幾乎不隨
變化而波動,,趨于常數(shù),,原因在于TCS方案采用了固定的編碼概率。
(a)靜態(tài)場景
(b)動態(tài)場景
圖6 基于3種不同策略的BDNC協(xié)議帶寬節(jié)省率
3.3.3 消息傳輸成功率
圖7描述了平均消息傳輸成功率隨變化曲線,。圖7比較了靜態(tài)轉(zhuǎn)發(fā)節(jié)點和動態(tài)轉(zhuǎn)發(fā)節(jié)點兩種情況下的平均消息傳輸成功率,,從圖中可知,靜態(tài)轉(zhuǎn)發(fā)節(jié)點有利于數(shù)據(jù)轉(zhuǎn)發(fā),,平均數(shù)據(jù)包傳遞率明顯高于動態(tài)轉(zhuǎn)發(fā)節(jié)點環(huán)境,。此外,在動態(tài)轉(zhuǎn)發(fā)節(jié)點環(huán)境下,,當(dāng)
<1.5時,,PNC的消息傳輸成功率最低,并且隨著?姿1的增加,,消息傳輸成功率慢慢上升,,且略優(yōu)于BSC策略。
圖7 基于3種不同策略的BDNC協(xié)議的消息傳輸成功率
3.3.4 未解碼的消息數(shù)
最后,,分析了未解碼的消息條數(shù),。圖8描述了平均每個車輛不能解碼的消息條數(shù)。未解碼的數(shù)據(jù)包是指:車輛收到編碼的消息,,但是由于沒有其他消息,,無法解碼。這種情況多數(shù)由于車輛的移動所引起的,。從圖8可知,,TCS方案的未編碼消息條數(shù)最少。隨著的增加,,未編碼消息條數(shù)下降,,這主要因為
的增大,消息就不用在隊列中等待過長的時間,相應(yīng)地,,就降低了已編碼消息不能被解碼的概率,。
圖8 未編碼的消息數(shù)
4 總結(jié)
針對車聯(lián)網(wǎng)的商業(yè)應(yīng)用,其有兩個源節(jié)點向同一個興趣區(qū)域傳輸數(shù)據(jù),。為了提高網(wǎng)絡(luò)帶寬利用率,,采用網(wǎng)絡(luò)編碼技術(shù)。為了降低因網(wǎng)絡(luò)編碼所增加的額外時延,,提出BSC和TC策略,。BSC策略從控制緩存區(qū)域大小角度控制時延,而TC策略采用定時器原則,。仿真結(jié)果表明,,網(wǎng)絡(luò)編碼技術(shù)可以有效地提高帶寬利用率,帶寬節(jié)省率高達(dá)38%,;而TC策略更能有效地控制時延,,在時延控制方面優(yōu)于BSC策略。
參考文獻(xiàn)
[1] HARRI J,,F(xiàn)IORE M,,F(xiàn)ILALI F,et al.Vehicular mobility simulation with VanetMobiSim[J].Simulation,,2011,,87(4):275-300.
[2] JARUPAN B,EKICI E.PROMPT:A cross-layer positionbased communication protocol for delay-aware vehicular access networks[J].Ad Hoc Networks,,2010,,8(5):489-505.
[3] LA R,SEO E.Expected routing overhead for location service in MANETs under flat geographic routing[J].IEEE Trans.Mobile Comput.,,2011,,10(3):434-448.
[4] 熊飚,張小橋.VANET網(wǎng)絡(luò)中小尺度衰落信道仿真[J].通信技術(shù),,2010,,43(12):56-57.
[5] NGUYEN D,TRAN T,,NGUYEN T,,et al.Wireless broadcast using network coding[J].IEEE Trans.Veh.Technol.,2009,,58(2):914-925.
[6] LI L,,RAMJEE R,BUDDHIKOT M,,et al.Network codingbased broadcast in mobile ad hoc networks[C].in Proc.IEEE INFOCOM,,2014:1739-1747.
[7] YU T X,,YI C W,TSAO S L.Rank-based network coding for content distribution in vehicular networks[J].IEEEWireless Commun.Lett.,,2012,,1(4):368-371.
[8] LEE U,PARK J S,,YEH J,,et al.VANETCODE: Network coding to enhance cooperative downloading in vehicular adhoc networks[C].in Proc.IWCMC,2006:1-5.
[9] CHEN J W.A vote-based position verification method in VANET[J].Communications technology,,2012,,11(54):50-55.
[10] HAMATO S,ARIFFIN S,,F(xiàn)ISAL N.Contention free time efficient broadcasting protocol for safety applications in VANETs[J].International Review on Computers and Software,,2014,9(11):1923-1931.
[11] AHMED S A M,,ARIFFIN S H S,,F(xiàn)ISAL N.Survey on broadcasting in VANET[J].Research Journal of Applied Sciences,Engineering and Technology,,2014,,7(18):23-32.
[12] LI M,,YANG Z,,LOU W.Code on:cooperative popular content distribution for vehicular networks using symbol level network coding[J].IEEE Journal.Sel.A.Commun.,2011,,29(1):223-235.
[13] ZHOU L,,CHAO H C,VASILAKOS A V,,et al.Joint forensics-scheduling strategy for delay-sensitive multimedia applications over heterogeneous networks[J].IEEE Journal.Selected Areas in Communications,,2011,29(7):1358-1367.