A framework for network coding in challenged wireless network

David Cavin, Alaeddine El Fawal, Jean-Yves Le Boudec, Yoav Sasson
2006
Discussion par affiche

Résumé

Network coding is an area that has emerged in 2000, and has since then attracted an increasing interest, as it promises to have a significant impact in both the theory and practice of networks. To evaluate its performance in realistic situation, we developed a network coding based framework for challenged wireless networks where disconnection and reconnection is frequent as in PANs (Personal Area Networks) or vehicular networks, resulting in a new appelation for these scenarios as Delay Tolerant networks (DTN). For living in such hostile environment our development complies with several constraints as portability, flexibility, genericity, etc. Moreover to reduce the development effort using our framework, a single implementation might be used as standalone as well as inside a simulation environment.

Official source

https://infoscience.epfl.ch/record/88682?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

On uncoordinated wireless ad-hoc networks

Alaeddine El Fawal

Emerging pervasive wireless networks, pocket switched networks, Internet of things, vehicular networks and even sensor networks present very challenging communication circumstances. They might involve up to several hundreds of wireless devices with mobility and intermittent connectivity. Centralized coordination in such networks is practically unfeasible. We deal with these challenge using two potential technologies: WIFI and Ultra Wide Band (UWB) Impulse Radio (IR) for medium and short communication range, respectively. Our main goal is to improve the communication performance and to make these networks sustainable in the absence of a centralized coordination. With WIFI, the goal is to design an environment-oblivious data dissemination protocol that holds in highly dynamic unpredictable wireless ad-hoc networks. To this end, we propose a complete design for a scope limited, multi-hop broadcast middleware, which is adapted to the variability of the ad-hoc environment and works in unlimited ad-hoc networks such as a crowd in a city, or car passengers in a busy highway system. We address practical problems posed by: the impossibility of setting the TTL correctly at all times, the poor performance of multiple access protocols in broadcast mode, flow control when there is no acknowledgment and scheduling of multiple concurrent broadcasts. Our design, called "Self Limiting Epidemic Forwarding" (SLEF), automatically adapts its behavior from single hop MAC layer broadcast to epidemic forwarding when the environment changes from being extremely dense to sparse, sporadically connected. A main feature of SLEF is a non-classical manipulation of the TTL field, which combines the usual decrement-when-sending to many very small decrements when receiving. Then, we identify vulnerabilities that are specific to epidemic forwarding. We address broadcast applications over wireless ad-hoc networks. Epidemic forwarding employs several mechanisms such as forwarding factor control and spread control, and each of them can be implemented using alternative methods. Thus, the existence of vulnerabilities is highly dependent on the methods used. We examine the links between them. We classify vulnerabilities into two categories: malicious and rational. We examine the effect of the attacks according to the number of attackers and the different network settings such as density, mobility and congestion. We show that malicious attacks are hard to achieve and their effects are scenario-dependent. In contrast, rational attackers always obtain a significant benefit. The evaluation is carried out using detailed realistic simulations over networks with up to 1000 nodes. We consider static scenarios, as well as vehicular networks. In order to validate our simulation results, we build a solid and widely adaptable experimental testbed for wireless networks. It is composed of 57 mobile wireless nodes equipped with WIFI interface. The adopted platform is OpenWrt, a Linux-like firmware, which makes the testbed robust and easily configurable. With UWB IR, the main problem we deal with is the presence of uncontrolled interference. Indeed, similarly to Code Division Multiple Access (CDMA) systems, signal acquisition with UWB IR signaling requires power control in the presence of interferers, which is very expensive in an uncoordinated system. We solve this problem through a cross-layer optimization: We propose a new signal acquisition method that is independent of the received signal power and we adapt the MAC layer accordingly. Our signal acquisition method 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 a common code for control or broadcast purposes. At the MAC level, we focus only on one component of a MAC layer, which is the sleeping mode that could be added to any MAC layer proposal adequate to UWB IR. We are motivated by the low power consumption constraint required by the potential applications. We identify the design elements that should be taken into account for an optimal design for a sleeping protocol for UWB-IR such as the possibility of transmitting concurrently without collision and the power consumption model of the hardware behind which is completely different than with the narrow-band signaling. Then, we design two sleeping protocols for centralized and decentralized ad-hoc networks, respectively. We evaluate their performance analytically with the adopted metric being the average life-time of the wireless nodes.

EPFL2009

Chargement

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

EPFL2010

Chargement

Nowadays the demand for communication over the wireless medium is significantly increasing, while the available wireless spectrum is already limited. In this thesis, we introduce new practical physical layer designs that employ node cooperation for more efficient wireless spectrum utilization. First, a cooperative scheme is introduced that takes advantage of the existence of simultaneous multiple frequency band operation in modern wireless devices. The main idea of this scheme is to use one frequency band for sharing data among collaborating nodes, and another one for cooperatively transmitting to a common destination. The benefits of such a cooperative design across frequency bands are evaluated on a testbed of software-defined radios, where we investigate and identify the possible network conditions under which our scheme enables better throughput compared to the traditional operation. Second, we present a practical design that facilitates physical layer cooperation in Long Term Evolution (LTE) networks. The main idea here is to adapt the inherent Hybrid Automatic Repeat-reQuest (H-ARQ) in standard LTE operation, so that multiple relays can cooperate over the transmission of one encoded block. Performance evaluation of the design reveals significant throughout gains under asymmetric channel conditions for parallel relay networks in LTE framework. Finally, we look at the node cooperation from a privacy perspective in wireless sensor networks. To this end, we design and evaluate a low-overhead message encryption protocol based on network coding. The main idea of the protocol is to employ node cooperation to increase the inherent weak security that network coding offers. Results show up to 60% increase in terms of extra security added on top of the inherent one.

EPFL2015

Chargement

On uncoordinated wireless ad-hoc networks

Alaeddine El Fawal

EPFL2009

EPFL2010