University of Cambridge > > Optimization and Incentives Seminar > Distributed Computation over Random Geometric Graphs: Some Asymptotic Results

Distributed Computation over Random Geometric Graphs: Some Asymptotic Results

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Neil Walton.

The problem setting is motivated by applications in wireless sensor networks. $n$ nodes are assumed distributed uniformly in the unit square. Node $i$ has data $x_i.$ The objective is to obtain $f(x_1,\ldots, x_n).$ The nodes communicate over a wireless communication channel and form a multihop radio network. Spatial reuse is determined by the protocol model.

An overview of the results for noisefree, organized networks and a summary of our results on networks with noisy links is first provided. Two variations to the basic model are considered. First, a method to compute a probably approximately correct (PAC) histogram of observations with a refresh rate of $\Theta(1)$ time units per histogram sample is described. This is then extended to a network with noisy links with the same refresh rate. This refresh rate for PAC that of $\Theta(1/\log n)$ for exact computation in noisy networks. The improvement is achieve by operating in the super-critical thermodynamic regime where the transmission range is smaller, leading to an increased spatial reuse. Computation is over a giant components rather than over a connected network.

Second, we motivate and develop the notion of structure-free networks and analyse them. In these networks, nodes do not have an identity or a sense of time. Thus traditional `organized’ protocols cannot be used here and we resort to an Aloha MAC with local computation. We describe the performance of this network to compute the MAX and the histogram. Here, links are assumed noisefree.

This talk is part of the Optimization and Incentives Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity