Counting-sort and Routing in a Single Hop Radio Network^*

Abstract

We consider two problems. First, sorting of n integer keys from the [0,2^m-1] range, stored in p stations of a single-hop and single channel radio network. Second problem is routing of the packets between the stations of the network. We introduce counting-sort algorithm which has 3mr_i+s_i+d_i+3 energetic cost and nm+n+p time cost, where station a_i stores s_i keys (r_i distinct keys) and receives d_i keys. On the basis of this sorting, we construct routing protocols with energetic costs (3⌈log₂p⌉+2)r_i+s_i+d_i+5 and (3⌈log₂p⌉+4)r_i+s_i+d_i+6, and time costs n⌈log₂p⌉+n+3p and r⌈log₂p⌉+n+r+3p, respectively, where r is sum of all r_i. Our routing is attractive alternative for previous solutions, since it is efficient, deterministic and simple.

Published in Proceedings of 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Wrocław, Poland, July 14, 2007, Lecture Notes in Computer Science, vol. 4837, Springer-Verlag 2007, pp. 138-149.

^*Partially supported by KBN grant 3 T11C 011 26.

Conference paper

Conference presentation.