線纜布線優(yōu)化問題模型分析

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

0 引言

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

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

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

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

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

G（V,E）表示一個(gè)圖， V表示圖的頂點(diǎn)集合[5]， E表示點(diǎn)和點(diǎn)之間的連線集合，連線稱為邊；如果邊全都是有方向的，那么稱為有向圖，如果邊全都是沒有方向的，那么稱為無向圖。

給定無向圖G（V,E） 及顏色集合C 。圖的頂點(diǎn)k-著色為：用圖C中的顏色對圖G（V,E）的頂點(diǎn)著色[6]，使得每一個(gè)頂點(diǎn)著一種顏色 ，且相鄰的頂點(diǎn)顏色不同。這里 V = {v1, v2, v3,???,vn};E 是邊的集合 E = {e1, e2, e3,???,en};C是顏色的集合 C = {c1, c2, c3,???,cn};

極大獨(dú)立集：I是G的一個(gè)頂點(diǎn)子集，I中任兩個(gè)頂點(diǎn)不相鄰，則I是圖G的一個(gè)獨(dú)立集。若獨(dú)立集I中增加任一除I集外的頂點(diǎn)后I不再是獨(dú)立集，則I是極大獨(dú)立集。在所有極大獨(dú)立集中含頂點(diǎn)數(shù)最多的為極大獨(dú)立集，此時(shí)的頂點(diǎn)數(shù)稱為獨(dú)立數(shù)。

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

2.1 線纜交叉模型建立

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

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

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

2.2 算法步驟

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

2）將平面交叉圖轉(zhuǎn)化為頂點(diǎn)線纜交叉圖G'；

3）對頂點(diǎn)線纜交叉圖G'采用頂點(diǎn)著色法，對頂點(diǎn)進(jìn)行顏色標(biāo)定，得出一種顏色集合 C；

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

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

5）將每種顏色集合C作為一個(gè)極大獨(dú)立集輸出。

2.3 實(shí)例求解

根據(jù)圖1的線纜交叉拓?fù)鋱D，表1的 線纜交叉表為基礎(chǔ)，進(jìn)行求解分析。

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

圖1 3×3的線纜交叉拓?fù)鋱D

圖2 頂點(diǎn)線纜交叉圖

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

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

圖3 頂點(diǎn)著色圖

由圖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 結(jié)論

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

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

[2]運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2001：320-356.

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

[4]徐俊明.圖論及其應(yīng)用[M].合肥：中國科學(xué)技術(shù)出版社，2004：45-87.

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

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