基于車聯(lián)網(wǎng)的中心導航云性能分析模型

中圖分類號：TP309 文獻標志碼：A 文章編號：1671-5489（2025）04-1150-07

Performance Analysis Model of Central Navigation Cloud Based on Internet of Vehicles

LENG Song1，LI Zhiqiang2，GAO Jinliang1，LIU Yanheng ^1，2 （204 （1. School of Com puter Science， Zhuhai College of Science and Technology ， Zhuhai 51904l，Guangdong Province，China; 2. College of Computer Science and Technology， Jilin University， Changchun 1300l2， China）

Abstract： In order to improve efficiency of road traffic， by using the minimum traffic navigation cloud sacle given number of road nodes and vehicles，we proposed a performance analysis model based on target map and cloud center related parameters. Firstly，we analyzed the target map and the relevant parameters of the cloud platform that affected navigation performance. Secondly，we considered the number of road nodes and vehicles，as well as virtual machines of different scales and frequencies，and conducted three sets of experiments.Finally，we verified the efectiveness of the model by using real datasets. The experimental results show that the proposed performance analysis model can accurately calculate the minimum scale of navigation cloud that satisfies the constraint conditions.

Keywords： Internet of vehicle； navigation cloud; performance analysis； dynamic route； queuingtheory

近年來，隨著我國汽車保有量的快速攀升，使各城市道路交通日趨擁堵．中心導航云（centralnavigationcloud，CNC）是為減輕交通壓力，提升交通流暢度，云端部署的導航服務(wù)系統(tǒng)，其利用實時全面的交通數(shù)據(jù)為目標區(qū)域內(nèi)的車輛規(guī)劃最佳導航路徑．但面對錯綜復(fù)雜的路網(wǎng)和數(shù)量龐大的車輛，為確保能為眾多車輛同時提供即時有效的導航服務(wù)，需依賴于高性能計算（high performancecomputing，HPC）技術(shù)．目前，云計算平臺有龐大的存儲能力、計算資源和網(wǎng)絡(luò)設(shè)施[1-2]，實現(xiàn)了隨時隨地訪問、即付即用，是一種基于網(wǎng)絡(luò)的計算范式．本文提出一種專門為改善城市道路交通效率的社區(qū)云，構(gòu)建一個性能較強、規(guī)模適中的云導航中心.

為構(gòu)建復(fù)雜條件下的動態(tài)路徑優(yōu)化模型，文獻[3]利用模糊集理論進行了模擬仿真，以真實交通數(shù)據(jù)作為輸人，得到了實際交通時間和交通負載節(jié)點．文獻[4]提出了一種動態(tài)路徑引導（dynamicrouting guidance，DRG）框架，在考慮實時道路擁塞信息的情況下能找到從車輛實時位置到目的地的最優(yōu)路徑．文獻[5]使用地理信息系統(tǒng)（geographic information system，GIS）提供動態(tài)變化的交通流信息和歷史數(shù)據(jù)，通過減少查找優(yōu)化路線和備用路線的重新計算次數(shù)，以獲得更少的內(nèi)存消耗和資源浪費，從而減少了響應(yīng)時間．文獻［6]設(shè)計了一種利用谷歌應(yīng)用引擎（google app engine，GAE），稱為C2Geo（cloud computing for geoprocessing）的新技術(shù)[7]，實時處理地理空間問題．文獻[8]提出了基于車輛對基礎(chǔ)設(shè)施（V2I）和基礎(chǔ)設(shè)施對車輛（I2V）通信的多智能體 AIM（MA-AIM）系統(tǒng)，該系統(tǒng)能利用云輔助物聯(lián)網(wǎng)（cloud of things，CoT）和區(qū)塊鏈設(shè)施安全管理通過交叉路口的車輛.

已有的研究結(jié)果表明，中心導航云能借助實時道路交通信息實現(xiàn)同時為多目標提供最優(yōu)路徑規(guī)劃，同時，云計算在處理地理信息等計算密集型任務(wù)上展現(xiàn)了巨大的潛力．然而，云平臺基礎(chǔ)設(shè)施通常未考慮數(shù)據(jù)特點和應(yīng)用場景，基礎(chǔ)架構(gòu)通常是為通用計算設(shè)計的，因此，還需深入研究如何構(gòu)建一個適合地理空間專用的云計算平臺．基于此，本文建立一個基于排隊論的車聯(lián)網(wǎng)中心導航云的性能分析模型，通過分析路網(wǎng)節(jié)點數(shù)、車輛數(shù)以及虛擬機規(guī)模（虛擬機數(shù)量和CPU頻率）對模型性能的影響，進而通過該模型確定符合約束條件的導航云最小規(guī)模，對導航云未來的發(fā)展具有重要意義.

1 中心導航云模型

1.1地圖模型和導航過程模型

本文討論的云具有與車載導航設(shè)備進行即時通信的能力，不但可以實時采集交通信息，而且在向車載設(shè)備提供最優(yōu)導航路徑規(guī)劃服務(wù)的同時，還能將實時信息發(fā)送到車載導航設(shè)備，如交通事故、車流密度、天氣狀況等．如果將道路路口視為節(jié)點，道路視為邊，則可將目標地圖視為一個無向有限圖．如圖1所示，其中 R_i 表示第 i 個路口，可用Map（n，m，λ） 表示目標地圖， n 為目標地圖的路口數(shù)量， Σ_m 為目標地圖道路上的車輛數(shù)量， λ 為導航請求的并發(fā)速率．假設(shè)圖1中車輛 Car₁ 當前導航路徑為 {R₁-R₂-R₃} ，即由 R₁ 經(jīng) R₂ 最終到達 R₃ ：當車輛 Car₂ 和車輛 Car₃ 發(fā)生事故，阻塞了從 R₂ 到 R₃ 的道路．此時，中心導航云就會基于當前路況為 Car₁ 重新規(guī)劃最優(yōu)導航路徑，并將新生成的導航路徑 發(fā)送給 Car₁

1. 2 云中心模型和性能建模

本文用 Cloud（C，F(xiàn)，O） 表示中心導航云，其中： C 為虛擬機的數(shù)量； （ 是一個向量， f_i 表示序號為 i 的虛擬機的頻率最高值； O 為動態(tài)導航算法的復(fù)雜度.

為達成導航請求的最小平均響應(yīng)時間，本文假設(shè)以最短路徑法作為云中心的導航算法．在圖G（V，E） 中， V 為節(jié)點集合， E 為邊集合，則最短路徑可用多種算法計算，各算法復(fù)雜度不同．其中，F(xiàn)loyd-War shall算法適用于帶負權(quán)的有向圖，可計算圖中任何兩個節(jié)點之間的最短路徑，其復(fù)雜度為O（∣V∣³） ；Dijkstra算法則適用于非負權(quán)圖，可計算某個節(jié)點與其他全部節(jié)點之間的最短路徑，其復(fù)雜度為 O（∣V∣²+∣E∣） ．在保持普遍性的前提下，假設(shè)本文模型的算法復(fù)雜度為二次方級別，即為O（n²） ，其中 n 為節(jié)點數(shù).

假設(shè)中心導航云虛擬機使用的CPU是制約云中心性能的唯一因素，且在單位時間內(nèi)平均可響應(yīng)的請求數(shù)量為 μ^[9] ， μ 與CPU的最高頻率 f_i 呈正比例關(guān)系， μ=Kf_i（Klt;1） ．如果也考慮時間復(fù)雜度，則 μ 隨著時間復(fù)雜度的增加而減小，即 μ 與時間復(fù)雜度 O 呈反比例關(guān)系， μ=Kf_i/O （ Klt;1） 》

采用排隊論，即使用隊列 {M，M，C，∞，m} ，對虛擬機數(shù)量為 C 、能響應(yīng)車輛數(shù)為 Ψ_m 的導航云中心

進行建模．假設(shè)車輛導航請求的到達遵循Poisson過程，服務(wù)時間符合負指數(shù)分布，排隊空間不受限

制，將先進先出作為排隊規(guī)則，同時各虛擬機之間彼此互不影響．如果系統(tǒng)狀態(tài)以接收到的請求數(shù)量

標識，則將存在 （m+1） 個狀態(tài)，即 0，1，…，m ．如圖2所示，Markov鏈中的狀態(tài)標識了中心導航云當

前接收到的請求數(shù)量，顯然它符合不可約Markov鏈，其服務(wù)速率的平均值為 kμ ，當 k k?C C_μ

系統(tǒng)處于平衡狀態(tài)的條件是 ρlt;1 ，即

Cgt;λ/μ.

平衡方程為

當 k 取不同值時，可得 P_k 的表達式為

根據(jù)概率的性質(zhì) ，可得 P₀ 的表達式為

當 ks 與導航算法所需的時間相同.因此，當 k?C 時，導航系統(tǒng)處在統(tǒng)計平衡狀態(tài)．此時，等待隊列的長度可表示為

平均隊列長度為

L_s=L_q+λ_e/μ，

其中 λ_e 表示導航請求的實際到達速率，它描述了中心導航云的吞吐量．根據(jù)排隊論可得：

m=λ_e（1/λ+W_s）.

根據(jù)Little法則[10]可得

2 仿真實驗

2.1道路節(jié)點數(shù)對平均響應(yīng)時間的影響

為分析模型中各參數(shù)對平均響應(yīng)時間 W_s 的影響，本文進行3組實驗，其中兩組為對比實驗，另一組為綜合實驗，模型參數(shù)的取值列于表1．第一組對比實驗得到了 f 為不同值（記為Exp. W_s-n-f） 時平均響應(yīng)時間 W 與節(jié)點數(shù) n 的關(guān)系；第二組對比實驗得到了 c 為不同值（記為Exp. W_s-n-C） 時平均響應(yīng)時間 W_s 與節(jié)點數(shù) n 的關(guān)系．實驗結(jié)果如圖3所示.

實驗結(jié)果表明，對于不同的虛擬機數(shù)量和頻率， n 與 W_s 呈正相關(guān)關(guān)系， n 增加的同時 W_s 也會逐漸上升，且 W_s 上升得越來越快，即在確定的范圍內(nèi)，隨著路網(wǎng)結(jié)構(gòu)復(fù)雜性的增加，平均響應(yīng)時間會增加更快.由圖3（A）可見，當 n 為某一定值時， W_s 會隨著 C 值的增大而快速降低；由圖3（B）可見， W 5會隨著 f 值的提高而快速減少．其原因是在單位時間內(nèi)，如果導航請求的數(shù)量保持不變，則增加虛擬機的數(shù)量或提高CPU的最大頻率，將會縮短請求的等待時間；并且根據(jù) =，系統(tǒng)的服務(wù)速率會隨著CPU頻率的提高而提高，減少請求的等待時間.

2.2車輛數(shù)對平均響應(yīng)時間的影響

圖4為當 C 取不同值（記為Exp. W_s-m-C） 和 f 取不同值（記為Exp. W_s-m-f） 時的平均響應(yīng)時間 W_s 與車輛數(shù) Σ_m 的關(guān)系．由圖4可見，在虛擬機數(shù)量和CPU頻率不同的情況下，隨著車輛數(shù) Σ_m 的增加，響應(yīng)時間 W 。也增加，呈現(xiàn)正向的關(guān)聯(lián)性，且?guī)缀蹩梢砸暈榫€性相關(guān)，即平均響應(yīng)時間隨所服務(wù)車輛數(shù)量的增加近乎線性增長．根據(jù)圖3和圖4的數(shù)據(jù)可見，當 Ψ_m 和 n 的值都較小時， W_s 受 Ψ_m 的影響更顯著．因此，部署時應(yīng)重視服務(wù)區(qū)域內(nèi)的車輛數(shù)量.

2.3 虛擬機規(guī)模和最大頻率對平均響應(yīng)時間的影響

分析圖3和圖4可見， C 和 f 對 W_s 的影響相似，無論是增加虛擬機數(shù)量，還是提高CPU最高頻率都能有效減少響應(yīng)時間．所以，在進行綜合實驗時，僅考慮了 m，n，C 對 W_s 的影響，未考慮 f 對 W 5的影響．圖5為車輛數(shù) Σ_m 、道路節(jié)點數(shù) n 及虛擬機個數(shù) C 對 W_s 的影響，其中第四維用顏色的深淺表

征，顏色越深表示數(shù)值越高．由圖5可見，這些點形成了帶有顏色的立方體，由 A 點出發(fā)到 B 點，顏色逐漸變深，即沿著 方向 W ，的數(shù)值遞增，表明 Ψ_m 和 n 的上升、 C 的下降均會導致 W ；變大．研究結(jié)果表明，中心導航云的平均響應(yīng)時間會隨路網(wǎng)復(fù)雜度的上升、車輛數(shù)量的增長、虛擬機數(shù)量的減少而相應(yīng)地延長．即如果給定了平均響應(yīng)時間的最大值，則利用該模型可準確計算出中心導航云的最小規(guī)模.

實驗結(jié)果表明，路網(wǎng)復(fù)雜度的提升、車輛數(shù)量的增多、虛擬機性能的下降，都會使請求的平均等待時間變長．該模型根據(jù)平均響應(yīng)時間與路網(wǎng)中的車輛數(shù)量、路網(wǎng)中的節(jié)點數(shù)量和虛擬機數(shù)量的關(guān)系，在給定性能約束條件的情況下，能準確計算出服務(wù)于特定區(qū)域的導航云的最小規(guī)模.

3真實數(shù)據(jù)校驗

由于仿真與真實交通環(huán)境存在一定的差異，因此為驗證模型，本文收集了一些城市的真實交通數(shù)據(jù)，以進一步驗證模型的有效性和實用性．首先，從 Mapzen[11]上下載了實驗地圖，并通過 SUMO（simulation of urbanmobility）[12]獲取路網(wǎng)節(jié)點數(shù)；其次，為獲取真實交通流中的車輛數(shù)，采取間接計算的方法，即用車流密度和道路長度的乘積近似得出車輛數(shù).

3.1 車輛數(shù)計算

根據(jù)交通流理論[13-14]下式成立：

其中： q 表示交通流的流量； D 表示交通流中車輛的瞬時密度； u 表示速度； u_m 表示最優(yōu)速度，即交通流取最大值時的速度； D_j 表示交通極度擁堵時的車輛密度； 表示平均車頭間距； 表示平均車頭時距．用 D_m 表示最優(yōu)車輛密度，即交通流取最大速率時的車輛密度，考慮 ，可得

其中e為自然對數(shù)的底.

假設(shè)交通流達到峰值時 ，交通極為阻塞時 ，則可得

將式（11）代入式（9）中第2個等式可得

根據(jù)車流密度 D 的定義，車輛數(shù)等于 D 與道路長度 L 的乘積．此外，車輛的平均速度可利用高德地圖公布的實時交通數(shù)據(jù)得到，道路長度可通過訪問高德地圖的在線服務(wù)取得.

3.2 實驗結(jié)果分析

性能模型中的比例系數(shù) K 和平均請求到達速率 λ 均為常數(shù)，其中 K 與道路節(jié)點數(shù) n 相關(guān)， λ 與車輛數(shù) Ψ_m 相關(guān)．本文實驗中，可令 K 和 λ 分別為

K=12.98exp{5.259×10^-6n}，

本文實驗中，基于各城市交通真實數(shù)據(jù)，假設(shè)對導航請求響應(yīng)延遲的容忍度為 0.5s ，即將約束條件 W_s 設(shè)定為 0.5s ，當 m 和 n 取不同值時，導航云的虛擬機數(shù) C 列于表2，其中 W_s^? 為最小規(guī)模中心導航云所對應(yīng)的 W_s 近似值.

由表2可見，在指定最大平均響應(yīng)時間W。的情況下，本文提出的性能模型可計算出準確的中心導航云最小規(guī)模值．上述各城市交通真實數(shù)據(jù)的實驗結(jié)果證明了本文模型的有效性和實用性.

綜上所述，本文以導航請求的平均響應(yīng)時間作為約束條件，進行了中心導航云模型的構(gòu)建及其性能評估，并討論了構(gòu)建中心導航云所需的最小規(guī)模．實驗結(jié)果表明，本文提出的性能分析模型，能根據(jù)給定的約束條件（即最大導航請求響應(yīng)時間），在滿足目標區(qū)域內(nèi)所有車輛導航服務(wù)的情況下，準確計算出中心導航云所需的最小規(guī)模，對智能交通系統(tǒng)的未來規(guī)劃和發(fā)展有指導意義.

參考文獻

[1]TRAN T K，VAN DUNG N， PHAM X Q，et al. Wi-Fi Indoor Positioning and Navigation： A Cloudlet-Based Cloud Computing Approach [J]. Human-Centric Computing and Information Sciences， 202O，10（1）：1-26.

[2]JIN W L，F(xiàn)ANG L M，WANG L J. Research on the Application of Mobile Navigation System Based on Cloud Computing [J]. Journal of Physics： Conference Series，2020，1648（3）： 032086-1-032086-6.

[3]WAHLE J，ANNEN O，SCHUSTER C，et al. A Dynamic Route Guidance System Based on Real Trafc Data [J]. European Journal of Operational Research，2001，131（2）：302-308.

[4]NGUYEN H H， JEONG H Y. Dynamic Route Guidance via Road Network Matching and Public Transportation Data[J]. Journal of the Korean Institute of Electrical Engineers，2O2l，25（4）： 756-761.

[5]BHAVANI M M， VALARMATHI A. Optimal Trafic Route Finder System [C]/Lecture Notes in Mechanical Engineering. Berlin：Springer，2020：39-47.

[6]KARIMI H A，ROONGPIBOONSOPIT D，WANG H P. Exploring Real-Time Geoprocessing in Cloud Computing： Navigation Services Case Study [J]. Transactions in GIS， 2O11，15（5） ： 613-633.

[7]KARIMI H A，ROONGPIBOONSOPIT D. Are Clouds Ready for Geoprocessing？[M]/Cloud Computing and Services Science. Berlin：Springer，2012：295-312.

[8]BUZACHIS A，CELESTI A，GALLETTA A，et al. A Multi-agent Autonomous Intersection Management （MA-AIM） System for Smart Cities Leveraging Edge-of-Things and Blockchain [J]. Information Sciences，2020， 522：148-163.

[9] PETRUCCI V，CARRERA E V，LOQUES O，et al. Optimized Management of Power and Performance for Virtualized Heterogeneous Server Clusters [C]/Proceedings of the 2011l 11th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing. Washington，D.C.： IEEE Computer Society，2011： 23-32.

[10] LITTLE J D C， GRAVES S C. Litle's Law [M]//Building Intuition. Berlin： Springer，2008： 81-100.

[11] MAPZEN. Metro Extracts [EB/OL]. （2021-08-05）[2024-10-10]. https：//mapzen.com/data/metro-extracts/.

[12] INSTITUTE OF TRANSPORTATION SYSTEMS. Simulation of Urban Mobility： DLR-Institute of Transportation Systems [EB/OL]. （2021-08-05）[2024-09-01]. http：//www.dlr.de/ts/en/desktopdefault.aspx/ tabid-9883/16931_read-41000.

[13］張亞平，楊龍海，劉麗華，等．交通流理論［M]．哈爾濱：哈爾濱工業(yè)大學出版社，2016：8-21．（ZHANGYP， YANG L H，LIU L H，et al. Trafic Flow Theory[M]. Harbin：Harbin Institute of Technology Press，2016： 8-21.）

[14]MAERIVOET S， DE MOOR B. Traffc Flow Theory [EB/OL]. （2005-07-15）[2024-09-15]. htp：//arxiv.org/ abs/physics/0507126.

（責任編輯：韓嘯）