面向云計(jì)算框架的最大流算法實(shí)現(xiàn)研究

鄧華富

(四川省 綿陽財(cái)經(jīng)學(xué)校，四川 綿陽 621000)

0 引 言

目前，計(jì)算機(jī)已經(jīng)成為研究各類問題的有效工具之一.例如，在交通路徑規(guī)劃領(lǐng)域，具備最大可增流量的出行路徑是實(shí)現(xiàn)交通科學(xué)誘導(dǎo)、緩解擁堵的基礎(chǔ);而在通信等領(lǐng)域，最大可增流路徑是實(shí)現(xiàn)有效路由尋址、避免數(shù)據(jù)擁塞的前提［1－2］.該類問題具有通用的數(shù)學(xué)模型，即從網(wǎng)絡(luò)中搜索任意2 個(gè)結(jié)點(diǎn)之間的具有最大可增加流量的路徑.圖論中將這樣的問題放在抽象的賦權(quán)圖中研究.賦權(quán)圖分為有向圖和無向圖，由結(jié)點(diǎn)、邊(有向圖中稱弧)和每條邊對(duì)應(yīng)的權(quán)值組成.權(quán)值一般代表邊上能通過某種物理量的最大值，如運(yùn)輸費(fèi)用、尋址代價(jià)等等，它與邊的自身性質(zhì)有關(guān).在此基礎(chǔ)上，可以計(jì)算任意2 個(gè)結(jié)點(diǎn)之間在權(quán)值約束下可增加流量最大的路徑，該路徑稱為最大可增路徑.將交通流或通信數(shù)據(jù)流按照最大可增路分配，能夠平衡網(wǎng)絡(luò)負(fù)載，減少因某局部區(qū)域擁堵而造成的網(wǎng)絡(luò)其他資源閑置，進(jìn)而提高網(wǎng)絡(luò)利用率［3］.然而，隨著科學(xué)技術(shù)的飛速發(fā)展，需要考察的路網(wǎng)規(guī)模越來越大，單機(jī)計(jì)算時(shí)間也超過了可以接受的限度，這已經(jīng)影響到多種實(shí)際問題的實(shí)時(shí)計(jì)算與決策.而近年興起的云計(jì)算思路與模型，為上述問題提供了一個(gè)可行的解決方案.基于此，本研究從最大流理論出發(fā)，提出了一種面向云計(jì)算框架的最大可增路分布式計(jì)算方式，并在開源云平臺(tái)——Hadoop 上加以實(shí)現(xiàn).

1 最大流理論及可增路計(jì)算方法

一般而言，抽象路網(wǎng)由有向圖N(V，L，C)表示.其中，結(jié)點(diǎn)集為V，邊集為L，分別代表路口和路段.以c(a)表示a 邊允許通過的最大流量，C 表示所有路段最大流量集合.稱起始結(jié)點(diǎn)為源結(jié)點(diǎn)，終止結(jié)點(diǎn)為匯結(jié)點(diǎn).根據(jù)圖論中的最大流理論以及上述定義，問題可歸結(jié)為:在網(wǎng)絡(luò)的某源—匯結(jié)點(diǎn)對(duì)間尋求最大可增路.理論上，可增路是指滿足以下條件的路徑P:對(duì)任意邊，若是P 的正向邊，則有△f(a)= c(a)－f(a)＞0;若a 是P 的反向邊，則有△f(a)= f(a)＞0.其中，f(a)是路段a 的當(dāng)前流量值，△f(a)稱為路段a 的可增流.對(duì)與某一對(duì)源— 匯結(jié)點(diǎn)，若存在某條可增路，則可以沿該可增路將網(wǎng)絡(luò)總流量增加△f(a).這也是可增路和可增流名稱的來源.進(jìn)一步，定義△f(P)= mina∈P△f(a)為路徑P 的可增流.在所有可增路中，具有最大可增流的路徑就是需要搜索的最大可增路.圖1 給出了一個(gè)簡單的示例.網(wǎng)絡(luò)中每條有向邊上括號(hào)里面的值表示該邊的最大流量，而括號(hào)之前的值代表當(dāng)前流量(即當(dāng)前交通流量).圖1(A)中虛線所示路徑即為一條可增路.該路徑上每條邊的可增流△f 均已標(biāo)明，顯然路徑可增流△f(P)= mina∈P△f(a)= min{6，6，3}=3.圖1(B)中虛線所示路徑為含有反向邊(v2-v3)的可增路，不屬于本研究考慮的范圍，予以排除.

對(duì)于理論上的最大流問題，已有一系列經(jīng)典的

圖1 網(wǎng)絡(luò)可增路示意圖

搜索算法可以很好地加以解決，例如Ford-Fulkerson算法［3］.然而，對(duì)于僅考察正向邊的情況，需要在原有基礎(chǔ)上稍加改動(dòng).其中，S1 為在原網(wǎng)絡(luò)基礎(chǔ)上構(gòu)造的殘差網(wǎng)絡(luò);S2 至S7 為迭代搜索可增路的過程，S3 僅對(duì)正向邊做處理，從而保證了可增路中只包含正向邊.S8 的輸出可能有2 種情況:一種是具有最大可增流的路徑，即為最優(yōu)交通分配路徑;另一種是空集，這意味著當(dāng)前網(wǎng)絡(luò)已經(jīng)達(dá)到最大流狀態(tài)，沿任何路徑均不能增加總的網(wǎng)絡(luò)流.從交通控制的角度看，這種情況表明當(dāng)前路網(wǎng)已經(jīng)達(dá)到最大承載能力，無論采用何種控制方式都不能改善交通狀況，只能通過進(jìn)一步加大基礎(chǔ)設(shè)施建設(shè)來達(dá)到目的.圖2 給出了以圖1 所示網(wǎng)絡(luò)作為輸入的計(jì)算過程.可以看到，“路徑4”具有最大的可增流，因此算法將輸出路徑4 作為最大可增流路徑.必須指出的是，最優(yōu)分配路徑并不唯一.當(dāng)多條可增路均具有最大可增流時(shí)，算法將隨機(jī)輸出一條作為結(jié)果.此時(shí)從流量分配的角度看，這些最大可增路是等效的.在實(shí)際應(yīng)用過程中，可以將考察全時(shí)段劃分成多個(gè)子區(qū)間，每個(gè)子區(qū)間上按照最大可增路的搜索算法搜索最大可增路并進(jìn)行流量分配，從而達(dá)到動(dòng)態(tài)更新的目的.

圖2 示例計(jì)算結(jié)果

最大可增路的搜索算法的具體步驟如下:

輸入:當(dāng)前路網(wǎng)N(V，L，C)中各路段的流量值.

輸出:所有源—匯結(jié)點(diǎn)對(duì)間的最大可增路及其可增流量值.

對(duì)任意出行源—匯結(jié)點(diǎn)對(duì)(Sou，Con)，可按以下步驟搜索:

S0:令PathSet=φ;(PathSet 為可增路集合)

S1:對(duì)所有路段a，令，△f(a)=c(a)－f(a)，得到一個(gè)新網(wǎng)絡(luò)，稱為殘差網(wǎng)絡(luò);

S2:令Stack=Sou，將Sou 標(biāo)號(hào)為“已查點(diǎn)”，其余標(biāo)號(hào)“未查點(diǎn)”;(Stack 用來記錄一條可增路)

S3:對(duì)Stack 中的棧頂結(jié)點(diǎn)u，若存在鄰結(jié)點(diǎn)v滿足:①(u，v)∈L;②vStack;③v 通過u 被檢查;則轉(zhuǎn)S4，否則，轉(zhuǎn)S5;

S4:將v 壓棧，轉(zhuǎn)S6;

S5:將所有通過u 查詢過的結(jié)點(diǎn)標(biāo)號(hào)為“未查點(diǎn)”，并將u 出棧，轉(zhuǎn)S6;

S6:若匯結(jié)點(diǎn)Con 位于棧頂，則將Con 標(biāo)號(hào)為“未查點(diǎn)”，將Stack 中的路徑結(jié)點(diǎn)復(fù)制存儲(chǔ)于Path-Set 中，并將Con 出棧;

S7:若Stack 非空，則轉(zhuǎn)S2，否則轉(zhuǎn)S8;

S8:若PathSet=φ，則當(dāng)前的網(wǎng)絡(luò)流已達(dá)到最大流，算法停止;否則，按照公式，△f(P)=mina∈P△f(a)，計(jì)算PathSet 中所有路徑的可增流，并輸出具有最大可增流的路徑和可增流量值，算法停止.

2 算法在Hadoop上的MapReduce實(shí)現(xiàn)

在實(shí)際應(yīng)用中，面對(duì)大規(guī)模路網(wǎng)搜索過程會(huì)非常緩慢，使得分配過程不能在有效時(shí)間內(nèi)完成，計(jì)算結(jié)果變得毫無意義.因此，必須采取加速手段來提高其實(shí)時(shí)性.

Hadoop 是一個(gè)開源的云計(jì)算平臺(tái)，由The Apache Software Foundation 公司維護(hù)，其實(shí)現(xiàn)語言是Java.Hadoop 的核心由分布式文件系統(tǒng)(Hadoop Distribution File System，HDFS)和MapReduce 編程模型構(gòu)成，是針對(duì)分布式計(jì)算所設(shè)計(jì)的一種編程方式［4－6］.在該模型框架下，用戶需要指定以下信息:分布式文件系統(tǒng)作業(yè)輸入路徑;分布式文件系統(tǒng)作業(yè)輸出路徑;輸入數(shù)據(jù)格式;輸出數(shù)據(jù)格式;包含Map 方法的類;包含Reduce 方法的類(可選);Map類、Reduce 類以及其他必需類的Jar 文件路徑.

MapReduce 的作業(yè)過程如圖3 所示.輸入數(shù)據(jù)以鍵值對(duì)的形式存在，稱為記錄.Map 操作對(duì)每一條記錄生成一條或多條輸出記錄.這些記錄在分割階段按照鍵排序并溢出到硬盤，以此作為Reduce 階段的輸入.在Reduce 階段，具有相同鍵值的記錄被打包作為一個(gè)Reduce 的輸入，從而進(jìn)行Reduce 操作.顯然，采用Hadoop 進(jìn)行計(jì)算時(shí)，最主要的問題是如何設(shè)計(jì)Map 和Reduce 函數(shù).

圖3 MapReduce 過程

在圖4 所示的實(shí)驗(yàn)路網(wǎng)，共14 個(gè)路口，38 條路段.抽象路網(wǎng)中每條邊上的值仍然代表某一檢測時(shí)間段內(nèi)的交通流量值以及路段最大流量值.

圖4 實(shí)驗(yàn)路網(wǎng)示意圖

圖5 是其第一輪MapReduce 過程示意圖.左側(cè)的Map 階段，以所有邊的信息作為輸入.其中鍵值對(duì)的鍵部分預(yù)設(shè)為默認(rèn)，而值部分由邊的起點(diǎn)終點(diǎn)和流量組成.Map 操作將對(duì)每一條記錄進(jìn)行展開，生成2 條記錄.結(jié)果記錄中鍵部分即為原輸入邊的起點(diǎn)和終點(diǎn)，而值部分的流量變?yōu)榭稍隽髁?可以看出，Map 操作實(shí)際上是生成了所有單條邊的可增流.在Reduce 階段，所有具有相同鍵的記錄被集中到一起，按照收尾結(jié)點(diǎn)相同的組合原則生成長度為2(即包含2 條邊)的可增路.可增路的可增流量為組合的2 條記錄中可增流的較小值.

圖6 所示為其第二輪MapReduce 迭代過程.在本輪操作中，將原始邊的信息和第一輪MapReduce的輸出結(jié)果一起作為輸入.同樣地，Map 對(duì)于每條輸入記錄，分別以其首尾結(jié)點(diǎn)做鍵產(chǎn)生2 條記錄.具有相同鍵的記錄被匯集到一起，根據(jù)首尾結(jié)點(diǎn)組合成長度為3 或者更長的可增路.可增流仍然采用組合記錄中的最小值.按照上述過程，可以繼續(xù)第4 輪、第5 輪迭代.隨著迭代次數(shù)的增加，得到的可增路的長度也逐步增加.需要指出的是，在每一輪Reduce中，需要排除結(jié)果中的“回路”，如此可以大幅降低計(jì)算開銷.當(dāng)某兩輪的迭代結(jié)果完全相同時(shí)，計(jì)算停止.此時(shí)，需要將歷次迭代的輸出結(jié)果匯總并排序.MapReduce 提供了二次排序的功能，即利用分割階段具有相同鍵的記錄被匯集到同一個(gè)Reduce 中的特點(diǎn)進(jìn)行排序.在二次排序中，需要對(duì)輸入結(jié)構(gòu)做微小修改，即以歷次迭代輸出記錄的鍵和可增流的組合作為新的鍵，稱為“復(fù)合鍵”(見圖7)，則Hadoop 分割器會(huì)首先按照復(fù)合鍵的邊部分排序，將相同起始結(jié)點(diǎn)和終止結(jié)點(diǎn)的記錄集中為一個(gè)組，然后再按照復(fù)合鍵的可增流部分從大到小排序.該步操作完成之后，只需要選取每個(gè)組的第一條記錄即為對(duì)應(yīng)出行起點(diǎn)和終點(diǎn)之間的最大可增路.

圖5 第一輪MapReduce 過程

圖6 第二輪MapReduce 過程

圖7 二次排序

3 Hadoop 下的計(jì)算性能分析

為考察上述模型在Hadoop 平臺(tái)上的計(jì)算性能，本研究進(jìn)行了一系列計(jì)算實(shí)驗(yàn).其中，Hadoop 平臺(tái)包含10 個(gè)計(jì)算結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)硬件配置均為Intel Core2 Quad 8400 CPU(主頻2.66 GHz)，4 GB Memory.實(shí)驗(yàn)網(wǎng)絡(luò)仍然采用圖4 所示的路網(wǎng).實(shí)驗(yàn)共進(jìn)行了10 輪迭代以及1 輪二次排序.

表1 給出了計(jì)算中單個(gè)任務(wù)的耗時(shí)情況.可以看出，Map 操作的時(shí)長基本穩(wěn)定在6 s 左右，這是因?yàn)镸ap 函數(shù)并不需要對(duì)輸入做復(fù)雜操作，而只需要按照首尾結(jié)點(diǎn)產(chǎn)生2 條幾乎完全一樣的記錄作為Reduce 的輸入.

隨著迭代次數(shù)的增加，可增路的長度也逐漸增加，體現(xiàn)為Reduce 的耗時(shí)越來越長.顯然，這是由于生成可增路的主要操作都在Reduce 函數(shù)中進(jìn)行，如組合路徑、檢查并排除回路等復(fù)雜步驟.在最后兩輪迭代中，Reduce 耗時(shí)有所下降，其原因是大部分可增路已經(jīng)生成，計(jì)算量有所減少.另外，二次排序由于只涉及到分割操作，而對(duì)Map 和Reduce 函數(shù)無復(fù)雜計(jì)算要求，故耗時(shí)較短.

表1 MapReduce 單個(gè)任務(wù)耗時(shí)統(tǒng)計(jì)

表2 MapReduce 任務(wù)分配統(tǒng)計(jì)

表2 給出了每一輪迭代中，計(jì)算任務(wù)分配到10個(gè)結(jié)點(diǎn)的情況.表2 中數(shù)據(jù)為Map/Reduce 階段的任務(wù)個(gè)數(shù).可以看出，除首輪迭代外，Map 函數(shù)的任務(wù)一般有15 個(gè)，而Reduce 任務(wù)一共有14 個(gè).從數(shù)據(jù)上看，計(jì)算任務(wù)分布較均衡，這表明Hadoop 的運(yùn)行狀況較理想.

4 結(jié) 論

本研究從最大流理論出發(fā)，回顧了最大可增路的搜索算法.同時(shí)，針對(duì)大規(guī)模網(wǎng)絡(luò)計(jì)算緩慢的情況，為提高計(jì)算速度，本研究給出了在開源云計(jì)算平臺(tái)——Hadoop 上的MapReduce 實(shí)現(xiàn)方式.基于簡單路網(wǎng)的計(jì)算實(shí)驗(yàn)表明，本研究算法的分布式實(shí)現(xiàn)方式能夠在較短時(shí)間內(nèi)得到最大可增路，可為實(shí)時(shí)快速?zèng)Q策奠定基礎(chǔ).

［1］Van Aerde M，Yagar S.Dynamic integrated freeway/traffic signal networks:a routing based modeling approach［J］.Transp Res Part A:General，1988，22(6):445－453.

［2］Jayakrishnan R，Chen A，Tsai W K.Freeway and arterial traffic flow simulation analytically embedded in dynamic assignment［J］.Transp Res Rec，1999，1678(1):242－250.

［3］Ford L R，F(xiàn)ulkerson D R.Maximal flow through a network［J］.Can J Math，1956，8(3):399－404.

［4］White Tom.Hadoop:The definitive guide［M］.Sebastopol，CA，USA:O＇Reilly Media，Inc.，2009.

［5］Venner J.Pro hadoop:Build scalable，distributed applications in the cloud［M］.New York:Apress，2009.

［6］Dean J，Ghemawat S.MapReduce:simplified data processing on large clusters［J］.Comm ACM，2004，51(1):107－113.