范文一：通信网的基本结构

通信网的基?本结构

二、通信网的基本结构?

任何通信网络都具有信?息传送、信息处理、信令机制、网络管理功?能?。因此，从功能的角度看，一个完整的?现代通信网?可分为相互?依存的三部?分:业务网、支撑网、传送网。?

(一)业务网

1)功能:业务网负责向用户提供?各种通信业?务，如基本话音?、数据、多媒体、租用?线、**(Virtual Priva?te Netwo?rk,?虚拟专用网络?)等。

2)构成一个业务网的主要?技术要素包?括网络拓扑?结构、?交换节点设备?、编号计划、信令技术、路由选择、业务类型、计费方式、服务性能保证机制?等。

例 单选题:

下列哪个技术要素是构?成业务网的?核心要素()?

A.网络拓扑结构? B.交换节点设备? C.路由选择 D.业务类型

正确答案是:?B

(二)支撑网

掌握功能和分类?

支撑网为保证业务网正?常运行，增强网络功?能，提高全网服?务质量而形?成的传递控?制?监测及信令等信号的?网络。?

支撑网负责提供业务网?正常运行所?必需的信令?、同步、网络管理、业务管理、运营?

管理等功能，以提供用户?满意的服务?质量。?

支撑网包含同步网、信令网、管理网三部?分。?

例:通信网中常说的支撑网?包括?( )、同步网和管理网。?

A.信令网

B.数字数据网 ?

C.传输网

D.互联网

答案是:A(2007年一级建造师??考试真题)

(三)传送网

1)传送网为各类?业务网、支撑管理网提供业务信?息传送手段?，负责将节点?连接起来，?

并提供任意两点之间信?息的透明传?输。?传送网是由传输线路、传输设备组?成的网络，所?以又称之为基础网。?

2)功能:具有电路调度、网络性能监?视、故障自动切?换等相应的?管理功能。?

3)构成传送网的主要技术?要素?有:传输介质、复用体制、传送网节点技术?等。

传送网节点:?

a)其中传送网节点主要有?分插复用设?备(?ADM)和交叉连接设备(?DXC)两种类型，它们是构成?传送网的核心要素。?

b)传送网节点之间的连接?则主要是通?过管理层面?来指配建立?或释放的，每一个连接??需要长期维持和相对固?定。?

三、通信网的类型及拓扑结?构?

(一)通信网的类型?

(二)通信网的拓扑结构?

在通信网中，所谓拓扑结?构是指构成?通信网的节?点之间的互?连方式。?

基本的拓扑结构有:网状网、星形网、环形网、总线?型网、复合型网等。?

要求掌握每一种拓扑结?构的拓扑形?状、优点、缺点、?使用场合，重点是掌握使用场?合。

1)具有N个节点的完全互?连的网状网?需要有?1/2?N?(N一1)条传输链路。?

2)具有N 个节点的星形网共需?(N一1)条传输链路。?

3)具有N个节点的环网需?要?N条传输链路。环网可以是?单向环，也可以是双?向?环。

1( 网状网:

.优点:线路冗余度大，网络可靠性?高，任意两点间?可直接通信?;?

.缺点: 线路利用率低?(N值较大时传输链路数?将很大?)，网络成本高，另外网?

络的扩容也不方?便，每增加一个?节点，就需增加?N条线路。?

.适用场合:通常用于节点数目少，又有很高可?靠性要求的?场合。?

如图1电信网的基本结?构?

2(星形网又称辐射网?

.优点:与网形网相比，降低了传输?链路的成本?，提高了线路??的利用率 .缺点:网络的可靠性?差，一旦中心转接节点发生?故障或转接?能力不足时?，全网的通信?都?

会受到影响。?

.适用场合:在传输链路费用高于转?接设备、可靠性要求?又不高的场?合，以降低建?

网成本。?

3(复合型网

.结构:是由网状网和星形网复?合而成的。它以星形网?为基础，在业务量较?大的转接交?换?

中心之间采用网状网?结构?.

.优点:兼并了网状网和星形网?的优点?。整个网络结构比较经济?，且稳定性较??好。

.适用场合:规模较大的局域网和电?信骨干网中?广泛采用分?级的复合型?网络结?构。

4(总线型网属于共?享传输介质型网络? ?

.结构:网中的所有节点都连至?一个公共的?总线上，任何时候只?允许一个用?户占用总线?发?

送或接送数据。?

.优点:需要的传输链路少，节点间通信?无需转接节?点，控制方式简?单，增减节点也?很方?

便;

.缺点:网络服务性能的稳定性??差，节点数目不宜过多，网络覆盖范?围也较小。?

.适用场合:主要用于计算机局域网?、电信接入网?等网络中。?

5.环形网

.结构:网中所有节点首尾相连?，组成一个环?。?

.N个节点的环网需要?N?条传输链路。环网可以是?单向环，也可以?是双向环。?

.优点:是结构简单，容易实现，双向自愈环?结构可以对?网络进行自?动保护;?

.缺点:是节点数较多时转接时?延无法控制?，并且环形结?构不好扩容?。?

.适用场合:目前主要用于计算机局?域网、光纤接入网?、城域网、光传输网等??网络中。

范文二：第2章 卫星通信网结构

第二章 卫星通信网结构

卫星通信网提供三种用户之间的连接链路:点到点,点到多点,多点到点。 l点到多点传输,用于视频和数据广播(GPS 等) 。由上行主站发往卫星, 再由卫星转送到其覆盖范围的每个接收用户。

l多点到 点是对 广 播系统 的接收站 赋予发送信息的能力, (DVB-S2, DVB-RCS ) 。

l网状网提供点到点的连接,支持交互式业务。

lVSA T 数据网采用星形结构,中心站和各小站间的链路是双向的。

2.1 网络结构简介

2.1.1 网络分类

网络的分类方式有很多种,例如按交换方式分,按拓扑结构分,按地理 位置 范围分等。

常 用的 计算机 网络的 基本 拓扑结构有:总线 形 、 星形 、环 形 、树 形 、 网状网 和 不规则 形。

1) 总线 形结构

图 2-1 总线 形结构网络

n通信网络 只 是传输 媒体

n 成本低 n 分 散控制

n 结构 简单 , 可靠性好

n 各结点 共 用 总线 ,广播式传输 n 扩充性好 , 增减 结点 容易 n 总线长度 有 限

2) 星形结构

图 2-2 星形结构

n 集 中 控制 ,中心交换 节 点 功 能 复杂 , 但 其 他 通信 节 点 负荷相 对 较轻 n 建设成本较大 , 可扩展性好 n 所 有结点 与 中 央 结点连接 n 结构 简单、控制简单 n 结点 出现故障易 于 隔离 n 中 央 结点的 可靠性致关重要 3) 环 形结构

图 2-3环 形结构

n 由 一组 转发 器 通 过 点对点连接 成环 路构 成 n 分 散控制

n 单 个 节 点的 故障 有 可 能 波及全 网

Central server

n 各结点 共享环 路

n 采用 令牌控制 , 重负载时吞吐量较大 4) 总线 结构

图 2-4总线 结构

5) 网状网

图 1-5网状网

n 端 结点之间 存在 多 条 通路, 需选择 路 径 n 可靠性高 n 通信 控制复杂

2.1.2 网络协议层次化

在 通信 过程 中 必 须遵守事先 规 定 好 的 规则 , 即 网络 协议 。

国际标准化 组 织 于 1979年公布了开放 系统互连 参考模型 OSI 。 OSI 模型 分 为 7层 ,如 图 2-6所 示 。 在 同 一 个结点上, 下层为 上 层 提供 服 务, 在 两 个结点之 间,对等 层 之间通 过 该层协议进 行通信。

优 点

n 简 化了协议 , 便 于 实 现、 调试 和 维护

n 各 层 相 互 独立 , 某 一 层 只需 知道下 一 层 通 过 接 口 所 提供的 服 务, 而

不需

了解 其 实 现 的 细 节

n功 能的 追加 和 变更 , 限 定 在相关 的 层 中, 使得 功 能 扩充 比 较 灵活 n结构上 可 分 割开 ,各 层都 可 以 选则 最适合 的 实 现 技术

图 2-6 OSI参考模型

两 个系统间的数据 在 网络中的传输如 图 2-7所 示 。

图 2-7 OSI中的数据 流

2.2 卫星通信网的一般特性

?面 向连接 与 无 连接

面 向连接的通信由 3个 过程组成

1) 建 立 连接

2) 传输数据

3) 撤消 连接

无 连接的通信 在 传输数据之 前 不需要建 立联 系,发送方 可 以随 时 发送数据, 但 数据中 要 携带目 的地的地 址 ,网络按 照目 的地地 址把 数据传送到 目 的地。

2.2.1 专用带宽业务

卫星发 展 初期 , 一 般为 每 一 业务的传输分 配 一条 固定 的卫星链路, 在 通信 期 间, 所建 立 的连接链路 始终保 持 不 间 断 。 这 种 固定 的 专 用 带宽 分 配 链路传输的 速 率始终 不 变 。

2.2.2 电路交换业务

所 谓 电 路交换(Circuit Switching ) , 就 是 在 两 通信 端 之间 建 立 一条 专 用的 (dedicated ) 实际 物 理通路路 径 。 此 路 径 由发送 端 开始 , 一 站 一 站往 目 的 端 串 联 起来 。 一 旦 建 立两 端 之间的 联 机 后 , 它将 一 直 维 持 专 用状 态 (即 他 人 无 法 使 用) , 直 到通信结 束 之 后 , 这 条 专 用路 径 才停止 使 用, 并让 出 供 他 人继续 使 用。 目前 的 电话 与 电报 交换系统 就 是 使 用 这 种 技术 。

图 2- 8 电 路交换的 工作 模 式

电 路交换方式 属 于 预 分 配 电 路 资源 系统, 即 在一 次 接 续 中, 电 路 资源预 先 分 配 给 一 对用户 固定使 用, 不 管 在 这 条 电 路上 实际 有 无 数据传输, 电 路 一 直被占 用, 直 到双方通信 完毕拆除 连接 为 止 。

电 路交换方式是 从 一 点到 另 一 点传 递 信息的 最 简单 的方式。 电 路交换方式是 基 于 电话 网 电 路交换的 原 理, 即 当 用户 要 求 发送数据 时 , 交换 机 就 在 主 叫 用户 终 端 和 被叫 用户 终 端 之间接 续 一条 物 理的数据传输通路, 这 种传输通路是双向的 。 图 2-9是 电 路交换的 基本过程 。

时间

图 2-9 电 路交换的 基本过程 。

为 用户分 配固定 的 专 用(带宽 )链路, 但 通 常 用户 只在 有 实际 通信 需 求 时 , 才 需要 资源 , 因此 这 种方式 不 经济 。

卫星通信网中, 地 球 站对 呼叫请求 的 响应将直 接传送到 电话 用户 或 公 用 电话 网(无 星上交换) 。

电 路 作 为 系统 容量 资源 , 对 应 一 个频 带 或 一 个 时 隙 , 实 行按 需 分 配 。 图 2-10是各类地 球 站的卫星 电话 网 示 意 图 。

图 2-10

优点

传输的 实 时性好 , 适合实 时性要 求 高 的交互式信息的传输。

缺点

n线 路的 利 用 率比 较低

n不 适合 少 量 的 突 发 性 数据的传输

n要 求 收发双方 不 “ 忙 ” ,有 相 同 的数据传输 速率

n不 能 完 成 编码格 式 、 通信 规程 等方 面 的转换

n中间结点 不 具备差错 控制 能力

n当 网络通信 量 很 大时 , 会 使 线 路的连接 失败

l在 NGEO 系统中, 呼叫 是通 过 多个卫星和星 际 链路的连接 实 现 , 考 虑 到用户 和卫星之间的 相 互 运动 , 需要 进 行卫星之间的 切 换, 更加 复杂 , 在 卫星通信 系统中, 呼叫 建 立 的 时 间通 常 达 10s 。

2.2.3 分组交换业务

l分 组 交换方式是 把 要 传输的 报文 分 成 若干 个小的数据 块 , 称 为 分 组 , 然后 以 分 组 为 单位 按 照 与 报文 交换 同 样 的方 法 进 行传输。 为了使得 信息的 可靠 传输 和 处 理, 信息 流 在 信 源 端 被封装 成 分 组时 , 要 加 上 “ 报头 ” , 在 接收 后 , “ 报头 ” 被去掉 。 TCP/IP成 为 分 组 数据网的主 流技术 , A TM 也 是 一 种分 组 交换业务。 l特点

1) 出现 误码后 , 只重 发有 误码 的分 组

2) 在 接收 下 一 个分 组 的 同 时 , 就 可 以 转发上 一 个分 组 ,提 高 了 吞吐量

3) 由于分 组 比 较 短 , 可 以 存 储 在 内 存 中, 减 少 了 存 储 时 间

4) 技术实 现 比 较复杂

l分组交换分为有两种基本形式:虚电路(VC , virtual circuit )和数据报方 式(DG , data gram) 。

一 .虚 电 路方式

虚 电 路方式, 是 一 种 面向连接 的 技术 , 它 与 电 路交换有 相 似 之 处 , 即 虚 电 路的连 接 也 有连接的 建 立 和 清 除 过程 , 但 不 是 物 理链路 的连接, 而 是由 虚 电 路 号 所 标 识 的 逻辑 信 道 的连接, 交换 节 点 根 据分 组 标 识 进 行路由。 在 传送 过程所 有的分 组 将 沿已 建 立 的 虚 电 路传送, 可靠性高 , 虚 电 路方式如 图 2-11所 示 。

图 2-11 虚 电 路方式

二. 数据 报 方式

l数据 报 方式, 无 需建 立 预 先 的连接, 源 终 端 的各数据分 组可 沿彼 此 独立 的路 由 进 行传输, 即 每个分 组可 以 沿 不 同 的路 径 通 过 网络, 但可靠性较 差 , 可 以

说 是 一 种 无连接服务 。 分 组 到 达 目 的地的 顺序 可 能 与 发送 不 同 , 还 需要 整序 。 l如 果 数据 报 方式 可 以 重 新排序 , 并 向 入 节 点 申 请 重 发 丢 失 的分 组 , 也 可 以 提 供 面 向连接的 服 务。

图 2-12 数据 报 方式

l分 组 交换网 具 有如 下 特 点:

(1)分 组 交换 具 有多 逻辑 信 道 的能力, 故 中 继 线 的 电 路 利 用 率 高 ;

(2) 可 实 现 分 组 交换网上的 不 同 码 型 、 速率 和 规程 之间的 终 端 互通 ;

(3)由于分 组 交换 具 有 差错 检测 和 纠正 的能力, 故 电 路传送的 误码 率 极 小 ;

(4) 分 组 交换的网路 管 理 功 能 强 。 经济 性 能 好 。 此 外 , 分 组 交换能 与 公 用 电话 网 、 用户 电报 网 及 其 他 专 用网互连 也 是分 组 交换网的 优 点。

2.2.4 ATM 简介

A TM 即 异步 传输 模 式, A TM 是 一 种 快 速 分 组 交换 技术 , 因 为 A TM 中的分 组 被称 为 信 元 ,如 图 2-13所 示 , 所 以 也叫 信 元 交换。

图 2-13 ATM 信 元 (53字 节 )

一 . 同 步 传输

采用 时 分多路 复 用,传输 介质 被 划 分 为 多个信 道 , 同 时 传送多路数据,如 图 2-14所 示 , 所 有信 道 平均 分 配 介质 带宽 若 某 路数据 较 少 , 可 能 造 成 信 道 空闲 , 浪 费 了带宽 资源 。

图 2-14 ATM 同 步 传输

二.异步 传输

采用 时 分多路 复 用, 根 据 需要 来 分 配 信 道 ,每个信 道 分到的 带宽 不 同 一 个信 元 占 据 一 个 时 隙 , 通 过 信 元 头 部 的 控制 信息 区 分信 道 可 以 充 分 利 用 介质 带宽 , 如 图 2-15所 示 。

图 2-15 ATM 异步 传输

三 . A TM 的 逻辑 连接

A TM 先 建 立 一条 虚 连接的通路,再发送数据, A TM 可在 两 个 层 次 上 建 立 虚 连接, 一条 链路上 可建 立 多 条 虚 路 径 ,用 虚 路 径 标 识 (VPI)区 分信 元 头 部 有 VPI , 用 以 表 示该 信 元 属 于 哪 个 虚 路 径 , 同 一 信 元 的 VPI 在不 同 链路上 可 以 不 同 。 图 2-16是 虚 路 径 下 的 虚拟 通 道 。

图 2-16 虚通道是虚路径下的虚拟通道

一条 虚 路 径 中 可 以 包含 一条 或 多 条 虚 通 道 , 用 虚 通 道标 识 VCI 区 分, 每 条 虚 通 道 是 一条 逻辑 信 道 ,传送 一 路信息信 元 头 部 有 VCI , 同 一 信 元 的 VCI 在不 同 链路上 可 以 不 同 ,如 图 2-17所 示 。

图 2-17.

四. 信 元 的传输

信 元 的 头 部 都 含 有 VPI 和 VCI 。 具 有 相 同 VPI 和 VCI 的信 元 在 同 一 个 虚 路 径 中的 虚 通 道 中传输,信 元 中的 VPI 和 VCI 在 每 段 链路上 可 以 是 不 同 的。 A TM 交换 机 按 照 在建 立 虚 连接 时 创 建 的路由 表 , 把 输 入 端 信 元 的 VPI 和 VCI 改 为 输 出端 的 VPI 和 VCI 。

虚 路 径 和 虚 通 道 是 逻辑 上的信息传输通路, 在 物 理链路上信 元 是 串 行传送 的, 逻辑 上的多通路是通 过复 用 技术实 现 的,每个信 元 头 部 的 VPI 和 VCI 决 定 了该 信 元 属 于 哪 条 逻辑 通路。

图 2-18 虚 路 径、 虚 通 道 与 信 元 之间的 关 系

2.2.5 卫星 ATM

卫星 A TM 网 要 解 决 的主 要 技术 问题 是卫星通信网 与 A TM 网的互连互通, 最终使 卫星网 成 为 全 球 通信网的 一 个 无 缝 、 可 互 操 作 的 部 分, 因 而 , 规 范网络结 构 、 标准 空 中接 口以 及与 A TM 兼 容 的网络 协议 是 解 决问题 的 关 键 。

卫星 A TM 网结 合了 各 自 的 特 点, 它 以 卫星传输 为 手段 达 到 A TM 的交换 及 业 务 要 求 , 又 比固定 A TM 增 加了 移 动 性、 灵活 的网络 及容量 配 置、 更 强 的广播能 力和 更 广的覆盖范围等 特 点。

l 卫星 A TM 网络 体 系分 为两 种:

(a) 用于卫星 透明 传输的卫星 A TM

(b) 用于 具 有星上交换能力的卫星 A TM 两 大体 系

在 透明 卫星网络中, 在 卫星的 A TM 层 或 以 上 层 次 不 进 行 处 理, 所 有 协议 处 理 都 是 在 地 面 的用户 端 (UT)、关 口 站 (GES)和网络 控制 中心 (NCC)进 行的。 尽 管 没 有星上 处 理和交换 功 能 妨碍 卫星网络和地 面 A TM 网络间的 完 全 融 合 , 但 因 其 具 有 处处 覆盖 、 独 特 的广播 性 能 、 灵活 的网络 配 置 和 容量 分 配以 及 提供 移 动 服 务等 优 点, 使得这 些 体 系结构 成 为了 地 面 高 速 网络的有力 扩展

由于 A TM 传输数据 速率 高 , 接收 终 端必 须使 用 定 向 天 线 。 对于 GEO 卫星的

固定终 端 来 说 使 用 固定 天 线 即 可 , 但 是对于 LEO 卫星, 需要 有 两 个 波 束 的 跟踪 天 线 , 以适 应 卫星的 切 换。 移 动 终 端 也 需要 额外 的 补偿 由于用户 移 动 带 来 的 损耗

图 2-19 ATM 卫星传输网络结构

2.2.5 数据通信和协议

利 用卫星 进 行数据通信, 关 键 在 于 正确 的 协议 和 编码 方 案 。

协议 :是 一 套 保 证 在 两 个 终 端 之间 进 行 码 元 (或 分 组 ) 正确 传输和 判 定 的 规则 , 要 有 出 错 重 传 机制 。

卫星链路 与 地 面 链路 相 比 , 可 能 出现成 串 的 突 发 错误 , 并 由 长 的传输 延 时 , 因此 要 采用 前 向 纠 错码 FEC , 目前最 常 用的是 卷积 码 。

2.2.6 卫星通信系统的服务质量问题

服 务 质 量 (QoS)是网络 在 传输数据 流 时要 求 满足 的 一 系 列 服 务 请求 , 具 体可 以 量 化为 带宽 、时 延 、时 延 抖 动 、 丢 失 率 、吞吐量、 耗费 等 性 能 指 标 。

l我们 关 注 的是业务 在 卫星通信网传输之 前 ,如 何 根 据 它 们 的 特 性 将它 们 区 分, 以便 区 别 的传送, 这 就 是 QoS 解 决 方 案 , QoS 研究 目标 是如 何 有 效 的 为 用户提供 端 到 端 的 服 务 质 量 和 保 证 。 它 无 法 创造 带宽 , 只 是 根 据 需 求 和网 络状 况 来管 理 带宽 。 具 体可 以 量 化为 传输 延 迟 、 抖 动 、 丢包 率 、 带宽 要 求 、 吞吐量、 业务 可 用 性 等 指 标 。 为了解 决 QoS 问题 , IETF 提 出 了下面 几 种 服 务 模 型 和 机 制 :集 成 服 务 和 资 源 预 留 协 议 (IntServ/RSVP)、 区 分 服 务 (DiffServ)、 和多 协议标 签 交换 (Multiprotocol label switching, MPLS) 。 一 . 卫星链路 特 点

l由于地 球 站对 GEO 卫星 仰角 较高 , 与 地 面 微 波 传播 相 比 , 大 气引 起 的 衰落 较轻 微 , 而 且 持 续 时 间 短 , 比 地 面 微 波 传输 要 稳 定 , 一 般 建 模 成 恒 参 信 道 。 l干 扰情况 与 地 面 网 不 同 。地 面 网主 要 受认 为 干 扰 和 不 同 类 型 的 短 期 脉冲 干 扰 ; 而 卫星链路的 干 扰 主 要 来源 于接收 机 内 部 噪声 (偏远 地 区 , 各种 干 扰 少 ) , 它 是由于 当 前 器 件 和 技术 水 平决 定 的 常量 , 可 以 用 增 加 信 号 功 率 的方 法 补 偿 。

l卫星 移 动 通信链路 较 卫星的 固定 通信链路传输 条 件恶劣 。 天 线高度低 , 增 益

也 低 , 而 且 由于 环 境影 响 , 存在 多 径现 象 。

二. 话 音 质 量与 回 波

l 由于链路 距 离长 ,传播 延 时大 , 单 跳 的传播 时 延 就达 到 250毫秒 , 加 上 语音

编码 器 等的 处 理 时 间 则单 跳 时 延 将达 到 350毫秒左右 , 当 移 动 用户通 过 卫星 进 行双 跳 通信 时 , 时 延 将达 到 700毫秒 , 这 是用户 所 难 以 忍受 的。 为了 避免 这 种双 跳 通信 就 必 须 采用星上 处 理 使得 卫星 具 有交换 功 能, 但 这 必 将 增 加 卫 星的 复杂度 , 不但增 加 系统 成本 , 也 有 一 定 的 技术 风险 。 长 的 延 时 对 电话 业 务有 影 响 。

l 卫星通信中, 长 的通信 时 延 会 带 来 回 波 干 扰 的 问题 。

l 在 二 线 传输的 两 个方向上 同 时 间 、 同 频 谱 地 占 用 线 路, 在线 路上 两 个方向传

输的信 号 完 全 混 在一 起 , 本端 发信 号 的 回 波 即 成 为 本端 收信 号 的 干 扰 信 号 , 利 用 自 适 应 滤 波器可 抵 消 回 波 以 达 到 较好 的接收信 号质 量 。 卫星通信中 回 波 产生 原 理如 图 2-20所 示 。

l 二 线制 是 电源 和信 号 输 出 都 由 两 根 线 来完 成 , 一 根 是 电源 的 正 , 另 一 根 即

做 电源 的 负 又 做 信 号 的输 出 。 回 波 抵 消 是 二 线全 双 工 通信中 一 个 不可 忽略 的 问题 , 在 二 线 双 绞 线 传输中,由于 存在 两 个方向上 同 时 工作 于 一 个频 带 , 加 上接 受 端 的 阻抗 不 匹 配 的 问题 , 致 使 接 受 端 很 容易 收到 本端 发 射 信 号 的 干 扰 , 因此 需要在 发 射 和接 受 端 之间 加 载一 个 感 应 线 圈 , 就 是 一 个 回声 消 除 器 。

图 2-20 卫星通信 线 路 产生回 波 干 扰 的 示 意 图

三 . 卫星和链路的 可靠性

l 卫星的 可靠性 是卫星通信系统的 决 定 因 素 ,卫星的 可靠性 是 比 较高 的,卫星

采用 高 质 量 的 部 件 (宇航级 ) 、 足 够 的系统 储备 和 冗余 设计 , 当 卫星 正确入 轨 ,卫星的 可靠性可 达 99.99%。

l 通信链路的 可靠性可 以 用能提供 服 务的 时 间 百 分数 给 出 (也称 可 用 度 ) , 图

2-21给 出 了 每 年 中 断 小 时 数 与 给 定 的有 效 性 之间的 关 系 曲 线 。 对于 固定 卫星 业务,链路的 可靠性 典 型 值 为 99.9%。对于卫星 移 动 业务,由于 移 动 环 境 造 成 的多 径 和 直 射 电 波可 能 被 阻挡 , 而 且 NGEO 星 座 的 移 动 和 切 换, 会 使得 链 路 可靠性 降 低 。

图 2-21

卫星通信中 断 的 原因 :

一 般 不 是 硬件 的 失 效 , 而 是由 雨季 的通信中 断 和 射 频 干 扰 造 成 。

提高可靠性的措施:

l卫星上系统 备 份 是 非 常重要 的, 关 键 子 系统 都 采用的是 100%备 份 。

l定期 的 检测 , 以 防 止 主 设 备 和 备 用 设 备 都 失 效 。

l地 面 链路提供 高可靠性 , 应 能提供 不 同 路由的 选择 。

例如:

l嫦娥 一 号 卫星发 射 需要 的 国 内 外 3个 测 控 网 近20个 测 控 站 、 船 和多个数据 处 理交换中心, 如 何 保 持 联 系 畅 通 ?绕月探 测 工 程 测 控 系统 租 用 了 4颗 通信 卫星, 并 开 设 了 中心 与 各 测 站的 80余 条 通信链路。

2.3点-多 点网络

2.3.1视频广播

点 -多点的广播网由 一 个发送地 球 站(上行站)和 众 多 单 收站 组成 ,网络 覆盖 简单 , 而 地 面 点 -多点广播(例,有 线 电 视网) 需要建设复杂 的地 面 网络。 GEO 卫星 一 个转发 器可 以 转发 一 个 或 多个 载波 ,用于 电 视 节 目 分 配 。 一 般 星 上采用 ku 波 段 实 现 广播, 不 能采用 C 波 段 , 因 为 地 面 中 继 站 一 般 采用 C 波 段 , 如采用 C 波 段 进 行 大功 率 转播, 会 对地 面 C 波 段 中 继 站 造 成 干 扰 。

l在 上 世纪 90年 代 提 出 的 DVB (Digital Video Broadcasting,数 字 视频广播) 标准 提供 了 一 套 完 整 的 适合 于卫星 、 电 缆 和地 面 等传输 媒 介 的数 字 电 视广播系统 规 范。 它 采用 MPEG2-TS 传输 流 小 包 作 为 “ 数据 容器 ” , 不但可 传送 压缩 的 图 像 、 声音 , 还 提供 了 对数据传输的 良 好 支持, 可 以 在 数 字 电 视广播信 道 上传输数据业 务。

利 用 基 于 DVB 的卫星 宽带 网络 实 现 数据传输, 系统用户 端 接收 机 价 格 较 低 , 且 能 够 实 现 数据业务和 电 视业务 集成 , 相 比 其 它 卫星数据传输系统 更 具 有 吸 引 力。 目前 , 全 球 已 经 普遍 采用 DVB-S 作 为 卫星数 字 视频广播 标准 。

早 期 的卫星 DVB 系统 只 支持 DVB-S 单 向广播业务。 整 个系统由用户 终 端、 地 面 主站和卫星 组成 , 为了 支持用户 请求 等信息的传送, 在 用户和主站之间 可 以 采用地 面 通信 线 路(如 电话 线 路) 建 立 回 传通路。

主站中通 过 网 关负 责 经 过 卫星链路的业务和 来 自 用户 反 向链路数据的 选 路, 并完 成 数据链路 控制、 数据 封装 、 信 道 分 配 等 功 能。 IP 分 组 经 网 关 封装后 , 经 过 加 扰 、复 用 以 及 调 制 ,发送到卫星信 道 。用户 终 端 装 置则 由接收 天 线、机 顶 盒 、 PC 机 等 组成 , 执 行 解调 、 解 扰 、 解 复 用 、 IP 分 组重组及 内 部 寻 路等 操 作 。

l 在现 有的 DVB 技术 中是 利 用 MPEG-2(一 种视频 压缩 编码 标准 ) 技术 来 实 现 数 字 卫星广播 功 能的, 而 DVB 技术 已 经 发 展 了两 代 , 早 期 的 DVB 系统由于 其用户 请求 信息 必 须 通 过 地 面 线 路传送, 因 而 系统是采用 单 向传输方式 工作 的。 目前 所 研 制 的系统 为 第 二 代 DVB 系统。 在 该 系统中,用户 以 可 变速率 访 问 信 道 (由用户 终 端 到中心站,通 过 卫星链路) , 并 同 时 具 有 话 音 通信 功 能。 在图 2-22中 给 出 了 日 本 NTT 无 线 实 验室 提 出 的 组 网方 案 。

图 2-22 基 于 DVB 的 IP 卫星通信系统结构

2.3.2数据 广播

由卫星支持的 一 种数据通信系统如 图 2-23所 示 , 是 一 个点 -多点系统,上行 站的数据 来 自 中心站数据 库 服 务 器 , 然后将 数据 装 配为 分 组 , 分 组 数据由上行站 发往卫星, 然后 由卫星向地 面 单 收站广播, 数据按地 址 由各 自 的接收 机 接收, 也 可 进 入 地 面 数据分 组 交换网,例如 Internet 。

图 2-23

l卫星数据 IP 广播 是通 过 UDP 协议 将 数据 打 包 送上卫星,再通 过 卫星 下 发 至 接收 端 。接收 端 使 用 指 定 的 PC 卡 /接收 机 和 相 应 的接收 软 件 即 可 接收。 IP 广播是 基 于 新 一 代 的卫星数据广播方式, 需要 占 用 专 门 的 IP 频 道 资源 。

卫星 IP 数据广播每个通 道 的数据传送 速率 可 达 1Mbps , 甚至 更 高 , 可 以 在 实 时 传输 高 清 晰 度 的数 字 视频信 号 的 同 时 传输 远 程 教学 所需 的其 他 多 媒体 信息, 完 全 能 够 满足 远 程 教学 对 带宽 的 要 求 。 由于 是基 于广播 方式传输, 其 带宽 不受上 网 人 数的 制约 , 每个 用 户都能拥 有 同样 的带宽, 不同于现在 Internet 的数据 广 播 。 IP 数据广播 不 同 于视频广播, 它将 根 据 需要 , 把 卫星上的转发 器 带宽 分 成 许 多 份 ,每 一 份 叫 一 个 IP 通 道 ,能 够 用于传送 一组 类 型 的数据 内 容 , 可 以 是 计 算机 网站信息,多 媒体 数据等。 IP 数据广播 目前 在 我 国 基本 上是 单 向, 即 只 能 接收, 也 可 以 是双向, 即 学校 或 家庭 利 用地 面 卫星 天 线 和双向 设 备 在 接收信 号 的 同 时 能 够 向卫星发 射 数据信息。

l交互式卫星广播系统

早 期 的 DVB 系统由于是 单 向广播方式, 在 操 作 性 和通信 质 量 等方 面 存在 很 大 缺陷 , 因此 , 欧洲 电 信 标准协 会 ETSI 发 布了 交互信 道标准 ,通 过 专 用的双向 交互信 道 , 可 以 构 造 基 于 GEO 卫星的交互网络。

在 系统中, 从 业务提供 者 到用户之间是 一条单 向的广播信 道 ,采用 DVB-S 标准 ,用于传输 视频 、 音 频和数据。 为了 做 到用户和业务提供 者 之间的信息交 互, 又 在 两 者 之间 定 义 了 一条 双向的交互信 道 , 从 用户到业务提供 者 的 为 回 传交 互路 径 (Return Interaction Path) , 用于发送 请求给 业务提供 者 、 应 答 或 传送数据 ; 从 业务提供 者 到用户的 为前 向交互路 径 (Forward Interaction Path) , 这 条 路 径可 以 嵌 入 到广播信 道 中, 在一 些 简单 系统中 也 可 以 省 去 这 条 信 道 , 直 接采用广播信 道 发送数据到用户。

2.3.3 点-点网络

卫星通信 为实 现 点 -点到通信网络, 必 须 采用多 址技术 , 常 用多 址技术 有 FDMA, TDMA, 和 CDMA 。

一 . 网状网

卫星网状网能提供 若干 条 链路 以 连接 不 同 位置 的多个地 球 站, 在 N 个地 球 站 之间的 最 大可 能的链路数 为 N(N-1)/2。

二. 多种数 字 业务

点 -点卫星链路 可 用 复 用的方 法 综 合 各种数 字 业务, 包 括 电话 、 会 议 电 视和 广 域 网数据。

复 用 技术 有:时 分 复 用 、 统 计复 用 、 快 速 分 组 交换 、 帧 中 继 和 A TM 交换。 卫星 非 常 适合为 不 同 地 域 的 大 型 计算机 系统 或局 域 网连接 而 构 成 W AN 。 利 用卫星和地 面 网的点 -点链路 可 以 组成 星形 、 网状和 环 形网拓扑结构。 与 地 面 链路 相 比 ,卫星链路 容量 小, 成本较高 , 一 般 可 作 为 地 面 链路的 备 份 。 2.3.4. VSAT网

VSA T 是 V ery Small Aperture Terminal的 缩 字 , 直 译 为 甚 小 口 经 卫星 终 端 站。 所 以 也称 为 卫星小数据站(小站) 或 个 人 地 球 站(PES ) , 这 里 的 “ 小 ” 指 的是 VSAT 卫星通信系统 中小站 设 备 的 天 线 口 径 小, 通 常 为 1. 2-2. 4米 。 利 用 此 系统 进 行通信 具 有 灵活 性 强 、 可靠性高、 使 用方 便 及 小站 可 直 接 装 在 用户 端 等 特 点, 利 用 VSAT 用户 数据 终 端可 直 接和 计算机 联 网, 完 成 数据传 递 、 文 件 交换 、 图 像 传输等通信 任 务, 从 而 摆脱 了 远距 离 通信地 面 中 断 站的 问题 。 使 用 V SAT 作 为专 用 远距 离 通信系统 是 一 种很 好 的 选择 。

VSA T 系统的 组 网方式 属 于点 -多点和点 -点的网状网拓扑结构。

一 . VSA T 星形数据网

VSA T 星形网,由 一 个中心站(HUB )和多个 远 端 小站 组成 ,如 果 链路是 单 向的, 则 为 广播系统, 可 用于数据发 布 、 新 闻 或 商 业 电 视等。

VSA T 星形网提供中心站 与 多个小站之间的 直 接双向通信, 以 数据业务 为 主, 而 个小站之间的信息交换 没 有 或 很 少 。 小站的信息 只与 中心站 进 行交换, 由 于中心站有 高 的发 射 功 率 和 大 的 天 线 , 因此 小站的 设 备 相 对 简单 , 天 线 口 径 小。 如 果 用于 语音 通信, 意 味着 有 “ 两 跳 ” 的传输 延 迟 , 所 以 星形网 一 般 只 用于数据 传输。

数据通 常 以 分 组 方式 进 行传输和交换。

二. 交互式 VSA T 网状网

网状 VSA T 网的各小站之间 可 以 通 过 卫星 直 接 建 立 通信链路, 单与 星形网 相 比 ,小站的 EIRP 和 G/T值 要高一 些 ,小站的 成本 也 较高 , 更 复杂 。

网状网主 要 用于支持 语音 业务, 避免 了 “ 两 跳 ” 传输 延 迟 。

习 题

范文三：通信网基础-网络体系结构

网络采用分层具有以下好处：

, 某一层并知道它下面的层是如何实现的，而仅仅需要知道

(即界面)。因此各层均可以采用来实现。

, 当任何一层发生变化时，，上下相邻层则均不受影响。而

且，某层提供的服务可以修改，如果当某层提供的服务不再需要时，可将这层取消。

, 分层结构通过把整个系统若干个，而使通信网的

实现、调试和维护等变得容易。

应用层：规定了应用程序怎样使用互联网。

传输层：应用进程之间的端-端通信

互联网层：负责将数据报送到目的主机。

网络接口层：提供一种数据传送的方法, 将IP地址映射为网络使用的物理地址。

相同之处：都，将庞大且复杂的问题划分为若干个较容易处理的范围较小的问题；各

协议层次的功能大体上相似，；两者都可以，实现世界上不同厂家生产的；都是计算机通信的；都是的概念。

不同之处：，它们都有网络层（或称互联网层）、传输层和应用层，

但其他的层并不相同；的同时支持和的通信，但是上支持的通信；TCP/IP模型的只提，但在上同时支持通信模式。

51

传输层的两个协议——TCP和UDP，建立在IP上，为支持广泛的应用而提供的“尽力而为”的服务基

础上。

是一个不可靠的的传输层协议，它是一个非常简单的协议，只提供在IP的范围外的两种额外服务：和。

在IP的基础上提供可靠的的字节流服务。它使用了；也使用通过分组丢失来，并且能通过拥塞窗口。

TCP

(Telecommunication NetworkTELNET)

(File Transfer ProtocolFTP)

(Simple Mail Transfer ProtocolSMTP)

(Domain Name SystemDNS)

(Hypertext Transfer ProtocolHTTP)

52

范文四：第二章 通信网的拓扑结构

第二章 通信网拓扑结构

通信网的拓扑结构是很基本，也是很重要的问题。拓扑结构是通信网规划和设计的第一层次问题。通信网的拓扑结构可以用图论的模型来代表，主要的问题为最短径和网络流量问题。本章还介绍了线性规划问题的基本概念和方法及网络优化结构模型。

§2.1图论基础

图论是应用数学的一个分支，本节介绍它的一些概念和结论。其基本内

容可参见（1）和（2）。

2.1.1图的定义

例2.1 哥尼斯堡7桥问题;

所谓一个图，是指给了一个集合V ，以及V 中元素的序对集合E ，V 和

E 中的元素分别称为图的端点和边。

下面用集合论的术语给出图的定义：

R 设有集合V 和E ，V={v1，v 2，……，v n }， E={e1，e 2，…… em } ，且V ?V ??→E

则V 和E 组成图G ，称V 为端集，E 为边集。

下面给出图的一些概念:

当e ij =(vi ，v j ) ，称边e ij 和端v i 与v j 关联；

当v i Rv j 不等价于v j Rv i 时，为有向图；

当v i Rv j 等价于v j Rv i (eij =eji ) 时，为无向图；

当V=φ(此时E 必为空集) ，为空图；

自环，孤立点图，重边；

简单图: 不含自环和重边的图称为简单图.

当V ，E 均有限元 ∣V ∣，∣E ∣≠∞时，称为有限图。我们一般讨论的都是有限图，考虑到实数集的不可数性，任何有限图都可以表示为三维空间的几何图形，使每两条边互不相交，而且边均可用直线来实现。但是若要在平面实现则不一定能办到，稍后我们会给出平面图的概念。

子图:若A 的端集与边集分别为G 的端集与边集的子集，则A 为G 的子图。若A ?G ，且A ≠G ，则A 为G 的真子图。特别地，当A 的端集和G 的端集相等，称A 为G 的支撑子图。由端点子集诱导生成的子图.

图的运算:

G1?G2, G1?G2, Gc 等

图的几种表现形式: 集合论定义, 几何实现, 矩阵表示.

图的同构; 权图.

2.1.2图的连通性

对无向图的端v i 来说，与该端关联的边数定义为该端的度数：，记为：d(vi ) 。对有向图：d +(vi ) 表示离开v i 的边数，d -(vi ) 表示进入v i 的边数

对图G=(V，E) ，若|V|=n，|E|=m，则有如下基本性质：

n

1）若G 是无向图 ∑d (v

i =1

n i ) =2m (=2E ) 2）若G 是有向图 n

+∑d

i =1(v i ) =∑d i =1- (v i ) =m 　　　

下面定义图的边序列，链，道路，环和圈：

相邻二边有公共端的边的串序排列（有限） (v1，v 2) ， (v2，v 3) ， (v3，v 4) ，?? (vi ，v j ) ，称为边序列。边序列中，无重边的，成为链(link)；若边序列中没有重复端，称为道路(path)；若链的起点与终点重合，称之为环(ring)； 若道路的起点与终点重合, 称之为圈(cycle)。

任何二端间至少存在一条径的图，为连通图。否则，就是非连通图。对非连通图来说，它被分为几个最大连通子图，即几个“部分”。“最大连通图”指的是在此图上再加任意一个属于原图而不属此图的元素，则此图成为非连通图，如下例:

G=A?B ?C=A+B+C

对于图的连通, 可以通过下面的方法给予准确的描述:

对于图G 中的任意两个端点u 和v , 如果存在一条从u 到v 的链, 称u 和v 有关系, 容易知道这是一个等价关系; 从而可以将图G 做一个等价分类, 每一个等价分类就是一个连通分支. 连通分支只有一个的图为连通图.

下面举一些图的例子:

(1)完全图Kn ：任何二端间有且只有一条边（即直通路由），称为完全图， 其边、端数之间存在固定关系:

m =? n ?n (n -1)

2??=

??2

下面是一个n=5的完全图

(2)正则图：所有端度数都相同的连通图为正则图

d(vi )=常数（i=1，2，?n ）

正则图是连通性最均匀的图

d (v ) =

2非正

则d (v ) =3

(3)尤拉图(Euler): 端度数均为偶数的连通图为尤拉图。

E u l e r 图

尤拉图的性质: 尤拉图存在一个含所有的边且每边仅含一次的环.

(4) 两部图

两部图的端点集合分为两个部分, 所有边的端点分别在这两个集合中.

完全两部图Km,n

(5)

2.1.3树:

树是图论中一个很简单，但是又很重要的概念，在图论中运用是十分重要的。 图的定义有多种, 如下面的定义：

1、任何二端有径且只有一条径的图称为树。

2、无圈的连通图称为树.

我们采用第2种关于图的定义方式, 也就是:

树: 无圈的连通图称为树.

树有以下性质:

1. 树是最小连通图，树中去一边则成为非连通图。

2. 树中一定无环。任何二端有径的图是连通图，而只有一条径就不能有环。

3. 树的边数m 和端数n 满足m=n-1

此式可以用数学归纳法证明。

4. 除单点树，至少有两个度数为1的端(悬挂点)

树上的边称为树枝 (branch)

定理2.1：给定一个图T ，若p=|V|，q=|E|，则下面论断等价：

（1）T 是树；

（2）T 无圈，且q=p-1；

（3）T 连通，且q=p-1；

证明：

1）→2），显然；

2）→3），反证：若T 不连通，它有k 个连通分支（k 大于等于2），每个都为

k

树，若第i 个树有p i 个点，则q =∑(p

i =1i -1) =p -k ≤p -2，与q = p-1相矛盾；

3）→1），p=1时，显然。设p ≥2，T 连通，且q=p-1，首先易证T 有悬挂点，不然，q =

定理2.2：若T 是树，则：

（1）T 是连通图，去掉任何一条边，图便分成两个且仅仅两个分图；

（2）T 是无圈图，但添加任何一条边，图便会包含一个且仅仅一个圈。

同时，若无向图满足（1）和（2），则T 是树。

定理2.3：设T 是树，则任何两点之间恰好有一条道路；反之，如图T 中任何两点1p i d ∑2i =1≥1p 2=p ，与q = p-1相矛盾；然后对点数进行归纳即可； ∑2i =1

之间恰好有一条道路，则T 为树。

定理2.2和2.3刻画了树的两个重要特征，事实上定理2.3也为图提供了另一个等价定义。上述两个定理的证明请读者自行完成。

支撑树(Spanning Tree)：

考虑树T 是连通图G 的子图，T ?G ，且T 包含G 的所有端，称T 是G 的支撑树。

由定义可知，只有连通图才有支撑树；反之有支撑树的图必为连通图。一般支撑树不止一个， 连通图至少有一个支撑树。支撑树上任二端间添加一条树支以外的边，则形成环(circuit)。支撑树外任一边称支撑树的连枝，连枝的边集称为连枝集或树补(Cotree)。不同支撑树对应不同连枝集。

对非连通图来说，它可以分成K 个最大连通子图，即K 个“部分”，每部分各有支撑树。K 个支撑树的集合形成图G 的主林，其余的边为林补。主林的边数称为图的阶，用ρ表示。主林的连枝数称为空度，用μ表示。有如下关系式： n=n1+n2+?+nk

ρ=( n1-1)+ ( n2-1)+ ?+ ( nk -1)=n-k

μ=m-n+k

例如：

n =11

m =12

k=3； ρ=11-3=8； μ=12-11+3=4

2.1.4割(cut)

割指的是某些子集(端集或边集) 。对连通图，去掉此类子集，变为不连通。对非连通图，去掉此类子集，其部分数增加。

割分为割端集与割边集。

1、割端与端集

设V 是图G 的一个端，去掉V 和其关联边后，G 的部分数增加，则称V 是图G 的割端。去掉几个端后，G 的部分数增加，这些端的集合称为割端集。有的连通图无割端，这种图称为不可分图。

对于连通图, 在众多的割端集中至少存在一个端数最少的割端集，称为最小割端集。最小割端集，其任意真子集不为割集。

最小割端集的端数目，称为图的联结度。联结度越大，图的连通性愈不易被破坏。

2、割边集与割集

连通图G 的边子集S ，去掉S 使G 为不连通，称S 为割边集

在众多的割集中边数最少的割集，称为最小割边集。最小割边集的任一真子集不为割边集。最小割集的边数，称为结合度. 结合度同样表示图的连通程度，结合度越高，连通程度越好。

3、基本割集与基本环（针对连通图讨论）

1）基本割集

设T 为连通图G 的一个支撑树，取支撑树的一边（枝）与某些连枝，定可构成一个极小边割集，此割集称为基本割集。即：基本割集是含支撑树T 之一个树枝的割集。基本割集有n-1个.

下面一个图来理解基本割集.

43

支撑树T={e 1e 6e 3e 4} 连枝：e 2，e 5

则基本割集：（e 1，e 5）， (e 6，e 2，e 5) ，(e 3，e 2) ， (e 4，e 5)

2）基本环

T 为连通图G 的一个支撑树，G-T 的边集为连枝集。取一连枝可与某些树枝构成环。这种包含唯一连枝的环称基本环。

每个基本环只包含一个连枝---与连枝一一对应，其数目=连枝数，共m-n+1个。

环和运算: 对于集合, 这个运算的意义为对称差运算.

通过环和运算, 由基本割集和基本环可以生成新的环和割集或它们的并集, 事实上可以生成所有的环和割集.

例2.2 通过基本环和基本割集理解基尔霍夫定律.

下面的图理解基本环.

e

连枝集 (e 6，e 7，e 8，e 9)

e 6：c 1={e 6，e 1，e 3，e 2}

e 7：c 2={e 7，e 3，e 4}

e 8：c 3={e 8，e 3，e 2}

e 9：c 4={e 9，e 4，e 5}

2.1.5 图的平面性

图G 若可以在一个平面上实现，除端点以外，任何两条边均无其他交点，则称G 是平面图。当平面图有一个平面实现后，它把全平面分成s 个区域（含包含无穷远点的开区域）。注意一个图为平面图等效于能够在球面上有一个几何实现.

设连通平面图有m 边，n 端，则s=m-n+2，此为著名的Euler 公式。这个性质可以用数学归纳法证明或树的性质证明。

m=4，n=4，s=2

定理2.4：简单连通图为平面图的必要条件是:

m<=3n-6 (n="">=3)

上述结论可以推广到有重边和自环的情形

.

重边

证：形成区域至少3边，区域周线上的边数至少3s(不考虑区域共边) ，实际每边均在二区域周线上，最多有2m 边（周线上）。考虑区域共边，有2m ≥3s ，代入Euler 公式得m ≤3n-6.

此为平面图的必要，非充分条件。

例2.3 讨论完全图K 5和完全两部图K 3,3的平面性.

定理2.5连通两部图为平面图的必要条件是:

m+4 <= 2n="" (n="">=3)

根据每个平面图G=（V ，E ），可以生成一个对偶图G' 。G 的每个平面对应于G' 的每个顶点，G 中相邻的两个面在G' 中有一些边与G 中的两个面的每一条边界的边相交，如下图所示。但是简单平面图的对偶图可能不再是简单图。

定理2.6 图G 为平面图当且仅当 G 不含K 5和K 3,3或它们的细分图为子图.

2.1.6图的矩阵表示

很多时候，需要将图表示在计算机中，这就有了图的矩阵表示。下面主要介绍关联阵和邻接阵。

1．关联阵

设图G 有n 个端，m 条边，则全关联阵 A 0=[a ij ]n ?m ；

端v i 对应于矩阵的第 I行(共n 行) ；边e j 对应于第j 列(共m 列);

其中:

?a ij =1, 若e j 与v i 关联?

?a ij =0, 若e j 与v i 不关联 在无向图中

?a ij =+1, e j 与v i 关联, 离开v i 在有向图中??a ij =-1, e j 与v i 关联, 指向v i

?a =0, e 与v 不关联j i ?ij

下面是一个例子说明关联矩阵,

例2.4

?v 1??1

???v 21???A 0=?v 3??0????v 4??0

v 10110e 1001110011??0?

1??0?v 2

e 4e 2

v 4e 33

由A 0可以看出:

(1)第i 行非零元个数等于端v i 度数, 每列有两个1;

(2)若第i 行均为0元素，则v i 为孤立端， G为非连通图;

(3)若i 行只有一个非O 元，则v i 为悬挂端;

(4)如果将A 0中每一个列中的任一个1改为-1, 则n 行之和0向量，所以最多只有n-1行线性无关，A 0秩最大为n-1。

将无向图全关联阵A 0 中每一个列中的任一个1改为-1， 再去掉任一行，得到关联阵A ，为n-1?m 阶。A 中的每一个非奇异方阵对应一个支撑树。图G 的支撑树数目可由以下方法得到：

定理2.7(矩阵-树定理)

用A T 表示A 的转置, 无向图G 的主树数目

τ(G) = det(AAT ) ，

注意上面的定理计算的主树数目为标号树的数目; 同时n-1阶矩阵det(AAT ) 可以直接写出, 主对角线的元素为相应端点的度数, 其余位置为-1或0, 而这取决于相应的端点之间是否有边. 例2.5 τ(Kn -2

n ) = n

, τ(Kn-1m-1

n,m ) = mn .

τ(K-2

n ) = n

n 的计算如下：

?n -1-1... -1?

?AA

T

=?-1n -1... ...

??

?-1-1... ... ?

??-1

-1

...

n -1?

?(n -1) ?(n -1)

?10... 0?

?

=?1

n ... 0?? ?... ... ... ... ???10

...

n ??

=n n -2

继续例2.4:

v 1v 2v 3v 4v 1?3-1-1-1?v ?2?-12-10??2-10v 3?-1-13-1?-13-1=8 v ?4?-1

-1

2??

-1

2

共有8种支撑树如下

2. 邻接阵

邻接阵是表征图的端与端关系的矩阵，其行和列都与端相对应。 令G=（V ，E ）是m 端，n 边的有向图，其邻接阵 C

=[C ij ]n ?n

其中，C ij =?

?1, 若v i 到v j 有边?0, 若v i 到v j 无边

10100

10000

01101

0??0?1??0?0??

?0

?0?

如： C =?0

?0???0

对于无向图C ij =C ji ，因此是邻接阵为对称阵。

我们可以通过对C 的一些计算，得到图G 的性质。如：计算C 的幂次可得到关于转接径长的一些信息。

若C ij (2)=1则存在k ，使C ik ? Ckj =1，即C ik = Ckj =1，i ，j 之间至少有径，径长为2；若C ij =a，则v i →v j 间有a 条径长为2的径，若C ij =0，则v i →v j 间无径长为2的径；所以， Cij (2)即为v i →v j 间径长为2即转接一次的径数。

n

(2)(2)

C

(3)

=

∑

k =1

c ik ?c kj

(2)

n n

=

∑∑

k =1s =1

c ik ?c ks ?c sj

同理，若C ij (3)=1， 则有v i →v k →v s →v j ，径长为3，即经过二次转接。 由此可得下面结论:邻接阵幂C 之元素表示了二端间转接次数不超过b-1的 径，但是经过转接的端可能重复。

已知图G 的邻接阵C, 需要解决图G 是否连通的问题? 当然通过计算邻接阵C 和C 的幂可以解决这个问题, 考虑下面的小算法, 它解决同样的问题, 但效率很高.

Warshall 1962

(1)置新矩阵 P:= C; (2)置 i = 1;

(3)对所有的j, 如果P(j,i)=1, 则对k=1,2,…,n P(j,k):= P(j,k)∨ P(i,k); (4) i = i+1;

(5)如n ≥ i转向步骤(3), 否则停止.

本节介绍了图论的简要知识，[1]和[2]介绍了很好的基础知识。[4]介绍了网络优化算法的详尽的和较新的进展。本节内容同时也借鉴[3]的一些结果。某些图论知识在以后应用是会在介绍。

b

§2. 2 最短径问题

上节中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端

赋予权值，讨论有权图。权值在各种各样实际问题中有不同的实际意义，如费用，几何距离，容量等等。本节将介绍一些算法，大部分算法可借助计算机实现。

§2.2.1 最短支撑树

给定连通图G=(V，E) ，W(e)是定义在E 上的非负函数，称W(e)为e 的权。T=(V，E T ) 为G 的一个支撑树。定义树T 的权为W (T ) =

∑W (e ) 。最短支撑

e ∈E T

树问题就是求支撑树T *，使W(T *) 最小。下面介绍求最短支撑树的方法。

1) 无限制条件的情况

Prim在1957年提出一个方法，简称P 算法。

图G 有n 端，端间“距离”d ij (i，j=1，2，3，….n) 已给定(若无边则d ij =∞) ， 找一个支撑树，使其n-1个边（树枝）的权和最小，步骤如下： P0:任取一端v 1，子图G 1={v1}，在G 1到G-G 1中取最小的d ij

v j ∈(G -G 1)

v i ∈G 1

Min

(d ij ) ≡d 12

*

得子图G 2={ v1， v2} P 1:求G 3

v i ∈G 2

v j ∈(G -G 2)

Min

(d ij ) ≡d i 3

*

得子图G 3={ v1，v 2，v 3} …

Pr-2:从G r-1求G r

v i ∈G r -1

v j ∈(G -G r -1)

Min

(d ij ) ≡d ir

*

得子图G r ={ v1，v 2，…，v r } Pr-1:重复P r-2，直至得到G n 为止 例2.5:

v v 1

4

5v 7

G 1={v1} G 2={v1，v 3}

G 3={v1，v 3，v 6} G 4={v1，v 3，v 6，v 7} G 5={v1，v 3，v 6，v 7，v 2} G 6={v1，v 3，v 6，v 7，v 2，v 5} G 7={v1，v 3，v 6，v 7，v 2，v 5，v 4} 则W(T)=15

可以看出， Prim算法第K 步运算，是以G k 作为整体寻找至G-G k 的最短边，每次并入G k 的边总是保持余下m-k+1个中最短的，因此算法终止时，所得的支撑树为最短者(可用数学归纳法证明) 。

从算法始至终止，共进行n-1步，每步从k 个端与n-k 个端比较，须经k(n-k)-1次，可得总计算量 ∑[k (n -k

k =1n -1

-1]=

16

(n -1)(n -2)(n -3)

约为n 3量级。当n 很大时，可借助计算机实现。

另一个算法由Kruskal 在1956年提出:

设G (k)是G 的无圈支撑子图, 开始G (0)=(V,φ) 。若G (k)是连通的, 则它是最小支撑树；若G (k)不连通, 取e (k)为这样的一边, 它的两个端点分属G (k)的两个不同连通分图, 并且权最小。令G

(k+1)

= G+ e, 重复上述过程。

(k)(k)

上面算法的实现过程需要排序算法； Rosenstiehl 和管梅谷提出了另一个算法：

设G 是G 的连通支撑子图，开始G =G，若G 中不含圈，则它是最小支撑树；若G (k)中包含圈，设μ是G (k)中的一个圈，取μ上的一条权最大的边e (k)，令G (k+1)= G (k)-e (k)，重复上述过程。

上面算法的实现过程需要解决如小问题： 对于一个无向图G, 如何寻找其中的圈? 可以通过搜索图中度为1的顶点而逐步简化.

上面算法的实施过程, 都是一种贪心法原理的应用; 从局部最优的结果中寻找全局最优的结果. 问题如果复杂, 这种方法一般只能找到准最优解.

2) 有限制情况

在许多情况下，不但要求最短支撑树，还要求一些额外条件。有两种解决此类问题的方法穷举法和调整法。穷举法就是先把图中的支撑树穷举出来，按条件逐个筛选，最后选出最短支撑树。这种方法较直观，但很烦琐。下面讨论调整法。以Esau-William 算法为例(解决一种特定的问题):

问题:

图G 有n 个站, 其中已知v 1是主机，已知各边间距离d ij ，以及各个端站

(k)

(0)

(k)

的业务量F i （i ，j=1，2，…，n ），要求任端至v 1的径边数<>

算法主要思想:

从上图开始(星形树), 采用贪心法原则, 逐步用边e ij (2≤i , j ≤n ) 替换v i

至v 1的边, 为此需要计算转接损失矩阵T =(t ij ) , 每次选用一条边使新树的长度减少最多, 但每次要注意新树是否满足限制条件。实质上，每次都和上次得到的树做比较，看看能否有进展。

步骤：

EW 0：起始，n 个端为n 个部分，邻接阵为全零阵；

EW 1：计算到v 1各个部分的距离D 1i ，和不在同一个部分内的两端之间的边的转接损失t ij

D 1i =min (d 1i )

G v v i 是包含i 的部分

i ∈G i

t ij =d ij -D

1i

EW2：t i *j *=min (t i , j

ij )

测试增加边(i*,j *) 边后是否仍满足条件，若满足，在邻接阵置 a i *j *=1；若不满足，则重复EW 2；

EW3：考虑形成的新的部分，若部分数大于1，返回；等于1，终止； 说明：若t ij >0, ?i , j , 则说明星形树已经是最好。

实例2.6(其中K=3, M=50)：

v v v 1

计算T 矩阵：

v 2?0?v 3-9?T =

v 4?-4?v 5?1

-10-55

-2-1103

4

5

-1??-5? -1??0?

t 34=-11 最小，

取边（3, 4）最替换边(3, 1)；

如此反复，最后得树为: {(3, 4), (4, 1), (2, 5), (5, 1)} 树长=12

上面的例中, 如果将边(3, 2), (2,1)和(4, 5)的权改为2, 3.5和3.5, 容易得到一个简单的反例, 存在一个树长为11的支撑树, 也满足问题中要求的限制条件，说明上述EW 算法得到的不是全局最优解.

§2.2.2、端间最短径

当网络结构已定，我们需要寻找端间的最短距离和路由。分两种情况： 寻找指定端至其它端的最短径和路由，我们采用Dijkstra 算法； 寻找任意二端最短径和路由, 用Floyd 算法。 1) 指定端至其它端最短径和路由算法:

已知 图G=(V，E) 及d ij ，求端v s 至其它端的最短径和路由，用Dijkstra 算法：

v v 2

由上图可以看出：

直边不一定是最短径，如d s2，其实v s 与v 2间最短径长为3(经v 3转接) 。但可肯定，与v s 相连的直边最小的一个必定为最短径(如e s3) ，其它转接至v s 必不短。因此，算法从始找邻近端， 从v s 最邻近端找起， 每次得一个最短径。

下面我们介绍Dijkstra 算法，暂时不考虑端有权, 对于端有权的情况稍后处理; 首先我们会用到下列计算中的名词：

置定：某端置定即表示得到了至该端的最短径 标值：至该步时的暂时最短径，（置定端可供转接） w i 为v s →v i 暂时的的最短径长 w j*为v s →v i 的置定时的最短径长

Dijkstra 算法步骤：

端点集合V p 表示置定的端点集合, V- Vp 为没有置定的端点集合;

D0 开始置定v s ，w s*=0（v s →v s ），其它端暂置w j =∞( 如果边(s, j)存在, wj = ds,j ) D1 计算未置定端v j 的标值的公式

w j :=min（w j ，w i +dij ）, 其中v i ∈V p v j ∈V- Vp D2 取最小值,

w j* = min wj 然后, 置定端v j*∈V p ; 当所有端置定，算法结束. 不然, 返

回D1.

上面的算法没有给出取得最短径的路由, 不过对于路由可以很简单处理. 路由的给出方法可以有许多种, 如前向路由和回溯路由等. 对于Dijkstra 算法, 可以给出回溯路由, 即给出最短径的前一个端点的标号, 而这个端点标号可以在算法D1的更新计算中获得; 每个端点的标号可以由两部分组成, 即距离和前一个端点标号.

例2.6：

v 2

v 4

D 算法计算量:当有个k 端已置定，需做(n-k)次加法，(n-k)次比较以更新各端的暂定值，(n-k-1)次比较求最小值，则总计算量约为

n

∑3(n -k ) =

k =1

3n (n -1)

2

→O (

32

n )

2

对于Dijkstra 算法, 提出若干问题如下: 1 如果端点有权如何处理?

2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？

上面Dijkstra 算法中使用的为Label-setting 的方法, 下面介绍一个用Label-correcting 技术的方法, 效率要高许多。

不失一般性，假设是G 一个有向图，用d(i)记从s 至i 的距离，pred(i)记路由s →i 的上一个顶点(回朔路由), A(i)记录从i 出发的所有边的集合。算法如下：

begin

d(s):=0 and pred(s):=0; d(j):=∞ List:={s}; while List ≠ φ do begin

从 List 中去掉一个元素i ; 对每个边(i, j) ∈A(i) do

if d(j)> d(i)+Cij then

begin

for each j∈V-{s};

d(j):= d(i)+ Cij pred(j):=i；

if j ?List, then 将j 并入List; end;

end; end;

上面的算法中没有指明List 的结构, 如果将List 组织为一个队列, 算法效率会更高, 计算复杂度为O(nm), 大约为目前最快的算法, 上面两个算法的解决思路的比较是很有意义的。

值得注意的是，如果附加一些条件，那么问题便很复杂了。如果边有两个权, 相应的算法就复杂的多, 并且很可能无多项式算法.

2、所有端间最短径算法

Floyd 算法解决了图G 中任意端间的最短距离和路由，并且也采用Label-correcting 的方法。

给定图G 及其边 (i, j)的权d ij (i，j=1，2，3，…，n); F0：初始化距离矩阵W (0)和路由矩阵R (0) ; W (0)=[ Wij (0)] n ?n 其元素：

W ij

(0)

同时 R (0)=[ rij (0)] n ?n

r ij

(0)

?d ij 　若e ij ∈E (有边) ?

=?∞　若e ij ?E (无边) ?0　　　　若i =j ?

(不同于邻接阵)

?j 　若W ij (0) ≠∞=?

0　, 　其它?

F1：已求得W (k-1) 和R (k-1)，求W (k) 和R (k) ; w ij (k)=min[wij (k-1)，w ik (k-1)+ wkj (k-1)]

r i , j

(k )

(k ) (k -1) (k -1)

?

(k ) (k -1)

　若w i , j =w i , j ??r i , j

F2：若k<>

上面的路由方法为前向路由，容易更改算法使它的路由为回溯路由; 算法要执行n 次迭代, 第k 次迭代的目的为经过端k 转接是否可以使各端之间距离缩短. 从本质上讲, Floyd算法的迭代过程就是保证满足下面的定理成立.

定理2.8 对于图G , 如果w(i, j) 表示端i 和j 之间的可实现的距离, 那么w(i, j) 表示端i 和j 之间的最短距离当且仅当对于任意i, k, j有:

w(i, j) ≤ w(i, k) +w(k, j)

Floyd 算法计算量 : w ij (k)=min[wij (k-1)，w ik (k-1)+ wkj (k-1)]中，每定一k 值，求w ij 经1次加，1次比较，求一次迭代为n 2次加，n 2次比较，共n 个迭代，所以其运算量为n 3级; 显然比重复使用Dijkstra 算法效率高，同时存储效率也要高。 对于Floyd 算法, 同样提出若干问题如下: 1 如果端点有权如何处理?

2 如果边的权可正可负, 算法是否仍然有效? 3 算法是否对有向图也适用？

例2.7 给定一个无向图G , 求任意两端之间最少转接次数和路由. 例2.8图有六个端，端点之间的有向距离矩阵如下：

v 1v 1v 2v 3v 4v 5v 6

?0?1??2?∞??∞??7

v 2

90∞∞6∞v 3140522

v 43∞∞08∞

v 5∞71202

v 6∞??∞?∞??7?5??0?

1. 用D 算法求V1到所有其他端的最短径长及其路径。 2. 用F 算法求最短径矩阵和路由矩阵，并找到V2至

V4和V1至V5的最短径长及路由。

3. 求图的中心和中点。

解：

10 2∞ 9 9 8 8 3∞ 1 4∞ 3 3 5∞ ∞ 6∞ ∞ ∞ 7 7 V 1 V 3 V 5 V 4 V 3 W 1＝0, 1 W 13＝1, 1 W 15＝2, 3 W 14＝3, 1 W 16＝7, 5

2. F 算法

最短路径矩阵及最短路由阵为W 5，R 5 v 2→v 1→v 4有向距离为4

v 1→v 3→v 5有向距离为2

?0913∞∞??023400???104∞7∞????103050??W ?2∞0∞1∞?00050?0=?

?∞∞5027?R =?10?

??003056???∞62805??023406???7∞2∞20????103450???0913∞∞??023400????10247∞???101150??W =?211051∞?1?

R ?110150?1=?

?∞∞5027???003056???∞62805??023406???71621020????113150???091316∞??023420????10247∞???101150??W ?211051∞?2=?

R =?110150?2?

?∞∞5027???003056???762805??223406???71621020????11315

0??

?09132∞??023430????10243∞???101130??W =?211051∞?3?

R ?110150?3=?

?7165027???333056???462805??323306???4132720????31

3

3

5

0???0913210??023434????1024311???101134??W ?21105112?4=?

R =?110154?4?

?7165027???333056???462705??323306???413272

0????31335

0???081327??053435????102438???101135??W ?270516?5=?

R ?150155?5=?

?684027???555056???462705??323306???4

8

2

7

2

0??

??3

53

3

5

0??

3.

Max W 5

ij =(8, 8, 7, 8, 7, 8)

中心为V j

3或V 5

∑W

5ij

=(21, 18, 21, 27, 24, 23) 中点为V 2

j

在实际问题中，除了求最短径外，如当主路由（最短径）上业务量溢出或故障时，需寻求次短径或可用径。次短径指备用径，可用径指一批满足某种限制条件的径（如限径长，限转接次数….）。但这些问题一般没有多项式算法, 可以根据实际情况采用某种贪心策略获得近似解.

3、网的中心与中点

如网络用图G=(V, E)表示, 根据Floyd 算法的计算结果可以定义网络的中心和中点.

中心:

对每个端点i, 先求max (w (n ) i , j )

j

此值最小的端称为网的中心，即满足下式的端i*：

m a x (w (n ) (n )

j

i *,j

) =min i

[max j

(w i , j )] 网的中心宜做维修中心和服务中心。 中点:

将“平均最短径长”最小的端，定义为中点，

先计算 s i = [∑w (n ) i , j ], 然后求出s i 的最小值, 相应的端点为中点.

j

网的中点可用做全网的交换中心。

§2.3网络流量问题

网络的目的是把一定的业务流从源端送到宿端。流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量以及路由规划。本节及下节中关于流量的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要输出的只有一种商品或业务。通信网络的服务对象有随机性的特点, 关于通信业务随机性特点将在下一章中考虑, 本节中假设网络源和宿的流量为常量.

§2.3.1基本概念

给定一个有向图G=（V ，E ），C(e)是定义在E 上一个非负函数，称为容量；对边e ij ，边容量为C ij ，表示每条边能通过的最大流量。设f={ fij }是上述网络的一个流，若能满足下述二限制条件，称为可行流。 a)非负有界性：0≤f ij ≤C ij ； b)连续性: 对端v i 有：

∑

v j ∈Γ(vi )

f ij -

∑

f ji

v j ∈Γ' (vi )

?F

?=?-F ?0?

v i 为源端v i 为宿端 其他

v(f) = F为源宿间流{fij }的总流量.

式中 Γ（v i ）={vj : ( vi ， vj ) ∈E} 流出v i 的边的末端集合; Γˊ(vi )={vj : ( vj ， vi ) ∈E} 流入v i 的边的始端集合;

有n 个连续性条件，共有2m+n个限制条件，满足上述二限制条件的流称为可行流。

需要解决的问题分为两类: 1 最大流问题

在确定流的源和宿的情况下, 求一个可行流f, 使v(f) = F为最大; 2 最小费用流问题

如果边(i,j)的单位流费用为d i,j , 流f 的费用为: Φ=

(i , j ) ∈E

∑d

i , j

f

i , j

所谓最小费用流问题:

在确定流的源和宿的情况下, 求一个可行流f, 使φ为最小.

下面介绍割量和可增流路的概念.

设X 是V 的真子集，且v s ∈X ，v t ∈X ，（X ，X ）表示起点和终点分别在X 和X c 的边集合，这个集合当然为一个割集, 割集的正方向为从v s 到v t 。 割量定义为这个割集中边容量的和:

c

c

C (X , X c ) =∑C ij

v i ∈X , v j ∈X

c

对可行流{fij }:

f(X，X c ) 表示前向边的流量（和）∑f ij, 其中v i ∈X ，v j ∈X c f(Xc ，X) 表示反向边的流量 (和) ∑f ji, 其中v i ∈X ，v c j ∈X 则源为v s 宿为v t 的任意流f 有:

(1) v(f)=f(X,Xc )-f(Xc ,X), 其中v s ∈X ，v t ∈X c 证明：

对任v i ∈X : ∑f v i =v s ij -

∑

f ?F ji =?

v j ∈V

v j ∈V

?0

v i ≠v s

对所有v i ∈X, 求和上式：

∑∑

f ij -

∑∑

f ji =

∑∑

f ij -

∑∑

f ji

v i

∈X v

j

∈V

v i ∈X v j ∈V

v i ∈X v j ∈X

c

v i ∈X v c

j ∈X

=f (X , X c

) -f (X c

, X ) =F =v (f )

v t

∑∑

f ij

∑∑

f ij

v i ∈X v j ∈X

c

v c

i ∈X

v j ∈X

源端 s: fs1+fs2+fs3

中转端 1: f14 -(fs1+f21) 中转端 2: f21+f23 -(fs2) 中转端 3: f3t -(fs3+f23+f53)

∑∑

f ij

-∑∑

f ij

v c

i ∈X v j ∈X

v c

i ∈X

v j ∈X

= f14+f3t -f 53= f(X,Xc )-f(Xc ,X)=F (2) F≤C(X,Xc

)

由（1）及f(X, Xc ) 非负，可得：

F =f (X , X c

) -f (X c

, X ) ≤f (X , X c

) ≤C (X , X c

)

下面讨论可增流路的概念。

从端s 到端t 的一个路，有一个自然的正方向，然后将路上的边分为两类：前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（f ij

若流{ fi,j }已达最大流，f 则从源至宿端的每条路都不可能是可增流路，即每条路至少含一个饱和的前向边或流量为0的反向边。

§2.3.2 最大流问题

所谓最大流问题，在确定流的源端和宿端的情况下, 求一个可行流f, 使v(f) 为最大。对于一个网络，求最大流的方法采用可增流路的方法，下面的定理2.9为这种方法提供了保证.

如果网络为图G = (V, E),源端为v s , 宿端为v t . 定理2.9 (最大流-最小割定理) 可行流f * = {在从v s 到v t 的可增流路. 证明:

必要性: 设f *为最大流, 如果G 中存在关于f *的从v s 到v t 的可增流路μ.

*令 0 <θ= min[min="" (c="" i="" ,="" j="" -f="" i="" *,="" )="" (f="" ,="" j="" min="" i="" ,="" j="" )="" ]="">

(i , j ) ∈μ

+

f

*i , j

}为最大流当且仅当G 中不存

(i , j ) ∈μ

-

构造一个新流f 如下:

如果 (i , j ) ∈μ+, f i , j =f i *+θ , j

-θ 如果 (i , j ) ∈μ-, f i , j =f i *

, j

如果 (i , j ) ?μ, f i , j =f i *, 不难验证新流f 为一个可行流, 而且, j

v(f)=v(

f

*i , j

)+θ, 矛盾.

充分性: 设f *为可行流, G中不存在关于这个流的可增流路. 令X * = {v|G中存在从v s 到v 的可增流路},从而v s ∈X *, vt ?X *.

=c i , j 对于任意边 (i , j ) ∈(X *, X *c ) , 有f i *, j =0 对于任意边 (i , j ) ∈(X *c , X *) , 有f i *, j

这样, v (f *) =c (X *, X *c ) , 那么流f *为最大流，(X *, X *c ) 为最小割。证毕。 网络处于最大流的情况下，每个割集的前向流量减反向流量均等于最大流量且总存在一个割集(X *, X *c ) ，其每条正向边都是饱和的，反向边都是零流量；其割量在诸割中达最小值，并等于最大流量。

推论：如果所有边的容量为整数，则必定存在整数最大流。

求最大流的基本思想是：在一个可行流的基础上，找v s →v t 的可增流路，然后在此路上增流，直至无可增流路时，停止。

具体方法(M算法) ：从任一可行流开始，通常以零流{fi,j =0}开始。 （1）标志过程：从v s 开始给邻端加标志, 加上标志的端称已标端; （2）选查过程：从v s 开始选查已标未查端

查某端，即标其可能增流的邻端; 所有邻端已标，则该端已查。

标志宿端，则找出一条可增流路到宿端，进入增流过程。 （3）增流过程：在已找到的可增流路上增流。 步骤：

M 0：初始令f i,j =0

M1：标源端v s ：（+，s ，∞）

M2：从v s 始，查已标为查端v i ，即标v i 的满足下列条件的邻端v j ， 若（v i ,vj ）∈E ，且c i,j > fi,j ， 则标v j 为: (+，i ，εj ) 其中εj

=min(ci,j -f i,j ，εi

) ε

i

为v i 已标值。

若（v j ,vi ）∈E ，且 fj,i >0， 则标v j 为: (-，i ，εj ) ，

其中ε

j

=min（ε

i

，f j,i ）其它端v j 不标。

所有能加标的邻端v j 已标，则称v i 已查。 倘若所有端已查且宿端未标，则算法终止。 M3：若宿端v i 已标，则沿该可增流路增流。 M4: 返回M1。

上面的算法是针对有向图且端无限制的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。

若端i 和端j 之间为无向边，容量为C i,j ，那么将它们化为一对单向边 (i，j) 和(j，i) ，并且它们的容量均为C i,j 。

如果端i 有转接容量限制C i ，那么将V i 化为一对顶点V ' i , V ' ' i ，原终结于V i 的边全部终结于V ' ' ' ' i ，原起始于V i 的边均起始于V i ，且从V ' i 至V ' i 有一条边容量为C i 。

对多源多宿的情况，设原有源为V s 1, V s 2,..., V sl ，原有宿为V t 1, V t 2,..., V tk ，要求从源集到宿集的最大流量，可以虚拟一个新的源V s 和新的宿V t ，源V s 到

V s 1, V s 2,..., V sl 的各边容量均为无限大，V t 1, V t 2,..., V tk

到宿V t 的各边容量也为无

限大，这样多源多宿的问题就化为从V s 到V t 的最大流问题。见下图：

v s

v t

仔细考虑一下会发现，前面介绍的算法在任何网络中是否一定会收敛，也就是说会不会不断有增流路，但却不收敛于最大流呢？如果边的容量均为有理数，是不会出现这种情况，也就是说一定会收敛。但若边的容量为无理数，就不一定收敛。对于计算量的问题, Ford和Fulkerson 曾给出下面的例子。

如图所示，一个四个节点的网络，求v s 至v 的最大流量。假设按前述算法，

t

并且按如下顺序从f=0开始增流： 例

2.8

v s

p v t

v s →q →p →v t 增流1； v s →p →q →v t 增流1;

显然，这样需要2n+1步增流才能找到v s →v t 的最大流，流量为2n+1。这个例子说明前述算法虽然能够达到最大流，但是由于没有指明增流方向，导致有可能象这个例子一样，效率很低，这个例的计算工作量与边容量有关。1972年，Edmonds 和Karp 修改了上述算法, 在M2步骤时采用FIFO 原则(在选哪个端查时), 从而解决了这个问题；新算法一方面收敛, 同时也为多项式算法. 后来，人们提出了许多改进的算法，如Dinits 算法和MPM 算法，其主要思想是赋予网络一些新的结构可以使算法更有效率等等。有兴趣者可参阅[2]。

§2.3.3最小费用流问题

如果网络为图G = (V, E), 源端为v s , 宿端为v t . 边(i,j)的单位流费用为d i,j 流f 的费用为: Φ=

(i , j ) ∈E

∑d

i , j

f

i , j

所谓最小费用流问题:

在确定流的源和宿的情况下, 求一个可行流f, 使φ为最小.

最小费用流问题是线性规划问题，但也可用图论方法求解, 效率更高。对于它的存在性可以这样理解，流量为F 的可行流一般不是唯一的，这些不同的流的费用一般也不一样, 有一个流的费用最小.

寻找最小费用流，用负价环法(Klein, 1967) , 所谓负价环的意义如下: 负价环为有向环, 同时环上费用的和为负。负价环算法的具体步骤如下： K 0：在图 G上找任意流量为F 的可行流f; K1：做流f 的补图; 做补图的方法如下:

对于所有的边e i , j , 如果c i , j >f i , j , 构造边e i 1, j ,

容量为:c i , j -f i , j , 单位流费用为: d i,j ;

对于所有的边e i , j , 如果f i , j >0, 构造边e i 2, j ,

容量为:f i , j , 单位流费用为: -d i,j ;

K2：在补图上找负价环C -。若无负价环，算法终止。 K3：在负价环C -上沿环方向使各边增流 增流数：

δ=min (c i *, j )

(i , j ) ∈C

-

K4： 修改原图的每边的流量，得新可行流。 K5： 返回k1。

例2.9：已知c i,j ，d i,j ，要求F=9。求最小费用流。

v s

4, 6

v t

v s

t

上面可行流安排总费用为: φ=102. 下面做补图, 寻找负价环, 调整可行流.

v

Φ=96

δ

=min -

(3, 3, 4) =3

C

v 已无负价环

价环

零价环上增流: 得另一最小费用流

4X 6=243X 6=18v s

原53=155X 3=15现6X 3=18

现6X 3=18

24+15+15=54 18+18+18=54

前面负价环的算法中, 如何寻找负价环? 这个问题可以应用Floyd 算法解决. 最小费用流问题是网络流问题中比较综合的问题，和线性规划问题的关系非常密切, 对于它的研究仍将继续进行。

第2章 通信网拓扑结构

参考文献：

1.Bondy ,J.A.and U.S.R.Murtly, Graph theory with applications,The Macmillan Press Ltd,1976

2. 图与网络流理论，田丰，马仲蕃，科学出版社，1987

3. 通信网理论基础，周炯磐，人民邮电出版社，1991

4.RAVINDRA K.AHUJA THOMAS L. MAGNANTI

NETWORK FLOWS. Prentice hall 1993

5.ORLIN,J.B.1988 A faster strongly polynomical minimum cost flow algorithm JAMES B.ORLIN Procedings of the coth ACM Symposium on the Theory of Computing

6. 线性规划最新进展，马仲蕃，科学出版社，1994

7. 《运筹学》，清华大学出版社，1990.1

PP377-387 36

范文五：【doc】论通信网的分层体系结构

论通信网的分层体系结构 伍桀技术协作信息

论通信网的分层体系结构

?郭立佳

通信网是通信的高级形态和高级形式,它具有跨地域的特点.虽然从信息共 享的角度看,通信网与计算机系统内部的信息共享并没有多少区别,但是从技术 实现上看,通信的复杂性要远远高于后者.这种复杂性的主要原因就是通信网的 跨地域性引起的.长距离的信息传输有2个直接后果,那就是传输速度受限制和 传输质量受限制.这些限制导致了通信网复杂的结构.现代通信网都采用分层的 体系结构来实现其复杂的功能.

分层的体系结构大大降低了现代通信网设计的复杂性,所以绝大多数网络 都是按层为单位来组织的.不同体系结构的网络,其协议层的数量和各层的功能 都不尽相同.虽然如此,各个不同分层的网络体系结构一般都要求每一层向它的 上一层提供相应的服务,并且对上一层屏蔽其如何完成的细节.相邻层之间有接 口,接口定义了下层向上层提供的服务.

下面我们将介绍2个着名的分层模型:OSI/RM和TCP/IP. 一

,OSI/RM

早在20世纪80年代初,国际标准化组织就完成了基于功能分层概念的网 络体系结构模型,即"开放系统互连参考模型,称为IS07498.这里的"开放系统" 指任何信息系统,只要遵循这一标准,就可以与其他遵循这一国际标准的系统互 连和互通.

现在OSI/RM被公认为是现代通信网的一种基本结构模型.OSI模型将通 信处理过程分为7层,将通信网的功能分配到OSI参考模型相应的各层.各层相 对独立,或者说下层对上层屏蔽厂所有的细节,从而使得分配到各层的任务能够 独立实现.这样当其中一层提供的实现细节变化时,不会影响其他层. 1.物理层.

该层的功能是传输原始比特信息.在这一层,人们通常关心像每比特持续多 长时间,电平高低范围,插座用几根针等问题,这涉及到一些机械的,电气的和功 能的一些接口.

在这一层数据的单位是比特.

2.数据链路层.

数据常被简称为链路层.链路层的主要功能是在物理信道上建立具有一定 传输格式的点到点逻辑连接.这一层的基本数据单位是帧,数据链路层要保障传 输的帧被正确接收到.因为物理层传输的比特可能出错,所以数据链路层需要有 差错控制功能.数据链路层的另一个功能是流量控制,即控制发送方发送数据的 速率,以免接收方来不及接收.

3.网络层.

网络层的关键问题是决定分组从源节点通过哪条路径到H的节点.路径的 选择可以采用静态的选径表,也可以根据网络的负载情况动态的决定,还可能在 发起通信时决定.为配合选径,网络层还可能有其他的一些工作,比如差错控制 和处理等.网络层的基本数据单位是"包"(Packet),或称为"分组". 4.传送层.

传送层的主要功能是为端到端的2个对等实体提供透明的数据传输.传送 层从其上层接收数据,然后交给网络层,其中可能把数据划分成小的单元.传送 层对上层提供的服务可能是可靠的,按发送顺序传递数据的端到端通道,也可能 是不保证传输数据顺序的报文传输服务.现代的计算机系统往往同时运行着多 个进程,它们可能都需要与远方节点通信,传送层还负责把多个传送连接复用到 一

个网络连接上,使它们看起来在同时传输,这就是所谓的"服务接人点"(SAP, ServiceAccessPoint).

5.会晤层.

会晤层的功能类似传送层,但功能更强.会晤层的一个功能是管理"对话", 这包括实体的身份鉴别,半双工和全双工等功能.会晤层的另一个重要功能是会 晤同步,一旦网络出现故障,会晤层可以根据同步点,重新传输部分数据,而无需 重传所有数据.一般来说会晤层的功能较少.

6.表示层.

表示层为高层提供数据格式方面的服务.比如,数据的压缩,数据的加密,格 式转换等工作.数据压缩的目的是减少传输的比特,而数据加密可以增加安全性 互程技术

和保护秘密信息.在通信双方交换的信息有特定的意义时,比如是姓名,年龄,日 期,金钱等内容时,就会涉及到用整形数,浮点数或字符串之类的表示形式,而这 些形式在不同的计算机上可能有不同的表示方法.表示层可以在这一层提供一 个一致的格式.

7.应用层.

应用层是OSI/RM的最高层,它包含了各式各样的协议,其功能取决于用户 和网络服务的内容.应用OS1参考模型传输信息时,在发送端需要发送进程从高 到低依次将数据传递给各层进行处理.发送进程首先把数据交给应用层.应用层 给数据报文附加一个应用报文头,即AH,作其他相应处理后交给表示层.各层协 议处理的基本数据单元,称为协议数据单~(PDU,Pmtoc~DataUni0.不同的协议 层都有自己的协议数据单元.

二,TCP/IP

传输层协议fI'CP,TransmissionContmlProtoca1)和网络互连协议(1P,Intemet Proto—cs1)",是20世纪70年代中期美国国防部为ARPANET(I~II国际互联网的前

身)开发的网络体系结构和协议族.实际上TCP和IP只是这个协议族里最有代表 性,最能体现该体系核心思想的协议,它们如此重要,以至人们用TCP/IP来称 呼整个协议族和它们所代表的网络体系结构.

与OSI参考模型不同,TCP/IP协议族的设汁者从一开始,就把协议设计问 题的重点放在了异种网络互连上.所谓异种网络,即遵从不同网络体系结构的网 络.ICP/IP的目的不是要求各种网络都遵循一种标准,而在现有不同协议标准 的情况下,解决这些问题,实现异种网络的互连.

TCP/IP由4个层次组成,从高到低依次是:应用层,传输层,1P层和网络接 口层.需要注意的是,TCP/IP体系结构的某些层的名称虽然和OSI参考模型相 似,但它们的内部细节和功能存在着很大的差别.OSI/RM的最底层——物理

层,被包含在网络接口层中.

1.应用层.

TCP/IP体系结构的应用层实际上向用户提供了应用程序,比如文件传输协 议(VTP),电子邮件(E—mail),超文本传输协议(H'IqP,Hyper,TextTrans~rPmt~01),

新闻组(NewsGroup),远程登录(Telnet)等.

2.传输层.

TCP/IP体系结构的传输层提供应用程序之间f即端到端)的通信.这一层使 用了2种不同的协议.一种是传输控制协议(TCP,TransmissionControlProtocO1),

提供端到端之间的可靠传输,数据传送单位是报文段,即报文;另一种是用户数 据报协议(UDP,UserDatapamProtoc01),在端与端之间提供不可靠服务,但传输效 率在一些情况下比TCP高,数据传送单位被称为数据报(Datagram),实际上也是报 文.

3.网间网层.

TCP/IP体系结构的网间网层负责相邻网络之间的通信,简称为IP层,IP协 议是该层的核心,数据传送单位是数据包,即分组.其地位类似于OSI参考模型 的网络层,向其上层提供不可靠的数据包传输服务,即无需确认的数据包传输. 网间网层的功能主要包括3个部分:?处理传输层的报文发送请求,将数据 报文打包,择去往目的地址的路径;?处理接收到的数据包,即转发该包,或将该 包交传输层;?处理互联网控制消息协议(1CMP,IntemetControlMessageProtocO1)

包,ICMP是网间网层的另一个重要协议.

4.网络接口层.

网络接口层是TCP/IP的最底层,负责接收网间网层发来的数据包并通过 网络发送,或者从网络上接收物理帧,抽出IP数据包,交给网间网层.一般来说, 它包含了OSI/RM的物理层和数据链路层,有时还有网络层.

网络接口有2种类型:一种是设备驱动程序;另一类是有自身数据链路协议 的复杂子系统.

现在TCP/1P协议族还在发展之中,国际上与互联网和TCP/IP相关的标 准主要由互联网工程仟务组(1ETF,IntemetEngineeringTaskForce)负责. (作者单位:铁通佳木斯通信段)

?

l09

转载请注明出处范文大全网 » 通信网的基本结构