# An Affinity Propagation-Based Self-Adaptive Clustering Method for Wireless Sensor Networks
## 4 The Proposed Affinity Propagation-Based Self-Adaptive (APSA) Algorithm
### Set-Up Phase  
The main goal of the set-up process is to find the CHs and divide all the sensor nodes into appropriate clusters. During this phase, the AP algorithm is firstly introduced to find out the optimal cluster number and the position of initial cluster centers. Then K-medoids algorithm is used to achieve the final clustering result. In the traditional K-medoids algorithm, the initial cluster centers are randomly selected which means that the algorithm needs to iterate more time to converge. Additionally, the traditional K-medoids runs easily into local optimal solutions. With the purpose of solving the mentioned problems, AP is adopted to figure out the initial cluster centers to enhance the performance of K-medoids. Firstly, the similarity between sensors can be calculated using the following formula:  
\[s(m,n)=-||X_{m}-X_{n}||^{2}m,n\in\{1,\ldots,N\},m\
eq n \tag{5}\]  
where \(X\) represents the location of sensors and \(s(m,n)\) denotes the similarity between node \(m\) and node \(n\) which is calculated by the square of their Euclidean distance. The similarity indicates whether the node \(n\) is suitable to be the CH for node \(m\). For each node \(n\), a real number \(s(n,n)\) represents the preference that it will be chosen as a cluster head node. \(s(n,n)\) is calculated by Formula (6). \[s(n,n)=p \tag{6}\]  
where \(p\) represents the negative cost of adding a cluster. By numerous simulations, when \(p\) is set as \(-6000\), the AP algorithm can achieve a good result. \(r\) represents the responsibility and \(a\) represents the availability. \(a\) is firstly set as zero, and then \(r\) and \(a\) can be updated using Formulas (7) and (8). \[r(m,n)=s(m,n)-\max\limits_{n^{\prime}\
eq n}\{s(m,n^{\prime})+a(m,n^{\prime})\} \tag{7}\]  
\[a(m,n)=\left\{ \begin{array}{ll}\sum\limits_{m^{\prime}\
eq m}max\{0,r(m^{ \prime},n)\}&if\ n=m\\ min\{0,r(n,n)+\sum\limits_{m^{\prime}\
eq[m,n]}max\{0,r(m^{\prime},n)\} \}&if\ n\
eq m^{\prime}\end{array} \right. \tag{8}\]  
where \(r(m,n)\) is defined as the value of the degree of node \(n\) if node \(n\) is selected as the CH of node \(m\). \(a(m,n)\) represents the appropriate degree of node \(m\) to select \(n\) as its CH. Finally, Formula (9) is used to calculate the initial cluster centers. \[T=argmax\limits_{n}\{a(m,n)+r(m,n)\} \tag{9}\]  
where \(T\) represents the set of the initial cluster centers. The pseudocode of AP is described as Algorithm 1. ```
Input: the coordinate set of \(N\) sensor nodes \(\{X_{1},X_{2},X_{3},\cdots,X_{N}\}\); for\(i=1,2,3,\ldots,N\)do for\(j=1,2,3,\ldots,N\)do if\(i==j\)then set preference\(S_{i,j}=-6000\) else calculate similarity\(S_{i,j}=-\|X_{i}-X_{j}\|^{2}\) endif endfor endfor Repeat for\(i=1,2,3,\ldots,N\) for\(j=1,2,3,\ldots,N\)  calculate responsibility\(R_{i,j}=S_{i,j}-\max\limits_{j^{\prime}\
eq j}\{S_{i,j^{\prime}}+A_{i,j^{ \prime}}\}\) if\(i==j\)then \(A_{i,j}=\sum\limits_{i^{\prime}\
eq i}max\{0,R_{i^{\prime},j}\}\) else \(A_{i,j}=min\{0,R_{i,j}+\sum\limits_{i^{\prime}\in[i,j]}max\{0,R_{i^{\prime},j }\}\}\) endif calculate \(T=argmax\limits_{j}\{A_{i,j}+R_{i,j}\}\) Endfor Endfor Until\(T\) does not change
```  
**Algorithm 1** The method for obtaining initial cluster centers  
The initial cluster centers obtained through the AP algorithm are not optimal, and there may be outliers. Due to the disadvantages above, the K-medoids algorithm is adopted to further optimize the clustering results. K-medoids adopts real points as the cluster centers instead of virtual points, and therefore the absolute errors can be effectively reduced. By combining the advantages of AP and K-medoids algorithm, the distance between the member node and its corresponding CH is minimized. Formula (10) describes the problem that the algorithm needs to solve. We want to study how to minimize the criterion of the absolute error \(\sigma\). \[\sigma=\sum_{i=1}^{k}\sum_{s\in T_{i}}dist(s,T_{i}) \tag{10}\]  
where \(s\) is the common node in \(T_{i}\) and \(T_{i}\) represents the set of nodes of cluster \(i\).