Distributed Estimation of the Degree Distribution in Wireless Sensor Networks

Published on Dec 1, 2016 in GLOBECOM (Global Communications Conference)
· DOI :10.1109/GLOCOM.2016.7841740
Sai Zhang7
Estimated H-index: 7
(ASU: Arizona State University),
Jongmin Lee6
Estimated H-index: 6
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias32
Estimated H-index: 32
A distributed consensus algorithm for estimating the degree distribution of a graph is proposed. The proposed algorithm is based on average consensus and in-network empirical mass function estimation. It is fully distributed in the sense that each node in the network only needs to know its own degree, and nodes do not need to be labeled. The algorithm works for any connected graph structure in the presence of communication noise. The performance of the algorithm is analyzed. A discussion on how the properties of the graph degree distribution can be exploited for post-processing after consensus is reached is given. Simulation results corroborating the theory are also provided.
📖 Papers frequently viewed together
9 Citations
4 Authors (Lin Luo, ..., Qi Yang)
2 Citations
13 Citations
#1Xiangrong Wang (TU Delft: Delft University of Technology)H-Index: 7
#2Stojan Trajanovski (TU Delft: Delft University of Technology)H-Index: 12
Last. Piet Van Mieghem (TU Delft: Delft University of Technology)H-Index: 44
view all 4 authors...
Topological characteristics of links of complex networks influence the dynamical processes executed on networks triggered by links, such as cascading failures triggered by links in power grids and epidemic spread due to link infection. The line graph transforms links in the original graph into nodes. In this paper, we investigate how graph metrics in the original graph are mapped into those for its line graph. In particular, we study the degree distribution and the assortativity of a graph and i...
10 CitationsSource
#1Yaonan Zhang (BU: Boston University)H-Index: 2
#2Eric D. Kolaczyk (BU: Boston University)H-Index: 36
Last. Bruce D. SpencerH-Index: 17
view all 3 authors...
Networks are a popular tool for representing elements in a system and their interconnectedness. Many observed networks can be viewed as only samples of some true underlying network. Such is frequently the case, for example, in the monitoring and study of massive, online social networks. We study the problem of how to estimate the degree distribution – an object of fundamental interest – of a true underlying network from its sampled network. In particular, we show that this problem can be formula...
35 CitationsSource
#1Catherine A. Bliss (UVM: University of Vermont)H-Index: 7
#2Christopher M. Danforth (UVM: University of Vermont)H-Index: 27
Last. Peter Sheridan Dodds (UVM: University of Vermont)H-Index: 36
view all 3 authors...
Complex networks underlie an enormous variety of social, biological, physical, and virtual systems. A profound complication for the science of complex networks is that in most cases, observing all nodes and all network interactions is impossible. Previous work addressing the impacts of partial network data is surprisingly limited, focuses primarily on missing nodes, and suggests that network statistics derived from subsampled data are not suitable estimators for the same network statistics descr...
28 CitationsSource
Apr 7, 2014 in WWW (The Web Conference)
#1Anirban Dasgupta (IITGN: Indian Institute of Technology Gandhinagar)H-Index: 31
#1Anirban Dasgupta (IITGN: Indian Institute of Technology Gandhinagar)H-Index: 77
Last. Tamas Sarlos (Google)H-Index: 20
view all 3 authors...
Networks are characterized by nodes and edges. While there has been a spate of recent work on estimating the number of nodes in a network, the edge-estimation question appears to be largely unaddressed. In this work we consider the problem of estimating the average degree of a large network using efficient random sampling, where the number of nodes is not known to the algorithm. We propose a new estimator for this problem that relies on access to node samples under a prescribed distribution. Nex...
45 CitationsSource
Dec 1, 2013 in CDC (Conference on Decision and Control)
#1Håkan TereliusH-Index: 6
#2Damiano VaragnoloH-Index: 17
Last. Karl Henrik JohanssonH-Index: 92
view all 4 authors...
The aggregation and estimation of values over networks is fundamental for distributed applications, such as wireless sensor networks. Estimating the average, minimal and maximal values has already been extensively studied in the literature. In this paper, we focus on estimating empirical distributions of values in a network with anonymous agents. In particular, we compare two different estimation strategies in terms of their convergence speed, accuracy and communication costs. The first strategy...
6 CitationsSource
May 26, 2013 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
#1Joya A. Deri (CMU: Carnegie Mellon University)H-Index: 5
#2Jose M. F. Moura (CMU: Carnegie Mellon University)H-Index: 81
Online social networks and the World Wide Web lead to large underlying graphs that might not be completely known because of their size. To compute reliable statistics, we have to resort to sampling the network. In this paper, we investigate four network sampling methods to estimate the network degree distribution and the so-called biased degree distribution of a 3.7 million wireless subscriber network. We measure the quality of our estimates of the degree distributions by using the Kolmogorov-Sm...
5 CitationsSource
Jan 1, 2013 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 4 authors...
A distributed consensus algorithm for estimating the maximum and the minimum of the initial measurements in a sensor network is proposed. Estimating extrema is useful in many applications such as temperature control. In the absence of communication noise, max estimation can be done by updating the state value with the largest received measurements in every iteration at each sensor. In the presence of communication noise, however, the maximum estimate may incorrectly drift to a larger value at ea...
12 CitationsSource
#1Franck Iutzeler (ENST: Télécom ParisTech)H-Index: 13
#2Philippe Ciblat (ENST: Télécom ParisTech)H-Index: 30
Last. J. Jakubowicz (Telecom SudParis)H-Index: 2
view all 3 authors...
In this paper, we address the problem of estimating the maximal value over a sensor network using wireless links between them. We introduce two heuristic algorithms and analyze their theoretical performance. More precisely, i) we prove that their convergence time is finite with probability one, ii) we derive an upper-bound on their mean convergence time, and iii) we exhibit a bound on their convergence time dispersion.
87 CitationsSource
Jun 21, 2010 in ICDCS (International Conference on Distributed Computing Systems)
#1Jan Sacha (VU: VU University Amsterdam)H-Index: 10
#2Jeff Napper (VU: VU University Amsterdam)H-Index: 5
Last. Guillaume Pierre (VU: VU University Amsterdam)H-Index: 25
view all 4 authors...
To enable decentralised actions in very large distributed systems, it is often important to provide the nodes with global knowledge about the values of attributes across all nodes. This paper shows how, given an attribute whose values are distributed across a large decentralised system, each node can efficiently estimate the statistical distribution of these values. Simulations using heavily skewed real-world node attribute distributions show that our estimation methods outperform the state-of-t...
34 CitationsSource
May 23, 2010 in ICC (International Conference on Communications)
#1Christian Bettstetter (AAU: Alpen-Adria-Universität Klagenfurt)H-Index: 49
#2Johannes Klinglmayr (AAU: Alpen-Adria-Universität Klagenfurt)H-Index: 8
Last. Stefan Lettner (AAU: Alpen-Adria-Universität Klagenfurt)H-Index: 7
view all 3 authors...
In performance evaluations of communication and computer networks the underlying topology is sometimes modeled as a random graph. To avoid unwanted side effects, some researchers force the simulated topologies to be connected. Consequently, the resulting distribution of the node degrees does then no longer correspond to that of the underlying random graph model. Being not aware of this change in the degree distribution might result in a simulation pitfall. This paper addresses the question as to...
15 CitationsSource
Cited By3
#1Sameeksha Katoch (ASU: Arizona State University)H-Index: 4
#2Gowtham Muniraju (ASU: Arizona State University)H-Index: 6
Last. Devarajan SrinivasanH-Index: 7
view all 8 authors...
This paper describes three methods used in the development of a utility-scale solar cyber-physical system. The study describes remote fault detection using machine learning approaches, power output optimization using cloud movement prediction and consensus-based solar array parameter estimation. Dynamic cloud movement, shading and soiling, lead to fluctuations in power output and loss of efficiency. For optimization of output power, a cloud movement prediction algorithm is proposed. Integrated f...
11 CitationsSource
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
Last. Mahesh K. Banavar (Clarkson University)H-Index: 17
view all 4 authors...
Abstract The area of detection and estimation in a distributed wireless sensor network (WSN) has several applications, including military surveillance, sustainability, health monitoring, and Internet of Things (IoT). Compared with a wired centralized sensor network, a distributed WSN has many advantages including scalability and robustness to sensor node failures. In this book, we address the problem of estimating the structure of distributed WSNs. First, we provide a literature review in: (a) g...
5 Citations
#1Sai ZhangH-Index: 7
1 Citations