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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.