# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### PoiFord Design
#### 4.2.2 Phase 2: Encounter Relevance and Maintaining Encounter History  
In this section, we present PoiEncounters, the mechanism for determining relevant encounters and maintaining encounter history using the significant locations identified in the previous section. Without any loss of generality, and to demonstrate how PoiFord can be incorporated into an existing routing protocol, PoiEnconters adopts PRoPHET's approach for acquiring and computing encounter history, with two major modifications (Note that besides PRoPHET's, algorithms of other existing encounter-based routing protocols can be utilized. This demonstrates the flexibility of PoiFord). Unlike PRoPHET, which maintains encounter history for every encountered node, encounter history between \(a\) and \(b\), a node pair, is maintained if and only if at least one of the significant locations of \(a\)'s intersects with at least one of \(b\)'s. Also, PoiEncounters does not utilize the transitive property.  
**Determining encounter relevance.** Upon encounter, two nodes \(a\) and \(b\) exchange summary vectors containing their significant locations, which in this case are their home and work locations, as well as the encounter history stored at each node. With this information, each node determines if the circular area of radius \(r\) formed from either of its significant locations intersect with the circular area formed from either of the other's. Given their home location as \(home_{a}\), \(home_{b}\) and their work location \(work_{a}\), \(work_{b}\), respectively, each node determines if \(home_{a}\) intersects with \(home_{b}\) or \(work_{b}\), and if \(work_{a}\) intersects with \(home_{b}\) or \(work_{b}\). Let \(\{x_{sA},y_{sA}\}\) represent the coordinates of \(a\)'s home or work location, and \(\{x_{sB},y_{sB}\}\) represent the coordinates of \(b\)'s home or work location. If there is an intersection (i.e., if \(d_{sA,sB}<2r\)), \(a\) maintains/updates its encounter history for \(b\), and \(b\) does the same for \(a\). The idea is to find nodes that share the same significant location. \(2r\) (i.e., the diameter of the circle) represents the span of the area of concern, which may either be a living home or an office.  
**Maintaining and updating encounter history.** The encounter history table holds encounter records in the form of node ID and delivery predictability [39]. Updating the encounter history table is done in two steps. First, each node checks its encounter history table if an encounter history for the other node \(e_{(a,b)}\) already exists. Then the necessary PRoPHET operations are carried out as follows: if a history exists, it is aged based on \(k\), the number of time units elapsed since the last encounter, as shown in Equation (9), where \(\gamma\in[0,\ 1)\) is the aging constant; otherwise, it is assigned a value of \(0\).  
\[e_{(a,b)aged}=e_{(a,b)}\times\gamma^{k} \tag{9}\]  
With this value, the encounter history (or new encounter history if there was a previous encounter) is computed using Equation (10), where \(e_{init}\epsilon[0,\ 1]\) is an initialization constant.  
\[e_{(a,b)}=e_{(a,b)aged}+\left(1-e_{(a,b)aged}\right)\times e_{init} \tag{10}\]  
After computing the encounter history for the node pair, the encounter history table is updated by inserting this value (or by replacing the old value if there was a previous encounter). Algorithm 2 summarizes the process of updating the encounter history table when two nodes encounter each other.