8.2.1 MDP-Based Tuning Methodology for Embedded Wireless Sensor Networks

Figure 8.1 depicts the process diagram for our MDP-based application-oriented dynamic tuning methodology. Our methodology consists of three logical domains: the application characterization domain, the communication domain, and the sensor node tuning domain.

The application characterization domain refers to the EWSN application's characterization/specification. In this domain, the application manager defines various application metrics (e.g., tolerable power consumption, tolerable delay), which are calculated from (or based on) application requirements. The application manager also assigns weight factors to application metrics to signify the weightage or importance of each application metric. Weight factors provide application managers with an easy method to relate the relative importance of each application metric. The application manager defines an MDP reward function, which signifies the overall reward (revenue) for given application requirements. The application metrics along with the associated weight factors represents the MDP reward function parameters.

The communication domain contains the sink node (which gathers statistics from the embedded sensor nodes) and encompasses the communication network between the application manager and the sensor nodes. The application manager transmits the MPD reward function parameters to the sink node via the communication domain. The sink node in turn relays reward function parameters to the embedded sensor nodes.

The sensor node tuning domain consists of embedded sensor nodes and performs sensor node tuning. Each sensor node contains an MDP controller module, which implements our MDP-based tuning methodology (summarized here and described in detail in Section 8.3). After an embedded sensor node receives reward function parameters from the sink node through the communication domain, the sensor node invokes the MDP controller module. The MDP controller module calculates the MDP-based policy. The MDP-based policy prescribes the sensor node actions to meet application requirements over the lifetime of the sensor node. An action prescribes the sensor node state (defined by processor voltage, processor frequency, and sensing frequency) to transition from the current state. The sensor node identifies its current operating state, determines an action “” prescribed by the MDP-based policy (i.e., whether to continue operation in the current state or transition to another state), and subsequently executes action “.”

Our proposed MDP-based dynamic tuning methodology can adapt to changes in application requirements (since application requirements may change with time, for example, a defense system initially deployed to monitor enemy troop position for 4 months may later be required to monitor troop activity for an extended period of 6 months). Whenever application requirements change, the application manager updates the reward function (and/or associated parameters) to reflect the new application requirements. Upon receiving the updated reward function, the sensor node reinvokes MDP controller module and determines the new MDP-based policy to meet the new application requirements.

Our MDP-based application-oriented dynamic tuning methodology reacts to environmental stimuli via a dynamic profiler module in the sensor node tuning domain. The dynamic profiler module monitors environmentalchanges over time and captures unanticipated environmental situations not predictable at design time [300]. The dynamic profiler module may be connected to the sensor node and profiles the profiling statistics (e.g., wireless channel condition, number of packets dropped, packet size, radio transmission power) when triggered by the EWSN application. The dynamic profiler module informs the application manager of the profiled statistics via the communication domain. After receiving the profiling statistics, the application manager evaluates the statistics and possibly updates the reward function parameters. This reevaluation process may be automated, thus eliminating the need for continuous application manager input. Based on these received profiling statistics and updated reward function parameters, the sensor node MDP controller module determines whether application requirements are met or not met. If application requirements are not met, the MDP controller module reinvokes the MDP-based policy to determine a new operating state to better meet application requirements. This feedback process continues to ensure that the application requirements are met in the presence of changing environmental stimuli.

Algorithm 3 depicts our MDP-based dynamic tuning methodology in an algorithmic form, which applies to all embedded sensor nodes in the WSN (line 1) and spans the entire lifetime of the embedded sensor nodes (line 2). The algorithm determines an MDP-based policy according to the application's initial requirements (captured by the MDP reward function parameters) at the time of EWSN deployment (lines 3 and 4). The algorithm determines a new MDP-based policy to adapt to the changing application requirements (lines 6 and 7). After determining , the algorithm specifies the action according to for each embedded sensor node state , given the total number of states (lines 9–17).

8.2.2 MDP Overview with Respect to Embedded Wireless Sensor Networks

In this section, we define basic MDP terminology in the context of EWSNs and give an overview of our proposed MDP-based dynamic tuning policy formulation for embedded sensor nodes. MDPs, also known as stochastic dynamic programming, are used to model and solve dynamic decision-making problems. We use standard notations as defined in [313] for our MDP-based problem formulation. Table 8.1 presents a summary of key notations used in this chapter.

Notation	Description
	Sensor node state
	State space
	Number of decision epochs
	Number of sensor node state tuples
	Reward at time given state and action
	Action to transition from state to state
	Allowable actions in state
	Transition probability function
	Expected reward of policy with initial state
	Discount factor
	Expected total reward
	Expected total discounted reward
	Maximum expected total discounted reward
	Optimal decision rule
	Decision rule at time
	Optimal policy
	MDP-based policy

The basic elements of an MDP model are decision epochs and periods, states, action sets, transition probabilities, and rewards. An MDP is Markovian (memoryless) because the transition probabilities and rewards depend on the past only through the current state and the action selected by the decision maker in that state. The decision epochs refer to the points of time during a sensor node's lifetime at which the sensor node makes a decision. Specifically, a sensor node makes a decision regarding its operating state atthese decision epochs (i.e., whether to continue operating at the current state (processor voltage, frequency, and sensing frequency) or transition to another state). We consider a discrete time process where time is divided into periods and a decision epoch corresponds to the beginning of a period. The set of decision epochs can be denoted as , where and denotes the sensor node's lifetime (each individual time period in can be denoted as time ). The decision problem is referred to as a finite horizon problem when the decision-making horizon is finite and infinite horizon otherwise. In a finite horizon problem, the final decision is made at decision epoch ; hence, the finite horizon problem is also known as the period problem.

The system (a sensor node) operates in a particular state at each decision epoch, where denotes the complete set of possible system states. States specify particular sensor node parameter values and each state represents a different combination of these values. An action set represents all allowable actions in all possible states. At each decision epoch, the sensor node decides whether to continue operating in the current state or to switch to another state. The sensor node state (in our problem) represents a tuple consisting of processor voltage (), processor frequency (), and sensing frequency (). If the system is in state at a decision epoch, the sensor node can choose an action from the set of allowable actions in state . Thus, an action set can be written as . We assume that and do not vary with time [313].

When a sensor node selects action in state , the sensor node receives a reward and the transition probability distribution determines the system state at the next decision epoch. The real-valued function denotes the value of the reward received at time in period . The reward is referred to as income or cost depending on whether or not is positive or negative, respectively. When the reward depends on the system state at the next decision epoch, we let denote the value of the reward received at time when the system state at decision epoch is . The sensor node selects action , and the system occupies the state at decision epoch . The sensor node evaluates using [313]

8.1

where the nonnegative function is called a transition probability function. denotes the probability that the system occupies state at time when the sensor node selects action in state at time and usually . Formally, an MDP is defined as the collection of objects .

A decision rule prescribes an action in each state at a specified decision epoch. Our decision rule for sensor nodes is a function , which specifies the action at time when the system is in state for each , . This decision rule is both Markovian and deterministic.

A policy specifies the decision rule for all decision epochs. In the case of sensor nodes, the policy prescribes action selection under any possible system state. A policy is a sequence of decision rules, that is, for . A policy is stationary if , that is, for stationary policy .

As a result of selecting and implementing a particular policy, the sensor node receives rewards at time periods . The reward sequence is random because therewards received in different periods are not known prior to policy implementation. The sensor node's optimization objective is to determine a policy that maximizes the corresponding random reward sequence.

8.3.1 State Space

The state space for our MDP-based tuning methodology is a composite state space containing the Cartesian product of embedded sensor node tunable parameters' state spaces. We define the state space as

8.2

where denotes the Cartesian product, is the total number of sensor node tunable parameters, denotes the state space for tunable parameter where , and denotes the state space cardinality (the number of states in ).

The tunable parameter 's state space () consists of values

8.3

where denotes the tunable parameter 's state space cardinality (the number of tunable values in ). is a set of -tuples where each -tuple represents a sensor node state . Each state is an -tuple, that is, . Note that some -tuples in may not be feasible (e.g., all processor voltage and frequency pairs are not feasible) and can be regarded as do not care tuples.

Each embedded sensor node state has an associated power consumption, throughput, and delay. The power, throughput, and delay for state are denoted by , , and , respectively. Since different sensor nodes may have different embedded processors and attached sensors, each node may have node-specific power consumption, throughput, and delay information for each state.

8.3.2 Decision Epochs and Actions

Embedded sensor nodes make decisions at decision epochs, which occur after fixed time periods. The sequence of decision epochs is represented as

8.4

where the random variable corresponds to the embedded sensor node's lifetime.

At each decision epoch, a sensor node's action determines the next state to transition to the given current state. The sensor node action in state is defined as

8.5

where denotes the action taken at time that causes the sensor node to transition to state at time from the current state . A policy determines whether an action is taken or not. If , the action is taken and if , the action is not taken. For a given state , a selected action cannot result in a transition to a state that is not in . The action space can be defined as

8.6

8.3.3 State Dynamics

The state dynamics of the system can be delineated by the state transition probabilities of the embedded Markov chain. We formulate our sensor node policy as a deterministic dynamic program (DDP) because the choice of an action determines the subsequent state with certainty. Our sensor node DDP policy formulation uses a transfer function to specify the next state. A transfer function defines a mapping from , which specifies the system state at time when the sensor node selects action in state at time . To formulate our DDP as an MDP, we define the transition probability function as

8.7

8.3.4 Policy and Performance Criterion

For each given state , a sensor node selects an action according to a policy where is a set of admissible policies defined as

8.8

A performance criterion compares the performance of different policies. The sensor node selects an action prescribed by a policy based on the sensor node's current state. If the random variable denotes the state at decision epoch and the random variable denotes the action selected at decision epoch , then for the deterministic case, .

As a result of selecting an action, the sensor node receives a reward at time . The expected total reward denotes the expected total reward over the decision-making horizon given a specific policy. Let denote the expected totalreward over the decision-making horizon when the horizon length is a random variable, the system is in state at the first decision epoch, and policy is used [300, 314]

8.9

where represents the expected reward with respect to policy and the initial state (the system state at the time of the expected reward calculation), and denotes the expected reward with respect to the probability distribution of the random variable . We can write Eq. (8.9) as [313]

8.10

which gives the expected total discounted reward. We assume that the random variable is geometrically distributed with parameter , and hence the distribution mean is [299]. The parameter can be interpreted as a discount factor, which measures the present value of one unit of reward received for one period in the future. Thus, represents the expected total present value of the reward (income) stream obtained using policy [313]. Our objective is to find a policy that maximizes the expected total discounted reward, that is, a policy is optimal if

8.11

8.3.5 Reward Function

The reward function captures application metrics and sensor node characteristics. Our reward function characterization considers the power consumption (which affects the sensor node's lifetime), throughput, and delay application metrics. We define the reward function , given the current sensor node state and the sensor node's selected action as

8.12

where denotes the power reward function; denotes the throughput reward function; denotes the delay reward function; and , , and represent the weight factors for power, throughput, and delay, respectively. The weight factors' constraints are given as where such that , , and . The weight factors are selected based on the relative importance of application metrics with respect to each other, for example, a habitat monitoring application taking camera images of the habitat requires a minimum image resolution to provide meaningful analysis that necessitates a minimum throughput, and therefore throughput can be assigned a higher weight factor than the power metric for this application.

We define linear reward functions for application metrics because an application metric reward (objective function) typically varies linearly, or piecewise linearly, between the minimum and the maximum allowed values of the metric [300, 311]. However, a nonlinear characterization of reward functions is also possible and depends on the particular application. We point out that our methodology works for any characterization of reward function. The reward function characterization only defines the reward obtained from operating in a given state. Our MDP-based policy determines the reward by selecting an optimal/suboptimal operating state, given the sensor node design space and application requirements for any reward function characterization. We consider linear reward functions as a typical example from the space of possible reward functions (e.g., piecewise linear, nonlinear) to illustrate our MDP-based policy. We define the power reward function (Fig. 8.2(a)) in Eq. (8.12) as

8.13

where denotes the power consumption of the current state given action taken at time , and the constant parameters and denote the minimum and maximum allowed/tolerated sensor node power consumption, respectively.

We define the throughput reward function (Fig. 8.2(b)) in Eq. (8.12) as

8.14

where denotes the throughput of the current state given action taken at time and the constant parameters and denote the minimum and maximum allowed/tolerated throughput, respectively.

We define the delay reward function (Fig. 8.2(c)) in Eq. (8.12) as

8.15

where denotes the delay in the current state and the constant parameters and denote the minimum and maximum allowed/tolerated delay, respectively.

State transitioning incurs a cost associated with switching parameter values from the current state to the next state (typically in the form of power and/or execution overhead). We define the transition cost function as

8.16

where denotes the transition cost to switch from the current state to the next state as determined by action . Note that a sensor node incurs no transition cost if action prescribes that the next state is the same as the current state.

Hence, the overall reward function given state and action at time is

8.17

which accounts for the power, throughput, and delay application metrics as well as state transition cost.

We point out that many other application metrics (e.g., security, reliability, and lifetime) are of immense significance to EWSNs. For example, EWSNs are vulnerable to security attacks such as distributed denial of service and Sybil attacks for which a security reward function can be included. A reliability reward function can encompass the reliability aspect of EWSNs since sensor nodes are often deployed in unattended and hostile environments and are susceptible to failures. Similarly, considering sensor nodes' constrained battery resources, power optimization techniques exist that put sensor nodes in sleep or low-power mode (where communication and/or processing functions are disabled) for power conservation when less activity is observed in the sensed region as determined by previously sensed data. These power optimizations can be captured by a lifetime reward function. These additional metrics incorporation in our model is the focus of our future work.

8.3.6 Optimality Equation

The optimality equation, also known as Bellman's equation, for expected total discounted reward criterion is given as [313]

8.18

where denotes the maximum expected total discounted reward. The following are the salient properties of the optimality equation: the optimality equation has a unique solution; an optimal policy exists in given conditions on states, actions, rewards, and transition probabilities; the value of the discounted MDP satisfies the optimality equation; and the optimality equation characterizes stationary policies.

The solution of Eq. (8.18) gives the maximum expected total discounted reward and the MDP-based policy , which gives the maximum . prescribes the action from action set , given the current state for all . There are several methods to solve the optimality equation (8.18) such as value iteration, policy iteration, and linear programming; however, in this work, we use the policy iteration algorithm.

8.3.7 Policy Iteration Algorithm

The policy iteration algorithm can be described in four steps:

1. 1. Set and choose any arbitrary decision rule where is a set of all possible decision rules.
2. 2. Policy evaluation—Obtain by solving the equations:8.19
3. 3. Policy improvement—Select to satisfy the equations:
   8.20

   and setting if possible.

4. 4. If , stop and set where denotes the optimal decision rule. If , set and go to step 2.

Step 2 is referred to as policy evaluation because, by solving Eq. (8.19), we obtain the expected total discounted reward for decision rule . Step 3 is referred to as policy improvement because this step selects a -improving decision rule. In step 4, quells cycling because a decision rule is not necessarily unique.

8.4.1 Implementation Guidelines

In order to implement our MDP-based policy, particular values must be initially defined. The reward function Eq. (8.17) uses the power, throughput, and delay values offered in an embedded sensor node state (Section 8.3.1). An application manager specifies the minimum and maximum power, throughput, and delay values required by Eq. (8.13)–(8.15), respectively, and the power, throughput, and delay weight factors required in Eq. (8.12) according to application specifications.

A sensor node's embedded processor defines the transition cost as required in Eq. (8.16), which is dependent on a particular processor's power management and switching techniques. Processors have a set of available voltage and frequency pairs, which defines the and values, respectively, in a sensor node state tuple (Section 8.3.1). Embedded sensors can operate at different defined sensing rates, which define the value in a sensor node state tuple (Section 8.3.1). The embedded processor and sensor characteristics determine the value of , which characterizes the state space in Eq. (8.2) (i.e., the number of allowable processor voltage, processor frequency, and sensing frequency values determine the total number of sensor node operating states, and thus the value of ).

The sensor nodes perform parameter tuning decisions at decision epochs (Section 8.2.2). The decision epochs can be guided by the dynamic profiler module to adapt to the environmental stimuli. For instance, for a target-tracking application and a fast-moving target, the decision epoch period should be small to better capture the fast-moving target. On the other hand, for stationary or slow-moving targets, decision epoch period should be large to conserve battery energy. However, since the exact decision epoch period is application specific, the period should be adjusted to control the sensor node's lifetime.

Both the MDP controller module (which implements the policy iteration algorithm to calculate the MDP-based policy ) and the dynamic profiler module (Section 8.2.1) can either be implemented as software running on a sensor node's embedded processor or custom hardware for faster execution.

One of the drawbacks for MDP-based policy is that computational and storage overhead increases as the number of states increases. Therefore, EWSN designer would like to restrict the embedded sensor states (e.g., 2, 4, or 16) to reduce the computational and storage overhead. If state restriction is not a viable option, the EWSN configuration could be augmented with a back-end base station node to run our MDP-based optimization, and the sensor node operating states would be communicated to the sensor nodes. This communication of operating state information to sensor nodes by the base station node would not consume enough power resources, given that this state information is transmitted periodically and/or aperiodically after some minimum duration determined by the agility of the environmental stimuli (e.g., more frequent communication would be required for a rapidly changing environmental stimuli as opposed to a slow changing environmental stimuli). This EWSN configuration could also consider global optimizations, which are optimizations that take into account sensor node interactions and dependencies and is a focus of our future work. We point out that global optimization storage and processing overhead increases rapidly as the number of sensor nodes in EWSN increases.

8.4.2 Computational Complexity

Since sensor nodes have limited energy reserves and processing resources, it is critical to analyze our proposed MDP-based policy's computational complexity, which is related to the convergence of the policy iteration algorithm. Since our problem formulation (Section 8.3) consists of finite states and actions, Puterman [313] proves a theorem that establishes the convergence of the policy iteration algorithm for finite states and actions in a finite number of iterations. Another important computational complexity factor is the algorithm's convergence rate. Puterman [313] shows that for a finite number of states and actions, the policy iteration algorithm converges to the optimal/suboptimal value function at least quadratically fast. Empirical observations suggest that the policy iteration algorithm can converge in iterations where each iteration takes time (for policy evaluation); however, no proof yet exists to verify these empirical observations [314]. Based on these empirical observations for convergence, policy iteration algorithm can converge in four iterations for .

8.4.3 Data Memory Analysis

We performed data memory analysis using the 8-bit Atmel ATmega128L microprocessor [192] in XSM sensor nodes [315]. The Atmel ATmega128L microprocessor contains 128 KB of on-chip in-system reprogrammable Flash memory for program storage, 4 KB of internal SRAM data memory, and up to 64 KB of external SRAM data memory. Integer and floating-point data types require 2 and 4 B of storage, respectively. Our data memory analysis considers all storage requirements for our MDP-based dynamic tuning formulation (Section 8.3) including state space, action space, state dynamics (transition probability matrix), Bellman's equation (8.18), MDP reward function calculation (reward matrix), and policy iteration algorithm. We estimate data memory size for three sensor node configurations:

• 4 sensor node states with 4 allowable actions in each state (16 actions in the action space) (Fig. 8.4);
• 8 sensor node states with 8 allowable actions in each state (64 actions in the action space);
• 16 sensor node states with 16 allowable actions in each state (256 actions in the action space).

Data memory analysis revealed that 4, 8, and 16 sensor node state configurations required approximately 1.55, 14.8, and 178.55 KB, respectively. Thus, currently available sensor node platforms contain enough memory resources to implement our MDP-based dynamic tuning methodology with 16 sensor node states or fewer. However, the memory requirements increase rapidly as the number of states increases due to the transition probability matrix and reward matrix specifications. Therefore, depending on the available memory resources, an application developer could restrict the number of states accordingly or otherwise would have to resort to doing computations on the back-end base station as outlined in Section 8.4 to conserve power and storage.

8.6.1 Fixed Heuristic Policies for Performance Comparisons

Due to the infancy of EWSN dynamic optimizations, there exist no dynamic sensor node tuning methods for comparison with our MDP-based policy. Therefore, we compare to several fixed heuristic policies (heuristic policies have been shown to be a viable comparison method [299]). To provide a consistent comparison, fixed heuristic policies use the same reward function and the associated parameter settings as that of our MDP-based policy. We consider the following four fixed heuristic policies:

• A fixed heuristic policy that always selects the state with the lowest power consumption.
• A fixed heuristic policy that always selects the state with the highest throughput.
• A fixed heuristic policy that spends an equal amount of time in each of the available states.
• A fixed heuristic policy that spends an unequal amount of time in each of the available states based on a specified preference for each state. For example, given a system with four possible states, the policy may spend 40% of time in the first state, 20% of time in the second state, 10% of time in the third state, and 30% of time in the fourth state.

8.6.2 MDP Specifications

We compare different policies using the expected total discounted reward performance criterion (Section 8.3.6). The state transition probability for each sensor node state is given by Eq. (8.7). The sensor node's lifetime and the time between decision epochs are subjective and may be assigned by an application manager according to application requirements. A sensor node's mean lifetime is given by time units, which is the time between successive decision epochs (which we assume to be 1 h). For instance for , the sensor node's mean lifetime is h 42 days.

For our numerical results, we consider a sensor node capable of operating in four different states (i.e., in Eq. (8.2)). Figure 8.4 shows the symbolic representation of our MDP model with four sensor node states. Each state has a set of allowed actions prescribing transitions to available states. For each allowed action in a state, there is a pair where specifies the immediate reward obtained by taking action and denotes the probability of taking action .

Table 8.2 summarizes state parameter values for each of the four states –. We define each state using a tuple where is specified in volts, in MHz, and in kHz. For instance, state one is defined as , which corresponds to a processor voltage of 2.7 V, a processor frequency of 2 MHz, and a sensing frequency of 2 kHz (2000 samples/s). We represent state power consumption, throughput, and delay as multiples of power, throughput, and delay base units, respectively. We assume one base power unit is equal to 1 mW, one base throughput unit is equal to 0.5 MIPS (millions of instructions per second), and one base delay unit is equal to 50 ms. We assign base units such that these units provide a convenient representation of application metrics (power, throughput, delay). We point out, however, that any other feasible base unit values can be assigned [299]. We assume, without loss of generality, that the transition cost for switching from one state to another is . The transition cost could be a function of power, throughput, and delay, but we assume a constant transition cost for simplicity as it is typically constant for different state transitions [192].

Notation
	10	15	30	55
	4	8	12	16
	26	14	8	6

Parameters are specified as a multiple of a base unit where one power unit is equal to 1 mW, one throughput unit is equal to 0.5 MIPS, and one delay unit is equal to 50 ms. Parameter values are based on the XSM mote (, , and denote the power consumption, throughput, and delay, respectively, in state )

Our selection of the state parameter values in Table 8.2 corresponds to XSM mote specifications [193, 316]. The XSM mote's Atmel ATmega128L microprocessor has an operating voltage range of 2.7–5.5 V and a processor frequency range of 0–8 MHz. The ATmega128L throughput varies with processor frequency at 1 MIPS/MHz, thus allowing an application manager to optimize power consumption versus processing speed [192]. Our chosen sensing frequency also corresponds with standard sensor node specifications. The Honeywell HMC1002 magnetometer sensor [320] consumes on average 15 mW of power and can be sampled in 0.1 ms on the Atmel ATmega128L microprocessor, which results in a maximum sampling frequency of approximately 10 kHz (10,000 samples/s). The acoustic sensor embedded in the XSM mote has a maximum sensing frequency of approximately 8.192 kHz [315]. Although the power consumption in a state depends not only on the processor voltage and frequency but also on the processor utilization, which also depends on sensing frequency, we report the average power consumption values in a state as derived from the data sheets [193, 322].

Table 8.3 summarizes the minimum and maximum reward function parameter values for application metrics (power, throughput, and delay) and the associated weight factors for a security/defense system, health care, and ambient conditions monitoring application. Our selected reward function parameter values represent typical application requirements [81]. We describe later the relative importance of these application metrics with respect to our considered applications.

Notation	Security/defense	Health care	Ambient monitoring
	12 units	8 units	5 units
	35 units	20 units	32 units
	6 units	3 units	2 units
	12 units	9 units	8 units
	7 units	8 units	12 units
	16 units	20 units	40 units
	0.45	0.5	0.65
	0.2	0.3	0.15
	0.35	0.2	0.2

and denote minimum and maximum acceptable power consumption, respectively; and denote minimum and maximum acceptable throughput, respectively; and denote minimum and maximum acceptable delay, respectively; , , and denote the weight factors for power, throughput, and delay, respectively.

Although power is a primary concern for all EWSN applications and tolerable power consumption values are specified based on the desired EWSN lifetime considering limited battery resources of sensor nodes. However, a relative importance in power for different applications can be delineated mainly by the infeasibility of sensor node's battery replacement due to hostile environments. For example, sensor nodes in a war zone for a security/defense application and an active volcano monitoring application make battery replacement almost impractical. For a healthcare application with sensors attached to a patient to monitor physiological data (e.g., heart rate, glucose level), sensor node's battery may be replaced though power is constrained because excessive heat dissipation could adversely affect a patient's health. Similarly, delay can be an important factor for security/defense in case of enemy target tracking and health care for a patient in intensive health conditions, whereas delay may be relatively less important for a humidity monitoring application. A data-sensitive security/defense system may require a comparatively large minimum throughput in order to obtain a sufficient number of sensed data samples for meaningful analysis. Although relative importance and minimum and maximum values of these application metrics can vary widely with an application domain and between application domains, we pick our parameter values (Table 8.3) for demonstration purposes to provide an insight into our optimization methodology.

We point out that all of our considered application metrics specifically throughput depends on the traffic pattern. EWSN throughput is a complex function of the number of nodes, traffic volume and patterns, and the parameters of the medium access technique. As the number of nodes and traffic volume increases, contention-based medium access methods result in an increased number of packet collisions, which waste energy without transmitting useful data. This contention and packet collision results in saturation, which decreases the effective throughput and increases the delay sharply. We briefly outline the variance in EWSN traffic patterns for our considered applications. The security/defense application would have infrequent bursts of heavy traffic (e.g., when an enemy target appears within the sensor nodes' sensing range), healthcare applications would have a steady flow of medium-to-high traffic, and ambient conditions monitoring applications would have a steady flow of low-to-medium traffic except for emergencies (e.g., volcano eruption). Although modeling of application metrics with respect to traffic patterns would result in a better characterization of these metric values at particular instants/times in WSN, these metric values can still be bounded by a lower minimum value and an upper maximum value as captured by our reward functions (Section 8.3.5).

Given the reward function, sensor node state parameters corresponding to XSM mote, and transition probabilities, our MATLAB MDP tool box [318] implementation of policy iteration algorithm solves Bellman's equation (8.18) to determine the MDP-based policy and determines the expected total discounted reward (Eq. (8.10)).

8.6.3 Results for a Security/Defense System Application

8.6.3.1 The Effects of Different Discount Factors on the Expected Total Discounted Reward

Table 8.4 and Fig. 8.5 depict the effects of different discount factors on the heuristic policies and for a security/defense system when the state transition cost is held constant at 0.1 for , and , and are equal to 0.45, 0.2, and 0.35, respectively. Since we assume the time between successive decision epochs to be 1 h, the range of from 0.94 to 0.99999 corresponds to a range of average sensor node lifetime from 16.67 to 100,000 h days years. Table 8.4 and Fig. 8.5 show that results in the highest expected total discounted reward for all values of and corresponding average sensor node lifetimes.

Discount factor	Sensor lifetime (h)
0.94	16.67	10.0006	7.5111	9.0778	7.2692	7.5586
0.95	20	12.0302	9.0111	10.9111	8.723	9.0687
0.96	25	15.0747	11.2611	13.6611	10.9038	11.3339
0.97	33.33	20.1489	15.0111	18.2445	14.5383	15.1091
0.98	50	30.2972	22.5111	27.4111	21.8075	22.6596
0.99	100	60.7422	45.0111	54.9111	43.6150	45.3111
0.999	1000	608.7522	450.0111	549.9111	436.15	453.0381
0.9999	10,000
0.99999	100,000

if ,

Figure 8.6 shows the percentage improvement in expected total discounted reward for for a security/defense system as compared to the fixed heuristic policies. The percentage improvement is calculated as where denotes the expected total discounted reward for and denotes the expected total discounted reward for the fixed heuristic policy where = {POW, THP, EQU, PRF}. For instance, when the average sensor node lifetime is 1000 h (), results in a 26.08%, 9.67%, 28.35%, and 25.58% increase in expected total discounted reward compared to , , , and , respectively. Figure 8.6 also depicts that shows increased savings as the average sensor node lifetime increases due to an increase in the number of decision epochs and thus prolonged operation of sensor nodes in optimal/suboptimal states as prescribed by . On average over all discount factors , results in a 25.57%, 9.48%, 27.91%, and 25.1% increase in expected total discounted reward compared to , , , and , respectively.

8.6.3.2 The Effects of Different State Transition Costs on the Expected Total Discounted Reward

Figure 8.7 depicts the effects of different state transition costs on the expected total discounted reward for a security/defense system with a fixed average sensor node lifetime of 1000 h () and , and equal to 0.45, 0.2, and 0.35, respectively. Figure 8.7 shows that results in the highest expected total discounted reward for all transition cost values.

Figure 8.7 also shows that the expected total discounted reward for is relatively unaffected by state transition cost. This relatively constant behavior can be explained by the fact that our MDP policy does not perform many state transitions. Relatively few state transitions to reach the optimal/suboptimal state according to the specified application metrics may be advantageous for some application managers who consider the number of state transitions prescribed by a policy as a secondary evaluation criteria [299]. performs state transitions primarily at sensor node deployment or whenever a new MDP-based policy is determined as the result of changes in application requirements.

We further analyze the effects of different state transition costs on the fixed heuristic policies, which consistently result in a lower expected total discounted reward as compared to . The expected total discounted rewards for and are relatively unaffected by state transition cost. The explanation for this behavior is that these heuristics perform state transitions only at initial sensor node deployment when the sensor node transitions to the lowest power state and the highest throughput state, respectively, and remain in these states for the entire sensor node's lifetime. On the other hand, state transition cost has the largest affect on the expected total discounted reward for due tohigh state transition rates because the policy spends an equal amount of time in all states. Similarly, high switching costs have a large affect on the expected total discounted reward for (although less severely than ) because spends a certain percentage of time in each available state (Section 8.6.1), thus requiring comparatively fewer transitions than .

8.6.3.3 The Effects of Different Reward Function Weight Factors on the Expected Total Discounted Reward

Figure 8.8 shows the effects of different reward function weight factors on the expected total discounted reward for a security/defense system when the average sensor node lifetime is 1000 h () and the state transition cost is held constant at 0.1 for . We explore various weight factors that are appropriate for different security/defense system specifics, that is, . Figure 8.8 reveals that results in the highest expected total discounted reward for all weight factor variations.

8.6.4 Results for a Healthcare Application

8.6.4.1 The Effects of Different Discount Factors on the Expected Total Discounted Reward

Figure 8.9 depicts the effects of different discount factors for a healthcare application when the state transition cost is held constant at 0.1 for , and , and are equal to 0.5, 0.3, and 0.2, respectively. Figure 8.9 shows that results in the highest expected total discounted reward for all values of and the corresponding average sensor node lifetimes as compared to other fixed heuristic policies.

Figure 8.10 shows the percentage improvement in expected total discounted reward for for a healthcare application as compared to the fixed heuristic policies. For instance, when the average sensor node lifetime is 1000 h (), results in a 16.39%, 10.43%, 27.22%, and 21.47% increase in expected total discounted reward compared to , , , and , respectively. On average over all discount factors , results in a 16.07%, 10.23%, 26.8%, and 21.04% increase in expected total discounted reward compared to , , , and , respectively.

8.6.4.2 The Effects of Different State Transition Costs on the Expected Total Discounted Reward

Figure 8.11 shows the effects of different state transition costs on the expected total discounted reward for a healthcare application with a fixed average sensor node lifetime of 1000 h () and , and equal to 0.5, 0.3, and 0.2, respectively. Figure 8.11 shows that results in the highest expected total discounted reward for all transition cost values. The fixed heuristic policies consistently result in a lower expected total discounted reward as compared to . Comparison of Figs. 8.7 and 8.11 reveals that a security/defense system and a healthcare application have similar trends with respect to different state transition costs on the expected total discounted reward.

8.6.4.3 The Effects of Different Reward Function Weight Factors on the Expected Total Discounted Reward

Figure 8.12 depicts the effects of different reward function weight factors on the expected total discounted reward for a healthcare application when the average sensor node lifetime is 1000 h () and the state transition cost is kept constant at 0.1 for . We explore various weight factors that are appropriate for different healthcare application specifics (i.e., ). Figure 8.12 shows that results in the highest expected total discounted reward for all weight factor variations.

Figures 8.8 and 8.12 show that the expected total discounted reward of gradually increases as the power weight factor increases and eventually exceeds that of for a security/defense system and a healthcare application, respectively. However, close observation reveals that the expected total discounted reward of for a security/defense system is affected more sharply than a healthcare application because of the more stringent constraint on maximum acceptable power for a healthcare application (Table 8.3). Figures 8.8 and 8.12 show that tends to perform better than with increasing power weight factors because spends a greater percentage of time in low power states.

8.6.5 Results for an Ambient Conditions Monitoring Application

8.6.5.1 The Effects of Different Discount Factors on the Expected Total Discounted Reward

Figure 8.13 demonstrates the effects of different discount factors for an ambient conditions monitoring application when the state transition cost is held constant at 0.1 for , and , and are equal to 0.65, 0.15, and 0.2, respectively. Figure 8.13 shows that results in the highest expected total discounted reward for all values of .

Figure 8.14 shows the percentage improvement in expected total discounted reward for for an ambient conditions monitoring application as compared to the fixed heuristic policies. For instance, when the average sensor node lifetime is 1000 h (), results in a 8.77%, 52.99%, 40.49%, and 32.11% increase in expected total discounted reward as compared to , , , and , respectively. On average over all discount factors , results in a 8.63%, 52.13%, 39.92%, and 31.59% increase in expected total discounted reward as compared to , , , and , respectively.

8.6.5.2 The Effects of Different State Transition Costs on the Expected Total Discounted Reward

Figure 8.15 depicts the effects of different state transition costs on the expected total discounted reward for an ambient conditions monitoring application with a fixed average sensor node lifetime of 1000 h () and , and equal to 0.65, 0.15, and 0.2, respectively. Figure 8.15 reveals that results in the highest expected total discounted reward for all transition cost values. The fixed heuristic policies consistently result in a lower expected total discounted reward as compared to . Figure 8.15 reveals that the ambient conditions monitoring application has similar trends with respect to different state transition costs as compared to the security/defense system (Fig. 8.7) and healthcare applications (Fig. 8.7).

8.6.5.3 The Effects of Different Reward Function Weight Factors on the Expected Total Discounted Reward

Figure 8.16 shows the effects of different reward function weight factors on the expected total discounted reward for an ambient conditions monitoring application when the average sensor node lifetime is 1000 h () and the state transition cost is held constant at 0.1 for . We explore various weight factors that are appropriate for different ambient conditions monitoring application specifics (i.e., ). Figure 8.16 reveals that results in the highest expected total discounted reward for all weight factor variations.

For an ambient conditions monitoring application, Fig. 8.16 shows that the expected total discounted reward of becomes closer to as the power weight factor increases, because with higher power weight factors, spends more time in lower power states to meet application requirements. Figure 8.16 shows that tends to perform better than with increasing power weight factors similar to the security/defense system (Fig. 8.8) and healthcare applications (Fig. 8.16).

8.6.6 Sensitivity Analysis

An application manager can assign values to MDP reward function parameters, such as , , , , , , , , , and , before an EWSN's initial deployment according to projected/anticipated application requirements. However, the average sensor node lifetime (calculated from ) may not be accurately estimated at the time of initial EWSN deployment, as environmental stimuli and wireless channel conditions vary with time and may not be accurately anticipated. The sensor node's lifetime depends on sensor node activity (both processing and communication), which varies with the changing environmental stimuli and wireless channel conditions. Sensitivity analysis analyzes the effects of changes in average sensor node lifetime after initial deployment on the expected total discounted reward. Thus, if the actual lifetime is different than the estimated lifetime, what is the loss in total expected discounted reward if the actual lifetime had been accurately predicted at deployment.

EWSN sensitivity analysis can be carried out with the following steps [299]:

1. 1. Determine the expected total discounted reward given the actual average sensor node lifetime , referred to as the Optimal Reward .
2. 2. Let denote the estimated average sensor node lifetime, and denote the percentage change from the actual average sensor node lifetime (i.e., ). results in a suboptimal policy with a corresponding suboptimal total expected discounted reward, referred to as Suboptimal Reward .
3. 3. The Reward Ratio is the ratio of the suboptimal reward to the optimal reward (i.e., ), which indicates suboptimal expected total discounted reward variation with the average sensor node lifetime estimation inaccuracy.

It can be shown that the reward ratio varies from (0, 2] as varies from (100%, 100%]. The reward ratio's ideal value is 1, which occurs when the average sensor node lifetime is accurately estimated/predicted ( corresponding to ). Sensitivity analysis revealed that our MDP-based policy is sensitive to accurate determination of parameters, especially average lifetime, because inaccurate average sensor node lifetime results in a suboptimal expected total discounted reward. The dynamic profiler module (Fig. 8.1) measures/profiles the remaining battery energy (lifetime) and sends this information to the application manager along with other profiled statistics (Section 8.2.1), which helps inaccurate estimation of . Estimating using the dynamic profiler's feedback ensures that the estimated average sensor node lifetime differs only slightly from the actual average sensor node lifetime, and thus helps in maintaining a reward ratio close to 1.

8.6.7 Number of Iterations for Convergence

The policy iteration algorithm determines and the corresponding expected total discounted reward on the order of , where is the total number of states. In our numerical results with four sensor node states, the policy iteration algorithm converges in two iterations on average.