基于路徑搜索算法的通信業(yè)務(wù)優(yōu)化研究

陳郁喬

【摘要】 隨著光纖逐步成為傳輸業(yè)務(wù)的主要載體，越來越多的接入業(yè)務(wù)基于光路通道開放，由于通信網(wǎng)絡(luò)資源有限，業(yè)務(wù)擴(kuò)張帶來的壓力與日俱增，如何通過有效的方法，對現(xiàn)網(wǎng)業(yè)務(wù)進(jìn)行調(diào)整優(yōu)化，實現(xiàn)更好的市場效應(yīng)，成為通信維護(hù)管理工作的一大挑戰(zhàn)。本文嘗試引入路徑搜索算法，對主干業(yè)務(wù)系統(tǒng)進(jìn)行路徑分析和優(yōu)化，找到基于資源現(xiàn)狀且面向業(yè)務(wù)最優(yōu)分配的調(diào)度方案，在完成業(yè)務(wù)需求的同時，實現(xiàn)最佳的資源配置，并在現(xiàn)網(wǎng)中實踐應(yīng)用。

【關(guān)鍵詞】 路徑搜索 通信資源 業(yè)務(wù)優(yōu)化

一、引言

在日常資源調(diào)度中，由于現(xiàn)網(wǎng)業(yè)務(wù)的緊迫性，需要及時根據(jù)資源情況調(diào)配業(yè)務(wù)需求。前期的調(diào)配本著快速完工形成市場效益，在資源分配上并非最優(yōu)，甚至?xí)共糠制瑓^(qū)資源呈現(xiàn)不合理的緊缺。隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大和建設(shè)拓展，維護(hù)管理中亟需對業(yè)務(wù)合理優(yōu)化，釋放緊缺資源，優(yōu)化網(wǎng)絡(luò)架構(gòu)。

隨著數(shù)年來資源數(shù)據(jù)信息化的建設(shè)，已經(jīng)實現(xiàn)了資源數(shù)據(jù)的平臺化。在實際分配過程中，不同的需求部門對業(yè)務(wù)分配方式有各自的側(cè)重關(guān)注點，如市場部門關(guān)注業(yè)務(wù)覆蓋范圍，即資源的可達(dá)性；網(wǎng)絡(luò)線條關(guān)注資源的提供和承載能力；業(yè)務(wù)維護(hù)部門關(guān)注開通和維護(hù)的便利性；建設(shè)部門關(guān)注建設(shè)和當(dāng)前需求的均衡性等。此外，還有業(yè)務(wù)的穩(wěn)定性、后期的擴(kuò)容性等等。

基于這種全局化的資源分配需求，以及對后續(xù)拓展進(jìn)行網(wǎng)絡(luò)優(yōu)化工作的探索，必須有能夠兼顧各方面需求的算法來進(jìn)行資源調(diào)配，本文將針對線路資源數(shù)據(jù)的特點，采用搜索規(guī)劃的算法解決優(yōu)化問題。這種算法能夠就對一定規(guī)模的網(wǎng)絡(luò)節(jié)點和線段進(jìn)行分析，尋求具備合理性的最佳業(yè)務(wù)路線。

二、業(yè)務(wù)模型概述

當(dāng)前網(wǎng)絡(luò)基本建立在劃分城區(qū)而成的網(wǎng)格上，每個規(guī)劃的網(wǎng)格中都存在相應(yīng)的業(yè)務(wù)側(cè)設(shè)備，并通過中繼段連通至接入側(cè)設(shè)備。為了便于簡化模型，假定在一個較小的片區(qū)中進(jìn)行傳輸業(yè)務(wù)規(guī)劃，在整個業(yè)務(wù)的流向中，數(shù)據(jù)從源端設(shè)備到宿端設(shè)備所經(jīng)過的承載載體進(jìn)行遍歷，不難發(fā)現(xiàn)業(yè)務(wù)的走向是經(jīng)由“始端設(shè)備→交接設(shè)施→中繼段→交接設(shè)施→…→交接設(shè)施→中繼段→末端設(shè)備”這種點線交替的形式。剔除首末端固定的設(shè)備，該路徑是由“點-線”間插交替的路徑模型。

針對該業(yè)務(wù)模型，可定義擬定優(yōu)化方向的判定標(biāo)準(zhǔn)：①總體和當(dāng)前業(yè)務(wù)覆蓋能力，②交接設(shè)施成端的比率，③局向纖芯使用率。

為簡化模型計算的呈現(xiàn)，對運算變量統(tǒng)一標(biāo)識，表述基礎(chǔ)數(shù)據(jù)如下：

交接設(shè)施點集（m為總節(jié)點數(shù)）：S={S1，S2，S3，…，Sm}

中繼段集（n為總線段數(shù)）：L={L1，L2，L3，…，Ln}

中繼段長度集：Len={Len1，Len2，Len3，…，Lenn}

中繼段纖芯占用率：Ф={Ф1，Ф2，Ф3，…，Фn}

中繼段纖芯數(shù)：n={n1，n2，n3，…，nn}

vik代表規(guī)劃路徑所經(jīng)交接設(shè)施，第i條可達(dá)路徑的第k個跳接點。有vik∈S。

lik代表規(guī)劃路徑經(jīng)中繼線段，第i條可達(dá)路徑的第k條線段。有l(wèi)ik∈L。

lenik代表第i條可達(dá)路徑的第k條線段的長度，有l(wèi)enik∈Len。

所有規(guī)劃出的路徑集合（Trace Route）：

TRi= （1）

如上，則第i條可達(dá)業(yè)務(wù)路徑的跳接次數(shù)為Ni，vi0=v0，viNi+1=vd。

假定某次業(yè)務(wù)優(yōu)化路徑數(shù)量為，全程功率損耗為λi dB，單位線長的損耗為λadB，跳接點的熔接損耗為λbdB，全程可供的最大損耗為λT，則可以得出每條規(guī)劃路徑的全程損耗為：

λi=∑Leni ×λa +Ni ×λb≤λT （2）

對于第i條規(guī)劃業(yè)務(wù)路徑自至的跳接次數(shù)Ni，假定有序集合TRi中的元素個數(shù)為Ri（Ri=CardiTRi），則：

Ni=（Ri-1）/2-1 （3）

在整個業(yè)務(wù)路徑規(guī)劃中，路徑損耗是業(yè)務(wù)開通的關(guān)鍵因素，路徑損耗必須在業(yè)務(wù)要求的功率范圍內(nèi)滿足，且取最小。損耗主要包括光路中的單位損耗和跳接點的接續(xù)損耗。而跳接點的數(shù)量也會在現(xiàn)場布線操作時產(chǎn)生人工消耗和業(yè)務(wù)不穩(wěn)定因素，所以確定路徑規(guī)劃的兩個基本約束條件為：a. 損耗最小，b. 跳接點最少。

由此，該模型可轉(zhuǎn)變?yōu)椋涸谟邢薜奶哟螖?shù)以內(nèi)，使得功率損耗最小的路徑，即目標(biāo)函數(shù)為：

MINTRi U（Ni，λi）≤λT （4）

其中U（Ni，λi）為以目標(biāo)優(yōu)先的二元目標(biāo)函數(shù)集，也就是說在滿足最少跳接次數(shù)Ni的前提下使得λi可控且最優(yōu)的方案集合。

從函數(shù)的性質(zhì)上看，應(yīng)該有 U/ Ni>0， U/ λi>0。從目標(biāo)優(yōu)先的次序看，有 U/ Ni>> U/ λi。

規(guī)劃路徑的節(jié)點集：

PA={P1，P2，P3，…，PNi} （5）

規(guī)劃路徑的線路集：

QA={Q1，Q2，Q3，…，QNi+1} （6）

路徑損耗：

n'

根據(jù)上述推演，求解式（1）-（7）所形成基本約束條件。

三、算法求解思路

根據(jù)上述算法，擬定求解思路如下：

（1）根據(jù)業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋該業(yè)務(wù)范圍的業(yè)務(wù)設(shè)施位置，擬定為通路起點P1，確認(rèn)設(shè)施P1的業(yè)務(wù)提供能力；（2）從所選擇業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋范圍內(nèi)是否含有末梢光交接設(shè)施，得出最近直線距離內(nèi)交接設(shè)施點坐標(biāo)，擬為路徑終點PNi；（3）分別從P1、PNi點出發(fā)，對比各中繼段所能到達(dá)的交接設(shè)施，追溯由P1至PNi的可達(dá)路徑，通過比較跳接次數(shù)和全程功率損耗來確定最優(yōu)路徑；（4）從搜索算法來看，需設(shè)定多個路線集和點集，運算量會隨網(wǎng)絡(luò)規(guī)模和跳接次數(shù)的增加成級數(shù)增長，為節(jié)約算法復(fù)雜度和計算成本，需考慮限定措施。

具體算法設(shè)計如下：

A. 先將起始點作為P1，假定P1到目標(biāo)點PNi存在直通通路（直通纜段），則直接得出最優(yōu)路徑；

B. 當(dāng)直通纜段不存在時，匹配經(jīng)過節(jié)點P1的所有線路{QP1}和經(jīng)過節(jié)點PNi的所有線路{QPNi}，確認(rèn)是否存在公共節(jié)點P2，若存在，則P1-P2-PNi為所求通路路徑；

C. 當(dāng){QP1}和{QPNi}中不存在公共節(jié)點P2時，將問題轉(zhuǎn)換為節(jié)點P2和節(jié)點PNi之間是否存在公共節(jié)點P3的問題求解，以確定P1-P2-P3-PNi的通路路徑；

D. 以此類推，考慮N次跳接的情況，逐步追溯得出結(jié)果；

E. 同步考慮功率損耗，當(dāng)最短路徑已超出光功率限額范圍時，自動退出搜索并返回；

F. 當(dāng)結(jié)果TRi存在多個時，通過對比各個結(jié)果的λi選擇最優(yōu)的業(yè)務(wù)規(guī)劃路徑。

不難看出，對業(yè)務(wù)優(yōu)化的模型可以轉(zhuǎn)換為對點線模型路徑規(guī)劃的算法演繹。受到路徑規(guī)劃算法復(fù)雜度的限制，算法的計算成本隨著網(wǎng)絡(luò)規(guī)模增長而加大，在本文應(yīng)用的模型中，過多的跳接點會帶來額外的路徑損耗，而路徑損耗是業(yè)務(wù)規(guī)劃模型的基本約束條件，常規(guī)場景下，布線跳接次數(shù)應(yīng)有限限定，因此，在算法中也可通過減少或限定計算的跳接次數(shù)（如NiMax≤5），使算法的計算成本基本可控。

四、結(jié)論

經(jīng)測試算法內(nèi)容通過輸入測試數(shù)據(jù)圓滿實現(xiàn)業(yè)務(wù)優(yōu)化?；谧詣踊惴ǖ哪M資源調(diào)配方案，可用于現(xiàn)網(wǎng)有限資源的調(diào)整，為新增業(yè)務(wù)騰出空間，同時也可推廣應(yīng)用到基于現(xiàn)網(wǎng)資源基礎(chǔ)的工程預(yù)設(shè)計中，從方案初期就介入方案合理性，減少后期因資源優(yōu)化帶來的業(yè)務(wù)中斷影響客戶感知。

【摘要】 隨著光纖逐步成為傳輸業(yè)務(wù)的主要載體，越來越多的接入業(yè)務(wù)基于光路通道開放，由于通信網(wǎng)絡(luò)資源有限，業(yè)務(wù)擴(kuò)張帶來的壓力與日俱增，如何通過有效的方法，對現(xiàn)網(wǎng)業(yè)務(wù)進(jìn)行調(diào)整優(yōu)化，實現(xiàn)更好的市場效應(yīng)，成為通信維護(hù)管理工作的一大挑戰(zhàn)。本文嘗試引入路徑搜索算法，對主干業(yè)務(wù)系統(tǒng)進(jìn)行路徑分析和優(yōu)化，找到基于資源現(xiàn)狀且面向業(yè)務(wù)最優(yōu)分配的調(diào)度方案，在完成業(yè)務(wù)需求的同時，實現(xiàn)最佳的資源配置，并在現(xiàn)網(wǎng)中實踐應(yīng)用。

【關(guān)鍵詞】 路徑搜索 通信資源 業(yè)務(wù)優(yōu)化

一、引言

在日常資源調(diào)度中，由于現(xiàn)網(wǎng)業(yè)務(wù)的緊迫性，需要及時根據(jù)資源情況調(diào)配業(yè)務(wù)需求。前期的調(diào)配本著快速完工形成市場效益，在資源分配上并非最優(yōu)，甚至?xí)共糠制瑓^(qū)資源呈現(xiàn)不合理的緊缺。隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大和建設(shè)拓展，維護(hù)管理中亟需對業(yè)務(wù)合理優(yōu)化，釋放緊缺資源，優(yōu)化網(wǎng)絡(luò)架構(gòu)。

隨著數(shù)年來資源數(shù)據(jù)信息化的建設(shè)，已經(jīng)實現(xiàn)了資源數(shù)據(jù)的平臺化。在實際分配過程中，不同的需求部門對業(yè)務(wù)分配方式有各自的側(cè)重關(guān)注點，如市場部門關(guān)注業(yè)務(wù)覆蓋范圍，即資源的可達(dá)性；網(wǎng)絡(luò)線條關(guān)注資源的提供和承載能力；業(yè)務(wù)維護(hù)部門關(guān)注開通和維護(hù)的便利性；建設(shè)部門關(guān)注建設(shè)和當(dāng)前需求的均衡性等。此外，還有業(yè)務(wù)的穩(wěn)定性、后期的擴(kuò)容性等等。

基于這種全局化的資源分配需求，以及對后續(xù)拓展進(jìn)行網(wǎng)絡(luò)優(yōu)化工作的探索，必須有能夠兼顧各方面需求的算法來進(jìn)行資源調(diào)配，本文將針對線路資源數(shù)據(jù)的特點，采用搜索規(guī)劃的算法解決優(yōu)化問題。這種算法能夠就對一定規(guī)模的網(wǎng)絡(luò)節(jié)點和線段進(jìn)行分析，尋求具備合理性的最佳業(yè)務(wù)路線。

二、業(yè)務(wù)模型概述

當(dāng)前網(wǎng)絡(luò)基本建立在劃分城區(qū)而成的網(wǎng)格上，每個規(guī)劃的網(wǎng)格中都存在相應(yīng)的業(yè)務(wù)側(cè)設(shè)備，并通過中繼段連通至接入側(cè)設(shè)備。為了便于簡化模型，假定在一個較小的片區(qū)中進(jìn)行傳輸業(yè)務(wù)規(guī)劃，在整個業(yè)務(wù)的流向中，數(shù)據(jù)從源端設(shè)備到宿端設(shè)備所經(jīng)過的承載載體進(jìn)行遍歷，不難發(fā)現(xiàn)業(yè)務(wù)的走向是經(jīng)由“始端設(shè)備→交接設(shè)施→中繼段→交接設(shè)施→…→交接設(shè)施→中繼段→末端設(shè)備”這種點線交替的形式。剔除首末端固定的設(shè)備，該路徑是由“點-線”間插交替的路徑模型。

針對該業(yè)務(wù)模型，可定義擬定優(yōu)化方向的判定標(biāo)準(zhǔn)：①總體和當(dāng)前業(yè)務(wù)覆蓋能力，②交接設(shè)施成端的比率，③局向纖芯使用率。

為簡化模型計算的呈現(xiàn)，對運算變量統(tǒng)一標(biāo)識，表述基礎(chǔ)數(shù)據(jù)如下：

交接設(shè)施點集（m為總節(jié)點數(shù)）：S={S1，S2，S3，…，Sm}

中繼段集（n為總線段數(shù)）：L={L1，L2，L3，…，Ln}

中繼段長度集：Len={Len1，Len2，Len3，…，Lenn}

中繼段纖芯占用率：Ф={Ф1，Ф2，Ф3，…，Фn}

中繼段纖芯數(shù)：n={n1，n2，n3，…，nn}

vik代表規(guī)劃路徑所經(jīng)交接設(shè)施，第i條可達(dá)路徑的第k個跳接點。有vik∈S。

lik代表規(guī)劃路徑經(jīng)中繼線段，第i條可達(dá)路徑的第k條線段。有l(wèi)ik∈L。

lenik代表第i條可達(dá)路徑的第k條線段的長度，有l(wèi)enik∈Len。

所有規(guī)劃出的路徑集合（Trace Route）：

TRi= （1）

如上，則第i條可達(dá)業(yè)務(wù)路徑的跳接次數(shù)為Ni，vi0=v0，viNi+1=vd。

假定某次業(yè)務(wù)優(yōu)化路徑數(shù)量為，全程功率損耗為λi dB，單位線長的損耗為λadB，跳接點的熔接損耗為λbdB，全程可供的最大損耗為λT，則可以得出每條規(guī)劃路徑的全程損耗為：

λi=∑Leni ×λa +Ni ×λb≤λT （2）

對于第i條規(guī)劃業(yè)務(wù)路徑自至的跳接次數(shù)Ni，假定有序集合TRi中的元素個數(shù)為Ri（Ri=CardiTRi），則：

Ni=（Ri-1）/2-1 （3）

在整個業(yè)務(wù)路徑規(guī)劃中，路徑損耗是業(yè)務(wù)開通的關(guān)鍵因素，路徑損耗必須在業(yè)務(wù)要求的功率范圍內(nèi)滿足，且取最小。損耗主要包括光路中的單位損耗和跳接點的接續(xù)損耗。而跳接點的數(shù)量也會在現(xiàn)場布線操作時產(chǎn)生人工消耗和業(yè)務(wù)不穩(wěn)定因素，所以確定路徑規(guī)劃的兩個基本約束條件為：a. 損耗最小，b. 跳接點最少。

由此，該模型可轉(zhuǎn)變?yōu)椋涸谟邢薜奶哟螖?shù)以內(nèi)，使得功率損耗最小的路徑，即目標(biāo)函數(shù)為：

MINTRi U（Ni，λi）≤λT （4）

其中U（Ni，λi）為以目標(biāo)優(yōu)先的二元目標(biāo)函數(shù)集，也就是說在滿足最少跳接次數(shù)Ni的前提下使得λi可控且最優(yōu)的方案集合。

從函數(shù)的性質(zhì)上看，應(yīng)該有 U/ Ni>0， U/ λi>0。從目標(biāo)優(yōu)先的次序看，有 U/ Ni>> U/ λi。

規(guī)劃路徑的節(jié)點集：

PA={P1，P2，P3，…，PNi} （5）

規(guī)劃路徑的線路集：

QA={Q1，Q2，Q3，…，QNi+1} （6）

路徑損耗：

n'

根據(jù)上述推演，求解式（1）-（7）所形成基本約束條件。

三、算法求解思路

根據(jù)上述算法，擬定求解思路如下：

（1）根據(jù)業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋該業(yè)務(wù)范圍的業(yè)務(wù)設(shè)施位置，擬定為通路起點P1，確認(rèn)設(shè)施P1的業(yè)務(wù)提供能力；（2）從所選擇業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋范圍內(nèi)是否含有末梢光交接設(shè)施，得出最近直線距離內(nèi)交接設(shè)施點坐標(biāo)，擬為路徑終點PNi；（3）分別從P1、PNi點出發(fā)，對比各中繼段所能到達(dá)的交接設(shè)施，追溯由P1至PNi的可達(dá)路徑，通過比較跳接次數(shù)和全程功率損耗來確定最優(yōu)路徑；（4）從搜索算法來看，需設(shè)定多個路線集和點集，運算量會隨網(wǎng)絡(luò)規(guī)模和跳接次數(shù)的增加成級數(shù)增長，為節(jié)約算法復(fù)雜度和計算成本，需考慮限定措施。

具體算法設(shè)計如下：

A. 先將起始點作為P1，假定P1到目標(biāo)點PNi存在直通通路（直通纜段），則直接得出最優(yōu)路徑；

B. 當(dāng)直通纜段不存在時，匹配經(jīng)過節(jié)點P1的所有線路{QP1}和經(jīng)過節(jié)點PNi的所有線路{QPNi}，確認(rèn)是否存在公共節(jié)點P2，若存在，則P1-P2-PNi為所求通路路徑；

C. 當(dāng){QP1}和{QPNi}中不存在公共節(jié)點P2時，將問題轉(zhuǎn)換為節(jié)點P2和節(jié)點PNi之間是否存在公共節(jié)點P3的問題求解，以確定P1-P2-P3-PNi的通路路徑；

D. 以此類推，考慮N次跳接的情況，逐步追溯得出結(jié)果；

E. 同步考慮功率損耗，當(dāng)最短路徑已超出光功率限額范圍時，自動退出搜索并返回；

F. 當(dāng)結(jié)果TRi存在多個時，通過對比各個結(jié)果的λi選擇最優(yōu)的業(yè)務(wù)規(guī)劃路徑。

不難看出，對業(yè)務(wù)優(yōu)化的模型可以轉(zhuǎn)換為對點線模型路徑規(guī)劃的算法演繹。受到路徑規(guī)劃算法復(fù)雜度的限制，算法的計算成本隨著網(wǎng)絡(luò)規(guī)模增長而加大，在本文應(yīng)用的模型中，過多的跳接點會帶來額外的路徑損耗，而路徑損耗是業(yè)務(wù)規(guī)劃模型的基本約束條件，常規(guī)場景下，布線跳接次數(shù)應(yīng)有限限定，因此，在算法中也可通過減少或限定計算的跳接次數(shù)（如NiMax≤5），使算法的計算成本基本可控。

四、結(jié)論

經(jīng)測試算法內(nèi)容通過輸入測試數(shù)據(jù)圓滿實現(xiàn)業(yè)務(wù)優(yōu)化。基于自動化算法的模擬資源調(diào)配方案，可用于現(xiàn)網(wǎng)有限資源的調(diào)整，為新增業(yè)務(wù)騰出空間，同時也可推廣應(yīng)用到基于現(xiàn)網(wǎng)資源基礎(chǔ)的工程預(yù)設(shè)計中，從方案初期就介入方案合理性，減少后期因資源優(yōu)化帶來的業(yè)務(wù)中斷影響客戶感知。

【摘要】 隨著光纖逐步成為傳輸業(yè)務(wù)的主要載體，越來越多的接入業(yè)務(wù)基于光路通道開放，由于通信網(wǎng)絡(luò)資源有限，業(yè)務(wù)擴(kuò)張帶來的壓力與日俱增，如何通過有效的方法，對現(xiàn)網(wǎng)業(yè)務(wù)進(jìn)行調(diào)整優(yōu)化，實現(xiàn)更好的市場效應(yīng)，成為通信維護(hù)管理工作的一大挑戰(zhàn)。本文嘗試引入路徑搜索算法，對主干業(yè)務(wù)系統(tǒng)進(jìn)行路徑分析和優(yōu)化，找到基于資源現(xiàn)狀且面向業(yè)務(wù)最優(yōu)分配的調(diào)度方案，在完成業(yè)務(wù)需求的同時，實現(xiàn)最佳的資源配置，并在現(xiàn)網(wǎng)中實踐應(yīng)用。

【關(guān)鍵詞】 路徑搜索 通信資源 業(yè)務(wù)優(yōu)化

一、引言

在日常資源調(diào)度中，由于現(xiàn)網(wǎng)業(yè)務(wù)的緊迫性，需要及時根據(jù)資源情況調(diào)配業(yè)務(wù)需求。前期的調(diào)配本著快速完工形成市場效益，在資源分配上并非最優(yōu)，甚至?xí)共糠制瑓^(qū)資源呈現(xiàn)不合理的緊缺。隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大和建設(shè)拓展，維護(hù)管理中亟需對業(yè)務(wù)合理優(yōu)化，釋放緊缺資源，優(yōu)化網(wǎng)絡(luò)架構(gòu)。

隨著數(shù)年來資源數(shù)據(jù)信息化的建設(shè)，已經(jīng)實現(xiàn)了資源數(shù)據(jù)的平臺化。在實際分配過程中，不同的需求部門對業(yè)務(wù)分配方式有各自的側(cè)重關(guān)注點，如市場部門關(guān)注業(yè)務(wù)覆蓋范圍，即資源的可達(dá)性；網(wǎng)絡(luò)線條關(guān)注資源的提供和承載能力；業(yè)務(wù)維護(hù)部門關(guān)注開通和維護(hù)的便利性；建設(shè)部門關(guān)注建設(shè)和當(dāng)前需求的均衡性等。此外，還有業(yè)務(wù)的穩(wěn)定性、后期的擴(kuò)容性等等。

基于這種全局化的資源分配需求，以及對后續(xù)拓展進(jìn)行網(wǎng)絡(luò)優(yōu)化工作的探索，必須有能夠兼顧各方面需求的算法來進(jìn)行資源調(diào)配，本文將針對線路資源數(shù)據(jù)的特點，采用搜索規(guī)劃的算法解決優(yōu)化問題。這種算法能夠就對一定規(guī)模的網(wǎng)絡(luò)節(jié)點和線段進(jìn)行分析，尋求具備合理性的最佳業(yè)務(wù)路線。

二、業(yè)務(wù)模型概述

當(dāng)前網(wǎng)絡(luò)基本建立在劃分城區(qū)而成的網(wǎng)格上，每個規(guī)劃的網(wǎng)格中都存在相應(yīng)的業(yè)務(wù)側(cè)設(shè)備，并通過中繼段連通至接入側(cè)設(shè)備。為了便于簡化模型，假定在一個較小的片區(qū)中進(jìn)行傳輸業(yè)務(wù)規(guī)劃，在整個業(yè)務(wù)的流向中，數(shù)據(jù)從源端設(shè)備到宿端設(shè)備所經(jīng)過的承載載體進(jìn)行遍歷，不難發(fā)現(xiàn)業(yè)務(wù)的走向是經(jīng)由“始端設(shè)備→交接設(shè)施→中繼段→交接設(shè)施→…→交接設(shè)施→中繼段→末端設(shè)備”這種點線交替的形式。剔除首末端固定的設(shè)備，該路徑是由“點-線”間插交替的路徑模型。

針對該業(yè)務(wù)模型，可定義擬定優(yōu)化方向的判定標(biāo)準(zhǔn)：①總體和當(dāng)前業(yè)務(wù)覆蓋能力，②交接設(shè)施成端的比率，③局向纖芯使用率。

為簡化模型計算的呈現(xiàn)，對運算變量統(tǒng)一標(biāo)識，表述基礎(chǔ)數(shù)據(jù)如下：

交接設(shè)施點集（m為總節(jié)點數(shù)）：S={S1，S2，S3，…，Sm}

中繼段集（n為總線段數(shù)）：L={L1，L2，L3，…，Ln}

中繼段長度集：Len={Len1，Len2，Len3，…，Lenn}

中繼段纖芯占用率：Ф={Ф1，Ф2，Ф3，…，Фn}

中繼段纖芯數(shù)：n={n1，n2，n3，…，nn}

vik代表規(guī)劃路徑所經(jīng)交接設(shè)施，第i條可達(dá)路徑的第k個跳接點。有vik∈S。

lik代表規(guī)劃路徑經(jīng)中繼線段，第i條可達(dá)路徑的第k條線段。有l(wèi)ik∈L。

lenik代表第i條可達(dá)路徑的第k條線段的長度，有l(wèi)enik∈Len。

所有規(guī)劃出的路徑集合（Trace Route）：

TRi= （1）

如上，則第i條可達(dá)業(yè)務(wù)路徑的跳接次數(shù)為Ni，vi0=v0，viNi+1=vd。

假定某次業(yè)務(wù)優(yōu)化路徑數(shù)量為，全程功率損耗為λi dB，單位線長的損耗為λadB，跳接點的熔接損耗為λbdB，全程可供的最大損耗為λT，則可以得出每條規(guī)劃路徑的全程損耗為：

λi=∑Leni ×λa +Ni ×λb≤λT （2）

對于第i條規(guī)劃業(yè)務(wù)路徑自至的跳接次數(shù)Ni，假定有序集合TRi中的元素個數(shù)為Ri（Ri=CardiTRi），則：

Ni=（Ri-1）/2-1 （3）

在整個業(yè)務(wù)路徑規(guī)劃中，路徑損耗是業(yè)務(wù)開通的關(guān)鍵因素，路徑損耗必須在業(yè)務(wù)要求的功率范圍內(nèi)滿足，且取最小。損耗主要包括光路中的單位損耗和跳接點的接續(xù)損耗。而跳接點的數(shù)量也會在現(xiàn)場布線操作時產(chǎn)生人工消耗和業(yè)務(wù)不穩(wěn)定因素，所以確定路徑規(guī)劃的兩個基本約束條件為：a. 損耗最小，b. 跳接點最少。

由此，該模型可轉(zhuǎn)變?yōu)椋涸谟邢薜奶哟螖?shù)以內(nèi)，使得功率損耗最小的路徑，即目標(biāo)函數(shù)為：

MINTRi U（Ni，λi）≤λT （4）

其中U（Ni，λi）為以目標(biāo)優(yōu)先的二元目標(biāo)函數(shù)集，也就是說在滿足最少跳接次數(shù)Ni的前提下使得λi可控且最優(yōu)的方案集合。

從函數(shù)的性質(zhì)上看，應(yīng)該有 U/ Ni>0， U/ λi>0。從目標(biāo)優(yōu)先的次序看，有 U/ Ni>> U/ λi。

規(guī)劃路徑的節(jié)點集：

PA={P1，P2，P3，…，PNi} （5）

規(guī)劃路徑的線路集：

QA={Q1，Q2，Q3，…，QNi+1} （6）

路徑損耗：

n'

根據(jù)上述推演，求解式（1）-（7）所形成基本約束條件。

三、算法求解思路

根據(jù)上述算法，擬定求解思路如下：

（1）根據(jù)業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋該業(yè)務(wù)范圍的業(yè)務(wù)設(shè)施位置，擬定為通路起點P1，確認(rèn)設(shè)施P1的業(yè)務(wù)提供能力；（2）從所選擇業(yè)務(wù)點坐標(biāo)確認(rèn)覆蓋范圍內(nèi)是否含有末梢光交接設(shè)施，得出最近直線距離內(nèi)交接設(shè)施點坐標(biāo)，擬為路徑終點PNi；（3）分別從P1、PNi點出發(fā)，對比各中繼段所能到達(dá)的交接設(shè)施，追溯由P1至PNi的可達(dá)路徑，通過比較跳接次數(shù)和全程功率損耗來確定最優(yōu)路徑；（4）從搜索算法來看，需設(shè)定多個路線集和點集，運算量會隨網(wǎng)絡(luò)規(guī)模和跳接次數(shù)的增加成級數(shù)增長，為節(jié)約算法復(fù)雜度和計算成本，需考慮限定措施。

具體算法設(shè)計如下：

A. 先將起始點作為P1，假定P1到目標(biāo)點PNi存在直通通路（直通纜段），則直接得出最優(yōu)路徑；

B. 當(dāng)直通纜段不存在時，匹配經(jīng)過節(jié)點P1的所有線路{QP1}和經(jīng)過節(jié)點PNi的所有線路{QPNi}，確認(rèn)是否存在公共節(jié)點P2，若存在，則P1-P2-PNi為所求通路路徑；

C. 當(dāng){QP1}和{QPNi}中不存在公共節(jié)點P2時，將問題轉(zhuǎn)換為節(jié)點P2和節(jié)點PNi之間是否存在公共節(jié)點P3的問題求解，以確定P1-P2-P3-PNi的通路路徑；

D. 以此類推，考慮N次跳接的情況，逐步追溯得出結(jié)果；

E. 同步考慮功率損耗，當(dāng)最短路徑已超出光功率限額范圍時，自動退出搜索并返回；

F. 當(dāng)結(jié)果TRi存在多個時，通過對比各個結(jié)果的λi選擇最優(yōu)的業(yè)務(wù)規(guī)劃路徑。

不難看出，對業(yè)務(wù)優(yōu)化的模型可以轉(zhuǎn)換為對點線模型路徑規(guī)劃的算法演繹。受到路徑規(guī)劃算法復(fù)雜度的限制，算法的計算成本隨著網(wǎng)絡(luò)規(guī)模增長而加大，在本文應(yīng)用的模型中，過多的跳接點會帶來額外的路徑損耗，而路徑損耗是業(yè)務(wù)規(guī)劃模型的基本約束條件，常規(guī)場景下，布線跳接次數(shù)應(yīng)有限限定，因此，在算法中也可通過減少或限定計算的跳接次數(shù)（如NiMax≤5），使算法的計算成本基本可控。

四、結(jié)論

經(jīng)測試算法內(nèi)容通過輸入測試數(shù)據(jù)圓滿實現(xiàn)業(yè)務(wù)優(yōu)化?；谧詣踊惴ǖ哪M資源調(diào)配方案，可用于現(xiàn)網(wǎng)有限資源的調(diào)整，為新增業(yè)務(wù)騰出空間，同時也可推廣應(yīng)用到基于現(xiàn)網(wǎng)資源基礎(chǔ)的工程預(yù)設(shè)計中，從方案初期就介入方案合理性，減少后期因資源優(yōu)化帶來的業(yè)務(wù)中斷影響客戶感知。