## 4 Analysis
### Overhead Analysis  
In our mechanism, each node should update location-based private key when it moves out of its own MSA. The expected numbers of nodes, which update their location-based keys in interval T, are evaluated. Let \(\text{E}_{\text{update}}\) denote the expected numbers. First of all, the upper limit of the expected numbers will be derived. We assume that all nodes move at the maximum speed \(\text{V}_{\text{max}}\). In an interval \(\text{T}_{\text{i}}\), nodes are deployed at different positions within their own MSA at a certain time. Every node's moving distance is no more than \(\Delta\) in next interval T. Since the moving directions of nodes are chosen randomly, nodes update their location-based keys when they move out of their own MSAs. The probability for updating location-based keys is derived as follows:  
\[P_{update}\,=\,1-\frac{S}{\pi\Delta^{2}} \tag{11}\]  
If node u is within its own MSA, the location-based key is always valid. Let \(\pi\Delta^{2}\) denote the set of regions that node u can get to in next interval T. As shown in Figure 6, S denotes the overlapped region. The probability for updating the location-based key is the probability that node u moves out of the MSA. Figure 6: An example of updating the location-based keys in an extreme case. We use binomial distribution to compute expected numbers. Then E\({}_{\text{update}}\) can be calculated by equation E\({}_{\text{update}}\) = N \(\times\) P\({}_{\text{update}}\). Let N denote the total number of nodes in the network; the value of E\({}_{\text{update}}\) is 0.609N by calculation. This means that 60.9% of nodes will update their location-based private keys in interval T when all nodes are deployed at the boundary of their own MSAs and move at the maximum speed V\({}_{\text{max}}\). It is also the largest value of E\({}_{\text{update}}\). We assume that the density of nodes is a constant \(\rho\). In general, node u is randomly deployed in its own MSA. The radius of each MSA is divided into k equal parts, that is to say, each MSA is partitioned into a circular area and k-1 concentric ring areas. We assume that each node is deployed at the boundary of one of the k areas and moves at the speed V\({}_{\text{max}}\). Let N\({}_{\text{i}}\) denote the number of nodes in the i-th area and A\({}_{\text{i}}\) denote the area of the i-th region. Equation (12) calculates the number of nodes in each area:  
\[N_{i}=\rho\times A_{i} \tag{12}\]  
N denotes the total number of nodes in MSA. Then, we can derive:  
\[\text{N}=\sum_{i=1}^{k}N_{i}=\sum_{i=1}^{k}(\rho\times A_{i}) \tag{13}\]  
Figure 7 is an example illustrating how to divide MSA when k = 3. There is no doubt that nodes must be deployed in one of these 3 divided areas. We assume that all nodes are deployed at the boundary of their areas, as shown in Figure 8a-c. S\({}_{1}\), S\({}_{2}\) and S\({}_{3}\) all denote the overlapped area between the region that nodes can get into in the next time interval and the current MSA. Equation (14) calculates the expected number of key-updating nodes:  
Figure 8: An example of how nodes are deployed at the boundary of area (**a**) A1; (**b**) A2 and (**C**) A3. Figure 7: An example of how to divide MSA when k = 3. \[\text{E}=\sum_{i=1}^{k}p_{i}\times N_{i} \tag{14}\]  
In the equation, \(\text{N}_{i}\) denotes the number of nodes in the i-th area, and \(\text{P}_{i}\) denotes the corresponding key-updating probability. With the value of k increasing, MSA will be finely partitioned, hence the expected number E will decrease gradually and eventually keep stable at 0.41 N. Figure 9 shows the upper limit of the expected numbers of key-updating nodes. It seems that there are many nodes need update their location-based private keys in one period T. However the expected number is computed in the extreme case that all nodes are updated at the boundary of their own MSAs and move at the maximum speed, the number of the key-updating nodes will be smaller in actuality.