No / Abstract: Error control techniques are designed to ensure reliable data transfer over unreliable communication channels that are frequently subjected to channel errors. In this paper, the effect of applying a convolution code to the Scattered Random Network Coding (SRNC) scheme over a multi-hop wireless channel was studied. An interleaver was implemented for bit scattering in the SRNC with the purpose of dividing the encoded data into protected blocks and vulnerable blocks to achieve error diversity in one modulation symbol while randomising errored bits in both blocks. By combining the interleaver with the convolution encoder, the network decoder in the receiver would have enough number of correctly received network coded blocks to perform the decoding process efficiently. Extensive simulations were carried out to study the performance of three systems: 1) SRNC with convolutional encoding, 2) SRNC; and 3) A system without convolutional encoding nor interleaving. Simulation results in terms of block error rate for a 2-hop wireless transmission scenario over an Additive White Gaussian Noise (AWGN) channel were presented. Results showed that the system with interleaving and convolutional code achieved better performance with coding gain of at least 1.29 dB and 2.08 dB on average when the block error rate is 0.01 when compared with system II and system III respectively.

Recently, there has been an increasing demand for reliable, robust and high data rate communication systems that can counteract the limitations imposed by the scarcity of two fundamental resources for communications: bandwidth and power. In turn, cooperative communications has emerged as a new communication paradigm in which network nodes share their antennas and transmission resources for distributed data exchange and processing. Recent studies have shown that cooperative communications can achieve significant performance gains in terms of signal reliability, coverage area, and power savings when compared with conventional communication schemes. However, the merits of cooperative communications can only be exploited with efficient resource allocation in terms of bandwidth utilization and power control. Additionally, the limited network resources in wireless environments can lead rational network nodes to be selfish and aim at maximizing their own benefits. Therefore, assuming fully cooperative behaviors such as unconditionally sharing of one's resources to relay for other nodes is unjustified. On the other hand, a particular network node may try to utilize resources from other nodes and also share its own resources so as to improve its own performance, which in turn may prompt other nodes to behave similarly and thus promote cooperation. This dissertation aims to answer the following three questions: ``How can bandwidth-efficient multinode cooperative communications be achieved?'', ``How can optimal power allocation be achieved in a distributed fashion?'', and finally, ``How can network nodes dynamically interact with each other so as to promote cooperation?''. In turn, this dissertation focuses on three main problems of cooperation in ad-hoc wireless networks: (i) optimal node selection in network-coded cooperative communications, (ii) auction-based distributed power allocation in single- and multi-relay cooperative networks, and finally (iii) coalitional game-theoretic analysis and modeling of the dynamic interactions among the network nodes and their coalition formations. Bi-directional relay networks are first studied in a scenario where two source nodes are communicating with each other via a set of intermediate relay nodes. The symbol error rate performance and achievable cooperative diversity orders are studied. Additionally, the effect of timing synchronization errors on the symbol error rate performance is investigated. Moreover, a sum-of-rates maximizing optimal power allocation is proposed. Relay selection is also proposed to improve the total achievable rate and mitigate the effect of timing synchronization errors. Multinode cooperative communications are then studied through the novel concept of many-to-many space-time network coding. The symbol error rate performance under perfect and imperfect timing synchronization and channel state information is theoretically analyzed and the optimal power allocation that maximizes the total network rate is derived. Optimal node selection is also proposed to fully exploit cooperative diversity and mitigate timing offsets and channel estimation errors. Further, this dissertation investigates distributed power allocation for single-relay cooperative networks. The distributed power allocation algorithm is conceived as an ascending-clock auction where multiple source nodes submit their power demands based on an announced relay price and are efficiently allocated cooperative transmit power. It is analytically and numerically shown that the proposed ascending-clock auction-based distributed algorithm leads to efficient power allocation, enforces truth-telling, and maximizes the social welfare. A distributed ascending-clock auction-based power allocation algorithm is also proposed for multi-relay cooperative networks. The proposed algorithm is shown to converge to the unique Walrasian Equilibrium allocation which maximizes the social welfare when source nodes truthfully report their cooperative power demands. The proposed algorithm achieves the same performance as could be achieved by centralized control while eliminating the need for complete channel state information and signaling overheads. Finally, the last part of the dissertation studies altruistic coalition formation and stability in cooperative wireless networks. Specifically, the aim is to study the interaction between network nodes and design a distributed coalition formation algorithm so as to promote cooperation while accounting for cooperation costs. This involves an analysis of coalitions' merge-and-split processes as well as the impact of different cooperative power allocation criteria and mobility on coalition formation and stability. A comparison with centralized power allocation and coalition formation is also considered, where the proposed distributed algorithm is shown to provide reasonable tradeoff between network sum-rate and computational complexity. / Ph. D.

Unmanned aerial vehicle (UAV) networks, a flying platform, are a promising wireless communications infrastructure with wide-ranging applications in both commercial and military domain. Owing to the appealing characteristics, such as high mobility, high feasibility, and low cost, UAV networks can be applied in various scenarios, such as emergency communications, cellular networks, device-to-device (D2D) networks, and sensor networks, regardless of infrastructure and spatial constraints. To handle complicated missions, provide wireless coverage for a large range, and have a long lifetime, a UAV network may consist of a large amount of UAVs, working cooperatively as a swarm, also referred to as swarm UAV networks. Although high mobility and numerous UAVs offer high flexibility, high scalability, and performance enhancement for swarm UAV networks, they also incur some technical challenges. One of the major challenges is the routing protocol design. With high mobility, a dynamic network topology may be encountered. As a result, traditional routing protocols based on routing path discovery are not applicable in swarm UAV networks, as the discovered routing path may be outdated especially when the amount of UAVs is large causing considerable routing path discovery delay. Multicast is an essential and key technology in the scenarios, where swarm UAV networks are employed as aerial small base station (BSs), like relay or micro BS. Swarm UAV networks consisting of a large amount of UAVs will encounter severe multicast delay with existing multicast methods using acknowledgement (ACK) feedback and retransmissions. This issue will be deteriorated when a swarm UAV network is deployed far away from BSs, causing high packet loss. Data exchange is another major technical challenge in swarm UAV networks, where UAVs exchange data packets with each other, such as requesting and retrieving lost packets. Due to numerous UAVs, data exchange between UAVs can cause message and signaling storm, resulting in a long data exchange delay and severe ovehead. In this dissertation, I focus on developing novel routing protocols, multicast schemes, and data exchange schemes, enabling efficient, robust, and high-performance routing, multicast, and data exchange in swarm UAV networks. To be specific, two novel flooding-based routing protocols are designed in this dissertation, where random network coding (RNC) is utilized to improve the efficiency of the flooding-based routing in swarm UAV networks without relying on network topology information and routing path discovery. Using the property of RNC that as long as sufficient different versions of encoded packets/generations are accumulated, original packets could be decoded, RNC is naturally able to accelerate the routing process. This is because the use of RNC can reduce the number of encoded packets that are required to be delivered in some hop. In a hop, the receiver UAV may have already overheard some generations in previous hops, so that it only needs to receive fewer generations from the transmitter UAV in the current hop. To further expedite the flooding-based routing, the second flooding-based routing protocol is designed, where each forwarding UAV creates a new version of generation by linearly combining received generations rather than by decode original packets. Despite the flooding-based routing significantly hastened by RNC, the inherent drawback of the flooding-based routing is still unsolved, namely numerous hops. Aiming at reducing the amount of hops, a novel enhanced flooding-based routing protocol leveraging clustering is designed, where the whole UAV network will be partitioned into multiple clusters and in each cluster only one UAV will be selected as the representative of this cluster, participating in the flooding-based routing process. By this way, the number of hops is restricted by the number of representatives, since packets are only flooded between limited representatives rather than numerous UAVs. To address the multicast issue in swarm UAV networks, a novel multicast scheme is proposed based on clustering, where a UAV experiencing packet loss will retrieve the lost packets by requesting other UAVs in the same cluster without depending on retransmissions of BSs. In this way, the lost packet retrieval is carried out through short-distance data exchange between UAVs with reliable transmissions and a short delay. Tractable stochastic geometry tools are used to model swarm UAV networks with a dynamic network topology, based on which comprehensive analytical performance analysis is given. To enable efficient data exchange between UAVs in swarm UAV networks, a data exchange scheme is proposed utilizing unsupervised learning. With the proposed scheme, all UAVs are assigned to multiple clusters and a UAV can only carry out data exchange within its cluster. By this way, UAVs in different clusters perform data exchange in a parallel fashion to expedite data exchange. The agglomerative hierarchical clustering, a type of unsupervised learning, is used to conduct clustering in order to guarantee that UAVs in the same cluster are able to supply and supplement each other's lost packets. Additionally, a data exchange mechanism, including a novel random backoff procedure, is designed, where the priorities of UAVs in data exchange determined by the number of their lost packets or requested packets that they can provide. As a result, each request-reply process would be taken fully advantage, maximally supplying lost packets not only to the UAV sending request, but also to other UAVs in the same cluster. For all the developed technologies in this dissertation, their technical details and the corresponding system procedures are designed based on low-complexity and well-developed technologies, such as the carrier sense multiple access/collision avoidance (CSMA/CA), for practicability in practice and without loss of generality. Moreover, extensive simulation studies are conducted to demonstrate the effectiveness and superiority of the proposed and developed technologies. Additionally, system design insights are also explored and revealed through simulations. / Doctor of Philosophy / Compared to fixed infrastructures in wireless communications, unmanned aerial vehicle (UAV) networks possess some significant advantages, such as low cost, high mobility, and high feasibility, making UAV networks have a wide range of applications in both military and commercial fields. However, some characteristics of UAV networks, including dynamic network topology and numerous UAVs, may become technical barriers for wireless communications. One of the major challenges is the routing protocol design. Routing is the process of selecting a routing path, enabling data delivered from a node (source) to another desired node (destination). Traditionally, routing is performed based on routing path discovery, where control packets are broadcasted and the path, on which a control packet first reaches the destination, will be selected as routing path. However, in UAV networks, routing path discovery may experience a long delay, as control packets go through many UAVs. Besides, the discovered routing path may be outdated, as the topology of UAV networks change over time. Another key technology in wireless communications that may not work well in UAV networks is multicast, where a transmitter, like a base station (BS), broadcasts data to UAVs and all UAVs are required to receive this data. With numerous UAVs, multicast delay may be severe, since the transmitter will keep retransmitting a data packet to UAVs until all UAVs successfully receive the packet. This issue will be deteriorated when a UAV network is deployed far away from BSs, causing high packet loss. Data exchange between UAVs is a fundamental and important system procedure in UAV networks. A large amount of UAV in a UAV network will cause serious data exchange delay, as many UAVs have to compete for limited wireless resources to request or send data. In this dissertation, I focus on developing novel technologies and schemes for swarm UAV networks, where a large amount of UAVs exist to make UAV networks powerful and handle complicated missions, enable efficient, robust, and high-performance routing, multicast, and data exchange system procedures. To be specific, two novel flooding-based routing protocols are designed, where random network coding (RNC) is utilized to improve the efficiency of flooding-based routing without relying on any network topology information or routing path discovery. The use of RNC could naturally expedite flooding-based routing process. With RNC, a receiver can decode original packets as long as it accumulates sufficient encoded packets, which may be sent by different transmitters in different hops. As a result, in some hops, fewer generations may be required to be transmitted, as receivers have already received and accumulated some encoded in previous hops. To further improve the efficiency of flooding-based routing, another routing protocol using RNC is designed, where UAVs create new encoded packets by linearly combining received encoded packets rather than linearly combing original packets. Apparently, this method would be more efficient. UAVs do not need to collect sufficient encoded packets and decode original packets, while only linearly combining all received encoded packets. Although RNC could effectively improve the efficiency of flooding-based routing, the inherent drawback is still unsolved, which is a large amount of hops caused by numerous UAVs. Thus, an enhanced flooding-based routing protocol using clustering is designed, where the whole UAV network will be partitioned into multiple clusters. In each cluster only one UAV will be selected as the representative of this cluster, participating in the flooding-based routing process. By this way, the number of hops could be greatly reduced, as packets are only flooded between limited representatives rather than numerous UAVs. To address the multicast issue in swarm UAV networks, a novel multicast scheme is proposed, where a UAV experiencing packet loss will retrieve its lost packets by requesting other UAVs in the same cluster without depending on retransmissions of BSs. In this way, the lost packet retrieval is carried out through short-distance data exchange between UAVs with reliable transmissions and a short delay. Then, the optimal number of clusters and the performance of the proposed multicast scheme are investigated by tractable stochastic geometry tools. If all UAVs closely stay together in a swarm UAV network, long data exchange delay would be significant technical issue, since UAVs will cause considerable interference to each other and all UAVs will compete for spectrum access. To cope with that, a data exchange scheme is proposed leveraging unsupervised learning. To avoid interference between UAVs and a long-time waiting for spectrum access, all UAVs are assigned to multiple clusters and different clusters use different frequency bands to carry out data exchange simultaneously. The agglomerative hierarchical clustering, a type of unsupervised learning, is used to conduct clustering, guaranteeing that UAVs in the same cluster are able to supply and supplement each other's lost packets. Additionally, a data exchange mechanism is designed, facilitating that a UAV with more lost packets or more requested packets has a higher priority to carry out data exchange. In this way, each request-reply process would be taken fully advantage, maximally supplying lost packets not only to the UAV sending request, but also to other UAVs in the same cluster. For all the developed technologies in this dissertation, their technical details and the corresponding system procedures are designed based on low-complexity and well-developed technologies, such as the carrier sense multiple access/collision avoidance (CSMA/CA), for practicability in reality and without loss of generality. Moreover, extensive simulation studies are conducted to demonstrate the effectiveness and superiority of the developed technologies. Additionally, system design insights are also explored and revealed through simulations.

The development of Unmanned Aerial Vehicles (UAVs) and fifth-generation (5G) wireless technology provides more possibilities for wireless networks. The application of UAVs is gradually evolving from individual UAVs performing tasks to UAV swarm performing tasks in concert. A UAV swarm network is when many drones work cooperatively in a swarm mode to achieve a particular goal. Due to the UAV swarm's easy deployment, self-organization, self-management, and high flexibility, it can provide robust and efficient wireless communications in some unique scenarios, such as emergency communications, hotspot region coverage, sensor networks, and vehicular networks. Therefore, UAV networks have attracted more and more attention from commercial and military; however, many problems need to be resolved before UAV cellular communications become a reality. One of the most challenging core components is the routing protocol design in the UAV swarm network. Due to the high mobility of UAVs, the position of each UAV changes dynamically, so problems such as high latency, high packet loss rate, and even loss of connection arise when UAVs are far apart. These problems dramatically reduce the transmission rate and data integrity for traditional routing protocols based on path discovery. This thesis focuses on developing, emulating, and optimizing a flooding-based routing protocol for UAV swarm using Random Linear Network Coding (RLNC) to improve the latency and bit rate and solve the packet loss problem without routing information and network topology. RLNC can reduce the number of packets demand in some hops. Due to this feature of RLNC, when relay transmitter UAVs or the destination receiver UAV receive sufficient encoded packets from any transmitter UAVs, the raw data can be decoded. For those relay transmitter UAVs in the UAV swarm network that already received some encoded packets in previous hops but not enough to decode the raw data, only need to receive the rest of the different encoded packets needed for decoding. Thus, flooding-based routing protocol significantly improves transmission efficiency in the UAV swarm network. / Master of Science / People are used to using fiber, 4G, and Wi-Fi in the city, but numerous people still live in areas without Internet access. Moreover, in some particular scenarios like large-scale activities, remote areas, and military operations, when the cellular network cannot provide enough bandwidth or good signal, UAV wireless network would be helpful and provide stable Internet access. Successful UAV test flights can last for several weeks, and researchers' interest in high-altitude long-endurance (HALE) UAVs are booming. HALE UAVs will create Wi-Fi or other network signals for remote areas, including polar regions, which will allow millions of people to enter the information society and connect to the Internet. The development of UAV and 5G provides more possibilities for wireless networks. UAV applications have evolved from individual UAV performing tasks to UAV swarm performing tasks. A UAV swarm network is where multiple drones work in tandem to achieve a particular goal. It can provide robust and efficient wireless communications in unique scenarios. As a result, UAVs are receiving attention from both commercial and military. However, there are still many problems that need to be resolved before the actual use of UAVs. One of the biggest challenges is routing protocol which is how UAVs communicate with each other and select routes. As the location of UAVs is constantly changing, this leads to delays, data loss, or complete loss of connectivity. Ultimately these issues can lead to slow transmission speed and lack of data integrity for traditional routing protocols based on path discovery. This thesis focuses on developing, emulating, and optimizing a flooding-based routing protocol for the UAV swarm. Specifically, this protocol uses RLNC, which can reduce the number of packets demand in some hops so that the latency and transmission speed will be improved, and the data loss problem will also be solved. Due to this feature of RLNC, when any receiver receives enough encoded packets from any transmitter, the original data can be decoded. Some receivers that already received some encoded packets in the previous transmission only need to receive the rest of the different encoded packets needed for decoding. Therefore, flooding-based routing protocol significantly improves transmission efficiency for UAV swarm networks.

The following thesis consists of two main contributions to the fields of network coding and resource allocation. The first is a quantitative analysis of the effects of channel estimation errors and time synchronization errors on the performance of different network coding algorithms. It is shown that the performance improvement gained by a relay-based network scheme is significant for small number of users and when the quality of the relay link is better than that of the direct link. However, it is shown that potential performance improvement resulting from the considered relay-based network coding scheme could be negated by channel estimation errors. To consider the effects of time synchronization errors, we study a digital network coding (DNC) system and a physical-layer network coding (PNC) system with non-coherent frequency shift keying (FSK) modulation. For each of these two systems, we investigate the effects of received Eb/N0, unequal link quality, and time synchronization errors. The second contribution is an analysis of the value and cost of cognition obtained by investigating three resource allocation algorithms with different levels of channel knowledge in the context of ad hoc networks. The performance (quantified in terms of "percentage of users reaching target data rate" and "average effective data rate") and cost ("power consumption" and "number of channel estimations") of these algorithms are analyzed. Results show that a resource allocation algorithm with a higher level of channel knowledge results in better performance, but greater cost in terms of number of channel estimations, as expected. In addition, a resource allocation algorithm with a higher level of channel knowledge converges quicker when channel adaptation are necessary. Both an ideal medium access control (MAC) protocol and a non-ideal MAC protocol (dedicated control channel) are considered. / Master of Science

Spatial diversity, in the form of employing multiple antennas (i.e., MIMO), has proved to be very effective in increasing network capacity and reliability. However, equipping a wireless node with multiple antennas may not be practical, as the footprint of multiple antennas may not fit on a wireless node (particularly on handheld wireless devices). In order to achieve spatial diversity without requiring multiple antennas on the same node, the so-called cooperative communications (CC) has been introduced. Under CC, each node is equipped with only a single antenna and spatial diversity is achieved by exploiting the antennas on other nodes in the network through cooperative relaying. The goal of this dissertation is to maximize throughput at network level through CC at the physical layer. A number of problems are explored in this investigation. The main contributions of this dissertation can be summarized as follows. <b>1. Optimal Relay Assignment.</b> We first consider a simple CC model where each source-destination pair may employ only a single relay. For this three-node model, the choice of a relay node (among a set of available relay nodes) for a given session is critical in the overall network performance. We study the relay node assignment problem in a cooperative ad hoc network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. Our objective is to assign the available relay nodes to different source-destination pairs so as to maximize the minimum data rate among all pairs. We present an optimal polynomial time algorithm, called ORA, that solves this problem. A novel idea in this algorithm is a "linear marking" mechanism, which maintains linear complexity at each iteration. We offer a formal proof of optimality for ORA and use numerical results to demonstrate its capability. <b>2. Incorporating Network Coding.</b> It has been shown that network coding (NC) can reduce the time-slot overhead when multiple session share the same relay node in CC. Such an approach is called network-coded CC (or NC-CC). Most of the existing works have mainly focused on the benefits of this approach. The potential adverse effect under NC-CC remains unknown. We explore this important problem by introducing the concept of network coding noise (NC noise). We show that due to NC noise, NC may not be always beneficial to CC. We substantiate this important finding in two important scenarios: analog network coding (ANC) in amplify-and-forward (AF) CC, and digital network coding (DNC) in decode-and-forward (DF) CC. We analyze the origin of NC noise via a careful study of signal aggregation at a relay node and signal extraction at a destination node. We derive a closed-form expression for NC noise at each destination node and show that the existence of NC noise could diminish the advantage of NC in CC. Our results shed new light on how to use NC in CC effectively. <b>3. Session Grouping and Relay Node Selection.</b> When there are multiple sessions in the network, it may be necessary to combine sessions into different groups, and then have each group select the most beneficial relay node for NC-CC. We study this joint grouping and relay node selection problem for NC-CC. By studying matching problems in hypergraphs, we show that this problem is NP-hard. We then propose a distributed and online algorithm to solve this problem. The key idea in our algorithm is to have each neighboring relay node of a newly joined session determine and offer the best group for this session from the groups that it is currently serving; and then to have the source node of this newly joined session select the best group among all received offers. We show that our distributed algorithm has polynomial complexity. Using extensive numerical results, we show that our distributed algorithm is near-optimal and adapts well to online network dynamics. <b>4. Grouping and Matching for Multi-Relay Cooperation.</b> Existing models of NC-CC consider only single relay node for each session group. We investigate how NC-CC behaves when multiple relay nodes are employed. For a given session, we develop closed form formulas for the mutual information and achievable rate under multi-relay NC-CC. In multi-relay NC-CC, the achievable rate of a session depends on the other sessions in its group as well as the set of relay nodes used for NC-CC. Therefore, we study NC-CC via joint optimization of grouping and matching of session and relay groups in an ad hoc network. Although we show that the joint problem is NP-hard, we develop an efficient polynomial time algorithm for grouping and matching (called G²M). G²M first builds beneficial relay groups for individual sessions. This is followed by multiple iterations during which sessions are combined with other sessions to form larger and better session groups (while corresponding relay groups are merged and updated accordingly). Using extensive numerical results, we show the efficiency and near optimality of our G²M algorithm. / Ph. D.

There has recently been growing interest in using physical layer network coding techniques to facilitate information transfer in wireless relay networks. The physical layer network coding technique takes advantage of the additive nature of wireless signals by allowing two terminals to transmit simultaneously to the relay node. This technique has several performance benefits, such as improving utilization and throughput of wireless channels and reducing delay. In this thesis, we present an algorithm for joint decoding of two unsynchronized transmitters to a modulo-2 sum of their transmitted messages. We address the problems that arise when the boundaries of the signals do not align with each other and when their phases are not identical. Our approach uses a state-based Viterbi decoding scheme that takes into account the timing offsets between the interfering signals. As a future research plan, we plan to utilize software-defined radios (SDRs) as a testbed to show the practicality of our approach and to verify its performance. Our simulation studies show that the decoder performs well with the only degrading factor being the noise level in the channel.

The network coding is a new paradigm that has been shown to improve throughput, fault tolerance, and other quality of service parameters in communication networks. The basic idea of the network coding techniques is to relish the "mixing" nature of the information flows, i.e., many algebraic operations (e.g., addition, subtraction etc.) can be performed over the data packets. Whereas traditionally information flows are treated as physical commodities (e.g., cars) over which algebraic operations can not be performed. In this dissertation we answer some of the important open questions related to the network coding. Our work can be divided into four major parts. Firstly, we focus on network code design for the dynamic networks, i.e., the networks with frequently changing topologies and frequently changing sets of users. Examples of such dynamic networks are content distribution networks, peer-to-peer networks, and mobile wireless networks. A change in the network might result in infeasibility of the previously assigned feasible network code, i.e., all the users might not be able to receive their demands. The central problem in the design of a feasible network code is to assign local encoding coefficients for each pair of links in a way that allows every user to decode the required packets. We analyze the problem of maintaining the feasibility of a network code, and provide bounds on the number of modifications required under dynamic settings. We also present distributed algorithms for the network code design, and propose a new path-based assignment of encoding coefficients to construct a feasible network code. Secondly, we investigate the network coding problems in wireless networks. It has been shown that network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks each packet transmitted by a device is broadcasted within a certain area and can be overheard by the neighboring devices. When a device needs to transmit packets, it employs the Index Coding that uses the knowledge of what the device's neighbors have heard in order to reduce the number of transmissions. With the Index Coding, each transmitted packet can be a linear combination of the original packets. The Index Coding problem has been proven to be NP-hard, and NP-hard to approximate. We propose an efficient exact, and several heuristic solutions for the Index Coding problem. Noting that the Index Coding problem is NP-hard to approximate, we look at it from a novel perspective and define the Complementary Index Coding problem, where the objective is to maximize the number of transmissions that are saved by employing coding compared to the solution that does not involve coding. We prove that the Complementary Index Coding problem can be approximated in several cases of practical importance. We investigate both the multiple unicast and multiple multicast scenarios for the Complementary Index Coding problem for computational complexity, and provide polynomial time approximation algorithms. Thirdly, we consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to-peer, or massive storage network. Parts of the data can be stored in either original form, or encoded form at multiple network locations. Clients access the parts of the data through simultaneous downloads from several servers across the network. For each link used client has to pay some cost. A client might not be able to access a subset of servers simultaneously due to network restrictions e.g., congestion etc. Furthermore, a subset of the servers might contain correlated data, and accessing such a subset might not increase amount of information at the client. We present a novel efficient polynomial-time solution for this problem that leverages the matroid theory. Fourthly, we explore applications of the network coding for congestion mitigation and over flow avoidance in the global routing stage of Very Large Scale Integration (VLSI) physical design. Smaller and smarter devices have resulted in a significant increase in the density of on-chip components, which has given rise to congestion and over flow as critical issues in on-chip networks. We present novel techniques and algorithms for reducing congestion and minimizing over flows.

Optimising the throughput performance for wireless networks is one of the challenging tasks in the objectives of communication engineering, since wireless channels are prone to errors due to path losses, random noise, and fading phenomena. The transmission errors will be worse in a multihop scenario due to its accumulative effects. Network Coding (NC) is an elegant technique to improve the throughput performance of a communication network. There is the fact that the bit error rates over one modulation symbol of 16- and higher order- Quadrature Amplitude Modulation (QAM) scheme follow a certain pattern. The Scattered Random Network Coding (SRNC) system was proposed in the literature to exploit the error pattern of 16-QAM by using bit-scattering to improve the throughput of multihop network to which is being applied the Random Linear Network Coding (RLNC). This thesis aims to improve further the SRNC system by using Forward Error Correction (FEC) code; the proposed system is called Joint RLNC and FEC with interleaving. The first proposed system (System-I) uses Convolutional Code (CC) FEC. The performances analysis of System-I with various CC rates of 1/2, 1/3, 1/4, 1/6, and 1/8 was carried out using the developed simulation tools in MATLAB and compared to two benchmark systems: SRNC system (System-II) and RLNC system (System- III). The second proposed system (System-IV) uses Reed-Solomon (RS) FEC code. Performance evaluation of System IV was carried out and compared to three systems; System-I with 1/2 CC rate, System-II, and System-III. All simulations were carried out over three possible channel environments: 1) AWGN channel, 2) a Rayleigh fading channel, and 3) a Rician fading channel, where both fading channels are in series with the AWGN channel. The simulation results show that the proposed system improves the SRNC system. How much improvement gain can be achieved depends on the FEC type used and the channel environment.

Network data rates are growing rapidly. The data rates provided to the customers by their network providers vary from Mbps to Gbps. However, rarely do users get the promised peak throughput. In cellular networks, network conditions change based on obstacles, weather conditions between the client and the base stations, and even the movement of objects and people. As a result of the changes in the radio link, the data transfer rate can change rapidly, hence devices needs to adjust their communications based on the currently available data rate. The Transmission Control Protocol (TCP) is widely used for reliable data transfer over networks. However, TCP was initially designed when link data rates were much lower than the link data rates commonly available today. As a result, TCP does not perform well at high data rates, despite some of the changes that have been made to the protocol to support high data rate links. Moreover, TCP has problems adapting to large changes in link bandwidth (not caused by congestion), resulting in a lower average throughput than the link could potentially deliver. This thesis evaluates two different versions of the TCP protocol (e.g., TCP Reno and Cubic TCP) and proposes a network coding scheme to enhance users’ experience when communicating over unstable radio links. The performance of the two TCP protocols and Random Linear Network Coding (RLNC) scheme were measured in an emulated network environment. The results of these measurements were analyzed and evaluated. The analysis shows that RLNC can provide a higher throughput than TCP over a network with high packet loss. However, RLNC is a UDP based solution and does not implement congestion control algorithms or reliability. A new solution is proposed that increases reliability and implements network adaptation in RLNC solutions. The results obtained in this thesis can be used to develop a new protocol to increases the quality of users’ experience in high loss networks. / Datahastigheter över nätverk ökar drastiskt. Datahastigheterna som ges tillgängliga till användare av deras respektive dataleverantör kan variera från Mbit/s till Gbit/s. Det är dock inte ofta användare får ut vad som har lovats. I mobila nätverk kan nätverkets tillstånd ändras baserat på hinder, väderleksförhållanden mellan en klient och basstationerna, till och med beroende på förflyttning av objekt eller människor. På grund av detta så behöver användares utrustning anpassa dess kommunikation, baserat på den för närvarande tillgängliga datahastigheten. Transmission Control Protocol (TCP) används i stor utsträckning vid behovet av tillförlitlig dataöverföring över nätverk. Däremot så designades TCP när länkdatahastigheterna var mycket lägre än vad som är vanligen tillgängligt idag. På grund av detta så presterar inte TCP över höga datahastigheter, trots ändringar som har gjorts i protokollet för att stödja höghastighets datalänkar. Utöver det så har TCP svårt att anpassa sig efter stora ändringar i länkens bandbredd (som inte är orsakat av stockning), som resulterar i en mindre genomsnitts-dataström än vad länken potentiellt hade kunnat ge. Detta examensarbete utvärderar två olika versioner av TCP (e.g., TCP Reno och Cubic TCP) och föreslår ett sätt att använda network coding för att öka användares upplevelse vid dataöverföring över instabila radio länkar. Prestationerna av de två TCP versionerna och Random Linear Network Coding (RLNC) metoden har blivit mätt i en emulerad nätverksmiljö. Resultaten från dessa mätningar blev analyserade och utvärderade. Analysen visar att RLNC kan ge en högre dataström än TCP över ett nätverk med hög risk för paketförluster. Däremot så är RLNC en User Datagram Protocol (UDP) baserad lösning, och därav inte implementerar trängselkontrolls-algoritmer eller tillförlitlighet. Ett förslag till en ny lösning som ökar tillförlitlighet och implementerar nätverksanpassning till RLNC lösningar har presenterats. Resultaten från detta examensarbete kan användas till att utveckla nya protokoll för att öka kvalitén av användares upplevelse i nätverk med risk för hög paketförlust.