車載自組織網(wǎng)絡(luò)環(huán)境下基于軟件定義網(wǎng)絡(luò)的數(shù)據(jù)協(xié)作調(diào)度算法

吳 怡，馬良義，魏允峰，徐哲鑫

(福建師范大學(xué) 光電與信息工程學(xué)院，福州 350007)

(*通信作者電子郵箱wuyi@fjnu.edu.cn)

車載自組織網(wǎng)絡(luò)環(huán)境下基于軟件定義網(wǎng)絡(luò)的數(shù)據(jù)協(xié)作調(diào)度算法

吳 怡*，馬良義，魏允峰，徐哲鑫

(福建師范大學(xué) 光電與信息工程學(xué)院，福州 350007)

(*通信作者電子郵箱wuyi@fjnu.edu.cn)

針對車載自組織網(wǎng)絡(luò)(VANET)中路側(cè)單元(RSU)應(yīng)答車輛請求效率低下的問題，提出基于軟件定義網(wǎng)絡(luò)(SDN)的數(shù)據(jù)調(diào)度算法SDDS。首先，依據(jù)車輛狀態(tài)信息生成策略沖突圖，并求解其最大權(quán)重獨立集，實現(xiàn)單個周期內(nèi)被應(yīng)答請求數(shù)目最大化；其次，通過分析數(shù)據(jù)在車輛節(jié)點中的冗余度對系統(tǒng)服務(wù)能力的影響確定最優(yōu)參數(shù)，設(shè)計了一種基于地理位置的協(xié)助車輛挑選機制；最后，分析跨區(qū)切換車輛的特點和影響多RSU協(xié)作的因素，提出一種基于沖突避免的多RSU協(xié)作機制；此外，提出了新的評價指標(biāo)——服務(wù)效能來評價系統(tǒng)的整體服務(wù)質(zhì)量。仿真實驗中，相比請求數(shù)目優(yōu)先算法(MRF)和協(xié)作數(shù)據(jù)分發(fā)算法(CDD)，SDDS的服務(wù)效能最高增幅達到15%和20%。仿真結(jié)果表明，SDDS能顯著提高調(diào)度系統(tǒng)的服務(wù)效率和質(zhì)量。

數(shù)據(jù)調(diào)度；車載自組織網(wǎng)絡(luò)；軟件定義網(wǎng)絡(luò)；協(xié)作車輛；多路側(cè)單元協(xié)作

0 引言

車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Network, VANET)是智能交通系統(tǒng)(Intelligent Transport System, ITS)的重要組成部分，受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[1-2]。隨著VANET中的新興應(yīng)用越來越多，車和車之間、車和路側(cè)單元(Road Side Unit, RSU)之間共享和傳輸?shù)南⒁苍絹碓蕉鄻踊?，如：路況信息、天氣狀況、基礎(chǔ)設(shè)施分布情況等[3]。當(dāng)面對眾多車輛的多種請求時，RSU迫于信道資源限制，難以為所有發(fā)出請求的車輛提供及時、有效的服務(wù)，因此對于數(shù)據(jù)調(diào)度算法的研究引起了學(xué)術(shù)界的廣泛關(guān)注。

為提高基站的服務(wù)效率和服務(wù)質(zhì)量，數(shù)據(jù)調(diào)度算法成為研究的熱點之一。MRF(Most Requests First)[4]每次優(yōu)先服務(wù)請求數(shù)目較多的請求，導(dǎo)致其所服務(wù)請求大多為出現(xiàn)頻率較高的請求，請求頻率不高的請求就很難被服務(wù)到。文獻[5]提出了一個多信道的數(shù)據(jù)調(diào)度方法，有效地降低了服務(wù)時延，提高了帶寬的利用率。Zhang等[6]提出了一種兩步調(diào)度方案D*S/N(deadline, data size and pending requests)來均衡下載和上傳請求，方案中RSU包含下載隊列和更新隊列，兩個隊列分配不同的帶寬，并且有自己的優(yōu)先分配方案。該方案在選取待服務(wù)請求時引入了參數(shù)截止時間和數(shù)據(jù)包大小，優(yōu)先服務(wù)將要脫離服務(wù)范圍車輛發(fā)出的請求和所請求數(shù)據(jù)包較小的請求，提高了出現(xiàn)頻率低的請求被服務(wù)到的概率；但是當(dāng)上傳請求中所請求數(shù)據(jù)已經(jīng)存在于基站并且已經(jīng)被下載過，則繼續(xù)對其進行服務(wù)會產(chǎn)生重復(fù)性存儲，造成資源浪費和降低系統(tǒng)的運作效率。針對該問題文獻[7]提出了一個聯(lián)合調(diào)度方案來選擇最合適的請求。在該方案中，RSU中同樣包含下載和更新隊列。該方案首先計算出兩個隊列中每個請求的權(quán)重，然后從兩個隊列中選擇權(quán)重最大的兩個請求，最后再選擇權(quán)重大的一個進行服務(wù)。如果上傳隊列中所選請求的權(quán)重大于下載隊列，則檢查該上傳請求所請求數(shù)據(jù)是否已被下載過，如果沒有下載過則提供服務(wù)，否則不提供服務(wù)。為保證安全數(shù)據(jù)的時效性，文獻[8]中將請求分為安全性數(shù)據(jù)和非安全性數(shù)據(jù)，且安全性優(yōu)先級大于非安全性。安全性請求的優(yōu)先級依據(jù)脫離時間、請求車輛數(shù)和數(shù)據(jù)包大小來確定，而非安全性請求的優(yōu)先級依據(jù)請求個數(shù)、脫離時間和數(shù)據(jù)包大小來確定，優(yōu)先處理數(shù)據(jù)包較小的。該方法保證了安全數(shù)據(jù)的優(yōu)先處理并且實現(xiàn)了非安全數(shù)據(jù)被服務(wù)量的最大化。以上這些方法都是以RSU多播為基礎(chǔ)參考請求的請求數(shù)目、緊急情況、數(shù)據(jù)包大小等參數(shù)進行I2V(Infrastructure-to-Vehicle)服務(wù)，而基站受限于信道資源，在單個周期的服務(wù)能力有限，致使總體服務(wù)能力并不是很理想。本文將參考以上文獻所述參數(shù)并側(cè)重于結(jié)合I2V和V2V(Vehicle-to-Vehicle)兩種服務(wù)方式來尋求一種更為有效的數(shù)據(jù)調(diào)度系統(tǒng)。文獻[9]借助車輛的轉(zhuǎn)發(fā)功能提出了一種分布式的緊急消息傳播協(xié)議，提高了緊急消息的投遞率并降低了傳遞時延。文獻[10]提出了一種基于軟件定義網(wǎng)絡(luò)(Software Defined Network, SDN)的數(shù)據(jù)調(diào)度方法CDD(Cooperative Data Dissemination)。該方法依靠SDN的集中控制思想控制系統(tǒng)中所有車輛和RSU的轉(zhuǎn)發(fā)行為，在理論上尋找到了一個全局最優(yōu)的數(shù)據(jù)調(diào)度方案，在整體性能上取得了進一步的提升。該方法中的轉(zhuǎn)發(fā)策略都是基于當(dāng)前車輛狀態(tài)所制成，由于車輛的高速移動性，部分車輛會互相脫離通信范圍導(dǎo)致轉(zhuǎn)發(fā)策略不能完全被執(zhí)行，即部分策略會在當(dāng)前周期內(nèi)失效。針對此問題本文提出了策略失效檢測機制以保證轉(zhuǎn)發(fā)策略的可靠性。此外，由于基站每次只能服務(wù)一種請求，所以數(shù)據(jù)在車輛中分布很稀疏，而且還存在數(shù)據(jù)集中在小范圍區(qū)域的車輛中的情況，當(dāng)距離較遠(yuǎn)且超過通信范圍的車輛請求這些數(shù)據(jù)時，雖然這些數(shù)據(jù)存在于車輛中，但是因為距離問題，這些車輛就不能被V2V方式服務(wù)到，這在一定程度上限制了車輛被服務(wù)的概率。本文針對這個問題提出了協(xié)助轉(zhuǎn)發(fā)車輛的概念，利用協(xié)助轉(zhuǎn)發(fā)車輛增大其他車輛被服務(wù)的概率。

由于車輛的高速移動性以及RSU通信半徑有限，車輛在RSU通信范圍內(nèi)的時間很短，使得單個RSU很難完成對每一個請求的服務(wù)，尤其是當(dāng)車流量比較大時，就會導(dǎo)致很多車輛還未被服務(wù)就已經(jīng)脫離了RSU的服務(wù)范圍。為解決單個RSU的服務(wù)瓶頸，一些專家和學(xué)者提出了一些多RSU協(xié)作的方案。文獻[7]提出DSIN(Deadline Size Inverse Number of pending requests)機制，在該機制中負(fù)載較重的RSU將部分請求轉(zhuǎn)移給預(yù)測車輛運動方向上負(fù)載較輕的RSU，在一定程度上平衡了多個RSU之間的負(fù)載情況，但是車輛在遠(yuǎn)處的RSU范圍內(nèi)重新接受服務(wù)會嚴(yán)重影響請求的時效性。文獻[8]中針對單個RSU負(fù)載過重的情況也作出了相應(yīng)處理，將部分請求轉(zhuǎn)發(fā)至下一個RSU并提升其被服務(wù)的優(yōu)先級，對于請求數(shù)據(jù)量過大致使在一個RSU內(nèi)不能完成傳輸?shù)恼埱笞鲃h除處理。該方法在一定程度上降低了請求被服務(wù)的延遲，減輕了單個RSU特殊時期的負(fù)載。在另外一種機制MPO(Motion Prediction Optimization)中[11]，基站依據(jù)車輛的運動特征預(yù)判車輛的運動軌跡并發(fā)送相關(guān)請求信息給預(yù)期方向上的RSU，減輕了單個RSU在特殊時期的負(fù)載并提高了整體的帶寬利用率，但是與DSIN類似，均難以保證請求信息的時效性。文獻[12]也提出了一些基于車輛運動方向的多RSU負(fù)載均衡的方法。文獻[13]中提出了一種面向高速公路場景的無間隙協(xié)助下載方法(Non-Intermittent Cooperative Downloading Method, NICDM)，目標(biāo)車輛未完成的下載任務(wù)依據(jù)車速、任務(wù)大小以及通信盲區(qū)(Dark Area, DA)距離等信息進行分解，并分別委托行駛方向上的最近2個接入點(Access Point, AP)協(xié)助下載。一組經(jīng)過優(yōu)化選擇的協(xié)助車輛從AP獲得數(shù)據(jù)，并在DA轉(zhuǎn)交給相遇的目標(biāo)車輛。但是對于車輛稀疏的場景，尋找協(xié)助車輛比較困難，而且協(xié)助車輛被占用時間較長，影響協(xié)助車輛自身的請求狀態(tài)。因此本文提出一種基于SDN的多RSU協(xié)作機制，以達到在不影響車輛自身請求行為的情況下降低請求被服務(wù)時延的目的。

本文將以提升車輛請求被服務(wù)率、降低請求被服務(wù)時延為目標(biāo)，提出一種軟件定義數(shù)據(jù)調(diào)度(Software Defined Data Scheduling)算法，該算法基于SDN設(shè)計；將車輛狀態(tài)信息生成轉(zhuǎn)發(fā)策略集，利用轉(zhuǎn)發(fā)策略的有效性檢測機制以確保轉(zhuǎn)發(fā)策略的可靠性；根據(jù)沖突條件將轉(zhuǎn)發(fā)策略集生成策略沖突圖，引入最大獨立集生成算法，通過最大獨立集提取，以確保所選集合為最大策略集且所選策略集之間互相不沖突。基于地理位置合理選擇協(xié)助轉(zhuǎn)發(fā)車輛，并下發(fā)信息以增加車輛間的信息容量，提高車輛間互相被服務(wù)的概率；基于SDN架構(gòu)提出了新的RSU協(xié)作方法，將跨區(qū)切換車輛的請求轉(zhuǎn)發(fā)至鄰近RSU，并挑選合適的協(xié)助服務(wù)車輛以解決RSU邊緣服務(wù)問題，降低跨區(qū)切換車輛請求的服務(wù)時延，提高系統(tǒng)的服務(wù)率;提出新的性能評價指標(biāo)——服務(wù)效能，以綜合評價系統(tǒng)的服務(wù)率和服務(wù)時延。仿真結(jié)果表明所提機制在周期平均服務(wù)能力、服務(wù)效能及車輛間服務(wù)能力上都有明顯的提高。

1 系統(tǒng)場景及模型

本文提出的數(shù)據(jù)調(diào)度方法的系統(tǒng)模型如圖1所示。系統(tǒng)場景與文獻[10]相似，所設(shè)定道路為單向三車道的公路，車輛由右側(cè)進入，多個RSU之間通過電纜連接起來，RSU的服務(wù)區(qū)覆蓋為無縫覆蓋。圖中請求隊列中普通字母表示車輛發(fā)出且未被服務(wù)到的請求，有下劃線的字母表示車輛中已存儲的請求數(shù)據(jù)。車輛發(fā)出的請求可以由RSU對其進行服務(wù)，相應(yīng)的轉(zhuǎn)發(fā)策略為I2V 轉(zhuǎn)發(fā)策略；也可以由已存儲請求車輛所需信息的車輛對其服務(wù)，相應(yīng)的轉(zhuǎn)發(fā)策略為V2V轉(zhuǎn)發(fā)策略。例如：IdV4表示基站發(fā)送數(shù)據(jù)d給車輛V4，V5cV6表示車輛V5發(fā)送數(shù)據(jù)c給車輛V6?；贗EEE1609.4無線通信標(biāo)準(zhǔn)[14-15]，本文將信道劃分為控制信道、V2I和V2V三個信道，控制信道用于傳輸控制信息，V2I信道用于發(fā)出請求和傳輸數(shù)據(jù)，V2V信道僅用于數(shù)據(jù)傳輸，且設(shè)定單位時間內(nèi)車輛只能工作在一個信道內(nèi)。I2V策略工作于V2I信道，V2V策略工作于V2V信道。對于車輛發(fā)送狀態(tài)信息時的信道分配，本文采用IEEE 802.11p MAC(Media Access Control)層的DCF(Distributed Coordination Function)機制[16]。

RSU作為其覆蓋范圍內(nèi)的網(wǎng)絡(luò)控制中心，負(fù)責(zé)依據(jù)車輛上傳的狀態(tài)信息為整體作出調(diào)度策略，并下放表項給車輛以實現(xiàn)整個系統(tǒng)的高效運行，車輛的轉(zhuǎn)發(fā)行為完全依照RSU所下發(fā)表項。其中車輛的狀態(tài)信息包含信息如下：自身標(biāo)識idi、地理位置坐標(biāo)(xi,yi)、當(dāng)前車速Vi、請求隊列rqi、已被服務(wù)請求隊列sqi。其中請求類型ID為車輛中已存儲的信息類型。RSU中維護一個信息列表如下：list={(id0,x0,y0,v0,rq0,sq0),(id1,x1,y1,v1,rq1,sq1),…,(idn,xn,yn,vn,rqn,sqn)}。RSU根據(jù)車輛地理位置及車輛間通信半徑求得每一個節(jié)點的鄰居節(jié)點列表Ni組成鄰居節(jié)點列表N。

圖1 系統(tǒng)模型Fig. 1 System model

2 SDDS算法總體流程

車輛進入RSU的服務(wù)范圍后，在每個周期的開始階段向RSU發(fā)送其自身的狀態(tài)信息，并且隨機地向RSU發(fā)出請求。在該階段，車輛全部工作在V2I信道，RSU處于偵聽狀態(tài)。設(shè)定車輛當(dāng)前處于路側(cè)單元R的服務(wù)范圍內(nèi)，行駛方向上下一個路側(cè)單元為R′。

基于SDN的數(shù)據(jù)調(diào)度算法的總體流程如圖2所示，主要分為四部分：1)RSU依據(jù)車輛上傳的狀態(tài)信息生成所有可能的轉(zhuǎn)發(fā)策略，為提高所生成策略的可靠性，利用策略失效檢測機制判斷策略是否會失效，刪除會失效的策略，得到所有可靠的轉(zhuǎn)發(fā)策略；2)根據(jù)策略沖突條件生成策略沖突圖并通過一種貪婪算法求解出沖突圖的最大獨立集得到當(dāng)前周期內(nèi)的轉(zhuǎn)發(fā)策略集Vselected；3)基于地理位置均勻地選出協(xié)助轉(zhuǎn)發(fā)車輛，生成相應(yīng)的策略并存入Vselected；4)搜索即將脫離當(dāng)前R且還有請求未被服務(wù)到的車輛，將其請求發(fā)給下一個R′，R′尋找合適的服務(wù)策略并反饋R。

圖2 SDDS總體流程Fig. 2 Flow chart of SDDS

3 SDDS各環(huán)節(jié)設(shè)計

3.1 生成策略集

與CDD生成單跳轉(zhuǎn)發(fā)策略集類似，SDDS遍歷所有節(jié)點的請求信息及鄰居節(jié)點列表信息，生成所有可行的轉(zhuǎn)發(fā)策略。如前所述，由于車輛的高速移動性，會導(dǎo)致部分策略在當(dāng)前周期失效，因此本文提出一種失效檢測機制以提高所選策略的可靠性，對于生成的每一個策略檢測其在當(dāng)前周期內(nèi)是否會失效，若會失效則作刪除處理。

(1)

(2)

其中θ為車輛速度與X軸的夾角。若車輛節(jié)點下一秒位置滿足式(3)，則表明該車在下一秒內(nèi)將會脫離RSU的范圍，則該I2V即為失效策略。

(3)

(4)

刪除所有會失效的策略，得到策略集TS。

3.2 構(gòu)造沖突圖求解最大獨立集

本文沿用文獻[10]的方法將策略集TS中每一個策略都視為一個節(jié)點并根據(jù)五種策略沖突條件生成策略沖突圖G={V,E}，V表示策略節(jié)點集，E表示連接兩個節(jié)點的邊，如圖3所示。

圖3 策略沖突圖示例Fig. 3 Example of policy conflict graph

求解策略沖突圖的最大獨立集步驟如下：

1)計算每個策略節(jié)點的權(quán)重wi為：

(5)

其中：Li為節(jié)點的度數(shù)，即在策略沖突圖與其相連節(jié)點的個數(shù)；t為車輛脫離RSU范圍所需時間；α取0.04[10,17]。

2)挑選出權(quán)重最大的策略節(jié)點TSmax，將策略TSmax放入集合Vselected，刪除與TSmax相連的策略節(jié)點。

3)判斷G是否為空，若不為空則返回第2)步。

集合Vselected中策略即為當(dāng)前周期所要執(zhí)行的策略集。由集合Vselected可得在當(dāng)前周期內(nèi)基站組播數(shù)據(jù)di、接收基站信息車輛集VRI、V2V策略中發(fā)送車輛集VS以及接收車輛集VR。

3.3 選取協(xié)助轉(zhuǎn)發(fā)車輛

如前所述車輛中所存儲信息分布不均勻限制了車輛被服務(wù)的概率，為解決這個問題，本文提出了一種基于地理位置的協(xié)助車輛選取方法。該方法基于車輛地理位置均勻地選取協(xié)助轉(zhuǎn)發(fā)車輛，為不影響協(xié)助轉(zhuǎn)發(fā)車輛的自身請求狀態(tài)，所選取車輛都是在當(dāng)前周期處于空閑狀態(tài)的車輛，即協(xié)助轉(zhuǎn)發(fā)車輛不存在于前面所挑選的V2V策略，并將基站在本周期組播的數(shù)據(jù)發(fā)送給它們，實現(xiàn)該數(shù)據(jù)在RSU范圍內(nèi)的全覆蓋均勻分布，以此提高在以后周期內(nèi)該請求被服務(wù)的概率。

選擇協(xié)助轉(zhuǎn)發(fā)車輛的方法如下：首先從道路一端的起點開始等距離地選取n個坐標(biāo)作為協(xié)助轉(zhuǎn)發(fā)點{(xnod0,ynod0),(xnod1,ynod1),…,(xnodn,ynodn)}，如圖4所示。協(xié)助轉(zhuǎn)發(fā)點個數(shù)n的計算公式如下：

n=2·Dr/Dv

(6)

其中:Dr為RSU通信半徑，Dv為車輛通信半徑。

Vhi?VS

(7)

圖4 協(xié)助轉(zhuǎn)發(fā)車輛示例Fig. 4 Example of cooperative relay vehicle

3.4 多RSU協(xié)作機制

如引言所述，由于單個RSU服務(wù)能力有限，導(dǎo)致一些即將駛出RSU范圍的車輛還有請求未被服務(wù)，針對該問題本文提出了一種基于SDN架構(gòu)的多RSU協(xié)作機制，機制中R將即將脫離車輛的請求信息發(fā)給下一個R′，R′負(fù)責(zé)尋找合適的車輛服務(wù)這些請求。具體步驟如下：

步驟1 識別即將脫離RSU服務(wù)范圍的車輛(下稱跨區(qū)切換車輛)，并從中找出還有被服務(wù)潛力的車輛集Vt，Vt中車輛滿足以下兩個條件：1)仍有請求未被服務(wù)到；2)其鄰居節(jié)點中沒有在當(dāng)前周期要發(fā)送數(shù)據(jù)的車輛，該條件保證了該車輛接收信息不會受到其他鏈路的干擾。

步驟2 將Vt中車輛的狀態(tài)信息及當(dāng)前周期的決策信息轉(zhuǎn)發(fā)給其行駛方向上的R′，決策信息包含di、VS和VR中車輛的狀態(tài)信息。R′在其服務(wù)范圍內(nèi)尋找合適的車輛Vni并制成V2V策略表項下發(fā)相關(guān)車輛為其服務(wù)。R′尋找合車輛的方法如下：對于Vt中的Vti，R′在其服務(wù)范圍內(nèi)尋找出滿足以下條件的車輛集Vni：

1)與Vti為鄰居節(jié)點，即Vni滿足式(8),確保Vni在Vti的通信范圍內(nèi)。其中L(A，B)表示A，B兩點之間的距離。

L(Vti,Vni)

(8)

(9)

(10)

(11)

3)Vni滿足式(12)，即Vni中已存儲Vti所需數(shù)據(jù)dj，其中sqni表示車輛Vni中已存儲的信息列表。

dj∈sqni

(12)

4)Vni鄰居節(jié)點在當(dāng)前周期內(nèi)不存在于V2V策略中的接收者，式(13)中Nni表示車輛Vni的鄰居節(jié)點列表，該式確保了Vni作為發(fā)送車輛不會影響其鄰居節(jié)點的接收轉(zhuǎn)狀態(tài)。

(13)

因為跨區(qū)切換車輛都即將駛出邊界，因此跨區(qū)切換車輛距離邊界的距離很近，跨區(qū)切換車輛之間的間距也相對很近，而多個V2V轉(zhuǎn)發(fā)鏈路同時工作在V2V信道會相互影響，所以一旦找到可以為Vti服務(wù)的車輛后就終止搜索。

步驟4R將Vselected中的策略制成表項下發(fā)車輛。至此，發(fā)送車輛和接收車輛都接收到了指令，可以開始進行轉(zhuǎn)發(fā)。如圖1中V6即將駛出RSU1，但是其還有未被服務(wù)到的請求c，則RSU1將V6的狀態(tài)信息轉(zhuǎn)發(fā)給RSU2，RSU2在其服務(wù)范圍內(nèi)找到合適的車輛V5并生成轉(zhuǎn)發(fā)策略V5cV6下發(fā)給車輛V5和V6。

4 性能仿真與分析

4.1 仿真場景及參數(shù)設(shè)置

為了驗證所提算法的有效性，在Matlab中進行了仿真實驗，場景設(shè)置為三條單向的馬路，RSU中數(shù)據(jù)庫模型及請求分布模型設(shè)置同文獻[10]，表1為SDDS機制的性能仿真參數(shù)設(shè)計。

表1 仿真參數(shù)Tab. 1 Simulation parameters

為模擬不同車輛密度下的系統(tǒng)性能，本文設(shè)定了五種交通環(huán)境的仿真參數(shù)如表2所示，隨著場景編號的增大，車輛密度逐漸提升，車輛密度由車速確定，車輛間最小車距為車輛2 s行駛的距離。為分析SDDS機制性能，本文還對比了MRF和CDD機制性能，三種算法仿真的場景參數(shù)相同，所統(tǒng)計各項性能數(shù)據(jù)為一個RSU范圍內(nèi)的數(shù)據(jù)。

表2 不同交通場景下的仿真參數(shù)Tab. 2 Simulation statistics under different traffic scenarios

4.2 仿真結(jié)果分析

系統(tǒng)平均增益是RSU在每個周期內(nèi)服務(wù)到的請求個數(shù)的平均值，既包括I2V所服務(wù)的請求個數(shù)，也包括V2V所服務(wù)到的請求個數(shù)，它反映了單個周期內(nèi)系統(tǒng)服務(wù)車輛的能力大小。圖5所示為在不同場景下三種算法的系統(tǒng)增益曲線，可以看出，三種算法的平均服務(wù)車輛數(shù)隨著車輛密度的逐漸增大都逐漸增多。在各個場景中，SDDS平均服務(wù)數(shù)最多，CDD次之，MRF最少。原因在于MRF的服務(wù)方式只有I2V方式，而CDD和SDDS還引入了V2V服務(wù)方式，并且隨著車輛中所存儲信息的積累，V2V服務(wù)數(shù)所占比重也越來越大，刺激了總服務(wù)數(shù)的增長，所以MRF的平均服務(wù)個數(shù)最少。SDDS在CDD基礎(chǔ)之上又添加了協(xié)助轉(zhuǎn)發(fā)車輛，提高了車輛中的信息含量，增大了車輛之間互相服務(wù)的概率，眾多車輛同時運作進行服務(wù)大大提高了系統(tǒng)的服務(wù)能力；除此之外SDDS還引入了多RSU協(xié)助機制，使得部分跨區(qū)切換的車輛也能受到服務(wù)，也增加了被服務(wù)請求的個數(shù)，所以SDDS的周期平均服務(wù)個數(shù)高于CDD算法。

圖5 不同場景下系統(tǒng)平均增益比較Fig. 5 Average gain of system under different scenarios

為了比較系統(tǒng)的整體增益，本文提出了服務(wù)效能S這一性能指標(biāo)，用以反映系統(tǒng)服務(wù)請求的整體性能，該性能指標(biāo)基于服務(wù)率Ri和平均服務(wù)延遲Di這兩項性能指標(biāo)，計算公式如下：

(14)

服務(wù)率和平均時延的性能曲線分別如圖6和圖7所示。從圖6可以看出在不同的場景下MRF的服務(wù)率最低，CDD的服務(wù)率有明顯提升，而CDD的服務(wù)率最高。這是因為單個周期內(nèi)車輛所發(fā)出的請求個數(shù)是一樣的，所以單個周期內(nèi)平均服務(wù)請求數(shù)目大的算法會有較高的服務(wù)率，故而SDDS的服務(wù)率最高。從圖7可以看出隨著車輛密度的增加，三種算法的時延都有明顯增加，且在各個場景中MRF時延最短，SDDS次之，CDD最長。MRF時延低于SDDS的原因在于:由于MRF服務(wù)基于單個周期內(nèi)請求類型的數(shù)目，而每個周期中請求次數(shù)最多的集中為出現(xiàn)頻率高的請求，所以其只服務(wù)到了出現(xiàn)概率大的信息;又因為其服務(wù)到的信息數(shù)目相對最少(詳見圖5),而平均服務(wù)時延是由已被服務(wù)的請求的時延統(tǒng)計而來，故而服務(wù)請求數(shù)目較少且服務(wù)類型為高頻請求的MRF機制的時延較低。相對于MRF，SDDS單個周期內(nèi)服務(wù)的請求數(shù)目多且不局限于出現(xiàn)頻率高的請求，即SDDS比MRF服務(wù)了更多的請求類型，服務(wù)了更多的時延較長的請求，故而SDDS的平均時延高于MRF。SDDS的平均時延低于CDD的原因在于SDDS提升了車輛中的信息含量，強化了V2V服務(wù)方式，使得SDDS可以在單個周期內(nèi)通過V2V方式服務(wù)到更多的車輛，從而在總體上降低了車輛等待的時間。但綜合考慮兩個指標(biāo)，即從服務(wù)效能上看，性能曲線如圖8所示，隨著場景編號的增大，三條曲線都呈下降趨勢。這意味著隨著車輛密度越大，服務(wù)效能越低，但是所提機制在各個場景下的服務(wù)效能均優(yōu)于其他兩種機制，并且隨著車輛密度的增加，其下降的幅度也相對比較平緩。SDDS服務(wù)效能高于MRF的原因在于SDDS有著最高的服務(wù)率和較低的服務(wù)時延，服務(wù)率上的優(yōu)勢彌補了平均服務(wù)時延上的欠缺并在整體性能上超越了MRF。MRF雖然在車輛密度小的場景下有較好的服務(wù)效能，但是隨著密度增大，其下降的幅度是最大的，并且在場景5中其服務(wù)效能是最差的，這歸咎于其較低的服務(wù)率。CDD整體下降幅度不大，但是其服務(wù)效能遠(yuǎn)小于SDDS，這是因為其在服務(wù)率和服務(wù)時延上都不具有優(yōu)勢，故而服務(wù)效能最差。所以本文所提出機制的整體服務(wù)性能是最優(yōu)的。

圖6 不同場景下服務(wù)率比較Fig. 6 Service ratio under different scenarios

圖7 不同場景下服務(wù)延遲比較Fig. 7 Service delay under different scenarios

在SDDS中，請求可以通過I2V和V2V兩種方式被服務(wù)到，為了更清晰地查看這兩種服務(wù)方式所占比重，本文還分別統(tǒng)計了這兩種服務(wù)方式各自的服務(wù)數(shù)目。其中：分布式產(chǎn)能為平均每個周期內(nèi)以V2V方式服務(wù)到的請求數(shù)，反映了系統(tǒng)的分布式服務(wù)能力；I2V廣播產(chǎn)能為RSU平均每個周期內(nèi)以I2V方式服務(wù)到的車輛數(shù)，反映了系統(tǒng)中基站廣播服務(wù)能力。

圖9為在不同場景下CDD和SDDS兩種算法的車輛服務(wù)產(chǎn)能曲線，橫坐標(biāo)還是為場景編號，縱坐標(biāo)為車輛服務(wù)產(chǎn)能，即通過V2V方式服務(wù)到的平均請求個數(shù)。因為MRF只有I2V服務(wù)模式，所以圖中無MRF參與比較。由圖可以看出SDDS算法的車輛服務(wù)產(chǎn)能明顯高于CDD，原因在于SDDS機制中有借助協(xié)助轉(zhuǎn)發(fā)車輛的轉(zhuǎn)發(fā)能力，進一步增加了以后周期內(nèi)車輛間互相被服務(wù)的概率，并且增加了RSU協(xié)作機制，最終的協(xié)作方式也是通過V2V方式來完成服務(wù)的，所以SDDS中充分發(fā)揮了車輛間互相服務(wù)的潛力，在車輛間服務(wù)產(chǎn)能上表現(xiàn)更為出色。

圖8 不同場景下服務(wù)效能比較Fig. 8 Service efficiency under different scenarios

圖9 不同場景下分布式產(chǎn)能比較Fig. 9 Distributed productivity under different scenarios

圖10所示為不同場景下I2V廣播產(chǎn)能的曲線，可以看出，隨著車輛密度的增大，三種算法的I2V服務(wù)產(chǎn)能都呈現(xiàn)逐漸上升的趨勢。因為MRF每個周期都選擇請求數(shù)目最多的請求進行服務(wù)，所以其基站服務(wù)能力最強；而CDD和SDDS在選擇I2V和V2V時對兩種策略進行了權(quán)衡處理，更傾向?qū)で笳w最優(yōu)方案，所以會在I2V服務(wù)上有所欠缺。CDD該性能高于SDDS的原因在于SDDS增加了協(xié)助轉(zhuǎn)發(fā)車輛，增強了車輛之間的互相服務(wù)能力，使得車輛被車輛服務(wù)的概率大于基站對車輛的服務(wù)概率，從而導(dǎo)致了I2V的減少。

5 結(jié)語

針對RSU服務(wù)范圍內(nèi)的數(shù)據(jù)調(diào)度問題，提出了基于SDN的數(shù)據(jù)調(diào)度算法SDDS，在CDD的基礎(chǔ)之上提出了轉(zhuǎn)發(fā)策略失效監(jiān)測算法，監(jiān)測在當(dāng)前周期會失效的策略并刪除，保障了轉(zhuǎn)發(fā)策略的可靠性；將轉(zhuǎn)發(fā)策略生成策略沖突圖并引入最大獨立集提取算法，求得策略集的最大獨立集，實現(xiàn)了轉(zhuǎn)發(fā)策略集的最大化；基于地理位置均勻地選取協(xié)助轉(zhuǎn)發(fā)車輛，將基站廣播信息發(fā)送到更多的車輛中，提高了車輛間的信息容量，進而提高了車輛被車輛服務(wù)的概率；將跨區(qū)切換車輛的未被服務(wù)信息發(fā)送給鄰居RSU，鄰居RSU選取合適車輛為其服務(wù)，降低了跨區(qū)切換車輛請求的服務(wù)時延，改善了系統(tǒng)的服務(wù)效能。最后仿真表明，SDDS在不同車輛密度場景下的周期平均服務(wù)能力、服務(wù)效能、車輛間服務(wù)能力上均優(yōu)于CDD機制與MRF機制；SDDS在基站服務(wù)產(chǎn)能上不及MRF和CDD，但SDDS在V2V服務(wù)產(chǎn)能上的優(yōu)勢可以彌補基站服務(wù)性能的不足。本文的研究工作是假定RSU包含所有數(shù)據(jù)內(nèi)容，但RSU緩存空間有限，大多數(shù)據(jù)內(nèi)容還需要從數(shù)據(jù)中心獲取，導(dǎo)致網(wǎng)絡(luò)間重復(fù)性流量。因此，RSU如何在緩存空間有限的情況下保證一定的服務(wù)效能并減少網(wǎng)絡(luò)間流量，將是下一步的研究內(nèi)容。

圖10 不同場景下I2V廣播產(chǎn)能比較Fig. 10 I2V broadcast productivity under different scenarios

References)

[1] WANG H, LIU R P, NI W, et al. VANET modeling and clustering design under practical traffic, channel and mobility conditions [J]. IEEE Transactions on Communications, 2015, 63(3): 870-881.

[2] AKHTAR N, ERGEN S C, OZKASAP O. Vehicle mobility and communication channel models for realistic and efficient highway VANET simulation [J]. IEEE Transactions on Vehicular Technology, 2015, 64(1): 248-262.

[3] NEGI S, SINGH S, GOEL S K, et al. Data scheduling in VANET: a survey [J]. International Journal of Computer Science Trends and Technology, 2016, 4(2): 25-31.

[4] ALI G G M N, CHAN E. Co-operative data access in multiple road side units (RSUs)-based Vehicular Ad Hoc Networks (VANETs) [C]// ATNAC 2011: Proceedings of the 2011 Australasian Telecommunication Networks and Applications Conference. Piscataway, NJ: IEEE, 2011: 1-6.

[5] LIU K, LEE V C S, LEUNG K R P H. Data scheduling for multi-item requests in multi-channel on-demand broadcast environments [C]// MobiDE ’08: Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York: ACM, 2008: 47-54.

[6] ZHANG Y, ZHAO J, CAO G. Service scheduling of vehicle-roadside data access [J]. Mobile Networks and Applications, 2010, 15(1): 83-96.

[7] ALI G G M N, CHAN E, LI W. Two-step joint scheduling scheme for road side units (RSUs)-based vehicular Ad Hoc networks (VANETs) [C]// DASFAA’11: Proceedings of the 16th International Conference on Database Systems for Advanced Applications. Berlin: Springer-Verlag, 2011: 453-464.

[8] BOK K, HONG S, LIM J, et al. A multiple RSU scheduling for V2I-based data services [C]// Proceedings of the 2016 International Conference on Big Data and Smart Computing. Washington, DC: IEEE Computer Society, 2016: 163-168.

[9] ZEMOURI S, DJAHEL S, MURPHY J. A fast, reliable and lightweight distributed dissemination protocol for safety messages in urban vehicular networks [J]. Ad Hoc Networks, 2015, 27: 26-43.

[10] LIU K, NG J K Y, LEE V C S, et al. Cooperative data scheduling in hybrid vehicular Ad Hoc networks: VANET as a software defined network [J]. IEEE/ACM Transactions on Networking, 2016, 24(3): 1759-1773.

[11] GUI Y, CHAN E, A motion prediction based cooperative scheduling scheme for vehicle-roadside data access [C]// Proceedings of the 2011 2nd International Conference on Networking and Information Technology. Singapore: IACSIT Press, 2011: 195-204.

[12] GUI Y, CHAN E. Data scheduling for multi-item requests in vehicle-roadside data access with motion prediction based workload transfer [C]// WAINA ’12: Proceedings of the 2012 26th International Conference on Advanced Information Networking and Applications Workshops. Washington, DC: IEEE Computer Society, 2012: 569-574.

[13] 謝永,吳黎兵,何炎祥,等.無間隙的車聯(lián)網(wǎng)協(xié)助下載方法[J].通信學(xué)報,2016,37(1):180-190. (XIE Y, WU L B, HE Y X, et al. Non-intermittent cooperative downloading approach for VANET [J]. Journal on Communications, 2016, 37(1): 180-190.)

[14] 張書僑.DSRC無線通信模式的原理及應(yīng)用[J].數(shù)字通信世界,2014(9):43-45. (ZHANG S Q. The principle and application of DSRC wireless communication mode [J]. Digital Communication World, 2014(9): 43-45.)

[15] MORGAN Y L. Notes on DSRC & WAVE standards suite: Its architecture, design, and characteristics [J]. IEEE Communications Surveys & Tutorials, 2010, 12(4): 504-518.

[16] WU Q, ZHENG J. Performance modeling and analysis of IEEE 802.11 DCF based fair channel access for vehicle-to-roadside communication in a non-saturated state [J]. Wireless Networks, 2015, 21(1): 1-11.

[17] BOURGIN G, BOURRICAUD F, GERNET L, et al. Review: human behavior and the principle of least effort (an introduction to human ecology) by George Ripf Kingsley [J]. Lannée Sociologique, 1948-1949, 3(3): 157-158.

This work is partially supported by the National Natural Science Foundation of China (61571128), the Research Fund for the Doctoral Program of Higher Education of China (20133503120003), the Key Projects of Science and Technology Plan for Industy of the Science and Technology Department of Fujian Province (2014H0019).

WUYi, born in 1970, Ph. D., professor. Her research interests include wireless communication network, computer network.

MALiangyi, born in 1993, M. S. candidate. His research interests include mobile communication, computer network.

WEIYunfeng, born in 1988, M. S. candidate. His research interests include photo-communication, computer network.

XUZhexin, born in 1985, Ph. D., associate professor.His research interests include wireless communication network, smart home.

DataschedulingalgorithmbasedonsoftwaredefinednetworkforvehicularAdHocnetwork

WU Yi*, MA Liangyi, WEI Yunfeng, XU Zhexin

(CollegeofPhotonicandElectronicEngineering,FujianNormalUniversity,FuzhouFujian350007,China)

Focusing on the issue that the Road Side Unit (RSU) has inefficient response to the request of the vehicles in Vehicular Ad Hoc Network (VANET), a data scheduling algorithm based on Software Defined Network (SDN) architecture, namely SDDS, was proposed. Firstly, a graph of conflicting policies was generated based on status information of vehicles, and a maximum weighted independent set of the graph was solved to maximize the number of satisfied requests in current cycle. Secondly, the redundancy of data in vehicles was analyzed to figure out the optimum parameter, and a selection mechanism for collaborative vehicles was designed based on geographical position. Finally, the characteristics of handover vehicles and some factors that would affect the multi-RSU cooperation were analyzed, and a multi-RSU cooperation mechanism was put forward based on collision avoidance. In addition, a new evaluation indicator, service efficiency, was proposed to estimate the overall quality of service. Simulation results showed that compared with Most Requests First (MRF) and Cooperative Data Dissemination (CDD) algorithms, the service efficiency of SDDS algorithm was increased up to 15% and 20% respectively. The simulation results prove that SDDS algorithm can observably improve the sevice eficiency and quality of scheduling system.

data scheduling; Vehicular Ad Hoc NETwork (VANET); Software Defined Network (SDN); collaborative vehicle; multiple Road Side Unit (multi-RSU) cooperation

TN929.52

A

2017- 01- 13;

2017- 03- 03。

國家自然科學(xué)基金資助項目(61571128)；教育部高等學(xué)校博士學(xué)科點專項科研基金(新教師類)資助項目(20133503120003)；福建省科技廳工業(yè)科技計劃重點項目(2014H0019)。

吳怡(1970—)，女，遼寧葫蘆島人，教授，博士，主要研究方向：無線通信網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)； 馬良義(1993—)，男，河南濮陽人，碩士研究生，主要研究方向：移動通信、計算機網(wǎng)絡(luò)； 魏允峰(1988—)，男，安徽亳州人，碩士研究生，主要研究方向：光通信、計算機網(wǎng)絡(luò)； 徐哲鑫(1985—)，男，福建福州人，副教授，博士，主要研究方向：無線通信網(wǎng)絡(luò)、智能家居。

1001- 9081(2017)08- 2139- 06

10.11772/j.issn.1001- 9081.2017.08.2139