We present a simple model, called depleatable channels, of multi-hop communication in ad hoc networks. We introduce a model for channel energy consumption, and we propose a notion of channel equivalence based on the communication service they provide, regardless of specific routing protocols. In particular, we consider equivalent two channels with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence, and variants of it, coincide with standard equivalences borrowed from the theory of concurrency. Unfortunately, while the maximum flow can be computed in polynomial time, calculating the value of a minimum inhibiting flow is NP-hard. Thus, we propose a characterization of those graphs, called weak, which admit charge assignments for which the minimum inhibiting flow is strictly less than the maximum flow and show that weakness can be checked efficiently by providing an algorithm that does so in polynomial time.
Depletable channels: dynamics, behaviour, and efficiency in network design / Cenciarelli, Pietro; Gorla, Daniele; Salvo, Ivano. - In: ACTA INFORMATICA. - ISSN 0001-5903. - (2018). [10.1007/s00236-018-0329-6]
Depletable channels: dynamics, behaviour, and efficiency in network design
Cenciarelli, Pietro;Gorla, Daniele;Salvo, Ivano
2018
Abstract
We present a simple model, called depleatable channels, of multi-hop communication in ad hoc networks. We introduce a model for channel energy consumption, and we propose a notion of channel equivalence based on the communication service they provide, regardless of specific routing protocols. In particular, we consider equivalent two channels with identical maximum and minimum inhibiting flow, and prove that this notion of equivalence, and variants of it, coincide with standard equivalences borrowed from the theory of concurrency. Unfortunately, while the maximum flow can be computed in polynomial time, calculating the value of a minimum inhibiting flow is NP-hard. Thus, we propose a characterization of those graphs, called weak, which admit charge assignments for which the minimum inhibiting flow is strictly less than the maximum flow and show that weakness can be checked efficiently by providing an algorithm that does so in polynomial time.File | Dimensione | Formato | |
---|---|---|---|
Cenciarelli_depletable_2018.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.62 MB
Formato
Adobe PDF
|
1.62 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.