景维程

（黑龙江第一测绘工程院，黑龙江 哈尔滨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．