修士論文 重要度とデッドラインを考慮した情報BOX経由の DTNデータ

NAIST-IS-MT0851005
修士論文
重要度とデッドラインを考慮した情報 BOX 経由の
DTN データ配送手法
石丸 泰大
2009 年 2 月 4 日
奈良先端科学技術大学院大学
情報科学研究科 情報処理学専攻
本論文は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した修士論文である。
石丸 泰大
審査委員：
伊藤 実 教授
（主指導教員）
山口 英 教授
（副指導教員）
安本 慶一 准教授
（副指導教員）
孫 為華 助教
（副指導教員）
重要度とデッドラインを考慮した情報 BOX 経由の
DTN データ配送手法∗
石丸 泰大
内容梗概
被災地やイベント会場などでは，固有な通信インフラ（携帯電話網，WLAN な
ど）を満足に使用できない場合がある．このような環境で遅延耐性ネットワーク
(DTN, Delay/Disruption Tolerant Network) を用いて情報の収集や散布を行う研
究が近年注目されている．これまでの DTN に関するる研究は，データ配送成功
率の向上や遅延の縮小などを目的としており，データの優先順位を考慮し，優先
度の高いデータをより確実かつ早期に送り届けることを目的とする研究は存在し
ない．
本研究は，DTN 環境において，メッセージの重要度や配信期限 (デッドライン)
を考慮し，重要かつ緊急性のあるデータを優先して処理することによって，輻輳
が発生しても，重要度の高いデータの配送率をできるだけ高くすることを目的と
する．提案手法が運用されるサービスエリアには，Bluetooth 機能を備えたバッ
テリ駆動の小型 PC が幾つかの地点に情報サーバ（以降，情報 BOX とする）と
して配置されると想定し，情報 BOX 間の直接通信はできないとする．ユーザは
Bluetooth 機能を備えた携帯端末 (携帯電話，ノート PC など) を所持しており，情
報 BOX とデータの送受信を Bluetooth を介して行うが，ユーザ間の通信は行わ
ないものとする．また，情報 BOX は情報 BOX 間を往来するユーザの移動確率
の統計的データを把握しているとする．ある情報 BOX(SRC とする) と通信可能
なユーザは，その情報 BOX にリクエストを送信することでシステムを利用する.
∗
奈良先端科学技術大学院大学 情報科学研究科 情報処理学専攻 修士論文, NAIST-ISMT0851005, 2009 年 2 月 4 日.
i
リクエストは, 「将来訪れる情報 BOX(DEST とする) に保存されているデータを
途中で訪れる別の情報 BOX(RL とする) において受け取りたい」という形式で記
述されるとする. リクエストには，リプライを得たときの満足度と，デッドライ
ン (RL を出発するまでの予定時間) が付される. 提案手法では，情報 BOX はリ
クエストを受信すると，それを DEST まで届け，リプライを DEST から RL に届
けるために，情報 BOX 間のユーザ移動確率に基づいて必要数のデータを複製し，
複製したデータを異なるユーザに渡すことで，適切な複製数で高い配送率を実現
する.
また，輻輳が発生した際に無駄な帯域消費を防ぐため，処理するデータの取捨
選択を行う. この際，
（1）情報 BOX がコストパフォーマンス (単位データ量に対
する満足度, 以降 ECP と呼ぶ) を計算し，ECP の高いデータを優先的に配信する
ようキュー管理を行う，
（2) デッドラインに間に合わないと見積もったデータを
キューから廃棄する，
（3）情報 BOX がデッドラインに間に合わないと判断した
データの受信を拒否する，といった工夫により，不必要なデータ運搬を省き，シ
ステム全体で達成される満足度の総和を最大化する．
提案手法の有効性を確かめるために，マンハッタンモデルを想定したシミュレー
ション実験を行い，FIFO やデッドライン順などの，他の手法と比較した．さま
ざまなユーザの移動パターンで，リプライのデータサイズを変化させ実験を行っ
た結果，提案手法におけるデータ配送成功率は他の手法よりも 10%から 25%程度
優れていることを確認した. また，満足度の総和においては，提案手法が 20%か
ら 50%程度優れていることを確認した．
キーワード
遅延耐性ネットワーク，データ配送，キャリーアンドフォワード，優先度キュー
イング
ii
DTN Data delivery method using priority and
deadline∗
Yasuhiro Ishimaru
Abstract
In a specific environment such as disaster area and event area, communication
infrastructure (e.g., cellular phone network, WLAN, etc.) might not be available
due to damage or deployment cost. There have been a lot of research activities
aiming to realize data delivery/dissemination in such an environment with delay
tolerance network (DTN, Delay/ Disruption Tolerant Network). Most of existing
studies on DTN focus on improvement of data delivery success ratio and reduction
of delay, and there are little studies that allow data delivery taking into account
data priority and deadline.
In this thesis, we propose a DTN (Delay Tolerant Network) based data delivery
method for an environment without communication infrastructures (e.g., disaster
area, event place, etc) that takes into account relative importance and deadline
of users’ data requests. As a target application, we suppose a system that allows
users in the target service area to retrieve word-of-mouth information such as
photos on sightseeing spots. We assume that multiple portable servers called
“InfoBoxes” that collect/disseminate data from/to user terminals via short range
wireless communication (e.g., Bluetooth) are deployed in the service area. In our
proposed system, each user terminal sends, to an InfoBox, a query specifying (1)
a destination spot on which the user wants to get information, (2) the importance
∗
Master’s Thesis, Department of Information Processing, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT0851005, February 4, 2009.
iii
of the query (to what extent the user satisfies when getting the query response),
and (3) a receiving spot where the user wants to receive the query response. We
propose a carry-and-forward based technique for delivering queries/responses so
that the overall user satisfaction is maximized. Depending on a given probability
of user movement between two spots, the proposed method appropriately adjusts
the number of data replicas copied from each InfoBox to user terminals. In
addition, we introduced a method that each InfoBox does not accept data upload
from user terminals when the data is likely to exceed the delivery deadline, and
discards the data in its queue which cannot meet the delivery deadline, for efficient
bandwidth utilization. Through computer simulations, we confirmed that the
proposed method achieves 20 – 50 % better overall user satisfaction than other
conventional methods such as FIFO and EDF(early deadline first).
Keywords:
Delay Tolerant Network，Data delivery，Carry-and-forward, Priority Queuing
iv
目次
1. 序論
1
2. 関連研究
5
3. DTN を利用したデータ配送問題
8
3.1 携帯通信端末に対する仮定 . . . . . . . . . . . . . . . . . . . . . .
8
3.2 情報 BOX に対する仮定 . . . . . . . . . . . . . . . . . . . . . . .
9
3.3 ノードの移動モデル . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.3.1
ノードの移動経路 (ノードのみが知っている情報) . . . . .
9
3.3.2
スポット間の移動確率と移動時間 (情報 BOX のみが知って
3.4
いる情報) . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
DTN における優先度とデッドラインを考慮したデータ配送問題 .
11
4. 優先度とデッドラインを考慮した DTN 配送手法
12
4.1 提案手法における各ノードと情報 BOX の動作 . . . . . . . . . . .
12
4.1.1
ノードの動作 . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.1.2
情報 BOX の動作 . . . . . . . . . . . . . . . . . . . . . . .
13
4.2 経路制御とキュー管理 . . . . . . . . . . . . . . . . . . . . . . . .
14
4.2.1
複製数の見積もり . . . . . . . . . . . . . . . . . . . . . . .
14
4.2.2
交信時間の見積もり . . . . . . . . . . . . . . . . . . . . .
15
4.2.3
複数の情報 BOX を経由する場合のコストパフォーマンス
値の計算 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.3 アルゴリズムの改良 . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.3.1
データ配送調整カウンター機能 . . . . . . . . . . . . . . .
18
4.3.2
キューイング遅延の推定に基づく選択的アップロード . . .
19
5. 実験
22
5.1 実験設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
サービスエリア . . . . . . . . . . . . . . . . . . . . . . . .
25
5.1.1
v
5.1.2
比較対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
5.1.3
複数の環境の用意 . . . . . . . . . . . . . . . . . . . . . . .
26
5.1.4
評価結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
5.1.5
環境の違いによる詳細な評価 . . . . . . . . . . . . . . . .
29
5.1.6
提案手法の改良機能の効果 . . . . . . . . . . . . . . . . . .
33
6. 結論
37
謝辞
38
参考文献
39
vi
図目次
1
想定環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2
グラフ表現された地図 . . . . . . . . . . . . . . . . . . . . . . . .
10
3
メッセージ配送時間の見積もり . . . . . . . . . . . . . . . . . . .
15
4
データ配送調整カウンター機能 . . . . . . . . . . . . . . . . . . .
19
5
キューイング遅延の推定に基づく選択的アップロード機能 . . . .
21
6
シミュレーションの様子 . . . . . . . . . . . . . . . . . . . . . . .
22
7
コンタクトタイム . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
8
サービスエリアにおけるスポット間移動経路 . . . . . . . . . . . .
25
9
全ての環境における平均メッセージ取得成功率 . . . . . . . . . . .
28
10
全ての環境における平均ユーザ満足度
. . . . . . . . . . . . . . .
28
11
各環境における平均メッセージ取得成功率 . . . . . . . . . . . . .
30
12
各環境におけるユーザ満足度
. . . . . . . . . . . . . . . . . . . .
32
13
各環境における平均メッセージ取得成功率 . . . . . . . . . . . . .
34
14
各環境におけるユーザ満足度
. . . . . . . . . . . . . . . . . . . .
36
表目次
1
用語の定義
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2
経路の種類
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3
スポット間の移動確率の例 . . . . . . . . . . . . . . . . . . . . . .
10
4
リクエストフォーマット . . . . . . . . . . . . . . . . . . . . . . .
12
5
時間の種類
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
6
シミュレーションの設定 . . . . . . . . . . . . . . . . . . . . . . .
23
7
ユーザのスケジュールの組み合わせ . . . . . . . . . . . . . . . . .
27
vii
1. 序論
被災地やイベント会場などでは，固有な通信インフラ（携帯電話網，公衆無線
LAN など）を満足に使用することのできない場合がある．このような環境で情報
の蓄積，収集，散布を行うために，低コストで短期間に構築できるアドホックネッ
トワークがよく用いられる．しかし，アドホックネットワークで広いエリアを完全
にカバーすることは困難なため，アドホックネットワークをエリア内の複数の地
点に散発的に構築し，スポット間は衛星通信や人間の移動によりデータの受け渡
しを行う遅延耐性ネットワーク (DTN， delay/Disruption Tolerant Network)[5]，
が近年注目されている.
DTN 技術はこれまで，宇宙空間における衛星間通信や，砂漠のような過疎地
域における集落間通信に有効と考えられてきた．近年，携帯電話には Bluetooth
や WiFi が標準装備され，携帯電話同士のみならず，パソコンとの連携なども行
うことができるようになった．DTN 技術を用いることによって，固定ネットワー
クがなくても情報検索と流通のプラットフォームを構築することが可能と考えら
れる．DTN 技術の標準化を研究する専門グループである IRTF DTNRG[4] の活
動とその関連研究により，これまでにいくつかキャリーアンドフォワード (通信可
能な端末が現れるまで，情報を保持し続けたまま移動することにより情報転送を
可能とする技術) を用いた経路制御手法が提案されてきた．Epidemic routing[18]
は，移動中に出会ったノードに，確率的に複製を配信するという，もっとも基本
的な DTN ルーティング手法である．他にも，コンタクトオラクル (いつどのノー
ドとコンタクトするかという情報) が利用できるという仮定のもと，コンタクト
待ち時間が最小になる通信パスの選択を行う MED[8] や，過去のコンタクト履歴
情報を収集してコンタクト待ち時間を予測する MEED[9] という手法が提案され
ている．その他にもノードのモビリティを利用してトポロジを予測する手法 [19]
など，DTN を対象とした経路制御手法が多数提案されている．しかし，これら
の既存手法は，いずれもデータ配送における遅延時間を小さくしデータ到達率を
均一に高めることを目標としており，データ間の重要度が考慮されていない．そ
のため，輻輳が発生する際，すべてのデータにおいて一様に到達率が低下し，シ
ステム全体の性能が著しく低下してしまう問題がある．
1
本研究は配送データの重要度や配送期限を考慮し，重要かつ緊急性のあるデー
タを優先して処理することによって，輻輳が発生する場合でも，重要度の高いデー
タの配送成功率をできるだけ高くすることを目的とする． 図 1 は本研究で想定するサービスエリアの一例である．図 1 の SRC，RL，DEST
やその他のスポットに，Bluetooth 機能を備えたバッテリ駆動の小型 PC(ノート
PC など) が情報サーバ（以降，情報 BOX と呼ぶ）として置かれると想定する．
さらに，ユーザは Bluetooth 機能を備えたの携帯端末 (携帯電話，ノート PC な
ど) を所持しており，情報 BOX とデータの送受信を Bluetooth を介して行える
とする．ただし，情報 BOX 間，ユーザ間のデータ通信は行わないものとする.
情報 BOX は各スポット間を往来するユーザの移動確率と所要時間を統計的に
把握しているとする．また，提案手法では次の二つの仮定を置く．
（1）情報 BOX
間の直接通信ができない．前述したように，提案手法を適用する環境では，広域
通信インフラが満足に使用できない場合が多く，情報 BOX 間の直接通信ができ
ない，あるいは使用可能帯域が非常に小さいと想定する．
（2）ユーザ間の通信（す
れ違い通信）を行わない．ユーザ間の通信を許す場合，短期的に見れば，送受信
できるデータ量が増加するが，常にプローブ状態のユーザ携帯端末はバッテリの
消耗が激しく，逆にデータを既定のスポットに運べなくなる可能性が高い．提案
手法では，ユーザの移動速度とスポット間距離から，ユーザと情報 BOX とのコ
ンタクト時間を見積もることができるため，コンタクトする時だけ，ピンポイン
ト的にユーザ端末の Bluetooth をオンにすることで，電力消費を最小限に抑える．
図 1 を用いて提案システムの応用アプリケーションを説明する．システム利用者
が，現在滞在しているスポット (SRC:Source) から，
「スポット DEST(Destination，
今後訪問するスポット) に関する写真や動画などの情報を，スポット RL(Receiving
Location，DEST に行く途中に通過する場所) に送ってほしい．このコンテンツ
を取得できた場合に x 点の対価 (満足度) を支払う」，という情報リクエストを出
す場合の動作例を考える．想定する環境において，サイズの大きいデータが頻繁
に送受信されるなどして，DTN の輸送容量を超えた場合，全てのデータをそれ
ぞれの配送期限までに配送することは不可能である．そのような場合では，個々
のデータを配送する際のコストパフォーマンス (単位データ量あたりの満足度, 以
2
降 ECP と呼ぶ) を計算し，効率の良いデータ配送を行うことで，システム全体で
達成されるを満足度の総和を最大化することが望まれる．以上より，本研究では，
配信するデータに満足度と配送期限 (デッドライン) の属性を持たせ，デッドライ
ンまでに配信されるコンテンツのユーザ満足度の総和をできるだけ大きくする経
路制御手法を提案する．本研究では，
（1）情報 BOX はリクエストの満足度，及び
それを達成するために必要なデータ複製量（リクエストとリプライ）から ECP を
計算し，ECP の高いデータを優先的に配信するよう情報 BOX でキュー管理を行
う，
（2）送信キューのデータ量とユーザによるデータの運搬速度に基づき，配信
期限に間に合わないと見積もったデータを情報 BOX のキューから廃棄する，
（3 ）
情報 BOX はユーザが運搬してきたデータを受信する前に，そのデータが配送期
限内に配送可能か計算し，間に合わないと見積もった場合，データの送信を拒否
する，という３つのアイディアを用いて輻輳が起こった場合でもシステム全体で
得られる満足度の総和を最大化するデータ配送を行う．
図 1 想定環境
提案手法の有効性を確かめるために，マンハッタンモデルを想定したシミュレー
ション実験を行った. その際，比較相手として，データの先着順 (FIFO 式) キュー，
満足度順キュー，デッドライン順キューを挙げた. さまざまなユーザの移動パター
ンで，リプライのデータサイズを変化させ実験を行った結果，提案手法のデータ
配送成功率は他の手法よりも 10%から 25%程度優れていることを確認した. ま
3
た，満足度の総和においては，提案手法が 20%から 50%程度優れていることを確
認した．
4
2. 関連研究
近年，DTN に関する研究が盛んに行われている．DTN 技術の標準化を研究す
る専門グループである IRTF DTNRG[4] の活動により，これまでにいくつかの経
路制御手法が提案されてきた．通信可能な全ノードにデータを配信するフラッディ
ングと異なり，移動中に出会ったノードに確率的にデータを複製する Epidemic
routing[18] は DTN における基本的な手法であり，複製する確率に応じて高い到
達率を得られるが，バッファ容量や通信帯域を無駄に消費し，スケーラビリティ
の点で問題があると考えられている [8]．そのため帯域やバッファを節約し，人や
車のモビリティを効果的に利用して情報を配信する様々な研究が行われている．
Jain ら [8] の研究では，通信の断絶のパターンが既知のものとし，遅延を最小
にする経路制御問題の定式化を行っており，幾つかの基本的なルーティングアル
ゴリズムの提案が行われている．Yong ら [20] は，符号化したメッセージを k × r
個のブロックに分割し (このブロックの合計サイズは，元のメッセージの r 倍に
なる)，k 個のブロックが宛先に到達すれば，元のメッセージが復元されるような
符号化を既存のルーティング手法に導入することを提案している (k は定数，r は
複製因子:replication factor)．この研究により，一定のオーバヘッドを保ちつつ，
遅延時間を抑えることができることを明らかにしている．Xuwen ら [21] はノー
トルダム大学で収集したデータセットを元に，Epidemic routing を用いてデータ
を共有するようなアプリケーションを想定し，実験を行った．しかし過去の文献
[18] にあるような高い到達率を得ることはできなかった．文献 [23] では，Message
Ferrying (MF) アプローチを提案している. これは既知の経路を通る移動ノード
をデータを運搬する媒介とすることで，効率良くデータ配信を行う手法である.
文献 [12] では，Data mule アプローチを提案している. これは mule という端末
が，フィールドを移動して情報を回収する方式である. 情報を運搬する媒介とし
て，日常に用いられる自動車を想定した研究も存在する [13]，[2].
Zhao ら [24] は送信の機会 (コンタクト) が多ければ DTN の性能が改善されると
考え，ThrowBox という情報を蓄積する固定ノードを配置して DTN をネットワー
ク容量の面で強化することを提案した．情報を蓄積する固定ノードをシステム内
に複数配置し，各ユーザの通信の機会を増やす．Throwbox の最適な配置場所を
5
決定するアルゴリズムと，マルチパスルーティングでデータ配送を行うアルゴリ
ズムを提案し，シミュレーションによってその効果を確認している．Banerjee ら
[1] は Zhao らの研究 [24] をさらに発展させ，実際に Throwbox の試作品を作成し
たうえで，電力消費量を改善する方法を提案し，UMassDieselNet[17] と呼ばれる
バスを利用したテストベッドを用いて実機による実験を行い，Throwbox によっ
て遅延時間が改善することと，データ配送率と Throwbox の電力消費量がトレー
ドオフとなることを明らかにしている．
また，ネットワークの輻輳制御として，既存の TCP/IP 通信ネットワークでは，
RED(Random Early Detection)[6] によって確率的なパケット廃棄を行う方法が有
効である. DTN 上での輻輳制御も研究されている. 文献 [11]，[22] では，バッファ
残量が足りない場合は近隣のノードにメッセージを移動させることで，輻輳を回
避している. 本研究では，メッセージの優先度とデッドラインを考慮したキュー
管理と，デッドラインまでに間に合わないと見積もったデータの廃棄を行うこと
で，輻輳した状況に対処する点が，既存研究 [11]，[22] と異なる.
また，DTN に関するいくつかの研究開発プロジェクトも活発に行われている.
Wizzy[16] は，敷設コストの問題でインターネットの使用できないエリアに，人の
モビリティを利用してデータを運ぶことで，インターネットサービスを提供する
プロジェクトである. 同様の目的のプロジェクトとして，TIER[15]，KioskNet[10]
などがある. Haggle[14] は，PSN(Pocket Switched Network) と呼ばれる，携帯端
末を所持したユーザのモビリティを利用してデータを運ぶことで形成されるネッ
トワークに関する研究を行っているプロジェクトである. Haggle プロジェクトで
は，ノード間のコンタクト時間をログデータとして記録し，そのログデータを元
に DTN におけるルーティングの研究などを行っている. 文献 [7] では，Infocom
2005 の会場で端末同士のコンタクト時間を記録し，人や時間によってコンタクト
時間に特徴があることを明らかにしている.
以上に述べたように，DTN において到達率を高めるためにさまざまな工夫や
実験が行われている．しかし，現実に利用可能な通信帯域を考えれば，要求され
たデータを一度のコンタクト時間に送信しきれない場合も存在する．重要なデー
タを優先的に受信するために，データの重みに応じた優先制御が必要であるが，
6
既存研究はデータの緊急性や重要度などは考慮されていない．
本研究ではデータ配送を行う際に情報 BOX を用いるため，Throwbox モデル
[24] に近いモデルを採用している．しかし，人の移動確率を利用した複製数の調
整を行うこと，ノード間の通信は行わないこと，データ間の優先度を考慮してい
ること，データの配送途中で配送予定時刻の見積もりを行い，配送期限に間に合
わない場合は，そのデータを廃棄することなどが既存研究 [24]，[1] と異なる．
7
3. DTN を利用したデータ配送問題
本章では，提案手法を実現するための前提条件となる諸仮定について述べ，本
研究が対象とする，DTN を用いたデータ配送問題を定義する. 本章および以降の
章で用いる用語の定義を表 1 にまとめる．
表 1 用語の定義
用語
スポット
Source
Destination
Receiving Location
Deadline
満足度
移動確率
コストパフォーマンス期待値
記号
Spot
SRC
DEST
RL
Deadline
Satis
pMove(x，y)
ECP
意味
観光スポットなどの人が訪れる場所．情報 BOX が存在する．
リクエストの送信地点
リエストの送信先，宛先情報源
宛先情報源から送られるリプライ（コンテンツ）の受信地点
DEST のコンテンツを受け取るまでの配送期限．
ユーザが送受信要求（リクエスト+コンテンツ）に対して付与する対価点数．
要求したコンテンツを Deadline までに配信されれば，同額な満足度を支払う．
スポット x に滞在している人が次のスポット y に移動する確率
送信要求のコストパフォーマンスの期待値 (満足度/データ量)．
提案手法では，ユーザは携帯通信端末を持ち，図 1 のようなサービスエリア
（提案手法に基づくデータ配送を実行する地理的領域）における各スポットに情
報 BOX と無線通信によりデータ交換を行うものとする．以下で携帯通信端末お
よび情報 BOX に関する仮定を述べる．
3.1 携帯通信端末に対する仮定
提案手法におけるノードはユーザが所持する携帯電話，PDA のような携帯通
信端末であると仮定する．携帯通信端末は，下記の機能を持っている．
• プログラム処理能力: 提案手法を実装したプログラムを処理する能力．
• デバイス ID: 各端末はユニークな ID を持つ．この ID だけで端末を特定で
きる．
• 電子地図: 指定した 2 点間の歩行経路およびその距離を計算できる．
8
• バッファ: データ送受信用メモリバッファ．移動中に情報 BOX から送信さ
れるデータを全て保存できる程度に大きい.
• 通信機能: Bluetooth による通信ができる．
3.2 情報 BOX に対する仮定
各スポットにデータの蓄積と送受信機能を有するバッテリ駆動の小型サーバが
一台ずつ設置されており，これを情報 BOX と呼ぶ．情報 BOX はその付近を往
来するノードと Bluetooth で通信ができ，リクエストやコンテンツ情報をデータ
とした双方向通信が行えると仮定する．隣接するスポットは Bluetooth の電波到
達距離より離れており，情報 BOX 間の通信はできないものとする．また，各情
報 BOX におけるリクエストとコンテンツの送信順序は，すべてその情報 BOX で
スケジューリングされる．情報 BOX として，バッテリ動作可能なノート PC な
どを使用することを想定する．
また，情報 BOX では，過去に通信したノードの ID を保持することによって，
現在コンタクトしているノードが過去にコンタクトしたかどうかを判断できると
仮定する．情報 BOX は，スポットへの入口/出口付近に設置されるものとし，各
ノードは各スポットを出発する直前の２度コンタクトするとしている．情報 BOX
は，コンタクトしているノードがスポットに到着直後なのか，十分な時間滞在し
た後の出発直前コンタクトなのかが過去のコンタクト情報から分かるものとする.
3.3 ノードの移動モデル
本節では，実際のユーザの移動特徴を模倣したノードの移動モデルを定義する．
3.3.1 ノードの移動経路 (ノードのみが知っている情報)
各ユーザは観光スケジュールなどのように，事前に行動するスケジュールを決
めており，計画したとおりに行動すると仮定する．また，各スポットでの滞在時
9
3
500m
1.2km
表 2 経路の種類
経路
6
1.5km
650m
1
1→3→6→7→5→2→1
600m
2
1→2→5→7→6→3→1
840m
300m
1→4→2→1
1km
4
580m
1→4→7→5→2→1
7
880m
5
1→6→7→4→1
1→3→6→1
図 2 グラフ表現された地図
表 3 スポット間の移動確率の例
スポット
Box ID
Average stay
Neighboring Moving probability
time (minutes) Box ID
近鉄奈良駅
1
60
2, 3, 4, 6
1/6, 1/3, 1/3, 1/6
興福寺
2
60
1, 4, 5
3/4, 0, 1/4
東大寺
3
60
1, 6
1/3, 2/3
奈良国立博物館
4
60
1, 2, 7
1/3, 1/3, 1/3
浮見堂
5
60
2, 7
2/3, 1/3
奈良公園
6
60
1, 3, 7
1/4, 1/4, 1/2
春日大社
7
60
4, 5, 6
1/4, 1/2, 1/4
10
間も，計画したスケジュールによって決められているとする．上記に基づいて，
ユーザの経路は，表 2，図 2 に示すような一定数の予め決まったルートのどれか
とする．また，表 3 に示すように，各観光スポットにおいてあらかじめ設定され
た時間滞在するものとする．ただし，各ノードの移動予定経路や滞在時間に関す
る情報はそのノードだけが知っており，他のノードや情報 BOX は知ることがで
きないとする．
3.3.2 スポット間の移動確率と移動時間 (情報 BOX のみが知っている情報)
各スポットに存在する情報 BOX はユーザの移動予定経路を知らないが，各ユー
ザが隣接スポットに移動する確率を統計的に把握していると仮定する．BOX 間
の移動確率の例を表 3 に示す．
3.4 DTN における優先度とデッドラインを考慮したデータ配送問
題
提案手法では図 1 に示すような環境で，ノードが送信地点 SRC から，リソー
ス所在地である宛先情報源 DEST に向けてコンテンツを要求するリクエストを送
信し，リクエストに記述された情報受け取り地点 RL に到達するまでに，受信点
RL の情報 BOX が DEST の情報 BOX からコンテンツを受け取るようなシステム
を実現する．ユーザ間のデータ取得の公平性を実現するため，各ユーザに，一定
のポイントを配布する．各ユーザはリクエストを出す際，そのリクエストに対し
ポイントの一部を付与し，予定した受信地点に到達したときに，要求コンテンツ
が得られた場合，付与したポイントに相当する満足度が得られるとする．提案手
法の目標は，システム全体で達成するユーザ満足度の総和をなるべく大きくする
ことである．
11
4. 優先度とデッドラインを考慮した DTN 配送手法
本章では，3.4 節で定義したデータ配送問題を解くアルゴリズムを提案する. 提
案アルゴリズムでは，データを宛先に届けるため，情報 BOX 間のユーザ移動確
率に基づいて必要数のデータを異なるユーザに渡すことで，適切な複製数で高い
配送率を実現する.
また，配送データの満足度とデータサイズによるコストパフォーマンス (ECP，
単位データあたりの満足度) を算出し，ECP の高い配送データを優先的に配信
する．
さらに，デッドラインまでに配信されない配送データはまったく満足度が得ら
れないため，各情報 BOX は配送データを送信する前に，デッドラインまでに配
送データが間に合うかを見積もり，間に合わないと判断した配送データは受信を
拒否する．
4.1 提案手法における各ノードと情報 BOX の動作
提案手法の適用例として，奈良公園付近における観光者の口コミ情報収集アプ
リケーションを挙げる (図 1)．
ノードは近鉄奈良駅から東大寺を目指して出発する際に，
“ 東大寺大仏殿に滞
在している間に，奈良公園に関する情報を受信したい ”というリクエストを送信
する．リクエストフォーマットは表 4 の形式に従うものとする．リクエストの各
項目の内容は以下のとおりである.
上記シチュエーションで生成されるリクエストメッセージの内容は以下の通り
である．
表 4 リクエストフォーマット
SRC
DEST
RL
Deadline
• SRC(送信地点): 近鉄奈良駅
12
Satis
DataSize
Payload
• DEST(宛先情報源): 奈良公園
• RL(受信地点): 東大寺大仏殿
• Deadline(デッドライン): SRC から RL まで移動する時間，および RL での
滞在時間との和
• Satis: リクエストとリプライされるコンテンツに対する満足度 (与えられた
ポイントの一部)
• DataSize: Payload を含むメッセージ全体のサイズ
• Payload: 問い合わせ内容などを記述
4.1.1 ノードの動作
ノードの通信可能な距離に情報 BOX があれば，リクエストメッセージは自動
的に情報 BOX に転送される．情報 BOX がなければ，ノードが次の情報 BOX と
通信可能な範囲に進入するまで自身の端末に保持する．
仮定より次に訪れるスポットとそこまでの距離が分かっているので，移動速度
から次のコンタクト時間を推測し，それまでの間 Bluetooth の probe を行わず，デ
バイスをオフにすることで，電力消費を節約する.
4.1.2 情報 BOX の動作
情報 BOX はノードからリクエストを受信したとき，リクエストに記載されて
いる満足度とデータサイズに基づき，そのリクエストを叶える際に必要な複製数
n（4.2.1 節参照）を計算し，コストパフォーマンスとして，データパケットあた
りの満足度を求める．コストパフォーマンス上位のリクエストを優先的に配送す
るスケジュールを決定する．情報 BOX は配送スケジュールのリクエストを順次
配送する前に，そのリクエストが送信されてからリプライコンテンツを受信する
までの時間 t（交信時間と呼ぶ）を見積もり，配送期限を超過する見込みの場合
には，配送せずに破棄する．なお，交信時間の見積もり方法に関しては 4.2.2 節
13
で詳述する．スケジュール上位のリクエストが配送期限に間に合わないリクエス
トでなければ，その情報 BOX から出発する u 個のノードにコピーされる．
4.2 経路制御とキュー管理
4.2.1 複製数の見積もり
3 章の仮定より，情報 BOX はコンタクトしてきた各ユーザについてその移動
先を確率的にしか把握していない. そのため，リクエスト・コンテンツの到達率
を高めるために，ユーザノードに転送するデータの複製数を増やす．しかし，む
やみに複製数を増やせば，ネットワークの負荷を高め，送信できるリクエストや
コンテンツ数が減少してしまう．そこで，コストパフォーマンスの最も良いデー
タ複製数の求め方を以下で提案する．
まず，要求到達確率と期待到達確率を定義する. 本来，100%の到達率を達成
したいが，DTN による配送は宛先への到達が保障されないため不可能である.
(100%の到達を実現したい場合，無限に複製を作らなければならない.) よって本
研究では，システムに期待する宛先への到達率を要求到達確率として指定する.
提案手法では，人の統計的な移動確率を用いて，要求到達確率を満たす複製数
を計算する. しかし複製数は整数であるため，複製数と人の移動確率から計算で
きる実際の到達率は，要求到達率とは異なる値になる. 人の移動確率から要求到
達確率を満たすよう計算された複製数により達成される到達率を期待到達確率と
する.
情報 BOXBOX1 にコンタクトするノードの集合および移動確率が与えられて
いる場合，これらに基づき，ある隣接情報 BOXBOX2 への期待到達確率を要求
到達確率 δ 以上にするためのデータ複製数 n は，以下の式 (1) で計算できる．
1 − (pM ove(BOX1,BOX3)+pM ove(BOX1,BOX4)+pM ove(BOX1,BOX6))n ≥ δ
(1)
3 章で述べたように，pMove(BOX １，BOX3) は BOX1 から BOX3 まで移動す
る確率で，pMove（BOX1，BOX4)，pMove（BOX1，BOX6) は BOX1 から BOX4，
14
BOX6 へ移動する確率である．BOX1 から BOX2 以外への移動可能経路はこの 3
通りしかないため，この三つを足し合わせた確率は，BOX1 から BOX2 へ移動し
ない確率である．式 (1) に，表 3 の移動確率と δ = 0.8 を適用すると，式 (2) が得
られる．
1 − (5/6)n ≥ 0.8
(2)
複製数 n が 1 の場合，5/6 の確率で BOX2 以外のところに移動してしまうが，
複製数 n を増やすにつれ，BOX2 以外のところに移動する確率が減少する．式 (2)
を達成する n は 1 − (5/6)9 = 0.81 より，n = 9 である．このように隣接 BOX へ
の移動確率が既知の場合，特定の隣接 BOX へ到達率 δ を達成するための複製数
n を容易に求めることができる．
4.2.2 交信時間の見積もり
デッドラインの計算
各リクエストのデッドラインは，ノードがそのリクエストを生成した時点から，
受信地点 RL までの移動時間および途中で立ち寄るスポットでの滞在時間の合計
となる．各情報 BOX 間の移動時間やスポットでの平均滞在時間は仮定より予め
与えられているため，デッドラインは容易に計算できる．ノードがリクエストを
作成する際，受信地点 RL を指定すれば，携帯通信端末は現在地点 SRC と受信地
点 RL 間の最短経路の通過時間および途中で立ち寄るスポットでの平均滞在時間
から自動的に計算し (表 5 の γ)，これをデッドラインとしてリクエストに含める．
SRC
γ
RL
β
DEST
α
図 3 メッセージ配送時間の見積もり
15
表 5 時間の種類
時間の種類
値
SRC から DEST への移動に必要な時間
α
DEST から RL への移動に必要な時間
β
メッセージのデッドライン
deadline
リクエストしたノードが RL に行くまでの時間
γ
返答時間の見積もり
リクエストが SRC から DEST へ配送されるために必要な時間 (表 5 の α) は，
別のユーザにデータをキャリーアンドフォワードしてもらうので，最短では最短
経路通過時間となる．同じくコンテンツの DEST から RL への移動にかかる時間
(表 5 の β) も求められる．交信時間を t = α + β とした時，Deadline ≥ t が成り
立つ必要がある．
交信時間 t が Deadline よりも長いと予測される場合，そのリクエストは配送
期限に間に合わないリクエストとなり，廃棄する．
4.2.3 複数の情報 BOX を経由する場合のコストパフォーマンス値の計算
シングルホップのコストパフォーマンス期待値 ECP (パケット当たりの満足度)
は，満足度 (Satis)，期待到達確率 δ ′ ，データサイズ (DataSize)，データ複製数
n から式 (3) により求めることができる．
ECP = (Satis × δ ′ )/(DataSize × n)
(3)
要求到達確率 δ が高いほど，期待到達確率 δ ′ も高くなるが，その反面，δ を高
くするために，複製数 n を多くする必要があり，それによる ECP の低下が起こ
る．このため，ECP を最大にする δ と n の値の組が存在し，それを求めること
で最大のコストパフォーマンス期待値が得られる．
16
さらに，複数の情報 BOX を経由してデータを送信する際，経由した情報 BOX
の数が増加するにつれ，指数的に到達率が低下してしまう．h 個の情報 BOX を
経由すれば，以下の式 (4) のように，指数的に ECP 値が低下する．
ECP = (Satis × δ h )/(DataSize × n)
(4)
そのため，提案手法で複数ホップで到達する宛先に対しデータ配送を行う時に
は，1 ホップで到達可能な宛先に送る場合に比べ，複製数を増やす必要がある.
よって h ホップの場合の宛先への要求到達確率 δ の値を実現するための，期待到
達率 δ ′ は式 (5) で計算される.
δ ′ = (δ)(1/h)
(5)
ペナルティの計算
ホップ数の大きいデータは受信率が悪くなると考えられる．それはホップ数が
増えるほど複製数も増大するため，システム全体のパフォーマンスを下げる原因
になっているからである．よって輻輳している時は，ホップ数の大きいデータを
救済するよりも，ホップ数の大きいデータはペナルティを負わせることで優先度
を下げ，救済できる可能性の高い，ホップ数の小さいデータを優先するという仕
組みを導入する．
ホップ数の大きいデータにペナルティを負わせるため，式 (7) を導入した.
よってマルチホップの場合も考慮した，最終的な ECP の値は式 (7) によって
計算される．
penalty = −0.2 × (h − 1)2 + 1
(6)
ECP = (Satis × δ ′ )/(DataSize × n) × penalty
(7)
17
4.3 アルゴリズムの改良
前述の基本的なアルゴリズムについて予備実験を行ったところ，想定したより
もデータ到達率が悪かった．原因を分析したところ，(a) ノードから情報 BOX へ
のアップロードを優先して行っていたため，アップロードされるメッセージが大
量にある場合，情報 BOX からノードへのデータの複製 (ダウンロード) があまり
行われない; (b) ノードから情報 BOX にメッセージを複製 (アップロード) する際，
デッドラインまでに間に合うことのないメッセージもアップロードされている; と
いう２つの問題が見つかった．(a) の問題を解決するため，データ配送調整カウ
ンター機能を導入することで解決し，(b) の問題を解決するため，キューイング
遅延の推定に基づく，選択的アップロード機能を導入することで解決を行った．
4.3.1 データ配送調整カウンター機能
いま，情報 BOX からノードへダウンロードさせたいデータ，ノードから情報
BOX へアップロードしたデータが複数存在する場合を考える. この時ダウンロー
ド，あるいはアップロードのみを優先した場合，ダウンロードを優先させた時は
アップロードが，アップロードを優先させた時はダウンロードが十分に行えない
ため，データ到達率が低くなり，システム全体の性能が低下する．公平なデータ
配送を行うためには，アップロードされるデータ量とダウンロードされるデータ
量の関係は，n を要求到達確率を満たす複製数とした時，式 (8) を満たさなけれ
ばならない．
アップロードされるデータ量 : ダウンロードされるデータ量 = 1 : n
(8)
よって，図 4 のようなカウンター機能を設けることで，式 (8) の関係を保つこ
ととした．
図 4 のフローチャート中で使用される記号の意味は次のようになる.
Box.ULCounter 情報 BOX におけるアップロードカウンター. ノードから情報
BOX へ送信されたデータのバイト数.
18
no
yes
Box.ULCounter>
Box.DLCounter
UL
DL
ノードから情報BOXに
メッセージを送信
情報BOXからノード
からノードに
ノードに
メッセージを送信
メッセージのサイズx複製数を
Box.ULCounter に加算
メッセージのサイズx複製数を
複製数を
Box.DLCounterに加算
図 4 データ配送調整カウンター機能
Box.DLCounter 情報 BOX におけるダウンロードカウンター. 情報 BOX が
ノードから受信したデータのバイト数.
図 4 のフローチャートの動作は次のとおりである.
(1) アップロードカウンターがダウンロードカウンターよりも大きい場合
(a) 情報 BOX からノードへメッセージを送信 (ダウンロード) する.
(b) 情報 BOX のダウンロードカウンターを送信したメッセージのバイト
数分加算する.
(2) ダウンロードカウンターがアップロードカウンターよりも大きい場合
(a) ノードから情報 BOX へメッセージを送信 (アップロード) する.
(b) 情報 BOX のアップロードカウンターを送信したメッセージのバイト
数分加算する.
4.3.2 キューイング遅延の推定に基づく選択的アップロード
ノードから情報 BOX にメッセージを複製する際，デッドラインまでに間に合
うことのないメッセージの送信 (アップロード) も行ってしまう問題を解決するた
めに，アップロードする前に，予めアップロードしたいメッセージのサイズ，重
19
要度，デッドライン，RL が含まれた情報を情報 BOX に送信する. 情報 BOX は，
この情報を使って，アップロード要求のあったデータ (D1 とする) のキューイング
遅延を，後に述べる方法で予測する．予測したキューイング遅延とそれ以降の配
送遅延を足した時間が D1 のデッドラインを超えない場合には，D1 のアップロー
ドにより，情報 BOX のキューに既に存在する他のデータがデッドラインを満た
せなくなるかどうかを調べる．そのようなデータが無い場合には，D1 のアップ
ロードを許可する．そのようなデータが存在する場合には（D2 とする），D1 と
D2 の重要度を比較し，D1 の方が大きい重要度を持つ場合に限りアップロードを
許可する．以上の機構により，デッドラインに間に合わないデータのアップロー
ドによる帯域消費の無駄を削減する．このキューイング遅延の推定に基づく選択
的アップロードを実現するアルゴリズムを Algorithm1 として示す．
Algorithm 1 キューイング遅延の推定に基づく選択的アップロード
1: U lSet: アップロード要求のあるデータの集合
2: sendQ: 情報 BOX の送信キュー (ECP の値で順位付けされた優先順位付き
キュー)
3: while U lset ̸= ϕ do
4:
UlSet 内で最も重要度の高いメッセージを D1 として取り出す
5:
sendQ をコピーし，sendQcp を作成
6:
sendQcp に D1 を挿入
7:
sendQcp 内の各メッセージに対してキューイング遅延を考慮したデッドラ
インの判定を行い，デッドラインをオーバーするメッセージの集合 D2 を
計算
8:
if D2 の各メッセージの重要度の総和 > D1 の重要度 then
D1 を廃棄
9:
10:
11:
12:
else
D1 のアップロードを開始
end if
13: end while
7 行目のキューイング遅延を考慮したデッドラインの計算方法について，図 5 を
20
用いて解説する．今，情報 BOX に毎秒 k 個のノードがコンタクトを開始するとす
る．また，情報 BOX にコンタクトしている全ノードが持つアップロードしたメッ
セージの集合を，U lSet = {S1 · · · Sk } とする．(S1 · · · Sk は，この順に重要度が高
い) さらに，情報 BOX が複製したいメッセージの集合を sendQ = {m1 · · · mn } と
する．(m1 · · · mn は，この順に複製する優先度が高い) メッセージ mi のデッドラ
インを mi .deadline，メッセージの大きさを mi .size，複製数を mi .cpnum，重要
度を mi .prio とする．また，ノードのコンタクト時間 (sec) を ContactT ime，ノー
ドと情報 BOX が共有する伝送容量を BW c(bit/sec)，情報 BOX における平均コ
ンタクト回数を k(回/sec) とすると，sendQ に存在するメッセージ mi がノードへ
の送信を完了するまでに必要とする時間 ti の見積もりを式 (9)，(10) に示す．
t1 = (m1 .size ∗ m1 .cpnum)/(k ∗ ContactT ime ∗ BW c)
(9)
i≥2
ti =
i−1
∑
tj + (mi .size ∗ mi .cpnum)/(k ∗ ContactT ime ∗ BW c)
(10)
j=1
情報BOXのsendQ
UlSet
S1
S2
・・・
m1
Sk
m2
人秒
k( / )
情報BOX
・
・
E
・E
E
mn
図 5 キューイング遅延の推定に基づく選択的アップロード機能
さらに，メッセージ mi の，宛先までの最短経路の通過時間を ShortestP athCost(mi )(情
報 BOX は各情報 BOX 間の移動時間が与えられているため，簡単に導出できる)
とすると，メッセージを受信せずに拒否するかどうかの判定式は式 (11) となる．
ti + ShortestP athCost(mi ) > mi .deadline
これまでに述べたようにして，7 行目では Set1 を計算する．
21
(11)
5. 実験
提案手法により，ユーザ全体の満足度をどの程度高めることができるかを評価
するために，対象サービスエリアとしてマンハッタンモデルを用いたシミュレー
ション実験を行った. シミュレーションは，Java 言語で自作したシミュレータを
用いて行った.
負荷が大きくても提案手法が有効に動作することを確認するために，リクエス
トするデータサイズの組み合せを様々な値に変更し，シミュレーションを行った．
5.1 実験設定
今回の実験に Java 言語で自作のネットワークシミュレータを使用した. シミュ
レータの様子を図 6 で示す. グラフィック機能により，データの運搬過程や情報
BOX の輻輳状況を視認できる. (6 の，黄色の帯が輻輳メッセージ数を表現し，赤
の帯が受信データ数を表現している.)
図 6 シミュレーションの様子
22
本研究は Bluetooth を利用した通信を想定したため，Bluetooth の通信モデル
を使用した．具体的な設定を表 6 に示す．
表 6 シミュレーションの設定
有効通信半径
帯域
10m
1Mbps
隣接スポット間の距離
300m
リクエストサイズ
1KB
要求コンテンツサイズ
100KB (50%)
200KB · · · 1000KB(50%，100KB の倍数)
10 · · · 100(10 の倍数)
リクエストに付与されるポイント
シミュレーション時間
約 18 時間
リクエスト投稿開始時刻
開始 6 時間後
リクエスト投稿終了時刻
開始 12 時間後
アクティブな端末数
約 3000
ノードの移動速度
1m/s
ノードの移動方法
事前設定された経路
ノードの移動モデルや，情報 BOX に関する設定は 3 章で述べたものと同じも
のを使用した．ノードは，平均到着間隔 60 秒のポアソン到着に従って，各々のス
ケジュールのスタート地点から，各スポットの巡回を開始する．そして各スポッ
トに到着する度に，そのスポットで決められた時間滞在し，これをゴール地点ま
で繰り返す．今回の実験では，ノードは各スポットで 60 分間滞在する. 各スポッ
トに存在する情報 BOX へのコンタクトタイム (ContactTime) は，図 7 のように，
利用者が各スポットへの入り口を通過する時間として見積もっている．このコン
タクトタイムは式 (12) に従って計算する．
ContactT ime =
無線半径 × 2
人の速度
(12)
このコンタクトタイムが，1 つのスポットにつき，到着したときと出発すると
23
ContactTime
InfoBox
r
r
Entrance
図 7 コンタクトタイム
きの２回発生するものとする．すなわち，今回のシミュレーション設定では，到
着時に 20 秒，出発時に 20 秒，合計 40 秒間通信可能と想定した (コネクションの
確立や，ピコネットの形成にかかる時間を考慮しない)．また，3.2 節の仮定より，
情報 BOX はノードのコンタクトがスポットに到着したときに発生したものか，ス
ポットを出発する直前に発生したものかを知ることができる．今回の実験では，
スポットを出発直前のノードのみにリプライを配布している.
各ユーザがリクエストに与える満足度ポイントは初期の保持ポイントを 100 と
し，リクエストを送信するたびに，保持ポイントの範囲内で 10 の倍数としてラ
ンダムに与えるものとした. また，ゴール地点に到着するまでに 100 ポイントを
使い切るものとする (スタート前に，100 のポイントを使い切るようなリクエスト
を計算して求めておく). また，リクエストに対するリプライのデータサイズは，
50%の確率で 100KB，50%の確率で kKB となるようにした. 今回の実験では，k
は 200KB から 1000KB まで，100KB 刻みで変更した. こうすることで，サイズが
小さく満足度の高いコストパフォーマンスの良いリクエスト，サイズが大きく満
足度の低いコストパフォーマンスの悪いリクエストが混在する状況を生成した．
シミュレーション開始直後は，ユーザがエリア上に存在していないため，ユー
ザの運搬によるデータ配送がおこなえない. よって表 6 に示すように，リクエスト
投函開始時刻とリクエスト投函終了時刻を設定し，十分に時間が経過し，ノード
24
がエリア上に十分にいきわたった状態でリクエストの開始を行った. シミュレー
ションはこの間に投函されたリクエストのデッドラインが終了するまで行う. 終
了する時刻は，およそ開始から 18 時間後である.
ノードは各々に設定されたスケジュールに従った移動と，スポットでの待機を
行う. スケジュール別に考えると，スタート地点のスポットから，60 秒を平均到
着間隔とするポアソン到着で出発 (スタート) し，スケジュールの終点のスポット
でゴールする. シミュレーション実行中に，エリア内でスタートしており，かつ
ゴールしていないユーザの数をアクティブな端末数としている. 表 6 のアクティ
ブ端末数は，シミュレーション実行中に 10 秒間隔で計測した際の平均値である.
式 (9)，(10) で，各情報 BOX は，平均コンタクト回数 k を計算しなければなら
ない. 今回の実験では，各々の情報 BOX でコンタクトが開始された数をカウン
トし，180 秒間隔で平均コンタクト数の更新を行った.
5.1.1 サービスエリア
シミュレーションで用いたサービスエリアとスポット，スポット間の移動経路
を図 8 に示す．
1
2
3
4
5
6
7
8
9
300m
300m
図 8 サービスエリアにおけるスポット間移動経路
25
5.1.2 比較対象
提案手法の比較対象として，コストパフォーマンスを考慮しない以下の 3 つの
方式を使用した．
FIFO データの到着順で配送する方式
deadline デッドラインの短い順に配送する方式
satisfaction 満足度が高い順に配送する方式
5.1.3 複数の環境の用意
提案手法を網羅的に評価するためには，異なる複数の環境で評価することが望
ましい. トポロジ，ノード数，リクエストの数，さまざまなパラメタが存在する.
今回はユーザの移動スケジュールを変化させることで，複数の環境を作ることに
した.
ユーザの移動スケジュールの組み合わせは，表 7 の (a)∼(d) に示す通りに４パ
ターン用意した. このユーザスケジュールは図 8 に示すとおりのスポットと道の
データから，ランダムに出発スポットを選択し，決められたスポットの数を経由
することで作成した. ユーザの移動スケジュールを変化させると，各情報 BOX
に与えられる移動確率も変化するため，提案手法および比較対象の結果も変化す
る. 網羅的な実験を行うため，ユーザの移動スケジュールを変化させることで４
つの異なる環境を作り，各環境で実験を行った.
5.1.4 評価結果
リプライのデータサイズ２種類を 100KB:200KB から 100KB:1000KB まで，100KB
づつ変化させながら実験を行った. また，それぞれのリプライサイズの組毎に 10
回実験を行う実験を１セットとして，ユーザの移動スケジュールの組み合わせを
変化させることで，同様の実験を計４セット行った. ４セットの実験セットの平
均メッセージ取得成功率および１人あたりのユーザ満足度の平均値を取得した
26
表 7 ユーザのスケジュールの組み合わせ
(a)
(b)
(c)
(d)
Route
Route
Route
Route
6-3-2-5-8-9
3-2-1-4-7-8
7-4-1-2-5-6
1-2-3-6-5-8
9-6-5-8-7-4
3-2-5-6-9-8
7-4-1-2-3-6
7-8-5-4-1-2
8-5-4-1-2-3
3-2-1-4-7-8
9-8-5-2-3-6
1-2-3-6-5-8
2-1-4-5-8-9
3-2-1-4-5-8
5-8-7-4-1-2
1-2-3-6-9-8
2-3-6-5-8-9
4-1-2-3-6-5
5-4-1-2-3-6
5-8-7-4-1-2
6-3-2-1-4-5
6-9-8-5-2-1
8-5-4-1-2-3
7-8-9-6-3-2
4-5-8-9-6-3
6-3-2-5-4-7
4-1-2-5-6-3
3-2-1-4-5-6
9-8-7-4-5-6
9-6-3-2-5-4
6-9-8-5-4-1
6-3-2-5-4-1
6-3-2-5-8-7
2-1-4-5-6-3
5-4-1-2-3-6
8-7-4-1-2-5
8-5-2-1-4-7
3-6-9-8-7-4
9-6-5-8-7-4
9-6-3-2-1-4
(図 9，図 10). ここでメッセージ取得成功率とは，RL で受信されるリプライの数
/SRC で投稿される全リクエストの数 であり，１人あたりのユーザ満足度とは，
100 ポイントを与えられたユーザが得られた満足度の値である (最大値は 100).
全環境での平均メッセージ取得成功率を図 9，全環境での平均ユーザ満足度を
図 10 に示す.
図 9 より，リプライのデータ量が増加し，ネットワークに与える負荷が大きく
なり，輻輳状況が悪化するほど，どの手法も到達率が下がっている. しかし提案
手法 (proposed) は，100KB:200KB の時は 25%，100KB:1MB のときは 10%程度，
他の手法よりも優れていることが確認できる.
また，図 10 より，輻輳状況が悪化するほど，どの手法も得られる満足度が下
がっていく様子が確認できる. しかし提案手法は，100KB:200KB の時は 50%，
100KB:1MB のときは 20%程度，他の手法よりも優れていることが確認できる.
27
28
request size set
図 10 全ての環境における平均ユーザ満足度
100KB:1MB
75
100KB:1MB
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Recieve Rate(SRC-RL)
0.75
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Satisfaction Per Person
0.8
FIFO
proposed
deadline
satisfaction
0.7
0.65
0.6
0.55
0.5
0.45
0.4
request size set
図 9 全ての環境における平均メッセージ取得成功率
80
FIFO
proposed
deadline
satisfaction
70
65
60
55
50
45
40
5.1.5 環境の違いによる詳細な評価
４つの環境において，それぞれの環境別の評価を行った. 移動スケジュールの
組み合わせにより，人の往来が集中する情報 BOX や，頻繁にリプライデータを
受信する情報 BOX ができる. (図 8 では，中央のスポット (id:5) は人の往来が集
中しやすいため，データの送受信が頻繁に行われ，大きな輻輳が起こりやすい)
その影響を反映して，到達率や満足度の性能は環境毎に異なる結果となった.
メッセージ取得成功率に関する評価
(a)∼(d) の各環境のメッセージ取得成功率の平均値と最大，最小を記したもの
を図 11 として示す．どの環境においても，提案手法と他の手法の傾向は，平均的
な評価結果である図 9 と同様の傾向があることが確認できる.
29
0.7
FIFO
proposed
deadline
satisfaction
0.85
0.8
0.55
0.75
0.5
0.45
0.4
0.35
0.3
0.5
0.25
0.45
0.2
0.4
request size set
request size set
(c)
(d)
図 11 各環境における平均メッセージ取得成功率
30
100KB:1MB
(a)
100KB:1MB
100KB:900KB
100KB:800KB
0.8
100KB:900KB
request size set
100KB:800KB
0.35
100KB:700KB
0.4
100KB:700KB
0.4
100KB:600KB
0.45
100KB:600KB
0.45
100KB:500KB
0.5
100KB:500KB
0.55
100KB:400KB
0.6
100KB:400KB
0.65
100KB:300KB
0.8
100KB:300KB
0.7
Recieve Rate(SRC-RL)
0.75
100KB:200KB
100KB:1MB
FIFO
proposed
deadline
satisfaction
100KB:200KB
0.6
Recieve Rate(SRC-RL)
0.65
100KB:1MB
0.85
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Recieve Rate(SRC-RL)
0.9
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Recieve Rate(SRC-RL)
0.95
0.85
FIFO
proposed
deadline
satisfaction
0.75
0.7
0.65
0.6
0.55
0.5
request size set
(b)
0.9
FIFO
proposed
deadline
satisfaction
0.7
0.65
0.6
0.55
ユーザ毎の満足度に関する評価
(a)∼(d) の各環境のユーザ毎の得られた満足度の平均値と最大，最小を記した
ものを図 11 として示す．どの環境においても，提案手法と他の手法の傾向は，平
均的な評価結果である図 10 と同様の傾向があることが確認できる. 提案手法の
比較手法のなかでは，どの環境でも，もっとも輻輳している状況 (100KB:1MB)
において，satisfaction が最も高い満足度を達成している.
31
request size set
(a)
(b)
80
FIFO
proposed
deadline
satisfaction
90
85
50
40
30
10
request size set
request size set
(c)
(d)
図 12 各環境におけるユーザ満足度
32
100KB:1MB
100KB:1MB
80
100KB:900KB
85
100KB:900KB
request size set
100KB:800KB
35
100KB:800KB
40
100KB:700KB
40
100KB:700KB
45
100KB:600KB
45
100KB:600KB
50
100KB:500KB
50
100KB:500KB
55
100KB:400KB
60
100KB:400KB
65
100KB:300KB
70
Satisfaction Per Person
75
100KB:200KB
80
100KB:300KB
60
Satisfaction Per Person
100KB:1MB
Satisfaction Per Person
FIFO
proposed
deadline
satisfaction
100KB:200KB
70
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
85
100KB:1MB
Satisfaction Per Person
90
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
95
90
FIFO
proposed
deadline
satisfaction
75
70
65
60
55
95
FIFO
proposed
deadline
satisfaction
80
75
70
65
60
55
20
50
45
40
5.1.6 提案手法の改良機能の効果
提案手法に加えたメッセージ取捨選択機能がどの程度効果があったかを確認す
る. 以下の３つの方式の比較を行った.
Selection: Algorithm1 を用い，アップロードされるデータを取捨選択する方式
Upload: ノードから情報 BOX へのアップロードを優先する方式.
Counter: 図 4 の，アップロードとダウンロードを 1 : n(複製数) に保つ方式
なお，上述の方式のキュー管理はすべて ECP の値順とする.
メッセージ取得成功率の結果
(a)∼(d) の各環境毎のメッセージ取得成功率を図 13 に示す．どの環境において
も，各手法の関係は，同様の傾向があることが確認できる. 特にもっとも輻輳の
状況が軽い (100KB:200KB) のとき，Selection は他の手法よりも 20%程度優れて
いる. この結果は，アップロードされる候補のなかからデッドラインに間に合う
ものを選択し，帯域を有効に使用する効果だと考えられる.
また，輻輳の状況が悪化するほど，Selection は取得成功率は下がっていき，
(100KB:1MB) では，他の手法との差は小さくなる. これは，Selection も他の手
法も，100KB のリプライは宛先に送ることできているが，サイズを変動させてい
るもう一方の k(200 ≤ k ≤ 1000)KB のリプライが，徐々に届けられなくなりつつ
ある結果だと考えられる.
さらに，今回 Counter と Upload の差がほとんどなかったが，これはアップロー
ドの過負荷が小さかったためだと考えられる. もしノードの運搬するデータ複製
量が，情報 BOX へのコンタクトタイム (到着時の 20 秒と出発時の 20 秒で 40 秒)
で送信しきれない量だった場合，Selection と Upload の性能はより悪化したと考
えられる.
33
proposed(Selection)
proposed(Counter)
proposed(Upload)
0.85
0.6
0.5
0.45
0.4
0.35
0.3
0.55
0.25
0.5
request size set
request size set
(c)
(d)
図 13 各環境における平均メッセージ取得成功率
34
100KB:1MB
0.7
100KB:900KB
(a)
100KB:1MB
100KB:900KB
100KB:800KB
0.8
100KB:800KB
request size set
100KB:700KB
0.4
100KB:700KB
0.45
100KB:600KB
0.45
100KB:600KB
0.5
100KB:500KB
0.55
100KB:500KB
0.6
100KB:400KB
0.65
100KB:400KB
0.7
100KB:300KB
0.75
100KB:200KB
0.8
Recieve Rate(SRC-RL)
0.85
100KB:300KB
0.55
Recieve Rate(SRC-RL)
100KB:1MB
100KB:900KB
proposed(Selection)
proposed(Counter)
proposed(Upload)
100KB:200KB
100KB:1MB
100KB:900KB
0.65
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Recieve Rate(SRC-RL)
0.9
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
Recieve Rate(SRC-RL)
0.95
0.85
proposed(Selection)
proposed(Counter)
proposed(Upload)
0.75
0.7
0.65
0.6
0.55
0.5
request size set
(b)
0.9
proposed(Selection)
proposed(Counter)
proposed(Upload)
0.8
0.75
0.7
0.65
0.6
ユーザ毎の満足度の結果
(a)∼(d) の各環境毎のメッセージ取得成功率を図 14 として示す．どの環境にお
いても，各手法の関係は，同様の傾向を示していることが確認できる. 図 13 の到
達率の関係と似ているが，これは到達率が高いほど，得られる満足度も高くなる
ためである.
しかし，100KB:1MB のとき，満足度は 5∼10%程度の差があり，図 13 の到達
率のときよりよりも若干他の手法よりも優れている様子が確認できる.
これは，Algorithm1 の，情報 BOX にコンタクトしているノードが持つ複製デー
タの候補の中で，最も満足度が高いデータを選択して受信する機能の効果だと考
えられる.
35
(b)
75
proposed(Selection)
proposed(Counter)
proposed(Upload)
65
90
55
50
45
40
35
30
55
25
50
request size set
request size set
(c)
(d)
図 14 各環境におけるユーザ満足度
36
100KB:1MB
(a)
100KB:900KB
request size set
100KB:1MB
100KB:900KB
100KB:800KB
100KB:700KB
85
100KB:800KB
request size set
100KB:700KB
40
100KB:600KB
50
100KB:600KB
45
100KB:500KB
55
100KB:500KB
60
100KB:400KB
65
100KB:400KB
70
100KB:300KB
75
Satisfaction Per Person
80
100KB:200KB
Satisfaction Per Person
85
100KB:300KB
60
Satisfaction Per Person
100KB:1MB
100KB:900KB
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
proposed(Selection)
proposed(Counter)
proposed(Upload)
100KB:200KB
100KB:1MB
70
100KB:900KB
Satisfaction Per Person
90
100KB:800KB
100KB:700KB
100KB:600KB
100KB:500KB
100KB:400KB
100KB:300KB
100KB:200KB
95
90
proposed(Selection)
proposed(Counter)
proposed(Upload)
80
75
70
65
60
55
50
95
proposed(Selection)
proposed(Counter)
proposed(Upload)
85
80
75
70
65
60
6. 結論
本論文では，PDA や携帯電話などの Bluetooth 使用端末を所持したモバイル
ユーザが，情報 BOX を経由して情報を共有するための，データの優先度と配送
期限を考慮した DTN 経路制御手法を提案した．提案手法は，
（1）情報 BOX はリ
クエストの満足度，及びそれを達成するために必要なデータ複製量からコストパ
フォーマンスを計算し，コストパフォーマンスの高いデータを優先的に配信する
よう情報 BOX でキュー管理を行う，
（2）送信キューのデータ量とユーザによる
データの運搬速度に基づき，配信期限に間に合わないと見積もったデータを廃棄
する．
（3）情報 BOX はユーザから搬送されるデータを受信する前に，そのデー
タが配送期限に間に合う可能性を見積り，間に合わない場合，データの受信を拒
否することで，帯域負担を軽減する，などの工夫により，従来の研究では達成さ
れていなかった，DTN での重要度と配送期限を考慮したデータ転送を実現して
いる.
提案手法を典型的なマンハッタンモデルを想定したエリアサイズ 600mx600m
に携帯端末数約 3000 台が常に動き回っている場合について, 提案手法と FIFO な
どの他の手法との比較実験を網羅的に行った．リプライのサイズを変更させるこ
とでネットワークに与える負荷を変化させたところ, 提案手法はメッセージ配送
率が比較相手よりも 10%から 25%程度優れていることを確認した. また，満足度
においても，比較相手よりも 20%から 50%程度優れていることを確認した.
一方，提案手法の実用化に向けて以下の課題が挙げられる．第一に，より現実
的な条件においてシミュレーション実験を行う必要がある. 例として，現実の観
光地や, かつて災害が発生した地域などの地図を用い，モビリティや端末密度をそ
れに合わせ，所々に情報 BOX を配置した状況を扱ったシミュレーションがある.
第二に，実機に実装して実証実験を行うことが挙げられる. 本研究はコンピュー
タシミュレーションのみの評価であったが，実機への実装はシミュレーションで
は扱いきれない事象に対して，如何に提案手法が機能するかを評価することがで
きる.
37
謝辞
本研究を進めるにあたり，暖かい御指導および御助言を頂いた伊藤実教授に，
心より感謝いたします．
山口英教授には，御多忙の中に関わらず論文審査委員を引き受けて頂き，貴重
なご意見を賜りました．心より感謝致します．
安本慶一准教授には，本研究を進めるにあたり，熱心な御指導および御助言を
頂きました．厚く御礼申し上げます．
孫為華助教には，本研究を進めるにあたり，数多くの御助言，御指導を頂きま
した．厚く御礼申し上げます．
最後に，学生生活を通じて御世話になった本学ソフトウェア基礎学講座の皆様
に御礼申し上げます．
38
参考文献
[1] Banerjee, N., Corner, M. D. and Levine, B. N.: An Energy-Efficient Architecture for DTN Throwboxes, In Proc. IEEE INFOCOM, pp. 776–784
(2007).
[2] Burgess, J., Gallagher, B., Jensen, D. and Levine, B. N.: MaxProp: Routing
for Vehicle-Based Disruption-Tolerant Networks, In Proc. IEEE INFOCOM,
pp. 1–11 (2006).
[3] Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R. and Scott, J.:
Impact of Human Mobility on Opportunistic Forwarding Algorithms, IEEE
Transactions on Mobile Computing, pp. 606–620 (2007).
[4] DTN Research Group: http://www.dtnrg.org/.
[5] Fall, K.: A delay-tolerant network architecture for challenged internets, In
Proc. the 2003 conference on Applications, technologies, architectures, and
protocols for computer communications(SIGCOMM ’03), pp. 27–34 (2003).
[6] Floyd, S. and Jacobson, V.: Random Early Detection Gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, Vol. 1, pp. 397–
413 (1993).
[7] Hui, P., Chaintreau, A., Scott, J., Gass, R., Crowcroft, J. and Diot, C.:
Pocket switched networks and human mobility in conference environments,
In Proc. the 2005 ACM SIGCOMM workshop on Delay-tolerant networking(WDTN ’05), pp. 244–251 (2005).
[8] Jain, S., Fall, K. and Patra, R.: Routing in a delay tolerant network, In Proc.
the 2004 conference on Applications, technologies, architectures, and protocols for computer communications(SIGCOMM ’04), pp. 145–158 (2004).
39
[9] Jones, E. P. C., Li, L. and Schmidtke, J. K.: Practical Routing in DelayTolerant Networks, IEEE Transactions on Mobile Computing, Vol. 6, No. 8,
pp. 943–959 (2007).
[10] KioskNet.: http://blizzard.cs.uwaterloo.ca/tetherless/index.php/KioskNet/.
[11] Seligman, M., Fall, K. and Mundur, P.: Storage routing for DTN congestion
control, Research Articles, Wireless Communications and Mobile Computing,
Vol. 7, No. 10, pp. 1183–1196 (2007).
[12] Shah, R. C., Roy, S., Jain, S. and Brunette, W.: Data MULEs: Modeling
a Three-tier Architecture For Sparse Sensor Networks, In Proc. IEEE International Workshop on Sensor Network Protocols and Applications(SPNA
’03), pp. 30–41 (2003).
[13] Spyropoulos, T., Psounis, K. and Raghavendra, C. S.: Spray and Wait: An
Efficient Routing Scheme for Intermittently Connected Mobile Networks,
In Proc. the 2005 ACM SIGCOMM workshop on Delay-tolerant networking(WDTN ’05), pp. 252–259 (2005).
[14] The Haggle project.: http://www.haggleproject.org.
[15] The TIER project.: http://tier.cs.berkeley.edu/.
[16] The Wizzy project.: http://www.wizzy.org.za/.
[17] UMassDieselNet.: http://prisms.cs.umass.edu/dome/.
[18] Vahdat, A. and Becker, D.: Epidemic Routing for Partially-Connected Ad
Hoc Networks, Technical report cs-2000-06.
[19] Wang, M. and Nahrstedt, K.: SOCIAL STRUCTURE BASED ROUTING OF INTERMITTENTLY CONNECTED NETWORK USING CONTACT INFORMATION, In Proc. IEEE Military Communications Conference, 2008(MILCOM ’08), pp. 1–7 (2008).
40
[20] Wang, Y., Jain, S., Martonosi, M. and Fall, K.: Erasure-coding based routing
for opportunistic networks, In Proc. the 2005 ACM SIGCOMM workshop on
Delay-tolerant networking(WDTN ’03), pp. 229–236 (2005).
[21] Yu, X. and Chandra, S.: Delay Tolerant Collaborations among CampusWide Wireless Users, In Proc. IEEE INFOCOM, pp. 2101–2109 (2008).
[22] Zhang, G., Wang, J. and Liu, Y.: Congestion management in delay tolerant networks, In Proc. the 4th Annual International Conference on Wireless
Internet(WICON ’08) (2008).
[23] Zhao, W., Ammar, M. and Zegura, E.: A Message Ferrying Approach for
Data Delivery in Sparse Mobile Ad Hoc Networks, In Proc. the 5th ACM international symposium on Mobile ad hoc networking and computing(MobiHoc
’04), pp. 187–198 (2004).
[24] Zhao, W., Chen, Y., Ammar, M., Corner, M., Levine, B. and Zegura, E.:
Capacity Enhancement using Throwboxes in DTNs, In Proc. IEEE Intl Conf
on Mobile Ad hoc and Sensor Systems (MASS ’06), pp. 31–40 (2006).
41