（计算机软件与理论专业论文）新一代网间结算系统关键技术的研究.pdf

南京邮电人学硕：j ：学位研究生论文摘要 摘要 网间结算系统是保证各电信运营企业间能够及时、准确的进行互联结算的业务支撑系 统，也是运营商实现业务收入的核心保障系统。第三代移动通信系统( 3 g ) 带给我们的是 更为丰富、多样化、个性化的业务，同时也在海量数据、并行处理、实时结算和多方结算 等方面对网间结算系统提出了更高的要求。p e t r i 网是一种可用图形表示的组合模型，具 有直观、易懂和易用的特点，最适合表示事件之间的并行性和自然相关性。本文将p e t r i 网的建模技术引入到网问结算系统的建模中。 本文首先分析了3 g 业务类型和特点，总结了3 g 对网间结算系统的需求；其次提炼 了网间结算系统的层次模型；在此基础上，采用p e t r i 网分层建模、逐步求精的思想，先 构建了系统的整体模型，然后对数据采集、预处理、批价、结算处理和入库等处理环节及 其子对象进行了建模；为确保系统数据处理的完整性和一致性，给出了审核校验和回退处 理的设计实现方案：针对现有网间结算系统单一批次的不足，提出一种“多环节组合批次” 的方法，可以更准确高效地实现审核校验和回退处理。 采用现有省级网间结算系统的实际运营数据和3 g 实验网的测试数据进行大量的实例 验证与分析之后，验证了本文所建立的网间结算系统的p e t r i 网模型具有结构完整、开放 性好、可扩展性强等特点，审核校验和回退处理的设计实现方案具有功能完备、流程合理、 可操作性强、实现方便等特点，“多环节组合批次”的方法具有灵活性好、针对性强等特 点。 关键词：网间结算系统，3 g ，p e t r i 网，建模 南京邮l 也人学烦，i ：学位研究生论文 a b s t r a c t a b s t r a c t 。ih ei n t e r c o n n e c t l o ns e t t l e m e n ts y s t e m w h i c he n s u r e sa l lk i n d so fd a i l ys e t t l e m e n tb u s i n e s s c a r r y i n go u ts m o o t h l ya n dt i m e l y ，i sa l s ot h ec o r es y s t e me n s u r i n gg o o ds e r v i c ei n c o m ef o r t e l e c o mo p e r a t o r s t h et h i r dg e n e r a t i o no fm o b i l ec o m m u n i c a t i o ns y s t e mw i l lb r i n gu sa n a b u n d a n t ，d i v e r s i f i e d ，p e r s o n a l i z e ds e r v i c e ，a n dp u t ah i g h e r s y s t e mr e q u i r e m e n t t o i n t e r c o n n e c t i o ns e t t l e m e n ts y s t e mi nm a g n a n i m o u sd a t a ，t h ep a r a l l e lp r o c e s s i n g ，t h er e a l - t i m e s e t t l e m e n t s e t t l e da c c o u n t sa n ds oo n p e t r in e ti sak i n do fc o m b i n a t i o nm o d e lt h a tc a l lb e r e p r e s e n t e db ys k e t c h ，w i t ht h ec h a r a c t e r i s t i co fi n t u i t i v e ，e a s y - t o u n d e r s t a n da n de a s y t o u s e ， a n di ti ss u i t a b l et oe x p r e s st h ep a r a l l e l i s ma n dt h en a t u r a lr e l e v a n c ei nt h ee v e n t s ，a n di th a sa u n i q u ea d v a n t a g et od e s c r i b ea n da n a l y z et h ec o n c u r r e n tp h e n o m e n o n t h i sp a p e ri n t r o d u c e s p e t r in e tm o d e l i n gt e c h n o l o g yi n t ot h em o d e l i n go ft h ei n t e r c o n n e c t i o ns e t t l e m e n ts y s t e m f i r s t l y ，t h i sp a p e ra n a l y z e st h et y p ea n dt h ec h a r a c t e r i s t i co f3gs e r v i c e ，s u m m a r i z e st h e d e m a n d so fi n t e r c o n n e c t i o ns e t t l e m e n ts y s t e mf o r3 g s e c o n d l y ，r e f i n e st h eh i e r a r c h i c a lm o d e l o ft h ei n t e r c o n n e c t i o ns e t t l e m e n ts y s t e m ；o nt h i sb a s i s ，u s eh i e r a r c h i c a lm o d e l i n ga n ds t e p w i s e r e f i n e m e n tm e t h o do fp e t r in e t ，f i r s tc o n s t r u c t st h eo v e r a l lm o d e lo ft h es y s t e m ，a n dt h e nt ot h e f l o w sa n dt h es u b o b j e c to fd a t ac o l l e c t i o n ，t h ep r e t r e a t m e n t ，t h ew h o l e s a l ep r i c e ，s e t t l e m e n t p r o c e s s i n ga n dd e p o s i t i n g t oe n s u r et h ei n t e g r i t ya n dt h ec o n s i s t e n c yo fd a t ap r o c e s s i n g ，g i v e s t h ed e s i g na n di m p l e m e n t a t i o no fv e r i f i c a t i o na n dr o l l b a c kp r o c e s s i n g ；p r o p o s e sa ”m u l t i 1 i n k c o m b i n a t i o nb a t c h e s ”m e t h o d ，w h i c hc a nb em o r ee f f i c i e n ta n da c c u r a t ei na c h i e v i n gv e r i f i c a t i o n a n dr o l l b a c kp r o c e s s i n gi nv i e wo ft h ei n s u f f i c i e n c yo fe x i s t i n gi n t e r c o n n e c t i o ns e t t l e m e n t s y s t e m t h r o u g hc o n f i r m a t i o na n da n a l y s i so fm a n yi n s t a n c e sf r o ma c t u a lo p e r a t i o nd a t ao ft h e e x i s t i n gp r o v i n c i a li n t e r c o n n e c t i o ns e t t l e m e n ts y s t e ma n dt h e t e s td a t ao f3 ge x p e r i m e n t a l n e t w o r k ，c o n f i r m st h a tt h ep e t r in e tm o d e lh a st h ec h a r a c t e r i s t i c ss u c ha ss t r u c t u r a l i n t e g r i t y ， o p e n n e s sg o o d ，s c a l a b i l i t ya n ds oo n ；a n dt h ed e s i g np l a no fv e r i f i c a t i o na n dr o l l b a c kp r o c e s s i n g h a sc o m p l e t e l yf u n c t i o n ，r e a s o n a b l ef l o w , s t r o n gf e a s i b i l i t y , a n dt oa c h i e v ee a s y ；”m u l t i 1 i n k c o m b i n a t i o no fb a t c h ”m e t h o dh a sf l e x i b i l i t yw e l l ，s t r o n gt a r g e t e dc h a r a c t e r i s t i c s k e y w o r d s ：i n t e r c o n n e c t i o ns e t t l e m e n ts y s t e m ，3 g ，p e t r in e t ，m o d e l i n g i i 南京邮r u 入学颂【：学位研究生论文术语和定义 术语和定义 序 名词解释 号 将各种电信业务的网间结算、网内摊分( 含专业间摊分) 、漫游结 l 综合结算 算、漫游摊分，综合到统一的平台上、进行统一的结算处理。 j 义的结算是指综合结算，狭义的结算指运营商与外部运行实体 ( 国际及国内电信运营商、虚拟i s p 等) 之间根据相关协议完成通信费 2 结算用的划分与核对的过程。当一次电信服务使用了多个合作伙伴的通信资 源或增值服务资源时，根据各个合作伙伴的资源使用情况，并按合作伙 伴之间所事先拟定的协议进行费用分成。 不同电信运营商之间在互联互通时，由于使用对方的通信资源或服 3网间结算 务，双方根据协议对相关通信费用进行结算处理的过程。 电信运营商之间或电信返营商内部所约定的进行结算或摊分t 作 4 结算周期 的时间周期。 5 结算规则在进行对外结算的处理过程中使用的所有规则。 根据需求从使用记录中抽取的某些属性字段作为统计分析用的最 6 统计要素 小元素。 电信用户使用电信资源或服务后产生的详细使用信息记录，用于对 7使刚记录 刖户计费或运营商结算。包括语音服务的使用记录年数据服务的使用记 录。根据使用记录的处理流稃分为：原始记录、标准记录、批价记录。 8 话单语音业务的使f j 记录通常称为话单。 完成通信服务过程所需要的指定设备所记录的与通信费用有关的 9 原始记录 信息的记录。 1 0 原始话单语音业务的原始记录通常称为原始话单。 1 1 标准记录原始记录经过格式标准化斤的输出称为标准记录 1 2 标准话单语音业务的标准记录通常称为标准话单。 1 3 清单 与帐单相关联。经过计费或结算处理后的最终处理记录。 1 4 结算清单经过结算批价处理后所形成的详细记录。 未在结算协议内描述的，无法判断结算类别的记录或者字段不完整 1 5 无效记录 的记录。 在各个处理环节中产生的无法进行正常处理的使用记录，不包括重 1 6 异常记录复记录、无效记录。异常记录可以通过异常记录处理转换为正常记录， 不能转换的做放弃处理。 指同一次通话或服务中产生的重复使用记录，又称为重单。这里的 1 7 重复记录重复使用记录的判定标准是使用记录中的重单判别字段完全一致，不同 业务的判定标准不一致。 7 1 南京u 火学硕士学位研究生论文 术语和定义 1 8 结算批价按照相关结算协议计算出各项费用的过程。 川丁回退的特定的处理环节，包括结算回退、批价同退、预处理同 1 9 同退步次 退三种。 2 0批次号每一批处理的文件称为一个批次用批次号去标识。 2 1详单 详单也称清单，是标准服务使用记录批价后的记录。 7 2 南京f i | i j u 人学硕l j 学位研究生论文缩略涮 缩略词 n o缩略词英文全称译文 lc d m ac o d ed i v i s i o nm u l t i p l ea c c e s s 码分多址 2c pc o n t e n tp r o v i d e r 内容提供商 3f d m a f r e q u e n c yd i v i s i o nm u l t i p l ea c c e s s 频分多址 g l o b a ls y s t e mf o rm o b i l e 4g s m 全球移动通信系统 c o m m u n i c a t i o n s i n t e m a t i o n a lt e l e c o m m u n i c a t i o n 5i t u 国际电信联盟 u n i o n 6l b sl o c a t i o nb a s e ds e r v i c e s 移动位置服务 7m m sm u l t i m e d i am e s s a g es e r v i c e 多媒体短信息服务 8 q o sq u a l i t yo fs e r v i c e 服务质量 9s m ss h o r tm e s s a g es e r v i c e 短消息服务 l0 s ps e r v i c ep r o v i d e r 服务提供商 1 1t d m a t i m ed i v i s i o nm u l t i p l ea c c e s s 时分多址 t i m ed i v i s i o n s y n c h r o n o u sc o d e 时分同步的码分多 1 2t d s c d m a d i v i s i o nm u l t i p l ea c c e s s 址 7 3 南京邮也人学顾二f ：学位研究生论文图表清单 图表清单 图2 1p e t r i 网图实例5 图2 2p e t r i 网t 1 激发后状态示意图6 图2 3 资源冲突示意图8 图2 4 构建覆盖树1 0 图3 1 电信结算摊分业务分类1 6 图3 2 网间结算系统体系结构18 图3 33 g 业务分类2 0 图4 1 网间结算系统功能示意图2 4 图4 2 网间结算系统层次模型2 5 图4 3 网间结算系统顶层p e t r i 网模型2 6 图4 4 数据采集链接图：2 7 图4 5 数据采集的p e t r i 网模型2 7 表4 1 可识别的记录级错误表2 9 图4 6 格式转换的p e t r i 网模型2 9 图4 7 分拣过滤的p e t r i 网模型图：3 0 图4 8 预处理的p e t r i 网模型31 图4 9 结算类型判别的p e t r i 网模型3 3 图4 1 0 计费批价的p e t r i 网模型3 4 图4 1 1 结算批价的p e t r i 网模型3 5 图4 1 2 排重的p e t r i 网模型3 6 图4 1 3 批价的p e t r i 网模型3 7 图4 1 4 结算处理的p e t r i 网模型3 9 图4 1 5 选取举例4 0 图4 1 6 冲突举例一4 l 图4 1 7 冲突举例二4 l 表5 1x x 省网间结算系统运行维护核对日报表( 文件处理阶段) 4 6 表5 2x x 省网间结算系统运行维护核对日报表( 清单入库阶段) 4 6 7 4 南京邮电大学硕一i ：学位研究生论文 图表清单 表5 3 汇总入库数据处理情况同报表4 7 表5 4 输入参数表4 9 图5 1 数据库系统回退流程图5 0 图5 2 文件回退流程图51 图5 3 单一批次的文件拆分处理示意图5 5 图5 4 改进批次的文件拆分处理示意图5 8 表6 1 用户a 的原始记录6 0 表6 2 用户b 的原始记录6 0 表6 3 用户c 的原始记录6 1 表6 4 用户d 的原始记录6 1 表6 5 数据类业务标准记录6 2 表6 6 语音类业务标准记录6 2 表6 7 数据类业务批价记录表6 3 表6 8 语音类业务批价记录表6 3 表6 9 结算处理记录表6 4 表6 10x x 数据业务日审核校验报表6 5 表6 1 1 需回退报表6 6 表6 1 2 回退后审核校验报表6 6 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：e t 期： 南京邮电大学学位论文使用授权声明 。 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：导师签名：日期： 南京邮i 乜人学顾j ：学位研究生论文第一章绪论 1 1 课题的研究背景 第一章绪论 电信网间互联是指在提供通信网络或者通信业务的企业之间实现网络设备在物理上 和逻辑上的连接，以确保一个电信业务经营者的用户能够与另一个电信业务经营者的用户 相互通信，或者能够使用另一个电信业务经营者的各种电信业务【i 】。 网间结算是指不同电信网互联后，因为一个电信网为另一个电信网的用户提供了服务 并发生了相应的成本，另一个电信网的运营者应向这个电信网的运营者支付一定的报酬。 所付报酬的数量称为网间结算费用【2 】。我国通信网络上的互联互通是以资费为基础，按照 一定的比例进行网间互联的费用结算。也就是说，网间结算是在对用户进行计费的基础上 再按一定原则在不同运营商之间摊分费用【3 】。 我国目前的电信体制改革具有与世界上其它国家不同的特点：它与我国总体的经济体 制改革交叉在一起，与近二十年来的电信技术革命交叉在一起，与世界经济一体化和人类 迈向信息化社会的历史潮流交叉在一起。随着我国电信业务的迅猛发展，新的电信运营商 不断出现，由以前中国电信的“一枝独秀”到现在中国移动、中国联通、中国网通、中国 铁通等公司的“百花齐放”，中国电信业呈现出多家竞争的经营局面，使得各电信公司网 络之间的结算工作变得日益重要。据统计，中国电信每年仅网问结算收入就高达近3 0 0 亿， 而中国联通和中国移动的网间结算支出分别为1 0 0 亿和2 0 0 亿。 近年来，以成本为基础的电信资费和网间结算己经成为世界公认的基本原则。在这个 大环境下，随着电信资费体系不断进行结构性的调整，网间结算的办法和标准也在不断调 整。随着电信业的发展，依附于基础网络的运营商会不断增加，这必然导致竞争的加剧， 使基本电信业务的运营变得更加复杂，各运营商之间的互联互通关系也会越来越复杂，这 就导致电信网间结算功能越来越复杂，同时也越来越重要。对于互联互通的每一方而言， 如果网间结算的功能得不到强化，其损失将是巨大的。因此，网间结算业务越来越受到各 个运营商的重视。 与2 g 相比较，3 g 可以提供更高的传输带宽和速度。在业务模式上，3 g 将提供更为 多样化和个性化的服务，从而吸引大量用户的使用，这将大大增加结算处理的数据量；在 3 g 网络上，业务种类的不断丰富将大大增加结算的难度；在3 g 环境下，各种商业交易 南京邮电入学硕士学位研究生论文 第一章绪论 行为、在线游戏、流媒体、位置服务等的兴起，将对结算的实时性提出更高的要求；同时， 由于3 g 业务的价值链中增加了服务提供商、内容提供商等，因此大大增加了结算的复杂 性。这些变化对于网间结算系统而言将是巨大的挑战。 基于以上情况，本文将对新一代网间结算系统进行深入研究。本研究课题来源于某电 信运营商3 g 网间结算系统的项目研发。 1 2 课题的研究目标 本课题的研究目标是，根据3 g 时代对网间结算系统的要求，结合国内运营商之间结 算的实际情况，遵循易使用性、可扩展性、灵活性等设计原则，采用p e t r i 网作为建模工 具进行网间结算系统的建模，同时对网间结算系统中的关键技术问题进行研究，实现一个 结构合理、功能齐全、实用性强、灵活性高的支持3 g 的新一代网间结算系统。 1 3 论文的组织结构 本文共分七个部分： ( 1 ) 第一章绪论：介绍本文研究课题的背景、研究目标以及论文的组织结构。 ( 2 ) 第二章p e t r i 网概述：首先介绍p e t r i 网的基本概念和性质；其次介绍了p e t r i 网的 两种分析方法，基于可达性的分析和基于不变量的分析；最后介绍了p e t r i 网建模的 优点、原则和一般步骤。 ( 3 ) 第三章3 g 网间结算系统概述：首先对网间结算系统进行了详细介绍，给出了结 算的定义和分类；然后介绍了网间结算系统的发展和体系结构；最后分析了3 g 及其 业务类型和特点，总结了3 g 对网间结算系统的需求，由此引出本文研究的课题。 ( 4 ) 第四章基于p e t r i 网的网间结算建模：首先对网间结算处理的功能进行了描述； 其次采用p e t r i 网分层建模、逐步求精的思想，先构建了系统的整体模型，然后对数 据采集、预处理、批价、结算处理和入库等处理环节及其子对象进行了建模；最后对 p e t r i 网建模的优势进行了分析。 ( 5 ) 第五章网间结算系统中几个关键问题的研究：首先详细介绍了对结算主处理流 程具有重要影响的审核校验的实现方案，然后给出了回退处理的流程设计，最后对批 次进行了改进设计。 ( 6 ) 第六章实例验证与分析：通过实例验证的描述，说明如何利用设计的新一代网 间结算系统进行结算实例的配置，以及如何进行审核校验和回退处理，并进行分析； 2 南京i l gjl l 人学硕i j 学位研究生论文第一章绪论 最后对本文所设计的网问结算系统进行了评价。 ( 7 ) 第七章总结和展望：对本文工作进行总结，并指出需要进一步研究的内容。 南京邮也人学顾j j 学位研究生论文 第二章p e t r i 别概述 第二章p e t r i 网概述 p e t r i 网自6 0 年代由德国学者c a p e t r i 提出以来，经过3 0 多年的发展，己被广泛应用于 各个领域进行系统的建模、分析和控制，如通信协议的验证、网络性能的分析、并行程序 的设计、柔性制造系统的控制、知识推理以及人工神经元网络等。 p e t r i 网是一种适用于多种系统的图形化、数学化建模工具，为描述和研究具有并行、 异步、分布式和随机性等复杂系统提供了强有力的手段，能较好的描述系统的结构，并以 图形表示的组合模型，具有直观、易懂和易用的特点，对描述和分析并发现象有独到的优 越之处。同时，p e t r i 网又是严格定义的数学对象，有完整的数学理论为基础f 4 】。 2 1p e t r i 网介绍 2 1 1p e t ri 网的基本概念 定义2 i ：一个最典型的p e t r i 网可以表示为一系列元素集的组合： p n = ( p ，t ，o ，m o )( 2 1 1 ) 其中p = 露，芝，只 是库所的有限集合， 0 为库所个数： t = t , t 2 ，t m ) 是变迁的有限集合，m o 为变迁的个数；p n t = g ( 空集) ； ，：p xt 专是输入函数，它定义了从p 到t 的有向弧的重复数或权( w e i g h t ) 的集合， 这里= 7 1 ， 为非负整数集； o ：t xp 专n 是输出函数，它定义了从t 到p 的有向弧的重复数或权的集合； m o 为初始状态标识，它为一列向量，其第i 个元素表示第i 个库所中托肯的数目【5 1 。如 图2 1 所示：m o - ( 1 ，1 ，o ) 7 ，表示其中第一个元素为r e ( p , ) = 1 ，第二个元素为m ( p ：) = 1 ，第 三个元素为m ( p s ) = 0 。 4 南京邮电大学硕士学位研究生论文 第二章p e t r i 网概述 p 2 图2 1p e t r i 网幽买例 在表示p e t r i 网结构的有向图中，库所以圆表示；变迁以长方形或粗实线段表示；若从 库所p n 变迁t 的输入函数取值为非负整数w ，记为i ( p ，t ) = w ，则用从p 到t 的一有向弧并旁 注w 表示；若从变迁t 到库所的输出函数取值为非负整数w ，记为o ( p ，) = w ，则用从t 至l j p 的一有向弧并旁注w 表示。特别的，若w = l ，则不必标注；若i ( p ，) = 0 ，或o ( p ，f ) = 0 ， 则不必划弧。i 与0 均可表示为n x 珑非负整数矩阵，0 与i 之差c = 0 一i 称为关联矩阵。圆 圈中的小黑点被称为令牌或者托肯( t o k e n ) ；状态标识m o 为一个向量 聊= 肌( 局) ，m ( p ：) ，朋( 见) 7 为当前状态下库所p 中的托肯数。 2 1 2p e t ri 网的运行 以上定义的是p e t r i 网的静态结构，p e t r i 网的动态特性是在其运行过程中体现出来的。 在p e t r i 网的运行过程中，令牌将被作为一种资源来传递，输入位置中的令牌将减少，输出 位置中将增加。 我们用t 表示t 的所有输入库所的集合，1 f i t 表示t 的输入库所的个数；用t 表示t 的输出 库所( 由来自t 的弧连接的库所，即所有o p ，t ) o 的p ) 的集合，h t 表示t 的输出库所的个 数。此外还用p 与p 分别表示库所p 的输入与输出变迁，他们的个数表示为恻与i p i 。 在p e t r i 网中，我们以变迁t 表示一事件，用变迁的使能表示时间发生因前提条件得以满 足而能够发生。用变迁t 的输入库所( 通过指向t 的弧连接的库所) 表示该时间的发生所需 要的前提局部状态，用由输入库所至t 的输入函数定义这些要求局部前提状态实现的次数， 而局部状态的实现情况由库所中所包含的托肯数目来表示。因此，t 的使能不仅与其输入函 数有关，而且与其所有输入库所的托肯数目有关。为此，引入一下变迁使能规则。 定义2 2 ：一变迁，r 在标识m 下使能，当且仅当：对于所有的p t ：m ( p ) 1 ( p ，t ) 。 在图2 1 中，。f l = p lp 2 ，由t - m ( p ) = 1 i ( p 。，1 ) = 1 ，m ( p ：) = 1 i ( p 2 ，1 ) = 1 ，因此 南京邮i 乜人学硕 j 学位研究生论文第一二章p e t r i 网概述 f 1 使能：而t 2 = p 3 ) 由于r e ( p 3 ) = 0 肌。 在图2 1 所示的p e t r i 网中，在m o 下使能的f l 激发后，将产生新的标识所： m l ( p ) = 拂。( p 1 ) 一j f ( 翻，t ，) + d ( p i ，t i ) = t - t + o = o ； m ：( p ) = m o ( p 2 ) - i ( p ：，) + d ( p 2 ，) - - 1 - 1 + 0 = 0 ； m 3 ( p ) = 聊。( p 3 ) - i ( p a ，f 1 ) + d ( 见， ) = 0 - 0 + 1 = 1 ； m ，= ( o ，0 ，1 ) 1 ： t l 激发分别消耗p 1 中的1 个托肯及p 2 中的1 个托肯，n 日, - t 在p 3 产生一个托肯，这些消 耗与产生的托肯由t 。的输入函数与输出函数确定。t 1 激发后标识变化的结果如图2 2 所示： p 图2 2p e t r i 网t l 激发后状态示意图 p e t r i 网之所以可以用来模拟离散事件系统，关键就在于其动态特性，即其可运行性， 各个变迁的触发既可有严密的逻辑关系，又可完全地相互独立。依据变迁和令牌的不同形 南京邮i 乜人学硕i j 学位研究生论文第二章p e t r i 网概述 式和特性，从基本p e t r i 网又可扩展出很多新型p e t r i 网，例如赋时p e t r i 网、有色p e t r i 网、随 机p e t r i 网等。 2 1 3p e t ri 网的基本性质 ( 1 ) 可达性 定义2 3 ：若从初始标识为m o 开始激发一个变迁序列产生标识m ，则称i t i ，是从m o 可达 的。若从m o 开始只要激发一个变迁即可产生m ，则称i t i ，是从m o 立即可达的。所有从m o 可达 的标识的集合称为可达标识集或可达集，记为r ( m 。) 。 可达性是p e t r i 网的一个重要行为特征，是研究p e t r i 网时所关注的最基本的和最重要的 性质。 ( 2 ) 有界性与安全性 定义2 4 ：对给定p n = ( 尸，丁，0 ，m 。) 及其可达标识凡( ) ，对于库所p p ，对于所有 的m r ( m o ) ：m ( p ) k ，则称p 是k 有界的，此处k 为正整数；若：p e t r i 的所有库所都是k - 有界的，贝, w p e t r i 网是k 有界的。 特别的，k = l 时，即当某库所或是p e t r i 网是1 有界的，我们称该库所或p e t r i 网是安全的 【6 1 o ( 3 ) 活性 定义2 5 ：对于一变迁r t ，在任一标识m r 下，若存在某一变迁序y i j s ，该变迁序 列的激发使得此变迁t 使能，则称该变迁是活的。若一个p e t r i 网的所有变迁都是活的，则该 p e t r i 网是活的【7 1 。 死变迁与死锁从反面描述p e t r i 网的活性，若存在m r ，不存在从m 开始的变迁序列， 该序列的激发使得t 使能，则变迁t 为死变迁。若存在m r ，在此m 下无任何变迁使能，则 称p e t r i 网包含一死锁，该标识为死标识。 出现死锁的原因是不合理的资源分配策略或某些或全部资源的耗尽。p e t n 网的活性以 为着在任意从初始标识m o 死标识可达的标识m 下，总可以通过逐步激发某变迁序列来激发 任意变迁。因此，若p e t r i 网是活的，则其不存在死锁。 ( 4 ) 可逆性 定义2 6 ：一个p e t r i 网是可逆的，若对于每一标识聊r ( m o ) ，m o r ( m o ) 。标识 南京邮电大学硕- | 二学位研究生论文第二章p e t r i 刚概述 m ，尺( ) 称为主宿状态( h o m es t a t e ) ，若对于所有的m r ( m o ) ，m ，是从m 可达的。 由定义知，初始标识m o 是从所有可达标识可达的。可逆性意味着模型可以自身初始化。 这对于自动从差错中回复过来是极为重要的，这是由于经过有限步骤，系统将回到期望的 状态；若无法做到，则不得不人为干预。 ( 5 ) 冲突 定义2 7 ：对给定初始标识m o 的一个p e t r i 网，冲突是指这样一种现象，如果p e t r i 网的两 个或多个变迁同时处于使能即具有发射权的状况，但由于共享某些输入库所，使一个变迁 的发射导致另一个变迁的不能发射。 如图2 3 所示2 个过程都需要资源p 4 进行各自的操作，这是典型的冲突问题。如果 t 1 与t 3 同时使能，但只能两者其一可以激发。我们必须作出决策以决定谁优先激发。 p 5t 3p 6t 47 p 7 图2 3 资源冲突示意图 2 2 基本p e t r i 网的分析方法 对于基本p e t r i 网的分析主要有两种方法，一是基于可达性的分析，二是基于不变量的 分析。前者为图形分析方法，后者为数学方法。 2 2 1 基于可达性的分析 基于可达性的概念，现在作一些扩展，首先介绍可达图的概念。 定义2 8 ：对给定初始标识m o 的一个p e t r i 网，把从初始状态标识m o 开始，能够达到的所 有可能的标识以及产生这些标识的变迁用一个图形表示，图中的节点为状态标识，节点之 间用表示变迁的带箭头的线或弧连接，带箭头的线起端所连接的标识，通过由该线所代表 的变迁的激发，产生该线末端所连接的标识，这样的图称为可达图。 8 南京邮i u 入学顾。i ：学位硎。究生论文第二幸p e t r i 网概述 若p e t r i 网是无界的或p e 仃i 网所描述的系统具有无限个状态，则可达树将无限扩展，为 此，引入覆盖性的概念，用有限表达式来表现无限可达树： 定义2 9 ：若p ：伪2 ( p ) m l ( p ) ，则标识m 2 覆盖m l ，表示为m 2 垅l 。 有了“覆盖性”的定义，可构造覆盖树，用于在有限的树形结构中表示无限的可达树。 首先引入符号( 0 表示“准无限大，用于表示任意大的令牌数，它有以下性质( k 是任意正 数) ：k 肌”( p ) 成立的p ：用取代所( p ) ； ( 4 3 ) 以m 为一节点，从m 至m 画一有向线，并将其记为t ，并将坍- 记为“n e w ”： ( 5 ) 除去m 的“n e w ”标志，回到步骤( 2 ) 。 对于图2 4 中1 ) 所示的模型，构建其覆盖树。初始标识为m 。= ( 10010 ) t 。 南京邮i 乜大学顾j j 学位研究生论文 第一二章p e t r i 网概述 t 4 p 5 m 5 = 10 ( ) 1 ) p e m l 网模型 蛳 l0010 ) t t ， 土 m l = ( o1 01 t t 2 上 m 2 = ( 10 ( 1 ) 1 毋t u r、 m 3 气01 1 毋tm 4 = ( 10 ( ) 10 ) t o l d t 2 3 10 ) t o l d m 6 = ( ol 01 ) t 叫以簧 图2 4 构建覆盖树 通过基于可达树的分析，可以对p e t r i 网模型可能达到的所有状态有清楚的了解，更便 于分析和理解。 2 2 2 基于不变量的分析 基于不变量的分析是一种依据简单的线性代数方程来研究p e t r i 网性能的方法。该方法 基于矩阵线性代数，这里所建立的线性代数方程决定着由p e t r i 网所描述的分都系统的动态 特性。 在p e t r i 网中，弧描述库所与变迁之间的关系，它可用0 与i 这2 个矩阵表示，两者之差 o i 为关联矩阵c 。若用m k 表示第k 次运行( k 0 ) 后p e t r i 网的标识( 一次运行就是激发一个 变迁序列，它可能包括若干变迁的激发，一个变迁可能在一次运行中激发多次) ，则第k + 1 次运行后p e t r i 网的表示为： m + l = m + c p t ，k 0 ( 2 2 1 ) 这里u k 为激发记数向量，它为一( m 1 ) 向量，其第i 个元素表示在第k + 1 次运行中变迁t i 激发的次数。上式称为p e t r i 网的状态方程。特别的，若一次运行仅包含激发某一变迁1 次， 即u k 只有1 个元素为1 ，而其他元素均为0 ，则上式将表示p e t r i 网的激发规则。由于所以库所 中的托肯数是非负的，因此合法的运行( 激发使能的变迁) 将保证： l o l 2 伲 3 3 t p p l 温一 南京邮电人学硕七学位研究生论文第二章p e t r i 网概述 m k + c “k 0 ，对于所有k 0 。 不变量分为p 不变量与t 不变量，它们的定义如下： 定义1 8 ：一个p 不变量为- - ( n x l ) 非负整数向量x ，并满足： x7 c = 0 而一t 不变量为一( m 1 ) 非负向量y ，并满足： c y = 0 ( 2 2 2 ) ( 2 2 3 ) 将式( 2 2 1 ) 两边左乘x t ，得到x t mk + 1 = x 7 m k + x r c p k 。由式( 2 2 2 ) 则有 x t m k + l2 x t m k ，k 0 特别地，从七= 0 递推有石，m o = x t m l = x t m 2 = x7 m 3 = x7 m = 常数，即 x t m - - x 7 m o = 常数 上式表明由p 不变量加权的所有库所中初试托肯数之和为常量。或者说，p 不变量的非 0 元素式相应的库所中托肯数的权值，似的在任何从非i i l o 可达的m 下所有库所中的托肯加 权和为常数。称这些库所被该p 不变量覆盖。 假设经过激发某一变迁序列( 该序列记数向量为u ) ，p e t r i 网从初始标识又返回初始标 识。则由式( 2 2 1 ) 有： m o5m o + c l a 必有c p = 0 ，因此，u 为一t 不变量，即y = p 。这表明t 不变量中的非负元素为将p e t r i 网的标识从m o 出发经一系列变化返回m o 的变迁序列中相应的变迁激发的次数。但是，t 不 变量并不包含这些变迁激发的先后次序。 p e t r i 网的不变量不是唯一的，称那些不是其他不变量线性组合的不变量为基本不变量。 由线性代数可知，若关联矩阵c 的秩为厂= r a n k ( c ) ，则其有( n - r ) 个基本p 不变量与( m - r ) 个t 不变量。 例如求图2 5 所示p e t r i 网的不变量。 南京| i j l 5 i 【1 人学倾1 ：学位研究生论文 第_ 二章p e t r i 网概述 p 1 由于r a n k ( c ) = 2 ，因此存在2 个基本p 不变量与2 个基本t 不变量。 求解工7 c = 0 得：x 2 = 2 x l 与x 4 - - - - - x 3 ，令x l = x 3 = l ，n x 2 = 2 ，x a = l ，得到p 不变量( 121 1 ) 。： 令x l = l 且x 3 = 0 ，则x 2 = o ，x 4 = l ，得到p 不变量( 1001 ) 。 求解c y = 0 得：y 2 = ) r l ，y 4 = y 3 。令y l = y 3 = l ，则得到t 不变量( 1 11 1 ) 1