# Design and Evaluation of Flooding-Based Location Service in Vehicular Ad Hoc Networks+
## 4 Performance Analysis
### Algorithm Scalability  
From the uniform distributions presented above, it was possible to determine the mean number of broadcast messages to update the location information of node \(i\) in a network.  
We first considered a 1D network. The number of nodes at distance \(j\) from node \(i\) was computed above. Each of these nodes retransmitted 1 over \(q^{j}\) times. Thus, the mean number of messages generated per location update is:  
\[\overline{m_{i}}^{(1)} = 1+2\lambda R\sum_{j=1}^{l_{i}}\frac{1}{q^{j}} \tag{4}\]  
Since \(\sum_{i=1}^{l_{i}}\frac{1}{q^{i}}=\frac{1}{q-1}\Big{(}1-\frac{1}{q^{l_{i}}} \Big{)}\), Equation (4) can be rewritten as  
\[\overline{m_{i}}^{(1)} = 1+\frac{2\lambda R}{q-1}\left(1-\frac{1}{q^{l_{i}}}\right). \tag{5}\]  
For the probabilistic approach with the retransmission of a packet with probability \(r\), we have  
\[\overline{m_{i}}^{(1)} = 1+\frac{2\lambda Rr}{1-r}\left(1-r^{l_{i}}\right) \tag{6}\]  
We now consider a 2D network. The number of nodes at distance \(j\) from node \(i\) was upper-bounded above. Each of these nodes retransmitted 1 over \(q^{j}\) times. The mean number of messages generated per location update could be upper-bounded as follows:  
\[\overline{m_{i}}^{(2)} \leq 1+\lambda\pi R^{2}\ \sum_{j=1}^{l_{i}}\frac{2j-1}{q^{j}} \tag{7}\]  
Since  
\[\sum_{i=1}^{l_{i}}\frac{(2i-1)}{q^{l}}=\frac{q+1}{(q-1)^{2}}+\frac{-(2l_{i}+1 )q+2l_{i}-1}{q^{l_{i}}(q-1)^{2}},\]  
Equation (7) can be rewritten as  
\[{m_{i}}^{(2)}\leq 1+\lambda\pi R^{2}\Big{(}\frac{q+1}{(q-1)^{2}}+\frac{-2(l_ {i}+1)q+2l_{i}-1}{q^{l_{i}}(q-1)^{2}}\Big{)}. \tag{8}\]  
For the probabilistic approach, Equation (7) becomes  
\[{m_{i}}^{(2)} \leq 1+\lambda\pi R^{2}\Big{(}\frac{r(r+1)}{(1-r)^{2}}-\frac{r^{l_{i} }((2l_{i}+1)r)-2l_{i}-1)}{(1-r)^{2}}\Big{)}. \tag{9}\]  
We now consider a 3D network. The number of nodes at distance \(j\) from node \(i\) was upper-bounded above. Each of these nodes retransmitted 1 over \(q^{j}\) times. The mean number of messages generated per location update could be upper-bounded as follows:  
\[\overline{m_{i}}^{(3)} \leq 1+\lambda\frac{4}{3}\pi R^{3}\ \sum_{j=1}^{l_{i}}\frac{3^{j}-3j-1}{q^{j}} \tag{10}\]Since  
\[\sum_{j=1}^{l_{i}}\frac{3^{j}2^{-3j-1}-1}{q^{j}} = \frac{-3(l_{i}^{2}+l_{i}+1)q^{2}}{(q-1)^{3}q^{j_{i}}}+\frac{(6l_{i} ^{2}-4)q-3l_{i}^{2}-6l_{i}-10}{(q-1)^{3}q^{j_{i}}}\] \[+\frac{q^{2}+4q+1}{(q-1)^{3}}, \tag{11}\]  
Equation (10) can be rewritten as  
\[\begin{array}{lll}\overline{m_{i}}^{(3)}&\leq&1+\lambda\frac{4}{3}\pi R^{3} \Big{(}\frac{(-3l_{i}^{2}+3l_{i}-1)q^{2}}{(q-1)^{3}q^{i-1}}\\ &&+\frac{(6l_{i}^{2}-12l_{i}+2)q-3l_{i}^{2}-7}{(q-1)^{3}q^{i-1}}+\frac{q^{2}+4 q+1}{(q-1)^{3}}\Big{)}.\end{array} \tag{12}\]  
For the probabilistic approach, Equation (10) becomes  
\[\begin{array}{lll}\overline{m_{i}}^{(3)}&\leq&1+\lambda\frac{4}{3}\pi R^{3} \Big{(}\frac{(-3l_{i}^{2}+3l_{i}-7)r^{2}}{r_{i}^{l_{i}-1}(1-r)^{3}}\\ &&+\frac{(6l_{i}^{2}-12l_{i}+2)r-3l_{i}^{2}+3l_{i}^{2}-1}{r_{i}^{l_{i}-1}(1-r) ^{3}}+\frac{r(r^{2}+4r+1)}{(1-r)^{3}}\Big{)}.\end{array} \tag{13}\]  
From Equations (5), (8), and (12), it is straightforward to demonstrate that  
\[\lim_{l_{i}\rightarrow+\infty}\overline{m_{i}}^{(1)} = 1+\frac{2\lambda R}{q-1}. \tag{14}\]  
\[\lim_{l_{i}\rightarrow+\infty}\overline{m_{i}}^{(2)}\leq 1+\lambda\pi R^{2} \Big{(}\frac{q+1}{(q-1)^{2}}\Big{)} \tag{15}\]  
and  
\[\lim_{l_{i}\rightarrow+\infty}\overline{m_{i}}^{(3)}\leq 1+\lambda\frac{4}{3} \pi R^{3}\Big{(}\frac{q^{2}+4q+1}{(q-1)^{3}}\Big{)}. \tag{16}\]  
These limits are of the \(1+a\times M\) form, where \(M\) is the mean number of neighbors of node \(i\), and \(a\) only depends on \(q\). One can easily derive the mean number of transmissions for node \(i\) with a simple flooding:  
\[\overline{M_{i}}^{(1)}=2\lambda Rl_{i}\simeq N \tag{17}\] \[\overline{M_{i}}^{(2)}=\pi\lambda R^{2}l_{i}^{2}\simeq N\] (18) \[\overline{M_{i}}^{(3)}=\frac{4}{3}\pi\lambda R^{3}l_{i}^{3}\simeq N. \tag{19}\]  
The comparison between \(1+a\times M\) and \(N\) clearly shows the advantage and scaling properties of our proposed algorithm.