An Optimal Algorithm for Relay Node Assignment in Cooperative Ad Hoc Networks

Abstract

Recently, cooperative communications, in the form of having each node equipped with a single antenna and exploit spatial diversity via some relay node's antenna, is shown to be a promising approach to increase data rates in wireless networks. Under this communication paradigm, the choice of a relay node (among a set of available relay nodes) is critical in the overall network performance. In this paper, we study the relay node assignment problem in a cooperative ad hoc network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. Our objective is to assign the available relay nodes to different source-destination pairs so as to maximize the minimum data rate among all pairs. The main contribution of this paper is the development of an optimal polynomial time algorithm, called ORA, that achieves this objective. A novel idea in this algorithm is a ?linear marking? mechanism, which maintains linear complexity of each iteration. We give a formal proof of optimality for ORA and use numerical results to demonstrate its capability.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2010
Accession Number
ADA536094

Entities

People

  • Sastry Kompella
  • Sushant Sharma
  • Yantian Hou
  • Yi Shi

Organizations

  • Virginia Tech

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Ad Hoc Networks
  • Algorithms
  • Background Noise
  • Communication Channels
  • Computer Science
  • Computing System Architectures
  • Data Rate
  • Electronic Mail
  • Environment
  • Iterations
  • Mesh Networks
  • Military Research
  • Network Topology
  • Networks
  • Polynomials
  • Wireless Communications
  • Wireless Networks

Fields of Study

  • Computer science

Readers

  • Computer Networking