（计算机软件与理论专业论文）无线传感器网络中编译优化工具的研究及实现.pdf

浙江大学硕士学位论文 摘要 摘要 无线传感器网络具有广泛的应用前景，其中所使用的大量微型节点，处理能 力弱、内存空间十分有限、各种资源严重受限。与此同时，节点程序往往需要长 时间运行于各种不同环境中，对程序本身有较高的要求。相应的，在进行程序开 发时，相对于桌面平台以及传统的嵌入式平台，开发者需要特别关注程序的执行 效率、代码占用空间和内存使用等信息，保证资源的使用未超出系统的限制，往 往面临更多的困难。 本论文针对无线传感器网络中的微型节点上应用程序开发时的编译工具展 开研究，主要内容包括：首先，论文分析现有的节点编程语言及其编译系统，对 程序编译过程中的优化工具进行研究。在现有工作的基础上，基于无线传感器网 络微型操作系统s e n s p i r eo s ，结合节点自身独特的硬件特性和应用环境，设计新 型编程语言c s p i r e ，同时设计实现在该系统中针对c s p i r e 语言的编译系统，在完 成程序编译过程的同时，结合操作系统进行资源分配上的优化；然后，特别在程 序的堆栈使用分析方面进行展开，对针对可执行文件的静态分析方法进行分析和 总结，提出一般性的计算方法，并在此基础上在多平台和多系统以及精确性方面 进行扩展，提供额外的安全检查和系统优化；最后，将语言编译时所采用的优化 工具进行集成，整合进集成开发环境之中以方便使用。 关键词：无线传感器网络，节点编程语言，编译优化工具，堆栈使用分析 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k sh a v eas i g n i f i c a n tp o t e n t i a li nd i v e r s ea p p l i c a t i o n sb u t r a i s el o t so fd i f f i c u l t i e sf o ra p p l i c a t i o nd e v e l o p m e n t t h ed i f f i c u l t yi np r o g r a m m i n g s e n s o rn e t w o r k si sn o to n l yd u et oi t se x t r e m e l yc o n s t r a i n e dr e s o u r c e s ，s u c ha sl o w c o m p u t a t i o na b i l i t ya n ds m a l lm e m o r ys i z e ，b u ta l s ot h eh i g hr e l i a b l er e q u i r e m e n t f o r i t s l o n gr u n n i n g t i m ea n dr u n n i n ge n v i r o n m e n t c o m p a r i n gw i t ha p p l i c a t i o n d e v e l o p m e n tf o rn o r m a lp l a t f o r m ，t h ed e v e l o p e r ss h o u l dc a r em o r e a b o u tt h er u n n i n g t i m eo rt h er a ma n dr o mu s a g eo fa p p l i c a t i o n sf o rs e n s o rn o d e s ，a n dm e e tk i n d s o f d i f f i c u l t i e s t h er e s e a r c hw o r ko ft h i st h e s i si sc o n c e n t r a t e do nt h ec o m p i l i n g t o o l so fs e n s o r n o d ea p p l i c a t i o nd e v e l o p m e n t t h ec o n t r i b u t i o n sc a nb es u m m a r i z e da sf o l l o w s ：f i r s t l y , d e s i g nt h en e wp r o g r a m m i n gl a n g u a g ec s p i r ea n d i t sb u i l d i n gs y s t e ma f t e ra n a l y s i s c u r r e n ts e n s o rn o d ep r o g r a m m i n gl a n g u a g e sa n dt h e i rb u i l ds y s t e m s t h ec s p i r e a d p l i c a t i o ni sa l s oo p t i m i z e df o ri t sr e s o u r c ea l l o c a t i o n s e c o n d l y b a s e do ns o m es t a t i c s t a c ka n a l y s i sm e t h o do fe x c i t a b l ef i l e ，p o i n to u tac o m m o na n a l y s i sp r o c e s sa n d e x t e n dt h em e t h o dt od i f f e r e n tp l a t f o r m sa n ds y s t e m sa n di m p r o v ei t sa c c u r a c y a n d f i n a l l y ，i n t e g r a t et h eb u i l ds y s t e ma n dc o m p i l i n go p t i m i z a t i o nt o o l s t os e n s p i r ei d e k e y w o r d s ： w i r e l e s ss e n s o rn e t w o r k s ，n o d ep r o g r a m m i n gl a n g u a g e ，c o m p i l i n g o p t i m i z a t i o nt o o l s ，s t a c ke s t i m a t i o n l i 浙江大学硕士学位论文 图目录 图目录 图2 1c 语言编译系统1 1 图2 2t i n y o s 系统中n e s c 编译流程1 2 图2 3m a t e 虚拟机编译执行系统13 图3 1c s p i r e 语言中的t a s k 结构。2 2 图3 2s e n s p i r eo s 编译系统总体框架2 4 图3 3c s p i r e 编译器实现框架2 6 图4 1 节点程序内存使用模型3 3 图4 2 程序堆栈最大使用状况3 6 图5 1s e n s p i r ei d e 代码编辑界面5 0 u 1 浙江大学硕士学位论文表目录 表目录 表2 1 常用微型传感器节点5 表3 1 语法分析器生成工具比较2 5 表3 2c s p i r e 系统类说明2 8 表3 3c s p i r e 与n e s c 代码行数比较3 0 表3 4c s p i r e 和n e s c 源代码大小比较3 0 表3 5 应用程序优化前后r a m 占用比较3l 表3 6 应用程序优化前后r o m 占用比较3l 表4 1o s c i l l o s c o p e 单个中断的堆栈分析结果4 5 表4 3 应用程序堆栈分析结果比较4 7 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构送交 本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以将学位 论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月 e t 签字日期：年月e t 浙江大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 随着网络技术和计算机技术的发展，无线传感器网络技术【1 】【2 】也得到极大的 发展并引起巨大的关注，成为近年来的研究热点之一。无线传感器网络不需要固 定网络支持，可以快速展开，易于在不同的环境中进行部署，在交通、环保、工 业、商业、军事等各个领域内都可以广泛应用。 无线传感器网络由具有计算、感知和无线通信能力的微型传感器通过自组织 的方式形成，这些传感器节点体积小、价格低廉，使用时采用电池供电，可以自 主工作。节点自身具有一定的计算能力，可以在采集传感数据后进行一般处理， 节点间通过无线模块进行相互的数据传输通讯。基于节点的数据采集、数据处理 和无线通讯，整个网络可以进行信息的获取与收集。实际使用中，传感器网络中 的节点种类繁多，应用类型也有较大的差异。典型的应用包括：监测，通过节点 持续采集周围的环境数据，如噪音、温度或光照等数据，然后定时将此类获取到 的信息发回基站；预警，在节点部署区域，检查周遭的环境参数，当监测指标超 出时进行报警，例如森林防火或有害气体的检查等。 在进行信息的获取与收集时，除了具有基本的数据传感功能以外，无线传感 器网络还具有一些特性使其对特殊环境可以更为适应。节点可以十分容易的部署 于各种特殊环境之中，同时无需统一的控制或用户的干预就可以自主工作，另外 还可以根据外界的环境变化而自行改变行为。对于具有一定规模并良好分布的网 络，即使某些节点发生异常无法工作，整个系统仍能够保证长期的正常运行。对 于无线传感器网络的应用，系统通常可以维持运行几十天甚至一年以上，在运行 期间，通过网络节点的重编程机制，节点还可以更新所执行的程序。 无线传感器网络在灵活应用的同时，也面临有一些重要的限制。首先不同于 通常的系统，由于成本的限制，系统中的节点作为一种简单的嵌入式设备，其自 身资源更为受刚3 1 ，主要表现在以下几方面：首先计算能力有限，大部分的传感 l 浙江大学硕士学位论文第l 章绪论 器节点选择结构简单、计算能力十分有限的m c u 作为主处理器，只能进行一般 的简单计算；其次存储空间十分有限，在传感器节点上，可编程f l a s h 和r a m 相 对于一般平台空间极小，可编程f l a s h 和r a m 与程序的运行紧密相关，前者一般 用来存放可执行程序的镜像，主要是代码部分，后者则供程序执行时堆栈、数据 变量等临时动态数据使用，有限的内存给程序的编写和运行都带来较多的限制。 总的来说，多样的无线传感网络节点在硬件方面在大多资源上都极其受限。 除了在硬件方面受到有限资源的限制以外，节点上所运行的程序在其功能需 求和运行环境上具有特殊性，使得在进行节点程序的开发时，具有更高的要求1 4 】。 在功能上，传感器节点上运行的应用程序功能上具有一定的复杂性，典型的传感 器程序在进行环境监控、数据收集时，需要负责包括数据的采集、处理、发送和 接收等功能。在程序运行环境方面，无线传感器网络中的节点大多部署在无人监 管的环境中，持续运行较长的时间【5 】，应用程序自身需要具有较高的稳定性和可 靠性。另外，因为节点运行环境特殊多变，其操作行为相对于一般的通用平台， 有更大的可能发生失败和错误，例如在数据发送接收时链路由于环境原因其状况 频繁改变而不可靠，节点本身由于能量不足等原因而运行出错，因而需要在程序 实现中加入更多的代码处理种种错误与异常，使得程序的实现逻辑更为复杂。 1 2 研究内容及意义 无线传感器网络具有广泛的应用前景，但是传感器节点本身资源的限制以及 节点程序自身功能和可靠性的要求，对传感器节点的应用程序开发提出了更高的 要求。受到节点硬件资源的限制，针对无线传感器网络的微型节点开发应用程序 时，相对于通用平台，开发者需要特别关注程序的执行效率、代码占用空间和内 存使用等信息，保证资源的使用未超出系统的限制，往往面临更多的困难。传统 的节点程序开发时，广泛使用c 语言结合少量的汇编语言，通过此种方式可以细 粒度的控制资源的使用，但同时也要求开发者具有相当的开发水平并对底层十分 熟悉，才可以十分有效的管理和使用各种有限的资源，实现系统的高效和稳定。 在这种情况下，目前有一些针对无线传感器网络微型节点编程语言，结合无线传 浙江大学硕上学位论文第l 章绪论 感器网络微型节点的自身特点，对编程语言进行改进，设计和提出更为适合节点 程序开发的编程方式。 在传统平台上进行程序开发时，在程序的编译过程中，往往有一些辅助工具 用以进行附加的安全检查或优化。对于资源有限并需要长期运行的节点系统而 言，在应用程序开发过程中，在编译阶段额外的安全检查和程序优化显得更为有 益。在编译过程中，通过研究和实现新的辅助工具，在编译过程中结合执行系统， 对程序进行检查和优化，将会给开发工作提供良好的帮助，有效的降低开发难度， 提高开发效率。目前，在节点程序的开发过程中，针对不同的编程语言，在语言 自身设计的同时，在语言编译过程中，针对程序自身的运行效率和资源使用的优 化，有一些研究工作，达到良好的效果。 本文针对微型传感器节点编程的特点，在现有工作的基础上，通过与节点操 作系统紧密结合，研究与实现适合节点程序开发的专用编程语言以及编译优化工 具，通过这些工作，方便节点程序的开发，降低开发难度，提高开发效率，提高 程序的安全性。基于无线传感器网络微型操作系统s e n s p i r eo s ，结合节点自身独 特的硬件特性和应用环境，设计新型编程语言c s p i r e ，同时在程序编译时，结合 系统进行优化处理。特别的，针对可执行程序的内存使用，对堆栈使用分析方法 进行研究，利用该研究结果，可以优化系统的资源分配。 1 3 论文组织结构 论文的主要内容在于针对无线传感器网络中的微型节点，研究和设计符合其 特点的编程语言，同时在语言编译系统中，通过进行应用程序的资源使用的静态 分析，特别是堆栈使用的分析，提供额外的安全检查和系统优化，从而简化节点 程序的开发过程。 论文后续章节的主要内容安排如下： 第2 章主要介绍目前在节点应用开发时所采用的各种主要语言及其编译系统 和系统中的辅助工具。在编译系统部分介绍了目前主要使用的编程语言或编程模 型，以及这些语言各自的编译过程；在辅助工具部分着重介绍了目前对应用程序 浙江大学硕士学位论文 第1 章绪论 进行堆栈使用分析时的各种工具或方法。 第3 章是在s e n s p i r eo s 中，针对应用程序开发所需的编译系统的总体研究， 具体包括c s p i r e 语言的设计和编译过程，以及在编译过程中根据语言和系统的特 点所进行的基本优化措施。 第4 章就节点程序编译中的内存使用优化进行展开，研究可执行程序的最大 堆栈使用的分析技术，在分析和总结一般计算方法的同时，在精确性和多平台及 多系统方面进行扩展。 第5 章的内容是关于s e n s p i r e 系统中应用程序开发平台，通过将上述的编译 系统和优化工具整合，同时结合代码编辑工具和仿真工具等其它辅助部分，综合 进行应用程序的开发。 第6 章是论文的最后一部分，通过对全文的内容进行概括总结，同时指出现 有工作的不足以及下一步可以继续完善之处。 4 浙江大学硕士学位论文第2 章编译系统及工具相关背景概述 第2 章编译系统及工具相关背景概述 2 1 节点编译系统概述 无线传感器网络具有极大的应用前景，是目前的研究热点之一。随着传感器 相关技术的发展，在微型的节点上，可以利用有限的能量，实现无线通讯和各种 环境数据的收集等功能。 表2 1 中是目前一些常用的微型传感器节点，节点采用的1 6 位m c u 主频为 几m h z ，r a m 为4 k b 1 0 k b ，可编程f l a s h 仅有几十到上百k b 。除了微型节点 以外，还有一些高性能的节点作为基站少量部署于网络之中，如s u ns p o t t 6 】和 i m o t e 等类型，采用a r m 处理器芯片，具有更大的r a m 和f l a s h 空间。对于大 规模的网络应用而言，成本等方面的限制，实际应用中更多采用m i c a z 和t e l o s b 7 1 等微型节点，进行实际部署并长期运行。 表2 1 常用微型传感器节点 节点m c ur a m 可编程f l a s h m i c a 2 a t m e g a l 2 8 l 4 k b1 2 8 k b m i c a z a t m e g a l 2 84 k b1 2 8 k b i i u s a t m e g a l 2 88 k b1 2 8 k b t e l o s bm s p 4 3 0l o k b4 8 k b 无线传感器网络可被看作是一种分布式系统，但和传统的分布式系统相比， 又具有一些显著的不同。资源受限是传感网络的一大特点，由于成本的限制，硬 件资源受限，与此同时能量也是重要的限制条件，目前的节点在实际应用时大多 使用电池进行供电，在有限的电量下，降低程序的能量消耗，保证程序更长时间 的运行，对节点程序开发来说十分重要。另外一方面，在节点间进行通信时，传 感网络节点间的链路更为不可靠，链路状况变化频繁，经常发生数据包的丢失等 情况。以上这些情况也决定了，在进行传感器节点的程序开发时，除了完成程序 浙江大学硕士学位论文第2 章编译系统及工具相关背景概述 的基本功能逻辑以外，需要更多的关注一些实现细节，包括实现中程序本身对资 源的有效使用，如低功耗的操作，有效的r a m 使用等，另外还有通信时的错误 处理，数据包的重发等行为。 总的来说，在无线传感器网络系统中，由于其自身的特点，造成在程序开发 时相对于一般系统，面临到许多不便之处。因而，在无线传感器网络研究领域内， 节点编程语言的研究是一个重要的研究内容。下面具体介绍目前在节点编程语言 方面的一些主要的研究状况。 2 1 1 节点编程语言 在进行无线传感器网络系统程序开发时，有多种不同类型的编程语言可供选 择使用。这些编程语言的总体设计目的是为了简化程序的开发过程，不同的语言， 或者通过提供对各种库的支持，或者通过与传感器网络操作系统相结合协同设 计，用以方便程序的编写。 目前在节点开发时所使用的编程语言，可以分为以下两类： 一类是原有的通用平台编程语言，例如目前节点程序开发时多直接使用c 语言进行程序编写，另外还有对一些通用平台的高级语言在语法上进行 简化，在节点上使用这些语言的简化版本开发程序，例如目前c + + 、j a v a 和b a s i c 都有一些尝试性的实现和使用。 另一类编程语言则是重新设计实现的节点专用编程语言。这类语言针对 节点程序的编程特点，借鉴通用语言的部分语法规则，同时加入一些新 的语法特性，进行重新的设计和实现。这类语言既有以节点为单位进行 程序设计，也有以整个网络为单位进行程序设计。针对单一节点的编程 语言，以节点为单位进行程序的设计，在程序设计时关注节点自身的硬 件特征，具体行为和操作，往往在应用程序编写好之后，将相同的可执 行文件通过基站分发到整个网络或者部分网络中去进行执行，针对单一 节点的设计语言可以更为灵活的进行节点的控制。而针对整个网络的编 程语言，则将整个网络视为一个应用进行程序设计开发，关注整个网络 的总体行为，关注节点间的彼此交互数据传输等行为。 6 浙江大学硕上学位论文第2 章编译系统及工具相关背景概述 下面具体介绍在无线传感器网络中进行节点编程时所可采用的各种语言。 通用平台编程语言 c 语言是目前整个嵌入式系统开发过程中使用最为广泛的编程语言，在无线 传感器网络系统中也不例外。通常微控制器程序的开发，面对多样的硬件平台， 多直接使用c 语言进行程序的编写。c 语言适合进行底层程序的开发，语言本身 具有良好的执行效率，编译工具较为成熟，针对不同的平台都有完善的编译工具 链。更为重要的，使用c 语言开发应用程序时，相对于其它编程语言，直接与底 层交互，可以更细粒度的控制和使用各种不同类型的底层资源，在资源十分有限 的平台下，更细粒度的操控各种紧缺资源，就意味着可以写出高效的代码对有限 的资源进行良好的管理和使用，提高整个系统的运行效率。但与此同时，这种细 粒度的操控一方面对开发者的开发水平有较高的要求，开发人员需要对底层十分 了解；另一方面也意味着程序开发过程中工作量的增加，面对节点硬件平台种类 繁多的情况，不同硬件平台下的实现操作也不尽相同，程序员在开发时，需要编 写大量的代码以保证系统的可维护性，同时由于运行环境特殊，节点程序在安全 性和稳定性方面有较高的要求，加之语言自身缺少相应的安全检查机制或者错误 恢复机制等，因而在实现时，在业务逻辑代码中，需要加入大量的代码进行错误 操作的检查处理等。因此，在使用c 语言进行无线传感网络节点的应用程序开发 时，虽然具有较高的运行效率和成熟的工具，但同时也具有相当的开发难度和工 作量，具有一定的挑战。 在编程语言的发展上，随着应用的复杂化和规模的扩大，对语言的设计带来 巨大的挑战【s 】。为了应对这一系列的问题，面向对象的编程方式被越来越多的采 用，在程序设计时，通过进行数据和行为的抽象、封装、动态行为绑定、代码重 用等，可以在一定程度对问题进行缓解，使得在复杂系统的开发时，在代码维护 方面有所改善。但是高级语言在执行效率和最终可执行程序的大小上相比于c 语 言等更与硬件更接近的语言相比还有较大的差距。以面向对象编程语言中效率较 高的c + + 为例，面向对象语言c + + 也可以直接在嵌入式系统中使用，节点开发所 使用的编译器如a v r - g c c 和m s p 4 3 0 g c c 也有对c + + 语言的支持，但是一方面这些 浙江大学硕士学位论文第2 章编译系统及工具相关背景概述 实现并不完整，另一方面更为重要的，由于节点本身资源的限制，c + + 复杂的对 象模型以及在运行时所需的额外开销，为其直接在节点上进行使用带来了许多的 不便；目前的无线传感器网络操作系统，也较多使用c 语言实现，并未考虑和 c + + 的结合。 在处理能力较强的传感器节点s u ns p o t 上，其上所运行的j a v a 虚拟机 s q u a w k 提供了对j a v a 语言的支持。 节点专用编程语言 除了以上那些通用平台下的编程语言以外，还有一些专为传感器节点而设计 的编程语言，目前针对传感器网络的专用编程语言，其设计目的多是为了简化节 点应用程序的开发和部署过程。这些专用语言在语法设计上，多借鉴了目前广泛 使用的通用语言的一些语法特性，同时还包括有事件驱动的编程方式【9 1 、结构化 查询以及函数式编程【1 0 】等。这些专用的编程语言同时针对传感器自身的特点加入 特殊的设计，其中使用最为广泛的是t i n y o s t 1 系统中所设计和应用的n e s c 1 2 1 语 l 口o t i n y o s 是一个专门用于无限传感网络及其应用的节点操作系统，是日前该领 域内使用最为广泛的操作系统之一。t i n y o s 系统使用n e s c 语言实现，基于模块 构建，采用事件驱动的编程模型，具有非常小的内存占用。n e s c 语言专为t i n y o s 设计，用于系统和应用的开发，以c 语言为基础设计，在语法上和c 语言具有一 定的类似性。n e s c 的应用由组件( c o m p o n e n t ) 构成，并分为两类：模块组件( m o d u l e c o m p o n e n t ) 和配置组件( c o n f i g u r a t i o nc o m p o n e n t ) ，模块组件用于实现程序的执 行逻辑，包括变量和函数的定义使用等内容，而配置组件则用来绑定不同的组件， 在组件之间通过接口进行连接，在组件内部，分别通过c o m m a n d 和e v e n t 调用上 层和下层模块。 n e s c 语言所采用模块化的设计，在程序编写时，不同层次的程序实现逻辑被 封装到不同的模块中，同时通过配置组件的使用，在编译时依据模块间的绑定信 息，选择使用相对应的模块，由此在编译期提供了足够的灵活性，同时，通过模 块化的封装，在不同的实现间提供统一的接口，保证了编程时只需要关注特定部 塑垩奎兰堡主堂垡堡兰笙! 里墨堡墨竺墨三墨塑茎堕墨堑垄 分的软件或硬件1 1 3 】【1 4 】。另外一方面，使用n e s c 语言进行程序开发，模块内部采 用和c 类似的语法保证了传统的嵌入式开发者比较容易实现程序的逻辑，可以灵 活调整和设置应用程序的各种参数，以此保证程序的低功耗和资源的高效使用。 t i n y o s 目前的使用十分广泛，功能丰富，在t i n y o s 系统中，使用n e s c 语 言可以更为方便的开发高效可靠的节点应用程序。但同时，在n e s c 的使用过程 中也同样存在有一些问题：首先，在应用程序实现时，模块间配置信息的描述显 著的增加了代码的编写量；其次，在n e s c 的处理过程中，应用程序代码和系统 代码在编译期一同处理和优化，生成单一的c 文件并进行静态链接，这样有利于 单个应用程序的优化，但造成编译后的程序各部分紧密耦合，给之后节点上代码 的更新或者维护带来不便；另外，基于事件的编程方式和n e s c 的模块绑定机制， 和通用平台下的传统编程语言相比还是有十分明显的不同，对于一般编程者而 言，具有一定的学习难度，带来一定的困难。 v i r g i l t ”】是一种针对资源受限系统而设计的轻量级的面向对象编程语言，该语 言的主要贡献在于语言所用的对象的内存分配进行优化，以适应节点上有限的内 存空间。 在节点系统中，另外一类重要的编程模型是在节点上运行虚拟机，然后在虚 拟机提供的执行环境中通过编写脚本指令完成实际的应用操作。和j a v a 虚拟机等 通常平台下的虚拟机技术不同，由于节点本身的限制，微型节点上的虚拟机所支 持的指令更为简单。 虚拟机技术在一般平台上因其所带来的平台无关性和不同系统间的隔离而 被广泛使用，而在传感网络中，则主要是由于其在可编程方面的优势而被采用。 通过在运行时可以方便的更新代码，此类编程方式在可执行代码的大小方面相对 于执行二进行代码具有明显的优势，因而在部署节点需要多次通过无线传输代 码，进行重编程时十分有效，但同时也带来了运行时的开销。除了可编程性以外， 虚拟机同时也提供了一种平台无关的执行环境，通过虚拟机提供的编程接口，可 以方便开发者针对多样的平台，编写简洁的代码。 m a t e ，【1 6 】是在t i n y o s 系统上实现的一种基于堆栈执行的虚拟机，针对特定的 9 浙江大学硕士学位论文第2 章编译系统及工具相关背景概述 应用环境，通过虚拟机提供少量的指令，利用这些指令实现程序逻辑，通过虚拟 机提供的接口可以使用传感器网络和外部f l a s h 等多种组件模块。m a t e 虚拟机中 提供了一种语法上与b a s i c 类似的语言t i n y s c r i p t 以供使用。m e l e t e l l 刀在m a t e 的 基础上进行扩展，可以支持多个程序并发执行，v m s t a 9 1 8 】贝u 可以允许虚拟机自身 像其上所运行的程序一样进行更新动态更新。 以上的编程语言都是针对单个节点进行应用程序的设计，程序实现上更为关 注节点自身的行为。另外还有一类编程语言以整个网络为单位进行程序设计【1 9 】， 这类更为高层的编程语言，将整个网络进行抽象，程序设计开发时针对于多个节 点或者整个网络进行。例如c o u g a r f 2 0 1 、t i n y d b l 2 1 1 和s i n a l 2 2 】中将网络应用视为一 个数据库进行程序设计，采用类似于s q l 语句类型的语法，以数据查询的方式获 取数据。c o u g a r 中将查询操作在节点中执行，以减少数据的传输量。t i n y d b 中 关注于底层数据采样和发送的处理，同时对查询命令和查询结果的传输路由树进 行优化。s i n a 则在语法上进行改进，通过在s q l 语句中嵌入脚本，采用混合的 编程方式，从而可以执行更为复杂的任务。 2 1 2 语言编译系统 以上的各种编程语言，都需要通过其各自的语言编译系统，从源代码生成最 终的可执行文件，在节点上运行。在不同语言的编译处理过程中，c 语言的编译 系统、n e s c 编译系统以及m a t e 虚拟机的编译系统最为典型。下面就这三类进行 具体的介绍。 2 1 2 1c 语言编译系统 c 语言是最基本的节点程序开发语言，针对不同的硬件平台，通过编译工具 链可以产生最终的可执行代码，在相应的节点上运行，目前最常用的是开源的g c c 在不同平台下移植后的版本，如a v v g c c 或m s p 4 3 0 - g c c 等。图2 1 是c 程序的具 体编译系统，包含了c 语言编译器，汇编器，链接器等。 浙江 硎十￥论立 镕2 $ * i i a 目关口女摊述 图2 1c 苦言编译系统 首先c 编译器将c 文件进行编译处理，产生对应的汇编代码文件。在使用c 语言开发时，可以以编译器支持的方式在代码中直接嵌入汇编代码，或者直接以 手工编写汇编代码但除非必要，如需要直接使用某些特殊指令等操作，通常由 编译器产生汇编代码。在c 代码中，可以通过使用不同平台下的c 库，避免一些 底层操作，在c 库中对端口和寄存器地址等信息进行封装，还提供一些通用摹本 操作，在引用相应的头文件后使用。然后通过汇编器，将由c 文件产牛的汇编文 件毗及其它可能用到的外部汇编文件，热同处理产生独有独立地址的0 b i 文件供 链接器处理。链接器将系统库与之前汇编器产生的。断文件中的符号台并，加上 系统启动代码，进行重定位操作之后生成最终可以执行的e l f 文件，通常仿真工 具多直接使用e l f 文件作为输入，而调试工具可以使用含有调试信息的e l f 文 件进行调试操作，对于节点执行来说，e l f 格式的文件含有许多多余的信息，最 后将e l f 文件中的符号表等信息去除，产生供节点分发和运行使用的f i e x 格式 文件，上传到节点上执行。 2 1 2 2a e s c 语言编译系统 对于其它编程语言，特别是针对无线传感器喇络系统而专门设计的语言，如 塑些三兰堡兰兰堡堡兰苎! 兰璺堡苎竺些三墨塑墨笪墨垦垩 果重新实现整个编译系统，面对各异的硬件平台，开发时具有相当的工作量和难 度。因而通常这些语言在编译时， _ _ 往利用现有的c 语言编译系统首先将使用 专用语言实现的应用程序转换翻译成c 程序，然后再针对具体的平台调用相应的 c 语言编译工具，产生最终的可执行文件。图2 2 是t i l l y o s 系统中n e s c 的编译 流程。 罔2 , 2t i n y o s 系统中n e s c 编译流程 i i n y o s 中的应用程序由多个n e s c 文件构成，在编译时，旨先通过n e s c 的编 译工具将一个n e s c 应用中的多个n c 文件进行分析处理转化为一个单一的c 文 件，然后利用相应平台下的c 编译器处理该c 文件。 具体的，对于具体的n e s c 应用，在其m a k e f i l e 中指定了一个n e s c 的配置组 件文件作为参数传递给n e s c 编译器，生成c 文件的过程分为如下儿步：首先对 传入的文件进行词法和语法分析，然后递归的将其用到的其它组件模块全部加 载，然后将载入的模块和接口进行连接，产生一个类型为c g r a p h 的图，之后对其 中的一些常量进行展开，最后入口函数开始，依照之前的连接关系罔将有连接的 函数依次处理，并进行内联函数的优化，产生最终的c 文件。 】2 | | | 一 浙江大学硕士学位论文第2 章编译系统及工具相关背景概述 v i r g i l 的编译流程也是如此，使用c 语言作为中间语言完成代码的编译。另 外还有一些语言，在编译过程中，利用现有t i n y o s 系统丰富的功能和相对完善 的编译系统，将其特殊语言首先进行翻译产生对应的n e s c 应用程序，然后再使 用现有的t i n y o s 编译环境将生成的n e s c 应用进行编译处理。 2 1 2 3 解释型语言的编译处理 以上的那些语言的编译过程都是在本地完成，最终产生可执行文件以供节点 直接执行。而对于采用虚拟机模型的编程语言，则需要在节点上完成语言的解释 执行。其中以m a t e 虚拟机最为典型。图2 3 是其编译执行系统。 图2 3m a t e 7 虚拟机编译执行系统 m a t e 7 提供了一种通用的采用堆栈结构的虚拟机架构，所谓通用模型是指其提 供了一些基本的操作原语，然后基于这些基本操作可以定义上层不同的指令集。 t i n y s c r i p t 是基于之上的一种解释型语言。m a t e 的编译过程系统主要分为两部分， 虚拟机的构建和程序的编译。在编译过程中，首先通过向v m b u i l d e r 提供语言的 浙江大学硕十学位论文第2 章编译系统及工具相关背景概述 定义信息，然后将生成t i n y o s 应用程序作为基本的虚拟机烧录到节点上。然后 对于应用程序代码，通过译码将其转换为符合定义的虚拟机指令，应用程序以字 节码的形式传递到节点上然后进行解释执行。 2 2 编译工具概述 在语言的编译系统的设计实现上，除了完成基本功能将应用程序编译为可执 行文件之外，往往还设计实现一些辅助工具，以此在系统资源的使用或分配上进 行优化【2 3 1 ，特别是在内存使用上【2 4 】。下面着重就堆栈使用的分析工具详细介绍。 微型传感器节点中，内存空间极为有限，有限的内存空间，主要分配给d a t a 段、b s s 段以及堆栈共同使用，如果有使用动态内存，则一般还要使用堆空间与 堆栈相对增长。其中d a t a 段与b s s 段分配给全局变量，在编译期可以确定其空间 占用。而堆栈的使用则随着程序的执行而不断变化，在程序执行时，函数调用或 者中断被处理时，需要将寄存器的内容保存到堆栈上，如果堆栈的使用超出了内 存的限制，程序本身的执行也随之发生异常。对于节点程序而言，对其堆栈使用 进行分析就十分必要。 在程序运行时，可以清楚的了解到其当前的内存使用状况，通过采用测试的 方法，可以了解程序的堆栈的使用情况。例如在a v r 平台下，使用仿真工具 a v r o r a 【2 5 1 ，通过跟踪堆栈指针寄存器的内容，就可以在仿真运行时可以对堆栈的 使用情况进行监测。但是，仅是通过实际执行代码，一方面在测试中某些执行路 径可能未被经过，另一方面，对于主要由中断处理程序构成的代码而言，其最坏 情况下的堆栈使用，发生在多个中断相互嵌套的情况下，并且在不同的嵌套顺序 下的堆栈使用也有所不同，因而很难检测到最坏情况的发生。另外，利用测试的 方法，仅能得知系统是否是安全的，也无法利用其测试结果对内存的使用进行优 化。 除了实际执行以外，也可以通过静态分析的方法分析程序的堆栈使用，这也 是目前最常采用的分析方法。通过对编译产生的可执行文件对应的汇编代码进行 静态分析，可以了解其堆栈使用情况，主要的工具包括s t a c k e s t i m a t o r 2 6 】和 1 4 塑垩奎兰堡主兰垡堡茎兰! 兰塑堡至竺墨三墨塑茎堕墨壁堕 s t a c k t o o l l 2 7 1 。目前的这些研究工作，多侧重于某一特定平台或系统，并且其分析 结果仍有进一步精确的可能。 s t a c k e s t i m a t o r 是t i n y o s 下的多线程库t i n y t h r e a d 中携带的一个堆栈分析工 具，其主要是用来分析t i n y t h r e a d 中各线程的堆栈使用，以使各线程的分配堆栈 更为有效。s t a c k e s t i m a t o r 可以支持目前主要的无线传感网络平台m i c a z 和 t e l o s b ，但是其实现方法较为简单。在计算堆栈使用情况，s t a c k e s t i m a t o r 在对单 个函数进行处理时，顺序的计算每条指令的堆栈使用，并未考虑分支跳转等指令 的影响，然后仅根据全局中断允许位的状态，用以计算最终的结果。 s t a c k t o o l 是针对a v r 芯片的堆栈分析工具，在其静态分析的过程中，进行数 据流的分析，可以更为精确的得到不同寄存器的可能取值及相应的状态。该方法 仅针对单一平台，同时其数据流分析的方法在实现上有一定的复杂性，难以在多 种平台下进行扩展。 2 3 本章小结 本章介绍了当前传感器节点上所使用编程语言的编译系统以及编译过程中 现有的优化工具。首先介绍了目前进行节点编程时所采用的各种编程语言以及各 种语言的编译过程，主要介绍了c 语言、n e s c 语言以及解释型语言的编译过程。 然后，在编译系统之中，对应用程序的堆栈使用分析工具进行了介绍。 浙江大学硕士学位论文第3 章s e n s p i r eo s 编译系统研究 3 1 概述 第3 章s e n s p i r eo s 编译系统研究 s e n s p i r eo s 2 8 】f 2 9 1 是一个基于无线传感节点的微型操作系统，以该操作系统为 核心，利用其提供的各种服务，可以针对不同的平台，进行具体应用的开发。 s e n s p i r eo s 相对于其它针对无线传感器网络的操作系统，在平台支持、任务调度 机制和所提供的上层服务方面都具有一些独特之处。首先，该系统可以灵活支持 多种不同的微型传感器节点硬件平台，通过抽象出不同硬件之间一致的访问接 口，构件化的设计和实现，提高代码的复用率，不仅支持了目前流行的m i c a z 和t e l o s b 节点平台，还对自主设计并实际使用的s e n s p i r e 硬件平台予以支持。其 次，在任务调度方面，提出了灵活、轻量、实时的任务调度机制，实现了事件驱 动与多线程相结合的混合调度模型。最后，该系统向上层应用程序提供了功能丰 富的高层服务，特别是在网络通信方面，在底层对不同平台下的无线通信芯片进 行抽象和封装，屏蔽硬件的细节，使上层应用使用时具有一定的跨平台性，通过 同时管理来自不同网络协议资源层，管理来自不同网络协议的通信请求，保证不 同协议间的公平性和实时性，另外可以支持基本的网络通信协议，系统对上层的 应用提供了通用的支撑服务，包括邻居列表维护和链路估计等。 s e n s p i r eo s 在开发实现时，主要使用c 语言来完成，一方面是由于执行效 率方面的要求，另一方面c 语言针对各种硬件平台都有成熟的编译环境。基于该 系统，进行上层应用程序的开发时，在直接使用c 语言之外，通过提供新的编程 语言，针对节点自身的特点和底层操作系统的特点，可以更为有利一般开发者实 现应用程序。另一方面，随着无线传感器网络应用的增多和规模的扩大，节点程 序的复杂程度也随之上升，编程语言如果没有底层操作系统作为基础或者自身提 供多种功能的系统库进行支持，程序开发的难度并不能有效的降低。 c s p i r e 语言是针对无线传感器网络微型节点而设计的一种编程语言。在现有 的设计实现中【3 0 1 ，主要提供在语法上对面向对象特性和事件订阅机制的支持，同 浙江大学硕士学位论文 第3 章s e n s p i r eo s 编译系统研究 时在编译过程中对可能的数据竞争情况进行检测，以此达到节点编程的封装性、 可靠性和易用性。现有的语言，在其设计和实现时，因而只从微型节点的自身特 点出发进行研究，缺少与底层系统的联系。 现在，随着底层微型操作系统的日趋完善以及程序自身开发的逐渐复杂，为 了更为方便的在现有底层系统中使用新型语言进行程序的开发，简化代码编写过 程，在应用程序编写时充分利用s e n s p i r eo s 所提供的种种资源，需要在该系统 的编译系统中，加入对新语言的支持，在现有工作的基础上，研究并设计新版本 的语言和语言的编译系统。首先，对于c s p i r e 语言，在语法设计和实现上进行改 进，一方面完善面向对象方面的特性，优化实现，另一方面是语言与s e n s p i r eo s 结合的协同设计，在语法层次上适应在该系统中程序的编写。另外，在s e n s p i r eo s 对c s p i r e 应用程序进行编译时，结合其语法特点进行检查和优化，使得在方便开 发的同时，保证执行的效率。 本章主要是关于s e n s p i r eo s 下使用c s p i r e 语言进行应用程序开发的编译系 统的研究。首先是关于新的c s p i r e 语言的设计，包括语言的设计目标以及语言的 具体特点；然后是在s e n s p i r eo s 系统中，针对c s p i r e 语言的编译系统的总体框 架，主要是c s p i r e 语言的编译过程以及在编译过程中的附加的安全检查与优化措 施等；最后是对实现的评测。 浙江大学硕士学位论文 第3 章s e n s p i r eo s 编译系统研究 3 2c s p