## 5 The Proposed GMDPSO for Our Protocol
### GMDPSO: Greedy Discrete PSO with Memory
After finished _Step 2_, then the position vector _Xi_ will look as following: \(Xi=\{0,9,10,0,9,10,0,13,13,13,0,0\}\). _Step 3_ The relay nodes of remaining nodes are mapped by randomly choosing a node from their neighbor. For example, for \(Source_{1}\) (i.e., node\({}_{11}\)), let random \(n=1\), then its first neighbor is chosen as the next relay node. _Step 4_ Finally, after finished the above three initiation steps, position vector _Xi_ is initiated as \(Xi=\{6,9,10,5,9,10,5,13,13,13,4,3\}\). It is worth noting that the invalid routing tree, in which contains one or more invalid routing path (that does not terminate on the agent node or that have loops), will be punished with a very high fitness. The velocity vectors are initialized as all-zero vectors. The \(P_{best}\) vectors are initialized in the same manner as the position vectors, and the vector is set as the best position vector in the original population. Comparing to the conventional random initialization, the advantages of our initiation method are follows:

1. Since node can and only can select its next relay node from its neighbors based on the network topology of \(G(V,\,E)\), our method takes advantage of this feature to reduce the vast search space significantly. 2. In our method, agent node and its neighbors are mapped firstly in _step1_ and _step3_, and this reduces the likelihood of invalid routing path. In addition, it further reduces search space and drives particle to find its personal best position faster. That is, it speeds the algorithm convergence. #### 5.2.4 Velocity and Position Update

In canonical PSO, velocity gives a particle the moving direction and tendency. After updating its velocity, the particle builds its new position using the new velocity. However, in the proposed algorithm, the particle position and velocity vectors have been redefined in a discrete integer form, and thus, the mathematical updating rules in the canonical continuous PSO no longer fit the discrete case. In order to meet the requirements of building routing tree in discrete MWSNs, the particle's velocity and position updating rules have been redefined as follows:

\[V_{i}\left(t+1\right)=w\times V_{i}\left(t\right)\oplus c_{1}\times r_{1}\times \left(pbest_{i}\ominus X_{i}\left(t\right)\right)+c_{2}\times r_{2}\times \left(Gbest\ominus X_{i}\left(t\right)\right) \tag{28}\]

\[X_{i}\left(t+1\right)=X_{i}\left(t\right)\otimes V_{i}\left(t\right) \tag{29}\]

where \(w\) is the dimensional inertial weight vector, \(c_{1}\) and \(c_{2}\) are two \(N_{V}^{\prime}\) dimensional cognitive and social components, \(r_{1}\) and \(r_{2}\) are two \(N_{V}^{\prime}\) dimensional random vectors in rang [0,1]. Equation (28) is used to update the old velocity, and Equation (29) is the position updating rule. It can be observed that the new updating rules take the same form in canonical PSO but different the key operator. The following will detail our new operators in discrete PSO. **Definition 3 (Position Operator).**\(\ominus\). _Position \(\ominus\) Position builds a velocity vector. Assume that we are given two position vector \(X_{i}=\{x_{i}^{1},\,x_{i}^{2},\,x_{i}^{3}\,\ldots\,x_{i}^{N^{\prime}}\}\) and \(X_{j}=\{x_{j}^{1},\,x_{j}^{2},\,x_{j}^{3},\ldots,\,x_{j}^{N^{\prime}}\}\), \(X_{i}\ominus X_{j}=V=\{v_{1},\,v_{2},\,\ldots,\,v_{N^{\prime}}\}\), the element \(v_{d}\) is defined as:_

\[v_{d}=\left\{ \begin{array}{ll}0&if\quad x_{i}^{k}\,=\,\,x_{j}^{k}\\ 1&otherwise\end{array} \right. \tag{30}\]

Definition 3 is inspired from the following two aspects:

First, it is well known that, in canonical PSO, a particle adjusts its velocity by learning from its old velocity (\(V_{i}(t)\)), personal best position (\(Pbest_{i}\)-\(X_{i}(t)\)) and the swarm global best position (\(Gbest\)-\(X_{i}(t)\)). It can be seen that the learning process is actually a comparison between the positions, that is to say,two position vectors should generate a velocity vector. Second, two position vectors represent two different routing trees.