线缆布线优化问题模型分析

2010-08-29魏传佳武汉工业学院数理科学系湖北武汉430023

科技传播 2010年19期

魏传佳武汉工业学院数理科学系，湖北武汉 430023

0 引言

线缆布线是随着计算机网络兴起而快速发展起来的工程技术，在布线总体框架上有了比较成熟的综合布线技术[1]，对计算机网络规模的扩充起到了重要的作用。以往线缆布线主要考虑节省线缆和综合外观[2]，对于线槽中的线缆交叉问题[3]考虑的比较少。尤其对于大型网络来说，这种线缆交叉会对网络性能产生重大的影响。本文根据综合布线技术，对线槽中的线缆交叉提出一种分层布线优化模型，解决了线缆交叉问题。

1 线缆布线优化问题理论基础

大规模并行计算机网络由计算节点系统，网络交换节点系统，光缆系统组成，计算节点由大规模的主机系统组成，主机分别连接在计算节点上，网络交换节点由大规模的服务器系统组成，服务器分别连接在网络交换节点上。计算节点通过光纤系统连接到各个网络交换节点上，如果光缆[4]通过地沟线槽以全互联方式将计算节点与网络交换节点连接起来，必然在地沟线槽中产生大量的线缆交叉问题，对此提出利用分层布线的思想，对交叉线缆进行分层布线。如果两条线缆交叉，就将其布在地沟线槽的不同层，并保证在同一层中的线缆不交叉，同时为了减少工程施工量，分层布线的层数越少越好。

线缆布线优化问题是针对网络交叉线缆进行分层布线，并使得布线层数最少，层间和每一层的内部线路都不存在交叉的情况。

为了解决线缆交叉，又要确保线缆不交叉的同时保证所布线的层数最少，需要以下的图论知识作为基础。

G（V,E）表示一个图， V表示图的顶点集合[5]， E表示点和点之间的连线集合，连线称为边；如果边全都是有方向的，那么称为有向图，如果边全都是没有方向的，那么称为无向图。

给定无向图G（V,E）及颜色集合C 。图的顶点k-着色为：用图C中的颜色对图G（V,E）的顶点着色[6]，使得每一个顶点着一种颜色，且相邻的顶点颜色不同。这里 V = {v1, v2, v3,⋅⋅⋅,vn};E 是边的集合 E = {e1, e2, e3,⋅⋅⋅,en};C是颜色的集合 C = {c1, c2, c3,⋅⋅⋅,cn};

极大独立集：I是G的一个顶点子集，I中任两个顶点不相邻，则I是图G的一个独立集。若独立集I中增加任一除I集外的顶点后I不再是独立集，则I是极大独立集。在所有极大独立集中含顶点数最多的为极大独立集，此时的顶点数称为独立数。

2 线缆布线优化问题的模型的建立与求解

2.1 线缆交叉模型建立

计算节点与网络节点以全互联的方式通过地槽布线系统进行连接，即每个计算节点出来的线缆都要和每个计算节点进行互连，为简化模型，以3个计算节点，3个网络节点为例如图1所示。设Mi为计算节点，Nj为网络节点，Mi与Nj之间共有i×j条线缆，工程中计算节点与网络节点都是按规则性排列，共产生i×j条交叉线缆。对图1进行提取，设如果Mi与Nj之间有连线就用点表示，两条线缆如果有交叉就用线段表示，这样就将图1转化为一个线缆关系图，如图2所示。图2是一个无向图G（V,E）， V为Mi与Nj的节点集合，为计算节点与网络节点的连线集合。对线缆分层布线就转化为无向图G（V,E）的最小顶点着色问题。对图2进行正常顶点着色即可完成对各个顶点的着色，这里迭代3次即可。

每种颜色的集合是一个极大独立集，集合中的线缆互不相交，且不同种颜色的独立集之间的线缆互不相交，将每一个极大独立集作为布线的一层。这样就解决了线缆交叉的问题。

工程线缆布线要求：1）如果线缆交叉，则布在不同层；2）较长的线缆对于较短线缆如何布线；3）层数数量少。对于要求1）和2），可以将地槽进行分层编号{1 ,2,3,⋅⋅⋅k} ，从下至上编号，将交叉线缆布在不同层，对于较长的线缆，将其布在编号较大的位置，以节省线缆的长度。

2.2 算法步骤

1）将主干线线缆交叉转化为平面节点交叉图G；

2）将平面交叉图转化为顶点线缆交叉图G'；

3）对顶点线缆交叉图G'采用顶点着色法，对顶点进行颜色标定，得出一种颜色集合 C；

然后对除标定出同种颜色的顶点外的其他顶点继续进行颜色标定，得到另外的颜色集合C；

4）重复3）的步骤，直到G中的所有顶点都标定完毕且颜色数最少；

5）将每种颜色集合C作为一个极大独立集输出。

2.3 实例求解

根据图1的线缆交叉拓扑图，表1的线缆交叉表为基础，进行求解分析。

Mi,i=1,2,3为计算节点，Nj,j=1,2,3为网络节点。Mi-Nj，i=1,2,3；j=1,2,3为Mi与Nj之间的连线。图中每条边（Mi-Nj）表示节点间的每条线缆，此例中干线系统中总共有9条交叉线缆。为减少不必要的线缆交叉[6]，需要对图2中的线缆进行分层设计，并且使设计出的分层数能够尽可能的少，同时保证同一层的线缆不相互交叉。提取每条线缆作为平面图中的节点，令（Mi-Nj）→（i,j）。将Mi与Nj之间的连线用顶点图在平面上表示出来。

图1 3×3的线缆交叉拓扑图

图2 顶点线缆交叉图

○：表示Mi与Nj之间的连线。

Mi与Nj之间产生9条连线，图2中用9个点表示出来，以相应数字标出。根据图2，如果线缆之间有交叉，就在图3中将两个点用直线连接起来。至此，将线缆分层设计转化为求解顶点线缆交叉图的顶点分配问题。对于求出的顶点集合，各个顶点之间不存在互连，将这样的一个顶点集合设置为一层，属于这个集合的顶点的线缆布在这一层中，这样线缆之间就不存在了交叉问题。理论上直接将9个顶点分为9个集合，将9条线缆布在9层中，这样就消除了线缆交叉问题，但是在实际中这是不可能实现的，这会造成巨大的工程材料浪费，维护更加困难，不符合工程预算。对此对图3利用最优化的顶点着色方法，对顶点进行着色选取，首先对一个顶点vi进行着色，在剩下的顶点中寻找和vi不相交的顶点，将这些顶点标成同一种颜色。以此循环进行标定，直到无顶点再进行标定为止。同种颜色集合的顶点，作为一个独立集输出。如图3所示。

图3 顶点着色图

由图3得出，第一层为： {(1,1),(1,2),(2,2),(3,2),(3,3)}；第二层为：{(1,3),(2,3)}；第三层为：{(2,1),(3,1)}。即，线缆{(M1,N1),(M1,N2),(M2,N2),(M3,N2),(M3,N3)}放置在第一层；线缆{(M1,N3),(M2,N3)}放置在第二层；线缆{(M2,N1),(M3,N1)}放置在第三层。由此解决了干线布线系统线缆交叉的问题。