## 5 The Proposed GMDPSO for Our Protocol
### GMDPSO: Greedy Discrete PSO with Memory  
The GMDPSO makes use of the network topology of candidate relay nodes to guide particle's position and velocity updates. The greedy strategy originated from greedy forwarding mechanism is proposed to direct particles to move towards better position. Some small operators, such as position initialization and memory mechanism, are introduced to speed up convergence. This section will describe the proposed algorithm in detail. The whole framework of GMDPSO is given in Algorithm 1. ```
1:\(\mathit{Pbest}_{i}=\{\mathit{pbest}_{i}^{1},\,\mathit{pbest}_{i}^{2},\,\mathit{ pbest}_{i}^{3},\,\ldots,\,\mathit{pbest}_{i}^{D}\}\)
2:\


```
Parameters: particle swarm size \(N_{p}\), number of iterations \(Gen\), inertia weight \(w\), learning factors \(c_{1}\) and \(c_{2}\); Input: (1) adjacency matrix \(A\) for \(Sink_{i}\); (2) the residual energy vector \(E_{res}\) = {\(E_{res}\) (1), \(E_{res}\) (1),..., \(E_{res}\) (\(N-1\))} (3) the delay vector \(Del\) = {\(Del\)(1), \(Del\)(2),..., \(Del\)(\(N-1\))}; Output: \(G\)bext.X: the routing result Step 1: initialize Prev Step 2:for\(i=1\) to \(N_{p}\)do//Initialize the population \(P[i]\). \(X\) = initPathTree // seeing Section 5.2.3 for more information \(\textbf{Prev}\) = \(\textbf{Prev}\cup P[i]\).X If\(P[i]\).X#Prev// memorize new position \(P[i]\). \(V\) = \(P[i]\) \(\textbf{P}[i]\)  Calculate Fitness \(P[i]\). \(fit\) //Using Equation (26) end for Step 3:\(Gbest=\{P[k]\) | Fitness(\(Pbest[k]\)) = min(\(Fitness(\textbf{Pbest[i]})\))//update\(G\)best Step 4: While ((Terminate)) for\(i=1\) to \(N_{p}\)do Update\(P[i]\)//carefully described in Section 5.2.4  Memorize new position: \(\textbf{Prev}\) = \(\textbf{Prev}\)\(\cup\) new \(P[i]\).X If\(P[i]\).X#Prev Calculate Fitness \(P[i]\). \(fit\)  Update the \(\textbf{Pbest}_{i}\)\(\textbf{Pbest[i]}\).X if\(\textbf{Pbest[i]}\),fit \(>P[i]\). fit end  Update the \(G\)best:\(Gbest=\textbf{Pbest[best]}\) end Step 5: output \(Gbest\).X
```

**Algorithm 1** Framework of GMDPSO Algorithm

#### 5.2.1 Fitness Function Derivation

Fitness function is an important issue because it directly affects the final results. Now, we construct our fitness function (_fitness_) to evaluate the individual particle of population, in GMDPSO, the optimal tree is built such that it minimizes the _fitness value_. We have three objectives when build the optimal routing tree for \(Sink_{i}\) (i.e., _PTree\({}_{i}\)_): **The first one** is to maximize the lifetime of the routing tree to achieve energy-consumption balancing; **The second one** is to minimize the length of the routing tree to achieve energy conservation and enhance reliability; and **the third one** is to minimize the communication delay to enhance network throughout. In order to tune the three objectives to build optimal routing tree, we need to normalize the above three objectives and use the weight sum approach (WSA) [28] to construct our multi-objective fitness function _fitness_. Therefore, our fitness function depends on the following parameters:

(1) Lifetime of relay node

Our first objective is to maximize the routing tree lifetime, which is defined as the time interval from the establishment of the routing tree till its first relay node dies (FND). This is possible if we can maximize the lifetime of relay node that has least lifetime. Let \(RN_{j}^{k}\) be the kth relay node on the Pathj. The lifetime of \(RN_{j}^{k}\) is defined as follows:

\[lf\left(RN_{j}^{k}\right)=E_{res}\left(RN_{j}^{k}\right)/E_{cons}\left(RN_{j} ^{k}\right) \tag{7}\]where \(\mathit{Eres}(RN_{j}^{k})\) is the residual energy of relay node \(RN_{j}^{k}\), and \(E_{cons}(RN_{j}^{k})\) is its consumed energy. It can be seen from Equation (7) that, even though \(RN_{j}^{k}\) keeps more \(E_{\mathit{res}}(RN_{j}^{k})\), it maybe die faster if its \(E_{cons}(RN_{j}^{k})\) is bigger than others at the same time. Now, we begin the energy consumption analysis for relay node.