軟件定義異構車聯網移動智能服務定制算法設計

余 庚,朱劍寶,謝道彪

(福建船政交通職業學院,福建 福州 350007)

0 引言

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

1 方案原理

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

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

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

2 方案模型

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

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

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

3 算法設計

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

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

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

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

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

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

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

MISC算法經由過往移動軌跡樣本精確訓練和未來行車路徑精確評估兩個步驟的設計,為軟件定義異構車聯網提前定制安裝移動服務流表項提供了可靠的節點選擇依據。使軟件定義異構車聯網提供平滑、無縫的快速移動智能定制服務成為可能。

4 方案測試

為驗證所構思的MISC算法模型的合理性,測試環節設計了兩組測試工作。第一組測試工作旨在驗證MISC算法模型相對于TMOE算法模型的優勢。第二組測試工作旨在驗證MISC算法模型部署在軟件定義異構車聯網中的定制成效。

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

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

圖1 算法時間成本

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

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

圖3 算法評估精度

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

圖4 交換機通信時延

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

圖5 交換機通信時延

5 結語

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