Full Rate Network Coding via Nesting Modulation Constellations

Wireless communications suffer greatly from multipath fading where outages may degrade communication quality. Different schemes, such as adaptive modulation and coding and relay [1], have been exploited to mitigate this problem. The relay efficiency can be improved via network coding (NC) [2] if the traffic pattern and the a priori information are exploited. Typical transmission patterns suitable for applying NC include two-way relay [3‐5], multihop forwarding [6], multiple access channel [7], multicast channel, and so forth. In addition, joint network and channel coding can further improve spectral efficiency [7, 8].

A two-way relay transmission typically consists of two stages: multiple access stage and broadcast stage. NC is applied in the second stage and has two types. The first type of NC is performed in the bit level [3]. Each node transmits its packet to the relay node successively. The relay node decodes each packet and combines them together via NC and forwards the coded packet later. The second type of NC is performed in the signal level. Typically two nodes transmit simultaneously their packets. The relay node regards the superposed signal as a NC signal and forwards it. Each node recovers its desired signal from the NC signal with interference cancelation [4]. The NC signal is further refined in [5] by taking modulation constellations into account.

The performance of NC, especially bit level NC, is limited by several factors such as packet length mismatch (the short packets are zero padded), traffic rate mismatch (some packets cannot be network-coded due to lack of pairing packets) and transmit rate mismatch. The last factor is neglected in most previous works. In the two-way relay scenarios, the rate mismatch may be formed due to two factors. One is the relay position (which leads to relatively stable differences in link qualities) and the other is fading. Even though the relay lies exactly in the middle of two nodes, the two relay links may have different instantaneous qualities. Since the network-coded packet is intended to be received by both nodes, the minimal rate is chosen for the NC transmission [3]. In this way, the transmission at a low rate on the link supporting a high rate wastes channel bandwidth.

When NC is applied to multiple flows, the effect of rate mismatch becomes more obvious, since the minimal rate over more links only gets lower. One solution to this problem is to exploit opportunistic scheduling. Instead of transmitting network-coded packets to all potential nodes, only some of them are selected by taking the tradeoff between the number of links and the actual rate [9]. This opportunistic scheduling, however, cannot exploit the full power of NC.

Recently, some initial efforts were made to fully exploit rate adaptations in NC. Multiplicative NC was proposed in [10] to better adapt code and modulation rates to different links. However, it only applies to constant modulus signals. Unconventional 5-ary modulation was introduced to work together with QPSK in [11]. This makes modulation complex and is difficult to extend to other modulations. Compress and forward was studied in [12], with the assumption that the relay is much closer to the sink than nodes and has a much higher rate. Its application is limited to multiple access up-link. XOR-based NC and physical layer superposition coding were combined together to better exploit rate adaptation in [13], however, at the cost of significant power loss. Moreover, its performance is degraded and approaches that of NC when relay links have similar quality. Despite all these efforts, there is still no complete solution to the rate mismatch problem.

In this paper, we focus on the bit level NC and propose to achieve full rate network-coding (FRNC) on the broadcast channel via nesting modulation constellations. With a cross-layer design, we exploit physical layer method as well. The principle of dirty paper coding [14] indicates that a signal known at the receiver is not interference at all and with suitable coding the full capacity is achievable. As an analogy for NC, when the a priori information is available, NC should also achieve the highest rate over each link, in other words, achieve the full rate on the broadcast channel. This is our starting point. The basic idea is as follows: (i) at the relay node, in order to combine packets together and transmit them over links supporting different rates (modulations), the low level constellation points are nested in the high level constellation. In other words, a subset of the high level constellation is used as the low level constellation, and this subset depends on the design of NC. (ii) At the receiver side, nodes merely supporting low level modulation first find their constellation according to the a priori information and then perform demodulation and decoding. In this way, the highest rate of each link is used and the sum rate is achieved over the broadcast channel. We further study the effect of the limit in constellation size and suggest combining FRNC with superposition coding (SC). Both the analysis and simulation evaluation show that FRNC with SC is significantly superior to the state-of-the-art solutions to the rate mismatch problem.

The rest of the paper is organized as follows: the relay model is presented in Section 2 and the reinterpretation of NC as constellation mapping is addressed in Section 3. In Section 4, the detailed procedures for achieving full rate in network-coded transmissions are described. The performance of different schemes is analyzed in the two-way relay scenario in Section 5 and the related simulation evaluation is presented in Section 6. Finally, we conclude the paper with Section 7.

We consider a network with nodes , , and 1 relay . For the simplicity of description, we assume that all nodes and are synchronized and the transmissions are done in terms of TDMA (it is possible to extend the proposed scheme to other channel access methods such as CSMA.) There are flows. The th flow from to goes through the two-hop path - - and the actual transfer of packets is via the relay . The packet transfer is divided into two stages: (a) multiple access stage where collects packets from all nodes. Each node sends packet to in the th slot, using its optimal rate (modulation and coding). After the data transmission, each node reports its receiving status of packets to , in a similar way as the COPE scheme [15]. Based on such a feedback, makes the NC scheduling, selecting a subset of nodes, each of which knows all packets involved in the NC except its own desired packet. Without loss of generality, in the following, we assume equals . Then after slots, knows . (b) Broadcast stage where forwards packets to all nodes. transmits ( represents the bitwise exclusive or (XOR) operation) to all nodes, and recovers by . Hence, packets are exchanged in +1 slots. A typical example for the model is the local area wireless networks where nodes exchange packets via their associated access point ( in the model). A special case is , corresponding to the two-way relay in Figure 1. In this special case, each node uses its transmitted packet as the a priori information and the feedback of receiving status of packets is unnecessary.

Over each link, the rate can be adjusted by modulation and coding. With coding rate and modulation level (constellation size = ), on average bits can be transmitted by each symbol. Generally, the modulation level determines a rate range, within which the coding scheme further fine adjusts the rate. Different modulation levels have constellations with different sizes. But these constellations all have the same normalized energy.

In the above model, NC is used at the second stage. We focus on this stage and exploit joint design of modulation and coding so that the highest rate of each link is realized in the NC transmission. We take the following assumptions: (i) has collected enough data for each flow so that the zero-padding is unnecessary in the NC transmission, (ii) the a priori information required for network decoding is available at each node by recording the overheard packets, and (iii) the relay node knows the channel state information of all links. The key problem is how to realize full rate on all links simultaneously.

In conventional bit level NC schemes, bits from different flows are XORed together, channel coded, modulated, and then transmitted. The receiver just works in the reverse way to recover its information bits. Due to the linearity of both channel coding and NC, their order can be exchanged [16]. In this paper, the NC operation is done after channel coding.

Although the NC is performed in the bit level, it can be reinterpreted as a function of constellation mapping. This is explained by an example shown in Figure 2 using the typical QPSK constellation with gray codes. Assume relays ("01") from to , and ("11") from to , respectively. When relaying these bits, combines them together as "10" by XOR and transmits . already knows ("11"). Exploiting this as the a priori information, for all possible bits of , the NC bits and corresponding signals can be computed locally at . These signals, when interpreted as the points for , construct a new QPSK constellation . This constellation has the same size as but with a different layout due to NC. In this way, the NC function actually provides a mapping between constellations. Instead of a fixed constellation in conventional modulations, such a mapping depends on the a priori information and changes for each symbol. The reinterpretation of NC can be summarized as follows:

(i) transmits where is the channel-coded packet of the th flow, and involves NC (XOR in conventional NC) and modulation.

(ii)At the receiver side, ( in conventional NC) provides the constellation for demodulating , where is the a priori information at the th receiver.

In conventional NC schemes, the constellations for different flows have the same size and min-distance, and the latter is the main factor that decides the rate. This forces the relay node to transmit the XORed packet with the minimal rate of all links so that all nodes can correctly recover the XORed packet.

The above constellation mapping can be extended to support simultaneous use of modulations with different levels (size and min-distance). Specifically, we use constellation-compatible modulations and nest the low level constellation inside the high level constellation. For example, a subset of four 16 QAM constellation points can be used as the QPSK constellation so that over the broadcast channel QPSK is used for one link while 16 QAM is used for the other link in the two-way relay scenario. In other words, among the links supporting different modulations, the highest modulation level is always used as the container. Other low level modulations use a subset of the high level constellation as their constellations.

In this section, we present the full rate network-coding (FRNC) protocol. First the basic idea is explained with a simple example. Then the idea is generalized. How to nest constellations, how to find the actual constellation under the NC operation, how to transmit at the relay, and how to receive at the nodes are successively described in detail.

In this section, we analyze the performance of different schemes under the two-way relay scenario shown in Figure 1. Six schemes are compared here. (i) DF, the decode-and-forward scheme, (ii) NC, the normal bit level NC scheme with minimal rate constraint, (iii) SC, the superposition coding scheme, (iv) NC + SC, the iPack scheme in [13], (v) FRNC, and (vi) FRNC + SC. In the analysis, we assume (i) each channel has zero mean AWGN noise with variance ; (ii) channel gain of the link - is ; (iii) each symbol has normalized energy and the SNR over each link is , (iv) the packet length is infinite.

In this section, we evaluate the proposed FRNC and FRNC + SC schemes using Monte-Carlo simulations. Each slot consists of 4800 symbols. Messages are coded by a 4-state recursive systematic convolutional (RSC) code with the generator matrix (1, 5/7). Modulation and coding schemes shown in Table 5 are used. Altogether, 10 different transmit rates can be supported. The number of information bits in a message varies from 2400 bits to 28800 bits. Messages are transmitted from to nodes via different schemes and decoded accordingly. In the evaluation, we focus on the broadcast channel, and compare FRNC, FRNC + SC against DF, NC [3], NC with opportunistic scheduling (NCSched) [9], SC, and NC + SC [13]. SNR loss in FRNC is taken into account when choosing rates for transmissions. It is assumed that each link experiences independent block Rayleigh fading. Modulation constellations are adopted from IEEE 802.11a and the related parameters (symbol period, number of subcarrier) are used in calculating throughput [19].

With the two-way relay scenario shown in Figure 1 and the same setting as in Section 5.2, we compare the actual throughput achieved by different schemes, with the practical constellation size limit. Figure 7 shows the total throughput of different schemes on the broadcast channel with respect to the normalized distance, where the largest constellation is 256 QAM. Generally speaking, Figure 7 shows similar trend as Figure 6. But with the limit in constellation size, some differences do occur: (i) FRNC + SC outperforms FRNC, (ii) at a small distance, FRNC and NC + SC have similar performances, and (iii) the difference between FRNC + SC and NC + SC gets larger than that in Figure 6. By the optimal allocation of power between FRNC and SC, the best performance is achieved in FRNC + SC under all distances. When the distance equals 0.30, FRNC + SC reaches the largest throughput gain, 25.8%, against NC + SC. At this distance, FRNC + SC achieves a much larger gain, 74.2%, against NC. The cumulative density function of the throughput at this distance is shown in Figure 8. The superiority of FRNC and FRNC + SC over other schemes is very clear.

Figure 9 shows the effect of constellation size limit. When the largest constellation is constrained to 64 QAM instead of 256 QAM, the performance of both FRNC + SC and FRNC is degraded. But the performance of FRNC + SC is less affected, where the extra-power is used in SC transmission than being wasted in FRNC.

Next the effect of the number of nodes, , is evaluated. Average SNR of all relay links is fixed at 20 dB. In such scenarios, SC can hardly be used. Therefore, only the schemes without using SC are compared. Figure 10 shows the throughput on the broadcast channel. DF transmits in a TDMA manner. Therefore, it cannot benefit from the increase in nodes and its throughput is almost a constant value. On the other hand, NC, NCSched and FRNC all benefit from the increase in flows more or less. Due to the different capability in handling rate mismatch, the slopes of three curves differ greatly. FRNC always has the highest throughput because the rate mismatch problem is completely solved and full rate is achieved.

Recently, network coding is widely studied for improving the relay efficiency in wireless networks. Its performance, however, is greatly limited by factors such as rate mismatch. In this paper, we reinterpreted network coding as a mapping between modulation constellations and extended this mapping to enable simultaneous use of different modulations in network-coded transmissions. In this way, the highest rate over each link can be used and the sum rate can be achieved over the broadcast channel. As a result, the rate mismatch problem is completely solved. The only shortcoming of the proposed scheme is its SNR loss in nesting constellations. This little SNR loss is acceptable if the throughput gain is taken into account. We will further study the effect of the direct link and the potential errors at relay node.