We consider the problem of controlling the motion of a set of robots to ferry messages between a given set of statically-placed nodes. The design and analysis of an arrivalrate unaware throughput-optimal policy for this problem is challenging because of the coupling between position and link rate. We propose a fine-grained backpressure message ferrying algorithm (FBMF) for joint motion and transmission control of robots. Unlike traditional backpressure settings, because the controlled motion of the relay nodes changes the channel rates, it turns out that the conventional approach to prove throughput optimality does not work in this problem setting. We prove for the simplest setting (single-flow, single-robot, constant arrival) that this policy indeed achieves throughput optimality. The analysis reveals that under feasible traffic, even when queues are highly over-loaded, the change in the total queue size can be positive over a time step, nevertheless the system exhibits a limit-cycle behavior and stability holds because the change in the total queue size is negative over the cycle for sufficiently large queues. We pose the design and analysis of a throughput optimal policy for the general case as a challenging open problem for network theory.

Gasparri, A., & Krishnamachari, B. (2014). Throughput-optimal robotic message ferrying for wireless networks using backpressure control. In Proceedings - 11th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2014 (pp.488-496). Institute of Electrical and Electronics Engineers Inc. [10.1109/MASS.2014.105].

Throughput-optimal robotic message ferrying for wireless networks using backpressure control

Gasparri, Andrea;
2014

Abstract

We consider the problem of controlling the motion of a set of robots to ferry messages between a given set of statically-placed nodes. The design and analysis of an arrivalrate unaware throughput-optimal policy for this problem is challenging because of the coupling between position and link rate. We propose a fine-grained backpressure message ferrying algorithm (FBMF) for joint motion and transmission control of robots. Unlike traditional backpressure settings, because the controlled motion of the relay nodes changes the channel rates, it turns out that the conventional approach to prove throughput optimality does not work in this problem setting. We prove for the simplest setting (single-flow, single-robot, constant arrival) that this policy indeed achieves throughput optimality. The analysis reveals that under feasible traffic, even when queues are highly over-loaded, the change in the total queue size can be positive over a time step, nevertheless the system exhibits a limit-cycle behavior and stability holds because the change in the total queue size is negative over the cycle for sufficiently large queues. We pose the design and analysis of a throughput optimal policy for the general case as a challenging open problem for network theory.
9781479960354
Gasparri, A., & Krishnamachari, B. (2014). Throughput-optimal robotic message ferrying for wireless networks using backpressure control. In Proceedings - 11th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2014 (pp.488-496). Institute of Electrical and Electronics Engineers Inc. [10.1109/MASS.2014.105].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/332633
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact