Performance Evaluation of Adaptive Weighted Scheduling Scheme in Wireless Sensor Networks

Performance Evaluation of Adaptive Weighted Scheduling Scheme in Wireless Sensor Networks

Performance Evaluation of Adaptive Weighted Scheduling Scheme in Wireless Sensor Networks

S.Vanithamani, P.G Student

Department of ECE

M. Kumarasamy College of Engineering Karur, India

vanithas.karur@gmail.com

N.Mahendran, Assistant Professer

Department of ECE

1. Kumarasamy College of Engineering Karur, India

   mahendrann.ece@mkce.ac.in

   AbstractWireless Sensor Networks (WSNs) are visualized in military, emergency, habitat monitoring and process monitoring applications. Wireless sensor networks employ a huge number of sensor nodes, which is used to collect the information from sensing environment. The objective of the paper is to reduce the end to end delay, energy consumption of sensors and average waiting time in WSNs. Dynamic Multilevel Priority (DMP) scheduling was used in wireless sensor network in which sensor nodes organized into a hierarchical structure. DMP scheme utilizes three levels of priority queues which are used to schedule the data packets based on priorities. In that scheduling scheme real-time packets are given highest-priority queue and non-real- time packets are placed into two other queues. High priority queues can preempt datas from other queues. In this paper, we proposed an Adaptive Weighted Scheduling Scheme. In this scheme scheduling weights of Behavior is changed adaptively by adjusting the weights based on the average queue size of premium service. Simulation results demonstrate that the Adaptive weighted scheduling scheme performs better than DMP scheduling scheme in terms of end to end delay and average waiting time.

   KeywordsWireless sensor networks, dynamic multilevel priority scheduling, adaptive weighted scheduling, real time, non real time.

   1. INTRODUCTION

      Wireless sensor networks (WSNs) consist of huge number of low power, inexpensive and intelligent sensor nodes which deployed over a geographical area. Sensor nodes have a limited energy supply and deployment of these nodes is based on highly redundant manner [1]. The sensor nodes can perform many functions such as sensing, processing and communicating with other nodes in the network. These nodes are having one or more sensors, processor, memory, power supply and a radio. Sensor nodes perform the sensing task by turns [2]. Thus sensor scheduling gets more importance by extending the network life time of the wireless sensor network. To achieve the long life of sensors in WSN should be consumed by low energy with allocated time slot [3]. Power consumption of nodes are increased by the sleeping and awakening of sensors based on availability of data. The nodes are not involved in transmission usually in sleep mode to conserve the energy. WSN has many applications such as environmental sensing, military surveillance, inventory tracking, smart spaces, process monitoring and healthcare monitoring systems [4]. Figure 1.1 describes the basic architecture of the wireless sensor network. Sensor nodes communicate with each other and collect the information from environment; sometimes nodes directly send the information to

      base station where base station acts as a gateway. Base stations receive the information from nodes and forward to server.

      Fig 1.1 Architecture of Wireless Sensor Network

      Scheduling is the process of deciding and how to assign the resources between selection of possible tasks. A scheduling algorithm consists of three basic characteristics such as resource sharing, performance, and computational complexity. The resource sharing represents how the general resources are shared between the users, the second one is a quantitative measure of the quality of service, and last one deals with its practical implementation [5]. The main criteria for a good scheduling algorithm depend on the following factors such as fairness, waiting time, response time, turnaround time and throughput [6]. By using the above factors we can improve the network performance. Packet scheduling refers to the decision process which is used to select the packets should be serviced or dropped. Dropping packets should be based on network characteristics like bandwidth, packet arrival rate, deadline of packet and packet size. If the packet rate is high and the bandwidth is too low the scheduler will find it difficult to handle all the incoming packets [7]. Packet scheduling ensures that packets which is transmitted from a queue buffer. Scheduling of real time and non real time packets at sensor nodes will reduce end to end transmission delay, saves energy consumption and also increase network life time. For instance, real time applications are assigned in highest priority queues than non- real time applications [8].

      Dynamic Multilevel Priority (DMP) [9] packet scheduling scheme for WSNs in sensor nodes are almost organized into a

      hierarchical structure. Nodes have the same hop distance from the BS are measured to be located at the same hierarchical level. Data packets are sensed by nodes at different levels which are processed using a TDMA scheme. Real-time packets are assigned into highest-priority queue and can preempt the data packets in other queues. Non-real-time packets are assigned into two other queues based on an estimated processing time. In this paper, we propose an Adaptive Weighted Scheduling scheme for WSNs. This scheduling scheme is used to change the scheduling weights of Behavior Aggregates which adaptively adjusting the weights according to the dynamics of the average queue size of premium service. It ensures minimum end-to-end delay, waiting time, and increase the network lifetime of WSNs.

      The remainder of the paper is organized as follows. In section II, we discuss several existing WSN scheduling algorithms. Section III describes the proposed Adaptive weighted scheduling scheme. Section IV evaluates the performance of the Adaptive weighted scheduling scheme through simulations and finally, concludes the paper in section V.

   2. RELTED WORK

      In this section, we present existing packet scheduling schemes which are classified based on several factors.

      Most of the existing Wireless sensor Network (WSN) applications use first come first serve (FCFS) schedulers that simplify the processing of data in the order of their arrival times at ready queue. In FCFS, data from intermediate nodes of the network that arrives late from distant leaf nodes and require a lot of time to be delivered to base station but data from nearby neighboring nodes are take less time to be processed at the intermediate nodes. In FCFS, many data packets arrive late and have a long waiting time. The advantages of FCFS include simplest form of scheduling algorithm, easy to implement and intrinsically fair [10].

      In fair scheduling, data packets are classified into flows by the system and then allocated to the queue. This queue is mainly committed to that flow. Queues are serviced of one packet at a time in Round Robin (RR) order and empty queues are rejected. Devavratshah et al [11] proposed a new algorithm in fair scheduling called most urgent cell first algorithm. In this algorithm packets are scheduled based on the maximum weight schedule with urgencies of queues weights. A Non empty queue is given new urgency than an empty queue. From this, a weight of an empty queue is less than or equal to weight of the non empty queue in the system. The fair schedule selected by the algorithm tries to minimize the number of empty queues it serves. Songwer Lu [12] proposed a new algorithm in fair scheduling to address the main problems of th wireless media such as bursty channel errors, location dependent channel capacity and errors. The BS typically performs the scheduling for both downlink and uplink flows in a cell. Fluid fair algorithm is to handle the location dependent error bursts.

      Jae Han Jeon [13] proposed end to end delay guaranteed scheduling algorithm, which guarantees the end to end delay based on delay parameter. With the newly created optimization problem is derived by using delay parameter and the average end to end delay requirements are guaranteed with improved network throughput performance. By deriving the

      end to end delay requirement guarantee the performance is increased by reducing the end to end delay.

      Jun Yi et al. [14] proposed minimum bandwidth reservation for periodic streams in sensor networks. The main advantage of this reservation based channel access is providing contention free access within allocated channel intervals to meet timing limitation. Fixed priority, earliest deadline first, first in first out are using this generic minimum bandwidth reservation algorithm and efforts based on a subclass of priority driven packet scheduling policies. Here the bandwidth reservation scheme leads to minimize waste of bandwidth when scheduling policies and stream parameters are given properly and also leads to energy savings and simple to implement.

      You-Chuin Wang et al [15] proposed a multi rate fair queuing algorithm (MR-FQ). The data transmission of data is based on both time fairness and service fairness. It allows a flow to transmit of data at different rates according to channel condition and lagging degree. MR-FQ follows the design in separating real-time flows from non real-time ones and compensates real-time lagging flows with higher priorities to reduce their delays. It increases overall system throughput and guarantees fairness and bounded delay for all flows.

      Gyula Simon [16] proposed wireless sensor network TDMA based routing schemes using RR where nodes form a multiple connected cycles. TDMA utilize periodic RR slotted communication where each period in identical and contains the schedule for each node in the network. In this method, the usage of different speeds in the main cycle and the sub cycles allows the design of sub networks with different delays and save energy utilization. It guarantees delivery times and long network lifetime due to the low duty cycle operation.

      Nidal Nasser et al [9] proposed a Dynamic Multilevel Priority (DMP) packet scheduling scheme. This scheme uses three-level of priority queues to schedule data packets based on their types and priorities. It ensures minimum end-to-end data transmission for the highest priority data and acceptable fairness towards lowest-priority data. Moreover, in FCFS and multilevel queue schedulers, the processing time of a task is not considered when deciding the priority of a task. DMP scheme gives the highest priority to real time (RT) tasks and also allows RT data packets to preempt the processing of non real time data packets. DMP packet scheduling scheme has better performance than the existing FCFS and Multilevel Queue Scheduler in terms of the average task waiting time and end to-end delay [9].

   3. PROPOSED WORK

      In this paper, we propose an adaptive-weighted packet scheduling scheme for premium service to support delay- sensitive traffic, which can be applied to weighted round robin and weighted fair queuing. The proposed scheme achieves low queuing delay apart from guaranteeing minimum waiting time.

      1. Working Principle

         The working principle of the adaptive-weighted packet scheduling scheme is illustrated in Fig 3.1. It is assumed that the scheduler state having the values Oi for all input queues is available to the base station at the beginning of each frame. This can be accomplished by sending to BS once per frame the

         queue size together with the bandwidth request messages for every established connection, as mentioned in [17].

         Adaptive weighted scheme include some features:

         • The average queue size of premium service, which is the index used for calibrating the weights is estimated using Exponential weight moving average (EWMA)

         • With respect to the dynamics of average queue size, the weight of premium service is adaptively adjusted. However, there is an upper limit by which the weight of premium service should be bounded; and

         • Low queuing delay is achieved by maintaining a very small average queue size. The fluctuation of instantaneous queue size is reduced by using low-pass filter, achieving low delay.

      Thus we employ the estimated average queue size of premium service as the index to adaptively adjust the weights with Random Early Detection (RED) [5]. a low-pass filter with an exponential weighted moving average is used to calculate the average queue size of premium service. Assuming as average queue size, Q is the instantaneous queue size and 1 is the low-pass filter, the average queue size of premium service is estimated as,

      avg (1-f1) avg + f1 × Q

      The low pass filter 1 is set to 0.01 in the proposed scheme to reduce the fluctuation of instantaneous queue size, which results in a low delay. Two thresholds (minimum and maximum) are introduced to adaptively calibrate the weight of premium service. The maximum threshold represents the acceptable queuing delay, and the minimum threshold represents the desired queuing delay. A low queuing delay is achieved by keeping average queue size below the maximum threshold. The weight of premium service should be proportionally increased once the average queue size exceeds the minimum threshold in order to achieve a low queuing delay.

      Fig 3.1 Adaptive scheduler

      TABLE I. SIMULATION PARAMETERS AND VALUES

      Parameters	Values
      Network Size	500m × 500m
      Number of Nodes	101
      Initial Node Energy	100 joules
      Sensing Period	1.0ms
      Packet Size	64 bytes

      The adaptive weighted scheduling scheme would temporarily degrade to priority queuing and lead to packet clustering if the weight of premium service cannot exceed an upper limit after the average queue size reaches maximum value [18].

      S1, S2 Sn (Si) = traffic sources for all Sub Stations (SSs) Q1, Q2Qn (Qi) = per source input FCFS queues Scheduler = distributed time slot scheduler (in all SSs)

      Oi = size of Qi

      Pi = priority of Si

      Li = number of uplink slots allocated to Si

   4. PERFORMANCE ANALYSIS

      The simulation model is implemented by using Network Simulator (NS2) tool. In our simulations, the sensor nodes are randomly distributed in 500m × 500m area. The number of nodes is 101 and the packet size is 64 bytes. It is used to analyse the performance of the Adaptive weighted scheduling scheme and comparing with DMP scheduling scheme. Table I presents the simulation parameters and values. The goal of our simulations is to evaluate the adaptive weighted scheduling in terms of end to end delay, average waiting time, energy consumption and network life time and compares its performance with those achieved by using DMP scheduling scheme in these simulation scenarios.

      Figs 4.1 and 4.2 illustrate the end to end delay and average waiting time of all data traffic over a number of zones respectively. By analyzing the results, Adaptive weighted scheduling scheme outperforms than DMP in terms of end to end delay and average waiting time. Figs 4.3 and 4.4 illustrate the energy consumption of sensors and network life time over a number of zones respectively. When compare to the DMP scheduler, the performance of the Adaptive weighted scheduling has been improved. As the number of zones increases, the energy consumption is reduced and the network life time is increased.

      Generally energy isconsumed, when a node transmits or receives data or performs data aggregation. A node goes to sleep mode, when more than 90% coverage area is covered by neighbour nodes. The network lifetime depends on energy efficiency and transmission capacity of nodes. One of the important criteria in our Adaptive weighted scheduling scheme is related to its energy requirement of nodes. Otherwise the Adaptive weighted scheduling scheme could be less energy efficient compare with DMP scheduling.

   5. CONCLUSION

In this paper, we have studied the problem for minimizing the network life time and maximizing the end to end delay, average waiting time of packets in wireless sensor network. Here we proposed an adaptive weighted scheduling scheme to achieve premium service where the scheduling weights of behavior aggregates are adaptively changed dynamically based on average queue size of premium service.

End to End Delay (msec)

0.005

0.004

0.003

0.002

0.001

0

DMP

Adaptive weight

5

0.4

0.35

0.3

0.25

0.2

0.15

0.1

0.05

0

Energy Consumption (joules)

DMP

Adaptive weight

Zone Size

10

9

8

7

6

5 6 7 8 9 10

Zone Size

DMP

60

50

40

30

Average Waiting Time (sec)

Fig 4.1: End to End delay of all types of data over a number of zones

Fig 4.3 Energy consumption over a number of zones

5 6 7 8 9 10

Zone Size

Adaptive weight

20

10

0

Fig 4.2 Average waiting time of tasks over a number of zones

180

160

Network Lifetime

140

120

100

80

60

40

20

0

DMP

Adaptive weight

5 6 7 8 9 10

Zone Size

It is able to absorb the traffic distortion inside network without reducing delay and provides accurate traffic conditioning and rigid control for not essential requirements to support premium service. Finally we show that the proposed scheme can achieve low delay and low average waiting time for the premium service.

ACKNOWLEDGMENT

The author would like to thank the anonymous reviewers for their constructive comments and suggestions, which helped to improve the quality of this paper.

REFERENCES

1. Chi-Tsun Cheng, Member, IEEE, Chi K. Tse, Fellow, IEEE, and Francis

   C. M. Lau, Senior Member, IEEE, A Delay-Aware Data Collection Network Structure for Wireless Sensor Networks IEEE Sensors Journal, Vol. 11, No. 3, March 2011.

2. Giuseppe Anastasi, Marco Conti, Mario Di Francesco, Andrea Passarella Energy conservation in wireless sensor networks: A survey Department of Information Engineering, University of Pisa, via Diotisalvi 1, 56122 Pisa, Italy, July 2008

3. Yong Ding, Student Member, IEEE, Chen Wang, Senior Member, IEEE, and Li Xiao, Member, IEEE An Adaptive Partitioning Scheme for Sleep Scheduling and Topology Control in Wireless Sensor Networks IEEE Transactions On Parallel And Distributed Systems, Vol. 20, No. 9,

   September 2009

4. Feng Liu, Chi-Ying Tsui, Member, IEEE, and Ying Jun (Angela) Zhang, Member, IEEE Joint Routing and Sleep Scheduling for Lifetime Maximization of Wireless Sensor Networks IEEE Transactions On Wireless Communications, Vol. 9, No. 7, July 2010

   Fig 4.4 Network lifetime over a number of zones

5. Soumyadip Sengupta, Swagatam Das, Member, IEEE, Md. Nasir, Athanasios V. Vasilakos, and Witold Pedrycz An Evolutionary Multiobjective Sleep-Scheduling Scheme for Differentiated Coverage in Wireless Sensor Networks IEEE Transactions On Systems, Man, And CyberneticsPart C: Applications And Reviews, Vol. 42, No. 6,

   November 2012

6. Abbas Noon1, Ali Kalakecp, Seifedine Kadry1 A New Round Robin Based Scheduling Algorithm for Operating Systems: Dynamic Quantum Using the Mean Average" IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 3, No. 1, May 2011 ISSN (Online): 1694- 0814

7. Alexander Bertrand, Member, IEEE, Joseph Szurley, Member, IEEE, Peter Ruckebusch, Ingrid Moerman, and Marc Moonen, Fellow, IEEE Efficient Calculation of Sensor Utility and Sensor Removal in Wireless Sensor Networks for Adaptive Signal Estimation and Beamforming IEEE Transactions On Signal Processing, Vol. 60, No. 11, November 2012

8. L.Mokdad a, J. Ben-Othman, B. Yahya, S. Niagne Performance evaluation tools for QoS MAC protocol for wireless sensor networks

   LACL Laboratory, University of Paris-Est, Créteil, France 2010

9. Nidal Nasser, Lutful Karim, and Tarik Taleb Dynamic Multilevel Priority Packet Scheduling Scheme for Wireless Sensor Network IEEE Transactions on Wireless Communications, Vol. 12, No. 4, April 2013

10. Chuck Semeria, Supporting Differentiated Service Classes: Queue Scheduling Disciplines, Juniper Networks, Part Number:: 200020-001, December 2001.

11. Srikanth Jagabathula and Devavrat Shah Fair Scheduling in Networks Through Packet Election IEEE Transactions On Information Theory,

    Vol. 57, No. 3, March 2011

12. Songwu Lu, Student Member, IEEE, Vaduvur Bharghavan, and R. Srikant, Member, IEEE, Fair Scheduling in Wireless Packet Networks IEEE/ACM Transactions on Networking, vol. 7, no. 4, August 1999.

13. Jae-Han Jeon, Hee-Jung Byun, and Jong-Tae Lim End-to-End Delay Guaranteed Proportional Fair Scheduling for Wireless Networks IEEE Communications Letters, Vol. 15, No. 4, April 2011

14. Jun Yi, Christian Poellabauer, Minimum Bandwidth Reservations for Periodic streams in Wireless Real-Time syatems IEEE Transactions on Mobile computing, VOL 10, NO. 5, APRIL 2011.

15. You-Chiun Wang, Yu-Chee Tseng, and Wen-Tsuen Chen MR-FQ: A Fair Scheduling Algorithm for Wireless Networks with Variable Transmission Rates SIMULATION: Transactions Of The Society For Modeling And Simulation International, 2005

16. Gergely Vakulya, Gyula Simon Extended Round-Robin TDMA Scheduling Scheme for Wireless Sensor Networks University of Pannonia Department of Computer Science and Systems Technology Veszprem, Hungary Email: simon@dcs.uni-pannon.hu, 2013.

17. Wei Liu, Wenqing Cheng, Jianhua He, Chunhui Le, Zongkai Yang,An Adaptive Scheduling Scheme for Fair Bandwidth Allocation Huazhong University of Science and Technology, China wliu@public.wh.hb.cn

18. Haining Wang, Chia Shen, Adaptive-Weighted Packet Scheduling for Premium Service The University of Michigan Ann Arbor, kgshin

@eecs.umich.edu