Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks

O. Durmaz, A. Ghosh, B. Krishnamachari, K. Chintalapudi

Research output: Book/ReportReportProfessional

105 Downloads (Pure)

Abstract

We explore the following fundamental question - how fast can information be collected from a wireless sensor network? We consider a number of design parameters such as, power control, time and frequency scheduling, and routing. There are essentially two factors that hinder efficient data collection - interference and the half-duplex single-transceiver radios. We show that while power control helps in reducing the number of transmission slots to complete a convergecast under a single frequency channel, scheduling transmissions on different frequency channels is more efficient in mitigating the effects of interference (empirically, 6 channels suffice for most 100-node networks). With these observations, we define a receiver-based channel assignment problem, and prove it to be NP-complete on general graphs. We then introduce a greedy channel assignment algorithm that efficiently eliminates interference, and compare its performance with other existing schemes via simulations. Once the interference is completely eliminated, we show that with half-duplex single-transceiver radios the achievable schedule length is lower-bounded by max(2nk − 1,N), where nk is the maximum number of nodes on any subtree and N is the number of nodes in the network. We modify an existing distributed time slot assignment algorithm to achieve this bound when a suitable balanced routing scheme is employed. Through extensive simulations, we demonstrate that convergecast can be completed within up to 50% less time slots, in 100-node networks, using multiple channels as compared to that with single-channel communication. Finally, we also demonstrate further improvements that are possible when the sink is equipped with multiple transceivers or when there are multiple sinks to collect data.
Original languageUndefined
Place of PublicationLos Angeles
PublisherUSC-Ceng
Number of pages9
Publication statusPublished - Sep 2008

Publication series

Name
PublisherUSC-Ceng
No.Supplement/CENG-2008-9

Keywords

  • EWI-13512
  • METIS-251201
  • IR-65004

Cite this

Durmaz, O., Ghosh, A., Krishnamachari, B., & Chintalapudi, K. (2008). Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks. Los Angeles: USC-Ceng.
Durmaz, O. ; Ghosh, A. ; Krishnamachari, B. ; Chintalapudi, K. / Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks. Los Angeles : USC-Ceng, 2008. 9 p.
@book{90007f1f78ee4f67a26a5ff5913e27bf,
title = "Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks",
abstract = "We explore the following fundamental question - how fast can information be collected from a wireless sensor network? We consider a number of design parameters such as, power control, time and frequency scheduling, and routing. There are essentially two factors that hinder efficient data collection - interference and the half-duplex single-transceiver radios. We show that while power control helps in reducing the number of transmission slots to complete a convergecast under a single frequency channel, scheduling transmissions on different frequency channels is more efficient in mitigating the effects of interference (empirically, 6 channels suffice for most 100-node networks). With these observations, we define a receiver-based channel assignment problem, and prove it to be NP-complete on general graphs. We then introduce a greedy channel assignment algorithm that efficiently eliminates interference, and compare its performance with other existing schemes via simulations. Once the interference is completely eliminated, we show that with half-duplex single-transceiver radios the achievable schedule length is lower-bounded by max(2nk − 1,N), where nk is the maximum number of nodes on any subtree and N is the number of nodes in the network. We modify an existing distributed time slot assignment algorithm to achieve this bound when a suitable balanced routing scheme is employed. Through extensive simulations, we demonstrate that convergecast can be completed within up to 50{\%} less time slots, in 100-node networks, using multiple channels as compared to that with single-channel communication. Finally, we also demonstrate further improvements that are possible when the sink is equipped with multiple transceivers or when there are multiple sinks to collect data.",
keywords = "EWI-13512, METIS-251201, IR-65004",
author = "O. Durmaz and A. Ghosh and B. Krishnamachari and K. Chintalapudi",
year = "2008",
month = "9",
language = "Undefined",
publisher = "USC-Ceng",
number = "Supplement/CENG-2008-9",

}

Durmaz, O, Ghosh, A, Krishnamachari, B & Chintalapudi, K 2008, Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks. USC-Ceng, Los Angeles.

Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks. / Durmaz, O.; Ghosh, A.; Krishnamachari, B.; Chintalapudi, K.

Los Angeles : USC-Ceng, 2008. 9 p.

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks

AU - Durmaz, O.

AU - Ghosh, A.

AU - Krishnamachari, B.

AU - Chintalapudi, K.

PY - 2008/9

Y1 - 2008/9

N2 - We explore the following fundamental question - how fast can information be collected from a wireless sensor network? We consider a number of design parameters such as, power control, time and frequency scheduling, and routing. There are essentially two factors that hinder efficient data collection - interference and the half-duplex single-transceiver radios. We show that while power control helps in reducing the number of transmission slots to complete a convergecast under a single frequency channel, scheduling transmissions on different frequency channels is more efficient in mitigating the effects of interference (empirically, 6 channels suffice for most 100-node networks). With these observations, we define a receiver-based channel assignment problem, and prove it to be NP-complete on general graphs. We then introduce a greedy channel assignment algorithm that efficiently eliminates interference, and compare its performance with other existing schemes via simulations. Once the interference is completely eliminated, we show that with half-duplex single-transceiver radios the achievable schedule length is lower-bounded by max(2nk − 1,N), where nk is the maximum number of nodes on any subtree and N is the number of nodes in the network. We modify an existing distributed time slot assignment algorithm to achieve this bound when a suitable balanced routing scheme is employed. Through extensive simulations, we demonstrate that convergecast can be completed within up to 50% less time slots, in 100-node networks, using multiple channels as compared to that with single-channel communication. Finally, we also demonstrate further improvements that are possible when the sink is equipped with multiple transceivers or when there are multiple sinks to collect data.

AB - We explore the following fundamental question - how fast can information be collected from a wireless sensor network? We consider a number of design parameters such as, power control, time and frequency scheduling, and routing. There are essentially two factors that hinder efficient data collection - interference and the half-duplex single-transceiver radios. We show that while power control helps in reducing the number of transmission slots to complete a convergecast under a single frequency channel, scheduling transmissions on different frequency channels is more efficient in mitigating the effects of interference (empirically, 6 channels suffice for most 100-node networks). With these observations, we define a receiver-based channel assignment problem, and prove it to be NP-complete on general graphs. We then introduce a greedy channel assignment algorithm that efficiently eliminates interference, and compare its performance with other existing schemes via simulations. Once the interference is completely eliminated, we show that with half-duplex single-transceiver radios the achievable schedule length is lower-bounded by max(2nk − 1,N), where nk is the maximum number of nodes on any subtree and N is the number of nodes in the network. We modify an existing distributed time slot assignment algorithm to achieve this bound when a suitable balanced routing scheme is employed. Through extensive simulations, we demonstrate that convergecast can be completed within up to 50% less time slots, in 100-node networks, using multiple channels as compared to that with single-channel communication. Finally, we also demonstrate further improvements that are possible when the sink is equipped with multiple transceivers or when there are multiple sinks to collect data.

KW - EWI-13512

KW - METIS-251201

KW - IR-65004

M3 - Report

BT - Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks

PB - USC-Ceng

CY - Los Angeles

ER -

Durmaz O, Ghosh A, Krishnamachari B, Chintalapudi K. Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks. Los Angeles: USC-Ceng, 2008. 9 p.