Optimal Stochastic Policies in a network coding capable Ad Hoc Networks

KSII Transactions on Internet and Information Systems (TIIS).
2014.
Dec,
8(12):
4389-4410

- Received : May 30, 2014
- Accepted : October 27, 2014
- Published : December 31, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

Network coding is a promising technology that increases system throughput by reducing the number of packet transmissions from the source node to the destination node in a saturated traffic scenario. Nevertheless, some packets can suffer from end-to-end delay, because of a queuing delay in an intermediate node waiting for other packets to be encoded with exclusive or (XOR). In this paper, we analyze the delay according to packet arrival rate and propose two network coding schemes,
iXOR (Intelligent XOR)
and
oXOR (Optimal XOR)
with
Markov Decision Process (MDP)
. They reduce the average delay, even under an unsaturated traffic load, through the Holding-
χ
strategy. In particular, we are interested in the unsaturated network scenario. The unsaturated network is more practical because, in a real wireless network, nodes do not always have packets waiting to be sent. Through analysis and extensive simulations, we show that
iXOR
and
oXOR
are better than the
Distributed Coordination Function (DCF) without XOR (the general forwarding scheme)
and
XOR with DCF
with respect to average delay as well as delivery ratio.
L
inear network coding and exclusive or (XOR) are two major techniques in network coding. Linear network coding transforms the packets with the linear equation in every intermediate node, and the destination node only needs to receive enough of the linear equations in the form of coded packets to successfully decode the original packets
[1]
[2]
. It allows the destination node to avoid unnecessarily receiving the same packets several times via the retransmission mechanism after transmission failure. In addition, XOR reduces the number of transmissions because the intermediate node encodes the packets from both sides into one packet and broadcasts it to all original destinations in an Alice-Bob topology or X-topology
[3]
. As a result, network coding has recently become a spotlight mechanism due to its effect on improving network throughput and proof of the theoretical maximum network capacity. It was first shown under the wired multicasting network
[4]
, and later, the wireless network environment in several papers
[5]
[6]
[7]
.
IEEE 802.11 recommended the Distributed Coordination Function (DCF) as the mandatory function for the Media Access Control (MAC) layer of the wireless Local Area Network (LAN)
[8]
. In wireless communication, transmission failures due to packet collisions can occur when the stations transmit at the same time, because they share the transmission medium—air. To reduce collision probability, DCF uses a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism, in which the stations count down a random back-off time once during each slot time of the idle channel, and they transmit a packet when the back-off time reaches zero. However, network performance can still decrease due to frequently occurring packet collisions in a saturated traffic scenario. Therefore, most previous network coding schemes have only focused on throughput improvement by reducing the number of transmission packets and collisions in a saturated traffic scenario. However, we are particularly interested in improvement of network coding with DCF in the unsaturated network. The unsaturated network is more practical because, in a real wireless network, nodes do not always have packets waiting to be sent.
Some researchers
[9]
have investigated throughput performance of physical-layer network coding (PNC) under DCF
[10]
. They considered a wireless network where two client groups communicate with each other across one relay node, and focused on the unsaturated network. They further derived an approximate closed-form solution for the transmission probability of client nodes that maximizes PNC network throughput. Even though they
[9]
considered the unsaturated scenario, they derived analytical network throughput for only the PNC under DCF. They did not provide an optimal policy in the relay node to improve performance in the unsaturated wireless network.
Other researchers
[11]
first reduced the average delay, even under an unsaturated traffic load, with DCF through the Holding-
χ
strategy concept to maximize the number of network coding chances. However, they only provided a heuristic algorithm for the proper Holding-
χ
value based on simulation in a specific simple scenario without the optimal solution.
Then
[12]
proposed a network coding algorithm for a video conference system to minimize the maximal transmission delay during multicast while retaining high throughput at the same time. Zeng et al.
[13]
proposed enhanced network coding (ENC) considering a delay-energy lower bound on two-way–relay wireless network coding. Dong et al.
[14]
provided a dynamic network coding model called Dynamic Network Coding with Packet-transmission Delay Guarantee (DNPDG), which effectively controls packet transmission delay in network coding by dynamically determining the coding operation and adjusting the size of data generation. However, they focused on analyzing the average delay in a specific wireless networks without DCF and did not consider the unsaturated practical scenarios as well as the trade-off between throughput and delay.
Our contribution is average delay reduction as well as delivery ratio improvement using network coding based on IEEE 802.11 distributed coordination function, even in the unsaturated scenario. Therefore, we first analyzed the delay according to packet arrival rate and proposed
Intelligent XOR (iXOR)
using the Holding-
χ
strategy to get more XOR chances. With the Markov Decision Process (MDP) of optimization theory, we also propose
oXOR (Optimal XOR)
for the optimal Holding-
χ
value. And we evaluated
oXOR
,
iXOR
,
XOR
and
DCF without XOR (the general forwarding scheme)
. The rest of the paper is organized as follows. In sections 2 and 3, we discuss related work and delay analysis under dynamic traffic scenarios in
DCF without XOR
and
XOR with DCF
. Section 4 presents the heuristic proposed scheme,
iXOR
. We analyze
oXOR
with the Markov Decision Process theory in Section 5. Section 6 evaluates the performance. Finally, Section 7 concludes the paper.
χ
strategy concept to reduce average delay even under an unsaturated traffic load with DFC by maximizing the number of network coding chances. However, they only provided the proper Holding-
χ
value heuristically, based on an extensive simulation in a specific scenario without an optimal solution.
DCF without XOR (the general forwarding scheme)
and
DCF with XOR
. First of all, i)
DCF without XOR
shows the end-to-end delays taken by each packet generated from source nodes 1 and 3 to destination nodes 3 and 1, D
_{1-wo-XOR}
and D
_{3-wo-XOR}
, respectively. D
_{1-wo-XOR}
is composed of the time (C
_{1}
) for source node 1 to compete for and grab the channel, the time (T
_{1→2}
) for the packet to be transferred from source node 1 to intermediate node 2, the time (C
_{2}
) for intermediate node 2 to compete for and grab the channel, and the time (T
_{2→3}
) for the packet to be transferred from intermediate node 2 to destination node 3. Similarly, D
_{3-wo-XOR}
can be derived like D
_{1-wo-XOR}
. And, A
_{1,3-wo-XOR}
means the average delay of the packets from nodes 1 and 3.
E2E delay comparison, i) DCF without XOR and ii) DCF with XOR
In contrast, ii)
DCF with XOR
shows the end-to-end delays of the packets from source nodes 1 and 3 to destination nodes 3 and 1 via broadcast transmission of the coded packet in intermediate node 2: D
_{1-w-XOR}
, D
_{3-w-XOR}
, respectively. D
_{1-w-XOR}
is composed of the time (C
_{1}
) when source node 1 competes for and grabs the channel, the time (T
_{1→2}
) when the packet is transferred from source node 1 to intermediate node 2, the time (
χ
) when the packet from the source node 1 is queued in intermediate node 2 to wait for a packet generated by another source (node 3) to be encoded, the time (C
_{3}
) when source node 3 competes for and grabs the channel, the time (T
_{3→2}
) when the packet is transferred from source node 3 to intermediate node 2, the time (C
_{2}
) when intermediate node 2 competes for and grabs the channel, and the time (T
_{2→1,3}
) when intermediate node 2 broadcasts and successfully delivers the coded packet to destination nodes 3 and 1. D
_{3-w-XOR}
can be also interpreted like D
_{1-w-XOR}
. However, the packet from node 3 does not wait at intermediate node 2 because the packet from node 1, being coded, is already in the queue of intermediate node 2. And in fact, D
_{3-w-XOR}
is not needed because it could be part of D
_{1-w-XOR}
. As a result, the average delay A
_{1,3-w-XOR}
is generally shorter than A
_{1,3-wo-XOR}
in the saturated scenario, because XOR reduces the number of transmissions.
However, A
_{1,3_w_XOR}
can be longer than A
_{1,3_wo_XOR}
due to the holding time,
χ
, according to the packet arrival rate, specially in the unsaturated scenario. Based on this motivation about the relationship between the delay and the packet arrival rate in a network coding–capable wireless network, we propose two strategies,
iXOR
using the heuristic Holding-
χ
, and
oXOR
with the optimal holding
χ
value, to get more XOR chances, even in the unsaturated network scenario based on IEEE 802.11 distributed coordination function.
iXOR
in an ad hoc network, we define several terms, as follows.
Fig. 2
. shows the meaning of
W_{A_i}
and
W_{A_ii}
. Specifically, i)
Fig. 2
(a) shows when Bob has a packet to transmit at time t, while Alice’s packet is transmitted to the relay node. As a result, the waiting time for Alice’s packet in the queue of the intermediate node to be encoded with Bob’s packet,
W_{A_i}
, is Bob’s packet’s transmission time, T. Otherwise, i)
Fig. 2
(b) shows when Bob has a packet to transmit at time t, after Alice’s packet is transmitted to the relay node. As a result, the waiting time for Alice’s packet (in the queue of the intermediate node) to be encoded with Bob’s packet,
W_{A_ii}
, is the time to Bob’s packet generation and transmission from Bob to the relay node, t+T-T. Time t in
Fig. 2
(b) is when Bob has a packet to transmit; the first capital T is the transmission time of Bob’s packet from the Bob node to the intermediate node, and the second capital T is the transmission time of Alice’s packet from the Alice node to the intermediate node. The reason for the negative effect of transmission time T for Alice’s packet is that Bob has to wait until time t to at least have a packet. Therefore, the meaning of the value “t+T-T” is the needed time for Alice’s packet to wait in the middle node to code with Bob’s packet.
Two cases of waiting time of Alice’s packet at the intermediate relay node, W_{A_i} and W_{A_ii} .
As a result, if we assume that packet arrival rate λ is an exponential distribution, we can calculate the expectation of the waiting time for Alice’s packet
E[W_{A}]
by considering
E[W_{A_i}]
and
E[W_{A_ii}]
in Eq. (1) and Eq. (2).
Each probability of case i) and case ii),
q_{A_i}
and
q_{A_ii}
, is a cumulative distribution probability according to each duration of the probability density function of the exponential distribution, λe
^{-λt}
in Eq. (3).
T
is the channel occupation time (DIFS+backoff+Tx+SIFS+AcK+round-trip propagation delay), and
t
is the generation time for Bob’s packet.
Along the same lines, we can also define the waiting time for Bob’s packet in the queue of the Bob node as follows.
Fig. 3
. shows the meanings for
W_{B_i}
and
W_{B_ii}
.
Two cases of waiting time of Bob’s packet in the Bob node, W_{B_i} and W_{B_ii} .
W_{B}
- waiting time for Bob’s packet in the queue of the Bob node for Alice’s packet to be delivered to the intermediate node
W_{B_i}
,
W_{B_ii}
– two cases of waiting time for Bob’s packet in the queue of the Bob node according to Bob’s packet arrival
As a result, we can also calculate the expectation of Bob’s packet’s waiting time
E[W_{B}]
considering
E[W_{B-i}]
and
E[W_{B-ii}]
in Eq. (4).
Finally, we can get the total waiting time of
DCF with XOR
in Eq.(5) since in this paper, the overall waiting time is the summation of each holding packet for the network coding in any queues due to the busy medium based on IEEE 802.11 distributed coordination function.
Fig. 4
. shows the comparisons of
E[W_{A}]
and
E[W_{B}]
for each packet according to the packet arrival rate, λ, and packet size T. And
Fig. 5
. shows
E[W_{XOR}]
of the XOR exchange system. It shows that the network coding introduces a longer delay when packet arrival rate λ is very low. Therefore, we need to find the proper Holding-
χ
at the intermediate node to reduce the average delay.
E[W_{A}] and E[W_{B}] comparisons of each packet
E[W_{XOR}] for the XOR exchange system
To compare
DCF without XOR
and
DCF with XOR
, we in detail explain the case studies of
DCF without XOR
. These are classified into
DCF without RTS/CTS
and
DCF with RTS/CTS
as shown in
Figs. 6
and
7
, respectively.
The case studies of DCF without XOR (w/o RTS and CTS)
The case studies of DCF (w/ RTS and CTS)
1) DCF without RTS/CTS
This is classified into three cases according to Bob’s packet arrival rate. In the saturation and middle-saturation scenarios with 0≤t≤T and T ≤ t ≤ 2T, respectively, we again have two cases based on the channel taking chances between the Alice packet and Bob packet. In case of the unsaturated scenario with 2T < t, there is a single case where each packet from Alice and Bob is transmitted to each destination in the order named.
And we can calculate the expected total waiting time based on the
DCF without RTS/CTS
of
Fig. 6
in Eq. (6). The probability σ is so low that the second case of the middle-saturation scenario can be ignored. Therefore, only the two cases of the saturation and the first case of middle-saturation scenarios are considered to get the expectation delay of
E[W_{DCF}]
.
2) DCF with RTS/CTS
With the
DCF with RTS/CTS
exchange protocol, we only think about i-ii), ii-ii) and iii) cases of
Fig. 6
, as shown in
Fig. 7
. The relay node can calculate the transmission duration of the Alice packet after receiving the RTS control packet from the Alice node. And the relay node can send CTS with information about the next transmission turn and time, as well as acknowledge the RTS. For example, in ii) and ii) cases of
Fig. 7
, Bob (receiving the CTS from the relay node) can transmit the corresponding packet to the relay node at the given time after CTS. However, if the corresponding packet from Bob is lately generated under the severe unsaturated scenario, as shown in case iii) of
Fig. 7
, the relay node should just forward the Alice packet to the Bob node to minimize the average end-to-end delay. Eq.(7) is the expected total waiting time based on the
DCF with RTS and CTS
of
Fig. 7
.
At last, we can get the cross point of the light blue, which gives the motivation for the proposed scheme,
iXOR
, as shown in
Fig. 8
.
iXOR
opportunistically exchanges the function from
XOR
to
DCF
, or conversely, according to packet arrival rate λ. Specifically, in
iXOR
, the relay node holds Alice’s packet until it gets Bob’s packet, as long as the arrival rate of the packet is larger than the cross point of the light blue. On the other hand, the relay node does not hold Alice’s packet but forwards it directly to the destination based on
DCF
when the arrival rate of the packet is smaller than the cross point of the light blue to reduce the average delay.
Delay comparison between DCF with XOR (E[W_{XOR}]) and DCF without XOR (E[W_{DCF}])
Therefore, motivated by the previous part and
Fig. 8
, we focus on the holding time,
χ
, to reduce the average delay with
iXOR
in the various scenarios, according to packet arrival rate λ.
Fig. 9
shows
iXOR
using the Holding-
χ
strategy in ad hoc networks. The proposed scheme considers three scenarios according to packet arrival rate λ. In the first scenario with the low enough arrival rate λ, after a packet from node 1 has arrived at intermediate node 2, intermediate node 2 cannot XOR-encode with another packet from node 3. Even though intermediate node 2 waits for the Holding-
χ
for another packet from node 3, it is not delivered to intermediate node 2 within the Holding-
χ
. Specifically, time
t
for packet arrival from node 3 is longer than the Holding-
χ (t>χ and χ≠0)
. In the second scenario, with the medium arrival rate, intermediate node 2 can XOR-encode the two packets from nodes 1 and 3 because, after a packet from node 1 arrives at intermediate node 2, the packet from node 3 arrives at intermediate node 2 within Holding-
χ (t<χ and χ≠0)
. And in the third scenario with the high enough arrival rate, intermediate node 2 can instantly XOR-encode the packets from nodes 1 and 3 regardless of Holding-
χ
because, after a packet from node 1 arrives at intermediate node 2, the packet from node 3 immediately arrives at intermediate node 2 before Holding-
χ
(
χ=0
).
iXOR using Holding-χ Strategy
In the proposed scheme the intermediate node opportunistically uses the Holding-
χ
strategy according to the packet arrival rate to get more XOR chances. Heuristically, we can get the proper holding time,
χ
=0.03 ms, through the extensive simulations.
iXOR
, and an optimal solution, we develop optimal policies that yield a transmit/wait decision at each time instant in the relay node to optimize the timely throughput over DCF. We define our objective as the maximum long-run average throughput and minimum delay on a per-unit-time basis. Thus, we proposed
oXOR
based on the optimal policies. In this scheme, the relay node can transmit and incur a transmission cost for forwarding a single packet. It can also wait in the hope that a codable packet will arrive, which allows the transmission cost for broadcasting the XOR-ed packet as well as the latency cost for holding a packet. For that, in
Fig. 10
the relay node maintains two queues
q_{A}
and
q_{B}
, such that
q_{A}
and
q_{B}
store packets that are needed to be delivered to the nodes
Alice
and,
Bob
respectively. If both the queues are not empty, then, it can forward the two packets from these queues by performing a bitwise XOR operation. However, if one of the queues has packets to transmit and the second queue is empty, the relay node should wait the optimal time for a coding opportunity.
Wireless network coding in a downlink scenario
To compare
oXOR
with
iXOR
, we first consider Alice and Bob topology with a single relay node, and assume that arrivals into both the queues follow independent Bernoulli processes
[26]
. We find that the optimal policy is a stationary queue-length threshold policy with one threshold for each queue at the relay. Its action is simple: if a coding opportunity exists, code and transmit; else if the threshold for that queue is reached, it transmits a packet. We show how to find the optimal thresholds, and find the exact expressions for the expected throughput and latency based on the stationary distribution of the Markov Chain when controlled by this policy.
n
=
A
,
B
and
t
= 0, 1, 2, . . ., let
be the number of packets in a queue of
n
at the end of the time slot
t
, just before an opportunity to transmit as showin in
Fig.10
.
Let
A_{t}
be the action chosen at the end of the
t
th time slot with
A_{t}
= 0 implying that the action is to do nothing but wait, and
A_{t}
= 1 implying that the action is to transmit. We define costs for the transmission and latency. Let
C_{tx_XOR}
be the transmission cost for broadcastingthe XOR-ed packet. Let
C_{tx_fwd}
be the transmission cost for forwarding a single packet and let
C_{w}
be the latency cost for holding a packet for a length of time which is equal to one slot. They are calculated by the expected transmission count (ETX) and the expected transmission time (ETT)
[31]
[32]
metrics.
C_{tx_XOR}
is the ETT for the relay node to broadcast a XOR-ed packet with a low rate to the two destinationnodes while
C_{tx_fwd}
is the ETT for the relay node to unicast a single packet to one destination node. Without loss of generality, we assume that if a packet was transmitted in the same slot through which it arrived, its latency cost is zero. On the other hand, if a packet was transmitted through a different slot from which it arrived,
C_{w}
is ETT/ETX. Our objective is to derive an optimal policy that maximizes the long-run average throughput while minimizing the average delay per slot. For this, we define the MDP {(
Q_{t}
,
A_{t}
),
t
≥0} where
Q_{t}
= (
Q_{t}^{A}
,
Q_{t}^{B}
) is the state of the system and
A_{t}
is the control action chosen at a time
t
. The state space (i.e. all possible values of
Q_{t}
) is the set{(i, j - integers): i≥0, 0≤j≤1 or j≥0, 0≤i≤1} as shown in
Fig. 11
. Let
C(Q_{t}, A_{t})
be the cost incurred at time
t
in Eq. (8) if the action
A_{t}
is taken when the system is in state
Q_{t}
.
Markov Decision Process Model for oXOR
where, [x]
^{+}
= max(x,0). For the MDP {(
Q_{t}
,
A_{t}
),
t
≥0}, the transition probability (P
_{1}
, P
_{2}
, P
_{3}
) from a state
Q_{t}
to
Q_{t+1}
that is associated with the action
A_{t}
∈{0,1}. This can be derived from the different Bernoulli arrival rates (
p_{A}
,
p_{B}
) and the optimal policy is of the threshold type as in shown
Fig. 11
.
There exist the optimal thresholds
i
^{*}
_{A}
and
j
^{*}
_{B}
of each queue size for the packets to wait. The optimal deterministic action in states (i, 0) is to wait if i≤
i
^{*}
_{A}
and to transmit without coding if i>
i
^{*}
_{A}
. While in state (0, j), it is to wait if j≤
j
^{*}
_{B}
, and to transmit without coding if j >
j
^{*}
_{B}
. Therefore, the optimal thresholds
i
^{*}
_{A}
and
j
^{*}
_{B}
for the long-run average throughput per slot are (
i
^{*}
_{A}
,
j
^{*}
_{B}
) =
Eq. (9) shows the way how to derive an optimal policy that maximizes the long-run average throughput while minimizing the average delay per slot. To maximize the average throughput, the denominator with the average delay should be reduced.
As shown in
Fig. 12
, the expected number of XOR-ed transmissions per slot is the states with the red circles. It can be derived by,
A steady-sate transition diagram for oXOR with the optimal thresholds
The expected number of forwarding transmissions per slot is the states with the yellow circles. It can be derived by,
The average number of packets in the system at the beginning of each slot is the states with the blue circles. It can be derived by,
To complement the optimal solution with the steady-state probabilities of the Markov chain from the MDP problem, we define two variables. Let
X_{t}^{A}
be the number of packets from node
A
at the beginning of the tth slot before any arrival or transmission. It is crucial to note that, this observation time is different from the time when the MDP is observed. Then, the bivariate stochastic process {(
X_{t}^{A}
,
X_{t}^{B}
,
t
≥0} is a discrete-time Markov chain only consisting of the states with the white and blue circles as shown in
Fig. 12
. The states are (0, 0), (1, 0),(2, 0), . . ., (
i_{A}
, 0), (0, 1), (0, 2), . . ., (0,
i_{B}
). Define
α
as a parameter such that,
α
= (1-
p_{B}
)
p_{A}
/(1-
p_{A}
)
p_{B}
. And let
π_{i,j}
be the steady-state probabilities of the Markov chain. To prove the balance equations for 0 <
i
≤
i_{A}
and 0 <
j
≤
j_{B}
, we define two equations as follows:
Since,
we have,
χ
, we evaluate the average delay and the delivery ratio of
DCF without XOR, DCF with XOR, iXOR
and
oXOR
with the event-driven simulator NS-3 under the various scenarios. The parameters used in simulations are summarized in
Table 1
.
Simulation Properties
Fig. 13
,
14
and
15
show the average delay of
DCF
,
XOR
,
iXOR_{1} (w/o RTS/CTS)
,
iXOR_{2} (w RTS/CTS)
and
oXOR
according to the holding
χ
, “chi”, in unicast, multicast and broadcast scenarios, respectively. Because
DCF
and
XOR
do not involve “chi” parameter, the average delays of them are unchanged according to the “chi”. And when the “chi” is zero,
iXOR_{1}
,
iXOR_{2}
and
oXOR
work exactly the same as
XOR
. While the “chi” is increased until 0.3msec, the average delay of
iXOR
and
oXOR
schemes outperforms
XOR
. However, if the “chi” value is longer than 0.3msec, the holding-
χ
can be rather overhead in the unsaturated scenario. The reason why
oXOR
is better than
iXOR_{1}
and
iXOR_{2}
, it can find the optimal holding time based on the MDP process. However, the gain between
oXOR
and
iXOR
schemes is not quite amazing since the holding-
χ
(i.e.,
χ
=0.3msec) based on the extensive simulations of the previous our work
[11]
can reach the optimal value. Therefore, the contribution of this paper is the average delay reduction as well as delivery ratio improvement using the Markov Decision Process (MDP) of optimization theory firstly in the unsaturated scenario. And through the evaluation results, our previous heuristic algorithm (i.e.,
iXOR
[11]
) is proved meaningful since it can reach the optimal solution (i.e.,
oXOR
) of this paper with the small gap.
Average delay with holding-χ in unicast scenario
Average delay with holding-χ in multicast scenario
Average delay with holding-χ in broadcast scenario
Fig. 16
shows the average delay according to the packet arrival rate λ, “lambda” in unicast scenario. It shows that
iXOR
and
oXOR
schemes outperform
XOR
regardless of the “lambda”.
Fig. 17
show the busy ratio of
DCF
,
XOR
,
iXOR_{1} (w/o RTS/CTS)
,
iXOR_{2} (w RTS/CTS)
and
oXOR
according to the holding
χ
, “chi”, in unicast. Busy ratio means the wireless channel occupation ratio.
iXOR
and
oXOR
schemes outperform
DCF
and
XOR
because they can reduce the number of transmissions through more coding chances. Due to the similar reasons, the delivery ratios of
iXOR
and
oXOR
schemes are also better than
DCF
and
XOR
as shown
Fig. 18
.
Fig. 19
shows the delivery ratio according to the number of nodes to consider multiuser effects. Apparently, there is a trade-off between throughput and collisions in multiuser case. More users will lead to higher throughput gain whereas it will bring much more collisions. However, generally multiuser increase network coding chances in
iXOR
and
oXOR
schemes. Specifically,
iXOR_{2}
is very similar with
oXOR
since it can solve the collision problems with RTS and CTS than
iXOR_{1}
.
Average delay according to lambda (=packet arrival rateλ)
Busy ratio according to chi (=holding-χ )
Delivery ratio according to chi (=holding-χ )
Delivery ratio according to the number of nodes
iXOR
and
oXOR
using holding-
χ
strategy in ad-hoc network. Through the simulation and analysis with MDP, we can get the optimal holding-
χ
value. And we found
iXOR
and
oXOR
outperform
DCF
and
XOR
schemes if the intermediate node opportunistically XOR-encodes the packets with the optimal holding-
χ
.
Hayoung Oh received the B.S. degree in Computer Science from Duksung Womans University and the M.S. degree in the School of Computer Science and Engineering from Ewha Womans University in 2002 and 2006 respectively. And she received the Ph.D. degree in Computer Science from Seoul National University in 2013. From 2002 to 2004, she joined Shinhan Financial Group as a developer in applied research. In 2010, she was with U.C. Berkeley as a researcher. Since 2013, she has been with Soongsil University as a professor in the School of Electronic Engineering. Her research interests include social and computer networks, and security.

1. Introduction

2. Related Work

- 2.1 DCF (Distributed Coordination Function)

IEEE 802.11 recommends DCF as the standard mechanism to reduce the collision probability of stations that share the transmission medium in wireless networks
[8]
. In wireless networks, packet collision is unavoidable because the stations are unaware of the time when their competitors transmit, and several stations transmit simultaneously within the propagation delay. Thus, IEEE 802.11 recommends the CSMA/CA mechanism, in which the stations count down a random back-off time once during each slot time of the idle channel, and they transmit when the back-off time reaches 0 to reduce the packet collision probability.
DCF describes two techniques for packet transmission
[15]
. The default scheme is a two-way handshake technique called the basic access mechanism. This mechanism is characterized by the immediate transmission of a positive acknowledgement (AcK) by the destination station, upon successful reception of a packet transmitted by the sender station. Explicit transmission of an AcK is required since, in the wireless medium, a transmitter can determine if a packet was successfully received by listening for AcK from the destination station.
In addition to basic access, an optional four-way handshake technique, known as the request-to-send/clear-to-send (RTS/CTS) mechanism was standardized. Before transmitting a packet, a station operating in RTS/CTS mode “reserves” the channel by sending a special Request-To-Send short frame. The destination station acknowledges receipt of an RTS frame by sending back a Clear-To-Send frame, after which normal packet transmission and AcK response occurs. Since collision may occur only on the RTS frame, and collision is detected by lack of a CTS response, the RTS/CTS mechanism allows an increase in system performance by reducing the duration of a collision when long messages are transmitted. As an important side effect, the RTS/CTS scheme designed in the 802.11 protocol is suited to combat the problem of so-called Hidden Terminals
[16]
, which occurs when pairs of mobile stations are unable to hear each other. This problem has been specifically considered elsewhere
[17]
[18]
, where the phenomenon of packet capture was also studied.
- 2.2 Network Coding

Network coding makes the theoretical maximum network capacity practically achievable by reducing the number of packet transmissions. There are two specific mechanisms in network coding, XOR
[3]
and linear (random) network coding
[1]
[2]
. XOR reduces the number of transmissions in such as way that the intermediate node only broadcasts the packet once after it has been encoded from packets sent by several transmitters, rather than simply forwarding all those packets one by one. Several authors implemented an XOR-bit-level network coding mechanism in a wireless network test-bed, showing that it improves network throughput by 38%
[3]
[8]
. More recently, it was shown that analog network coding
[5]
utilizing signal interference, rather than excluding it, reduces transmission time even more than the traditional bit-level network coding. All these network coding mechanisms could be widely utilized for reliability gain
[19]
[27]
, multi-hop network gain
[20]
[25]
, relay network gain
[21]
[24]
[34]
, opportunistic routing
[7]
, peer-to-peer networks
[23]
, efficient content distribution
[28]
[29]
[33]
, and energy efficiency
[14]
[22]
, etc.
In contrast, linear coding
[1]
[2]
is where the intermediate nodes forward every packet linear-transformed by a certain linear equation, and destination nodes decode the original packets as long as they receive enough of the linear equations in adequate number. Linear transformation is a multiplication of a vector’s so-called coefficient to the bit-pattern of the packet that passes through a station, and is called linear coding when the coefficient becomes 1, whereas it is called random linear coding when the coefficient is less than 1 and larger than 0. (Random) linear coding is generally applied with packet error recovery
[7]
, a multicast scenario, and efficient delivery of urgent messages in Vehicular Ad Hoc Networks and Delay-Tolerant Networking (DTN)
[30]
.
Zeng et al.
[13]
proposed enhanced network coding with a delay-energy lower bound on a two-way relay wireless network. In ENC, the relay transmits both coded and uncoded packets for reducing delay. Generally, in exchange between two nodes, more energy is consumed to transmit uncoded packets. ENC is a practical algorithm to achieve minimal average delay and a zero packet-loss rate under a given energy constraint. Dong et al.
[14]
provided a dynamic network coding model called Dynamic Network Coding with Packet-transmission Delay Guarantee (DNPDG). They effectively controls packet transmission delay in network coding by dynamically determining the coding operation and adjusting the size of data generation. And in the coding operation, the model schedules and forwards the packets based on measurement of the current accumulative transmission delay and the service priority of the packet. Lastly, the acknowledgement information feedback with per-hop transmission technique promotes packet transmission of various data generations in the relay nodes. However, these schemes focused on analyzing the fundamental trade-off between average delay and energy/data size and did not consider the unsaturated practical scenario with DCF as well as the trade-off between throughput and delay.
Hui Zhang, et al., proposed the network coding algorithm for a video conference system by minimizing the maximal transmission delay while retaining high throughput at the same time. They first formulate a minimizing delay in multicast scenario with a network coding strategy as an optimization problem
[12]
. It is based on an algebraic framework represented by a directed graph, G (V, E), with vertex set V representing nodes, and directed edge set E representing links. However, since this paper assumes the multicast scenario is based on the wired Internet, end–to-end delay is mainly caused by the propagation delay along the Internet route and the buffering delay at the intermediate nodes. They did not consider timely throughput and unsaturated scenarios considering DCF.
Some researchers have investigated the throughput performance of physical-layer network coding (PNC) under the unsaturated network with DCF
[9]
[10]
. They derived an approximate closed-form solution of the transmission probability of client nodes that maximizes throughput. Even though they considered the unsaturation scenario, they only focused on the analytical network throughput results in a specific wireless network scenario where two client groups communicate with each other across one relay node. And they did not provide an optimal policy in the relay node to improve XOR performance in unsaturated wireless networks.
Other researchers
[11]
first introduced the Holding-
3. Delay analysis under dynamic traffic in DCF without XOR and with XOR

Fig. 1
shows the delay comparison between
PPT Slide

Lager Image

4. iXOR (Intelligent XOR) using Holding-χ strategy in an ad hoc network

To design
- WA– the waiting time of Alice’s packet in the queue of the intermediate node for Bob’s packet to arrive and to be encoded
- WA_i,WA_ii– two cases for waiting time of Alice’s packet in the queue of the intermediate node according to the arrival of Bob’s packet

PPT Slide

Lager Image

- E[WA_i],E[WA_ii]– the expectation of Alice’s packet waiting time in each case

PPT Slide

Lager Image

- E[WA]– the expectation of Alice’s packet waiting time

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- E[WB-i],E[WB-ii]– the expectation of Bob’s packet’s waiting time in each case
- E[WB]– the expectation of Bob’s packet’s waiting time

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. oXOR (Optimal XOR) using Markov Decision Process

To compare the difference between the previous heuristic algorithm,
PPT Slide

Lager Image

- 5.1 Markovian Model

To develop a strategy for the relay to decide at every transmission opportunity, for its best course of action, we use a Markov Decision Process (MDP) model. For
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

6. Performance evaluation

To get the proper holding deadline,
Simulation Properties

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Conclusion

In this paper, we analyzed the average delay and timely throughput according to the packet arrival rate λ in a network coding capable wireless network with Markov Decision Process (MDP) and proposed the
Acknowledgements

This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning(NRF-2014R1A1A1003562).

BIO

Li S.-Y. R.
,
Yeung R. W.
,
Cai N.
2003
“Linear network coding,”
IEEE Trans. Inf. Theory
49
371 -
381
** DOI : 10.1109/TIT.2002.807285**

Fragouli Christina
,
Widmer Jorg
,
Le Boudec Jean-Yves
2008
“Efficient Broadcasting Using Network Coding,”
IEEE/ACM TRANSACTIONS ON NETWORKING
16
(2)
** DOI : 10.1109/TNET.2007.901080**

Katti Sachin
,
Rahul Hariharan
,
Hu Wenjun
,
Katabi Dina
“XORs in the Air: Practical Wireless Network Coding,”
ACM SIGCOMM 2006
Pisa, Italy
September 2006

Ahlswede R.
,
Cai N.
,
Li S.-Y. R.
,
Yeung R. W.
“Network Information Flow,”
IEEE Transactions on Information Theory
2000

Katti Sachin
,
Gollakota Shyamnath
,
Katabi Dina
2007
“Embracing Wireless Interference: Analog Network Coding,”
ACM SIGCOMM

Katti Sachin
,
Katabi Dina
,
Hu Wenjun
,
Rahul Hariharan
,
Medard Muriel
“Practical Network Coding for WirelessEnvironments,”
in Proc. of Allerton Conference on Communication, Control, and Computing
September 2005

Chachulski S.
,
Jennings M.
,
Katti S.
,
Katabi D.
2007
“Trading Structure for Randomness in Wireless Opportunistic Routing,”
in Proc. of ACM SIGCOMM

IEEE
“International Standard for Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific Requirements- Part 11: Wireless LAN Medium.”

Shijun Lin
,
Fujianand Xiamen
,
Liqun Fu
2013
“Unsaturated Throughput Analysis of Physical-Layer Network Coding Based on IEEE 802.11 Distributed Coordination Function,”
IEEE Transactions on Wireless Communications

Eylem E.
2011
“Single hop IEEE 802.11 DCF analysis revisited: accurate modeling of channel access delay and throughput for saturated and unsaturated traffic cases,”
IEEE Trans. Wireless Commun.
10
(10)
3256 -
3266
** DOI : 10.1109/TWC.2011.072511.101227**

Oh Hayoung
,
Lee Junjie
,
Lee Suchul
,
Kim Chong-kwon
“iXOR : Intelligent XOR using Holding-x Strategy in Ad hoc Networks,”
IEEE VTC-Spring
May 2011

Zhang Hui
,
Zhoub Jin
,
Chenb Zhen
,
Lib Jun
“Minimizing Delay for Video Conference with Network Coding,”
ACM Sigcomm
2009

Hongyi Zeng
,
Chen Wei
2014
“Delay-Energy lower bound on Two-Way Relay Wireless Network Coding,”arXiv preprint arXiv:1401.6275

Zanqiang DONG
,
SHEN Subin
,
Yangqun L. I.
2013
“Dynamic Network Coding with Delay-guarantee in Multi-hop Wireless Networks,”
Journal of Computational Information Systems 9.4
1529 -
1538

Bianchi G.
2000
“Performance Analysis of The IEEE 802.11 Distributed Coordination Function,”
IEEE J. Selected Areas in Comm.
18
(3)
535 -
547
** DOI : 10.1109/49.840210**

Cali F.
,
Conti M.
,
Gregori E.
1998
“IEEE 802.11 Wireless LAN: Capacity Analysis and Protocol Enhancement,”
in Proc. of IEEE INFOCOM ’98 Conf.
142 -
149

Cali F.
,
Conti M.
,
Gregori E.
2000
“IEEE 802.11 Protocol: Design and Performance Evaluation an Adaptive Backoff Mechanism,”
IEEE J. Selected Areas in Comm.
18
(9)
1774 -
1786
** DOI : 10.1109/49.872963**

Chatzimisios P.
,
Boucouvalas A.C.
,
Vitsas V.
2004
“Performance Analysis of IEEE 802.11 DCF in Presence of Transmission Errors,”
in Proc. of IEEE Int’l Conf. Comm.
3854 -
3858

Ghaderi Majid
,
Towsley Don
,
Kurose Jim
“Reliability Gain of Network Coding in Lossy Wireless Networks,”
IEEE Infocom 2008

Koutsonikolas Dimitrios
,
Hu Y. Charlie
,
Wang Chih-Chun
“An Empirical Study of Performance Benefits of Network Coding in Multihop Wireless Networks,”
IEEE Infocom 2009

Zhang Jin
,
Zhang Qian
“Cooperative Network Coding-Aware Routing for Multi-Rate Wireless Networks,”
IEEE Infocom 2009

Fragouli C.
,
Widmer J.
,
Boudec J.-Y. L.
“A network coding approach to energy efficient broadcasting: From theory to practice,”
IEEE INFOCOM
Barcelona, Spain
Apr. 2006

Zhang Xinyu
,
Li Baochun
“On the Market Power of Network Coding in P2P Content Distribution Systems,”
IEEE Infocom 2009

Sagduyu Y. E.
,
Ephremides A.
2007
“On Joint MAC and Network Coding in Wireless Ad Hoc Networks,”
IEEE Transactions on Information Theory

Jin Jin
,
Li Baochun
,
Kong Taegon
“Is Random Network Coding Helpful in WiMAX?,”
IEEE Infocom 2008

Hsu Yu-Pin
“Opportunities for Network Coding: To Wait or Not to Wait,”
2011 IEEE International Symposium on Information Theory Proceedings
2011

Le Jilin
,
Lui John C.S.
,
Chiu Dah-Ming
Fellow, IEEE
2010
“On the Performance Bounds of Practical Wireless Network Coding,”
IEEE TRANSACTIONS ON MOBILE COMPUTING
9
(8)

Gkantsidis C.
,
Rodriguez P.
“Network coding for large scale content distribution,”
IEEE INFOCOM
Miami, FL
Mar. 2005

Lee Uichin
,
Park JoonSang
,
Yeh Joseph
,
Pau Giovanni
,
Gerla Mario
“CodeTorrent: Content Distribution using Network Coding in VANET,”
MobiShare’2006

Park Joon-Sang
,
Lee Uichin
,
Oh Soon Young
,
Gerla Mario
,
Lun Desmond
“Emergency Related Video Streaming in VANETs using Network Coding,”
UCLA CSD TECHNICAL REPORT: TR-070016

De Couto Douglas S. J.
“A High-Throughput Path Metric for Multi-Hop Wireless Routing,”
in Proc. of ACM Mobicom
Sep.2003

Draves R.
,
Padhye J.
,
Zill B.
“Routing in multi-radio, multi-hop wireless mesh networks,”
in Proc. of ACM Mobicom
Sep.2004

Hou I-Hong
,
Tsai Yu-En
,
Abdelzaher Tarek
,
Gupta Indranil
“AdapCode: Adaptive Network Coding for Code Updates in Wireless Sensor Networks,”
IEEE Infocom 2008

Cui Tao
,
Chen Lijun
,
Ho Tracey
“Energy Efficient Opportunistic Network Coding for Wireless Networks,”
IEEE Infocom 2008

Citing 'Optimal Stochastic Policies in a network coding capable Ad Hoc Networks
'

@article{ E1KOBZ_2014_v8n12_4389}
,title={Optimal Stochastic Policies in a network coding capable Ad Hoc Networks}
,volume={12}
, url={http://dx.doi.org/10.3837/tiis.2014.12.009}, DOI={10.3837/tiis.2014.12.009}
, number= {12}
, journal={KSII Transactions on Internet and Information Systems (TIIS)}
, publisher={Korean Society for Internet Information}
, author={Oh, Hayoung}
, year={2014}
, month={Dec}