Optimal Data Collection for A Mobile Sink

The proliferation of Internet of Things (IoTs) has driven a large number of widely deployed networks. To collect information from those networks, methods using mobile data collection with one or more sink nodes moving in the area are proposed. The objective for mobile sink is to collect all necessary data while following a path with certain object function, e.g., shortest length. We propose an efficient algorithm to obtain shortest routine path for the mobile data collection. We first solve a special case under the assumption that the sink node has to go to the exact location of a wireless node in order to collect data packets. We further present an efficient accessibility-based algorithm with approximation ratio $O\left(\log^{2}n\log t\log\log n\right)$ where n is the number of wireless nodes deployed and $t(t\leq n)$ is the cardinality of the largest network. Here, the accessibility from node v i to node v j is defined as the probability for node v j to successfully send data packets to node v i through one- or multi-hops. In other words, the accessibility indicates whether or to what extent a mobile sink could obtain data packets of one sensory node from another sensory node. For the general case, i.e., the sink node and other nodes are able to finish data exchanging as long as they are within the transmission range of each other. We present an algorithm with approximation ratio $O\left(\log^{2}n\log t\log\log n\right)$ when $\displaystyle \epsilon=O\left(\frac{\|P_{\text{opt}}\|}{n}\right)$ where $\|P_{\text{opt}}\|$ is the optimal path length and $\epsilon$ is a constant determining the algorithm running time.