On the reduction of broadcast redundancy in mobile ad hoc networks

The paper that we will be reading today describes an important and efficient technique to reduce redundancy in mobile ad hoc networks. I will be first explaining what ad hoc networks are, so people already familiar with that can skip the next part.

Computer networks are classified into two categories:
1. Wired Networks
2. Wireless Networks

Our focus for today is going to be wireless networks.
Wireless connections, as the name suggests, do not use wires for communication. Instead, they use radio communication. While both wired and wireless networks have their perks, wireless networks have seen a major development in its applications due to one particular advantage it has — Mobility.

Now, what exactly are ad hoc networks?
Ad hoc networks are decentralized wireless networks. They do not have any fixed architecture.
Why is this cool?
This is cool because in real life many networks do not follow a fixed architecture. Take us for example. Do we follow a fix path every day? Mind you, when I say fixed, I mean taking the exact same route, at the exact same time every single day. It is not. Similarly, a network may or may not a fixed architecture.
Ad hoc is cool because it is flexible.

In an ad hoc network devices are connected or disconnected spontaneously based on various factors. These factors can be the number of devices( we will call them nodes from now on) a network can contain, the communication range, the transmission range, etc.

A mobile ad hoc network involves mobile devices communicating directly with one another.

Ad hoc networks use broadcast to achieve various tasks.
When one node sends a message to all the other nodes of the network, it is called broadcast. Ideally, this is a very useful technique as it helps in route discovery i.e when you have to find the route between to specific nodes or to update the network information. However, as the number of nodes in a network increases, this leads to a lot of redundancy as well as traffic.

The paper explains a method using which this can be avoided.

Traditional ad hoc networks use flooding for broadcasting. Here, every node forwards a message it receives to all the nodes in the network. This is very simple to implement but it leads to a lot of duplicate messages. Hence the authors offer a different approach. This new broadcast approach makes two assumptions:
1. The omni-directional antenna is used and all mobile nodes have the same wireless transmission range. So, there exists a bi-directional link between two nodes if either is within another’s radio coverage.
2. The wireless channel is shared by all nodes and can be accessed by any node at random time. If a node transmits while one neighbor is receiving, a collision may occur at the latter.
First, every node should know his neighbor as well as his neighbor’s neighbor. This is done by exchanging “hello messages” among all neighbors periodically. Take this example.

A has two neighbors, B, C, and H.
B has three neighbors D, E, F.
C has one neighbor F.
F has one neighbor H.

They send hello messages to each other periodically as this system is mobile. Nodes tend to change their positions and hence their neighbors and the overall topology of the system.

Now, let S be the source of a message that is broadcast to all its neighbors.
Eventually, the message reaches Node A and it sends it to Node B. Now B carries out one the following functions:

1. It compares its neighbors with the neighbors of Node A and Node A itself. If they have all received the message, Node B will not rebroadcast and drop the message.

2. If the message is received firstly, Node B waits for a random time. During this time, duplicates will be discarded, the transmission will be carried on further and updates will be made. Node B then checks with all its 2 hop neighbors who have received the message. If they have it discards the message.

3. However, if all the neighbors are not covered, a rebroadcast is done.

In our example, when the message is received by C, using the neighbor table, it understands that its neighbor F as well as its 2- hop neighbor H, has received the message. Hence it discards it.

The technique can reduce broadcast redundancy efficiently. Normally, about 60% of duplicate messages can be saved compared with that of flooding. The delivery ratio of flooding decreases with the increase of the network size and the traffic load. The delivery ratio remains high for all pause times in both approaches, while this approach takes only about 30% broadcast cost to deliver messages to 97% receivers.