Delay-Throughput Trade-Off with Opportunistic Relaying in Wireless Networks

In this paper, we study the delay/throughput trade- off with opportunistic relaying over channels with random connections, in which the channel connections are independent and identically distributed (i.i.d.). Previous work which proposed an opportunistic relaying scheme has focused on the throughput analysis only, we show that the opportunistic relaying scheme provides an upper bound of O(n) delay, including full effects of queueing in the network model. In addition, we use the redundant scheduling algorithm to reduce the upper bound of delay scaling to O(n/√(log n)). Furthermore, we prove two key inequalities that capture the various tradeoffs inherent in the broad class of opportunistic relaying protocols, which indicate the tradeoff of delay/throughput ≥ O(n/log n), illustrating that no scheduling and routing algorithm can simultaneously yield lower delay and higher throughput.