In this paper, we propose to address the energy efficient routing problem in multi-hop wireless networks with accumulative relay. In the accumulative relay model, partially overheard signals of previous transmissions for the same packet are used to decode it using a maximal ratio combiner technique [J.G. Proakis, 2001]. Therefore, additional energy saving can be achieved over traditional energy efficient routing. The idea of accumulative relay originates from the study of relay channel in information theory with a main focus on network capacity. It has been independently applied to minimum-energy broadcasting in L.G. Manish Agrawal et al. (2004), I. Maric and R. Yates (2002). We formulate the minimum energy accumulative routing problem (MEAR) and study it. We obtain hardness of approximation results counterbalanced with good heuristic solutions which we validate using simulations. Without energy accumulation, the classic shortest path (SP) algorithm finds the minimum energy path for a source-destination pair. However, we show that with energy accumulation, the SP can be arbitrarily bad. We turn our attention to heuristics and show that any optimal solution of MEAR can be converted to a canonical form - wave path. Armed with this insight, we develop a polynomial time heuristic to efficiently search over the space of all wavepaths. Simulation results show that our heuristic can provide more than 30% energy saving over minimum energy routing without accumulative relay. We also discuss the implementation issues of such a scheme.

We introduce a notion of universality in the context of optimization problems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain quality of goodness for all possible completions of the partial information set. Universal variants of optimization problems can be defined that are both natural and well-motivated. We consider universal versions of three classical problems: TSP, Steiner Tree and Set Cover.We present a polynomial-time algorithm to find a universal tour on a given metric space over n vertices such that for any subset of the vertices, the sub-tour induced by the subset is within O(log4n/log log n) of an optimal tour for the subset. Similarly, we show that given a metric space over n vertices and a root vertex, we can find a universal spanning tree such that for any subset of vertices containing the root, the sub-tree induced by the subset is within O(log4n/log log n) of an optimal Steiner tree for the subset. Our algorithms rely on a new notion of sparse partitions, that may be of independent interest. For the special case of doubling metrics, which includes both constant-dimensional Euclidean and growth-restricted metrics, our algorithms achieve an O(log n) upper bound. We complement our results for the universal Steiner tree problem with a lower bound of Ω(log n/log log n) that holds even for n vertices on the plane. We also show that a slight generalization of the universal Steiner Tree problem is coNP-hard and present nearly tight upper and lower bounds for a universal version of Set Cover.

We introduce a new power control scheme, for IEEE 802.11-like MAC protocols. Our scheme carefully combines collision avoidance and spatial reuse. Although many power control schemes were proposed for IEEE 802.11, to the best of our knowledge, our scheme is the first to achieve significant improvements for network throughput and energy efficiency simultaneously (up to 40% throughput increase and 3 times more data delivery with the same amount of energy), while adhering to the single-channel, single-transceiver design rule. Furthermore, our scheme solves the fairness problem identified in (J. Monks et al, IEEE INFOCOM, 2003), i.e., IEEE 802.11 and some power control schemes deliver more packets for short distance source-destination pairs than for long distance pairs. Thus, our scheme also improves the bit-metre/sec metric (by up to 70%). Our proposed scheme belongs to a more general class of power control schemes, that we extensively simulate. We also provide a theoretical analysis to justify our approach and simulation results.

An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any fixed infrastructure. Indeed, an important task of an ad hoc network is to determine an appropriate topology over which high-level routing protocols are implemented. Furthermore, since the underlying topology may change with time, we need to design routing algorithms that effectively react to dynamically changing network conditions.The aim of this paper is to explore the limits of communication in wireless mobile networks, concentrating on local-control algorithms for topology control and routing. We analyze the performance of the algorithms under three measures: throughput, which is the rate at which packets can be delivered, space overhead, i.e. the space necessary to buffer packets, and the total energy consumed due to packet transmissions. Energy consumption is an important performance measure for ad hoc networks since the battery power of mobile nodes is usually limited.Towards topology control, we show that for any distribution of nodes in the 2-dimensional Euclidean plane, a simple local algorithm allows to establish and maintain a connected constant degree overlay network that contains energy-efficient paths between every pair of nodes. Towards routing, we present a local routing algorithm that works for arbitrary overlay networks without transmission interference. We show that for any sequence of network changes and packet injections the algorithm is within a constant factor of the optimal, with respect to both throughput and energy, when compared to what a best possible routing algorithm can achieve under the same sequence of network changes and injection. We then combine the topology control and routing algorithms to obtain competitive wireless communication algorithms that account for transmission interference, an important performance-limiting aspect of wireless communication.