A hierarchical virtual backbone construction protocol for mobile ad hoc networks

We propose a hierarchical backbone construction protocol for mobile ad hoc networks. Our protocol is based on the idea of using an efficient extrema finding method to create clusters comprising the nodes that are within certain prespecified wireless hop distance. Afterward, we apply our ‘diameter’ algorithm among clusters to identify the dominating nodes that are, finally, connected via multi-hop virtual links to construct the backbone. We present the analytic as well as simulation study of our algorithm and also a method for the dynamic maintenance of constructed backbone. In the end, we illustrate the use of the virtual backbone with the help of an interesting application.