Analysis of Hop Limit in Opportunistic Networks by Static and Time-Aggregated Graphs

Hop count limitation helps controlling the spread
of messages as well as the protocol complexity and overhead
in a distributed network. For a mobile opportunistic network,
we examine how the paths between any two nodes change with
increasing number of hops a message can follow. Using the all
hops optimal path (AHOP) problem, we represent the total delay
of a route from a source node to a destination node as additive
weight and use the number of encounters as a representation
of bottleneck weight. First, we construct a static (contact) graph
from the meetings recorded in a human contact trace and then
analyze the change in these two weights with increasing hop
count. Alternatively, we aggregate all the contact events in a
time interval and construct several time-aggregated graphs over
which we calculate the capacity metrics. Although, we observe
differences in the properties of the static and the time-aggregated
graphs (e.g., higher connectivity and average degree in static
graph), our analysis shows that second hop brings most of the
benefits of multi-hop routing for the studied networks. However,
the optimal paths —path that provides the most desirable
bottleneck/additive weight— are achieved at further hops, e.g,
hop count ≈ 4. Our finding, which is also verified by simulations,
is paramount as it puts an upper bound on the hop count for
the hop-limited routing schemes by discovering the optimal hop
count for both additive and bottleneck weights.