車聯網中基于隨機網絡演算的路由算法

朱國暉，楊 瑛

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

目前，移動通信正在完成從第四代移動通信技術(the Fourth Generation of Mobile Communication Technology,4G)到第五代移動通信技術(5th Generation Mobile Communication Technology，5G)的過渡，逐漸具備移動通信功能的汽車也在不斷向著智能駕駛方向發展，正處在過渡過程中的網聯階段[1]。這個階段的核心特征是出現了基于通信的車到車(Vehicle to Vehicle，V2V)和車到基礎設施(Vehicle to Infrastructure，V2I)、車到人(Vehicle to Pedestrian，V2P)的通信技術，將車與車、車與周圍的萬物進行連接。5G將為車到其他(Vehicle to X，V2X)提供更高的通信能力和安全性。在5G環境下，無論是基站還是移動終端，其數量都會較4G網絡環境有一個較大的增長，特別是5G帶來的微基站，其高密度的部署能確保網絡的高度覆蓋性。

在車聯網場景中，車輛作為網絡中的移動節點，其運動特性帶來的網絡高度動態拓撲性，會在一定程度上引起網絡連接的不穩定性，而5G微基站的高密度部署可以很好地解決此問題，尤其是在城市場景中，基本可以保證每一個移動節點都在其覆蓋范圍內。但隨著節點數量的增多，隨之而來的是路由選擇的問題，每一個攜帶數據需要進行轉發的節點，都會有更多備選的中繼節點。因此，適應于車聯網環境的路由算法成為一個研究熱點。

不同的路由算法會根據網絡中節點與鏈路之間不同的具體情況，選擇不同的傳輸路徑完成數據包的傳輸工作。國內外已有許多研究者對不同場景和傳輸需求進行了研究[2]。文獻[3]在車輛自組織網絡場景中提出了基于路口的V2V通信方式的路由表學習與維護的算法。該算法可以提供更穩定的路由，使傳輸成本更低，并且避免了不必要的數據丟失情況。文獻[4]提出的MADSDV算法以多代理方法和PSO優化算法相結合，提高了鏈路的穩定性，可以有效地降低丟包量并增加了吞吐量。文獻[5]提出了以街道為中心的機會路由算法，通過建立鏈路模型預測鏈路的可用概率。該概率通過車輛活動的穩定性與車輛的狀態，使用不同的鏈路組合傳輸具有較少網絡資源和較高吞吐量的分組。文獻[6]提出了基于模糊邏輯系統的簇首選擇算法，以運動中的車輛節點作為候選中繼，減少了分簇的次數，提高了簇結構的穩定性。但是，以車輛節點作為中繼的路由算法會因為車輛節點的移動性而帶來網絡的不穩定性。

傳統的路由算法并未過多地考慮當網絡中數據流具有突發性特點時的網絡整體的服務質量(Quality of Service，QoS)。為了能夠提供更優的QoS的中繼節點，考慮使用網絡演算分析節點與網絡性能。網絡演算[6]的發展分為確定性網絡演算(Deterministic Network Calculus,DNC)和隨機網絡演算(Stochastic Network Calculus,SNC)兩個分支。DNC提供的是確定性的QoS，數據從源節點(Source Node,SN)傳輸到目的節點(Destination Node,DN)時滿足所有預定的性能指標。確定性的QoS是基于最壞情況下的場景，預留了充足的資源，可以保證最好的服務水平，但缺點是導致了網絡資源的浪費。而SNC提供的隨機QoS可以看做是用戶所得到的服務是以一定的概率低于期望值的，允許一些數據包不滿足預定的性能指標。確定性的QoS可以看做是隨機QoS中違背期望值的概率為零的特殊情況，隨機QoS相較于確定QoS可以更好地提高網絡資源的利用率。因此，SNC已經被廣泛應用于不同的網絡領域[7-13]。

為了使選擇出的中繼節點具有更低的網絡時延與積壓，擬提出一種基于SNC的路由選擇算法。該算法對同一時間到達同一服務節點的數據流進行區分，分別建立服務節點對目標數據流與競爭數據流的隨機服務曲線。使用SNC分析網絡中節點的服務質量，并以此為依據找到性能最優的中繼節點，以期降低網絡時延與積壓。

1 算法分析

將網絡中可以為車輛節點提供服務的固定網元統稱為路邊單元( Roadside Unit,RSU )，攜帶數據的源節點SN將數據發送給距離自己最近的RSU，再由RSU選擇中繼，直至包含DN的RSU接收到數據。在RSU沿路鋪設達到全覆蓋的場景下，每個RSU都具備充分的預信息，SN將選擇RSU作為中繼節點進行數據的傳輸，這樣可以避免移動中的車輛作為中繼所帶來的不穩定性以及在一定程度降低因多跳傳輸引起的時延，具體車聯網場景如圖1所示。

圖1 車聯網場景

SNC的核心思想是將網絡中的數據到達流和網絡提供的服務分別用隨機到達曲線(Stochastic Arrival Curve,SAC)和隨機服務曲線(Stochastic Service Curve,SSC)進行建模，從而分析網絡的時延與積壓。

1.1 數據隨機到達模型分析

用非負廣義遞增累積函數A(t)描述數據流到達某一節點的到達過程，A(t)具有隨機性與突發性。A(t1,t2)表示在時間段[t1,t2)內所積累的到達數據量，并且定義A(0)=0，A(t1,t1)=0，A(t1,t2)=A(t2)-A(t1)，0≤t1≤t2。用廣義遞增函數曲線α(n)表示數據流A(t)的隨機到達曲線，α(n)描述了對到達網絡節點的數據流的約束行為，當n=t2-t1時，α(t2-t1)為A(t1,t2)的上包絡線。用A*(t)表示數據從節點的離開過程，A(t)和A*(t)均為統計獨立的平穩隨機過程，可以定義網絡的時延與積壓，如圖2所示。

圖2 網絡的時延與積壓

對于所有0≤t1≤t2，SAC滿足

A(t1,t2)-α(t2-t1)≤0
A?β(t)-A*(t)≤0

式中，?為最小加卷積運算。

定義非負廣義增函數f(x)和g(x)的最小加卷積?運算為

在確定性網絡中，確定的QoS保證了網絡是基于最壞情況下的場景預留足夠量的資源，累積到達數據量A(t1,t2)不會超過到達曲線α(t2-t1)。但在SNC中，允許數據存在突發性，用違約變量x描述，允許A(t1,t2)-α(t2-t1)>x的情況發生，并且定義函數f(x)為α(n)的違約概率函數。

上述突發情況發生的概率受到違約概率函數f(x)的限制，對于?0≤t1≤t2，x>0，若有概率

P{sup0≤t1≤t2{A(t1,t2)-α(t2-t1)}>x}≤f(x)

成立，則稱該過程具有v.b.c(virtual-backlog-centric) SAC[14-15]，記為A(t)～sac。

假設車輛節點的數據到達過程符合泊松過程，則隨機到達過程A(t)由[σa(θ),ρa(θ)]上界限制表示。其中：σa(θ)表示突發的增量；ρa(θ)表示數據流的平均速率上界。若?θ>0,?t1,t2≥0，則有

成立。其中：E表示期望；e為自然底數，即

E[eθA(t1,t2)]≤eθ[ρa(θ)(t2-t1)+σa(θ)]

設車輛節點到達過程服從參數為λ的泊松過程，N(t)表示t時刻到達的節點數量，則在時間段(t1,t2]內有n個節點到達的概率為

則服從泊松過程的數據流到達過程可以表示為

可得到eλ(t2-t1)(eθ-1)≤eθ[ρa(θ)(t2-t1)+σa(θ)]，即

λ(t2-t1)(eθ-1)≤θ[ρa(θ)(t2-t1)+σa(θ)]

可得到ρa(θ)=λ(eθ-1)/θ，σa(θ)=0。

由切爾諾夫不等式，可得

f(x)=m1e-θx

到達曲線為

式中，α(n)是關于時間間隔n的線性函數。

1.2 中繼RSU隨機服務模型分析

與SAC的定義類似，SSC用來表示服務節點所能提供的服務性能統計特性。網絡節點所提供的隨機服務曲線用廣義增函數β(t)表示，當且僅當對于任意的t≥0，均滿足A*(t)≥A?β(t)。假設違約概率函數為g(x)，在時間段(t1,t2]內，?x≥0，系統為到達的數據提供的服務過程S(t1,t2)滿足

P{β(t2-t1)-S(t1,t2)>x}≤g(x)

成立，服務系統S可為到達業務提供SSC,表示為S(t)～ssc。其中，β(t2-t1)為服務節點S(t1,t2)的下包絡。系統在某時間段內累積的數據服務量S(t1,t2)比隨機服務曲線β(t2-t1)小的概率受到g(x)的限制，服務曲線與服務過程如圖3所示。

圖3 服務曲線與服務過程

隨機服務過程S(t)由[bs(θ),rs(θ)]下界限制表示，bs(θ)表示增量，rs(θ)表示服務平均速率下界，其表達式為

等價于

E[e-θS(t1,t2)]≤e-rs(θ)[(t2-t1)-bs(θ)]

由切爾諾夫不等式，可得

P{β(t2-t1)-S(t1,t2)>x}≤
e-θxE[eθ(β(t2-t1)-S(t1,t2))]≤
e-θxe-θ[rs(θ)[(t2-t1)-bs(θ)]-β(t2-t1)]

將e-θ[rs(θ)[(t2-t1)-bs(θ)]-β(t2-t1)]記為m2，則違約概率函數g(x)=m2e-θx。

在實際的網絡環境中，服務節點對到達的數據所提供的服務也會帶有一定的隨機性。在絕大多數場景下的服務過程中，一個RSU會同時服務于多個車輛節點。因此，對于上述分析的數據流到達過程A(t)而言，存在與其競爭RSU服務的數據流。將與A(t)同時到達同一RSU的其他數據到達過程看作是合并后的同一數據流，并將其稱為A(t)的競爭數據流到達過程，用C(t)表示，如圖4所示。

圖4 數據到達流與競爭流

競爭數據流到達過程同樣具有隨機到達曲線，若A(t)記為A(t)～sac，則競爭數據流的隨機到達曲線C(t)可以記為C(t)～sac。與A(t)相類似，可以得到競爭數據流的違約概率函數和到達曲線

等價為

E[eθC(t1,t2)]≤eθ[ρc(θ)(t2-t1)+σc(θ)]

記競爭到達過程C(t)服從參數為λc的泊松分布，則可以得到

由此可得

式中：ρc(θ)表示競爭數據流的平均速率上界；σc(θ)表示競爭數據流突發的增量。

設RSU對到達數據的服務速率為vc，則RSU的隨機嚴格服務曲線可以記為β(n)=vcn。由剩余服務特性可知，假設到達系統的數據流由兩條聚合流A(t)和C(t)組成，如果系統對到達的總的聚合流提供隨機服務曲線滿足S～，并且數據流C(t)滿足隨機到達曲線C～，則數據流A(t)所能獲得的隨機服務曲線記為

Sa～

其中,

ga(x)=g?fc(x)
βa=β(n)-αc(n)

得到節點對到達數據流的服務下包絡線和違約概率函數，表達式分別為

1.3 系統時延與積壓分析

攜帶數據的車輛節點在與RSU進行信息傳輸的過程中，由于競爭數據流C(t)的存在，RSU對目標數據流A(t)的處理造成一定的延時與積壓，導致信息傳輸無法達到理想狀態。

找到滿足隨機時延P{D(t)>x}≤εd(x)和隨機積壓P{B(t)>x}≤εb(x)的邊界函數εd(x)與εb(x)，即找到各自的違約概率函數后，使用互補累積分布函數分析邊界函數，則時延D(t)和積壓B(t)[16]有

根據以上分析，網絡的時延與積壓的表達式分別為[17]

通過以上計算過程得到節點的時延與積壓的函數表達式，選擇最優中繼節點算法的具體步驟如下。

步驟1初始化相關信息。

步驟2發送hello數據包，并標記候選中繼RSU。

步驟3建立A(t)～sac，S(t)～ssc及其違約概率函數。

步驟4選擇性能最優的RSU。

步驟5判斷該RSU是否為距離SN最近的RSU，如果不是，返回步驟1，如果是，則結束。

通過以上步驟選擇出的RSU即為最優中繼節點。

2 模型仿真與性能分析

2.1 仿真環境設置

為了驗證所提算法的性能，使用Matlab仿真軟件對提出的算法進行驗證分析，仿真場景設置為一個SN，一個DN，多中繼的場景，在保持鏈路連通可靠性的基礎上完成仿真。

2.2 性能分析

通過將所提算法與文獻[13]算法進行對比分析，得到違約概率與時延的關系，如圖5所示。設Rn為源節點的數量，那么數據到達率與時延的關系如圖6所示。

圖5 違約概率與時延的關系

圖6 數據到達率與時延的關系

由圖5和圖6可以看出，不同的違約概率對傳輸時延的影響關系，仿真中設置數據的到達率為0.5 MB·s-1。隨著違約概率的增加，中繼RSU對于有著突發性特點的數據的處理能力也在增強，傳輸時延也隨之減小。在違約概率為0，即在確定性QoS的情況下，時延會達到最大。圖6比較了在候選中繼數量不同的情況下，SN所攜帶的數據的到達率與時延的關系。隨著數據到達率的增加，系統的傳輸時延會增大。在中繼數量一定的情況下，較高的數據到達率會引起RSU負載的增加。同時，會帶來時延。考慮隨著RSU部署密度的增加，會使得需要被服務的數據分散，可以減輕數據在排隊系統中因等候而引起的傳輸時延。因此，候選中繼的增加，會在一定程度上降低時延。

違約概率與積壓的關系，以及數據到達率與積壓的關系分別如圖7和圖8所示。

圖7 違約概率與積壓的關系

圖8 數據到達率與積壓的關系

由圖7和圖8所示，隨著違約概率的增加，中繼RSU對于具有突發特性的數據的處理能力會使得系統的積壓減少。在允許一些數據不滿足預定的性能指標的情況下，網絡資源可以得到更充分的利用。同時，圖8給出了不同數據到達率與積壓上界的關系，可以看出，數據到達率的增大會增加系統的負載，中繼RSU的積壓也隨之增大，候選中繼數量的增加會分散需要被服務的數據，使得積壓減少，并且相比于移動中的車輛節點，選擇RSU作為中繼，計算能力與存儲空間會優于車輛節點，且RSU中留有充足的預信息，能夠更加可靠地進行服務。因此，所提算法與文獻[13]算法相比，能夠得到更優的積壓性能。

3 結語

在車聯網中，由于車輛節點的運動特性帶來的網絡高度動態拓撲性和數據突發性等特點，如果選擇移動中的車輛做為數據傳輸的中繼節點，會導致鏈路連接不穩定，增大傳輸時延。在5G城市環境中，RSU達到全覆蓋的場景下，選擇RSU作為信息傳輸的中繼能夠在一定程度上減少鏈路連接的不穩定性以及降低由多跳傳輸所帶來的時延。同時，采用SNC作為網絡性能的分析工具進行路由的選擇，更加符合車聯網的特點。利用SNC建立SN的SAC與中繼RSU的SSC，并分析競爭數據流存在時的SAC與SSC對時延與積壓的關系。仿真結果表明，所提算法在選擇中繼RSU時，可以有效降低系統的傳輸時延與積壓。