Research On TDMA Scheduling Algorithm In Wireless Sensor Network

Since the limited energy of sensor nodes, energy saving has been the focus of researcheson WSN (Wireless Sensor networks). Considering the composition of energy wasting, theenergy consumed by MAC layer is an important part. Current scheduling algorithms mayhave different advantages and disadvantages because of the variety of optimization objectives.However, the scheduling algorithms which are used for clustering networks are fewer, and thenetwork would be valuable only it can provide users with necessary service qualities.Therefore, this paper would do researches on MAC-based scheduling algorithms, and threeTDMA-based scheduling algorithms are proposed to avoid conflicting, as well as improvenetwork performances.The two graph coloring theory based TDMA scheduling algorithms are proposed first.Before introduction of them, the current centralized algorithm called NBS (Node-basedscheduling algorithm) and distributed algorithm noted as DFS(Depth First Search basedscheduling algorithm) are analyzed. NBS has been used for tree-based network withoutconsidering the energy consumed for scheduling or the impact of network structure and DFSalgorithm has also been used for tree-based network without considering the impact ofnetwork structure, which lead to the increase of average communication energy and datacollection time used. Then, to avoid the communication conflict among nodes, decrease datacollection time and communication energy at the same time, the GCTS (Graph Coloringbased TDMA Scheduling algorithm) and MDFS (Modified Depth First Search basedscheduling algorithm) are proposed for clustering networks. In GCTS and MDFS, there aretwo phases: coloring phase and scheduling phase, they use different graph coloring algorithmsin coloring phase, but the same strategy in scheduling phase. A network conflict model wouldbe built firstly, and then graph coloring algorithms will work based on this model duringcoloring phase. In the first algorithm GCTS, a novel graph coloring algorithm DVCA(Distributed Vertex Coloring Algorithm) is presented, which can decrease the schedulingenergy and obtain a sub optimal partition of independent sets to decrease the average delay.The proofs of correctness and performances of DVCA are given in the paper. In thescheduling phase, cluster-heads calculate the priorities of intra-cluster independent sets basedon the network structure with local conflict information, and make adjustments for them, inorder to decrease data collection time. However, Sink would pre-allocate timeslots forcluster-heads in a centralized form, and the entire communication process can be representedwith several timeslots. In the second algorithm MDFS, which is proposed later, a moreenergy-saving graph coloring algorithm DFS, which is based on the depth first search process, is used to further reduce the energy consumed for scheduling. While, MDFS uses the samestrategy as GCTS in scheduling phase. MDFS can get similar data collection time andcommunication energy consumed to GCTS because of the adjustments of intra-clusterindependent sets.The experiments analyze the performance of GCTS and MDFS, such as energyconsumed for scheduling, communication energy consumed and data collection time. It canbe indicated that GCTS and MDFS can meet the above objectives with acceptable energyconsumed for scheduling, and the data collection time and communication energy they usedare far superior to the NBS and DFS. MDFS uses less energy for scheduling, when thenetwork is dense, the data collection time and communication energy GCTS used are slightlyless than MDFS. The performances of DVCA, which is proposed in coloring phase of GCTS,are also given in the experiments, such as the rounds it runs, the number of colors used, thecomplexity of broadcast messages, etc. The experiments show that DVCA has goodscalability and can increase the parallelism of coloring.Given that it is more accurate to model a real network using the physical interferencemodel, the research on algorithms which are based on the physical interference model ismeaningful. So, a modified link scheduling algorithm MLSA is proposed in this paper, whichis based on this model and is an improved algorithm of LS-NLPA(Link Scheduling withNon-Linear Power Assignment). Since LS-NLPA doesn’t consider the impact of the farthestnode when it allocates timeslots for nodes, it gets lager average packet delay. The improvedlink scheduling algorithm MLSA would first schedule the link set which includes the farthestnode every time, in order to decrease the average packet delay and communication energyconsumed. The proofs are given, and the impact of parameters in this model on theperformance of algorithms is analyzed in the paper. Experiments are set to validate theaccuracy of the analysis about MLSA and related parameters.