分布式并行計算在交通網絡仿真中的應用

摘要：根據交通網絡仿真的并行特征采用域分解方法設計交通并行仿真系統的框架，把交通網絡分為幾個子網，集群系統的每個節點機分別負責其中的一個子網，提出基于車輛數負載的網絡分割算法來平衡各子網的負載量，并分析子網之間的通信機理。同時，在基于MPI 的并行計算平臺上實現設計的并行仿真系統。通過實例表明，提出的并行算法能大大提高交通網絡仿真的速度和效率。

關鍵詞：交通網絡仿真；分布式并行計算；域分解；網絡分割算法

中圖分類號：TP391．9文獻標志碼：A

文章編號：1001－3695(2007)08－0251－04

近幾年，并行計算在許多領域得到了廣泛應用，如量子化學、天體物理學、氣象學等。由于許多科學問題非常復雜，需要功能強大的計算機進行并行處理，并行計算的應用為其計算性能的改善帶來了益處。微觀交通網絡仿真是對路網上每一個車輛實體的復雜運行行為進行仿真。如果網絡規模較大，仿真計算就需要消耗更多的時間和計算資源，單處理器的PC機已經不能滿足計算能力的需求，交通網絡仿真的速度會越來越低。由于大型并行計算機的成本高，難以普及，而分布式集群系統具有自治性、并行性、擴展性、模塊化、成本低等優點，同樣可以加快仿真速度和計算效率。分布式并行計算在交通網絡仿真中的應用成為提高仿真速度和效率、滿足交通管理與控制實時性需要的有效方法。

交通網絡仿真的并行實現是一個相對較新的研究領域。自20世紀90年代以來，隨著計算機科學的迅猛發展，美國、英國、德國等發達國家的一些學術科研機構一直嘗試著利用大型并行計算機對大規模道路網進行并行仿真研究，并取得了一些理論和實踐成果。美國的Transims交通仿真軟件應用元胞自動機模型開發了并行仿真版本。英國的Quadstone公司和加拿大的Softimage公司合作應用并行計算理論，在大規模并行計算機上開發出了Paramics仿真軟件，并在智能運輸系統的實施中得到了應用。德國的PTV Vision公司與西門子公司合作開發VISUMOnline的并行仿真系統。目前大多數文獻中，應用專用并行機進行并行仿真的較多，而采用分布式集群系統進行并行仿真的較少。本文采用分布式并行計算技術進行交通網絡仿真[1，2]。

1分布式并行交通網絡仿真系統結構

1．1交通網絡仿真的并行特征

交通系統狀態的變化是由多個在同一時刻或同一時間間隔發生的若干個事件引起的，具有并行性和并發性，是并行離散事件系統。在任何時刻，道路網絡上一個區域的交通狀態變化不會立即影響其他區域的交通。例如，在一條路段上行駛的車輛的運行行為不會立即影響到另一條路段上的車輛。這種時間和空間上的獨立性允許交通仿真系統的并行化。另外，在實際交通系統中主要包括三個部分，即交通路網、網絡控制和車輛。其中的大多數活動，如車輛運動或信號燈運行實質上都是并行的。因此，交通系統中的很多實體都可以同時仿真。

1．2分布式并行仿真系統結構

根據交通網絡仿真的并行特征和不同仿真區域計算相關性不強的特點，采用域分解的任務劃分方法，把計算任務分為等量的幾部分，然后分別由集群系統中的PC機進行仿真計算，最后匯總輸出仿真結果。在仿真過程中，部分車輛由于目的地不同會從一個區域進入另一個區域。這時就需要交換相鄰區域邊界處的交通流信息，以保持不同區域仿真的一致性。

在仿真過程中，并行程序采用主從式方法把計算任務均勻地分配到集群工作站的各個節點機上。主進程負責全局調度控制、派生從進程、路網劃分、流量分配、給從進程分配任務和仿真結果匯總。從進程負責各個區域的仿真計算。主從式并行仿真結構如圖1所示。

分布式并行交通網絡仿真的基本思想如下：首先由主從進程分別從SQL數據庫中讀取整個路網數據，進行網絡分割，指定每個從進程負責的交叉口和路段；然后從進程開始在各自負責的那一塊子網中進行微觀車輛運行仿真，每一步長結束時，都將更新的車輛數據及信號燈數據發送給主進程；再由主進程發送到前臺可視化操作界面進行動畫顯示，同時統計匯總整個網絡的運行指標。當車輛穿越子網邊界時兩個進程需要進行消息傳遞交換車輛信息和邊界區域信息；在每個仿真時間步長內，都要進行一次時鐘同步。交通網絡仿真系統主要由輸入模塊、網絡控制模塊和微觀仿真模塊組成。微觀仿真模塊又由車輛產生、車輛狀態更新和車輛位置更新三個子模塊組成。隨著仿真系統時鐘的推進，這三個子模塊共同完成路網上車輛的加載過程。同時，在微觀交通仿真過程中，網絡控制模塊同步執行。

根據分布式并行交通網絡仿真思想設計系統結構如圖2所示。

在并行仿真環境下，不同區域之間的信息交換有兩種方法，即共享地址空間和消息傳遞。在共享存儲空間方法中，所有的處理器共享同一個存儲空間，程序變量均存于此存儲空間中，處理器間的通信通過讀寫共享存儲空間的同一變量來實現，但每次只能有一個處理器對存儲空間進行訪問。因此，隨著處理器數的增多，存儲空間的帶寬會成為并行仿真的瓶頸。在消息傳遞方法中，每個處理器都有自己獨立的存儲空間來保存變量和數據；處理器間彼此通過發送消息來交換信息；處理器間的數據傳輸要求雙方協作完成。因此，該方法不受處理器規模的限制，能提高大規模并行仿真的速度和效率[3]。

MPI是目前最重要的一個基于消息傳遞的并行編程工具。它具有移植性好、功能強大、效率高等優點，而且有多種不同的免費、高效、實用的實現版本，幾乎所有的并行計算機廠商都提供對它的支持。這是其他所有的并行編程環境都無法比擬的。MPI為大規模高性能并行機和工作站集群的程序設計提供了更加豐富、更為高效的通信函數，也支持Fortran和C/C++語言編程。MPI支持多種通信模式，提供了緩沖區管理函數，實現了完全的異步通信，提供了可靠的數據傳輸機制，發送的信息總能被對方正確接收，而用戶不必檢查錯誤信息。MPI具有豐富的數據類型，包括通過派生數據類型來定義由類型不同且空間不連續的數據元素構成的數據類型[4]。此外，MPI還提供非常豐富的集群通信函數。鑒于MPI強大的通信功能，本文采用MPI作為并行編程平臺，在Linux操作系統下以C++程序設計語言編制交通網絡仿真并行程序。

2網絡分割方法

在并行交通網絡仿真中，為了使各處理器負載均衡和最小化通信開銷，網絡分割是至關重要的一步。根據網絡拓撲結構把交通網絡分成幾個大致相同的子網，每個處理器負責一個子網的交通流仿真，然后通過各個子網之間的通信交換車輛數據和信息，從而完成整個交通網絡的并行仿真。為了將路網中交叉口的交通流復雜性與并行化后產生的復雜性分割開來，路網分割時將分割點設在路段中間位置，這樣也更易于計算速度的優化。在具體實現中，被分割的路段在它所連接的兩個節點機中都保存有完整的表達數據。在仿真過程中，每個節點機分別負責處理一半路段。

網絡分割后，各個子網大致相同并不是說它們的區域面積相等，而是每個子網所承擔的計算量大致相等。由于交通網絡仿真是對路網上每一輛車運行行為和路徑選擇行為的仿真，而每一輛車的計算量都是相等的，每個子網的計算量就等于它所包含的車輛數。要使每個子網的計算量相等，達到負載均衡，也就意味著每個子網所包含的車輛數大致相等。本文提出基于車輛數負載的網絡分割算法來保證各處理器之間的負載均衡和最小化通信開銷。

2．1網絡分割算法的基本思想

為了減少交通行為的復雜性和通信開銷，把交叉口作為并行仿真的基本單位。每個交叉口包括出入路口所有路段的一半。其計算量等于它所包含的交叉口內和路段上的所有車輛數。根據交通網絡的全部計算量和要劃分的進程數，把網絡分割成等量的幾部分，每個進程負責其中的一部分。分割位置盡量在交通量小的路段上，以減少通信開銷。交叉口是最小的并行計算單元，即每個交叉口中的車輛要分在同一個子網上。另外，同一子網上的交叉口應盡量相互鄰接，以減少子網間的通信開銷。初始分割路網時，由于沒有加載交通量，把交叉口數作為計算負載進行子網劃分。每個進程分配的交叉口數大致相當，每隔一定的時間間隔根據路網上的車輛數重新分割一次路網，以達到動態負載平衡。

首先定義網絡分割算法中所用到的符號，如下所示。

3消息傳遞機理

在并行計算環境中，處理器間的通信是以事件及消息的形式進行的。事件可以看做一個包含類型、地址、數據的信息包，一個或多個事件可以合并為一個消息。其中包含了消息類型及目標節點機。在交通網絡仿真過程中，當被分割路段上的車輛從一個子網進入到另一個子網時，此車輛的信息就需要從原節點機發送到負責車輛將要進入子網的那臺節點機。邊界處的數據通信主要包括以下四個部分：確定車輛將要進入的處理器；接收相鄰區域的車輛運行情況；根據車輛跟馳模型移動車輛位置；刪除車輛在原子網的信息，相鄰子網中增加該車輛的信息。

在數據通信過程中，當車輛從一個子網進入另一個子網時，需要同時更新邊界車輛的狀態，但是由于兩個子網分布在不同的處理器上，需要跨區計算，這時有可能會出現后進入車輛先更新，而前車后更新的情況。這就需要解決兩個子網之間數據時鐘同步的問題。

本文采用在兩個相鄰子網分割路段邊界處建立車輛緩沖區（路段中間位置左右各30 m）的方法來保持被分割路段信息在兩節點機上的一致性。在每個仿真步長內，每一個節點機都需要將各自負責的那一半路段距分割點30 m區域內每條車道離分割點最近的車輛信息發送到另一節點機。如果該區域內沒有車輛，則發送零消息給另一節點機。30 m區域是車輛產生相互影響的范圍。由于在跟馳模型中僅考慮同車道視野范圍內最近的前方車輛，在跨區計算時，只需將離分界線距離最近的車輛備份即可。

每個節點機上都保存有一個被分割路段的隊列結構和一個相應于被分割路段鄰接節點機的隊列結構。邊界信息交換必須在車輛狀態更新之前進行，每個節點機都需要在合適的時間進行消息傳遞的初始化工作，并等待接收從鄰接節點機發送來的邊界交換信息。

4并行仿真性能評價

4．1評價指標

并行仿真性能主要是通過計算復雜性來評價。計算復雜性表現為時間復雜性和空間復雜性兩個方面，并行仿真的目標是盡可能減少時間復雜性。通常這是通過增加空間復雜性來實現的，如增加空間的維數及增加處理器數。并行仿真的復雜性分析與串行程序的復雜性分析有很大差別，需要考慮的因素很多。測度指標主要包括工作量、執行時間、處理器數目、加速比、效率、可擴展性、粒度等。本文主要從程序執行時間、加速比、并行效率和可擴展性等四個指標來對并行算法的效益進行分析。

程序執行時間是算法評價的重要指標，而測試單機上的運行時間則是對并行效益分析中的加速比和效率指標進行評價的基礎及比較的依據。程序執行時間是指從第一個處理器開始執行并行計算的時間到最后一個停止運行的處理器停止執行的時間之差。它包括計算時間、I/O時間和通信時間。

從以上圖表可看出，隨著交通網絡規模的增大，并行仿真的速度比串行程序的速度有很大提高，系統具有很好的可擴展性。這為更大規模的交通網絡仿真和實時應用提供了有效途徑。

5結束語

本文闡述了分布式并行計算在交通網絡仿真中應用的必要性，建立了分布式并行仿真系統結構。為了保持各處理器間的負載均衡和最小化通信開銷，提出了基于車輛數負載的網絡分割算法。通過在分割路段上建立車輛緩沖區的方法使各處理器間進行信息交換并保持時鐘同步。最后通過在基于MPI并行試驗平臺上的實例應用來評價并行仿真的性能。

參考文獻：

［1］CETIN N，NAGEL K. Large scale transportation simulation on Beowulf Clusters [J].Transportation Research，2001（2）：1－25.

［2］LIU H X，MA Wenteng， JAYAKRISHNAN R. A distributed modeling framework for largescale microscopic traffic simulation[C]//Proc of the 84th Annual Meeting of the Transportation Research Board.Washington D.C:[s.n.]，2005:1－21.

［3］魏麗英.分布式微觀交通網絡模擬建模方法研究 [D] . 長春：吉林大學，2002.

［4］陳國良，安虹，陳崚，等. 并行算法實踐 [M]. 北京：高等教育出版社，2004.

［5］高林杰， 雋志才， 倪安寧. 微觀交通分布式并行仿真系統設計與效益分析 [J].公路交通科技，2006，23(4):94－98.

［6］交通網絡分布式并行模擬軟件系統研究與開發 [R].長春：吉林大學，2004.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”