## 5 The Proposed GMDPSO for Our Protocol
### GMDPSO: Greedy Discrete PSO with Memory
A routing tree is constructed by decoding the encoded particle, in which each route path from a source node to sink can be built by appending relay nodes one by one till the agent node is selected as the end._

As shown in Figure 4c, the path tree can be decoded as follows: firstly, the routing path of \(\mathit{Source}_{1}\) (i.e., \(\mathit{node}_{11}\)) is built as \(\mathit{Path}_{1}\): \(\mathit{Source}_{1}\)\(\rightarrow\)\(\mathit{node}_{4}\)\(\rightarrow\)\(\mathit{node}_{5}\)\(\rightarrow\)\(\mathit{node}9\)\(\rightarrow\)\(\mathit{Agent}_{1}\).Then, routing path of \(\mathit{Source}_{2}\) (i.e., \(\mathit{node}_{12}\)) is built as \(\mathit{Path}_{2}\):\(\mathit{Source}_{2}\)\(\rightarrow\)\(\mathit{node}_{3}\)\(\rightarrow\)\(\mathit{node}_{10}\)\(\rightarrow\)\(\mathit{Agent}_{1}\), and at last, the whole routing tree can be constructed by combining \(\mathit{Path}_{1}\) and \(\mathit{Path}_{2}\). It can be seen from Figure 4 that our discrete position definition is straightforward and easy to decode and will lower the computational complexity, especially in the case of large-scale MWSNs, because the dimensions of the fitness function is equal to the size of candidate relay nodes collected by sink which is smaller than the entire MWSN size. **Definition 2** (Velocity). : _Velocity is a very crucial component in PSO, by working on the position vector, it guides a particle and determines whether it can reach its destination and by how fast it could. Our discrete velocity of particle \(i\) is defined as \(V_{i}=\{v_{i}^{1}\), \(v_{i}^{2}\),..., \(v_{i}^{N^{\prime}}\}\), where \(v_{i}^{j}\)\(\in\)[0,1] is binary-coded, \(v_{i}^{j}\) = 1 means that the corresponding element \(x_{i}^{j}\) in \(X_{i}\) will be changed, otherwise, \(x_{i}^{j}\) keeps its original state. \(v_{i}^{j}\) and \(x_{i}^{j}\) have the same dimension._

In canonical PSO, velocity is used to learn knowledge from itself and swarm and finally leads the particle to a better position. In addition, a threshold \(V_{max}\) is used to inhibit particles from flying out of the boundaries because there is a situation whereby when the speed of a particle is substantial. Unlike the continuous optimization, we have known that, in our discrete MWSNs scenarios, to compare two different routing paths from the same source node to the same agent, we only take care about whether their relay nodes are the same. Furthermore, we only need to compare the two relay nodes ID value in the same position of two different routing paths. There are only two results: is equal or no, therefore, the velocity can be encoded binary, and we defined 0 means two relay nodes are the same, 1 means they are different. The first motivation of the velocity definition is to actually reflect the differences between two position vectors. The second motivation of the velocity definition is to prevent particles from flying away, because our velocity is binary-coded, we no longer need \(V_{max}\) parameter. #### 5.2.3 Particle Swarm Initialization

A good initialization mechanism can reduce the searching space to reach global optima faster and promote diversity. Conventional random initialization method for PSO based algorithm is not applicable for our algorithm. The main reason is that random sequence of edges usually results in invalid routing tree that does not terminate on the agent node or that have loops. Therefore, we need

Figure 4: (a) Network topology; (b) Position vector encoded for (a); (c) Routing tree decoded from (b). to design a more efficient initialization method for our protocol. Based on our particle representation for discrete MWSNs, the position vectors initialization focus on how to map the next relay node, in other words, how to select the next relay node for the current one, for example, how to map another node as the next relay node for current node node\({}_{\text{d}}\). Our main idea to solve this problem is that the next relay node for the current one is randomly selected from its neighbors.