Fast Algorithm for Finding Unicast Capacity of Linear Deterministic Wireless Relay Networks

Download Now Free registration required

Executive Summary

The deterministic channel model for wireless relay networks proposed by Avestimehr, Diggavi and Tse '07 has captured the broadcast and inference nature of wireless communications and has been widely used in approximating the capacity of wireless relay networks. The authors generalized the max-flow min-cut theorem to the linear deterministic wireless relay networks and characterized the unicast capacity of such deterministic network as the minimum rank of all the binary adjacency matrices describing source-destination cuts whose number grows exponentially with the size of the network. In this paper, the authors developed a fast algorithm for finding the unicast capacity of a linear deterministic wireless relay network by finding the maximum number of linearly independent paths using the idea of path augmentation.

  • Format: PDF
  • Size: 245.31 KB