Achieving repeatability of asynchronous events in wireless sensor networks with EnviroLog

Achieving Repeatability of Asynchronous Events in Wireless Sensor Networks with EnviroLog Liqian Luo†, Tian He‡, Gang Zhou, Lin Gu, Tarek F. Abdelzaher†, John A. Stankovic Computer Science Department, University of Virginia, Charlottesville, Virginia 22904 {ll4p, tianhe, gz5d, lg6e, zaher, stankovic}@cs.virginia.edu Abstract— Sensing events from dynamic environments are normally asynchronous and non-repeatable. This lack of repeata- bility makes it particularly difficult to statistically evaluate the performance of sensor network applications. Hence, it is essential to have the capability to capture and replay sensing events, providing a basis not only for system evaluation, but also for realistic protocol comparison and parameter tuning. To achieve that, we design and implement EnviroLog, a distributed service that improves repeatability of experimental testing of sensor networks via asynchronous event recording and replay. To use EnviroLog, an application programmer needs only to specify two types of simple annotations to the source code. Automatically, the preprocessor embeds EnviroLog into any desired level of an event-driven architecture. It records all events generated by lower layers and can replay them later to upper layers on demand. We validate the accuracy and performance of recording and replay through a set of microbenchmarks, using the latest XSM platforms. We further demonstrate the strength of EnviroLog in system tuning and performance evaluation for sensor network applications in an outdoor environment with 37 XSMs. I. INTRODUCTION With the increase in maturity of sensor networks research and with recent solutions to several practical systems and de- ployment problems, sensor network applications are entering the real world. Representative experiences of such evolution are documented in recent literature such as military surveil- lance [7] [19], habitat monitoring [13] [12], and environmental monitoring [23] [2], just to name a few. Quite different from controlled lab settings, physical environments introduce a high degree of uncertainty that makes it hard to conduct repro- ducible experiments. Consequently it is hard for researchers to obtain statistically consistent empirical results. With the growing number of applications developed and deployed, there is an increasing need for tools and services to assist with system evaluation and debugging, as well as with performance tuning of applications in outdoor environments. To address this issue, we propose EnviroLog, a tool to im- prove repeatability of experimental testing of distributed event- driven sensor network applications. Unlike time-driven appli- cations, such as periodic sampling of environmental condi- tions, the state of event-driven systems can change depending on the particular sequence of events received and their timing. The work reported in this paper was supported in part by the National Science Foundation grants EHS-0208769, CSR-0509233, and NETS-0435060, and by MURI grant N00014-01-1-0576. †Liqian Luo and Tarek F. Abdelzaher are now with University of Illinois at Urbana-Champaign. ‡Tian He is now with University of Minnesota. Matters such as tuning protocol parameters for particular event scenarios or comparing performance of different protocols typ- ically require the same distributed event traces to be replayed (e.g., to ensure a common basis for comparison). To address this requirement, we provide an event recording and replay service that can capture and reproduce distributed events on demand. The service provides the abstraction of a completely repeatable environment as observed by the sensory subsystem for the sake of experimental testing. Communication properties remain stochastic. Hence, a separation is achieved between the effects of communication non-determinism and the effects of environmental non-repeatability in the study of sensor network protocols. The service is especially valuable in the study of rare, unsafe, or hard-to-reproduce events such as the motion of tracked animals through a sensor field. Our service is geared for the final stages of testing, typically performed in-field, where the effects of environmental realities can be studied. Early testing can use simulators that may be good for initial debugging since they allow fully controlled and repeatable experiments to be conducted. However, simulators are notoriously inaccurate when it comes to sensor network applications, since: (i) certain practical issues (e.g., the dis- tribution of radio irregularity) are not adequately captured in most available simulators, resulting in large discrepancies between simulation results and empirical measurements, and (ii) simulators do not faithfully mimic environmental event signatures which affects the performance of sensor network applications. The problem is especially severe in event-driven architectures, where application behavior is more sensitive to the sequence, timing, and parameters of events received. In addition to improving the repeatability of field testing, our service significantly reduces experimentation cost. In the absence of a recording and replay service, the investigators would have to either physically reproduce or passively wait for environmental events of interest, which entails additional costs. For example, the authors of [7] have developed a surveillance system that tracks persons and vehicles in the field. The need for walking or driving through the field hundreds of times while tuning an array of protocol parameters has proved to be a major practical impediment imposing a significant limitation on the rate at which experiments could be conducted in practice. EnviroLog, the asynchronous event recording and replay service described in this paper, provides a comprehensive solution to this problem. Most sensor platforms employ flash memory for persistent storage. For example, Mica, Mica2, Mica2Dot [15] and XSM [17] hardware platforms incorporate 128 KB internal flash for code storage and 512 KB external flash for other usage. EnviroLog logs environmental events into such persistent storage devices. Later on, in replay mode, EnviroLog replaces environmental inputs with retrieved logs and re-issues the logged events in their original time sequence as asynchronous inputs. In addition to environmental events, EnviroLog can also log system runtime status for future analysis by recording selected variable values at runtime as specified by the program- mer using simple annotations. EnviroLog has two unique features. First, EnviroLog can operate at any layer of an application. In other words, events recorded and replayed by EnviroLog are not limited to direct reflection of environmental events such as raw sensory read- ings. They can be any system-level events. This characteristic of EnviroLog enables the debugging or tuning of any specific layer using controlled and repeatable inputs from lower layers in an event-driven system. Second, EnviroLog provided a very friendly user interface. Users only need to add simple annotations before events or variables to be logged. Applica- tions with EnviroLog annotations can be compiled either into production code that ignores all EnviroLog annotations or into development code that allows on-demand recording and replay. The potential uses of EnviroLog include (i) in-field de- bugging and performance tuning of specific parameters of an application, (ii) collecting statistical results from a large number of repeated experiments, and (iii) generating traces for mixed simulation environments that accept experimental measurements as inputs. The remainder of the paper is organized as follows. Section II reviews related work. Section III describes the design goals and system architecture for EnviroLog. Section IV describes the implementation details. Section V evaluates EnviroLog, using XSM platforms, through a series of in-field experiments based on several sample applications provided by TinyOS [8] and a surveillance system [7] built upon TinyOS. Section VI concludes the paper. II. RELATED WORK In recent years, sensor network researchers have proposed several tools and middleware that aid the debugging and evaluation of sensor network applications. Generally, they can be divided into four categories: simulators, emulators, test-beds and services. The section compares EnviroLog with related work in each of these categories. Simulators are popular tools in debugging and evaluation of sensor network applications since they don’t usually require the deployment of sensor hardware. NS-2 [16], GloMoSim [24] and TOSSIM [11] are good examples. NS-2 is a discrete event simulator supporting various networking protocols over wired and wireless networks. GloMoSim focuses more on mobile, wireless networks. It allows comparison of multiple protocols at a given layer. TOSSIM is a simulator especially designed for TinyOS applications, which provides scalable simulations of sensor network software. Current simulators, however, do not adequately capture the real behavior of sensor networks. This is due to the difficulty in modeling practical imperfections such as radio irregularity as well as due to the lack of good models of environmental inputs. The ability of EnviroLog to record environmental events can presumably be utilized to improve these tools by importing recorded event data to simulate environmental inputs. Another category of debugging and performance evaluation tools in sensor networks is emulators that mimic sensor devices either in software or hardware. AVR JTAG ICE [1], a real time in-circuit emulator, is a good representative of hardware emulators. It uses the JTAG interface to enable a user to do real-time emulation of the microcontroller of sensor devices. A drawback of such in-circuit emulators is that they have to be physically connected to emulated devices, which causes logistical difficulties in conducting experiments especially for large-scale applications covering a wide field. Atemu [18] is a software emulator for AVR-processor-based systems that emulates AVR processors as well as other peripheral devices on the MICA2 platform. Like TOSSIM, Atemu also sim- ulates wireless communication. Such software emulators do not introduce the logistical difficulties exhibited in hardware emulators, but they are usually less realistic in reproducing network behavior. The final stages of debugging and performance tuning typically use actual testbeds to evaluate sensor network appli- cations. For example, Motelab [22] is a public testbed using MICA2 platforms, which allows users to upload executables and receive execution results via the Internet. Kansei [20] is another testbed. It employs XSM, MICA2, and Stargate platforms. EmStar [5] is a combination of emulators and testbeds for Linux-based sensor network applications, which runs applications using either a modeled radio channel or the channel of real nodes. EmTOS [6] extends EmStar to run TinyOS applications by compiling them into EmStar binaries. These testbeds ease the development and evaluation a lot without requiring full-scale deployment. However, they do not focus on repeatability of environmental inputs like EnviroLog does. We categorize all other software facilitating field tests of sensor network applications as services. EnviroLog belongs to this category. Monitoring tools such as Message Center [21] aid field tests by capturing messages in the air, filtering and displaying them to users. Closest to EnviroLog is TOSHILT [10], a middleware for hardware-in-the-loop testing. TOSHILT defines emulated stimuli to replace the real environmental events, so that applications can be evaluated repeatedly before the final deployment. Since TOSHILT uses synthetic and parametric event profiles, the detail of accuracy is less than what can be captured by EnviroLog. In addition, TOSHILT doesn’t provide abstractions similar to EnviroLog annotations to ease the integration of the middleware into user applications. All these difference make EnviroLog unique. In the following, EnviroLog is described in more detail. Record Stage Log modules Target modules Target modules Enviro- Log Flash Input Output Replay Stage Log modules Target modules Target modules Flash Input Output Enviro- Log Fig. 1. Main idea of EnviroLog III. DESIGN The major goal of EnviroLog is to enable experimental repeatability by recording and replaying environmental in- puts. From a program’s view, such inputs are essentially data streams that are transformed by each module of the program until they reach the modules at the topmost layer and become outputs. If we log the data stream generated by a module during the occurrence of an environmental event, and regenerate the same data stream later, from the perspective of the modules that consume the data, the environmental event is repeating itself. EnviroLog makes the assumption that data is transferred from one module to another module only through function calls and their parameters. This assumption conforms to the event-driven sensor acquisition convention of TinyOS, where sensory data is usually obtained through asynchronous events (defined as a type of function calls in TinyOS) with parameters containing the data. Based on this assumption, the desired data stream generated by a module can be recorded by logging all its issued function calls and their parameters. That founds the main idea that EnviroLog is built upon. Users of EnviroLog, through user interfaces, designate the modules that provide the data stream. These modules are called log modules. The modules that directly or indirectly consume the logged data stream are called target modules. As depicted in Figure 1, during the record stage, EnviroLog logs all function calls issued by the log modules into persistent storage devices such as a flash. During the replay stage, log modules are disabled. Instead, EnviroLog issues the previously recorded function calls at the right time and in the right sequence as recorded. Based on this main idea, the following subsections discuss the design of EnviroLog in more detail. A. Design Goals The design goals of EnviroLog are: • Effectiveness: Effectiveness of EnviroLog is measured by its ability to perform: (i) accurate event record and event replay, and (ii) reliable runtime status record and retrieve. • Efficiency: In sensor platforms, resource constraints (on both CPU and memory) are significant which makes it critical to use resources efficiently. EnviroLog is designed EnviroLog service Code depository Stage controller Record and replay Time synchronization Preprocessor Applications with EnviroLog annotation Applications with EnviroLog service incorporated Fig. 2. System architecture of EnviroLog with efficiency in mind so that it can be applied to complex applications that consume a significant fraction of available resources. • Simplicity: As a tool aimed to simplify the life of sensor network programmers, EnviroLog must be easy to use. In other words, simple user interfaces should be provided. Experiences tell us that simple tools tend to gain more popularity and persist longer while more complex tools sometimes run into usability barriers and become deserted. • Flexibility: There are always tradeoffs between perfor- mance and overhead. Since EnviroLog cannot achieve optimal performance and minimum overhead at the same time, it should allow users to flexibly select their specific performance requirements (e.g., high logging throughput) at the expense of incurring a corresponding overhead. EnviroLog should also be flexible enough to allow users to record and replay any application behavior not limited to direct inputs of environmental events. The above design goals provide guidelines throughout the design and implementation of EnviroLog. B. System Architecture Figure 2 illustrates the architecture of EnviroLog. Users indicate the set of events and variables to be recorded by inserting special annotations, called EnviroLog annotations, into applications. EnviroLog annotations are essentially the user interface of EnviroLog. Annotated applications are then processed by a preprocessor that translates EnviroLog annota- tions into real code, and, based on the annotations, integrates only the necessary modules from a code repository into the applications. The preprocessor and the code repository constitute EnviroLog services. As a result of the processing, application code is given the ability to record and replay specified events and to record and retrieve specified variable values that represent runtime status. C. User Interface Our design goal of simplicity calls for an easy user interface through which users are able to express the desired function- ality of EnviroLog in a simple and intuitive manner. The user specifies two main issues: asynchronous environ- mental event record and replay, and runtime status record and retrieve. The user interface design for the latter is easier since runtime status can be interpreted as values of variables at runtime. Such variables are simply annotated for logging. The former one is more complicated. As stated in the be- ginning of this section, EnviroLog supports environmental event record and replay by logging and regenerating data streams originating from environmental events. Since these data streams are transferred between modules through function calls and their parameters in most embedded systems such as TinyOS, we can log the behavior of a module by recording all issued function calls. Therefore, the only action an EnviroLog user is required to take is to specify a set of data-providing modules whose output data streams (issued function calls) are to be logged. The preprocessor takes the responsibility of enumerating function calls within the annotated modules and using APIs to log and replay each of them. To be more flexible, instead of specifying entire modules, advanced users are allowed to specify the exact function calls to be logged within a module. Different from most services that usually provide function call APIs, EnviroLog provides EnviroLog annotations as the user interface. Table I lists the basic set of EnviroLog anno- tations. The special characteristics of this user interface are: 1) EnviroLog annotations are simple to use. Users only need to insert annotations before function calls without worrying about details such as how these function calls are recorded, what data structures are used, and how and when to re-execute them when replaying. The preprocessor takes the responsibility to automatically generate code and integrate modules from the code depository to handle these details. 2) EnviroLog annotations take the form of comments that are ignored by the regular language compiler. This allows users to freely switch between original applications without EnviroLog integrated and EnviroLog-augmented applications. Annotated applications, when directly compiled, generate exe- cutables that do not include EnviroLog support. Alternatively, if they are processed by the EnviroLog preprocessor before compiling, the resulting executables are able to record and replay/retrieve the specified set of function calls and variable values based on user annotations. To log environmental events, one option is to log the inputs of sensor drivers. However, users may focus on the evaluation and tuning of a specific layer higher than the layer of sensor drivers, thus requiring repeatable inputs to this layer. To fulfill such requirements, EnviroLog allows users to use EnviroLog annotations at any layer to enable repeatable input to that specific layer without interference from lower layers. Though EnviroLog is geared for recording and replaying events of interest, it is also possible to choose whether to record the radio channel conditions using the user interface. If function calls