home > Publications > Search

Found 119 publications with these criteria

1. Xu, Kuang; Dousse, Olivier; Thiran, Patrick   [XuDT:10]   [published]
   Self-Synchronizing Properties of CSMA Wireless Multi-hop Networks    
   ACM Sigmetrics; New York, June 14?18, 2010
   We show that CSMA is able to spontaneously synchronize transmissions in a wireless network with constant-size packets, and that this property can be used to devise efficient synchronized CSMA scheduling mechanisms without message passing. Using tools from queuing theory, we prove that for any connected wireless networks with arbitrary interference constraints, it is possible to implement self-synchronizing TDMA schedules without any explicit message passing or clock synchronization besides transmitting the original data packets, and the interaction can be fully local in that each node decides when to transmit next only by overhearing its neighbors? transmissions. We also provide a necessary and sufficient condition on the emergence of self-synchronization for a given TDMA schedule, and prove that such conditions for self-synchronization can be checked in a finite number of steps for a finite network topology.
   
   
2. Bénézit, Florence; Blondel, Vincent; Thiran, Patrick; Tsitsiklis, John; Vetterli, Martin   [BénézitBTTV:10]   [published]
   Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices     
   IEEE International Symposium on Information Theory; Austin, Texas, USA, June 13-18, 2010
   This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]?[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.
   
   
3. Chao Tian, Suhas Diggavi, Shlomo Shamai   [TianDS:10]   [published]
   The Achievable Distortion Region of Bivariate Gaussian Source on Gaussian Broadcast Channel    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
4. Chao Tian, Jun Chen, Suhas Diggavi, Shlomo Shamai   [TianCDS:10]   [published]
   Optimality and Approximate Optimality of Source-Channel Separation in Networks    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
5. Satish Babu Korada, Andrea Montanari, Emre Telatar, Ruediger Urbanke   [KoradaMTU:10]   [published]
   An Empirical Scaling Law for Polar Codes    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
6. Etienne Perron, Suhas Diggavi, Emre Telatar   [PerronDT:10]   [published]
   On cooperative secrecy for discrete memoryless relay networks    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
7. Mohammad Karzand, Emre Telatar   [KarzandT:10]   [published]
   Polar Codes for Q-ary Source Coding    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
8. Ayfer Ozgur, Suhas Diggavi   [OzgurD:10]   [published]
   Approximately achieving Gaussian relay network capacity with lattice codes    
   ISIT 2010, Austin, 13-18 June 10
   
   
   
9. Ghita, Denisa; Nguyen, Hung; Kurant, Maciej; Argyraki, Aikaterini; Thiran, Patrick   [GhitaNKAT:10]   [published]
   Netscope: Practical Network Loss Tomography    
   IEEE INFOCOM Conference; San Diego, CA, USA, March 15-19, 2010
   We present Netscope, a tomographic technique that infers the loss rates of network links from unicast end-to-end measurements. Netscope uses a novel combination of first- and second-order moments of end-to-end measurements to identify and characterize the links that cannot be (accurately) characterized through existing practical tomographic techniques. Using both analytical and experimental tools, we show that Netscope enables scalable, accurate link-loss inference: in a simulation scenario involving 4000 links, 20% of them lossy, Netscope correctly identifies 94% of the lossy links with a false positive rate of 16%?a significant improvement over the existing alternatives. Netscope is robust in the sense that it requires no parameter tuning, moreover its advantage over the alternatives widens when the number of lossy links increases. We also validate Netscope?s performance on an ?Internet tomographer? that we deployed on an overlay of 400 PlanetLab nodes.
   
   
10. Herzen, Julien; Aziz, Adel; Thiran, Patrick   [HerzenAT:10]   [published]
    Demo Abstract of Net-Controller: a Network Visualization and Management Tool    
    Infocom demo; San Diego, March 2010
    Net-Controller is a user-friendly network visualization and management tool developed at EPFL in order to easily retrieve and display in real time network statistics, such as link throughput and queue occupancy from a large testbed composed of wireless routers. Additionally, Net-Controller allows to control and modify the parameters of a complete network from a central point, and to easily generate traffic between different nodes. We intend to illustrate some of the features of Net-Controller through two examples that show how easily this tool detects and helps elucidate the throughput degradation that occurs in a wireless multi-hop network. The first example shows how and why fair queuing [6] improves performance compared to the standard FIFO policy used in off-the-shelf routers. The second example shows how and why a hop-by-hop congestion control mechanism, such as EZ-Flow [4] is needed to tackle the instability problem of a multi-hop scenario.
    
    
11. Aziz, Adel; Starobinski, David; Thiran, Patrick; El Fawal, Alaeddine   [AzizSTE:09]   [published]
    EZ-Flow: Removing Turbulence in IEEE 802.11 Wireless Mesh Networks without Message Passing    
    ACM CoNEXT 2009; Rome, December 1-4, 2009
    Recent analytical and experimental work demonstrate that IEEE 802.11-based wireless mesh networks are prone to turbulence. Manifestations of such turbulence take the form of large buffer build-up at relay nodes, end-to-end delay fluctuations, and traffic congestion. In this paper, we propose and evaluate a novel, distributed flow-control mechanism to address this problem, called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a 9-node testbed deployed over 4 different buildings, show that EZ-flow effectively smoothes traffic and improves delay, throughput, and fairness performance. We further corroborate these results with a mathematical stability analysis and extensive ns-2 simulations run for different traffic workloads and network topologies.
    
    
12. Shirin Saeedi Bidokhti, Suhas Diggavi, Christina Fragouli, Vinod Prabhakaran   [BidokhtiDFP:09]   [published]
    On degraded two message set broadcasting    
    IEEE Information Theory Workshop (ITW 2009); Taormina, 11-16 Oct 09
    
    
    
13. E. Telatar   [Telatar:09]   [published]
    Performance of Polarization Codes    
    IEEE Information Theory Workshop (ITW 2009); Taormina, 11-16 Oct 09
    
    
    
14. Etienne Perron, Suhas Diggavi, Emre Telatar   [PerronDT:09]   [published]
    A Multiple Access Approach for the Compound Wiretap Channel    
    IEEE Information Theory Workshop (ITW 2009); Taormina, 11-16 Oct 09
    
    
    
15. Durvy, Mathilde; Dousse, Olivier; Thiran, Patrick   [DurvyDT:09b]   [published]
    On the Fairness of Large CSMA Networks    
    IEEE Journal on Selected Areas in Communications, vol. 27, no 7, p. 1093-1104
    We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, such as IEEE 802.11, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. This unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large one-dimensional networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In two-dimensional networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness.
    
    
16. C. Tian, S. Mohajer, S N. Diggavi   [TianMD:09]   [published]
    Approximating the Gaussian Multiple description Rate Region Under Symmetric Distortion    
    IEEE Transactions on Information Theory, Volume 55, Issue 8, Aug 2009
    
    
    
17. S. Mohajer, S N. Diggavi, D. Tse   [MohajerDT:09]   [published]
    Approximate Capacity of a Class of Gaussian Relay-Interference Networks    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
18. Mahdi Jafarisiavoshani; Soheil Mohajer; Christina Fragouli; Suhas Diggavi   [JafarisiavoshaniMFD:09]   [published]
    On the Capacity of Non-Coherent Network Coding    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
19. Etienne Perron; Suhas Diggavi; Emre Telatar   [PerronDT:09]   [published]
    Lossy Source Coding with Gaussian or Erased Side-Information    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
20. Ashish Khisti; Suhas Diggavi; Gregory Wornell   [KhistiDW:09]   [published]
    Secret key agreement using asymmetry in channel state knowledge    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
21. Chao Tian; Suhas Diggavi; Shlomo Shamai   [TianDS:09]   [published]
    Approximate Characterizations For the Gaussian Broadcasting Distortion Region    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
22. Erdal Arikan; Emre Telatar   [ArikanT:09]   [published]
    On the Rate of Channel Polarization    
    IEEE International Symposium on Information Theory (ISIT09), Seoul, 28 June - 3 July 09
    
    
    
23. S. Mohajer, S N. Diggavi, C. Fragouli, D. Tse   [MohajerDFT:09]   [published]
    Capacity of Deterministic Z-Chain Relay-Interference Network    
    IEEE Information Theory Workshop (ITW), Volos, 10-12 June 2009
    
    
    
24. S. Mohajer, M. Jafari Siavoshani, S. Diggavi, Ch. Fragouli   [MohajerSDF:09]   [published]
    On the Capacity of Multi-source Non-Coherent Network Coding    
    IEEE Information Theory Workshop (ITW), Volos, 10-12 June 2009
    
    
    
25. S. Mohajer, S. Diggavi   [MohajerD:09]   [published]
    A Deterministic Approach to Wireless Network Error Correction    
    IEEE Information Theory Workshop (ITW), Volos, 10-12 June 2009
    
    
    
26. D. Tschopp, S N. Diggavi, M. Grossglauser   [TschoppDG:09]   [submitted]
    Hierarchical Routing over Dynamic Wireless Networks    
    Random Structures and Algorithms, May 2009
    
    
    
27. E. Perron; S. Diggavi; E. Telatar   [PerronDT:09]   [published]
    On Cooperative Wireless Network Secrecy    
    IEEE Infocom 09, Rio de Janeiro, 19-25 Apr 09
    
    
    
28. L. Keller; M. Jafarisiavoshani; C. Fragouli; K. Argyraki; S. Diggavi    [KellerJFAD:09]   [published]
    Identity Aware Sensor Networks    
    IEEE InfoCom 2009; Rio de Janeiro, Brazil, April 19-25, 2009
    
    
    
29. Hung Nguyen; R. Teixeira; P. Thiran; C. Diot   [HungTTD:09]   [published]
    Minimizing Probing Cost for Detecting Interface Failures: Algorithms and Scalability Analysis    
    IEEE Infocom 09, Rio de Janeiro, 19-25 Apr 09
    
    
    
30. Florence Benezit, Patrick Thiran, Martin Vetterli   [BenezitTV:09]   [published]
    INTERVAL CONSENSUS: FROM QUANTIZED GOSSIP TO VOTING    
    IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP); Taiwan, April 19-24, 2009
    
    
    
31. D. Tschopp, S N. Diggavi   [TschoppD:09]   [published]
    Rank-sensitive Hashing for Nearest Neighbor Search    
    EPFL-Licos Technical Report, April 2009
    
    
    
32. Durvy, Mathilde; Dousse, Olivier; Thiran, Patrick   [DurvyDT:09]   [published]
    Self-Organization Properties of CSMA/CA Systems and Their Consequences on Fairness    
    IEEE Transactions on Information Theory, vol. 55, no 3, p. 931-943
    Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the IEEE 802.11 protocol, are known to be unfair. In multihop networks, they can even favor some links to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood.We find that the capture effect and the relative values of the receive and carrier sensing ranges play a crucial role in the performance of these protocols. Using a simple Markovian model, we show that an idealized CSMA/CA protocol suffers from starvation when the receiving and sensing ranges are equal, but quite surprisingly that this unfairness is reduced or even disappears when these two ranges are sufficiently different. We also show that starvation has a positive counterpart, namely organization. When its access intensity is large the protocol organizes the transmissions in space in such a way that it maximizes the number of concurrent successful transmissions. We obtain exact formulae for the so-called spatial reuse of the protocol on large line networks. [pdf]
    
    
33. Piorkowski, Michal; Sarafijanovoc-Djukic, Natasa; Grossglauser, Matthias   [PiorkowskiSG:09]   [published]
    A Parsimonious Model of Mobile Partitioned Networks with Clustering    
    THE First International Conference on COMmunication Systems and NETworkS (COMSNETS); Bangalore, India, January 5-10, 2009, p. 1-10
    Mobile wireless networks frequently possess, at the same time, both dense and sparse regions of connectivity; for example, due to a heterogeneous node distribution or radio propagation environment. This paper is about modeling both the mobility and the formation of clusters in such networks, where nodes are concentrated in clusters of dense connectivity, interspersed with sparse connectivity. Uniformly dense and sparse networks have been extensively studied in the past, but not much attention has been devoted to clustered networks. We present a new mobility model for clustered networks, which is important for the design and evaluation of routing protocols. We refer to our model as Heterogeneous Random Walk (HRW). This model is simple, mathematically tractable, and it captures the phenomenon of emerging clusters, observed in real partitioned networks. We provide a closed-form expression for the stationary distribution of node position and we give a method for ?perfect simulation?. Moreover, we provide evidence, based on mobility traces, for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. In particular, we show that in some scenarios, nodes have statistically very similar mobility patterns. Also, we discuss cluster dynamics and the relationship between node speed and node density.
    
    
34. S. Mohajer, S N. Diggavi, C. Fragouli, D. Tse   [MohajerDFT:08]   [published]
    Transmission techniques for relay-interference networks    
    Allerton Conference on Communication, Control and Computing, 25 Aug 2008
    
    
    
35. Salman Avestimehr, Suhas Diggavi, David Tse   [AvestimehrDT:08]   [published]
    Approximate Capacity of Gaussian Relay Networks    
    IEEE International Symposium on Information Theory (ISIT); Toronto, July 6-11 2008
    
    
    
36. Mahdi Jafari Siavoshani, Christina Fragouli, Suhas Diggavi   [Siavoshani:FD:08]   [published]
    Noncoherent Multisource Network Coding    
    IEEE International Symposium on Information Theory (ISIT); Toronto, July 6-11 2008
    
    
    
37. S. Dusad, S. N. Diggavi   [DusadD:08]   [published]
    Successive refinement of diversity for fading ISI MISO    
    IEEE International Symposium on Information Theory (ISIT); Toronto, July 6-11 2008
    
    
    
38. Tschopp, Dominique; Diggavi, Suhas; Grossglauser, Matthias   [TschoppDG:08]   [published]
    Hierarchical Routing over Dynamic Wireless Networks    
    ACM Sigmetrics; Annapolis, MD, 2-6 June 2008
    
    
    
39. Piorkowski, Michal; Sarafijanovic-Djukic, Natasa; Grossglauser, Matthias   [PiorkowskiSG:08]   [published]
    On Clustering Phenomenon in Mobile Partitioned Networks    
    The First ACM SIGMOBILE International Workshop on Mobility Models for Networking Research; Hong Kong SAR, China, 26 May, p. 1--8
    According to different kinds of connectivity, we can distinguish three types of mobile ad-hoc networks: dense, sparse and clustered networks. This paper is about modeling mobility in clustered networks, where nodes are concentrated into clusters of dense connectivity, and in between there exists sparse connectivity. The dense and sparse networks are extensively studied and modeled, but not much attention is paid to the clustered networks. In the sparse and clustered networks, an inherently important aspect is the mobility model, both for the design and evaluation of routing protocols. We propose a new mobility model for clustered networks, called Heterogeneous Random Walk. This model is simple, mathematically tractable and most importantly it captures the phenomenon of emerging clusters, observed in real partitioned networks, in an elegant way. We provide a closed-form expression for the stationary distribution of node position and we give a recipe for the "perfect simulation". Moreover, based on the real mobility trace we provide strong evidence for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. For the very first time in the literature we show evidence for the correlation between the spatial speed distribution and the cluster formation. We also present the results of the analysis of real cluster dynamics caused by nodes' mobility.
    
    
40. Hung Nguyen, Daniel Figueiredo, Patrick Thiran, Matthias Grossglauser   [NguyenFTG:08]   [published]
    Balanced Relay Allocation on Heterogeneous Unstructured Overlays    
    IEEE Infocom 2008, Phoenix, 15-17 Apr 08
    Due to the increased usage of NAT boxes and firewalls, it has become harder for applications to establish direct connections seamlessly among two end-hosts. A recently adopted proposal to mitigate this problem is to use {\em relay nodes}, end-hosts that act as intermediary points to bridge connections. Efficiently selecting a relay node is not a trivial problem, specially in a large-scale unstructured overlay system where end-hosts are heterogeneous. In such environment, heterogeneity among the relay nodes comes from the inherent differences in their capacities and from the way overlay networks are constructed. Despite this fact, good relay selection algorithms should effectively balance the aggregate load across the set of relay nodes. In this paper, we address this problem using algorithms based on the {\em two random choices} method. We first prove that the classic load-based algorithm can effectively balance the load even when relays are heterogeneous, and that its performance depends directly on relay heterogeneity. Second, we propose an utilization-based random choice algorithm to distribute load in order to balance relay utilization. Numerical evaluations through simulations illustrate the effectiveness of this algorithm, indicating that it might also yield provable performance (which we conjecture). Finally, we support our theoretical findings through simulations of various large-scale scenarios, with realistic relay heterogeneity. [pdf]
    
    
41. Mathilde Durvy, Olivier Dousse, Patrick Thiran   [DurvyDT:08]   [published]
    Border Effects, Fairness, and Phase Transition in Large Wireless Networks    
    IEEE Infocom 2008, Phoenix, 15-17 Apr 08
    [pdf]
    
    
42. Denantes, Patrick; Benezit, Florence; Thiran, Patrick; Vetterli, Martin   [DenantesBTV:08]   [published]
    Which Distributed Averaging Algorithm Should I Choose for my Sensor Network?    
    IEEE INFOCOM 2008; Phoenix, AZ, 13-18 April 2008
    Average consensus and gossip algorithms have recently received significant attention, mainly because they constitute simple and robust algorithms for distributed information processing over networks. Inspired by heat diffusion, they compute the average of sensor networks measurements by iterating local averages until a desired level of convergence. Confronted with the diversity of these algorithms, the engineer may be puzzled in his choice for one of them. As an answer to his/her need, we develop precise mathematical metrics, easy to use in practice, to characterize the convergence speed and the cost (time, message passing, energy...) of each of the algorithms. In contrast to other works focusing on time-invariant scenarios, we evaluate these metrics for ergodic time- varying networks. Our study is based on Oseledec?s theorem, which gives an almost-sure description of the convergence speed of the algorithms of interest. We further provide upper bounds on the convergence speed. Finally, we use these tools to make some experimental observations illustrating the behavior of the convergence speed with respect to network topology and reliability in both average consensus and gossip algorithms.
    
    
43. Piorkowski, Michal; Raya, Maxim; Lugo, Ada; Papadimitratos, Panos; Grossglauser, Matthias; Hubaux, Jean-Pierre   [PiorkowskiRLPGH:08]   [published]
    TraNS: Realistic Joint Traffic and Network Simulator for VANETs    
    ACM SIGMOBILE Mobile Computing and Communications Review, vol. 12, no 1, p. 31--33
    Realistic simulation is a necessary tool for the proper evaluation of newly developed protocols for Vehicular Ad Hoc Networks (VANETs). Several recent efforts focus on achieving this goal. Yet, to this date, none of the proposed solutions fulfill all the requirements of the VANET environment. This is so mainly because road traffic and communication network simulators evolve in disjoint research communities. We are developing TraNS, an open-source simulation environment, as a step towards bridging this gap. This short paper describes the TraNS architecture and our ongoing development efforts.
    
    
44. Hung Nguyen and Patrick Thiran   [NguyenT:07b]   [published]
    Network Loss Inference with Second Order Statistics of End-to-End Flows    
    ACM IMC'07, San Diego, 24-27 Oct 07
    We address the problem of calculating link loss rates from end-to-end measurements. Contrary to existing works that use only the average end-to-end loss rates or strict temporal correlations between probes, we exploit second-order moments of end-to-end flows. We first prove that the variances of link loss rates can be uniquely calculated from the covariances of the measured end-to-end loss rates in any realistic topology. After calculating the link variances, we remove the uncongested links with small variances from the first-order moment equations to obtain a full rank linear system of equations, from which we can calculate precisely the loss rates of the remaining congested links. This operation is possible because losses due to congestion occur in bursts and hence the loss rates of congested links have high variances. On the contrary, most links on the Internet are un-congested, and hence the averages and variances of their loss rates are virtually zero. Our proposed solution uses only regular unicast probes and thus is applicable in today’s Internet. It is accurate and scalable, as shown in our simulations and experiments on PlanetLab. [pdf]
    
    
45. Benyuan Liu, Patrick Thiran, Don Towsley   [LiuTT:07]   [published]
    Capacity of a Wireless Ad Hoc Network with Infrastructure    
    MobiHoc 2007, Montreal, 9-14 Sep 07
    In this paper we study the capacity of wireless ad hoc networks with infrastructure support of an overlay of wired base stations. Such a network architecture is often referred to as hybrid wireless network or multihop cellular network. Previous studies on this topic are all focused on the two-dimensional disk model proposed by Gupta and Kumar in their original work on the capacity of wireless ad hoc networks. We further consider a one-dimensional network model and a two-dimensional strip model to investigate the impact of network dimensionality and geometry on the capacity of such networks. Our results show that different network dimensions lead to significantly different capacity scaling laws. Specifically, for a one-dimensional network of $n$ nodes and $b$ base stations, even with a small number of base stations, the gain in capacity is substantial, increasing linearly with the number of base stations as long as $b \log b \leq n$. However, a two-dimensional square (or disk) network requires a large number of base stations $b = \Omega(\sqrt{n})$ before we see such a capacity increase. For a 2-dimensional strip network, if the width of the strip is at least on the order of the logarithmic of its length, the capacity follows the same scaling law as in the 2-dimensional square case. Otherwise the capacity exhibits the same scaling behavior as in the 1-dimensional network. We find that the different capacity scaling behaviors are attributed to the percolation properties of the respective network models. [pdf]
    
    
46. Chao Tian, Suhas Diggavi   [TianD:07]   [published]
    On Scalable Source Coding With Decoder Side Informations     
    IEEE International Symposium on Information Theory, Nice, 24-29 June 07
    
    
    
47. Suhas Diggavi, Michael Mitzenmacher, Henry Pfister    [DiggaviMP:07]   [published]
    Upper Bounds on the Deletion Channel Capacity     
    IEEE International Symposium on Information Theory, Nice, 24-29 June 07
    
    
    
48. Emre Telatar, David Tse   [TelatarT:07]   [published]
    Bounds on the capacity region of a class of interference channels    
    IEEE International Symposium on Information Theory, Nice, 24-29 June 07
    
    
    
49. Maciej Kurant and Patrick Thiran   [KurantT:07]   [published]
    Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction    
    IEEE Journal on Selected Areas in Communications, Volume 25, Issue 5, June 2007
    Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called survivable. Finding a survivable mapping is known to be NP-complete, making it impossible in practice to assess the existence or absence of such a mapping for large networks. (i) We first introduce a new concept of piecewise survivability, which makes the problem much easier in practice (although still NP-complete), and allows us to formally prove that a given survivable mapping does or does not exist. (ii) Secondly, we show how to trace the vulnerable areas in the topology, and how to strengthen them to enable a survivable mapping. (iii) Thirdly, we give an efficient and scalable algorithm that finds a survivable mapping. In contrast to the heuristics proposed in the literature to date, our algorithm exhibits a number of provable properties (e.g., it guarantees the piecewise survivability) that are crucial for (i) and (ii).
    
    
50. Durvy, M; Dousse, O; Thiran, P   [DurvyDT:07]   [published]
    Modeling the 802.11 protocol under different capture and sensing capabilities    
    Infocom 2007; Anchorage, Alaska , USA.
    Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the 802.11 protocol, are known to be unfair. In multi-hop networks, they can even favor some connections to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood. We find that the capture effect and the relative values of the receiving and carrier sensing ranges play a crucial role in the unfairness of these protocols. We show that an idealized 802.11 protocol does suffer from starvation when the receiving and sensing ranges are equal, but quite surprisingly this unfairness is reduced or even disappears when these two ranges are sufficiently different. Using a Markovian model, we explain why apparently benign variations in these ranges have such a dramatic impact on the 802.11 protocol performance. [pdf]
    
    
51. Hung Nguyen, Patrick Thiran   [NguyenT:07]   [published]
    The Boolean Algebra Solution to the Congested IP Link Location Problem: Theory and Practice    
    Infocom 2007, Anchorage, 6-12 May 07
    Like other problems in network tomography or traffic matrix estimation, the location of congested IP links from end-to-end measurements requires solving a system of equations that relate the measurement outcomes with the variables representing the status of the IP links. In most networks, this system of equations does not have a unique solution. To overcome this critical problem, current methods use the unrealistic assumption that all IP links have the same prior probability of being congested. We find that this assumption is not needed, because these probabilities can be uniquely identified from a small set of measurements, using properties of Boolean algebra. We can then use the learnt probabilities as priors to find rapidly the congested links at any time, with an order of magnitude gain in accuracy over existing algorithms. We validate our results both by simulation and real implementation in the PlanetLab network. [pdf]
    
    
52. Tschopp, Dominique; Diggavi, Suhas; Grossglauser, Matthias; Widmer, Joerg   [TschoppDGW:07]   [published]
    Robust Geo-Routing on Embeddings of Dynamic Wireless Networks    
    IEEE INFOCOM
    Wireless routing based on an embedding of the connectivity graph is a very promising technique to overcome shortcomings of geographic routing and topology-based routing. This is of particular interest when either absolute coordinates for geographic routing are unavailable or when they poorly reflect the underlying connectivity in the network. We focus on dynamic networks induced by time-varying fading and mobility. This requires that the embedding is stable over time, whereas the focus of most existing embedding algorithms is on low distortion of single realizations of a graph. We develop a beaconbased distributed embedding algorithm that requires little control overhead, produces low distortion embeddings, and is stable. We also show that a low-dimensional embedding suffices, since at a sufficiently large scale, wireless connectivity graphs are dictated by geometry. The stability of the embedding allows us to combine georouting on the embedding with last encounter routing (LER) for node lookup, further reducing the control overhead. Our routing algorithm avoids dead ends through randomized greedy forwarding. We demonstrate through extensive simulations that our combined embedding and routing scheme outperforms existing algorithms. I. INTRODUCTION
    
    
53. Franceschetti, Massimo; Dousse, Olivier; Tse, David N C; Thiran, Patrick   [FranceschettiDTT:07]   [published]
    Closing the gap in the capacity of random wireless networks via percolation theory    
    IEEE Transactions on Information Theory, vol. 53, no 3, p. 1009-1018
    An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics. It is shown that randomly scattered nodes can achieve, with high probability, the same 1/\sqrt{n} transmission rate of arbitrarily located nodes. This contrasts with previous results suggesting that a 1/\sqrt{nlogn} reduced rate is the price to pay for the randomness due to the random location of the nodes. The network operation strategy to achieve the result corresponds to the transition region between order and disorder of an underlying percolation model. If nodes are allowed to transmit over large distances, then paths of connected nodes that cross the entire network area can be easily found, but these generate excessive interference. If nodes transmit over short distances, then such crossing paths do not exist. Percolation theory ensures that crossing paths form in the transition region between these two extreme scenarios. Nodes along these paths are used as a backbone, relaying data for other nodes, and can transport the total amount of information generated by all the sources. A lower bound on the achievable bit rate is then obtained by performing pairwise coding and decoding at each hop along the paths, and using a time division multiple access scheme. [pdf] [pdf]
    
    
54. Vasudevan, D.; Tian, C.; Diggavi, S N.   [VasudevanTD:06]   [published]
    Lossy source coding for a cascade communication system with side-informations    
    Allerton Conference on Communication, Control and Computing; Allerton, Illinois, 27-29 Sep, 2006
    We investigate source coding in a cascade communication system consisting of an encoder, a relay and an end terminal, where both the relay and the end terminal wish to reconstruct source $X$ with certain fidelities. Additionally, side-informations $Z$ and $Y$ are available at the relay and the end terminal, respectively. The side-information $Z$ at the relay is a physically degraded version of side-information $Y$ at the end terminal. Inner and outer bounds for the rate distortion region are provided in this work for general discrete memoryless sources. The rate distortion region is characterized when the source and side-informations are jointly Gaussian and physically degraded. The doubly symmetric binary source is also investigated and the inner and outer bounds are shown to coincide in certain distortion regimes. A complete equivalence of the rate-distortion region is established between the problem being considered and the side-information scalable source coding problem, when there is no side-information at the relay. As a byproduct, the same equivalence can be established between the well-known successive refinement problem and Yamamoto's cascade communication system, without relying on their rate-distortion characterization.
    
    
55. Sarafijanovic-Djukic, Natasa; Piorkowski, Michal; Grossglauser, Matthias   [Sarafijanovic-DjukicPG:06]   [published]
    Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks    
    SECON'06; Reston, VA, September 25-28, vol. 1, p. 226 - 235
    Mobile wireless ad hoc and sensor networks can be permanently partitioned in many interesting scenarios. This implies that instantaneous end-to-end routes do not exist. Nevertheless, when nodes are mobile, it is possible to forward messages to their destinations through mobility. We observe that in many practical settings, spatial node distributions are very heterogeneous and possess concentration points of high node density. The locations of these concentration points and the flow of nodes between them tend to be stable over time. This motivates a novel mobility model, where nodes move randomly between stable islands of connectivity, where they are likely to encounter other nodes, while connectivity is very limited outside these islands. Our goal is to exploit such a stable topology of concentration points by developing algorithms that allow nodes to collaborate to discover this topology and to use it for efficient mobility forwarding.We achieve this without any external signals to nodes, such as geographic positions or fixed beacons; instead, we rely only on the evolution of the set of neighbors of each node. We propose an algorithm for this collaborative graph discovery problem and show that the inferred topology can greatly improve the efficiency of mobility forwarding. Using both synthetic and data-driven mobility models we show through simulations that our approach achieves end-to-end delays comparable to those of epidemic approaches, while requiring a significantly lower transmission overhead. [pdf]
    
    
56. Durvy, M; Thiran, P   [DurvyT:06a]   [published]
    Understanding the Gap between the IEEE 802.11 Protocol Performance and the Theoretical Limits    
    SECON 2006; Reston, VA, USA
    The ability of the IEEE 802.11 Medium Access Control (MAC) protocol to perform well in multi-hop ad hoc networks has been recently questioned. We observe levels of spatial reuse that are 30% to 50% away from the theoretical limit. The goal of this paper is to answer the following question: what prevents the IEEE 802.11 MAC protocol from operating at the limit determined by its physical layer? We identify three problems in the contention resolution mechanism of the IEEE 802.11 MAC protocol, and we show that they account for most of the gap separating the actual and optimal performances of the protocol. For each of the problems, we propose a solution that, once implemented, allows us to quantify the impact of the problem on the performance of the IEEE 802.11 MAC protocol. The resulting protocol operates 10% to 15% away from the theoretical limit. Finally, we show that reducing the overhead of the protocol to some negligible quantity brings the spatial reuse of the protocol to the theoretical limits. It also makes apparent the powerful organizing capacity of the IEEE 802.11 MAC protocol. [pdf]
    
    
57. Ajdler, Thibaut; Konsbruck, Robert Lee; Roy, Olivier; Sbaiz, Luciano; Telatar, Emre; Vetterli, Martin   [AjdlerKRSTV:06]   [published]
    Spatio-Temporal Sampling and Distributed Compression of the Sound Field    
    European Signal Processing Conference (EUSIPCO); Florence, Italy, September 4-8, 2006
    We investigate how the sound field induced by an acoustic event evolves over space and time. The characteristics of its bidimensional Fourier spectrum are analyzed and spatio-temporal sampling results using an array of microphones are provided for different scenarios of interest. We then address the distributed compression problem using an information-theoretic point of view. In this context, optimal rate-distortion tradeoffs are derived for two scenarios of interest. A linear network setup is first considered, where a central base station aims at recovering with minimum distortion the signals recorded by an infinite line of microphones. A hearing aid problem is then studied, where two hearing devices exchange data over a rate-constrained wireless link in order to provide spatial noise reduction. [pdf]
    
    
58. Perron, E; Diggavi, S N.; Telatar, I E.   [PerronDT:06]   [published]
    On the Role of Encoder Side-Information in Source Coding for Multiple Decoders    
    IEEE International Symposium on Information Theory (ISIT); Seattle, WA, 9-14 July, 2006, p. 331-335
    
    
    
59. Tian, C; Diggavi, S N.   [TianD:06]   [published]
    Multistage successive refinement for Wyner-Ziv source coding with degraded side informations    
    IEEE International Symposium on Information Theory (ISIT); Seattle, WA, 9-14 July, 2006, p. 1594-1598
    
    
    
60. Musy, Stephane; Telatar, Emre   [MusyT:06]   [published]
    On the Transmission of Bursty Sources    
    IEEE International Symposium on Information Theory; Seattle, July 2006
    Traditionally, the bursty nature of data sources is not taken in consideration by information theory. Random arrival times typically are assumed to be smoothed out by appropriate source coding, rendering any meaningful analysis of the end-to-end delay impossible. On the other hand, network theory directly treats these issues, but over-simplifies the channel model. Particularly, the issues of noise and interference are ignored and no sophisticated coding is allowed. In this paper, we introduce a framework in which some aspects of both sides are incorporated. This results in the formulation of new scheduling problems. In simple settings, we are able to characterize and analyze delay optimal policies.
    
    
61. Koksal, Can Emre; Jamieson, Kyle; Telatar, Emre; Thiran, Patrick   [KoksalJTT:06]   [published]
    Impacts of Channel Variability on Link-Level Throughput in Wireless Networks    
    ACM Sigmetrics/Performance 2006; Saint Malo, 26-30 June 2006, vol. 34, no 1
    We study analytically and experimentally the throughput of the packetized time-varying discrete erasure channel with feedback, which closely captures the behavior of many practical physical layers. We observe that the channel variability at different time scales affects the link-level throughput positively or negatively depending on its time scale. We show that the increased variability in the channel at a time scale smaller than a single packet increases the link-level throughput, whereas the variability at a time scale longer than a single packet reduces it. We express the throughput as a function of the number of transmissions per packet and evaluate it as in terms of the cumulants of the samples of the stochastic processes, which model the channel. We also illustrate our results experimentally using mote radios. [pdf]
    
    
62. Luo, Jun; Panchard, Jacques; Piorkowski, Michal; Grossglauser, Matthias; Hubaux, Jean-Pierre   [LuoPPGH:06]   [published]
    MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks    
    the 2nd IEEE/ACM DCOSS; San Francisco, CA, USA, June 2006
    Improving network lifetime is an important issue involved in every aspect of the design and deployment of wireless sensor networks. There is a recent research trend of studying the application of a mobile sink to transport (rather than let the sensor nodes transmit) data back. Whereas this approach trades data delivery latency for reduced (node) energy consumption (and thus an improved lifetime), our experience tells us that sacrificing latency to extend lifetime is not necessary. In this paper, in line with our previous work, we investigate the approach that makes use of a mobile sink for balancing the traffic load and in turn improving network lifetime. We engineer a routing protocol that effectively supports sink mobility. Through intensive simulations in TOSSIM with a real implementation, we prove the feasibility of our mobile sink approach by demonstrating the improved network lifetime in several deployment scenarios.
    
    
63. Grossglauser, M.; Vetterli, M.   [GrossglauserV:06]   [published]
    Locating Mobile Nodes with EASE: Learning Efficient Routes from Encounter Histories Alone    
    IEEE/ACM Transactions on Networking, vol. 14, no 3, p. 457-469
    Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient {\em location service}, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that {\em node mobility} can be exploited to disseminate destination location information {\em without incurring any communication overhead}. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has ``diffused'' estimates of that location. We define and analyze a very simple algorithm called EASE (Exponential Age Search) and show that in a model where $\Theta(n)$ nodes perform independent random walks on a square lattice of size $n$, the length of the routes computed by EASE are of the same order as the distance between the source and destination {\em even for very large $n$.} Therefore, without disseminating any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalability. [pdf]
    
    
64. Bhaskaran, S.R.; Telatar, E.   [BhaskaranT:06]   [published]
    Kurtosis Constraints In Communication Over Fading Channels    
    IEEE International Conference on Communications; Instanbul, Turkey, 11-15 June 2006, vol. 12, p. 5500-5504
    The kurtosis of a signal is a quantitative measure of how `peaky' it is. In this paper we consider two scenarios of communication over fading channels with kurtosis constraints: in the first, we analyze a non-coherent Rayleigh fading channel where the input signal is required to satisfy a kurtosis constraint in addition to a power constraint. In the second, we find the `worst' fading process that satisfies a kurtosis constraint and has a given second moment, while the fading coefficients are assumed to be known at the receiver. In both cases the transmitter is assumed ignorant of the instantaneous fading realization. The technique that enables our analysis is based on bounding mutual information between random variables which satisfy kurtosis and second moment constraints; the bound is tight in the low second moment regime and can be extended to multi-antenna communications. [pdf]
    
    
65. Dousse, Olivier; Franceschetti, Massimo; Thiran, Patrick   [DousseFT:06]   [published]
    On the throughput scaling of wireless relay networks    
    IEEE Transactions on Information Theory (joint issue with IEEE/ACM Transactions on Networking), vol. 52, no 6, p. 2756--2761
    The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed non-zero rate imply some of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.
    
    
66. Olivier Dousse, Massimo Franceschetti, Nicolas Macris, Ronald Meester, Patrick Thiran   [DousseFMMT:06]   [published]
    Percolation in Signal-to-interference-ratio Connectivity Graphs    
    Journal of Applied Probability, Volume 43, Number 2 (2006)
    Continuum percolation models in which pairs of points of a two-dimensional Poisson point process are connected if they are within some range to each other have been extensively studied. This paper considers a variation in which a connection between two points depends not only on their Euclidean distance, but also on the positions of all other points of the point process. This model has been recently proposed to model interference in radio communication networks. Our main result shows that, despite the infinite range dependencies, percolation occurs in the model when the density of the Poisson point process is greater than the critical density value of the independent model, provided that interference from other nodes can be sufficiently reduced (without vanishing). [pdf]
    
    
67. Olivier Dousse, Christina Tavoularis, Patrick Thiran    [DousseTT:06]   [published]
    Delay of intrusion detection in wireless sensor networks    
    7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
    In this paper we consider sensor networks for intrusion de- tection, such that node deployment, node failures and node behavior result in coverage gaps and a fraction of discon- nected nodes in an otherwise dense and well-connected net- work. We focus on the time delay for a mobile intruder to be detected by a sensor with a connected path to the sink, in contrast to existing results for the detection time by a sensor with arbitrary connectivity. We model our network using a supercritical percolation model on the plane, implying the existence of a unique unbounded connected component, and we assume that the sink belongs to this component. We analyze the distribution of the distance traveled by a mov- ing target until it comes within sensing range of a node in the giant component, providing analytical bounds for linear intruder mobility and thorough simulation results for other mobility models. We show that the probability that the in- truder proceeds undetected exhibits non-memoryless behav- ior over shorter distances and an exponentially decreasing tail. We also show that the time of contact with the giant component incurs considerably more delay than the time of first contact with any node, in networks with less than 10% of nodes without a path to the sink, which means that even a small percentage of node failures may have a drastic im- pact on the performance of intrusion detection by a wireless sensor network. [pdf]
    
    
68. Michal Piorkowski, Matthias Grossglauser and Aristidis Papaioannou   [PiorkowskiGP:06]   [published]
    Mobile User Navigation Supported by WSAN: Full-fledge demo of the SmartPark system (Demo)    
    7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
    
    
    
69. Emre Telatar   [Telatar:06]   [published]
    Broadcasting with an upgraded relay    
    IEEE Communication Theory Workshop, Puerto Rico, 21-24 May 2006
    
    
    
70. Konsbruck, Robert; Telatar, Emre; Vetterli, Martin   [KonsbruckTV:06]   [published]
    On the multiterminal rate-distortion function for acoustic sensing    
    IEEE Conference on Acoustics, Speech and Signal Processing, vol. 4, p. 701-704
    
    
    
71. Tchamkerten, Aslan; Telatar, Emre   [TchamkertenT:06]   [published]
    Variable length coding over an unknown channel    
    IEEE Transactions on Information Theory, vol. 52, no 5, p. 2126-2145
    Burnashev in 1976 gave an exact expression for the reliability function of a discrete memoryless channel (DMC) with noiseless feedback. A coding scheme that achieves this exponent needs, in general, to know the statistics of the channel. Suppose now that the coding scheme is designed knowing only that the channel belongs to a family Q of DMCs. Is there a coding scheme with noiseless feedback that achieves Burnashev's exponent uniformly over Q at a nontrivial rate? We answer the question in the affirmative for two families of channels (binary symmetric, and Z). For these families we show that, for any given fraction, there is a feedback coding strategy such that for any member of the family: i) guarantees this fraction of its capacity as rate, and ii) guarantees the corresponding Burnashev's exponent. Therefore, for these families, in terms of delay and error probability, the knowledge of the channel becomes asymptotically irrelevant in feedback code design: there are blind schemes that perform as well as the best coding scheme designed with the foreknowledge of the channel under use. However, a converse result shows that, in general, even for families that consist of only two channels, such blind schemes do not exist.
    
    
72. Durvy, Mathilde; Thiran, Patrick   [DurvyT:06]   [published]
    A Packing Approach to Compare Slotted and Non-Slotted Medium Access Control    
    Infocom 2006; Barcelona, April 23-29, 2006
    In multi-hop ad hoc networks, the efficiency of a medium access control protocol under heavy traffic load depends mainly on its ability to schedule a large number of simultaneous non-interfering transmissions. However, as each node has only a local view of the network, it is difficult to globally synchronize transmission times over the whole network. How does the lack of global coordination affect spatial reuse in multi-hop wireless networks? We show that in a de-centralized network the spatial reuse does not benefit from global clock synchronization. On the contrary, we demonstrate that non-slotted protocols using collision avoidance mechanisms can achieve a higher spatial reuse than the corresponding slotted protocols. By means of a simple backoff mechanism, one can thus favor the spontaneous emergence of spatially dense transmission schedules. [pdf]
    
    
73. Nguyen, H. X.; Thiran, P   [NguyenT:06]   [published]
    Using End-to-End Data to Infer Lossy Links in Sensor Networks    
    IEEE Infocom 2006; Barcelona, Spain, 23-30 April, 2006
    Compared to wired networks, sensor networks pose two additional challenges for monitoring functions: they support much less probing traffic, and they change their routing topologies much more frequently. We propose therefore to use only end-to-end application traffic to infer performance of internal network links. End-to-end data do not provide sufficient information to calculate link loss rates exactly, but enough to identify poorly performing (lossy) links. We introduce inference techniques based on Maximum likelihood and Bayesian principles, which handle well noisy measurements and routing changes. We evaluate the performance of both inference algorithms in simulation and on real network traces. We find that these techniques achieve high detection and low false positive rates. [pdf]
    
    
74. Diggavi, S. N.; Tse, D. N. C.   [DiggaviT:06]   [published]
    On opportunistic codes and broadcast codes with degraded message sets    
    IEEE Information Theory Workshop, Uruguay, p. 227--231
    
    
    
75. Diggavi, S N.; Grossglauser, M   [DiggaviG:06]   [published]
    On information transmission over a finite buffer channel    
    IEEE Transactions on Information Theory, vol. 52, no 3, p. 1226-1237
    
    
    
76. Tchamkerten, A; Telatar, I E   [TchamkertenT:06]   [published]
    On the use of training sequences for channel estimation    
    IEEE Transactions on Information Theory, vol. 52, no 3, p. 1171-1176
    Suppose Q is a family of discrete memoryless channels. An unknown member of Q will be available, with perfect, causal output feedback for communication. We study a scenario where communication is carried by first testing the channel by means of a training sequence, then coding according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such coding scheme. If we consider the Binary Symmetric and the Z families of channels this bound is much lower than Burnashev's exponent. For example, in the case of Binary Symmetric Channels this bound has a slope that vanishes at capacity. This is to be compared with our previous result that demonstrates the existence of coding schemes that achieve Burnashev's exponent (that has a nonzero slope at capacity) even though the channel is revealed neither to the transmitter nor to the receiver. Hence, the present result suggests that, in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.
    
    
77. Piorkowski, Michal; Grossglauser, Matthias   [PiorkowskiG:06]   [published]
    Constrained Tracking on a Road Network    
    European Workshop on Wireless Sensor Networks EWSN2006; ETH Zurich, Switzerland, February 13-15, 2006
    Many applications of wireless ad hoc sensor and actuator networks (WSANs) rely on the knowledge of node locations. These are challenging to obtain when nodes are mobile and are not equipped with any expensive positioning hardware. In this paper, we are interested in scenarios where there are constraints on the movement of nodes, such as with cars on the road network. We develop and analyse a tracking algorithm called MOONwalk, which explicitly takes such constraints into account in order to improve the tracking precision. Furthermore, MOONwalk does not require global knowledge of the network, and therefore lends itself well to large-scale and high-mobility applications. We evaluate the accuracy of MOONwalk by comparing it to the optimal maximum likelihood estimator, under different radio conditions and deployment scenarios. We find that MOONwalk performs well despite its localized operation.
    
    
78. Olivier Dousse, Massimo Franceschetti and Patrick Thiran   [DousseFT:06]   [published]
    A case for partial connectivity in large wireless multi-hop networks    
    Information Theory and Applications Inaugural Workshop, UC San Diego, 6-10 Feb 06
    As in every other network, nodes of a wireless multi-hop network must be well connected. Unlike many other networks, some wireless multi-hop networks (e.g., sensor networks), do not necessarily require full connectivity of all the nodes of the networks. In this paper, we show the beneits of replacing this usual requirement by that of a partial, alpha-connectivity, where only a given fraction alpha < 1 of the nodes needs to be connected to the network. This feature is found in models neglecting interferences, taking interferences as noise or taking a more information theoretic approach. The paper summarizes and updates the results in our previous paper [1]
    
    
79. F. Oggier, N. Sloane, S. Diggavi, A. Calderbank   [OggierSDC:05]   [published]
    Nonintersecting subspaces based on finite alphabets    
    IEEE Transactions on Information Theory, Volume 51, Issue 12, Dec. 2005
    
    
    
80. Goseling, Jasper; Diggavi, Suhas N.   [GoselingD:05]   [published]
    Scaling Laws for Energy-constrained Wireless Networks    
    Technical Report EPFL-LICOS 2005-002
    Although there has been much interest in scaling laws for wireless networks, most work has focussed on characterizing throughput and delay in power-constrained networks. Energy-constrained networks have not received much attention. Previous work on energy-constrained networks was based on models that ignored interference. In this work energy-constrained networks are studied, taking interferences into account. The number of bits per unit energy is introduced, a quantity that measures performance of a wireless network in terms of energy consumption. Scaling laws for the number of bits per unit energy are analyzed on a extended random wireless network using the physical model. An upper bound is given and it is shown that it is achievable. The tradeoff between the number of bits per unit energy and the average bit delay is characterized. Finally, it is shown that there is no tension between the throughput and the number of bits per unit energy, i.e.\ they can be simultaneously optimized. [pdf]
    
    
81. S. Diggavi, M. Grossglauser, D. Tse   [DiggaviGT:05]   [published]
    Even One-Dimensional Mobility Increases the Capacity of Wireless Networks    
    IEEE Transactions on Information Theory, Volume 51, Issue 11, Nov. 2005
    
    
    
82. S. Das; N. Al-Dhahir; S. N. Diggavi; A. R. Calderbank   [DasADC:05]   [published]
    Opportunistic Space-Time Block Codes    
    Proceedings of IEEE Vehicular Technology Conference, Dallas, Texas, USA, 2005, p. 2025--2029
    
    
    
83. A R. Calderbank; S. Das; N. Al-Dhahir; Diggavi, S. N.   [CalderbankDAD:05]   [published]
    A Novel Full-Rate Full-Diversity STBC with Application to WiMAX    
    Proceedings of IEEE Vehicular Technology Conference, Dallas, Texas, USA, p. 1791--1795
    
    
    
84. Dousse, Olivier; Nguyen, Hung X.; Thiran, Patrick   [DousseNT:05]   [published]
    Deux applications de processus ponctuels aux réseaux de communication    
    GRETSI; Louvain-la-Neuve, Belgium
    This paper (in Frensh) summarizes recent results obtained by using shot noise processes for two applications in communication networks: first, TCP/IP traffic models for backbone networks; and next the study of connectivity under rate constraints in wireless ad hoc networks. [pdf]
    
    
85. Tchamkerten, A; Telatar, E   [TchamkertenT:05b]   [published]
    On the use of training sequences for channel estimation    
    International Symposium on Information Theory 2005; Adelaide, Australia, 4-9 September 2005, p. 1391-1395
    Suppose Q is a family of discrete memoryless channels. An unknown member of Q is available with perfect (causal) feedback for communication. A recent result (A. Tchamkerten and I.E. Telatar) shows the existence, for certain families of channels (e.g. binary symmetric channels and Z channels), of coding schemes that achieve Burnashev's exponent universally over these families. In other words, in certain cases, there is no loss in the error exponent by ignoring the channel: transmitter and receiver can design optimal blind coding schemes that perform as well as the best feedback coding schemes tuned for the channel under use. Here we study the situation where communication is carried by first testing the channel by means of a training sequence, then coding the information according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such scheme. If we consider binary symmetric channels and Z channels this bound is much lower than Burnashev's exponent. This suggests that in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.
    
    
86. Tchamkerten, A; Telatar, E   [TchamkertenT:05d]   [published]
    On the universality of Burnashev's error exponent    
    International Symposium on Information Theory 2005; Adelaide, Australia, 4-9 September 2005, p. 1382-1385
    We consider communication over a time invariant discrete memoryless channel with noiseless and instantaneous feedback. We assume that the communicating parties are not aware of the underlying channel, however they know that it belongs to some specific family of discrete memoryless channels. Recent results (A. Tchamkerten and I.E. Telatar) show that for certain families (e.g., binary symmetric channels and Z channels) there exists coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent.
    
    
87. Diggavi, S. N.; Tse, D. N. C.   [DiggaviT:05]   [published]
    Fundamental limits of diversity-embedded codes over fading channels    
    IEEE International Symposium on Information Theory,Adelaide, Australia, p. 510--514
    
    
    
88. Tchamkerten, A; Telatar, E   [TchamkertenT:05]   [published]
    On the universality of Burnashev's error exponent    
    IEEE Transactions on Information Theory, vol. 51, no 8, p. 2940-2944
    We consider communication over a time-invariant discrete memoryless channel (DMC) with noiseless and instantaneous feedback. We assume that the transmitter and the receiver are not aware of the underlying channel, however, they know that it belongs to some specific family of DMCs. Recent results show that for certain families (e.g., binary-symmetric channels and Z channels) there exist coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent.
    
    
89. Dousse, Olivier; Thiran, Patrick   [Dousse:05]   [published]
    Asymptotic properties of wireless multi-hop networks    
    PhD thesis EPFL, accepted in Aug 2005 (Prof. P. Thiran)
    In this dissertation, we consider wireless multi-hop networks, where the nodes are randomly placed. We are particularly interested in their asymptotic properties when the number of nodes tends to infinity. We use percolation theory as our main tool of analysis.

    As a first model, we assume that nodes have a fixed connectivity range, and can establish wireless links to all nodes within this range, but no other (Boolean model). We compute for one-dimensional networks the probability that two nodes are connected, given the distance between them. We show that this probability tends exponentially to zero when the distance increases, proving that pure multi-hopping does not work in large networks. In two dimensions however, an unbounded cluster of connected nodes forms if the node density is above a critical threshold (super-critical phase). This is known as the percolation phenomenon. This cluster contains a positive fraction of the nodes that depends on the node density, and remains constant as the network size increases. Furthermore, the fraction of connected nodes tends rapidly to one when the node density is above the threshold. We compare this partial connectivity to full connectivity, and show that the requirement for full connectivity leads to vanishing throughput when the network size increases. In contrast, partial connectivity is perfectly scalable, at the cost of a tiny fraction of the nodes being disconnected.

    We consider two other connectivity models. The first one is a signal-to-interference- plus-noise-ratio based connectivity graph (STIRG). In this model, we assume deterministic attenuation of the signals as a function of distance. We prove that percolation occurs in this model in a similar way as in the previous model, and study in detail the domain of parameters where it occurs. We show in particular that the assumptions on the attenuation function dramatically impact the results: the commonly used power-law attenuation leads to particular symmetry properties. However, physics imposes that the received signal cannot be stronger than the emitted signal, implying a bounded attenuation function. We observe that percolation is harder to achieve in most cases with such an attenuation function.

    The second model is an information theoretic view on connectivity, where two arbitrary nodes are considered connected if it is possible to transmit data from one to the other at a given rate. We show that in this model the same partial connectivity can be achieved in a scalable way as in the Boolean model. This result is however a pure connectivity result in the sense that there is no competition and interferences between data flows. We also look at the other extreme, the Gupta and Kumar scenario, where all nodes want to transmit data simultaneously. We show first that under point-to-point communication and bounded attenuation function the total transport capacity of a fixed area network is bounded from above by a constant, whatever the number of nodes may be. However, if the network area increases linearly with the number of nodes (constant density), or if we assume power-law attenuation function, a throughput per node of order 1/√n can be achieved. This latter result improves the existing results about random networks by a factor (log n)1/2.

    In the last part of this dissertation, we address two problems related to latency. The first one is an intruder detection scenario, where a static sensor network has to detect an intruder that moves with constant speed along a straight line. We compute an upper bound to the time needed to detect the intruder, under the assumption that detection by disconnected sensors does not count. In the second scenario, sensors switch off their radio device for random periods, in order to save energy. This affects the delivery of alert messages, since they may have to wait for relays to turn on their radio to move further. We show that asymptotically, alert messages propagate with constant, deterministic speed in such networks. [pdf]
    
    

90. Dousse, Olivier; Baccelli, Francois; Thiran, Patrick   [DousseBT:05]   [published]
    Impact of Interferences on Connectivity in Ad Hoc Networks    
    IEEE/ACM Trans. on Networking, 2005, vol. 13, no 2, p. 425-436
    We study the impact of interferences on the connectivity of large-scale ad-hoc networks, using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at the receiver is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient gamma, and of a background noise. We find that there is a critical value of gamma above which the network is made of disconnected clusters of nodes. We also prove that if gamma is non zero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of gamma cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every n-th time slot. We show that it achieves connectivity similar to the previous system with a parameter gamma/n. [pdf]
    
    
91. S. Chen; S. N. Diggavi; S. Dusad; Muthukrishnan, S.   [ChenDDM:05]   [published]
    Efficient String Matching Algorithms for Combinatorial Universal Denoising    
    IEEE Data Compression Conference (DCC); Snow Bird, UTAH, March 2005
    Inspired by the combinatorial denoising method {\tt DUDE} \cite{WOSVW04}, we present efficient algorithms for implementing this idea for arbitrary contexts or for using it within subsequences. We also propose effective, efficient denoising error estimators so we can find the best denoising of an input sequence over different context lengths. Our methods are simple, drawing from string matching methods and radix sorting. We also present experimental results of our proposed algorithms.
    
    
92. Dousse, Olivier; Franceschetti, Massimo; Thiran, Patrick   [DousseFT:05]   [published]
    Information theoretic bounds on the throughput scaling of wireless relay networks    
    Infocom; Miami, 2005
    The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed non-zero rate imply some of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes. [PDF]
    
    
93. Durvy, Mathilde; Thiran, Patrick   [DurvyT:05]   [published]
    Reaction-Diffusion Based Transmission Patterns for Ad Hoc Networks    
    Infocom; Miami
    We present a new scheme that mimics pattern formation in biological systems to create transmission patterns in multi-hop ad hoc networks. Our scheme is decentralized and relies exclusively on local interactions between the network nodes to create global transmission patterns. A transmission inhibits other transmissions in its immediate surrounding and encourages nodes located further away to transmit. The transmission patterns created by our medium access control scheme combine the efficiency of allocation-based schemes at high traffic loads and the flexibility of random access schemes. Moreover, we show that with appropriately chosen parameters our scheme converges to collision free transmission patterns that guarantee some degree of spatial reuse. [PDF]
    
    
94. Lévêque, Olivier; Telatar, Emre   [LevequeT:05]   [published]
    Information-Theoretic Upper Bounds on the Capacity of Large Extended Ad Hoc Wireless Networks    
    IEEE Transactions on Information Theory, vol. 51, no 3, p. 858-865
    We derive an information-theoretic upper bound on the rate per communication pair in a large ad hoc wireless network. We show that under minimal conditions on the attenuation due to the environment and for networks with a constant density of users, this rate tends to zero as the number of users gets large. [pdf]
    
    
95. Sibi Raj and Emre Telatar   [RajT:05]   [published]
    Queuing and Scheduling in Multiuser Communications    
    Winter School on Coding and Information Theory, Bratislava, 20-25 Feb 05
    [pdf]
    
    
96. Diggavi, S. N.; Vaishampayan, V. A.   [DiggaviV:04]   [published]
    On multiple description source coding with decoder side information    
    Information Theory Workshop (ITW), San Antonio
    
    
    
97. Dousse, Olivier; Franceschetti, Massimo; Thiran, Patrick   [DousseFT:04]   [published]
    The Costly Path from Percolation to Full Connectivity    
    Allerton Conference; Monticello IL, 2004
    Requiring all nodes of a wireless multihop network to be connected is expensive and results in a poor scalability of properties such as transport capacity. We show however that it is no longer the case if we only slightly loosen the connectivity requirement, by just imposing that most nodes be connected to each other (so that the network ``percolates``). This feature is found in models neglecting interferences, taking interferences as noise or taking a more information theoretic approach. [pdf]
    
    
98. Tchamkerte, A; Telatar, E   [TchamkertenT:04]   [published]
    Optimal feedback schemes over unknown channels    
    International Symposium on Information Theory ; Chicago, USA, 27 June - 2 July 2004, p. 378-378
    Communication over unknown discrete memoryless channels with instantaneous and perfect feedback is considered. For a given set of channels we define a notion of optimal coding schemes in terms of achievable rate and error exponent, and prove the existence of such coding schemes for two families of channels.
    
    
99. Franceschetti, Massimo; Dousse, Olivier; Tse, David; Thiran, Patrick   [FranceschettiDTT:04]   [published]
    Closing the gap in the capacity of random wireless networks    
    ISIT 2004; Chicago, 2004
    We consider the problem of how throughput in a wireless network with randomly located nodes scales as the number of users grows. Following the physical model of Gupta and Kumar, we show that randomly scattered nodes can achieve the optimal 1/sqrt(n) per-node transmission rate of arbitrarily located nodes. This contrasts with previous achievable results suggesting that a 1/sqrt(n log(n)) reduced rate is the price to pay for the additional randomness introduced into the system. Of independent interest is that we directly apply results from percolation theory to prove our result. [pdf]
    
    
100. Lévêque, Olivier; Telatar, Emre   [LévêqueT:04]   [published]
     Information theoretic upper bounds on the capacity of large extended ad-hoc wireless networks    
     IEEE International Symposium on Information Theory; Chicago, USA, 27 June - 2 July 2004
     We derive an information theoretic upper bound on the maximum achievable rate per communication pair in a large extended ad-hoc wireless network. We show that under a reasonably weak assumption on the attenuation due to environment, this rate tends to zero as the number of users gets large. [pdf]
     
     
101. A R. Calderbank; S. N. Diggavi; S. Das; Al-Dhahir, N.   [CalderbankDDA:04]   [published]
     Construction and analysis of a new 4 x 4 orthogonal space-time block code    
     IEEE International Symposium on Information Theory (ISIT2004), Chicago, 27 Jun - 2 Jul 04
     
     
     
102. A R. Calderbank; S. N. Diggavi; N. Al Dhahir   [CalderbankDA:04]   [published]
     Space-time signaling based on Kerdock and Delsarte-Goethals codes    
     IEEE International Conference on Communications (ICC) Paris, 2004, p. 483--487
     
     
     
103. Dousse, Olivier; Mannersalo, Petteri; Thiran, Patrick   [DousseMT:04]   [published]
     Latency of wireless sensor networks with uncoordinated power saving mechanisms    
     Mobihoc; Tokyo, 2004, p. 109-120
     We consider a wireless sensor network, where nodes switch between an active (on) and a sleeping (off) mode, to save energy. Their switching on/off schedules are completely non-coordinated. Their positions are distributed according to a Poisson process, and their connectivity range is larger or equal to their sensing range. The durations of active and sleeping periods are such that the number of active nodes at any particular time is so low that the network is always disconnected. Is it possible to use such a network for time-critical monitoring of an area? Such a scenario requires indeed to have bounds on the latency, which is the delay elapsed between the time at which an incoming event is sensed by some node of the network, and the time at which this information is retrieved by the data collecting sink. A positive answer is provided to this question under some assumptions discussed in the paper. More precisely, we prove that the messages sent by a sensing node reach the sink with a fixed asymptotic speed, which does not depend on the random location of the nodes, but only on the network parameters (node density, connectivity range, duration of active and sleeping periods). The results are obtained rigorously by using an extension of first passage percolation theory. [pdf]
     
     
104. Sarafijanovic-Djukic, Natasa; Grossglauser, Matthias   [Sarafijanovic-DjukicG:04]   [published]
     Last Encounter Routing under Random Waypoint Mobility    
     Networking 2004; Athens, Greece, 2004, p. 974-988
     Last Encounter Routing (LER) algorithms for mobile ad hoc networks rely only on encounter histories at every node to route packets, and therefore do not need control traffic to track topology changes due to node mobility. LER exploits the fact that past information about a node`s mobility helps to locate that node in the future. As we have pointed out in earlier work \cite{mg}, the performance of LER algorithms depends on the mobility processes of nodes. In this paper, we ask whether LER can work under the random waypoint (RWP) mobility model. This question is important for several reasons. First, as shown in \cite{mg}, a good performance for the RWP model is harder to achieve than for another prominent mobility model, the random walk. This is because the RWP model has a much shorter relaxation time, i.e., a time-horizon over which past information is still useful. Also, the RWP model has a much less favorable ratio of number of encounters between nodes and the traveled distance. Second, in contrast to the random walk, the RWP model is predictable. This provides us with an opportunity to exploit additional information collected in an encounter (such as speed, direction, etc.) to improve routing. We formally define the RWP model, and compute the optimal predictors for several observation sets, i.e., observed parameters of node mobility. We develop a new LER algorithm tuned to the RWP model called GREASE-RWP, and present simulation results that demonstrate that an efficient and scalable LER for the RWP model is possible. [pdf]
     
     
105. Dousse, Olivier; Thiran, Patrick   [DousseT:04]   [published]
     Connectivity vs Capacity in Dense Ad Hoc Networks    
     IEEE Infocom; Hong Kong, 2004
     We study the connectivity and capacity of finite area ad hoc wireless networks, with an increasing number of nodes (dense networks). We find that the properties of the network strongly depend on the shape of the attenuation function. For power law attenuation functions, connectivity scales, and the available rate per node is known to decrease like 1/sqrt(n). On the contrary, if the attenuation function does not have a singularity at the origin and is uniformly bounded, we obtain bounds on the percolation domain for large node densities, which show that either the network becomes disconnected, or the available rate per node decreases like 1/n. [pdf]
     
     
106. N. Duffield, M. Grossglauser   [DuffieldG:04]   [published]
     Trajectory sampling with unreliable reporting    
     IEEE Infocom 2004, Hong-Kong, 7-11 March 04
     
     
     
107. Diggavi, S N.; Al-Dhahir, N; Stamoulis, A; Calderbank, A R.   [DiggaviASC:04]   [published]
     Great expectations: the value of spatial diversity in wireless networks    
     Proceedings of the IEEE, vol. 92, no 2, p. 217--270
     
     
     
108. Chiurtu, Nicolae; Rimoldi, Bixio; Telatar, Emre; Pauli, Volker   [ChiurtuRTP:03]   [published]
     Impact of correlation and coupling on the capacity of MIMO systems    
     2003 ISSPIT
     In this work we consider multiple antenna systems in which a large number of antennas occupy a given physical volume and we investigate the behavior of the capacity when increasing the number of antennas. In this regime the assumptions of the standard multiple antenna models become questionable. We introduce several new channel models that better fit this scenario and show that for such ''spatially dense'' multiple antenna systems one should expect the behavior of the capacity to be qualitatively different than what the standard multiple antenna models predict.
     
     
109. S N. Diggavi; N. Al-Dhahir; Calderbank, A. R.   [DiggaviAC:03]   [published]
     Diversity-embedded space-time codes    
     IEEE GLOBECOM San Francisco, p. 1909--1914
     
     
     
110. Dubois-Ferrière, Henri; Grossglauser, Matthias; Vetterli, Martin   [Dubois-FerriereGV:03b]   [published]
     Space-Time Routing in Ad Hoc Networks    
     Proc. 2nd International Conference on AD-HOC Networks and Wireless (also app. in Lecture Notes in Computer Science, Nr. 2865)
     [pdf]
     
     
111. M. Grossglauser, D. Tse   [GrossglauserT:03]   [published]
     A time-scale decomposition approach to measurement-based admission control    
     IEEE Transactions on Networking, Volume 11, Issue 4, Aug 2003
     
     
     
112. Staab, Steffen; Heylighen, F.; Gershenson, C.; William Flake, G.; Pennock, D. M.; Fain, D. C.; De Roure, D.; Aberer, Karl; Shen, Wei-Min; Dousse, O.; Thiran, P.   [StaabHGFPFRASDT:03]   [published]
     Neurons, Viscose Fluids, Freshwater Polyp Hydra-and Self-Organizing Information Systems    
     IEEE Intelligent Systems, vol. 18, no 4, p. 72-86
     [pdf]
     
     
113. Tchamkerten, A; Telatar, E   [TchamkertenT:03]   [published]
     Reliability and latency in binary communication    
     IEEE International Symposium on Information Theory; Yokohama, Japan, 29 June - 4 July 2003, p. 116
     The transmission of one of two messages over a binary symmetric channels with perfect and instantaneous feedback is considered. We study the situation where transmitter and receiver want to communicated reliably and quickly. We propose a simple decoding rule, and show that it minimizes the weighted combination of the probability of error and decoding delay for a certain range of crossover probabilities and combination weights.
     
     
114. Dubois-Ferrière, Henri; Grossglauser, Matthias; Vetterli, Martin   [Dubois-FerriereGV:03]   [published]
     Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages    
     Proc ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), p. 257-266
     We propose FResher Encounter SearcH (FRESH), a simple algorithm for efficient route discovery in mobile ad hoc networks. Nodes keep a record of their most recent encounter times with all other nodes. Instead of searching for the destination, the source node searches for any intermediate node that encountered the destination {\em more recently than did the source node itself}. The intermediate node then searches for a node that encountered the destination yet more recently, and the procedure iterates until the destination is reached. Therefore, FRESH replaces the single network-wide search of current proposals with a succession of smaller searches, resulting in a cheaper route discovery. Routes obtained are loop-free. The performance of such a scheme will depend on the nodes' mobility processes. Under standard mobility processes our simulations show that route discovery cost can be decreased by an order of magnitude, a significant gain given that route discovery is a major source of routing overhead in ad hoc networks. [ps]
     
     
115. Dousse, Olivier; Baccelli, Francois; Thiran, Patrick   [DousseBT:03]   [published]
     Impact of Interferences on Connectivity in Ad Hoc Networks    
     Infocom; San Francisco, 2003
     We study the impact of interferences on the connectivity of large-scale ad-hoc networks, using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at reception is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient g, and of a background noise. We find that there is a critical value of g above which the network is made of disconnected clusters of nodes. We also prove that if g is non zero but small enough, there exist node spatial densities at which the network contains an large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of g cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every n-th time slot. We show qualitatively that it even achieves a better connectivity than the previous system with a parameter g/n. [pdf]
     
     
116. Grossglauser, Matthias; Vetterli, Martin   [GrossglauserV:03b]   [published]
     Locating nodes with EASE: last encounter routing for Ad Hoc networks through mobility diffusion    
     Proc. IEEE Infocom, vol. 3, p. 1954-1964
     
     
     
117. Sibi Raj, Emre Telatar, David Tse   [RajTT:03]   [published]
     Job Scheduling and Multiple Access    
     DIMACS Workshop on Network Information Theory, 17-19 Mar 03, Rutgers Univ.
     We establish an analogy between the additive Gaussian multiple access channel and multi-processor queues. We exploit this analogy to investigate certain problems arising in multiple access information theory. In particular we address the question of minimal average delay for multiple users, each with a finite bit pool, and then a multiple access channel with users arriving according to a Poisson process. In the latter case, we show that the system is stable under all arrival rates, and show that the communication analog of shorter-tasks-faster strategy is close to optimal for high arrival rates.
     
     
118. Tchamkerten, A; Telatar, E   [TchamkertenT:02]   [published]
     A feedback strategy for binary symmetric channels    
     IEEE International Symposium on Information Theory 2002; Lausanne, Switzerland, 30 June - 5 July 2002, p. 362
     Communication over unknown binary symmetric channels with instantaneous and perfect feedback is considered. We describe a universal scheme based on a decision feedback strategy. [pdf]
     
     
119. Dousse, O.; Thiran, P.; Hasler, M.   [DousseTH:02]   [published]
     Connectivity in ad-hoc and hybrid networks    
     Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002); New York, 23-27 June 2002, vol. 2, p. 1079-1088
     We consider a large-scale wireless network, but with a low density of nodes per unit area. Interferences are then less critical, contrary to connectivity. This paper studies the latter property for both a purely ad-hoc network and a hybrid network, where fixed base stations can be reached in multiple hops. We assume here that power constraints are modeled by a maximal distance above which two nodes are not (directly) connected. We find that the introduction of a sparse network of base stations does significantly help in increasing the connectivity, but only when the node density is much larger in one dimension than in the other. We explain the results by percolation theory. We obtain analytical expressions of the probability of connectivity in the 1-dim. case. We also show that at a low spatial density of nodes, bottlenecks are unavoidable. Results obtained on actual population data confirm our findings. [pdf]