Two main approaches to achieve reliable data transfer over error-prone networks are retransmission and Forward Error Correction (FEC). Retransmission techniques retransmit packets when they are lost or despaired, causing significant delays, especially on multihop connections. On the contrary, to reduce latency FEC sends redundant data together with the original one. In particular, FEC through Random Linear Network Coding (RLNC) reduces the number of distinct packet transmissions in a network and minimizes packet transmissions due to poor network conditions. Consequently, RLNC has the potential to both improve energy efficiency and reduce the overall latency in a network. Fulcrum network coding (FNC), proposed as an RLNC's variation, has partly solved the challenge of heterogeneous communication networks by providing two-layer coding, enabling the destinations to decode packets based on their computing capabilities. However, coding parameters are statically chosen before data transmission, while using feedback or retransmission is impractical in rapidly changing network conditions. FNC is unadaptable to the available capabilities of nodes in a network and thus negatively impacts the coding performance. The main objective of this thesis is to design a versatile network coding scheme supporting heterogeneous communication networks that allow a node to adjust and adapt the coding process depending on the network condition and computing capabilities of the node. The research also focuses on reducing computational complexity in nodes while maintaining a high successful decoding probability and employing as simple operations as possible in intermediate nodes. Particularly, three main approaches are investigated in a source, intermediate, and destination node to achieve the objectives. First, the research examines both static and dynamic combinations of original packets in the encoding process by proposing dynamic sparsity and expansion packets (DSEP). This scheme significantly increases the coding throughput at both source and destination. Second, a new recoding scheme is proposed to manage the number of packets stored and recoded. Thus, this recoding scheme reduces memory usage and computing complexity at intermediate nodes, processing huge traffic. Finally, the research proposes adaptive decoding algorithms, which allow the destinations to choose the proper decoder depending on the network conditions. These algorithms improve the decoding probability in an unreliable network while reducing the computational complexity in a reliable network. For each proposed approach, both mathematical analysis and practical implementation were performed. Especially, the implementation leverages Kodo, a well-known network coding library for simulation and real-time implementation using during the last decade.:Abstract Acknowledgements List of Tables List of Figures Abbreviations and Symbols 1 Introduction 1.1 Fundamentals 1.2 Research motivation 1.3 Objectives 1.4 Methodology 1.5 Main contributions 1.5.1 Summary 1.5.2 List of publications 1.6 Thesis organization 2 Background and Related Work 2.1 RLNC and its variations 2.2 FNC: General principles and coding specification 2.2.1 General principles 2.2.2 Encoding specification 2.2.3 Decoding specification 2.3 Related work 2.4 Analysis of FNC performance 2.4.1 Preliminaries: MDS outer code property for theoretical analysis 2.4.2 Delay modelling: Number of required packet receptions for decoding 2.4.3 Decoding probability 2.4.4 Decoding probability for broadcast to heterogeneous destinations 2.4.5 Overhead 2.4.6 Throughput 2.5 Summary and discussion 3 Sparse Fulcrum Network Coding 3.1 Introduction 3.2 Encoding and decoding implementations 3.2.1 Encoding implementation 3.2.2 Decoding implementation 3.3 Integrating sparsity into FNC 3.3.1 Sparse inner and outer encoding 3.3.2 Sparse recoding and decoding 3.3.3 Evaluation setup 3.3.4 Throughput results 3.3.5 Decoding probability results 3.4 Summary 4 DSEP Fulcrum: Dynamic Expansion Packets and Sparsity 4.1 Introduction 4.2 Probability of linearly independent coded packets 4.3 Dynamic sparsity and expansion packets 4.3.1 Dynamic sparsity 4.3.2 Dynamic expansion packets 4.3.3 Sparsity level as a function of number of expansion packets and decoder rank 4.4 DSEP schemes 4.4.1 Example scheme: Dynamic sparsity with expansion packets region-based 4.4.2 Example scheme: Dynamic sparsity with expansion packets stepping up 4.5 Evaluation of DSEP schemes 4.5.1 Throughput results 4.5.2 Decoding probability results 4.5.3 Impact of feedback and packet losses 4.5.4 Energy consumption in IoT devices 4.6 Summary 5 Exploring Benefits of Recoding 5.1 Introduction 5.2 Recoding principle 5.3 Recoding scheme 5.3.1 General idea 5.3.2 An unlimited buffer recoding 5.3.3 A limited buffer recoding 5.4 Evaluation 5.4.1 Coding overhead 5.4.2 Recoding and decodinEvaluation.5 Summary 6 Adaptive Decoding for Fulcrum Codes 6.1 Introduction 6.2 Adaptive Fulcrum decoder 6.2.1 Motivating example 6.2.2 Adaptive Fulcrum decoding algorithm 6.3. Advanced adaptive Fulcrum decoder 6.3.1 Principles 6.3.2 Advanced adaptive Fulcrum decoding algorithm 6.4 Analysis 6.4.1 Decoding delay 6.4.2 Decoding probability 6.4.3 Overhead 6.5 Evaluation of adaptive Fulcrum decoding algorithms 6.5.1 Performance metrics 6.5.2 Evaluation results 6.6 Summary 7 Conclusion and Future Work 7.1 Summary and main contributions 7.2 Future work A Reed-Solomon Outer Code: Proof of Full Rank Property of Remapped Packets Bibliography

No description available.

"In this thesis, a transmission frequency rendezvous approach for secondary users deployed in decentralized dynamic spectrum access networks is proposed. Frequency rendezvous is a critical step in bootstrapping a wireless network that does not possess centralized control. Current techniques for enabling frequency rendezvous in decentralized dynamic spectrum access networks either require pre-existing infrastructure or use one of several simplifying assumptions regarding the architecture, such as the use of regularly spaced frequency channels for communications. Our proposed approach is designed to be operated in a strictly decentralized wireless networking environment, where no centralized control is present and the spectrum does not possess pre-defined channels. In our proposed rendezvous algorithm, the most important step is pilot tone detection and receiver query. In order to realize a shortest search time for the target receiver, an efficient scanning rule should be employed. In this thesis, three scanning rules are proposed and evaluated, namely: frequency sequence scanning, pilot tone strength scanning, and cluster scanning. To validate our result, we test our scanning rules with actual paging band spectrum measurements. Previous research on security of network coding focuses on the protection of data dissemination procedures and the detection of malicious activities such as pollusion attacks. The capabilities of network coding to detect other attacks has not been fully explored. In this thesis, a new mechanism based on physical layer network coding to detect wormhole attacks is proposed. When two signal sequences collide at the receiver, the difference between the two received sequences is determined by its distances to the senders. Therefore, by comparing the differences between the received sequences at two nodes, we can estimate the distance between them and detect those fake neighbor connections through wormholes. While the basic idea is clear, we design many schemes at both physical and network layers to turn the idea into a practical approach. Simulations using BPSK modulation at the physical layer show that the wireless nodes can effectively detect fake neighbor connections without the adoption of any special hardware on them."

Les systèmes de stockage actuels font face à une explosion des données à gérer. A l'échelle actuelle, il serait illusoire d'imaginer une unique entité centralisée capable de stocker et de restituer les données de tous ses utilisateurs. Bien que du point de vue de l'utilisateur, le système de stockage apparaît tel un unique interlocuteur, son architecture sous-jacente est nécessairement devenue distribuée. En d'autres termes, le stockage n'est plus assigné à un équipement centralisé, mais est maintenant distribué parmi de multiples entités de stockage indépendantes, connectées via un réseau. Par conséquent, la bande passante inhérente à ce réseau devient une ressource à prendre en compte dans le design d'un système de stockage distribué. En effet, la bande passante d'un système est intrinsèquement une ressource limitée, qui doit être convenablement gérée de manière à éviter toute congestion du système. Cette thèse se propose d'optimiser l'utilisation de la bande passante dans les systèmes de stockage distribués, en limitant l'impact du churn et des défaillances. L'objectif est double, le but est d'une part, de maximiser la bande passante disponible pour les échanges de données, et d'une autre part de réduire la consommation de bande passante inhérente aux opérations de maintenance. Pour ce faire, nous présentons trois contributions distinctes. La première contribution présente une architecture pair-à-pair hybride qui tient compte de la topologie bas-niveau du réseau, c'est à dire la présence de gateways entre les utilisateurs et le système. La seconde contribution propose un mécanisme de timeout adaptatif au niveau utilisateur, basé sur une approche Bayésienne. La troisième contribution décrit un protocole permettant la réparation efficace de données encodées via des codes à effacement. Enfin, cette thèse se conclut sur la possibilité d'utiliser des techniques d'alignement d'interférence, communément utilisées en communication numérique afin d’accroître l'efficacité des protocoles de réparation de données encodées. / Modern storage systems have to face the surge of the amount of data to handle. At the current scale, it would be an illusion to believe that a single centralized storage device is able to store and retrieve all its users' data. While from the user's viewpoint the storage system remains a single interlocutor, its underlying architecture has become necessarily distributed. In others words, storage is no longer assigned to a centralized storage equipment, but is now distributed between multiple independent storage devices, connected via a network. Therefore, when designing networked storage systems, bandwidth should now be taken into account as a critical resource. In fact, the bandwidth of a system is intrinsically a limited resource which should be handled with care to avoid congestion. The focus of this thesis is to optimize the available bandwidth of distributed storage systems, lowering the impact of churn and failures. The objective is twofold, on the one hand the purpose is to increase the available bandwidth for data exchanges and on the other hand, to decrease the amount of bandwidth consumed by maintenance. We present three distinct contributions in this manuscript. The first contribution of this thesis presents an hybrid peer-to-peer architecture taking into account the low level topology of the network i.e., the presence of gateways between the system and the users. The second contribution proposes an adaptive and user-level timeout mechanism, based on a Bayesian approach. The third contribution describes a repair protocol especially designed for erasure-coded stored data. Finally, this thesis concludes on the possibility of employing interference alignment techniques in order to increase the efficiency of repair protocols especially designed for encoded data.

Fréquemment exploités pour venir en complément aux réseaux mobiles traditionnels, les réseaux sans-fil multi-sauts, aussi appelés réseaux ad-hoc, sont particulièrement mis à profit dans le domaine des communications d'urgence du fait de leur capacité à s'affranchir de toute infrastructure. Néanmoins, la capacité de ces réseaux étant limitée dès lors que le nombre d'utilisateurs augmente, la communauté scientifique s'efforce à en redéfinir les contours afin d'étendre leur utilisation aux communications civiles. La gestion des interférences, considérée comme l'un des principaux défis à relever pour augmenter les débits atteignables dans les réseaux sans-fil multi-sauts, a notamment connu un changement de paradigme au cours des dernières années. Alors qu'historiquement cette gestion est régie par les protocoles de la couche d'accès dont l'objectif consiste à éviter les interférences entre utilisateurs, il est désormais possible, grâce à différentes techniques avancées de communication numérique, de traiter ces interférences, et même de les exploiter. Ces techniques de transmission, dites techniques de gestion des interférences, viennent alors concurrencer les mécanismes d'ordonnancement traditionnels en autorisant plusieurs transmissions simultanées et dans la même bande de fréquence vers un même récepteur. Dans cette thèse, nous nous intéressons à l'une de ces techniques, le Physical-Layer Network Coding (PLNC), en vue de son intégration dans des réseaux ad-hoc composés de plusieurs dizaines de nœuds. Les premiers travaux se concentrant principalement sur des petites topologies, nous avons tout d'abord développé un framework permettant d'évaluer les gains en débit à large échelle du PLNC par rapport à des transmissions traditionnelles sans interférence. Motivés par les résultats obtenus, nous avons ensuite défini un nouveau cadre d'utilisation à cette technique visant à élargir sa sphère d'application. Le schéma de PLNC proposé, testé à la fois sur de vrais équipements radio et par simulation, s'est alors révélé offrir des gains significatifs en débit et en fiabilité en comparaison aux solutions existantes.

Physical-Layer Network Coding (PNC) is a promising technique that has great potentials for improving the achievable data rates of end-to-end flows through higher packet transmission rates, thereby increasing the overall network throughput. In this thesis, we study the performance of the PNC transmission techniques for unidirectional end-to-end flows in multi-hop wireless networks, and compare it with that of the traditional transmission techniques. We first derive the bit-error rate (BER) that the PNC transmission technique achieves. Then, using the derived BER, we evaluate and quantify the achievable network throughput under both the PNC transmission technique and the traditional technique, where the network throughput is measured as the aggregate/sum of all end-to-end flows' achievable data rates in the wireless network. Using extensive simulations, we show that PNC increases the overall achievable end-to-end flow throughput in multi-hop wireless networks, especially under medium to high signal-to-noise ratios. / Graduation date: 2012

Demand for high data rates is increasing rapidly for the future wireless generations, due to the requirement ofubiquitous coverage for wireless broadband services. More base stations are needed to deliver these services, in order tocope with the increased capacity demand and inherent unreliable nature of wireless medium. However, this would directly correspond to high infrastructure costand energy consumption in cellular networks. Nowadays, high power consumption in the network is becoming a matter of concern for the operators,both from environmental and economic point of view. Cooperative communications, which is regarded as a virtual multi-input-multi-output (MIMO) channel, can be very efficient in combating fading multi-path channels and improve coverage with low complexity and cost. With its distributed structure, cooperativecommunications can also contribute to the energy efficiency of wireless systems and green radio communications of the future. Using networkcoding at the top of cooperative communication, utilizes the network resources more efficiently. Here we look at the case of large scale use of low cost relays as a way of making the links reliable, that directly corresponds to reductionin transmission power at the nodes. A lot of research work has focused on highlighting the gains achieved by using network codingin cooperative transmissions. However, there are certain areas that are not fully explored yet. For instance, the kind of detectionscheme used at the receiver and its impact on the link performance has not been addressed.The thesis looks at the performancecomparison of different detection schemes and also proposes how to group users at the relay to ensure mutual benefit for the cooperating users.Using constellation selection at the nodes, the augmented space formed at the receiver is exploited for making the links more reliable. Thenetwork and the channel coding schemes are represented as a single product code, that allows us to exploit the redundancy present in theseschemes efficiently and powerful coding schemes can also be designed to improve the link performance. Heterogeneous network deployments and adaptive power management has been used in order to reduce the overall energy consumption in acellular network. However, the distributed structure of nodes deployed in the network, is not exploited in this regard. Here we have highlightedthe significance of cooperative relaying schemes in reducing the overall energy consumption in a cellular network.  The role of differenttransmission and adaptive resource allocation strategies in downlink scenarios have been investigated in this regard.It has been observed that the adaptive relaying schemes can significantly reduce the total energy consumption as compared to the conventionalrelaying schemes. Moreover, network coding in these adaptive relaying schemes, helps in minimizing the energy consumption further.The balance between the number of base stations and the relays that minimizes the energy consumption, for each relaying scheme is also investigated. / QC 20120124

This thesis studies a two-way relay network (TWRN), which consists of two single antenna source nodes and a multi-antenna relay node. The source nodes exchange information via the assistance of the relay node in the middle. The relay scheme in this TWRN is amplify-and-forward (AF) based analog network coding (ANC). A robust beamforming matrix optimization algorithm is presented here with the objective to minimize the transmit power at the relay node under given signal to interference and noise ratio (SINR) requirements of source nodes. This problem is first formulated as a non-convex optimization problem, and it is next relaxed to a semi-definite programming (SDP) problem by utilizing the S-procedure and rank-one relaxation. This robust beamforming optimization algorithm is further validated in a MATLAB-based orthogonal frequency-division multiplexing (OFDM) MIMO two-way relay simulation system. To better investigate the performance of this beamforming algorithm in practical systems, synchronization issues such as standard timing offset (STO) and carrier frequency offset (CFO) are considered in simulation. The transmission channel is modeled as a frequency selective fading channel, and the source nodes utilize training symbols to perform minimum mean-square error (MMSE) channel estimation. BER curves under perfect and imperfect synchronization are presented to show the performance of TWRN with ANC. It is shown that the outage probability of robust beamforming algorithm is tightly related to the SINR requirements at the source nodes, and the outage probability increases significantly when the SINR requirements are high.

Recently, there has been a growing interest in improving the performance of the wireless relay networks through the use of Physical Layer Network Coding (PLNC) techniques. The physical layer network coding technique allows two terminals to transmit simultaneously to a relay node and decode the modulo-2 sum of the transmitted bits at the relay. This technique considerably improves performance over Digital Network Coding technique. In this thesis, we will present an algorithm for joint decoding of the modulo-2 sum of bits transmitted from two unsynchronized transmitters at the relay. We shall also address the problems that arise when boundaries of the signals do not align with each other and when the channel parameters are slowly varying and are unknown to the receiver at the relay node. Our approach will first jointly estimate the timing o sets and fading gains of both signals using a known pilot sequence sent by both transmitters in the beginning of the packet and then perform Maximum Likelihood detection of data using a state-based Viterbi decoding scheme that takes into account the timing o sets between the interfering signals. We shall present an algorithm for simultaneously tracking the amplitude and phase of slowly varying wireless channel that will work in conjunction our Maximum Likelihood detection algorithm. Finally, we shall provide extension of our receiver to support antenna diversity. Our results show that the proposed detection algorithm works reasonably well, even with the assumption of timing misalignment. We also demonstrate that the performance of the algorithm is not degraded by amplitude and/or phase mismatch between the users. We further show that the performance of the channel tracking algorithm is close to the ideal case i.e. when the channel estimates are perfectly known. Finally, we demonstrate the performance boost provided by the receiver antenna diversity.

Wireless networks increasingly utilize diverse spectral bands, which exhibit vast differences in transmission range, bandwidth and available airtime. While tremendous efforts have been devoted to enable efficient mobile access of single-band networks and increase their throughput, e.g., via network coding, such single-band solutions are unfortunately oblivious to the diversity and abundance of the available spectral bands. In this thesis, I present and evaluate novel schemes for mobile access and for throughput increase using network coding, schemes that are designed for diverse-band wireless networks, i.e., networks operating in multiple diverse bands. Specifically, I introduce the first scheme designed for mobile clients to evaluate and select both APs and spectral bands in diverse-band networks. The fundamental problem is that the potentially vast number of spectrum and AP options may render scanning prohibitive. Thus, my key technique is for clients to infer the critical metrics of channel quality and available airtime for their current location and bands using limited measurements collected in other bands and at other locations. I evaluate my scheme via experiments and emulations, which are enabled by a four-band testbed that I deploy. A key finding is that under a diverse set of operating conditions, mobile clients can accurately predict their performance without a direct measurement at their current location and spectral bands. Moreover, I introduce the first band selection schemes designed for diverse-band networks exploiting overheard packets to enable network coding. The main problem is that band selections in such networks are challenged by conflicting factors affecting throughput: while the number of overhearing nodes generally increases with decreasing frequency, channel width and spatial reuse unfortunately decrease. Thus, the key technique of the proposed schemes is to jointly incorporate coding gains, channel width and spatial reuse in band selections. I evaluate these schemes via simulations employing a physical-layer model driven by measurements collected using the deployed four-band testbed. An important finding is that the proposed schemes can outperform coding-oblivious spectrum access in terms of throughput, as their band selection enables more coding opportunities. My work has two key implications. First, it can significantly improve throughput performance in networks enabled by today’s unlicensed spectrum and by the billion-dollar industry of white-space networking. Second, I anticipate that this thesis will highly impact future research, as I open new research areas in a domain that has attracted such tremendous commercial and research interest.