Generalization of Sorting in Single Hop Wireless Networks

Shyue-Horng SHIAU  Chang-Biau YANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.4   pp.1432-1439
Publication Date: 2006/04/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.4.1432
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
Keyword: 
parallel algorithm,  wireless,  sorting,  broadcast communication,  conflict,  generalized sorting,  

Full Text: PDF>>
Buy this Article



Summary: 
The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.