中圖分類號：TP309 文獻(xiàn)標(biāo)志碼：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

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

為構(gòu)建復(fù)雜條件下的動(dòng)態(tài)路徑優(yōu)化模型，文獻(xiàn)[3]利用模糊集理論進(jìn)行了模擬仿真，以真實(shí)交通數(shù)據(jù)作為輸人，得到了實(shí)際交通時(shí)間和交通負(fù)載節(jié)點(diǎn)．文獻(xiàn)[4]提出了一種動(dòng)態(tài)路徑引導(dǎo)（dynamicrouting guidance，DRG）框架，在考慮實(shí)時(shí)道路擁塞信息的情況下能找到從車輛實(shí)時(shí)位置到目的地的最優(yōu)路徑．文獻(xiàn)[5]使用地理信息系統(tǒng)（geographic information system，GIS）提供動(dòng)態(tài)變化的交通流信息和歷史數(shù)據(jù)，通過減少查找優(yōu)化路線和備用路線的重新計(jì)算次數(shù)，以獲得更少的內(nèi)存消耗和資源浪費(fèi)，從而減少了響應(yīng)時(shí)間．文獻(xiàn)［6]設(shè)計(jì)了一種利用谷歌應(yīng)用引擎（google app engine，GAE），稱為C2Geo（cloud computing for geoprocessing）的新技術(shù)[7]，實(shí)時(shí)處理地理空間問題．文獻(xiàn)[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é)果表明，中心導(dǎo)航云能借助實(shí)時(shí)道路交通信息實(shí)現(xiàn)同時(shí)為多目標(biāo)提供最優(yōu)路徑規(guī)劃，同時(shí)，云計(jì)算在處理地理信息等計(jì)算密集型任務(wù)上展現(xiàn)了巨大的潛力．然而，云平臺(tái)基礎(chǔ)設(shè)施通常未考慮數(shù)據(jù)特點(diǎn)和應(yīng)用場景，基礎(chǔ)架構(gòu)通常是為通用計(jì)算設(shè)計(jì)的，因此，還需深入研究如何構(gòu)建一個(gè)適合地理空間專用的云計(jì)算平臺(tái)．基于此，本文建立一個(gè)基于排隊(duì)論的車聯(lián)網(wǎng)中心導(dǎo)航云的性能分析模型，通過分析路網(wǎng)節(jié)點(diǎn)數(shù)、車輛數(shù)以及虛擬機(jī)規(guī)模（虛擬機(jī)數(shù)量和CPU頻率）對模型性能的影響，進(jìn)而通過該模型確定符合約束條件的導(dǎo)航云最小規(guī)模，對導(dǎo)航云未來的發(fā)展具有重要意義.

1 中心導(dǎo)航云模型

1.1地圖模型和導(dǎo)航過程模型

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

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

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

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

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

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

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

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

標(biāo)識(shí)，則將存在 （m+1） 個(gè)狀態(tài)，即 0，1，…，m ．如圖2所示，Markov鏈中的狀態(tài)標(biāo)識(shí)了中心導(dǎo)航云當(dāng)

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

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

Cgt;λ/μ.

平衡方程為

當(dāng) k 取不同值時(shí)，可得 P_k 的表達(dá)式為

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

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

平均隊(duì)列長度為

L_s=L_q+λ_e/μ，

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

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

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

2 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

3真實(shí)數(shù)據(jù)校驗(yàn)

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

3.1 車輛數(shù)計(jì)算

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

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

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

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

將式（11）代入式（9）中第2個(gè)等式可得

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

參考文獻(xiàn)

[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è)大學(xué)出版社，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.

（責(zé)任編輯：韓嘯）