| dc.description.abstract | Recently, many types of mobile devices with high level computing capabilities, such as cellular phones, PCs, digital cameras, and high performance PDAs, have come into widespread use. In 2000, some of these devices became capable of short range wireless communication empowered by Bluetooth technology. Although most present day wireless networks have a cellular structure, ad hoc networks promise more flexible networks with no wired backbone. Ad hoc networks are especially promising when it comes to forming a network among mobile devices. The Internet Engineering Task Force (IETF) [1] has been working on such technologies. One of its Active Working Groups in the Routing Area, called Mobile Ad hoc Networks (MANET) [2], specifically works on ad hoc networks.
This thesis proposes methodologies for the optimization of wireless ad hoc networks. The approach is based on the Cluster Based Routing Protocol (CBRP) [3], where each node can both transmit and receive.
The network consists of arbitrarily placed nodes (hosts). Given a positioning of such nodes, the minimum transmission power at which nodes must transmit has to be determined. We need to keep this as low as possible to optimally use the battery life of transmitter nodes. We first determine the minimum power at which each node transmits such that every node is able to communicate with every other node in the network. The underlying graph structure has an edge connecting a pair of nodes if the transmission power is adequate for the two to communicate directly.
None of the nodes actually knows the whole topology of the graph. Each node is aware only of its one hop neighbourhood, i.e., the set of nodes whose transmission range covers that particular node. A fundamental problem is to determine if there is a feasible clustering based on limited local knowledge.
We define the capacity of an ad hoc network as the maximum number of simultaneous transmissions per hop in one time slot and optimize the clustering based on this metric. We propose two Integer Programming (IP) formulations that, when solved, determine the maximum capacity clustering. These formulations take the entire topology as input-i.e., they require complete knowledge of the whole graph. Both formulations give rise to good solutions. However, they cannot always be implemented practically because it is difficult for any single node to learn the entire topology, particularly since the nodes may move from time to time.
We therefore devise a distributed algorithm, derived from the two formulations, which may not reach the global optimum but is practical. Each node can follow this algorithm with limited knowledge of the topology and still lead to a feasible clustering. This algorithm avoids the formation of partitioned clusters that can occur in existing distributed algorithms such as the highest degree algorithm [4] or the lowest ID algorithm [5]. | |
