Betweenness centrality in Delay Tolerant Networks: A survey

Dynamic networks, in particular Delay Tolerant Networks (DTNs), are characterized by a lack of end-to-end paths at any given instant. Because of that, DTN routing protocols employ a store-carry-and-forward approach, holding messages until a suitable node to forward them is found. But, the selection of the best forwarding node poses a considerable challenge. Additional network information (static or dynamic) can be leveraged to aid routing protocols in this troublesome task. One could use centrality metrics, therefore providing means to differentiate the importance of nodes in the network. Among these metrics, betweenness centrality is one of the most prominent, as it measures the degree to which a vertex is in a position of brokerage by summing up the fraction of shortest paths between other pairs of vertices passing through it. So, in this paper, betweenness centrality is surveyed, that is, its definitions and variants in static and dynamic networks are presented. Also, a survey of standard algorithms used to compute the metric (exact and approximate) is presented. Finally, a survey and a discussion on how DTN routing protocols make use of the betweenness centrality metric and algorithms to aid message forwarding is also presented.