[發明專利]一種基于并行元胞自動機的城市演變模擬實現方法

無效

• 申請號: 200810219880.6
• 申請日: 2008-12-12
• 公開（公告）號: CN101436204A
• 公開（公告）日: 2009-05-20
• 發明（設計）人: 黎夏;伍少坤;劉濤;劉小平;張嘯虎
• 申請（專利權）人: 中山大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/00
• 代理公司: 廣州粵高專利代理有限公司
• 代理人: 禹小明

技術領域

本發明屬于利用元胞自動機進行大區域城市群土地利用演變的模擬技術領域。

技術背景

元胞自動機(Cellular?Automata，簡稱CA)模型是由Ulam和Von?Neumann于20世紀40年代提出的時間、空間、狀態都離散，(空間的)相互作用及(時間上)因果關系皆局部的網格動力學模型。不同于一般的動力學模型，CA模型沒有明確的方程形式，而是包含了一系列模型構造的規則。許多地理現象都屬于復雜系統，無法利用數學公式對它們進行表達和模擬。研究結果表明，CA模型是對城市復雜系統進行微觀模擬的有效手段。近年來，CA已經被較多地應用于地理現象的模擬中，特別用于城市土地利用變化模擬中，即城市CA。

城市CA是一種“自下而上”的微觀模擬系統，模型中有大量的微觀個體(元胞)，微觀元胞之間的交互作用，是一系列的嵌套循環過程，導致其計算量非常龐大。并且，城市CA的計算量與研究區域的范圍及空間數據的分辨率有很大的關系，隨著研究區域范圍的擴大和空間分辨率的提高，其計算量呈指數級增長。此外，地理空間系統是一個由多要素共同作用的，自然、社會和經濟復合的、整體開放的復雜巨系統，城市CA作為其模擬的工具，涉及到大量的運算，這些模型和計算需要相互協作才能共同完成任務。地理現象的時空動態模擬涉及到大量數據的輸入，譬如，土地利用數據、地形數據、政府規劃數據、交通數據、社會經濟數據、人口數據等。目前城市CA模擬基本上采用的都是在單個計算機上進行處理的辦法，而上述原因導致城市CA模擬往往耗時過長，且無法勝任大范圍的城市群模擬的任務，大大限制了城市CA在實際工作中的應用，而該方面的研究在國際上至今未有有效的解決方案，在國內仍為一片空白。

發明內容

本發明的目的在于克服現有技術的不足，提出了并行式運算的城市CA，通過網絡互聯的計算機聯合運算，解決城市CA速度瓶頸的問題，達到高效能空間計算的目標。

為了實現上述發明目的，采用的技術方案如下：

一種基于并行元胞自動機的城市演變模擬實現方法，采用元胞自動機對城市的地理現象進行模擬，其發明點在于將元胞空間分解成多個子域，再將每個子域分發到每個分布式的處理器上進行處理，最后將所有處理器的運算結果合并成最終的模擬結果。

上述技術方案中，所述元胞空間建立在二維矩陣的空間上，元胞空間按行分解或按列分解成多個子域。

每一個子域包括一個或者多個相鄰子域的邊界層，子域設有邊界緩器用來接受和發送數據給近鄰子域。

所述子域分發到處理器上通過網絡傳輸實現。

所述網絡傳輸采用網絡文件系統實現數據的共享和分發。

本發明采用消息模型為子域之間進行通訊。

進一步的，通過消息傳遞接口實現子域之間的通訊。

每個處理器在對子域進行計算的每次迭代后僅傳輸變化的數據以減少網絡的開銷。

本發明將并行處理技術應用于城市CA中，實驗結果表明，該技術能夠顯著提高城市CA的模擬速度，達到預期的高效能空間計算目標。與普通的CA模擬實現相比，具有如下的優勢：

1、并行城市CA通過局域網互聯的集群系統進行并行計算，顯著提高了模擬速度，使得以往耗時極長的模擬實驗能夠在較短的時間內完成，為研究者節約大量時間，也提供了更大的靈活性，使他們能夠集中精力在模型建立、規則定義和參數校正上；

2、比串行城市CA更能勝任大范圍區域的高精度模擬，它能夠突破單機的內存限制，使系統更加穩定；

3、不需要運行在超級計算機上，能夠運行在筆記本、普通PC、工作站和服務器上，這樣一是充分利用各種閑置的資源，二是大大節約了硬件設備成本，促使并行CA投入實際使用。

附圖說明

圖1是影元胞技術實現示意圖；

圖2是元胞空間的域分解方式示意圖，其中(a)為按行分解，(b)為按列分解；

圖3為并行城市CA模型框架；

圖4為結果示意圖，其中(a)為并行城市CA的運算時長，(b)為加速比，(c)為效率。

具體實施方式