Ricerc@Sapienza

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.