International Journal of Computer Networking, Wireless and Mobile Communications (IJCNWMC) ISSN 2250-1568 Vol.

3, Issue 1, Mar 2013, 27-38 TJPRC Pvt. Ltd.,

ENERGY EFFICIENT BANDWIDTH RESERVATION MODEL USING CYCLIC FLOWS IN WIRELESS NETWORKS
A.ANITHA1 & S.SHERIN LIBA2
1

Professor/CSE,PET Engineering College, Tirunelveli, TamilNadu-627117, India

2

PET Engineering College, Tirunelveli, TamilNadu-627117, India

ABSTRACT
Wireless networks are of broadcasting nature. Transmissions from nearby nodes interfere with each other. Quality of Service (QoS) is a set of technologies for managing network traffic in a cost effective manner. The goal of QoS is to provide guarantees on the ability of a network to deliver predictable results that the users and services are provided with enough network bandwidth to ensure that the data is delivered with minimal delay and packet loss. Reservation-based channel access in WLANs provides predictable and deterministic transmission. Reservation-based channel access is energy efficient since a wireless adaptor is powered on only during its exclusive channel access times. This work aims at finding the minimum channel bandwidth reservation that meets the real-time constraints of all periodic streams of a given node. Bandwidth reservation of each node to a minimum lead to reduced energy, resource requirements and leaves more bandwidth for future reservations by other nodes. To minimize the bandwidth reservation problem at a given node, the proposed work uses sleeping mechanism and time slicing mechanism. Generic algorithm is used in the periodic packet scheduling process. Fixed-clients, Fixed-bandwidth and First-In-First-Out policies are used in the bandwidth reservation process.

KEYWORDS: Bandwidth Reservation, Time Slicing, Wireless Network INTRODUCTION

Wireless embedded real-time systems are becoming prevalent with the continuous increase in streaming applications such as video/audio communications, mobile gaming, and wireless sensor and actuator networks. This is used for research efforts to enhance the support of timeliness and Quality of Service in wirelessly networked embedded environments. Existing Contention-based media accesses such as Carrier Sense Multiple Access (CSMA) are nondeterministic and thus incapable of providing predictable QoS support to periodic communications often found in wireless real-time systems. In existing system, multiple nodes are active simultaneously, continuously sense and contend for the shared media, leading to excessive energy consumption. A. K. Mok, X. A. Feng, investigate an approach to implement open system environment idea by means of temporal resource partitions [3]. Because the existing work implements the application task groups with hard timing constraints, may share the same physical resource and yet be free from interference with one another. Each resource partition uses a fraction of time partition. Partitions are specified by two models, a static partition model and a bounded-delay model. Both models achieve a clean separation of concerns between task group and resource level partition scheduling. The schedulable problems for both preemptive fixed and dynamic priority scheduling policies is described by the author. The disadvantages of this approach are the scheduling policy of each task group and exclusive access to a resource. The different task groups

28

A.Anitha & S.Sherin Liba

may conflict with one another. Infinite time slicing is impractical because of the context switching overhead costs and resource specific constraints. D. Rajan, C. Poellabauer and et.al proposed reservation-based channel access forproviding Quality of Service guarantees in wireless embedded real-time applications [13]. This work addresses this issue by presenting a strategy for nodes to determine minimal resource reservations that guarantee the real-time constraints of their network traffic. The disadvantages of this work are requirements has largely been ignored which has often resulted in poor real-time support, Overprovisioning of valuable resources and poor scalability. Therefore, such access mechanisms are ideally suited for providing real-time servicesin wireless environments. Reservation-based channel management requires each node to negotiate its desired channel access duration for a given period based on its traffic constraints. The goal of this work is to develop a strategy for the computation of the channel access reservations required for a given packet scheduling policy, such that (i) the real time constraints of each nodes traffic are satisfied and (ii) Resource reservations are minimized. Accordingly, the scheduling policy for the extended stream set is extended from the original scheduling policy for the original stream set such that (a) The sleep stream always has the highest priority and is non-interruptible and (b) The priority relationship among the original stream set is unchanged. As a consequence, the minimum bandwidth reservation problem has to be transformed to the maximum sleep time problem. Based on supply/demand analysis, a generic algorithm is developed to compute the maximum sleep time for a subclass of priority-driven packet scheduling policies namely, fixed-clients, fixed-bandwidth and FIFO. This subclass exhibits two properties: (1) the scheduling policy is static at the client level but can be either static or dynamic at the task level (2) the scenario of the worst-case response time of the stream set occurs within the synchronous busy interval of the stream set, i.e., if all stream instances released within this interval meet their deadlines, then all stream instances will meet their deadlines everywhere. The main contributions of this paper are (1) the transformation of the problem of periodically reserving a time interval of minimum length to serve all real-time streams; and (2) present an alternative solution to this problem by applying an augmented supply/demand analysis on the transformed problem in an efficient manner.

LITERATURE SURVEY
In networking environments, reservation-based mechanisms are becoming highly prominent in supporting latencycritical and energy-aware traffic. In this section, existing protocol standards and techniques related to resource and channel access reservations are discussed. The problem of reducing the time complexity ofWorst case response times must be determined repeatedly during the interactive design of real-time application systems, repeated exact computation of such response times would slow down the design process considerably. O. Redell and M. Torngren,identified three desirable properties of estimates of the exact response times: continuity with respect to system parameters, efficient computability, and approximability [6]. Estimating the worst-case response time of sporadic task systems that are scheduled using fixed priorities upon a preemptive uniprocessor usability tests has

Energy Efficient Bandwidth Reservation Model Using Cyclic Flows in Wireless Networks

29

been largely addressed by the real-time research community. Discontinuities are a major problem to a process of incremental interactive system design. Ideally, such a design process would allow for the interactive exploration of the state space of possible designs; this would be greatly facilitated if making minor changes to a design results in minor changes to system properties. Any such continuous upper bound on response time is necessarily not tight since, as stated above, worst case response time is itself not continuous in the system parameters. Hierarchical CPU scheduling has emerged as a way to Support applications with diverse scheduling requirements in open systems, and Provide load isolation between applications, users, and other resource principals.

X.A.Feng and A. K. Mok,describe a system of guarantees that permits a general hierarchy of soft real-time schedulers [5]. This analysis results in deterministic guarantees for threads at the leaves of the hierarchy.Hierarchical Loadable Schedulers (HLS) is a system that supports composition of scheduling behaviors using hierarchical scheduling, as well as the ability to provide guaranteed scheduling behavior. The disadvantages are granularity is inefficient and scheduling is particularly difficult when the demand for one or more resources exceeds the supply. The time-sharing scheduler makes no particular guarantees to entities that it schedules. The real-time scheduler cannot predict when it will receive CPU time. In most real-time applications, deadlines are artifices that need to be enforced to meet different performance requirements. H.Hoang, G. Buttazzo and et.al present a method for calculating the minimum EDF- feasible deadline of a real-time task [10]. The proposed algorithm allows computing the shortest deadline that can be assigned to an arbitrary task in the set, or to a new incoming task, still preserving the EDF feasibility of the new task set. Their approach is based on the processor utilization; hence, it cannot find the shortest possible deadline. The problem of multiprogramming scheduling on a single processor is studied from the viewpoint of the characteristics irregular to the program functions that need guaranteed service. C. L. Liu and J. W. Layland present the technique that an optimum fixed priority scheduler possesses an upper bound to processor utilization [1]. It describes the full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed namely mixed scheduling policies and fixed priority scheduling policies.A scheduling algorithm is a mixed scheduling algorithm means if the priorities of some of the tasks are fixed yet the priorities of the remaining tasks vary from request to request. Two factors occur in the fixed scheduling

policies, that is deadline and critical instant. The deadline of a request for a task is defined to be the time of the next request for the same task. A critical instant for a task is defined to be an instant at which a request for that task will have the largest response time. A critical time zone for a task is the time interval between a critical instant and the end of the response to the corresponding request of the task.

PROPOSED SYSTEM
The goal of this work is the computation of the required channel access reservations for a given packet scheduling policy, such that (i) the real-time constraints of each nodes traffic are satisfied. (ii) Resource reservations are minimized. The minimum bandwidth reservation problem is transformed to the maximum sleep time problem, which is then solved by computing the schedulable execution time of the sleep stream for a subclass of scheduling policies. This section discuss about the bandwidth reservation, network access model, traffic model, transformation the scheduling model, minimum bandwidth reservation.

30

A.Anitha & S.Sherin Liba

Figure 1: Block Diagram for the Bandwidth Reservation

Bandwidth Reservation In this section, the network throughput/performance is measured. Total Bandwidth of the network in which the analysis is to be done.Bandwidth is a measure of how fast information is transferred on other network. Network bandwidth is defined as the total data capacity that can be handled by a data connection. Bandwidth on a network is defined in bits/second (bps).In a network data is send sequentially to avoid collision. For example, a 10Base network has total capacity of 10 Megabits/sec (Mbps), and a 100 Base network has a total bandwidth capacity of 100 Mbps. The data stored in computers are measured in Bytes rather than bits. There are 8 bits in a byte, but when data is transferred on a network there is also overhead that takes up some of the bandwidth available. Inorder to calculate this bandwidth italso makes all the computations easier. To get some idea of the bandwidthrequired first need to understand the size of the file used by various types of information. A Word document contains about 30 50 Kbytes of data. This document, which contains pictures, contains about 110 Kbytes. The time to transfer this document from one computer to another on the network is very short, because it doesnt contain a lot of data. Inorder to calculate bandwidth utilized,bytes are converted to bits (10 X 110 Kbytes = 1100 bits). If I have a 100 Mb/sec network (and this is the only data transfer occurring), it takes 1100 Kbits/100,000 Kbits/sec = 0.011 seconds to transfer the document. Network Access Model In a reservation-based channel access mechanism, each node is provided a Service Period ( ), during which the

node has exclusive access to the wireless medium. Polling frames issued by the BS specify the start time and maximum duration of the allotted to a node. At the end of an for a node, the BS begins polling the next node in its schedule. The period of recurrence of the is referred to as the Service Interval ( ), which is usually specified by the BS in advance

Energy Efficient Bandwidth Reservation Model Using Cyclic Flows in Wireless Networks

31

and equal to a multiple of the beacon interval of the BS shared by all client nodes. We call the pair bandwidth profile of a node.

the

Figure 2: Wireless Devices Network Model (SP, SI),SP-Service Period, SI-Service Interval

This reservation-based channel access model is very practical and valuable in both wireless local area networks (WLANs) and wireless sensor networks (WSNs). Traffic Model This work investigates the impact of traffic scheduling policies on bandwidth reservation from the perspective of a single node. The policies under consideration are a subclass of priority-driven polices, and assumes there is a shared queue for all released packets. The priority-driven scheduling policies under consideration includefixed-priority policies and dynamic-priority policies. A set of wireless nodes with applications on each node is considered for generating one or more periodic real-time streams. Nodes connect wirelessly to a common BS to access an external network. Wireless channel conditions are time-varying and error-prone. Each datagram of Si has a relative transmission completion deadline Di. The release time and deadline of are denoted as and = +Di, respectively. Therefore, a datagram can be also treated

as a logical collection of a series of physical packets. The maximum size of packets cannot be greater than the MTU. During the sleep duration, more packets that are urgent may arrive at the network queue. When the network resource is available again, the scheduler may need to transmit these newly arrived urgent packets before the transmitted packets.

Figure 3: Traffic Model

Transforming the Scheduling Model To approach the MBR problem, first transform the scheduling model another scheduling model policy where the stream set of the MBR problem to

extends by adding a sleep stream; the scheduling represents the dedicated resource allocation

extends A by assigning the sleep stream the highest priority; and

for S. M is schedulable if and only if

is schedulable. As a corollary, show that the MBR problem in M is a dual of the .Maximum Execution Time (MET) is calculated using the first

maximum execution time problem of the sleep stream in in first out policy.

Figure 4: BW Profile for Original Stream

32

A.Anitha & S.Sherin Liba

Figure 5: Transformed BW Profile for Adding Sleep Stream

Minimum Bandwidth Reservation In systems that use dynamic job-level scheduling, a datagram (a client) may consist of multiple packets, whose priorities may be different from each other or they may change over time. This, while adding flexibility, would significantly add to the complexity of the network scheduler. Instead, this work assumes that the network schedule is client-level static, i.e., all packets from the same datagram have the same priority, which is assigned at the release time of the datagram. A priority-driven scheduling policy (a set of priority rules) can be considered as a time-varying function for any two clients and , taking on values -1, 0, and 1. A synchronous busy interval of the

stream set starts with all streams generating their datagrams at the same time and ends with the transmission of the last one of these datagrams. The above discussed two constraints are stated explicitly as follows. Client-level static: The scheduling policy is static at the client level, but it can be either static or dynamic at the task level. Critical instant: The worst-case response time of any given stream set by a given scheduling policy occurs within the synchronous (in-phase) bus interval of the stream set. Generic Framework for MET Problem This framework distinguishes between the finished portion and the unfinished portionof execution before a given deadline. This concept allows to conservatively reducing the sleep time of the sleep stream to approach its minimum value, assuming that the reduced sleep time (equal to the unfinished portion) is solely utilized by the client missing its deadline.To compute the finished/unfinished portions of a client, define a generic time-demand function at every client release event point. The available time at a client, release event point for lower-priority clients is equal to the dedicated time supply minus the generic time demand. As a result, the finished portion of a client before its deadline is equal to, provided it has not finished, the maximum available time over all client release event points between its release time and its deadline. This approach avoids iterative computations of fixed-point equations. Algorithm 1.First sleep stream execution time ( reservation for S'. 2. Scan every job in increasing order of release times or deadlines in the busy interval time period. 3. For each job compute the finished portion , unfinished portion and the completion time 4. If unfinished portion >0 means decrement the execution time of S0. 5. Otherwise abort when it is impossible to meet the jobs deadline even if the node were allocated the entire bandwidth (i.e., SP=SI). 6. If<0 means abort the job.
i,j

) is initialized to the maximum value since the goal is to minimize bandwidth over-

Energy Efficient Bandwidth Reservation Model Using Cyclic Flows in Wireless Networks

33

7.Determine if the synchronous busy interval is terminated or whether it is impossible to meet the jobs deadline even if the node were allocated the entire bandwidth. 8. If overall completion time the jobs. This framework scans every client within the synchronous busy interval to check if it meets its deadline. The timeliness checks of the clients of S0, referred to as sleep clients in the remainder of the paper, are temporarily skipped until the synchronous busy interval ends. Consider the execution of each clientto be divided into two distinct portions: the finished portion + , and the unfinished portion (1)
j

is satisfied, move on to check next job and perform the same steps for all

(2)

before the deadline. If client misses its deadline, the execution time will be reduced such that the total amount of reduced execution times of all sleep clients before is equal to Scheduling Policies In this section, the three scheduling policies are first-in-first-out, fixed Clients, and fixed Bandwidth First-In-First-Out All the clients are waiting in a queue, data is sent to each client one at a time, at maximum bandwidth (BW). This module specifically is used to benchmark the performance of the network. In FIFO, only clients released no later than clienthave higher priority than .At a time, only one client is connected and data is transmitted. The files are sending .

sequentially. The total times to send files are equal to the sum of net sleep time and the execution time. The BW is calculated for one client is, (3) Therefore, the total number of clients is calculated is function, and completion time function is, = =
i , j=

.The time-demand function, finished/unfinished portion

(4) (5) (6)

Fixed Bandwidth In this fragment, transfer is done only when a minimum bandwidth (BW(SP,SI)) is met. Minimum bandwidth is assigned for each client . Other clients will wait in a queue as in FIFO.Total number of clients denoted as , the

number of clients will be varying depend on the BW. When the current bandwidth for any client is less than the given BW, the number of clients is decremented, i.e.; one of the clients is disconnected. Equation (7) is calculated for bandwidth. (7)

34

A.Anitha & S.Sherin Liba

Therefore, (8) The time-demand function, finished/unfinished portion function is,

+ +

(9)

=
Fixed Clients

(10)

In this fragment transfer is done only to a specific number of clients at maximum possible. Maximum m numbers of clients are assigned previously; other clients will wait in a queue as in FIFO. Here BW is not considered under any circumstances numbers of clients are connected parallel and data is transmitted. So minimum BW for each client is calculated as the total BW is divided into number of clients. The time-demand function, finished/unfinished portion function is,

+ +

(11)

=
EXPERIMENTAL RESULTS

(12)

This result shows the impact of varying SI on the over-reservation ratio (E).The over-reservation ratio E is defined as the normalized ratio of the bandwidth reservation to the idealized minimum utilization U= .That is,E= .

Thus, E=1 means that all reserved bandwidth is used and no bandwidth is wasted. Increasing SI significantly impacts the over-reservation ratios of Fixed Client, Fixed Bandwidth and FIFO.The results derived from the simulation experiments reveal the following. (1) Increasing the validitycan greatly increase the bandwidth usage efficiency and increase the probability of successful bandwidth reservation. When the validity goes beyond 4.5, the advantageof using complex scheduling policies diminishes and their minimum bandwidth reservations converge.In this case, FIFO works perfectly considering its low system overheadand scheduling complexity. Similarly, decreasing the given value has a similar effect as increasing the validity. The

important point is notes as varying the service period and bandwidth depending upon the file size is to be transferred. For example, 2.5KB size file is transferred to the computer means; it is converted to bytes/datagram i.e. 2654bytes. The Service Interval is given 400sec.So the bandwidth is calculated for sending file is 6.6Kbps.So, the finished and unfinished portion is calculated for FIFO, fixed clients, fixed bandwidth is shown in table 1.

Energy Efficient Bandwidth Reservation Model Using Cyclic Flows in Wireless Networks

35

Table1: Finished and Unfinished Portion

Service Interval(Sec)

Finished Portion(Kbps)

Unfinished Portion(Kbps)

0 50 100 150 200 250 300 350 400

0 330 660 990 1320 1650 1980 2310 2640

6.6 2324 1994 1664 1334 1004 674 344 14

Figure 6: Comparison Finished and Unfinished Portion The Over-reservation Ratio is calculated for the following steps: Step1.The utilization Period is calculated

Same like fixed clients and fixed bandwidth is calculated the values are Fixed Clients U=0.7, Fixed Bandwidth U=0.5. Step2.The Service Period and over-reservation ratio values for FIFO, Fixed Clients, Fixed Bandwidth is shown table 2 Table 2: Service Period and Over-reservation Ratio

Service Period Service Interval(Sec) Fixed Clients(Sec) Fixed Bandwidth(Sec) FIFO(Sec) Fixed Clients(Sec)

Over-Reservation Ratio Fixed Bandwidth(Sec) FIFO(Sec)

50 100 150 200

13 24 36 48

13 28 51 92

18 42 72 108

0.3 0.3 0.3 0.3

0.3 0.4 0.5 0.9

1.2 1.4 1.6 1.8

36 Table 2: Contd., Service Period Service Interval(Sec) Fixed Clients(Sec) Fixed Bandwidth(Sec) FIFO(Sec)

A.Anitha & S.Sherin Liba

Over-Reservation Ratio Fixed Clients(Sec) Fixed Bandwidth(Sec) FIFO(Sec)

250 300 350 400

60 72 98 120

125 180 238 280

155 210 259 312

0.3 0.3 0.4 0.3

1 1.5 2.2 2.3

2 2.3 2.4 2.6

Figure7: Comparison of Bandwidth Reservation

CONCLUSIONS AND FUTURE WORK

This work provides contention-free access within allocated/reserved channel access intervals to meet timing constraints predictably. They allow a wireless radio to be powered down when the channel is not needed. Resource reservations are minimized it can be used to determine the minimum resource requirements of an application, given this applications local scheduling policy (fixed clients, fixed bandwidth and FIFO).Transform the minimum bandwidth reservation problem to the maximum sleep time problem for minimizing the bandwidth reservation is equivalent to maximizing the sleep time of the sleep stream. It supports latency-critical and energy-aware traffic. The proposed bandwidth reservation scheme leads to minimal amounts of bandwidth waste if appropriate scheduling policies and stream parameters are selected for a given stream set. However, it also leads to potentially large energy savings, while being simple to implement and deploy. In the future work 1) Encryption of Packets to prevent eavesdropping. 2) Compression of data using gZip for conserving bandwidth can be addressed.

REFERENCES
1. C. L. Liu and J. W. Layland, Scheduling algorithms for multiprogramming in a hard-real time environment, Journal of the ACM, vol. 20, no. 1, pp. 46-61, 1973. 2. K. Mok and X. A. Feng, Towards compositionality in realtime resource partitioning based on regularity bounds, Proceedings of the 22nd IEEE Real-Time Systems Symposium. Washington, DC, USA, IEEE Computer Society, 2001, p. 129. 3. K. Mok, X. A. Feng, and D. Chen, Resource partition for realtime systems, Proceedings of the Seventh RealTime Technology and Applications Symposium. Washington, DC, USA, IEEE Computer Society, 2001, p. 75.

Energy Efficient Bandwidth Reservation Model Using Cyclic Flows in Wireless Networks

37

4.

J. Regehr and J. A. Stankovic, HLS: A framework for composing soft real-time schedulers, Proceedings of the 22nd IEEE Real-Time Systems Symposium, London, UK, Dec. 2001, pp. 3-14.

5.

X.A.Fengand A. K. Mok, A model of hierarchical real-time virtual resources, Proceedings of the 23rd IEEE Real-Time Systems Symposium. Washington, DC, USA, IEEE Computer Society, 2002, p. 26.

6.

O. Redell and M. Torngren, Calculating exact worst case response times for static priority scheduled tasks with offsets and jitter, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium, Washington, DC, USA, 2002, p. 164.

7.

Shin and I. Lee, Periodic resource model for compositional real-time guarantees, Proceedings of the 24th IEEE International Real-Time Systems Symposium. Washington, DC, USA, IEEE Computer Society, 2003, p. 2.

8.

W. Ye, J. Heidemann, and D. Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Trans. Netw., vol. 12, no. 3, pp. 493-506, 2004.

9.

IEEE 802.11 WG, Part II: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications: Medium access control (MAC) enhancements for quality of service (QoS), IEEE 802.11e Standard, Nov 2005.

10. H.Hoang, G. Buttazzo, M. Jonsson, and S. Karlsson, Computing the minimum edf feasible deadline in periodic systems, Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Washington, DC, USA, 2006, pp. 125-134. 11. Easwaran, M. Anand, and I. Lee,Compositional analysis framework using edpresource models, in Proceedings of the 28th IEEE International Real-Time Systems Symposium. Washington, DC, USA, IEEE Computer Society, 2007, pp. 129-138. 12. F. Zhang and A. Burns, Analysis of hierarchical edf pre-emptive scheduling, Proceedings of the 28th IEEE International Real-Time Systems Symposium. Washington, DC, USA, IEEE Computer Society, 2007, pp. 423434. 13. D. Rajan, C. Poellabauer, X. S. Hu, L. Zhang, and K. Otten, Wireless channel access reservation for embedded real-time systems, Proceedings of the 7th ACM international conference on Embedded software, Atlanta, GA, USA, 2008, pp. 129-138. 14. F. Zhang and A. Brns, Schedulability analysis for real-time systems with edf scheduling, IEEE Transactions on Computers, vol. 118, no. 1, pp. 100-120, 2009. 15. N. Fisher and F.Dewan, Approximate bandwidth allocation for compositional real-time systems,Proceedings of the 21st Euromicro Conference on Real-Time Systems. Washington, DC, USA, IEEE Computer Society, 2009, pp. 87-96.