ñòð. 37 |

use the power assignment induced by EMST(V). It was proved in [26] that the longest

edge of the Euclidean minimum spanning tree EMST(V) is always the critical link for

minâ€“max assignment. Here, for an optimum transmission power assignment fopt, call a

link uv the critical link if ||uv|| + c = mc( fopt). Both algorithms presented in [26] and [51]

compute the minimum spanning tree from the fully connected graph with possible very

large communication cost. Notice that the best distributed algorithm [52â€“54] can compute

the minimum spanning tree in O(n) rounds using O(m + n log n) communications for a

general graph with m edges and n nodes. Using the fact that the relative neighborhood

graph, the Gabriel graph, and the Yao graph all have O(n) edges and contain the Euclidean

minimum spanning tree, a simple O(n log n) time-complexity centralized algorithm can

be developed and can be implemented efficiently in a distributed manner.

The minâ€“total assignment problem was studied by Kiroustis et al. [55] and by Clemen-

ti et al. [56â€“58]. Kiroustis et al. [55] first proved that the minâ€“total assignment problem is

NP-hard when the mobile nodes are deployed in a three-dimensional space. A simple two-

approximation algorithm based on the Euclidean minimum spanning tree was also given

in [55]. The algorithm guarantees the same approximation ratio in any dimensions.

188 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

Clementi et al. [56â€“58] proved that the minâ€“total assignment problem is still NP-hard

when nodes are deployed in a two-dimensional space.

So far, we have generated asymmetric communication graphs from the power assign-

ment. For the symmetric communication, several methods also guarantee a good perfor-

mance. It is easy to show that the minimum spanning tree method still gives the optimum

solution for the minâ€“max assignment and a two-approximation for the minâ€“total assign-

ï›µ

ment. Recently, Calinescu et al. [59] gave a method that achieves a better approximation

ratio (5/3) by using ian dea from the minimum Steiner tree. Like the minimum spanning

tree method, it works for any power definition.

6.3 LOCALIZED ROUTINGS

The geometric nature of the multihop ad hoc wireless networks allows a promising idea:

localized routing protocols. A routing protocol is localized if the decision to which node

to forward a packet is based only on:

The information in the header of the packet. This information includes the source

and the destination of the packet, but more data could be included, provided that its

total length is bounded.

The local information gathered by the node from a small neighborhood. This infor-

mation includes the set of one-hop neighbors of the node, but a larger neighborhood

set could be used provided it could be collected efficiently.

Randomization is also used in designing the protocols. A routing is said to be memory-

less if the decision as to which node to forward a packet is solely based on the destination,

current node, and its neighbors within some constant hops. Localized routing is some-

times called in the literature stateless [17], online [60, 61], or distributed [62].

6.3.1 Location Service

In order to make the localized routing work, the source node has to learn the current (or

approximately current) location of the destination node. Notice that for sensor networks

collecting data, the destination node is often fixed; thus, location service is not needed in

these applications. However, the help of a location service is needed in most application

scenarios. Mobile nodes register their locations to the location service. When a source

node does not know the position of the destination node, it queries the location service to

get that information. In cellular networks, there are dedicated position severs. It will be

difficult to implement the centralized approach of location services in wireless ad-hoc

networks. First, for centralized approach, each node has to know the position of the node

that provides the location services, which is a chicken-and-egg problem. Second, the dy-

namic nature of the wireless ad hoc networks makes it very unlikely that there is at least

one location server available for each node. Thus, we will concentrate on distributed loca-

tion services.

For the wireless ad hoc networks, the location service provided can be classified into

four categorizes: some-for-all, some-for-some, all-for-some, and all-for-all. Some-for-all

service means that some wireless nodes provide location services for all wireless nodes.

Other categorizations are defined similarly.

189

6.3 LOCALIZED ROUTINGS

An example of all-for-all services is the location services provided in the Distance

Routing Effect Algorithm for Mobility (DREAM) by Basagni et al. [63]. Each node stores

a database of the position information for all other nodes in the wireless networks. Each

node will regularly flood packets containing its position to all other nodes. A frequency of

the flooding and the range of the flooding is used as a control of the cost of updating and

the accuracy of the database.

Using the idea of quorum developed in the databases and distributed systems, Hass and

Liang [64] and Stojmenovic [65] developed quorum-based location services for wireless

ad hoc networks. Given a set of wireless nodes V, a quorum system is a set of subset (Q1,

Q2, Â· Â· Â· , Qk) of nodes whose union is V. These subsets could be mutually disjoint or often

have equal numbers of intersections. When one of the nodes requires the information of

the other, it suffices to query one node (called the representative node of Qi) from each

quorum Qi. A virtual backbone is often constructed between the representative nodes us-

ing a nonposition-based methods such as those in [7, 6]. The updating information of a

node v is sent to the representative node (or the nearest if there are many) of the quorum

containing v. The difficulty of using quorums is that the mobility of the nodes requires the

frequent updating of the quorums. The quorum-based location service is often of the

some-for-some type.

The other promising location service is based on the quadtree partition of the two-di-

mensional space [66]. It divides the region containing the wireless network into a hier-

archy of squares. The partition of the space in [66] is uniform. However, we notice that

the partition could be nonuniform if the density of the wireless nodes were not uniform

for some applications. Each node v will have the position information of all nodes with-

in the same smallest square containing v. This position information of v is also propa-

gated to up-layer squares by storing it in the node with the nearest identity to v in each

up-layer square containing v. Using the nearest identity over the smallest identity can

avoid the overload of some nodes. The query is conducted accordingly. It is easy to

show that it takes about O(log n) time to update the location of v and to query another

nodeâ€™s position information.

6.3.2 Localized Routing Protocols

We summarize some localized routing protocols proposed in the networking and compu-

tational geometry literature (see Figure 6.6).

The following routing algorithms on the graphs were proposed recently.

Compass Routing. Let t be the destination node. Current node u finds the next relay

node v such that the angle vut is the smallest among all neighbors of u in a given

topology. See [67].

Random Compass Routing. Let u be the current node and t be the destination node.

Let v1 be the node on the above of line ut such that v1ut is the smallest among all

such neighbors of u. Similarly, we define v2 to be nodes below line ut that mini-

mizes the angle v2ut. Then node u randomly chooses v1 or v2 to forward the pack-

et. See [67].

Greedy Routing. Let t be the destination node. Current node u finds the next relay

node v such that the distance ||vt|| is the smallest among all neighbors of u in a given

topology. See [16].

190 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

v v1

v

t t t

u u u

v2

v

v v

t t t

Î± Î±

u u u

Figure 6.6. Various localized routing methods. Shaded area is empty and v is next node.

Most Forwarding Routing (MFR). Current node u finds the next relay node v such

that ||v t|| is the smallest among all neighbors of u in a given topology, where v is

the projection of v on segment ut. See [62].

Nearest Neighbor Routing (NN). Given a parameter angle , node u finds the nearest

node v as forwarding node among all neighbors of u in a given topology such that

vut .

Farthest Neighbor Routing (FN). Given a parameter angle , node u finds the far-

thest node v as forwarding node among all neighbors of u in a given topology such

that vut .

Greedyâ€“Compass. Current node u first finds the neighbors v1 and v2 such that v1

forms the smallest counterclockwise angle tuv1 and v2 forms the smallest clock-

wise angle tuv2 among all neighbors of u with the segment ut. The packet is for-

warded to the node of {v1, v2} with minimum distance to t. See [61, 68]

Notice that it is shown in [16, 67] that compass routing, random compass routing, and

greedy routing guarantee to deliver the packets from the source to the destination if De-

launay triangulation is used as the network topology. They proved this by showing that the

distance from the selected forwarding node v to the destination node t is less than the dis-

tance from current node u to t. However, the same proof cannot be carried over when the

network topology is Yao graph, Gabriel graph, relative neighborhood graph, and localized

Delaunay triangulation. When the underlying network topology is a planar graph, the

right-hand rule is often used to guarantee the packet delivery after simple localized rout-

ing heuristics fail [16, 62, 17].

It was proved in [68] that greedy routing guarantees the delivery of the packets if the

Delaunay triangulation is used as the underlying structure. Compass routing guarantees

the delivery of the packets if the regular triangulation is used as the underlying structure.

There are triangulations (not Delaunay) that defeat these two schemes. Greedyâ€“compass

191

6.3 LOCALIZED ROUTINGS

routing guarantees the delivery of the packets as long as there is a triangulation used as

the underlying structure. Every oblivious routing method is defeated by some convex sub-

divisions.

Localized routing protocols support mobility by eliminating the communication-inten-

sive task of updating the routing tables. But mobility can affect the localized routing pro-

tocols, in both the performance and the guarantee of delivery. There has been no work so

far to design protocols with guaranteed delivery when the network topology changes dur-

ing the routing.

6.3.3 Quality Guaranteed Protocols

With respect to localized routing, there are several ways to measure the quality of the pro-

tocol. Given the scarcity of the power resources in wireless networks, minimizing the total

power used is imperative. A stronger condition is to minimize the total Euclidean distance

traversed by the packet. Morin et al. [61, 68] also studied the performance ratio of previ-

ously studied localized routing methods. They proved that none of the previous proposed

heuristics guarantees a constant ratio of the traveled distance of a packet compared with

the minimum. They gave the first localized routing algorithm such that the traveled dis-

tance of a packet from u to v is at most a constant factor of ||uv|| when the Delaunay trian-

gulation is used as the underlying structure.

Bose and Morin [68] basically use the binary search method to find which path of the

tunnel connecting the source u and the destination v is better. However, their algorithm

(called DTR hereafter) needs the Delaunay triangulation, which is expensive to construct

in wireless ad hoc networks, as the underlying structure. In [69], they further extend their

method to any triangulations satisfying the diamond property. Let G(V, rn) be the graph

defined over V, which has an edge uv iff ||uv|| rn. Li et al. [70] showed that the sum of

all edges in Del(V) is no more than rn with high probability, where rn is the transmission

radius needed by each node so the induced unit disk graph G(V, rn) is connected with high

probability.

2

To make G(V, rn) connect with probability 1 â€“ (1/n), we need n rn 2 ln n, see [71].

They [70] showed that, with probability at least 1 â€“ (1/ ), the longest edge Dn of Delaunay

triangulation is Dn 3(ln n + ln + ln 3)/(n ). Thus, the required transmission range

so that local Delaunay triangulation PLDel equals the Delaunay triangulation Del is just

3/2 of the minimum transmission range to have a connected network with high proba-

bility. This implies that the localized Delaunay triangulation can be used to approximate

the Delaunay triangulation almost always when the network G(V, rn) is connected and

when V is randomly deployed. Consequently, the method by Bose et al. [68] can be used

on local Delaunay triangulation almost always.

Table 6.1 illustrates the delivery rates. For routing methods NN and FN, we choose the

next node within /3 of the destination direction. Interestingly, we found that when the

Yao graph is used, the delivery rates are high in all methods. The reason these methods de-

livered the packets when the Yao structure is used could be that there is a node within the

transmission range in the direction of the destination with high probability when N1(u) is

large enough. Table 6.2 illustrates the maximum spanning ratios of the path traversed by

the packet from source s to destination t to ||st||. Although the maximum spanning ratio by

DTR is larger than most previous methods, DTR is the only known method guaranteeing a

constant spanning ratio.

192 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

Table 6.1. The Delivery Rate

LDel(2)

Yao RNG GG Del PLDel

NN 100 20.4 83.3 100 100 98.4

FN 94.5 25.8 70.2 94.6 100 95.2

MFR 98.6 54.5 90 97.4 95 97.2

Cmp 97.1 23.2 66.2 100 100 100

RCmp 95.4 51.4 66.2 85.7 86.9 89.9

Grdy 100 78.3 100 100 100 100

GCmp 95 26.5 76.6 100 98.4 100

DTR 100 100 100

Table 6.2. The Maximum Spanning Ratio

LDel(2)

Yao RNG GG Del PLDel

NN 1.7 1.3 1.6 1.5 1.6 1.6

FN 3.3 1.6 1.8 1.9 2.3 2.4

MFR 4.7 1.7 2.3 1.8 1.8 3.1

Cmp 11 2.2 6.2 16 18 18

RCmp 27 20 19 31 27 21

Grdy 1.7 2.0 1.8 1.6 1.5 1.6

GCmp 2.5 1.6 2.7 1.9 1.9 1.9

DTR 8.6 8.6 8.4

6.4 STOCHASTIC GEOMETRY

One of the remaining fundamental and critical issues is to have multiple disjoint paths

connecting every pair of nodes without sacrificing the spectrum-reusing property. As

power is a scarce resource in wireless networks, it is important to save the power con-

sumption without losing the network connectivity. The universal minimum power used by

all wireless nodes such that the induced network topology is connected is called the criti-

cal power. Although determining the critical power for static wireless ad hoc networks has

been well studied [26, 51, 72], it remains to study the critical power for connectivity for

mobile wireless networks. As the wireless nodes move around, it is impossible to have a

unanimous critical power to guarantee the connectivity for all instances of the network

configuration. Thus, we need to find a critical power, if possible, at which each node has

to transmit to guarantee the connectivity of the network almost surely, i.e., with high prob-

ability of almost one.

ñòð. 37 |