| 講演名 | 2000/6/19 COMP2000-25 アドホック無線ネットワーク上の省電力初期化アルゴリズム ボルジン ジャシル, 崔 江涛, 林 達也, 中野 浩嗣, オラりウ ステファン, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では、アドホック無線ネットワーク上の省電力初期化アルゴリズムを示す。まず、ステーション台数nが既知の場合、チャンネル数が1のアドホック無線ネットワーク上では、初期化がΟ(n)時間で高い確率で行えることを示す。また、このプロトコルで、各ステーションが動作するのはΟ(log n)時間である。次に、ステーション台数nが未知の場合に、nの近似値を求めるΟ((log n)^2)時間の確率プロトコルを示す。このプロトコルで、各ステーションが動作するのはΟ(log n)時間である。このプロトコルを利用し、ステーション台数nが未知の場合にΟ(n)時間で初期化が行えることを示す。最後にチャンネル数がκの場合、初期化がΟ(n/κ+log n)時間で行え、各ステーションの動作時間もΟ(log n)時間にできることを示す。 |
| 抄録(英) | The main contribution of this work is to propose energy-efficient randomized initialization protocols for ad-hoc radio networks(ARN, for short). First, we show that if the number n of stations is known beforehand, the single-channel ARN can be initialized by a protocol that terminates, with high probability, in Ο(n) time slots with no station being awake for more than Ο(log n)time slots. We then go on to address the case where the number n of stations in the ARN is not known beforehand. We begin by discussing, an elegant protocol that provides a tight approximation of n. Interestingly, this protocol terminates, with high probability, in Ο((log n)^2)time slots and no station has to be awake for more than Ο(log n)time slots. We use this protocol to design an energy-efficient initialization protocol that terminates, with high probability, in Ο(n)time slots with no station being awake for more than Ο(log n)time slots. Finally, we design an energy-efficient initialization protocol for the κ-channel ARN that terminates, with high probability, in Ο(n/κ+log n)time slots, with no station being awake for more than Ο(log n)time slots. |
| キーワード(和) | ラジオネットワーク / 配置プロトコル / 省エネルギー / 確率的なアルゴリズム |
| キーワード(英) | radio networks / initialization protocols / energy-efficient / randomized algorithms |
| 資料番号 | COMP2000-25 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | COMP2000-25 アドホック無線ネットワーク上の省電力初期化アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | COMP2000-25 Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ラジオネットワーク / radio networks |
| キーワード(2)（和/英） | 配置プロトコル / initialization protocols |
| キーワード(3)（和/英） | 省エネルギー / energy-efficient |
| キーワード(4)（和/英） | 確率的なアルゴリズム / randomized algorithms |
| 第 1 著者 氏名（和/英） | ボルジン ジャシル / J.L. Bordim |
| 第 1 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering, Nagoya Institute of Technology |
| 第 2 著者 氏名（和/英） | 崔 江涛 / J. Cui |
| 第 2 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering, Nagoya Institute of Technology |
| 第 3 著者 氏名（和/英） | 林 達也 / T. Hayashi |
| 第 3 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering, Nagoya Institute of Technology |
| 第 4 著者 氏名（和/英） | 中野 浩嗣 / K. Nakano |
| 第 4 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Department of Electrical and Computer Engineering, Nagoya Institute of Technology |
| 第 5 著者 氏名（和/英） | オラりウ ステファン / S. Olariu |
| 第 5 著者 所属（和/英） | オールドドミニオン大学計算機科学科 Department of Computer Science, Old Dominion University |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-25 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |