統計的決定理論に基づく複数のクラスに属する文書の分類方法

A Note on Theoretical Limit of
Type-I Hybrid Selective-repeat ARQ
with Finite Receiver Buffer
Yasunari MAEDA (Kitami Institute of Technology)
Hideki YOSHIDA (Kitami Institute of Technology)
Toshiyasu MATSUSHIMA (Waseda University)
1
Topics
1. Introduction
2. Preparations
3. Modeling
4. Proposed algorithm
5. Experiments
6. Conclusion
2
1. Introduction
overview of type-I hybrid selective-repeat ARQ
codeword
transmitter
binary symmetric
channel
feedback channel
noiseless
received block
receiver
acknowledgement
symbol
ACK (a positive acknowledgement symbol)
no bit error or correctable bit errors in the received block
NAK (a negative acknowledgement symbol)
uncorrectable bit errors in the received block
3
1. Introduction
example of operation in type-I hybrid selective-repeat ARQ
time 1
2
3
4
5
6
7
8
9
10
round-trip delay D=3
transmitter 1
2
3
4
2
5
receiver
1
×2
3
4
×2
receiver buffer
size of
receiver buffer
C=4
6
2
6
7
5 △6
2
6
5
3
○1
×2
4
4
4
3
3
3
×2
7
5 ○5
4 ○4
3 ○3
○2 ○6 ○7
ACK
NAK ○ delivered to the user
× undetectable errors △ buffer over flow
4
1. Introduction
overview of Markov decision processes
r s1 , a1 , s2  reward
action
a1
state
1
p( s2 s1, a1,  * ) transition probability
a2
state
2
s
s
p( s2 s1, a1,  )
*
*
r s1 , a1 , s2 
S  s1 , s2 . set of states
A  a1 , a2 . set of actions
a probability of an event that a state transition from state s1
to state s 2 is occurred when action a1 is selected at state s1
a true parameter of transition probability (known)
a reward of a state transition from state s1 to state
the condition that action a1 is selected at state s1
s 2 under
target : to maximize total rewards
5
1. Introduction
the theoretical limit of throughput of type-I hybrid
Selective-repeat ARQ
the theoretical limit of
throughput with infinite
receiver buffer
many previous research
the theoretical limit of
throughput with finite receiver
buffer
our research
In previous research many type-I hybrid selective-repeat ARQ
methods with finite receiver buffer are proposed.
But the throughput of the proposed methods can not be
compared with the limit with finite receiver buffer.
We study the theoretical limit of throughput of type-I hybrid
selective-repeat ARQ with finite receiver buffer.
6
2. Preparations(1/4)
mi , mi  M .
a codeword which a transmitter wants to send


M , M  m1 , m2 ,, m M .
a set of codewords
ACK a positive acknowledgement symbol
NAK a negative acknowledgement symbol
w t an acknowledgement symbol received by the transmitter at time t
z t the minimum number of a codeword whose ACK symbol is not
received yet at time t
y t the number of codeword which is transmitted at time t
C
D
the size of finite receiver buffer
a round-trip delay
(The transmitter receives the acknowledgement symbol for
at time t  D.)
yt
7
2. Preparations(2/4)
x t a state at time t in Markov decision processes(MDP)
xt  xt , 0 , xt ,1 ,, xt ,C 1 , yt, t D1 ,, yt, t 1 ,
where, x represents a situation of the receiver buffer.
t ,i


(1)

 1, the transm itter knows that mzt  i is in the rexeiverbuffer ;
xt , i  
(2)

 0, else ,
yt, i
represents codeword already sent by the transmitter.
, i  1 or i  T ;
 2

, the transmitter knows that m yi is deliveredto
 1
yt, i  
the user or m yi is in the receiverbuffer ;

(3)
 y  z , else .
t
 i
yt, i    2 ,  1, 0 , 1 ,  , C  D  2 . （actions in MDP）
8
2. Preparations(3/4)


p erb 
p ACK 

a bit error rate of a BSC(binary symmetric channel)

 ,   .
 * ,  *  .

the probability of an event that a receiver sends
back ACK symbol
a parameter which dominates p er 

b

the true parameter which is known
 

Nc  n 


p ACK   p Ne  Nc      1  p erb 
i 0 i 
pNAK    1  pACK  
ni perb  i
(4)
(5)
assumptions
(n,k) linear code is used, feedback channel is noiseless,




p Ne  Nc   p Ne  Nd  ,
where,
Nc
Ne
Nd
the maximum number of correctable bit errors
the number of bit errors in the received block
the maximum number of detectable bit errors
9
2. Preparations(4/4)
operations from time
t
(after deciding action
to time
t 1
yt, t at time t
)
(1) Transmitter receives an acknowledgement symbol wt 1 at time t
( wt 1 is for codeword sent at time t  D  1 )
 1.
(2) State xt 1 at time t  1 and zt 1 are computed by using state x t at time t ,
action yt, t at time t and acknowledgement symbol wt 1 at time t  1.
(3) Reward at time t is computed by using state x t at time t , action
at time t and state xt 1 at time t  1.
C1x  C1x  1,
 t ,i
t 1, i

i 0
r xt , yt ,t , xt 1    i 0

 0,
(4) Action
yt, t
ACK symbol is received and
some codewords are sent to
the user ;
else .
(6)
yt1, t 1 at time t  1 is decided.
10
3. Modeling(1/2)
modeling to solve T  D periods MDP problem
utility function

U x
T D
, d   ,  , w ,
T

*


T  D 1
  r xi , yi, i , xi 1   r xi , wi 1 , xi 1  ,
T
where,
iD
d , 
(7)
i T 1
decision function which returns the number of
codeword to send by using the state and time
r xi , wi1 , xi1 
reward after time T  1
eqs.(7) is equal to the number of codewords which
are delivered to the user.
11
3. Modeling(2/2)
expected utility function

EU d   ,  , *


x T  D1 , wT




p xT  D 1 , wT x1 , d   ,  , * U xT  D , d   ,  , wT , * ,
(8)
where, x1 is first state and known.
expected value for the number of codewords which are
delivered to the user
In order to compute the theoretical limit with finite
receiver buffer, we have to maximize the expected utility.
12
4. Proposed algorithm
compute the maximum of eqs.(8) by using dynamic
programming method

V xt , t   m ax p wt 1 
yt , t
*

wt 1
r x , y , x   V x
t
t,t
t 1
t 1

, t  1 ,
(9)
where, V  xt , t  is the maximum of expected utility after
time t  1.
(Expected utility is equal to the expected value for the
number of codewords which are delivered to the user.)
the theoretical limit of throughput
with finite receiver buffer
V  x1 ,1
T
13
5. Experiments(1/2)
conditions
a round-trip delay D=4
size of receiver buffer C=4, C=8
number of sending codewrods T=1000
bit error rate 0.001, 0.01
using (255,115)BCH code，3 conditions
N c  3, N d  39 , N c  2, N d  40 , N c  1, N d  41
N c :the maximum number of correctable bit errors
N d :the maximum number of detectable bit errors
ISR : theoretical limit with infinite receiver buffer（  pACK   ）
PRO : proposed theoretical limit with finite receiver buffer
WEL : an averaged throughput of 1000 times simulations by
Weldon’s method
(Weldon’s method is one of typical selective-repeat ARQ
methods. And we apply Weldon’s method to type-I hybrid for
the experiments.)
14
5. Experiments(2/2)
case of N c  2, N d  40, C  4
bit error rate
ISR
0.001
0.997737
0.01
0.530352
PRO
WEL
0.997708
0.997663
0.449197
0.425040
The differences between
ISR and WEL are big,
but the differences
between PRO and WEL
are small.
The performance of
WEL is close to the
theoretical limit with
finite receiver buffer.
Our proposed theoretical limit with finite receiver buffer is
useful to investigate the performance of previous methods.
15
6. Conclusion
We applied Markov decision processes to type-I hybrid
selective-repeat ARQ with finite receiver buffer.
We proposed the algorithm which computes the theoretical
limit of throughput of type-I hybrid selective-repeat ARQ
with finite receiver buffer.
The theoretical limit of throughput computed by our
proposed algorithm is useful to investigate the performance
of previous type-I hybrid selective-repeat ARQ methods
with finite receiver buffer.
As further works, we want to study the relationship of
throughput and decoding error probability.
16

Download Report