基于物聯(lián)技術(shù)的交叉口流量實時管理

曹春勤

（上海電科智能系統(tǒng)股份有限公司，上海 200063）

1 概述

交通擁堵是當(dāng)前社會較為關(guān)注的話題，一些城市花費(fèi)極大人力物力改善交通，但收效甚微，甚至適得其反。道路擁堵問題不但影響民眾通行效率，大量的尾氣排放也嚴(yán)重影響著城市居民的生活環(huán)境。近年來隨著智能交通行業(yè)的發(fā)展，最新的信息技術(shù)被應(yīng)用到交通基礎(chǔ)設(shè)施以及管理手段。其中無線通訊技術(shù)發(fā)展較為迅速，無線網(wǎng)通過無線電波、微波等媒介將各網(wǎng)點(diǎn)連接，并實時傳輸數(shù)據(jù)。車載自組網(wǎng)（VANET）是無線通訊技術(shù)在交通領(lǐng)域的一大應(yīng)用，利用無線通信技術(shù)，以移動中的車輛及交通設(shè)施為節(jié)點(diǎn)，形成移動網(wǎng)絡(luò)[1]。加入這個網(wǎng)絡(luò)的車輛，會成為一個無線節(jié)點(diǎn)或是無線路由。當(dāng)某個車輛脫離了信號范圍，其它的車輛可以加入，彼此鏈接，創(chuàng)建起新的移動互聯(lián)網(wǎng)。車載自組網(wǎng)技術(shù)也被認(rèn)為是下一代智能交通領(lǐng)域的關(guān)鍵技術(shù)[2]。

1.1 問題定義

交叉口流量控制是智能交通領(lǐng)域的難題之一，不但由于交叉口分布復(fù)雜，形態(tài)各異，還因為交叉口不同方向的車流同時匯聚于此。此外交叉口還有大量行人通過，現(xiàn)有路口信號控制系統(tǒng)有不少缺陷，尤其高流量的交叉口堵塞，大量排隊車輛滯留在進(jìn)口處。因此，路口交通控制對道路管理至關(guān)重要，是提升交通流通性和安全性的關(guān)鍵。

1.2 研究目的

當(dāng)前信號配時優(yōu)化是解決道路交叉口問題的重要手段，但由于算法的復(fù)雜性有時并不貼合管理實際。隨著車聯(lián)網(wǎng)技術(shù)的快速發(fā)展，車與車通信（V2V）、車與道路基礎(chǔ)設(shè)施通信（V2I）、車與行人通信（V2P）已不是難事，同時更高速、更安全的通訊制式也不斷適應(yīng)車聯(lián)網(wǎng)應(yīng)用場景[3]。

基于當(dāng)前車聯(lián)網(wǎng)技術(shù)的發(fā)展，為提升道路交叉口車輛及行人的通行效率和安全性，本文提出一種新式模型，受進(jìn)程同步理論啟發(fā)，將車輛和行人看作進(jìn)入交叉口臨界面的一個過程，如何在高流量下且所有對象處于競爭條件下減少等待時間，將是本文對交通流控制研究的關(guān)鍵。此外，當(dāng)出現(xiàn)大量車輛時系統(tǒng)可能會陷入等候死循環(huán)，從而導(dǎo)致交叉口擁堵，本文也提出一種有效的方式應(yīng)對此問題。

1.3 本文貢獻(xiàn)及結(jié)構(gòu)

本文的主要貢獻(xiàn)包括：（1）提出一種實時控制動態(tài)交通流的方法；（2）未使用優(yōu)化算法因此具有更低的計算復(fù)雜度；（3）交叉口管理系統(tǒng)采用無線通訊方式，實際部署時更具靈活性；（4）仿真結(jié)果表明本方法能有效提升交通流量并縮短等候時長。

圖1 交叉口和進(jìn)口道

各章節(jié)內(nèi)容：第二章主要介紹進(jìn)程同步理論在本文的應(yīng)用并構(gòu)建仿真模型。第三章搭建交叉口對象交互結(jié)構(gòu)并提出系統(tǒng)算法，解決各對象同路口控制系統(tǒng)協(xié)調(diào)問題。第四章通過仿真對模型進(jìn)行驗證，第五章對本文進(jìn)行了總結(jié)。

2 背景

當(dāng)前有很多處理交叉口擁堵的方法，信號控制是最為傳統(tǒng)的方法，較先進(jìn)的信號控制技術(shù)通過動態(tài)自適應(yīng)信號控制協(xié)調(diào)各方向的流量壓力，主要采用的方式是最優(yōu)化算法。其中陳曉峰[4]提出利用遺傳算法解決交叉口問題，Srinivasan 利用神經(jīng)網(wǎng)路解決實時性問題，主要通過信號配飾優(yōu)化解決問題[5]，這些方法能在一定程度解決問題，但由于計算復(fù)雜度過高而不利于實際應(yīng)用。吳維[6]提出一種基于互斥算法的方式解決動態(tài)信號控制問題，但在高交通流壓力下系統(tǒng)仍會面臨高復(fù)雜性計算問題。隨著物聯(lián)網(wǎng)的發(fā)展，許多研究也在朝著無線感知聯(lián)網(wǎng)技術(shù)靠近，但大量的傳感設(shè)施建設(shè)也會帶來能耗問題。因此，車載自組網(wǎng)技術(shù)能有效解決這一問題。Bento et al.提出一種基于車載自組網(wǎng)技術(shù)的智能信號控制方式[7]，Jabbarpour 等人研究了車流密度和速度如何影響車載自組網(wǎng)中基于位置的路由協(xié)議，通過這種方式各車輛收到信號從而避免擁堵[8]，但所有車輛只能在很短的距離內(nèi)交互。物聯(lián)網(wǎng)技術(shù)的興起能在很大程度解決此問題，不但能提升信息交互速率同時增加傳輸距離。本文主要討論如何基于物聯(lián)技術(shù)改善交叉口交通流量問題，提出一個假定十字交叉口，有東南西北（E、S、W、N）四個方向，每個方向上有兩條進(jìn)口車道，分別是直行（F）和左轉(zhuǎn)（L），還有一條行人過街道（PF）。由于右轉(zhuǎn)車道不會形成沖突因此本文暫不論及。本文對車輛和行人做統(tǒng)一考慮，一個交叉路口總共有以下12 種對象狀態(tài)。見圖1。

表1 和表2 顯示了交叉口中各方向車道與行人道間的沖突關(guān)系，“x”代表兩方向存在沖突，空白代表不存在沖突。

表1 各方向車道間沖突關(guān)系

表2 各方向車道與行人間沖突關(guān)系

在計算機(jī)科學(xué)領(lǐng)域中，進(jìn)程同步理論是較為常用的理論，是指多道程序環(huán)境下，進(jìn)程并發(fā)執(zhí)行，不同進(jìn)程間存在著不同的相互制約關(guān)系。為了協(xié)調(diào)進(jìn)程之間的相互制約關(guān)系，達(dá)到資源共享和進(jìn)程協(xié)作，避免進(jìn)程之間的沖突，引入進(jìn)程同步的概念[9]。圖2 表達(dá)了進(jìn)程間通信的原理，如有兩個進(jìn)程需要進(jìn)行通信，需通過兩種機(jī)制，分別是發(fā)送send(message)和接收receive(message)，通信完成時，進(jìn)程間的連接將被切斷。

圖2 進(jìn)程間通信：消息傳送

本文探討基于物聯(lián)網(wǎng)技術(shù)的交叉口車流量控制，當(dāng)一輛車或一個行人到達(dá)交叉口時，車或行人發(fā)送信號請求通過，系統(tǒng)實時分析交叉口路況決定允許通過時間。由于考慮到通信數(shù)據(jù)實時性的問題，本文只討論基于本地?zé)o線聯(lián)網(wǎng)的車輛及行人之間的通信。

3 進(jìn)程同步算法

3.1 交叉口對象連接架構(gòu)

車聯(lián)網(wǎng)系統(tǒng)中車輛識別基于每輛車的ID（車牌）以及車輛的高精度定位，行人可通過手機(jī)端接收信號，因此系統(tǒng)可檢測到每個進(jìn)入交叉口的對象的行進(jìn)方向以及時間。圖3 表示交叉口各對象間的通信架構(gòu)。

圖3 交叉口各對象間通信架構(gòu)

每個方向的傳感設(shè)備可檢測進(jìn)入?yún)^(qū)域內(nèi)的車輛和行人，交通信號燈和行人信號燈顯示為變量（紅燈和綠燈）。無線網(wǎng)基站提供對象間的無線通訊，假定此設(shè)備傳送范圍能夠覆蓋整個區(qū)域。

圖4 表示了交叉口內(nèi)車輛和行人與系統(tǒng)的交互方式，當(dāng)一個對象來到交叉口后，需要發(fā)送請求信息至控制單元，根據(jù)實時狀況，控制單元向請求對象回復(fù)允許通過信號或?qū)⑵浞湃肱抨犆麊?，等待回?fù)信號。當(dāng)車輛或行人通過交叉口后，需要向控制單元回復(fù)完成信號。

3.2 進(jìn)程同步算法

算法1 體現(xiàn)了車輛和行人與交叉口控制單元的交互方式，當(dāng)對象i 進(jìn)入交叉口區(qū)域時，將向控制單元發(fā)送通過請求，信息內(nèi)容包含對象編號id 和道路名稱li，等待控制單元回復(fù)消息，圖5。當(dāng)控制單元收到對象i 的訊息后，將分析交叉口交通流量（算法2），檢測是否有行人或車在沖突方向運(yùn)動，當(dāng)交叉口出現(xiàn)堵塞情況，對象i 會被列入等候名單Pl 不允許i 通過（算法3）。其它情況會允許i 通過[10-11]，圖6。

當(dāng)車輛離開交叉口后，必須發(fā)送信息告知控制器，控制器檢查等候名單，并告知下一對象，整個過程控制器按照先進(jìn)先出模型進(jìn)行處理。

圖4 交叉口對象間信息傳送方式

圖5 算法1

圖6 算法2

3.3 循環(huán)等候解決算法

當(dāng)交通流迅速增多時，可能出現(xiàn)多輛車互相等候的狀況，造成死循環(huán)堵塞[12]，示意圖見圖7。現(xiàn)有交通控制系統(tǒng)沒有將此情況納入考慮范圍，因為此情況出現(xiàn)概率較小。在本文討論的車聯(lián)網(wǎng)情形中，系統(tǒng)能實時檢測車輛的實時位置和到達(dá)時間，并通過Floyd 判圈算法在車輛通過交叉口時判斷死循環(huán)會否發(fā)生。

圖7 死循環(huán)舉例

圖8 算法3

死循環(huán)檢測算法步驟：（1）轉(zhuǎn)化為Floyd 判圈算法G(N,E)，將各車輛當(dāng)作點(diǎn)，從i 車到j(luò) 車的邊表示i 等待j 的空間；（2）利用判圈算法找到有向圖中的圈；（3）若結(jié)果是true 則存在死循環(huán)，相反則車輛可通過交叉口。此算法的復(fù)雜度為O(n2)，n 代表此刻區(qū)域內(nèi)的車輛數(shù)，圖8。

3.4 期望輸出

本文的目的是通過進(jìn)程同步方法在大流量交通情形下提升交叉口的通過率并減少等待時間，主要通過在一定的時間內(nèi)交叉口通行的車輛數(shù)以及等待時間來判斷系統(tǒng)有效性。對象i 的通過時間可按如下公式計算：

4 算法驗證

本章引入循環(huán)調(diào)度算法，并通過Netlogo 仿真軟件進(jìn)行對比，表3 是設(shè)定的模擬參數(shù)。

表3 模擬參數(shù)

圖9 和圖10 表示經(jīng)過10 次模擬的車輛和行人到達(dá)交叉口的數(shù)量分布情況（按升序）。

圖11 是循環(huán)調(diào)度算法和進(jìn)程同步算法兩種算法在相同時間條件下（1000 ticks）交叉口通行車輛數(shù)比較，可以看到本文算法更優(yōu)，因為基于動態(tài)交通流控制，車輛在沒有沖突的情況下即可通過交叉口，極大程度上減少了等候時間。圖12 體現(xiàn)了兩種算法得出的最大和最小等候時長對比，等候時長通常隨交通流密度的增大而增長，但本文所使用的方法呈現(xiàn)的變化卻不明顯，原因是本文的處理機(jī)制遵循先進(jìn)先出原則，車輛能夠盡快通過交叉口。圖13 顯示了平均等候時間。

圖14 和圖15 顯示了隨著行人密度的增長，兩種不同算法對交通流量控制的比較，顯然進(jìn)程同步法更優(yōu)于循環(huán)調(diào)度算法。從平均等候時間角度看，通常等候時間同流量成正比，但通過本文算法得出的結(jié)果可看到等候時間隨流量增加并無明顯變化，原因同前文。

5 結(jié)論

圖9 車輛數(shù)隨機(jī)分布情況

圖10 行人數(shù)隨機(jī)分布情況

圖11 一定時間段內(nèi)的通行車數(shù)

本文提出利用物聯(lián)網(wǎng)技術(shù)實時獲取道路對象信息并對流量進(jìn)行實時控制，然而實際情況中可能需要大量多種類的物聯(lián)設(shè)施實現(xiàn)多個交叉口的聯(lián)動，此外本文尚未考慮其他形態(tài)交叉路口，以及緊急車輛的通行問題。未來仍有許多工作可進(jìn)行研究。

本文提出一種基于進(jìn)程同步理論的交通流實時管控手段，當(dāng)車輛或行人進(jìn)入路口時，能實時與系統(tǒng)進(jìn)行交互，極大節(jié)省了等候時間，提升了通行效率。此外，本文還提出一種新式避免等候死循環(huán)的算法，結(jié)果證明能較大程度減少對象等候時長。

圖12 最大和最小等候時長

圖13 平均等候時長

圖14 一定時間段內(nèi)的車輛和行人通行數(shù)

圖15 車輛和行人平均等候時長