基于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）; 藏区网络空间安全与舆情智能监管科研创新团队建设项目。