基于遗传算法的布站方案规划 2018年同济大学数学建模竞赛答辩 队长：张卢家 队员：王亚伟 张冉 指导教师：王勇智.

Presentation on theme: "基于遗传算法的布站方案规划 2018年同济大学数学建模竞赛答辩 队长：张卢家 队员：王亚伟 张冉 指导教师：王勇智."— Presentation transcript:

1 基于遗传算法的布站方案规划 2018年同济大学数学建模竞赛答辩 队长：张卢家 队员：王亚伟 张冉 指导教师：王勇智

2 2019/4/30 目录 问题分析 模型构建 模型检验 /117

3 2019/4/30 问题分析 根据题目的介绍可知，在部分场景下Relay技术可以代替微波和光纤， 解决传输可达性的问题，并且降低建造成本。在Relay架构中，DeNB 为宿主站，RRN为子站，其中子站可看做为一个中继节点。 宿主站分为RuralStar和蝴蝶站，其中RuralStar最多接入6个子站，蝴 蝶站最多接入12个子站。宿主站首跳距离最远为20KM。宿主站之间 的最大通信距离为50KM。一个卫星最多服务8个成片的宿主站。 由于两种站型成本一致，从降低成本的角度应该尽可能多的采用蝴蝶站，以尽可能少的宿主站连接子站，这样也能减少卫星的使用数量。 由于首跳距离最远为20KM，如果某点周围20KM以内没有其他点，那么该点就没有成为子站的可能，只可能成为宿主站，单独覆盖周围的地区。 宿主站之间的最大通信距离为50KM，由题目知卫星的单价成本是最高的，且其回传特性是服务成片的宿主站，所以除了要降低宿主站的数量之外，宿主站网络最好还是要满足彼此连接的，不要有落单的。 但考虑到Relay技术的性质特点以及实际的环境，我认为这一点是一定满足的，原因如下： Relay技术是一种小型无线网络传输技术，主要应用的场景： （1）存在 4G 覆盖盲区或弱覆盖的区域。 （2）城市高楼遮挡所形成的阴影盲区。 其主要的作用是进行信号的补盲补弱。 而50KM这一距离在实际环境中通常是中心城市到周边县级市的距离，作为一种小型无线回传技术显然不会承担这样长距离的通信任务 图1：Relay基本架构 /117

4 模型基本框架 与一般的适应度函数越大越好不同的 是，本题中的目标是成本最低和损耗 最小，故所得的适应度是越小越好的。
2019/4/30 模型构建 输入待连接站点经纬度数据，首先将经纬度转化为弧度制，再根据球面距离公式计算出各个基站之间的距离。 考虑到站点数量规模（1000左右）而且站点类别类似于0/1规划，如果使用二进制符号0和1所组成的二进制字符串代表布站方案，编码和解码方法简单易行，故采用遗传算法研究本问题。 根据回传拓扑结构约束条件，确定出各个站点之间的连接关系确定连接度，然后以连接度最优作为筛选函数。剔除不合理的站点方案。 模型基本框架 根据各站点之间的连接状态矩阵，分别计算出总体成本、回传路径损耗、两者量纲化加权求和算得整体最优度，再分别以这三个目标函数作为遗传算法中的适应度函数。 考虑到站点数量规模（1000左右）而且站点类别类似于0/1规划，认为采用二进制编码遗传算法是研究本问题的较好方法，使用二进制符号0和1所组成的二值符号集{0,1}，个体基因型是一个二进制符号串。二进制编码和解码方法操作简单易行，交叉、变异等遗传算法操作便于实现。 首先需要确定一个初始化种群，即本问题中各站点布置方案，本文中利用产生 0/1随机数的方式得到初始的种群（30种布站方案）。这样做会产生一些不合理 的布站方案，所得的初始种群中的个体由于 是随机产生的，是否满足问题的实际 意义是一个关键问题。本问题中的站 点网络应该满足的一个基本要求是尽 可能多的站点连接成网，避免出现孤 立的点，如果所得网络中有大量孤立 的点，即使最后计算出的成本很低， 也不具有实际的意义。 为此，在遗传算法的基础上额外设置一个专门衡量网络站点互相连接程度的指标，即连接度。这个指标的目的是剔除不具有实际意义的含有超出限度的大量孤立点的初始个体（布站方案），从而保留下符合基本要求，达到一定连接度的布站方案。经过这一筛选后，再进行个体的适应度计算，即成本和损耗的计算比较。 站点网络要挑战的目标有两个，即最低成本和最低损耗。虽然最低成本具有最高的优先级，但信号损耗直接影响通信质量，而通信质量又是网络服务的基本要求，所以不妨讨论三种情况：利益最大化方案（只考虑最低成本）、信号最优型方案（只考虑最低损耗）以及综合权衡两者的方案，但由于题中已强调成本优先，故应赋予成本项较大的权重。 与一般的适应度函数越大越好不同的 是，本题中的目标是成本最低和损耗 最小，故所得的适应度是越小越好的。 对于分别考虑成本最低和损耗最低， 适应度可以直接比较，得到最优个体。 而综合权衡两者时，要分别进行归一 化处理去量纲，得到在【0,1】的数 值，然后加权。 考虑到成本项具有最高优先，此处赋 权重2/3。损耗赋权重1/3。 交叉和变异过程中，先保留最优个体的信息，然后在种群中以0.5的遗传概率进行随机配对交叉，变异概率取0.2。 图2：模型基本框架 /117

5 模型构建 图3：模型结构图 数据输入 遗传代数结束 输出结果 生成初始种群 否 是 确定各个体方案的站点连接 个体交叉变异
检验各方案的站点连接程度 成本最低方案 综合最优方案 损耗最低方案 否 是 代入适应度函数 连接度是否达到90% 淘汰 图3：模型结构图

6 模型构建 图4：站点连接过程 2019/4/30 否 是 寻找宿主站最近站点 记录为一级子站，并且更新站点连接状态信息 寻找一级子站最近站点
（站点处于未连接状态）&& （距离小于20KM）&& （宿主站接入一级子站数小于8） 否 否 是 寻找二级子站最近站点 记录为二级子站，并且更新站点连接状态信息 （站点处于未连接状态）&& （距离小于10KM）&& （宿主站接入以及子站数小于12） （站点处于未连接状态）&& （距离小于10KM）&& （宿主站接入以及子站数小于12） 站点间连接关系判定从宿主站开始，寻找最近的站点作为一级子站，搜索范围要除去已经成为一级子站、二级子站和三级子站的站点，搜索条件是距离小于 20km 且宿主站连入的一级子站数小于 8（以蝴蝶站上限为限，尽可能多地连接子站）。 此处以距离最近的子站为一级子站，可能会导致子站的不均匀分配，即有的宿主站连入很多子站，而有的宿主站连入的较少。但这样的选择方式更符合实际站点建造过程，而且随着遗传代数的递增，这种效应会逐渐减小。 然后寻找二级子站，出发点是各一级子站。 搜索范围是所有未连接的子站。 搜索条件是距离小于 10km，而且只连一个，且所在宿主站的总接入子站数要小于 12（以蝴蝶站上限） 最后寻找三级子站，出发点是各二级子站。 搜索条件是距离小于 10km，只连一个，且所在宿主站的总接入子站数要小于 12（以蝴蝶站上限）。 是 记录为三级子站，并且更新站点连接状态信息 图4：站点连接过程 /117

7 模型构建 图5：算法流程图 求解球面距离 循环次数结束 输出结果 否 是 确定各级子站 二进制字串以一定概率随机交叉替换和取反
生成0/1随机矩阵（1表示宿主站，0表示子站） 否 是 确定各级子站 二进制字串以一定概率随机交叉替换和取反 计算处于连接状态的站点数 成本最低方案 综合最优方案 损耗最低方案 否 是 计算成本和损耗 连接站点数与总数之比是否达到90% 淘汰 图5：算法流程图

8 2019/4/30 模型检验 目标一：总体成本最低 把总体成本最低作为适应度函数，基于遗传算法求解模型得到如下结果，其中红色圆圈代表宿主站点，黑色圆圈代表子站点。 成本最低布站方案，最低总体成本约为6285万。 图5：总体成本最低布站方案 总体成本的计算公式为 COST= 𝑄 ℎ𝑜𝑠𝑡 ∙ 𝐶𝑂𝑆𝑇 ℎ𝑜𝑠𝑡 + 𝑄 𝑠𝑢𝑏 ∙ 𝐶𝑂𝑆𝑇 𝑠𝑢𝑏 + 𝑄 𝑠𝑎𝑡 ∙ 𝐶𝑂𝑆𝑇 𝑠𝑎𝑡 平均成本为 𝐶𝑂𝑆𝑇 𝑎𝑣𝑒 = 𝐶𝑂𝑆𝑇 𝑆 𝑣𝑎𝑙𝑖𝑑 这里卫星的数量为 𝑄 𝑠𝑎𝑡 =Ceil 𝑄 ℎ𝑜𝑠𝑡 8 其中，Ceil表示向上取整。 为检验模型的有效性，我们到网上搜集到 2013 年上海联通基站的经纬度数据来对模型进行试验。 之所以选择此数据，有以下原因： 1.合理性 电信运营商的站点选址是经过考察，综合各方因素而得出的站点位置，不会出现完全不合常理的数据。 2.规模性 题目中要求站点规模在1000左右，此数据符合了这一条件。 3.背景相近 Relay技术的应用场景包括城区、城镇，所搜集的数据与此是贴合的。 /117

9 2019/4/30 模型检验 目标二：回传路径损耗最低 把回传路径损耗最低作为适应度函数，基于遗传算法求解模型得到如下结果，其中红色圆圈代表宿主站点，黑色圆圈代表子站点。 回传路径损耗最低布站方案：损耗最小约为是26671dB。 图6：回传路径损耗最低布站方案 采用自由空间传播模型的回传路径损耗计算公式 LOSS= ∙ lg D +20∙ lg F 其中距离单位为km，频率单位为MHz，这里F默认采用900MHz，另外， 该路径损耗只考虑子站回传部分，宿主站之间采用微波传输，只需满足距离限制，不计算该损耗。 /117

10 模型检验 目标三：总体成本与回传路径损耗整体最优
2019/4/30 模型检验 目标三：总体成本与回传路径损耗整体最优 把整体最优度最低作为适应度函数，基于遗传算法求解模型得到如下结果，其中红色圆圈代表宿主站点，黑色圆圈代表子站点。 图7：整体最优最低布站方案 经检验，代入实际数据后，模型给出了满足拓扑条件并且90%以上的站点连入网络的布站方案，计算出了最低成本和最低损耗。 整体最优布站方案为：连接度为0.9020>0.9，成本约为6285万，量纲化后值为0.2124，损耗值约为26748 dB，量纲化后值为0.1397，加权求和得整体最优度OPT为0.1882，虽然损耗非最优，但最终适应度最优，故确定为整体最优方案。 整体最优度定义如下 OPT= 𝐶𝑂𝑆𝑇 ′ ∙ 𝐿𝑂𝑆𝑆 ′ ∙ 1 3 /117

11 谢谢聆听！欢迎批评指点！ 2018年同济大学数学建模竞赛答辩 队长：张卢家 队员：王亚伟 张冉 指导教师：王勇智