Energy Efficient Algorithm Research In Wireless Sensor Networks

Recently, wireless sensor networks (WSNs) have attracted a great deal of research attention due to their wide-range potential applications. Because a microsensor node must operate on a tiny battery with limited energy that recharge or replacement is not an option due to the complex environment it deployed, a paramount design consideration for WSNs is how to extend system lifetime without sacrificing system reliability. The information gathered in conventional WSNs is often of simple scalar format due to the severe resource limitations on a single sensor node. The data processing on the sensor node is assumed to be very simple, and the energy consumption in data processing is very little. Hence, the communication energy is the dominant factor in conventional WSNs and has attracted a lot of research attention. Energy efficient algorithms and protocols have been proposed at network levels to balance available energy and system reliability, and thus extend the lifetime of each node throughout the network. Compared to research on communication energy, little work has been reported on reducing the computational energy in conventional WSNs designs. However, within the context of multimedia sensor networks such as wireless video sensor networks, with the computationally intensive and energy-demanding video compression incorporated into the sensor node, its energy consumption behavior becomes very complex. The computational energy consumes a significant portion of the total energy supply on a wireless video sensor. This requires us to develop a framework to analyze the power consumption in both computation and wireless transmission. Therefore, there is a need to analyze the energy consumption behavior of individual sensor nodes and optimize their performance under energy constraints. Hence, in this dissertation, we emphasize particularly on the node level energy optimization and focus our attention to the issue of minimizing the power consumed during computation and communication. Since the sensor node is the basic operation unit of the WSNs system, its performance analysis is the first step, as well as the gateway, to the performance analysis and optimization of the whole sensor network. The analysis will also provide a solid foundation for protocol design and algorithm development at upper layers of the network system. Moreover, we also adopt the node sleep scheduling scheme that can reduce system overall energy consumption to yield significantly higher energy saving.In many WSNs applications, the data gathering has the Quality of Services (QoS) requirements in terms of real-time guarantees,reliability, etc. Therefore, to design the protocols with low energy consumption and flexible QoS provision is of great significance to the applications of WSNs. In this dissertation, we put forward a suite of techniques that perform aggressive computation and communication power optima-tion while guaranteeing the real-time constraints. When the node sleep scheduling scheme is adopted to save the energy consumed in idle state, we also propose mathematical model to preserve coverage qualities. Therefore, in this dissertation, we carry out a deep and systematic research work on the energy efficiency and QoS provision in WSNs.The main contributions of this dissertation include:1. Energy efficient algorithms for computationFirstly, we analyze the scheduling method of the mixed tasks in multi-task and multi-hop WSNs. Then, for the processors that dynamic power is the dominant component in the overall power consumption, we propose system level low power real-time scheduling algorithms to reduce energy consumption through dynamic voltage scaling (DVS). Our solution includes two components:â‘ A static algorithm to compute the task's speed, assuming worst case execution time for each arrival;â‘¡A dynamic speed reduction algorithm to pass the previous task's unused amount of slack time to the next task based on the actual workload.The development of deep-submicron CMOS technology results in an exponential increase in leakage power consumption. For some types of processors, the leakage power dissipation becomes comparable to dynamic power consumption. Most traditional low power technologies to reduce the dynamic energy consumption of sensor processor without considering the leakage power are less effective to reduce the overall energy consumption. In this dissertation, a procrastination algorithm that combines the dynamic voltage scaling(DVS) and dynamic power management(DPM) is proposed for periodic real-time tasks with specified relative deadlines to decrease the overall power dissipation. Without causing any deadline miss, processor speed for each task is selected by using DVS technology. Then, the speed will be modulated to balance the dynamic and leakage energy consumption by comparing with the critical speed which minimizes the dynamic and leakage energy consumption per unit work. The higher-than-necessary speeds can result in some idle intervals. We present a procrastination scheduling scheme to merge these scattered intervals into larger ones to switch CPU to low power state by using DPM technology.2. Energy efficient algorithms for communicationPower management of radios is extremely important since wireless communication is a major power consumer during system operation. Dynamic modulation Scaling is an effective way to reduce the transmission energy at the cost of an increase in the latency of communication. The character of energy function with modulation level for the long range communication is different from that of short range communication. We propose two low power scheuduling heuristic altorithms for these two scenarios respectively based on a multiple non-preemptive real-time traffic streams.â‘ When the transmission distance is long, the transmission energy is dominant in the total energy consumption. Thus, it is beneficial to make the modulation level as low as possible to minimize the transmission energy. We propose a nonpreemptive scheduling heuristic algorithm that combines DMS to find a feasible schedule and then to adjust the modulation level for low power.â‘¡In the scenario of short range transmission, the circuit energy consumption becomes comparable to or even dominates the transmission energy in the total energy consumption. Thus, in order to find the optimal transmission scheme, the overall energy consumption including both transmission and circuit energy consumption needs to be considered. To be overall energy efficient, the radio may have to transmit at a higher-than-necessary modulation level, since a low modulation level increases the active period of the radio, which in turn increases the circuit energy consumption to a degree that can offset or even surpass the transmission energy reduction. Adjusting the modulation level will cause a large number of idle intervals, and it is desirable to put the radio in a low power mode when idle by using DPM technology. Hence, we present a circuit energy conscious scheduling approach that combines both the DMS and DPM strategies to optimize the overall energy consumption of short range communication.3. Research on node sleep scheduling schemeThe low duty cycle and the redundant deployment of sensors provide us with much room to design energy efficient protocols to increase the system lifetime. A broadly-used strategy is to turn off redundant sensors by scheduling sensor nodes to work alternatively without jeopardizing sensory coverage that is a measure of the QoS of the sensing function. Based on the random deployment and the random sleep scheme, we put forward an accurate mathematical model for expected coverage ratio and point event detection quality. Different from most existing works, our approach does not require the knowledge about the locations of sensor nodes, thus can considerably save the hardware cost and the energy consumption on sensor nodes needed for deriving and maintaining location information. Furthermore, the model also takes the border effects into account and thus improves the accuracy of performance and quality analysis. Our model is flexible enough to capture the interaction among the essential system parameters. Therefore, this model could provide beneficial guidelines for optimal sleep scheduling schemes satisfying both the lifetime and reliability requirements.