
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Initialization Algorithms on SingleHop Radio Networks
Naoki INABA Koichi WADA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E90D
No.6
pp.915922 Publication Date: 2007/06/01
Online ISSN: 17451361
DOI: 10.1093/ietisy/e90d.6.915
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Networks Keyword: radio network, singlehop, initialization,
Full Text: PDF>>
Summary:
We consider an initialization problem in singlehop radio networks. The initialization is the task of assigning distinct ID numbers to nodes in a network. We have greatly improved the previous results [10] for the initialization in an nnode 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+ln n+O (1) expected time slots, and the algorithm for the second case completes in en+O() 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.

