[發明專利]一種基于矩形區域的仿真空間分割方法

有效

• 申請號: 201710480672.0
• 申請日: 2017-06-22
• 公開（公告）號: CN107302457B
• 公開（公告）日: 2020-04-07
• 發明（設計）人: 屈洪春;姚獻慧;宋衛貞;唐曉銘;王平
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 廖曦

本發明涉及一種基于矩形區域的仿真空間分割方法，屬于仿真空間分割領域。該方法包括以下步驟：S1：獲取聚心，S2：聚集：S3：凸包分割，S4：調整區域空白，S5：調整區域重疊，S6：判斷分區K，直到滿足用戶分區需求。該方法基于仿真空間中不同區域的Agent需要跨平臺通信的要求，將仿真空間中通信頻率較高的Agent聚集到一個區域，這使得不同仿真區域跨平臺通信的代價降低，降低了仿真的運行時間，提高仿真的運行效率。

技術領域

本發明屬于仿真空間分割領域，涉及一種基于矩形區域的仿真空間分割方法。

背景技術

在空間直觀仿真中，隨著真實細節的增加和可視化質量的提高，對運算資源的消耗也會急速增加，為了提高空間直觀仿真的運行效率，減少仿真的運行時間，空間分割成為解決大規模仿真的最好辦法。空間分割技術按照一定的區域劃分方法將仿真區域分解為小的子區域，極大的加速了仿真的各種操作和處理速度。空間分割后采用并行的方式執行大規模仿真，能夠充分挖掘硬件性能，可以獲得較高的性能，并且擴展性比較好，所以此方法在大規模并行仿真中使用的最為廣泛。

在仿真空間分割領域，Lozano等人提出了基于遺傳算法的分布式語義數據庫仿真模型，該方法從一組初始的染色體祖先集開始，通過雜交和變異等遺傳進化過程，最終達到作者所提出的在函數最小化時收斂的要求。其中染色體為一個包含k維的最小包含矩形的整形數組，每個最小包含矩形是一個包含[min_x,max_x,min_y,max_y]的四元組，定義了虛擬環境的一個矩形區域。該方法雖然滿足了函數最小化要求達到收斂，但是會引入邊緣重疊區域處理的問題，提高了以后仿真運行復雜度。而且也忽略了不同分割空間在通信時，需要盡可能減少跨區域通信量的要求。

Farhat提出的算法在生成子區域時，不斷接收周圍未被分區的單元，因此被稱為貪婪算法，貪婪算法在接收子區域時具有顯著的局部性，不能完成全局優化的能力，因此在負載均衡方面存在著不足。現有的基于Agent空間劃分的K-means空間分割方法，以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新聚類中心的值，指導獲取最好的聚類結果。雖然基于K-means算法劃分的仿真空間分區降低了不同仿真空間的通信代價，但是K-means算法的分割區域形狀不規則，計算復雜，同時這樣的分割區域不符合人使用的習慣，讓仿真實驗觀察困難。

大規模仿真空間的分割是根據仿真規模，虛擬環境被劃分成若干個子區域，每個服務器維護協同虛擬環境區域的狀態和不同區域之間的信息交換。仿真空間分割的不規則性，以及通信的花費，對仿真運行的有著顯著影響。

綜上分析，當前仿真空間分割需要解決的問題有：

(1)仿真空間分割如何做到最小化通信代價，同時兼顧分割算法的性能與分割區域簡單直觀。

(2)不需要分割區域數量的限制，算法自適應對空間進行規則形狀分割。

發明內容

有鑒于此，本發明的目的在于提供一種基于大規模仿真空間并行化的優化分割方法。該算法大幅度降低了仿真區域的通信代價，克服傳統矩形分割中的等面積分割，找到仿真目標空間分割的最優解。

為達到上述目的，本發明提供如下技術方案：

一種基于矩形區域的仿真空間分割方法，該方法包括以下步驟：

S1：獲取聚類中心：根據區域聚集度以及根據聚類中心的距離因素獲取不同區域的矩形；

S2：聚類：采用二分K-means標準化方法將Agent進行區域聚類；

S3：凸包分割：在基于聚類的基礎之上，將所得到聚類區域進行正矩形分割；

S4：調整區域空白：根據空白區域中的Agent與不同聚類中心的距離，將與其最近的矩形進行擴展；