<< Kod*lab Publications

# A Recursive, Distributed Minimum Spanning Tree Algorithm for Mobile Ad Hoc Networks

#### *2014 Robotics: Science and Systems Conference, CarNet Workshop*

#### July, 2014

OmurArslan*, and D. E. Koditschek*

*: Electrical and Systems Engineering, University of Pennsylvania

Extended Abstract(PDF), Poster(PDF) | Penn Scholarly Commons

**Recursive, Distributed MST Algorithm**
Abstract |

We introduce a recursive (“anytime”) distributed algorithm that iteratively restructures any initial spanning tree of a weighted graph towards a minimum spanning tree while guaranteeing at each successive step a spanning tree shared by all nodes that is of lower weight than the previous. Each recursive step is computed by a different active node at a computational cost at most quadratic in the total number of nodes and at a communications cost incurred by subsequent broadcast of the new edge set over the new spanning tree. We show that a polynomial cubic in the number of nodes bounds the worst case number of such steps required to reach a minimum spanning tree and, hence, the number of broadcasts along the way. We conjecture that the distributed, anytime nature of this algorithm is particularly suited to tracking minimum spanning trees in (sufficiently slowly changing) mobile ad hoc networks. |

This work was funded in part by the Air Force Office of Science Research under the MURI FA9550–10–1−0567. |

BibTeX entry |

@Misc{arslan_kod_RSS2014CarNetWorkshop,
Author = {Omur Arslan and Daniel E. Koditschek},
Title = {A Recursive, Distributed Minimum Spanning Tree Algorithm for Mobile Ad Hoc Networks},
TowPublished = {Poster presented at RSS2014 Workshop on Communication-aware Robotics:
New Tools for Multi-Robot Networks, Autonomous Vehicles, and Localization},
Month = {July},
Year = {2014}
} |