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.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.