## 3 A Centralised Mapping Service
### A New Network Service: Map Generation  
Often, WSNs field data collection takes the form of single points that need to be processed to get a continuous map. The problem of map generation is essentially a problem of interpolation from sparse and irregular points. Interpolation describes the process of taking many single points and building a complete surface, the inter-node gaps being filled based on the spatial statistics of the observation points.  
Through extensive empirical analysis and research, published in [20], we identified the Shepard interpolation algorithm [18] as a suitable algorithm for the distributed mapping service. Visual aspects, sensitivity to parameters, and timing requirements were used to test the characteristics of this method. Shepard interpolation was found to be an attractive solution due to its wide use in the literature. It is intuitively understandable and provides a large variety of possible customisations to suit particular purposes, e.g. relaxation of the interpolation condition for noisy data sets [21]. Also, [PERSON]'s method can be easily modified to incorporate different external conditions that might have an impact on the interpolation results, such as physical barriers. [PERSON]'s method is simple to implement with fast computation and modelling time [22; 23] and generalisation to more than two independent variables is feasible. This method can be localised, which is an advantage for large and frequently changing data sets, making it suitable for sensor network applications. Local map generation by Shepard function reduces data communication across the network and evades the computation of the complete network map when one or more observations are changed. Finally, there are few parameter decisions and it makes only one assumption, which gives it the advantage over other interpolation methods [22].  
[PERSON] defined a continuous function where the weighted average of data is inversely proportional to the distance from the interpolated location. The algorithm explicitly implies that the further away a point is from an interpolated location, \(P\), the less effect it will have on the interpolated value. This algorithm exploits the intuitive sense that things that are close to each other are more alike than those that are further apart.  
Data points, \(D_{i}\), are weighted during interpolation relative to their distance from \(P\). Weighting is assigned to data through the use of a weighting power, which controls how the weighting factors drop off as the distance from \(P\) increases. [PERSON]'s expression for globally modelling a surface is:  
\[f_{1}(P)=\left\{\begin{aligned} &\sum_{i=1}^{N}\left[(d_{i})^{-u}z_{i} \right]\\ &\sum_{i=1}^{N}(d_{i})^{-u}\\ & z_{i}\end{aligned}\right.\text{ if }d_{i}\
eq 0\text{ } \forall\text{ }D_{i}(u>0) \tag{1}\]  
where \(d_{i}\) is the standard distance metric from \(P\) to the point \(D\) numbered \(i\) in the \(N\) known points set and \(z_{i}\) is the known value at point \(D_{i}\). The exponent \(u\) is used to control the smoothness of the interpolation. As the distance between \(P\) and \(D_{i}\) increases, the weight of that sampled point will decrease exponentially. As \(P\) approaches \(D_{i}\), \(d_{i}\) tends to zero and the \(i\)th terms in both the numerator and denominator exceeds all bounds while other terms remain bounded. Therefore, the \(lim_{P\to D_{i}}f_{1}(P)=z_{i}\) is as desired and the function \(f_{1}(P)\) is continuously differentiable even at the junctions of local functions.