无线基站选址的应用

无线基站选址的应用

1基于地图划分的方法区位选择问题涉及各专业领域，如大型基站布局问题、无线通信领域的公共基础设施分布问题、城市规划领域的公共机构分布等。这些问题共同点都是需要在宏观上考察地理信息,并结合本领域的应用需求,得到选址方案。其问题的本质是一种图的划分应用。在计算机领域,尤其是在地理信息的海量数据处理上,有基于格网划分的自适应点集划分算法。该方法对点集进行排序、分割,然后进行约束处理,算法的时间复杂程度接近于O(n)。另外,人们在解决图的划分算法中,根据启发式规则,提出了一些著名的算法。例如谱图划分算法通过计算特征向量,几何划分算法利用图的几何信息,它们都能得到优良的划分结果。还有一种多级划分算法,它通过合并节点与边,从而得到一个点边集合规模较小的图,在这较小的图上进行划分,最后还原到初始图,也能快速得到划分结果。这些算法在海量地理信息处理和图划分理论中有着重要的作用。本文借鉴了其中的某些思想,以基站选址为背景,采用自适应分治策略,从宏观上提出了基于地图划分的选址方法。同时在上海城市电子地图上,通过绘制矢量地图,做出方法的应用。对方法进行了分析,为相关领域中选址问题提供较为准确的科学方法。2区位问题和地图数据表指示2.1地图及监狱组织建设无线基站的目的是在其覆盖的区域内发送和接收信号。然而,基站的选址往往不仅需要考虑覆盖范围,容量以及网络质量,同时还要从宏观角度考虑城市地理信息,例如:人口密度,交通道路,地面建筑等。问题的难点在于,如何在宏观上利用城市地理信息,在微观上充分考虑基站自身特点的情况下,进行选址工作。本文将重点放在宏观方面的地理信息处理上。城市地理信息是以地图的形式表现。通过点、线以及多边形来描绘整个城市的地理特征。针对基站选址问题,有必要利用这些信息来划分地图,为每个基站提供选址区域。基站自身有着不同的覆盖范围、容量和网络质量。覆盖能力是以半径来衡量,它决定了基站接收或发送信号的范围,在地图上就表现为基站周围的几何形状。在最优设计的情况下,几何形状一般是类似蜂窝的六边形或圆形。容量则是基站可以使用的频带宽度,它反映了基站可以承载负荷。基站的容量要与其覆盖范围内需求的通讯量相匹配。市区内人口密集,通讯量大,要在这里部署更多的基站。网络质量则反映基站覆盖范围内的信号强弱。这些微观条件也是划分地图需要考虑的因素。本文描述基于地图划分的无线基站选址问题如下:一个矢量地图M,将它划分成不同的块,每个块是一包含点子集Vi的区域,并在这个区域中进行无线基站的选址。基站有着固定的覆盖范围s,和固定的覆盖点的数目k。同时要求无线基站能够覆盖到地图上所有的点。2.2图划分算法测试本文采用矢量形式来描述地图,优点在于清晰地描述几何形状之间的拓扑结构。矢量地图有点和线两种元素,即M=(V,E),其中M表示地图,V为点集合,E为边集合。有两种矢量地图的表示方式:以线为中心的数据表示方式,它是这样表示的:e1v1v2。其中e1表示图中的某条线段e1∈E。v1、v2表示它的两个连接点。以点为中心的数据表示方式。这种表示方式是参考了格林威治大学ChrisWalshaw教授对图划分算法进行测试的图表示方式。其中第一行标记出图中所有点的个数v和边的个数e。接着有v行用来描述每个点的邻接点及邻接边情况。具体每一行的形式如下:a1表示所要描述的点,其后每列数据由一个三元组<ai,pi,vi>表示,其中ai表示与a1相邻的点的ID号。pi表示边的方向,0代表双向,1代表以a1作为起点,2代表以a1作为终点。vi表示边的权值。计算机中采用邻接点数据表示方式,并用文件形式存储邻接图。图2展示了部分地图A,图3说明了文件中地图的存储形式。图3中第一行说明图2中有12个点和20条边,第二行说明标号为0的点的邻接情况:它与点1相连,边的方向是从点1到点0,边的权值是1,等等。3有小块地图基基于地图划分的基站选址的基本思想是将地图不断地进行自适应性分治划分,结合约束条件和属性,对每块小地图进行考察。如果某小块地图条件满足,则设立一个基站。在这种方法的基本思想指导下,本文分别考虑基于覆盖点数的选址方法,基于覆盖范围的选址方法和基于密度梯度的选址方法,最后将其综合,给出一般的基于地图划分的基站选址方法。3.1.现有传统地图中的车站点和校园基站选址首先要考虑容量问题。直观地说,在市区,人口密集,无线通讯发达,要求基站的容量大或者尽可能地部署基站。相反在郊区,基站的部署则要少些。在地图上有许多代表路口的点,而且一般是市区的路口较为密集,郊区的路口较为稀疏。这也从一个侧面反映了市区人口较为集中和通讯量需求量较大的实际情况。因此可以使用地图中的路口点的地理坐标作为计算基站选址点的依据。本文在方法中为基站添加了覆盖点数的属性k,其中要求k∈[K-i,K+j],其中K是用户指定的基站覆盖的点数目,i、j是两个可以微调的上下限参数。在这里,点就是指地图上的路口点。对所有的基于覆盖点数选址方法得到的基站集合B,其任一基站b,有:∀b∈B,kb∈[K-i,K+j]。在确定基站的位置时,使用平均值方法。通过求这个基站覆盖范围内的所有点的坐标的平均值,得到基站的具体地理位置。3.2适用范围的选取基站选址还要考虑基站的覆盖范围问题。对于一个给定的基站,在功率恒定的情况下,它的覆盖范围是确定的。实际中基站的覆盖范围是一个类似蜂窝的多边形,或者是一个圆。在这里覆盖范围使用的是矩形。如图4所示。对这个矩形定义为包含基站覆盖范围的最小外接矩形。无线基站选址方法的核心是自适应的分治思想。采用矩形作为分治的单元,可以在四分矩形时提高算法的效率,同时降低算法的复杂度。同时,最小外接矩形也保证了满足基站本身的覆盖范围的要求。在算法中用户可以为基站指定最大覆盖半径r,方法将在四分矩形的过程中,检查覆盖范围是否至少大r的要求。找到了满足基站覆盖范围的最小矩形,就可以计算基站的具体的选址位置。计算方法同3.1给出的平均值方法。3.3基于路口点的密度梯度设置目前许多城市都形成了以平面交叉为主的棋盘状市内交通网,和快速的环线网。例如:上海市中心城区的“三横三纵”快速干道,和内外环。整个城市的人口密度及通讯量都随着交通网呈现出从市区到郊区逐渐减少的趋势。本文考虑根据这种由城市中心到郊区人口和通讯密度逐渐递减的条件进行无线基站的选址。通过这种选址方法可以体现出城市的人口密度分布、无线通讯量分布等情况。假设基站b的覆盖范围是恒定半径r的圆,面积是s,路口点数为N。则路口点的单位密度ρ=N/s,即表示每平方米有多少个路口点。假定基站数目与路口点的单位密度成正比,则在密度为kρ的覆盖范围内应设置k个基站。由3.1节中关于路口点的数量与人口数量和通讯量的分析,可以知道基于路口点的密度梯度进行基站的选址也能够反映整个城市的通讯需求的。假设有n个沿市中心到郊区排列的基站覆盖范围,路口点的密度梯度组成的集合设为Sρ={ρ1,ρ2,…ρn},且ρ1代表市中心的路口点的密度,ρn代表地图上最外围路口点密度,则有ρi≤ρj,其中1≤j≤i≤n。在第i个覆盖范围内需要设置的基站数「ρi/ρ+。在确定好每个覆盖范围的基站数目后,需要为每个基站在覆盖范围内选址。如果在这个覆盖范围内仅有一个基站,则采用如3.1给出的平均值方法。如果有k个基站,则将覆盖范围内的所有的路口点分成k份,取每一份路口点的平均值作为各个基站的位置。3.4地图划分算法基于覆盖点数,基于覆盖范围,以及基于密度梯度的选址方法,分别从三个角度描述了如何通过划分地图进行基站的选址。它们的本质都是利用不同的目的和约束条件来进行地图的划分。基于地图划分的选址算法基本思想是自适应的分治算法。在算法执行中由于不同的约束条件,以及地图上路口点的分布影响,会产生划分块大小不均等的情况。地图上的每个点都有两个属性P:其一是实际的地理坐标;其二是否已被某基站覆盖。基于地图划分的基站选址问题的必要约束条件C是:完全覆盖地图上的所有路口点。基于地图划分的基站选址问题的可选约束条件C是:基站的固定的可覆盖的点的数目k,k∈[K-i,K+j],其中K是基站可以覆盖的点数目,i,j是两个可以微调的上下限参数;基站的固定覆盖范围s,s≤S,其中S是基站能够覆盖的最大范围;给定基站的覆盖范围s和路口点的单位密度ρ。这三个条件任选其一,分别对应以上提到的三种基站选址方法。下面给出基于地图划分的算法框架。输入:地图M,M=(V,E,P),V为节点集合,E为边集合,P为属性集。初始地图所在的矩形R。输出:基站选址的经纬度坐标点集。算法伪码:(1)构造矩形格网集合Rset和基站坐标集合Bset;(2)将初始地图所在格网R加入到集合Rset中。即初始Rset={R};(3)此时,Rset={ri,ri+1,ri+2,ri+3,…,rn},若满足必要约束条件或Rset为空,转到(7);否则,从格网集合Rset中的取出第一个元素ri;(4)若ri不包含任何点,则将ri从Rset中删除,并返回(3);(5)若ri不满足可选约束条件,则将ri四分,产生四个新的格网rn+1,rn+2,rn+3,rn+4,;将新产生的四个格网加入到Rset集合,并返回(3);(6)若ri满足可选约束条件,将根据均值法选定的基站位置(xi,yi)点,加入到集合Bset,同时将ri从集合Rset中删除,并返回(3);(7)若满足必要约束条件,则程序输出基站选址的经纬度坐标点集Bset;若不满足必要约束条件,则输出无解信息;(8)程序结束。4布局方法的实验4.1实验环境和程序本文将基于地图划分的无线基站选址方法应用在上海市城市交通电子地图上。上海城市交通地图有14007个路口点,21753条路段,数据量相对较大。实验的硬件环境是8台PC构成的Cluster集群,实验的软件环境:Java虚拟机运行环境(1.5.0版本)。程序启动后,从配置文件中读取参数,最后将结果以图形化和基站地理位置文件的形式输出。分别考虑覆盖点数,覆盖范围和密度梯度三种情况。同时下面给出基于密度梯度算法得到的基站部署的地理坐标点表。在实验中,得到了60个基站选址数据,其中地理坐标点数据均保留2位有效数字。4.2基于密度梯度的地图布局从图5中可以看出,基于覆盖点数的选址方法,仅考虑了覆盖点数,地图的部分边缘没有部署基站。这主要是因为在这些地方路口点较少,人口相对较少,它们被地图中心的一些基站所覆盖。从图6中可以看出,基于覆盖范围的选址方法,在地图的市区中心部分又没有部署更多的基站,这显然也不能满足市区通讯量大实际要求。图7显示出基于密度梯度的选址方法较为合理,它充分考虑了上两种基站选址方法的特点,将基站稀疏有度地在地图上进行了分布。本文对表1的数据进行了统计,并做出如图8所示的直方图。从这图8和图9中可以看出基站主要分布在北纬31.0°至31.5°,东经121.0°至121.5°,而这个范围恰是上海市市区所处的地理范围。通过对数据的进一步统计,发现在市区分布的基站数目约占所有部