（计算机软件与理论专业论文）蓝牙串口仿真协议的研究与实现.pdf

中文摘要 摘要：蓝牙协议栈中的串口仿真协议位于l 2 c a p 协议层和应用层协议层之间，提 供了基于l 2 c a p 协议层之上的模拟串口，从而对现有使用串行线接口的应用提供 了支持。本文首先对蓝牙协议体系和串口仿真协议层进行了深入的分析，然后详 细讲述了形式化的协议软件开发方法，即通过形式化技术s d l 语言和消息序列图 对协议进行描述和开发。 传统的协议软件开发主要采用落后的阅读协议然后手工编码的方法，这样的开 发过程耗时较长，代码质量没有保障。形式化的开发方法相对于阅读协议后直接 编码的开发方法来说，具有更高的开发效率和质量。 本文系统地使用了基于状态转换模型的形式化协议开发方法对蓝牙串口仿真 协议进行了形式化描述和实现，详细讲述了通过s d l 和m s c 对协议进行描述、 验证与代码生成的过程，同时介绍了在协议实现过程中注意到的问题，并对各种 描述与验证方法进行了比较。 与传统协议开发方法相比，形式化开发方法不仅能够节省开发时间，而且能 够通过开发过程中的多次验证提高代码的质量，当然这种方法也有不足之处，需 要不断改进，才能得到更广泛的应用。 关键词：蓝牙、串口仿真、l 2 c a p 、s p p 、l a p a b s t r a c t a b s t r a c t ：a sal a y e ri nb l u e t o o t h p r o t o c o ls u i t e ，t h es e r i a lp o r te m l u a t o rp r o t o c o li s b e t w e e nt h el 2 c a p l a y e r a n d a p p l i c a t i o nl a y e r ，o f f e r ss u p p o r to ft h e s e r i a l u s i n g - a p p l i c a t i o nb ys e r i a lp o r te m u l a t o rb a s e do nt h el 2 c a ef i r s t ，t h i sp a p e r g o e sd e e pi n t ot h eb l u e t o o t hp r o t o c o ls u i t ea n ds e r i a lp o r te m u l a t o rp r o t o c o l ，t h e n e x p l a i nt h ef o r m a lm e t h o do fd e v e l o p i n gp r o t o c o ls o f t w a r ew h i c hi su s i n gt h ef o r m a l m e t h o ds d l l a n g u a g ea n dm e s s a g es e q u e n c ed i a g r a m t h eo l dm e t h o di nt h ed e v e l o p m e n to fp r o t o c o ls o f t w a r ei ss t i l li nu s e b yr e a d i n g p r o t o c o ls p e c i f i c a t i o na n dt h e nc o d i n gm a n u a l l y , w h i c hi st i m e - c o n s u m i n ga n dc a n n o t e n s u r eg o o dq u a l i t yo fs o u r c ec o d e t h ef o r m a lm e t h o do fd e v e l o p i n gp r o t o c o lh a s b e t t e rq u a l i t ya n de f f i c i e n c yt h a nt h eo l dm e t h o d t h i sp a p e re x p l a i nt h ed e s c r i p t i o na n di m p l e m e n to f b l u e t o o t hs e r i a lp o r te m u l a t o r p r o t o c o l ，a n da n a l y z e si nd e t a i lo ns p e c i f y i n g ，v a l i d a t i n ga n dc o d eg e n e r a t i o nb ys d l a n dm s c s o m es p e c i f i cm e t h o d so fs p e c i f i c a t i o na n dv a l i d a t i o na r ec o m p a r e da n d p r a c t i c a lo n e sa r er e c o m m e n d e d c o m p a r e dw i t ht r a d i t i o n a lw a y s ，t h ef o r m a lm e t h o do fd e v e l o p m e n tc a l lr e d u c e d e v e l o p i n g t i m ea n di m p r o v et h ec o d e q u a l i t yd r a m a t i c a l l y h o w e v e r s o m e d i s a d v a n t a g e sh a v e t ob es o l v e dt om a k ei tm o r eu s e f u li n p r o t o c o ls o f t w a r e d e v e l o p m e n t k e y w o r d s ：b l u e t o o t h ；s e r i a lp o r te m u l a t o r ；l 2 c a p ；s p p ；l a p 致谢 本论文的工作是在我的导师李伟生教授的悉心指导下完成的，李伟生教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 李伟生老师对我的关心和指导。 李伟生教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向李伟生老师表示衷心的谢意。 李伟生教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，郭铃、赵光嗣等同学对我论文研究工作给予 了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 1 蓝牙技术简介 1 引言 蓝牙作为一种实现开放性短距离无线通信的技术，其主要面向移动设备之间的 小范围连接，蓝牙工作在无需申请的2 4 g h z 频段，使用调频扩频( f h s s ) ，适用于 在小型的办公和家庭网络中实现全方位的语音与数据通信的传输。 在1 9 9 8 年，随着计算机网络和移动讯息技术的迅猛发展，小范围内无线数据 与语音通信的发展显得越来越需要。诺基亚、爱立信，i n t e l 、i b m 等公司联合推 出了蓝牙这项新的无线网络技术。蓝牙特殊兴趣组织s i g ( s p e c i a li n t e r e s tg r o u p ) 专 注于蓝牙技术的开发，1 9 9 9 年7 月份蓝牙s i g 推出了蓝牙协议1 0 版，从而将其 推向了应用阶段。迄今为止，s i g 已经拥有9 个成员及1 0 0 多个辅助商和2 0 0 0 多 名参与者。 蓝芽技术解决了小型移动设备间的无线互连问题。蓝牙技术的硬件市场非常广 阔，涵盖了包括如计算机、移动电话在内的局域网数据及语音设备。蓝牙技术面 向移动设备间的小范围连接，所以从本质上说它是一种电缆替代技术。蓝芽技术 力图将通用电缆在成本、承载能力和安全等方面的优势尽可能地发挥出来，支持 应用层和链路层的认证和加密，做到像电缆一样安全，并且能够降到和电缆一样 的成本，而且可以同时连接多个移动用户的多个设备，从而形成微微网；并且能 够支持不同微微网之间的互连，能够支持高速率以及支持包括声音和数据在内的 不同数据类型；在功耗方面也要满足低功耗和致密性要求，以便其能够嵌入到小 型的移动设备中。 蓝牙协议栈中的串口仿真协议是在欧洲电信标准协议e t s i t s 0 7 1 0 规范的基 础上进行修改而来，其位于l 2 c a p 协议层和应用层协议层之间，提供了基于 l 2 c a p 协议层之上的模拟串口，从而对现有使用串行线接口的应用提供了支持， 这样就可以尽可能利用现有的各种高层应用程序，保证b l u e t o o t h 技术与现有技术 的融合以及各种应用之间的互通性，充分利用兼容b l u e t o o t h 技术规范的软硬件体 系。 1 2 本文研究内容及组织结构 本文第二章对蓝牙协议体系和串口仿真协议层进行了深入的分析，在第三章中 详细介绍了形式化的协议软件开发方法，即通过形式化技术s d l 语言和消息序列 图对协议进行开发。采用形式化的开发方法相对于阅读协议后直接编码的开发方 法来说，具有更高的开发效率和质量。 本文的第四章系统地讲述了使用基于状态转换模型的形式化协议开发方法对 蓝牙串口仿真协议进行了形式化描述和实现的过程，介绍了在协议实现过程中注 意到的问题；并讨论了常用的交互式验证、随机验证和全搜索验证方法，对各种 验证方法的优缺点进行了比较，总结出了协议验证的经验。 在本文的第五章介绍了如何使用串口应用规范对串口仿真协议进行封装，从而 使其能够被加以实际的应用。 2 2 蓝牙协议及其体系结构 2 1 蓝牙协议体系概述 作为一种以安全的方式把众多的移动设备连接起来的网络技术，蓝牙技术实 质上建立起了通用的无线电空中接口及其控制软件的公开标准，使得遵守这种无 线数据通信规范的计算机及其它设备不使用电缆互连而相互通信。作为一个综合 协议系统，蓝牙协议采用将协议固化在p c 等设备芯片中的应用模式，这种模式使 得其控制方式相当便捷，而且具有同各种操作系统良好的兼容性。 i o b e x p p p la t 命令 t c p i p 蓝牙协议体系中的协议按s i g 的需要分为四层：核心协议b a s e b a n d ，l m p 、 l 2 c a p 、s d p ；电缆替代协议r f c o m m ；电话传送控制协议，t c sb i n a r y 、a t 命令集；可选协议，p p p 、u d p 厂r c p i p 、0 b e x 、w a p 、v c a r d 、v c a l 、i r m c 、w a e 、 a v d t p 等。除上述协议层外，规范还定义了主机控制器接口( h c i ) ，它为基带 控制器、连接管理器、硬件状态和控制寄存器提供命令接口。设计协议和协议栈 的主要原则是尽可能利用现有的各种高层协议，保证现有协议与蓝牙技术的融合 以及各种应用之间的互通性，充分利用兼容蓝牙技术规范的软硬件系统。蓝牙技 术规范的的开放性保证了设备制造商可自由地选用其专利协议或常用的公共协 议，在蓝牙技术规范基础上开发新的应用。 蓝牙核心协议由s i g 制定的蓝牙专利协议组成，绝大部分蓝牙设备都需要核 心协议( 加上无线部分) ，而其它协议根据应用的需要而定。总之，电缆替代协议、 电话控制协议和被采用的协议在核心协议基础上构成了面向应用的协议。 2 2 蓝牙核心协议 2 2 1 基带协议( b a s e b a n d l 基带和链路控制层确保各蓝牙设备单元之间由射频构成的物理连接。蓝牙的 射频系统是一个跳频系统，其任一分组在指定时隙、指定频率上发送，它使用查 询和寻呼进程同步不同设备间的发送频率和时钟，可为基带数据分组提供两种物 理连接方式：面向连接( s c o ) 和无连接( a c l ) ，而且在同一射频上可实现多路 数据传送。a c l 适用于数据分组，s c o 适用于话音及话音与数据的组合，所有话 音与数据分组都附有不同级别的正向纠错( f e c ) 或循环冗余校验( c r c ) ，而且 可进行加密。此外，不同数据类型( 包括连接管理信息和控制信息) 都分配一个 特殊通道。 可使用各种应用在蓝牙设备问传送话音，面向连接的话音分组只需经过基带 传输，而不到达l 2 c a p 。话音应用在蓝牙系统内相对简单，只需开通话音连接， 就可传送话音。 2 2 2 连接管理协议( l m p ) 连接管理协议( l m p ) 负责蓝牙各设备间连接的建立。它通过连接的发起、 交换、核实，进行身份验证和加密，通过协商确定基带数据分组大小；它还控制 无线设备的电源模式和工作周期，以及各设备单元的连接状态。 2 2 3 主机控制接口( h c i ) 在b b 和l m p 上与l 2 c a p 之间还有一个主机控制接口层h o s tc o n t r o l l e r i n t e r f a c e ( h c l ) 。h c i 是蓝牙协议中软硬件之间的接口，它提供了一个调用下层b b 、 l m p 、状态和控制寄存器等硬件的统一命令接口。h c i 协议以上的协议软件实体 运行在主机上，而h c i 以下的功能一般由蓝牙设备硬件来完成，二者之间通过一 个对两端透明的传输层进行交互。 通过h c i 传出的信息可包括命令、事件、数据三类。命令由主机端发给硬件 设备，事件由设备提交给主机，数据则是双向的。下面简要介绍这三类信息。 由主机发给设备的命令按执行方式可分为同步命令和异步命令。同步命令主 4 韭丞銮塑左堂亟堂焦盈塞笪星垃这厦墓佳丕结也 要用于本地查询和设置参数，完成后立即返回类似于c o m m a n dc o m p l e t ee v e n t 的命令完成事件；异步命令一般涉及到双方的通信，比如建立连接等，h c i 固件 接收到命令后，先返回一个命令状态事件c o m m a n ds t a t u se v e n t ，表示命令参数 的正确与否，完成后再返回一个命令完成事件。 两个蓝牙设备之间只能建立一条a c l ( a s y n c h r o n o l l sc o n n e c t i o n l e s s ) 信道，但可 以建立多条s c o ( s y n c h r o n o u sc o n n e c t i o n o r i e n t e d ) 信道。a c l 主要用来收发数据， s c o 主要用于话音通信。连接建立起来后，主机控制器( h c ) 将从主机端收到的数 据通过l m 、b b 和r f 发送出去，当收到数据时则过程相反。 2 2 4 逻辑链路控制和适配协议( l 2 c a p l 逻辑链路控制适配层协议( l o g i c a ll i n kc o n t r o la n da d a p t a t i o nl a y e rp r o t o c o l 简称l 2 c a p ) ，是一个为高层传输层和应用层协议屏蔽基带协议的适配协议。 l 2 c a p 位于基带协议层之上，属于数据链路层，它在整个协议层体系中的地位如 图2 - 1 。l 2 c a p 为高层提供数据服务，允许高层和应用层协议收发大小为6 4 k b 字 节的l 2 c a p 数据包。虽然基带协议提供了s c o 和a c l 两种连接类型，但是l 2 c a p 只支持面向无连接的异步传输( a c l ) ，不支持面向连接的同步传输( s c o ) ，s c o 链路主要用预留的带宽进行实时语音传输。 2 2 5 串口仿真协议( r r c o m m ) 蓝牙串口仿真协议是基于e t s l0 7 1 0 规范的串口仿真协议。e t s i ( 欧洲电信 标准协会) 是一个在欧洲范围内制定电信标准的非盈利性组织。蓝牙串口仿真协议 只是应用了g s m0 7 1 0 协议标准的一个子集，并且在g s m0 7 1 0 的基础上作了适 于蓝牙的改动和扩展。这一串口仿真协议在蓝牙基带协议上仿真r s 2 3 2 控制和数 据信号，为使用串行线传送机制的上层协议( 如o b e x ) 提供服务。b l u e t o o t h 特 别兴趣小组提出蓝牙串口仿真协议的目的在于以下几点：提供对现有使用串行线 接口的应用软件的支持；利用已有的g s m0 7 1 0 标准；支持b l u e t o o t h 设备之间点 对点的通信。 蓝牙串口仿真协议完成了对r s 2 3 2 串口的仿真，这样就可以尽可能利用现有 的各种高层应用程序，保证b l u e t o o t h 技术与现有技术的融合以及各种应用之间的 互通性，充分利用兼容b l u e t o o t h 技术规范的软硬件体系。其中最常用的是基于串 行线传送机制的高层协议，如：o b e x 、p p p 和a t 命令集。其中p p p 完成点对点 的连接；o b e x ( 对象交换协议) 是由红外数据协会( i r d a ) 制定的会话层协议， 它采用简单的和自发的方式交换目标数据，它是一种类似于h 1 v r p ( h y p e r t e x t t r a n s f e rp r o t o c 0 1 ) 的协议，假设传输层是可靠的，采用客户机一服务器模式，独 立于传输机制和传输应用程序接口；a t 命令集是专门为调制解调器设计的接口， 用来提供拨号上网和收发传真的功能。 根据实现方式不同，存在两种不同的b t 设备。类型1 的b t 设备本身具有完 整的b l u e t o o t h ( b t ) 硬件和软件，能独立完成b l u e t o o t h 的功能，实现通信设备之 间的短距离无线连接。类型2 的b t 设备仅仅起到类似于m o d e m 的功能，负责将 普通设备所要传输的信息与b l u e t o o t h 格式的码流的相互转换。当采用类型2 的b t 设备时，数据传输的瓶颈在于实际的串口之间的有线连接，即受到标准串口最高 速率9 2 1 6 0 0 b i t s 的限制；而采用类型1 的b t 设备时，数据传输的速率则不受到 串口速率的限制。 串口仿真协议中的组件如表2 1 所示： 表2 - 1 串口仿真协议组件 组件备注 应用程序是指应用串口通信接口的应用程 序 端口仿真实体 端口仿真实体将具体系统的通信 接口( a p i ) 映射为r f c o m m 的服务。 端口仿真实体加上r f c o m m 组成一个 端口驱动程序。 r f c o m m提供了在l 2 c a p 信道上的透明数 据流和控制信道。复用了多个仿真串 口。 服务注册发现 服务应用程序注册在本地设备上， 并为客户应用程序提供服务以便客户 应用程序连接到其他设备上的服务应 用程序。 l 2 c a p协议复用，s a r 基带 b t 定义的基带协议 2 2 6 蓝牙应用框架( p r o f i l e s ) 在蓝牙规范中定义了一些高层应用框架( p r o f i l e s ) ，其中较典型的有拨号网络 6 ( d i a l u pn e t w o r k i n g ) 、耳机( h e a d s e t ) 、局域网访问( l a na c c e s s ) 、文件传输( f i l e t r a n s f e r ) 等，分别对应一种应用模式。蓝牙系统软件组成中，最高层的各种应用程 序可以通过各自对应的p r o f i l e 实现无线通信。也就是说，每一个高层应用程序加 上相应的竖向的协议栈即为一种p r o f i l e ，即应用模型。 对于每一种蓝牙应用，除核心协议外，其他三层协议可以按照需要来选择使 用。如局域网访问应用，除核心协议外只使用了r f c o m m 、s d p 、p p p 、t c p f l p 等协议。 再如音频视频传输应用，使用的协议和应用规范有： a v d t p 一音频视频传输协议 g a v d p一音频视频传输应用规范 a 2 d p 一高级音频传输应用规范 v d p 一视频传输应用规范 s d p一服务发现协议 在此应用中，用户在听音乐时可以通过无线连接的方式摆脱数据线的束缚。 把次应用使用在家庭影院中，则可以减少布线的麻烦并方便以后的移动。 2 3 蓝牙控制流及数据流 2 3 1 蓝牙数据流 蓝牙可以传输同步和异步数据。同步数据一般直接由硬件接出如输出给耳机， 异步数据流则要通过软件层。 a p p l i c a t i o n s d pt c sr f c o m m 善 il 2 c a p l 害 l i - t c i i 图2 - 2 蓝牙异步数据流 蓝牙协议栈为高层应用提供透明信道，完成与远端高层应用的透明数掘交换。 如图2 2 所示，当发送蓝牙异步数据时数据的走向为 a p p r f c o m m l 2 c a p h c i 硬件；接收异步数据时的数据走向为：硬件 7 h c i l 2 c a p - r f c o m m a p p 。 2 3 2 蓝牙控制流 a p p l i c a t i o n k t 1 t c o n f ir 一 、 s d p li t c s i l r f c 0 m l t e t 十c 。f i l 2 c a p 一。t 1 t “n m m h c i 幽2 3 监牙控制流 协议栈的每一层都接受上一层的命令，并向下一层发送命令，接收下一层提 交的事件，向上一层报告事件。在串口读写操作的过程中，应用程序a p p 通过打 开、关闭、读和写等命令操作仿真串口。仿真串口向r f c o m m 发出与远端建d l c 链、拆除d l c 链和发送接收数据的的指令，r f c o m m 层向下发出由l 2 c a p 建立 设备间蓝牙数据链路的指令，完成整个数掘收发的过程。 2 4 移动及安全性 蓝牙系统的移动性和开放性使得安全问题极其重要。虽然蓝牙系统所采用的 跳频技术就已经提供了一定的安全保障，但是蓝牙系统仍然需要链路层和应用层 的安全管理。在链路层中，蓝牙系统提供了认证、加密和密钥管理等功能。每个 用户都有一个个人标识码( p i n ) ，它会被译成1 2 8 b i t 的链路密钥( l i n kk e y ) 来 进行单双向认证。一旦认证完毕，链路就会以不同长度的密码( e n c r y p t i o nk e y ) 来加密( 此密码以8 b i t 为单位增减，最大1 2 8 b i t ) 链路层安全机制提供了大量的认 证方案和一个灵活的加密方案( 即允许协商密码长度) 。 当来自不同国家的设备互相通信时，这种机制是极其重要的，因为某些国家 会指定最大密码长度。蓝牙系统会选取p i c o n e t 网中各个设备的最小的最大允许密 码长度。例如，美国允许1 2 8 b i t 的密码长度，而西班牙仅允许4 8 b i t ，这样当两国 的设备互通时，将选择4 8 b i t 来加密。 蓝牙系统也支持高层协议栈的不同应用体内的特殊的安全机制。比如两台计 算机在进行商业卡信息交流时，一台计算机就只能访问另一台计算机的该项业务， 而无权访问其它业务。蓝牙安全机制依赖p i n 码在设备间建立信任关系，一旦这 种关系建立起来了，这些p i n 码就可以存储在设备中以便将来更便捷的连接。 9 3 协议的形式化开发方法 3 1 形式化描述协议模型 通信系统互连参考模型( o s l j r m ) f h 国际标准化组织( i s o ) 定义，采用分层技术 将通信系统按照功能划分为若干个层，对每层执行的功能进行了明确定义。上下 层之间通过必要的接口进行交互，上层通过接1 ：3 调用下层的功能，下层为上层提 供服务；每一层按照预先定义的规则，通过数据和控制信息的交互完成设定的功 能。其中预先定义的规则就是协议，互相传递的数据和控制信息被称作协议数据 单元( p d u ) 。 服务用户 通信甩户卜厂五忑歪罪- 且l 肿服务i 正- - 可夕务提供者_ 氆入争 ( n + 1 ) 层 n 服务 n 层 ( n - i ) 服务 图3 一i 协议层模型 通信系统互连参考模型中的应用层、表示层和业务层是面向应用的协议层， 用于用户应用程序的相互通信。这部分协议层屏蔽了网络细节，给用户应用程序 提供了一个类似于本地服务的界面，主要在本地操作系统中实现；协议层模型中 传输层的功能是为上层协议实体提供系统间数据透明传输的能力；协议层模型中 的网络层、数据链路层和物理层实现数据的传输，是面向网络的协议层。 通信系统互连参考模型作为一个参考模型，具体应用时需要根据需求定义出 协议的体系结构。蓝牙协议中的各层与通信系统互连参考模型中的各层之间存在 大致的对应关系：链路管理层、基带层和射频层是面向网络的协议层；逻辑链路 控制和适配层相当于传输层；蓝牙主机控制器接口是逻辑链路控制和适配层与链 路管理层之间的一个接口；电话通信协议层、串口仿真协议层和服务发现协议层 是面向应用的协议层。 l o 3 1 1 协议的形式化描述方法 协议工程指的是协议的一体化、形式化开发过程。在这个过程中，协议的转换 及验证、证实及性能分析以及一致性测试在同一个系统内前后衔接地完成。协议 转换负责将协议的非形式化描述文本转换成形式化的描述文本。状态转换模型和 进程模型是两种主要的协议形式化描述模型。其中的状态转换模型认为，通信协 议由若干事件驱动实体组成，每个实体的特性可以描述为一系列响应外部和内部 事件的动作，实体问通过消息进行通信。常用状态转换模型有限状态机$ ! p e t r i 网。 二者相比，有限状态机( f i n i t es t a t em a c h i n e s s ) 易于验证，可以简单明了的描述协 议事件和协议状态之间的关系，但描述协议元素的能力不够，对于复杂的协议会 因为状态数目的急剧上升导致状态转换过于复杂，有时甚至可能产生状态爆炸。 扩展的有限状态机力图弥补这个不足。与有限状态机相比，p e t r i 网具有能够较好 描述并发性的优点，从而可以提高协议功能的并发度，并及早发现和解决协议中 潜在的碰撞现象。 进程模型的原理为以进程作为演算元素建立进程代数系统，进程代数系统规 定了明确的定义和代数变换法则，具有高抽象度。在协议的形式化描述之后进行 对协议说明中语法语义正确性的检查。在协议说明设计完成以后，对其所具有的 特性进行评价，最后根据协议说明测试协议实现与协议说明的一致性。 3 2 形式化描述语言s d l 形式化描述语言s d l 是一种用来描述分布式并行信息处理系统的形式化技 术，可以看作是形式化协议模型与程序设计语言的结合。s d l 语言一方面可以充 分描述协议的并发性、时序性、不确定性等各种特性，另一方面又具有程序设计 语言可读性好的优点，因此适用于描述o s i 体系中的通信协议和服务。对协议进 行s d l 描述可以消除协议非形式化描述的二义性，在描述完成后可以自动生成协 议实现代码和测试用例。 s d l 由i t u - t 在1 9 7 8 年制订，此后每四年推出一个新的版本。s d l 的最初版 本面向串行系统，很少涉及到并行，而且基本上是非形式化的。1 9 8 6 年版s d l 引 入了数据和数据结构；1 9 9 0 年版s d l 开始真正形式化并成为一项成熟的形式化描 述技术；1 9 9 4 年版s d l 引入了面向对象的概念，增加了如数据类型和在所谓的包 中维护类型库的能力等新特性；1 9 9 8 年以后s d l 进行的升级较少。与大多数形式 化语言不同的是，s d l 不仅可以用文本表示( 比如数据和信号的定义) ，一而且具有 图形化的表示形式，这使得s d l 具有友好的用户界面并且易于使用。 s d l 协议描述包括协议提供的服务、协议实现环境假定、实现协议所需消息 集合、消息的编码规则、信息交互一致性规则五个基本元素，其描述的对象都处 在特定的环境当中；任何系统之外的因素都看作是环境的一部分，系统与环境之 间通过信号进行通信。 系统最重要的属性是行为，系统行为由其中包括的所有进程实例来体现。每 个进程实例都有自己的存储空间，除某些定义为外部可见的变量外不能为其它进 程访问；进程实例之间可以互相通信，比如可以通过进程间互发信号来改变变量 值，进程也可以与环境交互信号；各进程实例具有同样的特性，当一个进程实例 创建另一个进程后二者就并行存在，没有继承关系。一个进程实例就对应一个扩 展的有限状态机，扩展的有限状态机之间通过交换携带参数信息的信号而相互影 响；每一个进程实例分配一个无界的先进先出缓冲区作为接收信号的输入队列， 所以信号到达的顺序与其存入、取出和使用的顺序一致；一个进程实例在某一时 刻或者处于等待状态、或者正在进行状态间的转换，进行何种状态转换由自口一状 态和输入信号决定；环境也可以看作是一个与系统通过信号进行通信的进程。 3 2 1s d l 描述方法 用s d l 描述系统时将实际的系统划分为系统、模块、进程和过程四个层次， 这样做可以隐藏细节信息和有效控制模块大小，并可以对已有代码进行重用，下 面对这四个层次分别进行讲述： 印咖m 咖瑚 1 b 崮幽1 ，l ，) l 酽 口 骝、揭 q 捆峙七剥 图3 - 2 s d l 系统结构概貌 系统级描述 如图3 - 3 所示，s d l 系统级描述表示出了组成系统的各个模块及各模块之间 的相互联系，不显示各模块内部的细节。 1 2 图3 - 3s d l 系统 上图给出了一个典型的s d l 系统描述，系统由模块构成，每一个模块实现系 统的某一部分功能，两个模块间及模块与环境之间通过信道( c h a n n e l ) 通信。其中的 模块既可像图中那样直接定义和使用，也可以先定义一个模块类型，通过模块实 例( b l o c k i n s t a n c e ) 进行引用。模块间的信道上标出了信道号和每个方向上传送的信 号或者信号集。这里也可以定义整个系统中可见的数据和信号。 模块级描述 如图3 - 4 所示，s d l 模块级描述表示出了组成模块的各个部分及各部分之间 的相互联系，同样不显示进程内部的各种细节。 图3 - 4s d l 模块 在上图给出的一个s d l 模块描述中，模块由进程组成，每一个进程实现模块 中的一部分功能，进程相互之间以及进程与外界之间通过信号通道进行通信；模 块中的进程既可直接定义和使用，也可以先定义一个进程类型，通过定义进程实 例来引用。 对比图3 3 和图3 4 可以看出，模块与系统的不同之处就在于模块能够成为系 统或者模块的组成部分，能够出现在系统内部而且可以嵌套；而系统不能成为系 统或者模块的组成部分，其只能出现在顶层。采用将系统划分成模块、进而将模 块划分为实现有限功能的各个进程的策略是为了有效避免发生状态爆炸，出于同 样的原因，s d l 中还使用了过程，其中仅包括一定条件下的动作集合而没有状态 的转换及信号的输入。 进程级描述 如图3 5 所示，s d l 的进程级描述中包括输入端口、扩展的有限状态机、时 钟和变量等四个主要部分。每个s d l 进程都有一个系统中唯一的p i d 数据类型标 识，其主要用来指明输出的目的进程，其数值可以从以下p i d 表达式获得：s e l f 进程本身；0 f f s p r 玳e 一此进程最近创建的进程实例；p a 趾n 卜如果 此进程是动态创建的，则p a r e n t 表示创建进程；s e n d e r 进程最近处理的 消息的发送者。 输入端口负责接收到来的新信号。信号即单个的消息，其中带有发送方标识 号和附加数据。当一个信号到达进程后，立即被送到输入端口，由扩展的有限状 态机处理。扩展的有限状态机处理信号的顺序与其到达的顺序一致，并根据信号 的名字来决定执行哪一个状态转换。每处理一个信号，扩展的有限状态机就执行 一次状态跳转，同时还可能产生输出信号来对变量或者时钟进行操作。 l r t “高乞卜s 。 t i m e o u t sl 掣南 图3 - 5s o l 进程 扩展的有限状态机的状态转换行为可由进程图来表示，进程图可以准确地描 述进程如何对每一种可能的输入产生响应。进程可以在系统启动时创建，也可以 在已有进程请求时动态创建，如图3 - 6 所示，进程图的第一个符号是表示开始的符 号，接着是进程创建后立即执行的一次转换。进程开始后将首先进行初始化工作， 如调用初始化过程，完成初始化工作后进入第一个状态，有限状态机在此状态下 等待输入，输入到来后，进程根据输入信号来进入不同的分支，处理不同的信号。 对每一种状态都定义了一些可能的转换，在每一次转换中，首先指明引起此转换 的输入信号，接着按一定的顺序描述下一个状态到达之前所执行的动作。有限状 态机在接受输入信号及其携带的信息后进行动作，如设置变量值、初始化或设置 时钟、输出信号等。完成后根据输入队列中的输入信号继续执行下一状态或者等 1 4 待输入信号的到来。 时钟处理 图3 - 6s d l 进程 s d l 中的时钟操作是一种特殊的动作，具有重要的作用；一个时钟进入活动 状态前需要进行设置，设置时钟时要指定一个具体的数值作为时钟的超时周期， 一旦超过了超时周期时钟将进入不活动状态，同时系统将发出超时消息。设置活 动时钟后时钟将继续处于活动状态，但是具有新的超时时问值。重置时钟可以使 时钟进入不活动状态。图3 7 所示为时钟状态的变迁。 i n a c t i v ea c t i v es e t ()() _ 1 雨丽f - 、。一 图3 7 时钟状态的变迁 时钟声明为t i m e r 类型的变量，s d l 系统中还有两种与时钟有关的特殊的数 据类型 v l m e 和d u r a t i o n ，分别表示时间点和时间段的概念。t i m e 类型的表达式 “n o w + d ”表示未来的一个时问点，即操作符n o w 返回的当前时问经过d u r a t i o n 类型的变量d 表示的一段延时后的时间点。如果设置一个时钟时带上变量 “n o w + 5 ”，就表示从当前时间点开始5 秒钟后时钟将超时。 由 超时消息是s d l 系统的一个内部消息，但是对于进程而言，超时消息与其它 消息并没有区别。通信系统中常常要用到时钟，对系统的某些处理加上时问限制， 比如各种请求的响应，等待已丢失的数据等，如果没有时钟机制，进程会由于没 有响应而陷入无限等待，导致整个系统没有响应。 3 2 2 消息序列图 消息序列图( m s c ) 在描述通信系统的过程中被用作s d l 描述的辅助手段。 s d l 和消息序列图这两种系统描述方法在很多方面可以起到互补的作用。s d l 以 进程为中心，可以对单个s d l 进程的行为进行清晰全面的描述，但是由于不能直 接表示出进程间的通信过程，因而描述出的系统在很多方面不够直观透明。相对 而言，消息序列图主要用于描述通信系统的一次执行过程中通信实体之间以及与 环境之间的消息交互过程，消息序列图以消息交互为中心，描述的是系统组件问 以及与环境之间交互消息的通信行为，用类似于消息流图的形式表述系统的执彳亍 轨迹。消息序列图描述的是进程与外部的消息交互，进程本身作为一个元素存在， 其内部的动作是对外不可见的。 在系统开发的各个阶段，消息序列图都可以作为s d l 的辅助手段。使用s d l 进行完整的静态的系统描述，而在动态地对协议运行的一个片断进行直观描述时 使用消息序列图。 消息序列图描述方法 如图3 8 所示，消息序列图中主要包括进程实例和消息、时钟、进程创建和终 止等。消息序列图也有文本和图形两种语法形式，当把图形化描述转换为对应的 文本描述时会丢失一些图形信息。 在图3 - 8 ( a ) 中，消息序列图的边框代表了系统的环境；其中的纵轴为时间轴， 每条竖线都代表一个进程实例，进程实例之间的箭头表示消息，箭头的方向标明 了消息的发送者和接收者。进程实例按时间先后顺序发生的各个事件显示在一条 竖线上，最后的实心黑线标明了此进程实例的终止。 1 6 韭塞銮堑左堂亟堂位迨塞垃邀丝丝式丝珏攘直迭 a 典型的m s c 图 b 时钟超时 c 时钟清零d 进程实例的创建 图3 - 8 m s c 图 在图3 - s c b ) 中，进程i n i t i a t o r 发出消息m l 后启动时钟t i m e r ，并等待返回消息 的到来直到时钟超时，当时钟超时发生时进程i n i t i a t o r 向上层服务用户发送相应的 超时消息。图3 - 8 ( c ) 中的i n i t i a t o r 进程在时钟超时之前收到了对端的返回消息，然 后重新设置了时钟。通信系统在必要的时候应该能够创建新的进程实例，在图3 - 8 ( d ) 中，进程i n i t i a t o r 在特定的情况下，创建新的进程实例r e s p o n d e r 。该实例在创建 后就可以自行执行下去，与其它在系统初始时就得到创建的进程实例没有区别。 3 2 3 形式化协议开发工具 在协议软件的形式化描述、验证、代码生成与测试过程中，需要使用商用协 议形式化开发工具，如c sv e f i l o g 的o b j e c t g e o d e 软件工具包。o b j e c t g e o d e 工具 包中集成了生成s d l 、m s c 图的图形化编辑工具，静态和动态的语法检查工具， 生成可执行代码的应用程序生成器，以及在整个开发周期中保证总体一致性的机 1 7 制。o b j e c t g e o d e 的组件包括用来描述协议的编辑器；用来检查s d l m s c 中语法 错误的编译器；用来进行协议仿真的仿真器；以及代码生成器，作用为从s d l 生 成c 代码；还有运行库，其为从s d l 生成的c 代码提供支持。 3 - 3 有限状态机 使用有限状态机来描述通信系统中协议实体的行为时，一个协议实体在任何 时候都处于数目有限的状态中的某一个，当有限状态机的接口处发生有效输入事 件时，有限状态机会从一种状态变迁到另一种状态并在层接口处产生输出协议数 据单元。接口处的有效输入事件包括从上层接口收到一个服务原语、从下层接口 收到一个服务原语和从与本地实体交互( 如计时器或管理子层) 的接口处收到一 个服务原语。 ( n + 1 ) 层 n 层 ( n - i ) 层 图3 - 9 输入事件接口 如图3 - 9 所示，所有的输入事件都假定为原子化的，一个协议实体在处理另一 个事件之前要执行与前一个事件相关的所有操作( 输出事件、具体动作、状态改 变) ，从而保证每个输入事件都以原子化的方式处理。每个接口都实现为一对队列： 一个队列用于实现对协议实体的输入，另一个用于实现对协议实体的输出，协议 实体以规定的方式服务于这些队列。在处理输入事件时可能进行动作如启动一个 计时器或者修改一个( 多个) 有限状态机变量。 3 3 1 有限状态机的非形式化描述 使用事件状态表和状态转换图对有限状态机进行的描述为非形式化描述。有 限状态机使用事件状态表来表示时如下表所示，表中的每一登录项指定对于此输 入事件和当前状态适当的输出事件( 连同任何具体的动作) 和有限状态机的新状 态。有效的事件一状态结合在表中才有登录项，所有其它的结合为空登录项，是一 种协议错误，应按预先规定的方法处理。 当前s 0s 1 s j s n 状态 输入事件、 j e o ! i e l l e i o e c i ，j ) ， ： s k x i e m 上表中，o e ( i ，j ) s k x 表示有限状态机处于状态s j 时如果输入事件i e i ，则 产生输出事件o e ( i ，j ) ，执行具体动作x ，有限状态机跳转到状态s k 。 使用状态转换图来表示有限状态机的动作更为直观。图3 1 0 中的圆圈表示状 念，状态之间的连线表示状态的变迁，在连线上标出此次变迁的输入事件、输出 事件和相关的具体动作。 i a j o a x 图3 - 1 0 状态转换图 使用事件状态表和状态转换图可以较全面而直观地描述和模拟通信系统协议 实体的动作，因而被广泛用于通信协议的设计与验证中。但是这些直观的工具难 于操作，下面给出有限状态机的形式化描述。 3 3 2 有限状态机的形式化描述 结合通信系统的实际，有限状态机可以定义为一个五元组m = ( i ，o ，s ，d ， l ) ，其意义如下： i ，输入集合，包括请求f 响应服务原语，协议用户发送的抽象服务原语( a s p ) 以 及从对等层来的p d u 。 o ，输出集合，包括指示，证实服务原语，送往协议用户的抽象服务原语( a s p ) 以及送往对等层的p d u 。 s ，有限非空的状态集合，包括有限状态机可能达到的所有状态。在接收任何输入 以前，有限状态机处于初始状态s s ；s 的一个子集f s 包含了有限状态机停止时 所处的所有可能状态，即终止状态。 d ，状态转换函数，定义为d ：i s s 。 l ，输出函数，定义为l ：i s o 。 有限状态机从初始状态s 开始运行，每一次状态变迁都对应其状态转换函数和 输出函数的一次执行，最终，有限状态机停止于f 中的一个最终状念上。 3 3 3 扩展的有限状态机 使用上述的有限状态机不能方便地处理变量和变量值的传送，因为系统中的 状态数目会随着系统复杂度的升高而急剧上升，可能会产生状态爆炸的问题。为 了弥补有限状态机的这个缺陷，对其进行如下修改非常有必要：引入变量的概念， 变量具有自己的符号名，可以取允许的任何具体的值，但只有最后一次所赋的值 才能被取出来；使有限状态机能够传送变量的值，即输入和输出不仅仅是符号名， 还带有具体的参数值；另外一个修改是引入一系列算术和逻辑符号来操作变量。 一个扩展的有限状态机可以定义为一个六元组m = ( i ，o ，s ，a ，d ，l ) ，其 中i 、o 、s 的定义同上，a 是变量的集合，d 和l 在应用时要根据变