A novel framework was introduced recently for stochastic routing in wireless multihop networks, whereby each node selects a neighbor to forward a packet according to a probability distribution. Generalizing (deterministic) shortest path routing, stochastic routing offers greater flexibility that matches the random nature of wireless links. Consider the pairwise reliability matrix R, whose (i, j)-th entry Rij represents the probability that a packet transmitted from the j-th user Uj is correctly received by the i-th user Ui. Using R to capture physical layer aspects of the wireless medium, several rate-oriented stochastic routing formulations can be reduced to centrally solvable convex optimization problems. The present paper, introduces distributed algorithms that find optimal routing probabilities without the burden of collecting R at a central node and then percolating the resulting routing probabilities through network nodes. The resultant schemes are distributed in the sense that: (i) terminal Uj has access only to the j-th row and column of R; and (ii) Uj interchanges variables only with those single-hop neighbors having positive probability of decoding its packets. The distributed algorithms are built by recasting the optimization problems and applying dual decomposition techniques. Since iterates obtained via dual decomposition do not always converge to centralized optimal routing probabilities, two known regularization approaches are further invoked, namely the method of multipliers (MoM) and the alternating-direction MoM. Convergence to the optimal routing matrix is then guaranteed under mild conditions. Many rate-oriented optimality criteria of practical interest can be addressed by the distributed framework, including maximization of: (i) the minimum rate; (ii) a weighted sum of rates; (iii) the product of rates; and (iv) the source's rate in a relay network. Robustness of the distributed algorithms is tested with respect to "topological" changes, communication errors and node mobility.
Bibliographical noteFunding Information:
Manuscript received November 8, 2006; revised May 15, 2007 and October 21, 2007; accepted December 8, 2007. The associate editor coordinating the review of this paper and approving it for publication was D. Wu. A summary of the main results in this paper was presented in the IEEE ICASSP Conf., Honolulu, HI, April 2007. Work in this paper was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U. S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U. S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. The work of N. D. Sidiropoulos was partially supported by the EU under FP6 FET project CoopCom.
- Convex optimization
- Distributed network optimization
- Dual decomposition
- Wireless multihop networks