Article
Full entry |
PDF
(7.2 MB)
Feedback
PDF
(7.2 MB)
Feedback
Keywords:
sensor coverage problem; max-plus algebra; integer linear programming
sensor coverage problem; max-plus algebra; integer linear programming
Summary:
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.
References:
[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 10.1145/2240092.2240098
[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. Zbl 1202.15032
[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 1169.90493
[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 10.1145/1978802.1978811
[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 10.1145/1464420.1464428
Search
Partner of
