

       
       

      !  "           ! # 

Multi-round topology construction in wireless sensor networks
Mihiro Sasaki a ,Takehiro Furuta b , Fumio Ishizaki c , Atsuo Suzuki a

Abstract
One of the important issues in wireless sensor networks is how to save power consumption
and extend the network lifetime. For this purpose, various network topology construction
algorithms have been studied. However, most of them are based on a myopic method, where
the topology construction is carried out round-by-round. To address this issue, we take theenergy dissipation of sensor nodes over multiple rounds into account, and we consider the
problem as a multi-dimensional knapsack problem, which enable us to find optimal network
topologies until at least one sensor node exhausts its battery power. We also propose asolution method to maximize the network lifetime. The computational experiments showthat the proposed approach provides efficient topology construction in the wireless sensor
network in terms of network lifetime compared to the cluster-based approach.

1

Introduction

Wireless sensor networks have been paid much attention due to recent rapid advances of wirelesstechnology combined with prospects of their future progress in scientific, medical, commercial,military area and so on. A wireless sensor network is formed by tens to thousands sensor nodes
randomly deployed in a target area, which is called a sensor field. Using wireless sensor networks,
we can easily collect information monitored by sensor nodes at the remote base station (BS)without checking each sensor node one by one. In addition, wireless sensor networks make itpossible to monitor events even in a field where people cannot get in.
Various network architectures and protocols have been studied so far. (e.g., see [6] andreferences therein). These network architectures can be classified into two classes. One is basedon a distributed network, where each sensor node makes decisions for itself with locally collected
information. The other is based on a centralized network, where the BS organizes the networkand controls all sensors’ activities.
Throughout this paper, we focus on a topology construction problem arise in the centralized
sensor networks. Main advantage of the centralized network is that the BS can collect global
information about whole network and sensor nodes, which implies the BS may find better
topology construction in order to save power consumption of sensor nodes. Moreover, sensor
nodes do not expend their power for topology construction under the centralized network because
the BS which has no power limitation is charged with doing all computing. From these reasons,the centralized network can be regarded as a good alternative if a good topology construction
can be established.
aDepartment of Information Systems and Mathematical Sciences, Nanzan University
Department of Management Science, Tokyo University of Sciencec
Department of Information and Telecommunication Engineering, Nanzan Universityb

1One of crucial challenges in the organization of sensor networks is energy efficiency, because
battery capacities of sensor nodes are severely limited and replacing the batteries is not practical.
Once all sensor nodes drain their batteries, the sensor network doesn’t work anymore. Since
sensor nodes expend a large amount of energy during the data transmission, the transmission
distance is a critical factor to save power consumption. The transmission distance is largely
depends on network topology. Therefore, an efficient network topology is required to save power
consumption.
Various topology construction in sensor networks have been studied in order to save power
consumption and extend the network lifetime [5, 6]. Among them, cluster-based network organization (see Figure 1(a)) is considered as the most favorable approach in terms of energy
efficiency. In this approach, sensor nodes are organized into clusters, and one sensor node ineach cluster is selected as cluster head (CH) to play a special role as transfer point. Moreover,each CH creates a schedule for the sensor nodes within the cluster, which allows the radio components of each non-CH-node to be turned off all times except during its transmit time. The
rotation of CHs is also important factor in the cluster-based sensor networks. Since the BS is
generally far away from the sensor field, CHs expend much amount of power for data transmission. Hence, CHs will die quickly if the same node continuously works as a CH. As a result, it
is required to introduce the rotation of CHs among sensor nodes to find efficient clustering or
topology construction in order not to drain the battery power of a single sensor.
One of the primal studies on cluster-based network organization is LEACH-C (Low Energy
Adaptive Clustering Hierarchy Centralized) [4], which is considered as a centralized version of
LEACH [3]. LEACH-C is more efficient than LEACH in terms of energy efficiency as the computational results reported in [4] show. Moreover, Furuta et al [1, 2] pointed out the drawbacksof LEACH-C and proposed a new clustering approach in which they overcame the drawbacks
and further extended the network lifetime.
Topology construction algorithms proposed in LEACH-C [4] and its improved method [1]are designed based on a myopic view. More precisely, they construct a single topology using theinformation about current battery level distribution, and repeat the topology construction forevery data transmission. The objective in each topology construction is to maximize the total
amount of battery power of sensors to be remained after the next data transmission.
Repeating a myopic method may fail to find a good solution after all. To address thisissue, we propose a multi-round topology construction method, where we take into accountcontinual changing battery level distribution as well as current distribution in order to findbetter topologies over multiple data transmissions at a time.
The remainder of this paper is organized as follows. In Section 2, we briefly describe ourmodel and explain a multi-round topology construction arises in the centralized wireless sensor
networks. In Section 3, we formulate the multi-round topology construction problem as a multi-

2

BS

BS

CH

Root
SensorSensorSensor field

Sensor field(a) Cluster-based sensor network(b) Tree-based sensor network

Figure 1: Wireless Sensor Networks
dimensional knapsack problem. We also address a problem to find topology construction to
maximize the network lifetime, and propose a solution method. In Section 4, we show thecomputational results. Finally, we give concluding remarks and mention future works in Section
5.

2Model description

We consider the following centralized sensor network. The BS is located far from the sensor
field. Each sensor node monitors events and transmits the data to the BS through the network
simultaneously. The data monitored by a sensor node is transmitted in a small packet of a
fixed size. If a sensor node receives data from several sensor nodes, data aggregation process
can be carried out by the sensor, then the resultant data is transmitted from the sensor. These
operations are continued until all sensor nodes die, i.e. drain their own batteries. Each sensor
node has a small battery, however, its capacity is severely limited and replacing the battery
is not possible. Since the data monitored by sensor nodes located closely each other are often
correlated or redundant, the BS does not require all data. Data aggregation process removes
such redundant data and reduces the size of data to be sent to the BS, which consequently saves
the power consumption. Here, we assume the perfect aggregation, where all packets received bya sensor node can be combined into one packet. Hence, each sensor node transmits the same
size of data. Sensor nodes expend their own battery power by data reception, data aggregationand data transmission.
The operation of wireless sensor network can be divided into rounds. Each round has twophases, which are a set up phase and a data transmission phase. In the set up phase, network
topology is constructed. In the data transmission phase, each sensor node monitors eventsand transmit the data using predetermined network topology. Rounds are repeated to monitor
3events continuously.
Once a sensor drains its battery, it never monitor events and transmit data. In addition, allsensor nodes drain their batteries, the sensor network doesn’t work anymore. As a measure for
evaluation of wireless sensor networks, we introduce a network lifetime, which is defined as thenumber of rounds repeated before all sensor nodes die. An energy efficient network topology
will be a strong tool for the centralized wireless sensor networks in terms of network lifetime.
In most of the cluster-based networks, data is transmitted from each sensor node to the BS
via a CH (see Figure 1(a)). Thus, the number of hops between each sensor and the BS is at
most two. In other words, every data can be transmitted to the BS on a two-level tree. Anotherpossibility is a multi-level tree, where more than two hops may be required to transmit data to
the BS (see Figure 1(b)). We call this sensor network as a tree-based sensor network.
In the tree-based sensor network, we assume that there is one special node which is connectedto the BS. We call this sensor node as a root. Data monitored by each sensor node should betransmitted to the root through the given tree, then the root finally transmits the data to the
BS. A forest composed of several trees can be a candidate. In this case, more than one sensor
node should be connected to the BS. However, from our preliminary test to evaluate energy
efficiency of both trees and forests, we confirm that trees are more efficient. This may be caused
by a large amount of power consumption during the data transmission from the roots to theremote BS. The perfect aggregation may also help trees be more efficient than forests. Thus,
we eliminate forests from the candidates.
As we see, more than two hops are required from some sensor nodes to the BS in the treebased sensor network. As the number of hops increases, power consumption caused by the data
reception and aggregation increases while that caused by data transmission decreases. However,since power consumption caused by data transmission is most critical, shorter transmission
distances would afford to save power consumption. From these observations, we consider atopology construction problem arise in a tree-based sensor network.
As mentioned in the previous section, wireless sensor networks have been applied in manydifferent settings. One of the common objectives among them is to extend the network lifetime,or perhaps maximize the number of rounds repeated while a certain percentage of sensor nodes isalive. With these objectives, various methods for topology construction have been addressed [5].
Most of them are based on a myopic algorithm, where one topology established by the current
battery level distribution. After the current optimal topology is found, battery level distribution
is updated in order to find an optimal topology for the next round. Repeating these operations
until certain criterion is satisfied, the network lifetime or the number of rounds can be obtained.
However, repeating myopic method does not necessarily provide optimal topologies throughout
the rounds. On the other hand, in the multi-round topology construction, we take into accountcontinual changing battery level distribution. We may expect to find better topologies over4

multiple rounds at a time.
Note that a tree should be a spanning tree of all sensor nodes to ensure network connectivity.
Once a tree to be used in a round is given, the transmission routes from each sensor node to the
BS are uniquely established. Hence, we can compute the power consumption of each sensor nodein the round. From these observations, we consider an approach, where we first prepare somecandidate trees which consists of a spanning tree and a root, then find out which candidate tree
should be used how many rounds in order to maximize the number of rounds. This approachenables to construct optimal topologies for multiple rounds at a time.

3

Formulation and solution method

In the following, we show a mathematical programming formulation of the multi-round topology
construction problem. First, we employ the following notations.
N:the index set of sensor nodes,T:the index set of candidate trees,bj :the battery level of sensor node j ∈ N ,cij : energy dissipation of sensor j ∈ N when tree i ∈ T is used.
We further introduce xi (i ∈ T ) as integer variables, which express the number of rounds using
candidate tree i ∈ T . Hence, the multi-round topology construction problem MRTC(N, T ) can
be formulated as the following multi-dimensional knapsack problem.
[MRTC(N, T )]maximize

X

xi

(1)

i∈T

s.t.

X

cij xi ≤ bj ,j ∈ N,(2)i∈Txi ∈ Z,i ∈ T.

The objective (1) is to maximize the number of rounds. Constraints (2) show that sensor nodej ∈ N cannot expend energy over the battery level bj .
We further propose a simple algorithm to maximize the network lifetime using MRTC. Notethat the optimal objective value of MRTC(N, T ) denotes the maximum number of rounds until
at least one sensor node among N drains its battery. Some wireless sensor network systems arerather interested in maximizing the network lifetime. In this case, the network lifetime can becomputed in the following manner. First, we solve MRTC(N, T ) with all sensor nodes set N
and associated T , After that, we reconstruct the sensor node set N by removing the dead sensor
nodes and remake candidate trees set T to be adjusted to the updated N . With the updated N
and T , we solve a MRTC(N, T ) again. Repeating these operations until all sensor nodes die, i.e.
N = ∅, we can obtain the network lifetime of the sensor network. We summarize the algorithm
to compute the network lifetime as follows.
5

[Algorithm for computing the network lifetime](Input)N:

the index set of all sensor nodes.

(Output)L:the total number of rounds.

T ∗:the set of used trees.

fi :the number of rounds using tree t∗i ∈ T ∗ .

Step 0:(Initialize) Set k := 1, Nk := N, L := 0 and T ∗ = ∅.

Step 1:(Tree set-up) Create the set of candidate trees Tk for sensor node set Nk . Set

M := |Tk |. Let tik (i = 1, · · · , M ) denote an element of Tk .
Step 2:(Solve) Find an optimal solution x of MRTC(Nk , Tk ) with the optimal value zk .

Step 3:(Update)(a) Set L := L + zk and i := 1.
(b) If xi > 0, then update T ∗ := T ∗ ∪ tik and set fi := xi . If i < M , then set i := i + 1.
Goto Step 3(b).
(c) Let D be the index set of the dead sensor nodes. Set k := k + 1, and Nk := Nk−1 \D.
If Nk is not empty, then go to Step 1.
Step 4:(Terminate) L is the network lifetime which is established by using tree ti ∈ T ∗ forfi rounds (i = 1, · · · , |T ∗ |).
This algorithm also can be regarded as a kind of myopic method, because it doesn’t necessarily take into account continual change of battery level distribution throughout the network
lifetime. However, as far as the authors know, topology construction considering multiple rounds
at a time has never addressed. It may be possible to provide better topologies compared to those
provided by the algorithm based on round-by-round optimization such as proposed in [1].

4Computational experiments

We made computational experiments to see how long our approach can extend the network
lifetime compared to that achieved by the cluster-based approach proposed in [1]. We adopted
the same physical constants and parameters as used in [1, 4]. That is, we assume that initialbattery level of each sensor node is 0.5 J, i.e. bi = 0.5 for all i ∈ N ; energy dissipation cij iscomputed under the conditions that the data amount transmitted by each sensor node is 4200
bits; the electronics energy is 50 nJ/bit; the amplifier energy is 10 pJ/bit/m2 if the transmission
distance is less than 87 m and 0.0013 pJ/bit/m4 otherwise; the energy dissipation for data
aggregation is set as 5 nJ/bit.
6

We used an optimization software Xpress-MP (2005B) to solve the problems. All experiments
were run on a PC with Intel Pentium 4 processor (2.53GHz) and 512MB RAM.
We prepared three test data sets (data1, · · · , data3), where 100 sensor nodes are randomly
deployed in a 100-meter-square. For convenience, we define the lower left of the square as (x = 0,
y = 0) and the upper right of the square as (x = 100, y = 100). We assume that the BS is
located at (x = 50, y = 175). These settings are also the same as those used in [1, 4].
We selected the minimum spanning tree (MST) and shortest path trees (SPT) as the candidates of the sensor network topology. They should be suitable to save power consumption
because they connect the sensor nodes so as to minimize distance measures. Hence, the set ofcandidate trees consists of a hundred SPT-based trees and a hundred MST-based trees. For
SPT-based trees, we select a sensor node as a root and find the shortest path form the root toall sensor nodes, where the distance is measured by the squared distance. For MST-based trees,
we first constructed the MST of the sensor node set, where the distance is also measured bysquared distance. Then, we created the hundred MST-based trees so that each has a different
root. Note that topology of all MST-based trees is the same and each MST-based candidate
tree has the different energy dissipation because the root is different.
The objective of the problem is to select the trees from the candidate trees and decide how
many rounds we should use the trees so as to maximize the number of rounds until at least
one sensor node dies. After that, at least one sensor node can not send data using any given
candidate trees. To continue the monitoring, we need to decide new candidate trees without thedead sensor nodes. To remove the dead senor nodes, we need to know whether a sensor node still
have enough battery power. In our experiments, we use two criteria for it. The first is whether
a sensor node has enough power to receive data from at least two sensor nodes and transmit
the aggregated data to the nearest sensor node. We use this criterion in the first experiment(ex1). The second is whether a sensor node has power to receive data from at least three sensor
nodes and transmit the aggregated data to the nearest sensor node. We use this criterion in thesecond experiment (ex2). Note that the power consumption of receiving and aggregating data
is dependent on only the amount of data.
Table 1 and Figure 2 show the comparisons of the number of rounds in the two experiments
mentioned above and “UFLP” using data1. The column labeled “UFLP” denotes the resultsof Furuta et al. [1] which is one of the cluster-based approach. The number of total rounds
in our proposed method is about twice of the number of rounds displayed in “UFLP”. The
ex1 provides better results compared to those achieved by the ex2. This can be caused by thedifferent criteria introduced to determine the dead sensor nodes. The criterion introduced in theex2 is more strict than that of the ex1. Regardless of the strict criterion, the number of deadsensor nodes is the same in both the ex1 and the ex2 at the beginning. However, as the rounds
are repeated, more sensor nodes can be regarded as dead in the ex2. After all, the ex1 which has

7rather soft criterion tends to provide better results. In our experiments using the other two data
sets, we observed similar results (see Tables 2 and 3, Figures 3 and 4). These results show that
our algorithm provides energy-efficient selection of the spanning trees throughout the network
lifetime. As a result, the network lifetime is drastically extended.
Table 1: The number of rounds (data1)#Sensors UFLP
ex1
ex2
99
902
961
961
90
922
967
967
70
933 1171 1171
50
939 1327 132130
944 1456 147710
952 1645 1605
0963 1857 1814

The number of sensor nodes alive

data1
100

UFLP :

90

ex1 :

80

ex2 :

70
60
50
40
30
20
10
0
0

200

400

600

800

1000

1200

1400

1600

1800

2000

The number of rounds

Figure 2: Relationship between the number of sensor nodes alive and the number of rounds :the case of data1

5

Conclusion

We consider a multi-round topology construction problem arises in the centralized wirelesssensor networks, and formulated the problem as a multidimensional knapsack problem. We
made computational experiments to compare our results with those provided by the previous
approach using the cluster-based network. From the computational experiments, we showedthat the number of rounds until at least one sensor node drains its battery is larger than thoseachieved in the previous study. Moreover, we showed that the network lifetime is also extended8

data2
UFLP :

100

ex1 :
ex2 :

The number of sensor nodes alive

90
80
70
60
50
40
30
20
10
0
0

200

400

600

800

1000

1200

1400

1600

1800

2000

The number of rounds

Figure 3: Relationship between the number of sensor nodes alive and the number of rounds :the case of data2

data3
UFLP :
ex1 :
ex2 :

100

The number of sensor nodes alive

90
80
70
60
50
40
30
20
10
0
0

200

400

600

800

1000

1200

1400

1600

1800

2000

The number of rounds

Figure 4: Relationship between the number of sensor nodes alive and the number of rounds :the case of data3

9

Table 2: The number of rounds (data2)
ex1
ex2# Sensors UFLP
99
902
969
969
919
969
969
90
70
933 1028 1035
50
939 1203 117530
944 1307 1281
10
954 1543 1573
0960 1811 1708
Table 3: The number of rounds (data3)
ex1
ex2# Sensors UFLP
99
916 1022 102290
933 1024 102570
950 1123 112050
957 1241 1240
30
961 1405 139110
969 1559 1570
0
981 1778 1730
about two times of the previous results. Our solution method is primitive, however it still
provides better results in a reasonable time.
In this paper, in order to extend the network lifetime of wireless sensor networks, we focus
on the topology construction which is energy efficient. However, although the delivery rate ofdata to the BS is an important factor in the topology construction of wireless sensor networks
as well as energy efficiency, we do not consider the delivery rate of data. As a future work,
we will develop a topology construction method considering both the delivery rate and energy
efficiency. Since the failure of data transmission randomly occurs in wireless networks, we mayneed the analysis of a mathematical model incorporating the stochastic characteristics of the
failure process.

Acknowledgment
This research was supported by Grant-in-Aid for Scientific Research ((A) (2)) (grant No. 16201035)
from Japan Society for the Promotion of Science and Nanzan University Pache Research Subsidy I-A-2 for the 2007 academic year. Mihiro Sasaki was supported by Grant-in-Aid for Young
Scientists (B) (grant No. 17710148) from Japan Society for the Promotion of Science. Fumio Ishizaki was supported by Nanzan University Pache Research Subsidy I-A-1 for the 2007
academic year.

10References[1] T. Furuta, M. Sasaki, F. Ishizaki, A. Suzuki and H. Miyazawa, “A new clustering algorithm using facility location theory for wireless sensor networks,” Technical Report of the
Nanzan Academic Society Mathematical Sciences and Information Engineering (NANZANTR-2006-04), submitted to European Journal of Operational Research, 2007.
[2] T. Furuta, H. Miyazawa, F. Ishizaki, M. Sasaki and A. Suzuki, “A heuristic method forclustering a large-scale sensor network,” to appear in Proceedings of Wireless Telecommunications Symposium 2007, 2007.
[3] W.R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient communication
protocol for wireless microsensor networks,” Proceedings of the 33rd Hawaii International
Conference on System Sciences, 2000.
[4] W.B. Heinzelman, A.P. Chandrakasan and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, Vol. 1, pp. 660-670, 2002.
[5] J.C. Hou, N. Li and I. Stojmenovic, “Topology construction and maintenance in wirelesssensor networks,” in Handbook of Sensor Networks: Algorithms and Architectures (I. Stojmenovic ed.), pp. 311-341, John Wiley & Sons, Inc., 2005.
[6] M. Kochhal, L. Schwiebert and S. Gupta, “Self-organizing of wireless sensor networks,”
in Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, andPeer-to-Peer Networks (J. Wu, ed.), pp. 369-392, Auerbach Publications, 2006.

11