Construction and Analysis of Distributed Coding Algorithms for Data Persistence and Data Gathering in Wireless Ad-hoc Networks

Abstract

<p>Starting with the rediscovery of low-density parity-check (LDPC) codes, the last<br />decade of coding theory was marked by extensive research and major advances in&nbsp;the field of sparse-graph codes. Low complexity encoding/decoding procedures and&nbsp;close-to-optimal properties of sparse-graph codes spurred their application virtually&nbsp;on all layers of the communication protocol stack.<br />Another important development that occurred recently within coding theory was<br />the introduction of network coding, which reaches the capacity limits of information&nbsp;transfer in multiuser scenarios. Network coding particularly highlighted the potential&nbsp;of simple random linear network codes in various usage scenarios.<br />Among broad variety of applications, the usage of sparse-graph and random linear&nbsp;codes for the efficient packet-level coding for the purposes of efficient data dissemination,&nbsp;distributed data storage and securing data persistence in wireless ad-hoc&nbsp;networks recently attracted a lot of interest. These applications constitute the topic&nbsp;of this thesis. Particularly, the thesis addresses the construction and analysis of&nbsp;simple and efficient coding algorithms in a two specific scenarios of wireless ad-hoc&nbsp;networking.<br />In the first part of thesis, we investigate the distributed sparse-graph coding in<br />decentralized wireless sensor networks (WSNs). We are concerned with WSNs with&nbsp;a flat network topology, where nodes are deployed in remote areas with no access to&nbsp;the external networks and where data gathering is performed only occasionally. Our&nbsp;aim is to develop distributed, robust and stateless sparse-graph coding algorithm that&nbsp;results with distributed data storage, ensures data persistence until the next gathering&nbsp;cycle and allows for the recovery of the whole sensed information by gathering of the&nbsp;encoded data from a random subset of network nodes. Following these objectives,&nbsp;we designed a packet-centric approach to distributed coding. The core idea of the&nbsp;proposed approach is to perform distributed encoding using packets that randomly&nbsp;walk over network, sample and encode sensed data, and finally perform networkwide&nbsp;dispersion of the encoded data. We introduce the the general framework of the proposed scheme and specialize it for several important classes of sparse-graph codes -&nbsp;low-density generator matrix (LDGM) codes, irregular and regular repeat accumulate&nbsp;(IRA and RA) codes, LT and raptor codes. Finally, we assess performance of the&nbsp;scheme for several data gathering strategies.<br />In the second part of the thesis, we expand the proposed packet-centric approach<br />to perform the distributed encoding of random linear codes. Specifically, we analyze&nbsp;the distributed encoding of sparse random linear codes, as our aim is to minimize&nbsp;communication expenses required by the encoding procedure. We further develop the&nbsp;scheme and propose the distributed encoding algorithm called Fireworks, with an aim&nbsp;to exploit the broadcast nature of wireless transmissions. We compare the performance&nbsp;of the packet-centric and Fireworks random linear coding via a simulation study.&nbsp;The third part of the thesis is devoted to efficient infrastructure-to-vehicle (I2V)&nbsp;data dissemination in vehicular ad-hoc networks (VANETs). We consider the scenario&nbsp;where infrastructure nodes (i.e., base stations) periodically distribute traffic-related&nbsp;data to mobile nodes (i.e., vehicles). Our aim is to design a simple and reliable data&nbsp;dissemination scheme, which does not rely on the lengthy/complex acknowledgment,&nbsp;retransmission, handover and content reconciliation procedures. We demonstrate&nbsp;that these goals could be achieved by the usage of fountain codes applied at the&nbsp;application layer. Furthermore, we introduce the importance layers in the disseminated&nbsp;data and demonstrate that the unequal error protection (UEP) fountain codes&nbsp;are well suited for the corresponding set-up, allowing both more reliable and faster&nbsp;retrieval of higher importance layers.</p>

<p> Teza se bavi konstrukcijom i analizom&nbsp;distribuiranih kodnih algoritama kodova<br /> na retkim grafovima i slucajnih linearnih&nbsp;kodova, u bežicnim ad-hok mrežama.</p>