无线回传拓扑规划的研究 软件学院 袁昊 1652676 数学科学学院 宇果 1653478 环境科学与工程学院 万维民 1651449.

Presentation on theme: "无线回传拓扑规划的研究 软件学院 袁昊 1652676 数学科学学院 宇果 1653478 环境科学与工程学院 万维民 1651449."— Presentation transcript:

1 无线回传拓扑规划的研究 软件学院 袁昊 数学科学学院 宇果 环境科学与工程学院 万维民

2 目录 CONTENTS 问题重述 问题分析与假设 模型的建立 模型的评价 参考文献 PART ONE PART TWO PART THREE
PART FOUR PART FIVE

3 PART ONE 问题重述 问题重述 PART ONE

4 PART ONE 问题重述 背景介绍 现代社会，信号无处不在，基站的建设与规划就显得十分重要，也面临着诸多问题。在城区建设基站时，传输光纤成本高且到站率低，而微波信道比例较低。在农村建设基站时，各项花费对运营商又是不小的负担。因此，可以解决城区、农村等场景传输问题的Relay 无线回传方案就具有很好的应用前景。如何部署Relay 无线回传基站以最大化的利用资源，是当前亟需解决的问题。 Relay组网包含宿主基站 DeNB 和中继站 RN 两个节点，把 DeNB 称为宿主站，RN 称为子站，站点又分为 RuralStar 站型和蝴蝶站两种。

5 PART ONE 问题重述 连接方式需要满足以下约束条件： RuralStar 站共包含1个扇区，蝴蝶站共包含2个扇区；若该站点为宿主站，则每个扇区第一级最大接入子站数为4，最大总接入子站数为6 宿主站和与之相连的子站采用无线回传连接，最大通信距离小于 20 Km 宿主站之间采用微波连接，最大通信距离为 50 Km 子站与子站之间采用无线回传连接，最大通信距离为 10 Km 任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的子站数小于等于 3 每个子站最多只能有 2 条无线回传连接 任意宿主站都有且只有一颗卫星负责回传，成片连接的宿主站可共享同一颗卫星，但一颗卫星最多只能负担 8 个成片宿主站的回传数据 成片宿主站中，宿主站总数不设上限

6 PART ONE 问题重述 满足条件的连接如下图所示： RuralStar型宿主站 蝴蝶型宿主站

7 总体成本：宿主站数量×宿主站成本 + 子站数量×子站成本+ 卫星数量×卫星成本 下表为各种传输方式的成本： 宿主站成本 10
PART ONE 问题重述 同时，连接方式需要尽可能满足以下目标： 更低的总体成本 总体成本：宿主站数量×宿主站成本 + 子站数量×子站成本+ 卫星数量×卫星成本 下表为各种传输方式的成本： 宿主站成本 10 子站成本 5 卫星成本 50

8 其中，PL是路径损耗，是两个站点之间的距离，D单位为km，F是发射频率，单位为MHz，这里默认采用900MHz。
PART ONE 问题重述 同时，连接方式需要尽可能满足以下目标： 更低的回传路径损耗 路径损耗的计算公式： 其中，PL是路径损耗，是两个站点之间的距离，D单位为km，F是发射频率，单位为MHz，这里默认采用900MHz。

9 PART TWO 问题分析与假设 问题分析与假设 PART TWO

10 第一部分：基础宿主站的选取 分析： 基本思路： 1.减少卫星数量：8个成片宿主站最多 2.减少宿主站数量：蝴蝶站比RuralStar站划算
PART TWO 问题分析与假设 第一部分：基础宿主站的选取 分析： 1.减少卫星数量：8个成片宿主站最多 2.减少宿主站数量：蝴蝶站比RuralStar站划算 3.在一些较特殊的情况下，站点的类型是可以确定的 基本思路： 1.选取：从蝴蝶站入手，引入DFS 算法（深度优先搜索算法），运用Python软件编程进行合理筛选，找出所有能成片（距离在50KM以内）的蝴蝶站片区，将它们连成片 2.添加：在未确认为主站的蝴蝶站中，找到周围 20 KM内RuralStar站数量多于4的蝴蝶站，将该蝴蝶站选为主站，连入片区 （成片宿主站：任两个宿主站可直接或经其他宿主站由微波相连）

11 基本思路 3.排除：如果有成片宿主站数量大于8的片区，则对它们进行逐个排除研究 （ⅰ.成片宿主站间距由近到远至20km
PART TWO 问题分析与假设 基本思路 3.排除：如果有成片宿主站数量大于8的片区，则对它们进行逐个排除研究 （ⅰ.成片宿主站间距由近到远至20km ⅱ周围20km内RuralStar站数量由少到多） 4.添加：对RuralStar站和非主站蝴蝶站，若20 KM范围内没有其他站点，则该站被选为主站（必须） 5.添加：对RuralStar站和非主站蝴蝶站，若40Km范围内没有已经确定的主站，则该站被选为主站（必须） 经过这五步，确定的全部宿主站称为“基础宿主站”

12 第二部分：主站--子站、子站--子站连接方式的判定
PART TWO 问题分析与假设 第二部分：主站--子站、子站--子站连接方式的判定 分析： 对于子站的连接，最主要的目标是减小损耗，即确定总路径最短的连接方式 基本思路： 1.从主站出发，在首跳距离20Km范围内的子站全部直接连入，如果多于扇区最大可接入数量，则进行随机舍弃 2.依次对20Km、30Km、40Km内未连入的子站运用修改过的Dijkstra算法（加入题目约束条件），可以求出符合条件的最短路径 （跳：宿主站与子站、子站与子站之间的无线回传 首跳：从宿主站出发的第一跳 跳数：子站到相连宿主站经过的无线回传段数 ）

13 第三部分：对剩余站点的筛选和连接规划 分析： 基本思路： 在以上两步结束后，会有少数未确认类型也未接入系统的站点存在。
PART TWO 问题分析与假设 第三部分：对剩余站点的筛选和连接规划 分析： 在以上两步结束后，会有少数未确认类型也未接入系统的站点存在。 针对这些站点，沿用前两部分的思想进行循环操作。 基本思路： 1.适当降低选取宿主站的标准，仍用DFS算法从系统外的站点中确定出一批宿主站 2.同样运用Dijkstra算法找到最优的路径 3.如果剩余站点较多，则重复以上操作 （系统：已选定的所有宿主站和已接入的子站全体）

14 模型的假设： 1.（1） 假设题中所有数据真实可靠 （2） 不考虑宿主站扇区方向对连接的影响
PART TWO 问题分析与假设 模型的假设： 1.（1） 假设题中所有数据真实可靠 （2） 不考虑宿主站扇区方向对连接的影响 2.（1） 假设站点类型（RuralStar站或蝴蝶站）对站点的分布无影响 （2） 假设站点分布有一定的聚集性，即大多数站点间距在合理范围内， 不存在极其分散而完全无法成片的情况 （3） 假设两种类型的站点都占有一定的比例，不存在RuralStar站或蝴蝶 站极少的情况 3. 假设第二步子站的连接中，任一子站的连接对其他子站连接方式产 生的影响不会影响全系统无线回传总路径长度。

15 PART THREE 模型的建立 模型的建立 PART THREE

16 一、符号说明： Bi:第i个蝴蝶站 Ri:第i个RuralStar站 v(i):站点纬度 u(i):站点经度
PART THREE 模型的建立 一、符号说明： Bi:第i个蝴蝶站 Ri:第i个RuralStar站 v(i):站点纬度 u(i):站点经度 BRi,j:第i个蝴蝶站的第j个RuralStar站间的距离 BB:蝴蝶站间的距离矩阵 BBlist:蝴蝶站间的连通分量矩阵 BRAll:所有站点间的距离矩阵 around_r_list:各宿主站周围40km内所有RuralStar站的 编号组成的矩阵 dist:到片区内某个站点由近及远列出便于查找站点的字典 cost:各宿主站周围区域内各子站到该宿主站的距离矩阵 parents:父站矩阵 （父站：与子站直接相连的上级站点）

17 对于图（E，V），深度优先搜索算法的时间复杂度为 O（E+V）
PART THREE 模型的建立 深度优先搜索算法（DFS）是一种用于遍历数据结构树或图的算法，由约翰·E·霍普克洛夫特（John E. Hopcroft）发明。其步骤简要为：随机选取一个节点作为起点，然后沿着图的分枝尽可能向下搜索到最底层，再回溯到上一个分枝的节点，直到搜索完全。 对于图（E，V），深度优先搜索算法的时间复杂度为 O（E+V）

18 由给出的蝴蝶站的经纬度，用 Python软件计算出蝴蝶站间的距离），并储存为蝴蝶站距离矩阵
PART THREE 模型的建立 成片基础宿主站的选取 由给出的蝴蝶站的经纬度，用 Python软件计算出蝴蝶站间的距离），并储存为蝴蝶站距离矩阵 再使用 深度优先搜索算法，对蝴蝶站之间的距离矩阵BB 计算其连通分量，找出距离在50km内的成片蝴蝶站，得到蝴蝶站之间以矩阵表示的聚集关系,记为Bblist 在未确认为主站的蝴蝶站中，找到周围 20 KM内RuralStar站数量多于4的蝴蝶站，将该蝴蝶站选为主站，连入片区

19 对得到的蝴蝶站联通矩阵BBlist 进行筛选。
PART THREE 模型的建立 对得到的蝴蝶站联通矩阵BBlist 进行筛选。 首先遍历蝴蝶站联通矩阵BBlist ，找出联通分量大于8的片区，将里面所有的蝴蝶站标记。 逐个计算给定蝴蝶站与RuralStar 站点距离，统计在首跳半径20km内的RuralStar站点个数并返回。筛除机制为：检查上一步被标记的蝴蝶站，如果有蝴蝶站到其他蝴蝶站的距离小于20 Km，将它剔除。运行后若每一片区连通分量仍大于8，再依次剔除主站周围20 Km 内可连接RuralStar站数最小的站点，直至连通分量等于8 对RuralStar站和非主站蝴蝶站，若20 KM/40Km范围内没有已经确定的主站，则该站被选为主站（必须） 将留在蝴蝶站联通矩阵 BBlist 中的蝴蝶站定义为主站

20 对于 图（E,V）Dijkstra 算法的时间复杂度为 O（V^2）
PART THREE 模型的建立 最短路径算法（Dijkstra 算法）是一种可以解决有向图中的最短路径问题的算法，由荷兰计算机科学家狄克斯特拉（Dijkstra ）于1959 年提出。 步骤简要为：随机选择一个起点，先在与该节点联通的路径中寻找最短的一条，标记与之相连的点；再选择下一点，从所有未标记的点中选择到该点距离最小的点，进行标记。重复该过程，直到所有点都被标记。在这个过程中，到所有顶点的最短路径也被求出。 对于 图（E,V）Dijkstra 算法的时间复杂度为 O（V^2）

21 遍历计算该区域中所有点相互之间的距离，并根据题目给定的数值判断点之间是否构成通路，并将其记录到一个字典中, 记为dist
PART THREE 模型的建立 对每一个特定的宿主站，用Python计算出该主站40 Km内所有的RuralStar站，将这些RuralStar站的编号记录在矩阵中,记为around_r_list 遍历计算该区域中所有点相互之间的距离，并根据题目给定的数值判断点之间是否构成通路，并将其记录到一个字典中, 记为dist 再根据dist 中各点之间的通路情况，构造一个一维矩阵cost，记录该区域中所有点到宿主站的距离，若能形成通路就记为实际的距离，若没有通路则记为999 根据dist 中的数据，计算出与每一个子站相连的上级站点（称为该子站的父站）之间距离的最小值，并将该父站对应的编号记录与一个一维矩阵中，记为parents

22 7.重复上述过程，直到与主站相连的子站数目饱和或者剩下的子站都无法连接到主站位置
PART THREE 模型的建立 5. 从一个主站开始，每次都从与主站相连的且没有被访问过的子站中挑选一个距离主站最短的子站，在dist中查找与该子站相邻的其他子站，并判断这些子站到宿主站之间的距离 6.一旦发现新子站距主站的距离小于之前在主站与子站距离矩阵cost中保存的距离，则更新该子站在cost 中的值为新发现的距离，并将该节点标记为已经访问过，且将父站parents矩阵中对应的站点的值设为父站的编号。同时，判断该站的总跳数，一旦发现跳数等于3，将锁定该站点，禁止它再与别的站点相连接。 7.重复上述过程，直到与主站相连的子站数目饱和或者剩下的子站都无法连接到主站位置

23 本文依然沿用前两部分的思想，即先选取宿主站，再确定子站的连接方式。
PART THREE 模型的建立 对剩余站点的筛选和连接规划 本文依然沿用前两部分的思想，即先选取宿主站，再确定子站的连接方式。 对于这些未连入系统的站点，针对它们具有的稀疏性，本文将结合随机数的情况不断降低前两步的筛查标准。搜索能连成片的蝴蝶站选为宿主站，逐个对它们周围的子站用 Dijkstra 算法进行连接的规划。

24 PART FOUR 模型的评价 模型的评价 PART FOUR

25 优点 问题和不足 模型的推广 PART TWO 论文结构 按照问题的目标和约束条件给出了合理的步骤划分，具有条理性和简洁性。
对距离的测算运用了DFS算法，将对站点的搜索过程进行了优化，结合回溯法、递归法等做到了算法优化程度的最大化。在子站的规划中，结合条件改进Dijkstra算法，最大程度降低了搜索最短路径的程序复杂度。 对未能成片的站点直接进行了前两个步骤改进后的循环。 虽然能够很好地达到目标，但对于剩余的为数不多的站点而言，这样的分步搜索规划过于复杂，本文为了追求最满足目标的理想化结果，忽略了第三步步骤的简化。 而在检验的过程中发现，经过前两步的筛选后，第三步需要考查的站点其实是非常少的。 模型基于站点及连接的规划。除了信号传输以外，在交通、网络、商业等中都可以有广泛的应用。

26 PART FIVE 参考文献 参考文献 PART FIVE

27 PART FIVE 参考文献 1.佚名.迪杰斯特拉算法python实现[EB/OL]. 2. Frank R. Giordano, William P. Fox, Steven B. Horton等.数学建模(第五版)[M].机械工业出版社，2017 3. PAYPAL.Depth-first search (DFS) for undirected graphs[EB/OL]. 4. Anoymous.Depth First Search in Python (including cycles)[EB/OL],   5.黎珍惜,黎家勋.《基于经纬度快速计算两点间距离及测量误差》[J].测绘与空间地理信息，2013 6.麦金尼.《利用 Python 进行数据分析》[M]，机械工业出版社，2014

28 THANK YOU 软件学院 袁昊 数学科学学院 宇果 环境科学与工程学院 万维民