Routing and search on large scale networks

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.

Modeling and Measuring Performance of Data Dissemination in Opportunistic Networks

Nikodin Ristanovic

In this thesis we focus on understanding, measuring and describing the performance of Opportunistic Networks (ONs) and their applications. An “opportunistic network” is a term introduced to describe a sparse, wireless, ad hoc network with highly mobile nodes. The opportunistic networking paradigm deviates from the traditional end-to-end connectivity concept: Forwarding is based on intermittent connectivity between mobile nodes (typically, users with wireless devices); complete routes between sources and destinations rarely exist. Due to this unique property of spontaneous link establishment, the challenges that exist in ONs are specific. The unstructured nature of these networks makes it difficult to give any performance guarantees on data dissemination. For this reason, in Part I of this thesis we explore the dynamics that affect the performance of opportunistic networks. We choose a number of meaningful scenarios where our models and algorithms can be validated using large and credible data sets. We show that a drift and jump model that takes a spatial approach succeeds in capturing the impact of infrastructure and mobile-to-mobile exchanges on an opportunistic content update system. We describe the effects of these dynamics by using the age distribution of a dynamic piece of data (i.e., information updates) as the performance measure. The model also succeeds in capturing a strong bias in user mobility and reveals the existence of regions, whose statistics play a critical role in the performance perceived in the network. We exploit these findings to design an application for greedy infrastructure placement, which relies on the model approximation for a large number of nodes. Another great challenge of opportunistic networking lies in the fact that the bandwidth available on wireless links, coupled with ad hoc networking, failed to rival the capacity of backbones and to establish opportunistic networks as an alternative to infrastructure-based networks. For this reason, we never study ONs in an isolated context. Instead, we consider the applications that leverage interconnection between opportunistic networks and legacy networks and we study the benefits this synergy brings to both. Following this approach, we use a large operator-provided data set to show that opportunistic networks (based on Wi-Fi) are capable of offloading a significant amount of traffic from 3G networks. At the same time, the offloading algorithms we propose reduce the amount of energy consumed by mobiles, while requiring Wi-Fi coverage that is several times smaller than in the case of real-time offloading. Again we confirm and reuse the fact that user mobility is biased towards certain regions of the network. In Part II of this thesis, we treat another issue that is essential for the acceptance and evolution of opportunistic networks and their applications. Namely, we address the absence of experimental results that would support the findings of simulation based studies. Although the techniques such as contact-based simulations should intuitively be able to capture the performance of opportunistic applications, this intuition has little evidence in practice. For this reason, we design and deploy an experiment with real users who use an opportunistic Twitter application, in a way that allows them to maintain communication with legacy networks (i.e., cellular networks, the Internet). The experiment gives us a unique insight into certain performance aspects that are typically hidden or misinterpreted when the usual evaluation techniques (such as simulation) are used. We show that, due to the commonly ignored factors (such as the limited transmission bandwidth), contact-based simulations significantly overestimate delivery ratio and obtain delays that are several times lower than those experimentally acquired. In addition to this, our results unanimously show that the common practice of assuming infinite cache sizes in simulation studies, leads to a misinterpretation of the effects of a backbone on an opportunistic network. Such simulations typically overestimate the performance of the opportunistic component, while underestimating the utility of the backbone. Given the discovered deficiencies of the contact-based simulations, we consider an alternative statistical treatment of contact traces that uses the weighted contact graph. We show that this approach offers a better interpretation of the impact of a backbone on an opportunistic network and results in a closer match when it comes to modeling certain aspects of performance (namely, delivery ratio). Finally, the security requirements for the opportunistic applications that involve an interconnection with legacy networks are also highly specific. They cannot be fully addressed by the solutions proposed in the context of autonomous opportunistic (or ad hoc) networks, nor by the security frameworks used for securing the applications with continuous connectivity. Thus, in Part III of this thesis, we put together a security framework that fits the networks and applications that we target (i.e., the opportunistic networks and applications with occasional Internet connectivity). We then focus on the impact of security print on network performance and design a scheme for the protection of optimal relaying capacity in an opportunistic multihop network. We fine-tune the parameters of our scheme by using a game-theoretic approach and we demonstrate the substantial performance gains provided by the scheme.

EPFL2012

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

Low Complexity Scheduling and Coding for Wireless Networks

Siddhartha Brahma

The advent of wireless communication technologies has created a paradigm shift in the accessibility of communication. With it has come an increased demand for throughput, a trend that is likely to increase further in the future. A key aspect of these challenges is to develop low complexity algorithms and architectures that can take advantage of the nature of the wireless medium like broadcasting and physical layer cooperation. In this thesis, we consider several problems in the domain of low complexity coding, relaying and scheduling for wireless networks. We formulate the Pliable Index Coding problem that models a server trying to send one or more new messages over a noiseless broadcast channel to a set of clients that already have a subset of messages as side information. We show through theoretical bounds and algorithms, that it is possible to design short length codes, poly-logarithmic in the number of clients, to solve this problem. The length of the codes are exponentially better than those possible in a traditional index coding setup. Next, we consider several aspects of low complexity relaying in half-duplex diamond networks. In such networks, the source transmits information to the destination through

n

half-duplex intermediate relays arranged in a single layer. The half-duplex nature of the relays implies that they can either be in a listening or transmitting state at any point of time. To achieve high rates, there is an additional complexity of optimizing the schedule (i.e. the relative time fractions) of the relaying states, which can be

2^n

in number. Using approximate capacity expressions derived from the quantize-map-forward scheme for physical layer cooperation, we show that for networks with

n\leq 6

relays, the optimal schedule has atmost

n+1

active states. This is an exponential improvement over the possible

2^n

active states in a schedule. We also show that it is possible to achieve at least half the capacity of such networks (approximately) by employing simple routing strategies that use only two relays and two scheduling states. These results imply that the complexity of relaying in half-duplex diamond networks can be significantly reduced by using fewer scheduling states or fewer relays without adversely affecting throughput. Both these results assume centralized processing of the channel state information of all the relays. We take the first steps in analyzing the performance of relaying schemes where each relay switches between listening and transmitting states randomly and optimizes their relative fractions using only local channel state information. We show that even with such simple scheduling, we can achieve a significant fraction of the capacity of the network. Next, we look at the dual problem of selecting the subset of relays of a given size that has the highest capacity for a general layered full-duplex relay network. We formulate this as an optimization problem and derive efficient approximation algorithms to solve them. We end the thesis with the design and implementation of a practical relaying scheme called QUILT. In it the relay opportunistically decodes or quantizes its received signal and transmits the resulting sequence in cooperation with the source. To keep the complexity of the system low, we use LDPC codes at the source, interleaving at the relays and belief propagation decoding at the destination. We evaluate our system through testbed experiments over WiFi.

EPFL2015