Distribution des degrés | EPFL Graph Search

thumb|right|320px|Distribution de degrés intrant/sortant du réseau des liens hypertextes de Wikipedia (échelles logarithmiques) La distribution des degrés est, dans l'étude des graphes et des réseaux, une distribution probabiliste des degrés de chaque sommet du réseau. Le degré d'un sommet est le nombre de liens entre ce sommet et d'autres sommets du graphe. Définition Le degré d'un sommet dans un réseau est égal au nombre de liens ou d'arêtes liant ce sommet à d'autres sommets. Si un réseau est orienté, ce qui signifie que des arcs pointent dans un sens, d'un sommet vers un autre, les sommets ont alors deux degrés différents: le degré intrant (in-degree), qui correspond au nombre d'arcs pointant vers lui, et le degré sortant (out-degree), qui décompte le nombre d'arcs partant dudit sommet. La distribution de degrés P(k) d'un réseau est alors définie comme étant la fraction des sommets dans le réseau ayant un degré k. S'il y a n sommets au total dans un réseau et que nk

Collaborative routing in mobile partitioned networks

Natasa Sarafijanovic-Djukic

Embedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spatially heterogeneous node distributions, which may cause network partitions. In this thesis, we consider the problem of routing in mobile networks under such challenging conditions. More specifically, we endeavor to identify features of mobility common to different applications, in order to devise routing methods that are tailored to exploit these features. We explore two features in particular, (i) predictability and (ii) stable and heterogeneous spatial node distribution. A mobility process is predictable if the future location of a node can be well estimated, given knowledge of its current and past locations and possibly other statistics. We show how the performance of routing can be improved by explicitly incorporating mobility prediction. Specifically, we consider the performance of Last Encounter Routing (LER) under a simple synthetic random waypoint (RWP) mobility model. We extend the LER algorithm so that it takes into account predicted node trajectories when making routing decisions, and we show that this significantly improves its performance. A mobility process has a stable spatial node distribution if, informally, the node density remains the same over time, even though individual nodes are not constrained in space. This is a common feature of many mobility patterns because the spatial distribution is determined by the natural or constructed environment, regardless of the behavior of individual nodes. This typically leads to heterogeneous connectivity and to network partition, where highly connected clusters are interspersed with low-connectivity regions. We model such a situation with a set of stable concentration points (CPs) characterized by high node density, and with a mobility process that describes how nodes move between these islands of connectivity. We study two instances of this model: the G-model, where the CPs and the flow of nodes are abstracted as a graph, and the H-model, where nodes perform heterogeneous random walks on the plane. We exploit the presence of this stable CP topology in order to develop an efficient routing algorithm under these two mobility models. Our routing algorithm, Island Hopping (IH), exploits knowledge of the CP topology to make routing decisions. IH achieves a very good delay-throughput trade-off compared with several other existing routing algorithms, and it scales well with the network size. In many situations, it would be unrealistic to assume that CPs and the flows of mobile nodes among them are known a-priori. We develop methods, collectively called Collaborative Graph Discovery (COGRAD), that allow the nodes to discover the CP graph without any explicit signals from the environment (such as GPS coordinates or fixed beacons). We show that COGRAD can replace an oracle with knowledge of the CP topology after a sufficient warm-up period, allowing IH to operate even in scenarios without any cues from the environment.

EPFL2010

On the Convergence Speed of Spatially Coupled LDPC Ensembles

Vahid Aref

Spatially coupled low-density parity-check codes show an outstanding performance under the low-complexity belief propagation (BP) decoding algorithm. They exhibit a peculiar convergence phenomenon above the BP threshold of the underlying non-coupled ensemble, with a wave-like convergence propagating through the spatial dimension of the graph, allowing to approach the MAP threshold. We focus on this particularly interesting regime in between the BP and MAP thresholds. On the binary erasure channel, it has been proved that the information propagates with a constant speed toward the successful decoding solution. We derive an upper bound on the propagation speed, only depending on the basic parameters of the spatially coupled code ensemble such as degree distribution and the coupling factor

w

. We illustrate the convergence speed of different code ensembles by simulation results, and show how optimizing degree profiles helps to speed up the convergence.

2013