Efficient Initialization Algorithms on Single-Hop Radio Networks(Networks)
スポンサーリンク
概要
- 論文の詳細を見る
We consider an initialization problem in single-hop radio networks. The initialization is the task of assigning distinct ID numbers to nodes in a network. We have greatly improved the previous results for the initialization in an n-node network. We propose randomized initialization algorithms in two cases. The first case is that n is known to all the nodes and the second case is that n is unknown to all the nodes. The algorithm for the first case completes in en+lnn+O(1) expected time slots, and the algorithm for the second case completes in en+O(√<n>) expected slots. The main idea of the algorithm for the case that n is unknown is presumption of the number of nodes. In the algorithm, each node presumes the number of nodes efficiently and is assigned ID by using the algorithm for the case that n is known with the presumption value.
- 社団法人電子情報通信学会の論文
- 2007-06-01
著者
-
Wada Koichi
Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute Of Te
-
INABA Naoki
Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of
-
Inaba Naoki
Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute Of Te
関連論文
- Rectal carcinoid tumor associated with the Peutz-Jeghers syndrome
- Polynomially Fast Parallel Algorithms for Some P-Complete Problems (Special Section on Discrete Mathematics and Its Applications)
- Designing Efficient Parallel Algorithms with Multi-Level Divide-and-Conquer (Special Section on Discrete Mathematics and Its Applications)
- Finding the Envelope of Segments in Parallel
- Efficient Initialization Algorithms on Single-Hop Radio Networks(Networks)
- Special Section on Invited Papers from New Horizons in Computing
- Architecture and Performance of Dynamic Offloading Mechanism for Maestro2 Cluster Network
- Architecture and Performance of Dynamic Offloading Mechanism for Maestro2 Cluster Network