MEBRS: Energy Balancing Route Scheduling in Centralized Wireless Sensor Networks

Yawen Dai1, Quan Wang2, Xiaoqiang Li1

1School of Science, Wuhan University of Technology, Wuhan, China, 2College of Automation, Chongqing University of Posts and Telecommunications, Chongqing, China

daiyaweny@163.com

Abstract Abstract-Energy efficiency has been known as the most

important problem in wireless sensor networks. However, different applications need different energy efficiency protocols. A centralized wireless sensor network with mesh topology can enable the reliable monitoring of a variety of environments, such as plant monitoring, city traffic monitoring. In this paper, we propose the MEBRSS (Mesh Network Energy Balancing Route Scheduling) algorithm for the network of this type. This algorithm considers both the traffic and the remaining power of all nodes. In addition, the shortest path is selected after such considerations to meet the delay requirement of many applications. The algorithm computes an energy consumption balancing factor for each node, which can represent a balance of the traffic and the remaining energy of each node. We use several matrices to describe the relative information to make the decision, which makes the algorithm simple and efficient. The simulation shows good result for its applicability. 1. Introduction

Wireless sensor networks (WSNs) are technologies that grow rapidly with new applications being developed each day. A sensor network is composed of hundreds or thousands of tiny sensor nodes which are deployed in a specific region. Each node typically consists of one or more sensors, an embedded processor, and low-power radios and an energy source, usually a battery. Different sensors cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion, or pollutants. The sensor nodes collect data from their environment and then send them to one or more main nodes which are called sinks. The sink node collects data from other sensor nodes and processes them [1].

WSN has a wide range of applications. Some of the application areas are environmental monitoring, traffic management, health care, manufacturing, disaster management, object tracking, and fire detection. However, design and deployment of sensor networks are application dependent. In natural disaster recovery，for example, WSN are required to possess the rapid deployment, self-organization, and fault tolerance capabilities. And sensor network topologies are frequently changing after deployment in order to avoid deliberate jamming. But in applications such as plant monitoring system and city traffic system, real-time, reliability, and certainty take priority. With respect to points mentioned above, wireless sensor network technology designed for one kind of applications could be different from that designed for another kind of applications. The protocols

of wireless sensor networks should be designed based on their unique and different characteristics. In this paper, we study centralized wireless sensor networks with mesh topology that require real-time and certainty requirements [2].

MSNs have different limitations such as computational power, storage capacity, energy source, etc. Of course, the main constraint is energy. Energy source which is dedicated to sensor nodes is limited and, in most applications, is not rechargeable. Energy determines the network lifetime. Communication is the most important factor in node energy consumption. In WSN, all sensor nodes are responsible to forward their local and transient data toward the sink node. Therefore, if a node is frequently used by the other nodes for data forwarding, it will lose its energy and will die sooner than the other nodes. The dead nodes lead to wireless sensor network partitioning. When a network is partitioned, its energy consumption will be increased seriously. Therefore, balance in energy consumption of sensor nodes has direct impact on the network energy consumption. By using balancing routing protocols which provide balance in energy consumption, the network lifetime will be increased.

Many routing algorithms have been designed for wireless sensor networks including energy aware protocols. In [3], EBAT algorithm is proposed. It is a centralized and distributed algorithm. The base station calculates a proportion for each sensor node in the network. According to the proportion value, each sensor node uses the distributed algorithm to decide its data packet delivery path every time. But it assumes that all nodes can access the base station directly, which makes the monitoring range limited. LEACH [4] algorithm first proposes the clustering-based protocol which does a tremendous contribution on energy efficiency. But it has some drawbacks that the cluster head may not be well distributed and the number of nodes in each cluster is distributed unequally. Considering the disadvantages of LEACH, BEBC [5] proposed an improved way. But it has too many constraints on the location of base station and clusters.

Lately centralized MSN has gained much attraction. Two of the industrial automation wireless network standards, ISA100 [11] and WirelessHART [12], have chosen this architecture. The reason is obvious in that the more demanding industrial environment requires a more robust, reliable, and secure real-time network. While centralized MSN gives up lots of flexibilities that come with non-centralized MSN, it provides additional information for the centralized manager to better manage the MSN. In other

978-1-4244-4952-1/09/$25.00 ©2009 IEEE 270 1st Int'l Symposium on Quality Electronic Design-Asia

words, we could have a more robust, reliable, secure, and long lasting MSN.

To the best of our knowledge, there is no well-known algorithm considering the centralized wireless sensor network with mesh topology, not to mention the overall energy balancing routing protocol of networks with these features. In this paper, we propose an overall energy balancing routing algorithm. The algorithm can make sure that the nodes with much traffic and low energy take less transmission tasks. It is clear that this kind of sensor network is not suitable for all WSNs applications. However, it is a good choice in some specific applications such as traffic management, and plant monitoring system.

The reminder of this paper is organized as follows. In Section II, centralized wireless sensor network with mesh topology is discussed. In Section III, the MEBRS algorithm is proposed. In Section IV, by using computer simulation, we demonstrate the feasibility of the mentioned routing algorithms. Finally we conclude the paper in section V.

2. The network model In this paper, the network model we discuss is centralized

wireless sensor network with mesh topology. It is a centralized control network and consists of sensor nodes, a sink node or gateway and a system manager.

Sensor nodes are responsible to sense and collect data from the environment, then transmit the data to the sink node using the routing path allocated by the system manager. Each node can route data to or from other nodes in its communication range. Periodicity, each node sends the information about itself to the system manager such as remaining power and communication cycle. The nodes also receive configuration information from the system manager (e.g. routing path, communication timeslot). Each node knows the time slot of itself, and then the node will keep the transceiver off until its time slot. In its time slot, the node transmits the sensing data to the next hop according to the provisioned path.

The sink node transmits the data got from sensor nodes to the system manager. And it doesn’t have energy constraint.

The system manager is the core of the network. It has plenty of resources like energy, flash, memory etc. It performs policy-based control of the network runtime configuration, monitors and reports on communication configuration, performance, and operational status, and provides time-related services. It will update the configuration information when it considers there is need to do this. It can be located in the gateway or on a host.

When a sensor node intends to join the network, it will first listen to the network. After a short period of time, it will receive packet from one or more devices, indicating that they can communicate with it. The node selects one of them to send its information to the system manager. After the authentication, the system manager decides whether the device can join the network. If so, the system manager stores the link information in the link table, which contains all the links in the network. Then the system manager uses the algorithm proposed in this paper to obtain an energy balancing routing path and notify the device. The device

communicates with the system manager through the allocated path. The system manager also arranges other communication resources (timeslot, channel etc.) for the device using other algorithms.

As the system manager allocates the routing path for the sensor node, the sensor node can spend its limited energy on collecting and routing the data. With the timeslot and the channel resources, the device can communicate in a certain timeslot, using a certain channel by a certain path, which are all allocated by the system manager. The sensor nodes usually sleep, and they just wake up to communicate with other devices on the configured time slot. This saves a lot of energy. This way, the network can meet the strict requirements of the real-time, reliability, and certainty in the industrial field. The network model we described here is adopted by both ISA100 and WirelessHART, which means that our algorithms proposed in this paper could be applied to both an ISA100 MSN and a WirelessHART MSN. This kind of network can also be used in other environment where it is appropriate.

3. The MEBRS algorithm As all the devices route data through the paths arranged

by system manager, the strategy in System Manager is particularly important. This paper proposes a mesh network energy balancing routing algorithm (MEBRS), which does not only take into account balancing energy consumption but also minimizing data transmission hops. The MEBRS algorithm considers both the traffic and the remaining power on the device. Firstly, the system manager calculates the device energy consumption balancing factor. Then, by using the balancing factor as the weighting factor, the system manager computes the “shortest” path using the Shortest Path Routing algorithm.

First of all, it is assumed that the network system meets the following conditions:

(1) Each node in the network transmits data using full power;

(2) The energy used in one data transmission for each node is equal;

(3) The system manager allocates the same time amount to the device for each data communication;

(4) The battery capacity of each node is equal, and the remaining power is expressed by a percentage the full power;

MEBRS works as follows. The system manager maintains the status of the current network, including the transmission usage of each node in the network. When a node requires sending data periodically to the host, being it a newly joined node or an existing node with new data, the system manager allocates a new path for the data. MEBRS is the algorithm that produces such a new path. Once the path is allocated, the path information is sent to each node on the path and the new data could then start transmission. This procedure is repeated from the creation of the MSN until all data sources have their respective paths to the host.

The steps that the system manager calculates an energy balancing routing path are described in the following. Stages A and B are performed beforehand and maintained in the system manager. Stage C is performed upon request to allocate a new data path.

A. Preparation for the routing algorithm The system manager stores all the information in the

network, including the links, routing paths, device communication cycle, device remaining power etc. In order to describe the network and related information, we use the system link matrix, the path matrix, the time matrix and the remaining power matrix.

These matrices are formed in the following way.

The system link matrix N LC stores all the links in the

network. The system manager gets the information from the sensor devices. N is the number of nodes and L is the number of links in the network. A column of the matrix is allocated to each link and a row to each node. An entry at ( , )i j is 1 if node i is an endpoint of link j and 0,

otherwise. The path matrix L GP stores all the paths in the network.

Once the system manager allocates a routing path for a device, it updates its path matrix simultaneously. L is still the number of links and G is the number of paths in the network,

the entry at ( , )i j is 1 if path j uses link i ,0 if not.

The time matrix G G represents the number of

communications each device does per second. As we assume that the system manager allocates the same time period to the device for each communication, the number indicates the time that each device uses. Each node has a routing path and the communication period. The system manager derives the number of the communication from the communication period. For example, if the communication period is 1s, then the number of the communication is 1; if 30s, then it is 1/30. The time matrix is a diagonal matrix, and the entry at ( , )i i

represents the number of the communication path i has in one second. The bigger the number, the more frequently communication happens on that device.

The remaining power matrix NPow indicates the

remaining power of each device. The system manager also gets it from the device. It is a single column matrix and the entry at (i) represents the remaining power of the device i. All of the matrices must be put in the same order.

B. Calculate the energy consumption balancing factor

In this phase, the system manager uses the matrices mentioned in the former phase to calculate the device energy consumption balancing factor, which is used as a weighting factor in the next phase. The steps that the system manager calculates the device energy consumption balancing factor are as follows:

(1) We multiply the path matrix L GP with the time

matrix G G , the resulting matrix T becomes one that

indicates the time that each link spends on each path per second.

GGGLPT (1)

(2) Adding the elements in each row of T gives us the time that each link uses per second. The expression is:

G

jijL TTl

1 (2)

(3) We multiply N LC with LTl , the resulting matrix

NDp represents the device energy consumption factor. It is

a single column matrix, and each element represents the factor of one device.

LLNN TlCDp (3) We use the device energy consumption factor matrix

NDp and the remaining power matrix NPow to obtain the

device energy consumption balancing factor matrix

NPb which is our main purpose.

i

iN Pow

DpPb

(4) Now, we’ve obtained the device energy consumption

balancing factor. In the next phase, we will use the factor as the weighting factor in the shortest path routing algorithm.

C. Compute the path and use it Next we shall use NPb as the weight on each node for

the path search. A path’s length value is the summation of the

weighted nodes on the path. From the derivation of NDp , we

know the bigger it is, the faster its energy is to be consumed, and so the less it should be reused for any new path.

Similarly, the smaller NPow is, the less its energy should be

consumed, so the less it should be reused for any new path. This is the rationale behind Equation (4).

Taking the energy consumption balancing factor as the weighting factor, the system manager use the shortest path routing algorithm to find the next hop with the minimum factor sum from the source node. It will do this until it reaches the destination node. The shortest path with the optimal energy balance is formed. Then the system manager will update its path matrix and notice the node to route data using the obtained path. Fig.1 shows the procedure of the MEBRS algorithm.

Figure 1: The procedure of the MEBRS algorithm

4. The Simulation Results We tested the MEBRS algorithm with Matlab as the

simulation environment. We use the network illustrated in Fig.2. In the network, there are 7 nodes marked with A to G, where A is the gateway responsible for collecting the information from the nodes and sending them to the system manager which is also in the gateway. There are 11 links marked with a to g.

Figure 2: the example network in the simulation

We assume the communication cycle and the remaining power of each node are as shown in Table 1.

If there is a new device H intending to join the network, it will first listen to the network to find out which nodes can communicate with it. Then the node uses one of them to send its information to the system manager. After the authentication, the system manager decides whether the device can join the network. Here we assume the node can join the network and it can form links between E, F, and G. Then, the system manager uses the algorithm proposed in this paper to obtain an energy balancing routing path and notify the device. The simulation steps are as follows.

A. Preparation for the routing algorithm The original matrices do not include node H. With H, the

new system link matrix, path matrix, time matrix, and power matrix become:

11100000000000

10010100000000

01001110000000

00100011110000

00000000101000

00011001000110

00000000011101

00000000000011

LNC

0000000

0000000

0000000

1000000

0100000

0000000

0000000

0010000

0000000

0001000

0000100

0000000

1110010

0001101

GLP

8.0

1

5.0

5.0

2

1

1

GG

B. Calculate the energy consumption balancing

factor Use the matrices derived above, we obtain T:

0000000

0000000

0000000

8.0000000

0100000

0000000

0000000

005.00000

0000000

0005.0000

0000200

0000000

8.015.00010

0005.0201

GGGLPT

Table 1: Remaining power of each node Node A B C D E F G

Communication Cycle（s）

1 1 0.5 2 1 1.25

Remaining Power

NPow 1 0.5 0.7 0.4 0.2 0.1 0.5

And then we get LTl :

0

0

0

8.0

0.1

0

0

5.0

0

5.0

0.2

0

3.3

5.3

1

Gj

jijL TTs

The energy consumption factor and the device energy consumption balancing factor matrix are:

0

8.0

0.1

0.1

0.2

6.5

0.6

8.6

0

0

0

8.0

0.1

0

0

5.0

0

5.0

0.2

0

3.3

5.2

11100000000000

10010100000000

01001110000000

00100011110000

00000000101000

00011001000110

00000000011101

00000000000011

LLNN TsCDp

The queue of device’s residual energy which

named NPow could be given according to the table 1. It is

shown as follow:

Using (4), each device’s energy consumption balancing

factor NPb is calculated based on each device’s energy

consumption factor NDp and residual energy. The results

are shown on the following table 2.

C. Compute the path and use it Finally we apply the shortest path algorithm on the

weighted graph to obtain the new path to send H’s data to the host.

Fig. 3 is the simulation result with the new path for H established. In Fig. 3, the dots marked with 1 to 7 represent the 7 nodes from A to G. The energy consumption balancing factor of each node is 6.8, 12.0, 8.0, 5.0, 5.0, 10.0, and 1.6. The blue lines are links and the red line is the routing path the system manager computes for the new node. The total cost of this path is 16.4.

The result shows that the energy consumption balancing factor can illustrate the traffic and the remaining power of the node very well and the MEBRS algorithm can find out an energy balancing routing path according to the factor.

5. Conclusions Centralized sensor networks are adopted by industrial

automation for their possibility to offer robust, reliable, and secure real-time support. Good routing method could be achieved with the unique features of a centralized sensor network. In this paper we talked about the characteristics of a centralized wireless sensor network with mesh topology. Then we proposed MEBRS and discussed the reason for it and how the MEBRS algorithm is fulfilled in the system manager. The simulation result shows that the MEBRS algorithm is an efficient energy balancing routing algorithm.

References [1] Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubram-

aniam, and Erdal Cayirci, “A Survey on Sensor Networks”, IEEE Communications Magazine, August 2002. Pp.102-114.

9.0

5.0

1.0

2.0

4.0

7.0

5.0

1

NPow

0

6.1

10

0.5

0.5

8

12

8.6

i

iN Pow

DpPb

Table 2: Energy consumption factor of each node

Node A B C D E F G H

Energy Consumption

Balancing Factor

6.8 12 8 5 5 10 1.6 0

Figure 3: The example network in the simulation

[2] Alois Ferscha1, Stephan Olariu, and Tom Pfeifer, “Wireless Sensor Networks and Applications”, Dagstuhl Seminar Proceedings 04122, 2006.

[3] Sun Yu-ting, Lv Wei-qin etc. “EBAT: Energy Balanced Adaptive Transmission Algorithm for Sensor Networks”, IEEE computer society, pp.565-574.

[4] W. Heinzelman, A. Chandrakansan and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless MircrosensorNetworks", Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS '00), January 2000.

[5] Ruihua Zhang , Lin Wang, Shichao Geng, Zhiping Jia, “A Balanced Cluster Routing Protocol of Wireless Sensor Network”, IEEE computer society, pp.221-225.

[6] Hua Yu, Prasant Mohapatra, Xin Liu “Channel assignment and link scheduling in multi-radio multi-channel wireless mesh networks” Mobile Netw Appl (2008),Volume 13 , Issue 1-2 ,Pages: 169-185

[7] Ian F. Akyildiz, Xudong Wang, Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005.

[8] Zhang Xia, Yu Hong-yi, “A Virtual Multipath Routing Protocol for Reliable Data Delivery in Wireless Sensor Networks”, IEEE 2008

[9] Bastien Mainaud, Mariem Zekri, and Hossam Afifi, “Improving routing reliability on wireless sensors network with emergency paths”, The 28th International Conference on Distributed Computing Systems Workshops, 2008, pp.545-550.

[10] W. Heinzelman, A. Chandrakansan and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Mircrosensor Networks", Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS '00), January 2000.

[11] ISA100 standard, http://www.isa.org/ [12] WirelessHART standard,

http://www.hartcomm2.org/index.html