CONSTRUCTION OF OPTIMAL WIRE SENSOR NETWORK FOR THE AREA OF COMPLEX SHAPE

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.