-移动通信基站网络覆盖问题

移动通信基站网络覆盖问题摘要随着人均生活水平的不断提升，人们对于移动通信技术水平的要求也在不断提高，移动通信基站的覆盖问题也成了热点研究问题之一。本文主要研究移动通信基站的覆盖问题，即可将其转化为由若干个圆形面积来无缝覆盖一个矩形面积的问题，题中采用大基站和小基站覆盖的方法，即用两种半径分别为1km和0.5km的圆形面积覆盖矩形面积。而圆周为弧线，因此必存在重叠覆盖的区域，则将其转化为正多边形无重叠覆盖的问题。按照我们对题目要求的理解，在优先满足使用基站费用最少的条件来覆盖整个矩形面积，然后在这个基础之上再来调整使得覆盖面积的浪费最少。由此我们得出以下结论：（1）基站覆盖时，小基站覆盖面积为s=π*0.5^2，费用为1.1万元；大基站覆盖面积为S=π*1^2，费用为4万元，由此得出多使用大基站，空缺的地方再用小基站来补全的结论。（2）为满足“覆盖该区域”这一条件，就需要圆形相接。相接的圆形交点可以连成多边形，而这个多边形恰恰就是有效面积。我们将圆覆盖矩形的问题转化为多边形覆盖矩形的问题。而相比较之下，六边形的有效面积利用率最高，由此得出利用六边形模型来等效圆的结论。（3）为达到覆盖优化的效果，我们将边界处的低利用大圆面积，用小基站来覆盖。关键词：无线通信、六边形覆盖、利用率高、优化一、问题重述设某移动公司在建移动通信基站中，有一长200km，宽100km的矩形区域，需要建一基站覆盖该区域。基站有两类：一类是大功率基站，一类是小功率基站，有效覆盖是半径分别为1km和0.5km的圆域，每建一个基站的费用分别为4万元和1.1万元。问：（1）当所需区域为平面时请设计方案，使总费用最小；（2）设中心区域有一个小山，其海拔高度分布为h(x,y)=2210000001000xy(x^2+y^2=1000000)x,y的单位为m，区域的其余部分是海拔为500m的平地，请设计一个建基站的方案，使总费用最小。二、问题分析问题的目标是在于费用使用最少的情况下，尽可能多地全覆盖矩形面积。大基站、小基站的覆盖面积都是固定的，方案的关键是基站与基站间的位置建设。我们将这个问题转简化用一系列半径已知的圆形面积来覆盖矩形面积的问题。第一问规定所需区域为平面。从图形我们可以很容易看出，如果想要无缝覆盖这个矩形面积，各个圆之间会有重叠的部分，即重复覆盖的区域；而在矩形的边缘一定会有被矩形切割在外的部分，即浪费的面积。想要使得用的基站数量最小，就要求重复面积和浪费面积的和最小。几个圆相接的接点可以连成多边形即为有效的面积，所以我们通过圆的内接多边形来分析求解这个问题。第二问的分析方法基本和第一问相同，均为使用大、小基站，区别在于有部分面积转化为三维空间的立体图形的表面积，从h(x,y)的表达式可以看出，这座小山是一个圆锥，我们采用将圆锥表面积展开成平面的方法进行讨论。三、问题的假设与记号（1）每个基站点可以对其周围实行全方向网络覆盖，及其覆盖范围是一个半径为r的圆形区域s=π*r^2；（2）每个移动通信基站都具有相同且稳定的发射功率；（3）该模型可忽略偏远地区的小面积无法覆盖。R——大基站的半径大基站的覆盖面积——S=π*R^2r——小基站的半径小基站的覆盖面积——s=π*r^2L——矩形区域的长度W——矩形区域的宽度四、模型建立4.1.1圆形划分模型基础在基站半径有限的情况下，用最少的基站数实现给定区域完全无缝覆盖，实际上也就是该区域内的每一个基站所能覆盖的有效区域面积为最大，尽量减少辐射圆之间的重叠部分，充分利用每一个圆面积。通过几何证明可以得出【1】，三个半径相同的圆两两相交，以圆心为定点的三角形是正三角形且正三角形变长是圆半径的3倍时，圆域的面积最大，重叠部分最小，如图1所示。这是三个圆两两相交面积最大的极限情况，也就是说，在这种情况下，三个圆构成的无缝面积最大。图1半径相同的三个圆两两相交于一点图2用最少的基站覆盖给定区域基站的覆盖范围是以基站为圆心，以r为半径的圆。按照以上理论，对移动通信基站的位置进行排列。在一个给定的区域内S（L*W）内，按照图2所示排列，·代表的移动基站是每个圆的圆心，圆代表以传感半径r为半径的辐射圆。由以上理论可知，相邻基站之间的距离都是其覆盖半径的3倍。相邻基站以r为半径的辐射圆相交，每三个两两相交的圆相交于一点，相交部分为最小；它们的圆心，即移动通信基站构成变长为3r的的等边三角行。每个辐射圆的面积都充分利用，且区域S（L*W）实现无缝覆盖。4.1.2正方形网格划分与六边形网格划分的比较正方形的网格划分是以基站的覆盖半径为依据划分的。即基站的覆盖半径为r，则以为半径圆的内接正方形的边长就是每个网格的边长，基站处于网络的中心位置。不难得出，网格边长为2r。由上节的理论基础可以得出，由于图5所示的情形时四个圆两两相交，相交部分最小、构成的圆域面积最大的极限情况，故正方形网格中辐射圆的相交部分大于正方形网格中辐射圆的相交部分，前者较后者的辐射圆的有效利用面积小。也就是说，与正方形的网格划分来比，正方形网格划分的辐射圆相交面积大，有效利用面积小，所需的节点数更多。在同样是S(W*L)区域内，不难理解正方形网格划分所需的节点数是：N=2Lr*2Wr图5正方形网格划分示意图通过比较可知正六边形网格划分比正方形网格划分使用的基站数更少。4.1.3正六边形网格划分模型基础在图2所示区域网格划分中，把圆两两相交的部分简化，用线段代替圆的相交部分，即用圆的内接正六边形来代替圆形，则图2可化简成如图3所示。圆形简化成正六边形，这种形状接近圆形的理想功率覆盖区域，且在正六边形之间无缝也无重叠部分，非常适合于区域划分与网格划分。按照这样的方法对覆盖区域进行网格划分，只要确定移动通信基站的半径，就可以使用最少的基站实现对目标区域的覆盖。进行这样的网格规划，并不影响基站的圆形覆盖区域，简化的正六边形只是为了使规划的图形更加直观。因此，把这种利用正六边形进行网格划分的方法称为正六边形网格划分法。图3正六边形网格化分示意图图4相邻三个正六边形为了得出网络实现无缝覆盖的最少基站数公式，我们取出其中相邻的三个正六边形，如图4，由于是正六边形，我们可以得到：d1=3/2r（1）d2=3r2）因此，我们可以得出网络实现无缝覆盖的最少基站数公式：N=rL3*2/3rW其中，N是网络实现无缝覆盖所需的最少基站数，r是覆盖半径，是向下取整。4.1.4边界问题对于用大基站填充浪费太大的问题，我们采用用小基站补填的方式来优化覆盖。4.1.5模型求解4.2由Matlab可得出问题二的图形为一个圆锥，一个底面积为1km，高为0.5km的圆锥，由此我们可以得出问题的模型，即在一个平面中间有一个圆锥形的小山坡。移动通信的信号为空间分布，在不同高度，最大水平面积内，通信信号都相同分布，所以问题二的模型与问题一样，即在小山的山顶建一个大基站，其他与模型一一样。