International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Reduction of End To End Delay Using Priority Queues in Wireless Sensor Network

Jayasudha.J1 , T.Prabakaran2
  1. PG Scholar,Department of Electronics & communication Engineering, SNS College of Technology, Chennai Anna university, Tamilnadu, India
  2. Department of Electronics & communication Engineering, SNS College of Technology,Coimbatore, Tamilnadu, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Wireless sensor network are usually deployed, possibly in extreme conditions such as mountainous region, and left unattended to function for long time. In order to prolong the network lifetime, it is necessary to minimize the consumption of energy by individual nodes. In addition, it is also necessary to ensure that the average rate of consumption of energy by each node is also the same. The existing packet-scheduling mechanisms of WSN use First Come First Served (FCFS), non-pre-emptive priority and pre-emptive priority scheduling algorithms. In this project, a Dynamic Multilevel Priority packet scheduling scheme proposed. In the proposed scheme, each node, except those at the last level of the virtual hierarchy in the zone based topology of WSN, has three levels of priority queues. According to priority of packet node will route the packet to destination.

Keywords
Wireless Sensor Network, Dynamic Multilevel Priority(DMP),First Come First Served.

I . INTRODUCTION
Most existing Wireless Sensor Network (WSN) operating systems use First Come First Serve (FCFS)[23] schedulers that process data packets in the order of their arrival time and, thus, require a lot of time to be delivered to a relevant base station (BS). However, to be meaningful, sensed data have to reach the BS within a specific time period or before the expiration of a deadline. Additionally, real-time emergency data should be delivered to BS with the shortest possible end-to-end delay. Hence, intermediate nodes require changing the delivery order of data packets in their ready queue based on their importance (e.g., real or non-real time) and delivery deadline. Furthermore, most existing packet scheduling algorithms of WSN are neither dynamic nor suitable for large scale applications since these schedulers are predetermined and static, and cannot be changed in response to a change in the application requirements or environments[23]-[26]. For example, in many real- time applications, a real-time priority scheduler is statically used and cannot be changed during the operation of WSN applications.
In this paper, Dynamic Multilevel Priority (DMP) packet scheduling scheme proposed for WSN in which sensor nodes are virtually organized into a hierarchical structure. Nodes that have the same hop distance from the BS are considered to be located at the same hierarchical level. Data packets sensed by nodes at different levels are processed using a TDMA scheme. For instance, nodes that are located at the lowest level and one level upper to the lowest level can be allocated timeslots 1 and 2, respectively. Each node maintains three levels of priority queues. This is because we classify data packets as (i) real-time (priority 1), (ii) non-real-time remote data packet that are received from lower level nodes (priority 2), and (iii) non-real-time local data packets that are sensed at the node itself (priority 3). Non-real-time data traffic with the same priority are processed using the shortest job first (SJF) scheduler scheme since it is very efficient in terms of average task waiting time [23].

II . LITERATURE SURVEY
In [4], the sensors and/or the radios of sensor nodes are modelled to sleep (switch them off) so as to conserve energy. In this work we propose several distributed algorithms to perform sensor and radio sleep scheduling in wireless sensor networks while trying to minimize its negative impact. The network as a RBN and show how sensors are able to coordinate their sensor activity to avoid redundant sensing. While in our work the sensors make changes (if any) to their active slot choice synchronously at every time-step, in their work the authors iterate over each node in the network in a random order and apply their local heuristics. Although the difference may seem minor, parallel updates of states in such a system can lead to new constraint violations being generated.In [14], the node sleep scheduling scheme in the commonly used static disk model for sensor networks, where homogenous sensors are uniformly distributed in a circular area with a stationary sink located at the center. Then, we introduce and analyze a Hops-based Sleeping Scheduling algorithm (HSS) for enhancing the lifetime and energy efficiency of the sensor networks.
The HSS firstly divides the circular sensor network into several levels based on the average hop distance by initially flooding. Then, it controls the density distribution of the active sensors by setting hops-based sleeping probabilities of the sensors. The network lifetime and energy efficiency can be therefore greatly improved as compared to Normal and RSS schemes. We can extend this work to clustered heterogeneous multi-hop wireless sensor networks.In [11] cluster based heterogeneous wireless sensor network, by deploying a large number of low power sensor nodes and a small number of more powerful, special nodes to serve as cluster heads (CHs). We propose a sleep scheduling scheme on our heterogeneous network for balancing energy consumption rates in low power sensor nodes. We consider three factors contributing to the nodes scheduling decision - distance of node from CH, residual energy of the nodes and backloginformation- buffer-queue.
We have considered single hop network environment. Unlike our scheme is dynamic, in that we do not assume any prior distribution of fraction of sleeping nodes in each round. Our scheme selects the nodes for sleeping based on node’s distance to its CH, its residual energy and backlog-information-buffer-queue. The sleeping probabilities are a function of these three factors, which ensure energy load balancing on sensor nodes.

III . RELATED WORKS
First Come First Served (FCFS): Most existing WSN applications use First Come First Served (FCFS) schedulers that process data in the order of their arrival times at the ready queue. In FCFS, data that arrive late at the intermediate nodes of the network from the distant leaf nodes require a lot of time to be delivered to base station (BS) but data from nearby neighbouring nodes take less time to be processed at the intermediate nodes. In FCFS, many data packets arrive late and thus, experience long waiting times.
Earliest Deadline First (EDF): Whenever a number of data packets are available at the ready queue and each packet has a deadline within which it should be sent to BS, the data packet which has the earliest deadline is sent first. This algorithm is considered to be efficient in terms of average packet waiting time and end-to-end delay.

Factors

Priority
Packet scheduling schemes can be classified based on the priority of data packets that are sensed at different sensor nodes.

Non-pre-emptive
In non-pre-emptive priority packet scheduling, when a packet t1 starts execution, task t1 carries on even if a higher priority packet t2 than the currently running packet t1 arrives at the ready queue. Thus t2 has to wait in the ready queue until the execution of t1 is complete.
Pre-emptive In pre-emptive priority packet scheduling, higher priority packets are processed first and can pre-empt lower priority packets by saving the context of lower priority packets if they are already running.
Real-time packet scheduling Packets at sensor nodes should be scheduled based on their types and priorities. Realtime data packets are considered as the highest priority packets among all data packets in the ready queue. Hence, they are processed with the highest priority and delivered to the BS with a minimum possible end-to-end delay.
Single Queue Each sensor node has a single ready queue. All types of data packets enter the ready queue and are scheduled based on different criteria: type, priority, size, etc. Single queue scheduling has a high starvation rate. Multi-level Queue Each node has two or more queues. Data packets are placed into the different queues according to their priorities and types. Thus, scheduling has two phases: (i) allocating tasks among different queues, (ii) scheduling packets in each queue. The number of queues at a node depends on the level of the node in the network. For instance, a node at the lowest level or a leaf node has a minimum number of queues whilst a node at the upper levels has more queues to reduce end-to-end data transmission delay and balance network energy consumptions.
Non-real-time packet scheduling Non-real time packets have lower priority than real-time tasks. They are hence delivered to BS either using first come first serve or shortest job first basis when no real-time packet exists at the ready queue of a sensor node. These packets can be intuitively pre-empted by real-time packets.
The existing packet-scheduling mechanisms of WSN use First Come First Served (FCFS), non-pre-emptive priority and pre-emptive priority scheduling algorithms. These algorithms incur a high processing overhead and long end-to-end data transmission delay due to the FCFS concept. Indeed, most existing Wireless Sensor Network operating systems use First Come First Serve schedulers that process data packets in the order of their arrival time and, thus, require a lot of time to be delivered to a relevant base station (BS). Sensed data have to reach the BS within a specific time period or before the expiration of a deadline.
Additionally, real-time emergency data should be delivered to BS with the shortest possible end-to-end delay. Hence, intermediate nodes require changing the delivery order of data packets in their ready queue based on their importance and delivery deadline.Furthermore, most existing packet scheduling algorithms of WSN are neither dynamic nor suitable for large scale applications

IV . PROPOSED SYSTEM
Data packets that are sensed at a node are scheduled among a number of levels in the ready queue. According to the priority of the packet and availability of the queue, node will schedule the packet for transmission.Due to separated queue availability packet transmission delay is reduced. Due to reduction in packet transmission delay, node can goes to sleep mode as soon as possible. So we can improve the energy saving also.In base paper, node only scheduled priority packet buffering. In our enhancement node can check whether expire packets are buffered or not, if buffered then node deletes dead packet.According to queuing delay, node can drop packet in intelligent manner.Due to this operation, we can reduce buffering delay and we can improve power saving

Priority Queuing
Priority Queuing (PRIQ) assigns multiple queues to a network interface with each queue being given a priority level. A queue with a higher priority is always processed ahead of a queue with a lower priority. If two or more queues are assigned the same priority then those queues are processed in a round-robin fashion.
The queuing structure in PRIQ is flat -- you cannot define queues within queues. The root queue is defined, which sets the total amount of bandwidth that is available, and then sub queues are defined under the root. Consider the following example:
Root Queue (2Mbps)
Queue A (priority 1)
Queue B (priority 2)
Queue C (priority 3)
The root queue is defined as having 2Mbps of bandwidth available to it and three sub queues are defined. The queue with the highest priority (the highest priority number) is served first. Once all the packets in that queue are processed, or if the queue is found to be empty, PRIQ moves onto the queue with the next highest priority. Within a given queue,packets are processed in a First in First out (FIFO) manner.
It is important to note that when using PRIQ you must plan your queues very carefully. Because PRIQ always processes a higher priority queue before a lower priority one, it's possible for a high priority queue to cause packets in a lower priority queue to be delayed or dropped if the high priority queue is receiving a constant stream of packets.

V . CONCLUSION
A Dynamic Multilevel Priority (DMP) packet scheduling scheme for Wireless Sensor Networks (WSNs). The 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 End-to-End Delay of all Tasks (microSec) for the highest priority data while exhibiting acceptable fairness towards lowest-priority data. Experimental results show that the proposed 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. As enhancements to the proposed DMP scheme, we envision Assigning task priority based on task deadline instead of the shortest task processing time. To reduce processing overhead and save bandwidth, we could also consider removing tasks with expired deadlines from the medium. Furthermore, if a real-time task holds the resources for a longer period of time, other tasks need to wait for an undefined period time, causing the occurrence of a deadlock. This deadlock situation degrades the performance of task scheduling schemes in terms of end to- end delay. Hence, we would deal with the circular wait and pre-emptive conditions to prevent deadlock from occurring

VI . ACKNOWLEDGMENT
I am very much grateful to my project guide Mr.T.Prabhakaran,Assistant Professor, who has constantly encouraged me and provided me enough attention to help with my work. Without him this will not be complete. I also thank my college management for providing me many opportunities to carry out my research. Finally I thank my college Principal Dr.S.ChenthurPandian for his constant support.

References
  1. G. Anastasi, M. Conti, and M. Di Francesco, “Extending the lifetime of wireless sensor networks through adaptive sleep,” IEEE Trans. Industrial Informatics, vol. 5, no. 3, pp. 351–365, 2009.
  2. G. Bergmann, M. Molnar, L. Gonczy, and B. Cousin, “Optimal period length for the CQS sensor network scheduling algorithm,” in Proc. 2010 International Conf. Netw. Services, pp. 192–199.
  3. E. Bulut and I. Korpeoglu, “DSSP: a dynamic sleep scheduling protocol for prolonging the lifetime of wireless sensor networks,” in Proc. 2007 International Conf. Advanced Inf. Networking Appl., vol. 2, pp. 725– 730.
  4. S. Chachra and M. Marefat, “Distributed algorithms for sleep scheduling in wireless sensor networks,” in Proc. 2006 IEEE International Conf. Robot.Autom., pp. 3101–3107.
  5. P. Guo, T. Jiang, Q. Zhang, and K. Zhang, “Sleep scheduling for critical event monitoring in wireless sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 23, no. 2, pp. 345–352, Feb. 2012.
  6. F. Liu, C. Tsui, and Y. J. Zhang, “Joint routing and sleep scheduling for lifetime maximization of wireless sensor networks,” IEEE Trans. Wireless Commun., vol. 9, no. 7, pp. 2258–2267, July 2010.
  7. J. Liu, N. Gu, and S. He, “An energy-aware coverage based node scheduling scheme for wireless sensor networks,” in Proc. 2008 In- ternational Conf. Young Comput. Scientists, pp. 462–468.
  8. O. Khader, A. Willig, and A. Wolisz, “Distributed wakeup scheduling scheme for supporting periodic traffic in wsns,” in Proc. 2009 European Wireless Conf., pp. 287–292.
  9. B. Nazir and H. Hasbullah, “Dynamic sleep scheduling for minimizing delay in wireless sensor network,” in Proc. 2011 Saudi International Electron., Communications Photon. Conf., pp. 1–5.
  10. D. Shuman and M. Liu, “Optimal sleep scheduling for a wireless sensor network node,” in Proc. 2006 Asilomar Conf. Signals, Syst. Comput., pp. 1337–1341.
  11. S. Paul, S. Nandi, and I. Singh, “A dynamic balanced-energy sleep scheduling scheme in heterogeneous wireless sensor network,” in Proc. 2008 IEEE International Conf. Netw., pp. 1–6, 2008.
  12. A. R. Swain, R. C. Hansdah, and V. K. Chouhan, “An energy aware routing protocol with sleep scheduling for wireless sensor networks,” in Proc. 2010 IEEE International Conf. Adv. Inf. Netw. Appl., pp. 933–940.
  13. Y. H. Wang, Y. L. Wu, and K. F. Huang, “A power saving sleep scheduling based on transmission power control for wireless sensor networks,” in Proc. 2011 International Conf. Ubi-Media Comput., pp. 19–24.
  14. Y. Wang, D. Wang, W. Fu, and D. P. Agrawal, “Hops-based sleep scheduling algorithm for enhancing lifetime of wireless sensor net- works,” in Proc. 2006 IEEE International Conf. Mobile Adhoc Sensor Syst., pp. 709–714.
  15. Y. Xiao, H. Chen, K. Wu, B. Sun, Y. Zhang, X. Sun, and C. Liu, “Coverage and detection of a randomized scheduling algorithm in wireless sensor networks,” IEEE Trans. Comput., vol. 59, no. 4, pp. 507–521, Apr. 2010.
  16. X. Xu, Y. H. Hu, J. Bi, and W. Liu, “Adaptive nodes scheduling approach for clustered sensor networks,” in Proc. 2009 IEEE Symp. Comput.Commun., pp. 34–39.
  17. Y. Zhao, J. Wu, F. Li, and S. Lu, “VBS: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones,” in Proc. 2010 IEEE INFOCOM, pp. 1–5.
  18. B. Zeng, Y. Dong, and D. Lu, “Cooperation-based scheduling algorithm in wireless multimedia sensor networks,” in Proc. 2011 International Conf. Wireless Commun., Netw. Mobile Comput., pp. 1–4.
  19. N. Edalat, W. Xiao, C. Tham, E. Keikha, and L. Ong, “A price-based adaptive task allocation for wireless sensor network,” in Proc. 2009 IEEE International Conf. Mobile Adhoc Sensor Syst., pp. 888–893.
  20. H. Momeni, M. Sharifi, and S. Sedighian, “A new approach to task allocation in wireless sensor actor networks,” in Proc. 2009 International Conf. Computational Intelligence, Commun. Syst. Netw., pp. 73–78.
  21. F. Tirkawi and S. Fischer, “Adaptive tasks balancing in wireless sensor networks,” in Proc. 2008 International Conf. Inf. Commun. Technol.: From Theory Appl., pp. 1–6.
  22. X. Yu, X. Xiaosong, and W. Wenyong, “Priority-based low-power task scheduling for wireless sensor network,” in Proc. 2009 International Symp. Autonomous Decentralized Syst., pp. 1–5.
  23. W. Stallings, Operating Systems, 2nd edition. Prentice Hall, 1995.
  24. Y. Zhao, Q. Wang, W. Wang, D. Jiang, and Y. Liu, “Research on the priority-based soft real-time task scheduling in TinyOS,” in Proc. 2009 International Conf. Inf. Technol. Comput. Sci., vol. 1, pp. 562–565.
  25. TinyOS. Available: http://webs.cs.berkeley.edu/tos, accessed June 2010.
  26. Available: http://webs.cs.berkeley.edu/tos, accessed June 2010.
  27. E. M. Lee, A. Kashif, D. H. Lee, I. T. Kim, and M. S. Park, “Location based multi-queue scheduler in wireless sensor network,” in Proc. 2010 International Conf. Advanced Commun. Technol., vol. 1, pp. 551–555.
  28. C. Lu, B. M. Blum, T. F. Abdelzaher, J. A. Stankovic, and T. He, “RAP: a real-time communication architecture for large-scale wireless sensor networks,” in Proc. 2002 IEEE Real-Time Embedded Technol. Appl. Symp., pp. 55–66.