An Efficient Minimum-Latency Collision-Free Scheduling Algorithm for Data Aggregation in Wireless Sensor Networks

Data collection is one of the most important operations in applications of wireless sensor networks (WSNs). In many emerging WSN applications, it is urgent to achieve a guarantee for the latency involved in collecting data. Many researchers have studied collecting data in WSNs with minimum latency but without data collision while assuming that any (or no) data are allowed to he aggregated into one packet. In addition, tree structures are often used for solutions. However, in some cases, a fixed number of data are allowed to be aggregated into one packet. This motivates us to study the problem of minimizing the latency for data aggregation without data collision in WSNs when a fixed number of data are allowed to be aggregated into one packet, termed the minimum-latency collision-avoidance multiple-data-aggregation scheduling (MLCAMDAS) problem. The MLCAMDAS problem is shown to be NP-complete here. In addition, a nontree-based method, termed the independent-set-based collision-avoidance scheduling (ISBCAS) algorithm, is proposed accordingly. The ISBCAS is demonstrated via simulations to have good performance.