8.5 Multirate Link-Quality Measurement

To make our MGOR protocol work, we need to estimate the link quality (PRR) at different data rates. We propose a broadcast-based multirate link-quality measurement scheme in this section. This link quality measurement scheme also serves for multirate neighborhood management.

Recall that there are k different data rates. Each node maintains k neighbor tables corresponding to the k data rates. The jth table stores the bidirectional PRR information about its neighbors at rate Rj. For every τ second, each node broadcasts k “Hello” messages with each transmitted at a different data rate, e.g. 11 mbps, 5.5 mbps, and 2 mbps. Whenever a node n receives a “Hello” message sent from a node m at rate Rj, it will include node m into the corresponding neighbor table. Two events drive the updating of PRRmn at Rj on node n: one is the periodical updating event set by node n. For example, every tu seconds node n will update PRRmn. We denote this event as T. The other is the event that node n receives a “Hello” packet sent from m at rate Rj. We denote this event as H.

The exponentially weighted moving average (EWMA) method (Woo and Culler 2003) is used to update PRR information. Since at each rate, the PRR is updated according to the same EWMA mechanism, we only describe the EWMA at a particular rate as follows. Let PRRmn be the current estimation made by node n, lastHello be the time stamp of the last event H, Nm be the number of known missed “Hello” packets between the current event H and last event H based on “Hello” message sequence number difference, and Ng be a guess on the number of missed packets based on “Hello” message broadcast frequency over a time window between the current T event and last H or T event. Nl and Ng are initialized to be 0, and FDRmn is initialized to be 1.

This technique allows node n to measure PRRmn and m to measure PRRnm. Each “Hello” message sent at rate Rj by a node n contains PRR measured by n from each of its neighbors Nn at that rate during the last period of time. Then each neighbor of n, Nn, gets the PRR to n whenever it receives a “Hello” message from n.

The pseudocode of EWMA algorithm for node n to estimate PRRmn at rate Rj is described in Table 8.1, where currentSeq and lastSeq denote the sequence numbers of the current received “Hello” message and the last received “Hello” message, respectively, and 0 < γ < 1 be the tunable parameter.

Table 8.1 Pseudocode of EWMA for a particular data rate

For node n:

When H event happens

Nl = currentSeq − lastSeq − 1

lastSeq = currentSeq

lastHello = current time

l = Max(Nl − Ng, 0)

Ng = 0

PRRmn = PRRmn · γl+1 + (1 − γ)

When T event happens

l = Ng

PRRmn = PRRmn · γl

With kind permission from Springer Science+Business Media: Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply, ACM Wireless Networks (WINET), vol. 15 , no. 1, Jan 2009, pp. 39–51, K. Zeng, K. Ren, W. Lou, and P. J. Moran.