Article Preview
TopIntroduction
Wireless sensor networks (WSNs) have recently become popular (Akyldiz, Su, Sankarasubramaniam, & Cayirci; 2002) because of their wide range of applications. Although WSNs have a lot of potential applications, there are still challenging problems that should be solved to meet real-world demands, i.e., higher instability, higher uncertainty, and lower power capacity as compared to conventional networks. Many methods have been proposed to solve these problems (Karl & Willig, 2005; Boulis, Ganeriwal, & Srivastava, 2003; Heinzelma, Chandrakasan, & Balakrishnan, 2000; Lim, Lam, Foo, & Zeng, 2006; Brown & Sreenan, 2006). These include not only basic protocols such as routing protocols (Karl & Willig, 2005), data aggregation (Boulis, Ganeriwal, & Srivastava, 2003), and energy management (Heinzelma, Chandrakasan & Balakrishnan, 2000) but also resource allocation (Lim, Lam, Foo, & Zeng, 2006) and software update (Brown & Sreenan, 2006). However, even if such network control technologies are introduced, a WSN cannot continue its monitoring service if some functions in the WSN are damaged. For example, if the sensor node (hereafter SN, or node) that coordinates a network is damaged and disappears suddenly, the WSN cannot be controlled, and its monitoring service breaks down.
In this paper, we propose a distributed algorithm to sustain the initial functionality of a WSN by dynamic function alternation even if some SNs are damaged. With this algorithm, the damaged function of a SN is dynamically taken over by a neighboring SN. Each SN calculates an indicator value that represents its suitability as a candidate to assume the function of the damaged node. Exchanging this indicator value with its neighboring nodes allows the SN with the largest indicator value to actually take over the function of the damaged node, and the damaged function is restored in the network.
The goal of the proposed algorithm is similar to that of a dynamic resource allocation problem in which the function (or task) performed by a SN is distributed to other SNs in a network when the condition of the network is changed. In WSNs, various algorithms have been proposed for the resource allocation problem (Lim, Lam, Foo, & Zeng, 2006; Mainland, Parkes, & Welsh, 2005; Giannecchini, Caccamo, & Shih, 2004). Although these provide smart methods to solve resource allocation problems, most of them are not suitable for our aim, which assumes frequent changes in network conditions. For example, Self-Organizing Resource Allocation (SORA) (Mainland, Parkes, & Welsh, 2005) can increase the network lifetime by optimizing the energy consumption of each node. In Mainland, Parkes and Welsh (2005), a SN has a local task, and when a SN cannot handle its task, it sells the task to the SN that offers the highest price among the SNs in the network. Here, the price is determined based on its energy and interests. However, because SORA assumes that a task is only sold by the SN that has the task, if a SN disappears suddenly, its task is never distributed and that function breaks down. The Adaptive Distributed Resource Allocation (ADRA) scheme (Giannecchini, Caccamo, & Shih, 2004) is also a good way to increase network lifetime. In ADRA, each SN has two statuses, “active” and “sleep.” The network lifetime can be extended by selecting one of these statuses for each SN. This is actually done in a distributed manner. ADRA can realize an optimal resource allocation in terms of power saving. However, the ADRA scheme changes the status of each node frequently to perform energy balancing; this often makes the network unstable. As compared to the aforementioned related works, the proposed algorithm has the following features: