Sorting on single-channel wireless sensor networks

Abstract

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 low-cost, 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√n) time slots when r < √n. We also reason that future applications of wireless sensor networks are very likely to employ short-range radio communications (i.e., r less than 100 meters). If this is the case, the time complexity of our sorting protocol is optimal.