Real-time Scheduler for Wireless Sensor Network : A Review

Real-time Scheduler for Wireless Sensor Network : A Review

Abstract

With the great advancement in the area of embedded systems and sensor technology, a wireless sensor networks (WSNs) attract a great deal of research attention and this technology are widely used in the number of applications related to variety of fields including military, healthcare monitoring, biological, home, vehicular monitoring, infrastructure monitoring, building energy monitoring and industrial sensing. Many of applications in WSNs are real time applications that are requested to run in real time way. To support such real time applications we need Real Time Operating System (RTOS) which provides logically correct results and also deadline has to be met. This paper presents an overview of existing work in sensornet operating system (OS) design. Then, the specialties what sensornet OS should posses are discussed in detail. Next, we discuss scheduling algorithms to be used for real time systems. At last, we proposed Micro Controller OS-II (µC/OS-II) with Earliest Deadline First (EDF) algorithm.

Keywords

Wireless Sensor Network, Real Time Operating System,

µC/OS-II operating system, Earliest Deadline First.

1. INTRODUCTION

   A WSN composed of number of wireless interconnected sensors. These are usually tiny autonomous devices that are used to monitor some physical conditions or other values with their sensors and use short range wireless link for communication between them and between higher level systems. The measured values typically are temperature, humidity, light intensity; moisture etc.WSN is found lot of interest due to great variety of applications like environmental monitoring, military surveillance, biomedical systems, intelligent parking, healthcare applications and industrial applications. All these applications interface with the real world environments and the delivery of packet is bound to certain timing constraints [11]. It is a special type of real time

   embedded systems where deadline is one of the critical parameter. Applications in embedded systems are

   usually domain-specific. Different applications will require different operating systems to provide various tailor made functionalities. The basic functionalities of an OS include resource abstraction, process management, memory management, interrupt management and device management, scheduling policies, multithreading, and multitasking [1]. The OS also have a very efficient inter-process communication (IPC) subsystem so that if a process wants to communicate, it should be able to do so without fail [18]. Over the past few years we have seen that OS plays a central role in building scalable distributed applications that are efficient and reliable. WSNs typically does not use general purpose operating system rather they use OS designed directly for them called special purpose OS i.e. RTOS. RTOS supports applications that meet deadlines and certain timing constraints to providing logically correct results [17]. To meet the real-time constraints in Real time system we need to schedule the task, for that different scheduling algorithms were used. The main objective of a real-time task scheduler is to meet the deadline of tasks in the system. Mostly all the real-time systems in existence use multitasking and pre-emption.

   µC/OS-II is a real-time pre-emptive multitasking embedded OS kernel. A pre-emptive kernel is used when system responsiveness is important; therefore,

   µC/OS-II and most commercials real-time kernels are pre-emptive. µC/OS-II is a completely portable, ROMable, scalable, real-time kernel. µC/OS-II is written in ANSI C and contains a small portion of assembly language code to adapt it to different processor architectures. µC/OS-II has been ported to over 40 different processor architectures, ranging from 8 to 64-bit CPUs. The µC/OS-II provides a number of key functionalities needed by networked embedded applications, such as multitasking, synchronization, timer management, memory management. The series of advantages existed in µC/OS-II could encourage programmers to rapidly prototype novel sensor applications, meanwhile, the µC/OS-II also enables micro sensor nodes to natively interleave complex tasks with time-sensitive tasks, thereby mitigating the bounded buffer producer-consumer problem. Additionally, the security and reliability is helpful to construct robust wireless sensor networks [29].

   In this paper, we proposed µC/OS-II operating system for wireless networked sensors with suitable scheduling policy. The remainder of this paper is organized as follows: Section 2 introduces related works of sensor network OS. Section 3 discusses the specialties which a sensor OS should possess. Section 4 elaborates the task scheduling algorithms required to schedule the task in WSN. Finally, section 5 concludes this paper with some suggestions for further improvement.

2. RELATED WORK

   The huge potential of WSN applications needs the RTOS to be suitable for different operating environments, from a simple single-task event to a real- time multi-thread system. Moreover, due to the resource constrains of WSN node, the RTOS must consume tiny resource, including CPU, and memory. It means that the RTOS must be resource-and context aware to minimize energy consumption. This section presents a brief overview of the related work that has been done on sensor node operating systems and also discussed different scheduling policies implemented in RTOS.

   In [14], Levis et al. proposed Berkeleys TinyOS architecture which is designed for WSN. TinyOS is a well-known operating system having light weight, low power and the Mote platform has been widely used in many kinds of applications. It is currently a fundamental framework of research on wireless sensor networks. TinyOS can support concurrent programs with very low memory requirements. The OS has a footprint that fits in 400 bytes and having monolithic kernel. Since TinyOS kernel supports FIFO scheduling policy but FIFO scheduling policy having some disadvantages that are also associated with the TinyOS scheduler. TinyOS does not support real-time application; hence this OS is not a good choice to run real time applications.

   In [6], Dunkels et al. proposed Contiki is an event- driven, portable, a lightweight open source OS written in C for WSN sensor nodes. It does not employ any special kind of scheduling algorithm for real time applications. Events are classified as synchronous and asynchronous and they are scheduled as they arrive. In case of interrupts, interrupt handlers of an application runs with respect to their priority.

   In [3], Bhatti et al. proposed the Mantis OS is energy efficient, multithreaded OS provides scheduler which uses round robin scheduling policy within the each priority class. This policy means the highest priority thread class can cause starve to lower priority thread. As compare to TinyOS or Contiki scheduler, the

   Mantis OS scheduler is better because of pre-emptive priority scheduling technique that may support real- time task. But there is still some requirement of real- time schedulers like Rate Monotonic and Earliest Deadline First in order to truly accommodate real-time tasks.

   In [7], Eswaran et al. proposed Nano-RK provides priority scheduling at two levels: priority scheduling at the process leel and priority scheduling at the network level. Author only discuss the scheduling algorithms that are being used in Nano-RK for process scheduling. To support real-time applications, Nano-RK uses a fully pre-emptive priority driven scheduling algorithm, i.e., at any given instance the highest priority task is scheduled by the operating system. A rate monotonic scheduling algorithm is used for real-time periodic tasks and the priority of the task is set statically based upon the period of the job: the shorter the period of the job, the higher is its priority. Since rate monotonic scheduling algorithm statically assigns priorities to tasks, Nano-RK recommends configuring task parameters offline.

   In [4] [15], Cao Q et al. LiteOS provides an implementation of Round Robin scheduling and Priority-based scheduling. Whenever a task is added to the ready queue, the next task to be executed is chosen through priority-based scheduling. The tasks run to completion or until they request a resource that is not currently available. When a task requires a resource that is not available, the task enables interrupts and goes to sleep mode. Once the required resource becomes available, the appropriate interrupt is signalled and the task resumes it execution from where it had left. When a task completes its operation it leaves the kernel. When there are no active tasks in the system, the sensor node goes to sleep mode. Before going to sleep mode the node enables its interrupts so that it can wake up at the proper event or time. LiteOS scheduler allows tasks to run until completion, there is a chance that a higher priority task enters the ready queue when a low priority task is completing its execution. In this scenario, a higher priority task may miss its deadline; therefore LiteOS is not an appropriate OS for real-time sensor networks.

   From the above discussion it can be seen that few OSs provide support for real-time application. Some OSs provides support for priority scheduling while many others do not even provide support for this.

3. SENSOR OS DESIGN AND CHALLENGES

   In order to develop a practical and efficient sensornet OS, many challenges have to be addressed, mainly due to the severe resource constraints of the sensor node

   hardware and demanding requirements of WSN applications. The major challenges that influence the OS design are listed as follows.

   1. Small Footprint. The current era of embedded processors demanding larger Read Only Memory sizes with smaller Random Access Memory sizes [29]. Due to the limitation of memory on a sensor node demands the OS to be designed with a very small footprint. It is a fundamental characteristic of a sensor network OS and is the primary reason why so many sophisticated embedded OS cannot be easily ported to sensor nodes [26].

   2. Power management capability. Power management interfaces provided by an OS can be used to enforce an optimal way of utilizing energy. Energy is important parameter in WSNs that must achieve long lifetimes while operating on battery energy. Sensor nodes provide very limited battery life-time. Thus possessing power management capability is essential, which helps to improve system performance and extend the battery lifetime [5].

   3. Reliability. In most of the applications OS reliability is of great importance to facilitate developing complex WSN software, ensuring the correct functioning of WSN systems.

   4. Portability. In WSN the hardware platforms are evolving day-by-day. Portability is considered to be an important issue as everyone is working on their customized hardware platforms. The OS should be designed in such a way that it is easily portable to different hardware platforms with minimal changes.

   5. Real-Time Guarantee. As most applications in WSN are time-sensitive in nature where data must be forwarded and relayed on a timely basis, real-time guarantee is a necessary requirement for such applications. For example in applications like fire detection in nuclear reactors, preventive action should be taken within hard deadlines. By using real-time scheduler with proper scheduling technique real-time constraints of the application can be satisfied [10].

   6. Networking Stack. The networking stack facilitates developing distributed WSN applications. The OS should support multi-hop wireless networking, routing. It also handles reliable packet transmission, multicasting, queue management, radio chip configuration, and Medium Access Control (MAC) [26].

   7. Programming Convenience. For application programmers OS should provide a convenient programming environment. Many Sensor network

      applications are diverse and demanding. Hence importance on development of sensor network applications programming convenience is of great importance.

   8. Dynamic Reprogramming. Dynamic reprogramming is an especially useful feature for wireless networked sensors. It is the process of updating the software dynamically running on the sensor nodes. It has been a very active research area in WSN because of the inaccessibility of the sensor nodes after deployment and due to the presence of large number of them in the network. Without reprogramming, it is difficult to perform operations like modification, deletion or adding the contents in the software from the running system in WSN [23].

   9. Customizability. Mostly all the software platforms developed for WSN is application specific. Different applications demand different requirements from operating system [1]. These requirements may be small footprint, real-time guarantees, reprogramming. The design of OS should be in such a way that it should be easily customizable and extensible to various applications.

   10. Timeliness and Schedulability. Most sensor applications tend to be time-sensitive in nature where processing must be completed within the defined time- bound otherwise system will fail. Scheduling is technique for allocating tasks on processors to ensure that deadlines are to meet. Managing the deadlines of these tasks requires support of a real-time operating system.

       Usually it is very hard, if not impossible, to achieve optimality in all aspects. Most current solutions address the primary design challenges.

       Following table represents the summary of OS which supports the above mentioned challenges.

       Table 1 Summary of OS

       Features	Tiny OS	Contiki OS	Mantis OS	Nano- Rk OS	Lite OS	C/ OS-II
       Priority based scheduling	No	No	No	Yes	Yes	Yes
       Real time guarantee	No	No	No	Yes	No	Yes
       Dynamic Reprogramming	No	Yes	Yes	Yes	Yes	Yes
       Memory Management	No	No	No	No	Yes	Yes
       Low Power Mode	Yes	Yes	Yes	Yes	Yes	Yes
       Scheduling algorithms used	FIFO	Run time scheduling	Round Robin	Rate Monotonic	Round Robin	Rate Monotonic

4. REAL-TIME SCHEDULING ALGORITHM

   Most of the tasks in WSN are requested to run in a real- time way. Real-time systems have well defined, fixed time constraints i.e., processing must be completed within the defined constraints otherwise the system will fail. The most important attribute of real-time systems is that the correctness of such systems depends on not only the computed results bu also on the time at which results are produced. The real time systems accepts commands from external peripherals, processes the data and then perform desired action. Mostly we can classify real-time system into two main categories: Hard real- time and soft real-time system. In Hard Real-Time System requires that fixed deadlines must be met otherwise disastrous situation may arise whereas in Soft Real-Time System, missing an occasional deadline is undesirable, but nevertheless tolerable. As real-time systems execute critical tasks, therefore it must be designed very carefully. For that, many scheduling policy has been already designed [28].

   A fundamental operation of an OS is scheduling the task. In order to meet a programs temporal requirements of real-time systems, it is of the utmost importance that the scheduling algorithm should produce a predictable schedule, that is, at all times it should be known that which task is going to be executed [9]. Figure 1 shows the basic scheduling algorithm function.

   Make an allocation

   Make an allocation

   Schedule processor

   Schedule processor

   Is it feasible?

   Is it feasible?

   Display Output

   Declare Failure

   Display Output

   Declare Failure

   Figure 1. Basic Function of Scheduling Algorithm

   1. Different available scheduling algorithms and their characteristics

      In Real-time systems scheduling algorithms are classified into two categories: Static algorithm and Dynamic algorithm. Based on execution attributes of tasks, dynamic algorithm assigns priorities at runtime. This algorithm allows switching of priorities between tasks. In contrast with dynamic algorithm, a static algorithm assigns priorities at design time. All assigned priorities remain fixed throughout the execution of task. Figure 2 gives the classification of available scheduling algorithms for real-time systems. Known scheduling algorithms include Round Robin Scheduling, Priority- Based Scheduling, Earliest Deadline First Scheduling, Rate Monotonic Scheduling, Feedback Scheduling [13][16].

      Figure 2. Types of Real time Scheduling Algorithms

      Rate Monotonic (RM): In RM algorithm tasks have to be periodic in nature and deadline must be equal to its period. Tasks are scheduled according to their period. This algorithm implemented by assigning fixed priority to tasks based on their periods: the shorter the period, the higher the priority.

      Deadline Monotonic (DM): Tasks have to be periodic and are scheduled according to their deadline. RM and DM are identical except priorities are automatically computed from period of task or deadline.

      Least Laxity First (LLF): Tasks can be periodic or not and are scheduled according to their laxity. Laxity time is defined as the temporal difference between the deadline, the ready time and the run time.

      Earliest Deadline First (EDF): The most common dynamic priority scheduling algorithm for real-time systems is the EDF. Here priorities are dynamically reassigned at run-time based on the time still available for each task to reach its next deadline. Both static and dynamic systems are scheduled by EDF algorithm.

      A queue of task is maintained in the ascending order of their respective deadlines. An EDF scheduling policy is used to serve the first task from this queue as and when processor becomes free. When new task arrives, its deadline will be compared with the deadline of currently executing task, and in case if deadline of newly arrived task is closer to the current time, it will receive the processor time and the old task will be pre- empted and placed back in the queue. The EDF algorithm has been proven to be optimal among all scheduling policies on a uniprocessor, in the sense that if a real-time task set cannot be scheduled by EDF, then this task set cannot be scheduled by any algorithm [8][19][22]. As compared to other algorithms EDF is simple to implement and gives much better utilization of processor.

      In WSN, most of the tasks are appeared dynamically over the network. By using RM, DM, LLF algorithms more real time tasks not be completed before the deadline and leads to packet loss, overload, and decline of throughput. In most applications, the sensor nodes are unattended and live only as long as their batteries can support. The sensor node has limited battery energy and thus the sensor node must use available resources effectively and manage the energy to extend the lifetime of the network as much as it can. Therefore

      energy management is a challenging problem in designing a WSN.

      This paper proposes an EDF scheduling algorithm which helps to schedule tasks dynamically and enhance the throughput, reduce the overload and also helps to decrease energy consume in data transmission and routing [22][27]. EDF improves the systems performance and allows a better exploitation of resources.

5. CONCLUSION AND FUTURE WORK

OS support is important to facilitate the development and maintenance of WSNs. In this paper, we provide an overview of existing work; discuss the challenges of in the OS design space. In this paper, we discussed the

µC/OS-II operating system with its features. µC/OS-II operating system supports various real time applications in WSN. Next, we discussed various scheduling algorithms with their characteristics and also proposed EDF scheduling algorithm with their benefits over the other real time scheduling algorithms. Currently, we are designing and implementing EDF algorithm for scheduling the entire tasks in WSN by using C/OS-II RTOS. Further study is required to improve performance.

REFERENCES

1. Adi Mallikarjuna Reddy V AVU Phani Kumar, D Janakiram, and G Ashok Kumar, (2007). Operating Systems for Wireless Sensor Networks: A Survey Technical Report.

2. Andre Rodrigues, Tiago Camilo, Jorge Sa Silva, Fernando Boavida, (2012). Diagnostic Tools for Wireless Sensor Networks: A Comparative Survey, Springer Science Business Media, LLC.

3. Bhatti S.; Carlson J.; Dai H.; Deng J.; Rose J.; Sheth A.; Shucker B.; Gruenwald C.; Torgerson H.R., (2005). Mantis OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms. Mobile. Network, 563-579.

4. Cao, Q.; Abdelzaher, T.; Stankovic, J.; He, T., (2008). The LiteOS Operating System: Towards Unix Like Abstraction for Wireless Sensor Networks. In Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), St. Louis, MO, USA, 2224.

5. Chi-Tsun Cheng, Chi K. Tse, and Francis C. M. Lau, (2010). An Energy-Aware Scheduling Scheme for Wireless Sensor Networks, IEEE transaction on vehicular technology, vol. 59, no. 7.

6. Dunkels, A.; Gronvall, B.; Voigt, T., (2004). Contiki a Lightweight and Flexible Operating System for Tiny

1. M.Kaladevi and Dr.S.Sathiyabama, (2010). A Comparative Study of Scheduling Algorithms for Real Time Task. International Journal of Advances in Science and Technology, vol. 1, no. 4.

2. M.V. Panduranga Rao, K.C. Shet, R.Balakrishna, K. Roopa, (2008). Development of Scheduler for Real Time and Embedded System Domain, 22nd International Conference on Advanced Information Networking and Applications Workshops, IEEE Computer Society, pp. 1-6.

3. Octav Chipara, Chenyang Lu, and Gruia-Catalin Roman, (2013). Real-Time Query Scheduling for Wireless Sensor Networks, IEEE transactions on computers, vol. 62, no. 9.

4. Pinkesh Pachchigar, P.Eswaran, Amol Kashinath Boke, (2013). Design and Implementation of Deadline based EDF Algorithm on ARM LPC2148, Proceedings

for Wireless Sensor Networks,IEEE transactions on computers, vol. 60, no. 12.

1. ZHAO Zhi-bin* and GAO Fuxiang, (2009). Study on Preemptive Real-Time Scheduling Strategy for Wireless Sensor Networks, Journal of Information Processing Systems, vol.5, no.3.

2. Zhou Yu, Jing Bo, (2007). Research and implementation on µC/OS-II operating system into wireless networked sensors, The Eighth International Conference on Electronic Measurements and Instruments, pp. 199-204.