論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2

D2

アドホックネットワークにおける更新データ配布方式
Updated Data Dissemination Methods inAd Hoc Networks

林 秀樹†

原 隆浩‡

Hideki HAYASHI
Shojiro NISHIO

Takahiro HARA

In this paper, we propose two updated data
dissemination methods to update old replicas effectively
in ad hoc networks where each data item is updated. In
the first method, when a mobile host holding an original
data item updates the data item, it disseminates theupdated data item to all connected mobile hosts. In theother method, when two mobile hosts are connected, theyre-disseminate updated data items.

1. はじめに近年，ルータ機能をもつ移動体のみで一時的なネットワークを形成するアドホックネットワークに関する研究への関心が高まっている[1][2][3]．アドホックネットワークでは，移動体の移動によってネットワークが分断された場合に，分断された部分ネットワーク内のデータに対してアクセスできないため，データの利用性が低下してしまう[4][5]．例えば，図1のアドホックネットワークにおいて，中央の2 台の移動体間の無線リンクが切断されたとすると，左側の3台の移動体はデータD2に，右側の3台の移動体はデータD1にアクセスできなくなる．この問題を解決する手法として，オリジナルデータをもつ移動体とは別の移動体に，データの複製を配置することが有効である．
筆者らは文献[6]において，データ更新が発生しないアドホックネットワークを想定して，移動体が限られたキャッシュ領域にデータの複製を配置する方式を提案した．一方，実環境では，データ更新が発生することが一般的である．このような環境では，移動体が更新発生後の古い複製（キャッシュデータ）にアクセスする可能性がある．古い複製へのアクセスは，オリジナルをもつ移動体と再接続した際に，必要に応じてロールバックされる．このような無駄なデータアクセスやロールバック処理は，消費電力が重要な問題となる移動体

学生会員 大阪大学大学院情報科学研究科マルチメディ
ア工学専攻 hideki@ist.osaka-u.ac.jp‡ 正会員 大阪大学大学院情報科学研究科マルチメディア
工学専攻 {hara,nishio}@ist.osaka-u.ac.jp

1

D1

西尾 章治郎‡

本論文では，データ更新が発生するアドホックネットワー
クにおいて，古いキャッシュデータを効率的に更新するために，各移動体が更新データを配布する二つの方式を提案する．
一つめの方式では，移動体がデータを更新した際に，その移動体と相互接続している移動体に更新データを配布する．二つめの方式では，ある二つの移動体が新たに接続した際に，更新データを再配布する．

†切断
図1

ネットワークの分断Fig.1

Network division.

計算環境では好ましくない場合がある．そこで，筆者らは，
文献[7]において，データ更新が発生するアドホックネットワ
ークを想定し，移動体が無効化情報を放送することで，古い複製を効果的に無効化する方式を提案した．しかし，これらの方式では，古い複製を効率的に無効化できるが，データアクセスの成功率は向上できなかった．そこで，本論文では，古い複製へのアクセス回数の削減とデータアクセスの成功率の向上を目的として，各移動体が更新データを配布することで，古い複製を効率的に更新する方式を提案する．
以下では，2章で想定環境について述べる．3章で本論文で提案する更新データ配布方式について述べる．4章で提案方式の性能評価のために行ったシミュレーション実験の結果を示す．最後に5章で本論文のまとめを述べる．

2. 想定環境
本論文では，データ更新が発生するアドホックネットワー
クにおいて，他の移動体のもつデータにアクセスする環境を想定する．各移動体は，自身のキャッシュ領域に，他の移動体がオリジナルとしてもつデータの複製を作成し，複製を一定の周期（再配置周期）で再配置する．複製を再配置する際には，筆者らが文献[6]において提案した DCG (DynamicConnectivity based Grouping) 方式を用いる．DCG 方式では，再配置周期ごとに安定度の高い移動体のグループを作成し，グループ内で複製を共有する．2 連結成分を一つのグループにしているため，任意の一つの移動体がネットワークから離脱してもグループは分断されない．
移動体のデータアクセスは，オリジナルにアクセスした場合，もしくはオリジナルと同じタイムスタンプ（バージョン）をもつ複製にアクセスした場合にのみ成功とみなし，オリジナルと異なるタイムスタンプをもつ古い複製にアクセスした場合は失敗とみなす．アクセス要求は，自身もしくは相互接続している移動体が，アクセス対象のオリジナルをもつ場合，即座に成功する．なお，本論文において，相互接続している移動体とは，1 ホップ以上の無線リンクで相互に通信可能な移動体の集合を指す．自身もしくは相互接続している移動体が，アクセス対象のオリジナルをもたず，複製のみをもつ場合，その複製に対して暫定的にアクセスする．ここで，複数の移動体がアクセス対象の複製をもつ場合には，最も新しい複製をもつものに暫定的にアクセスする．暫定的なアクセスは，後にオリジナルをもつ移動体と相互接続した際に，成功か失敗かが決定する．暫定的なアクセスが失敗となった
場合は，必要に応じてロールバック処理を行う．一方，自身もしくは相互接続している移動体がアクセス対象のオリジナルや複製を保持していない場合，アクセス要求は即座に失敗する．

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
表 1 メッセージの要素
Table 1 Elements of messages.
メッセージ名要素

無効化情報
更新データ問合せ
更新データ返信

データ ID，TS
移動体 ID，データ ID リスト
移動体 ID，データ ID リスト

想定環境のその他の詳細を以下に示す．
m 個の移動体（識別子：M1,M2,…,Mm）が存在し，各々が自由に移動する．
n 個のサイズの等しい異なるデータ（識別子：D1,D2,…,Dn）が存在し，各々が特定の移動体にオリジナルデータとして保持されている．
各移動体 Mi(i=1,…,m)は，自身のもつオリジナルデータ以外に，データ C 個分のキャッシュ領域をもち，そこに複製を作成する．
各データは，そのオリジナルをもつ移動体によって更新される．更新発生後，古い複製は無効なものとなる．
各移動体は，ネットワーク内に存在する各データの最近の更新時刻（タイムスタンプ）を保持する．この情報を記録する表をタイムスタンプ表と呼ぶ．

3. 更新データの配布
前章で述べた想定環境において，古い複製へのアクセス回数の削減とデータアクセスの成功率の向上を目的として，各移動体が更新データを配布する方式を提案する．以下では，提案する二つの方式について説明する．表1に，提案方式において用いるメッセージを示す．表中のIDは識別子，TSはタイムスタンプを表す．

3.1

DU (Dissemination on Update) 方式

DU 方式では，オリジナルデータをもつ移動体がそのデータに対して更新を行ったとき，まず文献[7]の方式と同様に，自身と相互接続している移動体に無効化情報を放送する．無効化情報を受信した各移動体は，自身のタイムスタンプ表を参照して，自身のもつ複製が無効かどうかを判断する．具体的には，受信した無効化情報に含まれるタイムスタンプと自身のタイムスタンプ表の情報を比較して，前者の方が新しい場合は，自身のもつタイムスタンプ表の情報を更新する．これと同時に，受信した無効化情報を，自身と隣接している移動体に転送する．
さらに，このデータの複製を自身のキャッシュ領域に保持している場合は，それをキャッシュ領域から破棄し，オリジナルをもつ移動体に対して更新データの送信を要求する．オ
リジナルをもつ移動体がこの要求を受信すると，要求した移動体に対して，更新データを配布する
ここで受信した無効化情報に含まれるタイムスタンプと自身のタイムスタンプ表の情報が同じ場合は，同一の無効化情報を再度受信しているため，隣接している移動体には転送せず，無効化情報を破棄する．
図 2 は，DU 方式において，移動体 M1 がオリジナルデー
タ D1 を更新したときに，更新データを配布する様子を示している．図中の四角は，各移動体がキャッシュ領域に保持している複製を表し，矢印は，更新データの流れを表している．
ここでは，M1 は，M3 に D1 を更新データとして配布している．

2

DBSJ Letters Vol.2, No.2

M2

M5

D3D4M3

更新 M1
D１M6D１

オリジナル
図2M4

D1D2

DU 方式における更新データの配布

Fig.2 Updated data dissemination in DU method.
この方式では，移動体がオリジナルを更新した場合にのみ，無効化情報の放送と更新データの配布が行われるため，トラヒックは小さい．また，オリジナルをもつ移動体と相互接続している移動体が，その複製を保持している場合，データ更新 が発生する 度 にオリジナルと同じタイムスタンプの複製を配置できる．しかし，更新時にオリジナルをもつ移動体と相互接続していないと，無効化情報と更新データを受信できない．そのため，移動体の移動に伴い，無線リンクの接続や切断が頻繁に起こる環境では，相互接続している移動体が異なるタイムスタンプ情報や異なるバージョンの複製をもつ場合がある．

3.2

DC (Dissemination on Connection) 方式

DC 方式では，オリジナルをもつ移動体が更新した際に無効化情報の放送と更新データの配布を行うことに加え，新たに接続（隣接）した移動体どうしが，タイムスタンプ表の情報を更新し，無効化情報の放送と更新データの配布を行う．
DC 方式では，二つの移動体が新たに接続した際，まず文献[7]の方式と同様に，次のように無効化情報を再放送する．
(1) 識別子が Mi と M（i<j）である二つの移動体が新たに接j
続したとき，識別子の添字が大きい移動体(Mj)が，小さい移動体(Mi)に自身のタイムスタンプ表を送信する．
(2) 移動体 Mi は，受信した移動体 Mj のタイムスタンプ表と自身のもつタイムスタンプ表の各項目を比較して，タイムスタンプ情報を更新する．その後，次の処理を行う．
移動体 Mi のもつタイムスタンプの方が古かったデータに関しては，無効化情報（新しいタイムスタンプ情報）を Mi がもともと相互接続していた移動体に放送する．
移動体 Mj のもつタイムスタンプの方が古かったデータに関しては，新しいタイムスタンプ情報を Mjに送信する．その後，Mj は，自身にもともと相互接続していた移動体の集合に，無効化情報を放送する．
無効化情報を受信した移動体は，DU 方式と同様に，自身のもつタイムスタンプ表の更新と古い複製の破棄を行う．
次に，無効化情報の放送後，接続した二つの移動体それぞれが，もう一方の移動体に更新データを配布する．ここで，Mj (Mi)が，Mi (Mj)に更新データを配布する手順を説明する．
(3) 移動体 Mi (Mj)は，前述の無効化情報の放送によって無効化された複製のデータ識別子（リスト）を含む更新データ問合せメッセージを，移動体 Mj (Mi)に送信する．
(4) 更新データ問合せメッセージを受信した移動体 Mj (Mi)は，これに含まれるデータ識別子のデータ（複製）を保持している場合，そのデータ（複製）を更新データとして Mi (Mj)に送信する．

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
M5D20.3

D3M3M1D1接続{D3}

図3Fig.30.35

M4M6D3D4

本章では，提案方式の性能評価のために行ったシミュレーション実験の結果を示す．

シミュレーション環境

50×50 の 2 次元平面上に，40 個の移動体(M={M1,…,M40})が存在する．各移動体は，この 2 次元平面からランダムに目的地を決定し，0 から 1（最大移動速度）の範囲でランダムに決定した速度で移動する．移動体がその目的地に到達すると，停止することなく，次の目的地を決定し，移動する．各移動体の無線通信範囲は，半径 5 の円とする．ネットワーク
内 に は ， 40 種 類 の デ ー タ (D={D1,…,D40}) が 存 在 し ， Dj
(j=1,…,40) は Mj にオリジナルデータとして保持されている．
各移動体は，再配置周期を 100 として，2 章で述べた DCG方式を用いて，自身のキャッシュ領域に最大 10 個の複製を作成する．各移動体 Mi の各データ Dj へのアクセス頻度は，pij=0.05×(1+0.001j)とする．各移動体は，自身のもつオリジナルデータを平均 Uavg（平均更新間隔）の指数分布に基づいた間隔で更新する．また，表 1 の各メッセージに含まれる項目一つ分をデータ量の単位として，全てのデータのサイズを
表 2 パケットのサイズ
Table 2 Packet size.

3

パケット名サイズ

無効化情報
更新データ問合せ

21＋（データ ID リストの要素数）

更新データ返信

1＋（データ ID リストの要素数）

データ25,000

0.2
0.15

NODU
DC0.1

00

Updated data dissemination in DC method.

4. 性能評価

0.250.05

DC 方式における更新データの配布

図 3 は，左側の移動体の集合{M1, M2, M3}と右側の移動体の集合{M4, M5, M6}がそれぞれ相互接続していたときに，M3と M4 が新たに接続した場合の，DC 方式の動作例を示している．なお，ここでは，M3 が M4 に更新データを配布する動作のみに着目している．このとき，M3 は，M4 の要求するD3 をもつため，M4 に更新データ(D3)を配布する．
この方式では，二つの移動体が新たに接続する度に，無効化情報の放送と更新データの配布が行われる．そのため，DU方式と比較して，古い複製へのアクセス回数が削減され，アクセス成功率が向上するものと期待される．また，相互接続している移動体は，同一のタイムスタンプ表をもつようになる．しかし，ネットワークのトポロジ変化が頻繁な場合，無効化情報の放送と更新データの配布の頻度が高くなるため，
DU 方式と比較して，トラヒックが大きくなる．

4.1

Data Accessibility

M2

DBSJ Letters Vol.2, No.2306090120
Average Update Period

図4

Uavg とアクセス成功率

Fig.4150

Uavg and Data Accessibility.

等しく 25,000 とする．表 2 に各パケットのサイズを示す．
初期位置として各移動体をランダムに配置し，シミュレーションの単位時間ごとに，各移動体の各データに対するアクセス頻度に基づいてアクセス要求を発行させる．シミュレー
ション実験では，1,000,000 単位時間を経過させたときの下記の評価値について調べた．
アクセス成功率
シミュレーション時間内に発生したアクセス要求の総数に対するアクセス成功回数の割合．
古い複製にアクセスした割合
シミュレーション時間内に発生したアクセス要求の総数に対する，更新発生後の古い複製に行われたアクセスの総数の割合．
トラヒック
シミュレーション時間内に発生した，無効化情報，更新データ問合せメッセージ，更新データ返信メッセージ，および更新データの配布に要する通信ホップ数に，それぞれのサイズを掛けたものの総和．

4.2

Uavg の影響

Uavg の提案方式への影響を調べた．その結果を，図 4，図5，図 6 に示す．これらの図において，横軸は Uavg を示す．
縦軸は，図 4 ではアクセス成功率，図 5 では古い複製にアクセスした割合，図 6 ではトラヒックを示す．ここで，比較のため，無効化情報の送信や更新データの配布を行わない場合の結果も示し，これを NO と表記している．
図 4 は，DC 方式が，DU 方式よりも高いアクセス成功率を示している．これは，DC 方式では，移動体の接続が生じる度に更新データの配布が行われるため，各移動体がより新しい複製を保持できるからである．また，平均更新間隔が大きくなると，各移動体のもつ複製が有効な時間が長くなるため,どの方式においてもアクセス成功率が高くなる．
図 5 は，DC 方式が，DU 方式より古い複製にアクセスした割合が低いことを示している．これは，DC 方式では，移動体の接続時に更新データを配布するだけではなく，無効化情報も放送するため，DU 方式よりも，無効化情報を広範囲に伝播し，多くの古い複製を破棄できるからである．
図 6 より，DC 方式は，DU 方式よりトラヒックが高いことがわかる．これは，DC 方式が DU 方式よりも頻繁に更新データを配布するという性質上，自明の結果になっている．
また，平均更新間隔が大きくなると，どの場合でもトラヒックが小さくなる．これは，平均更新間隔が大きくなると，各

日本データベース学会 Letters Vol.2, No.2

Ratio of Accessing to Invalid Replicas

論文――――――――――――――――――――――――――――――――――――
0.45

[謝辞]

NODU
DC

0.4
0.350.3

本研究の一部は，文部科学省科学技術振興調整費「モバイル環境向 P2P 型情報共有基盤の確立」，および文部科学省 21
世紀 COE プログラム（研究拠点形成費補助金）の研究助成によるものである．ここに記して謝意を表す．

0.25
0.2

[文献]

0.15
0.1
0.05
0030

図5Fig.56090120
Average Update Period

150

Uavg と古い複製にアクセスした割合

Uavg and Ratio of Accessing to Invalid replicas.
3.5E+11NODU
DC

3E+11Traffic

2.5E+112E+111.5E+111E+115E+100030

図6Fig.660
90120
Average Update Period

150

Uavg とトラヒック

Average Update Period and traffic.

データが更新される頻度が低くなるため，各メッセージの送信や更新データの配布の頻度も低くなるからである．

5. まとめ
本論文では，データ更新が発生するアドホックネットワー
クにおいて，古い複製へのアクセス回数の削減とデータアクセスの成功率の向上を目的として，各移動体が更新データを配布する方式を提案した．DU 方式では，オリジナルをもつ移動体がデータを更新した際に，自身と相互接続している移動体に更新データを配布する．一方，DC 方式では，DU方式の動作に加え，新たに接続した移動体どうしでタイムスタンプ表を比較し，更新データを配布する．
性能評価のために行ったシミュレーション実験の結果から，DC 方式は，DU 方式と比較して，古い複製にアクセスする割合を削減できるが，トラヒックが大きくなることを確認した．したがって，実環境で提案方式を適用する場合，データの更新頻度や各移動体の計算能力とバッテリ容量などのシステム特性に応じて，最適な方式を選択する必要がある．
今後は，更新データによるトラヒックを削減することを目的として，各移動体が複製の更新に必要な差分データのみを配布する方法について検討する予定である．

4

DBSJ Letters Vol.2, No.2

[1] Broch J., Maltz, D.A., Johnson, D.B., Hu, Y.C., andJetcheva J.: “A performance comparison of multi-hop
wireless ad hoc network routing protocols,” Proc.
Mobicom'98, pp.85-97 (1998).
[2] Lee, S., Su, W., Hsu, J., Gerla, M., and Bagrodia, R.: ”Aperformance comparison study of ad hoc wirelessmulticast protocols,” Proc. IEEE Infocom’00, pp.
565-574 (2000).
[3] Wang, K., and Li, B.: “Group mobility and partition
prediction in wireless ad-hoc networks,” Proc. IEEE
ICC’02, vol. 2, pp. 1017-1021 (2002).
[4] Karumanchi, G., Muralidharan, S., and Prakash, R.:“Information dissemination in partitionable mobile ad
hoc networks,” Proc. Symposium on Reliable
Distributed Systems (SRDS'99), pp. 4-13 (1999).
[5] Luo, J., Hubaux, J.P., and Eugster, P.: “PAN:
providing reliable storage in mobile ad hoc networks
with probabilistic quorum systems,” Proc. ACM
MobiHoc’03, pp. 1-12 (2003).
[6] 原 隆浩: “アドホックネットワークにおけるデータ利用性向上のための複製配置，信学論(B)，” vol. J84-B，no. 3，
pp. 632-642 (2001)．
[7] 林 秀樹，原 隆浩，西尾 章治郎: “アドホックネットワー
クにおける不定期データ更新を考慮したキャッシュ無効化について，” 情報処理学会マルチメディア通信と分散処理ワークショップ論文集，pp. 219-224 (2002).

林 秀樹

Hideki HAYASHI

2002 年大阪大学工学部電子情報エネルギー工学科卒業．同年，同大学大学院情報科学研究科博士前期課程に入学し，現在に至る．移動体計算環境におけるデータベースシステムに興味をもつ．日本データベース学会学生会員．

原 隆浩

Takahiro HARA

1997 年大阪大学大学院工学研究科博士前期課程修了．同年，博士後期課程中退後，同大学大学院工学研究科情報システム工学専攻助手．2002 年同大学院情報科学研究科マルチメディア工学専攻助手となり，現在に至る．工学博士．データベースシステム，モバイルコンピューティングなどの研究に従事．IEEE，電子情報通信学会，情報処理学会，日本データベース学会の各会員．

西尾 章治郎Shojiro NISHIO

1980 年京都大学大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科教授を経て，2002 年より同大学院情報科学研究科教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長を併任．データベース，マルチメディアシステムの研究に従事．現在，ACM Trans. on Internet Technology などの論
文誌編集委員，本学会理事，情報処理学会フェロー含め，9学会の会員．

日本データベース学会 Letters Vol.2, No.2