A Distributed Sorting Framework for Ad Hoc Wireless Sensor Networks
Wireless Sensor Networks (WSN) are distributed, self-organizing, pervasive systems, which perform collaborative computations to provide useful information about the underlying stochastic phenomenon. In this paper, the authors explore the ranking and sorting problems in distributed sensor networks which provide perspectives in understanding certain fundamental issues in WSN, as well as motivate many exciting real life applications. In the sequel, they consider the sorting problem under a generalized framework of geometric random graphs and show that finding a time and/or energy optimal distributed sorting algorithm is NP-hard. Finally, they prove the existence of a randomized sorting algorithm under the generic setup.