Scripting customized components for Wireless Sensor Networks

Adriano Francisco Branco Scripting customized components for Wireless Sensor Networks Tese de Doutorado Thesis presented to the Programa de P´os–Gradua¸c˜ao em Inform´atica of the Departamento de Inform´atica, PUC–Rio as partial fulfillment of the requirements for the degree of Doutor em Ciˆencias – Inform´atica. Advisor : Prof. Noemi de La Rocque Rodriguez Co–advisor: Prof. Silvana Rossetto Rio de Janeiro September 2015 PUC-Rio - Certificação Digital Nº 1112677/CA Adriano Francisco Branco Scripting customized components for Wireless Sensor Networks Thesis presented to the Programa de P´os–Gradua¸c˜ao em Inform´atica, of the Departamento de Inform´atica do Centro T´ecnico Cient´ıfico da PUC–Rio, as partial fulfillment of the requirements for the degree of Doutor. Prof. Noemi de La Rocque Rodriguez Advisor Departamento de Inform´atica — PUC–Rio Prof. Silvana Rossetto Co–advisor UFRJ Prof. Roberto Ierusalimschy Departamento de Inform´atica — PUC-Rio Prof. Markus Endler Departamento de Inform´atica — PUC-Rio Prof. Claudio Luis de Amorim UFRJ Prof. Bruno Oliveira Silvestre UFG Prof. Jos´e Eugenio Leal Coordinator of the Centro T´ecnico Cient´ıfico — PUC–Rio Rio de Janeiro, September 10th, 2015 PUC-Rio - Certificação Digital Nº 1112677/CA All rights reserved. Adriano Francisco Branco Adriano Branco currently is a PhD candidate of Computer Science Department at PUC-Rio. His research focus on Wireless Sensor Network (WSN) in distributed system area. He also got his master in computer science at PUC-Rio in 2011 working with WSN. He undergraduates in Electronic Engineering at CEFET/RJ in 1992. From the undergraduate course he worked as electronic engineer and system developer at CBPF/CNPq (Brazil) and CERN (Switzerland). At CPBF, in the LAFEX laboratory, he worked on the parallel computer program from Fermilab collaboration group. At CERN he spent two years working in the New Trigger Project for LEP Delphi Experiment. After that he had worked more than 12 years in system integration consulting projects (as developer and project manager) for large companies. Mainly for the Industrial Automation and Telecommunications industries, including an international project in Manila/Philippines. Bibliographic data Branco, Adriano Francisco Scripting customized components for Wireless Sensor Networks / Adriano Francisco Branco; advisor: Noemi de La Rocque Rodriguez; co–advisor: Silvana Rossetto. — 2015. 100 f. : il. (color.); 30 cm Tese (doutorado) - Pontif´ıcia Universidade Cat´olica do Rio de Janeiro, Rio de Janeiro, Departamento de Inform´atica, 2015. Inclui bibliografia. 1. Inform´atica – Teses. 2. Rede de Sensores sem Fio (RSSF). 3. Sistemas Distribu´ıdos. 4. Modelo de Programa¸c˜ao. 5. Linguagem Reativa. 6. M´aquina Virtual. I. Rodriguez, Noemi de La Rocque. II. Rossetto, Silvana. III. Pontif´ıcia Universidade Cat´olica do Rio de Janeiro. Departamento de Inform´atica. IV. T´ıtulo. CDD: 004 PUC-Rio - Certificação Digital Nº 1112677/CA Acknowledgement Thank to my advisors Prof. Noemi Rodriguez and Prof. Silvana Rossetto for their support and encouragement for this work. Thank to CNPq, PUC-Rio, and FAPERJ, for the financial support which allowed this work to be done. To my wife, who accompanied me all this time with direct and indirect support. To my parents, family and friends who supported me even with my absence in family life. To all colleagues, faculty and staff of the Department of PUC-Rio, for the fellowship, learning and support. PUC-Rio - Certificação Digital Nº 1112677/CA Abstract Branco, Adriano Francisco; Rodriguez, Noemi de La Rocque (Advisor); Rossetto, Silvana (Co-Advisor). Scripting customized components for Wireless Sensor Networks. Rio de Janeiro, 2015. 100p. D.Sc. Thesis — Departamento de Inform´atica, Pontif´ıcia Universidade Cat´olica do Rio de Janeiro. Programming wireless sensors networks (WSN) is a difficult task. The programmer must deal with several concurrent activities in an environment with severely limited resources. In this work we propose a programming model to facilitate this task. The model we propose combines the use of configurable component-based virtual machines with a reactive scripting language which can be statically analyzed to avoid unbounded execution and memory conflicts. This approach allows the flexibility of remotely uploading code on motes to be combined with a set of guarantees for the programmer. The choice of the specific set of components in a virtual machine configuration defines the abstraction level seen by the application script. To evaluate this model, we built Terra, a system combining the scripting language C´eu-T with the Terra virtual machine and a library of components. We designed this library taking into account the functionalities commonly needed in WSN applications — typically for sense and control. We implemented different applications using Terra and using an event-driven language based on C and we discuss the advantages and disadvantages of the alternative implementations. Finally, we also evaluate Terra by measuring its overhead in a basic application and discussing its use and cost in different WSN scenarios. Keywords Wireless Sensor Network (WSN); Distributed Systems; Programming Model; Reactive Language; Virtual Machine. PUC-Rio - Certificação Digital Nº 1112677/CA Resumo Branco, Adriano Francisco; Rodriguez, Noemi de La Rocque; Rossetto, Silvana. Programando redes de sensores sem fio com scripts sobre componentes customizados. Rio de Janeiro, 2015. 100p. Tese de Doutorado — Departamento de Inform´atica, Pontif´ıcia Universidade Cat´olica do Rio de Janeiro. Programar redes de sensores sem fio (RSSF) ´e uma tarefa dif´ıcil. O programador tem que lidar com v´arias atividades simultˆaneas em um ambiente com recursos extremamente limitados. Neste trabalho propomos um modelo de programa¸c˜ao para facilitar essa tarefa. O modelo que propomos combina o uso de m´aquinas virtuais configur´aveis baseadas em componentes com uma linguagem de script reativa que pode ser analisada estaticamente para evitar conflitos de mem´oria e execu¸c˜ao de la¸cos infinitos. Essa abordagem permite a flexibilidade de carregamento remoto de c´odigo nos n´os da rede combinado com um conjunto de garantias para o programador. A escolha de um conjunto espec´ıfico de componentes numa configura¸c˜ao de m´aquina virtual define o n´ıvel de abstra¸c˜ao visto pelo script da aplica¸c˜ao. Para avaliar esse modelo, constru´ımos Terra, um sistema que combina a linguagem de script C´eu-T com uma m´aquina virtual e uma biblioteca de componentes. N´os projetamos esta biblioteca considerando as funcionalidades comumente necess´arias em aplica¸c˜oes de RSSF — tipicamente para sensoreamento e controle. Implementamos diferentes aplica¸c˜oes utilizando Terra e uma linguagem orientada a eventos baseados em C. Al´em disso discutimos as vantagens e desvantagens dessas implementa¸c˜oes alternativas. Finalmente, tamb´em avaliamos Terra medindo o custo adicional em uma aplica¸c˜ao b´asica e discutimos sua utiliza¸c˜ao e custo em diferentes cen´arios de aplica¸c˜oes WSNs. Palavras–chave Rede de Sensores sem Fio (RSSF); Sistemas Distribu´ıdos; Modelo de Programa¸c˜ao; Linguagem Reativa; M´aquina Virtual. PUC-Rio - Certificação Digital Nº 1112677/CA Contents 1 Introduction 8 1.1 Research Question 8 1.2 Major problems in programming WSNs 9 1.3 Contributions 13 1.4 Document structure 13 2 Terra programming System 14 2.1 Terra basics 14 2.2 Terra in details 18 2.3 Terra Customizations 26 3 Programming evaluation 36 3.1 Execution strategy and Metrics 37 3.2 Test applications 38 3.3 App #1 - Multi-Hop monitoring & alarm 39 3.4 App #2 - Complex Grouping 50 3.5 App #3 - Topology Control Protocol 55 3.6 App #4 - Volcano Application 60 3.7 Items outside the programming evaluation procedure 65 3.8 Analysis 67 4 Cost evaluation 70 4.1 Execution strategy and Metrics 70 4.2 Test scenarios 70 4.3 Results 71 5 Related work 82 6 Final remarks 85 6.1 Main findings 86 6.2 Future work and related improvements 87 7 Bibliography 89 A Terra – complementary informations 95 A.1 Execution model example 95 A.2 Terra operation 96 A.3 Integration between script and components 97 PUC-Rio - Certificação Digital Nº 1112677/CA 1 Introduction Programming a wireless sensor network (WSN) remains a challenge. WSNs are typically composed by computing devices (motes) that communicate via radio and rely on batteries for energy. Although a whole range of microcontrollers can be used in this setting, it is very common, due to cost restrictions and scale of usage, to employ units with very limited memory and computing resources. This scarcity of resources, along with the event-oriented nature of applications and the need for coordination among large numbers of nodes, makes programming applications a difficult and error prone task (Awan et al., 2007; Kothari et al., 2007; Mottola and Picco, 2011). It is also often the case that the user must reprogram sensor network nodes after they are in place. This is hard to do physically, because in most cases it is difficult to recover the motes from the position in which they are installed. The obvious solution is to do the updates through radio messages; however, transferring complete binaries over radio can lead to high energy consumption, and is thus undesirable. On the other hand, because of their restricted resources and deployment characteristics, a given sensor network is normally used for a single category of application, such as environment control or building security, even if the application itself evolves over time. This indicates that a small set of coordination and processing patterns can support all of the applications that a sensor network must run along its lifetime. 1.1 Research Question We believe that WSN programming environments can benefit from commonality not only inside a single application area. Programming patterns such as collecting values to a base station or broadcasting them to the whole network are recurrent in different application areas, with variations regarding issues of reliability or security. So we discuss an approach in which common programming patterns are designed and implemented separately as a component-based virtual machine. These components may be combined as needed, creating customized virtual machines with abstractions provided by the component interfaces. As discussed by Ousterhout (Ousterhout, 1998), scripting languages enforce a programming model that glues components PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 1. Introduction 9 together to create powerful applications in a few lines of code, We thus propose the use of a scripting language with support for several of the problems encountered in WSNs. This makes them suitable for creating programs that benefit from the pre-defined and pre-installed set of components and that can be easily sent over the network. We argue that this model, based on virtual machine and combining a reactive scripting language with a set of customized components, is highly convenient for use in WSN. We formulated the following as research question for this thesis: To what extent can a programming environment based on the combination of a reactive high-level scripting language with safety guarantees with a virtual machine that encapsulates customized components facilitate the task of programming WSNs, providing abstractions to simplify programming, reducing the possibility of errors, and allowing reprogramming? To investigate this idea we built Terra, a flexible system that targets both WSN programmer experts and application programmer. The application programmer benefits from a high-level programming environment where the WSN programmer expert may easily integrate new operations as needed. The system uses virtual machines which embed these new operations as components and facilitate remote distribution of scripts with low energy consumption. Our scripting language is based on the reactive programming language C´eu (Sant’Anna et al., 2013). In the next section we describe some typical difficulties in building distributed systems and event-driven programming in WSNs projects. 1.2 Major problems in programming WSNs Probably, the major concern in WSN systems is with energy consumption. An approach to reduce this consumption is to put the CPU in sleep mode during idle state and waits for a hardware interruption to wake up the CPU. For example, a sensor converts some physical unit to a voltage value and the microcontroller uses its analog to digital converter (A/D) to read this voltage value. In general, this operation interacts with the CPU in two points, first the CPU starts the conversion and second the converter signals an interruption to indicate a valid value to be read. During this two points, probably, the CPU may be idle and may stay in sleep mode to save energy. The interruptions are also used in timers, radio interface and data memory chip. Depending of the application, a WSN node may be in idle mode during long time. For example, a periodic monitoring application may wake-up the CPU each hour. The event-driven programming model is very suitable to this execution PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 16 interface must implement its commands and may signal its events. This model allows for different implementations of the same interface, facilitating system configuration for different platforms. TinyOS provides a library of components and some tools that simplify the task of building new applications. TinyOS does not work as a conventional operating system which runs user applications, but rather as a library that must be linked to these applications to build a single executable program. This executable must be loaded into the WSN mote. TinyOS implements a task queue to support nesC task management. In TinyOS, each task runs to completion, one at a time. In that way, only an interruption handler may run concurrently with a task. Typically the interruption handler posts a task to the scheduler as soon as possible, to avoid conflicts. When the task queue is empty, TinyOS keeps the CPU in sleep mode to save energy. The use of the nesC component model facilitate modularity, allowing TinyOS to have equivalent components to access different types of hardware. The selection of suitable components for each hardware is done during the build process and is transparent to the user. In addition to the tools to compile and load programs, TinyOS provides the TOSSIM tool (Levis et al., 2003) for network simulations. 2.1.2 The C´eu programming language C´eu (Sant’Anna et al., 2013) was originally developed as a compiled language, and has bindings1to Arduino2, to the TinyOS environment, and to SDL3running in conventional computers (Linux, Windows, and Mac OS X). C´eu is a reactive language strongly influenced by Esterel (Boussinot and Simone, 1991). C´eu provides a parallel construct and a blocking await statement that allows programs to handle multiple events at the same time. In contrast with standard split-phase event-based systems, such as nesC (Gay et al., 2003) and Contiki (Dunkels et al., 2004), C´eu can keep sequential and separate lines of execution (trails) for each activity in the program. Trails in C´eu are guided by reactions to the environments. Furthermore, the extra support for parallelism provides precise information about the program control flow to the C´eu compiler, enabling a number of static safety guarantees, such as race-free shared-memory (Sant’Anna et al., 2013). 1http://ceu-lang.org/ 2Arduino open-source microcontroller platform (https://www.arduino.cc/) 3SDL - Simple DirectMedia Layer (http://www.libsdl.org/) PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 17 Programs in C´eu are designed by composing blocks of code through sequences, conditionals, loops, and parallelism. The combination of parallelism with standard control flow enables hierarchical compositions, in which selfcontained blocks of code can be deployed independently. To illustrate the expressiveness of compositions in C´eu, consider the two variations of the structure in Figure 2.2. loop do par/and do <...> with await 1s; end end loop do par/or do <...> with await 1s; end end Figure 2.2: Compositions in C´eu. In the par/and loop variation, the code block in the first trail (represented as <...>) is repeated every second at minimum, as the second trail must also terminate to rejoin the par/and primitive and restart the loop. In the par/or loop variation, if the code block does not terminate within one second, the second trail rejoins the composition (canceling the first trail) and restarts the loop. These structures represent, respectively, sampling and timeout patterns, which are typically found in WSN applications. Scripts in C´eu follow the synchronous concurrency model, that is, reactions to input events run to completion and never overlap: in order to proceed to the next event, the current event must be completely handled by the script. To ensure that scripts are always reactive to incoming events, the synchronous model relies on the guarantee that a reaction always executes in bounded time. The C´eu compiler statically verifies that programs contain only bounded loops (i.e., loops that contain an await statement in every possible execution path) (Sant’Anna et al., 2013). Even though C´eu supports multiple lines of execution, accesses to shared memory are safe. Because programs can react to only one component-triggered event at a time, the C´eu compiler also performs a flow analysis to detect concurrent accesses (Sant’Anna et al., 2013): if two accesses to a variable can occur in reactions to the same event and are in parallel trails, then the compiler issues an error message. As a trade-off for safety, the C´eu design imposes limitations on language expressiveness; it is not possible to program computationally-intensive operations and hard real-time responsiveness, possibly making it hard to program low level code such as radio protocols (Sant’Anna et al., 2013). In the original PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 18 language, the programmer can resort to C for this tasks, but this means loosing the safety guarantees. 2.2 Terra in details In this section we describe in more details the Terra programming system. Branco and others (Branco et al., 2015) describe a previous version quite close to the this one. Figure 2.3 shows the Terra application life cycle. The C´eu-T program is compiled and checked statically in the user computer to generate the virtual machine bytecode. The user then transfers the generated bytecode to the motes in the network and the virtual machine runtime, previously installed, executes the bytecode. In this version of Terra the same bytecode is loaded in all nodes. The only part of scripts that escapes static analysis are calls to components provided by Terra’s VM, which are encapsulated in modules and have been extensively tested beforehand. In this way, Terra strives to provide adequate abstractions while providing a safe execution environment and allowing remote program update. Figure 2.3: Terra application life cycle: compilation and execution. 2.2.1 C´eu-T scripting language For the use of C´eu in Terra, we implemented a new variation of the language that generates code for VM-T. C´eu is originally compiled to C and C´eu scripts can include chunks of C code, however, any call to C is exempt of verification. In Terra, we want only the VM components to escape the safety analysis, so we took out the facility to include arbitrary C code, but we did PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 19 maintain all of C´eu’s original control structures. The C´eu-T language inherits almost all characteristics of C´eu 0.3 version4discussed in section 2.1.2, and its implementation inherited all the safety checks from the original compiler. Because C´eu relies on C for typing, function calls, event operations, and expressions, we had to extend C´eu-T to include these language elements. Figure 2.4 shows these compilation differences. Figure 2.4: Ceu x Terra In Terra, the C´eu-T language is used only to glue components written in nesC/TinyOS. All virtual-machine code and low-level components rely on the TinyOS architecture. C´eu-T and components in the VM-T communicate through system calls,output events and input events. System calls and output events cross the script boundary towards the VM components, while input events go in the opposite direction, crossing the VM boundary towards the script. In the C´eu-T implementation, the system calls provided by Terra are the only way to escape this verification. Because only the system calls that are part of component interfaces are available, it is feasible to ensure that these run in bounded time (e.g., do not contain recursive calls and infinite loops). To allow the configuration of these events and system calls we extended the C´eu-T language with a special syntax for a configuration block, as detailed in the Appendix section A.3 Integration between script and components. The type system for WSN applications is, in general, very simple. Besides the basic integer types, we need some kind of data structures to exchange data with the customized components. For example, to send a radio message we need to populate the data message, and this data structure may be different 4Terra is based on the previous version 0.3 of C´eu (Sant’Anna et al., 2013). PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 20 depending on the application. The type system we developed and the facilities for defining data structures are explained in the subsection Types and data structures. Types and data structures In C´eu, data definition and manipulation relies on the use of C. For C´eu-T, we defined a basic type system that includes integer values with 8, 16, and 32 bits and float values of 32 bits. Pointer types are not allowed for safety reasons. The basic types supported by C´eu-T are: byte,short,long,ubyte, ushort, and ulong – respectively 8, 16, and 32-bit signed and unsigned integers and float. But we need more complex data structures to use in the interfaces between the user C´eu-T script and the VM components. For that, we define three types of data structures – one-dimension arrays, registers and packets. Onedimension arrays are defined as a basic type within a dimension. Listing 2.1, in line 3, shows an example of one-dimension array with five ubyte elements. Aregtype declaration creates new register type. A register can only have fields that are values of basic types or arrays of basic types. Listing 2.1 (lines 5–11) shows an example of register declaration and use. We also defined a packet declarations for partial predefined structures. This kind of data structure is useful when a component interface needs to specify some fields and the user can define other fields as needed. A typical example of packet use is in the radio message interface, where some fields are mandatory, such as message type and target node, and other fields depend on the application needs. The packet command declares a new abstract register type which must contain, at least, a field of a special type called payload and its length in bytes. Later on, during application writing, the pktype declaration may be used to create a new register type based on the abstract register. In pktype declaration the user must specify at least one basic type field or array field for the abstract packet register’s payload. The only restriction is that the sum of bytes of all user-defined fields can not exceed the payload length defined by the packet command. Listing 2.1 (lines 13–27) shows an example. The packet declarations can be used only in the configuration block as its use is intended to the developer of the customization. C´eu-T type system has simple rules for expressions. Assignments of integer values to any integer variable are allowed and, if necessary, automatic type casting occurs. Assignments of integer to float or float to integer are also allowed and, if necessary, automatic type casting occurs. In expressions, math operations with at least one float operand will be evaluated converting all PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 21 operands to float. In all other cases, the operation will be done with integers. Each automatic type casting generates a compile-time warning. A register value can be assigned only to another identically-typed variable. The integer and float assignment rules are also applied to arguments of functions and events. A register argument is always passed by reference and an additional rule verifies the compatibility between the packet type and the register type. The end of Listing 2.1, lines 30–34 show examples of valid assignment for the variables, array, and register defined in the previous rows. Listing 2.1: Examples of the Terra type system implementation 1var us ho rt nodeId ; // Simple i n t e g e r var 2var f l o a t average ; // Simple f l o a t po i nt var 3var us ho rt [ 5 ] sensorReads ; // Array var 4 5re gt ype myData with // R e g i s t e r type 6var ubyte sequence ; 7var us ho rt nodeID ; 8var ushort sensorValue ; 9end 10 11 var myData sensorData ; // R e g i s t e r var 12 13 // Abstr ac t r e g i s t e r type 14 packet radioMsg with 15 var ubyte msgId ; 16 var us ho rt t a r g e t ; 17 var payload [ 2 0 ] data ; // 20 bytes 18 end 19 20 // R e g i s t e r / packet type 21 pktype userMsg of radioMsg with 22 var ubyte seq ; 23 var us ho rt s ens o rVa l ; 24 end 25 26 // R e g i s t e r / packet var 27 var userMsg sendMsg ; 28 29 // Val id a t t r i b u t i o n examples 30 nodeId = 5; 31 average = nodeId / 2 . 0 ; 32 sensorData . se nsorValue = sensorReads [ 0 ] ; 33 sendMsg . t a r g e t =1; 34 sendMsg . s ens orV a l=sensorData . sensorValue ; PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 22 2.2.2 Terra Implementation A C´eu-T program is compiled to a bytecode file that can then be disseminated to the network nodes, where it is interpreted by the VM-T, which implements the bytecode interpreter, the execution model, the code dissemination service, and some specific customized components. In the next subsections we present the C´eu-T compiler, the componentbased VM-T architecture, and the bytecode dissemination algorithm. In the Appendix A.2 we present the basic operation process. The C´eu-T Compiler The implementation of the C´eu-T compiler is based on the C´eu compiler implementation. The compiler was written em Lua programming language and uses the LPeg library (Ierusalimschy, 2009) for pattern-matching. From this base implementation we inherit all the static checking. The compiler checks scripts for non-deterministic memory accesses and tight loops (loops without awaits), and others properties, such as whether all possible block cancellations are correctly captured. Also, the compiling process uses the C preprocessor (cpp) to allow inclusion of header files, macro expansions, conditional compilation, and line control. The main modifications for C´eu-T are the types and the configuration block described in section 2.2.1 and the bytecode generation. Other modifications include the addition of expression operations, as C´eu relies on the C compiler for expressions, and some checks and code optimizations. The absence of pointers in the C´eu-T type system avoids all kind of references to external variables and also avoids memory leaking. Checking types on assignments further enhances safety. Terra has a hybrid set of instructions with some opcodes using a stack and other opcodes using arguments. Most opcodes accept variable-sized arguments. We choose to use a stack-based architecture because of its smaller code size in comparison to register-based architecture (Gregg et al., 2005). Since memory is a limited resource, it is important to reduce the bytecode program size. In Terra all script variables are statically arranged in the program memory and the stack is used only for expression operations. Some assignment instructions access directly the memory variables and the push/pop instructions put and get values into/from the stack. All expression operations are evaluated using the stack. During code generation the compiler checks for code size optimization opportunities. Whenever possible, code generation prioritizes PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 23 accesses to memory instead of use of stack. Expressions with binary operations like sum or minus always need to use the stack. Listing 2.2 shows an example of optimization for a simple assignment like v1 = v2;. Considering both as short type variables and with the memory address bellow 256 (i.e needing only 1-byte for address). In this example, the first part (lines 2–8) pushes to the stack two 16 bits addresses for each variable and, the last instruction, pops these addresses to copy the contents of one address to the other address. The second part (lines 12–14) uses only one instructions that does all work without using the stack. In this case using addresses of 8 bits. In this example, the optimization changes from seven bytes of non-optimized code to three bytes of optimized code Listing 2.2: A code optimization example. 1/∗∗∗ Not optimized and u si ng s ta ck ∗∗∗/ 2push &v2 : opcode 3: addr2Low 4: addr2High 5push &v1 : opcode 6: addr1Low 7: addr1High 8s e t s h o r t : opcode 9t o t a l of 7 by te s of code + 2 s ta ck word (8 b yt es ) 10 11 /∗∗∗ Optimized ∗∗∗/ 12 s e t s h o r t &v1 , &v2 : opcode 13 : addr2Low 14 : addr1Low 15 t o t a l of 3 by te s Another kind of optimization is to reduce the path to terminate hierarchical blocks. For example, in the follow code: 1i f x do 2<do something> 3i f z do 4<do something> 5i f w do 6<do something> 7end 8end 9end At the end of the most inner block, the compiler generates a instruction to jump to the end of the middle block, where the compiler also generates a instruction to jump to the end of the outer block. In this case the most inner PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 24 block may have a instruction to jump directly to the end of the most outer block. VM-T architecture The Terra virtual machine (VM-T) is composed by three modules as shown in Figure 2.5. The interfaces between modules or sub-modules are indicated by arrows. Figure 2.5: VM-T modules The VM module is the main module. It provides an interface for receiving new application code from the Basic Services module (Code Upload interface) and three interfaces for customized events and functions (outEvt, function, and inEvt interfaces). The Engine submodule controls the execution of code interpreted by the Decoder submodule and handles external events received from the Event Queue submodule. As the VM-T is implemented using TinyOS, each task runs to completion in a single-threaded model, guaranteeing race-free conditions over application trails and embedded operations. The only exception are the interrupt-handlers, which must be isolated in the low-level functions. Terra uses a similar control for trail execution that C´eu uses to maintain execution guarantees. Basically the application program is broken in execution trails, each trail has an address as entry point and an end opcode at the end. For example, a simple block with a command await is broken in two trails. The beginning of the block is the first entry point and the position after the await command is the second entry point. The runtime maintains a set of slots to execute entry points. When an event is received, the engine scans all slots to execute, one by one, all trails that were awaiting this event. Appendix A.1 presents the C´eu-T code and the assembler code for this example. The Basic Services module controls the communication primitives to give support to code dissemination (Code Upload interface) and to the custom components module interface (Comm. interface). The Upload Control submodule controls the dissemination protocol and loads code into VM program memory. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 25 The Custom Comm submodule has a generic interface to support new communication protocols defined at the Custom Components module level. All communication protocols implemented in Terra aim to be operational with no intention of implementing the most optimized algorithms. The Custom Components module implements specific flavors of Terra. The developer of new customization needs only to implement the custom events and functions inside this module and write the equivalent configuration file to be used by a C´eu-T script. It is possible to start from a very basic customization of Terra to include the new events and functions. Currently, an output event returns a void value. These events have one argument of any type, including void, a basic type address, a register, or a packet. Because this argument is passed to the VM-T interpreter as an instruction parameter, constants and variables are passed by value and registers and packets are passed by address. The custom component that implements the output events must handle correctly each argument. Custom functions may have none or many arguments. Arguments can be basic types, basic type addresses, registers, or packets. All arguments are passed via stack and the custom operation must pop from the stack exactly the number of arguments defined in the configuration block. A custom function must always return a basic type value by pushing it back to the stack. The use of the stack for the returned value is important to enable the use of functions inside expressions. An input event may be defined to return a basic type value or an address. In all cases, the returned data is copied directly to the memory location defined in the assignment operation. In the case of an address value, the custom operation must pass the internal buffer address that holds the data. Because this operation does not use the stack, input events can not be used inside expressions. Bytecode dissemination algorithm This Terra version disseminates the same bytecode to all nodes in the network. We assume that bytecode dissemination starts on a computer connected to a basestation node via wired interface. The VM-T runtime includes a dissemination algorithm that floods code blocks into the network. Each block goes as a wave. The basestation starts the code dissemination process with a newProgramVersion message and next sends the bytecode blocks. Each node forwards each incoming message to its neighbors (all nodes at 1-hop radio range). All messages carry a version number and a sequence number to allow individual nodes to identify when it is a new program version. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 32 each group. The script starts an aggregation operation by emitting the output event AGGREG with the specific aggregation identifier as parameter. When the aggregation is completed, this is signaled by the AGGREG DONE event. As in the Group Management component, Terra maintains all the configuration parameters of aggregation in a data structure that can be modified at any time. The program in Listing 2.5 illustrates the use of the aggregation facilities. In lines 1–2, a new group (gr1) is created. A single leader will be automatically elected for that group. At each node, the id of the group’s leader will be stored in gr1.leader. In lines 3–4, a new agregation (agA) is created by invoking the system call aggregInit(). This aggregation will be associated with the gr1 group (the second argument). The third and fourth arguments to aggregInit() define the sensor to be read (temperature in this case) and the aggregation operation to be applied (average). The next arguments define a relational operator (GTE, for greater then or equal) and the reference value (not used in this case). Line 11 uses a predefined data structure type that will hold the result of the aggregation operation. In lines 15–16, the leader node starts the aggregation operation by triggering the AGGREG output event (emit AGGREG()). (Non-leader nodes will transparently react to the messages triggered by the aggregation.) In line 17, the leader node waits for the end of the aggregation and assigns the result to data. Next, it assigns this value to the data field in dataMsg and, in line 19, sends the message to the base station, illustrating the use of the output event SEND BS. The use of this event is similar to that of the SEND GR event, but in this case msgBS t type does not have predefined field grId. Listing 2.5: Aggregation and communication example in Terra. 1var group t gr1 ; 2g r o u p I n i t ( gr1 ,1 , 0 ,2 ,TRUE, eACTIVE , 0 ) ; 3var a ggr e g t agA ; 4a g g r e g I n i t (agA , gr1 , SID TEMP , fAVG , opGTE , 0 ) ; 5 6pktype msg from msgBS t with 7var ulong average ; 8end ; 9var msg dataMsg ; 10 dataMsg . msgId=1; 11 var aggDone t data ; 12 13 loop do 14 await 10 s ; 15 i f ( getNodeId ( ) == gr1 . l e a d e r ) then 16 emit AGGREG(agA ) ; PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 33 17 data = await AGGREG DONE; 18 dataMsg . average = data . val ue ; 19 emit SEND BS( dataMsg ) ; 20 end 21 end 2.3.3 Terra Volcano - CPU Intensive Operation Volcano is an application that uses WSN as a cheap alternative for traditional volcanic instrumentation. The application was built in nesC/TinyOS and is detailed by Tan5(Tan et al., 2010; Tan et al., 2013). The main idea is to reduce raw data transmission doing some in-network signal processing. In the laboratory version, that we had access, the application maintains real data in the node flash memory and emulates a seismic sensor that reads these data as streams. In our TerraVolcano customization, we break the Volcano application into five functions: Mean, Seismic Energy, Energy Scale, Copy Buffer, and Detect. The Mean operation computes the intensity mean of valid values of the raw data from seismic sensor. The Seismic Energy operation computes the seismic energy considering the intensity mean. The Energy Scale operation finds the scale of the energy computed. The Copy Buffer operation fills a five stage buffer with data to be used in Detect operation. The Detect operation includes the Fast Fourier Transform (FFT) and the seismic detection algorithm. Additionally, this customization offers an interface to read seismic data as a stream and a storage interface to load the Gaussian data model used in the detection algorithm. This kind of application needs a lot of memory to accommodate all data vectors. The original work uses the TelosB mote with 10kB of RAM and 48kB of ROM. In our case, combining the Terra Virtual Machine code with the Volcano components overflows the available ROM space of the TelosB. Our alternative was to exclude some basic functionalities from Terra to be able to add Volcano operations. In the evaluation, in section 3.6, we present an use case for Volcano application. 2.3.4 Terra memory usage Traditional WSN platforms impose an architectural restriction where the microcontroller has, at least, two types of memories. The equivalent to 5We thank the authors for making the source code available. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 34 the ROM (Read-Only Memory) where the machine code to be executed is written and the RAM (Random Access Memory) where the program variables, runtime controls, and the execution stack are stored. Using the virtual machine approach, we have to load and execute the VM-T runtime in ROM space and allocate part of the RAM memory to load the script bytecode and variables. Besides the VM-T runtime needs some RAM space for its execution. As we increase the embedded custom components, the use of ROM and RAM, by VM-T, is also increased. Consequently, the memory space for the C´eu-T script decreases. Some hardware platforms have memory limitations that may restrict the use of specific configurations. Table 2.1 presents the Terra memory configuration for different hardware platforms. Table 2.1: Terra memory usage Customization Memory MicaZ Mica2 TelosB TerraNet ROM 40.0k 37.3k 35.0k RAM 3.6k 3.5k 7.5k TerraGrp ROM 55.3k 52.4k 47.1k RAM 3.6k 3.5k 7.8k TerraVolcano ROM — — 45.2k RAM — — 8.4k Units in bytes The ROM utilization depends on the CPU type and the specific TinyOS component implementations for each hardware. The RAM value represents the memory used by variables in VM-T and in TinyOS, including the total memory allocated for the C´eu-T script. This is not the full RAM size because we need to leave some memory for the C stack. Table 2.2: C´eu-T script memory size Customization Platform Script max size TerraNet mica2/micaz 2,000 telos 7,500 TerraGrp mica2/micaz 768 telosb 4,800 TerraVolcano telosb 2,668 Units in bytes When writing a C´eu-T program, it is important to verify the amount of memory used. Table 2.2 shows how much of C´eu-T script memory is left to the application programmer in each of the customizations we explored. For example, TerraNet on MicaZ has about 2,000 bytes for the C´eu-T script program, but TerraGrp has only 800 bytes on the same platform. This PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 2. Terra programming System 35 happens because the TerraGrp components use more RAM than the TerraNet components, consequently leaving little memory to the user script. Because the radio of MicaZ and TelosB are fully compatible, it is possible to have a heterogeneous network using the same Terra customization. In this case, because the Terra interface is the same for all nodes, it is possible to run the same C´eu-T script on all network nodes. PUC-Rio - Certificação Digital Nº 1112677/CA 3 Programming evaluation In this part of the evaluation, we built and evaluated different types of applications using different abstraction levels. For example, the script application can use a specific component that offers a ready-to-use complex routing protocol or can use another component that offers a set of basic communication operations, leaving to the application programmer to implement his own routing protocol. Another example is the use of pre-defined calculation components like a Fast Fourier Transform (FFT), instead of providing the programmer only with basic math functions. We next recall the list of programming issues defined in Section 1.2.1. In the next section, we defined a set of metrics that were used to evaluate the role of Terra in resolving these issues. A. Programming complexity A.1. Sequential and event-driven programming A1.i. Learning curve A1.ii. Split phase A1.iii. Global variables A.2. Local starvation A.3. Invalid pointers B. Networking complexity B.1. Radio operations B.2. Communication protocols Our main evaluation procedure doesn’t cover three items from this list: learning curve, local starvation, and invalid pointers. In the end of this chapter we present our analysis and discussion for these three remaining items. Although most of the cost evaluation is left to the next chapter, we took the opportunity to measure the size of the codes used in the programming evaluation to identify the code dissemination cost. The next sections detail the evaluation process, presenting the execution strategy, the experiment metrics, the test applications, and the execution of the evaluation. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 37 3.1 Execution strategy and Metrics In most of our tests, we built two versions of an application: a reactive one, using Terra and the C´eu-T programming language, and an event-driven one, using TinyOS (Levis et al., 2004) and the nesC (Gay et al., 2003) programming language. We compared the applications built for the two environments and, in some cases, we compared different applications for the same environment. Table 3.1 contains the metrics we selected for our evaluation. This selection determined the data we gathered. Table 3.1: Programming – evaluation metrics Metric Description Program lines Number of lines in a program. Bytecode size Script bytecode in bytes. Machine code size Machine code in bytes. Code blocks Number of code blocks to be disseminated. Global variables Perception of explicit and implicit global states variables. Distributed system concerns Problems found during programming and debugging. Abstraction level Positive and negative points using different abstraction levels. The program lines is a traditional metric to measure program size and complexity. Although this metric considers blank lines and comments, it is important in counting the total effort to produce the code. The C´eu-T script bytecode size and the TinyOS machine code size indicate the program size to be loaded. In our case, we are interested in the amount of code blocks that must be disseminated on the network for remote installation. The global variables are the use of global variables to maintain the program state. This is a key feature used in event-driven programming because it is not possible maintain the local state between two independent events. Protothreads (Dunkels et al., 2006) and C´eu (Sant’Anna et al., 2013) also used similar metrics in its evaluation. In Protothreads, the authors focus on reducing the number of explicit state machines and events. In C´eu, the authors focus on reducing the global variables. The distributed system concerns and the abstraction level are qualitative metrics to identify significant points to our evaluation. These points appear in our evaluation text as different items depending on each test variation. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 38 3.2 Test applications We define four test applications to analyze abstraction level and code complexity. These applications were specially selected so as to exercise different system/network execution models. To maintain a certain degree of impartiality we used WSN applications from the literature in two of four test applications. Also, all applications were tested on real motes. Table 3.2 shows the environments considered in our tests and Table 3.3 describes the application functionality for each test. Table 3.2: Execution environments Prog. model Environment Description Event-driven TinyOS Low level code environment. Reactive TerraNet Environment with low level abstraction. TerraGrp Environment with high-level abstraction. TerraVolcano Environment with an abstraction of intensive use of CPU. Table 3.3: Applications # Application Description 1 Multi-Hop monitoring & alarm A monitoring and alarm application with multi-hop network topology. Requires routing protocol to send messages to base-station. (#1a. Using its own routing script and #1b. using the TinyOS CTP routing component) 2Complex Grouping A monitoring and alarm application for different spaces and with multi-hop network topology. Requires routing protocol to send messages to base-station and local group communication protocol. 3 Topology Control protocol A topology control support that actively varies the radio transmission power to discover the lower energy consumption path. 4Volcano Application High processing application to monitor volcanos. Application #1a, Multi-Hop monitoring & alarm, is a typical WSN application in which the programmer needs to deal with a simple routing protocol. It is a simple application, but exemplifies a network model very commonly used in WSN application. As alternative test application (#1b) we use the routing abstraction CTP (Gnawali et al., 2009) supplied by TinyOS. In this test it is possible to compare the implementation and the execution of a simple abstraction. Also it is possible to compare the same application using different abstraction levels. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 39 Application #2, Complex Grouping, exercises a more complex programming pattern where the programmer deals with network subgroups, coordinator nodes, and also with a routing protocol. In this case, the grouping control must be implemented from scratch in the low abstraction level environment of TinyOS. This application is very important for understanding the impact of using a high-level abstraction. Application #3 is a topology builder based on radio transmission power that was implemented by Auza in his master thesis (Auza, 2013; Auza et al., 2014). This application allows us to evaluate the use of Terra for writing more complex network protocols. Application #4, Volcano, is a CPU-heavy application built in nesC/TinyOS to support in-network collaborative signal processing algorithms in the Volcano experiment as defined by Tan (Tan et al., 2010; Tan et al., 2013). This is an application that stresses the limitations of Terra as to program memory size and processing capacity. Also, it allows us to work at a very high abstraction level and to experiment with scripts that uses higher or lower-level constructs. Table 3.4 shows each test application and the respective execution environment. Table 3.4: Applications X Execution environments (Abstraction level) Application TinyOS Terra Net Terra Grp Terra Volcano Multi-Hop monit. & alarm 1a + 1b 1a 1b Complex Grouping 2[∗]2 Topology Control 3 3 Volcano 4 4 [∗]- only pseudocode for TinyOS version. 3.3 App #1 - Multi-Hop monitoring & alarm We implemented two variations of application #1. The first one (#1a) implements its own algorithm for message routing and the other one (#1b) uses CTP (Gnawali et al., 2009), a message routing protocol already implemented in the TinyOS. We compare these two applications using two programming models: event-driven and reactive. For the event-driven model, we built #1a and #1b applications using nesC/TinyOS. For the reactive model, we use two flavors of Terra, TerraNet in application #1a and TerraGrp in application #1b. While TerraNet doesn’t include any support for message routing, TerraGrp includes the CTP routing abstraction. These applications allow us to examine PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 40 the use of different abstraction levels. At the end of this section we present the results of the Terra version applications running in a network of 14 real nodes. 3.3.1 App #1a - programming the routing algorithm In this application, each node periodically sends its temperature to the central computer (via base-station node). Nodes also send an alarm message when the temperature value exceeds a predefined value. The alarm check period must be much smaller than the monitoring period, to allow a fast reaction. Communicating with the central computer requires support for message routing from any network node to the base-station node. Our routing solution is based on a spanning tree in which the root node may be the base-station node or any node in the radio range of the basestation. The root node starts a flooding message that is repeated by all nodes on a best-effort basis. A parent node is defined by the first message received, and nodes must repeat only this first message. For simplicity, we are ignoring failures. During the monitoring operation, after the tree construction process, a node sends the reading or alarm messages to its parent node. All nodes must redirect the received messages to their parent node. The root node must redirect the received messages to the central computer via the base-station node. To have a minimal guarantee of message delivery, the send and receive operations must implement an acknowledgement protocol and avoid message duplication. The send operation must implement an output buffer to avoid loss of message caused by concurrency in the radio service. Because this test is the first one in our text, we present some general considerations about comparing an application built with an event-driven model and with a reactive model. Listings 3.1 and 3.2 shows the pseudocodes for a simplified version of our test application. The event-driven programming model is represented here by the nesC language and the reactive programming model is represented by the C´eu-T language. These pseudocodes don’t contain the code for message queues, message retries, and duplicated-message checks. In the nesC program version, as in traditional event-driven programs, the code is split into several nesC event procedures (callbacks or event handlers). In nesC we use call to request a command and event to define an event handler, while in C´eu-T we use, respectively, emit and wait. To the nesC application code it doesn’t matter where an event handler is positioned in the text. The idea is that an event procedure is always ready to be called and its execution condition is controlled by the user code, via global variables. This kind of combination, considering global variables and event procedures, PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 41 amplifies possible valid and invalid control combinations that the programmer must be aware of. This situation complicates program debugging and test cases creation, and also creates an error-prone environment. On the other side, C´eu-T enables writing a more structured program in which the programmer may combine sequential and parallel structures. This approach also allows creating different operation stages. For example, it is possible to enable or disable an event handler depending of program flow. Listing 3.1 presents the nesC pseudocode version. Although we differentiate the pseudocode in two parts, all events are defined for the same execution context. The C´eu-T version presented in the Listing 3.2 has two explicit execution contexts. The first stage is executed before the second stage. This kind of separation avoids context mixing and is important to simplify the number of possible control combinations. Also, using parallel structures to separate concurrent contexts reduces possible conflicts in global variables. Listing 3.1: The nesC pseudocode for the test application #1a. 1hasParent = f a l s e 2alarmMute = f a l s e 3 4: f i r s t pa rt −Build ad−hoc t r e e 5event booted 6s t a r t r a d i o 7event r a dio s t a r t e d 8i f r oo t node then 9broad ca st d i s c o v e r message 10 event d i s c o v e r message 11 i f hasParent i s f a l s e then 12 hasParent = tr u e 13 broad ca st d i s c o v e r message 14 s t a r t data p e r i o d i c timer 15 s t a r t alarm p e r i o d i c timer 16 s t a r t mo nitoring p e r i o d i c time r 17 18 : second p ar t −monitoring f u n c t i o n a l i t y 19 event alarm ti mer 20 read s ens o r 21 event s enso r done 22 i f i s an alarm and alarmMute i s f a l s e 23 alarmMute=t r u e 24 s t a r t mute ti mer 25 send alarm message to parent node 26 event mute time r 27 alarmMute = f a l s e 28 event data timer 29 send data message to parent node 30 event data message PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 48 Table 3.6: Terra: No CTP X CTP Metric no CTP CTP Program lines 199 63 Bytecode size (bytes) 650 189 Machine code size (bytes) 40,000 55,300 Code blocks 28 9 Table 3.7: TinyOS: No CTP X CTP Metric no CTP CTP Program lines 307 224 Machine code size (bytes) 15,566 21,548 Code blocks 649 898 was, respectively, 75 and 46 lines for the version without CTP and 17 and 16 lines for the version with CTP. This means that, in Terra, using a highlevel abstraction not only reduces code size but also reduces the proportion of number of commands to the number of flow control statements. If we compare both nesC versions, we find that the number of lines doesn’t change as much as in the Terra version. The nesC version without CTP has about 1.4 times more lines than the version with CTP. This means that the use of the CTP component in TinyOS had low impact when we look at the full application code. On the other hand, the TinyOS implementation of the CTP increases the machine code size for Terra and TinyOS. Thus, the ratio between the machine code of the TinyOS version and the bytecode of the Terra version jumps to 114. This was only 24 in the version without CTP. The Terra version without CTP represents an increase of 3.4 times the bytecode size when compared to the version with CTP. The TinyOS version without CTP represents a decrease of 0.72 times the bytecode size when compared to the version with CTP. This difference, comparing the two version in TinyOS, is due to the fact that the TinyOS CTP implementation considers radio link quality and message buffering to offer much more guarantees than our nesC flooding algorithm and this reflects directly on bytecode size. Because the CTP is already embedded in the Terra runtime, and is sent along with the application in the case of TinyOS, this difference reflects in the dissemination cost. In this case the TinyOS version spends 100 times more energy than the Terra version. The results for global variables are similar to those of the first test. As expected, the main difference is that now the code uses fewer globals. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 49 3.3.3 Real motes experiment This experiment uses a network of real motes to evaluate the execution of the two Terra versions – applications #1a and #1b. To identify the routing tree topology, we add in the data message of each application the parent of the node considered in the routing tree. Our experimental test uses the C´eu na Terra1testbed, a testbed for WSN experiments built with the support of RNP. We use a network with 14 MicaZ motes distributed under the desks of a classroom. The nodes are identified from 4 to 17. The output of our experiment is the topology tree formed for each application, #1a using its own routing tree algorithm and #1b using the embedded CTP component. We also register, for each node and cycle, the node messages received by the basestation during 5 minutes of test. Considering a data cycle of one minute, we can receive at least five messages for each node. Node 8 is configured as the Terra basestation and does not execute the C´eu-T script. This node is used only to interconnect the radio network with the USB serial interface of our conventional computer. In application #1a we defined, in the C´eu-T script, node 9 as the root node and, in application #1b, the CTP component also uses node 8 (basestation) as the root node. Figures 3.1 and 3.2 present the routing tree topology formed for the two applications. We colored in gray the nodes that were not discovered in the routing tree building process. Figure 3.1: Tree topology formed for the application #1a Table 3.8 presents, for Apps.#1a and #1b, the parent node for each node. We present only one data cycle because all cycles have the same values. We have empty values for node 8 because this node works as basestation and 1Ce´u na Terra Testbed – http://ceunaterra.voip.ufrj.br/ PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 50 Figure 3.2: Tree topology formed for the application #1b doesn’t run the application. In application #1a, nodes 11 and 17 were left outside of the tree, probably because of the default radio transmission power used in Terra. In the case of application #1b, the CTP component has a more complex algorithm that considers the link quality to build the tree. Table 3.8: Received parent node for each node – Apps.#1a and #1b node Id App.#1a App.#1b 4 9 8 5 9 8 6 9 8 7 9 8 8 9 8 8 10 9 8 11 - 8 12 9 16 13 9 8 14 9 16 15 13 16 16 9 8 17 - 16 3.4 App #2 - Complex Grouping We next present an example of application with complex group requirements. Application #2 monitors the average temperature value for each floor in a building. A coordinator node must be elected for each floor. The criterion for election is battery voltage and the greater identifier is used to break ties. The coordinator node aggregates all values in its floor, computes the average value, and sends this information to the base-station node. The implementations use CTP for messaging routing. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 51 To simplify our implementation, we establish a link between the node identifier and the floor number. We assume a maximum of 10 nodes in each floor and also that the tens of the node identifier represent its floor number. For example, nodes 21 and 25 are in the 2nd floor and nodes 42 and 47 are in the 4th floor. We again compare the code written for an event-driven model with that of the Terra reactive model. Listing 3.5 presents the pseudocode for the nesC version of the monitoring application. This nesC version is based on some premises to simplify the implementation. We used a predefined leader for each group and, considering the radio range, a connected graph is formed by the nodes of same group. Also, the pseudocode for group messaging does not include message queue management, message acknowledgements, message retries, or checks for duplicated message. Listing 3.5: nesC pseudocode for the application #2. 1: f i r s t part −monitor ing f u n c t i o n a l i t y 2event booted 3s t a r t r a d i o 4event r a dio s t a r t e d 5i f r oo t node 6setRoot 7end 8i f nodeID%10 == 0 9s t a r t data p e r i o d i c timer 10 end 11 event data timer 12 msg . group=nodeID /10 13 msg . hops=0 14 t o t a l =0 15 count=0 16 s t a r t timeout timer 17 send r eques t msg 18 read s ens o r 19 event r e q u est msg 20 i f msg . group == nodeId /10 and msg . hops <MAX HOPS 21 parent = msg . source 22 read s ens o r 23 event s enso r done 24 i f nodeID%10 == 0 25 t o t a l = t o t a l + s val u e 26 count = count + 1 27 e l s e 28 msg . t a r g e t = pare nt 29 msg . v al u e = s v a l u e 30 send answer msg 31 end PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 52 32 event r e c e i v e answer msg 33 i f nodeID%10 == 0 34 t o t a l = t o t a l + msg . val ue 35 count = count + 1 36 e l s e 37 msg . t a r g e t = pare nt 38 send answer msg 39 end 40 event timeout timer 41 msg . v al ue = t o t a l / count 42 msg . group=nodeID%10 43 send average msg Listing 3.6 presents the complete C´eu-T code for the monitoring application. Because TerraGrp provides a ready-made parametrized grouping algorithm with support for aggregation, the C´eu-T code is very concise. In this case, programming is not the most important task: the user must understand how the grouping mechanism works to be able to set all parameters correctly. Variable floor, initialized in line 2, holds the floor of the node. This variable is used as parameter to the groupInit() function (line 7) and identifies the node group (subgroup parameter). The group type parameter has the same value for all nodes and is represented by the constant GRID. As the leader election algorithm is set as active by argument eACTIVE (line 7), the grouping component elects one node as the leader. This leader node is stored in the leader field of structure grFloor. An aggregation operation, using the created group, is defined by function aggregInit() in line 11. During the periodic loop, only leader nodes start the aggregation process (line 16). The emit AGGREG() command (line 19) starts the aggregation operation. The aggregation result, when completed, is returned in await AGGREG DONE; in line 20. Then the node can send the results via the emit SEND BS() command in line 24. Section 2.3.2 presented TerraGrp in details. Listing 3.6: The C´eu-T code for the application #2. 1var us ho rt nodeId = getNodeId ( ) ; 2var ubyte f l o o r = ( nodeId /10)+1; 3var ubyte seqData =0; 4 5var g ro u p t g r F l o o r ; 6// (RegName , grtype , subgr , nhops , st atus , e lFla g , l e a d e r ) 7g r o u p I n i t ( grFloor , GRID , f l o o r , 5 , TRUE, eACTIVE , 0 ) ; 8 9var a ggr e g t agFloor ; 10 // (RegName , grName , s en so rI d , agOper , agComp , r e f V a l ) 11 a g g r e g I n i t ( agFloor , grFloor , SID TEMP , fAVG , opGT , 0 ) ; 12 var aggDone t agResult ; PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 53 13 14 loop do 15 par /and do 16 i f nodeId == g r F l o o r . l e a d e r then 17 await ( f l o o r ∗500)ms ; 18 i n c seqData ; 19 emit AGGREG( agFloor ) ; 20 agR esu lt = await AGGREG DONE; 21 msgData . d16 [ 0 ] = agRe sult . va lu e ; 22 msgData . d8 [ 2 ] = seqData ; 23 msgData . d8 [ 3 ] = agResu lt . count ; 24 emit SEND BS( msgData ) ; 25 await SENDBS DONE(ID DATA ) ; 26 end 27 with 28 await 10 s ; 29 end 30 end Table 3.9 presents the quantitative values observed for this test. This table only shows the values for Terra, because we implemented the application in TerraGrp and only wrote the pseudocode for the TinyOS version. We considered this to be enough because the complexity of the nesC version is similar to that of multi-hop monitoring application #1a. Additionally, here we had to handle a bunch of parameters, like group identifier, leader node, and aggregation result. Because TerraGrp defines high-level abstractions for components of general use, the interface with these components are also rather complex. The interface parameters must represent, in a way, the several allowed operations modes. For example, a group definition needs parameters like group type, group id, max hop range, activated flag, and election flag. In this case we have to deal with the trade-off between the script size and the complexity of parametrization. Implementing equivalent script directly in nesC and using the TerraGrp components would also reduce the program lines in the nesC version. But, in this case, the user does not take advantage of the guarantees and facilities given by proposed model. Mainly the programming safeties and the remote reconfiguration. The bytecode size of the application in Terra shows that using an embedded complex component, it is possible to have a relatively complex application with small code size. This C´eu-T script needs only 9 bytecode blocks to have its full code disseminated. This is an example of bytecode that starts in the end of the first block, thus adding one block to the dissemination process. We included in Table 3.9 the total memory size used by the script. This total size includes the memory for the bytecode, the variables, the operations PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 54 Table 3.9: Quantitative metrics - for app #2 Metric Terra Program lines 43 Bytecode size (bytes) 174 Machine code size (bytes) 55,300 Code blocks 9 Total memory size (bytes) 316 Global variables 1 stack, and the runtime controls. In TerraGrp, we must take care with the memory limit, in this case 316 bytes. As presented in Section 2.3.4, in the worst case, TerraGrp in the MicaZ platform allows for only 800 bytes of script memory. This Terra application uses only one global variable, field leader of the group control structure. To exercise the reprogramming of applications we built a variant of application #2 where only well-lighted sensors participate in the computation. It was enough to set the field status of the group control structure. This field is a boolean flag that indicates if the group is activated or not in the respective node. This flag is computed from readings of luminosity sensor, as defined in Listing 3.7. This additional code increased the application in 13 lines and the number of radio messages to disseminate the application increased only in one. We need to disseminate all the 10 messages to replace the old application and to have the new version running in the network, using the same VM-T previously installed in the nodes. Listing 3.7: The additional C´eu-T code for luminosity control. 1par do 2// p r e v i o u s c o n t r o l 3with 4loop do 5emit REQ PHOTO; 6var us ho rt photo = await PHOTO( ) ; 7if photo >10 then 8g r F l o o r . s t a t u s=TRUE; 9e l s e 10 g r F l o o r . s t a t u s=FALSE ; 11 end 12 await 30 s ; 13 end 14 end PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 55 3.5 App #3 - Topology Control Protocol Compared to application #1a, application #3 introduces a more advanced routing protocol. In this application, we evaluate the flexibility of Terra to implement a complex network algorithm. This is an application from the literature that implements a routing tree algorithm with energy saving for WSN as implemented by Auza in his master thesis (Auza, 2013; Auza et al., 2014). Auza’s implementation is based on the theoretical algorithm defined by Chen and Rowe (Chen and Rowe, 2011). To build a routing topology, the algorithm adjusts the radio transmission power to the minimum that maintains the original network tree. The application works in two phases. First, it executes the DTNBOR (Determine the minimal Transmission power to reach each NeighBOR) where all nodes exchange radio messages, gradually reducing the transmission power, to discover the minimal value to reach all neighbors. After that, an application similar to #1a is executed, using the chosen transmission power, to build the routing tree. Here we evaluate the ability of the C´eu-T to build network algorithms. In this case, because we do not use ready-made protocols, we use TerraNet which contains only low-level abstractions. We begin focusing only on the implementation of the DTNBOR algorithm without building the routing tree. The DTNBOR algorithm implementation defines different time execution windows for each node. In the beginning of its execution window, a node sets its radio power to the maximum value and broadcasts a HELLO message to its neighbor nodes. The HELLO message includes the value of radio power in use. Each node, upon receiving a HELLO message, sets its radio power at the received value and sends an answer to the source node. This message exchange is repeated decreasing the radio power settings until the minimal value. As the radio power is decreased, the communication may fail depending on the nodes distance. When it receives an answer, the requester node updates a local table with the node identifier and the radio power level. At the end of this process, all nodes will have a neighborhood table with all neighbor nodes and the respective minimal radio power. The selected radio power for each node is the minimal stored value that reaches all neighbors. The implementation assumes that all nodes start together and plays with different timers to synchronize the message exchanges without any conflict. Because we use the node identifier to define the execution window, the global execution time depends on the highest node identifier. We used the TinyOS version implemented by Auza (Auza, 2013; Auza PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 56 et al., 2014)2. We do not present the pseudocode of this implementation. Table 3.10 shows some quantitative data for the original code. Figure 3.3 shows the block diagram for the C´eu-T DTNBOR program. Inside the main block, in the left side of the diagram, we have the DTNBOR block in parallel with a time-out procedure. The time-out is configured to cancel the DTNBOR execution, and considers the execution time for all nodes. For its part, the DTNBOR block has two parallel blocks. One, in the role of active node, sends a request a message to all neighbors. The other, in the role of passive neighbor, answers any received requests. The request block is detailed on the right side of the diagram. This block starts with a command that holds the node in the passive role until the time windows (that is based on the node identifier) elapses. After this, the node repeats, for each radio power step, a broadcast command and a timed receive loop. The broadcast command sends the HELLO message. The receive loop waits for any ANSWER message until a time-out that breaks its loop to returns to the next radio power step loop. Figure 3.3: DTNBOR block diagram Listing 3.8 presents the complete C´eu-T code for this application. Lines 2–50 contains the DTNBOR block and line 52 the DTNBOR time-out. Inside the DTNBOR block, lines 3–36 contains the request block and lines 38–49 the answer block. For the details of request block, after the delay in line 3, we have the radio power step loop encompassing the broadcast HELLO message at lines 7–14 and the timed received loop at lines 16–34. This radio power step loop is repeated 8 times for different radio-transmission power levels and each received ANSWER message updates the local neighbor table. The answer block, that works in the passive mode, is represented by lines 39–49. Listing 3.8: The C´eu-T code for the application #3. 2We thank the author for making the source code available. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 57 1par / or do 2par do 3await ( ( ( nodeId−FIRST ID)∗T CYCLE) )ms ; 4loop i ,8 do 5var ubyte power = 7−i ; 6// send Hello 7helloMsg . type=HELLO ID; 8helloMsg . source=nodeId ; 9helloMsg . t arget=BROADCAST; 10 helloMsg . power = power ; 11 helloMsg . tp = 0; 12 setRFPower ( power ) ; 13 emit SEND( helloMsg ) ; 14 await SEND DONE( ) ; 15 // r e c e i v e HelloAnswer 16 par / or do 17 loop do 18 respMsg = await RECEIVE(ANSWER ID) ; 19 loop x , MAX NBORS do 20 i f nbor . id [ x]==respMsg . source then 21 nbor . power [ x ] = respMsg . power ; 22 nbor . s tat [ x ] = 1; 23 break ; 24 e l s e / i f nbor . id [ x]==0 then 25 nbor . id [ x ] = respMsg . source ; 26 nbor . power [ x ] = respMsg . power ; 27 nbor . s tat [ x ] = 1; 28 break ; 29 end 30 end 31 end 32 with 33 await T ANSWERS ms ; 34 end 35 end 36 await FOREVER; 37 with 38 // Receive Hello and send answerHello 39 loop do 40 helloMsg = await RECEIVE(HELLO ID ) ; 41 respMsg . type=ANSWER ID; 42 respMsg . targe t=helloMsg . source ; 43 respMsg . source=nodeId ; 44 respMsg . power = helloMsg . power ; 45 await ( nodeId∗ANSWER DELAY)ms ; 46 setRFPower ( respMsg . power ) ; 47 emit SEND( respMsg ) ; 48 await SEND DONE( ) ; 49 end PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 64 available for the C´eu-T script in the Terra Volcano customization, as presented in table 2.2 in section 2.3.4. We also used the Volcano application to evaluate Terra in high-processing condition. Similarly to the original work in Volcano for TinyOS, we measured, for each version, the execution time for different code sections. These sections are grouped as Mean, Energy+Scale, Copy Buffer, and Detect. Figure 3.4 presents a graph with the values we obtained for the three versions – Terra-B, Terra-A, and Original in TinyOS. The durations of the four section are stacked and the three graphs have the same scale to facilitate the comparison. The Y axis has the duration, in milliseconds, of the execution time for the processing of each 1-second data stream in the X axis. Although we ran the test during the first 300 seconds of data, we selected a sampling from seconds 200–219. This sampling range contains three different activity periods. The first period (seconds 200–208) is a full valid data stream with no seismic events that activated the Mean, Energy + Scale, and Copy Buffer operations. The second period (seconds 209–216) is a section combining seismic events that activated all operations, including the Detect operation. The third period (seconds 217–219) is a stream with small number of valid data which does not require so much processing. The Terra-B version, implementing some functions in C´eu-T, spends more time processing data than the other cases and almost reaches the one second limit. As this measurements refer to only part of the code, and do not cover the time needed to read the seismic sensor and to send messages, the total time, may, in fact, exceed one second. This graph also shows that the time of processing for the Terra-A version, that basically glues the embedded Volcano functions together, has the same order of magnitude than the original TinyOS version. The processing cost of the Detect operation is similar in the three versions and is significant even in the TinyOS version. Breaking the full Volcano application into different operations brings the possibility of configuring the script, not only using different parameters when calling the operations, but making it possible to replace or complement specific parts of the operation by script code. Figure 3.5 presents a magnified view of the graph comparing the TerraA version with the original TinyOS version. In this graph it is possible to identify the additional cost incurred by the script interpretation, including the flow control operations and the function calls. For example, it is possible to see the constant difference for the CopyBuffer operation and the additional processing for the Detect operation even outside the detection event. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 65 Figure 3.4: Comparative of execution time for the three versions – B, A, and Original 3.7 Items outside the programming evaluation procedure In our programming evaluation procedure we did not consider three items: learning curve, local starvation, and invalid pointers. This section presents our analysis and discussion for these three items. The learning curve is evaluated based on our teaching experience in WSN programming. Terra solves local starvations and invalid pointers imposing some restrictions at system definition level. 3.7.1 Learning curve We have been using Terra for teaching for at least three years. As part of this experience, we proposed the use of WSN programming as support to teach distributed system (Branco et al., 2013). Currently we use Terra in two courses at PUC-Rio, one of them a graduate course on Distributed Systems, and the PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 66 Figure 3.5: Magnified view of Terra-A vs Original version other an undergraduate course on Reactive Systems. We started by spending about 10 hours (five classes) to introduce students to programming WSNs with nesC and TinyOS, and including some extra time for the implementation of RPC and of Probe/Echo (Andrews, 1991). After we started using Terra, we spend about four hours (two classes) teaching approximately the same material. The first class explores WSN basics, the Terra programming model, its resources, and some simple exercises. In a second class, the students do some exercises, including simple network routing. With that, most of the students are able to build, in the extra time, a network protocol similar to application #1. Besides the reduction in classroom time needed to achieve the same results, we observe, informally, that students are more motivated and have a better programming experience in Terra than they did before. 3.7.2 Local starvation Generally, in WSN, starvation occurs with tight processing loops that don’t leave the CPU free to react to other pending events. TinyOS, over which VM-T is implemented, has a simple scheduler to execute tasks posted in a queue. A task cannot be re-posted if it is pending in the queue. Because the system is single threaded, each task is executed to completion before starting the next task. Exceptions are the CPU interruptions that may execute during the execution of a task. All interrupt handlers in TinyOS must be as short as PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 67 possible and post tasks that complete the necessary work. In the developer’s point of view, almost everything runs as a task. The scheduler guarantees starvation freedom only at task level, but a simple infinite loop inside a task will block the system. In the Terra environment we have to worry about possible infinite loops at two programming levels. At one level are the Terra customized components and, at the second level, the user script application. At the first level, in nesC/TinyOS, we expect an experienced programmer to build and to test exhaustively all components before making them available to the application programmer. For the second level, we combine the guarantees in the original C´eu language with a specific detail of the Terra execution model. The Terra implementation treats each C´eu trail as a TinyOS task. (See Section 2.2.2 for more details). The C´eu and C´eu-T compilers include in their static analysis checks for infinite loops without await statements inside them. Thus, an infinite loop in C´eu-T code is necessarily composed of different tasks. This guarantees that the scheduler will run all pending tasks. 3.7.3 Invalid pointers Terra avoids invalid pointers in three different ways. First, C´eu-T treats all memory addresses statically, both for code and for variables. Second, we implemented in Terra a simple type system that does not allow pointer variables. (See Section 2.2.1 for more details.) Terra also offers guarantees against out-of-bound array indexes. For constant indexes, the Terra compiler gives an out of bound error for invalid values. For variable indexes, the assembler opcode for array indexing carries the index max value and the Terra runtime checks it in execution time. In case of error, the operation is not executed and an ERROR event is generated with E IDXOVF value. 3.8 Analysis In this section we consolidate our analysis with a general view. Although the reduction of global variables is not explicit in all cases, a C´eu-T program tends to push globals to local procedures. This also tends to reduce the number of possible combination of global variables and events, keeping the reactive program logic clearer when compared to an equivalent event-driven version. Even when we need to use global variables, in general, these variables are strongly related to only few blocks of code. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 68 When compared to two separate operations in different position in the code, the split phase operations using (emit+await) of C´eu-T also reduce program complexity, allowing a more concise code. Terra’s guarantees against local starvation and invalid pointers contribute to safer code. Handling a basic radio operation in TinyOS requires some special knowledge and needs several lines of code in different parts of the nesC program. Besides handling the message data structure and calling the send command, the user must additionally configure some TinyOS components, define the used interfaces, and call some functions to build the message buffer. Terra simplifies this operation, because the user needs only to define the message data structure and call the send command. The reactive model of C´eu-T has some patterns of construction that are very useful for programming network protocols. These patterns, along with the points identified above, allow a network algorithm written in C´eu-T to be very concise when compared to an equivalent one written in nesC/TinyOS. The low-level abstractions of Terra for send and receive operations already present an interface that is simpler to use than one provided by TinyOS. As we get higher up in the abstractions levels, we may also have simpler interfaces. But, in abstractions of general use like the grouping component, the interface takes a number of different arguments to allow the configuration of different operation modes. This variety of arguments make complex the use of the component because it transposes the operation complexity to the arguments of the interface. We have a trade-off between the program size simplification and the component parametrization. Sometimes it may be better restrict some internal configurations to reduce the parameterization degree and provide a more simple interface. As regards error checking, the VM-T implementation captures the arrayindex overflow and generates a special ERROR input event to the user script. Division by zero and stack overflow are handled similarly. In general, the Terra system allows the VM-T expert programmer to build customized components for use by the application developer in a specific context. This opens the opportunity for high-level components with simple interfaces, in contrast to the relatively complex interface of our generic grouping components. These interface simplifications, added to the C´eu-T language characteristics, allow a fast learning curve when compared to a programming environment like nesC/TinyOS. Using high-level abstraction we obtained drastic reductions in bytecode size. A good side effect is the small amount of the messages necessary to reprogram the application running on the network. In general, the energy cost PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 3. Programming evaluation 69 for the dissemination of this code is not significant compared to the energy cost of a long running application. The remote reprogramming capacity, given by the use of virtual machine, is an advantage over traditional systems like TinyOS and Contiki. The developer easily reprograms the application and the network nodes use much less energy than needed to disseminate the full machine code via radio. Although CPU-intensive processing is not common in WSN applications, we experimented with a Terra system configuration using a specialized highprocessing application. When we embedded all high-processing functions in a customized component, the execution time of the Terra version was compatible with that of the original application written in TinyOS. On the other hand, implementing high-processing operations in C´eu-T may not be adequate for some applications. As expected, the code complexity decreases when we increase the abstraction level. Figure 3.6 shows the expected relation between complexity of scripts, complexity of components, and the roles of Application programmer versus Expert programmer. The border adjustment between code complexity and abstraction level may create a simple development environment for application programmers. Figure 3.6: Behavior of abstraction complexity PUC-Rio - Certificação Digital Nº 1112677/CA 4 Cost evaluation In this chapter, we address the cost issues due the use of virtual machine architecture, as defined in Section 1.2.2. The next two sections present the execution strategy, the test metrics and the test scenarios we used to measure CPU and memory overhead. The following sections describe our observations regarding the overhead imposed by VM-T and the time needed for code dissemination. 4.1 Execution strategy and Metrics The test application was again compared in two different environments, one using nesC/TinyOS and other using the specific TerraNet customization. Table 4.1 describes all metrics we chose to help us understand and compare resource usage in different test scenarios. Table 4.1: Resource usage metrics Metric Description Cycles/Time Number of loop cycles in CPU/IO bound test. CPU Active/Idle Cycles Number of clock cycles in active and idle CPU modes. Radio/CPU Energy Amount of consumed energy. Byte-code size Program size in bytes/blocks to be disseminated via radio. To obtain values for the first three metrics we ran the tests using the Avrora simulator (Titzer et al., 2005). Avrora can simulate a network with MicaZ nodes. It acts at machine code level and also emulates radio-chip operation. 4.2 Test scenarios We chose three test scenarios to support our analysis. The first two scenarios are conditions of saturated execution and aim to make the VM overhead explicit. The third scenario represents a simple and typical application. Table 4.2 shows the two environments considered in our tests. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 4. Cost evaluation 71 Table 4.2: Execution environments (Resource) Environment Description nesC/TinyOS Low level code environment. TerraNet Low level abstraction environment. Table 4.3 describes the application used for each test scenario. Applications #1 and #2, respectively CPU-Bound and IO-Bound, are used to stress the system to reveal execution differences between nesC and Terra. These applications are used to identify performance impacts from the use of virtual machine. Application #3 is a simple read sensor loop like a regular monitoring application. We use this to show resource utilization in a normal operation condition. For all tests we compared similar applications running in nesC/TinyOS and in TerraNet. Table 4.3: Applications # Application Description 1 CPU-Bound An intensive CPU loop without I/O events. 2 IO-Boud An intensive I/O loop. 3Normal operation A simple monitoring application running in a normal operation condition without intensive use of CPU or IO. 4.3 Results In this section, we evaluate VM-T from two different points of view. In Section 4.3.1, we try to estimate the overhead incurred by interpretation. To this end, we compare computing-intensive code written in Terra and in the native nesC programming language1. Next, in Section 4.3.2, we evaluate the time for code dissemination and its scalability for network growth. 4.3.1 VM overhead benchmarking We use three different tests to evaluate the overhead incurred by the VM as compared with direct execution over TinyOS. In the first test, we run a simple CPU-bound application: a loop that continuously increments a value. This would be an extremely uncharacteristic pattern for sensor network applications, which typically pass through relatively long intervals of quiescence, followed by short periods of activity, triggered by external events. 1All program versions, including the Terra runtime, were compiled to MicaZ platform using the same radio transmission power (CC2420 DEF RFPOWER=7). PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 4. Cost evaluation 72 The idea of this test is to stress the processing capacity of VM-T to the limit. In the second test, we measure the overhead of the VM bounded by an IO operation. In this case the application repeatedly reads data from a sensor in a closed loop. In the third test, we measure the overhead of the VM in a more typical scenario, in which the application repeatedly reads data from a sensor in a periodic loop. In each test, we run both variants of the application for five minutes. Every ten seconds interval, all applications send the value of the loop counter to the base station. In both systems, programs are coded with event-based loops. In Terra, because a tight loop is forbidden, we use a custom event to break the loop with an await command. In the corresponding Terra custom component, the return event is generated immediately from the request. In the nesC/TinyOS version, each iteration posts a task representing the following iteration. To compare the results, we use two metrics. The first one is the total number of iterations executed along the five minutes that the applications are left running. This number is the value of the counter sent to the base station at time 300s. The goal of using this metric — which can be measured both in real motes and in the simulator — is to have a rough idea of the relative processing speeds of the two platforms. The second metric we use is the total number of cycles in Active and Idle state2. The values for this metric were obtained through the simulations on Avrora and help us to understand the difference in the processing time. Test scenario 1 - CPU-bound Application Table 4.4 presents the results obtained with Avrora for our first scenario. Listings 4.1 and 4.2 show the code we used for this experiment. In the nesC version, the main loop is executed in a TinyOS task that contains only two commands: the loop counter increment and the (re)post of the task itself. A periodic timer sends the counter value to the basestation every 10 seconds. The message data are copied to the radio message buffer (lines 16–20) and the sending command (lines 21–23) is executed followed by a debug message (lines 24–26) specific to the TOSSIM version. In Terra we have a “par” with two sections. The first section controls the loop and increments the counter variable (lines 3–7) and the second section sends the counter value to the basestation every 10 seconds (lines 10–14). We use the CUSTOM event to act as dummy event, as it forces a returned value via event interface (lines 4–5). 2TinyOS keeps the CPU in idle state when the task queue is empty. The CPU goes into active state when it receives an interruption. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 4. Cost evaluation 73 Table 4.4: CPU-bound Test Metric Program Version Terra(a)nesC(b)b/a loop counter 597,511 11,735,607 19.64 active cycles 2,175,061,049 2,174,060,892 1.00 idle cycles 37,735,747 4,768 0.0 Listing 4.1: The code for CPU-bound experiment in TinyOS/nesC. 1// CPU bound loop 2task vo id incTask (){ 3counter++; 4post incTask ( ) ; 5} 6 7// Monitoring message 8event v oid RadioControl . startDone ( e r r o r t e r r o r ){ 9c a l l sendTmr . s t a r t P e r i o d i c (10000) ; 10 post incTask ( ) ; 11 } 12 event v oid sendTmr . f i r e d (){ 13 e r r o r t s t a t ; 14 Msg . d16 [0]++; 15 Msg . d32 [0]= counter ; 16 memcpy( c a l l send . getPayload ( 17 &sendBuff , 18 c a l l send . maxPayloadLength ( ) ) , 19 &Msg , 20 s i z e o f ( sendBS t ) ) ; 21 s t at = c a l l send . send ( 0 x f f f f , 22 &sendBuff , 23 s i z e o f ( sendBS t ) ) ; 24 i f ( s t a t != SUCCESS) { 25 dbg (APPNAME,”CM: : send ( ) : Send e r r o r \n ” ) ; 26 } 27 } Listing 4.2: The code for CPU-bound experiment in Terra. 1par do 2// CPU bound loop 3loop do 4emit REQ CUSTOM; 5await CUSTOM( ) ; 6i n c msg1 . count ; 7end 8with 9// Monitoring message PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 4. Cost evaluation 80 recovery stage, which would be a probable scenario in a real-world use. We ran our test using a script for a real monitoring application that includes routing to the basestation. The program bytecode has 24 message blocks to be disseminated. Table 4.8 presents the dissemination times for three scenarios. The first scenario is a very basic case with only one node. The second scenario considers a grid with 9 nodes (3 x 3) and the third scenario considers a grid with 49 nodes (7 x 7). In our grid network, each radio node reaches up to 8 neighbor nodes. Only one node in the corner of the grid exchanges messages with the basestation. This configuration forces the use of the flooding mechanism. Figure 4.1 shows an example for the 7 x 7 grid with the radio range highlighted for nodes 11, 32, and 44. We also measured, for each node, the total time it took to load the program (local load time). Table 4.8 includes the minimum, maximum, and average for local load times in each scenario. All dissemination tests were done considering that all radios were switched on. Figure 4.1: Simulated 7x7 grid - node 11, 32, and 44 with radio range highlighted. Table 4.8: Dissemination time Scenario Total Total Avg local Min local Max local Nodes Duration load time load time load time #1 1 7.17 7.17 7.17 7.17 #2 9 7.25 6.76 6.70 7.17 #3 49 7.50 6.58 6.40 7.17 all durations in seconds PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 4. Cost evaluation 81 The dissemination for the single-hop scenario took 7.17 seconds for 24 messages, that is, approximately 300ms per message. The 300ms step delay time is exactly the configuration parameter used in our algorithm. Using one real node it is possible to measure a similar duration, but the reference is a message sent back to the computer. In our real-node test we got 7.2 seconds. Although it is possible to use lower values for the step delay time to reduce the total dissemination duration, we chose to be more conservative to minimize radio collision in dense networks. The VM-T customizer may choose different values for this parameter. This subject should be matter of further investigation and depends on network topology. The differences between minimum, maximum, and average local load times are of fractions of seconds. Considering the nature of WSN applications, in general these differences don’t affect system operation. The combination of the step delay with the random send delay allows some nodes to receive more than one message in the same dissemination step. When this happens, the local load time drops to less than the standard 1.7ms. Comparing results for the different scenarios we get the time for each additional hop in the network. In general, as our dissemination algorithm floods message by message in sequential waves, the total time doesn’t increase much as the network grows. In our case this time varied from 40ms up to 55ms. These values are consistent with our radio-send policy, where the sending message is delayed randomly from 20ms up to 95ms. Based on the scenarios #2 and #3, respectively with 9 and 49 nodes, the dissemination time has increased only 250ms (3.45%) for an increment of 40 nodes (444%). These results indicate that the system scales well. PUC-Rio - Certificação Digital Nº 1112677/CA 5 Related work Terra’s basic proposal is to combine the advantages of using applicationspecific, or high-level, virtual machines with a scripting language that provides a set of facilities and guarantees. In this section we report on works that are related to each of these approaches and discuss how Terra relates to them. To our knowledge, the first work proposing the use of virtual machines in WSN is Mat´e (Levis and Culler, 2002). The Mat´e VM is built on TinyOS and has a very simple instruction set. The code propagation and execution is broken up into 24 instructions called capsules. A capsule fits into a single message packet. Mat´e limits its context execution to only three concurrent paths, one for sending messages, another one for receiving messages, and a third one for a timer. Mat´e has up to 8 user-defined instructions that enable additional virtual machine customization and its operand stack has a maximum depth of 16. To address some of Mat´e’s limitations the Mat´e team built ASVM (Levis et al., 2005). ASVM is an application-specific virtual machine. The authors proposed a custom runtime machine to support different application-specific high-level languages, but each language needs its own compiler. ASVM implements a central concurrency manager to support the sequential execution on concurrent handlers. This is an optional service to help user applications avoid race conditions. This solution assumes that handlers are short-running routines that do not hold on to resources for very long. DAViM (Michiels et al., 2006) is very similar to ASVM but adds the possibility of parallel execution. DVM (Balani et al., 2006) is based on the application-specific VM concept from ASVM, but it uses SOS (Han et al., 2005) as its operating system. SOS allows dynamic loading of system modules. In DVM, it is possible to load different combinations of high-level scripting languages and low-level runtime modules. DVM and DAViM also use a concurrency manager like ASVM’s. Several groups have worked on VMs for Java. VMStar (Koshy and Pandey, 2005) uses the Java as high-level language for customized VMs. The VMStar toolset helps to build a new VM runtime from the device characteristics and the component library. VMStar uses a “select” concept to register event-wait points in a sequential program. The select interface executes event handlers sequentially to avoid race conditions, in a singlethread implementation. VMStar inherits type-safety from Java, like the other PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 5. Related work 83 Java VMs. NanoVM (Harbaum, 2005), ParticleVM (Riedel et al., 2007), TakaTuka (Aslam et al., 2008), and Darjeeling (Brouwers et al., 2009) also use Java as their programming language. Inspired on TinyDB (Madden et al., 2005), SwissQM (Mueller et al., 2007) has a query-specific instruction set and a high-level language similar to SQL. Cosmos and Regiment implement customizable VMs with high-level languages that are specifically designed for WSNs. Cosmos (Awan et al., 2007) uses mPL as high-level language and mOS as operating system. mPL supports intra-network operation programming, that is, network-wide operations. A Cosmos application is defined by a data-flow graph and some custom C functions loaded within mOS. The mOS system executes the application graph as a script. The scripting language is limited to the data flow control using the custom mOS functions. Cosmos also allows dynamic loading of new C functions. The graph approach also limits the application types. In Cosmos, an event handler is represented as a Functional Component (FC). A FC uses only local variables and its data are exchanged by input/output interface queues. These characteristics avoid race conditions. Regiment (Newton and Welsh, 2004; Newton et al., 2007) uses a reactive functional language with a special semantic for intra-network operations. The runtime implements basic operations and access to devices. A Regiment application is compiled to an intermediate language called Token Machine(TM). A TM segment propagates across the network and it is interpreted to execute local operations or intranetwork operations like group formation and aggregation. In Regiment, an event handler task run to completion and cannot be blocked. This also avoids race conditions. Discussion VM-T architecture combines small size with a model that is less restrictive than Mat´e’s. Because Terra implements the concurrency model of C´eu, it is possible to have several concurrent execution paths. Terra also enables up to 255 identifiers for each group of input events, output events, and functions. VM-T stack is defined at compile time and is limited only by memory space shared with the application script. Differently from DVM and Cosmos, Terra doesn’t allow low-level code loading, but Terra natively supports remote parameterization of runtime components. We believe Terra’s reactive programming model, similarly to Regiment’s, is more suitable to event-driven application then the traditional program models. In a C´eu-T program it is possible to suspend the execution of PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 5. Related work 84 one program block and wait for an event without suspending all other program blocks. Terra inherits the C´eu execution control in which a trail (a C´eu handler) is serialized to execute to completion. C´eu trails are similar to Protothreads coroutines (Dunkels et al., 2006), because they both offer multiple sequential lines of execution to handle concurrent activities. This execution mode minimizes race conditions and doesn’t burden the user with synchronization mechanisms (centralized controls, interface queues, or semaphores and mutexes). It still may get race conditions from multiples trails waiting for the same event and writing the same memory address. However, the compiler offers an analysis mode which find these race conditions. This analysis mode is similar to the safe annotations from TinyOS but it is checked at compile time. Well tested builtin components extend the safety guarantees to runtime. C´eu-T avoids tight loops which is not recommended but allowed by most of the related work. By itself, C´eu-T doesn’t give execution guarantees in intra-network operations. In Terra, these guarantees may be given by built-in runtime intra-network operations. Unlike Cosmos and Regiment, Terra doesn’t support network-wide programming. The user must think about the application as a whole but write the code that each node will run. However, the provision of components inspired by macro-programming alleviates this problem in some measure, by abstracting some typical collective operations. PUC-Rio - Certificação Digital Nº 1112677/CA 6 Final remarks Programming WSN system is a difficult task. The distributed system nature and the resource limitation turn it into a complex activity and error prone. Our research seeks how to simplify this programming activity and how to reduce typical errors. We formulated the following as research question for this thesis: To what extent can a programming environment based on the combination of a reactive high-level scripting language with safety guarantees with a virtual machine that encapsulates customized components facilitate the task of programming WSNs, providing abstractions to simplify programming, reducing the possibility of errors, and allowing reprogramming? To investigate this idea we built Terra, a flexible system that uses a reactive language combined with a virtual machine which allows to embed new operations as components and facilitates remote distribution of scripts using low energy consumption. In this work we described the Terra implementation and its operation mode and evaluated Terra in different test scenarios. Our evaluation for programming used different abstraction levels for the functionalities available at the script level. Also we evaluate the Terra performance to identify the resource overhead incurred from the use of virtual machine. To meet our evaluation requirements we built three different customizations of Terra — TerraNet, TerraGrp, and TerraVolcano. TerraNet represents our low-level abstraction environment. It includes only basic operations as sensor readings and simple radio operations. The TerraGrp represents our version with high-level abstractions. It implements a set of components for network operations over groupings of nodes. TerraVolcano is a high-level abstraction that uses a specialized implementation for the volcano experiment. This version combines heavy use of CPU with large data memory. We evaluated Terra comparing the reactive programming model of Terra with the event-driven programming model of nesC/TinyOS. Applications in the test experiments ranged from low-level network algorithms up to highlevel grouping operations or data processing. The evaluation produced a set of listing and some metrics regards to programming issues in WSNs. In the performance evaluation we collected some metrics from saturated processing situation up to regular operation. Also we compared the Terra virtual machine operation with the TinyOS operation for an equivalent program. PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 6. Final remarks 86 6.1 Main findings Our experiments showed that the Terra programming model, compared to an event-driven programming model, simplifies the programming and gives guarantees to a safer code. An interesting discovery, in the programming evaluation, was related the use of global variables. We started from the idea that a program in Terra reduces the needs of global variables in the application. This reduction might contribute to reduce the application complexity and subsequently reduce the chance of programming errors. As well, we discovered that the structured programming patterns of C´eu-T allows a more clear context separation. In this case, a global variable may be related to a few contexts in the programming, diminishing the program complexity and subsequently reducing the chance of programming errors. Another point is the combination of the split phase operations using (emit+await) of C´eu-T and the simplification in the operation interfaces, this also contribute to have a more concise code. Also, Terra’s guarantees for racefree and against local starvation and invalid pointers contribute to safer code. Considering the use of low-level abstractions in low-level networking algorithms, the simplification came from the combination of C´eu-T facilities, in special the combination of some C´eu-T programming patterns and global variables, with the simplification in the interface of low-level components. Programming low level networking algorithms has a small reduction in the program lines, because these kind of algorithms, in general, has a transactional model for message exchanges that hardly can be reduced. In our example of full transactional algorithm the reduction was 35% and in the case of hybrid algorithms the reductions reached 73%. In this test variant the major benefit of Terra is the opportunity, if desired, to remotely changing the network algorithm. This is useful in WSN systems in which the best network algorithm may not be completely determined beforehand and may need modifications during application life time. Considering use of high-level abstractions for complex functionalities, we show that when we embed complex components this will reduce drastically the code size. An example of complex grouping operation compared to an example of a simple low-level network algorithm had a reduction of 78% in the line codes. But we also identify that creating general components may have more complexity in the interface with functionality abstractions. In this case, the script is more simple, but the use of component may be more complex and may generate difficulties in the code implementation. In some cases it may be PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 6. Final remarks 87 better to offer more specialized components, with fixed internal parameters, rather than generic components. The performance issues evaluation shows that the virtual machine approach is viable for WSNs system. The additional costs are not so important in a long run application. However we observed a significant trade-off between the memory (RAM and ROM) requirement and the high-level abstraction customizations. A complex component tends to use more ROM and RAM and this limits, in special for small platforms, the available memory for the script application and may also overflow the ROM. In general this has low impact in the case of RAM, where the application script tends to be small, however someone may write a more complex script and reach the memory limit. Another attention point is about high-processing operations. Our experiment with Volcano shows that it is better to leave this operation embedded in a custom component instead of try to execute by script. Our experiments show that several benefits of Terra come from the combination of two or three of the basic elements of the system: C´eu-T language, Embedded VM, and Built in components. The reduction in the programming complexity came from the combination of the C´eu-T reactive language with the use of embedded components. The verifications from the compiler combined with the VM implementation avoids local starvation and invalid pointers in a Terra application. The use of the VM approach combined with the high-level components allows very small bytecode size and low energy cost to reprogramming an application. In general, we are very satisfied with the demonstrated results. The Terra approach showed that it is possible to simplify the WSN programming while reducing the chances of typical errors. Currently we have used Terra in undergraduate and graduate courses to teach concepts of WSN and distributed systems. From our experience, we identified that Terra allowed to reduce the learning curve compared to a low-level event-driven programming model. Additionally, we exercise a bit more the reactive programming model of C´eu. Applying it in different applications brings more confidence in its use. 6.2 Future work and related improvements The work on Terra was born from our interest in WSN macroprogramming (network-wide programming) and from thinking that we needed nodelevel support before moving to the network level. We might now be able to investigate this issue using Terra as the base system for a new macroprogramming language. This new macroprogramming language may use C´eu-T PUC-Rio - Certificação Digital Nº 1112677/CA Chapter 6. Final remarks 88 as intermediate language or be compiled directly to the VM-T assembly code. Another approach is to evaluate Terra’s model in the world of IoT (Internet of Things). As WSN applications are one of the base of IoT, we may take advantage of reconfigurable characteristic of Terra to make “things” more adaptable. A more specific approach, also related to IoT, is to evaluate the Terra model for use in embedded system for different kinds of appliances. In this direction, we have already started to migrate the VM-T implementation to the Arduino1platform. We believe that some future experiments and related improvements in Terra may give a better support to the areas of macroprogramming and IoT. One of them is to evaluate the Terra model to allow different roles in a heterogeneous network. In this case Terra will work as a homogeneous environment layer over heterogeneous devices, enabling the dissemination of a specific code by node. This is important for IoT experiments that connect different devices for specific applications like home automation, health-care monitoring, and industrial automation. Finally, another important evaluation is about security. This Terra implementation relies on radio services from TinyOS, where messages are exchanged without any security support. An intruder may capture data and inject malicious data or scripts. A future experiment is to evaluate the impact, in memory size and processing, of embedding some security in Terra’s communication layer. 1www.arduino.cc PUC-Rio - Certificação Digital Nº 1112677/CA 7 Bibliography ANDREWS, G. R. Paradigms for process interaction in distributed programs. ACM Computing Surveys, ACM, New York, NY, USA, vol. 23, no. 1, p. 49–90, mar. 1991. ISSN 0360-0300. Available from Internet: <http://doi.acm.org/10.1145/103162.103164>. 3.7.1 ASLAM, F. et al. Introducing TakaTuka: a Java virtual machine for motes. In Proceedings of the 6th ACM conference on Embedded network sensor systems. New York, NY, USA: ACM, 2008. (SenSys ’08), p. 399–400. ISBN 978-1-59593-990-6. Available from Internet: <http://doi.acm.org/10.1145/1460412.1460472>. 5 ATMEL. ATMEGA128. 2467x–avr–06/11. ed. San Jose, CA, USA, 2011. Available from Internet: <http://www.atmel.com/Images/doc2467.pdf [accesed in june/2015]>. 4.3.1 AUZA, J. M. N. An´alise de Desempenho de Algoritmos de Eficiˆencia Energ´etica em RSSF. Master thesis — Pontif´ıcia Universidade Cat´olica do Rio de Janeiro, Departamento de Engenharia El´etrica, 2013. 94p Text in Portuguese. 3.2, 3.5, 3.5 AUZA, J. N.; BRANCO, A.; MARCA, J. Boisson de. Experimental evaluation of energy efficient algorithms for WSN using variable transmission powers. In Sensors (IBERSENSOR), 2014 IEEE 9th Ibero-American Congress on. Washington, DC, USA: IEEE, 2014. p. 1–4. ISBN 978-1-4799-6835-0. 3.2, 3.5, 3.5 AWAN, A.; JAGANNATHAN, S.; GRAMA, A. Macroprogramming heterogeneous sensor networks using Cosmos. In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007. New York, NY, USA: ACM, 2007. (EuroSys ’07), p. 159–172. ISBN 978-1-59593-636-3. Available from Internet: <http://doi.acm.org/10.1145/1272996.1273014>. 1, 2.3.2, 5 BAKSHI, A. et al. The Abstract Task Graph: a methodology for architectureindependent programming of networked sensor systems. In Proceedings of the 2005 Workshop on End-to-End, Sense-and-Respond Systems, Applications and Services. Berkeley, CA, USA: USENIX Association, 2005. (EESR ’05), p. 19–24. ISBN 1-931971-32-3. Available from Internet: <http://dl.acm.org/citation.cfm?id=1072530.1072535>. 2.3.2 PUC-Rio - Certificação Digital Nº 1112677/CA Appendix A. Terra – complementary informations 96 13 Addr , Data addr 14 00016 0008 $ r e t : |i n t e r n a l use v a r i a b l e 15 00017 0009 a : |var byte a ; 16 00018 0010 b : |var byte b ; 17 18 −− F i r s t e n try po in t 19 Addr , bytecode , mnemonic |Ceu−T code 20 00019 c4 s e t c byte 9 10 |a = 10 21 00020 09 22 00021 0a 23 00022 29 c l k e n c 0 2000 30 |await 2000ms ; 24 00023 03 25 00024 00 26 00025 07 27 00026 d0 28 00027 00 29 00028 05 30 00029 01 end |end 31 32 −− Second ent r y p oin t 33 Addr , bytecode , mnemonic |Ceu−T code 34 00030 c4 s e t c byte 10 20 |b = 20 35 00031 0a 36 00032 14 37 00033 01 end |end A.2 Terra operation After VM-T is loaded at all network nodes, the user can upload his script to be disseminated via radio to the network nodes. The VM is typically loaded over a wired interface for each node as for any TinyOS program. It is also possible to run a simulated version of VM-T in the TOSSIM TinyOS Simulator or in emulators like AVRORA and COOJA. In a typical use of Terra, the programmer writes a C´eu-T program, compiles it, and uploads its bytecode to the network. The compilation process must include a specific Terra configuration file for the chosen virtual machine. The C´eu-T program can only use events and functions defined in the configuration file. The generated bytecode must then be disseminated over the WSN using Terra’s upload tool. This tool transfers the bytecode to the basestation node connected to the computer via wired interface. The base station node then starts the dissemination algorithm to send the bytecode program, which is divided in blocks, to all nodes. This is a basic flooding algorithm where all nodes forward each incoming message until all nodes are reached. Figure A.1 PUC-Rio - Certificação Digital Nº 1112677/CA Appendix A. Terra – complementary informations 97 presents the load interface of Terra Tool. Figure A.1: Terra Tool - load bytecode interface A.3 Integration between script and components In C´eu, the user program may indicate a list of external events and functions (written in C) that will be called. In the virtual machine approach, the script code should call only events and functions that have been previously embedded in the virtual machine over which it will execute. We have thus decided that, besides input and output events, the VM components would also provide functions in order to allow some interactions to occur in a more natural way. Typical examples of functions are getNodeId(), that returns the node identifier, and groupInit(), that sets parameters for a node to participate in a group of nodes. System calls behave like normal function calls and are used to initialize and configure the components (e.g. groupInit()). The invocation of a system call is synchronous: control returns to the script when the system call finishes execution. The developer writing new system calls should make sure their implementation does not block (this restriction is compatible with the intended use of system calls). Output events are used to request asynchronous operations to components (e.g. emit REQ TEMP();). Signaling an output event is an asynchronous operation, and returns immediately, without blocking the script. Input events, in contrast, cross the VM boundary towards the script and guide PUC-Rio - Certificação Digital Nº 1112677/CA Appendix A. Terra – complementary informations 98 its execution through successive reactions. An event occurrence starts a new reaction in the script, awaking all trails awaiting that event (e.g, await TEMP). The virtual machine developer must describe the custom data structures, external events and functions that the VM provides using the C´eu-T syntax for configuration blocks. These descriptions and some definitions of constant values must be written in a configuration file to be included in the user application program. The customized virtual machine and the configuration file must be distributed together in order to ensure the correct execution of the user program. The C´eu-T compiler can generate, without any modification, the bytecode of any scripts compatible to the new configuration. Listing A.3 shows an example of a configuration file. The header of configuration block defines the name and the version of the customization. Also defines, for each compatible platform, the amount, in bytes, of RAM memory available to the application script. The body of configuration block defines the events and functions available in the customization. In this example we define two output events, one input event and two functions. Event definitions have always two types in its definition, the first is the returned value and the second is its argument. Function definitions have a first type that defines its returned value and may have a list of types of its arguments. All definitions must have, at the end of line, a unique number for each type of definition. This number is used to identify the respective operation inside the VM-T. Listing A.3: A simple configuration block example. 1config 2name : TerraNet , 3code : 00.03. 00 , 4{ 5t e l o s b : 5808 , 6micaz : 2016 , 7mica2 : 2016 , 8} 9do 10 output v oid REQ TEMP voi d 1; 11 output v oid SEND SENSOR radioMsg 2; 12 13 in pu t ushort TEMP voi d 1; 14 15 f u n c t i o n ubyte getNodeId () 1 ; 16 f u n c t i o n ubyte queuePut ( radioMsg ) 2 ; 17 end Figure A.4 list the definition file to be included into the VM custom module implementation. This definition is related to same definitions for the configuration presented in the Figure A.3. PUC-Rio - Certificação Digital Nº 1112677/CA Appendix A. Terra – complementary informations 99 Listing A.4: A include file related to a configuration block. 1typedef nx struct sensorMsg{ 2n x u i n t 8 t id ; 3n x u i n t 1 6 t valu e ; 4}sensorMsg t ; 5 6enum { 7O REQ TEMP = 1; 8O SEND SENSOR = 2; 9 10 I TEMP = 1; 11 12 F GETNODEID = 1; 13 F QUEUEPUT = 2; 14 }; Figure A.5 presents a partial implementation for the elements introduced in the Figure A.4. The two first functions are called from the VM decoder, the fist function procOutevt() dispatch any defined output events and the function callFunction() dispatch any defined customized functions. Lines 17–22 shows an example of a custom function that returns a value via stack. Lines 24–27 has a example of an external event call. Lines 29–34 presents an example how a input event is put in the queue of the VM engine. Listing A.5: VM Customization – input/output events and functions. 1// Output e ven t d i s p a t c h e r 2command v o i d VM. procOutEvt ( u i n t 8 t id , u i n t 3 2 t value ){ 3switch ( id ){ 4c a s e O REQ TEMP: proc req temp ( id , value ) ; break ; 5c a s e O SEND SENSOR: proc se nd senso r ( id , value ) ; b r e a k ; 6} 7} 8 9// Function d i s p a t c h e r 10 command v o i d VM. callFunction(u i n t 8 t id ){ 11 switch ( id ){ 12 c a s e F GETNODEID: func getNodeId ( id ) ; break ; 13 c a s e F QUEUEPUT: func queuePut ( id ) ; break ; 14 } 15 } 16 17 // Pushing a value to the s t ac k 18 v o i d func getNodeId( u i n t 1 6 t id ){ 19 u i n t 1 6 t s t at ; 20 sta t = TOS NODE ID; 21 s i g n a l VM. push ( s ta t ) ; 22 } 23 24 // C a l l i n g a o ut put ev en t 25 v o i d proc req temp ( u i n t 1 6 t id , u i n t 3 2 t value ){ PUC-Rio - Certificação Digital Nº 1112677/CA Appendix A. Terra – complementary informations 100 26 c a l l S TEMP. read ( ) ; 27 } 28 29 // Queueing an inp ut event + v a l u e 30 u i n t 1 6 t lastTemp ; 31 event v o i d S TEMP. readDone ( e r r o r t result , u i n t 1 6 t val ) 32 lastTemp = val ; 33 s i g n a l VM. queueEvt (I TEMP, 0 , &lastTemp ) ; 34 } PUC-Rio - Certificação Digital Nº 1112677/CA