On the Design and Analysis of Fair Contact Plans in Predictable Delay-Tolerant Networks

Abstract

Delay-tolerant networks (DTNs) have become a promising architecture for wireless sensor systems in challenged communication environments where traditional solutions based on persistent connectivity either fail or show serious weaknesses. As a result, different routing schemes have been investigated that take into account the time-evolving nature of the network topology. Among them, contact graph routing has been proposed for space environments with predictable connectivity. In order to evaluate routing decisions, DTN nodes need to know the contact plan in advance, which comprises all communication links among nodes that will be available in the future. Since not all potential contacts can belong to the contact plan, its design requires analyzing conflicting contacts in order to select those that meet an overall goal. In this paper, we consider the design of contact plans that can maximize fairness requirements while still maximizing the overall capacity as well. To this end, we propose to formalize the problem by means of an optimization model and evaluate its performance in terms of different fairness metrics. Since this model can be computationally intractable for a large number of contacts, we also propose to tackle it as a matching problem, resulting in algorithms of polynomial complexity, and compare these results with those of the original model. We show that fairness can be properly modeled to design contact plans and that efficient algorithms do exist to compute these plans quite accurately while also improving overall network routing metrics for a proposed case study.