## 4 Distance-Based Energy Aware Routing (DEAR) Algorithm
### DEAR Algorithm
#### 4.2.3 Route Setup Phase  
The whole route setup phase is summarized in Algorithm 1. Once source node has data to send, it will try to set up a route from source to sink node as follows.  
```
1:Source node \(i\) has data to send to BS
2:if\(d_{{}_{I},BS}<d_{{}_{I}}(n=2)\) then
3:direct transmission
4:else
5:choose next hop candidate set \(A\) with \(d(i,j)\in(d_{{}_{I}},d_{{}_{I}}+\Delta]\)
6:choose next hop candidate sub-set \(B\in A\) with \(d_{{}_{J},BS}<d_{{}_{I},BS}\)
7:choose next hop candidate sub-set \(C\in B\) with \(d_{{}_{C},BS}<d_{{}_{B-C},BS}\)
8:choose final next hop candidate \(j^{*}\in C\) with maximal residual energy
9:end - if
10:Node \(i\) sends RREQ to node \(j^{*}\) to request route setup
11:Node \(j^{*}\) sends ACK to node \(i\) to confirm reception of RREQ
12:Node \(j^{*}\) determines its next hop in an iterative way above and sends RREQ
13:RREQ message reaches BS
14:BS sends RREP to node \(i\) and traffic begins
15:End
```  
**Algorithm 1**Route setup phase.  
First, it determines the transmission manner by comparing the source to sink node distance \(d\) and \(d_{{}_{I}}(n=2)=100\) in Table 2, as is explained above. It is worth mentioning that we might choose direct transmission when \(\mathrm{d}\geq 100+\Delta\) under real network environment. For example, when \(d=120\), it is very difficult to find a 2-hop route with \(d_{{}_{I}}=100\) and \(d_{2}=20\) so that \(E_{{}_{I}}=E_{2}\) under random network topology, especially when BS is placed outside. The value of \(\Delta\) is dependant on network density and we set \(\Delta\in\)[20,50] in this paper under different network topologies.  
Once multi-hop transmission manner is chosen, source node will determine its next hop as is illustrated in Table 2 and 3. It is worth emphasizing that the selection criterion of next hop node is critical during routing process. Here, we choose the final next hop based on the following rules:* The distance between node \(i\) and its next hop node \(j\) should be \(d(i,j)\in(d_{i},d_{i}+\Delta]\).
* The distance between node \(j\) to BS should be less than node \(i\) to BS, namely: \(d_{j,BS}<d_{i,BS}\).
* The final next hop node \(j\) should have relatively much residual energy.  
Therefore, the final next hop node \(j\) is chosen after the following 3 steps. First, we choose a set of candidates with \(d(i,j)\in(d_{i},d_{i}+\Delta]\) based on the analysis in Equation (9) and Table 2 and 3. Then, some of the candidates whose distance to BS is less than the current node \(i\) to BS are chosen based on greedy routing mechanism, namely \(d_{j,BS}<d_{i,BS}\). Among them, we will choose half of them whose distance to BS is smaller than the other half. Finally, the one with the largest residual energy is chosen as the next hop. It is worth emphasizing that our first parameter is the distance and our secondary is the residual energy in order to achieve energy balancing and energy efficiency during routing process.  
When the next hop node is chosen, the source node will send a RREQ message to that specific neighbor directly with its own location information encapsulated inside RREQ. Once the neighbor receives the RREQ message, it will send an ACK message back to its previous node. Then, it will add its own location information again into the RREQ message and send it to its next hop neighbor in an iterative manner like above. Finally, the RREQ message will reach the sink node carrying the complete route information and a RREP message will be sent back to the source node based on the assumption of symmetric link.  
The traffic can get started once the source node gets the RREP message with complete route information from sink node. After the traffic session is closed, each node on the route will update its routing table as well as neighboring table.