|
摘 要：随着信息通信行业的快速发展，光纤网络日益复杂，为了实现更加快速高效的光纤路由规划，结合Dijkstra算法以起始点为中心向外层扩展的特点和广度优先搜索算法的遍历策略，提出一种最短路径计算算法，并完成算法的并行设计与实验分析。通过在Spark平台上对所提出的算法进行实验，并与传统的Dijkstra算法比较，结果表明该算法高效可行，达到了设计要求。 关键词：光纤路由；最短路径；云平台；Spark DOIDOI：10.11907/rjdk.1511307 中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2015）012004603 作者简介作者简介：胡朝举（1963-），男，河北沧州人，硕士，华北电力大学控制与计算机工程学院副教授、硕士生导师，研究方向为数据库、信息安全；张和琳（1990-），男，福建福州人，华北电力大学控制与计算机工程学院硕士研究生，研究方向为数据库与信息系统。 0 引言 光缆传输系统是一种高效、可靠、大容量的通信手段，除了卫星通信方式外，其它涉及到地面段通信手段的数据传输基本完全依赖光缆传输网络[1]。目前，随着光纤网络日渐复杂，光纤资源作为底层的连接资源，如何实现对该类资源的管理和调度已经成为优化资源配置、节约建设成本的关键问题。因此，在数据处理量日趋庞大的今天，传统的最短路径算法已经无法满足高效率、快节奏的要求。 随着云计算的提出及发展，其运用领域越来越广，其中效率最高的当属Spark。Spark支持内存计算、多迭代批量处理、即席查询、流处理和图计算等多种范式[2]，它的内存计算框架适合各种迭代算法和交互式数据分析，能够提升大数据处理的实时性和准确性，为并行求解光纤路由最短路径提供了有效途径。 本文在探讨光纤业务需求的基础上，抽象出数学模型，提出基于Spark平台的光纤路由最短路径的具体算法，并进行实验分析。 1 基本概念 1.1 光纤路由 在光纤网络高速发展的今天，作为光纤网络重要载体的光缆及光纤，其应用范围越来越广泛。在光纤网络的基础建设中，光纤路由规划是必不可少的环节，规划的优劣程度直接影响建设成本。光纤路由的载体是地下井管道、电杆等基础设施，光纤路由规划就是根据组网需求在两节点间铺设一条光缆，并根据已有的光缆载体资源使用情况，寻找出一条合适的铺设路径，实现光纤资源的预占[3]。因此在光缆铺设中，最重要的环节是为光缆在地下井管道和电杆中规划一条合适的路由。 图1展示了光纤路由拓扑及一条完整的光纤路由，其中用黑体线将起点和终点连接起来的为最优光纤路由。因此可以将光纤路由规划问题抽象为图论问题。 图1 光纤路由拓扑图 1.2 图论 图论（Graph Theory）是数学的一个分支，以图形为研究对象，研究点与线之间关系，它是由若干给定的点及连接两点的线所构成的图形，对于这种图形重点关注有多少个点和哪些结点之间有线连接，连接两点之间的线表示相应两个结点之间的某种关系[4]。 1.3 Dijkstra算法 Dijkstra算法是典型的最短路径算法，是一种用于寻找给定加权图中单源点到其余各顶点的最短路径算法，其主要特点是以起始点为中心向外层扩展，直到终点为止[5]。 Dijkstra算法的基本思想如下：从任意结点v到任意结点u的最短路径共有两种可能：一是直接从v到u，二是从v经过一个或若干个点到u。因此，在图G=（V，E）中，如果存在一条从i到j的最短路径（Vi，…，Vk，Vj），Vk是Vj前面的一个点，那么（Vi，…，Vk）也必定是从i到k的最短路径。为求出最短路径，Dijkstra提出以最短路径长度递增逐次生成最短路径的算法。 1.4 广度优先搜索算法 广度优先搜索算法是最简单的图搜索算法之一，是连通图的一种遍历策略，也是许多重要的图算法原型。给定图G=（V，E）和一个可以识别的源节点s，对图G中的点进行系统性探索发现可以从源节点s到达所有节点。该算法能够计算从源节点s到每个可到达节点的距离，同时生成一棵“广度优先搜索树”[6]。广度优先搜索算法的执行方法主要是：从任意节点s出发，先遍历与s相邻的m个节点（k1，k2，…，km），然后再遍历与ki相邻的节点。广度优先搜索基于其搜的特性，适用于分布式计算。 1.5 Spark模型 Spark中最重要的核心概念是弹性分布式数据集（Resilient Distributed Datasets），简称RDD，是Spark的最基本抽象，是对分布式内存的抽象使用，实现了以操作本地集合的方式来操作分布式数据集[7]。其实际数据分布存储于一批机器内存中，相对于MapReduce，Spark是直接处理内存，而不是使用大量的磁盘IO来操作文件，因此，相比迭代运算和迭代算法，效率有很大的提升。RDD实现了map、filter、join、flatMap等数据集操作方法，在容错性方面有所提高。 Spark通过转换操作，可以将一个RDD转换为另外一个RDD，然后这个RDD还可以继续转换成另外一个RDD，且这个过程是并行、分布式的。Spark在实现迭代时，由于中间结果无需进行IO操作，而且能进行多次的RDD转换操作。因此，Spark迭代计算时速度相较于MapReduce显著提高。 2 算法设计 传统最短路径算法有Dijkstra、Floyd、Bellman-Ford和SPFA等，以其算法简单且高效曾流行于一时，但是对于图的信息量越来越大的今天，传统的最短路径算法不再适用于大图计算。本文主要结合Dijkstra算法和广度优先搜索的思想及特性，提出一个基于Spark云计算平台的数据结构及算法。 2.1 数据模型构建 光纤路由规划问题，其可以抽象为图模型，对于一个管线网络，可以看成是一个无向图的问题，对于规模比较小的问题用传统的最短路径算法来求解，如Dijkstra算法。 在传统的最短路径算法中，对于有n个结点的图G=（V，E），主要存储结构是一个n×n的邻接矩阵及两个1×n的距离矩阵和前驱矩阵。在光纤路由图模型中任意一个结点v和其它结点u相邻的数量m远小于节点个数n，因此若以n×n的邻接矩阵W=[w（i，j）]存储边和点，则W类似一个稀疏矩阵。因此若使用三元组存储则将大大减少内存使用。图2为n为8的无向图。 以三元组表示图G的边和节点关系：E，E，E，E，E，E，E，E，E，E，E，E，E，E，E，E，E，EG8的邻接矩阵和三元组相比，当节点数较大时，三元组的存储结果明显比邻接矩阵节省空间。 当进行最短路径计算时，若有源节点s，定义节点二元组V>，其中id为结点编号，len为该结点到结点s的最短路径，prev为其最短路径前驱节点；边三元组T，即T>，>，len>，用来计算从s通过结点v1再到节点v2的距离，每次计算后同时更新T和V。 2.2 算法实现 结合Dijkstra算法和广度优先搜索算法的思想，以及前述设计的数据模型，算法流程具体如下： （1）初始化边和结点关系集合Edge={E1，E2，…，Em}，其中Ei=[vsrc，vdst，len]，表示从节点v1到节点v2有边，且长度为len；初始化节点二元组集合Vertex={V1，V2，…，Vn}，其中 Vi=[vi，[len，prev]]，且len=∞，prev=-1，表示无前驱节点；初始化三元组Triplet={T1，T2，…，Tm}，Ti=[Vsrc，Vdst，len]即Ti=[[vsrc，[len1，prev1]]，[vdst，[len2，prev2]]，len]，初始化源节点Vs相关元素，更新Vertex和Triplet中，设置len=0；初始化活动集合Alive=Vertex。 （2）若集合Alive为空，则结束计算。否则，合并活动集合Alive，若在Alive中对于任意的Vi和Vj，若有vi=vj，则合并Vi和Vj，prev=min{previ，prevj}，len=min{leni，lenj}，combine（Vi，Vj）Vk=[vi，[len，prev]]。 （3）读取Alive节点，更新Vertex。对于Alive和Vertex，Vv=min{Va，Vv|va=vv}。 （4）生成新活动集合Alive。新建空集Alive，集合M={Ti，Ti.vsrc∈{Ta.va，Ta∈Alive}}，对于Ti，若newlen=len1+len 3 实验验证及分析 文中结合Scala语言、Spark编程模式并结合广度优先搜索算法和Dijkstra算法的思想，设计一个基于Spark平台的光纤路由规划并行最短路径算法。实验搭建的Spark集群在standalone模式下运行，有1个Master节点和8个Worker节点，同时Master节点是namenode节点，其它的worker是datanode，并通过高速交换机形成一个192.168.0.1网段的内部网络。Spark集群每个节点配置为双核，2G内存容量，操作系统为Ubuntu12.04。实验集群在无其它任务运行的条件下进行。 本实验主要目标是测试上述设计算法的计算性能，在不同Worker节点个数下的计算性能，以及和Dijkstra算法进行比较。实验用Spark计算框架支持Scala、Python和Java多种语言编程，由于Spark内核是采用Scala语言编写，所以本实验选择使用Scala语言编写实现并行最短路径算法。 3.1 正确性验证 算法正确性验证采用单机环境，整个基于Spark的最短路径算法程序是由Scala语言来编写实现的。为了验证算法的正确性和计算过程，实验采用数据为图2中展示的一个结点个数为8边个数为9的无向图。初始化结点1的数据为（1，（0，-1）），其它结点初始化为（id，（∞，-1），其运行步骤如表1所示。 表1中的活动结点状态列供下一步骤使用，通过活动节点就可知道下一步要更新的结点及要计算的节点，由表1的步骤5可看出算法的运行结果是正确的。步骤0为通过计算源节点1的相邻点，求得从1到2的距离为3及前驱节点为1，从1到3的距离为6及前驱节点为1；步骤1更新节点2和3，并分别计算出自身到其相邻节点4的距离；步骤2通过合并活动节点4的结果并更新节点4。其计算过程与算法所设计的过程完全一致。 3.2 集群运行 集群环境下，实验用Spark集群启动8个Worker节点，测试用数据存储在HDFS文件系统中。利用Spark集群测试在不同节点个数下的运行效率及在普通环境下Dijkstra算法的效率。 在图的复杂度较低，即图的边数较少时，基于Spark的最短路径算法在不同节点个数的集群下其运行时间比较接近，8个节点的集群并不比1个节点的集群有多少优势；但随着图的边数增加，8个节点的集群的优势慢慢得到体现，运行时间相对于其它的集群明显缩短，且运行时间变化不明显。 图3 不同结点下运行对比图 图4是传统的单源最短路径算法——Dijkstra算法的运行时间当图的边数少时，其运行效率很高，运行时间为纳秒级，但随着图的边数增加，其运行时间开始越来越长，特别是在边数1W以上后，其运行时间呈指数型增长，而且在实验过程中，当边条数超过5W时，程序将出现OutOfMemoryError错误。 通过图3和图4的对比可知，对于复杂度较低的图传统的最短路径算法的运行效率高于基于Spark的最短路径算法；对于复杂度较高的图，基于Spark的最短路径算法的运行效率比传统的最短路径算法高。 图4 Dijkstra算法运行效果 4 结语 本文基于光纤路由规划问题，分析光纤路由的结构，设计了一种基于Spark云平台的最短路径并行算法，并在不同节点个数的集群下对算法的运行时间进行了测试。实验结果证明了算法的正确性、可行性和高效性，能够快速解决规模较大的光纤路由规划问题。 参考文献参考文献： [1] 郭利超，马朝霞，周云锋，等.通信光缆监测管理一体化平台设计与实现[J].计算机测量与控制，2012（8）：22132216. [2] 叶飞，李莉，江涛，等.基于Hadoop的免疫规划管理信息平台研究[J].中国管理信息化，2015（8）：8687. [3] 李楠.网络优化技术在光缆路由自动设计中的应用[D].北京：北京邮电大学，2011. [4] REINHARD DIESTEL.图论（第4版） [M].北京：高等教育出版社，2013. [5] 江家宝，郑尚志.基于PSO算法的OSPF多约束路由策略[J].软件导刊，2015，14（6）：7679. （责任编辑：陈福时）
| 
