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.

In the last few years, wireless sensor networks (WSNs) have become a very actively researched area. The impetus for this spurt of interest were developments in wireless technologies and low-cost VLSI, that made it possible to build inexpensive sensors and actuators. Each such device has limited computational power, memory and energy supply. Nevertheless, because of the low cost, such devices can be deployed in large numbers, and can thereafter form a sensor network. Usually, one or more base stations are also present which act as sink nodes. When sensors are deployed in hostile environments, security becomes an integral part for such type of networks. A first step in this direction is to provide secure communication between any two nodes and between a node and the base station. Since the public key cryptographic techniques are computationally expensive for resource constrained sensors, one need to rely on symmetric key cryptography for secure communication. The distribution and management of cryptographic keys poses a unique challenge in sensor networks. One requires efficient key distribution algorithms for such type of networks. In this thesis, we address the problem of secure path key establishment in wireless sensor networks. We first propose a pairwise key distribution algorithm for probabilistic schemes. Inspired by the recent proxy-based schemes, we introduce a friend-based scheme for establishing pairwise keys securely. We show that the chances of finding friends in a neighbourhood are considerably more than that of finding proxies, leading to lower communication overhead. Further, we prove that the friend-based scheme performs better than the proxy-based scheme both in terms of resilience against node capture as well as in energy consumption for pairwise key establishment. A recent study has shown that the advantages of the probabilistic approach over the deterministic approach, are not as much as people have believed. Thus, we focus our attention on deterministic schemes in which we first discuss why one cannot use the conventional security measure for determining the resilience of a key distribution scheme in case of schemes in which nodes share more than one key. Then, we propose a new and a more general security metric for measuring the resilience of a key distribution scheme in wireless sensor networks. Further, we present a polynomial-based scheme and a novel complete connectivity scheme for distributing keys to sensors and show an analytical comparison, in terms of security and connectivity, between the schemes. Motivated by the schemes, we derive general expressions for the new security measure and the connectivity. A number of conclusions are made using these general expressions. Then, we conclude our work with a number of future directions that can be followed with this piece of work.

Energy harvesting (EH) nodes, which harvest energy from the environment in order to communicate over a wireless link, promise perpetual operation of wireless networks. The primary focus of the communication system design shifts from being as energy conservative as possible to judiciously handling the randomness in the energy harvesting process in order to enhance the system performance. This engenders a significant redesign of the physical and multiple access layers of communication. In this thesis, we address the problem of maximizing the throughput of a system that consists of rate-adaptive EH nodes that transmit data to a common sink node. We consider the practical case of discrete rate adaptation in which a node selects its transmission power from a set of finitely many rates and adjusts its transmit power to meet a bit error rate (BER) constraint. When there is only one EH node in the network, the problem involves determining the rate and power at which the node should transmit as a function of its channel gain and battery state. For the system with multiple EH nodes, which node should be selected also needs to be determined. We first prove that the energy neutrality constraint, which governs the operation of an EH node, is tighter than the average power constraint. We then propose a simple rate and power adaptation scheme for a system with a single EH node and prove that its throughput approaches the optimal throughput arbitrarily closely. We then arrive at the optimal selection and rate adaptation rules for a multi-EH node system that opportunistically selects at most one node to transmit at any time. The optimal scheme is shown to significantly outperform other ad hoc selection and transmission schemes. The effect of energy overheads, such as battery storage inefficiencies and the energy required for sensing and processing, on the transmission scheme and its overall throughput is also analytically characterized. Further, we show how the time and energy overheads incurred by the opportunistic selection process itself affect the adaptation and selection rules and the overall system throughput. Insights into the scaling behavior of the average system throughput in the asymptotic regime, in which the number of nodes tend to infinity, are also obtained. We also optimize the maximum time allotted for selection, so as to maximize the overall system throughput. For systems with EH nodes or non-EH nodes, which are subject to an average power constraint, the optimal rate and power adaptation depends on a power control parameter, which hitherto has been calculated numerically. We derive novel asymptotically tight bounds and approximations for the same, when the average rate of energy harvesting is large. These new expressions are analytically insightful, computationally useful, and are also quite accurate even in the non-asymptotic regime when average rate of energy harvesting is relatively small. In summary, this work develops several useful insights into the design of selection and transmission schemes for a wireless network with rate-adaptive EH nodes.

In this thesis, we consider a cooperative relay-assisted communication system that uses rateless codes. When multiple relays are present, the relay with the highest channel gain to the source is the first to successfully decode a message from the source and forward it to the destination. Thus, the unique properties of rateless codes ensure that both rate adaptation and relay selection occur without the transmitting source or relays acquiring instantaneous channel knowledge. We show that in such cooperative systems, buffering messages at relays significantly increases throughput. We develop a novel analysis of these systems that combines the communication-theoretic aspects of cooperation over fading channels with the queuing-theoretic aspects associated with buffering. Closed-form expressions are derived for the throughput and end-to-end delay for the general case in which the channels between various nodes are not statistically identical. Results are also shown for the benchmark system that does not buffer messages. Though relay selection combined with buffering of messages at the relays substantially increases the throughput of a cooperative network, it also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In order to overcome this, we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a message from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the message is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times. Next we combine the single relay selection scheme at the source with physical layer power control at the relays (due to the diversity provided by the rateless codes, power control at the source is not needed). We derive an optimal power control policy that minimizes the relay to destination transmission time. Due to its computational and implementation complexity, we develop another heuristic easily implementable near optimal policy. In this policy, power allocated turns out to be inversely proportional to the square root of channel gain. We also see that this policy performs better than the channel inversion policy. Our power control solution substantially decreases the mean end-to-end delays with a marginal increase in throughput also. Finally, we combine bit dropping with power control at the relays which further improves the system performance.

This thesis considers the modulation division based on the concept of uniquely factorable constellation pair (UFCP) and uniquely decodable constellation group (UDCG) in multiuser wireless communication networks. We first consider a two-hop relay network consisting of two single-antenna users and a two-antenna relay node, for which a novel distributed concatenated Alamouti code is devised. This new design allows the source and relay nodes to transmit their own information to the destination node concurrently at the symbol level with the aid of the UFCP generated from both PSK and square QAM constellations as well as by jointly processing the noisy signals received at the relay node. Moreover, an asymptotic symbol error probability (SEP) formula is derived for the ML receiver, showing that the maximum diversity gain function is achieved, which is proportional to $\ln \mathtt{SNR}/\mathtt{SNR}^2$. Then, we concentrate on the point-to-point correlated multiple-input and multiple-output (MIMO) communication systems where full knowledge of channel state information (CSI) is available at the receiver and only the first- and second-order statistics of the channels are available at the transmitter. When the number of antenna elements of both ends goes to infinity while keeping their ratio constant, the asymptotic SEP analysis is carried out for either optimally precoded or uniformly precoded correlated large MIMO fading channels using the zero-forcing (ZF) detector with equally likely PAM, PSK or square QAM constellations. For such systems, we reveal some very nice structures which inspire us to explore two very useful mathematical tools (i.e., the Szego's theorem on large Hermitian Toeplitz matrices and the well-known limit: $\lim_{x\to\infty}(1+1/x)^x=e$), for the systematic study of asymptotic behaviors on their error performance. This new approach enables us to attain a very simple expression for the SEP limit as the number of the available antenna elements goes to infinity. In what follows, the problem of precoder design using a zero-forcing decision-feedback (ZF-DF) detector is also addressed. For such a MIMO system, our principal goal is to efficiently design an optimal precoder that minimizes the asymptotic SEP of the ZF-DF detector under a perfect decision feedback. By fully taking advantage of the product majorization relationship among eigenvalues, singular-values and Cholesky values of the precoded channel matrix parameters, a necessary condition for the optimal solution to satisfy is first developed and then the structure of the optimal solution is characterized. With these results, the original non-convex problem is reformulated into a convex one that can be efficiently solved by using an interior-point method. In addition, by scaling up the antenna array size of both terminals without bound for such a network, we propose a novel method as we did for the ZF receiver scenario to analyze the asymptotic SEP performance of an equal-diagonal QRS precoded large MIMO system when employing an abstract Toeplitz correlation model for the transmitter antenna array. This new approach has a simple expression with a fast convergence rate and thus, is efficient and effective for error performance evaluation. For multiuser communication networks, we first consider a discrete-time multiple-input single-output (MISO) Gaussian broadcast channel (BC) where perfect CSI is available at both the transmitter and all the receivers. We propose a flexible and explicit design of a uniquely decomposable constellation group (UDCG) based on PAM and rectangular QAM constellations. With this new concept, a modulation division (MD) transmission scheme is developed for the considered MISO BC. The proposed MD scheme enables each receiver to uniquely and efficiently recover their desired signals from the superposition of mutually interfering cochannel signals in the absence of noise. Using max-min fairness as a design criterion, the optimal transmitter beamforming problem is solved in a closed-form for two-user MISO BC. Then, for a general case with more than two receivers, a user-grouping based beamforming scheme is developed, where the grouping method, beamforming vector design and power allocation problems are addressed by employing weighted max-min fairness. Then, we consider an uplink massive single-input and multiple-output (SIMO) network consisting of a base station (BS) and several single-antenna users. To recover the transmitted signal matrix of all the users when the antenna array size is large, a novel multi-user space-time modulation (MUSTM) scheme is proposed for the considered network based on the explicit construction of QAM uniquely-decomposable constellation groups (QAM-UDCGs). In addition, we also develop a sub-constellation allocation method at the transmitter side to ensure the signal matrix is always invertible. In the meanwhile, an efficient training correlation receiver (TCR) is proposed which calculates the correlation between the received sum training signal vector and the sum information carrying vector. Moreover, the optimal power allocation problems are addressed by maximizing the coding gain or minimizing the average SEP of the received sum signal under both average and peak power constraints on each user. The proposed transmission scheme not only allows the transmitted signals with strong mutual interference to be decoded by a simple TCR but it also enables the CSI of all the users to be estimated within a minimum number of time slots equal to that of the users. Comprehensive computer simulations are carried out to verify the effectiveness of the proposed uniquely decomposable space-time modulation method in various network topologies and configurations. Our modulation division method will be one of the promising technologies for the fifth generation (5G) communication systems. / Dissertation / Doctor of Philosophy (PhD)

<p>Smart downlink scheduling can be used to reduce infrastructure-to-vehicle energy costs in delay tolerant roadside networks. In this thesis this type of scheduling is incorporated into ON/OFF roadside unit sleep activity, to further reduce infrastructure power consumption. To achieve significant power savings however, the OFF-to-ON sleep transitions may be very lengthy, and this overhead must be taken into account when performing the scheduling. The OFF/ON sleep transitions are incorporated into a lower bound on energy use for the constant bit rate air interface case. An online scheduling algorithm referred to as the Flow Graph Sleep Scheduler (FGS) is then introduced which makes locally optimum ON/OFF cycle decisions. This is done by computing energy estimates needed both with and without a new OFF/ON cycle. The energy calculation can be efficiently done using a novel minimum ow graph formulation. We also consider the fixed transmit power, variable bit rate, air interface case. As before, a lower bound on RSU energy use is computed by formulating and solving an integer program. Results from a variety of experiments show that the proposed scheduling algorithms perform well when compared to the energy lower bounds. The algorithms are especially attractive in situations where vehicle demands and arrival rates are such that the energy costs permit frequent ON/OFF cycling.</p> / Master of Science (MSc)

Network lifetime is a key issue in wireless sensor networks where sensor nodes, distributed typically in remote/hostile sensing areas, are powered by finite energy batteries which are not easily replaced/recharged. Depletion of these finite energy batteries can result in a change in network topology or in the end of network life itself. Hence, prolonging the life of wireless sensor networks is important. Energy consumed in wireless sensor nodes can be for the purpose of i) sensing functions, ii) processing/computing functions, and ii) communication functions. For example, energy consumed by the transmit and receive electronics constitute the energy expended for communication functions. Our focus in this thesis is on the efficient use of energy for sensing. In particular, we are concerned with energy efficient algorithms for scheduling the sensing activity of sensor nodes. By scheduling the sensing activity we mean when to activate a sensor node for sensing (active mode) and when to keep it idle (sleep mode). The novel approach we adopt in this thesis to achieve efficient scheduling of sensing activity is an information coverage approach, rather than the widely adopted physical coverage approach. In the physical coverage approach, a point is said to be covered by a sensor node if that point lies within the physical coverage range (or the sensing radius) of that sensor, which is the maximum distance between the sensor and the point up to which the sensor can sense with acceptable accuracy. Information coverage, on the other hand, exploits cooperation among multiple sensors to accurately sense a point even if that point falls outside the physical coverage range of all the sensors. In this thesis, we address the question of how to schedule the activity of various sensor nodes in the network to enhance network lifetime using information coverage. In the first part of the thesis, we are concerned with scheduling of sensor nodes for sensing point targets using information coverage – example of a point-target being temperature or radiation level at a source or point that needs to be monitored. Defining a set of sensor nodes which collectively can sense a point-target accurately as an information cover, we propose an algorithm to obtain Disjoint Set of Information Covers (DSIC) that can sense multiple point-targets in a given sensing area. Being disjoint, the resulting information covers in the proposed algorithm allow a simple round-robin schedule of sensor activation (i.e., activate the covers sequentially). We show that the covers obtained using the proposed DSIC algorithm achieve longer network life compared to the covers obtained using an Exhaustive-Greedy-Equalized Heuristic (EGEH) proposed recently in the literature. We also present a detailed complexity comparison between the DSIC and EGEH algorithms. In the second part of the thesis, we extend the point target sensing problem in the first part to a full area sensing problem, where we are concerned with energy efficient ‘area-monitoring’ using information coverage. We refer to any set of sensors that can collectively sense all points in the entire area-to-monitor as a full area information cover. We first propose a low-complexity heuristic algorithm to obtain full area information covers. Using these covers, we then obtain the optimum schedule for activating the sensing activity of various sensors that maximizes the sensing lifetime. The optimum schedules obtained using the proposed algorithm is shown to achieve significantly longer sensing lifetimes compared to those achieved using physical coverage. Relaxing the full area coverage requirement to a partial area coverage requirement (e.g., 95% of area coverage as adequate instead of 100% area coverage) further enhances the lifetime. The algorithms proposed for the point targets and full area sensing problems in the first two parts are essentially centralized algorithms. Decentralized algorithms are preferred in large networks. Accordingly, in the last part of the thesis, we propose a low-complexity, distributed sensor scheduling algorithm for full area sensing using information coverage. This distributed algorithm is shown to result in significantly longer sensing lifetimes compared to those achieved using physical coverage.