魏傳佳武漢工業(yè)學院 數(shù)理科學系，湖北武漢 430023

0 引言

線纜布線是隨著計算機網(wǎng)絡興起而快速發(fā)展起來的工程技術，在布線總體框架上有了比較成熟的綜合布線技術[1]，對計算機網(wǎng)絡規(guī)模的擴充起到了重要的作用。以往線纜布線主要考慮節(jié)省線纜和綜合外觀[2]，對于線槽中的線纜交叉問題[3]考慮的比較少。尤其對于大型網(wǎng)絡來說，這種線纜交叉會對網(wǎng)絡性能產(chǎn)生重大的影響。本文根據(jù)綜合布線技術，對線槽中的線纜交叉提出一種分層布線優(yōu)化模型，解決了線纜交叉問題。

1 線纜布線優(yōu)化問題理論基礎

大規(guī)模并行計算機網(wǎng)絡由計算節(jié)點系統(tǒng)，網(wǎng)絡交換節(jié)點系統(tǒng)，光纜系統(tǒng)組成，計算節(jié)點由大規(guī)模的主機系統(tǒng)組成，主機分別連接在計算節(jié)點上，網(wǎng)絡交換節(jié)點由大規(guī)模的服務器系統(tǒng)組成，服務器分別連接在網(wǎng)絡交換節(jié)點上。計算節(jié)點通過光纖系統(tǒng)連接到各個網(wǎng)絡交換節(jié)點上，如果光纜[4]通過地溝線槽以全互聯(lián)方式將計算節(jié)點與網(wǎng)絡交換節(jié)點連接起來，必然在地溝線槽中產(chǎn)生大量的線纜交叉問題，對此提出利用分層布線的思想，對交叉線纜進行分層布線。如果兩條線纜交叉，就將其布在地溝線槽的不同層，并保證在同一層中的線纜不交叉，同時為了減少工程施工量，分層布線的層數(shù)越少越好。

線纜布線優(yōu)化問題是針對網(wǎng)絡交叉線纜進行分層布線，并使得布線層數(shù)最少，層間和每一層的內(nèi)部線路都不存在交叉的情況。

為了解決線纜交叉，又要確保線纜不交叉的同時保證所布線的層數(shù)最少，需要以下的圖論知識作為基礎。

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是極大獨立集。在所有極大獨立集中含頂點數(shù)最多的為極大獨立集，此時的頂點數(shù)稱為獨立數(shù)。

2 線纜布線優(yōu)化問題的模型的建立與求解

2.1 線纜交叉模型建立

計算節(jié)點與網(wǎng)絡節(jié)點以全互聯(lián)的方式通過地槽布線系統(tǒng)進行連接，即每個計算節(jié)點出來的線纜都要和每個計算節(jié)點進行互連，為簡化模型，以3個計算節(jié)點，3個網(wǎng)絡節(jié)點為例如圖1所示。設Mi為計算節(jié)點，Nj為網(wǎng)絡節(jié)點，Mi與Nj之間共有i×j條線纜，工程中計算節(jié)點與網(wǎng)絡節(jié)點都是按規(guī)則性排列，共產(chǎn)生i×j條交叉線纜。對圖1進行提取，設如果Mi與Nj之間有連線就用點表示，兩條線纜如果有交叉就用線段表示，這樣就將圖1轉化為一個線纜關系圖，如圖2所示。圖2是一個無向圖G（V,E）， V為Mi與Nj的節(jié)點集合， 為計算節(jié)點與網(wǎng)絡節(jié)點的連線集合。對線纜分層布線就轉化為無向圖G（V,E）的最小頂點著色問題。對圖2進行正常頂點著色即可完成對各個頂點的著色，這里迭代3次即可。

每種顏色的集合是一個極大獨立集，集合中的線纜互不相交，且不同種顏色的獨立集之間的線纜互不相交，將每一個極大獨立集作為布線的一層。這樣就解決了線纜交叉的問題。

工程線纜布線要求：1）如果線纜交叉，則布在不同層；2）較長的線纜對于較短線纜如何布線；3）層數(shù)數(shù)量少。對于要求1）和2），可以將地槽進行分層編號{1 ,2,3,???k} ，從下至上編號 ，將交叉線纜布在不同層，對于較長的線纜，將其布在編號較大的位置，以節(jié)省線纜的長度。

2.2 算法步驟

1）將主干線線纜交叉轉化為平面節(jié)點交叉圖G；

2）將平面交叉圖轉化為頂點線纜交叉圖G'；

3）對頂點線纜交叉圖G'采用頂點著色法，對頂點進行顏色標定，得出一種顏色集合 C；

然后對除標定出同種顏色的頂點外的其他頂點繼續(xù)進行顏色標定，得到另外的顏色集合C；

4）重復3）的步驟，直到G中的所有頂點都標定完畢且顏色數(shù)最少 ；

5）將每種顏色集合C作為一個極大獨立集輸出。

2.3 實例求解

根據(jù)圖1的線纜交叉拓撲圖，表1的 線纜交叉表為基礎，進行求解分析。

Mi,i=1,2,3為計算節(jié)點，Nj,j=1,2,3為網(wǎng)絡節(jié)點。Mi-Nj，i=1,2,3；j=1,2,3為Mi與Nj之間的連線。圖中每條邊（Mi-Nj）表示節(jié)點間的每條線纜，此例中干線系統(tǒng)中總共有9條交叉線纜。為減少不必要的線纜交叉[6]，需要對圖2中的線纜進行分層設計，并且使設計出的分層數(shù)能夠盡可能的少，同時保證同一層的線纜不相互交叉。提取每條線纜作為平面圖中的節(jié)點，令（Mi-Nj）→（i,j）。將Mi與Nj之間的連線用頂點圖在平面上表示出來。

圖1 3×3的線纜交叉拓撲圖

圖2 頂點線纜交叉圖

○：表示Mi與Nj之間的連線。

Mi與Nj之間產(chǎn)生9條連線，圖2中用9個點表示出來，以相應數(shù)字標出。根據(jù)圖2，如果線纜之間有交叉，就在圖3中將兩個點用直線連接起來。至此，將線纜分層設計轉化為求解頂點線纜交叉圖的頂點分配問題。對于求出的頂點集合，各個頂點之間不存在互連，將這樣的一個頂點集合設置為一層，屬于這個集合的頂點的線纜布在這一層中，這樣線纜之間就不存在了交叉問題。理論上直接將9個頂點分為9個集合，將9條線纜布在9層中，這樣就消除了線纜交叉問題，但是在實際中這是不可能實現(xiàn)的，這會造成巨大的工程材料浪費，維護更加困難，不符合工程預算。對此對圖3利用最優(yōu)化的頂點著色方法，對頂點進行著色選取，首先對一個頂點vi進行著色，在剩下的頂點中尋找和vi不相交的頂點，將這些頂點標成同一種顏色。以此循環(huán)進行標定，直到無頂點再進行標定為止。同種顏色集合的頂點，作為一個獨立集輸出。如圖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)}放置在第三層。由此解決了干線布線系統(tǒng)線纜交叉的問題。

3 結論

此算法從工程中的線纜交叉問題出發(fā)，通過所設計的布線算法使得線纜布線得到優(yōu)化，易于管理，節(jié)省了工程預算，對節(jié)點較多的大型網(wǎng)絡布線具有明顯的優(yōu)化效果。通過在工程中檢驗，此算法具有很好的有效性和正確性。

[1]殷劍宏，吳開亞.圖論及其算法[M].合肥：中國科學技術大學出版社，2004：65-99.

[2]運籌學教材編寫組.運籌學[M].北京：清華大學出版社，2001：320-356.

[3]陳志平，徐宗本.計算機數(shù)學[M].北京：科學出版社，2001：53-59.

[4]徐俊明.圖論及其應用[M].合肥：中國科學技術出版社，2004：45-87.

[5]吳彤.復雜網(wǎng)絡研究及其意義[J].北京：哲學研究，2004，8(1):58-70.

[6]王海軍.大型科技會議議程安排問題[D].政學者論文集北京大學，2001：42-50.