Analysis of Distributed Random Grouping for aggregate computation on wireless sensor networks with randomly changing graphs

作     者：Chen, Jen-Yeu Hu, Jianghai 

作者机构：Natl Dong Hwa Univ Dept Elect Engn Hualien 97401 Taiwan Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA 

出 版 物：《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》 (IEEE Trans Parallel Distrib Syst)

年 卷 期：2008年第19卷第8期

页      面：1136-1149页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：US National Science Foundation, (CNS-0643805) Purdue Research Foundation 

主　　题：performance analysis aggregate computation sensor networks randomized algorithms distributed algorithms stochastic hybrid systems graph theory 

摘      要：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. In this paper, using stochastic hybrid systems (SHSs), we model the dynamics and analyze the performance of an epidemic-like algorithm, Distributed Random Grouping (DRG), for average aggregate computation on a wireless sensor network with dynamical graph changes. Particularly, we derive the convergence criteria and the upper bounds on the running time of the DRG algorithm for a set of graphs that are individually disconnected but jointly connected in time. An effective technique for the computation of a key parameter in the derived bounds is also developed. Numerical results and an application extended from our analytical results to control the graph sequences are presented to exemplify our analysis.