通信网理论基础Projrct

是G的真子图，记为G’ G 。
c.若V’=V，E’ E，即子图G’包含G的所有端，则称
G’是G的生成子图。
21
v1
v2
v1
v2
v1
v2
v3 v5 v4 (a) 原图 v5 v4 (b) 真子图 图与子图 v5 v4 (c) 生成子图
v3
22
4. 最大连通子图：若图G’是图G的一个连通子图，但再加上 一个属于原图G的任何一个其他元素，图G就失去了连通性，成 为非连通图，则图G’叫图G最大连通子图。最大连通子图并不是 极大连通子图。 （三）几种特殊的图
树枝集：图G的生成树上的边组成树枝集。
连枝：生成树之外的边称为连枝，连枝的边集称为连枝集或 称为树补。
具有n个端、m条边的连通图，生成树T有n-1条树枝和 m-n+1条连枝。
29
图G的阶ρ：连通图G的生成树T的树枝数称为图G的阶，记 为ρ。如果图G有n个端，则：ρ（G）=ρ=n-1。 图G的空度μ：连枝集的连枝数称为图G的空度，记为μ。 当G有m条边时，有μ(G)= μ=|G-T|=m-n+1 m=ρ+μ
v5
2.7 5.3
v2
v4
1.8
v3
10
二、图的连通性 （一）相关概念
1.自环、重边和度数
自环：若与一个边er相关联的两个端是同一个端点,则称边er 为自环。
重边：在无向图中与同一对端点关联的两条或两条以上的边 称为重边。在有向图中与同一对端点关联且方向相同 的两条或两条以上的边称为重边。没有自环和重边的 图称为简单图。
ρ：表示生成树的大小，取决于G 中的端点。 μ：
（1）表示生成树覆盖该图的程度。μ越小，覆盖度越高，μ=0表 示图G就是树。

9 prob. that all n channels are occupied at an arbitrary time = the fraction of time that all n channels are occupied
9 容易计算、但不易统计和测量
¾呼叫阻塞率：n 次呼叫中k 次被阻塞的概率
λi-2
λi-1
λi
λi+1
i-1
i
i+1
μi-1
μi
μi+1
μi+2
2004-3-31
牛志升@清华大学
23
到达率和服务率可变的M/M/1排队系统
转移率矩阵
全局平衡 方程式
局域平衡 方程式
平稳状态 概率
2004-3-31
牛志升@清华大学
24
M/M/1排队系统-最基本的排队模型
平稳状态转移图
λ
λ
λ
λ is called the arrival rate
2004-3-31
牛志升@清华大学
9
Service-Time Process
n +1 n n −1
sn t
sn : service time of customer n at the server
{sn , n ≥ 1} is a stochastic process
pi 迭代后可得
i
其中：
2004-3-31
牛志升@清华大学
27
2004-3-31
牛志升@清华大学
28
M/M/1排队系统的性能分析
队列长度的均值/方差
等待/滞留时间＝？
¾ 求解等待时间需要顾客到达时刻的状态概率！

通信网理论基础
1 计算机通信网理论基础
计算机通信网理论是计算机网络的理论基础，它的主要内容包括网络结构、网络协议、通信协议、网络通信处理、信息安全、信道分析、信息管理等理论。

通信网理论与计算机网络相结合，形成了计算机网络技术的复合体。

网络结构
网络结构是计算机网络理论中最重要的一部分，它指定了计算机网络的拓扑结构、路由选择、网络拓扑结构、数据传输拓扑结构等，以及数据传输模型、网络分层结构、网络通信的中间节点协议、网络设施的组织结构等。

网络结构为计算机网络提供了基础支撑，并为计算机网络上的数据传输提供可靠的基础保证。

网络协议
网络协议是计算机网络通信的活动规格，协议的存在是为了让计算机网络中的计算机和通信设备之间的沟通双方统一采用一种协议约定进行配合。

有效的网络协议不仅能指导多媒体数据的传输，还能够管理网络服务质量、网络资源使用情况，确保网络通信的可靠性、安全性及有效利用网络资源。

通信协议
通信协议是指在计算机网络中节点之间传送数据、发送控制信息
而达成沟通的一种协议。

其主要作用是规范双方通信的格式，统一通
信双方的语言，建立沟通的桥梁，使多台计算机可以组成网络工作。

它可以定义多媒体数据传输的方式，也可以对网络资源分配、网络访问、网络状态监视等等进行管理。

计算机通信网理论是计算机网络技术的重要理论基础，网络结构、网络协议和通信协议都必须有效实现才能使计算机网络具有安全、可靠、有效的通信能力，使计算机网络发挥更大的作用。

(
m
m
)
1
m
3
46
Байду номын сангаас
ρ(x,y) ρ 常量 • 这包含了欧式距离和矩形线距离 • 当 m 2 时 为欧式距离 • 当 m 1 时 为矩形线距离 ∆ 最佳区域的边界方程为
(x
m
+ y
m
或 y = a
(
)
1
m
= a −x
m
m
)
1
m
(x
m
+ y
m
)
1
m
= a
或 y = a
(
m
−x
m
)
1
m
• 这结果与 ρ(x,y)的形式无关 • 亦即 最佳区域的形状只与距离测度的定义有关 ∆ 再利用 ρ(x,y)来求 x 轴上的截距 即区域的大小 • 由于最佳区域的对称性 积分可分四个象限进行 • 它们是相等的 所以有
m = 1时 m = 2时 1 m= 时 2 3C a= 2 ρK 3C a= πρK 9C a= 2ρ
i
[(y w ⋅
i
q
− y i ) ⋅ ∆x q − (x q − xi ) ⋅ ∆y q d qi
3
]
2
≥0
≡ 所以 L 函数是下凸的 L 有极小值 ∆ 令一阶偏导数为零可求得极小值
xq
∑w x = ∑w
i i i i i i i
i
d qi d qi
yq
∑w y = ∑w
i
i
d qi d qi
3
34
i i
1
2
n

2014-4-11
40
图的空度


图的空度μ（G）表示了主树覆盖该联结图的 程度。μ（G）越小，则主树对图的覆盖程度 越高。μ（G）＝0，则表示图就是树，没有 连枝。 图的空度μ（G）还可以表示图G的联结程度。 μ（G）越大，即树的连枝越多，图的联结性 越好。μ（G）＝0时的树，其联结性是最差 的。这是最低的联结性。
2014-4-11
36
树
3、树的分类：树可以分为：根树、星树、 线树等。 4、主树：联结图G，若T ∈ G，即T 是 G 的子图，且T 含有G的所有端，则称T是 G 的主树。
2014-4-11
37
树




注意：主树是图G 的一个子图，G本身 不一定是树。 只有联结图才有主树，并且至少有一个 主树。非联结图没有主树。 有主树的图必为联结图，没有主树的图 一定是非联结图。 图的主树的边称为树枝。非树枝的边称 为连枝。
端：电压、交换机、节点机、路由器、光端机 等； 边：电流、电阻、信道、带宽、速率、流量等；
2014-4-11 13
图与集合
子图：若图A的端集和边集分别为图G的端 集和边集的子集（一部分），则图A是图 G的子图。 记为：A ∈G（图A是图G的子图）； 特例：A = G（图A与图B相等）； 推论：任何图都是自己的子图； 若A∈G，但A ≠ G，则A是G的真子图； 若A∈G，且G∈A，则必有A＝G；
2014-4-11 10
关于边集的讨论
1、图中某一边关联的两端，是同一个元 （端点），则称为自环； 2、无向图中两个端之间存在两条或两条 以上的边，则称为重边。重边的数量并 不限定。重边可以合并，以简化计算。 3、有向图中若重边的方向不同，则在通 常的情况下，不称为重边，也不予合并。 但是有时也可以将其合并为无向边。

第一章1,什么是通信网：通信网是由一定数量的节点(包括终端节点、交换节点)和连接这些节点的传输系统有机地组织在一起的，按约定的信令或协议完成任意用户间信息交换的通信体系。

用户使用它可以克服空间、时间等障碍来进行有效的信息交换。

2，通信网实现的4个主要的网络功能：(1) 信息传送：(2) 信息处理：(3) 信令机制(4) 网络管理3，通信网的类型：按业务类型可以将通信网分为电话通信网(如PSTN、移动通信网等)、数据通信网(如X.25、Internet、帧中继网等)、广播电视网等。

按空间距离可以将通信网分为广域网(WAN：Wide Area Network)、城域网(MAN：Metropolitan Area Network)和局域网(LAN：Local Area Network)。

按信号传输方式，可以将通信网分为模拟通信网和数字通信网。

按运营方式，可以将通信网分为公用通信网和专用通信网。

第二章1，传输介质：有线介质目前常用的有双绞线、同轴电缆和光纤；无线传输常用的电磁波段主要有无线电、微波、红外线等。

2，基带传输系统：基带传输系统是指在短距离内直接在传输介质上传输模拟基带信号的系统。

基带传输的优点是线路设备简单；缺点是传输媒介的带宽利用率不高，不适于在长途线路上使用。

3，频分复用传输系统：频分复用传输系统是指在传输介质上采用FDM技术的系统，FDM是利用传输介质的带宽高于单路信号的带宽这一特点，将多路信号经过高频载波信号调制后在同一介质上传输的复用技术。

为防止各路信号之间相互干扰，要求每路信号要调制到不同的载波频段上，而且各频段之间要保持一定的间隔,这样各路信号通过占用同一介质不同的频带实现了复用4，OTN的分层结构：OTN是在传统SDH网络中引入光层发展而来的，光层负责传送电层适配到物理媒介层的信息，在ITU-T G.872建议中，它被细分成三个子层，由上至下依次为：光信道层(OCh：Optical Channel Layer)、光复用段层(OMS：Optical Multiplexing Section Layer)、光传输段层(OTS：Optical Transmission Section Layer)。

《通信网理论基础》 结课论文XXX 通信工程 XX 班 XXX XXX XXX2011年11月25日院 系： 专 业： 年级班级： 学 号： 姓 名： 指导教师： 设计日期：通信网理论基础概论一 GSM的数据业务1 GSM数据业务及其网络结构GSM数据业务的发展大致经历了一下几个阶段：第一阶段提供的数据传输速率最高为9.6kbit/s,属于低速电路交换无线数据业务，包括透明和非透明2种传输方式。

透明方式传输精确度较差，但速度快，适合要求速度较快但精确度不高的需求。

非透明方式传输精度高，数据传输过程中除了前向纠错编码外，还要通过无线链路协议（RLP）进行控制，不合格的帧需要重传，故而传输速度较慢。

为了突破9.6kbit/s的瓶颈限制，GSM在低速电路数据的基础上，提出了高速电路交换数据业务（HSCSD），通过改进编码调制方式是的一个时隙的传输速度从9.6kbit/s 提高到14.4kbit/s，并且它还允许几个时隙同时传送一路数据，理论上可达115kbit/s.HSCSD更适合实时性高的应用，如高速传真，其缺点是信道利用率低。

GSM数据业务的第三个阶段是通用无线分组交换业务（GPRS），它引入了分组交换传输技术，具有无线资源利用率高、接入速度快的优点，最高速率可达171kbit/s，并且有多种服务质量，可以灵活支持多种数据应用。

GSM数据业务的第四个阶段是增强数据速率业务（EDGE），它采用高效的调制方式，每时隙传输速率高达48kbit/s,可同时使用8个时隙传送一路数据。

EDGE包括增强型GPRS和增强型HSCSD两种。

2 承载业务和用户终端业务GSM提供的业务可分为2大类：电信基本业务和补充业务，而其中基本业务又可分为承载业务和用户终端业务。

承载业务提供在用户之间实时传递信息（语言、数据、图像等）的手段，而不改变信息本身的内容。

它定义的是对网络功能的要求，并且由网络功能来提供这类业务，而这种网络功能是由承载能力来定义的。

通信原理课程设计Project
作者：D组
• 1. 记录一段语音波形，画出时域与频域波形（能量谱密度）图， 计算90%带宽，98%带宽。 • 2.假设一基带传输系统来传输该语音，要做到传输质量与频谱利 用率的平衡。请设定带宽，并给出理由。 • 3.将该语音波形作为一个AM 系统的基带信号（取98%带宽内信 号），分别给出该基带信号经过DSB-LC，DSB-SC，SSB，VSB 调制后的时域波形与频域波形。 • 4.在上述DSB-SC 系统中，假设接收机与发射机有一固定频偏， 试编写一个程序来测试该频偏达到多少时会有显著影响 • 5.将该语音波形作为一个PM 系统的基带信号，画出调制后的时 域波形，频域波形。 • 6.假设在DSB-SC 接收机有一加性高斯白噪声，试编写一个程序 来测试噪声方差对接收机性能的影响。 • 7.将该语音样本分别进行AM 和宽带PM 调制，假设接收机理想 同步，但两个系统接收机都有相同功率谱密度的高斯白噪声，设 计一个程序来比较两个系统的性能，验证课本中学到的有关AM 与PM 输出信噪比的结论。
该频偏达到多少时会有显著影响？
对信号有显 著影响的频 偏值呈周期 性出现。
假设在DSB-SC 接收机有一加性高斯白噪声
噪声方差对接收机性能的影响？
噪声方差越大，对信号的影响越明 显。
我们将该语音将该语音样本分别进行AM 和宽带PM 调制
假设两接收机理想同步
两个接收机有相同功率谱密度高斯白噪声 比较两个系统的性能
应用MATLAB记录一段语音波形
“通信原理” by 邵老师
时域与频域波形图
90%
98%
713.1
2960.3
传输质量与频谱利用率的平衡
信道带宽和语音信号所占带宽相等的时候，信道利用率100%，随 着信道带宽的增加，噪声能量会增加，但信号中的非语音部分的能 量也在增加，所以总体信噪比会增加但趋势渐渐平缓。

•RJ-11 Port for Connection to ADSL •Four 10/100Mbps Ethernet Ports for Connection to Computers
14
Cable Modem
例如：The DCM-201 has a
maximum downloading speed at 38Mbps (256 QAM) and a maximum uploading speed at 10Mbps (16 QAM). The DCM-201 uses the Reed-Solomon error correction method for data packet integrity.
所谓数据传输链路是指在物理传输媒 介（如双绞线、同轴电缆、光纤、微 波传输系统、卫星传输电路等）上利 用一定的传输标准（它通常规定了电 气接口、调制解调的方式、数据编码 的方式、比特同步、帧格式和复分接 的方式等）形成的传输规定速率（和 格式）的数据比特通道。
11
1.1.1 数据传输链路（2）
数据传输链路分为两大类： 一类是用户到网络节点（路由器或交换机） 之间的链路（简称为接入链路）； 另一类是网络节点（路由器或交换机）到网 络节点（路由器或交换机）之间的链路（简 称为网络链路）。
1.4 通信网络的基本理论问题

8
1.1通信网络的基本构成
1.1.1 数据传输链路 1.1.2 数据传输网络 1.1.3 网络的互连
3
1.1通信网络的基本构成
传输链路 （电话线、 光纤） 用户终端
（电话机、 传真机、计 算机）
链路汇聚点 （路由器、程控交换机）
基本网络由物理传输 链路和链路汇聚点组成
•Downstream Modulation: 64QAM,256QAM

通信网理论基础修订版课程设计一、前言通信技术是当今社会不可或缺的一项基础技术，随着科技的飞速发展，通信技术也在不断进步和发展。

通信网理论基础是通信技术发展中的一个重要组成部分，对于许多工程师和研究人员来说，理解通信网理论基础对于其职业生涯的成功至关重要。

本课程设计主要针对修订版的通信网理论基础，课程设计将从以下几个方面对通信网理论基础进行深入的介绍和探讨：•核心基础概念•通信网络体系结构•网络协议与技术•传输介质与信道编码技术•小型分组交换技术二、核心基础概念1. 性能指标性能指标是衡量通信网性能的重要标准，课程设计中将对以下性能指标进行详细介绍和探讨：•时延•带宽•吞吐量•丢包率2. 传输媒介传输媒介是信息传递的物理载体，课程设计中将对以下传输媒介进行详细介绍和探讨：•光纤•同轴电缆•双绞线•无线电波三、通信网络体系结构通信网络体系结构主要涉及到以下几个方面：1. OSI模型OSI模型是计算机网络中的通信协议的一种体系结构模型，课程设计中将主要介绍以下七层：•物理层•数据链路层•网络层•传输层•会话层•表示层•应用层2. 通信网络分类通信网络按其规模和范围可分为以下三类：•个人局域网•企业局域网•公共交换网本课程设计主要将对以上三类网络进行详细介绍。

四、网络协议与技术网络协议是计算机网络中的基础，课程设计将对以下网络协议进行介绍：•TCP/IP协议•HTTP协议•DNS协议此外，本课程设计还将对以下网络技术进行介绍：•VPN技术•NAT技术•DHCP技术五、传输介质与信道编码技术传输介质和信道编码技术与通信网络的带宽、传输速度和数据传输质量密切相关，课程设计将对以下传输介质和信道编码技术进行介绍：•多路复用技术•CDMA技术•OFDM技术六、小型分组交换技术小型分组交换技术是通信网络传输数据的一种重要技术，课程设计主要将从以下两个方面对小型分组交换技术进行介绍：•分组交换的原理和特点•ATM技术及其应用七、结语本课程设计主要围绕通信网络理论基础的核心概念和关键性技术进行深入探讨和介绍，旨在帮助读者更好地理解通信网络理论基础，从而更好地应对工作和研究中的相关问题。

S为任一割
华北电力大学电子与信息工程学院
2004-08-15
第15/149页
3.4.1 一概念.15
通信网理论基础
或表示为: f (S,V ) f (V , S) f (x, y)
由于: V S S ,
SS
有: f (S,V ) f (V , S) f (S, S S ) f (S S , S)
x V1
y
10,4
集合V1
v2
9,5
割K中的边
v4
集合V1
割K的容量 f1,3 f2,4 9 9 18
华北电力大学电子与信息工程学院
2004-08-15
第12/149页
3.4.1 一概念.12
通信网理论基础
割与割集的区别
都是边的集合， 但 割:有向图 割集:无向图
v1
9,3
8,4
割中的流的净值,即割的自V1 , 到V1的边中的 流减去自V1到V1的边的流的总体
V1
x
f (V1,V 1)
V1
f (x, y)
y f (V1,V1) f (V1,V1)
f (V 1,V1, )
f (x, y)
华北电力大学电子与信息工程学院
2004-08-15
第17/149页
3.4.1 一概念.17
华北电力大学电子与信息工程学院
2004-08-15
第7/149页
3.4.1 一概念.7
通信网理论基础
流的和:
设V1和V2是顶点集合 V的子集, 用(V1,V2 )表示起点在 V1
而终点在 V2的边的集合 .用f (V1,V2 )表示(V1,V2 )中边的流之和 :

============================================================================--------------------------------------------------------------------------------------------------------------------------------------命运如同手中的掌纹，无论多曲折，终掌握在自己手中第一章1,什么是通信网：通信网是由一定数量的节点(包括终端节点、交换节点)和连接这些节点的传输系统有机地组织在一起的，按约定的信令或协议完成任意用户间信息交换的通信体系。

用户使用它可以克服空间、时间等障碍来进行有效的信息交换。

2，通信网实现的4个主要的网络功能：(1) 信息传送：(2) 信息处理：(3) 信令机制(4) 网络管理3，通信网的类型：按业务类型可以将通信网分为电话通信网(如PSTN 、移动通信网等)、数据通信网(如X.25、Internet 、帧中继网等)、广播电视网等。

按空间距离可以将通信网分为广域网(WAN ：Wide Area Network)、城域网(MAN ：Metropolitan Area Network)和局域网(LAN ：Local Area Network)。

按信号传输方式，可以将通信网分为模拟通信网和数字通信网。

按运营方式，可以将通信网分为公用通信网和专用通信网。

第二章1，传输介质：有线介质目前常用的有双绞线、同轴电缆和光纤；无线传输常用的电磁波段主要有无线电、微波、红外线等。

2，基带传输系统：基带传输系统是指在短距离内直接在传输介质上传输模拟基带信号的系统。

基带传输的优点是线路设备简单；缺点是传输媒介的带宽利用率不高，不适于在长途线路上使用。

3，频分复用传输系统：频分复用传输系统是指在传输介质上采用FDM 技术的系统，FDM 是利用传输介质的带宽高于单路信号的带宽这一特点，将多路信号经过高频载波信号调制后在同一介质上传输的复用技术。

V2 V4 V1 V3 V6 V5
割边集
割边集：若S是联接图G的边子集，在G中去掉S使G 称为非联接图，称S是G的割边集。 割集； S是G的割边集，若S的任何真子集都不是割 边集，则称S是割集。 图的结合度：割集中所含边数最小的数目。它表示图 的连通程度。
e1 e3 e2 e5 e6 e4 e7
基本割集与基本环
每一条边联接在两个（或一个）结点上； 除结点外没有任何公共结点。
G = {V , E}
其中：
V = { 1 , V2 ,V3 ,⋯} V
结点集合 边集合
E = {E1 , E2 , E3 ,⋯}
边
边反映了结点的关联性。 有向图和无向图
图中的边有方向性 图中的边无方向性
V1 V2 V3 无向图 V2
若某两个端之间的 Cij(r)值在 r<=m 时都是零，说明 Vi 到 Vj 间没有径长小于 m 的径，若不论什么 m，Cij(r) 均为零，则Vi到Vj不能对接。 Cij(r) 表示 C 的 r 次幂运算后的第（i，j）位元素
C
( 2) ij
= ∑ Cik ⋅ Ckj
k =1
n
i, j = 1, 2,⋯ , n
图的权
节点和边被赋值。 节点的权：交换机的容量或造价等。 链路的权：信道的传输容量、传输时间、几何 长度和造价等。
B = bij
( m − n +1)×m
割阵和环阵的关系
BQ = 0
T
割与环是对偶的，彼此可互求。
邻接阵
表达节点与节点间关系的矩阵。对于一个n节 点的图，邻接阵是n×n的方阵。
C = cij
n× n
1 cij = 0

(1) (2)
12
以vn回推,归纳法证:
a: vnvsn必共有, vnvsn< vnvsn’ b:若vr+1vsr+1为共有,则vrvsr必共有:
vr与vsr必有径
不用(vr,vsr)边,不经已共枝边,据(1),Q非最佳 若经已共枝边,则说明得到P树比Q树好
Prim算法是最佳算法.
13
算法复杂度分析
m in
( d ij ) d ir
*
得子图 Gr={ v1,v2,…,vr} Pr-1 ：重复Pr-2,直至得到Gn为止
9
例：用Prim算法求如下图的最短主树。
v2
3 4 2 4
6 2 1 3 5
v7 v6 v5
10
v1
v3
v4
G1={v1} G2={v1,v3} G3={v1,v3,v6} G4={v1,v3,v6,v7} G5={v1,v3,v6,v7,v2} G6={v1,v3,v6,v7,v2,v5} G7={v1,v3,v6,v7,v2,v5,v4} 则w=15.
原长径可能缩短）， 依次得：W
(1)，W (2)，…,W(n)
元素计算由W(k-1) W(k) (以vk为转接端)
wij(k)=min[wij(k-1),wik(k-1)+ wkj(k-1)]
路由阵:
ri j
(k )
k 若 w ij w ij ( k 1 ) (k ) ( k 1 ) ri j 若 w ij w ij
vi置定后，计算未置定端vj的标值的公式 Wj*=min（wj，wi+dij） 所有端置定，算法结束 返回D3
26
D4 D5