PaperlayerView exact revision on arXiv

Source-linked AI summary

Markov Decision Processes with Applications in Wireless Sensor Networks: A Survey

Mohammad Abu Alsheikh, Dinh Thai Hoang, Dusit Niyato, Hwee-Pink Tan, Shaowei Lin

arXiv:1501.00644v1cs.NI

TL;DR

Wireless sensor networks need adaptive decisions despite limited resources and stochastic operating conditions. This survey reviews how MDPs model and optimize WSN operations, compares solution methods, and identifies practical boundaries including implementation difficulty and costly exploration.

  • Problem

    WSNs must support data exchange, topology formation, resource optimization, sensing, tracking, and security while operating with limited resources in stochastic environments.

  • Method

    The survey organizes MDP applications and extensions for WSNs, reviews solution methods, and discusses their advantages and disadvantages.

  • Results

    The reviewed literature demonstrates MDP use across data exchange, topology formation, resource and power optimization, sensing and tracking, and security applications.

  • Takeaways & Limitations

    MDPs provide a decision-making framework for developing adaptive WSN algorithms and protocols across diverse design and resource-management problems.

Abstract

from arXiv · show

Wireless sensor networks (WSNs) consist of autonomous and resource-limited devices. The devices cooperate to monitor one or more physical phenomena within an area of interest. WSNs operate as stochastic systems because of randomness in the monitored environments. For long service time and low maintenance cost, WSNs require adaptive and robust methods to address data exchange, topology formulation, resource and power optimization, sensing coverage and object detection, and security challenges. In these problems, sensor nodes are to make optimized decisions from a set of accessible strategies to achieve design goals. This survey reviews numerous applications of the Markov decision process (MDP) framework, a powerful decision-making tool to develop adaptive algorithms and protocols for WSNs. Furthermore, various solution methods are discussed and compared to serve as a guide for using MDPs in WSNs.

I. INTRODUCTION

WSNs require adaptive decision-making because resource-limited nodes operate in stochastic environments and must support diverse network objectives. The survey presents MDPs as a framework for modeling these decisions and reviews applications, extensions, and solution methods.

  • Motivation: WSNs use autonomous, battery-powered nodes whose limited resources and stochastic environments require adaptive, energy-efficient operation.Nodes interact with changing surroundings through state-dependent actions, such as sleeping radios or adjusting operational strategies.
  • Benefits for WSNs: MDPs support dynamic resource optimization, multiple-objective design, prediction of mobile entities, and policy implementation through look-up tables.Examples include adaptive transmit-power control, balancing energy consumption with sensing coverage, and predicting moving-object locations.
  • Survey scope: The survey classifies MDP applications into data exchange and topology formation, resource and power optimization, sensing coverage and event tracking, and security and intrusion detection.It also reviews algorithms that trade off energy consumption against solution optimality and discusses advantages and disadvantages of solution methods.
  • Survey scope: Unlike Markov chains, which support performance analysis without actions and rewards, MDPs enable stochastic optimization of actions for specified objectives.The survey therefore focuses on MDP applications rather than the broader use of Markov chains in WSNs.
  • Paper organization: The paper introduces the MDP framework and solution methods before surveying applications and concluding with future directions and open research problems.The application discussions cover Sections III–VII, while future directions appear in Section VIII and the conclusion in Section IX.
  • MDP framework: MDPs model sensor nodes as agents that choose actions in states, receive rewards, and transition probabilistically to new states.The model represents states, actions, transition probabilities, immediate rewards, and decision epochs, with a policy mapping states to actions.

B. Solutions of MDPs

The paper presents solution approaches for finite-horizon MDPs based on Bellman optimality equations. Backward induction works from a known terminal state, whereas forward induction proceeds from a known initial state; both depend on the time horizon.

  • Finite-horizon formulation: Finite-horizon MDPs operate over a known period and seek a policy that maximizes the value function from the initial state.The optimal value at each state can be computed recursively using Bellman’s optimal equations.
  • Solution approaches: Two typical finite-horizon approaches are backward induction and forward induction.Both derive optimal actions from Bellman equations but differ in the direction of computation.
  • Backward induction: Backward induction computes the optimal action and value at the final period, then recursively solves earlier periods.It is especially useful when the MDP state in the last period is known.
  • Forward induction: Forward induction divides the problem by steps remaining, computes Q-values, and derives the optimal policy until the last period.It is applied when only the initial state is known.
  • Comparison: Both induction approaches have complexity that depends on the MDP time horizon, although their use depends on which endpoint state is known.Backward induction uses terminal-state information, while forward induction uses initial-state information.

2) Solutions for Infinite Time Horizon Markov Decision Processes:

Infinite-horizon MDPs require iterative or approximate solution methods because operation time is often unknown and assumed infinite. The survey contrasts value, policy, linear-programming, approximation, and online-learning approaches, then reviews extensions for partial observability and multiple agents.

  • Infinite-horizon MDPs are widely used because practical system operation times are often unknown and assumed to be infinite.
  • Solution methods: Value iteration repeatedly updates value estimates until a stopping criterion guarantees convergence, making it useful for large discounted state spaces.The survey describes value iteration as efficiently implemented and quick to converge.
  • Solution methods: Policy iteration alternates policy evaluation with policy improvement, generating an improving sequence from an arbitrary initial policy.
  • Solution methods: Linear programming finds a static policy through a linear program and is useful when constraints can be expressed as linear equations, though it is relatively inefficient for large state spaces.
  • Solution methods: Approximate dynamic programming represents value or policy functions with parameters, while online learning uses simulated agent–system interaction when transition probabilities are unknown.
  • MDP extensions: POMDPs replace unobservable state histories with belief states, whereas MMDPs model cooperating agents with full system observation but rapidly expanding joint spaces.

4) Stochastic Games (SGs):

The surveyed WSN applications use Markov models to address unreliable, changing network conditions through adaptive routing, aggregation, transmission, and topology decisions. These approaches balance resource and performance objectives, but mobile-network implementations and distributed learning can remain costly.

  • Stochastic Games (SGs): Stochastic games model non-cooperative agents that rationally maximize individual payoffs, making optimal strategies complex when objectives conflict.
  • Data exchange and topology maintenance: WSN links can degrade over time, while MDPs model temporal correlation in network structure and support adaptive data exchange and topology maintenance.
  • Data aggregation and routing: MDP-based data aggregation and routing selects energy-efficient sensor alternatives while incorporating metrics such as transmission delay, energy consumption, and expected congestion.
  • Opportunistic transmission: Adaptive transmission strategies select minimum transmit power to reach destinations, reducing energy consumption and interference among nodes.
  • Relay selection: Relay-selection decisions use location and distance information to reduce energy consumption at relay and source nodes.
  • Mobile Wireless Sensor Networks (MWSNs): Distributed mobile-sensor algorithms are hard to implement and maintain, while distributed MDPs may require costly, long-lived exploration before convergence.

3) Delay-Energy Tradeoff:

MDP-based transmission methods adapt forwarding, power, scheduling, and redundancy decisions to balance energy use, delay, reliability, and connectivity in changing WSN conditions.

  • Controlled-power opportunistic routing selects forwarding nodes and power levels to reduce energy consumption, interference, and end-to-end delay.
  • Adaptive distributed transmission policies use channel, traffic, and buffer information to choose transmit power and modulation while avoiding buffer overflow.
  • 2x throughput was achieved over a simple SIR-matching policy by the adaptive policy of Pandana and Liu.
  • A distributed threshold policy for slotted ALOHA reaches Nash equilibrium, with channel-access probability decreasing as network size increases.
  • Discrete-time models constrain critically time-sensitive applications because nodes remain in states for fixed intervals; continuous-time models and SMDPs are proposed as a direction.
  • Scheduling MDPs choose between waiting for a mobile sink and immediate multihop transmission, while redundant transmission selects cross-layer FEC–ARQ protocols for time-varying channels.

3) Wireless Transmit Power:

MDP variants are applied to wireless transmit-power, relay-selection, and topology decisions under changing channel, energy, and network conditions. The reviewed methods trade energy use, delay, connectivity, and information availability, but most rely on full neighbor information and lack long-running real-world validation.

  • Wireless Transmit Power: POMDP-based transmit control uses partial interference information to choose transmission energy, waiting, or channel probing actions.Successful transmissions can indicate an idle channel, helping nodes increase transmission probability during idle periods.
  • Wireless Transmit Power: Centralized MDP energy configuration manages transmission behavior using complete battery and channel information to support network lifetime, connectivity, and operation.The backend requires no local information exchange among nodes.
  • Relay Selection and Scheduling: Relay selection evaluates direct transmission and relay paths using source and relay energy, maximum transmission range, and connectivity requirements.MDPs are used to compare relay paths with direct-link decisions when suitable relays are unavailable.
  • Relay Selection and Scheduling: Energy-harvesting relay selection can formulate partial observability and relax the POMDP to an MDP, with states representing energy budgets and event occurrence.The source fully observes its own state but has only partial information about other relays.
  • Summary: Most reviewed data-exchange and topology methods favor fully observable MDPs for lower computational burden, but beacon exchange increases transmission overhead.The survey also notes that most studies lack long-running real-world testbed or deployment experiments under changing conditions.

IV. RESOURCE AND POWER OPTIMIZATION

MDPs support resource and power optimization across energy control, dynamic protocol operation, duty cycling, and energy harvesting. These methods adapt decisions to battery, traffic, channel, and environmental conditions while balancing energy use with delay, throughput, data delivery, or monitoring quality.

  • Overview: Resource optimization targets limited node energy, bandwidth, and computation, with surveyed work emphasizing long network lifetime.The survey groups applications into energy control, dynamic optimization, and duty cycling or channel-access scheduling.
  • Energy Control: MDPs schedule charging order and timing by accounting for battery charging or discharging, available energy, and stochastic energy harvesting.Energy-harvesting nodes can be scheduled for tasks that fit their expected harvested energy.
  • Energy Control: Charging-management models address unequal energy drain across nodes and can minimize recharge delay while maximizing the number of recharged nodes.Nodes near the sink may drain faster because they relay other nodes’ data.
  • Energy Harvesting: Energy-harvesting spectrum-access schemes use POMDPs to choose access decisions from partial spectrum and battery information.Some controllers build beliefs from past transmission outcomes and battery charging or discharging behavior.
  • Future Directions: Future directions include constrained spectrum access with waiting-time bounds for fairness and delay control, and stochastic games for non-cooperative algorithms.The survey also identifies event occurrence and data priority as extensions for delivering important packets at low energy.
  • Energy Harvesting: Adaptive data gathering balances lossy compression against sensor energy budgets, using energy efficiency, data importance, and current energy to avoid battery overflow and drainage.The optimal policy is obtained with policy iteration.

B. Dynamic Optimization and Resource Allocation

MDP-based dynamic optimization allocates tasks, manages maintenance, and configures WSN hardware and protocols under heterogeneous resources and changing operating conditions. The reviewed approaches address energy, deadlines, network performance, and operational cost, but harsh environments remain challenging.

  • Dynamic Optimization and Resource Allocation: Task scheduling in heterogeneous WSNs uses MDPs to assign parallel tasks while considering node energy consumption, deadlines, and task dependencies.More resourceful nodes may finish sooner but consume more energy.
  • Dynamic Optimization and Resource Allocation: Maintenance policies decide which nodes to replace by balancing network operation, replacement cost, and the number of drained nodes.Replacing more sensors can reduce the cost per sensor, while the objective is to maintain operation with minimum replacements.
  • Dynamic Optimization and Resource Allocation: MDP-based computer-aided design selects hardware configurations for deployment requirements instead of relying on complex design-space simulation analysis.The modeled design solutions include components such as CPUs, memories, and radio transceivers.
  • Dynamic Optimization and Resource Allocation: Dynamic protocol-optimization methods adjust routing, data aggregation, and topology control using metrics including delay, energy consumption, and data consistency.Actions include idle mode, event listening, sampling, and packet aggregation.
  • Limitations: Changing weather, wireless channels, and interference models make dynamic configuration and lifetime modeling particularly challenging outdoors and in harsh environments.The limitation concerns the stability of the operating conditions assumed by these algorithms.

C. Duty Cycling and Medium Access Control (MAC)

MDP, POMDP, and game-based methods manage duty cycling and medium access by adapting node activation, channel access, contention, and transmission timing. The surveyed protocols target energy savings, connectivity, throughput, delay, and scalability while facing overhead and complexity constraints.

  • Duty Cycling: Duty cycling addresses wasted energy from simultaneous node activation by managing active and sleep modes.This is especially relevant when all sensors attached to a human body would otherwise remain continuously active.
  • Duty Cycling: An MDP duty-cycling algorithm uses available energy to maintain connected active nodes with the highest energy budgets.Nodes broadcast their available energy, making full information available for activation decisions.
  • Medium Access Control: Stochastic-game MAC protocols let nodes transmit, listen, or sleep while dynamically tuning contention parameters such as backoff time or contention-window size.These methods model competing nodes as opponents sharing channel access.
  • Medium Access Control: MDP channel-access models use channel-state representations such as quantized SNR ranges to select access times and predict future fading states.When transitions are limited to neighboring states, the transmission matrix is tridiagonal.
  • Medium Access Control: The proposed backoff algorithm improves scalability as node counts increase, whereas conventional MAC transmission rates decrease beyond about 20 nodes.The comparison concerns performance at increased network size.
  • Medium Access Control: Hybrid CSMA/CA-TDMA designs use buffer occupancy and rewards combining energy, bandwidth, and throughput to select transmission or waiting policies.Actions distinguish contention access, contention-free access, both periods, and waiting.
  • Limitations: Offline policy updates can require costly redistribution after network changes, while stochastic-game solutions become computationally critical in large WSNs.These constraints limit adaptation and scalability of MAC management approaches.

V. SENSING COVERAGE AND OBJECT DETECTION

MDP and POMDP models support sensing coverage, target detection, and rescue-area planning by adapting node activation, movement, and camera actions under uncertainty. Reviewed rescue applications remain insufficiently validated in real-world environments.

  • Coverage Applications: MDPs predict the minimum active nodes or movement strategies needed to maintain sensing coverage over time.
  • Coverage Applications: Detection-probability requirements generally determine how many sensors must remain active for object tracking.
  • Coverage Applications: POMDP-based camera control balances zoomed-in high-resolution views of small areas against zoomed-out views of larger areas.
  • Area Coverage in Rescue Applications: In corridor scenarios, deploying more relay sensors decreased total network energy consumption while maintaining connectivity objectives.
  • Area Coverage in Rescue Applications: Real-world testbed and deployment experiments are still needed before MDP-based rescue systems are used in practical cases.

B. Target Tracking and Localization

MDP-based target tracking and localization methods coordinate sensor activation, prediction, and transmission decisions to balance detection quality with constrained energy and spectrum resources. The surveyed approaches include centralized, hierarchical, partially observable, and game-based designs.

  • Target Tracking and Localization: MDP-based tracking methods use predicted object activity and location to trigger sensor and alarm activation while addressing energy efficiency.
  • Target Tracking and Localization: The malicious-object localization policy activates nodes whose detection regions maximize detection, achieving localization error below 0.3 relative to coverage radius in grid simulations.
  • Target Tracking and Localization: A POMDP optimizes energy and detection efficiency for overlapped and non-overlapped sensor deployments using beliefs about object locations.
  • Target Tracking and Localization: The surveyed centralized tracking and detection algorithms require offline learning at a central unit, creating data-gathering and computation costs.
  • Target Tracking and Localization: Hierarchical tracking divides target prediction among lower-level agents and activation management among higher-level cluster-head agents.

3) Multiple Target Tracking:

The survey extends MDP applications across health monitoring, indoor asset localization, prioritized target-tracking delivery, and security. These methods manage activation, sensing, forwarding, and attack response under resource and information constraints.

  • Multiple Target Tracking: A POMDP schedules biometric sensors to balance detection performance and sensor lifespan under noisy outputs.
  • Multiple Target Tracking: Indoor asset-localization coverage is affected by walls and equipment, motivating agent-based path planning for retrieving medical assets.
  • Multiple Target Tracking: Selective dropping of unimportant samples remarkably extends network lifetime and minimizes total energy consumption versus forwarding all samples.
  • Multiple Target Tracking: The reviewed coverage and detection literature still needs real-world experiments and more general deployment distributions beyond commonly used grid topologies.
  • Multiple Target Tracking: MDP-based intrusion detection includes vulnerable-node identification, attack-pattern prediction, and security actions based on positive or negative rewards.
  • Multiple Target Tracking: A stochastic-game attack model reports that MTTF decreases as attacking probabilities increase, while survival lifetime is proportional to node count.

B. Resource Starvation Attacks

Security applications use adaptive MDP, stochastic-game, and self-management approaches for resource starvation, jamming, coordinator protection, and specialized WSN operation. Reported designs select defenses dynamically but remain part of a relatively small literature.

  • Resource Starvation Attacks: Packet-denial protection uses acknowledgments from a randomly selected subset of nodes to counter broadcast-message suppression.
  • Resource Starvation Attacks: An MDP-based jamming framework dynamically selects an anti-jamming method according to the characteristics of the current attack.
  • Resource Starvation Attacks: A stochastic-game coordinator-selection mechanism improves total throughput and network lifetime by choosing a new unattacked coordinator in jamming scenarios.
  • Resource Starvation Attacks: The existing literature on MDP-based security methods is relatively small, although stochastic games and fully observable MDPs are identified for security monitoring and channel-jamming prevention.
  • Custom WSN Applications: MDP applications also address camera QoS, road monitoring, unattended networks, threat transmission timing, and maintenance after node or link faults.

D. Agriculture Wireless Sensor Networks

MDP applications in WSNs include agricultural sensing, vehicular data collection, and methods for representing complex state spaces. The surveyed approaches also expose practical assumptions and unresolved scalability challenges.

  • Agriculture sensing: A POMDP-based soil-moisture scheme schedules sparse sampling while modeling noiseless sensors in active or sleep modes.The formulation converts the problem into an infinite-horizon MDP structure under these assumptions.
  • Vehicular networks: Vehicular sensor networks use moving vehicles to collect sensor data, while MDPs address relay-buffer allocation and data-routing decisions.Buffer allocation seeks fair service among source nodes, and routing accounts for vehicle speed, distribution, delivery delay, and link conditions.
  • Solution methods: Large state or action spaces commonly require approximate rather than standard direct MDP solution methods.The survey identifies approximate solutions as a way to reduce the complexity of MDP-based WSN methods.
  • State abstraction: Self-organizing maps can transform continuous sensory inputs into distinctive MDP states by learning correlations among state parameters from historical data.The illustrated map uses a 4D input space, 12 output classes, a 2D lattice, and offline competitive learning.
  • Open challenges: MDP state formulation in WSNs remains insufficiently explored, limiting direct handling of continuous and discrete state values in practical applications.Further exploration is presented as a way to reduce the complexity of solving MDP problems.

2) Learning Unknown Parameters:

The survey identifies unresolved challenges and emerging opportunities for applying MDPs in WSNs and related systems. It highlights learning, distributed coordination, cross-layer optimization, spectrum sharing, privacy, and scalable IoT decision-making.

  • Learning unknown parameters: When transition probabilities and rewards are unknown, learning algorithms or robust MDPs can estimate uncertain modeling parameters from historical data.Robust MDPs are especially suited to settings where long-term expected reward is sensitive to estimation errors.
  • Distributed decision-making: Distributed and multi-agent MDP solutions often assume that sensor nodes observe one another through information exchange or a central coordinator.The survey identifies this observability and coordination assumption as potentially inapplicable in practical contexts.
  • Cross-layer optimization: MDPs can support cross-layer optimization by handling multiple objectives such as end-to-end delay, bandwidth usage, and loss rate.Cross-layer architectures allow protocols at different layers to interact.
  • Cognitive radio sensor networks: Cognitive-radio sensor networks offer further opportunities for MDP-based dynamic spectrum access, including quality-of-service-aware routing.Existing studies have considered centralized coordination, while additional applications remain open.
  • Summary: The survey concludes by reviewing MDP applications across data exchange, topology formation, resource and power optimization, coverage, tracking, security, and intrusion detection.It also identifies research directions for future study.
Loading 1501.00644v1…