Abstract

Energy conservation is an essential and critical requirement for a wireless sensor network with battery operated nodes intended for long term operations. Prior work has described different approaches to routing protocol designs that achieve energy efficiency in a wireless sensor network. Several of these works involve variations of mote-to-mote routing (flat routing) while some make use of leader nodes in clusters to perform routing (hierarchical routing). A key question then arises as to how the performance of an energy-aware, flat routing protocol compare with that of one based on hierarchical routing. This paper demonstrates a hierarchical routing protocol design that can conserve significant energy in its setup phase as well as during its steady state data dissemination phase. This paper describes the design of this protocol and evaluates its performance against existing energy-aware flat routing protocols. Simulation results show that it exhibits competitive performance against the flat routing protocols.

1.  Introduction

Wireless adhoc networks comprise of stationary or mobile devices that communicate over wireless channels without any fixed wired backbone infrastructure. A wireless sensor network (WSN) is a special class of adhoc networks that integrates sensing, processing and communications in small, battery-powered motes [1,2]. These motes (sensor nodes) typically collaborate on a global sensing task and deliver required data to one or more hubs. Sensor nodes that have variable-powered RF transceivers can provide greater routing performance at the cost of higher power consumption [3-5]. On the other hand, nodes that have fixed-power RF transceivers are generally cheaper but may be more prone to communication disruptions [6,7]. Despite advances in MicroElectro Mechanical Systems (MEMS) technology, energy constraints continue to limit the operations lifetime of a WSN and new, energy-aware motes are still experimental [2,6,8,9]. Some WSNs adopt a hierarchical configuration during deployment [5,10]. The deployed network topology consists of distributed clusters of sensor nodes. Each of these clusters is managed by a cluster head (or leader sensor node) that is responsible for data aggregation within the cluster and communications between this cluster and neighbouring ones.

Within a WSN, whether clustered or non-clustered, the primary means of relaying data among nodes is via a routing protocol [5,10-19]. Hence, an essential and critical design requirement of the routing protocol is that it be energy-aware. An energy-aware routing protocol should exhibit energy efficiency and balanced energy consumption across the WSN. The first requirement ensures that the WSN can sustain operations over prolonged, unattended periods. The latter requirement ensures that sections of the WSN do not fail prematurely and disrupt operations. A routing protocol for WSNs typically comprises the three phases: set-up phase, route management phase and data dissemination phase. With clustered wireless sensor networks, the set-up phase may also incorporate the formation of clusters around each available cluster head.

Energy-aware routing protocols cannot merely deliver the message to a hub via the shortest or most energy-efficient route. Due to high usage, energy resources of nodes along these routes will be depleted faster than others and these routes will fail. Protocol design must also ensure that packet traffic is distributed relatively uniformly across the network so that energy resources of all nodes are depleted at a balanced rate. This will ensure that certain network sections/nodes will not be abruptly disconnected due to low energy resources [7,9]. These are by no means trivial requirements and pose conflicting demands on the design of energy-aware routing protocols [20]. While conventional routing protocols for wireless networks are typically concerned with throughput and network latency, energy-aware routing protocols in WSNs have to consider energy consumption, energy variance and scalability as well [2,10,12,14,21-23].

With these issues in mind, we propose an energy-aware routing protocol, Energy Clustering Protocol (ECP) that routes messages via cluster heads. Unlike other clustered configurations, ECP exploits nodes at the boundaries of the cluster (border nodes) to assist in the forwarding of packets as well as to reduce dependency on and energy expenditure of cluster heads. Via performance simulations against existing energy-efficient routing protocols that use energy-distance metrics, probabilistic distribution of packet traffic and MAC adaptations, we show that ECP exhibits very low energy variance as well as high energy efficiency over WSNs with increasing number of nodes. The remainder of this paper is organised as follows. Section 2 surveys three existing energy efficient routing protocols proposed for multi-hop WSNs. Section 3 highlights our motivation and the contribution of our work. Section 4 describes the detailed design of our proposed routing protocol. Simulation results are presented and discussed in Section 5. Finally, Section 6 concludes this paper followed by the references.

2.  Related Work

In this section, we discuss three more recently proposed routing protocols for multi-hop WSNs. They are Energy Probabilistic Routing (EPR) [6], Gradient Based Routing (GBR) [24] and Efficient and Reliable Routing (EAR) [25]. These routing protocols are similar in the sense that they make use of neighbourhood information such as hop-count and node energy levels to relay data. They differ in their approach to distribute packet traffic.

2.1.  EPR

EPR is a reactive protocol that is destination-driven. That is, the hub or sink node initiates the route request and subsequently maintains the route. EPR selects routes probabilistically based on residual energy and energy consumption, thus helping to spread energy use among all the nodes. The protocol has three phases: setup, data dissemination and route maintenance. In the setup phase, interest propagation occurs as localized flooding, in the direction of the source node, to find all routes from source to hub and their energy costs. Before sending the request, the hub sets a “Cost” field to zero. Every intermediate node forwards the request only to neighbouring nodes that are closer to the source node than itself and farther away from the hub. On receiving the request at a node, the energy cost for the neighbour that sent the request is computed and is added to the total cost of the path. Routing tables are generated during this phase. Only neighbouring nodes with paths of low cost are added to the routing table. Paths that have a very high cost are discarded. A probability is assigned to each of the neighbours in the routing table with the probability inversely proportional to the cost. In the data dissemination phase, data is relayed using information from the routing tables generated in the setup phase. Paths are chosen probabilistically according to the energy costs that were calculated earlier. This is continued till the data packet reaches the destination node. A node may therefore have multiple routes to the hub. In the route maintenance phase, localized flooding is performed intermittently from hub to source to keep all the paths alive.

2.2.  GBR

The GBR protocol seeks to distribute the network traffic load evenly among all nodes to prevent overloading. The hub will broadcast an interest message that is propagated throughout the network. Each node upon receiving the interest message will record the number of hops taken by the interest message. This allows the node to know the number of hops it needs to reach the hub. The difference between the hop count of a node and that of its neighbour is the gradient of that link. Gradients are thus setup from the nodes to the hub and all messages will flow in that direction towards the hub. A node will forward a message to a neighbour with the greatest gradient. If this link is not available due to failure or disruption, the neighbour with the next highest gradient is chosen and so on. When there are multiple neighbours with links having the same gradient, one is randomly chosen. Random choice of the next hop node has a good effect of spreading traffic over time as well as achieving re-configuration to adapt to communication disruptions and distortions.

When a node detects that its energy level has dropped by 50% or more, it increases its hop count (lowering its gradient) to discourage other nodes from routing packets through it. This change in gradient is propagated as far as needed over the network to keep other gradients consistent.

2.3.  EAR

In the EAR protocol, routing decisions are based on hopcount and a weighted combination metric. This second metric is a weighted combination of energy levels, distance traversed and transmission success history used to determine optimal routes during data dissemination. A “sliding-window” that keeps track of the last N successful transmissions via a specified RF link is used to compute transmission success history. An optimal route in EAR may not be the shortest but represents the best combination of distance, energy requirements and RF link performance. Control packets are minimized by “piggy-backing” route management information onto MAC-layer protocol packets. EAR deals well with communication disruptions and distortions in WSNs with low to moderate traffic volumes, mostly due to moreinformed and therefore accurate routing decisions. However, in WSNs with a high-volume of network traffic, the proportionate increase in control packets incur an appreciable overhead affecting its performance.

3.  Motivation and Contribution

The protocols in our survey use different approaches to achieve energy efficiency. A minimum cost spanning tree such as that used in EAR allows for a low total energy consumption but sacrifices node survivability by over-utilising nodes on optimal routes. Probabilistic routing over multiple alternative paths to the hub is a technique used by EPR to overcome the over-utilisation of nodes on shortest paths. Such multi-paths are built based on a weighted combination of neighbouring node distance, projected energy expenditure and node residual energy. Energy availability metrics such as those employed in GBR control routing through nodes with the highest residual energy to balance energy consumption over the network.

In all cases, the focus is primarily on balancing energy consumption during the data dissemination phase. Typically, the set-up phase in these protocols involves flooding that starts from the hub to relay location and route information throughout the WSN. This technique consumes a significant proportion of energy from all nodes in the WSN. Set-up tasks are important as they provide necessary network configuration and status information that allows subsequent successful operation of the WSN. In noisy environments and where the WSN nodes are mobile, initiating a secondary set-up phase is the most straightforward and practical way to re-configure the network and re-synchronize operations.

In our design, we adopt a node clustering approach to utilise the gains of data fusion in tandem with energy conservation. Our proposed protocol, ECP, is designed with the following advantages: energy-efficient set-up process, low and balanced energy consumption during data dissemination by utilizing cluster boundary nodes instead of solely cluster heads, and scalable performance.

4.  Energy Clustering Protocol (ECP) Design

4.1.  Overview

In this section, the design and operation of ECP is presented. ECP is a routing protocol that minimizes route setup energy whilst maintaining low data dissemination energy consumption. A low energy route setup cost is important in applications where the network configuration may change dynamically due to inconsistent RF links, node mobility or simply when the nodes have fallen in residual energy after a period of time. In these applications, a low route setup cost is valuable to establish new routes again that reflect the new network topology in terms of residual energy and connectivity.

Unlike LEACH [19], ECP does not assume that all network nodes are able to reach the hub directly. Nodes route data packets to cluster heads. Each cluster head then routes to its border nodes and these in turn route to border nodes and cluster head of a neighbouring cluster. In this way, data is relayed from cluster to cluster and eventually to the hub. ECP is thus able to cater to larger network deployments where motes may be scattered over significant distances. Also, the use of border nodes as routing support balances the energy consumption per cluster and obviates requirements for differentiated high transmission power cluster heads.

Another novel feature of ECP is that cluster heads are elected probabilistically. ECP elects one hop clusters in a 3-round process, each round with increasing probabilities to form its clusters. This clustering process strives to increase the number of border nodes between clusters for the conduct of inter-cluster routing. Instead of using multiple hop clusters in a multi-hierarchical setting, ECP forms one-hop clusters in a single level hierarchy in the WSN. The advantages of one hop cluster are detailed in Subsection 4.2. In ECP, nodes already in a cluster may join another cluster if through distance estimation they are detected to be nearer to the other cluster head. Thus, more energy can be conserved through this simple scheme without additional control messages. Energy is also minimised during routing since nodes are clustered based on their distance from the cluster head.

ECP does not need location information of its nodes through localisation or GPS techniques as in the BCDCP protocol [26]. The use of localisation or GPS techniques consumes additional energy in order to initialise the nodes with their geographical coordinates. ECP also does not require all nodes to send their information to the hub first for some centralized processing. Sending information to the hub for centralized processing is a common technique which allows for some useful network-wide information regarding residual energy, average energy levels or geographical location of nodes to be mapped out. Routing patterns can then be fixed through this network mapping. This method, however, is not distributed and does not scale very well with increasing network size. ECP achieves clustering and routing in a distributed manner and thus provides good scalability. The operation of ECP is divided into 3 phases: clustering, route management, and data dissemination. The following sub-sections will detail the design of these phases.

4.2.  Clustering

Phase one of ECP is to cluster sensor nodes together to achieve a maximum number of border nodes and minimum number of clusters. To prevent the same border nodes from being used continuously, the clustering algorithm aims to achieve denser clusters. One-hop clustering is adopted for ECP because these clusters have been shown to be more robust and subjected to less connectivity problems and communication overheads [27]. When a node is first powered on, it will decide if it will elect itself to be a CH. The probabilities used for the 3-round clustering are 0.1, 0.4 and 1 for the first, second and third rounds of clustering, respectively. These values are determined empirically. The flowchart in Figure 1 shows how cluster formation is done.

CHs once elected wait for a random amount of time before broadcasting a PROBE message to its neighbours. The node is confirmed as a CH after the PROBE message is sent. This PROBE message announces the status of the newly formed CH to surrounding nodes. Nodes already elected to be CHs but have not yet sent the PROBE will give up their status to become cluster members. Nodes without cluster status (not cluster head or cluster members) will join the cluster as members via the PROBE message. The selection of a random range of time to wait before broadcasting a PROBE message is dependent on the density of the cluster and the maximum time for a message to be sent from one hop to the next.

Let the cluster density d be defined as the number of nodes which a particular sensor node is able to reach within its transmission range. Let t be the maximum time taken for a PROBE or REPLY message to traverse one hop. This is also the minimum time that an elected cluster head node has to wait before broadcasting the PROBE message.

Assuming a worst case scenario where all the (d+1) nodes in a potential cluster (1 potential cluster head node surrounded by d neighbours) may be elected as cluster heads. To prevent this scenario, the minimum range of waiting time allocated to the nodes has to be at least (d+1) t.

That is, a node that has elected itself as cluster head waits at least t units or as long as (d+2)t units as shown in the right diagram of Figure 1.

After a node elects itself as a potential cluster head and broadcasts the PROBE message, only one CH is formed and the rest of the elected CHs give up their CH candidacy to be cluster members. Upon reception of a PROBE message, nodes without a CH will reply with a REPLY message and store the address of the CH. Nodes which have already joined a CH will also reply with a REPLY message if the PROBE message is from another CH. These nodes then compare the distance between the original CH and the PROBE message from the new CH and join the CH that is nearer. Its previous CH will be regarded as a secondary CH. This ensures that no CHs will be deprived of cluster members or some CHs will have too many cluster members. All CHs thus keep a record of their cluster members using the REPLY messages.

4.3.  Route Management Phase

The route management phase comprises of route propagation and route request. Route propagation avoids conventional flooding to discover an unknown network. It achieves this by using the clusters from the previous phase to forward the route messages. ECP forms a minimum energy-cost spanning tree of CHs instead of all nodes. CHs, upon receiving a routing cost, will be able to update their cluster members of the route cost by intra-cluster broadcasting. The non-border node cluster members thus play a passive role in route dissemination. This helps to save transmission cost as not all nodes will have to participate in forwarding the route messages. A route request round follows after route propagation. This is necessary because of the possible presence of isolated clusters. An isolated cluster that does not have any border nodes with another cluster misses out on route information. This phase of ECP discovers these nodes without a routing table and requests for a route.

4.3.1.  Route Propagation

Route propagation begins when the hub first broadcasts an advertisement (ADV) packet with its address to its neighbours. All nodes start with an original cost to the hub of infinity. The ADV packet from the hub starts with a cost of 0. Nodes that receive the ADV packet add the cost of the ADV and the cost of transmitting from sender to receiver. If this cost is smaller than the receiver’s original cost, it will add the sender’s information into its route table. Otherwise, the ADV packet is ignored. Where the sender is the hub, the node will add the route to the hub and forwards future data packets direct to the hub and not to its CH. Nodes receiving the ADV packet from a non-hub node will send it to their CHs. In the case of border nodes where they have more than one cluster head (one primary CH where it sends its data packet to and secondary CHs for routing purposes), the border node sends point-to-point traffic to all its primary and secondary CHs. The CHs upon receiving the ADV will check that the cost of this ADV is lower than its original cost. If the ADV packet is of a lower cost, it will broadcast this route cost to its cluster member nodes. Border nodes upon receiving this new routing cost will thus be able to resend it to the other CHs. Figure 2 shows this.

4.3.2.  Route Request (Route propagation)

Route request starts after route propagation of ADV packets. Here, nodes that do not have a route after a timeout period potentially belong to an isolated cluster that does not have a border node with other clusters. These nodes then broadcast Route Request messages (RREQ) in an attempt to discover a neighbouring cluster that has a route to the hub. When nodes receive an RREQ packet, they will reply with an ADV packet. The sender of the RREQ packet receives this ADV and propagates the route information to its own CH. The CH then continues with the normal route propagation. CHs and non-CHs may broadcast RREQ packets and the lowest route cost ADV packet is kept. Transmission of data packets start immediately after a route to hub is received. If a lower cost ADV should arrive to the node, dynamic updating of the lower cost route is done concurrently with application sensing. The lower cost route will thus be the new route used.

4.3.3.  Energy Metric

The energy metric that is used can include information about the cost of using the path, energy status of the nodes along the path or reliability of the RF links etc. ECP evaluates routes by evaluating the energy used to transmit and receive on a link. For motes with variable transmission power, the energy metric would be a function of the distance between the sender and receiver. For motes with fixed transmission power, the energy to transmit and receive on a link is the same for all nodes. As channel acquisition overhead is large, small control packets have disproportionately high energy costs. ECP minimizes the use of control packets to propagate the route information to all the nodes by propagating the route information to its CHs instead.

4.3.4.  Energy Model

In the evaluation of the protocols in this study, the energy model in [19,28] is used. The energy costs of broadcast, point-to-point and non-destination traffic are different. We denote the energy lost due to channel transmission as r², where r is the distance between the sending and receiving nodes. Therefore, the energy expended to transmit a k-bit packet over a distance d and to receive that packet defined by:

ETx (k, d) = Eelec * k + Eamp * k * d² + b    (1)

ERx (k) = Eelec * k + b                   (2)

where, ETx = Energy taken to transmit the packet ERx = Energy taken to receive the packet Eelec = Energy dissipation of radio transceiver circuitry Eamp = Energy to run transmit amplifier For simplification, we consider the radio channel to be symmetrical. The above energy model where a node consumes energy through transmitting/receiving packets may be described as a linear equation [29]. To account for energy consumption at the data link layer through device mode changes and channel acquisition cost, a fixed cost b is included that depends on the operation mode:

Broadcast traffic: In an IEEE 802.11 Broadcast, the sender listens briefly to the channel and sends the messages if the channel is clear. We define the fixed channel access cost as b_b-send and b_b-recv:

ETx (k, d) = Eelec * k + Eamp * k * d² + b_b-send

ERx (k) = Eelec * k + b_b-recv

Point-to-point traffic: In IEEE 802.11, when a node sends an RTS control message identifying the receiver node, the latter responds with a CTS. Upon receiving the CTS, the the data is sent and the sender waits for an ACK from the receiver. This handshake overhead is accounted by the fixed channel access cost for sending/receiving a packet as bpp-send and bpp-recv respectively:

ETx (k, d) = Eelec * k + Eamp * k * d2 + b_pp-send

ERx (k) = Eelec * k + b_pp-recv

Non-destination traffic: Non-destination nodes in the range of either the sender or receiver overhear some or all of the packet traffic. Non-destination nodes in non-promiscuous mode can enter into a reduced energy consumption mode while data is being transmitted in the vicinity. For non-promiscuous nodes discarding traffic, Equation (2) becomes:

Discard cost = Eelec * k + b_discard                   (3)

Experimental values for all the b parameter in the 3 modes of operation are listed as follows:

4.4.  Data Dissemination

The clustering phase, route propagation and route request processes ensure that every node has a route to the hub via its own CH. Depending on the application, nodes will start generating DATA packets at periodic intervals or cluster member nodes may go into sleep mode if they are not needed. If a node has a direct route to the hub, the DATA packet will be sent direct to it. Cluster member nodes that are not border nodes will send the DATA packet to its CH for data fusion. Besides cluster members, CHs also keep a record of member nodes that are border nodes and their corresponding costs to the hub. The CHs will select the border node with the least cost to the hub and route the DATA packet to the border node. Border nodes upon receiving a DATA packet will send the packet to its record of CHs with lower energy cost than itself. Hence, DATA packets are routed from cluster to cluster till it reaches the hub. Data aggregation is also used by ECP. When DATA packets meet along the same path at a CH, the data is aggregated before transmission. Through this inter-cluster routing approach using CHs and border nodes together with data fusion and aggregation methods, the network is effectively condensed into a shortest spanning tree of CHs and their border nodes. Non-border node cluster members thus do not participate in the routing decisions. The total number of transmissions is thus reduced leading to higher energy savings and lower variance across the network.

5.  Simulation

GloMoSim [30] is a discrete-event simulator designed for wireless networks. It is made up of library modules, each of which simulates a specific routing protocol in the protocol stack. Simulator settings used are shown in Table 1.

5.1.  Performance Metrics

The following metrics were used to measure the performance of the routing protocols.

Packet delivery ratio (PDR): this measures the percentage of data packets generated by the nodes that are successfully routed to the hubs. It is expressed as:

Packet latency: this measures the average time it takes to route a data packet from the source node to the hub. It is expressed as:

Energy Consumption: this measures the energy expended per delivered data packet. It is expressed as:

Energy Variance: this measures the energy distribution of the network. It is expressed as:

5.2.  Noisy Environment Tests

These tests analyze the protocols’ behavioural differences in an actual operating environment. The test is conducted by generating random noise factors of between 10% and 50%. The noise factor of a node indicates the probability that packets received by the node are corrupted or lost in transmission. Results were averaged over 30 runs each with a different seed and presented in Figures 3 to 6.

5.2.1.  Packet Delivery Ratio and Latency

When more active sources are included, probability of packet collisions increases and PDR of all protocols fall. ECP is able to maintain about the same throughput as packets need only be sent to CHs. The reduced transmissions help lessen the impact of noise. PDR of GBR dips the most with more source nodes because it routes via shortest paths to the hub but lacks a robust delivery mechanism. EPR performs better than GBR as it is a probabilistic protocol and does not consistently use the same routes. Packet latency of EPR is highest at 10% source nodes as it routes according to the residual energy remaining in the nodes and does not consider how long the route may take. ECP suffers from some latency overhead due to routing to the CH first before routing to the hub. GBR and EAR suffers the least latency at 10% source nodes due to shortest path routing to the hub. At 50% and 90% source nodes, EAR showed the highest

latency from 200 nodes onwards. Route blacklisting occurs and data packets are routed through other less noisy RF links leading to more hops. The random back off mechanism for re-transmissions also contributes to the high latency.

5.2.2.  Energy Consumption and Variance

The reason for EPR’s higher energy consumption is due to the use of multi-path routing. Each node makes a localized decision to route the data packet based on probability. The node with the highest residual energy has the highest probability to be used as an intermediate node for routing to the hub. The protocol does not take a shortest path to the hub but instead aims to minimise the energy variance over the network. The energy consumption of EAR and GBR are about the same. Both protocols use optimal paths to route to the hub. The energy consumption of ECP is the lowest among the four protocols. Although additional energy is expended by routing to the CH first, the energy

spent is less than the cumulative energy savings of data fusion. As the number of nodes increases, the clusters become denser. The effects of increased data packets from the higher number of nodes are mitigated by data fusion. The energy variance of EAR, EPR and GBR are shown to increase with network size. As more packets are generated, optimal paths are used continuously resulting in a higher energy variance in the network. For ECP, although more packets are generated, these packets are aggregated at the CHs thus leading to a reduced energy variance in the network.

5.2.3.  Energy Remaining

Figure 7 shows the average node energy remaining after data packet transmissions have ceased in different sized networks for 10%, 50% and 90% active source nodes. In all 3 scenarios, ECP shows the highest average node energy remaining due to the use of cluster heads for packet routing. The trend is also relatively stable with increasing network size showing uniform route distribution of packets over the network. For 10% and 50% active sources, results exhibited by EAR and GBR are similar up to network sizes of 300. Beyond that, as well as with 90%