GUO et al.: JOINT ENCODING AND GROUPING MULTIPLE NODE PAIRS FOR PNC WITH LOW-COMPLEXITY ALGORITHM 9277
Rectangles for two-way relay network scenario. With the objec-
tive of determining the optimal symbol/bit mappings in PNC,
an optimization framework has been presented by jointly con-
sidering noisy transmissions in both MA and BC phases, and
methods with low-complexity have been designed to solve the
optimization problem in [14]. Since the network coding map
at the relay has a direct relationship with network access, two
methods for the network coding map acquirement have been
studied in [15]: 1) from finding all the required maps to select-
ing a small set of maps by employing the structural properties
of the Latin squares and 2) proposing a criterion to adopt the
Latin square for the specific realization of fade state. In order
to approach the upper bound capacity of Gaussian and fading
two-way relay channels, the authors in [16] have studied a prac-
tical nested lattice code based method to minimize the error
probability.
In this paper, we study a joint encoding method which can sup-
port various modulation types with asynchronous signals, and
also design a grouping method to ensure the decodability. Our
study is more challenging than previous ones, because high-level
sophisticated modulations require complicated joint encoding
methods, and there are a large number of possible node-pair
combinations to be checked for selecting the best one. Part of
our work has been presented in [17]. This work distinguishes
with the previous one in that 1) the original joint encoding and
node-pair grouping scheme has been extended to a more general
model for diverse network situations, and three improved PNC
schemes are studied with different objectives; 2) compared with
the previous study, the Latin rectangle based encoding method
has a lower computational complexity; 3) the grouping method
has been reconstructed with a lower computational complex-
ity; 4) and extensive performance evaluations are conducted to
demonstrate the effectiveness of our studied method.
III. S
YSTEM MODEL
We consider a star topology, which consists of one relay
and a number of node pairs. The two nodes in one node pair
communicate with each other through the relay. A centralized
scheduling scheme is studied as in [18], in which there exists a
control node that schedules the packet-exchange process of the
star topology. In the considered scenario, this control node is
performed by the relay R. We assume that the channel gains of
all the involved links in the considered topology can be acquired
by the control node. We also assume that the network is in the
saturation condition, i.e., a node always has packets to send
when it has the opportunity to access the channel.
For fairness, each node pair only performs packet exchange
once within one scheduling round. The whole packet-exchange
process includes two stages, i.e., MA and BC stages. In the
MA stage, all the node pairs exchange packets sequentially.
After that, the relay R jointly encodes the received packets and
broadcasts them to node pairs in the BC stage. A stage contains
a number of phases. The number of MA phases in a MA stage is
fixed with the number of involved node pairs, while a BC stage
may have separate numbers of phases in each scheduling round
according to the encoding opportunity.
In our scheduling scheme, node pairs are divided into multiple
groups (see Section VI), and packets sent by node pairs in the
same group can be encoded together. Let G⊆{1, 2,...,K} de-
note the index set of node pairs in a group. To be convenient, we
also use G to illustrate the node pairs in the following discussion.
The gth node pair in this group is defined as N
g
1
↔ N
g
2
, and the
group G totally contains |G| node pairs. The symbol sent by N
g
j
is denoted by S
N
i
j
∈M(j = 1, 2), where M represents the set
of possible symbols. Correspondingly, the signal carrying sym-
bol N
g
j
is denoted by X
N
g
j
. Considering a scenario where a node
pair N
g
t
1
↔ N
g
t
2
(g
t
∈G) transmits signals (X
N
g
t
1
,X
N
g
t
2
),the
relay R and other nodes N
g
r
j
(g
r
= g
t
, ∀g
r
∈G) in G receive
different superposed signals
1
in the MA stage:
Y
MA
R
= H
N
g
t
1
,R
X
N
g
t
1
+ H
N
g
t
2
,R
X
N
g
t
2
+ Z
n
(1)
Y
MA
N
g
r
j
= H
N
g
t
1
,N
g
r
j
X
N
g
t
1
+ H
N
g
t
2
,N
g
r
j
X
N
g
t
2
+ Z
n
(2)
where H
m,n
denotes the channel coefficient from nodes m to
n, and Z
n
represents the noise at the receiver.
After receiving the superposed signal, the minimum dis-
tance criterion [19] is leveraged to estimate the originally
transmitted s ymbols (S
N
g
t
1
,S
N
g
t
2
) by the relay R and node
N
g
r
j
, because we assume that the original symbols are equiprob-
able and the noise is Gaussian. The estimation of the orig-
inally transmitted symbols is defined as (
ˆ
S
N
g
t
1
,
ˆ
S
N
g
t
2
)
R
or
(
ˆ
S
N
g
t
1
,
ˆ
S
N
g
t
2
)
N
g
r
j
. It is not necessary to decode the encoded
symbol (S
N
g
t
1
,S
N
g
t
2
), because nodes can directly use it to de-
code their intended symbols i n PNC. In the whole MA stage,
for a group G,therelayR and node N
g
j
receive a number of
encoded symbols
ˆ
S
R
= {(
ˆ
S
N
g
1
,
ˆ
S
N
g
2
)
R
: ∀g ∈G}and
ˆ
S
O
N
g
j
=
{(
ˆ
S
N
g
t
1
,
ˆ
S
N
g
t
2
)
N
g
j
: g
t
= g, ∀g
t
∈G}.LetM
C
denote the set of
the possible encoded symbols, and C :(M×M)
|G|
→M
C
denote the encoding mapping. The symbols in
ˆ
S
R
are encoded
into a new symbol C(
ˆ
S
R
) by relay R. Section IV discusses how
to design the encoding function C(·).
In the BC stage, the encoded symbol C(
ˆ
S
R
) is broadcasted
to all nodes in G. We define X
C
as the signal that carries the
encoded symbol C(
ˆ
S
R
). The signal received by node N
g
j
can
be written as
Y
BC
N
g
j
= H
R,N
g
j
X
C
+ Z
n
. (3)
After receiving this signal, node N
g
j
can decode the intended
symbol from C(
ˆ
S
R
) by the overheard symbols in
ˆ
S
O
N
g
j
.
IV. N
ODE-PAIR ENCODING WITHIN THE GROUP
This section introduces how t o design an appropriate joint en-
coding method C(·). For a node pair N
g
j
↔ N
g
j
(j ∈{1, 2}, j =
j) in a certain group G, our purpose in the design of C(·) is to: 1)
ensure that node N
g
j
can decode signal S
N
g
j
sent by N
g
j
(when
1
We neglect scenarios that a node in other groups of the considered network
receives a signal superposed by (X
N
g
t
1
,X
N
g
t
2
) because the two signals are
not related to this node.