随着互联网的迅速发展,网络信息资源呈现出三种特征:网络信息量非常庞大;网络信息的语义化;信息以多种不同的语言分布在Web页面和数据库中。传统的信息处理技术已无法高效地处理如此庞大的、语义化的多语言信息,需要新的技术和方法来解决这一问题。语义网格^{[ 1]}是解决这一问题的有效途径。语义网格是结合了网格计算^{[ 2]}及语义Web^{[ 3]}而提出的一个新概念,其目的是利用语义Web与网格技术,为互联网提供一个基于语义面向服务的分布式共享基础架构,以支持自治的异构应用之间的无缝集成、语义互操作和各种自动化任务,使用户可以共享用任何语言描述的信息和知识。

信息检索是目前人们获取网上信息资源使用最多也是最主要的一种技术,因此,多语言信息检索成为研究的热点问题^{[ 4, 5, 6, 7]}。但作为多语言信息检索重要组成部分的多语言信息资源调度却鲜有研究。多语言信息资源调度的关键问题有调度流程的描述与分析、调度模型与算法等。由于语义网格环境下的多语言信息资源具有分布、异构、动态、自治等特点,所以其调度极其复杂,因而需要一个有力的图形与数学工具来对它进行描述与分析,这样既可以用图型直观地描述语义网格环境下多语言信息资源调度流程,又可以借助于数学方法来分析、评价与验证多语言信息资源调度的正确性、可靠性与有效性。Petri网^{[ 8]}作为一种模拟与分析具有并发、异步、动态等特点的信息处理系统的形式化模型,是描述与分析语义网格环境下多语言信息资源调度的理想工具。本文的主要工作是用有色时延Petri网模型对语义网格环境下的多语言信息资源调度进行描述与分析,从而分析、评价与验证多语言信息资源调度的流程设计的正确性、可靠性与有效性。

自2001年语义网格的概念被提出以后,国内外关于语义网格的研究就陆续展开。关于语义网格的研究,英国走在世界前列,投入巨资于e-Science计划,开发了CoAKTinG项目。美国在国家科学基金资助下开发了SCEC/IT项目。中国在973项目资助下,开展了语义网格基础理论、模型与方法的研究,提出了基于分类语义的资源空间模型、基于关系语义的语义链网络模型以及语义链的自动发现机制;建立了资源空间模型到语义链网络的映射、语义链的代数模型;提出了对等知识流模型^{[ 9]}。在数字图书馆应用方面,文献[10]研究了基于元数据本体的数字图书馆系统间的互操作问题,文献[11]构建了一个4层体系架构的智能化数字图书馆知识推送服务系统模型。

语义网格环境下的资源调度研究目前还很少,但网格环境下的资源调度已有大量研究^{[ 12, 13, 14, 15, 16, 17, 18]}。资源调度方案主要有集中式、层次式与分布式三种^{[ 12]}。资源调度算法主要有基于调度时间的最小化和负载平衡化,基于用户的服务质量(Quality of Service,QoS)和基于经济理论的资源调度算法以及基于基因算法、模拟退火算法、蚂蚁算法等资源调度算法^{[ 13, 14, 15, 16, 17, 18]}。

早在1995年Van der Aalst就对调度问题的Petri网建模与分析进行了系统的研究^{[ 19]},用时延Petri网(Timed Petri Nets)模拟与分析了调度问题,提出了一种将任务、资源和限制映射到时延Petri网的方法。近几年,部分学者对网格计算环境下资源调度的Petri网建模与分析展开研究。文献[20]利用层次颜色Petri网和颜色时延Petri网分别对网格任务调度进行建模。文献[21]为网格调度建立了带抑制弧的广义随机Petri网。文献[22]运用变迁使能优先级、抑制弧、可实施谓词等Petri网冲突解决方法实现不同资源运用策略建模。文献[23]使用有色Petri 网对网格调度系统和Sufferage算法进行了建模和仿真分析。笔者也对网格计算环境下资源调度的Petri网建模与分析开展了系列研究,并取得一定成果^{[ 12, 24]},先后使用有色Petri网、时间Petri网、时延Petri网、Petri网的合成与化简等对网格调度系统进行了建模和分析。

上述用Petri网对资源调度的建模和分析,有的没有体现网格资源的动态性,有的不能描述信息资源的多语言性。本文给出的语义网格环境下多语言信息资源调度的有色时延Petri网模型,用颜色表示语言种类,并且变迁发生的持续时间是其前集位置中标识的一个函数,因而既可以描述信息资源的多语言性,又可以体现网格资源的动态性。

基于层次化方法,给出语义网格环境下多语言信息资源调度的体系结构,如图1所示:

图1

	Figure Option ViewDownloadNew Window
	图1 语义网格环境下多语言信息资源

调度系统的体系结构

(1)用户接入层:该层为网格用户提供进入网格系统的方式,既面向使用PC终端通过有线网络进入网格系统的固定用户,也面向使用手机、PDA等移动终端通过无线网络进入网格系统的移动用户。

(2)技术支撑层:该层为任务预处理提供所需要的技术支撑。包括对用户进入网格系统合法性的身份认证技术、对所提交的任务进行验证与优化的任务处理与建模分析技术、为了满足多语言信息需求的机器翻译技术、为了实现语义功能的本体技术以及分布式处理技术等。

(3)调度层:该层主要提供将用户需求映射到某个或某些资源、将需求与索引数据库中存放的信息资源数据进行匹配、根据匹配结果将用户需求分配给相应的网格实体、将符合用户需求的信息资源根据用户要求对信息进行处理所需的调度算法、匹配策略、信息集成技术等。

(4)资源层:该层为整个系统的运行提供底层资源,包括物理资源(如:计算、存储、网络资源等)和信息资源(如:语料库、知识库、原始信息库等)。

图1给出的是语义网格环境下多语言信息资源调度系统的体系结构,为便于用Petri网对信息资源调度流程进行建模与分析,还应给出信息资源调度的详细流程。笔者在文献[24]中给出了网格计算环境下信息资源调度的详细流程,该流程也可用于语义网格环境下多语言信息资源的调度(故本文略去流程图),其区别主要有以下两点:在用户接口与控制模块之间增加一个请求处理模块,利用语言学、机器翻译、自然语言处理等知识,对提交的请求进行多种语言之间的语言翻译,处理后提交给控制模块;增加一个语料库和本体库,用于请求处理模块对用户所提交的请求进行多语言及语义处理。

有关Petri网的基本概念,可参见文献[8,25,26]。

定义1:设语义网格系统有n个信息资源提供者,对任一m种语言的信息请求,资源调度系统所对应的有色时延Petri 网(CTDPN)是一个7元组,CTDPN=(P, T, F, W, M₀, C, D),其中:

P={p_j|j=1,2,3,4,5,6,7,10,11}∪{p_8i, p_9i |i=1,2,…,n}是位置的有限集合;

T= {t_j|j =1,2,3,5,8}∪{t_ji|j =4,6,7; i =1,2, … ,n}是变迁的有限集合;

F⊆(P×T) ∪ (T×P) 是弧的有限集合;

C={lan}∪{ir}∪{cs}是颜色的集合,其中lan是语言种类,ir是信息资源的相关信息,cs是语料和语义信息;

W=f(F)是弧的权函数集合;

M₀为初始标记,其中M₀(p₁)={ulan}⊆{lan}为用户提交的信息请求中的语言种类,是{lan}的子集,M₀(p₃)={cs},M₀(p₅)={ir},其余位置的初始标记为空;

D是使变迁发生的持续时间,是由T到前集位置中标识的映射函数。它是对一般时延Petri网的一个扩展。在一般时延Petri网^{[ 26]},D是一个由T到有理数的映射函数,是一个常数,而这里给出的D是一个变量,它随其前集位置中标识的变化而变化。

其图形表示如图2所示:

图2

	Figure Option ViewDownloadNew Window
	图2 资源调度系统对应的Petri 网模型CTDPN

位置与变迁的说明如表1所示:

表1

表1

表1 图2中位置与变迁的描述 位置 说明 变迁 说明 发生持 续时间 p1 用户准备提交请求 t1 提交请求 0 p2 用户提交后的请求 t2 处理请求 0 p3 语料和语义信息 t3 匹配请求与资源信息 p4 处理后的请求 t4i 发送请求到第i个站点 传输 时间 p5 资源信息 t5 返回无法满足的信息 0 p6 匹配的结果 t6i 调度第i个站点的信息 执行 时间 p7 未满足的请求 t7i 返回第i个站点的信息 传输 时间 p8i 分配给第i个站点的请求 t8 处理各站点返回的信息 0 p9i 第i个站点已调度好的信息 p10 各站点返回的信息 p11 返回给用户所要求的信息

表1 图2中位置与变迁的描述

图2所示的资源调度系统所对应的Petri 网模型CTDPN中,位置p₁中的标识为用户欲提交的请求,通过变迁t₁提交给系统。位置p₂中存放用户提交后的请求,位置p₃中的标识为语料库信息。变迁t₂表示请求处理模块,将利用语料库和机器翻译、自然语言处理等技术,对提交的请求进行多种语言之间的语言翻译,位置p₄中的标识为处理后的请求。位置p₅中的标识为搜集到的各网格站点的资源信息及本体库信息。变迁t₃表示控制模块,将用户请求与收集的信息资源进行匹配,位置p₄中存放的是匹配结果。变迁t₅表示目前信息资源无法满足用户请求,本次请求失败,位置p₇中的标识是未满足的请求信息;变迁t_4i表示分配模块,根据请求和资源之间的匹配程度,将请求分配给相应的网格实体,位置p_8i中的标识为分配给各站点的可满足的请求。变迁t_6i表示执行信息调度的过程,位置p_9i中的标识为各站点已调度好的信息。变迁t_7i表示从各站点返回用户所要求的信息,位置p₁₀中的标识为返回的信息。变迁t₈表示信息处理模块,根据用户需求对返回的信息进行组织、筛选、集成等各种处理,位置p₁₁中的标识为已处理好的返回给用户的信息。

用Petri网对调度系统建模的目的,除了具有图形表示的直观性外,更重要的是通过该模型的运行,利用Petri网的性质对系统进行性能分析。为了分析系统的特性,首先要构造调度系统所对应的Petri网模型的可达调度图(Reachable Scheduling Graph,RSG),可达调度图的概念与构造方法类似于文献[12]中所给出的可达任务图。以下将图2所示的资源调度系统所对应的有色时延Petri网模型的可达调度图记为RSG(CTDPN)。在可达调度图中,对节点M加以标签“[et_ij]”,其中et_ij为产生标识M的变迁t因第i个用户的j种语言请求发生后的时刻。有向边加以标签“t/r_ij”或“t/r_i”,其中r_ij表示变迁t的发生与第i个用户的j种语言请求有关,r_i表示变迁t的发生与第i个用户的所有语言请求有关。变迁t₅和t₈发生后所对应的标识M称为端点。

命题1:假设在某一时间段内有n个用户提交请求到网格资源调度系统,其中第i个用户请求m_i种语言信息(i=1,2,…,n)。CTDPN是多语言网格资源调度系统所对应的有色时延Petri网模型,RSG是CTDPN的可达调度图,则用户i对其请求的所有语言种类的满足率为:

/m_i (1)

在该时间段内调度系统的完成率为:

( 「 /m_i⌉)/n (2)

其中,M∈RSG为端点且为变迁t₈发生后所产生的标识,符号“||”表示集合中元素的个数,符号“「⌉”表示取整数。

证明:根据CTDPN 的定义知,p₁₁中的标识为调度系统返回给用户的请求信息,若用户i所请求的第j种语言信息得到满足,则lan_ij∈M(p₁₁)。因此M(p₁₁)与集合{lan_i1,lan_i2,…,la }的交运算后的元素就是系统返回给用户i所请求的语言种类,将元素的个数记为k_i。从而得到用户i对其请求的语言种类的满足率为k_i/m_i,即公式(1)所给出的表达式。

如果用户i请求的所有m_i种语言信息均得到满足,则k_i=m_i,此时k_i/m_i=1;否则k_ii,此时k_i/m_i<1,取整后其值为0。由此得知,公式(2)中分子为所有种类的语言信息均得到满足的用户数,除以n后即为调度系统的完成率。

在调度系统中,可行性与有效性是两个重要特性。

定义2:在多语言信息资源调度系统中,一个用户的请求是可行的,当且仅当其请求的所有语言种类的满足率为100%。在某个时间段内,整个系统的调度方案是可行的,当且仅当所有用户的请求是可行的。

定义3:在多语言信息资源调度系统中,一个用户的可行请求是有效的,当且仅当其在各种可行方案中所用调度时间是最短的。在某个时间段内,整个系统的调度方案是有效的,当且仅当在所有可行调度方案中,所用调度时间是最短的。

命题2:设CTDPN是多语言网格资源调度系统所对应的有色时延Petri网模型,RSG是CTDPN的可达调度图。有效的可行用户请求调度的周转时间为Min{et_ijn}。其中et_ijn 是第i个用户请求的第j种可行方案完成后所对应的端点标识M_ijn的标签。

根据CTDPN 的定义、RSG的构造方法以及定义2和定义3,该命题的结论容易得证,故在此省略。

通过以下例子和实验对本文所建模型和给出的命题进行验证和分析。

6.1 举 例

假设一个数字图书馆语义网格系统由两个站点组成,在某一时间段内有3个用户请求该两个站点的多语言信息资源。假设在站点1能够提供语言1和语言2的信息资源,站点2能够提供语言2和语言3的信息资源。用户1请求语言1和语言2的信息资源,用户2请求语言2和语言3的信息资源,用户3请求语言3和语言4的信息资源。由于网格系统的异构性与复杂性。同一用户请求在不同站点上的信息处理与通信所需时间是不同的,具体数据如表2所示:

表2

表2

表2 例中的各项数据 用户请求 站点1 站点2 执行时间 通信时间 执行时间 通信时间 1 整体 60 80 不提供 不提供 语言1 40 50 不提供 不提供 语言2 50 60 30 40 2 整体 不提供 不提供 不提供 不提供 语言2 50 60 30 40 语言3 不提供 不提供 60 90 3 整体 不提供 不提供 不提供 不提供 语言3 不提供 不提供 70 100 语言4 不提供 不提供 不提供 不提供

表2 例中的各项数据

根据定义1,构造出语义网格多语言信息资源调度系统所对应的有色时延Petri网模型CTDPN,类似于图2(其中n=3)。然后构造CTDPN所对应的可达调度图RSG。3个用户的请求调度所对应的部分可达调度图如图3至图5所示:

图3

	Figure Option ViewDownloadNew Window
	图3 用户1的请求调度所对应的部分可达调度图

图4

	Figure Option ViewDownloadNew Window
	图4 用户2的请求调度所对应的部分可达调度图

图5

	Figure Option ViewDownloadNew Window
	图5 用户3的请求调度所对应的部分可达调度图

(1)对于第1个用户,其请求的语言种类为语言1和语言2。从图3得知,t₈发生后,产生了标识M₇和M₁₃两个端点,且M₇(p₁₁)和M₁₃(p₁₁)均包含语言1和语言2,所以由命题1知,该用户请求的所有语言种类的满足率为100%,再由定义2知,请求是可行的。由可达调度图的定义、定义3、命题2及图3知,该用户的有效请求为从站点1上获取语言1、站点2上获取语言2的信息,有效调度的周转时间为min{200,140}=140。

(2)对于第2个用户,其请求的语言种类为语言2和语言3。从图4得知,t₈发生后,只产生M₉一个端点,且M₉(p₁₁)包含语言2和语言3,所以由命题1知,该用户请求的所有语言种类的满足率为100%。因为只有一种可行调度方案,所以由定义3知该调度也是有效的,其周转时间为240。

(3)对于第3个用户,其请求的语言种类为语言3和语言4。从图5得知,t₈发生后,只产生M₉一个端点,但M₉(p₁₁)只包含语言3,所以由命题1知,第3个用户请求的所有语言种类的满足率为50%,由定义2知,该用户的请求是不可行的。从而由定义3知,该用户也不存在有效调度。

通过上述分析,由命题1知,在某一时间段内该系统的完整完成率为2/3=66.67%,由定义2知,整个系统的调度方案是不可行的。由定义3知,该系统也不存在有效调度。

6.2 实 验

实验参数如下:站点数=3,共提供4种语言信息,分别为:站点1提供语言a和b,站点2提供语言b和c,站点3提供语言c和d。请求信息的用户数=10,这20个用户请求的信息包括a、b、c、d、e共5种语言,各用户所请求的语言种类、在各站点处理信息的时间(范围20-80)、传输时间(范围30-90)均通过编程由程序随机产生,产生的结果如表3(因表3太大,故限定用户数=10,每个用户请求的语言种类小于3)所示。

根据图2所示的Petri网模型的运行过程,并结合给出的命题,通过程序分析可得如表4所示的结果。

表3

表3

表3 实验产生的用户各项数据 用户请求 站点1 站点2 站点3 执行时间 通信时间 执行时间 通信时间 执行时间 通信时间 1 语言a 44 42 -1 -1 -1 -1 语言b 56 83 22 73 -1 -1 语言c -1 -1 46 30 51 79 2 语言a 37 81 -1 -1 -1 -1 语言c -1 -1 40 33 36 55 语言d -1 -1 -1 -1 64 34 3 语言b 30 49 67 30 -1 -1 4 语言b 62 32 49 61 -1 -1 语言c -1 -1 30 34 54 69 5 语言b 25 49 51 68 -1 -1 语言c -1 -1 55 59 49 57 6 语言a 50 39 -1 -1 -1 -1 语言c -1 -1 42 41 46 81 语言d -1 -1 -1 -1 61 56 7 语言b 54 74 61 78 -1 -1 语言c -1 -1 29 85 44 74 语言d -1 -1 -1 -1 28 73 8 语言c -1 -1 61 69 26 74 语言d -1 -1 -1 -1 57 85 语言e -1 -1 -1 -1 -1 -1 9 语言a 44 30 -1 -1 -1 -1 10 语言c -1 -1 65 57 30 43 语言d -1 -1 -1 -1 67 65 语言e -1 -1 -1 -1 -1 -1 (注:表中-1表示该站点不提供此种语言信息。)

表3 实验产生的用户各项数据

表4

表4

表4 实验得出的分析结果 用户请求 满足率% 是否可行 有效调度 调度方案 周转时间 1 100 是 1a‖2b‖3c 209 2 100 是 1a‖2c-‖3d 199 3 100 是 2b 127 4 100 是 1b‖2c 126 5 100 是 2b‖3c 163 6 100 是 1a‖2c-‖3d 173 7 100 是 1b‖2c‖3d 202 8 66.67 否 No -1 9 100 是 1a 104 10 66.67 否 No -1 (注:表中调度方案中数字表示站点号;字母表示语言种类;“‖”表示并行调度,如“1b‖2c”表示b语言信息从站点1调度,c语言信息从站点2调度,且这两种语言信息可以在两个站点并行调度;-1表示不存在有效调度。)

表4 实验得出的分析结果

从表4可以看出,这10个用户请求除8和10(满足率为66.67%)外,其余满足率均为100%,由定义2和定义3知,用户请求8和10为不可行请求,也是无效请求,他们也不存在有效调度序列。其余8个用户请求均为可行请求,它们的有效调度序列与有效调度的周转时间见表4。由命题1知,该系统针对这10个用户请求的完成率为80%。

本文给出了语义网格环境下多语言信息资源调度架构,利用有色时延Petri网对多语言信息资源调度流程进行了建模与分析。利用可达调度图,对多语言信息资源调度流程进行了正确性、可靠性与有效性分析。通过数字图书馆语义网格系统举例及程序模拟可以看出,利用Petri网对语义网格环境下多语言信息资源调度进行建模与分析,可以直观、形象地看出其调度过程,并能从数学角度对多语言信息资源调度系统中的一些重要特性进行定量分析。进一步的工作是探讨有效的语义网格环境下多语言信息资源调度算法,并对调度系统做进一步的详细模拟。