Counting the minimum node weight spanning trees for broadcast transmission in wireless sensor networks

Jolanta Tańcuła


Article presents algorithm optimizing power consumption for broadcast in sensor networks. The broadcast allows of sending data to all ports connected to a given network. Wireless sensor networks are built of distributed measuring devices. Each sensor is an autonomous unit, operating independently of the other. They have limited energy resources. Energy management is of key importance for sensors. In this article, we will create a sensor network model with one broadcast node. For this network we will use an algorithm finding minimum node weight spanning tree for which energy consumption will be the smallest.


minimum spanning tree; broadcast transmission

Full Text:



Even S.: Algorithmic Combinatorics. The Macmillan Company, 1973.

Gavril F.: Generating the Maximum Spanning Trees of a Weighted Graph. Journal of Algorithms, vol. 8, issue 4, 1987, p. 592÷597.

Berge C.: Graphs.North, Holland, 1989.

Tamaghna A., Goutam P.: Maximum Lifetime Broadcast Communications in Cooperative Multihop Wireless Ad-hoc Networks: Centralized and Distributed Approaches. Ad Hoc Network 11, 2013, p. 1667÷1682.

Wieselthier J.E., Nguyen G.D.: Algorithms for Energy-Efficient Multicasting in Static Ad-hoc Wireless Networks. Mobile Networks and Applications 6, 2001, p. 251÷263.

Guofeng D., Gupta K.S.: Maximizing Broadcast Tree Lifetime in Wireless Ad Hoc Networks. Global Telecommunications Conference, 2006.

Kang I., Poovendran R.: Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Network. Mobile Networks and Applications 10, 2005, p. 879÷896.

Lee S.H., Radzik T.: Improved Approximation Bounds for Maximum Lifetime Problems in Wireless Ad-hoc Network. ADHOC-NOW 2012, Springer LNCS,vol. 7363, 2012, p. 14÷27.

Nunes B., Barboza F., Assis F.: Maximum Lifetime Broadcast in Mobile Sensor Networks. ADHOC-NOW 2013, Springer LNCS, vol. 7960, 2013, p. 26÷37.

Broder A., Mayr E.W.: Counting Minimum Weight Spanning Trees. Journal of Algorithm 24, 1997, p. 171÷176.