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

無效

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，該方法還包括：得到相對應的柵格組合后，在所述指定交通網絡區域中進行柵格映射還原，將所述柵格組合還原成對應的交通網絡區塊。

3.根據權利要求1所述的方法，其特征在于，所述對獲取的指定交通網絡區域的交通流數據進行柵格映射之前，該方法還包括：初始化過程；

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

4.根據權利要求1、2或3所述的方法，其特征在于，所述交通流數據至少包括：交通網絡的邊的長度信息和拓撲信息、交通網絡交叉口的空間位置。

5.根據權利要求4所述的方法，其特征在于，得到所述各柵格的權重值具體包括：遍歷交通網絡的所有邊時，將所述邊的長度信息累加至其所對應的柵格中得到柵格的計算量并作為柵格的權重值；

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

6.根據權利要求4所述的方法，其特征在于，柵格映射結束后得到各柵格的權重值和相鄰柵格間的關聯度具體為：得到每個柵格的計算量、和每個柵格對應四個相鄰方向的相鄰柵格間的關聯度并作為柵格的通信量；

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

7.根據權利要求6所述的方法，其特征在于，所述非空柵格具體為柵格的計算量和通信量不同時為零的柵格；

所述逐一將符合所述生長劃分條件的柵格標記為已劃分柵格具體包括：將所述劃分區塊中與每一個當前掃描到的柵格相鄰的周邊未劃分柵格，作為待選位置，計算未劃分柵格的柵格的計算量和通信量并加入到劃分區塊中作為劃分區塊的計算量和通信量，若劃分區塊的計算量不大于設置的劃分區塊的計算量上限X，則將所述未劃分柵格標記為已劃分柵格，繼續對柵格進行掃描和生長劃分。

8.一種基于柵格映射生長的負載分擔配置服務器，其特征在于，該服務器包括：柵格映射單元、柵格生長劃分單元；其中，

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

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

9.根據權利要求8所述的服務器，其特征在于，該服務器還包括：柵格映射還原單元，用于在所述指定交通網絡區域中進行柵格映射還原，將所述柵格組合還原成對應的交通網絡區塊。

10.根據權利要求8或9所述的服務器，其特征在于，所述交通流數據至少包括：交通網絡的邊的長度信息和拓撲信息、交通網絡交叉口的空間位置。

11.根據權利要求10所述的服務器，其特征在于，所述柵格映射單元，進一步用于遍歷交通網絡的所有邊時，將所述邊的長度信息累加至其所對應的柵格中得到柵格的計算量并作為柵格的權重值，根據所述拓撲信息得到跨越柵格的邊，將所述跨越柵格的邊所對應的相鄰柵格的關聯度進行累加得到柵格的通信量并作為所述相鄰柵格間的關聯度。

12.根據權利要求10所述的服務器，其特征在于，所述柵格映射單元，進一步用于柵格映射結束后得到每個柵格的計算量、和每個柵格對應四個相鄰方向的相鄰柵格間的關聯度并作為柵格的通信量；

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