基于GIS的光接安全入網主干光纜路由優化模型和算法研究

◆王 璇

（四川通信科研規劃設計有限責任公司 四川 610000）

基于GIS的光接安全入網主干光纜路由優化模型和算法研究

◆王 璇

（四川通信科研規劃設計有限責任公司 四川 610000）

本文分別介紹了星形、環形及線形三種結構的光接入網主干光纜路由的優化模型及算法，這種主干光纜路由數學模型及優化算法均是在MapInfo GIS 平臺構建的，通過減少鏈路段的數目及搜索的節點有效的提高了算法的效率，具有較好的實用性。

GIS; 光接入網; 主干光纜路由; 優化模型

0 前言

光接入網規劃中主干光纜路由優化是重要的工作內容，直接影響著光接入網的建設投資即網絡生存性。目前來說，光接入網主干光纜路由主要有星形、環形及線形三種結構，本文主要就光接入網主干光纜路由優化的模型及算法進行簡單的探討分析。

1 主干光纜路由的數學模型

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

圖1 主干光纜路由的模型

其中Rlen、Rcos、Rcov分別指的是路由的長度、投資及覆蓋度，E指的是網絡中的第i條鏈路段,Li則指的是第i條鏈路段的長度，R指的是光纜的路由,Cf、Cp、Cp表示路由上光纜的投資、管道投資及人孔投資，NS指的是路由目標點集，N1、N2分別指的是主干光纜覆蓋的規劃小區數及該業務節點覆蓋的總規劃小區數目。

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

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

圖2 單目標模型

2 主干光纜路由優化的算法設計

2.1 主干光纜路由的拓撲結構

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

星型拓撲結構路由優化時需要分別搜索業務節點到每個目標點之間的最佳的路徑，因此星型結構路由優化實際上求解目標點與業務節點之間的最有路徑，實際的優化過程中，經常會出現路由之間鏈路重復的問題，因此相關設計人員需要根據實際的優化設計要求采取對應的控制措施，允許重復時則不需要對使用過的路段進行標示，如果不允許重復則需要進行禁用標識。

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

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

2.2 路由優化算法

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

Dijkstra算法應用的關鍵在于下一個擴展節點及數據結構的選擇，一般情況下，BFS（best-first-search）、LIFO（last-in-first-out）、FIFO（first-in -first -out）是三種應用比較多的擴展節點選擇方法，哈希散列和隊列、堆棧等等是常見的數據結構。

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

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

3 結束語

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

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

[2]蘇輝，劉越男.光纖接入網規劃與優化中GIS和ES技術的整合[J].電信技術，2015.

[3]蘇輝，吳立新，陸鎮虹，等.基于GIS和ES的光纖接入網規劃系統的設計和實現[J].地理學與國土研究，2014.

[4]李樹平.光接入網技術與設計方法探討[J].科技創新導報，2015.

圖4 訪問某個藏區Web站點產生多個TCP 流的示例

1.2 指紋信息定義

本文將藏區內Web站點的指紋信息定義為能夠明確區分本站點與其他Web站點的標識特征集合，用FPWeb標識。根據1.1節中的相關特征的描述和分析，FP此處被定義為:

FPWeb=（Pair，Lable，Order，Num）

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

2 測試結果

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

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

表1 10個藏區Web站點的指紋信息

3 結論

本文針對藏區內Web站點安全，基于Web站點域名DNS解析記錄、HTTP Response報頭字段特殊標識、字段順序和TCP流數量四個特征定義了藏區內Web站點指紋信息并進行了相關測試，測試結果表現良好。下一步將提取其他藏區內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.

西藏民族大學2016年大學生創新創業訓練計劃項目《藏區Web站點指紋信息提取研究》; 西藏自治區高校青年教師創新支持計劃項目（QCZ2016-41）; 藏區網絡空間安全與輿情智能監管科研創新團隊建設項目。