Significant research effort has been directed towards the design and performance analysis of imperfect scheduling policies for wireless networks. These imperfect schedulers are of interest despite being sub-optimal, as they allow for more tractable implementation at the expense of some loss in performance. However much of this prior work takes a uniform scaling approach to analyzing scheduling performance, whereby the performance of a scheduling policy is characterized in terms of a single scalar quantity, the efficiency-ratio. While suitable for characterizing worst-case performance, this approach limits one's ability to understand the different extents of performance degradation that may be experienced by different links in a network. Such an understanding is very valuable when average performance is of greater interest than the worst-case, or when certain links are more important than others. Furthermore, once one approaches scheduler design with non-uniform performance guarantees in mind, one finds that simple modifications to well-known scheduling algorithms can yield substantially improved non-uniform scaling results compared to the original algorithms. In this paper, we make a comprehensive case for adopting such an approach by presenting non-uniform scaling results for a set of algorithms that are variants of well-known algorithms from the class of maximal schedulers.

This paper studies the reliable broadcast problem in a radio network with locally bounded failures. We present a sufficient condition for achievability of reliable broadcast in a general graph subject to Byzantine/crash-stop failures. We then consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. For the Byzantine failure model, we describe an algorithm which is optimal for the grid network model, as it tolerates faults up to a previously established upper bound for this model. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one-fourth fraction of nodes in any neighborhood are faulty. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty.

We consider the problem of reliable broadcast in a wireless network in which nodes are prone to failure. Each node can fail independently with probability p. Failures are permanent. The primary focus is on Byzantine failures, but we also handle crash-stop failures. We consider two network models: a regular grid, and a random network. Our necessary and sufficient conditions for the Byzantine failure model indicate that p should be less than frac12, and the critical node degree is Theta(dmin+(lnn/ln(1/2p))+ln(1/2(1-p))) (where dminis the minimum node degree associated with a non-empty neighborhood, and is a small constant). For a random network we prove that, for failure probability less than frac12, the critical average degree for reliable broadcast is O(lnn/frac12-p+frac12ln(1/2(1-p))). We briefly discuss the issue of crash-stop failures for which we have results that improve upon previously existing results for this model, when p approaches 0. We also identify an interesting similarity in the structure of various known results in the literature pertaining to a set of related problems in the realm of connectivity and reliable broadcast.

This paper argues for the need to address the issue of multi-channel network performance under constraints on channel switching. We present examples from emergent directions in wireless networking to motivate the need for such a study, and introduce some models to capture channel switching constraints. For some of these models, we study connectivity and capacity of a wireless network comprising n randomly deployed nodes, equipped with a single interface each, when there are c=O(logn) channels of equal bandwidth W/c available. We consider an adjacent (c,f) channel assignment where a node may switch between f adjacent channels, but the adjacent channel block is randomly assigned. We show that the per-flow capacity for this channel assignment model is Theta(Wradic(f/cnlogn)). We then show the adjacent (c,2) assignment maps to the case of untuned radios. We also consider a random (c,f) assignment where each node may switch between a pre-assigned random subset of f channels. For this model, we prove that per-flow capacity is O(Wradic(prnd/nlogn)) (where prnd=1-(1-f/c)(1-f/(c-1))...(1-f/(c-f+1)) and Omega(Wradic(f/cnlogn))).

Wireless networks are increasingly being used for latency-sensitive applications that require data delivery to be timely, efficient and reliable. This trend is primarily driven by the proliferation of wireless networks of real-time data-gathering sensor-actuator devices. This has led to a strong need to bring real-time concerns to the forefront of an integrated research thrust into wireless real-time systems. In this paper, we introduce and analyze a specific instance of the rich set of problems in this domain. We consider a wireless network serving real-time flows in which the underlying physical layer provides multiple transmission rates. Higher rates have more stringent SINR requirements and thus represent a trade-off between raw transmission speed and packet error rate. We adopt a first principles approach to the design of optimal real-time scheduling algorithms for such a multi-rate wireless network. We illustrate the inherent complexities of the problem through examples and obtain provably optimal structural results. We then characterize the optimal policy for an approximate model. Our theoretical analysis provides guidelines for heuristic scheduler design. Our initial work indicates that this is a rich problem domain with the potential for a unifying theory that integrates real-time requirements into multi-rate wireless network design.

We argued for the need to study the performance of multi-channel networks in situations where there are constraints on channel switching. We proposed some constraint models in [1] to capture some expected constraints, and analyzed two such models, viz., adjacent (c,f) assignment and random (c,f) assignment. We studied the impact of such restricted switching, quantified by the parameter f (where f is the number of channels an individual node may switch to) in the regime c = O(log n). One of our proposed models was termed random (c,f) assignment.

First responders equipped with PDAs in disaster recovery scenarios may need to make decisions that select the best out of multiple options. Each of these options may originate from different parts of the network (e.g., risk assessment of various entrances to a collapsed building). Yet the highest priority option needs to be spread to all nodes within a time deadline and in an efficient manner, i.e., by preventing lower priority options from spreading too far. We define this problem as PriorityCast, and study a wide range of possible solutions. The emphasis is on solutions that are scalable, and resilient to unreliability and unpredictability. Our basic scheme, called flood and suppress, suppresses lower priority options from being forwarded by a node that has seen other higher priority options. We then augment this basic scheme using probabilistic approaches, background gossiping techniques, and delayed propagation. We quantify the impact of using various combinations of the mentioned approaches, by presenting mathematical analysis for the flood and suppress protocol, and evaluating a suite of composable PriorityCast protocols via simulations. The results provide insight into the feasibility and scalability of this class of solutions. While the focus of this paper is on the PriorityCast problem, these solutions are also relevant as potential building blocks for other distributed operations in ad-hoc networks

We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task.

It is vital to support concurrent applications sharing a wireless sensor network in order to reduce the deployment and administrative costs, thus increasing the usability and efficiency of the network. We describe Melete 1 , a system that supports concurrent applications with efficiency, reliability, flexibility, programmability, and scalability. Our work is based on the Maté virtual machine [1] with significant modifications and enhancements. Melete enables reliable storage and execution of concurrent applications on a single sensor node. Dynamic grouping is used for flexible, on-the-fly deployment of applications based on contemporary status of the sensor nodes. The grouping procedure itself is programmed with the TinyScript language. A group-keyed code dissemination mechanism is also developed for reliable and efficient code distribution among sensor nodes. Both analytical and simulation results are presented to study the impact of several key parameters and optimization techniques on the code dissemination mechanism. Simulation results indicate satisfactory scalability of our techniques to both application code size and node density. The usefulness and effectiveness of Melete is also validated by empirical study.

We consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. We improve on previously proved bounds for the number of tolerable Byzantine faults [6]. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one fourth fraction of nodes in any neighborhood are faulty, and impossible otherwise. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty. In particular, we establish exact thresholds under a specific distance metric.