• Calendar

March 28, Wednesday
14:30 – 16:00

The problem that is addressed in the talk is connecting a collection of agents that are randomly placed in a rectangular area in the plane or 3D space by a wireless network in a way that minimizes the sum of the powers of the agents' transmitters. Depending on a variant, the problem is proved or believed to be NP-hard. Known approximation algorithms use computing means and/or information that is usually not available in practice (e.g., knowledge of the whole network globally available, positions of agents known). Standard power allocation algorithms like unit (uniform) disk model or k-th nearest neighbor graph are provably asymptotically inefficient when applied to a random set of agents

The first result of the talk is a distributed algorithm that provably achieves almost surely a result that is optimal up to a multiplicative constant. However, while being a perfect solution of a problem of constuction of a connected network, a network built by the algorithm mentioned in the previous paragraph is not well suited for communication - it is similar to a minimum spanning tree and hence many physically close pairs of nodes are connected by a very long path in a network (high stretch factor), which causes important congestion in a network. The second part of the talk shows that connectivity of a network can be substantially improved while not increasing the total transmit power too much by inserting a certain number of bridges - direct connections of high stretch factor pairs of nodes.