nbhkdz.com冰点文库

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

Wen-Zhan Song ?

July 14, 2004 Abstract. Topology control in wireless ad hoc networks is to select a subgraph of the communication graph (when all nodes use their maximum transmission range) with some properties for energy conservation. In this paper, we propose two novel localized topology control methods for homogeneous wireless ad hoc networks. Our ?rst method constructs a structure with the following attractive properties: power 1 ef?cient, bounded node degree, and planar. Its power stretch factor is at most ρ = 1?(2 sin π )β , k and each node only has to maintain at most k + 5 neighbors where the integer k > 6 is an adjustable parameter, and β is a real constant between 2 and 5 depending on the wireless transmission environment. It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can be represented in O(log n) bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is O(log n) bits. Our second method improves the degree bound to k, relaxes the theoretical power span√ β ning ratio to ρ = 1?(2√22sin π )β , where k > 8 is an adjustable parameter, and keeps all other properties. We show that the second structure can be constructed using at most 3n messages, where each message has size of O(log n) bits. We also experimentally evaluate the performance of these new energy ef?cient network topologies. The theoretical results are corroborated by the simulations: these structures are more ef?cient in practice, compared with other known structures used in wireless ad hoc networks and are easier to construct. In addition, the power assignment based on our new structures shows low energy cost and small interference at each wireless node. Keywords: Wireless ad hoc networks, topology control, bounded degree, planar, spanner, ef?cient localized algorithm, power assignment.

k

Yu Wang ?

Xiang-Yang Li?

Ophir Frieder?

1. Introduction Wireless ad hoc networks have been undergoing a revolution that promises to have a signi?cant impact throughout society. Unlike traditional ?xed infrastructure networks, there is no centralized control over ad hoc wireless networks, which consist of an arbitrary distribution of radios in certain geographical area. In ad hoc networks, mobile devices can communicate via

Department of Computer Science, Illinois Institute of Technology, 10 W. 31st Street, Chicago, IL 60616. Email: songwen@iit.edu, xli@cs.iit.edu, ophir@cs.iit.edu. The work of Xiang-Yang Li is partially supported by NSF CCR-0311174. ? Department of Computer Science, University of North Carolina at Charlotte, 9201 University City Blvd, Charlotte, NC 28223. Email: wangyu@ieee.org c 2004 Kluwer Academic Publishers. Printed in the Netherlands.

?

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.1

2 multi-hop wireless channels; a node can reach all nodes in its transmission region, while two far-away nodes communicate through the message relaying by intermediate nodes. Wireless ad hoc networks trigger many challenging research problems, as it intrinsically has many special characteristics and some unavoidable limitations, compared with other wired or wireless network. An important requirement of these networks is that they should be self-organizing, i.e., transmission ranges and data paths are dynamically restructured with changing topology. Energy conservation and network performance are probably the most critical issues in ad hoc wireless networks, because wireless devices are usually powered by batteries only and have limited computing capability and memory. The topology control technique is to let each wireless device adjust its transmission range and select certain neighbors for communication, while maintaining a structure that can support energy ef?cient routing and improve the overall network performance. By enabling each wireless node shrinking its transmission power (which is usually much smaller than its maximal transmission power) to suf?ciently cover the farthest selected neighbor, topology control can not only save energy and prolong network life, but also can improve network throughput through mitigating the MAC-level medium contention. Unlike traditional wired networks and cellular wireless networks, the wireless devices are often moving during the communication, which could change the network topology in some extent. Hence it is more challenging to design a topology control algorithm for ad hoc wireless networks: the topology should be locally and self-adaptively maintained without affecting the whole network, and the communication cost during maintaining should not be too high. Topology control has drawn signi?cant research interest (Gr¨ newald et al., u 2002; Li et al., 2001a; Li et al., 2001b; Li et al., 2002b; Rajaraman, 2002; Ramanathan and Rosales-Hain, 2000; Wang et al., 2002; Wattenhofer et al., 2001) in last few years. Different topologies have different properties, however, none of them can achieve all three preferred properties for unicast applications on wireless ad hoc networks: power spanner, planar, degree-bounded. Until recently, Wang and Li (Wang and Li, 2003) proposed a localized algorithm to build a degree-bounded planar spanner both in centralized and distributed way, which is based on the combination of localized Delaunay triangulations (LDel) (Li et al., 2002a) and Y ao structure (Yao, 1982). It is the ?rst localized algorithm that can achieve all the three desirable features. However, the node degree of their structure can reach 25 in the worst case; and the communication cost of their method can be large, although it is shown that the total number of messages is O(n), the hidden constant could be as high as several hundreds since the method needs to collect the 2-hop information for every node.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.2

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

3

In this paper, we propose two novel methods to build a power ef?cient planar structures with much less communication costs and lower node degree bounds. Our ?rst structure has the following attractive properties: 1. It is power ef?cient: given any two nodes u and v, there is a path connecting them in the structure with a total power cost no more than ρ = 1 times of the power cost of any path connecting them in the 1?(2 sin π )β k original homogeneous network; 2. Its node degree is bounded from above by a positive constant k + 5 where integer k > 6 is an adjustable parameter; 3. It is a planar structure, which enables several localized routing algorithms; 4. It can be constructed and maintained in a localized and dynamic way. Moreover, by assuming that the node ID and its position can be represented in O(log n) bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is O(log n) bits. Our second method reduces the degree bound to k, and keeps all other properties, except that the theoretical power spanning ratio is relaxed to ρ =

√ β √2 1?(2 2 sin

the second structure can be constructed using at most 3n messages, where each message has size of O(log n) bits. We also experimentally evaluate the performance of these new energy ef?cient network topologies. The theoretical results are corroborated in the simulations: our new structures are more ef?cient in practice and easier to construct, compared to other known structures used in wireless ad hoc networks. By shrinking the transmission range of each node to reach the farthest neighbors in our new structures, the experiment shows that each node indeed costs low energy and has a small number of physical neighbors. The physical neighbors are those nodes within its transmission region, and smaller number of physical neighbors means less interference. The rest of the paper is organized as follows. In Section 2, we describe some most preferred properties of topology control protocol in wireless ad hoc networks and review the related works in this area. We then present our two localized methods, in Section 3, to construct degree-bounded planar power spanners for U DG(V ) with total communication cost O(n) under the broadcasting communication model. In Section 4, we conduct extensive simulations to validate our theoretical results. Finally, we conclude the paper in Section 5.

π β ) k

, where k > 8 is an adjustable parameter. We show that

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.3

4 2. Preliminaries 2.1. N ETWORK M ODEL A wireless ad hoc network (or sensor network) consists of a set V of n wireless nodes distributed in a two-dimensional plane. Each node has the same maximum transmission range R. 1 By a proper scaling, we assume that all nodes have the maximum transmission range equal to one unit. These wireless nodes de?ne a unit disk graph U DG(V ) in which there is an edge between two nodes iff their Euclidean distance is at most one. In other words, we assume that two nodes can always receive the signal from each other directly if the Euclidean distance between them is no more than one unit. Hereafter, U DG(V ) is always assumed to be connected. We also assume that all wireless nodes have distinctive identities and each wireless node knows its position information either through a low-power Global Position System (GPS) receiver or some other ways. More speci?cally, in our protocol, it would be enough if each node knows the relative position of its one-hop neighbors. The relative position of neighbors can be estimated by the direction of signal arrival and the strength of signal. By one-hop broadcasting, each node u can gather the location information of all nodes within its transmission region. In the most common power-attenuation model, the power to support a link uv is assumed to be uv β , where uv is the Euclidean distance between u and v, β is a real constant between 2 and 5 depending on the wireless transmission environment. 2.2. P REFERRED P ROPERTIES Wireless ad hoc network topology control schemes are to maintain a structure that can be used for ef?cient routing (Bose et al., 2001; Karp and Kung, 2000) or improve the overall networking performance (Gr¨ newald et al., 2002; Li u et al., 2001a; Ramanathan and Rosales-Hain, 2000), by selecting a subset of links or nodes used for communication. In the literature, the following desirable features are well-regarded and preferred in wireless ad hoc networks: Power Spanner: In ad hoc wireless networks, two far-apart nodes can communicate with each other through the relay of intermediate nodes; hence, each node only need set small transmission ranges. This has two advantages: (1) reducing the signal interference, (2) saving transmission power. To guarantee the advantage, a good network topology should be energy ef?cient, that is to say, the total power consumption of the shortest path (most power ef?cient path) between any two nodes in the ?nal topology should not exceed

In practice, R can be de?ned as the minimum of all the maximum node transmission ranges.

1

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.4

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

5

a constant factor of the power consumption of the shortest path in original network. Given a path v1 v2 · · · vh connecting two nodes v1 and vh , the energy h?1 cost of this path is j=1 vj vj+1 β . The path with the least energy cost is called the shortest path in a graph. Formally speaking, a subgraph H is called a power spanner of a graph G if there is a positive real constant ρ such that for any two nodes, the power consumption of the shortest path in H is at most ρ times of the power consumption of the shortest path in G. The constant ρ is called the power stretch factor. A power spanner is usually energy ef?cient for routing. Obviously, for any weighted graph G and a subgraph H ? G, we have the following lemma. LEMMA 1. (Li et al., 2001b) Subgraph H of a graph G has stretch factor ρ if and only if for any link uv ∈ G, dH (u, v) ≤ ρ · dG (u, v), where dG (u, v) is the total power consumption of the shortest path between u and v in G. Lemma 1 implies that, to generate a power ef?cient structure, we only need to guarantee that any two adjacent nodes u and v in G are connected by a path in H with energy cost no more than a constant factor of the cost of link uv. Degree Bounded: It is also desirable that the node degree in the constructed topology is small and bounded from above by a constant. A small node degree reduces the MAC-level contention and interference, also may help to mitigate the well known hidden and exposed terminal problems. A common believe in the literature is that small node degree will imply small interference. Although this is recently disproved in (Burkhart et al., 2004), we found that in practice our structures with small node degree indeed have small interferences (it is because that our structures often select short links). Structures with a small node degree also have applications in Bluetooth wireless networks. In Bluetooth based wireless ad hoc networks, the master node degree is preferred to be less than 7, according to Bluetooth speci?cations, to maximize the ef?ciency. In addition, a structure with small degree will improve the overall network throughout (Kleinrock and Silvester, 1978). Planar: Many routing algorithms require the planar topology to guarantee the message delivery, such as right hand routing, Greedy Perimeter Stateless Routing (GPSR) (Karp and Kung, 2000), Greedy Face Routing (GFR) (Bose et al., 2001), Adaptive Face Routing(AFR) (Kuhn et al., 2002), and Greedy Other Adaptive Face Routing (GOAFR) (Kuhn et al., 2003). Ef?cient Localized Construction: Due to the limited resources and high mobility of the wireless nodes, it is preferred that the underlying network topology can be constructed and maintained in a localized manner. Here a distributed algorithm constructing a graph G is a localized algorithm if every node u can exactly decide all edges incident on it based only on the information of all nodes within a constant hops of u. More importantly, we expect

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.5

6 that the total communication cost of the algorithm is O(n) messages, where each message is O(log n) bits; the time complexity of each node running the algorithm is at most O(d log d), where d is the number of 1-hop or 2-hop neighbors. 2.3. R ELATED W ORKS Several structures (such as relative neighborhood graph RNG, Gabriel graph GG, Yao structure, etc) have been proposed for topology control in wireless ad hoc networks. The relative neighborhood graph, denoted by RN G(V ) (Toussaint, 1980), consists of all edges uv such that the intersection of two circles centered at u and v and with radius uv do not contain any node w from the set V . See Figure 1(a). The Gabriel graph (Gabriel and Sokal, 1969) GG(V ) contains edge uv if and only if disk(u, v) contains no other points of V , where disk(u, v) is the disk with edge uv as a diameter. See Figure 1(b). Denote GG(U DG) and RN G(U DG) as the intersection of U DG(V ) with GG(V ) and RN G(V ) respectively. Both GG(U DG) and RN G(U DG) are connected, planar, and contain the Euclidean minimum spanning tree M ST of V if U DG is connected. Delaunay triangulation, denoted by Del, is also used as an underlying structure by several routing protocols. Here a triangle △uvw belongs to Delaunay triangulation Del if its circumcircle does not contain any node inside. Let Del(U DG) be the set of edges in Delaunay, which are also in UDG. It is well known that RN G(U DG) ? GG(U DG) ? Del(U DG). The structure Del(U DG) has a bounded length spanning ratio (Li et al., 2002a); both RN G(U DG) and GG(U DG) are not length spanners; GG(U DG) is power ef?cient. The Yao graph (Yao, 1982) with an integer parameter k > 6, denoted by ?→ ? Y Gk (U DG), is de?ned as follows. At each node u, any k equally-separated rays originating at u de?ne k cones. In each cone, choose the shortest edge uv ∈ U DG(V ) among all edges emanated from u, if there is any, and add → a directed link ? Ties are broken arbitrarily or by ID. See Figure 1(c). uv. The resulting directed graph is called the Yao graph. Let Y Gk (U DG) be ?→ ? the undirected graph by ignoring the direction of each link in Y Gk (U DG). Some researchers used a similar construction named θ-graph (Lukovszki, 1999; Keil and Gutwin, 1992). The difference is that it chooses the edge which has the shortest projection on the axis of each cone instead of the shortest edge in each cone. In (Bose et al., 2001; Karp and Kung, 2000), relative neighborhood graph and Gabriel graph are used as underlying network topologies. However, Bose, et al. (Bose et al., 2002a) proved that the length stretch factors of these two √ graphs are Θ(n) and Θ( n) respectively. Actually, they are at most n ? 1 √ and n ? 1 (Wang et al., 2003). Moreover, in (Li et al., 2001b), Li, et al. showed that the power stretch factor of RNG is n ? 1 while the power stretch

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.6

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

7

u

v

u

v

11111 00000 11111 00000 11111 00000 11111 u 00000 11111111 00000000 11111 00000 11111111 00000000

(a) RNG

(b) GG

(c) YG

Figure 1. The de?nitions of RN G, GG, and Y G. The shaded area is empty of nodes inside.

factor of GG is 1. Recently, some researchers (Li et al., 2001b; Wattenhofer et al., 2001) proposed to construct the wireless network topology based on Yao graph. It is known that the length/power stretch factor and the node outdegree of Yao graph are bounded by some positive constants. But as Li et al. mentioned in (Li et al., 2001b), all these three graphs can not guarantee node degree bounded (for Yao graph, the node in-degree could be as large as Θ(n)). In (Li et al., 2001b; Li et al., 2002b), Li, et al. further proposed to use another sparse topology, Yao and Sink, that has both a constant bounded node degree and a constant bounded length/power stretch factor. However, all these graphs (Li et al., 2001b; Li et al., 2002b; Wattenhofer et al., 2001) are not guaranteed to be planar. In (Li et al., 2002a) Li, et al. proposed a planar spanner localized Delaunay triangulations (LDel), and in (Gao et al., 2001) Gao et al. proposed a planar spanner Restricted Delaunay Graph for wireless ad hoc networks. Unfortunately, both of them might result in an unbounded node degree. Bose et al.(Bose et al., 2002b) proposed a centralized method with running time O(n log n) to build a degree-bounded planar spanner for a twodimensional point set. They construct a planar t-spanner for a given nodes set V , for t = (1 + π) · Cdel ? 10.02, such that the node degree is bounded from above by 27. Hereafter, we use Cdel to denote the spanning ratio of the Delaunay triangulation (Dobkin et al., 1990; Keil and Gutwin, 1989; Keil and Gutwin, 1992). However the distributed implementation of this centralized method takes O(n2 ) communications in the worst case for a set V of n nodes. Recently, Wang and Li (Wang and Li, 2003) proposed the ?rst ef?cient localized algorithm to build a degree-bounded planar spanner BP S(U DG) for wireless ad hoc networks. It has a length spanning ratio t = max{ π , π sin α + 2 2 1} · Cdel (1 + ?), and each node has degree at most 19 + ? 2π ?. Here 0 < α α ≤ π/3 is an adjustable parameter, and Cdel ≤ 4 9 3 π is the spanning ratio of the Delaunay triangulation. Though their method can achieve all these three desirable features: planar, degree-bounded, and power ef?cient, the theoretical bound on the node degree of their structure is a large constant. For example, when α = π/6, the theoretical bound on node degree is 25. In addition, the communication cost of their method can be very high, although

√

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.7

8 it is O(n) theoretically, because it needs to collect the 2-hop information for every wireless node. Even as mentioned in (Wang and Li, 2003), the method by Calinescu (Cˇ linescu, 2003) to collect 2-hop neighbors information takes a O(n) messages, however the hidden constant can be as high as several hundreds. Concerning this large communication cost and the possible large node degree, we propose two communication ef?cient methods to construct small degree-bounded planar power ef?cient structures, which are more practical in wireless ad hoc networks. The construction of our second structure only needs at most 3n messages, the tradeoff is that theoretically our structures do not have constant length spanning ratio.

3. Proposed Approaches We propose two novel methods to build power ef?cient planar structures with much less communication costs and lower node degree bounds compared with previously best known planar power ef?cient structures (Wang and Li, 2003) called BP S, see Figure 2(b). Before presenting our methods, we ?rst present a localized construction of Gabriel graph structure for homogeneous wireless ad hoc networks.

(a) UDG

(b) BPS

(c) GG and YaoGG

(d) OrdYaoGG

(e) SYaoGG

Figure 2. Several planar power spanners on the UDG shown in (a). Here k = 9 for Yao related construction.

ALGORITHM 1. C ONSTRUCT G ABRIEL G RAPH 1. In the beginning, each node u locally broadcasts a message with IDu , and its position (xu , yu ) to all nodes in its transmission region. Each node

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.8

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

9

u initiates sets EU DG (u) and EGG (u) to be empty. Here EU DG (u) and EGG (u) are the set of links known by u in UDG and GG respectively. 2. At the same time, each node u processes the incoming messages. Assume that node u gets a message from some new node v, then it adds a link uv to EU DG (u). Node u checks whether there is another link uw ∈ EU DG (u) where w ∈ disk (u, v). If no such link uw exists, then it adds uv to EGG (u). On the other hand, for any link uw ∈ EGG (u), node u checks whether v ∈ disk (u, w), if the condition holds, then u removes link uw from EGG (u). Node u repeats this step until no new messages are received. 3. All links uv in EGG (u) are the ?nal links in GG(U DG) incident on u. We ?rst show that Algorithm 1 builds the structure GG(U DG) correctly. For any link uv ∈ GG(U DG), clearly, we cannot remove them in Algorithm 1. For a link uv ∈ GG(U DG), assume that a node w is inside disk (u, v) and both links uw and wv belong to UDG. If node u gets the message from w ?rst, and then gets the message from v, clearly, uv cannot be added to EGG (u). If node u gets the message from v ?rst, then node u will remove link uv from EGG (u) (if it is there) when u gets the information of node w. It is not dif?cult to prove that structure GG(U DG) is connected by induction if UDG is connected. In addition, since we remove a link uv only if there are two links uw and wv with w inside disk (u, v), it is easy to show that the power stretch factor of structure GG(U DG) is exactly 1 (Li et al., 2002b). In other words, the minimum power consumption path for any two nodes u and v in UDG is still kept in GG(U DG). Remember that here we assume the power needed to support a link uv is uv β , for β ∈ [2, 5]. Notice that, as mentioned in the literature, GG(U DG) is not degree bounded. For example, when all n ? 1 nodes are uniformly distributed on a unit circle with the nth node u as center, the node degree of u is n ? 1. Figure 2(a) shows another example, where (n ? 1)/2 nodes are uniformly distributed on a unit circle, another (n ? 1)/2 nodes are on a half unit circle, and both circles have the nth node u as center. The node degree of center is (n ? 1)/2 = O(n) in GG, as shown in Figure 2(c). The following result is folklore. THEOREM 2. (Li et al., 2001b) GG(U DG) is a planar power spanner, whose power stretch factor is 1. Hereafter, if it is clear that these structures are constructed on U DG(V ), we omit the (U DG) in the representation of all structures. For instance, we will use GG to denote Gabriel Graph instead of GG(U DG).

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.9

10 3.1. D EGREE -( K +5) P LANAR P OWER S PANNER (O RDYAO GG) One natural way to construct a degree-bounded planar power spanner is to apply the Yao structure on Gabriel graph. In (Li et al., 2002b), Li, et. al showed that the ?nal structure by directly applying the Yao structure on GG is a planar power spanner, called Y aoGG, however its in-degree can be as large as O(n), as in the example shown in Figure 2(c). In this paper, we present a new method by applying the ordered Yao structures on Gabriel graph to bound node degree. The idea is similar with the method in (Wang and Li, 2003) where they apply Yao structures on the localized Delaunay triangulations to build a degree-bounded planar length spanner based on a locally computed ordering of nodes. The major differences are 1) here we only use 1-hop information instead of two hop information, which reduces communication cost signi?cantly; 2) we use Gabriel graph instead of the localized Delaunay triangulation, which makes the localized method much simpler and more ef?cient; 3) the method used to bound the degree is also different. Since Gabriel graph is power ef?cient, we will then bound the node degree of the Gabriel graph by removing some edges without destroying the power spanner property. We will process the nodes in a special order. When we process a node u, we use the Yao structure to decide which unprocessed neighbors will be selected, while keeping already processed neighbors. Our special order makes sure that when processing a node, it only has at most 5 processed neighbors. The algorithm detail is as follows. ALGORITHM 2. C ONSTRUCT D EGREE -( K +5) P LANAR P OWER S PAN OrdY aoGG 1. First, each node self-constructs the Gabriel graph GG locally based on the strategy described in Algorithm 1. Let NGG (u) be the neighbors set of node u in GG. 2. Second, each node u decides its order π locally as follows. Two data structures at each node u are used in this algorithm: (1) π[ ]: the list of the local orders of all neighbors of u (including itself) in GG, where each element is initially set as 0, i.e., unordered. Hence π[v] denotes the order of node v, which is a neighbor of node u or node u itself. (2) d(u): the number of its unordered neighbors known by node u so far, which is initially set as its degree in GG. (3) DO Q UERY: a ?ag indicating whether this node need perform a query to its neighbors now. Initially, the ?ag is set as FALSE if its degree d(u) >

NER

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.10

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

11

5 and T RUE otherwise. Notice that when the node is ordered (i.e., π[u] > 0), this ?ag DO Q UERY is always set to FALSE. The strategy of ?nding a local ordering is as follows: a) If DO Q UERY is true, then node u queries all its unordered neighboring nodes by sending a message Q UERY. The query message Q UERY contains only the ID of node u. b) When an unordered node v receives a message Q UERY from a neighboring node u in GG, it checks whether d(v) ≤ 5 and ID(v) < ID(u). If so, node v replies node u a message FAILED Q UERY with the IDs of itself and u. Otherwise, node v replies node u a message PASSED Q UERY with the IDs of itself and u. c) If node u received a message FAILED Q UERY, node u sets DO Q UERY to FALSE. Node u will not perform such query until its degree is decreased later, so there are at most 5 rounds of queries. d) If node u receives message PASSED Q UERY from all its unordered neighbors, node u sets π[u] = max{π[v] | v ∈ NGG (u)} + 1, sets DO Q UERY to FALSE, and broadcasts π[u] to its neighbors NGG (u) through message M YO RDER. e) If node v receives a M YO RDER message from its neighbor u in GG saying that π[u] = k, it records π[u] locally, and updates its d(v) = d(v) ? 1. If π[v] = 0 and d(v) ≤ 5, then node v sets DO Q UERY to T RUE. f) When node u ?nds that d(u) = 0 and π[u] > 0, it can go to next step to bound its degree in the ?nal structure. 3. All nodes self-form the ?nal topology based on the local ordering π as follows. Initially, all nodes are marked with W HITE color, i.e., unprocessed. Let NOY GG (u) be the set of neighbors of u in the ?nal topology, which is initialized as NGG (u). a) If node u is unprocessed (marked W HITE) and has the largest order π[u] among all its W HITE neighbors in NGG (u), it divides its transmission region (which is a unit disk centered at the node u) into k equal-sized cones, keeps one nearest W HITE neighbor v ∈ NOY GG (u) (if available) in each cone and deletes others. Node u marks itself B LACK, i.e., processed, and noti?es all nodes in NGG (u) of the deleted edges through a broadcast message U PDATE N. The message U PDATE N includes all unselected neighbors.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.11

12 b) Once the node u receives the message U PDATE N for deleting edge vu from its neighbor v, it deletes the node v from its local list NOY GG (u). 4. When all nodes are processed, all the remaining edges {uv|v ∈ NOY GG (u), ?v ∈GG} form the ?nal network topology OrdY aoGG. Each node then can shrink its transmission range as long as it suf?ciently reaches its farthest neighbor in the ?nal topology.

LEMMA 3. The ?nal topology OrdY aoGG is a planar graph, whose node degree is bounded by k + 5 where k > 6 is an adjustable parameter. P ROOF. The Yao graph construction does not add any edges to original graphs, on the contrast, it only deletes edges. Hence the planar property is inherited from GG graph. We then show that each node degree is bounded by k + 5 in OrdY aoGG. To prove this, we ?rst review one important property for planar graph: there always exists a node with degree at most 5. Clearly, our local ordering is able to start, since there is at least one node with degree at most 5 initially. Once a node is ordered, the neighboring nodes will update their node degree accordingly. We clearly can repeat this procedure until all nodes are ordered, since the Gabriel graph induced on all unordered nodes is always planar. Let Pu be the neighbors of node u in GG that are ordered after u. From our processing order of nodes, these nodes will be marked B LACK before node u, i.e., being processed before u. We will then call Pu predecessors of node u. Clearly, in the local ordering π, every node u has at most 5 edges to its predecessors Pu in GG, that is to say, before it is marked with B LACK, it has at most 5 processed neighbors. When node u is processed, it could select at most k other unprocessed neighbors into ?nal structure, thus, its degree is bounded by k + 5. Once a node is marked with B LACK color, its degree will be kept unchanged according to our algorithm. This ?nishes our proof. In Figure 2, we show that GG and Y aoGG cannot bound the node degree, while our structure OrdY aoGG is indeed degree-bounded by k + 5 = 14, here k is set as 9 in our experiment. We then prove that the ?nal structure is also power ef?cient. LEMMA 4. OrdY aoGG is a power spanner of U DG, and its power span1 ning ratio is ρ = 1?(2 sin π )β , where k > 6 is an adjustable parameter and β ∈ [2, 5] is a constant depending on the transmission environment. P ROOF. Since the GG is a power spanner with spanning ratio 1, we only need prove that OrdY aoGG is a power spanner of GG with spanning ratio

k

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.12

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

13

1 ρ = 1?(2 sin π )β . The proof is similar to the proof for Yao on UDG (Li et al., k 2001b) and the later proof of Theorem 7. Due to space limitation, we omit the details here.

We then analyze the total communication cost of Algorithm 2. (1) Clearly, the ?rst step of building GG can be done using only n messages: each message contains the ID and geometry position of a node. (2) The second step of computing local ordering can be done in 21n messages: First, an unordered node u sends out at most 5 query messages containing its ID. Each such query message is replied by d(u) neighbors. Since we perform a new query only if d(u) decreases from last failed query, the total messages used for queries is at most n · 5 (i + 1) = 20n messages. Second, an ordered node i=1 u sends a message containing its ID and the local ordering πu computed. The second step can thus be done in at most 21n messages. (3) In the third step, a processed node u will inform all its W HITE neighbors v about the deletion of the edge uv from Gabriel Graph (which has at most 3n edges). In the ?nal topology OrdYaoGG, at least n ? 1 edges were kept to guarantee the connectivity, thus, the total number of such messages is at most 2n. In summary, the following lemma directly follows. LEMMA 5. Assuming that both the ID and the geometry position can be represented by log n bits each, the total number of messages of Algorithm 2 is then at most 24n, where each message has at most 2 log n bits. Additional communication and computation cost can be saved, if the degree is expected to be bounded by k + 5 only. The modi?cation is to let all nodes with degree at most k + 5 be initially marked as B LACK, that is to say, they do not participate in the third step in Algorithm 2. Remember that the total messages of our Algorithm 2 is bounded by O(n). This implies that the average number of messages per node is a constant, which is veri?ed in our simulations presented later. However, in the worst case, the number of messages sent by some node could be as large as O(n). Algorithm 2 can be modi?ed to further bound the communication cost of each node. During the Yao construction in the third step, instead of using message U PDATE N to delete the unselected links, each node will notify its neighbors of the kept edges. In other words, the message U PDATE N contains the selected neighbor IDs instead of the deleted neighbor IDs. The communication cost of each node can be bounded since at most k neighbors are kept during Yao construction. It is easy to show that each node sends at most 31 messages during constructing GG and computing the local order: at most 5 Q UERY messages are sent, and at most 25 PASSED Q UERY or FAILED Q UERY messages are sent. The tradeoff is that the total communication cost could be higher than that used in Algorithm 2 if the ?nal topology is denser.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.13

14 3.2. D EGREE - K P LANAR P OWER S PANNER (SYAO GG) Algorithm 2 constructs a planar power ef?cient structure using at most O(n log n) bits communications, and the ?nal structure has a theoretical degree bound k + 5, where k > 6 is a parameter. In this section, we propose a more ef?cient method with much less communication cost during construction. Notice that, the majority communication cost of Algorithm 2 is spent on computing a local ordering of nodes so a bounded node degree is achieved. Our second method will eliminate this step while still achieving a bounded node degree. We still process the nodes in a local order, which can be obtained easily. Each node u uses the Yao structure to decide which neighbors will be kept: always keep the closest processed neighbor if exists, otherwise keep the closest unprocessed neighbor. Clearly, this will bound the node degree, but, as will see later, it is much tricky to prove the ?nal structure is power ef?cient. The second method works as follows. ALGORITHM 3. C ONSTRUCT D EGREE - K P LANAR P OWER S PANNER SY aoGG 1. First, each node self-constructs the Gabriel graph GG locally based on the strategy described in Algorithm 1. 2. All nodes together self-form the ?nal topology as follows. Initially, each node u is marked with W HITE color, i.e., unprocessed, and initializes NSY GG (u) as the set of all the neighbor nodes in GG. a) If a W HITE node u has the smallest ID among its W HITE neighbors in GG, it divides its transmission region into k equal-sized cones where k > 8 is an adjustable parameter. In each cone, node u checks whether there are some B LACK nodes in NSY GG (u) within same cone: i) Yes. Node u keeps the closest B LACK neighbor v ∈ NSY GG (u) among them and deletes all the other links in the cone; ii) No. Node u keeps a closest W HITE neighbor v ∈ NSY GG (u) (if available) among them and deletes all the other links in the cone. After processing all k cones, node u marks itself B LACK, i.e. processed, then noti?es each deleted neighboring node v in GG by a broadcasting message U PDATE N. b) Once a W HITE node v receives the message U PDATE N from a neighbor u in GG, it checks whether itself is in the nodes set for deleting: if so, it deletes the sending node u from NSY GG (v), otherwise, marks u as BLACK in its local list NSY GG (v).

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.14

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

15

c) Once a B LACK node v receives the message U PDATE N from a neighbor belonging to NSY GG (v), it checks whether itself is in the nodes set for deleting: if so, it deletes the sending node u from NSY GG (v), otherwise, marks u as BLACK in its local list NSY GG (v). 3. When all nodes are processed, all selected edges {uv|v ∈ NSY GG (u), ?v ∈GG} form the ?nal network topology, denoted by SY aoGG. Each node then can shrink its transmission range as long as it suf?ciently reaches its farthest neighbor in the ?nal topology. Algorithm 3 further reduces the communication cost during constructing a degree-bounded planar power spanner, because we do not demand the local ordering before construction. Our analysis of the structure SY aoGG relies on the following simple observation. LEMMA 6. In GG graph, if two edges uv and uw emanates from a single node u, then both the angle uwv and uvw must be acute. P ROOF. We prove it by inducing contradiction. Suppose the angle uvw is an obtuse angle, then wv < uw , hence, all the three edges uv, vw and uw are in the UDG graph. Thus, the circle with diameter uw contains the node v inside. According to the property of GG graph, edge uw can not be kept during GG construction. The contradiction is induced. This ?nishes the proof. THEOREM 7. The structure SY aoGG is k degree-bounded planar power spanner, whose power stretch factor is at most ρ =

√ β √2 1?(2 2 sin

9 is an adjustable parameter and β ∈ [2, 5] is a constant factor depending on the communication environment. P ROOF. First, the node degree is obviously bounded by k because each node only keeps one undirected edge in each cone. Figure 2(e) illustrates the SY aoGG structure self-constructed on the U DG graph in Figure 2(a). The node degree is indeed at most k = 9. Second, the graph SY aoGG is planar, because the Gabriel graph GG is planar and Algorithm 3 does not add any more edges, thus, the planar property is inherited. In the following, we show that the structure SY aoGG is a power spanner. According to Theorem 2, GG has power spanning ratio 1. Hence, from Lemma 1, it is suf?cient to show that for any nodes u and v with an edge uv ∈ GG, there is a path connecting u and v in SY aoGG with power cost at most ρ · uv β .

π β ) k

, where k ≥

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.15

16 Given any edge uv ∈ GG, we will construct a path u v connecting u and v in SY aoGG. If edge uv is kept in the ?nal structure, then u v 2 when processing node u. is just uv. Otherwise, assume that uv is removed There must exist a link uw selected by node u in the same cone. Then u v is the concatenation of uw with w v, see Figure 3. Notice that node u is marked as processed in this stage. It is possible that the link uw could then be removed by node w later on since node w is not processed when process w, see Figure 4 for illustration, node u. If so, we replace link uw by u details will be explained later. We then prove by induction, on the number of its edges, that the path u v has power cost, denoted by p(u v), at most ρ uv β . Obviously, if there is only one edge in u v, p(u v) = uv β < β ρ uv . Assume that the claim is true for any path with l edges. Then conv with l + 1 edges, which is the concatenation of edge uw sider a path u (or path u w) and the path w v with at most l edges. Without loss of generality, we always assume that the link uv is removed after node u is processed and link uw is selected in the cone. Notice that the link uw could be removed later by node w if w is processed after u, so there are two cases that need to be discussed carefully: 1. The ?rst case is that link uw is kept in the ?nal structure. Remember that, as described in the algorithm, we always select the nearest B LACK neighbor in a cone if it exists; otherwise the nearest W HITE neighbor is selected if it exists.

w

w

u

v

(a) Both w and v are W HITE or B LACK

u

(b) w is B LACK and v is W HITE

v

Figure 3. The link uw is kept in the ?nal structure.

Figure 3 illustrates the situations that a W HITE node u starts Yao construction in the cone. Suppose, we delete uv in the cone and choose edge uw, which is also kept in the ?nal structure. Again, there are two subcases that need to be analyzed: Subcase 1: uw ≤ uv . This subcase happens only when both nodes v and w are processed (or unprocessed), and node u deletes link uv

Notice that an edge uv ∈ GG can only be removed while processing its endpoint node u or node v.

2

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.16

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

17

since the existence of closer processed (or unprocessed) neighbor w. Figure 3(a) illustrates the situation. We bound the length wv respecting to uv . Notice that uw ≤ uv and wuv < θ = 2π . The maximum length of vw is achieved k when uw = uv because the angle uwv is acute according to Lemma 6. Therefore wv ≤ 2 sin By induction, we have p(u v) = uw ≤ uw ≤ uv ≤ ρ uv when ρ ≥

1 1?(2 sin

π β ) k

θ π uv = 2 sin uv . 2 k

β β β

+ p(w + ρ wv

β

v) π β ) uv k

β

+ ρ · (2 sin

β

,

.

Subcase 2: uw > uv . This case happens only when node w is processed while node v is not processed yet, and node u deletes link uv since any processed neighbor has higher priority in our algorithm. Figure 3(b) illustrates the situation. We bound the length wv respecting to uw . Notice that uw > uv and wuv < θ = 2π < π according to Lemma 6. So we have k 4 uv = √ 2 uv . The maximum length of vw is achieved when uw = uv because the angle uwv is acute. Therefore wv ≤ 2 sin By induction, we have p(u v) = uw

β π 4

<

uwv <

uvw <

π 2.

Consequently, uw <

sin sin

π 2 π 4

√ π π uw ≤ 2 2 sin uv . k k

+ p(w

v)

β

≤ uw β + ρ wv β √ π ≤ ( 2)β (1 + ρ(2 sin )β ) uv k β ≤ ρ uv , when ρ ≥

√ β √2 1?(2 2 sin

π β ) k

.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.17

18 2. The second case is that link uw is later removed by node w. We show that the spanning ratio is still kept. Notice that, this case could only succeed Subcase 1. The link uw in Subcase 2, see Figure 3(b), can never be removed in our algorithm, since both node u and w have processed and kept this edge. An edge can only be removed by its endpoints. This is the tricky case in this algorithm.

x w v

(a) processing u

x u w v

(b) processing w

u

Figure 4. Link uv is removed when processing node u (illustrated in the left ?gure) and link uw is then removed by node w later (illustrated in the right ?gure).

Figure 4(a) shows the situation that a W HITE node u selects a link uw in a cone, where the neighbor node w is not processed. Figure 4(b) illustrates the scenario when node w processes its neighbors: since it has two processed3 neighbors u and x in the cone, it will select the nearest processed neighbor in that cone, which is node x. Observe that after node w decided to keep link wx and remove link uw, the link wx will be kept in the ?nal structure since both end nodes w and x are processed and only an unprocessed node can remove its incident links later. Obviously, from the selection procedure, we know that uv ≥ uw ≥ wx . Notice that, both nodes u and x select the node w in one of their cones when they are processed before node w starts its processing. Node w then selects x instead of u because wx is shorter. Consequently, node u does not have any neighbors kept in the node u’s cone shown in Figure 4(b). This is a sharp contrast to our ?rst structure OrdY aoGG, in which every node always keep an edge in each cone if it originally has one neighbor from Gabriel graph. Then the path v u connecting nodes u and v is composed of path v w, link wx and path x u. The total power cost of the path v u is

Node x must also be a processed node, otherwise w will de?nitely select u instead of x according to our rule.

3

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.18

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

19

p(u

v) = wx ≤ wx

β β β

+ p(w + ρ wv

β

v) + p(u

β β

x)

β

+ ρ ux π β ≤ wx + ρ(2 sin ) ( uv k π β ≤ uv (1 + 2ρ(2 sin )β ) k β ≤ ρ uv , when ρ ≥

1 1?2(2 sin

π β ) k

+ uw

)

.

√ β √2 1?(2 2 sin

All conditions about ρ are satis?ed when ρ = the proof.

π β ) k

. This ?nishes

We then analyze the communication cost of Algorithm 3. (1) Clearly, the ?rst step of building GG can be done using only n messages: each message contains the ID and geometry position of a node. (2) In the second step of the algorithm, initially, the number of edges in Gabriel Graph is less than 3n since it is a planar graph. Clearly, there are at most 2n such removed edges since we keep at least n ? 1 edges from the connectivity of the ?nal structure. Thus the total messages used to inform the deleted edges from GG is at most 2n. Then the following lemma directly follows. LEMMA 8. Assuming that both the ID and the geometry position can be represented by log n bits each, the total number of messages by Algorithm 3 is at most 3n, where each message has at most 2 log n bits. Similarly, if the message U PDATE N contains the selected neighbor IDs instead of the deleted neighbor IDs, then the communication cost of each node also can be bounded by k + 1 since at most k neighbors will be kept during Yao construction. Theoretically, compared with OrdY aoGG, the topology SY aoGG has lower node degree bound while higher power spanning ratio bound. Worth to mention that, our simulation later shows the power spanning ratios of OrdY aoGG and SY aoGG are very close in practice.

4. Performance Evaluation on Random Networks We evaluated the performance of our new degree-bounded and planar spanners by conducting simulations on randomly deployed wireless ad hoc networks. In our experiments, we randomly generated a set V of n wireless

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.19

20 nodes and U DG(V ), then tested the connectivity of U DG(V ). If it is connected, we construct different localized topologies on U DG(V ), including our new topologies OrdY aoGG and SY aoGG, some well-known planar spanner topologies GG(Bose et al., 2001; Karp and Kung, 2000), Y aoGG(Li et al., 2002b), and BP S(Wang and Li, 2003). Then we measure the sparseness, the power ef?ciency and the communication cost during construction of these topologies. In the experimental results presented here, we generated n random wireless nodes in a 20×20 square; the parameter k, i.e., the number of cones, is set to 9 when we construct BP S, OrdY aoGG and SY aoGG; the transmission range is set to 8. We tested all preferred properties described in Section 2.2 of these planar structures by varying node number from 30 to 300, where 100 node sets are generated for each case to smooth the possible peak effects caused by some exception examples. The average and the maximum were computed over all these 100 node sets. 4.1. P OWER E FFICIENCY The most important design metric of wireless network topology is perhaps the power ef?ciency, as it directly affects both the node and the network lifetime. So while our new topologies increase the sparseness, how does it affect the power ef?ciency of the constructed network? First, we test power stretch factors of all structures. In our simulations, we set power attenuation constant β = 2. Setting larger β, from our proofs, we expect to see smaller spanning ratios of our structures. In Figure 5, we summarize our experimental results of power stretch factors of all these topologies. It shows all of the power stretch factors are small in practice, just around 1.002, except GG has power stretch factor 1. In other words, the path remaining in the sparse planar structures can estimate the shortest path in the original communication graph without too higher power consumption. It is not surprising that the average/maximum power stretch factors of OrdY aoGG and SY aoGG are at the same level of those of GG while they are much sparser. Another interesting thing to notice is that OrdY aoGG has smaller power spanning ratio than Y aoGG, even though OrdY aoGG is sparser than Y aoGG theoretically and practically (Refer Figure 7). One reason is that OrdY aoGG is more uniform than Y aoGG. Hence, the proper ordering scheme can conserve more energy. Notice that after constructing the sparse structures, a node can shrink its transmission energy as long as it is enough to cover the longest adjacent link in the structure. By this way, we de?ne the node transmission power for each node u in a constructed structure as follows. If u has a longest link, say uv, in the structure, then the node transmission energy of u is uv β . As expected, Figure 6 shows the average node transmission energy of each

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.20

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

21

1.004 GG YaoGG OrdYaoGG SYaoGG BPS

1.0035

1.003 Average Power Spanning Ratio

1.0025

1.002

1.0015

1.001

1.0005

1

0

50

100

150 Number of Nodes

200

250

300

1.5

1.45

1.4 GG YaoGG OrdYaoGG SYaoGG BPS

Maximum Power Spanning Ratio

1.35

1.3

1.25

1.2

1.15

1.1

1.05

1

0

50

100

150 Number of Nodes

200

250

300

Figure 5. Average and maximum power spanning ratio of different topologies.

topology decreases as the network density increases. The power needed by each node in our new structures OrdY aoGG and SY aoGG is almost same with that by GG, which is much less than its maximum transmission energy (which is 8β here β = 2 in our experiment). Each node in BP S need to set higher transmission energy since it has more neighbors. Speci?cally, BPS is a supergraph of the Gabriel graph and our new structures are subgraphs of the Gabriel graph. 4.2. N ODE D EGREE The node degree is an important performance metric in wireless ad hoc networks, since the degree of each node directly relates to its power consumption and the global network performance.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.21

22

30 GG YaoGG OrdYaoGG SYaoGG BPS

25

Average Node Transmission Energy

20

15

10

5

0

0

50

100

150 Number of Nodes

200

250

300

Figure 6. Average node transmission power of different topologies.

The average and maximum node degrees of each topology are shown in Figure 7. It shows that OrdY aoGG and SY aoGG have less number of edges (average node degrees) than Y aoGG, GG and BP S. In other words, these graphs are sparser. Notice that the node degree of BP S is much higher than those of other graphs, since BP S uses many edges from LDel which is a supergraph (thus much denser than) of GG, see Figures 2(b) and (c), while all the other structures discussed here are subgraphs of the Gabriel graph. Recall that theoretically, only BP S, OrdY aoGG and SY aoGG have bounded node degree (both for in-degree and out-degree). In (Li et al., 2001b; Li et al., 2002b), Li et al. gave an example to show that RN G, GG, and LDel could have large node degree (in-degree for Y G and Y aoGG). Notice that, in our experiments, since the wireless nodes are randomly distributed in two dimensional space, it is easy to understand that the maximum node degree of GG and Y aoGG are not as big as the extreme example, however, it can happen. Recall that we proved OrdY aoGG and SY aoGG have bounded node degree k + 5 and k respectively. In Figure 2, we give a special example to show the theoretical node degree bound for OrdY aoGG and SY ao, where two group wireless nodes, with size 17 each, are uniformly distributed on a unit disk and a half-unit disk respectively. Both disks are centered at one node u with ID = 0. Figure 2 shows the unit disk graph, which is a complete graph, and other structures built on it. Notice that GG and Y aoGG keep all the links to u in the inner cycle, while BP S and OrdY aoGG can remove some links to bound node degree, and SY aoGG has the best node degree bound k = 9. Notice that BP S is constructed based on LDel, and it also added some edges to keep the length spanner property, so it is the densest among them.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.22

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

5.5

23

5 GG YaoGG OrdYaoGG SYaoGG BPS 4.5

Average Node Degree

4

3.5

3

0

50

100

150 Number of Nodes

200

250

300

10

9.5

9 GG YaoGG OrdYaoGG SYaoGG BPS

8.5 Maximum Node Degree

8

7.5

7

6.5

6

5.5

5

0

50

100

150 Number of Nodes

200

250

300

Figure 7. Average and maximum node degree of different topologies.

Beside the node degree of all these structures, we are also interested in another kind of node degree, called physical node degree. For each node u, it has a longest link, say uv, in a constructed structure. Then the physical degree of u is de?ned as all nodes w such that uw ≤ uv . This is the total number of nodes that can cause direct interference with u. The average and maximum physical node degrees of each topology are shown in Figure 8. They are higher than the node degrees in Figure 7 as expected, however they follow the same pattern of curves. Moreover, the possible interference increases slightly while the number of wireless nodes grows. This is tolerable because each node also decreases its transmission range as shown in Figure 6 and the average number of actual physical neighbors of a node is around 6 in our simulations.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.23

24

11

10 GG YaoGG OrdYaoGG SYaoGG BPS

Average Num of Physical Neighbors

9

8

7

6

5

4

0

50

100

150 Number of Nodes

200

250

300

70 GG YaoGG OrdYaoGG SYaoGG BPS

60

Maximum Num of Physical Neighbors

50

40

30

20

10

0

50

100

150 Number of Nodes

200

250

300

Figure 8. Average and maximum physical node degree of different topologies.

Notice that for randomly deployed wireless networks, the simulation results do not show big difference between the proposed structures and the structures GG and YaoGG. The reason behind it is that, for randomly deployed networks, the structures GG and YaoGG will have small node degrees with a high probability. Then, the additional steps in our methods to bound the node degree will do nothing in this case. However, our structures can theoretically bound the worst case performance with only a suf?ciently small communication overhead, e.g., the structure SYaoGG can be constructed with at most 3n messages.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.24

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

9

25

8

7 Average Node Communication Cost

6

OrdYaoGG SYaoGG

5

4

3

2

1

0

50

100

150 Number of Nodes

200

250

300

16

14

Maximum Node Communication Cost

12

10 OrdYaoGG SYaoGG 8

6

4

2

0

50

100

150 Number of Nodes

200

250

300

Figure 9. Communication cost during construction of OrdY aoGG and SY aoGG.

4.3. C OMMUNICATION C OST D URING C ONSTRUCTION In Section 3 we proved that the localized algorithms constructing OrdY aoGG and SY aoGG use at most O(n) messages. We found that when the number of wireless nodes increases the average messages used by each node for constructing them is still in the same level. Figure 9 summarizes our experimental results of the communication costs in each node during the construction of OrdY aoGG and SY aoGG. Here we do not compare our communication costs with that of BP S, since it uses 2-hop neighbors information and needs to build LDel(2) (U DG) which costs much more messages for sure. It is clear that the network becomes more and more dense while the number of wireless nodes increases. However, experiment shows that the localized method does not cost more messages on each node even when the graph becomes denser.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.25

26 An interesting observation is that the average number of messages per node for structures OrdY aoGG is around 8 though the theoretical bound is 24. It is reasonable because nodes do not always query 5 times in local ordering in practice. Notice that SY aoGG costs much less messages than OrdY aoGG does, so it is indeed a very ef?cient topology construction method. This is expected and consistent with our theoretical analysis. Moreover, simulations results in all charts also show that the performances of our new topologies OrdY aoGG and SY aoGG are stable when number of nodes changes.

5. Conclusion We proposed several novel localized algorithms that construct energy ef?cient routing structures, where each node has a bounded degree and the structures are planar, for wireless ad hoc networks modelled by unit disk graph (UDG). Our ?rst structure has a bounded node degree k + 5 where integer k > 6 is an adjustable parameter; its power stretch factor is no more 1 than ρ = 1?(2 sin π )β ; it is planar; and it can be constructed locally in 24n messages, where each message has O(log n) bits for a wireless network of n nodes. Our second method improves the degree bound to k, and keeps all other properties, except that the theoretical power spanning ratio is relaxed to ρ =

√ β √2 1?(2 2 sin

k

second structure can be constructed using at most 3n messages, where each message has O(log n) bits. We conducted extensive simulations to study these new sparse network topologies and compared them with previously known ef?cient structures. Theoretical results are corroborated by the simulations. Notice that the bounded node degree of a structure cannot guarantee that the structure has a small link interference. We would like to study how to construct ef?cient topologies with small interferences while being power ef?cient and having a bounded node degee.

π β ) k

, where k > 8 is an adjustable parameter. We showed that the

References

Bose, P., L. Devroye, W. Evans, and D. Kirkpatrick: 2002a, ‘On the spanning ratio of Gabriel graphs and beta-skeletons’. In: Proceedings of the Latin American Theoretical Infocomatics (LATIN). Bose, P., J. Gudmundsson, and M. Smid: 2002b, ‘Constructing plane spanners of bounded degree and low weight’. In: Proceedings of European Symposium of Algorithms.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.26

Localized Algorithms for Energy Ef?cient Topology in Wireless Ad Hoc Networks

27

Bose, P., P. Morin, I. Stojmenovic, and J. Urrutia: 2001, ‘Routing with guaranteed delivery in ad hoc wireless networks’. ACM/Kluwer Wireless Networks 7(6), 609–616. 3rd int. Workshop on Discrete Algorithms and methods for mobile computing and communications, 1999, 48-55. Burkhart, M., P. V. Rickenbach, R. Wattenhofer, and A. Zollinger: 2004, ‘Does topology control reduce interference’. In: ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc). Cˇ linescu, G.: 2003, ‘Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks’. In: a AD-HOC Networks and Wireless (AdHoc-Now). Dobkin, D., S. Friedman, and K. Supowit: 1990, ‘Delaunay Graphs are Almost as Good as Complete Graphs’. Discr. Comp. Geom. pp. 399–407. Gabriel, K. and R. Sokal: 1969, ‘A new statistical approach to geographic variation analysis’. Systematic Zoology 18, 259–278. Gao, J., L. J. Guibas, J. Hershburger, L. Zhang, and A. Zhu: 2001, ‘Geometric Spanner for Routing in Mobile Networks’. In: Proceedings of the 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). Gr¨ newald, M., T. Lukovszki, C. Schindelhauer, and K. Volbert: 2002, ‘Distributed mainu tenance of resource ef?cient wireless network topologies’. In: Proceedings of the 8th International Euro-Par Conference on Parallel Processing. pp.935-946 Karp, B. and H. Kung: 2000, ‘GPSR: Greedy perimeter stateless routing for wireless networks’. In: Proc. of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). Keil, J. and C. Gutwin: 1989, ‘The Delaunay triangulation closely approximates the complete Euclidean graph’. In: Proc. 1st Workshop Algorithms Data Structure (LNCS 382). Keil, J. M. and C. A. Gutwin: 1992, ‘Classes of graphs which approximate the complete Euclidean graph’. Discr. Comp. Geom. 7, 13–28. Kleinrock, L. and J. Silvester: 1978, ‘Optimum Transmission Radii for Packet Radio Networks or Why Six is a Magic Number’. In: Proceedings of the IEEE National Telecommunications Conference. pp. 431–435. Kuhn, F., R. Wattenhofer, and A. Zollinger: 2002, ‘Asymptotically Optimal Geometric Mobile Ad-Hoc Routing’. In: International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM). Kuhn, F., R. Wattenhofer, and A. Zollinger: 2003, ‘Worst-Case Optimal and Average-Case Ef?cient Geometric Ad-Hoc Routing’. In: ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc). Li, L., J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer: 2001a, ‘Analysis of a ConeBased Distributed Topology Control Algorithms for Wireless Multi-hop Networks’. In: PODC:ACM Symposium on Principle of Distributed Computing. Li, X.-Y., G. Calinescu, and P.-J. Wan: 2002a, ‘Distributed Construction of Planar Spanner and Routing for Ad Hoc Wireless Networks’. In: 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3. Li, X.-Y., P.-J. Wan, and Y. Wang: 2001b, ‘Power Ef?cient and Sparse Spanner for Wireless Ad Hoc Networks’. In: IEEE Int. Conf. on Computer Communications and Networks (ICCCN01). pp. 564–567. Li, X.-Y., P.-J. Wan, Y. Wang, and O. Frieder: 2002b, ‘Sparse Power Ef?cient Topology for Wireless Networks’. In: IEEE Hawaii Int. Conf. on System Sciences (HICSS). Lukovszki, T.: 1999, ‘New Results on Geometric Spanners and Their Applications’. Ph.D. thesis, University of Paderborn. Rajaraman, R.: 2002, ‘Topology Control and Routing in Ad hoc Networks: A Survey’. SIGACT News 33, 60–73.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.27

28

Ramanathan, R. and R. Rosales-Hain: 2000, ‘Topology Control of Multihop Wireless Networks using Transmit Power adjustment’. In: IEEE INFOCOM. Toussaint, G. T.: 1980, ‘The relative neighborhood graph of a ?nite planar set’. Pattern Recognition 12(4), 261–268. Wang, W., X.-Y. Li, K. Moaveninejad, Y. Wang, and W.-Z. Song: 2003, ‘The spanning ratios of beta-skeleton’. In: Canadian Conference on Computational Geometry (CCCG). Wang, Y. and X.-Y. Li: 2003, ‘Ef?cient Construction of Bounded Degree and Planar Spanner for Wireless Networks’. In: ACM DIALM-POMC Joint Workshop on Foundations of Mobile Computing. Wang, Y., X.-Y. Li, and O. Frieder: 2002, ‘Distributed Spanner with Bounded Degree for Wireless Networks’. In: International Journal of Foundations of Computer Science. Wattenhofer, R., L. Li, P. Bahl, and Y.-M. Wang: 2001, ‘Distributed Topology Control for Wireless Multihop Ad-hoc Networks’. In: IEEE INFOCOM’01. Yao, A. C.-C.: 1982, ‘On constructing minimum spanning trees in k-dimensional spaces and related problems’. SIAM J. Computing 11, 721–736.

SYaoGG-MONET-final.tex; 14/07/2004; 17:42; p.28

赞助商链接

- Wireless sensor networks for habitat monitoring
- A new approach to channel access scheduling for Ad Hoc networks
- Geographic routing without location information
- TAG a Tiny AGgregation service for ad-hoc sensor networks
- Spatiotemporal multicast in sensor networks
- Energy-Efficient Topology Control for Wireless Ad Hoc Sensor Networks ￡
- Localized Topology Control for Unicast and Broadcast in Wireless Ad Hoc Networks
- Topology control of ad hoc wireless networks for energy efficiency
- Energy-efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks
- Energy Efficient Cross Layer Design for Broadcast in Ad hoc Wireless Networks
- Energy Efficient Multicasting Using Smart Antennas for Wireless Ad Hoc Networks in
- Energy-Efficient Collision Resolution in Wireless Ad-Hoc Networks
- Localized Algorithms and Their Applications in Ad Hoc Wireless Networks
- Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks
- Survey of Energy Efficient Strategies in Wireless Ad Hoc and Sensor Networks