iMST: A bandwidth-guaranteed topology control algorithm for TDMA-based ad hoc networks with sectorized antennas

Many topology control algorithms aim to minimize energy consumption, interference, etc. while maintaining connectivity among the nodes. Links are realized between nodes by proper adjustment of transmission power in each node. However, a link is not useful if its bandwidth is lower than what is required by the applications it supports. Therefore, topology control algorithms should also consider the minimum realizable link bandwidth when generating topologies. As the realizable bandwidth of a link depends on the amount of interference received, interference analysis must be carried out. We study the minimum realizable link bandwidth of a given network under a TDMA/TDD channel sharing mechanism. We carried out the interference analysis assuming the general multi-sectored antenna configuration, since an omni-directional antenna can be visualized as a special configuration of a sectorized antenna (i.e. with 1 sector). We then proceed to derive the transmission power to be used in each sector of all nodes in the network to maximize average channel utilization. However, a brute-force method that runs through all possible topologies takes exponential time.We thus propose an algorithm, iMST, that attempts to maximize average channel utilization by reducing interference. The iMST algorithm not only generates k-edge-connected networks, but also guarantees minimum link bandwidth. Although iMST requires global knowledge of the locations of nodes, by using a distributed MST generation method, iMST can be run in a distributed manner. The iMST scheme is evaluated and compared against a modified Fault-tolerant Cone-Based Topology Control (FCBTC) scheme, referred to as s-FCBTC, that works with sectorized antennas, on a few performance metrics: average channel utilization, network diameter, minimum link bandwidth and edge-connectedness, where edge-connectedness is a new metric defined in this paper. The iMST scheme is shown to exhibit good performance in many of these performance metrics.