On a Routing Problem within Probabilistic Graphs
Chunming Qiao, Seokhoon Yoon, Hung Quang Ngo, Joy Ghosh · 2006
Our problem formulation is as follows. Given a probabilistic graph G and routing algorithm A, we wish to determine a delivery subgraph G[A] of G with at most k edges, such that the probability Conn2(G[A]) that there is a path from source s to destination t in a graph H chosen randomly from the probability space defined by G[A] is maximized. To the best of our knowledge, this problem and its complexity has not been addressed in the literature. Also, there is the corresponding distributed version of the problem where the delivery subgraph G[A] is to be constructed distributively, yielding a routing protocol. Our proposed solution to this routing problem is multi-fold: First, we prove the hardness of our optimization problem of finding a delivery subgraph that maximizes the delivery probability and discuss the hardness of computing the objective function Conn2(G[A]) (which is not the hardness of Conn2(G[A]) itself); Second, we present an algorithm to approximate Conn2(G[A]) and compare it with an optimal algorithm; Third, we model mobility using a Semi-Markov Chain to estimate the pairwise user contact probabilities; and Fourth, we propose an edgeconstrained routing protocol (EC-SOLAR-KSP) for intermittently connected networks based on the insights obtained from the first step and the contact probabilities computed in the third step. We then highlight the protocol’s novelty and effectiveness by comparing it with a probabilistic routing protocol, and an epidemic routing protocol proposed in literature for intermittently connected networks.