## 5 The Proposed GMDPSO for Our Protocol
### GMDPSO: Greedy Discrete PSO with Memory
best\(RN_{i}\) is the node ID which can be calculated by:_

\[bestRN_{i}\ =\argmin_{k}\varphi\left(i,k|k\in Neig\left(i\right)\right) \tag{34}\]

\(argmin_{k}\textit{f(k)}\) _returns the value of \(k\) that minimizes \(\textit{f(k)}\). \(\varphi\) is calculated using the following equation:_

\[\varphi\left(i,j|k\in Neig\left(i\right)\right)\ =fit\left(Path_{j}\left(i \to k\right)\right) \tag{35}\]

_where \(i\rightarrow\)k means that node\({}_{k}\) is chosen as the next relay node of node\({}_{i}\). fit(\(x\)) is the fitness function (i.e., Equation (26)), and fit(Path\({}_{j}\)(i\(\rightarrow\)k)) means that we only calculate the fitness value of the two adjacent relay nodes in \(Path_{j}\). Similar to greedy forwarding mechanism, Equation (35) means we choose the best next relay node for the current node from all its neighbors. However, unlike greedy mechanism that only chooses the nearest neighbor as the best next relay node, our approach chooses the neighbor node, which achieves the best balance of lifetime, distance and delay as the best next relay node by using our fitness function. Therefore, with the beginning from \(\text{Source}_{j}\). Path\({}_{j}\) can be built by selecting the best relay node one after one until the agent node is chosen, and Path\({}_{j}\) that is built in this way is the optimal routing path. For example, let first \(\text{bestRN}_{1}\) be \(\text{RN}_{j}^{1}\), then \(\text{Path}_{j}^{1}=(\text{Source}_{j}\to\text{RN}_{j}^{1})\) is the current optimal routing path. Let \(\text{Path}_{j}^{2}\) be the \(\text{bestRN}_{2}\) of \(\text{RN}_{j}^{1}\), \(\text{Path}_{j}^{2}=(\text{RN}_{j}^{1}\to\text{RN}_{j}^{2})\) is the current optimal routing path. Then,_

\[ \begin{array}{l}\text{Path}_{j}^{1}=(\text{Source}_{j}\to\text{RN}_{j}^{1}) \\ \text{Path}_{j}^{2}=(\text{RN}_{j}^{1}\to\text{RN}_{j}^{2})\end{array} \right\} \Rightarrow\text{Path}_{j}=(\text{Source}_{j}\to\text{RN}_{j}^{1}\to \text{RN}_{j}^{2}) \tag{36}\]

_where Path\({}_{j}\) is also the optimal routing. Using the same way, the other routing branches of \(X_{t}\) can be built. Next, the fitness of the \(X_{t}\) can be calculated using Equation (26)._

This search mechanism of \(\text{bestRN}_{i}\) (i.e., Equation (34)) actually act as our particle searching strategy in GMDPSO, in which a particle update its position by selecting the next relay node that can generate the largest decrement of the fitness value, so it can be regard as a greedy local search strategy. Our motivation of searching \(\text{bestRN}_{i}\) in this way is based on the divide-conquer strategy, in order to build an optimal routing tree of \(X_{t}\), we firstly build each optimal routing path branch of \(X_{i}\) respectively. When all routing path branches are built completely, then, the whole routing path tree is finished. Similarly, in order to build the optimal routing path branch \(\text{Path}_{j}\), we choose the best next relay node for the previous relay node one after one, until the whole _Path\({}_{j}\)_ is completed. However, Equation (34) is only used to build the single optimal routing path branch, rather than build the routing path tree (i.e., \(X_{i}\)). Because when we choose the best relay node for the current node of \(\text{Path}_{j}\), we do not consider the effect of the other routing path branch. Therefore, this method may neglect such a case, each routing branch is optimal, but the whole routing tree are weak due to the intersection relay nodes of multi routing paths. In other words, optimal routing path branches do not mean the optimal routing tree. As shown in Figure 5, many source nodes send their data packets to same next relay node, and these relay nodes will consume more energy to forward more packets. For example, \(node_{6}\) need forward data packets of \(Source_{1}\), \(Source_{2}\) and \(Source_{3}\) to \(node_{10}\), while, \(node_{10}\) needs forward data packets of \(Source_{1}\), \(Source_{2}\), \(Source_{3}\), \(Source_{4}\) and \(Source_{5}\) to \(Agent_{1}\).