Minimum Latency Aggregation Scheduling in Wireless Sensor Networks with Successive Interference Cancellation
Shiliang Xiao, Lebing Pan, Yunzhou Qiu and Xiaobing Yuan
We study the minimum latency aggregation scheduling (MLAS) problem in wireless sensor networks (WSNs) under the physical interference model combined with successive interference cancellation (SIC). Recognized as a powerful technique of multi-packet reception (MPR) at the physical layer, SIC allows a receiver to decode several arriving signals at the same time as long as these signals differ in strength significantly, resulting in increased transmission throughput and reduced latency, potentially. We first formulate the problem of MLAS with SIC and prove its NP-hardness. To resolve it effectively, we then propose two heuristic polynomial-time scheduling algorithms, namely first-fit aggregation scheduling (F2AS) and shortest-fit aggregation scheduling (SFAS), through fully exploiting the new transmission opportunities offered by SIC. Both algorithms are greedy ones that try to achieve maximal possible links scheduled in each time slot, thereby minimizing the total time consumed by the data aggregation task. Theoretical analysis indicates that the schedule results of F2AS and SFAS are both interference-free. Simulations show that F2AS and SFAS outperform state-of-the-art scheduling algorithms designed for MLAS under the physical interference model without SIC in terms of latency under various network configurations.
Keywords: Data aggregation, scheduling, physical interference model, successive interference cancellation, wireless sensor networks