## 4 Lifetime Improvement Mechanisms in Routing
### Mobile Sink Mechanism
#### 4.2.1 Random/Stochastic Sink Mobility  
[PERSON] _et al._[8] presented three randomized patterns for sink mobility accompanied by two data collection mechanisms. They showed that randomized methods can prolong the network lifetime, at the expense of increasing data latency. These schemes are as follows: (1) _Random Walk and Passive Data Collection:_ in this method the protocol uses two following techniques: firstly, it chooses a random path in the sensor field so that the next step for the sink movement is achieved by a stochastic function called \(M_{random}\). This function produces two random uniform values. The first one is an angle in [-\(\pi\),\(\pi\)] radians that determines the deviation from the current direction of mobile sinks. The second one indicates a distance \(d\in\) (0, d\({}_{\text{max}}\)] that the sink node should travel along the defined direction. Secondly, data collection from the source nodes is implemented by a (passive manner) pull strategy. It means the sink asks one hop or _k_-hop neighbors to send their information (where, _k_\(>\) 1). (2) _Partial Random Walk with Limited Multi-hop Data Propagation:_ The network in this method is a square of size \(D\)\(\times\)\(D\) and \(R\) is the fixed radio transmission range of the nodes. All of the sensor nodes form a graph \(G_{o}\) during the network initialization. This graph partitions the network in _i_\(\times\)_i_ square regions. The mobile sink is located on one of the nodes of graph \(G_{o}\) at the beginning. Then a random function \(M_{graph}\) computes the next place for the sink repositioning among the neighbors of current vertex by selecting one of them uniformly randomly. If _i_\(=\)\(\left[D\times\sqrt{2}/R\right]\), the sink can cover all of the sensor nodes in _D/i_\(\times\)_D/i_ area when it locates at the center point of each square. Data collection protocol is a tree with the sink at root. The sink periodically broadcasts a beacon including hop count and TTL fields. When a sensor node receives a beacon, it updates these fields and specifies its parent in this tree. After that, it starts to send data to the mobile sink. In comparison to the first method, the distance traveled by the sink node is reduced efficiently and the sensor nodes are covered much faster at the expense of computational and communication overhead. (3) _Biased Random Walk with Passive Data Collection:_ in biased random mechanism, the sink node collects some information about the areas that were visited and then decides to change its position based on this information. If the sink is currently on vertex \(u\), the probability of visiting a neighboring vertex \(v\) are \(p(f)_{v}\) and \(p(d)_{v}\) based on frequency of visiting this area and the node density in this place respectively. Therefore, the final probability for sink repositioning to the area related to vertex \(v\) is presented in Equation (5), where \(\alpha\) and \(\beta\) are positive weighted factors so that \(\alpha+\beta=1\):  
\[p_{v}=\alpha\times p(f)_{v}+\beta\times p(d)_{v} \tag{5}\]  
A passive data collection is also used for this protocol, but in comparison with the first method, it has lower latency and higher delivery ratio. Nevertheless, the main drawback of the random sink mobility is that data collection from all of the sensor nodes through the network is not guaranteed [8]. The simulation results [8] show that the random sink mobility could apply in delay tolerant applications as well. It seems the delivery delay would be decreased by trading off some energy efficiency. However, the results are not affected by topology settings. The main drawback of random waypoint algorithms is that the sink cannot visit all of the source nodes in the field. On the other hand, the delivery ratio depends strictly on the speed of the sink node. In this protocol, when s = 8 m/s the success rate is about 95%. This metric will be reduced to 85% when the sink node decreases its speed to s = 4 m/s. Increasing the sink speed may cause more energy wastage across the network.