Sorting on Single-Channel Wireless Sensor Networks

作     者：Jacir Luiz Bordim Koji Nakano Hong Shen 

作者机构：Adaptive Communications Research Laboratories Advanced Telecommunications Research Institute International 2-2-2 Hikaridai Kyoto 619-0288 Japan School of Artificial Complex Systems Engineering Hirhoshima University Kagamiyama Higashi-Hiroshima 799-8527 Japan School of Information Science Japan Advanced Institute of Science and Technology Asahidai Tatsunokuchi Ishikawa 923-1292 Japan 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：2003年第14卷第3期

页      面：391-403页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Wireless sensor networks sorting bitonic sorting sensing devices 

摘      要：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 time slots when . 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.