Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks

Roberto Montemanni

.

DOI: 10.4236/wsn.2010.212111                

Abstract

Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.

Keywords

Sensor Networks, Mixed Integer Linear Programming, Energy Models, Topology Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. Negri, D. Zanetti, R. Montemanni and S. Giordano, “Power-optimized Topology Formation and Configura- tion in Bluetooth Sensor Networks: an Experimental App- roach,” Ad-Hoc and Sensor Wireless Networks, Vol. 6, No. 1-2, 2008, pp. 145-175.
[2]	W. Ye, J. Heidemann and D. Estrin, “An Energy-efficient MAC Protocol for Wireless Sensor Networks,” IEEE Infocom Proceedings, New York, 23-27 June 2002, pp. 1567-1576.
[3]	A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, “Wireless Sensor Networks for Habitat Moni- toring,”, Proceedings of the 1st ACM international work- shop on Wireless sensor networks and applications con- ference, Atlanta, 28 Sepmeber 2002, pp. 88-97
[4]	S. Kim, S. Pakzad, D.E. Culler, J. Demmel, G. Fenves, S. Glaser, and M. Turon, “Health monitoring of civil infras- tructures using wireless sensor networks,” Proceedings of the IEEE Information Processing in Sensor Networks Conference, Cambridge, 25-27 April 2007, pp. 254-263.
[5]	D. M. Doolin and N. Sitar, “Wireless Sensors for Wild- fire Monitoring,” Proceedings of the Sensors and smart structures technologies for civil, mechanical, and aero- space systems conference, San Diego, 7-10 March 2005, pp. 477-484.
[6]	I. Chlamtac, C. Petrioli and J. Redi, “Energy- conserving Access Protocols for Identification Net- works,” IEEE Transactions on Networking, Vol. 7, No. 1, 1999, pp. 51- 59.
[7]	D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challanges: Scalable Coordination in Sen- sor Networks,” Mobicom Proceedings, Seattle, 15-19 Au- gust 1999, pp. 263-270.
[8]	S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “TAG: a Tiny Aggregation Service for Ad-hoc Sensor Networks,” Proceedings of the 5th Annual Sym- posium on Operating Systems Design and Implementa- tion conference, Boston, 9-11 December 2002, pp. 131-146.
[9]	W. Heinzelman, A. Chandrakasan, and H. Balakrish- nan, “Energy-efficient Communication Protocols for Wireless Microsensor Networks,” Proceedings of the 33th Hawaii International International Conference on Systems Sci- ence, Hawaii, 4-7 January 2000, p. 8020.
[10]	S. Singh and C. S. Raghavendra, “Power Aware Multi- access Protocol with Signalling for Ad Hoc Networks,” Computer Communication Review, Vol. 25, No. 3, 1998, pp. 5-26.
[11]	R. Montemanni, L. M. Gambardella and A. K. Das, “The Minimum Power Broadcast Problem in Wireless Net- works: a Simulated Annealing Approach,” Proceedings of the IEEE Wireless and Communications and Networking Con- ference, New Orleans, 13-17 March 2005, pp. 2057- 2062.
[12]	I. Stojmenovic, M. Seddigh and J. Zunic, “Internal Nodes Based Broadcasting in Wireless Networks,” Proceedings of the 34th Hawaii International International Con- ference on Systems Science, Maui, 3-6 January 2001, p. 9005.
[13]	J. Wieselthier, G. Nguyen and A. Ephremides, “On the Construction of Energy-efficient Broadcast and Multicast Trees in Wireless Networks,” Proceedings of the IEEE Infocom conference, Tel-Aviv, 26-30 March 2000, pp. 585-594.
[14]	P. Basu and J. Redi, “Effect of Overhearing Trans- missions on Energy Efficiency in Dense Sensor Net- works,” Proceedings of the IEEE Information Processing in Sensor Networks Conference, California, 26-27 April 2004, pp. 196-204.
[15]	E. S. Biagioni and G. Sasaki, “Wireless Sensor Placement for Reliable and Efficient Data Collection,” Proceedings of the 36th Hawaii International International Con- ference on Systems Science, Hawaii, 6-9 January 2003, p. 127.2.
[16]	A. K. Das, M. El-Sharkawi, et al., “Maximization of Time-to-first-failure for Multicasting in Wireless Net- works: Optimal Solution,” IEEE Milcom Proceedings, Vol 3, 2004, pp. 1358-1363.
[17]	R. Montemanni, “Maximum Lifetime Broadcasting Topologies in Wireless Sensor Networks: Advanced Mathematical Programming Models,” Proceedings of the 42nd Hawaii International International Conference on Systems Science, Hawaii, 5-8 January 2009.
[18]	V. Leggieri, P. Nobili, and C. Triki, “Minimum Power Multicasting Problem in Wireless Networks,” Mathemati- cal Methods of Operations Research, Vol. 68, No. 2, 2008, pp. 295-311.
[19]	G. B. Dantzig, D. R. Funkerson, and S. Johnson. “Solu- tion of a Large-scale Traveling Salesman Problem,” Jour- nal of the Operations Research Society of America, Vol. 2, No. 4, 1954, pp. 393-410.
[20]	J. Bauer, D. Haugland and D. Yuan, “Analysis and Com- putational Study of Several Integer Programming Formu- lations for Minimum-energy Multicasting in Wire- less Ad Hoc Networks,” Networks, Vol. 52, No. 2, 2008, pp. 57-68.
[21]	R. Montemanni and L. M. Gambardella, “Minimum Po- wer Symmetric Connectivity Problem in Wireless Net- works: a New Approach,” Proceedings of the Mobile and Wireless Communication Networks Conference, Paris, 25-27 October, 2004, pp. 496-508.
[22]	H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs,” Combin- atorica, Vol. 6, No. 2, 1986, pp. 109-122.