# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### PoiFord Design
#### 4.2.1 Phase 1: Identification of Significant Locations  
Phase 1 presents the design of PoiTrace, for identifying POIs. User movement may reveal multiple significant locations and can be exploited for routing. However, we are interested in investigating how our POI approach can reduce contact information overhead. In order to keep the idea comprehensive, the mechanism proposed here identifies only the two most significant locations, which we refer to as \"home\" and \"work\" location. Apart from these locations often corresponding to the actual home and work locations of users, research also shows that most users have at least two most significant locations and regularly commute between them [59]. **Collecting and recording location information. ** At every sampling interval \(\Delta t\), each node collects its current position by GPS in form of latitude and longitude and records it in the corresponding time slot in the location table (cf. Definition 1)--note that PoiFord is fully distributed and does not require synchronization between devices. For example, \((x_{i},y_{i})\), the GPS coordinates collected at \(\Delta t_{i}\), the current sampling interval, are recorded in the current time slot as \(loc_{i}\), a location reference. Although GPS is globally available, the signal may not always be reliable in geographically restricted areas (e.g., in buildings and underground locations). In case the signal is too weak or lost, the current position is approximated as the previous record in the location table. **Definition 1 (Location Table). **_The location table, \(LT\), which consists of \(n\) time slots, is a set of \(n\) elements, each known as a location reference (cf. Equation (6)). Each location reference \(loc_{i}\in LT\) is a tuple of the format \(loc_{i}=\langle x_{i},y_{i}\rangle\), where \(i\) (\(\{i:Z|i\in 1\ \ldots\ n\}\)) indicates the current time slot._  
\[LT=\ \{loc_{1},loc_{2},loc_{3},\ldots,loc_{n}\}=\{\langle x_{1},y_{1} \rangle,\langle x_{2},y_{2}\rangle,\langle x_{3},y_{3}\rangle,\ldots,\langle x _{n},y_{n}\rangle\} \tag{6}\]  
The basic idea behind the algorithm for recording location information is as follows: location references in \(LT\) should be able to map geographical locations visited for longer periods from user movement, by representing them with circular areas. In order to achieve this, a certain extent of deviation between successive incoming GPS locations is tolerated while acquiring location references. The location reference \(loc_{a}\) for any two locations \((x_{1},y_{1})\) and \((x_{2},y_{2})\) is the same if the circular areas formed by radius \(r\) from both locations intersect. This condition is fulfilled if the Euclidean distance between the two locations \(d_{1,2}\) is less than \(2r\) (cf. Equation (7)). \[d_{1,2}=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}} \tag{7}\]  
Hence, if the circular area formed by \(r\) from any incoming pair of coordinates \((x_{i},y_{i})\) intersects with the circular area formed by \(r\) from a previous pair of coordinates \((x_{a},y_{a})\), the corresponding location reference \(\langle x_{a},y_{a}\rangle\) is formed from the existing coordinates. Otherwise, a location reference \(\langle x_{i},y_{i}\rangle\) is formed from the incoming coordinates (cf. Equation (8) and Figure 2). \[loc_{i}=loc(d_{a,i})=\left\{ \begin{array}{ll}\langle x_{a},y_{a}\rangle,&d_{a,i}<2r\\ \langle x_{i},y_{i}\rangle,&d_{a,i}\geq 2r\end{array} \right. \tag{8}\]  
Algorithm 1 summarizes how \(loc_{i}\) is acquired using the current location in the form of latitude \(x_{i}\) and longitude \(y_{i}\), the previous location references in \(LT\), and a threshold distance \(r\). Consequently, the number of recurrences of a location reference \(loc_{a}\) in \(LT\) represents the number of periods in which the user is present in the circular area formed by \(r\) from location \((x_{a},y_{a})\).