没有合适的资源?快使用搜索试试~ 我知道了~
图论loyd算法算法-光传送网建模与价值评估.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 16 浏览量
2022-05-01
20:07:26
上传
评论
收藏 2.57MB PDF 举报
温馨提示
试读
38页
图论loyd算法算法-光传送网建模与价值评估.pdf
资源推荐
资源详情
资源评论
1
“华为杯”第十五届中国研究生
数学建模竞赛
题 目 光传送网建模与价值评估
摘 要:
本文针对光传送网的链路,利用二维正太分布的概率模型对不同调制格式
的纠前错误概率进行了估计,并建立了光传输链路的传输性能模型。针对光网
络的规划问题,建立了赋权连通图模型,利用 Prim 算法、最速下降法、Floyd
算法以及模拟退火算法进行优化,进而得到近似全局最优解。针对不等概率的
调制方式提出了一种优化的星座图配置。
针对问题一(1),我们探究 QPSK、8QAM 和 16QAM 三种调制格式,在不同信
噪比 SNR 情况下接收到的调制信号概率分布。利用二维正态分布对接收到的符
号的概率分布进行了建模,在信号功率归一化的约束条件下,对每一类星座图
上的星座点的出现概率以及判决错误概率期望进行了估计,结合每个星座点的
信息熵计算出了纠前错误概率和 SNR 的关系曲线。通过二分法得出了 BER
=0.02 时的 SNR 容限点,对 QPSK、8QAM 和 16QAM 三种调制方式 6.9207、
10.341 和 12.7726。问题一(2),要求计算光链路在符合 SNR 容限情况下最大传
播跨数和最远传播距离。我们建立了光链路传输过程中的信号噪声功率衰减、
增益的动态模型,求解出了在跨长为 80km 时,QPSK、8QAM 和 16QAM 能传输
17,8,4 跨,其最远传输距离为 1360,640,320km;在跨长为 100km 时,
2
QPSK、8QAM 和 16QAM 能传输 6,3,1 跨,其最远传输距离为 600,300,
100km;
针对问题二(1),我们将光传送网规划简化成赋权连通图问题,通过 prim
算法求得 12 个城市的最大生成树,并将剩下的最大价值边加入到传送网里,16
条连接和 33 条连接的最大价值分别为 5174.3和 8418.6。针对问
题二(2),我们结合数学推导和最速下降法编程证明,定性、定量的证明了:
1)城市互连结构里,即使考虑分流机制,也是最大生成树价值最大;
2)添加成树之外的边时三元结构中引入分流机制所得价值比当前最大价值
要低;
3)证明添加成树之外的边时任意元结构中引入分流机制所得价值比当前最
大价值要低。
从而在最大生成树基础上,综合考虑城市两两间最低通信容量
,得到引入中转分流节点下 16 条连接和 33 条连接的城市最大网络价值
分别为 7069.9和 19151.46,16 条连接和 33 条连接的省份最大网
络价值分别为 23510.5和 64254.4。针对问题二(3),我们综合考
虑了城市距离、人口、发达程度、辐射范围以及地理条件,既考虑了点单独的信
息,又考虑了点与点之间的邻域信息,提出了新的目标价值函数
。并根据此目标函数结合 Floyd 算法以及模拟退火算
法,给出了 16 条连接和 33 条连接的最优网络连接图,使得华南地区以武汉和上
海为中心,华北地区以北京为中心,并且对于西南地区以及新疆的规划也都更加
合理,同时也保持连通所必要的跨地形阶梯连接。
针对问题三,我们探寻满足信息熵为 3bit 的 16QAM 的基础上优化星座图上
星座点的位置分布以及出现概率,以达到性能的最优。根据对问题的分析,我
9QAM,利用对二的负幂次方概率的穷举式搜索方式,确定了一组符合条件星座图
概率分布(
),结合格雷码编码优化出了一种非等概率的 9QAM 的调
制方式。其 SNR 容限点为,较题设的 8QAM 调制方式优化了 1.6 dB。
关键词:光传送网规划 二维高斯分布 最大生成树 Floyd 算法 模拟退火算法
QAM 调制
3
1 问题重述
1.1 问题背景
2009 年诺贝尔物理学奖授予了英籍华人高锟(Charles K. Kao)博士,以表彰
他对光纤通信发展所做出的贡献,诺贝尔奖委员会在给公众的公开信中写到:
“当诺贝尔物理学奖宣布的时候,世界大部分地方几乎瞬间收到了这条信息…文
字、语音和视频信号沿着光纤在世界各地来回传输,几乎瞬时地被微小而便捷的
设备接收,人们已经把这种情况当做习惯。光纤通信正是整个通信领域急速发展
的前提。”
从诞生至今,50 多年里基于数字光纤通信技术的光传送网构建起了全球通信
的骨架。从城市内的传输,直到跨越大洋的传输,光传送网为人类提供了大容量、
高可靠性和低能耗的信息传输管道,人类对通信容量的追求也成为光传送技术发
展的源源不断的动力。
光传送网的规划与建设是运营商、设备商以及政府必须考虑的课题。光传送
的基本规律是——在相同技术条件下传输的容量会随着传输距离增加而减小。网
络规划者需要在有限资源的条件下,综合考虑传输距离,传输容量、网络拓扑等
各种因素,以最大化网络的价值。本课题中,请你们站在上述角度,从底层物理
出发为光传送链路建模,制定光传送网规划,探索光传送网有关规律。
1.2 需要解决的问题
1.2.1 问题一:光传送链路建模
现代数字传输系统可认为是对 0101 二进制序列进行编码传输的系统,1 个
二进制的 0 或 1 称为 1 个比特(bit)。 无论是语音、视频还是任何类型的消息,
都可以数字化为一串串”0101…”的二进制比特序列,经编码并调制为某个“载体
信号”后,再经过特定的“信道”(信息的通道)传输到目的地。图 1 中给出了
简化的模型。在光纤通信中,光纤就是信道,光纤传输的光波就是信息的载体。
信道中无法避免的噪声可能导致最终接收的二进制序列中比特出错,即产生误码。
接收机
解调制
噪声
信号
接收
信号
发送序列
0101010...
接收序列
0101110...
发射机
编码调制
图 1-1 简化后的数字传输模型
二进制序列通常需要将 K 个比特作为一个“符号”进行传输,每个符号有
个不同状态。光传输利用光波的复振幅承载信号,因此可用复平面上不同的点来
更多数学建模资料请关注微店店铺“数学建模学习交流”
https://k.weidian.com/RHO6PSpA
4
对应不同的符号状态,这种将符号状态画在复平面上的图称为“星座图”,图上
的点称为“星座点”。如图 2(a)所示的 QPSK(Quadrature Phase Shift Keying)调
制,经过信道叠加噪声和接收机处理后,接收端的星座图不再是理想的四个点,
而是会出现扩散。当接收机收到 1 个符号时,就将发送的符号判定为离该符号最
近的星座点。显然,如果噪声过大,接收到的符号可能被判错从而产生误码,如
图 2(b)中的蓝点。误码率(Bit Error Ratio, BER)定义为错误的比特数占总传输
比特数的比例,例如传输了 50 个符号共 100 个比特,其中有 1 个符号被误判为
相邻的符号,错误了 1 个 bit,则误码率为 0.01。BER 是衡量通信系统性能的最
根本指标,采用纠错编码,只要纠前 BER 小于某个门限值(BER 容限点),纠错
编码后就能实现纠后误码率为零的传输,本题中 BER 都是指纠错编码前的误码
率(纠前 BER)。
I
Q
10 11
I
Q
00
01
1110
0100
(a)
(b)
噪声
图 1-2 星座图与噪声导致误码的示意图
r
k
I
Q
s
k
n
k
图 1-3 信号和噪声的相关定义示意图
000
001
010
011
100
101
110
111
1110
0110
00101010
1100
0100
00001000
1101
0101
00011001
1111
0111
0011
1011
Q
I
I
Q
00 01
10
11
I
Q
QPSK
8QAM
16QAM
图 1-4 三种调制格式的编码方案
5
星座图的编码分布模式也称为调制格式,对于给定的调制格式,BER 和 SNR
呈一一对应的关系,纠前 BER 门限对应的 SNR 记做“SNR 容限点”。给出图 1-
4 中所示的三种调制格式及编码方式(相邻星座点距离相等),每个符号等概率
出现,分别称为 QPSK,8QAM (Quadrature Amplitude Modulation, QAM),16QAM。
题目要求计算出 BER 与 SNR 的关系曲线,以及当 BER=0.02 时 SNR 容限点。
光传输链路由多个相同跨段的级联而成。如图 4 所示,几十 km 的光纤和一
个放大器构成了 1 个跨段。信号每传输 15km,光功率衰减一半,经过一段光纤
传输后,需要用放大器对光功率进行补偿。在信号、噪声同步放大的同时,放大
器还引入自发辐射噪声;另一方面,光纤作为一种传输介质,其本身的非线性效
应也会等效地引入噪声。其等效噪声功率与入纤功率近似呈平方关系,光纤功率
为 1mW 时的非线性噪声约等于单个放大器噪声的 2/3。放大器的自发辐射噪声
和光纤的非线性噪声都是加性噪声。
发射机
接收机
放大器
放大器
光纤
光纤
...
一跨
图 1-5 基本的光传输链路模型
本问题需要求解当单跨传输距离为 80km 和 100km 两种情况,以纠前误码
率 0.02 为门限,图 1-5 给出的传输格式最远的传输距离(每跨距离×跨段数量)。
1.2.2 问题二:光传送网规划
表 1 给出进一步优化升级后的三种典型光传输设备参数。考虑到通信网络的
目的是把更多的人更充分地连接到一起,我们按照如下方式定义网络的价值:
1)每条直接连接两个城市/区域的链路当做 1 个连接,每个连接的价值定义
为传输的容量与连接区域人口数的乘积(取两区域人口数乘积的 0.5 次
方)
2)网络的价值则是所有连接价值的加权和
网络价值 权重 容量 人口
以图 5 给出的北京、南京、上海三座城市为例,若相互之间均互有连接,根
据城市的距离可得出能传输的容量。若每条链路的权重为 1,进而再由人口算出
网络价值(Network Value, NV)为
其中 m 代表百万人(million),
, 该网络的连接数为 3。
然而由于资源等因素制约,网络往往并不能让每对节点都直接连接,但可通
剩余37页未读,继续阅读
资源评论
普通网友
- 粉丝: 12w+
- 资源: 9335
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功