B题-无线回传拓扑规划（3人完成）
在城区建设基站，传输光纤部署最后一公里的成本高，光纤到站率低，全球综合来看低于60%；如果使用微波传输，由于微波只能在LOS（视距）场景下部署，而城区场景中LOS信道比例低于50%。
在农村网建设基站，单站业务量低，收入低，ROI（投资回报率）差，运营商建站对成本较为敏感。卫星传输租金、光纤传输建设费用对于运营商是很大的负担，而如果使用微波传输，对于相当一部分站点需要提升铁塔高度来满足微波的LOS场景要求，铁塔费用的增加对于运营商来说同样是不小的负担。
Relay无线回传方案利用FDD LTE或TDDLTE制式承载来为站点回传，相对微波有较强的NLOS（非视距）传输能力，可以解决城区、农网等场景下的传统传输方式不可达的问题，同时在部分场景下也可以替代微波，有效降低站高，节省加站费用。
图1 Relay架构
RRN（eRelay Remote Node），是Relay方案中的无线回传设备，它用于为基站提供无线回传服务。如图1所示。Relay组网包含宿主基站DeNB和中继站RN两个逻辑节点：
DeNB是在普通基站（DeNB）上增加了Relay功能，DeNB支持普通手机（UE）接入，也支持RRN的接入；
RN包括RRN和ReBTS两部分。RRN通过无线信号接入DeNB并建立空口承载；ReBTS可供覆盖范围内的UE接入；ReBTS的传输由RRN提供
为了方便理解，这里分别将DeNB和RRN称作宿主站和子站，一个宿主基站通常可以有1~3个宿主小区，分别覆盖不同的方向（可理解为扇区的定义），如图2所示。图2中方块代表子站，每个宿主小区可以接入一定数量的子站，子站与子站之间可以级联（即多跳），但跳数有限制。
图2 Relay拓扑关系示意图
2.1 任务简述
本任务中，在给定一个地区中候选站点的位置分布的情况下，参赛队伍需要根据站点间的相互位置、站点间拓扑关系限制等条件，在满足一定回传质量（本次任务仅根据宿主站与子站的距离是否满足某门限来判断是否满足最低回传质量要求。而实际Relay部署时，影响回传质量的因素包括距离、地形阻挡、普通手机接入影响、ReBTS干扰、相邻基站干扰等多种复杂因素）的前提下，设计成本最优的部站方案，包括：
候选站点是安装子站还是宿主站？
候选站点间的连接关系如何？
结合现网中对于无线回传拓扑规划问题的具体需求，算法还应该具有以下特点：算法收敛速度快、尽可能覆盖更多的站点。
2.2 输入输出
每个地区内，所有站点列表，包括：
站点经纬度；
站型：RuralStar或蝴蝶站；
各种站型的综合成本，包括：
宿主站的综合成本；
子站的综合成本；
卫星设备成本；
输出的拓扑关系，应满足如下限制条件：
首跳距离≤20km，之后每跳距离≤10km
站点包含RuralStar和蝴蝶站两种不同站型；其中，RuralStar共包含1个扇区，蝴蝶站共包含2个扇区；若该站点为宿主站，则每个扇区第一级最大接入子站数4，最大总接入子站数6；为了简化问题，暂不考虑蝴蝶站的扇区覆盖方向；
宿主站之间采用微波连接，最大通信距离为50KM
宿主站和子站以及子站之间采用无线回传连接
每个子站最多只能有2条无线回传连接；
任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3
任意宿主站都有且只有一颗卫星负责回传，成片连接的宿主站可共享同一颗卫星，但一颗卫星最多只能负担8个成片宿主站的回传数据
成片宿主站中，宿主站总数不设上限
例如，如下图所示的连接关系中
宿主小区2不满足“每个扇区第一级最大接入数4，最大总接入数6”
子站1、子站2不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路”
子站4不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3”中的“跳数小于等于3”
子站5不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3”中的“任意子站只能归属一个宿主站”
上图连接关系可修改如下（前提是其它约束条件也满足），即可满足约束条件：
按输入数据中站点顺序，输出以下数据：
输出文件包含以下两个
二维矩阵表示所有站点间的连接关系，0表示没有连接关系，1表示采用无线回传连接，2表示采用微波连接；
包含以下数组，按列存储：
一维数组表示站点类型，0表示子站，1表示宿主站；
如上图所示的连接关系，以上数组将表述为：
算法效率：5分钟内
站点规模：1000站点左右
2.2 挑战目标
在拓扑架构满足约束条件的前提下，
挑战目标1（最高优先级）：更低的总体成本
总体成本：宿主站数量*宿主站成本+子站数量*子站成本+卫星数量*卫星成本
平均成本=总体成本/地区内站点总数
这里，卫星的数量等于Ceil(宿主站数量/8)，Ceil()表示向上取整。
下表为各种传输方式的成本，单位：W USD
宿主站成本
挑战目标2：更低的回传路径损耗
虽然无线回传中存在NLOS影响，但为了简化问题，采用自由空间传播模型估计站点之间的路径损耗，公式如下：
PL=32.5+20*lg（D）+20*lg（F）
其中，PL是路径损耗，是两个站点之间的距离，D单位为km，F是发射频率，单位为MHz，这里默认采用900MHz。
系统平均损耗=所有无线回传连接的损耗之和/无线回传连接数
需要注意，该路径损耗只考虑子站回传部分，宿主站之间采用微波传输，只需满足距离限制，不计算该损耗。
附：球面距离公式
计算球面两点间距离的公式，设A点纬度β1，经度α1；B点纬度β2，经度α2，则距离S为：
S=R·arc cos[cosβ1cosβ2cos（α1-α2）+sinβ1sinβ2]
其中R为地球半径，本题中取6378km；
无线回传拓扑规划（优化算法+并查集+贪心）
背景描述：
为参加2018年9月的研究生数学建模竞赛，组队参加由学校组织的数学建模小组模拟赛。赛题据说是深圳2018年的数学建模比赛。经过讨论，我们最终选择了B题-无线回传拓扑规划。
一开始，我们...
拓扑基础题
有N个比赛队（1&=N&=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每...
Hyper-V 高可用性 (网络规划及拓扑篇)
上一篇文章解了存储的概念后呢，我们再来了解一些Hyper-V群集的另一个重要的方面，网络
在Hyper-V中有三种类型的网络：外部、内部和私有网络
外部：此类型的网络可以支持物理网络的访问
内部：此类...
2018深圳杯数学建模A题
2018思特奇杯数学建模竞赛题目（请严格遵守对论文格式的统一要求）A题-人才吸引力评价模型研究
在世界各国和全国各地都加大争夺人才的背景下，一个城市要保持其竞争活力和创新力，必须与时俱进地但...
没有更多推荐了，豆丁微信公众号
君，已阅读到文档的结尾了呢~~
广告剩余8秒
文档加载中
江苏移动LTE题库
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
江苏移动LTE题库
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口这是我第一次参加数学建模比赛，经过和队友几天（特别是在辛酸的520日)的通力合作，最终拿了个三等奖，嗯，勉强还行。
废话不多说，来看题目和题解。
题目：无限拓扑回传规划
在城区建设基站，传输光纤部署最后一公里的成本高，光纤到站率低，全球综合来看低于60%；如果使用微波传输，由于微波只能在LOS（视距）场景下部署，而城区场景中LOS信道比例低于50%。
在农村网建设基站，单站业务量低，收入低，ROI（投资回报率）差，运营商建站对成本较为敏感。卫星传输租金、光纤传输建设费用对于运营商是很大的负担，而如果使用微波传输，对于相当一部分站点需要提升铁塔高度来满足微波的LOS场景要求，铁塔费用的增加对于运营商来说同样是不小的负担。
Relay无线回传方案利用FDD LTE或TDDLTE制式承载来为站点回传，相对微波有较强的NLOS（非视距）传输能力，可以解决城区、农网等场景下的传统传输方式不可达的问题，同时在部分场景下也可以替代微波，有效降低站高，节省加站费用。
图1 Relay架构
RRN（eRelay Remote Node），是Relay方案中的无线回传设备，它用于为基站提供无线回传服务。如图1所示。Relay组网包含宿主基站DeNB和中继站RN两个逻辑节点
DeNB是在普通基站（DeNB）上增加了Relay功能，DeNB支持普通手机（UE）接入，也支持RRN的接入；
RN包括RRN和ReBTS两部分。RRN通过无线信号接入DeNB并建立空口承载；ReBTS可供覆盖范围内的UE接入；ReBTS的传输由RRN提供
为了方便理解，这里分别将DeNB和RRN称作宿主站和子站，一个宿主基站通常可以有1~3个宿主小区，分别覆盖不同的方向（可理解为扇区的定义），如图2所示。图2中方块代表子站，每个宿主小区可以接入一定数量的子站，子站与子站之间可以级联（即多跳），但跳数有限制。
图2 Relay拓扑关系示意图
2.1 任务简述
本任务中，在给定一个地区中候选站点的位置分布的情况下，参赛队伍需要根据站点间的相互位置、站点间拓扑关系限制等条件，在满足一定回传质量（本次任务仅根据宿主站与子站的距离是否满足某门限来判断是否满足最低回传质量要求。而实际Relay部署时，影响回传质量的因素包括距离、地形阻挡、普通手机接入影响、ReBTS干扰、相邻基站干扰等多种复杂因素）的前提下，设计成本最优的部站方案，包括：
候选站点是安装子站还是宿主站？
候选站点间的连接关系如何？
结合现网中对于无线回传拓扑规划问题的具体需求，算法还应该具有以下特点：算法收敛速度快、尽可能覆盖更多的站点。
2.2 输入输出
每个地区内，所有站点列表，包括：
站点经纬度；
站型：RuralStar或蝴蝶站；
各种站型的综合成本，包括：
宿主站的综合成本；
子站的综合成本；
卫星设备成本；
输出的拓扑关系，应满足如下限制条件：
首跳距离≤20km，之后每跳距离≤10km
站点包含RuralStar和蝴蝶站两种不同站型；其中，RuralStar共包含1个扇区，蝴蝶站共包含2个扇区；若该站点为宿主站，则每个扇区第一级最大接入子站数4，最大总接入子站数6；为了简化问题，暂不考虑蝴蝶站的扇区覆盖方向；
宿主站之间采用微波连接，最大通信距离为50KM
宿主站和子站以及子站之间采用无线回传连接
每个子站最多只能有2条无线回传连接；
任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3
任意宿主站都有且只有一颗卫星负责回传，成片连接的宿主站可共享同一颗卫星，但一颗卫星最多只能负担8个成片宿主站的回传数据
成片宿主站中，宿主站总数不设上限
例如，如下图所示的连接关系中
宿主小区2不满足“每个扇区第一级最大接入数4，最大总接入数6”
子站1、子站2不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路”
子站4不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3”中的“跳数小于等于3”
子站5不满足“任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3”中的“任意子站只能归属一个宿主站”
上图连接关系可修改如下（前提是其它约束条件也满足），即可满足约束条件：
按输入数据中站点顺序，输出以下数据：
输出文件包含以下两个
二维矩阵表示所有站点间的连接关系，0表示没有连接关系，1表示采用无线回传连接，2表示采用微波连接；
包含以下数组，按列存储：
一维数组表示站点类型，0表示子站，1表示宿主站；
如上图所示的连接关系，以上数组将表述为：
算法效率：5分钟内
站点规模：1000站点左右
2.2 挑战目标
在拓扑架构满足约束条件的前提下，
挑战目标1（最高优先级）：更低的总体成本
总体成本：宿主站数量*宿主站成本+子站数量*子站成本+卫星数量*卫星成本
平均成本=总体成本/地区内站点总数
这里，卫星的数量等于Ceil(宿主站数量/8)，Ceil()表示向上取整。
下表为各种传输方式的成本，单位：W USD
宿主站成本
挑战目标2：更低的回传路径损耗
虽然无线回传中存在NLOS影响，但为了简化问题，采用自由空间传播模型估计站点之间的路径损耗，公式如下：
PL=32.5+20*lg（D）+20*lg（F）
其中，PL是路径损耗，是两个站点之间的距离，D单位为km，F是发射频率，单位为MHz，这里默认采用900MHz。
系统平均损耗=所有无线回传连接的损耗之和/无线回传连接数
需要注意，该路径损耗只考虑子站回传部分，宿主站之间采用微波传输，只需满足距离限制，不计算该损耗。
附：球面距离公式
计算球面两点间距离的公式，设A点纬度β1，经度α1；B点纬度β2，经度α2，则距离S为：
S=R·arc cos[cosβ1cosβ2cos（α1-α2）+sinβ1sinβ2]
其中R为地球半径，本题中取6378km；
因为考虑到分组，最后采用了人工智能里常见的K-Means聚类方法来把子站按照距离最近原则分组。本人当时比较喜欢java，所有代码均采用java语言编写。
在具体实现过程中，所有输入数据均是符合条件的随机值，1000个站点大致随机分布在东经112.98~113.98和北纬28.12~28.24的公共区域内，1000个站点，每组最多12个，大致分为84组，这里就有两种思路了
在第一次分区的时候不加限制每个区子站数，这样就可能有的区子站数会超过12个，超过12个的区再分簇，以此类推，直至符合条件，将所有符合条件的分区加入结果集。
在第一次分区的时候限制每个区子站数最多为12个。
细细体会，觉得第一种思路好些，于是最后完成了思路一，思路二也做了大半，最后提交的是思路一。
代码里有丰富的注释，代码、算法思想说明、运算结果结果csv文件都已上传到github,，欢迎star,有问题欢迎评论
深圳杯---无线回传拓扑规划
B题-无线回传拓扑规划（3人完成）
在城区建设基站，传输光纤部署最后一公里的成本高，光纤到站率低，全球综合来看低于60%；如果使用微波传输，由于微波只能在LOS（视距）场景下部署，而...
无线回传拓扑规划（优化算法+并查集+贪心）
背景描述：
为参加2018年9月的研究生数学建模竞赛，组队参加由学校组织的数学建模小组模拟赛。赛题据说是深圳2018年的数学建模比赛。经过讨论，我们最终选择了B题-无线回传拓扑规划。
一开始，我们...
2018深圳杯数学建模A题
2018思特奇杯数学建模竞赛题目（请严格遵守对论文格式的统一要求）A题-人才吸引力评价模型研究
在世界各国和全国各地都加大争夺人才的背景下，一个城市要保持其竞争活力和创新力，必须与时俱进地但...
2016深圳杯D题 思路
离2016年深圳杯比赛已经过去半年多了，当时我们获得了国家二等奖，楼主对具体思路也记得不大清了。简单说一下当时的思路吧。
题目不再赘述。。。
本题神坑，出题人神坑。
第一问，构建人体动态量化模型...
路线规划算法设计要点
路线规划算法设计要点
( 10:42:14)
2018年数学建模校赛
最近每个周末都有好多作业，上周趁有空就参加了数学建模校赛，就用今年“深圳杯”数学建模挑战赛作题目。连续打了两天，最后已经没有时间做结果分析了，写的论文也不算理想，不过我觉得模型做得还不错，所以想记录一...
这是网上看到的一个比较清晰的入门的拓扑算法
链接：http://www.cnblogs.com/dolphin0520/archive//2017737.html
感觉可以...
没有更多推荐了，豆丁微信公众号
君，已阅读到文档的结尾了呢~~
全国通用移动网上大学L2考试题库(最新全版-包括基站、直放站室分WLAN、集客家客、传输线路、动环)
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
全国通用移动网上大学L2考试题库(最新全版-包括基站、直放站室分WLAN、集客家客、传输线路、动环)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口豆丁微信公众号
君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
代维基站设备及配套L1
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口