## 3 Reducing Transmission Overhead without Compromising Throughput
### LARep Design
#### 3.2.1 Phase 1: Determining the Relative Distance between Nodes  
Phase 1 introduces PoiTrace [73], a mechanism that maintains region-based information from which the most significant locations visited by a node can be inferred. 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. Besides these locations often corresponding to home and work locations, research also shows that most users have at least two most significant locations and regularly commute between them [74]. 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 LARep 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 as \(loc_{i}\), a location reference in the current time slot. **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 (1)). 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{1}\]  
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 met if \(d_{1,2}\), the Euclidean distance between the two locations, is less than \(2r\) (cf. Equation (2)). \[d_{1,2}=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}} \tag{2}\]  
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})\), then \(\langle x_{a},y_{a}\rangle\), the corresponding location reference, is formed from the existing coordinates. Otherwise, a location reference \(\langle x_{i},y_{i}\rangle\) is formed from the incoming coordinates (cf. Equation (3) and Figure 12). \[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{3}\]  
Algorithm 1 summarises 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})\).