INT J COMPUT COMMUN, ISSN 1841-9836
Vol.7 (2012), No. 4 (November), pp. 785-790

Clustering-Based Energy-Efficient Broadcast Tree in Wireless
Networks

J. Yu, H. Jiang, G. Wang, Q. Guo

Jiguo Yu, Honglu Jiang
School of Computer Science,
Qufu Normal University, Rizhao, 276826, P.R. China
E-mail: jiguoyu@sina.com; jianghonglu88@163.com

Guanghui Wang
School of Mathematics, Shandong University,
Jinan, 250100, P.R. China
E-mail: ghwang@sdu.edu.cn

Qiang Guo
Key Laboratory for Computer Networks of Shandong Province
Shandong Computer Science Center, Jinan, 250014, P.R. China
E-mail: guoq@keylab.net

Abstract: The characteristics of wireless networks present formidable challenges
to the study of broadcasting problem. A crucial issue in wireless networks is the
energy consumption, because of the nonlinear attenuation properties of radio signals.
Another crucial issue is the trade-off between reaching more nodes in a single hop
by using higher power versus reaching fewer nodes in that single hop by using lower
power. Given a wireless network with a specified source node that broadcasts messages
to all other nodes in the network, the minimum energy broadcast (MEB) problem is
NP-hard. In this paper, we propose a hybrid approach CBEEB(clustering-based
energy-efficient broadcast) for the MEB problem based on clustering. Theoretical
analysis indicates the efficiency and effectiveness of CBEEB. Simulation results show
that CBEEB has better performance compared with the existing heuristic approaches.
Keywords: Wireless Network, Energy-Efficient, Broadcast, Clustering

1 Introduction

Nodes in wireless networks are usually powered by batteries with limited capacity. There-
fore, energy efficiency is one of the most important design issues for wireless networks. The
energy consumption in transmission can be further reduced by using one or more intermediate
nodes instead of transmitting directly.

Broadcasting in wireless networks is different from that in wired networks, since all nodes
that are within the transmission range of the sender can receive the transmission without any
additional cost at the sender. This characteristic of wireless transmission is known as wireless
multicast advantage (WMA) [1]. This allows us to seek power optimal range assignment for the
energy-efficient broadcast problem. The minimum energy broadcast (MEB) problem is to find a
broadcast scheme with minimum energy consumption. The problem is also known as minimum
power broadcast (MPB) problem or minimum energy consumption broadcast subgraph (MECBS)
problem [2]. We use energy and power alternatively throughout this paper.

In this paper, we study the problem of broadcasting in wireless networks, where every node
is equipped with omni directional antennas. We propose a hybrid algorithm based on clustering
and prove its correctness. Theoretical analysis shows the effectiveness of our approach. We
compare it with the Broadcast Incremental Power (BIP) [1] algorithm and the best heuristic
approaches known in [2–4] by simulation.

Copyright c⃝ 2006-2012 by CCC Publications



786 J. Yu, H. Jiang, G. Wang, Q. Guo

2 Related work

Most previously developed models for broadcasting and multicasting problems were link-
based models, which does not properly reflect the properties of the all-wireless network environ-
ment. To solve the MPB problem, Wieselthier et al. first proposed the node-based approach
(BIP)which is more suitable for wireless environment than the link-based algorithms [1]. It was
subsequently shown in [5] that the BIP algorithm has an approximation ratio between 13/3 and
12. Das et al. gave an improvement procedure called r-shrink for MEB problem [6]. Cagalj et
al. [7] proposed another improvement procedure called embedded wireless multicast advantage
(EWMA). Kang et al. [8] generalized the EWMA into another heuristic called largest expanding
sweep search(LESS). In [9], an ant-colony based approach for the problem was presented. An
algorithm called CM using ant colony optimization approach was also presented in [3]. Further-
more, in [4] a simple simulated annealing algorithm with Metropolis chains of dynamic length
was presented. The algorithm is in fact a probabilistic version of the 1-shrink tree-improvement
algorithm described in [9]. Kang et al. [10] gave a perturbation based iterated local optimization
method that uses LESS as local search. In [11], Montemanni et al. presented a simulated anneal-
ing approach based on r-shrink. They used sweep procedure to improve the solution obtained
through simulated annealing. Al-Shihabi et al. [12] developed a hybrid approach combining
nested partitioning with LP relaxation and r-shrink method. In [13], Wolf et al. proposed an
evolutionary local search, which uses modified r-shrink as local search and random increase in
transmission power of some nodes as mutation operator. Recently, Wu et al. [14] developed a
generational genetic algorithm that uses permutation encoding to represent a broadcast scheme.
Hashemi et al. presented a simulated annealing algorithm using a special node selection mecha-
nism in its neighborhood structure [2]. In [15], Singh et al. proposed a hybrid approach to the
MEB problem combining a genetic algorithm with a local search heuristic, which is a modified
version of r-shrink improvement procedure [6].

3 Preliminaries and model

We consider static multi-hop ad hoc wireless networks with omni-directional transmitters,
and each node can adjust its transmitting power based on the distance to the receiving node. In
the most common power attenuation model, received signal power varies as d−α, where d is the
distance from the transmitter and α is an environment-dependent constant typically between
2 and 5. Therefore, the transmitter power required to support the direct communication is
proportional to dα.

To represent one wireless ad hoc network, let G = (V,E) be a directed graph, where V
denotes the set of nodes and E denotes the set of edges, and a special node s ∈ V that broadcasts
messages to all other nodes of v. The transmission energy required by a node in an arborescence
is determined by the longest edge among all edges of that arborescence. Leaf nodes do not relay
messages to any other node. Therefore, the transmission energy required by leaf nodes is zero.
The total transmission energy required for the broadcast can be computed by adding the energy
which is required by each node in that arborescence.

Definition 1. Min-Energy Broadcast Problem(MEB): Let G = (V,E) be a directed graph, find
a broadcast tree T ⊆ E rooted at s, with the minimum energy cost

∑
u∈V max(u,v)∈T d(u,v)

α,
where d(u,v) is the distance between the nodes u and v.



Clustering-Based Energy-Efficient Broadcast Tree in Wireless Networks 787

4 Hybrid approach–CBEEB

We now propose a hybrid approach CBEEB (clustering-based energy-efficient broadcast)
to MEB problem, which includes a clustering algorithm and the IBIP (improved BIP) algorithm.

A special node s broadcasts messages to all other nodes of V , and each node except s has
one unique identifier ID. For convenience, the notation and terminology used in the rest of this
paper are summarized in Table 1.

Definition 2. Priority of nodes: For two nodes i,j ∈ V\{s},i.prio > j.prio ⇔
d(i) > d(j), or d(i) = d(j) & &ID(i) > ID(j)

Table 1. Notation and Terminology
ID(i) The unique identifier of node i
i.prio The priority of node i
d(i) The degree of node i
N1i The set of one-hop neighbors of node i
i.ch The clusterhead elected by node i
i.type The type of node i, which is a clusterhead or a leaf node

The clustering algorithm is as follows:
Step 1. Each node except s collects the information of all its one-hop neighbors N1i . Such

information can be acquired by each node exchanging message including its ID and priority
to its one-hop neighbors. Then each node sorts the priority for all nodes within its one-hop
neighborhood.

Step 2. A node i decides to become a clusterhead if either one of the following criteria is
satisfied:

(1)Node i has the highest priority in its one-hop neighborhood.
(2) Node i is an one-hop neighbor of a node b. Furthermore, i has the highest priority in
the one-hop neighborhood of b.
Step 3. All the clusterheads are added to the set D. Assign to each clusterhead v ∈ D the

transmission range rv = maxv′∈N1i d(v,v′). Then, all the cluster members are the leaf nodes of
the broadcast tree.

The following Figure 1 gives an example of the clustering algorithm in a twenty-node network.

1

2
3

5

6

7

4

8

1
0

9

1
2

1
3
 1
4

1
1

1
5
1
6

1
7

1
8

1
9
2
0

1

2
3

5

6

7

4

8

1
0

9

1
2

1
3
 1
4

1
1

1
5
1
6

1
7

1
8

1
9
2
0

1

2

3

5

6

7

4

8

1
0

9

1
2

1
3
1
4

1
1

1
5
1
6

1
7

1
8

1
9
2
0

F
i
g
u
r
e
 
1
a
.
 
 
 
R
a
n
d
o
m
 
 
 
n
e
t
w
o
r
k
(
n
=
2
0
)
 F
i
g
u
r
e
 
1
b
.
 
R
e
d
 
n
o
d
e
s
 
a
r
e
 
c
l
u
s
t
e
r
h
e
a
d
s
 
e
l
e
c
t
e
d
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b
y
 
t
h
e
 
c
l
u
s
t
e
r
i
n
g
 
a
l
g
o
r
i
t
h
m

F
i
g
u
r
e
 
1
c
.
 
C
o
n
n
e
c
t
 
t
h
e
 
c
l
u
s
t
e
r
 
m
e
m
b
e
r
s
 
t
o
 
t
h
e
 
c
l
u
s
t
e
r
h
e
a
d

Figure 1. An example of clustering in a twenty-node network.

We give the IBIP(Improved BIP) algorithm.
The IBIP algorithm runs on the clusterhead set D. The cluster members elected by the

clustering algorithm consist of the leaf nodes of the broadcast tree.
Step 1. Initially, the tree consists of only the source node s. We begin by determining the

node that node s can reach with minimum expenditure of power.



788 J. Yu, H. Jiang, G. Wang, Q. Guo

Step 2. Determine which new clusterhead can be added to the tree at minimum additional
power in the set of D. If node i is already in the tree, and node j is not yet in the tree, (i,j ∈ D).

If Pi,j < rαi , then we add j to the tree, where Pi,j is the power required to support the
transmission between node i and j, and ri is the transmission range of node i which is
assigned in the clustering algorithm.
Otherwise let P ′i,j = Pi,j −max{rαi ,P(i)}, where P ′i,j represents the incremental power
associated with adding j to the set of nodes to which node i is already transmitting. The
pair {i,j} that causes the minimum value of P ′i,j is selected. Node i transmits at a power
level sufficient to reach node j. Thus, one new node is added to the tree.
Step 3. This process continues until all nodes are included in the tree. The total power

required to maintain this tree is the sum of the transmitted powers at each of the transmitting
nodes.

The following Figure2 gives an example of the IBIP algorithm.

s

1

2

3

4

9
6

7
5

8
s

1

2

3

4

9
6

7
5

8

S
t
e
p
1
:
 
s
 9
 S
t
e
p
2
:
s
 6
 
F
i
g
u
r
e
 
2
a
.
  
F
i
g
u
r
e
 
2
b
.

s

1

2

3

4

9
6

7
5

8
s

1

2

3

4

9
6

7
 5

8

S
t
e
p
3
:
 
6
 7
 F
i
n
a
l
 
t
r
e
e
 
F
i
g
u
r
e
 
2
c
.
  
F
i
g
u
r
e
 
2
d
.

Figure 2. An example of IBIP algorithm in a nine-clusterhead network with source node s.

5 Algorithm Analysis and Simulation

Theorem 3. The set of clusterheads elected by the clustering algorithm cover all network nodes.

Proof: Because each node either has the highest priority among its one-hop neighbors or has
a neighbor with the highest priority among one-hop neighbors of the node. By the definition
of the dominating set, a node either becomes a dominator itself or elects the neighbor with the
highest priority among one-hop neighbors of the node as a dominator. Thus the network has a
dominating set elected by the algorithm. Therefore, we conclude that the sets of clusterheads
elected by the clustering algorithm can cover all network nodes. 2

Theorem 4. The CBEEB algorithm has time complexity of O(M2), where M ≤ N
dmin+1

is the
number of clusterhead elected by the clustering algorithm and dmin is the smallest degree of nodes
in the network.

Proof: The clustering algorithm adopts a distributed clustering strategy. Thus, the time com-
plexity of the entire network equals that of a single node O(1). In the algorithm IBIP, it runs
on the set of clusterheads. Obviously, the number of the clusterheads is smaller than N

dmin+1
.

Moreover, the IBIP algorithm is based on the Prim’s algorithm. Thus the time complexity is
O(( N

dmin+1
)2). Therefore, the total time complexity of the CBEEB algorithm is O(1 +M2), that

is O(M2). 2

Theorem 5. The overhead complexity of control messages in the network of the CBEEB algo-
rithm is O(N + M3), where M ≤ N

dmin+1
is the number of clusterhead elected by the clustering

algorithm and dmin is the smallest degree of nodes in the network.



Clustering-Based Energy-Efficient Broadcast Tree in Wireless Networks 789

Proof: At the beginning of the clustering algorithm, each node broadcasts a message to collect
its information of its one-hop neighbors. Therefore, the overhead complexity of control messages
in the network is O(N). The IBIP runs on the set of clusterheads elected by the clustering
algorithm based on the Prim’s algorithm. Because we need to update the power P ′i,j at each
step of the algorithm, the message complexity is O(M3) when a straightforward implementation
is used [1]. Therefore, we can conclude that the overhead complexity of control messages in the
network of the CBEEB algorithm is O(N + M3). 2

Comparing with the time complexity of the BIP algorithm is O(N2), and the message com-
plexity is O(N3) [1]. Obviously, our algorithm CBEEB shows better effectiveness.

We now compare the performance of CBEEB algorithm with other six broadcast algorithms
BLiMST [1], BIP [1], CM [3], SA [4], ESA [2]and GA [15] by simulations. The simulations are
carried out in an ideal network generated over a 100 × 100m2 area without consideration for
packet lost. The number of network nodes changes from 25 to 250 with each increment of 25.

Fig 3a. The original network topology with 150
nodes

Figure 3b.The topology after running clustering
algorithm

Figure 3c.The topology after running IBIP Figure 4.Energy cost comparison among seven
algorithms

Figure 3 illustrates the backbone topology construction process using CBEEB. In Figure 4,
we compare the energy cost of our algorithm with other six algorithms. The simulation results
show that our algorithm makes further improvements on the energy cost compared with the
BliMST and BIP algorithm. CM, SA, ESA and GA algorithm can improve the energy cost
over the BIP algorithm. Moreover, we can see CBEEB performs better than the GA algorithm
especially when the number of nodes is large.



790 J. Yu, H. Jiang, G. Wang, Q. Guo

6 Conclusions

In this paper, we propose a hybrid approach for the MEB problem in wireless networks.
Compared with existing approaches, theoretical and experimental results show the superiority.
As further work, we will develop fully distributed algorithms for MEB problem.

Acknowledgments

This work was partially supported by the National Natural Science Foundation of China
for contract (11101243, 60373012), Natural Science Foundation of Shandong Province for con-
tract(ZR2009GM009, ZR2009AM013), STPU of Shandong Province for contract (J10LG09) and
TKP of Shandong Province for contract (2009GG10001014).

Bibliography

[1] J. E. Wieselthier, G. D. Nguyen, A. Ephremides, On the construction of energy efficient broadcast
and multicast trees in wireless networks, in: Proc. of INFOCOM 2000, 585-594, 2000.

[2] S. M. Hashemi, Mohsen Rezapour, Ahmad Moradi, Two new algorithms for the Min-power Broadcast
problem in static ad hoc networks, Applied Math. and Compu., Vol.190, pp. 1657-1668, 2007.

[3] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, A cluster-merge algorithm for solving
the minimum power broadcast problem in large scale wireless networks, in Proc. of the Milcom
conference, 13-16, 2003.

[4] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, The minimum power broadcast problem
in wireless networks: a simulated annealing approach, in Proc. of WCNC, 2057-2062, 2005.

[5] P. J. Wan, G. Calinescu, X. Y. Li, O. Frieder, Minimum-energy broadcast routing in static ad hoc
wireless networks, in Proc. of INFOCOM, 1162-1171, 2001.

[6] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshai, A. Gray, r-shrink: a heuristic for improving
minimum power broadcast trees in wireless networks, in Proc. of GLOBECOM 523-527, 2003.

[7] M. Cagalj, J. P. Hubaux, C. Enz, Minimum-energy broadcast in all-wireless networks: NP-
completeness and distribution issues, in Proc. of MobiCom’02, 172-182, 2002.

[8] I. Kang, R. Poovendran, Broadcast with heterogeneous node capability, in Proc. of GLOBECOM
4114-4119, 2004.

[9] A. K. Das, R. J. Marks, M. EI-Sharkawi, P. Arabshi, A. Gray, The minimum power broadcast problem
in wireless networks: an ant colony system approach, in Proc. of the IEEE CAS Workshop on Wireless
Communications and Networking, 5-6, 2002.

[10] I. Kang, R. Poovendran, Iterated local optimization for minimum energy broadcast, in: Proc. of
WiOpt, 332-341, 2005.

[11] R. Montemanni, L. M. Gambardella, A. K. Das, The minimum power broadcast in wireless networks:
a simulated annealing approach, in Proc. of WCNC, 2057-2062, 2005.

[12] S. Al-Shihabi, P. Merz, S. Wolf, Nested portioning for the minimum energy broadcast problem,in
Proc. of LION 2, LNCS 5313, 1-11, 2008.

[13] S. Wolf, P. Merz, Evolutionary local search for the minimum energy broadcast problem,in Proc. of
EvoCOP’08, LNCS 4972, 61-72, 2008.

[14] X. Wu, X. Wang, R. Liu, Solving minimum power broadcast problem in wireless ad hoc networks
using genetic algorithm,in Proc. of CNSR, 203-207, 2008.

[15] Alok Singh, Wilson Naik Bhukya, A hybrid genetic algorithm for the minimum energy broadcast
problem in wireless ad hoc networks, Applied Soft Computing, Vol.11, pp. 667-674, 2011.