An Analytic Latency Model for a Next-Hop Data-Ferrying Swarm on Random Geometric Graphs

Abstract

Next-hop data-ferrying is a data-driven approach to ferrying data between graph components of a disconnected network. In contrast to pre-planned routing methods like the Traveling Salesman tour, only the next-hop is planned, allowing the ferry to be reactive to the data flows within the network. When multiple ferries are used, explicit coordination between them is difficult due to the data-driven approach of the algorithm, and the distributed and disconnected nature of the problem. However, coordinated behavior can still be produced through swarm intelligent means and while this is a useful pragmatic result, mathematical models describing system properties are difficult to develop. This generally results in algorithm correctness being demonstrated through simulation. In this article, we describe the development of a mathematical model of such a next-hop ferrying swarm. We show that the closed-form expression for user data latency is a close match to simulation results for Random Geometric Graphs under the assumption of a zero expected degree. In non-zero degree graphs, a near constant offset between the model and simulation is observed.

Keywords

• Data ferrying
• emergent behavior
• MANET
• random geometric graph