基幹車両を使ったマルチヘッドクラスタリングの性能評価
M2014SC011 熊澤 秀俊
指導教員: 河野 浩之

1

はじめに

一方で MCH の停車などに起因してクラスタが解散す
ると SCH や CM (Cluster Member) はどのクラスタにも属さない UN (Undecided Node) に戻り，クラスタを再形成するオーバヘッドが発生する．また CM からみてクラスタ間の移動は提供されておらず，クラスタから離反すれば UN に戻り他のクラスタを探すか MCH となってクラスタを形成しなければならない．

VANET (Vehicular Ad Hoc Network) と呼ばれる車々間のネットワークを作る研究がなされている．移動体通信の中でも高い移動性，地域や時間帯によって大きく変化するノード密度などの VANET 特有の性質が周波数帯域の圧迫やトポロジの急激な変化を引き起こし，安定したネットワークの提供を困難にしている．
これらの問題に対して車両をクラスタリングし，対応 2.2 ハンドオーバを試みる研究 [1] がなされているが，移動性の高いノード
Sheu らは V2I (Vehicle to Infrastructure) における通によって形成される VANET において CH の離脱などに信基地局と車両の間のハンドオーバを提案した [3]．図 1
起因してクラスタが解散し，通信が途絶したりクラスタのように車両の基地局に対する状態 S ∈ {11, 10, 01, 00}
再形成のために生まれるオーバヘッドが問題となるので，を信号強度にもとづいて定める．あるノードが基地局から可接続性の向上や効率的なクラスタのマネジメントが重信号を受信したとき閾値以上の信号強度であった場合を要とされている．
S = 11 とする．信号強度が閾値に満たない場合は，ノー
そこで我々が提案する CH に対する安定性を評価する
ドが基地局に接近しているか離反しているかに着目し，そ指数 RSM (Relative State and Mobility) により CM がれぞれを S = 10，S = 01 とする．S = 00 は信号を受信クラスタ間でハンドオーバし，各 CM のクラスタ離脱率できないときを指す．の低下，ひいてはクラスタ所属率の向上を図る．これにより各ノードにおける可接続性の向上し，さらにクラスタ再形成のためのオーバヘッドが削減すると考えられる．
この検証にはトラフィックシミュレータ SUMO を用いて都市部におけるモビリティモデルを生成し，ネットワー
クシミュレータ ns-3 に提案アルゴリズムの追加モジュー
ルを C++14 で実装し，性能を評価する．
図 1 V2I における状態の定義とハンドオーバ
本研究論文は全 5 章で構成される．2 章では車々間通信における諸問題を解決すべく提案されたクラスタリング
データの交換するさいは自身の状態をヘッダに加えフおよびハンドオーバを解説する．3 章では我々が提案すラッディングする．あるノード
i が他のノード j からのる基幹車両を使った MCIH (Multi-head Clustering with
Inter-cluster Handover) を説明する．4 章では提案アル データを受信したさい，i の信号強度 Si が j から受信しゴリズムにもとづいて都市部シナリオにおける車々間通 たデータに記された受信感度 Sj を上回るときノード i は信をシミュレートし，5 章で提案アルゴリズムが示した性 そのデータをフラッディングする．このリレーによりデータが基地局まで伝達される．
質を評価する．
課題

2

先行研究

2.3

2.1

クラスタリングLo らのマルチヘッドクラスタリングはモビリティを評価関数に組み込むことで安定したクラスタが形成された．
また複数の MCH が一定時間接近するとクラスタを併合し領域内にクラスタを効率よく配置した．しかし CM はクラスタ間を移動できず，クラスタから離脱して一度未所属状態にならないと他のクラスタに移動できない．また Sheu らのハンドオーバは車両間の距離や速度を考慮していない．

Lo らは一つのクラスタの代表となる MCH (MasterCluster Head) と，それを補助する複数の SCH (Sub Cluster Head) を選出するマルチヘッドクラスタリングを提案した [2]．3.2 節で後述する評価式 RPM(Relative Positionand Mobility) を用いて MCH を選出する．この RPM はあるノードが近隣ノード群における位置の平均と速度の中央値に対して相対位置と相対速度を求め，郡中の移動度とする．この RPM が群中で小さいノードが MCH と 3 Multi-head Cluster with Inter-cluster
して推薦され，MCH はクラスタ内に SCH を複数配置しHandoverてクラスタサイズを増大させクラスタの乱立を抑止した．
3.1 定義また移動性の高い V2V (Vehicle to Vehicle) のためのク
Sheu らが提案した V2I における車両の通信基地局に対ラスタ形成においてモビリティを評価関数に組み込んだする状態を拡張し，クラスタベースV2V のための状態をことでクラスタの長寿命化を達成した．

提案する．任意のノード i のクラスタヘッド l に対する状態 S ∈ {11, 10, 01, 00} を定義する．とすることでクラスタの解散を低減する．これにより，空間内でのクラスタが冗長に配置されるが基幹車両は都市内で過密とならないよう配置されることから，MCH の一
11 : 受信感度が閾値を超える局集中はないものと考えられる．
10 : 受信感度が閾値未満かつ増大傾向
受信ノードが UN であるばあい，エントリテーブル内で評価式 (9) にもとづいて算出される RPM 値がもっとも小
01 : 受信感度が閾値未満かつ減少傾向
さいエントリに対して招待要求を送る．このとき α = [0, 1]
00 : 受信不能
は RPM における位置と速度の重みをあわらす．MCH は全てのノードは Role をもつ．Role は UN，CM，MCH， 基幹車両が担うが，地域や時間帯によっては基幹車両がSCH の 4 種類である．UN はクラスタに属していないノー ないばあいが考えられる．このときは Lo らによって提案ドを指す．また MCH と SCH をまとめて CH (Cluster されたアルゴリズムを使って MCH を選出する．
Head) と呼ぶ．
クラスタ間ハンドオーバ
さらに相対位置 Rel Dist，相対速度 Rel Speed を次のMCH からの離反にともなって，クラスタから離反し一ように定義する．この研究では平面上で車両が移動していると仮定 (D = 2) する．位置 P および速度 v と近 時的に UN におちいり通信不可となる．この問題を解決
隣車両の基準値として位置 Pc ，速度 vc を考える．前者 するために我々の提案する評価式 (10) を用いてクラスタ
は相対位置 Rel Dist の算術平均をとり，後者は相対速度 間ハンドオーバを実現する．このとき β = [0, 1] は RSM
Rel Speed の中央値をとる．m 台の近隣車両と h 台の CH における状態と速度の重みをあわらす．
が近隣に存在するとき，それぞれの集合を M，H とする．
2 点間の受信感度は state とする．

P =[x1 , x2 , . . . , xD ]
m
∑

(1)

1Pim i=1(2)

Rel DistAB =PA − PB

(3)

Pc =vc =M edian{vi |i ∈ M }Rel SpeedAB =|vA − vB |stateki)+
M ax{stateki , k ∈ H}
Rel Speedki(1 − β)M ax{Rel Speedki , k ∈ H}

RSM =β(1 −(4)(5)

M ={1, 2, . . . , m}(6)

H ={1, 2, . . . , h}(7)stateAB =11, 10, 01, 00(8)

ここでは受信感度は距離に比例して増減するものと仮定する．

(10)

MCH は定期的に HELLO メッセージを送信しており，そのメッセージは周囲のクラスタに属するノードも受信できる．つまり各々のノードは自身の周囲にあるクラスタとの安定性を常に評価できる状況にある．
各ノードは周囲のクラスタに対する RSM 値を記録するテーブルをもつ．自身が所属するクラスタとの RSM 値が閾値を超えていなければハンドオーバはなされない．しかし，閾値を超えたばあいテーブル内でもっとも RSM 値が小さいクラスタに移る．
3.3

メッセージ

MCIH では全ノードが定期的に広告する HELLO，クラスタへの登録要求がRGSTREQ (Registration Request)
3.2 MCIH の概要
メッセージ，対する応答が RGSTREP (Registration ReHELLO メッセージply) メッセージ，クラスタヘッドへの推薦に ELECT メッ
各ノードは定期的に HELLO メッセージを広告する． セージ使う．
HELLO メッセージには自身の IPv6 アドレス，属する
Hello メッセージは全ノードから All Nodes Multicast
CH の IPv6 アドレス，位置，速度，RPM，Role，クラ に宛てて発信され，自身の IPv6 Global Unicast Address，スタサイズで構成されている．RPM は式 (9) で得る．
位置，速度，RPM，RSM，Role，そして発信者が CH である場合は自身のクラスタに属するメンバの数が記録される．Hello を受け取ったノードはその情報にもとづいて
Rel Distic
RP M =α ·3.4 節で述べる近隣リストにエントリを登録，または更新
M ax{Rel Distjc , j ∈ M }する．また時間 Tout を超えたエントリはタイムアウトとRel Speedic(9) して削除する．
+ (1 − α) ·M ax{Rel Speedjc , j ∈ M }RGSTREQ メッセージは UN または CM から All
近隣に CH がいない場合は，RPM 値が最も小さいノー Routers Multicast に宛てて発信され，登録先 CH の IPv6ドを MCH として推薦しクラスタを形成する．
Address と自身の IPv6 Address が記録される．受信した
CH は登録先アドレスと自身がもつアドレスを比較し，自基幹車両を使ったクラスタリング
身宛ての場合はクラスタメンバとして登録し RGSTREP
我々の提案では特定の地域を巡回し，走行時間が長く公メッセージを送る．自身宛てでないが CM リストの中に共性の高いタクシーやバスなどの基幹車両を専任の MCH

発信者のアドレスが登録されている場合は，当該エントリを削除する．
RGSTREP メッセージは CH から RGSTREQ に記録されていた発信者 IP アドレスに向けて発信される．UNが受信した場合は，自身のクラスタヘッドとして登録して Role を CM に変更する．CM が受信した場合は，自身のクラスタヘッドを変更する．
ELECT メッセージは UN の近隣に CH に存在しない
場合に MCH を推薦するときに UN から UN へ発信される．発信の基準は HELLO メッセージで交換される値にもとづいて RPM が最も小さい UN が推薦される．
ELECT メッセージは SCH を MCH は推薦するさいにも利用し，CM に発信される．受信した CM は SCH への昇格する．

3.4

utility モジュール全体で共通するマクロ定義など：137 行
icho 実験シナリオ：2498 行
4.2

地図データ

我々は Open Street Map から取得した南山大学名古屋キャンパス周辺の地図を使った．緯度および経度は35.1493,136.9624 である．使用した地図を図 2 に示す．

近隣ノードリスト

IPv6 における Link local multicast が届く範囲を近隣とし，Neighbor List に記録する．Neighbor List のエン
トリは，IP Address，既知であれば MAC Address，エントリの有効期限，位置，速度，RPM，State，Role で構成される．近隣ノードは Hello メッセージを受信したさいに追加または更新される．有効期限が切れたエントリが見つかればその都度削除していく．

4実験

4.1

実験環境と実装実験に使用したツールと，実装したプログラムについて説明する．我々は ns-3 に C++で新たに記述した MCIHモジュールを追加した．

OSM Open Street Map はフリーの地図情報データを作成，共有するプロジェクトである．当研究においてOSM から取得した南山大学名古屋キャンパス周辺の地図情報をモビリティシミュレーションに用いた．
JOSM Java OSM Editor は Java で記述された OSMファイル用のエディタおよびビューアである．
SUMO Simulation of Urban Mobility はオープンソー
スのモビリティシミュレータである．シミュレーショ
ン結果は xml ファイルで出力されるが，同梱されているツール群で各種ファイル形式へと変換できる．
ns-3 Network Simulator 3 は C++で記述され，Pythonへのラッパをもつネットワークシミュレータである．
clang clang は LLVM (Low Level Virtual Machine) を使った C，C++，Objective-C，Objective-C++用のコンパイラである．MCIH モジュールは clang 3.6.1でコンパイルした．
実装した ns-3 用の追加モジュールは 6 つにわけて説明する．追加モジュールおよびシミュレーションのシナリ
オファイルは C++14 で記述されている．
mcih モジュール全体を管理：1416 行
routing-table 経路情報を管理：192 行
packet 各種メッセージのヘッダを定義：844 行
neighbor 近隣リストを管理：592 行

図 2 JOSM を使った地図の表示と編集

実験の概要
表 1 に示したパラメタにもとづいて，MCIH を RPMのみを用いた CPM (Center-Position and Mobility)[2] と比較する．基幹車両比率は全車両に対して基幹車両が含まれる割合である．
表 1 設定したパラメタ
シミュレーション時間
300s
MAC プロトコル
IEEE802.11p
車両数30 台基幹車両比率0, 10, 20, 30, 40, 50%
ブロードキャスト間隔 (BI) 0.5s
タイムアウト
2 × BI
実験には SUMO (Simulation Urban Mobility) と ns-3
(Network Simulator 3) を使う．
SUMO は地図データとノードが移動する経路を生成し交通流をシミュレートするツールである．地図データは自動生成できるが，Open Street Map の地図も利用できる．我々は SUMO version 0.23 を使った．
ns-3 は様々な通信プロトコルに対応した離散事象駆動ネットワークシミュレータである．C++を使ってスクラッチで開発され，現在は python でラップされている．我々は ns-3.23 に対して MCIH を C++で実装した新たなモジュールを追加した．

評価基準
高い移動性をもつ VANET においてクラスタリングが有効 [1] であるが，クラスタを形成するにはノード同士が情報を交換しなければならず各ノードが本来望む通信以外に余計な通信が発生する．これは帯域を圧迫し通信を阻害する可能性を示唆している．MCIH はこの帯域の圧迫を緩和する．これを示すために MCIH が発するパケッ
ト数とクラスタの安定性の 2 点に着目して評価する．
パケット数
MCIH が発する HELLO，RGSTREQ，RGSTREP，RESIGN，ELECT のうち定期的に発信する HELLOを除いた 4 種のパケット数を比較する．
クラスタ安定性
基幹車両の増加にともなうクラスタの安定性を RPMで示す．0 に近いほど安定しており，1 に近いほど不安定である．

4.3

実験

OSM から地図を取得し SUMO 用の形式に netconvertを使って変換する．randomTrip，duarouter を使って地図に対応した車両と経路情報を生成し，さらに SUMO を使ってモビリティをシミュレートする．そのシミュレーション結果を ns-3 に適用するにあたり，SUMO は xml 形式で出力するが ns-3 へは tcl 形式で入力するので traceExporterを使って変換しなければならない．変換されたデータと追加モジュールを使い，ns-3 で実験した．
MCIH が送信するパケットのうち，定期的に広告するHELLO を除いた各種パケットの数を図 3 に示した．横軸は基幹車両の比率である．

図 4 各 CM の所属クラスタの CH に対する平均 RPMせたと考えられる．一方で図 4 からクラスタの不安定性を示す RPM 値を増加させている．これは基幹車両が相対位置や相対速度を考慮せず MCH に着任するため，必ずしも安定したクラスタが形成できないことを示している．しかしクラスタ間ハンドオーバにより CM がより安定したクラスタへ移動するため，基幹車両の比率が 30%のとき，RPM を 0.443 から 0.396 に 10.6% 低減させクラスタの安定性を向上していると考えられる．

5むすび

V2V のためのクラスタリングには CH の離脱にともなうクラスタの解散およびクラスタ再編成のためのオーバヘッドという問題があった．これらの問題にたいして基幹車両を使ったマルチヘッドクラスタリングとクラスタ間ハンドオーバの適用を提案した．OSM の地図と SUMO を使い車両のモビリティファイルを生成し，MCIH と CPMを比較した．結果として，基幹車両を使ったマルチヘッドクラスタリングによってクラスタ形成パケットおよびメンテナンスパケットが減少した．一方でクラスタの安定性が低下したが，クラスタ間ハンドオーバを適用し安定性を維持した．今後，α および β を変化させることで，基幹車両増加にともなう不安定化をより抑えられると考える．

参考文献

図 3 各種 MCIH パケット数と基幹車両比率[1] Bali, R. S., Kumar, N. and Rodrigues, J. J.: clustering in Vehicular Ad Hoc Networks: Taxonomy,
Challenges and Solutions, Vehicular Communications, Vol. 1, No. 3, pp. 134–152 (2014).

各 CM の所属クラスタの CH に対する RPM を BI ごとに記録し，その平均を図 3 に示した．横軸は基幹車両の比率である．

[2] Lo, S., Lin, Y. and Gao, J.: A Multi-Head Clustering
Algorithm in Vehicular Ad Hoc Networks, International Journal of Computer Theory & Engineering,Vol. 5, No. 2, pp. 242–247 (2013).

4.4

考察

図 3 によれば，基幹車両が増えるにつれて各種パケットが減少している．特に CH を推薦する ELECT パケッ
トは最大で 16.1packets から 7.369packets に 54.2% 減少
し，基幹車両がクラスタ形成にかかるパケットを減少さ[3] Sheu, J., Lo, C. and Hu, W.: A Distributed Routing
Protocol and Handover Schemes in Hybrid Vehicular
Ad Hoc Networks, Parallel and Distributed Systems(ICPADS), 2011 IEEE 17th International Conference on, pp. 428–435 (2011).