VANET中流調度與路徑選擇聯合優化的傳輸策略?

強 敏,陳曉江,尹小燕,賈茹昭,徐 丹,湯戰勇,房鼎益

(西北大學 信息科學與技術學院,陜西 西安 710069)

目前,車載自組網(vehicular ad-hoc network,簡稱 VANET)已經獲得世界各國研究機構與科研工作者的關注.VANET中,車輛節點與路邊設施的強大存儲與計算能力、良好的無線通信能力以及不間斷的能量供應,因而可以檢測車輛行駛環境的變化,評測危險路況并預警,如前方事故現場預警、交叉路口防碰撞預警等,預估司機的反應時間,為安全駕駛及駕駛體驗提供技術支持[1-3].車輛節點配備的傳感器負責采集環境數據與交通狀況數據,借助路邊設施或其他車輛節點,采集的數據被實時地傳輸到云計算中心.云計算中心經過數據挖掘、大數據處理等計算技術對信息進行綜合分析、處理,從而實現智能化的交通信息管理,為智能交通系統的發展提供保障[4-6].VANET中動態產生的數據量與車輛的密集程度息息相關.眾所周知,數據乃 VANET各類應用的前提與基礎,數據應在盡可能短的時間內可靠地傳輸到控制中心.因此,數據傳輸成為 VANET中亟待研究的重要問題之一.

VANET是移動自組織網絡在道路上的應用,具有高密度節點分布、車輛節點高速移動等特點,因而VANET中數據傳輸面臨無線信道質量不穩定、網絡拓撲瞬息萬變、無線鏈路壽命短、帶寬受限、通信負載量大等多重挑戰.同時,VANET中異質數據有不同的傳輸需求.研究結果表明,若在發生碰撞前的 0.5s內對駕駛者發出警告,則60%的交通事故可以避免[7].該類數據對時延敏感,需要在嚴格的時間限制內被傳輸到云計算中心,本文稱其為強實時數據;另一方面,為提升駕駛體驗的PM2.5,CO2含量數據與音頻視頻數據[8-11]對時延不敏感,對可靠性要求高,本文稱其為弱實時數據.利用 VANET的有限資源,在滿足其傳輸需求的前提下將兩類數據傳輸到云計算中心,是本文的研究重點.

VANET中,強實時數據和弱實時數據共存,形成了混合數據.本文為強實時數據和弱實時數據設置了不同的優先級別,在傳輸時提供區分服務.現存的 VANET傳輸協議,如專用短距離通信(dedicated short range communications,簡稱 DSRC)協議,能夠提供基于優先級的數據服務.DSRC中,高優先級的強實時數據流侵占了全部網絡帶寬,能夠將高優先級的數據盡快傳輸到云計算中心,但低優先級的弱實時數據流則被阻塞,致使駕駛體驗降低[12-14].因此,受經濟學理論的啟發,考慮存儲成本、丟包懲罰與傳輸獎勵,本文首先提出了面向 VANET的混合流調度策略,為不同優先級的數據流分配傳輸資源,最大化車輛節點的收益;結合鏈路狀況,隨后提出了VANET中混合流調度與路徑選擇聯合優化的數據傳輸策略,滿足強實時數據流對傳輸時延的需求,同時提高弱實時數據流的傳輸可靠性.

1 混合流調度及研究現狀

迄今,面向VANET的混合流調度策略均基于傳統網絡的傳輸協議,如專用短距離通信協議DSRC.DSRC為VANET中車與車(vehicle to vehicle,簡稱V2V)、車與路邊單元(vehicle to roadside unit,簡稱V2R)間的通信提供支持[15],基于增強的分布式信道訪問(enhanced distributed channel access,簡稱EDCA)機制,為VANET應用中的混合流提供調度策略,為 VANET的數據傳輸提供服務質量(quality of service,簡稱 QoS)保障[12].EDCA為VANET數據賦予不同的優先級,并設計相應的混合流調度策略.對于車輛發生碰撞時產生的危急預警、車輛的實時速度、方向等強實時數據,EDCA賦予其最高優先級別,使其可搶占信道而優先發送;對于環境信息、娛樂信息等弱實時數據,EDCA賦予其較低優先級別,將其暫存在車輛緩沖區,在高優先級數據全部成功傳輸之后,再對其進行發送.DSRC中,EDCA采用8種不同的優先級別,對應4種不同的訪問類別.優先級別與訪問類別間的對應關系見表1[16].

表1中的每個訪問類別(access categories,簡稱AC)對應一個隊列,不同的EDCA參數對應不同的優先級別.除了用戶的優先級別和訪問類別外,EDCA再引入虛擬競爭機制,以解決AC隊列的沖突問題.根據表1的對應關系,AC隊列將來自應用層不同用戶優先級的數據轉發到相應的AC隊列中,高優先級的AC隊列和低優先級的AC隊列發送時機取決于各自的退避計數器.當兩個AC隊列的退避計數器數值都減到0時,兩個AC隊列同時發送數據,引發沖突.沖突發生時,虛擬競爭機制先發送高優先級別的數據,緩存低優先級數據,高優先級別的數據成功發送之后,再發送低優先級別的數據.但是 VANET中,強實時數據的通信負載量大且不可預期,實施調度時易導致弱實時數據流“餓死”,從而導致駕駛體驗降低.

Table 1 Relationship between priority levels and access categories表1 EDCA中優先級別與訪問類別的對應關系

面向隊列的調度方案中,基于輪詢的調度算法尤為經典.其基本思想是:首先調度具有最高優先級別的非空隊列中的分組,然后轉向次優先級別的非空隊列,直到對每個非空隊列都調度一遍之后,再次調度最高優先級別的非空隊列.如此循環往復.常用的基于輪詢的調度算法有輪詢(round robin,簡稱RR)、加權輪詢(weighted round robin,簡稱 WRR)等.基于既定規則,RR[17]調度算法首先將到達服務器的數據分組分配至相應隊列,然后對每個非空隊列依次進行訪問,直到所有隊列都被訪問一遍后再次循環進行.RR算法每次僅服務1個分組,如此能夠保證帶寬資源的共享.但 RR算法的調度單位為分組,數據分組的大小不同將導致帶寬資源分配不均,且不能預測傳輸時延,無法為強實時數據提供時延保障.WRR[18]是RR算法的擴展,遵循一定的分配比例.WRR為不同權值的隊列提供相應服務.WRR可以有效地避免“饑餓”現象的出現,但可變尺寸的分組將導致不公平的資源分配.

基于GPS(general processing sharing)的調度算法[19]立足于協商,即數據流提前向GPS預約資源,一旦預約成功,用戶則獲得事先協商的業務保證.基于GPS的調度算法中,比特為最小的調度單元.基于GPS的調度算法規定,所有的調度隊列優先級別相同,因而能夠確保所有隊列分配到相同的服務資源,在保證公平性的同時,端到端的時延也能得到保障.但基于GPS的調度算法目前是相對理想化的模型,不能投入使用[20].

基于優先級的調度算法 PQ(priority queuing)[21,22]中,每個隊列的調度與其優先級別密切相關.調度算法先對高優先級隊列中的分組進行服務,直到全部高優先級別的數據分組均被處理后,相對較低優先級隊列中的分組才能得到調度.同一隊列遵循先來先服務的準則.因此,PQ能夠為高優先級別的數據提供QoS保障.PQ在對低優先級隊列中的分組進行調度時,若有高優先級隊列中的分組到達,PQ則立即轉去服務高優先級隊列中新到達的分組,導致低優先級隊列中的分組得不到處理而被“餓死”.本文基于主流隊列調度算法,考慮存儲成本、丟包懲罰與傳輸獎勵,結合鏈路狀況對 VANET中的混合流進行實時調度,為強實時數據流與弱實時數據流分配傳輸資源,防止弱實時數據流被“餓死”.

2 路徑選擇及研究現狀

目前,面向移動自組網的路徑選擇算法主要包括平面數據傳輸協議、基于位置的數據傳輸協議以及層次傳輸協議這3類.

基于位置的傳輸協議,其前提是網絡中每個節點的位置已知,節點選擇最近的鄰居節點作為轉發節點.VANET中,由于車輛節點攜帶全球定位系統,易于獲取位置信息,因此,基于位置的傳輸協議為 VANET的主流路由協議;層次數據傳輸協議按照不同歸類基準,將節點劃分為不同大小的簇,由簇頭對簇內節點進行統一管理,數據包分簇發送;平面數據傳輸協議則由每個節點采取主動或者被動的方式建立路由表,實施數據傳輸.GPSR(greedy perimeter stateless routing)[23]是一種典型的基于位置的數據傳輸協議,其選擇轉發節點的依據為邊界轉發和貪婪轉發.GPSR的優點在于節點僅需維護鄰居節點的狀態信息,對于動態變化的拓撲結構具有更好的適應性.原因在于,當節點需要路由時,以距離為基準,GPSR探測其鄰居節點的狀態,選擇距目的節點最近的鄰居節點作為下一跳節點,實現數據轉發.鑒于車輛節點的位置已知,GPSR在VANET中有明顯優勢.但VANET中車輛節點分布不均,源節點與目的節點的最短路徑上不一定存在可用車輛節點.由于缺少中心設備的支持,GPSR難以避免將數據傳輸至車輛稀疏區域,從而使數據僅能通過車輛攜帶的方式傳遞至下一跳,甚至是目的節點,將導致數據包的傳播時延成倍增加.

DSDV(destination sequenced distance vector routing)[24]為典型的平面數據傳輸協議,網絡中的每個節點均可與其他節點建立一條傳輸路徑,節點定期地廣播自己的狀態,鄰居節點獲取廣播消息,以此更新路由表.路由表中包含所有可到達的節點以及跳步數,節點在發送/轉發數據時,優先選擇最小跳步數的路徑.DSDV適用于節點數較少且移動不頻繁的情形,可快速檢測出異常鏈路并有效避免.但當網絡中的節點數目增加且移動速度較快時,DSDV的路由表建立時間增加,周期性的全網鏈路狀態廣播也將給網絡負載帶來巨大壓力.

CGS(cluster-gateway selection)[25]為典型的層次數據傳輸協議,采用分簇思想,簇頭管理簇內移動節點,普通節點一跳將信息傳遞至簇頭,然后,簇頭再利用網關將信息傳遞到目的節點所在的簇.網關指多個簇共同擁有的節點,即網關同屬多個簇,其主要作用是在簇之間傳遞信息.與 DSDV相比,CGS的優點在于路由表的簡化,路由表更新帶來的開銷也隨之降低.但VANET中網絡拓撲結構動態變化,無線鏈路壽命短,簇的維系異常困難,簇頭的失效將引起CGS算法的失效.

鑒于VANET中無線信道質量不穩定、網絡拓撲瞬息萬變、無線鏈路壽命短、帶寬受限等特點,移動自組網中現行的路徑選擇算法不能直接適用于 VANET.因此,本文提出了混合流調度與路徑選擇聯合優化的思想,為強實時數據流提供時延保證,為弱實時數據流提供可靠性保證.

3 面向VANET的混合流調度

VANET中,車輛節點采集環境數據、路況信息等多模態數據,基于數據對傳輸 QoS的不同需求,分為強實時數據流與弱實時數據流,強實時數據流具有更高的優先級別.本文關注如何利用 VANET受限的帶寬資源將強實時數據流實時地傳輸到云計算中心,同時保證弱實時數據流的可靠傳輸.

3.1 問題描述

我們假設VANET中:(1)所有車輛節點均安裝有車載單元(on board unit,簡稱OBU)模塊;(2)車輛在進行數據傳輸時,數據包不會丟失;(3)數據包在傳輸過程中不會發生損耗;(4)路邊單元(road side unit,簡稱RSU)與基礎設備間數據交換的時間可忽略不計;(5)鏈路帶寬相同,用B表示.

VANET中,車輛節點被稱為目標車輛,RSU規則部署于道路邊,RSU都通過大容量電纜被直連到云計算中心.目標車輛的 OBU 模塊采集車輛本身移動參數,比如速度和移動方向以及位置信息等,采集到的此類信息被統稱為 Traffic數據包.同時,OBU模塊也采集車輛所處周圍環境的 CO2含量、PM2.5值等,此類信息被稱為Environment數據包.OBU模塊中配備的無線收發器充當VANET中發送者以及接收者的角色,既能將目標車輛緩沖區中的數據包發送出去,同時也能接收發送給目標車輛的數據包.

目標車輛首先將采集到的所有Traffic數據包和Environment數據包存放在自己的緩沖區,力求將其發送至云計算中心.車輛節點首先搜索離它最近的 RSU,若搜索到可用的 RSU,則將緩沖區的數據直接傳給 RSU,RSU再將其轉發給云計算中心;若車輛節點的通信半徑內無可用 RSU,則借助于鄰近的車輛節點,采用多跳的方式,將數據發至RSU,最終將數據發送至云計算中心,如圖1所示.

Fig.1 System architecture of a VANET圖1 VANET系統架構圖

本文中,我們只討論數據從車輛節點流向云計算中心的情形.云計算中心對接收到的海量數據進行處理、分析,實現各種個性化VANET服務.

所有車輛持續地收集Traffic數據和Environment數據,相對于Environment數據,Traffic數據具有較高優先級別,數據產生后立即進入相應的緩沖區隊列.而緩沖區隊列長度亦有限制.為了避免隊列溢出,應盡快將隊列中的數據發送出去,但受限的VANET帶寬不可能為所有數據提供實時服務.因此,需權衡VANET的通信資源與數據的傳輸需求,為兩種數據流分配合理的通信資源,最大化系統性能.

3.2 系統建模

在時刻t0,目標車輛VA收集到的實時路況數據和道路環境數據分別對應Traffic和Environment數據,設產生Traffic數據包的數目為Af,Environment 數據包的數目為Ae.車輛節點的Traffic隊列中已存在數據包的數目為Souf,目標車輛Environment隊列中已存在的數據包數目為Soue.VA將收集到的兩種數據包分別存放至相應緩沖區隊列,Traffic緩沖區的隊列長度為Qf,Environment隊列的緩沖區隊列長度為Qe.VA每發送一個Traffic包就得到獎勵βf,Traffic包屬強實時數據,每個Traffic包都攜帶deadline信息,除給予每個Traffic包基準獎勵外,系統還根據實際完成時間與deadline的關系,給予額外獎勵.VA每發送一個Environment包將得到獎勵βe,鑒于Traffic包的優先級高于Environment包,設βf>βe.VA將盡力將所有Traffic包和Environment包發送至云計算中心.同時,緩沖區大小有一定限制,若緩沖區溢出,則溢出的包視為被丟棄.引入懲罰函數,計算緩沖區溢出帶來的危害,Traffic包的懲罰因子為γf,Environment數據包的懲罰因子為γe,懲罰因子的設置如公式(1)所示.

為了最大化自己的收益,VA應盡快將數據包發送出去,應優先發送 Traffic包.數據包在緩沖區隊列中存放,將占用存儲空間,導致相應的存儲成本.Traffic包的大小為af,Environment包的大小為ae,單位數據的存儲成本記為c.xf表示VA在特定時間段內發送的Traffic包數量,xe表示VA發送的Environment包數量,t為Traffic數據包發送時刻.于是,VA的收益可如下計算.

該目標函數記為 V_MFS模型.其中,公式(2)表示目標函數,公式(3)為帶寬約束,公式(4)為 Traffic包的緩沖區約束,公式(5)為 Environment包的緩沖區約束,公式(6)為決策變量約束.系統給予VA的獎勵,包括發送 Traffic包獎勵與Environment獎勵之和.因此,VA獲得的總獎勵為

VA緩沖區中的每一個Traffic或Environment包都會占據相應的緩存空間,因此,這兩類數據包對應的存儲成本為

緩沖區溢出而引發的懲罰為

若VA中采集的數據包個數超過相應的緩沖區大小時,懲罰則會啟動,(Af+Souf-Qf)+表示若前者大于后者時,則溢出的包數目為Af+Souf-Qf;若相反,則值為0,即前者小于后者,意味著緩沖區未溢出,則懲罰為0.Environment包的懲罰機制與Traffic包類似.

3.3 問題證明

V_MFS模型所描述的問題是典型的NP-hard問題.

證明:V_MFS模型中主要包括兩部分:第1部分為目標函數S的表達式,第2部分為其約束條件,共有4個線性約束條件,xf與xe為該模型的決策變量,xf表示的是在最大化目標車輛收益時應發送的Traffic包數目,xe則為應發送的Environment包數目.顯而易見,xf與xe的取值均為自然數,即決策變量的取值只能是整數.因此,本文的V_MFS模型與整數規劃問題(integer programming,簡稱IP)一一對應.整數規劃的規范形式為

V_MFS模型可表示為

因此,本文的V_MFS模型屬于典型的整數規劃問題.

整數規劃問題已被證明為NP-hard問題[24],因而本文的V_MFS模型也是NP-hard問題. □

3.4 算法設計

目標車輛VA的緩沖區中分別存放Af個Traffic包以及Ae個Environment包,其緩沖區大小分別為Qf和Qe.目標車輛VA每發送一個Traffic包i,則收到獎勵(deadlinei-t)+×βf,每發送一個Environment包,則會收到獎勵βe.數據包在緩沖區的存放,對應存儲成本,若目標車輛收集到的數據包個數大于緩沖區能夠接受的最大長度時,懲罰將被啟動.目標車輛的收益見公式(2),為了最大化目標車輛VA的收益,即S取最大值.問題的求解思路是:充分利用有限的通信資源,為Traffic數據流與Environment數據流分配最佳帶寬,最大化車輛節點的收益.

借鑒 0-1背包問題的思路,對目標函數求解.0-1背包問題描述如下:現有一組物品,每個物品的價值和重量均已知,對于給定的背包,背包重量有限制,在背包容量限定的范圍內選擇物品,使得背包的總價值最大.對于每個物品,只能選或不選,物品被選擇用1表示,而不被選擇則用0表示,將這類問題稱為0-1背包問題.將目標車輛對Traffic包和Environment包的發送問題進行轉化,確定兩種數據包在某段時間內t′內的發送速率,即確定哪些包被成功發送,哪些包未被發送,統計發送成功的數據包數目即為求解結果.因此,目標函數的求解,被轉化為求解目標車輛緩沖區中每個Traffic包與每個Environment包是否發送,設置中間向量X和Y,X代表Traffic包的發送向量,Y代表Environment包的發送向量,X和Y向量的取值只能是0或者1,0代表不發送該包,1則代表發送該數據包,同一時間段內發送的兩類數據包不能超過帶寬B.考慮所有約束,最大化目標車輛的收益,確定應發送的Traffic包和Environment包,即X向量和Y向量為目標函數的解,統計X以及Y向量中1的數目,得到xf與xe的值,此時對應的S即為最優目標值.因此,Traffic包和Environment包的調度與0-1背包問題對應,帶寬B對應于0-1背包問題中的限定重量,車輛節點的總收益對應于0-1背包問題中的總價值,最終的求解目標均為最大化總價值.V_MFS模型與0-1背包的差別在于:0-1背包問題僅針對1類物品,而本文的模型中則有2種類型的數據包,0-1背包問題中的限定條件只是針對1類物品的重量限定,而本文所提出的V_MFS模型面向2類數據包,帶寬B為2類包的共同限定條件.綜上,本文的V_MFS模型可映射到0-1背包問題,但又有所區別.對于緩沖區中的兩類數據包,并不直接求其需要發送的數據包數目,轉而為緩沖區中的所有數據包進行狀態求解,0為不放入待發送序列,1則表示放入待發送序列.最后,統計狀態為1的數據包數目即為求解結果.

3.5 模擬退火算法原理

模擬退火算法(simulate anneal,簡稱 SA)在求解大規模的組合優化問題方面效果頗佳.SA算法是一種通用概率算法,其思想借鑒于金屬處理工藝中的退火過程,首先將金屬的溫度加熱到充分高,然后再讓其徐徐冷卻,在冷卻過程中,金屬內部的粒子運動逐漸趨于穩定,并且能夠在每個溫度下都達到平衡狀態,最后,金屬內部粒子會達到基態,此時它的內能也逐漸減到最少[26].

應用模擬退火時,首先為控制參數T(對應上述金屬初始溫度)設置初始值,目標函數f(對應于上述金屬的內能)的表達式給定,Markov鏈長度L也給定.在解空間內隨機選擇一個作為初始解,然后根據相應的鄰域函數隨機產生新解,計算目標函數的差值,根據Metropolis準則確定是否接受新解.持續進行上述過程,即隨機產生新解→計算目標函數f差值→確定是否接受新解,迭代次數等于Markov鏈長時,再繼續對控制參數T進行降溫.繼續迭代執行上述過程,隨著控制參數T的減小,系統狀態也將越來越趨于穩定,最終求得最優解.SA算法性能的關鍵是冷卻參數表的選取,冷卻參數表包括控制參數T、退火率α、每個溫度下的迭代次數Markov鏈長度L以及終止條件s.

Metropolis準則是模擬退火算法的精髓,模擬退火與貪心算法相比,差別在于在搜索過程加入了隨機因素,對于比當前解要差的解,并不直接丟棄,而是以一定的概率來接受新解,所以有極大的可能找到全局最優解.而貪心算法僅接受比當前解更優的解,貪心算法因而很容易陷入局部最優而不能達到全局最優.模擬退火算法中接受新解的過程就是Metropolis準則,即

· 如果目標函數的差值Δf小于0,則接受新解;

· 如果Δf大于0,則首先生成一個0-1之間的隨機數,判斷exp(-f′/kT)>Random是否成立:若成立,則接受新解;否則不接受新解.

對于惡化解,不直接丟棄,而是以一定的概率接受.模擬退火算法的流程圖如圖2所示.

Fig.2 Workflow of the simulated annealing algorithm圖2 模擬退火算法流程

3.6 面向VANET的混合流調度策略實現——TESA算法

基于V_MFS模型的分析討論,結合0-1背包的思想,將模型中某段時間內求解的兩種數據流發送速率問題轉化為求解每個數據包是否被發送的問題.不同于貪心算法,模擬退火算法以一定的概率來接受可能會使問題變糟的惡化解.因此,模擬退火算法有更大的概率跳出局部最優,從而找到全局最優解.結合模擬退火算法的思想,本文提出啟發式的TESA算法對目標函數進行求解.TESA算法包括數學模型、問題解空間、初始解、目標函數、新解的產生規則、價值差、Metropolis接受準則,工作流程如下.

1)本文將混合流的調度問題建模為典型的組合優化問題,即為V_MFS模型.

2)問題的解空間即由該問題的所有可行解組成:

3)初始解,可任選解空間中的任一向量為初始解,簡單起見,選擇零向量作為初始解和.

4)目標函數,V_MFS模型的目標函數如公式(2)所示.

5)新解的產生規則,隨機選取兩類數據包中的任意一個數據包i,若i不在待發送序列,則直接將其放入待發送序列,或者將i放入待發送序列的同時再取出另一數據包j;若數據包i已經在待發送序列,則取出i,并隨機放入數據包j.

6)價值差,根據上述產生新解的3種可能情況,對應的價值差為

S(i)表示將數據包i直接放入待發送序列;S(i)-S(j)表示將數據包i放入且將j取出;S(j)-S(i)表示選取的數據包i已經在待發送序列,則將i取出并放入j.

7)借鑒Metropolis準則,接受準則為

本文首先將該問題轉化為與類0-1背包問題,結合模擬退火算法,設計TESA算法,對目標函數求解.模擬退火算法的性能取決于冷卻參數表,冷卻參數表包括一組用來控制算法進程的參數,即(T,L,α,s).

·T表示控制參數,即退火的初始溫度;

·L表示Markov鏈長度;

·α為退火率;

·s為算法的終止條件.

一般地,將退火溫度下降為 0作為算法的終止條件.只有選取了合理的退火參數才能保證模擬退火算法在有限的時間內達到全局收斂性,從而找到全局最優解.

1)控制參數T的選取

控制參數T為初始的退火溫度.T值應設置足夠大,算法的搜索范圍也將隨之增大,最終求得全局最優解的概率也將增加.但若T值過大,則會導致算法的迭代次數增加,使得程序的CPU運行時間明顯增加.因此,T值的選取應與其他參數進行折中考慮,綜合選取.

2)Markov鏈長的選取

Markov鏈長L對于模擬退火算法至關重要.TESA算法中,每個Markov鏈長迭代結束后,問題的解也會趨于穩定.鏈長L的選擇,應使每個控制參數T對應的解都能趨于穩定,對應于金屬退火中的粒子狀態趨于穩定.鏈長L若選取得當,將大幅度提高程序的運行效率與結果.

3)退火率的選取

α為衰減函數的退火率,α用于對控制參數T降溫,降溫的方式有多種,本文選取指數降溫,即

若α過小,則將導致控制參數T快速衰減,致使算法無法訪問更多鄰域,無法搜索更大解空間,最終導致與最優解擦肩而過.因此,退火率α應盡可能地大,使得控制參數T緩慢衰減,從而找到更高質量的解.

4)程序終止條件的確定

算法終止條件為控制參數T小于某個正數值,即當控制參數T<1的時候程序將終止.目標車輛收集到的所有Traffic包的deadline信息被表示為deadline數組.增加兩個待發送序列Traffic和Environment序列,基于算法1,目標車輛選擇需要發送的數據包到待發送序列.

算法1.面向VANET的低時延混合流調度策略——TESA算法.

4 VAENT中混合流調度與路徑選擇的聯合優化

Traffic包和Environment包為VAENT中兩種典型的數據包.Traffic包屬強實時數據,其實時性必須得以保障.數據包的有效調度能夠確保數據被正確發送,路徑選擇則可以提高數據發送的成功率.對混合流調度與路徑選擇進行聯合優化,VANET的數據傳輸成功率將大為提高,Traffic包和Environment包的QoS需求得以保障.

4.1 問題描述

面向VANET的混合流調度策略有效地解決了VANET中優先級不同的數據流共存時的資源與速率分配問題,滿足了兩種數據流的傳輸需求,提高了數據流的傳輸效率.Traffic包和 Environment包為不同優先級的數據,Traffic包所攜帶的信息主要包括車輛的實時位置信息、行駛速度以及方向等,而Environment包攜帶的信息為CO2、PM2.5值等環境參數.Traffic包屬強實時數據,為了確保信息的時效性,Traffic包應盡快被發送到云計算中心.為了將 Traffic數據包快速傳輸到云計算中心,路徑選擇尤為必要.同時,弱實時數據流的傳輸可靠性也能隨之提高.

由于具有節點高速移動、節點密度過高、無線鏈路壽命短等特點,VANET的傳輸控制協議更具有挑戰性和獨創性.如車輛同向行駛時,車輛節點間的鏈路相對穩定,網絡拓撲也相對穩定;但車輛相向而行時,無線鏈路轉瞬即逝,網絡拓撲變化快.因此,靜態路由選擇不適于 VANET,需為 VANET設計動態自適應的路由選擇算法.并且應結合車輛節點的行駛方向、車速和道路信息,對鏈路進行預測,為車輛節點選擇最佳下一跳.

4.2 模型建立

在指定時間內,VA需將待發送序列中的Traffic包和Environment包傳輸到云計算中心,VA到云計算中心有多條可選路徑,每一條候選路徑由若干鏈路組成.

· 若數據流k通過了路徑j,即;

· 若鏈路l屬于該路徑,即.

而且Traffic數據流和Environment數據流可能分享同一條傳輸鏈路.因此,鏈路l的帶寬應滿足:

其中,

·F代表Traffic和Environment兩條數據流的集合;

·j代表任一條數據流的任一候選路徑;

·Pk代表Traffic或Environment數據流的所有候選路徑集合;

·L表示該車載自組網中所有鏈路的集合;

·xk即xf或者xe,ak即af或者ae.

其中,f代表的是Traffic數據流,e代表的是Environment數據流,Pk表示k數據流的所有候選路徑.假如任一條數據流選擇了路徑j,則簡記為;如果恰好鏈路l在被選擇的路徑j上,則記為,鏈路容量記為cl.

綜上,V_MFSPS數學模型如下:

其中,公式(21)為目標函數,公式(22)為帶寬約束,公式(23)和(24)為決策變量約束,公式(25)為路徑約束.相較于V_MFS,對混合流調度與路徑選擇采取聯合優化的模型V_MFSPS可大幅提高數據流的傳輸效率.目標車輛VA采集到的Traffic包數目表示為Af,Environment包數目表示為Ae,Traffic包的緩沖區大小表示為Qf,Environment包的緩沖區大小表示為Qe以及代價因子c,懲罰因子γf和γe已知.S代表鏈路的總收益.結合路徑選擇,V_MFSPS模型可轉換為

4.3 理論分析

V_MFSPS有4個約束條件,ζ為已知常數,要使目標函數值S取最大值,只需討論除ζ之外的部分.于是,對最大化目標函數的問題進行轉換,得到公式(26).

為了獲得S的最大值,對公式(31)進行放松處理,于是可得:

設每條鏈路容量為cl(B≤cl),βf表示 Traffic包的單位基準價值,wf×βf實質仍代表βf,令wf×βf=βf,公式(32)可轉換為

對于 Traffic和 Environment數據包來說,數據包容量越大,說明其攜帶的信息量越大,因此價值也越大.Traffic 數據包的單位價值βf與af成正比,af越大,βf也將會越大;同理,βe與ae也成正比,即

由此可得:

結合約束條件公式(22),可得:

求解的目標是使S達到最優值,即maxl∈LS=μ×cl.S與cl成正比,cl越大,S就越大.因此,在混合流調度與路徑選擇的聯合優化策略中,最佳策略是為Traffic數據流和Environment數據流選取鏈路容量最大的鏈路所組成的路徑.

4.4 PS&TESA算法設計

加入路徑選擇后,決策變量變成3個,分別為目標車輛應發送的Traffic包的數目、Environment包的數目以及鏈路的選擇.xf與xe的取值為整數,對于任意鏈路來說,只有選或不選,故取值為 0或 1.在模型 V_MFSPS中,3個決策變量的取值都為整數,對應的PS&TESA算法也屬整數規劃問題,也是一個NP-hard問題[24].

將路徑選擇因素作為決策變量,鏈路容量越大,則目標函數值S越大.當目標車輛發送這兩類數據流時,從目標車輛可用的所有鏈路中選擇鏈路容量最大的一條作為數據流的當前路徑,并對已選擇過的路徑進行標記.當目標車輛移動時,根據前述規則動態進行鏈路選取,直到到達目的地,即云計算中心.

此啟發式算法命名為PS&TESA算法.算法偽代碼如算法2所示.

算法2.面向VANET的混合流調度與路徑選擇聯合優化的數據傳輸策略.

5 實驗結果與性能分析

為了滿足 VANET中兩種不同優先級的混合數據流的傳輸需求,同時最大化目標車輛的收益,本文提出了TESA與PS&TESA算法.仿真實驗結果可證實該算法的有效性.

5.1 VANET中混合流調度與路徑選擇的聯合優化策略性能分析

基于傳輸時延,評價本文所提出的算法的性能.仿真實驗證實在不同的問題規模下,本文所提出的PS&TESA算法在時延方面具有明顯優勢.

本文采用OMNET++平臺仿真各移動車輛節點數據通信情況,最后采用MATLAB仿真對算法進行性能分析.仿真環境設置為一條雙向通行的城市道路,車輛在兩條車道上均勻分布,車間距為20m,RSU在道路兩側隨機分布,在道路盡頭設置云計算中心.道路兩側均勻分布10輛車,車輛在時間段t內接收Traffic和Environment數據包的數目分別設置為50、100、150和300.設Traffic數據包長度為5KB,Environment數據包長度為3KB.

基于Traffic數據包的傳輸時延,對未進行路徑選擇的TESA算法與加入路徑選擇后的PS&TESA算法進行比較,仿真結果如圖3 所示.Af、Qf、Ae、Qe分別取值為(50,50,40,40)、(100,100,80,80)、(150,150,130,130)、(300,300,270,270),圖3給出了實驗結果.每個問題規模分別進行100次仿真求平均.實驗僅統計Traffic數據流的傳輸時延,取最后一個Traffic包傳輸完成的時間為整條數據流的傳輸時延.由圖3可知,PS&TESA的Traffic傳輸時延明顯低于TESA.即使規模增加,傳輸時延依然呈現出相同的規律,相對于TESA,PS&TESA的Traffic傳輸時延顯著提高.原因在于,與路徑選擇聯合優化的優勢顯而易見,PS&TESA將從所有可用路徑中選擇鏈路容量最大的路徑.鏈路容量越大,丟包率越低,重傳次數減少,傳輸時延減少.PS&TESA 對于強實時數據尤為有效,能夠保證Traffic數據包的傳輸時延.

Fig.3 Comparison of transmission delay between PS&TESA and TESA in different scales圖3 不同規模下PS&TESA與TESA的傳輸時延對比

5.2 PS&TESA與DSRC算法的性能比較

基于傳輸時延,結合不同類型數據包的速率和緩存區占用比,對PS&TESA與DSRC算法進行比較.仿真實驗結果表明,相對于DSRC算法優先發送強實時數據流,本文提出的PS&TESA有效地提高了弱實時數據流的發送速率,并降低了緩存區占用比.由于路徑優化的關系,PS&TESA算法的時延與DSRC算法相比并無明顯差距.由圖4可知,PS&TESA算法不僅能夠有效地減小Traffic包的傳輸時延,而且能夠提高弱實時數據流的發送速率,降低弱實時數據流緩存占用比.

由圖4(a)可知,不同的數據包產生速率下,DSRC算法優先發送強實時數據流,導致弱實時數據流“餓死”.而PS&TESA算法有效地提高了弱實時數據流的發送速率.圖4(b)表明,本文所提出的算法不僅提高了弱實時數據流的發送速率,而且未對強實時數據流產生任何不良影響,與優先發送強實時數據流的DSRC算法相比,兩者的傳輸時延近似.圖4(c)給出了不同的數據包產生速率時兩類數據流占用緩存空間的情況,由圖4(c)可知,PS&TESA算法有效地降低了弱實時數據流的緩存占用比例,降低了緩沖區超負荷溢出概率.

Fig.4 Performance comparison of PS&TESA and TESA under different packet generating rates圖4 不同數據包產生速率下PS&TESA與TESA性能對比

6 總結與展望

車載自組網具有廣闊的應用前景,可在道路上建立一個自組織、結構開放的車輛實時通信網絡,實現交通預警、車輛的自動化駕駛、提升駕駛舒適度與實時路況查詢.VANET中強實時數據與弱實時數據共存,數據動態產生且不可預期.同時,VANET通信帶寬受限,面臨無線信道質量不穩定、網絡拓撲瞬息萬變、無線鏈路壽命短、帶寬受限、通信負載量大等多重挑戰.本文提出了VANET中混合流調度與路徑選擇聯合優化的數據傳輸策略,以滿足強實時數據流對傳輸時延的需求,同時提高弱實時數據流的傳輸可靠性.仿真實驗與性能分析結果表明,本文提出的聯合優化策略 PS&TESA不僅能夠減小強實時數據流的時延,而且能夠提高弱實時數據流的發送速率,降低弱實時數據流的緩存占用比.