In this paper, we consider a set of n mobile wireless nodes, which have no information about each other. The only information a single node holds is its current location and future mobility plan. We develop a two-phase distributed self-stabilizing scheme for producing a bounded hop-diameter communication graph. In the first phase, nodes construct a temporary underlying topology and disseminate their current location and mobility plans. This is followed by a second phase, in which nodes construct the desired topology under two modes: static and dynamic. The static mode provides a fixed topology which does not change in spite of node movements; the dynamic mode allows the topology to change; however, the hop-diameter remains the same. We provide an O(λ,λ2)-bicriteria approximation (in terms of total energy consumption and network lifetime, respectively) algorithm in the static mode: for an input parameter λ, we construct a static h-bounded hop communication graph, where h=n/λ + log λ. In the dynamic mode, given a parameter h, we construct an optimal (in terms of network lifetime) h-bounded hop communication graph when every node moves with constant speed in a single direction along a straight line during each time interval. Our results are validated through extensive simulations.

We study the problem of spanner construction in wireless ad-hoc networks through power assignments under two spanner models—distance and energy. In particular, we are interested in asymmetric power assignments so that the induced communication graph holds good distance and energy stretch factors simultaneously. In addition, we consider the following optimization objectives: low total energy consumption, low interference level, low hopdiameter, and high network lifetime. Two node deployment scenarios are studied: random and deterministic. For n random nodes distributed uniformly and independently in a unit square, we present several power assignments with varying construction-time complexities. The results are based on various geometric properties of random points and shortest path tree constructions. Due to the probabilistic nature of this scenario, the probability of our results converges to one as the number of network nodes, n , increases. For the deterministic case, we present two power assignments with nontrivial bounds. These are established in addition to shortcut edges that satisfy desired threshold stretch. To the best of our knowledge, these are the first results for spanner construction in wireless ad-hoc networks with provable bounds for both energy and distance metrics simultaneously. Our power assignments, in addition, try optimizing additional network properties, such as network lifetime, interference, and hop diameter.

This paper studies the bottleneck link capacity under the Gaussian channel model in strongly connected random wireless ad hoc networks, withnnodes independently and uniformly distributed in a unit square. We assume that each node is equipped with two transceivers (one for transmission and one for reception) and allow all nodes to transmit simultaneously. We draw lower and upper bounds, in terms of bottleneck link capacity, for homogeneous networks (all nodes have the same transmission power level) and propose an energy-efficient power assignment algorithm (CBPA) for heterogeneous networks (nodes may have different power levels), with a provable bottleneck link capacity guarantee of Ω(Blog(1+1/√nlog2n)), whereBis the channel bandwidth. In addition, we develop a distributed implementation of CBPA withO(n2) message complexity and provide extensive simulation results.

Beamforming is a signal processing technique which is aimed at focusing the transmission energy in the desired direction through the use of antenna arrays and phase alignment. In this paper we explore the benefits of using distributed antenna beamforming in multi-hop sensor wireless networks. The major challenge in using distributed beamforming in ad hoc wireless networks is that the relative disposition of wireless devices cannot be controlled with high precision as required by antenna arrays. We develop several optimization techniques for antenna radiation pattern generation in multi-hop ad hoc settings and analyze their effectiveness through simulations. In particular, we propose an optimization scheme for single hop beampattern generation and then show how to utilize it in a multi-hop environment.

In this paper we study the minimum total energy and maximum network lifetime routing problem in wireless ad hoc networks. We develop competitive online schemes for an infinite sequence of random routing requests with provable approximation factors in both measures. In addition, we produce fundamental bounds on the expected total energy consumption and network lifetime in the optimal offline solution. Our results are verified through simulations. In the course of our analysis we derive an interesting property of shortest path trees (SPT) for a random point process. We show that the maximum edge length of any SPT is asymptotically equal to the maximum edge length of a minimum spanning tree. This result is of self interest for the study of energy efficient routing as many heuristics rely on SPTs.

According to the Gaussian channel model, the throughput of a wireless link (u, v) is B log(l + S/N) bps, where B is the channel bandwidth and S/N is the signal to noise ratio. Wireless links which are scheduled simultaneously add to the noise levels of each other and cause the overall network capacity to decrease. In this paper we consider a wireless ad hoc network with unicast or multicast routing and simultaneously transmitting nodes along the route. Our major goal is to increase the capacity of the unicast/multicast sessions when all the wireless links are scheduled simultaneously. In addition, we try to minimize the number of active nodes involved in the unicast/multicast session for the purpose of energy efficiency. We assume that all the nodes share the same transmission range if activated and propose several node activation schemes with provable asymptotic bounds on the capacity and energy efficiency of the induced communication graph. We verify our results by simulations.

This paper studies the problem of interference-free broadcast in wireless ad hoc networks. In particular, we are interested in asymmetric power assignments so that the induced broadcast communication graph is both, energy efficient and has a short collision-free broadcast schedule. We consider both random and deterministic node layouts and develop four different broadcast schemes with provable performance guarantees on three optimization objectives simultaneously: total energy consumption, network lifetime and collision-free schedule length. We also show some numerical results which support our findings.

This paper studies the problem of topology control in random wireless ad-hoc networks through power assignment for n nodes uniformly distributed in a unit square. In particular, we are interested in asymmetric power assignments so that the induced communication graph has a good distance and energy stretch simultaneously, with additional optimization objectives: both minimizing the total energy consumption, interference level, hop-diameter, and maximizing the network lifetime. We present several power assignments with varying construction time complexity. The probability of our results converges to one as the number of network nodes, n, increases. To the best of our knowledge, these are the first results for spanner construction in wireless ad-hoc networks with provable bounds for both, energy and distance, metrics simultaneously.

This paper studies the problem of topology control in random wireless ad hoc networks through power assignment for n nodes uniformly distributed in a unit square. We require that the network is strongly connected and look to maximize the minimum throughput (or capacity) link in the case that all the nodes transmit simultaneously. According to the Gaussian channel model, the throughput of a wireless link (u, v) is B log(1 + S/N) bps, where B is the channel bandwidth and S/N is the channel bandwidth. We distinguish between two types of power assignments: homogeneous (all nodes have the same power level) and heterogeneous (nodes may have different power levels) cases. For the homogeneous case we give lower and upper bounds on the minimum capacity link. In the heterogeneous case we develop an energy efficient power assignment algorithm which achieves a minimum throughput of Ω(B log(1 + 1/√n log2n)) and also discuss how to implement this algorithm in a distributed fashion. Finally, we present some simulation results. To the best of our knowledge, these are the first provable bounds for capacity in wireless networks, when nodes are allowed to transmit simultaneously.

In this paper, we study asymmetric power assignments that induce a low-energy k-strongly connected communication graph with spanner properties. We address two spanner models: energy and distance. The former serves as an indicator for the energy consumed in a message propagation between two nodes, while the latter reflects the geographic properties of routing in the induced communication graph. We consider a random wireless ad hoc network with IVI = n nodes distributed uniformly and independently in a unit square. For k ∈ {1, 2}, we propose several power assignments that obtain a good bicriteria approximation on the total cost and stretch factor under the two models. For k > 2, we analyze a power assignment developed by Carmi et al. and derive some interesting bounds on the stretch factor for both models as well. We also describe how to compute all the power assignments distributively, and we provide simulation results. To the best of our knowledge, these are the first provable theoretical bounds for low-cost spanners in wireless ad hoc networks.

This paper studies asymmetric power assignments for which the induced communication graph is a good spanner of the Euclidean graph, induced on the wireless nodes V, while the total energy is minimized. We propose two spanner models: distance and energy. We consider a random wireless ad-hoc network with |V| = n nodes distributed uniformly and independently in a unit square. For the first model, we propose an approximation algorithm, which constructs a power assignment so that the induced network is an O ((1 + alpha)(n-m)/m log n + alpha)-spanner of Gvwith high probability, such that the total energy is at most betaldrm+2 times the optimum, for any alpha > 1, beta ges 1 + 2/(alpha-1), and any positive integer m les n in O(mn2) time. For the second model, we develop a power assignment such that the resulting network is a 2-spanner with a total energy of at most O(log n) times the optimum in O(n4log n) time. We also analyze a power assignment developed and show it is a low cost good k-fault resistant spanner. To the best of our knowledge, these are the first provable theoretic results for low cost spanners in wireless ad-hoc networks.