Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Networks

We investigate the problem of extending the network lifetime of a single broadcast session over wireless stationary ad hoc networks where the hosts are not mobile. We define the network lifetime as the time from network initialization to the first node failure due to battery depletion. We provide through graph theoretic approaches a polynomial-time globally optimal solution, a variant of the minimum spanning tree (MST), to the problem of maximizing the static network lifetime. We make use of this solution to develop a periodic tree update strategy for effective load balancing and show that a significant gain in network lifetime over the optimal static network lifetime can be achieved. We provide extensive comparative simulation studies on parameters such as update interval and control overhead and investigate their impact on the network lifetime. The simulation results are also compared with an upper bound to the network lifetime. A preliminary version of this paper appeared in IEEE ICC 2003 [35]. This research was funded in part by NSF grant ANI-0093187, ONR award #: N00014-04-1-0479 and Collaborative Technology Alliance (CTA) from ARL under DAAD19-01-2-0011. All statements and opinions are that of the authors and do not represent any position of the U.S government Intae Kang received his B.S. degree in physics from Seoul National University, Seoul, Korea and M.S. degree in electrical engineering from the Johns Hopkins University, Baltimore, MD. He is currently working toward the Ph.D. degree in the Department of Electrical Engineering at the University of Washington, Seattle, WA. His current research interests are in the area of ad hoc and sensor networks. In particular, he is interested in energy efficient routing, topology control, medium access control, mobility management, and modeling and performance analysis of network protocols using directional/smart antennas. Radha Poovendran has been an assistant professor at the Electrical Engineering Department of the University of Washington at Seattle since September 2000. He received his Ph.D. in Electrical Engineering from the University of Maryland, College Park in 1999. His research interests are in the areas of applied cryptography for multiuser environment, wireless networking, and applications of Information Theory to security. He is a recipient of Faculty Early Career Award from the National Science Foundation (2001), Young Investigator Award from the Army Research Office (2002), Young Investigator Award from the Office of Naval Research (2004), and the 2004 Presidential Early Career Award for Scientists and Engineers, for his research contributions in the areas of wired and wireless multiuser security. He is also a co-recipient of the 2002 Outstanding Teaching as well as the Outstanding Advisor Awards from the Department of Electrical Engineering of the University of Washington.