小區(qū)進(jìn)行多邊形劃分方法的改進(jìn)

岳 軍

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司 北京 100080）

1 現(xiàn)有小區(qū)區(qū)域劃分的方法

現(xiàn)有小區(qū)劃分算法是主要是分別進(jìn)行Delaunay三角形生成，Voronoi圖生成，方向角平分線剖分這三個(gè)步驟。以下先將現(xiàn)有的劃分方法進(jìn)行介紹。

1.1 Delaunay三角形生成

以獨(dú)立站點(diǎn)位置信息參與計(jì)算生成Delaunay剖分三角形。

三角剖分的數(shù)學(xué)定義為：假設(shè)V是二維實(shí)數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段,E為e的集合。那么該點(diǎn)集V的一個(gè)三角剖分T＝(V，E)是一個(gè)平面圖G，該平面圖滿足條件以下條件：

（1）除了端點(diǎn)，平面圖中的邊不包含點(diǎn)集中的任何點(diǎn)；

（2）沒有相交邊；

（3）平面圖中所有的面都是三角面，且所有三角面的合集是散點(diǎn)集V的凸包（點(diǎn)集的凸包是指一個(gè)最小凸多邊形，滿足的點(diǎn)或者在多邊形邊上或者在其內(nèi)）。

最常用的三角剖分是Delaunay三角剖分，它是一種特殊的三角剖分，它需要滿足2個(gè)準(zhǔn)則，分別為：

（1）空?qǐng)A特性：Delaunay三角網(wǎng)是唯一的（任意4點(diǎn)不能共圓），在Delaunay三角形網(wǎng)中任一三角形的外接圓范圍內(nèi)不會(huì)有其他點(diǎn)存在。

（2）最大化最小角特性：在散點(diǎn)集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。從這個(gè)意義上講，Delaunay 三角網(wǎng)是“最接近于規(guī)則化的”的三角網(wǎng)。具體的說是指在兩個(gè)相鄰的三角形構(gòu)成凸四邊形的對(duì)角線，在相互交換后，六個(gè)內(nèi)角的最小角不再增大。

根據(jù)它的準(zhǔn)則可以推斷Delaunay剖分所具備以下的優(yōu)異特性：

（1）最接近：以最近臨近的三點(diǎn)形成三角形，且各線段(三角形的邊)皆不相交。

（2）唯一性：不論從區(qū)域何處開始構(gòu)建，最終都將得到一致的結(jié)果。

（3）最優(yōu)性：任意兩個(gè)相鄰三角形形成的凸四邊形的對(duì)角線如果可以互換的話，那么兩個(gè)三角形六個(gè)內(nèi)角中最小的角度不會(huì)變大。

（4）最規(guī)則：如果將三角網(wǎng)中的每個(gè)三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大。

（5）區(qū)域性：新增、刪除、移動(dòng)某一個(gè)頂點(diǎn)時(shí)只會(huì)影響臨近的三角形。

（6）具有凸多邊形的外殼：三角網(wǎng)最外層的邊界形成一個(gè)凸多邊形的外殼。

以上特性決定了很容易通過現(xiàn)有的Delaunay來進(jìn)行相鄰站點(diǎn)的判斷，而且它的特性決定了算法實(shí)現(xiàn)的效率很高。

在站點(diǎn)劃分中可以理解每一端點(diǎn)都是一個(gè)獨(dú)立站點(diǎn)，過每一點(diǎn)的所有線段的另外一側(cè)端點(diǎn)組成了當(dāng)前站點(diǎn)的第一圈緊鄰站點(diǎn)，這一部分的結(jié)果為隨后的Voronoi剖分提供基礎(chǔ)。

1.2 Voronoi圖生成

Voronoi圖，又叫泰森多邊形或Dirichlet圖，它是由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成。N個(gè)在平面上有區(qū)別的點(diǎn)，按照最鄰近原則劃分平面；每個(gè)點(diǎn)與它的最近鄰區(qū)域相關(guān)聯(lián)。

在站點(diǎn)區(qū)域劃分中使用的直線即是上一步Delaunay生成后的直線。這一步的生成效果如圖1所示。

1.3 方向角平分線剖分

以上一步Voronoi圖的結(jié)果按照每一獨(dú)立站點(diǎn)包含的小區(qū)的方向角平分線來進(jìn)行分割，得到小區(qū)的模擬覆蓋區(qū)域，這就是現(xiàn)階段各類軟件可達(dá)到的小區(qū)模擬劃分的結(jié)果，劃分效果如圖2所示。

1.4 現(xiàn)有剖分的誤差

現(xiàn)有的剖分實(shí)際上可以理解為相鄰站點(diǎn)采用中垂線進(jìn)行剖分，但實(shí)際現(xiàn)網(wǎng)小區(qū)存在著掛高、下傾角、天線類型、海拔高度、發(fā)射功率等差異，采用垂直平分線進(jìn)行剖分肯定和現(xiàn)實(shí)情況差異較大。

圖1 Voronoi圖的站點(diǎn)效果

圖2 Voronoi圖的小區(qū)效果

但三角形的三條邊的垂直平分線相交于外接圓的圓心，這一特點(diǎn)導(dǎo)致只有通過垂直平分線才能保證區(qū)域被完整分割。這也是Voronoi圖的基本出發(fā)點(diǎn)，如果通過簡(jiǎn)單的更改剖分的位置點(diǎn)必然導(dǎo)致三角形內(nèi)部劃分混亂。可以說如果還在此基礎(chǔ)上進(jìn)行改良很難得到能夠表示小區(qū)覆蓋區(qū)域的模擬剖分多邊形。

2 新劃分方法的引入

2.1 新方法的整體思路

考慮只使用簡(jiǎn)單的自由空間傳播損耗公式，不考慮地物類型也可以對(duì)電平情況進(jìn)行簡(jiǎn)單預(yù)估，預(yù)估的結(jié)果用來進(jìn)行小區(qū)區(qū)域的劃分。考慮到絕大多數(shù)區(qū)域的鄰近小區(qū)間的地物類型應(yīng)該相同，海拔差異不會(huì)很明顯，使用自由空間傳播損耗公式可以得到比較真實(shí)的最佳小區(qū)劃分。

整體思路為：首先按照之前的Voronoi圖生成過程使用中垂線的劃分方式得到粗略的小區(qū)區(qū)域劃分，接著對(duì)站點(diǎn)分布區(qū)域生成預(yù)定義大小（50×50）的柵格，對(duì)小區(qū)所屬站點(diǎn)周邊站點(diǎn)區(qū)域范圍內(nèi)的每一柵格點(diǎn)按照自由空間傳播損耗公式：LS＝32.45＋20lgF(MHz)＋20lgD(km)進(jìn)行預(yù)測(cè)，對(duì)每一柵格點(diǎn)只保留最大場(chǎng)強(qiáng)的小區(qū)標(biāo)示，預(yù)測(cè)電平。隨后將同一屬性的柵格進(jìn)行合并，邊界進(jìn)行平滑處理得到小區(qū)模擬覆蓋區(qū)域。

每一柵格點(diǎn)的預(yù)估場(chǎng)強(qiáng)= 小區(qū)的有效發(fā)射功率-（32.45＋20lgF(MHz)+20lgD(km)）+天線的標(biāo)稱增益+天線水平方向增益+天線垂直方向增益。

以上公式中對(duì)于每一柵格點(diǎn)存在變化的有距離D；天線水平方向增益；天線垂直方向增益。其余參數(shù)對(duì)于特定的小區(qū)來說都是常量。

2.2 新方法的大體過程

（1）按照前面已述方法生成小區(qū)的Voronoi劃分區(qū)域，見圖3所示。

（2）生成網(wǎng)格，判斷A小區(qū)的Voronoi相鄰區(qū)域及自身作為A小區(qū)的預(yù)測(cè)區(qū)域，見圖4所示。

圖3 小區(qū)的Voronoi劃分異

圖4 判定小區(qū)的預(yù)測(cè)區(qū)域

圖5 傳統(tǒng)方式和新方法小區(qū)劃分的對(duì)比

（3）讀取小區(qū)的天線配置及工程參數(shù)，對(duì)上述區(qū)域的每一網(wǎng)格點(diǎn)都進(jìn)行場(chǎng)強(qiáng)值的計(jì)算，場(chǎng)強(qiáng)值=小區(qū)的有效發(fā)射功率-（32.45＋20lgF(MHz)＋ 20lgD(km)）+天線的標(biāo)稱增益+天線水平方向增益+天線垂直方向增益，將網(wǎng)格屬性值（歸屬小區(qū)，場(chǎng)強(qiáng)）進(jìn)行更改；

（4）對(duì)所有室外小區(qū)都完成同樣3～7步的計(jì)算，用最大值替換網(wǎng)格屬性；

（5）將同一屬性的網(wǎng)格進(jìn)行合并，并將外圍平滑化。

2.3 新方法效果

圖5分別是同一區(qū)域使用傳統(tǒng)方法得到的小區(qū)邊界劃分和新方法劃分的對(duì)比。

總體比較，從劃分效果上新的模擬劃分效果更加貼近小區(qū)的實(shí)際覆蓋，在運(yùn)行效率上同一臺(tái)電腦上進(jìn)行比較，對(duì)923個(gè)小區(qū)進(jìn)行運(yùn)算，規(guī)劃軟件耗時(shí)866s，新算法劃分耗時(shí)20s。算法剛剛實(shí)現(xiàn)還存在優(yōu)化的可能，優(yōu)化后運(yùn)算時(shí)間還能有所提升。

3 總結(jié)

由上可知采用新的方法可以在不使用三維數(shù)字地圖的基礎(chǔ)上高效地生成非常貼近實(shí)際網(wǎng)絡(luò)覆蓋情況的小區(qū)多邊形，這為很多依據(jù)小區(qū)多變形劃分的應(yīng)用打好了基礎(chǔ)。