Geodesic
Solving the sensor cover energy problem via integer linear programming
Kybernetika, Tome 57 (2021) no. 4, pp. 568-593
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2021-4-0568
Classification : 15A80, 52C15, 90C10
Keywords: sensor coverage problem; max-plus algebra; integer linear programming 
@article{10_14736_kyb_2021_4_0568,
     author = {Li, Pingke},
     title = {Solving the sensor cover energy problem via integer linear programming},
     journal = {Kybernetika},
     pages = {568--593},
     year = {2021},
     volume = {57},
     number = {4},
     doi = {10.14736/kyb-2021-4-0568},
     zbl = {07478629},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-4-0568/}
}
TY  - JOUR
AU  - Li, Pingke
TI  - Solving the sensor cover energy problem via integer linear programming
JO  - Kybernetika
PY  - 2021
SP  - 568
EP  - 593
VL  - 57
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-4-0568/
DO  - 10.14736/kyb-2021-4-0568
LA  - en
ID  - 10_14736_kyb_2021_4_0568
ER  - 
%0 Journal Article
%A Li, Pingke
%T Solving the sensor cover energy problem via integer linear programming
%J Kybernetika
%D 2021
%P 568-593
%V 57
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2021-4-0568/
%R 10.14736/kyb-2021-4-0568
%G en
%F 10_14736_kyb_2021_4_0568
Li, Pingke. Solving the sensor cover energy problem via integer linear programming. Kybernetika, Tome 57 (2021) no. 4, pp. 568-593. doi: 10.14736/kyb-2021-4-0568

[1] Astorino, A., Miglionico, G.: Optimizing sensor cover energy via DC programming. Optim. Lett. 10 (2016), 2, 355-368. | DOI

[2] Bartolini, N., Calamoneri, T., Porta, T. La, Petrioli, C., Silvestri, S.: Sensor activation and radius adaptation (SARA) in heterogeneous sensor networks. ACM Trans. Sensor Netw. 8 (2012), 3, Article 24. | DOI

[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. | Zbl

[4] Elbassioni, K. M.: A note on systems with max-min and max-product constraints. Fuzzy Sets Syst. 159 (2008), 2272-2277. | DOI

[5] Fredman, M. L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21 (1996), 618-628. | DOI

[6] Hoai, P. T., Tuy, H.: Monotonic optimization for sensor cover energy problem. Optim. Lett. 12 (2018), 1569-1587. | DOI

[7] Thi, H. A. Le, Pham, D. T.: 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

[8] Thi, H. A. Le, Pham, D. T.: DC programming and DCA: thirty years of developments. Math. Program., Ser. B 169 (2018), 5-68. | DOI

[9] Li, P.: Fuzzy Relational Equations: Resolution and Optimization. Ph.D. Dissertation, North Carolina State University 2009. | DOI

[10] Li, P., Fang, S.-C.: 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 | Zbl

[11] Li, P., Fang, S.-C.: Latticized linear optimization on the unit interval. IEEE Trans. Fuzzy Syst. 16 (2009), 6, 1353-1365.

[12] Priyadarshi, R., Gupta, B., Anurag, A.: Deployment techniques in wireless sensor networks: a survey, classification, challenges, and future research issues. J. Supercomput. 76 (2020), 7333-7373. | DOI

[13] ReVelle, C. S.: Facility siting and integer-friendly programming. Eur. J. Oper. Res. 65 (1993), 2, 147-158. | DOI

[14] Tuy, H., Minoux, M., Phuong, N. T. H.: Discrete monotonic optimization with application to a discrete location problem. SIAM J. Optim. 17 (2006), 78-97. | DOI

[15] Wang, B.: Coverage problems in sensor networks: A survey. ACM Comput. Surv. 43 (2011), 4, Article 32. | DOI

[16] Wang, Y., Wu, S., Chen, Z., Gao, X., Chen, G.: Coverage problem with uncertain properties in wireless sensor networks: A survey. Comput. Netw. 123 (2017), 200-232. | DOI

[17] Zhou, Z., Das, S.R., Gupta, H.: Variable radii connected sensor cover in sensor networks. ACM Trans. Sensor Netw. 5 (2009), 1, Article 8. | DOI

Cité par Sources :