We advocate a novel programming approach we call slotted programming that not only addresses the specific hardware capabilities of sensor nodes, but also facilitates coding through a truly modular design. The approach is based on the temporal decoupling of the different tasks of a sensor node such that at any time at most one task is active. In contrast to traditional sensor network programming, slotted programming guarantees that each of these tasks can be implemented as an independent software module, simplifying not only the coding and testing phase, but also the code reuse in a different context. In addition, we believe that the proposed approach is highly qualified for energy efficient and real time applications. To substantiate our claims, we have implemented slotos, an extension to TinyOS that supports slotted programming. Within this framework, we demonstrate the advantages of the slotted programming paradigm.

Greedy routing is a novel routing paradigm where messages are always forwarded to the neighbor that is closest to the destination. Our main result is a polynomial-time algorithm that embeds combinatorial unit disk graphs (CUDGs - a CUDG is a UDG without any geometric information) into O(log2n)- dimensional space, permitting greedy routing with constant stretch. To the best of our knowledge, this is the first greedy embedding with stretch guarantees for this class of networks. Our main technical contribution involves extracting, in polynomial time, a constant number of isometric and balanced tree separators from a given CUDG. We do this by extending the celebrated Lipton-Tarjan separator theorem for planar graphs to CUDGs. Our techniques extend to other classes of graphs; for example, for general graphs, we obtain an O(log n)-stretch greedy embedding into O(log2n)-dimensional space. The greedy embeddings constructed by our algorithm can also be viewed as a constant-stretch compact routing scheme in which each node is assigned an O(log3n)-bit label. To the best of our knowledge, this result yields the best known stretch-space trade-off for compact routing on CUDGs. Extensive simulations on random wireless networks indicate that the average routing overhead is about 10%; only few routes have a stretch above 1.5.

We present YETI, an Eclipse plug-in providing support for TinyOS development. YETI provides features well-known from development environments for other languages such as syntax highlighting, code completion and error detection. Furthermore, it includes an additional set of tools which are designed to ease the TinyOS development process for both newcomers and experienced developers. The plugin seamlessly integrates with the existing TinyOS toolchain and provides debugging support on the target platform using a JTAG hardware adapter.

We reconsider the problem of geographic routing in wireless ad hoc networks. We are interested in local, memoryless routing algorithms, i.e. each network node bases its routing decision solely on its local view of the network, nodes do not store any message state, and the message itself can only carry information about O(1) nodes. In geographic routing schemes, each network node is assumed to know the coordinates of itself and all adjacent nodes, and each message carries the coordinates of its target. Whereas many of the aspects of geographic routing have already been solved for 2D networks, little is known about higher-dimensional networks. It has been shown only recently that there is in fact no local memoryless routing algorithm for 3D networks that delivers messages deterministically. In this paper, we show that a cubic routing stretch constitutes a lower bound for any local memoryless routing algorithm, and propose and analyze several randomized geographic routing algorithms which work well for 3D network topologies. For unit ball graphs, we present a technique to locally capture the surface of holes in the network, which leads to 3D routing algorithms similar to the greedy-face-greedy approach for 2D networks.

This paper studies routing schemes and their distributed construction in limited wireless networks, such as sensor or mesh networks. We argue that the connectivity of such networks is well captured by a constant doubling metric and present a constant stretch multicast algorithm through which any network nodeucan send messages to an arbitrary receiver setU. In other words, we describe a distributed approximation algorithm which is only a constant factor off the NP-hard minimum Steiner tree onucupU. As a building block for the multicasting, we construct a 1 + epsiv stretch labeled routing scheme with label size O(log ominus) and storage overhead O(1/epsiv)alpha(log ominus)(O(alpha) + log Delta), where ominus is the diameter of the network, Delta the maximum degree of any network node, andalphaa constant representing the doubling dimension of the network. In addition to unicast and multicast, we present a constant approximation for anycasting on the basis of radic(6)-approximate distance queries. We provide a distributed algorithm to construct the required labeling and routing tables.

ALGO is a distributed location service to track the position of mobile nodes and to route messages between any two nodes. The lookup of nodes is achieved by searching in a hierarchy of pointers that each node maintains. We show that ALGO has constant stretch for lookup requests. In contrast to previous work, we consider a concurrent setup where nodes are truly mobile and move even while messages are being routed towards them. We prove correctness and efficiency of ALGO and determine the maximum speed at which the nodes might move, which is up to 1/15 of the routing speed. To the best of our knowledge, this is the first work that bounds the node speed, a necessity to prove the success of a lookup algorithm. We verified our theoretical results through extensive simulation and show that the average lookup stretch is around 6.