In this paper, we describe the design and implementation of a distributed operating system for ad hoc networks. Our system simplifies the programming of ad hoc networks and extends total system lifetime by making the entire network appear as a single virtual machine. It automatically and transparently partitions applications into components and dynamically finds them a placement on nodes within the network to reduce energy consumption and to increase system longevity. This paper describes our programming model, outlines the design and implementation of our system and examines the energy efficiency of our approach through extensive simulations as well as validation of a deployment on a physical testbed. We evaluate practical, power-aware, general-purpose algorithms for component placement and migration, and demonstrate that they can significantly increase system longevity by effectively distributing energy consumption and avoiding hotspots.

We analyze the asymptotic cost of discovering a route within a flat ad hoc network and we show that one can discover a route with cost that is proportional only to the area of the network and that is independent of the number of network nodes. Furthermore, we show that this is optimal and that bordercasting (a query propagation protocol where a node retransmits a query to a set of nodes at some hop-distance away) possesses this density-independence property. We present the design of bordercast and the associated maintenance protocols, and we evaluate their performance. In particular, we highlight that the aggregation of local information by boredercasting at each network node is a fundamental building block for the construction of scalable protocols in flat ad hoc networks.

Discrete event simulators are important scientific tools and their efficient design and execution is the subject of much research. In this paper, we propose a new approach for constructing simulators that leverages virtual machines and combines advantages from the traditional systems-based and language-based simulator designs. We introduce JiST, a Java-based simulation system that executes discrete event simulations both efficiently and transparently by embedding simulation semantics directly into the Java execution model. The system provides standard benefits that the modern Java runtime affords. In addition, JiST is efficient, out-performing existing highly optimized simulation runtimes. As a case study, we illustrate the practicality of the JiST framework by applying it to the construction of SWANS, a scalable wireless ad hoc network simulator. We simulate million node wireless networks, which represents two orders of magnitude increase in scale over what existing simulators can achieve on equivalent hardware and at the same level of detail. Copyright © 2005 John Wiley & Sons, Ltd.