Prashant Sharma: Master's Thesis, Aug 2005

Title: Radio Placement Algorithm and Dynamic Channel Allocation for Large Area Community Networks

Abstract: Community networks are being deployed today over large geographical regions (few tens of kilometres) to provide various services like VOIP (Voice over Internet protocol), web access, information sharing etc. to people in cities as well as villages. We will call these community networks covering large geographical regions as Large Area Community Networks. In this thesis, we consider the large area community networks in which nodes are mounted at pre-existing towers or on the tall buildings and most of the nodes use only a single radio for all of its directional antennas to begin with. More radios are later added to this network to increase its capacity and throughput. In this thesis, we consider the problem of adding new radios to the given network to increase its capacity.

We are proposing a Radio Placement Algorithm for the selection of nodes to which new radios could be connected in order to maximize the throughput of the network. The algorithm does node selection, and also allocates an appropriate channel to the newly formed link. This algorithm uses a heuristic to determine position of new radios in the network. This heuristic determines the amount of contention present in the network. So using this heuristic, we determines the position for a new radio, where amount of contention in the network is minimum, this indicates that improvement in the capacity of the network will be maximum. This algorithm determines the node position in linear time as compared to a naive exhaustive search method which is combinatorial. We have evaluated this algorithm through simulation on various kinds of topologies. We also describe Dynamic Channel Allocation for large area community networks which uses more than one radio per node. This scheme uses the available channels in the best possible way to minimize the contention in the network.

Bhaskaran Raman
Last modified: Sun Aug 7 21:17:44 IST 2005