# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### Overview of PoiFord  
Our model in Section 3 showed that maintaining encounter history about more nodes leads to more contact information overhead, which is in turn directly proportional to the delay incurred in exchanging contact information and the energy utilized in the process. Therefore, less contact information implies less delay and energy consumption. The only problem is how to achieve this without degrading throughput. PoiFord is focused on reducing the amount of encounter history maintained by nodes so that less contact information would be exchanged during encounters. The basic idea behind the approach is as follows. Users often return to their points-of-interest (POIs) in which they may encounter other users that visit the same location regularly. Thus, there is a high chance that most well-connected nodes have at least one mutual POI (e.g., users living in the same house or working in the same office). PoiFord aims to minimize contact information by requiring only nodes that have mutual POIs to maintain encounter history for each other. By limiting information to be maintained only for neighbors with mutual POIs, the problem of existing location-based solutions (i.e., inferring future encounters from location-based information alone) can be addressed while the forwarding ability of nodes that are less connected to the destination can be inferred from location-based information, specifically through spatial locality. That way, nodes moving towards a destination that is located in a shopping small would carry a message and forward it to a node that has a mutual POI with the destination (i.e., a node whose user works in a shopping mall) to deliver it. Hence, the task of reducing contact information overhead without degrading throughput can be divided into three subtasks:  
1. Determining a node's significant locations or POIs. 2. Determining nodes for which to maintain encounter history based on mutual POIs. 3. Determining a forwarding utility that can deliver messages with the available information. \begin{table}
\begin{tabular}{c c c c c c} \hline \multirow{2}{*}{**Forwarding Solution**} & \multirow{2}{*}{\begin{tabular}{c} **Low Contact** \\ **Info.** \\ **Overhead** \\ \end{tabular} } & \multirow{2}{*}{\begin{tabular}{c} **No Message** \\ **Flooding** \\ \end{tabular} } & \multirow{2}{*}{\begin{tabular}{c} **Can Determine Better** \\ **Forwardes among** \\ **Home Nodes** \\ \end{tabular} } & \multicolumn{2}{c}{\
\begin{tabular}{c} **Does Not Infer** \\ **Encounters from** \\ **Location-Based** \\ **Information Alone** \\ \end{tabular} } & \multirow{2}{*}{
\begin{tabular}{c} **Improves** \\ **Delivery** \\ **Guarantees** \\ \end{tabular} } \\ \hline HERO [29] & \(\surd\) & \(\surd\) & \(\times\) & \(\times\) & \(\times\) \\ A-HERO [48] & \(\surd\) & \(\times\) & \(\times\) & \(\times\) & \(\times\) \\ HERO++ [49] & \(\surd\) & \(\surd\) & \(\surd\) & \(\times\) & \(\times\) \\ LOC [53] & \(\surd\) & \(\surd\) & \(\surd\) & \(\times\) & \(\times\) \\ Our proposal (PoiFord) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) \\ \hline \end{tabular}
\end{table} 
Table 3: Relevant forwarding solutions and their main features. This section overviews PoiFord by presenting the tasks involved in realizing the three subtasks. As shown in Figure 1, the subtasks are addressed in three phases. **Phase 1. ** The first phase is concerned with determining POIs. The current location is collected via GPS at fixed intervals and maintained in device memory. From this, significant locations are determined at larger fixed intervals. The major challenge in this phase is how to maintain GPS coordinates from which significant locations can be determined, knowing that the same pair of coordinates may never be recorded twice. To address this, we propose PoiTrace, a mechanism that maintains incoming GPS locations in a location table after converting them to a more stable form we call location references, from which POIs are determined. This minimizes the focus area for each node, as compared to the entire network area.