9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Energy-efficient scheduling of packet transmissions over wireless networks

INFOCOM 2002

1

Energy-ef?cient Scheduling of Packet Transmissions over Wireless Networks

Abbas El Gamal, Chandra Nair, Balaji Prabhakar, Elif Uysal-Biyikoglu, and Sina Zahedi Information Systems Laboratory Stanford University Stanford, CA 94305 abbas@isl.stanford.edu,mchandra@stanford.edu,balaji@stanford.edu, elif@stanford.edu, szahedi@stanford.edu

Abstract— The paper develops algorithms for minimizing the energy required to transmit packets in a wireless environment. It is motivated by the following observation: In many channel coding schemes it is possible to signi?cantly lower the transmission energy by transmitting packets over a long period of time. Based on this observation, we show that for a variety of scenarios the of?ine energy-ef?cient transmission scheduling problem reduces to a convex optimization problem. Unlike for the special case of a single transmitterreceiver pair studied in [5], the problem does not, in general, admit a closedform solution when there are multiple users. By exploiting the special structure of the problem, however, we are able to devise energy-ef?cient transmission schedules. For the downlink channel, with a single transmitter and multiple receivers, we devise an iterative algorithm, called MoveRight, that yields the optimal of?ine schedule. The MoveRight algorithm also optimally solves the downlink problem with additional constraints imposed by packet deadlines and ?nite transmit buffers. For the uplink (or multiaccess) problem MoveRight optimally determines the of?ine time-sharing schedule. A very ef?cient online algorithm, called MoveRightExpress, that uses a surprisingly small look-ahead buffer is proposed and is shown to perfom competitively with the optimal of?ine schedule in terms of energy ef?ciency and delay.

Before we introduce the minimum-energy scheduling problem, we brie?y discuss it within the larger context of packet transmission protocols in wireless networks. Reducing energy consumption by lowering transmission power (and thus increasing transmission time) also reduces interference to other nodes, resulting in an increase in the overall throughput of the network. But, as noted in several previous papers ([10] is a recent reference), power control requires the participation of all nodes in the network: Nodes that reduce transmission power unilaterally risk suffering a high interference from nodes that do not. Thus, a network-wide protocol is needed to ensure that users adhere to the physical and link layer algorithms employed for energy minimization or for interference mitigation. While considerable research has been devoted to the design of good power control algorithms for dealing with interference, energy minimization is a more recent problem motivated by the advent of ad hoc and sensor networks. It is the goal of this paper to develop algorithms for energy-ef?cient scheduling in a wireless environment, building upon the approach taken in [5]. A. Minimum-Energy Transmission Scheduling Problem For concreteness, consider the downlink channel in a wireless network involving a single transmitter and multiple receivers. Suppose that ? packets arrive at the transmitter at random times ? in the interval ? ? ? destined for one of ? receivers. The node is required to transmit all ? packets within the interval ? ? ? 1 . Since the transmitter knows the destination of each packet, we may assume, without loss of generality, that the energy required to transmit packet over units of time is given by the energy function ? ? ?. The ? ? ? are assumed to satisfy the following conditions: 1. ? ? ? ?. 2. ? ? ? is monotonically decreasing in . 3. ? ? ? is strictly convex in . 4. ? ? ? is continuously differentiable and its derivative, ? tends to ?? as tends to 0.

I. I NTRODUCTION

AND

P ROBLEM F ORMULATION

The energy-ef?ciency of computing, signal processing and communication devices is key to the widespread deployment of wireless networks, especially of sensor and mobile ad hoc networks. On the networking side, several recent papers have proposed methods for conserving energy. For example, [1] proposes a randomized algorithm that allows nodes in a dense wireless network to switch between on and sleep modes so as to trade-off topology maintainence with energy conservation, [4] proposes a method for empirically measuring the energy consumed by a node in an ad hoc network by monitoring its power consumption, [5] considers the problem of minimizing the transmission energy of a wireless node and presents “lazy” schedules that trade-off delay for energy; and, [9] studies the problem of constructing energy-ef?cient multicast and broadcast trees. This paper studies the problem of minimizing the energy required to transmit packets over a wireless network based on the following observation [5]: In many channel coding schemes, lowering transmission power and increasing the duration of transmission leads to a signi?cant reduction in transmission energy. In particular, it was observed that for a given channel coding scheme if ?? ? is the energy expended for transmitting a packet over units of time, then ?? ? is a non-negative, monotonically decreasing, and strictly convex function of .

? ?

The ?rst three conditions have been justi?ed in [5] by considering some channel coding schemes. The last condition is a technical condition introduced here for ease of exposition. It is not

? The imposition of a strict deadline, ? , by which all transmissions had to terminate was intended to capture several realistic wireless scenarios (see [5] for further details).

INFOCOM 2002

2

be its transmission duration. The causality constraint × ? ensures that the transmission of a packet cannot begin before its arrival time. Even though it is not necessary for minimizing energy that packets be transmitted in the order of their arrivals, it is easy to see that any set of transmission times that satisfy the causality constraints and the overall deadline constraint ? for some packet transmission order also sati?es them when the packets are transmitted in the order of their arrivals. Thus, without loss of generality, we can assume that the × are monotonically increasing in . With this assumption the deadline constraint requires that × ? · ? ? . A vector of transmission times and transmission duration pairs, ?× ? ? ? that satis?es the above conditions will be called a feasible schedule. We are now ready to state the of?ine energy minimization problem. Given: a. a vector of packet arrival times ? ?? ?, ? ? ·? , and ?? ? , and b. energy functions ? ? ? which, for each isfy the hypotheses 1-3 mentioned above;

required for the proofs, since strict convexity implies the existence of right and left derivatives and one can work with these. The last condition is also not arti?cial since it is satis?ed by several channel coding schemes. For example, optimal coding over an additive white Gaussian noise (AWGN) channel with noise ? power ? yields the energy function ? ?? ? ?? for a -bit packet, which clearly satis?es condition 4. Let × be the start time of the ? packet’s transmission and

explicit solution. For example, in the downlink problem there is a signi?cant difference: the ? ???s are not all identical. This is because scheduling must be simulatneously done for the different channels between the transmitter and each receiver. These channels could possibly give rise to different packet transmission energy functions. For example, this occurs when the receivers are not equidistant from the transmitter. Since signal attenuation depends on the distance between the transmitter and each receiver, the energy required to transmit a packet reliably in time will be different for the different receivers. This makes it impossible, in general, to obtain explicit solutions for the optimal of?ine minimum-energy schedule in terms of the ? s as was possible before. Of course, one could use general convex optimization techniques to solve the above problem numerically. However, we note that the problem has special structure, making it amenable to special methods. In particular, its cost function is the sum of several convex energy functions, allowing us to perform local optimizations ef?ciently. Furthermore, the individual energy functions decrease monotonically, allowing local optimizations to be one-sided – namely, to the right. These special features are exploited in developing the MoveRight algorithm, which ?nds the optimal schedule ef?ciently. The MoveRight algorithm also solves several other convex optimization problems related to determining of?ine energy ef?cient schedules in wireless networks. These include the following scenarios: a. The downlink problem. b. The optimal time-sharing schedule for the uplink multiaccess 2 problem. c. All of the above scenarios when packets have individual deadlines before which they must be transmitted. The deadlines may be different for each packet, but must satisfy some conditions as stated later. d. All of the above scenarios when the transmit buffer has a ?nite size of . Additionally, by employing a look-ahead buffer, the optimal of?ine schedule determined by the MoveRight algorithm can be used for online implementation. In this case, we show that a much faster version of the MoveRight algorithm, which we call MoveRightExpress, can be used to schedule the buffered packets. Of course, use of the look-ahead buffer would impose additional delays, but energy-ef?ciency requires one to trade-off an increase in delay for a decrease in energy consumption. The trade-off would be worth it if a small increase in delay leads to a signi?cant reduction in energy. Previous work [5] shows that this is indeed the case for the single transmitter-receiver pair. In this paper we ?nd that a small amount of look-ahead can lead to a substantial reduction in energy in the scenarios mentioned above.

? Recall that the uplink problem involves multiple users transmitting to one receiver using multiple access schemes. Information theory [2] tells us that time-sharing is not optimal for the general multiple access problem. We may nevertheless seek the optimal time-sharing schedule, similar to other work in the networking literature on the multiple access channel [6].

?

?

, where

? ?

?

, sat-

?nd a feasible schedule so as to minimize the total transmission ?? energy: ?? ? ? We note that the convexity of the ? ? ? makes this a convex optimization problem with linear constraints. For the special case of a single receiver, the ? ???s are identical, say equal to the function ????. In this case, the problem was solved explicitly in [5], yielding the following optimal of?ine schedule:

?

where ? and ?, and de?ne

?

if

??

(1)

?

are obtained recursively as follows. Let

??

?

?

? ?

?

?

? ?

·?

and

? ?

·?

??

For ?

? , let

?

?

? ·?

·?

? ?

??

? ?

.

· ·? · ·?

?? ??

·? ·?

and

·? ? ??

? ·?

where ?

?

Unfortunately, for the general case involving multiple users, the convex energy minimization problem does not admit such an

INFOCOM 2002

3

B. Organization of the paper Section II develops the MoveRight algorithm for optimally solving the downlink of?ine transmission scheduling problem, and contains the main results of the paper. Section II-A provides the proof of optimality and Section II-B discusses the algorithm’s worst-case complexity, implementation issues, and its fairness properties. Section II-C shows that MoveRight can also ?nd the optimal of?ine schedule for scenarios involving deadlines for individual packets and ?nite transmit buffers. Section III discusses of?ine transmission scheduling for the uplink problem. Online scheduling using look-ahead buffers is presented in Section IV. II. A N O PTIMAL A LGORITHM FOR THE O FFLINE D OWNLINK S CHEDULING P ROBLEM We develop the MoveRight algorithm for determining the optimal of?ine schedule for the downlink problem. After introducing the algorithm, establishing its optimality properties and analyzing its complexity, we shall show how it applies to other situations of interest. Using notation introduced in the previous section, consider the problem of transmitting ? packets that arrive at times ? ? ? during the period ? ? ?, and as before, we assume ?? ?. For notational convenience, set ? ? ·? ? . Let × be the time the ? packet starts transmitting and let be the duration of its transmission. A schedule is feasible if it is causal: × ? for every ; and all packets are transmitted ? It is easy to see within the interval ? ? ?: ? · ? ? ? · ? that ? · ? ? ? · ? ? is a necessary condition for the optimal. Otherwise, we may simply ity of the transmission times increase some of the and reduce total energy (observe that increasing transmission times does not hurt the causality constraint). This reduces the causality constraint for all schedules ? which satisfy ? · ? ? ? · ? ? to ? ·? ? We are required to ?nd a feasible schedule so as to minimize ?? the total transmission energy: ? ? ? ?. The MoveRight Algorithm: The main idea of the MoveRight algorithm is to iteratively move the starting times of packet transmissions to the right, one packet at a time, so that each move locally optimizes the overall energy function. As we shall see, this iterative local optimization leads to the globally optimum solution. The algorithm proceeds iteratively. Initially, the start-times of all packets are set equal to their arrival times; that is, × ? ? ? ? , and we set the transmission duration of packet to ? ×?·? ? ×? . Now consider the ?rst two packets. Keep? ? ing ? · ? ?xed, we move × ? to ×? (see Figure 1), where ? ? ? ? ×? ×? ? is the point which minimizes the sum of the trans×? ? ? mission energies of the ?rst two packets. Note that × ? ×? nec? ? essarily, and therefore the start-time of packet 2 can only move to the right. In this simple case it is easy to see that leftward movements of the start time of packet 2 would violate the causality constraint, and are therefore not allowed. We prove that, in general, leftward movements are not necessary, and hence name

the algorithm MoveRight.

? Continuing, set ? to be the transmission time of the ?rst packet obtained after optimally increasing × ? as above, and reset ? ? ? ? ? by decreasing it by an amount ? ? ? .

Now consider the second and third packets. Again keeping ? ? · ? ?xed, increase ×? to ×? optimally, and hence obtain ? . ? ? ? by reducing it by an amount ? ? ? , and proceed to Reset ? ? ? obtain ? , for ? ? . This completes the ?rst pass of the algorithm. Continue to make additional passes and terminate the algorithm after pass ? , where

? ?

?

??

??

for all

?

?

A pseudo-code for the algorithm is given below.

k = 0; flag = 0; for i = 1:M

?

×

·?

?×

end while flag==0 k=k+1; for i=1:M-1

·?

?

best

? ? ?? ·??

×

??

end if flag=1; end end

??

? Here best? ?? ·?? × ?? returns the optimal transmission ? durations when the total transmission duration is ?? · ·?? ?? ? and the energy functions are ? ??? and ? ·? ???. However, best also keeps in mind the causality constraint that × · ? ·? .

Arrival times Pass 1 Pass 2

?

?? ×? ?

?? ×? ? ×? ? ×? ?

?

Fig. 1. Illustration of the MoveRight algorithm for

? packets.

A. Proof of optimality We ?rst establish the following lemma in the absence of causality constraints. Lemma 1: Consider two packets, 1 and 2, to be transmitted in the time interval × ??. Packet 1 is to begin its transmission at time ×, while packet 2 is to end its transmission at time ?. Let ? ? and ?? be the transmission energy functions for packets 1 and 2, respectively, and assume that they satisfy conditions 1-4, then the following hold. 1. The optimal transmission times are unique. 2. Let × be the start time of the second packet’s transmission in the optimal schedule. Then × increases when × increases,

INFOCOM 2002

4

holding ? ?xed. The same is also true if ? increases and × is held ?xed, and also if both × and ? increase.

3. If the total time, ? ? ×, decreases (increases) then the transmission durations of both packets decrease (increase, respectively). Proof Let ? and such that ? · ?

?

The main idea of the proof is to ?rst show that, for each , is non-decreasing in and that it is bounded above by × ??? . Therefore each × ×? . We ?nish by establishing that × ? ??? , for every . × Theorem 1: Let × ×? ×??? be as de?ned before. Then

×

, the algorithm determines × by increasing from 1 through 2. Consider the case when × increases to × ? and ? is ?xed. Let ??? and ? denote the optimal transmission times for the ?rst ? . Because of the causality constraint, it follows trivially that ? ? ? ×? for each ? ? ? (recall that × ? ? ). packet over intervals × ?? and × ? ??, respectively. Note that × ? ? and ? ? are the ?rst time that there is a ??? ? ? ? ?? ? × ? ??? ? ?? ? ? ?, where ? denotes the ?rst Suppose that ? ? ? ? violation; that is, × ? × ? ·? . Since this is the ?rst instance, we derivative. ? ·? ? ?? ? ? Because the energy functions are strictly convex, their deriva- have that × ? ?? × ? ?? and × ? ·? × ? ·? . tives are strictly increasing. Therefore, since × × ? , it follows Consider the intervals × ? × ? ?? ? and × ? ·? × ? ?. The ?rst ? ?? ? ·? ? ?? ? ·? ??? ??? ??? ??? that ?? ? ? ???? ???×? ? ? ? ?? ? ? ???? ???×? ? ? interval determined the boundaries within which the MoveRight ??? ? ?×? ? ×?? ? ? ?? ? × ? ??? ? ?. ? ?. Similarly, ?? ? ? ? ? algorithm would place × ? , the start-time of packet ? in the ? th ?. The pass. Likewise the second interval determines the boundaries We wish to ?nd so that ?? ? ? ? ?? ?? ? ×? ? ? above two statements and the uniqueness of the optimal value for placing the start-time of packet ? in pass ? · ?. The in??? ??? ? allow us to conclude that ? ? ?×? ? ×? ? , or that equalities in the previous paragraph imply that each boundary ??? · × ? · ×? . This proves the claim. ? ? ? point of the second interval is to the right of the corresponding The case when ? increases can be established similarly. The last boundary point in the ? rst interval. Given this, the modi?ed ? ? case can be handled by ?rst increasing × and then increasing ?. version of part 2 of Lemma 1 implies × ? × ? ·? . This con? ·? 3. Observe that the optimal transmission durations are just a tradicts the assumption × ?? × ? and hence property (1) will function of total time available, ? ? ×, and do not depend on always hold. the absolute values of × and ?. Hence a decrease in ? ? × can ? ? and ? ? are the ?rst time be made equivalent to increasing × to × ? , say, while keeping ? 2. As above suppose that ??? ? ?×? ? ×? ??? . that there is a violation; that is, × ?? ? ×??? . (For reasons as ? ?xed. From above we have ? ? ? ??? , we have that the transmission duration of the above ? ? will not violate.) ? Since ? ? ?? ? ×??? ? and × ? ·?? ×??? . ?? ? ·? ?rst packet decreases. For the second packet we need to show Again, as before, we obtain × ? ?? ??? ? ? that ? ? × ? ? ? ? ×? ? ? . This readily follows from Notice that the boundary points of the interval × ???? × ??·?? ? ??? ? ?×? ? ×? ? . The case when ? ? × increases can be are each to the left of the corresponding boundary points of ? ? ? handled similarly. ×??? ? ×??? ?. Again by part 2 Lemma 1 we must have × ? ?? ? ·? ??? . This contradiction shows there can be no violation. We now introduce causality constraints to Lemma 1, which will × ? be needed in the proof of Theorem 1. Note that with no causal3. Let ? ?? ? ×? ? ×? . Note that the vectors ·? ity constraints, the start-times are unconstrained and the energy??? are ?xed points for the MoveRight algorithm: ? and optimal start time of packet ? can be to the left of (or earlier than) its arrival time. Of course, this can violate the causality passing them once through the algorithm does not alter any entry. This is true of ? , by de?nition. Since alterations by the constraint. However, it is not hard to see that, in this case, the optimal start-time for packet ? is in fact equal to its arrival time. Thus, part 1 of Lemma 1 holds with causality constraints. Part 2 needs to be modi?ed to: 2. Let × be the start time of the second packet’s transmission in the optimal schedule. Then × does not decrease when × increases, holding ? ?xed. The same is also true if ? increases and × is held ?xed, and also if both × and ? increase. MoveRight algorithm only result in energy reduction, the optimality of ??? ensures that it will be a ?xed point. From part (2), we have × ? ×??? , for all ? ? · ?, with equality holding at both the boundaries. Also, from × ? ·? ×??? , we ? ? ·? ?? ? ?? ??? ? . have ? ? We will argue by contradiction and hence let us assume that ??? ? ??? . It is easy to see from the ?? ? ? ·? ·? ??? . Therefore, it follows from the ? de?nition of that, × ·? × ·? feasibilty of ×? that the causality constraint did not play any ·? role in the placement of × ??? . The same however cannot be said ·? of ×? . That is, the pairwise optimization of the transmission ·? durations of packets and · ? could have yielded a start-time of ×?·? for packet · ?. However, packet · ? was forced to begin transmission only at × ? , due to causality constraints. It ·? follows that ×?·? ×? . ·?

1. Minimizing the strictly convex function ? ? ? ? ? · ?? ?? ? × ? ? ? × will yield the optimal schedule, which ? ? over ? ? will obviously be unique given the strict convexity.

??×

be any transmission transmission schedule

1. 2. 3.

× × ·? . × ×??? . ×? ×??? .

Proof 1. Recall that the algorithm works in passes: For each ?xed

Now suppose there are ? packets and let ? ? be their transmission durations after the ? pass of the MoveRight al? ?? gorithm. Let × ? ?× for ? ? ? and ? ??? ??? be the optimal transmislet ×? ·? ? . Let ? ? sion times, which exist because of the convexity of the problem ??? and the compactness of the search space. Let × ??? ? ? ?? ??? ?? × ??? ? ??? for ? ? ? and let ×? ·? ? . ? ?

INFOCOM 2002

5

Let

?

?

??? and

×?·? ? ×? and ?·? ×? ? ×?·? . We have ? ·? ??? . Therefore, ? ? ·? ·?

·?

?

??? and

?

·?

???

·?

We will now obtain the contradiction. First, suppose ??? · ??? . In this case from part 3 of Lemma 1 it follows ? ·? ??? and ? ??? . Next suppose ? · ? that ? ·? ·? ·? ??? · ??? . Then, by exactly similar arguments, it follows that ·? ??? and ? ??? . Finally, suppose ? · ? ? ·? ·? ·? ??? · ??? . Then, by part 1 of Lemma 1, it follows that ? ·? ??? and ? ??? . In all three cases we have contradicted equation (2) and proved the theorem. B. Properties of the MoveRight Algorithm

·? ·?

? · ·?

(2)

Lemma 2: Suppose ? packets with identical energy functions arrive at time 0 destined for a single receiver. Let × be the start-time of the ? packet after the ? pass of the MoveRight algorithm, and let × ? ×??? ? ? × ? ×??? . Then, given ? ?? ? an ?, × ? ×??? for ? ?? ?? ?? ?? , where ? is the largest eigenvalue of the matrix exhibited in the Appendix. Numerical evaluation of the above bound for values of ? up to ???? suggests growth rate of ? ? passes. Simulation shows that the run time and number of iterations taken by the MoveRight algorithm are comparable (in terms of orders) when the energy functions are all identical, as compared with the case when they are distinct. We considered 700 packets arriving at time ?, to be scheduled for transmission during ? ?????. Table I shows the number of moves, passes and the run-time of MoveRight when all 700 packets have equal energy functions. The algorithm was terminated when the total energy was within a certain percentage, denoted by % Opt in Table I, from its optimal value. Then we allowed each of the 700 packets to have an energy function chosen from a set of 10 types uniformly at random. The corresponding results are tabulated in Table II. The simulations were performed on a Pentium III 800 MHz machine. % Opt. 10 5 1 0.1 No. of Passes 85085 85609 86059 86164 Run-time (sec) 132.8 133.4 133.9 134.0

OF

1. An ordering on arrival times: Because the algorithm moves start-times monotonically to the right, the worst-case inputs (packet arrival times) are easily identi?able in the following sense. Consider two different sets of arrival times, ? and ?? , whose optimal schedules are identical. If ? ?? , for ev? are the corresponding start-times after the ery , and × and × ? pass of the MoveRight algorithm, then × ×? , for every and . Therefore, when the MoveRight algorithm converges for the ?rst input, it would have automatically converged for the second. We may therefore say that ? is worse than ?? . This ordering can be used to determine the complexity of the algorithm, as described next. 2. Computational complexity: From part 2 of Theorem 1 we know that the MoveRight algorithm does not change the starttimes of packets which are restricted by the causality constraint under the optimal schedule; that is, packets such that × ??? ? . Call these the “immovable packets”. The immovable packets have an interesting decoupling property: movements of packets to their left do not in?uence movements of packets to their right. Thus, the packets that move can be broken down into bands at whose end points there are immovable packets. The rate of convergence of the MoveRight algorithm is determined by the rate at which packets in the slowest moving band will converge to their optimal positions. So, how fast does the slowest-moving band converge? Observe that the start-times of packets within each band are not affected by the causality constraint. Therefore, their optimal start-times will be the same as determined by the MoveRight algorithm, assuming that the movable packets within a band all arrived at the beginning of the band! But, by the previous discussion on the ordering of arrival times, this last set of arrival times represents the worst-case as far as the convergence of the MoveRight algorithm is concerned. Although the worst-case inputs are identi?ed, without knowing the explicit form of the energy functions, it is dif?cult to bound the worst-case number of iterations of the MoveRight algorithm. However, assuming the energy functions are identical (the single receiver case), yields the following lemma, whose proof is presented in the Appendix.

TABLE I T HE NUMBER OF PASSES AND THE RUN - TIME

M OVE R IGHT FOR

PACKETS WITH EQUAL ENERGY FUNCTIONS .

% Opt. 10 5 1 0.1

No. of Passes 175425 186397 199081 203084

Run-time (sec) 240.1 251.6 264.9 269.0

OF

TABLE II T HE NUMBER OF PASSES AND THE RUN - TIME

M OVE R IGHT FOR

PACKETS WITH DIFFERENT ENERGY FUNCTIONS .

3. Algorithm implementation: The main computational module in the execution of the MoveRight algorithm is the best routine, which involves just two individual energy functions. For each pair of energy functions, the best routine can be implemented via a precomputed lookup-table, resulting in signi?cant speedup. Note that, by comparison, general convex optimization methods that do not exploit the special structure of the problem would need to perform a signi?cant amount of computation at each iteration. 4. All packets available at the origin: An important special

INFOCOM 2002

6

?. This case is when all of the ? packets are available at ? situation is particularly relevant for the online implementation of the MoveRight algorithm via a look-ahead buffer, and for the discussion on fairness to follow next.

Observe that none of the ? packets is constrained by causality: their start-times can be anywhere in ? ? ?. Number the packets 1 through ? and let ? ? be the optimal schedule as determined by the MoveRight algorithm. We claim that any other numbering of the packets will also lead to each of them having the same transmission durations. To verify the claim, ? simply note that cost function we’re minimizing is ?? ? ? subject to the constraint ? . Given the strict convexity of the cost function (and hence the uniqueness of the optimal schedule), the solution of this problem is identical to the solution of the problem: Minimize: subject to:

say (? ? ), it is not allowed to simultaneously buffer more than packets. (We include the packet currently being transmitted for determining the buffer occupancy at any time.) A transmission schedule under the presence of a buffer of size is valid if, and only if, for every , packets and · never reside in the buffer simultaneously. This translates to the following constraint on the departure time: ? · . Rewriting the last constraint as ? · ?? · ? ? ?, we see that this is equivalent to the previous case when ? · ? ? . Note that if packets arrive in batches, then it is possible that the optimal schedule may be to set one or more transmission durations to 0 (thereby incurring in?nite energy expenditure), if it is to satisfy the buffer constraint. This can be addressed either by dropping packets or by disallowing batch arrivals. III. O FFLINE S CHEDULING

FOR THE

?

? ?? ??

? ??

U PLINK P ROBLEM

?

for any permutation, , of the numbers 1 through M. 5. Fairness: For concreteness, consider the downlink problem , of all with two receivers. Suppose the transmit durations, packets are computed using the MoveRight algorithm. If, at the start of a new transmission, packets for both receivers are simultaneously present in the transmit buffer, then the packets may be transmitted in any order without affecting the energy-ef?ciency. This follows from the previous discussion point. Thus, when packets destined for different receivers are present in the buffer, in the interests of fairness, we may transmit packets in a roundrobin fashion as opposed to a ?rst-come-?rst-served order. The overall expenditure of energy is identical in both cases. C. Extensions of the MoveRight Algorithm Throughout this section we assume that there are ? packets to be scheduled in an of?ine fashion, given the arrival times of the packets. We will show how the MoveRight algorithm can be used to arrive at the optimal of?ine schedule. 1. Packets have individual deadlines: Packet , ? ?, arrives at time ? and must be transmitted by time ? · , where ? is the deadline for packet . Equally, if is the departure time of packet , then ? · . The ’s are allowed to vary across packets. However, ? · , will be assumed to be monotonically increasing with . Observe, that these impose additional linear constraints on the energy cost-function. The only modi?cation to make in the MoveRight algorithm is to change the best subroutine. The modi?ed best subroutine simply takes into account the individual packet deadlines before returning the optimal transmission durations of two adjacent packets. It can be shown, but we omit it here due to lack of space, that the convergence and optimality properties are preserved under this modi?cation. 2. Finite transmit buffers: Consider the downlink problem, where one transmitter is to send each of the ? packets to one of ? receivers. When the transmitter has a ?nite buffer of size,

The uplink or multiaccess wireless channel consists of multiple transmitters and a single receiver. In general, users transmit simultaneously causing their signals to interfere at the receiver. The optimal rates at which the users can simultaneously transmit has been determined for fairly general channel models, e.g., the Additive White Gaussian Noise (AWGN) channel (see Chapter 14 of [2]). The multiaccess of?ine scheduling problem involves the determination of time intervals and transmission rates obeying causality constraints. To make the discussion concrete we will assume the AWGN multiaccess channel model and restrict ourselves to two transmitters. We assume that in time the ?rst transmitter wishes to transmit a ? -bit packet while the second transmitter wishes to transmit a ? -bit packet. We let ?? and ?? be the received energies for users 1 and 2, respecively. Assuming receiver noise power ? , it can be shown that ? ? and ?? must obey the following conditions for some ? ? for reliable communication to take place

?? ?? ?? · ??

?? ??? ? ? ?? · ?? ?? ??? ? ? ?? · ?? ?? ???? ? · ? ? ? ?? · ??

Moreover, any ?? ? ?? ? pair that satisfy these bounds can be achieved (with some probability of error that can be made as small as needed by proportionally increasing ? , ? , and ) using simultaneous communication. Figure 2 plots the boundary of ??? ?? ? pairs satisfying these conditions. If instead we restrict ourselves to time-sharing transmission schemes, where the users do not transmit simultaneously, we can only achieve ??? ?? ? pairs satisfying

?? ??

? ?? ??? ? ?? ???

? ?? ? ? ??

? ?? · ?? ? ?? · ??

where ? ? ? ?? is the fraction of time the ?rst user transmits and ? ? ? ? is the fraction of time the second user transmits. The boundary of ?? ? ?? ? pairs satisfying these conditions is also plotted in Figure 2. Note that the boundary of the time sharing region meets that of the optimal region at a single point.

INFOCOM 2002

7

??

ets for departure in the interval ? ???. Meanwhile, buffer the packets arriving in ? ??? and schedule them for departure in the interval ?? ???. Proceeding in this fashion, packets arriving in the interval ?? ? ??? ??? are scheduled for departure using the MoveRight algorithm in the interval ?? ?? · ????. Call this scheme the “static look-ahead scheme”. We shall now see that property 4 of the MoveRight algorithm vastly simpli?es the scheduling complexity of the static look-ahead scheme, yielding the following algorithm. The MoveRightExpress Algorithm: Suppose there are ? packets in the look-ahead buffer at time ??, to be scheduled for transmission in the interval ?? ?? · ????. Let there be ?? ?? packets destined for receivers 1 through ? respectively. According to property 3 these packets may be scheduled in any order. Therefore, by reordering if necessary, we may assume the following order on the packets: all packets for receiver 1 appear ?rst, followed by all packets for receiver 2, and so on, with the packets for receiver ? appearing at the end. Suppose that all packets are of equal length 3 . Since the energy functions of the ?rst ? ? packets are all equal to ? ? , we may assemble these packets into a “superpacket”. The energy function of the superpacket is ? ? ? ? ?? ?? ? ?? ?. Likewise assemble the packets for the other receivers into superpackets with corresponding energy functions ? ? ? ? ? ? ? ?, ? ?. Now run the MoveRight algorithm on these ? superpackets to obtain ?? ?? as the optimal transmission durations. Given this and the fact that the packets destined for a single receiver must all have the same transmission duration (they have identical, strictly convex energy functions), it follows that the optimal transmission durations for the ? ? packets of receiver 1 ? are ?? . Likewise, the optimal transmission durations for the ? ? ? packets of receiver are ? . Having determined the optimal schedule for all the packets, another application of property 4 implies that they may be transmitted in any order in the interval ?? ?? · ????. Remark: It is worth noting the reduction in complexity achieved by the MoveRightExpress algorithm over the basic MoveRight algorithm. From depending on the total number of packets, ? , the MoveRight Online algorithm’s complexity only depends on the number of receivers, ? . As a comparison, we ran MoveRightExpress for the scenario of Table II. The results are tabulated in Table III. A comparison of Tables II and III shows that MoveRightExpress is much more ef?cient than the basic MoveRight algorithm. Again, the simulations were performed on a 800 MHz Pentium III machine. In contrast, one could also consider the following “dynamic look-ahead scheme”. Set the transmit time of the ?rst packet, ?. Buffer all subsequent packets which arrive in the ? interval ? ??. Schedule the second transmission using the MoveRight Online algorithm in the interval ? ???. Suppose according to this schedule, the transmit time of the second packet is ? ; i.e., it transmits from ? to ?· ? . At ?· ? , we have access to all packets that arrived in the interval ? ? · ??. Given

? Extending

?

???

?

? ??

?

?? Fig. 2. Achievable ?? ?? region for the AWGN multiaccess channel. The solid line represents the boundary of the optimal achievable region, while the dashed line represents the boundary of the region achievable using timesharing.

?

?

????

? · ??

? ??

The scheduling problem for the multiaccess channel involves the minimization of the total transmitted energy. First we discuss the problem of minimizing the energy needed to send two ? for user packets in time . Assuming path loss factors ? 1 and ? ? for user 2, the total transmitted energy can be expressed as ? ?? · ? ?? . In the symmetric case, i.e., when ? ? , it can be shown that time sharing achieves minimum total energy. Speci?cally the following lemma holds. Lemma 3: For the AWGN multiaccess channel ? and ? can be reliably transmitted in time at total minimum energy using time sharing. In this case ? ? · ?? ? ???? ? · ? ? ? ??. This lemma can be used to show that a time-sharing multiaccess of?ine schedule exists that achieves minimum total energy. Such optimal time-sharing schedule can be obtained by simply merging the packets of the two users and using the optimal of?ine schedule for a single user. Unfortunately when ? ? , time sharing is no longer optimal for the of?ine multiacess scheduling problem. However, the optimal time-sharing of?ine schedule can be obtained by merging the packets and then applying the MoveRight algorithm. We omit the proofs of Lemma 3 and the fact that time-sharing is optimal when ? ? due to limited space. IV. O NLINE S CHEDULING The of?ine version of the MoveRight algorithm lends itself nicely for online use by means of a look-ahead buffer. For concreteness, consider the downlink scheduling problem when there are ? distinct receivers (and hence energy functions of ? different types: ?? ?? ). We are required to schedule packets arriving during the time interval ? ? ?. Given the energy functions, the MoveRight algorithm provides the optimal of?ine schedule. For an online implementation of the MoveRight algorithm, buffer all packets which arrive in the interval ? ??, where ? ? . Using the MoveRight algorithm, schedule these pack-

this to variable-length packets is straightforward, see [8].

INFOCOM 2002

8

% Opt. 10 5 1 0.1

T HE NUMBER

FOR

No. of Passes 12 13 20 40

TABLE III

Run-time (sec) 0.0 0.0 0.1 0.1

Delay

1.4

x10

2

3.5 Static L.A. Dynamic L.A.

x10

7

1.2

3

1

2.5

Energy/Packet

M OVE R IGHT E XPRESS PACKETS WITH DIFFERENT ENERGY FUNCTIONS , AS CONSIDERED IN THE SCENARIO OF TABLE II.

OF PASSES AND THE RUN - TIME OF

0.8

2

Delay

0.6 1.5

0.4

1

Energy

0.2 0.5

these packets, again using the MoveRight Online algorithm, schedule the third transmission in the interval ? · ? ?? · ? ?. Proceeding thus, we may schedule packets one at a time by dynamically taking new arrivals into account. If no new packets arrive and the buffer gets empty, then the next arrival is scheduled for a duration of ? and the scheme proceeds as before.

x10

2

0 10

20

30

40

50

60

70

80

90

0 100

Look-ahead Window Size Fig. 4. Comparison of the Online Static and Dynamic Look-ahead schemes as the size of the look-ahead window increases. The packet generation, energy functions, and ? used are the same as for Figure 3. The combined rate was packets/unit time. The MoveRight algorithm gives energy , and delay of .

?

x10

6

?

? ? ??

2.5 Move Right Static L.A. Dynamic L.A. 2

10

8

1.5

Energy

6

1

4

Delay

0.5

2

0 0.1

x10 2

0.2

0.3

0.4

0.5

0.6

0.7

0.8

Arrival Rate (pkts/unit time) Fig. 3. Comparison of the Online Static and Dynamic Look-ahead schemes with the Of?ine MoveRight algorithm for a two-user downlink channel. The users’ packets arrive according to two independent Poisson processes ?? with identical rates. The energy functions used are ?? and

?

Another interesting comparison is between the two online schemes mentioned above, as the size of the look-ahead window, ?, varies. Clearly, larger values of ? will make the online schemes compete better with the of?ine scheme in terms of energy, but will increase the delay considerably. On the other hand, small values of ? will give good delay, but at the expense of energy ef?ciency. This suggests that there is a good choice for the size of the look-ahead window, ?, which tradesoff energy-ef?ciency and delay optimally for a given distribution of the arrival times. Figure 4 illustrates this trade-off when there are two users and the packet arrival times are independent Poisson processes. We notice that the energy curves have a sharp knee around ? ??, suggesting that most of the gain in energyef?ciency is obtained with a look-ahead window of this size. Extension to Channels with fading: Suppose that the fading state of the channel (or channels) is known causally, at the end of each transmission to both the transmitter and receiver. Also suppose that the fading changes slowly compared to the packet transmission duration 4 . Knowing the fading state at time ? is tantamount to knowing the energy functions of all packets (given this fade-state). With these assumptions, the dynamic look-ahead scheme described can be readily used: The transmission duration of the ?rst packet is computed by running the MoveRightExpress algorithm with this set of energy functions. After the ?rst packet is transmitted, the current fading state is used to compute the transmission duration of the second packet, and so on. V. C ONCLUSIONS Recently, there has been a lot of research effort directed toward the design of low power signal processing and computing circuitry. On the networking side protocols are being designed

These are standard assumptions for the slowly fading wireless channel in the literature (see, for example, [7]).

Energy/Packet

Delay

than that for the optimal of?ine. The simulated delay and energy/packet functions are plotted as a function of the combined arrival rate.

?? ? ?? ?????, and the look-ahead window for each rate is chosen so that the energy/packet for static lookahead is ??± larger

???

???? ? ??, ?

Of course, one expects the dynamic look-ahead scheme to outperform the static look-ahead scheme since it uses more information. However, the dynamic look-ahead scheme introduces considerable extra complexity, since it needs to run the MoveRight Online algorithm for every transmission. This is in contrast to the static look-ahead scheme, which only runs the MoveRight Online algorithm once for each look-ahead window of length ?. This extra complexity would be worth it if the dynamic look-ahead scheme considerably outperforms the static look-ahead scheme. But, Figure 3 shows that the difference in energy and delay performance between the two schemes is negligible and quite competitive with respect to the of?ine algorithm when there are two receivers.

INFOCOM 2002

9

for minimum-energy routing, and for power control to mitigate interference. We considered the energy-ef?ciency of packet transmission in several scenarios arising in wireless networks. For the downlink channel, we formulated the energy-ef?cient of?ine scheduling problem as a convex optimization problem and exploited its special structure to provide an ef?cient optimal algorithm, called MoveRight. We showed that MoveRight also optimally solves the downlink problem with additional constraints imposed by packet deadlines and ?nite transmit buffers. For the uplink (multiaccess) problem, MoveRight optimally determines the of?ine time-sharing schedule. A very ef?cient online algorithm, called MoveRightExpress, that uses a look-ahead buffer of small size was shown to perfom competitively with the optimal of?ine schedule in terms of energy ef?ciency and delay. Further work consists of integrating the ideas developed in this paper with network-wide, decentralized, minimum-energy transmission protocols. C ONVERGENCE

A PPENDIX

PROPERTIES OF THE ALGORITHM

M OVE R IGHT

Here we provide a proof for Lemma 2 in Section II-B, which gives an estimate for the worst-case number of iterations for the convergence of the MoveRight algorithm. For this analysis it is assumed that the energy functions are identical and that all packets are available at time ?. The justi?cations for these assumptions were discussed in Section II-B. From [5], we know that the optimal scheduling times are equal.

Proof of Lemma 2: Let ? and × , for ? ? ?? and ?, be the start-times of the packets at the beginning of the th pass of the MoveRight algorithm, where × ? ?, for ? ? , ×? ?, and ×? ·? ? ?. The algorithm is said to have -converged to the optimal solution if ? ? ?×??? ? × ? .

? × s follow the recursion, × ? ?× ?? · ? ? ? . Let × ×? ×? ×? × ? ? ? ×? ·? ?? , ?? × ?? , where then the recursion can be rewritten as ×

R EFERENCES

[1] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An EnergyEf?cient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” ACM Mobicom 2001, Rome, Italy, July 16-21. [2] T. Cover, J. Thomas, Elements of Information Theory, Wiley Series in Telecommunications, John Wiley & Sons, 1991. [3] A. El Gamal, E. Uysal-Biyikoglu and B. Prabhakar, “Reliable Communication with Minimum Energy,” pre-print. [4] L. Feeney and M. Nilsson, “Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment,” Proc. IEEE Infocom 2001. [5] B. Prabhakar, E. Uysal-Biyikoglu and A. El Gamal. “Energy-ef?cient Transmission over a Wireless Link via Lazy Packet Scheduling“. Proc. IEEE Infocom 2001. [6] M.B. Pursley, H.B. Russell, J.S. Wysocarski, “Energy-ef?cient transmission and routing protocols for wireless multiple-hop networks and spreadspectrum radios,” in Information Systems for Enhanced Public Safety and Security. IEEE/AFCEA EUROCOMM 2000. Page(s): 1 -5 [7] T. Rappaport, Wireless Communication, Principles and Practice, PrenticeHall, Inc. N.J.,1996. [8] E. Uysal-Biyikoglu, B. Prabhakar and A. El Gamal, “Energy-ef?cient Transmission over a Wireless Link via Lazy Packet Scheduling,” Submitted to IEEE Transactions on Networking. [9] J.E. Wieselthier, G.D. Nguyen, A. Ephremides, “On the construction of energy-ef?cient broadcast and multicast trees in wireless networks,” Proc. IEEE Infocom 2000. [10] M. Xiao and N. Shroff, E. K. P. Chong, “Utility-Based Power Control (UBPC) in Cellular Wireless Systems,” Proc. IEEE Infocom 2001.

? × ·?? ?

Observe that the

?

?

? ? ? ?

? ? ? ?

?

? ? ? ?

? ?

? ? ?

? ? ? ? ? ?

?

?

? ? ? ? ? ? ? ? ? ? ? ?

? ?

? ?

? ?

??

? ?

? ?? ??

? ?

? ?

? ?

? ?? ??

? ?

? ?? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ?

?

?

?

? ? ? ? ? ?

Therefore, we have × ? ? × ? ×? ? ?? ×? ? ? ? ? ×? ? ? , where ×? ×??? ? ? ?? ? ? ? ? ??. ?? ?× ? This implies that, ×? ? ×? ? ?? ??? ? ? ? ??? ???? ??? . ? ? ? De?ne ?? as the matrix obtained by removing the ?rst row, ? ?rst column, last row and last column of ? ? . Let × ?? ??? ? ? ? ??? ???? ?? . Now observe that ? ?×? ? ? ? ? ? ×? ? ? ?? ? × ? . Let ? be the largest eigen-value (in magnitude) of ??? . Therefore, we have, ? × ? ?? ? × ? ? ? × ? . Hence, for all k, such that ? × ? ? , ? ? ?? ?????? ??? ?? × ? we have ? . × ? ? ? ? ? . Taking ? to be ?xed, this implies for all

? ?? ? ? ? ? ? ?? ? ? ?

?

?

?

?? ? ??

?? ?? ?

?

, we have

?

?? ? × ?

.

INFOCOM 2002

10

Below is a plot of

?

2.5

????.

x 10

6

?? ? ? ? ? ? ?? ? ? ? ,

?

?

for ?

?????

?? ?

T = 10,000 ε = 0.1

2

Number of Passes

1.5

1

0.5

0 0

100

200

300

400

500

600

700

800

900

1000

Number of Packets Fig. 5. Number of passes versus number of packets assuming ? .

??

????? and

赞助商链接

- An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks
- An Energy-Efficient MAC Protocol for Wireless Sensor Networks
- Energy efficient design of wireless ad hoc networks
- Energy Efficient Wireless Packet Scheduling and Fair Queuing
- Energy-Efficient Packet Transmission Over a Wireless Link
- Energy-Efficient Packet Transmission Over a Wireless Link
- Energy-efficient transmission over a wireless link via lazy packet scheduling
- Energy Efficient Cooperative Techniques for Multimedia Services over Future Wireless Networks
- Gamal, “Energy-efficient transmission over a wireless link via lazy packet scheduling
- Energy Efficient Joint Scheduling and Power Control for Wireless Sensor Networks
- Localized algorithms for energy efficient topology in wireless ad hoc networks
- Energy efficient scheduler design in wireless networks in
- Energy-Efficient Routing Protocols in Wireless Sensor Networks - A Survey
- An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks
- Adaptive data fusion for energy efficient routing in wireless sensor networks

更多相关文章：
更多相关标签：