Multi-Channel Scheduling for Fast Convergecast in Wireless Sensor Networks

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

    Research output: Book/ReportReportProfessional

    113 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.