We investigate optimal channel assignment algorithms that maximize per node throughput in dense multi-channel multi-radio (MC-MR) wireless networks. Specifically, we consider an MC-MR network where all nodes are within the transmission range of each other. This situation is encountered in many real-life settings such as students in a lecture hall, delegates attending a conference, or soldiers in a battlefield. In this scenario, we show that intelligent assignment of the available channels results in a significantly higher per node throughput. We first propose a class of channel assignment algorithms, parameterized by T (the number of transceivers per node), that can achieve Θ(1/N1/T) per node throughput using Θ(TN1-1/T) channels. In view of practical constraints on T, we then propose another algorithm that can achieve Θ((1/log2n)2) per node throughput using only two transceivers per node. Finally, we identify a fundamental relationship between the achievable per node throughput, the total number of channels used, and the network size under any strategy. Using analysis and simulations, we show that our algorithms achieve close to optimal performance at different operating points on this curve. Our work has several interesting implications on the optimal network design for dense MC-MR wireless networks.

We present a transport protocol whose goal is to reduce power consumption without compromising delivery requirements of applications. To meet its goal of energy efficiency, our transport protocol (1) contains mechanisms to balance end-to-end vs. local retransmissions; (2) minimizes acknowledgment traffic using receiver regulated rate-based flow control combined with selected acknowledgements and in-network caching of packets; and (3) aggressively seeks to avoid any congestion-based packet loss. Within a recently developed ultra low-power multi-hop wireless network system, extensive simulations and experimental results demonstrate that our transport protocol meets its goal of preserving the energy efficiency of the underlying network.

Existing slotted channel access schemes in wireless networks assume that slot boundaries at all nodes are synchronized. In practice, relative clock drifts among nodes cause slot misalignment over time and can result in catastrophic data loss in such systems. We propose a simple network-wide slot synchronization scheme (Slot-Sync and Slot-Resync) suitable for duty-cycling wireless sensor networks. The proposed scheme attains high accuracy by circumventing dominant sources of error inherent in traditional time synchronization protocols. At moderate duty-cycle frequencies, the proposed scheme also has the unique advantage of eliminating re-synchronization (re-sync) overhead completely, thereby achieving slot re-sync essentially for free. We provide an energy efficient slot guard time and re- sync interval design for the proposed scheme and analyze several spanning tree structures for slot-alignment message propagation. In addition, we derive upper bounds on the synchronization (sync) error for a family of trees. Through simulations, we compare the spanning trees we propose to those used for time sync in literature and show up to 80% reduction in sync error and up to 70% reduction in energy needed for slot-alignment message propagation by choosing appropriate tree structures.

Mobile ad hoc networks are typically designed and evaluated in generic simulation environments. However the real conditions in which these networks are deployed can be quite different in terms of RF attentution, topology, and traffic load. Furthermore, specific situations often have a need for a network that is optimized along certain characteristics such as delay, energy or overhead. In response to the variety of conditions and requirements, ad hoc networking protocols are often designed with many modifiable parameters. However, there is currently no methodical way for choosing values for the parameters other than intuition and broad experience. In this paper we investigate the use of genetic algorithms for automated selection of parameters in an ad hoc networking system. We provide experimental results demonstrating that the genetic algorithm can optimize for different classes of operating conditions. We also compare our genetic algorithm optimization against hand-tuning in a complex, realistic scenario and show how the genetic algorithm provides better performance.

Directional antennas offer tremendous potential for improving the performance of ad hoc networks. Harnessing this potential, however, requires new mechanisms at the medium access and network layers for intelligently and adaptively exploiting the antenna system. While recent years have seen a surge of research into such mechanisms, the problem of developing a complete ad hoc networking system, including the unique challenge of real-life prototype development and experimentation has not been addressed. In this paper, we present utilizing directional antennas for ad hoc networking (UDAAN). UDAAN is an interacting suite of modular network- and medium access control (MAC)-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms-a directional power-controlled MAC, neighbor discovery with beamforming, link characterization for directional antennas, proactive routing and forwarding-all working cohesively to provide the first complete systems solution. We also describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented both for a specific scenario and using random mobility models. For the range of parameters studied, our results show that UDAAN can produce a very significant improvement in throughput over omnidirectional communications.

Energy efficiency is an important design criterion for the development of sensor networking protocols involving data dissemination and gathering. In-network processing of sensor data, aggregation, transmission power control in radios, and periodic cycling of node wake-up schedules are some techniques that have been roposed in the sensor networking literature for achieving energy efficiency. Owing to the broadcast nature of the wireless channel many nodes in the vicinity of a sender node may overhear its packet transmissions even if they are not the intended reci ients of these transmissions. Reception of these transmissions can result in unnecessary expenditure of battery energy of the recipients. In this paper,we investigate the impact of overhearing transmissions on total energy costs during data gathering and dissemination and attempt to minimize them systematically.We model the minimum energy data gathering problem as a directed minimum energy spanning tree problem where the energy cost of each edge in the wireless connectivity graph is augmented by the overhearing cost of the corresponding transmission. We observe that in dense sensor networks, overhearing costs constitute a significant fraction of the total energy cost and that computing the minimum spanning tree on the augmented cost metric results in energy savings, especially in networks with non-uniform s atial node distribution. We also study the impact of this new metric on the well known energy-efficient dissemination (also called broadcasting) algorithms for multihop wireless networks.We show via simulation that through this augmented cost metric, gains in energy efficiency of 10%or more are ossible without additional hardware and minimal additional complexity.

In this paper, we present UDAAN ("utilizing directional antennas for ad hoc networking"), which is an interacting suite of modular network- and MAC-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms - a directional power-controlled MAC, neighbor discovery with beamforming, link characterization with directional antennas, proactive routing and forwarding all working cohesively to provide the first complete systems solution. We describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented. For the range of parameters studied, our results show that UDAAN can produce up to a factor-of-10 improvement in throughput over omni-directional communications.

Since widespread commercial use of wireless technology is still many years off, there is very little data to determine what constitutes an accurate model for wireless traffic. Many studies have shown that landline network traffic does not follow a traditional Poisson model but instead exhibits self-similar behavior. Previous papers have introduced and analyzed the performance of fundamental classes of energy-conserving protocols under traditional Poisson models. In order to evaluate these protocols under a distribution which might more accurately depict future wireless network traffic, we use simulation and proven models to consider the trade-off between energy and delay under a self-similar arrival distribution.

A myriad of applications are emerging, in which energy conservation is a critical system parameter for communications. Radio frequency identification device (RFID) networks, smart cards, and even mobile computing devices, in general, need to conserve energy. In RFID systems, nodes are small battery-operated inexpensive devices with radio receiving/transmitting and processing capabilities, integrated into the size of an ID card or smaller. These identification devices are designed for extremely low-cost large-scale applications, such that the replacement of batteries is not feasible. This imposes a critical energy constraint on the communications (access) protocols used in these systems, so that the total time a node needs to be active for transmitting or receiving information should be minimized. Among existing protocols, classical random access protocols are not energy conserving, while deterministic protocols lead to unacceptable delays. This paper deals with designing communications protocols with energy constraint, in which the number of time slots in which tags need to be in the active state is minimized, while the access delay meets the applications constraints. We propose three classes of protocols which combine the fairness of random access protocols with low energy requirements.

Mobile communications implies reliance on a self-contained, portable power source, error-prone fading radio channels and subsequent need for acknowledgments. We propose two energy-conserving variants of the selective repeat ARQ protocol, which reduce the number of acknowledgments sent by the mobile node. The protocols are compared to previously described energy-conserving go-back-N ARQ protocols as well as classical approaches and shown to maintain favorable delay and throughput performances.

This paper deals with the design of a communications protocol which operates under an energy constraint, in which the fraction of timeslots in which tags need to be in the active (awake) state is minimized, and the access delay meets the applications constraints. We present a new approach to this problem, a pseudo-random protocol, which combines the fairness from random access protocols with the low energy requirements of classical TDMA. Considering an analytical model as well as simulations of the system behavior for the cases of uniformly and non-uniformly distributed traffic destinations, we show that in addition to fairness, and low energy requirements the proposed protocol provides low access delays.