Broadcasting and transmission coordination for ad hoc and sensor networks

This thesis studies the performance benefit of coordination in wireless sensor networks (WSNs) and ad hoc networks (AHNs). WSNs are often comprised of a large number of inexpensive nodes with short battery life and limited communication and processing capabilities. AHNs are wireless networks operating without the benefits of network infrastructure (basestations) or centralized control.;WSNs often require control messages be broadcast to the entire network. We study the performance of a class of randomized broadcast protocols that employ coordination to reduce the transmission of redundant messages and to reduce the occurrence of message collisions. Specifically, information coordination entails a potential transmitter employ local information to infer whether or not its potential receivers would be interested in its message, while communication coordination entails a potential transmitter employ local information to infer whether or not its transmission would interrupt other ongoing transmissions. The individual and joint benefits of these two forms of coordination are assessed through their impact on a variety of natural performance indicators.;AHNs working with limited spectrum perform best when simultaneous transmissions are coordinated to avoid collisions. Optimal transmission coordination is a combinatorial optimization problem that is, in general, intractable for large size networks, even with global information and central control. Constraints on simultaneous transmissions may arise from both transceiver limitations (e.g., half-duplex designs) and from requirements on the signal to interference ratio. We study the transmission coordination optimization problem under a variety of natural communication constraints. Our work identifies particular instances where the problem may be solved by greedy algorithms, and studies the performance of several natural heuristic solutions.