基于服務量的異構車載網絡資源調度算法

熊舸　張煜　楊勇

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

關鍵詞：計算機網絡；移動服務量；車載網絡；資源調度算法；二分圖

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

0 引言

車載網絡（Vehicular Ad Hoc Networks，VANETs）是支撐智能交通系統（Intelligent Transportation System，ITS）的關鍵技術，由具有無線通信能力的車輛節點或路邊基礎設施（Roadside Infrastructure Unit，RIU）構成。與傳統移動自組織網絡不同，車載網絡管理的是公路上高速移動的機動車輛，網絡拓撲隨車輛移動動態變化，基于車載網絡的交通應用對通信實時性要求較高。資源調度是提高車載網絡數據吞吐量、降低數據傳輸時延的重要技術手段，是車載網絡的重點研究內容。

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

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

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

1 異構車載網絡

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

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

2 車載網絡鏈路誤差分析

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

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

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

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

3 移動服務量

為設計更精確的資源調度方案，采用移動服務量代替瞬時可達速率，計算車輛在一個調度周期可以獲得的移動服務量，從而更精確的描述車載網絡鏈路狀態，為更精確的資源調度方案設計打下基礎。定義第k個調度周期可以獲得的移動服務量為：

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

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

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

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

6 結論

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