CDMA ALOHA - 片山研究室

博士論文 公聴会OHP
CDMA ALOHA方式における
最適アクセス制御方式の研究
名古屋大学 工学研究科 電子情報学専攻
小川研究室
岡田 啓
1999年2月
Copyrighted Hiraku Okada 1999 all rights reserved.
CDMA ALOHA方式における
最適アクセス制御方式の研究
小川研究室
岡田 啓
H. Okada, Ogawa Lab., Nagoya Univ.
目次
1. 本研究の背景と目的
2. CDMA ALOHA方式のスループット特性
3. パケットの再送に着目したアクセス制御
4. バッファリング機能を利用したアクセス制御
5. 本研究のまとめ
H. Okada, Ogawa Lab., Nagoya Univ.
移動体通信の動向
累計加入者台数
万台
5000
4000
3000
インターネットの普及予想
無線呼出
PHS
携帯電話
1997年 2005年 2010年
2000
利用者数
1000
利用世帯数
0
87 88 89 90 91 92 93 94 95 96 97 98年
年度
5月末
世帯普及率
1,115万 4,136万 4,459万
287万 1,929万 2,755万
6.4%
41.8%
54.9%
我国の移動電気通信事業加入数の推移
携帯電話やPHS, ポケットベルの
ここ数年の急激な増加
インターネットの目覚しい普及
無線データ通信の需要のさらなる増加
H. Okada, Ogawa Lab., Nagoya Univ.
これからの移動体通信
急速な需要の増加に対応
音声, データ, 画像等の情報源に対応
十分な通信容量
マルチメディア化
世界中どこでも使える
世界規模での
ローミング
次世代移動体通信システム (IMT-2000) の世界標準化
H. Okada, Ogawa Lab., Nagoya Univ.
次世代移動体通信の最も有力な候補
符号分割多元接続 (CDMA) 方式
信号空間を符号によって分割し,
各ユーザに割り当てる多元接続方式
数
波
時
間
特徴
ランダムアクセスが可能である
マルチメディアに適している
移動体通信に適している
同時送信局数の増加に対し, 誤り率が穏やかに変化する
自局の信号が他局に干渉を与えてしまう (多元接続干渉)
H. Okada, Ogawa Lab., Nagoya Univ.
周
回線交換とパケット交換
回線交換
パケット交換
通信を始める前に回線を確保
してから通信を行う
送りたい情報に宛先などの情報を
付加してパケット化
一度回線を確保すれば,
最後まで回線を独占できる
間欠型通信においても無線回線
の使用効率が高い
実際に情報が流れていない
ときにも回線を独占
いつでも回線を確保できる保証
なし
データ通信の分野では
パケット交換方式が有望視されている
H. Okada, Ogawa Lab., Nagoya Univ.
ALOHA方式
無線パケット通信における最も基本的なアクセス用プロトコル
各ユーザはパケットを送りたいときに送出
システムの簡単さ
ランダムアクセス可能
packet
hub station
user 1
user 2
user k
同時に１つのパケットしか送ることができない
collision
collision
collision
success
time t
H. Okada, Ogawa Lab., Nagoya Univ.
CDMA ALOHA方式
CDMA技術
同時伝送可能
マルチメディアに適する
ALOHA方式
システムの簡単さ
ランダムアクセス可能
パケット単位で送信
CDMA ALOHA方式
ランダムアクセスの簡便性
高効率なパケット通信の可能性
次世代移動体通信, 特に無線データ通信,
マルチメディア通信にとって有望な方式
H. Okada, Ogawa Lab., Nagoya Univ.
CDMA ALOHA方式の問題点と課題
同時に複数のパケットを伝送可能
同時送信局数が時々刻々と変化
誤り率が緩やかに変化
特性解析の複雑さ
同時に多くのパケットが送信されると
その影響が送信中のすべてのパケットにおよぶ
アクセス制御の必要性
H. Okada, Ogawa Lab., Nagoya Univ.
本研究の目的
CDMA ALOHA方式の特徴を考慮した特性解析
アクセス制御の観点から特性向上策の提案
本発表では
パケットの再送に着目したアクセス制御
バッファリング機能を利用したアクセス制御
H. Okada, Ogawa Lab., Nagoya Univ.
自分の研究の流れ
バッファリング機能を
利用したアクセス制御
指数長パケット
東海大会 (H6-10)
固定長パケット
ユーザ数無限
CDMA ALOHA
全国大会 (H7-3), 研究会 (H8-12)
ユーザ数有限
全国大会 (H9-3), 論文誌 (H10.7)
待時式
CDMA
ALOHA
再送パケットを考慮
システムの安定性
研究会 (H7-5), 論文誌 (H8-9)
CDMA Slotted ALOHA
CLSP
パケットの再送に着目
したアクセス制御
シンポジウム (H9-12), 国際会議 (H10-6),
論文誌 (H10-7)
ORC
CDMA Unslotted ALOHA
国際会議 (H10-10), 論文誌 (H10-10)
パケットの送信制御
パケットの再送制御
研究会 (H7-5), 論文誌 (H8-9)
MCLSP
アクセス制御遅延
の影響を和らげる
国際会議 (H8-11), 論文誌 (H8.12)
OACP
CLSPを適用した
待時式 CDMA ALOHA
パケットの送信と再送制御
研究会 (H7-12), 国際会議 (H8-7),
全国大会 (H9-3)
H. Okada, Ogawa Lab., Nagoya Univ.
目次
1. 本研究の背景と目的
2. CDMA ALOHA方式のスループット特性
3. パケットの再送に着目したアクセス制御
4. バッファリング機能を利用したアクセス制御
5. 本研究のまとめ
H. Okada, Ogawa Lab., Nagoya Univ.
CDMA ALOHA方式
CDMA unslotted ALOHA方式
Time
t
パケットをスロットと呼ばれる
時間枠に同期して送信
Number of packets
Number of packets
パケットをすきなときに非同期
に送信
CDMA slotted ALOHA方式
t
Time
H. Okada, Ogawa Lab., Nagoya Univ.
Throughput S
[packet/Tp ]
CDMA Slotted ALOHA方式とCDMA Unslotted ALOHA方式の比較
6
N=60
L=L=500 [bits]
Eb/No=10 [dB]
5
4
CDMA Slotted ALOHA
3
CDMA Unslotted ALOHA
2
1
0
0
5
10
15
20
Offered load G
25
30
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
目次
1. 本研究の背景と目的
2. CDMA ALOHA方式のスループット特性
3. パケットの再送に着目したアクセス制御
4. バッファリング機能を利用したアクセス制御
5. 本研究のまとめ
H. Okada, Ogawa Lab., Nagoya Univ.
パケット再送過程
パケットが正しく受信されなかったとき,
パケット再送が必要
平均 Tw=
パケット発生
ユーザ局
中央局
packet
再送要求
受信
待ち時間
1
の指数分布に従う
λr
パケット再送
packet
t
packet
packet
t
パケット受信
失敗
パケット受信
再送要求
終了
成功
H. Okada, Ogawa Lab., Nagoya Univ.
新規モードと再送モード
成功
失敗
新規モード
失敗
再送モード
成功
新規モードのユーザ
再送モードのユーザ
新規パケットを生成
再送パケットを送信
λo: 新規パケットの生起率
λr: 再送パケットの送出率
送る情報の発生状況に
より決まってしまう値
ユーザ局において設定可能
操作することが容易
H. Okada, Ogawa Lab., Nagoya Univ.
期待流動値 d(r)
研究会 (H7-5), 論文誌 (H8-9)
システムの安定性を調べるための指標
期待流動値
d(r)
新規モード
再送モード
再送モード
新規モード
再送モードのユーザ
状態 r =
ユーザ全体
d(r) > 0
再送モードのユーザが増加
( 状態 r が増加 )
d(r) < 0
新規モードのユーザが増加
( 状態 r が減少 )
d(r) = 0
平衡状態
H. Okada, Ogawa Lab., Nagoya Univ.
期待流動値
4
Go=6.13
期待流動値 d(r)
3
Gr=35
2
1
Go=K λo Tp
Gr=K λr Tp
Gr=25
0
-1
K: ユーザ数
Tp: パケット長時間
Gr=5
-2
Gr=15
-3
-4
0
0.2
0.4
0.6
0.8
1
状態 r (= 再送モードのユーザ／ユーザ全体)
H. Okada, Ogawa Lab., Nagoya Univ.
Optimal Retransmission Control (ORC)
研究会 (H7-5), 論文誌 (H8-9)
パケット再送を制御することにより
特性の向上を図る
望ましくない安定状態に陥るのを防ぐ
H. Okada, Ogawa Lab., Nagoya Univ.
再送パケットのコントロール方法
中央局 : 再送パケットの送出率 λr(r) を選ぶ
λr(r) をユーザー局に知らせる
ユーザ局 : λr(r) に従ってパケットを再送
Tp
ユーザ局
パケット
平均 Tw=
再送待ち時間
1
の指数分布に従う
λr (r)
パケット
t
中央局
失敗
成功
t
パケットの再送過程
H. Okada, Ogawa Lab., Nagoya Univ.
λr(r) の選び方
状態 r が小さいところで安定
期待流動値をできるだけ小さくする
λr(r) =
Gmax
(1 r) Go
Tp K r
Gmax : スループットを最大にするオファードロード
Go=K λo Tp
K : ユーザ数 Tp : パケット長時間
Throughput S
5
4
CDMA ALOHA
System
3
2
1
0
0
5 G max
10
15
20
Offered Load G
H. Okada, Ogawa Lab., Nagoya Univ.
期待流動値
4
Go=6.13
期待流動値 d(r)
3
Gr=35
2
1
no access
control
Gr=25
0
-1
Gr=5
-2
Gr=15
-3
ORC
-4
0
0.2
0.4
0.6
0.8
1
状態 r (= 再送モードのユーザ／ユーザ全体)
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
スループット特性
7
6
ORC
Throughput S
5
4
3
no access control
2
N=60
L=500 [bits]
Eb/No=10 [dB]
1
0
0
5
10
15
20
[packet/Tp ]
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
ORCではスループットの最大値は制御を行わない場合と同じ
Optimal Access Control Protocol (OACP)
全国大会 (H9-3), 研究会 (H7-12), 国際会議 (H8-7)
パケットの再送制御に加え,
パケット送信を制御することにより
スループットの最大値を向上する.
H. Okada, Ogawa Lab., Nagoya Univ.
パケットの送信制御
Channel Load Sensing Protocol (CLSP)
A. H. Abdelmonem et. al
・中央局がチャネル伝送中のパケットの数を観測
・チャネル伝送中のパケットの数が
スレッショルド以上
スレッショルド未満
パケット送信を拒否
パケット送信を許可
同時送信局数をスレッショルド以下に抑えることができる
4
channel 3
load 2
1
0
sensing
threshold
packet transmission
t
H. Okada, Ogawa Lab., Nagoya Univ.
OACPを用いたときのパケットの流れ図
新規パケット
生起率 λo
同時送信局数が
スレッショルド未満？
(送信制御)
伝送に
成功した
パケット
許可された
パケット
チャネル
Yes
No
再送パケット
再送率 λr(r) を制御
(再送制御)
拒否された
パケット
伝送に失敗した
パケット
ランダム
再送遅延
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
スループット特性
7
OACP
CLSP only
6
ORC only
Throughput S
5
4
3
no access control
2
N=60
L=500 [bits]
Eb/No=10 [dB]
1
0
0
5
10
15
20
[packet/Tp ]
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
CDMA パケット通信のスループットの上限値
発生したパケットが全て成功
同時送信局数が増えるとパケット成功確率は劣化するため,
スループットには上限が存在
7
Throughput S
6
5
4
3
2
1
00
5
10
15
20
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
スループット特性
7
OACP
upper
bound
6
CLSP only
ORC only
Throughput S
5
4
3
no access control
2
N=60
L=500 [bits]
Eb/No=10 [dB]
1
0
0
5
10
15
20
[packet/Tp ]
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
[s/Tp ]
遅延特性
200
N=60
L=500 [bits]
Eb/No=10 [dB]
K=1000
Delay D
150
no access control
ORC
CLSP
100
50
0
OACP
0
5
10
15
20
[packet/Tp ]
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
アクセス制御遅延
パケットの伝搬や処理に要する時間遅延
パケット
ユーザー局
アクセス制御の情報
中央局
伝搬時間
処理時間
ユーザー局
伝搬時間
処理時間 時間
アクセス制御遅延
アクセス制御の情報がアクセス制御遅延だけ古くなる
特性の劣化が生じる
特に衛星通信を用いるときに影響が大きい
低軌道衛星 (1,000km):0.013 [s]
静止衛星 (36,000km):0.5[s]
H. Okada, Ogawa Lab., Nagoya Univ.
アクセス制御遅延の影響
アクセス制御遅延の分だけ
アクセス制御に関する情報が古くなる
CLSPでは
時々刻々と変化する値(同時送信局数)に基づいて制御
特性に大きく影響
4
channel 3
load 2
1
X
0
sensing
controlled by old
information
threshold
packet to be transmitted
packet transmission
access timing delayTD
t
H. Okada, Ogawa Lab., Nagoya Univ.
Throughput S [packet/Tp ]
CLSPを用いた場合におけるアクセス制御遅延の影響
7
N=60
L=500 [bits]
Eb/No=10 [dB]
α =9
6
5
τD =0 (no access timing delay)
τD =0.1
τD =0.26
(LEO)
4
3
without
CLSP
τD =1
2
τD =9.2
(GEO)
1
0
0
5
10
15
Offered load G
20
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
アクセス制御遅延の影響を和らげるには
短時間において変動しない情報に基づいて制御
ORCでは
状態 r に基づいて制御
状態 r : 再送モードのユーザ数／全ユーザ数
状態 r は短時間ではあまり変動しない
system
state
r
controlled by
system state r
constant
packet to be transmitted
packet transmission
access timing delayTD
t
H. Okada, Ogawa Lab., Nagoya Univ.
Throughput S [packet/Tp ]
OACPを用いた場合におけるアクセス制御遅延の影響
7
6
5
OACP
τD =0
=0.1
=0.26
=1
=9.2
4
3
N=60
L=500 [bits]
Eb/No=10 [dB]
2
1
0
0
5
No access
control
10
15
20
[packet/Tp ]
Offered load Go
(all users are in originating mode)
H. Okada, Ogawa Lab., Nagoya Univ.
パケットの再送に着目したアクセス制御
まとめ
パケットの再送を制御するORCを提案
パケットの送信と再送の両方を制御するOACPを提案
ORCを用いることで, 望ましくない安定状態に陥るのを
防ぐことができる.
OACPを用いることで, スループット特性, 遅延特性を
向上させることができる.
OACPはアクセス制御遅延が存在しない場合において,
スループット特性を最適にすることができる.
アクセス制御遅延が存在しても, OACPは非常に有効な
アクセス制御方式である.
H. Okada, Ogawa Lab., Nagoya Univ.
目次
1. 本研究の背景と目的
2. CDMA ALOHA方式のスループット特性
3. パケットの再送に着目したアクセス制御
4. バッファリング機能を利用したアクセス制御
5. 本研究のまとめ
H. Okada, Ogawa Lab., Nagoya Univ.
CDMA ALOHA方式
パケットの伝送に失敗
パケットの再送が必要
パケット再送を行っている間に発生したパケット
呼損として扱う
パケット再送中
中央局
パケット
呼損
ユーザ局
H. Okada, Ogawa Lab., Nagoya Univ.
呼損を減らす
バッファリング機能
バッファリング機能とは
各ユーザにバッファを設け, 発生したパケットをいったん
バッファに蓄えてから, パケットを送信
中央局
パケット
バッファ
ユーザ局
H. Okada, Ogawa Lab., Nagoya Univ.
待時式CDMA ALOHA方式の提案
国際会議 (H10-10), 論文誌(H10-10)
各ユーザはパケットを蓄えることのできるバッファを持つ
新規パケットの呼損を減らすことができる
ユーザ局による自律的なアクセス制御ができる可能性を有する
λ
K ユーザ
ユーザ局
λ
中央局
λ
B パケット
H. Okada, Ogawa Lab., Nagoya Univ.
各ユーザにおけるパケットの送信方法
バッファが空のとき
遅延時間を減らすため
新規パケットを直ちに送信
バッファが空でないとき
送信レート p でパケットを送出
p=Gmax/K
Gmax : スループットを最大にするオファードロード
K : ユーザ数
平均 1/p の指数分布に従う
ユーザ局
パケット
送信間隔
パケット
t
H. Okada, Ogawa Lab., Nagoya Univ.
ユーザ局におけるパケットの流れ図
新規パケット
バッファ
は空?
λN
アイドル モード
Yes
ビジー No
モード
コピー
チャネルへ
送信
レート p
で送出
バッファ 蓄える
は満杯? No
Yes
バッファ
正しく伝送
呼損
バッファから削除
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
6
Throughput S
送信レートを変化させたときのスループット特性
4
p=0.10 (=Gmax/K)
5
p=0.05
p=0.15
3
p=0.20
N=60
Eb/No=10dB
K=100
L=500 [bits]
B=3
2
1
0
0
5
10
15
20
Offered load of new packet GN
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
6
Throughput S
バッファに蓄えられるパケット数を変えたときのスループット特性
4
5
3
B=1
2
3
4
5
2
1
0
0
5
N=60
Eb/No=10dB
K=100
L=500
p=0.1
10
15
20
Offered load of new packet GN
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
バッファに蓄えられるパケット数を変えたときの呼損率特性
Rejection probability Q R
1
10
10
10
10
-1
-2
B=1
2
3
4
5
-3
N=60
Eb/No=10dB
K=100
L=500
p=0.1
-4
0
5
10
15
Offered load of new packet GN
20
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
CLSPを適用した待時式CDMA ALOHA方式
チャネルにパケットを送出する前に送信制御
同時送信局数がスレッショルド未満ならパケットを送出
新規パケット
バッファ アイドル モード
は空?
λN
No
ビジー Yes
モード
CLSP
コピー
レート p
で送出
バッファ 蓄える
は満杯? No
Yes
同時送信局数
がスレッショルド
Yes
未満？
チャネルへ
送信
バッファ
正しく伝送
呼損
バッファから削除
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
CLSPを適用した待時式CDMA ALOHA方式のスループット特性
7
N=60
Eb/No=10dB
K=100
L=500
B=5
6
Throughput S
5
with CLSP
τD =0
=0.1
=0.26
=1
=9.2
w/o CLSP
4
3
2
1
0
0
5
10
15
20
Offered load of new packet GN
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
[packet/Tp ]
CLSPを適用した待時式CDMA ALOHA方式のスループット特性
7
N=60
Eb/No=10dB
K=100
L=500
B=5
6
Throughput S
5
with CLSP
τD =0
=0.1
=0.26
=1
=9.2
w/o CLSP
4
3
2
OACP
1
0
0
5
10
15
20
Offered load of new packet GN
[packet/Tp ]
H. Okada, Ogawa Lab., Nagoya Univ.
バッファリング機能を利用したアクセス制御
まとめ
待時式CDMA ALOHA方式を提案
特性評価を行った
バッファ数を増やすことにより, 呼損率を下げ,
スループット特性を向上できることがわかった.
CLSPを用いた待時式CDMA ALOHA方式を提案
OACPを用いたCDMA ALOHA方式と同等の
スループット特性を得ることができた
H. Okada, Ogawa Lab., Nagoya Univ.
目次
1. 本研究の背景と目的
2. CDMA ALOHA方式のスループット特性
3. パケットの再送に着目したアクセス制御
4. バッファリング機能を利用したアクセス制御
5. 本研究のまとめ
H. Okada, Ogawa Lab., Nagoya Univ.
本研究のまとめ
次世代移動体通信
CDMA ALOHA方式が重要な役割を果たす
CDMA ALOHA方式の特性解析, 特性評価
特性向上を目的とし, これを実現するアクセス
制御方式の検討
パケットの送信と再送を同時に制御するOACPの提案
バッファを設けることで呼損を減らし, 特性向上を図る
待時式CDMA ALOHA方式の提案
CDMA ALOHA方式の単純さを保ちつつ,
高能率化を図ることができるアクセス制御方式
H. Okada, Ogawa Lab., Nagoya Univ.
今後の展開
データのみならず, 音声や画像
などの複数メディアを扱う
マルチメディア通信の要望
移動体通信においては通信路の
状態は時々刻々と変動する
発生するトラヒックや通信路の状態に対応して
適応的にアクセス制御することが必要
H. Okada, Ogawa Lab., Nagoya Univ.