Scenarios like wireless network networks, Internet of Things, and pervasive computing, promote full distribution of computation as well as opportunistic, peer-to-peer interactions between devices spread in the environment. In this context, computing estimated distances between devices in the network is a key component, commonly referred to as the gradient self-organisation pattern: it is frequently used to broadcast information, forecast pointwise events, as carrier for distributed sensing, and as combinator for higher-level spatial structures. However, computing gradients is very problematic in an environment affected by mutability in the position and working frequency of devices: existing algorithms fail in reaching adequate trade-offs between accuracy and reaction speed to environment changes. We propose BIS (Bounded Information Speed) gradient, a fully-distributed algorithm that uses time information to achieve a smooth and predictable reaction speed, and prove it is optimal across algorithms following a single-path-communication strategy to spread information. We empirically evaluate BIS gradient and compare it with other approaches, showing that BIS achieves the best accuracy while keeping smoothness under control, and accordingly provides improved performance when used as building block in more complex algorithms for creating spatial structures and performing distributed collection of data.

Optimal single-path information propagation in gradient-based algorithms

Audrito, Giorgio;Damiani, Ferruccio;
2018-01-01

Abstract

Scenarios like wireless network networks, Internet of Things, and pervasive computing, promote full distribution of computation as well as opportunistic, peer-to-peer interactions between devices spread in the environment. In this context, computing estimated distances between devices in the network is a key component, commonly referred to as the gradient self-organisation pattern: it is frequently used to broadcast information, forecast pointwise events, as carrier for distributed sensing, and as combinator for higher-level spatial structures. However, computing gradients is very problematic in an environment affected by mutability in the position and working frequency of devices: existing algorithms fail in reaching adequate trade-offs between accuracy and reaction speed to environment changes. We propose BIS (Bounded Information Speed) gradient, a fully-distributed algorithm that uses time information to achieve a smooth and predictable reaction speed, and prove it is optimal across algorithms following a single-path-communication strategy to spread information. We empirically evaluate BIS gradient and compare it with other approaches, showing that BIS achieves the best accuracy while keeping smoothness under control, and accordingly provides improved performance when used as building block in more complex algorithms for creating spatial structures and performing distributed collection of data.
2018
166
146
166
https://www.sciencedirect.com/science/article/pii/S0167642318302387?via%3Dihub
https://doi.org/10.1016/j.scico.2018.06.002
Aggregate programming; Gradient; Information speed; Reliability; Spatial computing; Software
Audrito, Giorgio; Damiani, Ferruccio; Viroli, Mirko
File in questo prodotto:
File Dimensione Formato  
SCP-2018-Audrito-et-al.pdf

Accesso riservato

Descrizione: Ariticolo principale
Tipo di file: PDF EDITORIALE
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
main.pdf

Open Access dal 29/06/2020

Descrizione: Ariticolo principale
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 896.33 kB
Formato Adobe PDF
896.33 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/2318/1671326
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 13
social impact