Algorithms for computing message delay for wireless networks
Autor: | Hosam M. F. AboElFotoh |
---|---|
Rok vydání: | 1997 |
Předmět: |
Computational complexity theory
Computer Networks and Communications Computer science business.industry Wireless network Distributed computing End-to-end delay Network delay Graph theory Network planning and design Broadcasting (networking) Hardware and Architecture business Algorithm Time complexity Software Information Systems Computer network |
Zdroj: | Networks. 29:117-124 |
ISSN: | 1097-0037 0028-3045 |
DOI: | 10.1002/(sici)1097-0037(199703)29:2<117::aid-net6>3.0.co;2-m |
Popis: | 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 traveled 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, #P-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. |
Databáze: | OpenAIRE |
Externí odkaz: |