Sorting on single-channel wireless sensor networks

Jacir Luiz Bordim, Koji Nakano, Hong Shen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A Wireless Sensor Network (WSN) is a distributed system consisting of a large number of wireless sensing devices and a base station. Due to their compactness and lowcost, sensor networks can be distributed at a fraction of the cost of conventional wired sensors and actuator systems. The physical world generates an unlimited amount of data that can be observed and monitored. Hence, designing protocols to coordinate WSNs with hundreds, or even thousands, of sensors will face many challenges. In this work we focus on the design of protocols that enable the sensor nodes to coordinate among themselves to achieve a larger task. From this standpoint, we present a sorting protocol for wireless sensor networks. We show that in a WSN consisting of n sensor nodes, where each sensor stores an element and has a fixed transmission range r. sorting can be performed in $O(r \sqrt{n})$ time slots when $r < \sqrt{n}$. We also reason that future applications of wireless sensor networks are very likely to employ shortrange radio communications (i.e., r less than 100 meters). If this is the case, the time complexity of our sorting protocol is optimal.

Original languageEnglish
Pages (from-to)391-403
Number of pages13
JournalInternational Journal of Foundations of Computer Science
Issue number3
Publication statusPublished - 2003
Externally publishedYes


  • Wireless sensor networks
  • bitonic sorting
  • sensing devices
  • sorting


Dive into the research topics of 'Sorting on single-channel wireless sensor networks'. Together they form a unique fingerprint.

Cite this