Information Dissemination in Random Networks

Sérgio Armindo Lopes Crisóstomo Information Dissemination in Random Networks Departamento de Ciência de Computadores Faculdade de Ciências, Universidade do Porto and Fakultät für Technische Wissenschaften Alpen-Adria-Universität Klagenfurt September 2012 Sérgio Armindo Lopes Crisóstomo Information Dissemination in Random Networks Tese submetida à Faculdade de Ciências da Universidade do Porto para obtenção do grau de Doutor em Ciência de Computadores Orientadores: Professor Doutor João Barros, Universidade do Porto, e Univ.-Prof. Dr.-Ing. Christian Bettstetter, Alpen-Adria-Universität Klagenfurt Departamento de Ciência de Computadores Faculdade de Ciências da Universidade do Porto 2012 Sérgio Armindo Lopes Crisóstomo Information Dissemination in Random Networks DISSERTATION zur Erlangung des akademischen Grades Doktor der Technischen Wissenschaften Alpen-Adria-Universität Klagenfurt Fakultät für Technische Wissenschaften 1. Begutachter: Professor Doutor João Barros Institut: Faculdade de Engenharia Universidade do Porto 2. Begutachter: Univ.-Prof. Dr.-Ing. Christian Bettstetter Institut: Institut für Vernetzte und Eingebettete Systeme Alpen-Adria-Universität Klagenfurt April 2012 Word of honour I hereby confirm on my honour that I personally prepared the present academic work and carried out myself the activities directly involved with it. I also confirm that I have used no resources other than those declared. All formulations and concepts adopted literally or in their essential content from printed, unprinted or Internet sources have been cited according to the rules for academic work and identified by means of footnotes or other precise indications of source. The support provided during the work, including significant assistance from my supervisors has been indicated in full. The academic work has not been submitted to any other examination authority. The work is submitted in printed and electronic form. I confirm that the content of the digital version is completely identical to that of the printed version. I am aware that a false declaration will have legal consequences. Signature: Porto, Portugal, 25th of April 2012 vii To Lurdes, Armindo, and Paula. Zusammenfassung Die vorliegende Dissertation beschäftigt sich mit der Dissemination von Information in einem Kommunikationsnetzwerk mit Broadcast-Kanal. Die zentrale Frage, welcher wir uns in dieser Arbeit widmen, ist wie man eine Nachricht ausgehend von einem Quellknoten effizient an alle anderen Knoten im Netzwerk verteilt. Hierbei verfolgen wir zwei Hauptziele: (1) Die Nachricht soll mit hoher Wahrscheinlichkeit alle Knoten im Netzwerk erreichen; (2) Es sollen so wenige Übertragungen wie möglich stattfinden. In diesem Zusammenhang wenden wir uns hauptsächlich Algorithmen zur probabilistischen Dissemination von Information zu. Wir modellieren Kommunikationsnetzwerke als Zufallsgraphen, die auf stochastischen Prozessen beruhen. Wir verwenden Methoden der Graphentheorie sowie der stochastischen Geometrie um Disseminationsalgorithmen basierend sowohl auf Nachrichtenweiterleitung als auch auf Network Coding zu analysieren. Unser erstes Resultat ist eine analytische Studie von probabilistischem Flooding. In dieser Studie zeigen wir, wie die netzwerkweite Weiterleitungswahrscheinlichkeit gewählt werden soll, sodass eine Nachricht mit hoher Wahrscheinlichkeit alle Knoten im Netzwerk erreicht. Als nächstes widmen wir uns der Frage, welche Vorteile ein probabilistischer FloodingAlgorithmus basierend auf Network Coding gegenüber klassischen Methoden hat. Dabei wird die Network-Coding Methode mit dem weit verbreiteten MultiPoint Relay-Algorithmus verglichen. Der Vergleich erfolgt mittels analytischer und numerischer Methoden. Schlussendlich verwenden wir die Erkenntnisse der oben beschriebenen Studien dazu, um ein vernetztes Sensor-Aktuator-System zu entwerfen, welches als Notfallschutzsystem innerhalb von Gebäuden zum Einsatz kommen soll. Es soll Personen den kürzesten sicheren Pfad zu den Notausgängen anzeigen. Das Auffinden dieser Pfade erfolgt dabei verteilt basierend auf den Messungen der einzelnen Knoten, die über das gesamte Netzwerk disseminiert werden. xvii “Across the Dark Continent sound the never-silent drums: the base of all the music, the focus of every dance; the talking drums, the wireless of the unmapped jungle.” Irma Wassall Contents 1 Introduction 3 1.1 Information Dissemination in Communication Networks . . . . . . . . . . . . 4 1.2 Main Contributions ................................. 5 1.3 Thesis Outline ................................... 6 2 Models and Tools 9 2.1 Definitions from Graph Theory .......................... 9 2.2 Stochastic Geometry and Point Processes . . . . . . . . . . . . . . . . . . . . 10 2.3 FKG Inequality ................................... 11 2.4 Poisson Approximation by the Chen-Stein Method . . . . . . . . . . . . . . . 12 2.5 Wireless Link Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5.1 Free-Space Path Loss Model . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.2 Simplified Path Loss Model . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.3 Combined Path Loss and Shadowing Model . . . . . . . . . . . . . . . 14 2.6 Network Models ................................... 15 2.6.1 Erdős Rényi Random Graphs . . . . . . . . . . . . . . . . . . . . . . . 15 2.6.2 Random Geometric Graphs . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6.3 Small-world Networks ........................... 17 xxi xxii Contents 3 Probabilistic Flooding in Stochastic Networks 21 3.1 Probabilistic Flooding and Problem Statement . . . . . . . . . . . . . . . . . 23 3.1.1 Probabilistic Flooding ........................... 23 3.1.2 Problem Statement ............................. 23 3.2 Graph Sampling Approach ............................. 24 3.3 Probabilistic Flooding in Erdős Rényi Graphs . . . . . . . . . . . . . . . . . . 25 3.3.1 Derivation of the Outreach Probability . . . . . . . . . . . . . . . . . . 25 3.3.2 Parameters for Global Outreach . . . . . . . . . . . . . . . . . . . . . . 27 3.4 Probabilistic Flooding in Poisson Random Geometric Graphs without Border Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4.1 Derivation of the Outreach Probability . . . . . . . . . . . . . . . . . . 30 3.4.1.1 Graph Sampling and Poisson Processes . . . . . . . . . . . . 31 3.4.1.2 Node Isolation in G∗. . . . . . . . . . . . . . . . . . . . . . . 31 3.4.1.3 Connectivity of G∗. . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.1.4 Domination of G. . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.1.5 Dependence between Node Isolation & Domination . . . . . . 36 3.4.1.6 Dependence between Connectivity and Domination . . . . . . 37 3.4.1.7 Proof of Theorem 3 (Global Outreach in Random Geometric Graphs (RGGs)) . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4.2 Simulation of Outreach Probability in RGGs . . . . . . . . . . . . . . 39 3.4.3 Parameters for Global Outreach . . . . . . . . . . . . . . . . . . . . . . 42 3.5 Probabilistic Flooding in Poisson Random Geometric Graphs with Border Effects 42 3.6 Probabilistic Flooding with Unreliable Links . . . . . . . . . . . . . . . . . . . 44 3.7 Discussion and Related Work ........................... 48 3.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4 Network Coded Information Dissemination 53 Contents xxiii 4.1 Flooding Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1.1 Multipoint Relaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1.2 Random Linear Network Coding based Flooding . . . . . . . . . . . . 56 4.2 Asymptotic Analysis of Network Coded Flooding . . . . . . . . . . . . . . . . 57 4.2.1 Problem Statement ............................. 57 4.2.2 General Bounds ............................... 57 4.2.3 Bounds for Erdős Rényi Random Graphs . . . . . . . . . . . . . . . . 59 4.2.4 Bounds for Binomial Random Geometric Graphs . . . . . . . . . . . . 61 4.2.5 Bounds for Small-World Networks . . . . . . . . . . . . . . . . . . . . 61 4.3 Simulation based Analysis ............................. 64 4.3.1 Description of the Simulator and Simulation Setup . . . . . . . . . . . 64 4.3.2 Topology and Performance Metrics . . . . . . . . . . . . . . . . . . . . 65 4.3.3 Analysis of Erdős Rényi Random Graphs . . . . . . . . . . . . . . . . 65 4.3.4 Analysis of Binomial Random Geometric Graphs . . . . . . . . . . . . 66 4.3.5 Analysis of Small-World Networks . . . . . . . . . . . . . . . . . . . . 69 4.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5 Applications in Dynamic Sensor Networks 79 5.1 Modeling Assumptions ............................... 80 5.1.1 Building Topology ............................. 80 5.1.2 Emergency Navigation Graph . . . . . . . . . . . . . . . . . . . . . . . 81 5.1.3 Wireless Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.1.4 Spatial and Radio Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 Emergency Navigation Graph Computation . . . . . . . . . . . . . . . . . . . 84 5.2.1 Problem Statement ............................. 84 5.2.2 Security Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.2.2.1 Discrete Hazard Metric (DHM) . . . . . . . . . . . . . . . . . 85 xxiv Contents 5.2.2.2 Continuous Hazard Metric (CHM) . . . . . . . . . . . . . . . 87 5.2.3 Safest Exit Paths from Nodes . . . . . . . . . . . . . . . . . . . . . . . 88 5.2.4 Safest Exit Paths from Edges . . . . . . . . . . . . . . . . . . . . . . . 91 5.3 System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.3.1 Sensing and Navigation Plane . . . . . . . . . . . . . . . . . . . . . . . 92 5.3.2 Radio Communication Plane . . . . . . . . . . . . . . . . . . . . . . . 94 5.3.3 System Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.3.4 Evaluation of the Sensor Data Dissemination . . . . . . . . . . . . . . 96 5.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6 Main Contributions and Future Work 101 A Proofs for Chapter 3 107 A.1 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 A.2 Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.3 Proof of Lemma 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 B Symbols, Mathematical Notation, and Abbreviations 113 B.1 List of Symbols and Mathematical Notation . . . . . . . . . . . . . . . . . . . 113 B.2 Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Bibliography 117 List of Figures 2.1 Erdős Rényi Random Graph with 14 nodes and edge probability p= 0.2.. . . 15 2.2 Random Geometric Graph in a square of area A, with 25 nodes and transmission range r...................................... 16 2.3 Small-World model with rewiring with 12 nodes and k= 4 for different values of the rewiring probability p............................ 18 3.1 Global outreach probability Ψfor PF in Erdős Rényi graphs. Parameters: n= 1000 nodes, edge probability p= 0.15 and message forwarding probability ω. Comparison of simulated PF and GS algorithms with analytical expression for Ψ.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Probabilistic flooding in Erdős Rényi graphs. Plots show (p, ω)-pairs for global outreach probability Ψ=0.50,0.80,0.95.. . . . . . . . . . . . . . . . . . . . . 28 3.3 Probabilistic flooding in Erdős Rényi graphs. Plots show (p, n)-pairs for global outreach probability Ψ=0.50,0.80,0.95.. . . . . . . . . . . . . . . . . . . . 29 3.4 Probability of connectivity/no isolated node; relative frequency of the experiments of AGS yielding connected graphs; and relative frequency of experiments of AGS yielding graphs with no isolated node in RGGs. . . . . . . . . . . . . . 34 3.5 Probability of domination (assuming εD= 0) in comparison to the relative frequency of the experiments of the algorithm AGS yielding graphs with no non-dominated nodes. ............................... 36 3.6 Dependence between graph domination and connectivity/node isolation (algorithm AGS) in comparison to the analytical results. . . . . . . . . . . . . . . . 38 xxv 1Introduction Information dissemination in communication networks is a key function whose effectiveness depends both on the chosen dissemination algorithm and on the underlying network topology. It is needed, for example, in route discovery, link state advertisements, autoconfiguration, and query propagation in ad hoc networks and peer-to-peer systems. The process of (re-)transmitting a message can occur as a point-to-point or point-tomultipoint transmission. Point-to-point communication means that a node sends a message to only one of its neighbors. The node may then retransmit the same message to distinct neighbors using multiple transmissions. This model is applied, for example, in peer-to-peer networks. Point-to-multipoint communication implies that all neighbors of a transmitting node will receive the transmitted message (assuming no errors). This model is usually used in studies of networks with a broadcast medium such as wireless networks. The main focus of this work is to understand how to disseminate efficiently a message from a source node to all other network nodes using point-to-multipont communications. We target two goals: one is to deliver a source message to all network nodes with high probability; the other one is to use as few transmissions as possible for a given target reachability. We address mainly probabilistic dissemination algorithms. 3 41.1. Information Dissemination in Communication Networks 1.1 – Information Dissemination in Communication Networks Until recently, information dissemination resorted to replication based forwarding where nodes replicate and forward the information they receive. A naïve way of disseminating a message to all nodes in a network with point-to-multipoint transmissions is pure flooding. When a node receives a broadcast message for the first time it will always forward it. In a network with nnodes, the number of transmissions of a source message using pure flooding is n. This technique leads to a high number of redundant and unnecessary transmissions. A natural optimization goal that arises is to minimize the number of transmissions while achieving global outreach of the message sent. Finding an optimum scheme for disseminating a message in a given network with minimum overhead—i.e., finding the minimum connected dominating set—is however NP-complete [vJPHE02]. Two main classes of approximation algorithms were proposed to improve the efficiency of pure flooding. The first class comprises deterministic algorithms approximating connected dominating sets of networks [AWF02,LW02,AQL02]. Reference [AQL02] proposes a deterministic algorithm, which approximates the connected dominating set within a two-hop neighborhood of each node, thus forming a backbone of forwarding nodes and limiting the number of transmissions. The idea of using such a subset of nodes, also called Multipoint relays (MPR), has been implemented successfully in the Optimized Link State Routing (OLSR) protocol [CJA+03] for mobile ad hoc networks. The second class comprises probabilistic algorithms that introduce a stochastic element to the message forwarding process; these class of algorithms are commonly denoted as Probabilistic Flooding (PF) or gossiping [SCS03,HHL06,SB07,BBB+08,SRS07]. 1 The study of reachability in PF with point-to-point communications has received good attention from the research community both by analysis and simulation (see [OKS10,GS11] and references therein). PF with point-to-multipoint communications, however, has mainly been addressed by means of simulations [HHL06,SCS03,KWB01,YOKM+06,YOKP05, SRS07]. Some of these studies yield better insight into the behavior of PF—with inspiration from percolation theory—but most conclusions do not generalize beyond the particular setup [SCS03,HHL06,KWB01]. 1Some authors use both terms to refer to the same concept. Others use them in a way that in PF a node forwards a message to all its neighbors (point-to-multipoint communications), while in gossiping a node forwards a message to only one neighbor (point-to-point communications). Chapter 1. Introduction 5 The seminal paper of Ahlswede, Li, Cai, and Yeung [ACLY00], where they proved that the max-flow min-cut capacity of a general multicast network can only be achieved by allowing intermediate nodes to mix different data flows, landmarked the appearance of the new Network Coding paradigm. Network coding research suggests that further reductions in the number of transmissions required for flooding could be achieved due to the ability of intermediate nodes to mix multiple messages through algebraic operations. More specifically, reference [FWLB06] quantifies these gains for ring and square lattice topologies, and presents a heuristic algorithm which outperforms probabilistic flooding for a class of random geometric graphs. Related work on the benefits of network coding includes a proof that the minimum energy single-source multicast problem with network coding becomes solvable in polynomialtime [LMHK04] and in a distributed manner [LRK+05]. The problem of multiple multicasts, which is closer to flooding, remains however an open problem [LRM+06]. 1.2 – Main Contributions Modeling networks as random graphs built from stochastic processes and using methods from graph theory and stochastic geometry we address both replication and network coded information dissemination paradigms. We perform both analytical and numerical studies of “state-of-the-art” probabilistic dissemination algorithms, comparing their performance with deterministic algorithms — where performance is measured by the number of transmissions needed to disseminate a message and by the reachability of a dissemination process. Moreover, we apply the insights gained from the analysis of the information dissemination algorithms in the design of a sensor-actuator networked system for emergency response in indoor scenarios. The main contributions of this thesis are as follows: •We present a generic approach to estimate the probability of achieving global outreach with PF with a network-wide common forwarding probability. We derive an exact expression for the global outreach probability over Erdős Rényi Random graphs and an asymptotic expression for the global outreach probability in Random Geometric graphs that constitutes a good approximation at high node density. We address both reliable and unreliable links. •We characterize analytically the transmission cost of network coded flooding over 61.3. Thesis Outline Erdős Rényi Random graphs, Random Geometric graphs, and Small-World Networks. Moreover, we present a numerical study for the number of transmissions, delivery ratio, and delay of network coded and MPR flooding. We also analyze the interplay between the network topology with replication and network coded based flooding algorithms. •We propose graph theoretical abstractions of a sensor network for supporting building evacuation in disaster scenarios and algorithms for the computation of shortest safe path to exits. The wireless sensor network collects hazard information that is flooded throughout the network. This information is used as input for the computation of the shortest safe paths for leaving the building. We implement a prototype of the system in which we evaluate the proposed solutions. 1.3 – Thesis Outline The remainder of this thesis is organized as follows. In Chapter 2we introduce the fundamental concepts and mathematical techniques used throughout the dissertation. In Chapter 3 we take a mathematical approach to the analysis of PF. We determine analytically how PF with constant forwarding probability behaves over mathematically tractable abstractions of a network, namely random graph models. In Chapter 4we analyze network coded based flooding techniques and compare them to replication based deterministic flooding. We seek to understand which benefits in terms of number of transmission per message, reachability, and delay may we obtain from performing algebraic mixing of messages in intermediate forwarding nodes during an information dissemination process. In Chapter 5we address the problem of designing a sensor network system for the support of building evacuation in disaster scenarios. We characterize the problem with the help of graph models and we propose algorithms that use flooded hazard information to compute shortest paths to safely leave the building. Finally, Chapter 6concludes this dissertation, including possible directions of future work. Parts of the work presented in this thesis were previously published in [CBB08a,CBB08b, CSBB09,CSBB12]. New unpublished results are also presented. “Facts do not cease to exist because they are ignored.” Aldous Huxley “We don’t live in a world of reality, we live in a world of perceptions.” Gerald J. Simmons 2Models and Tools This chapter provides an overview of the analytical tools and modeling assumptions considered in the work presented in this thesis. 2.1 – Definitions from Graph Theory Let G= (V, E)be a graph with a set of nodes Vand a set of edges E⊆ {{u, v}:u, v ∈ V, u 6=v}. The number of nodes of G, called the order of G, is denoted by n=|V|. A node vis called neighbor of uif there exists an edge {u, v} ∈ E. The degree d(u)of a node uis the number of edges adjacent to u, i.e., the number of neighbors of u. A path in a graph is a sequence of nodes such that from each of its nodes there is an edge to the next node in the sequence. The length of a path is the number of edges traversed by the path. A shortest path between two nodes is a path such that its length is minimum. A graph Gis called connected if there is a path between any two distinct nodes u, v ∈V. The distance Lu,v between a pair of nodes {u, v}in a graph G(also known as the geodesic distance) is the number of edges in a shortest path connecting them. The diameter of a 9 10 2.2. Stochastic Geometry and Point Processes graph Gis the longest geodesic distance in the graph. The average distance Lfor a whole graph Gis the average of the distances between every distinct pair of nodes in G. A node with distance l∈Z+to a node uis called l-hop neighbor of u. The l-hop neighborhood Nl(u) of a node uis the set of l-hop neighbors of u. The 1-hop neighborhood N1(u)(or N(u)) of a node uis also called the neighborhood of u. The clustering coefficient Cufor a node uis the ratio between the number of edges connecting the nodes within its neighborhood and the maximum number of edges that could connect them. The clustering coefficient Cfor a whole graph Gis the average of the clustering coefficients of each node in G. Asubgraph G′= (V′, E′)of Gis a graph with V′⊆Vand E′⊆E. An induced subgraph G′of Gis a subgraph in which for any pair of nodes u, v ∈V′,{u, v}is an edge of E′ whenever {u, v}is an edge of E(i.e., ∀u, v ∈V′:{u, v} ∈ E⇒ {u, v} ∈ E′). A maximal connected subgraph G′= (V′, E′)is an induced connected subgraph of G= (V, E)that no longer satisfies the property of being connected when adding an additional node from V\V′ and the corresponding edges. A maximal connected subgraph of Gis called a connected component of G.V′is a dominating set if all nodes uthat are not within V′have an edge to a node v′∈V′, i.e., ∀u∈V\V′∃v′∈V′:{u, v′} ∈ E. If additionally the induced subgraph G′= (V′, E′)is connected, the node set V′is a connected dominating set. 2.2 – Stochastic Geometry and Point Processes In spatial networks, the location of nodes can be described by deterministic or stochastic models. Deterministic models are often defined by regular structures such as ring or square lattices. When the location of nodes is uncertain, stochastic processes are tipically used to model these networks. Point processes A Point Process (PP) is a type of random process for which any realization consists of a set of isolated points {x1, x2,...,xn}in a plane. Formally, a PP Π, is a measurable mapping from a probability space [Ω,A,P]into [N,N], where Nis the family of all sequences Π = {xi} of points in R2that satisfy the following conditions [SKM85]: (1) the sequence Πis locally finite, i.e., each bounded set of R2must contain only a finite number of points of Π; (2) the sequence Πis simple, meaning that there is no accumulation of points, i.e., xi6=xjif i6=j. Nis the smallest α-algebra on Nthat makes all mappings Π7→ Π(B)measurable, where B Chapter 2. Models and Tools 11 is a bounded Borel set. A PP realization corresponds to a random selection of one of the sequences in N. The number of points of a PP in a bounded region R ⊂ R2is a random variable that can analyzed probabilistically. The points of a PP can be used to model the locations of the nodes in a spatial network. Poisson Point Process A homogeneous Poisson Point Process (PPP) models a uniformly at random deployment of points in a plane, in which no preference is given to specific regions of the plane. The homogeneous PPP is characterized by an intensity parameter λ. The expected number of points in a region Rfollows a Poisson distribution with parameter λ·A(R), where A(R) is the area of R. Therefore, the probability of npoints being inside a region Ris given by [Kin93]: P(npoints in R) = (λ·A(R))n n!e−λ·A(R).(2.1) Moreover, the number of points in disjoint regions are independent Poisson distributed random variables. A realization of a PPP with intensity λin a given region Rcan be obtained by drawing a random number Nfrom the Poisson distribution Po(A(R)·λ), followed by scattering N points uniformly at random in R. 2.3 – FKG Inequality The FKG inequality [FKG71] expresses positive correlations between increasing events (see Ch. 2.2, [Gri99]). Consider two realizations P1and P2of a Poisson point process. We define a partial ordering P1 P2if and only if every point of P1is also present in P2. An event Ais an increasing event if for every P1 P2, the indicator function IAof the event A respects the relation IA(P1)≤IA(P2). If Aand Bare increasing events in a Poisson point process, then P(A∩B)≥P(A)P(B). 18 2.6. Network Models p=0 p=0.1 p=0.9 Figure 2.3: Small-World model with rewiring with 12 nodes and k= 4 for different values of the rewiring probability p. munication processes in complex networks (including SWNs), such as search and navigation, network transmission, epidemics, and information dissemination processes. In the original model of Watts and Strogatz (SWN with Rewiring [WS98]), shortcuts are introduced by rewiring the edges of the original ring lattice with a certain probability p. A typical variant was introduced by Newman and Watts (SWN with added Shortcuts [NW99]) where instead of reconnecting existing edges, new edges are added with probability p. Kleinberg [Kle00] introduced an SWN model that has the property of navigability, where short paths not only exist, but can also be easily found using merely local information. The model consists of a grid to which shortcuts are added not uniformly but according to a harmonic distribution, such that the number of outgoing links per node is fixed and the link probability depends on the distance between the nodes. For this class of SWNs a greedy routing algorithm, in which a message is sent through the outgoing link that minimizes the distance to the destination, was shown to be effective. Small-World Network with Rewiring ASmall-World Network with Rewiring G= (V, k, p)with set of nodes V, initial node degree k, and rewiring probability pis constructed as follows (see Fig. 2.3): the initial graph is a one-dimensional lattice of nnodes, with periodic boundary conditions (i.e., a ring), where each node is connected to its k-hop neighborhood. The nodes are then visited one after the other; each edge connecting a node to one of its k/2nearest neighbors in the clockwise sense is left in place with probability 1−p, and with probability pis reconnected to a randomly chosen other node. From now on we will use the acronym SWN to specifically refer to Small-World Networks with Rewiring. “Do not speak — unless it improves on silence.” Buddhist Sayings “God does not play dice.” Albert Einstein 3 Probabilistic Flooding in Stochastic Networks In Probabilistic Flooding (PF) with error-free point-to-multipoint communications, the transmission of a node is received by all its neighbors. The source node transmits a so called source message. Each of its neighbors then forwards the received message with some probability that may be common to all nodes, different for each node, or even adaptive. In contrast to deterministic algorithms, PF algorithms do not guarantee that all nodes of a connected network will receive a flooded message even under ideal conditions (collision-free MAC and error-free propagation medium). The set of forwarding nodes of the communication subgraph generated by the PF process of a message needs to be a connected dominating set of the network in order to achieve global outreach. This in turn is only assured if the forwarding probability of all nodes equals one (pure flooding). Besides this special case, global information outreach can only be achieved with a probability smaller than one. The study of reachability in PF with point-to-multipoint communications, however, has mainly been addressed by means of simulations. In this chapter, we take a mathematical approach to the analysis of PF. Our aim is to determine analytically how simple PF with constant forwarding probability behaves over mathematically tractable abstractions of a network, namely random graph models. We consider Erdős Rényi Random Graphs (ERGs) 21 22 and Poisson Random Geometric Graphs (P-RGGs) (or simply Random Geometric Graphs (RGGs) within this chapter; see Section 2.6). The results may be used as a reference for the study and development of more sophisticated algorithms.1In the following we refer to PF with point-to-multipoint communication only by PF, as our work addresses exclusively the reachability using this model. Consider a PF algorithm in which each node forwards a received message with a networkwide forwarding probability ω. We ask: How small can ωbe while still achieving global outreach with high probability? We answer this question using methods from graph theory and stochastic geometry, and make the following main contributions: •Presentation of a generic approach to estimate the probability of achieving global outreach; •Derivation of an expression for the global outreach probability in ERGs; •Derivation of an asymptotic expression for the global outreach probability in RGGs that constitutes a good approximation for dense RGGs; •Detailed analysis of the network-wide forwarding probability ωrequired to achieve global outreach with high probability in ERGs and RGGs; •Analysis of the global outreach probability of PF with unreliable transmission medium for ERGs and RGGs; •Study of the border effects in RGGs and proposal of a PF heuristic that minimizes these effects. The chapter is organized as follows. Section 3.1 describes the PF algorithm and gives the problem statement. Section 3.2 presents an analytical approach to compute the probability of global outreach. Section 3.3 employs this approach in ERGs, leading to an expression for the global outreach probability in such networks. In addition, we show (n, p, ω)-tuples leading to global outreach with high probability. Section 3.4 addresses RGGs, leading to an asymptotic expression for the global outreach probability. We also perform a numerical study, comparing analytical and simulation results evaluating the accuracy of the derived expressions. Again, we show (λ, A, r, ω)-tuples leading to global outreach with high probability. Section 3.5 studies border effects of RGGs on the global outreach probability and proposes a modification to the PF algorithm to address these effects. Section 3.6 presents analysis of global outreach probability in the presence of unreliable transmission medium. Section 3.7 discusses the achieved results in comparison to related work. Finally, Section 3.8 summarizes the main results of the chapter. 1E.g., PF with the forwarding probability given by some probability distribution; as function of local topology parameters; or as function of the dynamics of the dissemination process. Chapter 3. Probabilistic Flooding in Stochastic Networks 23 The main results of this chapter were published in [CSBB09,CSBB12] in collaboration with Christian Bettstetter, João Barros, and Udo Schilcher. Sections 3.1-3.8, excepting minor changes, are taken from [CSBB12], which were written with the corresponding co-authors. 3.1 – Probabilistic Flooding and Problem Statement 3.1.1 Probabilistic Flooding A naïve way of disseminating a message to all nodes in a network is pure flooding. When receiving a broadcast message for the first time a node will always forward it. In a network with nnodes, the number of transmissions of a source message using pure flooding is n. This technique leads to a high number of redundant transmissions, which is commonly known as the broadcast storm problem [NTCS99]. Probabilistic flooding is a family of techniques that aim to reduce the number of redundant transmissions, in which the message forwarding is a probabilistic event [SCS03,HHL06, KWB01]. In general, each node vmay have a distinct forwarding probability ω(v). We focus on the simple case where all nodes have the same forwarding probability. Only the source node utransmits the message always with probability 1. I.e., ω(v) = ω∀v∈V\u. The case ω= 1 is equivalent to pure flooding. Algorithm 1describes the flooding process. We assume an error-free broadcast medium, i.e., a transmission from a node will be successfully received by all its neighbors. In this case, for an appropriate choice of ωleading to global information outreach, the expected number of transmissions is reduced from nto (n−1) ω+ 1. 3.1.2 Problem Statement Let G= (V, E)represent a network. A source node u∈Vintends to deliver a message muto all other nodes v∈V. The message muis disseminated through Gusing the flooding algorithm AP F (G, u, ω). Algorithm 1 Probabilistic flooding APF(G, u, ω) Let G= (V, E)be a graph, u∈Vbe a source node with a source message muto be disseminated, and ω∈[0,1] be a forwarding probability common to all nodes v∈V\{u}. 1. A source node ubroadcasts its source message mu. 2. Each node vthat receives mufor the first time re-broadcasts it with probability ω. 24 3.2. Graph Sampling Approach We are interested in the forwarding probability ωneeded such that all nodes receive mu with a given probability α. In a more formal way, let V′⊆Vdenote the set of nodes that have received the message muafter the completion of AP F (G, u, ω). Our goal is to determine min{ω:P(V′=V)≥α}. The term P(V=V′)is the probability that all nodes of the network obtain the message. In the following, it is called global outreach probability Ψ,P(V′=V). 3.2 – Graph Sampling Approach We present a generic approach to calculate the global outreach probability. First, using probabilistic flooding, we can construct a communication subgraph G′= (V′, E′)of the network graph Gin the following way: We start with a node set V′={u}containing only the source node and an empty edge set E′={}. For each node vthat forwards the message, we add all receiving nodes to V′. Additionally, we add edges {v, w}between the forwarding node and the receiving nodes w∈N(v)to E′. Second, we construct an induced subgraph of G, called G∗= (V∗, E∗), using Graph sampling (GS) explained in Algorithm 2.G∗helps us to analyze the probability of global outreach for given ω. We show how properties of a random graph G∗are related to those of a random graph G′. We study two properties: •the event that G∗is connected, denoted as C(G∗); •the event that the nodes V∗are a dominating set of G, denoted as D(V∗, G). The event C(G∗)∩D(V∗, G)means that V∗is a connected dominating set of G. Theorem 1 (Global outreach).The probability of global outreach using probabilistic flooding AP F (G, u, ω)on a network G= (V, E)is equal to the probability that the node set V∗⊆V resulting from graph sampling AGS(G, u, ω)is a connected dominating set of G: Ψ(G, ω) = PC(G∗)∩D(V∗, G).(3.1) Algorithm 2 Graph sampling AGS(G, u, ω) Let G= (V, E)be a graph that represents the network and u∈Va source node. 1. The node set V∗is obtained by uniformly sampling the node set V\{u}with probability ωand adding u. 2. The edge set E∗contains all edges of Gthat connect nodes within V∗, i.e., E∗={{u, v} ∈ E: u, v ∈V∗}. Chapter 3. Probabilistic Flooding in Stochastic Networks 25 Proof. A node can decide beforehand whether or not it will participate in the forwarding process if it receives a message. This is equivalent to the sampling process of algorithm AGS. Hence, the set V∗can be associated with the set of nodes forwarding a message according to algorithm AP F if and only if G∗is connected. If the set V∗is also a dominating set of G, all nodes in V\V∗are neighbors of at least one node in V∗and thus receive a message. 3.3 – Probabilistic Flooding in Erdős Rényi Graphs This section analyzes the probability of global outreach on an ERG Gwith nnodes and edge probability p. We derive the expression for the probability of global outreach and present (n, p, ω)-triples leading to a global outreach probability of 0.50,0.80 and 0.95, respectively. 3.3.1 Derivation of the Outreach Probability If Gbelongs to the class of ERGs, the probability of global outreach is given by the following theorem. Theorem 2 (Global outreach in ERGs).The probability of global outreach using probabilistic flooding AP F with forwarding probability ωin an ERG with nnodes and edge probability pis Ψ(n, p, ω) = n X k=1 PC(k, p)·1−(1−p)kn−k ·n−1 k−1ωk−1(1 −ω)n−kwith (3.2) PC(m, p) = 1 − m−1 X j=1 m−1 j−1PC(j, p) (1 −p)j(m−j)(3.3) for m≥1with starting value PC(1, p) = 1. Fig. 3.1 plots Ψover ωalong with results from simulations of PF and GS. There is a critical interval of ω-values where Ψincreases from nearly zero to nearly one. Proof. To prove Theorem 2, we show that connectivity of G∗and domination of Gby V∗ given G∗, are mutually independent. Then, we characterize the connectivity and order of G∗, and the probability of domination of Gby V∗. Based on this, we derive the global outreach probability. 26 3.3. Probabilistic Flooding in Erd˝os Rényi Graphs 0 0.2 0.4 0.6 0.8 1 0.02 0.04 0.06 0.08 0.1 probability or rel. frequency ω Ψ (analytical) ΨPF (simulation) ΨGS (simulation) 0 0.2 0.4 0.6 0.8 1 0.02 0.04 0.06 0.08 0.1 probability or rel. frequency ω Ψ (analytical) ΨPF (simulation) ΨGS (simulation) Figure 3.1: Global outreach probability Ψfor PF in ERGs. Parameters: n= 1000 nodes, edge probability p= 0.15 and message forwarding probability ω. Comparison of simulated PF and GS algorithms with analytical expression for Ψ. Simulation results are obtained from 1 000 experiments. Each experiment is run over a new ERG. Each data point (with its 95% confidence interval limits) represents the relative frequency of the events “achieving global outreach (PF)” or “achieving a connected dominating set (GS)”. Connectivity and domination are independent The probability that V∗of G∗is a connected dominating set of Gis PC(G∗)∩D(V∗, G)=PC(G∗)·PD(V∗, G).(3.4) The event C(G∗)is equivalent to the existence of a path connecting any pair of nodes of G∗. Since a path in G∗is a sequence of consecutive edges of G∗, the sample space of C(G∗) is the set of edges {{u, v}:u, v ∈V∗, u 6=v}. The event D(V∗, G)denotes the existence of edges connecting any node in V\V∗to the node set V∗. Thus, its sample space is the edge set {{u, v}:u∈V∗, v ∈V\V∗}. In conclusion, since the existence of an edge in an ERG is independent of the existence of any other edge and since the sample spaces of C(G∗)and D(V∗, G)are disjoint edge sets, the events C(G∗)and D(V∗, G)are independent. Connectivity of G∗Gilbert [Gil59] derived the recurrence relation (3.3) for the probability that an ERG G(V, p)with m=|V|nodes and edge probability pis connected. Therefore, the probability of G∗being connected is P(C(G∗)|N∗) = PC(N∗, p).(3.5) Chapter 3. Probabilistic Flooding in Stochastic Networks 27 Order of G∗Since V∗\{u}is a uniformly sampled subset of V\{u}, the number of nodes N∗is a random variable. N∗−1is binomially distributed according to Bin(n−1, ω). The “−1” stems from the source node sending with probability 1. Thus, the probability mass function of N∗is P(N∗=k) = (0if k= 0, n−1 k−1ωk−1(1 −ω)n−kotherwise.(3.6) Domination of GThe probability that V∗is a dominating set of Gis P(D(V∗, G)|N∗) = 1−(1 −p)N∗n−N∗ .(3.7) For a given node u∈V\V∗the probability of having no edge to any of the nodes in V∗is (1 −p)N∗. Hence, the probability of an edge to at least one of them is 1−(1 −p)N∗. Since this probability is independent for each node u∈V\V∗, (3.7) gives the result. Proof of Th. 2Summing the conditional probabilities for connectivity and domination over all possible kof N∗, each of them multiplied with the probability P(N∗=k), gives Ψ= n X k=1 P(C(G∗)|N∗)·P(D(V∗, G)|N∗)·P(N∗=k).(3.8) Substituting (3.5), (3.6), (3.7) into (3.8) yields (3.2). 3.3.2 Parameters for Global Outreach Let us illustrate how these results can be used for network design. The goal is to meet a target value for Ψby creating or deploying networks and simultaneously tuning ωof the flooding algorithm. In practical applications, one is interested in high outreach probabilities—here we give design options for Ψ=0.50,0.80 and 0.95. If nis given, the parameters pand ωcan be chosen. Fig. 3.2 plots the (p,ω)-pairs required for achieving a high outreach probability Ψwith n= 100 and 1000, respectively. The curves show a trade-off in the choice of the (p,ω)-pairs. A sparse ERG (low p) requires higher ω-values. For well-connected ERGs (high p), small values of ωare sufficient to guarantee the desired Ψ. The plots also stress the non-linear dependence between these parameters. If the ωis given, the parameters pand ncan be determined. For ω= 0.08 and 0.5, Fig. 3.3 shows (p,n)-pairs ensuring Ψ=0.50,0.80 and 0.95. The dependency between nand pfor the same Ψis non-linear, as expected from Theorem 2. For increasing p, with pclose to 0, the required number of nodes experiences an expressive reduction. This trend is then smoothed, and this reduction becomes almost negligible as papproaches 1. 34 3.4. Probabilistic Flooding in Poisson Random Geometric Graphs without Border Effects Figure 3.4: Probability of connectivity/no isolated node (εC=εI= 0); relative frequency of the experiments of AGS yielding connected graphs; and relative frequency of experiments of AGS yielding graphs with no isolated node. Simulation results are obtained from 10 000 experiments. Each experiment is run over a new RGG. A proof can be found in A.2. Proposition 3 (Domination of G).Let α⋄,λ∗π r2−ln Aλ⋄.The probability that V∗is a dominating set of Gis P(D(V∗, G)) = e−e−α⋄ +εD,(3.25) where εD≥0and limλ→∞ εD= 0. Proof. The nodes of G∗are distributed in SAaccording to Π∗ swith density λ∗=λ ω +1 A. The set V∗dominates Gif for every node v⋄∈V⋄there is at least one edge {v⋄, w∗}such that w∗∈V∗. In this case, we say that v⋄is dominated by V∗. Hence, the probability that a node v⋄∈V⋄is dominated by V∗is equal to the probability that there is at least one node from Π∗ swithin the circle of radius rcentered at the position of node v⋄. That is P(dom(v⋄)) = 1 −e−λ∗π r2.(3.26) Let the random variable N⋄be the number of nodes of V⋄. Then, the probability that Gis dominated by V∗is P(D(V∗, G)|N⋄) = P N⋄ \ i=1 dom(v⋄ i)!.(3.27) The domination events for nodes of V⋄close to each other, i.e., within distance d(v⋄ i, v⋄ j)≤ 2rfrom each other, are dependent. They are increasing events with respect to ωand λ. Chapter 3. Probabilistic Flooding in Stochastic Networks 35 Application of the FKG inequality to (3.27) leads to P(D(V∗, G)|N⋄)≥ N⋄ Y i=1 P(dom(v⋄ i)) = h1−e−λ∗π r2iN⋄ , P(D(V∗, G)|N⋄) = 1−e−λ∗π r2N⋄ +ξD,(3.28) with ξD≥0. Applying the law of total probability yields P(D(V∗, G)) = E (P(D(V∗, G)|N⋄)) = E 1−e−λ∗π r2N⋄+ E (ξD) =e−e−(λ∗π r2−ln(A λ⋄))+εD=e−e−α⋄ +εD,(3.29) with εD= E (ξD)≥0, proving (3.25). From Lemma 2, the probability that there is no non-dominated node in Gis upper bounded as follows: P(D(V∗, G)) = P(W⋄= 0) ≤e−e−α⋄ +dTV W⋄,Po e−α⋄.(3.30) Combining (3.29) with (3.30) yields εD≤dTV W⋄,Po e−α⋄.(3.31) Finally, combining (3.31) with (3.24), we get limλ→∞ εD= 0. This shows that the domination probability converges asymptotically to e−e−α⋄, which is also a lower bound. Fig. 3.5 compares the analytical expression/lower bound with simulation results. As ωincreases, the relative frequency of graphs where V∗is a dominating set approaches 1, and the difference between the analytical expression and simulation results becomes negligible. 3.4.1.5 Dependence between Node Isolation & Domination The events ¬I(G∗)and D(V∗, G)depend on each other. Let us analyze this dependency and derive an asymptotic expression for P(¬I(G∗)∩D(V∗, G)) which is also a lower bound for this probability. The event ¬I(G∗)∩D(V∗, G)is equivalent to the event that the sum of all non-dominated nodes and isolated forwarding nodes in Gis 0. The following lemma helps us to derive the joint probability. A proof can be found in A.3. 36 3.4. Probabilistic Flooding in Poisson Random Geometric Graphs without Border Effects Figure 3.5: Probability of domination (assuming εD= 0) in comparison to the relative frequency of the experiments of the algorithm AGS yielding graphs with no non-dominated nodes. Lemma 3. Let α,λ∗π r2−ln (A λ + 1) and W⋄∗ be the sum of all non-dominated nodes and isolated forwarding nodes in G. The total variation distance between the distribution of W⋄∗ and a Poisson distribution Po(e−α)converges to 0when λ→ ∞, i.e., lim λ→∞dTV W⋄∗,Po e−α= 0.(3.32) Proposition 4. The probability that G∗has no isolated node and its nodes V∗dominate G is P(¬I(G∗)∩D(V∗, G)) = P(¬I(G∗))·P(D(V∗, G))+εID,(3.33) where εID ≥0, and lim λ→∞εID = 0.(3.34) Proof. The events ¬I(G∗)and D(V∗, G)are increasing events with respect to ωand λ. The FKG inequality yields P(¬I(G∗)∩D(V∗, G)) = P(¬I(G∗)) ·P(D(V∗, G)) + εID where εID ≥0, thus proving (3.33). Propositions 1,3yield P(¬I(G∗)∩D(V∗, G)) =γ e−e−α∗ +εIe−e−α⋄ +εD+εID =γ e−e−α +εDγ e−e−α∗ +εIe−e−α⋄ +εD+εID,(3.35) Chapter 3. Probabilistic Flooding in Stochastic Networks 37 with α,λ∗π r2−ln (A λ + 1). From Lemma 3, we have P(¬I(G∗)∩D(V∗, G)) = P(W⋄∗ = 0) ≤e−e−α+dTV W⋄∗,Po e−α.(3.36) Combining this expression with (3.35) yields γ e−e−α+εDγ e−e−α∗ +εIe−e−α⋄ +εD+εID ≤e−e−α+dTV W⋄∗,Po e−α⋄∗ .(3.37) Since limλ→∞ εI= limλ→∞ εD= limλ→∞ εID = 0, and limλ→∞ γ= 1, combining (3.32) with (3.37) yields limλ→∞ εID = 0. 3.4.1.6 Dependence between Connectivity and Domination Let us study the event C(G∗)∩D(V∗, G), inferring the asymptotic behavior of dependence between connectivity of G∗and domination of Gby V∗. Proposition 5. The probability of G∗being connected and V∗dominating Gis P(C(G∗)∩D(V∗, G))=P(C(G∗))P(D(V∗, G)) + εCD,(3.38) where εCD ≥0and limλ→∞ εCD = 0. Proof. The events C(G∗)and D(V∗, G)are increasing events with respect to ωand λ. The FKG inequality yields P(C(G∗)∩D(V∗, G)) = P(C(G∗))P(D(V∗, G)) + εCD,(3.39) where εCD ≥0, thus proving (3.38). From (3.23), the probability of no isolated node in an RGG Gis asymptotically the same as the probability of Gbeing connected. Thus, lim λ→∞P(C(G∗)∩D(V∗, G))= lim λ→∞P(¬I(G∗)∩D(V∗, G)).(3.40) Conjugating (3.39) and (3.33) with (3.40), we get lim λ→∞P(C(G∗)) ·P(D(V∗, G)) + lim λ→∞εCD = lim λ→∞P(¬I(G∗)) ·P(D(V∗, G)) + lim λ→∞εID.(3.41) Combining this equation with (3.40), we get lim λ→∞P(¬I(G∗)) ·P(D(V∗, G)) + lim λ→∞εCD = lim λ→∞P(¬I(G∗)) ·P(D(V∗, G)) + lim λ→∞εID.(3.42) Combining (3.34) with (3.42), we get limλ→∞ εCD = 0, thus proving the proposition. 38 3.4. Probabilistic Flooding in Poisson Random Geometric Graphs without Border Effects Figure 3.6: Dependence between graph domination and connectivity/node isolation (algorithm AGS) in comparison to the analytical results (assuming εI= 0,εD= 0, and εID = 0). The relative frequency F¬iso∩dom of simulated graphs with no isolated nodes in G∗and simultaneously having V∗dominating Gis higher than the corresponding analytical expression, and is also slightly higher than F¬isoFdom. Moreover, the relative frequency Fconn∩dom of graphs where G∗is connected and simultaneously Gis dominated by V∗is slightly higher than FconnFdom. In summary, the dependency between connectivity and domination becomes negligible as the node density increases. The term γ e−e−αis the asymptotic expression and lower bound for the joint probability of both events. This joint probability converges from above to the product of the individual probabilities. Fig. 3.6 shows analytical and simulation results that evidence these facts. 3.4.1.7 Proof of Theorem 3(Global Outreach in RGGs) Combining Propositions 2,3and 5, we get Ψ(A, λ, r, ω) = hγ e−e−α∗ +εI−εCihe−e−α⋄ +εDi+εCD =γ e−e−α+εψ,(3.43) where εψ,εDγ e−e−α∗ + (εI−εC)e−e−α⋄ +εD+εCD.(3.44) As limλ→∞ εI= limλ→∞ εC= limλ→∞ εD= limλ→∞ εCD = 0, we get limλ→∞ εψ= 0, thus proving the theorem. Chapter 3. Probabilistic Flooding in Stochastic Networks 39 Figure 3.7: Probability of global outreach (assuming εΨ= 0) in comparison to the relative frequency of the experiments of the algorithm AGS yielding connected dominating sets. In summary, γ e−e−αis the asymptotic expression of the global outreach probability Ψ(A, λ, r, ω)for PF with forwarding probability ωon an RGG G(A, λ, r). Fig. 3.7 compares analytical and simulation results. As ωincreases, ΨGS converges to the analytical expression of Ψ. The difference becomes negligible for high values of Ψ. 3.4.2 Simulation of Outreach Probability in RGGs Figs. 3.8(a) and 3.8(b) show the probability/relative frequency of floodings yielding global outreach in RGGs on G(1, λ, r)over ω. The analytical curve Ψrepresents the asymptotic expression (εψ= 0) of Ψ(A, λ, r, ω)derived in Theorem 3. The curve ΨGS is obtained from the application of the algorithm AGS to RGGs on a torus. Comparing results for different ωvalues, there is a critical interval where Ψchanges from zero to one. The simulated value ΨGS may lie below or above the asymptotic curve of Ψ, depending on the graph parameters. Moreover, the difference between simulated and asymptotic values is relatively small and becomes negligible as ωincreases. This behavior is due to the interplay of the components from which our expression for Ψwas derived. 40 3.4. Probabilistic Flooding in Poisson Random Geometric Graphs without Border Effects (a) Parameters: A= 1;λ= 3 000;r= 0.04,ω= 0.2...1.0. (b) Parameters: A= 1;λ= 10 000;r= 0.03;ω= 0.1...0.6. Figure 3.8: Global outreach probability (εΨ= 0) and relative frequency of experiments yielding connected dominating sets when applying AGS to RGGs on a torus. Each simulated data point (with its respective 95% confidence interval limits) is obtained from 10 000 experiments. Each experiment is run over a new RGG. Chapter 3. Probabilistic Flooding in Stochastic Networks 41 3.4.3 Parameters for Global Outreach The goal is to meet a target value Ψby tuning ω. If Aand λare given, the parameters ωand rcan be chosen. Fig. 3.9(a) plots the (ω,r)-pairs that approximately achieve a required Ψfor RGGs with A= 1 and λ= 1000. The curves show a clear trade-off in the choice of the (ω,r)-pairs. Sparse RGGs (low values of r) require higher values of ω. For well-connected RGGs (high values of r), small values of ωare sufficient to approximately achieve the desired Ψ. Again, the plots stress the non-linear dependence between these two parameters. If Aand rare given, the parameters ωand λmay be chosen. Fig. 3.9(b) plots the (ω,λ)- pairs that approximately achieve a required outreach probability Ψfor RGGs with A= 1 and r= 0.1. The curves show the existence of a clear trade-off in the choice of the (ω,λ)-pairs. Sparse RGGs (low values of λ) require higher values of ω. For well-connected RGGs (high values of λ), small values of ωare sufficient to approximately achieve the desired Ψ. 3.5 – Probabilistic Flooding in Poisson Random Geometric Graphs with Border Effects The global outreach probability of PF with a network-wide forwarding probability degrades if we drop the assumption of a torus distance metric. This degradation in RGGs with Euclidean distance metric is due to border effects. The probability of a node receiving a message is directly affected by the following parameters: the forwarding probability ω, the number of its neighbors, and by the probability of its neighbors having the message. The border nodes — located at distance smaller than the transmission radius from the border of the square — are expected to have a smaller number of neighbors when compared to central nodes. Therefore, the smaller neighborhood of the border nodes implies that these nodes are less likely to receive a source message when using a PF algorithm with constant ω. This fact has a significant impact in Ψ, since it is the product of the probabilities of each node receiving a message. 42 3.5. Probabilistic Flooding in Poisson Random Geometric Graphs with Border Effects (a) Design options for λ= 10 000. (b) Design options for r= 0.1. Figure 3.9: Probabilistic flooding in Random geometric graphs on a torus. PF and RGG parameter tuples for a global outreach probability Ψ = {0.50,0.80,0.95,0.99}. Plots (a) shows (ω, r)-tuples and plots (b) shows (ω, λ)-tuples that approximately achieve the aforementioned global outreach probability. Chapter 3. Probabilistic Flooding in Stochastic Networks 43 We now show how a modification to the PF algorithm, that we denote as Border-Aware Probabilistic flooding (BAPF), minimizes the penalization incurred in Ψdue to these border effects. The main idea is that border nodes should receive a message with the same probability as non-border nodes receive it. To do so, border nodes use an increased forwarding probability ω′depending on their location: ω′(u),(1−φ(u) q(1 −ω)π r2if uis a border node, ωotherwise; where φ(u),minv∈N(u)a(v)and a(v)is the coverage area of the node vlying within the square of area A. Figs. 3.10(a) and 3.10(b) show the probability/relative frequency of floodings yielding global outreach in RGGs on G(1, λ, r)over ω. We can observe that the frequencies of global outreach of the BAPF algorithm over RGGs with Euclidean distance closely match the ones of the PF algorithm with constant forwarding probability over RGGs with toroidal distance. In conclusion, the impact of border effects on global outreach can be minimized by using PF with increased forwarding probability for border nodes. 3.6 – Probabilistic Flooding with Unreliable Links In this section we drop the assumption of an error-free broadcast medium, but consider networks with erasure channels (Ch. 7, [CT06]). A message may fail to be received by each neighbor of the transmitting node independently with probability ζ. To model this unreliable transmission medium, it suffices to sample uniformly at random the edge set Eof the graph model G(V, E)of the network with probability (1 −ζ). This yields a new graph Gζ(V, Eζ). The PF algorithm is now analysed over this graph to take into account the effects of unreliable transmissions. Theorem 1still holds for PF over networks with erasure channels after replacing Gby Gζ. Therefore, (3.1) becomes: Ψ(G, ζ, ω) = PC(G∗ ζ)∩D(V∗, Gζ).(3.46) We now specialize this expression for ERGs and RGGs. 4Network Coded Information Dissemination In the previous chapter we analyzed the reachability of Probabilistic Flooding with a network-wide common forwarding probability. We derived analytical expressions for the global outreach probability in networks with a broadcast medium, both with reliable and unreliable links. In this chapter we devote our attention to the study of the trade-offs between distinct networking paradigms — replication based forwarding and network coded forwarding — in the dissemination of information. When nodes communicate over the wireless medium, the broadcast property of the channel enables us to optimize the flooding process with respect to the number of transmissions, with obvious repercussions on the overall energy expenditure and bandwidth consumption. Typically, flooding resorts to replication based forwarding where nodes replicate and forward the information they receive. Since the basic problem of finding the minimum energy transmission scheme for broadcasting a set of messages in a given network is known to be NP-complete, flooding optimization often relies on approximation algorithms. In the class of probabilistic flooding algorithms, messages are forwarded according to a set of predefined probabilistic rules, whereas in the 51 52 class of deterministic algorithms, the forwarding decision is always the same for each set of input parameters. Multipoint relay (MPR) flooding is a deterministic algorithm which approximates the connected dominating set within a two-hop neighborhood of each node, thus forming a backbone of forwarding nodes and limiting the number of transmissions. This algorithm plays a key role in the Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks. The spectrum of dissemination algorithms was recently enlarged by the advent of the Network Coding (NC) paradigm ([ACLY00,FLBW06]), in which intermediate nodes are allowed to mix information flows through algebraic operations. Research suggests that NC based flooding algorithms yield further reductions in the number of transmissions required for flooding a message in a network. More specifically, Reference [FWLB06] quantifies these gains for ring and square lattice topologies, and presents a heuristic algorithm which outperforms probabilistic flooding 1for a class of random geometric graphs. Related work on the benefits of network coding includes a proof that the minimum energy single-source multicast problem with network coding becomes solvable in polynomial-time [LMHK04] and in a distributed manner [LRK+05]. The problem of multiple multicasts, which is closer to flooding, remains however an open problem [LRM+06]. Early results on improvements in terms of throughput, security and energy efficiency are surveyed in [FLBW06]. Seeking to understand how information dissemination techniques compete over network topologies with broadcast medium, we compare replication and network coded based flooding techniques with respect to the number of transmissions, delivery ratio, and the end-to-end delay. More specifically, we base our analysis on Erdős Rényi Random Graphs (ERGs), Binomial Random Geometric Graphs (B-RGGs) (or simply Random Geometric Graphs (RGGs) within this chapter), and Small-World Networks (SWNs) (see Section 2.6); and shed some light on the impact of the network topology on the behavior of two main representatives: the NC flooding algorithm of [FWLB06] and the MPR flooding algorithm of [CJA+03,AQL02]. We present the following main contributions: •An analytical characterization of the transmission cost of network coded flooding; •A set of simulation results for the number of transmissions, delivery ratio, and delay trade-offs between network coding and MPR flooding; •A critical discussion of the interplay between network topology and replication and network coded based flooding algorithms. 1Reference [FWLB06] denotes probabilistic flooding as probabilistic routing. Chapter 4. Network Coded Information Dissemination 53 This chapter is organized as follows. Section 4.1 presents the algorithms under study. Section 4.2 gives an asymptotic analysis of the number of transmissions required by NC flooding algorithm. Section 4.3 presents a simulation study that compares delay, delivery ratio, and number of transmissions of both NC and MPR flooding algorithms. Moreover, the impact of the topology in the performance of both algorithms is also inferred. Finally, Section 4.4 summarizes the main results presenting some concluding remarks. The main results of this chapter were published in [CBB08a,CBB08b] in collaboration with Christian Bettstetter and João Barros. Sections 4.1-4.4 were adapted from [CBB08a] and [CBB08b], which were written with the corresponding co-authors. 4.1 – Flooding Algorithms 4.1.1 Multipoint Relaying In its simplest form, pure flooding means that all nodes retransmit the received messages. In a network with nnodes, the number of retransmissions of a source message using pure flooding is n−1. Multipoint relaying ([AQL02,JLMV01]) aims at reducing the number of duplicate retransmissions while forwarding a broadcast message. This technique reduces the set of nodes retransmitting the message in such a away that a message forwarded by a node is guaranteed to reach (assuming lossless transmissions) all the two-hop neighbors of that node. For this purpose, each node selects a subset of its neighbors (“multipoint relays”) that ensure connectivity to every two-hop neighbor. Although finding the optimal MPR set is an NPcomplete problem, efficient heuristics are available for its calculation [Vie98]. In this study we resort to the heuristic described in Algorithm MPRSelection for the MPR set computation, and Algorithm MPRFlood for MPR-based flooding. Asymptotic analysis of these two MPR algorithms can be found in [JLMV01]. 4.1.2 Random Linear Network Coding based Flooding Random linear network coding can be viewed as a distributed method for combining different data flows ([HMK+06], [CWJ03]). The basic principle is that each node in the network selects independently and randomly a set of coefficients and uses them to form linear combinations of the messages it receives. These linear combinations are then sent over the outgoing links. The global encoding vector, i.e., the matrix of coefficients corresponding 54 4.1. Flooding Algorithms Algorithm 3 MPRSelection [AQL02] Let N(u)denote the set of one-hop neighbors of u, and N2(u)denote the set of two-hop neighbors of u. 1. Start with an empty multipoint relay set MPR(u). 2. Select those one-hop neighbor nodes in N(u)as multipoint relays which are the only neighbor of some node in N2(u), and add these one-hop neighbor nodes to the multipoint relay set MPR(u). 3. While there still exist some nodes in N2(u)which are not covered by the multipoint relay set MPR(u): (a) For each node in N(u)not in MPR(u)compute the number of nodes that it covers among the uncovered nodes in the set N2(u). (b) Add that node of N(u)in MPR(u)for which this number is maximum. Algorithm 4 MPRFlood [JLMV01] 1. A source node ubroadcasts its source message mu. 2. Each node vthat receives mure-broadcasts it only if: (a) vis a multipoint relay of the previous hop of the message, and (b) the message was not previously forwarded by v. to the operations performed on the messages, is sent along in the packet header to ensure that the end receivers are capable of decoding the original data. Specifically, it was shown that if the coefficients are chosen at random from a large enough finite field, Gaussian elimination succeeds with high probability [HMK+06]. The NC algorithm used in our study ([FWLB06]). combines random linear network coding with a probabilistic forwarding algorithm. The proposed algorithm (Algorithm NCFWB), resorts to a heuristic that assigns to each node va probabilistic forwarding factor f(v). This forwarding factor is set to be inversely proportional to the degree d(v), i.e., f(v) = γ d(v), where γ≥0is a scaling factor whose value depends on the topology [FWLB06]. A node that receives a linearly independent combination of messages will form and broadcast new random linear combinations of the current and previously received messages depending on this forwarding factor. Chapter 4. Network Coded Information Dissemination 55 Algorithm 5 NCFWB [FWLB06] 1. Associate with each node va forwarding factor f(v). 2. Node vtransmits its source message max{1,⌊f(v)⌋} times, and an additional time with probability p=f(v)−max{1,⌊f(v)⌋} if p > 0. 3. When a node vreceives linearly independent messages, it broadcasts a linear combination over the span of the received coding vectors ⌊f(v)⌋times, and an additional time with probability p=f(v)−⌊f(v)⌋. 4.2 – Asymptotic Analysis of Network Coded Flooding 4.2.1 Problem Statement Let G= (V, E)be a connected graph and furthermore let M={mu:u∈V}be a set of messages. Assume that every node u∈Vacts as a source node intending to deliver a source message muto every other node. In the NC flooding process, one transmission of a node refers to broadcasting a message or a linear combination of messages to all neighbors of the node. We are interested in the number TNC of required transmissions per source message, such that all nodes can decode all messages mu∈M. Our goal is to characterize the expected value E(TNC )in ERGs, RGGs, and SWNs. 4.2.2 General Bounds Let Dbe a random variable representing the degree of an arbitrary node in G. Furthermore, let ED(g(D)) denote the expected value of some function g(D)of the random variable D, and let ξD= ED(D−1)be the first negative moment of D. Theorem 4. For a transmission scheme defined by Algorithm NCFWB, with γchosen to ensure that all nodes can decode all messages, the expected value ED(TNC )is bounded as follows: (n−1) γ ξD+ 1 ≤ED(TNC )≤(n−1) γ ξD+ max(1, γ).(4.1) For γ≤1the bounds are tight. Proof. Let Stbe the total number of transmissions performed by all source nodes for the 56 4.2. Asymptotic Analysis of Network Coded Flooding transmission of their source messages, and Itbe the total number of transmissions performed by intermediate nodes due to reception of linearly independent combination of messages. As there are nsource messages, the expected number of transmissions per source message is ED(TNC ) = ED(St) + ED(It) n.(4.2) To characterize Stwe define Sas the random variable representing the number of transmissions performed by a source node to broadcast its source message. Since Ghas nsources, ED(S) = 1 nED(St).(4.3) According to step 2of Algorithm NCFWB: S=(1,for D≥γ(4.4a) jγ Dk+S′,for D < γ (4.4b) where S′is a Bernoulli random variable representing the outcome of a potential additional transmission, with P(S′= 1) = B=γ D−γ D. The conditioned expected value of S′is ED(S′|D < γ) = ED(B|D < γ) = EDγ D−jγ DkD < γ.(4.5) The conditioned expected value of Sgiven D < γ is ED(S|D < γ) = = EDjγ DkD < γ+ EDS′|D < γ = EDjγ DkD < γ + EDγ DD < γ−EDjγ DkD < γ = EDγ DD < γ ≤γ, (4.6) because D≥1. Conjugating (4.6) with the fact that S≥1, we get: 1≤ED(S)≤max(1, γ).(4.7) With (4.3), we obtain n≤ED(St)≤nmax(1, γ).(4.8) To characterize Itwe define Ias the random variable representing the number of transmissions performed by an intermediate node due to the reception of a linearly independent combination of messages. According to step 3of Algorithm NCFWB: I=jγ Dk+I′,(4.9) Chapter 4. Network Coded Information Dissemination 57 where I′is a Bernoulli random variable representing the outcome of a potential additional transmission, with P(I′= 1) = B=γ D−γ D. The expected value of I′is: ED(I′) = ED(B) = EDγ D−EDjγ Dk.(4.10) The expected value of Iis: ED(I) = EDjγ Dk+ ED(I′) = EDγ D=γED1 D=γ ξD.(4.11) Since after the completion of the transmission process of all nmessages, the rank increase of the decoding matrix of each node is n−1and since Ghas nnodes, we have ED(It) = n(n−1) ED(I) =n(n−1) γ ξD.(4.12) Finally, from (4.2), (4.8) and (4.12), we get (4.1). 4.2.3 Bounds for Erdős Rényi Random Graphs Corollary 1. Let G= (V, p)be a connected ERG, ǫ1=O1 (n−1) p, and ǫ2= (1 −p)n−1. For a transmission scheme defined by Algorithm NCFWB, with γchosen to ensure that all nodes can decode all messages, we have γ p+ 1 ≤ED(TNC)≤γ p 1 + ǫ1 1−ǫ2 + max(1, γ).(4.13) Proof. ERGs have a Binomial degree distribution B(n−1, p). As we consider connected graphs, however, we must use a conditioned degree distribution. We know that each node has at least one neighbor, i.e., d(u)>0∀u∈V. For this reason, we assume a positive Binomial distribution, which can be obtained by normalizing the Binomial distribution with the factor 1−P(D= 0). This yields P(D=d) = 1 1−qn−1n−1 dpdqn−1−d,(4.14) with q= 1 −pand d∈Z+. The first negative moment of the degree is thus: ξD= ED1 D= n−1 X d=1 1 dP(D=d) =1 1−qn−1 n−1 X d=1 1 dn−1 dpdqn−1−d.(4.15) 58 4.2. Asymptotic Analysis of Network Coded Flooding This function can be developed into the following series [Rem04]: ξD=1 1−qn−1 r−1 X i=0 i!qi pi+1 (n−1)[i+1] +o1 (n−1)[r], for any r∈Z+, with s[j]=s! (s−j)!. Moreover, it can be rewritten as: ξD=1 1−qn−11 (n−1) p+O1 ((n−1) p)2.(4.16) Hence, we can compute (n−1) ξD= =n−1 1−qn−11 (n−1) p+O1 ((n−1) p)2 =1 p(1 −qn−1)1 + O1 (n−1) p =1 p 1 + ǫ1 1−ǫ2 (4.17) ≥1 p(4.18) with ǫ1=O1 (n−1) pand ǫ2=qn−1= (1 −p)n−1. Replacing (4.17) and (4.18) in (4.1), we get (4.13). Fig. 4.1 plots the analytical and simulation results in ERGs, showing that the simulated average value of TNC lies within the analytical bounds of ED(TNC )assuming ǫ1=ǫ2= 0. Section 4.3.1 explains the used simulation method. 4.2.4 Bounds for Binomial Random Geometric Graphs Corollary 2. Let G= (V, r)be a connected RGG in a square with toroidal distance metric and area A≫π r2, and let β=π r2 A, and ǫ1=O1 (n−1) β, and ǫ2= (1 −β)n−1For a transmission scheme defined by Algorithm NCFWB, with γchosen to ensure that all nodes can decode all messages, γ β+ 1 ≤ED(TNC)≤γ β 1 + ǫ1 1−ǫ2 + max(1, γ).(4.19) Proof. RGGs have a Binomial degree distribution B(n−1,πr2 A). Similar to Section 4.2.3, we derive: (n−1) ξD=1 β 1 + ǫ1 1−ǫ2 (4.20) ≥1 β(4.21) Chapter 4. Network Coded Information Dissemination 59 0 10 20 30 0.2 0.4 0.6 0.8 1 Tx/msg p simulated value (γ=4) analytical upper/lower bound 0 10 20 30 0.2 0.4 0.6 0.8 1 Tx/msg p simulated value (γ=4) analytical upper/lower bound Figure 4.1: Number of Transmissions per Message using Network Coded Flooding in Erdős Rényi Random Graphs with 50 nodes. with β=π r2 A, and ǫ1=O1 (n−1) β, and ǫ2= (1 −β)n−1. Replacing (4.20) and (4.21) in (4.1), the above result follows. Fig. 4.2 plots the analytical and simulation results in RGGs, showing that the simulated average value of TNC lies within the analytical bounds of ED(TNC)assuming ǫ1=ǫ2= 0. Corollaries 1and 2show that in ERGs and RGGs, the expected number of transmissions required to flood a message is asymptotically independent of the number of nodes n. It depends on other topological parameters and on the scaling factor γof Algorithm NCFWB which, according to the authors of [FWLB06], is independent of n. 4.2.5 Bounds for Small-World Networks Corollary 3. Let G= (V, k, p)be a connected SWN, and let Dbe a random variable representing the degree of an arbitrary node in G. For a transmission scheme defined by the NC algorithm (Algorithm NCFWB) with γchosen to ensure that all nodes can decode all messages, we have (n−1) γ k+ 1 ≤ED(TNC )≤2 (n−1) γ k+ max(1, γ).(4.22) 66 4.3. Simulation based Analysis 0 0.2 0.4 0.6 0.8 1 0.4 0.5 0.6 0.7 0.8 0.9 1 Delivery Ratio r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) 0 0.2 0.4 0.6 0.8 1 0.4 0.5 0.6 0.7 0.8 0.9 1 Delivery Ratio r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) (a) Delivery Ratio 0 20 40 60 80 100 0.4 0.5 0.6 0.7 0.8 0.9 1 Delay r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) 0 20 40 60 80 100 0.4 0.5 0.6 0.7 0.8 0.9 1 Delay r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) (b) Delay 0 10 20 30 0.4 0.5 0.6 0.7 0.8 0.9 1 Tx/msg r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) 0 10 20 30 0.4 0.5 0.6 0.7 0.8 0.9 1 Tx/msg r0 / √A MPR NC (γ=1.0) NC (γ=2.0) NC (γ=4.0) (c) Number of Transmissions per Message Figure 4.5: Analysis in Random Geometric Graphs (no torus). Chapter 4. Network Coded Information Dissemination 67 We repeat the same simulations for an RGG with the nodes placed on a torus to avoid edge effects [Bet02]. To ensure connected graph realizations and a broad diameter range we set r √A∈[0.25,1], recalling that it differs from the above non-toroidal case. Fig. 4.6(a) presents the DR for this case. Fig. 4.6(b) shows that NC with sufficiently large γand small r √Astill presents a substantial “delay gain” (1/3the delay of MPR for r √A= 0.25). From Fig. 4.6(c) we observe that in an RGG with torus geometry, with r≪√A, NC again outperforms MPR in terms of the number of transmissions. The fraction TNC /TMP R ranges from 0.7 (γ= 3) to 1(for γ= 0, not shown in the figure), as the diameter converges to 1. This behavior suggests that, as the diameter of the network falls, there is little or no benefit in using network coding. The distinct behaviors of TNC with and without border effects suggest that Algorithm NCFWB is affected negatively by the existence of border nodes in RGGs with average node degree smaller than the average degree of nodes near the center of the square. 4.3.5 Analysis of Small-World Networks We compare MPR and NC flooding in SWNs with n= 50 nodes, mean degree k= 8, and edge rewiring probability p∈[0,1]. The NC algorithm (Algorithm NCFWB) is simulated with scaling factors γ∈ {0.5,1.5,2.5}, chosen via simulation on an iterative trial-and-error approach to guarantee the existence of (γ, p)tuples that achieve 100% DR. Fig. 4.7(a) presents the normalized values of clustering coefficient C(p)/C(0) and the average path length L(p)/L(0), with C(0) ≃0.64 and L(0) ≃3.57. These curves follow the typical behavior of the topological properties of SWNs ([Wat99,New03]). Fig. 4.7(b) presents the average MPR set size. This metric increases sharply for small p, stabilizing thereafter. Moreover, comparing Fig. 4.7(b) with Fig. 4.7(a) we find a correlation between the mean MPR set size and the reciprocal of C. This correlation can be interpreted as follows: since Cvis roughly equivalent to the probability of two neighbors of vbeing also neighbors of each other, a higher Cvimplies a more ’cliquish’ neighborhood. Therefore, the number of 1-hop neighbors necessary to reach all the 2-hop neighbors of v(MPR set) is expected to increase when Cvdecreases. This is the observed case in our simulations when p converges from 0to 1. 68 4.3. Simulation based Analysis 0 0.2 0.4 0.6 0.8 1 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Delivery Ratio r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) 0 0.2 0.4 0.6 0.8 1 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Delivery Ratio r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) (a) Delivery Ratio 0 20 40 60 80 100 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Delay r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) 0 20 40 60 80 100 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Delay r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) (b) Delay 0 10 20 30 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Tx/msg r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) 0 10 20 30 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Tx/msg r0 / √A MPR NC (γ=0.75) NC (γ=1.5) NC (γ=3.0) (c) Number of Transmissions per Message Figure 4.6: Analysis in Random Geometric Graphs (torus). Chapter 4. Network Coded Information Dissemination 69 For successful decoding with random linear NC, the number of linearly independent combinations of coded messages received by a node needs to be equal to the number of source messages. Otherwise, a node may still decode a fraction of the source messages. This is illustrated in Fig. 4.7(c) and Fig. 4.8(a) which plot the NR and the DR respectively. For γ= 0.5the NR is around 0.35 while the DR only reaches 0.2(20%). For γ= 1.5the NR is almost 1and the DR is slightly smaller. With γ= 2.5the NR is 1, yielding a DR of 100%. We also notice that for the same γ(e.g., γ= 0.5) both the NR and the DR keep fairly constant with p. This suggests that in SWNs the rewiring probability does not significantly affect the performance of the NC algorithm. This behavior can be interpreted as follows. Given that our NC algorithm is probabilistic, we might expect that the reduction of the diameter would contribute to an increase in the NR. On the other hand, since a larger C implies a higher number of redundant paths between nodes, we would expect the decrease of Cto cause a decrease in NR. We argue that the combined reduction of Land Ccancel one another yielding an almost constant NR (and DR) regardless of p. Fig. 4.8(b) presents the number of transmissions per message for NC, MPR, and pure flooding. We observe that TMP R degrades significantly with p, converging to the number of transmissions per message attained with pure flooding. As expected, TMP R increases with the MPR set size (Fig. 4.7(b)). In contrast, TNC is almost constant with the rewiring probability p, presenting a fairly low transmission cost when compared to pure flooding or MPR flooding. The fraction TNC/TMP R ranges from 0.77 (p= 0, with γ= 1.5) to 0.4(p= 1, with γ= 2.5). The delay behavior (Fig. 4.8(c)) presents the same trend as the number of transmissions. For sufficiently large γ, the delay ratio between NC and MPR ranges from around 0.5(p= 0, with γ= 1.5) to 0.3(p= 1, with γ= 2.5). 70 4.3. Simulation based Analysis 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 L C p L(p)/L(0) C(p)/C(0) 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 L C p L(p)/L(0) C(p)/C(0) (a) Normalized Clustering Coefficient (C) and Distance (L) 0 2 4 6 8 10 0 0.2 0.4 0.6 0.8 1 p MPR set size MPR set size (b) MPR set size 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 p MPR NC (γ=0.5) NC (γ=1.5) NC (γ=2.5) NR (c) Normalized Rank Figure 4.7: Analysis in Small-World Networks: (a) Normalized Clustering Coefficient and Distance; (b) MPR set size; and (c) Normalized Rank. Chapter 4. Network Coded Information Dissemination 71 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 p MPR NC (γ=0.5) NC (γ=1.5) NC (γ=2.5) Delivery Ratio (a) Delivery Ratio 0 10 20 30 40 50 60 0 0.2 0.4 0.6 0.8 1 Tx/msg p Pure flooding MPR NC (γ=0.5) NC (γ=1.5) NC (γ=2.5) 0 10 20 30 40 50 60 0 0.2 0.4 0.6 0.8 1 Tx/msg p Pure flooding MPR NC (γ=0.5) NC (γ=1.5) NC (γ=2.5) (b) Number of Transmissions per Message 0 50 100 150 0 0.2 0.4 0.6 0.8 1 p MPR NC (γ=0.5) NC (γ=1.5) NC (γ=2.5) Delay (c) Delay Figure 4.8: Analysis in Small-World Networks: (a) Delivery Ratio; (b) Number of Transmissions per Message; and (c) Delay. 72 4.4. Concluding Remarks 4.4 – Concluding Remarks Aiming at understanding how distinct forwarding paradigms influence the dissemination of information over communication networks, we selected one representative of each paradigm for our study: the network coding algorithm of [FWLB06] and replication based flooding MPR algorithm of [AQL02]. We evaluated (a) the number of transmissions per source message and (b) the incurred delay, and (c) the delivery ratio, under three relevant classes of random graph models. Somewhat surprisingly, the analytical part of our work shows that over ERGs and RGGs, the number of transmissions required to flood a message with the NC flooding algorithm under consideration is asymptotically independent of the number of nodes. This observation becomes less surprising in retrospect, if we consider that in these classes of graphs the average node degree increases linearly with the number of nodes. Therefore, a higher number of nodes corresponds to a higher number of neighbors that can be reached by a single broadcast transmission. Since random linear network coding mixes multiple messages in a single transmission, it is very effective at exploiting the benefits of increased node density. With multipoint relays, however, the number of transmissions per message is not independent of the number of nodes. In contrast, for SWNs, the analysis shows that the number of transmissions per message of the network coding algorithm scales linearly with the number of nodes. The reason for these distinct results can be understood by the fact that in SWNs with rewiring the average node degree remains fixed irrespective of the number of nodes. Naturally, the number of transmissions depends on other features of the network topology, as evidenced both by Corollaries 1,2, and 3, and by our simulation results. Consequently, the question as to which scheme should be preferred requires a nuanced answer. In ERGs, NC flooding outperforms MPR flooding in terms of number of transmissions per source message; the extent of this gain is however deeply influenced by the diameter of the network. Reducing the diameter decreases both the number of transmissions and the delay gains. A unit diameter implies no gain at all. In contrast, in general RGGs (non-toroidal distance metric) the considered NC flooding algorithm does not bring any benefits in terms of number of transmissions per message, when compared to MPR flooding. This appears to be in contradiction with the observation in [FWLB06]. However, it is worth noting that [FWLB06] focuses on RGGs on a torus and Chapter 4. Network Coded Information Dissemination 73 compares NC with probabilistic flooding. Our results thus indicate that the existence of border effects in general RGG topologies has a negative effect on the performance of the considered NC flooding technique. In SWNs, the analytical expression for the number of transmissions per message of network coding shows no dependency on the rewiring probability of the SWN model. This result is corroborated by the simulation results. In fact, the simulations highlight the stability of the NC performance metrics (delivery ratio, number of transmissions per message and delay) within all the rewiring range of the SWN model (i.e., with distinct clustering coefficients and average geodesic distance values). NC flooding demonstrates to be relatively immune to changes in local connectivity parameters (i.e., presence or absence of strong local connectivity), suggesting that the strengths of the studied network coding algorithm in SWN topologies stems from its network-wide coding/decoding operation paradigm. In turn, the MPR flooding algorithm does not produce significant overhead reduction in terms of number of transmissions per source message, in poorly clustered SWN topologies. Its Achilles’ heel resides on the scoped and limiting view of the topological properties centered in the neighborhood of each node. “The unavoidable price of reliability is simplicity.” C.A.R. Hoare 82 5.2. Emergency Navigation Graph Computation The R-Graph GR(VR, ER)represents the wireless connectivity between the sensor nodes. It constitutes the communication graph over which the S-graph mapped hazard information shall be disseminated. The node set VRis equal to the node set VSof the S-graph. The edge set ERcontains all node pairs which are in radio communication range of each other. From a modeling perspective, we consider that each S-node has a sensing unit and an actuation unit per incident S-edge. Each sensing unit is in charge of collecting the data from the sensing probes of the corresponding S-edge. The emergency navigation graph GNshall be computed by each sensor node having as input the S-graph and the sensor measurements associated to each of its S-edges. Each actuation unit is responsible for sending command instructions for the signaling devices associated to the corresponding S-edge, according to the computed emergency navigation graph GN. 5.2 – Emergency Navigation Graph Computation In this section we address the problem of finding shortest safest exit paths from a building suffering a disaster event. We present a generic solution in which we abstract a building topology by its B-graph, having hazard information associated to its edges. This generic method is, in practice, easily transposed to the WSN solution by using the S-graph (instead of the B-graph) as the representation of the building topology. We first present a formal description of the problem of determining the emergency navigation graph GN. Then we propose unambiguous quantifiable definitions for path safety and we propose a discrete and a continuous hazard metric to quantify path security. Finally, we propose algorithms to compute the shortest safest exit paths from nodes and from edges (i.e., the emergency navigation graph GN). 5.2.1 Problem Statement Let GB(VB, EB)be a graph that represents the topology of a building, with a set of exit nodes Vx⊆VB. Each edge e={u, v} ∈ EBhas a length d(e)>0. Moreover, let H be a totally ordered set of states whose elements represent the severity of a hazard, and let hbe a mapping EB→H that assigns to each edge e∈EBa hazard state h(e), which is timevariant. The mapping his a function that takes as input a vector of sensor measurements of an edge e, and gives as output a hazard state h(e). The goal is to find the shortest safest directed exit path from each point in the building (represented by GB) to one of the exit nodes Vx, each time there is a change in the state h(e)of Chapter 5. Applications in Dynamic Sensor Networks 83 an edge eof EB. Obtaining a solution to this problem encompasses solving two sub-problems: 1. Finding the shortest safest directed exit paths from the points of the building represented by nodes in VBto one of the exit nodes in Vx. The solution to this problem yields a directed forest GF= (VF, EF)where VF=VB. The roots of the trees of GF are the exit nodes vx∈Vx. Note that GFis a navigation graph in which some of the edges of EBmay be absent. 2. Finding a shortest safest exit direction from any point in the building abstracted by an edge of EB. This is particularly important for points mapped to edges of EBwhich are absent from EF. 5.2.2 Security Metrics To be able to solve this optimization problem we must (a) agree on possible unambiguous definitions for path safety that are quantifiable, and, based on that, we need (b) to find a cost metric c(e)for an edge ethat encompasses both its length d(e)and its hazard state h(e), that is in agreement with the path safety definition. The cost c(P)of a path Pis a function of the costs c(e)of its edges, according to the following expression: c(P),X e∈P c(e).(5.1) If a path P1is safer than a path P2, denoted as P1≺P2, then c(P1)<c(P2). In the following we present two alternative definitions of path safety encompassing a discrete and a continuous hazard state set H. 5.2.2.1 Discrete Hazard Metric (DHM) Let H ∈Zbe a totally ordered finite countable set of states that represent the severity of a hazard. With no loss of generality, assume H ={0,1,2,3}. The set is ordered by increasing level of danger. Table 5.1 assigns a meaning to each element of H. Table 5.1: Semantics of the elements of H State Alias Semantic 0 GREEN Safe 1 YELLOW Low danger 2 ORANGE Medium danger 3 RED High danger 84 5.2. Emergency Navigation Graph Computation A path P1is safer than a path P2(i.e., P1≺P2) if one of the following conditions holds: (a) P2has at least one edge whose hazard state is higher than the maximum of the hazard states of the edges of P1; (b) The maximum of the hazard states (hmax) of the edges of P1is equal to the maximum of P2, and P1has a smaller sum of the edge lengths with a hazard state equal to the maximum; (c) In case the above stated maximum hazard states and edge length sums are equal, P1is safer than P2if, only considering the edges with hazard state smaller than hmax, one of the conditions (a) or (b) hold. We now present an edge and a path safety cost function that is in agreement to the above path safety definition. The strategy we follow in the definition of the edge cost function is to weight the edge length by a factor that grows exponentially with its hazard state. A safety cost c(e)of an edge ewith length d(e)and hazard state h(e)is given by: c(e),d(e)·αh(e),(5.2) and the safety cost of a path Pis: c(P),X e∈P c(e) = X e∈P d(e)·αh(e).(5.3) A choice of the parameter αensuring that the path safety cost function is in agreement with the above path safety definition, is: α=Pe∈EBd(e) mine∈EB{d(e)}.(5.4) Proof. According to the path safety definition, a path P2with a total edge length ǫin hazard state n+ 1 is more dangerous than any other path P1with maximum edge hazard state n. With no loss of generality, consider a particular case in which P2is composed by just one edge with the smallest edge length ǫof the graph GB, and that it has a hazard state of n+ 1. Moreover, assume that a hypothetical path P1composed by the remaining edges, has a total edge length (Pe∈EBd(e)) −ǫwith hazard state n. Hence, c(P2)>c(P1)⇔ ǫ·αn+1 >  X e∈EB d(e) −ǫ ·αn⇔ α > Pe∈EBd(e)−ǫ ǫ⇔ α > Pe∈EBd(e) ǫ−1.(5.5) Chapter 5. Applications in Dynamic Sensor Networks 85 v3 v4v5 d=100 d=10 d=2.5 d=1 d=0.5 P1P2P3 c(P1)=102.5 c(P2)=238 c(P3)=26002 (a) h({v2, v4})is GREEN. P1is the safest path v3 v4v5 d=100 d=10 d=1 d=0.5 P1P2P3 c(P1)= 670 c(P3)=26002 c(P2)=238 (b) h({v2, v4})changed to YELLOW, P2is now the safest path Figure 5.3: Comparison of exit path safety costs from node v1to exit nodes in Vx={v4, v5}, using the DHM model. The hazard state of the edges is represented by its colors (see Table 5.1). Three alternative paths are considered: P1= (v1, v2, v4),P2= (v1, v3, v4), and P3= (v1, v3, v5). Conjugating the above inequality with the fact that ǫ= mine∈EB{d(e)}, an appropriate choice for αis the one given by (5.4). Fig. 5.3 shows alternative escape paths together with its costs from node v1to exit nodes v4 and v5. The hazard state of each edge is represented by its color, according to Table 5.1. The value of α(calculated by equation (5.4)) used to determine the path costs is 228. Fig. 5.3(a) shows that, although paths P2and P3are shorter than P1, they have edges with higher hazard state (YELLOW and ORANGE, respectively). Therefore, P1is, according to the above safety definition, the safest of the three paths. This is corroborated by its path safety cost which is the smallest. In Fig 5.3(b), the hazard state of edge {v2, v4}changed from GREEN to YELLOW.P2is now the safest path, since it has the smallest total edge length with hazard state YELLOW, and P3has an edge with higher hazard state (ORANGE). Again, this is in agreement with the chosen cost function, which now yields for P2the smallest safety cost. 5.2.2.2 Continuous Hazard Metric (CHM) Let H ⊂Rbe a totally ordered continuous set of states that represent the severity of a hazard. With no loss of generality, assume H = [0,1). The set is ordered by increasing level of danger. The value h(e) = 0 corresponds to a safe state while h(e)→1corresponds to a very dangerous state, meaning that edge eshould not be used for building evacuation purposes. We define the safety cost c(e)of an edge eto be a function of its hazard state h(e)and 86 5.2. Emergency Navigation Graph Computation 0 0.2 0.4 0.6 0.8 1 0 2 4 6 8 10 h(e) c(e)/d(e) α= 0 α= 1 α= 2 Figure 5.4: Normalized edge safety cost c(e) d(e)in the CHM model as function of the edge hazard state h(e)for α∈ {0,1,2}. its length d(e)according the following expression: c(e),d(e) (1 −h(e))α,(5.6) where α≥0is a parameter that controls the grow rate of c(e). The strategy used in the definition of the above edge safety cost function is to cause the edge length to grow hyperbolically (for α > 0) with its hazard state. A secure edge (h(e) = 0) has safety cost equal to its length d(e). Furthermore, as the hazard state of an edge converges to one, the corresponding safety cost converges asymptotically to infinity, reducing sharply the likelihood of its use in a escape path. Fig. 5.4 plots the edge safety cost c(e)normalized over d(e)for distinct values of the exponent α. The value α= 0, is a special case where the safety cost is not influenced by the hazard state h(e), assuming a value c(e) = d(e). The safety cost of a path Pis given by: c(P),X e∈P d(e) (1 −h(e))α.(5.7) 5.2.3 Safest Exit Paths from Nodes The problem of finding the minimum cost exit paths from each of the nodes in VBto one of the exit nodes vx∈Vxcan be classified as a Multiple-Destination Shortest Paths (MDSP) problem. A generic strategy to solve this problem is the following: Chapter 5. Applications in Dynamic Sensor Networks 87 A) Transform the MDSP problem into a Single-Destination Shortest Paths (SDSP) problem by: (a) Adding a virtual destination node vdto VB; (b) Adding a virtual edge {vd, vx}with cost c({vd, vx}) = 0 to EBfor each node vx∈Vx. B) Solve the SDSP problem for GBwith vdas destination node using a “standard” SDSP algorithm (e.g., Bellman-Ford or Dijkstra’s algorithm [CSRL01, Chapter 24]). The outcome should be a minimum cost tree GTrooted at vd. C) Derive the solution to the MDSP problem from GT. It should be the induced forest GF that arises by removing vdfrom GT. Data Structures in Dijkstra’s Algorithm The SDSP Dijkstra’s algorithm resorts to two key data structures (see [CSRL01, Chap. 24]): •A predecessor array π[v]indexed by the nodes vof VB, having as values, either a node of VBor the symbol NIL. The symbol NIL means “no object at all”, indicating that a node vhas no predecessor whenever π[v] = NIL. •A cost estimate array ˆc[v]indexed by the nodes of VB. Each ˆc[v]value is an upper bound for the cost of a minimum cost path from the destination vdto a node v∈VB. These arrays are updated in such a way that at the end of the execution of the Dijkstra’s algorithm, each value ˆc[v]represents the cost of a minimum cost directed path between the destination node vdand the node v. Moreover, each π[v]value represents the predecessor node of vin that path. MDSP Method The solution, denoted as MDSP method, that we propose to the MDSP problem is an adaptation of the SDSP Dijkstra’s algorithm. It has the advantage over the generic approach described above of not needing a virtual destination node. Let us first define the minimum cost δ(u, V )of the paths between a node uand the nodes of a node set Vas: δ(u, V ),       min c(P) : uP v, v ∈Vif there is a path from uto at least one node v∈V. ∞otherwise. 88 5.2. Emergency Navigation Graph Computation The meaning of the cost estimate array ˆc[v]in the MDSP method has a central difference from the one assumed in the SDSP Dijkstra’s algorithm. For each node v∈VB\Vx, the cost ˆc[v]is an upper bound for δ(v, Vx). I.e., it is an upper bound for the minimum of the costs of all the paths between vand the destination nodes vx∈Vx(and not with a specific destination node). The MDSP method is composed by Algorithm 6and 7. Algorithm 6initializes the predecessor and cost estimate arrays π[v]and ˆc[v]. In particular, ˆc[vx]is initialized with a cost equal to zero for all destination nodes vx∈Vx(being the main difference to the Algorithm INITIALIZE-SINGLE-SOURCE in [CSRL01, Chap. 24]). Algorithm 7differs from Algorithm DIJKSTRA in [CSRL01, Chap. 24] by replacing the call to INITIALIZE-SINGLE-SOURCE by a call to MDSP_INITIALIZE_ARRAYS (Algorithm 6). Sis a set of nodes for which the minimums of the costs of the paths to nodes vx∈Vxhas already been determined (i.e., ˆc[v] = δ(u, Vx),∀v∈S). Qis a min-priority queue of nodes v∈VBkeyed by the cost estimate values ˆc[v]. The algorithm repeatedly selects the node u∈VB\Swith the minimum cost estimate, adds uto S, and updates the minimum cost estimate ˆc[v]and the predecessor node π[v]for all neighbors vof u. Algorithm 6 MDSP_INITIALIZE_ARRAYS MDSP_INITIALIZE_ARRAYS (GB, Vx) 1: for each node v∈VBdo 2: ˆc[v]← ∞ 3: π[v]←NIL 4: end for 5: for each node vx∈Vxdo 6: ˆc[vx]←0 7: end for Algorithm 7 MDSP_MAIN MDSP_MAIN (GB, Vx,c()) 1: MDSP_INITIALIZE_ARRAYS (GB, Vx) 2: S← ∅ 3: Q←VB 4: while Q6=∅do 5: u←EXTRACT_MIN(Q) 6: S←S∪ {u} 7: for each node v∈N(u)do 8: if ˆc[v]>ˆc[u] + c({u, v})then 9: ˆc[v]←ˆc[u] + c({u, v}) 10: π[v]←u 11: end if 12: end for 13: end while After the completion of Algorithm 7, the predecessor subgraph GF= (VF, EF)induced Chapter 5. Applications in Dynamic Sensor Networks 89 v3 v4v5 d=100 d=2.5 d=1 d=0.5 d=10 δ(v1, Vx)=102.5 δ(v2, Vx)=2.5 δ(v3, Vx)=112.5 δ(v4, Vx)=0 δ(v5, Vx)=0 (a) h({v2, v4})is GREEN v3 v4v5 d=100 d=1 d=0.5 d=10 δ(v1, Vx)=238 δ(v3, Vx)=228δ(v2, Vx)=338 δ(v4, Vx)=0 δ(v5, Vx)=0 (b) h({v2, v4})changed to YELLOW Figure 5.5: Minimum cost exit forest determined by the MDSP method. Exit node set (forest roots) is Vx={v4, v5}. Edge costs follow the DHM model. The hazard state of the edges is represented by its colors (see Table 5.1). by the predecessor array π[v]constitutes a minimum cost directed forest having as roots the nodes in the destination node set Vx: •VFcorresponds to the set of vertices of GBwith non-NIL predecessors plus the destination node set Vx(i.e., VF={v∈VB:π[v]6= NIL}∪Vx); •EFis a directed edge set induced by π[v]for nodes in VF(i.e., EF={(v, π[v]) ∈EB: v∈VF\Vx}). Fig. 5.5 presents the minimum cost exit forest determined by applying the MDSP method to the graph of Fig. 5.3. Edge costs are determined using the DHM model. In Fig. 5.5(a) the exit forest is composed by two trees. One is a directed path (v3, v1, v2, v4). The other is composed by the single node v5(only a root node with no edges). In Fig. 5.5(b) the hazard state of edge {v2, v4}has changed to YELLOW. The exit forest is now composed by a tree that is the directed path (v1, v2, v3, v4), and another tree with the single root node v5. 5.2.4 Safest Exit Paths from Edges After applying the MDSP method to GBthe exit paths/directions are defined only for spatial points mapped into nodes of VBor into edges of EF. Therefore, the exit paths/directions remain undefined for points mapped into edges of EB\EF. We now show how to determine the exit paths/directions from a given point at any edge of EB. Consider an edge {u, v} ∈ EBwith length d({u, v})and cost c({u, v}). Moreover, consider 90 5.3. System Design a point pmapped over an edge {u, v}at “mapped distance” β·d({u, v})from u, where β∈ (0,1). Departing from p, the exit path in GFto be followed is the one with the starting node s=     uif (u, v)∈EF ∨((v, u)/∈EF∧δ(u, Vx) + β·c({u, v})< δ(v, Vx) + (1 −β)·c({u, v})), votherwise. Note that the values δ(u, Vx)and δ(v, Vx)are equal to the values of ˆc[u]and ˆc[v]respectively, at the completion of Algorithm 7. 5.3 – System Design In this section we present an overview of the functional architecture of the wireless sensor nodes software. We focus on the presentation of general design guidelines, avoiding entering into platform specific details. The software architecture is divided in two main functional planes, as shown in Fig. 5.6. The radio communication plane, associated to the R-graph, encompasses all the functions to support the communication between nodes (e.g., neighborhood inference, information dissemination). The spatial topology plane, associated to the S-graph, encompasses all the functions concerning the calculation of the emergency navigation graph, from hazard sensing to actuation decisions on signaling devices. 5.3.1 Sensing and Navigation Plane This logical plane encompasses all the S-graph related functions of a node necessary to compute the emergency navigation graph. These functions are: (1) the classification of the sensed data collected by the attached sensors; (2) the reception, processing and generation of S-graph deployment messages and S-graph Hazard State (SGHS) messages; (3) the computation of the emergency navigation graph, and (4) the actuation on signaling devices, according to the emergency navigation graph, whenever a severe hazard situation arises. Next we present a brief functional description of the modules of this logical plane. S-graph Construction and Maintenance Module: This module is responsible for acquiring and maintaining the information about the spatial topology (represented by an S-graph GS). The S-graph information is to be sent during the system deployment phase. Chapter 5. Applications in Dynamic Sensor Networks 91 R-Graph Neighborhood Information Module Incoming Messages Radio Port Message Demux Outgoing Messages Radio Port Radio Communication Plane HELLO msgs HELLO msgs Message Dissemination Module Signaling Devices Navigation Graph Computation S-Graph Hazard State Module Sensors S-Graph Contruction and Mainteneance Module Sensing Units Actuation Units S-Graph deployement msgs Sensing and Navigation Plane HS msgs Sensor measurements Incident S-edges S-Graph updates HS msgs Hazard states HS and S-Graph deployement msgs Figure 5.6: Functional architecture of a wireless sensor node for emergency evacuation support. 6Main Contributions and Future Work Motivated by the relevance of information dissemination algorithms in several networking scenarios, we characterized the efficiency of some of their main representatives in terms of transmission cost and reachability. We addressed both replication and network coded based approaches, devoting our main focus to the class of probabilistic algorithms. Networks were modelled as random graphs generated by stochastic processes, facilitating the analyses of the interplay between the network topology and the process of disseminating information. With the insights gained from the analysis, we applied information dissemination algorithms into specific networking and application scenarios. In particular, we designed a sensor-actuator networked system for emergency response in indoor scenarios. It computes the shortest safest paths to exits using the measurements collected by the sensors and disseminated throughout the network. The system was successfully tested in a prototype. 99 100 Probabilistic Flooding in Stochastic Networks We analyzed how to set a system-wide forwarding probability ωof probabilistic flooding, such that all network nodes ultimately receive a message with high probability. For this purpose, we proposed a graph sampling method, which can be applied in arbitrary networks. This method yields an induced subgraph, whose node set is obtained by sampling the total node set uniformly at random with probability ω. We proved that the events “all nodes receive a flooded message” and “the induced subgraph is connected and its nodes dominate the network graph” have the same probability, and thus, the analysis of global outreach in probabilistic flooding can be performed by analyzing the properties of the induced subgraph. In networks modeled as Erdős Rényi graphs, we derived the exact expression for the probability of global outreach. In random geometric graphs—as often used in modeling wireless ad hoc networks—the local correlation among edges results in stochastic dependencies, but, in our model, these dependencies become asymptotically negligible with increasing node density. We derived an asymptotic expression for the global outreach probability, which is also a good approximation for high node density. Moreover, we analyzed the impact of border effects in random geometric graphs and proposed a heuristic to overcome these effects. Finally, we studied probabilistic flooding in unreliable networks; erroneous links can simply be incorporated into both graph models, while the basic analysis and proofs remained in principle unchanged. Network Coded Information Dissemination Aiming at understanding how distinct forwarding paradigms influence the dissemination of information over communication networks, we selected one representative of each paradigm for our study: the network coding algorithm of [FWLB06] and replication based flooding MPR algorithm of [AQL02]. We evaluated (a) the number of transmissions per source message and (b) the incurred delay, and (c) the delivery ratio, under three relevant classes of random graph models. Somewhat surprisingly, the analytical part of our work shows that over ERGs and RGGs, the number of transmissions required to flood a message with the NC flooding algorithm under consideration is asymptotically independent of the number of nodes. This observation becomes less surprising in retrospect, if we consider that in these classes of graphs the average node degree increases linearly with the number of nodes. Therefore, a higher number of nodes corresponds to a higher number of neighbors that can be reached by a single broadcast transmission. Since random linear network coding mixes multiple messages in a single transmission, it is very effective at exploiting the benefits of increased node density. With multipoint relays, however, the number of transmissions per message is not independent of Chapter 6. Main Contributions and Future Work 101 the number of nodes. In contrast, for SWNs, the analysis shows that the number of transmissions per message of the network coding algorithm scales linearly with the number of nodes. The reason for these distinct results can be understood by the fact that in SWNs with rewiring the average node degree remains fixed irrespective of the number of nodes. Naturally, the number of transmissions depends on other features of the network topology, as evidenced by Corollaries 1,2, and 3, and by our simulation results. Consequently, the question as to which scheme should be preferred requires a nuanced answer. In ERGs, NC flooding outperforms MPR flooding in terms of number of transmissions per source message; the extent of this gain is however deeply influenced by the diameter of the network. Reducing the diameter decreases both the number of transmissions and the delay gains. A unit diameter implies no gain at all. In contrast, in general RGGs (non-toroidal distance metric) the considered NC flooding algorithm does not bring any benefits in terms of number of transmissions per message, when compared to MPR flooding. This appears to be in contradiction with the observation in [FWLB06]. However, it is worth noting that [FWLB06] focuses on RGGs on a torus and compares NC with probabilistic flooding. Our results thus indicate that the existence of border effects in general RGG topologies has a negative effect on the performance of the considered NC flooding technique. In SWNs, the analytical expression for the number of transmissions per message of network coding shows no dependency on the rewiring probability of the SWN model. This result is corroborated by the simulation results. In fact, the simulations highlight the stability of the NC performance metrics (delivery ratio, number of transmissions per message and delay) within all the rewiring range of the SWN model (i.e., with distinct clustering coefficients and average geodesic distance values). NC flooding demonstrates to be relatively immune to changes in local connectivity parameters (i.e., presence or absence of strong local connectivity), suggesting that the strengths of the studied network coding algorithm in SWN topologies stems from its network-wide coding/decoding operation paradigm. In turn, the MPR flooding algorithm does not produce significant overhead reduction in terms of number of transmissions per source message, in poorly clustered SWN topologies. Its Achilles’ heel resides on the scoped and limiting view of the topological properties centered in the neighborhood of each node. Applications in Dynamic Sensor Networks We designed a sensor-actuator networked system for emergency response in indoor scenarios. The system guides people to the exits of a building via the safest shortest paths. These 102 paths are computed by sensor nodes whenever a new measurement collected by a sensor is flooded throughout the network. We characterized the building evacuation problem with help of graph models. We proposed appropriate security metrics and algorithms that use flooded hazard information to compute the shortest safest paths to leave a building. Finally, we successfully implemented a prototype of the sensor-actuator networked system for emergency response. Since sensor data dissemination using Pure Flooding does not give the necessary delivery guarantees for this type of applications, we plan to investigate new information dissemination algorithms and MAC layer solutions that meet high reliability requirements. Future Work We now present an overview of possible lines of research based on the work presented in this thesis. Further Analysis of Probabilistic Flooding The analysis of Probabilistic Flooding, performed in this thesis, addressed a reference algorithm with a network-wide forwarding probability common to all nodes. A natural extension to this study is to analyze variants of Probabilistic flooding with non-constant forwarding probabilities (e.g., function of local topological properties such as node density or node degree and/or function of graph distance metrics). Another line of research is to relax the reachability metric of the forwarding process. We considered scenarios that require a forwarding probability that ensures a given target for the global outreach of a flooded message. Less demanding applications may only require that each node independently gets the message with at least some target probability. This is an analytical open problem that deserves to be addressed. A natural extension to the analysis of the reachability of Probabilistic flooding is to consider other network models. Some obvious candidates are Small-World Networks, ScaleFree Networks, and graphs with a specified degree distribution (i.e., the Configuration model). Network Coded Information Dissemination In Chapter 4our study of Network Coded Information Dissemination addressed a class of algorithms that does not guarantee that the reception by a node of an encoded message that is linear independent of the ones received so far, will necessarily yield the decoding of (at least) a source message. As future work, we plan to analyze and propose new network coded dissemination algorithms in which every reception of a linear independent coded message Chapter 6. Main Contributions and Future Work 103 will result in the decoding of a source message with high probability. Moreover, we plan to propose probabilistic network coded dissemination algorithms that are aware of topological distance metrics, and that are adaptive and self-regulating depending on the dynamics of the dissemination process. Adaptive Probabilistic Dissemination Algorithms In this thesis we addressed mainly the interplay between Probabilistic Dissemination algorithms and network topology. As future work we plan to develop information dissemination algorithms that are topology aware and self-adaptive, adjusting the forwarding probability based on the dynamics of the dissemination process and based on target performance goals. AProofs for Chapter 3 A.1 – Proof of Lemma 1 This proof is based on the Chen-Stein method and follows a similar approach as in [Pen97] and [FM08]. We first give definitions that are used in this and the following proofs. Consider the √A×√Asquare SAused in the RGG definition. We partition the square SAin m2 disjoint sub-squares Siof side √A/m centered at ai∈SA, i = 1..., m2. A neighborhood of dependence Nifor each i≤m2is Ni,{j:d(ai, aj)≤3r}, where ris the transmission range. We define Dias disks of radius rcentered at ai, i = 1, ..., m2. Finally, we define D(r, x)as the area of the union of two disks of radius rwith centers at toroidal distance x apart. From the Chen-Stein method we have dTV (W∗,Po (E(W∗))) ≤2 (b1+b2).(A.1) Now we show that (a) W∗is a sum of Bernoulli random variables, (b) E(W∗) = e−α∗, (c) limλ→∞ b1= 0, and (d) limλ→∞ b2= 0. For this purpose we partition the square SAas 105 106 A.1. Proof of Lemma 1 described in 2.4. For i= 1,...,m2, define X∗ ito be the indicator of the event that there is a single point of Π∗ sin a sub-square Si⊂SAand no points of Π∗ sin the region of all sub-squares intersecting Di\Si. We have lim m→∞ E(X∗ i) A λ∗ m2e−λ∗π r2= 1.(A.2) If the two disks of radius rcentered at aiand ajcover each other’s centers, i.e. d(ai, aj)≤r, we get E(X∗ iX∗ j) = 0,(A.3) and if d(ai, aj)> r, we have lim m→∞ E(X∗ iX∗ j) A λ∗ m22e−λ∗D(r, d(ai,aj)) = 1,(A.4) Therefore, the total number of isolated nodes of G∗is W∗= limm→∞ Pm2 i=1 X∗ i, and E(W∗) = lim m→∞ m2 X i=1 E (X∗ i) = A λ∗e−λ∗π r2=e−α∗,(A.5) where α∗=λ∗π r2−ln(A λ∗). We now show that limλ→∞ b∗ 1= 0 and limλ→∞ b2= 0. Combining (A.2) and (2.4) we get lim m→∞b1= lim m→∞ m2 X i=1 X j∈Ni E(X∗ i) E(X∗ j) = lim m→∞ m2 X i=1 π(3r)2 A m2A λ∗ m2e−λ∗πr22 =π(3r)2 Ae−2α∗−−−→ λ→∞ 0.(A.6) Defining an annular neighborhood Oifor each i≤m2as Oi,{j:r≤d(ai, aj)≤3r},(A.7) and combining (2.5) with (A.3), (A.4), (A.7), we get lim m→∞b2= lim m→∞ m2 X i=1 X j∈Ni,j6=i E(X∗ iX∗ j) = lim m→∞ m2 X i=1 X j∈Oi,j6=iA λ∗ m22 e−λ∗D(r, d(ai,aj)) .(A.8) Appendix A. Proofs for Chapter 3 107 Due to the spatial stationary property of the Poisson point process, we can re-write (A.8) as lim m→∞b2= lim m→∞m2X j∈O1,j6=1 A λ∗ m22 e−λ∗D(r, d(a1,aj)) =A(λ∗)2Zr≤|x|≤3r e−λ∗D(r, |x|)dx ≤A(λ∗)2π(3 r)2e−λ∗3 2πr2−−−→ λ→∞ 0.(A.9) Combining (A.1) with (A.6) and (A.9) yields lim λ→∞dTV W∗,Po e−α∗= 0 .(A.10) A.2 – Proof of Lemma 2 Similarly, applying the Chen-Stein method we have dTV (W⋄,Po (E(W⋄))) ≤2 (b1+b2).(A.11) For i= 1,...,m2, define X⋄ ito be the indicator of the event that there is a single point of Π⋄in a sub-square Si⊂SA, and that there are no points of Π∗ sin the region of all sub-squares intersecting Di. We have lim m→∞ E(X⋄ i) A λ⋄ m2e−λ∗πr2= 1,(A.12) lim m→∞ E(X⋄ iX⋄ j) A λ⋄ m22e−λ∗D(r, d(ai,aj)) = 1.(A.13) Thus, the total number of non-dominated nodes of Gis W⋄= limm→∞ Pm2 i=1 X⋄ i, and E (W⋄) = lim m→∞ m2 X i=1 E (X⋄ i) = A λ⋄e−λ∗π r2=e−α⋄, where α⋄=λ∗π r2−ln (A λ⋄). We now show that limλ→∞ b1= 0 and limλ→∞ b2= 0. Combining (A.12) with (2.4), we 114 B.2. Abbreviations N-graph Emergency navigation graph NC Network Coding NR Normalized Rank OLSR Optimized Link State Routing P-RGG Poisson Random Geometric Graph PF Probabilistic Flooding PP Point Process PPP Poisson Point Process R-graph Radio connectivity graph RFGO Relative frequency of global message outreaches RLNC Random Linear Network Coding RGG Random Geometric Graph RGGT Random Geometric Graph on a Torus S-graph Spatial graph SGHS S-graph Hazard State SSSP Single-Source Shortest Paths SDSP Single-Destination Shortest Paths SWN Small-World Network WSN Wireless Sensor Network BBibliography [ACLY00] R. Ahlswede, N. Cai, S.Y.R. Li, and RW Yeung. Network information flow. IEEE Trans. on Information Theory, 46(4):1204–1216, July 2000. [pp. 4and 54] [AGG89] R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: The Chen-Stein method. Ann. of Prob., 17(1):9–25, January 1989. [pp. 12 and 48] [AGG90] R. Arratia, L. Goldstein, and L. Gordon. Poisson approximation and the Chen-Stein method. Statistical Science, 5(4):403–424, November 1990. [pp. 12 and 48] [AQL02] L. Viennot A. Qayyum and A. Laouiti. Multipoint relaying for flooding broadcast messages in mobile wireless networks. Proc. HICSS, Big Island, HI, USA, January 2002. [pp. 4,54,55,74, and 102] [AWF02] K. Alzoubi, P.-J. Wan, and O. Frieder. New distributed algorithm for connected dominating set in wireless ad hoc networks. Proc. HICSS, Big Island, HI, USA, January 2002. [p. 4] 115 116 Bibliography [BBB+08] Z. Benenson, M. Bestehorn, E. Buchmann, F. Freiling, and M. Jawurek. Query dissemination with predictable reachability and energy usage in sensor networks. Ad-hoc, Mobile and Wireless Networks, 5198:279–292, 2008. [p. 4] [Bet02] C. Bettstetter. On the minimum node degree and connectivity of a wireless multihop network. In Proc. ACM MobiHoc, Lausanne, Switzerland, June 2002. [pp. 66 and 69] [Bet04] C. Bettstetter. On the connectivity of ad hoc networks. The Computer Journal, 47(4):432–447, July 2004. [p. 48] [Bol98] B. Bollobás. Modern Graph Theory. Springer, 1998. [p. 15] [BW00] A. Barrat and M. Weigt. On the properties of small-world network models. The European Physical Journal B - Condensed Matter, 13(3):547–560, January 2000. [p. 62] [CBB08a] S. Crisóstomo, J. Barros, and C. Bettstetter. Flooding the Network: Multipoint Relays versus Network Coding. In Proc. IEEE ICCSC 2008, Shanghai, China, May 2008. [pp. 6and 55] [CBB08b] S. Crisóstomo, J. Barros, and C. Bettstetter. Network coding with shortcuts. In Proc. IEEE Intern. Conf. on Communication Systems (ICCS), Guangzhou, China, November 2008. [pp. 6and 55] [Che75] L. H. Y. Chen. Poisson approximation for dependent trials. Ann. of Prob., 3(3):534–545, June 1975. [pp. 12 and 48] [CJA+03] T. Clausen, P. Jacquet, C. Adjih, A. Laouiti, P. Minet, P. Muhlethaler, A. Qayyum, and L.Viennot. Optimized link state routing protocol (OLSR). RFC 3626, October 2003. Network Working Group. [pp. 4and 54] [Cre91] N. A. C. Cressie. Statistics for Spatial Data. Wiley, 1991. [p. 16] [Croa] Crossbow Technology, Inc. Crossbow Technology Webpage. http://www.xbow.com. Accessed: July 30, 2012. [p. 95] [Crob] Crossbow Technology, Inc. TelosB mote platform. www.willow.co.uk/TelosB_Datasheet.pdf. Accessed: July 30, 2012. [p. 95] [CSBB09] S. Crisóstomo, U. Schilcher, C. Bettstetter, and J. Barros. Analysis of probabilistic flooding: How do we choose the right coin? In Proc. IEEE Intern. Conf. on Communications (ICC), Dresden, Germany, June 2009. [pp. 6and 23] Bibliography 117 [CSBB12] S. Crisóstomo, U. Schilcher, C. Bettstetter, and J. Barros. Probabilistic flooding in stochastic networks: Analysis of global information outreach. Computer Networks, 56(1):142 – 156, 2012. [pp. 6and 23] [CSRL01] T. Cormen, C. Stein, R. Rivest, and C. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. [pp. 89 and 90] [CT06] T. Cover and J. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006. [p. 44] [CWJ03] P. Chou, Y. Wu, and K. Jain. Practical network coding. In Proc. Allerton Conf. Communication, Control and Computing, October 2003. [pp. 56 and 64] [DYT05] S. Dixit, E. Yanmaz, and O. K. Tonguz. On the design of self-organized cellular wireless networks. IEEE Communications Magazine, 43(7):86–93, 2005. [p. 17] [FB08] A. Faragó and S. Basagni. The effect of multi-radio nodes on network connectivity - A graph theoretic analysis. Proc. IEEE PIMRC, Cannes, France, September 2008. [p. 16] [FKG71] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Comm. Math. Phys, 22:89–103, 1971. [pp. 11,32, and 48] [FLBW06] C. Fragouli, J.-Y. Le Boudec, and J. Widmer. Network coding: an instant primer. SIGCOMM Comput. Commun. Rev., January 2006. [p. 54] [FM08] M. Franceschetti and R. Meester. Random Networks for Communication: From Statistical Physics to Information Systems. Cambridge University Press, 2008. [pp. 48 and 107] [FWLB06] C. Fragouli, J. Widmer, and J. Y. Le Boudec. A network coding approach to energy efficient broadcasting: From theory to practice. In Proc. INFOCOM, Barcelona, Spain, April 2006. [pp. 5,54,56,61,64,66,74,102, and 103] [GHH06] R. Gowaikar, B. Hochwald, and B. Hassibi. Communication over a wireless network with random connections. IEEE Trans. Inform. Theory, 52:2857–2871, 2006. [p. 16] [Gil59] E. N. Gilbert. Random graphs. Ann. of Math. Stat., 30(4):1141–1144, December 1959. [p. 26] [GLvB+03] D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. The nesC language: A holistic approach to networked embedded systems. SIGPLAN Not., 38(5):1–11, May 2003. [p. 95] 118 Bibliography [Gol05] A. Goldsmith. Wireless Communications. Cambridge University Press, 2005. [pp. 13 and 14] [Gri99] G. Grimmett. Percolation. Springer-Verlag, 1999. [p. 11] [GS11] R. Gaeta and M. Sereno. Generalized probabilistic flooding in unstructured peer-to-peer networks. IEEE Trans. Parallel Distrib. Syst., 99, 2011. [p. 4] [Hel03] A. Helmy. Small worlds in wireless networks. IEEE Communications Letters, 7(10):490–492, October 2003. [p. 17] [HHL06] Z. Haas, J. Halpern, and L. Li. Gossip-based ad hoc routing. IEEE/ACM Trans. Netw., 14(3):479–491, 2006. [pp. 4,23, and 48] [HLY04] K. Hui, J. Lui, and D. Yau. Small world overlay P2P networks. In Proc. Int. Workshop Quality of Service, Montreal, Canada, June 2004. [p. 17] [HMK+06] T. Ho, M. Médard, R. Koetter, D.R. Karger, M. Effros, J. Shi, and B. Leong. A random linear network coding approach to multicast. IEEE Transactions on Information Theory, 52(10):4413–4430, 2006. [p. 56] [JLMV01] P. Jacquet, A. Laouiti, P. Minet, and L. Viennot. Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models. Technical Report 4260, INRIA, 2001. [pp. 55 and 56] [Kin93] J. Kingman. Poisson Processes. Oxford University Press, 1993. [p. 11] [Kle00] J. Kleinberg. The small-world phenomenon: an algorithm perspective. In Proc. Thirty-second annual ACM symposium on Theory of computing, New York, NY, USA, 2000. [p. 18] [KWB01] B. Krishnamachari, S. B. Wicker, and R. Bejar. Phase transition phenomena in wireless ad hoc networks. Proc. IEEE GLOBECOM, San Antonio, TX, USA, November 2001. [pp. 4,23, and 48] [LMHK04] D. Lun, M. Medard, T. Ho, and R. Koetter. Network coding with a cost criterion. In Proc. Intern. Symp. on Information Theory and its Applications, Parma, Italy, October 2004. [pp. 5and 54] [LMP+05] P. Levis, S. Madden, J. Polastre, R. Szewczyk, K. Whitehouse, A. Woo, D. Gay, J. Hill, M. Welsh, E. Brewer, and D. Culler. TinyOS: An Operating System for Sensor Networks Ambient Intelligence. In Ambient Intelligence, chapter 7, pages 115–148. Springer Berlin Heidelberg, 2005. [p. 95] [LRK+05] D. Lun, N. Ratnakar, R. Koetter, M. Medard, E. Ahmed, and H. Lee. Achieving minimum-cost multicast: a decentralized approach based on network coding. In Proc. IEEE Infocom, Miami, FL, USA, March 2005. [pp. 5and 54] Bibliography 119 [LRM+06] D. Lun, N. Ratnakar, M. Médard, R. Koetter, D. Karger, T. Ho, E. Ahmed, and F. Zhao. Minimum-cost multicast over coded packet networks. IEEE/ACM Trans. Netw., 14:2608–2623, 2006. [pp. 5and 54] [LW02] W. Lou and J. Wu. On reducing broadcast redundancy in ad hoc wireless networks. IEEE Trans. Mobile Comput., 1(2):111–123, 2002. [p. 4] [MAA08] D. Miorandi, E. Altman, and G. Alfano. The impact of channel randomness on coverage and connectivity of ad hoc and sensor networks. IEEE Trans. Wireless Commun., 7:1062–1072, 2008. [p. 16] [Mad08] U. Madhow. Fundamentals of Digital Communication. Cambridge University Press, 2008. [p. 13] [Man69] N. Mantel. Functional averages of a variable. The American Statistician, 23(1):21–22, February 1969. [p. 62] [MNW04] G. S. Manku, M. Naor, and U. Wieder. Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks. In In Proc. of the 36th ACM Symp. on Theory of Computing (STOC), pages 54–63, 2004. [p. 17] [New03] M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167, 2003. [pp. 17 and 69] [NTCS99] S.-Y. Ni, Y.-C. Tseng, Y.-S. C., and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. Proc. ACM/IEEE MobiCom, Seattle, WA, USA, August 1999. [p. 23] [NW99] M. Newman and D. Watts. Scaling and percolation in the small-world network model. Physical Review E, 60(6):7332–7342, December 1999. [p. 18] [OKS10] K. Oikonomou, D. Kogias, and I. Stavrakakis. Probabilistic flooding for efficient information dissemination in random graph topologies. Computer Networks, 54(10):1615 – 1629, 2010. [p. 4] [Pen97] M. Penrose. The longest edge of the random minimal spanning tree. Ann. Appl. Prob., 47(4):432–447, July 1997. [pp. 33,48, and 107] [Pen03] M. Penrose. Random Geometric Graphs. Oxford Univ. Press, July 2003. [pp. 12,16,17, and 31] [Rem04] G. Rempala. Asymptotic factorial powers expansions for Binomial and Negative Binomial reciprocals. American Mathematical Society, 132(1):261–272, 2004. [p. 59] 120 Bibliography [RKV04] A. Reznik, S. Kulkarni, and S. Verdú. A small world approach to heterogeneous networks. Communication in Information and Systems, 3(4):325–348, 2004. [p. 17] [SB07] A. Stauffer and C. Barbosa. Probabilistic heuristics for disseminating information in networks. IEEE/ACM Trans. Netw., 15(2):425–435, 2007. [p. 4] [Sch05] M. Schwartz. Mobile Wireless Communications. Cambridge University Press, 2005. [pp. 13 and 15] [SCS03] Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. Proc. IEEE Wireless Comm. Netw. Conf., New Orleans, LA, USA, March 2003. [pp. 4,23, and 48] [SKM85] D. Stoyan, W. Kendall, and J. Mecke. Stochastic Geometry and its Applications. John Wiley & Sons, 1985. [p. 10] [SRS07] A. Sangwan, V. Ramaiyan, and R. Shorey. Reliable multihop broadcast protocols for inter-vehicular communication in a fading channel. Proc. Intern. Conf. Commun. Sys. Softw. Middlew., January 2007. [p. 4] [Tin12] TinyOS team. TinyOS Webpage. http://www.tinyos.net/, 2012. Accessed: July 30, 2012. [p. 95] [TMA09] X. Ta, G. Mao, and B. Anderson. On the phase transition width of kconnectivity in wireless multihop networks. IEEE Trans. Mobile Comput., 8(7):936–949, July 2009. [p. 16] [Vie98] L. Viennot. Complexity results on election of multipoint relays in wireless networks. Technical Report RR-3584, INRIA, 1998. [p. 55] [vJPHE02] M. Čagalj, J.-P. Hubaux and C. Enz. Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. Proc. ACM MobiCom, Atlanta, GA, USA, September 2002. [p. 4] [Wat99] D. Watts. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, 105(2):493–527, September 1999. [p. 69] [WS98] D. Watts and S. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393(6684), June 1998. [pp. 17 and 18] [YOKM+06] M. Yassein, M. Ould-Khaoua, L. Mackenzie, S. Papanastasiou, and A. Jamal. Improving route discovery in on-demand routing protocols using local topology information in MANETs. Proc. ACM PM2HW2N, Torremolinos, Spain, October 2006. [pp. 4and 48] Bibliography 121 [YOKP05] M. Yassein, M. Ould-Khaoua, and S. Papanastasiou. Performance evaluation of flooding in manets in the presence of multi-broadcast traffic. Proc. IEEE Intern. Conf. Parallel Distr. Sys., Fukuoka, Japan, July 2005. [pp. 4and 48] [YWLF06] C. Yi, P. Wan, X. Li, and O. Frieder. Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with Bernoulli nodes. IEEE Trans. Commun., 54(3):510–517, March 2006. [p. 48]