王 瓊,夏文云,馬曉亮
(江蘇第二師范學(xué)院 物理與電子工程學(xué)院,江蘇 南京 210013)
傳輸網(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ù)越小越好。這與著名的推銷員旅行問(wèn)題(Travel Saleman Problem or TSP)極其相似[1],即要求推銷員遍歷既定的城市,而使得總的路費(fèi)開(kāi)銷最小。
傳統(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)成本最低。
NP是指非確定性多項(xiàng)式(non-deterministic polynomial,縮寫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è)備成本越高。
遺傳算法(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)解。
已知有起點(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)。
以某運(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)路線路
本文借助數(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)用中具有很高的借鑒和參考意義。