Abstract
Dynamical connection graph changes are inherent in networks such as peer-to-peer networks, wireless ad hoc networks, and wireless sensor networks. Considering the influence of the frequent graph changes is thus essential for precisely assessing the performance of applications and algorithms on such networks. With two-fold states, stochastic hybrid systems (SHSs) can effectively model the dynamics of the execution of algorithms on a network with random and frequent graph changes. In this report, using SHSs, we analyze the performance of an epidemic-like algorithm, DRG (Distributed Random Grouping), for average aggregate computation on a wireless sensor network with dynamical graph changes. The convergence criteria and the upper bounds on the running time of the DRG algorithm for three representative types of random graph-changing models are derived. Numerical results are presented to illustrate our analysis.
Keywords
Performance Analysis, Sensor Networks, Aggregate Computation, Randomized Algorithms, Distributed
Date of this Version
September 2007