Ultra Low Power Communication Protocols for UWB Impulse Radio Wireless Sensor Networks

This thesis evaluates the potential of Ultra Wideband Impulse Radio for wireless sensor network applications. Wireless sensor networks are collections of small electronic devices composed of one or more sensors to acquire information on their environment, an energy source (typically a battery), a microcontroller to control the measurements, process the information and communicate with its peers, and a radio transceiver to enable these communications. They are used to regularly collect information within their deployment area, often for very long periods of time (up to several years). The large number of devices often considered, as well as the long deployment durations, makes any manual intervention complex and costly. Therefore, these networks must self-configure, and automatically adapt to changes in their electromagnetic environment (channel variations, interferers) and network topology modifications: some nodes may run out of energy, or suffer from a hardware failure. Ultra Wideband Impulse Radio is a novel wireless technology that, thanks to its extremely large bandwidth, is more robust to frequency dependent propagation effects. Its impulsional nature makes it robust to multipath fading, as the short duration of the pulses leads most multipath components to arrive isolated. This technology should also enable high precision ranging through time of flight measurements, and operate at ultra low power levels. The main challenge is to design a system that reaches the same or higher degree of energy savings as existing narrowband systems considering all the protocol layers. As these radios are not yet widely available, the first part of this thesis presents Maximum Pulse Amplitude Estimation, a novel approach to symbol-level modeling of UWB-IR systems that enabled us to implement the first network simulator of devices compatible with the UWB physical layer of the IEEE 802.15.4A standard for wireless sensor networks. In the second part of this thesis, WideMac, a novel ultra low power MAC protocol specifically designed for UWB-IR devices is presented. It uses asynchronous duty cycling of the radio transceiver to minimize the power consumption, combined with periodic beacon emissions so that devices can learn each other's wake-up patterns and exchange packets. After an analytical study of the protocol, the network simulation tool presented in the first part of the thesis is used to evaluate the performance of WideMac in a medical body area network application. It is compared to two narrowband and an FM-UWB solutions. The protocol stack parameters are optimized for each solution, and it is observed that WideMac combined to UWB-IR is a credible technology for such applications. Similar simulations, considering this time a static multi-hop network are performed. It is found that WideMac and UWB-IR perform as well as a mature and highly optimized narrowband solution (based on the WiseMAC ULP MAC protocol), despite the lack of clear channel assessment functionality on the UWB radio. The last part of this thesis studies analytically a dual mode MAC protocol named WideMac-High Availability. It combines the Ultra Low PowerWideMac with the higher performance Aloha protocol, so that ultra low power consumption and hence long deployment times can be combined with high performance low latency communications when required by the application. The potential of this scheme is quantified, and it is proposed to adapt it to narrowband radio transceivers by combining WiseMAC and CSMA under the name WiseMAC-HA.

Mobility-centric design of collaborative transportation systems

Embedded sensors and actuators are revolutionizing the way we perceive and interact with the physical world. Current research on such Cyber-Physical Systems (CPSs) has focused mostly on distributed sensing and data gathering. The next step is to move from passive information extraction from the physical world towards an active framework where information is retrieved, processed, and acted upon in situ. As an example of such sensor-actuator systems that provide large-scale, distributed coordination, we consider Intelligent Transportation Systems (ITSs), with the goal of increasing travel safety and efficiency. The proliferation of wireless technologies enables different actors (e.g., pedestrians, motorists, traffic operators) to communicate with each other cheaply, efficiently, and securely. By embedding computational intelligence, communication and control into such ITSs, it will be possible to build collaborative transportation applications that help solve, for example, congestion and parking problems. This thesis explores the following question: To what extent is it possible to build distributed ITS systems that rely exclusively on local communication between nodes? The potential benefits of building such systems without infrastructure are numerous, including lower fixed and variable costs, avoiding regulatory hurdles, lower entry barriers for new players, and more control over privacy. On the other hand, self-organized ITSs without infrastructure have to operate under challenging conditions: large scale, high mobility, lack of end-to-end connectivity, ephemeral contacts between wireless nodes, and heterogeneous node capabilities. Although the networking research community has invested a significant effort in designing service abstractions that mimic traditional IP connectivity on top of wireless ad hoc networks, the ITS scenarios considered in this work are too challenging to implement such a service model. The main goal of this thesis is to design communication service models and their underlying protocols that can operate in collaborative transportation applications, and to demonstrate their effectiveness through analysis of traffic data and through realistic simulations. A key point is that the ITS applications we consider can rely on more limited service primitives, because they do not require a general any-to-any delivery service with strict performance guarantees. We first define the collaborative transportation applications of interest. Then we quantify their potential benefits and discuss their functional requirements. Next, we focus on the problem of the collection of large-scale mobility data. We propose a new method for collecting such data and introduce a novel mobility data mining framework, which is necessary to study collective mobility patterns in the context of wireless ad hoc networking. Relying on the analysis of real-life mobility traces, we find that despite the high node mobility, clusters of time-stable connectivity emerge and last at specific locations. Outside such clusters the connectivity between nodes remains sparse. This leads us to the proposal of a new mobility model that captures in an elegant way two phenomena observed in reality, i.e., emergence of stable clusters and network partitioning. This mobility model, called Heterogeneous Random Walk (HRW), appears to be the worst-case mobility model for many mobility-assisted protocols. Moreover, we show that the HRW mobility model predicts the performance of an epidemic dissemination protocol more accurately than other, similarly parsimonious models. Based on the lessons learned from the mobility data analysis, we propose a new abstraction that allows us to capture collective mobility patterns. This abstraction, called a Mobility Map, can be shared globally among mobile nodes and it can be used to improve communication in mobile partitioned networks (MPNs). Notably, we present a new geocasting protocol called GeoMobCast, which uses Mobility Maps to minimize message delay. This protocol is designed to provide the users of the collective transportation applications with the required communication service. Finally, we turn our attention on the real-life implementation of the distributed ITS that leverage short-range wireless communication. To this extent, we present the results of our experimental work with wireless sensor network technologies. We also present the necessary simulation toolbox designed to implement and evaluate collaborative transportation applications.

EPFL2009

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

Rate Performance Objectives of Multi-hop Wireless Networks

Jean-Yves Le Boudec

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

2004

Mobility-centric design of collaborative transportation systems

EPFL2009

On uncoordinated wireless ad-hoc networks

Alaeddine El Fawal

EPFL2009