胡玉睿， 張文軍

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

?

·計(jì)算機(jī)技術(shù)應(yīng)用·

車載網(wǎng)中多信道報(bào)文分割傳輸算法

胡玉睿1， 張文軍2

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

為了保證通信質(zhì)量，提出一種多信道報(bào)文分割傳輸算法。首先根據(jù)可用服務(wù)信道(SCH)數(shù)量對報(bào)文進(jìn)行分割，然后利用各個(gè)SCH來傳輸報(bào)文?？紤]到由于部分信道未被使用和部分車輛不可達(dá)所導(dǎo)致的報(bào)文丟失現(xiàn)象，采用隨機(jī)線性網(wǎng)絡(luò)編碼來對報(bào)文進(jìn)行編碼，并根據(jù)信道可用概率和車輛可用概率提出算法來確定需要增加的報(bào)文數(shù)量。仿真實(shí)驗(yàn)結(jié)果表明，該算法的可靠性高、信道使用量低，有效地緩解了車輛密度較低所導(dǎo)致的連接性較弱的問題。

車載網(wǎng)； 多信道； 分割傳輸； 報(bào)文丟失； 網(wǎng)絡(luò)編碼； 可靠性

0 引 言

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

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

1 算 法

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

1.1 挑 戰(zhàn)

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

圖1 成功率比較

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

圖2 連接丟失率比較

1.2 丟失報(bào)文的彌補(bǔ)

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

(1)

1.3 新增網(wǎng)絡(luò)編碼報(bào)文

雖然通過隨機(jī)線性網(wǎng)絡(luò)編碼生成額外報(bào)文可以恢復(fù)丟失報(bào)文，但是本文研究的一個(gè)核心問題是到底應(yīng)該為原來的報(bào)文生成多少個(gè)額外報(bào)文。當(dāng)不需要額外報(bào)文時(shí)，每個(gè)信道中發(fā)送的報(bào)文數(shù)量為Mbase。

(2)

式中：R為多媒體信息初始報(bào)文總數(shù)；N為信道數(shù)量。

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.4 算法實(shí)現(xiàn)

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

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

R←初始報(bào)文總數(shù)

R←信道總數(shù)

Vt←相鄰車輛總數(shù)

M←R/N

γ←N

γ←γ-1

endwhile

returnM

endprocedure

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

2 性能評估

2.1 仿真設(shè)置

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

(a) 30輛/km

(b) 50輛/km

(c) 70輛/km

圖3 不同車輛密度下的三種方案的報(bào)文到達(dá)率比較

圖4(a)給出了信道傳輸一個(gè)報(bào)文的時(shí)間與SCH間隔持續(xù)時(shí)間的比值。從該圖可以看到，對于EDD算法而言，當(dāng)車輛密度增加時(shí)，需要傳輸?shù)念~外報(bào)文的數(shù)量下降，這表明EDD算法提高了信道的利用率。當(dāng)車輛密度不變時(shí)，增加ρ，車輛需要傳輸更多的報(bào)文，系統(tǒng)的可靠性增加，但總的來說EDD算法占用的SCH間隔要低于SC算法。這主要是因?yàn)镋DD算法通過隨機(jī)線性網(wǎng)絡(luò)編碼可以改變待傳輸?shù)膱?bào)文數(shù)量，而SC算法每個(gè)信道的報(bào)文數(shù)量固定。此外，盡管BDD算法在SCH期間使用的資源最少，但BDD的可靠性最低(見圖3)。因此，當(dāng)路邊單元和源車輛距離較遠(yuǎn)時(shí)，BDD算法便無法發(fā)揮作用。

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

(a) 占用的帶寬

(b) 使用的間隔

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

3 結(jié) 語

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

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

[2] 張 宇, 陳 晶, 杜瑞穎, 等. 適于車載網(wǎng)安全通信的高效簽密方案[J]. 電子學(xué)報(bào), 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: 一種基于分簇的多信道車載網(wǎng) MAC 協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 51(3): 502-510.

[10] 張 偉, 劉南杰, 趙海濤. VANET 多信道傳輸中控制信道沖突緩解算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61420106008/F0102)

胡玉睿(1979-)，女，陜西寶雞人，碩士，講師,研究方向?yàn)檐囕d網(wǎng)、智能信息處理。

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

E-mail:1715847023@qq.com

TP 393

A

1006-7167(2016)08-0111-05