无线回传拓扑规划问题分析 参赛编号：2018017455 1751377 唐明健 1751820 张鹏涛 1752935 杨宇卓.

Presentation on theme: "无线回传拓扑规划问题分析 参赛编号：2018017455 1751377 唐明健 1751820 张鹏涛 1752935 杨宇卓."— Presentation transcript:

1 无线回传拓扑规划问题分析 参赛编号： 唐明健 张鹏涛 杨宇卓

2 问题重述 采用Relay无线回传方案，利用DeNB（宿主站）和RRN（子站）作为无线回传设备，提供无线回传服务，针对8个拓扑约束关系，提出下面两个挑战目标： ①只考虑宿主站、子站、卫星成本的情况下，根据相应的根据成本的计算式，设计1000个左右的候选站点的类型和连接关系，使得成本尽可能低。 ②在第一个问题的基础上，采用自由空间传播模型估计站点之间（子站回传部分）的路径损耗，再对候选站点的类型和连接关系进行规划。

3 问题分析与模型假设 问题1：考虑1000个候选站点在满足一定拓扑约束条件下的成本最优化问题，我们先从局部分析，考虑宿主站个数为1、站型为Rural Star的情况，并先将球面看作平面，便于分析，然后再推广到多个宿主站、两种站型和球面上的连接情况。 问题2：可以分析发现，一个宿主站的子站数目一定的情况下，无线回传的连接数实际上已经确定。然后我们在前面问题的基础上，再通过对无线回传里面的距离约束进行分析。 假设：1.任何传播信号之间不相互干扰。 2.两种站型之间只存在扇区个数和它带来的差异， 除此之外没有其他不同点。 3.假设地球是一个半径为6378km的标准球体。

4 问题一：模型的建立（1） 初步分析： 最理想情况下成本计算公式 C=10𝑚+5 1000−𝑚 +50 𝑚 8 +1 W USD
一个Rural Star宿主站情况讨论 列出数学约束关系式 站型的推广（一个蝴蝶站型的宿主站） 宿主站连接关系确定 初步分析： 最理想情况下成本计算公式 C=10𝑚 −𝑚 𝑚 W USD 𝑚：所有候选站点中宿主站的个数 0≤𝑚≤1000 。 半定性定量分析：应该尽可能增加平均每个宿主站对应的子站的数目。

5 问题一：模型的建立（2） 一个Rural Star宿主站情况讨论 子站数目：6、5、4、3、2、1 进一步讨论：一级子站、二级子站、三级子站
一共20种情况 举两个例子(左边：子站个数为6；右边：子站个数为5） 数学约束关系式的确定:（1）距离排序（2)先决条件 （3）子站与子站的距离约束的确定 一个宿主站下站型的推广：分成两个扇区，对两个扇区分别进行上述一个Rural Star宿主站情况讨论

6 问题一：模型的建立（3） 宿主站点的关系确定： 根据前面的分析，我们找到了比较好的宿主站具体位置
宿主站之间的微波传输关系的规划，考虑如下成本公式： 𝑢 𝑖 , 𝑣 𝑖 ：第𝑖个宿主站的坐标 ；𝐸：全体宿主站集合； 𝑘 𝑗 ：第𝑗个片区拥有宿主站的个数； 𝑎 𝑖 ：第𝑖个宿主站拥有的子站个数 𝑚𝑖𝑛 𝐶 = 𝑢 𝑖 , 𝑣 𝑖 ∈𝐸 𝑎 𝑖 + 𝑗= 𝑘 𝑗 W USD 𝑠.𝑡. 𝑗=1 𝑘 𝑗 + 𝑖=1 𝑎 𝑖 =1000 1≤𝑖≤𝑚,𝑖∈ 𝑁 + 1≤ 𝑘 𝑗 ,0≤ 𝑎 𝑖 ≤ 6, 第𝑖个宿主站是Rural Star 12, 第𝑖个宿主站是蝴蝶站 令 𝑘 𝑗 =8 𝑏 𝑗 + 𝑐 𝑗 𝑏 𝑗 , 𝑐 𝑗 ∈𝑁, 𝑐 𝑗 ≤7 C= 𝑢 𝑖 , 𝑣 𝑖 ∈𝐸 𝑎 𝑖 + 𝑗= 𝑗=1 𝑏 𝑗 +50 𝑗=1 𝑐 𝑗 8 𝑐 𝑗 ≤7，上式中最后一项为0，平均成本与 𝑏 𝑗 的均值成负相关 结论： 𝑑 𝑖𝑗 ≤50，则第𝑖与𝑗个宿主站通过微波相连。

7 问题一：模型的求解 平面坐标到经纬度坐标：MATLAB的distance函数 （1）宿主站与子站、子站与子站无线回传拓扑关系求解
距离矩阵D(i,j)表示 𝑋 𝑖 , 𝑌 𝑖 与 𝑋 𝑗 , 𝑌 𝑗 的距离的平方和 对1000个点一一检验 距离排序：MATLAB的sort命令 从子站数目为6开始对条件是否满足进行检验 如果满足，则将该宿主站记入一维数组Posi，将站点间的连接关系记入Graph 如不满足，则继续对子站数目为5的条件进行检验，以此类推 （2）宿主站与子宿主站微波传输拓扑关系的求解 建立一个宿主站之间的距离矩阵d(i,j)，表示宿主站 𝑢 𝑖 , 𝑣 𝑖 与 𝑢 𝑗 , 𝑣 𝑗 之间距离的平方和 根据前面的分析， 𝑑 𝑖𝑗 ≤2500，则第𝑖与𝑗个宿主站通过微波相连。 在原来的矩阵Graph的基础上，对所有宿主站进行循环，让其中小于2500的取为2

8 问题二：模型的建立与求解（1） 初步分析与计算 最理想情况的成本计算公式： 以一个宿主站站型为Rural Star，它有6个子站的情况为例
C=10𝑚 −𝑚 𝑚 lg D +lg F 以一个宿主站站型为Rural Star，它有6个子站的情况为例 假设下面的计算中，宿主站与子站之间的距离均为20km，子站与子站之间的距离均为10km 以一级子站作为分类标准，分成三种情况 根据公式，计算出三种不同成本为70.74，71.76，72.67 （从左到右分别对应一级子站个数为2，3，4） 结论：随着一级子站个数的增加，回传路径损耗也随之增加 目标：规划使得一级子站个数变少 方法：引入成本变化参数γ，反映子站数目从某一值到子站数目多一个的成本变化率。

9 问题二：模型的建立与求解（2） 进一步计算子站数目为5、4、3最大影响情况 （其他情况：不利于参数求解；比较少见）
回传路径损耗矩阵：𝐴= 设𝐴的列向量组为 𝜂 1 , 𝜂 2 , 𝜂 3 ，近似认为rank A =1 进行数据拟合：令参数γ满足下面的关系：γ 𝜂 1 = 𝜂 2 ,γ 𝜂 2 = 𝜂 3 为合理地考虑 𝜂 1 , 𝜂 2 , 𝜂 3 ，引入权重𝑝，满足： 𝑝γ 𝜂 1 + 1−𝑝 γ 𝜂 2 =𝑝 𝜂 2 + 1−𝑝 𝜂 3 矩阵方程： −1.02𝑝 70.74−1.16𝑝 −1.34𝑝 66.66−1.94𝑝 γ= −0.91𝑝 71.76−1.02𝑝 −1.16𝑝 68.24−1.58𝑝

10 问题二：模型的建立与求解（3） 回传路径损耗参数的求解 （1）权重𝑝的值的确定（拟合）
𝑝可以认为是一级子站个数较少的宿主站个数占所有情况宿主站个数的相对比例 以纬度20°~25°，经度110°~120°的区域，宿主站的子站个数为6且宿主站站型全为Rural Star为例进行拟合 随机生成1000个站点坐标（MATLAB的unifrnd命令） 对问题一的算法进行修改，经过6次的重复随机生成站点和计算，得到6组拟合数据如下： 一级子站个数 实验次数 1 2 3 4 5 6 27 21 12 10 30 15 167 163 161 157 110 111 113 114

11 问题二：模型的建立与求解（4） 设子站数目为4、3、2时6次实验满足条件的宿主站的个数组成的行向量为 χ 1 , χ 2 , χ 3
权重𝑝的计算公式： χ 1 + χ 2 = χ 1 + χ χ 2 + χ 3 𝑝 最小二乘法拟合：设 𝑥 𝑖 , 𝑦 𝑖 1≤𝑖≤6 是需要拟合的六个点 设一个关于权重𝑝的函数：L= 𝑖= 𝑦 𝑖 −𝑝 𝑥 𝑖 2 令 𝑑𝐿 𝑑𝑝 =0，得𝑝= 𝑖=1 6 𝑥 𝑖 𝑦 𝑖 𝑖=1 6 𝑥 𝑖 2 =0.3988 （2）成本变化参数γ的求解 𝑝回代到矩阵方程，令Pγ=Q， P 𝑇 Pγ= P 𝑇 Q P 𝑇 P是一个非零数，γ= P 𝑇 P −1 P 𝑇 Q=1.0179

12 问题二：模型的建立与求解（5） 考虑回传路径损耗的无线回传拓扑规划：
通过成本变化参数γ ，我们将一级子站个数较多的情况下的成本，转变为一级子站个数较少的情况下的成本 以一个扇区的宿主站有6个子站为例 将成本变化参数的幂次乘到距离上： 一级子站数目为4时距离的平方前面乘上 γ 4 ； 一级子站数目为3时距离的平方前面乘上 γ 2 ； 一级子站数目为3时距离的平方前面不乘系数 考虑蝴蝶站的情形： 一级子站个数从8到5，在距离的平方前面依次乘上成本变化参数的幂次 γ 8 , γ 6 , γ 4 , γ 2

13 评价与思考 优点 缺点 思考 解决目标一：简化问题，从少到多 解决目标二：转化问题，引入参数，结果清晰 局部到整体：局部最优化≠整体最优化
外界拓扑关系变化：重新分析，灵活性差 思考 整体与局部分析相结合 在原来基础上，寻找适应于一般情况的分析办法

14 谢谢大家！