Routing in ad-hoc Networks

devices-341443_640What does make routing and communication in Ad Hoc Networks different from routing and communication in usual LANs, WANs etc.? The main peculiarities are the absence of wires, routers and any predefined infrastructure. The nodes communicate with each other over the air and this is a very unreliable medium. Because of reflection, diffraction, diffusion and other signal propogation properties the data exchanging by nodes is frequently lost. Not only the connections between nodes can break, but the nodes move and the topology of the network can change any time.

Taking into consideration all these facts, it’s obvious that the standard approaches applicable to the usual networks with pre-existing infrastructure aren’t suitable in general for the ad hoc networks. In following I’d like to tell a couple of words to ISO/OSI layers and explain briefly how they are realized in ad hoc networks.

Data Link Layer.
In Ethernet the Carrier Sense Multiple Access Collision Detection (CSMA/CD) is mostly used as the Medium Access Control Protocol. This protocol does not work well in ad hoc network. So imagine there is a node A that wants to send a packet to the other node B. A has to be sure that no other neighbour is sending at the moment to avoid collisions. If medium is already in use, A has to wait. The main lack of this approach is so called Hidden Terminal Problem. hiddenterminalThe picture depicts it. The node C is hidden from the node A. If C is already sending and A wants to send, it can’t find any sending nodes nearby, so it starts sending too. It leads to a collisions at the node B.
That’s why IEEE 802.11 offers the alternative MAC protocol that partly solves this problem. If the node A wants to send some packet to the node B and the medium is free, A sends first of all a short RTS (ready to send) signal. All the neighbours of A know then that A is going to send. When B recieves RTS it sends CTS (clear to send) signal, and thus all the neihbours of B know that B is going to recieve. After the transmition B sends an ACK and it releases the medium for the neighbours.

Network Layer.
The most important and interesting question is how one node finds a multi-hop path to the other node. Routing protocols for mobile ad hoc networks are devided into three large classes proactive, reactive and hybrid routing protocols.
Reactive protocols are designed for the ad hoc networks with high dynamics, where the network topology changes frequently. Each time when one node sends a packet to the other node, the routing path is built up again.

Proactive protocols use a kind of routing tables. It is assumed that the routes change not so often and they can be saved for a while in a table. The tables are then changed by the nodes.

Hybrid protocols use both of these technics.

The list of most popular algorithms can be found for example in Wikipedia.

Transport Layer.
In most ad hoc networks various realizations of TCP are used as the transport protocol. All the realizations like TCP Reno, TCP New-Reno differ from each other by algorithms that set the congestion window. The “normal” TCP doesn’t work well in ad hoc networks because the packets are frequently lost being propagating over the air. “Normal” TCP has to be adopted to these conditions.

Application Layer.
Unlike the Application Layer in common networks, application layer in mobile ad hoc networks can’t be completely isolated from the network layer. The developing applications have to be aware of the dynamics of the network and depending on the frequency of the topology changes apply for example the appropriate routing protocol.