（计算机应用技术专业论文）无线传感网络节点编程语言设计与实现.pdf

浙江大学硕i 学位论文 摘要 摘要 无线传感网络是指由无线传感网络节点通过无线通信组成的网络。无线传感 网络技术在最近十年来得到了飞速的发展，开始从学术界研究走向商业应用。然 而硬件技术的进步并不会使无线传感网络节点的资源受限特性得到改观：技术进 步使得无线传感网络节点价格下降却不会给能量容量带来提升。在内存和能量限 制下编写节点应用，使得应用满足灵活并发性和交互性，并且适应传感器种类繁 多和不断更新的硬件具有很大的困难。随着应用的越来越广泛，如何提供良好的 节点应用程序编程语言和编程模型以构建安全可靠易维护的应用程序是迫切需 要解决的问题。 当前的节点编程语言主要是c 语言和n 鹤c 语言。c 语言是非常流行的通用 编程语言，但是缺乏针对重用性和安全性的支持，n e s c 提供了基于组件的封装 以及任务和事件驱动编程模型，但是具有灵活性低、静态组件、学习曲线较大等 缺点。由于节点上资源极其受限，现代面向对象语言由于代价太大而无法适用于 节点编程 论文在分析主流无线传感网络节点编程语言和编程模型的基础上，对节点的 编程难点进行了研究，提出了一种专门针对无线传感网络节点编程的新型语言 c s p i r e 。在寻求节点编程对封装性、可靠性、易用性和性能上的需求的解决方案 上，c s p i r e 主要借鉴了面向对象的方法和当前高级语言语法，提供了具有面向对 象特性的、支持事件订阅机制的基本语法，并通过程序优化和限制性的面向对象 特性来保证目标程序的效率，编译期间对数据竞争的检测增加了目标程序的安全 性。 论文的工作可以归纳为：首先，分析了节点编程困难，在不失效率的基础上 引用了面向对象方法，设计了c s p i r e 语言；其次，通过对数据竞争的检测提高 了节点程序可靠性；最后，设计实现了c s p i r e 语言编译器，使用全局分析的方 法优化提升效率并生成目标代码 关键词：无线传感网络节点编程语言编程模型数据竞争分析编译器 浙江大学硕j ：学位论文 a b s t r a c t w i r e l e s s 鸵- f l s o rn e t w o r k sa l en e t w o r k so fc o m p a c tm i c r os e n s o r sw i t hw i r e l e s s c o m m u n i c a t i o nc a p a b i l i t y w i r e l e s ss 0 1 o rn e t w o r kt e c h n o l o g yh a sb e e nd e v e l o p e d r a p i d l yi nt h ep a s td e c a d e n o to n l yf o ra c a d e m i cr e s e a r c h , b u ta l s ow s n h a sb e a n u s e di nc o m m e r c i a la p p l i c a t i o n s h o w e v e r , t h et e c h n o l o g i c a lp r o g r e s sh a sn o tb e e n c h a n g e ds e n s o rn o d e sr e s o u r c e - c u n s t r a i n e dc h a r a c t e r i s t i c s ：p r o g r e s sm a k e ss a 眦埘 l o w e rp r i c eb u tw i l ln o tb r o u g h tm e m o r ya n de n e r g yc a p a c i t yu p g r a d e m e m o r ya n d e n e r g yc o n s t r a i n t sm a k e sb u i l d i n gc r o s sp l a t f o r mn o d ea p p l i c a t i o n sm o r ed i f f i c u l t , e s p e c i a l l yt h eh a r d w a mc o n s t a n t l yu p d a t e d w h i l et h ei n c r e a s i n g l yw s na p p l i c a t i o n s n e e d e d , h o wt op r o v i d eg o o dp r o g r a m m i n gl a n g u a g ea n dp r o g r a m m i n gm o d e lt o b u i l ds a f e , r e l i a b l ea n de a s yt om a i n t a i na p p l i c a t i o ni sa u r g e n tp r o b l e mt or e s o l v e t o d a y , m o s tu s e dn o d ep r o g r a m m i n gl a n g u a g ei st h ecl a n g u a g ea n dn e s c l a n g u a g e cp r o g r a m m i n gl a n g u a g ei sav e r yp o p u l a rg e n e r a ll a n g u a g e , b u td o e sn o t s u p p o r tt ob u i l ds a f ea n dr e u s a b l ea p p l i c a t i o n s n e s ce x p o s e sap r o g r a m m i n gm o d e l t h a ti n c o r p o r a t e se v e n t - d r i v e ne x e c u t i o n , a n dc o m p o n e n t - o r i e n t e da p p l i c a t i o nd e s i g n b u tn e s cd o e sn o ts u p p o r ti n s t a n c e sw i t hp r i v a t es t a t e s , a n dd i f f i c u l tt ou s ew i t ht h e a hh o cg r a m m a r s i n c en o d e se x t r e m e l yl i m i t e d “踟u r c 铭m o d e r no b j e c t - o r i e n t e d p r o g r a m m i n gi s n o ta p p l i c a b l ed u et o t h ec o s t a f t e ra n a l y s i so ft h em a i nn o d e p r o g r a m m i n gl a n g u a g e ，p r o g r a m m i n gm o d e l ，a n dp r o g r a m m i n gd i f f i c u l tf o ran o d e , t h i st h e s i sp r o p o s e sas p e c i f i cn e wp r o g r a m m i n gl a n g u a g ec s p i r e w h i l et r yt o p r o v i d ee n c a p s u l a t e , r e l i a b l e , e a s yt ou s ea n de f f i c i e n tl a n g u a g e , w er e f e rt ot h e o b j e c t - o r i e n t e dm e t h o da n dt h ec u r r e n th i g hl e v e ll a n g u a g eg r a m m a r c s p i r ep r o v i d e s ae f f i c i e n t0 0w a ya n dae v e n t - s u b s c r i b em e c h a n i s m c o m p i l e ro p t i m i z a t i o na n d r e s t r i c t i v eo b j e c t - o r i e n t e dc h a r a c t e r i s t i c se n s u r ee f f i c i e n c y d u r i n gt h ec o m p i l i n g , d a t ar a c ed e t e c ta n dm e m o r ya o c c s sc h e c kc o d ei n s e r tm a k ea p p l i c a t i o nm o r er e l i a b l e t h ec o n t r i b u t i o n so f t l l i st h e s i sc a nb e s u m m a r i z e da sf o l l o w s ：f i r s t l y , a n a l y s i so f t h en o d ep r o g r a m m i n gd i f f i c u l t i e s ，a n dp r o v i d eae f f i c i e n t0 0 p r o g r a m m i n gl a n g u a g e ； s e c o n d l y , d a t a “l c ed e t e c ti m p r o v et h er e l i a b i l i t yo fa p p l i c a t i o n s ；f i n a i l gd e v e l o p e da c o m p i l e rf o rc s p i r e , w i t c ho p t i m i z et h ee f f i c i e n c ya n dg e n e r a t et h et a r g e tc o d e k e y w o r d s ：w i r e l e s s s e n s o rn e t w o r k n o d e s ，p r o g r a m m i n gl a n g u a g e , p r o g r a m m i n gm o d e l ，d a t ar a c ed e t e c t , c o m p i l e r 浙江大学硕l 学位论文 图目录 图目录 图2 - 1t i n y o s 应用程序执行模型5 图2 2 n e s c 例子7 图2 - 3s o s 体系结构 图2 - 4s o s 中的消息机制 9 图2 5 模块之日j 消息传递9 图2 - 6 状态机模型1l 图2 7 0 s m 代码例子 图3 - 1c s p i r e 语言 图3 2c s p i r e 编译器编译流程1 5 图3 3 基于对象的封装1 7 图3 4 接口实现结构1 9 图3 5 通过不同实现和接口绑定实现逻辑控制流程的重用2 l 图3 6 对比柱状图 图3 7 事件事件处理例程2 4 图3 8 事件的触发和处理2 5 图3 - 9 事件响应例程函数列表2 6 图3 1 0s e n t h r e a d 构架 ：1 9 图4 - l 后台事件驱动系统3 2 图4 2 前台任务调度 3 3 图5 1 编译器功能。3 6 图5 - 2 编译器编译流程3 7 图5 3c s p i r e 编译器框架生成3 9 图5 4 语法树举例3 9 图5 5 符号表和类型系统4 0 图5 - 6 任务集遍历示例4 l 图6 1e w m a 例子4 2 v 浙江大学硕士学位论文表日录 表目录 表6 1 节点编程语言比较 表6 - 2 c s p i r e 和c 语言代码大小比较 表6 - 4 运行时b j 比较 v l 4 ：! 4 2 浙江人学硕i ：学位论文 第1 章绪论 1 1 研究背景 第1 章绪论 无线传感网络1 ( w i r e l e s ss e n s o r n e t w o r k , w s n ) 是指由大量传感节点通过 无线通信、以自组织方式构建的网络，其目的是协同地感知、采集和处理网络覆 盖区域中感知对象的信息，并最终传输到观察者。无线传感网络综合了传感器技 术、嵌入式计算技术和无线网络通信技术，在军事监控、工业过程控制、环境检 测、医疗监控和智能家居等方面具有广泛的应用前景，目前已引起国内外广泛的 关注和研究。 无线传感网络节点通常由低能耗微控制器、供能装置、无线通信板和传感器 四大部分组成无线传感网络节点一般独立工作在无人照看区域，和普通嵌入式 设备相比，无线传感网络节点硬件极其受限。例如，数掘带宽更小，只有8 位， 处理能力更弱，通常只有4 - - 8 m h z 无线传感网络节点微控制器采用h a r v a r d 体 系，即使用两个独立的存储器模块，分别存储指令和数据。一般来说，指令存储 在非易失性构件f l a s h 上，f l a s h 大小根据硬件平台的不同差异很大，大部分在8 k b 到5 1 2 k b 之间；运行时数据存储在易失性内存s r a m 上。由于s r a m 的能耗更 大，价格更高，因此无线传感网络节点上的s r a m 通常很小，一般为0 5 k b 到 6 4 k b 之间。无线传感网络节点使用电池供电，一般电池能量密度为1 5 0 0 j c m 3 到4 0 0 0 j c m 3 ，电池技术并不按照m o o r e 定律发展，其年增长率仅为3 。传感 器( 以及激活器) 是传感节点是发展最不成熟、最不稳定的技术之一传感器种 类繁多，应用也有很大差异，因此很难将所有的传感器归为一类。总的来说，无 线传感网络节点的硬件具有资源极其受限和多样性的特点。 无线传感网络节点应用程序也具有不同于传统应用程序的特点。无线传感网 络节点通常由环境驱动，如数据搜集、本地环境控制等应用，环境并发的产生诸 多触发事件，这就需要有事件驱动机制和并发控制。无线传感网络节点通常需要 在无人照看区域持续运行几个星期甚至几个月，所以节点操作系统和应用程序的 开发的一个重要目标是减少运行时错误，需要具有较高的可靠性。无线传感网络 节点由于和环境交互，对实时性也有较高要求，如不能及时对环境进行响应，将 造成数据丢失等不同程度的后果。 无线传感网络节点硬件特点和应用本身的各种额外的需求给编写节点应用 造成了很大的挑战，节点操作系统提供高效灵活、可靠易用的应用程序编写环境 和编程模型，不同于传统嵌入式操作系统成熟的研究和应用，无线传感网络节点 操作系统仍是当前的研究热点。早期节点操作系统和节点应用通常采用汇编语言 浙江大学硕十学位论文 第l 章绪论 和c 语言编写，然而c 语言并不能有效的和方便的形式支持面向无线传感网络 节点的操作系统和应用开发。因此，设计专门针对无线传感网络节点软硬件特点 的编程语言将大大降低编写节点应用的难度。目前国内外对节点操作系统和节点 编程语言以及基于这两者的编程模型都有深入和广泛的研究。 其中影响最广的节点操作系统和节点编程语言是u cb e r k e l e y 设计和开发的 t i n y o s 和n e s c 语言n e s c 语言反映了t i n y o s 的设计和在其之上的应用编程 模型。n e s c 语言的主要贡献有1 ) 提出了支持事件驱动系统的组件模型；2 ) 通 过额外的编译分析实现了简单但有效的并发模型。瑞士计算机科学研究所 ( s w e d i s hi n s t i t u t eo fc o m p m 茁s c i e n c e ) 研究开发了c o n t i k i 节点操作系统， c o n t i k i 2 ，3 】主要的贡献是实现了平台无关的动态加载技术，使得c o n t i k i 可运行 时替换应用程序和服务而不需要每次更新整个系统，节省了因程序更新而造成的 通讯的能量消耗，同时c o n t i k i 提出了p r o t o t h r e a d 4 并发模型，减少了基于事件 驱动编程而产生的状态数，同时只需要很小的代价。由加晕福利亚大学开发的 s o s 5 1 ，于2 0 0 4 年发布第一个版本，s o s 提出了可动态加载模块概念和一套消 息机制。美国科罗拉多州( c o l o r a d o ) 大学研发的m a n t i s o s ，m a n t i s o s 6 ，7 】使 用少量的代价实现了轻量级多线程库，同时具有动念重编程和跨平台等特性，极 大地方便了编程。除了这几个主要的无线传感网络节点操作系统实现外，还有关 于致力于解决上述问题的各种研究，例如o l i v e rk a s t e n 提出的基于对象状态机 模型的o s m 语言，通过状态机来解决事件驱动编程所面临的1 ) 事件和动作静 态关联，程序不能根据当前状态来改变关联关系；2 ) 程序被打断成很多片断， 缺乏有效的共享信息机制；两大问题。 本文主要针对节点编程的特点，结合节点操作系统的设计开发，设计出符合 节点软件开发的编程语言，降低开发难度，减少程序错误。 1 2 研究内容和意义 从上一节我们知道，无线传感网络具有非常广泛的应用背景，并且正处在不 断发展中，新的应用不断出现，已有的应用不断改善。但是无线传感网络节点的 硬件特点和特殊的软件需求的矛盾给应用程序开发带来很大的障碍。如何提供一 个良好的节点应用程序开发环境已经成为学术界的热点研究对象 作为程序员的表达工具，编程语言的好坏对开发具有重要的影响。语言可以 将经常性的任务自动化。可维护性、可扩展性、可移植性，都依赖于程序内部结 构。编程语言可以增强程序的内部结构亦或使之模糊混乱。编程语言有助于代码 分析。一个好的编程语言可以简化复杂程序的编写，一方面提高编程效率，另一 方面提高代码本身的质量。一种编程语言对于开发人员特别是节点程序开发人员 有着重要的意义。 2 浙江人学硕i 学位论文 第l 章绪论 本文从设计和实现一种无线传感网络节点编程语言的角度入手，深入分析节 点编程特点和编程模型，通过加强已有语言的抽象能力来增强语言的表达能力。 提高抽象层次往往带来性能上的损失，因此我们需要在性能上的损失和抽象层次 上找到一个平衡点，同时寻求优化等弥补损失的措施。目前节点编程语言中较有 影响力的主要是n e s c 语言。n e s c 通过特殊的静态语法和编译器优化来降低效率 损失至最低点但是这种静态语法却提高了n e s c 语言的使用门槛，使得n e s c 的使用范围很大程度上仅限于研究人员使用，较难普及到普通应用程序和硬件驱 动开发人员本文在其基础上，照顾到广大普通编程人员的编程习惯，在加强抽 象能力的基础上，通过限制表达能力和编译器优化来保证目标程序的效率。另外， 配合具有自主产权的新型节点操作系统的开发，语言的设计支持新节点操作系统 下节点硬件驱动和节点应用程序编程模型，给开发人员提供一个良好的开发环 境。 论文主要分析主流无线传感网络节点编程语言和编程模型，对节点的编程难 点进行了研究，提出了一种专门针对无线传感网络节点编程的新型语占c s p i r e 。 在寻求节点编程对封装性、可靠性、易用性和性能上的需求的解决方案上，c s p i r e 主要借鉴了面向对象的方法和当前高级语言语法和n e s c 、o s m 等语言的实现思 想，提出了具有面向对象特性的、支持事件订阅机制的基本语法，并通过程序优 化和限制性的面向对象特性来保证目标程序的效率，编译期间对数据竞争的检测 增加了目标程序的安全性。 1 3 文章结构 论文主要专注于设计一种更加容易学习和使用的，符合无线传感网络软件设 计开发特点的特定语言。在语法支持和语义上详细描述了该语言，针对这些语法 和语义实现了具有可移植性的、易维护的语言编译器和一个适用于无线传感网路 节点软件开发的开发环境。下面是论文的主要结构，主要分为两大部分： 第一、二章为论文的第一部分，这一部分主要讨论了无线传感网路节点硬件 和应用的特点，和对语言设计的要求和挑战，分析了现有的无线传感网上的编程 语言、各个操作系统和编程模型，交代了技术背景。第二章详细地分析了该领域 主要的语言和编程模型，并列举了这些语言和模型的优缺点，为下一部分做好铺 垫。 第三、四、五章为第二部分，第三章对新型语言c s p i r e 做了简单介绍。第 四章详细论述了c s p i r e 的语法的设计和实现第五章讨论了c s p i r e 语言中的并 发性和数据竞争的检测。第六章和第七章分别讨论了编译器的实现和c s p i r e 语 言的应用。 最后一章概览全文，指出下一步工作。 3 浙江大学硕上学位论文 第2 章编程语言相关背景概述 第2 章编程语言相关背景概述 2 1 传统主流编程语言 2 1 1c 语言 除了t m y o s 设计并使用n e s c 语言外，其他的无线传感网络节点操作系统都 使用c 语言来做开发，c 语言最初是由贝尔实验室在b 语言的基础上设计出来 的一种语言，从k & r 出版c 编程语言开始成为了世界上最流行的语言之一。 c 语言 9 】具有如下优点：1 和硬件结合紧密，灵活方便，程序自由度大；2 编译目标程序效率高，堪比直接由汇编编写的程序；3 可移植性好基于上述优 点，c 语言是既提供了低层程序开发又使目标程序具有可移植性的语言中最杰出 的代表【l o 】。c 语占成为了最流行的编程语言之一，特别是在嵌入式开发中，面 对不同的硬件都有相应的编译器后端支持，c 语言被广泛采用。 但是与此同时，c 语言也暴露出一系列问题。首先，c 语言在语言层面上不 支持对象或组件的封装，在无线传感网络节点硬件种类繁多、平台相关实现的千 差万别的情况下，增加了开发者开发出维护性和可移植性良好的操作系统或应用 程序的难度；其次，c 语言在提供指针直接访问内存的同时不具备访问的控制， 造成程序数据竞争、操作系统( 程序) 崩溃等等。因此，使用c 语言做无线传 感网络节点操作系统和应用的开发具有较大障碍。 2 1 2 高级面向对象编程语言 随着计算机技术的发展，应用不断复杂，规模不断加大，这些都对软件工程 带来巨大的挑战。为了解决这一系列问题，语言设计人员设计出了面向对象的语 言，使得在语言级别上能方便的进行数据和行为的抽象、封装、动态行为绑定、 代码重用等，在一定程度上缓解了问题。面向对象语言支持使开发大型复杂系统 变的容易，代码更可靠，系统的维护和更新也变得更为自然。目前流行的高级面 向对象编程语言主要有c + + 【l l 】、j a v a 1 2 、c # 1 3 1 、p y t h o n 1 4 和r u b y 1 5 等。 但是，在高级语言在效率和目标程序大小上明显弱于c 等接近硬件的低级语 言。以上面所述流行的面向对象编程语言中效率较高的c + + 为例，虽然具有面向 嵌入式领域的版本e m b e d d e dc + + 【1 6 】，但是一些特性如继承、异常、模板、r t t i 、 动态内存分配都显著的增加了应用程序大小和运行时代价，这使得在内存和能量 浙江人学硕十学位论文 第2 章编程语言相关背景概述 都极度受限的无线传感网络节点上面使用高级语言变的不可能。 虽然在节点编程中不可能直接使用高级面向对象语言，但是使用面向对象设 计提高程序可维护性、可扩展性、可移植性的方法在节点编程中仍值得借鉴【1 7 】。 例如n 姻c 中的组件相当于静态类( 所有成员均为静态成员) ，o s m 把状态作为 对象柬建立模型。 2 2 当前节点编程语言和编程模型 2 2 1t i n y o s 和n e s c 编程语言 t i n y o s 是由u cb e r k e l e y 开发的专门用于研究无限传感网络及其应用的节 点操作系统。t i n y o s 采用为事件驱动应用程序定制的编程模型，具有非常小的 内存占用。n e s c 编程语言是专门针对t m y o s 采用的编程模型而设计的。t i n y o s 使用n c s c 重写。t i n y o s 对n e s c 的设计产生影响的特点主要有：基于组件的体 系；事件驱动并发模型；两层执行结构等 a t i n y o s 编程模型 t m y o s 采用双层调度模型，为了减少r a i n 上和能量上的开销，t i n y o s 只维 护一个f i f o 的无抢占队列，底层产生事件，事件可以关联到应用上层的函数实 现，然后在事件中把长任务p o s t 到内核任务队列中延后执行。其流程如下图所 示。 逐个执行、 田2 - 1t m y o s 应用程序执行模型 t m y o s 的设计基于三个编程结构：命令( c o m m a n d ) 、事件( e v e n t ) 和任务 ( t a s k ) 命令相当于普通函数调用，一般用于服务请求并且马上被执行。命令 5 浙江人学硕上学位论文 第2 章编程语言相关背景概述 可以投递一个任务延后执行事件在命令执行完毕或硬件事件( 如中断) 产生时 唤醒，事件可以存放组件变量、投递任务、唤醒更高层的事件或调用命令。任务 被设计成延迟执行的函数调用，他们互相原子执行不能互相抢占但是可以被中断 抢占( 投递新的任务) ，为了有低执行延迟时日j ，每一个任务必须尽可能的短小。 任务在处理器空闲时以先进先出的顺序被执行 t m y o s 一次仅执行一个任务。它的并发模型表现在他有两个“执行”线程， 一个是任务，另一个是硬件事件中断处理程序。任务是被延期执行的函数，它们 一旦被调度，就会一直运行到结束，并且任务之间不会被抢占。硬件中断处理函 数是用来相应和处理硬件中断的，它们可以抢占任务或其他硬件中断处理函数。 由于任务和硬件中断处理程序可能被其他异步代码所抢占，所以需要处理特定的 数掘竞争。处理竞争的方法一般是使用排他性的访问共享数据，n e s c 编译器在 编译时蒯静态分析潜在的数据竞争。 b n e s c 编程语言及编译器 由于c 语言并不能以有效的和方便的形式支持面向无线传感网络节点的操 作系统和应用开发，因此t m y o s 丌发人员把c 语言进行了一定的扩展，提出了 基于组件化编程的n e s c 语言，同时结合了事件驱动编程模型和t m y o s 的并发 模型，提高了操作系统和应用开发的方便性和应用执行的可靠性，n e s c 有如下 特点： 1 ) n e s c 语言被设计为c 语言的一种扩展。主要基于一下理由：i ) c 语言为 各种可能作为无线传感网络节点的目杯微控制器提供了高效的代码，i i ) c 非常 适合于底层访问硬件的操作，i i i ) 使用n e s c 编写的程序也更容易使用已有的使 用c 语言编写的代码。 2 ) 语言层次上的静态化，无动态内存空间分配，所有调用关系在执行前静 态确定。使用这种方法简化了程序的正确性分析和优化，包括内联化函数调用和 数据竞争分析。另一方面，这种方式把动态内存分配和动态化执行流程需求的实 现负担扔给了程序员，造成了程序难以编写和理解。 3 ) 程序和操作系统结合在一起，不支持分开编译。整体分析使全局安全性 和优化变得更为容易，然而这种方式使得无限传感网络节点应用的更新必须整个 连同操作系统一起更新，或者在原操作系统之上开发虚拟机，如基于t m y o s 的 虚拟机m a t e 1 8 ，前者造成了能量的浪费( 无限传感网络中通讯消耗大量能量) ， 后者造成执行效率的下降。 4 ) 在语言级别上对t i n y o s 编程模型进行支持，支持组件模型，双向的接口 方式。在n e s c 中，组件包括配件和模块，配件描述不同组件接口之间的关系， 组件提供的接口中的函数功能在模块中描述其实现过程，组件的接口是实现组件 之间联系的通道，如果组件实现的函数没有在它的接口中说明，就不能被其他组 6 浙江人学硕p 学位论文第2 章编程语苦相关背景概述 件使用。如下图中描述了配件t i m e c 的代码和功能图。其中“- ”表示左边的 组件接口要调用位于“”右边的组件接口，即绑定( w i r e d ) 。如图定义了t i m c r c 提供的s t d c o n t r o l 和t i m e r 接口为模块t i m 盯m 提供的接口，把t i m e r m 的c l k 绑定到h w c l o c k 的c l o c k 接口。 s t d c o n t r o lt i m e rl 1 i l , s t d c o n t r o lt i m e r t i m e r m f 娶 c o n f i g u r a t i o nt i m e r cf p r o v i d e s i n t e r f a c es t d c o n t r o l ； i n t e r f a c et i m e r ： l i m p l e m e n t a t i o ni c o m p o n e n t st i m e r m ，h w c l o c k ； s t d c o n t r o l = t i m e r m s t d c o n t r o l j t i m e r = t i m e r m t i m e r ； t i m e r m c 1k - h w c l o c k c l o c k ； n e s c 代码段 使用n e s c 编写的t i m e r c 配件 田2 - 2 n e s c 例子 n c s c 中的双向接口由关键字c o r m n a n d 和e v e n t 来定义。c o n u n a n d 由上层往 下调用时使用，e v e n t 由下往上调用时使用。其中无论是c o n u n a n d 还是e v e n t 都 是静态绑定的，即绑定关系在编译分析时就确定。 n c s c 的编译器是n c c ，n c c 的工作有：把n c s c 程序翻译成g c c 接受的c 程序， 数据竞争分析和部分优化工作。 c n e s c 的优势和局限性 n c s c 有如下优势： 基于组件的封装。组件的提出相对于c 语言大大的提高了封装性 支持简单的并发模型。n e s c 提出了a s y n c 语义。任务之间不可抢占，中断事 件抢占任务，为异步( a s y n c ) 代码段。 静态语言有利于编译器分析和优化。n e s c 是完全静态语言，没有函数指针 和动态内存分配，有利于编译器分析提高目标代码的效率。 n e s c 由于t m y o s 的广泛应用而被广泛采用，然而虽然n e s c 提供了基于组 件的封装方式，使程序的模块化，提高了程序的可读性和可维护性，但是n e s c 的基于组件的方式只静态的封装了唯一的一个对象，而不是封装一组对象作为一 种类型，因此，在n e s c 中，程序员不能像传统面向对象语言一样定义多个实例 7 浙江大学硕t 学位论文第2 章编程语言相关背景概述 【1 9 】，只能通过不同的参数化来区别不同的个体。n v s c 语言组件中的变量被翻译 成全局变量，应用程序很难对共用模型进行重用，只能把寻找相应的解决方法的 包袱扔给程序员。 在无线传感网络中应用程序本身通常具有事件驱动状态转移的特性。n e s c 语言对事件的和动作的关联并不灵活。n e s c 编译器通过对代码全局分析对事件 进行静态绑定。程序员无法以灵活的方式动态订阅事件和取消订阅事件。 n e s c 语言本身融合了编程语言和描述语言，和传统编程语占有较大差异， 同时又不是完全的描述语言，使得n e s c 语占不易上手，学习曲线较大。 没有动态内存，仅依赖全局静态变量。虽然取消了动态内存分配和释放减少 了内存管理的开销，但是却把负担转移到程序员身上，程序员必须设计程序来应 对不定内存寻求情况下的解决方式。 没有对事件驱动编程模型有任何改善的措施，应用程序被打断成多个片段， 状态的维护和判断完全依靠程序员。 包管理机制不够完善。可能会有名字冲突。 2 2 2s o s 编程模型 s o s 是由加里福利亚大学开发的无线传感网络节点操作系统，s o s 由两部分 组成：可动态加载的模块和静态编译的内核组成。如下图所示： 圜图圈 内核服务( 调度器，动态内存管理) 设备驱动层( t i m e r 等) 硬件抽象层( a d c 、1 2 c 、c l o c k 等) 可动态加载模块 静态s o s 内核 圈2 - 3s o s 体系结构 s o s 主要贡献在于可动态加载模块的设计。在编程模型上，s o s 沿用t m y o s 的基于事件驱动的模型，使用前后台协助的方式。前台是中断调度、后台是以消 息方式实现的任务调度，s o s 中有两个不同优先级的f i f o 调度队列，任务队列 彼此之间以及队列内部都不可抢占，但高优先级的任务会先于低优先级的任务被 调度。只有前台的中断可以抢占任务在s o s 中的通信，包括应用程序之间， 应用和静态内核之间，主要采用消息传递方式来进行。 8 浙江大学硬i ：学位论文第2 章编程语言相关背景概述 a s o s 消息机制 s o s 采用c 进行编程，与t m y o s 使用n e s t 在语法上对事件关联进行支持 不同，s o s 采用消息派发来通知事件的触发，即在n e s t 中，事件直接对于到了 一个或一组函数调用，而在s o s 中，事件只是一个消息，消息被派发到感兴趣 的模块，感兴趣的模块根据消息的种类以及消息所携带的信息来做相关的工作。 相对与n e s c 中的事件关联来说，s o s 的消息有更好的灵活性 田2 - 4 $ o s 中的消息机制 s o s 的消息机制与s o s 的调度也息息相关，模块之间通过消息来进行通信， 同时s o s 内核也通过维护一个消息队列来对消息处理进行调度。s o s 中发向模 块都表明了目标模块和来源模块，以及相关的信息等。s o s 内核根据消息的内 容来判断调度优先级和选择相应模块来处理消息。模块之间的消息通信方式如下 图： 田2 5 模块之闻消恩传递 s o s 中除了使用消息通信外，还有间接函数调用。模块维护一个模块函数指 针表，模块之间通过模块函数指针表来间接函数调用。内核也维护了一个系统跳 转表，来提供模块对内核a p i 的访问。 b 8 0 8 消息机制的局限性 s o s 的模块之间消息机制虽然具有很高的灵活性但是却缺乏语言上的支持， 用户必须自己维护消息的格式、处理消息的格式等，而这些处理流程和传递调用 都是重复工作，不但加大了程序员的负担，而且容易出错。 9 浙江大学硕士学位论文第2 章编程语占相关背景概述 s o s 的消息传递都需要通过内核调度，s o s 的消息机制包括了底层中断事件 和模块服务请求。对于底层中断事件来说，因为一般需要一定的实时性，通过内 核调度消息机制虽然具有很好的灵活性但却并不适合。底层的消息容易被延后处 理，在无线传感网络节点应用上，比如环境信息监测等应用，如果没有及时相应 则通常会造成相关信息被丢弃。 2 2 3o s m 语言和状态机模型 o s m 2 0 是o b i o c ts t a t em o d e l 的简称，是苏黎世瑞士联邦理工大学( e t h z u r i c h ) 计算机学院针对当静节点开发使用的两大抽象方法：事件、线程的缺点 提出的基于有限状态机的另一种节点开发模型方法，并设计了相应的语言和编译 器。 传统的无线传感网络节点编程模型一般采用事件驱动编程模型，然而在实际 进行事件驱动编程的时候，存在如下问题：由于一个任务不能总是占用处理器， 任务必须是非阻塞的，因此在控制流中需要等待一个事件时，操作必须被打断 成两个部分：非阻塞的请求操作和异步请求完成事件。请求完成产生的事件触发 动作继续原有的操作。看似简单的事件操作可能引起非常复杂的情况，如一个动 作调用了一个非阻塞操作，该操作产生一个事件又引发另外一个动作。把一个概 念上完整的操作打断成几个不同的动作使得操作的流程和状态不清晰。由于在一 个函数中内部变量不能使作用域扩大到不同动作之间，程序员只能通过全局变量 或动态内存分配手动的维护操作的堆栈，而无论是通过全局变量或是动态内存分 配在无线传感网络节点受限资源环境下都不是很好的方法。另一方面，程序员必 须保证任意序列的事件都必须得到正确对应的动作。针对上述两大问题，设计了 基于有限状态机的o s m 语言 a o s m 语言 o s m 在语义和语言表现上都基于有限状态机模型。有限状态机有三大概念： 状态、事件和状态转移。一个有限状态机由一组状态和一组状态转移组成。状态 转移说明了状态机如何从一个状态转移到另外一个状态。每一个状态转移都关联 了特定的事件，状态在特定事件发生时触发相应的状态转移。状态机模型可以看 成是一个有向图，节点代表状态，边代表状态转移。o s m 对这些概念进行了抽 象，在语言中表达出来。通过显式的s t a t e 语法，使得事件和动作之间并不是静 态的关联，而是由当前程序状态和事件的相互作用共同决定的。状态内的变量使 得动作之间能方便地进行信息共享，从而使得特定功能的实现更加简单。另一方 面，状态内变量有特定的作用域( 状态内) ，因此在离开当前状态的时候可以释 放相应的内存空间。通过层次结构组合的状态机定义，o s m 支持模块化编程 并行的状态机的设计能处理来自独立源的事件一个状态机模型如下图所示 1 0 浙江人学硕 ：学位论文第2 章编程语言相关背景概述 掣啦 e o 。一 图2 - 6 状态机模型 在上图中，a 和c 分别是起始状态和终止状态，a 状态在事件e 发生时转移 到b 状态( 通过调用o u t a ( ) 和i n b ( ) ) ，b 状态在事件f 发生时b 状态转移到 终结状态c 。 0 s m 有以下特点： 状态模型状态模型是0 s g 的主要构成。0 s g 中状态的定义包括它的转 移的定义、动作的定义和内部变量。 变量的定义。在0 s m 中变量只能在状态内部定义。变量的定义域包括状 态中的所有动作。事件和变量作为动作的参数。状态之间的通信通过参 数或上一层共有的状态变量共享进行。 层次和并行模型。0 s g 支持层次化的状态模型和状态机模型。0 s m 也可以 定义并行的两个状态机来对于两个不同状态转移流程。 模块化。0 s g 把一组相关的状态集中在一起成为一个状态机，并在一个 状态机中能定义其他状态机，使得0 s m 编写的程序具有很好的模块化。 b o s m 编译器 与n e s c 编译器相同，o s m 编译器同样是把o s m 描述语言转换成c 语言， 这从另外一方面说明了c 语言在对于机器码执行效率和可移植性上的优势。然 而由于o s m 的描述性特性，o s m 并不是直接翻译成c 语言的。o s m 编译器首 先把o s m 语言装换成一种专门用于描述反应系统( r e a c t i v es y s t e m ) 的同步语言 e s t e r e i ，然后通过e s t e r e l 的编译器把中间态e s t e r e l 表述的程序编译成目标g e e 兼容的c 代码。 o s m 编译器根据状态机模型在编译过程中进行了优化。由于一个状态机在 某一个时刻只存在于一个状态，为了减少内存的消耗，o s m 编译器对状态内部 变量的内存分配和c 语言的内存分配进行了较好的对应。状态被对应成c 中结 构体，状态机中被对应成一个共享体，各种状态成为状态机共享体中不同成员。 例如o s m 代码： 兰! | 浙江大学硬l 二学位论文第2 章编程语言相关背景概述 攀霉翼篡瑟i 鬟篡翌薹薹三薹 被编译成： 打u c tp a r c dr ；u n i o nm a c h m c c i ? “噬”学“”v 一州螂# p 0 9 s t r u c ts t a t e c i i n tc ： i u n i o nm a c h i n e a b i r 耄 s t r u c ts t a t e a i n ta l ，a 2 ；) _ s