## 4 Algorithm Description
### Visiting Order Scheduling  
Once proxy nodes gather the sensed data from their neighboring nodes, these data should be collected by the mobile collector when they are in contact. Usually there are more than one proxy nodes, and \(MC\) has to arrange its visiting order and time slots so that it could gather the maximal amount of data within the limited period. The scheduling could also be viewed as the Proxy node Time Slot Allocation (PTSA) problem. **PTSA Problem**: _Given a set of proxy nodes \(V\), find a set of proxy nodes \(V^{*}=\{v_{1},..,v_{K}\}\) and their visiting schedule \(\Psi\) during the data gathering period \(\Upsilon\), such that the expected amount of gathered data \(\chi\) is maximized and the schedule \(\Psi\) is \(compatible\)._  
Firstly, the expected amount of gathered data by visiting the set of proxy nodes \(V^{*}\) is estimated as:  
\[\chi=\sum_{v_{i}\in V^{*}}\rho(v_{i})=\sum_{v_{i}\in V^{*}}\eta_{i}*A(r) \tag{9}\]where \(\rho(v_{i})\) is the expected amount of data stored at a proxy node, \(\eta_{i}\) is the number of distinct contacts of \(v_{i}\), \(A(r)\) denotes the amount of data a node might have in data gathering round \(r\). Secondly, when a scheduler is \(compatible\), the collector would visit each of the nodes one by one within the data gathering period \(\Upsilon=[b_{0},e_{K+1}]\subset E\), and would not conflict with each other. Formally, a schedule \(\Psi=\{(v_{1},[b_{1},e_{1}]),..,(v_{i},[b_{i},e_{i}]),..(v_{K},[b_{K},e_{K}])\}\) is said to be \(compatible\) if it follows the following condition:  
\[\forall\;(v_{i},[b_{i},e_{i}])\in\Psi,\;\;\;[b_{i},e_{i}]\subseteq SD(v_{i}), \;e_{i}-b_{i}\geq T_{slot},\;\;b_{0}\leq b_{i}<e_{i}<b_{i+1}\leq e_{K+1} \tag{10}\]  
where \((v_{i},[b_{i},e_{i}])\) denotes visiting \(v_{i}\) during the time range \([b_{i},e_{i}]\), \(SD(v_{i})\) denotes one of the key stationary duration of \(v_{i}\), and \(T_{slot}\) is minimal data gathering duration of a slot. Each slot is assigned to a proxy node for \(MC\)'s visiting, and they would not overlap with each other. Because the mobile collector could move fast, here we assume the time duration moving from one proxy node to the next is negligible compared with the period of data gathering round. So the collector \(MC\) is only constrained by the duration of data gathering, which is denoted by \(\Upsilon\). The PTSA problem is a variant of the famous \"Knapsack problem\" [20]: given a set of proxy nodes, each with an amount of data to be gathered, determine the set of proxy nodes to include in the data gathering period so that the total amount of data is as large as possible, under the constraints that the visiting of proxy nodes should be continuous and the _key stationary stays_ should not overlap each other in the time dimension. This problem is also defined as the _maximal coverage of line segments_, where the covering line is the data gathering duration. In Figure 5, the x-axis is the line of epoch, e.g., 8:00 to 20:00, the y-axis denotes id of the proxy nodes. The colored line segments are the key static durations (\(ksd\)) of different proxy nodes. The key stationary durations (\(ksd^{\prime}s\)) are projected on the time line of epochs (x-axis ), and they overlap with each other. ADG then calculates a period of data gathering round with length \(\Upsilon\), and assigns each of its slots to a proxy node, so that the total \(weight\) of the slots is maximized. Here the \(weight\) of a time slot is the expected amount of data that could be gathered by the \(MC\) during that slot. When a proxy node \(v\) is assigned to a time slot \(s\), \(MC\) is supposed to encounter \(v\) and gather its stored data, so the weight of \(s\) is the total amount of data stored at \(v\). From the figure, we could see that \(\Upsilon_{2}\) is preferred compared with \(\Upsilon_{1}\) because it covers more slots, and hence might get more amount of  
Figure 5: Mapping the Proxy node Time Slot Allocation (\(PTSA\)) problem into the problem of maximal coverage of line segment. data from the proxy nodes.