Construction of the minimal dominating set in the design of wi-fi-network

Currently, wireless technology is becoming the preferred, and in some cases the only possible for the information communication devices. If you need coverage of a large space with a complex configuration arises the need to efficiently host multiple Wi-Fi emitters, providing a stable connection with each possible location of the receiver signals. Suppose we have a model that allows to determine the coverage of a stable connection Wi-Fi emitter at a given spatial point. Then the problem of locating Wi-Fi emitters can be formulated as determining a discrete set of locations of transducers satisfying the condition. Otherwise, it is necessary to determine the positions of all the emitters that completely cover a given area, and the number of emitters should be minimal. In this formulation it is the task of the lowest coverage – the problem of finding the smallest set of columns of the matrix, "covering" all of her lines. To develop methods for solving a problem of the smallest covering usually resort to its matrix interpretation, which reduces to the problem of the smallest dominating set of a graph. From the point of view of the formulation of the problem of the smallest covering two cases are possible configuration of the coverage area of the surrounding space Wi-Fi emitters: 1. without variable. Its peculiarity is that the coverage area is completely defined by the location of the emitter. It is possible in the case where the coverage area of the symmetric or the orientation of the directivity diagram of the radiation is fixed. In this case it is possible to build a graph associated with the set of locations of emitters in which each point of placement are associated with adjacent vertices. In this formulation we arrive at the problem of the smallest dominating set of a graph. 2. Variable. It takes place in the case when the diagram of radiation is directed, and the coverage area may vary depending on the orientation of the emitter. That is, the actual emitter can be deployed in an infinite number of different provisions, but the limb covered points significantly limits the number of different orientations. In this case, each point position of the transmitter can be put into correspondence with several matrix rows and cover each point will correspond to exactly one column.