## 4 Lifetime Improvement Mechanisms in Routing
### Multi-Sink Mechanisms
Equation (1) shows the _REDR_ for node \(i\) where: \(\alpha\) is the weighting factor, _REDR\({}_{old}\)_ indicates the previous _REDR_'s value for this node and _REDR\({}_{sample}\)_ represents _REDR_ during past \(T\) seconds:  
\[REDR_{i}=\alpha\times REDR_{old}+(1-\alpha)\times REDR_{sample} \tag{1}\]  
_REDR\({}_{sample}\)_ is calculated by the Equation (2) as follows:  
\[REDRsample=(1-\frac{\textit{Current Residual Energy}}{\textit{Current Residual Energy}-T})/T \tag{2}\]  
The protocol consists of two phases as follows: (1) _Gradient field construction and data forwarding phase:_ in this stage, an advertisement (ADV) message is flooded by each sink but not at the same interval to ensure that there is no interference between two consecutive floodings. It contains the three following fields: (a) _hcnt:_ the number of hops from the sink, (b) _sum-redr_: the sum of nodes' _REDR_ on the path and (c) _max-redr_: the maximum _REDR_ value of nodes on the path. When the source node \(i\) receives an ADV message for the first time, it assumes that the acquired path is the shortest one and uses it for data transmission. Then it computes its gradient \(G_{i}\) according to Equation (3), saves it in memory, updates ADV message and finally rebroadcasts it through the network:  
\[G_{i}=\beta\times sum-redr_{L}+(1-\beta)\times max-redr_{L} \tag{3}\]  
Figure 3: Path selection with minimum hop count [5]. In this equation, _sum-redr\({}_{L}\)_ = the path's _REDR_ + node _i'_s _REDR_, _max-redr\({}_{L}\)_ = the maximum _REDR_ on the path including node \(i\) and _β_ is a weighting factor of these parameters. If node \(i\) experiences a lower loaded path than the first one so that its length does not exceed a specific number of hops and its gradient is lower than \(G_{i}\), it replaces this newly discovered path with the previous one. (2) _Gradient field maintenance:_ during the network functionality, the gradient field should be refreshed. Instead of flooding, GLOBAL updates this field during data transmission by exploring overhearing packets from other neighbors. This can reduce overhead throughout the network. Simulation results [6] indicate that GLOBAL improves the network lifetime by 50% and 18% more than shortest path routing (SPR) and CPL, which is a gradient-based routing using the cumulative path load only, respectively. The philosophy behind this improvement is that in GLOBAL, the traffic load of the most overloaded sensor over the path and a weighted average of the cumulative path load are used by an independent node to determine its gradient. The main drawback of GLOBAL is the high control overhead caused by sinks' advertisement flooding in the gradient field construction phase. The authors of the _Multi-Sink and Load-Balance Routing Algorithm (MSLBR)_[7] proposed a method to prolong the network lifetime through distribution of loads among sink neighbors that are called deputies. In this way, individual data packets generated by each source node can choose different deputies randomly as their destination and traverse different paths to reach them. Moreover, the source node uses a forward factor based on dividing the residual energy of its neighbors by their shortest hops to the destination. The quotient of this division used to find the next hop during a routing phase. MSLBR has three phases as follows: (1) _Network topology discovery:_ In this stage, all nodes use a beaconing mechanism to broadcast their deputy table periodically. As shown in Equation (4) the beacon of node \(N_{i}\) is a set of four items:  
\[\text{Beacon}=\left\{N_{i},E_{i},D_{j},H_{i,j}\right\} \tag{4}\]  
where \(E_{i}=\) the energy level of node \(N_{i}\), \(D_{j}\), = the identity of a deputy and \(H_{i,j}\) = minimum hops between node \(N_{i}\) and deputy \(D_{j}\). All of the entries in the deputy table of node \(Ni\) should be broadcasted periodically in a round-robin manner. (2) _Routing table updating:_ all sink nodes start to broadcast beacons at the initialization phase of a network.