線纜布線優化問題模型分析

魏傳佳武漢工業學院 數理科學系，湖北武漢 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)}放置在第三層。由此解決了干線布線系統線纜交叉的問題。

3 結論

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

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

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

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

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

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

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