基于价格时延Petri网的超级节点网格调度*
2013-09-29潘善亮茅琴娇
潘善亮 ，黄 希 ，茅琴娇
（1.宁波大学计算机科学技术研究所 宁波 315211；2.西安交通大学电子与信息工程学院 西安 710049）
1 引言
近几年提出的超级节点模式网格资源管理[1,2]很好地在高效的集中式搜索与扩展性强的分布式搜索之间实现了平衡。超级节点模式网格按资源注册方式主要分为两种[3]：一种是资源节点按地域界限划分的超级节点模式网格；另一种是资源节点基于语义相似度聚类的超级节点模式网格。其中，在第二种超级节点模式网格中，资源节点基于语义相似度聚类，同一超级节点域内的资源类型相同。这种类型的网格至少具有以下优点：资源的描述包含本体语义特征，资源发现具有更高的查全率与查准率[4]；具有相同类型的资源预先分组聚类，能降低查找空间，资源发现具有更高的效率[5,6]。因此，资源节点基于语义相似度聚类的超级节点模式网格受到了广泛的关注。
[7～9]提出了利用超级节点网络来管理文件共享系统，资源节点依据其共享文件的语义相似性进行分组。参考文献[10]将Web服务按照语义定义进行分组聚类，由超级节点进行管理。参考文献[11]构建了一个网格资源节点身份可靠性度量函数和行为表现信誉度评估策略，建立了一个网格任务调度的安全融合模型，以此为基础，提出一个时间—安全驱动的双目标优化网格依赖任务调度模型。参考文献[12]将节点的兴趣进行分组聚类，每个分组内的节点构成一个语义树，根节点之间互联形成一个覆盖网络。参考文献[13]提出语义覆盖簇的概念，讨论了资源节点如何加入对应的超级节点。参考文献[14]提出了基于超级节点模式网格的资源语义描述与注册框架。参考文献[15]在参考文献[14]的基础上提出了资源分类的处理过程以及超级节点的选择方法。以上学者虽然将本体以及资源分类聚集的思想引入网格中，但是他们的讨论局限于网格体系结构，资源的描述与注册框架以及资源分类的处理过程等方面，而没有具体讨论对于一个需要协同不同类型的资源以完成网格协作型任务的具体调度方法及其形式化建模和理论分析。参考文献[16]针对资源节点按地域界限划分的超级节点模式网格提出了一种两阶段网格任务调度方法，并用时延Petri网对调度过程进行了建模、分析。但是其讨论的对象是简单的元任务且只考虑了调度的时间特性。
不同于以上参考文献的研究，本文针对资源节点基于语义相似度聚类的超级节点模式网格，提出网格协作型任务的面向用户时间、费用及二者偏好参数等多QoS约束的调度算法且考虑了重调度机制。鉴于复杂的调度过程具有并行、分布式的特点，笔者利用价格时延Petri网对调度过程进行建模，图形化调度过程，构造并分析可达任务图，通过实例验证算法的有效性。
2 网格协作型任务调度算法
2.1 资源管理模型
图1显示了资源节点基于语义相似度聚类的超级节点模式网格体系结构[14,15]。
图1 网格体系结构
在图1中，网格资源节点基于语义相似度分组聚类，每个聚类对应的网格社区有一个超级节点负责管理。规定一个节点只提供一种类型的资源且资源的分类体系不考虑各类型之间的层次关系[17]。
“Class”为一组语义相似的网格资源节点集合。每个Class包含两种类型的节点：资源节点（node）和超级节点（SP）。超级节点是性能评估参数较高的节点，为本聚类中的节点作为服务器运作，代表对应的资源分类。不同类型的SP之间采用P2P模式互连。每个node都在对应的SP处进行注册。
有关资源节点基于语义相似度的聚类技术、资源与任务的匹配方法等在参考文献[6]中有详细介绍，本文不再赘述。
2.2 调度算法
先定义如下的参数：ti，j为任务i在资源节点j上的估计执行时间。T为任务的截止期限与到达时间之差。ci，j为任务i在其他用户资源节点j上的估计执行费用。C为任务的费用上限。α+β=1；α≥0，β≥0。其中，α，β为用户定义的时间和费用偏好参数。
定义1 在语义匹配且截止期限和费用上限均能满足的情况下，资源j对于任务i的评价函数为：
超级节点将从符合要求的多个资源中选择使目标函数I最小的资源j作为任务i的调度目标。
在本文的调度模型中，超级节点具有一定的智能，用户向系统提交任务，如果任务能在该用户所在社区执行完成，就直接由该社区的超级节点调度完成任务的执行。如果任务不能在该社区内完成，就需要由该用户所在的社区的超级节点与其他社区的超级节点协调，找到合适的社区完成任务的执行。调度算法简要描述如下。
步骤1 用户将网格任务提交给本地超级节点（SP），SP接收后，判断其是否可以根据资源类型分解为子任务。
步骤 2 对于任一任务（元任务或者子任务），SP首先考虑其所需的资源类型是否对应于本地类型，若是，则转步骤3；否则，转步骤 4。
步骤3 SP进行本地集中式调度。对于语义匹配的资源节点，以定义1中的评价函数作为衡量目标，择优调度，执行交易，返回执行结果给SP。
步骤4 SP进行分布式远程调度。根据所需资源类型查找并发送任务至目标SP，由其在对应分组内作集中式调度。对于匹配的资源节点，以定义1中的评价函数作为衡量目标，择优调度，执行交易，返回执行结果至源SP。
步骤5不断重复步骤2，直至协作型任务的所有子任务都执行完毕。
一个超级节点的网格任务调度算法用伪代码表示如下。
Super-peer scheduling algorithm
INPUT:grid task GT
OUTPUT:execution result of GT
Begin
While GT comes from local grid community do
If GT can decompose
Then according to resource classification,decompose it to subtasks with the QoS parameters;establish a dispatch list;
Else GT is called meta-task;
For every grid task GTi(GTiis a sub-task or meta-task)
If the local resource type can satisfy GTi,Super-peer.s search for the semantic matching node.k which also meets the following two requirements:
ArrivalTime(GTi)+ExecutedTime(GTi,Super-peer.s,node.k)DeadlineTime(GTi);//时间属性要求
ExecutedCost(GTi,Super-peer.s,node.k)CostLimt(GTi);//费用属性要求
Then for allnode.k calculate the function I;
Seek for the smallest I and the corresponding node.k′;Allocate(GTi,Super-peer.s,node.k′);
If an error occurs to node.k′
Then SendResult0(GTi,Super-peer.s);//错误报告，重调度
Else SendResult1(GTi,Super-peer.s);
Else Queuing(GTi,Peer-to-Peer Grid);
Search some Super-peer.t(t≠s)according to the resource type//超级节点之间分布式资源类型查询
Send(GTi,Super-peer.t);
Endwhile
While GT comes from remote Super-peer.r
For every semantic matching node.l in Super-peer.s which also meets the following two requirements:
ArrivalTime(GT)+ExecutedTime(GT,Super-peer.s,node.l)DeadlineTime(GT);
ExecutedCost(GT,Super-peer.s,node.l)
CostLimt(GT);
Calculate the function I;Seek for the smallest I and the corresponding node.l′;
Allocate(GT,Super-peer.s,node.l′);
If an error occurs to node.l′
Then SendResult0 (GT,Super-peer.s,Super-peer.r);//重调度
Else SendResult1(GT,Super-peer.s,Super-peer.r);
Endwhile
End
设任务T被分解为n个子任务t1,t2,…,tn执行，整个系统有m个网格社区。任务ti的执行时间是由任务在网格社区里的某个节点的最大执行时间决定的，设为max{ti}，则整个调度算法的时间复杂度为O(m·max{ti})。
3 网格调度的价格时延Petri网模型
有关Petri网、颜色Petri网的基本概念与性质可以参考文献[18,19]给出的价格时延Petri网的定义。
定义2 资源节点基于语义相似度聚类的超级节点模式网格任务调度对应的全局Petri网模型是一个层次颜色 Petri网：HCPN=（P，S，T；F，C，W，M0，I）。具体解释如下。
·P 是子网的集合，P={Super-peeri(SPi)/i=1，2，…，n}，n是超级节点的个数，Super-peeri(SPi)是第i个超级节点所对应的局部子网。
·S 是库所的集合，S={Si1，Si2/i=1，2，…，n}，n 是超级节点的个数，Si1是接收从远程超级节点发送来的信息的单元，Si2是向远程超级节点发送信息的单元。
·T 是变迁的集合，T={Tij/i，j=1，2，…，n，i≠j}，n 是超级节点的个数，Tij表示第i个超级节点的发送单元向第j个超级节点的接收单元发送消息。其中，每个变迁的时延、价格属性均为0。
·F 是弧的集合，F哿（P×S，S×P，S×T，T×S）。
·C={（rt，dt，dc，α，β）}∪{τ，et，ct}∪{（gt，gs）}∪R 是颜色的集合，rt、dt、dc 分别是任务（子任务）的到达时间、截止期限、费用上限。α、β分别是用户规定的时间及费用偏好参数。τ是变迁实施的时刻，et、ct是任务（元任务或者子任务）在各资源节点上执行时所花费的时间和费用估计值。gt、gs分别是超级节点之间发送的任务信息及其执行结果信息。R为资源类型集合。
·W为弧函数；M0是初始标识；I是哨岗函数。
假设图1中有代表4种不同类型资源的超级节点互连，则全局Petri网模型如图2所示。
定义3 第i个超级节点Super-peeri(SPi)所对应的局部子网包括两个相互联系的颜色、价格时延Petri网：集中式调度Petri网和分布式调度Petri网。
定义 4 集中式调度 Petri网：Super-peeriC={S，T；F，C，W，M0，I，Γ，D，E}。
·S 是库所的集合，S={si/i=1，2，…，17}∪{（CIN，COUT）}，CIN为集中式调度子网接收来自分布式调度子网信息的单元，COUT为集中式调度子网向分布式调度子网发送信息的单元。
·T是变迁的集合；F是弧的集合；C是颜色的集合；W为弧的加权函数集合；M0是库所的初始标识集合；I是变迁的哨岗函数集合；T是变迁实施时刻的集合。
·D是定义在变迁集T上的时延函数，D（t）=a表示变迁的发生需要a单位时间来完成。
·E是定义在变迁集T上的价格函数，E（t）=b表示变迁的发生需要b单位费用来完成。
图3显示了Super-peeri子网包含的集中式调度Petri网Super-peeriC。
图2 网格调度全局层次Petri网HCPN模型
图3 集中式调度Petri网Super-peer iC
为了简便，以下仅介绍图3中变迁的含义，见表1。
表1 图3中变迁的含义
定义 5 分布式调度 Petri网：Super-peeriD=（S，T；F，C，W，M0，I，Γ，D，E）。
其中，各元素的含义与定义4中类似。图4显示了Super-peeri子网包含的分布式调度Petri网Super-peeriD。图中每个变迁的时延、费用属性均为0。为了简便，仅介绍图4中库所的含义，见表2。
图4 分布式调度Petri网Super-peer iD
4 可达任务图
定义6 网格调度全局Petri网HCPN模型的可达任务图是一个有向图 RTG（HCPN）=（V，E），其中 V 是由带标记的标识组成的顶点集合，E是由带标记的连接顶点的有向边所组成的边集合。有向图的构造算法类似于参考文献[16]中提出的算法。基于RTG(HCPN)，可以进行时间和价格特性分析，根据每个任务上到达时间、截止期限、费用上限等，得出整个调度的总时间和总价格成本。这样，可在总体预算和时间的限度下进行调度。根据有向图RTG（HCPN）=（V，E）的时间和价格信息，分别可以得到对应的AOE网Nt和Np，Nt和Np是一个带权的有向无环图，其中顶点表示事件，弧表示任务，权表示任务持续的时间或价格。以下算法给出了计算调度最长时间或最大费用的过程。
表2 图4中库所的含义
算法 根据AOE网计算调度的总时间和成本。
步骤1 根据AOE网求得各个顶点的最大入度。
步骤 2初始化堆栈S。
步骤 3将入度为零顶点入堆栈S，置这些入度为零的顶点的最长时间ve(m)=0；//或最费用为零。
步骤 4 While堆栈S不为空
从堆栈中弹出顶点i
其中，T为所有以i为头的弧
若顶点k的入度为零，则将顶点k入堆栈；步骤5 最后返回各顶点的最长时间。
计算出的最长实施时间和最大成本，可作为调度算法的依据之一。
命题1 设 ne是 RTG(HCPN)中“端点”的个数，则系统的吞吐量为ne。
命题2 设etj为 RTG(HCPN)的第k个资源节点区域中标注在执行变迁tj边上的时延分量，sek=∑etj，μ与s分别是序列{sek}的平均值与标准差，则离散系数v=s/μ可以用来判断系统的负载平衡状态。
命题3设 Mk是RTG（HCPN）中的“端点”，ak、bk分别为Mk的时间、费用标识，则整个系统目前完成所有任务后所处的时刻为max{ak}，所消耗的总费用为∑bk。
5 实例分析
假设在如图5所示的网格计算环境中，节点a1和a2属于SP1所代表的资源分组A类型网格社区；节点b1、b2、b3属于SP2所代表的资源分组B类型网格社区；节点c1属于SP3所代表的资源分组C类型网格社区；节点d1、d2属于SP4所代表的资源分组D类型网格社区。有两个相互之间独立的协作型任务 GT1、GT2分别在节点 a1、c1提交，它们的子任务结构如图6所示。圆圈内的数字表示第几个子任务，字母表示所需的资源类型。
图5 一个调度实例
图6 协作型任务的子任务结构
表3给出了这些任务（子任务）的达到时间、截止期限、费用上限、时间/费用权重；表4和表5分别给出了任务（子任务）在各资源节点上的估计执行时间和估计执行费用。为了讨论方便，假设与每个子任务对应资源类型的网格节点均能满足其语义匹配要求。根据这些参数和调度算法、Petri网模型、定义6，可以构造出该系统网格调度对应的Petri网可达任务图RTG（HCPN），如图7所示。
与参考文献[16]对比，本文作了以下较大改进。
·资源节点基于语义相似度预先分组聚类，能提高资源发现准确率与效率。
·将网格调度的目标由简单的元任务改为常见的协作型任务，协作型任务调度机制复杂。
·调度算法面向用户时间、费用及二者之间权重参数等多QoS约束，而不只是考虑单一的时间参数；引入市场机制，调度算法更能够表征实际网格资源供需双方的自私性，实现资源的优化分配。
·建模工具价格时延Petri网相比于时延Petri网，功能更强大，能同时反映调度过程中产生的时延、价格问题。
总之，本文的研究更加全面、系统和科学。
下面结合表3～表5及可达任务图进行详细的调度分析。
（1）网格任务GT1、GT2均为协作型任务，都需要多种类型的资源协同配合才能完成。对于任务GT1，需要3种类型的资源：A、B、D。SP1接收到任务后，按照资源类型将其分解为 GT1-1、GT1-2、GT1-33个子任务。对于子任务 GT1-1，其需求的资源类型为A，属于SP1所管理的网格社区。由于a1是GT1的提交节点，故a1对应于GT1-1的执行费用为0。SP1进行集中式查询发现，a1、a2均能满足GT1-1的时间、费用等QoS参数的要求，计算a1、a2相对于子任务GT1-1的资源评价函数，发现a1优于a2，故a1是GT1-1的调度目标。其执行完成后所处的时刻为25，也是GT1-2的开始调度时刻；对于GT1-2，需要资源类型为B的资源，SP1将其发送给SP2进行分布式调度。由于其3次循环后的时刻不能超过120，故每次执行时间不能超过在网格社区B中，同时满足其时间、费用QoS参数要求的只有b2一个节点，SP2调度GT1-2到b2上执行。GT1-2执行完成后，所处的时刻为115，累积费用消耗为 72；对于 GT1-3，将被发送到 SP4进行分布式调度。其执行时间不能超过160-115=45，d1、d2均能满足其QoS参数要求。SP4计算它们的资源评价函数，Id1=为GT1-3的调度目标。当GT1-3执行完成后，GT1便执行完毕。GT1执行完毕后，所处的时刻为155，消耗的总执行时间为155，总费用为112。
图7 网格调度Petri网模型的可达任务图
表3 网格任务（子任务）的QoS约束
表4 网格任务（子任务）的执行时间估计值
表5 网格任务（子任务）的执行费用估计值
对于GT2，因其费用权重为0.7，用户更看重执行费用。SP3接收GT2后，按照其对资源类型的要求将其分解为4个具有相互依赖关系的子任务：GT2-1、GT2-2、GT2-3、GT2-4。对于GT2-1，需要A类型的资源，SP3将其发送给SP1，其开始时刻为60，截止期限为100，故执行时间不能超过40。SP1进行集中式查询发现，a1、a2均能满足GT2-1的时间、费用等QoS参数要求，计算a1、a2相对于子任务GT2-1的资源评价函数，发现a2优于a1，故a2是GT2-1的调度目标。GT2-1执行完成后所处的时刻为 60+38=98；此后，因 GT2-2、GT2-3是并行任务且分别需要B类型和C类型的资源，故可以在SP2、SP3处进行并行调度。对于GT2-2，SP2进行集中式查询发现b1、b2能满足其QoS参数要求且b1的资源评价函数优于b2，GT2-2被调度到b1上执行；对于GT2-3，SP3管理的社区中只有c1一个节点且它是GT2的提交节点，对应于GT2-3的执行费用为0。它能在截止期限内完成子任务GT2-3、GT2-3被调度到c1上执行；只有当GT2-2、GT2-3都顺利执行完成后，GT2-4才能获得调度机会，此时刻为60+38+92=190。由于其截止期限为240，故其执行时间限制为240-190=50，它需要D类型的资源，SP4管理的社区中只有d2能满足其QoS参数要求，GT2-4被调度到d2节点上执行。当GT2-4执行完成后，GT2便执行完毕。GT2执行完毕后，所处的时刻为238，消耗的总执行时间为178，总费用为94。
（2）资源节点 a1、a2、b1、b2、b3、c1、d1、d1执行所有任务（子任务）所用的时间分别为：se1=25，se2=38，se3=28，se4=90，se5=0，se6=92，se7=40，se8=48。它们的平均数为 μ=45.1，标准差S=29.6，离散系数v==0.66。由命题5知，系统目前的负载平衡状态较差，主要是因为目前统计的时间段短，子任务数量比较少，以致资源节点忙闲程度不同。相信在长时间的观察统计中，系统的负载平衡特性会处于良好状态。
（3）可达任务图有 2 个端点：M112、M213。系统的吞吐量为2。目前整个系统执行完所有任务后所处的时刻为max{155，238}=238，所消耗的总费用为：112+94=206。
6 结束语
本文针对资源节点基于语义相似度聚类的超级节点模式网格，提出网格协作型任务的面向用户时间、费用及二者偏好参数等多QoS约束的调度算法，并运用价格时延Petri网对调度过程进行建模，构造并分析可达任务图，实例验证算法的有效性。将子任务的传输过程、资源分配状况以及每一步产生的时延、费用等信息通过标识的形式反映在可达任务图中，便于观察、统计及分析任务的详细调度过程。下一步的工作重点是进一步优化调度算法。
参考文献
1 Kurve A,Griffin C,Miller D J,et al.Optimizing cluster formation in super-peer networks via local incentive design.Peer-to-Peer Networking and Applications,2013(4)
2 Liu M R,Koskela T,Ou Z H,et al.Super-peer-based coordinated service provision.Journal of Network and Computer Applications,2011,34(4):1210～1224
3 Hassan M I,Abdullah A.Semantic-based grid resource discovery systems a literature review and taxonomy.Proceedings of International Symposium in Information Technology(ITSim),Kuala Lumpur,June 2010
4 吴健，吴朝晖，李莹等.基于本体论和词汇语义相似度的Web服务发现.计算机学报，2005，28(4):595～602
5 曹洁，曾国荪，钮俊等.云环境下可用性感知的并行任务调度方法.计算机研究与发展，2013，50(7):1563～1572
6 倪晚成，刘连臣，吴澄等.基于概念关联程度的网格服务组合方法.清华大学学报，2007，7(40):1581～1585
7 Tan Y H,LüK,Lin Y P.Organisation and management of shared documents in super-peer networks based semantic hierarchical cluster trees. Peer-to-Peer Networking and Applications,2012,5(3):292～308
8 Garbacki P,Epema D H J,Steen M.The design and evaluation of a self-organizing superpeer network.IEEE Transactions on Computers,2010,59(3):317～331
9 Doulkeridis C,Vlachou A,Norvag K,et al.Efficient search based on content similarity over self-organizing P2P networks.Peer-to-Peer Networking and Applications,2009,3(1):67～79
10 Ayorak E,Bener A B.Super peer web service discovery architecture.Proceedings of IEEE the 23rd International Conference on Data Engineering,Istanbul,Turkey,2007:1360～1364
11 朱海，王宇平.融合安全的网格依赖任务调度双目标优化模型及算法.软件学报，2011，22(11)
12 Li J,Vuong S.A scalable semantic routing architecture for grid resource discovery.Proceedingsofthe 11th InternationalConference on Paralleland Distributed Systems,Fukuoka,Japan,2005:29～35
13 Lser A,Naumann F,Siberski W,et al.Semantic overlay clusters within super-peer networks.Databases,Information Systems and Peer-to-Peer Computing,2004(2944):35～38
14 Hassan M I,Abdullah A.A semantic description and registration framework for large grid resource discovery systems.Computer Science Letters,2009,1(1)
15 Hassan M I,Abdullah A.A new grid resource discovery framework.The International Arab Journal of Information Technology,2011,8(1):99～107
16 熊曾刚，杨扬，曾明.基于Petri网的两阶段网格任务调度模型与分析.通信学报，2009，30(8):69～77
17 孙瑞志，杨璐，欧阳娅.基于改进遗传算法的网格任务调度.解放军理工大学学报（自然科学版），2012，13(4)
18 Jensen K.Colored Petri Nets:Basic Concepts,Analysis Methods and Practical Use.Berlin:Springer,1996
19 刘卫东，宋佳兴，林闯.基于价格时间Petri网的网格计算应用模型及分析.电子学报，2005，33（8）： 1416～1420
