Mobile backbone architecture for wireless ad-hoc networks : algorithms and performance analysis

In this thesis, we study a novel hierarchical wireless networking approach in which some of the nodes are more capable than others. In such networks, the more capable nodes can serve as Mobile Backbone Nodes and provide a backbone over which end-to-end communication can take place. The main design problem considered in this thesis is that of how to (i) Construct such Mobile Backbone Networks so as to optimize a network performance metric, and (ii) Maintain such networks under node mobility. In the first part of the thesis, our approach consists of controlling the mobility of the Mobile Backbone Nodes (MBNs) in order to maintain network connectivity for the Regular Nodes (RNs). We formulate this problem subject to minimizing the number of MBNs and refer to it as the Connected Disk Cover (CDC) problem. We show that it can be decomposed into the Geometric Disk Cover (GDC) problem and the Steiner Tree Problem with Minimum Number of Steiner Points (STP-MSP). We prove that if these subproblems are solved separately by y- and 5-approximation algorithms, the approximation ratio of the joint solution is y1+6. Then, we focus on the two subproblems and present a number of distributed approximation algorithms that maintain a solution to the GDC problem under mobility. A new approach to the solution of the STP-MSP is also described. We show that this approach can be extended in order to obtain a joint approximate solution to the CDC problem. Finally, we evaluate the performance of the algorithms via simulation and show that the proposed GDC algorithms perform very well under mobility and that the new approach for the joint solution can significantly reduce the number of Mobile Backbone Nodes.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Srinivas, Anand, 1979-

Advisor dc:contributor.advisor

• Eytan H. Modiano.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/42179

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/42179