Minimum-power broadcast and maximization of time-to-first-failure in broadcast wireless networks

Unlike wired networks where a transmission from node i to j reaches only node j, in wireless networks, several nodes may be reached by a single transmission. Assuming that all nodes have omni-directional antennas, nodes which are closer to i than j will also receive the transmission. A few heuristics (sub-optimal) have recently been suggested which exploit this property for constructing broadcast/multicast routing trees which minimize the sum of transmitter powers in the tree. This is known as the Minimum Power Broadcast (MPB) problem.; An alternate routing strategy, particularly suitable for energy-constrained networks where individual nodes are powered by batteries and periodic replacement/maintenance of the batteries is not feasible, is to design trees which maximize the residual time to first node burn-out (i.e., when the first node in the network runs out of battery power). This is known as the time-to-first-failure (TTFF) maximization problem.; In this dissertation, we first formulate the minimum power broadcast/multicast and the TTFF maximization problems as mixed integer linear programming models which allow us to obtain optimal solutions to these problems. These models are based on the celebrated Traveling Salesman Problem and the well-studied Uncapacitated Network Flow problem. Given the rich body of literature which exist in these areas, they benefit from the numerous efficient solution strategies which are already available for these problems. We also propose a couple of deterministic tree-improvement heuristics for the MPB problem.; In addition, we propose a computationally intelligent solution mechanism for the MPB problem using swarm intelligence, a recent and novel paradigm which has proven to be immensely successful in solving hard combinatorial problems. A final contribution of this dissertation is the viability lemma, a mathematically simple tool that can be used to check the feasibility of an arbitrary broadcast tree. Used in conjunction with standard evolutionary search algorithms, the lemma provides a convenient framework for designing optimal or near-optimal broadcast routing trees in relatively little time.