Resource Constrained Wireless Networks

Wireless networks are characterized by limited resources (energy, bandwdith) and complex signal interactions due to the wireless broadcasting nature. Our approach utilizes the broadcasting capabilities to advantage for network coding rather than mitigating it. For example, we have shown that network coding can inherently use the broadcast nature to make every transmission maximally useful in reciprocated communications. This property can be realized though decentralized algorithms suitable for even dynamically changing networks. These ideas for information exchange naturally lead to questions about other traffic demand patterns and connect due to the increased energy efficiency they offer to sensor networks. The use of feedback with broadcast network codes can significantly reduce delay in delivery, and offer mechanisms to achieve fairness among competing users. Therefore the role of feedback with wireless network coding is a topic that we plan to explore further.

The deterministic approach proposed by Avestimehr, Diggavi and Tse shows that a simple linear deterministic model approximately captures the interference limited regime of wireless networks. Using this approach they proved an information theoretic min-cut max-flow result using exponential complexity processing at network nodes. We have developed a Ford-Fulkerson like polynomial time algorithm that provably achieves the capacity. The impact of this algorithm is to develop provably computationally efficient wireless network information flow algorithms. Translating these ideas to noisy Gaussian networks using lattice codes is part of our ongoing work. We are extending these combinatorial methods for other wireless network flow instances of relay-interference networks. These ideas open up fundamentally new network algorithm questions which are both rich in theoretical questions as well as practical insights.

Selected Publications

A PHP Error was encountered

Severity: Warning

Message: Creating default object from empty value

Filename: gettext/gettext.inc

Line Number: 195

  1. J. Ebrahimi and C. Fragouli, Combinatorial algorithms for wireless information flow, ACM Transactions on Algorithms, 2011
    Download:  
    Citation: BibTeX RIS
    A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
  2. S. Mohajer, S. N. Diggavi, C. Fragouli and D. Tse, Capacity of deterministic Z-chain relay-interference network, in IEEE Information Theory Workshop (ITW), 2009
    Download:  
    Citation: BibTeX RIS
    The wireless multiple-unicast problem is considered over a layered network, where the rates of transmission are limited by the relaying and interference effect. The deterministic model introduced is used to capture the broadcasting and multiple access effects. The capacity region of the Z-chain relay-interference network is fully characterized. In order to solve the problem, we introduce a new achievability scheme based on ldquointerference neutralizationrdquo and a new analysis technique to bound the number of non-interfering (pure) signals
  3. E. Drinea, C. Fragouli and L. Keller, Delay with network coding and feedback, in IEEE International Symposium on Information Theory (ISIT), 2009
    Download:  
    Citation: BibTeX RIS
    We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or a combination (encoding) of messages at each timestep. Receivers provide feedback as to whether the transmission was received. If at some time step a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. It allows Theta(mu) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay than online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains NP-hard even when coding is allowed. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.
  4. M. Jafari Siavoshani, S. Mohajer, C. Fragouli and S. N. Diggavi, On the capacity of non-coherent network coding, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
    Download:  
    Citation: BibTeX RIS
    The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ges 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.
  5. C. Fragouli, J. Widmer and J.-Y. Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Transactions on Networking, 16, 2008
    Download:  
    Citation: BibTeX RIS
    We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of , where is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.
  6. C. Fragouli, Network coding for dynamically changing networks, IEEE International Wireless Communications and Mobile Computing Conference, 2008
    Download:  
    Citation: BibTeX RIS
    We here advocate the case for network coding as a guiding paradigm for the operation of networks that vary in a small time frame, due to node mobility, channel variations, and varying traffic conditions. Three ideas that appeared succesively in time brought in place an elegant operation for network coding in such environments. These are, use of randomized network coding for intermediate node operation, use of generations to avoid synchronization, and use of subspace coding to allow for small packet sizes. Information theoretical performance limits support these results.
  7. C. Fragouli, J. Widmer and J.-Y. Le Boudec, A Network Coding Approach to Energy Efficient Broadcasting: from Theory to Practice, Infocom, 2006
    Download:  
    Citation: BibTeX RIS
    We show that network coding allows to realize significant energy savings in a wireless ad-hoc network, when each node of the network is a source that wants to transmit information to all other nodes. Energy efficiency directly affects battery life and thus is a critical design parameter for wireless ad-hoc networks. We propose an implementable method for performing network coding in such a setting. We analyze theoretical cases in detail, and use the insights gained to propose a practical, fully distributed method for realistic wireless ad-hoc scenarios. We address practical issues such as setting the forwarding factor, managing generations, and impact of transmission range. We use theoretical analysis and packet level simulation.
  8. Download:  
    Citation: BibTeX RIS
    A key problem in transporting multimedia traffic across wireless networks is a controlled sharing of the wireless link by different packet streams. So far this problem has been treated as that of providing support for quality of service in time division multiplexing based medium access control protocols (MAC). Adopting a different perspective to the problem, this paper describes an approach based on extending the class-based queueing (CBQ) based controlled hierarchical link sharing model proposed for the Internet. Our scheme enhances CBQ, which works well in wired links such as point-to-point wires of fixed bandwidth, to also work well with wireless links based on radio channels that are (i) inherently shared on-demand among multiple radios, and (ii) are subject to highly dynamic bandwidth variations due to spatially and temporally varying fading with accompanying burst errors. The proposed scheme is based on combining a modified version of CBQ with channel-state dependent packet scheduling.

All publications in wireless networks

research/wireless.txt · Last modified: 2011/04/24 11:39 by lokeller
© ARNI/EPFL, 1015 Lausanne
webmaster