海量遙感數據的高可靠并行處理方法

景維程

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

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

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

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

基于前述分析，本文提出了一種基于可靠性代價的面向海量遙感數據的并行調度算法（Remote sensing data reliable scheduling，RSDRS）。算法在利用主副版本的復制技術基礎上，通過計算虛擬節點及聯絡的可靠性代價以此屏蔽高風險節點。同時，通過計算主副版本任務的最佳開始時間，實現了調度時間的最優化。

1 任務模型

1．1 云計算系統模型

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

1．2 遙感數據任務模型

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

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

集合｛vx∈V：exi∈E｝表示任務vi所有前驅節點集合，記為pred（vi）。集合｛vx∈V：eix∈E｝表示任務vi所有后繼節點集合，記為succ（vi）。如果pred vi＝? 則任務節點vi是入口節點，記為ventry。如果succ（vi）＝?，則任務節點vi是出口節點，記為vexit。

m×n矩陣X 為遙感DAG任務與虛擬機映射關系，矩陣XB為遙感DAG副版本任務與虛擬機映射關系。即如果Xij＝1表示任務vi被任務被映射到虛擬機Pj上執行任務，遙感數據任務與虛擬機的映射調度。

2 可靠性代價驅動的調度算法

2．1 主任務的開始時間計算

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

2．2 副版本任務開始時間計算

遙感任務vj的主版本調度滿足上述要求時，pred（vj）2表示集合pred（vj）中滿足狀態遙感主任務集合，p d（vj）為vj所有任務中與vj存在間接與直接依賴關系滿足遙感主版本的任務集合。

因此有

2．3 可靠性代價

設Rij表示任務vi在虛擬機節點Pj的為提高可靠性而得到可靠性代價公式，如式（3）所示。可以看到，要提高調度算法的可靠性，需要最小化虛擬機的可靠性代價。

因此，提高系統可靠性，需要最小化虛擬機可靠性代價，在滿足執行時間前提下，將任務調度到可靠性代價最小的虛擬機上執行。

2．4 遙感任務優先級

遙感任務處理多為單個DAG任務的靜態調度方法，使用與HEFT［10］相似的優先級計算方法，將通信代價加入到判定中來，任務優先級表示為

假設w（vi）表示遙感任務vi在所有虛擬機上的平均執行代價，由式（4）可知，任務vi的優先級與后繼任務的優先權和通信代價有關。所有任務的優先權都是從出口任務向上遍歷任務圖，因此出口任務優先權表示為

算法描述如表1所示。

表1 算法描述

3 仿真實驗

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

3．1 實驗數據

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

表2 實驗參數

3．2 節點失效對調度算法的影響

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

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

3．3 處理機利用率

圖2 精度為100時處理機數的比較

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

圖3 精度為1 000時處理機數的比較

表3 實驗參數

4 結束語

任務調度和管理是遙感衛星數據地面預處理系統設計中的核心技術，本文以遙感數據的DAG應用處理為出發點，使用云計算技術，高效的處理遙感數據，提高了處理效率。同時，為了保證處理數據的可靠性，使用了主副版本技術及可靠性代價的虛擬節點計算方法，有效解決云計算調度中的不可靠性問題。

［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］ 向彪，李國慶，劉定生，等．高性能遙感衛星地面預處理系統中的任務管理與調度技術研究［J］．宇航學報，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．