Data aggregation, gathering and gossiping in duty-cycled multihop wireless sensor networks subject to physical interference

Data aggregation, gathering and gossiping are all vital communication tasks in wireless sensor networks (WSNs). When all networking devices are always active, scheduling algorithms for these communication tasks have been extensively investigated under both the protocol and physical interference models. However, wireless devices usually switch between the sleep state and the active state for the purpose of energy saving. A networking device with duty-cycled scenarios having sleep/awake cycles may need to transmit the message to all neighbors more than once. Taking the duty-cycled scenarios into consideration, communication scheduling algorithms for these tasks have been extensively investigated under the protocol interference model. As far as we know, scheduling algorithms for these communication tasks have not yet been investigated in WSNs with duty-cycled scenarios under the physical interference model. In this paper, we propose minimum latency scheduling algorithms for these communication tasks in duty-cycled WSNs under the physical interference model. Our innovative scheduling algorithms for both data gathering and gossiping achieve approximation ratios at most a constant time of |T|, where |T| is the length of a scheduling period. The approximation ratio of our proposed data aggregation scheduling algorithm is less than or equal to a constant times |T| with bounded maximum degree of the network