Computer Science – Information Theory
Scientific paper
2006-06-12
Computer Science
Information Theory
Submitted for Journal publication
Scientific paper
Let $N$ local decision makers in a sensor network communicate with their neighbors to reach a decision \emph{consensus}. Communication is local, among neighboring sensors only, through noiseless or noisy links. We study the design of the network topology that optimizes the rate of convergence of the iterative decision consensus algorithm. We reformulate the topology design problem as a spectral graph design problem, namely, maximizing the eigenratio~$\gamma$ of two eigenvalues of the graph Laplacian~$L$, a matrix that is naturally associated with the interconnectivity pattern of the network. This reformulation avoids costly Monte Carlo simulations and leads to the class of non-bipartite Ramanujan graphs for which we find a lower bound on~$\gamma$. For Ramanujan topologies and noiseless links, the local probability of error converges much faster to the overall global probability of error than for structured graphs, random graphs, or graphs exhibiting small-world characteristics. With noisy links, we determine the optimal number of iterations before calling a decision. Finally, we introduce a new class of random graphs that are easy to construct, can be designed with arbitrary number of sensors, and whose spectral and convergence properties make them practically equivalent to Ramanujan topologies.
Aldosari Saeed
Kar Soummya
Moura Jose M. F.
No associations
LandOfFree
Topology for Distributed Inference on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Topology for Distributed Inference on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topology for Distributed Inference on Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647774