# Collecting Sensed Data with Opportunistic Networks: The Case of Contact Information Overhead
## 4 An Algorithm for Reducing Contact Information Overhead
### PoiFord Design
#### 4.2.4 Forwarding Algorithm  
PoiFord forwards messages to suitable relays using the PoiUtility. The operation of PoiFord is as follows. When any node \(a\) with a list of messages, \(\{m_{a}\}\), encounters another node, \(b\), node \(a\) receives a summary vector from node \(b\) containing:  
* List of message identifiers in node \(b^{\prime}\)s buffer, \(\{m_{b}\}\);
* Node \(b^{\prime}\)s POIs, i.e., home and work location, \((x_{h},y_{h})\) and \((x_{w},y_{w})\), respectively (with which node \(a\) determines whether or not to maintain encounter history with node \(b\)--node \(a\) updates the previous value if one already exists);
* Node \(b^{\prime}\)s encounter history table, \(\{ET_{b}\}\) (with which node \(a\) computes node \(b^{\prime}\)s encounter history weight, \(E_{(b,d)}\), for the destination node, \(d\), of each message in \(\{m_{a}\}\)--this value is 0 for a destination node that node \(b\) has no encounter history with); and
* \((\overline{x}_{b},\overline{y}_{b})\) (with which node \(a\) computes the closeness-to-destination utility of node \(b\) for each message in \(\{m_{a}\}\)).  
With this information and others available in message headers (i.e., the destination node location, \((x_{d},y_{d})\), and the Euclidean distance from this location to the source node's location, \(d_{s,d}\)), node \(a\) computes \(PoiUtility_{(b,s,d)}\) for each message in \(\{m_{a}\}\). A straightforward replication technique is adopted onwards: node \(a\) compares \(PoiUtility_{(a,s,d)}\) and \(PoiUtility_{(b,s,d)}\), then a copy of any message in its buffer for which it has a less PoiUtility is forwarded to node \(b\), provided the message is not already in \(\{m_{b}\}\). The strategy for selecting suitable relay nodes among a set of peers (i.e., nodes within transmission range) to forward messages is summarized in Algorithm 4.  
```
Input: list of messages in buffer \(\{m_{a}\}\), set containing list of messages in peers' buffers \(\{m_{b}\}\), set of encounter history table of peers \(\{ET_{b}\}\), \((\overline{x}_{a},\overline{y}_{a})\), set of centroid of location references in peers' location tables \((\overline{x}_{b},\overline{y}_{b})\) Output: list of suitable relay node against respective message \(\{B,M\}\)
1 foreachInput \(\{m_{a}\}\)do
2 Obtain \((x_{d},y_{d})\) from the header of \(m_{a}\);
3 Obtain \(d_{s,d}\) from the header of \(m_{a}\);
4\(dMin_{a,d}=\sqrt{(\overline{x}_{a}-x_{d})^{2}+(\overline{y}_{a}-y_{d})^{2}}\);
5\(E_{(a,d)}=e_{(a,d)}\times\mu\);
6\(D_{(a,s,d)}=\left(1-\left(dMin_{a,d}/d_{s,d}\right)\right)\times\omega\);
7\(PoiUtility_{(a,s,d)}=E_{(a,d)}+D_{(a,s,d)}\);
8 foreachInput \(\{ET_{b},(\overline{x}_{b},\overline{y}_{b})\}\)do
9\(dMin_{b,d}=\sqrt{(\overline{x}_{b}-x_{d})^{2}+(\overline{y}_{b}-y_{d})^{2}}\);
10\(E_{(b,d)}=e_{(b,d)}\times\mu\);
11\(D_{(b,s,d)}=\left(1-\left(dMin_{b,d}/d_{s,d}\right)\right)\times\omega\);
12\(PoiUtility_{(b,s,d)}=E_{(b,d)}+D_{(b,s,d)}\);
13 if\(PoiUtility_{(b,s,d)}>PoiUtility_{(a,s,d)}\)then
14 if\(\{m_{b}\}\) does not contain \(m_{a}\)do
15 Insert \(\{b,m_{a}\}\) into \(\{B,M\}\);
16
17 end if
18
19 end for
20 return\(\{B,M\}\);
```  
**Algorithm 4** Selecting suitable relay nodes for messages with PoiFord