無線基站選址的應(yīng)用

無線基站選址的應(yīng)用

1基于地圖劃分的方法區(qū)位選擇問題涉及各專業(yè)領(lǐng)域，如大型基站布局問題、無線通信領(lǐng)域的公共基礎(chǔ)設(shè)施分布問題、城市規(guī)劃領(lǐng)域的公共機(jī)構(gòu)分布等。這些問題共同點(diǎn)都是需要在宏觀上考察地理信息,并結(jié)合本領(lǐng)域的應(yīng)用需求,得到選址方案。其問題的本質(zhì)是一種圖的劃分應(yīng)用。在計(jì)算機(jī)領(lǐng)域,尤其是在地理信息的海量數(shù)據(jù)處理上,有基于格網(wǎng)劃分的自適應(yīng)點(diǎn)集劃分算法。該方法對點(diǎn)集進(jìn)行排序、分割,然后進(jìn)行約束處理,算法的時(shí)間復(fù)雜程度接近于O(n)。另外,人們在解決圖的劃分算法中,根據(jù)啟發(fā)式規(guī)則,提出了一些著名的算法。例如譜圖劃分算法通過計(jì)算特征向量,幾何劃分算法利用圖的幾何信息,它們都能得到優(yōu)良的劃分結(jié)果。還有一種多級劃分算法,它通過合并節(jié)點(diǎn)與邊,從而得到一個點(diǎn)邊集合規(guī)模較小的圖,在這較小的圖上進(jìn)行劃分,最后還原到初始圖,也能快速得到劃分結(jié)果。這些算法在海量地理信息處理和圖劃分理論中有著重要的作用。本文借鑒了其中的某些思想,以基站選址為背景,采用自適應(yīng)分治策略,從宏觀上提出了基于地圖劃分的選址方法。同時(shí)在上海城市電子地圖上,通過繪制矢量地圖,做出方法的應(yīng)用。對方法進(jìn)行了分析,為相關(guān)領(lǐng)域中選址問題提供較為準(zhǔn)確的科學(xué)方法。2區(qū)位問題和地圖數(shù)據(jù)表指示2.1地圖及監(jiān)獄組織建設(shè)無線基站的目的是在其覆蓋的區(qū)域內(nèi)發(fā)送和接收信號。然而,基站的選址往往不僅需要考慮覆蓋范圍,容量以及網(wǎng)絡(luò)質(zhì)量,同時(shí)還要從宏觀角度考慮城市地理信息,例如:人口密度,交通道路,地面建筑等。問題的難點(diǎn)在于,如何在宏觀上利用城市地理信息,在微觀上充分考慮基站自身特點(diǎn)的情況下,進(jìn)行選址工作。本文將重點(diǎn)放在宏觀方面的地理信息處理上。城市地理信息是以地圖的形式表現(xiàn)。通過點(diǎn)、線以及多邊形來描繪整個城市的地理特征。針對基站選址問題,有必要利用這些信息來劃分地圖,為每個基站提供選址區(qū)域。基站自身有著不同的覆蓋范圍、容量和網(wǎng)絡(luò)質(zhì)量。覆蓋能力是以半徑來衡量,它決定了基站接收或發(fā)送信號的范圍,在地圖上就表現(xiàn)為基站周圍的幾何形狀。在最優(yōu)設(shè)計(jì)的情況下,幾何形狀一般是類似蜂窩的六邊形或圓形。容量則是基站可以使用的頻帶寬度,它反映了基站可以承載負(fù)荷?；镜娜萘恳c其覆蓋范圍內(nèi)需求的通訊量相匹配。市區(qū)內(nèi)人口密集,通訊量大,要在這里部署更多的基站。網(wǎng)絡(luò)質(zhì)量則反映基站覆蓋范圍內(nèi)的信號強(qiáng)弱。這些微觀條件也是劃分地圖需要考慮的因素。本文描述基于地圖劃分的無線基站選址問題如下:一個矢量地圖M,將它劃分成不同的塊,每個塊是一包含點(diǎn)子集Vi的區(qū)域,并在這個區(qū)域中進(jìn)行無線基站的選址?；居兄潭ǖ母采w范圍s,和固定的覆蓋點(diǎn)的數(shù)目k。同時(shí)要求無線基站能夠覆蓋到地圖上所有的點(diǎn)。2.2圖劃分算法測試本文采用矢量形式來描述地圖,優(yōu)點(diǎn)在于清晰地描述幾何形狀之間的拓?fù)浣Y(jié)構(gòu)。矢量地圖有點(diǎn)和線兩種元素,即M=(V,E),其中M表示地圖,V為點(diǎn)集合,E為邊集合。有兩種矢量地圖的表示方式:以線為中心的數(shù)據(jù)表示方式,它是這樣表示的:e1v1v2。其中e1表示圖中的某條線段e1∈E。v1、v2表示它的兩個連接點(diǎn)。以點(diǎn)為中心的數(shù)據(jù)表示方式。這種表示方式是參考了格林威治大學(xué)ChrisWalshaw教授對圖劃分算法進(jìn)行測試的圖表示方式。其中第一行標(biāo)記出圖中所有點(diǎn)的個數(shù)v和邊的個數(shù)e。接著有v行用來描述每個點(diǎn)的鄰接點(diǎn)及鄰接邊情況。具體每一行的形式如下:a1表示所要描述的點(diǎn),其后每列數(shù)據(jù)由一個三元組<ai,pi,vi>表示,其中ai表示與a1相鄰的點(diǎn)的ID號。pi表示邊的方向,0代表雙向,1代表以a1作為起點(diǎn),2代表以a1作為終點(diǎn)。vi表示邊的權(quán)值。計(jì)算機(jī)中采用鄰接點(diǎn)數(shù)據(jù)表示方式,并用文件形式存儲鄰接圖。圖2展示了部分地圖A,圖3說明了文件中地圖的存儲形式。圖3中第一行說明圖2中有12個點(diǎn)和20條邊,第二行說明標(biāo)號為0的點(diǎn)的鄰接情況:它與點(diǎn)1相連,邊的方向是從點(diǎn)1到點(diǎn)0,邊的權(quán)值是1,等等。3有小塊地圖基基于地圖劃分的基站選址的基本思想是將地圖不斷地進(jìn)行自適應(yīng)性分治劃分,結(jié)合約束條件和屬性,對每塊小地圖進(jìn)行考察。如果某小塊地圖條件滿足,則設(shè)立一個基站。在這種方法的基本思想指導(dǎo)下,本文分別考慮基于覆蓋點(diǎn)數(shù)的選址方法,基于覆蓋范圍的選址方法和基于密度梯度的選址方法,最后將其綜合,給出一般的基于地圖劃分的基站選址方法。3.1.現(xiàn)有傳統(tǒng)地圖中的車站點(diǎn)和校園基站選址首先要考慮容量問題。直觀地說,在市區(qū),人口密集,無線通訊發(fā)達(dá),要求基站的容量大或者盡可能地部署基站。相反在郊區(qū),基站的部署則要少些。在地圖上有許多代表路口的點(diǎn),而且一般是市區(qū)的路口較為密集,郊區(qū)的路口較為稀疏。這也從一個側(cè)面反映了市區(qū)人口較為集中和通訊量需求量較大的實(shí)際情況。因此可以使用地圖中的路口點(diǎn)的地理坐標(biāo)作為計(jì)算基站選址點(diǎn)的依據(jù)。本文在方法中為基站添加了覆蓋點(diǎn)數(shù)的屬性k,其中要求k∈[K-i,K+j],其中K是用戶指定的基站覆蓋的點(diǎn)數(shù)目,i、j是兩個可以微調(diào)的上下限參數(shù)。在這里,點(diǎn)就是指地圖上的路口點(diǎn)。對所有的基于覆蓋點(diǎn)數(shù)選址方法得到的基站集合B,其任一基站b,有:?b∈B,kb∈[K-i,K+j]。在確定基站的位置時(shí),使用平均值方法。通過求這個基站覆蓋范圍內(nèi)的所有點(diǎn)的坐標(biāo)的平均值,得到基站的具體地理位置。3.2適用范圍的選取基站選址還要考慮基站的覆蓋范圍問題。對于一個給定的基站,在功率恒定的情況下,它的覆蓋范圍是確定的。實(shí)際中基站的覆蓋范圍是一個類似蜂窩的多邊形,或者是一個圓。在這里覆蓋范圍使用的是矩形。如圖4所示。對這個矩形定義為包含基站覆蓋范圍的最小外接矩形。無線基站選址方法的核心是自適應(yīng)的分治思想。采用矩形作為分治的單元,可以在四分矩形時(shí)提高算法的效率,同時(shí)降低算法的復(fù)雜度。同時(shí),最小外接矩形也保證了滿足基站本身的覆蓋范圍的要求。在算法中用戶可以為基站指定最大覆蓋半徑r,方法將在四分矩形的過程中,檢查覆蓋范圍是否至少大r的要求。找到了滿足基站覆蓋范圍的最小矩形,就可以計(jì)算基站的具體的選址位置。計(jì)算方法同3.1給出的平均值方法。3.3基于路口點(diǎn)的密度梯度設(shè)置目前許多城市都形成了以平面交叉為主的棋盤狀市內(nèi)交通網(wǎng),和快速的環(huán)線網(wǎng)。例如:上海市中心城區(qū)的“三橫三縱”快速干道,和內(nèi)外環(huán)。整個城市的人口密度及通訊量都隨著交通網(wǎng)呈現(xiàn)出從市區(qū)到郊區(qū)逐漸減少的趨勢。本文考慮根據(jù)這種由城市中心到郊區(qū)人口和通訊密度逐漸遞減的條件進(jìn)行無線基站的選址。通過這種選址方法可以體現(xiàn)出城市的人口密度分布、無線通訊量分布等情況。假設(shè)基站b的覆蓋范圍是恒定半徑r的圓,面積是s,路口點(diǎn)數(shù)為N。則路口點(diǎn)的單位密度ρ=N/s,即表示每平方米有多少個路口點(diǎn)。假定基站數(shù)目與路口點(diǎn)的單位密度成正比,則在密度為kρ的覆蓋范圍內(nèi)應(yīng)設(shè)置k個基站。由3.1節(jié)中關(guān)于路口點(diǎn)的數(shù)量與人口數(shù)量和通訊量的分析,可以知道基于路口點(diǎn)的密度梯度進(jìn)行基站的選址也能夠反映整個城市的通訊需求的。假設(shè)有n個沿市中心到郊區(qū)排列的基站覆蓋范圍,路口點(diǎn)的密度梯度組成的集合設(shè)為Sρ={ρ1,ρ2,…ρn},且ρ1代表市中心的路口點(diǎn)的密度,ρn代表地圖上最外圍路口點(diǎn)密度,則有ρi≤ρj,其中1≤j≤i≤n。在第i個覆蓋范圍內(nèi)需要設(shè)置的基站數(shù)「ρi/ρ+。在確定好每個覆蓋范圍的基站數(shù)目后,需要為每個基站在覆蓋范圍內(nèi)選址。如果在這個覆蓋范圍內(nèi)僅有一個基站,則采用如3.1給出的平均值方法。如果有k個基站,則將覆蓋范圍內(nèi)的所有的路口點(diǎn)分成k份,取每一份路口點(diǎn)的平均值作為各個基站的位置。3.4地圖劃分算法基于覆蓋點(diǎn)數(shù),基于覆蓋范圍,以及基于密度梯度的選址方法,分別從三個角度描述了如何通過劃分地圖進(jìn)行基站的選址。它們的本質(zhì)都是利用不同的目的和約束條件來進(jìn)行地圖的劃分?；诘貓D劃分的選址算法基本思想是自適應(yīng)的分治算法。在算法執(zhí)行中由于不同的約束條件,以及地圖上路口點(diǎn)的分布影響,會產(chǎn)生劃分塊大小不均等的情況。地圖上的每個點(diǎn)都有兩個屬性P:其一是實(shí)際的地理坐標(biāo);其二是否已被某基站覆蓋?；诘貓D劃分的基站選址問題的必要約束條件C是:完全覆蓋地圖上的所有路口點(diǎn)。基于地圖劃分的基站選址問題的可選約束條件C是:基站的固定的可覆蓋的點(diǎn)的數(shù)目k,k∈[K-i,K+j],其中K是基站可以覆蓋的點(diǎn)數(shù)目,i,j是兩個可以微調(diào)的上下限參數(shù);基站的固定覆蓋范圍s,s≤S,其中S是基站能夠覆蓋的最大范圍;給定基站的覆蓋范圍s和路口點(diǎn)的單位密度ρ。這三個條件任選其一,分別對應(yīng)以上提到的三種基站選址方法。下面給出基于地圖劃分的算法框架。輸入:地圖M,M=(V,E,P),V為節(jié)點(diǎn)集合,E為邊集合,P為屬性集。初始地圖所在的矩形R。輸出:基站選址的經(jīng)緯度坐標(biāo)點(diǎn)集。算法偽碼:(1)構(gòu)造矩形格網(wǎng)集合Rset和基站坐標(biāo)集合Bset;(2)將初始地圖所在格網(wǎng)R加入到集合Rset中。即初始Rset={R};(3)此時(shí),Rset={ri,ri+1,ri+2,ri+3,…,rn},若滿足必要約束條件或Rset為空,轉(zhuǎn)到(7);否則,從格網(wǎng)集合Rset中的取出第一個元素ri;(4)若ri不包含任何點(diǎn),則將ri從Rset中刪除,并返回(3);(5)若ri不滿足可選約束條件,則將ri四分,產(chǎn)生四個新的格網(wǎng)rn+1,rn+2,rn+3,rn+4,;將新產(chǎn)生的四個格網(wǎng)加入到Rset集合,并返回(3);(6)若ri滿足可選約束條件,將根據(jù)均值法選定的基站位置(xi,yi)點(diǎn),加入到集合Bset,同時(shí)將ri從集合Rset中刪除,并返回(3);(7)若滿足必要約束條件,則程序輸出基站選址的經(jīng)緯度坐標(biāo)點(diǎn)集Bset;若不滿足必要約束條件,則輸出無解信息;(8)程序結(jié)束。4布局方法的實(shí)驗(yàn)4.1實(shí)驗(yàn)環(huán)境和程序本文將基于地圖劃分的無線基站選址方法應(yīng)用在上海市城市交通電子地圖上。上海城市交通地圖有14007個路口點(diǎn),21753條路段,數(shù)據(jù)量相對較大。實(shí)驗(yàn)的硬件環(huán)境是8臺PC構(gòu)成的Cluster集群,實(shí)驗(yàn)的軟件環(huán)境:Java虛擬機(jī)運(yùn)行環(huán)境(1.5.0版本)。程序啟動后,從配置文件中讀取參數(shù),最后將結(jié)果以圖形化和基站地理位置文件的形式輸出。分別考慮覆蓋點(diǎn)數(shù),覆蓋范圍和密度梯度三種情況。同時(shí)下面給出基于密度梯度算法得到的基站部署的地理坐標(biāo)點(diǎn)表。在實(shí)驗(yàn)中,得到了60個基站選址數(shù)據(jù),其中地理坐標(biāo)點(diǎn)數(shù)據(jù)均保留2位有效數(shù)字。4.2基于密度梯度的地圖布局從圖5中可以看出,基于覆蓋點(diǎn)數(shù)的選址方法,僅考慮了覆蓋點(diǎn)數(shù),地圖的部分邊緣沒有部署基站。這主要是因?yàn)樵谶@些地方路口點(diǎn)較少,人口相對較少,它們被地圖中心的一些基站所覆蓋。從圖6中可以看出,基于覆蓋范圍的選址方法,在地圖的市區(qū)中心部分又沒有部署更多的基站,這顯然也不能滿足市區(qū)通訊量大實(shí)際要求。圖7顯示出基于密度梯度的選址方法較為合理,它充分考慮了上兩種基站選址方法的特點(diǎn),將基站稀疏有度地在地圖上進(jìn)行了分布。本文對表1的數(shù)據(jù)進(jìn)行了統(tǒng)計(jì),并做出如圖8所示的直方圖。從這圖8和圖9中可以看出基站主要分布在北緯31.0°至31.5°,東經(jīng)121.0°至121.5°,而這個范圍恰是上海市市區(qū)所處的地理范圍。通過對數(shù)據(jù)的進(jìn)一步統(tǒng)計(jì),發(fā)現(xiàn)在市區(qū)分布的基站數(shù)目約占所有部