An algorithm to find global optimal routing assignments for a class of PRNs

The problem of determining routing assignments and transmission probabilities to maximize the end-to-end throughput in a slotted ALOHA packet radio network is investigated. Due to interference from the neighbors of a receiver, this optimization problem is inherently nonconvex. By restricting the transmission probability of each node to be the same, it is shown that a global optimal solution can be found by solving a series of linear programs. Dantzig-Wolfe decomposition is applied to solve the LPs. The numerical examples show that the proposed method is effective in determining the network capacity