基于价格时延Petri网的超级节点网格调度

doi:10.3969／j.issn.1000-0801.2013.11.009

摘要/Abstract

摘要：

针对资源节点基于语义相似度聚类的超级节点模式网格，提出了一种面向用户截止时间、费用上限及二者之间偏好参数等QoS参数约束的网格协作型任务调度算法，其中考虑资源的动态性，引入重调度机制。然后，采用价格时延Petri网这一图形与数学工具，对复杂的调度过程进行形式化、层次化建模，增进对调度系统的理解。构建调度模型的可达任务图，分析调度系统的诸如调度时间、费用、吞吐量、负载平衡等重要性能。实例验证调度算法的有效性，分析了需要协调多种类型资源的网格协作型任务的调度过程及调度系统的若干重要特性。研究内容对于指导实际超级节点模式网格系统的开发、部署均具有重要意义。

关键词: 网格调度, 超级节点, QoS参数, 价格时延Petri网

Abstract:

For grid of super-peer model where nodes were clustering together by means of semantic similarity, a compound task scheduling algorithm was proposed which taking users' time deadline, cost limit and the weight parameters between them as QoS requirements. Considering grid nodes were dynamic, the rescheduling mechanism was introduced. Price timed Petri net which was a powerful graphical and mathematical tool was used to formally and hierarchically model grid scheduling, in order to have better understanding about it. Reachable task graph of Petri net model was constructed to analyze scheduling performance, such as scheduling time, cost, throughout capacity and load balance, etc. Effectiveness of the scheduling algorithm was verified by an example, scheduling process of compound tasks which need several types of resources and the system's scheduling performances were analyzed. Related work had great significance on guiding the construction and implement of real grid systems of super-peer model.

Key words: grid scheduling, super-peer, QoS parameter, price timed Petri net

潘善亮,黄希,茅琴娇. 基于价格时延Petri网的超级节点网格调度[J]. 电信科学, 2013, 29(11): 52-59.

Shanliang Pan,Xi Huang,Qinjiao Mao. Grid Scheduling of Super-Peer Model Based on Price Timed Petri Net[J]. Telecommunications Science, 2013, 29(11): 52-59.

图/表 12

图1

图2

图3

表1

图4

表2

图5

图6

图7

表3

表4

表5

参考文献 19

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. Proceedings of the 11th International Conference on Parallel and 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

变迁	含义简介	时延，价格
t₁	用户在资源节点向本地Super-peer提交任务	0,0
t₂	判断任务是否可以根据资源类型进行分解	0,0
t₃	从元任务集合里选择任务待调度	0,0
t₄	将协作型任务分解为子任务	0,0
t₅	选择将要调度的子任务	0,0
t₆	判断任务（元任务或子任务）所需资源类型为本地还是远程的	0,0
t₇	集中式调度子网向分布式调度子网发送任务	0,0
t₈	为任务查询本社区资源	0,0
t₉	将任务调度到本社区某一资源节点	0,0
t₁₀	本社区某一资源节点在执行任务	a,b
t₁₁	返回任务的执行结果	0,0
t₁₂	从分布式调度子网接收远程任务	0,0
t₁₃	为远程任务查询本社区资源	0,0
t₁₄	将远程任务调度到本社区某一资源节点	0,0
t₁₅	某一资源节点正在执行远程任务	a,b
t₁₆	将远程任务的执行结果返回给分布式调度子网	0,0
t₁₇	本社区内某一资源节点发生故障	0,0
t₁₈	为远程任务生成一个含有错误报告的执行结果	0,0
t₁₉	为本地任务生成一个含有错误报告的执行结果	0,0

库所	含义说明
S₁	分布式调度子网接收到集中式调度子网发送来的待分布式远程调度的任务（元任务或子任务）
S₂	远程任务在本社区的执行结果
S₃	中继转发的任务
S₄	中继转发的任务执行结果
DIN1	此单元即是集中式调度Petri网中的COUT单元
DOUT1	此单元即是集中式调度Petri网中的CIN单元
DIN2	接收从远程超级节点发送来的信息的单元，即是定义2中的s_i1
DOUT2	向远程超级节点发送信息的单元，即是定义2中的s_i2

任务/子任务	到达时间	截止期限	费用上限	α	β
GT₁	0	160	140	0.6	0.4
GT_1-1	0	30	20
GT_1-2/3次		120/3次循环后	25/次
GT_1-3		160	45
GT₂	60	240	190	0.3	0.7
GT_2-1	60	100	25
GT_2-2		195	30
GT_2-3		195	90
GT_2-4		240	45

	a₁	a₂	b₁	b₂	b₃	c₁	d₁	d₂
GT₁
GT_1-1	25	23	-	-	-	-	-	-
GT_1-2/3次	-	-	26/次	30/次	34/次	-	-	-
GT_1-3	-	-	-	-	-	-	40	38
GT₂
GT_2-1	36	38	-	-	-	-	-	-
GT_2-2	-	-	28	31	35	-	-	-
GT_2-3	-	-	-	-	-	92	-	-
GT_2-4	-	-	-	-	-	-	52	48

	a₁	a₂	b₁	b₂	b₃	c₁	d₁	d₂
GT₁
GT_1-1	0	18	-	-	-	-	-	-
GT_1-2/3次	-	-	30/次	24/次	28/次	-	-	-
GT_1-3	-	-	-	-	-	-	40	44
GT₂
GT_2-1	24	22	-	-	-	-	-	-
GT_2-2	-	-	28	29	32	-	-	-
GT_2-3	-	-	-	-	-	0	-	-
GT_2-4	-	-	-	-	-	-	43	44