## 2 A Behavior-Based Self-Deployment and -Repair Algorithm
### Role Definition for Different Routing Mechanisms  
Deployment/self-healing algorithms return different network topologies depending on the employed routing algorithms. WSN support different routing mechanisms [37; 38]. However, when deployment is not planned and signaling traffic needs to be very limited to extend the network life as much as possible, the most popular routing mechanisms are (greedy) geographic and hierarchical routing. Geographic routing works over multi-hop topologies. Its main advantages with respect to other WSN strategies are [3; 38]: (i) it is a stateless, i.e., highly energy efficient, routing strategy; (ii) it adapts quickly to network topological changes; and (iii) it provides good scalability. One of the simplest approaches to geographic routing is the closest neighbor routing: a given node \(i\) sends a packet to all of its neighbor nodes within its transmission range. However, receiving neighbor nodes only retransmit a message if they are closer to the destination node than the one from which they received the message. A node never retransmits the same packet more than once. This algorithm provokes a partial flooding; but, it is very simple, and it does not require additional signaling for routing. Hierarchical routing is a popular approach to point-to-point routing with a very small routing state [38]. Hierarchical routing infrastructure can be autonomously bootstrapped and maintained by the nodes [39]. In its simplest formulation, a hierarchical network includes three node levels. The sink node is a Level 2 node. All nodes connected to the sink node are Level 1 nodes (L1). Finally, nodes connected to a Level 1 node are Level 0 nodes (L0). L0 nodes are registered with a specific L1 node. L1 nodes are registered with the sink node. Typically, an L0 node only exchanges data with the L1 node it is registered with, and that L1 node redirects data to the sink node. The main drawback of hierarchical routing in WSN is that failure in L1 nodes (critical nodes) may lead to loss of all L0 nodes that were registered with them. This problem can be partially mitigated if L0 nodes may become L1 nodes to replace dead ones. Furthermore, in MWSN, nodes may relocate to adapt to this new configuration. In this work, we propose a very simple role-swapping algorithm. Originally, all nodes except the sink start as L0. An L0 node is promoted to L1 if: (i) there is no L1 node in its vicinity; and (ii) the number of L1 nodes for the whole network is under a prefixed threshold that depends on the total number of nodes N. Alternatively, if an L0 node finds in its vicinity an L1 node that still accepts connections, it registers with that node. If an L0 node moves away from the L1 node it is registered with, it can unregister and find a closer one with which to register. This algorithm is presented in Figure 1. It needs to be noted that role swapping occurs when nodes move (deployment or self-healing). The main difference between both presented routing algorithms is that in geographic routing, all nodes have the same role, whereas in hierarchical routing, nodes may have different roles. The proposed SPF-based algorithm may support both routing strategies if we define node roles, as well. Forces defined in Section 2.1 that affect a node may change depending on the node role:  
* \(f_{r1}(r_{i,j})\) is the same for non-hierarchical and hierarchical topologies, i.e., in both cases, nodes need to avoid obstacles and remain in the coverage area. * Repulsion force(s) \(f_{r2}(r_{i,j})\) depends on node roles. In hierarchical routing, L0 nodes are less repelled from L1 nodes than from other L0 nodes or the sink node. Similarly, L1 nodes are less repelled from the sink than from other nodes. * The clustering force \(f_{c}(r_{i,j})\): in non-hierarchical networks, nodes are attracted to the sink node: in hierarchical networks, L0 nodes are attracted to L1 nodes, and L1 nodes are attracted to the sink node.