Project Topics
Get Complete Project Material File(s) Now! »
Physical Layer Modeling
In a WSN, messages are sent with a radio transceiver on a shared medium. In this context, modeling the way the signal propagates is crucial to evaluate how the message is received by other nodes. Physical layer modeling includes the radio range modeling, the radio link modeling, and the interference modeling [HCG09].
Radio Range Modeling
The range modeling is based on the Signal to Noise Ratio (SNR) of links. The SNR of a link (i; j), denoted snr(i; j), is defined as the path-loss PLi;j times the ratio between the power of the signal Pi over the power of the background noise Nj at node j: snr(i; j) = PLi;jPi Nj.
Let be the SNR threshold. Assuming the system interference free, the state of the radio link is binary: if the signal to noise ratio of a link is above the threshold, the link is on, otherwise, the link is off.
Propagation models The path-loss may depend on the transceiver property, the distance between the nodes, and other environmental aspects [PSG13]. It defines the way a signal sent by a node is attenuated when received by another node. Analytic models that are commonly used in wireless network simulators include the Freespace model. In a complex environment, other effects such as shadowing and fading appears.
To efficiently take these effects into account, there exist several models that add a random variable to a path-loss model to account for additional fading and shadowing in the wireless channel. For instance, the Log-Normal Shadowing model and the Rayleigh Fading model are commonly used. The shadowing corresponds to slow variations of the signal due to obstacles. With multiple obstacles, the signal may be split in different paths and different copies of the signal create a fading effect, corresponding to fast variations in the signal amplitude.
Radio Link Modeling
To model the radio link, one can replace the fixed SNR threshold by a random variable representing the Packet-Error-Rate (PER). The PER is a function of the Bit-Error-Rate (BER), which is derived from the radio properties and the modulation. Given a modulation, there exist different techniques to compute the BER [WG03].
Minimum Data Aggregation Time Problem in a WSN
Here, we suppose that the network is composed of sensor nodes that communicate through wireless transmission, and that the collisions due to interference are not handled by a MAC layer. We suppose that the topology of the network can evolve over the time. Since the problem is defined with discrete time instants, we choose to model the network as an evolving graph (see definition 3.2).
Due to the wireless nature of the communication, transmissions are subject to collisions. The simplest model of interference, as defined in chapter 2, constraints the communication with the following rules. Sensor nodes can send or receive data, but cannot do both at the same time. Moreover, if two nodes send their data simultaneously, all their common neighbors do not receive anything, due to interference (see Figure 4.1a) i.e., a node must have a unique transmitting neighbor in order to receive data from it. So, a solution of the MDAT problem in a WSN is a collisionfree schedule, telling when each node has to transmit, so that all the data of the network is aggregated at the sink node with minimum duration. This problem is studied in chapter 5.
One can observe that the term “collision-free” does not mean that no collision occurs, but that the data that have been aggregated are received without collision. Indeed, it is possible that two nodes u and v transmit simultaneously their data to nodes u0 and v0 (e.g. in Figure 4.1b, u is the only neighbor of u0 and v is the only neighbor of v0) and still a collision occurs at a node w (e.g. u and v are neighbors of w).
Distributed Online Data Aggregation in an Arbitrary Dynamic Network
Here, we consider the MDAT problem in an arbitrary dynamic network, such as sensors deployed on a human body, cars evolving in a city that communicate with each other in an ad hoc manner, etc. We focus our study on the distributed aspect of the problem. To do so, we consider that nodes execute the same algorithm and have to make a decision in an online manner i.e., each node processes its input in the order that the input is fed to the algorithm, without having the entire input
available from the start.
The essence of such a data aggregation algorithm is to decide whether or not to send a node’s data when encountering a given communication neighbor. Also, a node may base its decision on its past experience (past interactions with other nodes) and initial knowledge only. Then, an algorithm accommodating those constraints is called a Distributed Online Data Aggregation (DODA) algorithm. The existence of such an algorithm is conditioned by the (dynamic) topology, initial knowledge of the nodes (e.g. about their future communication neighbors, or some partial information about the evolving graph), etc.
For the sake of simplicity, we assume that interactions between the nodes are carried out through pairwise operations (so that no collision occurs). Anytime two nodes a and b are communication neighbors (or, for short, are interacting), either no data transfer happens, or one of them sends its data to the other. The receiver executes the aggregation function on both its previously stored data and the received data and the output replaces its stored data. In the sequel, we use the term interaction to refer to a pairwise interaction.
We assume that an adversary controls the dynamics of the network, that is to say, the adversary decides what are the interactions. As we consider atomic interactions, the adversary decides what sequence of interactions is to occur in a given execution. Then, the sequence of static graphs to form the evolving graph can be seen as a sequence of single edge graphs, where the edge denotes the interaction that is chosen by the scheduler at this particular moment. Therefore, the time when an interaction occurs is exactly its index in the sequence.
Table of contents :
1 Introduction
1.1 Context of the Thesis
1.2 Thesis Organization
I Context
2 Wireless Sensor Networks
2.1 Applications
2.2 Sensor Components
2.2.1 Hardware
2.2.2 Software
2.3 Challenges
3 Model
3.1 Physical Layer Modeling
3.1.1 Radio Range Modeling
3.1.2 Radio Link Modeling
3.1.3 Interference Modeling
3.2 WSN as a Unit-Disk Graph
3.3 Dynamic Networks
3.3.1 Time-Varying Graphs
3.3.2 Evolving Graphs
3.3.3 Definitions and Preliminaries
3.3.4 Hierarchy of Dynamic Graphs
3.4 Random Graphs
II Data Aggregation Problem
4 Introduction of Part II
4.1 Problem
4.1.1 Minimum Data Aggregation Time Problem in a WSN
4.1.2 Distributed Online Data Aggregation in an Arbitrary Dynamic Network
4.2 Related Work
4.2.1 Data Dissemination Problem
4.2.2 Data Aggregation Problem
4.3 Contribution of Part II
4.3.1 The Complexity of Data Aggregation in WSNs
4.3.2 Distributed Online Data Aggregation
5 The Complexity of Data Aggregation in Wireless Sensor Networks
5.1 NP-Completeness
5.1.1 Static grid graphs of degree at most three
5.1.2 Dynamic graphs of degree at most two
5.2 Upper and Lower Bounds
5.3 Impossibility Results
5.4 Approximation Algorithm
5.5 Conclusion
6 Distributed Online Data Aggregation
6.1 Oblivious and Online Adaptive Adversaries
6.1.1 Impossibility Results When Nodes Have no Knowledge
6.1.2 When Nodes Know The Underlying Graph
6.1.3 If Nodes Know Their Own Future
6.2 Randomized Adversary
6.2.1 Lower Bounds
6.2.2 Algorithm Performance Without Knowledge
6.2.3 Algorithm Performance With meetTime
6.3 Concluding Remarks
III Lifetime Estimation of a Wireless Sensor Network
7 Introduction of Part III
7.1 Problem
7.2 Related Work
7.2.1 Simulating a WSN
7.2.1.1 Generic Network Simulators
7.2.1.2 Emulators
7.2.1.3 Wireless Sensor Oriented Simulators
7.2.1.4 Simulating Energy Consumption in WSNs
7.2.2 Benchmarking Energy-Centric Broadcast Protocols
7.3 Contribution of Part III
8 WiSeBat: Accurate Energy Benchmarking of Wireless Sensor Networks
8.1 The WiSeBat Energy Model
8.1.1 Battery Modeling
8.1.1.1 Linear Battery Modeling
8.1.1.2 The Rate Capacity Effect
8.1.1.3 Voltage Variation
8.1.1.4 WiSeBat Model
8.1.1.5 Updates Triggering
8.1.2 WiSeBat Usage
8.1.2.1 WiSeBat Options
8.1.2.2 WiSeBat Consumption and Control Functions .
8.2 Evaluation
8.2.1 Comparison with Real life measurements
8.2.2 WiSeBat simulation overhead
8.3 Simulations
8.3.1 Single Node Scenario
8.3.2 Two-Node Scenario
8.4 Conclusion
9 Energy Benchmarking of Broadcast Protocols
9.1 Simulation Setup
9.2 Simulation Results and Discussion
9.2.1 Single Source Broadcast
9.2.2 Multiple Source Broadcast (Gossip)
9.2.3 Discussion
9.3 Conclusion
10 Conclusion
10.1 Overview of Thesis Contributions
10.1.1 Data Aggregation
10.1.2 Lifetime Estimation of a Wireless Sensor Network
10.2 Perspectives
A Version française
A.1 Contexte de la thèse
A.2 Modèle
A.2.1 Modélisation de la Couche Physique
A.2.2 Le Réseau Comme un Graphe de Disque-Unité
A.2.3 Modèle pour les Réseaux Dynamiques
A.3 Le Problème de l’Agrégation des Données
A.3.1 Dans les Réseaux de Capteurs Sans Fil
A.3.1.1 Complexité de l’Agrégation de Données en Temps Minimum
A.3.1.2 Borne Inférieure et Borne Supérieure
A.3.1.3 Conclusion
A.3.2 Agrégation en Ligne Dans un Réseau Dynamique Arbitraire .
A.3.2.1 Face à un Adversaire Sans Mémoire
A.3.2.2 Face à un Adversaire Probabiliste
A.3.2.3 Conclusion
A.4 L’Estimation de la Durée de Vie des Batteries
A.4.1 WiSeBat: Modèle pour une Évaluation Réaliste de la Durée de Vie des Batteries
A.4.1.1 Le Module WiSeBat
A.4.1.2 Validation Expérimentale
A.4.1.3 Conclusion
A.4.2 Analyse Comparative des Protocoles de Broadcasts Efficaces en Énergie
A.4.2.1 Configuration des Simulations
A.4.2.2 Résultats et Discussion
A.4.2.3 Conclusion
A.5 PerspectivesIndex
Acronyms and Abbreviations
List of Symbols
Bibliography
