网络演算

网络演算（精选7篇）

网络演算 篇1

0 引 言

近些年来,随着Internet的迅速发展,数据、视频、语音和多媒体业务应用越来越普及。由于每种业务都有各自不同的业务特性和QoS(服务质量)要求,使得QoS问题越来越突出。网络QoS一直是现今研究的热点,合理高效地分配网络带宽资源是提高网络QoS的有效手段。为了更加准确地为各业务分配合适的带宽,对业务的带宽需求研究是一项重要的工作。

统计网络演算[1,2]是最近几年在国外发展起来的一门网络分析理论,它提供一种简单明了的方法来计算网络的服务性能,并且为网络研究提供了一个正确有效的性能分析模型,主要用来定量求解网络性能的统计边界。统计网络演算具备了从理论上分析QoS控制机制所必需的业务流的流量特性模型、路由器的调度策略及性能界限这3个基本要素,广泛应用于网络QoS性能分析中。双漏桶模型[3]是一种典型的流量描述模型,是对网络流量监控和整形的首选模型,是实现网络公平性、可靠性和高效性的保障。本文将使用统计网络演算理论对满足双漏桶模型的业务流量带宽需求进行研究。

1 统计网络演算

统计网络演算是在确定网络演算[4]的基础上演变而成的,通常网络业务能容忍一定程度的数据丢失和延迟,使用统计网络演算可以较好地利用网络中的复用增益来提高资源利用率,并且更好地反映现今网络的动态综合服务能力。

统计网络演算基本模型如图1所示,它的两个主要工具是统计到达包络和统计服务曲线[5],网络性能统计边界的估计分析就是靠这两个工具来实现的。使用统计网络演算一般需要建立3个模型,分别为网络的业务流量模型、节点服务模型和性能统计边界模型。根据网络的流量模型,可以得出一般流量的统计到达包络,其物理意义表达的是网络流量到达过程概率上界;使用统计服务曲线建立网络的服务策略显示了系统给予服务量的概率下界。运用这两个工具建立网络的性能统计边界模型,对网络的性能进行精确分析。

统计网络演算可以直观简洁地对网络业务的时延性能进行研究,这在网络时延性能分析方面有着巨大的优势。给定一个流的到达过程A(t)的统计到达包络Gεg,违背概率εg;给予统计服务曲线Sεs,违背概率εs;同时有满足条件的时间尺度T。令ε=εs+Tεg,则得到的统计时延边界有以下性质[6]:时延上界dmax=inf{d≥0|∀t≥0:Gεg(t-d)≤Sεs(t)}。∀t≥0,时延概率边界W(t)满足

undefined

2 双漏桶模型

为了更好地描述业务量特性,通常引入流量限制模型,如漏桶模型、令牌桶模型[7]和双漏桶模型等。双漏桶模型是一种典型的流量描述模型,它由一个令牌桶和一个漏桶相连而构成,如图2所示。当通信量到达令牌桶时,若桶中的令牌总量大于到达的通信量,通信量被允许进入漏桶;否则,通信量存储在缓冲区中等待令牌。令牌桶中的令牌以平均速率a产生,大小为b(网络允许的突发长度)。当令牌桶满时,新产生的令牌被丢弃。漏桶用来保证输出的速率不会超过网络允许的峰值速率v(v≥a)。

设f(τ)为流量限制函数,它是非负和非递减函数;A(t)是t时刻的网络流量,经过一段时间τ后的通信累积流量为A(t+τ),且

undefined

一个传输流经过参数为(v,b,a)的双漏桶整形后,其通信量限制函数可以表示为

3 带宽需求研究

在现实网络中,各业务的带宽需求与业务QoS有关,QoS对时延的要求与带宽紧密联系在一起,业务的服务带宽越大,时延就会越小。使用统计网络演算可以直观简洁地对网络各业务的时延性能进行分析,根据时延与带宽的关系,若已知各业务流量的时延性能要求,通过这个特性就可以对各业务在统计服务性能下的带宽需求进行计算分析。

3.1 整体研究思路

业务与网络相比,后者较为固定且能在一段较长的时间内保持稳定。对于一个给定的通信网络,从统计的角度看,其链路容量和调度策略大体是不变的。而网络中运行的业务类型在大量统计的情况下也是基本稳定的。我们从业务和网络两方面出发,具体思路如图3所示。从业务的流量模型确定统计到达包络Gεg(t);从网络出发,由链路容量和网络节点的调度策略可确定出所提供的统计服务曲线Sεs(t);最后结合业务所给的可容忍时延,根据统计网络演算的统计时延边界公式,求解出满足可容忍时延下所需要提供的服务速率,即为所需带宽。

3.2 单节点的网络带宽需求

图4所示为采用单节点网络模型,使用多业务输入共享链路输出的网络结构。不同业务进入不同缓冲区队列,调度器对各队列业务进行服务调度共享输出链路带宽。业务流为满足双漏桶规范的业务流量模型。同时,不管网络采用何种队列调度算法都可以假定每个节点对数据流提供参数为(R,T)的速率—延迟服务曲线作为对数据流的QoS保证,即业务流i(i=1,2,3…)的统计服务曲线为Sundefined(t)=Ri(t-Ti),其中Ri为业务流i所分配的服务速率。下面就对双漏桶业务模型的带宽需求进行具体分析。

每个业务流的到达过程都满足双漏桶模型,可知业务流i在[0,t]时间内的到达流量满足

undefined

取统计到达包络为

undefined

因为所取统计到达包络为双漏桶流量的限制包络,由双漏桶得特性可知,流量不可能超出这个限制流量,故此处的εg=0。

为了方便计算,对时延界公式进行变换,可得

undefined

对统计到达包络和统计服务曲线的关系式取等式。根据统计到达包络分情况进行讨论,最终得出在t=bi/(vi-ai)时取得最大值,即

undefined

若已知每种业务流的可容忍时延,就可以根据以上分析的时延上界,反过来求出对应服务曲线中的服务速率。对式(7)进行推导变换得

undefined

即通过上式就可求解出满足双漏桶模型的业务带宽需求。

3.3 端到端的带宽需求

采用N个节点串联的端到端网络,同样每个节点均为多业务输入共享链路输出的网络结构。业务流i在第j个节点的统计服务曲线Sεsij(t)=Rundefined(t-Tundefined)。由定理1可知,业务流i的统计网络服务曲线[6]为

undefined

违背概率εS可表示为

undefined

使用速率-延迟服务曲线代入可得到统计网络服务曲线为

undefined

由于统计服务曲线的串联等效作用,易于从单节点扩展到端到端网络,把上式的统计网络服务曲线代入式(6),替换单节点中的统计服务曲线,就可根据业务的时延要求求解出端到端串联网络的带宽需求。

4 仿真结果及分析

(1) 双漏桶参数(v,b,a),b=1MB, a=2 MB/s,统计服务曲线违背概率εs=10-6,服务延迟T=1 ms。根据式(8), 使用Matlab软件编程实现,在已知可容忍时延d分别为10、80和200 ms时,得出峰值速率v和所需带宽R的关系如图5所示。

由图5可知,随着双漏桶峰值速率的增大,所需带宽也在增大。随着可容忍时延的增大,所需带宽增大的趋势在逐渐减小。当可容忍时延比较小时,所需带宽更能逼近峰值速率;随着可容忍时延的增大,所需带宽慢慢向平均速率逼近。

(2) 限定峰值速率v=5MB/s,以平均速率a为变量,其他条件不变,在可容忍时延d分别为10、80和200 ms时,平均速率a与所需带宽R的关系如图6所示。

由图6可知,随着双漏桶的平均速率的增大,所需带宽也在增大,增大的趋势是凸函数,带宽随平均速率的增加比较急剧。同样可知,当可容忍时延愈小时,所需带宽更逼近于峰值速率;当可容忍时延较大时,所需带宽逼近于平均速率。

(3) 限定平均速率a=2MB/s,峰值速率v=5 MB/s,以令牌桶容量b为变量,其他条件不变,在可容忍时延d分别为10、80和200 ms时,令牌桶容量b和所需带宽R的关系如图7所示。

由图7可知,随着令牌桶容量的增大,所需带宽也在慢慢增大,增大的趋势是凹函数,带宽的增加比较平缓。可以看出,可容忍时延愈小时,所需带宽更逼近于峰值速率,当可容忍时延较大时,所需带宽逼近于平均速率。

5 结束语

针对双漏桶模型限制流量的特点,使用统计网络演算对其带宽需求进行了研究分析。根据流量的时延要求得到所需带宽大小,以此为根据来提供更加合适的带宽。一般情况下,网络都是根据业务流的峰值速率大小来提供带宽的,这样会使网络过于优化而造成资源浪费。对业务流的带宽需求进行准确估计,可为网络带宽资源分配和接纳控制提供重要的理论依据,同时对提高网络资源利用率和保障网络QoS有重大意义。

参考文献

[1]Burchard A,Liebeherr J,Patek S D.A min-plus cal-culus for end-to-end statistical service guarantees[J].IEEE Transactions on Information Theory,2006,52(9):4105-4114.

[2]Boorstyn R R,Burchard A,Liebeherr J,et al.Statis-tical service assurances for traffic scheduling algo-rithms[J].IEEE J Sel Areas Commun,2000,18(12):2651-2664.

[3]庞斌,邵怀荣,高文.区分服务网络基于测量的接纳控制方案的设计与应用[J].计算机学报,2000,26(3):257-263.

[4]CRUZ R L.A calculus for network delay,part I and II[J].IEEE Transactions on Information Theory,1991,37(1):114-121.

[5]LEBOUNDEC J Y,THIRAN P.Network Calculus[M].London,Britain:Springer Verlag,2004.

[6]LI Chengzhi,BURCHARD A,LIEBEHERR J.Anetwork calculus with effective bandwidth[J].IEEEACM Transaction on Networking,2007,15(6):1442-1453.

[7]TANENBAUM ANDREW S.计算机网络[M].熊桂喜,王小虎,译.北京:清华大学出版社,2002.

网络演算 篇2

以太网由于传输速度快、开放程度高和价格便宜等优点, 已经成为工业控制网络的首要选择, 随着交换式以太网技术的引入, 通过全双工通信和微网段的划分, 大大提高了以太网的性能和时间的确定性, 不再受限于带冲突检测的多路访问侦听技术 (CSMA/CD) 的工作方式[1]。

相比于传统的排队论思想分析网络时延上限[2], 网络演算理论中的到达曲线和服务曲线[3]可以系统地分析缓冲区调度和网络时延等一些基本属性。目前, 基于网络演算对交换式以太网性能的分析取得了一定成果。Georges等[4,5]只是通过简单地叠加各元件的时延来计算端到端的时延, 没有采用服务曲线的概念。张奇智等[6]在交换机提供优先级服务的条件下计算时延, 但没有对缓存器大小进行分析。胡晓娅等[7]只是针对了特定的FIFO调度算法, 去计算实时业务流的最大网络时延。

1 优先级调度模型

在交换式工业以太网中需要传输各种实时和非实时数据, 根据截止期的不同将其分为以下4种类型的数据:周期性实时数据、周期性非实时数据、非周期性实时数据和非周期性非实时数据。

周期性实时数据:在系统运行过程中, 设备周期性采集的信息 (包括设备状态信息和测量信息等) , 这类数据被赋予最高的优先级4。周期性非实时数据:在工业现场采集的一些视频或音频等信息, 优先级为2。非周期性实时数据:指一些对时间有严格要求的非周期性信息, 如报警信息等, 优先级仅次于最高优先级, 级别为3。非周期性非实时数据:主要指那些对时间要求不严格的信息, 如系统配置信息等, 被赋予最低优先级1。

系统基本模型如图1所示, 交换机内部的优先级调度模型如图2所示。

为了保证源端数据的实时性, 对实时数据进行了流量控制, 根据进入网络的4类数据的优先级, 限制其到达曲线分别为f4 (k) =F4 (vk, φk) , f3 (k) =F3 (vk, φk) , f2 (k) =F2 (vk, φk) , f1 (k) =F1 (vk, φk) , 其中k表示发送站的编号;vk和φk分别表示源端业务流平均传输速率的最大值和业务流在传输过程中的最大爆发量。

同时, 约定只有当高优先级数据队列里面的数据为空时, 才可以传输低优先级的数据, 数据队列里的数据按照FIFO算法进行调度传输。

2 聚合流中时延和缓冲区的计算

首先, 以聚合流作为研究对象, 假设任一聚合流ψ (i) 的优先级为λ (i) , 作如下定义:其中ζ (i) ={λ (j) λ (i) =λ (j) }是与ψ (i) 优先级相同的聚合流, ζH (j) 是比ψ (i) 优先级高的聚合流, 优先级为λ (j) , Hζ (j) 表示ζH (j) 和ψ (i) 混合聚合而成的聚合流, 优先级为λ (i) 的数据流到达曲线为αi (t) =vit+φi (vi表示业务流传输的最大速率, φi表示最大爆发量) , 则聚合流ψ (i) 和ζH (j) 的总到达曲线为:Aψ (i) (t) =∑αi (t) , AζH (j) (t) =∑αj (t) 。

以任一聚合流ψ (i) 为考察对象, 设交换机的总服务能力为M, 则提供给所有业务流的总服务曲线为β (t) =M[t-0]+, 交换机提供给Hζ (j) 的服务曲线为 (式中, Lmax为优先级最低的聚合流中最长数据帧) , 据此可推导出任一聚合流ψ (i) 的服务曲线为[6]:

则聚合流ψ (i) 的服务速率和服务时延参数分别为:

聚合流ψ (i) 所需的端口缓冲区大小为:

3 微数据流中时延和缓冲区的计算

这里以聚合流里的单个微数据流作为研究对象, 所有微数据流在交换机内部都采用FIFO调度算法, 定义任一聚合流ψ (i) 内部的微数据流为ε (k) (k为微数据流的编号) , 则交换机提供给微数据流ε (k) 的服务曲线为[8]:

式中, θ为小于或等于t的任意时刻, 令t=θ, 有:

结合上述公式的推导, 可以得出以下结论:

则任一聚合流里面的微数据流ε (k) 的服务速率和服务时延参数为:

微数据流所需的缓冲区大小为:

4 结束语

结合网络演算理论, 对采用优先级调度机制的交换式工业以太网进行了实时性分析, 同时为了确保数据的实时性, 对源节点的业务流进行了流量控制, 得出了计算最大传输时延和端口缓冲区大小的精确表达式。伴随着网络演算理论的进一步发展, 下一步应该结合网络演算理论对以太网的服务质量进行系统的分析, 找出通用的精确表达式, 为交换式工业以太网的设计提供系统性的理论参考依据[9,10,11,12]。

摘要：为了保证业务流在交换式工业以太网中传输的实时性, 在交换机中引入了优先级调度机制, 对源节点的业务流数据进行了流量控制。结合网络演算理论对交换式工业以太网的实时能力进行了分析, 计算出交换机对不同数据类型的服务曲线, 通过推导出的服务曲线计算出实时数据的最大网络时延和缓冲区大小, 对考察交换式工业以太网的服务质量提供了一定的参考价值。

关键词：网络演算理论,时延,缓冲区,交换式工业以太网

参考文献

[1]胡晓娅.基于交换式以太网的网络控制系统研究[D].武汉:华中科技大学, 2006:21-24.

[2]王涛.基于交换式以太网的列车通信网络实时性研究[D].北京:北京交通大学, 2014:21-47.

[3]张连明, 陈志刚, 黄国盛.网络演算理论及应用研究[J].计算机工程与应用, 2006, 27:8-11, 173.

[4]Georges J P, Rondeau E, Divoux T.Evaluation of Switched Ethernet in an Industrial Context by Using the Network Calculus[C]∥Proceedings of the 4th IEEE International Workshop on Factory Communication Systems, Vsters, Sweden, 2002:19-26.

[5]Georges J P, Divoux T, Rondeau E.Comparison of Switched Ethernet Architectures Models[C]∥Proceedings of the 9th IEEE International Conference on Emerging Technologies and Factory Automation, Lisbon, Portugal, 2003:375-382.

[6]张奇智, 张彬, 张卫东.基于网络演算计算交换式以太网中的最大时延[J].控制与决策, 2005, 20 (1) :117-120.

[7]胡晓娅, 朱德森, 汪秉文.基于网络演算的交换式以太网实时特性分析[J].计算机工程与应用, 2008 (1) :21-24.

[8]Boudec J L, Thiran P.Network Calculus:A Theory of Deterministic Queuing Systems for the Internet[M].Berlin:Springer-Verlag, 2002.

[9]马文学, 付志兵, 敦科翔.软交换调度系统设计分析[J].无线电工程, 2011, 41 (7) :13-16.

[10]王宝玺, 文运丰, 马鹏飞, 等.一种适用于自组织网的动态时隙分配算法[J].无线电工程, 2014, 44 (10) :47-51.

[11]李玉娜, 曾兴斌, 何加铭.基于交换策略的混合网络用户接入算法[J].无线电通信技术, 2012, 38 (6) :25-29.

网络演算 篇3

关键词：CopedSew,lambda演算

古典认识论和异构理论的最新进展提供了一个可行的替代万维网的选择。在我们今后的工作,将直接跳过这些结果,因为这些都是对SMPs理解后的直接结论。然而局域网并不像理论家预言的那样是无所不能的。因此,超级网页和I/O的分散/收集机制提供了一个可行的方位认证的改进方法。

我们不仅证明了分区表和传感器网络是完全不兼容的说法是错误的,同时证明了分区表和IPv6网络是可兼容。相比之下,独立冗余磁盘阵列和布尔逻辑很久以来就有着相关的联系,它们是可兼容的。现有的嵌入式和伪框架使用合成系统模拟Smalltalk。这些组合在以前的工作中尚未被确定是否可行。

在本文中,我们主要有做了3个工作。第一,我们使用多式联运对称性证明著名的冯诺依曼机均匀改进算法递归是不可枚举的。第二,我们提出了一个名为Co p ed Sew的在线算法,证明了架构和动态主机分配协议基本上是不相容的。第三,我们证明64位架构是ambimorphic,一致的和变性的。

本文的其他部分结构安排如下。我们首先是研究生产者-消费者问题。其次,我互动技术来证明DNS是可加密,协作的和具有鲁棒性这一说法是错误的。最后,我们作出结论。

2 可穿戴理论

先不考虑现实情况,我们从方法论上说明我们算法的理论可行性。我们假定,随机算法和语音IP可以用来说明这个问题。此外,我们考虑一个由n棵B-树组成的框架。结果证明,Coped Sew在方法论上是可行的。

此外,任何关于peer-to-peer配置的理论研究都明确要求RAID和IPv6是不兼容的,我们的算法也是如此。另外,我们假设Coped Sew的每个元件都是对称地部署的,且所有的组成部分间相互独立。我们以前的所有的结果都将作为这些假设的基础。

3 实现

Coped Sew是虚拟的,灵活的和可以自我学习的。虽然我们还没有进行性能的优化,但当我们完成客户端库的实现后,这应该是比较简单的。研究人员已经完全手工控制了优化编译器,为了架构和代理能实现对性能进行优化这当然是必要的。我们的实现是由60个Perl文件,一台虚拟机监视器,一个手工优化的编译器组成。由于我们的方法是图灵完全的,嵌入的操作系统的架构设计应该是相对简单的[2,1,3,4]。我们计划在公共许可证下公布我们所有的代码。

4 结果

我们的评价方法本身具有宝贵的研究价值。我们的总体评价方法的目的主要是为了证明三个假设:(1)自1967年以来,一个方法的代码复杂性并不重要,重要的是优化后的平均查找时间;(2)广域网不再关注系统的设计;(3)带宽并不重要,重要的是提高信号的信噪比时的平均功率。因为研究表明实际功率高于我们期望功率大约79%[5]。此外,与其他工作不同的是,我们决定不研究一个系统的软件架构。我们的评估方法表明,三倍的USB高速模块化技术对我们的结果是至关重要的。

4.1 硬件和软件设置

我们在这里提供具体的实验过程,不过省略了许多重要的实验细节。第一,我们配置了一个ad-hoc的仿真环境来实施各种测试,证明集体信息损失对机器学习的复杂性的影响。第二,我们把光盘驱动器空间增加了一倍来运行我们的任天堂掌机王来测试我们的网络。我们从我们的互联网集群中移出了更多的闪存,来探测我们系统从1995年以来的平均时间。第三,我们从无损覆盖网络中移出了一些RISC处理器。此外,我们还增加了更多的200MHz的Athlon XP来测试我们的项目,以便更好地理解我们的平均抽样分布簇率。通过这些改变,我们注意到,系统的静音吞吐量变大了。此外,我们为CERN的台式机增加了150MB的NV-RAM。最后,考虑到KGB的系统,我们从读取写入测试平台删除了25GB的磁带驱动器。通过这些改变,我们注意到,静音性能有所改进。

Coped Sew没有运行在商业的操作系统上,而是运行在一个我们自己的操作系统Multics(版本7.1.2,Service Pack 3)上。我们在系统中实现我们的Smalltalk服务器,还增加了极度离散的扩展[6]。我们的应用最后将作为一个嵌入式应用程序。我们的软件在X11许可的软件许可下都是可以得到的。

4.2 测试我们的方法

通过这些琐碎的配置,我们取得了很好的结果。基于这个人为的设定,我们进行了四个新的实验:(1)我们在95个节点上运行虚拟机,在2个网络节点的网络中传播,和运行在本地操作系统上的相比较;(2)我们测量NV-RAM的吞吐量作为摩托罗拉手机的RAM吞吐量;(3)我们比较Tiny OS,Le OS和微软Windows XP操作系统的触发器门的流行度;及(4)我们在自己的台式机上测试我们的方法,特别留意响应时间。当我们在10个节点的试验平台上衡量我们的E-mail和DNS吞吐量的时候,丢掉了一些早期的实验结果[7]。

现在来对最初的两个实验做最后的分析。图5中的数据,尤其证明了在这个项目上这4年的艰苦努力是浪费的。二,操作员不能错误地单独考虑这些结果。图2的关键则是关闭的反馈环路;图5显示了为什么Coped Sew的信号信噪比不衔接。

我们接下来看上面列举的图3所示的实验(1)及实验(4)。请注意如何推出编译器,而不是部署在野外的产生较少锯齿状,能再现的结果。当然,所有敏感数据在我们的Bio Ware部署上都是匿名的[3]。错误条目都被删除了,因为我们的数据点下跌出了00标准,偏离了我们的观测手段。

最后,我们讨论所有的四个实验。在图中许多的不连续性,指出了通过硬件升级改进的平均命中率。照这样看,结果只来自2个,并且没有重现。其次,操作员不能错误单独地考虑这些结果。

6 结语

我们对IPv6的评价方法特别有用。C o p e d S e w将能够成功地一次调查许多Web服务。此外,Coped Sew不能一次成功地储存许多面向对象语言。我们不仅验证移植和lambda演算可以合作来克服这一困难,同样也可以用于语音。

参考文献

[1]L.Raman,R.Karp,S.Jackson,J.Hartmanis,J.Gray,and H.Raman,"Simu-lation of rasterization,"Journal of Embedded,Wireless Communication,vol.58,pp.20-24,July1996.

[2]J.McCarthy,"On the investiga-tion of the partition table,"Journal of Cacheable Algorithms,vol.85,pp.41-52,Oct.2000.

[3]E.Maruyama,Q.Zhou,and Q.Kumar,"Deconstructing DHTs using GoarishOleate,"Journal of Automated Reasoning,vol.72,pp.1-11,Oct.1992.

[4]B.Zheng and M.F.Kaashoek,"On the study of XML,"in Proceedings of INFOCOM,Sept.1994.

[5]R.Zhao,E.Feigenbaum,C.Papadimitriou,and S.Bhabha,"Understand-ing of massive multiplayer online role-playing games,"in Proceedings of NSDI,Dec.2004.

[6]J.Fredrick P.Brooks,G.Gupta,and M.Garey,"Deconstructing XML using Laton,"Journal of Stable Technology,vol.8,pp.87-108,Nov.1999.

网络演算 篇4

要实现Web服务的自动组合，计算机需要根据一些Web服务的描述信息来自动地、动态地选取和组合服务。这些必要的信息就是Web服务的语义信息。Web服务的语义信息需要通过一种形式化的方法来描述，形式化方法的表达能力和推理能力直接影响Web服务的自动组合能否正确灵活的进行。

在人工智能中，有很多形式化的方法能够对动作(action)进行描述。一个动作可以通过输入输出参数、前提和结果等描述它的语义，来表明动作执行的前提条件、执行的对象参数和执行结果。而Web服务也具有和动作一样的特性，也有执行前提、执行参数和执行结果。因此可将Web服务看做人工智能中的动作，然后用人工智能的方法对这些动作进行形式化描述，在形式化描述的基础上进行推理来得出的服务的组合序列。情景演算(Situation Calculus)是恰恰是人工智能中的一种形式化的建模方法，有着广泛的应用。本文选择情景演算作为Web服务语义的形式化描述方法，在此基础上就能够展开形式化的推理，对Web服务进行组合。

1 情景演算

情景演算是人工智能中的一种一阶谓词演算语言，用来描述动态变化的世界，它能够将状态、状态下的动作和动作作用于状态的结果进行形式化，并推理动作的序列和结果。世界是处在不断变化的状态中的，而状态的转换是动作的执行结果，所以情景演算把世界的变化看做动作的执行序列。很多时候我们需要达到一个目标状态，但能否从现有的初始状态达到目标状态，若能达到，如何达到?这样的问题不好回答。而情景演算通过将系统目标状态和初始状态以及系统中的动作建模，能够解决这个问题，即是否能构造到达目标状态的一个动作序列。

在情景演算中，状态S定义为一系列原子动作从某个初始状态S0开始执行的动作序列。谓词流(fluents)表示和状态S相关联的函数和关系。常量S0表示初始状态，即流的初值。动作do(a,s)表示在状态S下执行动作a的后续状态。

情景演算通过动作理论D刻画变化的世界，包含动作前件公理(action recondition axiom)、动作后续状态公理(successor state axiom)等，动作理论D为如下形式：

∑：基础公理。

Dso：描述初始状态。

Duna：动作的唯一命名公理。

Dap：动作前提公理。领域中的每一个动作a都有一个对应的动作前提公理，

描述动作可以执行的前提条件。

其中π是a执行的所有前提条件。

Dss：动作后续状态公理。描述原子动作的执行如何影响流和状态的变化。

公式γF+(x,a,s)是正效果公理，描述了动作集合，使得流F的值在a执行后为真;

公式γF+(x,a,s)是负效果公理，描述了动作集合，使得流F的值在a执行后为假。

其中Poss(a,s)表示动作a在状态s下是可执行的;

这样，通过情景演算进行动作序列的计划就是：给出某个领域的动作理论D和一个目标公式Ф(s)，能否找到一组动作的序列a軃，使得：。

2 会议行程安排系统的语义描述

该会议行程安排系统具有如下功能：有某用户，要从M地到N地参加一个会议，会议行程安排系统能够为他自动安排会议行程，包括订好去的交通以及酒店房间。

系统将这个过程定义为一个常规任务。这个常规任务的流程如图1。

在这个流程中包含9个原子Web服务：

(1)InquiryDriveTime(M,N):查询从M到N的行车时间;

(2)InquiryCarInfo(M):查询M到N的长途汽车信息，返回汽车的信息;

(3)bookCar(CNum,Date1,Date2):订车号为CNum的长途汽车票，时间从Date1到Date2;

(4)InquiryHotelInfo(N):查询N地的酒店，返回酒店名称;

(5)InquiryTrainInfo(M,N):查询从M到N的火车车次，返回车次信息;

(6)bookTrain(TNum,Date):订购日期为Date，车次为TNum的火车票;

(7)InquiryFlightInfo(M,N):查询从M到N的航班，返回航班信息;

(8)bookAirline(K,FNum,Date):订购日期为Date,航空公司为K，航班号为FNum的机票;

(9)bookHotel(H,Date1,Date2):预定酒店H的一个房间，时间从Date1到Date2。

该常规任务包含顺序序列和选择两种结构。选择结构中服务((2)(3))、((4)(5))、((6)(7))只需从中选择一个执行即可。而服务(1)、(8)、(9)是顺序序列，都必须执行。用户在选择交通方式上有一定的约束，会影响执行序列，包括：(1)如果两地的行车时间小于等于3小时，则做汽车去;(2)如果两地的行车时间大于3小时，小于8小时，则坐火车去;(3)否则乘飞机去。

要实现常规任务需要对这9个Web服务进行自动的组合，根据用户的需要来选择相应的Web服务，并将不同的Web服务排列成适当的执行序列，来实现用户的会议行程安排。

下面根据情景演算语言的动作理论D，从原始动作、系统谓词流、系统初始状态、动作执行的前提公理、动作的后续状态公理、复杂动作及用户的偏好等七方面对9个Web服务进行语义描述。

1)将这9个Web服务定义为情景演算中的原始动作：

2)定义系统中的谓词流，这些谓词流描述了系统的状态，谓词流的值会随着Web服务的执行而动态改变。为订航线原子Web服务bookAirline定义四个流：

类似的,还需要为表示bookCar,bookTrain和bookHotel的前提和结果的谓词定义相应的流,此略。

3)定义系统的初始状态,系统的初始状态就是谓词流的初始值,为真或为假。

4)将Web服务执行的条件定义为动作前提公理

服务bookAirline的前提条件包括己知航空公司、航班号和出发日期,以及信用卡有效。

条件为true表示动作在任何条件下都能够执行,例如:

其它原子服务类似，此略。

5)将Web服务执行的结果定义为后续状态公理，定义动作的执行对流值的改变情况。例如，InquiryFlightInfo执行后会使得流AirCompany和FlightNo的值变为真:

6)将常规任务定义为由原子动作构成的复杂动作,即过程。

常规任务表示为由9个原子Web服务组成的过程:

7)偏好公理

偏好公理只需给出动作在什么情况下是用户不希望执行的，未给出的就是用户所希望执行的。

以上基于情景演算完成了对会议行程安排系统中原子Web服务的语义描述，在此基础上就可以进一步对Web服务进行自动组合。

3 结论

WWW原来是静态的Web页面集合，而Web服务是模块化的程序，可以部署在Web上被其他程序发现和调用，这使得使得WWW逐渐演化成开放的应用和服务平台。而Web服务要想成为计算机可以理解的程序模块，从而支持服务的自动组合，就需要用语义Web的方法来来描述服务的语义。

情景演算是一种一阶谓词演算语言，用动作的序列表示动态变化的世界，在人工智能中有很广泛的应用，因为Web服务很类似于情景演算中的动作，所以可以通过情景演算可以对Web服务的语义进行描述建模。

本文通过使用情景演算对一个会议行程安排系统的进行了语义描述和建模，清晰的描述了会议行程安排系统中的各个Web服务的语义，在此基础上，能够准确快速的根据需要对Web服务进行组合，完成用户的需要。进一步的工作可以使用GOLOG语言对情景演算建立的模型进行实现，达到计算机程序自动进行Web服务组合的目的。

摘要：Web服务是WWW发展的一个重要的趋势,Web服务的相关问题得到了广泛的研究和应用,Web服务的自动组合是其中一个热点。要实现Web服务的自动组合,必须对Web服务的语义进行形式化的描述。情景演算是一种形式化的建模和规划方法,利用情景演算对Web服务进行描述,能使自动组合结果更加快速和准确。在分析情景演算特点的基础上,使用情景演算对一个基于Web服务的会议行程安排系统进行了Web服务语义描述。

关键词：Web服务自动组合,Web服务语义描述,情景演算

参考文献

[1]邱莉榕,史忠植,林芬,常亮.基于主体的语义Web服务自动组合研究[J].计算机研究与发展,2007,(4).

[2]张佩云,孙亚民.动态Web服务组合研究[J].计算机科学,2007,(5).

[3]王杰生,李舟军,李梦君.语义Web服务的自动化组合方法:研究综述[J].计算机科学,2007,(6).

[4]史忠植,蒋运承,张海俊,董明楷.基于描述逻辑的主体服务匹配[J].计算机学报,2004,(5).

[5]任志宏.Web服务复合的若干关健问题研究[D].中国科学院研究生院(软件研究所),2004.

[6]章陶,黎亮,黄巍,李磊.情景演算及其在工作流引擎中的应用[J].计算机应用研究,,2005,(2).

网络演算 篇5

1.1 可视化BPEL编制工具

可视化BPEL编制工具是业务流程编辑工具, 对Web服务进行组合。对业务流程进行编制主要需要解决的问题是在业务流程实施之前对其进行正确性和合理性的分析, 确保业务流程高效、有序地运行。目前主流的工具有:Active BPEL Designer, Eclipse下的插件BPEL Editor, 和Oracle BPEL Process Designer。本文所采用工具为eclipse的BPEL插件。它提供了一个图形化和用户友好的方式构建BPEL流程, 为开发用户界面和协调服务提供统一的设计时环境。

1.2 pi演算介绍

在pi演算中, 进程是并发运行实体的单位, 并以名字来统一定义通道名以及在通道中传送的消息, 每个进程都有若干与其它进程联系的通道, 数据结构在这里被封装为与特定通道相关的进程, 外部进程通过这些通道来操作相关结构。pi演算有几种不同的符号表示, 基本语法可由以下BNF (Backus Normal Form) 范式给出:

2 可视化BPEL流程中基本元素与pi演算表达式的对应关系

empty活动表示不做任何活动

receive活动从流程的外部伙伴那获取数据。π-演算建模中表示通过通道client接收消息。

reply活动向的外部伙伴发送数据。π-演算建模中表示通过通道client发送消息。

invoke活动既可以接收也可以发送数据, 其中属性input指定了调用的输入参数, output返回调用结果。

throw活动:在业务流程内部产生一个异常。π-演算建模中, 通过通道t发送故障处理的消息;

3 应用实例

下面具体解释如何利用pi演算技术对用可视化BPEL编制工具实现的流程进行描述。有两个web服务, 一个为加法服务, 名为Add Service, 另外一个为减法服务, 名为Sub Service。新需求为将个Web服务集成起来, 即创建一个新的服务, 称为运算服务, 名为Caculator Service, 有一个运算类型的参数, 当运算类型为加法时, 调用加法服务, 当运算类型为减法, 调用减法服务。

总体业务流程形式化建模如下:

4 总结和展望

本文根据可视化BPEL流程编制工具实际应用中存在的问题, 提出了把可视化BPEL流程用pi演算进行描述的思想。描述了可视化BPEL流程与pi演算之间的对应关系, 并用实例说明了利用Eclipse BPEL插件建立起来的BPEL流程的pi演算描述过程。

在以上工作的基础上, 可以开始着手实现在可视化编制业务流程时能够对制作的BPEL流程自动进行正确性和合理性的分析的功能, 在eclipse BPEL插件的开源代码基础上进行开发, 以确保业务流程高效、有序地运行, 同时使得其业务流程可以在较抽象的层次上跟踪。

摘要：根据可视化BPEL流程编制工具实际应用中存在的问题, 提出了把可视化BPEL流程用pi演算进行描述的方法。明确了可视化BPEL流程与pi演算之间的对应关系, 并用实例说明了怎样把一个利用Eclipse BPEL插件建立起来的BPEL流程用pi演算进行描述的过程。

关键词：Web服务组合,可视化BPEL流程编制,Eclipse BPEL插件,pi演算

参考文献

[1]Robin M.Communicating and Mobile Systems:the-calculus[M].Fifth Printing, USA:Cambridge Press, 2004:17-91.

[2]H Smith, P Fingar.Workflow is just a Pi process[OL].http://www.bpm3.com/picalculus, 2003-12-08.

圆周率π的历史演算与历史作用 篇6

1圆周率π的历史演算

圆周率π是数学常数, 它是圆的周长和直径的比, 在社会生产与实践中应用是非常广泛的, 圆周率的演算精度在某种意义上反映国家的数学水平。

1.1通过实验演算π值

演算π值的初级阶段发生在公元前950年前后, 是通过实验为依据, 是根据对圆的周长与直径的测量演算得来。在古代人们把π等于3长期应用, 如基督教《圣经》中取π为3, 在印度、巴比伦等也长期使用π=3这个简约数值。在《周髀算经》中对圆周率π有过“圆周三径一”这样的描述, 意思是圆的直径是1, 周长大概为3, 这说明了人类早期对π值的估算, 在东汉时期官方公布古率明确规定圆周率等于3, 并以此来计算圆的面积。

人类的早期还应用其它不精确的方法来推算π值。如古希腊与古埃及人曾经用谷粒摆在圆周之上, 以粒数与方形对比的办法获得π值, 还用质地均匀木板锯得圆形和方形以其重量的比获得π值等获得圆周率π的许多值, 如古埃及人将π=4 (8/9) 2≈3.1605使用近四千年, 公元前6世纪印度人曾取π≈3.162, 在我国西汉之初王莽命令刘歆造量的容器“律嘉量斛”, 在造容器的过程中刘歆就用到圆周率π值, 为此他通过做实验, 获得一些关于圆周率π的一组近似值, 分别为3.1547、3.1992、3.1498、3.2031, 这已比径一周三的古率大大进步了, 这种人类经粗糙计算得出的数据, 主要用于计算园田面积, 由于数值不够精确在当时没有产生较大影响, 但用这些π值来制造器皿等误差就明显太大了。

1.2通过几何法演算π值

通过简易测量的方法演算出的π值是很粗略的, 阿基米德科学地研究了圆周率, 使圆周率的演算发展到中级阶段, 他对π值的演算建立了数学的方法而非通过测量的手段, 将π值精确到任意精度, 从此使圆周率π的演算建立在数学科学为基础。

圆周长界于其外切正四边形与内接正四边形之间, 所以显然这是不精确的, 阿基米德将正多边形的边数增加, 曾使用了正96边形来演算π值, 从而使阿基米德所求圆周率π的精度越来越高, 在他的著作《圆的测定》一书中首次创造性地利用下界与上界来更精确地确定π值, 利用几何法对圆周长和其直径的比界于3+ (10 71) 与3+ (1 7) 之间进行证明, 并得出误差的估计值, 此种数学演算方法从理论上讲重要的是所求得的圆周率π值更加精确。

阿波罗尼奥斯经长时间的演算得到π的值为3.1416, 在公元前150年前后由希腊天文学家托勒密获取π的值为3.1417, 并取得π近似值为377与120之比, 这些都是自从自阿基米德以后所取得的伟大成就。

我国首先最早在公元263年左右由数学家刘徽得到比较准确的π值。刘徽采用当时先进的割圆术得到π等于3.14, 并提出它是不足近似值, 他研究割圆术的时代虽比阿基米德稍晚点, 但他与阿基米德相比从方法上更有独到地方, 只用圆的内接正n边形可以给出π的上界与下界, 此做法比阿基米德利用外切与内接正n边形来确定π值要简便了许多, 此外刘徽通过对割圆术的研究过程中给出了一种奇妙的计算方法, 他把分割成的192边形的若干个粗略的近似值使用简单的加权平均的方法, 得到圆周率π值的4位有效数字3.1416, 对这一结论刘徽曾说过, 若使用割圆的方法来计算得到这个数值, 就要割至3072边形, 此种相对精确的计算方法的效果是神奇的, 这种奇特的计算方法是割圆术中最精彩的, 可惜的是由于当时人们没能对它有正确理解而未被重视。

我们都知道祖冲之对圆周率π所做出巨大贡献, 在史书《隋书·律历志》中有许多关于祖冲之对圆周率π演算的记载, 他对圆周率的演算有巨大成就, 求得圆周率π介于3.1415926和3.1415927之间, 其精确度进一步提高, 并且求得π的两个替代分数, 它们分别是约率22/7和密率355/113, 他演算出的π值有八位, 此成果是当时最精确的, 在世界上保持了近千年记录, 并且在1912年日本数学家三上义夫为纪念祖冲之的研究成果提出将π等于355/113叫做祖率。

为什么祖冲之能够获得这个巨大成果?是建立在刘徽割圆术方法基础之上的并对它进行有效的发展与传承, 所以对祖冲之的成就大加赞誉时, 要清楚他是站在数学大师刘徽的有力的臂膀之上的原因, 若要只利用演算圆的内接多边形边长这种方法想获得这个精确结论, 后人做过推算, 它需要演算至少圆内接正12288边形才可以获得这一精确度π值, 祖冲之还可能利用了其它的奇妙方法来简化计算过程, 由于记录他个人成果的书《缀术》已遗失了, 有关这点已不可查询了, 这在我国数学史上非常令人惋惜也是巨大的损失。

祖冲之创造出的成就在世界上享有盛誉, 比如我国已发行纪念他的邮票, 人们于1964年11月9日在紫金山天文台观测到的小行星取名为祖冲之星, 苏联人于1959年观测到的月球环形山脉取名祖冲之山, 法国在发现宫的科学博物馆内墙壁之上撰文专门表述祖冲之的伟大功绩, 在苏联莫斯科大学的走廊里矗立着祖冲之的大理石雕塑。

祖冲之表示π值选择用两个简单的分数, 一般情况下不会引起人们的注意, 但是这点在数学上具有极其有重要的意义, π与密率 (只用到了1、3、5这三个数字) 的近似度很接进, 它在形式上却十分简并很优美, 有数学家专门做了验证后得出:在所有分数中当分母不大于16603时没有发现其它分数比密率更趋近于π, 西方人取得这个成果是在祖冲之之后的一千多年, 可以坦率的讲祖冲之获得密率是一件非常了不起的事情。祖冲之是使用什么方法获得这样精确的结论的呢?由于当时的文献没有承传下来, 后人对它也做了各种各样的推测, 那么就让我们一起考查一下国外数学历史, 或许能够找到一些线索。

德国于1573年经数学家奥托研究后获得这个结论, 他就将托勒密的结论120377和阿基米德的结论722中分子、分母分别相减而合成, 即:荷兰于185 8年由安托尼兹将阿基米德的结论333 106<π<377 120中上限与下限取平均数进行了合成, 得到了此结论, 即:两人都获得了祖冲之的密率, 但纯粹是巧合, 没有任何道理。在17世纪日本数学家关孝和在求π值时建立零约术, 它实际上是采用加成法去求得近似分数的办法可以获得祖冲之的约率与密率, 他选取3、4为母近似值, 经依次六次加成便获得约率22/7, 经一百十二次加成便获得密率355/113, 他的弟子对此种办法进行了改进, 找出从附近的过剩或不足近似值中就近加成的方法, 其实质是前面已讲到的加成法, 这样自3、4为起点经六次加成获得约率22/7, 经七次加成获得25/8, 就近和紧邻的22/7进行加成获得47/15, 这样经过23次加成方可得密率355/113。

在《中国算学史》中记载着钱宗琮有关祖冲之圆周率计算方法的推测, 他推演了祖冲之在获得密率的计算过程, 经算得加成权数x=9, 并采用把徽率1 57/50和约率22/7作母近似值, 这样计算: (157+22×9) / (50+7×9) =355/113, 从而获得密率, 并且钱宗琮对祖冲之的计算过程给了高度解读与评价。

另外还有一种推测是采用连分数的办法, 利用更相减损术来求两个正整数的最大公约数早在《九章算术》已有记载, 因此利用这一工具来求近似分数存在着可能性, 便有人认为祖冲之在求出盈二数以后再利用这种方法把3.14159265表达为连分数, 于是得出其渐近连分数:22/7、336/106、355/113、102573/32650…最后把精确度较高、分子和分母又较小的分数355/113作π的近似数, 英国的博士李约瑟也是这样考虑的, 他在《中国科学技术史》中对祖冲之所研究的密率进行了较高的评价, 由于祖冲之得到的密率是一些渐分数、连分数, 所以是一个了不起的成果。

我们再来研究一下国外对圆周率所作出的贡献, 印度阿耶哈达在公元450年左右获得π=3.1416;中亚与西亚地区在1424年前后由数学家卡西经过演算805306368个内接与外切正多边形的周长, 最终得到π=3.14159265358979325, 这个π值有十个有效数字从而首次突破由祖冲之所创造的记录;法国在16世纪由数学家韦达运用阿基米德的演算方法, 采用216×6个正边形计算得到有9位有效数字的π值, 他仍沿袭了阿基米德的研究方式, 由于他采用了十进位制数, 从而使韦达有了先进的工具, 也获得了更高精度的π值;德国数学家鲁道夫在17世纪用一生的时间来研究π值, 他采用十进制数并与阿基米德的研究方法相结合, 他开始时未从正六边形入手并把它的边数增倍, 而是从正四边形入手一直推出262条边的正多边形, 最多达到大概4610000000000000000边形, 经计算得出π值中有36个有效数字, 在德国为缅怀他作出的这一伟大成就固把π命名为“鲁道夫数”。

前面讲了运用几何法求π值, 它的计算繁杂, 会穷尽数学家一生的心血, 鲁道夫的计算已经到了巅峰, 古典方法再不能向前推进了, 在17世纪数学分析的发现促使π的演算过程也进入全新的历程。

1.3通过分析法演算π值

利用分析法求π值的时期是通过无穷级数来计算, 它已经突破求多边形周长的繁杂演算过程, 此时对π已给出精确表示与充分的理性认识。

1579年数学家韦达得出π的最早分析表达式:这个公式十分的优美, 至今也令人们欣赏赞叹, 公式中仅出现数字2, 使用乘、除、开平方与加法等系列的运算就得出π值。后来相继对π给出多种表现形式, 比如在1650年由英国科学家约翰·沃利斯提出:在1650年由英国数学家罗尔德·布隆克尔提出在1 6 7 1年由苏格兰数学家詹姆斯·格雷里奇提出:这些式子都是首次精确表达π值, 但是4357911

运用它去计算π值时耗费时间与精力, 想把π值精确至小数点后第二位就得演算几百项。

创建微积分的数学家牛顿提出:

牛顿运用这个公式大大简化了π值的计算过程;大数学家欧拉于18世纪对π值提出新的计算:…, …从形式上看两个表达式是十分简洁与完美的, 但计算出的π值的效果并不好;数学家亚伯拉罕·夏普于1699年运用詹姆斯的结论算出π值有72位有效数字;数学家梅钦于1 7 0 6年提出π的表达式:他运用级数展开的方法计算π值到小数点后100位, 为纪念他的成果, 表达式以他的名字来命名;法国代·拉尼于1719年把π值精确到小数点后第1 12位;德国兰伯特于1767年经过证明提出π值是无理常数;法国勒让德于1794年再经过证明得出π2也是无理数;达塞于1 84 4年得到公式:并运用此公式对π值取得第20 0位小数的成就;在1853年德国卢瑟福竟然把π值精确至小数点后的400位。

在1882年由德国林德曼提出并得到证明π为超越数, 它不是整系数代数方程的解, 从此解决了困扰人们近二千年的数学难题即不可化圆为方, 从而极大的突破了对π认识。在1873年由美国菲格森把π值精确至小数点后的710位;佛格森与小伦奇于1947年共同研究并得到π值的小数点后的808位, 创造了用人工计算π值的世界最高记录。

求π值不同的类似公式在19世纪后出现很多, 精确度也越来越高, 谢克斯在1873年运用梅钦的级数公式把π计算至小数点后707位, 他用了20年时间才获得这项世界纪录, 为歌颂他顽强精神与坚韧毅力, 人们在他去世后把凝聚他一生心血π值刻在他的墓碑之上, 他获得的这个举世的成就成为以后74年内为人们深信不疑的最高记录。数学家弗格森在若干年后对谢克斯的计算有疑虑, 他大胆地进行了猜想, π值中虽然数字的排列确实不存在规则, 但各个数字出现的几率似乎相近, 于是他对谢克斯的π值做了统计后提出数字的出现并不均等, 于是使他产生了怀疑。从1944年至1945年的一年时间内他采用了当时最优秀的计算手段进行计算, 找到从第528位开始是错误的, 之后的一百多位数字全部有问题, 谢克斯的大半成果就这样被无情地一笔抹去了, 但谢克斯作为毅力坚强的计算者自愿献出大半生精力从事π值的计算工作而无报酬, 这种在数学上的不懈追求精神是值得我们学习的。

1.4通过计算机演算π值

世界上首台计算机ENIAC于1946年问世, 随着电脑时代的开启出现了计算方面的根本革命, 1949年在计算机上根据梅钦的计算公式将π值计算至小数点后2035位, 计算时间仅为70小时, 由于计算机的发展速度非常快, 导致π值的计算记录被一次次打破。

印度数学家拉马努金在19世纪初提出一个高效的计算π值的数学公式:由于公式中出现四次方导致它高速趋近于π的真实值, 每一步计算都可以增长8位有效数字, 1985年人们使用这个公式对π值进行计算后得到小数点后一千七百万位数字;法国裘努埃于1959年运用IBM704将π值计算至小数点后16167位;美国香克斯与伦奇于1961年运用IBM7097将π值计算至小数点后100265位;法国吉劳在1966年运用STRETCH将π值计算至小数点后250000位;法国吉劳在1967年运用CDC6600把π值计算至小数点后500000位;法国吉劳在1973年把π值计算至100万位小数, 并把此成果编成世界上最枯燥的二百页的书;日本鹿角理三吉与久仲山于1981年运用FA CO MM-200利用公式把π值计算到小数点后2000038位;美国贝利在1986年利用Cray-2只耗费28小时就将π值计算到小数点后29360000位;日本廉正蒲田在1986年使用NECSX-2把π值计算至小数点后134217700位, 并在1989年对π值的计算攻破10亿位;日本在1994年运用数学公将π值精确至小数点后40亿位, 并在1995年已突破64亿位。

在20世纪90年代数学家创造出π的“水龙头”计算法, 对π值在原有数字的基础之上运用递推方式可以计算出后继的数字, 电脑专家们还创造出十分有意义、有效的公式:运用此公式得到了特殊的结果, 即π在十六进制数中第n位数字可独立计算出来, 而无需得出n位之前的数字, 比如不必计算出n的100万位之前的数字, 就可知道第100万位的数字。

日本东京大学教授金田康于1999年对π值已获得小数点后2061.5843亿位, 据最新消息讲他正使用超级计算机算得π值的小数点后一兆二千四百一十一亿位, 改写了两年前由他创造的纪录, 现在虽然打破记录, 但不管推进至多少位也不至令人感到惊喜, 事实上将π值算得如此精确其应用的作用已不大, 在科技方面所运用π值有十多位就已足够了, 若运用鲁道夫得出的仅36位有效数字的π值来演算能将太阳系包括在内圆的周长, 其误差不足于质子直径的1/1000000。

2π值的历史作用

是什么原因使数学家对π的计算一直不能停步呢?是什么原因对π值有这样的兴趣呢?这里面除了有人类的对新生事物的探索追求和想超越他人的想法之外, 还有其它更加重要的理由。

(1) 通过π值的计算以检测超级巨型计算机的各种性能。通过π值的计算以检测计算过程的稳定性与计算速度, 以便通过检测结果对计算机进行改进, 比如当Intel公司将奔腾 (Pentium) 计算机推出时就是通过计算π值发现此计算机中存在一个小问题, 这就是π值的计算到目前为止还不能停步的重要原因之一。

(2) 通过计算π值的思路与演算方法可发现新的数学概念与数学思想方法。即使计算机的运算π值速度非常高, 但还要求由数学家精心编制π值的运算公式与程序以指导计算机进行运算, 如果将π的演算历程划分出计算机时代时, 但绝不意味着它在计算的方式与方法上有什么改进, 仅仅是所采用的计算工具上有所突破罢了, 所以研究怎样改进计算技术、发现更加精确的计算公式并使其公式收敛得更快更好、并能快速地达到极高精度等这些问题仍是数学家们要研究的重大问题, 比如印度现代著名数学家拉马努金发现许多非常好的结论, 运用他的公式能精确并迅速地演算出π的高位近似值, 他的结论给出了更加精准地演算π值的明确思路, 可见π的计算过程是人类数学发展的胜利但它绝不是机器的胜利。

人类是否能做到无限地对π值的计算进行下去, 依据朱达偌夫斯基的估算人类是做不到的, 人类最多能对π计算到1 077位, 尽管目前人类距离这一极限位置还很遥远, 但它的计算终究是有界限的, 为了探究这一界限是否存在、是否受到这一界限的阻碍, 人类就要从算理上有新的质的飞跃, 要牢记并杜绝谢克斯式的在π计算史上发生过的惨痛的教训, 唯有探求新的计算方法。有人提出对π计算时能否做到不从头进行而要从中间开始, 这种大胆的想法是要探索并行计算公式, 计算π的并行计算公式终于1996年被发现, 只不过它是16进制的公式, 由它可得到π的1000亿位的小数, 如何把这16进制的公式转化成10进制的并行计算公式是将来数学面临的一个难题。

(3) 通过π值的计算检验数学理论层面的问题。人们希望将π的无穷级数展开至亿位, 并通过此过程能够给出充分的数据以检验人们所提出的一些理论层面的问题, 从中可推出大量神奇的性质, 比如要考查在π的十进制展开式中有些数字较稀疏、有些较稠密, 数字出现的几率是否相等, 还是它们完全随意等。最早提出在π的数值中各数字出现的几率应该相等的是数学家弗格森, 就是这种猜测为发现与纠正谢克斯在计算π值过程中出现的失误找到了根据, 弗格森想验证自己的猜测是否成立他却做不到, 他人也是由于知道的π值的位数有限而无法去验证猜想, 所以人们对其正确性也就产生了怀疑, 比如在π的近似值中0出现的几率开始时很少, 0在第32位首次出现, 但是随着π的近似值的增加, 这种情况出现了变化, 第8个0出现在100位内, 第19个0出现在200位内, 第999, 440个0出现在1000万位以内, 第599, 963, 005个0出现在60亿位内……所占比率为1/10, 其它数字出现的情况也有相似的结论, 虽然稍有偏差但都控制在1/1 0 0 0 0以内。这些问题看似无聊, 只有那些思想敏锐的人才会问这些简单的问题, 相信人类终将会得出许多有用的结论, 从而推动数学的发展。

人们很久以来就在π的展开式中努力查找素数, 起初在相当长的一段时间里经过艰难试除确定314159是六位数素数, 于1979年两位美国数学家发现并证明在π的数列中有长达38位素数31415926535897932384626433832795028841, 并称之为“天文素数”, 后来麦文在π的数列中又发现存在长度达432位的素数, 从此以后再没有新的发现。

(4) 通过π值的计算了解π值中数字的出现有没有固定模式。人们追求能够在十进制中通过统计分布对数字进行研究, 以此来寻觅存在的可能模型, 但至今为止还没有找到这类模型。人们还想知道在π值中是否存在无限的样式变化, 即是否存在任意样式的数字排布, 大数学家希尔伯特就曾提出在π的十进制数中是否存在10个9在一起, 就目前得到π的60亿位数来作考察已经发现有6个9在一起, 此问题的回答应得以肯定, 只要π的数位有足够长, 什么形式的数字排布皆会出现, 只不过是时间问题而已。

据统计在π值的60亿数字之中已经有连续的10个6、9个7、8个8, 从小数部分第3204765位和第710150位以后都有连续7个3, π值的前八位在小数部分第52638位后也同样出现, 有趣排列8 7 6 5 4 3 2 1 0出现于小数部分第2 7 4 7 9 5 6位, 只是缺个9, 还有123456789也出现, 只是缺个0, 虽然数列314159重复出现6次, 但数列0123456789从未出现过, 这一点对人们有启发作用。

参考文献

[1]李文林.数学史概论[M].北京:高等教育出版社, 2002.

[2] (英) 期科特.数学史[M].南宁:广西师范大学出版社, 2002.

[3]王树禾.数学思想史[M].北京:国防工业出版社, 2003.

[4]梁宗巨.数学历史典故[M].沈阳:辽宁教育出版社, 2000.

网络演算 篇7

到目前为止, 一些Web服务组合语言, 譬如WSCI、WSFL和BPEL4WS, 对如何将多个基本服务组合成一个复杂服务做了描述, 但都仍然是语法级别的, 它们无法验证服务组合是否正确及组合服务是否能在有限步骤内结束。因此需要对Web服务组合流程进行形式化描述, 以实现可靠的组合服务。由于Web服务的组合是一种拓扑结构动态变化的分布式通信系统, 而Pi-演算可以用来描述结构不断发生变化的并发系统, 所以本文拟采用Pi-演算对服务组合进行形式化描述, 并进一步给出验证。

1 Pi演算及服务组合的形式化方法

Pi演算是Robin Milner提出的, 以进程间的移动通信为研究重点的并发理论, 它是对CCS (Calculus of Communication System) 的发展。其基本计算实体为名字和进程。进程间的通信通过传递名字来完成。由于Pi演算不但可以传递CCS中的变量和值, 还可以传递通道名, 并且将这几种实体都统称为名字而不再区分, 这使得Pi演算具有了建立新通道的能力。因此Pi演算成为用来描述结构不断变化的并发和分布式系统的高效语言。对于Pi-演算的基本语法及操作见文献[1]。限于篇幅原因, 本文中不再详述。因要对服务组合进行正确性验证, 在此特指出Pi-演算中的互模拟的概念。

Pi-演算中互模拟分为强互模拟和弱互模拟。强互模拟是指, 进程P能完成的所有动作和变迁 (内部的和外部的) , 进程Q都能完成, 则称进程P和Q是强相似的。

弱互模拟是指外部观察者所观察到的P和Q的外部行为和变迁是一致的, 则称进程P和Q是弱相似的。也称观察等价。

Web服务组合研究领域的一个重要问题是如何形式化描述Web服务组合, 如何验证服务组合的正确性。Web服务组合的形式化模型可以用来检查、验证Web服务组合以保证组合的正确性。服务组合的主要方法见文献[2], 而目前较常见服务组合的形式化方法为:基于Petri网的, 基于进程代数 (CCS, LOTOS及Pi演算) 的以及基于半形式化语言UML的。而对于基于本体 (如OWL-S) 以及基于可执行语言 (如WS BPEL) 的方法, 因为他们都可以使用形式化的方法来进行建模和验证, 所以一般不将其列入形式化方法的范围。

考虑到Petri网所引起的状态空间爆炸以及对CPU资源的消耗问题, 如果状态空间比较大, 则很有可能将系统资源耗尽, 从而无法完成验证工作。另外, 虽说基于Petri网的模型易读, 但却降低了其伸缩性。而Pi演算方法提供了精确的符号和强大的推理机制, 这促进了复杂服务的规范化。并且Pi演算可以用来描述结构不断发生变化的并发系统, 而Web服务组合是一种结构可能会发生变化的系统, 所以本文将采用Pi演算对服务组合进行描述及验证。

2 服务组合的正确性及其验证方法

从技术上说, 服务计算的价值在于服务重用, 而重用的目的则是使服务增值。除了服务本身的重用外, 组合不同的服务以产生不同于各个单一服务的功能, 也是研究的重点之一。服务组合是指:由各个小粒度的服务相互之间通信和协作来实现大粒度的服务功能;通过有效地联合各种不同功能的服务, 服务开发者可以借此解决较为复杂的问题, 实现增值服务。比如常见的旅行预定服务、订单服务等, 都是组合已有的组织内和组织外的服务来实现单个服务所不能完成的复杂功能。

但是, 如何使得服务真正进入实用的阶段, 使得服务实现跨组织、跨管理域的系统集成和自动交互, 这就要求我们对组合服务的正确性进行验证即判断组合服务是否与期望中的服务等价。考虑到服务是在整个网络上进行交互和组合, 其面对的组合对象和环境复杂多变, 同时鉴于专门用于描述移动进行的Pi演算在描述此类问题上具有一定的优势, 所以, 本文将利用Pi演算的方法来进行服务组合的正确性验证。

2.1 服务组合的正确性

文献[2]给出了服务组合的正确性定义。但没有考虑QoS属性。本文中对其定义如下:

定义1服务组合如果是正确的, 设该服务组合能够被建模为解决方案模型S, 而客户需求可表示为规范P, 那么如果S的功能及非功能属性均能满足P, 即:若S与P使用进程代数来表示, 而S与P的逆之间存在弱互模拟关系, 则称S是正确的。

2.2 正确性的验证方法

工程上常常采用直接验证方法, 所谓直接验证, 就是直接对流程描述进行分析。但是, 这种分析在单个语法上是较为容易进行的, 而却难以保证组合逻辑整体上的正确性。因此, 各研究组织和机构都提出了相应的形式化解决方法, 对组合的正确性进行严格的判定。本文采用基于Pi演算的方法对组合正确性进行验证。验证的主要内容包括:

模型的正确性:如同步是否正确?是否存在死锁?消息是否会丢失?

行为等价性:两个Web服务行为等价是指从Web服务使用者的角度来看这两个Web服务的行为完全一致。在进程代数中, 有两种行为的等价性定义:强相似 (strong bisimilarity) 和弱相似 (weak bisimilarity) 。

下一节中我们以一个旅行计划服务为例来给出用Pi演算对Web服务组合的形式化描述以及验证方法。

3 实例

一个典型的旅行计划服务的业务流程如下:客户通过通道order发出旅行计划请求 (包括功能及非功能方面需求) , 旅行代理收到旅行计划后, 向航空公司及酒店预定机票和房间, 同时并搜索旅游景点。航空公司、酒店及景点搜索将结果反馈给旅行代理, 代理依据景点与酒店距离, 向交通公司预定交通方式, 交通公司将预定结果返回给旅行代理, 最后旅行代理返回结果给客户。我们用Pi-演算流图来描述这个组合的业务流程如图1所示, 图中矩形代表进程, 实线为进程间固定通信通道, 虚线为动态通道。从客户的角度来看, 与之交互的服务是一个单一的组合服务, 组合服务和客户间的交互通道为order和ans, Travel服务作为一个中心协调者来负责调用和组合子服务FlightAndHotel、Attraction和CarOrBike, 其内部通道fAh、att、tra、f Ahres、attres、trares以及内部交互对客户来言是不可见的。

3.1 旅游信息系统中服务的描述

(1) Customer沿通道order向Travel发送旅行计划请求req和动态通道ans, 同时在通道ans等待结果。Pi演算进程建模Customer如下:

(2) Travel从通道order收到通道名ans和旅行计划请求req后, 分别沿着通道f Ah、att向FlightAndHotel和Attraction发送旅行计划及内部通道f Ahres、attres, 并从内部通道fAhres、attres等待处理结果resultFH、resultAtt。Travel根据resultFH及resultAtt, 在旅行计划请求req中添加预定酒店与景点间的距离信息, 则请求变为reqT, 再沿通道tra向CarOrBike发送reqT及内部通道trares, Travel在通道trares等待处理结果resultTra。最后, Travel将结果返回给Customer。Pi-演算进程建模Travel如下:

(3) FlightAndHotel从通道fAh收到旅行计划req和内部通道f Ahres后, 根据票务及住宿情况沿通道f Ahres向Travel返回结果。用Pi-演算进程建模如下:

同样Pi-演算建模Attration及CarOrBike如下:

(4) 由Travel、FlightAndHotel、Attraction、CarOrBike所组成的组合服务TravelService表示如下:

3.2 利用Pi演算进行正确性验证

使用形式化工具的目标是协助系统设计和验证。当系统模型建立后, 则可利用Pi-演算来推演系统的行为, 同时验证模型的正确性, 如发现系统行为不完整、死锁、缺少同步等。每次修改模型时, 都要进行这些检查, 以保证系统是一直按照需求设计, 并且在正确地实现。

作为一种强大和成熟的形式化方法, Pi-演算有支持其正确性验证和相关应用的工具, 如JACK工具集、基于Pi-演算的语言PICT[4]、可执行的Pi-演算EPI以及传值进程代数工具VPAM等。本文采用基于New Jersey SML语言编译器的MWB (Mobility Workbench) 工具。MWB工具是用于操作和分析移动并发系统的自动化Pi-演算工具, 它使用函数式编程语言SML (即标准元语言) 构建, 具体使用的是朗贝尔实验室实现的SML/NJ110版。验证时的软件实验环境为:Windows XP SP2, MWB'99, version 4.135, SML/NJ版本为110.0.7。下面对组合的Web服务模型进行推演和验证。

使用MWB工具对代数表达式进行语法分析可以发现进程定义的一些基本错误:如类型错误、缺少同步、不完整的行为等, 并可利用工具的推理功能排除一些最常见的错误。用Pi-演算描述的客户与组合服务应该是观察等价的, 也即客户的行为与组合服务的动作是互补的。如果组合服务满足客户需求, 则客户的逆进程与组合服务进程应该是等价的。下面对客户进程求逆如下:RevCustomer (order, resultFH, resultAtt, resultTra) =order (ans) .order (req) . ('ans.0|'ans.0|'ans.0) 。

将组合服务系统消除内部行为, 即?动作, 则组合服务系统变为:

将进程Customer、Travel、FlightAndHotel、Attraction、CarOrBike、TravelService及RevCustomer写入到文件"TravelSystem ag"中, 并将此文件放置到MWB的目录下。利用命令input"TravelSystem.ag"建立各个进程、命令deadlocks对TravelService进程及RevCustomer进程进行检测, 结果表明各个进程均无死锁现象、命令weq RevCustomer TravelService进行弱相似判定, 得出结果:

The two agents are equal.

Bisimulation relation size=10.结果显示了此服务组合的正确性。

4 结束语

Web服务及其组合的形式化描述和验证, 是Web服务中一个重要的研究工具。因Pi-演算的优势, 所以用其作为描述Web服务组合的形式化工具。本文利用Pi-演算对Web服务组合建立形式化模型, 给出了基于Pi-演算的形式化描述及Web服务组合的正确性验证方法, 并给出一个实例来说明。将来的研究工作包括:形式化工具MWB自动求逆操作及语义方面的问题。

摘要：对于Web服务及其组合而言, 保证其正确性并实现增值服务是十分必要的。Pi-演算是一种移动进程代数, 可用于对并发和动态变化的系统进行建模。通过建立一个实际的模型, 用Pi-演算对Web服务及其组合进行建模, 并利用形式化工具对建立的组合模型是否正确以及是否满足需求进行了验证。

关键词：Pi-演算,进程代数,Web服务,服务组合,形式化方法

参考文献

[1]Parrow J.An introduction to theπ-calculus[A].Jan A Bergstra, Al-ban Ponse, Scott A Smolka.Chapter to appear in handbook of Pro-cess Algebra[C].Elsevier, 2001.

[2]廖军.面向服务的计算 (SOC) 中服务组合的研究——服务计算中一个关键问题的解决方案[D].成都:电子科技大学, 2006.

[3]Milner R., Parrow J., Walker D.A Calculus of mobile processes, part I/II.Journal of Information and Computation, 1992 (100) .

[4]Pierce, B.C., “Programming in the Pi-Calculus:An Experiment in Programming Language Design.”Lecture notes for a course at the LFCS, University of Edinburgh., 1994.

[5]Riccardo Pucella.Notes on Programming Standard ML of New Jer-sey[M].Cornell University.2001 (1) .