文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.08.031
中文引用格式： 黃欣，趙志剛，萬榮澤. BDNC:基于網絡編碼的車載網商業消息傳輸協議[J].電子技術應用，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 引言
車載網VANETs(Vehicle Ad hoc Networks)被認為是實現智能交通最有前景的技術之一[1-3]。在VANETs中，道路上的車輛組成分布式網絡，車輛與車輛進行通信，并交互信息，為此，VANETs在各類應用中得到廣泛使用，包括輔助駕駛類、信息共享類以及商務娛樂類。然而，部署車聯網VANET的根本目的在于提高交通應用，但隨著無線技術的發展，VANET在輔助駕駛、信息共享和商務方面廣泛應用，包括廣告、促銷等通知類消息以及天氣預報等[1]。
商業應用與安全應用的最主要區別在于它們對于消息響應時間的要求。顯然，安全應用有很苛刻的時間要求，而商業應用對時間要求相對寬裕[2-3]。但是，商業應用需要更寬的帶寬。
例如，酒店和加油站兩個商家都向道路行駛人員傳輸各自商業信息。酒店分為促銷信息，而加油站宣稱營業時間以及實時優惠油價。這兩個商家服務的對象均是道路上的行駛者，即它們有共同的興趣區域。在這種情況下，提高帶寬利用率、減少網絡堵塞以及降低數據包被重播的次數成為需要解決的問題。
網絡編碼是提高帶寬利用率的有效技術之一[4]。網絡編碼允許轉發節點對數據進行簡單的操作，進而降低重轉的數據包數。網絡編碼技術受到廣泛關注。NGUYEN D等[5]分析了網絡編碼在單跳無線網絡的應用特性。隨后，LI L等[6]提出基于網絡編碼的廣播協議。在多跳網絡中，利用鄰居節點間的協作提高網絡傳輸性能，但是文獻[5-6]并沒有考慮這點。此外，文獻[7]提出面向VANET的基于秩的網絡編碼算法。節點依據鄰居節點的競爭接收狀態，自適應地向網絡輸入數據包。而文獻[8]也提出隨機編碼方案。然而，這些基于網絡編碼方案并不是針對多跳廣播應用，它們均沒有考慮節點間的協作性。
為了提高帶寬利用率，在消息轉發前對其進行網絡編碼。然而，網絡編碼會額外增加消息傳輸時延。這就存在帶寬利用率和傳輸時延的權衡問題。即當轉發節點接收了一條消息后，它面臨一個主要問題：是直接轉發消息，降低時延，還是等待接收到其他消息，然后進行編碼，提高帶寬利用率。為此，本文以VANETs的商業消息傳輸為研究對象，考慮兩個商家具有多跳共同的興趣區域，它們均分道路車輛分發消息，為了提高帶寬利率和降低傳輸時延，提出面向帶寬和基于網絡編碼時延的消息傳輸協議(Bandwidth and Delay-Network Coding，BDNC)。
1 系統模型及問題描述
以圖1為研究場景，兩個商家分別位于道路兩側，它們服務對象是由一跳或多跳長的道路區域構成，均在這兩個商家信號覆蓋區域內[9]。
圖1 VANETs的商用場景模型
考慮兩個源節點(RSU1、RSU2)代表兩個商家，并且假定RSU1的傳輸速率快于RSU2。每個轉發節點有緩存區域，能夠儲存消息。若來自兩個商家的消息包被同一個轉發節點轉發，那在轉發前，采用網絡編碼，提高帶寬利用率。然而，在網絡內使用網絡編碼技術具有隨機性和交通流量的不對稱性。由于消息到達時間的隨機性，來自不同商家的消息不可能同時到達轉發節點。因此，轉發節點接收了一個消息后有兩種處理方式：(1)若需要編碼，它需要等待一段時間，直到接收到另一條消息；(2)不進行編碼，直接轉發消息，降低了時延。顯然，若采用第一種方式，等待時間增加了消息傳輸時延，多數應用是難以接受的。
當轉發節點從快的源節點(RSU1)接收了消息Mes，則查詢緩存區域。如果區域不是空的，那么將剛接收的消息Mes與緩存域單元內的第一個消息Mes進行編碼。反之，若緩存區域是空的，則立即轉發消息Mes。
然而，如果是從慢的源節點(RSU2)接收了消息Mes，那么轉發節點可等待機會進行編碼或立即轉發消息Mes。
為此，提出BDNC協議，并考慮兩種策略降低因網絡編碼所增加的額外時延，即緩沖區域控制(Buffer Size Control，BSC)和時間控制(Time Control，TC)兩種策略。BSC策略是通過控制緩沖區域大小降低因編碼所帶來的額外時延，而TC策略是通過設定定時器來控制時延。
2 BDNC協議
2.1 編碼規則
采用簡單的基于或操作網絡編碼規則，如圖2所示。節點X需要向節點Z轉發消息包P0，而節點Z正在向節點X轉發消息包P1。那么，節點Y需要向節點X和Z轉發消息。傳統路由中，節點Y分別向節點X、Z轉發數據包。若使用網絡編碼，節點Y將需要轉發的消息包P0、P1進行或操作，然后向X、Z轉發。X、Z節點接收被編碼后的消息包后，進行或操作，就能恢復原來的消息包。通過簡單的網絡編碼，帶寬利用率提高了50%。
圖2 網絡編碼示例
2.2 BSC策略
BSC策略目的在于通過控制緩存區大小，降低時延。通常，隊列內消息數越多，每條消息的時延就長[10]。為此，在BSC策略中，轉發節點依據隊列內消息的條數決定是否儲存消息。換而言之，儲存的概率p與當時隊列的大小成正比。
其中
表示隊列的大小。
然而，這樣簡單的操作會導致最新到達的消息被立即轉發，而之前的消息仍在隊列內等待編碼機會。這就顛倒了消息次序，加大了隊列內的消息時延。因此，轉發節點以概率p對新接收的消息編入隊列，而以概率1－p釋放隊列內的第一條消息。
2.3 TC策略
盡管商業應用對消息的傳輸沒有嚴厲的時間要求，但長的傳輸時延也是難以接受的[11]。因此，從時延角度選擇TC策略。轉發節點將來自慢速率源節點的消息緩存于隊列中，且保留于隊列中的時間不超過Tmax。當轉發節點從源節點接收了一條消息，直接緩存于隊列，并設置一個定時器，定時時長為Tmax。在定時器計時完畢后，若該條消息仍在隊列中，則立即轉發消息，且不進行編碼。
2.4 消息傳輸流程
提出的BDNC協議流程如圖3所示，當一旦接收了新的消息，就判斷是否來自快節點，若是就進一步判斷緩存區域是否為空，若是就直接轉發，否則就與區域內第一條消息進行或編碼，再轉發已編碼的消息。如果是來自慢節點，有兩種選擇，一種是采用BSC策略，另一種是TC策略。
圖3 BDNC協議消息傳輸流程圖
3 性能分析
3.1 仿真場景
考慮圖1所示的仿真場景，利用NS3進行模擬仿真，仿真參數如表1所示。兩個源節點隨機地產生消息，且產生消息的間隔服從泊松分布，即利用泊松分布計算兩條相鄰消息之間的間隔[12-13]。在仿真過程中，假定
而
是變化的。而車輛的速度從36～54 km/h變化。在仿真初期，250輛車隨機分布于長為4 km的雙向車道，20 s后，兩個源節點開始發送消息包。
在仿真過程中，分析兩個不同策略的平均每跳時延、消息傳輸成功率以及未編碼消息數。其中，未編碼消息條數表示在所接收的已編碼消息中因各種原因，不能解碼的消息數。
兩個策略目的在于提高帶寬利用率，并控制因編碼所導致的時延。因此，選擇每跳時延、帶寬節省率、消息傳輸成功率和未解碼的消息條數作為評估協議的性能指標。其中，每跳時延表示消息在傳輸過程中每跳的平均時延；消息傳輸成功率表示消息被成功傳輸的幾率，數值等于節點所收到的消息條數與兩個源節點所廣播的消息數之比；而未解碼的消息數表示節點收到已編碼消息后而不能解碼的消息條數。
為了更好地分析BSC、TC策略性能，選擇一個參照策略進行對比分析，其中參照策略是指：轉發節點對所有消息均進行編碼再轉發，不考慮兩個源節點的傳輸速度率，也不控制編碼時延[10]。在仿真中，將參照方案記為純網絡編碼(Pure Network Code，PNC)。
此外，在仿真過程中，同時考慮兩種場景：靜態的源節點和動態移動的源節點，在下列仿真圖中標記為Staionary和Mobile。將基于BSC策略、TC策略的BDNC協議分別記為BDNC-BSC、BDNC-TC。
3.2 Tmax參數
為了確認TC策略的Tmax參數，評估了它對吞吐量的影響，如圖4所示。從圖可知，隨著Tmax的增加，帶寬節省率也隨之增加，這有利于更合適地設置Tmax。當Tmax=0.3時，帶寬節省率增加緩慢，為此，在下面仿真中，設定Tmax=0.3。
圖4 BDNC-TC的帶寬節省率隨Tmax的變化曲線
3.3 數值分析
3.3.1 時延
圖5顯示了由源節點RSU2發送的消息每跳的平均傳輸時延，其中圖5(a)表示靜態的源節點場景，而圖5(b)表示動態的源節點場景。從圖中可知，在
=1 packet/s時, PNC策略會導致大的時延，而BSC和TC策略有效地控制了時延。隨著
的增加，BSC和PNC時延下降。當
=1.5時，BSC和PNC策略的時延分別為1 s、2 s。而當
=2.5時，這兩個策略的時延約為0.75 s。原因在于
是反映隊列的釋放數據概率，隨著
的增加，隊列的平均時延就下降。此外，TC策略的時延最低，若從時延角度，TC策略是不錯的選擇，TC策略的時延維持在0.3 s，與Tmax持平。
當轉發節點移動時，轉發節點動態的特性影響了網絡的穩定性。從圖5(b)可知，PNC方案的時延波嚴重，但是BSCS方案和TCS方案時延均低于PNC。這也進一步說明，BSCS和TCS方案能夠有效地控制因編碼所帶來的時延。
(a)靜態場景
(b)動態場景
圖5 基于3種不同策略的BDNC協議每跳傳輸時延
3.3.2 帶寬節省率
從圖6(a)可知，當
=1時，NC方案的帶寬節省率近50%，但是這是以高的時延為代價的（見圖5(a)）。而BSCS方案的帶寬節省率了近28%，遠優于TCS方案的13%。然而，隨著
的增加，NC和BSCS方案的性能帶寬節省率性能相近，且緩慢下降。而TCS方案的帶寬節省率的改善幾乎不隨
變化而波動，趨于常數，原因在于TCS方案采用了固定的編碼概率。
(a)靜態場景
(b)動態場景
圖6 基于3種不同策略的BDNC協議帶寬節省率
3.3.3 消息傳輸成功率
圖7描述了平均消息傳輸成功率隨
變化曲線。圖7比較了靜態轉發節點和動態轉發節點兩種情況下的平均消息傳輸成功率，從圖中可知，靜態轉發節點有利于數據轉發，平均數據包傳遞率明顯高于動態轉發節點環境。此外，在動態轉發節點環境下，當
<1.5時，PNC的消息傳輸成功率最低，并且隨著?姿1的增加，消息傳輸成功率慢慢上升，且略優于BSC策略。
圖7 基于3種不同策略的BDNC協議的消息傳輸成功率
3.3.4 未解碼的消息數
最后，分析了未解碼的消息條數。圖8描述了平均每個車輛不能解碼的消息條數。未解碼的數據包是指:車輛收到編碼的消息，但是由于沒有其他消息，無法解碼。這種情況多數由于車輛的移動所引起的。從圖8可知，TCS方案的未編碼消息條數最少。隨著
的增加，未編碼消息條數下降，這主要因為
的增大，消息就不用在隊列中等待過長的時間，相應地，就降低了已編碼消息不能被解碼的概率。
圖8 未編碼的消息數
4 總結
針對車聯網的商業應用，其有兩個源節點向同一個興趣區域傳輸數據。為了提高網絡帶寬利用率，采用網絡編碼技術。為了降低因網絡編碼所增加的額外時延，提出BSC和TC策略。BSC策略從控制緩存區域大小角度控制時延，而TC策略采用定時器原則。仿真結果表明，網絡編碼技術可以有效地提高帶寬利用率，帶寬節省率高達38%；而TC策略更能有效地控制時延，在時延控制方面優于BSC策略。
參考文獻
[1] HARRI J，FIORE M，FILALI 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網絡中小尺度衰落信道仿真[J].通信技術，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，FISAL 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，FISAL 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.