Divisible Load Scheduling Algorithms For Wireless Sensor Networks

The Wireless Sensor Network (WSN) is a very valuable system applicable in modern monitoring and surveillance processes. The network consists of a large number of sensors equipped with onboard battery, sensing element, processor, radio receiver and transmitter. In particular, the battery is the sole energy resource to operate the sensor. Sensing tasks mainly include the collection of environmental data such as temperature, humidity, wind speed, pollution particles, and many others. When video cameras are used, the WSN can be used for security purposes. For example, at airport, railway and bus terminals, WSNs are deployed in order to ensure the safety of commuters. With the embedded radio, sensors receive control commands, workload assignments, and transmit measured data to a central processor at the base station.When the WSN is designed for a particular application, its architectural topology, mode of operation, and workload allocation have to be thoroughly considered. Since sensors in the WSN are usually deployed with larger numbers and in an ad-hoc manner at inaccessible locations, it is generally difficult to replace the battery. Because of this problem, when sensors are placed in the field, even a small number of energy exhausted sensors would make the network malfunctioned. Therefore, reduction in energy consumption is a prominent concern for the whole network to operate in a longer lifespan. Attempts to solve the problem in energy depletion include properly managing the radio transmission power and the cooperative division of sensing workload. The former approach can be realized by putting sensors in position dependent clusters to minimize the transmission power; the latter approach is also possible with the use of Divisible Load Theory (DLT) to ensure that the sensing task is completed in a shortest time. The energy needed for a sensing round is thus reduced and consequently the whole WSN can function in an extended period.The work reported in this thesis is focused on the studies of cooperative operation of the WSN with reduced energy consumption. A game theory based approach together with a penalty mechanism is first proposed for sensors to participate in operation. Then the divisible load theory is analysed, improved, tailored and applied to assign workloads for sensors to reduce their energy consumptions. The contributions of this thesis include the follows.1. Developed a Mechanism Penalty for task scheduling based on average sensor residual energy for increased system efficiency:The lifespan of wireless sensors are severely limited by the amount of energy stored onboard. After deployed in operation, sensors may choose to constrain their power consumptions while compromising the requirement to complete an allocated sensing task. Conventional network management algorithms for task scheduling may not provide sufficient incentives for sensors to sacrifice power consumption for task completion within a required time frame. A method is proposed in this thesis, integrating the advantages from game theory, mechanism design, strategy-proof, divisible load theory and the introduction of a penalty function. For sensors with above average residual energy, an exponential penalty function is imposed, while for other sensors a power-law based function is adopted. This method encourage sensors to participate in contribution to the sensing task and is able to provide the WSN with a longer operation lifetime and guaranteed completion of the allocated task in a shortest time frame.2. Proposed an Energy Dependent Divisible Load Theory (EDDLT) workload assignment scheme for extended network lifespan:Despite its advantages in deployment flexibility and fault tolerance, the WSN is vulnerable to failures due to the depletion of limited onboard battery energy. A major portion of energy consumption is caused by the transmission of sensed results to the master processor. The amount of energy used, in fact, is related to both the duration of sensing and data transmission. Hence, in order to extend the operation lifespan of the WSN, a proper allocation of sensing workload among the sensors is necessary. An assignment scheme is formulated, in this thesis, on the basis of the divisible load theory for sensing workload allocations. In particular, the amount of residual energies onboard sensors are considered while deciding the workload assigned to each sensor. Sensors with smaller amount of residual energy are assigned lighter workloads, thus, allowing for reduced energy consumption and extended network lifespan.3. Formulated an Adaptive-Indexed Divisible Load Theory (AIDLT) based workload assignment scheme:Energy depletion in wireless sensors is a major obstacle for a WSN to operate. This problem can be extenuated by minimizing the need for high power transmission from sensors. They could be arranged in clusters and their sensing workloads properly determined for minimal energy consumption during the sensing and result reporting stages. The divisible load theory is applied here to obtain optimal allocation of workloads taking into account the balance of energy used. Since standard DLT assumes an ordered indexing of the sensors, its direct application in WSNs may result in unbalanced energy usage. Adaptive indexing schemes with the application of DLT are thus proposed to re-define the indices of sensors while calculating the assigned workload portions in each sensing round. Furthermore, adaptations based on transmission distances, sensor residual energies, double ranking of distances with residual energies, and randomized sensor identifications are formulated and evaluated. The adaptive-indexing method is able to provide constructive guidelines in WSN design.4. Proposed an Active-Sleep Divisible Load Theory (ASDLT) workload assignment scheme:Due to the limited onboard energy resources, the operation of a WSN is severely hindered. In order to alleviate energy depletion, the DLT is adopted to derive a proper workload assignment scheme. However, special considerations have to be paid for its generic applicability in feasible workload assignment for WSNs. An examination of DLT based WSN operations including the effect of assignment, measurement and report times are undertaken, and the problem of negative workloads inherently generated in some schemes is revealed. By making use of the negativity phenomenon, an active-sleep scheme based on divisible load theory (ASDLT) is proposed for the WSN such that sensor energy consumptions can be reduced. Specifically, sensors with smaller amount of residual energies are put into the sleep mode. On the other hand, positive workloads are normalized and re-assigned to sensors with larger amount of onboard energies. By making use of the developed active-sleep workload assignment scheme, energy consumptions among sensors are balanced and the operation duration of the WSN is noticeably extended.