DEIM Forum 2013 F1-4

DTN ブロードキャストにおける配布遅延削減のためのメッセージ送信順スケジューリング手法に関する一考察
澤村 雄介†

寺西 裕一††,†††

春本

要††††

西尾章治郎†† 大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘 1-5†† 大阪大学サイバーメディアセンター 〒 567-0047 大阪府茨木市美穂ヶ丘 5-1††† 独立行政法人情報通信研究機構 〒 184-8795 東京都小金井市貫井北町 4-2-1†††† 大阪大学大学院大学院工学研究科 〒 565-0871 大阪府吹田市山田丘 2-1
E-mail: †{sawamura.yusuke,nishio}@ist.osaka-u.ac.jp, ††teranisi@cmc.osaka-u.ac.jp,†††harumoto@eng.osaka-u.ac.jp
あらまし

本研究では，低密度に移動無線端末が存在する環境下でも高い到達率を維持可能な DTN におけるブロードキャスト配信 (DTN ブロードキャスト) において配布速度を向上させるための手法を提案する．DTN ブロードキャ
ストでは，端末間の通信で利用できる帯域が限られているとき，メッセージの流量が大きくなると，配信遅延が極端に大きなメッセージが発生してしまう問題がある．本稿では，各ノードが各メッセージのネットワーク全体での配布率を自律的に推定し，配布が遅いメッセージを優先的に送信することで，配布遅延が大きなメッセージの発生を抑止し，全体の配布速度を向上させる手法を提案する．シミュレーションにより，提案手法は従来方法と比べ，最悪遅延を 20%以上削減できることを確認した．
キーワード

DTN，ブロードキャスト，スケジューリング

Study of the message forwarding order scheduling methods for delivery
delay reduction of broadcast in Delay Tolerant Network
Yusuke SAWAMURA† , Yuichi TERANISHI††,††† , Kaname HARUMOTO†††† , and Shojiro
NISHIO†† Graduate School of Information Science and Technology, Osaka University
1-5 Yamada, Suita, Osaka 565-871 Japan†† Cybermedia Center, Osaka University
Mihogaoka 5―1, Suita-shi, Osaka 567―0047 Japan††† National Institute of Information and Communication Technology
4-2-1 Nukuikitamati, Koganei, Tokyo 184-8795 Japan†††† Graduate School of Engineering, Osaka University, Osaka University
2-1 Yamada, Suita, Osaka 565-0871 Japan
E-mail: †{sawamura.yusuke,nishio}@ist.osaka-u.ac.jp, ††teranisi@cmc.osaka-u.ac.jp,†††harumoto@eng.osaka-u.ac.jp

1. は じ め にことへの関心が高まっている．このような通信基盤を実現するために，モバイルアドホックネットワーク (MANET) に関す

近年，スマートフォン，タブレット PC などの移動無線端末

る研究が多く行われている．MANET では，ノードが自身の（ノード）と，Bluetooth や WiFi などの近距離無線技術の普無線通信範囲内に存在するノードと通信する場合，固定の基地及により，ノード間を無線技術で結びつけ通信基盤を構築する

局を介さずに直接通信する．自身の無線通信範囲内に存在しないノードと通信する場合，それらのノードの間に存在するノー増加する．その場合，ノードは送信するメッセージを選択する

ドがメッセージを中継する．MANET は，自律分散的にネット必要がある．しかし，従来のブロードキャスト手法では，単純ワークを構築できるため，災害時など固定の通信基盤を利用でなスケジューリングや消費電力を多く利用するスケジューリ

きない状況への応用が期待されている．

ングが採用されており効率的ではない．文献 [7], [3], [11] では，

MANET では，ノードが密に存在する環境においては，メッネットワーク中で早く発信されたメッセージほど優先して送信

セージの到達率は高いが，ノードが疎になるにつれ，到達率はされる．しかし，発信された早さのみで優先順を決定すると，低下する．したがって，ノードが疎に分布する環境においては，待っているノード数が多い確率が高い後発のメッセージが優先

自律的なネットワーク構築が困難となる問題がある．MANET

されないため待ち時間が増加する．また，配布率を考慮していにおいて，ノードの疎密が存在する環境であっても，メッセージ

ないため，一部のメッセージが状況により遅れた場合に，アプの到達率を保つために，蓄積運搬型転送に基づいてメッセージ

リケーションが要求する期限内に配布できないという問題があ転送を行う技術が提案されてきた．蓄積運搬型転送では，ノーる．文献 [8] で提案されている位置情報を利用してスケジュー

ドは伝搬すべきメッセージを自身のバッファに蓄積し，他ノーリングする手法では，位置情報を利用するため，スケジューリ

ドと通信可能になった時点で，メッセージを伝搬する．蓄積運搬

ング毎に電力が消費されてしまい，携帯電話などの電力に限り型転送に基づいた情報伝搬技術は遅延耐性ネットワーク (DTN:がある端末上での利用に不適である．

Delay Tolerant Network) 技術と呼ばれている．

そこで，本研究では位置情報を利用せずに，アプリケーショ

本研究では，特に，DTN におけるブロードキャストを取り上ンが要求する期限内にできるだけ多くのメッセージを配信し，げる．ブロードキャストは，あらゆるネットワーク機能の基本

各ノードへの配布遅延のばらつきを抑えるような手法を提案すとなる機能である．ブロードキャストは，配信元から発せられる．具体的には，各メッセージをネットワーク中での配布速度

たメッセージをネットワーク上のすべての他のノードへ配信すの小さい順に送信することで各ノードへメッセージの配布遅延るという単純な動作を実現する．ブロードキャストは，様々なとばらつきを削減しつつ，期限内に配布できるメッセージ数をアプリケーションから利用されることが想定されるため，ノー向上させる．

ドへメッセージを配信する際に，早く配信するという要求と多くのノードへ配信するという要求の双方を満たす必要がある．

2. 問 題 定 義

しかし，DTN 環境では，ノード間の通信帯域量が著しく少ない

ブロードキャストでは，各ノードへの平均的な配布遅延，最上に，ノードがあるノードとの接触を終了してから，次の接触

悪の場合の配布遅延，及び配布が 100%に到達することが保証が開始されるまでの時間が長いため，メッセージの発信タイミ

されていなければならない．以下では，ブロードキャストが満

ングやノードのメッセージ送信順の決定の仕方によって，メッ

たすべき要件について説明する．ネットワークに参加している

セージの配信速度には偏りが生じる．そのため，アプリケー

ノードの集合を N とする．ノードは自律的に移動する．ネット

ションに対して配布速度が安定したブロードキャスト機能を提ワークで発信されたメッセージ集合を M とする．メッセージ

供することは困難である．

m ∈ M がノード n ∈ N に配信されるまでの遅延を D(m, n)

DTN ブロードキャストによって実現されるアプリケーショとする．メッセージのサイズを Size(m) とする．これらの定義

ンとしては，たとえば，被災地における危険情報や緊急情報の上で，実環境におけるブロードキャストに対する要件についなどの不特定多数への情報配信，ショッピングモール等におけて説明する．

る口コミ情報や広告の配信，ソフトウェアアップデートなどがブロードキャストでは，配布遅延の最大値が有限である必要考えられる．こうしたアプリケーションでは，なるべく多くのがある．例えば，緊急情報をブロードキャストする場合は，全メッセージが短い時間ですべてのノードに配信されることが望てのノードに必ず情報を配布しなければならない．そのため，ましい．また，メッセージには有効期限，すなわち，配信遅延

ノード間の接触機会が極端に少ないケースが除かれた環境では，の上限があると考えられる．例えば，広告の配信において，広必ず全てのノードへメッセージを配信できるようにするべきで告の対象がタイムセールのような時間限定のものである場合，ある．あるメッセージ m がすべてのノードへ配布が完了する

その時間を過ぎてしまっては意味がない．設定された配信遅延

までの配信遅延の最大値 M D(m) を以下の通り定義する．

までになるべく多くのノードにメッセージを配信できることが望ましい．口コミ情報などは，イベント等によっては，一度に多くのメッセージが発せられる可能性があるが，そうした流量∃m ∈ M, ∀n ∈ N,
M D(m) = max{D(m, n)}(1)の変化にも対応しなければならない．既存の DTN のルーティ

このとき，「全てのノードへメッセージを配信できるように

ング・アプリケーションの研究では，ノードの位置が得られる

する」とは，全てのメッセージが全てのノードへ有限時間内前提のものが多いが，屋外で電源が潤沢にあれば可能だが，アに配信できること，すなわち，m における配信遅延の最大値

プリケーションの適用先として屋内を想定すると，ノードの正M D(m) について，以下が成立することに対応する．

確な位置情報は得られない考えることが現実的である．
トラフィック量が多い状況では，ノード間の一回の接触で利用できるリンクの帯域をバッファの差分が著しく超える頻度が∀l ∈ M,
AD(M ) = max{M D(l)} < ∞(2)

メッセージを配信するアプリケーションにおいては，一部の!"#$%& '()*&

メッセージのみが極端に高速に配布されたり，低速に配布され+5&てしまうと，アプリケーションの設計者にとって性能の予測が

:.&

:/&

+.34-=&:<&+,3-9&

困難となり，扱いづらいシステムとなる．期限が与えられた場
合，期限内に配布できるメッセージの量が多いことが望ましい．

-5&!"#$%& '()*&+5&+,34-5&

すなわち，AD(M ) は小さいことが望ましい．

-5&!"#$%& '()*&

+,&

-,&

+.&

-.&

+,34-<&

また，広告配信や緊急情報配布等のアプリケーションでは，各ノードが早く情報を受け取る事で売上が向上したり，人命救助に役立つなどの利益がある．したがって，各ノードへメッ!"#$%& '()*&

+,&

-,&

+.&

-.&

+/&

-/&

:9&

:,&

:;&

!"#$%& '()*&

+9&

-9&

!"#$%& '()*&

+,&

-,&

セージが到達するまでの遅延は，短いほど良いと考えられる．
すなわち，次式で定義される全てのメッセージの配布遅延の平均 E(M ) は，小さいことが望ましい．平均値 E(M ) は次の通!"#$%012&!"#$%67812)*& 12CHI!"#$%J)*& >)*-?@?ABCDEFGD)*&りである．

E(M ) =

図 1 FCFO の動作

X X

D(m, n)(3)

3. 関 連 研 究n∈N m∈M

また，本研究ではメッセージの流量が大きく，ノード間のバッ
ファの差分が利用できる帯域量を上回る環境を想定する．全てのノードは等しい通信半径を持ち通信半径は R[m] とする．あるノードが通信範囲内に入ることを接触と呼び，ネットワーク
で生じる接触の集合を C とする．接触 c ∈ C で送信できるメッ
セージの合計サイズ B(c) とする．接触 c が発生した時に接触したノード n1 , n2 ∈ N が保持しているメッセージの差分の集合を Dif f (n1 , n2 , c) とする．本研究では，Epidemic Routingを前提とし，ノード間ではこの差分集合のみが転送されるとする．本研究が想定する環境は次の通りである．まず、送信されるメッセージがすべて送信可能な通信帯域量が確保できるだけの接触があるものとする。すなわち次が成り立つものとする

X

Size(m) <

m∈M

X

B(c)

(4)

ノードから不特定多数のノードへメッセージをブロードキャ
ストする技術はアドホックネットワークの分野で盛んに研究されている [6], [5], [4]．アドホックネットワークにおけるほとんどのブロードキャスト手法はフラッディングを基本として，ノードが密な環境において発生する重複した送信等のオーバーヘッ
ドを削減するよう手法が設計されている．しかし，メッセージの伝搬が途切れた場合の対処がなされていないため，ノード間の接触機会が少なく，リンクが断続的にしか利用できない環境
では，ノード間の接触を最大限に利用できず，配布遅延が増大
したり，期限内の配布率が低下したりする．

DTN におけるブロードキャスト手法やアドホックネットワー
クの一部のブロードキャスト手法では，蓄積運搬型転送を用いてネットワークの分断を超えたブロードキャストを実現している．しかし，スケジューリング順を考慮したものは少ない．文c∈C

ただし、１回の接触で、送信すべき差分集合の全てが送信できるとは限らないものとする。すなわち，次が成り立つとする

献 [7], [3], [11] では，FCFO (First Created First Out) という発信されたタイミングが早いメッセージほど優先して送信する
方法を用いている．しかし，発信された早さのみで優先順を∃c,決定すると，待っているノード数が多い確率が高い後発のメッX

Size(m) > B(c)(5)

セージが優先されないため待ち時間が増加する．また，配布率を考慮していないため，一部のメッセージが状況により遅れたm∈Dif f (n1,n2,c)

したがって，本研究における目的関数は以下の通りとなる．

場合に，アプリケーションが要求する期限内に配布できないという問題がある．図 1 はネットワーク中でメッセージが配布される様子を表す．一度の接触で交換できるメッセージ量は 1

minimize E(M ), AD(M )subject to (2)(4)(5)(6)

個とする．図ではネットワーク中でメッセージ M1 を受信した
ノードは 3 ノードでメッセージ M2 を受信したノードは 1 ノー

全てのノードの位置および，移動経路があらかじめ分かって

ドである．そのため，メッセージ M2 を送信する機会はあり，おり，ノード間でのメッセージの送受信に利用できる帯域も把

低い配布率を向上させる機会があるにもかかわらず，送信され握できる状況のもとでは，本問題を自動的に解くことは可能でなくなってしまい，より多くのノード数の待ち時間が増加してある．しかし，DTN では，全てのノードの状況を一箇所で集しまう．また，この例でメッセージ M2 より早く生成されたメッ

中管理することはできない．また，全てのノードの位置や移動

セージが大量に存在する場合，メッセージ 2 が極端に優先され経路は，一般には予測できない．よって本研究では，各ノードにくくなり，メッセージ M2 の遅延時間が極端に大きくなってが自律的に動作することで，この目的関数を満たすための方法

しまう．

を検討する．

文献 [1] では，アプリケーション層においてメッセージに優先度が付与されているという前提の上で，優先度が高いメッセージほど，少ない遅延で各ノードに配布されるような手法が提案!"#$%& '()*&

されている．具体的には，バッファ内のメッセージを他のノー+5&ドから送信要求された際に，優先度に比例した確率で要求され

:.&

いない．
文献 [8] では，ネットワーク中の局所的な配布率に応じてパ+.34-=&:<&!"#$%& '()*&+5&+,34-5&

メッセージに優先度が付与されていない場合や，優先度が同じ場合に遅延が少ないブロードキャストをする方法は提案されて:/&+,3-9&

たメッセージの返信の有無を決定することで，優先度ごとに配布速度を調整することに成功している．しかし，この手法では，-5&!"#$%& '()*&

-5&

+,&

-,&

+.&

-.&

+.34-<&!"#$%& '()*&

+,&

-,&

+.&

-.&

+/&

-/&

:9&

:,&

+,34-,K&!"#$%& '()*&

+9&

:;&
!"#$%& '()*&

-9&

+,&

-,&

ケットのスケジューリングをすることでノード間で接触しているのに通信できない無駄時間を削減するための手法が提案されている．具体的にはノードが分布する二次元平面をグリッドに!"#$%012&!"#$%67812)*& 12CHI!"#$%J)*& >)*-?@?ABCDEFGD)*&

分割し，各ノードは各メッセージに対して，各グリッド i に対

図 2 ESF の動作

するチケット値 g(i) という値を管理する．ノードは自分よりネットワーク全体で他のノードと接触しやすいノードに対して，した配布率の推定値を交換する．その推定値は，過去の一定期メッセージ送信時にメッセージに対してチケット値を付与して間に遭遇したノードのうちそのメッセージを保持していたノー送信する．受信側はその値をメッセージのチケット値にする．

ドと送信した相手の割合である．メッセージの送信順を決定す

チケット値はグリッド内で他のノードと接触する頻度が大きい

る際に，他のノードから収集した推定値の平均値を計算し，そノードほど大きく割り当てられる．この手順により，無駄時間の値を推定配布率とする．その推定配布率に基いて配布速度をの削減が可能となる．しかし，この手法では各ノードは位置情計算して配布速度が小さいものを送信する．ESF では，メッ報を管理する必要があるため，消費電力を節約する必要がある

セージの配布速度を推定して，推定値に応じてメッセージを送携帯電話などに適用するのは適切ではない．

信することで平均遅延と最悪遅延を削減できる．図 2 に ESF を

4. 提 案 手 法用いたブロードキャスト手法の例を示す．ノード N1 ははじめの 2 回の送信ではメッセージ M1 を送信している．これは配布

4. 1 提案手法の概要

速度が低いと見積もられているためである．これにより配布率

本稿では，DTN においてメッセージの配布率を考慮しメッが低いメッセージが送信されて，また，時間経過によってメッ

セージのスケジューリングを行うことで，待ちノード数が多

セージ M2 の配布速度が低下し，残りの 3 回の送信では配布率

いメッセージを優先し，平均配布遅延を削減し，配布率が高いが高いがネットワーク中に長く滞在しているメッセージ M1 がメッセージに送信の機会を与えることで，配布遅延（99 パーセ

2 個，メッセージ M2 が 2 個送信されている．このように，提ンタイル）を削減する ESF (Estimated Slowest First) を提案

案手法では配布率が低いメッセージが優先され，配布率が高い

する．

メッセージが送信されないケースや，一部のメッセージが極端

ESF の前提について述べる．ESF では，全てのノードは PIDに遅く配布されることが避けられる．

や MAC アドレスなどの一意な識別子を持つ．バッファ容量に

4. 2 配布率の推定上限は設けないものとする．ノードが GPS などの位置推定シ

ESF では，各ノードは過去の一定期間中に受信したサマリベ

ステムを利用して位置情報を取得することはここでは想定しなクタの集合と過去にメッセージを送信した相手ノードに基いてい．各ノードは他ノードの接触情報や将来の接触情報を知るこ

局所推定値を作成し，推定値を周囲のノードと交換し，局所推とはできない．各ノードは独立してメッセージを発信するとす定値の平均から配布率の推定値を求める．局所推定値のみで推る．ノードは接触した際に，自身のバッファ内のメッセージの定した場合，近傍の配布状況のみを反映しているため，ネット

ID のリストであるサマリベクタを交換する．そして，交換しワーク全体の配布率をより反映するため，本手法ではノード間たサマリベクタと自身のバッファ内のメッセージ集合の差分をで配布率の局所推定値を交換する．

取ることで，相手が保持していないメッセージ集合を特定して，

4. 3 ESF におけるメッセージ転送アルゴリズム

そのメッセージ集合を送信する．

ESF を用いたメッセージ転送アルゴリズムの流れを説明す

ESF では，配布率と生成されてからの時間を考慮することでる．概略を図 3 に示す．

性能を向上させる．配布率が低いほど，そのメッセージを待っ4. 3. 1 サマリベクタと推定値の交換ているノード数が多いため，配布率が低いメッセージを優先す

ノードは他のノードと接触した際にメッセージの ID のリスることで，平均遅延を削減することができる．また，経過時間

トであるサマリベクタを交換する．その際，サマリベクタへはと配布率を考慮することで，遅れているメッセージを考慮する

各ノードが過去に受信したサマリベクタと送信情報に基づきことができる上に，配布率が高くなった時点で配布が停止する

局所推定値が計算され付与される．各ノードはサマリベクタを確率が低下するため，最悪遅延を削減できる．

受信すると，ノード自身がバッファ内に保持するメッセージ集

具体的には，ノードは接触した際に，お互いに局所的に計算合と受信したサマリベクタの差分を照合して，相手が保持して数 N を記録しているとする．それぞれのメッセージ m ∈ M を他人に送信した回数を s(m) とする．
送信テーブルに存在するメッセージ数 h(m) は次の通り計算

bI4JK"#$%&'()
cd/34e67fg)*+,-.BUV)

される．

h(m) =

hi)!"#$%&'()*+,-./01)X

f (m, n)

(8)

n∈N

8
<0
f (m, n) =:1(m ∈ SV T (n))(m ∈/ SV T (n))(9)

これらの値に基いて，局所推定配布率 Cel (m) は次の通り計算

CDEAFGHI4JKL,-./MNBOPQ)/,-.(RS)する．

h(m) + s(m)N

(10)

T,-.GHUVJK)OPWXYZ[8)\<]A^B_`J9345a-)

Cel (m) =23456789)
0:6;<=>?/@A'B01)

過去の一定期間にノード間で交換した局所推定値をそれぞれ

4. 3. 4 推定値の計算
Cel (m)(0 < i < n) とすると，配布率の推定値は次の通り計算
する．

Ce (m) = E(Cel (m))

図 3 ESF の動作(11)

例えば，表 2, 1 の場合で，一定期間に遭遇したノードが 3

表 1 メッセージ送信先テーブル
メッセージ ID

送信先ノード集合

ノードであるとすると，メッセージ１は 2 つのノードに送信さメッセージ 1

ノード A，ノード B

れていると共に，どのノードも保持していないため，2/3 が局

メッセージ 2

ノード C

メッセージ 3

ノード D

所推定配布率となる．メッセージ 2 はノード C に送信されていると共に，ノード A とノード B が保持されているため，局所推定配布率は 1 となる．メッセージ 3 は 1 ノードに送信され

表 2 サマリベクタテーブル
ノード ID

保持メッセージ集合ていると共に，１ノードが保持しているため，局所推定配布率

ノード A

メッセージ 2，メッセージ 3

は 2/3 となる．各ノードはノードと接触した際に，それぞれの

ノード B

メッセージ 2

メッセージに対して計算したこれらの局所推定値をサマリベク

ノード C

メッセージ 4

タと共に送信する．

4. 3. 5 推定精度が低い場合の処理いないメッセージを選択して送信候補とする．先にサマリベク

配布率を推定する手法では履歴保存期間に他のノードから受タを受信したノードはメッセージ送信の開始を相手に通知送信

信した情報から配布率の推定値を推定するため，その期間にし，先にアルゴリズムに基いて選択したメッセージの転送を開ノードと全く接触していない場合，メッセージの配布率を推定始する．

できない．そのため，提案手法では推定に必要な情報が全くな

4. 3. 2 メッセージの交換い場合には送信するメッセージをランダムに決定する．

ノードはメッセージを受信すると，相手に送信開始を相手に通知し，自身のメッセージを送信する．メッセージはバッファ

5. 性 能 評 価中のメッセージのうち推定した配布速度が一番低いメッセージ

提案手法 ESF の有用性を示すために，既存手法との比較評価を選択して送信する．メッセージ m の配布速度 Ve (m) は次のを行った．本稿では，提案手法の評価にオープンソースの DTN式で計算する．ただし，Ce (m) を局所推定配布率とし，Te (m)

無線シミュレータである OneSimulator [2] を用いた．

をメッセージ m が発信されてからの経過時間とする．

Ce (m)Ve (m) =Te (m)

5. 1 評 価 環 境(7)

4. 3. 3 局所推定値の計算

本評価で用いたシミュレーションパラメータを表 3 にまとめる．
ノードは二次元平面上に分布する．全てのノードはランダム

ノードは交換する局所推定値 Cel (m) を次の通り計算する．

ウェイポイント，もしくは測定等から得られたトレースデータ

SVT(n) はノード n から一定期間中に受信した最新のサマリベに基いて移動する．また，それぞれのノードは，同等の計算能クタが含むメッセージの集合を示す．また，SMT(m) はある

力，バッファ容量，通信半径，帯域幅を持つ．ノードは通信範

メッセージを送信したノードの集合を示す．例えば，表 2, 1 の囲内に入ったノードを瞬時に検出でき, 同時にそのノードの識ようになる．また，ノードはある一定期間中に遭遇したノード

別子を取得できるものとする．ノードの検出には検波やビーコ表 3 シミュレーションパラメータ
パラメータ

値

通信範囲（半径）10[m]ビットレート

30kbps

シミュレーション時間

4400[s]

有効期限

2100[s]

メッセージサイズ

Sm[バイト]

メッセージ生成頻度

Im[s/メッセージ]

停止時間[0, 0]s

平均速度Sa[m/秒]

ノード数

160 ノード

Zipf 分布の歪度sンを用いる. 通信半径の大きさは, 二次元平面全体を覆わない大図 4 4 矩形マンハッタン移動モデル

きさとする. すなわち, ネットワーク分断が発生する想定となる.
全てのメッセージの重要度が等しいことを想定する．実環境
において，ユーザが必ずしも全てのメッセージ間の重要度を決定出来るとは限らないからである．例えば，災害地において情報を配信する場合ではほとんどの情報が重要であることが想定される．ネットワーク中で発信されるメッセージの量に関して
は，ノード間の一回の接触において交換できるメッセージ量を
ノード間のバッファの差分メッセージが頻繁に上回ることを想定する．実環境では，様々なアプリケーションがネットワーク
を利用し，多くのメッセージが配布されると予想できるからである．
メッセージの発信者は評価の目的に応じて，Zipf の法則 [9]，一様分布に従うものとする．Zipf の法則は経験的に得られた法則であり，様々な現象（Web ページへのアクセス頻度や都市の人口など）において確認されている．Zipf の法則では，要素たノードの中で 99 番目に遅く受け取った値である．この値が平均配布遅延から離れていれば離れているほど，公平性が低く，近ければ近いほど公平性が高い．また，この値はある期限が存在する時，99%の配布率を達成を期待できる期限を示す．以下の評価のグラフでは，99 percentile of 100% delivery delay と記す．

5. 3 比 較 手 法
本評価で用いる比較手法は次の通りである．ただし，メッ
セージ m が生成されてからの時刻を Te (m) とする．

•

たす送信メッセージ ms を選択する．

ms = arg max Te (m)

(13)

m∈M

は下記の式から要素のサイズによって順位付けされる．式中のk は順位，N は要素数，s は頻度の偏りのパラメータの歪度でFCFO (First Created Fist Out)

各ノードは送信するメッセージを選択する際に，次の条件を満•OSF (Optimized Slowest First)

ある．s の値が大きいほど発信頻度が低いノードの割合が高く

各ノードがそれぞれのメッセージの正確な配布率 D(m) を知っなる．

ている前提で，次の条件を満たす送信メッセージ ms を選択

1/ks
f (k; s, N ) = PNsn=1 1/nする．

(12)
ms = arg minm∈M

また，メッセージの ID は 128 ビットとし，ID はメッセージ

D(m)Te (m)(14)の生成時刻や内容等から SHA 等のハッシュ関数で生成される

この手法は提案手法がどれだけ理想に近いかどうかを測るためものとする．サマリベクタは上記の ID のリストとして表現しのものである．

た．ノード間で情報を交換する手法においてノード間でやり取•

RS (Random Selection)

りするメッセージに付与する情報のサイズはメッセージ一個あ

送信メッセージ ms を差分メッセージ集合から一様分布に従いたり 32 ビットとした．

選択する．

5. 2 評 価 指 標
本評価にて用いた指標は次の通りである．

•

平均配布遅延5. 4 配布率と平均配布遅延・配布遅延（99 パーセンタイル）との関係
図 5, 図 6 に配布率と平均配布遅延・配布遅延（99 パーセンタイ

メッセージが発信されてから各ノードに到達するまでの遅延のル）との関係を示す．この評価の移動モデルには Mobireal [10]平均である．この指標は発信されたメッセージが各ノードに到のマンハッタンにおける人の移動を模したモデルを用いた．こ達するまでに期待できる遅延を示す．以下の評価のグラフでは，の移動モデルでは，図 4 のように 4 つの矩形の周囲をノードがAverage delay と記す．

自律的に移動する．メッセージサイズは 30[K バイト]，Zipf 分•

配布遅延（99 パーセンタイル）

布の歪度は 1.5，ノード数は 160[ノード] とした．図 5，図 6 よ各メッセージの配布率が 100%に到達するまでの遅延の 99 パー

り，ESF は配布率が 90%以上の場合 RS よりも平均配布遅延がセンタイルである．すなわち，各メッセージを最後に受け取っ

遅いが，配布率が 90%以下の場合，RS よりも平均配布遅延が図 5 配布率と平均配布遅延の関係

図 8 Zipf 分布の歪度 S を変化させた場合の配布遅延（99 パーセンタイル）

図 11

メッセージサイズが変化した場合の平均配布遅延の変化（Mobireal）

図 6 配布率と図 7 Zipf 分布の歪度 S を変化させた場合の配布遅延（99 パーセンタイル）の関係

図9

メッセージサイズを変えた場合の平均配布遅延図 10

メッセージサイズを変えた場合の配布遅延（99 パーセンタイル）の変化

平均遅延の変化

図 12 メッセージサイズが変化した場合の配布遅延（99 パーセンタイル）の変化（Mobireal）

小さくなっている．また，配布遅延（99 パーセンタイル）で比を 0.5[個/秒] に固定し，ノードの平均移動速度を 1.0[m/秒] と較した場合，各配布率において，RS と比較して 50%以上，配した．図 7, 図 8 によると，メッセージの偏りを示す歪度 S が大布遅延を低下させることに成功している．配布率が 90%以上

きくなれば大きくなるほど，全ての手法において平均遅延が増の場合の配布率の上昇が少ないのは，配布率の推定精度の誤差加している．これは，送信者が偏れば偏るほど，送信者の能力により，配布率が 90%以上のメッセージより，配布率 70%からをより大きく超えたメッセージを送信しなければならなくなり，80%の範囲のメッセージが優先されてしまうからである．OSF

一度の接触で送信できないメッセージ量が増え，それらのメッと比較して約 10%の配布遅延（99 パーセンタイル）が大きく

セージが次の接触を待たなければならなくなるからである．まなっている．したがって，配布が遅れているメッセージの検出

た，RS では一部のメッセージの送信頻度が著しく低下するた

回数，及び配布率が低いメッセージの検出回数が低くなっていめ，未配布メッセージが増大していることがわかる．また，偏ることがわかる．

りが増加するにつれ，LCFO の配布遅延（99 パーセンタイル）

5. 5 メッセージ発信者の偏りが変化した場合の性能の変化が増大し，FCFO の平均遅延が増大しているのに比べ，OSF，Zipf 分布の歪度を変化させた場合の性能の変化を調べた．各

ESF では平均遅延は僅かに増加しているが，配布遅延（99 パー

種パラメータはメッセージサイズを 30K，メッセージ発信間隔

センタイル）の増加は抑えられている．

5. 6 メッセージサイズを変えた場合のノードに送信することもできる．その点も考慮してどのメッ

メッセージサイズを変更した場合の性能の変化を調べた．図

セージを送信すべきか決定可能な手法も設計する必要がある．

9 によると，メッセージサイズの大きさが増加するに従い，全ての手法で平均配布遅延が増加している．OSF と ESF と比較して FCFO の平均配布遅延の増加が著しいのは，発信者の偏りがある環境では，限られた発信者から，ネットワーク中のそれ以外のノードへ配布されるメッセージの個数が減少することと，常時最も早い段階で発信されたメッセージのみが配信されるため，ほとんどのメッセージが発信者の手元から離れないか
らである．図 10 によると，メッセージサイズが増加するに従い RS，FCFO では最悪配布時間が急増している．これは，ある境界線を超えると現実的な時間では，配布が遅れているメッ
セージが偶然に配布される確率が減少し，配布率の上昇率が低下するためである．一方，ESF，OSF では，配布率の上昇率に応じて配布率を決定しているため，配布が遅れているメッセー
ジが優先され，最悪時間の増加は抑制されている．

5. 7 実環境の移動モデルにてメッセージサイズを変えた場
合の性能変化
実環境における有効性を示すために，実環境の移動モデルを用いて提案手法の評価を行った．本評価では，トレースデー
タに基づいた移動モデルの生成に，移動モデル生成器である

Mobireal [10] を利用した．図 11，12 はメッセージサイズを変化させた場合の配布遅延の変化である．これらの図より，RWPの移動モデルの場合と，メッセージサイズが小さい場合を除いて，同等の結果が得られたことがわかる．

6. 考

察

章 5. の評価より，ESF はトラフィックが多くメッセージに偏りがある環境において平均配布遅延，配布遅延（99 パーセンタ
イル）の双方を削減できる手法であることがわかる．また，実環境に近い移動モデルにおける評価でも，トラフィック量が大きい場合に，RS と比較して平均配布遅延を最大 13 ％，配布遅延（99 パーセンタイル）を最大 50 ％削減できている．

7. ま と め
本研究では位置情報を利用せずに，アプリケーションが要求する期限内にできるだけ多くのメッセージを配信し，各ノードへの配布遅延のばらつきを抑えるような手法を提案した．具
体的には，各メッセージをネットワーク中での配布速度の小さ
い順に送信することで各ノードへメッセージの配布遅延とばらつきを削減しつつ，期限内に配布できるメッセージ数を向上させた．
今後の課題としては，第一に配布制度の向上が挙げられる．
提案手法は理想的な手法である OSF と比較して，平均配布遅
延と配布遅延（99 パーセンタイル）が 10%大きい．配布率の推定制度を向上させることでこれらの遅延を削減できると考えられる．
第二に，実環境における実装のために様々なことを考慮する必要がある．例えば，UDP 上で本手法を実装する場合，Mac層のブロードキャストを利用して同一のメッセージを同時に他

文

献[1] H. Gong and J. Kim. A prioritization-based applicationoriented broadcast protocol for delay-tolerant networks.
In Wireless Communications and Networking Conference,
2009. WCNC 2009. IEEE, pp. 1 –6, april 2009.
[2] A. Keränen, J. Ott, and T. Kärkkäinen. The one simulator
for dtn protocol evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques,
Simutools ’09, pp. 55:1–55:10, ICST, Brussels, Belgium,
Belgium, 2009. ICST (Institute for Computer Sciences,
Social-Informatics and Telecommunications Engineering).
[3] A. Khelil, P. J. Marrn, C. Becker, and K. Rothermel. Hypergossiping: A generalized broadcast strategy for mobile
ad hoc networks. Ad Hoc Networks, 5(5):531 – 546, 2007.
[4] A. Khelil and N. Suri. Gossiping: Adaptive and reliablebroadcasting in manets. In A. Bondavalli, F. Brasileiro,
and S. Rajsbaum eds., Dependable Computing, Vol. 4746 of
Lecture Notes in Computer Science, pp. 123–141. Springer
Berlin Heidelberg, 2007.
[5] A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying for ﬂooding broadcast messages in mobile wireless networks. In System Sciences, 2002. HICSS. Proceedings ofthe 35th Annual Hawaii International Conference on, pp.
3866 – 3875, jan. 2002.
[6] Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for ﬂooding in wireless mobile ad hoc networks. In
Wireless Communications and Networking, 2003. WCNC
2003. 2003 IEEE, Vol. 2, pp. 1124 –1130 vol.2, march 2003.
[7] A. Vahdat and D. Becker. Epidemic routing for partiallyconnected ad hoc networks. 2000.
[8] Y. Wang and J. Wu. Ticket-based multiple packet broadcasting in delay tolerant networks. Ad hoc and Sensor Wireless Networks, April 2012.
[9] G. Zipf. Human behaviour and the principle of least-eﬀort.
Addison-Wesley, Cambridge, MA, 1949.
[10] 山口弘純, 安本慶一, 東野輝夫. モバイルネットワークアプリケー
ションの現実的評価を可能とするシミュレータ mobireal の設計
構想. 静岡大学情報学研究, 10:117–125, 2004.
[11] 澤村雄介, 寺西裕一, 竹内亨, 春本要, 西尾章治郎. 遅延耐性ネッ
トワークにおける安定リンクの推定と維持に基づくブロードキャ
スト効率化手法. マルチメディア、分散協調とモバイルシンポジ
ウム 2011 論文集, 第 2011 巻, pp. 1121–1129, jun 2011.