広島工業大学紀要研究編
第 44 巻（2010）pp.229-233

論文

マルチパケットによる無線通信遅延の低減に関する研究
長坂康史＊・福本剛＊＊（平成21年10月31日受理）

A Study on Delay Reduction of Wireless Communication by Using Multi-Packet
Yasushi NAGASAKA and Takeshi FUKUMOTO(Received Oct. 31, 2009)

Abstract
Our computing environment is changing to the ubiquitous one in which anyone uses any information anytime and anyplace. Therefore electricity consumption is one of the most important issues, because a wireless communication is required for using anyplace. The consumption
depends on the communication time and the seize of communication data. It also strongly depends on a packet loss during the communication, which occurs by a weakness of radio waves
near the border of maximum communication distance.
This paper describes the method for reducing the communication delay, that is, the retransmission caused by packet losses, by using a multi-packet transfer. The device predicts the distance between devices using the genetic algorithm, and transfers the multiplicative data in order to reduce the retransmission by packet losses. It was confirmed that the proposed method
was effective for the reduction in the case of high packet losses.
Key Words: wireless communication, communication delay reduction method, ubiquitous computing

力の消費量も増加するという問題がある。この問題により，

１．はじめに実際にストレスなく使用できる距離はさらに短くなってし昨今では，携帯端末や PDA などの移動端末が広く普及しまうと考えられる。ており，端末間の通信では IEEE802.11x や赤外線，Bluetooth

そこで本研究では，移動端末が通信相手との距離の把握などの無線通信が利用されている。近年では，動画のようを自動的に行い，パケットロスが頻発すると予想される通なファイルサイズが大きく，高速転送を求められる通信も信距離になった場合に，パケットロスによる再送処理を回行われており，高速で低消費電力の通信が以前にも増して避するシステムの提案をする。このような問題を解決する求められている。特に移動端末において消費電力は最も注ためには，通信相手との距離の把握が必要不可欠である。

目すべき点である。その中で Bluetooth は，その消費電力

本研究で注目している Bluetooth 技術では，受信時の電波の低さから注目されており，ここ数年で急速に普及してい強度により，送信相手との距離を知ることが出来る。しかる。しかし，Bluetooth の通信距離は最大でも 100m 程度し，電波強度には距離が同じであっても，周りの環境などと短い。また，限界通信距離付近では頻繁にパケットロスによりその値が大きく変化するという問題がある。

を起こし，再送処理のためスループットが低下し，また電＊＊＊広島工業大学情報学部情報工学科＊＊＊

日立ソフトウェアエンジニアリング株式会社― 229 ―

そこで本研究では，遺伝的アルゴリズムと過去の情報を長坂康史・福本利用することで，この電波強度への環境などからの影響を剛

3.2

過去値の利用より小さくし，より正確な距離の把握を行う［1］［2］ことを

歩行中の人間の移動速度を考えると，１秒程度で数ｍも目的とする。さらに，パケットロスによる再送処理の問題移動することは考えにくい。つまり，１秒程度前にいた場に対しては，あらかじめ複数個のパケットを送ることによ所の付近に現在もいる可能性が高い。この過去の情報も利り，再送要求，またはタイムアウトによる通信遅延を回避用することにより，誤差を抑制する。

することを目的としたマルチパケットシステムを提案する。

3.3

遺伝的アルゴリズム

遺伝的アルゴリズムとは，ジョン・H・ホランドによっ

２．マルチパケットシステムて提案された近似解を探索するためのアルゴリズムであ本研究におけるマルチパケットシステムでは，距離推定と再送処理回避の２段階のアルゴリズムを利用することでる。遺伝的アルゴリズムの処理の流れの例を図２に示す。
以下ではこの図を用いながら説明を行う。

処理を行う。
距離の推定は Bluetooth の電波強度を利用する。電波は送信元からの距離が離れるほど減衰していく性質があるた
め，これを数値化した受信電波強度（RSSI）を利用することで距離の推定を行うことが出来る。しかし，このRSSI は測定する環境により値が変動し，同距離で取得した場合でも平均 50cm 前後の誤差が生じてしまう。
そこで，本研究では，一時刻前に取得した値と，遺伝的アルゴリズムを利用することにより，この誤差の縮小を図る。
また，再送処理の回避は，まず，推定した距離からパケットロス率を推定する。そして，推定されたパケットロス率に応じた，最も効率の良い個数の同パケットを送信する。

図２

これにより，パケットロスによるタイムアウトやパケットエラーなどによる再送処理にかかる時間を短縮する。

まず，観測値として５回の RSSI の取得を行い，それを保持する。この時，過去の値がある場合は５回の観測値の３．マルチパケットアルゴリズム
3.1

遺伝的アルゴリズムの流れ後ろにその値を付け加えることにより利用する。

誤差縮小アルゴリズム

初期集団の生成では，観測値の取得で得られた５つ（過誤差を小さくする一番簡単な方法は，値の測定回数を増去の情報を使用する場合は過去の情報を加えた数）の値ひやすことである。数千個の値を取得し，その平均を取れば，とつひとつに対して，選択するかしないかの決定をランダ最も確からしい値に収束する。しかし，それでは取得に時ムで行う。これを１サイクルとし，５サイクル行う。こうす間がかかってしまう。そこで本システムでは，出来るだけることにより，サイクルごとに違った選択・非選択のパター

少ない測定回数で，最も確からしい値に近づけることを目

ンを得ることが出来る。これを選択パターン個体と呼ぶ。
評価では，初期集団で生成した選択パターン個体ひとつ的とする。
本システムでは，一時刻前の過去値の利用と遺伝的アルゴリズムの２つを利用することにより，これを達成する。

ひとつに対して行い，適応度 fi を求める。この時の評価関数は式（１）の通りである。

め，その予測パターンで選択された値の平均が推定値となΣ ｛（¦x ¦−¦x−x ¦）x́ ｝
f ＝
Σ ＝x́

る。

i は選択パターン個体の番号であり，それぞれの選択パその簡単な流れを図１に示す。図のように，観測値と過去N

k=1の値から遺伝的アルゴリズムによって予測パターンを求

iMAX

kN

k=1

ik

（１）

ik

ターン固体が生成された順番の番号を持つ。k は選択パターン個体の中に収められている観測値の順番号である。N は観測値の数である。x は観測値の中で一番大きな値である。
xMAX は観測値の平均である。x́ は選択されていれば１にな
図１

誤差縮小アルゴリズムの流れ

り，選択されていなければ０が入っている。つまり x́ik は，i 番目の選択パターン個体の k 番目の観測値が選ばれてい― 230 ―

マルチパケットによる無線通信遅延の低減に関する研究

るかどうかの判定を行っている。これにより選択されてい定により得た距離とパケットロス率の関係を図３に示す。

ない場合の解は常に０になり，評価に影響しない。

ここでのパケットロスは，リンクが確立できた場合に通選択では，評価のステップで選択パターン個体それぞれ信中に発生したパケットロスを指す。よって，リンクが確にふられた適応度を基に行う。選択はルーレット選択法を立できなかった場合の数は含まれていない。リンクエラー用いる。ルーレット選択法では式（２）を用いて選択確率とは，リンクの確立が行えなかった割合である。この結果pi を求める。この式により，全体に対して自分の占める割より，17m になるとリンクの確立が確実に行えなくなって合を求めることが出来る。つまり，適応度の高いものほどいることが分かる。

選択確率が高くなり，結果的が選ばれやすくなる。逆に適応度の低いものは選ばれにくくなる。これを選択パターン個体の個数回行う。

p i＝fiΣ

Nf

（２）

k=1 k

交叉では，前ステップで選択された選択パターン個体同士でペアを作り，お互いの選択パターンの一部を入れ替える。ペアの作り方は選択された選択パターン個体から順番

図３にペアを作っていく。交叉は２点交叉を行う。２点交叉と距離とパケットロス率の関係

は，交叉点と呼ばれる入れ替え場所をランダムで２点選び，次に，RSSI から推定パケットロス率を求めるために，交叉点で挟まれた部分をペアと入れ替える。交叉を行うこ

図３と同距離で RSSI の測定を行った。各距離で RSSI のとで，それまでにはなかった選択パターンを作り出すこと取得を 20 回行い，その平均と標準偏差を求めた。また，が出来る。

求めた値から最小二乗法により，近似直線を求めた。その淘汰では，選択のステップで選ばれなかった選択パター結果を図４に示す。

ン個体は削除される。これにより，選択されなかった個体，つまり評価値の低い個体が消えて，評価値の高いものが生き残っていくことになる。
交叉によって作られた新しい選択パターン個体を，再度評価する。これにより，前世代の時より評価値の高いものが見つかる可能性がある。遺伝的アルゴリズムはこの評価・選択淘汰・交叉を指定した回数繰り返すことで，より評価値の高い選択パターン個体を選び出すアルゴリズムである。指定した回数繰り返した後，最終的に評価を行い，そ図４の時に最も評価値の高い選択パターン個体を選び出す。同じ評価値のものが存在した場合，評価パターン個体の番号の若い方が選ばれる。

RSSI と距離との関係最後に，図５は図３と図４から RSSI とパケットロス率の関係を表したグラフである。

遺伝的アルゴリズムにより決定されたパターンに収められている観測値の平均を，最も確からしい値とする。本システムでは，最終的に算出された推定値をその時の RSSIとし，事前に用意しておいた観測モデルと比較することにより，その時のパケットロス率を推定し，パケットロス率が高い相手かどうかを判断する。
3.4

観測モデル

本システムの開発にあたり，距離とパケットロスの関係を明確にする必要がある。測定では，各距離で 20 個のパ図５

RSSI とパケットロス率の関係ケットを送信し，その応答率からパケットロス率を求めた。
これを 10 回行い，その平均を求めた。また，得られた値から，最小二乗法を利用することで近似直線を求めた。測図５を観測モデルとして利用することにより，推定したRSSI に応じたパケットロス率を導き出す。

― 231 ―

長坂康史・福本

3.5

マルチパケットアルゴリズム

剛合は，送信端末へ MP_REQ を返すことで再送信を行う。

誤差縮小アルゴリズムにより得た結果から，パケットロ受信時に，マルチパケットにより同一パケットが複数個ス率が高いと判断した場合に，事前に複数個のパケットを送られてきた場合には，２個目以降の同一パケットを破棄送ることで再送処理時間の無駄をなくす。

する必要がある。このため，すでに受信を終えたパケットこの処理を行うにあたり，パケットロス率に応じた最もに関してはそれ以降の同一パケットを全て破棄する。

効率の良い同時送信パケット個数を知る必要がある。そこ

送信後，一定の時間が経過しても応答がない場合，再送で，０% 〜 90% のパケットロスを故意に発生させ，各パケッを行う。タイムアウト時間は 100ms とした。これはパケッ

トロス率の時に最も効率の良いパケット数をシミュレー

トを送り，その返信が返ってくるまでの時間 RTT（Roundションにより求めた。その結果，表１のような結果を得た。

Trip Time）の約５倍を設定した。TCP のタイムアウト

マルチパケットアルゴリズムの実験では，これを利用して時間の初期値「RTT ×４＋ α」を参考にし，α=RTT とす実験を行う。

ることで，RTT の５倍を設定した。測定を行った結果，

表１

最適個数

RTT の平均は 20ms であったため，100ms を設定するこ

各パケットロス率に応じた最適パケット数

0% 102030405060708090

1233345552ととした

４．性能評価本システムの性能評価では，誤差縮小アルゴリズムを評また，この時送信するパケットの構成は図６のように価し，その後マルチパケットアルゴリズムの評価を行った。

な っ て い る。 先 頭 か ら ８ ビ ッ ト の Code，16 ビ ッ ト の誤差縮小アルゴリズムの実験を以下の環境で行った。測Length，16 ビ ッ ト の Sequence Number， ８ ビ ッ ト の

定場所は屋内の障害物の無い直線を利用した。測定に使用

Check Sum となっている。Code にはデータの種類選別のした Bluetooth 端末は，USB タイプの Bluetooth アダプタためのコードが入れられる。Length にはデータ長が入れを挿したノート PC と，Bluetooth 機能を搭載した携帯電られる。Sequence Number には現在の送信パケット番号話の２台を使用した。測定範囲は 1m 〜 10m とし，2m 間が入れられる。Check Sum には誤り検出のための値が入隔で測定した。

れられる。
Code（8bit）

実験方法は，まず各距離に対して５回の測定を行い，平Length Sequence
NumberCheckSum

データ部分（16）（8）（80）

図６（16）

均を求める。これを通常平均とする。次に，同じ５つの測定データを使用し，本アルゴリズムを適応する。これを１サイクルとし，各距離に対して 20 サイクル行った。そして求められた各距離 20 個の値の平均と偏差を求めた。そ本システムのパケット構成の後，通常平均の値と本アルゴリズムを適応した RSSI を，本システムで使用する Code は，通常パケットを表す
Single_Packet， 本 シ ス テ ム 用 の パ ケ ッ ト を 表 す Multi_

予め用意しておいた観測モデルと比較することにより比較を行う。

Packet，応答 MP_ACK，再送要求 MP_REQ の４つである。

測定を行い，この時の誤差と偏差に注目した。これを図Sequence Number は，何番目に送信したパケットがロ７に示す。図中の縦軸では観測モデルと比べた時の誤差をスしたのかを判断するために用いる。送信時に，パケット表し，横軸ではその時の距離を表している。また，その時の番号を Sequence Number に入れ送信を行い，受信側はの実際の数値と全体の誤差平均を表２に示す。

同番号の Sequence Number と MP_ACK を返すことにより，その番号の送信が成功したか否かの判断を行う。また，パケットに問題が起こり，MP_REQ が返ってきた場合，その時の Sequence Number を見ることにより，どのパケットを再送信すべきかを知ることができる。
Check Sum は，最後のデータ部分を１バイトごとに全て足し合わせ，その結果のビット列の下位８ビットを入れて送信を行い，受信側でも同じように受信したデータ部分を計算し，受け取った Check Sum と比較することにより，送信時に発生したデータ部分のデータ誤りを知ることができる。受け取った Check Sum と受信後に生成した値が違う場― 232 ―

図７

誤差縮小アルゴリズムの測定結果

マルチパケットによる無線通信遅延の低減に関する研究
表２

この結果から分かるように，本システムを適応すること

測定結果詳細値と全体の平均（単位 :m）

距離（m）

246810平均により，パケットロスが発生する状況による通信遅延を低

通常平均

0.63

0.40

0.150.81

0.450.48減することが出来た。ただし，15m 地点の結果を見ると，

提案手法

0.47

0.27

0.21

0.48

0.08

0.30

マルチパケットの方が時間がかかっている。これは送信パケット個数を見てわかるように，何度か重複パケットを提案手法を用いることにより，通常平均と比べ，全体で約 30% の誤差縮小を行うことに成功した。

送っていることが分かる。この重複パケットを送信したことで，遅延が発生してしまったと考えられる。他の地点でマルチパケットアルゴリズムの実験では，15m 〜 16.5mは通信遅延の低減に成功しており，パケットロスの確率がの各距離で 10 バイトのパケットを 100 個送信し，送信開高まるほどにその効果が顕著に現れており，16.5m 地点で始から受信完了までの時間を測定する。これを単一パケッは 34% の遅延時間の低減に成功した。

トの通信の場合と，本システムを適応した場合とで各 20回測定を行い，その平均を比較する。

５．まとめ比較を行った結果を，図８に示す。縦軸は送信開始から本研究では，Bluetooth 技術を用いたマルチパケットに受信完了までかかった時間をミリ秒で表している。また，よる無線通信遅延の低減に関する研究を行った。本研究で横軸は測定を行った時の距離を表している。シングルパは，推定した距離から予測パケットロス率を求め，パケッ

ケットは，本システムを適応していない，単一パケットのトロス率が高いと判断した時，再送要求を受ける前の送信みでの送信の場合の結果を表している。マルチパケットと時に，あらかじめ複数個のパケットを送ることで遅延の低本システムを適応した複数パケットを送信した場合の結果減を行った。距離の推定には通信相手の Bluetooth 端末かを表している。また，この時の詳しい数値と送信パケットらの電波受信強度を利用した。この電波受信強度は周りの数を表３に示す。この表でのパケット数とは，各距離での環境に影響を受けやすく，誤差が大きい問題があったため，実験で同時送信したパケットの個数の平均を表している。

誤差縮小アルゴリズムを適応することにより，その誤差の縮小を行った。また，そこで得られた電波受信強度から推定を行い，パケットロス率に応じた個数の同一パケットを送信することにより，単一パケットのみでの通信と比べどの程度通信遅延を低減できたのかの検証を行った。その結果，パケットロス率が上昇するにつれ本システムを適応した方が通信遅延を低減することができ，最大で 34 % の遅延時間の低減に成功した。

参考文献
図８

本システムの実験結果

表３［1］福本，長坂：「Bluetooth を用いたモバイルコンピュータの位置推定システムの開発」，FIT2008

実験結果の詳細

第７回情報科学技術フォーラム，pp.229-230（2008）

15m

15.5m

16m

16.5m

シングル

559.85 ms

2573.883643.4422846.58［2］福本，長坂：「Bluetooth を用いたモバイルコンピューマルチ

602.03 ms

1744.491988.20

15163.18

タ間の位置推定アルゴリズムの研究」，RENTAI2008，

1.4 個

3.6

3.7

4.8

パケット数

p.288（2008）― 233 ―