A Fast Initialization Algorithm for Single-Hop Wireless Networks

Shyue-Horng SHIAU  Chang-Biau YANG  

Publication
IEICE TRANSACTIONS on Communications   Vol.E88-B   No.11   pp.4285-4292
Publication Date: 2005/11/01
Online ISSN: 
DOI: 10.1093/ietcom/e88-b.11.4285
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
Keyword: 
parallel algorithm,  initialization,  broadcast,  communication,  wireless network,  conflict,  

Full Text: PDF>>
Buy this Article




Summary: 
Given a set of n stations, the initialization problem is to assign each station a unique identification number, from 1 to n. In the single-hop wireless Networks with collision detection, Nakano and Olariu proposed an algorithm to build a partition tree and solve the problem. In this paper, we shall classify the partition tree into four parts. By reviewing the classification, we find that three ideas can improve the algorithm. We show that it needs 2.88n time slots for solving the problem containing n stations. After applying our three ideas, the number of time slots will be improved to 2.46n.