Research On Algorithms For Scheduling In Battery-free Wireless Sensor Networks

The emergence of wireless sensor networks makes it possible to observe the complicated physical world through tiny sensor nodes.Therefore,wireless sensor networks are widely employed in variety of applications to bring convenience and interest for human life,such as military surveillance,environmental monitoring,traffic monitoring,and structural health monitoring,and so on.One of the most fundamental problems in wireless sensor networks is the scheduling problem,including transmission scheduling and computation scheduling.The scheduling problem focuses on the assignments of channel resources and computation resources of wireless sensor networks,which directly influences the performance of wireless sensor networks.Traditional wireless sensor networks are composed of sensor nodes equipped with batteries,which are known as batterypowered sensor nodes.Therefore,traditional wireless sensor networks are also known as battery-powered wireless sensor networks.However,one of the biggest limitations of traditional battery-powered wireless sensor networks is their finite lifetimes.It is difficult or even infeasible to replace batteries in many applications where sensor nodes may not be accessible by human beings.Besides,the leakage of batteries may lead to environmental pollution problems.The emerging battery-free sensor nodes break through the lifetime limitation of battery-powered sensor nodes.Battery-free sensor nodes do not need batteries but survive through harvesting energy from energy sources in their ambient environments,such as solar power,wind power and radio frequency signal,etc.Besides,battery-free sensor nodes are equipped with capacitors that can be unlimitedly recharged for energy storage.The networks composed of battery-free sensor nodes are known as battery-free wireless sensor networks.Since the energy sources in ambient environments are unstable and uncontrollable,the energy supply in battery-free wireless sensor networks are unstable and uncontrollable.These energy characteristics bring more challenges to the scheduling problem in battery-free wireless sensor networks.The existing methods proposed for the scheduling problem in battery-powered wireless sensor networks are no longer feasible for the scheduling problem in battery-free wireless sensor networks.Therefore,this thesis focuses on the scheduling algorithms for battery-free wireless sensor networks.The main contributions are as follows.First,this thesis investigates the broadcast scheduling problem in battery-free wireless sensor networks.Broadcast is an essential operation in wireless sensor networks,which is to disseminate the source data from a source sensor node to all other sensor nodes in a wireless sensor network.Since timeliness is one of the most crucial metrics for the performance of wireless sensor networks,the minimum-latency broadcast scheduling problem has been attracted a wide attention.In battery-free wireless sensor networks,battery-free sensor nodes harvest energy from unstable and uncontrollable energy sources in their ambient environments,where their energy harvesting rates are usually less than their energy consumption rates.As a consequence,battery-free sensor nodes are often out of service due to energy shortage.This thesis studies the minimum-latency broadcast scheduling algorithms for battery-free wireless sensor networks,which are interferencefree and feasible.The NP-hardness of the minimum-latency broadcast scheduling problem in battery-free wireless sensor networks is proved.Some energy prediction methods are applied to estimate the energy status of battery-free sensor nodes.According to the estimated energy status of battery-free sensor nodes,three approximate minimum-latency broadcast scheduling algorithms for different energy harvesting scenarios are proposed.The correctness and approximation ratio of these algorithms are proved theoretically,and the computation complexity of these algorithms are analyzed.Besides,extensive simulations are conducted to verify the performances of the proposed algorithms on reducing broadcast latency.Second,this thesis investigates the data collection scheduling problem in batteryfree wireless sensor networks.One of the most important functions of wireless sensor networks is to gather the sensory data generated by sensor nodes distributed in the monitored environment for further computation and processing.Data gathering can be divided into two categories,i.e.,data aggregation and data collection.This thesis first investigates the scheduling problem in data collection.In data collection,no in-network computations are conducted in data transmission,and the sink node directly gathers the raw sensory data generated by all sensor nodes in the network.Data collection is appropriate for the scenario where each sensory data is equally important or the temporal and spatial correlations among sensory data are relatively low.According to the energy characteristics of battery-free wireless sensor networks,this thesis studies the latencyefficient data collection scheduling algorithms for battery-free wireless sensor networks,which are interference-free and feasible.The monitored environment is first divided into sub-areas according to the interference model.Some energy prediction methods are applied to estimate the energy status of battery-free sensor nodes.Then,the beacon packets with energy status and scheduling strategy are transmitted between neighbor nodes.Finally,the latency-efficient data collection scheduling is generated distributedly.The line battery-free wireless sensor networks and general battery-free wireless sensor networks are considered in this thesis,and two data collection scheduling algorithms are proposed.The latency upper bound of the data collection schedules generated by the algorithms are proved,and the computation complexity of the algorithms are analyzed.Extensive simulations are carried out to verify that the proposed algorithms can significantly reduce the latency of data collection in battery-free wireless sensor networks.Third,this thesis investigates the data aggregation scheduling problem in batteryfree wireless sensor networks.Data aggregation is a category of data gathering with in-network computation.In data aggregation,sensory data gathered by a relay node can be merged by in-network computation and then transmitted towards the sink node,such as taking the maximum,average,or sum,etc.,of them.Data aggregation is appropriate for the scenario where the temporal and spatial correlations among sensory data are relatively high or the sink node only requires the aggregated result of all sensory data in the network.This thesis first proves that the minimum-latency data aggregation scheduling problem in battery-free wireless sensor networks is NP hard.According to the energy characteristics of battery-free wireless sensor networks,this thesis studies the latency efficient data aggregation scheduling algorithm for battery-free wireless sensor networks,which are interference-free and feasible.Some energy prediction methods are applied to estimate the energy harvesting rates of battery-free sensor nodes.Based on the estimated energy harvesting rates,an energy harvesting rate-workload balanced data aggregation tree is constructed.Then,transmission times are assigned for battery-free sensor nodes in the data aggregation tree according to the interference model.This thesis proposes a data aggregation scheduling algorithm with latency bound.The computation complexity of the proposed algorithm is analyzed,and the correctness of the proposed algorithm and the latency upper bound of data aggregation schedules produced by the proposed algorithm are proved.Finally,extensive simulations are conducted,which verify that the proposed algorithm can significantly reduce the latency of data aggregation.Finally,this thesis investigates the computation scheduling problem in mobile edge computing enabled battery-free wireless sensor networks.In mobile edge computing enabled battery-free wireless sensor networks,although sensor nodes have limited computing capacity,they can offload their intensive computation workloads to edge devices located at the edge of networks through wireless communication,such as base stations and access points.Meanwhile,edge devices provide energy for sensor nodes,where sensor nodes harvest energy through receiving the radio frequency signals transmitted by the edge devices.Since the quantity of computation completed in networks is one of the most crucial metrics for the performance of mobile edge computing enabled wireless sensor networks,the problem of computation scheduling with maximum computation completion ratio has been attracted a wide attention.The computation completion ratio is defined as the ratio of the processed computation data to the required computation data of all sensor nodes in the network.Due to the half-duplex transmission of sensor nodes,the transmission of radio frequency signals and the offloading of computation data in a network cannot be performed simultaneously.Then,assigning channel resources in the network to improve the network performance is the first problem to be considered.When multiple edge devices are deployed in a mobile edge computing enabled battery-free wireless sensor network,the offloading operations from a single sensor node to different edge devices have different energy and time consumption.Then,assigning computation resources in the network to improve the network performance is the other problem to be considered.This thesis studies the computation scheduling algorithms to maximize the computation completion ratio of mobile edge computing enabled battery-free wireless sensor networks.The computation completion ratio maximization scheduling problem for mobile edge computing enabled battery-free wireless sensor networks is proved to be NP hard.To generate proper channel resources assignment,a candidate set of energy harvesting time assignments is constructed.For each candidate energy harvesting time assignment,the optimal solution is deconstructed,where a part of the optimal solution is computed and the other part of the optimal solution is converted to the solution of a general assignment problem.Therefore,the approximate computation completion ratio maximization scheduling algorithm is proposed.The approximation ratio of the proposed algorithm is proved theoretically,and the computation complexity of the proposed algorithm is analyzed.Besides,extensive simulations are conducted,which verify that the proposed algorithm can significantly improve the computation completion ratio of mobile edge computing enabled battery-free wireless sensor networks.