Xem mẫu
Handbook of Wireless Networks and Mobile Computing, Edited by Ivan Stojmenovic´ Copyright © 2002 John Wiley & Sons, Inc.
ISBNs: 0-471-41902-8 (Paper); 0-471-22456-1 (Electronic)
CHAPTER 10
Leader Election Protocols for Radio Networks
KOJI NAKANO
Japan Advanced Institute for Science and Technology
STEPHAN OLARIU
Department of Computer Science, Old Dominion University, Norfolk
10.1 INTRODUCTION
A radio network (RN, for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. In a single-channel RN, the stations communicate over a unique radio frequency channel known to all the stations. A RN is said to be single-hop when all the stations are within transmission range of each other. In this chapter, we focus on single-channel, single-hop radio networks. Single-hop radio networks are the basic ingredients from which larger, multi-hop radio networks are built [3, 22].
As customary, time is assumed to be slotted and all transmissions are edge-triggered, that is, they take place at time slot boundaries [3, 5]. In a time slot, a station can transmit and/or listen to the channel. We assume that the stations have a local clock that keeps syn-chronous time, perhaps by interfacing with a global positioning system (GPS, for short) [6, 8, 18, 20]. It is worth noting that, under current technology, the commercially available GPS systems provide location information accurate to within 22 meters as well as time in-formation accurate to within 100 nanoseconds [6]. It is well documented that GPS sys-tems using military codes achieve a level of accuracy that is orders of magnitude better than their commercial counterparts [6, 8]. In particular, this allows the stations to detect time slot boundaries and, thus, to synchronize.
Radio transmission is isotropic, that is, when a station is transmitting, all the stations in its communication range receive the packet. We note here that this is in sharp contrast with the basic point-to-point assumption in wireline networks in which a station can spec-ify a unique destination station. We employ the commonly accepted assumption that when two or more stations are transmitting on a channel in the same time slot, the corresponding packets collide and are garbled beyond recognition. It is customary to distinguish among radio networks in terms of their collision detection capabilities. In the RN with collision detection, the status of a radio channel in a time slot is:
NULL if no station transmitted in the current time slot
SINGLE if exactly one station transmitted in the current time slot
219
220 LEADER ELECTION PROTOCOLS FOR RADIO NETWORKS
COLLISION if two or more stations transmitted the channel in the current time slot
The problem that we survey in this chapter is the classical leader election problem, which asks the network to designate one of its stations as leader. In other words, after exe-cuting the leader election protocol, exactly one station learns that it was elected leader, whereas the remaining stations learn the identity of the leader. Historically, the leader election problem has been addressed in wireline networks [1, 2, 9, 10, 21], in which each station can specify a destination station.
The leader election problem can be studied in the following three scenarios:
Scenario 1: The number n of stations is known in advance
Scenario 2: The number n of stations is unknown, but an upper bound u on n is known in advance
Scenario 3: Neither the number of stations nor an upper bound on this number is known in advance
It is intuitively clear that the task of leader election is the easiest in Scenario 1 and hardest in Scenario 3, with Scenario 2 being in between the two.
Randomized leader election protocols designed for single-channel, single-hop radio networks work as follows. In each time slot, the stations transmit on the channel with some probability. As we will discuss shortly, this probability may or may not be the same for individual stations. If the status of the channel is SINGLE, the unique station that has transmitted is declared the leader. If the status is not SINGLE, the above is repeated until, eventually, a leader is elected. Suppose that a leader election protocol runs for t time slots and a leader has still not been elected at that time. The history of a station up to time slot t is captured by
The status of the channel—The status of the channel in each of the t time slots, that is, a sequence of {NULL,COLLISION} of length t.
Transmit/not-transmit—The transmission activity of the station in each of the t time slots, that is, a sequence of {transmit,not-transmit} of length t.
It should be clear that its history contains all the information that a station can obtain in t time slots. From the perspective of how much of the history information is used, we iden-tify three types of leader election protocols for single-channel, single-hop radio networks:
1. Oblivious. In time slot i, (1 # i), every station transmits with probability pi. The probability pi is fixed beforehand and does not depend on the history.
2. Uniform. In time slot i (1 # i), all the stations transmit with the same probability pi. Here pi is a function of the history of the status of channel in time slots 1, 2, . . . , i – 1.
3. Non-uniform:In each time slot, every station determines its transmission probabili-ty, depending on its own history.
An oblivious leader election protocol is uniquely determined by a sequence P = kp1,
10.1 INTRODUCTION 221
p2, . . .l of probabilities. In time slot i (1 # i), every station transmits with probability pi. A leader is elected if the status of the channel is SINGLE. Clearly, oblivious leader election protocols also work for radio networks with no collision detection, in which the stations cannot distinguish between NULL and COLLISION.
A uniform leader election protocol is uniquely determined by a binary tree T of proba-bilities. T has nodes pi, j (1 # i; 1 # j # 2i–1), each corresponding to a probability. Node pi, j has left child pi+1,2j–1 and right child pj+1,2j. The leader election protocol traverses T from the root as follows. Initially, the protocol is positioned at the root p1,1. If in time slot i the protocol is positioned at node pi, j, then every station transmits on the channel with probability pi, j. If the status of the channel is SINGLE, the unique station that has trans-mitted becomes the leader and the protocol terminates. If the status of channel is NULL, the protocol moves to the left child pi+1,2j–1; if the status is COLLISION, the protocol moves to the right child pi+1,2j.
Similarly, a nonuniform leader election protocol is captured by a ternary tree T with nodes pi, j (1 # i; 1 # j # 3i–1), each corresponding to a probability. The children of node pi, j are, in left to right order, pi+1,3j–2, pi+1,3j–1, and pi+1,3j. Each station traverses T from the root as follows. Initially, all the stations are positioned at the root p1,1. If in time slot i a station is positioned at node pi, j then it transmits with probability pi, j. If the status of the channel is SINGLE, the unique station that has transmitted becomes the leader and the protocol terminates. If the status of the channel is NULL, the station moves to pi+1,3j–2. If the status of channel is COLLISION, then the station moves to pi+1,3j–1 or pi+1,3j depending on whether or not is has transmitted in time slot i. Figure 10.1 illustrates the three types of leader election protocols.
Several randomized protocols for single-channel, single-hop networks have been pre-sented in the literature. Metcalfe and Boggs [12] presented an oblivious leader election protocol for Scenario 1 that is guaranteed to terminate in O(1) expected time slots. Their protocol is very simple: every station keeps transmitting on the channel with probability 1/n. When the status of channel becomes SINGLE, the unique station that has transmitted is declared the leader. Recently, Nakano and Olariu [14] presented two nonuniform leader election protocols for Scenario 3. The first one terminates, with probability 1 – 1/n in O(log n) time slots. (In this chapter, log and ln are used to denote the logarithms to the base 2 and e, respectively.) The second one terminates with probability 1 – 1/log n in O(log log n) time slots. The main drawback of these protocols is that the “high probabili-
Figure 10.1 Oblivious, uniform, and nonuniform protocols.
222 LEADER ELECTION PROTOCOLS FOR RADIO NETWORKS
TABLE 10.1 A summary of known leader election protocols
Protocol
Oblivious Oblivious Oblivious Oblivious Oblivious Uniform Nonuniform
Scenario
1 2 3 3 3 3 3
Time slots with probability 1 – 1/f
e ln f log u log f
O[(log n)2 + (log f)2] O(fe log n)
O{min[(log n)2 + (log f)2, felog n]} log log n + o(log log n) + O(log f)
log log n + 2.78 log f + o(log log n + log f)
Time slots, average
e O(log u)
O[(log n)2] O(log n) O(log n)
log log n + o(log log n) log log n + o(log log n)
ty” expressed by either 1 – 1/n or 1 – 1/log n becomes meaningless for small values of n. For example, the O(log log n) time protocol may take a very large number of time slots to terminate. True, this only happens with probability at most 1/log n. However, when n is small, this probability is nonnegligible. To address this shortcoming, Nakano and Olariu [15] improved this protocol to terminate, with probability exceeding 1 – 1/f in log log n + 2.78 log f + o(log log n + log f) time slots. Nakano and Olariu [16] also presented an oblivious leader election protocol for Scenario 3 terminating with probability at least 1 – 1/f in O{min[(log n)2 + (log f)2, f3/5 log n]} time slots.
In a landmark paper, Willard [22] presented a uniform leader election protocol for the conditions of Scenario 2 terminating in log log u + O(1) expected time slots. Willard’s pro-tocol involves two stages: the first stage, using binary search, guesses in log log u time slots a number i (0 # i # log u), satisfying 2i # n < 2i+1. Once this approximation for n is available, the second stage elects a leader in O(1) expected time slots using the protocol of [12]. Thus, the protocol elects a leader in log log u + O(1) expected time slots. Willard \citeWIL86 went on to improve this protocol to run under the conditions of Scenario 3 in log log n + o(log log n) expected time slots. The first stage of the improved protocol uses the technique presented in Bentley and Yao [4], which finds an integer i satisfying 2i # n < 2i+1, bypassing the need for a known upper bound u on n. More recently, Nakano and Olariu with probability exceeding 1 – 1/f, in log log n + o(log log n) + O(log f) time slots. Our uniform leader election features the same performance as the nonuniform leader elec-tion protocol of [15] even though all the stations transmit with the same probability in each time slot.
In this chapter, we survey known leader election protocols. See Table 10.1 for the char-acteristics of these protocols.
10.2 A BRIEF REFRESHER OF PROBABILITY THEORY
The main goal of this section is to review elementary probability theory results that are useful for analyzing the performance of our protocols. For a more detailed discussion of background material we refer the reader to [13].
For a random variable X, E[X] denotes the expected value of X. Let X be a random variable denoting the number of successes in n independent Bernoulli trials with para-
10.2 A BRIEF REFRESHER OF PROBABILITY THEORY 223
meter p. It is well known that X has a binomial distribution and that for every integer r (0 # r # n)
Pr[X = r] = 1n2pr(1 – p)n–r
Further, the expected value of X is given by
n
E[X] = ^r · Pr[X = r] = np
r=0
To analyze the tail of the binomial distribution, we shall make use of the following esti-mates, commonly referred to as Chernoff bounds [13]:
Pr[X > (1 + d)E[X]] < 1(1 + d)(1+d) 2E[X] Pr[X > (1 + e)E[X]] < e–(e2/3)E[X]
Pr[X < (1 – e)E[X]] < e–(e2/3)E[X]
(0 # d) (10.1)
(0 # e # 1) (10.2)
(0 # e # 1) (10.3)
Let X be a random variable assuming only nonnegative values. The following inequali-ty, known as the Markov inequality, will also be used:
Pr[X $ c ·E[X]] # 1 for all c $ 1 (10.4)
To evaluate the expected value of a random variable, we state the following lemma.
Lemma 2.1 Let X be a random variable taking a value smaller than or equal to T(F) with probability at least F (0 # F # 1), where T is a nondecreasing function. Then, E[X] # e0 T(F)dF.
Proof: Let k be any positive integer. Clearly, X is no more than T(i/k) with probability i/k for every i (1 # i # k). Thus, the expected value of X is bounded by
E[X] # k 1i – i – 1 2T1i 2= k 1 T1}2. i=1 i=1
As k R ` we have E[X] # e1 T(F)dF. n
For later reference, we state the following corollary.
Corollary 2.2 Let X be a random variable taking a value no more than ln f with proba-bility at least 1 – 1/f. Then, E[X] # 1.
...
- tailieumienphi.vn
nguon tai.lieu . vn