# Information Relaying Methods in VANET: Algorithms, Standards and Tests
## 4 Enhanced K-Means-Type Algorithm
### Mathematical Formulation of the VANET Seeding Principle  
Recalling the vehicle nodes and cluster centers defined in (3), we recalculate the formulation of the objective function in [6] by imposing the constraints mentioned in Section 4.2. The following mathematical problem is obtained with a restriction on the distance between two consecutive cluster centers, which is formulated in (4) and corresponds to the proposed seeding principle for the VANET.  
\[\text{minimize}f(W,C)=\sum_{i=1}^{k}\sum_{j=1}^{m}w_{ij}D\big{(}v_{j},c_{i} \big{)}\] (5) subject to \[\sum_{i=1}^{k}w_{ij}=1,\,j=1,2,\cdots,m,\] \[w_{ij}=0\,\text{or}\,1,\,i=1,2,\cdots,k,\] \[\sum_{i=2}^{k}\Big{|}c_{i}^{(l)}-c_{i-1}^{(l)}\Big{|}\leq(k-1)D^{*},\]  
where \(W\) is a \(k\times m\) real matrix, \(C=\big{[}c_{1},c_{2},\cdots,c_{k}\big{]}\) is the set of cluster centers, \(D\big{(}v_{j},c_{i}\big{)}\) measures the dissimilarities between \(v_{j}\) and \(c_{i}\), and \(l\) represents the number of iterations.  
**Proposition 1**.: \(c_{k}^{*}\) _is the local minimum cluster center of the objective function (5)._  
Proof.: To obtain the local minimum cluster center, we adopt the Lagrange multipliers method to form a Lagrangian function with the KKT condition as follows.  
\[L(c,\mu) =\sum_{i=1}^{k}\sum_{j=1}^{m}w_{ij}D\big{(}v_{j},c_{i}\big{)}\] \[+\sum_{j=1}^{m}\mu_{j}\left[\sum_{i=2}^{k}\Big{|}c_{i}^{(l)}-c_{i -1}^{(l)}\Big{|}-(k-1)D^{*}\right]\] \[+\sum_{j=1}^{m}\lambda_{j}\left(\sum_{j=1}^{k}w_{ij}-1\right) \tag{6}\]  
By setting \(\bigtriangledown_{c_{k}}L=0\), we obtain a potential local minimum through  
\[\frac{\partial L}{\partial c_{k}}=\frac{\partial A}{\partial c_{k}}+\frac{ \partial B}{\partial c_{k}}=0, \tag{7}\]where  
\[A =\sum_{i=1}^{k}\sum_{j=1}^{m}w_{ij}D(v_{j},c_{i})\] \[B =\sum_{j=1}^{m}\mu_{j}\left[\sum_{i=2}^{k}\left|c_{i}^{(l)}-c_{i-1} ^{(l)}\right|-(k-1)D^{*}\right]\] \[\frac{\partial}{\partial c_{k}}\sum_{j=1}^{m}\lambda_{j}\left( \sum_{j=1}^{k}w_{ij}-1\right)=0.\]  
Then, we obtain  
\[c_{k}^{*}=\frac{\sum_{j=1}^{m}w_{ij}v_{j}+\mu_{j}c_{k-1}}{\sum_{j =1}^{m}w_{ij}\mu_{j}}, \tag{8}\] \[\sum_{j=1}^{m}\mu_{j}=\frac{\sum_{j=1}^{m}w_{ij}(c_{k}-v_{j})}{c_ {k-1}-c_{k}}. \tag{9}\]  
Suppose that \(c_{k}^{*}\) fulfills the local minimum requirement; then, a unique \(\mu^{*}\) exists, subject to the following:  
\[\bigtriangledown_{c_{k}}L(c_{k}^{*},\mu^{*}) =0, \tag{10}\] \[\mu^{*}\geq 0,\] (11) \[\mu^{*}g(c_{k}^{*}) =0, \tag{12}\]  
where \(g(c_{k}^{*})=\sum_{i=2}^{k}\left|c_{i}^{(l)}-c_{i-1}^{(l)}\right|-(k-1)D^{*}\leq 0\). For (12), consider two cases: \(\sum_{j=1}^{m}\mu_{j}=0\) and \(\sum_{j=1}^{m}\mu_{j}>0\). Thus,  
\[c_{k}^{*}=\max\left\{v_{j}\&w_{ij}=1,\frac{\sum_{j=1}^{m}w_{ij}v_{j}+\mu_{j}c _{k-1}}{\sum_{j=1}^{m}w_{ij}+\mu_{j}}\right\}. \tag{13}\]  
It is obvious that \(\mu^{*}g(c_{k}^{*})=0\) if \(\mu^{*}=0\). When \(\mu^{*}\geq 0\), the following approximation is obtained:  
\[\lim_{l}g(c_{k}^{*})=\sum_{i=2}^{k}\left|c_{i}^{(l)}-c_{i-1}^{(l)}\right|-(k- 1)D^{*}\approx 0. \tag{14}\]  
Hence, \(c_{k}^{*}\) is the local minimum cluster center position of the objective function (5). This ends the proof.  
As an NP-hard problem, the result could be easily falling into the local optimal circle instead of a global one due to its nature. Any deterministic algorithms targeting the optimization of the system performance in terms of minimizing or maximizing the objective function may have negative impacts on the overall performance. As such, we proposed to partition the clustering layout for the sake of local optimal relaying network, then connect different clusters for a nearly global optimization outcome.