車載網中多信道報文分割傳輸算法

胡玉睿， 張文軍

(1. 重慶化工職業學院， 重慶 400020; 2. 上海交通大學 電子信息與電子工程學院， 上海 200240)

?

·計算機技術應用·

車載網中多信道報文分割傳輸算法

胡玉睿1， 張文軍2

(1. 重慶化工職業學院， 重慶 400020; 2. 上海交通大學 電子信息與電子工程學院， 上海 200240)

為了保證通信質量，提出一種多信道報文分割傳輸算法。首先根據可用服務信道(SCH)數量對報文進行分割，然后利用各個SCH來傳輸報文。考慮到由于部分信道未被使用和部分車輛不可達所導致的報文丟失現象，采用隨機線性網絡編碼來對報文進行編碼，并根據信道可用概率和車輛可用概率提出算法來確定需要增加的報文數量。仿真實驗結果表明，該算法的可靠性高、信道使用量低，有效地緩解了車輛密度較低所導致的連接性較弱的問題。

車載網； 多信道； 分割傳輸； 報文丟失； 網絡編碼； 可靠性

0 引 言

車載網絡(Vehicular Ad-Hoc Networks, VANETs)是車輛間通信及車輛和路邊基礎設施通信的重要手段[1-2]。VANETs標準[3-4]支持6個服務信道(SCHs)和1個控制信道(CCH)。車輛在SCH間隔期間可以加入6個服務信道中的任意一個信道。另外，所有車輛必須在CCH間隔期間加入CCH信道，以便傳輸或接收安全信息。此外，來自所有車輛的信標信號利用該信道進行廣播。VANETs可幫助車輛將各種信息發送給其他車輛或司機。如果通過一個信道傳輸多媒體數據等大量信息，很容易造成控制信道擁塞。一種避免擁塞的可行方法是通過多個信道傳輸多媒體信息[5]。然而，車輛密度較低時多信道連接性較差，增加了多信道數據傳輸的難度[6]，如果這一問題不解決，將導致通信失敗。

使用多信道進行報文傳輸是VANETs的研究熱點。文獻[7]提出一種面向QoS保證的報文傳輸方案。車輛在其通信范圍內形成一個簇，選擇一個車輛作為簇頭，其余車輛作為簇成員接受簇頭車輛的控制。簇頭車輛為其他成員車輛分配信道，使多個信道得到有效共享。然而該方案需要專門的簇建立和維護協議，控制開銷較大。文獻[8]提出基于有向天線的多信道使用算法，實現了空間重用率最大化，降低了報文延時。但是，為了利用多個信道的有向天線，多個車輛間需要就使用的信道和方向進行協調。文獻[9]提出一種基于分簇的多信道混合型MAC協議，簇內通信采用非競爭的TDMA機制，簇間通信采用基于競爭的CSMA/CA機制，相鄰簇采用不同的服務信道。然而該協議要求所有車輛廣播數據，所以信道中的報文存在冗余。文獻[10]針對VANETs中由于多信道傳輸需要進行信道切換導致控制信道起始處的同步沖突問題，文中利用車輛節點估算信道占用率并計算發送概率，對控制信道的傳輸機制進行規劃，為安全消息和業務信道預約消息等設置不同優先級，然后進行自適應信道負載分散，提高了報文傳輸質量。但是該方法需要兩個無線傳輸接收器來偵聽控制信道中的報文，這在真實的VANETs應用場景中是不可行的。針對以上方法的不足，本文采用隨機線性網絡編碼技術，提出了一種面向多信道的報文分割傳輸算法。該算法可在保證系統可靠性的前提下，將每個信道用于傳輸報文的帶寬量降到最低，有效地緩解了車輛密度較低所導致的連接性較弱的問題。

1 算 法

首先分析面向多信道的報文分割傳輸算法所面臨的挑戰，然后考慮到車輛密度低、連接性低等因素所導致的報文丟失問題，通過新增網絡編碼報文來預測被丟失的報文，最后給出算法的偽碼表示。

1.1 挑 戰

分割傳輸算法若要取得成功，所有SCH中的所有分割報文均應被成功傳輸。下面通過一個簡單實驗來分析設計分割傳輸算法面臨的挑戰。設在某一測試場景中，車輛按照不同密度分布于10 km道路上，車輛中報文的傳輸范圍設置為300 m。分割傳輸算法每次運行時，隨機選擇一個源車輛廣播6個多媒體報文。廣播后，所有車輛切換到6個服務信道中的某一個信道。成功接收到報文的車輛稱為中繼車輛，中繼車輛需要轉發信道中的報文。如果每個信道中的每個報文均被成功轉發到另一車輛上，則這次運行視為成功。成功率定義為成功次數與總仿真次數之比。圖1中的測試結果表明，當車輛密度較大時，分割傳輸算法的成功率較高。然而，當車輛密度較低時，成功率也較低。因此，開發出在車輛密度較低或者沒有車輛的條件下仍可有效運行的算法，具有重要意義。

圖1 成功率比較

造成這種現象的因素有兩個：部分信道未被使用(UC)和部分車輛不可達(UV)。信道未被占用，表示部分信道中沒有中繼車輛存在。因為車輛隨機選擇服務信道，所以可能存在中繼車輛只存在于部分信道中的情況，這是密度較低時成功率較低的主要原因。成功率較低的另外一個原因是車輛不可達。之所以出現車輛不可達情況，是因為中繼車輛占據所有6個信道后，在中繼車輛傳輸范圍內沒有其他車輛。因此，中繼車輛無法利用信道傳輸報文。圖2描述了信道和密度不同時關于所有車輛的連接丟失率。當車輛傳輸范圍內沒有其他車輛時，認為發生一次連接性丟失。當車輛位于一個信道時(1ch)，連接性丟失率較低。然而，當車輛分布于6個信道時(6chs)，連接性丟失率上升。從圖2可以看出，即使在一個信道條件下車輛之間連接性較高(CCH間隔)，在多信道間隔期間(SCH間隔)，車輛與相鄰其他車輛間的連接性開始丟失。因此，分割傳輸算法需要處理低連接性問題。

圖2 連接丟失率比較

1.2 丟失報文的彌補

由于部分信道未被使用和部分車輛不可達導致部分信道內的報文未被傳輸，這些報文稱為丟失報文。但是具體而言，信道中的車輛很難知道其他信道中哪些報文被丟失。因此，難以準確預測被丟失的報文。最壞情況下，大部分帶寬將被浪費在無法彌補其他信道報文丟失問題的無用報文上。為此，本文采用網絡編碼來解決這一問題。因為網絡編碼可使報文共享其他報文的內容，當部分報文丟失時，可利用被成功接收的其他報文來恢復丟失信息。鑒于這一特點，可以增加每個信道中的報文數量，不用考慮其他信道丟失哪些報文就可恢復報文。具體而言，本文采用一種隨機線性網絡編碼技術[11]。在該技術中，發送方從Galois域隨機選擇系數，進行報文和系數的線性組合。接收方接收到足夠多的報文和已知系數后進行解碼操作。下式給出了隨機線性網絡編碼的基本操作，

(1)

1.3 新增網絡編碼報文

雖然通過隨機線性網絡編碼生成額外報文可以恢復丟失報文，但是本文研究的一個核心問題是到底應該為原來的報文生成多少個額外報文。當不需要額外報文時，每個信道中發送的報文數量為Mbase。

(2)

式中：R為多媒體信息初始報文總數；N為信道數量。

考慮連接性丟失情況后，本文需要處理的報文數量多于Mbase個。為了確定需要增加的報文數量M，本文考慮兩個因素：信道可用性概率和車輛可用性概率。其中，信道可用性概率表示車輛占用一定數量信道的概率。車輛可用性概率表示車輛位于其他車輛傳輸范圍內的概率。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.4 算法實現

設帶有多媒體安全信息(報文)的車輛，是其他相鄰車輛的數據源。源車輛在CCH間隔中以成功率ρ發送一定數量的編碼報文。成功接收到廣播報文的車輛成為中繼車輛。中繼車輛在SCH間隔內根據成功率ρ，決定新添多少個額外報文。為了確定將被廣播的報文數量，中繼車輛需要利用信道可用性概率Φ，車輛可用性概率Ψ，以及要求的成功率ρ，算法如下。

算法1：為給定的成功率ρ確定數量M。

R←初始報文總數

R←信道總數

Vt←相鄰車輛總數

M←R/N

γ←N

γ←γ-1

endwhile

returnM

endprocedure

根據算法1，中繼車輛增加每個信道中需要發送的報文數量，直到它達到成功率要求ρ為止。SCH間隔結束后，車輛進入CCH。然后，車輛開始通過收集其他車輛擁有的編碼報文來恢復原始信息。為了緩和共享過程中的車輛沖突，采用文獻[12]中的智能廣播算法。在該算法下，距離源車輛最遠的車輛具有最小的競爭窗口，且優先權更高。

2 性能評估

2.1 仿真設置

本文使用ns-3仿真器來評估算法性能。實驗場景設置為：車輛行駛在同向雙車道10 km道路上。在每1 km處測量被中繼傳輸的報文數量。在原點(0 km位置)生成報文，然后被車輛中繼傳輸，直到報文到達終點(10 km位置)。多媒體信息為12 Mb。每個報文的有效負載是1 kb，傳輸速度是3 Mb/s。源車輛在一個CCH間隔發送12個報文。以3 Mb/s速度傳輸時，這12個報文占用CCH間隔70%以上的時間。將SCH數量N設置為6。車輛移動的平均速度為80.467 2 km/h(50英里/h)，標準差為8.046 72 km/h(5英里/h)。

2.2 實驗結果

從3個角度分析算法的性能：可靠性、每個信道被占用的帶寬和間隔的使用。因為需要把報文傳輸給很遠距離之外且當時并不可用的路邊單元，所以可靠性是我們的主要指標。為了衡量可靠性，測量成功到達每個測量點的報文數量，并將其稱為報文到達率。選擇基本的分割傳輸算法(BDD)和單信道算法(SC)作為比較對象。BDD算法根據信道數量分割報文，然后把分割后的報文發送給每個信道。該算法沒有考慮采用網絡編碼和增加額外的報文。SC算法在SCH間隔期間只使用一個信道。本文算法稱為改進后的分割傳輸算法(EDD)，在該算法下，車輛根據仿真開始時明確的ρ，計算每個信道需要傳輸的報文數量M。

報文到達率取決于接收車輛的信噪比(SNR)，以及發送車輛通信范圍內的接收車輛數量。因為無線信道中的報文被隨機丟失，所以如果車輛的信噪比類似，那么報文到達率是通信范圍內車輛數量的函數。當通過廣播方式傳輸報文時，車輛數量對報文丟失率具有重要影響。當部分信道中沒有車輛接收到報文時，本文算法通過利用網絡編碼來有效提升報文到達率。圖3給出了每個測量點的報文到達率。如果在SCH間隔傳輸報文時沒有考慮已經下降了的車輛密度，那么數據傳輸的可靠性較低。三種算法中，BDD的報文到達率最低。SC算法優于BDD算法，但是車輛密度較低時可靠性較好，如圖3(a)所示。SC算法的可靠性較差，是因為在選擇的信道內缺乏接收報文的車輛。然而，在EDD算法中，雖然信道中部分報文未被中繼傳輸，但是其他信道中仍有報文被成功中繼傳輸。EDD算法利用網絡編碼策略成功傳輸這些報文，因此可靠性優于其他算法，如圖3(b),(c)所示。當ρ增加時，EDD算法的可靠性也會增加，原因是在信道中增添了更多額外報文來緩解車輛密度較低時導致的連接性較弱的問題。

(a) 30輛/km

(b) 50輛/km

(c) 70輛/km

圖3 不同車輛密度下的三種方案的報文到達率比較

圖4(a)給出了信道傳輸一個報文的時間與SCH間隔持續時間的比值。從該圖可以看到，對于EDD算法而言，當車輛密度增加時，需要傳輸的額外報文的數量下降，這表明EDD算法提高了信道的利用率。當車輛密度不變時，增加ρ，車輛需要傳輸更多的報文，系統的可靠性增加，但總的來說EDD算法占用的SCH間隔要低于SC算法。這主要是因為EDD算法通過隨機線性網絡編碼可以改變待傳輸的報文數量，而SC算法每個信道的報文數量固定。此外，盡管BDD算法在SCH期間使用的資源最少，但BDD的可靠性最低(見圖3)。因此，當路邊單元和源車輛距離較遠時，BDD算法便無法發揮作用。

圖4(b)表明，傳輸數據時使用的CCH數量較低。為了驗證這一點，將本文算法與只使用CCH間隔的算法(CO)和單信道算法(SC)做比較。在CO算法中，只在CCH間隔發送報文。SC算法和本文算法還利用了SCH間隔，所以CCH使用量低于CO算法。這表明，與CO算法相比，這些算法在CCH間隔可以為信標信息傳輸等安全應用提供更多帶寬。另外還可以看到，SC算法的間隔使用量低于EDD算法。原因是EDD算法需要在CCH間隔共享報文，而不像SC算法那樣將報文轉發給距離最遠的車輛。然而，EDD車輛可在SCH間隔采用多跳轉發策略。對于SC算法，傳輸大量報文會占據被選擇信道的大部分帶寬，因此用于多跳轉發的帶寬很少。對EDD算法，報文數量低于SC算法，使車輛可以采用多跳轉發策略。在圖4(b)中，雙跳EDD算法的CCH間隔使用量低于其他兩種算法。

(a) 占用的帶寬

(b) 使用的間隔

圖4 不同方案的信道使用量比較

3 結 語

多信道報文分割傳輸算法，可實現多媒體緊急信息的快速穩定傳輸。為了避免VANETs的控制信道過載，多媒體內容被分割到可用的服務信道中，因此每個服務信道中的流量負載降到最低水平。然而，如果車輛密度很低，那么連接性丟失問題將會比較嚴重。為此，在信道生存概念中引入網絡編碼技術，在增加可靠性的同時，降低服務信道的帶寬使用量。最后的仿真實驗也驗證了多信道報文分割傳輸算法的有效性。在下一步工作中，我們將針對VANETs中現有的報文轉發方案在可靠性、安全和隱私保護等方面的不足，研究一種面向隱私保護的報文轉發方案。

[1] 羅 娟, 肖 儀, 盧 真, 等. 基于網絡編碼的多播車載網路由算法研究[J]. 計算機研究與發展, 2015, 48(9): 1616-1622.

[2] 張 宇, 陳 晶, 杜瑞穎, 等. 適于車載網安全通信的高效簽密方案[J]. 電子學報, 2015, 43(3): 512-517.

[3] Ros F J, Ruiz P M, Stojmenovic I. Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2012, 11(1): 33-46.

[4] Wang Q, Leng S, Fu H,etal. An IEEE 802.11 p-based multichannel MAC scheme with channel coordination for vehicular ad hoc networks [J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(2): 449-458.

[5] Wasef A, Shen X. EMAP: Expedite message authentication protocol for vehicular ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2013, 12(1): 78-89.

[6] Dua A, Kumar N, Bawa S. A systematic review on routing protocols for vehicular ad hoc networks [J]. Vehicular Communications, 2014, 1(1): 33-52.

[7] Su H, Zhang X. Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks [J]. IEEE Transactions on Vehicular Technology, 2014, 56(6): 3309-3323.

[8] Xie X, Huang B, Yang S,etal. Adaptive multi-channel MAC protocol for dense VANET with directional antennas[C]// 6th IEEE Consumer Communications and Networking Conference(CCNC). Las Vegas, NV, United States: IEEE Press, 2009: 1-5.

[9] 何 鵬, 閻保平, 李 志, 等. CM-MAC: 一種基于分簇的多信道車載網 MAC 協議[J]. 計算機研究與發展, 2015, 51(3): 502-510.

[10] 張 偉, 劉南杰, 趙海濤. VANET 多信道傳輸中控制信道沖突緩解算法研究[J]. 計算機研究與發展, 2015, 25(6): 73-83.

[11] Swapna B T, Eryilmaz A, Shroff N B. Throughput-delay analysis of random linear network coding for wireless broadcasting [J]. IEEE Transactions on Information Theory, 2013, 59(10): 6328-6341.

[12] Amoroso A, Marfia G, Roccetti M. Going realistic and optimal: A distributed multi-hop broadcast algorithm for vehicular safety [J]. Computer Networks, 2011, 55(10): 2504-2519.

Research on Packets Split Transmission Algorithm for Multi-channel in Vehicular Ad-hoc Networks

HUYu-rui1,ZHANGWen-jun2

(1. Chongqing Chemical Industry Vocational College, Chongqing 400020, China; 2. School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

In order to guarantee the communication quality, a packets split transmission algorithm for multi channel is proposed. First, the packets are split by the number of the available service channels (SCH), and then the split packets are transmitted by using the SCH. Considering the packet loss due to the unoccupied channel and the unreached vehicle, the random linear network coding is used to encode the packets, and the algorithm can be used to determine the number of packets to be added according to the available probability of the channel and the available probability of the vehicle. The simulation results show that the proposed algorithm has the higher reliability and the lower channel usage, and can effectively alleviate the weak connectivity problems when the vehicle density is low.

vehicular ad-hoc networks; multi-channel; split transmission; packet loss; network coding; reliability

2015-10-29

國家自然科學基金重點項目(61420106008/F0102)

胡玉睿(1979-)，女，陜西寶雞人，碩士，講師,研究方向為車載網、智能信息處理。

張文軍(1963-)，男，山東人，教授，博士生導師，研究方向：車載網、智能信息處理。

E-mail:1715847023@qq.com

TP 393

A

1006-7167(2016)08-0111-05