Maintaining a quality of service routing tree for mobile ad hoc networks
Khaled M. Alzoubi, Moussa Ayyash · 2006
We define the Quality of Service Routing Tree (QoSRT) for the weighted graph G(V,E), as a subgraph G'(V,E') such that G' is a tree, and the set of intermediate edges of the path between any pair of nodes u and v is a subset of E'. The weight of an edge represents its bandwidth. Furthermore, the lowest weight edge (bottleneck) of the path is maximized. In this paper, we propose a distributed algorithm to construct a QoSRT that adapts quickly to mobile environments. The QoSRT is uniquely constructed for maintenance purposes. A maintenance scheme that responds quickly to mobility and bandwidth changes is also provided. A virtual backbone (VBB) which consists of a subset of the nodes is also constructed. The QoSRT and its VBB are constructed using O(nlog n) messages in O(nlog n) time.