負荷分散手法

TCPTCP

4.6 負荷分散手法

セッションマネージャは正しい裏表情報を位置計算サーバに伝えることで，左右情報の修正内容を伝える．以降，位置計算サーバはすべての端末のセッションマネージャに対して裏表情報の修正された相対位置を通知する．

A

B

C

位置推定端末

位置推定端末位置推定端末位置推定端末位置推定端末

割当割当

割当割当リストリストリストリスト

A B C

・・

・

図 4.9: 位置推定端末の動的割当

これらの情報が共有されていない場合でも，位置推定端末の交代は可能である．しかしその場合には，次に位置推定端末の役割を担うことになった無線端末が上記３つの情報を改めて収集しなおさなければならず，位置推定端末交代のオーバーヘッドが大きくなると考える．

本提案ではブロードキャストベースの通信を行なうことで，これらの情報を位置推定に参加する全無線端末であらかじめ共有する．

位置推定対象となる無線端末のリストは，位置推定端末が算出した位置推定結果と共に配布される．位置推定端末を担当する順序はこのリストを元に各端末に共有される．そのため，

各無線端末は位置推定結果を受信すると同時に，自身が次の位置推定端末であるか否かを判定できる．また，各無線端末は位置推定端末の割当順序を把握出来るため，たとえ次に位置推定端末に割り当てられていた端末がLSAC環境から離脱している場合でも，その次に位置推定端末に割り当てられている端末が，タイムアウト処理等を行なうことで位置推定端末となれる．

無線端末，特に携帯端末はラップトップを始め高機能なものもあれば，携帯電話のように計算処理に劣るものもある．位置推定端末の割り当て順を決定する無線端末リストは，このような各無線端末の計算資源や通信資源を考慮して割当順序を決定することが考えられる．

しかしながら，本研究の評価におけるプロトタイプでは，簡単な実装として無線端末リストへの登録順で無線端末リストを作成している．すなわち，図4.9に示すように，このリストにはネットワークに参加している端末が参加した順に並べられ，この順で位置推定端末の役割を各端末に動的に割り当てる．

提案手法による位置推定計算の基本的な手順は以下の通りである．

1. 各無線端末は位置推定端末によりブロードキャストされた位置推定結果を受け取り，自身が次に位置推定端末に割り当てられているか否かを判定する．

2. 各無線端末は直接通信可能な周囲の無線端末が出すパケットを受信し，それらの電波強度を測定する．

3. 各無線端末は測定した電波強度情報を，距離情報に換算する．

4. 各無線端末は距離情報を，ブロードキャストする．

5. 位置推定の役割を割り当てられた無線端末は，受信した距離情報を元に，各無線端末の位置を推定する

6. 位置推定端末は位置推定結果をブロードキャストする．

7. 各無線端末は位置推定結果から位置推定端末の割当順序を取得し，自身が位置推定端末になる順番であればその役割を果たす．

5.において，位置推定を開始するためのトリガーとして以下の２点が挙げられる．1)ある一定量の距離情報が貯まる，2)ある一定時間が経つそれぞれの特徴として，前者は距離情報があまり集まらない時は位置推定を行わないで良い点で，資源利用の効率性に優れているといえる．また，後者は定期的な位置推定を保証でき，前者に比べ情報の反映が早い点で即応性に優れていると言える．本論文でのシミュレーションでは，前述したとおり位置推定端末

に割り当てられていた端末が離脱した際のタイムアウト処理などを考えて，時間をトリガーとして位置推定を行なう．

また，距離情報や位置推定結果にはシーケンス番号をつける．ブロードキャストベースで通信を行なう際に，パケット損失の影響が考えられる．そのため，各無線端末が受信した距離情報が最新のものとは限らない．そこで，位置推定端末が位置推定に利用する距離情報が最低でも前回までの位置推定に利用されていないことを判断し，古い情報であった場合にはその距離情報を破棄することとする．それを判断する情報としてシーケンス番号を用いる．

4.6.2 位置推定計算の負荷軽減

上述したとおり，WiPS手法での位置推定の計算量は無線端末数nに対してO(n²)であった．そこで，一度の計算負荷を軽減する手法として，無線端末集合N(N ={hi|0≤i < n}) の部分集合のみの距離情報を用いて計算を行なう手法を提案する．

本研究では，無線端末集合Nから部分集合無線端末の中でも，前回の位置推定計算以降に移動した端末と，移動していない端末に分け，移動した端末のみの距離情報を用いて，位置推定を行なう．移動した端末数をm(0≤m≤n)，移動した端末をh⁰_iとすると，移動した端末の集合はM ={h⁰_i|0≤i≤m < n} ⊆N で表せる．このとき，移動したかどうかは各端末が判断するものとし，移動したと判断した端末が，測定した距離情報をブロードキャストする．このとき，Fig.4.10の様に，移動していない端末間の電波強度は変化が少ないと考えられ，これらの距離情報を排除して位置推定を行ってもある程度の精度が見込める．本手法は特に会議中などのユーザの移動が少ない時には有効であると考えられる．

位置推定計算の実行時間に関しては，hi,h⁰_iそれぞれの位置を−→p_i,−→p⁰_iと表す．移動した無線端末h⁰_iから測定した，ある無線端末h_jとの距離をd_i,jとすると，提案手法は次の条件を最小化する近似解を求めるものといえる．

m−1X

i=0 n−1X

j=0

¯¯

¯−→p⁰_i− −→p_j^¯^¯¯−d_i,j^¯^¯¯ (4.5) この時，計算量はO(mn)程度と考えられ，0≤O(mn)≤O(n²)である．