基于IEEE 分布式协议的物理层网络编
码非饱和吞吐量分析
林世俊1，付立群2
1 厦门大学通信工程系，厦门 361005
2 香港中文大学网络编码研究所，香港
摘要：在这篇文章中，我们基于IEEE 分布式协议，研究两个用户群通过一个中继节点
的网络场景下物理层网络编码的非饱和吞吐量性能。分析该场景的难点在于：该场景中存在两
种节点——用户节点和中继节点。这使得传统的分布式网络分析方法不能适用。幸运的是，我
们发现可以通过将该系统分成几个子系统进行分别建模。分析结果表明：物理层网络编码的吞
吐量增益主要由一个网络编码数据包中包含两个数据包信息的概率决定。因此，物理层网络编
码更适用于具有对等业务的平衡网络流量场景。此外，我们进一步推导出可以使网络吞吐量最
大化的最优用户节点数据包发送概率。最后，我们通过仿真验证了我们模型的精确性并分析系
统参数和网络吞吐量的关系。
关键词：通信与信息系统，物理层网络编码，IEEE ，非饱和吞吐量分析
中图分类号： TN91
Unsaturated throughput analysis of
physical-layer network coding based on IEEE
distributed coordination function
LIN Shi-Jun1, FU Li-Qun2
1 Department of Communication Engineering, Xiamen University, Xiamen 361005
2 Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong
Abstract: In this paper, we investigate the throughput performance of physical-layer
network coding (PNC) under the IEEE 802:11 distributed coordination function (DCF). We
consider the wireless network that two client groups communicate with each other across one
relay node, and focus on the unsaturated network case. The di�culty in modeling the relay
systems under the IEEE 802:11 DCF is that the minimum contention window sizes of the
client nodes and the relay node may be di�erent, which makes the traditional throughput
- 1 -
analysis methods for the non-relay wireless networks inapplicable. Fortunately, we �nd that
the relay system can be decomposed into four parts and respectively modeled. Analytical
results show that the throughput gain of PNC scheme is heavily a�ected by the probability
that a transmitted network-coding (NC) packet contains the information of two packets. The
implication is that the throughput bene�t of PNC is more signi�cant for bidirectional
isochronous tra�c with rate requirements. We further derive an approximate closed-form
solution of the optimal transmission probability of client nodes that maximizes the PNC
network throughput. We validate our analytical model through extensive simulations and
discuss the relationship between the PNC network throughput and other system parameters,
such as the minimum contention window sizes of both the client nodes and the relay node.
Key words: Communication and Information system, Physical-layer network coding, IEEE
, unsaturated throughput analysis.
0 Introduction
Due to the broadcast nature of wireless media, wireless links operated on the same channel
may cause interference to each other. The concept of physical-layer network coding (PNC),
which makes good use of the interference, has great potential to improve the throughput of
wireless networks [1,2]. For example, PNC can improve the throughput of the simple two-way
relay channel (TWRC) by 100% [1]. However, what is less understood is the throughput gain
of PNC when it is applied to a general wireless network.
The carrier sense multiple access (CSMA) protocol is the most widely used distributed
media access control (MAC) protocol in current wireless networks. In this paper, we focus on
investigating the throughput performance of the relay system with PNC under the IEEE
distributed coordination function (DCF). In particular, we are interested in the unsaturated
network case. The unsaturated network is more practical, as in a real wireless network, nodes do
not always have packets waiting for being sent. However, both the modeling and the theoretical
analysis of the unsaturated network are more complicated. Another di�culty in modeling the
relay systems under the IEEE DCF is that the minimum contention window sizes of the
client nodes and the relay node may be di�erent. This makes the throughput analysis methods
for the traditional non-relay wireless networks inapplicable.
The main contributions of this paper are summarized as follows:
1. We derive the analytical unsaturated network throughput results of the PNC scheme, the
traditional non-physical-layer network-coding (NC) scheme, and the non-network-coding
(NNC) scheme under IEEE DCF. What's more, we �nd that for all schemes, the
relay system will be stable when the sending bu�ers of the client nodes and the relay node
- 2 -
˖ڍመڙጲ
are not always non-empty, which can be achieved by controlling the packet generation
probability and setting appropriate minimum contention window sizes of the client nodes
and the relay node.
2. We show that the throughput gain of PNC scheme is heavily a�ected by the balance factor,
�PNC , which represents the probability that when one of the client nodes occupies the
channel and sends a packet to its destination client node, the destination client node also
has a packet to be sent to the source client node if the sending bu�er of the destination
client node is not empty. Compared with the non-physical-layer NC scheme and the NNC
schemes, the throughput gain of PNC scheme becomes more signi�cant as �PNC increases.
The implication of these results is that the throughput bene�t of PNC is more signi�cant
for bidirectional isochronous tra�c with rate requirements.
3. We optimize the network throughput of PNC scheme in terms of the transmission prob-
ability of client nodes kc, and derive an approximate closed-form optimal solution of kc.
Furthermore, we discuss the relationship between the PNC network throughput and other
system parameters, such as the minimum contention window sizes of both the client nodes
and the relay node. The results show that �rst, to achieve a better throughput perfor-
mance, the minimum contention window size of the client nodes should be self-adaptive
according to the number of client nodes in the system; second, the minimum contention
window size of the relay node has little e�ect on the system throughput, and thus can be
set as small as possible to make the system stable.
Related work
Network coding is a promising technique to improve the capacity of wired or wireless
networks [3]. Originally, NC operations are applied at high-layer (not at physical layer), and
three time slots are needed for exchanging two packets between two client nodes across a relay
node. We refer to this scheme as high-layer network-coding (HNC) scheme. Considering that
two packets encountering in the air can be seen as a natural way of network coding, two new
techniques, namely, PNC [1, 2] and analog network coding (ANC) [4] are proposed to further
improve the wireless network throughput. In PNC and ANC schemes, only two time slots are
needed when exchanging two packets between two client nodes across a relay node.
In the literature, most studies of PNC are focused on the physical layer, and within a
simple TWRC network, . [5, 6]. When the PNC scheme is applied to a general network, the
transmission coordination of PNC scheme with MAC protocols should be considered. In [7],
the authors proposed a distributed MAC protocol for PNC system which can be seen as an
extension of IEEE DCF. In [8], Argyriou proposed a MAC protocol for PNC scheme,
which makes two independent packet transmissions interfere in a controlled and cooperative
- 3 -
˖ڍመڙጲ
manner. Recently, Cocco et al. presented two new schemes to solve the collision problem
in slotted ALOHA networks based on multi-user PNC scheme [9]. The coordination of MAC
protocols with ANC scheme was investigated in [10{12]. However, to the best of our knowledge,
none of the existing works analyzes the throughput performance of PNC scheme in a general
network coordinated with MAC protocols.
The throughput performance analysis of IEEE DCF is mostly on traditional NNC
network [13{21]. In [13], Bianchi �rst considered a multistage exponential backo� window, and
proposed a bi-dimensional discrete-time Markov model for the saturated single-hop network.
And henceforth, Bianchi' model was widely used and extended. In [14,15], Bianchi' model was
extended to the throughput analysis of the unsaturated network by introducing an additional
idle state. While in [16, 17] and [18, 19], Bianchi' model was extended by considering the
retransmission limit and adding the back-o� counter freezing probability, respectively. In [20,
21], the throughput performance of traditional IEEE multi-hop networks was analyzed.
Recently, several works (. [22{24]) discussed the performance of the HNC scheme coor-
dinated with several distributed MAC protocols in a relay network with one relay node and two
client groups. In [22], Umehara et al. analyzed the throughput and delay of the relay system
employing HNC scheme and slotted ALOHA protocol under two representative unbalanced
tra�c cases. In [23], Umehara et al. extended the analysis to a general single-relay multi-user
network, and discussed the achievable throughput region. And in [24], the performance of HNC
scheme coordinated with an improved slotted ALOHA protocol was analyzed. In this paper,
we propose analytical models for the throughput performance of PNC, HNC and NNC schemes
coordinated with the widely used IEEE DCF based on the relay network with one relay
node and two client groups.
The rest of this paper is organized as follows. Section 1 presents the network model and
discusses the transmission processes of the NNC, HNC and PNC schemes under the
DCF. In section 2, we develop analytical models for the unsaturated network throughput of
the NNC, HNC and PNC schemes. In section 3, we derive an approximate closed-form optimal
solution for the transmission probability of client nodes kc that maximizes the PNC network
throughput. In section 4, we carry out extensive simulations to validate our model, discuss the
relationship between the PNC network throughput and system parameters, and compare the
throughput of the NNC, HNC and PNC schemes. And section 5 concludes this paper.
- 4 -
˖ڍመڙጲ
图 1: The two-hop wireless relay network
1 System description
Network Model
In this paper, a two-hop wireless system is considered, as shown in Fig. 1. Two client
groups each with u/2 client nodes communicate with each other across a relay node. All the
nodes contend for the channel according to the IEEE DCF and work in half-duplex
mode. What's more, we only consider the bidirectional tra�c across a relay node. That is,
�rst, the relay node does not generate tra�c; second, there is no tra�c within one client group
and all the tra�c generated by the client nodes in one group will be transmitted to the client
nodes in the other group. We further make the following assumptions: 1) The relay node is
within the transmission range of all the client nodes, but the client nodes in di�erent groups
are out of the transmission range of each other. One possible network scenario is that several
laptops in one room communicate with several other laptops in another room across a relay.
2) The client nodes in the same group are within the transmission range of each other, thus,
when a client node transmits packets, the other client nodes in the same group can perform
\opportunistic listening"1 if necessary; 3) All the nodes are in the carrier-sensing range of each
other, the channel condition is ideal, and there is no hidden node (HN). In fact, HN problem
can be avoided when \RS (Re-Start) mode" is adopted, and the network has a su�ciently
large carrier sensing range [25]. In this paper, we focus on the throughput analysis of HN
free network. When HN exists, transmission failures will occur during the time that a node
successfully occupies the channel. This will result in packet retransmissions in CSMA networks.
Thus, the analysis of the network throughput could be more complicated. 4) There is perfect
synchronization for PNC system to guarantee that the relay node can extract an NC packet from
the superimposed electromagnetic (EM) waves. In practice, high-precision synchronization can
1\Opportunistic listening" means that when a client node in one group sends a packet to the relay node, all the
other nodes in the same group can also receive the packet.
- 5 -
˖ڍመڙጲ
be implemented using Locata synchronization technology [26]. Moreover, some technologies,
such as Orthogonal Frequency Division Multiplexing (OFDM) [27], can be used so that the
synchronization requirement can be relaxed.
The NNC, HNC and PNC Transmissions Coordinated with
DCF
In the DCF, a node monitors the channel activity when there is a new packet to
transmit. If the channel is idle for a distributed inter frame space (DIFS), the node sends a
packet. Otherwise, the node waits until the channel is idle for a DIFS, and then after a random
backo� time, the node sends a packet. What's more, a node will wait for a random backo� time
after a successful transmission or a collision. In addition, in the DCF, an exponential
backo� scheme is adopted. That is, at the �rst transmission attempt of a packet, the backo�
time is uniformly chosen in the range (0; CWmin� 1), where CWmin is the minimum size of the
contention window. After each failed transmission, the size of the contention window is double
until a maximum value of 2m � CWmin, where m is called the maximum backo� stage.
For easy coordination with the PNC scheme, we consider the Request To Send (RTS)/Clear
To Send (CTS) mechanism in this paper. In the RTS/CTS mechanism, the RTS and CTS
packets contain the information of the length of the data packet to be transmitted, which can
be read by the other listening nodes to update their network allocation vectors (NAV)2 [13]. In
the following, we describe the detailed RTS/CTS mechanisms based on NNC, HNC and PNC
schemes. And in the description, we assume that the propagation delay between any two nodes
is the same and equals �.
In NNC scheme, when any node (a client node or the relay node) successfully occupies
the channel, the transmission process is the same, as shown in Fig. 2a. First, when node 1
wants to send some data to node 2, it sends an RTS packet to node 2. Second, if node 2 can
receive the RTS packet of node 1 correctly, it sends a CTS packet back to node 1 after a period
of time called short inter frame space (SIFS). Third, when receiving the CTS packet, node 1
sends a data packet to node 2 after a SIFS delay. Fourth, when node 2 receives the data packet
correctly, it sends back an acknowledgement (ACK) packet after a SIFS delay for con�rmation.
In HNC scheme, the transmission process when a client node successfully occupies the
channel is the same as that in NNC scheme, as described above. And, when a client node
transmits a packet, the other client nodes in the same group perform \opportunistic listening",
which makes the client nodes can decode all the NC packets from the relay node if there
are no signi�cant reception errors. In the transmission process when the relay node occupies
the channel, the CTS and ACK packets from di�erent client nodes should be transmitted at
2In protocol, the NAV represents the number of microseconds the sending node intends to hold the channel
busy.
- 6 -
˖ڍመڙጲ
PacketNode 1
PacketSIFS
SIFS
Node 2 SIFS
DIFS
NC
packet
Relay
node
NC
packet
SIFS DIFS
NC
packet
SIFS
Client
node 1
SIFS
Client
node 2
NC
packet
Packet
SIFS
SIFS SIFS
(c) Transmission process of PNC scheme when a client node occupies the channel
(d) Transmission process of PNC scheme when the relay node occupies the channel
SIFS DIFS
Relay
node
Client
node 1
Client
node 2
Relay
node
Client
node 1
Client
node 2
(a) Transmission process of NNC scheme when any node occupies the channel and
transmission process of HNC scheme when a client node occupies the channel
(b) Transmission process of HNC scheme when the relay node occupies the channel
RTS
RTS
CTS
CTS
ACK
ACK
SIFS
+2
SIFS
+ 2
SIFS
+2
RTS CTS
RTS CTS
RTS CTS
CTS
SIFS
+2
SIFS
+
ACK
ACK
ACK
ACK
SIFS
+2
SIFS
+
DIFS
+
DIFS
+
PacketSIFS DIFSRTS CTS ACK
SIFS
+2
SIFS
+2
RTS CTS ACK
SIFS
+2
CTS ACK
SIFS
+2
DIFS
+
NC
packet
SIFS SIFS RTS CTS ACK
SIFS
+2
DIFS
+
NC
packet
SIFSRTS
NC
CTS
NC
ACK
SIFS
+2
SIFS
+2
DIFS
NC
packet
SIFS SIFS RTS CTS ACK
SIFS
+2
DIFS
+
图 2: Successful transmission processes of all schemes
di�erent sub-time-slots to guarantee that the relay node can receive the CTS and ACK packets
from di�erent client nodes correctly, as shown in Fig. 2b. The transmission process is as follows:
First, the relay node broadcasts an RTS packet to both client node 1 and client node 2. The
RTS packet contains the transmission order of the CTS and ACK packets of client node 1 and
client node 2. Second, after the RTS packet correctly arrives at both the client nodes, the two
client nodes wait for a SIFS delay �rst, and then send two sequent CTS packets to the relay
node with a SIFS time interval respectively according to the order given in the RTS packet.
Third, after the CTS packets are correctly received, the relay node waits for a SIFS delay �rst
and then sends an NC packet to both client node 1 and client node 2. Fourth, after the NC
packet is correctly received by both the client nodes for a SIFS time, the two client nodes
respectively send two sequent ACK packets to the relay node according to the order given in
the RTS packet for con�rmation.
In PNC scheme, the transmission processes of a client node and the relay node are di�erent
when they successfully occupy the channel. Fig. 2c shows the transmission process of the PNC
scheme when a client node occupies the channel. When client node 1 wants to send a data
packet to client node 2, it sends an RTS packet with the information of the client node 2 to
the relay node. If the relay node can receive the RTS packet correctly, it broadcasts a CTS
packet to both client node 1 and client node 2 after a SIFS delay. When correctly receiving the
CTS packet, each client node waits for a SIFS delay �rst, and then sends a data packet to the
relay node. In the case that client node 2 does not have a data packet waiting for being sent to
the client node 1 when it receives the CTS packet from the relay node, client node 2 sends an
empty packet. Under the assumption of perfect synchronization, the relay node can deduce an
- 7 -
˖ڍመڙጲ
图 3: Transmission process when collision occurs
NC data packet from the received superimposed EM waves, and store it in its sending bu�er.
And, after a SIFS delay, the relay node broadcasts an ACK packet to both the client nodes for
con�rmation.
Fig. 2d shows the transmission process of the PNC scheme when the relay node occupies
the channel. When there is an NC data packet in the sending bu�er of the relay node waiting
for being sent to client node 1 and client node 2, the relay node broadcasts an RTS packet
to the two client nodes. If both the client nodes can receive the RTS packet correctly, each
of them sends a CTS packet to the relay node after a SIFS delay. Under the assumption of
perfect synchronization, the relay node can deduce an NC CTS packet. If the NC CTS packet
is correct, the relay node waits for a SIFS delay and then broadcasts an NC data packet to
both the client nodes. After correctly receiving the NC data packet, each client node sends
back an ACK packet to the relay node after a SIFS delay. By checking the overlapped ACK
packets, the relay node knows whether the NC data packet is correctly received or not.
When two or more nodes send RTS packets at the same time, collision occurs and no node
can successfully occupy the channel. In this case, the transmission processes of all schemes are
the same, which is illustrated in Fig. 3.
2 Throughput analysis
In this section, we model the relay system based on the NNC, HNC and PNC schemes, and
analyze their unsaturated network throughput performances. Since there are two kinds of nodes
in the relay system, the whole system will be separated into four parts, and be respectively
modeled. We make the following assumptions and approximations in the following discussions.
We assume that in each time slot, each client node generates a packet with a probability
g, and the sending bu�er of each client node is big enough and thus never full. And when g is
given, we make the following approximations:
1. The collision probability that a node transmits is independent and constant, regardless
of the number of failed transmissions [13], and that of each client node is the same.
This approximation could be more accurate as CWmin and u become larger, since the
collision probability means the probability of collision seen by a transmitted packet on
- 8 -
˖ڍመڙጲ
the channel [13].
2. The probability that a node transmits when its sending bu�er is not empty is constant, and
that of each client node is the same. Indeed, the probability that a node transmits when
its sending bu�er is not empty would vary over time since the time slots with collisions
are shorter than the time slots with successful transmissions. This approximation could
be more accurate when the collision probability is smaller.
3. The probability that the sending bu�er of a node is not empty is constant, and that of
each client node is the same.
All the above approximations have been veri�ed through simulations (see Section ). And
based on these approximations, the relay system can be modeled by four separate processes:
one is the changing process of the number of packets in a client node's sending bu�er; one is
the channel contention process of the client nodes based on the DCF when their sending
bu�ers are not empty; one is the changing process of the number of packets in the relay node's
sending bu�er; and the last one is the channel contention process of the relay node based on
the DCF when its sending bu�er is not empty. In the following, we analyze the network
unsaturated throughput of the three schemes by modeling the above processes.
The changing process of the number of packets in a client node's
sending bu�er
In this subsection, we focus on modeling the changing process of the number of packets in a
client node's sending bu�er. In NNC and HNC schemes, the number of packets in a client node's
sending bu�er will keep unchanged when one of the client nodes in the other group occupies
the channel. However, in PNC scheme, the number of packets in a client node's sending bu�er
may change when one of the client nodes in the other group occupies the channel. Therefore,
the changing process of the number of packets in a client node's sending bu�er in PNC scheme
should be separately modeled.
Let pc, hc and PNE c respectively denote the probability that the collision occurs when
a client node transmits, the probability that a client node transmits under the condition that
its sending bu�er is not empty, and the probability that the sending bu�er of a client node is
not empty. Then, the probability that a client node transmits a packet successfully under the
condition that its sending bu�er is not empty equals hc(1� pc).
Let Sc(t) represent the number of packets in the sending bu�er of a client node at discrete
time t. In the system, the time is slotted, and t and t+1 respectively represent the beginnings
of two adjacent time slots. Considering that in all schemes, Sc(t + 1) is determined by Sc(t)
and the number of packets that arrive at and depart from the sending bu�er of the client node
during the time [t; t+ 1], Sc(t) can be modeled with a Markov chain.
- 9 -
˖ڍመڙጲ
!1 (1 ) (1 )
(1 )
c c
c c
h p g
g h p
! "
(1 )(1 )c ch p g
! "1 (1 ) (1 )
(1 )
c c
c c
h p g
g h p
! "
(1 )(1 )c ch p g (1 )(1 )c ch p g
! "1 (1 )c cg h p ! "1 (1 )c cg h p
图 4: The Markov chain of the changing process of Sc(t) in NNC and HNC schemes
1. The changing process of Sc(t) in NNC and HNC schemes:
In NNC and HNC schemes, Sc(t) may change because of the following two events: 1) A
new packet is generated by the client node in the current time slot, and the probability of this
event equals g. 2) In the current time slot, the client node successfully occupies the channel
and sends a packet when its sending bu�er is not empty, and the probability of this event
equals hc(1� pc). Considering that the above two events may both happen during a time slot,
the transition diagram of the Markov chain of the changing process of Sc(t) in NNC and HNC
schemes is shown in Fig. 4. The one-step transition probabilities are:
PfSc(t+ 1) = 0 jSc(t) = 0g = 1� g; (1a)
PfSc(t+ 1) = 1 jSc(t) = 0g = g; (1b)
PfSc(t+ 1) = i jSc(t) = ig =
[1� hc(1� pc)] (1� g) + g � hc(1� pc); i � 1; (1c)
PfSc(t+ 1) = i+ 1 jSc(t) = ig =
g [1� hc(1� pc)] ; i � 1; (1d)
PfSc(t+ 1) = i� 1 jSc(t) = ig =
hc(1� pc)(1� g); i � 1; (1e)
PfSc(t+ 1) = j jSc(t) = ig = 0; ji� jj � 2: (1f)
The explanations of equation (1) are as follows:
1. Equation (1a) and (1b) represent that when the sending bu�er of a client node is empty,
only the event that a new packet is generated may happen.
2. Equation (1c) states that in NNC and HNC schemes, when the sending bu�er of a client
node is not empty, the number of packets in its sending bu�er may keep unchanged under
the following two cases: one is that no packet is generated and no packet is successfully
transmitted, and the probability of this case equals [1� hc(1� pc)] (1� g); the other case
is that there is a new packet generated and a packet transmitted successfully, and the
probability of this case equals g � hc(1� pc).
- 10 -
˖ڍመڙጲ
3. Equation (1d) accounts the fact that in NNC and HNC schemes, when the sending bu�er
of a client node is not empty, the number of packets in the sending bu�er may increase
by one if there is a packet generated but no packet is successfully transmitted.
4. Equation (1e) states that in NNC and HNC schemes, in the case that the sending bu�er
of a client node is not empty, the number of packets in the sending bu�er may decrease
by one if there is a packet successfully transmitted but no packet is generated.
5. Equation (1f) states the assumption that only one packet may be generated in each time
slot and the fact that only one packet is transmitted in a successful transmission.
We next calculate the stationary probabilities.
Let �c(i) be the stationary probability of Sc(t), which equals lim
t!1
P fSc(t) = ig. According
to the balance equations of steady states
+1P
i=0
�c(i) � PfSc(t+ 1) = j jSc(t) = ig = �c(j), (j � 0),
�c(i) in NNC and HNC schemes can be calculated by:8<: �c(1) =
g
hc(1�pc)(1�g) � �c(0);
�c(i) =
h
g�g�hc(1�pc)
hc(1�pc)(1�g)
ii�1
� �c(1); i � 2:
Then, if g�g�hc(1�pc)
hc(1�pc)(1�g) is less than one, the stationary probabilities exit. According to the
equation
+1P
i=0
�c(i) = 1, �c(0) in NNC and HNC schemes equals:
�c(0) =
hc(1� pc)� g
hc(1� pc) : (2)
Then, in NNC and HNC schemes, the probability that the sending bu�er of a client node
is not empty PNE c equals:
PNE c = 1� �c(0) = g
hc(1� pc) : (3)
In equation (3), g can be seen as the packet arrival probability, which is a given system
parameter; while hc(1� pc) can be seen as the packet departure probability when the sending
bu�er of the considered client node is not empty. Equation (3) shows that the changing process
of the number of packets in a client node's sending bu�er, and the channel contention process
of the client nodes based on the DCF are connected together. In fact, hc(1 � pc) also
represents the system service probability when the sending bu�er of a client node is not empty
in NNC and HNC schemes. Thus, a bigger hc(1� pc) will lead to a bigger system service rate
and then a higher system throughput of the NNC and HNC schemes.
2. The changing process of Sc(t) in PNC scheme:
Next we discuss the model of the changing process of Sc(t) in PNC scheme. Since in PNC
scheme, the number of packets in a client node's sending bu�er may change when one of the
- 11 -
˖ڍመڙጲ
1 g!
g
2
_
2
_
1 (1 )(1 ) (1 )
(1 )(1 )
c c PNC NE c
c c PNC NE c
h p P g
g h p P
! "# # $ #% &
$ ' # $
2
_1 (1 )(1 )c c PNC NE cg h p P ! "# # $% &
2
_(1 )(1 )(1 )c c PNC NE ch p P g ! " !
图 5: The Markov chain of the changing process of Sc(t) in PNC scheme
client nodes in the other group occupies the channel, the model of the changing process of Sc(t)
in PNC scheme is di�erent from the one in NNC and HNC schemes.
In PNC scheme, Sc(t) of a client node n
x
c may change because of the following three
events: 1) In the current time slot, there is a new packet generated by client node nxc , and
the probability of this event equals g; 2) In the current time slot, client node nxc successfully
occupies the channel when its sending bu�er is not empty, and the probability of this event
equals hc(1� pc); 3) In the current time slot, when the sending bu�er of client node nxc is not
empty, one of the client nodes in the other group, . client node nyc , successfully occupies
the channel with client node nxc as the destination client node and client node n
x
c has a packet
waiting for being sent to client node nyc . The third event only happens in PNC scheme, which
makes the changing process of Sc(t) in PNC scheme di�erent from the one in the NNC and
HNC schemes.
In the following, we calculate the probability of the third event. Since the probability that
a client node occupies the channel successfully equals PNE chc(1 � pc), the probability that
the channel is successfully occupied by a node in one client group equals u
2
� PNE chc(1 � pc).
Assume that every client node in the other group has the same probability to be the destination
client node. Then, the probability that client node nxc is the destination client node when the
channel is occupied by one of the client nodes in the other group equals 1u/2
� u
2
PNE chc(1� pc).
Therefore, when the sending bu�er of nxc is not empty, the probability that the channel is
occupied by one of the client nodes in the other group with nxc as the destination client node
equals PNE c � 1u/2
u
2
PNE chc(1 � pc). Let �PNC 2 [0; 1] be the balance factor in PNC scheme,
which represents the probability that when the channel is successfully occupied by a client
node, its destination client node has a packet waiting for being sent to the source client node
under the condition that the sending bu�er of the destination client node is not empty. Then,
the probability of the third event equals �PNC �
�
PNE c
1
u/2
u
2
PNE chc(1� pc)
�
, which can be
simpli�ed to �PNCP
2
NE chc(1� pc). Considering that the �rst and the second events, the �rst
and the third events may both happen in the same time slot, but the second and the third
- 12 -
˖ڍመڙጲ
events can not both happen in the same time slot because the channel can only be occupied
by one node in a time slot, then, the transition diagram of the Markov chain of the changing
process of Sc(t) in PNC scheme is shown in Fig. 5, and the one-step transition probabilities
are:
PfSc(t+ 1) = 0 jSc(t) = 0g = 1� g; (4a)
PfSc(t+ 1) = 1 jSc(t) = 0g = g; (4b)
PfSc(t+ 1) = i jSc(t) = ig =�
1� hc(1� pc)(1 + �PNCP 2NE c)
�
(1� g)
+ g � hc(1� pc)(1 + �PNCP 2NE c); i � 1; (4c)
PfSc(t+ 1) = i+ 1 jSc(t) = ig =
g
�
1� hc(1� pc)(1 + �PNCP 2NE c)
�
; i � 1; (4d)
PfSc(t+ 1) = i� 1 jSc(t) = ig =
hc(1� pc)(1 + �PNCP 2NE c)(1� g); i � 1; (4e)
PfSc(t+ 1) = j jSc(t) = ig = 0; ji� jj � 2: (4f)
The explanations of equation (4) are as follows:
1. Equation (4a) and (4b) state that in PNC scheme, when the sending bu�er of a client
node is empty, only the �rst event may happen.
2. Equation (4c) accounts the fact that in PNC scheme, when the sending bu�er of a client
node is not empty, the number of packets in its sending bu�er may keep unchanged under
the following three cases: i) both the �rst and the second events happen; ii) both the �rst
and the third events happen; iii) none of the events happens.
3. Equation (4d) states that in PNC scheme, in the case that the sending bu�er of a client
node is not empty, the number of packets in its sending bu�er may increase by one when
the �rst event happens but neither of the second and the third events happens.
4. Equation (4e) accounts the fact that in PNC scheme, in the case that the sending bu�er
of a client node is not empty, the number of packets in the sending bu�er may decrease
by one when the �rst event does not happen and one of the other two events happens.
5. Equation (4f) states the assumption that only one packet may be generated in each time
slot and the fact that only one packet is transmitted in a successful transmission.
In the following, we calculate the stationary probability �c(i) in PNC scheme.
- 13 -
˖ڍመڙጲ
According to the balance equations of the steady states
+1P
i=0
�c(i) � PfSc(t+ 1) = j jSc(t) = ig =
�c(j); (j � 0), �c(i) in PNC scheme can be expressed by:8<: �c(1) =
g
hc(1�pc)(1+�PNCP 2NE c)(1�g) � �c(0);
�c(i) =
h
g�g�hc(1�pc)(1+�PNCP 2NE c)
hc(1�pc)(1+�PNCP 2NE c)(1�g)
ii�1
� �c(1); i � 2:
If g�g�hc(1�pc)(1+�PNCP
2
NE c)
hc(1�pc)(1+�PNCP 2NE c)(1�g) is less than one, �c(i) exits. Since
+1P
i=0
�c(i) = 1, �c(0) equals:
�c(0) =
hc(1� pc)(1 + �PNCP 2NE c)� g
hc(1� pc)(1 + �PNCP 2NE c)
: (5)
Then, the probability that the sending bu�er of a client node is not empty PNE c equals:
PNE c = 1� �c(0) = g
hc(1� pc)(1 + �PNCP 2NE c)
: (6)
In equation (6), hc(1� pc)(1+�PNCP 2NE c) is the sum of the probabilities that the second
and the third events happen, which indeed represents the total packet departure probability or
total system service probability when there are packets in the sending bu�er of the considered
client node. Thus, a bigger hc(1� pc)(1+�PNCP 2NE c) will lead to a bigger system service rate
and then a higher system throughput in PNC scheme. Furthermore, we have the following two
observations: 1) The throughput gain of PNC scheme comes from the third event, which does
not happen in the other two schemes. 2) The balance factor, �PNC , has a signi�cant impact
on the throughput performance of PNC scheme since it directly determines the probability of
the third event.
The changing process of the number of packets in the relay node's
sending bu�er
In NNC, HNC, and PNC schemes, the changing processes of the number of packets in the
relay node's sending bu�er are similar. The only di�erence is the packet arrival probability.
Thus, in the following, we �rst propose a common model for all schemes, and then discuss the
di�erence of the packet arrival probability in the three schemes.
Let pr, hr and PNE r respectively denote the probability that a transmitted packet of
the relay node encounters a collision, the probability that the relay node transmits under the
condition that its sending bu�er is not empty, and the probability that the sending bu�er of
the relay node is not empty. Then, the probability that the relay node successfully occupies
the channel when its sending bu�er is not empty equals hr(1�pr). Let gr be the packet arrival
probability of the relay node's sending bu�er. Let Sr(t) denote the number of packets in the
sending bu�er of the relay node at discrete time t. Since Sr(t+ 1) can be determined by Sr(t)
- 14 -
˖ڍመڙጲ
(1 )r rh p
1 rg
rg rg rg
(1 )r rh p (1 )r rh p
1 (1 )r r rg h p 1 (1 )r r rg h p
图 6: The Markov chain of the changing process of Sr(t)
and the number of packets that arrive at and depart from the sending bu�er of the relay node
during the time [t; t+ 1], Sr(t) can be modeled with a Markov chain.
In all schemes, Sr(t) will change when one of the following two events occurs: 1) In the
current time slot, there is a packet arriving at the sending bu�er of the relay node, and the
probability of this event equals gr. 2) In the current time slot, there is a packet successfully
transmitted by the relay node, and the probability of this event equals hr(1� pr). Considering
that the above two events cannot both happen in the same time slot, the transition diagram
of the Markov chain of the changing process of Sr(t) is shown in Fig. 6, and the one-step
transition probabilities are:
PfSr(t+ 1) = 0 jSr(t) = 0g = 1� gr; (7a)
PfSr(t+ 1) = i jSr(t) = ig = 1� gr � hr(1� pr); i � 1; (7b)
PfSr(t+ 1) = i+ 1 jSr(t) = ig = gr; i � 0; (7c)
PfSr(t+ 1) = i� 1 jSr(t) = ig = hr(1� pr); i � 1; (7d)
PfSr(t+ 1) = j jSr(t) = ig = 0; ji� jj � 2: (7e)
The explanations of equation (7) are as follows:
1. Equation (7a) states that when the sending bu�er of the relay node is empty, only the
�rst event may occur.
2. Equation (7b) represents that in the case of the sending bu�er of the relay node being
not empty, Sr(t) will keep unchanged when neither of the two events occurs.
3. Equation (7c) accounts the fact that no matter if the sending bu�er of the relay node is
empty or not, Sr(t) may increase by one when the �rst event occurs.
4. Equation (7d) states that in the case that the sending bu�er of the relay node is not
empty, Sr(t) may decrease by one when the second event occurs.
5. Equation (7e) accounts the fact that only one packet is transmitted when a node success-
fully occupies the channel.
- 15 -
˖ڍመڙጲ
We next calculate the stationary probabilities of Sr(t).
Let �r(i) be the stationary probability of Sr(t), which equals lim
t!1
P fSr(t) = ig. Then,
according to the balance equations of the steady states
+1P
i=0
�r(i) � PfSr(t+ 1) = j jSr(t) = ig =
�r(j), (j � 0), we have:
�r(i) = �r(0) � �ir; (i � 0); (8)
where �r equals
gr
hr(1�pr) . When �r < 1, �r(0) can then be calculated according to the equation
+1P
i=0
�r(i) = 1. That is, �r(0) equals 1� �r.
Then, for all schemes, the probability that the relay node's sending bu�er is not empty
equals:
PNE r = 1� �r(0) = gr
hr(1� pr) : (9)
In equation (9), gr is determined by the channel contention process of the client nodes,
while hr(1�pr) is determined by the channel contention process of the relay node. That is, the
changing process of Sr(t), the channel contention process of the client nodes, and the channel
contention process of the relay node are connected together through equation (9).
In the following, we discuss the di�erence of gr in the three schemes.
In NNC and PNC schemes, when one of the client nodes occupies the channel successfully,
the relay node will receive a packet and directly store it in the sending bu�er. Thus, the packet
arrival probability of the relay node's sending bu�er, gr, equals the probability that one of the
client nodes occupies the channel successfully. Therefore, in NNC and PNC schemes, gr equals:
gr = u � PNE chc(1� pc): (10)
图 7: The packets arrival
ow at the relay node in HNC scheme
However, in HNC scheme, since the network coding operation occurs at the high layer,
the packets received from the client nodes are not directly stored in the sending bu�er. The
packets arrival
ow at the relay node is shown in Fig. 7. The packets from the client group
1 and client group 2 are respectively stored in the receiving bu�er 1 and receiving bu�er 2.
And, considering that the packet arrival probabilities of the receiving bu�ers are the same,
the network coding operation is done only when both of the bu�ers are not empty. After the
network coding operation, an NC packet is generated and stored in the sending bu�er of the
- 16 -
˖ڍመڙጲ
relay node. Thus, the packet arrival probability of the sending bu�er of the relay node equals
that of one of the receiving bu�ers in the relay node. That is, in HNC scheme, gr equals:
gr =
u
2
� PNE chc(1� pc): (11)
The relationships among the variables
In this subsection, we discuss the channel contention process of the client nodes and the
relay node, and the relationships among variables pc, hc, PNE c, pr, hr, and PNE r.
When the sending bu�er of a node is not empty, no matter how many packets there are in
the sending bu�er, the node will contend for the channel in the same way according to the
DCF. Thus, according to Bianchi's model [13], the relationships between the probability that
a node transmits under the condition that its sending bu�er is not empty and the probability
that a transmitted packet of a node encounters a collision are given as follows:
hc =
2(1� 2pc)
(1� 2pc)(Wc + 1) + pcWc [1� (2pc)m] ; (12)
hr =
2(1� 2pr)
(1� 2pr)(Wr + 1) + prWr [1� (2pr)m] ; (13)
where Wc and Wr are respectively the minimum contention window size of a client node and
the relay node, and m is the maximum backo� stage of any node.
What's more, since the collision probability that a node transmits is also the probability
that at least one of the other nodes transmits in a slot time, in all schemes, we have:
pc = 1� (1� PNE chc)u�1(1� PNE rhr); (14)
pr = 1� (1� PNE chc)u: (15)
Given g, all the variables can be solved by the above equations. In particular, in NNC
scheme, the values of pc, hc, PNE c, pr, hr, PNE r, and gr can be obtained by solving equations
(3), (9), (10), (12), (13), (14), and (15); in HNC scheme, the values of pc, hc, PNE c, pr, hr,
PNE r, and gr can be obtained by solving equations (3), (9), (11), (12), (13), (14), and (15);
in PNC scheme, the values of pc, hc, PNE c, pr, hr, PNE r, and gr can be obtained by solving
equations (6), (9), (10), (12), (13), (14), and (15).
The stability conditions of the relay system are as follows. In NNC and HNC schemes,
the relay system is stable when g�g�hc(1�pc)
hc(1�pc)(1�g) < 1 and
gr
hr(1�pr) < 1, which can be simpli�ed to
g < hc(1 � pc) (or PNE c < 1) and gr < hr(1 � pr) (or PNE r < 1). While in PNC scheme,
the relay system is stable when g�g�hc(1�pc)(1+�PNCP
2
NE c)
hc(1�pc)(1+�PNCP 2NE c)(1�g) < 1 and
gr
hr(1�pr) < 1, which can be
simpli�ed to g < hc(1�pc)(1+�PNCP 2NE c) (or PNE c < 1) and gr < hr(1�pr) (or PNE r < 1).
That is, for all schemes, the relay system is stable when PNE c and PNE r are both less than
one. The implications of these stable conditions are as follows: 1) The proposed model can only
- 17 -
˖ڍመڙጲ
be used to analyze the unsaturated scenario, thus, the packet generation probability g should
be small enough to ensure that the system is unsaturated. 2) In order to avoid the queue in
the relay node being in�nitely long, the relay node should have a large enough opportunity to
access the channel, which can be achieved by setting Wc and Wr appropriately. In fact, since
there are u client nodes and only one relay node, Wr should be set much smaller than Wc.
Throughput calculation
The network throughput, Qc, can be de�ned as the ratio of the average time used by
the client nodes to successfully transmit the payload information in a slot time to the average
length of a slot time.
In the following, we discuss the calculation of Qc. The probability that the channel is
successfully occupied by one of the client nodes, Ps c, and the probability that the channel is
successfully occupied by the relay node, Ps r, respectively equal:
Ps c = u � PNE chc(1� pc); (16)
Ps r = PNE rhr(1� pr): (17)
Furthermore, since the probability that no node transmits a packet equals (1�PNE chc)u(1�
PNE rhr), the probability that at least one node transmits a packet, Ptr, then equals:
Ptr = 1� (1� PNE chc)u(1� PNE rhr): (18)
After obtaining Ps c, Ps r, and Ptr, we are ready to calculate the average length of a slot
time in the unsaturated case. In the unsaturated case, a node does not transmit in the following
two cases: 1) the sending bu�er of the node is empty; 2) the backo� counter of the node does
not reach zero. In fact, for any node, the sending bu�er being empty can be regarded as the
value of the backo� counter being in�nitely large. Thus, when the channel is idle in a slot
time, we can postulate that the backo� counters of all nodes decrease by one and no backo�
counter reaches zero. Then, the average length of a slot time can be calculated based on the
fact that with probability (1 � Ptr), the slot time is idle; with probability Ps c, the slot time
is successfully occupied by a client node; with probability Ps r, the slot time is successfully
occupied by the relay node; with probability (Ptr � Ps r � Ps c), a collision occurs. Let TAST
be the average length of a slot time in the unsaturated case. Then, TAST can be calculated by:
TAST = (1� Ptr)� + Ps cTs c + Ps rTs r
+(Ptr � Ps r � Ps c)Tc;
(19)
where Ts c, Ts r, and Tc are respectively the average time that a successful transmission of
a client node experiences, the average time that a successful transmission of the relay node
experiences, and the average time that a collision experiences. In di�erent schemes, the values
- 18 -
˖ڍመڙጲ
of Ts c, Ts r, and Tc may be di�erent, which can be calculated according to the analysis in
section . The symbol � is the basic unit of the value of backo� counter described in the
DCF.
Therefore, the network throughput Qc can be expressed by:
Qc =
Ps cTL c
TAST
; (20)
where TL c is the average time used by a client node to transmit the total amount of the payload
information of a packet.
TL c is di�erent in di�erent schemes. In NNC and HNC schemes, when a client node
occupies the channel, the total amount of the payload information in the transmitted packet
equals the payload size SPL. Then, TL c in NNC and HNC schemes equals SPL/Rlink, where
Rlink is the physical link rate.
In PNC scheme, when a client node occupies the channel, the probability that the trans-
mitted packet contains the information of two packets equals PNE c�PNC , and the proba-
bility that the transmitted packet only contains the information of one packet equals (1 �
PNE c�PNC). Then, the average amount of payload information in the transmitted packet
equals [2SPL � PNE c�PNC + SPL � (1� PNE c�PNC)], which can be simpli�ed to SPL(1+PNE c�PNC).
Therefore, TL c in PNC scheme equals
SPL(1+PNE c�PNC)
Rlink
.
3 Throughput maximization of the PNC relay system
In this section, we focus on the throughput maximization of the PNC relay system. We
consider the nearly saturated case, that is, the packet generation probability g is set to its
maximum value which makes PNE c close to one. The reason is that the impact of system
parameters on the throughput will be less signi�cant when g is smaller. In particular, in the
extreme case that g equals zero, the throughput will equal zero under any system parameters.
In the nearly saturated case, the throughput in PNC scheme, Qc jPNE c!1 , approximately
equals:
Qc jPNE c!1 =
SPL/Rlink � Ps c(1 + �PNC)
TAST
: (21)
Let kc and kr respectively denote the transmission probability of a client node and the
relay node. Then, kc = PNE chc and kr = PNE rhr. Equations (16), (17) and (18) can be
simpli�ed.
Ps c = u � kc(1� kc)u�1(1� kr); (22)
Ps r = kr(1� kc)u; (23)
Ptr = 1� (1� kc)u(1� kr): (24)
- 19 -
˖ڍመڙጲ
According to equations (9), (10), (16) and (17), Ps c equals Ps r in PNC scheme. Then,
kr =
u � kc
1� kc + u � kc : (25)
Furthermore, according to equations (19), (21), (22), (23), (24) and (25), Qc jPNE c!1
equals:
Qc jPNE c!1 =
SPL/Rlink�(1+�PNC)
Tc(1�kc+u�kc)�(Tc��)(1�kc+u�kc)(1�kc)u
u�kc(1�kc)u +(Ts c+Ts r���Tc)
: (26)
In equation (26), SPL, Rlink, �PNC , u, Ts c, Ts r, Tc, and � are all given system parameters,
and only kc is the control variable. That is, Qc jPNE c!1 can be determined by kc.
In the following, we discuss the maximization of Qc jPNE c!1 .
Let Y denote u�kc(1�kc)
u
Tc(1�kc+u�kc)�(Tc��)(1�kc+u�kc)(1�kc)u . Then, according to equation (26),
Qc jPNE c!1 is maximized when Y is maximized.
Lemma 1. As kc increases from 0 to 1, Y �rst increases to a maximum value and then
decreases.
The proof of Lemma 1 is in the Appendix. Based on Lemma 1, the following theorem can
be obtained.
Theorem 1. The optimal kc that maximizes the network throughput approximately equals:
kc =
�(u+1)�+
q
(u+1)2�2+4�[Tc(u2�u)+ 12u(u+1)(Tc��)]
2Tc(u2�u)+u(u+1)(Tc��) :
(27)
Proof. According to Lemma 1, there is only one kc 2 [0; 1] which makes Y reach its maximum
value. The kc which maximizes Y can be obtained by imposing the derivative of Y with respect
to kc equal 0. After some simpli�cations, we have:
Tc
�
(u2 � u)k2c + (u+ 1)kc � 1
�
+ (Tc � �)(1� kc)u+1 = 0: (28)
According to the Taylor series approximation, under the condition kc � 1, we have:
(1� kc)u+1 � 1� (u+ 1)kc + (u+ 1)u
2
k2c : (29)
Then, according to equations (28) and (29), equation (27) can be obtained.
Theorem 1 provides the optimal value of kc that maximizes the nearly saturated throughput
of the PNC relay system. Considering that PNE c is close to one in the nearly saturated case,
the value of kc is close to the value of hc. Then, adjusting kc is equivalent to adjusting hc,
which can be achieved by adjusting Wc in a practical system. Furthermore, the maximization
process of the PNC relay system is general and can be applied to the relay system with other
schemes (., NNC and HNC).
- 20 -
˖ڍመڙጲ
表 1: Simulation parameters
Parameter Value Parameter Value
� 20 us CTS 112 bits
SIFS 10 us ACK 112 bits
DIFS 50 us Packet size
8472
bits
Physical
header
128 bits Payload size
8184
bits
RTS 160 bits
Propagation
delay
1 us
4 Simulations results
In the simulation, the protocol is adopted and the physical link rate equals 11Mb/s.
Other parameters are shown in Table 1.
Model validation
To validate our analytical models of NNC, HNC and PNC schemes, we calculate the
network throughputs of these schemes under di�erent system parameters when the packet
generation probability g varies from 0 to its maximum value which makes the network nearly
saturated (PNE c = 0:99), and compare the analytical throughputs with simulations, as shown
in Fig. 8. We can see that our models are quite accurate since the analytical results (lines) and
the simulation results (symbols) of the three schemes are very close. Another observation from
Fig. 8 is that the accuracy of our model decreases when both u and g are bigger. The possible
reasons are: When both u and g are bigger, the number of client nodes that have packets to
be transmitted increases, which makes the collision probability increases. Since the time slots
with collisions are shorter than the time slots with successful transmissions, the variation of hc
is bigger when both u and g are bigger. That is, the accuracy of the approximation that hc is
constant decreases when both u and g are bigger, which leads to a bigger deviation of network
throughput.
Throughput optimization of the PNC relay system
Next we discuss the impacts of the system parameters on the throughput of the PNC
system.
- 21 -
˖ڍመڙጲ
0 1 2
x 10
−3
0
g
N
N
C
t
h
ro
u
g
h
p
u
t
0 1 2
x 10
−3
0
g
H
N
C
t
h
ro
u
g
h
p
u
t
(a) NNC scheme (b) HNC scheme
0 1 2 3 4
x 10
−3
0
g
P
N
C
t
h
ro
u
g
h
p
u
t
u=2, W
c
=1024, W
r
=2, m=3
u=10, W
c
=1024, W
r
=2, m=3
u=20, W
c
=1024, W
r
=2, m=3
u=50, W
c
=1024, W
r
=2, m=3
u=100, W
c
=1024, W
r
=2, m=3
u=100, W
c
=1024, W
r
=4, m=3
u=100, W
c
=2048, W
r
=4, m=5
(c) PNC scheme,
PNC
=1
图 8: Throughput comparison: analysis . simulation
- 22 -
˖ڍመڙጲ
16 32 64 128 256 512 1024 2048 4096
The minimum contention window size of the client nodes
PN
C
th
ro
ug
hp
ut
u=2, g=
u=2, g=
u=6, g=
u=6, g=
u=14, g=
u=14, g=
图 9: The PNC throughput . the minimum contention window size of the client nodes
2 4 8 16 32
The minimum contention window size of the relay node
PN
C
th
ro
ug
hp
ut
u=2, g=
u=2, g=
u=6, g=
u=6, g=
u=14, g=
u=14, g=
图 10: The PNC throughput . the minimum contention window size of the relay node
- 23 -
˖ڍመڙጲ
0
0
Transmission probability of the client nodes
PN
C
ne
ar
ly
sa
tu
ra
te
d
th
ro
ug
hp
ut
Maximum value
Approximate maximum value
u=20
u=50
u=100
u=10
图 11: The PNC nearly saturated throughput . the transmission probability of the client
nodes
Fig. 9 shows the network throughput versus the minimum contention window size of the
client nodes (Wc) under di�erent client node numbers and packet generation probabilities when
�PNC , Wr, and m respectively equal 1, 2, and 3. From Fig. 9, we can see that under any given
u and g, the network throughput �rst increases and then decreases asWc increases. The reason
is that a small value of Wc will not only lead to a big transmission probability of a client node
but also lead to a big collision probability. Then, when Wc is too small, the channel will be
in the collision state most of the time; and when Wc is too big, the channel will be in the idle
state most of the time. Therefore, the average time that the channel is used to successfully
transmit packets is short when Wc is too small or too big, which leads to a small value of
throughput. What's more, from Fig. 9, we can see that the throughput-optimal value of Wc
is mainly determined by the number of client nodes in the system but almost independent of
the packet generation probability. Thus, it is better to adjust Wc according to the number of
client nodes.
Fig. 10 shows the network throughput versus the minimum contention window size of the
relay node (Wr) under di�erent client node numbers and packet generation probabilities when
�PNC , Wc, and m respectively equal 1, 1024, and 3. From Fig. 10, we can see that the network
throughput is almost independent of Wr. The reasons are as follows. According to the analysis
in section , to guarantee that the relay system is stable, PNE r should be smaller than one.
That is, the packet arriving probability of the relay node's sending bu�er should be smaller
than its packet departure probability. Thus, as long as Wr is small enough to make the system
work in the steady-state, the total number of packets successfully transmitted by the relay node
- 24 -
˖ڍመڙጲ
0 50 100 150 200
1
2
Number of client nodes
T
h
ro
u
g
h
p
u
t
g
a
in
(
P
N
C
v
.s
.
H
N
C
)
α
PNC
=
α
PNC
=
α
PNC
=
α
PNC
=1
0 50 100 150 200
1
2
Number of client nodes
T
h
ro
u
g
h
p
u
t
g
a
in
(
P
N
C
v
.s
.
N
N
C
)
α
PNC
=0
α
PNC
=
α
PNC
=
α
PNC
=1
(a) Throughput gain of PNC scheme versus HNC scheme (b) Throughput gain of PNC scheme versus NNC scheme
图 12: The throughput gain of PNC scheme
indeed equals the number of packets successfully transmitted by the client nodes. That is, Wr
has little e�ect on the network throughput and can be set as small as possible to make the
system stable.
Fig. 11 shows the PNC nearly saturated throughput versus the transmission probability
of a client node kc when �PNC equals 1. We can see that for any client node number, the
approximation result of the optimal kc in Theorem 1 is quite close to the optimal value obtained
from numerical solution. What's more, from Fig. 11, we also �nd that the maximum nearly
saturated throughput is almost independent of the number of client nodes in the system, which
is similar to the case in the traditional non-relay network [13]. In addition, because of
the overhead of protocol, the maximum nearly saturated throughput is much smaller
than the cut-set capacity bound in this network scenario, which equals one (the normalized
link capacity) [27].
Throughput comparison of di�erent schemes
To compare the network throughput of di�erent schemes, we consider the nearly saturated
case that PNE c equals . And in the comparison, Wc, Wr, and m are respectively set to
2048, 2, and 3. The results are shown in Fig. 12. We can see that compared with the HNC
and the NNC schemes, the throughput gain of PNC scheme becomes more signi�cant as �PNC
increases. For example, for the relay system with one hundred client nodes, the throughput
gains of PNC scheme versus HNC and NNC schemes respectively reach about 118% and 150%
when �PNC equals , and about 157% and 200% when �PNC equals 1. The reason is that
�PNC directly determines the probability that an NC data packet contains the information of
- 25 -
˖ڍመڙጲ
two data packets. In the extreme case that �PNC equals zero, all the NC data packets in PNC
scheme only contain the information of one data packet and the PNC scheme reduces to the
NNC scheme. Another observation from Fig. 12 is that the throughput gain of PNC scheme
versus HNC scheme decreases when the number of client nodes in the system increases, while
the throughput gain of PNC scheme versus NNC scheme keeps unchanged when the number
of client nodes in the system varies. The reasons are as follows. As shown in section , the
time used by the relay node to successfully transmit a data packet in HNC scheme is longer
than the one in PNC scheme. Then, when the number of client nodes in the system is small,
the collision rarely occurs, which makes the impact of longer transmission time in HNC scheme
more severe. And since the successful transmission time is the same in the NNC and PNC
schemes when any node occupies the channel, the throughput gain of PNC scheme versus NNC
scheme will be independent of the number of client nodes.
5 Conclusions
In this paper, we studied the throughput performance of PNC scheme coordinated with
IEEE DCF. In particular, we derived the analytical unsaturated network throughput
results of the relay network with PNC scheme and the traditional HNC, NNC schemes. We
found that the throughput bene�t of PNC is more signi�cant for bidirectional isochronous
tra�c with rate requirements. Furthermore, we derived an approximate closed-form solution
of the optimal transmission probability of client nodes that maximizes the system throughput
in PNC scheme. In addition, we discussed the relationship between the PNC throughput and
the system parameters and showed some interesting results: �rst, to achieve a better network
throughput, the minimum contention window size of the client nodes should be self-adaptive
according to the number of client nodes; second, the minimum contention window size of the
relay node has little e�ect on the system throughput and thus can be set as small as possible
to make the system stable.
Proof of Lemma 1.
Proof. The derivative of Y with respect to kc, Y
0(kc), equals:
Y 0(kc) = u(1� kc)u�1 � fTc PNC[(�u
2+u)k2c�(u+1)kc+1] �(Tc PNC��)(1�kc)u+1g
[Tc PNC(1�kc+u�kc)�(Tc PNC��)(1�kc+u�kc)(1�kc)u]2 :
(30)
Note that: 8>>>><>>>>:
0 � kc < 1;
u � 2;
Tc PNC > 0;
� > 0:
)
8>>>>>>><>>>>>>>:
0 < (1� kc)u � 1;
0 < (1� kc)u�1 � 1;
1� kc + u � kc > 1;
Tc PNC � (Tc PNC � �)
�(1� kc)u > 0:
(31)
- 26 -
˖ڍመڙጲ
Thus, u(1�kc)
u�1
[Tc PNC(1�kc+u�kc)�(Tc PNC��)(1�kc+u�kc)(1�kc)u]2 > 0.
What's more, let U denote Tc PNC �[(�u2 + u)k2c � (u+ 1)kc + 1]�(Tc PNC��)(1�kc)u+1.
Then, the derivative of U with respect to kc, U
0(kc), equals:
U 0(kc) = �2Tc PNC(u2 � u)kc � (u+ 1) [Tc PNC � (Tc PNC � �)(1� kc)u] : (32)
According to equation (31), U 0(kc) is negative. Since U jkc=0 = � > 0 and U jkc=1 = �u2Tc PNC <
0, U decreases from a positive value to a negative value. Let U jkc=kc0 = 0, then,(
U > 0; 0 � kc < kc0;
U < 0; kc0 < kc < 1:
)
8>><>>:
Y 0(kc) > 0; 0 � kc < kc0;
Y 0(kc) = 0; kc = kc0;
Y 0(kc) < 0; kc0 < kc < 1:
(33)
Therefore, as kc increases from 0 to 1, Y �rst increases to a maximum value and then decreases.
参考文献（References）
[1] Zhang S, Liew S C, Lam P P. Hot Topic: Physical-layer Network Coding[J]. Proceedings
of ACM Mobicom, 2006: 358-365.
[2] Popovski P, Yomo H. The Anti-packets Can Increase the Achievable Throughput of a
Wireless Multi-hop Network[J]. Proceedings of IEEE ICC, 2006: 3885-3890.
[3] Ahlswede R, Li S, Yeung R. Network information
ow[J]. IEEE Trans. Information Theory,
2000, 46(4): 1204-1216.
[4] Katti S, Gollakota S S, Katabi D. Embracing Wireless Interference: Analog network Cod-
ing[J]. Proceedings of ACM SIGCOMM, 2007: 397-408.
[5] Koike-Akino T, Popovski P, Tarokh V. Optimized Constellations for Two-way Wireless
Relaying with Physical Network Coding[J]. IEEE Journal on Selected Areas in Communi-
cations, 2009, 27(5): 773-787.
[6] Zhang S, Liew S C. Channel coding and decoding in a relay system operated with physical-
layer network coding[J]. IEEE Journal on Selected Areas in Communications, 2009, 27(5):
788-796.
[7] Yomo H, Maeda Y. Distributed MAC protocol for physical layer network coding[J]. Pro-
ceedings of International Symposium on Wireless Personal Multimedia Communications,
2011: 1-5.
[8] Argyriou A. MAC protocol for wireless cooperative physical-layer network coding[J]. Pro-
ceedings of IEEE Wireless Communications and Networking Conference, 2012: 1596-1601.
- 27 -
˖ڍመڙጲ
[9] Cocco G, Ibars C, Gunduz D, Herrero D R O. Collision Resolution in Slotted ALOHA with
Multi-User Physical-Layer Network Coding[J]. Proceedings of IEEE Vehicular Technology
Conference, 2011: 1-4.
[10] Argyriou A, Pandharipande A. Cooperative protocol for analog network coding in dis-
tributed wireless networks[J]. IEEE Trans. on Wireless Communications, 2010, 9(10):
3112-3119.
[11] Farhadi F, Ashtiani F. Throughput Enhancement of a Random Access WLAN by Combi-
nation of Digital and Analog Network Coding[J]. Proceedings of IEEE ICC, 2011: 1-5.
[12] Argyriou A. Coordinating Interfering Transmissions in Cooperative Wireless LANs[J].
IEEE Trans. on Wireless Communications, 2011, 10(11): 3804-3812.
[13] Bianchi G. Performance analysis of the IEEE distributed coordination function[J].
IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.
[14] Daneshgaran F, Laddomada M, Mesiti F, Mondin M. Unsaturated Throughput Analysis
of IEEE in Presence of Non Ideal Transmission Channel and Capture E�ects[J].
IEEE Transactions on Wireless Communications, 2008, 7(4): 1276-1286.
[15] Ziouva E, Antonakopoulos T. The IEEE distributed coordination function in small-
scale ad-hoc wireless LANs[J]. International Journal of Wireless Information Networks,
2003, 10(1): 1-15.
[16] Wu H, Peng Y, Long K, Cheng S, Ma J. Performance of reliable transports protocol over
IEEE wireless LAN: analysis and enhancement[J]. Proceedings of IEEE INFOCOM,
2002, 2: 599-607.
[17] Chatzimisios P, Boucouvalas A, Vitsas V. IEEE packet delay-a �nite retry limit
analysis[J]. Proceedings of IEEE GLOBECOM, 2003, 2: 950-954.
[18] Xiao Y. Performance analysis of priority schemes for IEEE and IEEE
wireless LANs[J]. IEEE Transactions on Wireless Communications, 2005, 4: 1506-1515.
[19] Emad, Eylem E. Single Hop IEEE DCF Analysis Revisited: Accurate Modeling of
Channel Access Delay and Throughput for Saturated and Unsaturated Tra�c Cases[J].
IEEE Transactions on Wireless Communications, 2011, 10(10): 3256-3266.
[20] Ping C N, Liew S C. Throughput Analysis of IEEE Multi-Hop Ad Hoc Networks[J].
IEEE/ACM Transactions on Networking, 2007, 15(2): 309-322.
[21] Gupta N, Kuman P R . A Performance Analysis of the Wireless Lan Medium Access
Control[J]. Communications in Information and Systems, 2003, 3(4): 279-304.
- 28 -
˖ڍመڙጲ
[22] Umehara D, Hirano T, Denno S, Morikura M, Sugiyama T. Wireless network coding in
slotted ALOHA with two-hop unbalanced tra�c[J]. IEEE Journal on Selected Areas in
Communications, 2009, 27(5): 647-661.
[23] Umehara D, Denno S, Morikura M, Sugiyama T. Performance analysis of slotted ALOHA
and network coding for single-relay multi-user wireless networks[J]. Ad Hoc Networks,
2011, 9: 164-179.
[24] Umehara D, Denno S, Morikura M, Sugiyama T. Throughput Analysis of Two-Hop Wire-
less CSMA Network Coding[J]. Proceedings of IEEE ICC, 2010: 1-6.
[25] Jiang L B, Liew S C. Hidden-node Removal and Its Application in Cellular WiFi Net-
works[J]. IEEE Transactions on Vehicular Technology, 2007, 56(5): 2641-2654.
[26] Mautz R. Indoor Positioning Technologies[D]. Zurich: ETH Zurich, 2012.
[27] Liew S C, Zhang S, Lu L. Physical-layer network coding: Tutorial, survey, and beyond[J].
Physical Communication, 2013, 6: 4-42.
- 29 -
