Optimal distributed stochastic routing algorithms for wireless multihop networks

Alejandro Ribeiro, Nikolaos D. Sidiropoulos, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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.

Original languageEnglish (US)
Article number4684602
Pages (from-to)4261-4272
Number of pages12
JournalIEEE Transactions on Wireless Communications
Issue number11
StatePublished - Nov 2008

Bibliographical note

Funding 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
  • Routing
  • Wireless multihop networks


Dive into the research topics of 'Optimal distributed stochastic routing algorithms for wireless multihop networks'. Together they form a unique fingerprint.

Cite this