PROC. IEEE INFOCOM, RIO DE JANEIRO, BRAZIL, APRIL 2009 1Delay-Limited Cooperative Communication withReliability Constraints in Wireless NetworksRahul Urgaonkar, Michael J. NeelyUniversity of Southern California, Los Angeles, CA 90089http://www-scf.usc.edu/∼urgaonkaAbstract—We investigate optimal resource allocation for delay-limited cooperative communication in time varying wirelessnetworks. Motivated by real-time applications that have stringentdelay constraints, we develop dynamic cooperation strategies thatmake optimal use of network resources to achieve a target outageprobability (reliability) for each user subject to average powerconstraints. Using the technique of Lyapunov optimization, wefirst present a general framework to solve this problem andthen derive quasi-closed form solutions for several cooperativeprotocols proposed in the literature.I. INTRODUCTIONThere is growing interest in the idea of utilizing cooper-ative communication [1]–[4] to improve the performance ofwireless networks with time varying channels. The motivationcomes from the work on MIMO systems [18] which showsthat employing multiple antennas on a wireless node canoffer substantial benefits. However, this may be infeasiblein small-sized devices due to space limitations. Cooperativecommunication has been proposed as a means to achievethe benefits of traditional MIMO systems using distributedsingle antenna nodes. Much recent work in this area promisessignificant gains in several metrics of interest (such as diversitygains [1] [2], capacity [3]–[6], energy efficiency [8] etc.) overconventional methods. We refer the interested reader to arecent comprehensive survey [7] and its references.The main idea behind cooperative communication can beunderstood by considering a simple 2-hop network consistingof a source s, its destination d and a set of m relay nodesas shown in Fig. 1. Suppose s has a packet to send to d intimeslot t. The channel gains for all links in this networkare shown in the figure. In direct communication, s usesthe full slot to transmit its packet to d over link s − d. Inconventional multi-hop relaying, s uses the first half of theslot to transmit its packet to a particular relay node i over links − i. If i can successfully decode the packet, it re-encodesand transmits it to d in the second half of the slot over linki − d. In both scenarios, to ensure reliable communication,the source and/or the relay must transmit at high power levelswhen the channel quality of any of the links involved is poor.However, note that due to the broadcast nature of wirelesstransmissions, other relay nodes may receive the signal fromthe transmission by s and can cooperatively relay it to d. TheThis material is supported in part by one or more of the following: theDARPA IT-MANET program grant W911NF-07-0028, the NSF grant OCE0520324, the NSF Career grant CCF-0747525.sm2i1hs1(t)h1d(t)hsi(t)hid(t)hsm(t)hmd(t)hsd(t)hs2(t)h2d(t)source transmitssource transmits relay i transmitssource transmitsrelay 1 transmitsrelay m transmitsrelay 2 transmitssource transmits all cooperatingrelays transmit(a) direct transmission(b) multi-hop transmission (c) cooperative transmissionover orthogonal channels(d) cooperative transmission using DSTC or beamformingFig. 1. Example 2-hop network with source, destination and relays. Thetime slot structures for different transmission strategies are also shown. Dueto the half-duplex constraint, cooperative protocols need to operate in twophases. Hence, there is an inherent loss in the multiplexing gain under anysuch cooperative transmission strategy over direct transmission.destination now receives multiple copies/signals and can useall of them jointly to decode the packet. Since these signalshave been transmitted over independent paths, the probabilitythat all of them have poor quality is significantly smaller.Cooperative communication protocols take advantage of thisspatial diversity gain by making use of multiple relays forcooperative transmissions to increase reliability and/or reduceenergy costs. This is different from traditional multi-hoprelaying in which only one node is responsible for forwardingat any time and in which the destination does not use multiplesignals to decode a packet.In this work, we consider a mobile ad-hoc network withdelay-limited traffic and cooperative communication. Manyreal-time applications (e.g., voice) have stringent delay con-straints and fixed/minimum rate requirements. In slow fadingenvironments (where decoding delay is of the order of thechannel coherence time), it may not be possible to meet thesedelay constraints for every packet. However, these applicationscan often tolerate a certain fraction of lost packets or outages.A variety of techniques are used to combat fading and meetthis target outage probability (including exploiting diversity,channel coding, ARQ, power control, etc.). Cooperative com-PROC. IEEE INFOCOM, RIO DE JANEIRO, BRAZIL, APRIL 2009 2munication is a particularly attractive technique to improvereliability in such delay-limited scenarios since it can offersignificant spatial diversity gains in addition to these tech-niques.Much prior work on cooperative communication considersphysical layer resource allocation for a static network, partic-ularly in the case of a single source. Objectives such as mini-mizing sum power, minimizing outage probability, meeting atarget SNR constraint, etc., are treated in this context [8]–[12].We draw on this work in the development of dynamic resourceallocation in a stochastic network with fading channels, nodemobility, and random packet arrivals, where opportunisticcooperation decisions are required. Dynamic cooperation wasalso considered in the prior work [13], where queue stabilityin a multi-user network with static channels and randomlyarriving traffic is considered using the framework of Lyapunovdrift. Our formulation is different and does not involve issuesof queue stability. Rather, we consider a delay limited scenariowhere each packet must either be transmitted in one slot,or dropped. This is similar to the concept of delay limitedcapacity [14]. We use techniques of both Lyapunov drift andLyapunov Optimization [17]. Different from most work thatapplies this theory, our solution involves a 2-stage stochasticshortest path problem due to the cooperative relaying structure.This problem is non-convex and combinatorial in nature anddoes not admit closed form solutions in general.