A Prim-Dijkstra Algorithm for Multi-Hop Calibration of Networked Embedded Systems

The development of large scale systems of networked embedded devices with sensing capabilities relies on the availabil- ity of low-cost and resource-constrained components However, the reduced precision and accuracy of low-cost sensors on board of low-power platforms risks to impair the overall reliability of these systems, thus preventing their potential diffusion, especially in deployments with several (e.g. hundreds or more) nodes. Hence, ensuring the required quality of measurements along the lifetime of a sensor network represents a key challenge, which is often tackled also by means of calibration techniques. In this article we propose a novel approach to multi-hop calibration, targeting the derivation of a spanning tree that encompasses the optimisation of a bi-objective problem. Indeed, since minimum spanning trees can be related to the energy budget of a network and shortest path trees can be used as a model for the minimisation of the cumulative calibration errors, the search for a spanning tree that simultaneously optimises the two metrics represents a useful direction towards the design of effective and efficient calibration strategies. To this aim, we introduce a method based on the Prim-Dijkstra algorithm, which represents an effective heuristics for effective search of solutions that could represent a trade-off between the accuracy of multi-hop calibration and the energy expenditure needed to calibrate sensors. The proposed approach allows fast derivation of different solutions by means of a single parameter, thus enabling the efficient exploration of the design space even in large scale scenarios as confirmed by numerical results obtained for validation.