基于分层思想的基本通信系统CPN建模论文.doc

基于分层思想的基本通信系统CPN建模论文 摘要：针对通信系统建模复杂度高、可靠性差、模型缺乏形式化验证方法以及可重用性差的问题，提出一种基于分层思想，并结合面向对象的概念，利用着色Petri网(CPN)对基本通信系统进行建模的方法。该方法融合CPN和面向对象技术的优点，从形式化、可视化的角度描述基本通信系统的运行过程。以一个简单的基本通信系统为例进行建模，证明该模型与实际系统中的对象可以相互对应，易于理解和实现。 关键词：基本通信系统;分层思想;对象子网;着色Petri网;建模 1概述 随着计算机网络技术的发展，通信系统越来越复杂，体现出空间分布性、并发性、异步性、不稳定性、多样性和实时性等特点，不能仅靠工程直觉方法设计出高质量的系统1。 基本通信系统由发端设备、收端设备、传输媒介以及三者之间的关系网络构成，是一种较为普遍的通信系统结构。 基于计算机技术对基本通信系统进行分析、建模和验证，从而提高系统的可靠性和可维护性，已经成为十分重要和普遍的研究课题。 目前，普遍采用面向对象的建模设计方法对基本通信系统进行建模，用UML标准建模语言对模型进行描述。系统的结构模型用类图描述，而系统的动态模型用交互图和顺序图描述。使用UML构建的模型清晰易懂，模型中类的概念可以直接与系统的代码实现相对应。但是，面向对象的分析和设计方法缺乏形式化基础，对建立的模型缺乏严谨的分析和验证手段2。 作为一种形式化建模方法的Petri网3，能够方便有效地描述带有并发性、异步性、分布性、非确定性、并行性的系统，被广泛地应用于基本通信系统的建模。该方法具备强大的数学理论基础和严格的形式化描述。但是，由于模型元素的单义性，容易产生“状态空间爆炸”的问题，并且建立的模型对系统的依赖性很高，也容易导致模型可重用性差。 为了解决上述问题，结合着色Petri网4(ColoredPetriNet,CPN)和面向对象的技术，本文针对基本通信系统，提出了一种基于分层思想5的CPN建模方法。利用分层思想对基本通信系统进行划分，降低系统结构的复杂性，减少“状态空间爆炸”的问题;将面向对象的概念引入CPN，并利用CPN中的颜色集描述系统的工作状况，以提高模型的正确性、可维护性和可重用性。 2基本通信系统的分层 一般来讲，基本通信系统由发送端、接收端以及两者之间的通信关系构成，这也可以视为基本通信系统的第1层。 发送端和接收端内部各对象之间，以及对象与外界之间的通信关系定义为第2层。通信关系一般包括建立连接、即时通信与断开连接3种。根据通信关系的不同，确定了对象之间不同的通信内容，从而形成不同的网络结构。同时，不同的通信关系也形成了各个对象内部不同相关的操作与状态。所以，对象内部的操作与状态定义为第3层。其形式定义为：定义1一个基本通信系统为一个三元组：SYS=(O,Net,I)。其中，O表示发送端对象;I表示接收端对象;Net表示根据两者之间的通信关系而确定的网络结构。 通信关系一般包括建立连接、即时通信和断开连接3种类型。根据通信关系的不同，可以定义基本通信系统的不同的网络结构。 定义2基本通信系统的网络结构为一个四元组：Net=(OBJ,R,ST,G)。其中，OBJ表示非空有限对象子网集合，是由发送对象子网和接收对象子网构成的，即OBJOBJ|1,2,i=i=n;R表示对象子网间的通信关系集合，即R=建立连接，即时通信，断开连接;ST是替代变迁;G是一种特殊的变迁，称为“门”变迁，起到对象子网间消息传递作用。 定义3对象OBJi表示为CPN(既可以是发送对象子网中的对象，也可以是接收对象子网中的对象)，定义为一个九元组：OBJ(,P,T,F,N,C,G,E,I)i=。其中：(1)是非空托肯颜色集合(ColorSet)，决定了在网描述中所使用的token类型、运算和函数; (2)P是有限库所集，P=PP,MP，PP是基本状态库所，MP=OMP,IMP是用于对象间消息传递的输入输出消息库所; (3)T是有限变迁集; (4)F是有限弧集，PT=PF=TF=; (5)N是节点函数，定义为N:F(PT)U(TP)，映射每一个弧到一个节点对，且前一个节点为源节点，后一个节点为目标节点，这2个节点类型不同，一个是变迁，另一个是库所; (6)C:P是颜色函数，把每一个库所pP映射到颜色集C(p)，p中每一个token颜色必须属于C(p); (7)G是保护函数，映射T到布尔型; (8)E是一个弧表达式函数，定义为从F到表达式的函数E(f)，使得MS?fF:(Type(E(f)=C(p)(Type(Var(E(f)?)，即弧表达式函数映射每个弧fF到一个表达式，且这个表达式的类型是C(p)MS，E(f)的每一个求值都生成一个依赖于相邻库所颜色集的多重集; (9)I是初始化函数，映射每一个pP到一个闭表达式，且这个表达式是C(p)上的多重集，即?pP:Type(I(p)=MSC(p)。 其中，用类型Type()映射表达式或变量的类型值，分别为Type(expr)或Type(v);函数Var(expr)表示表达式expr中的变量的集合;B表示布尔类型值，即true或false;C(p)MS表示颜色集C(p)上的多重集;不含任何变量的表达式称为闭表达式6。 图1是根据以上定义建立的一个简单通信系统模型的例子，采用CPNTools辅助绘制。 图1表示的是一个只包含一个发送端设备和一个接收端设备的通信系统，通信关系为建立连接的系统模型。建立连接的过程可简单描述为：(1)发送端发送hello数据包给接收端;(2)接收端接收后反馈发送端一个hello数据;(3)通信连接建立。 在图1中，由发送端对象S_O和接收端对象R_I构成第1层模型，用矩形框与双向箭头表示;发送对象send和接收对象receive之间的通信关系是第2层模型，用圆角矩形表示;2个对象内部的状态和操作是第3层模型。 在图1中，用圆角矩形来表示对象，对象所属的变迁和库所被封装在对象内部，对象的外部接口由消息接口、门以及它们之间的流关系给出。库所上的小圆内的数字表示库所当前所含的token数目。各对象内部的库所颜色集分别可以有若干token，各token所处的库所表示各对象的当前状态，随着变迁的引发，颜色token从一个库所移动到另一个库所，相应地，对象也从一个状态变化到另一个状态。 上述基本通信系统的形式描述为：第1层SYS=(S_O,NET,R_I);第2层Net=(send,receive,建立连接,T1,T2);第3层是对2个对象子网send和receive的描述，这2个对象子网都只包含一个对象，以send为例，send=,P,T,F,N,C,G,E,I，其中，=STRING,BOOL|colsetSTRING=string,colsetBOOL=boolean;P=P0,P1,P2,P3,P21,P24;T=T21,T22;C(P)=STRING,BOOL，弧表达式见图1，I(P24)=“hello”;对象receive与send类似，图1中未使用保卫函数。 3建模方法及模型验证 3.1建模方法利用上述定义建模一个基本通信系统，首先要了解该通信系统在不同阶段对象之间的通信关系;然后对每个阶段的执行过程进行详细描述。对通信系统及其执行过程进行整体把握后，分以下3步创建系统的各层CPN模型：(1)从基本通信系统中抽象出发送端对象和接收端对象，从整体上把握系统的网络结构，形成第1层系统模型。 (3)对于对象子网中的每个对象进行更进一步的细化，给出对象子网内部的各个对象的详细描述，建立第3层模型，该模型描述了每个对象内部的操作和状态。 3.2模型验证 在定义1中描述了一个基本通信系统的发送对象与接收对象之间一般存在的3种关系：建立连接关系，即时通信关系以及断开连接关系。通信系统建模期间是基于这3种关系分别建立CPN模型的。 对于每一种关系所建立起来的模型，应用普通CPN的公式化验证方法(如状态空间分析和不变量的分析方法等)就可得出所建Petri网模型的各种性质，从而使通信系统在这种关系上得到验证。 在此基础上，将建立连接模型的输出作为即时通信模型的输入，将即时通信模型的输出作为断开连接模型的输入，把整个通信系统的各个阶段的模型连接起来，从而使得通信系统在整个通信过程中得到严格的分析和验证。 4系统建模实例 本文以一个简单的基本通信系统为例说明如何进行分析并建立模型，因为主要解决系统建模的问题，所以忽略与本文讨论无关的问题，例如数据帧格式等。 4.1基本通信系统及通信过程描述该基本通信系统采取“一去一回”的简单数据传送方式，通信仍然分为3个阶段：建立通信连接阶段，进行即时通信阶段和断开通信连接阶段。本文以建立通信连接为例来说明整个建模过程，其他2个阶段与其情况相似，先不予讨论。 建立通信连接阶段所采用的通信过程如下： (1)由发送端发起进行连接，发送携带协商参数的初始化信息给对方接收端; (2)接收端检查从发送端发来的信息，如果信息中携带的参数能够被接受，则自己也发一个初始化信息给发送端，并携带参数; (3)发送端检查接收端发送来的参数，如果认同，对接收端发送keepalive消息，接收端收到后也发送keepalive消息，连接建立。 4.2通信系统的CPN模型 该通信系统仅存在一个发送端设备和一个接收端设备，针对这种情况，确定5个对象子网中各存在一个对象。该通信系统可以用一个三层的模型结构来描述。 基于通信过程中提出的“一去一回”的交互方式，以建立通信连接为例，通信系统模型如图2所示。 在图2所显示的模型中，在第1层模型中，如图2矩形框与双向箭头显示，从整体上确定了系统结构;在第2层模型中，如图2圆角矩形显示，描述了2个对象子网之间的通信关系;在第3层模型中，对于每个对象进行了详细建模，描述了在建立连接过程中对象内部所有的操作以及经历的状态，并且显示了与接口的数据传递关系。 4.3模型的验证 本文采用可达图的方法对图2的模型进行验证。P=P1,P2,P3,P4,P5,P6,P21,P22,P23,P24,P25,P26,P27,P28，初始标识为10000000101111T，如图3所示。 从图4中可以看到，随着时间轮数的延长，节点存活数量都随之下降，与LEACH协议和文献11中节点存活数量相比，本文算法的存活节点大于上述协议和算法。从而说明了本文算法中节点剩余能量高于LEACH协议和文献11中节点的剩余能量，进而延长了网络生存周期，优化了网络资源。 第3种情况是选择不同覆盖区域100m100m、200m200m、400m400m，比较不同区域覆盖率变化情况，如图5所示。从图5中可以看到，随着网络规模的扩大，要满足一定的网络覆盖率需求时，所须部署节点的数量也会随之增加，并且网络的覆盖率越高，需要部署节点的数量增加得越快，要实现不同区域完全覆盖的前提是在覆盖区域内完成对不同目标节点的完全覆盖。可以看出，在不同的覆盖区域内，完成对目标节点覆盖也需要不节点数量，在对某一区域内进行时，不同的区域所覆盖的范围也是不同的。在满足一定覆盖要求下，以相同的节点数作为基数，对100m100m区域进行覆盖所需节点最少，而400m400m需要的