# An Efficient Algorithm of Constructing Virtual Backbone Scheduling for Maximizing the Lifetime of Dual-Radio Wireless Sensor Networks

Authors: Bing-Hong Liu; Van-Trung Pham; Ngoc-Tu Nguyen
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Wireless sensor networks have often been used to monitor environmental conditions, such as temperature, sound, and pressure. Because the sensors are expected to work on batteries for a long time without charging their batteries, the major challenge in the design of wireless sensor networks is to enhance the network lifetime. Recently, many researchers have studied the problem of constructing virtual backbones, which are backbones used for different time periods, to prolong the network lifetime. In this paper, we study the problem of constructing virtual backbones in dual-radio wireless sensor networks to maximize the network lifetime, called the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, where each sensor is equipped with two radio interfaces. The problem is shown to be NP-complete here. In addition, rather than proposing a centralized algorithm, a distributed algorithm, called a Dominating-Set-Based Algorithm (DSBA), is proposed for a wide range of wireless sensor networks to find a backbone when a new one is required. Simulation results show that the proposed algorithm outperforms some existing algorithms.


---

## Body

## 1. Introduction

Wireless sensor networks are composed of many wireless sensors deployed in a wide range of areas, where each sensor is able to communicate with others through intersensor wireless communication [1–5]. The wireless sensor networks are able to collect, process, and store environmental information [6–8]. In wireless sensor networks, the batteries are the main energy sources of sensors, while the sensor nodes are expected to work in batteries for a long time without charging their batteries. Therefore, energy efficiency in wireless sensor networks is the main issue that we address in this paper.Backbone is a well-known technique for various aspects of wireless sensor networks, such as routing, multicasting, and broadcasting [9, 10]. In the backbone technique, some nodes in the backbone always turn on their radio to maintain the activation of the network, and the rest of the nodes turn off their radio to save energy. Recently, many research studies are mostly designed to minimize the size of the backbone to, therefore, reduce the energy consumption in the network. In [11], an energy-efficient backbone construction algorithm is proposed for mobilead hoc networks with adjustable transmission ranges. In [10], an algorithm was proposed to construct a backbone in the wireless sensor network such that the cost of routing would be reduced. In [12], Chuang and Chen proposed a novel heuristic-based backbone algorithm, called SmartBone. In SmartBone, two steps are required to form a backbone to improve energy saving in the network. The first step is to find backbone nodes by the proposed flow-bottleneck preprocessing method, and the second step is to reduce the number of redundant nodes by the proposed dynamic density cutback method. In [13], Zhang et al. proposed an algorithm to construct a connected backbone in the wireless sensor network such that the network achieves much higher throughput and delivery ratio and much lower end-to-end delay and routing distance.Recently, some researchers focused on prolonging the network lifetime while using the backbone technique. The network lifetime is often determined by the time span from when the network is active to when one node in the backbone runs out of energy. In [14], Torkestani introduced an extended version of the connected dominating set problem for modeling the energy-efficient backbone formation problem in wireless sensor networks. In addition, an algorithm of constructing the network backbone was proposed to maximize the lifetime.Because the nodes in the backbone are always active, their energy is depleted quickly so that the backbone is easily broken. Therefore, to prolong the network lifetime, some researchers studied scheduling nodes to become backbone nodes during some periods of time and nonbackbone nodes during other periods. In [15], Zhao et al. studied the problem of finding multiple backbones and scheduling the backbones to work for different time periods such that the network lifetime would be maximized. Hereafter, the multiple backbones used for different periods were called virtual backbones. The problem is shown to be NP-hard in [15]. In addition, centralized algorithms are proposed to find and schedule virtual backbones to maximize the network lifetime. However, centralized algorithms are often not feasible in a wide range of wireless sensor networks [16, 17].In wireless sensor networks, sensors can be equipped with multiple radios to promote the capacity of wireless sensor networks, such as simultaneous data transmission and reception, and operations on different frequency bands. Several researchers study minimizing total energy consumption while using sensors having multiple radios [18–20]. In this paper, to maximize the network lifetime, we study the problem of scheduling virtual backbones for a dual-radio wireless sensor network such that the network lifetime is maximized. This Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem occurs when each node in the network is equipped with two radio interfaces, including small-range radio and large-range radio. We first show that the problem is NP-complete, which implies that no polynomial time algorithm exists for the problem unless P=NP. Rather than proposing a centralized algorithm of finding a list of backbones working sequentially to prolong the network lifetime, in this paper, we propose a distributed algorithm, termed Dominating-Set-Based Algorithm (DSBA), to find a backbone when a new backbone is required; that is, the network is initialized or one node in the backbone is going to run out of energy. The rest of this paper is organized as follows. Section 2 describes the details of the network model, introduces the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, and shows its hardness. Section 3 proposes the DSBA. In Section 4, we provide the theoretical analysis to show the correctness of the DSBA. In Section 5, we evaluate the performance of the DSBA in terms of the network lifetime in wireless sensor networks. Finally, in Section 6, we conclude this paper.


## 2. System Model and Problem Definition

### 2.1. System Model

In dual-radio wireless sensor networks [21–23], each sensor is equipped with two radios whose ranges are r and R, respectively, where r<R. Each sensor can use only one of the radios at the same time. When every sensor selects one radio for communication, two sensors can communicate with each other if any one of the sensors is within the radio range of the other sensor. The wireless sensor network can then be represented as an undirected weighted graph G(VG,EG,wG), where node v∈VG denotes a sensor in the networks, edge (u,v)∈EG represents the fact that u and v can communicate with each other, and wG(v) denotes the energy power of v for being backbone nodes. In the networks, the sink node is a special node that acts as a gateway between the networks and the outside networks. Here, the sink is assumed to have infinite energy power. Take Figure 1, for example, where the number near a node represents its corresponding energy, and node s is a sink. Figure 1(a) shows the wireless sensor network whose nodes use the same radio for communication. In addition, w(f)=9 and w(s)=∞. Figure 1(b) shows the wireless sensor network in which nodes c, f, k, and s use large-range radios.Figure 1
Example of dual-radio wireless sensor networks, where the number close to a node denotes the node’s energy. (a) The network topologyG1(VG1,EG1,wG1) formed by the nodes using small-range radios. (b) The network topology G2(VG2,EG2,wG2) formed by the nodes each using large-range or small-range radio.
(a)
(b)Many applications in wireless sensor networks use backbone techniques to provide the benefits of routing, reducing signal interference, and energy saving [13, 15, 24]. A backbone is formed by some nodes in the networks and has the following two properties. The first is that the backbone is a connected subnetwork; that is, it is a connected subgraph B(VB,EB) in G, where VB⊆VG and EB⊆EG. The second is that any node in the networks is either a backbone node or a neighboring node of a backbone node; that is, for each v∈VG, v∈VB or edge (u,v)∈EG for some u∈VB. Here, we assume that if a node v∈VG has energy power greater than zero, v is able to be a backbone node; otherwise, it is a nonbackbone node and can use only a small-range radio to connect to the backbone. Take Figure 1, for example. B1(VB1,EB1) and B2(VB2,EB2) are backbones in Figures 1(a) and 1(b), respectively, where VB1={a,d,e,s}, VB2={b,c,f,k,s}, EB1={(a,s),(a,d),(a,e),(d,e)}, and EB2={(b,s),(b,c),(c,f),(k,s)}.To reduce the energy consumption of sensors, we assume that each sensor in the networks is duty-cycled and has the same working cycle [15, 25, 26]. That is, the state of each sensor in the same working cycle is either in an active or sleep mode. If a sensor is in an active mode, the sensor turns on the radio for forwarding or receiving messages; otherwise, it turns off the radio to save energy. For simplicity, a working cycle is assumed to be one unit of time. To prolong the lifetime of wireless sensor networks, sensors are selected in turn to become backbone nodes for a number of working cycles. The backbones working in different periods of time are also called virtual backbones hereafter [9, 15]. When a virtual backbone is determined to work for some period of time, the nodes in the backbone are in an active mode, and the others are in a sleep mode in the period. Take Figure 1, for example. Let B1(VB1,EB1) in Figure 1(a) be the virtual backbone of the wireless sensor network starting at time 0; and the working time for B1 is 2, where VB1={a,d,e,s}. Let B2(VB2,EB2) in Figure 1(b) be another virtual backbone of the wireless sensor network starting at time 2; and the working time for B2 is 2, where VB2={b,c,f,k,s}. Note that nodes a, d, e, and s are active from time 0 to time 2, and nodes b, c, f, k, and s are active from time 2 to time 4. Also note that nodes c, f, and k use large-range radios from time 2 to time 4.In the networks, each nodev is associated with an energy power wG(v) [27, 28]. For simplicity, we assume that R=2r and a sensor with a small-range radio (or a large-range radio) in the backbone consumes 1 (or 2) unit of energy power for one unit of time. Therefore, the maximum time period for v with a small-range radio (or a large-range radio) to be a backbone node is wG(v) (or ⌊wG(v)/2⌋). Let the maximum lifetime of a sensor v, denoted by l(v), be the time span from when v is active to when its energy is depleted [15]. Take Figure 1, for example. Node a with a small-range radio in Figure 1(a) has maximum lifetime l(a)=2. In addition, node k with a large-range radio in Figure 1(b) has maximum lifetime l(k)=4/2=2. Let VB={v1,v2,…,vk} be the set of nodes in virtual backbone B. The maximum lifetime of backbone B, denoted by l(B), is defined as the time span from when the backbone is active to when the energy power of one node in B is depleted. That is, l(B)=min(l(v1),l(v2),…,l(vk)). Take Figure 1, for example. Let B1(VB1,EB1) in Figure 1(a) be the virtual backbone of the wireless sensor network starting at time 0, where VB1={a,d,e,s}. Because l(a)=2, l(d)=2, and l(e)=2, we have l(B1)=2. Therefore, backbone B1 can work for, at most, two units of time. Note that after time 2, nodes a, d, and e have zero energy power and cannot become backbone nodes anymore. Later, suppose that another virtual backbone B2 starts to work at time 2, where VB2={b,c,f,k,s}. Because l(b)=2/1=2, l(c)=⌊5/2⌋=2, l(f)=⌊9/2⌋=4, and l(k)=4/2=2, we have l(B2)=2. Therefore, the backbone B2 can continue to work for, at most, 2 units of time. In a wireless sensor network, if virtual backbones B1,B2,…,Bp work in turn for time periods T1,T2,…,Tp, in which T1≤l(B1),T2≤l(B2),…,Tp≤l(Bp), the network lifetime is defined as the sum of the working time of the virtual backbones; that is, ∑i=1pTi. In the previous example, the network lifetime is 2+2=4 when virtual backbones B1 and B2 work in turn for time periods 2 and 2, respectively.When the wireless sensor network is initialized, we assume that each sensor can then periodically use small-range and large-range radios to associate with other sensors. Therefore, each node can have the information of nodes within its radio ranger (or R), including the identification (ID) and residual energy power. Hereafter, the set of nodes within u’s radio range r (or R) is denoted by u·Nr (or u·NR). Take Figure 1, for example. Because nodes b, d, k, and s are within a’s radio range r, a·Nr={b,d,k,s}. In addition, because nodes a, b, c, d, e, and k are within s’s radio range R, s·NR={a,b,c,d,e,k}.


### 2.2. Problem Definition and Its Hardness

When we are given a dual-radio wireless sensor network, our problem is to find a schedule of virtual backbones, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is maximized. Our problem, called the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, is illustrated as follows:INSTANCE: the dual-radio wireless sensor network;QUESTION: does there exist a schedule of virtual backbones in the network, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is not less than k?In this paper, the Maximum Lifetime Backbone Scheduling problem [15] is used to show the hardness of the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, as shown in Theorem 1. The Maximum Lifetime Backbone Scheduling problem is illustrated as follows:INSTANCE: the single-radio wireless sensor network;QUESTION: does there exist a schedule of virtual backbones in the network, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is not less than k?Theorem 1.
The Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem is NP-complete.Proof.
The Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem clearly belongs to the NP class. In addition, because the Maximum Lifetime Backbone Scheduling problem [15] is NP-hard and is clearly to be the subproblem of the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem, the proof is therefore completed.


## 2.1. System Model

In dual-radio wireless sensor networks [21–23], each sensor is equipped with two radios whose ranges are r and R, respectively, where r<R. Each sensor can use only one of the radios at the same time. When every sensor selects one radio for communication, two sensors can communicate with each other if any one of the sensors is within the radio range of the other sensor. The wireless sensor network can then be represented as an undirected weighted graph G(VG,EG,wG), where node v∈VG denotes a sensor in the networks, edge (u,v)∈EG represents the fact that u and v can communicate with each other, and wG(v) denotes the energy power of v for being backbone nodes. In the networks, the sink node is a special node that acts as a gateway between the networks and the outside networks. Here, the sink is assumed to have infinite energy power. Take Figure 1, for example, where the number near a node represents its corresponding energy, and node s is a sink. Figure 1(a) shows the wireless sensor network whose nodes use the same radio for communication. In addition, w(f)=9 and w(s)=∞. Figure 1(b) shows the wireless sensor network in which nodes c, f, k, and s use large-range radios.Figure 1
Example of dual-radio wireless sensor networks, where the number close to a node denotes the node’s energy. (a) The network topologyG1(VG1,EG1,wG1) formed by the nodes using small-range radios. (b) The network topology G2(VG2,EG2,wG2) formed by the nodes each using large-range or small-range radio.
(a)
(b)Many applications in wireless sensor networks use backbone techniques to provide the benefits of routing, reducing signal interference, and energy saving [13, 15, 24]. A backbone is formed by some nodes in the networks and has the following two properties. The first is that the backbone is a connected subnetwork; that is, it is a connected subgraph B(VB,EB) in G, where VB⊆VG and EB⊆EG. The second is that any node in the networks is either a backbone node or a neighboring node of a backbone node; that is, for each v∈VG, v∈VB or edge (u,v)∈EG for some u∈VB. Here, we assume that if a node v∈VG has energy power greater than zero, v is able to be a backbone node; otherwise, it is a nonbackbone node and can use only a small-range radio to connect to the backbone. Take Figure 1, for example. B1(VB1,EB1) and B2(VB2,EB2) are backbones in Figures 1(a) and 1(b), respectively, where VB1={a,d,e,s}, VB2={b,c,f,k,s}, EB1={(a,s),(a,d),(a,e),(d,e)}, and EB2={(b,s),(b,c),(c,f),(k,s)}.To reduce the energy consumption of sensors, we assume that each sensor in the networks is duty-cycled and has the same working cycle [15, 25, 26]. That is, the state of each sensor in the same working cycle is either in an active or sleep mode. If a sensor is in an active mode, the sensor turns on the radio for forwarding or receiving messages; otherwise, it turns off the radio to save energy. For simplicity, a working cycle is assumed to be one unit of time. To prolong the lifetime of wireless sensor networks, sensors are selected in turn to become backbone nodes for a number of working cycles. The backbones working in different periods of time are also called virtual backbones hereafter [9, 15]. When a virtual backbone is determined to work for some period of time, the nodes in the backbone are in an active mode, and the others are in a sleep mode in the period. Take Figure 1, for example. Let B1(VB1,EB1) in Figure 1(a) be the virtual backbone of the wireless sensor network starting at time 0; and the working time for B1 is 2, where VB1={a,d,e,s}. Let B2(VB2,EB2) in Figure 1(b) be another virtual backbone of the wireless sensor network starting at time 2; and the working time for B2 is 2, where VB2={b,c,f,k,s}. Note that nodes a, d, e, and s are active from time 0 to time 2, and nodes b, c, f, k, and s are active from time 2 to time 4. Also note that nodes c, f, and k use large-range radios from time 2 to time 4.In the networks, each nodev is associated with an energy power wG(v) [27, 28]. For simplicity, we assume that R=2r and a sensor with a small-range radio (or a large-range radio) in the backbone consumes 1 (or 2) unit of energy power for one unit of time. Therefore, the maximum time period for v with a small-range radio (or a large-range radio) to be a backbone node is wG(v) (or ⌊wG(v)/2⌋). Let the maximum lifetime of a sensor v, denoted by l(v), be the time span from when v is active to when its energy is depleted [15]. Take Figure 1, for example. Node a with a small-range radio in Figure 1(a) has maximum lifetime l(a)=2. In addition, node k with a large-range radio in Figure 1(b) has maximum lifetime l(k)=4/2=2. Let VB={v1,v2,…,vk} be the set of nodes in virtual backbone B. The maximum lifetime of backbone B, denoted by l(B), is defined as the time span from when the backbone is active to when the energy power of one node in B is depleted. That is, l(B)=min(l(v1),l(v2),…,l(vk)). Take Figure 1, for example. Let B1(VB1,EB1) in Figure 1(a) be the virtual backbone of the wireless sensor network starting at time 0, where VB1={a,d,e,s}. Because l(a)=2, l(d)=2, and l(e)=2, we have l(B1)=2. Therefore, backbone B1 can work for, at most, two units of time. Note that after time 2, nodes a, d, and e have zero energy power and cannot become backbone nodes anymore. Later, suppose that another virtual backbone B2 starts to work at time 2, where VB2={b,c,f,k,s}. Because l(b)=2/1=2, l(c)=⌊5/2⌋=2, l(f)=⌊9/2⌋=4, and l(k)=4/2=2, we have l(B2)=2. Therefore, the backbone B2 can continue to work for, at most, 2 units of time. In a wireless sensor network, if virtual backbones B1,B2,…,Bp work in turn for time periods T1,T2,…,Tp, in which T1≤l(B1),T2≤l(B2),…,Tp≤l(Bp), the network lifetime is defined as the sum of the working time of the virtual backbones; that is, ∑i=1pTi. In the previous example, the network lifetime is 2+2=4 when virtual backbones B1 and B2 work in turn for time periods 2 and 2, respectively.When the wireless sensor network is initialized, we assume that each sensor can then periodically use small-range and large-range radios to associate with other sensors. Therefore, each node can have the information of nodes within its radio ranger (or R), including the identification (ID) and residual energy power. Hereafter, the set of nodes within u’s radio range r (or R) is denoted by u·Nr (or u·NR). Take Figure 1, for example. Because nodes b, d, k, and s are within a’s radio range r, a·Nr={b,d,k,s}. In addition, because nodes a, b, c, d, e, and k are within s’s radio range R, s·NR={a,b,c,d,e,k}.


## 2.2. Problem Definition and Its Hardness

When we are given a dual-radio wireless sensor network, our problem is to find a schedule of virtual backbones, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is maximized. Our problem, called the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, is illustrated as follows:INSTANCE: the dual-radio wireless sensor network;QUESTION: does there exist a schedule of virtual backbones in the network, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is not less than k?In this paper, the Maximum Lifetime Backbone Scheduling problem [15] is used to show the hardness of the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, as shown in Theorem 1. The Maximum Lifetime Backbone Scheduling problem is illustrated as follows:INSTANCE: the single-radio wireless sensor network;QUESTION: does there exist a schedule of virtual backbones in the network, that is, a set of 2-tuples{(B1,T1),(B2,T2),…,(Bp,Tp)}, such that the network lifetime is not less than k?Theorem 1.
The Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem is NP-complete.Proof.
The Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem clearly belongs to the NP class. In addition, because the Maximum Lifetime Backbone Scheduling problem [15] is NP-hard and is clearly to be the subproblem of the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem, the proof is therefore completed.


## 3. The Dominating-Set-Based Algorithm (DSBA)

Because the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Networks problem is NP-complete, it is hard to find an exact solution in polynomial time. Rather than finding a list of backbones working for different periods of time, our idea is to find a backbone for any given dual-radio wireless sensor networks when a new backbone is required for the networks. That is, when the network is initialized or one node in the backbone is going to run out of energy, we will find another new backbone for sustaining the network lifetime. For the problem, we propose a distributed algorithm, called a Dominating-Set-Based Algorithm (DSBA), to find a backbone for any given dual-radio wireless sensor network, where each backbone node has an energy power greater than zero. The DSBA contains three steps. In the first step, the DSBA finds a dominating set in the wireless sensor network such that the nodes in the set have much energy power, which is illustrated in Section3.1. Here, a dominating set for a graph G′(VG′,EG′) is a set D⊆VG′ such that each node v∈VG′ is either in D or is connected to one node u∈D in G′ [29, 30]. In the second step, a backbone is established based on the selected dominating set, which is described in Section 3.2. Finally, some redundant nodes are pruned from the backbone to reduce the size of the backbone and minimize total energy consumption, which is given in Section 3.3. The necessary notation used in the section is defined in Definition 2.Definition 2.
Given a set of nodesS in a dual-radio wireless sensor network, node v∈S is said to be the most powerful node in S if (w(v)>w(p)) or (w(v)=w(p) and v·ID<p·ID) for all p∈S-{v}, where v·ID denotes v’s ID.


### 3.1. Construction of Dominating Set

In this step, our goal is to construct a dominating set for a given dual-radio wireless sensor network such that the nodes in the set have enough energy power to be the backbone nodes and can dominate all nodes in the network. Although the dominating set problem has been studied by many researchers [29, 31, 32], they do not consider the energy power while selecting nodes to be included in the dominating set. Therefore, in the subsection, we propose a distributed algorithm to construct the dominating set D for the network, called the distributed dominating set algorithm (DDSA), such that the nodes in D have enough energy to be the backbone nodes.Let the nodes included in the dominating set be called dominating nodes. In the DDSA, our idea is to let the sink node be a dominating node first because the sink node is a powerful node. Then, if a nodev has no energy power or has a dominating node within v’s radio range r, v is not considered to be the dominating node; otherwise, v is considered to be a dominating node. Algorithm 1 shows the DDSA executed by every node in the network.Algorithm 1:
DDSA
(
v
).
(1) if  v is a white node and receives a message m that is a BLACK_SET or GRAY_SET message  then
(2)  if  w(v)=0 or m is a BLACK_SET message  then
(3)   v is marked as gray.
(4)   v uses a small-range radio to locally broadcast the GRAY_SET message.
(5)  else if  m is a GRAY_SET message from node u  then
(6)  if v is the most powerful node in u⋅Nrh∩v⋅Nrh∪{v}  then
(7)   v is marked as black.
(8)   v uses a small-range radio to locally broadcast the BLACK_SET message.
(9)  end if
(10)  end if
(11) end ifInitially, every nodev is marked as white. The sink node s is then marked as black and uses a small-range radio to locally broadcast the BLACK_SET message. If a white node v receives the BLACK_SET message, v marks itself as gray and uses a small-range radio to locally broadcast the GRAY_SET message, including v·Nrh, where v·Nrh denotes the set of white nodes within v’s small radio range r, as described in Lines 2–4 in Algorithm 1. Otherwise, if a white node v receives a GRAY_SET or BLACK_SET message but has no energy power for being backbone nodes, that is, w(v)=0, v marks itself as gray and locally broadcasts the GRAY_SET message as described in Lines 2–4 in Algorithm 1. Otherwise, if a white node v receives a GRAY_SET message from node u, and v is the most powerful node in u·Nrh∩v·Nrh∪{v}, v marks itself as black and uses a small-range radio to locally broadcast the BLACK_SET message, as described in Lines 5–9 in Algorithm 1. Note that if the BLACK_SET (or GRAY_SET) message from node u is received by a node v, v updates its local information to set u as black (or gray).Take Figure1(b), for example. Initially, every node in the network is white. The sink node s first marks itself as black and locally broadcasts a BLACK_SET message by using a small-range radio. Each of nodes a and b that receives the message will become gray and locally broadcasts a GRAY_SET message as described in Lines 2–4 in Algorithm 1. Then nodes c and k that receive the GRAY_SET message will become black because they have higher energy power, according to Lines 5–9 in Algorithm 1. In addition, nodes d and e become gray and locally broadcast GRAY_SET messages because they have no energy power for being backbone nodes. Node f then becomes black because w(f)>w(i)>w(h)>w(g). In addition, node j becomes gray because node c is black. Finally, the DDSA constructs the set {c,f,s,k} as the dominating set.


### 3.2.  Establishment of Backbone

In this subsection, we propose a distributed backbone algorithm (DBA) to establish a backbone according to the dominating set constructed by the DDSA. In the DBA, the idea is first to treat the sink node as the smallest connected subnetwork having only one node. Then, the subnetwork gradually merges its nearby black nodes and suitable gray nodes that are obtained by the DDSA to form a larger connected subnetwork until a backbone of the network is established. After applying the DBA, the nodes in the network are either backbone nodes represented by the blue nodes or nonbackbone nodes represented by the yellow nodes and gray nodes. Algorithm2 shows the DBA executed by every node in the network.Algorithm 2:
DBA
(
v
).
(
1) if  v receives a BACKBONE_REQ_r (or BACKBONE_REQ_R) message  then
(2)  v is marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message.
(3)  v uses a small-range (or a large-range) radio in the backbone.
(4) else if  v receives a message m from node u that is a DBA_SET_B or DBA_SET_Y message  then
(5)  v marks u as blue (or yellow) in its local information if m is a DBA_SET_B (or DBA_SET_Y) message.
(6)  if  v is a gray node, w(v)>0, and there exists a blue node p∈v⋅Nr  then
(7)   v uses a large-range radio to locally broadcast the DBA_SET_Y message.
(8)   v is marked as yellow and uses a small-range radio in the network.
(9)  else if  v is a black node then
(10)  v is marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message.
(11)  if  there exists a blue node p∈v⋅Nr  then
(12)   v uses a small-range radio in the backbone.
(13)  else if  there exists a most powerful node p∈Yr, where Yr is the set of yellow nodes in v⋅Nr  then
(14)   v uses a small-range radio in the backbone and sends a BACKBONE_REQ_r message to p.
(15)  else if  there exists a most powerful node p∈BR, where BR is the set of blue nodes in v⋅NR  then
(16)   v uses a large-range radio in the backbone and sends a BACKBONE_REQ_R message to p.
(17)  else if  there exists a most powerful node p∈YR, where YR is the set of yellow nodes in v⋅NR  then
(18)   v uses a large-range radio in the backbone and sends a BACKBONE_REQ_R message to p.
(19)  end if
(20) end if
(21) end ifIn the DBA, every node is initially a black or gray node after applying the DDSA. The sink nodes is then marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message that is used to inform other nodes about the existence of the blue node and the connected subnetwork. If a gray node v having enough power receives the message, v marks itself as yellow, which is used to denote v as the node close to the connected subnetwork and able to be a candidate for becoming a backbone node, which is described in Lines 6–8 of Algorithm 2. Node v also uses a large-range radio to locally broadcast the DBA_SET_Y message that is used to inform other nodes about the existence of the yellow node. Then v uses a small-range radio in the network later. If a black node v receives the DBA_SET_B or DBA_SET_Y message, it implies that v is close to the connected subnetwork. Node v then marks itself as blue and tries to find a yellow or blue node p such that v can connect to the connected subnetwork through p, which is described in Lines 9–20 of Algorithm 2. If v finds that there exists a blue node p in v·Nr, v can use a small-range radio to connect to the connected subnetwork by p. Otherwise, if v finds that there exists a most powerful yellow node p in v·Nr, v will send a BACKBONE_REQ_r message to request p to become a blue node and use a small-range radio in the backbone. Otherwise, if v finds that there exists a most powerful blue node in v·NR, v will send a BACKBONE_REQ_R message to request p to use a large-range radio in the backbone. Otherwise, if v finds that there exists a most powerful yellow node in v·NR, v will send a BACKBONE_REQ_R message to request p to become a blue node and use a large-range radio in the backbone.Take Figure1(b), for example. Assume that after applying the DDSA, the nodes c, f, s, and k are black nodes, and the others are gray nodes. In the DBA, the sink node s first marks itself as blue and locally broadcasts a DBA_SET_B message. Then, the nodes that are within s’s large-radio range, that is, nodes a, b, c, d, e, and k, receive the DBA_SET_B message from s. Nodes a, d, and e are still gray nodes because their energy power is equal to zero. In addition, node b becomes yellow because blue node s∈b·Nr. Node c (or k) becomes blue because c (or k) is a black node. Because b is a most powerful yellow node in c·Nr, c requests b to become a blue node later. Then, b and c use a small-range radio in the backbone. Because blue node s∈k·NR, k requests s to use a large-range radio in the backbone. Therefore, k and s use a large-range radio in the backbone. Later, when node f receives a DBA_SET_B or DBA_SET_Y message, f becomes a blue node that uses a large-range radio because f is a black node, and blue node c∈b·NR. Node f then requests c to use a large-range radio in the backbone. When node g, h, i, or j receives a DBA_SET_B or DBA_SET_Y message, it becomes yellow because there exists a blue node in its small-range radio. After applying the DBA, b, c, k, f, and s are backbone nodes, where b uses a small-range radio, and the others use a large-range radio in the backbone.


### 3.3. Refinement of Backbone

When the DBA is completed, the nodes in the network are classified into backbone and nonbackbone nodes, where the blue nodes are backbone nodes, and the gray nodes and yellow nodes are nonbackbone nodes. In the next step, we provide a refinement for the generated backbone to minimize the size of the generated backbone or reduce the energy consumption of backbone nodes, where the refinement contains two rules mentioned in the following paragraph.From the observation of the generated backbones, we discover that if a backbone nodev can change its large-range radio to a small-range radio such that the backbone is still connected, the energy consumption of v for being a backbone node is reduced. Take Figure 2, for example. In Figure 2(a), backbone nodes u, v, x, and y use a large-range radio, but the distance between u and v is smaller than the radio range r. If we can change v’s large-range radio to a small-range radio, as shown in Figure 2(b), the backbone is still connected, and the energy consumption of v for being a backbone node is, thus, reduced. Therefore, the first rule is to change one backbone node’s radio in such case, as described in Rule 1.Figure 2
An example of reducing the energy consumption of backbone nodes. (a) Nodesu, v, x, and y use a large-range radio in the backbone. (b) Node v uses a small-range radio, and the others use a large-range radio in the backbone.
(a)
(b)Rule 1.
Given a backboneB, let v be any node that uses a large-range radio in B. Assume that G′=(VG′,EG′) is formed by v and all its neighboring nodes in the backbone, where VG′={u1,u2,…,uk-1,v}. If G′ is a k-clique network, there exists a node p∈VG′, p∈v·Nr, and p is the most powerful node in {v,p}; v can change to a small-range radio in the backbone.To minimize the size of the generated backbone, some nodes can be pruned from the backbone if they are redundant. That is, if all the neighboring nodes of a backbone nodev having a small-range radio in the backbone are dominated by another backbone node u, v is considered as a redundant backbone node and can be pruned. Take Figure 3, for example. In Figure 3(a), nodes u and v are backbone nodes. It shows that the set of the neighboring nodes of a backbone node u is {v,x,y,z}, and the set of the neighboring nodes of a backbone node v is {u,x,y}. Clearly, all neighboring nodes of node v in the backbone, that is, nodes u, x, and y, can be dominated by node u. Therefore, v can be pruned from the backbone, which is shown in Figure 3(b). Therefore, the second rule is to reduce the number of redundant backbone nodes in such case, as described in Rule 2.Figure 3
An example of pruning redundant backbone nodes. (a) The network has a redundant backbone nodev. (b) Node v is pruned from the backbone, shown in (a).
(a)
(b)Rule 2.
Given a backboneB, let v be any node that uses a small-range radio in B. Node v can be pruned from the backbone if there exists another backbone node u such that u∈v·Nr, v·Nr-{u}⊆u·Nr-{v}, and u is the most powerful node in {u,v}.


## 3.1. Construction of Dominating Set

In this step, our goal is to construct a dominating set for a given dual-radio wireless sensor network such that the nodes in the set have enough energy power to be the backbone nodes and can dominate all nodes in the network. Although the dominating set problem has been studied by many researchers [29, 31, 32], they do not consider the energy power while selecting nodes to be included in the dominating set. Therefore, in the subsection, we propose a distributed algorithm to construct the dominating set D for the network, called the distributed dominating set algorithm (DDSA), such that the nodes in D have enough energy to be the backbone nodes.Let the nodes included in the dominating set be called dominating nodes. In the DDSA, our idea is to let the sink node be a dominating node first because the sink node is a powerful node. Then, if a nodev has no energy power or has a dominating node within v’s radio range r, v is not considered to be the dominating node; otherwise, v is considered to be a dominating node. Algorithm 1 shows the DDSA executed by every node in the network.Algorithm 1:
DDSA
(
v
).
(1) if  v is a white node and receives a message m that is a BLACK_SET or GRAY_SET message  then
(2)  if  w(v)=0 or m is a BLACK_SET message  then
(3)   v is marked as gray.
(4)   v uses a small-range radio to locally broadcast the GRAY_SET message.
(5)  else if  m is a GRAY_SET message from node u  then
(6)  if v is the most powerful node in u⋅Nrh∩v⋅Nrh∪{v}  then
(7)   v is marked as black.
(8)   v uses a small-range radio to locally broadcast the BLACK_SET message.
(9)  end if
(10)  end if
(11) end ifInitially, every nodev is marked as white. The sink node s is then marked as black and uses a small-range radio to locally broadcast the BLACK_SET message. If a white node v receives the BLACK_SET message, v marks itself as gray and uses a small-range radio to locally broadcast the GRAY_SET message, including v·Nrh, where v·Nrh denotes the set of white nodes within v’s small radio range r, as described in Lines 2–4 in Algorithm 1. Otherwise, if a white node v receives a GRAY_SET or BLACK_SET message but has no energy power for being backbone nodes, that is, w(v)=0, v marks itself as gray and locally broadcasts the GRAY_SET message as described in Lines 2–4 in Algorithm 1. Otherwise, if a white node v receives a GRAY_SET message from node u, and v is the most powerful node in u·Nrh∩v·Nrh∪{v}, v marks itself as black and uses a small-range radio to locally broadcast the BLACK_SET message, as described in Lines 5–9 in Algorithm 1. Note that if the BLACK_SET (or GRAY_SET) message from node u is received by a node v, v updates its local information to set u as black (or gray).Take Figure1(b), for example. Initially, every node in the network is white. The sink node s first marks itself as black and locally broadcasts a BLACK_SET message by using a small-range radio. Each of nodes a and b that receives the message will become gray and locally broadcasts a GRAY_SET message as described in Lines 2–4 in Algorithm 1. Then nodes c and k that receive the GRAY_SET message will become black because they have higher energy power, according to Lines 5–9 in Algorithm 1. In addition, nodes d and e become gray and locally broadcast GRAY_SET messages because they have no energy power for being backbone nodes. Node f then becomes black because w(f)>w(i)>w(h)>w(g). In addition, node j becomes gray because node c is black. Finally, the DDSA constructs the set {c,f,s,k} as the dominating set.


## 3.2.  Establishment of Backbone

In this subsection, we propose a distributed backbone algorithm (DBA) to establish a backbone according to the dominating set constructed by the DDSA. In the DBA, the idea is first to treat the sink node as the smallest connected subnetwork having only one node. Then, the subnetwork gradually merges its nearby black nodes and suitable gray nodes that are obtained by the DDSA to form a larger connected subnetwork until a backbone of the network is established. After applying the DBA, the nodes in the network are either backbone nodes represented by the blue nodes or nonbackbone nodes represented by the yellow nodes and gray nodes. Algorithm2 shows the DBA executed by every node in the network.Algorithm 2:
DBA
(
v
).
(
1) if  v receives a BACKBONE_REQ_r (or BACKBONE_REQ_R) message  then
(2)  v is marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message.
(3)  v uses a small-range (or a large-range) radio in the backbone.
(4) else if  v receives a message m from node u that is a DBA_SET_B or DBA_SET_Y message  then
(5)  v marks u as blue (or yellow) in its local information if m is a DBA_SET_B (or DBA_SET_Y) message.
(6)  if  v is a gray node, w(v)>0, and there exists a blue node p∈v⋅Nr  then
(7)   v uses a large-range radio to locally broadcast the DBA_SET_Y message.
(8)   v is marked as yellow and uses a small-range radio in the network.
(9)  else if  v is a black node then
(10)  v is marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message.
(11)  if  there exists a blue node p∈v⋅Nr  then
(12)   v uses a small-range radio in the backbone.
(13)  else if  there exists a most powerful node p∈Yr, where Yr is the set of yellow nodes in v⋅Nr  then
(14)   v uses a small-range radio in the backbone and sends a BACKBONE_REQ_r message to p.
(15)  else if  there exists a most powerful node p∈BR, where BR is the set of blue nodes in v⋅NR  then
(16)   v uses a large-range radio in the backbone and sends a BACKBONE_REQ_R message to p.
(17)  else if  there exists a most powerful node p∈YR, where YR is the set of yellow nodes in v⋅NR  then
(18)   v uses a large-range radio in the backbone and sends a BACKBONE_REQ_R message to p.
(19)  end if
(20) end if
(21) end ifIn the DBA, every node is initially a black or gray node after applying the DDSA. The sink nodes is then marked as blue and uses a large-range radio to locally broadcast the DBA_SET_B message that is used to inform other nodes about the existence of the blue node and the connected subnetwork. If a gray node v having enough power receives the message, v marks itself as yellow, which is used to denote v as the node close to the connected subnetwork and able to be a candidate for becoming a backbone node, which is described in Lines 6–8 of Algorithm 2. Node v also uses a large-range radio to locally broadcast the DBA_SET_Y message that is used to inform other nodes about the existence of the yellow node. Then v uses a small-range radio in the network later. If a black node v receives the DBA_SET_B or DBA_SET_Y message, it implies that v is close to the connected subnetwork. Node v then marks itself as blue and tries to find a yellow or blue node p such that v can connect to the connected subnetwork through p, which is described in Lines 9–20 of Algorithm 2. If v finds that there exists a blue node p in v·Nr, v can use a small-range radio to connect to the connected subnetwork by p. Otherwise, if v finds that there exists a most powerful yellow node p in v·Nr, v will send a BACKBONE_REQ_r message to request p to become a blue node and use a small-range radio in the backbone. Otherwise, if v finds that there exists a most powerful blue node in v·NR, v will send a BACKBONE_REQ_R message to request p to use a large-range radio in the backbone. Otherwise, if v finds that there exists a most powerful yellow node in v·NR, v will send a BACKBONE_REQ_R message to request p to become a blue node and use a large-range radio in the backbone.Take Figure1(b), for example. Assume that after applying the DDSA, the nodes c, f, s, and k are black nodes, and the others are gray nodes. In the DBA, the sink node s first marks itself as blue and locally broadcasts a DBA_SET_B message. Then, the nodes that are within s’s large-radio range, that is, nodes a, b, c, d, e, and k, receive the DBA_SET_B message from s. Nodes a, d, and e are still gray nodes because their energy power is equal to zero. In addition, node b becomes yellow because blue node s∈b·Nr. Node c (or k) becomes blue because c (or k) is a black node. Because b is a most powerful yellow node in c·Nr, c requests b to become a blue node later. Then, b and c use a small-range radio in the backbone. Because blue node s∈k·NR, k requests s to use a large-range radio in the backbone. Therefore, k and s use a large-range radio in the backbone. Later, when node f receives a DBA_SET_B or DBA_SET_Y message, f becomes a blue node that uses a large-range radio because f is a black node, and blue node c∈b·NR. Node f then requests c to use a large-range radio in the backbone. When node g, h, i, or j receives a DBA_SET_B or DBA_SET_Y message, it becomes yellow because there exists a blue node in its small-range radio. After applying the DBA, b, c, k, f, and s are backbone nodes, where b uses a small-range radio, and the others use a large-range radio in the backbone.


## 3.3. Refinement of Backbone

When the DBA is completed, the nodes in the network are classified into backbone and nonbackbone nodes, where the blue nodes are backbone nodes, and the gray nodes and yellow nodes are nonbackbone nodes. In the next step, we provide a refinement for the generated backbone to minimize the size of the generated backbone or reduce the energy consumption of backbone nodes, where the refinement contains two rules mentioned in the following paragraph.From the observation of the generated backbones, we discover that if a backbone nodev can change its large-range radio to a small-range radio such that the backbone is still connected, the energy consumption of v for being a backbone node is reduced. Take Figure 2, for example. In Figure 2(a), backbone nodes u, v, x, and y use a large-range radio, but the distance between u and v is smaller than the radio range r. If we can change v’s large-range radio to a small-range radio, as shown in Figure 2(b), the backbone is still connected, and the energy consumption of v for being a backbone node is, thus, reduced. Therefore, the first rule is to change one backbone node’s radio in such case, as described in Rule 1.Figure 2
An example of reducing the energy consumption of backbone nodes. (a) Nodesu, v, x, and y use a large-range radio in the backbone. (b) Node v uses a small-range radio, and the others use a large-range radio in the backbone.
(a)
(b)Rule 1.
Given a backboneB, let v be any node that uses a large-range radio in B. Assume that G′=(VG′,EG′) is formed by v and all its neighboring nodes in the backbone, where VG′={u1,u2,…,uk-1,v}. If G′ is a k-clique network, there exists a node p∈VG′, p∈v·Nr, and p is the most powerful node in {v,p}; v can change to a small-range radio in the backbone.To minimize the size of the generated backbone, some nodes can be pruned from the backbone if they are redundant. That is, if all the neighboring nodes of a backbone nodev having a small-range radio in the backbone are dominated by another backbone node u, v is considered as a redundant backbone node and can be pruned. Take Figure 3, for example. In Figure 3(a), nodes u and v are backbone nodes. It shows that the set of the neighboring nodes of a backbone node u is {v,x,y,z}, and the set of the neighboring nodes of a backbone node v is {u,x,y}. Clearly, all neighboring nodes of node v in the backbone, that is, nodes u, x, and y, can be dominated by node u. Therefore, v can be pruned from the backbone, which is shown in Figure 3(b). Therefore, the second rule is to reduce the number of redundant backbone nodes in such case, as described in Rule 2.Figure 3
An example of pruning redundant backbone nodes. (a) The network has a redundant backbone nodev. (b) Node v is pruned from the backbone, shown in (a).
(a)
(b)Rule 2.
Given a backboneB, let v be any node that uses a small-range radio in B. Node v can be pruned from the backbone if there exists another backbone node u such that u∈v·Nr, v·Nr-{u}⊆u·Nr-{v}, and u is the most powerful node in {u,v}.


## 4. Analysis of the DSBA

Assume that the dual-radio wireless sensor network is connected when every sensor uses a small-range radio. Also assume that every sensor has energy power greater than zero. Theorem6 shows that the DSBA constructs a backbone for the network by Lemmas 3–5.Lemma 3.
In the DDSA, the set of the black nodes in the dual-radio wireless sensor network forms a dominating set.Proof.
Here, we first show that (S1) any white nodev in the network that receives a GRAY_SET message from node u will become a gray or black node later in the DDSA. Clearly, v will become a black node if v is the most powerful node in u·Nrh∩v·Nrh∪{v}. It suffices to show that v will become a gray or black node if v is not the most powerful node in u·Nrh∩v·Nrh∪{v}. Let p11,p21,…,pn1∈u·Nrh∩v·Nrh∪{v} be more powerful than v, and w(p11)>w(p21)>⋯>w(pn1)>w(v). If p11 does not become a black node later, it implies that there exists a white node p12∈u·Nrh∩p11·Nrh∪{p11} more powerful than p11. If p12 does not become a black node later, it implies that there exists a white node p13∈u·Nrh∩p12·Nrh∪{p12} more powerful than p12. Then, there always exists a white node p1n∈u·Nrh∩p1n-1·Nrh∪{p1n-1} more powerful than p1n-1 and becomes a black node later. It implies that p1n-1 becomes a gray node. Then we have that p1n-2 becomes a black node if no other neighboring white node is more powerful than p1n-2; otherwise, p1n-2 becomes a gray node. Continuing the same argument, p11 becomes a black or gray node later. Therefore, each of p21,…,pn1 becomes a black or gray node later. If all of p11,p21,…,pn1 become gray nodes, v becomes a black node later because v is the last node that is still white and the most powerful in u·Nrh∩v·Nrh∪{v}. Otherwise, v becomes a gray node because one of p11,p21,…,pn1 is black. This completes proof S1.
Next, we prove that (S2) if there exists a nodex that does not mark itself as gray or black in the DDSA, all nodes in x·Nr are all white. Assume that there exists a node x that does not mark itself as gray or black in the DDSA. Clearly, there is no black node in x·Nr, or x will mark itself as gray. In addition, according to S1, because any white node v in the network receiving a GRAY_SET message will become a gray or black node later in the DDSA, it implies that x does not receive any GRAY_SET message from its neighbors. This implies that all nodes in x·Nr are all white, which completes proof S2.
For the proof, because a nodew marks itself as gray only if there exists a black node in w·Nr in the DDSA, it suffices to show that every node marks itself as gray or black. Assume that there exists a node w that does not mark itself as gray or black in the DDSA. Because the network is connected, there exists a path p=(w,w1,w2,…,wn,s) in the network, where s is the sink node. Because w does not mark itself as gray or black, it implies that w1 is white and does not mark itself as gray or black according to S2. This also implies that w2,…,wn, and s is all white and does not mark itself as gray or black according to S2. However, s is the sink node and marks itself as black in the beginning of the DDSA. This constitutes a contradiction, which, thus, completes the proof.Lemma 4.
The DBA constructs a backbone for the dual-radio wireless sensor network.Proof.
According to Lemma3, the set of the black nodes forms a dominating set. In addition, because the black nodes become blue nodes in the DBA, it suffices to show that the blue nodes used to construct the backbone are connected. Assume that there exists a blue node v not connected to the sink node s. We know that any node x, except the sink node, becomes a blue node only if x is a black node that receives a DBA_SET_B or DBA_SET_Y message or a yellow node that receives a BACKBONE_REQ_r or BACKBONE_REQ_R message. If v is the black node that receives a DBA_SET_B or DBA_SET_Y message, it always can find a blue node p1, which is in v·Nr or v·NR, and is close to the node that generates the first DBA_SET_B message. Otherwise, if v is the yellow node that receives a BACKBONE_REQ_r or BACKBONE_REQ_R message, it always can find a blue node p1, which is in v·Nr, and is close to the node that generates the first DBA_SET_B message. Therefore, in any of the cases, v always can find a blue node p1 that is close to the node that generates the first DBA_SET_B message. Using the same argument, p1 can always find a blue node p2, which is close to the node that generates the first DBA_SET_B message. Therefore, there exists a connected path (v,p1,p2,…,pn), where pn is the node that generates the first DBA_SET_B message. Because v is not connected to the sink node s, it implies that s≠pn. However, in the DBA, only the sink node s can generate the first DBA_SET_B message, which constitutes a contradiction. And this completes the proof.Lemma 5.
After applying the refinement of a backbone, the remaining backbone nodes construct a backbone.Proof.
Here, we first prove that (S1), after applying Rule1, the backbone is still connected and can dominate all nodes in the network. Because no node is pruned from the backbone, it suffices to show that the backbone is connected. Assume that there exists a backbone node v such that the backbone is disconnected after applying Rule 1. Let v’s all neighboring nodes in the backbone be p1,p2,…,pk-1. When v is applied with Rule 1, there exists a node pi(1≤i≤k-1) such that pi is in v·Nr. When v changes to a small-range radio, it is clear that v can still connect to pi. However, because the backbone is disconnected when v changes to a small-range radio, it implies that there exists another node pj (1≤j≤k-1 and i≠j) that is not connected to pi. This implies that p1,p2,…,pk-1 cannot form a k-1-clique network, which constitutes a contradiction, and, thus, completes proof S1.
Next we prove that (S2), after applying Rule2, the backbone is still connected and can dominate all nodes in the network. Assume that there exists a backbone node v pruned from the backbone such that the backbone is disconnected or some node cannot be dominated after applying Rule 2. Let node u be the backbone node such that u∈v·Nr, v·Nr-{u}⊆u·Nr-{v}, and u is the most powerful node in {u,v}. If the backbone is disconnected when v is pruned, it implies that there exists a backbone node p∈v·Nr (p≠u and p≠v) but not in u·Nr. However, v·Nr-{u}⊆u·Nr-{v}, which constitutes a contradiction. In the other case, if some non-backbone node p cannot be dominated when v is pruned, it implies that p∈v·Nr but not in u·Nr. However, v·Nr-{u}⊆u·Nr-{v}, which constitutes another contradiction. This, thus, completes proof S2.According to S1 and S2, we, therefore, can conclude that after applying either Rule1 or Rule 2, the backbone nodes are connected and can dominate the nodes in the network.Theorem 6.
The DSBA constructs a backbone for the wireless sensor network.Proof.
By Lemma4, the DBA constructs a backbone for the dual-radio wireless sensor network. By Lemma 5, the remaining backbone nodes construct a backbone after applying the refinement of a backbone. Therefore, we conclude that the DSBA constructs a backbone for the wireless sensor network.


## 5. Performance Evaluation

Here, simulations were conducted to evaluate the performance of the DSBA. In the simulation, sensor nodes were randomly distributed in a square area with side length500. Every sensor was equipped with small-range and large-range radios whose ranges were 120 and 240, respectively. In addition, the initial energy power of sensors was set to 400 or randomly selected from the range [0,400]. The energy consumption of each sensor for being a backbone node for one working cycle was 1 (or 2) if a small-range radio (or large-range radio) was used. The STG [15] was compared with the DSBA in terms of the network lifetime, the average size of the constructed virtual backbones, the average residual energy of sensors, and the average number of virtual backbones. The STG [15] is a centralized algorithm used to find the virtual backbones in the network in which every sensor has only one radio range such that the network lifetime is maximized. To apply the STG to the dual-radio wireless sensor network, the STG that used a small-range radio (or large-range radio) to construct virtual backbones was adopted and denoted by STG_r (or STG_R). In the networks, the nodes in the virtual backbones constructed by STG_r (or STG_R) used a small-range radio (or large-range radio) to communicate with other backbone nodes; and the other nonbackbone nodes used a small-range radio to connect to the virtual backbones. The following empirical data were obtained by averaging the data of 10 simulations.


### 5.1. Network Lifetime

Figure4(a) shows the simulation results for the network lifetime versus the number of network nodes ranging from 50 to 500 when the initial energy of each sensor in the networks is 400. Clearly, when the number of network nodes increases, the network lifetime of the DSBA, STG_r, or STG_R increases. This is because more nodes in the DSBA, STG_r, or STG_R can be selected to be the backbone nodes, and the network lifetime is, thus, increased. Note that the STG_r has a longer network lifetime than that of the STG_R. This is because each backbone node in STG_R consumes double the energy consumption of each backbone node in the STG_r for one working cycle, and many nodes in the STG_R may deplete the energy such that it is hard to find a connected backbone, and, thus, the network lifetime in the STG_R is shorter than that in the STG_r. Also note that the DSBA has a longer network lifetime than that of the STG_r. This is because the DSBA can use a small-range or large-range radio to form the virtual backbones, and, thus, the network lifetime is prolonged. Figure 4(b) shows the simulation results for the network lifetime versus the number of network nodes ranging from 50 to 500 when the initial energy of each sensor in the networks is randomly chosen from the interval [0,400]. Note that the simulation results are similar to those in Figure 4(a). In addition, from the observations in Figures 4(a) and 4(b), the DSBA, STG_r, or STG_R in the networks with nodes having varying initial energy has lower network lifetimes than those in the networks with nodes having the same initial energy. This is because each node in the networks evaluated in Figure 4(b) has initial energy ranging from 0 to 400, which is less than or equal to the initial energy of each node in the networks evaluated in Figure 4(a).Figure 4
The network lifetime versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)Next, we evaluate the network lifetime when the energy consumption of backbone nodes using a large-range radio isβ times of that using a small-range radio, where β ranges from 1.25 to 2.75. Because the results of evaluating the network lifetime in the networks with nodes having varying initial energy are similar to those of the networks with nodes having the same initial energy, as shown in Figure 4, we show only the results when the nodes in the networks have the same initial energy. Figure 5 shows the simulation results for the network lifetime versus β when the initial energy of each sensor in the networks is 400, and the number of nodes in the networks is 500. It is clear that the DSBA has a longer network lifetime than that of the STG_r and STG_R, as demonstrated in Figure 4. In addition, the STG_R has a longer network lifetime than that of the STG_r when β≤1.5. This is because when β≤1.5, the STG_R can select more nodes than STG_r to be backbone nodes whose energy consumption for one working cycle is, at most, 1.5, which is close to the energy consumption for each backbone node in the STG_r. Furthermore, note that when β increases, the network lifetime in the DSBA (or STG_R) decreases. This is because more energy is consumed when backbone nodes use large-range radios. Also, note that there are almost no changes in the STG_r as β increases because no backbone nodes in the STG_r use a large-range radio.Figure 5
The network lifetime versusβ, where the backbone nodes using a large-range radio (or small-range radio) consume β (or 1) energy power for one working cycle; the network has 500 nodes and the initial energy of nodes in the networks is 400.


### 5.2. Size of Virtual Backbone

Figure6(a) (or Figure 6(b)) shows the simulation results concerning the average nodes of virtual backbones in the networks when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 6(b) are similar to those in Figure 6(a), we discuss only the results shown in Figure 6(a). In Figure 6(a), it is clear that the STG_R uses fewer backbone nodes than the DSBA and the STG_r because a large-range radio is used for each backbone node in the STG_R. Although the STG_R has the lowest average number of backbones nodes, the backbone nodes in the STG_R consume much energy power, and, thus, the STG_R often has a shorter network lifetime than the others, as shown in Figures 4 and 5. In addition, note that the more nodes in the networks, the bigger average size of virtual backbones in the DSBA, STG_r, or STG_R is required when the number of nodes is less than or equal to 300. This is because more nodes must be dominated, and, thus, more backbone nodes are required. Furthermore, when the number of nodes is greater than 300, the empirical data in the DSBA, STG_r, or STG_R are stable and have few differences. This is because the average number of backbone nodes in the DSBA, STG_r, or STG_R is enough to dominate all nodes in the networks.Figure 6
The average size of virtual backbones versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


### 5.3. Residual Energy

Figure7(a) (or Figure 7(b)) shows the simulation results in terms of the average residual energy of all nodes in the networks when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 7(b) are similar to those in Figure 7(a), we discuss only the results shown in Figure 7(a). In Figure 7(a), it is clear that the DSBA has lower average residual energy of all nodes in the networks than STG_r and STG_R. This is because more nodes are selected to be the backbone nodes whose energies are fully utilized to prolong the network lifetime. In addition, when the number of nodes in the networks increases, the average residual energy of all nodes in the network in the DSBA, STG_r, or STG_R appears to decrease. This is because more nodes can be selected to be backbone nodes in the DSBA, STG_r, or STG_R, and, thus, the network lifetime is prolonged, as shown in Figure 4.Figure 7
The average residual energy of all nodes in the networks versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


### 5.4. Number of Virtual Backbones

Figure8(a) (or Figure 8(b)) shows the simulation results in terms of the average number of virtual backbones when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 8(b) are similar to those in Figure 8(a), we discuss only the results shown in Figure 8(a). In Figure 8(a), it is clear that the DSBA has higher average number of virtual backbones than STG_r and STG_R. This is because the DSBA can use a small-range or large-range radio to form the virtual backbones, and thus, the average number of virtual backbones is increased. In addition, when the number of nodes in the networks increases, the average number of virtual backbones in the networks in the DSBA, STG_r, or STG_R appears to increase. This is because more nodes can be selected to be backbone nodes in the DSBA, STG_r, or STG_R, and, thus, the average number of virtual backbones is increased.Figure 8
The average number of virtual backbones versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


## 5.1. Network Lifetime

Figure4(a) shows the simulation results for the network lifetime versus the number of network nodes ranging from 50 to 500 when the initial energy of each sensor in the networks is 400. Clearly, when the number of network nodes increases, the network lifetime of the DSBA, STG_r, or STG_R increases. This is because more nodes in the DSBA, STG_r, or STG_R can be selected to be the backbone nodes, and the network lifetime is, thus, increased. Note that the STG_r has a longer network lifetime than that of the STG_R. This is because each backbone node in STG_R consumes double the energy consumption of each backbone node in the STG_r for one working cycle, and many nodes in the STG_R may deplete the energy such that it is hard to find a connected backbone, and, thus, the network lifetime in the STG_R is shorter than that in the STG_r. Also note that the DSBA has a longer network lifetime than that of the STG_r. This is because the DSBA can use a small-range or large-range radio to form the virtual backbones, and, thus, the network lifetime is prolonged. Figure 4(b) shows the simulation results for the network lifetime versus the number of network nodes ranging from 50 to 500 when the initial energy of each sensor in the networks is randomly chosen from the interval [0,400]. Note that the simulation results are similar to those in Figure 4(a). In addition, from the observations in Figures 4(a) and 4(b), the DSBA, STG_r, or STG_R in the networks with nodes having varying initial energy has lower network lifetimes than those in the networks with nodes having the same initial energy. This is because each node in the networks evaluated in Figure 4(b) has initial energy ranging from 0 to 400, which is less than or equal to the initial energy of each node in the networks evaluated in Figure 4(a).Figure 4
The network lifetime versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)Next, we evaluate the network lifetime when the energy consumption of backbone nodes using a large-range radio isβ times of that using a small-range radio, where β ranges from 1.25 to 2.75. Because the results of evaluating the network lifetime in the networks with nodes having varying initial energy are similar to those of the networks with nodes having the same initial energy, as shown in Figure 4, we show only the results when the nodes in the networks have the same initial energy. Figure 5 shows the simulation results for the network lifetime versus β when the initial energy of each sensor in the networks is 400, and the number of nodes in the networks is 500. It is clear that the DSBA has a longer network lifetime than that of the STG_r and STG_R, as demonstrated in Figure 4. In addition, the STG_R has a longer network lifetime than that of the STG_r when β≤1.5. This is because when β≤1.5, the STG_R can select more nodes than STG_r to be backbone nodes whose energy consumption for one working cycle is, at most, 1.5, which is close to the energy consumption for each backbone node in the STG_r. Furthermore, note that when β increases, the network lifetime in the DSBA (or STG_R) decreases. This is because more energy is consumed when backbone nodes use large-range radios. Also, note that there are almost no changes in the STG_r as β increases because no backbone nodes in the STG_r use a large-range radio.Figure 5
The network lifetime versusβ, where the backbone nodes using a large-range radio (or small-range radio) consume β (or 1) energy power for one working cycle; the network has 500 nodes and the initial energy of nodes in the networks is 400.


## 5.2. Size of Virtual Backbone

Figure6(a) (or Figure 6(b)) shows the simulation results concerning the average nodes of virtual backbones in the networks when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 6(b) are similar to those in Figure 6(a), we discuss only the results shown in Figure 6(a). In Figure 6(a), it is clear that the STG_R uses fewer backbone nodes than the DSBA and the STG_r because a large-range radio is used for each backbone node in the STG_R. Although the STG_R has the lowest average number of backbones nodes, the backbone nodes in the STG_R consume much energy power, and, thus, the STG_R often has a shorter network lifetime than the others, as shown in Figures 4 and 5. In addition, note that the more nodes in the networks, the bigger average size of virtual backbones in the DSBA, STG_r, or STG_R is required when the number of nodes is less than or equal to 300. This is because more nodes must be dominated, and, thus, more backbone nodes are required. Furthermore, when the number of nodes is greater than 300, the empirical data in the DSBA, STG_r, or STG_R are stable and have few differences. This is because the average number of backbone nodes in the DSBA, STG_r, or STG_R is enough to dominate all nodes in the networks.Figure 6
The average size of virtual backbones versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


## 5.3. Residual Energy

Figure7(a) (or Figure 7(b)) shows the simulation results in terms of the average residual energy of all nodes in the networks when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 7(b) are similar to those in Figure 7(a), we discuss only the results shown in Figure 7(a). In Figure 7(a), it is clear that the DSBA has lower average residual energy of all nodes in the networks than STG_r and STG_R. This is because more nodes are selected to be the backbone nodes whose energies are fully utilized to prolong the network lifetime. In addition, when the number of nodes in the networks increases, the average residual energy of all nodes in the network in the DSBA, STG_r, or STG_R appears to decrease. This is because more nodes can be selected to be backbone nodes in the DSBA, STG_r, or STG_R, and, thus, the network lifetime is prolonged, as shown in Figure 4.Figure 7
The average residual energy of all nodes in the networks versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


## 5.4. Number of Virtual Backbones

Figure8(a) (or Figure 8(b)) shows the simulation results in terms of the average number of virtual backbones when the initial energy of each sensor is 400 (or randomly chosen from the interval [0,400]). Because the empirical data in Figure 8(b) are similar to those in Figure 8(a), we discuss only the results shown in Figure 8(a). In Figure 8(a), it is clear that the DSBA has higher average number of virtual backbones than STG_r and STG_R. This is because the DSBA can use a small-range or large-range radio to form the virtual backbones, and thus, the average number of virtual backbones is increased. In addition, when the number of nodes in the networks increases, the average number of virtual backbones in the networks in the DSBA, STG_r, or STG_R appears to increase. This is because more nodes can be selected to be backbone nodes in the DSBA, STG_r, or STG_R, and, thus, the average number of virtual backbones is increased.Figure 8
The average number of virtual backbones versus the number of network nodes ranging from50 to 500. The initial energies of nodes in the networks are 400 in (a) and randomly chosen from the interval [0,400] in (b), respectively.
(a)
(b)


## 6. Conclusion

In this paper, while considering sensors each equipped with two radio interfaces, including small-range and large-range radios, a new problem, called the Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem, is introduced for finding virtual backbones to prolong the network lifetime. The Maximum Lifetime Backbone Scheduling for Dual-Radio Wireless Sensor Network problem proved to be NP-complete. Moreover, because centralized algorithms are not feasible in a wide range of wireless sensor networks, we propose a distributed algorithm, called the Dominating-Set-Based Algorithm (DSBA), to find a backbone when a new backbone is required for the network. In the DSBA, three steps are required. In the first step, the distributed dominating set algorithm (DDSA) is proposed to construct a dominating set for a given dual-radio wireless sensor network such that the nodes in the set have enough energy power to be the backbone nodes and can dominate all nodes in the network. In the second step, the distributed backbone algorithm (DBA) is proposed to establish a backbone according to the dominating set constructed by the DDSA. In the third step, the refinement for the generated backbone is proposed to minimize the size of the generated backbone or reduce the energy consumption of backbone nodes.In the simulations, we compared our proposed method with the STG [15] that is a centralized algorithm and is used to find the virtual backbones in the network with sensors each having a single radio. The STG that used a small-range radio (or large-range radio) to construct virtual backbones was adopted and denoted by STG_r (or STG_R). The performance was evaluated in terms of the network lifetime, the average size of the constructed virtual backbones, the average residual energy of sensors, and the average number of virtual backbones. Simulation results showed that our proposed method had a significantly longer network lifetime and the lower average residual energy of sensors than STG_r and STG_R.Planned future research will include research in routing in multiradio mobile wireless sensor networks. Other future research will study the routing in three-dimensional multiradio wireless sensor networks.



---

*Source: 475159-2015-10-19.xml*