Abstract
Wireless communication is inherently error-prone due to path loss, fading, noise, interference, etc. In such an error-inclined environment with scarce spectrum, it is of paramount importance to achieve reliable data delivery efficiently. In this thesis, we develop efficient schemes for providing reliable broadcast in wireless multihop networks and for providing advanced ARQ in wireless relay networks. We first address the minimum transmission broadcast problem in error-prone wireless networks and present efficient solutions, including an optimal broadcast scheme and a distributed game-based algorithm. The minimum transmission broadcast problems over reliable links and over unreliable links are formulated as two mixed integer linear programming (MILP) problems, respectively. This way, optimal broadcast schemes can be easily obtained using any existing MILP solver, for small-scale networks. For large-scale networks, we propose a distributed game-based algorithm and prove that the game-based algorithm achieves Nash Equilibrium. Using simulation, we confirm that compared with existing algorithms in the literature and optimal solutions obtained by our MILP techniques, the proposed game-based algorithm performs very well in terms of delivery ratio, number of transmissions, and convergence speed. We further address the issue of advanced ARQ in wireless relay networks and develop relay-assisted network-coding (RANC) ARQ protocols, which leverage both opportunistic retransmission and network coding techniques. We introduce the concept of work, which is the number of recoded blocks a relay node will send, and study ways to adjusting the rate at which a relay node increases its work. Based on this concept, we present the unified framework of work-based RANC and then, under the unified framework, we develop a number of RANC ARQ protocols including plain-RANC, Work-based Opportunistic RANC (WO-RANC), Listen-and-Supersede (LS) RANC, and Hold-and-Proceed (HP) RANC. LS offers a fundamental limit to any single-relay RANC ARQ protocol. HP is a simple yet efficient RANC ARQ protocol with near-zero overhead. We analyze saturation throughput and segment delay for both LS and HP. Through extensive analysis and simulation results, we show that HP has a performance close to LS.