## 4 Description of MRP
### Phase II: Constructing Multipath
\[\tau_{y}(t,t+1)=(1-\rho)\times\tau_{y}(t)+\rho\times\Delta\tau_{y}^{k}(t,t+1) \tag{30}\]  
\[\Delta\tau_{y}^{k}(t,t+1)=\lambda\times(E_{i}+E_{j})/d_{y}^{2} \tag{31}\]  
where \(\rho\) is the evaporation factor, which serves to diminish the intensity of existing trail over time. \(\lambda\) is a coefficient. \(d_{ij}\) is the distance between node \(i\) and node \(j\). \(E_{i}\) is the residual energy of node \(i\). Algorithm 2 represents the basic operations of a SANT. RAND(\(x\)) is a function to generate a random number uniformly distributed between 0 and \(x\). ``` Begin
1:ifTTL\(<\)0 then
2:ifa SANT arrives at sink then
3: create and release a new BANT;
4:else
5:ifRAND(x)\(<\)0.001 then
6: create a AANT;
7: the AANT randomly chooses a node as the next hop node;
8:else
9: choose the next hop node \(j\) according to (26)-(29);
10: refresh the residual energy of \(i\) and \(j\);
11:ifselected node visited then
12: back to the previous hop node;
13: re-elect another node as the next hop node;
14:endif
15: using (30), (31) to refresh pheromone value of link (\(i\),\(j\));
16:endif
17:endif
18:end-if
19:endBackward ant (BANT)

When a BANT is back along the reverse path passed by a SANT, the BANT also needs to update the pheromone value on link (\(i\),\(j\)) (Equation (30) and (32) are used to calculate and update the pheromone value.). \[\Delta\tau_{i_{j}}^{k}(t,t+1)=c\times\frac{f(t+1)-f_{best}(t^{*})}{f_{best}(t^{* })}+c_{1}\times f(t+1) \tag{32}\]

According to (12), we have

\[f(t)=c_{0}\frac{f_{1}^{k_{1}}(t)}{f_{2}^{k_{2}}(t)f_{3}^{k_{3}}(t)} \tag{33}\]

\[f_{1}(t)=\min_{i\in(n_{1},n_{2},\ldots,n_{n})}(E_{i}) \tag{34}\]

\[f_{2}(t)=\sum_{(i,j)=p}E_{ij} \tag{35}\]

\[f_{3}(t)=\sum_{(i,j)=p}(i,j) \tag{36}\]

\[f_{best}(t^{*})=\max[f(t)],t^{*}=1,\cdots,t \tag{37}\]

where _f(t)_ is the evaluation function on the current path. \(f_{1}(t)\) is the minimum energy node in path \(p\). \(f_{2}(t)\) is the sum of energy consumption in path \(p\). \(f_{3}(t)\) is the length of path \(p\). \(f_{best}(t^{*})\) is the optimal solution so far. (\(n_{1}\), \(n_{2}\), \(\ldots\), \(n_{m}\)) denotes the sequence of nodes along path \(p\). \(c\), \(c_{1}\) and \(c_{0}\) are coefficients, which can be used to control the value of (32) and (33), respectively. \(k_{7}\), \(k_{8}\) and \(k_{9}\) are weights that determine the relative importance of \(f_{1}(t)\), \(f_{2}(t)\) and \(f_{3}(t)\), respectively. In (32), a scheme of negative feedback is introduced into realizing reward or punishment to the current result. The scheme is helpful of fairness among found multiple paths. The format of message brought by a BANT is shown in Figure 3.

The Message Type field indicates that it is a BANT. The Length field is the path length from sink to the current node. The meaning of other fields is same as that of message brought by a SANT. Algorithm 3 denotes the basic operations of a BANT. Figure 3: Message Format of a BANT. ### Phase III: Data Transmission

MRP is different to these algorithms in [14] because the CH in MRP dynamically chooses one path to transmit data. According to (12), a load balancing function of path \(i\) is given by

\[\Delta\tau_{y}^{k}(t,t+1)=\lambda\times(E_{i}+E_{j})/d_{y}^{2} \tag{31}\]0

where \(k_{10}\), \(k_{11}\), \(k_{12}\) are weight values, \(k_{10}\)+ \(k_{11}\)+ \(k_{12}=1\). \(E_{min}(i)\) is the residual energy of the minimum energy node in path \(i\). \(E(i)\) is the sum of energy consumption in path \(i\). \(Length_{i}\) is the length of path \(i\), which can be used to estimate the delay of a path. \[\Delta\tau_{y}^{k}(t,t+1)=\lambda\times(E_{i}+E_{j})/d_{y}^{2} \tag{31}\]1

where \(N\) is the set of discovered paths. \[\Delta\tau_{y}^{k}(t,t+1)=\lambda\times(E_{i}+E_{j})/d_{y}^{2} \tag{31}\]2

The CH uses (38)-(40) to calculate the probability and transmit data along the selected path. Since the path is dynamically chosen, load balancing among the paths is achieved. ### Route Maintenance

In MRP, route maintenance is responsible for the maintenance of the routes during the communication.