Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks
Wakeup scheduling has been widely used in wireless sensor networks (WSNs), for it can reduce the energy wastage caused by the idle listening state. In a traditional wakeup scheduling, sensor nodes start up numerous times in a period, thus consuming extra energy due to state transitions (e.g., from t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi - SAGE Publishing
2012-02-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2012/525909 |
| _version_ | 1797762589048963072 |
|---|---|
| author | Junchao Ma Wei Lou |
| author_facet | Junchao Ma Wei Lou |
| author_sort | Junchao Ma |
| collection | DOAJ |
| description | Wakeup scheduling has been widely used in wireless sensor networks (WSNs), for it can reduce the energy wastage caused by the idle listening state. In a traditional wakeup scheduling, sensor nodes start up numerous times in a period, thus consuming extra energy due to state transitions (e.g., from the sleep state to the active state). In this paper, we address a novel interference-free wakeup scheduling problem called compact wakeup scheduling, in which a node needs to wake up only once to communicate bidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and it is NP-complete to decide whether a valid compact wakeup scheduling exists for an arbitrary graph. In particular, tree and grid topologies, which are commonly used in WSNs, have valid compact wakeup schedulings. We propose polynomial-time algorithms using the optimum number of time slots in a period for trees and grid graphs. Simulations further validate our theoretical results. |
| first_indexed | 2024-03-12T19:29:34Z |
| format | Article |
| id | doaj.art-5ee38d7a86b84169805d6678fd28b668 |
| institution | Directory Open Access Journal |
| issn | 1550-1477 |
| language | English |
| last_indexed | 2024-03-12T19:29:34Z |
| publishDate | 2012-02-01 |
| publisher | Hindawi - SAGE Publishing |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj.art-5ee38d7a86b84169805d6678fd28b6682023-08-02T04:39:02ZengHindawi - SAGE PublishingInternational Journal of Distributed Sensor Networks1550-14772012-02-01810.1155/2012/525909Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor NetworksJunchao MaWei LouWakeup scheduling has been widely used in wireless sensor networks (WSNs), for it can reduce the energy wastage caused by the idle listening state. In a traditional wakeup scheduling, sensor nodes start up numerous times in a period, thus consuming extra energy due to state transitions (e.g., from the sleep state to the active state). In this paper, we address a novel interference-free wakeup scheduling problem called compact wakeup scheduling, in which a node needs to wake up only once to communicate bidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and it is NP-complete to decide whether a valid compact wakeup scheduling exists for an arbitrary graph. In particular, tree and grid topologies, which are commonly used in WSNs, have valid compact wakeup schedulings. We propose polynomial-time algorithms using the optimum number of time slots in a period for trees and grid graphs. Simulations further validate our theoretical results.https://doi.org/10.1155/2012/525909 |
| spellingShingle | Junchao Ma Wei Lou Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks International Journal of Distributed Sensor Networks |
| title | Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks |
| title_full | Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks |
| title_fullStr | Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks |
| title_full_unstemmed | Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks |
| title_short | Interference-Free Wakeup Scheduling with Consecutive Constraints in Wireless Sensor Networks |
| title_sort | interference free wakeup scheduling with consecutive constraints in wireless sensor networks |
| url | https://doi.org/10.1155/2012/525909 |
| work_keys_str_mv | AT junchaoma interferencefreewakeupschedulingwithconsecutiveconstraintsinwirelesssensornetworks AT weilou interferencefreewakeupschedulingwithconsecutiveconstraintsinwirelesssensornetworks |