برنامه ریزی صرفه جویی در انرژی برای دسترسی چند گانه در شبکه های حسگر بی سیم: یک روش برنامه ریزی شغلی

With the objective to minimize the transmission energy cost, we consider the energy-efficient scheduling problem in a single hop multi-access data gathering network. We first prove by theoretical induction that transmitting with reduced powers decreases the energy budget in a multi-access transmission. Given the optimal transmit powers, we then examine the multi-access capacity polymatroid and argue that the optimal rate control can be achieved by controlling the successive decoding order of the transmitting sensor nodes. Consequently, the multi-access scheduling problem is reformulated into the job scheduling problems and solved by adapting job scheduling policies. We also address the implementation issues and demonstrate via simulations that the proposed strategies are efficient in energy conservation.

Energy efficiency in computation, signal processing and information transmission is a topic of increasing interest with the extensive implementation of wireless sensor networks (WSNs). The main objective of current sensor network research concentrates on the design of energy-efficient devices and algorithms to support all aspects of network operations. As “transmitting 1 bit consumes 1500–2700 times as much energy as executing one instruction” [1], the energy-efficient transmission scheduling becomes a particular important issue. Therefore, in this paper we investigate the energy-efficient scheduling problem in a multi-access sensor network. Energy-efficient scheduling was extensively studied under various circumstances, including [1] for single transmitter–receiver pair, [2] in multi-hop transmission, [3] in broadcasting channel, and [4] by a cross-layer approach. The proposed strategies are generally based on the previous result that in point to point (p2p) transmission the energy required to transmit a bit is a strictly convex and monotonously decreasing function of the transmission duration. In other words, the transmission energy can be conserved by reducing the transmit power and transmitting for a long time. By adaptively adjusting the transmission rate, the above mentioned strategies achieve optimal energy scheduling under deadline constraint, average delay constraint or throughput requirement. Due to the application scenarios of WSNs, delay and throughput constraints are not much concerned. Transmit power constraints, however, are more rigorous due to the limited capability of the amplifiers equipped with the sensor nodes. Hence, we particularly study the energy-efficient multi-access scheduling with transmit power constraints. In practical applications, WSNs are usually deployed as a multi-access transmission model. With the cluster head or the fusion center as the sink node, a collection of sensor nodes transmit data to the sink node. Earlier work concerning the energy-efficient scheduling in such multi-access channel includes [1], [3], [5], [6] and [7]. In all of these work, orthogonal transmission schemes, such as time division and frequency division, are adopted. In [8], it is proved that orthogonal transmission schemes are strictly suboptimal with respect to the bandwidth efficiency in an asymmetric multi-access channel. Therefore, in this paper we will discuss the optimal scheduling in a general multi-access transmission, where the sensor nodes simultaneously transmit and commonly occupy the entire bandwidth. Note that we emphasize an information theoretical analysis of the proposed problem. To obtain the optimal scheduling, we adopt a method combined of the polymatroid analysis and deterministic job scheduling. The capacity region of a multi-access channel possesses a polymatroid structure, which exhibits favorable characteristics and provides useful tools to analyze the multi-access scheduling problem. The vectors in the capacity polymatroid denote the feasible rate allocations in the multi-access capacity region. A vertex is a special rate allocation which can be realized by successive decoding the messages of the sensor nodes. Varying the successive decoding order we can achieve any vertex of the capacity polymatroid. The dominant face of the capacity polymatroid represents the boundary of the capacity region where the optimal bandwidth efficiency is achieved. Because the dominant face is a convex hull of the vertices, by time sharing transmission of the vertices we can realize an arbitrary rate allocation in the dominant face. Given the transmit powers, the multi-access capacity polymatroid is analyzed. We argue that the optimal rate control can be achieved by controlling the successive decoding order of the sensor nodes. Therefore, a similarity is drawn between the multi-access scheduling and deterministic job scheduling, since the solutions to both these problems reduce to optimal processing orders. The power control and rate control in a multi-access scheduling are mutually conditioned. In this paper, we first prove that transmitting with reduced powers cuts down the energy budget in a multi-access transmission. On acquiring the optimal power control policy, we argue that at any point of time the optimal rate allocation corresponds to an optimal successive decoding order of the sensor nodes. Therefore, a connection is built between the multi-access scheduling and the deterministic job scheduling. Exploiting the channel gains and backlog lengths of the sensor nodes, we reformulate the multi-access scheduling problem and tackle it by adapting the job scheduling policies. We also discuss the implementation procedure of the proposed scheduling and provide the simulation results to illustrate their significant improvement in energy conservation. Note that in [8] the authors consider a similar multi-access network with two sensor nodes and achieve the optimal scheduling subject to a deadline constraint. However, employing an iterative algorithm, the proposed strategy requires too much computation to be implemented in a practical sensor network. In addition, to compute the schedule, the packet arriving information is required non-causally before the transmission. Last but not least, powerful amplifiers must be equipped with the sensor nodes to produce large range power output to realize the scheduling. All of these prerequisites are unrealistic in practical application of WSNs. On the contrary, we introduces a new framework to solve the multi-access scheduling problems by combining the polymatroid analysis and the job scheduling formulation. The proposed strategies do not require any non-causal information and the transmission schedule is determined only upon the backlog lengths and the channel gains of the sensor nodes. Besides, we will show that the proposed strategies are efficient to compute and implement. The rest of the paper is organized as follow. In Section 2, the polymatroid structure of the multi-access capacity region and the deterministic job scheduling are briefly reviewed. In Section 3, the system model is introduced and the energy-efficient multi-access scheduling problem with power constraints is discussed. In Section 4, we prove that transmitting with reduced powers conserves energy in a multi-access transmission. In Section 5, we show that given the transmit powers the optimal rate control is realized by controlling the decoding order of the sensor nodes. Hence, we obtain the solutions to the rate control problems by adapting the job scheduling rules. In Section 6, we address the implementation issues and provide the method to compute the completion delay under the proposed scheduling strategies. We show the simulation results to validate the proposed strategies in Section 7 and conclude the paper in Section 8.

We prove that in the multi-access transmission the energy cost can be saved by transmitting with reduced powers over a long time duration. Given the transmit powers, we analyze the polymatroid structure of the multi-access capacity region. Then, we show that the rate control problem in a multi-access polymatroid can be reformulated as job scheduling problems and solved by adapting the rules in job scheduling theory. Due to the properties of the multi-access capacity polymatroid, the proposed scheduling can be achieved by controlling the successive decoding order of the sensor nodes. We also address the implementation issues and provide methods to compute the completion delay under the proposed strategies. The structure properties of the multi-access polymatroid and contra-polymatroid make it convenient to analyze the multi-access transmission. On the other hand, there is a number of mature job scheduling policies ready to be adapted to solve practical problems. Combining the polymatroid analysis and job scheduling formulation, the method proposed in this paper solve the scheduling problems in a general multi-access channel efficiently.