The Relay Selection and Transmission Trade-off in Cooperative Communication Systems

A common and practical paradigm in cooperative communication systems is the use of a dynamically selected `best' relay to decode and forward information from a source to a destination. Such systems use two phases - a relay selection phase, in which the system uses transmission time and energy to select the best relay, and a data transmission phase, in which it uses the spatial diversity benefits of selection to transmit data. In this paper, we derive closed-form expressions for the overall throughput and energy consumption, and study the time and energy trade-off between the selection and data transmission phases. To this end, we analyze a baseline non-adaptive system and several adaptive systems that adapt the selection phase, relay transmission power, or transmission time. Our results show that while selection yields significant benefits, the selection phase's time and energy overhead can be significant. In fact, at the optimal point, the selection can be far from perfect, and depends on the number of relays and the mode of adaptation. The results also provide guidelines about the optimal system operating point for different modes of adaptation. The analysis also sheds new insights on the fast splitting-based algorithm considered in this paper for relay selection.

Voluntary Energy Harvesting Relays and Selection in Cooperative Wireless Networks

The use of energy harvesting (EH) nodes as cooperative relays is a promising and emerging solution in wireless systems such as wireless sensor networks. It harnesses the spatial diversity of a multi-relay network and addresses the vexing problem of a relay's batteries getting drained in forwarding information to the destination. We consider a cooperative system in which EH nodes volunteer to serve as amplify-and-forward relays whenever they have sufficient energy for transmission. For a general class of stationary and ergodic EH processes, we introduce the notion of energy constrained and energy unconstrained relays and analytically characterize the symbol error rate of the system. Further insight is gained by an asymptotic analysis that considers the cases where the signal-to-noise-ratio or the number of relays is large. Our analysis quantifies how the energy usage at an EH relay and, consequently, its availability for relaying, depends not only on the relay's energy harvesting process, but also on its transmit power setting and the other relays in the system. The optimal static transmit power setting at the EH relays is also determined. Altogether, our results demonstrate how a system that uses EH relays differs in significant ways from one that uses conventional cooperative relays.

A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

Cooperative Spectrum Sensing Algorithms For OFDM Systems with Frequency Selective Channels

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user employs Orthogonal Frequency Division Multiplexing (OFDM). We specifically consider the scenario when the channel between the primary and a secondary user is frequency selective. We develop cooperative sequential detection algorithms based on energy detectors. We modify the detectors to mitigate the effects of some common model uncertainties such as timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. The performance of the proposed algorithms are studied via simulations. We show that the performance of the energy detector is not affected by the frequency selective channel. We also provide a theoretical analysis for some of our algorithms.

Cooperative OFDM with Amplify-and-Forward Relaying with Timing Offset

In this paper, we investigate cooperative OFDM communications using amplify-and-forward (AF) protocol at the relays, in the presence of imperfect timing synchronization. In most studies on cooperative communications, perfect time synchronization among cooperating nodes is assumed. In practice, however, due to imperfect time synchronization, orthogonality among the subcarriers of the different nodes' signals at the destination receiver can be lost, causing inter-symbol interference (ISI). In this paper, we derive analytical expressions for the average SINR at the DFT output at the destination as a function of timing offset in cooperative OFDM with AF protocol, and illustrate the SINR degradation as a function of the timing offset. We also present an interference canceling (IC) receiver to mitigate the effects of ISI when there is timing offset. We show that the proposed IC receiver achieves improved BER performance even when timing offsets are large.

Queued Cooperative Wireless Networks With Rateless Codes

Cooperative communication using rateless codes, in which the source transmits an infinite number of parity bits to the destination until the receipt of an acknowledgment, has recently attracted considerable interest. It provides a natural and efficient mechanism for accumulating mutual information from multiple transmitting relays. We develop an analysis of queued cooperative relay systems that combines the communication-theoretic transmission aspects of cooperative communication using rateless codes over Rayleigh fading channels with the queuing-theoretic aspects associated with buffering messages at the relays. Relay cooperation combined with queuing reduces the message transmission times and also helps distribute the traffic load in the network, which improves throughput significantly.

Social selection and the evolution of cooperative groups: The example of the cellular slime moulds

In social selection the phenotype of an individual depends on its own genotype as well as on the phenotypes, and so genotypes, of other individuals. This makes it impossible to associate an invariant phenotype with a genotype: the social context is crucial. Descriptions of metazoan development, which often is viewed as the acme of cooperative social behaviour, ignore or downplay this fact. The implicit justification for doing so is based on a group-selectionist point of view. Namely, embryos are clones, therefore all cells have the same evolutionary interest, and the visible differences between cells result from a common strategy. The reasoning is flawed, because phenotypic heterogeneity within groups can result from contingent choices made by cells from a flexible repertoire as in multicellular development. What makes that possible is phenotypic plasticity, namely the ability of a genotype to exhibit different phenotypes. However, co-operative social behaviour with division of labour requires that different phenotypes interact appropriately, not that they belong to the same genotype, or have overlapping genetic interests. We sketch a possible route to the evolution of social groups that involves many steps: (a) individuals that happen to be in spatial proximity benefit simply by virtue of their number; (b) traits that are already present act as preadaptations and improve the efficiency of the group; and (c) new adaptations evolve under selection in the social context-that is, via interactions between individuals-and further strengthen group behaviour. The Dictyostelid or cellular slime mould amoebae (CSMs) become multicellular in an unusual way, by the aggregation of free-living cells. In nature the resulting group can be genetically homogeneous (clonal) or heterogeneous (polyclonal); in either case its development, which displays strong cooperation between cells (to the extent of so-called altruism) is not affected. This makes the CSMs exemplars for the study of social behaviour.

The concentration dependent cooperative friction coefficient of dilute polymer solutions at the theta point

We combine multiple scattering and renormalization group methods to calculate the leading order dimensionless virial coefficient k(s) for the friction coefficient of dilute polymer solutions under conditions where the osmotic second virial coefficient vanishes (i.e., at the theta point T-theta). Our calculations are formulated in terms of coupled kinetic equations for the polymer and solvent, in which the polymers are modeled as continuous chains whose configurations evolve under the action of random forces in, the velocity field of the solvent. To lowest order in epsilon=4-d, we find that k(s) = 1.06. This result compares satisfactorily with existing experimental estimates of k(s), which are in the range 0.7-0.8. It is also in good agreement with other theoretical results on chains and suspensions at T-theta. Our calculated k(s) is also found to be identical to the leading order virial coefficient of the tracer friction coefficient at the theta point. We discuss possible reasons for the difficulties encountered when attempting to evaluate k(s) by extrapolating prior renormalization group calculations from semidilute concentrations to the infinitely dilute limit. (C) 1996 American Institute of Physics.

Male-biased adult sex ratios and their significance for cooperative breeding in dhole, Cuon alpinus, packs

Two free-ranging packs of dholes (Asiatic wild dog, Cuon alpinus) were monitored for a period of 6 yr (Sep. 1990-Sep. 1996) in the Mudumalai sanctuary, southern India. Demographic data on age structure, litter-size, sex ratio and age and sex specific dispersal were collected. Behavioural data on social interactions and reproductive behaviour among pack members were obtained to determine the frequencies of dominant and subordinate behaviours shown by malt: and female pack members and a measure of each male's reproductive access to females. Behaviours displayed by pack members at dens were recorded to determine whether any age- or sex-specific role specialization existed during pup care. Tenures for dominant males and females within the pack were calculated to ascertain the rate of breeding vacancies occurring within packs. Approximate levels of genetic relatedness within packs were determined by studying pedigrees. In most years one study pack had a male-biased adult sex ratio. This was caused by almost twofold higher dispersal of adult females over adult males. A considerable variance existed in the percentage of sub-adults dispersing from the two packs. Differences existed in the frequencies of dominant and subordinate behaviours shown by males. For males, dominance ranks and ranks based on submissive behaviours were not correlated with frequencies of reproductive behaviours. Subordinate males also displayed reproductive behaviours. In packs, dominant males had lower tenures than dominant females indicating that among males breeding vacancies arose more quickly. The litter size was found to be negatively correlated with the age of the breeding female. There were no significant differences across individuals of varying age or sex classes in the display of pup care behaviours. Significant differences did exist among individual adults. Genetic relatedness among packs tended to vary temporally as a consequence of possible mating by subordinate animals and immigration of new males into the pack. In conclusion, it appears that males delay dispersal and cooperate within their natal packs because of the variety of reproductive strategies they could pursue within. A combination of ecological constraints and the difficulties of achieving breeding status within non-natal packs may make early dispersal and independent breeding less beneficial.

Cyclic Prefix Based Cooperative Sequential Spectrum Sensing Algorithms for OFDM

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user is using Orthogonal Frequency Division Multiplexing (OFDM). For this we develop cooperative sequential detection algorithms that use the autocorrelation property of cyclic prefix (CP) used in OFDM systems. We study the effect of timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. We also modify the detector to mitigate the effects of these impairments. The performance of the proposed algorithms is studied via simulations. We show that sequential detection can significantly improve the performance over a fixed sample size detector.

Relay Load Balancing in Queued Cooperative Wireless Networks with Rateless Codes

Relay selection combined with buffering of packets of relays can substantially increase the throughput of a cooperative network that uses rateless codes. However, buffering also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In this paper we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a packet 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 packet 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 explicit necessary and sufficient 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.

DMT of multi-hop cooperative networks

Some basic results that help in determining the Diversity-Multiplexing Tradeoff (DMT) of cooperative multihop networks are first identified. As examples, the maximum achievable diversity gain is shown to equal the min-cut between source and sink, whereas the maximal multiplexing gain is shown to equal the minimum rank of the matrix characterizing the MIMO channel appearing across a cut in the network. Two multi-hop generalizations of the two-hop network are then considered, namely layered networks as well as a class of networks introduced here and termed as K-parallel-path (KPP) networks. The DMT of KPP networks is characterized for K > 3. It is shown that a linear DMT between the maximum diversity dmax and the maximum multiplexing gain of 1 is achievable for fully-connected, layered networks. Explicit coding schemes achieving the DMT that make use of cyclic-division-algebra-based distributed space-time codes underlie the above results. Two key implications of the results in the paper are that the half-duplex constraint does not entail any rate loss for a large class of cooperative networks and that simple, amplify-and-forward protocols are often sufficient to attain the optimal DMT.