| 講演抄録／キーワード |
| 講演名 |
2006-04-26 11:25
動的なセンサー網における効率的な情報頒布および収集アルゴリズムについて
○稲葉直貴・内田次郎・片山喜章（名工大）・陳 慰（テネシー大）・和田幸一（名工大） |
| 抄録 |
（和） |
文献[11]で我々は、$n$節点から成るセンサー網$G$上のクラスタに基づいた新たなアーキテクチャと、高速なブロードキャストを提案した。提案した構造は$p$個のクラスタと$2p-1$頂点を持つ背骨木から構成され、この構造においてブロードキャストは$O(p)$ラウンドで実行できる。ここで$p$は$G$の最小クリーク分割数であり、通常$p<<n$である。これらの構造は節点の$G$への参加と$G$からの離脱の二つの操作により維持される。
本論文では、ブロードキャストの実行時間を$O(h_{BT})$ラウンドに改良し、$G$上のすべての節点の情報をある節点に収集する操作を可能にした。提案する収集操作の実行時間は$O(h_{BT}+\Delta)$ラウンドである。ここで、$G$は単位円グラフであるとし、$h_{BT}$は背骨木の高さ、$\Delta$は$G$の最大次数を表す。また、参加と離脱に要するラウンド数のオーダーは以前とほとんど変わらない。 |
| （英） |
In [11], we have proposed a novel clustering on a flat sensor $n$-node-network $G$ and provides fast communication between clusters. The proposed cluster-based structure consists of $p$ clusters and backbone tree has at most $2p-1$ nodes, where $p$ is the smallest number of complete subgraphs in $G$. In usual setting, $p <<n$. In this structure, a broadcast can be done in $O(p)$ rounds and two structure reconfiguration operations,
a node-move-in and node-move-out are incorporated.
In this paper, we improve the performance of broadcasting into $O(h_{BT})$ rounds, and incorporate gathering operation, and it can be performed in $O(h_{BT}+\Delta)$ rounds, where $h_{BT}$ is the height of the backbone tree and $\Delta$ is the maximum degree of $G$, if $G$ is a unit disk graph. We also show these two operations can be performed efficiently with almost preserving the performance of the node-move-in and node-move-out. |
| キーワード |
（和） |
動的センサネットワーク / クラスタリング / ブロードキャスト / データ収集 / / / / |
| （英） |
sensor network / cluster-based / broadcast / gather / / / / |
| 文献情報 |
信学技報, vol. 106, no. 29, COMP2006-4, pp. 25-32, 2006年4月. |
| 資料番号 |
COMP2006-4 |
| 発行日 |
2006-04-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-04-26 - 2006-04-26 |
| 開催地（和） |
京都大学 |
| 開催地（英） |
Kyoto University |
| テーマ（和） |
一般 |
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-04-COMP |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
動的なセンサー網における効率的な情報頒布および収集アルゴリズムについて |
| サブタイトル（和） |
|
| タイトル（英） |
Efficient Broadcasting and Gathering Algorithms on Dynamic Sensor Networks |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
動的センサネットワーク / sensor network |
| キーワード(2)（和/英） |
クラスタリング / cluster-based |
| キーワード(3)（和/英） |
ブロードキャスト / broadcast |
| キーワード(4)（和/英） |
データ収集 / gather |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
稲葉 直貴 / Naoki Inaba / イナバ ナオキ |
| 第1著者 所属（和/英） |
名古屋工業大学 (略称： 名工大)
Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） |
内田 次郎 / Jiro Uchida / ウチダ ジロウ |
| 第2著者 所属（和/英） |
名古屋工業大学 (略称： 名工大)
Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） |
片山 喜章 / Yoshiaki Katayama / カタヤマ ヨシアキ |
| 第3著者 所属（和/英） |
名古屋工業大学 (略称： 名工大)
Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第4著者 氏名（和/英/ヨミ） |
陳 慰 / Wei Chen / チン イ |
| 第4著者 所属（和/英） |
テネシー州立大学 (略称： テネシー大)
Tennessee State University (略称： Tennessee State Univ.) |
| 第5著者 氏名（和/英/ヨミ） |
和田 幸一 / Koichi Wada / ワダ コウイチ |
| 第5著者 所属（和/英） |
名古屋工業大学 (略称： 名工大)
Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-04-26 11:25:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2006-4 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.29 |
| ページ範囲 |
pp.25-32 |
| ページ数 |
8 |
| 発行日 |
2006-04-19 (COMP) |