Highly Scalable Aggregate Computations in Cyber-Physical Systems: Physical Environment Meets Communication Protocols
Eduardo Tovar, Björn A. Andersson, Nuno Pereira, Mário Alves, K. Shashi Prabh, Filipe Pacheco · 2008
In this paper, we focus on large-scale and dense Cyber-Physical Systems, and discuss methods that tightly integrate communication and computing with the underlying physical environment. We present Physical Dynamic Priority Dominance ((PD) 2) protocol that exemplifies a key mechanism to devise low time-complexity communication protocols for large-scale networked sensor systems. We show that using this mechanism, one can compute aggregate quantities such as the maximum or minimum of sensor readings in a time-complexity that is equivalent to essentially one message exchange. We also illustrate the use of this mechanism in a more complex task of computing the interpolation of smooth as well as non-smooth sensor data in very low timecomplexity. 1.