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 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.

Broadcast Storm Problem - Analysis

Associated with flooding, we refer to these 3 problems as the Broadcast Storm Problem.
It here has the following characteristics:

• The broadcast is spontaneous.
  Any mobile host can issue a broadcast operation at any time.
  Preparing any kind of global topology knowledge is prohibitive due to host mobility and the lack of synchronization.
• The broadcast is unreliable.
  No acknowledgement mechanisms will be used.

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

Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the Broadcast Storm Problem.

Scheme-based Flooding

All but the last scheme (Cluster-based) operate in a fully distributed manner to estimate redundancy and accumulate knowledge.

Probabilistic Scheme

On receiving a broadcast message for the first time, a host will rebroadcast it with probability P. Clearly, with P = 1 the scheme is equivalent to simple flooding. A few slots delay (random) should be added to reduce collisions and contention.

Counter-based Scheme

When a host tries to rebroadcast a message, this message may be blocked by busy medium, backoff procedure or other queued messages. A counter keeps track of repeated arrivals of the same message, so that we can prevent a host from rebroadcasting if the expected additional coverage of a rebroadcast becomes to low.

Distance-based Scheme

The relative distance d between hosts decides whether the rebroadcast message is dropped or not. A larger d promises larger additional coverage. If the same message is heard more than once, the distance d from the nearest host (d_min) is used. If d_min is below a certain threshold D, the rebroadcast is canceled.

Location-based Scheme

The location-based scheme utilizes the exact locations of broadcasting hosts, which could for example be obtained with the help of GPS. With these 3D-coordinates, the additional coverage AC can be calculated with higher precision. If AC is below a certain coverage threshold A, the host is inhibited from rebroadcasting. As calculating AC is already difficult with four circles (covered areas resulting from the initial broadcast host and 3 rebroadcasting hosts), convex polygons are used to approximate AC.

Cluster-based Scheme

The above schemes are based on statistical and geometric modeling to estimate the AC of a rebroadcast. However, the cluster-based schemes bases on graph modeling. The algorithm assumes that clusters have been formed in the MANET which are maintained by the underlying cluster formation algorithm.

This algorithm works as follows:

• every hosts advertises its presence
• → every host can determine its connectivity
• the host with the local minimal ID elects itself as a cluster head, all surrounding hosts are cluster members
• a member who can communicate with a member of another cluster is called gateway
• when two heads meet, the one with the larger ID gives up his head role

In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.

Conclusion

As you can see, The Broadcast Storm is a serious problem. Already a simple counter-based scheme can eliminate many redundant rebroadcasts when the host distribution is dense. If location information is available, the location-based scheme is dominant because it reduces redundancy w/out compromising the reachability.

Please consider looking at my presentation notes for some nice pictures that might help you see things clearer :)
If you are interested in the results of performance simulations, please take a look at [1].

Credits

• [1] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network",
  in Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking, August 1999, pp. 152-162.
• [2] A. S. Tanenbaum, "Computer Networks", 4th edition, 2003