Delay with network coding and feedback.
Drinea, E.; Fragouli, C.; and Keller, L.
In
IEEE International Symposium on Information Theory (ISIT), 2009.
doi
link
bibtex
@inproceedings{drinea_delay_2009,
type={4},
author = {Drinea, Eleni and Fragouli, C. and Keller, L.},
booktitle = {{IEEE} {International} {Symposium} on {Information} {Theory} ({ISIT})},
doi = {10.1109/isit.2009.5205612},
keywords = {network coding, channel coding, erasure channel, feedback, feedback information, multiple description coding, NP-hard, offline algorithm, offline minimization problem, online algorithm, online heuristics},
tags = {network_coding,wireless},
title = {Delay with network coding and feedback},
year = {2009}
}
Multipath Diversity and Robustness for Sensor Networks.
Fragouli, C.; Argyraki, K.; and Keller, L.
In
Sensor Networks, pages 75–99. Springer, 2009.
link
bibtex
abstract
@incollection{fragouli_multipath_2009,
abstract = {Balancing energy efficiency and reliability is a common underlying goal for most information collection protocols in sensor networks. Multipath diversity has emerged as one of the promising techniques to achieve such a balance. In this chapter, we provide a unified framework for the multipath techniques in the literature and discuss their basic benefits and drawbacks. We also discuss emerging techniques from the area of network coding.},
type={4},
author = {Fragouli, C. and Argyraki, K. and Keller, L.},
booktitle = {Sensor {Networks}},
pages = {75--99},
publisher = {Springer},
tags = {sensor_networks},
title = {Multipath {Diversity} and {Robustness} for {Sensor} {Networks}},
year = {2009}
}
Balancing energy efficiency and reliability is a common underlying goal for most information collection protocols in sensor networks. Multipath diversity has emerged as one of the promising techniques to achieve such a balance. In this chapter, we provide a unified framework for the multipath techniques in the literature and discuss their basic benefits and drawbacks. We also discuss emerging techniques from the area of network coding.
A network coding approach to network tomography.
Fragouli, C.; Markopoulou, A.; and Gjoka, M.
IEEE Transactions on Information Theory. January 2009.
link
bibtex
@article{fragouli_network_2009,
type={2},
author = {Fragouli, C. and Markopoulou, Athina and Gjoka, M.},
journal = {IEEE Transactions on Information Theory},
month = {January},
tags = {wireless},
title = {A network coding approach to network tomography},
year = {2009}
}
An overview of network coding for dynamically changing networks.
Fragouli, C.
Int. J. Auton. Adapt. Commun. Syst., 2(1): 1–23. 2009.
Place: Inderscience Publishers, Geneva, SWITZERLAND Publisher: Inderscience Publishers
doi
link
bibtex
@article{fragouli_overview_2009,
type={4},
author = {Fragouli, C.},
doi = {10.1504/ijaacs.2009.024280},
issn = {1754-8632},
journal = {Int. J. Auton. Adapt. Commun. Syst.},
note = {Place: Inderscience Publishers, Geneva, SWITZERLAND
Publisher: Inderscience Publishers},
number = {1},
pages = {1--23},
tags = {network_coding,wireless},
title = {An overview of network coding for dynamically changing networks},
volume = {2},
year = {2009}
}
On the capacity of non-coherent network coding.
Jafari Siavoshani, M.; Mohajer, S.; Fragouli, C.; and Diggavi, S. N.
In
Information Theory, 2009. ISIT 2009. IEEE International Symposium on, pages 273–277, July 2009.
doi
link
bibtex
abstract
@inproceedings{jafari_siavoshani_capacity_2009,
abstract = {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.},
type={4},
author = {Jafari Siavoshani, Mahdi and Mohajer, S. and Fragouli, C. and Diggavi, Suhas N.},
booktitle = {Information {Theory}, 2009. {ISIT} 2009. {IEEE} {International} {Symposium} on},
doi = {10.1109/isit.2009.5205851},
keywords = {multicast theorem, noncoherent network coding, packet length, single bit routing, source coding, telecommunication network routingmin-cut value towards},
month = {July},
pages = {273--277},
tags = {network_coding,wireless},
title = {On the capacity of non-coherent network coding},
year = {2009}
}
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.
Compressed network coding vectors.
Jafari Siavoshani, M.; Keller, L.; Argyraki, K.; and Fragouli, C.
In
Information Theory, 2009. ISIT 2009. IEEE International Symposium on, pages 109–113, July 2009.
doi
link
bibtex
abstract
@inproceedings{jafari_siavoshani_compressed_2009,
abstract = {In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.},
type={4},
author = {Jafari Siavoshani, Mahdi and Keller, L. and Argyraki, K. and Fragouli, C.},
booktitle = {Information {Theory}, 2009. {ISIT} 2009. {IEEE} {International} {Symposium} on},
doi = {10.1109/isit.2009.5206041},
keywords = {linear codes, data compression, intermediate network node, linear combination, subspace coding, vectorscompressed network coding vector},
month = {July},
pages = {109--113},
tags = {network_coding,sensor_networks},
title = {Compressed network coding vectors},
year = {2009}
}
In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.
Distributed Rate Allocation for Network-coded Systems.
Jafarian, A.; Lee, S. H.; Vishwanath, S.; and Fragouli, C.
In
Sensor, Mesh and Ad Hoc Communications and Networks Workshops, 2009. SECON Workshops '09. 6th Annual IEEE Communications Society Conference on, pages 1–6, June 2009.
doi
link
bibtex
abstract
@inproceedings{jafarian_distributed_2009,
abstract = {This paper addresses the problem of distributed rate allocation for a class of multicast networks employing linear network coding. The goal is to minimize the cost (for example, the sum rates allocated to each link in the network) while satisfying a multicast rate requirement for each destination in the network. In essence, this paper aims to achieve network capacity while ensuring that the cost of operation (equivalently, the rate allocated per link in the network) is minimal. This paper uses a belief propagation framework to obtain a distributed algorithm for the rate allocation problem. Simulation results are presented to demonstrate the convergence of this algorithm to the optimal rate allocation solution.},
type={4},
author = {Jafarian, A. and Lee, Sang Hyun and Vishwanath, S. and Fragouli, C.},
booktitle = {Sensor, {Mesh} and {Ad} {Hoc} {Communications} and {Networks} {Workshops}, 2009. {SECON} {Workshops} '09. 6th {Annual} {IEEE} {Communications} {Society} {Conference} on},
doi = {10.1109/sahcnw.2009.5172929},
keywords = {cost minimization, distributed algorithm, distributed algorithms, distributed rate allocation, linear codes, linear network coding, minimisationbelief propagation framework, multicast network, network capacity, network-coded system},
month = {June},
pages = {1--6},
tags = {wireless},
title = {Distributed {Rate} {Allocation} for {Network}-coded {Systems}},
year = {2009}
}
This paper addresses the problem of distributed rate allocation for a class of multicast networks employing linear network coding. The goal is to minimize the cost (for example, the sum rates allocated to each link in the network) while satisfying a multicast rate requirement for each destination in the network. In essence, this paper aims to achieve network capacity while ensuring that the cost of operation (equivalently, the rate allocated per link in the network) is minimal. This paper uses a belief propagation framework to obtain a distributed algorithm for the rate allocation problem. Simulation results are presented to demonstrate the convergence of this algorithm to the optimal rate allocation solution.
Identity aware sensor networks.
Keller, L.; Jafari Siavoshani, M.; Fragouli, C.; Argyraki, K.; and Diggavi, S. N.
In
INFOCOM 2009, IEEE, pages 2177–2185, April 2009.
ISSN: 0743-166X
doi
link
bibtex
abstract
@inproceedings{keller_identity_2009,
abstract = {In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.},
type={4},
author = {Keller, L. and Jafari Siavoshani, Mahdi and Fragouli, C. and Argyraki, K. and Diggavi, Suhas N.},
booktitle = {{INFOCOM} 2009, {IEEE}},
doi = {10.1109/infcom.2009.5062142},
keywords = {identity aware sensor networks, source-identity-message separation, wireless sensor networks, wireless sensor networksenergy efficient},
month = {April},
note = {ISSN: 0743-166X},
pages = {2177--2185},
tags = {sensor_networks},
title = {Identity aware sensor networks},
year = {2009}
}
In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.
SenseCode: Network coding for reliable sensor networks.
Keller, L.; Atsan, E.; Argyraki, K.; and Fragouli, C.
EPFL Technical Report, in submission. 2009.
link
bibtex
abstract
@article{keller_sensecode_2009,
abstract = {Designing a communication protocol for sensor networks often involves obtaining the “right” trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks—and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it achieves higher reliability (typically 20\%, in certain cases up to 30\%), while consuming the same amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through TOSSIM simulations, as well as a testbed of 30 TinyNode sensors deployed in our department building},
type={4},
author = {Keller, L. and Atsan, Emre and Argyraki, K. and Fragouli, C.},
journal = {EPFL Technical Report, in submission},
tags = {network_coding,sensor_networks},
title = {{SenseCode}: {Network} coding for reliable sensor networks},
year = {2009}
}
Designing a communication protocol for sensor networks often involves obtaining the “right” trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks—and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it achieves higher reliability (typically 20%, in certain cases up to 30%), while consuming the same amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through TOSSIM simulations, as well as a testbed of 30 TinyNode sensors deployed in our department building
Approximate capacity of a class of gaussian interference-relay networks.
Mohajer, S.; Diggavi, S. N.; Fragouli, C.; and Tse, D.
IEEE Transactions on Information Theory. 2009.
link
bibtex
@article{mohajer_approximate_2009,
type={2},
author = {Mohajer, S. and Diggavi, Suhas N. and Fragouli, C. and Tse, D.},
journal = {IEEE Transactions on Information Theory},
tags = {network_coding},
title = {Approximate capacity of a class of gaussian interference-relay networks},
year = {2009}
}
Capacity of deterministic Z-chain relay-interference network.
Mohajer, S.; Diggavi, S. N.; Fragouli, C.; and Tse, D.
In
IEEE Information Theory Workshop (ITW), 2009.
link
bibtex
abstract
@inproceedings{mohajer_capacity_2009,
abstract = {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},
type={4},
author = {Mohajer, S. and Diggavi, Suhas N. and Fragouli, C. and Tse, D.},
booktitle = {{IEEE} {Information} {Theory} {Workshop} ({ITW})},
tags = {network_coding,wireless},
title = {Capacity of deterministic {Z}-chain relay-interference network},
year = {2009}
}
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
On the capacity of multisource non-coherent network coding.
Mohajer, S.; Jafari Siavoshani, M.; Diggavi, S. N.; and Fragouli, C.
In
Networking and Information Theory, 2009. ITW 2009. IEEE Information Theory Workshop on, pages 130–134, June 2009.
doi
link
bibtex
abstract
@inproceedings{mohajer_capacity_2009-1,
abstract = {We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1 - delta2), where deltai is what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.},
type={4},
author = {Mohajer, S. and Jafari Siavoshani, Mahdi and Diggavi, Suhas N. and Fragouli, C.},
booktitle = {Networking and {Information} {Theory}, 2009. {ITW} 2009. {IEEE} {Information} {Theory} {Workshop} on},
doi = {10.1109/itwnit.2009.5158556},
keywords = {channel capacity, channel codingchannel capacity, multisource noncoherent network coding, subspace codebook},
month = {June},
pages = {130--134},
tags = {network_coding,wireless},
title = {On the capacity of multisource non-coherent network coding},
year = {2009}
}
We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1 - delta2), where deltai is what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.
On Degraded Two Message Set Broadcast.
Saeedi, S.; Diggavi, S. N.; Fragouli, C.; and Prabhakaran, V. M.
In
IEEE Information Theory Workshop (ITW), 2009.
link
bibtex
abstract
@inproceedings{saeedi_degraded_2009,
abstract = {We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P x U. Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.},
type={4},
author = {Saeedi, Shirin and Diggavi, Suhas N. and Fragouli, C. and Prabhakaran, V. M.},
booktitle = {{IEEE} {Information} {Theory} {Workshop} ({ITW})},
tags = {network_coding,wireless},
title = {On {Degraded} {Two} {Message} {Set} {Broadcast}},
year = {2009}
}
We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P x U. Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
Multiple source multiple destination topology inference using network coding.
Sattari, P.; Markopoulou, A.; and Fragouli, C.
In
Network Coding, Theory, and Applications, 2009. NetCod '09. Workshop on, pages 36–41, June 2009.
doi
link
bibtex
abstract
@inproceedings{sattari_multiple_2009,
abstract = {In this paper, we combine network coding and tomographic techniques for topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. We combine and extend two ideas that have been developed independently. On one hand, network coding introduces topology-dependent correlation, which can then be exploited at the receivers to infer the topology. On the other hand, it has been shown that a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem can be decomposed into multiple two source, two receiver subproblems. Our first contribution is to show that, when intermediate nodes perform network coding, topological information contained in network coded packets allows to accurately distinguish among all different 2-by-2 subnetwork components, which was not possible with traditional tomographic techniques. Our second contribution is to use this knowledge to merge the subnetworks and accurately reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.},
type={4},
author = {Sattari, P. and Markopoulou, Athina and Fragouli, C.},
booktitle = {Network {Coding}, {Theory}, and {Applications}, 2009. {NetCod} '09. {Workshop} on},
doi = {10.1109/netcod.2009.5191391},
keywords = {network coding, encoding, multiple source multiple destination topology inference, network coded packets, network topology, receivers, routing protocols, telecommunication network topologycorrelation, tomographic techniques},
month = {June},
pages = {36--41},
tags = {network_coding},
title = {Multiple source multiple destination topology inference using network coding},
year = {2009}
}
In this paper, we combine network coding and tomographic techniques for topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. We combine and extend two ideas that have been developed independently. On one hand, network coding introduces topology-dependent correlation, which can then be exploited at the receivers to infer the topology. On the other hand, it has been shown that a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem can be decomposed into multiple two source, two receiver subproblems. Our first contribution is to show that, when intermediate nodes perform network coding, topological information contained in network coded packets allows to accurately distinguish among all different 2-by-2 subnetwork components, which was not possible with traditional tomographic techniques. Our second contribution is to use this knowledge to merge the subnetworks and accurately reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
![Group testing for connected communities [link]](http://bibbase.org/img/filetypes/link.svg "Paper")