**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Wireless Network Simplification: The Gaussian N-Relay Diamond Network

Abstract

We consider the Gaussian N-relay diamond network, where a source wants to communicate to destination node through a layer of N-relay nodes. We investigate the following question: what fraction of the capacity can we maintain using only k out of the N available relays? We show that independent of the channel configurations and operating SNR, we can always find a subset of k relays, which alone provide a rate k/(k + 1)(C) over bar - G, where (C) over bar is the information theoretic cutset upper bound on the capacity of the whole network and G is independent of the channel coefficients and the SNR and depends only on N and k (logarithmic in N and linear in k). In particular, for k = 1, this means that half of the capacity of any N-relay diamond network can be approximately achieved by routing information over a single relay. We also show that this fraction is tight: there are configurations of the N-relay diamond network, where every subset of k relays alone can at most provide approximately a fraction k/(k + 1) of the total capacity. These high-capacity k-relay subnetworks can be also discovered efficiently. We propose an algorithm that computes a constant gap approximation to the capacity of the Gaussian N-relay diamond network in O(N log N) running time and discovers a high-capacity k-relay subnetwork in O(kN) running time. This result also provides a new approximation to the capacity of the Gaussian N-relay diamond network, which is hybrid in nature: it has both multiplicative and additive gaps. In the intermediate SNR regime, this hybrid approximation is tighter than existing purely additive or purely multiplicative approximations to the capacity of this network.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related MOOCs (7)

Related concepts (34)

Related publications (49)

Ontological neighbourhood

Digital Signal Processing I

Basic signal processing concepts, Fourier analysis and filters. This module can
be used as a starting point or a basic refresher in elementary DSP

Digital Signal Processing II

Adaptive signal processing, A/D and D/A. This module provides the basic
tools for adaptive filtering and a solid mathematical framework for sampling and
quantization

Digital Signal Processing III

Advanced topics: this module covers real-time audio processing (with
examples on a hardware board), image processing and communication system design.

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.

Distance-vector routing protocol

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers using a distance-vector protocol exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information.

Network topology

Network topology is the arrangement of the elements (links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and control radio networks, industrial fieldbusses and computer networks. Network topology is the topological structure of a network and may be depicted physically or logically. It is an application of graph theory wherein communicating devices are modeled as nodes and the connections between the devices are modeled as links or lines between the nodes.

Patrick Thiran, Sébastien Christophe Henri

In recent years, multipath routing, i.e., employing several paths simultaneously, has emerged as an efficient way to provide significant throughput gains in local networks. This has been observed both with technologies that are not subject to interference, ...

Patrick Thiran, Sébastien Christophe Henri

In recent years, multipath routing, i.e., employing several paths simultaneously, has emerged as an efficient way to provide significant throughput gains in local networks. This has been observed both with technologies that are not subject to interference, ...

2018Dario Floreano, Bixio Rimoldi, Stefano Rosati, Grégoire Hilaire Marie Heitz, Karol Jacek Kruzelecki

This paper reports experimental results on self-organizing wireless networks carried by small flying robots. Flying ad hoc networks (FANETs) composed of small unmanned aerial vehicles (UAVs) are flexible, inexpensive and fast to deploy. This makes them a v ...