In this paper, we propose a novel concept called
Hitch-hiking in order to reduce the energy consumption of broadcast application for wireless networks. Hitch-hiking takes advantage of
the physical layer design that facilitates the combining of partial signals to obtain the complete information. The concept
of combining partial signals using
maximal ratio combiner [15] has been used to improve the reliability of the communication link but has never been exploited to reduce energy consumption
in broadcasting over wireless ad hoc networks. We study the advantage of Hitch-hiking for the scenario when the transmission
power level of nodes is fixed as well as the scenario when the nodes can adjust their power level. For both scenarios, we
show that Hitch-hiking is advantageous and have proposed algorithms to construct broadcast tree with Hitch-hiking taken into
consideration. For fixed transmission power case, we propose and analyze a centralized heuristic algorithm called SPWMH (Single
Power Wireless Multicast with Hitch-hiking) to construct a broadcast tree with minimum forwarding nodes. For the latter case,
we propose a centralized heuristic algorithm called Wireless Multicast with Hitch-hiking (WMH) to construct an energy efficient
tree using Hitch-hiking and also present a distributed version of the heuristic. We also evaluate the proposed heuristics
through simulation. Simulation results show that Hitch-hiking can reduce the transmission cost of broadcast by as much as
50%. Further, we propose and evaluate a protocol called Power Saving with Broadcast Tree (PSBT) that reduces energy consumption
of broadcast by eliminating redundancy in receive operation. Finally, we propose an algorithm that takes advantage of both
Hitch-hiking and PSBT in conserving energy.
Keywords wireless ad hoc networks - broadcast algorithms - distributed algorithms - maximal ratio combiner - simulations
Manish Agarwal is an engineer at Microsoft, Redmond. He received his Masters degree in Electrical and Computer Engineering from University
of Massachusetts, Amherst in 2004. He received his undergraduate degree from Indian Institute of Technology, Guwahati. His
research interest lies in the field of mobile ad hoc networks.
Lixin Gao is an associate professor of Electrical and Computer Engineering at the University of Masschusetts, Amherst. She received
her Ph.D. degree in computer science from the University of Massachusettes at Amherst in 1996. Her research interests include
multimedia networking and Internet routing. Between May 1999 and January 2000, she was a visiting researcher at AT&T Research
Labs and DIMACS. She is an Alfred P. Sloan Fellow and received an NSF CAREER Award in 1999. She is a member of IEEE, ACM,
and Sigma Xi.
Joon Ho Cho received the B.S. degree (summa cum laude) in electrical engineering from Seoul National University, Seoul, Korea, in 1995
and the M.S.E.E. and Ph.D. degrees in electrical and computer engineering from Purdue University, West Lafayette, IN, in 1997
and 2001, respectively. From 2001 to 2004, he was with the University of Massachusetts at Amherst as an Assistant Professor.
Since July 2004, he has been with Pohang University of Science and Technology (POSTECH), Pohang, Korea, where he is presently
an Assistant Professor in the Department of Electronic and Electrical Engineering. His research interests include wideband
systems, multiuser communications, adaptive signal processing, packet radio networks, and information theory. Dr. Cho is currently
an Associate Editor for the IEEE Transactions on Vehicular Technology.
Jie Wu is a Professor at Department of Computer Science and Engineering, Florida Atlantic University. He has published over 300
papers in various journal and conference proceedings. His research interests are in the area of mobile computing, routing
protocols, fault-tolerant computing, and interconnection networks. Dr. Wu served as a program vice chair for 2000 International
Conference on Parallel Processing (ICPP) and a program vice chair for 2001 IEEE International Conference on Distributed Computing
Systems (ICDCS). He is a program co-chair for the IEEE 1st International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04).
He was a co-guest-editor of a special issue in IEEE Computer on “Ad Hoc Networks”. He also editored several special issues
in Journal of Parallel and Distributing Computing (JPDC) and IEEE Transactions on Parallel and Distributed Systems (TPDS).
He is the author of the text “Distributed System Design” published by the CRC press. Currently, Dr. Wu serves as an Associate
Editor in IEEE Transactions on Parallel and Distributed Systems and three other international journals. Dr. Wu is a recipient
of the 1996–97 and 2001–2002 Researcher of the Year Award at Florida Atlantic University. He served as an IEEE Computer Society
Distinguished Visitor. Dr. Wu is a Member of ACM and a Senior Member of IEEE.