fマルチメディア通信と分1位処理ワークショップJ 平成19年10月 Publish/Subscribe
モデルに基づくセンサオーバレイネットワークの提案
小 川 和 其 ? 中 村 陽一什 斉 藤 裕 樹 ? 戸辺 義 人 ?T
東京電機大学工学部情報メディア学科t
t東京'屯機大学大綱~工，~羽T究科情報メディア学専攻 センサデバイスや無線通信デバイスの小型化や向性能化によって，センサを大量に使用した大規模な センサネットワークが構築，管理，運用されている.大規模なセンサネットワークでは，可用性と信 頼性の向上のために，分散型のアーキテクチャを検討する必要がある.そこで，センサデータを収集 するノード同士でセンシングデータの分散処理!を可能とするオーバレイネットワークについて検討す る.本研究では，即時性のあるイベント駆動型のセンサアプリケーションを想定し， PublishJSubscribe モデルを用いたセンサオーバレイネットワークのアーキテクチャを提案する. 1 . はじめに 近年，センサデバイスの小型化や無線通信デバ イスの高性能化により，大規模なセンサネットワ ークが構築，管 理，運用されている.従来のセン サネットワ}クはセンシングデータを一つのノ ードの下に収集するアーキテクチャで構築され ることが多いが，大規模なセンサネットワークで は，サービスの可用性と信頼性を高め，特定のノ ードへの負荷の集中を防ぐために，分散裂のアー キテクチャを検討する必要がある. 本研究では，特定の事象が発生したときに即時 的に処理!を開始するイベント駆動型アプリケー ションを対政とし， PublishJSubsぽibeモデノレに 基づいたセンサオーバレイネットワークを従衆 する. 2. センサオーバレイネットワーク 近年，分散アルゴリズムや分散ストレージなど の研究においてオーバレイネットワークが注目 さ れ て い る . 代 表 的 な ア ル ゴ リ ズ ム に は Chord[l，] CAN[2]などの分散ハツ‘ンュテープノレ (DHT)がある.これらの従来のオーバレイネット ワーク技術を大規模なセンサネットワークに適 用する場合，位世や時間などの属性を柔軟に指定 した検索ができないなどの問題がある.また，セ ンサから送られてくるデータは連続的かつ膨大 なデータストリームとみなすことができる.この ような述続的なデータストリームを単純に DHT 上に保存することは適切ではない. イベント駆動型のアプリケーションでは，あら かじめユーザが自分の情報をサーバに選択して おき，自分の興味のあるデータがサーバに送られ てきたときにユーザにデータを送るようなシス テムが適している.PublishJSubscribeモデノレを センサオーバレイネットワークに適用すること により負荷分散とデータストリーム処理の効率ィ
ι
を図る 3. Publish/Subscribeモデル PublishJSubscribeシステム[3]は，メッセージ の送り手が連続的にデータを送信しているのに 対して，受け手はあらかじめどのようなデータが 必要か選択しておき，必要な内容のみを得ること ができるシステムである ここでは，データの送 り手をPublisher，データの受け手を Subscriber， データの選択・仲介役をメッセージブローカと呼 ぶ. 従来のPublishJSubscribeシステムは，メッセ ージ処理を単一のメッセージブローカが集中し て行うアーキテクチャで椛築されている.本研究 ではメッセージブローカの機能を，複数のノード から構成するオーバレイネットワーク上で笑現 する分散型アーキテクチャを提案する. 4. Publish/Subscribeモデルに基づくセンサオーバ レイネットワークの設計 4.1Publis~、/Subscribe マップの構造 Subscriberは，どの範囲の位置で起こるどの ような事象(例えば，温度や湿度の範閤)を購読 するかをメッセージブローカに登録するものと する.この購読情報を Subscriptionと呼ぶ.メ ッセージブローカでは， Subscriberが受け取り 湿度(%) 90 60 30 Subscriber1の購読範図 10 120 30 40 Subscriber2の脱税制聞 図1.PublisbJSubscribe""ツプ lノード が 管 理 す る領域 t且皮("C)-
8
1
-表1.管理範囲による各ノードのStibs，cription数の分布
ω
等間隔で管理範囲を分割した際のSubscription数 たいデータの選択範囲を位置，温度，湿度，照度 といったセンシングデータの種別ごとに分け，種 別ごとに，登録されているS
u
b
s
c
r
i
b
e
r
の範囲を 示すマップ状の多次元のデータ構造を構築する. これをPub
l
i
s
h
l
S
u
b
s
ぽi
b
e
マップと呼ぶ.図1
は， 2つのS
u
b
s
c
r
i
b
e
r
が温度と湿度の2次元からな る 範 囲 を 指 定 し て 購 読 を 登 録 し た と き のP
u
b
l
i
s
h
l
S
u
b
s
c
r
i
b
e
マyプの状態を示している. 次 に ， 図1
の 点 線 に 示 す よ う にP
u
b
l
i
s
h
l
S
u
b
s
c
r
i
b
e
マyプを各次元について分割し，オー パレイネットワークを構成するノードに割り当 て る . 各 ノ ー ド は 割 り 当 て ら れ た 範 囲 のSubs
ぽi
p
t
i
o
n
の管理を行う.以下に，P
u
b
l
i
s
h
l
S
u
b
s
c
r
i
b
e
マップの分割方法とノードの割当て アルゴリズムについて説明する. 4.2 Publish/Subscribeマップの負荷分散処理 Pub
l
i
s
h
l
S
u
b
s
c
r
i
b
e
マップ内のS
u
b
s
c
r
i
p
t
i
o
n
は 一様な分布とはならず，頻繁に利用される事象の 周囲に偏るものと考えられる.したがって，表 1(a)のようにマップを一定間隔で分割するのは ノードに負荷の偏りが生じるため不適切である. そこでまず，表l
(
b
)
のようにS
u
b
s
c
r
i
p
t
i
o
n
数の 頻度分布を見たとき，Sub
scri.p
t
i
o
n
が多く分布す る領域は管理範囲を狭くし，S
u
b
s
c
r
i
p
t
i
o
n
の分布 が少ない領域は管理範囲を広くすることで負荷 分散を行う.以下にその手法について述べる. 図2
にPub
l
i
s
h
l
S
u
b
s
ぽi
b
e
マップの負荷分散ア ル ゴ リ ズ ム を 示 す . こ の ア ル ゴ リ ズ ム は ，S
u
b
s
c
r
i
p
t
i
o
n
数に偏りのある状態から反復的に 実行することで分割の全体的な均衡化を図る.ま ず，管理範囲が隣り合うノードx，yについてのS
u
b
s
c
r
i
p
t
i
o
n
数の比較を行い，管理範囲の変更を 行うかを決定する.ノード又Y
のS
u
b
s
c
r
i
p
t
i
o
n
数の差の絶対値が閥値より大きい場合，ノードX と ノ ー ド Y の 管 理 範 囲 の 境 界 を 移 動 し ，S
u
b
s
c
r
i
p
t
i
o
n
数を均衡させる.この動作をすべて の隣り合う領域のノード聞で定期的に反復して 行う. AI伊d血mL2つのノードXとYの偏りを調ペ管理領揖の “変更を決定するアルゴリズム Comparebegin首(X.numOjぬbscription-Y.numQ除制。由r:Jton>ε)也 佃 reqMoveXtoY:= (XmunOjSz伽 坤 伽 均 一
Y.numOjSubscription) 12; Xe.x戸'lIId(reqM01程XToY); d健iC(XnumOjSubscrlption -Y.numOjSubscription<・ε)曲 個 reqMoveηoX:=(Y.n捌 OjSub.庇:ription -XnumQ倒必tscripti<加~/2; X劫 ゆ 洲 崎MoveYtoX); endiC end AE伊d血皿怠管理領域の嚢更を行うアルゴリズム E専問7dbegin end newBo.何台r:=X呼事'1erBorrJer. while(Y.numOjSub抑 制 仰
(newB01也r，均7perB01由FドreqM伽 XToηdo
newBorrJeri= d do田 Xodd.ぬbscrip陶n(， Y.getS!泊 師 事tion(Y.lowerBorrJer，newBa崎~)); Y.rem01昭品bscription(X.lowerBm伽~newB切rIer); 工 呼 脚'rBorrJer:=Y.lowerBo1由r:=newBorder， 図2.Publi血ISubscribeマyプの 負荷分散アルゴリズム
5
.
まとめ 本論文では，大規模センサネットワークにおけ る 負 荷 分 散 を 実 現 す る た め に ，P
u
b
l
i
s
bJSubs
ぽi
b
e
モデルに基づいたセンサオー パレイネットワークを提案を行った.今後は，実 装を行い提案手法の評価を行い，提案手法の有用 性を実証する. 本研究は，東京電機大学総合研究所研究課題 ω7J-02として行ったものである. 参考文献 [1] S句協，1."Mo:πi，sR.，Karger， D.， K舗:-shoek，M. F. andBalakr油nan，H.:Chord: A S伺lab1ePeer-to-peerLookup PrO'旬∞IforIn飽metAppli図説ons， Proc.of ACM SIGCOMM 2
