Thang Le Duc, Duc Tai Le, Vyacheslav V.Zalyubovskiy, Dongsoo S. Kim, Hyunseung Choo
International Journal of Communication Systems, vol.28, January. 2015 (SCI, IF:1.106)
Broadcast is an essential operation in wireless sensor networks. Because of the necessity of energy conservation, minimizing the number of transmissions is always a challenging issue in broadcasting scheme design. This paper studies the minimum-transmission broadcast problem in duty-cycled wireless sensor networks where each sensor operates under active/dormant cycles. To address the problem, our proposed scheme, Broadcast Redundancy Minimization Scheduling (BRMS), finds a set of forwarding nodes, which minimizes the number of broadcast transmissions. Then, it constructs a forest of sub-trees based on the relationship between each forwarding node and its corresponding receivers. A broadcast tree is constructed ultimately by connecting all sub-trees with a minimum number of connectors. Theoretical analysis shows that BRMS obtains a lower approximation ratio as well as time complexity compared with existing schemes. A set of extensive simulations is conducted to evaluate the performance of BRMS. The results reveal that BRMS outperforms others and its solution is close to the lower bound of the problem in terms of the total number of transmissions.
Broadcast, Duty cycle, Wireless sensor network, Scheduling, Approximation algorithm