譚紅君，解亞敏，劉業(yè)君

（1.四川工程職業(yè)技術(shù)學(xué)院，四川 德陽(yáng) 618000；2.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110819）

可生存光纖—無(wú)線融合寬帶接入網(wǎng)規(guī)劃方法

譚紅君1，解亞敏2，劉業(yè)君2

（1.四川工程職業(yè)技術(shù)學(xué)院，四川 德陽(yáng) 618000；2.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110819）

光纖—無(wú)線融合（fiber-wireless，F(xiàn)iWi）寬帶接入網(wǎng)的出現(xiàn)不僅為隨時(shí)隨地的靈活寬帶接入提供了新的技術(shù)參考，同時(shí)也為可生存寬帶接入網(wǎng)的低成本設(shè)計(jì)增加了研究契機(jī)。研究了可生存FiWi接入網(wǎng)的網(wǎng)絡(luò)規(guī)劃問(wèn)題，提出一種基于無(wú)線重路由保護(hù)的可生存網(wǎng)絡(luò)規(guī)劃方法。當(dāng)任意光纖鏈路斷裂時(shí)，失效的光網(wǎng)絡(luò)單元可通過(guò)無(wú)線重路由將業(yè)務(wù)轉(zhuǎn)移到其他可用的光網(wǎng)絡(luò)單元承載。重點(diǎn)解決了無(wú)線路由器部署、備份射頻接口配置及光網(wǎng)絡(luò)單元容量分配的聯(lián)合優(yōu)化問(wèn)題，目標(biāo)是通過(guò)最小化網(wǎng)絡(luò)部署成本實(shí)現(xiàn)業(yè)務(wù)的完全保護(hù)。采用整數(shù)線性規(guī)劃方法獲得了小規(guī)模網(wǎng)絡(luò)規(guī)劃問(wèn)題的最優(yōu)解，同時(shí)提出了適用于大規(guī)模網(wǎng)絡(luò)規(guī)劃問(wèn)題的啟發(fā)式算法。仿真結(jié)果證實(shí)了所提方法在降低網(wǎng)絡(luò)部署成本方面的有效性。

光纖—無(wú)線融合；可生存網(wǎng)絡(luò)規(guī)劃；無(wú)線重路由；網(wǎng)絡(luò)保護(hù)；備份資源

1 引言

近年來(lái)，全球范圍的地震、海嘯等自然災(zāi)害頻發(fā)，這加劇了網(wǎng)絡(luò)故障的潛在風(fēng)險(xiǎn)，同時(shí)也為網(wǎng)絡(luò)生存性建設(shè)提出更高要求。網(wǎng)絡(luò)故障不僅導(dǎo)致大量數(shù)據(jù)丟失和運(yùn)營(yíng)商的極大經(jīng)濟(jì)損失，更制約著災(zāi)難營(yíng)救效率，可生存接入網(wǎng)規(guī)劃已成為學(xué)術(shù)界和工業(yè)界共同關(guān)注的焦點(diǎn)［1，2］。

無(wú)源光網(wǎng)絡(luò)（passive optical network，PON）憑借其在帶寬容量及傳輸穩(wěn)定性方面的突出優(yōu)勢(shì)，已被業(yè)界公認(rèn)為下一代寬帶接入理想的候選技術(shù)之一。然而，PON的樹(shù)型拓?fù)浣Y(jié)構(gòu)缺乏自愈能力，易受網(wǎng)絡(luò)組件故障的影響。例如，當(dāng)光網(wǎng)絡(luò)單元 （optical network unit，ONU）與光線路終端（optical line terminal，OLT）之間的光纖鏈路發(fā)生斷裂時(shí)，相應(yīng)ONU上承載的全部業(yè)務(wù)將被中斷［1-3］。現(xiàn)有研究主要通過(guò)為工作光纖鏈路配置備份光纖鏈路的方法對(duì)PON進(jìn)行保護(hù)。一旦工作光纖鏈路出現(xiàn)故障，被中斷的業(yè)務(wù)可通過(guò)光開(kāi)關(guān)轉(zhuǎn)移到備份光纖鏈路上承載。備份光纖的方法雖然能為業(yè)務(wù)恢復(fù)提供有效的帶寬保證，但它要求大量額外的成本投入。尤其在風(fēng)險(xiǎn)分離部署場(chǎng)景中，工作光纖鏈路與備份光纖鏈路不能共享相同的光纜或光纖隧道，額外的基礎(chǔ)設(shè)施建設(shè)將進(jìn)一步加劇備份光纖部署的成本壓力。因此，成本效益問(wèn)題一直是運(yùn)營(yíng)商進(jìn)行可生存PON建設(shè)面臨的主要挑戰(zhàn)之一［4，5］。

光纖—無(wú)線（fiber-wireless，F(xiàn)iWi）融合寬帶接入網(wǎng)作為一種新興的寬帶接入技術(shù)，它集成了光纖網(wǎng)絡(luò)帶寬容量高、傳輸穩(wěn)定以及無(wú)線網(wǎng)絡(luò)接入靈活、部署成本低等優(yōu)勢(shì)［6，7］，已得到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。不僅如此，F(xiàn)iWi接入網(wǎng)的出現(xiàn)也為可生存寬帶接入網(wǎng)的低成本設(shè)計(jì)提供了新的技術(shù)參考。典型的FiWi接入網(wǎng)呈樹(shù)型—網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，由前端的無(wú)線網(wǎng)狀網(wǎng)（wireless mesh network，WMN）及后端的無(wú)源光網(wǎng)絡(luò)組成［8，9］。在這種結(jié)構(gòu)下，前端的無(wú)線子網(wǎng)能通過(guò)在不同ONU之間進(jìn)行業(yè)務(wù)重路由為后端的光纖子網(wǎng)提供保護(hù)。例如，當(dāng)任意光纖鏈路斷裂導(dǎo)致ONU與OLT之間連接中斷，失效的ONU可通過(guò)無(wú)線路徑將業(yè)務(wù)轉(zhuǎn)移到其他可用的ONU上承載。由于無(wú)線設(shè)備比光纖基礎(chǔ)設(shè)施更易于部署和維護(hù)，因此無(wú)線重路由保護(hù)方法能實(shí)現(xiàn)比傳統(tǒng)備份光纖保護(hù)方法更高的成本效益，尤其適用于業(yè)務(wù)規(guī)模稀疏、運(yùn)營(yíng)成本敏感的網(wǎng)絡(luò)區(qū)域。

本文研究了可生存FiWi接入網(wǎng)的低成本規(guī)劃問(wèn)題，針對(duì)FiWi接入網(wǎng)中典型的單分支光纖鏈路故障情況，提出了基于無(wú)線重路由保護(hù)的可生存網(wǎng)絡(luò)規(guī)劃方法，重點(diǎn)解決了無(wú)線路由器部署、備份射頻接口配置與備份ONU容量分配的聯(lián)合優(yōu)化問(wèn)題，目標(biāo)是通過(guò)最小化的網(wǎng)絡(luò)部署成本構(gòu)建工作ONU與備份ONU之間的無(wú)線備份路徑。本文利用整數(shù)線性規(guī)劃（integer linear programming，ILP）對(duì)優(yōu)化問(wèn)題進(jìn)行了規(guī)范的數(shù)學(xué)描述，并獲得小規(guī)模網(wǎng)絡(luò)規(guī)劃問(wèn)題的最優(yōu)解?？紤]到大規(guī)模網(wǎng)絡(luò)規(guī)劃問(wèn)題的ILP模型難于求解，本文同時(shí)提出高效的啟發(fā)式算法。

2 無(wú)線重路由保護(hù)方法概述

無(wú)線重路由保護(hù)方法的原理如圖1所示，首先為每個(gè)工作ONU分配至少一個(gè)備份ONU，每個(gè)備份ONU需要為其工作ONU預(yù)留剩余容量作為備份容量。然后，在無(wú)線前端有策略地部署無(wú)線路由器并配置備份射頻接口，確保每個(gè)工作ONU與其任意備份ONU之間至少存在一條可用的無(wú)線備份路徑。為保證業(yè)務(wù)切換到備份路徑上的QoS，無(wú)線備份路徑經(jīng)過(guò)的每個(gè)備份射頻接口應(yīng)當(dāng)為重路由的業(yè)務(wù)分配備份容量。一旦網(wǎng)絡(luò)遭遇分支光纖鏈路故障，失效ONU可通過(guò)無(wú)線備份路徑將受影響業(yè)務(wù)轉(zhuǎn)移到其備份ONU。備份ONU將通過(guò)預(yù)留的備份容量將來(lái)自工作ONU的業(yè)務(wù)上傳給OLT。因?yàn)閭浞萑萘咳∽杂趥浞軴NU和備份射頻接口的剩余容量，因此業(yè)務(wù)從工作ONU切換到備份ONU，理論上不會(huì)影響備份ONU原有業(yè)務(wù)的性能。

3 可生存網(wǎng)絡(luò)規(guī)劃問(wèn)題描述

將整個(gè)網(wǎng)絡(luò)區(qū)域均勻地劃分成S×S個(gè)方型單元，以每個(gè)方型單元的中心作為無(wú)線路由器的候選位置。已知每個(gè)工作ONU在網(wǎng)絡(luò)區(qū)域中的位置及其業(yè)務(wù)的帶寬需求，基于無(wú)線重路由保護(hù)的可生存網(wǎng)絡(luò)規(guī)劃主要解決無(wú)線資源與光網(wǎng)絡(luò)資源的聯(lián)合優(yōu)化分配問(wèn)題，包括：哪些方型單元內(nèi)需要部署無(wú)線路由器；每個(gè)無(wú)線路由器需要配置多少個(gè)備份射頻接口；每個(gè)工作ONU需要分配哪些備份ONU；每個(gè)備份ONU需要預(yù)留多少備份容量。

3.1 符號(hào)定義

為便于問(wèn)題描述，定義如下符號(hào)。

（1）已知參量

i：無(wú)線節(jié)點(diǎn)（包括無(wú)線路由器和ONU／無(wú)線網(wǎng)關(guān)）的索引編號(hào)，i∈｛1，2，3，…｝；

wi：由i索引的無(wú)線節(jié)點(diǎn)；

圖 1 FiWi接入網(wǎng)中無(wú)線重路由保護(hù)方法示意

p，q：無(wú)線路由器的候選位置索引編號(hào)，p，q∈｛1，2，3，…，S×S｝；

lp：由p索引的候選位置；

Lp，q：候選位置 lp與 lq之間的無(wú)線鏈路；

k：無(wú)線路由器的索引編號(hào)，k∈｛1，2，3，…｝；

rk：由k索引的無(wú)線路由器；

U：網(wǎng)絡(luò)中ONU數(shù)量；

m，n：ONU 的索引編號(hào)，m，n∈｛1，2，3，…，U｝；

om：由m索引的 ONU；

T：無(wú)線節(jié)點(diǎn)的傳輸半徑；

dp，q：候選位置 lp和 lq之間的距離；

?p，q：二進(jìn)制常量，若 dp，q≤T，取值為 1；否則，取值為 0；

R：每個(gè)無(wú)線路由器最多能配置的備份射頻接口數(shù)量；

C：每個(gè)備份射頻的帶寬容量；

dm：ONU om的業(yè)務(wù)量；

μm：ONU om的剩余容量；

ρu：配置u個(gè)備份射頻接口的無(wú)線路由器的部署成本，u∈｛1，2，…，R｝；

H：無(wú)線備份路徑的長(zhǎng)度約束（單位：跳數(shù)）；

I：足夠大的整數(shù)。

（2）決策變量

λp：二進(jìn)制變量，如果無(wú)線路由器部署在位置坐標(biāo)lp，取值為1；否則，取值為0；

δm，n：二進(jìn)制變量，如果 on是 om的備份 ONU，取值為 1；否則，取值為0；

ηm，n：om到 on的無(wú)線備份路徑上承載的業(yè)務(wù)量；

πp，q：二進(jìn)制變量，如果 lp與 lq之間存在無(wú)線鏈路，取值為 1；否則，取值為 0。

3.2 優(yōu)化目標(biāo)

基于無(wú)線重路由保護(hù)的可生存網(wǎng)絡(luò)規(guī)劃以最小化FiWi前端無(wú)線網(wǎng)絡(luò)的部署成本為目標(biāo)。無(wú)線網(wǎng)絡(luò)的部署成本主要取決于每個(gè)無(wú)線路由器配置的備份射頻接口數(shù)量，因此優(yōu)化目標(biāo)可描述如下：

（1）關(guān)于備份ONU容量分配的約束條件

按照無(wú)線重路由保護(hù)方法，每個(gè)備份ONU將從自己的剩余容量中為其工作ONU預(yù)留備份容量。在單分支光纖鏈路故障情況下，任何一對(duì)工作ONU不會(huì)同時(shí)與OLT之間發(fā)生連接中斷，因此不同工作ONU之間可以共享相同的備份ONU的剩余容量。為保證工作ONU失效情況下業(yè)務(wù)恢復(fù)的帶寬需求，每個(gè)工作ONU的所有備份ONU的累計(jì)剩余容量應(yīng)大于或等于該工作ONU的業(yè)務(wù)量。因此，關(guān)于備份ONU容量分配的約束條件可定義為：

（2）關(guān)于備份射頻容量分配的約束條件

一旦工作ONU的分支光纖鏈路故障，失效的工作ONU將通過(guò)無(wú)線備份路徑將業(yè)務(wù)轉(zhuǎn)移到備份ONU承載，因此工作ONU到它的每個(gè)備份ONU之間至少存在一條可用的無(wú)線備份路徑。任意無(wú)線備份路徑能夠穿過(guò)位置坐標(biāo)lp與lq之間的邊，當(dāng)且僅當(dāng)lp與lq之間存在可用的無(wú)線鏈路時(shí)：

其中，lp與lq之間存在可用無(wú)線鏈路的條件是lp和lq上均部署無(wú)線路由器，且在彼此傳輸范圍之內(nèi)，如下：

如果在位置坐標(biāo)lp上沒(méi)有部署無(wú)線路由器，存在θup=0，?u，相應(yīng)的約束條件為：

無(wú)線備份路徑經(jīng)過(guò)的每個(gè)無(wú)線路由器需要為工作ONU分配足夠的備份射頻容量，以滿(mǎn)足業(yè)務(wù)轉(zhuǎn)移過(guò)程中的帶寬需求。由于業(yè)務(wù)轉(zhuǎn)移所占用的備份射頻容量被提前預(yù)留且獨(dú)立于其他業(yè)務(wù)，因此不同業(yè)務(wù)在轉(zhuǎn)移過(guò)程中不會(huì)爭(zhēng)用彼此的備份射頻容量。盡管如此，由于在單分支光纖鏈路故障場(chǎng)景下，不同工作ONU不會(huì)同時(shí)與OLT之間連接中斷，因此不同工作ONU的無(wú)線路徑經(jīng)過(guò)相同無(wú)線路由器時(shí)允許它們共享備份射頻容量。這要求無(wú)線路由器為每個(gè)工作ONU分配的備份射頻容量均不應(yīng)超過(guò)這個(gè)無(wú)線路由器上所有備份射頻的總?cè)萘浚瑪?shù)學(xué)表示為：

（3）關(guān)于無(wú)線備份路徑長(zhǎng)度的約束條件

無(wú)線重路由保護(hù)方法中影響業(yè)務(wù)恢復(fù)效率的因素包括保護(hù)切換時(shí)間和備份路徑的傳輸時(shí)延，二者均主要取決于無(wú)線備份路徑的跳數(shù)。顯然，較長(zhǎng)的無(wú)線備份路徑不利于業(yè)務(wù)恢復(fù)效率，為此引入無(wú)線備份路徑長(zhǎng)度約束，限制每條無(wú)線備份路徑的長(zhǎng)度不超過(guò)H跳，數(shù)學(xué)表示為：

為保證任意無(wú)線備份路徑的路由連續(xù)性，其源節(jié)點(diǎn)（如工作 ONU om）的輸出流量為 ηm，n，輸入流量為 0；目的節(jié)點(diǎn)（如備份 ONU on）的輸入流量為 ηm，n，輸出流量為 0；中間節(jié)點(diǎn)的輸出流量與輸入流量相等，為此引入如下的流守恒（flow conservation）約束：

此外，無(wú)線重路由保護(hù)方法允許每個(gè)失效的工作ONU通過(guò)多跳無(wú)線備份路徑將業(yè)務(wù)轉(zhuǎn)移給不同的備份ONU，所有無(wú)線備份路徑應(yīng)當(dāng)完全承載失效工作ONU的業(yè)務(wù)量。

其中，式（16）和式（17）保證每個(gè)工作 ONU 與其備 份ONU之間的無(wú)線備份路徑一定承載業(yè)務(wù)量，從而避免多余的空載備份路徑。

4 啟發(fā)式算法

考慮到大規(guī)模網(wǎng)絡(luò)規(guī)劃的應(yīng)用需求以及ILP等數(shù)學(xué)方法的耗時(shí)特征，本文提出了最大保護(hù)業(yè)務(wù)量?jī)?yōu)先（maximum protected-traffic first，MPTF）的啟發(fā)式算法。在MPTF算法中，首先將無(wú)線路由器逐個(gè)地部署到網(wǎng)絡(luò)中，初始情況下每個(gè)無(wú)線路由器按照最多R個(gè)備份射頻接口進(jìn)行配置。增加網(wǎng)絡(luò)中無(wú)線路由器的部署有利于工作ONU與備份ONU之間建立新的無(wú)線備份路徑，從而增加新的備份ONU以及被保護(hù)的業(yè)務(wù)量。然后，以最大化新增被保護(hù)業(yè)務(wù)量為目標(biāo)，依次決策出每個(gè)無(wú)線路由器的最佳部署位置，并為工作ONU的業(yè)務(wù)分配備份ONU容量和備份射頻容量，直到網(wǎng)絡(luò)中所有工作ONU的業(yè)務(wù)量被完全保護(hù)。最后，根據(jù)工作ONU的實(shí)際帶寬需求刪除每個(gè)無(wú)線路由器上的冗余備份射頻。為便于論述，為MPTF算法引入如下符號(hào)定義。

γk，p：如果 rk部署在位置坐標(biāo) lp上，整個(gè)網(wǎng)絡(luò)額外被保護(hù)的業(yè)務(wù)量；

W：網(wǎng)絡(luò)中總共部署的無(wú)線路由器數(shù)量；

P：當(dāng)前整個(gè)網(wǎng)絡(luò)已經(jīng)被保護(hù)的業(yè)務(wù)量；

Rk：為無(wú)線路由器rk配置的射頻接口數(shù)量。

下文為MPTF算法的偽代碼流程。當(dāng)部署第k個(gè)無(wú)線路由器rk時(shí)，遍歷所有可能的候選位置，對(duì)于任意候選位置lp，首先在包括lp的無(wú)線拓?fù)渲型ㄟ^(guò)Dijkstra路由算法為每個(gè)工作ONU om確定可能的備份ONU集合（見(jiàn)算法1第5行）。對(duì)于任一 ONU on∈，保證 om到 on之間至少存在一條滿(mǎn)足長(zhǎng)度約束且射頻容量非零的無(wú)線備份路徑。已知無(wú)線備份路徑上的節(jié)點(diǎn)集合，工作ONU om可以在這條無(wú)線備份路徑上承載的業(yè)務(wù)量主要受限于集合中剩余射頻容量較小的節(jié)點(diǎn)。對(duì)于任意無(wú)線節(jié)點(diǎn)wi∈，定義代表無(wú)線節(jié)點(diǎn)wi的剩余射頻容量中能夠繼續(xù)為工作ONU om備份的射頻容量，那么可計(jì)算出ONU om到on之間的這條無(wú)線備份路徑上最多承載的業(yè)務(wù)量如下（見(jiàn)算法1第6行）：

然后，進(jìn)一步考慮備份ONU on的剩余容量對(duì)業(yè)務(wù)保護(hù)的限制，可計(jì)算出om能夠被on保護(hù)的業(yè)務(wù)量為：

MPTF算法偽代碼如下所示。

算法1 MPTF算法

輸入 lp，U，C，R，dm，μm，?m，p。

輸出 δm，n，λp，Rkηm，n?p，k，m，n：m≠n。

（1）初始化 λp←0，δm，n←0，P←0，W←0，k←1，←0，

（5） 在滿(mǎn)足跳數(shù)約束的情況下，通過(guò)Dijkstra路由算法計(jì)算；

（6） ?on∈， 按照式（18）和式（19）計(jì)算；

（7） end for

（8） 按照式（20）計(jì)算 γk，p；

（9） end for

（10） 將rk部署在位置坐標(biāo)，實(shí)現(xiàn)最大化；

（12） ?k，i，m，n：m≠n，按照式（21）～式（24）分別計(jì)算

（13） 更新 k←k+1；

（14）end while

（16）根據(jù)式（25）計(jì)算Rk并刪除冗余的備份射頻；

（17）輸出 λp，δm，n，Rk，ηm，n，?p，k，m，n：m≠n

顯然，每個(gè)無(wú)線路由器rk部署在不同位置將實(shí)現(xiàn)不同程度被保護(hù)的業(yè)務(wù)量。為了減少無(wú)線前端的部署成本，MPTF算法將rk部署在可實(shí)現(xiàn)最大化被保護(hù)業(yè)務(wù)量的最佳位置

每完成一個(gè)無(wú)線路由器的部署，執(zhí)行以下更新步驟（見(jiàn)算法 1 第 11 行，W←W+1。同時(shí)，可根據(jù)式（21）和式（22）分別計(jì)算和（見(jiàn)算法 1第 12行）。

由于新增的無(wú)線備份路徑經(jīng)過(guò)的節(jié)點(diǎn)將預(yù)留額外的備份射頻容量，相應(yīng)地需要更新這些無(wú)線節(jié)點(diǎn)已分配給工作ONU的射頻容量（?i，m）。為此，首先定義臨時(shí)二進(jìn)制變量：當(dāng)無(wú)線節(jié)點(diǎn)wi位于工作ONU om到其備份ONU on（）的無(wú)線備份路徑上，即，那么取值為1；否則，取值為0，如下：

可得：

按照上面的迭代步驟，完成每個(gè)無(wú)線路由器的部署，直到所有工作ONU的業(yè)務(wù)量都得到完全的保護(hù)，即（見(jiàn)算法1第2行）。最后，為刪除每個(gè)無(wú)線路由器上冗余的備份射頻，計(jì)算無(wú)線路由器rk需要配置的備份射頻數(shù)量為：

5 性能評(píng)估

5.1 仿真設(shè)置

仿真中設(shè)置20 km×20 km的方形網(wǎng)絡(luò)區(qū)域，其中隨機(jī)部署10個(gè)ONU（即O=10）。指定OLT和分光器的位置，且主干光纖鏈路和分支光纖鏈路的長(zhǎng)度分別限定在15 km和5 km范圍內(nèi)［7］。將整個(gè)網(wǎng)絡(luò)區(qū)域劃分為S×S個(gè)單元格，其中，S∈｛6，7，8，9，10｝。每個(gè)無(wú)線路由器的備份射頻最大數(shù)目為R=4［10］。定義無(wú)線路由器配置單個(gè)備份射頻的成本作為無(wú)線子網(wǎng)部署成本的基本單位，并且每增設(shè)一個(gè)備份射頻，部署成本相應(yīng)增加0.5個(gè)單位。因此，無(wú)線路由器配置1、2、3、4 個(gè)備份射頻對(duì)應(yīng)的部署成本分別為 1、1.5、2 和2.5。所有ONU均等的分配20個(gè)單位容量。每個(gè)ONU的業(yè)務(wù)量在區(qū)間［5，dmax］內(nèi)生成 ，其中，dmax∈｛8，10，12，14，16｝。無(wú)線傳輸范圍T在｛0.6，0.7，0.8，0.9，1｝km 之間變化。任意一對(duì)無(wú)線節(jié)點(diǎn)間存在無(wú)線鏈路的條件是兩個(gè)節(jié)點(diǎn)在彼此的傳輸范圍之內(nèi)且占用相同信道。

仿真中分別基于ILP模型和啟發(fā)式算法進(jìn)行網(wǎng)絡(luò)規(guī)劃，其中，ILP模型在Intel Core i5 2.30 GHz CPU和2 GB RAM的主機(jī)上通過(guò)專(zhuān)業(yè)優(yōu)化工具ILOG CPLEX 12.1求解。為分析成本效益優(yōu)勢(shì)，將文中提出的網(wǎng)絡(luò)規(guī)劃方法與廣泛用于PON保護(hù)的備份光纖方法進(jìn)行比較，并假設(shè)部署每公里光纖的成本是配置單個(gè)備份射頻的無(wú)線路由器成本的16倍［11］。

圖2 不同業(yè)務(wù)量對(duì)應(yīng)的平均網(wǎng)絡(luò)部署成本

5.2 結(jié)果分析

在圖2中，設(shè)置參數(shù)S=7和T=0.7。根據(jù)美國(guó)加利福尼亞大學(xué)戴維斯分校的研究結(jié)果［12］，在FiWi接入網(wǎng)中無(wú)線路徑長(zhǎng)度大于3跳的情況下，傳輸時(shí)延性能出現(xiàn)明顯下降，因此本文在圖2及后續(xù)的仿真場(chǎng)景中將無(wú)線備份路徑長(zhǎng)度限制設(shè)為H=3。隨著ONU業(yè)務(wù)量的變化，圖2中對(duì)基于備份光纖保護(hù)的網(wǎng)絡(luò)規(guī)劃方法和基于無(wú)線重路由保護(hù)的網(wǎng)絡(luò)規(guī)劃方法（包括啟發(fā)式方法和ILP方法）進(jìn)行單位業(yè)務(wù)量平均網(wǎng)絡(luò)部署成本的性能對(duì)比。由于備份光纖保護(hù)方法中忽略了業(yè)務(wù)量的可擴(kuò)展性，其總部署成本與業(yè)務(wù)量無(wú)關(guān)，因此業(yè)務(wù)量的增加將導(dǎo)致單位業(yè)務(wù)量平均網(wǎng)絡(luò)部署成本逐漸下降，但與此同時(shí)也會(huì)增加光纖鏈路的帶寬壓力。相比之下，本文提出的基于無(wú)線重路由保護(hù)的網(wǎng)絡(luò)規(guī)劃方法在進(jìn)行備份射頻容量和備份ONU容量分配時(shí)充分保證業(yè)務(wù)量帶寬需求，因此在業(yè)務(wù)恢復(fù)過(guò)程中不會(huì)發(fā)生網(wǎng)絡(luò)擁塞。隨著業(yè)務(wù)量逐漸增加，本文提出的網(wǎng)絡(luò)規(guī)劃方法的總部署成本也逐漸升高，這導(dǎo)致單位業(yè)務(wù)量平均網(wǎng)絡(luò)部署成本的波動(dòng)變化。盡管如此，本網(wǎng)絡(luò)規(guī)劃方法始終保持比備份光纖保護(hù)方法更低的部署成本。當(dāng)業(yè)務(wù)量取值區(qū)間從［5，8］增加到［5，16］時(shí)，本啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法相對(duì)于備份光纖保護(hù)方法節(jié)省的部署成本比率從85.1%變化到66%。同時(shí)，可觀察到啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法的部署成本略高于ILP網(wǎng)絡(luò)規(guī)劃方法。然而，二者之間的差距始終限制在小于4.65%的范圍內(nèi)。更重要地，ILP網(wǎng)絡(luò)規(guī)劃方法要求數(shù)小時(shí)量級(jí)的運(yùn)行時(shí)間，而啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法的運(yùn)行時(shí)間僅為數(shù)秒。當(dāng)業(yè)務(wù)量從區(qū)間［5，8］變化到區(qū)間［5，16］時(shí)，啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法能節(jié)省超過(guò)99.99%的運(yùn)行時(shí)間，見(jiàn)表1。這些結(jié)果充分證明了啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法是產(chǎn)生次優(yōu)解的高效方法。

圖3顯示出不同網(wǎng)格數(shù)量情況下3種方法的單位業(yè)務(wù)量平均網(wǎng)絡(luò)部署成本的比較結(jié)果。設(shè)置參數(shù)dmax=14，T=0.7和H=3。網(wǎng)絡(luò)中更大的單元格數(shù)量意味著無(wú)線路由器的部署將有更多的候選位置，這有助于降低網(wǎng)絡(luò)部署成本。因此，可以觀察到當(dāng)單元格數(shù)量較大時(shí)，本文提出的網(wǎng)絡(luò)規(guī)劃方法的部署成本逐漸降低。特別當(dāng)單元格數(shù)目增加到10×10，啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法相比備份光纖保護(hù)方法在減少部署成本方面獲得了接近81.4%的優(yōu)勢(shì)。值得注意的是，當(dāng)單元格數(shù)目過(guò)高時(shí)，ILP的運(yùn)行時(shí)間將不可接受。在這種情況下，啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法比ILP網(wǎng)絡(luò)規(guī)劃方法更具時(shí)效性和實(shí)用性。

圖3 不同網(wǎng)格數(shù)量對(duì)應(yīng)的平均網(wǎng)絡(luò)部署成本

在圖4中，設(shè)置參數(shù)dmax=14，S=7和H=3，對(duì)不同無(wú)線傳輸范圍的單位業(yè)務(wù)量的平均網(wǎng)絡(luò)部署成本進(jìn)行比較。當(dāng)無(wú)線傳輸范圍較大時(shí)，每個(gè)無(wú)線節(jié)點(diǎn)擁有更多的鄰居節(jié)點(diǎn)，這有助于減少每條無(wú)線備份路徑上無(wú)線路由器的數(shù)量。因此，本文提出的網(wǎng)絡(luò)規(guī)劃方法的平均部署成本表現(xiàn)出逐漸降低的趨勢(shì)。例如，當(dāng)無(wú)線傳輸范圍從0.6 km變化到1 km時(shí)，啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法的部署成本減少了42.4%。相比之下，備份光纖保護(hù)方法的部署成本始終保持在恒定水平，即與無(wú)線傳輸范圍無(wú)關(guān)。所以，當(dāng)無(wú)線傳輸范圍較大時(shí)，本文提出的網(wǎng)絡(luò)規(guī)劃方法在減少網(wǎng)絡(luò)部署成本方面能實(shí)現(xiàn)出更為顯著的優(yōu)勢(shì)。

圖4 不同無(wú)線傳輸范圍對(duì)應(yīng)的平均網(wǎng)絡(luò)部署成本

為進(jìn)一步分析不同的無(wú)線備份路徑長(zhǎng)度約束H對(duì)平均網(wǎng)絡(luò)部署成本的影響，仿真中設(shè)定參數(shù)dmax=14，S=7和T=0.7，對(duì)基于無(wú)線重路由保護(hù)的網(wǎng)絡(luò)規(guī)劃方法與基于備份光纖保護(hù)的網(wǎng)絡(luò)規(guī)劃方法在 H∈｛2，3，4，5，6｝的情況下進(jìn)行部署成本比較，結(jié)果如圖5所示。根據(jù)無(wú)線重路由保護(hù)方法，每個(gè)工作ONU與它的備份ONU之間應(yīng)該至少存在一條可用的無(wú)線備份路徑，且路徑長(zhǎng)度小于或等于H跳。較大的H有利于減少無(wú)線備份路徑所需的無(wú)線路由器和備份射頻數(shù)量，因此有利于降低部署成本。例如，當(dāng)跳數(shù)限制H從2增加到6時(shí)，本文提出的啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法中平均每單位業(yè)務(wù)量需要的網(wǎng)絡(luò)部署成本降低24.3%。此外，啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法與ILP網(wǎng)絡(luò)規(guī)劃方法始終保持相當(dāng)接近的網(wǎng)絡(luò)部署成本，且差距小于5.7%。

表1 啟發(fā)式網(wǎng)絡(luò)規(guī)劃方法與ILP網(wǎng)絡(luò)規(guī)劃方法的比較

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

本文研究了可生存FiWi接入網(wǎng)的成本最小化規(guī)劃問(wèn)題，針對(duì)典型的單分支光纖鏈路故障情況提出一種基于無(wú)線重路由保護(hù)的網(wǎng)絡(luò)規(guī)劃方法。以最小化前端無(wú)線網(wǎng)絡(luò)部署成本為目標(biāo)，重點(diǎn)解決ONU備份容量分配、無(wú)線路由器部署、備份射頻配置的聯(lián)合優(yōu)化問(wèn)題。通過(guò)ILP模型對(duì)聯(lián)合優(yōu)化問(wèn)題進(jìn)行了規(guī)范的數(shù)學(xué)描述，并通過(guò)專(zhuān)業(yè)優(yōu)化工具ILOG CPLEX 12.1獲得小規(guī)模網(wǎng)絡(luò)的最優(yōu)解?？紤]到大規(guī)模網(wǎng)絡(luò)場(chǎng)景中ILP求解的耗時(shí)特征，本文還提出高效的啟發(fā)式算法。結(jié)果表明，本文提出的網(wǎng)絡(luò)規(guī)劃方法能實(shí)現(xiàn)比傳統(tǒng)備份光纖保護(hù)方法更低的網(wǎng)絡(luò)部署成本，尤其在候選位置較密集、無(wú)線傳輸范圍較大以及允許無(wú)線備份路徑較長(zhǎng)的場(chǎng)景中，這種成本效益優(yōu)勢(shì)會(huì)更加明顯。

圖5 無(wú)線備份路徑的不同跳數(shù)限制對(duì)應(yīng)的部署成本

［1］LIU Y J， GUO L， WEI X T.Optimizing backup optical-network-units selection and backup fibers deployment in survivable hybrid wireless-optical broadband access networks［J］.IEEE／OSA Journal of Lightwave Technology，2012，30 （10）：1509-1523.

［2］LIU Y J，GUO L，GONG B，et al.Green survivability in fiber-wireless （FiWi）broadband access network［J］.Optical Fiber Technology，2012，18（2）：68-80.

［3］GUO L，LIU Y J，WANG F Z，et al.Cluster-based protection for survivable fiber-wireless （FiWi）access network ［J］.IEEE／OSA Journal of Optical Communications and Networking，2013，5（11）：1178-1194.

［4］CHARNI R，MAIER M.Total cost of ownership and risk analysis of collaborative implementation models for integrated fiber-wireless smart grid communications infrastructures［J］.IEEE Transactions on Smart Grid，2014，5（5）：2264-2272.

［5］DAI Q L，SHOU G C，HU Y H，et al.A general model for hybrid fiber-wireless （FiWi）access network virtualization ［C］／／The IEEE International Conference on Communications Workshops，June 9-13，2013，Budapest，Hungary.New Jersey：IEEE Press，2013：858-862.

［6］RANAWEERAC，WONGE，LIMC，etal.Architecture discovery enabled resource allocation mechanism fornext generation optical-wireless converged networks ［J］.IEEE／OSA Journal of Optical Communications and Networking，2013，5（9）：1083-1094.

［7］BURAK K，MOUFTAH H T.Reliable and fast restoration for a survivable wireless-optical broadband access network ［C］／The International Conference on Transparent Optical Network，June 27-July 1，2010，Munich，Germany.［S.1.：s.n.］，2010：1-4.

［8］LAI C L，LIN H T，CHIANG H H，et al.Design and analysis of a frame-based dynamic bandwidth allocation scheme for fiber-wireless broadband access networks ［J］.IEEE／OSA Journal ofOpticalCommunicationsand Networking，2014，6 （5）：486-500.

［9］LIU Y J，SONG Q Y，MA R，et al.Protection based on backup radios and backup fibers for survivable Fiber-Wireless （FiWi）access network ［J］.Journal of Network and Computer Applications，2013，36（3）：1057-1069.

［10］REAZAS，RAMAMURTHIV，TORNATOREM，etal.Cloud-integrated WOBAN：an offloading-enabled architecture for service-oriented access networks ［J］.Computer Networks，2014，68（5）：5-19.

［11］SARKAR S，YEN H H，DIXIT S，et al.Hybrid wireless-optical broadband access network （WOBAN）：network planning and setup ［J］.IEEE Journal on Selected Areas in Communications，2008，26（11）：12-21.

［12］SARKAR S，YEN H H，DIXIT S.DARA：delay-aware routing algorithm in a hybrid wireless-optical broadband access network （WOBAN）［C］／The IEEE International Conference on Communications，June 24-28，2007，Glasgow，Scotland.New Jersey：IEEE Press，2007：2480-2484.

Planning approach of survivable fiber-wireless broadband access network

TAN Hongjun1，XIE Yamin2，LIU Yejun2
1.Sichuan Engineering Technical College，Deyang 618000，China 2.College of Information Science and Engineering，Northeastern University，Shenyang 110819，China

The emerging fiber-wireless（FiWi）broadband access network provides not only the new technological references for flexible broadband access anywhere and anytime，but also the research opportunities for the cost-efficient design of survivable broadband access network.The study of survivable FiWi access network planning was focused on，and an approach of survivable network planning based on wireless-rerouting protection was proposed.When any fiber link cuts，the failed optical network unit （ONU）can transfer its traffic into other normal ONUs.Solving the joint optimization problem of wireless routers placement，backup radios configuration and ONU capacity allocation was put more importance on，aiming to fully protect all traffic with the minimum deployment cost.The method of integer linear programming was employed to obtain the optimal solution for small-scale network planning.The heuristic algorithm was also proposed for the large-scale network planning.Simulation results demonstrate the effectiveness of the proposed approach in reducing network deployment cost.

fiber-wireless，survivable network planning，wireless rerouting，network protection，backup resource

TN915.63

A

10.11959／j.issn.1000-0801.2016120

2015-10-20；

2016-04-03

譚紅君（1977-），女，四川工程職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)殡娏﹄娮油ㄐ?、網(wǎng)絡(luò)規(guī)劃。

解亞敏（1990-），女，東北大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向?yàn)橄乱淮饨尤刖W(wǎng)。

劉業(yè)君（1986-），男，東北大學(xué)信息科學(xué)與工程學(xué)院副教授，主要研究方向?yàn)楣饫w—無(wú)線融合接入網(wǎng)。