Algorithms for computing message delay for wireless networks

In this paper, we consider the problem of computing the expected message delay in a wireless network where nodes are subject to random failures. The failure of one or more nodes in the network may increase the number of repeaters the message has to go through before reaching its destination. Therefore, the message delay varies depending on the number of hops travelled by the message. One of the important network design parameters is the expected (average) delay between a given source-and-destination pair in an operational network. Given an estimation of the failure probabilities of the nodes, we use a probabilistic graph to model arbitrary wireless networks. We show that the problem of computing the expected message delay is computationally intractable for arbitrary networks, in particular, NP-hard. We present two algorithms for computing the expected message delay for arbitrary networks. These two algorithms require a time exponential in the number of nodes in the network. We also consider two special cases where efficient (polynomial time) algorithms are developed.