A Fast Initialization Algorithm for Single-Hop Wireless Networks

Shyue-Horng SHIAU
Chang-Biau YANG

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
parallel algorithm,  initialization,  broadcast,  communication,  wireless network,  conflict,  

Full Text: PDF(329.8KB)>>
Buy this Article

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.