Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks
- 1
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.