2009年12月4日 ○ 前田康成（北見工業大学） 吉田秀樹（北見工業大学） 鈴木正清（北見工業大学） 松嶋敏泰（早稲田大学）

Presentation on theme: "2009年12月4日 ○ 前田康成（北見工業大学） 吉田秀樹（北見工業大学） 鈴木正清（北見工業大学） 松嶋敏泰（早稲田大学）"— Presentation transcript:

1 2009年12月4日 ○ 前田康成（北見工業大学） 吉田秀樹（北見工業大学） 鈴木正清（北見工業大学） 松嶋敏泰（早稲田大学）
通信路状態が未知の選択再送ARQに関する一考察 2009年12月4日 ○ 前田康成（北見工業大学） 吉田秀樹（北見工業大学） 鈴木正清（北見工業大学） 松嶋敏泰（早稲田大学）

2 従来研究との関連 選択再送（Selective-Repeat：SR） ARQ 統計的決定理論に基づき スループットの最大化 連続再送
　従来研究との関連 選択再送（Selective-Repeat：SR） ARQ 統計的決定理論に基づき スループットの最大化 連続再送 に基づく方法 通信路状態１つで既知 （ブロック誤り率既知） 雨宮等2005 ① 楠堂等1998 (連続多重送信：CMT)等 通信路状態複数で未知 （ブロック誤り率未知） 本研究 ② 小松1983 （適応選択再送：ASR）等 ①斉時的なマルコフ決定過程 ②非斉時的なマルコフ決定過程

3 × × × × 選択再送（SR）ARQの概要 △ 時点 往復伝播遅延D=3 送信者 1 2 3 4 5 6 7 受信者 1 2 3 4 5
8 9 10 往復伝播遅延D=3 送信者 1 2 3 4 5 6 7 受信者 1 2 3 4 5 6 7 × × △ 受信バッファ 5 4 3 1 2 6 7 ○ ○ バッファ容量 C=4 ○ ○ × × ○ ○ ○ ACK（確認信号） NAK（確認信号） ○ 上位層へ　× 誤りを検出　△ バッファがオーバーフロー

4 マルコフ決定過程（MDP）の概要 状態集合 行動集合 利得（利得関数） 遷移確率 行動 状態 で行動 を選択した時に状態 へ遷移する確率
状態 で行動 を選択した時に状態 へ遷移する確率 遷移確率分布を支配するパラメータ(通信路状態に相当) 状態 で行動 を選択し，かつ状態 へ遷移した時に得られる利得 行動選択，状態遷移，利得獲得という一連のプロセスを繰り返して，総利得の最大化をしたい 非斉時的なマルコフ決定 複数の通信路状態（パラメータ ）がマルコフ連鎖で遷移すると仮定

5 準備（1/3） 総送信回数（再送を含め延べ 個のメッセージブロックを送信） 送信者が受信者に送信するメッセージブロック
　準備（1/3） 総送信回数（再送を含め延べ 個のメッセージブロックを送信） 送信者が受信者に送信するメッセージブロック （添え字はメッセージブロック番号） メッセージブロックの集合 受信者が誤りを検出しなかった時に送り返す確認信号 受信者が誤りを検出した時に送り返す確認信号 時点 で送信者が受け取った確認信号（ または ） 時点 で送信者が上位層に送られたことをまだ確認していないメッセージブロック番号のうちで最小の値 時点 で送信者が送信したメッセージブロック番号 受信バッファの容量 往復伝播遅延 時点 で送信者が送信したメッセージブロックに対する確認信号を送信者は時点 で受け取る

6 準備（2/3） (1) (2) (3) （MDPの行動に相当） マルコフ決定過程（MDP）における時点 の状態 ただし，
　準備（2/3） マルコフ決定過程（MDP）における時点 の状態 (1) ただし， 時点 におけるバッファの状況を表す変数で，メッセージブロック の確認信号の受信状況を示す（送信者の把握状況） (2) を基準値として を次の式で変換した値 (3) （MDPの行動に相当）

7 準備（3/3） メッセージブロックに誤りが無い確率（ACKが生起する確率）（既知）
　準備（3/3） メッセージブロックに誤りが無い確率（ACKが生起する確率）（既知） メッセージブロックに誤りが検出される確率（NAKが生起する確率）（既知） と がMDPの状態遷移確率に相当 通信路状態 有限の通信路状態集合（既知） 通信路状態の遷移確率（マルコフ連鎖）（既知） 時点 の通信路状態（未知） 帰還通信路は誤り無し 検出不能な誤りは生じない（生じる確率は十分に小さい）

8 時点 から時点 への動き (4) 時点 で行動（送信するメッセージブロック） を決定した以降の動き
　時点 から時点 への動き 時点 で行動（送信するメッセージブロック） を決定した以降の動き (1) 時点 に送信した に対する確認信号を時点 の確認信号 として送信者が受け取る (2) 時点 の状態 が時点 の状態 ，時点 の行動 ，時点 の確認信号 によって決まる（ も決まる） (3) 時点 の利得が時点 の状態 ，時点 の行動 ，時点 の状態 によって次式のように決まる (4) (4) 時点 の行動 を決定する

9 定式化（1/3） 期間のマルコフ決定過程問題（メッセージブロックを 回送信）を考える 効用関数 (5)
　定式化（1/3） 期間のマルコフ決定過程問題（メッセージブロックを 回送信）を考える 効用関数 (5) 状態と確認信号系列と時点を受け取って，送信するメッセージブロック番号を決定する決定関数 時点 以降の利得関数（メッセージブロックの送信を伴わないので，代わりに確認信号） 上位層に送られるメッセージブロック数に相当

10 定式化（2/3） 期待効用関数 (6) ただし， はMDPの初期状態で既知 は通信路の初期状態で未知
　定式化（2/3） 期待効用関数 (6) ただし， はMDPの初期状態で既知 は通信路の初期状態で未知 上位層に送られるメッセージブロック数の期待値に相当

11 定式化（3/3） ベイズ期待効用 (7) ただし， は通信路の初期状態の事前分布
　定式化（3/3） ベイズ期待効用 (7) ただし， は通信路の初期状態の事前分布 式(7)を最大にする決定関数が，変化する通信路状態が未知の場合のスループットをベイズ基準のもとで最大化する選択再送ARQ方式

12 ベイズ最適な選択再送ARQ方式 動的計画法を用いてベイズ期待効用（式(7)）を最大化 (8)
ただし， は時点 以降のベイズ期待効用（上位層に送られるメッセージブロック数の期待値）の最大値 (9)

13 シミュレーションによる比較 パターン1 パターン2 0.01 0.2 0.4 0.1 提案方法 0.823 0.537 ASR 0.803
　シミュレーションによる比較 １００回のシミュレーションの スループットの平均で評価 パターン1 パターン2 0.01 0.2 0.4 0.1 提案方法 0.823 0.537 ASR 0.803 0.511 ASRがベイズ最適な提案方法と近い性能を有していることが分かる

14 受信バッファが埋まっているため，０の確認信号を待たずに連続再送
　提案方法における連続再送（従来方法と同様） 時点 t-9 t-8 t-7 t-6 t-5 t-4 t-3 t-2 t-1 t t+1 往復伝播遅延D=4 送信者 1 2 3 4 5 受信バッファが埋まっているため，０の確認信号を待たずに連続再送 受信者 1 2 3 4 × × × △ 受信バッファ 3 2 1 3 2 バッファ容量 C=4 1 ACK（確認信号） NAK（確認信号） ○ 上位層へ　× 誤りを検出　△ バッファがオーバーフロー

15 提案方法の特徴（1/2） × × × 時点 t-6 t-5 t-4 t-3 t-2 t-1 t 往復伝播遅延D=4 送信者 1 2 3
　提案方法の特徴（1/2） 時点 t-6 t-5 t-4 t-3 t-2 t-1 t 往復伝播遅延D=4 送信者 1 2 3 ０（時点t-6送信）のNAKを受信して，０を再送 時点t-2 受信者 1 2 × × × 受信バッファ 3 ０（時点t-2送信）の確認信号は未受信だが，誤りブロックが多く観測されるので０を再送 2 時点t バッファ容量 C=4 1 ACK（確認信号） NAK（確認信号） ○ 上位層へ　× 誤りを検出　△ バッファがオーバーフロー

16 提案方法の特徴（2/2） × × 時点 t-7 t-6 t-5 t-4 t-3 t-2 t-1 t 往復伝播遅延D=4 送信者 1 2 3
　提案方法の特徴（2/2） 時点 t-7 t-6 t-5 t-4 t-3 t-2 t-1 t 往復伝播遅延D=4 送信者 1 2 3 4 5 ０（時点t-7送信）のNAKを受信して，０を再送 時点t-3 受信者 1 2 3 × × 受信バッファ 2 1 3 ０（時点t-3送信）の確認信号は未受信だが，受信バッファの状況と観測されたブロック誤りから判断して０を再送 2 時点t バッファ容量 C=4 1 ACK（確認信号） NAK（確認信号） ○ 上位層へ　× 誤りを検出　△ バッファがオーバーフロー

17 提案方法の計算量 提案方法はベイズ基準のもとでスループットを最大化できるが， 計算量は の指数オーダで膨大 動的計画法で解く時に，各時点 で
　提案方法の計算量 提案方法はベイズ基準のもとでスループットを最大化できるが， 計算量は の指数オーダで膨大 動的計画法で解く時に，各時点 で [状態数 ]×[確認信号系列数 ] 回 [動的計画法の計算]と[事後分布の更新]を実施 回の送信の問題を解くために [動的計画法の計算]と[事後分布の更新] を実施する総回数 動的計画法で送信前に求める選択リストも同様に膨大 　→　今回のシミュレーション規模でも500MB

18 まとめと今後の課題 ・通信路状態が未知の場合の受信バッファ容量が有限かつ送 信回数が有限の選択再送ARQについて，ベイズ基準のもとで
　まとめと今後の課題 ・通信路状態が未知の場合の受信バッファ容量が有限かつ送 　信回数が有限の選択再送ARQについて，ベイズ基準のもとで　 　のスループットの限界を達成する方法を導出 ・シミュレーションによる比較 ASRがベイズ最適な提案方法に近い性能を保持していることが分かった →提案方法は計算量が多いので非実用的だが，ASRのよう 　な実用的な方法の評価用には適している 今後の 課題 ・計算量の軽減 ・提案方法の特徴的な選択のルール化