基于GIS的光接安全入網(wǎng)主干光纜路由優(yōu)化模型和算法研究

◆王 璇

（四川通信科研規(guī)劃設(shè)計有限責任公司 四川 610000）

基于GIS的光接安全入網(wǎng)主干光纜路由優(yōu)化模型和算法研究

◆王 璇

（四川通信科研規(guī)劃設(shè)計有限責任公司 四川 610000）

本文分別介紹了星形、環(huán)形及線形三種結(jié)構(gòu)的光接入網(wǎng)主干光纜路由的優(yōu)化模型及算法，這種主干光纜路由數(shù)學(xué)模型及優(yōu)化算法均是在MapInfo GIS 平臺構(gòu)建的，通過減少鏈路段的數(shù)目及搜索的節(jié)點有效的提高了算法的效率，具有較好的實用性。

GIS; 光接入網(wǎng); 主干光纜路由; 優(yōu)化模型

0 前言

光接入網(wǎng)規(guī)劃中主干光纜路由優(yōu)化是重要的工作內(nèi)容，直接影響著光接入網(wǎng)的建設(shè)投資即網(wǎng)絡(luò)生存性。目前來說，光接入網(wǎng)主干光纜路由主要有星形、環(huán)形及線形三種結(jié)構(gòu)，本文主要就光接入網(wǎng)主干光纜路由優(yōu)化的模型及算法進行簡單的探討分析。

1 主干光纜路由的數(shù)學(xué)模型

實際的光網(wǎng)規(guī)劃過程中規(guī)劃小區(qū)的分布、管道、原有光纜資源等都會影響到光接入網(wǎng)主干光纜路由，一般情況下主干光纜路由的長度比較短但覆蓋度均能夠達到一定的要求，主干光纜路由的模型主要如下所示:

圖1 主干光纜路由的模型

其中Rlen、Rcos、Rcov分別指的是路由的長度、投資及覆蓋度，E指的是網(wǎng)絡(luò)中的第i條鏈路段,Li則指的是第i條鏈路段的長度，R指的是光纜的路由,Cf、Cp、Cp表示路由上光纜的投資、管道投資及人孔投資，NS指的是路由目標點集，N1、N2分別指的是主干光纜覆蓋的規(guī)劃小區(qū)數(shù)及該業(yè)務(wù)節(jié)點覆蓋的總規(guī)劃小區(qū)數(shù)目。

主干光纜路由問題實際上是一個多目標規(guī)劃的問題，具體的規(guī)劃過程中需要將其轉(zhuǎn)化為單目標規(guī)劃問題之后才能夠更好的解決。光接入網(wǎng)主干光纜路由優(yōu)化時首先將路由上的投資作為目標，通過優(yōu)化路由覆蓋度及長度實現(xiàn)優(yōu)化的目的，在此過程中，覆蓋度作為路由檢驗的條件，路由的長度及投資呈現(xiàn)一種正相關(guān)關(guān)系，是影響路由上投資的重要因素。光接入網(wǎng)的路由主要表現(xiàn)為網(wǎng)絡(luò)鏈路段的集合，在光接入網(wǎng)中主干光纜路由沿著道路行進，管道、人孔等等影響路由的因素均附著在道路之上，將多目標規(guī)劃模型轉(zhuǎn)化為單目標規(guī)劃模型的過程中需要將這些影響因素都映射在道路網(wǎng)絡(luò)的鏈路段之上，最終形成一個綜合的權(quán)值然后進行路網(wǎng)路由的優(yōu)化。轉(zhuǎn)化之后單目標模型主要如下所示:

其中Wi指的是路網(wǎng)第i段鏈路段的綜合權(quán)值，Cfi、Cpi、Cmi指的是第i段鏈路段上光纜的投資、管道投資及人孔投資，Pf指的是每公里光纜芯的造價，Nf指的是該鏈路段上光纜的芯數(shù)，Pp指的是每公里管道孔的造價，Np指的是該鏈路段上管道的孔數(shù)，Pm指的是單位面積人孔的造價，S指的是第i個人孔的面積，r指的是規(guī)劃小區(qū)的光纜覆蓋率，剩余的變量的含義與主干光纜路由的模型中含義一致。

圖2 單目標模型

2 主干光纜路由優(yōu)化的算法設(shè)計

2.1 主干光纜路由的拓撲結(jié)構(gòu)

由上文可知，主干光纜路由主要有三種拓撲結(jié)構(gòu)，它們各自有著不同的特點，三種拓撲結(jié)構(gòu)主要的區(qū)別在于主干光分接點與業(yè)務(wù)節(jié)點及主干光分接點之間的連接方式不同，這些連接方式之間的差異導(dǎo)致了路由優(yōu)化方法的差別。通常情況下，路由求解時，主干光分接點未知，為了滿足主干光纜路由拓撲結(jié)構(gòu)的需求需要引入主干光分接點，實際的優(yōu)化計算過程中，基本上提供的都是路由目標點和業(yè)務(wù)節(jié)點。

星型拓撲結(jié)構(gòu)路由優(yōu)化時需要分別搜索業(yè)務(wù)節(jié)點到每個目標點之間的最佳的路徑，因此星型結(jié)構(gòu)路由優(yōu)化實際上求解目標點與業(yè)務(wù)節(jié)點之間的最有路徑，實際的優(yōu)化過程中，經(jīng)常會出現(xiàn)路由之間鏈路重復(fù)的問題，因此相關(guān)設(shè)計人員需要根據(jù)實際的優(yōu)化設(shè)計要求采取對應(yīng)的控制措施，允許重復(fù)時則不需要對使用過的路段進行標示，如果不允許重復(fù)則需要進行禁用標識。

線形拓撲結(jié)構(gòu)優(yōu)化過程中需要按照一定的順序從業(yè)務(wù)節(jié)點到目標點依次的串聯(lián)起來，并通過一定的措施保證路由的權(quán)值最小，線形拓撲結(jié)構(gòu)的路由之中不允許自相交及走回頭路，因此線性拓撲結(jié)構(gòu)優(yōu)化的含義就是將目標點與業(yè)務(wù)節(jié)點進行組合，組合過程中使用過的路段需要進行禁用標識。

環(huán)形拓撲結(jié)構(gòu)的路由中主干光纜從業(yè)務(wù)節(jié)點出發(fā)，按照一定的順序向目標點走，最終需要回到業(yè)務(wù)節(jié)點，實際的工作過程中容易出現(xiàn)路由自相交、出局路由與入局路由重合不良現(xiàn)象，路由優(yōu)化過程中為了避免此類問題,本文簡單介紹了一種“分界方法”。首先設(shè)業(yè)務(wù)節(jié)點坐標為（x0，y0），選擇一個目標點P（x，y），使得 max {|x- x0|+ |y- y0|}，然后以該點與業(yè)務(wù)節(jié)點所在的直線為分界線，將整個環(huán)形路由劃分為兩個呈線形特征的部分，此后通過一定的優(yōu)化方法分別求解這兩個部分之后再進行合并，形成環(huán)形,由于分界線兩邊的光分接點存在著十分明顯的線形特征，同時分界線能夠很好的避免自相交問題,因此通過這種分界方法，能夠有效的避免出局路由與入局路由重合、路由自相交等不良現(xiàn)象。

2.2 路由優(yōu)化算法

在計算源節(jié)點與其他節(jié)點最小代價路徑過程中，Dijkstra算法應(yīng)用價值較高，因此下文主要就基于Dijkstra算法的路由優(yōu)化算法進行簡單的分析介紹。

Dijkstra算法應(yīng)用的關(guān)鍵在于下一個擴展節(jié)點及數(shù)據(jù)結(jié)構(gòu)的選擇，一般情況下，BFS（best-first-search）、LIFO（last-in-first-out）、FIFO（first-in -first -out）是三種應(yīng)用比較多的擴展節(jié)點選擇方法，哈希散列和隊列、堆棧等等是常見的數(shù)據(jù)結(jié)構(gòu)。

Dijkstra 算法的時間復(fù)雜度為O（n2），因此當路網(wǎng)的規(guī)模比較大時，這種算法的速度比較慢，難以滿足工程應(yīng)用的實際要求，因此需要采用一定的處理方法降低時間復(fù)雜度。BFS的搜索策略和優(yōu)先隊列能夠?qū)崿F(xiàn)這一目的，實際的處理過程中通過圖的廣度優(yōu)先搜索方法，利用優(yōu)先列隊的手段按照路徑權(quán)值對節(jié)點進行排序，權(quán)值較小的先列隊，出隊列出后進行訪問標記，改進之后的算法稱為Di jkstra 優(yōu)先隊列算法。工程實踐中，優(yōu)先隊列中節(jié)點的鄰接點平均常數(shù)為C，隊列的長度并不受節(jié)點數(shù)的限制，Dijkstra 優(yōu)先隊列算法的時間復(fù)雜度為O（n），相對于Dijkstra 算法而言明顯降低。

使用Dijkstra優(yōu)先隊列算法進行主干光纜路由優(yōu)化算法設(shè)計的思路如下:星形主干光纜路由優(yōu)化時以業(yè)務(wù)節(jié)點為原點，采用Dijkstra 優(yōu)先隊列算法對每個節(jié)點進行優(yōu)化; 線形主干光纜路由優(yōu)化時采用選小及排序的搜索策略對目標點與業(yè)務(wù)節(jié)點進行優(yōu)化組合，這一過程實際上是一個迭代的過程，已經(jīng)求出的路由在迭代之前需要進行“障礙”標記，下一次優(yōu)化組合時需要重新選取目標點，這種搜索方法有效的避免了走回頭路及自相交問題，確保了目標點與業(yè)務(wù)節(jié)點組合的最優(yōu)性。環(huán)形主干光纜路由優(yōu)化過程中首先根據(jù)上文所述的max {|x- x0|+ |y- y0|} 的條件將符合要求的P（x，y）目標點找出，然后在分界線的兩邊形成兩條線形的路由，因此環(huán)形主干光纜路由優(yōu)化實際上是基于線形路由基礎(chǔ)上進行的。

3 結(jié)束語

本文在MapInfo GIS平臺之上使用VC+ +編程的方法構(gòu)造一個基于鏈路段的數(shù)據(jù)結(jié)構(gòu),結(jié)合某電信接入網(wǎng)規(guī)劃的具體數(shù)據(jù)對上文介紹的主干光纜路由優(yōu)化模型和算法進行了驗證,驗證結(jié)果表明這種規(guī)劃方法與原來的規(guī)劃結(jié)果一致,節(jié)點數(shù)及鏈路段數(shù)都明顯減少,求解的效率大幅度提高,能夠滿足工程實際的應(yīng)用需求。

[1]張梅，談俊忠.基于GIS的主干光纜路由敷設(shè)條件評價研究[J].中國新通信，2015.

[2]蘇輝，劉越男.光纖接入網(wǎng)規(guī)劃與優(yōu)化中GIS和ES技術(shù)的整合[J].電信技術(shù)，2015.

[3]蘇輝，吳立新，陸鎮(zhèn)虹，等.基于GIS和ES的光纖接入網(wǎng)規(guī)劃系統(tǒng)的設(shè)計和實現(xiàn)[J].地理學(xué)與國土研究，2014.

[4]李樹平.光接入網(wǎng)技術(shù)與設(shè)計方法探討[J].科技創(chuàng)新導(dǎo)報，2015.

圖4 訪問某個藏區(qū)Web站點產(chǎn)生多個TCP 流的示例

1.2 指紋信息定義

本文將藏區(qū)內(nèi)Web站點的指紋信息定義為能夠明確區(qū)分本站點與其他Web站點的標識特征集合，用FPWeb標識。根據(jù)1.1節(jié)中的相關(guān)特征的描述和分析，F(xiàn)P此處被定義為:

FPWeb=（Pair，Lable，Order，Num）

其中，Pair、Lable、Order和Num分別表示W(wǎng)eb站點域名與IP地址對、HTTP Response報頭字段特殊標識、HTTP Response報頭字段順序和 訪問Web站點是產(chǎn)的TCP流數(shù)量。

2 測試結(jié)果

第1.2節(jié)所提出的藏區(qū)Web站點指紋信息定義，本文對常見的10個區(qū)內(nèi)Web站點的指紋信息進行了提取，結(jié)果如表1所示。

可以看出，此10個Web站點的域名分別僅對應(yīng)唯一的IP地址。部分Web站點返回的HTTP Response報頭字段中沒有特殊標識ETag（即ETag:NULL）。HTTP Response報頭字段順序也不盡相同，其中C為“Content-Type”字段，S為“Server”，D代表“Date”字段，而且所產(chǎn)的TCP流的數(shù)目也有差異。因此，將這些特征構(gòu)成的集合作為Web站點指紋信息是合理的，并且可將該指紋信息應(yīng)用于初步甄別Web站點是否被冒充或偽造。

表1 10個藏區(qū)Web站點的指紋信息

3 結(jié)論

本文針對藏區(qū)內(nèi)Web站點安全，基于Web站點域名DNS解析記錄、HTTP Response報頭字段特殊標識、字段順序和TCP流數(shù)量四個特征定義了藏區(qū)內(nèi)Web站點指紋信息并進行了相關(guān)測試，測試結(jié)果表現(xiàn)良好。下一步將提取其他藏區(qū)內(nèi)Web站點指紋信息、建立指紋信息庫，提高指紋信息準確度，尋找更準確特征等方面展開研究。

參考文獻:

[1]Hypertext Transfer Protocol -- HTTP/1.1 [EB/OL]. [1999-06].http://www.ietf.org/rfc/rfc2616.

[2]Dshield[EB/OL].[2016-06-21].http://www.dshield.org/ httpheaders/?header=Content-Type.

西藏民族大學(xué)2016年大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目《藏區(qū)Web站點指紋信息提取研究》; 西藏自治區(qū)高校青年教師創(chuàng)新支持計劃項目（QCZ2016-41）; 藏區(qū)網(wǎng)絡(luò)空間安全與輿情智能監(jiān)管科研創(chuàng)新團隊建設(shè)項目。