## 2 Routing Protocols in Large-Scale WSNs
### Energy Consumption Mitigation Algorithms
However, if a number of non-nodes want to deliver data packets to the same father-node at the same time, only the first node which to be traversed can transmit the data to the father-node, and the others should be waiting for the next round. In a round of communication, if a node faces the situation of transmitting and receiving happening at the same time, receiving has priority. A comparison is shown in Figure 5. A club structure cluster is shown in Figure 5(a). The structure of DMSTRP and the transmitting sequence in a MST are depicted in Figure 5(b) where the first round transmission queue is {3, 5}, which means node 3 and node 5 can transmit their data simultaneously. The transmitting queue in the following round is {1, 4 and 6}. Obviously, DMSTRP consumes energy more efficiently than LEACH and BCDCP, because the average transmission distance between nodes is reduced through the multi-hop intra-cluster and inter-cluster communications, and thus the energy dissipation of transmitting data is potentially reduced. Furthermore, due to the reasonable schedule, the transmission collision is alleviated and DMSTRP can achieve shorter delay compared with LEACH and BCDCP. But the transmission schedule creates more overhead. _[PERSON]_. [PERSON] _et al._ in [36] proposed a novel idea by introducing cooperative communication from a mobile _ad hoc_ network (MANET) to a WSN for energy reduction in such energy constrained networks. In the first stage during packet delivery, the coalition head broadcasts data packets to all the nodes within its coalition; in the second stage the coalition head, together with the nodes in the coalition, cooperatively forward the packet to the next hop destination. The procedure lasts until the packet reaches its final destination. A larger coalition would reduce the cooperative cost, but may require more multicast energy to reach nodes located further away. Whereas a smaller coalition would require less multicast energy, it would have higher cooperative costs. The authors aimed to find the optimal coalition size to minimize the total transmission cost. During the one-hop delivery of packets, the optimal coalition size is derived by:  
Figure 5: **(a)** A club structure of a cluster in LEACH and BCDCP. **(b)** A MST in DMSTRP. \[C_{ab}=\underset{k_{a}}{min}\Big{[}P_{k_{a}}^{M}+P_{k_{a}}^{C}\Big{]} \tag{4}\] \[P_{k_{a}}^{M}=max\Big{\{}P_{a_{1}\_{-direct}},P_{a2\_{-direct}},\cdots P _{ak_{a}\_{-direct}}\Big{\}}\] \[\underset{p}{min}P_{k_{a}}^{C}=P_{a}+\sum_{j}^{k_{a}}P_{j}\] \[s.t. P\leq P_{max}\] \[\frac{I}{N}\Bigg{(}\sum_{j=1}^{k_{a}}\sqrt{P_{j}\ /\ d_{ab}^{\beta}}+\sqrt{P_{a}\ /\ d_{ab}^{\beta}}\ \Bigg{)}^{2}\geq\gamma\]  
In the equations above, \(P_{k_{a}}^{M}\) indicates the multicast cost to reach \(k_{a}\) neighbors, \(P_{k_{a}}^{M}\) means the cooperative cost from the \(k_{a}\) (plus node a itself) nodes to node b and \(P_{ai\_direct}\) is the cost of point-to-point transmission from node a to node i. \(P_{k_{a}}^{M}\) takes the maximum value among the set of \(P_{ai\_direct}\) that aims to be able to reach the farthest node in the coalition. The second restriction is intended to assure the receiver could receive the packets successfully by combining the signals from the coalition nodes. After finding the optimal coalition size, the original network could be modeled as an edge-weighted and directed graph, as Figure 6 shows. In general the number of neighbor nodes is a key factor, because the node with more neighbors could transmit with lower cost. Therefore, \(C_{ab}\) might not be equal to \(C_{ba}\). Based on the directed graph, the routing problem from the source node to the destination node is formulated as shortest path routing problem and could be solved by [PERSON]'s algorithm to find the minimal energy consumption route. Moreover, if the routing path is required to satisfy the delay constraint, the problem boils down to a Delay Constraint Least Cost (DCLC) problem which is NP-hard. Throughput was also considered as additional QoS requirement when route searching in [36].