論文IEEE 802.11 MAC プロトコルを用いたマルチホップアドホックネット

ワークにおける時刻同期過程とその障害の解析
田中 久陽†

太田 大輔†

増形惣†長谷川 晃朗††デイビス ピーター††

Analysis of Timing Synchronization Process and Its Bottleneck in Multi-Hop Ad
Hoc Networks Using IEEE 802.11 MAC Protocol
Hisa-Aki TANAKA† , Daisuke OHTA† , Osamu MASUGATA† , Akio HASEGAWA†† ,and Peter DAVIS††
あらまし IEEE802.11 を用いたアドホックネットワークの基本的構成要素の一つとして時刻同期が知られている．従来，時刻同期の問題において一つの閉じたネットワークの定常状態が想定されてきた．これに対し，本研究は他のセルから一つのノードがネットワークに参入する動的な状態を想定して，その同期過程に対し系統的なシミュレーション解析を行う．その結果，ある同期障害がしばしば生じ，同期完了までに長時間が必要となることが指摘される．以上の解析の結果，その同期障害の発生要因は，ネットワークのサイズと通信可能範囲の兼合いにより固有のビーコン伝搬の空間パターンが生成するためであることが示される．またこの発生要因の理解を手掛りに，この同期障害を解消する糸口も与えられる．
キーワード

IEEE 802.11，アドホックネットワーク，時刻同期，同期障害，TSF

クネットワークとセンサネットは一つの活発なトピッ

1. ま え が きクとなっている（例えば [2]〜[9]）．

移動可能な端末からなり自律分散制御により端末間アドホックネットワークを構成する際に無線 LAN のの通信を行う通信ネットワークとして無線アドホック

標準規格である IEEE 802.11 のアドホックモードがよネットワークが注目されている．そこでは端末（以下く用いられている．この IEEE 802.11（以降，802.11

では，ノードと呼ぶ）の小型化に伴い電力消費の制約と略記する）のアドホックモードにおいて，アクセスが重要となっている．そのためノードを常に受信可能ポイント（AP）を必要としないノードの集団からなる（awake）状態にしておくのではなく，周期的にスリー

独立基本サービスセット（IBSS：independent basicプ（power save）状態にすることなどの工夫が行われる（例えば [1] の p.138, [2] を参照）．また従来の小数service set）が定義されている．一つの IBSS は他の
IBSS との融合や新しいノードの追加を可能としていのノードからなるアドホックネットワークから発展しるので，これらにより一つのアドホックネットワークて，最近では 70 ノードからなるアドホックネットワーの構成/維持が自律的に行われる．

クの屋外実験が行われ [3]，大規模，高密度のアドホッ

ところが上記のように，より大規模なアドホックネッ
トワークで自律分散通信を行おうとする際に様々な問†題が生じている．例えば，より大規模なネットワーク

電気通信大学電気通信学部電子工学科，調布市
The University

においては，必然的に複数のノードを経由する多段階

of Electro-Communications, 1–5–1 Chofugaoka, Chofu-shi,のマルチホップ通信が必要となり，そのためにメディ

Department of Electronic Engineering,
182–8585 Japan††（株）国際電気通信基礎技術研究所，京都府

アアクセス制御（MAC：media access control）[10]ATR Adaptive Communications Research Laboratories, 2–とルーチング制御の効率的な方法を検討する必要が2–2 Hikaridai, Seika-cho, Soraku-gun, Kyoto-fu, 619–0288

生じる．このメディアアクセス制御の問題の一つとし

Japan

228

電子情報通信学会論文誌 A Vol. J90–A

c （社）電子情報通信学会 2007
No. 3 pp. 228–239 

論文／時刻同期過程の空間的障害の解析て，時刻同期すなわち TSF（timing synchronization
function）によるノード間の時刻同期が知られている．
この TSF は例えば電源管理のタイミング同期等におなっていく傾向があり，より効率的な電源管理が必要いて必要であり，安定した通信を支える重要なネット

えば [13] 及びその文献を参照のこと）．以上を考慮しワークの構成要素の一つである．

て，本論文では各ノードが周期的に power save 状態となっている．そのために端末（ノード）の通信可能範囲を可能な限り制限することも検討されている（例802.11 を用いるアドホックネットワークにおいてになるもとで，各ノードの通信可能範囲を系統的に狭は，TSF によりノード同士が定期的にビーコンを送い場合から広い場合までを想定して，そこでの同期過信して，各ノードの時刻と IBSS の識別子などの情報

程を解析する．

を互いに参照し合う．その結果，時刻同期した一つの以下ではまず，2. で時刻同期の機構と問題設定，3.

ネットワークが維持/更新されている．ここで一つのでこれに対するシミュレーション及びその結果についノードに同時に複数のビーコンが到来する場合，ビーて述べ，4. で観測された同期過程について解析を行

コン同士が衝突（コリジョン）を生じるためいずれもう．最後に 5. で結論及び同期障害の解消方法につい受信されず，このとき時刻等の更新は行われない．まて検討を行う．

た電力消費の観点からも，特定のノードのビーコン送信が頻発することを避けることが望ましい．以上の理

2. 時刻同期の機構と問題設定

由により，802.11 においては互いに通信可能な複数の802.11 の時刻同期のプロセスは TSF により直接にノード間で競合（コンテンション）を行うことにより規定される部分と，電源管理やノードの配置等によりすべてのノードが公平なビーコン送信を行うよう意図

間接的に影響を受ける部分からなる．以下では，まずされている．

TSF の機構について述べ，更に問題設定として，ノー802.11 の TSF による時刻同期は以上のように自律分散的に達成される．したがって，どのような過程を経て全体の同期が達成され，また同期時にどれほどのドの電源管理と空間配置について説明する．

2. 1 802.11 アドホックモードにおける時刻同期の機構

精度の時刻同期が得られるかを明確にすることが必要

各ノードの TSF は 64 bit のカウンタ（一つのカウである．これらについて，従来研究として例えばシンンタは 1 [µs]）を管理しており，この値が各ノードのグルホップの場合として [2]，更にマルチホップの場合

時刻（すなわち，TSF タイマ）に相当する．基地局として [11] が知られている．以上の [2], [11] を含む時

モードの場合，基地局から周期的に送信されるビーコ

刻同期の研究においては，通常以下の 2 点が暗黙に仮ンに含まれる時刻情報に従い各ノードは時刻を更新す定されている．

る．これに対しアドホックモードにおいては，基地局（ 1 ） 対象とするネットワークは一つの固定されたが存在しないため，ノード同士でビーコンを送受信しIBSS であり，そこに他の IBSS から新たにノードがてそれぞれの時刻を更新していく必要が生じる．その参入することは考えない．

際，ビーコンをむやみに送信するオーバヘッドを避け（ 2 ） この閉じたネットワークにおいて，各ノードる工夫も必要となる．このために 802.11 アドホックのタイマにははじめからわずかな周期誤差はあるが，モードの TSF はノード同士で競合を行い，その結果その時間的揺らぎはなく全体として準定常的な状態とビーコンを送信するノードを選出する方法を採用してなっている．

いる．以上の機構は具体的には次の（ 1 ）〜（ 5 ）のよ

ところが実際にアドホックネットワークのおかれる

うに規定されている．

環境においては，例えば新たなノードの参入や複数の（ 1 ） 各ノードは周期的にある時刻で次のビーコン

IBSS の融合が生じる過渡状態は無視できない．このを送信するまでの待機時間（すなわち，バックオフタ

ような動的な環境下での時刻同期の性能を評価するイマ）を設定する．このバックオフタイマの初期値はことは，我々の知る限り，長谷川，デイビスによる指0 からコンテンションウインドウ（CW）の 2 倍の値

摘 [12] を除けば，これまで看過されてきたようである．

までの 2 · CW + 1 個の整数からランダムに選ばれる．

本論文の目的は上記のような動的な環境下での時刻（ 2 ） 各ノードは自身のバックオフタイマの値をカ

同期に対し，その同期過程を明らかにし，そこで生じ

ウントダウンしていき，これが 0 になった時点で，送る障害を解明することである．現在端末はより小さく

信範囲内にあるすべてのノードに向けてビーコンを送229

電子情報通信学会論文誌 2007/3 Vol. J90–A No. 3

信する．
（ 3 ） バックオフタイマ値が 0 になる前に他のノードからビーコンを受信すると，その時点で予定していたビーコン送信をキャンセルする．
（ 4 ） ビーコンが受信されると，ノードは自身のTSF タイマと受信したビーコン内の時刻情報（タイム
スタンプ）を比較し，受信したタイムスタンプの方が進んでいるときには自身のタイマを受信したビーコンのタイムスタンプの値に更新する．
（ 5 ） ビーコン送信を行ったノードのみ，その後次の awake 状態まで 1 ビーコン周期間 awake 状態を継続し，power save 状態にならない．他のビーコンを送信しないノードは，その後 power save 状態となり，

1 ビーコン周期の後再び awake 状態となる．ここで，
1 ビーコン周期とは awake 状態と power save 状態の一つのサイクルに相当し，例えば 100 [ms] の長さをもつ．

2. 2 問 題 設 定
最 も 簡 単 な 構 成 例 と し て ，図 1 の よ う に 縦 横

L [m]×L [m] の正方形領域内に多数のノードがランダムに配置されているケースを考える．ここでは十分広い空間を想定し，壁，天井等での電波の反射はないものとする．今，初期状態として各ノードは相互にTSF タイマを同期し全体の時刻同期が安定して得られているとする．ここで領域外部の他の隣接する IBSSからノード（図 1 (a) のノード D）が速やかに領域内のある位置に参入したとする．この参入の仕方として，
実際にノードが移動してくる場合，あるいは参入するノードのビーコン送信可能な範囲が時間的に変動した
ためにノードの位置は不変でありながら想定する領域
内に影響が及んでくる場合の両者が考えられる．ここでは，問題の本質を損なわないことを考慮して両者を同一視して扱う．

論文／時刻同期過程の空間的障害の解析

以上のノード A，B，C の awake/power save 状態のサイクルの位相を • で，ノード D のそれを ◦ で表示

は終了しないことが想像される（注 1）．
以上の再同期に必要となる時間は上位のレイヤからしている．

通常たかだか数秒に収まることが要求される．その（ 2 ） ノード A，B，C はそれぞれ awake 状態のもために上記のような最悪のケースを検討することは，とでビーコンの送信競合を行う．この例ではノード C

802.11 に基づいたマルチホップアドホックネットワー

が最小のバックオフタイマをもち，ビーコンを送信す

クを構築する際に時刻同期からくる制約条件を明らかる．他のノード A，B はこれを受信し，それぞれのにすることになる．この目的から，以下では参入してビーコン送信予定をキャンセルする．またノード C かくるノードの awake/power save サイクルの位相は他

らのビーコンはノード D にも送信されるが，この例でのノードのそれに対し逆相（180 度の位相差）と設定すはノード D は power save 状態であるため受信されなる（図 2 のノード A，B とノード D の awake/power

い．以上のようにビーコン送信を行ったノード C は前save サイクルを参照のこと）．そのもとで系統的に領述の TSF の定義に従い，次の awake 状態まで本来予域内のノード数と各ノードのビーコン送信可能半径定される power save 状態（図 2 のノード C の点線部

（R）を変化して，それぞれの場合においてどのような分に対応）にならず awake 状態を継続しようとする．

過程で同期に至り，またこれにどれほど時間を要する（ 3 ） 次に，ノード D が awake 状態となりビーコ

かをシミュレーションにより解析する．

ン送信を行う．このときノード D のビーコン送信可能範囲内においてノード C は awake 状態であるので，ビーコンを受信する．受信した結果，ノード C

3. 時刻同期過程のシミュレーションとその結果

はノード D の時刻に同期し，本来 1 ビーコン周期のここではノード配置例として図 3 (a)，(b)，(c)，(d)間 awake 状態を継続する予定をキャンセルし（図 2の 4 通りの場合を対象とする．図 3 (a) は図 1 (a) と同じのノード C の破線部分に対応）ノード D に同期した

く縦横 L [m]×L [m] の正方形領域内に一様乱数に従っawake/power save 状態のサイクルを開始する．またてランダムにノードを配置した場合である．図 3 (b)，ノード D はビーコン送信を行ったので，その後 1 ビー(c) はノードの存在密度がほぼ均一の一様分布に近い場
合であり，それぞれノード間距離を (エリア面積/ノーコン周期の間 awake 状態を継続している．
以上の過程（ 1 ），（ 2 ），（ 3 ）を経て，1 ビーコン周期ド数)1/2 × 0.2，(エリア面積/ノード数)1/2 × 0.8 以上の間にノード D の近傍でノード C が時刻の更新を完とする条件下でランダムに配置している（このよう了する（図 1 (b)）．次のビーコン周期において，ノーな配置方法については [8] を参照のこと）．図 3 (d) は

ド D の近傍（ビーコン送信可能範囲）に加えノード

図 3 (b)，(c) の場合の理想化であり，一様分布のアレー

C の近傍においても上記の過程が繰り返され，徐々に状配置であり，(エリア面積/ノード数)1/2 × 1.0 の等間

時刻の更新が領域内ノードに伝搬することになる．以隔で配置している．ここでエリア面積はいずれの場合

上の説明から明らかに，この再同期の過程の遅速はも L2 であり，これに対しノード数 N を一定と設定す参入したノードのもつ時刻，すなわち，awake/power

る．これにより以上のいずれの場合も空間平均したノー

save 状態のタイミングに依存する．もし参入したノードの awake/power save 状態のタイミングが領域内

ド存在密度は等しくなる．以下のシミュレーションでのノードのそれに十分近ければ，参入したノードのつき，それぞれ N = 62 , 72 , 82 , 92 , 102 , 112 , 122 と設awake/power save 状態は領域内のノードのそれに近定する．すなわち，密度をほぼ一定（∼0.025 [1/m2 ]）は L = 100, 120, 140, 160, 180, 200, 220 [m] の場合にくなり，同時に awake 状態となる時間が存在する．このような場合には，参入したノードの近傍で複数のノードに再同期が進行し，短時間で全体の再同期が完了することが期待される．ところが，図 2 で示した例のように，参入したノードの awake/power save 状態のタイミングが領域内のノードのそれと異なり，互いに awake 状態となる時間をもたない場合には，再同期の過程は上で説明したとおり徐々に進行し，短時間で（注 1）：一つの IBSS 内では ATIM（announcement traﬃc indication message）ウィンドウの期間内に power save 状態のノードを含む
すべてのノードを awake 状態にすることが可能である（ [11]，p.130）．
この ATIM ウィンドウを十分長く設定（最大 1 ビーコン周期）すれば，
上記のような問題は回避されると考えられる．ところが ATIM ウィン
ドウを十分長く設定するということは，ネットワークの運用上，データを送ることができる時間が著しく制限されてしまうため困難である．また，これは常時すべてのノードが高い頻度で awake 状態となることであり冒頭で述べたように電力消費の制約の観点からも現実的とはいえな
い．

231電子情報通信学会論文誌 2007/3 Vol. J90–A No. 3
表 1 シミュレーションパラメータの設定
Table 1 Speciﬁcations of simulation parameters.

(a) Random(b) Randomized Uniform

シミュレーション 1 シミュレーション 2
Parameter
Value
Value
Channel Rate
1 Mbit/s
1 Mbit/s
Data
550 bit
550 bitCW
15
15
Slot Time
50µs
50µs
Beacon Period
100 ms
100 msTransmission Delay 0µs
1µs, 50µs, 100µs
Clock Accuracy±0%±0.01%の時刻同期のタイムスケールに比べ十分ゆっくりとした移動については第一近似として妥当であると考えられる．すなわち，まずノードの移動を無視できる単純(c) Randomized Uniform(c) Uniform

図 3 ノード配置例
Fig. 3 Examples of node positioning.

な場合を想定し，そこでの時刻同期の過程の本質を明確にすることを当初の目標とする．また同様に，このシミュレーションにおいて，まず次の三つの簡略化を行った．

としてシステムサイズを増加している．
シミュレーションの目的はこれらの場合の結果を比（ 1 ） ノードの通信可能範囲はすべてのノードで一様であり，IBSS 内で時間変化しないとする．したがっ較することにより，システムサイズ（すなわちネットてリンク特性は対称かつ定常的である．

ワークのマルチホップ性）あるいはノード配置が同期（ 2 ） ビーコンの送受信における遅延は 1 ビーコン過程の詳細及び同期に要する時間にどのような影響をスロット長（今の場合 50 [µs]）に比べ十分小さく，0与えるかを明らかにすることである．

と近似できる．

シミュレーションの初期条件として，上記のいずれ（ 3 ） ノードの TSF タイマは時間的に一定の周期の場合も参入する一つのノードを除くすべてのノードをもち，すべてのノードで同一の周期をもつとする．

は時刻同期していて，したがって awake/power save

以上のシミュレーション（これをシミュレーション

サイクルの位相も同期しているとする．これに対し新1 とする）に対し，上記の簡略化（ 2 ），（ 3 ）が成立たに参入するノードのみ他のノードより進んだ時刻をしない場合のシミュレーションも別に行う（これをシもち，これに対応する awake/power save サイクルのミュレーション 2 とする）．これら両者の結果の比較

位相は他のノードのそれに対し逆相と設定する．またを行い，シミュレーションの詳細に依存する部分と依参入するノードの位置は図 3 (a)，(b)，(c) の場合，領存しない部分を明確にする．以上のシミュレーション

域内のノードの一つをランダムに選び，そのノードが1 及びシミュレーション 2 に用いたパラメータは表 1参入したノードに相当するものとする．図 3 (d) のアのとおりである．

レー状の場合は以下で行う解析のためにその位置を領
域の右端の特定の位置にあらかじめ固定した．

以上のシミュレーションは C 言語によるプログラムを自作し行った．これらのプログラムは下記の URL [15]シミュレーションの終了条件は，各試行ごとに初期で公開されている．なお，理論値の得られている場合の二つの IBSS が一つに融合し，すべてのノードの時の種々のケースで理論値とシミュレーション結果の比刻が一つに同期した時点とした．以下ではこのすべて較を行いプログラムの信頼性を確認をしており，そののノードの時刻同期が完了した状態を完全同期と呼び，範囲で問題は認められない．

完全同期を達成するまでに要した時間を再同期時間と呼ぶことにする．

3. 1 同期時間の通信範囲依存性
以上に述べた設定のもとで領域の大きさ L を固定

またシミュレーションではすべてのノードは移動しし，ノードの通信可能範囲 R を狭い場合から広い場ないと設定した．この設定は車々間通信等の高速移動

合までのそれぞれの場合に対し 10000 回シミュレー

ノードの場合には制約となるが，たかだか数秒オーダ

ションを行った．その結果，完全同期までに要した時

232

論文／時刻同期過程の空間的障害の解析(a) L = 100 [m] の場合（36 ノード）(b) L = 160 [m] の場合（81 ノード）(c) L = 220 [m] の場合（144 ノード）(d) L = 100, 160, 220 [m] の場合の比較(e) 参入するノードの位置に関する比較
Fig. 4図 4 平均再同期時間の通信可能範囲依存性
Dependency of averaged resynchronization times to transmission ranges.

間の平均値（平均再同期時間）を図 4 (a)，(b)，(c)，1，2 は図 3 (b)，(c) のノード配置にそれぞれ対応している．図 4 (d) のデータはいずれも上記の uniform
1 の場合に対して得られたものである．

(d) に示す．なお，シミュレーションは上記の 7 通りの L に対し行っているが，紙面の制約のため，ここでは L = 100，160，220 [m] の場合のみを示す．このほ
かの L の場合も同様の傾向を示している．

シングルホップであり，かつビーコンのコリジョンが

図 4 (a)，(b)，(c) はそれぞれ L = 100，160，220 [m]生じない極限を想定し，その場合の同期時間のラフなの場合を示し，図 4 (d) はこれらの比較のため，グラフ

見積りを図 4 (a)，(b)，(c) のそれぞれに点線で与えのスケールを調整して重ねて表示したものである．こた．この見積りは，以上の設定において 1 ビーコン周のスケールの設定は，横軸を R/L として正規化し，縦期の間に平均して一つのノードが同期されていくため

軸を各データの右端での一定値（図 4 (a)，(b)，(c) 内に，すべてのノードの同期が完了するまでに，総ノーまた各データの比較の対象として，ネットワークがに記載）を 1 となるように正規化している．図 4 (a)，ド数 × 1 ビーコン周期（100 [ms]）の時間が必要とな(b)，(c) のデータにおいて array は図 3 (d) に，random 1，2，3 は図 3 (a) の異なる 3 パターン，uniformることから得られる．
これらのシミュレーション結果には共通して次の三233

電子情報通信学会論文誌 2007/3 Vol. J90–A No. 3

つの特徴が認められる．
（ 1 ） 図 4 (d) において，いずれのノードの配置においても R/L = 0.5 ∼ 1.0 の範囲内において平均再同
期時間は最大となる．これより大きい R(∼

√

2L) に

おいてはネットワークはシングルホップとなり，平均
再同期時間は R に依存せず一定値をとる．
（ 2 ） 一様乱数に従ってノードを配置した場合とそ
れ以外のほぼ一様な密度での分布の場合を比較すると，前者の方が最大値をとる R の値が幾分小さくなる．

(a) 送受信遅延 1 [µs] の場合（ 3 ） 別にシミュレーションを行い，新たに参入するノードの位置を右端に固定した場合とランダムに毎回更新する場合の比較を行ったが，いずれの場合においても後者のランダム更新の場合にわずかに平均再同期時間が長くなるのみであり，有意な差は生じない．
この特徴は以上で得られたすべてのデータに対し成立するが，ここでは紙面の制約のため，典型例として
図 4 (e) の一例のみを示す．

3. 2 周期分布及び遅延の影響
次に，ノードごとの TSF タイマの周期分布とビー(b) 送受信遅延 50 [µs] の場合

コンの送受信における遅延の影響を検討する．TSF タ
イマの周期分布については ±0.01% の範囲で一様乱数
に従い分布するとした（この設定例としては，[2], [11]参照）．またビーコンの送受信遅延についてはビーコンの伝搬遅延とノードの送受信に要する処理時間をまとめて扱い，ノードによらず一定であるとした．ここでは 1 [µs]，50 [µs]，100 [µs] の 3 通りを想定する．3.1のシミュレーションと同様の条件でシミュレーションを行った結果，これらの 3 通りの場合に対し得られる(c) 送受信遅延 100 [µs] の場合

平均再同期時間の通信可能半径への依存性をそれぞれ
図 5 (a)，(b)，(c) に示す．これらは上記の uniform 1の場合に対して得られたものであり，スケールの設定
も図 4 (d) のそれと同様に行った．これらのデータは上記のシミュレーション 1 に対して得られた定性的な図 5 平均再同期時間の通信可能範囲依存性（送信遅延を考慮した場合）Fig. 5 Dependency of averaged resynchronization
times to transmission ranges in the presenceof transmission delays.

特徴（ 1 ）がここでも成立することを示している．また同様に，特徴（ 2 ），（ 3 ）も成立することも確認されコンコリジョンの頻度が低くなるためであることが詳るが，そのデータは紙面の制約から割愛する．

細な解析から判明している．紙面の制約から，その詳上記の定性的側面に対し，以下では定量的側面について簡単に説明する．以上の図 5 (a)，(b)，(c) のデー
タ（遅延等が存在する場合）とこれに対応する図 4 (d)細については [14] の pp.47–54 に譲る．

4. 同期過程の解析（遅延等の存在しない理想状態）を比較すると，両者

以上二つのシミュレーションの結果から，平均再同の間には有意な値の差が生じていることが分かる．こ期時間が増大するボトルネックを生じる要因は，通信の差が生じる主な要因の一つとして，遅延とタイマ周

可能半径 R とネットワークのサイズ L の比によると期誤差が存在する場合は，遅延がそれほど大きくない

ころが大きく，以上で想定したノード配置の差や参入場合これらの存在しない理想状態と比べて，実質ビーするノードの位置，更に比較的小さい遅延にはあまり

234

論文／時刻同期過程の空間的障害の解析影響を受けないことが分かる．そこで以下では通信可解される．このとき R は想定している領域の対角線

能半径をパラメータとして平均再同期時間が決定されの長さであるるメカニズムを明らかにするため解析を行う．

てのノードが他のすべてのノードと直接通信可能で全√

2L より大きいゆえに，領域内のすべ

4. 1 同期過程の通信可能範囲依存性体が一つのシングルホップネットワークとなっている．

以上のシミュレーションにおいて平均再同期時間にそのために再同期時間が通信可能半径に依存せず一定

関して次の三つの特徴が認められる（図 6 参照）．

値となる．

（ 1 ） 通信可能半径 R が小さい場合（0.2 < R/L <これに比べ，特徴（ 1 ），（ 3 ）はそれぞれビーコン

0.4）にはネットワークのマルチホップ性が高いにもかの送受信が領域内でいかに伝搬していくかという空間

かわらず，平均再同期時間が最小となる．

パターンの問題に帰着する．これらの空間パターンは√（ 2 ） 一方，通信可能半 径が大きい場合（ 2 <上記のシミュレーション 1，2 の両者いずれにおいてR/L）には平均再同期時間は R に依存せず一定値をも認められ，これらを模式的に表したものがそれぞれとる．

図 6 (a)，(b) である．この図において矢印（⇐）は時（ 3 ） 以上の二つの場合の中間領域で，ネットワー

刻の同期が徐々に伝搬していく方向を示している．こクはマルチホップであるが通信可能半径もある程度大れらのパターンに対しそれぞれシミュレーション 1 できい場合（0.5 < R/L < 1.0）において，平均再同期

ノード数 36 の場合に得られる時刻同期の経過の様子

時間は最大となり，この例では最大値が約 5 [s] となる．

を図 8 (a)，(b) に示す．ここで得られた結果をまとめ

また，以上の特徴（ 1 ），（ 2 ），（ 3 ）のそれぞれのR/L の範囲での再同期時間の分布の様子を表示したものが図 7 であるが，特徴（ 1 ），（ 2 ）のケース（それぞれ R = 40, 140 [m] のデータに対応）に比べ特徴

ると，（i） 図 8 (a) のように通信可能範囲が狭い場合には時刻同期は参入したノードの周りから放射状に進展し，比較的短時間で終了する．

（ 3 ）のケース（R = 80 [m] のデータに対応）では分
布の幅は有意に広くなり，この場合には再同期時間の最大例は約 9 [s] にもなることが認められる．
これらの特徴のうち，特徴（ 2 ）の理由は容易に理

図 6 平均再同期時間とビーコン伝搬パターンの通信可能
範囲依存性
Fig. 6 Dependency of averaged resynchronization
times and beacon propagation patterns to thetransmission range.

Fig. 7図 7 再同期時間の分布
Distribution of resynchronization time.

Fig. 8図 8 同期過程の例
Examples of synchronization process.

235

電子情報通信学会論文誌 2007/3 Vol. J90–A No. 3（ii） 一方，図 8 (b) のように通信可能範囲がある

以上の事実から，4.1 の特徴（ 1 ），（ 3 ）における異程度の広さをもつ場合には参入したノードから出発しなる同期過程が生じる理由が次のように説明される．

て領域の端を巻き込むような方向に時刻同期が進展し，（i）各ノードの通信可能範囲内に存在する他のノード

領域の中央部のノードにはなかなか同期が及ばないこの数（すなわち，局所的なノードの存在密度）は上記とが判明した．

のように必ずしも領域内で均一ではなく，その空間的

4. 2 ノードの空間分布密度の影響

な不均一性が最も強く現れるのは上記の特徴（ 3 ）に

（ 3 ）においては以上の解析から，4.1 の特徴（ 1 ），

対応する通信可能範囲の場合である．一方，その局所それぞれ固有の時刻更新の空間パターンが対応してい的なノードの存在密度は上記の特徴（ 1 ）に対応する

ることが分かった．問題は，どのようにしてこれらの狭い通信可能範囲の場合には領域内の端で幾分不均空間パターンが生成され，これがいかに平均再同期時

一となるにすぎず，全体として不均一性は最も小さく間を決定するかというメカニズムの解明に帰着する．

なっている．
（ii）したがって，特徴（ 3 ）に対応する通このメカニズムを説明するかぎとなるのは 802.11 の信可能範囲の場合において領域の中央部と端でのビー

ビーコン送信競合の仕方である．2.1 に述べたように，

コン送信の機会は最もその差が大きくなる（図 10 (a)802.11 のビーコン送信競合はノードごとにランダム参照）．すなわち，中央部では競合の結果ビーコンをに割り当てられたバックオフタイマ値の大小により互送信して awake 状態を維持するノードの割合は低く

いに通信可能なノード間で決定されるものである．こなり，逆に端ではその割合は相対的に高くなる．

の競合において，領域内で各ノードの通信可能範囲内

今，時刻同期の過程は awake 状態にあるノードを介に存在する他のノードの数が場所によらず一様である

して進展するので，以上の理由（i），（ii）から，4.1 のならば，すべてのノードは場所によらず公平なビーコ

特徴（ 3 ）における領域の端で巻き込むように進展す

ン送信を行うはずである．ところが現実には，ノード

る同期パターンが生じることが説明される．一方，狭が配置される領域は有限であり端が存在する．その端い通信可能範囲の場合，領域内でビーコンを送信しての近くに置かれるノードと領域の中心部分に置かれる
ノードに対し，例えば 4.1 の（ 3 ）のように通信可能範囲が領域全体をカバーできるほどには広くない場合を考えよう．このとき明らかに端のノードの周りでは中央部のノードの周りに比べノードの数はより少なくなる（図 9 (a) 参照）．すなわち端のノードのビーコン
送信はより少数のノード間の競合により行われ，一方，中心部のノードのそれは多数のノードの競合により行われている（図 9 (b) 参照）．
(a) 特徴（ 3 ）に対応する通信可能範囲の場合(a) 端部のノードと通信可能範囲(b) 中央部のノードと通信可能範囲図 9 端部のノードと中央部のノードの通信可能範囲の比較
Fig. 9 A comparison between transmission ranges ofa node on the edges and a node in the centerof the network.

236(b) 狭い通信可能範囲の場合

図 10 ノードごとのビーコン送信頻度の例
Fig. 10 An example of beacon transmission
frequency for each node.

論文／時刻同期過程の空間的障害の解析ことにある．そこで上記の同期障害を解消する方法として，802.11 の MAC プロトコルの修正により公平なビーコン送信を保証することが考えられる．その一つの案として，特定のノードにビーコン送信が集中しないようにする方法を検討した．まず，図 10 (a) のようなケースで特定のノードにビーコン送信が集中している際に，そのノードがどのようなバックオフタイマ値
においてビーコンを送信しているかを調べた．その結果，領域の端のノードは相当に大きなバックオフタイ
マ値であってもビーコン送信を行っており，一方領域
中央部のノードはビーコン送信競合が激しいためビー
コン送信を行っているときは必ず小さなバックオフタ
イマ値が与えられている場合であることが認められた．
図 11 同期過程の終盤におけるビーコンコリジョンの様子
Fig. 11

Beacon collisions before timing
synchronization is completed.

したがって自然な発想として，802.11MAC プロトコ
ルのビーコン送信基準の従来の競合のメカニズムに加えて，ビーコン送信に際して，そのノードのバックオ
フタイマ値がある基準値より小さい場合のみビーコ

awake 状態を維持するノードの割合はほぼ均一であり（図 10 (b) 参照），このために参入したノードの周り

ン送信を行ういわば「足切り」の条件を付加すること

から放射状に同期が進展する．図 10 のヒストグラム

ションに付加して性能を評価したところ，特にノードは 36 ノードのアレーにおいて長時間平均により得ら数が多い場合に平均再同期時間が大幅に短縮されるこれた．他のノード配置においても以上と同様の傾向がとが確認された [16]．以上の手法の詳細，改良等につ認められる．

いては別に報告の予定である．

また，特徴（ 3 ）に対応する通信可能範囲の場合においては同期過程の終盤において複数のビーコンのコが考えられる．この修正案を以上で行ったシミュレー

5. む す び

リジョンが頻繁に生じることが認められる．図 11 は

本論文は，一つの IBSS に隣接する他の IBSS から

この状況の典型的な例である．ここで見られるように，ノードが参入して再び全体の同期が完了するまでの過端部のノードで既に同期が完了した後に，領域の四隅程に注目し，そこでの空間的同期障害の生成機構を明のノードを中心としてビーコンの送信が頻繁に行われらかにした．802.11 の TSF のメカニズムは本来ノーる．これらのノードは同期しており，かつ互いにそのドごとにビーコン送信を公平に行うことを意図してい通信可能範囲の外にある．したがって独立してビーコるが，これがネットワークのマルチホップ性のために必ン送信を行うためにビーコンのコリジョンが生じやす

ずしも保証されず，結果として時刻更新の空間パター

くなっている．ビーコンのコリジョンが生じると，そンの生成とビーコンコリジョンの頻発が生じることがの時点で同期は進行しないので，同期が完了するまで明らかとなった．またこの同期障害の生成機構の理解に平均して長時間が必要となるのである．このコリから，同期障害を回避する改良案の手掛りが得られた．

ジョンのパターンは初期に参入したノードの位置と無この同期障害の生じるメカニズムは，ネットワークの関係に生じることが認められ，したがって上記の特徴

サイズと通信可能範囲の大きさの兼合いにより生じる（ 3 ）が成立する根拠を与えていることがいえる．

という一般的な性質をもつ．したがってビーコンによ4. 3 同期障害の解消方法の検討

る時刻同期のみならず power save コントロールのも以上の解析から，マルチホップのアドホックネットとでフラッディング等の問題を考える際にもその基礎ワークにおいて 802.11 の MAC プロトコルを用いたとなることが期待される．

場合，空間的な同期障害が生じる可能性が理解されよ

本論文のシミュレーションに関する今後の課題としう．この障害の本質は図 10 (a) に示されるようにノーて，（ 1 ）ここで仮定した対称なリンク特性が非対称とドごとに公平なビーコン送信が必ずしも保証されないなる際の効果，（ 2 ）ノードごとの通信可能範囲の時間
237電子情報通信学会論文誌 2007/3 Vol. J90–A No. 3

変動，移動の効果が挙げられる．また（ 3 ）本研究は一つの IBSS に他の IBSS から一つのノードが参入す

881, March 2005.
[10]

る場合を対象としたが，より一般には複数の IBSS のhttp://standards.ieee.org/getieee802/download/802.

グループ移動（group mobility）（例として [17] 及びその文献を参照）として扱う必要性も考えられる．こ11-1999.pdf[11]J-P. Sheu, C-M. Chao, and C-W. Sun, “A clock synchronization algorithm for multi-hop wireless ad hoc

こでは時刻同期の過程に注目したが，同様の設定におnetworks,” Proc. 24th International Conference on

いてフラッディングを行う際の動特性も重要な課題とDistributed Computing Systems, Japan, pp.574–581,

考えられる．

2004.

本論文のシミュレーションに対応する実機による実[12]とするために，現状では相当に労力が必要と考えられ[13]

るが，最近のテストベッドの構築 [18] により今後実験

学ソ大（通信），B-5-37, Sept. 2004.
蓮池和夫，ソンプラカシュ バンディオパダイ，植田哲郎，“アドホックネットワークの技術的課題，” 信学論（B），vol.

検証が容易となることが期待される．
貴重な御助言を頂きました電通大 AWCC の

A. Hasegawa and P. Davis, “Long coalescencs times
for ad hoc cells using 802.11 MAC protocol,” 2004 信

験を行うことは，コントロールされた環境設定を必要

謝辞IEEE Std. 802.11 Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) speciﬁcation,[14]

J85-B, no.12, pp.2007–2014, Dec. 2002.
太田大輔，IEEE 802.11 MAC プロトコルによるマルチ

ホップネットワークの時刻同期に関する基礎研究，平成 17年度修士論文，電気通信大学電子工学専攻，2006.

藤井威生助教授，並びに御議論を頂きました東大 島田尚氏に感謝します．本研究の一部は平成 18 年度文科[15]

http://synchro3.ee.uec.ac.jp/download/IEICE06a/

省科研費補助金（課題番号 18560370）を受けて行わ[16]

田中久陽，太田大輔，長谷川晃朗，デイビス ピーター，“IEEE802.11 MAC プロトコルによるマルチホップネッ

れた．
文
[1]

トワークのタイミング同期（ 3 ）〜空間的同期障害の解消方法の提案，” 2006 信学総大，B-21-29, March 2006.

献

小牧省三，間瀬憲一，松江英明，守倉正博，無線 LAN と[17]

mobility to data replication in ad hoc networks,”

ユビキタスネットワーク，丸善，2004.
[2]

national Symposium on Mobile Ad Hoc Networking
and Computing, pp.173–182, Lausanne, Switzerland,
2002.
[3]

[4]

IEEE Trans. Mobile Computing, vol.5, no.5, pp.492–

L. Huang and T -H. Lai, “On the scalability of IEEE
802.11 ad hoc networks,” Proc. third ACM Inter-

八木啓之，“アドホックネットワーク・テストベッド共同
実験速報，” アドホックネットワーク・コンソーシアム第 2J -L. Huang and M -S. Chen, “On the eﬀect of group[18]

507, May 2006.
三觜 輝，岡田辰博，萬代雅希，渡辺 尚，“無線通信
MAC プロトコルのテストベッドについて，” 2006 信学総大，B-21-28, March 2006.
（平成 18 年 5 月 11 日受付，9 月 4 日再受付，
11 月 7 日最終原稿受付）

回シンポジウム，2005.
間瀬憲一，佐藤 正，“ブルートゥースを用いたアドホッ
クネットワークにおける自律分散スキャッタネットオペ
レーションプロトコル，” 信学論（B），vol.J85-B, no.12,
pp.2015–2024, Dec. 2002.

[5]

牛島準一，沖野正宗，加藤聰彦，伊藤秀一，“階層的な高密度センサーネットワークのための中継用ランドマークの評価，” 2005 信学ソ大（通信），B-21-36, Sept. 2005.

[6]

[7]

田村陽介，“Ameba：大規模アドホックネットワークにおける効率的なアドレス割当て方式，” 情処学論，vol.45,
no.5, pp.1376–1387, May 2004.
小野良司，撫中達司，渡辺 尚，“アドホックルーチングプ

ロトコルの制御メッセージによる無線 LAN リンクスルー
プットへの影響の分析，” 信学論（A），vol.88-A, no.12,
pp.1422–1431, Dec. 2005.
[8]

小川将克，服部 武，加山英俊，梅 田成視，“アドホックネットワークにおける動的な移動端末の状態変化を用いた MAC プロトコル，” 信学論（B），vol.88-B, no.3,
pp.643–655, March 2005.

[9]

N. Wakamiya and M. Murata, “Synchronizationbased data gathering scheme for sensor networks,”
IEICE Trans. Commun., vol.E88-B, no.3, pp.873–

238

田中

久陽 （正員）1995 早大大学院博士課程了．工博．同年より，日本学術振興会特別研究員（PD）．
1996 カリフォルニア大バークレー校客員研究員．1997 よりソニーコンピューター
サイエンス研究所研究員．2001 電気通信
大学電気通信学部電子工学科助教授．通信システム，数理生物学，非線形物理等の横断的分野の研究に従事．日本物理学会，IEEE 各会員．

論文／時刻同期過程の空間的障害の解析

太田大輔

2004 電通大・電気通信・電子卒．2006
同大大学院修士課程了．同年，NEC（株）

入社，現在に至る．非線形物理，複雑系科学に興味をもつ．在学中はアドホックネッ
トワークにおける時刻同期の研究に従事．

増形

惣2006 電通大・電気通信・電子卒．現在
同大大学院情報システム学研究科情報シス

テム設計学専攻在学中．アドホックネット
ワークのシミュレーションと実験に従事．

長谷川晃朗
平 7 明大・理工・電子通信卒．平 9 同大
大学院博士前期課程了．平 12 同大学院博士後期課程了（工博）．平 12 岐阜大学工学
部電気電子工学科助手．平 14（独）通信総合研究所（現（独）情報通信研究機構）専攻研究員．電子回路に発生するカオス現象
や同期現象，カオスの応用に関する研究に従事．平 16（株）国際電気通信基礎技術研究所適応コミュニケーション研究所研究員．アドホックネットワークに関する研究に従事．

デイビス

ピーター

昭 55 クィーンズランド大・物理卒（FirstClass Honours）．昭 56 京都大学理学部文部省留学研究員，昭 62 クィーンズランド大．同年（株）
学大学院博士課程了（Ph.D.）
国際電気通信基礎技術研究所光電波通信研究所研究員．平 8 同環境適応研究所研究員，カオス現象を利用した通信に関する研究に従事．平 13 同
適応コミュニケーション研究所主任研究員，自律ネットワーク
システムに関する研究に従事．AIP，IEEE 各会員．

239