Establishing connectivity among disjoint terminals using a mix of stationary and mobile relays

In multiple application scenarios, need arises to connect a set of disjoint nodes or segments. Examples include connecting a sparsely located data sources, repairing a partitioned network topology after failure, and federating a set of standalone networks to serve an emerging event. Contemporary solutions either deploy stationary relay nodes (RN) to form data paths or employ one or multiple mobile data carriers (MDCs) that pick packets from sources and transport them to destinations. In this paper we investigate the interconnection problem when the number of available RNs is insufficient for forming a stable topology and a mix of RNs and MDCs is to be used. We present a novel algorithm for determining where the RNs are to be placed and planning optimized travel paths for the MDCs so that the data delivery latency as well as the MDC motion overhead are minimized. The performance of the algorithm is validated through simulation.