王 瓊，夏文云，馬曉亮

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

0 引言

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

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

本文借助數學模型的思想[2]，將傳輸網絡的拓撲優(yōu)化抽象為NP-Hard問題，并利用遺傳算法，使得在滿足覆蓋和安全的前提下，整體建網成本最低。

1 NP-hard模型

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

圖1 傳輸系統接入層網絡

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

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

2 遺傳算法

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

圖2 遺傳算法流程圖

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

首先，我們做一些基本處理：將所有1—N個點編號，起點為1號，終點為N號。計算各點兩兩間的相關度(即成本)，用一組數表示，若完全不相關，則取相對較大的數，或者正無窮。

其次，要產生一組樣本空間，步驟如下：

a) 生成一個樣本的數組，用于存放路徑以及每條路徑經過的點，數組為二維，行存放一條路徑經過的點的號碼，列存放不同路徑的信息。數組行數不大于N/MIN，列數不大于MAX。

b) 對于每條路徑經過點的個數限制，我們用在MIN(環(huán)路最小節(jié)點數，取1)到MAX(環(huán)路最大節(jié)點數，取8)之間產生一組隨機整數，以此作為每條路徑所經過點的數目。

c) 對路徑數以及每條路徑經過的點數進行約束，即需要滿足數組內的點包含所有N個點，當要求各點只能利用一次時，亦可以將數組調整為全部N個點的不重復隨機排列。

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

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

2) 評估適應度

接下來，對獲得的樣本空間進行個體評價，步驟如下：

a) 考慮基因適應度的計算。在本接入環(huán)問題中，由于目標是令總花費最少，所以每個樣本的路徑總長越長，與目標越遠，即兩者負相關。因此，我們可以取函數1/S作為樣本基因的適應度(S為樣本的路徑總長)。當然，還可以取其它類似的函數作為適應度，如當負相關程度較大時，可取1/S^2或者1/S^3等等，可按實際情況調整。

b) 評價每個基因，得到各自的適應度，并進行歸一化，即使所有基因適應度相加為1，各基因按比例調整。

3) 繁殖

然后進行遺傳算法中的關鍵操作，即對“基因庫”進行選擇、交叉、變異操作：

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

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

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

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

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

4) 下一代

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

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

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

3 數學建模

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

限定條件為：單個環(huán)網最大節(jié)點數小于8個且不能產生同纜環(huán)即同一環(huán)路拓撲中相同路徑不得經過2次。

已知條件為：管線費用成本(通過站點管線長度矩陣表確定)、設備費用成本(匯聚端口占用+基站接入設備)。

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

設nk為第k條路徑需要經過的離散點總數，用集合Rk{rki≤i≤nk}來對應第k條路徑要經過的離散點，其中rki表示第k條路徑要到達的第i個離散點。

rk0為第k條路徑的起始點。

目標函數：

使得滿足如下條件：

.

(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)

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

4 實例驗證

以某運營商片區(qū)現有站點分布為例，我們對此片區(qū)的拓撲進行優(yōu)化。

圖3 某運營商片區(qū)站點分布

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

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

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

圖4 程序計算結果

程序中總路程48表示總的費用成本花費4.8萬元，數字和基站點位對應情況如下：

程序值123456789101112基站編號OABCDEFGHXYZ

即程序輸出的最優(yōu)拓撲環(huán)路數量為3，拓撲路徑如下：

1) O-A-B-Y-Z

2) O-C-D-G-Z

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

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

圖5 拓撲最優(yōu)路線路

5 結束語

本文借助數學模型的思想，將電信通信網絡傳輸系統的拓撲優(yōu)化抽象為NP-Hard問題，并利用遺傳算法，使得在滿足網絡覆蓋和安全的前提下，整體建網成本最低。這為運營商實現低成本、高效率地進行傳輸拓撲優(yōu)化提供了一個合理的解決方案，在實際開發(fā)和應用中具有很高的借鑒和參考意義。