王 瓊，夏文云，馬曉亮

(江蘇第二師范學(xué)院 物理與電子工程學(xué)院，江蘇 南京 210013)

0 引言

傳輸網(wǎng)絡(luò)一般采用核心-匯聚-接入的三層結(jié)構(gòu)，基于安全考慮，匯聚層面通常選擇兩個(gè)節(jié)點(diǎn)，接入層的其他宏基站采用雙歸的方式接入這兩個(gè)匯聚節(jié)點(diǎn)，從而形成傳輸環(huán)路，實(shí)現(xiàn)對(duì)末端節(jié)點(diǎn)的業(yè)務(wù)收斂。這就要求網(wǎng)絡(luò)拓?fù)涞膬?yōu)化必須在滿足遍歷所有節(jié)點(diǎn)的前提下，降低整體建網(wǎng)成本，即占用管線長(zhǎng)度和路由條數(shù)越小越好。這與著名的推銷(xiāo)員旅行問(wèn)題(Travel Saleman Problem or TSP)極其相似[1]，即要求推銷(xiāo)員遍歷既定的城市，而使得總的路費(fèi)開(kāi)銷(xiāo)最小。

傳統(tǒng)方法多以經(jīng)驗(yàn)為基礎(chǔ)，通過(guò)簡(jiǎn)單的計(jì)算完成網(wǎng)絡(luò)優(yōu)化，但是這往往會(huì)犧牲網(wǎng)絡(luò)的經(jīng)濟(jì)性。遺傳算法模擬自然進(jìn)化過(guò)程，是一種具有并行特征的搜索算法，利于對(duì)解空間進(jìn)行搜索，加快對(duì)解的搜索速度，便于推廣到多節(jié)點(diǎn)的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中，是解決大規(guī)模網(wǎng)絡(luò)優(yōu)化問(wèn)題的有效工具。

本文借助數(shù)學(xué)模型的思想[2]，將傳輸網(wǎng)絡(luò)的拓?fù)鋬?yōu)化抽象為NP-Hard問(wèn)題，并利用遺傳算法，使得在滿足覆蓋和安全的前提下，整體建網(wǎng)成本最低。

1 NP-hard模型

NP是指非確定性多項(xiàng)式(non-deterministic polynomial，縮寫(xiě)NP)。所謂的非確定性是指，可用一定數(shù)量的運(yùn)算去解決多項(xiàng)式時(shí)間內(nèi)可解決的問(wèn)題。傳輸網(wǎng)絡(luò)采用核心-匯聚-接入的三層結(jié)構(gòu)，其中，接入層最靠近末端節(jié)點(diǎn)，數(shù)量最多，結(jié)構(gòu)也最復(fù)雜。傳輸系統(tǒng)的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)與TSP問(wèn)題類似[3,4]，是一個(gè)改進(jìn)型的雙點(diǎn)NP-hard問(wèn)題，如圖1所示，如何能夠在滿足雙歸和環(huán)上最多節(jié)點(diǎn)限定的條件下，環(huán)路總成本最低。

圖1 傳輸系統(tǒng)接入層網(wǎng)絡(luò)

在傳輸系統(tǒng)接入層網(wǎng)絡(luò)中，每個(gè)匯聚子區(qū)內(nèi)有兩個(gè)匯聚節(jié)點(diǎn)，區(qū)域內(nèi)的所有宏基站均采用雙歸的方式接入。在已知任意兩個(gè)基站點(diǎn)之間的管線連接成本，以及限定每個(gè)接入環(huán)下掛宏站數(shù)量的條件下，要求整體建網(wǎng)成本最低，即管線成本和設(shè)備成本總和達(dá)到最低。圖1中從A到B規(guī)劃若干條路由遍歷所有基站點(diǎn)，要求滿足總成本最低，即管線長(zhǎng)度最短且路由條數(shù)最少。其中限定條件為單條路由下掛點(diǎn)有上限，同一條路由不可重復(fù)經(jīng)過(guò)同一段落。已知條件為任意兩個(gè)基站點(diǎn)之間的管線連接成本已知。對(duì)區(qū)域內(nèi)接入環(huán)結(jié)構(gòu)最優(yōu)的NP-hard問(wèn)題進(jìn)行數(shù)學(xué)建模，成為一個(gè)求函數(shù)最小值的優(yōu)化問(wèn)題。

本文通過(guò)對(duì)資管系統(tǒng)中的現(xiàn)網(wǎng)任意站點(diǎn)之間接入層光纜纖芯長(zhǎng)度進(jìn)行摸查，得到任意基站間的最短接入層纖芯長(zhǎng)度矩陣表。同時(shí)，根據(jù)無(wú)線專業(yè)的站點(diǎn)規(guī)劃選址庫(kù)，對(duì)待建站址進(jìn)行撒點(diǎn)，結(jié)合現(xiàn)有基站的分布確定任意基站間需要新建管線的新建光纜長(zhǎng)度矩陣表。設(shè)備成本主要受環(huán)路數(shù)量影響，環(huán)路數(shù)量越多，對(duì)匯聚設(shè)備的端口占用越多，設(shè)備成本越高。

2 遺傳算法

遺傳算法(Genetic Algorithm)[5-7]是一類借鑒生物界的進(jìn)化規(guī)律演化而來(lái)的隨機(jī)化搜索方法。由于遺傳算法采用隨機(jī)運(yùn)算，對(duì)搜索空間無(wú)特殊要求，無(wú)需求導(dǎo)，具有運(yùn)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，因此近年來(lái)有很快的發(fā)展，并在組合優(yōu)化、自適應(yīng)控制、機(jī)器學(xué)習(xí)等許多領(lǐng)域獲得應(yīng)用。遺傳算法流程如圖2所示。

圖2 遺傳算法流程圖

1) 建初始狀態(tài)

首先，我們做一些基本處理：將所有1—N個(gè)點(diǎn)編號(hào)，起點(diǎn)為1號(hào)，終點(diǎn)為N號(hào)。計(jì)算各點(diǎn)兩兩間的相關(guān)度(即成本)，用一組數(shù)表示，若完全不相關(guān)，則取相對(duì)較大的數(shù)，或者正無(wú)窮。

其次，要產(chǎn)生一組樣本空間，步驟如下：

a) 生成一個(gè)樣本的數(shù)組，用于存放路徑以及每條路徑經(jīng)過(guò)的點(diǎn)，數(shù)組為二維，行存放一條路徑經(jīng)過(guò)的點(diǎn)的號(hào)碼，列存放不同路徑的信息。數(shù)組行數(shù)不大于N/MIN，列數(shù)不大于MAX。

b) 對(duì)于每條路徑經(jīng)過(guò)點(diǎn)的個(gè)數(shù)限制，我們用在MIN(環(huán)路最小節(jié)點(diǎn)數(shù)，取1)到MAX(環(huán)路最大節(jié)點(diǎn)數(shù)，取8)之間產(chǎn)生一組隨機(jī)整數(shù)，以此作為每條路徑所經(jīng)過(guò)點(diǎn)的數(shù)目。

c) 對(duì)路徑數(shù)以及每條路徑經(jīng)過(guò)的點(diǎn)數(shù)進(jìn)行約束，即需要滿足數(shù)組內(nèi)的點(diǎn)包含所有N個(gè)點(diǎn)，當(dāng)要求各點(diǎn)只能利用一次時(shí)，亦可以將數(shù)組調(diào)整為全部N個(gè)點(diǎn)的不重復(fù)隨機(jī)排列。

d) 另設(shè)一份向量描述樣本的信息，即路徑的選擇與長(zhǎng)度等情況。

e) 以上可獲得一份樣本，重復(fù)a)-d)可得到一組樣本空間，其中要檢查避免各樣本的相似性過(guò)大，以求獲得較為全面的“基因庫(kù)”。需要注意，樣本空間中的樣本數(shù)量需要根據(jù)實(shí)際情況調(diào)節(jié)，當(dāng)問(wèn)題復(fù)雜度較低時(shí)，樣本數(shù)可取較少，當(dāng)問(wèn)題復(fù)雜度較高時(shí)需多取樣。

2) 評(píng)估適應(yīng)度

接下來(lái)，對(duì)獲得的樣本空間進(jìn)行個(gè)體評(píng)價(jià)，步驟如下：

a) 考慮基因適應(yīng)度的計(jì)算。在本接入環(huán)問(wèn)題中，由于目標(biāo)是令總花費(fèi)最少，所以每個(gè)樣本的路徑總長(zhǎng)越長(zhǎng)，與目標(biāo)越遠(yuǎn)，即兩者負(fù)相關(guān)。因此，我們可以取函數(shù)1/S作為樣本基因的適應(yīng)度(S為樣本的路徑總長(zhǎng))。當(dāng)然，還可以取其它類似的函數(shù)作為適應(yīng)度，如當(dāng)負(fù)相關(guān)程度較大時(shí)，可取1/S^2或者1/S^3等等，可按實(shí)際情況調(diào)整。

b) 評(píng)價(jià)每個(gè)基因，得到各自的適應(yīng)度，并進(jìn)行歸一化，即使所有基因適應(yīng)度相加為1，各基因按比例調(diào)整。

3) 繁殖

然后進(jìn)行遺傳算法中的關(guān)鍵操作，即對(duì)“基因庫(kù)”進(jìn)行選擇、交叉、變異操作：

a) 選擇。通過(guò)取隨機(jī)數(shù)模擬基因被選中的概率，根據(jù)隨機(jī)數(shù)落在樣本適應(yīng)度的空間位置判斷，顯然適應(yīng)度大的“優(yōu)秀”基因容易被選中，當(dāng)然“不優(yōu)秀”的基因也不會(huì)被完全放棄，這點(diǎn)十分重要。

b) 交叉。截取選中的基因的一部分，然后相互交換。在本接入環(huán)問(wèn)題中，即按一定概率原則交換兩個(gè)樣本中不同路徑中的一部分點(diǎn)的位置。優(yōu)秀的基因可能在交叉中誕生。

c) 進(jìn)行完交叉操作后需要重新約束每個(gè)樣本，使其滿足問(wèn)題條件。

d) 遺傳。對(duì)于一些相比之下“不優(yōu)秀”的基因，我們單獨(dú)隨機(jī)修改其中的數(shù)據(jù)，即路徑分配以及點(diǎn)的經(jīng)過(guò)順序。此項(xiàng)改動(dòng)可以較大，以達(dá)到“基因突變”的效果，使其有可能成為“優(yōu)秀”的基因。

e) 記錄a)- d)的數(shù)據(jù)，得到新一代的“基因庫(kù)”。

4) 下一代

最后，通過(guò)循環(huán)重復(fù)上述過(guò)程，使“基因庫(kù)”不斷更新并且遺傳，記錄每一代的最優(yōu)解信息。迭代終止的條件為以下兩種：

a) 認(rèn)為設(shè)置迭代次數(shù)，如可設(shè)置到達(dá)1000次時(shí)迭代終止，最后的解即視為最優(yōu)解。迭代次數(shù)的設(shè)置可視實(shí)際情況決定。

b) 觀察每一代的最優(yōu)解，當(dāng)在很長(zhǎng)一段時(shí)間內(nèi)解不再更新，即可認(rèn)為趨于穩(wěn)定，此時(shí)可輸出最優(yōu)解。

3 數(shù)學(xué)建模

已知有起點(diǎn)(匯聚點(diǎn)A)與終點(diǎn)(匯聚點(diǎn)B)兩個(gè)點(diǎn)，此外還分布著N個(gè)點(diǎn)(宏基站)，各點(diǎn)兩兩之間可能連通(有直達(dá)接入層光纜)，亦可能不連通(無(wú)直達(dá)接入層光纜)。要求由起點(diǎn)開(kāi)始經(jīng)過(guò)某些點(diǎn)到達(dá)終點(diǎn)，所經(jīng)過(guò)的點(diǎn)有數(shù)量限制(環(huán)路最小節(jié)點(diǎn)數(shù)設(shè)為MIN，環(huán)路最大節(jié)點(diǎn)數(shù)設(shè)為MAX)，路徑數(shù)無(wú)限制，但最終且必須遍歷每個(gè)點(diǎn)。通過(guò)結(jié)合遺傳算法最終求出最優(yōu)拓?fù)浣Y(jié)構(gòu)及建網(wǎng)總花費(fèi)[8,9]。

限定條件為：?jiǎn)蝹€(gè)環(huán)網(wǎng)最大節(jié)點(diǎn)數(shù)小于8個(gè)且不能產(chǎn)生同纜環(huán)即同一環(huán)路拓?fù)渲邢嗤窂讲坏媒?jīng)過(guò)2次。

已知條件為：管線費(fèi)用成本(通過(guò)站點(diǎn)管線長(zhǎng)度矩陣表確定)、設(shè)備費(fèi)用成本(匯聚端口占用+基站接入設(shè)備)。

設(shè)由起點(diǎn)出發(fā)分出K條路徑，K的值由算法動(dòng)態(tài)決定。每條路徑的初始載重為1，隨著深度搜索載重變?yōu)閔k(k=1,2,3……N)，每個(gè)點(diǎn)的權(quán)重di為(i=1,2,3……N)，N為離散點(diǎn)的個(gè)數(shù)。離散點(diǎn)i到離散點(diǎn)j之間的相關(guān)度為Cij。所有點(diǎn)的總集合設(shè)為{Q}。

設(shè)nk為第k條路徑需要經(jīng)過(guò)的離散點(diǎn)總數(shù)，用集合Rk{rki≤i≤nk}來(lái)對(duì)應(yīng)第k條路徑要經(jīng)過(guò)的離散點(diǎn)，其中rki表示第k條路徑要到達(dá)的第i個(gè)離散點(diǎn)。

rk0為第k條路徑的起始點(diǎn)。

目標(biāo)函數(shù)：

使得滿足如下條件：

.

(1)

(2)

MIN≤nk≤MAX(k=1,2,…,K).

(3)

Tkx(rkm,rkl)≠Tky(rkl,kkm),
Tkx,Tky∈Tk,x,y=1,2…,nk+1^x≠y.

(4)

上述表達(dá)式中：式(1)表示所有離散點(diǎn)都應(yīng)遍歷，但可重復(fù)使用；不等式(2)表示每條路徑的權(quán)重不超過(guò)路徑的載重；不等式(3)表示每條路徑經(jīng)過(guò)的離散點(diǎn)總和不大于最大要求點(diǎn)數(shù)，且不小于最小要求點(diǎn)數(shù)；式(4)表示每條路徑不走回頭路，也不兩次經(jīng)過(guò)相同的線段，即避免成同纜環(huán)。

4 實(shí)例驗(yàn)證

以某運(yùn)營(yíng)商片區(qū)現(xiàn)有站點(diǎn)分布為例，我們對(duì)此片區(qū)的拓?fù)溥M(jìn)行優(yōu)化。

圖3 某運(yùn)營(yíng)商片區(qū)站點(diǎn)分布

如圖3所示，該區(qū)域現(xiàn)有2個(gè)匯聚節(jié)點(diǎn)：分別定義為(O)和(Z)，周邊分布有10個(gè)現(xiàn)有機(jī)房，分別編號(hào)為基站(A)……(Y)。將現(xiàn)有的光纜長(zhǎng)度按照0.12元/纖芯公里進(jìn)行折算，得到各站點(diǎn)之間管線連接成本矩陣表。其中，99表示無(wú)現(xiàn)有直達(dá)光纜，需要新建(實(shí)際運(yùn)用中可考慮新建成本，按照1.5萬(wàn)元/公里*光纜長(zhǎng)度+需要新建管道長(zhǎng)度進(jìn)行折算，本例中為演示方便，統(tǒng)一按99考慮)。

表1 站點(diǎn)連接成本路由矩陣表(單位：千元)

本次設(shè)定單個(gè)接入環(huán)的環(huán)路節(jié)點(diǎn)數(shù)量上限為4，下限為1，建立數(shù)學(xué)模型后，利用遺傳算法求解。我們采用matlab進(jìn)行編程運(yùn)算，設(shè)定100次迭代計(jì)算之后，返回結(jié)果如圖4所示。

圖4 程序計(jì)算結(jié)果

程序中總路程48表示總的費(fèi)用成本花費(fèi)4.8萬(wàn)元，數(shù)字和基站點(diǎn)位對(duì)應(yīng)情況如下：

程序值123456789101112基站編號(hào)OABCDEFGHXYZ

即程序輸出的最優(yōu)拓?fù)洵h(huán)路數(shù)量為3，拓?fù)渎窂饺缦拢?/p>

1) O-A-B-Y-Z

2) O-C-D-G-Z

3) O-E-X-F-H-Z

最優(yōu)路線圖輸出如圖5所示。

圖5 拓?fù)渥顑?yōu)路線路

5 結(jié)束語(yǔ)

本文借助數(shù)學(xué)模型的思想，將電信通信網(wǎng)絡(luò)傳輸系統(tǒng)的拓?fù)鋬?yōu)化抽象為NP-Hard問(wèn)題，并利用遺傳算法，使得在滿足網(wǎng)絡(luò)覆蓋和安全的前提下，整體建網(wǎng)成本最低。這為運(yùn)營(yíng)商實(shí)現(xiàn)低成本、高效率地進(jìn)行傳輸拓?fù)鋬?yōu)化提供了一個(gè)合理的解決方案，在實(shí)際開(kāi)發(fā)和應(yīng)用中具有很高的借鑒和參考意義。