NOTE: The Center for Mobile Computing is no longer active, and this web site represents a historical view of its activities from 1996-2008. Although there is still mobile-computing research underway at Dartmouth, we no longer update this web site. Please contact David Kotz with any inquiries about the CMC.
[About CMC] [Partners] [Projects] [Papers] [People] [News]
Qun Li, Javed Aslam, and Daniela Rus
June 2001
More details can be found in our Mobicom 2001 paper.
Imagine a large ad-hoc wireless network consisting of thousands of computers, such as a network of sensors distributed over a large geographical area. In such networks, energy consumption is a critical factor, and the wireless transceivers are the most significant energy consumer. Our goal is to develop a power-aware approach to routing messages that is fast, scalable, and on-line. An on-line algorithm does not know ahead of time the sequence of messages to be routed over the network, whereas an off-line algorithm knows the complete sequence of messages to be routed, in advance. Needless to say, on-line algorithms are more realistic.
In our current research, we focused only on issues related to minimizing power consumption during communication, that is, while the system is transmitting and receiving messages. We use a global metric: maximizing the lifetime of the network, defined to be the earliest time that a message cannot be sent.
Our proposed on-line algorithm, called the max-min zPmin algorithm, combines the benefits of selecting the path with the minimum power consumption and the path that maximizes the minimal residual power in the nodes of the network. Despite the discouraging theoretical result concerning the competitive ratio for on-line routing, we show that the max-min zPmin algorithm has a good competitive ratio in practice, approaching the performance of the optimal off-line routing algorithm under realistic conditions.
The algorithm limits the total power consumption to send a message up to zPmin where Pmin is the minimal power needed to forward the message one hop and z is a small constant; at the same time, it chooses the path on which the nodes have the maximal minimal residual power after the message is sent, to avoid using the low-power nodes. Consider the accompanying figure (the first number after the node is the power level of that node before the message forwarding, and the second is the power consumption of sending the message along that edge). Suppose Pmin, the minimal power consumption from S to T is 6 (along the black path) and we choose z to be 3. The total power consumption of the red path (23) is more than z Pmin (18), so it is not considered. The total power consumed on other paths (green 15, blue 13, and black 6) are within the limit, so we then identify the node on each path with the lowest remaining power if the message were to be sent along that path. After sending the message, thegreen path would have minimal residual power 10; the black path 1; and the blue path 2. Since the green path has the maximal minimal residual power level, we choose the green path to send the message.
This algorithm requires information about the power level of each computer in the network. Knowing this information accurately is not a problem in small networks. For large networks, however, it is difficult to aggregate and maintain this information, which makes it hard to implement the max-min zPmin algorithm for large networks. Instead, we propose another on-line algorithm called zone-based routing that relies on max-min zPmin and is scalable. Our experiments show that the performance of zone-base routing is very close to the performance of max-min zPmin with respect to optimizing the lifetime of the network. Zone-based routing is a hierarchical approach where the area covered by the (sensor) network is divided into a small number of zones. To send a message across the entire area we find a "global" path from zone to zone and give each zone control over how to route the message within itself. Thus, zone-based power-aware routing consists of (1) an algorithm for estimating the power level of each zone; (2) an algorithm computing a path for each message across zones; and (3) an algorithm for computing the best path for the message within each zone (with respect to the power lifetime of the zone.)
More details can be found in our Mobicom 2001 paper.