基于服務(wù)量的異構(gòu)車載網(wǎng)絡(luò)資源調(diào)度算法

熊舸　張煜　楊勇

摘要：資源調(diào)度是提高車載網(wǎng)絡(luò)數(shù)據(jù)吞吐量、降低數(shù)據(jù)傳輸時延的重要技術(shù)手段，也是車載網(wǎng)絡(luò)的重點研究內(nèi)容。本文關(guān)注異構(gòu)車載網(wǎng)絡(luò)資源調(diào)度算法研究，提出了一種基于移動服務(wù)量的異構(gòu)車載網(wǎng)絡(luò)資源調(diào)度算法（Moble ServicesResource Scheduling algorithm，MSRS），通過移動服務(wù)量精確刻畫車載網(wǎng)絡(luò)鏈路傳輸能力，在此基礎(chǔ)上采用中繼選擇和最大服務(wù)量配對等手段提升移動車載網(wǎng)絡(luò)的總吞吐量。仿真實驗表明，與現(xiàn)有基于瞬時速率的資源調(diào)度算法相比，在不同車輛數(shù)量、車速、基站覆蓋范圍條件下MSRS算法都可以提供更高的數(shù)據(jù)吞吐量。

關(guān)鍵詞：計算機網(wǎng)絡(luò)；移動服務(wù)量；車載網(wǎng)絡(luò)；資源調(diào)度算法；二分圖

中圖分類號：TP311 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2015.05.012

0 引言

車載網(wǎng)絡(luò)（Vehicular Ad Hoc Networks，VANETs）是支撐智能交通系統(tǒng)（Intelligent Transportation System，ITS）的關(guān)鍵技術(shù)，由具有無線通信能力的車輛節(jié)點或路邊基礎(chǔ)設(shè)施（Roadside Infrastructure Unit，RIU）構(gòu)成。與傳統(tǒng)移動自組織網(wǎng)絡(luò)不同，車載網(wǎng)絡(luò)管理的是公路上高速移動的機動車輛，網(wǎng)絡(luò)拓撲隨車輛移動動態(tài)變化，基于車載網(wǎng)絡(luò)的交通應(yīng)用對通信實時性要求較高。資源調(diào)度是提高車載網(wǎng)絡(luò)數(shù)據(jù)吞吐量、降低數(shù)據(jù)傳輸時延的重要技術(shù)手段，是車載網(wǎng)絡(luò)的重點研究內(nèi)容。

為改進傳統(tǒng)智能交通系統(tǒng)低效的通信模式，車載網(wǎng)絡(luò)以更直接、高效的方式收集、傳播和分發(fā)信息。資源調(diào)度是提高車載網(wǎng)絡(luò)數(shù)據(jù)傳輸能力的重要技術(shù)手段，車載網(wǎng)絡(luò)資源調(diào)度的主要挑戰(zhàn)在于如何有效利用車載網(wǎng)絡(luò)物理層條件（車輛移動性、車輛無線信道、車輛相對位置）滿足應(yīng)用層的需求。

Liu等人研究了如何利用RIU作為協(xié)作中繼幫助車載網(wǎng)絡(luò)車輛傳輸數(shù)據(jù)。Wu等人提出了一種從路邊基站到行駛車輛的下行調(diào)度算法，對車載網(wǎng)絡(luò)下行信道資源進行有效管理。Zhang等人提出了同時考慮上行和下行請求的調(diào)度算法。2013年Li針對WiMAX網(wǎng)絡(luò)和WAVE網(wǎng)絡(luò)中資源調(diào)度方式不同，提出一種基于反饋的兩級資源調(diào)度機制。H.Ilhan等人提出了一種基于放大轉(zhuǎn)發(fā)的自組織Ad Hoc網(wǎng)絡(luò)的車載網(wǎng)絡(luò)架構(gòu)。M.Seyfi等人提出了一種兩跳車載網(wǎng)絡(luò)的中繼選擇策略。M.F.Feteiha等人提出了一種基于多天線放大中繼的車載網(wǎng)絡(luò)資源調(diào)度策略。Zheng等人基于圖論提出了一種車輛與基礎(chǔ)設(shè)施之間的鏈路V2I（Vehicle-to-Infrastructure）和車輛與車輛之間的鏈路V2V（Vehicle-to-Vehicle）并存的車載網(wǎng)絡(luò)資源調(diào)度方法。文獻[18]基于多選擇的聯(lián)合鏈路調(diào)度與資源優(yōu)化方法。文獻[19]基于LTE-Advanced架構(gòu)提出了中繼車載網(wǎng)絡(luò)的一種傳輸方法。

這些研究從車載網(wǎng)絡(luò)信道資源分配管理角度提高了路邊基站的訪問效率。不足之處在于，現(xiàn)有車載網(wǎng)絡(luò)資源調(diào)度方法大多都基于車輛的瞬時狀態(tài)，沒有考慮車輛的移動性，難以準確刻畫車載網(wǎng)絡(luò)鏈路傳輸能力并充分發(fā)揮車載網(wǎng)絡(luò)移動下的系統(tǒng)性能。

1 異構(gòu)車載網(wǎng)絡(luò)

如圖1所示，一個典型的異構(gòu)車載網(wǎng)絡(luò)結(jié)構(gòu)包含公路上高速行駛的車輛節(jié)點和RIU，所有的車輛都可通過V2I/V2V兩種鏈路與RIU通信，進而接入Internet。同時，車輛與車輛之間通過V2V鏈路互相通信，共享路面信息。本文研究的異構(gòu)車載網(wǎng)絡(luò)由V2I（采用LTE-Advanced協(xié)議）和V2V（采用Dedicated Short RangeCommunication，DSRC協(xié)議）兩部分鏈路組成；采用的調(diào)度算法是通過調(diào)度管理車載網(wǎng)絡(luò)傳輸鏈路資源（V2I與V2V），幫助車載網(wǎng)絡(luò)范圍內(nèi)各車輛互相協(xié)作，從而提高車載網(wǎng)絡(luò)整體數(shù)據(jù)傳輸性能。

針對車載網(wǎng)絡(luò)中網(wǎng)絡(luò)節(jié)點是高速移動的機動車輛，本文提出了一種基于移動服務(wù)量的異構(gòu)車載網(wǎng)絡(luò)資源調(diào)度算法（Moble Services Resource Scheduling algorithm，MSRS）。MSRS算法中，由基站對兩種網(wǎng)絡(luò)資源進行統(tǒng)一調(diào)度。與現(xiàn)有算法（Achievable Rate-based Resource Scheduling algorithm，ARRS）使用車輛瞬時可達速率調(diào)度不同，MSRS算法首先依據(jù)車輛的運行軌跡計算調(diào)度周期內(nèi)V2I和V2V鏈路移動服務(wù)量；根據(jù)V2I移動服務(wù)量分配車輛使用直接與基站通信還是通過協(xié)作轉(zhuǎn)發(fā)車輛與基站通信；若車輛為協(xié)作通信方式，基站利用圖論中的二分圖最大權(quán)重匹配算法為車輛分配協(xié)作轉(zhuǎn)發(fā)車輛，車輛作為二分圖頂點、V2I和V2V鏈路為二分圖邊、V2I和V2V移動服務(wù)量為邊的權(quán)重。MSRS算法為異構(gòu)車載網(wǎng)絡(luò)數(shù)據(jù)傳輸提供最大總吞吐量傳輸方案。仿真實驗表明，與現(xiàn)有基于瞬時速率的資源調(diào)度算法相比，在不同車輛數(shù)量、車速、基站覆蓋范圍條件下MSRS算法都可以提供更高的數(shù)據(jù)吞吐量，與窮舉資源調(diào)度算法相比，MSRS算法復(fù)雜度更低。

2 車載網(wǎng)絡(luò)鏈路誤差分析

車載網(wǎng)絡(luò)中由于車輛快速移動，從而導(dǎo)致網(wǎng)絡(luò)拓撲快速變化，節(jié)點間的通信鏈路質(zhì)量變化也很快。采用基于瞬時可達速率的車載網(wǎng)絡(luò)資源調(diào)度算法，為了適應(yīng)網(wǎng)絡(luò)的這種快變特點，必須縮短調(diào)度周期，不斷計算并更新調(diào)度結(jié)果。這會帶來調(diào)度計算和網(wǎng)絡(luò)信令的開銷大幅增長，降低車載網(wǎng)絡(luò)有效傳輸能力。

如圖2所示場景，V1遠離RIU行駛，V2、V3與V1相對行駛靠近RIU。在圖2（a）時刻車載網(wǎng)絡(luò)進行資源調(diào)度，此時若采用傳統(tǒng)的瞬時可達速率作為優(yōu)化目標效用函數(shù)，由于V1此時離RIU近、信道條件好，則V3的最大可達速率策略為選擇V1作為協(xié)作節(jié)點協(xié)助V3與RIU通信。圖2（b）所示為調(diào)度周期結(jié)束時車輛的所在位置。比較圖2（a）與（b）可以看出，由于V3與V1相對行駛且V1逐漸遠離RIU，V3通過V1協(xié)助與RIU的可達速率不斷減少，調(diào)度周期內(nèi)V3獲得的通信速率大大少于預(yù)期。可見，圖2（a）調(diào)度獲得的最優(yōu)調(diào)度方案在實際運行時并不是最優(yōu)方案，調(diào)度方案預(yù)期性能與實際效果有較大誤差。

造成這種誤差的原因是資源調(diào)度方案只考慮車載網(wǎng)絡(luò)的瞬時靜態(tài)可達速率狀態(tài)，并以此為依據(jù)進行資源調(diào)度。而車載網(wǎng)絡(luò)是不斷運動變化的網(wǎng)絡(luò)，節(jié)點相互位置動態(tài)變化，以靜態(tài)方案規(guī)劃動態(tài)變化的網(wǎng)絡(luò)必然造成誤差，難以達到最優(yōu)配置網(wǎng)絡(luò)資源的目的。為減少誤差，現(xiàn)有資源調(diào)度方案大多通過增加調(diào)度頻率、減少調(diào)度周期的方法減少網(wǎng)絡(luò)在調(diào)度周期運行期間與方案規(guī)劃時狀態(tài)的差異。這種方法增加了通信開銷，減少了算法有效持續(xù)時間，越來越不適應(yīng)車輛密度越來越大、車速越來越快的現(xiàn)代交通網(wǎng)絡(luò)。

因此，本文提出基于移動服務(wù)量的車載網(wǎng)絡(luò)資源調(diào)度算法，通過計算調(diào)度周期內(nèi)車輛能獲得的移動服務(wù)量代替調(diào)度時的瞬時可達速率進行車載網(wǎng)絡(luò)資源調(diào)度。該算法能反映調(diào)度周期內(nèi)車輛位置變化帶來的車輛可達速率改變，從而更精確的描述車載網(wǎng)絡(luò)狀態(tài)變化，減少車載網(wǎng)絡(luò)資源調(diào)度算法在實際應(yīng)用中出現(xiàn)的誤差。

3 移動服務(wù)量

為設(shè)計更精確的資源調(diào)度方案，采用移動服務(wù)量代替瞬時可達速率，計算車輛在一個調(diào)度周期可以獲得的移動服務(wù)量，從而更精確的描述車載網(wǎng)絡(luò)鏈路狀態(tài)，為更精確的資源調(diào)度方案設(shè)計打下基礎(chǔ)。定義第k個調(diào)度周期可以獲得的移動服務(wù)量為：

圖7仿真車輛數(shù)目對MSRS算法的影響。20、40、60、80、100、120、140、160、180、200輛車輛隨機分布在道路上，車輛最大時速35m/s，RIU覆蓋半徑500m，每種車輛數(shù)目進行200次實驗取均值。從圖7可以看出，十字路口場景下，無論車輛數(shù)目如何變化，MSRS算法相比ARRS算法所獲得的資源分配方案更優(yōu)，能使車載網(wǎng)絡(luò)達到更大的數(shù)據(jù)吞吐量。

圖8仿真車速對車載網(wǎng)絡(luò)資源調(diào)度算法的影響。100輛車隨機分布在道路上，RIU覆蓋半徑500m，車輛最大時速為22-52m/s，每種車速進行200次實驗取均值。圖8可以看出，十字路口場景下，無論最大車速如何變化，MSRS算法相比ARRS算法得出的資源分配方案更優(yōu)，能使車載網(wǎng)絡(luò)達到更大的數(shù)據(jù)吞吐量。隨著最大車速增加，MSRS算法相對ARRS算法的總吞吐量也呈現(xiàn)不斷增長趨勢；在最大車速大于40米/秒后，MSRS算法相對ARRS算法的性能優(yōu)勢更明顯，說明隨著車速增加，車輛在一個調(diào)度周期移動的距離增大，ARRS算法描述車輛鏈路性能的誤差也越大，因此MSRS算法相對ARRS算法的性能優(yōu)勢更加明顯，MSRS算法更適合高速移動車載網(wǎng)絡(luò)。

圖9仿真RIU覆蓋范圍對車載網(wǎng)絡(luò)資源調(diào)度算法的影響。100輛車輛隨機分布在道路上，車輛最大時速為35m/s，RIU覆蓋半徑500-1500m，為每種覆蓋半徑進行200次實驗取均值。

圖9表明，隨著RIU覆蓋范圍的不斷增加，MSRS算法和ARRS算法的總吞吐量都在不斷下降。這是因為RIU發(fā)送功率不變，當(dāng)RIU覆蓋范圍增加時場景面積相應(yīng)變大，車輛間、車輛與RIU間距離也相應(yīng)增加，因此路徑損耗變大、接收功率降低、吞吐量隨之下降。但無論RIU覆蓋范圍如何變化，MSRS算法都優(yōu)于ARRS算法，MSRS算法使車載網(wǎng)絡(luò)達到更高的數(shù)據(jù)吞吐量。

6 結(jié)論

本文首先分析了近期國內(nèi)外在車載網(wǎng)絡(luò)資源調(diào)度上的研究現(xiàn)狀以及研究中存在的問題。針對這些問題，本文引入移動服務(wù)量的概念，提出了基于移動服務(wù)量的異構(gòu)車載自組網(wǎng)資源分配算法（MSRS），根據(jù)車載網(wǎng)絡(luò)的實際因素（車速、位置）來改進車載網(wǎng)絡(luò)狀態(tài)描述，更精確的根據(jù)車載網(wǎng)絡(luò)狀態(tài)分配車載自組網(wǎng)資源，利用排序選擇、KM算法以及二分查找法設(shè)計了降低復(fù)雜度的算法提高網(wǎng)絡(luò)整體吞吐量。利用MATLAB分別從車載網(wǎng)絡(luò)總車輛數(shù)量、最大車速、RIU覆蓋范圍三方面仿真對車載網(wǎng)絡(luò)整體吞吐量的影響，結(jié)果表明與現(xiàn)有基于瞬時速率的資源調(diào)度算法相比，MSRS算法可以提供更高的數(shù)據(jù)吞吐量，與窮舉資源調(diào)度算法相比，MSRS算法有更低的算法復(fù)雜度。