胡朝舉++張和琳

摘 要：隨著信息通信行業(yè)的快速發(fā)展，光纖網(wǎng)絡(luò)日益復(fù)雜，為了實現(xiàn)更加快速高效的光纖路由規(guī)劃，結(jié)合Dijkstra算法以起始點為中心向外層擴展的特點和廣度優(yōu)先搜索算法的遍歷策略，提出一種最短路徑計算算法，并完成算法的并行設(shè)計與實驗分析。通過在Spark平臺上對所提出的算法進行實驗，并與傳統(tǒng)的Dijkstra算法比較，結(jié)果表明該算法高效可行，達到了設(shè)計要求。

關(guān)鍵詞：光纖路由；最短路徑；云平臺；Spark

DOIDOI：10.11907/rjdk.1511307

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號文章編號：16727800（2015）012004603

作者簡介作者簡介：胡朝舉（1963-），男，河北滄州人，碩士，華北電力大學(xué)控制與計算機工程學(xué)院副教授、碩士生導(dǎo)師，研究方向為數(shù)據(jù)庫、信息安全；張和琳（1990-），男，福建福州人，華北電力大學(xué)控制與計算機工程學(xué)院碩士研究生，研究方向為數(shù)據(jù)庫與信息系統(tǒng)。

0 引言

光纜傳輸系統(tǒng)是一種高效、可靠、大容量的通信手段，除了衛(wèi)星通信方式外，其它涉及到地面段通信手段的數(shù)據(jù)傳輸基本完全依賴光纜傳輸網(wǎng)絡(luò)[1]。目前，隨著光纖網(wǎng)絡(luò)日漸復(fù)雜，光纖資源作為底層的連接資源，如何實現(xiàn)對該類資源的管理和調(diào)度已經(jīng)成為優(yōu)化資源配置、節(jié)約建設(shè)成本的關(guān)鍵問題。因此，在數(shù)據(jù)處理量日趨龐大的今天，傳統(tǒng)的最短路徑算法已經(jīng)無法滿足高效率、快節(jié)奏的要求。

隨著云計算的提出及發(fā)展，其運用領(lǐng)域越來越廣，其中效率最高的當(dāng)屬Spark。Spark支持內(nèi)存計算、多迭代批量處理、即席查詢、流處理和圖計算等多種范式[2]，它的內(nèi)存計算框架適合各種迭代算法和交互式數(shù)據(jù)分析，能夠提升大數(shù)據(jù)處理的實時性和準(zhǔn)確性，為并行求解光纖路由最短路徑提供了有效途徑。

本文在探討光纖業(yè)務(wù)需求的基礎(chǔ)上，抽象出數(shù)學(xué)模型，提出基于Spark平臺的光纖路由最短路徑的具體算法，并進行實驗分析。

1 基本概念

1.1 光纖路由

在光纖網(wǎng)絡(luò)高速發(fā)展的今天，作為光纖網(wǎng)絡(luò)重要載體的光纜及光纖，其應(yīng)用范圍越來越廣泛。在光纖網(wǎng)絡(luò)的基礎(chǔ)建設(shè)中，光纖路由規(guī)劃是必不可少的環(huán)節(jié)，規(guī)劃的優(yōu)劣程度直接影響建設(shè)成本。光纖路由的載體是地下井管道、電桿等基礎(chǔ)設(shè)施，光纖路由規(guī)劃就是根據(jù)組網(wǎng)需求在兩節(jié)點間鋪設(shè)一條光纜，并根據(jù)已有的光纜載體資源使用情況，尋找出一條合適的鋪設(shè)路徑，實現(xiàn)光纖資源的預(yù)占[3]。因此在光纜鋪設(shè)中，最重要的環(huán)節(jié)是為光纜在地下井管道和電桿中規(guī)劃一條合適的路由。

圖1展示了光纖路由拓?fù)浼耙粭l完整的光纖路由，其中用黑體線將起點和終點連接起來的為最優(yōu)光纖路由。因此可以將光纖路由規(guī)劃問題抽象為圖論問題。

圖1 光纖路由拓?fù)鋱D

1.2 圖論

圖論（Graph Theory）是數(shù)學(xué)的一個分支，以圖形為研究對象，研究點與線之間關(guān)系，它是由若干給定的點及連接兩點的線所構(gòu)成的圖形，對于這種圖形重點關(guān)注有多少個點和哪些結(jié)點之間有線連接，連接兩點之間的線表示相應(yīng)兩個結(jié)點之間的某種關(guān)系[4]。

1.3 Dijkstra算法

Dijkstra算法是典型的最短路徑算法，是一種用于尋找給定加權(quán)圖中單源點到其余各頂點的最短路徑算法，其主要特點是以起始點為中心向外層擴展，直到終點為止[5]。

Dijkstra算法的基本思想如下：從任意結(jié)點v到任意結(jié)點u的最短路徑共有兩種可能：一是直接從v到u，二是從v經(jīng)過一個或若干個點到u。因此，在圖G=（V，E）中，如果存在一條從i到j(luò)的最短路徑（Vi，…，Vk，Vj），Vk是Vj前面的一個點，那么（Vi，…，Vk）也必定是從i到k的最短路徑。為求出最短路徑，Dijkstra提出以最短路徑長度遞增逐次生成最短路徑的算法。

1.4 廣度優(yōu)先搜索算法

廣度優(yōu)先搜索算法是最簡單的圖搜索算法之一，是連通圖的一種遍歷策略，也是許多重要的圖算法原型。給定圖G=（V，E）和一個可以識別的源節(jié)點s，對圖G中的點進行系統(tǒng)性探索發(fā)現(xiàn)可以從源節(jié)點s到達所有節(jié)點。該算法能夠計算從源節(jié)點s到每個可到達節(jié)點的距離，同時生成一棵“廣度優(yōu)先搜索樹”[6]。廣度優(yōu)先搜索算法的執(zhí)行方法主要是：從任意節(jié)點s出發(fā)，先遍歷與s相鄰的m個節(jié)點（k1，k2，…，km），然后再遍歷與ki相鄰的節(jié)點。廣度優(yōu)先搜索基于其搜的特性，適用于分布式計算。

1.5 Spark模型

Spark中最重要的核心概念是彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets），簡稱RDD，是Spark的最基本抽象，是對分布式內(nèi)存的抽象使用，實現(xiàn)了以操作本地集合的方式來操作分布式數(shù)據(jù)集[7]。其實際數(shù)據(jù)分布存儲于一批機器內(nèi)存中，相對于MapReduce，Spark是直接處理內(nèi)存，而不是使用大量的磁盤IO來操作文件，因此，相比迭代運算和迭代算法，效率有很大的提升。RDD實現(xiàn)了map、filter、join、flatMap等數(shù)據(jù)集操作方法，在容錯性方面有所提高。

Spark通過轉(zhuǎn)換操作，可以將一個RDD轉(zhuǎn)換為另外一個RDD，然后這個RDD還可以繼續(xù)轉(zhuǎn)換成另外一個RDD，且這個過程是并行、分布式的。Spark在實現(xiàn)迭代時，由于中間結(jié)果無需進行IO操作，而且能進行多次的RDD轉(zhuǎn)換操作。因此，Spark迭代計算時速度相較于MapReduce顯著提高。

2 算法設(shè)計

傳統(tǒng)最短路徑算法有Dijkstra、Floyd、Bellman-Ford和SPFA等，以其算法簡單且高效曾流行于一時，但是對于圖的信息量越來越大的今天，傳統(tǒng)的最短路徑算法不再適用于大圖計算。本文主要結(jié)合Dijkstra算法和廣度優(yōu)先搜索的思想及特性，提出一個基于Spark云計算平臺的數(shù)據(jù)結(jié)構(gòu)及算法。

2.1 數(shù)據(jù)模型構(gòu)建

光纖路由規(guī)劃問題，其可以抽象為圖模型，對于一個管線網(wǎng)絡(luò)，可以看成是一個無向圖的問題，對于規(guī)模比較小的問題用傳統(tǒng)的最短路徑算法來求解，如Dijkstra算法。

在傳統(tǒng)的最短路徑算法中，對于有n個結(jié)點的圖G=（V，E），主要存儲結(jié)構(gòu)是一個n×n的鄰接矩陣及兩個1×n的距離矩陣和前驅(qū)矩陣。在光纖路由圖模型中任意一個結(jié)點v和其它結(jié)點u相鄰的數(shù)量m遠(yuǎn)小于節(jié)點個數(shù)n，因此若以n×n的鄰接矩陣W=[w（i，j）]存儲邊和點，則W類似一個稀疏矩陣。因此若使用三元組存儲則將大大減少內(nèi)存使用。圖2為n為8的無向圖。

以三元組表示圖G的邊和節(jié)點關(guān)系：E<1，2，3>，E<1，3，6>，E<2，1，3>，E<2，4，6>，E<3，1，6>，E<3，4，1>，E<4，2，6>，E<4，3，1>，E<4，5，2>，E<5，4，2>，E<5，6，5>，E<5，7，3>，E<6，5，5>，E<6，8，3>，E<7，5，3>，E<7，8，7>，E<8，6，3>，E<8，7，7>G8的鄰接矩陣和三元組相比，當(dāng)節(jié)點數(shù)較大時，三元組的存儲結(jié)果明顯比鄰接矩陣節(jié)省空間。

當(dāng)進行最短路徑計算時，若有源節(jié)點s，定義節(jié)點二元組V>，其中id為結(jié)點編號，len為該結(jié)點到結(jié)點s的最短路徑，prev為其最短路徑前驅(qū)節(jié)點；邊三元組T，即T<>，>，len>，用來計算從s通過結(jié)點v1再到節(jié)點v2的距離，每次計算后同時更新T和V。

2.2 算法實現(xiàn)

結(jié)合Dijkstra算法和廣度優(yōu)先搜索算法的思想，以及前述設(shè)計的數(shù)據(jù)模型，算法流程具體如下：

（1）初始化邊和結(jié)點關(guān)系集合Edge={E1，E2，…，Em}，其中Ei=[vsrc，vdst，len]，表示從節(jié)點v1到節(jié)點v2有邊，且長度為len；初始化節(jié)點二元組集合Vertex={V1，V2，…，Vn}，其中 Vi=[vi，[len，prev]]，且len=∞，prev=-1，表示無前驅(qū)節(jié)點；初始化三元組Triplet={T1，T2，…，Tm}，Ti=[Vsrc，Vdst，len]即Ti=[[vsrc，[len1，prev1]]，[vdst，[len2，prev2]]，len]，初始化源節(jié)點Vs相關(guān)元素，更新Vertex和Triplet中，設(shè)置len=0；初始化活動集合Alive=Vertex。

（2）若集合Alive為空，則結(jié)束計算。否則，合并活動集合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節(jié)點，更新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 實驗驗證及分析

文中結(jié)合Scala語言、Spark編程模式并結(jié)合廣度優(yōu)先搜索算法和Dijkstra算法的思想，設(shè)計一個基于Spark平臺的光纖路由規(guī)劃并行最短路徑算法。實驗搭建的Spark集群在standalone模式下運行，有1個Master節(jié)點和8個Worker節(jié)點，同時Master節(jié)點是namenode節(jié)點，其它的worker是datanode，并通過高速交換機形成一個192.168.0.1網(wǎng)段的內(nèi)部網(wǎng)絡(luò)。Spark集群每個節(jié)點配置為雙核，2G內(nèi)存容量，操作系統(tǒng)為Ubuntu12.04。實驗集群在無其它任務(wù)運行的條件下進行。

本實驗主要目標(biāo)是測試上述設(shè)計算法的計算性能，在不同Worker節(jié)點個數(shù)下的計算性能，以及和Dijkstra算法進行比較。實驗用Spark計算框架支持Scala、Python和Java多種語言編程，由于Spark內(nèi)核是采用Scala語言編寫，所以本實驗選擇使用Scala語言編寫實現(xiàn)并行最短路徑算法。

3.1 正確性驗證

算法正確性驗證采用單機環(huán)境，整個基于Spark的最短路徑算法程序是由Scala語言來編寫實現(xiàn)的。為了驗證算法的正確性和計算過程，實驗采用數(shù)據(jù)為圖2中展示的一個結(jié)點個數(shù)為8邊個數(shù)為9的無向圖。初始化結(jié)點1的數(shù)據(jù)為（1，（0，-1）），其它結(jié)點初始化為（id，（∞，-1），其運行步驟如表1所示。

表1中的活動結(jié)點狀態(tài)列供下一步驟使用，通過活動節(jié)點就可知道下一步要更新的結(jié)點及要計算的節(jié)點，由表1的步驟5可看出算法的運行結(jié)果是正確的。步驟0為通過計算源節(jié)點1的相鄰點，求得從1到2的距離為3及前驅(qū)節(jié)點為1，從1到3的距離為6及前驅(qū)節(jié)點為1；步驟1更新節(jié)點2和3，并分別計算出自身到其相鄰節(jié)點4的距離；步驟2通過合并活動節(jié)點4的結(jié)果并更新節(jié)點4。其計算過程與算法所設(shè)計的過程完全一致。

3.2 集群運行

集群環(huán)境下，實驗用Spark集群啟動8個Worker節(jié)點，測試用數(shù)據(jù)存儲在HDFS文件系統(tǒng)中。利用Spark集群測試在不同節(jié)點個數(shù)下的運行效率及在普通環(huán)境下Dijkstra算法的效率。

在圖的復(fù)雜度較低，即圖的邊數(shù)較少時，基于Spark的最短路徑算法在不同節(jié)點個數(shù)的集群下其運行時間比較接近，8個節(jié)點的集群并不比1個節(jié)點的集群有多少優(yōu)勢；但隨著圖的邊數(shù)增加，8個節(jié)點的集群的優(yōu)勢慢慢得到體現(xiàn)，運行時間相對于其它的集群明顯縮短，且運行時間變化不明顯。

圖3 不同結(jié)點下運行對比圖

圖4是傳統(tǒng)的單源最短路徑算法——Dijkstra算法的運行時間當(dāng)圖的邊數(shù)少時，其運行效率很高，運行時間為納秒級，但隨著圖的邊數(shù)增加，其運行時間開始越來越長，特別是在邊數(shù)1W以上后，其運行時間呈指數(shù)型增長，而且在實驗過程中，當(dāng)邊條數(shù)超過5W時，程序?qū)⒊霈F(xiàn)OutOfMemoryError錯誤。

通過圖3和圖4的對比可知，對于復(fù)雜度較低的圖傳統(tǒng)的最短路徑算法的運行效率高于基于Spark的最短路徑算法；對于復(fù)雜度較高的圖，基于Spark的最短路徑算法的運行效率比傳統(tǒng)的最短路徑算法高。

圖4 Dijkstra算法運行效果

4 結(jié)語

本文基于光纖路由規(guī)劃問題，分析光纖路由的結(jié)構(gòu)，設(shè)計了一種基于Spark云平臺的最短路徑并行算法，并在不同節(jié)點個數(shù)的集群下對算法的運行時間進行了測試。實驗結(jié)果證明了算法的正確性、可行性和高效性，能夠快速解決規(guī)模較大的光纖路由規(guī)劃問題。

參考文獻參考文獻：

[1] 郭利超，馬朝霞，周云鋒，等.通信光纜監(jiān)測管理一體化平臺設(shè)計與實現(xiàn)[J].計算機測量與控制，2012（8）：22132216.

[2] 葉飛，李莉，江濤，等.基于Hadoop的免疫規(guī)劃管理信息平臺研究[J].中國管理信息化，2015（8）：8687.

[3] 李楠.網(wǎng)絡(luò)優(yōu)化技術(shù)在光纜路由自動設(shè)計中的應(yīng)用[D].北京：北京郵電大學(xué)，2011.

[4] REINHARD DIESTEL.圖論（第4版） [M].北京：高等教育出版社，2013.

[5] 江家寶，鄭尚志.基于PSO算法的OSPF多約束路由策略[J].軟件導(dǎo)刊，2015，14（6）：7679.

（責(zé)任編輯：陳福時）