IEEE Journal of Selected Topics in Signal Processing · 2011 · 14 citations · 34 references
ComputingCommunicationComputer ScienceComputer NetworksDistributed SystemsMessage PassingConsensus AlgorithmsConsensus ProtocolsDistributed ComputingDistributed ConsensusDistributed CoordinationInterference ManagementAverage ConsensusCommunication RangeConsensus Convergence AnalysisConvergenceConvergence Rate AnalysisInterferenceNetwork InterferenceSparse Communication
We analyze the effect of interference on the convergence rate of average consensus algorithms, which iteratively compute the measurement average by message passing among nodes. It is usually assumed that these algorithms converge faster with a greater exchange of information (i.e., by increased network connectivity) in every iteration. However, when interference is taken into account, it is no longer clear if the rate of convergence increases with network connectivity. We study this problem for randomly placed consensus-seeking nodes connected through an interference-limited network. We investigate the following questions: 1) How does the rate of convergence vary with increasing communication range of every node? 2) How does this result change when every node is allowed to communicate with a few selected far-off nodes? When nodes schedule their transmissions to avoid interference, we show that the convergence speed scales with <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2-</sup> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> , where <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> is the communication range and <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> is the number of dimensions. This scaling is the result of two competing effects when increasing <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</i> : increased schedule length for interference-free transmission versus the speed gain due to improved connectivity. Hence, although one-dimensional networks can converge faster with a greater communication range despite increased interference, the two effects exactly offset one another in two-dimensions. In higher dimensions, increasing the communication range can actually degrade the rate of convergence. Our results thus underline the importance of factoring in the effect of interference in the design of distributed estimation algorithms.
34
The capacity of wireless networks
Piyush Gupta, P. R. Kumar · IEEE Transactions on Information Theory · 2000 · 8.4K citations
Stephen Boyd, Aritra Ghosh, Balaji Prabhakar et al. · IEEE Transactions on Information Theory · 2006 · 2.5K citations