Research On Divisible Load Scheduling In Wireless Sensor Networks

Performance is a key point for applications, and it always resorts to scheduling. With the development of wireless sensor networks and increasing of these application demands, scheduling holds new connotation and challenge. It remains as the hotspot of the research of wireless sensor networks.Owing to the wireless sensor network node with limited energy, sensing tasks should be allocated and processed among sensor nodes in minimum times so that users can draw useful conclusions through analyzing sensed data. Furthermore, finishing sensing task faster will benefit energy saving, which is critical in system design of wireless sensor networks. Divisible load theory provides an effective solution to wireless sensor networks for task scheduling. Different from other heuristic solutions of task scheduling problem, such as directed acyclic graph and independent task sets in wireless sensor networks, this scheme can get not only the optimal solution, but also the analytic solution, thus ensuring the consistency of the results of scheduling. In this thesis, we discuss the technique of task scheduling algorithms based on divisible load theory in wireless sensor networks. The main contributions of this thesis are listed as follows:1. The task scheduling problem under clustering structure in heterogeneous wireless sensor networks is studied. The existing studies of task scheduling model based on divisible load theory in wireless sensor networks are under the single tree topology, or homogeneous clustering topology. These assumptions on the network are not suitable for wireless sensor network research and development. We analysis the task scheduling problem of heterogeneous wireless sensor networks under three conditions (single channel, multi-channel and sensor with coprocessor). The most reasonable scheme for task allocation in all nodes, and the shortest time required to complete the tasks are obtained. The limit case of task scheduling in wireless sensor networks is theoretically analyzed. And we gave the linear programming model of task scheduling to analyze the optimal solution for the case of cluster head having limited resource.2. The multi-round task scheduling problem in wireless sensor networks is studied. Divisible load scheduling algorithm can be divided into single-round scheduling algorithms and multi-round scheduling algorithms. Single-round scheduling algorithm is relatively simple, but its computation and communication overlap are rather poor, and the extra overhead is relatively large. Multi-round scheduling algorithm has the characteristics of better computation and communication overlap, thus properly reducing the scheduling overhead. However, it is more difficult to analyze, so fewer results of multi-round scheduling algorithm are available and the existing multi-rounds scheduling algorithms are designed based on grid computing environments. We proposed a multi-round task scheduling algorithm in wireless sensor networks based on divisible load theory. In this algorithm, according to divisible load theory, the tasks are distributed to every cluster head by multi-round based on the processing capacity of each cluster by SINK. To remove performance degradation caused by communications interference, SINK sends each round's tasks to cluster head sequentially. After each cluster finishing its tasks and fusing the data, the cluster heads also send this round's results to SINK sequentially. It could overlap the task-performing and communication phase much better, which can reduce task completion time and improve network resource utilization.3. The game algorithm of task scheduling based on divisible load theory in wireless sensor networks is studied. In large-scale wireless sensor networks, the sensors component of the system can belong to different companies, research institutions and even a personal sensor network. Thus each node would like to maximize their interests. That is, each sensor is rational and selfish. Because the energy constraints of sensors, they may refuse to collaborate to complete the task. For such potential selfish behavior, a non-cooperative game algorithm for task scheduling in wireless sensor networks is proposed. A mechanism which prevents the selfish nodes'deviation form cooperation is provided and a utility function related with the total task completion time and tasks allocating scheme is designed. The Nash equilibrium of the game algorithm is proved.4. A task scheduling algorithm based on divisible load theory in multi-Sinks wireless sensor networks is proposed. Multi-Sinks wireless sensor network, a current research focus, has better stability and effectiveness compared to the traditional structure. The tasks are distributed to wireless sensor network based on the processing and communication capacity of each sensor by Sinks. After received the sub-tasks, the intra-cluster sensors carry out its tasks simultaneously, and send its results to cluster head sequentially. By removing communication interference between each sensor, reduced task completion time and improved network resource utilization are achieved. Cluster heads send fused data to Sinks sequentially after fused the data got from intra-cluster nodes, which could overlap the task-performing and communication phase much better.5. We proposed a continuous time Markov Chain Model which is equivalent to the results of divisible load scheduling algorithm, and analyzed the Markov chain model with task scheduling problem, in which the state space is composed of the ratio of tasks allocated on each sensor. The consistency of divisible load scheduling and Markov chain model is indicated. We can get the same scheduling results through the set of local balance equations in above Markov chain model. The new model will be simple and compact, and it is easier to analyze large-scale wireless sensor networks.