Intertwined path formation and MAC scheduling for fast delivery of aggregated data in WSN

This paper studies the problem of data aggregation scheduling in wireless sensor networks (WSNs) to minimize time latency. In prior work on this problem, a node is assigned a parent from the set of unscheduled nodes in order to prevent the creation of cycles. However, using such a strategy reduces the time-slot reuse and consequently has a negative impact on the time latency. To address these shortcomings, we propose IPS (Interwined Path formation and MAC Scheduling), a novel cross-layer scheme for data aggregation scheduling that allows selecting a parent from all the node's neighbors including the scheduled ones. IPS achieves reduced data delivery latency through three key design features, namely, (1) intertwining aggregation tree formation and scheduling, (2) for each node, a parent can be selected from already scheduled nodes so that the time latency is reduced and the cycles are prevented and (3) applying parent selection criteria that maximize the time slot reuse. We prove that the data delivery latency for IPS is upper-bounded by (⌊2πarccos(11+∊)⌋+3)R+Δ-4, where R is the network radius, Δ is the maximum node degree, and 0.05<∊⩽1. The simulation results show that IPS outperforms seven competing state-of-the-art aggregation scheduling algorithms in terms of latency and network lifetime.