### Sayandeep Sen: Master's Thesis, June 2006

**Title:** Topology Planning for Long Distance Wireless Mesh
Networks

**Abstract:** Cost optimization is an important criterion in
technology deployment for developing regions. While IEEE 802.11-based
long-distance networks may provide a cost-effective option to connect
remote villages, planning such a network to cover the villages in a
given region can be a non-trivial task. This is especially so since
the antenna tower cost is the dominant cost in such scenarios. In
this thesis, we consider the problem of topology planning in the
context of 802.11-based long-distance rural networks. Our first
contribution is the formulation of this problem in terms of its
constraints and the optimization metric. We find the problem to be of
combinatorial nature, and hence not scalable for large input sets.
Our next contribution is in breaking down the problem into its
constituent sub-parts some of which are independent, this makes the
solution procedure tractable. Next we propose several searching and
pruning strategies in generation of an optimal solution.

We then present a set of results generated by the algorithm. We
have been able to find topologies for sets of nodes of size 31 (so
far). For a sub-set of the Ashwini (31 out of 34 nodes) project, a
long distance rural network currently being deployed in the West
Godavari district of Andhra Pradesh we have been able to show a cost
benefit of the order of 15 times on their cost savings, by improving
the process of assigning tower heights. Also careful topology planning
led to a further 22% savings over their current deployment plan.
Another fact to be borne in mind is the current deployment utilizes
three independent WiFi channel while our solution only uses one
channel. A final contribution of this thesis is the discussion of
further work necessary in this domain.

- Thesis: [pdf]
- Presentation: [pdf]

Bhaskaran Raman
Last modified: Mon Aug 7 23:58:52 IST 2006