Self -organization in large-scale wireless networks

Large-scale wireless networks such as ad-hoc networks and sensor networks have attracted considerable attention in the last few years, both in academia and industry. One of the main reasons for their popularity can be attributed to the various applications that they make possible. Habitat monitoring, environmental observation and forecasting, organ and health monitoring and target tracking are just a few examples of the many applications of such wireless networks. A characteristic requirement of these wireless networks is that they be self-organizing i.e., the wireless nodes organize themselves in order to efficiently perform the tasks required by the application. Self-organizing networks are attractive since they do not require human intervention and thereby reduce the cost of installation. In this thesis, we consider several tasks that arise commonly in the process of self-organization of a wireless ad hoc network, viz. topology formation, power control and leader election. We first consider the problem of neighbor discovery in wireless networks, the first step in bootstrapping a wireless network. We propose probabilistic algorithms that allow nodes to rapidly discover their neighbors, thereby expending less energy during neighbor discovery. In the second part of our thesis, we focus our attention on techniques to reduce the energy consumption of a wireless network. In particular, we consider the problem of optimal power assignment in wireless networks with transmitter-receiver tradeoffs. In these networks, the transmitter power can be increased to reduce the receiver power and consequently, the overall power consumption. We propose algorithms to assign power to nodes so that the lifetime of the network is maximized. Another aspect of self-configuration that arises frequently in wireless networks is the problem of leader election amongst a set of nodes. Arbitrary topological changes caused by node movement makes this problem significantly challenging. In the final part of this thesis, we propose a provably correct and highly efficient leader election algorithm that can tolerate arbitrary topological changes caused due to node movement