Department of Electrical Engineering

National Taiwan University

Taipei, Taiwan

wsc@lion.ee.ntu.edu.tw

Department of Electrical Engineering

National Taiwan University

Taipei, Taiwan

cylin@lion.ee.ntu.edu.tw

Department of Electrical Engineering

National Taiwan University

Taipei, Taiwan

Phone: +886-2-2368-9172

FAX: +886-2-2363-8247

sykuo@cc.ee.ntu.edu.tw

In this paper, we present a localized algorithm for constructing power-efficient topology for wireless ad hoc networks. The constructed topology is sparse, has a constant bounded power stretch factor, and the total transmission power is low. In addition, the time complexity of our algorithm to generate a solution is also low and the energy for each mobile node can thus be further saved, as computations also consume power from a mobile computer.

Wireless ad hoc networks, topology control, power consumption.

A wireless ad hoc network is formed from mobile nodes without using an infrastructure. The lack of a physical backbone poses a strong need of topology control of the network. Also, due to the finite power supply of a mobile computer, power conservation has been widely used as a primary control parameter in the design of protocols for ad hoc networks. Therefore, the problem of power-efficient topology control has been attracting more and more researchers from the areas of mobile computing and networking.

A wireless ad hoc network can be modeled by a weighted directed graph *G* = (*V*, *E*), where *V*
represents the set of all the mobile nodes and *E* represents a set of edges. Edge (*u*, *v*)
Î
*E* if and only if node *v* is in the transmission range of node *u*. We use ||*uv*|| to denote the
Euclidean distance between node *u* and node *v*. The weight of the edge (*u*, *v*) is the power
consumed for transmitting signal from node *u* to node *v*. It's value can be formulated as ||*uv*||* ^{
b
}*in the most widely-used power-attenuation model, where

In this paper, we assume that each mobile node has a GPS receiver for acquiring its own location information. We assume that
initially all mobile nodes are operated at full transmission power and have the transmission radius equal to one unit by a
proper scaling. Consequently, the resulted graph *G* will be a unit-disk graph (denoted as UDG (*V*))and there is
an edge between two nodes if and only if their Euclidean distance is at most one. We assume that UDG (*V*) is strongly
connected and all mobile nodes have unique identifiers (*ID*). Wireless ad hoc networks are power constrained, and it
is thus undesirable to ask each node to transmit with maximum power. As a result, each mobile node should adjust its
transmission power to potentially reduce the total power consumption while still maintain network connectivity. Due to the
characteristics of wireless ad hoc networks, it is preferred that the underlying network topology can be constructed in a
localized manner. Let *f* be a complete transmission power assignment on *V* and *G _{f}* be the
associated communication graph. We adopt the definitions of

In [3] Rodoplu and Meng described a distributed protocol for constructing a topology that guarantees the least-power path
between every pair of nodes that are connected in a given graph. Recently, Li *et* *al*. [4] proposed a protocol
based on their results but performs better and is computationally simpler. In [5] Li and Wan proposed a distributed
position-based protocol to construct an enclosure graph for conserving power in one communication session. All these works focus on constructing a subgraph of *G* that contains the
minimum-power topology, namely, a subgraph that is the union of all the least-power paths. On the other hand, the problems
of finding a complete transmission power assignment with optimization criteria of the maximum or total transmission power
assigned has been studied in [6,7]. In [1] Li *et* *al*. discussed the trade-off between sparseness and power
efficiency of the topology. They also studied the power efficiency property of several well-known proximity graphs.

For simplicity, we first assume that each node in the network is stationary. While considering a complete transmission power
assignment *f*, there is obviously a trade-off between total-cost of *f* and power stretch factor of *G _{f
}*since reducing the transmission power of each node may diminish least-power paths or vice versa. The problem of
finding a complete transmission power assignment

Our algorithm consists of two phases. In the first phase we construct the constrained Gabriel graph GG (*G*) over the
unit disk graph UDG (*V*). Here we choose GG (*G*) since it can be constructed locally and efficiently and has a
power stretch factor one. In addition, the constrained Gabriel graph was used as a subgraph in several important routing
protocols. Nevertheless, any other geometry structure that guarantees a constant bounded power stretch factor can be used in
this phase. Suppose that GG (*G*) is associated with a transmission power assignment *f*. For each node *u*,
if a logical link (*u*, *v*) of GG (*G*) satisfies the equation ||*uv*||* ^{
b
}* =

In the second phase, we eliminate the critical links that are replaceable with alternative paths. For each critical link (
*u*, *v*), node *u* tries to search a path that reaches node *v* based on its local information. We call
such path the replacing path of (*u*, *v*). Whenever a node *u* finds itself having the highest priority and
*ps* (*u*) > 0 within its two-hop neighborhood, it starts a search for the replacing paths. The searching process
is based on Dijkstra's algorithm. However, for each node *u*, no global knowledge of the network topology is available,
consequently, we ask *u* to construct a subgraph *G'* (*u*) = (*V'*, *E'*) on top of GG (*G*)
based on the location and transmission radius information of the nodes in its vicinity. A node *v _{i}* belongs
to

Figure 1. Illustrative example.

If all the critical links are excised, the priority of *u* is recalculated, with the critical links decided by a new
value of *f* (*u*) that corresponds to the minimum operational power needed to cover the remaining logical links.
Node *u* then disseminates its new priority and replacing paths to its two-hop neighborhood by a notification message.
Each constituent link in the replacing paths is tagged as a replacing link. For each node *w* with *ps* (*w*)
> 0, if *w* receives a notification message, it first checks if any of its critical links is tagged as replacing, if
yes, *w* sets *ps* (*w*) to 0 and disseminates its new priority to its two-hop neighborhood. Otherwise, if
node *w* finds its priority is the local maximum within its two-hop neighborhood, it starts to search the replacing
paths following the above steps. This searching procedure is repeated until every node *v _{i}* in the network
has

In this paper, we show how to construct a power-efficient topology for wireless ad hoc networks in a localized manner. The topology constructed by our algorithm has several desired features such as sparse and constant bounded power stretch factor. To develop a localized algorithm for constructing topologies in which the total transmission power assigned is within a constant factor of the optimal cost and that its power stretch factor is still bounded by a constant should be of interesting work.

- X.-Y. Li, P.-J. Wan, Y. Wang, and O. Frieder, "Sparse Power Efficient Topology for Wireless Networks,"
*HICSS*, Hawaii, 2002. - R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang, "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks,"
*IEEE INFOCOM 2001*, pp. 1388-1397, April 2001. - V. Rodoplu and T. H. Meng, "Minimum Energy Mobile Wireless Networks,"
*IEEE J. Selected Areas in Communications*, 17(8):1333-1344, August 1999. - L. Li and J. Halpern, "Minimum Energy Mobile Wireless Networks Revisited,"
*IEEE International Conference on Communications (ICC)*, June 2001. - X. -Y. Li and P.-Jun Wan , "Constructing Minimum Energy Mobile Wireless Networks,"
*ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)*, Long Beach, California, Oct 4-5, 2001. - R. Ramanathan and R. Rosales-Hain, "Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment,"
*IEEE INFOCOM*, 2000. - L. Kirousis, E. Kranakis, D. krizanc, and A. Pelc, "Power Consumption in Packet Radio Networks,"
*Symposium on Theoretical Aspects of Computer Science (STACS)'97*1997.