Cost-Effective Algorithms for Deployment and Sensing in Mobile Sensor Networks

In this dissertation, we propose cost-effective algorithms for deploying mobile sensors in traditional mobile sensor networks and scheduling mobile phone opportunistic sensing in mobile phone based sensor networks. Traditional sensor nodes must be deployed appropriately to successfully accomplish their sensing tasks. When the region of interest is unknown or hostile, manual deployment is infeasible. For such scenarios, how to employ sensor mobility to achieve cost-effective self-deployment is an interesting yet underexplored problem. While mobile phones are naturally sensor nodes, they differ from traditional sensor nodes in that they move along with their owners and only perform sensing tasks in an opportunistic manner. Therefore, an interesting question is how to cost effectively schedule sensing tasks on a group of mobile phones, taking account of the movements of these mobile phones. In the absence of a prior knowledge of the region, deploying sensors evenly in the region, referred to as even self-deployment, is one of the best known strategies. In the first part of the dissertation, we propose distributed algorithms for energy-efficient even self-deployment in mobile sensor networks. Specifically, we first formulate a locational optimization problem that achieves even deployment while takes account of energy consumption due to sensor movement, and then propose two iterative algorithms. In the second part of the dissertation, we study self-deploying sensors to monitor a set of targets when the target locations are known beforehand (through surveillance). Our goal is to determine which target a sensor moves to so that the duration for which a target can be monitored is balanced among the targets. We start with the simplest scenario where all sensors have the same initial location and energy, and propose an optimal algorithm to solve it. For the general scenario, the problem is NP-hard. While it is a special case of Max-min fair allocation problem, existing solutions are computational intensive, and hence are unsuitable for resource-constrained sensors. We propose a greedy heuristic scheme and demonstrate that it achieves similar performance as the best known algorithm for Max-min fair allocation while requires much less running time. In the third part of the dissertation, we study how to cost effectively schedule mobile phones to monitor a set of targets and upload the collected data. The goal of the problem is to obtain a cost-effective schedule of phone activities. We start with the offline problem, assuming the trajectories of the phones are known beforehand. We propose to overcome the limited cellular data plans of the phones by resorting to opportunistic communication among mobile phones. We then formulate and solve a minimum cost flow problem and a fair cost problem. After that, we investigate the online version of the problems under realistic assumptions where only the past trajectories of the phones are known. We develop two heuristic algorithms: one aims to minimize cost while the other aims to achieve cost fairness. Extensive simulation results show that the proposed algorithms perform well in terms of both minimizing total cost and achieving cost fairness