Node Placement Problems


Node placement belongs to the family of facility location problems. In such problems, facilities provide some kind of service to clients. In the case of mesh router placement, facilities aremesh routers that provide connectivity to mesh client nodes. The objective is to locate the facilities in such way that one or more criteria (e.g. cost reduction in terms nodes, demand capture, equitable service supply, fast response time etc.) are optimized. Node placement problems are shown computationally hard to solve for most of the formulations


WMN node placement


Different versions of the problem can be obtained depending on the types of mesh nodes to deploy, the objectives to optimize as well as different constraints, such as topological restrictions, battery restrictions, QoS requirements, etc. Some optimization problems are related to minimize the cost of the WMN, such as minimizing the number of mesh router nodes to deploy, while others focus on the WMN performance, such as computing optimal placement of an a priori fixed number of mesh router nodes. The objectives include minimizing the number of mesh routers , maximizing network connectivity , maximizing user coverage , minimizing energy consumption (especially in wireless and mobile networks), minimizing communication delay , maximizing throughput , minimizing deployment cost , etc. For instance, in Muthaiah and Rosenberg (2008), Zhou et al. (2007), Tang (2009) is considered the gateway placement aiming to optimize the throughput. In Antony Franklin and Siva Ram Murthy (2007), the authors consider a bi-objective version of the problem for two tierWMNs.

Mesh routers nodes placement


Mesh routers nodes placement can be formulated as follows. we are given a 2D area where to deploy a number of mesh router nodes (the deployment area is partitioned by grid cells), each of them with its own radio coverage, and a number of mesh client nodes of fixed positions (of an arbitrary distribution) and finds a location assignment for the mesh routers. Two main optimization objectives are maximization of network connectivity (measured through the size of the giant component of WMN graph) and client coverage (the number of users covered).

 An instance of the problem can be formalized by an adjacency matrix of the WMN graph, whose nodes are router nodes and client nodes and whose edges are links in the mesh network (there is a link between amesh router and mesh client if the client is within radio coverage of the router).

example of the output image


Optimization setting

For optimization problems having two or more objectivevfunctions, two settings are usually considered: the hierarchical and simultaneous optimization. In the former, the objectives are classified (sorted) according to their priority. Thus, for the bi-objective case, one of the objectives, say f1, is considered as a primary objective and the other, say f2, as secondary one. The meaning is that we first try to optimize f1, and then, we try to optimize f2 without worsening the best value of f1. In the later approach, both objectives are optimized simultaneously. Both approaches are very useful to explore. The first one is more convenient when priority applies to different criteria according to the problemdomain. For instance, in the case of WMNs, the the hierarchical approach is used due achieving network connectivity is considered more important than user coverage.

Client mesh nodes distributions

Mesh client nodes can be arbitrarily situated in the given deployment area. For evaluation purposes, it is interesting, however, to consider concrete distributions of clients. For instance, it hasbeen shown from studies in real urban areas or university campuses that mobile users tend to cluster to hotshots. We have considered Uniform, Normal, Exponential and Weibull distributions for client mesh nodes.

Resolution methods


Purely random placements would produce poor performance due to far from optimal router placement as a result. Therefore, using more efficient methods is crucial for node placement nodes in WMNs. Due to computational intractability of the problem, exact methods can only solve to optimality small size instances, and therefore heuristic and meta-heuristic approaches are the de facto approach to solve the problem for practical purposes.


Ad hoc Heuristics


1) Random placement: mesh router nodes are uniformly at random distributed in the grid area.

2) ColLeft placement: places almost all mesh routers at the left side of the grid area.

3) Diagonal placement: mesh routers are concentrated along the (main) diagonal of the grid area.

4) Cross placement: tends to place mesh routers along both diagonals of the grid area.

5) Near placement: mesh routers are concentrated in the central zone of the grid area.

6) Corners placement: distributes the mesh routers in the corners of the grid area.

7) HotSpot placement: is based on the idea of hotspots, that is most popular locations with a given area.

Local Search Heuristics

Local Search (LS) algorithms are among the best candidates for solving mesh node placement problems due to their efficiency and simplicity. These methods include Hill Climbing (HC), Simulated Annealing (SA) and Tabu Search (TS) methods for solving mesh router nodes problem.

Genetic Algorithms

Genetic Algorithms (Gas) are evolutionary algorithms that try to implement the selection process in nature. GAs start from an initial population of individuals, i.e. feasible solutions of the problem, each having associated a fitness value that indicates how good it is as compared to the rest of individuals. Thus, just as in natural processes, GA goes through a similar process of evaluation, selection, crossover, mutation and replacement yielding to the next generation of individuals. The process is repeated through a number of generations during which the best features of parents are passed on to offsprings and individuals of better quality are eventually obtained.

<< april - 2019 >>
  • Web cumple con la normativa w3ccs
  • Web que cumple con la normativa w3xhtml
  • Universitat Politècnica Catalunya
  • FIB
  • LSI