曹春勤

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

1 概述

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

1.1 問(wèn)題定義

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

1.2 研究目的

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

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

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

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

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

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

2 背景

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

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

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

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

在計(jì)算機(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)程間通信的原理，如有兩個(gè)進(jìn)程需要進(jìn)行通信，需通過(guò)兩種機(jī)制，分別是發(fā)送send(message)和接收receive(message)，通信完成時(shí)，進(jìn)程間的連接將被切斷。

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

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

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

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

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

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

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

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

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

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

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

圖4 交叉口對(duì)象間信息傳送方式

圖5 算法1

圖6 算法2

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

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

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

圖8 算法3

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

3.4 期望輸出

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

4 算法驗(yàn)證

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

表3 模擬參數(shù)

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

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

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

5 結(jié)論

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

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

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

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

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

圖12 最大和最小等候時(shí)長(zhǎng)

圖13 平均等候時(shí)長(zhǎng)

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

圖15 車(chē)輛和行人平均等候時(shí)長(zhǎng)