home > Publications > Search

Found 89 publications with these criteria

1. Poturalski, Marcin; Flury, Manuel; Papadimitratos, Panagiotis; Hubaux, Jean-Pierre; Le Boudec, Jean-Yves   [PoturalskiFPHL:10]   [accepted]
   The Cicada Attack: Degradation and Denial of Service in IR Ranging    
   International Conference on Ultra-Wideband; Nanjing, China, September 20-23, 2010
   We demonstrate that an interferer with malicious intentions can significantly degrade the performance of impulse radio (IR) ranging. The cicada attack we have developed can decrease the distance (degradation of service) measured by ranging algorithms designed to cope with weak NLOS conditions; it can also jam communication (denial of service). The attack is easy to mount and can be effective even against receivers designed to cope with benign multi-user interference. We also sketch possible countermeasures.
   
   
2. Hai Zhan, Jean-Yves Le Boudec, Jaouhar Ayadi and John Farserotu   [ZhanLAF:10]   [published]
   Ziv-Zakai Lower Bound for Impulse Radio Ultra-WideBand Ranging Error Based on Geometry of Indoor Environments    
   International Conference on Communications, Cape Town, 23-27 May 2010
   We discuss Ziv-Zakai lower bound for IR-UWB ranging error based on geometry of indoor environments.
   
   
3. Hai Zhan, Jean-Yves Le Boudec, Jaouhar Ayadi and John Farserotu   [ZhanLAF:10b]   [published]
   Theoretical Limit of Impulse Radio Ultra-WideBand TOA Positioning and TDOA Positioning    
   IEEE International Conference on Communications, Cape Town, 23-27 May 2010
   We discuss the theoretical limit of IR-UWB TOA positioning and TDOA positioning.
   
   
4. Flury, Manuel; Poturalski, Marcin; Papadimitratos, Panos; Hubaux, Jean-Pierre; Le Boudec, Jean-Yves   [FluryPPHL:10]   [published]
   Effectiveness of Distance-Decreasing Attacks Against Impulse Radio Ranging    
   3rd ACM Conference on Wireless Network Security (WiSec); Hoboken, New Jersey, USA, March 22-24, 2010
   We expose the vulnerability of an emerging wireless ranging technology, impulse radio ultra-wide band (IR-UWB), to distance-decreasing attacks on the physical communication layer (PHY). These attacks violate the security of secure ranging protocols that allow two wireless devices to securely estimate the distance between them, with the guarantee that the estimate is an upper-bound on the actual distance. Such protocols serve as crucial building blocks in security-sensitive applications such as location tracking, physical access control, or localization. Prior works show the theoretical possibility of PHY attacks bypassing cryptographic mechanisms used by secure ranging protocols. They also demonstrates that for physical layers used in ISO 14443 RFID and wireless sensor networks, some PHY attacks are indeed feasible. IR-UWB was proposed as a possible solution, but we show that the de facto standard for IR-UWB, IEEE 802.15.4a, does not automatically provide security against such attacks. We find that with the mandatory modes of the standard an external attacker can decrease the measured distance by as much as 140 meters with a high probability (above 99%).
   
   
5. Julien Freudiger, Mohammad Hossein Manshael, Jean-Yves Le Boudec, Jean-Pierre Hubaux   [FreudigerMLH:10]   [published]
   On the Age of Pseudonyms in Mobile Ad Hoc Networks    
   IEEE Infocom 2010, San Diego, 15-19 Mar 10
   
   
   
6. Liang Hu, Jean-Yves Le Boudec, Milan Vojnovic   [HuLV:10]   [published]
   Optimal Channel Choice for Collaborative Ad-Hoc Dissemination    
   IEEE Infocom 2010, San Diego, 15-19 Mar 10
   
   
   
7. Zhan, Hai; Ayadi, Jaouhar; Farserotu, John; Le Boudec, Jean-Yves   [ZhanAFL:09]   [published]
   Impulse Radio Ultra-Wideband Ranging Based on Maximum Likelihood Estimation    
   IEEE Transactions on Wireless Communications, vol. 8, no 12, p. 5852 - 586
   We propose a high-resolution ranging algorithm for impulse radio (IR) ultra-WideBand (UWB) communication systems in additive white Gaussian noise. We formulate the ranging problem as a maximum- likelihood (ML) estimation problem for the channel delays and amplitudes at the receiver. Then we translate the obtained delay estimates into an estimate of the distance. The ML estimation problem is a non-linear problem and is hard to solve. Some previous works focus on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of Iterative quadratic maximum likelihood (IQML) and we transform the ML problem into another optimization problem that avoids the estimation of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach (pseudo-quadratic maximum likelihood (PQML) algorithm). To demonstrate the good performance of the proposed estimator, we present the numerical evaluations under the IEEE 802.15.4a channel model. We show that our algorithm performs significantly better than previously published heuristics. We also derive a reduced complexity version of the algorithm algorithm, which will be implemented on the Xinlix field-programmable gate array (FPGA) board in the future. We test the approach in a real weak line of sight (LOS) propagation environment and obtained good accuracy for the ranging.
   
   
8. Flury, Manuel; Merz, Ruben; Le Boudec, Jean-Yves   [FluryML:09]   [published]
   Robust IEEE 802.15.4a Energy Detection Receiver Using Statistical Interference Modeling    
   Asilomar Conference on Signals, Systems, and Computers; Pacific Grove, CA, USA, November 2009
   Energy-detection is appealing for IEEE 802.15.4a receivers as it allows to exploit the ranging capabilities and the multipath resistance of impulse-radio UWB at a reasonable complexity. IEEE 802.15.4a receivers operate with interference created by uncontrolled piconets and an uncoordinated medium access control. Prior work showed that the performance of an energydetection based receiver is greatly degraded in such scenarios. Hence, we present an interference mitigation algorithm based on statistical interference modeling for energy-detection receivers. This combines a low complexity architecture and robustness to interference. Our performance evaluation shows that our solution decreases the packet error rate significantly.
   
   
9. Flury, Manuel; Merz, Ruben; Le Boudec, Jean-Yves   [FluryML:09]   [published]
   Robust Non-Coherent Timing Acquisition in IEEE 802.15.4a IR-UWB Networks    
   20th Personal, Indoor and Mobile Radio Communications Symposium 2009 (PIMRC'09); Tokyo, Japan, September 13-16, 2009
   Non-coherent energy-detection receivers are an attractive choice for IEEE 802.15.4a networks. They can exploit the ranging capabilities and the multipath resistance of impulse-radio ultra-wide band (IR-UWB) at a low complexity. However, IEEE 802.15.4a receivers operate with interference created by uncontrolled piconets and an uncoordinated medium access control layer. The performance of an energy-detection IR-UWB receiver is greatly degraded in such scenarios, for both timing acquisition and decoding. In this paper, we focus on timing acquisition: we present PICNIC, a robust and low-complexity algorithm that allows for reliable timing acquisition with an IR-UWB energy-detection receiver in the presence of multi-user interference (MUI), even in near-far scenarios. At the cost of a negligible performance reduction in single-user scenarios, PICNIC outperforms classic timing acquisition algorithms by up to two orders of magnitude if MUI is present. Furthermore, PICNIC exhibits a near perfect capture property: if several transmitters compete for timing acquisition at the receiver, one signal will be acquired with practically no false detection.
   
   
10. Flury, Manuel; Merz, Ruben; Le Boudec, Jean-Yves   [FluryML:09]   [published]
    Clock-Offset Tracking Software Algorithms For IR-UWB Energy-Detection Receivers    
    IEEE International Conference on Ultra-Wideband (ICUWB 2009); Vancouver, Canada, September 9-11, 2009, p. 534-539
    We present a clock-offset tracking algorithm for impulse-radio ultra-wide band (IR-UWB) energy-detection receivers. There is a complexity versus performance trade-off for the design of IR-UWB energy-detection receivers: Extremely low-complexity energy-detection receivers are built with a large, constant integration duration; they are robust to clock drifts but are sensitive to noise enhancement effects and cannot adapt to channel variations. More sophisticated energy-detection receivers use a shorter integration duration and combine several weighted outputs of the energy collector; they are robust to noise enhancement effects, can adapt to channel variations and offer a much better performance than non-adaptive receivers. However, they become sensitive to clock offsets. Hence, there is a need for low-complexity clock-offset tracking solutions to support adaptive energy-detection receivers. Our solution is constructed around the Radon transform, an image processing tool traditionally used to detect line features in images. Our solution is fully compatible with the IEEE 802.15.4a standard, does not increase the hardware complexity of the receiver and reduces the performance loss due to clock offset to less than 0.5 dB.
    
    
11. James Colli-Vignarelli, Jérôme Vernez, Ruben Merz , Catherine Dehollain, Stephan Robert, Jean-Yves Le Boudec   [Colli-VignarelliVMDRL:09]   [published]
    Concurrent Transmissions in IR-UWB Networks : an Experimental Validation    
    IEEE International Conference on Ultra-Wideband (ICUWB 2009), Vancouver, 9-11 Sep 09
    We experimentally demonstrate and validate that concurrent and parallel transmissions are feasible for low data-rate impulseradio ultra-wide band (IR-UWB) physical layers. The optimal organization for a low data-rate IR-UWB network is to allow for concurrent transmissions at the link layer, and to use interference mitigation techniques at the physical layer. In fact, even low data-rate IR-UWB physical layers can suffer from multi-user interference (MUI), especially in near-far scenarios. However, the practical feasibility of such a design has yet to be experimentally tested and validated. Therefore, we perform an experimental validation with a packet-based, low data-rate IR-UWB physical layer testbed. Our results clearly demonstrate that concurrent IR-UWB transmissions are possible. This shows that completely uncoordinated low data-rate IR-UWB networks are feasible. We also demonstrate that, in the presence of MUI, an interference mitigation scheme at the physical layer is indeed necessary. Because it is the first component for the proper receiption of a packet, we focus on packet detection and timing acquisition. We show that a traditional scheme is not robust against multiuser interference, and prevents concurrent transmissions. On the contrary, a scheme designed to take MUI into account, even with a very simple interference mitigation scheme, allows for concurrent transmissions, even in strong near-far scenarios. [pdf]
    
    
12. Hai Zhan, Jean-Yves Le Boudec, Jaouhar Ayadi and John Farserotu   [ZhanLAF:09c]   [published]
    One Step Impulse Radio Ultra-WideBand Positioning Algorithm    
    IEEE International Conference on Ultra-Wideband (ICUWB 2009), Vancouver, 9-11 Sep 09
    One Step Impulse Radio Ultra-Wideband Positioning Algorithm.
    
    
13. Hai Zhan, Jean-Yves Le Boudec, Jaouhar Ayadi and John Farserotu   [ZhanLAF:09b]   [published]
    Novel Algorithms on Impulse Radio Ultra-WideBand Ranging    
    IEEE International Workshop on Statistical Signal Processing (SSP2009), Cardiff, 31.8-3.9.09
    LOS/NLOS identification
    
    
14. Hai Zhan, Jean-Yves Le Boudec, Jaouhar Ayadi and John Farserotu   [ZhanLAF:09]   [published]
    A Novel Bayesian Impulse Radio Ultra-WideBand Ranging Algorithm Based on Importance Sampling    
    International Conference on Computer Communications and Networks (ICCCN 2009), San Francisco, 2-6 Aug 09
    We consider the problem of ranging with Impulse Radio (IR) Ultra-WideBand (UWB) radio under weak Line Of Sight (LOS) environments and additive Gaussian noise. We use a Bayesian approach where the prior distribution of the channel follows the IEEE 802.15.4a channel model, to estimate the joint posterior probability density function (pdf) of the channel and the targeted distance. One of applications of the joint posterior pdf of the channel and the targeted distance is the ranging determination with classical posterior estimators (such as Minimum Mean Square Error Estimator (MMSE)). For computing the joint posterior pdf of the channel and the targeted distance, we derived a novel algorithm which is based on importance sampling and expectation maximum techniques. Furthermore, we propose a reduced-complexity architecture of IR UWB ranging system using our proposed algorithm. The complexity analysis of the algorithm shows the proposed algorithm is a low-complexity one. Numerical evaluations under the IEEE 802.15.4a channel model are presented to demonstrate the good performance of the proposed estimator.
    
    
15. Hai Zhan, Jaouhar Ayadi, John Farserotu and Jean-Yves Le Boudec   [ZhanAFL:09b]   [published]
    Impulse Radio Ultra-Wideband Ranging Algorithm under Multi-User Environments    
    IEEE Vehicular Technology Conference Spring, Barcelona, 23-29 Apr 09
    Impulse Radio Ultra-Wideband Ranging Algorithm under Multi-User Environments
    
    
16. Jean-Yves Le Boudec, Ruben Merz   [LeBoudecM:08]   [published]
    Concurrent and Parallel Transmissions are Optimal for Low Data-Rate IR-UWB Networks    
    IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008), Cannes, France, September 15-18 2008
    The Internet of Things, emerging pervasive and sensor networks are low data-rate wireless networks with, a priori, no specific topology and no fixed infrastructure. Their primary requirements are twofold: First, low power consumption and, due to environmental concerns, low emitted power. Second, robustness to poor propagation environments and multi-user interference. Impulse-radio ultra-wide band (IR-UWB) physical layers have the potential to satisfy these requirements. Because the features of IR-UWB physical layers differ from narrow-band physical layers, the design rules of IR-UWB networks are likely to be different than for narrow-band wireless networks. Indeed, to optimally use the resources available, it is crucial for the network layers to take into account and take advantage of the underlying physical layer. Therefore, we are interested in the design of IR-UWB networks in a low data-rate, self-organized, and multi-hop context. We concentrate on the medium access control (MAC) layer and the physical layer. In the case of low data-rate IR-UWB networks, the optimal design is to allow for parallel and concurrent transmissions at the MAC layer. Interference is managed with rate adaptation, no power control and an interference mitigation scheme at the physical layer. A protocol that implements the optimal design and allows for parallel transmissions outperforms protocols that use exclusion or power control. [pdf]
    
    
17. Jean-Yves Le Boudec and Ruben Merz   [Le BoudecM:08]   [published]
    Concurrent and Parallel Transmissions are Optimal for Low Data-Rate IR- UWB Networks    
    PIMRC 2008, Cannes, 15-18 Sep 08
    The Internet of Things, emerging pervasive and sensor networks are low data-rate wireless networks with, a priori, no specific topology and no fixed infrastructure. Their primary requirements are twofold: First, low power consumption and, due to environmental concerns, low emitted power. Second, robustness to poor propagation environments and multi-user interference. Impulse-radio ultra-wide band (IR-UWB) physical layers have the potential to satisfy these requirements. Because the features of IR-UWB physical layers differ from narrow-band physical layers, the design rules of IR-UWB networks are likely to be different than for narrow-band wireless networks. Indeed, to optimally use the resources available, it is crucial for the network layers to take into account and take advantage of the underlying physical layer. Therefore, we are interested in the design of IR-UWB networks in a low data-rate, self-organized, and multi-hop context. We concentrate on the medium access control (MAC) layer and the physical layer. In the case of low data-rate IR-UWB networks, the optimal design is to allow for parallel and concurrent transmissions at the MAC layer. Interference is managed with rate adaptation, no power control and an interference mitigation scheme at the physical layer. A protocol that implements the optimal design and allows for parallel transmissions outperforms protocols that use exclusion or power control. [pdf]
    
    
18. M. Flury, R. Merz and J.-Y. Le Boudec   [FluryML:08]   [published]
    An Energy Detection Receiver Robust to Multi-User Interference for IEEE 802.15.4a Networks    
    IEEE International Conference on Ultra-Wideband (ICUWB 2008), Hannover, 10-12 Sep 08
    Energy-detection receivers are appealing to IEEE 802.15.4a low data-rate networks because of their low complexity. With a reasonable energy consumption, these receivers can exploit the ranging capabilities and multipath resistance of impulse-radio UWB (IR-UWB). However, the performance of energy-detection receivers can be severely degraded by multi-user interference (MUI). One solution may be to coordinate access to the physical layer with an exclusion protocol. Unfortunately, this cannot prevent MUI due to uncontrolled activities in neighboring networks (e.g., several IEEE 802.15.4a piconets running in parallel). Hence, interference must be taken into account already in the design of the physical layer. In this paper, we present an IR-UWB receiver robust to MUI for IEEE 802.15.4a networks. Its architecture is based on energy detection. We also take into full account the different signaling structure between the preamble and the payload of IEEE 802.15.4a packets. In certain scenarios with MUI we found the packet error rate to be up to two orders of magnitude lower when compared to a traditional energy detection receiver that neglects MUI. Further, this significant performance improvement entails only a moderate increase in complexity. [pdf]
    
    
19. Hai Zhan, Jean-Yves Le Boudec, John Farserotu and Jaouhar Ayadi   [ZhanLFA:08]   [published]
    Statistical Analysis of Impulse Radio Ultra-wideband Multi-User Interference Based on Measurements    
    IEEE International Conference on Ultra-Wideband (ICUWB 2008), Hannover, 10-12 Sep 08
    Multiuser interference (MUI) statistical models for impulse radio (IR)-UWB systems can be an important in providing an accurate estimate of the channel state. As such, it can have a major impact on the overall system performance. In the literature, MUI in the time domain is often approximated with Middleton class A and Gaussian Mixture Models. We use measurements from an indoor IR-UWB testbed to assess the validity of these models. We find that (1) the marginal distribution of MUI does not fit any of Gaussian, GMM or Middleton Class A models and (2) MUI is correlated in the time domain. We also analyze MUI measurements in the frequency domain. We find that, subject to the constraints of hermitian symmetry, (3) the square root of the MUI amplitude fits well with the Middleton class A model, (4) the phase of MUI has uniform distribution on the interval [-pi, pi], and (5) the amplitude and phase of MUI are mutually independent. We expect these findings to form the basis for useful interference models.
    
    
20. Rizzo, Gianluca; Le Boudec, Jean-Yves   [RizzoL:08]   [published]
    Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers    
    INFOCOM 2008; Phoenix, USA, April 13-18
    Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For networks of FIFO aggregate schedulers, the main existing sufficient conditions for stability (the possibility to derive bounds to delay and backlog at each node) are of little practical utility, as they are either relative to specific topologies, or based on strong ATM- like assumptions on the network (the so- called ?RIN? result), or they imply an extremely low node utilization. We use a deterministic approach to this problem. We identify a non linear operator on a vector space of finite (but large) dimension, and we derive a first sufficient condition for stability, based on the super-additive closure of this operator. Second, we use different upper bounds of this operator to obtain practical results. We find new sufficient conditions for stability, valid in an heterogeneous environment and without any of the restrictions of existing results. We present a polynomial time algorithm to test our sufficient conditions for stability. We show that with leaky-bucket constrained flows, the inner bound to the stability region derived with our algorithm is always larger than the one determined by all existing results. We prove that all the main existing results can be derived as special cases of our results. We also present a method to compute delay bounds in practical cases.
    
    
21. Slavisa Sarafijanovic, Sabrina Perez and Jean-Yves Le Boudec   [SarafijanovicPL:08a]   [published]
    Improving Digest-Based Collaborative Spam Detection    
    MIT Spam Conference, Cambridge, USA, 27-28 March 08
    Spam is usually sent in bulk. A bulk mailing consists of many copies of the same original spam message, each sent to a different recipient. The copies are usually obfuscated, i.e. modified a bit in order to look different from each other. In collaborative spam filtering it is important to determine which emails belong to the same bulk. This allows, after observing an initial portion of a bulk, for the bulkiness scores to be assigned to the remaining emails from the same bulk. This also allows the individual evidence of spamminess to be joined, if such evidence is generated by collaborating filters or users for some of the emails from an initial portion of the bulk. Then, the observed bulkiness and the estimated spamminess of a bulk can be used to better filter the remaining emails from the same bulk. The work by Damiani et al. [2] ("open-digest paper") is well know and often cited for its positive findings about the properties of a digest-based collaborative spam detection technique. The technique produces similar digests out of similar emails, and uses them to find out which emails belong to the same bulk. Based on the experimental evaluation, the paper suggests that the technique provides bulk-spam detection that is robust to increased obfuscation efforts by spammers, and low miss-detection of good emails. We first repeat and extend some of the open-digest paper [2] experiments, using the simplest spammer model from that paper. We find that the conclusions of the open-digest paper are rather miss- leading. Then we propose and evaluate, under the same spammer model, a modified version of the original digest technique. The modified version greatly improves the resistance of spam detection against increased obfuscation effort by spammers, while keeping miss-detection of good emails at a similar level. Based on the observed results, we discuss possible additional modifications and algorithms that could be added on top of the modified digest technique to further improve its filtering performance. [pdf]
    
    
22. Buchegger, S.; Mundinger, J.; Le Boudec, J.-Y.   [BucheggerML:08]   [published]
    Reputation Systems for Self-Organized Networks    
    IEEE Technology and Society Magazine, Volume 27, Issue 1, Spring 2008
    
    
    
23. Hai Zhan, Jaouhar Ayadi, Jean-Yves Le Boudec and John Farserotu   [ZhanALF:07]   [published]
    Impulse Radio Ultra-Wideband Ranging under Mulit-User Environments Based on Hidden Markov Model    
    10th International Symposium on Wireless Personal Multimedia Communications (WPMC2007), Jaipur, 3-6 Dec 07
    We propose a novel impulse radio ultra-wideband (UWB) ranging algorithm under multi-user and weak non-line of sight (NLOS) environments. The multi-user interference (MUI) can not be modeled through Gaussian approximation from the literature. In this paper, we modeled the multi-user interference through a hidden Markov model (HMM) where each state is associated with a Gaussian output distribution. Based on HMM model, we pose the ranging problem as a Maximum Likelihood (ML) estimation problem for the channel delays and attenuations at receiver. Ranging is obtained by translating the obtained delay estimates into an estimate of the distance. The good performances of the proposed estimator are shown by means of simulations.
    
    
24. Slavisa Sarafijanovic and Jean-Yves Le Boudec   [SarafijanovicL:07b]   [published]
    Artificial Immune System For Collaborative Spam Filtering    
    NICSO 2007, The Second Workshop on Nature Inspired Cooperative Strategies for Optimization, Acireale, 8-10 Nov 07
    Artificial immune systems (AIS) use the concepts and algorithms inspired by the theory of how the human immune system works. This document presents the design and initial evaluation of a new artificial immune system for collaborative spam filtering. Collaborative spam filtering allows for the detection of not-previously-seen spam content, by exploiting its bulkiness. Our system uses two novel and possibly advantageous techniques for collaborative spam filtering. The first novelty is local processing of the signatures created from the emails prior to deciding whether and which of the generated signatures will be exchanged with other collaborating antispam systems. This processing exploits both the email-content profiles of the users and implicit or explicit feedback from the users, and it uses customized AIS algorithms. The idea is to enable only good quality and effective information to be exchanged among collaborating antispam systems. The second novelty is the representation of the email content, based on a sampling of text strings of a predefined length and at random positions within the emails, and a use of a custom similarity hashing of these strings. Compared to the existing signature generation methods, the proposed sampling and hashing are aimed at achieving a better resistance to spam obfuscation (especially text additions) - which means better detection of spam, and a better precision in learning spam patterns and distinguishing them well from normal text - which means lowering the false detection of good emails. Initial evaluation of the system shows that it achieves promising detection results under modest collaboration, and that it is rather resistant under the tested obfuscation. In order to confirm our understanding of why the system performed well under this initial evaluation, an additional factorial analysis should be done. Also, evaluation under more sophisticated spammer models is necessary for a more complete assessment of the system abilities. [pdf]
    
    
25. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:07]   [published]
    A Unified Framework for Max-Min and Min-Max Fairness with Applications    
    ACM/IEEE Transactions on Networking, vol. 15, no 5
    Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing it; in most, but not all cases, they are based on the notion of bottlenecks. In spite of this wide applicability, there are still examples, arising in the context of wireless or peer-to-peer networks, where the existing theories do not seem to apply directly. In this paper, we give a unifying treatment of max-min fairness, which encompasses all existing results in a simplifying framework, and extend its applicability to new examples. First, we observe that the existence of max-min fairness is actually a geometric property of the set of feasible allocations. There exist sets on which max-min fairness does not exist, and we describe a large class of sets on which a max-min fair allocation does exist. This class contains, but is not limited to the compact, convex sets of Rn. Second, we give a general purpose centralized algorithm, called Max-min Programming, for computing the max-min fair allocation in all cases where it exists (whether the set of feasible allocations is in our class or not). Its complexity is of the order of N linear programming steps in Rn, in the case where the feasible set is defined by linear constraints. We show that, if the set of feasible allocations has the free-disposal property, then Max-min Programming reduces to a simpler algorithm, called Water Filling, whose complexity is much lower. Free disposal corresponds to the cases where a bottleneck argument can be made, and Water Filling is the general form of all previously known centralized algorithms for such cases. All our results apply mutatis mutandis to minmax fairness. Our results apply to weighted, unweighted and util-max-min and min-max fairness. Distributed algorithms for the computation of max-min fair allocations are outside the scope of this paper.
    
    
26. Flury, Manuel; Merz, Ruben; Le Boudec, Jean-Yves; Zory, Julien   [FluryMLZ:07]   [published]
    Performance Evaluation of an IEEE 802.15.4a Physical Layer with Energy Detection and Multi-User Interference    
    IEEE International Conference on Ultra-Wideband (ICUWB 2007); Singapore, 24-26 September 2007
    We evaluate the performance of an IEEE 802.15.4a ultra-wide band (UWB) physical layer, with an energy-detection receiver, in the presence of multi-user interference (MUI). A complete packet based system is considered. We take into account packet detection and timing acquisition, the estimation of the power delay profile of the channel, and the recovery of the encoded payload. Energy detectors are known to have a low implementation complexity and to allow for avoiding the complex channel estimation needed by a Rake receiver. However, our results show that MUI severely degrades the performance of the energy detection receiver, even at low traffic rate. We demonstrate that using an IEEE 802.15.4a compliant energy detection receiver significantly diminishes one of the most appealing benefits of UWB, namely its robustness to MUI and thus the possibility to allow parallel transmissions. We further find that timing acquisition and data decoding both equally suffer from MUI.
    
    
27. Hai Zhan, Jaouhar Ayadi , John Farserotu and Jean-Yves Le Boudec   [ZhanAFB:07]   [published]
    High-Resolution Impulse Radio Ultra Wideband Ranging    
    2007 IEEE International Conference on Ultra Wide-Band (ICUWB), Singapore, 24-26 Sep 07
    We propose a high resolution ranging algorithm for impulse radio Ultra-wideband (UWB) communication systems in gaussian noise. We pose the ranging problem as a Maximum Likelihood (ML) estimation problem for the channel delays and attenuations and phase offset at receiver. Then we translate the obtained delay estimates into an estimate of the distance. The ML problem is very non linear and hard to solve. Some previous works focused on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of Iterative Quadratic Maximum Likelihood (IQML) and transform the ML problem into another optimization problem that gets rid of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach (“pseudo-quadratic maximum likelihood”). We show that our algorithm performs significantly better than previously published heuristics. We tested the approach on a real non-line of sight system and obtained good accuracy. [pdf]
    
    
28. Zhan, Hai; Farserotu, John; Le Boudec, Jean-Yves   [ZhanAFL:07b]   [published]
    A Novel Maximum Likelihood Estimation Of Superimposed Exponential Signals In Noise And Ultra-Wideband Application    
    18th annual international symposium on personal, indoor and mobile radio communication; Athens, 3-7 septembre 2007
    We pose the estimation of the parameters of multiple superimposed exponential signals in additive Gaussian noise problem as a Maximum Likelihood (ML) estimation problem. The ML problem is very non linear and hard to solve. Some previous works focused on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of Iterative Quadratic Maximum Likelihood (IQML) and transform the ML problem into another optimization problem that gets rid of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach (?pseudo-quadratic maximum likelihood?). We also use this algorithm for Ultra-Wideband channel estimation and estimate ranging in non-line of sight environment. [pdf]
    
    
29. Klemm, Fabius; Girdzijauskas, Sarunas; Le Boudec, Jean-Yves; Aberer, Karl   [KlemmGLA:07]   [published]
    On Routing in Distributed Hash Tables    
    The Seventh IEEE International Conference on Peer-to-Peer Computing; Galway, Ireland, September 2-5, 2007
    There have been many proposals for constructing routing tables for Distributed Hash Tables (DHT). They can be classified into two groups: A) those that assume that the peers are uniformly randomly distributed in the identifier space, and B) those that allow order-preserving hash functions that lead to a skewed peer distribution in the identifier space. Good solutions for group A have been known for many years. However, DHTs in group A are limited to use randomized hashing and therefore, queries over whole identifier ranges thus do not scale. Group B can handle such queries easily. However, it is more difficult to connect the peers such that the resulting topology provides efficient routing, small routing tables, and balanced routing load. We present an elegant new solution to construct an efficient DHT for group B. Our main idea is to decouple the identifier space from the routing topology. In consequence, our DHT allows arbitrarily skewed peer distributions in the identifier space and does not require the overhead of sampling. Furthermore, the table construction is cheap and does not require active replacement of lost routing entries. To evaluate the performance of routing cost and table construction under high churn, we built an efficient simulator. Using the right data structures, we can easily process the state of over one million peers in RAM.
    
    
30. Sarafijanovic, Slavisa; Hernandez, Luis; Naefen, Raphael; Le Boudec, Jean-Yves   [SarafijanovicHNL:07]   [published]
    AntispamLab - A Tool for Realistic Evaluation of Email Spam Filters    
    Fourth Conference on Email and Antispam; Mountain View, California, USA, August 2-3, 2007
    The existing tools for testing spam filters evaluate a filter instance by simply feeding it with a stream of emails, possibly also providing a feedback to the filter about the correctness of the detection. In such a scenario the evaluated filter is disconnected from the network of email servers, filters, and users, which makes the approach inappropriate for testing many of the filters that exploit some of the information about spam bulkiness, users' actions and social relations among the users. Corresponding evaluation results might be wrong, because the information that is normally used by the filter is missing, incomplete or inappropriate. In this paper we present a tool for testing spam filters in a very realistic scenario. Our tool consists of a set of Python scripts for unix/linux environment. The tool takes as inputs the filter to be tested and an affordable set of interconnected machines (e.g., PlanetLab machines, or locally created virtual machines). When started from a central place, the tool uses the provided machines to build a network of real email servers, installs instances of the filter, deploys and runs simulated email users and spammers, and computes the detection results statistic. Email servers are implemented using Postfix, a standard linux email server. Only per-email-server filters are currently supported, whereas per-email-client filters testing would require additional tool development. The size of the created emailing network is constrained only by the number of available PlanetLab or virtual machines. The run time is much shorter then the simulated system time, due to a time scaling mechanism. Testing a new filter is as simple as installing one copy of it in a real emailing network, which unifies the jobs of a new filter development, testing and prototyping. As a usage example, we test the SpamAssassin filter.
    
    
31. Flury, Manuel; Merz, Ruben; Le Boudec, Jean-Yves   [FluryML:07]   [published]
    Managing Impulsive Interference in Impulse Radio UWB Networks    
    ST Journal of Research
    Wireless sensor networks are ideally built on low-cost, low-complexity nodes that have a low power consumption to guarantee a long network lifetime. These are all properties that can potentially be achieved with impulse radio ultra-wide band (IR-UWB). In addition, IR-UWB has a fine timing resolution resulting in accurate ranging and localization possible. For all these reasons, IR-UWB is an extremely interesting physical layer technology for wireless sensor networks. In this article, we consider the management of impulsive interference in IR-UWB networks. Impulsive interference is due to uncoordinated concurrent transmissions. It occurs, for instance, when several independent piconets operate in close vicinity and is also present in some MAC layer proposals that allow concurrent transmissions. If not properly addressed, impulsive interference can severely affect the throughput and energy consumption of an IR-UWB network; as such, it already needs to be taken into account in the design phase. First, we show that impulsive interference is a serious concern for IR-UWB networks. Second, we present techniques at the physical layer and at the link layer to cope with and combat such interference efficiently. Finally, we present DCC-MAC as an example of an interference-aware design. [pdf]
    
    
32. Merz, Ruben; Le Boudec, Jean-Yves; Widmer, Jörg   [MerzLW:07]   [published]
    An Architecture for Wireless Simulation in NS-2 Applied to Impulse-Radio Ultra-Wide Band Networks    
    10th Communications and Networking Simulation Symposium; Norfolk, VA, March 25-29, 2007
    We present an architecture for implementing a wireless physical layer in a packet-based network simulator. We integrate this architecture in the popular ns-2 network simulator and use it to implement an impulse-radio ultra-wide band (IR-UWB) physical layer. Contrary to the current wireless physical layer implementation of ns-2, in our case a packet is fully received by our physical layer before being delivered to the MAC layer. A packet detection and timing acquisition model has been implemented. Furthermore, for each packet, a packet error rate (PER) can be computed as a function of the received power, interference from concurrent transmissions, and thermal noise. This architecture is quite generic and allows for the simulation of any physical layer where an accurate model of interference is of high importance, e.g., IR-UWB or CDMA. Our implementation for IR-UWB takes into account transmissions with different time-hopping sequences (THS). The underlying modulation is binary phase shift keying (BPSK), followed by a variable-rate channel code. Our implementation is the first available that allows for the simulation of IR-UWB networks. It is modular and can thus be easily modified and extended. [pdf]
    
    
33. Merz, Ruben; Le Boudec, Jean-Yves; Vijayakumaran, Saravanan   [MerzLV:06]   [published]
    Effect on Network Performance of Common versus Private Acquisition Sequences for Impulse Radio UWB Networks    
    IEEE International Conference on Ultra-Wideband (ICUWB 2006); Waltham, MA, September 24-27
    Packet detection and timing acquisition for IR-UWB networks such as 802.15.4a relies on the presence of an acquisition sequence (or preamble) at the beginning of each packet. A simple network design choice is to use a common acquisition sequence for the whole network. A second design choice is to use an acquisition sequence private to destinations. It potentially yields a larger network throughput, but requires additional complexity for sources to learn the acquisition sequence of their destination. In this paper, we evaluate the effect of a common or private acquisition sequence on the network throughput. Our analysis is based on analytical modeling and simulations. We show that a private acquisition sequence yields a substantial increase in throughput. The throughput difference grows with the number of concurrent transmitters and interferers. We also show the presence of a compounding effect similar to the exposed terminal issue in 802.11 networks.
    
    
34. Flury, Manuel; Le Boudec, Jean-Yves   [FluryL:06]   [published]
    Interference Mitigation by Statistical Interference Modeling in an Impulse Radio UWB Receiver    
    IEEE International Conference on Ultra-Wideband (ICUWB 2006); Waltham, MA, September 24-27
    Some impulse radio UWB (IR-UWB) networks may allow concurrent transmissions without power control (for example MAC protocols that do not use power control, or co-existing, non-coordinated piconets). In such cases, it has been proposed to mitigate multi-user interference (MUI) at the physical layer, but existing proposals for interference mitigation do not account for the multipath nature of UWB channels. We address this problem and propose a receiver that employs a combination of statistical interference modeling and thresholding to mitigate MUI. We find that in a multipath environment the proposed receiver significantly outperforms existing receiver designs that either completely neglect the effect of MUI or only use a simple threshold to reject samples from interfering users. Further, in contrast to successive interference cancellation schemes, our receiver does not require active decoding of each interferer. Thus there is no need to synchronize the receiver with all the interfering users, which would be impractical in an IR-UWB system that is likely to be run in ad hoc mode. To model MUI we consider a hidden Markov model (HMM) and a Gaussian mixture model (GMM). We find that the HMM models interference better than the GMM. However, the resulting performance difference is not huge and comes at the cost of increased receiver complexity. [pdf]
    
    
35. Merz, Ruben; El Fawal, Alaeddine; Le Boudec, Jean-Yves; Radunovic, Bozidar; Widmer, Joerg   [MerzFLRW:06]   [published]
    The Optimal MAC Layer for Low-Power UWB is Non-Coordinated    
    IEEE International Symposium on Circuits and Systems (ISCAS 2006); Island of Kos, Greece, May 21-24, 2006
    We consider the design of the MAC layer for low power, low data-rate, impulse-radio ultra-wide band (IR-UWB) networks. In such networks, the primary concern is energy consumption rather than rate efficiency. We explore several dimensions such as power control, rate adaptation, mutual exclusion, slotted versus non-slotted operation, power saving modes and interference mitigation. We analyze the effect of these design choices on the energy consumption and rate efficiency. We use a method of energy quanta for computing the energy consumption. We find that for both cases, the optimal operation is non-coordinated and with no power control. Sources should send at their maximum power and not pay attention to neighboring nodes. However, sources should constantly adapt their transmission rate to the level of interference. [pdf]
    
    
36. Fragouli, Christina; Widmer, Joerg; Le Boudec, Jean-Yves   [FragouliWL:06]   [published]
    A Network Coding Approach to Energy Efficient Broadcasting: from Theory to Practice    
    Infocom '06; Barcelona, April 2006
    We show that network coding allows to realize energy savings in a wireless ad-hoc network, when each node of the network is a source that wants to transmit information to all other nodes. Energy efficiency directly affects battery life and thus is a critical design parameter for wireless networks. We propose an implementable method for performing network coding in such a setting. We analyze theoretical cases in detail, and use the insights gained to propose a practical, fully distributed method for realistic wireless ad-hoc scenarios. We address practical issues such as setting the forwarding factor, managing generations, and impact of transmission range. We use theoretical analysis and packet level simulation.
    
    
37. El Fawal, Alaeddine; Le Boudec, Jean-Yves   [ElfawalL:06]   [published]
    A Robust Signal Detection Method for Ultra Wide Band (UWB) Networks with Uncontrolled Interference    
    IEEE Transactions on Microwave Theory and Techniques (MTT), vol. 54, no 4, part 2, p. 1769-1781
    We propose a novel detection method for non-coherent synchronization (signal acquisition) in multi-user UWB impulse radio (IR) networks. It is designed to solve the IUI (Inter-User Interference) that occurs in some ad-hoc networks where concurrent transmissions are allowed with heterogeneous power levels. In such scenarios, the conventional detection method, which is based on correlating the received IR signal with a Template Pulse Train (TPT), does not always perform well. The complexity of our proposal is similar to that of the conventional method. We evaluate its performance with the Line Of Sight (LOS) and the Non LOS (NLOS) office indoor channel models proposed by the IEEE P802.15.4a study group and find that the improvement is significant. We also investigate the particular case where the concurrent transmissions have the same time-hopping code, and we show that it does not result in collision, such scenarios appear in ad-hoc networks that employ common code for control or broadcast purposes. [pdf]
    
    
38. Merz, Ruben; Le Boudec, Jean-Yves; Vijayakumaran, Saravanan   [MerzLV:06]   [published]
    Effect on Network Performance of Common versus Private Acquisition Sequences for Impulse Radio UWB Networks    
    Technical Report EPFL-LCA 2006-005, March 2006
    Packet detection and timing acquisition for IR-UWB networks such as 802.15.4a relies on the presence of an acquisition sequence (or preamble) at the beginning of each packet. A simple network design choice is to use a common acquisition sequence for the whole network. A second design choice is to use an acquisition sequence private to destinations. It potentially yields a larger network throughput, but requires additional complexity for sources to learn the acquisition sequence of their destination. In this paper, we evaluate the effect of a common or private acquisition sequence on the network throughput. Our analysis is based on analytical modeling and simulations. We show that a private acquisition sequence yields a substantial increase in throughput. The throughput difference grows with the number of concurrent transmitters and interferers. We also show the presence of a compounding effect similar to the exposed terminal issue in 802.11 networks. [pdf]
    
    
39. Flury, Manuel; Le Boudec, Jean-Yves   [FluryL:06]   [published]
    Interference Mitigation by Statistical Interference Modeling in an Impulse Radio UWB Receiver    
    Technical Report EPFL-LCA 2006-004
    Some impulse radio UWB (IR-UWB) networks may allow concurrent transmissions without power control (for example MAC protocols that do not use power control, or co-exisiting, non-coordinated piconets). In such cases, it has been proposed to mitigate multi-user interference (MUI) at the physical layer, but existing proposals for interference mitigation do not account for the multipath nature of UWB channels. We address this problem and propose a receiver that employs a combination of statistical interference modeling and thresholding to mitigate MUI. We find that in a multipath environment the proposed receiver significantly outperforms existing receiver designs that either completely neglect the effect of MUI or only use a simple threshold to reject samples from interfering users. Further, in contrast to successive interference cancellation schemes, our receiver does not require active decoding of each interferer. Thus there is no need to synchronize the receiver with all the interfering users, which would be impractical in an IR-UWB system that is likely to be run in ad hoc mode. To model MUI we consider a hidden Markov model (HMM) and a Gaussian mixture model (GMM). We find that the HMM models interference better than the GMM. However, the resulting performance difference is not huge and comes at the cost of increased receiver complexity. [pdf]
    
    
40. El Fawal, Alaeddine; Le Boudec, Jean-Yves; Merz, Ruben; Radunovic, Bozidar; Widmer, Jörg; Maggio, Gian Mario   [ElFawalLMRWM:05]   [published]
    Tradeoff Analysis of PHY-aware MAC in Low-Rate, Low-Power UWB networks    
    IEEE Communications Magazine, vol. 43, no 12, p. 147
    We are interested in the design of physical-layer aware medium access control (PHY-aware MAC) for self-organized, low power, low data-rate impulse-radio ultra-wideband (IR-UWB) networks. In such networks, energy consumption is much more of a concern than achieved data rates. So far, a number of different solutions have been proposed in the context of data rate efficiency for IR-UWB. However, the choices made for rate efficient designs are not necessarily optimal when considering energy efficiency. Hence, there is a need to understand the design tradeoffs in very low power networks, which is the aim of this paper. To this end, we first identify \emph{what} a PHY-aware MAC design has to achieve~: (1) interference management, (2) access to a destination and (3) sleep cycle management. Second, we analyze \emph{how} these functions can be implemented, and provide a list of the many possible building blocks that have been proposed in the literature. Third, we use this classification to analyze fundamental design choices. We propose a method for evaluating energy consumption already in the design phase of IR-UWB systems. Last, we apply this methodology and derive a set of guidelines; they can be used by system architects to orientate fundamental choices early in the design process. [pdf]
    
    
41. Merz, Ruben; Le Boudec, Jean-Yves   [MerzL:05c]   [published]
    Effect of Interfering Users on the Modulation Order and Code Rate for UWB Impulse-Radio Bit-Interleaved Coded M-ary PPM    
    IEEE UWBNETS; Boston, October 7th
    We consider the impact of multi-user interference on a bit-interleaved coded-modulation system with M-ary PPM (BIC M-ary PPM) in an impulse-radio ultra-wideband physical layer. In a realistic scenario such as an ad hoc network, the interference is inherently variable. This justifies the need for a physical layer that can optimally adapt its transmission parameters to the interference level. We use puncturing on the channel code so that we can not only change the modulation order $M$ but also the channel code rate. We study by simulation how the optimal combination of modulation order $M$ and channel code rate behaves with various degrees of interference. The results show that BIC M-ary PPM can be successfully adapted to various levels of interference conditions. It also shows the benefit of both rate and modulation adaptation, especially in the presence of multi-user interference.
    
    
42. Mundinger, Jochen; Le Boudec, Jean-Yves   [MundingerL:05]   [published]
    Analysis of a Robust Reputation System for Self-Organized Networks    
    European Transactions on Communication, 2005, vol. 16, no 5, p. 375-384
    Self-organized networks require some mechanism to ensure cooperation and fairness. A promising approach is the use of decentralized reputation systems. However, their vulnerability to liars has not yet been analyzed in detail. In this paper, we provide a rst step to the robustness analysis of a reputation system based on a deviation test. Users accept second hand information only if this does not dier too much from their reputation values. We simplify the original system in order to obtain a one-dimensional formulation and show that it exhibits a phase transition. In the subcritical regime, the reputation system is robust. In the supercritical regime, lying has an impact. We obtain the critical values via a mean- eld approach and verify the results by explicit computation. Thus, we provide conditions for the deviation test to make the reputation system robust as well as quantitative results on what goes wrong in the supercritical regime. [pdf]
    
    
43. Merz, Ruben; Le Boudec, Jean-Yves   [MerzL:05]   [published]
    Conditional Bit Error Rate for an Impulse Radio UWB Channel with Interfering Users    
    IEEE International Conference on Ultra-Wideband (ICU 2005); Zürich, Switzerland
    We consider a multi-user impulse radio UWB physical layer in a multipath environment. We propose a fast and efficient method to compute the conditional bit error rate (BER), given some realizations of the channels from source/interferer to destination, and of delay differences. Our motivation is packet level simulation of large scale or dense impulse radio UWB networks. The conditional BER is used in a packet level simulator with block fading channel assumption to sample packet transmission error events. However, due to the timescale difference between physical layer events and network events, a pulse-level simulation of the BER in a realistic multipath channel environment is infeasible. Our solution is based on a novel combination of large deviation and importance sampling.
    
    
44. El Fawal, Alaeddine; Le Boudec, Jean-Yves   [ElFawalL:05]   [published]
    A Power Independent Detection Method for UltraWide Band (UWB) Impulse Radio Networks    
    IEEE International Conference on Ultra-Wideband (ICU 2005); Zürich, Switzerland, 7 September 2005
    We propose a novel detection method for non-coherent synchronization (signal acquisition) in multi-access UWB impulse radio (IR) networks. It is designed to solve the IUI (Inter-User Interference) that occurs in some ad-hoc networks where concurrent transmissions are allowed with heterogeneous power levels. In such scenarios, the conventional detection method, which is based on correlating the received IR signal with a Template Pulse Train (TPT), does not always perform well. Our proposal has similar complexity as the conventional method. We evaluate its performance with the Line Of Sight (LOS) office indoor channel model proposed by the IEEE P802.15.4a study group and find that the improvement is significant. [pdf]
    
    
45. Sarafijanovic, Slavisa; Le Boudec, Jean-Yves   [SarafijanovicL:05a]   [published]
    An Artificial Immune System Approach with Secondary Response for Misbehavior Detection in Mobile Ad-Hoc Networks    
    IEEE Transactions on Neural Networks, Special Issue on Adaptive Learning Systems in Communication Networks, vol. 16, no 5, p. 1076 - 1087
    In mobile ad hoc networks, nodes act both as terminals and information relays, and they participate in a common routing protocol, such as dynamic source routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. In this paper, we investigate the use of an artificial immune system (AIS) to detect node misbehavior in a mobile ad hoc network using DSR. The system is inspired by the natural immune system (IS) of vertebrates. Our goal is to build a system that, like its natural counterpart, automatically learns, and detects new misbehavior. We describe our solution for the classification task of the AIS; it employs negative selection and clonal selection, the algorithms for learning and adaptation used by the natural IS. We define how we map the natural IS concepts such as self, antigen, and antibody to a mobile ad hoc network and give the resulting algorithm for classifying nodes as misbehaving. We implemented the system in the network simulator Glomosim; we present detection results and discuss how the system parameters affect the performance of primary and secondary response. Further steps will extend the design by using an analogy to the innate system, danger signal, and memory cells.
    
    
46. Merz, Ruben; Widmer, Jörg; Le Boudec, Jean-Yves; Radunovic, Bozidar   [MerzWLR:05]   [published]
    A Joint PHY/MAC Architecture for Low-Radiated Power TH-UWB Wireless Ad-Hoc Networks    
    Wireless Communications and Mobile Computing Journal, Special Issue on Ultrawideband (UWB) Communications, 2005, vol. 5, no 5, p. 567-580
    Due to environmental concerns and strict constraints on interference imposed on other networks, the radiated power of emerging pervasive wireless networks needs to be strictly limited, yet without sacrificing acceptable data rates. Pulsed Time-Hopping Ultra-Wideband (TH-UWB) is a radio technology that has the potential to satisfy this requirement. Although TH-UWB is a multi-user radio technology, non-zero cross-correlation between time-hopping sequences, time-asynchronicity between sources and a multipath channel environment make it sensitive to strong interferers and near-far scenarios. While most protocols manage interference and multiple-access through power control or mutual exclusion, we base our design on rate control, a relatively unexplored dimension for multiple-access and interference management. We further take advantage of the nature of pulsed TH-UWB to propose an interference mitigation scheme that alleviates the need for an exclusion scheme. A source is always allowed to send and continuously adapts its channel code (hence its rate) to the interference experienced at the destination. In contrast to power control or exclusion, our MAC layer is local to sender and receiver and does not need coordination among neighbors not involved in the transmission. We show by simulation that we achieve a significant increase in network throughput compared to alternative designs. [pdf]
    
    
47. Le Boudec, Jean-Yves   [LeBoudec:05]   [published]
    On the Stationary Distribution of Speed and Location of Random Waypoint    
    IEEE transactions on mobile computing, 2005, vol. 4, no 4, p. 404--405
    In ``Stationary Distributions for the Random Waypoint Mobility Model [pdf]
    
    
48. Sarafijanovic, Slavisa; Le Boudec, Jean-Yves   [SarafijanovicL:05b]   [published]
    An Artificial Immune System for Misbehavior Detection in Mobile Ad-Hoc Networks with Virtual Thymus, Clustering, Danger Signal and Memory Detectors    
    International Journal of Unconventional Computing, vol. 1, p. 221-254
    Nodes that build a mobile ad-hoc network participate in a common routing protocol in order to provide multi-hop radio communication. Routing defines how control information is exchanged between nodes in order to find the paths between communication pairs, and how data packets are relayed. Such networks are vulnerable to routing misbehavior, due to faulty, selfish or malicious nodes. Misbehavior disrupts communication, or even makes it impossible in some cases. Misbehavior detection systems aim at removing this vulnerability. For this purpose, we use an Artificial Immune System (AIS) approach, i.e, an approach inspired by the human immune system (HIS). Our goal is to make an AIS that, analogously to its natural counterpart [16], automatically learns and detects new misbehavior, but becomes tolerant to previously unseen normal behavior. We achieve this goal by adding some new AIS concepts to those that already exist: (1) the virtual thymus, which provides a dynamic description of normal behavior in the system; (2) ?clustering? is a decision making method that reduces the false-positive detection probability and minimizes the time until detection; (3) we apply the ?danger signal? approach, that is recently proposed in AIS literature [5,6] as a way to obtain feedback from the protected system and use it for correct learning and finaldecisions making; (4) we use ?memory detectors?, a standard AIS solution to achieve fast secondary response.
    
    
49. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:05b]   [published]
    Power Control is Not Required for Wireless Networks in the Linear Regime    
    WoWMoM; Taormina, Italy
    We consider the design of optimal strategies for joint power adaptation, rate adaptation and scheduling in a multi-hop wireless network. Most existing strategies control either power and scheduling, or rates and scheduling, but not all three together as we do. We assume the underlying physical layer is in the linear regime (the rate of a link can be approximated by a linear function of the signal-to-interference-and-noise ratio), like in time hopping UWB (TH-UWB) and low gain CDMA systems, and that it allows fine-grained rate adaptation, like in 802.11a/g, HDR/CDMA, TH-UWB. The goal is to find properties of the power control in an optimal joint design. Our main finding is that optimal power control is simple 0-PMAX power control, i.e. when a node is sending it uses the maximum transmitting power allowed. We consider both high rate networks where the goal is to maximize rates under power constraints and low power networks where the goal is to minimize average consumed power while meeting minimum rate constraints. We prove analytically that in both scenarios the optimal can always be attained with 0-PMAX power allocation. Moreover, we prove that, when maximizing rates, and if power constraints are on peak and not average, 0-PMAX is the only optimal power control strategy, and any other is strictly suboptimal. [pdf]
    
    
50. Mundinger, Jochen; Le Boudec, Jean-Yves   [MundingerL:05b]   [published]
    Analysis of a Reputation System for Mobile Ad-Hoc Networks with Liars    
    The 3rd International Symposium on Modeling and Optimization on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'05); Trento, Italy, 2005
    Using decentralized reputation systems is a promising approach to ensuring cooperation and fairness in Mobile Ad-Hoc Networks. However, they are vulnerable to liars and robustness has not been analyzed in detail. With our work, we provide a first step to the analysis of a reputation system based on a deviation test. Nodes accept second hand information only if this does not differ too much from their reputation values. Whereas our earlier paper [13] dealt with a simplified one-dimensional model, we now consider the original two-dimensional system. We show that the sys-tem exhibits a phase transition: In the subcritical regime, it is robust and lying has no effect. In the supercritical regime, lying does have an impact. We compute the critical values via a mean-field approach and use simulations to verify our results. Thus, we obtain conditions for the deviation test to make the reputation system robust and provide guidelines for a good choice of parameters. [pdf]
    
    
51. Le Boudec, Jean-Yves; Radunovic, Bozidar   [RadunovicL:05]   [published]
    Rate Adaptation, Power Adaptation and Mutual Exclusion in Variable Rate Wireless Networks    
    RAWNET; Riva Del Garda, Italy, 2005
    We consider the joint design of rate adaptation, power adaptation and mutual exclusion for the MAC layer of a multi-hop, ad-hoc wireless network. We assume the physical layer supports a variable bit-rate. Most of the existing MACs analyze impacts of only one of these elements, and the jointly optimal strategy is not known. We assume that successive decoding is not implemented, i.e. one receiver decodes only one source at a time. Using a theoretical model that neglects protocol overhead, we numerically find the optimal combination of the three basic elements. Our results suggest that the optimal strategy has the following properties: (1) When a node transmits it should always transmit with the maximum power and no power adaptation is necessary. (2) There is an optimal exclusion region around a destination. While a destination is receiving, nodes inside the exclusion region should stay silent. Nodes outside of the exclusion region should transmit in parallel. The size of the exclusion region does not depend on link sizes, nor on position of nodes, but only on maximum transmitted power. (3) A sender should adapt the transmission rate to the amount of interference generated by nodes outside of the exclusion region of a receiver. We present the results in detail for the 802.11a/g physical layer (but our conclusions hold for other rate functions as well). We show by simulations that the optimal protocol outperforms the existing 802.11 rate adaptation protocols; the exclusion region of 802.11a/g is too large and the spatial reuse is too low, in other words, the efficiency of 802.11 could be improved by allowing more interference. [pdf]
    
    
52. Le Boudec, Jean-Yves; Vojnovic, Milan   [LeBoudecV:05]   [published]
    Perfect Simulation and Stationarity of a Class of Mobility Models    
    IEEE INFOCOM ; Miami, 2005
    We define ``random trip", a generic mobility model for independent mobiles that contains as special cases: the random waypoint on convex or non convex domains, random walk with reflection or wrapping, city section, space graph and other models. We use Palm calculus to study the model and give a necessary and sufficient condition for a stationary regime to exist. When this condition is satisfied, we compute the stationary regime and give an algorithm to start a simulation in steady state (perfect simulation). The algorithm does not require the knowledge of geometric constants. For the special case of random waypoint, we provide for the first time a proof and a sufficient and necessary condition of the existence of a stationary regime. Further, we extend its applicability to a broad class of non convex and multi-site examples, and provide a ready-to-use algorithm for perfect simulation. For the special case of random walks with reflection or wrapping, we show that, in the stationary regime, the mobile location is uniformly distributed and is independent of the speed vector, and that there is no speed decay. Our framework provides a rich set of well understood models that can be used to simulate mobile networks with independent node movements. [pdf]
    
    
53. Blazevic, Ljubica; Le Boudec, Jean-Yves; Giordano, Silvia   [BlazevicLG:05]   [published]
    A Location Based Routing Method for Mobile Ad Hoc Networks    
    IEEE Transactions on Mobile Computing, 2005, vol. 4, no 2, p. 97--110
    Using location information to help routing is often proposed as a means to achieve scalability in large mobile ad-hoc networks. However, location based routing is difficult when there are holes in the network topology and nodes are mobile or frequently disconnect to save battery. Terminode routing, presented here, addresses these issues. It uses a combination of location based routing (Terminode Remote Routing, TRR), used when the destination is far, and link state routing (Terminode Local Routing, TLR), used when the destination is close. TRR uses anchored paths, a list of geographic points (not nodes) used as loose source routing information. Anchored paths are discovered and managed by sources, using one of two low overhead protocols: Friend Assisted Path Discovery and Geographical Map-based Path Discovery. Our simulation results show that terminode routing performs well in networks of various sizes. In smaller networks, the performance is comparable to MANET routing protocols. In larger networks that are not uniformly populated with nodes, terminode routing outperforms existing location-based or MANET routing protocols. [pdf]
    
    
54. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:04a]   [published]
    Self-Policing Mobile Ad-hoc Networks    
    P2PEcon 2004, 2004, p. 6
    Misbehavior in mobile ad-hoc networks occurs for several reasons. Selfish nodes misbehave to save power or to improve their access to service relative to others. Malicious intentions result in misbehavior as exemplified by denial of service attacks. Faulty nodes simply misbehave accidentally. Regardless of the motivation for misbehavior its impact on the mobile ad-hoc network proves to be detrimental, decreasing the performance and the fairness of the network, and in the extreme case, resulting in a non-functional network. Countermeasures to prevent or to combat misbehavior have been proposed, such as payment schemes for network services, secure routing protocols, intrusion detection and reputation systems to detect and isolate misbehaved nodes. We discuss the trade-offs and issues of self-policing mobile ad-hoc networks and give an overview of the state of the art, discussing and contrasting several solution proposals.
    
    
55. Le Boudec, Jean-Yves; Merz, Ruben; Radunovic, Bozidar; Widmer, Jörg   [LeBoudecMRW:04]   [published]
    DCC-MAC: A Decentralized MAC Protocol for 802.15.4a-like UWB Mobile Ad-Hoc Networks Based on Dynamic Channel Coding    
    Broadnets; San Jose, 2004
    We present a joint PHY/MAC architecture (DCC-MAC) for 802.15.4a-like networks based on PPM-UWB. Unlike traditional approaches it fully utilizes the specific nature of UWB to achieve high rates at low protocol complexity. It is the first MAC protocol that adapts the channel code (and thus the bit rate) to interference from concurrent transmissions instead of enforcing exclusion. In order to avoid a complex mutual exclusion protocol at the MAC layer, we propose an interference mitigation scheme. The scheme is based on a modification of the physical layer that cancels much of the interfering energy, in particular from nearby interferers. We further use dynamic channel coding to combat the remaining interference. Sources constantly adjust their channel codes to the level of interference and send incremental redundancy as required. Contention between sources sending to the same destination is solved by a ``private MAC`` protocol that involves only the nodes that want to talk to the same destination. The private MAC does not use any common channel; this avoids the issues of hidden and exposed terminals altogether. We show by simulation that our MAC protocol fully satisfies the application requirements of 802.15.4a in terms of link lengths, rates and mobility. We further show that it achieves a significant increase in network throughput, compared to traditional MAC protocols like 802.15.4, that are separated from the physical layer.
    
    
56. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:04c]   [published]
    Rate Performance Objectives of Multihop Wireless Networks    
    IEEE Transactions on Mobile Computing, 2004, vol. 3, no 4, p. 334-349
    We consider the question of what performance metric to maximize when designing ad hoc wireless network protocols such as routing or MAC. We focus on maximizing rates under battery-lifetime and power constraints. Commonly used metrics are total capacity (in the case of cellular networks) and transport capacity (in the case of ad hoc networks). However, it is known in traditional wired networking that maximizing total capacity conflicts with fairness, and this is why fairness-oriented rate allocations, such as max-min fairness, are often used. We review this issue for wireless ad hoc networks. Indeed, the mathematical model for wireless networks has a specificity that makes some of the findings different. It has been reported in the literature on ultra wide band that gross unfairness occurs when maximizing total capacity or transport capacity, and we confirm by a theoretical analysis that this is a fundamental shortcoming of these metrics in wireless ad hoc networks, as it is for wired networks. The story is different for max-min fairness. Although it is perfectly viable for a wired network, it is much less so in our setting. We show that, in the limit of long battery lifetimes, the max-min allocation of rates always leads to strictly equal rates, regardless of the MAC layer, network topology, channel variations, or choice of routes and power constraints. This is due to the [pdf]
    
    
57. Sarafijanovic, Slavisa; Le Boudec, Jean-Yves   [SarafijanovicL:04b]   [published]
    An Artificial Immune System for Misbehavior Detection in Mobile Ad-Hoc Networks with Virtual Thymus, Clustering, Danger Signal and Memory Detectors    
    ICARIS-2004, 3rd International Conference on Artificial Immune Systems; Catania, Italy, 2004, p. 342-356
    In mobile ad-hoc networks, nodes act both as terminals and information relays, and participate in a common routing protocol, such as Dynamic Source Routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. For this purpose, we use an Artificial Immune System (AIS), a system inspired by the human immune system (HIS). Our goal is to build a system that, like its natural counterpart, automatically learns and detects new misbehavior. In this paper we build on our previous work and investigate the use of four concepts: (1)
    
    
58. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:04b]   [published]
    Optimal Power Control, Scheduling and Routing in UWB Networks    
    IEEE Journal on Selected Areas in Communications, 2004, vol. 22, no 7, p. 1252
    Ultra-Wide Band (UWB) is an emerging wireless physical layer technology that uses a very large bandwidth. We are interested in finding the design objectives of the medium access (MAC, namely, power control and scheduling) and routing protocols of a multi-hop, best-effort, UWB network. Our objective is to maximize flow rates (more precisely, log-utility of flow rates) given node power constraints. The specificity of UWB is expressed by the linear dependence between rate and signal-to-noise ratio at the receiver. It is known that, in wireless networks, different routing strategies can imply differences in MAC protocol design. Hence we search for the jointly optimal routing, scheduling and power control. We find that the optimal solution is characterized by the following. (1) When data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. Additionally, the source adapts its transmission rate according to the level of interference at the destination due to sources outside of the exclusion region. (2) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. (3) Each node in a given time slot either sends data at the maximum power, or does not send at all. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination, and we show that (4) relaying along a minimum energy and loss route is always better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally (5), the design of the optimal MAC protocol is independent of the choice of the routing protocol. For narrow-band networks, (2), (4) and (5) do not hold, which shows that the design of an UWB network should be addressed in a different way than for narrow-band. Our technical approach is based on expressing the design requirements as a mathematical optimization problem. We solve it exactly for simple networks on a line and approximately on random topologies in a plane with up to 50 nodes with various power constraints, traffic matrices, and mobility parameters. [pdf]
    
    
59. Mundiger, Jochen; Le Boudec, Jean-Yves   [MundingerL:04]   [published]
    Analysis of a Robust Reputation System for Self-Organized Networks    
    Univ. Cambridge, Statistical Laboratory Research Report 2004-10
    Self-organized networks require some mechanism to ensure cooperation and fairness in the face of individual utility maximizing users and potential malicious attacks. Otherwise, network performance can be seriously deteriorated. One promising approach are decentralized reputation systems. However, these are vulnerable to users with an interest in passing on false information. Robustness against liars has not yet been analyzed in detail. In this paper, we provide a first step to the robustness analysis of a reputation system based on the deviation test as introduced in [6]. Users accept second hand information only if this does not differ too much from their reputation values. We show that the system exhibits a phase transition: In the subcritical regime, the reputation system is robust and the lying has no effect. In the supercritical regime, the lying does have an impact. We obtain the exact critical values via a mean field approach. We then use explicit computation to verify the mean field results. Thus, we can give conditions under which the deviation test makes the reputation system robust. We also obtain quantitative results on what goes wrong in the supercritical regime. [pdf]
    
    
60. Merz, Ruben; Le Boudec, Jean-Yves; Widmer, Jörg; Radunovic, Bozidar   [MerzLWR:04]   [published]
    A Rate-Adaptive MAC Protocol for Low-Power Ultra-Wide Band Ad-hoc Networks    
    Ad-Hoc Now 04, 3rd International Conference on AD-HOC Networks; Vancouver, British Columbia, Canada, 2004
    Recent theoretical results show that it is optimal to allow interfering sources to transmit simultaneously as long as they are outside a well-defined exclusion region around a destination and to adapt the rate to interference. In contrast, interference from inside the exclusion region needs to be controlled. Furthermore, when a source transmits, it should do so at maximum power. Based on these theoretical findings, we propose a cross-layer design of MAC and physical layer and present a fully distributed, rate adaptive MAC protocol for ultra-wide band (UWB) where sources constantly adapt their channel codes (and thus their rate) to the level of interference experienced at the destination. To mitigate the interference of sources inside the exclusion region, we propose a specific demodulation scheme that cancels most of the interfering energy. This scheme is entirely local to a destination and involves no protocol action. In contrast, existing MAC designs for UWB are either based on mutual exclusion, where no other communication is possible within the same collision domain, or based on power control. Through simulation we show that we achieve a significant increase in network throughput compared to traditional MAC proposals. Overall, we find that existing proposals do not fully take advantage of the specific nature of an ultra-wide band physical layer. [pdf]
    
    
61. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:04a]   [published]
    When Power Adaptation is Useless or Harmful    
    Technical Report EPFL IC/2004/60, July 2004
    We consider the design of optimal strategies for joint power adaptation, rate adaptation and scheduling in a multi-hop wireless network. Most existing strategies for ad-hoc networks control either power and scheduling, or rates and scheduling, but not the three together as we do. We assume the underlying physical layer allows fine-grained rate adaptation (like in 802.11a/g, HDR/CDMA, UWB). Our goal is to find properties of the power control in an optimal joint design. In the linear regime (i.e when the rate of a link can be approximated by a linear function of signal-to-noise ratio, SNR), we prove analytically that it is always optimal to use the simple 0-PMAX power control (when a node is sending it uses the maximum transmitting power allowed). This holds in both important networking scenarios: high rate networks where the goal is to maximize rates under power constraints, and low power networks where the goal is to minimize average consumed power while meeting minimum rate constraints. Moreover, we prove that, when maximizing rates, 0-PMAX is the only possible optimal power control strategy. Outside the linear regime, we do not know what the optimal power control is. We show that in the power minimization scenario, in some cases, rate adaptation and 0-PMAX power control performs much worse than power adaptation. Nevertheless, we conjecture, and we demonstrate numerically that when maximizing rates, even outside the linear regime, 0-PMAX is very close to the optimal power control, and the rate adaptation with 0-PMAX outperforms power adaptation with fixed link rates.
    
    
62. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:04b]   [published]
    A Robust Reputation System for Peer-to-Peer and Mobile Ad-hoc Networks    
    P2PEcon 2004; Harvard University, Cambridge MA, U.S.A., 2004
    Reputation systems can be tricked by the spread of false reputation ratings, be it false accusations or false praise. Simple solutions such as exclusively relying on one`s own direct observations have drawbacks, as they do not make use of all the information available. We propose a fully distributed reputation system that can cope with false disseminated information. In our approach, everyone maintains a reputation rating and a trust rating about everyone else that they care about. From time to time first-hand reputation information is exchanged with others
    
    
63. Le Boudec, Jean-Yves   [LeBoudec:04a]   [published]
    Understand the Simulation of Mobility Models with Palm Calculus    
    Technical Report EPFL IC/2004/43, June 2004
    This report is replaced by the revised version "Understanding the Simulation of Mobility Models with Palm Calculus" LCA-REPORT-2005-013 http://infoscience.epfl.ch/search.py?recid=52736&ln=en [pdf]
    
    
64. Sarafijanovic, Slavisa; Le Boudec, Jean-Yves   [SarafijanovicL:04a]   [published]
    An Artificial Immune System for Misbehavior Detection in Mobile Ad Hoc Networks with both Innate, Adaptive Subsystems and with Danger Signal    
    AISB 2004 Symposium on The Immune System and Cognition (ImmCog-2004); Leeds, UK, 2004, p. 45-46
    The document itself is an extended abstract. [pdf]
    
    
65. Le Boudec, Jean-Yves; Radunovic, Bozidar   [RadunovicL:04]   [published]
    Rate Performance Objectives of Multi-hop Wireless Networks    
    INFOCOM 04; Hong Kong, 2004
    We consider the question of what performance metric to maximize when designing adhoc wireless network protocols such as routing or MAC. We focus on maximizing rates under battery lifetime and power constraints. Commonly used metrics are total capacity (in the case of cellular networks) and transport capacity (in the case of adhoc networks). However, it is known in traditional wired networking that maximizing total capacity conflicts with fairness, and this is why fairness oriented rate allocations, such as max-min fairness, are often used. We review this issue for wireless ad-hoc networks. Indeed, the mathematical model for wireless networks has a specificity that makes some of the findings different. It has been reported in the literature on Ultra Wide Band that gross unfairness occurs when maximizing total capacity or transport capacity, and we confirm by a theoretical analysis that this is a fundamental shortcoming of such metrics in wireless ad-hoc networks, as it is for wired networks. The story is different for max-min fairness. Although it is perfectly viable for a wired network, it is much less so in our setting. We show that, in the limit of long battery lifetime, the max-min allocation of rates always leads to strictly equal rates, regardless of the MAC layer, network topology, choice of routes and power constraints. This is due to the ``solidarity [pdf]
    
    
66. Le Boudec, Jean-Yves; Sarafijanovic, Slavisa   [LeBoudecS:04]   [published]
    An Artificial Immune System Approach to Misbehavior Detection in Mobile Ad-Hoc Networks    
    Bio-ADIT 2004 (The First International Workshop on Biologically Inspired Approaches to Advanced Information Technology); Lausanne, Switzerland, 2004, p. 96-111
    In mobile ad-hoc networks, nodes act both as terminals and information relays, and participate in a common routing protocol, such as Dynamic Source Routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. In this paper we investigate the use of an Artificial Immune System (AIS) to detect node misbehavior in a mobile ad-hoc network using DSR. The system is inspired by the natural immune system of vertebrates. Our goal is to build a system that, like its natural counterpart, automatically learns and detects new misbehavior. We describe the first step of our design; it employs negative selection, an algorithm used by the natural immune system. We define how we map the natural immune system concepts such as self, antigen and antibody to a mobile ad-hoc network, and give the resulting algorithm for misbehavior detection. We implemented the system in the network simulator Glomosim; we present detection results and discuss how the system parameters impact the results. Further steps will extend the design by using an analogy to the innate system, danger signals, costimulation and memory cells. [pdf]
    
    
67. Sarafijanovic, Slavisa; Le Boudec, Jean-Yves   [SarafijanovicL:03]   [published]
    An Artificial Immune System Approach with Secondary Response for Misbehavior Detection in Mobile Ad-Hoc Networks    
    Technical Report No. IC/2003/65, EPFL, November 2003.
    In mobile ad-hoc networks, nodes act both as terminals and information relays, and participate in a common routing protocol, such as Dynamic Source Routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. In this paper we investigate the use of an Artificial Immune System (AIS) to detect node misbehavior in a mobile ad-hoc network using DSR. The system is inspired by the natural immune system of vertebrates. Our goal is to build a system that, like its natural counterpart, automatically learns and detects new misbehavior. We describe our solution for the classification task of the AIS; it employs negative selection and clonal selection, the algorithms for learning and adaptation used by the natural immune system.We define how we map the natural immune system concepts such as self, antigen and antibody to a mobile ad-hoc network, and give the resulting algorithm for classifying nodes as misbehaving. We implemented the system in the network simulator Glomosim; we present detection results and discuss how the system parameters impact the performance of primary and secondary response. Further steps will extend the design by using an analogy to the innate system, danger signal and memory cells. [pdf]
    
    
68. Buchegger, Sonja; Tissières, Cédric; Le Boudec, Jean-Yves   [BucheggerTL:03]   [published]
    A Test-Bed for Misbehavior Detection in Mobile Ad-hoc Networks --- How Much Can Watchdogs Really Do?    
    EPFL Technical Report No. IC/2003/72, November 2003
    Several misbehavior detection and reputation systems have been proposed for mobile ad-hoc networks, relying on direct network observation mechanisms, so-called watchdogs. While these approaches have so far only been evaluated in simulations and restricted to selfish packet dropping, we are interested in the capabilities of a watchdog detection component in a real network. In this paper we present our test-bed implementation of misbehavior detection. Following an evaluation of both the feasibility and detectability of attacks on routing and forwarding in the Dynamic Source Routing (DSR) protocol, we present the design of our test-bed. In order to add detection capabilities, we extend the concept of passive acknowledgment by mechanisms for partial dropping, packet modification, and fabrication detection. We combine DSR with Netfilter and APE to enable detection. We implement both attackers and detection and show their feasibility and limitations. [pdf]
    
    
69. Le Boudec, Jean-Yves; Sarafijanovic, Slavisa   [LeBoudecS:03]   [published]
    An Artificial Immune System Approach to Misbehavior Detection in Mobile Ad-Hoc Networks    
    Technical Report No. IC/2003/59, EPFL, September 2003,
    In mobile ad-hoc networks, nodes act both as terminals and information relays, and participate in a common routing protocol, such as Dynamic Source Routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. In this paper we investigate the use of an Artificial Immune System (AIS) to detect node misbehavior in a mobile ad-hoc network using DSR. The system is inspired by the natural immune system of vertebrates. Our goal is to be able to build a system that, like its natural counterpart, automatically learns and detects new misbehavior. We describe the first step of our design; it employs negative selection, an algorithm used by the natural immune system. We define how we map the natural immune system concepts such as self, antigen and antibody to a mobile ad-hoc network, and give the resulting algorithm for misbehavior detection. We implemented the system in the network simulator Glomosim; we present detection results and discuss how the system parameters impact the results. Further steps will extend the design by using an analogy to the innate system, danger signals, costimulation and memory cells. [pdf]
    
    
70. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:03b]   [published]
    A Robust Reputation System for Mobile Ad-hoc Networks    
    Technical report No. IC/2003/50, July 2003
    Reputation systems in mobile ad-hoc networks can be tricked by the spreading of false reputation ratings, be it false accusations or false praise. Simple solutions such as exclusively relying on one's own direct observations have drawbacks, as they do not make use of all the information available. We propose a fully distributed reputation system that can cope with false disseminated information. In our approach, everyone maintains a reputation rating and a trust rating about everyone else that they care about. From time to time first-hand reputation information is exchanged with others; using a modified Bayesian approach we designed and present in this paper, only second-hand reputation information that is not incompatible with the current reputation rating is accepted. Thus, reputation ratings are slightly modified by accepted information. Trust ratings are updated based on the compatibility of second-hand reputation information with prior reputation ratings. Data is entirely distributed: someone's reputation and trust is the collection of ratings maintained by others. We enable node redemption and prevent the sudden exploitation of good reputation built over time by introducing re-evaluation and reputation fading. We present the application of our generic reputation system to the context of neighborhood watch in mobile ad-hoc networks, specifically to the CONFIDANT protocol for the detection and isolation of nodes exhibiting routing or forwarding misbehavior. We evaluate the performance by simulation. [pdf]
    
    
71. Buchegger, Sonja; Le Boudec, Jean Yves   [BucheggerL:03a]   [published]
    Coping with False Accusations in Misbehavior Reputation Systems for Mobile Ad-hoc Networks    
    Technical Report IC/2003/31, EPFL, May 2003
    Some misbehavior detection and reputation systems in mobile ad-hoc networks rely on the dissemination of information of observed behavior, which makes them vulnerable to false accusations. This vulnerability could be removed by forbidding the dissemination of information on observed behavior in the first place, but, as we show here, this has more drawbacks than a solution that allows dissemination and copes with false accusations. We propose a method for reducing the impact of false accusations. In our approach, nodes collect first-hand information about the behavior of other nodes by direct observation. In addition, nodes maintain a rating about every other node that they care about, in the form of a continuous variable per node. From time to time nodes exchange their first-hand information with others, but, using the Bayesian approach we designed and present in this paper, only second-hand information that is not incompatible with the current rating is accepted. Ratings are slightly modified by accepted information. The reputation of a given node is the collection of ratings maintained by others about this node. By means of simulation we evaluated the robustness of our approach against several types of adversaries that spread false information, and its efficiency at detecting malicious nodes. The simulation results indicate that our system largely reduces the impact of false accusations, while still benefiting from the accelerated detection of malicious nodes provided by second-hand information. We also found that when information dissemination is not used, the time until malicious nodes are detected can be unacceptable. [pdf]
    
    
72. Radunovic, Bozidar; Le Boudec, Jean-Yves   [RadunovicL:03]   [published]
    Joint Scheduling, Power Control and Routing in Symmetric, One-dimensional, Multi-hop Wireless Networks    
    WiOpt`03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks; INRIA Sophia-Antipolis, France, 2003
    We are interested in finding a jointly optimal scheduling, routing and power control that achieves max-min fair rate allocation in a multi-hop wireless network. This is a highly complex non-convex optimization problem and it has been previously solved only for small networks. We restrict ourselves to symmetric networks with ring and line topologies, and we numerically solve the problem for a large number of nodes. We model point-to- point links as single user Gaussian channels where nodes cannot send and receive at the same time. This type of channel approximates the performance of CDMA networks and performs better than the equivalent 802.11 network. We show that for smaller transmission powers it is optimal to relay over other nodes whereas for high powers it is optimal to send data directly to a destination. We also show when this transition occurs. We analyze the optimal schedule and find that if a node is active, it should send at the maximum power. When a transmission power is small, the optimal schedule is that every second node is sending, and as the power grows, the distance between active nodes grows. Furthermore, in large networks the distance between nodes sending at the same time is never larger than 4.5 times the size of links used (number of nodes spanned by one transmission link), and it converges to that value for large transmission powers. [pdf]
    
    
73. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:03]   [published]
    The Effect of Rumor Spreading in Reputation Systems for Mobile Ad-hoc Networks     
    WiOpt `03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks; Sophia-Antipolis, France, 2003
    Mobile ad-hoc networks rely on the cooperation of nodes for routing and forwarding. For individual nodes there are however several advantages resulting from noncooperation, the most obvious being power saving. Nodes that act selfishly or even maliciously pose a threat to availability in mobile ad-hoc networks. Several approaches have been proposed to detect noncooperative nodes. In this paper, we investigate the effect of using rumors with respect to the detection time of misbehaved nodes as well as the robustness of the reputation system against wrong accusations. We propose a Bayesian approach for reputation representation, updates, and view integration. We also present a mechanism to detect and exclude potential lies. The simulation results indicate that by using this Bayesian approach, the reputation system is robust against slander while still benefitting from the speed-up in detection time provided by the use of rumors. [pdf]
    
    
74. Radunovic, Bozidar; Le Boudec, Jean-Yves   [LeBoudecR:02]   [published]
    A Unified Framework for Max-Min and Min-Max Fairness with Applications    
    40th Annual Allerton Conference on Communication, Control, and Computing; Allerton, IL, 2002
    Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing the max-min fair allocation; in most, but not all cases, they are based on the notion of bottlenecks. In spite of this wide applicability, there are still examples, arising in the context of mobile or peer-to-peer networks, where the existing theories do not seem to apply directly. In this paper, we give a unifying treatment of max-min fairness, which encompasses all existing results in a simplifying framework, and extends its applicability to new examples. First, we observe that the existence of max-min fairness is actually a geometric property of the set of feasible allocations (uniqueness always holds). There exist sets on which max-min fairness does not exist, and we describe a large class of sets on which a max-min fair allocation does exist. This class contains the compact, convex sets of \RR^N, but not only. Second, we give a general purpose, centralized algorithm, called Max-min Programming, for computing the max-min fair allocation in all cases where it exists (whether the set of feasible allocations is in our class or not). Its complexity is of the order of N linear programming steps in R^N, in the case where the feasible set is defined by linear constraints. We show that, if the set of feasible allocations has the free-disposal property, then Max-min Programming degenerates to a simpler algorithm, called Water Filling, whose complexity is much less. Free disposal corresponds to the cases where a bottleneck argument can be made, and Water Filling is the general form of all previously known centralized algorithms for such cases. Our derivations are based on the relation between max-min fairness and leximin ordering. All our results apply mutatis mutandis to min-max fairness. Our results apply to weighted, unweighted and util-max-min and min-max fairness. Distributed algorithms for the computation of max-min fair allocations are left outside the scope of this paper. [ps]
    
    
75. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:02c]   [published]
    Cooperative Routing in Mobile Ad-hoc Networks: Current Efforts Against Malice and Selfishness    
    Mobile Internet Workshop. Informatik 2002.; Dortmund, Germany, 2002
    In mobile ad-hoc networks, nodes do not rely on any routing infrastructure but relay packets for each other. Thus communication in mobile ad-hoc networks functions properly only if the participating nodes cooperate in routing and forwarding. However, it may be advantageous for individual nodes not to cooperate, for example to save power or to launch security attacks such as denial-of-service. In this paper, we give an overview of potential vulnerabilities and requirements of mobile ad-hoc networks, and of proposed prevention, detection and reaction mechanisms to thwart attacks. [pdf]
    
    
76. S. Buchegger, J.-Y. Le Boudec   [BucheggerL:02b]   [published]
    Performance Analysis of the CONFIDANT Protocol: Cooperation Of Nodes - Fairness In Distributed Ad-hoc NeTworks    
    MobiHoc 2002, Lausanne, 9-11 June 2002
    Mobile ad-hoc networking works properly only if the participating nodes cooperate in routing and forwarding. However, it may be advantageous for individual nodes not to cooperate. We propose a protocol, called CONFIDANT, for making misbehavior unattractive; it is based on selective altruism and utilitarianism. It aims at detecting and isolating misbehaving nodes, thus making it unattractive to deny cooperation. Trust relationships and routing decisions are based on experienced, observed, or reported routing and forwarding behavior of other nodes. The detailed implementation of CONFIDANT in this paper assumes that the network layer is based on the Dynamic Source Routing (DSR) protocol. We present a performance analysis of DSR fortified by CONFIDANT and compare it to regular defenseless DSR. It shows that a network with CONFIDANT and up to 60% of misbehaving nodes behaves almost as well as a benign network, in sharp contrast to a defenseless network. All simulations have been implemented and performed in GloMoSim. [pdf]
    
    
77. Blazevic, Ljubica; Le Boudec, Jean-Yves   [BlazevicL:02]   [published]
    Terminode Routing - A Scalable Routing Scheme for Large Mobile Ad Hoc Networks     
    Workshop on Multiaccess, Mobility and Teletraffic for Wireless Communications(invited speaker); Rennes, France (http://www.rennes.enst-bretagne.fr/~xlagrang/Mmt02/), 2002
    No abstract [pdf]
    
    
78. Blazevic, Ljubica; Giordano, Silvia; Le Boudec, Jean-Yves   [BlazevicGL:02b]   [published]
    Anchored Path Discovery in Terminode Routing    
    The Second IFIP-TC6 Networking Conference (Networking 2002); Pisa, 2002
    Terminode routing, defined for potentially very large mobile ad hoc networks, forwards packets along anchored paths. An anchored path is a list of fixed geographic points, called anchors. Given that geographic points do not move, the advantage to traditional routing paths is that an anchored path is always [pdf]
    
    
79. Blazevic, Ljubica; Giordano, Silvia; Le Boudec, Jean-Yves   [BlazevicGL:02a]   [published]
    Self Organized Terminode Routing    
    Journal of Cluster Computing,, 2002, vol. 5, no 2
    We consider the problem of routing in a wide area mobile ad-hoc network called Terminode Network. Routing in this network is designed with the following objectives. First, it should scale well in terms of the number of nodes and geographical coverage [pdf]
    
    
80. Blazevic, Ljubica; Le Boudec, Jean Yves   [Blazevic:02]   [published]
    Scalable routing protocols with applications to mobility    
    PhD Thesis EPFL, accepted in Feb 2002, Prof. JY Le Boudec
    [pdf]
    
    
81. Blazevic, Ljubica; Le Boudec, Jean-Yves; Giordano, Silvia   [BlazevicLG:02]   [published]
    A Scalable Routing Scheme for Self-Organized Terminode Network    
    Communication Networks and Distributed systems modeling and Simulation conference (CNDS); San Antonio, Texas,USA, 2002
    The focus of this paper is routing in a wide area mo-bile ad hoc network referred to as a Terminode Network. Our routing scheme is a combination of two protocols: Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is used for rem ote destinations. It utilizes the location of a destination obtained by the source using location management or location tracking. TLR acts when the packet gets close to the destination. The use of TRR results in a scalable solution that reduces d ependen ce on the intermediate systems, while TLR reduces problems due to the destination location inaccuracy. This paper describes TLR and TRR and the interaction between them. Terminode routing is implemented and evaluated using GloMoSim simulator. For the purp ose of more realistic rout-ing evaluation we designed a new mobility model, the restricted random waypoint model, which represents more realistic mo-bility pattern in a large scale mobile ad hoc environment. [pdf]
    
    
82. Buchegger, Sonja; Le Boudec, Jean-Yves   [BucheggerL:02a]   [published]
    Nodes Bearing Grudges: Towards Routing Security, Fairness, and Robustness in Mobile Ad Hoc Networks     
    Tenth Euromicro PDP (Parallel, Distributed and Network-based Processing); Gran Canaria, 2002, p. 403 - 410
    Devices in mobile ad hoc networks work as network nodes and relay packets originated by other nodes. Mobile ad hoc networks can work properly only if the participating nodes cooperate in routing and forwarding. For individual nodes it might be advantageous not to cooperate, though. The new routing protocol extensions presented in this paper make it possible to detect and isolate misbehaving nodes, thus making it unattractive to deny cooperation. In the presented scheme,trust relationships and routing decisions are made based on experienced, observed, or reported routing and forwarding behavior of other nodes. A hybrid scheme of selective altruism and utilitarianism is presented to strengthen mobile ad hoc network protocols in their resistance to security attacks, while aiming at keeping network throughput, or goodput, high. This paper focuses particularly on the network layer, using the Dynamic Source Routing (DSR) protocol as an example. [pdf]
    
    
83. Blazevic, Ljubica; Giordano, Silvia; Le Boudec, Jean-Yves   [BlazevicGL:01]   [published]
    Self Organized Routing in Wide Area Mobile Ad Hoc Network     
    IEEE Symposium on Ad Hoc Wireless Networks (Globecom 2001); San Antonio, Texas, 2001
    This paper considers the problem of routing in a wide area mobile ad-hoc network called Terminode Network. Our routing scheme is a combination of two protocols called Termin-ode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is activated when the destination is remo t e and uses loca-tion of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR al-lows to reduce problems due to location inaccuracy. The paper describes TLR and TRR protocols and presents some simulation results. [pdf]
    
    
84. Blazevic, Ljubica; Buttyan, Levente; Capkun, Srdjan; Giordano, Silvia; Hubaux, Jean-Pierre; Le Boudec, Jean-Yves   [BlazevicBCGHL:01]   [published]
    Self-Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes    
    IEEE Communications Magazine, 2001, vol. 39, no 6, p. 166
    The Terminodes project is designing a wide area, mobile ad-hoc network, which is meant to be used in a public environment, in our approach, the network is run by users themselves. We give a global description of the building blocks used by the basic operation of the network, they all rely on various concepts of self-organization. Routing uses a combination of geography-based information and local, MANET-like protocols. Terminode positioning is obtained either by GPS, or by a relative positioning method. Mobility management uses self-organized virtual regions. Terminodes employ a form of virtual money called ``nuglets [pdf] [ps]
    
    
85. Hubaux, Jean-Pierre; Gross, Thomas; Le Boudec, Jean-Yves; Vetterli, Martin   [HubauxGLV:01]   [published]
    Towards self-organized mobile ad hoc networks: The terminodes project    
    IEEE Communications Magazine, vol. 39, no 1, p. 118-124
    This article provides a technical overview of mobile ad hoc networks and describes their long-term potential. It covers current research, and describes major technical challenges, including networking, real-time services, and software. It shows that by their very nature, mobile ad hoc networks can bring a paradigm shift in the way networks are organized and operated, and can even lead to a fundamental change in the relationships between information technology and societal organization. As an illustration of these concepts, the article also contains an overall description of our long-term research project, called terminodes [pdf]
    
    
86. Hubaux, Jean-Pierre; Le Boudec, Jean-Yves; Vojnovic, Milan; Giordano, Silvia; Hamdi, Maher; Blazevic, Ljubica; Buttyan, Levente   [HubauxLGHBBV:00]   [published]
    Towards Mobile Ad-Hoc WANs: Terminodes    
    Technical Report SSC/2000/06, EPFL
    Terminodes are personal devices that provide functionality of both the terminals and the nodes of the network. A network of terminodes is an autonomous, fully self-organized, wireless network, independent of any infrastructure. It must be able to scale up to millions of units, without any fixed backbone or server. In this paper we present the main challenges and discuss the main technical directions. [pdf]
    
    
87. Blazevic, Ljubica; Giordano, Silvia; Le Boudec, Jean-Yves   [BlazevicGL:00]   [published]
    Self-Organizing Wide-Area Routing    
    SCI 2000/ISAS 2000; Orlando, 2000
    We consider the problem of routing in a Mobile Ad-Hoc wide area network called Terminodes Network. In our solution every node builds its personal view of the network, composed of local and remote views. Large scale routing in the terminode network is achieved by the combination of these two views. We describe two methods called Terminode Local Routing (TLR) and Anchored Geodesic Packet Forwarding (AGPF) that are used for routing in such a network, as well as path discovery and path maintenance mechanisms. [ps]
    
    
88. Giordano, Silvia; Hamdi, M.; Hubaux, Jean-Pierre; Le Boudec, Jean-Yves; Blazevic, Ljubica   [GiordanoHHLB:00]   [published]
    Issues on Mobile Ad-Hoc WANs    
    ICME2000; NY - US, 2000, p. 4
    In this paper we present the main challenges in mobile ad-hoc wide area networks (MAWANs). A MAWAN is a wide area, large, (potentially) entirely wireless networks. We describe the Terminodes Project (a 10-year-long research program (2000-2010) in MAWANs, see http://www.terminodes.org) that investigates issues and challenges in MAWANs. The name of the project comes from the fact that the elements of the network act as nodes and terminals at the same (terminodes). [html] [pdf]
    
    
89. S. Giordano, M. Hamdi, J. P. Hubaux, J. Y. Le Boudec   [GiordanoHHL:99]   [published]
    The Terminodes Project: Towards Mobile Ad-Hoc WANs    
    MOMUC 99, San Diego, November 1999
    The Terminode project follows a system approach to investigate wide area, large, totally wireless networks that we call mobile ad-hoc wide area networks. A network of terminodes is an autonomous, self-operated, wireless multimedia network, independent of any infrastructure. In this paper we present the main challenges and certain initial technical directions. [ps]