软件学报  2014, Vol.25 Issue (2): 326-340   PDF    
一种面向无线传感网应用重编程的逻辑式编程语言
朱晓瑞, 陶先平, 谢宏伟, 吕建    
计算机软件新技术国家重点实验室(南京大学),江苏 南京 210023
摘要:无线传感网的发展,使其需要具有高效地更新其上运行的应用软件的能力.为了解决这个问题,提出了一种面向无线传感网应用重编程的逻辑式编程语言及其处理系统ReLog.ReLog语言根据无线传感网应用的普遍特点,基于传统逻辑式语言进行扩展,并提供合适的编程抽象,方便程序员高效地构建、修改程序.同时,语言的处理系统使用中间代码将应用程序与系统软件解耦,从而减少应用更新时所需传输的更新代码的规模,提高更新效率.通过一个数据收集应用案例评估了ReLog语言及其执行机制,结果表明:使用ReLog语言能够获得简洁、易修改的程序;同时,语言的执行机制能够显著降低传输应用更新代码的能量和时间开销.
关键词逻辑式编程语言     操作语义     无线传感网     重编程     解释执行    
Reprogramming-Oriented Logical Programming Language for Wireless Sensor Network Applications
ZHU Xiao-Rui, TAO Xian-Ping, XIE Hong-Wei, LÜ Jian    
State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China
Corresponding author: ZHU Xiao-Rui, E-mail: zxr@smail.nju.edu.cn, http://www.nju.edu.cn
Abstract: The development of wireless sensor networks requires the ability of efficiently updating application software running on sensors. To address this problem, this paper proposes ReLog, a reprogramming-oriented logical programming language for wireless sensor network applications and its processing system. Based on common characteristics of wireless sensor network applications, the ReLog language extends a traditional logical programming language and provides suitable programming abstractions with which programmers can write and modify programs efficiently. Meanwhile, the language processing system leverages on intermediate code to decouple application programs from system software so as to reduce the size of updating code to improve the updating efficiency. This paper demonstrates ReLog through a case of data collection application. Results show that ReLog can achieve compact and ease-to-modified source code. In addition, the executing mechanism of ReLog can significantly reduce the cost of energy and time when transmitting updating code of applications.
Key words: logical programming language     operational semantics     wireless sensor network     reprogramming     interpreting    

无线传感网由资源(包括计算、存储、带宽和能量等)受限的传感器构成,通常被长期部署在目标区域收集数据,以支持各种应用[1].由于部署时间长,无线传感网常因应用维护(如修复bug)、应用需求变化(如感知新的信息)及应用实现变化(如使用更高效的算法)等原因需要对其传感器上运行的代码进行更新;又因受到部署区域和网络规模的限制,更新代码通常需要以无线的方式分发到各传感器上.我们将这种修改源程序、并将编译后的代码更新到传感器上的行为称为重编程(reprogramming)[2].

随着无线传感网应用领域的拓展及其自身规模的增长,重编程对程序设计语言提出了如下需求:

(1) 语言需要提供合适的编程抽象,帮助程序员高效地构建结构合理、易于修改和复用的程序.

(2) 对源程序的修改要易于反映到传感器上,因此语言的执行机制需要为传输的更新代码选择合适的抽象层次.例如,对单个传感器节点来说,传输中间代码所消耗的时间和能量通常仅约为传输二进制镜像的1%.对于整个网络,传输不同层次代码的时耗和能耗的差距与网络规模成正比[3].

(3) 语言的执行机制还要在网络正常运行开销和重编程开销之间进行权衡.

传统的嵌入式语言[4]不能很好地支持重编程:首先,嵌入式语言未提供合适层次的抽象,方便应用业务逻辑的描述,程序员需要从底层构建应用程序,并依靠经验保证程序结构的合理性.因此,编程工作繁琐,且程序不易修改和复用;其次,由于应用程序与系统软件一起被编译为目标代码,应用程序的更新需要整体替换传感器上的原有代码,更新代价较大.已有许多工作[5, 6, 7]针对嵌入式语言抽象层次低、书写程序繁琐的不足提出了不同的解决方法,但是这些工作并没有结合更新传感器上代码的问题一起考虑,因而对重编程的支持仍存在不足.

我们相信,逻辑式语言能够很好地满足重编程的需求.逻辑式编程风范关注“做什么”而不是“如何做”,这种编程风范不仅能够自然地屏蔽实现细节,使程序员更好地关注应用业务逻辑,而且能够降低业务逻辑与编程实现的耦合度,使程序易于修改和复用.同时,逻辑式语言适合解释执行,便于应用代码与系统软件解耦,减少重编程需要传输到传感器上的代码规模,使应用演化灵活.

因此,本文提出了一种面向无线传感网应用重编程的逻辑式语言:ReLog.ReLog语言的设计沿用了传统逻辑式语言的设计方法,并根据无线传感网应用的特点对语言成分进行扩展.扩展部分的设计充分考虑了无线传感网应用重编程的需求,使ReLog语言整体上保持了逻辑式语言低耦合的特性.为了清晰地理解ReLog语言,我们详细介绍了语言的各语言成分,并给出了语言中扩展部分的操作语义.为了减少更新代码的规模,ReLog语言处理系统采用了解释执行的实现方法来将应用代码和系统软件解耦.我们通过实验评估了ReLog语言及其处理系统,结果表明:使用ReLog语言能够书写简明、松耦合的无线传感网应用程序;同时,其解释执行的方式能够极大地降低应用更新时所需传输的更新代码的规模,从而降低应用更新的时间和能量消耗.

本文第1节通过一个示例介绍ReLog的总体设计思想.第2节给出语言的语法和操作语义.第3节简要介绍语言处理系统的设计和实现.第4节通过一个应用案例评估ReLog.第5节比较ReLog与相关工作.最后一节总结全文,并讨论ReLog中的一些问题.

1 ReLog设计思想

作为许多无线传感网应用的重要组成部分,生成树路由协议能够很好地反映无线传感网应用的特点,其算法描述如下:

(1) 每个节点获取其到一跳邻居的本地链路信息.

(2) 若节点是根节点的一跳邻居,则使用本地链路作为路由,并广播路由信息.

(3) 若节点是根节点的多跳邻居,且收到其一跳邻居广播的路由信息,则利用此邻居节点建立到根节点的路由.路由的代价是节点到其邻居的本地链路代价加上邻居节点到根节点的路由代价.路由建立后,广播路由信息.

(4) 若一个节点发现多条可选路径,则选择代价最小的作为路由.

协议的程序可参见TinyOS[8]已发布版本中对此协议的实现(程序名为MultihopLQI).

以此协议的算法为代表分析可知:(1) 无线传感网应用的业务需求可显式地分为数据加工和I/O相关操作两个部分.例如,在协议中,计算路由的数据加工过程不关心如何获取数据和如何使用计算结果,“I/O相关操作”(如收发消息)则负责为“数据加工”提供数据以及处理计算结果.(2) 应用具有事件驱动的特点.例如,协议中节点收到邻居节点路由消息的事件会驱动其计算新路径的代价,并与当前路由做比较.(3) 应用中的数据存在典型有效期.例如,在协议中,当新路径具有比当前路由更小的代价时,当前路由数据失效;(4) 无线传感网应用节点端业务需求不复杂.

无线传感网应用的特点决定了在为重编程设计语言时应遵循如下原则:

(1) 语言应能在较高层次上提供编程抽象描述数据加工和I/O相关操作,方便应用程序的书写;同时,应通过关注分离降低程序的耦合度.为此,需将数据加工和I/O相关操作显式地分开,并降低两者间的耦合度,使程序易于修改.

(2) 语言的设计应贴合无线传感网应用事件驱动的特点,使语言能够直观地描述无线传感网应用.

(3) 语言需要对应用中数据生存期的典型特征进行抽象,并提供语言设施加以描述.

(4) 语言的设计还应综合考虑其执行机制在无线传感网的特殊环境下对重编程的影响.

基于上述原则,ReLog语言的设计如下:

(1) ReLog语言的语言成分包括子句、shell和属性.子句中的事实和规则用于从高层描述数据加工逻辑;扩展的shell中的事件和动作用于建立事件和新事实的联系以及处理推理结果;属性可嵌入子句及shell中,用于声明事实的生存期和以及控制解释执行过程.

(2) 子句部分和shell部分在程序中显式地分开,并且两部分只存在数据耦合.

(3) 为了保持逻辑式语言低耦合的性质,扩展的shell部分中语句相互独立.

(4) 为了高效地将应用更新的代码传输到传感器上,ReLog使用中间代码将应用程序与系统软件解耦.中间代码仅包含与应用业务逻辑相关的代码,因而体积小,便于传输.

图 1展示了使用ReLog语言书写的生成树路由协议的样例程序:

Fig. 1 ReLog program of the spanning-tree routing protocol 图 1 生成树路由协议的ReLog程序

节点首先获得到达邻居节点的本地链路和代价(第9行).若节点为根节点的一跳邻居,则路由建立(第4行);若节点为根节点的多跳邻居,则通过已经建立路由的邻居节点来建立路由(第5行).若存在多条路径,则选择代价最小的那条作为路由(第6行).路由建立后,则广播路由信息(第10行),以便邻居节点收到消息后(第11行)建立路由.

可以看出,ReLog程序基本上是对协议算法的直接翻译.同时,在协议算法改变时,对源程序的修改也很方便.例如,若协议需要使用不同的链路质量评估策略,则只需将程序第9行的getLQI替换为需要的策略;又如,若需要在计算路径代价时仅考虑跳数(hop)的影响,则只需将path中的参数Cost替换为Hops,并在计算path的代价时使用此参数(将第5行中的Cost1+Cost2修改为Hops1+Hops2).同时,ReLog的解释执行机制使程序修改后需要更新到传感器上的代码量很小.另外,我们基于逻辑式语言进行扩展以及使用解释执行机制的原因,还在于易于在将来实现细粒度的增量式重编程.例如,某次应用更新仅修改了程序中的1条规则,则仅将这条规则对应的中间代码更新到传感器上.

2 ReLog语言成分及其语义

本节首先介绍ReLog语言中的各语言成分,随后给出作为扩展成分的属性及shell部分的操作语义.

2.1 语言成分
2.1.1 子句定义

ReLog语言继承了传统逻辑式语言中的许多成分,包括常量、变量、项、谓词、原子、事实和规则:

(1) 常量可以是表示节点编号等的整数,或是表示某些特殊含义的以小写字母开头的标识符,如sys_Root (表示sink节点).变量是首字符为大写字母的标识符,如Source.项可以是常量、变量,或是使用项作为参数的函数或算术表达式,如Cost1+Cost2.若项为常量或变量,则称其为平凡项.

(2) 谓词用于表示对观察对象的性质的判定,使用以小写字母开头的标识符来表示,如path.若p为谓词, t1,…,tn为项,则p(t1,…,tn)为原子,如dest(Dest).特别地,若t1,…,tn均为平凡项,则称原子p(t1,…,tn)为平凡原子;若t1,…,tn均为常量,则称原子p(t1,…,tn)为事实,如dest(sys_Root).

(3) 规则由演绎(deduction)符号“:-”、符号左边的一个原子(称为规则头)以及符号右边的1个或多个平凡原子(称为规则体)组成,如path(Source,Dest,Dest,Cost):-dest(Dest),link(Source,Dest,Cost).为了方便使用,ReLog允许在规则体中使用关系表达式,如Source!=Parent,此关系表达式在编译时被翻译为与之等价的内置原子sys_neq(Source,Parent).

2.1.2 属性定义

除了这些传统的语言成分以外,ReLog还引入了属性(attribute),用于声明事实的生存期,以及控制解释执行过程.在典型的无线传感网应用中,事实的有效期存在特定的规律.例如,在物体跟踪应用中,描述传感器在每个周期中感知到的物体位置的事实只在当下周期中有效;又如,在路由协议的示例中,每个节点只会保留最新的描述路由信息的myNextHop事实.因此,程序员可以利用一些属性声明事实的有效期,过期的事实由系统自动删除以节省存储空间.这些属性包括:

(1) @unique:在新的事实出现之前,已有的事实持续有效.例如,在路由协议示例中,节点在未找到更好的路由前,已有的用于描述路由信息的myNextHop事实持续有效.对于具有unique属性的事实,在更新事实库时1次只可向事实库中插入1个事实.

(2) @volatile(idtimer):事实在与之关联的定时器到时触发前有效.例如,link(Source,Dest,Cost)@volatile(t1)表示每当定时器t1到时触发时,已有的描述链路质量信息的link事实全部失效.对于具有volatile属性的事实,1次可向事实库中插入多个这样的事实.

与事实有效期相关的属性不能出现在规则体中.

为了节省计算资源,传感器上的解释器需要避免执行一些不需要的规则推理.例如,在示例程序中,当有新的path数据到来时,在确定由此路径生成的路由比当前路由更优(即,有新的minCost事实生成)之前,不需要对生成路由的规则(示例第7行)进行推理.因此,ReLog提供了@passive属性:具有passive属性的原子在其新事实到来时不触发原子所在规则的推理.显然,@passive属性只能出现在规则体中.

2.1.3 Shell定义

Shell部分的语句按照功能可划分为插入语句(insertion statement)和执行语句(execution statement).从功能上来看,插入语句用于向事实库插入事实以触发规则推理,执行语句则根据推理出的事实执行相应动作.同时,根据触发语句执行的方式不同,又可分为主动(proactive)语句和反应式(reactive)语句.主动语句由定时器到时触发执行,定时器的定义为timer(id,start,ni,nc),表示定时器id每隔ni ms触发一次.参数start表示定时器开始计时的时机:若其值为sys_Initial,则在系统启动时开始计时;若为其他定时器名id¢,则在定时器id¢到时触发后开始计时.参数nc表示定时器触发的次数:若其值为常数n,则表示只触发n次;若为sys_Infinity,则定时器会持续工作.反应式语句由相应事件触发.

(1) 插入语句

主动插入语句的形式为

其中,idevent(c1,…,cn;v1,…,vm)为事件,事件名idevent和实参c1,…,cn共同用于注册事件.当定时器到时后,事件发生 并将返回结果存放在变量v1,…,vm中.插入动作会使用v1,…,vm中的值将原子初始化为事实,并将其插入到事实库中.例如示例中的第9行代码,事件getLQI(;Srouce,Dest,Cost)会将与邻居节点的链路质量信息保存在变量Source,DestCost中,insert(link(Source,Dest,Cost))则利用变量的值初始化link事实并将其插入到事实库中.

反应式插入语句由接收消息事件触发执行,其形式为

当接收到类型为typemsg的消息时,receive事件发生,消息载荷中的数据被存放在变量v1,…,vm中.插入动作会使用v1,…,vm中的值将原子初始化为事实,并将其插入到事实库中.

(2) 执行语句

主动执行语句的形式为

其中,predicate(v1,…,vm)事件用于检查事实库中是否存在谓词predicate的事实.当定时器到时后事件发生,并选取谓词最新的事实predicate(c1,…,cn)中的值c1,…,cn依次为变量v1,…,vm赋值.动作使用、v1,…,vm中同名变量的值作为实参并依次执行.

反应式执行语句由推理出的事实触发,其形式为

当事件predicate(v1,…,vm)发生时(即,有事实predicate(c1,…,cm)被推理出),变量v1,…,vm会依次使用c1,…,cm 进行赋值.动作会使用v1,…,vm中同名变量的值作为实参并依次执行.例如示例中的第10行代码,当有新的myNextHop事实产生时,事实中的值会被广播出去.

2.2 操作语义

为了更清晰地理解ReLog语言,同时指导语言处理系统的实现,本节首先通过一个示例解释ReLog程序的运行过程,然后通过借鉴通信系统演算(calculus of communication system)[9]给出ReLog语言的结构化操作语义.由于ReLog语言中子句定义部分的语义与传统逻辑式语言基本相同,故这里不再赘述.我们只给出语言扩展部分的操作语义.

2.2.1 ReLog程序运行过程

首先,通过一个示例描述ReLog程序的运行过程,以帮助理解后续将要给出的ReLog语言的形式语义.假设应用需要监测环境温度,并要求当温度值高于37时,传感器将温度数值连同自己的节点编号广播出去.用ReLog语言书写的应用程序的运行过程如图 2所示.

此程序的运行过程描述如下:

(1) 定时器每500 ms到时触发后,感知(sense)事件发生并返回环境温度数值(value);

(2) 与此感知事件关联的readings原子使用Value的值初始化为事实;

(3) readings事实被插入到事实库中,

(4) 并触发规则推理;

(5) 推理出的warning事实同样被添加到事实库中,

(6) 同时,引起warning事实产生事件发生;

(7) 事实产生事件会触发发送动作,将事实包含的值发送出去.

Fig. 2 Illustration of the execution of a ReLog program图 2 ReLog程序运行示意

在对示例程序中的各语句的语义有了直观了解以后,我们接下来给出语言扩展部分的形式化操作语义.

2.2.2 定义与表示方法

给定序列Sh::T,函数head返回序列S的第1个元素h.

给定事实fact,约定stamp(fact)表示事实产生的时间.

定义1. 代入θ为变量及其值的集合:θ={c1/v1,…,cn/vn},其中,v1,…,vn为互不相同的变量,c1,…,cn为常量.约定使用符号^表示无效代入.

给定事件idevent(c1,…,cm;v1,…,vn),事件发生后将返回一个代入

给定平凡原子p(v1,…,vn)和事实θ(c1,…,cn),若谓词p与θ相同,则原子与事实可进行合一(unify).合一的结果为一个代入,其定义为


给定原子p()和代入θ,若被θ约束,则p(θ)为事实,并称此事实与原子p()关联.

定义2. 任务可分为推理任务(taskr)和插入任务(taski),推理任务被用于完成规则推理,插入任务被用于向事实库中添加事实.对于规则taskrtaski的定义如下:


给定原子p()和代入θ1,…,qn,且p(θ1),...,p(θn)为事实,函数posti用于生成插入任务:


给定事实库F和插入任务taski,函数insert用于将taski中的事实插入到事实库中:

给定事实库和原子p()函数exist用于判断p()是否存在于F中:

给定事实库F和原子p()若则函数delete删除事实库中与p()关联的事实:

给定原子p()和事实库F,函数p返回事实库中与p()关联的事实序列p()

给定动作action1,…,actionn,action1∇…∇actionn表示依次执行动作action1,…,actionn.

2.2.3 Shell部分的操作语义

为了方便讨论,我们首先单独给出定时器的操作语义;然后,在此基础上分别给出shell部分中4种语句的操作语义.

(1) 定时器的操作语义

如前所述,定时器的定义为timer(id,start,ni,nc).每次定时器到时触发后,均向内部信道b发送一条消息宣布自己触发:

其中,timestart表示定时器开始计时后持续的时间.若参数startsys_Initial,则timestart=timesys,表示定时器在系统启动后持续的时间(timesys为传感器的系统时间);若为其他定时器名,则timestart=timesys-timeβ?id¢,表示在信道b接收到定时器id¢触发时所发送的消息后持续的时间.

(2) 语句的操作语义

Stask表示待执行的任务序列,使用序偶ástm,Staskñ表示语句的格局,其表示在当前任务序列下将执行语句stm.各语句的语义如下:

i. 主动插入语句(PIS)

当从内部信道b收到定时器到时触发的消息以后,主动插入语句中的事件会发生并返回1个或多个代入.随后,insert动作使用这些代入θ1,…,qn和其包含的原子p()向Stask的末尾添加一个插入任务.

ii. 反应式插入语句(RIS)

当从外部信道a中收到消息(msg)时,若消息类型与receive事件中给定的类型相同,则receive事件返回一个 代入θ.随后,insert动作使用θ和其包含的原子p()向任务序列Stask的末尾添加一个插入任务.

iii. 主动执行语句(PES)

其中,当从内部信道b收到定时器到时触发的消息以后,主动执行语句中检测与原子关联的事实是否存在的事件发生,并返回原子与其在事实库中关联的最新事实合一后得到的代入θ.随后,语句中的动作会使用θ对参数赋值并依次执行.

iv. 反应式执行语句(RES)

其中,当从内部信道g接收到推理出的事实时,若事实的谓词与语句中原子的谓词相同, 则新事实产生事件发生并返回一个代入θ.随后,语句中的动作会使用θ对参数赋值并依次执行.

2.2.4 属性的操作语义

(1) @unique属性

给定事实库F和插入任务属性影响向事实库中插入事实的insert函数的定义.若,则

即,新事实的插入会删除已存在的事实.

(2) @volatile(idtimer)属性

使用序偶表示属性的格局,则@volatile(idtimer)的操作语义为

即,定时器到时触发后删除事实库中与原子p()关联的所有事实.注意,volatile属性在实现时并未完全按照此语义.若定时器到时触发后解释器正在执行推理任务,则删除操作延迟到推理结束之后进行,以避免volatile属性的副作用.

(3) @passive属性

给定事实属性@passive影响推理任务的生成.设函数postr用于生成推

理任务,其定义为

3 语言处理系统

使用嵌入式语言[4]书写的程序会与系统软件一起被编译为二进制镜像.由于二进制镜像通常规模较大,通过无线传输将其分发到传感器上代价高昂;同时,因为二进制镜像中应用程序与系统软件耦合紧密,对镜像中的应用代码进行增量更新存在诸多限制[10].

为了降低更新传感器上代码的代价,ReLog使用中间代码将应用程序与系统软件解耦.中间代码仅包含与应用业务逻辑相关的代码,因而体积小,便于传输.因此,ReLog语言处理系统选择了编译加解释的体系结构:包括运行在服务器端的编译器和运行在传感器端的解释器(如图 3所示).编译器负责将源程序转换为与具体传感器平台无关的中间代码,解释器和系统软件则常驻在传感器上解释执行接收到的中间代码.

Fig. 3Architecture of the ReLog processing system图 3ReLog处理系统体系结构
3.1 编译器

编译器的主要任务为生成仅包含应用业务逻辑的中间代码,从而减少应用更新所需要传输的代码量,提高重编程效率.同时,考虑到解释执行机制会给传感器执行应用代码带来一定的额外负担,因此,编译器的另一项重要任务是对中间代码进行优化,以提高解释器的计算速度并降低其能耗.

传感器上解释器的计算需求主要源自推理过程,包括:

(1) 当新事实到来时,查询需要进行推理的规则.

(2) 在推理过程中,查找能与当前原子进行合一操作的事实.

(3) 合一操作.其中,前两项查询操作带来了可观的计算开销,因此需要对其进行优化.

我们在中间代码中使用了如图 4所示的索引图技术来解决这个问题:(1) 每条规则都知道自己的规则体中包含的所有原子;(2) 与原子关联的所有事实按照存在时间递增顺序组织成链表,原子指向链表中第1个事实.因此,当有新事实到来时,根据事实关联的原子可知,应选择哪些规则进行推理.同时,在规则推理过程中,规则体中每个原子都可直接找到可用于合一操作的事实.

Fig. 4Illustration of the index graph图 4索引图示意
3.2 解释器

解释器与支撑其运行的系统软件一起常驻在传感器上解释执行中间代码.解释器使用nesC[4]语言在TinyOS[8]操作系统的基础上实现,其核心部分包括调度器、推理器、事实管理器和指令执行器(如图 5所示).

Fig. 5Architecture of the ReLog interpreter 图 5ReLog解释器体系结构

调度器负责根据任务类型调用不同的功能模块执行任务:若为推理任务,则调用推理器进行推理;若为插入任务,则调用事实管理器更新事实库.推理器负责对规则进行推理,若推理出新事实,则将事实交予事实管理器.事实管理器将推理出的事实插入到事实库,并根据事实向任务队列中添加相应的推理任务,同时,还将事实推送给指令执行器.指令执行器负责在收集到数据(包括接收到和感知到的数据)以后,向任务队列中添加相应的插入任务,或者根据事实管理器推送来的事实执行相应的动作.

3.2.1 实现选择

(1) 运行机制

解释器实现的一个重要问题是,如何在保证推理正确性的同时及时响应事件.例如在单条规则的推理过程中,推理涉及的事实不应被修改.此时,若事件发生(如接收消息)并请求更新事实库,则此事件应被响应,同时,更新请求应被推迟到规则推理完成后进行(如图 6所示).为了解决此问题,解释器的实现使用了TinyOS[8]提供的任务机制:任务之间以非抢占的方式按照发布时间的先后顺序执行,任务执行可以被事件中断.因此,ReLog解释器中的规则推理和事实库更新均被封装成任务.当事件发生时,当前的任务执行会被中断以响应事件,但是事件的处理(更新事实库)则被封装成任务放入任务队列中等待执行.

Fig. 6Running mechanism of the interpreter图 6解释器运行机制

(2) 内存分配

在无线传感网应用运行过程中,事实库中的事实变化频繁,因此,动态内存分配理论上可更好地支持推理过程和事实库管理.但是,ReLog解释器的实现选择了静态内存分配,其原因如下:

(1) 由于用户界面不友好,收集传感器上程序运行失败的信息很困难.静态内存分配易实现在内存不足时主动通知程序员,帮助程序员修改程序.

(2) TinyOS[8]对动态内存分配的支持不足.与实现健壮的动态内存分配相比,静态内存分配实现代价小,并且可以根据解释器中数据操作的特点进行优化.

4 案例研究

本节使用温度数据收集应用作为案例评估ReLog在如下4个方面的表现:(1) 通过使用ReLog语言书写应用程序展示语言的简明性;(2) 通过比较编译后代码的规模来评估更新的灵活性;(3) 通过比较每个传感器的丢包率和能耗来评估解释器的性能;(4) 通过比较应用程序运行时传感器上的内存开销来评估解释器的适用性.在评估中,我们使用nesC语言书写的程序作为对比目标.

温度收集应用要求传感器每500 ms采集一次温度数据,并将数据连同传感器节点编号一起发送给基站.父节点需要转发其子节点的数据包.为了更清楚地展示解释器的性能,我们在温度收集应用中使用静态路由来消除路由协议(例如CTP协议)带来的影响.应用的网络拓扑如图 7所示.

Fig. 7Topology used in the data collection application图 7数据收集应用中使用的拓扑
4.1 语言的简明性

图 8展示了使用ReLog语言书写的应用程序,其含义为:每隔500 ms定时器到时后,利用温度感知设备采集温度数据生成reading事实并插入到事实库中(第6行),reading事实触发规则推理生成log事实(第3行);若接收到子节点的消息,则生成forwarding事实并插入到事实库中(第7行),forwarding事实也会触发规则推理生成log事实(第4行);推理出log的事实会触发发送动作的执行,将log中记录的数据发送给父节点(第8行).

Fig. 8ReLog program of the data collection applicatio图 8数据收集应用的ReLog程序

使用ReLog语言书写的数据收集程序基本上可以看做是对应用需求的简单翻译,并且程序员不用考虑与应用需求无关的诸如硬件设备管理、消息缓冲等实现细节.

4.2 更新的灵活性

图 9展示了使用nesC语言书写的程序在编译后(目标平台为MicaZ传感器)的二进制镜像和ReLog程序编译后的中间代码的规模对比:二进制镜像为40261字节,而中间代码为245字节,仅为二进制镜像的0.6%.其原因在于:

(1) nesC程序会与操作系统一起编译,编译后的二进制镜像中大部分代码与应用业务逻辑无直接关系,而ReLog中间代码仅包含应用业务逻辑的相关代码.

(2) 与二进制镜像相比,ReLog中间代码的抽象层次较高.

Fig. 9Size of code 图 9代码规模

为了更直观地展示二进制镜像和中间代码对重编程的影响,我们使用Avrora[11]模拟器在MicaZ传感器上比较传输两种代码的能量和时间开销:

在传输二进制镜像时,我们使用载荷为28字节(默认最大载荷)的数据包;

在传输中间代码时,则使用了ReLog用于传输中间代码的真实数据包(载荷为24字节).

图 10图 11分别展示了传输两种代码的能耗和时耗:传感器在传输二进制镜像时,共消耗了8 826mJ的能量以及4 251ms的时间;而在传输中间代码时,仅消耗了508mJ的能量以及225ms的时间.由此可见,ReLog可以很好地支持重编程的需求,使应用演化灵活.

Fig. 10Energy consumption of code transmission图 10代码传输的能耗

Fig. 11Time consumption of code transmission图 11代码传输的时耗
4.3 解释器的性能

我们将nesC版本和ReLog版本的程序分别在Avrora模拟器上运行60 s.图 12给出了两个版本的程序运行结果中每个传感器总共发送数据包的数量.与预期一样,越靠近基站的传感器,丢失的数据包越多.但可以看出,两个版本中每个传感器的丢包情况非常接近,因此在这个应用中,ReLog解释执行的方式可以满足应用需求.

Fig. 12Number of packets sent by each node图 12节点发送数据包的数量

图 13给出了两个版本中每个传感器的能耗情况.ReLog版本传感器的总能耗在900mJ~1286mJ之间;而nesC版本在882mJ~1 205mJ之间.ReLog版本的传感器比nesC版本最多多消耗6.7%的总能量(节点1).而在每一轮(定时器两次触发之间)中,ReLog版本的传感器仅比nesC版本多消耗0.15mJ~0.68mJ的能量,这与一次更新节省的能耗(8 318mJ)相比是可以接受的.

Fig. 13Energy consumption of each node图 13节点能耗

另外,在ReLog版本中,传感器的通信能耗(尤其是发送消息的能耗)较高的原因在于数据包较大:因为无法预测传输应用数据所需的载荷大小,目前版本的解释器预先将数据包载荷设置为24字节.在这个应用中,nesC版本的程序所使用的数据包载荷仅为4字节,因而能耗较低.在未来的工作中,我们将为应用提供多种载荷的数据包,应用可选择最合适的数据包发送数据,以此来进一步降低能耗.

4.4 解释器的适用性

传感器的内存资源非常有限.在流行的传感器平台中,MicaZ可提供128KB的ROM和4KB的RAM,而TelosB可提供48KB的ROM和10KB的RAM.图 14给出了两个版本的程序在MicaZ平台上运行的内存开销. ReLog程序(即解释器)需要26 366字节的ROM和3 725字节的RAM,而nesC程序仅需要14 322字节的ROM和931字节的RAM.解释器的RAM消耗很高,其原因在于解释器使用了静态内存分配,也就是说,对于所有应用程序,其所需要的RAM始终约为这么多.另外,由于传感器上通常只运行1个程序,因此RAM全占用的情况是可接受的.

Fig. 14Memory overhead 图 14内存开销
5 相关工作

随着无线传感网的发展,许多工作致力于为应用编程提供支持,其中一些工作借鉴了申述式方法.

TinyDB[12]和Cougar[13]将无线传感网看作是关系数据库中的表,并提供类似SQL的语言让用户查询数据.查询结果由各传感器节点流向基站,并在汇集过程中根据需要进行合并,以减少传感器的资源消耗.TinyDB和Cougar提供的这种编程抽象能使用户写出非常简洁的代码,但同时,也因为抽象程度过高从而只能支持部分无线传感网应用[14].与这些工作不同,ReLog语言的设计总结了典型无线传感网应用的普遍特点,使其能够支持大多数无线传感网应用.

Snlog[15]也是逻辑式语言,其在传统逻辑式语言的基础上扩展了位置标识符和内置谓词机制.位置标识符用于声明数据的宿主,以此向用户屏蔽传感器间的通信细节;内置谓词机制可让用户使用嵌入式语言实现某些自定义谓词,通常用于将逻辑式程序与定时、感知等I/O相关操作链接起来.Snlog使用逻辑式语言成分处理无线传感网应用中的数据加工部分,而将逻辑式语言不擅长处理的I/O相关操作留给嵌入式语言解决,因而削弱了逻辑式语言所带来的松耦合的特性,增加了源程序修改的难度.同时,Snlog中的嵌入式语言成分促使语言处理系统采用了将源程序与系统软件一起编译为二进制镜像的实现方式,因而不利于应用更新.与Snlog不同, ReLog语言主要支持无线传感网应用的重编程.为了保持逻辑式语言松耦合的特性,作为扩展的shell部分提供高层抽象用于描述I/O相关操作;同时,其与子句部分在程序中显式地分开,且两者只存在数据耦合.此外,shell部分中的语句也相互独立,这样的设计不仅使得ReLog程序耦合度低,且语言的处理系统便于使用解释执行机制来降低更新代码的规模,从而高效地支持重编程.

在解释执行方式的相关工作中,VM*[16]在传感器上部署剪裁后的Java虚拟机,以解释执行源程序编译后得到的字节码.VM*致力于使用虚拟机来解决无线传感网规模性和传感器节点异构性的问题.虚拟机通常并不提供全部服务,若所要解释执行的代码包含虚拟机未提供的服务,则首先需要对虚拟机进行更新.与VM*不同,ReLog致力于提高重编程的效率.部署在传感器上的解释器提供执行应用代码可能需要的所有服务,因此不需要对解释器进行更新.同时,对于相同的源程序,ReLog编译器所生成的中间代码规模通常更小.

6 总 结

无线传感网的发展使得重编程问题日益重要.本文设计和实现了ReLog——一种面向无线传感网应用重编程的逻辑式语言.ReLog语言基于无线传感网应用的普遍特点,提供合适的编程抽象,方便程序员书写、修改和复用程序.同时,语言的执行机制使用中间代码将应用程序与系统软件解耦,极大地减少了应用更新所需传输的代码量,提高了重编程的效率.

最后,我们就ReLog语言及其执行机制的一些问题进行讨论:

(1) 语言成分

程序员在使用ReLog语言书写程序时,通过插入语句向事实库插入事实,通过申明原子的属性,让系统自动删除相关事实.ReLog并未提供语言成分支持程序员显式地删除事实库中的事实,其原因如下:

首先,我们使用ReLog书写了几类典型的无线传感网应用,发现现有的语言成分已能很好地支持应用编程.

其次,事实的不当删除将会造成推理过程出错,提供显式删除事实的语言成分,不利于保证程序的正 确性.

(2) 语言的可扩展性

DSN提供的内置谓词机制,允许程序员使用嵌入式语言实现自定义谓词.ReLog目前并未提供类似扩展机制,原因如下:

首先,对这种扩展机制的不当使用会导致源程序结构复杂,难以修改.

其次,扩展部分使用嵌入式语言实现,这提高了将源程序编译为中间代码的难度.

以上两点均不符合ReLog作为支持应用重编程语言的目的.

(3) 语言的执行机制

ReLog语言解释执行的机制在传感器执行应用代码时不可避免地带来一些额外开销,但是我们可以看出:

首先,无线传感网应用节点端的业务并不复杂.例如第1节所示的生成树路由算法对无线传感网应用来说已较为复杂,但在图 1所示的ReLog程序中,仅使用7条语句(4条规则和3条shell语句)就可以描述.因此,即使应用程序使用解释执行,其执行速度也很快.

其次,多数无线传感网应用并没有苛刻的实时性要求,解释执行速度可满足应用需求.例如,在图 12所示的多跳数据收集应用中,解释执行的速度并未影响应用运行的结果.

从无线传感网的现状来看,用户需要根据应用特点在网络正常运行开销和重编程开销之间权衡.从长远来看,随着无线传感网规模的扩大,传统的传输二进制镜像支持重编程的方法可能效率很低,甚至不能胜任重编程工作.因此,ReLog选择了解释执行机制.

参考文献
[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Computer Networks, 2008,52(12):2292-2330 .
[2] Wang Q, Zhu Y, Cheng L. Reprogramming wireless sensor networks: Challenges and approaches. IEEE Network, 2006,20(3): 48-55 .
[3] Hui JW, Culler D. The dynamic behavior of a data dissemination protocol for network programming at scale. In: Proc. of the 2nd ACM Conf. on Embedded Networked Sensor Systems (SenSys). ACM Press, 2004. 81-94 .
[4] Gay D, Levis P, von Behren R, Welsh M, Brewer E, Culler D. The nesc language: A holistic approach to networked embedded systems. In: Proc. of the ACM SIGPLAN 2003 Conf. on Programming Language Design and Implementation (PLDI). ACM Press, 2003. 1-11 .
[5] Mottola L, Picco GP. Logical neighborhoods: A programming abstraction for wireless sensor networks. In: Proc. of the Distributed Computing in Sensor Systems. Berlin, Heidelberg: Springer-Verlag, 2006. 150-168. [doi : 10.1007/11776178_10]
[6] Miller JS, Dinda PA, Dick RP. Evaluating a BASIC approach to sensor network node programming. In: Proc. of the 7th ACM Conf. on Embedded Networked Sensor Systems (SenSys). ACM Press, 2009.155-168 .
[7] Hossain MS, Islam ABMAA, Kulkarni M, Raghunathan V. mSETL: A set based programming abstraction for wireless sensor networks. In: Proc. of the 10th Int’l Conf. on Information Processing in Sensor Networks (IPSN). IEEE, 2011. 354-365.
[8] Hill J, Szewczyk R, Woo A, Levis P, Madden S, Whitehouse C, Polastre J, Gay D, Sharp C, Welsh M, Brewer E, Culler D. Tinyos: An operating system for sensor networks. In: Weber W, ed. Proc. of the Ambient intelligence. Berlin, Heidelberg: Springer-Verlag, 2005.115-148 .
[9] Milner R. A Calculus of Communicating Systems. New York: Springer-Verlag, 1982.
[10] Koshy J, Pandey R. Remote incremental linking for energy-efficient reprogramming of sensor networks. In: Proc. of the 2nd European Workshop on Wireless Sensor Networks. IEEE, 2005. 354-365.
[11] Titzer B, Lee D, Palsberg J. Avrora: Scalable sensor network simulation with precise timing. In: Proc. of the Int’l Conf. on Information Processing in Sensor Networks (IPSN). IEEE, 2005.477-482 .
[12] Madden SR, Franklin MJ, Hellerstein JM, Hong W. TinyDB: An acquisitional query processing system for sensor networks. ACM Trans. on Database Systems, 2005,30(1):122-173 .
[13] Yao Y, Gehrke J. The cougar approach to in-network query processing in sensor networks. ACM Sigmod Record, 2002,31(3):9-18 .
[14] Mottola L, Picco GP. Programming wireless sensor networks: Fundamental concepts and state of the art. ACM Computing Surveys (CSUR), 2011,43(3):19:1-19:51 .
[15] Chu D, Popa L, Tavakoli A, Hellerstein JM, Levis P, Shenker S, Stoica I. The design and implementation of a declarative sensor network system. In: Proc. of the 5th ACM Conf. on Embedded Networked Sensor Systems (SenSys). ACM Press, 2007. 175-188 .
[16] Koshy J, Pandey R. VMstar synthesizing scalable runtime environments for sensor networks. In: Proc. of the 3rd ACM Conf. on Embedded Networked Sensor Systems (SenSys). ACM Press, 2005.243-254 .