WIRELESS SENSOR NETWORKS

- AS PER BPUT SYLLABUS FOR B.TECH.(CS STREAM) 6TH SEMESTER

“The distance between dreams and reality is called action.”
— Brian Tracy

MODULE-II

Dr. Abhaya Kumar Samal

Dean(School of Computing), Dean(Project & Consultancy)
Professor in Comp. Sc. Engg.
AGENDA
Module-II (10 hours):
Part II: Basic Architectural Framework
• Chapter 5: Physical Layer
• Basic Components (5.1), Source and Channel Encoding (5.2,5.3), Modulation (5.4), Signal Propagation (5.5)
• Chapter 6: Medium Access Control
• Wireless MAC Protocols (6.2), Characteristics of MAC Protocols in Sensor Networks (6.3), Contention-Free
MAC Protocols (6.4), Contention-Based MAC Protocols (6.5), Hybrid MAC Protocols (6.6)
• Chapter 7: Network Layer
• Routing Metrics (7.2), Flooding and Gossiping (7.3), Data-Centric Routing (7.4),
Proactive Routing (7.5), On-Demand Routing (7.6), Hierarchical Routing (7.7),
Location-Based Routing (7.8), QoS-Based Routing Protocols (7.9)

Text Book:
1. Fundamentals of Wireless Sensor Network: Theory and Practice,
Waltenegus Dargie and Christian Poellabauer, Wiley Publication, 2010
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 5: PHYSICAL LAYER
• One of the desirable aspects of WSNs is their ability to communicate
over a wireless link, so that
• Mobile applications can be supported, and
• The nodes can be placed in areas that are inaccessible to wired nodes
• Some formidable challenges are:
• Limited bandwidth and transmission range, and
• Poor packet delivery performance because of interference, attenuation, and
multi-path scattering
• Therefore, it is vital to understand their properties and some of the
mitigation strategies
• This chapter provides a fundamental introduction to point-to-point
wireless digital communication
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – PRELUDE TO DIGITAL COMMUNICATION - ANALOG TO DIGITAL
• Communication involves signals – such as sound signals, generally, are analog
in nature and needs a medium (aka transmission media)
• For communication over a distance, the analog signals are sent through wire,
using different techniques for effective transmission
• Conventional methods used analog signals for long distance communications
• suffer from losses (distortion, interference, and other losses including security breach)
• To overcome this, signals are digitized using different techniques
• Makes the communication to be more clear and accurate without losses

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – ELEMENTS OF DIGITAL COMMUNICATION
• Block diagram below presents elements of a digital communication system:

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – BASIC COMPONENTS

Figure 5.1: Components of a digital communication system

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – BASIC COMPONENTS
• The communication source represents one or more sensors and produces
a message signal - an analog signal
• the signal is a baseband signal having dominant frequency components near zero
• the message signal has to be converted to a discrete signal (discrete both in time
and amplitude)
• The conversion requires sampling the signal at least at Nyquist rate - no information
will be lost
• Source encoding: the discrete signal is converted to a binary stream after
sampling
• Channel encoding: make the transmitted signal robust to noise and
interference

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – BASIC COMPONENTS
• Modulation - the baseband signal is transformed into a bandpass signal
• main reason is to transmit and receive signals with short antennas
• Power Amplifier - the modulated signal has to be amplified and the
electrical energy is converted into electromagnetic energy by the
transmitter’s antenna
• The signal is propagated over a wireless link to the desired destination
• The receiver block out the carries by carrying the reverse process to
retrieve the message signal from the electromagnetic waves

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PHYSICAL LAYER – BASIC COMPONENTS
• The magnitude and shape of the signal are changed because of noise,
losses and interferences
• The signal has to pass through a series of amplification and filtering
processes
• It is then transformed back to a baseband signal through the process of
demodulation and detection
• Finally, the baseband signal undergoes a pulse-shaping process and two
stages of decoding (channel and source)
• extract the sequence of symbols - the original analog signal (the message)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO SOURCE ENCODING – SOME KEY DEFINITIONS AND BACKGROUND
• What moves in the digital communication system?
• What is information?
• Messages and their contents
• Mathematical interpretation of information
• Consider few sample messages:
1. India got its independence in the year 1947
2. Everyday morning, the sun rises from the east
3. The dog will bark in next five minutes
4. Tomorrow here it will rain sporadically
5. It will snow in Delhi this Winter
6. Next Sunday may not be holiday

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO SOURCE ENCODING – SOME KEY DEFINITIONS AND BACKGROUND
• Probability and Information content
• Institutive Feel
• Analysis of the Message
MN Message of Event (xi) Size Nature or Characteristics P(xi) I(xi)
1 India got its independence in the year 1947 43 Historical event, already happened 1 0
2 Everyday morning, the sun rises from the east 45 Natural Truth, happens daily 1 0
3 The dog will bark in next five minutes 38 May or may not bark, a probable event 0.5 0.5
4 Tomorrow here it will rain sporadically 39 May or may not rain, a probable event 0.5 0.5
5 It will snow in Delhi this Winter 33 Little chance, never happened earlier, surprises 0.001 0.99
6 Next Sunday may not be holiday 30 Never happened earlier, surprises 0.001 0.99
• So
1 1 1
𝐼(𝑥𝑖 ) ∝ , or 𝐼 𝑥𝑖 = 𝑓 , or 𝐼 𝑥𝑖 = log , or 𝐼 𝑥𝑖 = −log 𝑃(𝑥𝑖 )
𝑃(𝑥𝑖 ) 𝑃(𝑥𝑖 ) 𝑃(𝑥𝑖 )
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO SOURCE ENCODING – SOME KEY DEFINITIONS AND BACKGROUND
• Consider tosses of a fair coin as a binary source which produces trains of 0’s
and 1’s
• 1 if H and 0 if T
• For this source, if X is the set of events (two possible outcomes, H or T),
• X = {x1,x2}, x1=1 or H, x2=0 or T, then P(1) = P(0) = 0.5 (fair coin)
• I(xi) = – log(P(xi)) = – log(0.5) = 1 bit
• So, any message with Head (1) or Tail (0), the information content of the
message can be expressed in 1 bit, but what about a biased coin?
• Now let’s extend to N tosses, memory-less events (successive tosses)
• I(xi) = – log2(P(xi)) = – log2(2-m) = – (–m) log2(2) = m bits

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
 3-bit resolution quantizes into eight levels (2323)
3-bit resolution quantizes into eight levels (2323)
3-bit resolution quantizes into eight levels (2323)

SOURCE ENCODING
• A source encoder transforms an analog signal into a
digital sequence
• The process consists of: sampling, quantizing, encoding
• Suppose a sensor produces an analog signal s(t)
2-bit resolution quantizes into
• s(t) will be sampled and quantized by the analog-to-digital four levels (22)

converter (ADC) that has a resolution of Q distinct values

• As a result, a sequence of samples, S = (s[1], s[2], ..., s[n]) are
produced
• The difference between the sampled s[j] and its
corresponding analog value at time tj is the quantization error
• As the signal varies over time, the quantization error also
varies and can be modeled as a random variable with a
probability density function, Ps(t)
3-bit resolution quantizes into
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar eight levels (23)
SOURCE ENCODING
• The aim of the source encoder is to map each quantized element, s[j] into
a corresponding binary symbol of length r from a codebook, C
• Block code: if all the binary symbols in the codebook are of equal length
• Often, the symbol length and the sampling rate are not uniform
• It is customary to assign:
• short-sized symbols and high sampling rates to the most probable sample values
• long-sized symbols and low sampling rates to less probable sample values

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
 SOURCE ENCODING
• A codebook can be instantaneously decoded
• if each symbol sequence can be extracted (decoded) from a stream of symbols
without taking into consideration previously decoded symbols
• This will be possible
• iff there does not exist a symbol in the codebook, such that the symbol a = (a1, a2,
..., am) is not a prefix of the symbol b = (b1, b2, ..., bn ), where m < n and ai = bi , ∀i =
1, 2, ..., m within the same codebook

Figure 5.2 illustrates the input – output

relationship of a source encoder

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
 SOURCE ENCODING

Set of Source Words: S = (s[1], s[2], …, s[m]) Codebook C = (C(1), C(2), …, C(n))

For a codebook C to be uniquely decoded, each sequence of symbols, (C(1), C(2), ...)
must be mapped back to a corresponding value in S = (s[1], s[2], ..., s[n]).
The binary codebook C has to satisfy the Equation (5.1) for it to be unique decodable:
Example: 6 Codebooks
(C 1, C 2, C 3, C 4, C 5 and C 6)
(for 𝐶11 + 𝐶21 + 𝐶31 + 𝐶41 )

= (½)1 + (½)2 + (½)2 + (½)2

= 0.5 + 0.25 + 0.25 + 0.25
= 1.25 or 1¼

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING

Table 5.1 Source-encoding techniques

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – THE EFFICIENCY OF A SOURCE ENCODE
• Quantity that expresses the average length
• Sampled analog signal: L(C) = E[li(C)]
• Suppose the probability of a q-ary source
• i.e., it has q distinct symbols
• Probability of producing the symbol si is Pi and the symbol Ci in a codebook is used
to encode si
• The expected length of the codebook is given by:

Equation (5.2)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – THE EFFICIENCY OF A SOURCE ENCODE
• To express efficiency in terms of the information entropy or Shannon’s
entropy
• Defined as the minimum message length necessary to communicate information
• Related to the uncertainty associated with the information
• If the symbol si can be expressed by a binary symbol of n bits, the information
content of si is:

Equation (5.3)

• The entropy (in bits) of a q-ary memoryless source encoder is expressed as:

Equation (5.4)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – THE EFFICIENCY OF A SOURCE ENCODE
• The efficiency of a source encoder in terms of entropy reveals the unnecessary
redundancy in the encoding process. This can be expressed by:

Equation (5.5)

• The redundancy of the encoder is:

Equation (5.6)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – EXAMPLE: THE EFFICIENCY OF A SOURCE ENCODE

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – EXAMPLE: THE EFFICIENCY OF A SOURCE ENCODE
• In Figure 5.3, it is quantized into four distinct values, 0, 1, 2, 3
• Some values (2) occur more frequently than others (0 and 3)
• If the probability of occurrence of these values is
• P(0) = 0.05, P(1) = 0.2, P(2) = 0.7, P(3) = 0.05, then,
• It is possible to compute the efficiency of two of the codebooks given in Table 5.1, namely C2 and
C3
• For P1 = 0.05, log2(1/0.005 ) = 4.3. Because li has to be a whole number and there
should be no loss of information, l1 must be 5. Likewise, l2 = 3; l3 = 1; and l4 = 5.
Hence:

Equation (5.7)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – EXAMPLE: THE EFFICIENCY OF A SOURCE ENCODE
• Using Equation (5.4), the entropy of C2 is calculated as:

Equation (5.8)

• Therefore, the encoding efficiency of the codebook, C2 is:

Equation (5.9)

• The redundancy in C2 is:

Equation (5.10)
• In terms of energy efficiency, this implies that 30% of the transmitted bits are
unnecessarily redundant, because C2 is not compact enough
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – A TAXONOMY OF MODULATION TECHNIQUES

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – PULSE AMPLITUDE MODULATION (PAM)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – PULSE WIDTH MODULATION (PWM)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – PULSE POSITION MODULATION (PPM)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – DELTA MODULATION (DM)

Delta Modulation Transmitter

Delta Modulation Waveform Representation

Delta Modulation Receiver
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
A PRELUDE TO MODULATION – PULSE CODE MODULATION (PCM)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – PULSE CODE MODULATION AND DELTA MODULATION
• PCM and DM are the two predominantly employed source encoding
techniques
• In digital pulse code modulation
• the signal is quantized first
• each sample is represented by a binary word from a finite set of words
• The resolution of a PCM technique and the source encoder bit rate are
determined by
• the size of the individual words
• the number of words in the set

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – PULSE CODE MODULATION AND DELTA MODULATION
• In PCM, information is conveyed in the presence or absence of pulses
• greatly enhances the transmission and regeneration of binary words
• the associated cost with this form of source encoding is
• the quantization error, the energy and bandwidth required to transmit the multiple bits for each
sampled output
• Figure 5.4 illustrates a PCM technique that uses two bits to encode a single sample
• four distinct levels are permissible during sampling

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – PULSE CODE MODULATION AND DELTA MODULATION

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – PULSE CODE MODULATION AND DELTA MODULATION
• Delta modulation is a digital pulse modulation technique
• it has found widespread acceptance in low bit rate digital systems
• it is a differential encoder and transmits bits of information
• the information describes the difference between successive signal values, as
opposed to the actual values of a time-series sequence
• the difference signal, Vd(t), is produced by first estimating the signal’s magnitude
based on previous samples (Vi (t0)) and comparing this value with the actual input
signal, Vin(t0)
• The polarity of the difference value indicates the polarity of the pulse
transmitted

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SOURCE ENCODING – PULSE CODE MODULATION AND DELTA MODULATION
• The difference signal is a measure of the slope of the signal
• first, sampling the analog signal
• then, varying the amplitude, width, or the position of the digital signal in
accordance with the amplitude of the sampled signal
• Figure 5.5 illustrates delta modulation

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING
• The main purpose is
• to produce a sequence of data that is robust to noise
• to provide error detection
• to forward error correction mechanisms
• Figure 5.6 illustrates these restrictions

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING
• According to the Shannon – Hartley theorem, the capacity of a channel to
transmit a message without an error is given as:
Equation (5.14)

• where C is the channel capacity in bits per second

• B is the bandwidth of the channel in hertz
• S is the average signal power over the entire bandwidth, measured in watts
• N is the average noise power over the entire bandwidth, measured in watts
• Equation (5.14) above states that for data to be transmitted free of errors,
its transmission rate should be below the channel’s capacity
• It also indicates how the signal-to-noise ratio (SNR) can improve the
channel’s capacity
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING
• The equation reveals two independent reasons why errors can be
introduced during transmission:
1. information will be lost if the message is transmitted at a rate higher than the
channel’s capacity - equivocation (subtractive error)
2. information will be lost because of noise, which adds irrelevant information into
the signal

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
 CHANNEL ENCODING – TYPES OF CHANNELS
• Binary Symmetric Channel
• a channel model
• bits of information (0 and 1) can be transmitted through it
• the channel transmits a bit of information
• correctly (regardless of whether information is 0 or 1) with a probability p
• incorrectly (by flipping 1 to 0 and 0 to 1) with a probability 1 – p:
Equation (5.20)

Equation (5.21)
• the channel matrix of a binary symmetric channel:

Equation (5.22)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING – TYPES OF CHANNELS
• Binary Symmetric Channel

Figure 5.7 A binary symmetric channel model

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING – TYPES OF CHANNELS
• Binary Erasure Channel
• in a BEC, there is no guarantee that the transmitted bit of information can be
received at all (correctly or otherwise)
• a binary input - a ternary output channel
• the probability of erasure is p and the probability that the information is correctly
received is 1 – p
• the probability of error is zero:
Equation (5.23)
• a bit of information
• Either transmitted successfully with P(1|1) = P(0|0) = 1 – p
• or erased altogether by the channel with a probability of p
• the probability that 0 is received by transmitting 1 or vice versa is 0

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHANNEL ENCODING – TYPES OF CHANNELS
• Binary Erasure Channel

Figure 5.8 A stochastic model of a binary erasure channel

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SIGNAL PROPAGATION – CHANNEL MODEL
• Wireless sensor networks
• Must share the spectrum with and
accept interference from devices that
operate in the same spectrum
• such as cordless phones, WLAN, Bluetooth,
Microwave oven
• A simple channel model (Figure 5.28)
• Ignores the effect of interference
• Considers the surrounding noise as the
predominant factor that affects the
transmitted signal
• The noise can be modeled as an
Additive White Gaussian Noise (AWGN)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SIGNAL PROPAGATION – RELATIONSHIP BETWEEN TX AND RX ANTENNA
• The received power can be improved by adjusting a number of parameters
• Figure 5.18 shows the relationship between transmitted and received power
• suppose the power amplifier outputs a constant transmission power, Pt, to transmit the signal
over a distance of ρ
• the relationship between the transmitter’s antenna gain, gt , and the antenna’s effective area, At ,
is expressed as:
Equation (5.44)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SIGNAL PROPAGATION – RELATIONSHIP BETWEEN TX AND RX POWER
• The relationship between the received power and the transmitted power
for a LOS link is expressed as:
Equation (5.45)
• where ρ is the distance that separates the transmitter and the receiver. Since the
receiver’s antenna gain, gr , and the effective area, Ar , are related, Equation (5.45)
can be reformulated:
Equation (5.46)
• the ratio of the transmitted power to the received power, Pt / Pr is the propagation
loss and it is customary to quantify this ratio in decibels (dBs)
Equation (5.47)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SIGNAL PROPAGATION – TYPES OF MODULATION
• Hence, the propagation loss expressed in dBs is:
Equation (5.48)

• the term 20log(4πρ/λ) is called the basic transmission loss and is independent of the
transmitter and receiver antennas

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 6: MEDIUM ACCESS CONTROL LAYER – PRELUDE DISCUSSION

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO MEDIUM ACCESS CONTROL LAYER

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO WIRELESS MEDIUM ACCESS CONTROL LAYER

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PRELUDE TO WIRELESS MEDIUM ACCESS CONTROL LAYER

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 6: MEDIUM ACCESS CONTROL LAYER
• In most networks, multiple nodes share a communication medium for
transmitting their data packets
• The medium access control (MAC) protocol is primarily responsible for
regulating access to the shared medium
• The choice of MAC protocol has a direct bearing on the reliability and
efficiency of network transmissions
• due to errors and interferences in wireless communications and to other
challenges
• Energy efficiency also affects the design of the MAC protocol
• trade energy efficiency for increased latency or a reduction in throughput or
fairness

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – OVERVIEW
• Responsibilities of MAC layer include:
• decide when a node accesses a shared medium
• resolve any potential conflicts between
competing nodes
• correct communication errors occurring at the
physical layer
• perform other activities such as framing,
addressing, and flow control
• Second layer of the OSI reference model
(data link layer) or the IEEE 802 reference
model (which divides data link layer into
logical link control and medium access
control layer)
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – PROTOCOL CATEGORIZATION

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – CONTENTION-FREE MEDIUM ACCESS
• Collisions can be avoided by ensuring that each node can use its allocated
resources exclusively
• Examples of fixed assignment strategies:
• FDMA: Frequency Division Multiple Access
➢ the frequency band is divided into several smaller frequency bands
➢ the data transfer between a pair of nodes uses one frequency band
➢ all other nodes use a different frequency band
• TDMA: Time Division Multiple Access
➢ multiple devices to use the same frequency band
➢ relies on periodic time windows (frames)
▪ frames consist of a fixed number of transmission slots to separate the medium accesses of different
devices
▪ a time schedule indicates which node may transmit data during a certain slot

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – CONTENTION-FREE MEDIUM ACCESS
• Examples of fixed assignment strategies (contd.):
• CDMA: Code Division Multiple Access
➢ simultaneous accesses of the wireless medium are supported using different codes
➢ if these codes are orthogonal, it is possible for multiple communications to share the same
frequency band
➢ forward error correction (FEC) at the receiver is used to recover from interferences among these
simultaneous communications
• Fixed assignment strategies are inefficient
• it is impossible to reallocate slots belonging to one device to other devices if not
needed in every frame
➢ generating schedules for an entire network can be a taunting task
➢ these schedules may require modifications every time the network topology or traffic
characteristics in the network change

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – CONTENTION-FREE MEDIUM ACCESS
• Dynamic assignment strategies: allow nodes to access the medium on
demand
• polling-based protocols
• a controller device issues small polling frames in a round-robin fashion, asking each station if it has
data to send
• if no data to be sent, the controller polls the next station
• token passing
• stations pass a polling request to each other (round-robin fashion) using a special frame called a
token
• a station is allowed to transmit data only when it holds the token
• reservation-based protocols
• static time slots used to reserve future access to the medium
• e.g., a node can indicate its desire to transmit data by toggling a reservation bit in a fixed location
• these often very complex protocols then ensure that other potentially conflicting nodes take note of
such a reservation to avoid collisions
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – CONTENTION-BASED MEDIUM ACCESS
• Nodes may initiate transmissions at the same time
• requires mechanisms to reduce the number of collisions and to recover from
collisions
• Example 1: ALOHA protocol
• uses acknowledgments to confirm the success of a broadcast data transmission
➢ allows nodes to access the medium immediately
➢ addresses collisions with approaches such as exponential back-off to increase the likelihood of
successful transmissions
• Example 2: slotted-ALOHA protocol
• requires that a station may commence transmission only at predefined points in
time (the beginning of a time slot)
• increases the efficiency of ALOHA
• introduces the need for synchronization among nodes
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MEDIUM ACCESS CONTROL LAYER – CONTENTION-BASED MEDIUM ACCESS
• Carrier Sense Multiple Access (CSMA)
• CSMA with Collision Detection (CSMA/CD)
➢ sender first senses the medium to determine whether it is idle or busy
• if it is found busy, the sender refrains from transmitting packets
• if the medium is idle, the sender can initiate data transmission
• CSMA with Collision Avoidance (CSMA/CA)
➢ CSMA/CD requires that sender aware of collisions
➢ instead, CSMA/CA attempts to avoid collisions in the first place

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CONTENTION-BASED MEDIUM ACCESS – HIDDEN AND EXPOSED TERMINAL PROBLEMS

• Hidden-terminal problem
• senders A and C are able to reach B, but cannot overhear each other’s signals
• it is possible for A and C to transmit data to B at the same time, causing a collision at
B, without being able to directly detect this collision
• Exposed-terminal problem
• C wants to transmit data D, but decides to wait because it overhears an ongoing
transmission from B to A
• B’s transmission could not interfere with data reception at C

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – CARRIER SENSE MULTIPLE ACCESS
• Nodes first sense the medium before they begin a transmission (reduces
number of collisions)
• Non-persistent CSMA
• node is allowed to immediately transmit data once medium is idle
• if the medium is busy, the node performs a back-off operation
• wait for a certain amount of time before attempting to transmit again
• 1-persistent CSMA
• node wishing to transmit data continuously senses the medium for activity
• once the medium is found idle, the node transmits data immediately
• if a collision occurs, the node waits for a random period of time before attempting
to transmit again

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – CARRIER SENSE MULTIPLE ACCESS
• p-persistent CSMA
• node continuously senses the medium
• node transmits data with a probability p once the medium becomes idle
• delays transmission with a probability 1 − p
• random back-off values are either continuous values in the case of un-slotted CSMA
or multiples of a fixed slot size in slotted CSMA
• CSMA/CA (CSMA with Collision Avoidance)
• nodes sense the medium, but do not immediately access the channel when it is
found idle
• instead, a node waits for a time period called DCF interframe space (DIFS) plus a
multiple of a slot size
• in case there are multiple nodes attempting to access the medium, the one with the
shorter back-off period will win
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – CARRIER SENSE MULTIPLE ACCESS
• Example:
• node A waits for DIFS + 4 ∗ s (where s represents the slot size), while node B’s back-
off is DIFS + 7 ∗ s
• once node A begins with its transmission, node B freezes its own back-off timer and
resumes the timer after node A completes its transmission plus another period of
DIFS
• once node B’s back-off timer expires, it can also begin its transmission

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – MACA AND MACAW
• Multiple Access with Collision Avoidance (MACA)
• dynamic reservation mechanism
• sender indicates desire to send with ready-to-send (RTS) packet
• intended receiver responds with clear-to-send (CTS) packet
• if sender does not receive CTS, it will retry at later point in time
• nodes overhearing RTS or CTS know that reservation has taken place and must wait
(e.g., based on the size of data transmission)
• address hidden terminal problem and reduces number of collisions
• MACA for Wireless LANs (MACAW)
• receiver responds with acknowledgment (ACK) after data reception
➢ other nodes in receiver’s range learn that channel is available
• nodes hearing RTS, but not CTS do not know if transmission will occur
➢ MACAW uses data sending (DS) packet, sent by sender after receiving CTS to inform such nodes of
successful handshake
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – MACA BY INVITATION
• In MACA-BI, destination device initiates data transfers by sending a Ready
To Receive (RTR) packet to the source
• source then responds with the data message
• Compared to MACA, MACA-BI reduces overhead
• increases the theoretical maximum throughput
• depends on the destination knowing when to receive data
• Source nodes can use an optional field within the data message to indicate
the number of queued messages
• providing the destination with an indication that more RTS packets will be required

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – IEEE802.11
• Published in 1999 by the Institute of Electrical and Electronics Engineers
(IEEE)
• specifies the physical and data link layers of the OSI model for wireless connections
• Often referred to as Wireless Fidelity (Wi-Fi)
• certification given by Wi-Fi Alliance, a group that ensures compatibility between
hardware devices that use the 802.11 standard
• Wi-Fi combines concepts found in CSMA/CA and MACAW, but also offers
features to preserve energy
• Two modes of operation
• Point Coordination Function (PCF) mode
• communication among devices goes through a central entity called an access point (AP) or base
station (BS): managed mode
• Distributed Coordination Function (DCF) mode
• devices communicate directly with each other: ad-hoc mode
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – IEEE802.11
• IEEE 802.11 is based on CSMA/CA
• before a node transmits, it first senses the medium for activity
• the node is allowed to transmit, if the medium is idle for at least a time period
called the DCF inter-frame space (DIFS)
• otherwise the device executes a back-off algorithm to defer transmission to a later
time
• this algorithm randomly selects a number of time slots to wait and stores this value
in a back-off counter
• for every time slot that passes without activity on the network, the counter is
decremented and the device can attempt transmission when this counter reaches
zero
• if activity is detected before the counter reaches zero, the device waits until the
channel has been idle for a period of DIFS before it continues to decrement the
counter value
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
WIRELESS MAC PROTOCOLS – IEEE802.11
• After a successful transmission
• receiver device responds with an acknowledgment after waiting for a time period
called the short inter-frame space (SIFS)
• the value of SIFS is smaller than the value of DIFS to ensure that no other device
accesses the channel before the receiver can transmit its acknowledgment
• Once a node A makes a reservation using RTS and CTS control messages
• another neighboring node B, overhearing the RTS message, must refrain from
accessing the medium until node A’s transmission has been completed and
acknowledged
• however, this would mean that node B has to continuously sense the medium to
detect when it becomes idle again

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 7: NETWORK LAYER – ROADMAP
• Routing basics
• Data-centric routing
• Proactive routing
• On-demand routing
• Hierarchical routing
• Location-based routing
• QoS-based routing

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CHAPTER 7: NETWORK LAYER – A PRELUDE DISCUSSION

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
NETWORK LAYER RESPONSIBILITY
• Direct communication model: every sensors
communicates directly (single- hop) with the sink
device (base station)
• often not feasible due to lack of energy, scale of
network, lack of unobstructed communication links
between sensors and sink
• Multi-hop communication model: sensors
cooperate in propagating sensor data towards the
sink
• Routing is a key responsibility of the network layer
• Routing protocol is responsible for finding and
maintaining path from sensor to sink
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CLASSIFICATION OF ROUTING PROTOCOLS

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
CLASSIFICATION OF ROUTING PROTOCOLS
• Network organization
• flat: all nodes are “equal”
• hierarchical: different “roles” for different nodes (e.g., cluster heads versus cluster
members)
• location-based: nodes rely on location information
• Route discovery
• reactive (on-demand): find route only when needed – slow, incurs delay in finding
• proactive (table-driven): establish routes before they are needed – may not be needed
• hybrid: protocols with reactive and proactive characteristics
• Protocol operation
• negotiation-based: negotiate data transfers before they occur
• multi-path: use multiple routes simultaneously
• query-based: receiver-initiated
• QoS-based: satisfy certain QoS (Quality-of-Service) constraints
• coherent-based: perform only minimum amount of in-network processing
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ROUTING METRICS
• Minimum hop (shortest hop)
• Energy
• minimum energy consumed per packet – select energy efficient path
• maximum time to network partition – last node linking two parts expires
• minimize variance in node power levels – all nodes are equally important
• maximum (average) energy capacity – favour routes with max. (av.) energy cap.
• maximum minimum energy capacity – select path with largest min. energy cap.
• Quality-of-Service
• latency (delay), throughput, jitter, packet loss, error rate
• Robustness
• link quality, link stability

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ROUTING METRICS – EXAMPLE

• Numbers along links: cost for transmission over link

• Numbers in parentheses: remaining energy capacity
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
FLOODING
• Every sensor node (re-)broadcasts sensor data to all of its neighbors
• Simple and reliable technique
• Incurs large traffic overhead (maximum-hop counts and sequence numbers
can be used to limit broadcasts and eliminate duplicates)
• However, flooding faces three more challenges:
• Implosion: nodes will re-broadcast
even when neighbors already have
a copy
• Overlap: sensor data contains
redundant information
• Resource blindness: resource
constraints of nodes are ignored
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPIN FAMILY OF PROTOCOLS
• Sensor Protocols for Information via Negotiation (SPIN)
• Example of data-centric routing
• Uses negotiations to address all problems of flooding
• implosion: nodes negotiate before data transmission
• overlap: nodes negotiate before data transmission
• resource blindness: resource manager keeps track of actual resource
consumption and adapts routing and communication behaviour
• SPIN uses meta-data to succinctly and completely describe sensor data
• Requirements:
• if x describes the meta-data for some sensor data X, the size of x (in bytes) must
be less than the size of X
• if two pieces of sensor data differ, their meta-data representations should differ
too
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPIN-PP
• Optimized for networks using point-to-point transmission media (two
nodes communicate exclusively with each other without interference)
• Flooding occurs using a 3-way handshake:
• node A advertises newly available data using ADV (advertisement) message
(containing dataʼs meta-data)
• neighbor nodes (B, C, D, E) check if advertised data needed and if so, respond
with REQ (request for data)message
• A sends DATA message to nodes that responded (i.e., B and D)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPIN-PP
• Only nodes needed the advertised data respond
• Nodes can aggregate received data with their own and advertise
aggregate Simple protocol
• Nodes need to know their single-hop neighbors only
• Lost ADV messages: periodically re-advertise
• Lost REQ/DATA messages: re-request data of interest if data does not
arrive within certain timeout interval
• Protocol could also use explicit acknowledgments (e.g., REQ can contain
list of data a node wants or does not want and using this list, a node can
identify whether previous advertisements were received successfully)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPIN-EC AND SPIN-BC
• SPIN-EC:
• adds simple heuristic to protocol to add energy conservation
• as long as energy sufficient, node participates in 3-way handshake
• nodes does not participate if it believes that this will reduce its energy below a
certain low-energy threshold
• node replies to ADV only if sufficient energy for transmitting REQ and receiving DATA
• node initiates handshake only if it has sufficient energy to send DATA to all neighbors
• SPIN-BC:
• uses one-to-many communications (broadcast)
• receiver node waits for a random time interval before issuing REQ; if other
nodeʼsREQ overheard, the receiver node cancels timer and does not send its
own REQ
• advertiser broadcasts DATA only once (ignore duplicate REQs)
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPIN-RL
• Reliable version of SPIN-BC
• nodes keep track of overheard REQ messages
• if DATA message does not arrive within certain timeout interval, it assumes that
either REQ or DATA did not arrive
• node broadcasts REQ to re-request data
• in message header, node specifies identity of randomly selected node among nodes that
previously sent ADV for missing
• DATA SPIN-RL limits frequency with which DATA messages are sent
• once a node sends a DATA message, it will wait for certain amount of time before responding
to other requests for the same data

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DIRECTED DIFFUSION
• Data-centric and application-aware dissemination protocol
• Nodes request data by sending interests for named data
• data is named by attribute-value pairs
• Interest dissemination sets up gradients within network to direct sensor
data toward recipient
• Intermediate nodes along the paths can combine data from different
sources
• eliminates redundancy
• reduce number of transmissions

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DIRECTED DIFFUSION: ATTRIBUTE-VALUE PAIRS
• Simple vehicle-tracking application
type = vehicle // detect vehicle location
interval = 20ms // send data every 20 ms
duration = 10s // perform task for 10 s
rect = [-100,-100,200,200] // from sensors within rectangle

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DIRECTED DIFFUSION

(a) Interested node (sink) periodically sends interest to neighbors, which re-broadcast these messages
(b) Each node establishes a gradient towards the sink, which is a reply link toward the neighbor from which
the interest was received
(c) Source can send data towards sink using these gradients
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DIRECTED DIFFUSION
• Reinforcement:
• multiple paths from source to sink may exist
• sink can reinforce one particular neighbor based on some data-driven local rule
• example: sink could reinforce neighbor from which it has received a previously unseen event
• sink resends original interest message to that neighbor, which in turn reinforces one or more
of its neighbors based on its own local rule
• Comparison to SPIN:
• interests (queries) are issued on demand by the sink (instead of source
advertisements)
• query-based approach may not be best solutions for networks with need for continuous data
transfers (e.g., environmental monitoring)
• communication is all neighbor-to-neighbor (removing the need for addressing
schemes and allowing nodes to perform aggregation and caching)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
RUMOR ROUTING
• Attempt to combine characteristics of event flooding (classic flooding)
and query flooding (directed diffusion)
• Nodes maintain two data structures:
• list of neighbors
• event table that contains forwarding information to all known events
• once an event is witnessed, it is added to the table (including a distance of 0) and an agent is
generated with certain probability
• agent is a long-lived packet traveling the network to propagate information about this new
event (and other events encountered along its route)
• once agent arrives at a node, the node can update its table

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
RUMOR ROUTING – EXAMPLE
• Node E reports new event E1 using agent
• A receives agent via G and updates its table reflecting shorter distance
to E1 via G

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
RUMOR ROUTING – QUERIES
• When node wants to issue query for certain event:
• check if route towards event is in table
• if yes, forward query to next-hop neighbor indicated in table
• if no, pass query to randomly selected neighbour
• process is continued on each forwarding node and query collects list of recently seen
nodes (to avoid revisiting them)
• TTL (time-to-live) counter is used to limit traveled distance
• if no response received after certain timeout value (i.e., the query did not reach the
target), a different technique (classic flooding of the query) can be used
• Summary: strikes balance between query and event flooding
• query flooding may be too expensive with large query/event ratio
• event flooding may be too expensive when number of events large
• rumor routing propagates queries directly to nodes that seen event of interest
• latency secondary concern in rumor routing
• table can grow large with large number of events
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GRADIENT-BASED ROUTING (GBR)
• Another variant of directed diffusion
• Gradient is determined on the basis of the number of hops to the sink
• a sink floods interest message
• each interest message records number of hops travelled
• therefore, a node can determine its distance (called height) to sink
• gradient is difference between a nodeʼsheight and height of neighbour
• packet is forwarded on the link with the largest gradient
• Nodes can establish a Data Combining Entity (DCE), which is responsible for
data compaction
• Nodes can use a traffic spreading technique to balance traffic over network
• stochastic scheme: node selects next hop randomly when there are two or more with
same gradient
• energy-based scheme: node increases its height when its energy level is low
• stream-based scheme: new streams are diverted away from nodes that already serve
other streams (e.g., by reporting increased heights)
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PROACTIVE ROUTING
• Routes are established before they are actually needed
• Also called table-driven routing
• Main advantage: routes can be used immediately when needed (table
look up for next-hop neighbor) Main disadvantages:
• establishing and maintaining routes that are infrequently (or never) needed
• routing tables can become very large
• stale information in tables can lead to routing errors

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DESTINATION-SEQUENCED DISTANCE VECTOR (DSDV)
• DSDV is a modified version of class Distributed Bellman-Ford algorithm
• Concept of distance-vector algorithms:
• node i maintains a list of distances {dij}x for each destination x via node j
• node i selects k as next-hop if dik =x min{dij}x
• distances stored in routing table, along with sequence number for each entry
(assigned by destination node)
• purpose of sequence number is to identify stale routes
• nodes broadcast their routing tables to their neighbors periodically and
whenever significant information is available
• full dump packet: contains entire routing table
• incremental packet: contains only changed table entries
• a receiving node updates its table if the received information has a more recent sequence
number or if sequence number is identical, but new route is shorter

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DSDV – EXAMPLE

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
OPTIMIZED LINK STATE ROUTING
• OLSR is a protocol based on the link state algorithm
• nodes periodically broadcast topological information updates to all other nodes
in the network
• allows nodes to obtain complete topological map and to compute paths
• Nodes use neighbor sensing using HELLO messages:
• allows nodes to identify neighbors and to detect changes in neighbourhood
• HELLO message contains nodeʼsidentity (address) and list of all known neighbors
• if node A can receive node Bʼs HELLO messages, but is not in node Bʼs list of
known neighbors, the link B ➔ A is asymmetric (otherwise symmetric)
• instead of flooding HELLO messages to all nodes in network, OLSR uses
multipoint relays (MPRs)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
OPTIMIZED LINK STATE ROUTING
• Multipoint relays:
• a node selects a set of symmetric neighbors as
MPRs (MPR selector set); each node can use
different algorithm/heuristic for the selection
process
• example: node determines its 2-hop neighbors (using
HELLO messages) and selects minimum set of 1-hop
neighbors to reach all 2-hop neighbors
• only MPRs forward messages to other nodes
• HELLO messages contain addresses of MPRs, i.e., a
node advertises its reachability via MPRs only
instead of all neighbors

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
ON-DEMAND (REACTIVE) ROUTING
• Routes are not established until actually needed
• Instead, a source node (knowing the identity/address of a destination node)
initiates a route discovery process which completes when at least one route
has been found or all possible paths have been examined
• A newly discovered route is then maintained until it either breaks or is no
longer needed by the source

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
AD HOC ON-DEMAND DISTANCE VECTOR
• AODV relies on broadcast route discovery mechanism, which is used to
dynamically establish route table entries at intermediate nodes
• Path discovery process:
• initiated whenever a source needs to transmit data to a sink and the source does not
have an entry for the sink in its routing table
• source broadcasts route request (RREQ) packet containing:
• addresses of source and sink
• hop count value
• broadcast ID (incremented whenever source issues a new RREQ)
• two sequence numbers
• upon receiving RREQ, if a node knows a route to the destination, responds by sending
a unicast route reply (RREP) message back to source
• otherwise RREQs are re-broadcast or duplicate RREQs (identified by source address
and broadcast ID) are discarded
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
AD HOC ON-DEMAND DISTANCE VECTOR
• Use of sequence numbers:
• Every node maintains own sequence numbers
• Sourceʼs RREQ includes its own sequence number and the most recent sequence
number (if known) from the destination
• Intermediate nodes only reply to RREQ if the sequence number of their route to the
destination is greater than or equal to the destination sequence number in the RREQ
• When RREQ is re-broadcast, node records the address of neighbor from which RREQ
came (establishing a reverse path towards source)
• As RREP travels towards source, intermediate nodes set up forward pointers to the
node from which the RREP came and records latest destination sequence number

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
AD HOC ON-DEMAND DISTANCE VECTOR
• Use of RREPs:
• RREP contains:
• addresses of source and destination
• destination sequence number
• hop count intermediate node propagates RREP only if
• this is the first copy of this RREP the node sees
• or destination sequence number in RREP is greater than that of previous RREP
• or destination sequence number is the same as in previous RREP, but the hop count is smaller
• limits the number of RREPs in network and ensures that the RREP over the shortest
route reaches the source

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
AD HOC ON-DEMAND DISTANCE VECTOR

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
AD HOC ON-DEMAND DISTANCE VECTOR
• Routes expire after certain amount of time
• Link state monitored using HELLO messages among neighbors
• when a link/route breaks, the node noticing this issues a route error (RRER) packet
towards the source (which can re-initiate route discovery)
• Summary:
• routes are established only when needed
• no need for route table updates and exchanges for unused routes
• periodic HELLO messages
• initial transmission delay if route must be discovered first
• RREP uses reverse path of RREQ, i.e., AODV assumes symmetric links

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DYNAMIC SOURCE ROUTING (DSR)
• Route discovery and maintenance similar to AODV
• Each node maintains route cache with entries that are continuously updated when
node learns new routes
• Similar to AODV, source first inspects cache and initiates route discovery if no route
found
• RREQ contains:
• addresses of source and destination
• unique request ID
• list of visited nodes
• Each forwarding node inserts its own address into list of visited nodes
• When node finds its own address in RREQ, packet is discarded
• Nodes keep cache of recently forwarded RREQs (sender address and request ID) to
identify duplicates (which are discarded)
• Once RREQ reaches destination, it has recorded the entire route
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
DYNAMIC SOURCE ROUTING (DSR)
• Symmetric networks:
• destination can unicast response packet back to source
• packet contains entire route
• Asymmetric networks:
• destination can initiate own route discovery to the source
• request packet contains path from source to destination
• Route maintenance similar to AODV
• Advantages and disadvantages similar to AODV
• Route discovery packets larger (contain routes), but allow intermediate
nodes to add new routes to their caches proactively

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
HIERARCHICAL ROUTING
• Sensor nodes communicate directly only with a cluster head
• Cluster head:
• responsible for propagating sensor data to sink
• sometimes more powerful than “regular” nodes
• experiences more traffic than “regular” nodes
• Challenges in cluster formation:
• selection (election) of cluster heads
• selection of cluster to join
• adaptation of clusters in response to topology changes, failures, etc.
• Advantages:
• potentially fewer collisions (compared to flat routing)
• easier duty cycling (energy efficiency)
• easier routing process (though routes may be longer)
• easier in-network data aggregation
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
VARIATIONS OF HIERARCHICAL ROUTING

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LANDMARK ROUTING
• Landmark: node to which its neighbors within certain number of hops know
a route to that node
• Example:
• nodes 2..6 have routes to node 1
• node 1 is a landmark “visible” to all nodes within 2-hop distance, i.e., node 1 is a
landmark of radius 2
• Node i for which nodes within n hops have routes toward is a landmark of
radius n
• Hierarchy of landmarks: packet can be forwarded toward a destination by
choosing an appropriate sequence of landmarks

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LANDMARK ROUTING

• Example:
• landmark address of node LM0: LM2.LM1.LM0
• source has entry for LM2: packet travels towards LM2
• once packet reaches node within range of LM1: packet travels towards LM1
• once packet reaches node within range of LM0: packet travels to LM0
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LANMAR PROTOCOL
• Combines landmark routing with Fisheye State Routing
• Uses landmarks to establish two-tiered logical hierarchy
• each landmark is a cluster head of a logicalsubnet
• Fisheye State Routing
• link state routing protocol
• frequency of route updates depends on the distance (routes within fisheye scope are more
accurate than others)
• Routing updates are only exchanged with nodes in immediate neighborhood and
with landmark nodes (update frequency to all other nodes is zero)
• Data propagation:
• if destination is known, forward data directly to destination
• otherwise, forward towards the landmark corresponding to the destinationʼs logical subnet
• once packet enters the scope of the destination, it is forwarded directly to the destination
Sensor Networks: Theory and Practice
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LEACH
• Low-Energy Adaptive Clustering Hierarchy
• Combines clustering with MAC-layer techniques (see previous discussion on
LEACH MAC layer)
• Assumes that cluster heads can communicate directly with base station
• Cluster heads are responsible for forwarding sensor data to base station
• Cluster heads are responsible for data aggregation to eliminate redundancy

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
PEGASIS
• Power-Efficient Gathering in Sensor Information System
• Nodes exchange packet with close neighbors and take turns in being
responsible for packet forwarding to the base station
• Nodes organize into chain (either decentralized algorithm or determined by
the base station)
• When data travels along chain, it can be aggregated with other data
• High energy-efficiency since nodes only communicate with closest neighbors
• Protocol assumes that all node can communicate with the base station
• Packet delays may be large
• Node forwarding to base station can become a bottleneck
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SAFARI
• Drums (landmarks) in Safari use a self-election algorithm to form subnet hierarchy
• level 0: each node forms its own cell
• level 1: fundamental cells contain multiple nodes, but no other cells
• level 2..n: cells composed of multiple smaller cells
• Drums periodically broadcast
• beacons within well-defined limited scopes
• beacons aid the hierarchy formation
• beacons give nodes an indication of their position in the network beacons provide routing information
toward the drumʼscell
• Routing within cells is based on DSR
• More distant nodes are reached using a proactive routing approach
• inter-cell communication relies on destination nodeʼs hierarchical address and on beacon records
stored on each node
• routing follows reverse path of beacons
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
LOCATION-BASED ROUTING
• Also referred to as geographic routing
• Used when nodes are able to determine their (approximate) positions
• Nodes use location information to make routing decisions
• sender must know the locations of itself, the destination, and its neighbors
• location information can be queried or obtained from a location broker
• Types of geographic routing: unicast: single destination multicast: multiple
destinations geocast: data is propagated to nodes within certain geographic
area

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
UNICAST LOCATION-BASED ROUTING
• One single destination
• Each forwarding node makes localized decision based on the location of the
destination and the nodeʼsneighbors (greedy forwarding)
• Challenge: packet may arrive at a node without neighbors that could bring
packet closer to the destination (voids or holes)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GREEDY PERIMETER STATELESS ROUTING
• In GPSR, a node forwards packet to neighbor that is geographically closest to
the destination
• Challenge of voids/holes (example: x is closer to the destination its neighbors
w and y)
• GPSR uses right-hand rule to traverse graph
• when a packet arrives at node x from node y, the next edge traversed is the next one
sequentially counterclockwise about x from edge (x,y)
• right-hand rule traverses interior of a polygon in clockwise edge order and exterior
region in counterclockwise edge order

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GREEDY PERIMETER STATELESS ROUTING
• Sequence of edges traversed according to rule is called perimeter
• In non-planar graphs, right-hand rule may take tour of edges that does not
trace the boundary of a closed polygon
• To obtain planar graphs, crossing edges must be removed (without
partitioning the network)
• Relative Neighborhood Graph (RNG)
• Gabriel Graph (GG)
• Example: RNG
• lune between u and v (intersection of radio ranges) must be empty of any witness
node w such that edge (u,v) can be included in the RNG (i.e., if this region is
nonempty, the link (u,v) will be removed)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
FORWARDING STRATEGIES
• Greedy: minimize distance to destination in each
hop
• Nearest with Forwarding Progress (NFP): nearest
of all neighbors that make positive progress (in
terms of geographic distance) toward destination
• Most Forwarding Progress within Radius (MFR):
neighbor that makes greatest positive progress
(progress is distance between source and its
neighbor node projected onto a line drawn from
source to destination)
• Compass Routing: neighbor with smallest angle
between a line drawn from source to the neighbor
and the line connecting source and destination
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC ADAPTIVE FIDELITY
• GAF was primarily designed for networks with mobile nodes
• Network region is divided into virtual grid
• In each cell, only one node is a forwarder at any given time (all other nodes
can sleep)
• Assumption: all nodes within a cell can communicate with all nodes within all
adjacent cells

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC ADAPTIVE FIDELITY
• Discovery state:
• nodes are initially in the discovery state, where they listen for messages from other nodes
within cell
• each node uses timer; when timer expires, node broadcasts discovery message and enters
active state
• Active state:
• node periodically re-broadcasts discovery messages
• node sets another timer to re-enter discovery state after timer expiration
• Sleep state:
• entered (from both discovery or active states) whenever node determines that some other
node is forwarder
• nodes periodically re-enter discovery state
• Forwarder node:
• determined using negotiation process
• nodes in active state win over nodes in discovery state
• node IDs used to break ties
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MULTICAST LOCATION-BASED ROUTING
• Multicast: deliver the same packet to multiple receivers
• Simple solution 1: deliver copies of same packet to each individual receiver
via unicast routing
• resource-inefficient
• Simple solution 2: flood the entire network
• resource-inefficient
• Concerned with efficiently delivering the same packet to receivers, i.e.,
minimize the number of links the packet has to travel
• Common approach: multicast tree rooted at source and destinations are leaf
nodes

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SCALABLE POSITION-BASED MULTICAST
• SPBM relies on group management
scheme to maintain list of all
destinations for a packet
• Packet header carries group
membership information instead of all
destinationʼs addresses to ensure
efficiency
• Network is represented as a quad-tree
with pre-defined number of levels L
• Example: L=3 (levels 0..L-1)
• All nodes within level-0 square are in
radio range of each other
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SCALABLE POSITION-BASED MULTICAST
• Nodes maintain twotables:
• global membertable
• containing entries for the three neighboring squares for each level
• each entry contains squareʼsidentifier and list of nodes insquare
• local member table
• containing all members of the nodeʼslevel-0neighbors
• each entry contains node IDs and membership information of nodes

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SCALABLE POSITION-BASED MULTICAST
• Membership information indicates the multicast groups to which node
belongs and is encoded as vector (each bit represents a multicast group)
• 10100010 for square 41 in the global member table indicates that there exist nodes in
square 41 that belong to multicast groups 2, 6, and 8
• 00000001 for node 14 in the local member table indicates that node 14 is a member
of multicast group 1
• Local member table is broadcast periodically within nodeʼslevel-0 square
• Randomly chosen node in each level-0 square periodically disseminates its
global member table to all nodes in its level-1 square (process repeated at
each level)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SCALABLE POSITION-BASED MULTICAST
• SPBM uses greedy forwarding to choose next-hop neighbors
• SPBM uses splitting to send copies of the same packet into different
“directions”
• splitting is based on a heuristic that provides a tradeoff between total number of
nodes forwarding the packet and the optimality of the individual routes toward the
destinations
• once a forwarding node finds a multicast member in its local member table, it
forwards packet directly to that node
• Similar to GPSR, SPBM uses perimeter routing mode to address voids

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
OTHER MULTICAST ROUTING PROTOCOLS
• Geographic Multicast Routing (GMR)
• heuristic neighbor selection scheme with low computational overheads
• results in routest based on a cost over progress metric (ratio of the number of selected forwarding
nodes over the progress made toward all destinations)
• Receiver Based Multicast (RBMulticast)
• sender can transmit packet without specifying next-hop node
• network is divided into multicast regions
• RBMulticast does not use membership tables (stateless)
• each multicast region is represented by virtual node and each forwarding node replicates packet for
each region that contains at least one multicast member; packet is then sent toward virtual node
• relies on MAC layer that ensures that neighbor closest to location of virtual node takes responsibility for
forwarding the packet (nodes contend for channel access and nodes closer to destination are more
likely to win)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOCASTING
• Packet is sent to all or some nodes within specific geographic region
• Example: query sent to all sensors within geographic area of interest
• Routing challenge:
• propagate a packet near the target region (similar to unicast routing)
• distribute packet within the target region (similar to multicast routing)

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC AND ENERGY AWARE ROUTING
• In the GEAR protocol, each node maintains two types of costs of reaching a
destination:
• estimated cost c(Ni,R) = α*d(Ni,R) + (1 -α)*e(Ni)
• Ni = neighbour i
• d(Ni,R) = distance from neighbor Ni to centroid D of region R normalized by
the largest such distance among all neighbors
• e(Ni) = consumed energy at node Ni
• α = tunableweight
• combination of both residual energy and distance to target region
• learned cost h(N,R) of node N
• refinement of estimated cost that allows nodes to circumvent voids (without voids, learned cost =
estimated cost)
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC AND ENERGY AWARE ROUTING
• GEAR makes greedy forwarding decisions
• If forwarder detects void:
• packet is sent to neighbor Nmin with minimum learnedcost
• forwarder adjusts it own learned cost
• h(N,R) = h(Nmin,R) + C(N,Nmin)
• C(x,y) = cost of transmitting a packet from node x to node y
• that is, learned cost will increase, which allows upstream nodes to avoid forwarding
packets toward the node in the void

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC AND ENERGY AWARE ROUTING
• Example: S(source) sending a packet to centroid of target region (T)
• Learned (estimated) costs are √5 for neighbors B and I and 2 for neighbor A
• Packet goes from S to A, which finds itself in hole
• A forwards packet to B and computes own cost h(A,T) = h(B,T) + C(A,B)
(assuming cost (A,B)=1, the new cost will be √5+1)
• Next time, S will directly select B instead of A

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC AND ENERGY AWARE ROUTING
• Once packet reaches target region R, simple flooding with duplicate
suppression could be used
• GEAR relies on Recursive Geographic Forwarding
• nodes within target region create four copies of packet bound to four smaller
subregions
• in each subregion, GEAR repeats the forwarding and splitting process until node is
reached that is the only one within the current subregion

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC-FORWARDING-PERIMETER-GEOCAST
• GFPG uses greedy forwarding to propagate packet toward target region
(destination is center of the region)
• Perimeter routing is used when voids are reached
• Within target region, flooding can be used, but delivery to all nodes would
not be guaranteed
• Instead, GFPG uses a combination of geocast and perimeter routing
• once a packet reaches target region, it is flooded too all nodes
• further, region border nodes (nodes with at least one neighbor outside the region)
send packet to neighbor nodes outside region
• nodes outside the region use right-hand rule to forward packet to neighbors in the
planar graph; packet travels around the face until it enters the region again

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
GEOGRAPHIC-FORWARDING-PERIMETER-GEOCAST

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
QOS-BASED ROUTING PROTOCOLS
• Protocols that explicitly address one or more Quality-of-Service (QoS) metrics
• Examples of QoS metrics:
• low (end-to-end) latency/delay
• low jitter
• low energy consumption
• low bandwidth requirements high
• reliability

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SEQUENTIAL ASSIGNMENT ROUTING
• Example of multipath routing
• SAR creates multiple trees, each rooted at a 1-hop neighbor of the sink, to establish
multiple paths from each node to the sink
• Tree grows outward from the sink, while avoiding nodes with low QoS
• Additive QoS metric (higher values indicate lower QoS)
• Nodes are likely to be part of multiple trees (routes)
• Route is chosen based on the QoS metric, energy (how many packets can be transmitted
without energy depletion?), and priority level of packet
• Goal of SAR is to minimize the average weighted QoS metric over the lifetime of the
network
• Multipath routing helps with fault tolerance and quick recovery from broken routes
• Establishing and maintaining all trees is expensive
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPEED
• Support for soft real-time applications, providing real-time unicast, real-time area-
multicast, real-time area-anycast
• Location-based routing
• Periodic HELLO (beacon) messages
• nodeID
• position
• average receive delay
• Each node maintains neighbor table with the following entries for each neighbor:
• nodeID
• position
• expiration time (ExpireTime)
• ReceiveFromDelay (estimated by measuring the delay experienced by packet in the MAC layer
of sender plus propagation delay)
• SendToDelay (delay received from beacon message)
• ReceiveFromDelay values of all neighbors are averaged periodically to obtain single
receive delay
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPEED
• Routing component: Stateless Nondeterministic Geographic Forwarding
(SGNF)
• Neighbor set of i: neighbors of i at least distance K away from i Dest
• Forwarding candidate set FSiDest : all neighbors that are at least distance K
closer to destination
• neighbor j is in set if L-Lnext ≥K
• L = d(i,dest)
• Lnext = d(j,dest)
• Packets are forwarded to nodes in FSiDest only; if empty, packet is dropped
• FSiDest further subdivided:
• set of nodes with SendToDelay less than certain single hop delay D
• set of all other nodes
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPEED
• Forwarding candidate is selected from first group where nodes with higher
relay speed have a greater chance of being selected.
• Relay speed considers both distance and delays:

• If there are no nodes in the first set, a relay ratio can be calculated, based on
SPEEDʼsneighborhood feedbackloop
• responsible for determining relay ratio by looking at miss ratios of neighbors
• if relay ratio is less than randomly selected number between 0 and 1, packet
is dropped
• goal is to keep system performance at desired value, attempting to keep
single hop delay below D
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SPEED
• Back-pressure rerouting protocol of SPEED is responsible for
• preventing voids that occur when nodes fail to find next hop node
• reducing congestion using a feedback approach

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MULTIPATH MULTI-SPEED
• MMSPEED provides QoS differentiation in terms of timeliness and reliability, while also
minimizing protocol overhead
• Makes localized routing decision without a priori route discovery or global network state
updates
• Offers multiple delivery speed options
• Can be considered as virtual overlay of multiple SPEED layers
• Each layer l has SetSpeedl associated, which is a pre-specified lower- bound speed, i.e.,
when a node computes the relay speed for each neighbor, it chooses a forwarding node
whose relay speed is at least the desired SetSpeed value

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MULTIPATH MULTI-SPEED
• Layer selected at one node can differ from layer selected at other node (e.g.,
packet can be boosted by using a higher layer)
• Necessary to determine remaining time to deadline, requiring synchronized
clocks in the network
• MMSPEED measures elapsed time at each node and piggybacks time onto
packet
• MMSPEED also offers different levels of reliability

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MULTIPATH MULTI-SPEED
• MMSPEED also offers different levels of reliability
• Each node maintains recent average of packet loss percentage ei,j to each
neighbor j losses include intentional drops (congestion control) and errors
• Node computes estimate of packet loss probability

• Assumption is that subsequent nodes have similar packet loss rate and that
progress to destination for each hop will be similar to current progress
• Node can determine number of forwarding paths that satisfy end-to-end
reachability requirement of packet

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
MULTIPATH MULTI-SPEED
• Total reaching probability is set to zero initially and updated for each forwarding
path being used:

• (1-TRP) is the probability that none of current paths can successfully deliver the
packet to the destination
• (1-RPi,jd) is the probability that additional path will fail to deliver the packet
• New TRP is then the probability that at least one path will successfully deliver
the packet to the destination
• Latency and reliability can be combined
• identify required speed level for a packet
• find multiple forwarding paths among paths with sufficient progress speed such that
total reaching probability is at least as high as required reaching probability
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
SUMMARY

Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar
Dr. Abhaya Kumar Samal, Dean(SoC), Dean(P&C), Professor in CSE, TAT, Bhubaneswar