DMT-optimal, Low ML-Complexity STBC-Schemes for Asymmetric MIMO Systems

For an n(t) transmit, nr receive antenna (n(t) x n(r)) MIMO system with quasi- static Rayleigh fading, it was shown by Elia et al. that space-time block code-schemes (STBC-schemes) which have the non-vanishing determinant (NVD) property and are based on minimal-delay STBCs (STBC block length equals n(t)) with a symbol rate of n(t) complex symbols per channel use (rate-n(t) STBC) are diversity-multiplexing gain tradeoff (DMT)-optimal for arbitrary values of n(r). Further, explicit linear STBC-schemes (LSTBC-schemes) with the NVD property were also constructed. However, for asymmetric MIMO systems (where n(r) < n(t)), with the exception of the Alamouti code-scheme for the 2 x 1 system and rate-1, diagonal STBC-schemes with NVD for an nt x 1 system, no known minimal-delay, rate-n(r) LSTBC-scheme has been shown to be DMT-optimal. In this paper, we first obtain an enhanced sufficient criterion for an STBC-scheme to be DMT optimal and using this result, we show that for certain asymmetric MIMO systems, many well-known LSTBC-schemes which have low ML-decoding complexity are DMT-optimal, a fact that was unknown hitherto.

Relay Selection for Geographical Forwarding in Sleep-Wake Cycling Wireless Sensor Networks

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. We seek to develop local forwarding algorithms that can be tuned so as to tradeoff the end-to-end delay against a total cost, such as the hop count or total energy. Our approach is to solve, at each forwarding node enroute to the sink, the local forwarding problem of minimizing one-hop waiting delay subject to a lower bound constraint on a suitable reward offered by the next-hop relay; the constraint serves to tune the tradeoff. The reward metric used for the local problem is based on the end-to-end total cost objective (for instance, when the total cost is hop count, we choose to use the progress toward sink made by a relay as the reward). The forwarding node, to begin with, is uncertain about the number of relays, their wake-up times, and the reward values, but knows the probability distributions of these quantities. At each relay wake-up instant, when a relay reveals its reward value, the forwarding node's problem is to forward the packet or to wait for further relays to wake-up. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate our local forwarding problem as a partially observable Markov decision process (POMDP) and obtain inner and outer bounds for the optimal policy. Motivated by the computational complexity involved in the policies derived out of these bounds, we formulate an alternate simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the inner and outer bound policies against the simple policy, and also against the optimal policy when the source knows the exact number of relays. Observing the good performance and the ease of implementation of the simple policy, we apply it to our motivating problem, i.e., local geographical routing of sporadic alarm packets in a large WSN. We compare the end-to-end performance (i.e., average total delay and average total cost) obtained by the simple policy, when used for local geographical forwarding, against that obtained by the globally optimal forwarding algorithm proposed by Kim et al. 1].

An Adaptive Conditional Zero-Forcing Decoder With Full-Diversity, Least Complexity and Essentially-ML Performance for STBCs

A low complexity, essentially-ML decoding technique for the Golden code and the three antenna Perfect code was introduced by Sirianunpiboon, Howard and Calderbank. Though no theoretical analysis of the decoder was given, the simulations showed that this decoding technique has almost maximum-likelihood (ML) performance. Inspired by this technique, in this paper we introduce two new low complexity decoders for Space-Time Block Codes (STBCs)-the Adaptive Conditional Zero-Forcing (ACZF) decoder and the ACZF decoder with successive interference cancellation (ACZF-SIC), which include as a special case the decoding technique of Sirianunpiboon et al. We show that both ACZF and ACZF-SIC decoders are capable of achieving full-diversity, and we give a set of sufficient conditions for an STBC to give full-diversity with these decoders. We then show that the Golden code, the three and four antenna Perfect codes, the three antenna Threaded Algebraic Space-Time code and the four antenna rate 2 code of Srinath and Rajan are all full-diversity ACZF/ACZF-SIC decodable with complexity strictly less than that of their ML decoders. Simulations show that the proposed decoding method performs identical to ML decoding for all these five codes. These STBCs along with the proposed decoding algorithm have the least decoding complexity and best error performance among all known codes for transmit antennas. We further provide a lower bound on the complexity of full-diversity ACZF/ACZF-SIC decoding. All the five codes listed above achieve this lower bound and hence are optimal in terms of minimizing the ACZF/ACZF-SIC decoding complexity. Both ACZF and ACZF-SIC decoders are amenable to sphere decoding implementation.

A weighted average based external clock synchronization protocol for wireless sensor networks

Clock synchronization is an extremely important requirement of wireless sensor networks(WSNs). There are many application scenarios such as weather monitoring and forecasting etc. where external clock synchronization may be required because WSN itself may consists of components which are not connected to each other. A usual approach for external clock synchronization in WSNs is to synchronize the clock of a reference node with an external source such as UTC, and the remaining nodes synchronize with the reference node using an internal clock synchronization protocol. In order to provide highly accurate time, both the offset and the drift rate of each clock with respect to reference node are estimated from time to time, and these are used for getting correct time from local clock reading. A problem with this approach is that it is difficult to estimate the offset of a clock with respect to the reference node when drift rate of clocks varies over a period of time. In this paper, we first propose a novel internal clock synchronization protocol based on weighted averaging technique, which synchronizes all the clocks of a WSN to a reference node periodically. We call this protocol weighted average based internal clock synchronization(WICS) protocol. Based on this protocol, we then propose our weighted average based external clock synchronization(WECS) protocol. We have analyzed the proposed protocols for maximum synchronization error and shown that it is always upper bounded. Extensive simulation studies of the proposed protocols have been carried out using Castalia simulator. Simulation results validate our theoretical claim that the maximum synchronization error is always upper bounded and also show that the proposed protocols perform better in comparison to other protocols in terms of synchronization accuracy. A prototype implementation of the proposed internal clock synchronization protocol using a few TelosB motes also validates our claim.

Low complexity adaptation for channel shortening equalizers

Since the days of Digital Subscriber Links(DSL), Time Domain Equalizers(TEQ's) have been used to combat time dispersive channels in Multicarrier Systems. In this paper, we propose computationally inexpensive techniques to recompute TEQ weights in the presence of changes in the channel, especially over fast fading channels. The techniques use no extra information except the perturbation itself, and provide excellent approximations to the new TEQ weights. The proposed adaptation techniques are shown to perform admirably well for small changes in channels for OFDM systems.

Minimizing the complexity of fast sphere decoding of STBCs

Decoding of linear space-time block codes (STBCs) with sphere-decoding (SD) is well known. A fast-version of the SD known as fast sphere decoding (FSD) has been recently studied by Biglieri, Hong and Viterbo. Viewing a linear STBC as a vector space spanned by its defining weight matrices over the real number field, we define a quadratic form (QF), called the Hurwitz-Radon QF (HRQF), on this vector space and give a QF interpretation of the FSD complexity of a linear STBC. It is shown that the FSD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization) or the number of receive antennas. It is also shown that the FSD complexity is completely captured into a single matrix obtained from the HRQF. Moreover, for a given set of weight matrices, an algorithm to obtain a best ordering of them leading to the least FSD complexity is presented. The well known classes of low FSD complexity codes (multi-group decodable codes, fast decodable codes and fast group decodable codes) are presented in the framework of HRQF.

A Novel Power Allocation Scheme for Two-User GMAC with Finite Input Constellations

Constellation Constrained (CC) capacity regions of two-user Gaussian Multiple Access Channels (GMAC) have been recently reported, wherein an appropriate angle of rotation between the constellations of the two users is shown to enlarge the CC capacity region. We refer to such a scheme as the Constellation Rotation (CR) scheme. In this paper, we propose a novel scheme called the Constellation Power Allocation (CPA) scheme, wherein the instantaneous transmit power of the two users are varied by maintaining their average power constraints. We show that the CPA scheme offers CC sum capacities equal (at low SNR values) or close (at high SNR values) to those offered by the CR scheme with reduced decoding complexity for QAM constellations. We study the robustness of the CPA scheme for random phase offsets in the channel and unequal average power constraints for the two users. With random phase offsets in the channel, we show that the CC sum capacity offered by the CPA scheme is more than the CR scheme at high SNR values. With unequal average power constraints, we show that the CPA scheme provides maximum gain when the power levels are close, and the advantage diminishes with the increase in the power difference.

The evolution of complexity in social organization-A model using dominance-subordinate behavior in two social wasp species

Dominance and subordinate behaviors are important ingredients in the social organizations of group living animals. Behavioral observations on the two eusocial species Ropalidia marginata and Ropalidia cyathiformis suggest varying complexities in their social systems. The queen of R. cyathiformis is an aggressive individual who usually holds the top position in the dominance hierarchy although she does not necessarily show the maximum number of acts of dominance, while the R. marginata queen rarely shows aggression and usually does not hold the top position in the dominance hierarchy of her colony. In R. marginata, more workers are involved in dominance-subordinate interactions as compared to R. cyathiformis. These differences are reflected in the distribution of dominance-subordinate interactions among the hierarchically ranked individuals in both the species. The percentage of dominance interactions decreases gradually with hierarchical ranks in R. marginata while in R. cyathiformis it first increases and then decreases. We use an agent-based model to investigate the underlying mechanism that could give rise to the observed patterns for both the species. The model assumes, besides some non-interacting individuals, the interaction probabilities of the agents depend on their pre-differentiated winning abilities. Our simulations show that if the queen takes up a strategy of being involved in a moderate number of dominance interactions, one could get the pattern similar to R. cyathiformis, while taking up the strategy of very low interactions by the queen could lead to the pattern of R. marginata. We infer that both the species follow a common interaction pattern, while the differences in their social organization are due to the slight changes in queen as well as worker strategies. These changes in strategies are expected to accompany the evolution of more complex societies from simpler ones.

Performance improvement of short-length regular low-density parity-check codes with low-complexity post-processing

It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high E-b/N-0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high E-b/N-0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.

Tradeoff of average power and average delay for a point-to-point link with fading

We consider a discrete time system with packets arriving randomly at rate lambda per slot to a fading point-to-point link, for which the transmitter can control the number of packets served in a slot by varying the transmit power. We provide an asymptotic characterization of the minimum average delay of the packets, when average transmitter power is a small positive quantity V more than the minimum average power required for queue stability. We show that the minimum average delay will grow either as log (1/V) or 1/V when V down arrow 0, for certain sets of values of lambda. These sets are determined by the distribution of fading gain, the maximum number of packets which can be transmitted in a slot, and the assumed transmit power function, as a function of the fading gain and the number of packets transmitted. We identify a case where the above behaviour of the tradeoff differs from that obtained from a previously considered model, in which the random queue length process is assumed to evolve on the non-negative real line.

Tradeoff of average service cost and average delay for the state dependent M/M/1 queue

The optimal tradeoff between average service cost rate and average delay, is addressed for a M/M/1 queueing model with queue-length dependent service rates, chosen from a finite set. We provide an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity V more than the minimum average service cost rate required for stability. We show that depending on the value of the arrival rate, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either a) increases only to a finite value, b) increases without bound as log(1/V), or c) increases without bound as 1/V, when V down arrow 0. We apply the analysis to a flow-level resource allocation model for a wireless downlink. We also investigate the asymptotic tradeoff for a sequence of policies which are obtained from an approximate fluid model for the M/M/1 queue.

Reduced-complexity partial-interference-cancellation group decoder for STBCs

In this letter, we propose a reduced-complexity implementation of partial interference cancellation group decoder with successive interference cancellation (PIC-GD-SIC) by employing the theory of displacement structures. The proposed algorithm exploits the block-Toeplitz structure of the effective matrix and chooses an ordering of the groups such that the zero-forcing matrices associated with the various groups are obtained through Schur recursions without any approximations. We show using an example that the proposed implementation offers a significantly reduced computational complexity compared to the direct approach without any loss in performance.

SC-FDMA for multiuser communication on the downlink

Single-carrier frequency division multiple access (SC-FDMA) has become a popular alternative to orthogonal frequency division multiple access (OFDMA) in multiuser communication on the uplink. This is mainly due to the low peak-to-average power ratio (PAPR) of SC-FDMA compared to that of OFDMA. Long-term evolution (LTE) uses SC-FDMA on the uplink to exploit this PAPR advantage to reduce transmit power amplifier backoff in user terminals. In this paper, we show that SC-FDMA can be beneficially used for multiuser communication on the downlink as well. We present SC-FDMA transmit and receive signaling architectures for multiuser communication on the downlink. The benefits of using SC-FDMA on the downlink are that SC-FDMA can achieve i) significantly better bit error rate (BER) performance at the user terminal compared to OFDMA, and ii) improved PAPR compared to OFDMA which reduces base station (BS) power amplifier backoff (making BSs more green). SC-FDMA receiver needs to do joint equalization, which can be carried out using low complexity equalization techniques. For this, we present a local neighborhood search based equalization algorithm for SC-FDMA. This algorithm is very attractive both in complexity as well as performance. We present simulation results that establish the PAPR and BER performance advantage of SC-FDMA over OFDMA in multiuser SISO/MIMO downlink as well as in large-scale multiuser MISO downlink with tens to hundreds of antennas at the BS.

On the sphere decoding complexity of high-rate multigroup decodable STBCs in asymmetric MIMO systems

A space-time block code (STBC) is said to be multigroup decodable if the information symbols encoded by it can be partitioned into two or more groups such that each group of symbols can be maximum-likelihood (ML) decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high-rate (rate greater than 1) multigroup decodable codes have rank-deficient matrix even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only in asymmetric MIMO systems when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank matrix, the complexity of the sphere decoding-based ML decoder for STBCs with rank-deficient matrix is polynomial in the constellation size, and hence is high. We derive the ML sphere decoding complexity of most of the known high-rate multigroup decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.