# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### PoiFord Design
#### 4.2.3 Phase 3: Forwarding Utility  
In this section, PoiUtility, the forwarding utility for PoiFord is determined using the available encounter history. Since nodes maintain encounter history for only a specific set of nodes (i.e., ones with which they share mutual POIs), neighboring nodes may not have any encounter history with the destination, especially when the destination's POIs are located in far-away districts. Hence, instead of a transitive property (which tends to increase contact information size with node population as nodes may eventually have to compute and maintain a forwarding utility for every other node in the network), geographical closeness to the destination is used to determine the forwarding ability of a node that has no encounter history with the destination. Encounter history with the destination is only considered when nodes that share a mutual POI with the destination are encountered. Therefore, PoiUtility, the overall forwarding utility, comprises of a location-based utility and an encounter-based utility. **Measuring closeness-to-destination. ** The information maintained in the encounter history table does not include a transitive property, i.e., a means of computing the likelihood of \(b\) to deliver a message to the destination \(d\) through \(c\), based on the encounter history of \(b\) and \(c\), and that of \(c\) and \(d\). Hence, the location-based \"closeness-to-destination\" utility is used to select a node that can take the message closer to the destination, and possibly improve the likelihood of forwarding it to nodes that have an encounter history with the destination. The main conditions are that for each message: (i) the location of the destination node, \(d\), denoted by \((x_{d},y_{d})\), is known by the source node--e.g., each sensor node can be preconfigured with this information during network initialization (PoiFord is designed for collecting sensed data from sensors--which may either be mobile (e.g., mobile user devices) or static (e.g., sensors deployed along roadsides) to their respective static gateways (e.g., an access point in a shopping mall) in Smart City scenarios. Each sensor node can be preconfigured with the location of the destination node(s) during network initialization. In case a destination node needs to be moved or replaced, the new information can be disseminated to the sources through the network); and (ii) the source node can compute the Euclidean distance from its location, \((x_{s},y_{s})\), to thedestination node's location, denoted by \(d_{s,d}\). With this information available in the message header, the closeness of a node \(a\) to the destination, \(d\), denoted by \(dMin_{a,d}\), can be determined. The procedure starts by computing \((\overline{x}_{a},\overline{y}_{a})\) as shown in Algorithm 3, which is the centroid of the location references in \(a\)'s location table, \(LT_{a}\). In other words, \(\overline{x}_{a}\) and \(\overline{y}_{a}\) are the mean values of the \(x\) and \(y\) coordinates of every location reference in \(LT_{a}\), respectively. Then \(dMin_{a,d}\) is given by the Euclidean distance between \((\overline{x}_{a},\overline{y}_{a})\) and \((x_{d},y_{d})\). Note that for a static source node, \(s\), \(dMin_{s,d}=d_{s,d}\), i.e., the closeness-to-destination utility of \(s\) is equivalent to the Euclidean distance from \(s\) to the destination node, \(d\). ```
Input: location references in \(LT[loc_{a}]\) Output:\((\bar{x}_{a},\overline{y}_{a})\)
1\(i=0\);
2\(\bar{x}_{a}=0\);
3\(\bar{y}_{a}=0\);
4 foreach\(Input\)\(\{loc_{a}\}\)do
5\(\bar{x}_{a}=\bar{x}_{a}+x_{a}\);
6\(\bar{y}_{a}=\bar{y}_{a}+y_{a}\);
7\(i=i+1\);
8 end fore
9\(\bar{x}_{a}=\bar{x}_{a}/i\);
10\(\bar{y}_{a}=\bar{y}_{a}/i\);
11 return\((\bar{x}_{a},\bar{y}_{a})\);
```  
**Algorithm 3** The algorithm for acquiring \((\overline{x}_{a},\overline{y}_{a})\)  
**Overall forwarding utility. ** The overall forwarding utility (i.e., the PoiUtility) of a node is given by summing the weight for encounter history and the weight for closeness-to-destination.