論文

地理情報の詳細度を考慮した移動オブジェクト群への情報配信
Broadcasting Geographic Information with Levels-of-Details toMoving Objects

羅 勇♥ 天笠 俊之♦
吉川 正俊♠ 植村 俊亮♦
Yong LUO Toshiyuki AMAGASA
Masatoshi YOSHIKAWA
Shunsuke UEMURA
近年，モバイル端末の普及に伴い，多数の端末に効率的な情報配信を可能にするデータ放送が盛んに研究されている．これまで
我々は，移動オブジェクトの位置だけではなく，移動方向と移動速度を考慮した移動オブジェクトのグループ化手法を提案してきた．本論文では，地理情報に詳細度 (Levels of Details; LoD)の概念を導入することによって情報配信のさらなる効率化を目指す．具体的には，地理情報と移動オブジェクトの距離に応じて異なる粒度の情報を配信する．これは XML で記述された元データと，元データから粒度の粗いデータを抽出する変換スクリプトによって実現される．その結果，転送されるデータ量を低く抑えることを可能にする．本論文ではさらに，配信データの放送スケジューリングアルゴリズムとして，移動オブジェクトの速度を考慮したスケジューリングと，配信データの連続性を考慮したスケジューリングのアルゴリズムを提案する．

In recent years, broadcast data delivery has beenstudied well with the spread of mobile terminals. Inorder to realize efficient data distribution, we haveproposed a technique to group moving objects withrespect to not only their positions, but also their direction and speeds. This paper aims at further improvements in the efficiency of information distribution by introducing the concept of LoD (Levels of Details) into broadcasted data. Specifically, the geographic data are distributed with distinct granularities depending on distances between the data andmoving objects. This is realized with the combination of source data written in XML and accompanying translation scripts that extract coarser data form
the source data. The proposed scheme makes it possible to lower the amount of transmitted data. Furthermore, we propose two algorithms for schedulingbroadcasted geographic data; One is based on speedsof moving objects, and the other is based on continuityof geographic data.
♥ 学生会員奈良先端科学技術大学院大学情報科学研究科博士後期課程
la-yu@is.aist-nara.ac.jp♦ 正会員 奈良先端科学技術大学院大学情報科学研究科{amagasa,uemura}@is.aist-nara.ac.jp♠ 正会員 名古屋大学情報連携基盤センター
yosikawa@itc.nagoya-u.ac.jp

1

DBSJ Letters Vol. 2, No. 1

1. はじめに計算機の小型化，高性能化と無線ネットワークの普及にともない，無線ネットワークを介した移動端末に対する情報配信が注目されている．今後は情報配信を受ける端末の数が急速に増加することが予想されるため，多数の端末に一括して情報を配信することのできるデータ放送が有効な配信手段となることが予想される．
このような状況では，例えばさまざまな情報が地域全域に分布し，これらをデータ放送により地域全体向けに配信するという状況が一般に行われるようになる．データ放送に関係した従来の研究では，(1) その地域に存在するすべての情報を配信することを想定し，放送の効率を上げるために配信する情報のスケジューリングを行う方法 [3, 4, 5]，(2) 移動オブジェクト側が配信された情報を受信する際，所望の情報だけを効率よく取り出す方法 [2, 6] などが提案されている．
しかし移動オブジェクトにとって必要なのは，多くの場合，地理情報のごく一部だけである．すなわち移動オブジェクトに対してその近傍情報だけを放送すれば十分である．また同時に，放送側から見ても，配信すべきデータの量を削減することができ，結果として放送の周期を短縮することができる．このとき移動オブジェクトは常に移動し続けているので，その近傍情報を効率良く組織する必要がある．このため，我々は移動オブジェクトを，位置，移動方向，移動速度の 3 つのパラメータを用いてグループ化し，近傍情報を効率的に組織化する方法を提案した [1]．
本論文ではこの手法に地理情報の詳細度 (Levels of Details;LoD) の考えを導入することによって，さらなる効率化を実現する．具体的には，あるグループに地理情報を配信する場合，そのグループから近い位置にある情報は詳細に記述する．一方，そのグループから遠い情報に関しては詳細度を下げ，大まかな情報のみを配信する．これにより配信情報の効率化を図ることができる．
また，本論文では近傍情報を配信データとしてスケジューリングする 2 つのアルゴリズムを提案する．1 つはグループの移動速度を考慮したスケジューリングである．すなわち，高速に移動しているグループではデータ配信の遅延が大きなペナルティとなるので，このようなグループに対しては優先的なスケジューリングを行う．2 つめは同一のグループに配信すべき地理情報をできるだけ連続して配信するスケジューリングである．これにより，移動オブジェクトは自分が受信すべきデータを常に受信する必要がなくなり，消費電力を節約できるなどの利点がある．

2. 移動オブジェクトのグルーピングに基づく情報配信
本章では，[1] で提案した移動オブジェクトのグループ化手法を説明する．提案手法において，移動オブジェクトのグループは，移動オブジェクトの位置，移動方向，移動速度を考慮して得られる．よって互いに近接しているだけでなく，類似した方向に類似した速度で移動しているオブジェクトが同じグループにまとめられる．このように得られたグループは，時間の変化に伴う移動オブジェクトとグループの対応づけの変動を抑えることが期待できる．このため，本手法では，移動オブジェクトに対して位置，速度，方向という特徴量でクラスタリングを行う．これにより，互いに近接し，似た速度と方向を持つオブジェクトを同じグループに分類することができる．
オブジェクトは時間とともに移動するため，生成したグループを維持するための処理が必要である．これを単純なクラスタリン
グの繰り返しで行うのはあまりにもコストが高い．このため，グループの外接包囲矩形 (MBR; Minimum Bounding Rectangle)
比較によるグループ維持更新手法を提案した [1]．この手法では，各グループの MBR の面積の経時変化を監視し，その変化の割合が与えられたある閾値を上回った場合に，もっとも外れた位置にあるオブジェクトの所属グループを再計算する (図 1)．

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

論文

DBSJ Letters Vol. 2, No. 1

面積が大きく変化したなら、分布が広がる。更新と判断再計算すべき移動オブジェクト

yymovingObject

movingObject

vv

3
group

group(a)t1t2

図 1: MBR に基づくグループの更新
それぞれのグループに対応する配信情報は，そのグループをカバーする円形の問合せ範囲を用いて求めることができる (図 2(a))．
しかし各グループは移動を続けているので，単純な円形の問合せ範囲では，データを受信するまでにその場所を通り過ぎてしまうかもしれない．提案手法では，各グループの位置に加えて，移動方向，移動速度がわかっているので，移動方向にある近傍情報を多めにとるように楕円形の問合せ範囲を決定するという方法をとる (図 2(b))．検索して得られた地理情報は木構造に組織化され，配信される．
yMoving object

Moving object

rv

vt

rc

c

QA(Query Area)
(a)

x

θ

QA(Query Area)x

図 2: 楕円問合せ範囲の生成

3. 地理情報への詳細度の導入[1] では，あるグループに配信する地理情報をすべて同等に扱っていた．しかし，実際には地理情報の重要性はそれぞれ異なっていると考えるのが自然である．重要性の考え方には色々あるが，1 つの見方として距離を挙げることができる．すなわち，あるグループから近い位置にある地理情報は遠い位置にある地理情報に比べて，より重要であると考えることができる．これは，3 次元グラフィックス分野における表示オブジェクトの詳細度 (Levels ofDetails; LoD) の考え方に似ている．このため，我々は地理情報の詳細度という概念を導入する．
具体的な例を図 3 に示す．図 3(a) の楕円はあるグループの問合せ範囲を示している．これを例えば，距離に応じた 3 つの区域に分けてみると，区域 1 における地理情報は詳細度の最も高いレベルで配信すべきであり，区域 2, 3 にいくにつれ，地理情報の詳細度を次第に減らして配信する．配信環境に詳細度を導入ことで，配信側から見れば，配信データ量を減らすことで配信周期の短縮につながる．移動オブジェクト側から見ても，遠くにある地理情報のデータ量が少ないので，端末の処理負担も減る．
図 3(a) の問合せ範囲は [1] に基づいているが，詳細度の考え方は，問合せ範囲の決め方とは無関係である．例えば図 3(b) は別の問合せ範囲を示している．このとき，区域 3 の面積が一番大きくなり，その範囲に含まれる地理情報の数が一番大きくなることが予想されるが，詳細度を導入することによって，その量を抑えることができる．

3. 1 実現方法
地理情報の詳細度を実現するためには，2 つの実現方法が考えられる．1) 予め地理情報を詳細度レベルに応じて準備して，地理情報データベースに格納しておく．2) 地理情報データベースには，オリジナルの地理情報と，詳細度に応じたデータを得るための変2x(b)換手続きを格納しておく．
1) の方法では，最初に詳細度を応じたデータを作っておけば，後はデータベースから対応した詳細度のデータを取り出すだけでよいという利点がある．しかし地理情報自身や詳細度に頻繁に変更がある場合，その都度データを作り直す必要がある．2) の方法
では，地理情報データをデータベースから取り出したとき，変換手続きを適用し，詳細度に応じたデータを動的に作る．サーバ側の負担が大きいかもしれないが，個々の詳細度に応じたデータを用意することを省ける上，データや詳細度の変更に対して柔軟性がある．
本論文では，2) の実現方法を念頭に説明を進めることにする．

3. 2 記述方法c’q(b)x

地理情報は XML 形式で記述され，データベースに格納されているものとする．このとき詳細度は以下の構造に従って記述する．

vr31

図 3: 詳細度による地理情報の区域分け

T

移動オブジェクト

y2

2

1<!DOCTYPE LOD [<!ELEMENT LOD(level+)><!ELEMENT level(#PCDATA)><!ATTLIST LOD location
ID #REQUIRED><!ATTLIST level number CDATA #REQUIRED><!ATTLIST level type (XQuery | XPath) #REQUIRED>]>

変換手続きの中の level 要素には XQuery 式，あるいは XPath式を記述する．それらは詳細度に応じたデータを地理情報から取り出すための問合せ式である．各詳細度レベルのデータは，以下のようにして抽出する．
詳細度のレベルを l = {1, 2, . . . , n} とし，詳細度 l の問合せ式をql () とする．ここでは詳細度 l の地理情報を引数に取り，詳細度l + 1 の情報を返す関数として扱う．このとき，詳細度 l の地理情
報 gdl は，以下のようにして求める．

gdl = ql−1 (. . . q2 (q1 ((gd1 ))))
gd1
gd2
gd3
query1level1

query2level2

leve3

queryigdn

leveli leveln

図 4: 各詳細度の求め方
すなわち，図 4 で示すように，gd2 は，q1 (gd1 ) により得られ，gd3 は，q2 (gd2 ) = q2 (q1 (gd1 )) により得られる．以下同様である．
この規定により，ある特定の地理情報に関して，異なる端末が異なる詳細度のデータを要求する際に，要求されたものの中で最も詳細度の高いデータと，そこからの変換式だけを配信することによって，全ての要求に答えることができるという利点がある．
図 5 の地理情報を例にして説明する．これはある電器店に関する情報を表している．
この電器店に関する詳細度を次のように規定したとする．詳細
度 1 では，店に関するすべての情報を提供すべく，店名，住所，電話番号及び商品に関する情報を配信情報とする．詳細度 2 では，店がある程度移動オブジェクトから離れているので，店名，住所，日本データベース学会 Letters Vol. 2, No. 1

論文

DBSJ Letters Vol. 2, No. 1<LOD location="sample.xml"><level number="1" type="XPath">[/]</level><level number="2" type="XQuery">[FOR $Info1 IN /GeoInfo/ShopInfo,$Info2 IN /GeoInfo/ItemInfo
RETURN{$Info1}{$Info2/items/@name}{$Info2/SaleInfo}]</level><level number="3" type="XQuery">[FOR $Info1 IN /GeoInfo/ShopInfo,$Info2 IN /GeoInfo/ItemInfo
RETURN{$Info1}{$Info2/SaleInfo}]</level></LOD><GeoInfo id="01"><ShopInfo><shopname>奈良電器店</shopnama><address>生駒市高山町</address><tel>(0743)72-XXXX</tel></ShopInfo><ItemInfo><items name="CD"><Item>CD01</Item>......
</items><items name="MD"><Item>MD01</Item>......
</items>......
<SaleInfo><SaleItem>CD01値引き15%</SaleItem>......
</SaleInfo></ItemInfo></GeoInfo>

図 5: sample.xml の地理情報

図 6: sample.xml の LoD

表 1: 地理情報とグループ間の詳細度の対応
gi1
gi2
gi3
gi4
gi5
gi6
gi7
gi8
gi9G11233G21233G33321

記述例

電話番号，商品の種類及びセールス情報に関する情報だけを配信すべき情報とすれば良い．詳細度 3 では，店名，住所，電話番号と客を引き寄せるためのセールス情報だけを配信すべき情報とする．
以上に基づき，図 6 のような記述ができる．ここで，詳細度 1 の変換には XPath 式，2, 3 には XQuery 式を記述している．実際の処理の際には，データベースから，sample.xml とそれに対応する手続き式が一緒に取り出される．図 3(b) の区域 1 内に位置している店の場合は，詳細度 1 の level 要素の XPath 式を sample.xmlに適用し，その結果を配信データとする．区域 2，区域 3 に位置していれば，それぞれ詳細度 2，3 の level 要素の XQuery 式をsample.xml に問合せして，その結果を配信データとする．

<BroadcastInfo name="gi3"><BroadcastInfo name="gi2"><head><head><location x="150" y="300"/><location x="100" y="200"/><groups><groups><group number="G2" detail="1"></><group number="G1" detail="2"/><group number="G1" detail="3"></groups>[詳細度1のデータから詳細度3のデータを</head>
取り出す式(XQuery or XPath)]<body></group>(gi2の詳細度2のデータ)</groups></body></head></BroadcastInfo><body>
gi2
bgi2(gi3の詳細度1のデータ)</body>(a)</BroadcastInfo>gi3bgi3(b)図 8: 配信データ

4. 配信データの構築

5. 配信データのスケジューリング

配信データの構築に当たって，特に問題になるのは，複数のグループおよびその問合せ範囲に重なり合いがある場合である．図 7のように，グループの問合せ範囲が互いに重なり合う 3 つのグループがある．地理情報 gi4 はグループ G1 に対しては区域 3 に，グループ G2 に対しては区域 2 に位置する．最も素朴な方法では，データ gi4 を 2 回配信すればよいが，効率が悪くなる．重なりの度合いが複雑になればなるほど非効率なのは明白である．

ここでは，速度とデータの連続性の観点から 2 つのスケジューリングアルゴリズムを提案する．

G2

Y

3

12

gi3v
gi4

2
gi2
1
G1 gi1v33gi7gi6gi82gi5v
gi9 1gik(k=1,...,9): Geographic Information
Gi(i=1,2,3): Group

G3X

図 7: グループの問合せ範囲の重なり合い配信データの重複を解消するため，次の方法を用いる．各グループとその範囲内の地理情報との関係から表 1 の状態図を作る．これは各々の地理情報がどのグループ，どの区域に位置するかを表している．次に表 1 に基づき，データベースから取り出された地理情報を次のステップで構築する．

1. 地理情報が 1 つのグループにしか属さない場合， その詳細度に対応したデータに，グループの識別情報などを付加して配信データとする (図 8(a))．
2. 地理情報が 2 つ以上のグループに属する場合，その中から一番高い詳細度の地理情報にグループの識別情報を付加した配信データに加えて，必要な他の詳細度の情報を得るための手続きを付加する (図 8(b))
そうすることで，実際に配信されるデータ bgi1，bgi2，. . . を得られる．次の章で bgi1, bgi2, . . . をどのようにスケジューリングするかについて述べる．

35. 1 速度によるスケジューリング
ある時刻の移動オブジェクトの位置に基づいて構築された近傍情報の配信が始められるとき，速く移動する移動オブジェクトは，自分がその位置からあまり離れていないうちに近傍情報を受信したいはずである．なぜなら，移動オブジェクトがその位置から遠く離れていれば，その近傍情報は無意味なデータになってしまうからである．よって，速度の速いものに対する配信データを優先的に配信することが速度によるスケジュールアルゴリズムの基本的な考え方である．

1. n 個のグループ Gi (i = 1, . . . , n) のそれぞれの平均移動速度をvave (Gi ) とする．このとき，最大の速度を Vmax = max(vave (Gi ))とする．
(Gi )2. vnorm (Gi ) = vaveを求める．平均移動速度が最も大きなグVmax
ループ Gi の vnorm (Gi ) は 1 で，速度が低ければ低いほど，1より段々小さくなる．

3. このステップでグループ範囲内の配信データに対して重みをvnorm (Gi ) に基づいて与えるには 2 つの処理方法が考えられる．1 つは，同一グループ範囲内であっても，位置する区域により，配信データに異なる重みを与える．これは，同じグループ範囲内での配信情報に差別化を図るためである．2 つめは，同一グループ範囲内のすべての配信データに同一の重みを与える．
(a) 同一グループ内に属するすべての配信データ bgi j ( j =1, . . . , m) には，bgi j が属するグループ範囲内のどの区域に位置するかにより，異なる重みを与える．重みは以下の計算式に従う．
bgi.weights = {vnorm (Gi ) ∗ (1 + k ∗ (1 − level)) | bgi が Giの詳細度の問合せ範囲に含まれる }ここで，level ∈ {1, 2, . . . , n}, k < 1 である．これは同一のグループ内であっても，区域の差異により優先順位

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

論文

DBSJ Letters Vol. 2, No. 1が付けられることを意味し，詳細度の高い bgi j には大きな重みが付与される．

(b) 同一グループ内に属するすべての配信データ bgi j ( j =1, . . . , m) には，bgi.weights = {vnorm (Gi ) | bgi が Gi の問合せ範囲に含まれる }により，重みを与える．
4. よって，最終的に bgi の重み wbgi は，
wbgi = H ∗ w∈bgi.weights w であり，H は，調節パラメータで，1 より小さい．つまり同時に幾つかのグループに属する bgi では，属するグループにおけるそれぞれの重みが合計される．
5. 最後に，各配信データ bgi を wbgi でソートし，最も大きな値を持つものから順番に配信すれば良い．
以上のアルゴリズムによりスケジュールされた配信データは，速度の速いグループの範囲内の配信データであれば，優先的に配信される．

5. 2 配信データの連続性によるスケジューリング
一方，同一グループ内に属する配信データであれば，できるだけ連続して配信するようにスケジューリングするのが次のアルゴリズムである．図 7 を例にとりながら説明する．

1. 表 1 で求めたグループと地理情報の詳細度の対応表を元に，送信データに重複を持つグループを求める．表 2 は表 1 を上から順に走査し，放送すべきデータを持つ時に 1 を，持たない場合に 0 を記入し，さらに重複する行を削除することによって得ることができる．この表からグループ同士の重複の度合いを知ることができる．例えば，この例では G1 と G2，G2 と G3 に重複があることが分かる．

表 2: 重複の度合
G1111100000G2 G30 00 0
10
10
10
1 1
10
10
10

(G1)
(G1, G2)(G2)(G2, G3)(G3)

2. 表 2 から放送スケジュールを導出する．各グループがなるべく連続して放送されるようにスケジュールする問題は，表 2の各行を符号と見たとき，各行のハミング距離の変化が最小となるように行を整列する問題に置き換えることができる．
このために，まず図 9 に示すような完全グラフを作成する．
グラフの各頂点は表 2 の各行に対応し，各辺はそれに隣接する二頂点間のハミング距離によって重みづけされている．
このグラフ上の重み最小の経路によって放送スケジュールを求めることができる (図 10)．

6. まとめ
本論文では，[1] で提案した移動オブジェクトのグループ化手法に地理情報の詳細度 (Levels of Details; LoD) を導入することによって配信情報を効率化する手法を提案した．この手法において，あるグループに地理情報を配信する場合，そのグループから

4root
(G2)
2(G1)
3(G3)

13

1(G1,G2)

配信順

222

1(G1)

(G1,G2)(G2)(G2,G3)(G3)

bgi1 bgi2

bgi3 bgi4

bgi5

bgi6

bgi7 bgi8 bgi91(G2,G3)

図 9: 組合せの完全グラフ

図 10: Tree 構造をもつ配信データソース

近い位置にある情報は詳細に記述する．一方，そのグループから遠い情報に関しては詳細度を下げ，大まかな情報のみを配信する．
また，本論文では配信情報のスケジューリングアルゴリズムとして，グループの移動速度を考慮したものと，同一のグループに配信すべき地理情報をできるだけ連続して配信する二種類のアルゴリズムを提案した．今後は，提案した手法を実装し，その有効性を実験を通じて検証する予定である．

[謝辞]
本研究の一部は，科学技術振興事業団（JST）の戦略的基礎研究推進事業（CREST）「高度メディア社会の生活情報技術」プログラムの支援によるものである．ここに記して感謝を表す．

[文献][1] 羅勇，天笠俊之，吉川正俊，植村俊亮， ”移動オブジェクトに対する効率的な地理情報配信手法”， 電子情報通信学会 第13 回データ工学ワークショップ (DEWS2002)， 2002 年 3
月 4〜6 日．
[2] Susanne Hambrusch ，Chuan-Ming Liu ，Walid G. Aref，
Sunil Prabhakar ， ”Query Processing in Broadcasted
Spatial Index Trees ”，Advances in Spatial and Temporal Databases ，502 – 521 ，2001．
[3] S.-C. Lo，A.L.P. Chen，”Optimal index and data allocation in multiple broadcast channels” ，Proceedings of2000 IEEE International Conference on Data Engineering，pp.293–304 ，2000．
[4] 箱守聰，田辺雅則，石川裕治，井上潮，”放送型通信とオンデマンド型通信を統合した情報提供システム”，情報処理学会論文誌，Vol.40, No.10, pp.3772–3781 ，1999．
[5] Chi-Jiun Su, Leandros Tassiulas, ”Broadcast Scheduling for Information Distribution”, INFOCOM, pp.109–117, 1997.
[6] Baihua Zheng, Wang-Chien Lee, Dik Lun Lee, ”Search
K Nearest Neighbors on Air”, MDM, pp.181-195, 2003.

羅 勇 Yong LUO
奈良先端科学技術大学院大学情報科学研究科博士後期課程在学中.
データベースの研究に従事. 情報処理学会学生会員. 日本データベース学会学生会員.

天笠 俊之 Toshiyuki AMAGASA
奈良先端科学技術大学院大学情報科学研究科助手. データベースシステムの研究に従事. 情報処理学会正会員. 電子情報通信学会正会員, 日本データベース学会正会員.

吉川 正俊 Masatoshi YOSHIKAWA
名古屋大学情報連携基盤センター教授. データベースシステムの研究に従事. 情報処理学会正会員. 電子情報通信学会正会員, 日本
データベース学会理事.

植村 俊亮 Shunsuke UEMURA
奈良先端科学技術大学院大学情報科学研究科教授. データベースシステムの研究に従事. 情報処理学会フェロー. 電子情報通信学会フェロー, IEEE Fellow, 日本データベース学会正会員. 著書に「データベースシステムの基礎」（オーム社）など.

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