# Towards an Efficient Method for Large-Scale Wi-SUN-Enabled AMI Network Planning
## 3 Related Work
### Approaches for Key Devices Positioning  
The state-of-the-art literature explores many strategies for positioning routers and gateways in the smart grid wireless communication scenario. In this section, we analyze different selected references, especially to identify the authors' research context and the algorithmic approach explored to deal with the positioning problem. The authors in [13] propose an algorithm to determine the optimal location of concentrators in smart grids, based on the ZigBee Mesh IEEE 802.15.4 communication protocol in the final access and Global Packet Radio Service (GPRS) communication in the concentrator of the mesh network, directly connecting to the utility's head-end system (backhaul). They assume a smart grid architecture with neighborhood area network (NAN) in which the meters are located, wide area network (WAN) where the collectors are positioned (usually installed on street light poles), and including a head-end system, the layer in which the network management is performed. Then, they present a proposal for a methodology for positioning concentrators in a Mesh network (in this case, a ZigBee network) based on the position of poles available in the region, aiming to optimize the network's performance. Then, all available poles become candidate positions for the concentrator installation. Additionally, they set a goal to find the minimum hops between meters and concentrators, aiming to find the shortest path that minimizes the cost of routes. Furthermore, they use different algorithms to establish the best route between two points. In this case, they use Dijkstra, Bellman-Ford, and BFS (Breadth-First Search). In situations where they define that more than one concentrator must be positioned, they use k-means to form clusters, having candidate positions (poles) as centroids. The proposed algorithm includes the following steps: obtaining the geographic coordinates of the meters and poles; if more than one concentrator must be positioned, they suggest the use of clustering (k-means) to define the centroid's position; the next step is choosing the position for the concentrator on one of the candidate poles; applying a shortest path algorithm (BFS, Dijkstra, and Bellman-Ford); evaluating the number of hops; changing the position of the concentrator; choosing as the final position the one with the least number of hops. In [14], the authors used the K-means-Dijkstra approach proposed by [13] to minimize the number of hops in the network. Additionally, they explored the recursive algorithm proposed by [11] to optimize the positioning of concentrators in smart grids aiming, among other factors, to balance the number of meters connected to the concentrators (load balancing) and the maximum number of hops. According to the authors in [11], in a network with many hops, a significant delay at each hop can occur due to wireless channel contention, packet processing, and queuing. They clarify that the delay depends on the number of hops between the source and the gateway. Thus, to minimize the delay, it is necessary to determine a cluster radius or maximum depth of the tree that interconnects the communication network nodes (rooted in the gateway) to ensure the quality criteria. To establish the position of gateways in wireless mesh networks, they divide the set of nodes formed by the meters into disjoint clusters. One node acts as a gateway in these clusters with the other nodes connected to it. A gateway-rooted spanning tree is used to aggregate and secure message traffic/forwarding in each cluster. The proposed algorithm is based on the dominant set (DS) concept, using recursive approximations of the minimum DS problem. The algorithm uses an adjacency matrix to represent the connectivity graph between network nodes. They consider nodes that are one hop from each other as adjacent, and they use a greedy algorithm to select a node \(v\) that will be the centroid of a cluster.