Modeling and optimization of energy efficient routing in wireless sensor networks

Wireless sensor networks (WSNs) have important applications in remote environmental monitoring and target tracking. The development of WSNs in recent years has been facilitated by the availability of sensors that are smaller, less expensive, and more intelligent. The design of a WSN depends significantly on its desired applications and must take into account factors such as the environment, the design objectives of the application, the associated costs, the necessary hardware, and any applicable system constraints. In this study, we propose mathematical models for a routing protocol (network design) under particular resource restrictions within a wireless sensor network. We consider two types of constraints: the distance between the linking sensors and the energy used by the sensors. The proposed models aim to identify energy-efficient paths that minimize the energy consumption of the network from the source sensor to the base station. The computational results show that the presented models can be used efficiently and applied to other network design contexts with resource restrictions (e.g., to multi-level supply chain networks).     

Minimizing energy consumption and makespan in a two-machine flowshop scheduling problem

Energy consumption has become a key concern for manufacturing sector because of negative environmental impact of operations. We develop constructive heuristics and multi-objective genetic algorithms (MOGA) for a two-machine sequence-dependent permutation flowshop problem to address the trade-off between energy consumption as a measure of sustainability and makespan as a measure of service level. We leverage the variable speed of operations to develop energy-efficient schedules that minimize total energy consumption and makespan. As minimization of energy consumption and minimization of makespan are conflicting objectives, the solutions to this problem constitute a Pareto frontier. We compare the performance of constructive heuristics and MOGAs with CPLEX and random search in a wide range of problem instances. The results show that MOGAs hybridized with constructive heuristics outperform regular MOGA and heuristics alone in terms of quality and cardinality of Pareto frontier. We provide production planners with new and scalable solution techniques that will enable them to make informed decisions considering energy consumption together with service objectives in shop floor scheduling.     

Optimizing sensor cover energy via DC programming

Wireless sensor coverage problem has been extensively studied in the last years, with growing attention to energy efficient configurations. In the paper we consider the problem of determining the radius of a given number of sensors, covering a set of targets, with the objective of minimizing the total coverage energy consumption. The problem has a non linear objective function and non convex constraints. To solve it we adopt a penalty function approach which allows us to state the problem in difference of convex functions form. Some numerical results are presented on a set of randomly generated test problems.     

iGreen: green scheduling for peak demand minimization

Home owners are typically charged differently when they consume power at different periods within a day. Specifically, they are charged more during peak periods. Thus, in this paper, we explore how scheduling algorithms can be designed to minimize the peak energy consumption of a group of homes served by the same substation. We assume that a set of demand/response switches are deployed at a group of homes to control the activities of different appliances such as air conditioners or electric water heaters in these homes. Given a set of appliances, each appliance is associated with its instantaneous power consumption and duration, our objective is to decide when to activate different appliances in order to reduce the peak power consumption. This scheduling problem is shown to be NP-Hard. To tackle this problem, we propose a set of appliance scheduling algorithms under both offline and online settings. For the offline setting, we propose a constant ratio approximation algorithm (with approximation ratio \(\frac{1+\sqrt{5}}{2}+1\)). For the online setting, we adopt a greedy algorithm whose competitive ratio is also bounded. We conduct extensive simulations using real-life appliance energy consumption data trace to evaluate the performance of our algorithms. Extensive evaluations show that our schedulers significantly reduce the peak demand when compared with several existing heuristics.     

Optimal wireless sensors' location for monitoring of structures in randomly disturbed environment

In the paper we present the specific conditions that appear in structures' monitoring by means of Wireless Sensor Networks (WSN). First, we introduce the problem of optimal sensors' location for structures monitoring and its specific constraints if one uses WSN. We formulate the conditions that must be taken into account during optimization. Then, we give an example of temperature measurements and formulate the procedure that leads to finding optimal wireless sensors locations. Finally, we present the experimental observations of wireless sensors in the network that strongly affect on the temperature estimation on a basis of the collected measurements. We conclude with remarks concerning WSN practical design for permanent structures' monitoring to obtain exact and reliable results. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Robust energy planning in buildings with energy and comfort costs

Energy management in buildings is addressed in this paper. The energetic impact of buildings in the current energetic context is first depicted. Then the studied optimization problem is defined as the optimal management of production and consumption activities in houses. A scheduling problem is identified to adjust the energy consumption to both the energy cost and the inhabitant’s comfort. The available flexibilities of the services provided by domestic appliances are used to compute optimal energy plans. These flexibilities are associated to time windows or heating storage abilities. A constraints formulation of the energy allocation problem is given. A derived mixed linear program is used to solve this problem. The energy consumption in houses is very dependent to uncertain data such as weather forecasts and inhabitants’ activities. Parametric uncertainties are introduced in the home energy management problem in order to provide robust energy allocation. Robust linear programming is implemented. Event related uncertainties are also addressed through stochastic programming in order to take into account the inhabitant’s activities. A scenario based approach is implemented to face this robust optimization problem.     

Self-stabilizing algorithm for efficient topology control in Wireless Sensor Networks

Wireless Sensor Networks lifetime mainly depends on energy saving efficiency. In this paper, we propose an energy-efficient self-stabilizing topology control protocol for WSN. We reduce the transmission power of each node so as to maintain network connectivity while saving maximum energy. Besides, we propose an approximation algorithm for minimum weighted connected dominating set that builds a virtual backbone formed by sensors with maximum energy. This backbone is used for efficient routing purpose. We proved the algorithm correctness and through our simulation results, we showed the efficiency of our proposed solution.     

Flow shop scheduling with peak power consumption constraints

We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with instances arising from the manufacturing of cast iron plates.     

Optimal relay node placement in delay constrained wireless sensor network design

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre-specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the node-cut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch-and-cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch-and-cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.     

Optimising for energy or robustness? Trade-offs for VM consolidation in virtualized datacenters under uncertainty

Reducing the energy consumption of virtualized datacenters and the Cloud is very important in order to lower CO\( _2 \) footprint and operational cost of a Cloud operator. However, there is a trade-off between energy consumption and perceived application performance. In order to save energy, Cloud operators want to consolidate as many Virtual Machines (VM) on the fewest possible physical servers, possibly involving overbooking of resources. However, that may involve SLA violations when many VMs run on peak load. Such consolidation is typically done using VM migration techniques, which stress the network. As a consequence, it is important to find the right balance between the energy consumption and the number of migrations to perform. Unfortunately, the resources that a VM requires are not precisely known in advance, which makes it very difficult to optimise the VM migration schedule. In this paper, we therefore propose a novel approach based on the theory of robust optimisation. We model the VM consolidation problem as a robust Mixed Integer Linear Program and allow to specify bounds for e.g. resource requirements of the VMs. We show that, by using our model, Cloud operators can effectively trade-off uncertainty of resource requirements with total energy consumption. Also, our model allows us to quantify the price of the robustness in terms of energy saving against resource requirement violations.     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

中国城市化发展、能源消费与碳排放的实证研究

选取了1995年至2007年我国29个省市面板数据,建立以城市化水平为被解释变量,能源消费和碳排放作为解释变量的模型,通过协方差分析检验和Haus man检验的分析结果,确定研究模型的形式为固定影响变截距模型,最后,通过对拟合模型的结果分析,实证结果表明:高能耗、高排放、粗放式经济发展方式不利于城市化水平的提高;同时,各省市的城市化发展水平也存在差异.因此,各省市应在城市化工业化进程中推进产业结构和能源消费结构调整使其朝着更有利于节能环保的方向演进,节能减排政策的调整重点应该放在能源强度和能源消费碳强度上.     

Energy-aware workload management models for operation cost reduction in data centers

In the last century, the costs of powering datacenters have increased so quickly, that datacenter power bills now dwarf the IT hardware bills. Many large infrastructure programs have been developed in the past few years to reduce the energy consumption of datacenters, especially with respect to cooling requirements. Although these methods are effective in lowering the operation costs they do require large upfront investments. It is therefore not surprising that some datacenters have been unable to utilize the above means and as a result are still struggling with high energy bills. In this work we present a cheap addition to or an alternative to such investments as we propose the use of intelligent, energy efficient, system allocation mechanisms in place of current packaged system schedulers available in modern hardware infrastructure cutting server power costs by 40%. We pursue both the quest for (1) understanding the energy costs generated in operation as well has how to utilize this information to (2) allocate computing tasks efficiently in a cost minimizing optimization approach. We were able to underline the energy savings potential of our models compared to current state-of-the-art schedulers. However, since this allocation problem is complex (NP-hard) we investigated various model approximations in a trade-off between computational complexity and allocative efficiency. As a part of this investigation, we evaluate how changes in system configurations impact the goodness of our results in a full factorial parametric evaluation.     

Iterative approaches for a dynamic memory allocation problem in embedded systems

Memory allocation has a significant impact on energy consumption in embedded systems. In this paper, we are interested in dynamic memory allocation for embedded systems with a special emphasis on time performance. We propose two mid-term iterative approaches which are compared with existing long-term and short-term approaches, and with an ILP formulation as well. These approaches rely on solving a static version of the allocation problem and they take advantage of previous works for addressing the static problem. A statistic analysis is carried out for showing that the mid-term approach is the best one in terms of solution quality.     

QoS and energy consumption aware service composition and optimal-selection based on Pareto group leader algorithm in cloud manufacturing system

Service composition and optimal selection (SCOS) is one of the key issues for implementing a cloud manufacturing system. Exiting works on SCOS are primarily based on quality of service (QoS) to provide high-quality service for user. Few works have been delivered on providing both high-quality and low-energy consumption service. Therefore, this article studies the problem of SCOS based on QoS and energy consumption (QoS-EnCon). First, the model of multi-objective service composition was established; the evaluation of QoS and energy consumption (EnCon) were investigated, as well as a dimensionless QoS objective function. In order to solve the multi-objective SCOS problem effectively, then a novel globe optimization algorithm, named group leader algorithm (GLA), was introduced. In GLA, the influence of the leaders in social groups is used as an inspiration for the evolutionary technology which is design into group architecture. Then, the mapping from the solution (i.e., a composed service execute path) of SCOS problem to a GLA solution is investigated, and a new multi-objective optimization algorithm (i.e., GLA-Pareto) based on the combination of the idea of Pareto solution and GLA is proposed for addressing the SCOS problem. The key operators for implementing the Pareto-GA are designed. The results of the case study illustrated that compared with enumeration method, genetic algorithm (GA), and particle swarm optimization, the proposed GLA-Pareto has better performance for addressing the SCOS problem in cloud manufacturing system.     

Energy-aware software: Challenges,opportunities and strategies

Energy consumption of computing systems has become a major concern. Constrained by cost, environmental concerns and policy, minimising the energy foot-print of computing systems is one of the primary goals of many initiatives.As we move towards exascale computing, energy constraints become very real and are a major driver in design decisions. The issue is also apparent at the scale of desk top machines, where many core and accelerator chips are common and offer a spectrum of opportunities for balancing energy and performance.Conventionally, approaches for reducing energy consumption have been either at the operational level (such as powering down all or part of systems) or at the hardware design level (such as utilising specialised low-energy components). In this paper, we are interested in a different approach; energy-aware software. By measuring the energy consumption of a computer application and understanding where the energy usage lies, may allow a change of the software to provide opportunities for energy savings.In order to understand the complexities of this approach, we specifically look at multithreaded algorithms and applications. By an evaluation of a benchmark suite on multiple architectures and multiple environments, we show how basic parameters, such as threading options, compilers and frequencies, can impact energy consumption. As such, we provide an overview of the challenges that face software developers in this regard. We then offer a view of the directions that need to be taken and possible strategies needed for building energy-aware software.     

Design and statistical analysis of a new chaotic block cipher for Wireless Sensor Networks

Security issue is a vital and active topic in the research of Wireless Sensor Networks (WSN). After surveying the existing encryption algorithms for WSN briefly, we propose a new chaotic block cipher for WSN and then compare the performance of this cipher with those of RC5 and RC6 block ciphers. Simulation result demonstrates that better performance in WSN encryption algorithms can be achieved using the new cipher.     

Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion

We are given a set of parallel jobs that have to be executed on a set of speed-scalable processors varying their speeds dynamically. Running a job at a slower speed is more energy-efficient, however, it takes a longer time and affects the performance. Every job is characterized by the processing volume and the number or the set of the required processors. Our objective is to minimize the maximum completion time so that the energy consumption is not greater than a given energy budget. For various particular cases, we propose polynomial-time approximation algorithms, consisting of two stages. At the first stage, we give an auxiliary convex program. By solving this problem, we get processing times of jobs and a lower bound on the makespan. Then, at the second stage, we transform our problem into the corresponding scheduling problem with the constant speed of processors and construct a feasible schedule. We also obtain an “almost exact” solution for the preemptive settings based on a configuration linear program.

     

带有风能的智能电网多周期买电策略研究

本文研究带有风能随机供给的智能电网中传统能源的多周期买电问题,假设存在一个能源运营商集中负责智能电网传统能源的购买和消费。通过构建并求解动态规划模型,找到能源运营商在风能供给不确定性下的传统能源最优多周期买电策略。在最优买电策略下,能源运营商只有在当期电价足够小时才购买传统能源,其买电量与风能分布、价格信息和时间信息有关。在实际数据的基础之上,提供详实的数值实验对比研究了本文的最优买电策略和其他两种策略(实践中只考虑风能估计的策略和放弃利用风能的策略)在最小化总成本方面的效果,并验证了本文的最优买电策略在真实风能数据中的鲁棒性。     

Modelling and computing the peaks of carbon emission with balanced growth

In this paper, we assume that under the balanced and optimal economic growth path, the economic growth rate is equal to the consumption growth rate, from which we can obtain the ordinary differential equation governing the consumption level by solving an optimal control problem. Then, a novel numerical method, namely a so-called discontinuous Galerkin method, is applied to solve the ordinary differential equation. The error estimation and the superconvergence estimation of this method are also performed. The model’s mechanism, which makes our assumption coherent, is that once the energy intensity is given, the economic growth is determined, followed by the GDP, the energy demand and the emissions. By applying this model to China, we obtain the conclusion that under the balanced and optimal economic growth path the CO₂ emission will reach its peak in 2030 in China, which is consistent with the U.S.-China Joint Announcement on Climate Change and with other previous scientific results.