論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

アドホックネットワークにおける消費電力を考慮した複製配置に関
する一考察

D1

A Study on Replica Allocation Considering
Power Consumption in Ad Hoc Networks

切断
D2

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

篠原 昌子 1
原 隆浩 2

林 秀樹 1
西尾 章治郎 2

Masako SHINOHARA Hideki HAYASHI
Takahiro HARA Shojiro NISHIO

アドホックネットワークでは，データの利用性を向上させるため，データの複製を作成することが有効である．このとき，他の移動体が頻繁にアクセスするデータをもつ移動体は，
多くのデータを転送するため，他の移動体より電力を多く消費してしまう．また，移動体が電力を使い果たしてネットワークから退出した場合，その移動体のもつデータにアクセスできなくなる．そこで本論文では，データの利用性の向上と移動体間の消費電力の均一化を目的として，二つの複製配置方法を提案する．一つめの方法では，各移動体が，データへのアクセス頻度とネットワーク内に存在する各データ（複製）の個数を考慮して複製を配置する．二つめの方法では，
電力残量の少ない移動体が電力を使い果たすことを防ぐため，一つめの方法において移動体の電力残量を考慮して複製を配置する．
In ad hoc networks, it is effective that each mobile hostcreates replicas of data items for improving data
accessibility. A mobile host that holds data items
frequently accessed by other mobile hosts has to transmit
them many times, and thus, it consumes higher amountsof power than other mobile hosts. Moreover, if a mobile
host exhausts its battery and leave from the network,
other mobile hosts cannot access data items held by themobile host. In this paper, we propose two replica
allocation methods for improving data accessibility andbalancing power consumptions among mobile hosts. In
the first method, each mobile host allocates replicas
considering the access frequency and the number of
replicas of each data item in the network. In the othermethod, in addition to the first method, each mobile hostallocates replicas considering the remaining batteries ofmobile hosts to avoid mobile hosts to exhaust theirbatteries.

1

学生会員 大阪大学大学院情報科学研究科{sinohara.masako,hideki}@ist.osaka-u.ac.jp
2 正会員 大阪大学大学院情報科学研究科{hara,nishio}@ist.osaka-u.ac.jp

1

1. はじめに
近年，無線通信技術の発展と計算機の小型化に伴い，時間や場所に関係なくネットワークに接続できる移動体計算環
境が普及しつつある．特に，ルータ機能をもつ移動体のみで一時的なネットワークを形成するアドホックネットワーク
への関心が高まっている[1, 3, 5]．アドホックネットワー
クでは，既存の通信インフラを必要とせず，各移動体が自律的にネットワークを構築できるため，緊急災害時の救助活動
やセンサネットワークへの利用が期待されている．このような環境では，移動体同士でデータを共有し，互いのもつデー
タにアクセスすることが多い．しかしアドホックネットワー
クでは，移動体の移動によってネットワークが分断されるため，分断された部分ネットワーク内のデータにアクセスできず，データの利用性が低下してしまう．例えば，図1における中央の無線リンクが切断された場合，左側の3台の移動体
はデータD2に，右側の3台の移動体はデータD1にアクセスできなくなる．ここで，データの利用性の低下を防ぐため，移動体が他の移動体のもつデータの複製を作成することが有効であり，これまでにいくつかの複製配置方式が提案されている[2, 4, 7, 8, 9]．文献[2, 9]では，データの利用性を向上させるため，移動体の各データへのアクセス頻度とネッ
トワークトポロジを考慮した複製配置方式を提案している．
文献[4]では，配置する複製の数を抑制することで複製配置のコストを削減しながら，データ転送による遅延を軽減する方法を提案している．文献[7]では，ネットワークが分断される時間を予測し，分断前に移動体間で複製を配置する方式を提案している．文献[8]では，アクセス遅延の軽減とデー
タ転送によるトラヒックの削減を実現するキャッシング方式を提案している．
ここで，他の移動体が頻繁にアクセスするデータ（複製）をもつ移動体や，ネットワーク内に保持している個数の少ないデータ（複製）をもつ移動体は，データ転送の機会が多くなり，消費電力が大きくなる．一般的にアドホックネットワ
ークでは，移動体の電力容量に制限があり，データ転送による消費電力が全体の大きな割合を占める場合が多い．したがって，データ転送を多く行う移動体は，他の移動体より自身の電力を早く使い果たして，ネットワークから退出してしまう．この場合，他の移動体がネットワークから退出した移動
体のもつデータにアクセスできなくなるため，データの利用性が低下してしまう．しかし，文献[2, 4, 7, 8, 9]では，移動体の電力残量を考慮していないため，データ転送を多く行う移動体が他の移動体より電力を早く使い果たす問題がある．
そこで本論文では，データの利用性の向上と移動体間の消費電力の均一化を目的として，移動体の消費電力を考慮した
二つの複製配置方法を提案する．一つめの方法では，特定の日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
移動体へのデータアクセスの集中を防ぐため，各移動体がデータへのアクセス頻度とネットワーク内に存在する各デー
タ（複製）の個数を考慮して複製を配置する．二つめの方法
では，電力残量の少ない移動体が電力を早く使い果たすことを防ぐため，一つめの方法において移動体の電力残量を考慮して複製を配置する．
以下では，2章で想定環境について述べる．3章で提案する
複製配置方法について述べ，4章で提案方法の性能を評価するために行ったシミュレーション実験の結果を示す．最後に5章で本論文のまとめと今後の課題について述べる．

2. 想定環境
本論文では，各移動体が自身または他の移動体のもつデー
タ（複製）にアクセスする環境を想定する．移動体がデータを要求するとき，そのデータを自身のデータ領域にもつ場合，即座にアクセスして，その要求は成功となる．要求したデー
タをもたない場合，相互接続している移動体のもつデータにアクセスする．ここで，相互接続している移動体とは，1ホップ以上の無線リンクで相互に通信可能な移動体の集合を指す．相互接続しているどの移動体も要求したデータをもたない場合，その要求は失敗となる．なお，本論文で提案する
複製配置方法は，データアクセス方法とは独立に動作するため，データアクセス方法を特に限定しない．各移動体はアクセスしたデータの複製を自身のデータ領域に配置する．ここでデータ領域に空きがない場合，複製配置方式に従って，データの置き換えが発生する．
移動体は外部から電力を供給できず，電力容量が限られているものとする．例えば，緊急災害時の救助活動において，被災地の電力インフラが破綻していた場合，救助隊員は携帯型端末に電力を補給できない．また,計算処理による消費電力は無視できるぐらい小さく，移動体の電力はデータ転送のみによって消費されるものとする．
想定環境のその他の詳細を以下に示す．
z m個の移動体（識別子：M1,M2,...,Mm）が存在し，各々が自由に移動する．
z n個のデータ（識別子：D1,D2,...,Dn）が存在し，各々が特定の移動体にオリジナルデータとして保持されている．簡単化のため，すべてのデータのサイズは等しく，
データ更新は発生しないものとする．
z 各移動体は，自身のオリジナルを格納するデータ領域以外に，データC個分の複製を配置するデータ領域をもつ．
z 各移動体Miは，自身の電力残量Piを測定できる．

3. 消費電力を考慮した複製配置方法
提案方法では，移動体が他の移動体のもつデータ（複製）にアクセスしたとき，その複製を自身のデータ領域に配置す
る．各移動体が頻繁にアクセスするデータを優先的に配置す
ると，自身のもつデータへのアクセスが多くなり，消費電力が減少する．しかし，この場合，類似したアクセス特性をもつ移動体同士は同じ種類のデータの複製を配置してしまい，
データの利用性が低下してしまう[2]．そこで，データの利用性の向上と移動体間の消費電力の均一化を目的として，二つの複製配置方法を提案する．

3.1

Expected Access (EA) 法

EA 法では，データの利用性を向上させるため，周囲の移動体が頻繁にアクセスし，かつ自身と周囲の移動体間で保持している個数の少ないデータの複製を優先的に配置する．

2以下では，移動体Miが自身のデータ領域に保持していない
データDnewにアクセスした後の動作について説明する．
(1) Miは，自身のデータ領域に空きがある場合，データDnewの複製を配置し，処理を終了する．データ領域に空きがない場合，自身からn(>1)ホップ内で相互接続している移動体にデータ情報問合せパケットをフラッディングする．
このパケットには，Miの識別子，Miが保持しているデー
タ（複製）とDnewの識別子のリストが含まれる．
(2) 問合せパケットを受信した移動体Mjは，データ情報返信
パケットを移動体 Mi に送信する．このパケットには，
MiとMjの識別子に加え，問合せパケットに含まれる各データへのアクセス頻度と，各データ（複製を含む）を保持しているか否かを示すフラグが含まれる．
(3) Miは，nホップ内の各移動体から返信パケットを受信す
ると，次の式を用いて，自身が保持しているデータDkを破棄してDnewを配置した場合のアクセス回数の変化量の期待値⊿i,k→newを求める．

∆ i , k → new=Ai , newA− i ,old
Ci , new + 1 Ci ,old

(1)

ここで，Ai,mは移動体Mi とnホップ内の移動体のデータ
Dmへのアクセス頻度の総和，Ci,mはこれらの移動体間で保持されているデータDm（複製を含む）の個数を示す．
つまり，式(1)の右辺の各項目は，移動体Miとnホップ内の移動体のデータ Dnew と Dk へのアクセス回数の期待値を示すため，⊿i,k→newはデータDkを破棄してDnewを配置した場合のアクセス回数の変化量の期待値を示す．
(4) Miは，自身が保持しているデータの中で，⊿i,k→newが正で最大となるDkを破棄してDnewを配置する．つまり，ア
クセス回数の期待値が最も増加するデータ Dk を破棄する．ただしCi,k=1 の場合（Mi以外の移動体がDkを保持していない場合），Dkを破棄する対象としない．これは，MiがDkを破棄した場合，周囲の移動体がDkにアクセスで
きず，データの利用性が低下してしまうからである．またCi,new=0 の場合（nホップ内のどの移動体もDnewを保持していない場合），Dnewを優先的に配置する．これは，MiがDnewを配置した場合，周囲の移動体がDnewにアクセスできるようになり，データの利用性を向上できるからである．
EA 法では，アクセス頻度の高いデータや自身と n ホップ
内の移動体間で保持している個数の少ないデータが優先的に配置されるため，データの利用性が向上する．また，各データがアクセス頻度に応じてネットワーク全体に配置されるため，移動体間の消費電力が大幅に偏ることはない．EA法では，n の値によりデータの利用性と移動体の消費電力を調整できる．例えば，n を小さく設定した場合，狭い範囲内の移動体同士でアクセス頻度の高いデータを共有するため，
ネットワーク全体で見ると複製の重複が多くなる．その結果，
各移動体のアクセス可能なデータ数が減少し，データの利用性が低下すると考えられる．一方，各移動体が近くの移動体のもつデータにアクセスできるようになるため，データ転送のホップ数が小さくなり，消費電力が減少する．n を大きく設定した場合は，逆の特性を示す．

3.2

Expected Access + Battery (EA+B) 法

EA 法では，アクセス回数の期待値が増加するデータの複製を優先的に配置するため，電力残量の少ない移動体が周囲の移動体から頻繁にアクセスされるデータの複製を配置し，電力残量が早く低下する可能性がある．

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
そこでEA+B法では，移動体がアクセス回数の変化量の期待値だけでなく，自身の電力残量も考慮して複製を配置する．
以下では，移動体Miが自身のデータ領域に保持していないデータDnewにアクセスした後の動作について説明する．
(1) Miは，自身のデータ領域に空きがある場合，データDnewの複製を配置し，処理を終了する．そうでない場合，nホップ内の移動体にデータ情報問合せパケットをフラッ
ディングする．このパケットを受信した各移動体Mjは，
データ情報返信パケットをMiに送信する．
(2) Miは，式(1)を用いて自身が保持しているデータDkを破棄してDnewを配置する場合のアクセス回数の変化量の期待値⊿i,k→newを求める．
(3) Miは，自身の電力残量Piが閾値σ（σは固定値）以上の場合，EA法と同様に⊿ i,k → new が正で最大となる Dk を破棄して D new を配置する．一方， P i がσ未満の場合，⊿i,k→newが負で最小となるDkを破棄してDnewを配置する．
つまり，アクセス回数の期待値が最も減少するデータDkを破棄する．これにより，アクセス回数の期待値を減少させ，電力残量の少ない移動体が早く電力を使い果たすことを防ぐことができる．ただし，EA法と同様に，Ci,k=1となるDkは破棄する対象にせず，Ci,new=0 となるDnewは優先的に配置する．
EA+B 法は，初期状態では移動体の電力残量がσ以上とな
り，EA 法の動作と等しくなる．しかし,時間が経過すると，電力残量がσ未満となる移動体が多くなり，電力残量の少ない移動体にアクセス頻度の高いデータやネットワーク内の個数の少ないデータが配置されにくくなる．これにより，他の移動体より極端に早く電力を使い果たす移動体の出現を防ぐことができる．しかし移動体が多種類のデータにアクセスできなくなり，EA 法に比べてデータの利用性が低下する
可能性がある．

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

4.1

シミュレーション環境

500[m]×500[m]の 2 次元平面上に 50 個の移動体 (M=M1,M2,...,M50)が存在し，各移動体は 0 から 10[m/秒]の範囲でランダムに決定した速度で，全方向に等確率に移動するものとした．各移動体の無線通信範囲は，半径 70[m]とした．
ネットワーク内には，50 種類のデータ(D=D1,D2,...,D50)が存在し，DjはMj (j =1,2,...,50) にオリジナルデータとして保持されるものとした．各移動体の各データDjへのアクセ
ス頻度はpj=0.005×(1+0.05j)として，各移動体は 1[秒]ごとにこのアクセス頻度に基づいてアクセス要求を発行するものとした．その際，移動体はアクセス要求をフラッディング
し，要求したデータをもつ移動体に最短ホップ数でアクセスするものとした．各データのサイズは 1[メガバイト]とし，各移動体は最大 5 個の複製を作成できるものとした．複製配置方法には，提案方法（EA法とEA+B法）に加え，比較方法
としてLRU（Least Recently Used）法を用いた．なお，EA
法とEA+B法では，nを 1 と∞に設定した場合について評価した．
各移動体のバッテリ容量はすべて等しく 50,000[単位エネルギー]とし，データの送信と受信に必要な電力は 1[単位エネルギー]とした．なお，制御パケットのサイズはデータに比べて非常に小さいものとして，その送受信による消費電力は

3

表 1 経過時間とアクセス成功率
Table1 Elapsed times and data accessibility.
EA
EA+B
経過時間
LRU
n
=∞
n=1
n=1 n=∞
1〜 30,000 0.53 0.63 0.69 0.63 0.69
30,001〜 60,000 0.47 0.57 0.50 0.53 0.32
60,001〜 90,000 0.24 0.29 0.24 0.20 0.12
90,001〜120,000 0.21 0.24 0.20 0.15 0.12
120,001〜150,000 0.19 0.19 0.19 0.12 0.10
無視した．また，EA+B 法の閾値σは初期電力の 20%（10,000[単位エネルギー]）に設定した．
以上のシミュレーション環境において，各移動体の初期位置をランダムに決定し，150,000[秒]を経過させたときの30,000[秒]ごとのアクセス成功率，および経過時間と生存移動体数の関係を調べた．アクセス成功率とは，アクセス要求の総数に対するアクセス成功回数の割合を指す．また，生存移動体数とは，電力を使い果たさずネットワークに参加している移動体数を指す．

4.2

シミュレーション結果

まずアクセス成功率を調べた結果を表 1 に示す．表 1 の結果より，いずれの方法も時間の経過によりアクセス成功率が低くなることがわかる．また各方法を比べると，この特徴は
EA+B 法で最も顕著で，次に EA 法が顕著だった．これは，電力を使い果たした移動体がネットワークから退出するため，その移動体のもつデータにアクセスできなくなるからである．提案方法では，アクセス頻度の高いデータやネットワ
ーク内の個数の少ないデータの複製を優先的に配置することで，データの利用性を向上させる反面，移動体が多くのデータを転送して早く電力を使い果たしてしまう．さらに，
EA+B 法では，電力残量の少ない移動体がアクセス頻度の高いデータやネットワーク内の個数の少ないデータを破棄するため，アクセス成功率の低下が顕著である．提案方法のn=1 と n=∞の場合を比べると，提案方法はシミュレーショ
ン開始時では n=∞の方が高く，終了時では n=1 の方が高い
ことがわかる．これは，n=∞と設定した場合，各移動体が多種類のデータにアクセスできる反面，アクセスするデータまでのホップ数が大きくなり，データ転送による消費電力が大きくなるからである．
次に，時間の経過による生存移動体数を調べた結果を図 2に示す．この図において，横軸は経過時間，縦軸はその時刻における生存移動体数を表す．図 2 の結果より，初めて電力を使い果たした移動体が現れるまでの時間（最短生存時間）
は，n=1 の場合は提案方法が LRU 法とほぼ同じだが，n=∞の場合は短くなることがわかる．これは，表 1 の結果における考察と同様で，n=∞と設定した場合，データの利用性が向上する反面，データ転送による消費電力が大きくなり，移動体が電力を早く使い果たしてしまうからである．また，EA法と EA+B 法を比べると，n=∞では EA 法の方が，n=1 では EA+B 法の方が，時間の経過による生存移動体数の減少度
合が大きくなっている．EA+B 法では，n=∞のとき，電力残量の少ない移動体がデータの利用性を低下させるように複製を配置することで電力を節約できている．しかし n=1 のとき，局所的な複製配置により，近くの移動体のもつデータにアクセスしにくくなる．そのため，アクセスするデータまでのホップ数が大きくなり，消費電力が大きくなる．

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――50

LRU
EA (n=1)
EA (n=∞)
EA+B (n=1)
EA+B (n=∞)

生存移動体数

40

30

20

10

0
0

30000

60000
90000
経過時間

120000150000

図 2 経過時間と生存移動体数
Fig.2 Elapsed time and number of living mobile hosts.

5. まとめ
本論文では，データの利用性の向上と移動体間の消費電力の均一化を目的として，二つの複製配置方法を提案した．一つめの方法では，各移動体が，データへのアクセス頻度とネットワーク内に存在する各データ（複製）の個数を考慮して，複製を配置する．二つめの方法では，電力残量の少ない移動体が電力を使い果たすことを防ぐため，一つめの方法において移動体の電力残量を考慮して複製を配置する．シミュレー
ション実験の結果より，各提案方法は LRU 法よりデータの利用性を向上させることを確認した．また，提案方法では，各移動体が多くのデータを転送するため，早く電力を使い果たしてしまうが，n=1 と設定した場合，最短生存時間は LRU
法とほぼ同じになることを確認した．
EA+B 法では，閾値σを固定値としたが，移動体の電力残量が時間の経過と共に減少していくことを考慮すると，σを適応的に変化させることで，さらに性能を向上できるものと考えられる．今後は，適応的なσの設定方法について検討する予定である．また，本論文では各移動体が要求したデータを最短ホップ数でアクセスすることを想定した．しかし，この場合，ネットワークの中心に存在する移動体は，多くのデータを中継することになり，他の移動体より消費電力が大きくなる．今後は，本論文で提案した複製配置方式と文献[6]で提案したデータアクセス方法を併用し，さらに移動体間の消費電力の均一化を図る予定である．

[謝辞]
本研究の一部は，文部科学省 21 世紀 COE プログラム「ネットワーク共生環境を築く情報技術の創出」，および文部科
学省若手研究(A)(16680005)の研究助成によるものである．
ここに記して謝意を表す．

[文献］[1] Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C. andJetcheva, J.: “A Performance Comparison ofMulti-Hop Wireless Ad Hoc Network Routing
Protocols”, Proceedings of IEEE/ACM MOBICOM'98,
pp.85-97 (1998).
[2] 原 隆浩: “アドホックネットワークにおけるデータ利用性向上のための複製配置”, 電子情報通信学会和文論文
誌 B, Vol.J84-B, No.3, pp.632-642 (2001).

4[3] Johnson, D. B.: “Routing in Ad Hoc Networks ofMobile Hosts”, Proceedings of IEEE WMCSA'94,
pp.158-163 (1994).
[4] Nuggehalli, P., Srinivasan, V. and Chiasserini, C.-F.:“Energy-Efficient Caching Strategies in Ad Hoc
Wireless Networks”, Proceedings of MobiHoc'03,
pp.25-34 (2003).
[5] Perkins, C. E. and Royer, E. M.: “Ad-hoc On-DemandDistance Vector Routing”, Proceedings of IEEEWMCSA'99, pp.90-100 (1999).
[6] 篠原昌子, 林 秀樹, 原 隆浩, 西尾章治郎: “アドホック
ネットワークにおける消費電力を考慮したデータアクセ
スについて”, 情報処理学会研究報告(データベースシス
テム研究会 2005-DBS-135・放送コンピューティング研
究グループ 2005-BCCgr-10 合同研究発表会), Vol.2005,
No.6, pp.111-118 (2005).
[7] Wang, K. and Li, B.: “Efficient and Guaranteed
Service Coverage in Partitionable Mobile Ad-hoc
Networks”, Proceedings of IEEE INFOCOM'02 (2002).
[8] Yin, L. and Cao, G.: “Supporting Cooperative Cachingin Ad Hoc Networks”, Proceedings of IEEE
INFOCOM'04 (2004).
[9] Yin, L. and Cao, G.: “Balancing the Tradeoffs between
Data Accessibility and Query Delay in Ad Hoc
Networks”, Proceedings of SRDS'04, pp.289-298(2004).

篠原 昌子

Masako SHINOHARA

2004 年大阪大学工学部電子情報エネルギー工学科卒業．同
年同大学大学院情報科学研究科博士前期過程に入学し，現在に至る．アドホックネットワークの研究・開発に従事．日本
データベース学会学生会員．

林 秀樹

Hideki HAYASHI

2002 年大阪大学工学部電子情報エネルギー工学科卒業．
2004 年同大学大学院情報科学研究科博士前期課程修了．同年，同大学大学院情報科学研究科博士後期課程に入学し，現在に至る．モバイルデータベースの研究に従事，情報処理学会，日本データベース学会の各学生会員．

原 隆浩

Takahiro HARA

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

西尾 章治郎Shojiro NISHIO

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

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