Construction of optimal wire sensor network for the area of complex shape

Authors

DOI:

https://doi.org/10.15587/1729-4061.2016.86171

Keywords:

circular coverage, area of complex shape, trace routing, means of modeling, construction of mathematical model, nonlinear optimization

Abstract

The study is devoted to the problem of designing wire sensory networks for the areas of arbitrary shape. The problem is posed as the construction of the optimum coverage of an area with circles of the equal radii, connected by routes. The purpose is to reduce the total cost of the construction of sensory network to minimum. For developing the effective algorithms in this field, it is necessary to construct the mathematical models, which are based on analytical description of relationships between the objects. The coverage restrictions are described in the work with the help of the phi-functions free from radicals and the new class of functions of belonging of points to areas. For modeling different relationships between the objects we proposed: pseudonormalized functions of belonging of points to areas, functions of quasi-belonging of points to areas, normalized functions of quasi-belonging of points to areas and pseudonormalized functions of quasi-belonging of points to areas. The mathematical model, constructed with the application of new means of modeling, is in the general case the problem of the non-smooth optimization. The strategy of the solution, which includes the algorithm for generation of starting points from the area of permissible solutions of the problem and the optimization procedure, is proposed. Starting points are constructed with the help of heuristic methods. The construction of the starting point includes the stage of the construction of circular coverage and the stage of trace routing. The procedure of the search for the local extrema, which reduces the problem of non-smooth optimization to the sequence of problems of nonlinear programming, was proposed. As a result of the conducted study, the approach, which makes it possible to use contemporary NLP-solvers in the search for the local-optimum solutions of the joint problem of circular coverage and trace routing of wire connections, was proposed. The proposed approach can be easily adapted to solving other problems of covering areas with identical circles. In particular, the problem of the minimization of radii of covering circles for areas with the curvilinear boundary was solved.

Author Biographies

Oleksiy Antoshkin, National University of Civil Protection of Ukraine Chernishevska str., 94, Kharkiv, Ukraine, 61023

Lecturer

Department of automated security systems and information technologies

Alexander Pankratov, A. N. Podgorny Institute for Mechanical Engineering Problems NAS of Ukraine Dm. Pozharsky str., 2/10, Kharkiv, Ukraine, 61046

Doctor of Technics, Senior Researcher

Department for Mathematical Modeling

References

  1. Wang, B. (2011). Coverage problems in sensor networks. ACM Computing Surveys, 43 (4), 1–53. doi: 10.1145/1978802.1978811
  2. Yadav, J., Mann, S. (2003). Coverage in wireless sensor networks: A survey. Int. J. Electron. Comput. Sci. Eng., 2, 465–471.
  3. Sangwan, A., Singh, R. P. (2014). Survey on Coverage Problems in Wireless Sensor Networks. Wireless Personal Communications, 80 (4), 1475–1500. doi: 10.1007/s11277-014-2094-3
  4. Eremeev, A. V., Zaozerskaya, L. A., Kolokolov, A. A. (2000). Zadacha o pokrytii mnozhestva: slozhnost', algoritmy, ehksperimental'nye issledovaniya. Diskretnyj analiz i issledovanie operacij. Ser. 2, 7 (2), 22–46.
  5. So, A. M.-C., Ye, Y. (2005). On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams. Internet and Network Economics, 584–593. doi: 10.1007/11600930_58
  6. Chizari, H., Hosseini, M., Poston, T., Razak, S. A., Abdullah, A. H. (2011). Delaunay Triangulation as a New Coverage Measurement Method in Wireless Sensor Network. Sensors, 11 (12), 3163–3176. doi: 10.3390/s110303163
  7. Pankratov, A. V., Pacuk, V. N., Romanova, T. E. (2002). Metod regulyarnogo pokrytiya pryamougol'noj oblasti krugami zadannogo radiusa. Radioehlektronika i informatika, 1 (18), 50–52.
  8. Lazos, L., Poovendran, R. (2006). Stochastic coverage in heterogeneous sensor networks. ACM Transactions on Sensor Networks, 2 (3), 325–358. doi: 10.1145/1167935.1167937
  9. Hall, P. (1988). Introduction to the Theory of Coverage Processesl. John Wiley & Sons Incorporated, 432.
  10. Liu, X., He, D. (2014). Ant colony optimization with greedy migration mechanism for node deployment in wireless sensor networks. Journal of Network and Computer Applications, 39, 310–318. doi: 10.1016/j.jnca.2013.07.010
  11. Xunbo, L., Zhenlin, W. (2011). Cellular genetic algorithms for optimizing the area covering of wireless sensor networks. C. J. of Electronics, 20 (2), 352–356.
  12. Lanza, M., Gutierrez, A. L., Perez, J. R., Morgade, J., Domingo, M., Valle, L. et. al. (2014). Coverage Optimization and Power Reduction in SFN Using Simulated Annealing. IEEE Transactions on Broadcasting, 60(3), 474–485. doi: 10.1109/tbc.2014.2333131
  13. Stoyan, Yu. G., Pacuk, B. H. (2006). Pokrytie mnogougol'noj oblasti minimal'nym kolichestvom odinakovyh krugov zadannogo radiusa. Dop. NAN Ukraini, 3, 74–77.
  14. Komyak, V., Pankratov, A., Patsuk, V., Prikhodko, A. (2016). The problem of covering the fields by the circles in the task of optimization of observation points for ground video monitoring systems of forest fires. An international quarterly journal, 5 (2), 133–138.
  15. Tarnai T., Gaspar, Zs. (1995). Covering a square by equal circles. Elem. Math, 50, 167–170.
  16. Brusov, B. C., Piyavskij, S. A. (1971). Vychislitel'nyj algoritm optimal'nogo pokrytiya oblastej ploskosti. Zhurnal vychislitelnoy matematiki i matematicheskoy fiziki, 11 (2), 304–312.
  17. Jandl, H., Wieder, K. (1988). A continuous set covering problem as a quasidifferentiable optimization problem. Optimization, 19 (6), 781–802. doi: 10.1080/02331938808843392
  18. Kiseleva, E. M., Lozovskaya, L. I., Timoshenko, E. V. (2009). Reshenie nepreryvnyh zadach optimal'nogo pokrytiya sharami s ispol'zovaniem teorii optimal'nogo razbieniya mnozhestv. Kibernetika i sistemnyj analiz, 3, 98–117.
  19. Ushakov, V. N., Lebedev, P. D. (2016). Algoritmy optimal'nogo pokrytiya mnozhestv na ploskosti R2. Vestn. Udmurtsk. un-ta. Matem. Mekh. Komp'yut. nauki, 26 (2), 258–270.
  20. Antoshkin, A. A., Romanova, T. E. (2002). Matematicheskaya model' zadachi pokrytiya vypukloj mnogougol'noj oblasti krugami s uchetom pogreshnostej iskhodnyh dannyh. Problems of mechanical engineering, 5 (1), 56–60.
  21. Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T. (2008). Tools of mathematical modeling of arbitrary object packing problems. Annals of Operations Research, 179 (1), 343–368. doi: 10.1007/s10479-008-0456-5
  22. Groër, C., Golden, B., Wasil, E. (2010). A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation, 2 (2), 79–101. doi: 10.1007/s12532-010-0013-5
  23. Wächter, A., Biegler, L. T. (2005). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106 (1), 25–57. doi: 10.1007/s10107-004-0559-y
  24. Ushakov, V. N., Lahtin, A. S., Lebedev, P. D. (2006). Optimizaciya hausdorfova rasstoyaniya mezhdu mnozhestvami v evklidovom prostranstve. Tr. IMM UrO RAN, 20 (3), 291–308.

Downloads

Published

2016-12-27

How to Cite

Antoshkin, O., & Pankratov, A. (2016). Construction of optimal wire sensor network for the area of complex shape. Eastern-European Journal of Enterprise Technologies, 6(4 (84), 45–53. https://doi.org/10.15587/1729-4061.2016.86171

Issue

Vol. 6 No. 4 (84) (2016): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2016 Oleksiy Antoshkin, Alexander Pankratov

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.