Native Process Migration in Wireless Sensor Networks

1. Introduction

Wireless sensor networks (WSNs) are distributed networks of sensors nodes typically comprising of a large number of communicating nodes. A sensor node is designed to be physically small and of low cost; therefore it has limited computational power and small memory space. It is equipped with short range wireless radio [1] for exchanging sensed data to other nodes on the network. WSNs find their use in applications needing measurements and monitoring of environmental attributes such as temperature, humidity, light, pressure, sound, acceleration, orientation, vibration, smoke, radiation, and geographical location. They find their applications in health, medicine, military, environment, and industrial environments for measuring and monitoring physical attributes.

In WSN nodes failure is a very frequent and common phenomenon. If a node fails the process or data are lost. In case of physical destruction the data and programs cannot be recovered but in case of depleted batteries recovery is possible. As soon as the batteries life crosses a certain threshold the sensors can transfer data and code to another node having more energy or resources. It can transfer not only data and programs but also processes which have been processed partially and can save more energy.

Process migration is the task of moving a process between nodes during execution. Advantages of process migration include dynamic processing load distribution [2], improved fault tolerance [3], easier system administration, resource sharing, data access locality, and distributed computing [4].

Process migration is generally accomplished in the following generic three steps [4]: (a) suspending a process to be migrated at the source node, (b) sending process state, memory space, and executable code over the network to destination node, and finally (c) restoring process using information received from source at target node.

Process migration has been done in WSN in agent based systems such as Agilla using virtual environment. Virtual environment consumes resources which is an expensive overhead in WSN because of its very limited resources. An implication and comparison of energy consumption of different strategies including native and virtual machine based code execution are given in Dunkels et al. [5]. The authors have compared Java VM based code and a native code energy consumption and conclude that native code outperforms VM code in terms of energy efficiency for extended duration tasks. It is therefore established that native code is better at energy saving than agent code.

The work presented in this paper focuses on creation of a resource aware architecture for process migration in homogenous WSNs [6] without using virtual environment. The proposed process migration architecture enables native live (running) processes to migrate between nodes. We have used Contiki as a platform for implementing and experimenting with process migration and further extend runtime dynamic linking [5] in Contiki.

The rest of the paper is organized as follows. Section 2 reviews process migration in various operating systems as well as middleware and motivates the development of process migration in WSNs by highlighting several application scenarios for process migration in practical applications. Section 3 shows our proposed architecture for process migration in WSNs. Evaluation of our process migration architecture is presented Section 4. We also compare our architecture to other known architectures of WSNs in Section 4.1. Finally future work and conclusion are presented in Section 5.

2. Process Migration in WSN

This section presents a brief review of process migration. In the past process migration has been extensively used in heterogeneous and homogenous distributed systems [4, 7]. Recent efforts focusing on process migration include LinuxPMI [8] for Linux clusters, [9] CRIU (Checkpoint/Restore in Userspace) for Linux systems [9], DMTCP (Distributed Multithreaded Checkpointing) [10], and BLCR (Berkeley Lab Checkpoint/Restart) [11]. In smart phones and mobile computing a framework for migration of android application to Cloud has also been proposed [12].

Process migration architectures can be divided into two types. The first type of architectures is based on native process migration, whereas the second type of architectures is based on virtual machines where applications run on virtual machines and are migrated from one machine to another while the application is active. When a process has to be migrated, both the code and the current state of the process have to be transferred across the network. The most important components which are transferred are the following: data segment, code segment, stack segment, and resource handles (unique identifiers to resources on the system) such as open file and network sockets. In addition, process control-block contains instruction pointer, process priority, process metrics, and privileges, as well as thread control block. In the virtual machine based systems the applications are often implemented as agents.

An agent is a program which runs on a virtual machine. The use of virtual machine makes agent programs highly portable and more secure. The agent can move from one machine to another during execution on a virtual machine [7].

Agent and code migration have been implemented in various WSN middleware and operating systems. Table 1 gives a brief comparison of the WSN middleware and operating systems which include BerthaOS [13], MagnetOS [14], Agilla [15], Mate [16], and Contiki [17]. Several Java virtual machines have also been implemented on embedded systems which include AOT (Ahead-of-Time) compilation [18, 19], Darjeeling JVM [20, 21], and TakaTuka JVM [22, 23]. Agilla [15] is a middleware supporting self-adaptive applications for WSN using mobile agents and allows agents to move from one sensor node to another during execution. Besides WSNs, agents also find widespread roles in gathering high quality information on the Internet, such as database searches, online transactions in e-commerce, and system diagnostics [15].

OPEN IN VIEWER

Table 1

Comparison of WSN operating systems and middleware.

	TinyOS	BerthaOS	MagnetOS	Agilla	Mate	Contiki	Proposed system
Code migration	Yes	Yes	Yes	Yes	Yes	Yes	Yes
Process migration	No	No	No	Yes	No	No	Yes
Platform heterogeneity	No	No	Yes	Yes	Yes	No	No
Virtual machine	No	No	Yes	Yes	Yes	No	No
High energy and memory space consumption	No	No	Yes	Yes	Yes	No	No

Although agents are very useful, the primary disadvantage of agent based paradigm, such as Agilla, is execution inefficiency such that programs take longer time to execute because the program has to be interpreted by the virtual machine, thereby taking more time, using more energy, and using more memory space. In comparison, native code is much faster and uses less energy and space [5], and it can be suggested that short duration tasks are more suitable to be run as agents (virtual machine based application programs), while long running tasks should be executed as native code.

Being resource constrained, the sensor nodes can be affected by the following inherent vulnerabilities: (a)

Low battery.

Nodes with continuous energy source are better for running computationally intensive jobs when the battery is being charged and excess energy is used up for running application on sensor node. Moreover, on solar powered sensor nodes, some nodes may be under full sunlight, whereas some nodes might be in partial or full shade. For nodes which are not receiving sunlight, conserved use of battery is a requirement to remain functional for a longer duration. In such a situation, if there are several processes that are executing on the node, highly active processes should preferably be moved to those nodes that have continuous energy supply and might run the processes at full processor speed. This can help in preserving energy resources of those nodes which do not have access to continuous energy source such as sun. In addition, it is more efficient to compute information locally instead of sending it to base station.

Similarly memory is also of limited size and is very crucial resource in WSN. If a wireless sensor node is running several processing threads simultaneously, very little free memory may be left. In addition, if a process demands more memory which is not available on the host node, the requesting process can be migrated to another node having more memory.

Process migration can offer the following broad advantages in WSNs.

3. Process Migration Architecture

Although process migration is a relatively old feature in various Unix-like operating systems, no known process migration mechanism has been developed for any of the WSNs operating systems. The main component of all process migration architectures is process checkpoint and restore [9] mechanism. Checkpoint stores the state of a live running process and restore is responsible for restoring an instance of checkpointed process from stored state of a process. The process state data is typically stored in a file which is later on used for restoring the process. The file typically stores stack, heap, and registers. The restorer can recover the state of a process from this file and resume the execution of checkpointed process.

Checkpointing can be implemented by user library or may be provided as an operating system service. When implemented in operating system kernel as a service, it can facilitate the suspension and resumption of running process for very long durations over multiple reboots of machine. Example of actively developed system for checkpointing is CRIU (Checkpoint/Restore in Userspace) [27], which provides checkpoint/restore for Linux processes. CRIU allows the user to checkpoint and restore a running process or groups of processes. Checkpointing is the core component of process migration implementation. In our architecture checkpoint and restore have been implemented as a middleware service and are used for storing process execution state for a later resumption. Checkpoint and restore concept can be applied in wider context to the whole WSN. Brouwers et al. [21] present an architecture for checkpointing and restoring the state of full WSN.

The proposed architecture for process migration has been split into several individual components. Figure 1 shows the complete architecture of process migration middleware for WSNs. The architecture is based on generic steps common to all process migration system [4].

OPEN IN VIEWER

Figure 1

Process migration architecture for WSN.

The central component of our architecture is migration manager. It provides support and functionality for various tasks required in migration of a process, such as checkpointing, restoration, serialization, broadcasting, listening to incoming migration requests, and transportation of process code image and state data. The resource monitor has two responsibilities, estimating battery charge and monitoring free memory. Battery charge estimation is done by battery estimator which is responsible for predicting the amount of charge left in the battery and determines how much time the battery can sustain the node operation. It uses battery voltage sensor to periodically sample the battery voltage. The request broadcaster and listener component is responsible for broadcasting migration request to other nodes on the network. The listener waits for migration request broadcasts being “request broadcast listener.” It continuously listens to requests on broadcast channel. After the request has been received by the request broadcast listener it replies back with acceptance message to the sender. The sender then selects a target node and then transmits the process state and executable code using process code image transporter. After the process state and code have been received at the target node, the program loader initializes process space from image received, and then state deserializer restores process's local and global variables. After process has been restored on the target node, it is resumed by the migration manager by adding it to the scheduling queue.

Steps for migrating a process are shown by activity diagram in Figure 2.

OPEN IN VIEWER

Figure 2

Basic process migration control flow.

This is described in detail by steps (a) to (h). The Source_Migration_Manager suspends the process to be migrated and issues a migration request to Target_Migration_Manager which then replies with acceptance message. When the acceptance message is received by the Source_Migration_Manager, it saves a process image containing process code and state. The process image is sent to Target_Migration_Manager which then creates a new process and initializes it with the code and state of migrated process. Next the migrated process resumes execution. At the same time an acknowledgment of successful migration is sent to Source_Migration_Manager, which then destroys the original process. (a)

The source node wanting to migrate out a process continuously monitors its battery and memory space. The battery charge is estimated by sampling battery voltage at regular fixed intervals. In the event of detecting low battery power or memory space beyond a user specified threshold it initiates process migration procedure. Process migration begins with node “A” broadcasting a request for migrating a process P. Any node that has the requested resources available (such as battery) can send back acknowledgement. The reply from accepting node is sent using a unicast reply channel. The replying node first makes sure that it can accommodate the migrated process in memory and storage. After checking for resource availability, migration request is accepted or may be rejected in case resources cannot be allocated. The sender node selects the physically nearest destination node if multiple replies are received. On the receiver side, if multiple requests are received, they are processed in the order of arrival one at a time. Before proceeding to next request the receiver has to complete the current migration request.

Algorithm 1: Algorithm for sender node.

Algorithm 2: Algorithm for receiver node.

4. Implementation and Evaluation

The implementation of process migration architecture was tested on COOJA [17]. The communication between nodes was achieved using Contiki's Rime Communication Stack. The main thread in the program named pmig_process opened broadcast channels and unicast channels and performed node monitoring and managed the process migration steps. The first program tested was the LED blinker program which migrated for several times between randomly selected nodes.

In Figure 3 the lower panel of COOJA simulator window shows the led blinking on node 1 and node 2. Half of the red-led blinks are on node 1 and remaining half are on the node 2 after migration completed which was initiated while the blinker process was running at node 1.

OPEN IN VIEWER

Figure 3

Process migration between two nodes in COOJA.

We also tested the proposed process migration system on a test bed of 25 TelosB nodes. In our implementation on TelosB nodes, we measured battery voltage using battery sensor in TelosB mote. Multiple readings were averaged to get approximate voltage reading. The measured voltage was used for estimating the battery remaining charge percentage.

4.1. Comparison with Related Architectures

In practical scenarios, nodes may be physically unreachable and reprogramming of the sensor nodes can be impossible or very difficult. To enable reconfiguration and reprogramming of software on WSN nodes, WSN middleware provides code management. Table 2 shows comparison of our work with other architectures including Dunkels et al. [17], Agilla [15] based on Mate [16], Darjeeling JVM [20, 21], and TakaTuka JVM [22, 23] for wireless sensor motes.

OPEN IN VIEWER

Table 2

Comparison of proposed process migration architecture with other architectures.

	TakaTuka VM [22, 23]	Darjeeling [20, 21]	Dunkels et al. [17]	Agilla [15]	Proposed architecture
Based on Agents	No	No	No	Yes	No
Virtual machine	Yes (JVM)	Yes (JVM)	No	Yes	No
Dynamic linking and loading	Yes	Yes	Yes	Yes	Yes
Compact ELF	Class file(s)	Class file(s)	Yes	No	Yes
Live transfer	No	No	No	Yes	Yes
State transfer	No	No	No	Yes	Yes
Resource monitoring	No	No	No	No	Yes
Energy aware	No	No	No	No	Yes
Live process migration	No	No	No	Yes	Yes

4.1.1. Code Migration

Code management in WSNs is typically achieved by code migration [16, 28] which allows the migration of application code from one node to another. This facilitates the remote installation of the software on nodes with ease and without the need of having physical access to nodes. Our implementation differs from code migration, because in addition to code migration it also supports the migration of the execution state which means that the whole process state is migrated. This allows the execution of migrated process to be resumed seamlessly on a different host node after migration has completed. This saves precious resources from being wasted.

4.1.2. Virtual Machine Agents

Process migration uses code migration. It incorporates the migration or transfer of state of executing process along with code from one sensor node to another in the WSN. By definition a live process has both native executable code image and state. The main focus in this work has been on the migration of natively executable processes along with state so that after migration the migrated process can resume execution at the target node. The native code is faster and more energy efficient [5]. This is similar to agent based systems in which code as well as the state of executing agent is migrated; however agent code is run on virtual machine and the code has to be interpreted at runtime. Therefore it requires extra resources to run the virtual environment.

An example of this strategy is Agilla [15] middleware which allows the mobile agents running on a byte code interpreter virtual machine to migrate state and executable code from one node to another node at runtime. It has been suggested that migrating small executable code modules consume less energy than a full application [29] and for shorter tasks this strategy is energy efficient, but for long running tasks the nature of code interpretation makes it less energy efficient. In real world situations virtual machine based applications typically consume more resources including time, space, and energy than the native applications. A comparison of the running times of different algorithms has been provided by Ellul [18, 19] and summarized in Table 3, which benchmarks Ahead-of-Time (AOT) compilation, with native and TakaTuka JVM. The increased time of execution indicates more energy consumed compared to native code.

OPEN IN VIEWER

Table 3

Comparison of VM with native code [18, 19] using BubbleSort16 benchmark for sorting 256 values.

	Execution time	Binary size	Energy consumed
TakaTuka	120 seconds	1050 bytes	587.76 mJ
AOT	13 seconds	110 bytes	63.67 mJ
Native Code	2 seconds	230 bytes	9.769 mJ

4.1.3. Long Running Tasks

Levis and Culler [16] suggest that it is more energy efficient to implement long running and complex application programs with frequent executions as native code rather than as virtual machine based code, because of the overhead caused by virtual machine's interpreted execution. Furthermore the energy saving in the long term outweighs the energy consumed during the migration of large and complex processes needing frequent executions. The authors recommend that for smaller applications with small sized executable code and frequent migration requirements mobile agents are suitable. And for larger and complex applications, process migration is preferred.

5. Conclusion and Future Work

This paper proposed architecture for native process migration in WSNs. The proposed architecture incorporates resource monitoring and dynamic process migration. This architecture improves fault tolerance and energy consumption of a WSN network without using virtual environment which is an extra burden. We have tested and implemented our architecture on both simulation and real test bed using Contiki and TelosB successfully.

In the future we will incorporate a security mechanism in our architecture to make native process migration secure. Energy consumption can also be improved even further in the proposed architecture by using a compression algorithm for compressing process images before transfer takes place; see Ansel et al. [10]. We also intend to work on solving resource dependency problem and on improving resource monitoring to better estimate the resource capacity of wireless sensor nodes.