# MQoSR: A Multiobjective QoS Routing Protocol for Wireless Sensor Networks

Authors: Hind Alwan; Anjali Agarwal
Journal: ISRN Sensor Networks
 (2013)

---

## Abstract

With the growing demand for quality-of-service (QoS) aware routing protocol in wireless networks, QoS-based routing has emerged as an interesting research topic. Quality of service guarantee in wireless sensor networks (WSNs) is difficult and more challenging due to the fact that the available resources of sensors and the various applications running over these networks have different constraints in their nature and requirements. In this paper, we present a heuristic neighbor selection mechanism in WSNs that uses the geographic routing mechanism combined with the QoS requirements to provide multiobjective QoS routing (MQoSR) for different application requirements. The problem of providing QoS routing is formulated as link, and path-based metrics. The link-based metrics are partitioned in terms of reliability, delay, distance to sink, and energy, and the path-based metrics are presented in terms of end-to-end delay, reliability of data transmission, and network lifetime. The simulation results demonstrate that MQoSR protocol is able to achieve the delay requirements, and due to optimum path selection process, the achieved data delivery ratio is always above the required one. MQoSR protocol outperforms the existing model in the literature remarkably in terms of reliable data transmission, time data delivery, and routing overhead and underlines the importance of energy-efficient solution to enhance network lifetime.


---

## Body

## 1. Introduction

The open nature of wireless sensor networks (WSNs) recently attracted significant research attention [1]. The wide range of WSNs applications [2] in both civil and military domains and the fast growth of wireless networks indicate that the future network design will need to support various applications with different quality-of-service (QoS) requirements [3].In QoS-based routing protocols, the network has to balance its traffic while improving the network performance. Researchers have proposed many metrics for QoS routing as a set of constraints which can be specified as a wireless link constraint or a path constraint. Link constraints specify the restriction on the use of links such as delay, while a path constraint specifies the end-to-end QoS requirement such as the data transmission reliability constraint. Thus, routing algorithms are required to find specific routes for each application requirements, frequently given in terms of objectives.In many applications, to extend the network lifetime is considered more important than the quality of data, and this is related to the reduction of the energy dissipation in the sensor nodes. Thus, a network requires an energy-aware routing protocol. In real-time applications, data should be delivered in time or otherwise data is considered useless. In this case, the network requires a timeliness-aware routing protocol. However, in other applications, a reliable routing protocol is used since the reliability of data transmission in the network is considered as an important issue.Most of the proposed QoS routing protocols for WSNs characterize the network with a single metric such as hop count, delay, or energy efficiency algorithms to compute paths, and due to the extreme energy constraints of sensor nodes, most of these protocols focused on energy efficiency in order to maximize network lifetime [4–6]. However, in order to support different and multiple QoS requirements, the protocols need to characterize the network with multiple metrics such as energy, delay, and data loss probability. The basic problem, therefore, is to find a path that satisfies the multiple constraints for QoS routing in an energy-efficient way. Compared with routing decision using single-objective or single-link constraint, the multiobjective or multiconstraint routing decision is very different, and the problem of determining a QoS route that satisfies the multiple constraints has been proven to be NP-complete [7].Our major contributions in this paper are the following. First, we define our QoS parameters of interest: end-to-end reliability, end-to-end delay and network lifetime. Second, we propose a novel heuristic mechanism in WSNs to provide multiobjective QoS routing for different applications. In the proposed MQoSR, the requirements of an application are modeled as multiple QoS classes in terms of reliability, delay, and energy, although others may also be considered. In particular, the problem of providing QoS routing is formulated as link-based and path-based metrics. In the link metrics, sensor nodes need to consider the distance to sink as well as the application requirements in order to calculate the total cost function of a link that is used to select next hop. Thus, sensor nodes need to have the information of its direct neighboring nodes only. However, in path-based metrics and benefit from the fact that the sink has unlimited resources, the sink is responsible for selecting the routing paths, the number of these paths, and the allocation strategy of data packet on each path in order to achieve the end-to-end requirements in terms of reliability and delay as well as to extend the network lifetime. Finally, we evaluate the performance of our routing protocol using extensive network simulations and compare this to the performance of some existing models in the literature.The remainder of this paper is organized as follows. Section2 provides a brief overview of the related work on QoS routing in WSNs. Section 3 introduces the network model and assumptions used in it as well as presenting the formulation of the QoS routing problem. The proposed MQoSR routing protocol is described in Section 4. The results of simulation are presented in Section 5. Finally, the conclusion of this work is provided in Section 6.


## 2. Related Work

With the growth in potential use of WSNs, considerable research efforts have been done in QoS routing and covered in comprehensive survey articles presented in [3, 8–10]. Most of the protocols presented focus on only one or two QoS fields. For instance, bandwidth is used as the only QoS parameter for routing in [11], and by considering collision, a multipath routing protocol is proposed in [12] to increase the network lifetime and throughput while decreasing latency. Moreover, the work in [13] proposed a secure and energy-efficient multipath routing protocol in WSNs.Position-based routing or geographic routing [14] uses greedy forwarding mechanism for packet delivery in multi-hop wireless networks. Direct neighbor nodes exchange location information and locally select the neighbor that is closest to the destination. In this case, a sensor node needs to know only the location information of its one-hop neighbors without the knowledge of the entire network; thus discovery floods and state propagation are not required beyond a single hop. The network is able to adapt proficiently to the topological changes and conserves energy and bandwidth. This greedy forwarding mechanism is modified according to the reliability of links in [15]. However, using traditional greedy forwarding, a transmission may fail when the node has no neighbors closer to the destination than itself and other limitations appear when used in realistic networks [16].One of the first QoS-based routing protocol is the Sequential Assignment Routing (SAR) [17] that builds multiple paths from sink to sensors by creating multiple trees where the root of each tree is a one-hop neighbor from sink by taking into account the energy resource on each path and the priority level of the data packet as the QoS metric. However, sensors involved in route setup have extra overhead introduced. The work in [18] avoided the overhead problem presented in SAR by selecting a path from a list of candidate paths that meets the end-to-end delay requirement and enhances the throughput for best effort traffic. It is assumed that each node in the network has a classifier to check and divert the incoming traffic to different priority queues for real-time and non-real-time traffic. Thus, a multipath routing protocol is proposed to support both best effort and real-time traffic at the same time; the gateway sets a specific bandwidth ratio as an initial value which represents the amount of bandwidth to be dedicated to real-time and non-real-time traffic on a particular outgoing link in case of congestion. Each node locally adjusts the bandwidth and delay requirement based on the path length and the traffic. However, the protocol is not scalable since global knowledge of the network topology is required by each node and also other QoS requirements for real-time traffic are not supported. Moreover, this protocol adapts the class-based priority queuing mechanism which is too complicated and costly.The work in SPEED [19] proposed a location-based real-time routing protocol for soft end-to-end deadline guarantee to maintain a desired delivery speed in the network. However, energy metric has not been considered in the design of SPEED protocol. An extension of SPEED is the MMSPEED [20] protocol, which is proposed to provide QoS differentiation in timeliness and reliability domains for WSN by delivering packets with respect to the required end-to-end delay parameter in order to avoid congestion and decrease the packet loss rate. To support timeliness, multiple network packet delivery speed options are provided for different traffic according to their end-to-end deadlines, and to support reliability, multipath is used to control the number of delivery paths based on the required end-to-end reaching probability.Another routing protocol which addresses both energy efficiency and QoS is the LQER protocol presented in [21]. LQER protocol makes path selection based on historical states of link quality after minimum hop field is established. The link quality estimation strategy results in reliability as well as energy efficiency. A multiobjective cross-layer routing algorithm for resource constrained WSNs was proposed in [22] that calculates the cost of each possible path between the source node and the sink after the application assigns weight for each requirement in order to achieve multiobjectivity of existing routing protocols.In [23], each node uses its own and its neighbor’s state information to adapt its routing and MAC layer behavior by employing a flexible cost function at the routing layer and adaptive duty cycles at the MAC layer that relies on local decisions to equalize the energy consumption of all nodes. In this way, the routes can be maintained easily and little overhead is added. However, decisions are made locally without considering the entire path from the source to the destination.A multiconstrained QoS multipath routing (MCMP) protocol is proposed in [24]; the protocol uses braided routes to deliver packets to the sink to enhance network performance with reasonable energy cost and achieves the required QoS in terms of reliability and delay. The end-to-end delay is expressed as an optimization problem and solved by an algorithm based on linear integer programming. However, routing data over the minimum hop count path to satisfy the required QoS leads in some cases to more energy consumption. ECMP protocol [25] is proposed as an extension to MCMP which considers QoS routing problem as a path-based energy minimization problem constrained by reliability, delay, and geospatial energy consumption.Furthermore, applying redundancy to satisfy some QoS requirements in WSNs drains considerable research efforts, and some are covered in a survey article presented in [26]. In [27], forward error correction technique is used to provide fault recovery, balance the energy consumption over sensor nodes, and increase the reliability of data transmission.Many routing protocols that have been designed to provide QoS are more appropriate for some application requirements having better performance while not suitable for other requirements having major limitations. Moreover, supporting different and multiple QoS requirements and modeling the network as path-based and link-based multiple metrics such as energy, delay, and reliability of data transmission were not considered in the aforementioned works.


## 3. QoS Routing Problem Formulation

In this section, we present the formulation of the proposed routing problem.


### 3.1. Network Model and Assumptions

We model a WSN withN nodes and one sink as an undirected graph, G=(S,L,Q) in the plane (Figure 1), where S denotes the set of vertices that represent the communication sensor nodes, L denotes the set of edges representing links between nodes, and Q is a nonnegative QoS capacity vector of each edge. The distance of a direct link l(sx,sy)∈L between nodes sx and sy is dsx,sy. A path is defined as a sequence of links from the source node to the sink, and P={path1,path2,…,pathn} is the set of n available node-disjoint paths between the source node and sink. We assume that sensors are homogeneous; each sensor has same transmission radius, a, and they consume equal energy to transmit a bit of data. Furthermore, we assume that the sensor nodes are stationary, and at any time, each sensor node is able to compute its available energy level,Eava, as well as record the link performance between itself and its neighbor nodes in terms of delay, Dlink and reliability, Rlink, where Rlink is expressed in terms of signal-to-noise ratio (SNR) [27]. Additionally, each node is assumed to know its exact position, the position of nodes within its range of communication, neighbour nodes, and of the sink using localization techniques.Figure 1
Wireless sensor network model.


### 3.2. Energy Consumption

The energy consumed for data transmission,Epathp, from any sensor node to the sink on a single path, p, can be written as
(1)Epathp=∑l=1hoppEconl,
where hopp is the hop count of path p, n≥p≥1, and Econl is the energy consumption and is expressed by Econl=etx+erx, where etx and erx are the energy consumption to transmit and receive b bits of data between two sensor nodes. This energy model is adopted from [28], where etx=(et+εamp×a2)×b and erx=(er×b), et and er are the energy consumption to transmit and receive one bit of data, respectively, εamp is the energy consumption of the transmitting amplifier. When sensors have fixed communication radius, a, nodes located randomly at any distance within the area of πa2 always have the same power consumption for transmission. Then, Econl(et+er+εamp×a2)×b. To transmit b bits of data packet, the available energy at a node,Eava, must be larger or equal to the minimum energy threshold required to transmit this packet, Ereq. In multipath routing, the total end-to-end energy consumption, Ee2e, to transmit any data packet is measured as the summation of the energy consumption on all the used paths and is given as
(2)Ee2e=∑p=1npEpathp,
where np is the number of node-disjoint multipath used to route the data packet. We assume that the energy consumption at the unintended receiver nodes that overhear the transmission is not included.We can then present the energy objective functionfE that minimizes the total energy consumption on all used paths as fE: Minimize the energy consumption, Ee2e.


### 3.3. Delay Metric

Delay is the time elapsed from the departure of a data packet from the source node to the destination node. The delay metric between two nodes represented asDlink is the sum of processing, queuing, transmission, and propagation delay. Many of the developing WSNs involve delay sensitive applications with real-time delay constraints; meeting such delay constraints requires deploying an efficient routing technique that reduces delay and ensures on-time packet delivery.The delay of a path,Dpathp, is the sum of the delays at all the intermediate nodes along the path:
(3)Dpathp=∑l=1hoppDlinkl.
Therefore, the end-to-end delay to transmit the data packet to the sink along the selected path or paths is given as
(4)De2e=max1≤p≤npDpathp.
The delay objective function, fD, is to ensure that the end-to-end delay on the selected paths is the minimum and/or De2e≤Dreq, where Dreq is an application-specific parameter which reflects the required end-to-end delay for data delivery.


### 3.4. Reliability Metric

The transmission reliability is an important index of QoS, calculated to measure the probability of transmission failures and can be expressed in terms of data delivery ratio. If all source nodes send total packets of Pktsource and the number of packets received by the sink is Pktsink, then the data delivery ratio, denoted as DDR, can be written as
(5)DDR=numberofpacketsreceivedatthesinknumberofpacketgeneratedbysourcenodes=PktsinkPktsource.
In the case that the required QoS can be met using a single path, the source node uses the single path to transmit data to the sink, and the reliability on a single path, p, is Rpathp and can be calculated as follows:
(6)Rpathp=∏l=1hoppRlinkl.
However, when the sink decides to use erasure coding to transmit the data packet on np disjoint paths, the end-to-end data transmission reliability, Re2e, is given by (7) and it is related to the number of used paths:
(7)Re2e=1-∏p=1np(1-Rpathp).
If Rreq is an application-specific parameter which reflects the required end-to-end reliability for data delivery, then WSN is considered reliable only if the data reliability satisfies Re2e≥Rreq. The reliability objective function, fR, is to maximize the data transmission reliability, Re2e, such that Re2e≥Rreq which is equivalent to minimize (-Re2e).To achieve the required reliability by an application using erasure coding, the network has to satisfy the reliability gained using erasure coding. The source node codes each data packet of sizebM bits it receives into M fragments, each of size b [26], and generates another K coding fragments to have in total a set of M+K fragments. This set of fragments is then transmitted as subpackets x1 to xnp over np selected paths to the sink, where ∑p=1npxp=M+K. To reconstruct the original packet, at least M fragments should be received by the sink, allowing at most K lost fragments, and the coding rate is thus defined as M/(M+K). The successful probability of packet received by the sink, Psucc, to achieve the requested reliability, Rreq, has a binomial distribution that depends on Rpath and can be written as
(8)Psucc[y≥M]=∑y=MM+K(M+Ky)[(Re2e)y][1-Re2e](M+K-y).


### 3.5. Required QoS Model

We model the QoS required by an application into seven different classes as shown in Table1. In all these classes, the cost function is used to calculate each link cost after assigning the weighting factors CE, CD, and CR that are related to each other by the formula CE+CD+CR=1. The three-digit QoS field in Table 1 represents the requirement in terms of energy, delay, and reliability, respectively.Table 1
QoS classes model.
Class
QoS
Application requirements
W
Goals
C
E
C
D
C
R
1
100
Energy
1
0
0
Increaseing network lifetime, minEe2e
2
010
Delay
0
1
0
D
e2e ≤ Dreq
3
001
Reliability
0
0
1
R
e2e
≥
R
req
4
101
Energy and reliability
0.5
0
0.5
minEe2e and Re2e≥Rreq
5
110
Energy and delay
0.5
0.5
0
minEe2e and De2e≤Dreq
6
011
Delay and reliability
0
0.5
0.5
D
e2e
≤
D
req and Re2e≥Rreq
7
111
Energy, delay, and reliability
0.333
0.333
0.333
minEe2e,De2e≤Dreq and Re2e≥RreqWe can then write the required QoS function,Creq, as follows:
(9)Creq=EreqEava×CE+DlinkDreq×CD+RreqRlink×CR.


## 3.1. Network Model and Assumptions

We model a WSN withN nodes and one sink as an undirected graph, G=(S,L,Q) in the plane (Figure 1), where S denotes the set of vertices that represent the communication sensor nodes, L denotes the set of edges representing links between nodes, and Q is a nonnegative QoS capacity vector of each edge. The distance of a direct link l(sx,sy)∈L between nodes sx and sy is dsx,sy. A path is defined as a sequence of links from the source node to the sink, and P={path1,path2,…,pathn} is the set of n available node-disjoint paths between the source node and sink. We assume that sensors are homogeneous; each sensor has same transmission radius, a, and they consume equal energy to transmit a bit of data. Furthermore, we assume that the sensor nodes are stationary, and at any time, each sensor node is able to compute its available energy level,Eava, as well as record the link performance between itself and its neighbor nodes in terms of delay, Dlink and reliability, Rlink, where Rlink is expressed in terms of signal-to-noise ratio (SNR) [27]. Additionally, each node is assumed to know its exact position, the position of nodes within its range of communication, neighbour nodes, and of the sink using localization techniques.Figure 1
Wireless sensor network model.


## 3.2. Energy Consumption

The energy consumed for data transmission,Epathp, from any sensor node to the sink on a single path, p, can be written as
(1)Epathp=∑l=1hoppEconl,
where hopp is the hop count of path p, n≥p≥1, and Econl is the energy consumption and is expressed by Econl=etx+erx, where etx and erx are the energy consumption to transmit and receive b bits of data between two sensor nodes. This energy model is adopted from [28], where etx=(et+εamp×a2)×b and erx=(er×b), et and er are the energy consumption to transmit and receive one bit of data, respectively, εamp is the energy consumption of the transmitting amplifier. When sensors have fixed communication radius, a, nodes located randomly at any distance within the area of πa2 always have the same power consumption for transmission. Then, Econl(et+er+εamp×a2)×b. To transmit b bits of data packet, the available energy at a node,Eava, must be larger or equal to the minimum energy threshold required to transmit this packet, Ereq. In multipath routing, the total end-to-end energy consumption, Ee2e, to transmit any data packet is measured as the summation of the energy consumption on all the used paths and is given as
(2)Ee2e=∑p=1npEpathp,
where np is the number of node-disjoint multipath used to route the data packet. We assume that the energy consumption at the unintended receiver nodes that overhear the transmission is not included.We can then present the energy objective functionfE that minimizes the total energy consumption on all used paths as fE: Minimize the energy consumption, Ee2e.


## 3.3. Delay Metric

Delay is the time elapsed from the departure of a data packet from the source node to the destination node. The delay metric between two nodes represented asDlink is the sum of processing, queuing, transmission, and propagation delay. Many of the developing WSNs involve delay sensitive applications with real-time delay constraints; meeting such delay constraints requires deploying an efficient routing technique that reduces delay and ensures on-time packet delivery.The delay of a path,Dpathp, is the sum of the delays at all the intermediate nodes along the path:
(3)Dpathp=∑l=1hoppDlinkl.
Therefore, the end-to-end delay to transmit the data packet to the sink along the selected path or paths is given as
(4)De2e=max1≤p≤npDpathp.
The delay objective function, fD, is to ensure that the end-to-end delay on the selected paths is the minimum and/or De2e≤Dreq, where Dreq is an application-specific parameter which reflects the required end-to-end delay for data delivery.


## 3.4. Reliability Metric

The transmission reliability is an important index of QoS, calculated to measure the probability of transmission failures and can be expressed in terms of data delivery ratio. If all source nodes send total packets of Pktsource and the number of packets received by the sink is Pktsink, then the data delivery ratio, denoted as DDR, can be written as
(5)DDR=numberofpacketsreceivedatthesinknumberofpacketgeneratedbysourcenodes=PktsinkPktsource.
In the case that the required QoS can be met using a single path, the source node uses the single path to transmit data to the sink, and the reliability on a single path, p, is Rpathp and can be calculated as follows:
(6)Rpathp=∏l=1hoppRlinkl.
However, when the sink decides to use erasure coding to transmit the data packet on np disjoint paths, the end-to-end data transmission reliability, Re2e, is given by (7) and it is related to the number of used paths:
(7)Re2e=1-∏p=1np(1-Rpathp).
If Rreq is an application-specific parameter which reflects the required end-to-end reliability for data delivery, then WSN is considered reliable only if the data reliability satisfies Re2e≥Rreq. The reliability objective function, fR, is to maximize the data transmission reliability, Re2e, such that Re2e≥Rreq which is equivalent to minimize (-Re2e).To achieve the required reliability by an application using erasure coding, the network has to satisfy the reliability gained using erasure coding. The source node codes each data packet of sizebM bits it receives into M fragments, each of size b [26], and generates another K coding fragments to have in total a set of M+K fragments. This set of fragments is then transmitted as subpackets x1 to xnp over np selected paths to the sink, where ∑p=1npxp=M+K. To reconstruct the original packet, at least M fragments should be received by the sink, allowing at most K lost fragments, and the coding rate is thus defined as M/(M+K). The successful probability of packet received by the sink, Psucc, to achieve the requested reliability, Rreq, has a binomial distribution that depends on Rpath and can be written as
(8)Psucc[y≥M]=∑y=MM+K(M+Ky)[(Re2e)y][1-Re2e](M+K-y).


## 3.5. Required QoS Model

We model the QoS required by an application into seven different classes as shown in Table1. In all these classes, the cost function is used to calculate each link cost after assigning the weighting factors CE, CD, and CR that are related to each other by the formula CE+CD+CR=1. The three-digit QoS field in Table 1 represents the requirement in terms of energy, delay, and reliability, respectively.Table 1
QoS classes model.
Class
QoS
Application requirements
W
Goals
C
E
C
D
C
R
1
100
Energy
1
0
0
Increaseing network lifetime, minEe2e
2
010
Delay
0
1
0
D
e2e ≤ Dreq
3
001
Reliability
0
0
1
R
e2e
≥
R
req
4
101
Energy and reliability
0.5
0
0.5
minEe2e and Re2e≥Rreq
5
110
Energy and delay
0.5
0.5
0
minEe2e and De2e≤Dreq
6
011
Delay and reliability
0
0.5
0.5
D
e2e
≤
D
req and Re2e≥Rreq
7
111
Energy, delay, and reliability
0.333
0.333
0.333
minEe2e,De2e≤Dreq and Re2e≥RreqWe can then write the required QoS function,Creq, as follows:
(9)Creq=EreqEava×CE+DlinkDreq×CD+RreqRlink×CR.


## 4. Proposed MQoSR Protocol

We propose a heuristic path selection mechanism that considers the quality metrics for both the links and the paths. For different QoS requirements, MQoSR uses a different selection policy. The QoS requirements presented in Section3 are the most commonly used in most routing problems. However, other QoS requirements can also be considered according to the need of the applications. A node can satisfy the requirements by selecting next hop nodes based on the link condition and the requested requirement, while the sink can satisfy the end-to-end QoS by selecting path or paths that satisfy the requested QoS. The routing protocol used is the on-demand routing protocol that builds multiple node-disjoint paths as proposed in [29], whereby a fair fault tolerance mechanism is provided by the availability of alternate paths and the use of erasure coding at the source node [26].


### 4.1. Link-Based Metrics and Next Node Selection

Each sensor node is assumed to update the local states of its one-hop neighbors by broadcasting a HELLO message in which the links conditions are reported. Each node then maintains and updates its neighboring table information to record the link performance between itself and its direct neighbor nodes in terms ofRlink, Dlink, and Eava. Each sensor node knows the distance to its neighbors and to the sink node.


#### 4.1.1. Link Cost Function

Geographic routing protocols are efficient in wireless networks [30], geographic routing accomplished based solely on location information of nodes, nodes need to know only the location of their one-hop neighbors, the discovery floods and state propagation are not required, the used memory at each node is minimal, the bandwidth consumption is reduced, the energy is conserved, and the overhead is minimal. All these gains are an important concern for resource-concentrated network like WSNs.To  get benefits from geographic routing and in order to minimize the number of sensor nodes used to route data between source and destination [31], we considered the idea of greedy forwarding as one of the metrics to calculate the link cost function. The sender node searches its neighbors list looking for the neighbor node that is closest to sink, with largest expected progress, while at the same time satisfying the application requirements among all its forwarding candidates. Then, the expected progress of a link can be defined as a link cost, Clink, as follows:
(10)Clink=1(dsx,sink-dsy,sink),
where dsx,sink and dsy,sink are the distance of a sender node sx and a receiver node sy to the sink, respectively. The implicit aim of this strategy is to minimize Clink in order to minimize the hop count between source and destination.However, using greedy forwarding strategy in sensor network may lead to the dead end problem [16], which occurs when a message is forwarded to a node with no neighbor that is closer to the sink than the node that currently has the packet and is called local optimum. Avoiding this problem is a challenging issue for any geographic greedy forwarding approach. Although a dense deployment of wireless nodes can reduce the incidence of this problem in the network, it is still possible for some nodes to experience a local optimum.In the proposed MQoSR, if a sender node does not have any neighbor closer to the sink than itself, the message is forwarded according to the required QoS function only (9).


#### 4.1.2. Total Cost Function

The route request phase is started when the source node has data packet to transmit to the sink to which it has no available route by broadcasting a route request message (RREQ, Figure2(a)). Each source node reports the application requirements in terms of Rreq and Dreq in the required QoS field of the RREQ message. Each source node also initializes the values in the path parameters’ field, Dpath, Rpath, and hops to zero, one, and zero, respectively. The source node then broadcasts the RREQ to all its neighbors within its transmission range in which the path parameters are updated along the available paths to the sink. The route discovery phase is, therefore, introduced. Upon receiving the RREQ, each intermediate node selects one node as the next hop from its neighbor list to forward the RREQ depending on the total cost function given in the following:
(11)Ctotal=Clink×Creq,
where Clink is the link cost function and Creq is the cost of the required QoS.RREQ and RREP messages format.
(a)
(b)IfSneig is a set of neighbors of sensor node sx, then the RREQ message will be forwarded to the neighbor whose total cost function is the least (minsi∈sneigCtotal). This node is chosen and is reserved for that path to avoid having paths with shared nodes. However, if the selected node is already reserved, then the next smallest Ctotal node will be selected and so on. The selected node then modifies the path parameters’ field in the RREQ. The path parameters field in RREQ messages is initialized at the source node and updated at each intermediate node as follows. (1)
Compare the node available energy with the value reported inEmin field, Emin is the minimum available energy at a node on any path, and if Eava<Emin, then Emin=Eava; otherwise there is no change. Note that the initial value of Emin is equal to the Eava of source node. Thus, Emin is capturing the minimum reading of energy along the path.(2)
Dpath=Dpath+Dlink.(3)
hop=hop+1.(4)
Rpath=Rpath×Rlink.After receiving all the RREQ messages, the sink estimates the number of all available disjoint paths to the source and obtains information about each path. The sink podcasts the route reply message,RREP (Figure 2(b)), after evaluating the optimal paths as described in Section 4.2.


#### 4.1.3. Illustrative Example

To understand the role of next node selection process and to underline the importance of selecting different nodes when different QoS is requested, we illustrate MQoSR with the example in Table2, based on Figure 3 information. Each sensor node is labeled with four attributes as follows: distance to sink, available energy, link delay, and link reliability. When the source node, Sourcein Figure 1, originates a data packet, the RREQ message is broadcasted to all the neighbors of the source node within its transmission range. If a node, say 0, is one of the source neighbor nodes which is located at a distance of ds0,sink=20, from the sink and node 0 initiates the next node selection process to select next node depending on the requested QoS and the available resources, from its list of neighbor nodes 1, 2, 3, 4, and 5.Table 2
Example of next node selection process in MQoSR.
Required QoS
Costs
Node 1
Node 2
Node 3
Node 4
Node 5
Next node minCtotal
Class 1–7
C
link
1
0.5
0.285
0.333
2
Class 1
C
req
100/300 = 0.333
100/200 = 0.5
100/200 = 0.5
100/500 = 0.2
100/400 = 0.25
4
C
total
0.333
0.25
0.142
0.066
0.5
Class 2
C
req
10/120 = 0.083
30/120 = 0.25
40/120 = 0.333
50/120 = 0.416
25/120 = 0.208
C
total
0.083
0.125
0.095
0.138
0.416
1
Class 3
C
req
0.9/0.6 = 1.5
0.9/0.8 = 1.12
0.9/0.4 = 2.25
0.9/0.3 = 3
0.9/0.9 = 1
C
total
1.5
0.562
0.641
0.999
2
2
Class 4
C
req
1.833
1.625
2.75
3.2
1.25
C
total
1.833
0.813
0.784
1.066
2.5
3
Class 5
C
req
0.416
0.75
0.833
0.616
0.458
C
total
0.416
0.375
0.237
0.205
0.916
4
Class 6
C
req
1.583
1.375
2.583
3.416
1.208
C
total
1.583
0.688
0.736
1.138
2.416
2
Class 7
C
req
1.916
1.875
3.083
3.616
1.458
C
total
1.916
0.938
0.879
1.204
2.916
3Figure 3
Next node selection process in MQoSR; each node is labeled with a (ds,sink, Eava, Dlink, Rlink) quadruple.Table2 summarizes the next node selection process introduced in MQoSR protocol; different nodes are selected depending on the requested QoS and the available resource. In Table 2, Rreq, Dreq, and Eava are set to 0.9, 120, and 100, respectively. The link cost function is fixed for each node while the required QoS cost functions are altered based on the QoS classes.


### 4.2. Path-Based Metrics and End-to-End QoS

The process of selecting the routing paths, the number of these paths, and the allocation strategy of data packet on each route are related to the end-to-end application requirements and are decided on at the sink side.In general, the multi-QoS optimization routing problem is to find a set of available multidisjoint paths,P={path1,path2,…,pathn} from the source node to the sink node that satisfies the following objective function:
(12)f:min(fE),min(fD),min(-fR).
This can be rewritten as
(13)min∑p=1npfp×W,
where W is the weight set for the QoS required by an application.The first term in the objective function (12) specifies the energy consumption from data packet transmission; the second term specifies the delay accrued in data transmission, while the third term specifies the reliability of data transmission. Hence, the objective function is to minimize data transmission power in order to extend the network lifetime, minimize the data transmission delay while maximize the data transmission reliability. This function is subject to the following constraints:
(14)min∑fE,fD≤Dreq,fR≥Rreq,min{np},n≥np≥1.


#### 4.2.1. Paths Selection Algorithm

The sink node satisfies an application requirement by selecting path or paths based on the requested QoS and the available paths conditions. After the route discovery begins, the sink collects all the RREQ messages and builds the sink decision table, Table3, from the information received in each message. Algorithm 1 is then used to calculate and sort the cost of each available path according to the QoS class requested in order to select the path with the minimum cost.Table 3
Sink decision table.
Path
E
min
D
path
R
path
Hop
Cost
1
E
min
1
D
path
1
R
path
1
hop
1
Cost
1
2
E
min
2
D
path
2
R
path
2
hop
2
Cost
2
⋮
⋮
⋮
⋮
⋮
⋮
n
E
min
n
D
path
n
R
path
n
hop
n
Cost
nAlgorithm 1:Paths selection algorithm.
for (class = 1;class≤7;class ++)
{
use Table1 to assign
C
E
,
C
D
,
C
R
;
for (p = 1;p≤n;p++)
{
CalculateEpathpusing (1);
Path[p].Cost=EpathpEminp×CE+DpathpDreq×CD+RreqRpathp×CR;
}
Ascending Sort
P
a
t
h
[
p
]
.Cost;        //firstPath[p].Cost is the smallest one and upwards
}


#### 4.2.2. Number of Paths

The number of paths to route data is based on the requested QoS since the selection criteria can be towards different objectives. We think of path failures as Bernoulli distribution. When a path fails, all the messages sent over the path are lost. On the other hand, when a path succeeds all the messages sent on it are successfully received. In MQoSR protocol, the sink uses multipath routing and erasures coding only when the requested QoS in terms of reliability cannot be achieved. Thus, when using multipath routing, the original packet is coded at the source node only to generateM+K coded subpackets before transmitting on the np selected from the n available node-disjoint paths between the source and the sink. The number of paths used to route data in MQoSR protocol can be defined as the routing strategy, T, and presented as
(15)T={npifn≥np≥2,multipathrouting1otherwise,singlepathrouting.
The sink uses the packet reliability, Re2e, to determine the number of multipath, np, using Algorithm 2.Algorithm 2:Select number of used paths.
n= number of available disjoint paths (source to sink)
R
e2e = 1;              //Initialization
n
p = 0;                 //Initialization
for (p
=
1;
p
≤
n;
p++)
{
Re2e=Re2e×(1-Rpathp)//CalculateRe2eaccording to (7)
np = np++;//Add another path to the used paths
if ((1 -Re2e) ≥ Rreq)
{
number of paths to be used = np;
}
break;
}


#### 4.2.3. Traffic Allocation and Data Transmission

Once the sink decides on the number of routing paths,np, to be used, it replies to the source node with the results through RREP messages that travel on the selected disjoint paths. The source node then encodes each data packet using erasure coding to have in total a set of M+K fragments and by receiving M fragments out of these M+K, the original data packet can be reconstructed (Section 3.4). For each data packet M, the parity fragments K are added such that the number of fragments on each path follows xp=⌈(M+K)/np⌉, p=1,2,…,np, and 1≤xp≤M-1. The first paths that have the highest requested QoS level, Algorithm 1, are allocated more fragments than other paths. With such allocation, a high recovery level is achieved since the allocated fragments on any path are less than M. After the selection of np disjoint paths for classes 3, 4, 6, and 7, and after adding coding fragments, the source node can begin sending data to the destination along these paths.


## 4.1. Link-Based Metrics and Next Node Selection

Each sensor node is assumed to update the local states of its one-hop neighbors by broadcasting a HELLO message in which the links conditions are reported. Each node then maintains and updates its neighboring table information to record the link performance between itself and its direct neighbor nodes in terms ofRlink, Dlink, and Eava. Each sensor node knows the distance to its neighbors and to the sink node.


### 4.1.1. Link Cost Function

Geographic routing protocols are efficient in wireless networks [30], geographic routing accomplished based solely on location information of nodes, nodes need to know only the location of their one-hop neighbors, the discovery floods and state propagation are not required, the used memory at each node is minimal, the bandwidth consumption is reduced, the energy is conserved, and the overhead is minimal. All these gains are an important concern for resource-concentrated network like WSNs.To  get benefits from geographic routing and in order to minimize the number of sensor nodes used to route data between source and destination [31], we considered the idea of greedy forwarding as one of the metrics to calculate the link cost function. The sender node searches its neighbors list looking for the neighbor node that is closest to sink, with largest expected progress, while at the same time satisfying the application requirements among all its forwarding candidates. Then, the expected progress of a link can be defined as a link cost, Clink, as follows:
(10)Clink=1(dsx,sink-dsy,sink),
where dsx,sink and dsy,sink are the distance of a sender node sx and a receiver node sy to the sink, respectively. The implicit aim of this strategy is to minimize Clink in order to minimize the hop count between source and destination.However, using greedy forwarding strategy in sensor network may lead to the dead end problem [16], which occurs when a message is forwarded to a node with no neighbor that is closer to the sink than the node that currently has the packet and is called local optimum. Avoiding this problem is a challenging issue for any geographic greedy forwarding approach. Although a dense deployment of wireless nodes can reduce the incidence of this problem in the network, it is still possible for some nodes to experience a local optimum.In the proposed MQoSR, if a sender node does not have any neighbor closer to the sink than itself, the message is forwarded according to the required QoS function only (9).


### 4.1.2. Total Cost Function

The route request phase is started when the source node has data packet to transmit to the sink to which it has no available route by broadcasting a route request message (RREQ, Figure2(a)). Each source node reports the application requirements in terms of Rreq and Dreq in the required QoS field of the RREQ message. Each source node also initializes the values in the path parameters’ field, Dpath, Rpath, and hops to zero, one, and zero, respectively. The source node then broadcasts the RREQ to all its neighbors within its transmission range in which the path parameters are updated along the available paths to the sink. The route discovery phase is, therefore, introduced. Upon receiving the RREQ, each intermediate node selects one node as the next hop from its neighbor list to forward the RREQ depending on the total cost function given in the following:
(11)Ctotal=Clink×Creq,
where Clink is the link cost function and Creq is the cost of the required QoS.RREQ and RREP messages format.
(a)
(b)IfSneig is a set of neighbors of sensor node sx, then the RREQ message will be forwarded to the neighbor whose total cost function is the least (minsi∈sneigCtotal). This node is chosen and is reserved for that path to avoid having paths with shared nodes. However, if the selected node is already reserved, then the next smallest Ctotal node will be selected and so on. The selected node then modifies the path parameters’ field in the RREQ. The path parameters field in RREQ messages is initialized at the source node and updated at each intermediate node as follows. (1)
Compare the node available energy with the value reported inEmin field, Emin is the minimum available energy at a node on any path, and if Eava<Emin, then Emin=Eava; otherwise there is no change. Note that the initial value of Emin is equal to the Eava of source node. Thus, Emin is capturing the minimum reading of energy along the path.(2)
Dpath=Dpath+Dlink.(3)
hop=hop+1.(4)
Rpath=Rpath×Rlink.After receiving all the RREQ messages, the sink estimates the number of all available disjoint paths to the source and obtains information about each path. The sink podcasts the route reply message,RREP (Figure 2(b)), after evaluating the optimal paths as described in Section 4.2.


### 4.1.3. Illustrative Example

To understand the role of next node selection process and to underline the importance of selecting different nodes when different QoS is requested, we illustrate MQoSR with the example in Table2, based on Figure 3 information. Each sensor node is labeled with four attributes as follows: distance to sink, available energy, link delay, and link reliability. When the source node, Sourcein Figure 1, originates a data packet, the RREQ message is broadcasted to all the neighbors of the source node within its transmission range. If a node, say 0, is one of the source neighbor nodes which is located at a distance of ds0,sink=20, from the sink and node 0 initiates the next node selection process to select next node depending on the requested QoS and the available resources, from its list of neighbor nodes 1, 2, 3, 4, and 5.Table 2
Example of next node selection process in MQoSR.
Required QoS
Costs
Node 1
Node 2
Node 3
Node 4
Node 5
Next node minCtotal
Class 1–7
C
link
1
0.5
0.285
0.333
2
Class 1
C
req
100/300 = 0.333
100/200 = 0.5
100/200 = 0.5
100/500 = 0.2
100/400 = 0.25
4
C
total
0.333
0.25
0.142
0.066
0.5
Class 2
C
req
10/120 = 0.083
30/120 = 0.25
40/120 = 0.333
50/120 = 0.416
25/120 = 0.208
C
total
0.083
0.125
0.095
0.138
0.416
1
Class 3
C
req
0.9/0.6 = 1.5
0.9/0.8 = 1.12
0.9/0.4 = 2.25
0.9/0.3 = 3
0.9/0.9 = 1
C
total
1.5
0.562
0.641
0.999
2
2
Class 4
C
req
1.833
1.625
2.75
3.2
1.25
C
total
1.833
0.813
0.784
1.066
2.5
3
Class 5
C
req
0.416
0.75
0.833
0.616
0.458
C
total
0.416
0.375
0.237
0.205
0.916
4
Class 6
C
req
1.583
1.375
2.583
3.416
1.208
C
total
1.583
0.688
0.736
1.138
2.416
2
Class 7
C
req
1.916
1.875
3.083
3.616
1.458
C
total
1.916
0.938
0.879
1.204
2.916
3Figure 3
Next node selection process in MQoSR; each node is labeled with a (ds,sink, Eava, Dlink, Rlink) quadruple.Table2 summarizes the next node selection process introduced in MQoSR protocol; different nodes are selected depending on the requested QoS and the available resource. In Table 2, Rreq, Dreq, and Eava are set to 0.9, 120, and 100, respectively. The link cost function is fixed for each node while the required QoS cost functions are altered based on the QoS classes.


## 4.1.1. Link Cost Function

Geographic routing protocols are efficient in wireless networks [30], geographic routing accomplished based solely on location information of nodes, nodes need to know only the location of their one-hop neighbors, the discovery floods and state propagation are not required, the used memory at each node is minimal, the bandwidth consumption is reduced, the energy is conserved, and the overhead is minimal. All these gains are an important concern for resource-concentrated network like WSNs.To  get benefits from geographic routing and in order to minimize the number of sensor nodes used to route data between source and destination [31], we considered the idea of greedy forwarding as one of the metrics to calculate the link cost function. The sender node searches its neighbors list looking for the neighbor node that is closest to sink, with largest expected progress, while at the same time satisfying the application requirements among all its forwarding candidates. Then, the expected progress of a link can be defined as a link cost, Clink, as follows:
(10)Clink=1(dsx,sink-dsy,sink),
where dsx,sink and dsy,sink are the distance of a sender node sx and a receiver node sy to the sink, respectively. The implicit aim of this strategy is to minimize Clink in order to minimize the hop count between source and destination.However, using greedy forwarding strategy in sensor network may lead to the dead end problem [16], which occurs when a message is forwarded to a node with no neighbor that is closer to the sink than the node that currently has the packet and is called local optimum. Avoiding this problem is a challenging issue for any geographic greedy forwarding approach. Although a dense deployment of wireless nodes can reduce the incidence of this problem in the network, it is still possible for some nodes to experience a local optimum.In the proposed MQoSR, if a sender node does not have any neighbor closer to the sink than itself, the message is forwarded according to the required QoS function only (9).


## 4.1.2. Total Cost Function

The route request phase is started when the source node has data packet to transmit to the sink to which it has no available route by broadcasting a route request message (RREQ, Figure2(a)). Each source node reports the application requirements in terms of Rreq and Dreq in the required QoS field of the RREQ message. Each source node also initializes the values in the path parameters’ field, Dpath, Rpath, and hops to zero, one, and zero, respectively. The source node then broadcasts the RREQ to all its neighbors within its transmission range in which the path parameters are updated along the available paths to the sink. The route discovery phase is, therefore, introduced. Upon receiving the RREQ, each intermediate node selects one node as the next hop from its neighbor list to forward the RREQ depending on the total cost function given in the following:
(11)Ctotal=Clink×Creq,
where Clink is the link cost function and Creq is the cost of the required QoS.RREQ and RREP messages format.
(a)
(b)IfSneig is a set of neighbors of sensor node sx, then the RREQ message will be forwarded to the neighbor whose total cost function is the least (minsi∈sneigCtotal). This node is chosen and is reserved for that path to avoid having paths with shared nodes. However, if the selected node is already reserved, then the next smallest Ctotal node will be selected and so on. The selected node then modifies the path parameters’ field in the RREQ. The path parameters field in RREQ messages is initialized at the source node and updated at each intermediate node as follows. (1)
Compare the node available energy with the value reported inEmin field, Emin is the minimum available energy at a node on any path, and if Eava<Emin, then Emin=Eava; otherwise there is no change. Note that the initial value of Emin is equal to the Eava of source node. Thus, Emin is capturing the minimum reading of energy along the path.(2)
Dpath=Dpath+Dlink.(3)
hop=hop+1.(4)
Rpath=Rpath×Rlink.After receiving all the RREQ messages, the sink estimates the number of all available disjoint paths to the source and obtains information about each path. The sink podcasts the route reply message,RREP (Figure 2(b)), after evaluating the optimal paths as described in Section 4.2.


## 4.1.3. Illustrative Example

To understand the role of next node selection process and to underline the importance of selecting different nodes when different QoS is requested, we illustrate MQoSR with the example in Table2, based on Figure 3 information. Each sensor node is labeled with four attributes as follows: distance to sink, available energy, link delay, and link reliability. When the source node, Sourcein Figure 1, originates a data packet, the RREQ message is broadcasted to all the neighbors of the source node within its transmission range. If a node, say 0, is one of the source neighbor nodes which is located at a distance of ds0,sink=20, from the sink and node 0 initiates the next node selection process to select next node depending on the requested QoS and the available resources, from its list of neighbor nodes 1, 2, 3, 4, and 5.Table 2
Example of next node selection process in MQoSR.
Required QoS
Costs
Node 1
Node 2
Node 3
Node 4
Node 5
Next node minCtotal
Class 1–7
C
link
1
0.5
0.285
0.333
2
Class 1
C
req
100/300 = 0.333
100/200 = 0.5
100/200 = 0.5
100/500 = 0.2
100/400 = 0.25
4
C
total
0.333
0.25
0.142
0.066
0.5
Class 2
C
req
10/120 = 0.083
30/120 = 0.25
40/120 = 0.333
50/120 = 0.416
25/120 = 0.208
C
total
0.083
0.125
0.095
0.138
0.416
1
Class 3
C
req
0.9/0.6 = 1.5
0.9/0.8 = 1.12
0.9/0.4 = 2.25
0.9/0.3 = 3
0.9/0.9 = 1
C
total
1.5
0.562
0.641
0.999
2
2
Class 4
C
req
1.833
1.625
2.75
3.2
1.25
C
total
1.833
0.813
0.784
1.066
2.5
3
Class 5
C
req
0.416
0.75
0.833
0.616
0.458
C
total
0.416
0.375
0.237
0.205
0.916
4
Class 6
C
req
1.583
1.375
2.583
3.416
1.208
C
total
1.583
0.688
0.736
1.138
2.416
2
Class 7
C
req
1.916
1.875
3.083
3.616
1.458
C
total
1.916
0.938
0.879
1.204
2.916
3Figure 3
Next node selection process in MQoSR; each node is labeled with a (ds,sink, Eava, Dlink, Rlink) quadruple.Table2 summarizes the next node selection process introduced in MQoSR protocol; different nodes are selected depending on the requested QoS and the available resource. In Table 2, Rreq, Dreq, and Eava are set to 0.9, 120, and 100, respectively. The link cost function is fixed for each node while the required QoS cost functions are altered based on the QoS classes.


## 4.2. Path-Based Metrics and End-to-End QoS

The process of selecting the routing paths, the number of these paths, and the allocation strategy of data packet on each route are related to the end-to-end application requirements and are decided on at the sink side.In general, the multi-QoS optimization routing problem is to find a set of available multidisjoint paths,P={path1,path2,…,pathn} from the source node to the sink node that satisfies the following objective function:
(12)f:min(fE),min(fD),min(-fR).
This can be rewritten as
(13)min∑p=1npfp×W,
where W is the weight set for the QoS required by an application.The first term in the objective function (12) specifies the energy consumption from data packet transmission; the second term specifies the delay accrued in data transmission, while the third term specifies the reliability of data transmission. Hence, the objective function is to minimize data transmission power in order to extend the network lifetime, minimize the data transmission delay while maximize the data transmission reliability. This function is subject to the following constraints:
(14)min∑fE,fD≤Dreq,fR≥Rreq,min{np},n≥np≥1.


### 4.2.1. Paths Selection Algorithm

The sink node satisfies an application requirement by selecting path or paths based on the requested QoS and the available paths conditions. After the route discovery begins, the sink collects all the RREQ messages and builds the sink decision table, Table3, from the information received in each message. Algorithm 1 is then used to calculate and sort the cost of each available path according to the QoS class requested in order to select the path with the minimum cost.Table 3
Sink decision table.
Path
E
min
D
path
R
path
Hop
Cost
1
E
min
1
D
path
1
R
path
1
hop
1
Cost
1
2
E
min
2
D
path
2
R
path
2
hop
2
Cost
2
⋮
⋮
⋮
⋮
⋮
⋮
n
E
min
n
D
path
n
R
path
n
hop
n
Cost
nAlgorithm 1:Paths selection algorithm.
for (class = 1;class≤7;class ++)
{
use Table1 to assign
C
E
,
C
D
,
C
R
;
for (p = 1;p≤n;p++)
{
CalculateEpathpusing (1);
Path[p].Cost=EpathpEminp×CE+DpathpDreq×CD+RreqRpathp×CR;
}
Ascending Sort
P
a
t
h
[
p
]
.Cost;        //firstPath[p].Cost is the smallest one and upwards
}


### 4.2.2. Number of Paths

The number of paths to route data is based on the requested QoS since the selection criteria can be towards different objectives. We think of path failures as Bernoulli distribution. When a path fails, all the messages sent over the path are lost. On the other hand, when a path succeeds all the messages sent on it are successfully received. In MQoSR protocol, the sink uses multipath routing and erasures coding only when the requested QoS in terms of reliability cannot be achieved. Thus, when using multipath routing, the original packet is coded at the source node only to generateM+K coded subpackets before transmitting on the np selected from the n available node-disjoint paths between the source and the sink. The number of paths used to route data in MQoSR protocol can be defined as the routing strategy, T, and presented as
(15)T={npifn≥np≥2,multipathrouting1otherwise,singlepathrouting.
The sink uses the packet reliability, Re2e, to determine the number of multipath, np, using Algorithm 2.Algorithm 2:Select number of used paths.
n= number of available disjoint paths (source to sink)
R
e2e = 1;              //Initialization
n
p = 0;                 //Initialization
for (p
=
1;
p
≤
n;
p++)
{
Re2e=Re2e×(1-Rpathp)//CalculateRe2eaccording to (7)
np = np++;//Add another path to the used paths
if ((1 -Re2e) ≥ Rreq)
{
number of paths to be used = np;
}
break;
}


### 4.2.3. Traffic Allocation and Data Transmission

Once the sink decides on the number of routing paths,np, to be used, it replies to the source node with the results through RREP messages that travel on the selected disjoint paths. The source node then encodes each data packet using erasure coding to have in total a set of M+K fragments and by receiving M fragments out of these M+K, the original data packet can be reconstructed (Section 3.4). For each data packet M, the parity fragments K are added such that the number of fragments on each path follows xp=⌈(M+K)/np⌉, p=1,2,…,np, and 1≤xp≤M-1. The first paths that have the highest requested QoS level, Algorithm 1, are allocated more fragments than other paths. With such allocation, a high recovery level is achieved since the allocated fragments on any path are less than M. After the selection of np disjoint paths for classes 3, 4, 6, and 7, and after adding coding fragments, the source node can begin sending data to the destination along these paths.


## 4.2.1. Paths Selection Algorithm

The sink node satisfies an application requirement by selecting path or paths based on the requested QoS and the available paths conditions. After the route discovery begins, the sink collects all the RREQ messages and builds the sink decision table, Table3, from the information received in each message. Algorithm 1 is then used to calculate and sort the cost of each available path according to the QoS class requested in order to select the path with the minimum cost.Table 3
Sink decision table.
Path
E
min
D
path
R
path
Hop
Cost
1
E
min
1
D
path
1
R
path
1
hop
1
Cost
1
2
E
min
2
D
path
2
R
path
2
hop
2
Cost
2
⋮
⋮
⋮
⋮
⋮
⋮
n
E
min
n
D
path
n
R
path
n
hop
n
Cost
nAlgorithm 1:Paths selection algorithm.
for (class = 1;class≤7;class ++)
{
use Table1 to assign
C
E
,
C
D
,
C
R
;
for (p = 1;p≤n;p++)
{
CalculateEpathpusing (1);
Path[p].Cost=EpathpEminp×CE+DpathpDreq×CD+RreqRpathp×CR;
}
Ascending Sort
P
a
t
h
[
p
]
.Cost;        //firstPath[p].Cost is the smallest one and upwards
}


## 4.2.2. Number of Paths

The number of paths to route data is based on the requested QoS since the selection criteria can be towards different objectives. We think of path failures as Bernoulli distribution. When a path fails, all the messages sent over the path are lost. On the other hand, when a path succeeds all the messages sent on it are successfully received. In MQoSR protocol, the sink uses multipath routing and erasures coding only when the requested QoS in terms of reliability cannot be achieved. Thus, when using multipath routing, the original packet is coded at the source node only to generateM+K coded subpackets before transmitting on the np selected from the n available node-disjoint paths between the source and the sink. The number of paths used to route data in MQoSR protocol can be defined as the routing strategy, T, and presented as
(15)T={npifn≥np≥2,multipathrouting1otherwise,singlepathrouting.
The sink uses the packet reliability, Re2e, to determine the number of multipath, np, using Algorithm 2.Algorithm 2:Select number of used paths.
n= number of available disjoint paths (source to sink)
R
e2e = 1;              //Initialization
n
p = 0;                 //Initialization
for (p
=
1;
p
≤
n;
p++)
{
Re2e=Re2e×(1-Rpathp)//CalculateRe2eaccording to (7)
np = np++;//Add another path to the used paths
if ((1 -Re2e) ≥ Rreq)
{
number of paths to be used = np;
}
break;
}


## 4.2.3. Traffic Allocation and Data Transmission

Once the sink decides on the number of routing paths,np, to be used, it replies to the source node with the results through RREP messages that travel on the selected disjoint paths. The source node then encodes each data packet using erasure coding to have in total a set of M+K fragments and by receiving M fragments out of these M+K, the original data packet can be reconstructed (Section 3.4). For each data packet M, the parity fragments K are added such that the number of fragments on each path follows xp=⌈(M+K)/np⌉, p=1,2,…,np, and 1≤xp≤M-1. The first paths that have the highest requested QoS level, Algorithm 1, are allocated more fragments than other paths. With such allocation, a high recovery level is achieved since the allocated fragments on any path are less than M. After the selection of np disjoint paths for classes 3, 4, 6, and 7, and after adding coding fragments, the source node can begin sending data to the destination along these paths.


## 5. Simulation Setup and Performance Metrics

In this section, we present our simulation setup for MQoSR protocol, followed by the performance metrics and comparisons.


### 5.1. Simulation Setup

We have conducted an extensive simulation study using C++ to evaluate the performance of our protocol for various QoS requirements. We compare our proposed MQoSR protocol with the MCMP model [24], which also considers multiconstraint QoS routing and shows its performance to be better than similar other protocols. Also, we compare our proposed protocol with higher achievable performances of an ideal QoS routing protocol, God routing [25, 32] in which each node is aware of the direct links delay and reliability and uses multipath routing based on this knowledge. A fair comparison can only be achieved with careful selection of simulation parameters and by using similar simulation parameters used in evaluation [24, 32], we ensure that our results are directly comparable to those published previously. At higher node densities, the likelihood of finding node-disjoint paths increases [33]. Thus, in order to increase the probability of finding these paths to evaluate the performance of our proposed protocol, we consider a network where 80 to 250 nodes are randomly scattered in a field of 200 m × 200 m area. We assume that all sensor nodes are static after deployment with transmission range of 40 m. The simulation parameters used are as follows. Simulation time is set to 1000 sec and the size of a data packet is 128 bytes with a fixed generation rate of 1 packet/sec. Thus, the total number of data packets transmitted through simulation, pkttotal, is 1000. et=er=90 nJ/bit, εamp=10 pJ/(bit·m2). Source nodes are picked randomly and the position of the sink is fixed in the top left side of the simulation area. To evaluate the worst case where link delay and reliability change suddenly at any transmission instant, link reliability and delay are randomly distributed. Links’ reliability is uniformly distributed in the range of [0.8,0.9], and the delay is in the range of [1,50] ms. Simulation results are obtained from different configurations and multiple runs to reduce the effect of the position of sensors, and the results shown are averaged over 10 simulation runs.


### 5.2. Performance Metrics

The following performance metrics are used to evaluate MQoSR protocol.(1)
Probability of successful transmission is the probability of packets achieving the reliability requirements (8).(2)
Probability of packets received on time is the probability of packets achieving the delay requirements.(3)
Data delivery ratio is the percentage of the packets sent by the source nodes and received by the sink (5).(4)
Average end-to-end delay per node for each transmission is the period of time that packet takes to reach the sink:(16)Average  end-to-end  delay=totalend-to-enddelay(numberofpacketsreceived×numberofnodes).(5)
Average energy consumption per transmission is the index of the network lifetime; less energy consumption per transmission indicates more network lifetime. Network lifetime is given in terms of when the energy of a first node drops under the energy threshold:(17)Averageenergyconsumption=totalenergyconsumptionnumberofpacketsreceived.(6)
Average routing overhead is the average number of routing packets transmitted to deliver a data packet; each hop transmission is counted as one routing packet. This is an index of the energy efficiency; more messages transmitted to deliver the data packet indicate higher energy consumption:(18)Averageroutingoverhead=(∑j=1j=pktsource∑p=1nphopjp)pkttotal.We begin by examining the effects of the proposed seven QoS for different requirements in terms of reliability and delay using the same values as in Table2, and the number of network nodes is set to 250. To highlight the ability of MQoSR protocol to distinguish services in the reliability domain, Figure 4 compares the probability of achieved reliability and the average energy consumption for the classes 3, 4, 6, and 7 that considered reliability as a metric. An average delay requirement of 90 ms is used. Figure 4 indicates that more than 87% of total packets sent by all sensor nodes in the network achieved the requested reliability for the high-reliability requirements and 100% achieved for low-reliability requirements. Note that, multipath routing is used and the number of these paths is related to the requested reliability. Thus, the energy consumption is increased when reliability requirement increases.Figure 4
Probability of achieved reliability and average energy consumption versus requested reliability.To distinguish services in the timeline domain, Figure5 illustrates the end-to-end probability of packet received on time and the average energy consumption per transmission for all the classes (classes 2, 5, 6, and 7) that considered delay as a metric; requested reliability of 0.7 is used. The end-to-end delay requirements are achieved up to 84% for the application with strict delay requirements and up to 99% for the application with a relaxed delay requirement. Note that for classes 6 and 7, the energy consumption per transmission is higher than the other classes since reliability is also considered as metric in these classes, and this reflects the energy consumption in the network.Figure 5
Probability of packet received on time and average energy consumption per transmission versus requested delay.Next, we change the number of network nodes and measure the resulting effects on the end-to-end delay, data delivery ratio, network lifetime, and routing overhead. Figure6 shows that the average end-to-end delay per packet for all the classes that considered the delay in MQoSR (classes 2, 5, 6, and 7). As expected, routing for the proposed classes with delay metric have much lowest average delay than that of the MCMP protocol. Note that God routing achieved the lower end-to-end delay per transmission. On the other hand, all the delay classes in the proposed MQoSR protocol fulfill the delay requirements of 90 msec.Figure 6
Average end-to-end delay per transmission versus number of nodes.Figure7 illustrates the data delivery ratio achieved for various number of nodes for the classes that consider the reliability metric in MQoSR compared with MCMP and God routing protocols. MQoSR outperforms the data delivery ratio for that of MCMP protocol and reached about 100% delivery ratio similar to God routing. In MQoSR, erasure coding is used to route data on multipath, and the selection strategy of links and paths is toward increasing reliability only or reliability combined with other required QoS.Figure 7
Data delivery ratio versus number of nodes.The average network lifetime obtained in the network for different number of nodes using the classes that consider energy as a metric (classes 1, 4, 5, and 7) is illustrated in Figure8. It is clear that MQoSR protocol highly outperforms the MCMP and God routing protocols in terms of decreasing energy consumption at the network towards extending the network lifetime. This is due to the fact that in MCMP protocol, the data packet is transmitted on more paths than in our MQoSR protocol. In MQoSR, erasure coding is used; therefore, data packet is split on the used paths. While in God routing protocol, the next node selection process decides on links with the least delays or maximum reliability, possibly including nodes with low available energy; thus, the same node transmits more packets hereafter the network lifetime depletes earlier. However, the next node selection process used in MQoSR for classes 1, 4, 5, and 7 chooses the next node with the maximum available energy and with the highest progress to destination as well as the path selection process decides on paths with the maximum available energy of its nodes and the minimum energy consumption among other paths; this energy conservation strategy, that is followed by the proposed MQoSR protocol, results in extending the lifetime of network nodes.Figure 8
Average network lifetime versus number of nodes.The routing overhead of transmissions per data packet is presented in Figure9. Classes 1, 2, and 5 in MQoSR protocol introduce low routing overhead, similar to God routing, since these classes use a single path routing and the selection process of links and paths is toward decreasing delay and/or energy combined with the minimum distance to destination. Classes 1 and 5 in MQoSR show an average routing overhead slightly less than that of God routing since links and paths selection strategies for these classes are elaborated in decreasing the number of nodes involved in routing to extend the lifetime of the network. However, the multipath routing classes in MQoSR, classes 3, 4, 6, and 7, introduce a higher routing overhead than God routing, but still gain more advantage than MCMP protocol. This is due to the fact that the number of routing paths used in MQoSR protocol is less than that of MCMP protocol which in turn reflects the communication overhead.Figure 9
Average routing overhead,N=250.


## 5.1. Simulation Setup

We have conducted an extensive simulation study using C++ to evaluate the performance of our protocol for various QoS requirements. We compare our proposed MQoSR protocol with the MCMP model [24], which also considers multiconstraint QoS routing and shows its performance to be better than similar other protocols. Also, we compare our proposed protocol with higher achievable performances of an ideal QoS routing protocol, God routing [25, 32] in which each node is aware of the direct links delay and reliability and uses multipath routing based on this knowledge. A fair comparison can only be achieved with careful selection of simulation parameters and by using similar simulation parameters used in evaluation [24, 32], we ensure that our results are directly comparable to those published previously. At higher node densities, the likelihood of finding node-disjoint paths increases [33]. Thus, in order to increase the probability of finding these paths to evaluate the performance of our proposed protocol, we consider a network where 80 to 250 nodes are randomly scattered in a field of 200 m × 200 m area. We assume that all sensor nodes are static after deployment with transmission range of 40 m. The simulation parameters used are as follows. Simulation time is set to 1000 sec and the size of a data packet is 128 bytes with a fixed generation rate of 1 packet/sec. Thus, the total number of data packets transmitted through simulation, pkttotal, is 1000. et=er=90 nJ/bit, εamp=10 pJ/(bit·m2). Source nodes are picked randomly and the position of the sink is fixed in the top left side of the simulation area. To evaluate the worst case where link delay and reliability change suddenly at any transmission instant, link reliability and delay are randomly distributed. Links’ reliability is uniformly distributed in the range of [0.8,0.9], and the delay is in the range of [1,50] ms. Simulation results are obtained from different configurations and multiple runs to reduce the effect of the position of sensors, and the results shown are averaged over 10 simulation runs.


## 5.2. Performance Metrics

The following performance metrics are used to evaluate MQoSR protocol.(1)
Probability of successful transmission is the probability of packets achieving the reliability requirements (8).(2)
Probability of packets received on time is the probability of packets achieving the delay requirements.(3)
Data delivery ratio is the percentage of the packets sent by the source nodes and received by the sink (5).(4)
Average end-to-end delay per node for each transmission is the period of time that packet takes to reach the sink:(16)Average  end-to-end  delay=totalend-to-enddelay(numberofpacketsreceived×numberofnodes).(5)
Average energy consumption per transmission is the index of the network lifetime; less energy consumption per transmission indicates more network lifetime. Network lifetime is given in terms of when the energy of a first node drops under the energy threshold:(17)Averageenergyconsumption=totalenergyconsumptionnumberofpacketsreceived.(6)
Average routing overhead is the average number of routing packets transmitted to deliver a data packet; each hop transmission is counted as one routing packet. This is an index of the energy efficiency; more messages transmitted to deliver the data packet indicate higher energy consumption:(18)Averageroutingoverhead=(∑j=1j=pktsource∑p=1nphopjp)pkttotal.We begin by examining the effects of the proposed seven QoS for different requirements in terms of reliability and delay using the same values as in Table2, and the number of network nodes is set to 250. To highlight the ability of MQoSR protocol to distinguish services in the reliability domain, Figure 4 compares the probability of achieved reliability and the average energy consumption for the classes 3, 4, 6, and 7 that considered reliability as a metric. An average delay requirement of 90 ms is used. Figure 4 indicates that more than 87% of total packets sent by all sensor nodes in the network achieved the requested reliability for the high-reliability requirements and 100% achieved for low-reliability requirements. Note that, multipath routing is used and the number of these paths is related to the requested reliability. Thus, the energy consumption is increased when reliability requirement increases.Figure 4
Probability of achieved reliability and average energy consumption versus requested reliability.To distinguish services in the timeline domain, Figure5 illustrates the end-to-end probability of packet received on time and the average energy consumption per transmission for all the classes (classes 2, 5, 6, and 7) that considered delay as a metric; requested reliability of 0.7 is used. The end-to-end delay requirements are achieved up to 84% for the application with strict delay requirements and up to 99% for the application with a relaxed delay requirement. Note that for classes 6 and 7, the energy consumption per transmission is higher than the other classes since reliability is also considered as metric in these classes, and this reflects the energy consumption in the network.Figure 5
Probability of packet received on time and average energy consumption per transmission versus requested delay.Next, we change the number of network nodes and measure the resulting effects on the end-to-end delay, data delivery ratio, network lifetime, and routing overhead. Figure6 shows that the average end-to-end delay per packet for all the classes that considered the delay in MQoSR (classes 2, 5, 6, and 7). As expected, routing for the proposed classes with delay metric have much lowest average delay than that of the MCMP protocol. Note that God routing achieved the lower end-to-end delay per transmission. On the other hand, all the delay classes in the proposed MQoSR protocol fulfill the delay requirements of 90 msec.Figure 6
Average end-to-end delay per transmission versus number of nodes.Figure7 illustrates the data delivery ratio achieved for various number of nodes for the classes that consider the reliability metric in MQoSR compared with MCMP and God routing protocols. MQoSR outperforms the data delivery ratio for that of MCMP protocol and reached about 100% delivery ratio similar to God routing. In MQoSR, erasure coding is used to route data on multipath, and the selection strategy of links and paths is toward increasing reliability only or reliability combined with other required QoS.Figure 7
Data delivery ratio versus number of nodes.The average network lifetime obtained in the network for different number of nodes using the classes that consider energy as a metric (classes 1, 4, 5, and 7) is illustrated in Figure8. It is clear that MQoSR protocol highly outperforms the MCMP and God routing protocols in terms of decreasing energy consumption at the network towards extending the network lifetime. This is due to the fact that in MCMP protocol, the data packet is transmitted on more paths than in our MQoSR protocol. In MQoSR, erasure coding is used; therefore, data packet is split on the used paths. While in God routing protocol, the next node selection process decides on links with the least delays or maximum reliability, possibly including nodes with low available energy; thus, the same node transmits more packets hereafter the network lifetime depletes earlier. However, the next node selection process used in MQoSR for classes 1, 4, 5, and 7 chooses the next node with the maximum available energy and with the highest progress to destination as well as the path selection process decides on paths with the maximum available energy of its nodes and the minimum energy consumption among other paths; this energy conservation strategy, that is followed by the proposed MQoSR protocol, results in extending the lifetime of network nodes.Figure 8
Average network lifetime versus number of nodes.The routing overhead of transmissions per data packet is presented in Figure9. Classes 1, 2, and 5 in MQoSR protocol introduce low routing overhead, similar to God routing, since these classes use a single path routing and the selection process of links and paths is toward decreasing delay and/or energy combined with the minimum distance to destination. Classes 1 and 5 in MQoSR show an average routing overhead slightly less than that of God routing since links and paths selection strategies for these classes are elaborated in decreasing the number of nodes involved in routing to extend the lifetime of the network. However, the multipath routing classes in MQoSR, classes 3, 4, 6, and 7, introduce a higher routing overhead than God routing, but still gain more advantage than MCMP protocol. This is due to the fact that the number of routing paths used in MQoSR protocol is less than that of MCMP protocol which in turn reflects the communication overhead.Figure 9
Average routing overhead,N=250.


## 6. Conclusion

In this paper, different classes of QoS are modeled to provide multiobjective QoS routing in WSNs to deal with diverse requirements by different applications under various network constraints. The proposed scheme integrates multicriteria for routing decision by partitioning the requested QoS into two subnetworks cost metrics: the sensor nodes cost metric where the link condition and available resources at each intermediate sensor node are collectively used to direct the data packet along the most appropriate links toward the sink and the path cost metric where the end-to-end metrics are calculated to achieve the requirements while minimizing the overall network resource consumption. The strength of the MQoSR protocol lies in the fact that the sensor nodes and the sink change their routing policy according to the current QoS requirements by an application.We evaluate the performance of the proposed protocol under different scenarios, and the results confirm that MQoSR protocol that takes into account variations of the link weights in selecting a single path or multipath can satisfy the application requirements in terms of reliability and delay in an energy-efficient way. Furthermore, MQoSR highly outperforms the MCMP and God routing protocols proposed in the literature in terms of energy consumption, data delivery, average end-to-end delay, and routing overhead.As a future extension to this work, we plan to apply MQoSR protocol to mobile wireless networks and to evaluate the optimum set of probabilities for the per-hop QoS-aware priority scheduling with respect to the seven proposed classes of QoS.



---

*Source: 495803-2013-06-04.xml*