07-11-2012, 12:29 PM
Adaptive Fault-Tolerant QoS Control Algorithms for Maximizing System Lifetime of Query-Based Wireless Sensor Networks
Adaptive Fault-Tolerant.pdf (Size: 1.64 MB / Downloads: 44)
Abstract
Data sensing and retrieval in wireless sensor systems have a widespread application in areas such as security and
surveillance monitoring, and command and control in battlefields. In query-based wireless sensor systems, a user would issue a query
and expect a response to be returned within the deadline. While the use of fault tolerance mechanisms through redundancy improves
query reliability in the presence of unreliable wireless communication and sensor faults, it could cause the energy of the system to be
quickly depleted. Therefore, there is an inherent trade-off between query reliability versus energy consumption in query-based wireless
sensor systems. In this paper, we develop adaptive fault-tolerant quality of service (QoS) control algorithms based on hop-by-hop data
delivery utilizing “source” and “path” redundancy, with the goal to satisfy application QoS requirements while prolonging the lifetime of
the sensor system. We develop a mathematical model for the lifetime of the sensor system as a function of system parameters
including the “source” and “path” redundancy levels utilized. We discover that there exists optimal “source” and “path” redundancy
under which the lifetime of the system is maximized while satisfying application QoS requirements. Numerical data are presented and
validated through extensive simulation, with physical interpretations given, to demonstrate the feasibility of our algorithm design.
INTRODUCTION
OVER the last few years, we have seen a rapid increase in
the number of applications for wireless sensor networks
(WSNs). WSNs can be deployed in battlefield
applications, and a variety of vehicle health management
and condition-based maintenance applications on industrial,
military, and space platforms. For military users, a
primary focus has been area monitoring for security and
surveillance applications.
A WSN can be either source-driven or query-based
depending on the data flow. In source-driven WSNs,
sensors initiate data transmission for observed events to
interested users, including possibly reporting sensor readings
periodically. An important research issue in sourcedriven
WSNs is to satisfy QoS requirements of event-to-sink
data transport while conserving energy of WSNs. In querybased
WSNs, queries and data are forwarded to interested
entities only. In query-based WSNs, a user would issue a
query with QoS requirements in terms of reliability and
timeliness.
RELATED WORK
Existing research efforts related to applying redundancy to
satisfy QoS requirements in query-based WSNsfall into three
categories: traditional end-to-end QoS, reliability assurance,
and application-specific QoS [4]. Traditional end-to-end QoS
solutions are based on the concept of end-to-end QoS
requirements. The problem is that it may not be feasible to
implement end-to-end QoS in WSNs due to the complexity
and high cost of the protocols for resource-constrained
sensors. An example is Sequential Assignment Routing
(SAR) [5] that utilizes path redundancy from a source node
to the sink node. Each sensor uses a SAR algorithm for path
selection. It takes into account the energy and QoS factors on
each path, and the priority level of a packet. For each packet
routed through the network, a weighted QoS metric is
computed as the product of the additive QoS metric and a
weight coefficient associated with the priority level of that
packet. The objective of the SAR algorithm is to minimize the
average weighted QoS metric throughout the lifetime of the
network. The algorithm does not consider the reliability issue.
ESRT [12] has been proposed to address this issue with
reliability as the QoS metric. ReInForM has been proposed
[6] to address end-to-end reliability issues. ReInForm
considers information awareness and adaptability to channel
errors along with a differentiated allocation strategy of
network resources based on the criticality of data. The
protocol sends multiple copies of a packet along multiple
paths from the source to the sink such that data is delivered
with the desired reliability. It uses the concept of dynamic
packet state to control the number of paths required for the
desired reliability using local knowledge of the channel
error rate and topology. The protocol observes that for
uniform unit disk graphs, the number of edge-disjoint paths
between nodes is equal to the average node degree with a
very high probability.
PROBABILITY MODEL
The adaptive fault-tolerant QoS control (AFTQC) algorithm
developed in this paper takes two forms of redundancy.
The first form is path redundancy. That is, instead of using
a single path to connect a source cluster to the processing
center, mp disjoint paths may be used. The second is source
redundancy. That is, instead of having one sensor node in a
source cluster return requested sensor data, ms sensor
nodes may be used to return readings to cope with data
transmission and/or sensor faults. Fig. 1 illustrates a
scenario in which mp ¼ 2 (two paths going from the CH
to the processing center) and ms ¼ 5 (five SNs returning
sensor readings to the CH).
Data Aggregation
The analysis performed thus far assumes that a source CH
does not aggregate data. The CH may receive up to ms
redundant sensor readings due to source redundancy but
will just forward the first one received to the PC. Thus, the
data packet size is the same. For more sophisticated
scenarios, conceivably the CH could also aggregate data
for query processing and the size of the aggregate packet
may be larger than the average data packet size. We extend
the analysis to deal with data aggregation in two ways. The
first is to set a larger size for the aggregated packet that
would be transmitted from a source CH to the PC. This will
have the effect of favoring the use of a smaller number of
redundant paths (i.e., mp) because more energy would be
expended to transmit aggregate packets from the source CH
to the PC. The second is for the CH to collect a majority of
sensor readings from its sensors before data are aggregated
and transmitted to the PC. The analysis of data aggregation
thus, in effect, is the same as the one we have performed for
SN software faults in Section 4.5.3 requiring a majority of
sensors to return correct sensor readings.
SIMULATION
In this section, we present simulation results to compare
with analytical results for the purpose of validation. Table 3
lists a default set of parameter values used in the simulation.
We use J-Sim as our simulation framework. We consider a
small-scaled WSN so we could obtain simulation results
with statistical significance. In our simulation environment,
SNs are distributed in a square terrain area of size A2 in
accordance with a population distribution function.
Adaptive Fault-Tolerant.pdf (Size: 1.64 MB / Downloads: 44)
Abstract
Data sensing and retrieval in wireless sensor systems have a widespread application in areas such as security and
surveillance monitoring, and command and control in battlefields. In query-based wireless sensor systems, a user would issue a query
and expect a response to be returned within the deadline. While the use of fault tolerance mechanisms through redundancy improves
query reliability in the presence of unreliable wireless communication and sensor faults, it could cause the energy of the system to be
quickly depleted. Therefore, there is an inherent trade-off between query reliability versus energy consumption in query-based wireless
sensor systems. In this paper, we develop adaptive fault-tolerant quality of service (QoS) control algorithms based on hop-by-hop data
delivery utilizing “source” and “path” redundancy, with the goal to satisfy application QoS requirements while prolonging the lifetime of
the sensor system. We develop a mathematical model for the lifetime of the sensor system as a function of system parameters
including the “source” and “path” redundancy levels utilized. We discover that there exists optimal “source” and “path” redundancy
under which the lifetime of the system is maximized while satisfying application QoS requirements. Numerical data are presented and
validated through extensive simulation, with physical interpretations given, to demonstrate the feasibility of our algorithm design.
INTRODUCTION
OVER the last few years, we have seen a rapid increase in
the number of applications for wireless sensor networks
(WSNs). WSNs can be deployed in battlefield
applications, and a variety of vehicle health management
and condition-based maintenance applications on industrial,
military, and space platforms. For military users, a
primary focus has been area monitoring for security and
surveillance applications.
A WSN can be either source-driven or query-based
depending on the data flow. In source-driven WSNs,
sensors initiate data transmission for observed events to
interested users, including possibly reporting sensor readings
periodically. An important research issue in sourcedriven
WSNs is to satisfy QoS requirements of event-to-sink
data transport while conserving energy of WSNs. In querybased
WSNs, queries and data are forwarded to interested
entities only. In query-based WSNs, a user would issue a
query with QoS requirements in terms of reliability and
timeliness.
RELATED WORK
Existing research efforts related to applying redundancy to
satisfy QoS requirements in query-based WSNsfall into three
categories: traditional end-to-end QoS, reliability assurance,
and application-specific QoS [4]. Traditional end-to-end QoS
solutions are based on the concept of end-to-end QoS
requirements. The problem is that it may not be feasible to
implement end-to-end QoS in WSNs due to the complexity
and high cost of the protocols for resource-constrained
sensors. An example is Sequential Assignment Routing
(SAR) [5] that utilizes path redundancy from a source node
to the sink node. Each sensor uses a SAR algorithm for path
selection. It takes into account the energy and QoS factors on
each path, and the priority level of a packet. For each packet
routed through the network, a weighted QoS metric is
computed as the product of the additive QoS metric and a
weight coefficient associated with the priority level of that
packet. The objective of the SAR algorithm is to minimize the
average weighted QoS metric throughout the lifetime of the
network. The algorithm does not consider the reliability issue.
ESRT [12] has been proposed to address this issue with
reliability as the QoS metric. ReInForM has been proposed
[6] to address end-to-end reliability issues. ReInForm
considers information awareness and adaptability to channel
errors along with a differentiated allocation strategy of
network resources based on the criticality of data. The
protocol sends multiple copies of a packet along multiple
paths from the source to the sink such that data is delivered
with the desired reliability. It uses the concept of dynamic
packet state to control the number of paths required for the
desired reliability using local knowledge of the channel
error rate and topology. The protocol observes that for
uniform unit disk graphs, the number of edge-disjoint paths
between nodes is equal to the average node degree with a
very high probability.
PROBABILITY MODEL
The adaptive fault-tolerant QoS control (AFTQC) algorithm
developed in this paper takes two forms of redundancy.
The first form is path redundancy. That is, instead of using
a single path to connect a source cluster to the processing
center, mp disjoint paths may be used. The second is source
redundancy. That is, instead of having one sensor node in a
source cluster return requested sensor data, ms sensor
nodes may be used to return readings to cope with data
transmission and/or sensor faults. Fig. 1 illustrates a
scenario in which mp ¼ 2 (two paths going from the CH
to the processing center) and ms ¼ 5 (five SNs returning
sensor readings to the CH).
Data Aggregation
The analysis performed thus far assumes that a source CH
does not aggregate data. The CH may receive up to ms
redundant sensor readings due to source redundancy but
will just forward the first one received to the PC. Thus, the
data packet size is the same. For more sophisticated
scenarios, conceivably the CH could also aggregate data
for query processing and the size of the aggregate packet
may be larger than the average data packet size. We extend
the analysis to deal with data aggregation in two ways. The
first is to set a larger size for the aggregated packet that
would be transmitted from a source CH to the PC. This will
have the effect of favoring the use of a smaller number of
redundant paths (i.e., mp) because more energy would be
expended to transmit aggregate packets from the source CH
to the PC. The second is for the CH to collect a majority of
sensor readings from its sensors before data are aggregated
and transmitted to the PC. The analysis of data aggregation
thus, in effect, is the same as the one we have performed for
SN software faults in Section 4.5.3 requiring a majority of
sensors to return correct sensor readings.
SIMULATION
In this section, we present simulation results to compare
with analytical results for the purpose of validation. Table 3
lists a default set of parameter values used in the simulation.
We use J-Sim as our simulation framework. We consider a
small-scaled WSN so we could obtain simulation results
with statistical significance. In our simulation environment,
SNs are distributed in a square terrain area of size A2 in
accordance with a population distribution function.