アドホックネットワークにおけるバーチャルバックボーンの構築の研究

(1)

1/4

日下裕貴

アドホックネットワークにおけるバーチャルバックボーンの構築の研究

A Study of Construction of Virtual Backbone in Ad Hoc Wireless Network

情報工学専攻日下裕貴

HINOSHITA Yuki

概要アドホックネットワークとは，無線

LAN

のようなアクセスポイント

(基地局)

を必要としない，無線で接続できる端末のみで構成されたネットワークのことである．本研究では，アドホックネットワークにおいて，仮想的なインフラとなるバーチャルバックボーンの要素を選出する問題を考える．

本論文では，この問題に対して，2002年に

Xiuzhen，

Ding-zhu [1]

らによって提案されたアルゴリズムを実装し，計算機実験を通してその近似性能を評価した．さらに，そのアルゴリズムに改善を加え，通信量，バーチャルバックボーンの要素数の変化といった観点から実験的性能評価を行った．

1

序論

アドホックネットワーク

(ad hoc network)

とは，インフラや中央管理施設等を必要とせずに，無線端末間の通信を可能とするネットワークのことである．端末はそれぞれ移動端末であるので，各端末は自由に移動することができる．また，端末がネットワークから取り除かれたり，新たな端末がネットワークに参加することも起こり得ることから，ネットワークのトポロジーは動的に変化するといえる．さらに，それぞれの端末はそれぞれが自律分散的にネットワークを形成していることから，本ネットワークにおいて，通信相手を特定するためにはフラッディング

(ﬂooding)

という通信方法を行う必要がある．しかし，この方法はネットワーク上に過度のデータ衝突や不和を引き起こし，大きなプロトコルオーバーヘッドの原因となり得る．

このような問題を軽減するため，ネットワーク上に仮想的なインフラ

(バーチャルバックボーン (virtual

backbone))

を構築する様々な研究が進められた．その

中で，

2002

年に

Xiuzhen，Ding-zhu [1]

らによって，それぞれの端末に通信速度の遅さなどのコストを与えた場合における，よりコストの低い端末で構成する効率的なバーチャルバックボーンの構築が提案された．

そこで，本研究では，この

Xiuzhen

らのアルゴリズムを実装し，実験を行うことでその性能を評価した．また，その手法に改善を加え実験し，通信量，バーチャルバックボーンの要素数や要素の変化といった観点からその性能を評価する．

2

問題定義

アドホックネットワークにおける移動端末

(以下ノー

ドと呼ぶ)の個数を

n

とする．全てのノードは地上に存在し，全て全方向性のアンテナが取り付けられてい

るとする．また，全てのノードの通信範囲を

R

とする．

すなわち，各ノードの通信範囲は，自身を中心とした半径

R/2

の円となる．ノードの集合を

V

，ノード間のリンクの集合を

E

とすると，アドホックネットワークのグラフ

G

は

G = (V, E)

と表すことができる．ノード

u ∈ V

とノード

v ∈ V

との間にリンクが存在するということは，uと

v

との距離が高々Rであることを意味し，このようにして得られるグラフを

Unit disk graph

と呼ぶ．

図

1 Unit disk graph

2.1

バーチャルバックボーンの定義

バーチャルバックボーンを構築するノードを決定するには，最小連結支配集合

(Minimum Connected Domi- nating Set

：MCDS)を利用する．最小連結支配集合に含まれるノードには以下のような性質がある．

2.2

最小連結支配集合

1.

最小連結支配集合に含まれるノード数は最小化される．

2.

最小連結支配集合に含まれる全てのノードは連結している．

3.

最小連結支配集合に含まれていないノードは，最小連結支配集合に含まれているノードと必ず隣接している．

最小連結支配集合に含まれるノードをバーチャルバックボーンの構成要素とすることで，できる限りサイズを小さくしたバーチャルバックボーンを得ることができる．しかし，Unit disk graphにおいて，最小連結

(2)

2/4

日下裕貴

支配集合を求めることは

NP

困難であることが証明されている．従って，最小連結支配集合を緩和した連結支配集合

(Connected Dominating Set：CDS)

を用い，

バーチャルバックボーンの要素となるノードを決定する．連結支配集合とは支配集合

(Dominating Set)

のノードを連結させた集合であり，以下に詳しく性質を述べる．

2.3

連結支配集合

支配集合を

D

とする．

D

は

V

の部分集合である．

D

に含まれていないノードは，Dに含まれているノードと少なくとも一つは隣接している．隣接する

2

つのノード

(u, v)

が存在し，u

∈ D, v 6∈ D

であるとき，uを支配点

(dominator)，v

を被支配点

(dominatee)

と呼ぶ．

また，このとき，uは

v

を

“支配している”

という．

u, v ∈ D

である場合，どちらかを支配点とする．また，Dが連結しているとき連結支配集合となり，この集合に含まれるノードをバックボーンの要素とする．

2.4

付加条件

さらに，本研究では

Xiuzhen

らの研究と同様，それぞれのノードにコストを付加した．この場合，コストとは端末の通信速度の遅さや消費電力の大きさなどを指す．これにより，バーチャルバックボーンを構築する要素に，よりコストの低いノードを選出するという条件が加えられる．

また，ノード間の情報

(ノードのコストやリンクの有

無など)は，自身のノードと隣接している

(1hop)

以内のノードのみとする．つまり，自身のノードから

2hop

離れたノードのコストや状態を把握することはできない．

3 Xiuzhen

らのアルゴリズム

[1]

バックボーンを構成するノードは，< dominator

(u, dom, l) >，< dominatee(u, dom, l) >，< active (u) >

という

3

つのメッセージをノード間で取り交わしながら選出していく．最初にメッセージを流すノードはリーダー

(leader)

に選ばれた

1

つのノードだけである．

3.1

メッセージとノードの状態

まず，Xiuzhenらのアルゴリズムで使用されるパラメータと，それぞれのノードが流すメッセージについて説明する．その後，ノードの状態について述べる．

dom：そのノードを支配している支配点．

rank

：隣接したノードとの関係を示す．または，リーダーからのレベル．

W

：隣接したノードのコストを要素とする集合．

< dominator(u, dom, rank) >：ノード u

が支配点となるときにブロードキャストされるメッセージ．

u

の支配点が

dom

であることと，uの

rank

を表す．

< dominatee(u, dom, rank) >：ノード u

が被支配点となるときにブロードキャストされるメッセージ．u の支配点が

dom

であることと，uの

rank

を表す．

< active(u) >：ノード u

が

active

の状態となるときブロードキャストされるメッセージ．

隣接するノードにメッセージをブロードキャストし，

メッセージを受け取ったノードはそのメッセージに応じて状態を変化させる．ノードの状態は

4

つ存在する．

S

0：初期状態．支配点でも被支配点でもない状態．

S

₁：ノードが被支配点である状態．

S

2：ノードが

active

である状態．この状態のノードの中から支配点となるノードが選出される．

S

3：ノードが支配点である状態．

以下にメッセージの伝達によるノードの変化を記す．

グラフ

G

において，全てのノードの状態が

S

1，もしくは

S

₃となったら終了する．

1.

まず，リーダーのノードは

< dominator (u, dom) >

をブロードキャストする．その後，

状態を

S

3に変化させる．

2.

状態が

S

0 か

S

2 のノードが

< dominator (u, dom, rank) >

を受け取った場合，domと隣接していたら

dom = dom, rank = rank

とし，

そうでなければ

dom = u, rank = rank + 1

として

< dominatee(u, dom, rank) >

をブロードキャストする．その後，状態を

S

3.

状態が

S

0 のノードが

< dominatee (u, dom, rank) >

を受け取った場合，dom

= u, rank = rank + 1

とし，< active(u)

>

S

2に変化させる．また，domを

W

から削除する．

4.

状態が

S

₂ のノードが

< dominatee (u, dom, rank) >

を受け取った場合，u を

W

から削除する．また，コストが

dom

より

u

の方が小さかったら，dom

= u, rank = rank + 1

とする．

5.

状態が

S

0か

S

2のノードが

< active(u) >

を受け取った場合，uのコストを

W

に加える．

6. W

の中のコストと

u

のコストを比較し，

u

のコストが最小であった場合，u は

<

dominator(u, dom, rank) >

S

7.

状態が

S

₂ のノードが

< dominator (u, dom, rank) >

を受け取り，dom

= u

であった場合，< dominator(u, dom, rank)

>

S

3 に変化させる．

8.

状態が

S

3のノードで，そのノードを支配点としているノードが一つも存在しなかった場合，<

dominatee(u, dom, rank) >

S

₁に変化させる．

(3)

3/4

日下裕貴

4

提案手法

Xiuzhen

らの提案したアルゴリズムは，リーダーの

ノードから始まり，徐々にバーチャルバックボーンの要素となるノードを広げていくというアルゴリズムであった．それに対し，本研究の提案手法は，ノードが移動することによって非連結となってしまったバーチャルバックボーンの要素を再び連結させるというアルゴリズムである．ネットワークのトポロジーが変化する度に最初からバーチャルバックボーンを構築するのではなく，以前はバーチャルバックボーンの要素だったノード同士を連結させることで，バーチャルバックボーンの要素の変化を軽減でき，ネットワークの変化に柔軟なバーチャルバックボーンを維持することが可能となる．

4.1

提案

1

提案

1

では，新たに

< search(u) >

というメッセージと

search

状態である

S

4を加える．

状態が

S

4のノードは，Xiuzhenらの提案したアルゴリズムにおける

active

の状態と似た動作を行う．こうすることで，グラフ上に支配点がほとんど存在していない部分があったとしても，連結支配集合を作ることができる．しかし，この手法だけでは非連結となったバーチャルバックボーンが連結することはない．バーチャルバックボーンを連結させるために，次の提案

2

を行う．

提案

2

は，非連結となったバーチャルバックボーンの先頭のノード

(自身を支配しているノードと隣接し

ていないノード)が，以前自分を支配していたノードを探し，見つかればそのノードと連結するという操作である．また，提案

1

と同時に行われている．

4.2

提案

2

提案

2

では，新たに

dom

p という，以前そのノードを支配していた支配点を表すパラメータと

<

research(u, dom

p

) >

research

状態である

S

₅を加える．

提案

2

は，非連結となったバーチャルバックボーンのノードを連結させるとき，連結する側のノードと連結される側のノードを特定して連結させる手法である．

これは，ノードを特定しないで連結させようとした場合，バーチャルバックボーンに閉路ができてしまう可能性が高いからである．非連結となったバーチャルバックボーンの先頭のノードや，そのノードを以前支配していたノードはそれぞれ一つに特定され，それぞれを連結する側のノード，連結される側のノードとすることで閉路を作ることなくバーチャルバックボーンを連結させることができる．しかし，提案

2

では，連結される側のノードが連結する側のノードの近く

(3hop

以内) に存在しない場合，バーチャルバックボーンは連結することができない．

提案

2

を行った後も連結していないバーチャルバックボーンは，次の提案

3

を行って，近くに存在するバーチャルバックボーンと連結させる．

4.3

提案

3

提案

3

では，新たに

< break(u) >

break

状態である

S

5を加える．

提案

2

との違いは，提案

3

は連結させる側のノードを特定していないところである．代わりに，まだ連結していないバーチャルバックボーンのノード全てを

break

状態とすることで，それらのノードは既に連結しているバーチャルバックボーンのノードと区別することができる．こうして，連結する側のノードは連結させる側のノードを特定しなくても良く，一番近くに存在するバーチャルバックボーンと閉路を作ることなく連結することができる．

5

実験的性能評価

5.1

実験方法

本研究の実験では，Xiuzhenらのアルゴリズムと提案手法との比較を行った．

まず，100

× 100

の座標平面に移動端末をランダムに配置し，Unit disk graphを作成した．それぞれの手法を用いてバーチャルバックボーンを構築した後，グラフに変化を与えるため，各端末の

x

座標，y座標に-5から

5

の値をランダムに与えた．この数字は端末間のリンクや状態などの情報を伝えるハローメッセージ

(hello message)

が

5

秒間隔で交わされていることと

(これに

よってメッセージの交換が始められる)，人間は

1

秒間に平均

1.1m

歩くということを考慮した結果である．このように変化していくグラフに対し，同じグラフを

2

つの手法を用いてバーチャルバックボーンを構成する要素の変化と情報量を求めた．ここでいう情報量とは，

ネットワーク全体を流れたデータ

(メッセージ)

の総量を指す．

さらに，端末の数を

100

から

1000

個まで変化させ，

通信範囲を

15

と固定して，それぞれ

100

回ずつ計算し，その平均を取ることで評価した．しかし，

Unit disk

graph

において，ノード数が

300

個を下回るとリンク

が連結されることが困難になり，100回計算することができなかった．それぞれの場所でバーチャルバックボーンを構築するという方法も考えたが，それは，結局バーチャルバックボーンを構築しても通信できない端末が現れるということとなり，本研究の意図から外れるものと判断し，考慮に入れなかった．

また，最初のバーチャルバックボーンを構築する手

法は

Xiuzhen

らのアルゴリズムを用いた．

以下に実験で使用した計算機を示す．

• CPU：Intel(R) Core(TM)2 1.86GHz

•

メモリ：2GB RAM

• OS：Windows XP Home Edition

•

コンパイラ：Microsoft Visual C++6.0

5.2

実験結果

バーチャルバックボーンの要素数は全体のノード数が増えるにつれて増加していった．しかし，

Xiuzhen

ら

(4)

4/4

日下裕貴

表

1

バーチャルバックボーンの要素数の変化

0 50 100 150 200 250 300

300 400 500 600 700 800 900 1000 ノード

ノードノードノード数数数数要

要要要素素素素数数数数

既存手法提案手法変化無し　既存変化無し　提案

のアルゴリズムが緩やかに増加するのに対し，提案手法では増加の割合が大きい結果となった．これは，提案したアルゴリズムが前回バーチャルバックボーンだった要素を多く保持し，そのノード数をあまり減少させずにバーチャルバックボーン同士を連結させるという方法を取ったためであると考えられる．

しかし，変化の無い要素数，つまり，前回から引き続きバーチャルバックボーンの要素に選出されたノードの数は，Xiuzhenらのアルゴリズムを大幅に改善できたといえる．これは，提案手法が，アドホックネットワークにおいてネットワークの変化により対応した，

柔軟性を持ったバーチャルバックボーンを構築できたことを示している．

表

2

バーチャルバックボーンのコストの変化

0 50 100 150 200 250 300 350 400 450

300 400 500 600 700 800 900 1000 ノードノード

ノードノード数数数数コココ

コススス

ストトトト既存手法

提案手法

コストに関しても，バーチャルバックボーンの要素数の結果と同じ理由が考えられる．バーチャルバックボーンを構成する要素数が増加したら，それに伴ってコストも増加する．

表

3

ネットワークの通信量の変化

0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

300 400 500 600 700 800 900 1000 ノードノードノード

ノード数数数数通通

通通信信信信量量量量

既存手法提案手法

バーチャルバックボーンの要素数，コストとは逆に，

通信量は

Xiuzhen

らのアルゴリズムを大幅に改善でき

た．通信量が安定しているとはいえないが，平均的に

Xiuzhen

らのアルゴリズムよりも良い解が，特に，ノー

ドの数が増加するに従って良い解が出ていることが分かる．

6

結論

本研究では，アドホックネットワークにおけるバーチャルバックボーンの構築を行った．

この問題に対して，Xiuzhen，Ding-zhuらの提案したアルゴリズムの実装，評価を行い，また，改善を行うことで，バーチャルバックボーンを構築する際の通信量を大幅に減少させ，より柔軟なバーチャルバックボーンを構築することができた．しかし，要素数やコストに関してはあまり良い解を得ることができなかった．

今後の課題としては，バーチャルバックボーンのノードが非連結となったときに，コストの高い要素を排除する方法の考案や，また，より現実に近い入力を与え実験を行うこと，さらには，バーチャルバックボーンのノードに負担がかかりすぎないよう，バーチャルバックボーンの要素と他のノードを適度に交換する方法の考案などが挙げられる．

謝辞

本研究を進めるにあたり，適切なご指導，熱心なご指摘を頂きました浅野孝夫教授に心から感謝致します．

参考文献

アドホックネットワークにおける バーチャルバックボーンの構築の研究

1/4