In this thesis, as an extension to [1], we propose a prioritized multi-layer network coding scheme for collaborative packet recovery in hybrid (interweave and underlay) cellular cognitive radio networks. This scheme allows the uncoordinated collaboration between the collocated primary and cognitive radio base-stations in order to minimize their own as well as each other’s packet recovery overheads, thus by improving their throughput. The proposed scheme ensures that each network’s performance is not degraded by its help to the other network. Moreover, it guarantees that the primary network’s interference threshold is not violated in the same and adjacent cells. Yet, the scheme allows the reduction of the recovery overhead in the collocated primary and cognitive radio networks. The reduction in the cognitive radio network is further amplified due to the perfect detection of spectrum holes which allows the cognitive radio base station to transmit at higher power without fear of violating the interference threshold of the primary network. For the secondary network, simulation results show reductions of 20% and 34% in the packet recovery overhead, compared to the non-collaborative scheme, for low and high probabilities of primary packet arrivals, respectively. For the primary network, this reduction was found to be 12%. Furthermore, with the use of fractional cooperation, the average recovery overhead is further reduced by around 5% for the primary network and around 10% for the secondary network when a high fractional cooperation probability is used.

Recent studies show that network coding improves multicast session throughput. In this thesis, we demonstrate how random linear network coding can be incorporated to provide security and network diagnosis for peer-to-peer systems. First, we seek to design a security scheme for network coding architectures which are highly susceptible to jamming attacks. We evaluate Null Keys, a novel and computationally efficient security algorithm, by studying its application in real-world topologies. Null Keys is a cooperative security based on the subspace properties of network coding. We then present a new trace collection protocol that allows operators to diagnose peer-to-peer networks. Existing solutions are not scalable and fail to collect measurements from departed peers. We use progressive random linear network coding to disseminate the traces in the network, from which the server pulls data in a delayed fashion. We leverage the power of progressive encoding to increase block diversity and tolerate block losses.

Information raining has been shown to address the problem of delivering Internet access to high-speed rail passengers. However, a wireline repeater or heterogeneous wireless relay design complicates implementation. Recent developments in extending mobile multihop relaying to the IEEE 802.16e standard have made it feasible to deploy an information raining using a common radio and physical layer. Two automatic repeat request techniques and two network coding techniques are proposed. An upper and lower bound on delay is established for a single fully network coded relay system operating in static signal to noise ratio conditions. Simulations involving a physical layer model demonstrate that network coding schemes can attain the maximum downlink capacity.

Information raining has been shown to address the problem of delivering Internet access to high-speed rail passengers. However, a wireline repeater or heterogeneous wireless relay design complicates implementation. Recent developments in extending mobile multihop relaying to the IEEE 802.16e standard have made it feasible to deploy an information raining using a common radio and physical layer. Two automatic repeat request techniques and two network coding techniques are proposed. An upper and lower bound on delay is established for a single fully network coded relay system operating in static signal to noise ratio conditions. Simulations involving a physical layer model demonstrate that network coding schemes can attain the maximum downlink capacity.

Recent studies show that network coding improves multicast session throughput. In this thesis, we demonstrate how random linear network coding can be incorporated to provide security and network diagnosis for peer-to-peer systems. First, we seek to design a security scheme for network coding architectures which are highly susceptible to jamming attacks. We evaluate Null Keys, a novel and computationally efficient security algorithm, by studying its application in real-world topologies. Null Keys is a cooperative security based on the subspace properties of network coding. We then present a new trace collection protocol that allows operators to diagnose peer-to-peer networks. Existing solutions are not scalable and fail to collect measurements from departed peers. We use progressive random linear network coding to disseminate the traces in the network, from which the server pulls data in a delayed fashion. We leverage the power of progressive encoding to increase block diversity and tolerate block losses.

When intermediate nodes encode messages in wireless network coding, a question arises: Which modulation scheme should be used to broadcast the encoded message? Should it be limited to a receiver with a low modulation-level requirement to maintain an acceptable BER or should it be broadcasted at the desired modulation-level of a receiver with a higher rate requirement? Such conflicting requirements typically arise when one receiver has a low channel capacity while the other has a higher one. Recently, the deployment of network coding in wireless networks has attracted significant research attention, mainly due to the capability of network coding to improve throughput and save energy. However, a challenging problem in wireless network coding is to determine which modulation scheme to employ in the broadcast phase when receivers have diverse modulation scheme requirements, e.g., Node A may desire an 8-PSK modulation scheme on the broadcasted signal, while Node B may require a QPSK on the same broadcasted signal. In this thesis, we introduce a new coding scheme aimed at solving the diverse modulation problem. The scheme is based on coding information such that a receiver with a high modulation-level requirement can decode more information from a broadcasted signal than a receiver with a low one. Several codes have been designed for various combinations of modulation schemes. Analytical studies have been carried out to quantify the performance of the proposed scheme. Extensive simulations have been conducted to demonstrate the performance of the proposed scheme and validate the accuracy of our analytic model.

When intermediate nodes encode messages in wireless network coding, a question arises: Which modulation scheme should be used to broadcast the encoded message? Should it be limited to a receiver with a low modulation-level requirement to maintain an acceptable BER or should it be broadcasted at the desired modulation-level of a receiver with a higher rate requirement? Such conflicting requirements typically arise when one receiver has a low channel capacity while the other has a higher one. Recently, the deployment of network coding in wireless networks has attracted significant research attention, mainly due to the capability of network coding to improve throughput and save energy. However, a challenging problem in wireless network coding is to determine which modulation scheme to employ in the broadcast phase when receivers have diverse modulation scheme requirements, e.g., Node A may desire an 8-PSK modulation scheme on the broadcasted signal, while Node B may require a QPSK on the same broadcasted signal. In this thesis, we introduce a new coding scheme aimed at solving the diverse modulation problem. The scheme is based on coding information such that a receiver with a high modulation-level requirement can decode more information from a broadcasted signal than a receiver with a low one. Several codes have been designed for various combinations of modulation schemes. Analytical studies have been carried out to quantify the performance of the proposed scheme. Extensive simulations have been conducted to demonstrate the performance of the proposed scheme and validate the accuracy of our analytic model.

Since its introduction in the year 2000 by Ahlswede et al., the network coding paradigm has revolutionized the way we understand information flows in networks. Traditionally, information transmitted in a communication network was treated as a commodity in a transportation network, much like cars on highways or fluids in pipes. This approach, however, fails to capture the very nature of information, which in contrast to material goods, can be coded and decoded. The network coding techniques take full advantage of the inherent properties of information, and allow the nodes in a network, not only to store and forward, but also to "mix", i.e., encode, their received data. This approach was shown to result in a substantial throughput gain over the traditional routing and tree packing techniques. In this dissertation, we study applications of network coding for guarantying reliable and secure information transmission in networks with compromised edges. First, we investigate the construction of robust network codes for achieving network resilience against link failures. We focus on the practical important case of unicast networks with non-uniform edge capacities where a single link can fail at a time. We demonstrate that these networks exhibit unique structural properties when they are minimal, i.e., when they do not contain redundant edges. Based on this structure, we prove that robust linear network codes exist for these networks over GF(2), and devise an efficient algorithm to construct them. Second, we consider the problem of securing a multicast network against an eavesdropper that can intercept the packets on a limited number of network links. We recast this problem as a network generalization of the classical wiretap channel of Type II introduced by Ozarow and Wyner in 1984. In particular, we demonstrate that perfect secrecy can be achieved by using the Ozarow-Wyner scheme of coset coding at the source, on top of the implemented network code. Consequently, we transparently recover important results available in the literature on secure network coding. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction. In the last part of this dissertation, we study the connection between index coding, network coding, and matroid linear representation. We devise a reduction from the index coding problem to the network coding problem, implying that in the linear case these two problems are equivalent. We also present a second reduction from the matroid linear representability problem to index coding, and therefore, to network coding. The latter reduction establishes a strong connection between matroid theory and network coding theory. These two reductions are then used to construct special instances of the index coding problem where vector linear codes outperform scalar linear ones, and where non-linear encoding is needed to achieve the optimal number of transmission. Thereby, we provide a counterexample to a related conjecture in the literature and demonstrate the benefits of vector linear codes.

In recent times, there has been an increased focus on the problem of information exchange between two nodes using a relay node. The introduction of physical layer network coding has improved the throughput efficiency of such an exchange. In practice, the reliability of information exchange using this scheme is reduced due to synchronization issues at the relay node. In this thesis, we deal with timing synchronization of the signals received at the relay node. The timing offsets of the signals received at the relay node are computed based on the propagation delays in the transmitted signals. However, due to the random attenuation of signals in a fading channel, the near far problem is inherent in this situation. Hence, we aim to design near far resistant delay estimators for this system. We put forth four algorithms in this regard. In all the algorithms, propagation delay of each signal is estimated using a known preamble sent by the respective node at the beginning of the data packet. In the first algorithm, we carefully construct the preamble of each data packet and apply the MUSIC algorithm to overcome the near far problem. The eigenstructure of the correlation matrix is exploited to estimate propagation delay. Secondly, the idea of interference cancellation is implemented to remove the near far problem and delay is estimated using a correlator. Thirdly, a modified decorrelating technique is presented to negate the near far problem. Using this technique we aim to obtain an estimate of the weak user's delay that is more robust to errors in the strong user's delay estimate. In the last algorithm, pilot signals with desired autocorrelation and cross correlation functions are designed and a sliding correlator is used to estimate delay. Even though this approach is not near far resistant, performance results demonstrate that for the length's of preamble considered, this algorithm performs similar to the other algorithms.

Network Coding is a technique which looks beyond traditional store-and-forward approach followed by routers and switches in communication networks, and as an extension introduces maps termed as ‘local encoding kernels’ and ‘global encoding kernels’ defined for each communication link in the network. The purpose of both these maps is to define rules as to how to combine the packets input on the node to form a packet going out on an edge. The paradigm of network coding was formally and for the first time introduced by Ahlswede et al. in [1], where they also demonstrated its use in case of single-source multiple-sink network multicast, although with use of much complex mathematical apparatus. In [1], examples of networks are also presented where it is shown that network coding can improve the overall throughput of the network which can not otherwise be realized by the conventional store-and-forward approach. The main result in [1], i.e. the capacity of single-source multiple-sinks information network is nothing but the minimum of the max-flows from source to each sink, was again proved by Li, Yeung, and Cai in [2] where they showed that only linear operations suffice to achieve the capacity of multicast network. The authors in [2] defined generalizations to the multicast problem, which they termed as linear broadcast, linear dispersion, and Generic LCM as strict generalizations of linear multicast, and showed how to build linear network codes for each of these cases. For the case of linear multicast, Koetter and Medard in [3] developed an algebraic framework using tools from algebraic geometry which also proved the multicast max-flow min-cut theorem proved in [1] and [2]. It was shown that if the size of the finite field is bigger than a certain threshold, then there always exists a solution to the linear multicast, provided it is solvable. In other words, a solvable linear multicast always has a solution in any finite field whose cardinality is greater than the threshold value. The framework in [3] also dealt with the general linear network coding problem involving multiple sources and multiple sinks with non-uniform demand functions at the sinks, but did not touched upon the key problem of finding the characteristic(s) of the field in which it may have solution. It was noted in [5] that a solvable network may not have a linear solution at all, and then introduced the notion of general linear network coding, where the authors conjectured that every solvable network must have a general linear solution. This was refuted by Dougherty, Freiling, Zeger in [6], where the authors explicitly constructed example of a solvable network which has no general linear solution, and also networks which have solution in a finite field of char 2, and not in any other finite field. But an algorithm to find the characteristic of the field in which a scalar or general linear solution(if at all) exists did not find any mention in [3] or [6]. It was a simultaneous discovery by us(as part of this thesis) as well as by Dougherty, Freiling, Zeger in [7] to determine the characteristics algorithmically. Applications of Network Coding techniques to wireless networks are seen in literature( [8], [9], [10]), where [8] provided a variant of max-flow min-cut theorem for wireless networks in the form of linear programming constraints. A new architecture termed as COPE was introduced in [10] which used opportunistic listening and opportunistic coding in wireless mesh networks.