# An Immune Cooperative Particle Swarm Optimization Algorithm for Fault-Tolerant Routing Optimization in Heterogeneous Wireless Sensor Networks

Authors: Yifan Hu; Yongsheng Ding; Kuangrong Hao
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

The fault-tolerant routing problem is important consideration in the design of heterogeneous wireless sensor networks (H-WSNs) applications, and has recently been attracting growing research interests. In order to maintaink disjoint communication paths from source sensors to the macronodes, we present a hybrid routing scheme and model, in which multiple paths are calculated and maintained in advance, and alternate paths are created once the previous routing is broken. Then, we propose an immune cooperative particle swarm optimization algorithm (ICPSOA) in the model to provide the fast routing recovery and reconstruct the network topology for path failure in H-WSNs. In the ICPSOA, mutation direction of the particle is determined by multi-swarm evolution equation, and its diversity is improved by immune mechanism, which can enhance the capacity of global search and improve the converging rate of the algorithm.  Then we validate this theoretical model with simulation results. The results indicate that the ICPSOA-based fault-tolerant routing protocol outperforms several other protocols due to its capability of fast routing recovery mechanism, reliable communications, and prolonging the lifetime of WSNs.


---

## Body

## 1. Introduction

The complex networks have attracted growing research interests in topology structure and dynamic problems. Many kinds of system can be described with the complex network model, and these models are constructed by several nodes connected with each other, such as the Internet and the wireless sensor networks (WSNs). Due to the ability of collecting data from the environment and reporting it back to the sink without human supervision [1, 2], WSNs, especially heterogeneous ones, have come to pervade every aspect of our lives, such as habitat monitoring, industrial sensing, and traffic control [3–5]. The heterogeneous WSNs always deploy an appropriate number of heterogeneous wireless sensor nodes (called macronodes), which contain devices with more capabilities, storage space, and energy than ordinary nodes. They cannot only improve the success rate of data transmission of WSNs, but also reduce the energy consumption of transmission, thus can effectively prolong the network lifetime. The benefits of using heterogeneous WSNs (H-WSNs) have been presented in the literature [6–9]. It is reported that when properly deployed, heterogeneity can triple the average delivery rate and provide a fivefold increase in the network lifetime [6].However, in practical applications, unpredictable events such as environmental impairment, communication link broken, and battery depletion may cause the sensor devices to fail, partitioning the network and disrupting network functions. Therefore, fault tolerance becomes a critical issue for the successful communication of H-WSNs. It is expected that the network topology broken by software or hardware failure of sensor nodes could be automatically reconstructed and self-healed by the fault-tolerant routing technology so as to be recovered from path failure and ensured the performance of the communication tasks.The objective of this paper is to solve the fault-tolerant routing problem for the H-WSNs while maintainingk disjoint communication paths from each source sensor to the macronode it belongs to (called k-disjoint-path routing recovery problem). For this purpose, we propose a swarm intelligence algorithm, immune cooperative particle swarm optimization algorithm (ICPSOA), to provide fast recovery from path failure in the H-WSNs. In this way, the network can tolerate the failure of up to k-1 sensor paths with reconstructed topology, traditional retransmissions can be decreased, and reliability can be provided with lower energy consumption. Our problem is specifically tailored to the situation that data is forwarded from sensors to macronodes.The main contributions of this paper are as follows: firstly, we formulate thek-disjoint-path routing recovery problem for the H-WSNs. Then, in order to maintain k disjoint communication paths from each source sensor to the set of macronodes, we propose the ICPSOA-based protocol to reconstruct the network topology and provide fast routing recovery from path failure in the H-WSNs. The proposed method can provide simplicity, robustness, and effectiveness for routing recovery problem of the WSNs.The remainder of this paper is organized as follows: Section2 overviews the related work on fault-tolerant routing problem, especially routing recovery problem in the H-WSNs. Then, we propose the H-WSNs architecture and fault model and the ICPSOA-based approach for solving the routing recovery problem in Section 3. The simulation results are presented in Section 4. Section 5 provides a conclusion of our paper and discusses a few future directions for further improving the performance of our approach.


## 2. Related Work

### 2.1. The Fault-Tolerant Routing Algorithms of WSNs

Fault-tolerant routing protocols proposed for WSNs can be classified into three groups: (1) proactive routing, called disjoint multipath, in which several paths from source node to sink are calculated, maintained in advance, and stored in a routing table, but greater energy consumption and the requirement to predict the global topology information are the disadvantages [10–12], (2) reactive routing, where all paths are created on demand [7], and (3) hybrid routing, which is a mix of the above two groups [8, 9].One of the common fault-tolerant routing solutions is to establish disjoint multipath with proactive routing mechanism. Disjoint multipath constructs a number of alternative paths which are node/links disjoint with the primary path and other alternative paths. Thus, a failure in any or all nodes/links on the primary path does not affect the alternative paths. Using this multipath scheme in a network withk disjoint paths from source to destination can tolerate at most k-1 intermediate network component failures. A secure and energy-efficient multipath routing protocol proposed by Nasser and Chen [10] is effectively resistive to some specific attacks, and has the character of pulling all traffic through the malicious nodes by advertising an attractive route to the destination.A considerable amount of work has also been done on the hybrid routing scheme, which combines multipath scheme and reactive routing scheme. In this scheme, multiple paths are calculated and maintained in advance, and then, alternative paths are created on demand. EARQ (energy-aware routing for real-time and reliable communication) is a hybrid routing scheme proposed by Heo and Hong [9], which selected a path that expended less energy than others, among paths that delivered a packet in time, which enabled even distribution of energy expenditure to sensor nodes. It also provided reliable communication and fast recovery from path failure, because it only sent a redundant packet via an alternative path if the reliability of a path was less than a predefined value. Pandana and Liu [11] sought to propose an algorithm which designed the connectivity weight of each node and established a most reliable path in order to keep the other nodes’ connectivity.Our work differs from the above existing ones [13–16] by considering a different architecture and routing objective. We consider the H-WSNs architecture with a number of macronodes and concern with providing k-connectivity from each source node to the set of macronodes, and as such, we provide a hybrid routing scheme to maintain the multipath routing. The H-WSNs usually consist of two types of wireless devices [12]: a large number of resource-constrained wireless sensor nodes deployed randomly and a much smaller number of resource-rich macronodes placed at known locations. The macronode network, which provides more energy, transmission bandwidth, computing ability, and storage space, is used to quickly forward sensor data packets to the sink. With this setting, data gathering in the H-WSNs has two steps. Firstly, sensor nodes transmit and relay information on multihop paths toward any macronode. Then, it is forwarded to the sink using fast macronode-to-macronode communication once a packet encounters a macronode.The similar hybrid routing schemes for the H-WSNs are as follows: CPEQ (cluster-based periodic, event-driven, and query-based protocol) [17] groups sensor nodes to efficiently relay data to the sink by uniformly distributing energy dissipation among the nodes. It can provide fast broken path reconfiguration and high reliability in the delivery of event packets and speed up new subscriptions by using the reverse path. Cardei and Yang [18] proposed GATCk and DATCk in the H-WSNs, with the objective of minimizing the total energy consumption while providing k independent paths from each node to macronodes. Such a topology provides the infrastructure for fault-tolerant data-gathering applications robust to the failure of up to k-1 sensors. Boukerche et al. [8] used a protocol of ICE (intercluster communication-based energy-aware and fault-tolerant protocol) by alternating the nodes responsible for intercluster communication inside one cluster. If one of multiple paths has faulty nodes, the other ones will be used for the event notification’s propagation. But the fast routing recovery mechanism for path failure has rarely been considered. Further, as the fault-tolerant optimization problem to find the optimal routing is NP-hard, these heuristic deterministic methods would always get the likely optimal routing result, and is easy to fall into local optimum. So, we employ a swarm intelligence algorithm, the ICPSOA, to improve the performance of solving these problems.In this paper, we propose an ICPSOA-based fault-tolerant routing algorithm, which reconstructs the network topology of H-WSNs and provides a fast recovery from path failure with alternative path. We also compare the performance of the protocols of EARQ, CPEQ, and ICE with that of our approach. As we known, EARQ is an effective fault-tolerant routing protocol for homogeneous WSNs, while ICE and CPEQ are for H-WSNs to provide routing recovery from path failure. In this way, we can evaluate the fault-tolerant routing recovery mechanism with different network types.


### 2.2. SPSOA, CPSOA, and ICPSOA

The EA-based bionic randomized algorithm has become the important tools for solving complex optimization problems because of its intelligence and widely used and global search ability. But the algorithm dealing with fault-routing problem of WSNs should support the characteristic of energy saving. In general, better fault-tolerant performance always needs more energy consumption. Therefore, we choose light-weight algorithm based on the particle swarm optimization algorithm (PSOA), which has a simple structure and is easy to realize.The PSOA is a new EA based method to search an optimal solution in the high-dimensional problem space [13], where each particle is a potential solution to the problem under analysis. In updating a population of particles with regard to their internal position and velocity, the PSOA is informed by the experiences of all the particles. It provides an idea to find solutions to complex problems using group advantage without global model and centralized control and can be suitable to apply in a dynamical modeling environment. It has been applied to many optimization problems, such as control problems and protocol design [14]. A remarkable difference between the PSOA and other EA-based algorithms is that the PSOA is very simple and has few parameters to be adjusted. Therefore, in general, it requires less computational complexity.In the standard PSOA (SPSOA), each particle is a potential solution to the problem. AssumeN particles fly in the D-dimensional search space, the position of the ith particle is xit=(xi1t,xi2t,…,xiDt)T, and its velocity is vit=(vi1t,vi2t,…,viDt)T. pi=(pi1t,pi2t,…,piDt) is the best previous position of the particle, and pg is the global best position of the whole particle swarm. Therefore, the velocity and position of each particle will be updated according to [15](2.1)vidt+1=wvidt+c1rand1(pidt-xidt)+c2rand2(pgdt-xidt),xidt+1=xidt+vidt+1,
where 1≤d≤D, c1 and c2 are learning factors, and usually, we make c1=c2=2; w is the inertia weight and used to control the tradeoff between the global and local exploration ability of the swarm. Random numbers rand1 and rand2 are uniformly distributed in [0,1].The SPSOA also exhibits several disadvantages: it sometimes posses the problem of converging to undesired local optimum, for the diversity of population decreases in the latter iteration of evolution; optimizing stops when reaching a likely optimal solution, and thus the accuracy of the algorithm is limited. Therefore, a cooperative PSOA (CPSOA), which uses cooperative behavior of multiple swarms to improve the SPSOA, is proposed in [16]. In the CPSOA, limitation of an individual can be compensated by a number of other individuals from other symbiotic groups in the interaction. It can avoid misjudgment caused by single exchange of information [16]. However, it still uses the formula of the SPSOA to evolve. The trajectory of each particle is unable to yield high diversity of particles to increase search space. Therefore, the CPSOA may get a suboptimal solution.For this reason, we draw on good diversity characteristic of immune mechanism and develop an immune CPSOA (ICPSOA), in which each particle is considered as an antibody. Particle clone is used to generate a new population with offspring. Mutation is used to diversify the search process. Immune restrain is considered to restrain the inferior ones in order to keep the stable population. Immune memory is used to store the feasible solutions [19]. The affinity between antibody and antigen can measure the optimal path, and the affinity between antibodies and antibodies can evaluate the diversity of population [20]. In the ICPSOA, mutation direction of the particle (called antibody) is determined by evolution equation, and its diversity is increased by immune mechanism [21]. Although the addition of the immune mechanism may add more time complexity to the system, the proposed ICPSOA largely improves the capability of jumping out of local optima. The use of the ICPSOA for the fault-tolerant routing problem in H-WSNs has been presented in the following sections.


## 2.1. The Fault-Tolerant Routing Algorithms of WSNs

Fault-tolerant routing protocols proposed for WSNs can be classified into three groups: (1) proactive routing, called disjoint multipath, in which several paths from source node to sink are calculated, maintained in advance, and stored in a routing table, but greater energy consumption and the requirement to predict the global topology information are the disadvantages [10–12], (2) reactive routing, where all paths are created on demand [7], and (3) hybrid routing, which is a mix of the above two groups [8, 9].One of the common fault-tolerant routing solutions is to establish disjoint multipath with proactive routing mechanism. Disjoint multipath constructs a number of alternative paths which are node/links disjoint with the primary path and other alternative paths. Thus, a failure in any or all nodes/links on the primary path does not affect the alternative paths. Using this multipath scheme in a network withk disjoint paths from source to destination can tolerate at most k-1 intermediate network component failures. A secure and energy-efficient multipath routing protocol proposed by Nasser and Chen [10] is effectively resistive to some specific attacks, and has the character of pulling all traffic through the malicious nodes by advertising an attractive route to the destination.A considerable amount of work has also been done on the hybrid routing scheme, which combines multipath scheme and reactive routing scheme. In this scheme, multiple paths are calculated and maintained in advance, and then, alternative paths are created on demand. EARQ (energy-aware routing for real-time and reliable communication) is a hybrid routing scheme proposed by Heo and Hong [9], which selected a path that expended less energy than others, among paths that delivered a packet in time, which enabled even distribution of energy expenditure to sensor nodes. It also provided reliable communication and fast recovery from path failure, because it only sent a redundant packet via an alternative path if the reliability of a path was less than a predefined value. Pandana and Liu [11] sought to propose an algorithm which designed the connectivity weight of each node and established a most reliable path in order to keep the other nodes’ connectivity.Our work differs from the above existing ones [13–16] by considering a different architecture and routing objective. We consider the H-WSNs architecture with a number of macronodes and concern with providing k-connectivity from each source node to the set of macronodes, and as such, we provide a hybrid routing scheme to maintain the multipath routing. The H-WSNs usually consist of two types of wireless devices [12]: a large number of resource-constrained wireless sensor nodes deployed randomly and a much smaller number of resource-rich macronodes placed at known locations. The macronode network, which provides more energy, transmission bandwidth, computing ability, and storage space, is used to quickly forward sensor data packets to the sink. With this setting, data gathering in the H-WSNs has two steps. Firstly, sensor nodes transmit and relay information on multihop paths toward any macronode. Then, it is forwarded to the sink using fast macronode-to-macronode communication once a packet encounters a macronode.The similar hybrid routing schemes for the H-WSNs are as follows: CPEQ (cluster-based periodic, event-driven, and query-based protocol) [17] groups sensor nodes to efficiently relay data to the sink by uniformly distributing energy dissipation among the nodes. It can provide fast broken path reconfiguration and high reliability in the delivery of event packets and speed up new subscriptions by using the reverse path. Cardei and Yang [18] proposed GATCk and DATCk in the H-WSNs, with the objective of minimizing the total energy consumption while providing k independent paths from each node to macronodes. Such a topology provides the infrastructure for fault-tolerant data-gathering applications robust to the failure of up to k-1 sensors. Boukerche et al. [8] used a protocol of ICE (intercluster communication-based energy-aware and fault-tolerant protocol) by alternating the nodes responsible for intercluster communication inside one cluster. If one of multiple paths has faulty nodes, the other ones will be used for the event notification’s propagation. But the fast routing recovery mechanism for path failure has rarely been considered. Further, as the fault-tolerant optimization problem to find the optimal routing is NP-hard, these heuristic deterministic methods would always get the likely optimal routing result, and is easy to fall into local optimum. So, we employ a swarm intelligence algorithm, the ICPSOA, to improve the performance of solving these problems.In this paper, we propose an ICPSOA-based fault-tolerant routing algorithm, which reconstructs the network topology of H-WSNs and provides a fast recovery from path failure with alternative path. We also compare the performance of the protocols of EARQ, CPEQ, and ICE with that of our approach. As we known, EARQ is an effective fault-tolerant routing protocol for homogeneous WSNs, while ICE and CPEQ are for H-WSNs to provide routing recovery from path failure. In this way, we can evaluate the fault-tolerant routing recovery mechanism with different network types.


## 2.2. SPSOA, CPSOA, and ICPSOA

The EA-based bionic randomized algorithm has become the important tools for solving complex optimization problems because of its intelligence and widely used and global search ability. But the algorithm dealing with fault-routing problem of WSNs should support the characteristic of energy saving. In general, better fault-tolerant performance always needs more energy consumption. Therefore, we choose light-weight algorithm based on the particle swarm optimization algorithm (PSOA), which has a simple structure and is easy to realize.The PSOA is a new EA based method to search an optimal solution in the high-dimensional problem space [13], where each particle is a potential solution to the problem under analysis. In updating a population of particles with regard to their internal position and velocity, the PSOA is informed by the experiences of all the particles. It provides an idea to find solutions to complex problems using group advantage without global model and centralized control and can be suitable to apply in a dynamical modeling environment. It has been applied to many optimization problems, such as control problems and protocol design [14]. A remarkable difference between the PSOA and other EA-based algorithms is that the PSOA is very simple and has few parameters to be adjusted. Therefore, in general, it requires less computational complexity.In the standard PSOA (SPSOA), each particle is a potential solution to the problem. AssumeN particles fly in the D-dimensional search space, the position of the ith particle is xit=(xi1t,xi2t,…,xiDt)T, and its velocity is vit=(vi1t,vi2t,…,viDt)T. pi=(pi1t,pi2t,…,piDt) is the best previous position of the particle, and pg is the global best position of the whole particle swarm. Therefore, the velocity and position of each particle will be updated according to [15](2.1)vidt+1=wvidt+c1rand1(pidt-xidt)+c2rand2(pgdt-xidt),xidt+1=xidt+vidt+1,
where 1≤d≤D, c1 and c2 are learning factors, and usually, we make c1=c2=2; w is the inertia weight and used to control the tradeoff between the global and local exploration ability of the swarm. Random numbers rand1 and rand2 are uniformly distributed in [0,1].The SPSOA also exhibits several disadvantages: it sometimes posses the problem of converging to undesired local optimum, for the diversity of population decreases in the latter iteration of evolution; optimizing stops when reaching a likely optimal solution, and thus the accuracy of the algorithm is limited. Therefore, a cooperative PSOA (CPSOA), which uses cooperative behavior of multiple swarms to improve the SPSOA, is proposed in [16]. In the CPSOA, limitation of an individual can be compensated by a number of other individuals from other symbiotic groups in the interaction. It can avoid misjudgment caused by single exchange of information [16]. However, it still uses the formula of the SPSOA to evolve. The trajectory of each particle is unable to yield high diversity of particles to increase search space. Therefore, the CPSOA may get a suboptimal solution.For this reason, we draw on good diversity characteristic of immune mechanism and develop an immune CPSOA (ICPSOA), in which each particle is considered as an antibody. Particle clone is used to generate a new population with offspring. Mutation is used to diversify the search process. Immune restrain is considered to restrain the inferior ones in order to keep the stable population. Immune memory is used to store the feasible solutions [19]. The affinity between antibody and antigen can measure the optimal path, and the affinity between antibodies and antibodies can evaluate the diversity of population [20]. In the ICPSOA, mutation direction of the particle (called antibody) is determined by evolution equation, and its diversity is increased by immune mechanism [21]. Although the addition of the immune mechanism may add more time complexity to the system, the proposed ICPSOA largely improves the capability of jumping out of local optima. The use of the ICPSOA for the fault-tolerant routing problem in H-WSNs has been presented in the following sections.


## 3. Fault-Tolerant Routing Problem in H-WSNs Based on the ICPSOA

### 3.1. Model of the Proposed H-WSNs

#### 3.1.1. The Architecture for the Model of H-WSNs

The architecture for the model of H-WSNs contains two types of wireless sensor devices as shown in Figure1. The lower layer is formed by sensor nodes with constrained resource, including small amount of source nodes and other relay nodes. The main tasks performed by the source nodes are sensing, data processing, and data transmission. The tasks performed by the relay nodes are data processing and relaying. The dominant energy consumer is the radio transceiver. The upper layer consists of resource-rich macronodes overlaid on the H-WSNs. Wireless communication links between macronodes have considerably longer ranges and higher data rates, allowing the macronode network to bridge remote regions of the interest area. The tasks performed by a macronode are data aggregation and transmission, complex computations, and decision making. The ICPSOA is also executed by macronodes.Figure 1
The architecture of H-WSNs.Therefore, in-network data transmission can be performed by forming a spanning tree among all the tree nodes. As shown in Figure1, transmission starts with the leaf nodes (source node) of the tree sending their values to their parent nodes (macronode, nodes 1,2,…,12) in the tree, until the final data is obtained at the root node (sink, node 13). Thus, the overall architecture would have a tree of macronodes and then each macronode can serve as the root of a subtree of ordinary nodes. Here, we are only interested in the fault-tolerant routing between sensor-sensor and sensor-macronode communications.Assume that the network has the following characters: (1) the H-WSNs is a static network, where the nodes will not move after deployment, (2) every node knows its own position and that of the macronodes and the sink. The location can be obtained by GPS or localization protocols for estimating the location of a node, (3) the wireless transmission energy of macronode can be adjusted based on the distance between the receiver and itself, (4) the adjacent nodes would acquire the state information of their 1-hop neighbors and the links between them through periodically broadcast. The meanings of used symbols is provided in Table1.Table 1
The main symbols.
STiTheith subtree of the tree of the H-WSNsNSToThe number of the sensor nodes inSTiPSTsThe state information of all the nodes inSTinsOne of the source nodes inSTinrThe root node (macronode) inSTiP(s,r)The set of all the possible paths betweenns and nr in STipi(s,r)Theith path between ns and nr in STinfailThe failed relay node ofpi(s,r) in STinfail-cThe child node ofnfail of pi(s,r) in STinfail-pThe parent node ofnfail of pi(s,r) in STiniTheith sensor node of pi(s,r) in STipbThe optimal path ofP(s,r) with optimal fitness in STinpbiTheith sensor node of pb in STi


#### 3.1.2. Thek-Disjoint-Path Spanning Graph in the Subtree

The subtreeSTi of the network is modeled as a directed, connected graph G(V,E), where V is a finite set of subtree nodes and E is the set of subtree edges representing connection between these nodes, where source node ns∈V and macronode (root) nr∈{V-{ns}}. pi(s,r) is a valid path between ns and nr, and P(s,r) is the set of all the paths pi(s,r).n(n∈pi(s,r)) represents a node in pi(s,r), and e(e∈pi(s,r)) represents direct edge between any two adjacent nodes in pi(s,r). Then, we can get the k-disjoint-path spanning graph in the subtree STi. The factors affecting the choice of path pi(s,r) include (1) the available energy function of each node, ene(n), (2) distance function of the edge between adjacent nodes, dist(e), (3) energy consumption function, ene(e), (4) communication delay function of the node, delay(n). Then, these parameters can determine the fitness function of pi(s,r), fitness(pi)(3.1)fitness(pi)=∑n∈pi(s,r)ene(n)ω1f1+ω2f2+ω3f3,f1=∑e∈pi(s,r)ene(n)∑e∈Eene(n),f2=∑n∈pi(s,r)delay(n)∑n∈Ndelay(n),f3=∑e∈pi(s,r)dist⁡(e)∑e∈Edist⁡(e),
where f1 is the ratio of the energy consumed by the edges of path pi and the energy consumed by all the edges in the subtree, f2 is the delay of the edges and nodes of path pi versus the delay of all the nodes in the subtree, and f3 is the distance of the edges of path pi versus the distance of all the edges in the subtree. ω1,ω2,ω3 are the weight of effective energy, delay and distance constraints in the fitness function, and ω1+ω2+ω3=1. We set ω1=0.4, ω2=0.2, ω3=0.4. The higher fitness value indicates the more suitable path.As illustrated in Figure2, we assume k=3, the three disjoint paths between source node (node 2) and root (node 30) are 2-3-9-15-20-25-28-30, 2-8-13-18-23-30, and 2-7-12-16-21-27-30, respectively. The detailed protocol dealing with routing recovery problem is presented in the following sections.Figure 2
k-disjoint-path spanning graph in subtree.


#### 3.1.3. The Proposed Fault Model and Energy Model

We use the simple fault model proposed in [22] and identify the node failure in it. The fault-model should be simple enough to analyze, but also sophisticated enough to capture the fault behavior effectively. The probability of sensor nodes failure of subtree is given by pnode. As we use the more reliable macronodes to sustain the failure during transmission process, the probability of macronode failure is assumed to be pmacro≈0. If any of the sensor nodes fails, our routing recovery approach for node failure in subtree can be implemented.We introduce the energy model adopted in [18], and the equation of energy model of a sensor node is as follows:(3.2)ene(m,d)=enetx(m,d)+enerx(m)=(a11+a2dn)m+a12m,
where d is the distance from the sensor node to the next-hop node, enetx(m,d) and enerx(m) are the energy consumption of sending and receiving m bits of data, a11, a2, and a12 are energy consumption parameters of sending circuit, sending amplifier, and receiving circuit, and n is the channel attenuation index. We also define eneDF as energy consumption of data fusion and eneRT as energy consumption of updating routing table. For the ICPSOA, we define energy consumption of paticle update, immune clone, mutation, particle selection, and restrain per iteration as enePU, eneIC, eneIM, enePS, and enePR, respectively. So, the total consumption of the ICPSOA is according to the actual iterated generations per round.


### 3.2. Fault-Tolerant Routing Problem Using the ICPSOA

As described in Section2.2, the ICPSOA is used to provide a fast recovery mechanism from path failure due to physical damage or energy depletion with an alternative path. It chooses a path with optimal fitness from the optional sensor nodes. The ICPSOA is the kernel of our fault-tolerant routing protocol. Its flowchart is shown in Figure 3, and its framework is shown in Algorithm 1. The detailed procedures are described in the following subsections.Algorithm 1:The ICPSOA for fault-routing problem.
Input: PSTo: The information parameters of nodesPGen: The iterated generations for searching processOutput: fitness(pi): The global optimal fitnessProcess:Step 1: Initialization: Generate initial particle swarm parameter.Step 2: Immunization: Immune clone, mutation, particle selection and restrain.Step 3: If termination criterion conditions are satisfied, go to  Step 5; elsego toStep 4.Step 4: Update: Update the velocity and position of each sub-swarm and particle.Step 5: Output: Output the global optimal fitness of the particle swarm. Ends.Figure 3
The architecture of the ICPSOA for the H-WSNs.(1) Initialization
The principle of the ICPSOA is to search, respectively, in differentD-dimensional target spaces using k independent particle swarms. To initialize the algorithm, we set the population size of particle n, the division factor k, and each particle swarm includes n/k particles. Then, the D-dimensional vector (vector of particle’s position and velocity) is divided into k swarms. We define a matrix by [D×2n] to represent the initial particle swarm, in which the former n columns are the position of particle, and the latter n columns are the velocity of particle.In Algorithm2, b(g) is a complete vector function consisting of all subswarms’ optimal position vector, xmSi represents position vector of the mth particle in the ith swarm, pmSi is the optimal history position vector of the mth particle in the ith swarm, and pgSi represents optimal experience position vector of the ith swarm.Algorithm 2:Initialization mechanism in the ICPSOA.
Input: PSTo: The information parameters of nodesn: The population size of particlek: The population size of swarmOutput: Si: The vector of the ith particle swarmb(g): Each sub-swarm’s optimal position vector functionProcess:Particle’sD-dimensional vector is divided into k particle swarms.b(L,i)=(pgS1,…,pgSi-1,L,pgSi+1,…,pgSk)(2) Immunization
In this step, each particle can be considered as an antibody, resulting in the clonal mutation setC. The clone number and the fitness of particle are proportional. The clonal number Nc is usually calculated as follows:
(3.3)Nc=αN,
where α is the clone factor and is proportional to particle’s fitness value. N is the number of particles. Mutation rule can be setup according to experience. The particle mutation rule for the function optimization problem is
(3.4)ci=xi+βrand,
where ci is the clonal individual, xi is the original antibody, β represents the mutation factor, and rand is uniformly distributed in [0,1].For the particles replacement rule, we need to calculate the antigen stimulus degree of the original particles and select clonal mutation particles. The Euclidean distance between any particleCt and antigen Yt is (3.5)d(i,j)=∑i=1n(cit-yjt)2.Therefore, the stimulus degree of antibody particle is(3.6)A(i,j)=1d(i,j).After that, each particle is compared with stimulus threshold; the higher one will maintain in the subswarm, and the lower one will be replaced (called restrain). The process of this step is as shown in Algorithm3. Then, go to Step 2 in Algorithm 1.Algorithm 3:Immune mechanism in the ICPSOA.
Input: n: The population size of particlesPGen: The iterated generations for searching processk: The population size of swarmOutput:The allele of the offspring’s antibodies (particles)Process:For each swarm i∈[1⋯k]For each particle m∈[1⋯n/k]Clone operation: Nc=αNMutation operation: ci=xi+βrandReplacement (restrain) operation:d(i,j)=∑i=1n(cit-yjt)2, A(i,j)=1/d(i,j)If A(i,j)> threshold, the particle (antibody) is replacedEnd ForEnd For(3) Termination Criterion
If the solution is satisfied with the termination criterion,fitness(pi) is the optimal fitness or PGen decreases to zero, the optimal path pi will be the desired optimal solution, and this procedure ends; otherwise, returns to Step 4 in Algorithm 1. Then, the kth path is established.(4) Update
In this step, the velocity and position of the particle is updated as (2.1). The process is as shown is Algorithm 4. The updating equation of particles’ optimal position vector in each subswarm is as follows:
(3.7)b(pmSi,i)={b(xmSi,i),fitness(b(xmSi,i))≥fitness(b(pmSi,i)),b(pmSi,i),fitness(b(xmSi,i))<fitness(b(pmSi,i)),
where 1≤i≤k. The updating equation of optimal position of each subswarm is(3.8)b(pgSi,i)=argP(pmSi,i)max fitness(b(pmSi,i)),1≤m≤nk,1≤i≤k.Algorithm 4:Update mechanism in the ICPSOA.
Input: PSTo: The information parameters of nodesSi: The ith particle swarmb(L,i): Each sub-swarm’s optimal position vector functionPGen: The iterated generations for searching processOutput:vidt+1and xidt+1: The velocity and position of each sub-swarm and its particlefitness(pi): The global optimal fitnessProcess:Foreach swarm i∈[1⋯k]For each particle m∈[1⋯n/k]Update velocity and position of each sub swarm’s particleIffitness(b(xmSi,i))≥fitness(b(pmSi,i)),  b(pmSi,i)=b(xmSi,i)Else Iffitness(b(xmSi,i))<fitness(b(pmSi,i)),b(pmSi,i)=b(pmSi,i)Calculate fitness(pi) of the particle (path)End Forb(pgSi,i)=argP(pmSi,i)maxfitness(b(pmSi,i))End ForEquation (3.8) indicates that the optimal position of the mth subswarm will select the personal optimal position with the optimal fitness of particle in the swarm.Inertia weightw plays an important role to the convergence of the result among the adjustable parameters. The larger weight can help the particle escape from the local best solution, and the smaller one is better for the convergence, thus the inertia weight can achieve balance between global search and local search. To overcome the limitations of other general strategies, the linear differential decreasing strategy is used [23]. Here, we select wstart=0.85, wend=0.35(3.9)dw(t)dt=2(wstart-wend)tmax⁡2t,w(t)=wstart-(wstart-wend)tmax⁡2t2.The computational complexity is an important issue in designing our optimization algorithms. In thenth iteration of the ICPSOA, the time to calculate fitness function for immune clone is Nc, the time to calculate fitness function for particle mutation and selection is βNc, and the time to calculate fitness function for particle update is tN. So the total calculating time Pn in the nth iteration should be(3.10)Pn≤[Nc+Ncβ]+tN=(1+β)Nc+tN.Therefore, the computational complexity of the ICPSOA isO(Nc), which indicates that the size of clone group has a direct impact on the search speed of the ICPSOA with the same size of particle.


### 3.3. The ICPSOA-Based Fault-Tolerant Routing Protocol Framework for H-WSNs

The ICPSOA is the kernel of fault-tolerant routing protocol. As shown in Figure2, once nfail (node 18) fails, the macronode nr (node 30) constructs subgraph G′(G′⊂G) according to the current topology information of nodes and extracts the set of nodes Np which can be used to construct an alternative path pi(s,r) from G′. Each node represents a particle, and the population size of particle is n. Some nodes of Np can form a particle sequence {npi1,npi2,npi3…,npim} (m≤n) according to their order, which can construct a path pi(s,r) from source ns to nr. The algorithm ICPSOA would optimize the particle sequence to obtain the optimal path pb(s,r) with optimal fitness fitness(pb), and pb(s,r) includes the following nodes {ns,npb1,npb2,…,npbm,nr}. Each node owns a routing table recording the paths it belongs to and the nodes’ information on these paths. We now demonstrate with an example how the routing recovery process is accomplished in our protocol. In the example (Figure 2), nfail’s child node nfail-c and parent node nfail-p are node 23 and 13.Step 1.
nfail-c reports the failure of nfail to nr, and nfail-p reports the failure to ns (node 2), then ns starts up another backup path to transmit data. ns broadcasts a path request (PR) packet, with routing table including its own available energy and coordinate.Step 2.
If an intermediate nodeni receives PR, it will relay the packet according to its own state of information: if ni is on one of the other existed k-1 paths between ns and nr, it will ignore the packet; else, ni will calculate dist(e), ene(e) and delay(e) between ni and ni-1 according to the information provided by ni-1. Then, it continues to relay packet RP, with routing table including above information, ni and ni-1’s ID, and its ene(n).Step 3.
Each intermediate node in the subtree repeats Step2 until nr receives the PR. Then nr extracts the information, calculates fitness(pi) using the ICPSOA and selects the path pb with optimal fitness. Then, it broadcasts packet RP_ACK, including the IDs of selected nodes {npb1,npb2,npb3,…,npbn} on pb (path 2-8-14-19-24-30 in Figure 2) in routing table.Step 4.
Ifnpbi has received PR_ACK, it checks whether its ID is in the packet’s routing table. Then it establishes a connection between child npbi-1 and parent npbi+1 and delivers PR_ACK to parent until ns receives the packet. Go to Step 5.Step 5.
ns broadcasts packet PR_END, and npbi on pb delivers it to nr. Once nr receives PR_END, the kth path from source node to its root in the subtree is established, the network topology is reconstructed, and protocol ends.
During this process,nr will broadcast one packet and receive three packets, ns will broadcast two packets and receive two packets, a part of relay nodes ni in the subtree will deliver four packets. We assume the number of hops of pi(s,r) (i∈(1,k-1)) is Npi(s,r)i, then the number of the packets received by nr before running the ICPSOA is N=NSTii-∑i=1k-1Npi(s,r)i. In this way the energy consumption of packet receiving and broadcasting of nr can be calculated.


## 3.1. Model of the Proposed H-WSNs

### 3.1.1. The Architecture for the Model of H-WSNs

The architecture for the model of H-WSNs contains two types of wireless sensor devices as shown in Figure1. The lower layer is formed by sensor nodes with constrained resource, including small amount of source nodes and other relay nodes. The main tasks performed by the source nodes are sensing, data processing, and data transmission. The tasks performed by the relay nodes are data processing and relaying. The dominant energy consumer is the radio transceiver. The upper layer consists of resource-rich macronodes overlaid on the H-WSNs. Wireless communication links between macronodes have considerably longer ranges and higher data rates, allowing the macronode network to bridge remote regions of the interest area. The tasks performed by a macronode are data aggregation and transmission, complex computations, and decision making. The ICPSOA is also executed by macronodes.Figure 1
The architecture of H-WSNs.Therefore, in-network data transmission can be performed by forming a spanning tree among all the tree nodes. As shown in Figure1, transmission starts with the leaf nodes (source node) of the tree sending their values to their parent nodes (macronode, nodes 1,2,…,12) in the tree, until the final data is obtained at the root node (sink, node 13). Thus, the overall architecture would have a tree of macronodes and then each macronode can serve as the root of a subtree of ordinary nodes. Here, we are only interested in the fault-tolerant routing between sensor-sensor and sensor-macronode communications.Assume that the network has the following characters: (1) the H-WSNs is a static network, where the nodes will not move after deployment, (2) every node knows its own position and that of the macronodes and the sink. The location can be obtained by GPS or localization protocols for estimating the location of a node, (3) the wireless transmission energy of macronode can be adjusted based on the distance between the receiver and itself, (4) the adjacent nodes would acquire the state information of their 1-hop neighbors and the links between them through periodically broadcast. The meanings of used symbols is provided in Table1.Table 1
The main symbols.
STiTheith subtree of the tree of the H-WSNsNSToThe number of the sensor nodes inSTiPSTsThe state information of all the nodes inSTinsOne of the source nodes inSTinrThe root node (macronode) inSTiP(s,r)The set of all the possible paths betweenns and nr in STipi(s,r)Theith path between ns and nr in STinfailThe failed relay node ofpi(s,r) in STinfail-cThe child node ofnfail of pi(s,r) in STinfail-pThe parent node ofnfail of pi(s,r) in STiniTheith sensor node of pi(s,r) in STipbThe optimal path ofP(s,r) with optimal fitness in STinpbiTheith sensor node of pb in STi


### 3.1.2. Thek-Disjoint-Path Spanning Graph in the Subtree

The subtreeSTi of the network is modeled as a directed, connected graph G(V,E), where V is a finite set of subtree nodes and E is the set of subtree edges representing connection between these nodes, where source node ns∈V and macronode (root) nr∈{V-{ns}}. pi(s,r) is a valid path between ns and nr, and P(s,r) is the set of all the paths pi(s,r).n(n∈pi(s,r)) represents a node in pi(s,r), and e(e∈pi(s,r)) represents direct edge between any two adjacent nodes in pi(s,r). Then, we can get the k-disjoint-path spanning graph in the subtree STi. The factors affecting the choice of path pi(s,r) include (1) the available energy function of each node, ene(n), (2) distance function of the edge between adjacent nodes, dist(e), (3) energy consumption function, ene(e), (4) communication delay function of the node, delay(n). Then, these parameters can determine the fitness function of pi(s,r), fitness(pi)(3.1)fitness(pi)=∑n∈pi(s,r)ene(n)ω1f1+ω2f2+ω3f3,f1=∑e∈pi(s,r)ene(n)∑e∈Eene(n),f2=∑n∈pi(s,r)delay(n)∑n∈Ndelay(n),f3=∑e∈pi(s,r)dist⁡(e)∑e∈Edist⁡(e),
where f1 is the ratio of the energy consumed by the edges of path pi and the energy consumed by all the edges in the subtree, f2 is the delay of the edges and nodes of path pi versus the delay of all the nodes in the subtree, and f3 is the distance of the edges of path pi versus the distance of all the edges in the subtree. ω1,ω2,ω3 are the weight of effective energy, delay and distance constraints in the fitness function, and ω1+ω2+ω3=1. We set ω1=0.4, ω2=0.2, ω3=0.4. The higher fitness value indicates the more suitable path.As illustrated in Figure2, we assume k=3, the three disjoint paths between source node (node 2) and root (node 30) are 2-3-9-15-20-25-28-30, 2-8-13-18-23-30, and 2-7-12-16-21-27-30, respectively. The detailed protocol dealing with routing recovery problem is presented in the following sections.Figure 2
k-disjoint-path spanning graph in subtree.


### 3.1.3. The Proposed Fault Model and Energy Model

We use the simple fault model proposed in [22] and identify the node failure in it. The fault-model should be simple enough to analyze, but also sophisticated enough to capture the fault behavior effectively. The probability of sensor nodes failure of subtree is given by pnode. As we use the more reliable macronodes to sustain the failure during transmission process, the probability of macronode failure is assumed to be pmacro≈0. If any of the sensor nodes fails, our routing recovery approach for node failure in subtree can be implemented.We introduce the energy model adopted in [18], and the equation of energy model of a sensor node is as follows:(3.2)ene(m,d)=enetx(m,d)+enerx(m)=(a11+a2dn)m+a12m,
where d is the distance from the sensor node to the next-hop node, enetx(m,d) and enerx(m) are the energy consumption of sending and receiving m bits of data, a11, a2, and a12 are energy consumption parameters of sending circuit, sending amplifier, and receiving circuit, and n is the channel attenuation index. We also define eneDF as energy consumption of data fusion and eneRT as energy consumption of updating routing table. For the ICPSOA, we define energy consumption of paticle update, immune clone, mutation, particle selection, and restrain per iteration as enePU, eneIC, eneIM, enePS, and enePR, respectively. So, the total consumption of the ICPSOA is according to the actual iterated generations per round.


## 3.1.1. The Architecture for the Model of H-WSNs

The architecture for the model of H-WSNs contains two types of wireless sensor devices as shown in Figure1. The lower layer is formed by sensor nodes with constrained resource, including small amount of source nodes and other relay nodes. The main tasks performed by the source nodes are sensing, data processing, and data transmission. The tasks performed by the relay nodes are data processing and relaying. The dominant energy consumer is the radio transceiver. The upper layer consists of resource-rich macronodes overlaid on the H-WSNs. Wireless communication links between macronodes have considerably longer ranges and higher data rates, allowing the macronode network to bridge remote regions of the interest area. The tasks performed by a macronode are data aggregation and transmission, complex computations, and decision making. The ICPSOA is also executed by macronodes.Figure 1
The architecture of H-WSNs.Therefore, in-network data transmission can be performed by forming a spanning tree among all the tree nodes. As shown in Figure1, transmission starts with the leaf nodes (source node) of the tree sending their values to their parent nodes (macronode, nodes 1,2,…,12) in the tree, until the final data is obtained at the root node (sink, node 13). Thus, the overall architecture would have a tree of macronodes and then each macronode can serve as the root of a subtree of ordinary nodes. Here, we are only interested in the fault-tolerant routing between sensor-sensor and sensor-macronode communications.Assume that the network has the following characters: (1) the H-WSNs is a static network, where the nodes will not move after deployment, (2) every node knows its own position and that of the macronodes and the sink. The location can be obtained by GPS or localization protocols for estimating the location of a node, (3) the wireless transmission energy of macronode can be adjusted based on the distance between the receiver and itself, (4) the adjacent nodes would acquire the state information of their 1-hop neighbors and the links between them through periodically broadcast. The meanings of used symbols is provided in Table1.Table 1
The main symbols.
STiTheith subtree of the tree of the H-WSNsNSToThe number of the sensor nodes inSTiPSTsThe state information of all the nodes inSTinsOne of the source nodes inSTinrThe root node (macronode) inSTiP(s,r)The set of all the possible paths betweenns and nr in STipi(s,r)Theith path between ns and nr in STinfailThe failed relay node ofpi(s,r) in STinfail-cThe child node ofnfail of pi(s,r) in STinfail-pThe parent node ofnfail of pi(s,r) in STiniTheith sensor node of pi(s,r) in STipbThe optimal path ofP(s,r) with optimal fitness in STinpbiTheith sensor node of pb in STi


## 3.1.2. Thek-Disjoint-Path Spanning Graph in the Subtree

The subtreeSTi of the network is modeled as a directed, connected graph G(V,E), where V is a finite set of subtree nodes and E is the set of subtree edges representing connection between these nodes, where source node ns∈V and macronode (root) nr∈{V-{ns}}. pi(s,r) is a valid path between ns and nr, and P(s,r) is the set of all the paths pi(s,r).n(n∈pi(s,r)) represents a node in pi(s,r), and e(e∈pi(s,r)) represents direct edge between any two adjacent nodes in pi(s,r). Then, we can get the k-disjoint-path spanning graph in the subtree STi. The factors affecting the choice of path pi(s,r) include (1) the available energy function of each node, ene(n), (2) distance function of the edge between adjacent nodes, dist(e), (3) energy consumption function, ene(e), (4) communication delay function of the node, delay(n). Then, these parameters can determine the fitness function of pi(s,r), fitness(pi)(3.1)fitness(pi)=∑n∈pi(s,r)ene(n)ω1f1+ω2f2+ω3f3,f1=∑e∈pi(s,r)ene(n)∑e∈Eene(n),f2=∑n∈pi(s,r)delay(n)∑n∈Ndelay(n),f3=∑e∈pi(s,r)dist⁡(e)∑e∈Edist⁡(e),
where f1 is the ratio of the energy consumed by the edges of path pi and the energy consumed by all the edges in the subtree, f2 is the delay of the edges and nodes of path pi versus the delay of all the nodes in the subtree, and f3 is the distance of the edges of path pi versus the distance of all the edges in the subtree. ω1,ω2,ω3 are the weight of effective energy, delay and distance constraints in the fitness function, and ω1+ω2+ω3=1. We set ω1=0.4, ω2=0.2, ω3=0.4. The higher fitness value indicates the more suitable path.As illustrated in Figure2, we assume k=3, the three disjoint paths between source node (node 2) and root (node 30) are 2-3-9-15-20-25-28-30, 2-8-13-18-23-30, and 2-7-12-16-21-27-30, respectively. The detailed protocol dealing with routing recovery problem is presented in the following sections.Figure 2
k-disjoint-path spanning graph in subtree.


## 3.1.3. The Proposed Fault Model and Energy Model

We use the simple fault model proposed in [22] and identify the node failure in it. The fault-model should be simple enough to analyze, but also sophisticated enough to capture the fault behavior effectively. The probability of sensor nodes failure of subtree is given by pnode. As we use the more reliable macronodes to sustain the failure during transmission process, the probability of macronode failure is assumed to be pmacro≈0. If any of the sensor nodes fails, our routing recovery approach for node failure in subtree can be implemented.We introduce the energy model adopted in [18], and the equation of energy model of a sensor node is as follows:(3.2)ene(m,d)=enetx(m,d)+enerx(m)=(a11+a2dn)m+a12m,
where d is the distance from the sensor node to the next-hop node, enetx(m,d) and enerx(m) are the energy consumption of sending and receiving m bits of data, a11, a2, and a12 are energy consumption parameters of sending circuit, sending amplifier, and receiving circuit, and n is the channel attenuation index. We also define eneDF as energy consumption of data fusion and eneRT as energy consumption of updating routing table. For the ICPSOA, we define energy consumption of paticle update, immune clone, mutation, particle selection, and restrain per iteration as enePU, eneIC, eneIM, enePS, and enePR, respectively. So, the total consumption of the ICPSOA is according to the actual iterated generations per round.


## 3.2. Fault-Tolerant Routing Problem Using the ICPSOA

As described in Section2.2, the ICPSOA is used to provide a fast recovery mechanism from path failure due to physical damage or energy depletion with an alternative path. It chooses a path with optimal fitness from the optional sensor nodes. The ICPSOA is the kernel of our fault-tolerant routing protocol. Its flowchart is shown in Figure 3, and its framework is shown in Algorithm 1. The detailed procedures are described in the following subsections.Algorithm 1:The ICPSOA for fault-routing problem.
Input: PSTo: The information parameters of nodesPGen: The iterated generations for searching processOutput: fitness(pi): The global optimal fitnessProcess:Step 1: Initialization: Generate initial particle swarm parameter.Step 2: Immunization: Immune clone, mutation, particle selection and restrain.Step 3: If termination criterion conditions are satisfied, go to  Step 5; elsego toStep 4.Step 4: Update: Update the velocity and position of each sub-swarm and particle.Step 5: Output: Output the global optimal fitness of the particle swarm. Ends.Figure 3
The architecture of the ICPSOA for the H-WSNs.(1) Initialization
The principle of the ICPSOA is to search, respectively, in differentD-dimensional target spaces using k independent particle swarms. To initialize the algorithm, we set the population size of particle n, the division factor k, and each particle swarm includes n/k particles. Then, the D-dimensional vector (vector of particle’s position and velocity) is divided into k swarms. We define a matrix by [D×2n] to represent the initial particle swarm, in which the former n columns are the position of particle, and the latter n columns are the velocity of particle.In Algorithm2, b(g) is a complete vector function consisting of all subswarms’ optimal position vector, xmSi represents position vector of the mth particle in the ith swarm, pmSi is the optimal history position vector of the mth particle in the ith swarm, and pgSi represents optimal experience position vector of the ith swarm.Algorithm 2:Initialization mechanism in the ICPSOA.
Input: PSTo: The information parameters of nodesn: The population size of particlek: The population size of swarmOutput: Si: The vector of the ith particle swarmb(g): Each sub-swarm’s optimal position vector functionProcess:Particle’sD-dimensional vector is divided into k particle swarms.b(L,i)=(pgS1,…,pgSi-1,L,pgSi+1,…,pgSk)(2) Immunization
In this step, each particle can be considered as an antibody, resulting in the clonal mutation setC. The clone number and the fitness of particle are proportional. The clonal number Nc is usually calculated as follows:
(3.3)Nc=αN,
where α is the clone factor and is proportional to particle’s fitness value. N is the number of particles. Mutation rule can be setup according to experience. The particle mutation rule for the function optimization problem is
(3.4)ci=xi+βrand,
where ci is the clonal individual, xi is the original antibody, β represents the mutation factor, and rand is uniformly distributed in [0,1].For the particles replacement rule, we need to calculate the antigen stimulus degree of the original particles and select clonal mutation particles. The Euclidean distance between any particleCt and antigen Yt is (3.5)d(i,j)=∑i=1n(cit-yjt)2.Therefore, the stimulus degree of antibody particle is(3.6)A(i,j)=1d(i,j).After that, each particle is compared with stimulus threshold; the higher one will maintain in the subswarm, and the lower one will be replaced (called restrain). The process of this step is as shown in Algorithm3. Then, go to Step 2 in Algorithm 1.Algorithm 3:Immune mechanism in the ICPSOA.
Input: n: The population size of particlesPGen: The iterated generations for searching processk: The population size of swarmOutput:The allele of the offspring’s antibodies (particles)Process:For each swarm i∈[1⋯k]For each particle m∈[1⋯n/k]Clone operation: Nc=αNMutation operation: ci=xi+βrandReplacement (restrain) operation:d(i,j)=∑i=1n(cit-yjt)2, A(i,j)=1/d(i,j)If A(i,j)> threshold, the particle (antibody) is replacedEnd ForEnd For(3) Termination Criterion
If the solution is satisfied with the termination criterion,fitness(pi) is the optimal fitness or PGen decreases to zero, the optimal path pi will be the desired optimal solution, and this procedure ends; otherwise, returns to Step 4 in Algorithm 1. Then, the kth path is established.(4) Update
In this step, the velocity and position of the particle is updated as (2.1). The process is as shown is Algorithm 4. The updating equation of particles’ optimal position vector in each subswarm is as follows:
(3.7)b(pmSi,i)={b(xmSi,i),fitness(b(xmSi,i))≥fitness(b(pmSi,i)),b(pmSi,i),fitness(b(xmSi,i))<fitness(b(pmSi,i)),
where 1≤i≤k. The updating equation of optimal position of each subswarm is(3.8)b(pgSi,i)=argP(pmSi,i)max fitness(b(pmSi,i)),1≤m≤nk,1≤i≤k.Algorithm 4:Update mechanism in the ICPSOA.
Input: PSTo: The information parameters of nodesSi: The ith particle swarmb(L,i): Each sub-swarm’s optimal position vector functionPGen: The iterated generations for searching processOutput:vidt+1and xidt+1: The velocity and position of each sub-swarm and its particlefitness(pi): The global optimal fitnessProcess:Foreach swarm i∈[1⋯k]For each particle m∈[1⋯n/k]Update velocity and position of each sub swarm’s particleIffitness(b(xmSi,i))≥fitness(b(pmSi,i)),  b(pmSi,i)=b(xmSi,i)Else Iffitness(b(xmSi,i))<fitness(b(pmSi,i)),b(pmSi,i)=b(pmSi,i)Calculate fitness(pi) of the particle (path)End Forb(pgSi,i)=argP(pmSi,i)maxfitness(b(pmSi,i))End ForEquation (3.8) indicates that the optimal position of the mth subswarm will select the personal optimal position with the optimal fitness of particle in the swarm.Inertia weightw plays an important role to the convergence of the result among the adjustable parameters. The larger weight can help the particle escape from the local best solution, and the smaller one is better for the convergence, thus the inertia weight can achieve balance between global search and local search. To overcome the limitations of other general strategies, the linear differential decreasing strategy is used [23]. Here, we select wstart=0.85, wend=0.35(3.9)dw(t)dt=2(wstart-wend)tmax⁡2t,w(t)=wstart-(wstart-wend)tmax⁡2t2.The computational complexity is an important issue in designing our optimization algorithms. In thenth iteration of the ICPSOA, the time to calculate fitness function for immune clone is Nc, the time to calculate fitness function for particle mutation and selection is βNc, and the time to calculate fitness function for particle update is tN. So the total calculating time Pn in the nth iteration should be(3.10)Pn≤[Nc+Ncβ]+tN=(1+β)Nc+tN.Therefore, the computational complexity of the ICPSOA isO(Nc), which indicates that the size of clone group has a direct impact on the search speed of the ICPSOA with the same size of particle.


## 3.3. The ICPSOA-Based Fault-Tolerant Routing Protocol Framework for H-WSNs

The ICPSOA is the kernel of fault-tolerant routing protocol. As shown in Figure2, once nfail (node 18) fails, the macronode nr (node 30) constructs subgraph G′(G′⊂G) according to the current topology information of nodes and extracts the set of nodes Np which can be used to construct an alternative path pi(s,r) from G′. Each node represents a particle, and the population size of particle is n. Some nodes of Np can form a particle sequence {npi1,npi2,npi3…,npim} (m≤n) according to their order, which can construct a path pi(s,r) from source ns to nr. The algorithm ICPSOA would optimize the particle sequence to obtain the optimal path pb(s,r) with optimal fitness fitness(pb), and pb(s,r) includes the following nodes {ns,npb1,npb2,…,npbm,nr}. Each node owns a routing table recording the paths it belongs to and the nodes’ information on these paths. We now demonstrate with an example how the routing recovery process is accomplished in our protocol. In the example (Figure 2), nfail’s child node nfail-c and parent node nfail-p are node 23 and 13.Step 1.
nfail-c reports the failure of nfail to nr, and nfail-p reports the failure to ns (node 2), then ns starts up another backup path to transmit data. ns broadcasts a path request (PR) packet, with routing table including its own available energy and coordinate.Step 2.
If an intermediate nodeni receives PR, it will relay the packet according to its own state of information: if ni is on one of the other existed k-1 paths between ns and nr, it will ignore the packet; else, ni will calculate dist(e), ene(e) and delay(e) between ni and ni-1 according to the information provided by ni-1. Then, it continues to relay packet RP, with routing table including above information, ni and ni-1’s ID, and its ene(n).Step 3.
Each intermediate node in the subtree repeats Step2 until nr receives the PR. Then nr extracts the information, calculates fitness(pi) using the ICPSOA and selects the path pb with optimal fitness. Then, it broadcasts packet RP_ACK, including the IDs of selected nodes {npb1,npb2,npb3,…,npbn} on pb (path 2-8-14-19-24-30 in Figure 2) in routing table.Step 4.
Ifnpbi has received PR_ACK, it checks whether its ID is in the packet’s routing table. Then it establishes a connection between child npbi-1 and parent npbi+1 and delivers PR_ACK to parent until ns receives the packet. Go to Step 5.Step 5.
ns broadcasts packet PR_END, and npbi on pb delivers it to nr. Once nr receives PR_END, the kth path from source node to its root in the subtree is established, the network topology is reconstructed, and protocol ends.
During this process,nr will broadcast one packet and receive three packets, ns will broadcast two packets and receive two packets, a part of relay nodes ni in the subtree will deliver four packets. We assume the number of hops of pi(s,r) (i∈(1,k-1)) is Npi(s,r)i, then the number of the packets received by nr before running the ICPSOA is N=NSTii-∑i=1k-1Npi(s,r)i. In this way the energy consumption of packet receiving and broadcasting of nr can be calculated.


## 4. Simulation Results

### 4.1. Simulation Model

To evaluate the performance of the ICPSOA, we design a corresponding simulation scenario upon Matlab. The simulation experiment is constructed on Windows XP with Intel Pentium 4 processor (2.4 GHz) and 2 GB RAM. The goal of the simulation is to show that the ICPSOA can provide a more stable transport environment in an error-prone network. The results are also compared to the protocols of ICE, CPEQ, and EARQ.In Table2, we present the parameters configured for the conducted simulation experiments. The sensor nodes are randomly deployed on area A, and the macronodes are located at known coordinates. 500 rounds are taken and five packets are delivered in each round. The size of the network is the same for different algorithms and the fitness function is then measured. The parameters used for the ICPSOA are function dimension D=30, iterated generations PGen=1000, division factor k=5, clone factor α=4, mutation factor β=0.5. According to the description of the ICPSOA in Section 3.1.3, we set energy consumption enePU=80 pJ, eneIC=5 pJ, eneIM=10 pJ, enePS=15 pJ, enePR=10 pJ per iteration. The metrics that we use in our experiments are average number of alive nodes per round, average energy depletion ratio per round (measured as the energy dissipation versus the initial energy), average delay of packet delivery, and packet delivery ratio (measured as the number of successfully delivered packet versus required packet).Table 2
Simulation parameters.
Simulation parameterValueNetwork areaA10000 m × 10000 mNumber of sensor nodennode50–500Number of macronodenmacro10Available energy on sensorsEnode120 JSensing radius of sensor nodeRnode-s300 mCommunication radius of sensor nodeRnode-c600 mCommunication radius of macronodeRmacro-c3500 mBandwidth of sensor nodeBnode250 kb/sNumber of disjoint multipathk3Number of simulation rounds500Number of packet in each round1Size of packet in each roundm400 bitsProbability of node failurepnode0.02Energy consumption of sending circuita1140 nJ/bitEnergy consumption of receiving circuita1280 nJ/bitEnergy consumption of sending amplifiera2200 pJ/bit/m2Channel attenuation indexn2Energy consumption of data fusioneneDF4 nJ/bitEnergy consumption of updating routing tableeneRT2 nJ/bit


### 4.2. Evaluation of the Simulation Results

To illustrate the effect of the proposed protocol, we take a snapshot during a simulation. Figure4 shows a small area (2000 m × 2000 m), which illustrates a subtree with the existed three paths between source node (node 29) and macronode (node 18). We can see when an intermediate node (node 24) fails, source node immediately establishes an alternative path to connect the macronode in order to replace the previous 3rd path.Figure 4
Snapshot of establishing the alternative path using ICPSOA.The simulation ends after 1000 rounds. We compare the number of alive nodes per round for these four protocols. As shown in Figure5 for different network sizes, the number of nodes died in the ICPSOA, ICE, and CPEQ is less than EARQ over the same number of rounds. This is because comparing with heterogonous WSNs, all the nodes only need to transmit data to its root (macronode) of the subtree in the H-WSNs, which indirectly shortens the transmission distance between sensor nodes to the sink, and prolongs their lifetime. The fast routing recovery mechanism of the ICPSOA also makes its number of alive nodes 5%~10% more than that of ICE, and CPEQ in the same rounds. Then, we would only compare the ICPSOA, ICE, and CPEQ with the same network style (H-WSNs) in the remaining simulation process.Experimental results for number of alive nodes per round with variant scale of network. (a) Size of 50 nodes. (b) Size of 250 nodes.
(a)(b)As shown in Figure6 for different network sizes, energy depletion ratio of the ICPSOA based protocol is 5%~15% smaller than that of ICE and CPEQ. And the dispersion between them is more obvious as the size of the cluster increases. That is because firstly, each source node has k paths to the macronode, and the total energy consumed is minimized; secondly, the ICPSOA can select the nodes with better QoS parameters (such as more available energy and less distance of path) to establish alternative path and construct a more reliable transmission environment to reduce the retransmission caused by unstable paths, therefore, prolong the network lifetime as compared to ICE and CPEQ.Experimental results for energy depletion ratio per round with variant scale of networks. (a) Size of 50 nodes. (b) Size of 250 nodes.
(a)(b)Figure7 shows the average delay of packet delivery (average delay of each packet delivered from source node to the sink). We can observe that the ICPSOA outperforms ICE and CPEQ in terms of average delay for the same networks. The ICPSOA has demonstrated a lower delay when network size grows. A low delay of packets can be explained by the multipath property and shortest alternative path selection of the proposed ICPSOA-based protocol for fault tolerance.Figure 7
Experimental results for average delay of packet delivery.Figure8(a) shows that the H-WSNs with the ICPSOA can deliver more packets to the sink than the network with EARQ and ICE with the value of 0.02 of pnode. In most cases, the ICPSOA can send 5%~15% more packets to the sink. A bigger value of packet delivery ratio indicates a lower packet dropout probability [24, 25] and a better network capability of delivering useful information. This result can be explained by the fact that the ICPSOA provides a fast recovery from path failure with an optimal alternative path, which improves the success rate of data transmission. Note that the packets in the ICPSOA experience a higher delivery ratio as the size of the network grows, which indicates the ICPSOA-based protocol of the H-WSNs is more feasible for practical deployment of large-scale WSNs than ICE and CPEQ.Experimental results for average successful packet delivery ratio with variant failure probability. (a)pnode=0.02. (b) pnode=0.04. (c) pnode=0.08.
(a)(b)(c)We should also compare the performance trend of the three algorithms with different probability of node failurepnode. We plot the packet delivery ratio against the number of nodes in Figure 8 for various pnode (value of 0.02, 0.05, and 0.08). As shown in Figure 8(a), 8(b), and 8(c), the observed packet delivery ratio of the proposed schemes degrades as pnode ascends, which means the performance of proposed scheme is reduced as the percentage of failed nodes increases. But the ICPSOA can still deliver more packets than ICE and CPEQ for different size of the sensor network.


## 4.1. Simulation Model

To evaluate the performance of the ICPSOA, we design a corresponding simulation scenario upon Matlab. The simulation experiment is constructed on Windows XP with Intel Pentium 4 processor (2.4 GHz) and 2 GB RAM. The goal of the simulation is to show that the ICPSOA can provide a more stable transport environment in an error-prone network. The results are also compared to the protocols of ICE, CPEQ, and EARQ.In Table2, we present the parameters configured for the conducted simulation experiments. The sensor nodes are randomly deployed on area A, and the macronodes are located at known coordinates. 500 rounds are taken and five packets are delivered in each round. The size of the network is the same for different algorithms and the fitness function is then measured. The parameters used for the ICPSOA are function dimension D=30, iterated generations PGen=1000, division factor k=5, clone factor α=4, mutation factor β=0.5. According to the description of the ICPSOA in Section 3.1.3, we set energy consumption enePU=80 pJ, eneIC=5 pJ, eneIM=10 pJ, enePS=15 pJ, enePR=10 pJ per iteration. The metrics that we use in our experiments are average number of alive nodes per round, average energy depletion ratio per round (measured as the energy dissipation versus the initial energy), average delay of packet delivery, and packet delivery ratio (measured as the number of successfully delivered packet versus required packet).Table 2
Simulation parameters.
Simulation parameterValueNetwork areaA10000 m × 10000 mNumber of sensor nodennode50–500Number of macronodenmacro10Available energy on sensorsEnode120 JSensing radius of sensor nodeRnode-s300 mCommunication radius of sensor nodeRnode-c600 mCommunication radius of macronodeRmacro-c3500 mBandwidth of sensor nodeBnode250 kb/sNumber of disjoint multipathk3Number of simulation rounds500Number of packet in each round1Size of packet in each roundm400 bitsProbability of node failurepnode0.02Energy consumption of sending circuita1140 nJ/bitEnergy consumption of receiving circuita1280 nJ/bitEnergy consumption of sending amplifiera2200 pJ/bit/m2Channel attenuation indexn2Energy consumption of data fusioneneDF4 nJ/bitEnergy consumption of updating routing tableeneRT2 nJ/bit


## 4.2. Evaluation of the Simulation Results

To illustrate the effect of the proposed protocol, we take a snapshot during a simulation. Figure4 shows a small area (2000 m × 2000 m), which illustrates a subtree with the existed three paths between source node (node 29) and macronode (node 18). We can see when an intermediate node (node 24) fails, source node immediately establishes an alternative path to connect the macronode in order to replace the previous 3rd path.Figure 4
Snapshot of establishing the alternative path using ICPSOA.The simulation ends after 1000 rounds. We compare the number of alive nodes per round for these four protocols. As shown in Figure5 for different network sizes, the number of nodes died in the ICPSOA, ICE, and CPEQ is less than EARQ over the same number of rounds. This is because comparing with heterogonous WSNs, all the nodes only need to transmit data to its root (macronode) of the subtree in the H-WSNs, which indirectly shortens the transmission distance between sensor nodes to the sink, and prolongs their lifetime. The fast routing recovery mechanism of the ICPSOA also makes its number of alive nodes 5%~10% more than that of ICE, and CPEQ in the same rounds. Then, we would only compare the ICPSOA, ICE, and CPEQ with the same network style (H-WSNs) in the remaining simulation process.Experimental results for number of alive nodes per round with variant scale of network. (a) Size of 50 nodes. (b) Size of 250 nodes.
(a)(b)As shown in Figure6 for different network sizes, energy depletion ratio of the ICPSOA based protocol is 5%~15% smaller than that of ICE and CPEQ. And the dispersion between them is more obvious as the size of the cluster increases. That is because firstly, each source node has k paths to the macronode, and the total energy consumed is minimized; secondly, the ICPSOA can select the nodes with better QoS parameters (such as more available energy and less distance of path) to establish alternative path and construct a more reliable transmission environment to reduce the retransmission caused by unstable paths, therefore, prolong the network lifetime as compared to ICE and CPEQ.Experimental results for energy depletion ratio per round with variant scale of networks. (a) Size of 50 nodes. (b) Size of 250 nodes.
(a)(b)Figure7 shows the average delay of packet delivery (average delay of each packet delivered from source node to the sink). We can observe that the ICPSOA outperforms ICE and CPEQ in terms of average delay for the same networks. The ICPSOA has demonstrated a lower delay when network size grows. A low delay of packets can be explained by the multipath property and shortest alternative path selection of the proposed ICPSOA-based protocol for fault tolerance.Figure 7
Experimental results for average delay of packet delivery.Figure8(a) shows that the H-WSNs with the ICPSOA can deliver more packets to the sink than the network with EARQ and ICE with the value of 0.02 of pnode. In most cases, the ICPSOA can send 5%~15% more packets to the sink. A bigger value of packet delivery ratio indicates a lower packet dropout probability [24, 25] and a better network capability of delivering useful information. This result can be explained by the fact that the ICPSOA provides a fast recovery from path failure with an optimal alternative path, which improves the success rate of data transmission. Note that the packets in the ICPSOA experience a higher delivery ratio as the size of the network grows, which indicates the ICPSOA-based protocol of the H-WSNs is more feasible for practical deployment of large-scale WSNs than ICE and CPEQ.Experimental results for average successful packet delivery ratio with variant failure probability. (a)pnode=0.02. (b) pnode=0.04. (c) pnode=0.08.
(a)(b)(c)We should also compare the performance trend of the three algorithms with different probability of node failurepnode. We plot the packet delivery ratio against the number of nodes in Figure 8 for various pnode (value of 0.02, 0.05, and 0.08). As shown in Figure 8(a), 8(b), and 8(c), the observed packet delivery ratio of the proposed schemes degrades as pnode ascends, which means the performance of proposed scheme is reduced as the percentage of failed nodes increases. But the ICPSOA can still deliver more packets than ICE and CPEQ for different size of the sensor network.


## 5. Conclusions

We propose the ICPSOA-based fault-tolerant routing protocol for H-WSNs, which focuses on a solution to the problem of energy depletion and packet delivery of nodes, by trying to reconstruct the topology structure and recover the routing for the path failure and achieve energy conservation by avoiding unnecessary retransmission. The conserved energy can be used to increase the quantity of information received by the sink. The experiment presents the promising ability of the ICPSOA, and better solutions of fault tolerance and prolonging the network lifetime can be obtained by the ICPSOA-based protocol than the protocols of EARQ, ICE and CPEQ. The results have illustrated the advantage of H-WSNs and backup disjoint multipath, which can reduce the risk of data delivery loss and energy consumption on the path exploring. It also aims at shortening delay of packet delivery, evening energy dissipation among the nodes by constructing the optimal alternative paths in the H-WSNs with the swarm intelligence algorithm. The strength of the ICPSOA is its simplicity, robustness and effectiveness for fast routing recovery compared to other approaches and makes the ICPSOA a potential solution to meet the requirements of critical conditions monitoring applications.As for future studies, the following directions are under the way: firstly, the proposed protocol ignores the fault-tolerant routing between macronode-macronode communications, which could be considered to form a more complete protocol architecture; secondly, we should further reduce the computational complexity of the proposed ICPSOA such that it converges faster to a better solution, providing robustness against failure in the network.



---

*Source: 743728-2011-12-25.xml*