Broadcast in Wireless multi-hop Networks

Introduction

Broadcasting in the field of network communication usually means the distribution of messages/data to a number of recipients.

Why broadcasting?

Broadcasting is a common technique to realize many network issues such as

• paging,
• sending alarm signals,
• routing (e.g., DSR, ZRP, AODV),
• providing multicast in rapidly changing topologies.

Broadcasting by flooding

There are several ways to send a message from one host to all the other hosts. Broadcasting done by flooding is a simple and straight-forward approach to deal with this problem. Unfortunately, if flooding is done blindly, we could observe

• redundant rebroadcasts,
• heavy contention,
• collisions.

Many rebroadcasts are considered to be redundant, since the radio propagation is omnidirectional and a physical location may be covered by the transmission ranges of several hosts. As rebroadcasting hosts might be close to each other, heavy contention could exist. Collisions are more likely to occur because the timing of rebroadcasts is highly correlated.

We refer to these problems associated with flooding as the Broadcast Storm Problem. Reducing the possibility of redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate this problem.

Broadcast Storm Problem - Analysis

Redundant Rebroadcasts

Imagine the simple scenario where host A sends a broadcast message and host B decides to rebroadcast it.
Due to the intersection area of the omnidirectional radio signals, a rebroadcast can only provide up to 61% additional coverage.
The expected additional coverage EAC(k) is even less: 41% for the 1^st rebroadcast, 19% for the 2^nd rebroadcast. When k ≥ 4, EAC(k) is below 0.05%!

Contention

Consider the situation where host A transmits a broadcast message. Let hosts B and C be two receiving hosts which try to rebroadcast the message. The expected probability for C to contend with B is ≈ 59%. Clearly, the contention is expected to be higher as n, the number of hosts willing to rebroadcast, increases. The probability cf(n,k) that k hosts among these n hosts experience no contention in their rebroadcasts increases quickly over 0.8 for n ≥ 6 and k = 0. So, the more crowded the area is, the more serious the contention is. The probability of having at least one contention-free host (cf(n,1)) is under 10% for n ≥ 5. Further, having more than one contention-free host is very unlikely.

Collisions

CSMA/CA requires a host to backoff right after the transmission of a message, or when a host wants to transmit but the medium is busy and the previous backoff has been done.
The procedure is as follows:

• a counter is set to to an integer randomly picked from the current backoff window
• if channel clear assessment (CCA) detects no channel activity during the past slot: counter-1
• counter == 0 ⇔ backoff procedure finished

Now consider host X sending a broadcast.
Collisions occur for several reasons:

1. X's surrounding has been quiet for some time
   • →X's neighbours might have finished their backoff
   • →they may all start rebroadcasting at the same time
2. lack of RTS/CTS-dialogue (not used for broadcasts)
3. lack of CD (collision detection)
   • →host finishes its transmission, even if bits have been garbled