When one joins by an edge the nodes which are reciprocally in the range of their radio interface, one draws a graph (a random one) which looks like the one depicted in Figure 15.3.
Given two arbitrary nodes, the problem of routing results in calculating ˜the best path which makes it possible to join them. It is a shorter path problem in a graph using several powerful algorithms (Ford-Bellman, Dijkstra, are best known) to solve it, but the true difficulty is elsewhere. Each node must have its own up to date routing table, and it is necessary to update these tables (the nodes are mobile, they can appear or disappear, and their activity varies with time). This constraint is the cause of a considerable overhead of data in the network, the mobiles having to emit updating information for these tables. This overhead increases with the size of the network and the mobility of the nodes. The various routing algorithms which are proposed (for example at IETF) aim to solve this problem.
There is a difficulty in the choice of the criterion that states that a path is ˜better than another. It is a question of assigning a metric ( ˜length ) to each edge of the graph, so that the length of a path is the sum of the lengths of the branches that constitute it. Several metrics are possible, in particular:
The number of branches of the path.
The quality of each branch, in order to favour the hops of good quality because they allow the transmission of a greater information rate. Moreover, if one mechanism of retransmission is envisaged on each hop, choosing a good hop minimises the number of retransmissions and thus the delay from end to end.
One can also mix several metrics.