Maximizing Quality of Aggregation in WSNs Under Deadline and Interference Constraints
Explore strategies to improve data aggregation quality in wireless sensor networks under deadline and interference constraints. Topics include real-time communication, interference management, and maximizing Quality of Aggregation (QoA) under SINR. Challenges and solutions in meeting deadline-constrained aggregation tasks are discussed.
Uploaded on Mar 07, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Maximizing Quality of Aggregation in WSNs Under Deadline and Interference Constraints Hamed Yousefi*, Masoud Mehrabi Koushki , Bahram Alinia , and Kang G. Shin* *University of Michigan, University of British Columbia, Telecom SudParis Presenter: Kangjin Yoon @ Seoul National University
2 Real-time Data Aggregation Energy is a critical resource in WSNs Data aggregation has been used widely to save energy in tree-based WSNs Data aggregation is a time-consuming function Real-time communication is becoming more important in emerging apps Target tracking, environmental monitoring, health monitoring, and battlefield surveillance Real-time Data Aggregation!
3 Interference Interference is the main culprit for long aggregation latency at the sink Limit # of concurrent transmissions 2 primary objectives according to app needs: Minimum Latency Aggregation Scheduling (MLAS) Deadline-Constrained Aggregation Scheduling
4 Minimum Latency Aggregation Scheduling MLAS how fast information can be aggregated from a WSN? Studied extensively under different interference models! Some delay-sensitive apps can t even tolerate the latency obtained under MLAS how much information can be aggregated within the deadline? A fundamentally different problem in both objective function and constraint set!
5 Delay-constrained Aggregation Scheduling The imposed deadline doesn t allow participation of all sensor nodes in interference-free data aggregation Goal: Maximize # of participating sources (QoA) Question: how to schedule transmissions (and which nodes to participate) under deadline and interference constraints?
6 Maximizing QoA under SINR Existing work [1,2]: Only on simplest (i.e., one-hop) interference model Children of the same parent cannot transmit concurrently [1] Maximizing aggregated information in sensor networks under deadline constraints, IEEE Transactions on Automatic Control, 2011. [2] Maximizing quality of aggregation in delay-constrained wireless sensor networks, IEEE Communications Letters, 2013. Interference constraints are not local and pairwise, but global and additive! Physical interference model (SINR) makes existing solutions trivial or inapplicable Becomes much harder under SINR, an open problem!
7 Contributions Maximizing QoA under SINR NP-complete! A heuristic method for a sub-optimal solution (in two phases): (1) Maximize QoA under one-hop interference model: Optimally selects source participants (and gives the upper bound) Comes with major interferences in SINR due to global blindness! (2) Resolve the interferences efficiently (Main Contribution) Markov approximation framework + matching graph modification
8 Contributions (cont.) Maximizing QoA under SIC Goal: Maximize # of concurrent transmissions SIC (Successive Interference Cancellation) Breaks the rule of one-time slot-one-sender barrier in each parent Partitions children of the same parent into a few groups (meta-nodes) Nodes in each group transmit simultaneously An overlay view: Schedule a number of meta-nodes
9 Problem Formulation
10 SINR Solution A two-phase solution BASIC: finds the optimal solution under one-hop interference model Resolution: resolves the globally-imposed interferences iteratively A new configuration of participants and their schedules after each iteration
11 BASIC Finding X[i,Wi] is the core for both BASCI and Resolution Maximum Weighted Matching (MWM)
12 Resolution (Phase 1) Objective: find an interference-free set of links with maximum weighted sum in each slot Markov Approximation Resolution runs in two phases: (1) Random walk on Markov chain toward the state maximizing QoA Each Markov state corresponds to a possible permutation of concurrently transmitting nodes
13 Resolution (Phase 2) Resolution runs in two phases: (2) Run BASIC in each parent with a modified matching graph to update n and W
14 Matching Graph Modification and QoA Estimation Matching graph modification is the core Remove an interfering link (respecting to its priority in permutation) deadlines Search for possible replacements iteratively (Replacement Search) Terminate after finding maximum # of possible concurrent transmissions for each slot
15 Evaluation A custom simulator written in Python Sensor nodes are uniformly deployed in a 100m 100m region Objective: show how the underlying deadline and interference constraints hinder participation of all nodes in aggregation for different algorithms BASIC provides the optimal solution under the one-hop interference model (upper bound) [1] Maximizing aggregated information in sensor networks under deadline constraints, in IEEE Transactions on Automatic Control, 2011. SINR SINR-Simple is SINR, but without the replacement search phase SIC
16 Evaluation (cont.) . deadlines
17 Evaluation (cont.) .
18 Summary The first to address the problem of interference-free scheduling under physical interference model for maximizing QoA in deadline-constrained WSNs Proposed a sub-optimal scheduling (Markov approximation framework and matching graph modification for interference resolution) Coupled the problem (and solution) with SIC to improve QoA The proposed scheduling approaches are shown to be effective
Thanks hyousefi@umich.edu
SIC Solution Each parent s children are partitioned into a few meta-nodes ID-based grouping is used An overlay view: Schedule a number of meta-nodes The approach in the previous part is extended for wait assignment and then resolution of interfering meta-nodes Run BASIC to solve the problem under one-hop interference model Run Resolution on a slot-by-slot basis (Markov + Matching Graph Modification) Run BASIC in each parent with modified matching graph to update n and W 20
Resolution under SIC Regrouping is necessary in interfering meta-nodes Push the removed nodes in other groups as much as possible and make a new group for the remaining ones
