[發明專利]一種基站輻射范圍的快速計算與更新方法

在審

• 申請號: 201710976973.2
• 申請日: 2017-10-19
• 公開（公告）號: CN107798182A
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 史策;徐秋輝;馬登峰;馬曉丹
• 申請（專利權）人: 江蘇金陵科技集團有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50;H04W4/02;H04W64/00
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 王安琪,梁耀文

技術領域

本發明涉及空間分析算法領域，尤其是一種基站輻射范圍的快速計算與更新方法。

背景技術

由于用戶在基站上的登錄位置實際是所在基站的位置，是固定的、離散的高密度點信息，無法真實反映用戶實際所處位置，相比而言，通過基站輻射范圍可以更為準確地定位用戶位置。

基站輻射范圍一般以蜂窩網絡表示，蜂窩網原理和Voronoi圖原理本質上趨于一致，可以采用Voronoi圖相關算法來構建基站理論輻射范圍。實際上，理論上蜂窩狀信號覆蓋網絡并不存在，受制于基站建設點的限制，基站輻射范圍往往為不規則網絡。

Voronoi圖也稱泰森多邊形，對于泰森多邊形的生成，采用生成速度更接近線性時間的基于Delaunay三角網算法；對于泰森多邊形的更新，則以Delaunay三角網更新為基礎，其中，Delaunay三角網更新主要包括點插入更新和點刪除更新。對于點插入更新，采用時間效率較高的方法：確定外接圓包含插入點的三角形構成的影響域，將插入點與影響域邊界節點連接，對影響域整體進行LOP優化。對于點刪除更新，國內外相關研究很多，Aggarwal最早提出了點刪除算法，但計算復雜，應用很少。Heller提出了最小外接圓的點刪除算法，Devillers對Heller算法進行改進，并糾正Heller的錯誤，提出了凸耳權值點刪除算法，計算效率較高，但由于凸耳定義嚴格，動態編輯過程中凸耳隊列的更新維護比較復雜，在一定程度上影響了計算效率。

發明內容

本發明所要解決的技術問題在于，提供一種基站輻射范圍的快速計算與更新方法，能夠快速的更新基站理論輻射范圍，有利支撐基站理論輻射范圍定位基站上登錄用戶的手段，輔助實現對基站上登錄用戶更為準確的定位。

為解決上述技術問題，本發明提供一種基站輻射范圍的快速計算與更新方法，包括如下步驟：

(1)以初始三角形為基礎，計算與更新Delaunay三角網；

(2)計算與更新Delaunay三角形的網格索引與拓撲關系；

(3)基于Delaunay三角網與Voronoi圖生成算法，計算與更新Voronoi圖；

(4)結合Voronoi圖與基站輻射方向，計算與更新基站理論輻射范圍；

(5)依據包含基站的最小外接矩形，對基站理論輻射范圍進行裁剪。

優選的，步驟(1)中，初始三角形為包含點集的最小外接矩形的外接等邊三角形。

優選的，步驟(2)中，計算與更新Delaunay三角形的網格索引與拓撲關系具體包括如下步驟：

(21)根據全球地理范圍建立網格；

(22)對點集的凸包三角化，生成初始三角形，并以三角形重心為標識，對生成的三角形進行網格索引；

(23)依次將點集中每個點內插到三角網，依據空圓準則更新三角網，并對三角網中的三角形進行網格索引和拓撲關系的計算與更新。

優選的，步驟(4)中，計算基站理論輻射范圍具體包括如下步驟：

(41)基于Delaunay三角網，以接近線性的速度，為每個基站生成Voronoi圖，作為其理論輻射范圍；

(42)對于同一位置有輻射方向的多個基站，其組合方向是全方向，則每個基站的理論輻射范圍為其對應Voronoi圖在其輻射方向上的部分。

優選的，步驟(4)中，更新基站理論輻射范圍包括基站插入的更新和基站刪除的更新。

優選的，對于基站插入，先判斷是否需要擴充Delaunay三角網范圍，再進行基站插入；判斷是否需要擴充Delaunay三角網范圍具體為：a、將待插入基站構成點集，對該點集的凸包三角化，生成新三角形；b、判斷初始三角形是否包含新三角形，若不包含，將待插入基站與初始三角形頂點構成點集，對該點集的凸包三角化，生成新三角形，將新三角形頂點作為初始三角形頂點，更新三角網中與該頂點關聯的三角形，同時更新其網格索引與拓撲關系。

優選的，基站插入分為在已有基站的位置上插入基站和在新位置上插入基站，在已有基站的位置上插入基站無須更新Voronoi圖，在新位置上插入基站則要更新Voronoi圖。