| 講演抄録／キーワード |
| 講演名 |
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ダウンロード |
|