ABSTRACT

In hierarchical networks, nodes are separated to play different roles such as CHs and cluster members. Each CH collects data from the cluster members within its cluster, aggregates the data and then transmits the data to the sink. Each algorithm that is used for packet routing in quality of service (QoS) based applications should be able to establish a tradeoffs between end to end delay parameter and energy consumption. Therefore, enabling QoS applications in sensor networks requires energy and QoS awareness in different layers of the protocol stack. We propose a QoS based and Energy aware Multi-path Hierarchical Routing Algorithm in wireless sensor networks namely QEMH. In this protocol, we try to satisfy the QoS requirements with the minimum energy via hierarchical methods. Our routing protocol includes two phase. In first phase, performs cluster heads election based on two parameters: node residual energy and node distance to sink. In second phase, accomplishes routes discovery using multiple criteria such as residual energy, remaining buffer size, signal-to-noise ratio and distance to sink. When each node detect an event can send data to the CH as single hop and CH to the sink along the paths. We use a weighted traffic allocation strategy to distribute the traffic amongst the available paths to improve the end to end delay and throughput. In this strategy, the CH distributes the traffic between the paths according to the end to end delay of each path. The end to end delay of each path is obtained during the paths discovery phase. QEMH maximizes the network lifetime as load balancing that causes energy consume uniformly throughout the network. Furthermore employs a queuing model to handle both real-time and non-real-time traffic. By means of simulations, we evaluate and compare the performance of our routing protocol with the MCMP and EAP protocols. Simulation results show that our proposed protocol is more efficient than those protocols in providing QoS requirements and minimizing energy consumption.

1. Introduction

In the recent years, the rapid advances in micro-electromechanical systems, low power and highly integrated digital electronics, small scale energy supplies, tiny microprocessors, and low power radio technologies have created low power, low cost and multifunctional wireless sensor devices, which can observe and react to changes in physical phenomena of their environments. These sensor devices are equipped with a small battery, a tiny microprocessor, a radio transceiver, and a set of transducers that used to gathering information that report the changes in the environment of the sensor node. The emergence of these low cost and small size wireless sensor devices has motivated intensive research in the last decade addressing the potential of collaboration among sensors in data gathering and processing, which led to the creation of Wireless Sensor Networks (WSNs).

A typical WSN consists of a number of sensor devices that collaborate with each other to accomplish a common task (e.g. environment monitoring, object tracking, etc.) and report the collected data through wireless interface to a sink node. The areas of applications of WSNs vary from civil, healthcare and environmental to military. Examples of applications include target tracking in battlefields, habitat monitoring, civil structure monitoring, forest fire detection and factory maintenance [1].

However, with the specific consideration of the unique properties of sensor networks such limited power, stringent bandwidth, dynamic topology (due to nodes failures or even physical mobility), high network density and large scale deployments have caused many challenges in the design and management of sensor networks. These challenges have demanded energy awareness and robust protocol designs at all layers of the networking protocol stack [2].

Efficient utilization of sensor’s energy resources and maximizing the network lifetime were and still are the main design considerations for the most proposed protocols and algorithms for sensor networks and have dominated most of the research in this area. However, depending on the type of application, the generated sensory data normally have different attributes, where it may contain delay sensitive and reliability demanding data. Furthermore, the introduction of multimedia sensor networks along with the increasing interest in real time applications have made strict constraints on both throughput and delay in order to report the time-critical data to the sink within certain time limits and bandwidth requirements without any loss. These performance metrics (i.e. delay and bandwidth) are usually referred to as Quality of Service (QoS) requirements [3]. Therefore, enabling many applications in sensor networks requires energy and QoS awareness in different layers of the protocol stack in order to have efficient utilization of the network resources and effective access to sensors readings.

Many routing solutions specifically designed for WSNs have been proposed [4,5]. In these proposals, the unique properties of the WSNs have been taken into account. These routing techniques can be classified according to the protocol operation into negotiation based, query based, QoS based and multi-path based. The negotiation based protocols have the objective to eliminate the redundant data by include high level data descriptors in the message exchange. In query based protocols, the sink node initiates the communication by broadcasting a query for data over the network. The QoS based protocols allow sensor nodes to make tradeoffs between the energy consumption and some QoS metrics before delivering the data to the sink node [6]. Finally, multi-path routing protocols use multiple paths rather than a single path in order to improve the network performance in terms of reliability and robustness. Multi-path routing establishes multiple paths between the source-destination pair. Multi-path routing protocols have been discussed in the literature for several years now [7,8]. Multi-path routing has focused on the use of multiple paths primarily for load balancing, fault tolerance, bandwidth aggregation and reduced delay [9].

Data gathering is a typical operation in many WSN applications and data aggregation in a hierarchical manner is widely used for prolonging network lifetime. Data aggregation can eliminate data redundancy and reduce the communication load. Hierarchical mechanisms (especially clustering algorithms) are helpful to reduce data latency and increase network scalability [10]. Clustering techniques have emerged as a popular choice for achieving energy efficiency and scalable performance in large scale sensor networks. Cluster formation is a process whereby sensor nodes decide which cluster head they should associate with among multiple choices. Typically this cluster head selection decision involves a metric based on parameters including residual energy and distance to the sink [11].

The rest of the paper organized as follows: in Section 2, we explain some of the related works. Section 3 describes the proposed protocol with detailed. Section 4 presents the performance evaluation. Finally, we conclude the paper in Section 5.

2. Related Works

In hierarchical networks, nodes are separated to play different roles, such as CHs and cluster members. The higher level nodes, cluster heads (CHs), Each CH collects data from the cluster members within its cluster, aggregates the data and then transmits the data to the sink. All of the hierarchical routing protocols aim at selecting the best CH and clustering the nodes into appropriate clusters in order to save energy. The hierarchical clustering protocol may execute reclustering and reselecting of CHs periodically in order to distribute the load uniformly among the whole network. By the method of CH selection, the hierarchical routing protocols can be classified into two categories: random-selected-CH protocol and well-selected-CH protocol. The former randomly selects CHs and then rotates the CH task among all nodes, while the latter carefully selects appropriate CHs and then gathers nodes under the CHs based on the network status [12]. On the other hand, meeting QoS requirements in WSNs introduces certain overhead into routing protocols in terms of energy consumption, intensive computations, and significantly large storage. This overhead is unavoidable for those applications that need certain delay and bandwidth requirements. In this section we do not give a comprehensive summary of the related work, instead we present and discuss some works related to proposed protocol.

One of the early proposed routing protocols that provide some QoS is the Sequential Assignment Routing (SA R) protocol [13]. SAR protocol is a multi-path routing protocol that makes routing decisions based on three factors: energy resources, QoS on each path and packet’s priority level. Multiple paths are created by building a tree rooted at the source to the destination. During construction of paths those nodes which have low QoS and low residual energy are avoided. Upon the construction of the tree most of the nodes will belong to multiple paths. To transmit data to sink, SAR computes a weighted QoS metric as a product of the additive QoS metric and a weighted coefficient associated with the priority level of the packet to select a path. Employing multiple paths increases fault tolerance, but SAR protocol suffers from the overhead of maintaining routing tables and QoS metrics at each sensor node.

K. Akkaya and M. Younis in [14] proposed a cluster based QoS aware routing protocol that employs a queuing model to handle both real-time and non real time traffic. The protocol only considers the end-to-end delay. The protocol associates a cost function with each link and uses the K least-cost path algorithm to find a set of the best candidate routes. Each of the routes is checked against the end-to-end constraints and the route that satisfies the constraints is chosen to send the data to the sink. All nodes initially are assigned the same bandwidth ratio which makes constraints on other nodes which require higher bandwidth ratio. Furthermore, the transmission delay is not considered in the estimation of the end-toend delay which sometimes results in selecting routes that do not meet the required end-to-end delay.

X. Huang and Y. Fang have proposed multi constrained QoS multi-path routing (MCMP) protocol [15] that uses braided routes to deliver packets to the sink node according to certain QoS requirements expressed in terms of reliability and delay. The problem of the end-toend delay is formulated as an optimization problem, and then an algorithm based on linear integer programming is applied to solve the problem. The protocol objective is to utilize the multiple paths to augment network performance with moderate energy cost. However, the protocol always routes the information over the path that includes minimum number of hops to satisfy the required QoS which leads in some cases to more energy consumption.

Authors in [16], have proposed the Energy constrained multi-path routing (ECMP) that extends the MCMP protocol by formulating the QoS routing problem as an energy optimization problem constrained by reliability playback delay and geo-spatial path selection constraints. The ECMP protocol trades between minimum number of hops and minimum energy by selecting the path that satisfies the QoS requirements and minimizes energy consumption.

LEACH is one of most important clustering protocol; the network organizes itself into clusters. LEACH performs a periodic randomized rotation of the cluster head to enable all the nodes in order not to drain the battery of a single Node Cluster head nodes drain energy much faster than other nodes, for balancing the overall energy consumption across the network the role of cluster head is rotated among all sensors [17].

In HEED [18], author introduces a variable known as cluster radius which defines the transmission power to be used for intra-cluster broadcast. The initial probability for each node to become a tentative cluster head depends on its residual energy, and final heads are selected according to the intra-cluster communication cost. HEED terminates within a constant number of iterations, and achieves fairly uniform distribution of cluster heads across the network.

Energy Residue Aware (ERA) clustering algorithm is one of energy-aware hierarchical approaches. It is also improved from LEACH by including the communication cost into the clustering. The communication cost includes residual energy, communication energy from the CH to the sink and communication energy from the cluster members to the CH. ERA uses the same CH selection scheme as LEACH but provides an improved scheme to help non-CH nodes choose a “better” CH to join by calculating the clustering cost and finding CH according to maximum energy residue [19].

In EAP (Energy-Aware Routing Protocol), a node with a high ratio of residual energy to the average residual energy of all the neighbour nodes in its cluster range will have a large probability to become the cluster head. This can better handle heterogeneous energy circumstances than existing clustering algorithms which elect the cluster head only based on a node’s own residual energy. After the cluster formation phase, EAP constructs a spanning tree over the set of cluster heads [20]. Only the root node of this tree can communicate with the sink node by single-hop communication. Because the energy consumed for all communications in the network can be computed by the free space model, the energy will be extremely saved and thus leading to sensor network longevity.

In QEMH protocol, we combine different ideas from the previous protocols in order to optimally tackle the problem of QoS and prolong lifetime in sensor networks. In this protocol we try to satisfy the QoS requirements with the minimum energy via hierarchical methods. The proposed protocol performs cluster heads election and routes discovery using multiple criteria such as residual energy, remaining buffer size, signal-to-noise ratio and distance to sink.

3. Description of the Proposed Protocol

In QEMH, the role of the cluster head must be rotated among all sensor nodes. Therefore, the operation of this protocol is divided into rounds. Each round begins with a formation of CHs phase and then in the route discovery phase, multiple paths between CHs are constructed as well as aggregated data are sent to the sink node.

3.1. Network Model

This paper assumes that N sensor nodes are randomly scattered in a two-dimensional square field A and the energy of sensor nodes cannot be recharged and each node in the network is assigned a unique ID. Also at any time, we assume that each sensor node is able to compute its distance to sink, its residual energy and its available buffer size (remaining memory space to cache the sensory data while it is waiting for servicing), as well as record the link performance between itself and its neighbours node in terms of signal-to noise ratio (SNR) and distance to sink.

3.2. Formation of CHs Phase

At the beginning of each round, each node first broadcasts the CE-Msg message within radio range r which contains value of CE parameter. Each node receives the CE-Msg from all neighbors in its cluster range and compares it with its CE. If node’s CE is the largest value within radio range r, it will set its state as cluster head. CE parameter obtained by Equation (1) :

(1)

where, (E_node-res)_j is the current residual energy of node j and dis(j) is calculated by Equation (2):

(2)

In here D_db is node distance to sink also we assume that number of bits, k = 1 and Transmission power, t_p = 1.

3.3. Route Discovery Phase

In multi-path routing, node-disjoint paths (i.e. have no common nodes except the source and the destination) are usually preferred because they utilize the most available network resources, hence are the most fault-tolerant. If an intermediate node in a set of node-disjoint paths fails, only the path containing that node is affected, so there is a minimum impact to the diversity of the routes [21,22]. After election CHs, in first phase of path discovery, each cluster head broadcasts a HELLO message to its neighbouring CHs within radio range R in order to have enough information about which of its neighbours can provide it with the highest quality data. Each cluster head maintains and updates its neighbouring table during this phase. Figure 1 shows the structure of the HELLO message.

1) Link Cost metric

The link Cost metric is used by the CH to select the next hop during the path discovery phase. Let N_i be the set of neighbours of CH_i. Cost metric includes an energy factor, available buffer factor and link performance factor and can be computed as below:

(3)

where, E_resd,j is the current residual energy of CH_j, where, B_buffer,j is the available buffer size of CH_j and Lp_ij is the link performance value between CH_i and CH_j which is obtained by Equation (4) :

(4)

In here SNR_ij is the signal to noise ratio (SNR) for the link between CH_i and CH_j as well as Distance_{j to sink} is the distance from CH_j to sink. So, to select next hop we use from Equation (5):

(5)

After initialization phase each CH has enough information to compute the Cost metric for its neighbouring CHs. Then, the sink node locally computes its preferred next hop CH using the link Cost metric and sends out a RREQ message to its the most preferred next hop , Figure 2 shows the structure of the RREQ message. Similarly, through the link Cost metric, the preferred next hop CH of the sink computes locally its the most preferred next hop in the direction of the cluster head related to source node and sends out a RREQ message to its next hop, the operation continues until source node (the node which has detected event).

TR field shows the received time of the packet and Delay field shows the transmission delay of the packet, so we can compute the link end to end delay by using the information in the RREQ message. When a node receives the RREQ message from its neighbour, it calculates the difference between the value of TR field and the current time which represents the measured delay of the link between two neighbours as well as stores it in the Delay field. For the second alternate path, the sink sends alternate path RREQ message to its next the most preferred neighbour CH. To avoid having paths with shared CH, we limit each CH to accept only one RREQ message. For those CHs that receive more than one RREQ message only accept the first RREQ message and reject the remaining messages. In order to save energy, we reduce the overhead traffic through reducing control messages. Therefore, instead of periodically flooding a KEEPALIVE message to keep multiple paths alive and update Cost metrics, we append the metrics on the data message by attaching the residual energy, remaining buffer size and link performance to the data message.

2) Path Selection

After the completion of paths discovery phase, we need to select a set of paths to transfer the traffic from the source node to the sink. So out of the P paths, the proposed protocol picks out a number of r paths to be used to transfer the real-time traffic and n paths for non-real-time traffic, where P = r + n . To calculate r, we assume that the sensor node knows the size of its traffic (both real-time and non-real-time traffic). Let T_r represents the size of the real-time traffic and T_nr represents the size of the non-real-time traffic, then we have:

(6)

As we divided the P paths between the real-time and non-real-time traffic according to the traffic size, we select the best r paths that minimize the end to end delay to transfer the real-time traffic to ensure that the critical-time data is delivered to the destination within the time requirements, with out any delay. To find the best baths in terms of the end-to-end delay, during the paths discovery phase, we use Delay field in RREQ message.

3.4. Traffic Allocation and Data Transmission

QEMH employs the queuing model presented in [14] to handle both real-time and non-real-time traffic. Two different queues are used; one instant priority queue for real-time traffic and the other queue follow the first in first out basis for non-real-time traffic. Figure 3 shows the example of queuing model. The source node knows the degree of the importance of each data packet it is sending which can be translated into predefined priority levels. The application layer sets the required priority level for each data packet by appending an extra bit of information to act as a stamp to distinguish between realtime and non-real-time packets. Based on the packet type, the classifier directs packets into the appropriate queue. The traffic allocation scheme first adds error correction codes to improve the reliability of transmission and to increase the resiliency to paths failures and ensure that an essential portion of the packet is received by the destination without incurring any delay and more energy consumption through data retransmission .Then schedules packets simultaneously for transmission across the available multiple paths . Correction codes are calculated

as a function of the information bits to provide redundant information. We use an XOR-based coding algorithm like the one presented in [23]. This algorithm does not require high computation power or high storage space. Figure 4 shows the functional diagram of the QEMH.

After the selection of a set of multiple paths for both traffic types and after adding FEC codes, the source node can begin sending data to the CH as single hop and CH to the sink along the paths. We use a weighted traffic allocation strategy to distribute the traffic amongst the available paths to improve the end to end delay and throughput. In this strategy, the CH distributes the traffic amongst the paths according to the end to end delay of each path. The end to end delay of each path is obtained during the paths discovery phase via Delay field in RREQ message. Figure 5 shows the packet format and fields in each segment.

4. Performance Evaluation

We used NS-2 to implement and simulate QEMH and compare it with the EAP and MCMP protocols. Simulation parameters are presented in Table 1 and obtained results are shown below. We investigate the performance of the QEMH in a multi-hop network topology. The metrics

used in the evaluation are the average energy consumption, lifetime (number of rounds), time of nodes dead, average end to end delay and delivery ratio. We study the impact of changing the packet arrival rate and the node failure probability on average end to end delay, packet delivery ratio and average energy consumption also impact of changing the number of nodes on lifetime and time of 100% nodes dead. Simulation results are averaged over several simulation runs.

4.1. Impact of Packets Arrival Rate

We change the packet arrival rate at the source node from 5 to 50 packets/second. The generated traffic at the source node is mixed traffic of both real-time and nonreal-time traffic. The real-time traffic is set to 10% of the generated traffic.

1) Average end-to-end delay

The average end to end delay is the average time required to transfer a data packet from source node to the sink node. The Average end to end delay is an important metric in evaluating QoS based routing protocols. The average end to end delay of QEMH, MCMP and EAP protocols as the packet arrival rate increases is illustrated in Figure 6. From the results, it is clear that QEMH successfully differentiates network service by giving high real-time traffic absolute preferential treatment over low priority traffic. The real-time traffic is always combined with low end-to-end delay. MCMP protocol outperforms QEMH in the case of non-real-time traffic, because of the overhead caused by the queuing model. Furthermore, for higher traffic rates the average delay increases because the our protocol gives priority to process real-time traffic first, which causes more queuing delay for nonreal-time traffic at each sensor node. Performance of EAP protocol has reduced because of the overhead caused by the creation spanning tree.

2) Packet delivery ratio

Another important metric in evaluating routing protocols is the average delivery ratio. The average delivery ratio is the number of packets generated by the source node to the number of packets received by the sink node. Figure 7 shows the average delivery ratio of QEMH, MCMP and EAP protocols. Obviously, QEMH outperforms the MCMP and EAP protocols; this is because in the case of path failures, our protocol uses forward error correction (FEC) technique to retrieve the original message, which is not implemented in the MCMP and EAP protocols. Implementing a FEC technique in the routing algorithm enhances the delivery ratio of the protocol as well as minimizes the overall energy consumption especially in the case of route failures.

3) Average energy consumption

The average energy consumption is the average of the energy consumed by the nodes participating in message transfer from source node to the sink node. Figure 8 shows the results for the energy consumption; we observe that QEMH achieves more energy savings than MCMP and EAP protocols. This is because our protocol easily recovers from path failures and be able to reconstruct the original messages through the use of the FEC algorithm while the other protocols needs to initiate a data retransmission to recover lost data, which leads to a significant increase in the energy consumption. Furthermore, because of adding multi-path capability with hierarchical techniques, energy consumption is reduced.

4.2. Impact of Node Failure Probability

In this experiment, we study the behaviour of the protocol in the presence of node failures and change the node failure probability from 0 to 0.05.

1) Average end-to-end delay

The average end to end delay of QEMH, MCMP and EAP protocols as the node failure probability increases is illustrated in Figure 9. We observe that, the MCMP and EAP protocols are very sensitive to the increase in node failure probability. On the other hand, QEMH (either for real-time or non-real-time traffic) is not as sensitive to the increase of node failure probability as MCMP and EAP protocols. The FEC technique implemented in QEMH

protocol makes the protocol very effective and more resilience to node failures. Furthermore, the delay is not affected too much as the node failure probability increases.

2) Packet delivery ratio

Average packet delivery ratio for three protocols is illustrated in Figure 10. As the node failure probability increases, the average packet delivery ratio of MCMP and EAP protocols drops significantly. On the other hand, the QEMH protocol is slightly affected by the increase in the node failure probability. This is because of QEMH employs an error correction scheme which contributes in increasing the delivery ratio in the case of path failures by reconstructing the original message using the generated XOR codes without the need to initiate data retransmissions.

3) Average energy consumption

Figure 11 shows the results for the average energy consumption under node failures. We observe that QEMH protocol achieves more energy savings than MCMP and EAP protocols. This is because QEMH protocol easily recovers from path failures and be able to reconstruct the original messages through the use of the FEC algorithm. While the MCMP and EAP protocols needs to initiate a data retransmission to recover lost data, which leads to a significant increase in the energy consumption.