2018年深圳杯B题--无线回传拓扑约束

题目

z.png

1. 输入：

每个地区内，所有站点列表，包括：

• 站点经纬度；
• 站型：RuralStar或蝴蝶站；

各种站型的综合成本，包括：

• 宿主站的综合成本；
• 子站的综合成本；
• 卫星设备成本；

2.约束

输出的拓扑关系，应满足如下限制条件：

• 首跳距离≤20km，之后每跳距离≤10km
• 站点包含RuralStar和蝴蝶站两种不同站型；其中，RuralStar共包含1个扇区，蝴蝶站共包含2个扇区；若该站点为宿主站，则每个扇区第一级最大接入子站数4，最大总接入子站数6；为了简化问题，暂不考虑蝴蝶站的扇区覆盖方向；
• 宿主站之间采用微波连接，最大通信距离为50KM
• 宿主站和子站以及子站之间采用无线回传连接
• 每个子站最多只能有2条无线回传连接；
• 任意子站只能归属一个宿主站，到达所属宿主站有且只有一条通路，且该通路包含的跳数小于等于3
• 任意宿主站都有且只有一颗卫星负责回传，成片连接的宿主站可共享同一颗卫星，但一颗卫星最多只能负担8个成片宿主站的回传数据
• 成片宿主站中，宿主站总数不设上限

3.输出：

按输入数据中站点顺序，输出以下数据：输出文件包含以下两个

Graph.csv
Posi.csv

Graph.csv 包含：

• 二维矩阵表示所有站点间的连接关系，0表示没有连接关系，1表示采用无线回传连接，2表示采用微波连接；

Posi.csv包含以下数组，按列存储：

• 一维数组表示站点类型，0表示子站，1表示宿主站；

在拓扑架构满足约束条件的前提下，

挑战目标1（最高优先级）：更低的总体成本

总体成本：宿主站数量 * 宿主站成本+子站数量 * 子站成本+卫星数量 * 卫星成本
平均成本=总体成本/地区内站点总数
这里，卫星的数量等于Ceil(宿主站数量/8)，Ceil()表示向上取整。

挑战目标2：更低的回传路径损耗

虽然无线回传中存在NLOS影响，但为了简化问题，采用自由空间传播模型估计站点之间的路径损耗，公式如下：

PL=32.5+20lg（D）+20lg（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；

解析