# QPRD: QoS-Aware Peering Routing Protocol for Delay-Sensitive Data in Hospital Body Area Network

Authors: Zahoor A. Khan; Shyamala Sivakumar; William Phillips; Bill Robertson; Nadeem Javaid
Journal: Mobile Information Systems
 (2015)

---

## Abstract

Consistent performance, energy efficiency, and reliable transfer of data are critical factors for real-time monitoring of a patient’s data, especially in a hospital environment. In this paper, a routing protocol is proposed by considering the QoS requirements of the Body Area Network (BAN) data packets. A mechanism for handling delay-sensitive packets is provided by this protocol. Moreover, linear programming based modeling along with graphical analysis is also done. Extensive simulations using the OMNeT++ based simulator Castalia 3.2 illustrate that the proposed algorithm provides better performance than other QoS-aware routing protocols in terms of higher successful transmission rates (throughputs), lower overall network traffic, no packets dropped due to MAC buffer overflow, and fewer numbers of packet time outs in both the mobile and static patient scenarios. The scalability of the protocol is demonstrated by simulating a 24-bed real hospital environment with 49 nodes. It is shown that, even in the larger real hospital scenario requiring the transmission of delay-sensitive data packets with stringent delay requirements, QPRD outperforms comparable protocols.


---

## Body

## 1. Introduction

A patient’s real-time health-related data monitoring is possible with the help of a new emerging field, Body Area Networks (BANs). Body Area Network is a small wireless network which consists of sensors placed inside or outside of the human body. The body implant or wearable sensors transmit the data to a central device called Body Area Network Coordinator (BANC). BANC is computationally more powerful device then the body sensors. BANC is responsible for transferring the sensors’ data to the next node or destination reliably.Some important issues of BAN data transmission are to ensure the high reliability, low latency, compatibility with movable sensors, and low energy consumption. The specific need of BAN communication is not fulfilled by the existing Personal Area Network (PAN) standards [1]. IEEE task group 6 was assigned a job in November 2007 to suggest a BAN communication standard 802.15.6 by the consideration of short range transmission, reliability and latency requirements of QoS, and less energy consumption [2]. The real-time monitoring of patients requires the transmission of delay-sensitive data such as video imaging, motion sensing, and Electromyography (EMG) using BAN. Some projects like SMART [3], CareNet [4], AID-N [5], and ALARM-NET [6] provide different methods to monitor the patient data. In these methods, the transmission of BAN data from body sensors to the central database is considered and then BAN data is downloaded and monitored from the central database. However, these techniques do not monitor or display in real-time BAN data in hospital environment. The advantages of using a centralized system are to have better control and maintain the data privacy of the patient. However, traffic congestion, server failure, or link failure can cause considerable delays in monitoring the patient data which can badly affect treatment. On the other hand, distributed data approaches help to reduce the traffic load and can better accommodate patient mobility. The ZK-BAN peering framework proposed in [7] suggests a semicentralized system for reliably monitoring BAN data. The hybrid ZK-BAN uses both centralized and distributed techniques.The routing protocols EPR, proposed and discussed in [7], resolves the problem of handling ordinary data packets. The QoS-aware peering routing protocol for reliability-sensitive data (QPRR) [8, 9] provides a mechanism of handling the reliability-sensitive packets in addition to the ordinary data packets. The requirement of real-time display for delay-sensitive packets is different from those of ordinary and reliability-sensitive packets. Hence, a new QoS-aware routing protocol is required to handle delay-sensitive packets. A novel routing protocol that addresses the issue of handling delay-sensitive data and displaying in real-time delay-sensitive BAN data is proposed in this paper. The proposed QoS-aware peering routing protocol for delay-sensitive packets (QPRD) is designed for the ZK-BAN peering framework discussed in [7]. QPRD provides an innovative approach to the reliable transmission of ordinary packets (OPs) and delay-sensitive packets (DSPs). The initial results and architecture of QPRD were presented in IEEE conference proceedings [10].This paper is organized as follows: Section2 provides the related work; Section 3 discusses the problem formulation and modeling; Section 4 provides the proposed QoS-aware peering routing protocol for delay-sensitive data (QPRD); Section 5 describes the performance evaluation; Section 6 discusses the scalability test of QPRD and Section 7 presents the conclusions.


## 2. Related Work

A smart monitoring system of BAN data in hospital environment can resolve the challenges related to the management of patients’ medical information [11]. The Scalable Medical Alert and Response Technology (SMART) [3] is designed to monitor the patient’s data in hospital emergency area. The data from sensors is transferred to the PDA and then the PDA sends it to the next tier by using wireless standard 802.11b. CareNet [4] provides an integrated wireless sensor based solution to monitor the patient’s data from remote hospitals. The two-tier wireless communication is used in the projects [3, 4]. A GPS system is used in [5] to monitor the patient’s data only in outdoor BAN communication. A wireless sensor network for assisted-living and residential monitoring system with a query based protocol is provided in ALARM-NET [6]. A three-tier communication approach is used in [12] to store the BAN data on the server and then make this data available for the physician to analyze the patient’s data. The projects [3–6, 12] used a centralized approach to monitor the patient’s data. However, the real-time display of data by considering the delay requirements of delay-sensitive packets is not considered. To access the data from a centralized server may cause delay and even a simple link failure can completely disconnect the healthcare system from the central server.In [7], an energy-aware peering routing protocol (EPR) was presented which considers the energy level and geographic information of the neighbor nodes for choosing the best next hop. The EPR only considers ordinary packets. It was shown that EPR has an overall lower energy consumption than comparable protocols [11, 13–16] and provides better results in terms of reduced overall network traffic, reduced number of packets forwarded by intermediate nodes, and higher successful data transmission rates. However, EPR does not provide a mechanism for dealing with delay-sensitive packets (DSPs). In this paper, delay-sensitive packets are considered by the proposed QoS-aware peering routing protocol for delay-sensitive data (QPRD) and their performance is investigated by comparing it to the existing DMQoS protocol [13]. In [13], DMQoS categorizes the data packets into four types: ordinary packets (OPs), critical packets (CPs), reliability-driven packets (RPs), and delay-driven packets (DPs). The DMQoS [13] provides better results for delay-driven packets than several previously investigated methods [11, 14–16] in terms of end-to-end path delay. However, DMQoS employs ahop-by-hop approach to determine the next hop. DMQoS considers the neighbor device with the lowest delay, and the next hop then determines the best next upstream hop with least delay. The disadvantage of thishop-by-hop delay-driven approach employed in DMQoS is that only neighboring nodes delay information is considered by source node. The source node forwards the packet to a particular neighbor node which has lower node delay than the required delay. The neighbor node sends the acknowledgement of the successfully received packet to the source node. Now, the packet receiving neighbor node determines its best upstream node in terms of delay requirement and forwards the packet to the upstream node if the node delay of upstream node is less than the required delay. In case the neighbor node does not find any upstream node with node delay less than required delay, then the packet is dropped. In this case, the packet does not reach the destination, but the source node assumes that the packet has been successfully received by the destination. Furthermore, thehop-by-hop approach used in DMQoS causes an increase in overall network traffic, and the required end-to-end latency may not be guaranteed. In this paper, the proposed QPRD addresses these shortcomings by selecting and choosing the next hop device based on the lowest end-to-end path delay from the source node to the destination.


## 3. Problem Formulation and Modeling

The motivation that BAN consists of nodes connected with each other via wireless links leads us to model it as a directed graph. This section focuses on two points: (i) to maximize throughput, and (ii) to minimize the end-to-end delay. These two problems are modeled via linear programming [17, 18] because requirements to these problems could easily be represented by linear relationships.


### 3.1. Throughput Maximization

We consider BAN as a directed graphG
=
(
S
,
L
), S
=
s, and L
=
l; S is the set of nodes and L is the set of directed graphs (links). If the network operations are divided into rounds, each round r is the duration from the network establishment till the death of all nodes; then linear programming based mathematical formulation for throughput maximization is as follows:(1)
Max
⁡
⁡
∑
r
T
r
,
∀
r
∈
R
,where(2)
T
r
=
∑
i
l
i
,
Dst
·
T
i
,
Dst
∀
i
∈
S
,
(3)
l
i
,
Dst
=
1
if packet delivery is guaranteed
0
otherwisesuch that(4a)
B
≤
B
max
⁡
,
(4b)
∑
i
E
i
≤
E
0
,
∀
i
∈
S
,
(4c)
∑
i
DL
path
i
,
Dst
≤
∑
i
t
out
i
,
Dst
,
∀
i
∈
S
,
(4d)
∑
i
d
i
,
Dst
≤
∑
i
R
i
t
x
,
∀
i
∈
S
,
(4e)
∑
i
f
i
-
1
,
i
+
∑
i
λ
i
t
≤
∑
i
f
i
,
Dst
,
∀
i
∈
S
.The objective function in (1) aims to maximize throughput T during each round r such that (2) associates packet delivery from source i to destination Dst with link flag l. Equation (3) provides details about the status of l being raised (l
=
1) if packet delivery through that link is guaranteed else not (l
=
0). Constraint in (4a) provides the upper bound for the allocated bandwidth B as B
max
⁡. Similarly, constraint in (4b) deals with limited energy constraint; that is, each node i is equipped with an energy source E
i such that ∑
i
E
i is upper bounded by E
0. Node ceases transmission whenever its battery is drained out, so, energy efficient utilization is very important (routing and MAC layer protocols play a critical role here). Constraint in (4c) comes into consideration if and only if ∃
m
/
P
∈
P
QoS; m path(s) out of total P satisfies the given quality of service P
QoS where DLpath is the end-to-end delay and t
out is the timeout period. This means that, as a first priority, QoS needs to be satisfied. Afterwards, if there is more than one QoS path, then as a second priority end-to-end delay is checked. Transmission range R
t
x constraint in (4d) demonstrates that packet delivery is successful if a source node transmits data to an in-range destination node where d
(
i
,
Dst
) is the distance between source and destination. For data generation rate λ, (4e) constraint entails flow conservation such that the incoming data flow f
(
i
-
1
,
i
) plus the data generated during time t should not exceed the outgoing data flow f
(
i
,
Dst
). Violation of (4c), (4d), and (4e) leads to packets being dropped which ultimately results in decreased throughput.


### 3.2. Delay Minimization

The delay minimization problem, while routing dynamically such that path for each request is selected to prevent routing latency for future demands, is addressed here. The linear programming problem is formulated as follows:(5)
Min
⁡
⁡
∑
i
DL
path
i
,
Dst
,
∀
i
∈
S
,where(6)
DL
path
i
,
Dst
=
DL
node
i
+
DL
path
j
,
Dst
j
≠
Dst
DL
node
i
j
=
Dst,
(7)
DL
node
i
=
DL
trans
⁡
i
+
DL
queue
+
channel
+
DL
proc
,
∀
i
∈
Ssuch that (8a)
l
path
i
,
Dst
=
1
,
∀
i
∈
S
,
(8b)
R
bit
≤
R
bit
max
⁡
,
(8c)
∑
t
=
1
t
max
⁡
n
≤
n
cap
,
(8d)
∑
i
λ
i
arrival
<
∑
i
λ
i
departure
,
∀
i
∈
S
,
(8e)
0
≤
∑
i
node
i
≤
s
,
∀
i
∈
S
,
(8f)
N
bit
e
≤
N
bit
proc
.The objective function in (5) aims to minimize the end-to-end path delay DL
path
(
i
,
Dst
), where (6) depicts the two possible cases: communication via intermediate node and without intermediate node, and (7) defines the node delay D
L
node
(
i
) calculated at the network layer as the addition of packet delays due to transmission D
L
trans
⁡
(
i
), queuing DLqueue, channel capturing DLchannel, and processing DLproc. Constraint (8a) clearly says that the link through which data is routed must be established where l
path is the link flag. Constraint in (8b) provides the upper bound of data rate R
bit as R
bit
max
⁡ such that R
bit is inversely proportional to DL
trans
⁡ according to (15) explained in later Section 4.4. Constraint in (8c) says that the number of transmitted packets n in 4 seconds (t
max
⁡
=
4 sec) should not exceed the packet handling capacity n
cap because, at negligible load, there is constant small delay. However, queuing delays on each node are added as soon as the network load increases and when n exceeds n
cap delays increase without bound. Similarly, constraint in (8d) deals with queue stability meaning that the packet arrival rate λ
i
arrival should be always less than the packet departure rate λ
i
departure. Violation of (8d) results in nonavailability of buffer space leading to queue instability which in turn leads to congestion and thus causing increased delay. Constraint in (8e) states that the total number of nodes ∑
i
‍
node
(
i
) in the given network is limited such that i has an inverse relation with DLchannel. In other words, increasing the number of nodes means that there are more chances that one of the noncapturing nodes might have a lower backoff time as compared to that of the capturing node, thereby increasing the idle time due the backing off of noncapturing nodes. Constraint in (8f) deals with DLproc. It is obvious that the total bit level errors N
bit
e should not exceed a certain threshold N
bit
proc; otherwise increased erroneous bits would increase DLproc and performance of the network would degrade in terms of processing delays at the nodes.


### 3.3. Graphical Analysis

Consider the simplified pathB
3
-
B
1
-NSC where B
3 can directly send data to NSC as well as via B
1 (refer to Figure 3 in Section 4.4). Moreover, NSC can also send data to itself. For typically assumed delay values, path delay is maximum when B
1 is involved in forwarding the data of B
3 intended for the destination NSC (i.e., 50 ms), and path delay is minimum when B
3 directly communicates with NSC (i.e., 20 ms). Let z
=
DL
path
(
i
,
Dst
), x
=
DL
node
(
i
), and y
=
DL
path
(
j
,
Dst
). The objective function in (5) can be reformulated as(9)
Min
⁡
⁡
z
,where (10)
z
=
x
+
ysuch that (11a)
x
+
y
≥
20
,
(11b)
x
+
y
≤
50
,
(11c)
0
≤
x
≤
20
,
0
≤
y
≤
30
.The objective function in (9) aims to minimize end-to-end delay regarding the selected path, whereas (10) illustrates nature of the objective function, that is, two-dimensional linear programming problem. Constraints in (11a) and (11b) provide lower and upper bounds for the selected path, respectively, whereas constraint in (11c) deals with similar bounds for x as well as y. For simplicity in calculation, we replace the inequalities in (11a), (11b), and (11c) with equalities, respectively. In subject to the given constraints, Figure 1 shows the set of feasible solutions which is obtained by the intersection of lines, L
1, L
2, L
3, and L
4, and is indicated by coloured region such that each point in the feasible region satisfies each constraint. We can find the minimum value of z by testing it at each of the vertices (refer to P
1, P
2, P
3, and P
4 in Figure 1) as follows:atP
1
(
0,0
): z
=
0 ms,
atP
2
(
20,0
): z
=
20
+
0
=
20 ms,
atP
3
(
0,30
): z
=
0
+
30
=
30 ms,
atP
4
(
20,30
): z
=
20
+
30
=
50 ms.Figure 1
Feasible region.The minimum value ofz is 0 ms at x
=
0 and y
=
0. However, this value indicates self transmission or communication within NSC. The next minimum value is z
=
20 ms showing the case of direct communication between B
3 and NSC. Similarly, z
=
30 ms when B
1 directly communicates with NSC. On the other hand, end-to-end path delay is maximum when B
3 communicates with NSC via an intermediate B
1; z
=
50 ms.


## 3.1. Throughput Maximization

We consider BAN as a directed graphG
=
(
S
,
L
), S
=
s, and L
=
l; S is the set of nodes and L is the set of directed graphs (links). If the network operations are divided into rounds, each round r is the duration from the network establishment till the death of all nodes; then linear programming based mathematical formulation for throughput maximization is as follows:(1)
Max
⁡
⁡
∑
r
T
r
,
∀
r
∈
R
,where(2)
T
r
=
∑
i
l
i
,
Dst
·
T
i
,
Dst
∀
i
∈
S
,
(3)
l
i
,
Dst
=
1
if packet delivery is guaranteed
0
otherwisesuch that(4a)
B
≤
B
max
⁡
,
(4b)
∑
i
E
i
≤
E
0
,
∀
i
∈
S
,
(4c)
∑
i
DL
path
i
,
Dst
≤
∑
i
t
out
i
,
Dst
,
∀
i
∈
S
,
(4d)
∑
i
d
i
,
Dst
≤
∑
i
R
i
t
x
,
∀
i
∈
S
,
(4e)
∑
i
f
i
-
1
,
i
+
∑
i
λ
i
t
≤
∑
i
f
i
,
Dst
,
∀
i
∈
S
.The objective function in (1) aims to maximize throughput T during each round r such that (2) associates packet delivery from source i to destination Dst with link flag l. Equation (3) provides details about the status of l being raised (l
=
1) if packet delivery through that link is guaranteed else not (l
=
0). Constraint in (4a) provides the upper bound for the allocated bandwidth B as B
max
⁡. Similarly, constraint in (4b) deals with limited energy constraint; that is, each node i is equipped with an energy source E
i such that ∑
i
E
i is upper bounded by E
0. Node ceases transmission whenever its battery is drained out, so, energy efficient utilization is very important (routing and MAC layer protocols play a critical role here). Constraint in (4c) comes into consideration if and only if ∃
m
/
P
∈
P
QoS; m path(s) out of total P satisfies the given quality of service P
QoS where DLpath is the end-to-end delay and t
out is the timeout period. This means that, as a first priority, QoS needs to be satisfied. Afterwards, if there is more than one QoS path, then as a second priority end-to-end delay is checked. Transmission range R
t
x constraint in (4d) demonstrates that packet delivery is successful if a source node transmits data to an in-range destination node where d
(
i
,
Dst
) is the distance between source and destination. For data generation rate λ, (4e) constraint entails flow conservation such that the incoming data flow f
(
i
-
1
,
i
) plus the data generated during time t should not exceed the outgoing data flow f
(
i
,
Dst
). Violation of (4c), (4d), and (4e) leads to packets being dropped which ultimately results in decreased throughput.


## 3.2. Delay Minimization

The delay minimization problem, while routing dynamically such that path for each request is selected to prevent routing latency for future demands, is addressed here. The linear programming problem is formulated as follows:(5)
Min
⁡
⁡
∑
i
DL
path
i
,
Dst
,
∀
i
∈
S
,where(6)
DL
path
i
,
Dst
=
DL
node
i
+
DL
path
j
,
Dst
j
≠
Dst
DL
node
i
j
=
Dst,
(7)
DL
node
i
=
DL
trans
⁡
i
+
DL
queue
+
channel
+
DL
proc
,
∀
i
∈
Ssuch that (8a)
l
path
i
,
Dst
=
1
,
∀
i
∈
S
,
(8b)
R
bit
≤
R
bit
max
⁡
,
(8c)
∑
t
=
1
t
max
⁡
n
≤
n
cap
,
(8d)
∑
i
λ
i
arrival
<
∑
i
λ
i
departure
,
∀
i
∈
S
,
(8e)
0
≤
∑
i
node
i
≤
s
,
∀
i
∈
S
,
(8f)
N
bit
e
≤
N
bit
proc
.The objective function in (5) aims to minimize the end-to-end path delay DL
path
(
i
,
Dst
), where (6) depicts the two possible cases: communication via intermediate node and without intermediate node, and (7) defines the node delay D
L
node
(
i
) calculated at the network layer as the addition of packet delays due to transmission D
L
trans
⁡
(
i
), queuing DLqueue, channel capturing DLchannel, and processing DLproc. Constraint (8a) clearly says that the link through which data is routed must be established where l
path is the link flag. Constraint in (8b) provides the upper bound of data rate R
bit as R
bit
max
⁡ such that R
bit is inversely proportional to DL
trans
⁡ according to (15) explained in later Section 4.4. Constraint in (8c) says that the number of transmitted packets n in 4 seconds (t
max
⁡
=
4 sec) should not exceed the packet handling capacity n
cap because, at negligible load, there is constant small delay. However, queuing delays on each node are added as soon as the network load increases and when n exceeds n
cap delays increase without bound. Similarly, constraint in (8d) deals with queue stability meaning that the packet arrival rate λ
i
arrival should be always less than the packet departure rate λ
i
departure. Violation of (8d) results in nonavailability of buffer space leading to queue instability which in turn leads to congestion and thus causing increased delay. Constraint in (8e) states that the total number of nodes ∑
i
‍
node
(
i
) in the given network is limited such that i has an inverse relation with DLchannel. In other words, increasing the number of nodes means that there are more chances that one of the noncapturing nodes might have a lower backoff time as compared to that of the capturing node, thereby increasing the idle time due the backing off of noncapturing nodes. Constraint in (8f) deals with DLproc. It is obvious that the total bit level errors N
bit
e should not exceed a certain threshold N
bit
proc; otherwise increased erroneous bits would increase DLproc and performance of the network would degrade in terms of processing delays at the nodes.


## 3.3. Graphical Analysis

Consider the simplified pathB
3
-
B
1
-NSC where B
3 can directly send data to NSC as well as via B
1 (refer to Figure 3 in Section 4.4). Moreover, NSC can also send data to itself. For typically assumed delay values, path delay is maximum when B
1 is involved in forwarding the data of B
3 intended for the destination NSC (i.e., 50 ms), and path delay is minimum when B
3 directly communicates with NSC (i.e., 20 ms). Let z
=
DL
path
(
i
,
Dst
), x
=
DL
node
(
i
), and y
=
DL
path
(
j
,
Dst
). The objective function in (5) can be reformulated as(9)
Min
⁡
⁡
z
,where (10)
z
=
x
+
ysuch that (11a)
x
+
y
≥
20
,
(11b)
x
+
y
≤
50
,
(11c)
0
≤
x
≤
20
,
0
≤
y
≤
30
.The objective function in (9) aims to minimize end-to-end delay regarding the selected path, whereas (10) illustrates nature of the objective function, that is, two-dimensional linear programming problem. Constraints in (11a) and (11b) provide lower and upper bounds for the selected path, respectively, whereas constraint in (11c) deals with similar bounds for x as well as y. For simplicity in calculation, we replace the inequalities in (11a), (11b), and (11c) with equalities, respectively. In subject to the given constraints, Figure 1 shows the set of feasible solutions which is obtained by the intersection of lines, L
1, L
2, L
3, and L
4, and is indicated by coloured region such that each point in the feasible region satisfies each constraint. We can find the minimum value of z by testing it at each of the vertices (refer to P
1, P
2, P
3, and P
4 in Figure 1) as follows:atP
1
(
0,0
): z
=
0 ms,
atP
2
(
20,0
): z
=
20
+
0
=
20 ms,
atP
3
(
0,30
): z
=
0
+
30
=
30 ms,
atP
4
(
20,30
): z
=
20
+
30
=
50 ms.Figure 1
Feasible region.The minimum value ofz is 0 ms at x
=
0 and y
=
0. However, this value indicates self transmission or communication within NSC. The next minimum value is z
=
20 ms showing the case of direct communication between B
3 and NSC. Similarly, z
=
30 ms when B
1 directly communicates with NSC. On the other hand, end-to-end path delay is maximum when B
3 communicates with NSC via an intermediate B
1; z
=
50 ms.


## 4. QoS-Aware Peering Routing Protocol for Delay-Sensitive Data (QPRD)

Based on the mathematical analysis in Section3, the proposed QoS-aware routing protocol used in an indoor hospital ZK-BAN peering framework [7] is discussed in this section. The proposed QPRD provides a mechanism to (
1
) calculate the node delays and path delays of all possible paths from the source node to the destination, (
2
) determine the best path, and (
3
) choose the best next hop NH
D based on the delay requirements of the packet. For each destination, the routing table contains information about the next hop device connected to the path with the least end-to-end latency. For any DSP, if the path delay (DL
path
(
i
,
Dst
)) is less than or equal to the delay requirement, the source node sends the DSP through that path.The architecture of proposed QPRD, based on the mathematical formulation of the end-to-end path delay problem, is shown in Figure2. It consists of seven modules: MAC receiver, delay module (DM), packet classifier (PC), Hello protocol module (HPM), routing services module (RSM), QoS-aware queuing module (QQM), and MAC transmitter. The modules are discussed below.Figure 2
QPRD protocol architecture.Figure 3
Example of finding the path delay.


### 4.1. MAC Receiver

The MAC receiver receives the data or Hello packets from other nodes (BAN, MDC, or NSC). It checks the MAC address of the packet. It only forwards the broadcast packets or the packets which have the same node’s MAC address as destination address to the network layer.


### 4.2. Delay Module (DM)

The delay module monitors the time required to capture the channel (DL
channel
(
i
)), MAC layer queuing delay (DL
MAC_queue
(
i
)), and transmission time (DL
trans
⁡
(
i
)) of a packet. The delay module sends this information to the network layer. The network layer uses this information to calculate the node delay (DL
node(
i
)).


### 4.3. Packet Classifier (PC)

The packet classifier (PC) receives all the packets from the MAC receiver. The data packets and Hello packets are differentiated by the PC. The PC forwards the data and Hello packets to the routing services module and Hello protocol module, respectively.


### 4.4. Hello Protocol Module (HPM)

The neighbor table constructor and the neighbor table are the two submodules of Hello protocol module. The information received from the delay module of the MAC layer and the Hello packets is used by the neighbor table constructor to construct the neighbor table. Initially, Hello packets are broadcasted by each of type 1 (NSC) and type 2 (MDC) devices. The nodei receives the Hello packet. The neighbor table constructor of node i calculates its own DL
path
(
i
,
Dst
) based on the information in the Hello packets. The Hello packet is updated and forwarded by node i to the other nodes. The Hello packet fields of node j are shown as follows.Hello Packet Structure. Consider(12)
ID
Dst
L
Dst
ID
j
L
j
D
j
,
Dst
E
j
T
j
DL
path
j
,
DstThe commonly used notations in this paper and their descriptions are summarized in notations section.The neighbor table contains fields for both hop-by-hop delay (DL
node
(
i
)) and end-to-end path delay (DL
path
(
i
,
Dst
)). The neighbor table constructor updates the neighbor table periodically after receiving every new Hello packet. The neighbor table structure of node i is shown as follows.The Neighbor Table Structure. Consider(13)
ID
Dst
L
Dst
ID
j
L
j
D
j
,
Dst
D
i
,
j
C
j
T
j
DL
node
i
DL
path
i
,
DstThe node delay (D
L
n
o
d
e
(
i
)) can be found by adding the packet delays due to transmission, queuing, processing, and channel capturing:(14)
DL
node
i
=
DL
trans
⁡
i
+
DL
queues
+
channel
+
DL
proc
.The node updates its Hello packets periodically; 4 seconds are used in QPRD for simulation purposes. The time interval 4 seconds is used because the delay module sends the delays of MAC queue and channel capture after every 4 seconds. The average transmission delay (D
L
t
r
a
n
s) before sending the Hello packets is calculated by using (15)
DL
trans
⁡
=
1
R
bit
∑
z
=
1
n
N
bit
z
n
,where R
bit is the data rate and as per BAN requirement 250 kbps is used in the simulations. N
bit is the total number of bits in each packet. n is the number of packets transmitted in 4 seconds.The delay due to the MAC and network layers’ queues and capturing the channel can be calculated by using the Exponentially Weighted Moving Average (EWMA) formula and is given in(16)
DL
queues
+
channel
=
1
-
ρ
∗
DL
queues
+
channel
+
ρ
∗
DL
queues
+
channel
,where queues are both network and MAC layers’ queues.Initial values ofDL
queues
+
channel are the delay of the first packet sent by the node. ρ is the average weighting factor that satisfies 0
<
ρ
≤
1. The selection of ρ value is heuristic and was chosen based on simulations experience. The recommended values are 0.2
≤
ρ
≤
0.3. The best suited value of ρ found for QPRD simulations is 0.2.The path delay between nodei and destination node Dst (D
L
path
(
i
,
Dst
)) is calculated by using (17)
DL
path
i
,
Dst
=
DL
node
i
+
DL
path
j
,
Dst
,where initial value of D
L
p
a
t
h
j
,
D
s
t is zero when j
=
Dst.An example of finding the path delay from nodei (B
3) to Dst (NSC) is shown in Figure 3. The delay calculation of two paths B
3
-
B
1
-
M
D
C
2
-NSC (path 1) and B
3
-
M
D
C
3
-
B
2
-
M
D
C
1
-NSC (path 2) is given for illustrative purposes. The typical assumed values are chosen for illustrated purposes. The individual node delays used in this example are given below:(18a)
DL
node
NSC
=
20
ms
,
(18b)
DL
node
MDC
2
=
40
ms
,
(18c)
DL
node
B
1
=
30
ms
,
(18d)
DL
node
B
3
=
20
ms
,
(18e)
DL
node
MD
C
1
=
20
ms
,
(18f)
DL
node
B
2
=
30
ms
,
(18g)
DL
node
MD
C
3
=
10
ms
.The path delay of destination (D
L
path
(
Dst
,
Dst
)) is approximately zero, because the time required to receive the packet from MAC to network layer is negligible. So, in this example initial path delay is given below:(19)
DL
path
NSC
,
NSC
=
0
ms
.Each node calculates the path delay from itself to the NSC. First, the calculations of the path delay for path 1 (B
3
-
B
1
-
M
D
C
2
-NSC) are considered.The path delay of MDC2 (DL
path
(
MDC
2
,
NSC
)) is calculated by using (17):(20)
DL
path
MDC
2
,
NSC
=
DL
node
MDC
2
+
DL
path
NSC
,
NSC
.Using the values from (18a) and (19) in the above equation, we get(21)
DL
path
MDC
2
,
NSC
=
40
+
0
=
40
ms
.The path delay of BAN B
1 is calculated below:(22)
DL
path
B
1
,
NSC
=
DL
node
B
1
+
DL
path
MDC
2
,
NSC
,
DL
path
B
1
,
NSC
=
30
+
40
=
70
ms
.The node B
3 determines the path delay by using the values from (18d) and (22):(23)
DL
path
B
3
,
NSC
=
DL
node
B
3
+
DL
path
B
1
,
NSC
,
DL
path
B
3
,
NSC
=
20
+
70
=
90
ms
.In the same manner, the path delay of path 2 (B
3
-
M
D
C
3
-
B
2
-
M
D
C
1
-NSC) can be calculated as follows:(24)
DL
path
M
D
C
1
,
NSC
=
20
+
0
=
20
ms
,
DL
path
B
2
,
NSC
=
30
+
20
=
50
ms
,
DL
path
M
D
C
3
,
NSC
=
10
+
50
=
60
ms
,
DL
path
B
3
,
NSC
=
20
+
60
=
80
ms
.Equations (23) and (24) show that the path delays of path 1 and path 2 are 90 ms and 80 ms, respectively. It is quite possible that the path with less delay is longer (has more hops) than the other paths. As it is observed from the above example, path 2 includes five devices and path 1 has four devices. However, the path delay of path 2 is lower than the path delay of path 1.


### 4.5. Routing Services Module (RSM)

The routing services module is responsible for constructing the routing table, categorizing the data packets into delay-sensitive packets (DSPs) and ordinary packets (OPs). It also chooses the best path(s) for each category (DSPs or OPs) of traffic. QoS classifier, routing table constructor, path selector, and routing table are the submodules of routing services module. The routing table structure for nodei is shown as follows.The Routing Table Structure for QPRD. Consider(25)
ID
Dst
L
Dst
NH
E
NH
D
DL
path
i
,
DstThe notations and their descriptions are listed in notation section. Two next hop entries N
H
E and NH
D are given for each destination Dst in routing table. The routing table constructor contains the energy-aware and delay algorithms. The energy-aware algorithm discussed in [7] is used to find next hop N
H
E for OPs. Residual energy and geographic location of the neighbor nodes are considered for choosing N
H
E. For DSPs, the new proposed algorithm finds the best possible path to ensure the minimum required path delay. The routing table is constructed by using the neighbor table entries. Neighbor table contains multiple records for each destination. For example, Figure 3 shows that there are many paths from B
3 to NSC. Some of these paths are B
3
-
B
1
-
MDC
2
-NSC, B
3
-
M
D
C
3
-
B
2
-
MDC
1
-NSC, and so forth. For each destination, the routing table constructor stores the next hop (NH
D) which has the lowest latency.Algorithm1 shows that node i identifies the next hop candidates by searching the records which have the same IDDst in the neighbor table. The path delay has been calculated by using the neighbor table constructor and stored in neighbor table for each next hop candidate, using (17). The node stores the neighbor nodes’ IDs in the variable NH (line 2). If NH has only one entry, this means there is only one path available. The node stores this entry to NH
D (line 4).Algorithm 1:Routing table construction algorithm for delay-sensitive packets.
INPUT:  Neighbor table, i’s neighbor table records NH
(
i
,Dst
), ∀Dst ∈
{
MDC, NSC, BAN
}
(1)
for  each destination Dst ∈
{
NSC, MDC, BAN
}  do
(2)  NH = All neighbor nodes
j
∈
NH
(
i
,Dst)
(3)  if  (|
NH
|
=
=
1)  then
(4) NH
D
←
NH
(5) else if  (|
NH
|
>
1)  then
(6) Sort NH in ascending order of DL
path(
i
,Dst)
(7) NH
D = first neighbor node j
∈
NH;
(8)  end if
(9)
end forOtherwise, the node sorts the NH entries in ascending order of delay and then stores the first entry which has the lowest path delay inNH
D (lines 6-7). The next hop candidate NH
D is then stored with its path delay value (DL
path
(
i
,
Dst
)) in the routing table. The data packets from both upper layers and packet classifier are received by QoS classifier. The QoS classifier classifies the packets into DSP and OP data. For each data packet, the path selector (PS) checks the QoS requirement and chooses the most appropriate next hop(s) by using Algorithm 2.Algorithm 2:Path selector algorithm for delay-sensitive packets.
INPUT:Routing table, i’s routing table records NH
i
,
Dst, ∀Dst ∈
{
MDC, NSC, BAN
}
(1)
for each data packet do
(2)  if data packet is delay-sensitive packet (DSP)
(3) if (DL
path(
i
,Dst)
≤
DL
req) then
(4)   send to NH
D
(5) else
(6) Drop the packet immediately
(7) end if
(8)else if data packet is Ordinary Packet (OP)
(9) send to NH
E
(10)
else
(11)   drop the packet immediately
(12)
end if
(13)end forThe path selector compares the delay requirement (DLreq) with the path delay (DL
path
(
i
,
Dst
)) of NH
D which is stored in the routing table. If the path delay (DL
path
(
i
,
Dst
)) is lower than required delay (DLreq), the packet is sent to NH
D (lines 3-4). Otherwise, the packet is dropped (line 6).For ordinary packets, the PS returns the next hopN
H
E which is discussed by the EPR (lines 8-9); else the packet is dropped.


### 4.6. QoS-Aware Queuing Module (QQM)

The routing services module passes the data packets to the QoS-aware queuing module (QQM) after choosing the appropriate next hop(s). The QQM receives the data packets and separates these packets in two classes (DSP and OP). An individual queue is used for each class of packets. QQM functions are the same as discussed in [13]. The priority of the DSP queue is higher than that of the OP queue. By default, the DSP queue with higher priority sends the packets first. The packets from lower priority OP queue will be sent only when the DSP queue is empty. However, for fair treatment of OP data, a timeout is used by all the queues. A queue sends the packets to the MAC layer within the period specified by the timeout for that queue. QQM changes the control from higher priority queue to lower priority queue after the queue timeout occurs or when the higher priority queue is empty whichever is earlier.


### 4.7. MAC Transmitter

The MAC transmitter receives the data and Hello packets from the network layer and stores it in the queue. The queue works in a First-In-First-Out (FIFO) fashion. It transmits the packets after capturing the channel by using CSMA/CA algorithm.


## 4.1. MAC Receiver

The MAC receiver receives the data or Hello packets from other nodes (BAN, MDC, or NSC). It checks the MAC address of the packet. It only forwards the broadcast packets or the packets which have the same node’s MAC address as destination address to the network layer.


## 4.2. Delay Module (DM)

The delay module monitors the time required to capture the channel (DL
channel
(
i
)), MAC layer queuing delay (DL
MAC_queue
(
i
)), and transmission time (DL
trans
⁡
(
i
)) of a packet. The delay module sends this information to the network layer. The network layer uses this information to calculate the node delay (DL
node(
i
)).


## 4.3. Packet Classifier (PC)

The packet classifier (PC) receives all the packets from the MAC receiver. The data packets and Hello packets are differentiated by the PC. The PC forwards the data and Hello packets to the routing services module and Hello protocol module, respectively.


## 4.4. Hello Protocol Module (HPM)

The neighbor table constructor and the neighbor table are the two submodules of Hello protocol module. The information received from the delay module of the MAC layer and the Hello packets is used by the neighbor table constructor to construct the neighbor table. Initially, Hello packets are broadcasted by each of type 1 (NSC) and type 2 (MDC) devices. The nodei receives the Hello packet. The neighbor table constructor of node i calculates its own DL
path
(
i
,
Dst
) based on the information in the Hello packets. The Hello packet is updated and forwarded by node i to the other nodes. The Hello packet fields of node j are shown as follows.Hello Packet Structure. Consider(12)
ID
Dst
L
Dst
ID
j
L
j
D
j
,
Dst
E
j
T
j
DL
path
j
,
DstThe commonly used notations in this paper and their descriptions are summarized in notations section.The neighbor table contains fields for both hop-by-hop delay (DL
node
(
i
)) and end-to-end path delay (DL
path
(
i
,
Dst
)). The neighbor table constructor updates the neighbor table periodically after receiving every new Hello packet. The neighbor table structure of node i is shown as follows.The Neighbor Table Structure. Consider(13)
ID
Dst
L
Dst
ID
j
L
j
D
j
,
Dst
D
i
,
j
C
j
T
j
DL
node
i
DL
path
i
,
DstThe node delay (D
L
n
o
d
e
(
i
)) can be found by adding the packet delays due to transmission, queuing, processing, and channel capturing:(14)
DL
node
i
=
DL
trans
⁡
i
+
DL
queues
+
channel
+
DL
proc
.The node updates its Hello packets periodically; 4 seconds are used in QPRD for simulation purposes. The time interval 4 seconds is used because the delay module sends the delays of MAC queue and channel capture after every 4 seconds. The average transmission delay (D
L
t
r
a
n
s) before sending the Hello packets is calculated by using (15)
DL
trans
⁡
=
1
R
bit
∑
z
=
1
n
N
bit
z
n
,where R
bit is the data rate and as per BAN requirement 250 kbps is used in the simulations. N
bit is the total number of bits in each packet. n is the number of packets transmitted in 4 seconds.The delay due to the MAC and network layers’ queues and capturing the channel can be calculated by using the Exponentially Weighted Moving Average (EWMA) formula and is given in(16)
DL
queues
+
channel
=
1
-
ρ
∗
DL
queues
+
channel
+
ρ
∗
DL
queues
+
channel
,where queues are both network and MAC layers’ queues.Initial values ofDL
queues
+
channel are the delay of the first packet sent by the node. ρ is the average weighting factor that satisfies 0
<
ρ
≤
1. The selection of ρ value is heuristic and was chosen based on simulations experience. The recommended values are 0.2
≤
ρ
≤
0.3. The best suited value of ρ found for QPRD simulations is 0.2.The path delay between nodei and destination node Dst (D
L
path
(
i
,
Dst
)) is calculated by using (17)
DL
path
i
,
Dst
=
DL
node
i
+
DL
path
j
,
Dst
,where initial value of D
L
p
a
t
h
j
,
D
s
t is zero when j
=
Dst.An example of finding the path delay from nodei (B
3) to Dst (NSC) is shown in Figure 3. The delay calculation of two paths B
3
-
B
1
-
M
D
C
2
-NSC (path 1) and B
3
-
M
D
C
3
-
B
2
-
M
D
C
1
-NSC (path 2) is given for illustrative purposes. The typical assumed values are chosen for illustrated purposes. The individual node delays used in this example are given below:(18a)
DL
node
NSC
=
20
ms
,
(18b)
DL
node
MDC
2
=
40
ms
,
(18c)
DL
node
B
1
=
30
ms
,
(18d)
DL
node
B
3
=
20
ms
,
(18e)
DL
node
MD
C
1
=
20
ms
,
(18f)
DL
node
B
2
=
30
ms
,
(18g)
DL
node
MD
C
3
=
10
ms
.The path delay of destination (D
L
path
(
Dst
,
Dst
)) is approximately zero, because the time required to receive the packet from MAC to network layer is negligible. So, in this example initial path delay is given below:(19)
DL
path
NSC
,
NSC
=
0
ms
.Each node calculates the path delay from itself to the NSC. First, the calculations of the path delay for path 1 (B
3
-
B
1
-
M
D
C
2
-NSC) are considered.The path delay of MDC2 (DL
path
(
MDC
2
,
NSC
)) is calculated by using (17):(20)
DL
path
MDC
2
,
NSC
=
DL
node
MDC
2
+
DL
path
NSC
,
NSC
.Using the values from (18a) and (19) in the above equation, we get(21)
DL
path
MDC
2
,
NSC
=
40
+
0
=
40
ms
.The path delay of BAN B
1 is calculated below:(22)
DL
path
B
1
,
NSC
=
DL
node
B
1
+
DL
path
MDC
2
,
NSC
,
DL
path
B
1
,
NSC
=
30
+
40
=
70
ms
.The node B
3 determines the path delay by using the values from (18d) and (22):(23)
DL
path
B
3
,
NSC
=
DL
node
B
3
+
DL
path
B
1
,
NSC
,
DL
path
B
3
,
NSC
=
20
+
70
=
90
ms
.In the same manner, the path delay of path 2 (B
3
-
M
D
C
3
-
B
2
-
M
D
C
1
-NSC) can be calculated as follows:(24)
DL
path
M
D
C
1
,
NSC
=
20
+
0
=
20
ms
,
DL
path
B
2
,
NSC
=
30
+
20
=
50
ms
,
DL
path
M
D
C
3
,
NSC
=
10
+
50
=
60
ms
,
DL
path
B
3
,
NSC
=
20
+
60
=
80
ms
.Equations (23) and (24) show that the path delays of path 1 and path 2 are 90 ms and 80 ms, respectively. It is quite possible that the path with less delay is longer (has more hops) than the other paths. As it is observed from the above example, path 2 includes five devices and path 1 has four devices. However, the path delay of path 2 is lower than the path delay of path 1.


## 4.5. Routing Services Module (RSM)

The routing services module is responsible for constructing the routing table, categorizing the data packets into delay-sensitive packets (DSPs) and ordinary packets (OPs). It also chooses the best path(s) for each category (DSPs or OPs) of traffic. QoS classifier, routing table constructor, path selector, and routing table are the submodules of routing services module. The routing table structure for nodei is shown as follows.The Routing Table Structure for QPRD. Consider(25)
ID
Dst
L
Dst
NH
E
NH
D
DL
path
i
,
DstThe notations and their descriptions are listed in notation section. Two next hop entries N
H
E and NH
D are given for each destination Dst in routing table. The routing table constructor contains the energy-aware and delay algorithms. The energy-aware algorithm discussed in [7] is used to find next hop N
H
E for OPs. Residual energy and geographic location of the neighbor nodes are considered for choosing N
H
E. For DSPs, the new proposed algorithm finds the best possible path to ensure the minimum required path delay. The routing table is constructed by using the neighbor table entries. Neighbor table contains multiple records for each destination. For example, Figure 3 shows that there are many paths from B
3 to NSC. Some of these paths are B
3
-
B
1
-
MDC
2
-NSC, B
3
-
M
D
C
3
-
B
2
-
MDC
1
-NSC, and so forth. For each destination, the routing table constructor stores the next hop (NH
D) which has the lowest latency.Algorithm1 shows that node i identifies the next hop candidates by searching the records which have the same IDDst in the neighbor table. The path delay has been calculated by using the neighbor table constructor and stored in neighbor table for each next hop candidate, using (17). The node stores the neighbor nodes’ IDs in the variable NH (line 2). If NH has only one entry, this means there is only one path available. The node stores this entry to NH
D (line 4).Algorithm 1:Routing table construction algorithm for delay-sensitive packets.
INPUT:  Neighbor table, i’s neighbor table records NH
(
i
,Dst
), ∀Dst ∈
{
MDC, NSC, BAN
}
(1)
for  each destination Dst ∈
{
NSC, MDC, BAN
}  do
(2)  NH = All neighbor nodes
j
∈
NH
(
i
,Dst)
(3)  if  (|
NH
|
=
=
1)  then
(4) NH
D
←
NH
(5) else if  (|
NH
|
>
1)  then
(6) Sort NH in ascending order of DL
path(
i
,Dst)
(7) NH
D = first neighbor node j
∈
NH;
(8)  end if
(9)
end forOtherwise, the node sorts the NH entries in ascending order of delay and then stores the first entry which has the lowest path delay inNH
D (lines 6-7). The next hop candidate NH
D is then stored with its path delay value (DL
path
(
i
,
Dst
)) in the routing table. The data packets from both upper layers and packet classifier are received by QoS classifier. The QoS classifier classifies the packets into DSP and OP data. For each data packet, the path selector (PS) checks the QoS requirement and chooses the most appropriate next hop(s) by using Algorithm 2.Algorithm 2:Path selector algorithm for delay-sensitive packets.
INPUT:Routing table, i’s routing table records NH
i
,
Dst, ∀Dst ∈
{
MDC, NSC, BAN
}
(1)
for each data packet do
(2)  if data packet is delay-sensitive packet (DSP)
(3) if (DL
path(
i
,Dst)
≤
DL
req) then
(4)   send to NH
D
(5) else
(6) Drop the packet immediately
(7) end if
(8)else if data packet is Ordinary Packet (OP)
(9) send to NH
E
(10)
else
(11)   drop the packet immediately
(12)
end if
(13)end forThe path selector compares the delay requirement (DLreq) with the path delay (DL
path
(
i
,
Dst
)) of NH
D which is stored in the routing table. If the path delay (DL
path
(
i
,
Dst
)) is lower than required delay (DLreq), the packet is sent to NH
D (lines 3-4). Otherwise, the packet is dropped (line 6).For ordinary packets, the PS returns the next hopN
H
E which is discussed by the EPR (lines 8-9); else the packet is dropped.


## 4.6. QoS-Aware Queuing Module (QQM)

The routing services module passes the data packets to the QoS-aware queuing module (QQM) after choosing the appropriate next hop(s). The QQM receives the data packets and separates these packets in two classes (DSP and OP). An individual queue is used for each class of packets. QQM functions are the same as discussed in [13]. The priority of the DSP queue is higher than that of the OP queue. By default, the DSP queue with higher priority sends the packets first. The packets from lower priority OP queue will be sent only when the DSP queue is empty. However, for fair treatment of OP data, a timeout is used by all the queues. A queue sends the packets to the MAC layer within the period specified by the timeout for that queue. QQM changes the control from higher priority queue to lower priority queue after the queue timeout occurs or when the higher priority queue is empty whichever is earlier.


## 4.7. MAC Transmitter

The MAC transmitter receives the data and Hello packets from the network layer and stores it in the queue. The queue works in a First-In-First-Out (FIFO) fashion. It transmits the packets after capturing the channel by using CSMA/CA algorithm.


## 5. Performance Evaluation

Simulations are performed on OMNeT++ based simulator Castalia 3.2 [19]. In this section, the proposed QPRD algorithm is compared with the DMQoS [13] and noRouting protocols. In noRouting, the delay-sensitive data packets are forwarded to random next hop devices instead of algorithm’s next hop based on end-to-end path delay routes. The network parameters used in simulations are shown in Table 1.Table 1
Parameters information.
Deployment
Area
Scenarios 1 and 2: 9 m by 9 m
Scenario 3: 21 m× 16 m
Deployment type
Scenario 1: all nodes are static
Scenario 2: movable source node B4
Scenario 3: hospital environment
Number of nodes
Scenarios 1 and 2: 8 nodes (4 BANs, 3 MDCs, 1 NSC)
Scenario 3: 49 nodes (24 BANs, 24 MDCs, 1 NSC)
Initial nodes locations
Scenarios 1 and 2: NSC(0,3),
MDC1(2,5), MDC2(2,1), MDC3(3,3)
B1(5,5), B2(5,1), B3(6,3), B4(9,3)
Scenario 3: shown in Figure8
Initial node energy
18720 J (= 2 AA batteries)
Buffer size
32 packets
Link layer trans. rate
250 Kbps
Transmit power
−25 dBm
Task
Application type
Event-driven
Max. packet size
32 bytes
Traffic type
CBR (Constant Bit Rate)
MAC
IEEE 802.15.4
Default values
Simulation
Time
2003 seconds
(3 seconds are setup time. Simulation results are the average of three rotations.)Three scenarios are considered for simulation. All the nodes used in scenario 1 are static, whereas the source nodeB
4 is moving in scenario 2. Scenario 3 is used for the scalability test of the protocol. The transmit power used in the simulations is −25 dBm. The performance of the QPRD is measured by calculating the throughput, number of packets forwarded by the intermediate nodes, overall network traffic, packets timeout due to not fulfilling the required delay condition, and packets dropped due to the buffer overflow. The better results provided by QPRD are in accordance with the equations used in Section 4. The higher throughput is due to the use of objective function in QPRD, as described in (1), and the least violations of (4c), (4d), and (4e). The simulation results show that the end-to-end path delay mechanism, as discussed in Sections 3.2 and 4.4, used in QPRD helps to reduce the packets forwarded by intermediate nodes and the packets dropped due to the buffer overflow, which results in higher throughput and lower overall network traffic. To achieve a 97% confidence interval for the illustrative results, the average of three runs is simulated in every experiment which may introduce a maximum error of 3
×
10
-
3, based on the error calculation done by Castalia 3.2 simulator [20]. The results obtained for first two scenarios are discussed below.


### 5.1. Scenario 1: Static Nodes

Figure4 shows the deployment of the experimental network for scenario 1. All the nodes are static in this scenario. The type 1 devices (BANCs: B
1, B
2, B
3, and B
4) are considered as source nodes, and type 2 devices (NSC and MDCs) are the destination nodes. B
1 sends packets to MDC1, B
2 sends packets to MDC2, B
3 sends packets to MDC3, and B
4 sends packets to NSC. The data of B
4 has to go through the other devices to reach NSC. The source nodes send a total of 20 k delay-sensitive packets. The throughput, packets forwarded by intermediate nodes, overall network traffic, number of packets timeout, packets dropped due to MAC buffer overflow, and overall energy consumption are calculated after every 1000 packets until 4 k and then every 4000 packets sent by all BANCs.Figure 4
Node deployment for scenario 1.From Figure5(a), it is seen that QPRD consistently provides throughput of 94% or more. In comparison, noRouting provides an average of 74% transmission rate, whereas DMQoS has a throughput ranging from 49% to 57%. For low offered data loads of 1 k, DMQoS has a throughput of 57% that continues to decrease especially for high offered data loads of 20 k, when the throughput is 49%. The low throughput in DMQoS may be explained by the way it selects the next hop using the energy-aware geographic forwarding scheme. Because the best next hop does not guarantee that it has the smallest latency connection to the destination, the packet may timeout when it is sent using the “best” next hop. Moreover, the energy-aware geographic forwarding scheme used in DMQoS prefers the nearest next hop candidate in terms of hop count and ignores next hop nodes having a lower delay. As a result, the network traffic is increased and the packets are dropped due to timeout before reaching the destination. QPRD resolves these issues by using the end-to-end path delay.Figure 5
Performance comparison for different parameters when source nodes are static.
(a)
Throughput
(b)
Packets forwarded by intermediate nodes
(c)
Overall network traffic
(d)
Packets timeout
(e)
Packets dropped due to MAC buffer overflow
(f)
Overall energy consumptionB
2 is the closest node to the destination nodes (i.e., NSC or MDCs) as shown in Figure 4. In DMQoS [13], B
2 is responsible for forwarding the data packets from other nodes to NSC or MDCs. This results in more energy consumption for B
2 and increased traffic congestion experienced by B
2. EPR resolves these problems by choosing the most appropriate next hop. In the proposed QPRD scheme, the BAN coordinator does not send data to another BAN coordinator unless it is absolutely necessary. Figure 5(b) shows the number of packets forwarded by the intermediate nodes. It is seen from Figure 5(b) that number of data packets forwarded by intermediate nodes before reaching the destinations in QPRD are on average 0.5 times and 3 times lower than DMQoS and noRouting, respectively.The lower number of forwarded packets by intermediate nodes helps to reduce the overall network traffic. Figure5(c) shows the total network traffic generated by QPRD, DMQoS, and noRouting as a function of the offered traffic load. From this Figure, it is seen that QPRD generates about an average of 26% and 99% less traffic in the network compared to DMQoS and noRouting, respectively. The path calculation in QPRD considers the delay of all the nodes and uses the best path delay information to select the next hop to send the data from source to destination.In contrast to the method used in DMQoS which decides on the immediate next hop based merely on next hop delay instead of overall path delay, each upstream hop in DMQoS sends the packet to its next hop and resultant path in DMQoS may not be the most optimal.From Figure5(d) it is observed that QPRD and noRouting have no packets that were timed out for all offered traffic loads (number of data packets sent by source node range from 0 k to 20 k). QPRD has better performance in terms of reduced overall network traffic and fewer numbers of dropped packets due to timeout, because the clear end-to-end path delay information helps the packet to reach the destination within the requested delay requirement. Moreover, the path calculation in QPRD considers the delay of all the nodes in the network and chooses only those paths which can guarantee delivering the packet to the destination before it times out.Figure5(e) shows that there is no packet dropped due to the MAC buffer overflow in QPRD protocol. This is due to no violation of the model constraints as explained in Sections 4.1 and 4.2. The source node chooses the path which provides the maximum throughput and minimum end-to-end path delay as described in [16, 18]. Only few packets are dropped in DMQoS, whereas 7.5 K packets are dropped in noRouting.It is seen from Figure5(f) that the end-to-end path delay mechanism used in QPRD does not affect the overall energy consumption when compared with DMQoS. QPRD and DMQoS consume the same 18 Joules to 275 Joules of energy when 1 K to 20 K packets are sent by source nodes. On the other hand, the energy consumption of noRouting protocol is 2.6 Joules to 47.7 Joules when 1 K to 20 K packets are sent by source nodes. The data packets in noRouting are randomly forwarded to three neighbor nodes without considering the delay requirements. The additional computations for delay in QPRD consume on average 6 times more energy than noRouting. However, it must be noted that noRouting results in on average a 99% higher overall network traffic. This may be attributed to the 3 times more packets forwarded by intermediate nodes in noRouting resulting in a 20% lower throughput as compared to QPRD.In summary, QPRD outperforms DMQoS and noRouting when the source node is static.


### 5.2. Scenario 2: Mobile Source Node

In the second scenario, the source nodeB
4 is moving at the speed of 1 meter per second vertically as shown in Figure 6. It is assumed that the speed of a fast walking patient is 1 meter per second.Figure 6
Node deployment for scenario 2.Once again, it is observed that QPRD provides better results than DMQoS and noRouting in case of mobile source node scenario. Figure7(a) shows that the throughput is in excess of 80% in QPRD for offered data packet rates less than 8 K. The throughput reduces slightly at higher offered data packet rates of 8 K and more and reduces to 71% when total offered packets sent by the source are 20 K. In contrast with DMQoS, it is observed that when the offered data packet load is increased, DMQoS suffers from a much lower successful data transmission rate that reduces from 50% to 32% with resultant low throughput. Due to node mobility, the source node moves away from its neighbor nodes resulting in a connection loss which results in more packets being lost. QPRD handles this situation much more gracefully than DMQoS. In QPRD, the mobile nodes resume the connection more rapidly once the nodes come back into the range of neighbor node. The overall lower throughput in this scenario is due to the packet lost when the mobile node is out of range. Equation (4d) in Section 3.1 also supports this behavior. According to (4d), the packet delivery is successful only if a source node transmits data to an in-range destination node. The packets are dropped when the movable nodes go out of range. The noRouting provides the lower throughput with an average of 64%.Figure 7
Performance comparison for different parameters when source node is mobile.
(a)
Throughput
(b)
Packets forwarded by intermediate nodes
(c)
Overall network traffic
(d)
Packets timeout
(e)
Packets dropped due to MAC buffer overflow
(f)
Overall energy consumptionFigure7(b) shows that the number of packets forwarded by the intermediate nodes in QPRD is on average 0.75 times and 9 times lower when compared to the number of packets forwarded by intermediate nodes in DMQoS and noRouting protocols, respectively. The routing mechanism used in the QPRD protocol helps to send the data directly to the destination without transferring the packets to the intermediate nodes in case the destination is in range. It can be seen in Section 3.3 that use of intermediate node results in larger delay and in Section 3.2 that the backoff of other noncapturing nodes also contributes to exacerbating the problem. The performance of noRouting for this parameter is worst as it forwards up to 26 K packets which increases the overall network traffic.It is observed from Figure7(c) that the overall network traffic in QPRD is about 25% and 50% less than DMQoS and noRouting protocols, respectively, for all offered network data loads considered. This is due to the end-to-end path calculation mechanism used in QPRD. The delay of all the nodes is considered and QPRD algorithm selects the best next hop, on the basis of end-to-end path delay information, to send the data from source to destination.From Figure7(d), it is seen that QPRD has no packets that were timed out for data packet transmissions at 8 k or less. The selection of minimum end-to-end path delay, given in [18], helps QPRD to send the data through a path where lower packets time out occurs. For high data packets (above 8 k), the source node moves out of the neighbors’ radio range which causes more packets to time out. On the other hand, DMQoS has more timed out packets than QPRD. Initially for low offered data packet rates below 4 k, about 40% of data packets were timed out, and for higher offered data packets (above 4 k) the 40% of data packet time outs increase to 50% (approximately). This is because the packets travel through different nodes by using hop-by-hop delay calculation as discussed in detail in scenario 1. Equation (9) in Section 4.2 shows that the delay on each node is the summation of four different delays (i.e., transmission (DL
trans
⁡), MAC and network queues (DLqueue), channel (DLchannel), and processing (DLproc). The calculations done by DMQoS on each node increase the processing delay which causes the increase of overall node delay. The higher node delay results in packet time out. The source node mobility makes the packet time out worse than scenario 1 of Figure 5(d).Figure7(e) shows that there are no packet drops due to MAC buffer overflow in QPRD and DMQoS protocols, whereas 9 k packets are dropped in noRouting. The performance of DMQoS is similar to QPRD in terms of MAC buffer overflow; however, DMQoS has on average 39% lower throughput and an average of 25% higher overall network traffic.From Figure7(f), it is observed that the overall energy consumptions of QPRD and DMQoS are 18.9 Joules to 275.7 Joules when 1 k to 20 k packets are sent by source nodes. The noRouting consumes 2.6 Joules to 47 Joules when 1 k to 20 k packets are sent by source nodes. The computations for delay in QPRD are almost similar to the DMQoS but QPRD provides on average 25% lower overall network traffic, 73% fewer packets forwarded by intermediate nodes, and, more importantly, a 40% higher successful data transmission rate (throughput) as compared to DMQoS.In summary, the overall performance of QPRD is better than DMQoS and noRouting when the source node is mobile.


## 5.1. Scenario 1: Static Nodes

Figure4 shows the deployment of the experimental network for scenario 1. All the nodes are static in this scenario. The type 1 devices (BANCs: B
1, B
2, B
3, and B
4) are considered as source nodes, and type 2 devices (NSC and MDCs) are the destination nodes. B
1 sends packets to MDC1, B
2 sends packets to MDC2, B
3 sends packets to MDC3, and B
4 sends packets to NSC. The data of B
4 has to go through the other devices to reach NSC. The source nodes send a total of 20 k delay-sensitive packets. The throughput, packets forwarded by intermediate nodes, overall network traffic, number of packets timeout, packets dropped due to MAC buffer overflow, and overall energy consumption are calculated after every 1000 packets until 4 k and then every 4000 packets sent by all BANCs.Figure 4
Node deployment for scenario 1.From Figure5(a), it is seen that QPRD consistently provides throughput of 94% or more. In comparison, noRouting provides an average of 74% transmission rate, whereas DMQoS has a throughput ranging from 49% to 57%. For low offered data loads of 1 k, DMQoS has a throughput of 57% that continues to decrease especially for high offered data loads of 20 k, when the throughput is 49%. The low throughput in DMQoS may be explained by the way it selects the next hop using the energy-aware geographic forwarding scheme. Because the best next hop does not guarantee that it has the smallest latency connection to the destination, the packet may timeout when it is sent using the “best” next hop. Moreover, the energy-aware geographic forwarding scheme used in DMQoS prefers the nearest next hop candidate in terms of hop count and ignores next hop nodes having a lower delay. As a result, the network traffic is increased and the packets are dropped due to timeout before reaching the destination. QPRD resolves these issues by using the end-to-end path delay.Figure 5
Performance comparison for different parameters when source nodes are static.
(a)
Throughput
(b)
Packets forwarded by intermediate nodes
(c)
Overall network traffic
(d)
Packets timeout
(e)
Packets dropped due to MAC buffer overflow
(f)
Overall energy consumptionB
2 is the closest node to the destination nodes (i.e., NSC or MDCs) as shown in Figure 4. In DMQoS [13], B
2 is responsible for forwarding the data packets from other nodes to NSC or MDCs. This results in more energy consumption for B
2 and increased traffic congestion experienced by B
2. EPR resolves these problems by choosing the most appropriate next hop. In the proposed QPRD scheme, the BAN coordinator does not send data to another BAN coordinator unless it is absolutely necessary. Figure 5(b) shows the number of packets forwarded by the intermediate nodes. It is seen from Figure 5(b) that number of data packets forwarded by intermediate nodes before reaching the destinations in QPRD are on average 0.5 times and 3 times lower than DMQoS and noRouting, respectively.The lower number of forwarded packets by intermediate nodes helps to reduce the overall network traffic. Figure5(c) shows the total network traffic generated by QPRD, DMQoS, and noRouting as a function of the offered traffic load. From this Figure, it is seen that QPRD generates about an average of 26% and 99% less traffic in the network compared to DMQoS and noRouting, respectively. The path calculation in QPRD considers the delay of all the nodes and uses the best path delay information to select the next hop to send the data from source to destination.In contrast to the method used in DMQoS which decides on the immediate next hop based merely on next hop delay instead of overall path delay, each upstream hop in DMQoS sends the packet to its next hop and resultant path in DMQoS may not be the most optimal.From Figure5(d) it is observed that QPRD and noRouting have no packets that were timed out for all offered traffic loads (number of data packets sent by source node range from 0 k to 20 k). QPRD has better performance in terms of reduced overall network traffic and fewer numbers of dropped packets due to timeout, because the clear end-to-end path delay information helps the packet to reach the destination within the requested delay requirement. Moreover, the path calculation in QPRD considers the delay of all the nodes in the network and chooses only those paths which can guarantee delivering the packet to the destination before it times out.Figure5(e) shows that there is no packet dropped due to the MAC buffer overflow in QPRD protocol. This is due to no violation of the model constraints as explained in Sections 4.1 and 4.2. The source node chooses the path which provides the maximum throughput and minimum end-to-end path delay as described in [16, 18]. Only few packets are dropped in DMQoS, whereas 7.5 K packets are dropped in noRouting.It is seen from Figure5(f) that the end-to-end path delay mechanism used in QPRD does not affect the overall energy consumption when compared with DMQoS. QPRD and DMQoS consume the same 18 Joules to 275 Joules of energy when 1 K to 20 K packets are sent by source nodes. On the other hand, the energy consumption of noRouting protocol is 2.6 Joules to 47.7 Joules when 1 K to 20 K packets are sent by source nodes. The data packets in noRouting are randomly forwarded to three neighbor nodes without considering the delay requirements. The additional computations for delay in QPRD consume on average 6 times more energy than noRouting. However, it must be noted that noRouting results in on average a 99% higher overall network traffic. This may be attributed to the 3 times more packets forwarded by intermediate nodes in noRouting resulting in a 20% lower throughput as compared to QPRD.In summary, QPRD outperforms DMQoS and noRouting when the source node is static.


## 5.2. Scenario 2: Mobile Source Node

In the second scenario, the source nodeB
4 is moving at the speed of 1 meter per second vertically as shown in Figure 6. It is assumed that the speed of a fast walking patient is 1 meter per second.Figure 6
Node deployment for scenario 2.Once again, it is observed that QPRD provides better results than DMQoS and noRouting in case of mobile source node scenario. Figure7(a) shows that the throughput is in excess of 80% in QPRD for offered data packet rates less than 8 K. The throughput reduces slightly at higher offered data packet rates of 8 K and more and reduces to 71% when total offered packets sent by the source are 20 K. In contrast with DMQoS, it is observed that when the offered data packet load is increased, DMQoS suffers from a much lower successful data transmission rate that reduces from 50% to 32% with resultant low throughput. Due to node mobility, the source node moves away from its neighbor nodes resulting in a connection loss which results in more packets being lost. QPRD handles this situation much more gracefully than DMQoS. In QPRD, the mobile nodes resume the connection more rapidly once the nodes come back into the range of neighbor node. The overall lower throughput in this scenario is due to the packet lost when the mobile node is out of range. Equation (4d) in Section 3.1 also supports this behavior. According to (4d), the packet delivery is successful only if a source node transmits data to an in-range destination node. The packets are dropped when the movable nodes go out of range. The noRouting provides the lower throughput with an average of 64%.Figure 7
Performance comparison for different parameters when source node is mobile.
(a)
Throughput
(b)
Packets forwarded by intermediate nodes
(c)
Overall network traffic
(d)
Packets timeout
(e)
Packets dropped due to MAC buffer overflow
(f)
Overall energy consumptionFigure7(b) shows that the number of packets forwarded by the intermediate nodes in QPRD is on average 0.75 times and 9 times lower when compared to the number of packets forwarded by intermediate nodes in DMQoS and noRouting protocols, respectively. The routing mechanism used in the QPRD protocol helps to send the data directly to the destination without transferring the packets to the intermediate nodes in case the destination is in range. It can be seen in Section 3.3 that use of intermediate node results in larger delay and in Section 3.2 that the backoff of other noncapturing nodes also contributes to exacerbating the problem. The performance of noRouting for this parameter is worst as it forwards up to 26 K packets which increases the overall network traffic.It is observed from Figure7(c) that the overall network traffic in QPRD is about 25% and 50% less than DMQoS and noRouting protocols, respectively, for all offered network data loads considered. This is due to the end-to-end path calculation mechanism used in QPRD. The delay of all the nodes is considered and QPRD algorithm selects the best next hop, on the basis of end-to-end path delay information, to send the data from source to destination.From Figure7(d), it is seen that QPRD has no packets that were timed out for data packet transmissions at 8 k or less. The selection of minimum end-to-end path delay, given in [18], helps QPRD to send the data through a path where lower packets time out occurs. For high data packets (above 8 k), the source node moves out of the neighbors’ radio range which causes more packets to time out. On the other hand, DMQoS has more timed out packets than QPRD. Initially for low offered data packet rates below 4 k, about 40% of data packets were timed out, and for higher offered data packets (above 4 k) the 40% of data packet time outs increase to 50% (approximately). This is because the packets travel through different nodes by using hop-by-hop delay calculation as discussed in detail in scenario 1. Equation (9) in Section 4.2 shows that the delay on each node is the summation of four different delays (i.e., transmission (DL
trans
⁡), MAC and network queues (DLqueue), channel (DLchannel), and processing (DLproc). The calculations done by DMQoS on each node increase the processing delay which causes the increase of overall node delay. The higher node delay results in packet time out. The source node mobility makes the packet time out worse than scenario 1 of Figure 5(d).Figure7(e) shows that there are no packet drops due to MAC buffer overflow in QPRD and DMQoS protocols, whereas 9 k packets are dropped in noRouting. The performance of DMQoS is similar to QPRD in terms of MAC buffer overflow; however, DMQoS has on average 39% lower throughput and an average of 25% higher overall network traffic.From Figure7(f), it is observed that the overall energy consumptions of QPRD and DMQoS are 18.9 Joules to 275.7 Joules when 1 k to 20 k packets are sent by source nodes. The noRouting consumes 2.6 Joules to 47 Joules when 1 k to 20 k packets are sent by source nodes. The computations for delay in QPRD are almost similar to the DMQoS but QPRD provides on average 25% lower overall network traffic, 73% fewer packets forwarded by intermediate nodes, and, more importantly, a 40% higher successful data transmission rate (throughput) as compared to DMQoS.In summary, the overall performance of QPRD is better than DMQoS and noRouting when the source node is mobile.


## 6. Scalability Test: Real Hospital Environment with 24 Beds (49 Nodes)

A real 24-patient-bed hospital is considered for the scalability test of QPRD routing protocol, as shown in Figure8. The approximate area covered is 16 m by 21 m which is similar to the Hematology-Oncology Unit of the Children Hospital named IWK Health Centre Halifax, Canada. The distance between two beds is 3 meters which is in accordance with the recommended transmission range for BAN communication in hospital environment. The total nodes used in the deployment area are 49 (24 BANs, 24 MDCs, and 1 NSC). Each BAN transmits the data to its peer MDC. All the BANs and MDCs are sending or receiving Hello protocols to/from other nodes and the NSC.Figure 8
Scenario 3. Node deployment for 24 patient beds in hospital environment.Both MDCs and BANs are movable. Generally, BANs can move freely anywhere and the movement of a MDC is only within the room where it is placed. It is assumed that the MDC of one room has a connection with the MDC of the next room.The simulation results show that QPRD performs better than DMQoS and noRouting even when the number of nodes is increased to 49. From Figure9(a) it is seen that the throughput provided by QPRD is in excess of 91%, whereas the throughput of noRouting and DMQoS protocols is on average 74% and 52%, respectively. From Figure 9(b), it is observed that the overall network traffic of QPRD is 50% and 25% less than noRouting and DMQoS protocols, respectively. Figure 9(c) shows that the packet drops due to MAC buffer overflow in QPRD and DMQoS protocols are negligible, whereas 9 k packets are dropped in noRouting. Figure 9(d) shows that there are no packets timeouts due to not fulfilling the delay requirements in QPRD and noRouting. On the other hand 25 k packets are timed out in DMQoS. From these results it is shown that QPRD is equally effective when the deployment area is larger, and number of nodes has been increased to simulate a real hospital scenario with 24 patient beds.Figure 9
Performance comparison for different parameters of scenario 3.
(a)
Throughput versus offered load
(b)
Overall network traffic
(c)
Packets dropped due to MAC buffer overflow
(d)
Packets timeout


## 7. Conclusion

The paper models the wireless BAN as a directed graph and derives conditions for throughput maximization and end-to-end delay minimization. It is shown that efficient energy utilization is critical to the proper design of the routing and MAC layer protocols. Similarly, delay is minimized by formulating the BAN end-to-end path delay as a linear programming problem with multiple constraints to be satisfied simultaneously.Based on the mathematical analysis, a novel modular QoS-aware routing protocol for hospital BAN communication is proposed in this paper. The architecture of the new protocol consists of seven modules: the MAC receiver, the delay module (DM), the packet classifier (PC), the Hello protocol module (HPM), the routing services module (RSM), the QoS-aware queuing module (QQM), and the MAC transmitter. The proposed routing protocol provides a mechanism for the end-to-end path delay calculation of all possible paths from a source to destination and then decides the best possible path by considering the path delay requirements of the delay-sensitive packets.OMNeT++ based simulator Castalia 3.2 is used to test the performance of the proposed protocol (QPRD) and compare it with DMQoS and noRouting. The simulations are performed for both the movable source and stationary scenarios. A scalability test is done with larger deployment area and by using higher number of nodes. The results show that the QPRD offers over 94% successful data transmission rates for delay-sensitive packets in a stationary patient scenario. QPRD provides about 35% better results in terms of successful transmission rate than DMQoS in the movable patient scenario. The simulation results show that the QPRD improves the reliability of Body Area Networks by 40% on average for each scenario by decreasing the number of packet time outs with zero and averaging 729 packets for the static and mobile patient scenarios, respectively. In addition, QPRD results in an average of 25% lower overall network traffic for each mobile and static patient scenarios as compared to similar protocols. The scalability test results prove that QPRD outperforms DMQoS and noRouting even when a higher number of nodes are employed in the BAN. QPRD provides on average 93% throughput without any packet being timed out and any packet being dropped due to MAC buffer overflow.



---

*Source: 153232-2015-09-30.xml*