| Title:
|
Solving the sensor cover energy problem via integer linear programming (English) |
| Author:
|
Li, Pingke |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
57 |
| Issue:
|
4 |
| Year:
|
2021 |
| Pages:
|
568-593 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
sensor coverage problem |
| Keyword:
|
max-plus algebra |
| Keyword:
|
integer linear programming |
| MSC:
|
15A80 |
| MSC:
|
52C15 |
| MSC:
|
90C10 |
| idZBL:
|
Zbl 07478629 |
| DOI:
|
10.14736/kyb-2021-4-0568 |
| . |
| Date available:
|
2021-11-04T12:53:24Z |
| Last updated:
|
2022-02-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149209 |
| . |
| Reference:
|
[1] Astorino, A., Miglionico, G.: Optimizing sensor cover energy via DC programming..Optim. Lett. 10 (2016), 2, 355-368. |
| Reference:
|
[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. 10.1145/2240092.2240098 |
| Reference:
|
[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms..Springer, Berlin 2010. Zbl 1202.15032 |
| Reference:
|
[4] Elbassioni, K. M.: A note on systems with max-min and max-product constraints..Fuzzy Sets Syst. 159 (2008), 2272-2277. |
| Reference:
|
[5] Fredman, M. L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms..J. Algorithms 21 (1996), 618-628. |
| Reference:
|
[6] Hoai, P. T., Tuy, H.: Monotonic optimization for sensor cover energy problem..Optim. Lett. 12 (2018), 1569-1587. |
| Reference:
|
[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. |
| Reference:
|
[8] Thi, H. A. Le, Pham, D. T.: DC programming and DCA: thirty years of developments..Math. Program., Ser. B 169 (2018), 5-68. |
| Reference:
|
[9] Li, P.: Fuzzy Relational Equations: Resolution and Optimization..Ph.D. Dissertation, North Carolina State University 2009. |
| Reference:
|
[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. Zbl 1169.90493, |
| Reference:
|
[11] Li, P., Fang, S.-C.: Latticized linear optimization on the unit interval..IEEE Trans. Fuzzy Syst. 16 (2009), 6, 1353-1365. |
| Reference:
|
[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. |
| Reference:
|
[13] ReVelle, C. S.: Facility siting and integer-friendly programming..Eur. J. Oper. Res. 65 (1993), 2, 147-158. |
| Reference:
|
[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. |
| Reference:
|
[15] Wang, B.: Coverage problems in sensor networks: A survey..ACM Comput. Surv. 43 (2011), 4, Article 32. 10.1145/1978802.1978811 |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1145/1464420.1464428 |
| . |
