日加成

曼

圆鳖垫

查丛

NetworkT

echnology

／／

拳文利

用图论的基本理论对北京有线

电视光

缆

网干线网的稳

定

性进

分析．

我

国的有线电视系统起步于1974年．

随着

光

纤技术的日加成熟．

1994年北京

开始利

用

光缆和电缆相互结合的方式来

组建有

线

电视网络．即混合光纤／同轴有

线电视

系统(H

y

brid

FiberCabIe

，

HFC)。现在．北京的有

线电视系

统干线

部分

已

经建设

为

全光网络．并实现了

860MHz带宽。

有

线

电视网在我国的普及率相当高，

无论

是数据传输环境还

是带宽

容量．比

起电信网而言具有无可比拟的优势。今

后有线电视网主要将从模拟窄带宽发展

为

宽带

数字网．以

光

缆传输为

主．发展数

字有线电视。未来的信息社会需要的是

一个不仅能传输模

拟电

视信号．还要传

输

数字电视信号．高清电视．数据，语音

等多业务的平台，而作

为

整

个有线电视

光缆网络的核心

就是其

向各个机房传输

信号的干线网络，有线电视网络

的

整

个

系统的正常传输由干线网络保证。干线

网络的稳

定

性对与

整

个电视网络的安全

性有

着至关

重

要的意义。网络

的拓扑结构

对

整

个网络的

可靠性有

着很重要的意义，

它

也是网络规

划

和设计中的基本问题。

0扎小。同纸屯1抛几现l纸

网拓扑结构

网络拓扑是

整

个网络规划和设计的首

要问题，网络的许多性质

和

它的拓扑结构

密切相

关．网络

中的路由规

划也和拓扑结

构有紧密联系。所以网络拓扑结构

的

分

析

对于一个网络来说是最基本．也

是最

重要

的问题。

北京的有

线电视

光

缆网

干线网的拓扑

结构是

环

形加星形的网状结构。整

个网络

由5个一级分

中心机房

和24个二级分中

心机房组成。其

中5个一级分中心

机房每

个机房与相邻2个级分中心机

房，形成

环

形结

构

(见

图1)。每个一级分中心机房

下面有36个二级

分中心

机房．每个二级

分中心分别与上

属一级分中心相连接．每

个二级分中心机

房还与相

邻的同属一个一

级分

中心的其他2个二级分中心

机房连

接．形成星形结构(见图2)。在

所属不

同

一级分中心的二级分中心机房

间还存在

一个

环

形结构．将二级分中心机

房进

行

连接，因此

环

形结构与一级分中心形成

的环形结构类似．在本文中．只分析计算

级分中心形成的环

形

网络。

所谓一个图G

，是指给了一个端点集

合V

，以及边的集

合

或V中元素的序对集

合f

，图一般用6=ry

，目来表示。

一个图

如

果有边

fy

，，_J

就一定有边

f匕，KJ．这个图称为无向

图。此次分

析的

拓扑结构都是无向图。

对无向图的端与该

端关联边的数目为

该端的度数，记为df¨。

2008~4YJ，RA

DIO&T

ELEVISIONINFORMATION，㈠g々}

xf；目i6

9

维普资讯

-技术专题／／

，

N

e

tworkTechnology

／／

八刀…V∑一

V5

w

任何两端问至少存在一条链的

图．为

连通图。

(5)

树

任何两端有且

只有一条道路的图称为

树．也

可以

认

为树是无圈的连通

图。树在

图

论中一个很简单．但是

又是一个很重要

的概念。

(6)

支撑树

如

果

树T是连通

图G的子图，且T包

含G的所有端．称T是G的支撑树。如

果

一个连通

图中确定了一个支撑树，图的边

集合被分

为两类，属于树的边称为树边．

不属于树的边

称为连枝。

(7)割集

割集

指的是某些端集或边

子集。对连

通

图，去掉此类子集．图变

为不

连通。

(8)割端

与

害4端集

设V是图G的一个端，去掉V和其关

联边后，

G的部分数增加，则称V是图G

的割端。去掉一个端集

合后．

G的部分数

增加．这个端的集合称为割端集。对于

连

通

图，在众多的割端集

中至少存在个端

数

最少的割端集．称为最小

割端集。最小

割端集的端数目．称为

图的点连通度或连

通度．连通度用d表示。

割边与割边集

设e是

图G的一条

边．去掉e后．

G的

部分数

增加，则称e是

图G的割

边。去掉

一个边集

合后．

G的部分数

增加．这

个

边

的

集

合称为割边集。割边集

中边数最少的

割边集．称为最小割边集。最小割边集的

边数目．称为线连通度，线连通度用p表

不。

(9)混合适通度v

Y=rai

nfXl，其中为X混合割集

“=V

≤卢≤石

≤

2m／几

，其中6为最

小度．IVl=n

，

IEl=m

。

引入

3个辅助指

标A

，，

8

口，

C

。，

C

一为最小割端

集

的数

目；

B

。为最小割边集

的数目；

A

．为最小混合割集的数目。

(10)网络可靠集

网络

是一个庞大的对象．在不同的应

用场合可靠

集

的含义会有不同的解释．这

里网络的可靠集表示为没有失效的端之间

连通，而网络可靠

度为网络处于可靠集的

概率。网络的可靠度不但和各种连

通度有

关，而且与边

和端的故障概率有关。

3对

干线网拓扑结构的分析

通信网络的拓扑结构可以用图

论

的模

型来代表．因此对有线电视光

缆网

干线网

络的拓扑结构分

析就是利用

图

论

的一些基

础理论进行分析。整

个干线网络比较复

杂．为了方便分

析．将环

形结构和星形结

构分别进行分析。

(1)

北京有线电

视光缆网

干线网中5

个一级分

中心形成的环

形拓扑结构(

见

图

1)的分析：

根据

图1的结构．其每个端点的度为

2

，即d(V

，J=d(V

2

)：d(V

3

)=d(V

4

)=d(V

5

)=2

。

此

图

共有54"端点，

5条边．即n=m=5

，

因此2m／n

。其最

小割端集的端数目为2

．

即

此

图的点连通度G【=2

。由于d=Y

≤卢

≤

6

≤

2m／n

，因此a=p=v=2

。

经计算C

。

=5×2=10

：

B

。

=5×2=10

：

A

。

=10+10+5×2=30

。

(2)北京有线电视光

缆网

干线网中1

个一级分中心与

所属6个二级分中心

形成

的星形拓扑结构(见

图2)的分析(因每

个一级分中心

下面的二级分中心的数量不

等，现以6个二级分

中心

为例)：

根

据

图2的结

构．其端点的度

d(V

z

)=d(V

3

)=dfyJ=dfy5J=df匕J=dfy7J

一

．

d(V

，J=6

。

其最小割端集

的端数目为3

，即此图

的点连通度a=3

。

此

图共有7个端点．

12条边．即n=7

，

m=12

，因此2m／n=3．4

。由于a=v

≤p

≤6≤2m／n

．由

于d

．v．口．

6都为

整

数，因此a=卢=v=3

。

经计算C

，，

=6×2=12

：

8

。

=6×2=12

；

A=12+12+6×2+15+6×2+6×2=75．

4对干线网网络可靠度的计算

假设网络用无向图6=fV

，

EJ

表示，

lVI=n

，lEI=m

。如

果每边的不可靠度为

P．每端

的不可靠度

为

q，各边、端之间的

故障概率相互独立。在

P

《1

，q

《1的条

件下，计算网络可靠度的近似计算。

首先．假设网络仅有端故障．

C

；(i

≥c【

)

表示有i个割端

的割端集的数目。此时．

网络的不可靠集可以按照割端集

来分类．

由于各个端点的故

障独立．网络可靠度可

以计算为：RfnJ=7