Cost-delay tradeoffs for two-way relay networks

Ertugrul Necdet Ciftcioglu*, Yalin Evren Sagduyu, Randall A. Berry, Aylin Yener

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We consider two sources in a wireless network exchanging stochastically varying traffic using an intermediate relay. Each relay use incurs some cost, which, for example, could be transmission energy. This cost is shared between the sources when packets from both are transmitted simultaneously by the relay using network coding. If the relay transmits a packet originating from one source only, the cost is incurred by that source only. In this setting, we study transmission policies that tradeoff the average cost with the average packet delay. We first present the cost-delay tradeoff for a centralized scheme using Lyapunov stability arguments. Next, we consider a distributed policy, where each source aims to optimize its own cost-delay tradeoff. We determine the Nash equilibrium of the resulting non-cooperative game and show that it performs worse than the centralized algorithm. To overcome this limitation, we introduce a pricing mechanism at the relay, which is shown to achieve the centralized performance. These algorithms, though oblivious to the arrival statistics, do require global knowledge of queue backlogs. Lastly, we consider distributed algorithms that overcome this requirement. Among those, we observe that simple queue-length threshold algorithms perform remarkably well.

Original languageEnglish (US)
Article number6059446
Pages (from-to)4100-4109
Number of pages10
JournalIEEE Transactions on Wireless Communications
Issue number12
StatePublished - Dec 2011


  • Cost sharing
  • competition
  • cooperation
  • delay
  • network coding
  • queue stability
  • stochastic traffic
  • two-way relaying

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Cost-delay tradeoffs for two-way relay networks'. Together they form a unique fingerprint.

Cite this