強(qiáng) 敏,陳曉江,尹小燕,賈茹昭,徐 丹,湯戰(zhàn)勇,房鼎益

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

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

VANET是移動(dòng)自組織網(wǎng)絡(luò)在道路上的應(yīng)用,具有高密度節(jié)點(diǎn)分布、車輛節(jié)點(diǎn)高速移動(dòng)等特點(diǎn),因而VANET中數(shù)據(jù)傳輸面臨無線信道質(zhì)量不穩(wěn)定、網(wǎng)絡(luò)拓?fù)渌蚕⑷f變、無線鏈路壽命短、帶寬受限、通信負(fù)載量大等多重挑戰(zhàn).同時(shí),VANET中異質(zhì)數(shù)據(jù)有不同的傳輸需求.研究結(jié)果表明,若在發(fā)生碰撞前的 0.5s內(nèi)對駕駛者發(fā)出警告,則60%的交通事故可以避免[7].該類數(shù)據(jù)對時(shí)延敏感,需要在嚴(yán)格的時(shí)間限制內(nèi)被傳輸?shù)皆朴?jì)算中心,本文稱其為強(qiáng)實(shí)時(shí)數(shù)據(jù);另一方面,為提升駕駛體驗(yàn)的PM2.5,CO2含量數(shù)據(jù)與音頻視頻數(shù)據(jù)[8-11]對時(shí)延不敏感,對可靠性要求高,本文稱其為弱實(shí)時(shí)數(shù)據(jù).利用 VANET的有限資源,在滿足其傳輸需求的前提下將兩類數(shù)據(jù)傳輸?shù)皆朴?jì)算中心,是本文的研究重點(diǎn).

VANET中,強(qiáng)實(shí)時(shí)數(shù)據(jù)和弱實(shí)時(shí)數(shù)據(jù)共存,形成了混合數(shù)據(jù).本文為強(qiáng)實(shí)時(shí)數(shù)據(jù)和弱實(shí)時(shí)數(shù)據(jù)設(shè)置了不同的優(yōu)先級(jí)別,在傳輸時(shí)提供區(qū)分服務(wù).現(xiàn)存的 VANET傳輸協(xié)議,如專用短距離通信(dedicated short range communications,簡稱 DSRC)協(xié)議,能夠提供基于優(yōu)先級(jí)的數(shù)據(jù)服務(wù).DSRC中,高優(yōu)先級(jí)的強(qiáng)實(shí)時(shí)數(shù)據(jù)流侵占了全部網(wǎng)絡(luò)帶寬,能夠?qū)⒏邇?yōu)先級(jí)的數(shù)據(jù)盡快傳輸?shù)皆朴?jì)算中心,但低優(yōu)先級(jí)的弱實(shí)時(shí)數(shù)據(jù)流則被阻塞,致使駕駛體驗(yàn)降低[12-14].因此,受經(jīng)濟(jì)學(xué)理論的啟發(fā),考慮存儲(chǔ)成本、丟包懲罰與傳輸獎(jiǎng)勵(lì),本文首先提出了面向 VANET的混合流調(diào)度策略,為不同優(yōu)先級(jí)的數(shù)據(jù)流分配傳輸資源,最大化車輛節(jié)點(diǎn)的收益;結(jié)合鏈路狀況,隨后提出了VANET中混合流調(diào)度與路徑選擇聯(lián)合優(yōu)化的數(shù)據(jù)傳輸策略,滿足強(qiáng)實(shí)時(shí)數(shù)據(jù)流對傳輸時(shí)延的需求,同時(shí)提高弱實(shí)時(shí)數(shù)據(jù)流的傳輸可靠性.

1 混合流調(diào)度及研究現(xiàn)狀

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

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

Table 1 Relationship between priority levels and access categories表1 EDCA中優(yōu)先級(jí)別與訪問類別的對應(yīng)關(guān)系

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

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

基于優(yōu)先級(jí)的調(diào)度算法 PQ(priority queuing)[21,22]中,每個(gè)隊(duì)列的調(diào)度與其優(yōu)先級(jí)別密切相關(guān).調(diào)度算法先對高優(yōu)先級(jí)隊(duì)列中的分組進(jìn)行服務(wù),直到全部高優(yōu)先級(jí)別的數(shù)據(jù)分組均被處理后,相對較低優(yōu)先級(jí)隊(duì)列中的分組才能得到調(diào)度.同一隊(duì)列遵循先來先服務(wù)的準(zhǔn)則.因此,PQ能夠?yàn)楦邇?yōu)先級(jí)別的數(shù)據(jù)提供QoS保障.PQ在對低優(yōu)先級(jí)隊(duì)列中的分組進(jìn)行調(diào)度時(shí),若有高優(yōu)先級(jí)隊(duì)列中的分組到達(dá),PQ則立即轉(zhuǎn)去服務(wù)高優(yōu)先級(jí)隊(duì)列中新到達(dá)的分組,導(dǎo)致低優(yōu)先級(jí)隊(duì)列中的分組得不到處理而被“餓死”.本文基于主流隊(duì)列調(diào)度算法,考慮存儲(chǔ)成本、丟包懲罰與傳輸獎(jiǎng)勵(lì),結(jié)合鏈路狀況對 VANET中的混合流進(jìn)行實(shí)時(shí)調(diào)度,為強(qiáng)實(shí)時(shí)數(shù)據(jù)流與弱實(shí)時(shí)數(shù)據(jù)流分配傳輸資源,防止弱實(shí)時(shí)數(shù)據(jù)流被“餓死”.

2 路徑選擇及研究現(xiàn)狀

目前,面向移動(dòng)自組網(wǎng)的路徑選擇算法主要包括平面數(shù)據(jù)傳輸協(xié)議、基于位置的數(shù)據(jù)傳輸協(xié)議以及層次傳輸協(xié)議這3類.

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

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

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

鑒于VANET中無線信道質(zhì)量不穩(wěn)定、網(wǎng)絡(luò)拓?fù)渌蚕⑷f變、無線鏈路壽命短、帶寬受限等特點(diǎn),移動(dòng)自組網(wǎng)中現(xiàn)行的路徑選擇算法不能直接適用于 VANET.因此,本文提出了混合流調(diào)度與路徑選擇聯(lián)合優(yōu)化的思想,為強(qiáng)實(shí)時(shí)數(shù)據(jù)流提供時(shí)延保證,為弱實(shí)時(shí)數(shù)據(jù)流提供可靠性保證.

3 面向VANET的混合流調(diào)度

VANET中,車輛節(jié)點(diǎn)采集環(huán)境數(shù)據(jù)、路況信息等多模態(tài)數(shù)據(jù),基于數(shù)據(jù)對傳輸 QoS的不同需求,分為強(qiáng)實(shí)時(shí)數(shù)據(jù)流與弱實(shí)時(shí)數(shù)據(jù)流,強(qiáng)實(shí)時(shí)數(shù)據(jù)流具有更高的優(yōu)先級(jí)別.本文關(guān)注如何利用 VANET受限的帶寬資源將強(qiáng)實(shí)時(shí)數(shù)據(jù)流實(shí)時(shí)地傳輸?shù)皆朴?jì)算中心,同時(shí)保證弱實(shí)時(shí)數(shù)據(jù)流的可靠傳輸.

3.1 問題描述

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

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

目標(biāo)車輛首先將采集到的所有Traffic數(shù)據(jù)包和Environment數(shù)據(jù)包存放在自己的緩沖區(qū),力求將其發(fā)送至云計(jì)算中心.車輛節(jié)點(diǎn)首先搜索離它最近的 RSU,若搜索到可用的 RSU,則將緩沖區(qū)的數(shù)據(jù)直接傳給 RSU,RSU再將其轉(zhuǎn)發(fā)給云計(jì)算中心;若車輛節(jié)點(diǎn)的通信半徑內(nèi)無可用 RSU,則借助于鄰近的車輛節(jié)點(diǎn),采用多跳的方式,將數(shù)據(jù)發(fā)至RSU,最終將數(shù)據(jù)發(fā)送至云計(jì)算中心,如圖1所示.

Fig.1 System architecture of a VANET圖1 VANET系統(tǒng)架構(gòu)圖

本文中,我們只討論數(shù)據(jù)從車輛節(jié)點(diǎn)流向云計(jì)算中心的情形.云計(jì)算中心對接收到的海量數(shù)據(jù)進(jìn)行處理、分析,實(shí)現(xiàn)各種個(gè)性化VANET服務(wù).

所有車輛持續(xù)地收集Traffic數(shù)據(jù)和Environment數(shù)據(jù),相對于Environment數(shù)據(jù),Traffic數(shù)據(jù)具有較高優(yōu)先級(jí)別,數(shù)據(jù)產(chǎn)生后立即進(jìn)入相應(yīng)的緩沖區(qū)隊(duì)列.而緩沖區(qū)隊(duì)列長度亦有限制.為了避免隊(duì)列溢出,應(yīng)盡快將隊(duì)列中的數(shù)據(jù)發(fā)送出去,但受限的VANET帶寬不可能為所有數(shù)據(jù)提供實(shí)時(shí)服務(wù).因此,需權(quán)衡VANET的通信資源與數(shù)據(jù)的傳輸需求,為兩種數(shù)據(jù)流分配合理的通信資源,最大化系統(tǒng)性能.

3.2 系統(tǒng)建模

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

為了最大化自己的收益,VA應(yīng)盡快將數(shù)據(jù)包發(fā)送出去,應(yīng)優(yōu)先發(fā)送 Traffic包.數(shù)據(jù)包在緩沖區(qū)隊(duì)列中存放,將占用存儲(chǔ)空間,導(dǎo)致相應(yīng)的存儲(chǔ)成本.Traffic包的大小為af,Environment包的大小為ae,單位數(shù)據(jù)的存儲(chǔ)成本記為c.xf表示VA在特定時(shí)間段內(nèi)發(fā)送的Traffic包數(shù)量,xe表示VA發(fā)送的Environment包數(shù)量,t為Traffic數(shù)據(jù)包發(fā)送時(shí)刻.于是,VA的收益可如下計(jì)算.

該目標(biāo)函數(shù)記為 V_MFS模型.其中,公式(2)表示目標(biāo)函數(shù),公式(3)為帶寬約束,公式(4)為 Traffic包的緩沖區(qū)約束,公式(5)為 Environment包的緩沖區(qū)約束,公式(6)為決策變量約束.系統(tǒng)給予VA的獎(jiǎng)勵(lì),包括發(fā)送 Traffic包獎(jiǎng)勵(lì)與Environment獎(jiǎng)勵(lì)之和.因此,VA獲得的總獎(jiǎng)勵(lì)為

VA緩沖區(qū)中的每一個(gè)Traffic或Environment包都會(huì)占據(jù)相應(yīng)的緩存空間,因此,這兩類數(shù)據(jù)包對應(yīng)的存儲(chǔ)成本為

緩沖區(qū)溢出而引發(fā)的懲罰為

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

3.3 問題證明

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

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

V_MFS模型可表示為

因此,本文的V_MFS模型屬于典型的整數(shù)規(guī)劃問題.

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

3.4 算法設(shè)計(jì)

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

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

3.5 模擬退火算法原理

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

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

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

· 如果目標(biāo)函數(shù)的差值Δf小于0,則接受新解;

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

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

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

3.6 面向VANET的混合流調(diào)度策略實(shí)現(xiàn)——TESA算法

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

1)本文將混合流的調(diào)度問題建模為典型的組合優(yōu)化問題,即為V_MFS模型.

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

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

4)目標(biāo)函數(shù),V_MFS模型的目標(biāo)函數(shù)如公式(2)所示.

5)新解的產(chǎn)生規(guī)則,隨機(jī)選取兩類數(shù)據(jù)包中的任意一個(gè)數(shù)據(jù)包i,若i不在待發(fā)送序列,則直接將其放入待發(fā)送序列,或者將i放入待發(fā)送序列的同時(shí)再取出另一數(shù)據(jù)包j;若數(shù)據(jù)包i已經(jīng)在待發(fā)送序列,則取出i,并隨機(jī)放入數(shù)據(jù)包j.

6)價(jià)值差,根據(jù)上述產(chǎn)生新解的3種可能情況,對應(yīng)的價(jià)值差為

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

7)借鑒Metropolis準(zhǔn)則,接受準(zhǔn)則為

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

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

·L表示Markov鏈長度;

·α為退火率;

·s為算法的終止條件.

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

1)控制參數(shù)T的選取

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

2)Markov鏈長的選取

Markov鏈長L對于模擬退火算法至關(guān)重要.TESA算法中,每個(gè)Markov鏈長迭代結(jié)束后,問題的解也會(huì)趨于穩(wěn)定.鏈長L的選擇,應(yīng)使每個(gè)控制參數(shù)T對應(yīng)的解都能趨于穩(wěn)定,對應(yīng)于金屬退火中的粒子狀態(tài)趨于穩(wěn)定.鏈長L若選取得當(dāng),將大幅度提高程序的運(yùn)行效率與結(jié)果.

3)退火率的選取

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

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

4)程序終止條件的確定

算法終止條件為控制參數(shù)T小于某個(gè)正數(shù)值,即當(dāng)控制參數(shù)T<1的時(shí)候程序?qū)⒔K止.目標(biāo)車輛收集到的所有Traffic包的deadline信息被表示為deadline數(shù)組.增加兩個(gè)待發(fā)送序列Traffic和Environment序列,基于算法1,目標(biāo)車輛選擇需要發(fā)送的數(shù)據(jù)包到待發(fā)送序列.

算法1.面向VANET的低時(shí)延混合流調(diào)度策略——TESA算法.

4 VAENT中混合流調(diào)度與路徑選擇的聯(lián)合優(yōu)化

Traffic包和Environment包為VAENT中兩種典型的數(shù)據(jù)包.Traffic包屬強(qiáng)實(shí)時(shí)數(shù)據(jù),其實(shí)時(shí)性必須得以保障.數(shù)據(jù)包的有效調(diào)度能夠確保數(shù)據(jù)被正確發(fā)送,路徑選擇則可以提高數(shù)據(jù)發(fā)送的成功率.對混合流調(diào)度與路徑選擇進(jìn)行聯(lián)合優(yōu)化,VANET的數(shù)據(jù)傳輸成功率將大為提高,Traffic包和Environment包的QoS需求得以保障.

4.1 問題描述

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

由于具有節(jié)點(diǎn)高速移動(dòng)、節(jié)點(diǎn)密度過高、無線鏈路壽命短等特點(diǎn),VANET的傳輸控制協(xié)議更具有挑戰(zhàn)性和獨(dú)創(chuàng)性.如車輛同向行駛時(shí),車輛節(jié)點(diǎn)間的鏈路相對穩(wěn)定,網(wǎng)絡(luò)拓?fù)湟蚕鄬Ψ€(wěn)定;但車輛相向而行時(shí),無線鏈路轉(zhuǎn)瞬即逝,網(wǎng)絡(luò)拓?fù)渥兓?因此,靜態(tài)路由選擇不適于 VANET,需為 VANET設(shè)計(jì)動(dòng)態(tài)自適應(yīng)的路由選擇算法.并且應(yīng)結(jié)合車輛節(jié)點(diǎn)的行駛方向、車速和道路信息,對鏈路進(jìn)行預(yù)測,為車輛節(jié)點(diǎn)選擇最佳下一跳.

4.2 模型建立

在指定時(shí)間內(nèi),VA需將待發(fā)送序列中的Traffic包和Environment包傳輸?shù)皆朴?jì)算中心,VA到云計(jì)算中心有多條可選路徑,每一條候選路徑由若干鏈路組成.

· 若數(shù)據(jù)流k通過了路徑j(luò),即;

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

而且Traffic數(shù)據(jù)流和Environment數(shù)據(jù)流可能分享同一條傳輸鏈路.因此,鏈路l的帶寬應(yīng)滿足:

其中,

·F代表Traffic和Environment兩條數(shù)據(jù)流的集合;

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

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

·L表示該車載自組網(wǎng)中所有鏈路的集合;

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

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

綜上,V_MFSPS數(shù)學(xué)模型如下:

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

4.3 理論分析

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

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

設(shè)每條鏈路容量為cl(B≤cl),βf表示 Traffic包的單位基準(zhǔn)價(jià)值,wf×βf實(shí)質(zhì)仍代表βf,令wf×βf=βf,公式(32)可轉(zhuǎn)換為

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

由此可得:

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

求解的目標(biāo)是使S達(dá)到最優(yōu)值,即maxl∈LS=μ×cl.S與cl成正比,cl越大,S就越大.因此,在混合流調(diào)度與路徑選擇的聯(lián)合優(yōu)化策略中,最佳策略是為Traffic數(shù)據(jù)流和Environment數(shù)據(jù)流選取鏈路容量最大的鏈路所組成的路徑.

4.4 PS&TESA算法設(shè)計(jì)

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

將路徑選擇因素作為決策變量,鏈路容量越大,則目標(biāo)函數(shù)值S越大.當(dāng)目標(biāo)車輛發(fā)送這兩類數(shù)據(jù)流時(shí),從目標(biāo)車輛可用的所有鏈路中選擇鏈路容量最大的一條作為數(shù)據(jù)流的當(dāng)前路徑,并對已選擇過的路徑進(jìn)行標(biāo)記.當(dāng)目標(biāo)車輛移動(dòng)時(shí),根據(jù)前述規(guī)則動(dòng)態(tài)進(jìn)行鏈路選取,直到到達(dá)目的地,即云計(jì)算中心.

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

算法2.面向VANET的混合流調(diào)度與路徑選擇聯(lián)合優(yōu)化的數(shù)據(jù)傳輸策略.

5 實(shí)驗(yàn)結(jié)果與性能分析

為了滿足 VANET中兩種不同優(yōu)先級(jí)的混合數(shù)據(jù)流的傳輸需求,同時(shí)最大化目標(biāo)車輛的收益,本文提出了TESA與PS&TESA算法.仿真實(shí)驗(yàn)結(jié)果可證實(shí)該算法的有效性.

5.1 VANET中混合流調(diào)度與路徑選擇的聯(lián)合優(yōu)化策略性能分析

基于傳輸時(shí)延,評(píng)價(jià)本文所提出的算法的性能.仿真實(shí)驗(yàn)證實(shí)在不同的問題規(guī)模下,本文所提出的PS&TESA算法在時(shí)延方面具有明顯優(yōu)勢.

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

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

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

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

基于傳輸時(shí)延,結(jié)合不同類型數(shù)據(jù)包的速率和緩存區(qū)占用比,對PS&TESA與DSRC算法進(jìn)行比較.仿真實(shí)驗(yàn)結(jié)果表明,相對于DSRC算法優(yōu)先發(fā)送強(qiáng)實(shí)時(shí)數(shù)據(jù)流,本文提出的PS&TESA有效地提高了弱實(shí)時(shí)數(shù)據(jù)流的發(fā)送速率,并降低了緩存區(qū)占用比.由于路徑優(yōu)化的關(guān)系,PS&TESA算法的時(shí)延與DSRC算法相比并無明顯差距.由圖4可知,PS&TESA算法不僅能夠有效地減小Traffic包的傳輸時(shí)延,而且能夠提高弱實(shí)時(shí)數(shù)據(jù)流的發(fā)送速率,降低弱實(shí)時(shí)數(shù)據(jù)流緩存占用比.

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

Fig.4 Performance comparison of PS&TESA and TESA under different packet generating rates圖4 不同數(shù)據(jù)包產(chǎn)生速率下PS&TESA與TESA性能對比

6 總結(jié)與展望

車載自組網(wǎng)具有廣闊的應(yīng)用前景,可在道路上建立一個(gè)自組織、結(jié)構(gòu)開放的車輛實(shí)時(shí)通信網(wǎng)絡(luò),實(shí)現(xiàn)交通預(yù)警、車輛的自動(dòng)化駕駛、提升駕駛舒適度與實(shí)時(shí)路況查詢.VANET中強(qiáng)實(shí)時(shí)數(shù)據(jù)與弱實(shí)時(shí)數(shù)據(jù)共存,數(shù)據(jù)動(dòng)態(tài)產(chǎn)生且不可預(yù)期.同時(shí),VANET通信帶寬受限,面臨無線信道質(zhì)量不穩(wěn)定、網(wǎng)絡(luò)拓?fù)渌蚕⑷f變、無線鏈路壽命短、帶寬受限、通信負(fù)載量大等多重挑戰(zhàn).本文提出了VANET中混合流調(diào)度與路徑選擇聯(lián)合優(yōu)化的數(shù)據(jù)傳輸策略,以滿足強(qiáng)實(shí)時(shí)數(shù)據(jù)流對傳輸時(shí)延的需求,同時(shí)提高弱實(shí)時(shí)數(shù)據(jù)流的傳輸可靠性.仿真實(shí)驗(yàn)與性能分析結(jié)果表明,本文提出的聯(lián)合優(yōu)化策略 PS&TESA不僅能夠減小強(qiáng)實(shí)時(shí)數(shù)據(jù)流的時(shí)延,而且能夠提高弱實(shí)時(shí)數(shù)據(jù)流的發(fā)送速率,降低弱實(shí)時(shí)數(shù)據(jù)流的緩存占用比.