Computation of Minimal Uniform Transmission Range in Ad Hoc Wireless Networks

Power conservation is a critical issue for ad hoc wireless networks. The main objective of the paper is to find the minimum uniform transmission range of an ad hoc wireless network, where each node uses the same transmission power, while maintaining network connectivity. Three different algorithms, Prims Minimum Spanning Tree (MST), its extension with Fibonacci heap implementation, and an area-based binary search are developed to solve the problem. Their performance is compared by simulation study together with Kruskals MST, a known solution proposed by Ramanathan and Rosales-Hain for topology control by transmission power adjustment, and an edge-based binary search used by the same study in order to find the per-node-minimality after Kruskals algorithm is applied. Our results show that Prims MST outperforms both Kruskals MST and the two binary searches. The performance between Prims MST implemented with binary heap and Fibonacci heap is fairly close, with the Fibonacci implementation slightly outperforming the other.Qing Dai received her M.S. degree in Computer Science from Florida Atlantic University on August 2003, and M.S. degree in Microbiology from Upstate University on July 2000. She is currently a software engineer at Motorola, Plantation, FL.Jie Wu is a Professor at Department of Computer Science and Engineering, Florida Atlantic University. He has published over 200 papers in various journals and conference proceedings. His research interests are in the areas of wireless networks and mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. He served on many conference organization committees. Dr. Wu is on the editorial board of IEEE Transactions on Parallel and Distributed Systems and was a co-guest-editor of IEEE Computer and Journal of Parallel and Distributed Computing. He is the author of the text Distributed System Design published by the CRC press. He was also the recipient of the 1996–97 and 2001–2002 Researcher of the Year Award at Florida Atlantic University. Dr. Wu has served as an IEEE Computer Society Distinguished Visitor. He is a Member of ACM and a Senior Member of IEEE.