[發明專利]一種基于柵格映射生長的交通網絡劃分方法及配置服務器

無效

• 申請號: 201210528128.6
• 申請日: 2012-12-10
• 公開（公告）號: CN103871234A
• 公開（公告）日: 2014-06-18
• 發明（設計）人: 陸平;董振江;秦旭彥;史其信;付強
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: G08G1/00
• 分類號: G08G1/00;G06F9/38;G06F9/50
• 代理公司: 北京派特恩知識產權代理有限公司 11270
• 代理人: 蔣雅潔;張穎玲

技術領域

本發明屬于智能交通領域，尤其涉及一種基于柵格映射生長的交通網絡劃分方法及負載分擔配置服務器。

背景技術

隨著智能交通系統的發展，動態路徑誘導、出行者信息服務、動態交通流組織等先進的管理手段和理念不斷發展，分析效率是實時分析和交通管理關心的問題。

在進行交通分析時需要將整個城市的交通網絡分拆為若干個部分，每個部分的運算由一個處理器負責，每個處理器只處理自己負責部分網絡的車輛情況。一個好并行執行系統應該使各個處理器的負載平衡，并且相互之間的數據傳遞盡可能少。

在現有的交通網絡劃分方案中，研究分為幾類：

1)基于分割的劃分方法。其劃分結果受初始結點選擇的影響很大，不能一次劃分就得到最終的劃分結果，有反復迭代的調整的過程。

2)基于合并的劃分方法。很多時候通過直接分割得到的分割結果不夠理想，而且執行效率也不高，就出現了合并的思路，不過合并通常也不能一次就得到最終的劃分結果，需要多次合并才行。

3)基于合并和分割的組合劃分方法。也存在上述反復迭代的調整的過程和多次合并的問題，精確度有所提高，但是執行復雜度高，劃分結果也不盡理想。

綜上所述，現有交通網絡劃分方案存在的問題是：1)無論哪種方案，都不能一次劃分就得到最終的劃分結果，需要反復迭代的調整及多層合并才能夠得到，因此，執行復雜度高。2)為了降低復雜度，使運算不要過于復雜，目前通常針對普通的矩陣情形，由于是有所選擇的，因此，在交通網絡劃分中的適用范圍不大。3)現有的交通網絡劃分方案中，由于劃分的精度不高，進行劃分運算的每個處理器的負載就不夠均衡，并行處理的效率不高，當執行復雜度高的情況下問題就更為明顯了。目前迫切需要一種執行復雜度低、精度高、負載均衡、并行處理效果高的解決方案。

發明內容

有鑒于此，本發明的主要目的在于提供一種基于柵格映射生長的交通網絡劃分方法及負載分擔配置服務器，執行復雜度低、精度高、負載均衡、并行處理的效率高。

為達到上述目的，本發明的技術方案是這樣實現的：

一種基于柵格映射生長的交通網絡劃分方法，該方法包括：

對獲取的指定交通網絡區域的交通流數據進行柵格映射，得到各柵格的權重值和相鄰柵格間的關聯度；

根據所述各柵格的權重值和相鄰柵格間的關聯度進行柵格生長劃分，得到相對應的柵格組合。

其中，該方法還包括：得到相對應的柵格組合后，在所述指定交通網絡區域中進行柵格映射還原，將所述柵格組合還原成對應的交通網絡區塊。

其中，所述對獲取的指定交通網絡區域的交通流數據進行柵格映射之前，該方法還包括：初始化過程；

所述初始化過程具體包括：根據指定交通網絡區域的所述交通流數據進行任務劃分并將劃分的任務配置到不同的計算服務器，根據所述計算服務器的數量確定所述指定交通網絡區域中待劃分處理的劃分區塊數量。

其中，所述交通流數據至少包括：交通網絡的邊的長度信息和拓撲信息、交通網絡交叉口的空間位置。

其中，得到所述各柵格的權重值具體包括：遍歷交通網絡的所有邊時，將所述邊的長度信息累加至其所對應的柵格中得到柵格的計算量并作為柵格的權重值；

得到所述相鄰柵格間的關聯度具體包括：遍歷交通網絡的所有邊時，根據所述拓撲信息得到跨越柵格的邊，將所述跨越柵格的邊所對應的相鄰柵格的關聯度進行累加得到柵格的通信量并作為所述相鄰柵格間的關聯度。

其中，柵格映射結束后得到各柵格的權重值和相鄰柵格間的關聯度具體為：得到每個柵格的計算量、和每個柵格對應四個相鄰方向的相鄰柵格間的關聯度并作為柵格的通信量；

所述進行柵格生長劃分具體包括：按照逐行掃描的方式獲取到第一個非空柵格作為柵格生長劃分的起始位置，分析其周邊相鄰柵格的生長劃分條件，逐一將符合所述生長劃分條件的柵格標記為已劃分柵格，將所述已劃分柵格的柵格的計算量和通信量加入到劃分區塊中并作為劃分區塊的計算量和通信量，設置劃分區塊的橫向長度和縱向長度，直至結束柵格生長劃分。

其中，所述非空柵格具體為柵格的計算量和通信量不同時為零的柵格；