Kybernetika 57 no. 4, 568-593, 2021

Solving the sensor cover energy problem via integer linear programming

Pingke LiDOI: 10.14736/kyb-2021-4-0568

Abstract:

This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated instances and demonstrates that it is capable of solving large size instances of the sensor cover energy problem.

Keywords:

max-plus algebra, sensor coverage problem, integer linear programming

Classification:

90C10, 15A80, 52C15

paper.pdf

References:

  1. A. Astorino and G. Miglionico: Optimizing sensor cover energy via DC programming. Optim. Lett. 10 (2016), 2, 355-368.   DOI:10.14257/ijsh.2016.10.6.35
  2. N. Bartolini, T. Calamoneri, T. La Porta, C. Petrioli and S. Silvestri: Sensor activation and radius adaptation (SARA) in heterogeneous sensor networks. ACM Trans. Sensor Netw. 8 (2012), 3, Article 24.   CrossRef
  3. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010.   CrossRef
  4. K. M. Elbassioni: A note on systems with max-min and max-product constraints. Fuzzy Sets Syst. 159 (2008), 2272-2277.   DOI:10.1016/j.fss.2008.02.020
  5. M. L. Fredman and L. Khachiyan: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21 (1996), 618-628.   DOI:10.1006/jagm.1996.0062
  6. P. T. Hoai and H. Tuy: Monotonic optimization for sensor cover energy problem. Optim. Lett. 12 (2018), 1569-1587.   DOI:10.1007/s11590-017-1219-5
  7. H. A. Le Thi and D. T. Pham: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133 (2005), 23-46.   DOI:10.1007/s10479-004-5022-1
  8. H. A. Le Thi and D. T. Pham: DC programming and DCA: thirty years of developments. Math. Program., Ser. B 169 (2018), 5-68.   DOI:10.1007/s10107-018-1235-y
  9. P. Li: Fuzzy Relational Equations: Resolution and Optimization. Ph.D. Dissertation, North Carolina State University 2009.   DOI:10.1002/ss.328
  10. P. Li and S.-C. Fang: On the resolution and optimization of a system of fuzzy relational equations with sup-$T$ composition. Fuzzy Optim. Decis. Making 7 (2008), 169-214.   DOI:10.1007/s10700-008-9029-y
  11. P. Li and S.-C. Fang: Latticized linear optimization on the unit interval. IEEE Trans. Fuzzy Syst. 16 (2009), 6, 1353-1365.   CrossRef
  12. R. Priyadarshi, B. Gupta and A. Anurag: Deployment techniques in wireless sensor networks: a survey, classification, challenges, and future research issues. J. Supercomput. 76 (2020), 7333-7373.   DOI:10.1007/s11227-020-03166-5
  13. C. S. ReVelle: Facility siting and integer-friendly programming. Eur. J. Oper. Res. 65 (1993), 2, 147-158.   DOI:10.1016/0377-2217(93)90329-L
  14. H. Tuy, M. Minoux and N. T. H. Phuong: Discrete monotonic optimization with application to a discrete location problem. SIAM J. Optim. 17 (2006), 78-97.   DOI:10.1137/04060932X
  15. B. Wang: Coverage problems in sensor networks: A survey. ACM Comput. Surv. 43 (2011), 4, Article 32.   CrossRef
  16. Y. Wang, S. Wu, Z. Chen, X. Gao and G. Chen: Coverage problem with uncertain properties in wireless sensor networks: A survey. Comput. Netw. 123 (2017), 200-232.   DOI:10.1016/j.comnet.2017.05.008
  17. Z. Zhou, S.R. Das and H. Gupta: Variable radii connected sensor cover in sensor networks. ACM Trans. Sensor Netw. 5 (2009), 1, Article 8.   CrossRef