## 4 Description of MRP
### Phase II: Constructing Multipath  
In MRP, when the CH needs to deliver data to sink, an improved ACO algorithm is used to establish multiple paths with optimal or suboptimal energy consumption. There are three kinds of ants in MRP: search ant (SANT), backward ant (BANT) and abnormal ant (AANT). A SANT is used to collect information about multiple paths and intermediate nodes as it travel along the path. A BANT is used to update the pheromone value along the reverse path, and bring information of path to source node, such as residual energy of node, path length and energy consumption of the current path. MRP adds a new type of ant: Abnormal ant (AANT), which is used to partly avoid stagnation of the protocol. The procedure of searching for multiple paths is as follows:  
* The CH creates several SANTs to search for sink. The SANTs gather path information as they travel along the paths. * The sink creates a BANT when a SANT arrives. The BANT is sent back following the reverse path. When a BANT moves, it need to update the pheromone on the link _(i,j)_ at the reverse path. * When a SANT arrives at an intermediate node, whether or not a AANT is generated according to a small probability. The following subsections explain the procedure in detail. Search Ant (SANT)  
After the cluster formation phase ends, the CH that needs to find several optimal and suboptimal paths to sink sends many SANTs to obtain path information. In order to reduce route discovery time and overheads, the number of SANTs is related to the network scale and the demand of the application. The format of message brought by a SANT is shown in Figure 2.  
The message type field indicates that it is a SANT. The S_ID field denotes the previous node identification. The field D_ID is next node identification. The K field is the number of a SANT. The E\({}_{\text{min}}\) field gives the minimum energy till the current node. The Ep field gives the sum of energy consumption till the current node. The H field gives the path length so far. The TTL (time-to-live) field gives the depth that a SANT can travel (When a SANT is forwarded, the value of TTL is decreased. That is to say, if TTL reaches zero before the SANT arrives at sink, the SANT message is discarded.). In order to balance load among nodes and maximize the network lifetime, we modify those equations of the basic ACO as follows:  
\[P_{g}(t)= \begin{cases}\frac{\tau_{g}^{a}(t)\times\eta_{g}^{g}(t)}{\sum\limits_ {k}\tau_{g}^{a}(t)\times\eta_{g}^{g}(t)},&\forall j\in N_{i}\ and\ j\
ot\in M^{k}\\ 0,&otherwise\end{cases}  \tag{26}\]  
where \(P_{ij}(t)\) is the probability of selecting the next hop node \(j\) of the current node \(i\). \(\eta_{\bar{y}}\) denotes the local heuristic value of the link _(i,j)_, and \(\tau_{g}\) is the pheromone value on link _(i,j)_. \(\alpha\) and \(\beta\) are two parameters used to control the relative weight of pheromone trail and heuristic value, respectively. \(M^{k}\) contains the nodes already visited. In MRP, \(M^{k}\) is kept in the node's memory instead of keeping in  
Figure 2: Message Format of a SANT. a SANT's memory. This approach can decrease the size of the data to be transmitted and save energy. \(\eta_{y}\) can be given by  
\[\eta_{y}= \begin{cases}\eta_{\max}&(\mu_{y}>\mu_{\max})\\ \mu_{y}&(\mu_{\min}\leq\mu_{y}\leq\mu_{\max})\\ \eta_{\min}&(\mu_{y}<\mu_{\min})\end{cases}  \tag{27}\]  
\[\mu_{y}=\frac{(E_{j})^{k_{4}}}{(d_{y})^{k_{4}}}+\ \theta_{ij} \tag{28}\]  
\[\theta_{y}= \begin{cases}(E_{j})^{k_{4}}\\ (d_{y})^{k_{4}}\times(\frac{d_{j}}{d_{j}})^{k_{4}}\\ 0&\text{otherwise}\end{cases} \ \ \ \ \ (h_{j}\leq h_{t}) \tag{29}\]  
where \(k_{4}\), \(k_{5}\), \(k_{6}\) are three parameters, which are used to control the impacts of \(E_{j}\), \(d_{y}\), \(\theta_{y}\) on \(\mu_{y}\), respectively. \(\eta_{\min}\) and \(\eta_{\max}\) are predetermined parameters. Equation (30) and (31) are used to update the pheromone value at link (\(i\),\(j\)).