For designing the perturbation algorithms, we start with the assumption that the anonymity server knows the current position of all subjects. The subject's mobile nodes could periodically update their position information with the anonymizer.
While anonymity is etymologically defined as ``being nameless'' or ``of unknown authorship'' [31], information privacy researchers interpret it in a stronger sense. According to Pfitzmann and Koehntopp, ``anonymity is the state of being not identifiable within a set of subjects, the anonymity set''[11]. Inspired by Samarati and Sweeney [28], we consider a subject as k-anonymous with respect to location information, if and only if the location information presented is indistinguishable from the location information of at least k - 1 other subjects.
Unless otherwise stated, we assume that location information includes temporal information (i.e., when the subject was present at the location). More specifically, location information is represented by a tuple containing three intervals ([x1, x2],[y1, y2],[t1, t2]). The intervals [x1, x2] and [y1, y2] describe a two dimensional area where the subject is located. [t1, t2] describes a time period during which the subject was present in the area. Note that the intervals represent uncertainty ranges; we only know that at some point in time within the temporal interval the subject was present at some point of the area given by the spatial intervals. Thus, a location tuple for a subject is k-anonymous, when it describes not only the location of the subject, but also the locations of k - 1 other subjects. In other words, k - 1 other subjects also must have been present in the area and the time period described by the tuple. Generally speaking, the larger the anonymity set k is, the higher is the degree of anonymity. Thus, we will measure the degree of anonymity as the size of the anonymity set.
The desired degree of anonymity is specified by the parameter kmin, the minimum acceptable anonymity set size. Furthermore, the algorithm takes as inputs the current position of the requester, the coordinates of the area covered by the anonymity server, and the current positions of all other vehicles/subjects in the area.
The spatial discretization algorithm that identifies a sufficiently large area for a given kmin is described in more detail in Table 2. In summary, the algorithm is inspired by quadtree algorithms [32]. It subdivides the area around the subject's position until the number of subjects in the area falls below the constraint kmin. The previous quadrant, which still meets the constraint, is then returned.
An orthogonal approach to spatial cloaking is temporal cloaking. This method can reveal spatial coordinates with more accuracy, while reducing the accuracy in time. The key idea is to delay the request until kmin vehicles have visited the area chosen for the requestor. The spatial cloaking algorithm is modified to take an additional spatial resolution parameter as input. It then determines the monitoring area by dividing the space until the specified resolution is reached. The algorithm monitors vehicle movements across this area. When kmin different vehicles have visited the area, a time interval [t1, t2] is computed as follows: t2 is set to the current time, and t1 is set to the time of request minus a random cloaking factor. The area and the time interval are then returned.