Algorithmic aspects of energy efficient transmission in multihop cooperative wireless networks

2011-11-25We consider the problem of energy-efficient transmission in cooperative multihop wireless networks. Although the performance gains of cooperative approaches are well known, because of the combinatorial nature of these schemes, designing efficient polynomial-time algorithms to decide which nodes should take part in cooperation, and when and with what power they should transmit, has remained a challenge. We propose to tackle this problem in this dissertation. ❧ We provide a generalized algorithmic formulation of the problem that encompasses the two main cooperative approaches, namely: energy accumulation and mutual Information accumulation. We investigate the similarities and differences of these two approaches under our generalized formulation, focusing in particular on the scenario where a delay constraint is present. We prove that the broadcast and multicast problems are, in general, o(log(n)) inapproximable. We break this NP hard problem into three parts: ordering, scheduling and power control and propose a generalized novel algorithm that, given an ordering, can optimally solve the joint power allocation and scheduling problems simultaneously in polynomial time. We further show empirically that this algorithm used in conjunction with an ordering derived heuristically using the Dijkstra's shortest path algorithm yields near-optimal performance in typical settings. In the unicast case, we prove that although the problem remains hard with mutual information accumulation, it can be solved optimally and in polynomial time when energy accumulation is used. We use our algorithm to study, numerically, the trade-off between delay and power-efficiency in cooperative broadcast and compare the performance of energy accumulation vs mutual information accumulation as well as the performance of our cooperative algorithm with a smart non-cooperative algorithm in a broadcast setting. We also provide an O(Tlog²(n)) approximation algorithm for the broadcast case where energy accumulation is used. ❧ We further formulate the problem of minimum energy cooperative transmission in a delay constrained multiflow multihop wireless network, as a combinatorial optimization problem, for a general setting of k-flows and formally prove that the problem is not only NP-hard but it is o(n^{1/7-\epsilon}) inapproxmiable. To our knowledge, the results in this dissertation provides the first such inapproxmiablity proof in the context of multiflow cooperative wireless networks. We show that for a special case of k=1, the solution is a simple path and develop an optimal polynomial time algorithm for joint routing, scheduling and power control. We then use this algorithm to establish analytical upper and lower bounds for the optimal performance for the general case of k flows. Furthermore, we propose a polynomial time heuristic for calculating the solution for the general case and evaluate the performance of this heuristic under different channel conditions and against the analytical upper and lower bounds