Predicting the Suitable Parameters of Indoor Propagation Model Using CSP Algorithm

Predicting the Suitable Parameters of Indoor Propagation Model Using CSP Algorithm

Anuj Agrawal

M.E. (Electronics)

PEC University of Technology, Chandigarh

Abstract: Constraint programming is the study of system which is based on constraints. The solution of a constraint satisfaction problem is a set of variable value assignments, which satisfies all members of the set of constraints in the CSP. In this paper the application of constraint satisfaction programming is to be used in predicting the path loss of various indoor propagation models using Depth First Search Algorithm, which is basic algorithm of CSP. After predicting the path loss at different set of parameters such as frequencies , floor attenuation factor , path loss exponent , we find the optimum set of parameter frequency , floor attenuation factor , path loss exponent at which the path loss is minimum. For this optimization CSP provides an optimization algorithm called Branch and Bound Algorithm. Presents the additional path loss caused by the floors between transmitter and receiver by considering the average floor attenuation factors found for up to floors of the building. A comparative analysis has been done to validate the applicability of these three different indoor propagation models at various frequencies and distances.

Keywords: Path Loss, Indoor Propagation Model, CSP Algorithm.

1. INTRODUCTION

   programming, namely constraint satisfaction and constraint solving.

   Constraint satisfaction deals with the problem defined over finite domain, on the other hand constraint solving algorithm are based on mathematical techniques. The constraint satisfaction programming (CSP) offers its basic algorithm like depth first search and branch and bound algorithm to solve and optimize the problem. Constraints satisfaction algorithm can be viewed as an iterative procedure that repeatedly assigns domain value to the variables [4].

   In this paper problem of finding the path loss of various Empirical indoor wireless propagation models in different environment has been stated as a CSP (constraint satisfaction problem) and has been solved by depth-first search algorithm. The branch and bound algorithm then used to optimize the constraint satisfaction problem.

   Importance of propagation model is discussed in section II. In section III, methodology and basic algorithm of CSP is explained. Result of indoor model is discussed in section IV.

   Various researches into adaptive algorithm has concerned to find the heuristics which is best suited for solving particular problems from a set of completely specified heuristics. In last few years, the constraint satisfaction programming (CSP) has attracted high attention among experts from many years because of its potential for solving problems. The constraint satisfaction programming approach has been widely used in many academics and research parlance to tackle wide range of search problem. It is defined by finite set of variables, a set of domain and constraints [1]. All CSPs are characterized by the inclusion of a finite set of variables; a set of domain values for each variable; and a set of constraints that are only satisfied by assigning particular domain values to the problems variables [2]. The CSP deals with the set of values from its domain to the variable in order that no constraint is violated.

   A CSP problem includes some variables, and valid values for those variables (we call it domain of the variables) and conflict tables. We must find a solution to assign values to all the variables and those values must satisfy the conflict tables [3]. There are currently two branches of constraint

2. PROPAGATION MODEL

   Nowadays cellular phones are used widely for the communication. The number of people using cell phone increases rapidly. Therefore, for an indoor environment an efficient planning and development is surely essential. For the design of indoor wireless services the knowledge of the signal propagation in different environment is demanded. The need for high capacity networks, estimating coverage accurately has become extremely important. Therefore, for more accurate design, signal strength measurement and the path loss measurement must be taken into consideration.

   Propagation models in wireless communication have focused on predicting the average received signal strength at a given distance from the transmitter as well as the variability of the signal strength in close proximity to a particular location. Propagation models that predict the mean signal strength for an arbitrary transmitter receiver separation distance are useful in estimating the radio coverage area of transmitter.

   Radio propagation models are required to determine the coverage of a transmitter. It is used to determine the transmitter

   power requirement and the battery lifetime. The radio propagation models are required because it is used to finding the modulation & coding scheme to improve the channel quality and the maximum channel capacity. The accuracy of propagation prediction involves many aspects. These include the accuracy of locations and sizes of buildings and accurate knowledge of the electric parameters of walls and other objects involved. Trees, large posts, traffic, and pedestrians in outdoor cases and furniture in indoor cases can also influence the results and make a difference [10].

   Propagation model that characterize the rapid fluctuation of the received signal strength over very short travel distances or short time duration are called small scale or fading models. As mobile moves over very small distances, the instantaneous received signal strength may vary rapidly giving rise to small scale fading [5].

   These models can be broadly categorized into three types: empirical, deterministic and stochastic. Empirical models are based on observation and measurement alone. These are mainly used to predict path loss [6]. Empirical models use measurement data to model a path loss equation. To conceive these models, a relationship is found between the received signal strength and other parameters such as distance, path loss exponent, floor loss attenuation factor. The main complexity to model indoor propagation channel is its sensitiveness to indoor environment and less probability of line-of-sight.

   There are two types of propagation modeling, site- specific and site-general modeling. In the site-specific modeling, detailed information on building layout, furniture locations are required. But for the most environment, the knowledge of the building layout and material is limited the environment can change rapidly by just moving furniture and doors. Thus the site- specific modeling is not commonly employed. Whereas site- general modeling provide a statistical prediction of path loss and are useful tools for performing initial design and layout of indoor wireless system [11].

   Three indoor models, ITU indoor path loss model, distance-dependent path loss model and floor attenuation factor path loss model have been developed. These models have been developed based on the number of floors between transmitter and receiver. The path loss depends upon different obstacles between transmitter and receivers.

3. METHODOLOGY OF CSP

   Constraint satisfaction problems (CSPs) representing problems to form a class of models that have a common properties, a set of variables and a set of constraints. A solution to a CSP is a set of variable value assignments, which satisfies all members of the set of constraints in the CSP. In some situations, it is not possible to find a solution satisfy al the constraints belonging to a CSP. Such problems are termed as over constrained problems [7]. The algorithms or techniques that

   use in constraint satisfaction depend on the kind of constraint being considered. The two algorithms of CSP, depth first search and branch and bound algorithm which are used to solve and optimize the wireless indoor propagation models are explained as below:-

   Depth-First Search Algorithm:

   There are various ways to traverse the graph systematically. Depth first search is one of the ways which give us some information about the graph structure. In depth-first search the idea is to travel as deep as possible from neighbour to neighbour before backtracking. DFS algorithm considers outgoing edges of a vertex before any of the vertex's siblings that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. It continues unit it reaches a node that is non-viable or non-promising. Depth first search prunes the subtree rooted at this node and continues the depth-first traversal of the tree. Depth-first search tends to prunes the entire subtree if their root node is a viable solution. The algorithm will backtrack up the tree to search for other possible solutions [12]. There are different types of variables, such as frequency , distance , path loss exponent , floor attenuation factor etc. After implementation of the depth-first search algorithm, we find the path loss of indoor propagation model at different set Frequency , distance , path loss exponent and floor attenuation factor . The DFS algorithm has a significant advantage over an exhaustive search of the tree for the average problem.

   Branch and Bound Algorithm:

   After finding the path loss for different set of parameters, we have to find that particular set of parameter at which propagation loss is minimum. For this optimization CSP provides an optimization algorithm called branch and bound algorithm. Branch and bound strategy involves two mechanisms, a mechanism to generate branches when searching the solution space and a mechanism to generate a bound so that many branches can be terminated. The branch and bound algorithm uses a breadth-first search with pruning and a queue as an auxiliary data structure. Branch and bound algorithm starts with considering the root node and apply a lower-bounding and upper bounding technique to it. A bound is nothing but a global variable which is defined according to the minimization or maximization problem, it depends upon the case that either problem needs minimum or maximum value of the function [4]. Once the bound match, an optimal solution has been found and the algorithm is finished. If the bound does not match, then algorithm runs on the child nodes. The branch and bound algorithm in indoor wireless propagation models is used to find that particular set of frequency , the distance , path loss exponent and floor attenuation factor at which the propagation loss is minimum. This procedure will carry on until and unless a minimum value is found and reverse of this procedure is used if we have to find the maximum value [4].

   A constraint satisfaction problem is defined as tuple where,

   is a finite set of variables,

   is a finite set of domains, one domain is assigned for each variable,

   and is the finite set of constraints that restrict certain value assignments [8].

   Domains of variables are: frequency, distance, path loss exponent and floor attenuation factor.

   Constraint is the path loss.

4. RESULT & DISCUSSION

   Among numerous propagation models, the following are the most significant ones. The indoor propagation models are:

   1. ITU indoor path loss model

   2. Distance dependent path loss model

   3. Floor attenuation factor path loss model

   Measurements have been taken for distance to for the different floors of the building from the same floor to the three floors respectively.

   1. ITU indoor path loss model:

      The graph has shown here is for which is measured as the average distance power loss coefficient in office area environment. The value of is taken as , , and from the same floor to the three floor respectively which is average floor penetration loss factor measured in different buildings. From the graph shown above, it can be concluded that the path loss of ITU model increases as frequency increases. It can also be seen that path loss increase as the number of floors between transmitter and receiver increases. From the above graph it can be noted that as number of floor increases the

      incremental ratio of path losses are decreases.

   2. Distance dependent path loss model:

      A model used in [9] shows that mean path loss increases exponentially with distance, i.e.,

      (2)

      Where is the mean path loss and n is the mean path loss exponent which indicates the path loss increases exponentially with distance. Absolute mean path loss in decibels is defined as the addition of the path loss at a reference distance d0 and some additional path loss in decibels.

      Let us analyse the indoor propagation model by taking an example of ITU indoor propagation model. It is also known as ITU model for indoor attenuation. It is a radio propagation model that estimates the path loss inside a room or a closed area inside a building. The ITU indoor path loss model is defined as,

      (3)

      For this, reference distance is chosen as and assumes that is due to free space propagation from the transmitter to a reference distance. This leads to

      path loss at MHz over a reference distance free space path.

      where,

      (1)

      is the distance power loss coefficient.

      is the number of floors between the transmitter and receiver.

      is the floor penetration loss factor

      Table 1. Path loss exponent in various types of buildings

      n Number of

      All Locations	3.14	634
      Same Floor	2.76	501
      Through First Floor	4.19	73
      Through Two Floor	5.04	30
      Through Three Floor	5.22	30
      Grocery Store	1.81	89

      All Locations	3.14	634
      Same Floor	2.76	501
      Through First Floor	4.19	73
      Through Two Floor	5.04	30
      Through Three Floor	5.22	30
      Grocery Store	1.81	89

      locations All Buildings:

      100

      80

      60

      915 MHz

      1900 MHz

      2400 MHz

      100

      80

      60

      915 MHz

      1900 MHz

      2400 MHz

      40

      40

      5

      10

      15

      20

      5

      10

      15

      20

      Figure 1- Analysis of path loss in ITU path loss model

      Retail Store 2.18 137 The value of depends on the specific propagation

      environment in various types of building. Table (1) lists path loss exponent for various types of building.

      120 100 80 60 40																					915 MHz 1900 MHz	Table 2: value for the floor attenuation factor in different floors of the office building Building FAF (dB) Number of locations
      20																						Office Building 1:
      0																						Through One Floor	12.9	52
      			5															0				Through Two Floors	18.7	9
      																						Through Three Floors	24.4	9

      120 100 80 60 40																					915 MHz 1900 MHz	Table 2: value for the floor attenuation factor in different floors of the office building Building FAF (dB) Number of locations
      20																						Office Building 1:
      0																						Through One Floor	12.9	52
      			5															0				Through Two Floors	18.7	9
      																						Through Three Floors	24.4	9

      2400 MHz

      10 15 2

      Figure 2- Analysis of path loss in distance dependent path loss model

      It can be concluded from the above graph that the path loss in the case of distance dependent path loss model is increases as the frequency increases. It can also be seen that path loss increases as the number of floors between the transmitter and receiver increases. From the graph, it is clear that the path loss at the same floor environment is always less than that at the higher floor at any frequency. From the above graph it can be noted that as number of floor increases the incremental ratio of path loss decreases.

   3. Floor attenuation factor path loss model:

   The path loss in multi-floored environments is predicted by a mean path loss exponent that is a function of the number of floors between transmitter and receiver. But in floor attenuation factor model, path loss is predicted by a constant floor attenuation factor (in ). FAF is a function of the number of floors and building type. This FAF is basically added to the mean path loss predicted by a path loss model which uses the same floor path loss exponent for a particular building type [5]. So the mean path loss of floor attenuation factor model is given by:

   (4)

   Values for the floor attenuation factor are mention is . Values for the floor attenuation factor is an average value (in ) of the difference between the path loss observed at multi floor locations and the mean path loss predicted by the simple model where is the same floor exponent given in table for the particular building structure and is the distance between transmitter and receiver [5].

   For three floors building, the mean path loss exponent for same floor measurement is taken from table (1) and the average floor attenuation factor is taken from table (2) for different number of floor(s) between transmitter and receiver.

   Through Four Floors 27.0 9

   120

   100

   80

   60

   40

   20

   0

   915 MHz

   1900 MHz

   2400 MHz

   120

   100

   80

   60

   40

   20

   0

   915 MHz

   1900 MHz

   2400 MHz

   5 10 15 20

   5 10 15 20

   Figure 3- Analysis of path loss in floor attenuation factor path loss model

   It can be concluded from the above graph that the path loss in the case of floor attenuation factor model is increases as the frequency increases. It can also be seen that path loss increases as the number of floors between the transmitter and receiver increases because the floor attenuation factor increases. From the graph, it is clear that the path loss at the same floor environment is always less than that at the higher floor at any frequency. From the above graph it can be noted that as number of floor increases the incremental ratio of path loss decreases.

5. COMPARISON BETWEEN INDOOR MODELS

   In ITU indoor model, as the frequency increases the path loss also increases. Initially losses are high at high frequency but as the partition increases the loss rate is low as compared to at low frequency. The more partition causes the less loss rate. Because of that there is not much variation in loss for far end partition. The distance dependent path loss model is basically relying on the environment we are working in, because there is a different path loss exponent for a different indoor environment. This model is not suitable if we are taking a wall effect or floor effect. Floor attenuation factor path loss model is the most appropriate model which can be used in predicting the path loss in indoor environment. Floor attenuation factor model

   is most affected by partitions. The attenuation between one floor of the building is greater than the incremental attenuation caused by each additional floor. So it is useful for multi floor building, mainly for the building having more than three floors. The comparison of indoor models at MHz is shown in the figure.

   105

   There may be many different obstructions between transmitter and receiver which can contribute to the path loss. Therefore Researchers have not found an indoor propagation path loss model which closely matches measurements within homes. This may be an indication that new parameters need to be introduced into the path loss model, such as construction materials and layout of the home. Future improvement can be made to the indoor propagation model by considering the wall

   95

   85

   75

   65

   55

   45

   5 10 15 20

   ITU Model

   Dis-dep Model

   FAF Model

   effect and construction material. The results motivate to develop a further model that takes into account the inter-action of penetrated walls and floors.

   REFERENCES

   1. Tope R. Karem, H. Anthony Chan, A low cost design of next generation sonnet/sdh network with multiple constraint, IEEE, National Research Foundation, 2007.

   2. Stuart Bain, John Thornton, Abdul Sattar, Evolving algorithm for

      constraint satisfaction, IEEE, pp. 265-272, 2004.

      Figure 4- comparison of indoor model characteristics at MHz

      As we can see from the graph that at MHz, the path loss in same floor environment is minimum in the case of both distance-dependent path loss model and floor attenuation model whereas it is high in the case of ITU path loss model. When the number of floors between transmitter and receiver increases the path loss measured in that case is also increases and floor attenuation factor model provides minimum path loss compared to other both models whereas maximum path loss obtained in distance dependent model.

6. CONCLUSION & FUTURE SCOPE

This work shows the relative study of path loss models. Several conclusions can be drawn from the indoor propagation study. The most obvious is that indoor propagation within indoor environment appears to be site-specific. The data collected in this study showsthat there does not appear to be a one model fits all solution.

In this paper, a brief survey of basic solving techniques behind constraint programming has been done. There are various wireless indoor propagation models used to find the propagation loss using the constraint satisfaction algorithm. An overview of the main technique of solving constraint optimization problem i.e. branch and bound algorithm has been used. Minimum path loss for various propagation models has been found for the given parameters using branch and bound algorithm.

Data collected in this study indicates that the model should be based on the floor attenuation factor path loss model with the addition of a floor attenuation factor. This indoor propagation study clearly indicates a need for a better understanding of indoor wave propagation within homes.

1. Tianbing Lin, Scott Goodwin, CSP: definition, creation, and algorithms.

2. Nagendra Sah and Amit Kumar, CSP algorithm in predicting and optimizing the path loss of wireless empirical propagation models, International Journal of Computer and Electrical Engineering, vol. 1, no. 4, pp. 464-472, October 2009.

3. Theodore S. Rappaport, Wireless communications: principles and practice, Second Eddition, PHI Learning Private Limited, 2008.

4. V.S. Abhayawardhana, I.J. Wassell, D. Crosby, M.P. Sellars, M.G. Brown, Comparison of Empirical propagation path Loss Models for Fixed Wireless Access Systems, IEEE, 2005.

5. Srinivas Padmanabhuni, Extended analysis of intelligent backtracking algorithms for the maximal constraint satisfaction problem, In the proceedings of the 1999 IEEE Canadian Conference on Electrical and Computer Engineernig, pp. 1710-1715, May 1999.

6. J.I. van Hemert, Evolving binary constraint satisfaction problem instances that are difficult to solve, National Research Institute for Mathematics and Computer Science, IEEE, pp. 1267-1273, 2003.

7. Scott Y. Seidel, Theodore S. Rappaport, 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings, In the proceeding of IEEE Transactions on Antennas and Propagation, vol. 40, no. 2, pp. 207-217, Feb 1992.

8. Magdy F. Iskander and Zhengqing Yun, Propagation prediction models for wireless communication systems. In the proceedings of IEEE transactions on microwave theory and techniques, vol. 50, no. 3, pp. 662-673, March 2002.

9. John S. Seybold, Introduction to RF propagation. WILEY- INTERSCIENCE, John Wiley & Sons, Inc. 2005.

10. Edward Tsang, Foundation of constraint satisfaction. 1996.