余 庚,朱劍寶,謝道彪

(福建船政交通職業(yè)學(xué)院,福建 福州 350007)

0 引言

為順應(yīng)智能網(wǎng)聯(lián)汽車發(fā)展,促進車聯(lián)網(wǎng)QoS[1]服務(wù)成效走向縱深,SDN技術(shù)被廣泛用于擴展異構(gòu)車聯(lián)網(wǎng)的各項應(yīng)用服務(wù)。然而由于異構(gòu)車聯(lián)網(wǎng)所服務(wù)的移動車端存在接入規(guī)模較大且移動頻繁等諸多復(fù)雜特征,導(dǎo)致SDN技術(shù)為異構(gòu)車聯(lián)網(wǎng)提供的在線計算服務(wù)時效存在不確定性,進而弱化了QoS服務(wù)成效。造成該現(xiàn)象的原因在于當移動車端發(fā)起數(shù)據(jù)流計算請求時,數(shù)據(jù)轉(zhuǎn)發(fā)單元和控制器之間需交互較長時間以分割數(shù)據(jù)包長度,制定數(shù)據(jù)包適配規(guī)則,形成流表項并下發(fā)到每一個數(shù)據(jù)轉(zhuǎn)發(fā)單元。尤其在上下班及節(jié)假日等繁忙時段,移動車端的接入規(guī)模呈現(xiàn)高度隨機突發(fā)特征,接入狀態(tài)呈現(xiàn)高頻移動特性,導(dǎo)致每一次產(chǎn)生的數(shù)據(jù)流第一個數(shù)據(jù)子集需耗費較多的時延代價用于建立流表項。移動車端在高速移動期間總是頻繁向附近車聯(lián)網(wǎng)接入點提出獲取相同服務(wù)的請求,這勢必要求數(shù)據(jù)層面的數(shù)據(jù)轉(zhuǎn)發(fā)單元之間不僅能夠快速廣播流表項,同時要求數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)備和應(yīng)用服務(wù)器之間能夠進行數(shù)據(jù)無縫傳輸。因此有必要根據(jù)異構(gòu)車聯(lián)網(wǎng)的接入特征重構(gòu)SDN[2]數(shù)據(jù)路由機制,為移動車端設(shè)計一個兼具平滑和實時的在線移動計算方案?；诖?本文構(gòu)思將SDN架構(gòu)融入異構(gòu)車聯(lián)網(wǎng),用于實現(xiàn)為移動車端提供移動智能服務(wù)定制(Mobile Intelligent Service Customization,MISC)的技術(shù)。

1 方案原理

在移動用戶設(shè)備和移動車端所組成的異構(gòu)車聯(lián)網(wǎng)中,由于節(jié)點移動規(guī)律和移動范圍須符合實際交通系統(tǒng)的部署,因此移動節(jié)點的運動需遵循道路網(wǎng)絡(luò)規(guī)則。正是這樣的移動局限性使得可以通過統(tǒng)計分析節(jié)點過往移動路徑和移動模式來推算出移動節(jié)點未來的運動軌跡。目前已有學(xué)者陸續(xù)針對移動軌跡預(yù)測開展相關(guān)研究。張海霞等[3]通過為車載終端構(gòu)建移動行為評估模型來實現(xiàn)導(dǎo)航路線測算。這為異構(gòu)車聯(lián)網(wǎng)移動節(jié)點的行車路徑評估提供了良好的依據(jù)。同時依托強大的云計算能力不僅可以高速響應(yīng)運動軌跡的移動計算,也能進一步提高預(yù)測數(shù)據(jù)的可信度。因此,通過重構(gòu)SDN數(shù)據(jù)路由機制為異構(gòu)車聯(lián)網(wǎng)節(jié)點定制移動智能服務(wù)的方案具有可行性。

該方案首先根據(jù)移動行為推算出節(jié)點即將產(chǎn)生的概率最高的行車軌跡。再采用主動部署的方式由控制層發(fā)起監(jiān)測,記錄每個數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點的通信范圍。然后在可能性最大的評估軌跡所經(jīng)過的節(jié)點中提前添加流表項來實現(xiàn)移動智能服務(wù)定制的目標。采用評估策略添加定制流表項不僅最大程度地縮小所涉及節(jié)點的規(guī)模,同時可有效約束定制流表項的規(guī)模,避免不必要的資源消耗。當異構(gòu)車聯(lián)網(wǎng)邊緣移動終端靠近此節(jié)點申請接入時,無須頻繁地向控制層提交數(shù)據(jù)適配的請求,控制器也不再制定流表下發(fā)給節(jié)點。當有新的移動數(shù)據(jù)流發(fā)起時,該數(shù)據(jù)流的第一個數(shù)據(jù)子集被轉(zhuǎn)發(fā)到交換機。由于交換機內(nèi)存已加載了該數(shù)據(jù)子集的流表,只需直接傳輸即可。通過缺省數(shù)據(jù)層和控制器的雙工交互,加速了預(yù)加載的移動流表項讀取速度,提高了定制移動智能服務(wù)的QoS成效。

然而預(yù)測存在一定偏差,偏差將導(dǎo)致節(jié)點所加載的定制流表項失效。隨著時間推移,流表項將占據(jù)更多節(jié)點內(nèi)存,消耗更多網(wǎng)絡(luò)計算資源,進而弱化異構(gòu)車聯(lián)網(wǎng)全網(wǎng)節(jié)點性能。且采用預(yù)測機制在部署成本上表現(xiàn)欠佳,缺乏實用性。因此有必要根據(jù)道路交通網(wǎng)絡(luò)實際情況為所定制的流表項引入超時機制[4]。倘若在特定的時間間隔內(nèi)節(jié)點未啟用定制流表項,則將其從節(jié)點內(nèi)存中移除。因此評估移動車端移動軌跡的精度決定了移動智能服務(wù)的定制成效。

2 方案模型

為使異構(gòu)車聯(lián)網(wǎng)能夠為移動車端提供平滑的移動接入服務(wù),通過挖掘分析既往移動軌跡信息來計算移動車端未來行車路線已成為研究車聯(lián)網(wǎng)的關(guān)鍵技術(shù)之一。移動車端行駛過的每一個軌跡均代表了該移動車端過往每個時刻所處的離散位置。根據(jù)時序先后將這些位置點形成一個序列,再結(jié)合關(guān)聯(lián)法則[5]運用數(shù)據(jù)挖掘算法對車端的移動方位開展測算。然而移動車端行駛軌跡的持續(xù)增加將增加算法復(fù)雜度。但該算法所涉及的馬爾科夫方位評估模型被證實和實際異構(gòu)車聯(lián)網(wǎng)環(huán)境中終端行車規(guī)律較吻合,評估精度較高。即便如此,該模型依然存在一些不足。諸如,狀態(tài)空間規(guī)模與階數(shù)成正比、狀態(tài)參數(shù)選取稍有偏差將造成預(yù)測軌跡嚴重偏離實際軌跡。隨著異構(gòu)車聯(lián)網(wǎng)接入的移動車端規(guī)模不斷增加,潛在風(fēng)險也逐漸加大。因此本文考慮通過引入一個階數(shù)自適應(yīng)調(diào)整的馬爾科夫方位評估模型(Markov Bearing Evaluation Model with Adaptive Order Adjustment,AOA)來解決該風(fēng)險。模型的建立過程如下:

假設(shè)X是有限個狀態(tài)構(gòu)成的馬爾科夫鏈狀態(tài)空間集。其中隨機狀態(tài)序列長度有限,記作{Xk}。k為從0開始的自然數(shù),狀態(tài)nk和狀態(tài)m均為空間集合X的子集。如果存在一個階數(shù)為z的自適應(yīng)馬爾科夫方位評估模型,則狀態(tài)空間集要滿足如下規(guī)則:

P(Xk+1=m|Xk-z+1=nk-z+1,…,Xk-1=nk-1,Xk=nk)=P(Xk+1=m|X0=n0,X1=n1,…,Xk-1=nk-1,Xk=nk).

此時,{Xk}即為自適應(yīng)馬爾科夫鏈。通過統(tǒng)計第z-1個隨機狀態(tài)序列的概率和目前第z個隨機狀態(tài)序列的概率來共同確定第z+1個隨機狀態(tài)序列的概率。由于變量z的長度可調(diào),故稱為自適應(yīng)模型。若變量z取值1,則自適應(yīng)馬爾科夫方位評估模型即為初始標準化的馬爾科夫方位評估模型。該自適應(yīng)馬爾科夫方位評估模型的結(jié)構(gòu)描述為:將隨機狀態(tài)序列集合轉(zhuǎn)化為一棵非空概率的拓撲樹,拓撲樹的高度為H。將隨機狀態(tài)序列集合中的字符標識作為該拓撲樹的邊權(quán)重。任意一個樹節(jié)點延伸出的邊與該節(jié)點的其他邊具有不同的字符標識。除了根部主節(jié)點之外的其他節(jié)點均有一個字符序列串。該字符序列串由從自身節(jié)點開始逐漸遍歷到主節(jié)點過程中所涉及的所有邊的字符標識權(quán)重組合而成。拓撲樹的節(jié)點同時分配了概率向量用于表明自身節(jié)點字符標識串后續(xù)字符的慣性值。相對于傳統(tǒng)馬爾科夫方位評估模型(Traditional Markov Orientation Evaluation Model,TMOE),自適應(yīng)馬爾科夫方位評估模型優(yōu)勢在于算法可避免不斷累積的歷史行車軌跡規(guī)模對算法復(fù)雜度的影響[6]。同時由于移動車端受到實際道路駕駛環(huán)境的限制以及駕駛員行車習(xí)慣的影響,移動軌跡具有一定的約束性和規(guī)律性。因此部署自適應(yīng)馬爾科夫方位評估模型應(yīng)首先將拓撲樹節(jié)點存儲的過往移動軌跡數(shù)據(jù)作為訓(xùn)練對象,通過定義信任閾值建立信任機制篩選出可靠性較高的節(jié)點進行拓撲樹的優(yōu)化重構(gòu)。然后根據(jù)移動車端當前行程所組建的移動軌跡序列[7],去和優(yōu)化重構(gòu)后的拓撲樹節(jié)點開展適配。直到遍歷出從當前節(jié)點出發(fā)能夠途經(jīng)的概率最大的那個拓撲樹節(jié)點,即作為本次評估的未來移動軌跡。由于實際道路交通網(wǎng)絡(luò)環(huán)境中的交叉路口都部署了諸多路側(cè)單元與移動車端進行交互,增加了問題的復(fù)雜度。為簡化說明,本文將位于交叉路口的路側(cè)單元視為移動軌跡的評估點,以便簡化隨機狀態(tài)移動軌跡序列的表征,優(yōu)化算法過程。

3 算法設(shè)計

設(shè)計算法前先規(guī)劃道路交通網(wǎng)絡(luò)和移動軌跡狀態(tài)序列。具體規(guī)劃步驟如下:假設(shè)道路的集合為D={d0,d1,…,dn},道路交叉路口的路口單元集合為L={l0,l1,…,ln}。引入一個路網(wǎng)有向圖G=(D,L)。本文將位于交叉路口的路側(cè)單元視為移動軌跡的評估點[8],因此移動終端途經(jīng)的路側(cè)單元即為移動路徑序列,記作p={l1,l2,…,lm},其中n>m。每個移動路徑的跨度為K。移動終端在整個圖G的移動路徑序列集合為P={p1,p2,…,pn}。為提高移動終端在下一時刻移動路徑的評估精度,考慮將早期交叉路口的信息缺省,將剩余的移動軌跡序列定義為序列子集,記作Sm(p)={lm,lm+1,…,ln}。完整的算法實施過程應(yīng)先對過往移動軌跡樣本進行訓(xùn)練再對未來的移動趨勢開展評估。

假設(shè)移動路徑序列集合中長度最大的軌跡序列為pK,max,該序列長度記作kmax。從長度最小的軌跡序列開始遍歷路徑序列集合,直至遍歷完高度為H的拓撲樹。具體遍歷過程如下:

首先,構(gòu)建一個根主節(jié)點的拓撲樹。將交叉路口單元集內(nèi)所有路側(cè)單元激活的頻次視為該主節(jié)點的經(jīng)驗概率[9],即概率向量。假設(shè)有個特定的路口單元設(shè)備在路口單元集合采集的樣本集合中激活的頻次為fL,全部的路口單元設(shè)備在路口單元集合采集的樣本集合中激活的頻次為fA,則概率向量表征為C(lm)=fL/fA。由于傳統(tǒng)馬爾科夫方位評估模型在部署期間存在待用節(jié)點序列集合規(guī)模隨時間推移呈現(xiàn)驟增的現(xiàn)象,本文引入一個可信度閾值門限Pth1。如果某節(jié)點屬于可靠的待用節(jié)點,可考慮納入序列集合,就須滿足關(guān)系式Pth1

其次,循環(huán)開展迭代式計算,直至遍歷完整個拓撲樹完成可信節(jié)點的拓撲樹優(yōu)化重構(gòu)。在待用節(jié)點集內(nèi)選擇一個當前待選節(jié)點,表征為pK。再推算出該待選節(jié)點的后面節(jié)點的概率向量。倘若節(jié)點li在集合P緊隨pK被激活的概率C(li|pL)超過了可信度閾值門限Pth2,則節(jié)點li屬于可信節(jié)點,可作為拓撲樹的節(jié)點。字符串為pKli的節(jié)點作為節(jié)點li的備選后續(xù)節(jié)點。假設(shè)節(jié)點li緊隨pK被激活的頻次為f0,過往樣本集合緊隨pK出現(xiàn)的交叉路口的規(guī)模為fP,則概率向量表征為C(li|pK)=f0/fP。通過定義Pth2閾值門限機制高效地簡化了拓撲樹冗繁的結(jié)構(gòu)。

考慮實際道路環(huán)境中的駕駛情況,移動終端的軌跡序列的后續(xù)備選節(jié)點和pK中末尾交叉路口單元總是保持相鄰,故僅遍歷S(lK)-1次即可算得移動軌跡序列的概率向量。其中,lK指pK末端的交叉路口;S(lK)指和路側(cè)單元lK關(guān)聯(lián)的路口單元集合。這樣的設(shè)計可顯著降低算法時間復(fù)雜度和空間復(fù)雜度。但在傳統(tǒng)評估模型中需完成路側(cè)單元集合內(nèi)每一個路口單元設(shè)備的遍歷。相比之下,傳統(tǒng)評估模型的算法復(fù)雜度較高。

假設(shè)現(xiàn)有一個移動終端接入軟件定義異構(gòu)車聯(lián)網(wǎng),所產(chǎn)生的移動軌跡序列為pi={l1,l2,…,li},序列跨度為Ki。當H>Ki時,交叉路口單元l′滿足條件l′∈{S(l1)-l2}。若概率向量符合Pth2Ki情形下的步驟,將該序列納入可信節(jié)點行列進行循環(huán)迭代。倘若pi內(nèi)的交叉路口單元不在當前集合內(nèi),需新建一個拓撲樹。

實施過往移動軌跡樣本訓(xùn)練后形成一個可信度較高的優(yōu)化拓撲樹[10]。通過該優(yōu)化拓撲樹便可推算出移動終端后續(xù)的行車路徑。推算過程為:借助路側(cè)單元采集存儲的數(shù)據(jù)來提取移動終端當前行車狀態(tài)下的移動軌跡序列pl。從過往移動軌跡拓撲樹的根主節(jié)點開始,讓pl按照逆序的方式去遍歷拓撲樹直至遍歷到可適配的拓撲樹節(jié)點。相對而言,跨度較短的時間內(nèi)所采集的移動終端行車軌跡對于測算未來移動軌跡更有參考價值。因此有必要更新pl中的序列,將時間跨度較大的過往交叉路口單元的節(jié)點剔除以便實現(xiàn)當前行車狀態(tài)和拓撲樹的精確適配[11]。所以如果pl按照逆序的方式遍歷完整個拓撲樹依然未能找到可適配的節(jié)點,需按照先后順序選取pl中跨度第二長、第三長的子序列開展拓撲樹節(jié)點的遍歷配對。再從所適配的節(jié)點中選出概率向量最高的那個節(jié)點作為移動車端未來大概率途經(jīng)的目標方位點。

MISC算法經(jīng)由過往移動軌跡樣本精確訓(xùn)練和未來行車路徑精確評估兩個步驟的設(shè)計,為軟件定義異構(gòu)車聯(lián)網(wǎng)提前定制安裝移動服務(wù)流表項提供了可靠的節(jié)點選擇依據(jù)。使軟件定義異構(gòu)車聯(lián)網(wǎng)提供平滑、無縫的快速移動智能定制服務(wù)成為可能。

4 方案測試

為驗證所構(gòu)思的MISC算法模型的合理性,測試環(huán)節(jié)設(shè)計了兩組測試工作。第一組測試工作旨在驗證MISC算法模型相對于TMOE算法模型的優(yōu)勢。第二組測試工作旨在驗證MISC算法模型部署在軟件定義異構(gòu)車聯(lián)網(wǎng)中的定制成效。

針對第一組測試工作,相關(guān)參數(shù)設(shè)置為:Pth1=3×10-4,Pth2=3×10-3,K<20。假設(shè)通過模擬器安排的移動軌跡序列規(guī)模為A=8 000。將此規(guī)模序列隨機地設(shè)置成8個軌跡序列小組,任意選擇2個小組開展行車狀態(tài)評估,任意選擇6個小組開展樣本訓(xùn)練。每個小組安排1 000條軌跡序列。算法所在路段的交叉路口單元設(shè)為80個。循環(huán)執(zhí)行上述分組操作10次后再收集測試數(shù)據(jù)開展分析。該項測試工作主要考察兩個算法方案的復(fù)雜度以及行車軌跡測算精度。

圖1描述了兩種算法方案在開展移動軌跡預(yù)估時,過往軌跡長度變化對算法運行時間的影響程度。從曲線走勢可見,隨著過往移動軌跡序列長度持續(xù)增長,兩種算法開展未來移動軌跡測算的時間成本持續(xù)增加,但本文構(gòu)思的MISC算法運行時間成本相對低一些。究其原因,MISC算法思想是將過往移動軌跡序列和拓撲樹節(jié)點開展適配,算法復(fù)雜度僅為O(A·K)。而TMOE算法則利用傳統(tǒng)矩陣轉(zhuǎn)移的方式來開展軌跡測算,導(dǎo)致算法復(fù)雜度高達O(n3·z)。隨著時間推移,引入信任閾值門限機制的MISC算法逐漸卸載了參考價值不大的交叉路口單元信息,算法性能得到持續(xù)優(yōu)化,這樣的優(yōu)化機制是TMOE算法所不具備的。因此隨著軌跡序列規(guī)模和長度持續(xù)增加,MISC算法下的時間成本優(yōu)勢表現(xiàn)得越加明顯。

圖1 算法時間成本

圖2描述了兩種算法方案在開展移動軌跡預(yù)估時,處理不同長度的過往移動軌跡序列所消耗的內(nèi)存硬件資源情況。從曲線走勢可見,兩種算法在處理長度較小的過往移動軌跡序列時消耗的內(nèi)存空間大小相差無幾。隨著長度持續(xù)增加,本文提出的MISC算法在處理數(shù)據(jù)時消耗的空間增量逐漸減小。出現(xiàn)這樣的曲線走勢是由于在評估未來移動軌跡時MISC算法方案通過創(chuàng)建優(yōu)化拓撲樹進行節(jié)點和序列適配的方法,該方法的復(fù)雜度僅為O(A)。而TMOE算法方案采用傳統(tǒng)馬爾科夫模型矩陣轉(zhuǎn)移方法來開展預(yù)測,復(fù)雜度高達O(n2·z)。

圖3描述了兩種算法通過處理不同長度的移動軌跡序列評估的未來行車軌跡精度。不難看出,評估初期由于過往移動軌跡序列長度較短,兩種算法在低階狀態(tài)下評估未來行車軌跡的精度沒有太明顯的區(qū)分。當增加過往移動軌跡序列長度,兩種算法精度開始明顯提升。隨著過往移動軌跡序列長度進一步增加,MISC算法開始持續(xù)發(fā)揮出潛在計算優(yōu)勢,精度曲線繼續(xù)走升,而TMOE算法的精度曲線則開始趨于平穩(wěn)。這是由于MISC算法方案采用了自適應(yīng)評估模型,可根據(jù)過往移動軌跡序列長度動態(tài)調(diào)整序列評估參數(shù),并結(jié)合閾值門限機制進一步提升了MISC算法評估未來移動軌跡的精度。定制算法的部署成效主要取決于數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點和控制層之間交互時延,以及終端移動的平滑性。因此第二組測試工作以響應(yīng)時延為考察指標將MISC算法下的定制級安裝方式和典型安裝方式[12]開展對比。典型安裝方式是在所有車聯(lián)網(wǎng)數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點中提前安裝移動服務(wù)流表項。借助Mininet軟件模擬搭建軟件定義異構(gòu)車聯(lián)網(wǎng)環(huán)境,定義6個交換節(jié)點。通過變化接入異構(gòu)車聯(lián)網(wǎng)的移動車端行駛速度和移動車端規(guī)模來考察節(jié)點通信時延,進而驗證定制級安裝方式的智能性。

圖3 算法評估精度

圖4描述了兩種安裝方式在應(yīng)對不同移動車端規(guī)模時交換機的通信時延。從曲線走勢可見,接入軟件定義異構(gòu)車聯(lián)網(wǎng)的移動車端數(shù)量越多,交換機通信時延代價總體越高,尤其是典型安裝方式下的交換機通信時延代價更高。這是因為本文設(shè)計的定制級流表安裝方式將典型安裝方式中上行移動服務(wù)請求和下行計算服務(wù)響應(yīng)兩個流表降至一個流表。當移動車端行駛到異構(gòu)車聯(lián)網(wǎng)交換機節(jié)點附近并向其提請移動服務(wù)請求時,只要適配到該交換機內(nèi)存中的移動服務(wù)流表即可獲取下發(fā)的響應(yīng)數(shù)據(jù)。這不僅缺省了服務(wù)請求轉(zhuǎn)發(fā)到遠程云數(shù)據(jù)中心的過程,也免去了控制層制定流表項下發(fā)的步驟。同時,由于持續(xù)增加的流表數(shù)量過度消耗交換機內(nèi)存空間,導(dǎo)致交換機性能下降,進而引發(fā)通信遲緩的問題也得到有效解決。因此,定制級安裝方式更有利于提升節(jié)點的通信效率,控制通信時延代價。

圖4 交換機通信時延

圖5描述了兩種安裝方式在應(yīng)對不同移動車端行車速度時節(jié)點通信時延對比情況。由圖5可見,當行車速度增加,兩種安裝方式下的節(jié)點通信時延都在增加,但本文定制級安裝方式下的時延變化率較低。這是由于行車速度增加導(dǎo)致軟件定義異構(gòu)車聯(lián)網(wǎng)節(jié)點拓撲結(jié)構(gòu)發(fā)生更加快速的變化,加劇了網(wǎng)絡(luò)變化的復(fù)雜度。此時典型安裝方式因缺乏智能化移動流表適配的預(yù)安裝功能,其移動支持能力較弱,導(dǎo)致節(jié)點通信時延延長。定制級安裝方式則是在精確預(yù)測的下一個移動交換節(jié)點中提前定制安裝了移動流表,顯著地降低了通信時延,高效地增加了移動服務(wù)定制成效。這種成效將隨移動車端速度增加而表現(xiàn)得更加明顯。因此定制級安裝方式在高速公路環(huán)境中也具備有一定的適應(yīng)性。

圖5 交換機通信時延

5 結(jié)語

本文設(shè)計的移動智能服務(wù)定制算法依托軟件定義網(wǎng)絡(luò)架構(gòu)優(yōu)勢,通過分析移動車端過往行車軌跡特征開展未來行車路徑的評估。定制算法中關(guān)于未來移動軌跡的評估方案,不僅充分考慮了過往軌跡序列長度和數(shù)量等因素對異構(gòu)車聯(lián)網(wǎng)節(jié)點性能的影響,同時通過淘汰信任度較低的路口單元信息來確保子軌跡序列具有實時的參考價值,為軟件定義異構(gòu)車聯(lián)網(wǎng)節(jié)點提前安裝移動流表提供了科學(xué)的節(jié)點評估機制。經(jīng)測試表明,該移動服務(wù)定制算法部署在軟件定義異構(gòu)車聯(lián)網(wǎng)中具有良好的自適應(yīng)性。