Wireless network development as an optimization problem

Размещено на http://www.allbest.ru/

WIRELESS NETWORK DEVELOPMENT AS an OPTIMIZATION PROBLEM

Kazakovtsev L.A.

Krasnoyarsk State Agricultural University,

Krasnoyarsk, Russia

Wireless networks of various size are the most obtainable means of the telecommunication infrastructure development for sparsely populated rural areas and often, they are the only available means in case of territories of the Far North. In this work, we consider an approach to the spatial pattern optimization of the developed wireless network based on the variant probability method.

INTRODUCTION

wireless access points north

Rural areas and sparsely populated territories with underdeveloped infrastructure need a special approach for solving the problem of supply with the telecommunication facilities. An uninterrupted rapid growth of the telecommunication networks including qualitative increasing of data channels bandwidth and quality of service is mostly typical for the megapolises and densely populated territories but it is least apparent in remote and sparsely populated regions where the networks are nevertheless important. On the one hand, the absence of any infrastructure (not only telecommunication one but also traditional telephone lines, power transmission lines and roads along which the telecommunication cable infrastructure are usually laid) embarrasses the development of the traditional cable infrastructure. The implementation of ADSL technology using the existing cable infrastructure is also impossible. On the other hand, the necessity to supply that territories with the qualitative network access is dictated by the standards (written or de-facto ones) of the office work and business processes of various business, governmental, educational and research organizations. Furthermore, the remote territories need a qualitative communications which makes them 'nearer' to the 'big earth' even more than the central regions because this is the only way to establish contacts with the partners, to realize centralized management and even to make simple things like bank transfer. In conditions of the Northern Siberia, the existence of any serious cable infrastructure is often absolutely impossible even within small territories because of permafrost, bogs, moving soil. By the way, this problem embarrasses also the placing of wireless base stations, nevertheless, only the wireless technologies have any the serious perspectives at these territories.

Certainly, the satellite technologies allow to establish the Internet access, telephone connection and everything else at every point but they are expensive. That is why, the local area networks (often covering large territories) are usually developed with WiFi technology (often, in addition to cable or VSAT equipment as a gateway to WAN).

Often, such networks are developed chaotic as far as an exigency to cover new territories arises. The equipment (especially arctic versions of devices) is not too cheap. The superfluous quantity of access points does not do much good because of interference and frequency sharing problems but this problem is less important for sparsely populated territories. The execution of the field testing of radio propagation properties of medium and its geometry needs special equipment, skilled personnel and significant expenditure of time. Meanwhile, the maximum usage of available information (even if it is not precise) of signal and noise levels at different points and RF absorbing properties of medium acquired from the working wireless network hardware is able to help with the search of the optimal configuration of new elements of the growing network. The same is actual for the wireless networks which are developed chaotic at the large built-up territories (for example, reconstructed territories of the former agricultural or industrial enterprises).

In this work, we consider a method of searching of the direction of a wireless network development (the places of new access points or base stations etc.) optimized with criteria of coverage of important territories and minimum cost of equipment and additional needed infrastructure which does not need any special field testing and determination of the exact geometry of elements of radio propagation medium and their RF absorbing properties but takes into account the minimum accessible information obtained from built-in measuring instruments of wireless hardware and approximate data of the medium elements shape. The problem of search of a disposition and types of the infrastructure elements of the growing network is formulated as a multi-criteria discrete constrained optimization problem solvable with variant probability method [1]. The problem of a radio propagation medium properties modeling is also formulated and solved as a discrete optimization task.

RELATED WORKS

The considered problem of optimal access points placement is often a subject of the engineers and network administrators in the Internet forums and scientific publications. Some of them offer ready-to use software able to forecast the signal coverage in accordance with the physical properties of the environment elements. Other scientific works offer various methods of search of new access points placement with optimal signal coverage [2, 3] or (come complex case) placement which provides for the best localization of a mobile WLAN equipment position (calculation of its coordinates) within the area of coverage of the network [4, 5]. The prognosis of signal level at each point taking into consideration the path loss of walls, ceilings and other elements is a well known engineering problem [7].

The recent literature proposes and approves many techniques to analyze the indoor and outdoor signal coverage problem and different deterministic and stochastic optimization methods to find the optimal placement.

In [2], author a version of the Nelder-Mead simplex method and a pattern algorithm that considers the minimization of the ratio of covered points in a mesh.

In [3], there is a method of design of large-scale indoor network where placement of the access points guarantees the absence of the gaps. The optimal signal coverage area of an AP is considered as a cylinder and the AP positions are optimized with usage of geometrical schemes.

Using the empirical Motley-Keenan indoor wave propagation model taking into consideration the type of walls and ceilings to calculate the path loss, [6] proposes an AP placement technique for optimal inside signal coverage. Genetic algorithm is used to find a configuration with less value of maximum path loss for each point.

In [8], authors also propose a strongly typed genetic programming to solve access point configuration problem with optimal disposition of the access points providing the best coverage.

In [4], they use genetic algorithms to find the disposition of access points which gives the optimal localization of the mobile device within some area covered by access points. In [5], they propose a ready-to-use system for the localization of such device.

In our case, the optimal coverage is one of the objectives. The second important one is the minimum cost of the wireless equipment and infrastructure needed to make this equipment work. The results of the above methods are hard to interpret when the 'optimal' placement of an access point is situated far from the electric wiring, walls or other constructions where we are able to install the equipment. The transferal of the resulting position of the access point to the nearest possible place may significantly change the forecast of coverage. The erecting work is possible during a very short period of the year in Siberian weather conditions but we do not know when the necessity to change our network configuration arises.

Most of above works are based on the signal propagation model which considers the logarithmic loss of each obstacle (walls, ceilings) from some information tables but often, we do not know even the exact building material of our environment elements and their exact geometry and the real absorption may differ very significant. In [4], they propose to use the least-squares fit on experimental data to determine the real path loss produced by the obstacles. But we may have enough or not enough experimental data which are needed for the least-squares method and it may be difficult to obtain the additional data.

AVAILABLE INFORMATION

The minimum information we need is the level of the signal and noise in different points. At least, the information of the signal and noise levels at the points where the network is already working is able to acquire from the network equipment (for example, in Linux, the iwconfig utility gives us such information). The minimum information of the environment geometry (the disposition of walls, trees and other objects) is always available from maps, schemes or immediate visual observation. The RF absorbing properties of the environment elements are available from the information tables [8] and able to be defined more exactly if the element is situated between the existing transmitter and receiver or in the Fresnel zone. In complex cases, the absorbing properties can be specified as a solution of the below optimization problem.

Also, we have an information about the possibility and the approximate cost to allocate the new access point at each place. So, the places where we have an electric wiring (at least, the places with the existing client wireless hardware) are more suitable to set the new access points than outdoor ones distant from the buildings and power supply infrastructure. Moreover, the researcher is able to set some number of possible places of the new access points in accordance to the reasons which are evident for him but hard to be formalized.

SUPPOSITIONS, SIMPLIFICATIONS

Figure 1. Fragment of the scheme of equipment placement and environment elements in discrete coordinates

So, we have the information about the approximate geometry of the environment (disposition of the existing equipment, disposition of the obstacles for propagation and their presumable RF absorption properties) and the data of signal and noise levels at some points.

To simplify calculations, let's divide our area into cells. As a rule, the real problems do not allow us to ignore the vertical positional relationship of the infrastructure and environment elements. That is why, we should consider our environment as a 3D space. For the simplicity of the statement and representation at the paper, we consider 2-dimensional case.

Let's consider that the equipment is situated in the centers of the cells and the borders of the environment elements (obstacles such as walls, windows, trees etc.) coincide with the borders of any set of the cells. So, we draw the scheme of our environment with the existing and new access points and obstacles and existing and perspective zones of coverage of our network as if we mark the elements in the checked writing-book (Fig.1). If we have an information about the signal level at some place then we suppose that this level is equal for the whole cell.

If our network contains directional antennas then we suppose then the signal of such antenna is propagated within the area bounded with an angle (excluding pairs of beam transmission antennas, in this case, we suppose suppose that the area of propagation includes only 2 cells where 2 antennas are situated).

PROBLEM STATEMENT

Let there be several areas in our scheme which need to become the consistent reception (consistent coverage) areas. Moreover, certain areas are most important, other ones are desirable to supply the consistent coverage but it is not so important. We define the weight coefficient for each of these areas. Besides, we are allowed to demand some minimum bit rate for one or another area. Thus, we have N_c cells where we need to supply the coverage with the weight coefficients v_j and minimum bitrates b_j, 1? j? N_c.

Let there be N_p points (cells) where we are able to place the access points. For each of these cells, we take into consideration N_t types of hardware (various antennas, amplifiers etc). For each of these places, we know also the approximate cost of infrastructure equipment (such as power supply wires or self-contained power supply, antenna holders etc.) C_i, 1? i?N_p and the cost of each kind of the hardware C_k is also known, 1?k?N_c.

Let's define a matrix X of Boolean variables x_ik. Setting the value of the variable x_ik to 1 means that we decided to place the access point hardware of k-th type within the i-th possible cell and setting its value x_ik=0 means that we decided to place there another kind of equipment or not to place any access point within the i-th cell.

Our objective is to supply the maximum bit rate at maximum number of cells in accordance with their weight coefficients with minimum expense.

Here, b_j(X) is the maximum possible bit rate at the j-th receiving point (though all wireless devices are duplex, for the simplicity, we name he place to be covered by the growing device `receiving' point in contrast to the access point). The access points are set in accordance with the vector X of Boolean variables, v_j is the weight coefficient of the j-th receiving point, N_p is the total number of possible places of access points in the future system, N_t is the number of types of access point equipment (access points or wireless routers equipped with corresponding types of antennas), b_minj are minimum guaranteed bit rates needed for some receiving points.

MODEL

Let's define the RF absorbing properties of each obstacle shown in our scheme. Let П_l be the absorption (in decibels) of the signal passing through the layer of l-th obstacle a cell thick. The initia values can be obtained from information tables [8]. For example, for a wall П_l = -7 dB, for a window -2 dB, for the forest -3 dB for each meter (the value for a cell depends on its size). Below, we consider a method allowing us to define more exactly the value of П_l in accordance with the experimental data.

Then, the signal level (see Fig. 2) of the i-th access point which we can receive at the j-th cell can be calculated as

,

.

Here, P_rij(X) is the signal level (dBm) of the i-th access point received at j-th receiving point, G_ti is the gain of the antenna of the access point (including the loss of all cables), G_r is the gain of the antenna of the receiving point (also, including all cables), L_ij(OBST) is the path loss between the i-th access points and j-th receiving point with the configuration of obstacles (walls, windows, trees etc.) described with a set OBST. D_ij is the distance (in meters) between the i-th AP and the j-th receiving point.

A bit rate which is supplied for this signal level is

Here, b_ij(X) is the maximum available bit rate of the link between the i-th access point and the j-th receiving point.

Taking into consideration several possible variants of the wireless equipment for each access point, we the signal level is

and the available bit rate of the j-th receiving point is

To calculate the signal level received at some cell from some access point we should determine which obstacles lay between the access point and the covered cell taking into consideration the Fresnel zone. Let's evaluate the thickness of the Fresnel zone in cells.

Figure 2. Path loss

To determine the cells which we consider to belong to the direct sight line we implement the line drawing algorithm (which is implemented in the computer graphics software) [11] (Figure 3).

Here, R_F is the diameter of the Fresnel zone, d_cell is the size of a cell in discrete coordinates scheme, D_i is the distance to the i-th AP, D_j is the distance to the j-th receiving point and F is the frequency (let it be 2.44 GHz).

Let's determine (in cells) the thickness of the Fresnel zone in the middle point. If it does not exceed 1.5 points then we suppose it to be equal to 1 cell and the wave propagation zone lays within the line shown in Figure 3.

Figure 3. Fresnel zone and its presentation in discrete coordinates

.

Otherwise, for each cell of the line shown in the Figure 3 where the Fresnel zone thickness exceeds 1.5 cells, we 'draw' a line segment normal to the direct sight line (Fig.4) with the length equal to the diameter of the Fresnel zone. Let's investigate what number of cells of this line segment is occupied with the obstacle.

.

Here, r_mij is the ratio of the number of cells of the m-th line segment occupied with the obstacle (N_{OBST m}) and the total number of cells in the line segment (N_Fm).

If the obstacle occupies less than 25% of the line segment cells then we suppose that the absorption of the obstacle at this segment is proportional to the part of the Fresnel zone, if it exceeds 25% then we suppose that the path loss caused by the obstacle is equal to that the obstacle blocks up all the cut of the Fresnel zone.

Here, L_OBSTq is the path loss caused with the q-th obstacle which have the size of 1 cell, OBST_q is the configuration of the q-th obstacle (a set of the cells which it occupies), SEG_mij is a set of cells of the m-th line segment normal to the line from the i-th AP to the j-th receiving point.

Figure 4. Fresnel zone and its presentation in discrete coordinates

If the Fresnel zone is occupied with the obstacle with more than 30% then we suppose that the obstacle absorbs the signal as if it occupies 100% of the Fresnel zone [8].

So, we know the value of loss caused by the obstacles situated between the access point and covered cell.

Here, L_ij is the total path loss caused by the obstacles situated the i-th AP and the j-th receiving point.

Thus, the signal level from the i-th access point equipped with the hardware of the k-th type received within the j-th cell is

The client wireless equipment situated within each of the covered cells is able to establish a connection with any access point but it selects the access point with maximum signal level. The signal level of the 'best' access point received within the j-th cell can be calculated as

.

Thus, we have a discrete optimization problem with pseudo-Boolean object functions with constraints having 2 criteria. To solve problems of that kind we have a large experience of implementation of the variant probability algorithm (MIVER) proposed by A.Antamoshkin [1]. The problem of contraction of the 2^nd criterion and analysis of of Pareto-optimal set of solutions we use the method proposed in [12]. The algorithm and method have been successfully implemented for a large class of the analogous 2-criteria optimization problems of telecommunication systems [13], so, it is possible to presume its efficiency for our problem. The final step of the algorithm is the comparison of the Pareto-optimal solutions shown at the scheme with the values of possible bit rates of each cell for different values of the cost spent to achieve such coverage.

The maximum bit rate available at the j-th point is

MODEL PARAMETERS ADJUSTMENT

We can presume the absorption of each obstacle in our scheme. But usually, we do not know the exact structure of the building materials, exact thickness of the walls and other parameters that causes the significant difference (even in logarithmic scale) between the real values and ones taken from the information tables. Sometimes, there are the obstacles which are not shown in the initial scheme but exert the significant influence upon the signal propagation. Let's solve the problem of accurate definition of the values of absorption for each obstacle and detection of 'invisible' obstacles.

Let the real value of signal level at j-th cell be and the calculated value be

Here, X^real is a vector characterizing the configuration of the current placement of access points (x_ik^real = 1 if there is the k-th type of equipment already situated at the i-th place).

In this calculation, we take into consideration only the existing access points. Thus, to determine the most adequate values of coefficients L_mij we should solve the minimization problem

.

Figure 5. Additional 'invisible' obstacle

Here, N_p^real is the number of the access points which are already functioning.Here, the optimized variables are the absorption values of 'invisible' obstacles. For the simplicity, we assume that these obstacles are situated between the access point and receiving cell and their shape is a sphere or circle with the center between the access point and receiving cell (in the middle, Fig. 5) because we do not know the real shape. We assume that such an invisible obstacle exists when the direct sight line and Fresnel zone is clear but the real measured signal level differs from the calculated one significantly (10 dB in our example)

Here, L_ij^inv is the path loss caused by each cell of this `invisible' obstacle situated between the i-th AP and j-th receiving point.

RESULTS

We considered the problem of choice of place for additional access points of the growing network and their types as an optimization problem which is based on the adapted model of wave propagation environment.

Though our model takes into consideration only the most important of the propagated signal and environment (practically, only the absorption and noise without detection of its nature), this model allows us to forecast the signal level and bit rate of each perspective area at least as a rough estimation. This method does not need any field testings but it taker into consideration the results of them if they have been performed. Basically, our method coincides with the usual practice of the engineering calculations but it allows to collect all the information about our environment into a single model and find one or more Pareto-optimal solutions taking into account all the information of the environment and cost of the new equipment placing.

The results of our method can be simply interpreted by the specialist because the possible places of access points are defined at the first step.

The practice brings to light the necessity to check the real signal level after theoretical solving of the problem with our method and to implement the method with new measured values. For the system similar to one shown in Fig.1 we have the difference between the real and calculated values of the signal up to 11 dB, the second step gives the maximum error not more than 6 dB which is enough for the engineering calculation.

REFERENCES

[1] A.Antamoshkin, “Optimization of functionals with Boolean variables”, Tomsk University Press, Tomsk, 1987 (in Russian)

[2] M.H.Wright, “Optimization methods for base station placement in wireless applications” in Proceedings of IEEE Vehicular Technology Conference, vol.89, 1998, pp 11513-11517

[3] A.Hills, “Large-scale wireless LAN design”, IEEE Communications Magazine, vol.39, pp.98-107, 2001

[4] R.Battiti, M.Brunato, Andrea Delai, “Optimal wireless access point placement for location-dependent services”, Technical Report DIT-03-052, Informatica e Telecomunicazioni, University of Trento., 2003

[5] P.Bahl and V.N.Padmanabhan, “RADAR: An in-building RF-based user location and tracking system”, in Proceedings of IEEE INFOCOM 2000, March 2000, pp. 775-784

[6] L.Nagy and L.Farkas, “Indoor base station location optimization using genetic algorithms”, in IEEE PIMRC 2000, vol. 2, 2000, pp. 843-846

[7] T.S. Rappaport, “Wireless communications : principles and practice, 2nd ed.”, IEEE Press, 2002

[8] J.Hu, E.Goodman, “Wireless access point configuration by genetic programming”, in Evolutionary Computation, 2004. CEC2004. Congress on, vol.1,pp. 1178- 1184, 2004

[9] V.Vishnevsky, A.Lyakhov, S.Portnoy, I.Shakhnovich, “Broadband wireless telecommunication networks”,Eko-Trendz, Moscow, 2005

[10] T.Roos, P.Myllymaki, H.Tirri, P.Misikangas, and J.Sievanen, “A probabilistic approach to WLAN user location estimation”, International Journal of Wireless Information Networks, vol.9, no.3, July 2002

[11] J.D.Foley, A. van Dam, S.K.Feiner, J.F.Hughes, “Computer graphics: Principles and practice”, Addison-Wesley Longman Publishing Co., 1990

[12] Kazakovtsev L.A., Stateinova A.V,. ”System approach to the Realization Of the Assortment Planning”, Vestnik NII SUVPT, issue 6: Collected scientific works, Krasnoyarsk, NII SUVPT, 2001, pages 37-46.

[13] Kazakovtsev L.A. “Adaptive model of static routing for traffic balance between multiple telecommunication channels to different ISPs”, in Materials of . In: Workshop on Optimization Technologies for Low-Bandwidth Networks, 2006, Trieste, Italy, http://eprints.ictp.it/419

Размещено на Allbest.ru