Virtual movement of relay nodes for two-tier wireless sensor networks in tunnels

Relay model of network

In the case of a long tunnel, the shape of a coal lane mapped to a flat is a thin rectangle. Therefore, the link of RNs on one route is linear. The topology of the link is a one-dimensional chain labeled by i = 1,…, M, as depicted in Figure 1. The only sink is located at the end of the line. We assume that all sensors are homogeneous and have an ID number.

OPEN IN VIEWER

Figure 1.

Linear model of WSNs in tunnels.

Assume that we place N nodes on the monitoring path with a constant hop distance and that the number of RNs is M; that is to say, the number of clusters is M. The ith cluster has N_i nodes ( ∑ i = 1 N i = N ) . The entire length of the tunnel is λ, and the distance between the RNs of the ith cluster and the (i − 1)th cluster is d_i. We assume a data collection application in which the sensors organized as clusters are required to send their sensing data to a CH at a certain rate. The CH nodes would transfer data to the sink node by a multi-hop route. When we look at a single part of the route, an RN is the CH of one cluster. SNs in the cluster send messages to an RN in one hop.

To facilitate the placement of nodes, we imagine that the tunnel is mapped into a thin two-dimensional (2D) rectangle. The actual distance between a pair of nodes will be slightly shorter than that in a real tunnel. The distance is assumed to be approximately the same as that in an actual environment. Table 2 lists the notations used in this article.

OPEN IN VIEWER

Table 2.

Notations and variables.

Symbol	Definition
λ	The whole length of tunnel.
m	A variable of cluster number, M is the total number of cluster.
rm,n	Relay nodes n in cluster m. Rm is the relay nodes set of cluster m.
ni	The number of nodes in cluster i.
Ci	Cluster i.
di	Distance between the relay nodes of ith cluster and (i − 1)th cluster. d0 is an optimal relay distance.
Es,0	Initial energy of sensor node s.
si	A node s in the ith cluster.
Ek,s	Energy of a node s in the kth cluster.
Etx(i,k)	The power dissipated at node i while transmitting a one-bit message to node k. Ei−1, tx (i) is that (i − 1) transmitting all messages to node i. Ei,tx(Rk) is the power dissipated at node i while transmitting messages to an RN set Rk.
Erx(i)	The power dissipated at node i while receiving a one-bit message. Ei−1, rx (i) is that (i − 1) receives all messages from cluster of node i. Ei,rx(Rk) is the power dissipated at node i while receiving messages from an RN set Rk.
εrx,εele	Distance-independent constant terms, εele = 50 nj/bit.
εamp	A coefficient associated with the distance-dependent term, εamp = 0.0013 pj/bit/m4.
α	Path loss index, 2 ≤ α ≤ 4.
d 0	The optimal relaying distance by Wu et al., 11 shown as formula (3).
P s , r m	The number of bits that rm relays from node s. Ps is the whole number of bits that rm relays.

RN: relay node.

Power dissipation

Because of their rough surface and complex geometry, underground tunnels are often hostile radio frequency (RF) environments. To maintain reliable communication, we must consider the energy of each node. We refer to the radio model used in the works by Wang et al. ²⁰ and Heinzelman et al. ²¹ in this article. Considering the hardware circuit, the modules that consume energy include processor module, sensor module, and wireless communication module. With rapid development of integrated circuit technology, low energy consumption and high performance of processors and sensors are more widely available. ²² Therefore, in this article, we ignore these two parts, processor module and sensor module, of energy consumption calculation in the nodes and focus on the energy consumption of wireless communication modules. For the sake of simplicity, the general assumptions of the model are as follows:

E tx ( s , i ) = ε ele + ε amp d i α

(1)

and the receiving formula is given by formula (2)

E rx ( s , k ) = ε rx

(2)

where ε_rx and ε_ele are distance-independent constant terms; ε_amp is a coefficient associated with the distance-dependent term, which accounts for the energy dissipated in the transmitter amplifier; α is the path loss index, whose value is 2 ≤ α ≤ 4. ²⁴ Typical values of these parameters are ε_ele = 50 nj/bit and ε_amp = 0.0013 pj/bit/m⁴.

d 0 = ε ele ( ε amp ( α − 1 ) ) α

(3)

where if d_k ≤ d₀, α = 2; otherwise, α = 4. The energy for receiving a bit is E_rx(i), whose value is typically 50 nj/bit. Assume that the relay distance is the optimal value d₀ for saving energy.

E i , tx ( i + 1 ) = ( ε ele + ε amp d i α ) ∑ k = i + 1 M N k

(4)

Therefore, the first RN nearest to the BS should be equipped with many batteries if the tunnel is very long.

Problem and VM

For a WSN, when one node dies, the whole network may die because a sensing hole is created. To increase the performance and lifetime of a network, it is expected that all nodes are exhausted at the same time. However, because of different distances among SNs and RNs, this expectation is difficult to achieve. For example, if there are just two nodes in a place, and one is relaying data from the other, it is easy to compute the batteries they require. However, each cluster contains many nodes. Thus, it is difficult to know the exact number for each cluster because of complex geometry. Moreover, there are some differences in tunnel models relative to models in open space. Owing to the length of tunnels, SNs in the area (Figure 2, labeled A) that are far away from RNs still die faster than those closer to the RNs, as is shown in Figure 2. This is easy to understand in terms of the formula in which the transmitting energy consumption varies directly with distance to the αth power. Figure 3 shows that the energy consumption of nodes after several cycles is significantly different if α = 2. Figure 3 suggests that more than one-third of the power in the SNs close to the RNs may remain alive when the power of the SNs far from the RNs is depleted. Thus, there is a significant imbalance of energy consumption in SNs for WSNs in tunnels. This is the reason why fixed RNs shorten the lifespan of WSNs.

OPEN IN VIEWER

Figure 2.

Area where nodes consume energy faster.

OPEN IN VIEWER

Figure 3.

Theoretical differences of energy consumption. (Each vertical line paralleled to the Y-axis indicates the energy consumption of the node at the intersection point of the line cutting the X-axis.)

To save energy in the SNs and design an energy-load balanced model, mobile sinks in previous research works, such as Jawhar, ¹⁸ Luo et al., ²⁶ provide a wise way to solve this problem. Each of the SNs never sends its messages to the sink over a long distance when the sink moves from one side to the other. In terms of this, we hope to move the RNs in each cluster. However, it is difficult to design and arrange mobile nodes in tunnels.

There is an alternative way to move RNs if we consider the node movement from the perspective of node position shifting. We select some nodes as RNs for every cluster, but only one of them in each cluster is working at a time. These RNs change in sequence; that is to say, an RN changes in a cluster from one frontier to the other along the tunnel. At the same time, all clusters’ RNs change according to the first one. This provides the appearance that the RNs are moving. We call it “virtual movement of RNs” (VMRN), and the solution is called VMRNS.

It may seem as if this solution merely changes the CHs in clusters, similar to the low-energy adaptive clustering hierarchy (LEACH) protocol. ²⁷ But the difference from LEACH is each RNs in a cluster works in a sequence and attached with extra battery according to formula (4). Figure 4 shows the process of selected RNs as the sequence. First, the sequence {r_1,1, r_2,1,…, r_M,1} works until one of their batteries is depleted. Then, a new sequence {r_1,j, r_2,j,…, r_M,j} is selected instead of them where r_i,j ∈ C_i. It seems the sequence {r_1,1, r_2,1,…, r_M,1} moves to a new position. It is called VM. With the VM, two new problems come out. One is where these RNs should be placed when we select n nodes as RNs. The other is how many nodes we should select as RNs in one cluster.

OPEN IN VIEWER

Figure 4.

Virtual movement model of relay nodes.

Lemma 1

If all RNs r_k,i move from point x_k,i to x_k+1,i with constant speed v at the same time and the energy dissipation of node s as it transmits messages during the RNs moving process is E s a , tx ( R k ) , for any nodes s a , s b ∈ C k , E s a , tx ( R k ) = E s b , tx ( R k ) .

Proof

According to assumptions, the distance between two RNs in adjoining clusters is the optimal relaying distance d₀; that is, the range of a cluster is d₀. We prove the case N = 1 first. An RN r_k,0 moves from x_k,0 to x_k+1,0, as shown in Figure 5. When a node in cluster k changes its owner during the process of RN movement, the variation range of the node’s transmit distance is [0, d₀/2], we can find point x_a,1 and x_a,2 such that d₀/2 = |x_a,2 − x_sa| = |x_sa − x_a,1|. That is to say, when r_k,0 moves at the right of x_a,2, s_a may change r_k−1,0 as its RN. When r_k,0 is in [x_k,0, x_a,2], the energy dissipation of node s_a is denoted by E s a , tx ( r k , 0 )

E s a , tx ( r k , 0 ) = ∫ x k , 0 x a , 2 ( ε ele + ε amp x α ) dx

(5)

OPEN IN VIEWER

Figure 5.

Distance changes when RN moves.

Then, s_a changes its RN. When r_k−1,0 is in [x_a,1, x_k,0], the energy dissipation of node s_a is E s a , tx ( r k − 1 , 0 )

E s a , tx ( r k − 1 , 0 ) = ∫ x a , 1 x k , 0 ( ε ele + ε amp x α ) dx

(6)

Then, we can determine the energy dissipation of node s_a in cluster m when RNs are moving, as shown in formula (7)

E s a , tx ( R k ) = E s a , tx ( r k , 0 ) + E s a , tx ( r k − 1 , 0 ) = ∫ x a , 1 x k , 0 ( ε ele + ε amp x α ) dx + ∫ x k , 0 x a , 2 ( ε ele + ε amp x α ) dx = ∫ x a , 1 x a , 2 ( ε ele + ε amp x α ) dx = ∫ 0 d 0 / 2 E s a , tx ( R k ) dx

(7)

We can get the same result to s_b, and then E s a , tx ( R k ) = E s b , tx ( R k ) . We can get the same result when 2 ≤ n^r_k.

Lemma 1 suggests that the energy consumption of all SNs in a cluster is balanced when RN of the cluster moves to the position of its adjacent RN’s. The lifetime of the SNs is prolonged.

However, in Lemma 1, the environment is ideal because some conditions are difficult to meet. For instance, “all RNs move with constant speed at the same time” is an unsuitable condition because it is hard to set synchronized clocks. So, we attempt to find a suboptimal result to balance energy dissipation among SNs.

First, the signals that s_a sends are discrete; we assume that s_a sends Ω bits to RNs. According to Figures 5 and 6, each SN passes through two phases as an RN moves from x_k,0 to x_k+1,0. One of the two phases is a segment in which the node belongs to cluster k, and the other is to join cluster k − 1. Thus, the energy consumption comprises two parts. Assume that s_a sends p₁ bits to r_k,0 and p₂ to r_k−1,0. Then, we have formula (8)

E s a , tx = E s a , tx ( r k , 0 ) + E s a , tx ( r k − 1 , 0 ) = ∑ s a ∈ C k p 1 ( ε ele + ε amp ( | x s a − x k , 0 | ) α ) + ∑ s a ∈ C k − 1 p 2 ( ε ele + ε amp ( | x s a − x k − 1 , 0 | ) α )

(8)

where k ∈ {1, M} and p₁ + p₂ = Ω.

OPEN IN VIEWER

Figure 6.

Different distances of the substituted RN.

Second, we consider the VMRN. In this situation, it is difficult for the movement of RNs to be continuous because they are fixed and not deployed without gaps. We consider a case in which an extra RN sequence RQ = {r_k,1, r_k,2,…, r_k,q} is inserted between r_k,0 and r_k+1,0. These RNs in RQ will work in turns, which seems r_k,0 changes its position. Therefore, the energy dissipation of s_a changes when an RN r_k,j substitutes for r_k,j−1, j ∈ {1,…, q}. Assume that r_k,j will relay P s a , R k , j bits for s_a. Formula (8) should change as formula (9)

E s a , tx ( RQ ) = ∑ j = 0 q P s a , r k , j ( ε ele + ε amp ( | x s a − x k , j | ) α ) , s a ∈ C k

(9)

where k ∈ {1, M}, j ∈ {0, q}, Ω = ∑ j = 0 q P s a , R k , j . Formula (9) would be consistent with E s a , tx in Lemma 1 if q→∞ and P s a , r k , i = P s a , r k , j ( i , j ∈ { 0 , q } ) . P s a , r k , j denotes the number of bits that r_k,j relays from node s_a.

Nevertheless, it is not sufficient for maximizing the lifetime of WSN if E s a , tx ( RQ ) is minimum. We must solve the problem of energy balance in a cluster. For simplicity, we consider a case in which one extra RN (r_k,1) is inserted between two RNs, that is, each interval would be inserted one RN. The position of r_k,0, x_k,0, is variable, which affects the energy consumption of the nodes in its working range. There is a problem to identify the proper position to place r_k,0 such that the node whose energy consumption is maximum would consume the least amount of energy in cluster k. This optimization problem is described by the following

Min { Max ( | E s b , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) − E s a , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) | ) }

s . t . E s a , tx ( r k , j ) > 0 , E s b , tx ( r k , j ) > 0 , s a , s b ∈ C k , k ∈ { 1 , M }

| x s − x i , j | ≤ d 0 2 , s ∈ { s a , s b } ; x s , x i , j ∈ C i ; j ∈ { 0 , 1 } P s a = P s b , s a , s b ∈ C k x k , 0 < x k , 1 < x k + 1 , 0 , k ∈ ( 1 , M − 1 )

(10)

where P s a = P s a , r k − 1 , 1 + P s a , r k , 0 + P s a , r k , 1 , r_k−1,1 is an RN instead of r_k−1,0, P s a , r k , 0 is the number of bits that r_k,0 relays from node s_a. For simplicity, we assume that all nodes transmit messages for the same amount of time. It is intuitive that the best positions for r_k,1 would be the middle of the intervals between r_k,0 and r_k+1,0. We will prove it.

Proposition 1

Assume that there are M clusters on a straight line. Suppose that RN in cluster k is R_k,0 (k ∈ {1, M}). All RNs {R_k} perform a VM. The location of a node s is x_s, and the location of r_k,0 is x_k,0. d₀ = |x_k,0 − x_k−1,0|. For each interval of sequence {r_k,0}, one node r_k,1 situated on x_k,1 would be selected as an RN such that |x_k,1 − x_k,0| = |x_k+1,0 − x_k,1|. Then, the additional sequence {r_k,0, r_k,1} is one optimal solution of 1-inserted case to problem (10) if P s , r k , 0 = P s , r k , 1 .

Proof (reference to Figure 6)

When collecting data ranges from x_k−1,1 to x_k,1, node r_k,0 is working as a relaying node of cluster k. Assume that x_k,1 is the middle of x_k,0 and x_k+1,0; that is, |x_k,1 − x_k,0| = |x_k+1,0 − x_k,1| = |x_k+1,0 − x_k,0|/2. When the working time of r_k,0 is running out, r_k,1 will relay data instead of r_k,0. E_s,tx({r_k−1,1, r_k,0, r_k,1}) is a piecewise function of x_s as follows

E s , t x ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) = { P s , R k , 0 ( ε e l e + ε a m p ( | x s − x k , 0 | ) α ) + P s , R k − 1 , 1 ( ε e l e + ε a m p ( | x s − x k − 1 , 1 | ) α ) , x s ∈ [ x k − 1 , 1 , x k , 0 ] P s , R k , 0 ( ε e l e + ε a m p ( | x s − x k , 0 | ) α ) + P s , R k , 1 ( ε e l e + ε a m p ( | x s − x k , 1 | ) α ) , x s ∈ [ x k , 0 , x k , 1 ]

(11)

To prove Proposition 1 by contradiction.

Suppose that s a , s b ∈ C k , such that E s b , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) is the maximum value and E s a , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) is the minimum. If we cannot obtain Min { Max ( | E s b , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) − E s a , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) | ) } when r_k,1 is at x_k,1, there must be another position x′_k,1 to satisfy this. Assume that r′_k,1 is set on a position x′_k,1, such that E s b , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) is the max value and E s a , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) is the min. Then, for the sequence {r′_1,1,…, r′_k,1,…, r′_M,1}, |x′_k,1 − x′_k−1,1| = d₀. Suppose there are two points x_k,c and x_k,d such that |x′_k,1 − x_k,c| = |x_k,d − x′_k,1| = d₀/2 if r′_k,1 works. Without loss of generality, we assume x′_k,1 > x_k,1.

According to assumption, the RNs work for the same amount of time; we have P s b , r k , 0 = P s b , r k , 1 = P s b , r ′ k , 1 = P s a , r k , 0 = P s a , r k , 1 = P s a , r ′ k , 1 . The function E s , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) is continuous when x_s ∈ [x_k−1,1, x_k,0] or x_s ∈ [x_k,0, x_k,1]. According to Fermat’s theorem, let the two-order derivative of E s , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) equal zero, and we can get the min extreme points (x_k−1,1 + x_k,0)/2 or (x_k,0 + x_k,1)/2, respectively. Comparing the two extreme values, we get the same least value. We also get the global maximum value on the point x_sb = x_k,1 or x_sb = x_k,0 or x_sb = x_k−1,1. On the other side, E_s,tx({r′_k−1,1, r_k,0, r′_k,1}) is continuous when x_s ∈ [x_k−1,1, x′_k−1,1] or x_s ∈ [x′_k−1,1, x_k,0] or x_s ∈ [x_k,0, x_k,1], respectively. Then, according to Fermat’s theorem, E_s,tx({r′_k−1,1, r_k,0, r′_k,1}) has its minimum value on x ′ s a = ( x k , 0 + x ′ k , 1 ) / 2 and maximum on x ′ s b = x k , 0 or x ′ s b = x ′ k − 1 , 1 .

According to the hypothesis, if the proposition is mistakes we have | E s b , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) − E s a , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) | − ( | E s ′ b , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) − E s ′ a , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) | ) > 0 . For E_s,tx({r_k−1,1, r_k,0, r_k,1}) is a piecewise function, we have to consider two parts of them. So, the range [x_k−1,1, x_k,1] is divided into four parts [x_k−1,1, x′_k−1,1], [x′_k−1,1, x_k,0], [x_k,0, x_k,c], and [x_k,c, x_k,1].

First, when x_s ∈ [x_k,c, x_k,1], we have

ε amp ( | x s b − x k , 0 | ) α + ε amp ( | x s b − x k , 1 | ) α − ε amp ( | x s a − x k , 0 | ) α − ε amp ( | x s a − x k , 1 | ) α − ( ε amp ( | x s ′ b − x k , 0 | ) α + ε amp ( | x s ′ b − x ′ k , 1 | ) α − ε amp ( | x s ′ a − x k , 0 | ) α − ε amp ( | x s ′ a − x ′ k , 1 | ) α ) > 0

(12)

Let x ′ s b = x ′ k , 1 and x s b = x k , 1 , we have

( | x s b − x k , 0 | ) α − ( | x s a − x k , 0 | ) α − ( | x s a − x k , 1 | ) α − ( ( | x s ′ b − x k , 0 | ) α − ( | x s ′ a − x k , 0 | ) α − ( | x s ′ a − x ′ k , 1 | ) α ) > 0

(13)

when x_s ∈ [x_k,c, x_k,1], x ′ s a = ( x k , 0 + x ′ k , 1 ) / 2 and x s a = ( x k , 0 + x k , 1 ) / 2 , substitute them into formula (13), we have

( | x k , 1 − x k , 0 | ) α − 2 ( | x k , 1 − x k , 0 2 | ) α − ( ( | x ′ k , 1 − x k , 0 | ) α − 2 ( | x ′ k , 1 − x k , 0 2 | ) α ) > 0

(14)

However, according to the hypothesis, x′_k−1,1 > x_k−1,1 and x′_k,1 > x_k,1. Because 2 ≤ α ≤ 4 and the function x^α − 2(x/2) ^α is non-decreasing when x_s ∈ [x_k,c, x_k,1], we have

( | x k , 1 − x k , 0 | ) α − 2 ( | x k , 1 − x k , 0 2 | ) α ≤ ( ( | x ′ k , 1 − x k , 0 | ) α − 2 ( | x ′ k , 1 − x k , 0 2 | ) α )

(15)

According to formula (15), | E s b , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) − E s a , tx ( { r k − 1 , 1 , r k , 0 , r k , 1 } ) | − | E s ′ b , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) − E s ′ a , tx ( { r ′ k − 1 , 1 , r k , 0 , r ′ k , 1 } ) | ≤ 0 , which contradicts the assumption. We can get the same result when x_s ∈  [x_k−1,1, x′_k−1,1] or [x′_k−1,1, x_k,0] or [x_k,0, x_k,c]. We also encounter the same contradiction when x′_k,1,1 < x_k,1.

The above proposition leads us to an extended result: the lifetime of SNs is maximized if these substituted RNs owning the same working time obey uniform distribution throughout the cluster. This is formalized in the following proposition.

Proposition 2

Assume that there are M clusters on a straight line. Suppose that RN in cluster k is R_k (k ∈ {1, M}). All RNs {R_k} perform a VM. The location of node s in the kth cluster is x_s. For each interval of sequence {r_k,0}, n nodes in sequence {r_k,1,…, r_k,n} would be selected as RN in the kth cluster such that |x_k,i − x_k,i−1| = |x_k,j − x_k,j−1|, where r_k,i situated on x_k,i, ∀i, j ∈ {1,n} and i ≠ j. The number of bits relayed by r_k,i from node s is P S , r k , i . The energy dissipation of node s while transmitting messages during an RN switching process is E_s,tx. Then, the sequence {r_1,0,…, r_1,n,…, r_k0n,…, r_M,n} is a solution to problem (10) if P s , r k , i = P s , r k , j , i , j ∈ { 1 , n } .

According to the above proposition, we have some optimal position to deploy the RNs. We can add extra batteries to the nodes that perform the RNs’ VM to prolong the lifetime of normal SNs in WSN.

Moreover, we have to solve the problem of synchronization. Here, we refer to gossip methods. If the voltage of a working RN node is below a preset level, the conditions-satisfied RN would notify its neighbors and transmits the VM signal over the networks by gossips. Then, the RNs will be substituted in the whole networks. We describe an algorithm for the solution as follows.

OPEN IN VIEWER

VMRN Gossip Algorithm (VMRN-GA) pseudocode for RN r k,i .

Initial: Eflagid = 1, Clusterid = k, RNid = i, MVflag = 0, urgent bit bu = 0, Feedback = 0;

// For RNk,0 Eflagid = 0, MVflag is a public variable.

void ReceiveMSG_VM (Message msg){ // Receive messages with an urgent bit msg.bu from Ck and rk+1,0.

1. Read the urgent bit msg.bu;

2. If(msg.bu) {

3.  Read msg.MVflag; //A bit denotes the message is a MV command.

4.  If(msg.MVflag){ //MV starts.

5.   Read msg.Feedback bit;

6.   If(msg.Feedback == 1){ Eflagid = −1; MVflag = 0;} //RN becomes a normal sensor nodes if feedback msg received.

7.   Else{

8.    Read msg.Clusterid bit and msg.RNid bit;

9.    If(Clusterid == msg. Clusterid && msg.RNid == RNid){ // It is the RN named RNid whose turns to do VM.

10.     Eflagid = 1; // The RN r k,i begin to work.

11.     SendMsg_VM (Feedback, 1,0,currenttime); //To tell the RN who start VM that MV msg was received.

12.    }

13.    ElseIf(abs(Clusterid- msg. Clusterid) == 1){ //The VM message is from adjoining cluster

14.     If(!MVflag){ //To start VM and relay it

15.      MVflag = 1; SendMsg_VM(Null, MVflag,1,currenttime); //Node becomes a RN and disperses the MV gossip}

16.    }

17.   }

18.  } Else{

19.   Read other urgent bit and goto its handler; }

20. }Else{

21.  Calculate its own energy level Eremains and compare the result with thresholds th.

22.  If(Eremains<th){

23.   If(!MVflag){

24.    MVflag = 1; Sendmsg_VM(Null, MVflag,1,currenttime); }

25.   }Else SendMsg_VM(msg, 0,0,0);

26.  }

}

Int SendMsg_VM(Message msg, int MVflag, int count, Time time){

27.  If(!Eflagid){ //If a RN node is not a working RN it only sends what it sensed.

28.   Send sensing msgs; return;}

29.  If(MVflag){ //To start VM messages

30.   New a message msgn in which msgn.bu == 1 && msgn.MVflag == 1

31.   && msgn.Clusterid == Clusterid && msgn. RNid == msg.RNid+count;

32.   Wait(period);

33.   If(Compare(currenttime, time) > time requirement) count++; //RN decides whether the time is out.

34.   If(count > MaxRNid) send error msg.err;

35.   Else SendMsg_VM(Null, MVflag, count, time);

36.  }

37. }Else{ Relay msg; Send sensing msgs; } //If a RN node is a working RN it relays what it received.

}

The solution includes two functions. The ReceiveMSG_VM function analyzes received messages. If RN is a working RN, it will calculate its own remaining energy and decide whether to start a VM process. Eflagid belongs to an RN and denotes whether an RN is used. On the contrary, there are some bits in a message to show its status. The VM message is signed as an urgent message to avoid delaying and to spread across all network. A substituted RN will become active and relay messages after receiving the VM signal, MVflag == 1, for its turns. After the prior RN received a Feedback message from the newer, it becomes a normal SN. The SendMsg_VM function shows that RN would relay messages if no VM signal received or stops sending VM signal if a Feedback received. There is a deadline time for a signal feeding back. If no feedback signal received before the deadline time, the working RNs will select another substituted RN to work until all substituted RNs have been tested.