Analysis of Contention-based relay selection mechanisms in autonomous multi-hop networks

A fundamental question of interest in multi-hop networks is whether routing should be done in a smaller number of longer hops, or larger number of shorter hops. However, underneath these aspects of the routing problem itself is the number of contending nodes involved in the relay selection taking place at each hop so as to realize whichever routing strategy adopted. A larger number of nodes increases the likelihood of finding an adequate relay, whereas increasing the selection overhead, and vice-versa. In this article we investigate both the expected cost (in time consumed) incurred by the relay selection strategy, and the effectiveness of the forwarding strategy (in spatial advancements) as a function of the number of the contending nodes, when using contention-based geographic forwarding (CGF) strategies to relay packets in multi-hop scenarios. In particular, probability generating functions (PGFs) are utilized to compute the distribution of contention resolution intervals (CRIs) and quantify overhead, while stochastic geometry is utilized to model topological aspects of the network and quantify expected progress. Both a totally random and an auction-based relay selection algorithms (RSAs) are studied and compared, with the advantages of the auction-based approach established analytically. From an overhead point of view, the selection of the furthest and the nearest relays are equivalent, but our results indicate that the long-hop routing approach is less sensitive to the number of contending nodes than the short-hop alternative.