Energy Efficient Scheduler for wireless terminal.pdf

Proceedings of ICCT2003

CSDE2WF’Q:An Energy Efficient Scheduler for wireless terminal

Wang Xue-Pmg, Zheng JimLi and ZHANG Gen-Du

School of information science & Engineering, Fudan University, Shanghai, China 200433

Tel: 8621-65642193#1 Email: x~t2000~hotmail.com

delay; and (3) it manifests the theoretical results by

experiments.

Abstruct-Energy-Efficient for wireless terminal is a

significant research topic due to the characteristicsof wireless

terminal. The communication subsystem is one of the most

important component of wireless terminal system, thus

decrease energy consumption for communication is vital. In

this paper, first a channel state dependent energyefficient

weighted fair queue model is presented, then the upper bound

for packet delay is obtained through theoretical analysis, .and

the performance is construed by simulations, finally further

research is outlined.

B. Related work

Presently main research on wireless schedule focuses

on schedule schemes in base-station, and the main schedule

schemes include channel state dependent packet schedule

(CSDPS)[3] and its variants, ideal wireless fair queue

(IWF)[4] and channel independent fair queue (CIF-Q) [5].

Those schedule schemes, which are running in1 Base-station,

exhibit rather good performance characterismticssuch as

delay constrain, bandwidth guarantee and fairness.

However they all have a serious drawback, Le:. they cannot

schedule uplink data packet effectively and efficiently. To

schedule uplink data packet effectively and efficiently,

such information as the arrival time of uplink data packet

and the status of the queue in wireless terminals is vital,

and however it’s not convenient for base-station to obtain

all these necessary scheduling information.

On the other side, recent research has indicated that

terminal-based schedule is more suitable for uplink data

packet. Authors of [ 61 suggest an energyefficient weighted

fair queue, which is fit for mobile terminals and solve the

uplink data packet schedule effectively. Also they consider

the problems of QoS requirement such as delay constrain,

bandwidth guarantee, fairness and energy limited, which is

the most prominent feature of wireless terminal.

However, authors of [6] pay no attention to channel

state in their wireless schedule, which is a most significant

part of the schedule. Figure 1 depicts the whole schedule

structure of [6]. A channel is an error-free channel, which

is not true in practice. This article extends the thoughts of

[6] and considers error-prone channels and its influence on

schedule .

Keywordv-Energy efficieng Quality of Service, Mrekss

Schedule, WirelessMobile Equipment, WirelessChannel

I. INTRODUCTION

It’s not a fresh topic to schedule data packet in wireless

terminals. While wireless terminals feature both small size

and powered by batteries, the consumption of energy is an

essential problem. Though there will be new high-

performance

batteries,

how

decrease

energy

consumption is still a question.

Recently some research focuses on the schedule of

wireless terminals ’ operating system. Based on operating

system, this kind of schedule make use of the

characteristics of OS, which can have multiple states and

each state has different powerconsumption, thus it’s

possible to decrease the total powerconsumption for the

terminals. For example, in [ 11 Authors suggest decreasing

powerconsumption sharply by making wireless terminals

stay more time at hibernation state. However more research

concentrates on the communication subsystem of wireless

terminal. By decreasing the energyconsumption of

communication, esp. the energy related to receive/transmit

data packet, it could decrease the total energyconsumption

of wireless terminals. In [2] Authors suggest using

dynamic modulation scheme can decrease the total energy-

consumption in communication subsystem because

dynamic modulation scheme automatically selects proper

transmission rate according to the load of communication

system.

The main objective of this article is to research how to

use -dynamic modulation scheme to decrease energy

consumption, and how to guarantee delay, bandwidth,

fairness between different flows, and effects rendered by

error-prone channels.

, irptqae

A. Contribution of Paper

The main contribution of Paper is: (1) it suggests a

channel state dependent energyeficient weighted fair

queue model (CSDE?WFQ: Channel State Dependent

Energy Efficient Weighted Fair Queue); (2) it gives a brief

theoretical analysis and gives a upper bound formula of

Fig. 1. A channel state independent energy-efficient WFQ model

860

Authorized licensed use limited to: Politechnika Lodzka. Downloaded on January 14, 2010 at 20:13 from IEEE Xplore. Restrictions apply.

will insure each stream its guaranteed service rate g ,

which is expressed by (3).

II. KEY TECHNOLOGY

Terminal-basedwireless schedulepolicy

In (3), we suppose that each queue has backlog to send

and the queue is not empty. The premise for GPS is that

each data packet is divided infinitely and each ‘stream can

be scheduled simultaneously. However it’s impossible in

reality, because the basic schedule unit is a block or a

packet and each stream must be scheduled one by one.

WFQ endeavors to simulate GPS model and realize the

serial schedule based on packets or blocks.

D. Wirelesschannel model

For wireless communication, the channel state related

to both time and location [9]. How to simulate the channel

state is a tough task. Nowadays there are a lot of channel

state models, such as two -state Markov Process, multi-state

Markov Process and etc.

Gilbert model is one of the most popular channel state

models, and essentially a two-state Markov Process model

with two states, namely Good and Bad. When channel is in

Good state, packets can be sent; and when channel in bad

state, packets cannot be sent. And the transition between

Good state and Bad state is at will. Fig. 3 depicts the

Gilbert model state transition diagram. Table I lists the

measured value for these transition probabilities obtained

by measuring wireless channels in [Ill. Moreover a

method is introduced in [ 1 11 to artificially generate such

channel model.

There is another variant for Gilbert model. When

channel is in Good state, packets can be sent using a big

probability; and when channel is in Bad state, packets can

be sent using a much small probability. Similarly the state

transition between two states is at will.

Fig. 2. A channel state dependent energy-efficient WFQ model

Fig. 2 presents the logic structure diagram for a channel

state dependent energy-efficient schedule model. In this

figure, the schedule policy is made up of four parts, namely,

the packet arrival process, the scheduler, the channel

monitor and the packet departure process. The essential

point of the schedule policy is how to match the speeds of

multiple input queues and rmltiple output queues at the

same time considering the channel state.

In this model, Leaky bucket algorithm is used to

describe the packet arrival process; weighted fair queue to

depict the schedule; Gilbert model to characterize the

channel monitor, and finally dynamic modulation tech to

send the packet. Below details the former key technologies.

B. . Leaky Bucket Algorithm

Leaky bucket algorithm is used to describe the packet

arrival process. For each input stream i, there are tow

parameters A and U while A stands for the average

arrival rate of stream i uI for the burst size of stream i ,

and Ai( T ,t) for the traffic between time T and t. So

Ai(z, t)< oi +4x(t -z), vt 22 2 0

(1)

Theorem 1: if input stream i conforms to the leaky

bucket algorithm with parameters 0 I and AI, and g stands

for the guaranteed service rate for stream i. then the max

packet delay for stream i under GPS is [8]:

P61

Fig 3. The state transition diagram for Gilbert model

Theorem 1 expresses the upper bound for the packet

delay under GPS. And it’s easy to see that the lower bound

is near 0.

TABLE I.

THE STATISTICS CHARACTER FOR GILBERT MODEL

state(s)

0.9449

0.0087

0.9913

C. WeightedFair Queue

WFQ (Weighted fair queue) is based on the GPS

(Generalized Pro ssor Sharing) model. According to N

streams weights vi to share total link capacity C, GPS

0.055 1

0.8509

0.1492

86 1

Authorized licensed use limited to: Politechnika Lodzka. Downloaded on January 14, 2010 at 20:13 from IEEE Xplore. Restrictions apply.

the,delay to transmit (as in the case b=8); by con.traries,the

less the energy to transmit one bit, the more the delay (as in

the case b=2). Thus it's possible to save energy by

increasing proper delay.

E. Dynamic Modulation Scaling

Dynamic Modulation Scaling (DMS) is first presented

in [2]. There are two rates, which are baud rate Rs and bit

rate R in "munication network. Baud rate means the

transmitted symbols per second, and bit rate the transmitted

bits per second. The relation between the two rates is :

'11

R = R,xb,

(4)

where b stands for modulation level. By varying

modulation level b, we can achieve tradeoff between

energy and delay. According to (4), the time to transmit

one bit can be reckoned:

0'4

T, =-=-

1'0

1'2

1'4

1'6

1'8

2'0

R,xb

Delay Per Bit (us)

The energy to transmit one bit using Quadrature

Ahplitude Modulation (QAM) is given by [2]:

Fig. 4. Energy versus Delay in dynamic modulation scaling

111.

AN ENERGY EFFICIENT SCHEDULE FOR WIRELESS

TERMINAL

2b -1

+c, x-

EE, =CSx-

A. Schedule Algorithm

Fig. 2 presents the logic structure diagram for a channel

state dependent energyefficient schedule model. The

schedule policy is made up of four parts, namely, the

packet arrival process, the scheduler, the channel monitor

and the packet departure process. The essential point of the

schedule policy is how to match the speeds of multiple

input queues and multiple output queues at the same time

considering the channel state.

When each packet enters the queue, the corresponding

rate will be calculated. Algorithm 1 and Algorithm 2 gives

the detailed the calculation process, and Algorithm 3 gives

the schedule algorithm

Algorithm 1: Algorithm for packets enqueing

Enqueue(I,P), i :stream identifier , P : Newly arrived

The first item of (6) gives the energy consumed in the

radio front-end for generating the electro-magnetic waves

that carry the information. Parameter CS depends on the

radio implementation, the wireless channel, the transmit

distance, and the required error performance. Strictly

speaking, it is also a function of b, but a very weak one [7].

The rest of the radio energy consumption is lumped into

the second term of (5), where CE depends on the radio

implementation. Although (5) is only exact for even integer

values of b, it is also a reasonable approximation when b is

odd. In addition, a packet can be split into two parts, each

with a different modulation. In this case, the average

energy and delay per bit for the packet as a whole are a

linear interpolation between the corresponding values of

the two modulation levels.

packet:

TABLE 11.

BASIC PARAMETERS FOR MODULATION SCALING

1 : Add-to-queue-at-tail

(Qi,P); //packet enters the

Parameter

Value

queue

lOOnJ

2: Total-rate=&-calc-total-rate();//recalculate

the

I 180nJ

instant rate

3: return;

Algorithm 2: Computing for instant rate

Re-c alc-total-rate0 :

1: calculate:

Table I1 lists the basic parameters for DMS used by (4),

(5) and (6). According to these basic parameters, Figure 4

plots the energy versus delay. Figure 4 shows the operating

points that correspond to real constellations and those that

are obtained through interpolation. From Figure 4, it's

clear that the more the energy to transmit one bit, the less

kxLi

r. =

Vk E {I, ..., m} ;

A,, +A-r

862

Authorized licensed use limited to: Politechnika Lodzka. Downloaded on January 14, 2010 at 20:13 from IEEE Xplore. Restrictions apply.

,&/c

//Li for the length of Queue i;

2: calculate:

P = I=I

Similarly, define the channel availability for error

channels as

T{ Good)

T(Good} + T{Bad)

(9)

’

In which T{Good} stands for the time when channel is

in Good State, while T{Bad} for the time when channel is

in Bad state. According to (7) and (8), we can define the

channel utilization for error channels as

5: returnR;

Algorithm 3: ScheduleAlgorithm

Schedule():

1 : select-a-packet-from-queue();

2: if (channel is BAD)

3: delay-some-time();

4 adjust-total-rate();

5 : transmit-the-packet ();

6: delete-the-packet-from-queue();

There are a lot of parameters to explain, in which Ai,k

stands for the k’th packet arrival time of queue i; A for the

max delay for all packets, i.e. all packets must leave the

queue in A ; T for the current time of the system.

The schedule simulates WFQ, and selects a proper

packet each time. Before sending the packet, the schedule

will decide whether to delay sending the packet according

to the channel state. If the packet is delayed, after that the

schedule will adjust the current sending rate. Then transmit

the packet according to the current instant rate, and finally

delete the packet from the queue.

Theorem 2: For error channels, if P *<1, then (7) still is

true; but when P * approaches 1, the system is not in stable

state, esp. the delay ranges wide, and it’s hard to express

the delay limit.

IV. SIMUNATION

RESULT

In order to verify our scheme, plenty of experiments are

done to obtain data. Below the simulation framework and

results will be presented.

A. Simulation Environment

PARSEC (Parallel Simulation Environment for

Complex System) [12] is used to simulate the model.

PARSEC is a C-based discrete event simulator, in which

logic process stands for objects or object sets and the

interaction between objects are implemented by time-

stamped messages exchanged between logic processes.

PARSEC provides message sending and receiving

mechanisms, and makes the program more like natural

language. At the same time, it uses several asynchronous

simulation protocols to separate the model description and

realization. Table III lists key parameters for experiments.

Delay Analysis

The max delay for a packet to transmit over an error-

free channel is give by [6]:

TABLE 111.

KEY PARAMETERSFOR EXPERIMENTS.

Parameter

Lmax

Value

In which LmadCmin stands for the max packet

transmission time. Notice that the upper bound for an

error-free channel can be reached only when the utility of

the system approaches 1.

However for an error channel each packet will be

delayed according to the above schedule algorithm, and the

delay equals to the time when channel is in Bad state.

Suppose the Gilbert model in Section 2.4 are used, and the

delay time satisfies the uniform distribution and the

average delay time is LmdCrnin.

Define the channel utilization for error-free channels as

IOOObit

2mps

200ms

Nb*lOO for every 1000 packets

863

Authorized licensed use limited to: Politechnika Lodzka. Downloaded on January 14, 2010 at 20:13 from IEEE Xplore. Restrictions apply.

xi). There are two observations from that can be made from

this figure: (1) when the link utilization is less: than 1, the

delay distribution center around 50 ms and the packet

number with delay great than Di* is zero; (2) the value of

Nb directly influences the delay distribution. When Nb

equals to 0, the delay distribution centers around and is less

than 50 ms; and when Nb equals to 12!, the delay

distribution disperses and the max delay is 200 ins.

In fig. 5(b) and 6(b), according to (6) we can calculate

the energy for max transmission rate. Given the link

utilization and the burst size of Nb, we can use the Model

to calculate the energy consumed by each packet. Then the

normalized energy ( a) can be expressed by (1 1):

Key Simulation Result

The simulation is shown in Fig. 5 and 6, and Fig. 5

stands for ideal channels while Fig. 6 for error channel.

a) Delay distribution of data packets

“I

o = Cei/ZEi = Cei KxEi

(11)

i ::

J 0.4

Where K indicates the total number of packets.

1) , DMS can decrease energy consumptionefectively

As seen from Fig. 5(b) and 6(b), when the link

utilization approaches 1, there are no difference between

two sending schemes: one with DMS deployed and another

with max transmission rate; but when the link utilization is

less than 1, esp. when the link utilization is light, there are

sharp difference between two schemes. For example, when

the link utilization is less than 50% and Nb equals to 0,

only 20% of energy is used for DMS compared to max

sending rate scheme.

0.4

0.0

0.7

Llnk utwzallon

b) Energy consumption of data packets

Fig.5. Energy and Delay for error free channels

burst

characteristics

influence

the

schedule

loo 1

perjiormance greatly

Nb measures the burst characteristics of data streams.

When Nb has a big value, the burst of data stream is very

sharp; while Nb a small value, the burst smooth. As seen

from Fig. 5(b) and 6(b), when the link utilization is at the

same level, if the stream has a big Nb value, then energy

consumed will be more correspondingly. And if the

stream’s Nb equals to 0, then the energy consumed will be

the least.

r~l. 111118. mm. --, __. .

100 . 125 150 . 175 200 . 225 . 250 275

Deal y (ns)

error rate

channels

affect

the

schedule

a) Delay dstribution of data packets

perjiormance.

Given two streams have the same link utilization kd

burst characteristic Nb, the energy consumed for each

packet will increase with the channel error rate. Table IV

shows energy versus delay with P *=0.6 and Nb=6: It’s

clear that the average delay and the average energy

consumed increase as the channel error rate increases.

TABLE IV. ENERGY “US

DELAYWN P +=0.6 ANDM

Link Ulilizelion

avg. delay per

Channel

error rate

0.05

0.1

0.15

avg. energy per

packet( P J).

21 19.25

2191.32

packet(ms)

46.54

b) Energy consumption of data packets

Fig.6. Energy and delay for error channels

In Fig. 5(a) and 6(a), the bar at x = 8 stands for the

percentage of packets whose delays lie in the interval (%-I,

2261.12

58.18

2334.83

864

Authorized licensed use limited to: Politechnika Lodzka. Downloaded on January 14, 2010 at 20:13 from IEEE Xplore. Restrictions apply.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: