The need for larger, mobile, and dynamic networks--such as modern mobile ad hoc networks (MANETs)--is growing. Maintaining MANETs’ end-to-end routes at all times is not always guaranteed, due to node mobility, different capabilities, energy conservation, and wireless link vulnerability. Hence, a new “store-carry-and-forward” (SCF) routing protocol is utilized over self-organizing delay-tolerant networks to alleviate existing MANET deficiencies. In such SCF delay-tolerant networks, mobile nodes carry packets until passing them to other suitable relay carrying nodes, otherwise discarding them. The nodes carrying messages are chosen based on some sophisticated node centrality metrics.
The paper extensively surveys the routing of delay-tolerant networks using dynamic (for example, nodes’ location, traffic, and encounter information) and static (for example, social nodes’ relations) network information. Centrality metrics, mainly betweenness centrality, are also considered the most used metrics in social and complex networks. Betweenness centrality has many metrics to measure the relay nodes’ brokerage effectiveness--namely, shortest paths, flow, current flow, random walk, and ego--for static and dynamic networks. The paper also surveys variants of betweenness centrality such as canonical path, e-betweenness, bounded-distance, distance-scaled, a-weight, and k-path betweenness; all are based on shortest path except the k-path, which is based on random walk. Betweenness centrality requires O(n3) time and O(n2) space complexities (where n is the network’s nodes), so exact and approximate algorithms (with the latter subdivided into random, adaptive, and local sampling) are introduced to alleviate them. Since the delay-tolerant networks’ routing protocols face the challenge of finding a node to forward messages to, especially if packets require guaranteed delivery and low end-to-end delay, various routing protocols are surveyed: deterministic/scheduled (source-destination information is known a priori), enforced (deliver messages to disconnected parts of a network over ferries’ mobile nodes), and opportunistic (including greedy, controlled, and utility-based).
The authors also review resource allocation delay-tolerant network routing, where selecting a node is based on its pre-allocated resources and social-oblivious/social-aware schemes. The social-oblivious scheme applies random diffusion of relocated messages for better chances of delivery, whereas the social-aware scheme applies probabilistic delivery to a node with two sub-types/schemes: self-reported (using nodes’ a priori known social information) or detected (with real-time online social information retrieval). Social-based routing delay-tolerant network protocols are discussed according to their social characteristic effect: positive (boosting routing performance) or negative (nodes selfishly maximize their use as a carrying node).
This paper is the first to carry out an in-depth survey of the use of betweenness centrality metrics--including the concept, variants, and standard algorithms (exact and approximate)--to compute metrics’ values, while reducing the high time/space computation complexity. Another major contribution is the very solid scientific discussion of the challenges of routing over delay-tolerant networks, with protocols that boost their packets’ forwarding.
