Abstract: Power consumption is an important issue in energy-constrained sensor networks. Many scheduling schemes have been proposed for sensor networks with high node density, to extend their lifetime by making only some nodes active while allowing others to go to sleep with negligible power consumption. However, most scheduling schemes do not take into account that the directional and uneven data traffic moving towards a data sink results in some areas running out of energy more rapidly than others, which may disconnect the network and the data sink, thereby wasting residual energy in other areas. This study proposes to balance the power consumption throughout the network for homogeneous sensor networks with high node density. The sensor network is partitioned into rectangular grids. Only one node is scheduled to be active in each grid at any time, to monitor that grid and to relay the data from other grids. To make energy stored in a grid proportional to the total power consumption of that grid, the lifetime of all individual grids is equalized. The simulation results show that the proposed algorithm not only extends the lifetime but it also improves the performance of sensor networks by preventing some areas from being out of monitoring earlier than other areas when the connectivity of the network is lost.
INTRODUCTION
A sensor network is a self-organizing multi-hop system without pre-existing infrastructure. Each sensor node in this network can act as a router to relay packets for others to the data sink by using multi-hop routes. Sensor networks usually have many sensor nodes and they are often implemented in hostile environments, making energy recharge infeasible. Energy efficiency therefore becomes important.
Many scheduling schemes have been proposed for sensor networks with high node density to improve their energy efficiency. Scheduling schemes save energy by scheduling some nodes into active state to generate the data and to keep the connectivity of the network, while putting others into sleep state with negligible power consumption.
Figure 1 shows a sensor network with high node density. Because of the high node density, an area that could be monitored by only one node may in fact have several sensor nodes. If all of these nodes in this area are active, i.e., are generating and relaying data, (1) the duplicate data in this area will waste network resources, such as energy and bandwidth; (2) the large number of nodes participating in relaying data will make the topology complicated, thereby increasing delay in route discovery in reactive routing protocol or increasing routing table overhead in proactive routing protocol and (3) the high-density data traffic will increase the probability of data congestion thereby increasing the packet loss rate.
The active nodes should generate, transmit and relay data; because of this, they will run out of energy rapidly. Therefore, the roles of active nodes are rotated. Using a scheduling algorithm to rotate the roles of active nodes can thus balance the power consumption among the nodes. However, most scheduling algorithms do not take into account the directional and uneven data traffic in sensor networks, which usually results in the nodes near the data sink running out of energy more rapidly than the others. The connectivity between the data sink and the network may therefore be lost due to the transmission range limitation of the sensor nodes thereby wasting the residual energy in other areas. The earlier running out of energy in these areas that results in theses areas out of monitoring will furthermore affect the performance of the network.
| Fig. 1: | The colored area covered in duplicate by 5 nodes |
This study proposes to prolong the lifetime of the network by addressing the uneven data traffic issue for homogeneous sensor networks with high node density, so that the connectivity of the network will not be lost before almost every node has run out of energy. In addition, the nodes in this algorithm need not initiate an omni-directional flooding to find a route, but they will direct route requests towards the data sink so that the flooding in reactive route discovery is reduced, saving further energy.
RELATED WORK
Power consumption is important in ad hoc sensor networks. Many technologies have been proposed to extend the lifetime of sensor networks such as:
| • | Scheduling active and non-active nodes in ad hoc sensor networks with high node density; |
| • | Selecting the route with the least number of hops or with the minimum needed energy to forward the data; |
| • | Balancing the power consumption among the nodes participating in routing the data; |
| • | Compressing the data that needs to be relayed; |
| • | Using directional antennas to reduce flooding in route discovery, etc. |
This study investigates the scheduling schemes, which save energy by scheduling only some nodes to be active and are usually applied in sensor networks with high node density. The existing schemes are classified into two major categories: The Medium Access Control (MAC) schemes and the routing and topology management schemes.
MAC schemes: This study investigates contention based MAC schemes and non-contention based MAC schemes.
Early MAC schemes for sensor networks are usually contention based, such as (IEEE standards Department, 1997). Nodes that are ready to send data in some contention based MAC schemes sense the activity of the channel. If no activity is detected, they send a Request to Send (RTS) to their destinations from which they can receive a Clear to Send (CTS) message. The first successful pair of nodes to RTS and ACK has the right to use the channel. During the data transmission, all other nodes are required to keep quiet. When the transmission is completed, the destination will send an Acknowledgment (ACK) back to the source node. The PAMAS (Raghavendra and Singh, 1998) modifies IEEE 802.11 into the architecture with two channels. The nodes in PAMAS can sleep when other nodes are transmitting or their transmission would interfere with the transmissions of neighbors. However, PAMAS does not take into account the issue of idle listening. S-MAC (Ye et al., 2002) is a single-channel protocol. The frame in S-MAC is separated into active part and sleep part. The messages can only be sent out during the active part thereby reducing the idle listing issue compared to PAMAS. However the nodes in S-MAC need some synchronization of sleep schedules with surrounding neighbors, which is realized by periodically broadcasting their schedule increasing flooding. Several schemes have been proposed based on S-MAC, such as T-MAC (Dam and Langendoen, 2003), which extends S-MAC by adjusting the length of time that sensors are awake between sleep intervals based on communication of neighbors. Most recently, Chowdhury et al. (2006) proposes a CMAC scheme. This scheme assumes a multi-channel scenario and in-band signaling. It allows for listening and replying to controlling messages even when the reception of a data packet is in progress at a sensor node, thus taking a step towards solving the deafness problem in sensor networks.
The contention based MAC schemes allow the node go into sleep state to save energy. However, the power consumption in these schemes by collision, overhearing and idle listening is still significant so that people propose the non-contention based MAC schemes, such as preamble-based TDMA, to improve the energy efficiency of sensor networks. Preamble-based TDMA MAC schemes are collision-free by scheduling each node when it should be active and when it can go to sleep.
The TDMA MAC protocol by Katayoun and Pottie (1999) schedules each node a timeslot to communicate its known neighboring nodes. TRAMA (Rajendran et al., 2003) employs a traffic adaptive and distributed election scheme to allocate timeslots among nodes. The nodes in TRAMA periodically awake to exchange broadcasts and to learn their two-hop neighborhood so that it can reserve future slots for backlogged traffic and only one node in a two-hop neighborhood will transmit in a given slot. Miller and Vaidya (2004) improves TRAMA design by scheduling long-lived, end-to-end, periodic flows instead of scheduling recently received packets on a hop-by-hop basis. Furthermore, their scheme does not need to maintain consistent two hop neighborhood information and results in a simpler scheduling algorithm. The ER-MAC protocol (Rajgopal et al., 2003) is similar to TRAMA. This scheme divides a network into TDMA groups based on the neighborhood information. Using an energy criticality of a node which is a function of the residual energies and traffic flow rates of its neighbors, it can adaptively allocate the timeslot to the nodes so that can balance the power consumption. In Sichitiu’s (2004) scheme, the nodes maintain a table of times when they should wakeup to send and receive. When a sender intends to schedule a new flow on a link, the nodes will awake at a specified time and the sender will send an RSETUP packet if no data transmission is sensed in the slot. If the RSETUP packet is received successfully by the receiver, an ACK will be sent back to the sender and the slot is scheduled. Otherwise, no ACK is sent back to the sender and the sender should try in a different slot.
Routing and topology management schemes: The Geographical Adaptive Fidelity (GAF) algorithm (Xu et al., 2001) uses geographical information to prolong the lifetime of the network. The main idea of GAF is to partition the network into virtual square grids. The grids are structured such that any two nodes within neighboring grids can communicate with each other. Energy is saved by scheduling only one node to be active in any grid and placing the other nodes in its grid into a sleeping state. Koushanfar et al. (2003) does not separate the network into grids, but forms a backbone for the network while putting other nodes into a sleep state. The nodes take turns to form the backbone to distribute the power consumption. Differently from GAF and Koushanfar’s algorithms, the nodes in ASCENT (Cerpa and Estrin, 2002) decide to become active based not only on neighborhood links but also on observed data loss rates, thereby providing the network with the ability to trade energy consumption for communication reliability. Similarly to ASCENT, SPAN (Chen et al., 2004) adaptively elects active nodes according to the number of their neighbors, but SPAN also considers the residual energy of the nodes. The node in SPAN takes the responsibility for making an independent decision on whether it should become active, based on its residual energy and its benefit to the neighboring nodes to bridge their communication. The active and the sleep nodes will periodically check their states to decide whether they should take a new role as to go to sleep or to become active, respectively.
| Fig. 2: | Basic energy-conserving algorithm |
Xu et al. (2000) propose two distributed coordination routing algorithms to manage nodes’ channels: The Basic Energy-Conserving Algorithm (BECA) and the Adaptive Fidelity Energy-Conserving Algorithm (AFECA). The basic idea of BECA is to put the nodes into sleep state when they are not participating in sending, forwarding, or receiving data. BECA defines three possible states for a node in terms of its radio: Sleeping, listening and active as shown in Fig. 2. Each node has an initial sleep period of time Ts. However, during this sleep period, if the node has data to send, it will become active. If it does not have data to send, it will change to listening state after the sleep period Ts. The listening period will be Tl. If it has data to send during this period, it will change to active state. If not, it will return to sleep state after Tl. The active period is defined as Ta. When a node becomes active, if it does not send or receive data after Ta, it will return to sleep mode. AFECA is built on BECA but it adjusts the sleep time of a node based on node density.
Both STEM (Schurgers et al., 2002) and RATE-EST (Miller and Vaidya, 2005) use two channels: The primary channel is for sending data and the secondary one is a wake-up signal. Both algorithms use a busy tone instead of encoded data for the wakeup signal. Energy is saved by leaving the sensors in a sleep state while they are monitoring the environment but not sending data.
PROPOSED ALGORITHM FOR BALANCING POWER CONSUMPTION
The main purpose of this algorithm is to prolong the lifetime of large sensor networks with high node density by balancing power consumption throughout the network.
| Fig. 3: | Directional data traffic in sensor network |
| Fig. 4: | Connectivity of the network is lost |
First, the existing scheduling schemes are analyzed and then the proposed algorithm is presented in detail.
Analysis of existing schemes: In most sensor networks, the analysis capability of the nodes is not conclusive. The sensors can only generate or relay data. Therefore, a data sink is required to gather all data for further analysis. The data sink thus becomes the same destination for all sensor nodes, resulting in directional data traffic, as shown in Fig. 3. The directional traffic makes the traffic density of the network different according to their distance from the data sink. The nodes near the data sink will usually encounter higher traffic and will therefore run out of energy more rapidly. If the area width that exhausts energy exceeds the transmission range of the sensor nodes, the data sink will be isolated and the connectivity between the data sink and the network will be lost, as shown in Fig. 4. The residual energy in other areas will then be wasted. Therefore, if the power consumption can be balanced throughout the network, some areas running out of energy and thereby out of monitoring sooner than others can be prevented and the lifetime of the network can be extended.
We had previously addressed the above problem and the need to consider the lifetime of the entire network instead of just saving energy for individual nodes (Wei et al., 2005). The concept of extending the lifetime of the network by balancing the node energy consumption is also explained (Du et al., 2006). However, their scheme, which uses a chessboard configuration with a heterogeneous sensor network, is different from this algorithm, which balances the power consumption in a homogeneous sensor network with high node density by adjusting the sizes of the rectangular grids, each of which has only one active node.
| Table 1: | Parameters and their meanings |
Balancing power consumption: GAF (Xu et al., 2001) partitions the network into equal squares with only one node active at any time in each square. As analyzed, however, the areas near the data sink in GAF will run out of energy sooner, thereby shortening the network lifetime and affecting the network performance. Therefore, energy efficiency and network performance can be further improved by balancing the power consumption throughout the network. However, this improvement will usually require squares of different sizes if the nodes are uniformly or randomly distributed in the network. Unfortunately, to partition the entire network into squares of different sizes to balance the power consumption is infeasible. This algorithm therefore partitions the network into rectangular grids. But, each grid will also have only one active node to monitor that grid and to relay the data for others.
In this algorithm, it is assumed that if the active nodes are not transmitting or receiving data, they will be put into sleep state automatically with negligible power consumption. The simplified equation of the power consumption of one node (1) can then be achieved with the definition of each parameter shown in Table 1 in which et and er have the same value.
(1) |
The power attenuation n depends on the distance between the transmitter and receiver. That is, for short distances the propagation loss is modeled as inversely proportional to d2 while for long distances this loss is modeled as inversely proportional to d4 (Heinzelman, 2000; Liu and Lin, 2005).
| Fig. 5: | Balance the power consumption |
| Fig. 6: | Example of how to balance the power consumption |
In addition, for the transmit amplifier to give a reasonable Signal to Noise Ratio (SNR) at least 30 dB with distance d<dcrossover(=87 m), eTx-amp = 10 pJ/bit/m2; while for a distance d≥dcrossover, eTx-amp = 0.0013pJ/bit/m4 (Liu and Lin, 2005).
The sensors in this algorithm are in general identical, so that they all start with the same initial energy Einitial. Therefore, if there are m nodes in one grid, as shown in Fig. 5, the total initial energy stored in that grid is mxEinitail. Σ Pre and Σ Ptr are, respectively used to express the power consumption on receiving and transmitting data of the active node. The total power consumption of the grid is then the sum of Σ Pre and Σ Ptr. Dividing the total initial energy stored in the grid by its total power consumption is then the lifetime of that grid (2). If the lifetime of each grid is almost the same, the power consumption is then balanced among the grids and therefore the entire network.
(2) |
Figure 6 is used as an example to explain the algorithm in detail. Suppose all active nodes generate a amount of data and which is sent to the data sink by multi-hop routes. The node transmission range is limited within the neighboring grid. That is, when the active node in grid I is sending the packets, only the active node in grid I-1 can receive it. Assume that the power consumption on transmitting a amount of data is Ptra and on receiving a amount of data it is Prea, the power consumption of each active node in different grids can then be achieved as shown in Table 2.
| Fig. 7: | How to find a route |
| Table 2: | Power consumption of active nodes in different grids |
The main purpose of this design is to equalize the lifetime of all grids. Therefore, in this example (3) must be observed, in which mi means the total number of the nodes in that grid.
(3) |
Route discovery: Because the data sink is the same destination of all sensor nodes, the omni-directional flooding in traditional reactive routing protocol is thus unnecessary. This algorithm directs route requests towards the data sink so that the flooding in route discovery is reduced, thereby saving further energy.
Each node in this algorithm has an ID number, which increases according to its distance to the data sink. That is, a node with a longer distance to the data sink will have a higher ID number than a node which is closer to the data sink.
It is assumed that the node has the function of Received Signal Strength Indication (RSSI) so that it can estimate and compare the distances between the nodes, that is, when the strength is strong, the distance is short, otherwise it is long. With this RSSI the exact required power for each hop can be estimated and assigned to individual nodes. All sensor nodes have a maximum transmission range. Because all sensors are identical, this maximum transmission range is a constant.
Figure 7 helps to explain how a node in this network finds a route by using reactive routing protocol. Suppose the active node in grid 8 is ready to send data and needs to find a route. It sends a route request to its neighboring nodes. There may be some active nodes with lower ID number than that of the active node in grid 8 within its maximum transmission range, yet only the active one with the lowest ID number will be allowed to relay the request so that the route request is directed towards the data sink. In this example, only the active node in grid 5 will relay the request. The active node in grid 5 continues to relay the request to its next hop until the data sink is reached. The route information is then sent back to the active node in grid 8. The data will be sent to the data sink along this route. Therefore, the omni-directional flooding in traditional reactive protocol is unnecessary in this algorithm.
PERFORMANCE EVALUATION
This section shows the simulation results of the proposed algorithm. The simulation environment is a rectangular network of 50x100 m with 40 homogeneous nodes randomly distributed in it. The data sink is set at the corner of the network as shown in Fig. 8. The parameters and their values used in the simulation are shown in Table 3. The network is separated into 8 grids to evaluate the performance of the algorithm. Each grid has only one active node. The maximum transmission range of the nodes is limited within 55 m; according to (1), here n is defined as 2.
The active node will periodically send a 500 Byte packet to the data sink and the communication is clock driven. A Round is defined as the period from when all the active nodes start to send a 500 Byte packet towards the data sink to when the data sink receives all the data that can reach the data sink. The lifetime of the network can then be measured by the number of Rounds.
| Fig. 8: | Simulation scenario |
| Table 3: | Parameters used in the simulation |
| Fig. 9: | Average residual energy in the grids at 750 Rounds |
The role as the active node is rotated every 2 Rounds. The node with the highest residual energy in that grid will be selected to be the active node for the next 2 Rounds.
The GAF (Xu et al., 2001) is used as a comparison for this algorithm.
Figure 9 shows the residual energy in the nodes in GAF and the proposed Balancing Power Consumption Algorithm (BPC) at 750 Rounds. From this figure, it can be seen that the uneven data traffic makes the nodes in grid 1 consume energy more rapidly in GAF. Yet in the proposed BPC, the power consumption rate of different grids is similar.
Basically, the lifetime of a sensor network can be defined in three ways:
| • | when the first node runs out of energy |
| • | when the connectivity of the network is lost |
| • | when the last node runs out of energy. |
In this simulation, the lifetime of the network is measured as defined by (a) and (b). (a) is used to measure how BPC can extend the lifetime of the network by balancing the power consumption throughout the network. However, the first node running out of energy does not mean the network cannot work, because the nodes can still send and relay their data to the data sink by others that still have residual energy. That is, the connectivity of the network is still maintained. Therefore it is also necessary to measure the lifetime of the network as defined in (b). Although some people measured the lifetime as defined in (c) such as LEACH (Heinzelman et al., 2000), the authors assumed that all the nodes have high enough power to transmit their data to the data sink by a single hop. This, however, is not in fact the case in most sensor networks, especially in large sensor networks with many nodes far away from the data sink. Therefore, only the lifetime as defined in (a) and (b) is measured in this simulation.
The first node in GAF runs out of energy at 1410 Rounds, whereas in BPC runs out of energy at 2365 Rounds, as shown in Fig. 10 and 11, respectively. From this definition, BPC extends lifetime by 67.7% compared to GAF. When the first node runs out of energy, there are totally 22.57J and 4.29J energy left in GAF and BPC, respectively. Because the total initial energy of the network is 40J, the energy usage rate of GAF is only 43.6% whereas it is 89.3% in BPC.
Because the role of the active node is rotated, the nodes in the same grid will almost run out of energy simultaneously. That is, the first node running out of energy means the whole grid runs out of energy. The connectivity of the network is still maintained when one grid uses up its energy. However, the whole grid out of monitoring will definitely affect the performance of the entire network. The grids size in BPC may be quite different because of the different data traffic density. The frequent rotation as an active node in that grid, however, will almost not affect the performance of the network.
The simulation is continued to measure the number of Rounds until the connectivity of the network is lost. The results are shown in Fig. 12. GAF loses its connectivity at 1886 Rounds whereas BPC loses it at 2620 Rounds. From this definition, BPC extends the lifetime of the network by 38.9% compared to GAF. And as explained, the performance of the network is furthermore improved by BPC because it prevents some areas from running out of energy sooner than others.
| Fig. 10: | Average residual energy in the grids of GAF when the first node in grid 1 runs out of energy at 1410 Rounds |
| Fig. 11: | Average residual energy in the grids of BPC when first node in grid 5 runs out of energy at 2365 Rounds |
| Fig. 12: | Lifetime of the network |
Figure 12 also provides information on how many nodes still have residual energy when the connectivity of the network is lost. GAF has 30 nodes whereas BPC only has 10 nodes. When the connectivity of the network is lost, the total residual energy in GAF is 14.99J whereas in BPC it is only 1.15J. So, the energy usage rate of GAF and BPC is 62.5 and 97.1%, respectively, when the connectivity of the network is lost.
CONCLUSIONS
Power consumption is crucial for energy constrained sensor networks. Many scheduling algorithms have been proposed to improve the energy efficiency for sensor networks with high node density. Yet the nodes near the data sink in most scheduling algorithms will run out of energy sooner due to the uneven data traffic, resulting in wasting the residual energy in other areas and affecting the performance of the entire network.
This study proposes to balance the power consumption throughout the sensor network with high node density, so that no area will run out of energy earlier than other areas. The network is partitioned into rectangular grids. Only one node in each grid is scheduled into active state at any time. By making the initial energy store in each grid proportional to its power consumption, each grid will have almost the same lifetime. In addition, by directing the route requests towards the data sink results in further energy saving.
Simulation results show that the proposed algorithm extends lifetime by 67.7% based on when the first node runs out of energy and by 38.9% based on when the connectivity of the network is lost compared to GAF, respectively. The results also show that this algorithm improves the energy usage rate of the network by 104.8 and by 55.4% compared to GAF when the first node runs out of energy and when the connectivity of the network is lost, respectively. This means that it can be used to improve energy efficiency and performance for sensor networks with high node density.