‧ 應用智慧設備和物聯網的 V2I-V2V 系統中，塞車的路由發現機制

 

What's V2V? - And Why Will It Make Your Car Safer?

什麼是V2V？ - 為什麼它會讓你的汽車更安全？

IDVIEW 即將登場 100% MIT

MDPI

（本文屬於特刊無線傳感器網路與物聯網）

摘要

物聯網是一種新的範式，在這種範式中，特定上下文中的對象，可以整合到傳統的通信網路中，以積極參與解決確定的問題。車對車 (V2V) 和車對基礎設施 (V2I) 技術是物聯網的具體案例，也是智慧交通系統 (ITS) 的關鍵推動因素。V2V 和 V2I 已被廣泛用於解決與城市交通相關的不同問題，其中最重要的是交通堵塞。高比例的堵塞，通常是由於車輛基礎設施，資源使用不當造成的。此外，由於其高動態行為，將交通堵塞納入車輛交通決策是一個挑戰。

在本文中，建立了街道擁堵率負載均衡優化模型。後來，我們探索了一個完全面向堵塞的路由發現機制，我們提出了基於 V2I 和 V2V 通信的通信基礎設施應該支持它。該機制還與修改後的 Dijkstra 方法進行了比較，該方法在堵塞狀態下做出反應。最後，我們比較了車輛出行效率，與車聯網容量使用效率的結果。該機制還與修改後的 Dijkstra 方法進行了比較，該方法在堵塞狀態下做出反應。最後，我們比較了車輛出行效率與車聯網容量使用效率的結果。該機制還與修改後的 Dijkstra 方法進行了比較，該方法在堵塞狀態下做出反應。最後，我們比較了車輛出行效率，與車聯網容量使用效率的結果。

關鍵詞： 物聯網；交通擁堵；車輛路線；負載均衡優化；公平；擁堵；V2I ; V2I ; 它的

一、簡介

隨著經濟和科技的快速發展，城市不斷擴張，人口密度不斷增加，機動車輛密度也隨之增加。城市中高車輛密度的主要影響，是當車輛行駛到目的地時，由於行駛的車輛數量超過道路容量，並阻塞其路線而無法行駛，因此車輛不得不等待，直至到達目的地時出現堵塞現象。前方車輛能夠移動。這種等待的主要影響是旅行時間、燃料消耗、事故率和 CO 2 排放量的增加（研究顯示，人類活動產生的二氧化碳排放量中約有 30% 來自車輛）。

解決城市堵塞問題的主要策略是：增加現有道路的數量和規模（容量），鼓勵人們使用替代汽車交通，透過堵塞收費系統，或使用道路選擇性和配給使用。在特定時間間隔內，限制使用等機制，並以更有效的方式利用現有道路容量。從上面的建議來看，前三個重點是減輕堵塞的負面影響，而不是關注成因。第四個提案可能會產生更大的影響，因為它側重於車輛如何使用可用街道。然而，這並不是一個簡單的方法，因為司機很難確定他的決定如何影響車輛網路狀態，從而影響他自己的行程。堵塞的主要特徵之一是以不可預測的方式發生，因此無法確定車輛必須等待多少次，因此，基於這些期望的總行駛時間是多少。

美國交通部創建了聯邦 ITS 計劃，其中確定了以下兩個方面中的任何一個方面的投資機會和舉措：交通基礎設施和車輛應用；這些項目的分類導致了現有 ITS 系統的分類。在表1顯示了當前的應用，如果他們專注於交通基礎設施和車輛系統。

表 1. [ 4 ]提供的 ITS 分類法。

然後，為了有效地利用交通基礎設施，近幾十年來一直使用智慧交通系統。智慧交通系統 (ITS) 是一組新的組件和服務，它整合了資訊、基礎設施和通信技術，以允許其元素進行交互並提供特定的功能，從而提高城市交通的效率。ITS 的領域已經擴展到支持多種操作，因此現在有大量的項目、提案和應用。

交通基礎設施最常見的應用是資訊傳播應用，而在車輛系統的應用中，最常見的是駕駛員輔助應用。前者指的是允許在特定交通條件下有效地收集信息並將其分發給車輛和作為系統一部分的其他元素的系統。第二種是指使用從每輛車的上下文中收集的資訊（例如速度或與其他車輛的接近程度）的應用，以使駕駛員能夠即時做出決策，以防止事故發生，提高其路線效率，提供更安全的旅程，等等。

解決方法依賴於特定的概念，例如物聯網 (IoT)，其範例如圖 1所示。物聯網是指任何允許將不同對象，整合到通信環境中的技術，這種方式可以透過軟體訪問和管理實體世界。主要部件涉及傳統通信技術（GSM、LTE、Wimax等），以及目標對象中的感測器和執行器。

圖 1. 物聯網範式。

車對車 (V2V) 通信和車對基礎設施 (V2I) 通信的概念，已作為物聯網的子集引入。V2V 通信，在所示圖2一個，允許兩個車輛直接交互，而不依賴於一個固定的通信基礎設施，而 V2I 通信，在所示圖2 B中，允許車輛與道路基礎設施的元件，諸如交通燈進行通信控制器、智慧信號等。

圖 2. V2V 和 V2I 技術的表示。( a ) V2V 通信；( b ) V2I 通信。

在車輛路由的特定情況下，傳統方法基於靜態變量，或者在將路線分配給車輛之前，從道路環境中獲得的資訊，是眾所皆知的或計算的。這些資訊通常不會隨著時間的推移而改變，例如，基於 Dijsktra 算法 的方法專注於最小距離，或 Dijkstra 的修改版本，將成本函數更改為另一個參數，即，行程時間，但假設它們可以在計算路線之前解決。在堵塞的情況下，這個變量通常不是大多數提案中優化函數的一部分，這意味著，開發的方法是堵塞感知的，但不是面向堵塞的。此外，當堵塞必須加以考慮，它是從其他變量如預期時間或速度得到，但如前所述，這些作品可以建立預先計算的值，以消除在全球堵塞狀態（活力）。這樣做的原因是，以與決策相關的方式維護和處理，不斷變化的堵塞狀態的成本很高。這就是為什麼 V2I 和 V2V 系統，對於解決涉及高動態參數的問題非常重要。它們允許大量設備的整合和協作，從而使收集和處理上下文資訊的任務，變得不那麼複雜。

本文的工作是開發一種方法，在該方法中，評估路線的條件，涉及車輛所遵循路徑中堵塞的定義。此外，該方法將得到基於 V2I 或 V2V 通信的通信機制的支持，允許解決在完全動態的環境中，獲得最相關的全局堵塞狀態的問題。此外，我們根據可用街道的使用效率，來評估所提出的方法，並提出了一個關於街道負載平衡的優化模型。

本文的其餘部分組織如下：在第 2 節中討論了相關工作。在第 3 節中，提出了每條街道容量使用負載平衡的優化模型。在第 4 節中提出的基於堵塞的機制，被描述為支持基礎設施。在第5節的仿真的描述中，驗證場景和結果。最後在第 6 節中，我們提出了結論和未來的工作。

2. 相關工作

2.1. V2V 和 V2I 應用的技術背景

自從 80 年代和 90 年代提出 ITS 以來，這些系統提供了解決城市環境中，車輛堵塞問題的負面影響的新方法。ITS 中的工作基於透過新技術，在車輛領域的不同元素之間進行有效通信。

歐洲電信標準協會 (ETSI) 已定義了 ITS 通信 (ITSC)的架構標準。參考架構遵循 OSI 模型的原則，定義了 OSI 層的擴展以支持 ITS 通信。正如圖3所示，三個主要的層被定義為：訪問，聯網和設施。此外，還存在應用程序、管理和安全層。通用架構和示例元素如下所示。

圖 3. ITS 系統架構中的主要組件。

圖 4. 現有的 ITS 子系統。( a ) 個人 ITS 子系統；( b ) 車輛 ITS 子系統；( c ) 路邊 ITS 子系統；( d ) 中央 ITS 子系統。

三個是為 ITSC 定義的功能元素：Gateway、主機和路由器。這些元素存在於多個 ITS 子系統中：個人 ITS 子系統（圖4a ）、車輛 ITS 子系統（圖4b）、路邊 ITS 子系統（圖4c）和中央 ITS 子系統（圖4d）。

物聯網範式成為 ITS 應用程序的推動者。物聯網完全基於這樣一個事實：現實世界中的對象可以整合到傳統通信中，充當能夠根據新的特定服務的需求，修改它們所在的上下文的主動組件。物聯網的基石是目標對像中，可用的感測器和執行器，這些感測器和執行器結合到通信架構中。圖 5顯示了感測器網路和物聯網組件之間的關係 。

感測器/執行器與其他網路元素，結合使用的具體情況，是車輛對基礎設施和車輛對車輛通信。V2V 和 V2I 是車輛自組織網路 (VANET) 的兩個子集，它們是用於兩輛或多輛車輛之間以及車輛與道路基礎設施之間通信的架構，其中具備處理能力和無線通信能力的人可以組成網路，如他們沿著道路移動。在 VANET 架構的規範中，定義了一些協議來實現網路中元素之間的有效通信。

圖 5. 感測器網絡和物聯網之間的關係。經Perera, C.等人許可轉載。, IEEE 通信調查和教程；IEEE 出版，2013 年。

在對物理、MAC、網路、傳輸和應用中的協議進行了回顧。在物理層，Dedicated Short-Range Communication (DSRC) 最近被不同的標準化實體定義，以在移動車輛（200 km/h，範圍從 300 到 1000 m）中建立短程通信機制。IEEE 802.11 技術委員會已將 DSRC 定義為車載環境中的 802.11p 無線接入 (WAVE) 。一些研究人員已經集中在研究 802.11p 的城市交通環境[性能]。另一方面，3GPP 標準用於為 V2V 和 V2I 提出的其他通信解決方案 。這兩種技術的比較顯示，使用 802.11p 的節點間通信的總體性能，優於該機制基於 3GPP 技術（例如 LTE）時獲得的性能。然而，將 3GPP 技術用於車載通信的主要優勢，在於 (1) 實施該技術的設備市場的滲透率，以及 (2) 現有佈署的基礎設施。

此外，車載網路可以支持不同的通信機制：圖6a 所示的單播通信，其中數據通過多跳無線通信從一個源節點發送到一個目標節點；組播/地理廣播通信分別如圖6b、c所示，其中，數據從一個源節點發送到多個目標節點，不同之處在於在地理廣播通信中，目標節點是按地理位置分組的；和廣播通信如圖6 d所示，其中源節點向其所有鄰居發送數據。

圖 6. 車載網路支持的支持機制。( a ) 單播通信；( b ) 多播通信；( c ) 地理廣播通信；( d ) 廣播通信。

2.2. 現有的動態路線規劃算法

回顧在 VPR 問題的車輛路由階段，計算路線的最相關算法。這些分為 3 組，如圖 7所示。

圖 7. 動態路線規劃算法的分類。經 Djahel, S.等人許可轉載。, 首屆智慧城市車輛交通管理國際研討會 (VTM)；IEEE 出版，2012 年。

最優算法專注於在所有現有解決方案中，尋找全局最優解決方案。在這個類別中可以找到 Dijkstra 和增量圖算法。啟發式算法是探索總解的子集，並允許找到非常接近全局最優解的算法。作為啟發式算法的示例，我們發現 A* 算法、遺傳算法 [、蟻群優化和禁忌搜索。混合算法嘗試將每個類別中的算法組合起來，以生成強大的組合解決方案，以彌補每個單獨策略的任何缺點或限制。例如，Kanoh等人提出的在多目標優化中使用 Dijkstra 啟發式進行動態路線規劃的遺傳算法。

基於所提出的分類，作者通常在不同的場景中對所描述算法的評估做出一些不同的貢獻。例如，在 Wang等人所做的工作中，使用 SUMO 模擬器，在使用從 TAPAS-Cologne 項目數據集獲得的真實數據的場景中，評估基於最短路徑策略的四種算法。評估的算法是 Dijkstra 和 A*，每一種都採用靜態和動態方式。他們選擇了三個區域（中心、郊區和農村），並根據進行的評估，提出了在不同道路場景中最有效的路由算法的建議。

3. 街道負載均衡優化模型

在本節中，我們將探討堵塞負載平衡模型的提議，以便資源（具有各自容量的街道）在不同用戶（車輛）之間有效分配。在提出了一種多目標優化方案，該方案遵循 MINMAX 方法對多播路由鏈路的使用，即最小化最大鍊路利用率，以獲得更好的平衡。此外，在 Jain's index 用於描述異構無線網路，根據網路負載分配資源的平衡百分比。這就是為什麼我們選擇 Jain 提出的方程，來描述車輛網路街道使用的平衡。

3.1. 車載網路表示

車輛網路被建模為有向圖G = (N , L)，其中N是表示交叉點的節點集，L是表示連接節點的道路的鏈路集；i , j ∈ N 是節點，(i , j) ∈ L 是對應於街道 L 的有序對。對於車輛v$$, 節點 電子v, dv ∈ N$$定義，分別代表起點和終點節點。車輛將穿過網路的街道直到到達目的地，因此它的路徑對應於一組街道磷v= { (電子v,j1) , ... , ( 一世n,dv) } $$如圖8所示。

圖 8. 車輛網路中車輛路線的圖示。

網路有一組狀態 克$$對應於車輛在特定時刻，位於不同網路鏈路中的方式。這種狀態如圖 9 所示，其中我們有兩輛車透過車載網路，總共有 4 種狀態：在狀態 1 中，車輛 1在街道上 ( n 1, n 2)，以及車輛2在街上 ( n 1, n 4); 在狀態2中，車輛1在( n 2, n 5)中，車輛2在( n 4, n 6)中；在狀態 3 中，車輛 1處於 ( n5, n 7) 並且車輛 2在 ( n 6, n 5) 中；在狀態 4 中，車輛 1不再在網路中，而車輛 2在 ( n 5, n 3) 中。

一條街 ( i , j )$$ 有用 你( i , j )（ķ ）$$ 對應於一個州街道上的車輛總數 克$$, 和最大容量 C( i , j )$$. 決策二元變量Xv ( i , j )dv（ķ ）$$ 被定義為 Xv ( i , j )dv（ķ ）$$ = 1 如果處於狀態 克$$ 一輛車 v$$ 有目的地 dv$$ 上街 ( i , j )$$, 否則為 0。因此，解向量X是每輛車在每個狀態下網絡不同街道的分配集。

圖 9. 具有四種狀態的車輛網絡。

3.2. 優化模型中車輛堵塞的定義

街道上的車輛堵塞 ( i , j )$$ 表示為狀態 k 的街道使用率與街道容量之間的比率：

α( i , j )( k ) = 你( i , j )（ķ ）C( i , j )= ∑v ∈ VXv ( i , j )dv（ķ ）C( i , j )$$$$

(1)

3.3. 基於 Jain 公平指數的負載均衡

Jain 的公平指數方程用於平衡車輛網路中每條街道的堵塞，並將其應用於以下公式化問題：

Fα( k ) =[∑( i , j ) ∈ Nα( i , j )( k ) ]2∑( i , j ) ∈ N是( i , j ) *∑( i , j ) ∈ N(α( i , j )( k ) )2, α( i , j ) ≥ 0 ∀ ( i , j ) , ∀ k   $$$$

(2)

在哪裡 是( i , j ) $$是一個二元變量 = 1 如果節點 ( i , j )  $$ 連接，否則為 0。

結果為 Fα（ķ ）$$ 在 [0, 1] 範圍內，接近 1 的值表示可能街道的更好分配，因此我們可以確定優化模型包括最大化以下值 Fα（ķ ）$$.

3.4. 型號限制

上述模型的主要限制是：

3.4.1. 容量限制

在狀態k 中分配給街道的車輛數量不能超過街道的容量：

∑v ∈ VXv ( i , j )dv( k ) ≤ C ( i , j  ) , ∀ ( i , j ) ∈ N , ∀ k ∈ K $$$$

(3)

3.4.2. 連接限制

此約束指定在同一狀態 ka 車輛 v 不能分配到兩條不同的街道：

∑( i , j ) ∈ NXv ( i , j )dv( k ) = m aX1 ≤ i , j ≤ | N|(Xv ( i , j )dv( k ) ) ∀v∈V , ∀ k ∈ K $$$$

(4)

3.4.3. 中間節點的流量限制

在作為每輛車路線一部分的中間節點中，進入的車輛數量必須等於離開的車輛數量，因此車輛流量的總和等於 0：

∑ķ ∈ ķ  ⎛⎝⎜∑( i , j ) ∈ N, Xv ( i , j )dv( k ) -∑( i , j ) ∈ N, v ∈ V  Xv ( j , i  )dv（ķ ）⎞⎠⎟= 0 , i ≠ 電子v, j ≠ dv ∀ v ∈ V$$$$

(5)

3.4.4. 目標節點

此約束指定車輛行駛的路徑應始終在其目的地節點結束：

∑ķ ∈ ķ  ∑( i ) ∈ NXv ( i , j )dv( k ) = 1 , j = dv, ∀ v ∈ V$$$$

(6)

3.4.5. 關於使用模型的結論

描述的模型在 GAMS 軟體中執行，GAMS 軟體是一種用於線性、非線性和混合整數優化問題的通用代數建模工具。圖 10顯示了獲得的結果：圖10a 是使用建議模型為狀態k獲得的分配，圖10b 是使用優化路線成本的替代模型獲得的狀態k分配。

圖 10. 使用 ( a ) 建議模型和 ( b ) 其他基於路線成本的優化模型獲得分配。( a ) 獲得與建議模型的分配( b ) 獲得與其他模型的分配。

表 2顯示了每個模型的計算公平性。

表 2.圖 10 中 的分配結果。

圖 11顯示了每個模型中每個鏈接的使用情況以及獲得的公平性。

圖 11. 堵塞級別的圖形結果。

圖 12. 鏈接的總體分配。

正如我們在上圖中看到的，當使用所描述的模型時，堵塞水平更加平衡，這導致街道分配的公平性值增加。儘管如此，圖 12中為整個車輛路線顯示的街道分配表明，某些車輛的跳躍次數更高，以實現更好的公平值。在下一節中，將評估優化車輛個體路線的機制的提議，並將其與獲得的公平值進行比較，從而建立該度量在車輛網路行為中的相關性。

4. 提案

在幾項工作中，我們注意到在考慮時，車輛網路的堵塞資訊是在本地描述的，並且無法建立車輛網路的全局堵塞狀態。這是對不同方法來路由車輛的限制，原因是以有效的方式確定和維護可變交通資訊的成本很高，主要是如果它是接收交通資訊的中央實體，併計算和分配路線給每個不同的車輛。這就是一些作者考慮整合 V2V 和 V2I 通信方法的原因，以減少車輛路由或對堵塞事件做出反應所需的工作量。

所做的工作就是基於這個想法。當車輛因意外堵塞事件而需要重新路由時，它建立了車輛路線平均時間的優化模型，並使用 MAS 架構來實施所提出的解決方案，並將新路線分配給車輛。在這種情況下，參考流量負載的優化參數是在本地獲得的。

在本節中，我們探索了一種通信基礎設施，該基礎設施允許車載網路中的不同元素進行交互，以建立所需的資訊，以獲得基於全球堵塞的最佳路線。此外，我們解釋了基於支持基礎設施的執行算法。

4.1. 車載網路中的通信技術和元素

系統中通信的主要元素是交叉路口節點、車輛和佈署，在道路基礎設施上的路邊感測器。這些車輛是具有通信能力的設備，還與支持 GPS 的設備一起計數，這樣車輛就可以知道其實際位置，和目的地節點的位置，並且可以透過 802.11p 技術與其他車輛進行通信。它還與交叉路口節點通信，以檢索與其路線相關的資訊，並在車輛進入堵塞狀態時進行報告。街道被視為具有距離和容量等特徵的靜態元素，路邊感測器能夠從環境中收集數據，並將其傳輸到交叉路口節點（即車輛計數和速度測量）。

路口節點被視為活動元素和檢查站，因此負責儲存從路邊感測器收集的數據，以建立堵塞狀態，並可以透過 802.11p 技術與車輛通信。交叉點還透過 802.11p 與下一個節點進行短距離分離，或透過 802.16 進行大分離，或透過 3GPP 通信（如 2G、3G 和 LTE）與形成臨時網路的其他交叉點節點進行通信。圖 13 顯示了支持的通信基礎設施：

圖 13. 支持通信基礎設施。

路線分配和重新計算服務將在每個節點中進行，這意味著每個交叉路口節點，都能夠為其附近的車輛分配路線，而無需依賴中央實體。與車聯網相關的擁堵數據是透過節點和路邊感測器的合作建構的，並在所有節點之間共享，因此無需在每次車輛請求時，由單個實體重新計算整個車聯網的堵塞狀態。路線或影響它使用的街道。當車輛進入下一個路口節點的範圍時，它會發送其路線意圖，路口節點根據網路堵塞狀態，分配車輛將要遵循的街道集，如圖14所示。圖15顯示了重新計算過程：當路邊感測器資訊報告感測超過閾值時，或當車輛報告無法移動時，會觸發重新計算服務。重新計算消息傳送到街道中的源交叉路口節點，該交叉路口節點搜索，並為前一條街道中其範圍內的所有車輛，分配替代路線。

圖 14. 車輛和交叉路口節點之間的通信。

圖 15. 路由重新計算機制

4.2. 提議的算法

本節介紹了由交叉口執行的算法的主要方法，以獲取車輛的路線，或在需要時重新計算路線。此外，還描述了另外三個近似值，以便在後續部分中執行的模擬期間，在車輛行程效率方面，比較所提出的方法。

4.2.1. 全局堵塞算法 (GC)

所提出的解決方案目的在根據車輛網路不同街道上，報告的堵塞狀態，來分配車輛的路線，因此當車輛決定遵循一條路線時，它會在後續街道中試驗最佳的全局堵塞狀態。因此，車輛的未來近似堵塞，被認為是獲得車輛應該遵循的最佳路線。

為此，節點具有潛在路由的資訊，並且能夠以這樣的方式，獲得每個路由的堵塞狀態，即所提供的路由是具有較少全局堵塞的路由。這意味著車輛不僅在堵塞較少的街道上行駛，而且在堵塞較少的路徑上行駛，因此任何街道的使用，都會影響路徑的全局堵塞狀態，即使不是下一個連接的街道。透過這種方式，我們期望算法不僅對堵塞做出反應（也就是說，只有在檢測到堵塞時才重新分配路由），而且可以防止堵塞，從第一次路由分配中減少堵塞。

在算法執行之前計算潛在路由，並且在允許節點間通信的基礎設施上，支持該策略。此路由計算步驟生成一個輸出，該輸出是到拓撲中任何節點的路徑列表。有了這些資訊，一個節點就能夠知道到另一個節點的所有現有路徑，只要它存在。路徑計算方法不屬於本文討論範圍。

此外，節點能夠為每條路徑建立全局堵塞狀態，並與前方節點交換消息，並接收由路邊感測器或其範圍內前方車輛觸發的重新計算消息。在這兩種情況下（車輛請求路線或需要重新計算），我們的路線分配算法由交叉路口節點執行，以返回車輛的相應路線。

算法 1 的偽代碼如下所示。

算法 1.全局堵塞 (GC)

要求：車輛的目的地節點d$$ 要求：所有可能的路徑d$$： p一個噸ħ小號= {磷1, ... ,  磷n}$$ 1：排序 p一個噸ħ小號$$ (A 到 Z) 由 Ç Ò Ñ克Ë小號噸我ön磷一世$$ 2：路徑 p a t h = p a t h s [ 0 ]$$ 3： p一個噸Hv= p一噸ħ$$ 4：返回 p一個噸Hv$$

該算法的輸入，是車輛的目的地節點和到目的地節點的潛在路線的路徑列表。這個想法是算法只返迴路徑，並為需要的車輛或一組車輛進行分配。在車輛需要路線的情況下，車輛將目的地節點通知給交叉路口節點並執行算法。在需要重新計算的情況下，交叉點節點需要其範圍內的車輛，即它們的目的地節點。之後，它為算法上報的每個不同的目的節點生成相應的路徑，並根據車輛的路線意圖通知車輛新的路徑。這避免了當每個車輛具有相同的目的地時，節點必須為每輛車重複該算法。

4.2.2. 改進的 Dijkstra 算法 (MD)

開發此實現是為了將車輛，根據距離沿著路線行駛時發生的情況，與提議的基於堵塞的機制進行比較。在這種情況下，任何車輛的初始路線，都是使用 Dijkstra 啟發式計算的，以計算每輛車的最短路徑。車輛將嘗試沿著該路徑行駛，直到到達目的地節點。在車輛無法前進到下一條街道的情況下，交叉路口節點再次使用，Dijkstra 策略重新計算相關路線，但只考慮不擁擠的相鄰街道（如果有）。

尋找替代街道的最後一個變化的目的，是不複制具有相同起點/終點節點的車輛的堵塞狀態。如果一個重要的組具有相同的 O/D 特性，並且不重新計算路由，則堵塞可能總是更大，從而很難實現提案之間的客觀比較。

在沒有替代道路的情況下，車輛必須在當前街道上等待。尋找替代街道的最後一個變化的目的，是不複制具有相同起點/終點節點的車輛的擁堵狀態。算法 2 顯示了路由重新計算過程的偽代碼。

和原來的 Dijkstra 一樣，該算法接收目的節點並有一個距離矩陣，但是當它修改下一個距離最小的節點時（算法 3），算法驗證該節點是否與當前節點相連，如果是，如果街道用途不等於容量。這允許它根據下一個空閒街道建構最短路線，以獲得替代路線，這樣汽車就不必等到原始路線空閒時。

算法 2.修改的 Dijkstra 路由重新計算 (MD)

要求：需要車輛v 要求：車輛的目的地節點d 要求：實際節點實際 要求：相鄰節點Ad = { k 1 ,..., k n } 不為空 要求：相鄰距離矩陣d [ n ] ▷ n = 節點數 要求：未訪問節點unVisited = { } 空 1：d [實際] = 0 2：將實際添加到unVisited 3：雖然仍然是unVisited 中的節點do 4： Min =獲取最小距離節點 (3) 5： 如果 Min不存在則 6： 返回沒有可用的替代路線 7: else 8:從unVisited 中取出Min 9: 對於相鄰節點中的所有k Ad = { k 1 ,..., k n } do 10: if d [ k ] > distance ( actual , k ) + d [ Min ] then 11 : d [ k ] ←距離(實際, k ) + d [最小 ] 12：如果結束 13：結束 14： 結束如果 15：結束

算法3.獲取最小距離節點

要求：未訪問節點unVisited = { u 1 ,…, u n } 非空 要求：實際節點實際 要求：鄰接距離矩陣d [ n ] 1: min = NotExists 2: for u in unVisited do 3: if use ( actual , u ) ≥ capacity ( actual , u ) AND u is not direct 連接到實際 then 4:從unVisited 中取出u : else 6: if d [ u ] < d [ min ] then 7: min ← u 8：結束如果 9：結束如果 10：結束 11：返回 分鐘

4.2.3. 基於局部堵塞的算法 (LC)

在這種方法中，僅根據與節點相鄰街道的局部堵塞資訊，為車輛分配路線。這樣做是為了確定從車輛附近狀態授予的堵塞資訊，是否足以獲得良好的結果，或者是否有必要在最優搜索空間中開發詳盡的解決方案。在這個實現中，交叉路口僅根據其堵塞狀態，評估其相鄰街道，並將可用街道之間堵塞較少的街道報告給車輛，即，在那些有足夠車輛空間的街道之間。偽代碼如下所示（算法 4 和 5）。

算法 4.局部擁塞（LC）

要求：需要車輛v 要求：實際節點實際 1：節點k = 獲取下一個擁塞最小且具有 車輛空間 (6) 2：如果 k存在則 3： 返回下一條街道（實際，k） 4：else 5： 返回沒有可用的路線 6：結束如果

算法 5.獲取下一個節點

Require: Adjacent nodes Ad = { k 1 ,…, k n } 非空 Require:實際節點actual 1: min = NotExists 2: for k in Ad do 3: if use ( actual , k ) < capacity ( actual , k ) AND 擁塞( actual , k ) <擁塞( actual ,min ) 4: min ← k 5：結束如果 6：結束 7：返回 分鐘

4.2.4. 自然行為算法

在此實施中，目標是模擬如果決策不受任何通信系統支持，車輛在城市中行駛時會做什麼。車輛不與十字路口節點通信，因此當它到達十字路口時，它只會評估與其當前街道相鄰的街道，並選擇容量小於其使用量的第一個街道。在現實生活中，這種行為被轉化為司機在他們適合的第一個移動。偽代碼如下所示（算法 6 和 7），並在仿真中由車輛執行。

算法 6.自然行為

要求：實際節點實際 要求：目標節點目的地 1：節點k = 獲取連接第一條可用街道的下一個節點 (7) 2：如果 k存在那麼 3： 如果 k =目的地 那麼 4：退出網絡 5： 其他 6：等待 7：結束如果 8：其他 9：等待 10：結束如果

算法 7.獲取第一個可用節點

Require：實際節點實際 Require：相鄰節點Ad = { k 1 ,..., k n } 非空 1: for k in Ad do 2: if use ( actual , k ) < capacity ( actual , k ) then 3: return k 4：結束如果 5：結束 6：返回 不存在

5. 驗證場景

本節描述了不同方法的驗證過程。我們定義了一個基於兩個場景的計算實驗，一個是對每個實現的結果，進行小規模檢查的控制場景，一個是包含從谷歌地圖中，提取的一些特徵的參考場景。此外，還描述了執行的模擬，並指定了評估指標以在實現之間進行比較。

5.1. 場景定義

5.1.1. 控制場景

對於控制場景，我們有一個由 15 條街道組成的小型車輛網路，在區間 [ 7 , 20  中具有隨機容量。] 和等於該容量的距離。另外，我們定義了特定的起點和終點節點O，N。選擇相同的 O/D 來評估，當一組具有相同起點/終點特徵的車輛，獲得一條新路線時，這些車輛的新路線是否相同，堵塞被轉移到新路線而不是變得更好。這裡開發了兩種不同的模擬方式：首先，我們建立了最大數量 N 車輛通過網路，並在同一轉彎處進入，以建立車輛網路狀態，如何隨著車輛數量的增加而演變；在第二個模擬中，在 X 步之後加入了數量 F 的車輛，以比較不同的車輛流量。對應的配置如圖16所示：

圖 16. 建議的控制方案。

5.1.2. 參考場景

這個場景基於之前實現的工作，它提出了堵塞收費的建議。本文以波哥大為例分析了哥倫比亞城市的擁堵情況。作為這項工作的一部分，在波哥大市確定了堵塞區域，這些區域位於城市主要經濟活動集中的擴展中心。選擇確定的區域之一來創建參考場景。其主要特性如圖17所示。

圖 18顯示了為此區域創建的車輛網路。所構成的網路並不打算準確表示該區域，因此僅針對主要走廊進行映射，並進行了一些調整以獲得更多連接的節點，交通流向由作者決定。基於提出的車輛網路圖，有必要確定每條街道的容量、通過它們的大致車輛數量，以及它們各自的起點和目的地。

圖 17. 理想的堵塞區域，取自谷歌地圖。

圖 18. 提議的車輛網路。

(a) 街道容量

為了確定每條街道的容量，使用了以下公式：

Ç一個p一個Ç我噸是一世= 升È Ñ克噸ħ小號噸ř Ë Ë 噸一世一個v Ë ř一個克È升È Ñ克 Ť ^ h$$$$

(7)

平均長度定義為車輛平均長度加上最小間距的地板函數。該最小值對應於哥倫比亞國家交通法規中定義的間距，即從一輛車的前端到另一輛車的後端測量的兩個連續車輛之間的距離。

• 為了 升È Ñ克噸ħ小號噸ř Ë Ë 噸一世$$，獲取為每個街道網路提供 Google 地圖的近似距離。
• 為了 一個v Ë ř一個克È升È Ñ克 t h = v e h i c l e a v e r a g È升È Ñ克 t h + m i n g 一個p$$, 取為所有車輛的平均長度 3.8 m 和 2.4 m 的車輛間隔，因此總長度為 6.2 m。

(b) 每輛車的起點/終點對和近似流量

在這種情況下，車輛從每個不同的起點和目的地出發。由於我們定義了網路中每條街道的流量，因此有必要建立可能的起點和終點 (O/D) 的子集，以便任何車輛都可以到達其目的地節點。當車輛進入網路時，車輛的 O/D 是隨機分配的。此外，在模擬的每一步都建立了一個包含在網絡路中的車輛數量 F，因此，每次允許隨機數量的車輛加入。這樣做是為了建立所提出解決方案的穩健性，因為在不同的行程條件下，網絡的整體狀態可能會發生變化，並且檢查解決方案在不受控制的參數下的行為是有用的。

5.2. 模擬說明

由於我們沒有使用專門的車輛交通模擬器，因此有必要對車輛在特定假設下在車輛網路中移動時的行為進行建模。車輛在沿著路線行駛時將具有三種可能性：移動、等待和退出網路。當車輛開始行駛時，它沿著初始街道移動，其最終位置永遠不會超過前車位置減去最小間距。如果超過間隔，車輛不會移動並等待。車輛的位置變化是完全離散的。車輛移動流程圖如下圖所示：

圖 19. 車輛運動模擬。

5.3. 比較指標

5.3.1. 路線效率

由於模擬以離散方式運行，因此有必要進行一些近似以建立車輛的路線效率。我們從這樣一個事實開始：車輛必須等待的次數，會影響它所遵循的路線的品質。這種情況下的效率定義如下：

Ë ˚FF我Ç我È Ñ Ç是v= Ñ ü中號b Ë ř ö ˚F  米直徑：v Ë小號 Ñ ü中號b Ë ř ö ˚F  米直徑：v Ë小號+瓦特一個我噸小號$$$$

(8)

其中車輛的移動次數由街道上的總「槽位」或其容量決定，並且每次車輛無法前進時都會產生等待。建議將此指標直接與行駛的總距離進行比較，因此儘管汽車根據其距離選擇了成本更高的路線，但如果在行程中沒有產生等待，則效率為 1。

5.3.2. 行駛距離

它是車輛從起點節點到終點節點的總行駛距離：

Ť d= ∑( i , j ) ∈電阻vd( i , j )$$$$

(9)

5.3.3. 公平指數

公平指數用作比較指標，以確定車輛路線效率的個別優化，與道路基礎設施的使用方式之間的關係。按照第 3.2 節中使用的等式 ，公平性計算如下：

Fα( k ) =[∑​你秒電子小號噸ř Ë Ë噸一世/ Ca p a c i t是小號噸ř Ë Ë噸一世]2秒* Σ( U秒電子小號噸ř Ë Ë噸一世/ Ca p a c i t是小號噸ř Ë Ë噸一世)2$$$$

(10)

其中 S 是車輛網路中的街道總數，k 是當前狀態。

5.3.4. 堵塞

呈現平均堵塞的目的，是將其與獲得的效率和公平性聯繫起來：

μ ( k ) =∑​[你秒電子（小號噸ř Ë Ë噸一世)Ca p a c i t是（小號噸ř Ë Ë噸一世)]秒$$$$

(11)

其中 S 是車輛網絡中的街道總數，k 是當前狀態。

6. 獲得的結果

本節介紹了一組評估場景中每個實現的結果。首先，我們使用第 5.1.1 節中描述的兩種不同驗證方法呈現控制場景結果：N 輛汽車和 F 輛汽車。稍後，我們將展示參考場景結果。下一節描述了結果呈現。

6.1. 取得成果展示

對於每個場景，我們提供兩種圖形：代表相應度量的一般行為的圖形，以及代表度量值與獲得的最佳值的比較結果的圖形。下面給出了每一種的描述。

6.1.1. 一般行為

圖 20、圖 22、圖 23、圖 24、圖 25、圖 27、圖 28、圖 29和圖 31顯示了在相同場景下為每個實現獲得的值。呈現的值對應於 (a) 當描述的度量是效率或距離時，一組車輛的每個度量的平均值；或 (b) 當所描述的度量是公平性或平均擁塞時，為模擬的狀態 k 獲得的特定值。每個場景中都描述了該場景的具體細節。

6.1.2. 與最佳價值的比較

為了更好地了解一個實現相對於另一個實現的好壞，基於每個指標的最佳結果的比較百分比被執行，以指示每個實現離最佳結果有多遠。當最好的結果應該是整體的最大值時，這個百分比的計算公式，當最好的值應該是最小值時，百分比的計算公式：

% = （乙ë小號噸- - [R Ë一升）乙Ë小號噸$$$$

(12)

% = ( R e a l - B e s t )乙Ë小號噸$$$$

(13)

等式中，如果實現得到的值為最大值，則比較百分比在x = 0行，後面的值在該行上方的正值集合中。此定義用於 Fairness 和 Efficiency。同樣，在公式中，當得到的值是最小值時，比較百分比在行x = 0。這個定義用於距離和堵塞。在這兩種情況下，百分比越大，結果離最佳值越遠，並且應該解釋為，例如，值 X 比最佳值差 30%。

6.2. 控制方案結果

6.2.1. N輛

在這個場景中，10、20、30、40、50、60、70、80、90 和 100 輛車沿著車輛網路移動，以隨著車輛數量的增加檢查每個指標。車輛同時進入一個空的網路，當集合中的所有車輛都到達目標節點時模擬停止，這意味著在最後的模擬步驟之後網路是空的。

(a) 效率和距離

結果對應於在模擬過程中，通過的 N 輛車的總集合的平均值（即，10 輛車、20 輛車等的平均效率/總行程距離）。圖 20 中的行為代表獲得的效率和行程距離，而圖 21 中的最佳值比較代表第 6.1.2 節中所述的比較百分比。

圖 20. N 車輛場景中路線效率和行程距離的行為。( a ) 每個 N 車輛集的平均效率值；( b ) 每個 N 車輛集的平均距離值。

圖 21. N 車輛場景中路線效率和行程距離的最佳值比較。( a ) 與獲得的最佳效率值的百分比比較；( b ) 與行程距離的最佳值的百分比比較。

該模擬關於效率和距離行為的主要結論是：

—— 

隨著網絡中車輛數量的增加，所有實現中的路線效率都會降低。

——

 行程距離受網路中車輛數量的影響，並且隨著車輛數量的增加而增加，即使對於 MD 解決方案也是如此。

—— 

即使效率水平始終在 0.8 和 1 之間並且結果的可變性不是很大，GC 的結果也比其他實現更好，其次是 LC。

——

 另一方面，該實施具有車輛中最大的平均行程距離之一，這意味著它在行駛距離和路線效率之間存在權衡。

Natural和 MD 實現的行為，僅因行程距離而異。在效率的情況下，這兩者表現相似。

圖 22. 在每個實現的每個 N 車輛集的狀態 k 中獲得的公平性。( a ) 使用自然行為算法為每個 N 車輛獲得的公平性；( b ) 使用局部堵塞算法為每個 N 車輛獲得的公平性；( c ) 使用全局堵塞算法為每個 N 車輛獲得的公平性；( d ) 使用 Modified Dijkstra 算法為每個 N 車輛獲得的公平性。

(b) 公平和堵塞

結果對應於在模擬的狀態 k 中獲得的公平性和堵塞值。由於評估的 N 輛汽車的數量不同（10 到 100 輛），模擬可能有更多或更少的狀態，因此它顯示了所有評估的 N 輛汽車的結果，這些結果顯示在每個實施的不同圖表中。圖 22顯示了每個實現的公平性行為，圖 23顯示了每個實現的每個 N 車輛通過的平均堵塞行為。

該模擬關於公平和堵塞行為的主要結論是：

——

公平行為和堵塞行為非常相似：當達到街道的最大容量時，街道變得飽和，導致高堵塞水平，這意味著街道的使用百分比非常相似。

——

當堵塞程度不高時，GC 和 LC 實現的公平性最高，這意味著在這些情況下街道得到了更好的利用。此外，這些實施在效率方面獲得了最佳值，表明每輛車的出行效率與街道使用平衡之間存在關係。

圖 23. 使用每個實現為每個 N 車輛集獲得狀態 k 中的平均擁堵。（一）平均。使用自然行為算法為每個 N 車輛獲得的擁堵；( b ) 平均。使用本地擁塞算法對每個 N 車輛進行擁塞；( c ) 平均。使用全局擁塞算法對每個 N 車輛進行擁塞；( d ) 平均。使用 Modified Dijkstra 算法對每個 N 車輛進行擁塞。

6.2.2. F 車輛

在這種情況下，在每個模擬（k 狀態）中，固定數量 F 的車輛被合併到車輛網路中。車輛進入一個空的網路，當 N 輛車輛到達目的地節點時，模擬停止。這意味著與 N 輛車的模擬場景相比，在最後的模擬步驟之後，網絡中將有車輛。在呈現的結果中沒有考慮距離的最佳值比較。

(a) 效率和距離

結果對應於每組 5 輛車的平均值，在模擬期間通過的總共 N 輛車中的 100 輛車的樣本中。此外，每個指標都是獨立呈現的，並包含每個選定F的結果。圖 24表示獲得的效率，圖 25表示獲得的行程距離。圖 26表示效率的最佳值比較。

圖 24. F 車輛場景中的路線效率行為。( a ) 當 F 為 10 時，每組 5 輛車的平均效率值；( b ) 當 F 為 20 時，每組 5 輛車的平均效率值；( c ) 當 F 為 30 時，每組 5 輛車的平均效率值；( d ) 當 F 為 40 時，每 5 輛車的平均效率值。

圖 25. F 車輛場景中行程距離的行為。( a ) F 為 10 時設定的每 5 輛車的平均行程距離值；( b ) F 為 20 時設定的每 5 輛車的平均行程距離值；( c ) F 為 10 時設定的每 5 輛車的平均行程距離值；( d ) F 為 20 時設定的每 5 輛車的平均行程距離值。

圖 26. F 車輛場景中效率的最佳值比較。( a ) 當 F 為 10 時，與每 5 輛車組獲得的最佳效率值的百分比比較；( b ) 當 F 為 20 時，與每 5 輛車組獲得的最佳效率值的百分比比較；( c ) 當 F 為 30 時，與每 5 輛車組的效率最佳值的百分比比較；( d ) 當 F 為 40 時，與每 5 輛車組的效率最佳值的百分比比較。

該模擬關於效率行為的主要結論是：

——

隨著車輛數量 F 的增加，重複之前模擬中效率的模擬結果：所有實現中的路線效率隨著網路中的車輛集合達到飽和值而降低，實際上，對於 F = 30 和 F = 40 實現中的效率值之間沒有很大差異。

——

此外，即使效率值相似，GC 也有更好的結果。相反，此實現具有最差的行程距離值之一。

——

行程距離再次與效率相關，與效率行為相比，顯示出類似的增加/減少行為。

(b) 公平和擁塞

公平性和擁塞的結果對應於車輛網絡中的總狀態樣本，並以每個 F 的不同圖形表示。得到的結果如下圖：

結果對應於在模擬中的狀態樣本的狀態 k 中獲得的公平性和擁塞值。圖 27和圖 28顯示了公平性和擁塞的行為，即為狀態 k 獲得的值，其中 k 是每個 F 所選模擬的 10 個中間狀態之一。這 10 個狀態以均勻分佈隨機選擇，以嘗試表示車輛網路的初始、中間和最終狀態。

圖 27. 在狀態 k 中為每個 F 車輛值獲得的公平性。( a ) 當 F 為 10 時，在狀態 k 下獲得的公平性；( b ) 當 F 為 20 時，在狀態 k 下獲得的公平性；( c ) 當 F 為 30 時，在狀態 k 下獲得的公平性；( d ) 當 F 為 40 時，在狀態 k 中獲得的公平性。

圖 28. 對於每個 F 車輛值，在狀態 k 下獲得的平均堵塞情況。（一）平均。當 F 為 10 時在狀態 k 下獲得的堵塞；( b ) 平均。當 F 為 20 時，在狀態 k 下獲得的堵塞；( c ) 平均。當 F 為 30 時在狀態 k 下獲得的堵塞；( d ) 平均。當 F 為 40 時，在狀態 k 下獲得的堵塞。

該模擬關於公平和堵塞行為的主要結論是：

——

與之前的模擬一樣，GC 和 LC 公平性在網路的低堵塞情形下，比 Normal 和  SMD 好得多，而在高堵塞情形下，公平性幾乎相同。此外，公平性和路由效率之間存在關係。

6.3. 參考情景結果

在這個模擬中，在每個模擬步驟中，隨機數量 F 的車輛被合併到車輛網路中。這個數字在區間 [90, 600] 中，其中 90 是入口街道集（與原點連接的街道）的平均容量。車輛進入一個空的網路，當 N 輛車輛到達目的地節點時，模擬停止。圖 29和圖 30 中的結果，對應於每組 50 輛車的平均值，在完成行程的總共 N 輛車中的 1000 輛車的樣本中。圖 29顯示了獲得的效率，圖 30顯示了效率和行程距離的最佳值比較。此外，圖 31 中的結果對應於公平和堵塞的行為，即為狀態 k 獲得的值，其中 k 是模擬的 10 個中間狀態之一。以均勻分佈隨機選擇的 10 個狀態嘗試，表示車輛網路的初始、中間和最終狀態 獲得的結果如下所示：

圖 29. 路線效率和行程距離的行為。( a ) 100 輛汽車樣本中每 50 輛汽車的平均效率值；( b ) 100 輛車樣本中每 50 輛車的平均行程距離值。

圖 30. 效率和行程距離的最佳值比較。( a ) 與獲得的最佳效率值的百分比比較；( b ) 與行程距離的最佳值的百分比比較。

圖 31. 公平和堵塞的行為。( a ) 在狀態 k 中獲得的公平性；( b ) 平均。在狀態 k 中獲得的堵塞。

如我們所見，對於每輛車的來源和目的地，以及在模擬步驟中進入網路的車輛流量都是隨機的模擬，控制場景的結果被複製。

——

可以理解，對於 GC，在其他實現中，效率更穩定，結果最好。儘管如此，我們可以再次看到，提供更好效率的 GC 實現是距離更大的實現之一，通常與 DT 的距離更好。

——

此外，模擬中的平均堵塞不是很大，實現的公平值非常相似，但是，當堵塞級別不超過限制時，GC 具有更好的公平性。

——

對於 Normal 實現，效率值較低（與最佳值相比最多差 60%–70%）並且距離不是最好的，因此該實現與其他實現相比確實沒有任何優勢。

7. 結論

物聯網允許以這樣的方式整合元素，從而可以以新的方式解決舊問題，特別是在需要處理不斷變化的環境成為優先事項的情況下。事實證明，車輛堵塞問題成為一個挑戰，提供一種能夠處理該參數的高動態性的機制，不斷改變車輛網路的全局狀態，這種新範式可以得到支持。

開發了一種基於通信 V2I 的路由機制，其中節點能夠與車輛交互，並將其與其他方法進行比較，即基於最短路徑距離的啟發式方法、僅了解局部參數的方法，以及基於該路由不依賴於任何支持通信。顯示的結果證明：（1）決策不僅應了解堵塞狀態，並對其採取反應方式，而且應以在每個時刻實現較低的堵塞為導向；(2)局部堵塞狀態資訊，不足以實現車輛行駛的最優效率和更好的結果，因此需要將全局資訊，傳達給每個元素，以便做出適當的決策；

在不同特徵的場景中，所提出的解決方案在效率和公平性方面，都具有最佳性能。因此，它是一種更強大的解決方案，並且在實際環境中，應用它很可能會在車輛所走的路線中產生好處。此外，公平和效率之間顯示的關係，以及通過所提出的解決方案，獲得的前者的更高結果，意味著車輛正在以更有效的方式，使用車輛基礎設施。這就是為什麼在未來的工作中，開發 V2I 和 V2V 通信機制的原因，該機制允許對堵塞進行全局優化，而不是針對車輛的個別行程，而是針對整個車輛網路。

AKD 寰楚專業級全系列監控設備 

按此回今日3S Market新聞首頁