景維程

（黑龍江第一測繪工程院，黑龍江 哈爾濱150025）

隨著多源、多角度、多分辨率的空天地一體化的對地觀測網(wǎng)絡(luò)的建設(shè)，對地觀測數(shù)據(jù)的規(guī)模呈幾何數(shù)量級(jí)提高。應(yīng)用海量的遙感數(shù)據(jù)不但能夠準(zhǔn)確、快速的對自然災(zāi)害監(jiān)測，同時(shí)高效實(shí)時(shí)的分析也能對災(zāi)情進(jìn)行預(yù)警和快速響應(yīng)，以降低災(zāi)害所帶來的損失。這要求在建立海量遙感數(shù)據(jù)的復(fù)雜計(jì)算模型同時(shí)，也要面對遙感大數(shù)據(jù)的應(yīng)用特點(diǎn)，設(shè)計(jì)有效的解決計(jì)算密集和數(shù)據(jù)密集型處理的云計(jì)算及并行算法，以滿足當(dāng)前大數(shù)據(jù)量遙感應(yīng)用的需求。

針對海量遙感數(shù)據(jù)的并行處理方法，國內(nèi)外有大量的研究成果：文獻(xiàn)［1］使用網(wǎng)格計(jì)算實(shí)現(xiàn)了對海量遙感數(shù)據(jù)進(jìn)行并行處理，提高計(jì)算效率；文獻(xiàn)［2］提出使用MPI并行計(jì)算框架來解決遙感數(shù)據(jù)處理模型；文獻(xiàn)［3］研究實(shí)現(xiàn)了遙感信息服務(wù)網(wǎng)格節(jié)點(diǎn)，并實(shí)現(xiàn)了對大規(guī)模數(shù)據(jù)處理的高通量計(jì)算；文獻(xiàn)［4］提出一種成功應(yīng)用于通用高性能衛(wèi)星地面預(yù)處理系統(tǒng)（GHIPS）中的、基于機(jī)群平臺(tái)的任務(wù)管理與調(diào)度技術(shù)。前述相關(guān)研究更多關(guān)注調(diào)度算法的并行效率，忽略了在調(diào)度過程中云計(jì)算（并行）系統(tǒng)產(chǎn)生的故障而導(dǎo)致算法效率下降的問題。

由于云計(jì)算建立在大規(guī)模廉價(jià)的服務(wù)集群上的一種新的服務(wù)模式，加上遙感計(jì)算任務(wù)的復(fù)雜性和動(dòng)態(tài)性以及具有極大的關(guān)聯(lián)性，導(dǎo)致計(jì)算節(jié)點(diǎn)極容易出現(xiàn)故障，因此，在面向遙感數(shù)據(jù)的并行調(diào)度算法必須在探求整體任務(wù)的最短完成時(shí)間情況下，提高任務(wù)調(diào)度可靠性。文獻(xiàn)［5－9］中論述使用主副版本（PB）的調(diào)度機(jī)制是有效提高調(diào)度算法可靠性方法。文獻(xiàn)［5］提出了使用將所有的調(diào)度任務(wù)都進(jìn)行復(fù)制，以此保證算法具有較高的可靠性，并定義執(zhí)行副本的具體時(shí)間；文獻(xiàn)［6］提出一種在處理實(shí)時(shí)任務(wù)的最佳Makespan和可靠性的調(diào)度算法；文獻(xiàn)［7］在文獻(xiàn)［6］算法的基礎(chǔ)上使用Map Reduce編程框架實(shí)現(xiàn)可靠性和性能最優(yōu)；文獻(xiàn)［8］提出優(yōu)先級(jí)約束的調(diào)度算法，規(guī)定DAG（有向無環(huán)圖，Directed Acyclic Graph）任務(wù)的主副版本重疊調(diào)度方法，但是該方法更多關(guān)注前一節(jié)點(diǎn)的完成情況，而沒有考慮所有節(jié)點(diǎn)任務(wù)的完成問題；文獻(xiàn)［9］提出了基于云理論的遙感影像分類方法。

基于前述分析，本文提出了一種基于可靠性代價(jià)的面向海量遙感數(shù)據(jù)的并行調(diào)度算法（Remote sensing data reliable scheduling，RSDRS）。算法在利用主副版本的復(fù)制技術(shù)基礎(chǔ)上，通過計(jì)算虛擬節(jié)點(diǎn)及聯(lián)絡(luò)的可靠性代價(jià)以此屏蔽高風(fēng)險(xiǎn)節(jié)點(diǎn)。同時(shí)，通過計(jì)算主副版本任務(wù)的最佳開始時(shí)間，實(shí)現(xiàn)了調(diào)度時(shí)間的最優(yōu)化。

1 任務(wù)模型

1．1 云計(jì)算系統(tǒng)模型

云計(jì)算的計(jì)算資源由于進(jìn)行虛擬化，這里將虛擬化后異構(gòu)虛擬機(jī)集合描述為P＝｛P1，P2，…，PM｝，其中M表示虛擬機(jī)數(shù)。調(diào)度到虛擬機(jī)Pk上的任務(wù)vi的主版本開始時(shí)間表示為（vi，pk），完成時(shí)間分別表示為（vi，pk）；任務(wù)vj副版本開始時(shí)間和完成 時(shí) 間 分別表 示 為（vj，pk）（vj，pk）。任務(wù)vi的主、副版本任務(wù)被調(diào)度的虛擬機(jī)表示為Pp（vi）和PB（vi）。

1．2 遙感數(shù)據(jù)任務(wù)模型

在典型的遙感數(shù)據(jù)的云計(jì)算處理中，對于需要并行處理的遙感任務(wù)用DAG圖來表示，以下進(jìn)行形式化定義：

四元組G＝（V，E，w，c）表示節(jié)點(diǎn)和邊的DAG圖，其中V＝｛v1，v2，v3，…，vN｝表示任務(wù)集合，N 表示任務(wù)數(shù)。任務(wù)之間具有的依賴關(guān)系用E＝｛eij｜vi，vj∈V｝表示。w（vi）j表示任務(wù)vi的在虛擬機(jī)Pj計(jì)算消耗，c（eij）表示任務(wù)vi和vj之間的通信消耗。

集合｛vx∈V：exi∈E｝表示任務(wù)vi所有前驅(qū)節(jié)點(diǎn)集合，記為pred（vi）。集合｛vx∈V：eix∈E｝表示任務(wù)vi所有后繼節(jié)點(diǎn)集合，記為succ（vi）。如果pred vi＝? 則任務(wù)節(jié)點(diǎn)vi是入口節(jié)點(diǎn)，記為ventry。如果succ（vi）＝?，則任務(wù)節(jié)點(diǎn)vi是出口節(jié)點(diǎn)，記為vexit。

m×n矩陣X 為遙感DAG任務(wù)與虛擬機(jī)映射關(guān)系，矩陣XB為遙感DAG副版本任務(wù)與虛擬機(jī)映射關(guān)系。即如果Xij＝1表示任務(wù)vi被任務(wù)被映射到虛擬機(jī)Pj上執(zhí)行任務(wù)，遙感數(shù)據(jù)任務(wù)與虛擬機(jī)的映射調(diào)度。

2 可靠性代價(jià)驅(qū)動(dòng)的調(diào)度算法

2．1 主任務(wù)的開始時(shí)間計(jì)算

通過對遙感任務(wù)vj的主任務(wù)分析，可以得到，如果任務(wù)的完成時(shí)間小于集合pred（vj）中所有前驅(qū)任務(wù)主副版本任務(wù)最遲完成時(shí)間與通信完成時(shí)間的最大值。這樣就可以保證主版本任務(wù)出現(xiàn)故障后，副版本任務(wù)仍然能夠順利執(zhí)行。

2．2 副版本任務(wù)開始時(shí)間計(jì)算

遙感任務(wù)vj的主版本調(diào)度滿足上述要求時(shí)，pred（vj）2表示集合pred（vj）中滿足狀態(tài)遙感主任務(wù)集合，p d（vj）為vj所有任務(wù)中與vj存在間接與直接依賴關(guān)系滿足遙感主版本的任務(wù)集合。

因此有

2．3 可靠性代價(jià)

設(shè)Rij表示任務(wù)vi在虛擬機(jī)節(jié)點(diǎn)Pj的為提高可靠性而得到可靠性代價(jià)公式，如式（3）所示。可以看到，要提高調(diào)度算法的可靠性，需要最小化虛擬機(jī)的可靠性代價(jià)。

因此，提高系統(tǒng)可靠性，需要最小化虛擬機(jī)可靠性代價(jià)，在滿足執(zhí)行時(shí)間前提下，將任務(wù)調(diào)度到可靠性代價(jià)最小的虛擬機(jī)上執(zhí)行。

2．4 遙感任務(wù)優(yōu)先級(jí)

遙感任務(wù)處理多為單個(gè)DAG任務(wù)的靜態(tài)調(diào)度方法，使用與HEFT［10］相似的優(yōu)先級(jí)計(jì)算方法，將通信代價(jià)加入到判定中來，任務(wù)優(yōu)先級(jí)表示為

假設(shè)w（vi）表示遙感任務(wù)vi在所有虛擬機(jī)上的平均執(zhí)行代價(jià)，由式（4）可知，任務(wù)vi的優(yōu)先級(jí)與后繼任務(wù)的優(yōu)先權(quán)和通信代價(jià)有關(guān)。所有任務(wù)的優(yōu)先權(quán)都是從出口任務(wù)向上遍歷任務(wù)圖，因此出口任務(wù)優(yōu)先權(quán)表示為

算法描述如表1所示。

表1 算法描述

3 仿真實(shí)驗(yàn)

為了評(píng)估算法的性能，使用4臺(tái)曙光服務(wù)器和一臺(tái)普通PC機(jī)，主要配置如下：曙光I450－G10：塔式服務(wù)器，一個(gè)Inter Xeon E5－2407四核2．2 GHz處理器，8 GB內(nèi)存，硬盤300 G；PC機(jī)配置為：HP Compaqdx 2308，Intel Pentiu m E216處理器，主頻1．8 GHz，1 G內(nèi)存，160 G硬盤；曙光服務(wù)器作為虛擬機(jī)的物理載體，搭配上XenServer－6．2，實(shí)現(xiàn)虛擬化，pc機(jī)獨(dú)立出來作為集群的 Master節(jié)點(diǎn)（1個(gè)），管理Slaves節(jié)點(diǎn)（16個(gè)）；每個(gè)節(jié)點(diǎn)安裝Centos6．4＿final作為系統(tǒng)平臺(tái)，其內(nèi)核為2．6．32版，在該平臺(tái)上安裝JDK（jdk－6u31－linux－i586．bin）作為 Hadoop的底層運(yùn)行架構(gòu)，在JDK上安裝Hadoop（hadoop－1．0．0．tar．gz）來構(gòu)建云集群。

3．1 實(shí)驗(yàn)數(shù)據(jù)

為了評(píng)估算法的處理遙感數(shù)據(jù)時(shí)體現(xiàn)的高可靠性，使用渤海灣遙感影像數(shù)據(jù)（34°N－42°N and 115°E－120°E）進(jìn)行試驗(yàn)。實(shí)驗(yàn)中使用的數(shù)據(jù)是從200到1 200，主要完成遙感衛(wèi)星影響數(shù)據(jù)的校正處理任務(wù)，實(shí)驗(yàn)數(shù)據(jù)參數(shù)如表2所示。

表2 實(shí)驗(yàn)參數(shù)

3．2 節(jié)點(diǎn)失效對調(diào)度算法的影響

設(shè)遙感云計(jì)算平臺(tái)虛擬機(jī)節(jié)點(diǎn)的最小失效率MIN＿F＝10－6／h，最大失效率 MAX＿F為3．5×10－6～7．5×10－6／h。并且每小時(shí)增加0．5×10－6／h，鏈路失效概率LINK＿F為0．65×10－6／h到0．95×10－6／h。由圖1可以看到將遙感任務(wù)規(guī)模限定在100，虛擬計(jì)算節(jié)點(diǎn)為20個(gè)時(shí)的可靠性結(jié)果。實(shí)驗(yàn)結(jié)果中橫坐標(biāo)是節(jié)點(diǎn)失效概率，縱坐標(biāo)是虛擬機(jī)的可靠性，可以看到與FTRMFF及TPFTRM比，算法的可靠性在不同失效概率下虛擬機(jī)的可靠性有了明顯提高，其可靠性分別提高了約10%和20%。

圖1 不同失效概率下的可靠性

3．3 處理機(jī)利用率

圖2 精度為100時(shí)處理機(jī)數(shù)的比較

為了更好地測試遙感云平臺(tái)的利用率，設(shè)定測試的渤海灣遙感數(shù)據(jù)的遙感精度為100和1 000時(shí)不同精度下的虛擬機(jī)的利用率，如表3所示。圖2、圖3中橫坐標(biāo)是進(jìn)行處理的遙感任務(wù)數(shù)，縱坐標(biāo)為虛擬機(jī)的利用率，可以看到算法的虛擬機(jī)利用率有了較大的提高，由于對副版本任務(wù)的設(shè)定及完成時(shí)間的準(zhǔn)確估算使得虛擬平臺(tái)能夠高效利用。

圖3 精度為1 000時(shí)處理機(jī)數(shù)的比較

表3 實(shí)驗(yàn)參數(shù)

4 結(jié)束語

任務(wù)調(diào)度和管理是遙感衛(wèi)星數(shù)據(jù)地面預(yù)處理系統(tǒng)設(shè)計(jì)中的核心技術(shù)，本文以遙感數(shù)據(jù)的DAG應(yīng)用處理為出發(fā)點(diǎn)，使用云計(jì)算技術(shù)，高效的處理遙感數(shù)據(jù)，提高了處理效率。同時(shí)，為了保證處理數(shù)據(jù)的可靠性，使用了主副版本技術(shù)及可靠性代價(jià)的虛擬節(jié)點(diǎn)計(jì)算方法，有效解決云計(jì)算調(diào)度中的不可靠性問題。

［1］ N．Bataille，M．Lematre and G．Verfaillie．“Efficiency and fair ness when sharing the use of a satellite．”In Proceedings of the 5th International Sy mposiu m on Artificial Intelligence，Robotics and Automation in Space，pages 465－470，Noor d wijk（1999）．

［2］ J．－F．Cordeau and G．Laporte．“Maxi mizing the Value of an Earth Observation Satellite Or bit．”Jour nal of the Operational Research Society，56：962－968（2005）．

［3］ Domenico Beneventano，PSonia Ber gamaschi，PClaudio Sartori．Description logics f or semantic query optimization in object－oriented database systems［J］．ACM Transactions on Database Systems，2003，28（1）：1－50．

［4］ 向彪，李國慶，劉定生，等．高性能遙感衛(wèi)星地面預(yù)處理系統(tǒng)中的任務(wù)管理與調(diào)度技術(shù)研究［J］．宇航學(xué)報(bào)，2008，29（4）：1443－1446．

［5］ ZHANG Jun，EDWIN Sha，Qingfeng Zhuge．，Kaijie WU．Efficient fault－tolerant scheduling on multiprocessor systems via replication and deallocation［J］．Inter national Jour nal of Embedded Systems，2014，6（2－3）：216－224．

［6］ BARUAH V B，A Marchetti Spaccamela，L Stougie A Wiese．A generalized parallel task model f or recurrent real－ti me pr ocesses［C］／／Proceedings of the 33t h Real－Time Systems Sy mposium （RTSS）．Piscataway：IEEE，2012．

［7］ RAJU R，A MUDHAVEL J，SAULE E，ANUJA S．A heuristic fault tolerant Map Reduce framewor k f or mini mizing makespan in Hybrid Cloud Environ ment［C］／／Proceedings of the Green Computing Communication and Electrical Engineering （ICGCCEE 2014）．Piscataway：IEEE，2014．

［8］ XIE Guoqi，LI Renfa，LIU Lin，YANG Fan．DAG reliability model and fault－tolerant algorithm for heterogeneous distributed systems［J］．Infor mation Processing Letters，2009，109（11）：539－542．

［9］ 趙靜，王崇倡，王家海，等．基于云理論的遙感影像分類方法分析［J］．測繪工程，2014，23（12）：21－24．

［10］MACEY B S，ZOMAYA A Y．A Perfor mance evaluation of CP list scheduling heuristics for co mmunication intensive task graphs［C］／／Proceedings of the International Parallel Processing Sy mposiu m．Piscataway：IEEE，1998．