Источник: http://www.cs.berkeley.edu/~pal/pubs/tossim-sensys03.pdf

Accurate and scalable simulation has historically been a key enabling factor for systems research. We present TOSSIM, a simulator for TinyOS wireless sensor networks. By exploiting the sensor network domain and TinyOS’s design, TOSSIM can capture network behavior at a high fidelity while scaling to thousands of nodes. By using a probabilistic bit error model for the network, TOSSIM remains simple and efficient, but expressive enough to capture a wide range of network interactions. Using TOSSIM, we have discovered several bugs in TinyOS, ranging from network bitlevel MAC interactions to queue overflows in an ad-hoc routing protocol. Through these and other evaluations, we show that detailed, scalable sensor network simulation is possible.

Development of the right simulation tools has been a key step in systems research progress for several areas. In general, simulation can provide a way to study system design alternatives in a controlled environment, explore system configurations that are difficult to physically construct, and observe interactions that are difficult to capture in a live system. A debate often emerges over how much fidelity is required to observe critical phenomena, since simulation cost typically increases quickly with the level of detail. Several times in the past, we have seen a tool that captured the essential elements of the area of study; these tools dramatically accelerated progress in emerging research areas. For example, SimOS [24] used binary rewriting techniques to provide enough detail and yet enough speed and flexibility to allow workload-driven evaluation of machine architectures and operating systems for multiprocessors by running whole programs. ns-2 [2], using an object approach, provided a common toolbox for studying a wide range of network protocols and implementations against various traffic models. Proteus [5] provided broad feedback on the design of parallel programs.

The event-driven nature of sensor networks means that testing an individual mote is insufficient. Programs must be tested at scale and in complex and rich conditions to capture a wide range of interactions. Deploying hundreds of motes is a daunting task; the focus of work shifts from research to maintenance, which is time-consuming due to the failure rate of individual motes. A simulator can deal with these difficulties, by providing controlled, reproducible environments, by enabling access to tools such as debuggers, and by postponing deployment until code is well tested and algorithms are understood. In this section, we provide background on TinyOS, presenting points of its design that are of particular interest for simulation. TinyOS is an operating system specifically designed for sensor networks. It has a component-based programming model, provided by the nesC language [9], a dialect of C. TinyOS is not an OS in the traditional sense. It is a programming framework for embedded systems and set of components that enable building an applicationspecific OS into each application.

A TinyOS program is a graph of components, each of which is an independent computational entity. Each TinyOS component has a frame, a structure of private variables that can only be referenced by that component. Components have three computational abstractions: commands, events, and tasks. Commands and events are mechanisms for inter-component communication, while tasks are used to express intra-component concurrency. A command is typically a request to a component to perform some service, such as initiating a sensor reading, while an event signals the completion of that service. Events may also be signaled asynchronously, for example, due to hardware interrupts or message arrival. From a traditional OS perspective, commands are analogous to downcalls and events to upcalls. Commands and events cannot block: rather, a request for service is split phase in that the request for service (the command) and the completion signal (the corresponding event) are decoupled. The command returns immediately and the event signals completion at a later time.

TOSSIM captures the behavior and interactions of networks of thousands of TinyOS motes at network bit granularity. Figure 3 shows a graphical overview of TOSSIM. The TOSSIM architecture is composed of five parts: support for compiling TinyOS component graphs into the simulation infrastructure, a discrete event queue, a small number of re-implemented TinyOS hardware abstraction components, mechanisms for extensible radio and ADC models, and communication services for external programs to interact with a simulation. TOSSIM takes advantage of TinyOS’s structure and whole system compilation to generate discrete-event simulations directly from TinyOS component graphs. It runs the same code that runs on sensor network hardware. By replacing a few low-level components (e.g., those shaded in Figure 3), TOSSIM translates hardware interrupts into discrete simulator events; the simulator event queue delivers the interrupts that drive the execution of a TinyOS application. The remainder of TinyOS code runs unchanged. TOSSIM uses a very simple but surprisingly powerful abstraction for its wireless network. The network is a directed graph, in which each vertex is a node, and each edge has a bit error probability. Each node has a private piece of state representing what it hears on the radio channel. This abstraction allows testing under perfect transmission conditions (bit error rate is zero), can capture the hidden terminal problem (for nodes a,b,c, there are edges (a, b) and (b, c) but no edge (a, c)), and can capture many of the different problems that can occur in packet transmission (start symbol detection failure, data corruption, etc.).

We evaluate how well TOSSIM meets the four core needs of a sensor network simulator: fidelity, completeness, bridging, and scalability. To evaluate its fidelity and completeness, we used Surge, a sample application that comes packaged with TinyOS. Surge is a simple send/report program; nodes periodically collect sensor readings and route them to a base station, which collects and graphically displays them for the user.

Simultaneously meeting all of the requirements posed to a sensor network simulator is difficult. Several other sensor network simulators have been proposed, but none meet all of the requirements as TOSSIM does. ns-2 [2] is the predominant discrete event simulator used in network systems. It simulates networks at the packet level, and allows a wide range of heterogeneous network configurations. Complex models to determine packet loss rates from physical topologies are written in Tcl or C, separate from a protocol implementation. ns- 2 is, as its name suggests, a network simulator, while TOSSIM is a TinyOS simulator that provides a network model. Numerous sensor network research efforts have evaluated algorithms with simulations using ns-2. For example, research on geographic hash tables used a 50-200 node simulation with an 802.11 MAC[23]. Simulations for the PSFQ routing protocol used 25 nodes with 2Mbps links[26]; there are other examples of an 802.11 MAC being used in ns-2 to simulate sensor networks[30], although initial evidence indicates it is inappropriate[13]. Additionally, ns-2 does not model application behavior. For trace driven simulations of layered protocols, this is appropriate. In sensor networks, however, protocols and applications interact; for example, protocol layers are often crossed or ignored to provide time-dependent aggregation of sensor readings, following a model of integrated layer processing instead of strict layering [6]. ns-2 is inappropriate to model this sort of behavior; while ns-2 is a much more general network simulator, TOSSIM simulates applications, the network, and their interaction, thereby providing a degree of fidelity, bridging, and completeness that ns-2 cannot

TinyOS’s event-based execution maps easily to discrete event simulation. Unfortunately, it is unlikely that TOSSIM would be effective for simulating thread-based systems; the cost of the large number context switches (even if in user-land) would be prohibitive. Additionally, maintaining accurate time across motes and interrupt modeling in the presence of possible spin loops would require the same techniques as capturing preemption – a tremendous performance cost. We tackled the problem of testing and analyzing sensor network applications, and have demonstrated that it is possible to build scalable, high fidelity simulations of full sensor network applications. The number of bugs and flaws we found in core TinyOS services suggests that simulation should be an important phase in application development, and the ease with which one can transition between deployments and simulation means doing so is not prohibitive. Our hope is that TOSSIM will be of great use to the sensor network community, enabling research in this new and wide domain.

1. D. Braginsky and D. Estrin. Rumor Routing Algorithm for Sensor Networks. In Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, 2002.
2. E. A. Brewer, C. Dellarocas, A. Colbrook, and W. E. Weihl. PROTEUS: A High-Performance Parallel-Architecture Simulator. Measurement and Modeling of Computer System, pages 247–8, 1992.
3. D. D. Clark and D. L. Tennenhouse. Architectural Considerations for a New Generation of Protocols. In Proceedings of SIGCOMM, september 1990.
4. J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B. Greenstein, T. Schoellhammer, T. Stathopoulos, and D. Estrin. Emstar: An environment for developing wireless embedded systems software. Technical Report Technical Report 0009, CENS, Mar. 2003.