An Energy-aware Hierarchical Architecture Design Scheme

doi:10.4236/ijcns.2008.11009

Paper Menu >>

Journal Menu >>

I. J. Communications, Network and System Sciences. 2008; 1: 1-103

Published Online February 2008 in SciRes (http://www.SRPublishing.org/journal/ijcns/).

An Energy-aware Hierarchical Architecture

Design Scheme

Linfeng YUAN1, Yang XU1, Xu DU2, Wenqing CHENG2

1 Wuhan Maritime Communication Research Institute, Wuhan, P.R.China

2 Huazhong University of Science and Technology, Wuhan, P.R.China

E-mail: yuanlf@163.com

Abstract

Compared with the flat architecture in the design of sensor networks, the hierarchical architecture gains much

attractive for the reason of scalability, management and energy efficiency. In order to distribute the energy evenly,

nodes act the cluster head in some orders. The existing approaches don’t pay a critical attention to the overhead during

the role rotations. And the duration of a round is a priori, which is very application-specific. An energy-aware

hierarchical architecture design scheme is put forward in this paper, namely, Adaptive Minimum Rotational Cost

(AMRC) cluster formation scheme. The decision of beginning a new round is made adaptively by the cluster head itself.

It combines the dynamic and static advantages in the clustering architecture. The simulation results demonstrate AMRC

outperforms some other clustering protocols in many aspects.

Keywords: Sensor Network, Hierarchical Architecture, Energy-Aware, Role Rotation

1. Introduction

Sensor network technology, based on sensing,

communication and computing research results, is a key

technology for the future. Many future applications will

rely on the embedded sensor network [1]. Sensor

networks have spurred much interest in the networking

research community recently.

Many questions must be dealt with in the design of

the sensor network. Efficient routing protocol is one of

those significant items. There are two main routing

topologies in the sensor network: flat and hierarchical.

The hierarchical (clustering) architecture gains much

attractive for the reason of scalability, management and

energy efficiency.

In the hierarchical architecture, each cluster includes

one cluster head (CH) and several common member

nodes (MNs). MNs send the data to the CH during the

communication and the CH send the gathered data to the

sink node or to the other CHs. Usually, the MNs in one

cluster will not communicate with each other directly,

and the MNs in different clusters communicate with each

other via the CHs in their clusters. So the CHs act the

roles of “router” in the hierarchical architecture, they

take more responsibility than the MNs and will consume

more energy than the MNs.

Based on the role assigned to sensor nodes in a

system, a hierarchical scheme can be grouped as a static

one or a dynamic one [2]. In a static system [3][4], the

CHs and their corresponding nodes will not change. So it

is hard to minimize the system’s energy consumption for

non-optimized distances between a CH and its MNs or

distribute energy cost among all the nodes. Dynamic

mechanisms [5][6][7] can provide better fairness while

remaining simplicity. In these dynamic schemes, clusters

are periodically regenerated, and nodes take

responsibility as the CHs in rotation. However, the

regeneration of clusters is energy consuming. Therefore,

it is desirable to design a hybrid scheme combining the

advantages of both static and dynamic scheme [2].

In order to distribute the energy evenly, nodes act the

CH in some orders. The existing approaches have solved

the problems in many aspects [6][8][9][10], but they

have two main disadvantages. First, they all don’t pay a

critical attention to the overhead during the role rotations.

If the energy cost for the role rotations has added up to a

certain degree, it will kill the benefits of hierarchical

architecture. Second, these hierarchical protocols decide

the beginning of a new round by some constant

experimental periodic time. If the round time is too short,

the rotational overhead will increase much. Or if the

round time is long enough, when the CH has depleted its

energy before the time of a new round, the system is

“dead” in fact. Therefore, the selection of the duration

time is closely dependent on the specific applications,

AN ENERGY-AWARE HIERARCHICAL ARCHITECTURE DESIGN SCHEME 63

which will greatly affect the scalability and management

of the system.

In this paper, we put forward an adaptive minimum

rotational cost (AMRC) energy efficient cluster

formation scheme to minimize the rotational times and

the rotational overhead. In AMRC, in order to minimize

the rotational times, the node with the biggest residual

energy will act the CH during the role rotations; in order

to minimize the rotational overhead, one round will last

for a period until the CH finds its residual energy has

dropped to a certain threshold which is only decided by

the CH’s own energy. Therefore, the decision of

beginning a new round is made adaptively by the CH. It

needs no information of the other nodes and needs no

global information. Each cluster’s rotation is

independent and the rotation in one cluster will not affect

the other clusters. So it combines both the dynamic

advantages and static advantages in the hierarchical

architecture. And, it is totally application-independent. It

can not only distribute energy consumption in the

network, but also reduce the overhead to prolong the

system’s lifetime.

The main contributions of this paper are as follows:

 Minimum rotational cost to reduce the overhead.

 Adaptive round time to meet any application’s

requirement.

 Combination of dynamic and static advantages

in the hierarchical architecture.

The rest of the paper is organized as follows. Section

2 discusses some related work. Section 3 describes the

AMRC scheme. Section 4 presents some experiments

and compares AMRC with other schemes. The last

section concludes this paper.

2. Related Work

In the flat routing architecture, each node typically

plays the same role and sensor nodes collaborate to

perform the sensing task. In hierarchical routing

architecture, higher-level nodes (CH) can be used to

process and send the information, while low-level nodes

(MN) can be used to perform the sensing in the

proximity of the target [11]. The hierarchical techniques

can greatly contribute to overall system scalability,

lifetime, and energy efficiency for load balancing and

efficient resource utilization [2][5][6][7][11].

The CH will cost more energy than its MNs. In order

to distribute energy consumption evenly among all the

nodes including CHs and MNs, role rotations will be

used to let all nodes take turn to act the CH [2][5][6][7].

The selection of CH can be weight-associated

[4][12][13][14] or weight-independent [6][7]. The latter

is simpler to implement and more robust in the presence

of network dynamics while the former can produce more

optimal clusters, which is more essential to the sensor

networks. In weight-associated selection methods, the

selection of CHs can be based on node ID [12][13],

nodal degree [14], residual energy [4][6] or a

combination of several parameters [5][12]. Since the

energy consumption is more sensitive to the sensor

network, the residual energy is often used as the criterion

for CH selection. They all take the ratio, the node’s

residual energy to the sum of all nodes’ residual energy,

as the selection principle. Every node will need to know

the sum either by a central controller or by computing on

its own, it is hard or costly to get the computation results.

In AMRC, each node is restricted within one cluster

forever, so the selection of CH is very easy to be decided.

Many times of role rotations will take place in

clustering formation, which will cost lots of energy too.

But none of the existing cluster-based routing schemes

have paid a critical attention to the overhead during the

role rotations. Some have tried to reduce the rotation

times by setting appropriate round period time. For

example, LEACH [6] sets the round time to enable each

node has enough energy to act CH once and act MN

several times throughout the simulation lifetime. It gives

no analysis about the number of role rotations and the

energy consumption for these rotations. Though the

network operation interval (Tno) is forced to be much

bigger than the clustering process interval (Tcp) in HEED

[5], the decision of its privilege, it will become the CH

again if it has more energy than the other neighboring

nodes. So this rotation is not necessary, and it will cost

some energy among all the nodes in this cluster. In

AMRC, each role rotation will happen in the same

cluster and it will not affect any other clusters, different

clusters have different number of role rotations and

different duration time.

3. AMRC Scheme

3.1. Connectivity Subnet

It will efficiently decrease the overhead incurred by

the interfaces among the clusters if each role rotation

will only happen in its own cluster and it will not affect

other clusters. So in AMRC, we restrict that the members

in each cluster will not change throughout the whole

transmission lifetime.

After the system runs in a steady state, the position of

the sink node is relatively fixed. In order to make fully

use of the position information in this protocol, the sink

node lets all related nodes know its coordinates before

the route discovery process. We need to establish a

Connectivity Subnet (or Connectivity Set, CS). The CS

is organized as follows. The sensing area is divided into

sub-areas according to the position information, which

must ensure the nodes in either sub-area can directly

communicate with any node in the neighboring sub-area.

64 L.F. YUAN ET AL.

GAF [15] has also put forward the concept of virtual

grid to try to ensure the direct communication, but in fact,

it cannot ensure the direct communication between the

diagonal neighboring sub-area, as shown in Figure 1.

Figure 1. Connectivity subnet

We will establish the CS as follows. In Figure 1, the

dashed line surrounds each sub-area and sixteen sub-

areas are involved here. If the communication radius of

each node is R and the square’s length of each sub-area

is r, in order to ensure direct communication for any

nodes in the neighboring sub-areas, R and r must meet

the following requirement:

222 )2()2( Rrr ≤+

That is

4/2Rr≤

In this case, whichever node is selected as the CH in

each cluster, it can directly communicate with the other

CHs in the neighboring sub-areas. The restriction

ensures that each role rotation can only take place in the

same cluster, and it will not affect the other clusters. It

also implies that different clusters can have different

number of role rotations and different interval time.

3.2. Decisive Rotational Threshold

Since the role rotation in one cluster has no

relationship with the other clusters, we first consider the

rotation process within one cluster. Suppose the ith node

is the CH in a cluster at some time. If the CH finds its

residual energy has decreased to some threshold, it will

tell all the nodes in this cluster to begin a new round.

Denote )(CHEias the energy when the node acted as

the CH and)(iEias its residual energy at present. In

AMRC, the threshold to begin a new round is)(CHEi

⋅

where

is a coefficient parameter of the threshold and it

is determined before the system works. That is to say, if

the energy of the CH has dropped to the

times of the

energy when it acted the CH in this round, it needs to

initiate a new round selection, as shown in the following

term,

)()(CHEiE ii ⋅≤

Since the energy )(CHEi is different for each node

and it is also different for each node in different round,

the time to begin a new round is changeable. It means

the role rotations will change adaptively.

3.3. Cluster Formation

There are two main issues in the design of the

hierarchical architecture: the number of clusters and the

cluster formation. We have discussed the first one in

above subsection, now we consider the second issue.

In AMRC, because the nodes in a specific cluster will

not change throughout the lifetime, the main problem in

the cluster formation is to select a new CH within this

cluster. If the old CH decides to begin a new round, it

will broadcast an energy-request message (ReqEn) using

a non-persistent carrier-sense multiple access (CSMA)

MAC protocol. Each MN transmits its residual energy

with an acknowledgement message (ACK) back to the

CH. The CH compares all the MNs’ residual energy and

informs the node with the highest one to become the new

CH in the coming round with an indication message

(IND). The new CH sets up a TDMA schedule and

transmits this schedule to the MNs in the cluster. After

all nodes in the cluster know the TDMA schedule, the

set-up phase is complete and the steady-state network

operation phase (data transmission) can begin. Figure 2

gives the AMRC flowchart.

Figure 2. AMRC flow chart

3.4. Some Discussions

The design of hierarchical architecture can gain many

benefits from the AMRC’s solutions.

First, the process of AMRC ensures that the node

with the highest residual energy will act the CH in the

local area during the role rotations. Second, it is a prior

for each node to know the parameters k (number of

clusters) and N (total number of nodes) in LEACH-like

protocols [5], while in AMRC, the decision to begin a

AN ENERGY-AWARE HIERARCHICAL ARCHITECTURE DESIGN SCHEME 65

new round is made adaptively by the CH own and it

needs no information of the other nodes or any global

information. Third, the working status is independent for

each cluster and each node in one cluster will act the CH

in some turns, so it combines the static and dynamic

advantages successfully. Fourth, the duration of each

round is determined adaptively, so it is not application-

specific. The parameters

can be set with a bit smaller

value when there are many packets should be transmitted

after establishing the source-destination pair, so as to

reduce the number of rotations. Or else, it can be set with

a bit larger value when only a few packets need to

deliver from the source node to the destination node, so

as to balance the energy consumption more efficiently.

From these benefits, AMRC can reduce the number of

rotations and minimize the rotational overhead

significantly.

4. Performance Simulation

In this section, we evaluate the performance of

AMRC protocol in the ns-2 simulator. Some parameters

are set as seen in Table 1.

Table 1. Parameters setting

Parameter Meaning Value

M*M

Eelec

Ldata

Ei(max)

sensing region

total number of nodes

radio propagation range

electronics energy

free space coefficient

multipath fading coefficient

data packet size

initial energy of each node

200m*200m

100

50m

50nJ/bit

10pJ/bit/m2

100bytes

1Joules

We compare AMRC with LEACH-like protocols and

evaluate the following performance metrics:

z The number of role rotations.

z Energy consumption in the transmission.

4.1. The Number of Role Rotations

We first examine the number of role rotations in

LEACH-like protocols. In LEACH-like protocols, there

are two steps in each round: the cluster process time Tcp

(set-up phase) and the network operation time Tno

(steady-state phase). Along with the differences of the

network operation time Tno, the number of role rotations

is also different. In our simulation, the network operation

time Tno are set as 20, 40, 60, 80 seconds, the number of

role rotations is calculated every 100 seconds and the

system lasts for 700 seconds. Figure 3 shows the

simulation results.

From the figure, we can find that at the time of 700

second, the number of role rotations is 24 when Tno

equals to 100 second, but it reaches 132 when Tno

equals to 20 second. It indicates that Tno has a great

influence to the number of role rotations in LEACH-like

protocols.

While in AMRC protocol, the network operation time

is not decided by manual operation and it is not

application-specific, so it cannot influence the number of

role rotations directly. It is the parameter of

that can

decide the number of role rotations. With the same

settings in LEACH-like protocol, we set

as 0.8, 0.85,

0.9, 0.95, and also examine the number of role rotations

when the system works in the time from 100 second to

700 second. Figure 4 shows the simulation results.

120

100200 300400 500600 700

Time (sec)

Rotation times (LEACH-like)

Tno=20

Tno=40

Tno=60

Tno=80

Tno=100

Figure 3. The number of role rotations in LEACH-like

protocol

From Figure 4, when we compare the number of role

rotations in the same times, we can find along with the

increasing number of

, the number of role rotations

gets larger. At the time of 700 second, the number of

role rotations is 4 when

equals to 0.8, and it is 22

when

equals to 0.95. This implies that the decisive

rotation threshold is more likely satisfied when

smaller.

100 200 300 400 500 600 700

Time (sec)

Rotation times (AMRC)

alpha=0.8

alpha=0.85

alpha=0.9

alpha=0.95

Figure 4. The number of role rotations in AMRC protocol

Comparing Figure 3 and Figure 4, we can also find

that at the same time, all the number of role rotations in

AMRC protocol is smaller than those in LEACH-like

protocols, even that of the worst curve in Figure 4

(

=0.95) is smaller than that of the best curve in Figure

3 (Tno =100). In fact,

equals to 0.95 means that the

CH will begin a new round when it detects that its

66 L.F. YUAN ET AL.

current energy has dropped 5%, but 5% is not necessary

for the CH to give up its CH’s privilege, and that CH can

continue to do more jobs at that time.

4.2. Energy Consumption in the Transmission

We set the network operation time as 20, 40, 60, 80

seconds in LEACH-like protocol and set

as 0.9 in

AMRC protocol, Figure 5 shows the energy

consumption of all the nodes during the transmission per

100 seconds.

100 200300 400500600 700 8009001000

Time (sec)

Energy consumption (J)

Tno=20s

Tno=40s

Tno=60s

Tno=80s

AMRC, alpha=0.9

Figure 5. Energy consumption

In LEACH-like protocols, the energy consumption

gets smaller when the network operation time is longer.

The differences of energy consumption come from the

different number of the role rotations. This implies that

from the view of the energy efficiency, the role rotations

cannot be neglected in the hierarchical architecture

system. In AMRC protocol with

equals to 0.9, the

energy consumption is smaller than those in LEACH-

like protocols at each corresponding time. It is for the

reason that decreasing the number of role rotations that

the energy consumption is reduced too. It can be

expected that when

gets smaller, the energy

consumption for all nodes will reduce further.

5. Conclusion

The LEACH-like hierarchical protocols suffered from

the overhead for the role rotations and they are

application-specific. In this paper, the AMRC energy

efficient scheme is put forward to minimize the number

of role rotations and the rotational overhead. Each

cluster can take its own rotation without affecting the

other clusters. And the adaptive round time makes it

widely used in any application scenarios.

6. Acknowledgement

This work is supported by the National Natural

Science Foundation of China (No.60572049) and the

Natural Science Foundation of Hubei Province,

P.R.China (No. 2005ABA264).

7. References

[1] John A. Stankovic, Tarek F. Abdelzaher, Chenyang Lu,

Lui Sha, Jennifer C. Hou, “Real-Time Communication

and Coordination in Embedded Sensor Networks”,

Proceedings of the IEEE, July 2003, Vol.91, No.7,

pp.1002-1022.

[2] Quanhong Wang, Hossam Hassanein, Glen Takahara.

“Stochastic Modeling of Distributed, Dynamic,

Randomized Clustering Protocols for Wireless Sensor

Networks”, Proceedings of the 2004 International

Conference on Parallel Processing Workshops, pp.1-8.

[3] C. F. Chiasserini, I. Chlamtac, P. Monti, and A. Nucci,

“Energy Efficient Design of Wireless Ad Hoc Networks”,

Proc. of Networking 2002, Lecture Notes in Computer

Science (LNCS), Italy, May 2002, No.2345, pp.387-398.

[4] S. Ghiasi, a. Srivastava, X. Yang, and M. Sarrafzadeh,

“Optimal Energy Aware Clustering in Sensor Networks”,

Sensors Magazine, 2002, Vol.19, No.2, pp.258-269.

[5] O. Younis, and S. Fahmy. “Distributed Clustering in Ad-

hoc Sensor Networks: A Hybrid, Energy-Efficient

Approach”, IEEE INFOCOM 2004, March 2004, Vol.1,

pp.629-640.

[6] W.B.Heinzelman, A.P.Chandrakasan, H.Balakrishnan.

“An Applicationspecific Protocol Architecture for

Wireless Microsensor Networks”, IEEE Transactions on

Wireless Communications, Oct. 2002, Vol.1, No.4,

pp.660-670.

[7] S. Bandyopadhyay and E. J. Coyle, “An energy efficient

hierarchical clustering algorithm for Wireless Sensor

Networks”, IEEE INFOCOM 2003, Vol.3, pp.1713-1723.

[8] Mark Perillo and Wendi Heinzelman, “DAPR: A

Protocol for Wireless Sensor Networks Utilizing an

Application-based Routing Cost”, IEEE WCNC 2004,

Vol.3, March 2004, pp.1540-1545.

[9] Yan Yu, Ramesh Govindan, Deborah Estrin.

“Geographical and Energy Aware Routing: a recursive

data dissemination protocol for wireless sensor networks”,

In Seventh Annual ACM/IEEE International Conference

on Mobile Computing and Networking (MobiCom’00),

August 2000.

[10] Fan Ye, Haiyun Luo, Jerry Cheng, et al. “A Two-tier

Data Dissemination Model for Large-scale Wireless

Sensor Networks”. In Proc. of the 8th Annual

International Conf. on Mobile Computing and

Networking (MobiCom’02), September 2002, pp.148-

159.

[11] Jamal N. Al-karaki, Ahmed E. Kamal, “Routing

techniques in wireless sensor networks: a survey”,

Wireless Communications, IEEE [see also IEEE Personal

Communications], vol: 11, issue: 6, Dec 2004, pp. 6-28.

[12] D. J. Baker, and A. Ephremides, “The architecture

organization of a mobile radio network via a distributed

algorithm”, IEEE Tran. On Communications (Legacy,

pre 1988), vol.29, issue: 11, Nov. 1981, pp.1694-1701.

[13] A. Ephremides, J.E.Wieselthier, and D.J. Baker, “A

AN ENERGY-AWARE HIERARCHICAL ARCHITECTURE DESIGN SCHEME 67

design concept for reliable mobile radio networks with

frequency hopping signaling”, Proceedings of IEEE,

vol.75, Issue: 1, Jan. 1987, pp. 56-73.

[14] M. Gerla, and J. T. C. Tsai, “Multi cluster, mobile,

multimedia radio network”, Wireless Networks, vol.1,

issue: 3, 1995, pp.255-265.

[15] Xu Y, Heidemann J, and Estrin D. “Geography-informed

Energy Conservation for Ad Hoc Routing”. In Proc. 7th

Annual International Conference on Mobile Computing

and Networking (MobiCOM 2001). July 2001, pp. 70-84.