Communications and Network, 2013, 5, 1-7
doi:10.4236/cn.2013.52B001 Published Online May 2013 (http://www.scirp.org/journal/cn)
Essential Topics on Constructing WCDS-based Virtual
Backbone in Wireless Sensor/Mesh Networks
Chie Dou, Yung-Han Hsiao
Department of Electrical Engineering, National Yunlin University of Science and Technology, 640 Touliu, Yunlin, Taiwan，Ch ina
Received 2013
ABSTRACT
Clustering or connected dominating set (CDS) both approaches can establish a virtual backbone (VB) in wireless sensor
networks (WSNs) or w ireless mesh networks (WMNs). Each cluster consisting of a cluster head ( CH) and its neighbor-
ing nodes can form a dominating set. After some bridging nodes were selected, cluster heads (CHs) connected through
these bridging nodes naturally formed a CDS. Although CDS provides obvious backbone architecture, however, the
number of cluster heads and bridging nodes may be too large, th is may cause the loss of advantages of virtual backbone.
When we effectively reduce their numbers, more effectively WCDS (Weakly Connected Dominating Set) can be fining
out. Some essential topics on constructing WCDS-based VB in WSN/WMN are discussed in this paper. From the point
of view of three different protocol layers, including network (NWK) layer, MAC layer, and physical (PHY) layer, we
explore their cross-layer research topics and design algorithms. For NWK layer, area-based WCDS algorithms and
routing strategies including via VB and not via VB are discussed. For MAC layer, a WCDS-based energy-efficient
MAC protocol is presented. For PHY layer, battery-aware alternative VB selections and sensor nodes with different
transmission ranges are addressed.
Keywords: Weakly C o n ne cted Dominati ng Set; Wirele ss Sensor/Mesh Ne t works; V i r tual Back bone; Cross-Layer De-
sign
1. Introduction
The main advantages of establishing virtual backbones in
WSN/WMN are as follows. First, it can reduce the heavy
exchange of routing control messages, to avoid the ex-
pansion of broadcasting storm problem. Because that all
routing control messages exchanged need only be carried
out on the virtual backbone. Second, it can solve the
problem of network scalability. A large number of nodes
in a sensor network may have a small but beautiful vir-
tual backbone. Ev en if the new node is added, it will not
be that great an impact on the virtual backbone. Third,
when the event occurs, all sensing nodes of this event
will send data to the CH, and the CH will filter the ex-
cess information to avoid repeated transmissions to re-
duce the amount of communication.
Since finding out CDS/WCDS is a NP-hard problem,
the identification of CDS/WCDS is not unique. How to
effectively identify WCDS, and a fair assessment of the
performance between the different WCDS algorithms, is
an important issue. Several WCDS algorithms, including
centralized and distributed two classes, were proposed in
[1]. In [2], WSN/WMN is first divided into several areas,
and then each area builds its own WCDS. So that each
area will have a smaller size of WCDS and has a smaller
Control&management´s overhead. The concept of CDS/
WCDS with bounded diameters has been proposed in [3].
The diameter of a CDS/WCDS is defined as the longest
path length that could be between any two CHs on the
VB. It has been shown in [3] that nodes transmission
ranges will affect the efficiency of WCDS algorithms in
terms of the resulting WCDS size and the value of ABPL
(Average Backbone Path Length). In [4-5], the concepts
of disjoint CDSs/WCDSs were proposed. That is, VB can
alternate between two or more disjoint CDSs/WCDSs to
avoid more serious power consumption of the CHs and
the bridging nodes on the VB. If we do not plan for re-
placement, it may cause the shortening of the life expec-
tancy of these nodes. In [4] the solution to the CDP
(Connected Domatic Partition) problem in graph theory
is used to identify the disjoint groups of CDSs/WCDSs.
In addition, the battery recharge recovery principle was
mentioned in [4] for periodically rotation between the
disjoint CDSs/WCDSs, to extend the life-time of VB
nodes. The authors of [5] proposed a power-aware dis-
joint CDSs concept that the VB nodes participating re-
placement their power level must be above a certain
threshold level. In [6,7] the authors proposed CDS/
WCDS localized formation algorithms, which have a

C. DOU,Y.-H. Hsiao
2
great difference to the centralized algorithms proposed in
[1,2,8,9]. Centralized algorithms require the coordinator
to use of the entire network topolog y to form the WCDS.
Localized formation algorithms use the interconnection
information between neighboring nodes to identify the
most suitable dominating node in local. These selected
dominating nodes are then used to form the CDS/WCDS.
In [8], the authors use the entire network topology to
establish the DAT (Data Aggregation Tree) for all nodes,
and then use it to form the WCDS. In [9] all nodes to-
gether are used for WCDS formation, and then cut-ver-
texes are identified from the WCDS created. Because
cut- vertex will cause leaf block and cut-vertex failure
will cause greater network failure. The concept of the
2-Connected virtual backbone was adopted in [9] to in-
crease the number of dominating nodes in the WCDS, to
eliminate the problem of the cut-vertex. In [10-12], CDS/
WCDS-based routing algorithms were proposed. It was
pointed out in [10] that not all messages must make use
of the CDS/WCDS according to the specified routing
cost constraints, especially short-distance transmission
path is even more so. The use of establishing routing
table for each node was proposed in [11]. The contents of
the routing table include its dominating node, its one-
hop neighbors, its neighbors’ distances to sink, and its
neighbors' remaining energies. Routing path is set ac-
cording to the routing information stored in the routing
tables. In [12], power-aware alternative path selection
was used in addition to the adoption of WCDS-based
shortest path routing. When the remaining power of
nodes on the primary path is insufficient, then shift to go
alternative path. In [13], CDS/WCDS algorithm using
UBG (Unit Ball Graphs) concept was proposed in the
three-dimensional environments, as opposed to the general
use of UDG (Unit Disk Graphs) in the two-dimensional
environments. In [14], UDG radius with different sizes
was proposed to find ing out CDS/WCDS. That is, nodes
with different transmission ranges were considered. In
[15], the authors proposed algorithm to finding out
load-balanced VB in WSNs.
In this paper, some essential topics on constructing
WCDS-based VB in WSN/WMN are addressed. From
the point of view of three different protocol layers, in-
cluding NWK (network) layer, MAC layer, and PHY
(physical) layer, we explore their cross-layer research
topics and algorithms. The rest of the paper is structured
as follows. Section 2 discusses the NWK layer issues of
WCDS-based algorithms, including the construction of
VB, routing strategies and self-configuration. In section 3, a
WCDS-based energy-efficient MAC protocol is presented.
Section 4 discusses the PHY layer issues related to
WCDS-based VB construction, including battery-aware
alternative VB selections, nodes with different transmis-
sion ranges. Section 5 concludes the contributions of the
paper.
2. NWK Layer Related Issues
2.1. WCDS Algorithms
In the WCDS algorithms proposed in [1], a piece is used
to specify a particular sub-configuration diagram; a white
piece refers to the piece that contains only one white
node; a black piece is a black node with all its adjacent
one-hop gray nodes. As shown in Figure 1, node 1, 2, 3
each forms a black piece, and each of the remaining
white nodes forms a white piece. In this paper, we
adapted two WCDS algorithms proposed in [1] to use by
the following subject matter discussed. The first algorithm
we called it Maximum-Neighbor (MN) algorithm. The
second algorithm we called it Two-Hop Maximum-
Neighbor (2H-M N) algorith m.
Maximum-Neighbor algorithm:
(Using Figure 1 as an example)
Step 1: Initially all nodes are colored in white.
Step 2: Find the node with the maximum number of
one-hop adjacent nodes; set this node to be the starting
point and be the first chosen CH labeled with 1 (colored
in black); and then marked all its one-hop neighboring
nodes in gray.
Step 3: Find the node from the remaining white nodes
with the maximum number of one-hop adjacent nodes,
and set it to be the next chosen CH, i.e., node 2 in Figure
1; then marked all its one-hop neighboring nodes in gray.
Step 4: Repeat step 3 to find the third CH; i.e., node 3.
(Now, three small black pieces including CH1, CH2
and CH3 are combined into one large black piece, and
there have two white pieces left. Among the remaining
white nodes, if there has more than one that has the same
maximum number of one-hop adjacent nodes, then
choose the one that can merge most pieces as the CH.)
Figure 1. A snapshot of pieces in WCDS algorithms.

C. DOU, Y.-H. Hsiao 3
Step 5: Choose node 4 as the CH, and stop the algo-
rithm.
Two-Hop Maximum-Neighbor (2H-MN) algorithm:
(Using Figure 2 as an example)
Step 1: Initially all nodes are colored in white.
Step 2: Randomly choose a node as the first CH, i.e.,
CH1, and labeled it with 1 (colored in black); and then
marked all its one-hop neighboring nodes in gray.
Step 3: Find the node from the CH1’s two-hop neighbor-
ing nodes which has the maximum number of one-hop
adjacent nodes, and set it to be the next chosen CH, i.e.,
node 2 in Figure 2; t hen marked all its one-hop neighboring
nodes in gray.
Step 4: For all chosen CHs, find the node from their
two-hop neighboring nodes which has the maximum
number of one-hop adjacent nodes, and set it to be the
next chosen CH; then marked all its on e-hop neigh boring
nodes in gray. So on and so forth until all white nodes
are marked either in black or gray.
In the example shown in Figure 2, the repetitions of
step 4 will produce node 3 and node 4 as new CHs, and
finally choose node 6 as the last CH and ending the
algorithm. However, node 6 in Figure 2 is a leaf node,
and it is trivial to select a leaf node to be a CH. So the
algorithm chooses node 5 as a CH and marked node 6 in
gray. This is an exceptional case.
This paper combines the area-based concept proposed
in [2] with the MN and 2H-MN algorithms to form the
following two area-based WCDS algorith ms: Area-based
MN algorithm and Area-based 2 H-MN algorithms.
Shown in Figures 3 and 4 are two examples used to ex-
plain how to construct WCDS-based VB by using these
two area-based WCDS algorithms, respectively. Both
examples use the same sensor nodes deployment. Fifty
nodes are randomly deployed in a 5 by 5 squared area.
All nodes have the same transmission radius 0.89.
Figure 2. A snapshot of the 2H-MN algorithm.
Figure 3. An example of the area-based MN algorithm.
Figure 4. An example of the area-based 2H-MN algorithm.
Area-ba sed MN algorithm:
(Using Figure 3 as an example)
Step 1: Select Roo t-CHs and partitions th e whole area
into sub-areas according to the number of selected Root-
CHs. The selected Root-CH s must own th e most one- hop
adjacent nodes. (Of course, the locations of the selected
Root-CHs may not suitable for partitioning the whole
areas. In addition, to draw boundaries between sub-areas
is a difficult problem that have to be manipulated by the
network organizer or people.) In Figure 3, nodes 3, 8, 44
are selected as the Root-CHs, and three sub-areas A1, A2,
and A3 are built accordingly.

C. DOU,Y.-H. Hsiao
4
Step 2: For each sub-area, use MN algorithm to con-
struct its respective WCDS. For example, nodes 2, 10, 23,
and 24 are selected as CHs in area A2, as shown in
Figure 3.
Step 3: On the border between any two adjacent areas,
border nodes are supplemented for linking two adjacent
WCDSs. For example, node 29 is selected as the border
node between A1 and A 2, as sho w n in Figure 3.
Area-based 2H-MN al g orit hm :
(Using Figure 4 as an example)
All steps are the same as Area-based MN algorithm,
except that 2H-MN algorithm is used to construct the
respective WCDS for each sub-area.
WCDS-based VBs constructed for both cases are
drawn by the bolded lines marked in red. The calculated
values of ABPL are 5.98 and 5.33 for the two VBs
shown in Figures 3 and 4, respectively. This indicates
that the VB shown in Figure 4 is more efficient than that
shown in Figure 3 in some sense.
2.2. WCDS-based VB Routing Strategies
It was pointed out in [10] that not all messages must
make use of the CDS/WCDS-based VB according to the
specified routing cost constraints, especially short dis-
tance transmission path is even more so. In this paper,
we suggest that the routing paths can be classified into
via virtual backbone and not via virtual backbone two
types, in order to increase the performance efficiency of
WCDS- based routing strategy. The routing paths that are
not going through VB are especially suitable for short
distance transmissions. If the shortest path length be-
tween a pair of communicating nodes is less than two or
three hops, then not via VB routing strategy should be
considered. On the contrary, if the path length is larger
than three hops then we suggest that the routing path
should go via VB. Shown in Figure 5 is an example of
WCDS-based VB, where nodes 1, 7, 8, 9 are CHs. Using
node 1 (CH1) as the center, its one-hop neighboring
nodes are 2, 3, 4, 5; and its two-hop neighboring nodes
are 6, 7, 8, 9. Node 10 is within its three-hop range. If we
assume that node 5 wants to communicate with node 10,
the best route selected is 5-1-3-9-10, which has to go
through the VB. But if we assume that node 2 wants to
communicate with node 10, the best route selected is
2-6-10, which needs not to go through the VB. The use
of establishing routing table for each node was proposed
in [11]. The contents of the routing table include: its
dominating node, its one-hop neighbors, its neighbors’
distances to sink, and its neighbors' remaining energies.
Routing path is set according to the routing information
stored in the routing tables. Here we suggest that the
routing table for each node should also include its two-
hop or even three-hop neighbors. So that node 2 knows
that node 10 is its two-hop neighbor and the shortest
routing path is 2-6-10 and should not go via VB.
2.3. Self-Configuration WCDS Algorithms
Because the virtual backbone network brings together
most of the traffic on the network, CHs and bridging
nodes on the backbone network, compared to the other
sensor nodes on the network, will inevitably consume
more power. The design of a WCDS algorithm with self-
configuration capability is important. The WCDS algo-
rithm should be able to start by its own, when the re-
maining power of the CH and its affiliated bridging
nodes below some thresholds. New CH and its affiliated
bridging nodes need to be dynamically selected to extend
the life cycle of wireless sensor/mesh networks. In [4-5],
the concepts of disjoint CDSs/WCDSs were proposed.
That is, the selected VB can alternate between two or
more CDSs/WCDSs to avoid more power consumption
of the CHs and the bridging nodes on the VB.
3. MAC Layer Related Issues
Very little literature considered in conjunction with the
WCDS algorithms and MAC protocols to do cross-layer
design. In this paper, we propose a new WCDS-based
energy-efficient MAC protocol to address this important
issue. The literature [16] proposed a Sensor-MAC (S-
MAC), which belongs to a common active period protocol.
S-MAC takes periodic wakeup, that is, each node ac-
cording to the schedule has a fixed length listen cycle
with a fixed length sleep cycle in turn. In the common
active cycle, S-MAC will adjust the schedule of the ad-
jacent nodes. The literature [17] proposed the Z-MAC,
which is a combination of TDMA and CSMA hybrid
MAC design. The literature [18] proposed a funneling
MAC, which is a funnel-shaped WSN that is divided into
two tiers, the outer tier using the pure- CSMA and the
inner tier using the combination of TDMA/CSMA. Lit-
ature [19] proposed a power aware clustered TDMA
Figure 5. An example of WCDS-based VB routing.

C. DOU, Y.-H. Hsiao 5
(PACT) MAC, which belongs to the scheduled protocol.
PACT determines the duty cycle of a node in accordance
with the node's traffic. PACT selects qualified CHs
based on the remaining battery energies of nodes, and
those CHs will become the backbone of the entire net-
work. PACT only allows CHs and gateway nodes to
transmit routing requests, thus reducing the flooding
messages. PACT classifies nodes into four classes: CH,
gateway, ordinary and LES (low energy state). PACT
adopts TDMA superframe structure. Sending node uses
controlled mini- slots to broadcast the addresses at the
receiving nodes of the following subsequent data slots.
WCDS-based Energy-Efficient MAC Protocols
The proposed WCDS-based energy-efficient MAC pro-
tocol combines the mechanisms used in the common
active period protocol (S-MAC) and in the scheduled
protocol (PACT). We use the example shown in Figure
5 to explain the concepts adopted in the proposed MAC
protocol. Since node 10 is a two-hop neighbor of node 2,
when node 2 wants to communicate with node 10, it
must send a request to CH1 in the active period of CH1.
After receiving the request, CH1 will allocate some time
interval to node 2 to do RTS-CTS-Data-ACK exchange
with node 6. This means that not only node 2 but also
node 6 has to wake up together with CH1. So, the pro-
posed WCDS-based MAC protocol requires that when
CH1 is wake up, all its two-hop neighboring nodes as well
as one- hop neighboring nodes must be wake up. Figure 6
shows the timing diagram of the proposed WCDS-based
MAC protocol. Using CH1 as an example, when it wakes
up, we assume that node 5 has message to be sent to node
3, and node 2 wants to communicate with node 6 simul-
taneously. Node 5 and node 2 both have to send their
requests to CH1 in the Rx. request interval (marked in
red color) using controlled mini-slot competition mecha-
nism. After a timer setting with duration tA (marked in
green color), if there has no requests sending to CH1 by
any one-hop neighbor ing nodes during this time interval,
CH1 will then broadcast the schedule (marked in yellow
color) for the following message exchange sequences
within this active period (marked in blue color) to all its
one-hop neighboring nodes. For instance, at what time
node 5 should send message to CH1 and at what time
CH1 will send message to node 3, and at what time node
2 may send message to node 6. This broadcasting sched-
ule is the competition result of the controlled mini-slot
mechanism. For any two-hop neighboring node of CH1,
if no requests from any CH1’s one-hop neighboring
nodes have been sent to it during the mini-slot competition
interval, it can go to sleep immediately after the request
competition interval. For any one-hop neighboring node
of CH1 that has no messages tosend to any other nodes,
Figure 6. The timing diagram of the proposed WCDS-based
MAC protocol.
after having received the broadcasted schedule for the
following data exchange period and found that it was not
in the schedule (i.e., no other nodes have messages to
send to it), it can then go to sleep immediately. In our
proposed MAC protocol, we assume that only messages
collected in the previous active/sleep cycle can be sent in
the current active cycle. For any one-hop neighboring
node of CH1 that has been scheduled in the current ac-
tive cycle, it can go to sleep immediately after it has
completed its data exchange task(s) during the data ex-
change period. The current active cycle of CH1 is ended
when all data exchange tasks in the schedule have been
completed. For all black nodes (CHs) shown in Figure 5,
i.e., nodes 1, 7, 8, 9, we will use TDMA to arrange who
should sleep and who should wake up among them. The
details about the associated TDMA protocol and the
overall performan ce of the proposed W CDS-based MAC
protocol will be presented in the results to come.
4. PHY Layer Related Issues
4.1. Battery-aware Alternative VB Selections
Using battery model can help us in understanding the
battery internal changes and cell characteristics, and to
assist us in designing the system simulation. Literature
[20] reviewed a variety of battery models using in wire-
less devices. The battery model we used is an analytical
battery model which was proposed by Rakhmatov and
Vrudhula in 2001. This model is based on the diffusion
characteristics of the ions in the electrolyte. Using a
given load current value, we can simulate the charging
status of the battery, and thus to predict the life cycle of
the battery. Such battery model using equations (1) and
(2) to calculate the battery power consumption.
(,, ),
ii i
IFtt



 (1)
22 22 ()
22
1
(,, )2i
mt mt
ii
m
ee
Ftt m
 
 
 












 (2)
Assuming the i-th battery discharge time is i

, t is the
starting time of the discharge, the load current is i
I
,
(0)

 is the diffusion constant, i

is the power con-
sumption of the i-th battery discharge. In (2), the power
consumption can be divided into two parts. The first part
ii
I


is the portion of the real battery charge consumed,
and the second part is the loss of the battery's discharge.
Equation (3) is used for computation of the remnant of

C. DOU,Y.-H. Hsiao
6
the discharge loss, wh en the recovery time is . t
22 22 ()t
()
22
1
()2 i
mt
mt t
ii
m
ee
tI m









 


 (3)
From (1)-(3), we can calculate the battery power con-
sumption and understand the characteristics of the bat-
tery recharge recovery.
It has been shown that battery performance can be
greatly improved by using pulsed discharge instead of
constant discharge. The battery recharge recovery princi-
ple was mentioned in [4] for periodically rotation be-
tween the disjoint CDSs/WCDSs, to extend the life-time
of virtual backbone nodes. By scheduling the CDS rota-
tion periodically, a simple mechanism that combines
load balancing and rest times for lifetime extension was
proposed in [4]. Besides load balancing, the rotation of
CDS breaks the continuous operation of high battery
discharge by introducing a rest time to allow the recharge
recovery effect in electrochemical batteries in extending
the battery lifetime. This allows a pulsed discharg e in the
battery to prevent from having a long continuous battery
discharge in any node of network. The operating CDS is
rotated among CDPs (Connected Domatic Partitions) so
that each CDS is given a rest period to recharge. For a
large-size CDP, the rest period is larger. It has been
shown in [4] that the longer the rest period, the greater
the battery recovery effect. Thus, the large sizes of CDP
enable substantial extension of the battery lifetime, re-
sulting in enhanced network lifetime.
In order to exploits the advantages of battery recharge
recovery, periodically rotation between disjoint CDSs/
WCDSs to extend the life-time of virtual backbone node s
is a topic worth exploring. There are many factors that
affect the rest period that a CH may be taken. In general,
different CHs may have different rest periods. This is a
cross-layer design issue that should take WCDS-based
energy-efficient MAC issues into considerations, such as
the TDMA scheduling among different CHs discussed
above. Even different WCDS-based routing strategies
will result in different settings of CHs’ rest periods. Us-
ing (1)-(3) to evaluate the performance of cross-layer
algorithms for battery-aware alternative VB selections is
a topic that worth further studying.
4.2. Sensor Nodes with Different Transmission
Ranges
In [14], UDG radius with different sizes was proposed to
finding out CDS/WCDS. That is, nodes with different
transmission ranges were considered. Figure 7 shows an
example of nodes with different sizes UDG radius in a
WMN. In Figure 7, the transmission ranges of black
nodes (CHs) are drawn in solid lines and that of white
nodes are drawn in dotted lines. Figure 8 shows an ex-
ample of nodes with different sizes UDG radius in a
WSN. It is well known that the nodes near the sink will
consume more power than that of the nodes located in
outer tiers. Hence, the transmission ranges of the nodes
in inner tiers should smaller than that of the nodes in
outer tiers. In addition, a sensor node with several dif-
ferent transmission power levels is in common practice.
If a network always adopts larger transmission power for
its nodes, then a smaller size WCDS can be obtained;
however, this will increase the interferences generated
simultaneously. This is because to enlarge node’s trans-
mission power is to shorten the routing path, that is, to
minimize the number of hops on the routing path. This
phenomenon has been demonstrated by the results pre-
sented in [14].
5. Conclusions
Essential topics on constructing WCDS-based VB in
WSN/WMN are addressed from different protocol layers.
We explore their cross-layer research topics and design
algorithms. In this paper, two area-based WCDS algorithms
Figure 7. Nodes with different sizes UDG radius in WMN.
Figure 8. Nodes with different sizes UDG radius in WSN.

C. DOU, Y.-H. Hsiao
7
are presented, and their constructed VBs are compared by
using ABPL. Via VB and not via VB two routing strate-
gies are considered. A novel WCDS-based energy-effi-
cient MAC protocol is proposed. Cross-layer design for
battery-aware alternative VB selections is discussed.
Comments on the issue of sensor nodes with different
transmission ranges are given.
6. Acknowledgements
This work was supported by National Science Council,
Taiwan, under the Grant NSC 100-2221-E-224-056.
REFERENCES
[1] Y. P. Chen and A. L. Liestman, “Approximating Mi
nimum Size Weakly Connected Dominating Sets for
Clustering Mobile Ad Hoc Networks,” Proceedings o
fthe 3rd ACM international symposium on Mobile ad
hoc networking & computing, New York, USA: AC
M, 2002, pp. 165-172.
[2] B. Han and W. Jia, “Clustering Wireless Ad Hoc Ne
tworks with Weakly Connected Dominating Set,” Jou
rnal of Parallel and Distributed Computing, Vol. 67,
2007, pp. 727 – 737. doi:10.1016/j.jpdc.2007.03.001
[3] D. Kim, Y. Wu, Y. Li, F. Zou and D. Z. Du, “Con
structing Minimum Connected Dominating Sets with
Bounded Diameters in Wireless Networks,” IEEE Tra
nsactions on Parallel and Distributed Systems, Vol.
20, No. 2, 2009, pp. 147-157.
[4] R. Misra and C. Mandal, “Rotation of CDS via Con-
nected Domatic Partition in Ad Hoc Sensor Networks,”
IEEE Transactions on Mobile Computing, Vol. 8, No. 4,
2009, pp. 488-499.
[5] T. Acharya, S. Chattopadhyay and R. Roy, “Multiple
Disjoint Power Aware Minimum Connected Dominating
Sets for Efficient Routing in Wireless Ad Hoc Network,”
Proceedings International Conference on Information
and Communication Technology, 2007, pp. 336-340.
[6] F. Dai and J. Wu, “An Extended Localized Algorithm for
Connected Dominating Set Formation in Ad Hoc Wire-
less Networks,” IEEE Transactions on Parallel and Dis-
tributed Systems, Vol. 15, No. 10, 2004, pp. 908-920.
doi:10.1109/TPDS.2004.48
[7] J. Wu, F. Dai and S. Yang, “Iterative Local Solutions for
Connected Dominating Sets in Ad Hoc Wireless Net-
works,” IEEE Transactions on Computers, Vol. 57, No. 5,
2008, pp. 702-715. doi:10.1109/TC.2008.25
[8] S. Zhang, J. Fan, J. Jia and J. Wang, “An Efficient Clus-
tering Algorithm in Wireless Sensor Networks Using
Cooperative Communication,” International Journal of
Distributed Sensor Network, Vol. 2012, pp. 1-11.
[9] F. Wang, M. T. Thai and D. Z. Du, “On the Construction
of 2-Connected Virtual Backbone in Wireless Networks,”
IEEE Transactions on Wireless Communications, Vol. 8,
No. 3, 2009, pp. 1230-1237.
doi:10.1109/TWC.2009.051053
[10] L. Ding, W. Wu, J. Wilson, H. Du, W. Lee and D. Z. Du,
“Efficient Algorithms for Topology Control Problem
with Routing Cost Constraints in Wireless Networks,”
IEEE Transactions on Parallel and Distributed Systems,
Vol. 22, No. 10, 2011, pp. 1601-1609.
doi :10.1109/TPDS.2011.30
[11] N. Chakchouk, B. Hamdaoui and M. Frikha, “WCDS-
nduced Routing for Data-Aggregation in Wireless Sensor
Networks,” Proceedings of the First International Con-
ference on Communications and Networking, 2009, pp.
1-6.
[12] M. H. Imtiaz, M. R. A. Sumi, S. M. Mostafa Al Mamun
and Md. N. Hassan, “A New Approach for Designing and
Analysis of Distributed Routing Algorithm and Protocols
of Wireless Ad Hoc Network,” International Journal of
Science and Advanced Technology, Vol. 1, No. 6, 2011,
pp. 10-17.
[13] D. Kim, Z. Zhang, X. Li, W. Wang, W. Wu and D. Z. Du,
“A Better Approximation Algorithm for Computing
Connected Dominating Sets in Unit Ball Graphs,” IEEE
Transactions on Mobile Computing, Vol. 9, No. 8, 2010,
pp. 1108-1118. doi:10.1109/TMC.2010.55
[14] M. T. Thai, F. Wang, D. Liu, S. Zhu and D. Z. Du,
“Connected Dominating Sets in Wireless Networks with
Different Transmission Ranges,” IEEE Transactions on
Mobile Computing, Vol. 6, No. 7, 2007, pp. 721-730.
doi:10.1109/TMC.2007.1034
[15] J. He, S. Ji, P. Fan, Y. Pan and Y. Li, “Constructing a
Load-Balanced Virtual Backbone in Wireless Sensor
Networks,” Proceedings of the International Conference
of the IEEE ICNC, Hawaii, Vol. 30, 2012, pp. 959-963.
[16] W. Ye, J. Heidemann, and D. Estrin, “Medium Access
Control With Coordinated Adaptive Sleeping for Wire-
less Sensor Networks,” IEEE/ACM Transactions on
Networking, Vol. 12, No. 3, 2004, pp. 493–506.
doi:10.1109/TNET.2004.828953
[17] Injong Rhee, A. Warrier, M. Aia, Jeongki Min, and M. L.
Sichitiu, “Z-MAC: A Hybrid MAC for Wireless Sensor
Networks,” IEEE/ACM Transactions on Networking, Vol.
16, No. 3, 2008, pp. 511-524.
doi:10.1109/TNET.2007.900704
[18] G.-S. Ahn, E. Miluzzo, S. G. Campbell, Andrew T. Hong
and F. Cuomo, “Funneling-MAC: A Localized,
Sink-Oriented MAC for Boosting Fidelity in Sensor
Networks,” Proceedings of the 4th ACM Conference on
Embedded Networked Sensor Systems (SenSys), Colorado,
USA: ACM, 2006, pp. 293–306.
[19] G. Pei and C. Chien, “Low Power TDMA in Large Wire-
less Sensor Networks,” Proceedings of the IEEE Military
Communications Conference (MILCOM’01), 2001, pp.
347-351.
[20] M. R. Jongerden and B. R. Haverkort, “Which Battery
Model to Use?” IET Software, Vol. 3, No. 6, 2009, pp.
445-457. doi:10.1049/iet-sen.2009.0001