The power of quasi-shortest paths and the impact of node mobility on dynamic networks

Abstract

The objective of this thesis is to investigate three important aspects of dynamic networks: the impact of node mobility on multihop data transmission, the effect of the use of longer paths on the relative importance of nodes and the performance of the network in the presence of failure on central nodes. To analyze the first aspect, this work proposes the (κ, λ)-vicinity, which extends the traditional vicinity to consider as neighbors nodes at multihop distance and restricts the link establishment according to the relative speed between nodes. This proposal is used later on the development of three forwarding strategies. The relative speed restriction imposed on these strategies results in significant reduction of resources consumption, without incurring significant impact on the average packet delivery ratio. To analyze the second aspect, we propose the ρ-geodesic betweenness centrality, which uses shortest and quasi-shortest paths to quantify the relative importance of a node. The quasishortest paths are limited by a spreadness factor, ρ. The use of non-optimal paths causes the reranking of several nodes and its main effect is a reduced occupation of the most central positions by articulation points. Lastly, the network performenace in presence of failures is investigated through simulations, in which failures happen on nodes defined as the most central according to distinct centrality metrics. The result is a severe reduction of the average network throughput, and it is independent of the metric used to determine which nodes are the most central. The major strength of the proposed metric, then, is that, despite the severe reduction of the throughput, there is a high probability of maintaining the network connected after a failure, because it is unlikely that a failing node in the most central position is also an articulation point.