車載自組織網絡環境下基于軟件定義網絡的數據協作調度算法

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

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

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

車載自組織網絡環境下基于軟件定義網絡的數據協作調度算法

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

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

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

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

數據調度；車載自組織網絡；軟件定義網絡；協作車輛；多路側單元協作

0 引言

車載自組織網絡(Vehicular Ad Hoc Network, VANET)是智能交通系統(Intelligent Transport System, ITS)的重要組成部分，受到了學術界和工業界的廣泛關注[1-2]。隨著VANET中的新興應用越來越多，車和車之間、車和路側單元(Road Side Unit, RSU)之間共享和傳輸的消息也越來越多樣化，如：路況信息、天氣狀況、基礎設施分布情況等[3]。當面對眾多車輛的多種請求時，RSU迫于信道資源限制，難以為所有發出請求的車輛提供及時、有效的服務，因此對于數據調度算法的研究引起了學術界的廣泛關注。

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

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

本文將以提升車輛請求被服務率、降低請求被服務時延為目標，提出一種軟件定義數據調度(Software Defined Data Scheduling)算法，該算法基于SDN設計；將車輛狀態信息生成轉發策略集，利用轉發策略的有效性檢測機制以確保轉發策略的可靠性；根據沖突條件將轉發策略集生成策略沖突圖，引入最大獨立集生成算法，通過最大獨立集提取，以確保所選集合為最大策略集且所選策略集之間互相不沖突?；诘乩砦恢煤侠磉x擇協助轉發車輛，并下發信息以增加車輛間的信息容量，提高車輛間互相被服務的概率；基于SDN架構提出了新的RSU協作方法，將跨區切換車輛的請求轉發至鄰近RSU，并挑選合適的協助服務車輛以解決RSU邊緣服務問題，降低跨區切換車輛請求的服務時延，提高系統的服務率;提出新的性能評價指標——服務效能，以綜合評價系統的服務率和服務時延。仿真結果表明所提機制在周期平均服務能力、服務效能及車輛間服務能力上都有明顯的提高。

1 系統場景及模型

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

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

圖1 系統模型Fig. 1 System model

2 SDDS算法總體流程

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

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

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

3 SDDS各環節設計

3.1 生成策略集

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

(1)

(2)

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

(3)

(4)

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

3.2 構造沖突圖求解最大獨立集

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

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

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

1)計算每個策略節點的權重wi為：

(5)

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

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

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

集合Vselected中策略即為當前周期所要執行的策略集。由集合Vselected可得在當前周期內基站組播數據di、接收基站信息車輛集VRI、V2V策略中發送車輛集VS以及接收車輛集VR。

3.3 選取協助轉發車輛

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

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

n=2·Dr/Dv

(6)

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

Vhi?VS

(7)

圖4 協助轉發車輛示例Fig. 4 Example of cooperative relay vehicle

3.4 多RSU協作機制

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

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

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

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

L(Vti,Vni)

(8)

(9)

(10)

(11)

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

dj∈sqni

(12)

4)Vni鄰居節點在當前周期內不存在于V2V策略中的接收者，式(13)中Nni表示車輛Vni的鄰居節點列表，該式確保了Vni作為發送車輛不會影響其鄰居節點的接收轉狀態。

(13)

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

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

4 性能仿真與分析

4.1 仿真場景及參數設置

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

表1 仿真參數Tab. 1 Simulation parameters

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

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

4.2 仿真結果分析

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

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

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

(14)

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

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

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

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

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

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

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

圖10所示為不同場景下I2V廣播產能的曲線，可以看出，隨著車輛密度的增大，三種算法的I2V服務產能都呈現逐漸上升的趨勢。因為MRF每個周期都選擇請求數目最多的請求進行服務，所以其基站服務能力最強；而CDD和SDDS在選擇I2V和V2V時對兩種策略進行了權衡處理，更傾向尋求整體最優方案，所以會在I2V服務上有所欠缺。CDD該性能高于SDDS的原因在于SDDS增加了協助轉發車輛，增強了車輛之間的互相服務能力，使得車輛被車輛服務的概率大于基站對車輛的服務概率，從而導致了I2V的減少。

5 結語

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

圖10 不同場景下I2V廣播產能比較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] 謝永,吳黎兵,何炎祥,等.無間隙的車聯網協助下載方法[J].通信學報,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無線通信模式的原理及應用[J].數字通信世界,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。

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

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

1001- 9081(2017)08- 2139- 06

10.11772/j.issn.1001- 9081.2017.08.2139