论文研究-移动通信系统中Voronoi图的研究及应用 .pdf

所需积分/C币:6 2019-08-17 05:33:40 612KB .PDF

移动通信系统中Voronoi图的研究及应用,任欢欢,,在移动通信系统中,基站覆盖范围的划分是一个重要研究内容。为此,本文提出一种基于Voronoi图的基站覆盖范围划分方法。首先,依据��
山国武技论文在线 第二,空圆特性。即过 Voronoi图中的任意结点qi作圆Ci,且使Ci过结点qi所在的 Voronoi边所对应的邻接顶点,数目大于等于3个,并且在Ci内不包含平面点 集中的任何其他顶点,即是一个空圆。如图2所示。 第三,第三,删除或增加一个顶点,只会影响局部相邻点的 Voronoi多边形,称为局 部影响特性。 图 图的空圆特性 角网 不规则三角网也称为曲面数据结构,是由 Pauker和他的同事设计的一个系统。它是 棖据区域内有限点集将区域划分成相等的三角面网络。每个三角形两两互不相交。 Delaunay 三角网是具有以下两个性质的不规则三角网: 第¨,空外接圆性质。即每个 Delaunay三角形的外接圆不包含面内的其他任何点。 第二,最大化最小角性质。即在点集所能形成的三角网中, De launay三角网中三角形 的最小角度是最大的。 三角网 2 De launay三角剖分 Delaunay三角网生成算法有多和,例如分治算法、逐点插入法、三角网生长法。其中 三角网生长法的有点事内存空间占用较少,但是时间效率不高。主要原因在于第三点的搜索 本文对三角网生长法在第三点的搜索上进行了改进。采用姗格划分的形式,缩小第三点 的搜索范围,提高速度。 山国武技论文在线 三角网的生成算法 三角网生长算法是先找出点集中相距最短的两点连接成为一条 边然后按 边三角网的判别法则找出包含此边的 三角形的另一端点依次处理所有 新生成的边直至最终完成。在传统三角网生长法的基础上,利用平面划分栅格的方式,对 第三点寻找进行改进。最终算法执行步骤如下: 1)给基站建立栅格索引,标记每个基站扇区所在的栅格。 2)先将基站链表中的第一个基站点选为三角剖分第一点。P1,再找一个离p1最近的点 P2,然后连接此二点,作为定向基线。在找第二点的时候使用索引栅格找到第一点P1所在的 栅格,然后在其周围的9个栅格中找满足条件的第二点,如果9个栅格内没冇有找到则在其周 围的16个栅格内继续找,知道找到第二点P2。 3)找到第一个三角形的第三点,第三点是使PIP2的夹角最大的点,记为p3。使用索 引栅格找第三点同2)中找第二点相同。 4)生成第一个三角形,更新点、边和三角形的链表。将三条边按顺时针顺序放入边界 边链表。 5)遍历边界边链表寻找每条边对应的合法第三点,更新点、三角形链表,然后从边界 边链表中删除当前边界边添加对应的两条新增边界边。(找第三点的方法同3)一样,使用 索引栅格) 6)复第4步,直到所有的边界边都不会被扩展为止 7)遍历边界边寻找合法第三点了程序 ①因为第个三角形的边界边是顺时针存储的,所以对于每个边界边已经找到了其右手 边的合法第三点,现在需要的就是找到其左手边的合法第三点。作为此边扩展的三角形 ②搜索点集,看是否能找到同时满足一下几个条件的点: 第一,此点与当前边界边组成的夹角最大。第二,点在线向量的左手边。第三,此点没 有被使用过,或者使用变量为1的。第四,此点不是当前线向量的两个端点。第五,此点与 边界边连线后形成的两条边与所有边不交叉 ③如果找到这样的点,更新点、边、三角形的链表。 ④结束算法。 三角网“蚕食”改进 按照三角网生成法的过程,编写程序,得到如图左边图形样的三角网,但是此三 角网存在着边界边过长的情况,在此采用了边界边蚕食的方法将网中长度超过一定阈 值的边界边进行了蚕食处理。处理后,得到图右边图形的结果。 山国科技论文在线 图蚕食边前后的三角网 3 Vor ono i图生成 Voronoi多边形是将平面点集用直线分割,使平面上的每个点都包含在一个多边形内。 Voronoi多边形的性质是多边形内只包含一个离散点,且包含点P的多边形内的任何一点Q 到P的距离都小于Q到平面上其他点的距离。平面上所有点对应的 Voronoi多边形构成的图 为 Voronoi图。 De launay三角形与 Voronoi图为对偶图。在此,采用间接V图生成法生成V 图,即首先构造平面点集的 Delaunay三角剖分,然后由剖分后的三角形生成Ⅴ图 图间接生成法 如图6所示,V图间接生成算法的主要步骤有以下几步 按照上一节的方法进行平面点集的三角剖分。 从点集中取出一个点。 从三角形链表中取出所有的其中的一个顶点为该离散点的三角形。 计算各个三角形的垂心 对这些垂心按照空间位置进行逆时针排序,按照逆序连接垂心就是以该离散点为母点的 多边形 重复步骤直至生成所有离散点的 多边形。 当两佟只有彼此相交,找到出现问题的两顶点,分别找到两顶点(其实为三角形的中 心点)所属的三角形,然后看其是否有公共边,如果有公共边则调整公共边(即对角线 互换),优化图。 用)处理完后,还有一部分有问题的图,其主要是有问题的三角形没有公共边,此 时使用三角剖分空接员。 最后生成图的时候要对边界点进行处理,如果边界点在现有图之中则不用扩展 图,如果边界点不在其图范围内则找到此边界点的两条边界边,并取两条边界边的夹 角的角平分线方向上,长度为当前点的最近邻区距离上的一点作为虚拟基站点,然后此 山国武技论文在线 点与两条边界边形成三角形求出其中心点,此两个中心点作为当前点的图的扩展两 求扇区级的图。找到某基站内的 扇区的各个方向角,求其方向角中间的角平 分线作为扇区图的分界点。找到某基站的 扇区的各个方向角,求其方向角中间 的角半分线作为扇区图的分界点。 其中,到步是对生成的图进行局部优化的过程。采用局部优化原理,将不符合最优 条件的三角形进行对角线互换,改进图。 Start 点集的三角音 从点集中取出一个点 从三角形链表中取出有其中的 顶点为该离散点的二角形 计算各个三角形的垂心 对这些垂心控照空 置进行逆吋针排序 得到一个以这离散点位母点的 oron多边形 还有没有生成 vor。no多边形的离散点 一叠加三角形中心图层与 yorng图看是否有相交 使用第一种整方案调整E 相邻有问题的三角形互换对角 使用第科 角剖分接页性质率 图 图生成流程图 图局部优化 在 图生成过程中,出现图重叠的情况,因为生成的 三角网不是最 优的三角网,需要局部优化。局部优化原理是将对角线对调,使兑换后的三角形满足空接圆 性质。优化后重新生成图,反复比过程,知道图正确为止。在对边界边进行虚拟点建 设,边界点 多边形处理后得到图的效果。其中,左图为修正前,右图为修正后 山国武技论文在线 图局部优化 4 Voronoⅰ图在移动通信网中的应用 依据本文提出的 图算法,将 图应用于移动通信中的下列应用里 基站覆盖区域划分中的应用 画出所有基站后,以仝网基站为母点画出基站的 图,得到每个基站的覆盖区域。 完成基站的初始布局。得到的基站图如下图所小 图基站 图 )基站话务密度分布图制作的应用 基站话务密度分布图可以从整体上来分析基站的状态,通过话务密度图分析,可以找出 负载较重的基站,进行wla站点安放,或者增基站操作,来为现有基站分流。应用于移 动通信网络优化中。下图为某市话务密度分布图: 山国武论文在线 图话务密度分布图 其中不同颜色代表不同的话务密度值,颜色鲜亮的为高话务密度区域。 5结论 移动通信系统中网络优化是一项重要而且艰巨的仼务,并受到移动通信运营商的高度重 视。木文利用计算儿何中的 Voronoi图与 Delaunay三角剖分原理,以及对V图制作过程中 的改进改善工作,完成了基站覆盖区域划分的功能。并且将覆盖区域划分的⊥作引入到了基 站话务密度分布图制作上作中。V图在移动通信网络优化上作中还有很多作用,例如新加基 站的选址工作、小区容量估算、基站场强预测等值线等方面,都可应用到V图。所以解决以 上问题时,需要进一步研究ⅴ图的制作。 参考文献 孟洛明,元峰现代网络管理技术北京:北京邮电大学出版社, 戴美泰,大志忠,邰世祥移动通信內络优化北京:人民邮电出版社 査光明,李正茂蜂房移动通信系统成都:电」科技大学出版社 丁水样,夏巨 图和 三角剖分的计算及应用华中理工大学学报, 张有公线段加权的 图计算机学报 刘少华,程朋根,史文中约束 三角网生成算法研究测绘通报 邵春丽,胡鹏,黄承义 三角网的算法详述及其应用发展前景测绘科学, 李玉龙,朱华华应用 图的点群范围自动识别工程图学学报, () 艾廷华,刘耀保持空间分布特征的点群化简方法测绘学报,

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐