Wyszukiwarka
Abstrakt
Let G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at least one active interface. In general, every node holds a subset of all the possible k interfaces. Such networks are known as multi-interface networks. In this setting, we study two basic problems: Connectivity and Cheapest Path. The Connectivity problem corresponds to the well-known Minimum Spanning Tree problem in graph theory. In practice, we need to cover a subgraph of G of minimum cost which contains a spanning tree of G. The problem turns out to be APX-hard in general and for many restricted graph classes, however it is possible to provide approximation algorithms: a 2-approximation in general and a (2-1/k)-approximation for the unit cost interface case, i.e. when the cost of activating an interface is unitary for any interface. We also consider the problem in special graph classes, such as graphs of bounded degree, planar graphs, graphs of bounded treewidth, complete graphs. The Cheapest Path problem corresponds to the well-known Shortest Path problem in graph theory. In the multi-interfacesetting this problem is still polynomially solvable, and we point out a simple Dijsktra-based algorithm with O(k|E| + k|V| log (k +|V|)) runtime in general and O(k(|E| + |V|)) runtime for the unit cost interface case.
Cytowania
-
2 3
CrossRef
-
0
Web of Science
-
2 3
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
WIRELESS NETWORKS
nr 16,
strony 1063 - 1073,
ISSN: 1022-0038 - Język:
- angielski
- Rok wydania:
- 2010
- Opis bibliograficzny:
- Kosowski A., Navarra A., Pinotti C.: Exploiting multi-interface networks: Connectivity and Cheapest Paths // WIRELESS NETWORKS. -Vol. 16, nr. Iss. 4 (2010), s.1063-1073
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s11276-009-0188-8
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 82 razy
Publikacje, które mogą cię zainteresować
On extremal sizes of locally k-tree graphs
- M. Borowiecki,
- P. Borowiecki,
- E. Sidorowicz
- + 1 autorów