Scheduling algorithms and routing structures for efficient convergecast in wireless sensor networks

Nai Luen Lai, Chun Han Lin, Chung Ta King

Research output: Contribution to journalArticle

Abstract

Purpose – A primary task of wireless sensor networks is to measure environmental conditions. In most applications, a sink node is responsible for collecting data from the sensors through multihop communications. The communication pattern is called convergecast. However, radio congestion around the sink can easily become a bottleneck for the convergecast. The purpose of this paper is to consider both scheduling algorithms and routing structures to improve the throughput of convergecast. Design/methodology/approach – The paper addresses the issue from two perspectives. First by considering the transition scheduling that reduces radio interference to perform convergecast efficiently. Second, by studying the effects of routing structures on convergecast. A routing algorithm, called disjointstrip routing, is proposed as an alternative to existing shortestpath routing. Findings – The paper shows that constructing a shortestlength conflictfree schedule is equivalent to finding a minimal vertex coloring. To solve the scheduling problem, a virtualnode expansion is proposed to handle relay operations and then coloring algorithms are utilized. Regarding the routing structures, a disjointstrip algorithm is proposed to leverage possible parallel transmissions. Proposed algorithms are evaluated through simulations. Originality/value – This paper separates the problem for optimizing datacollection throughput into two stages: constructing a routing structure on a given deployment; and scheduling the activation time of each link. Determining routing topologies and communication schedules for optimal throughput are shown to be hard, so heuristics are applied in both stages. VNE is proposed, which makes traffic information visible to coloring algorithms. The advantage of VNE is verified through simulations. VNE can be applied to any coloring algorithm and any deterministic traffic pattern. It is shown that routing structures set a limit on the performance of scheduling algorithms. There are two possible ways in routing algorithms to improve convergecast throughput: first, by reducing the total number of transmissions during data collection; second, by transferring data in parallel. The shortestpath routing addresses the first point while DS addresses the second one. As expected, when the deployments are even and balanced, minimizing the number of transmissions is more effective than parallelizing them. On the other hand, when the deployments are unbalanced and conflicts are not strict, parallel transmissions can improve the throughput.

Original languageEnglish
Pages (from-to)4-18
Number of pages15
JournalInternational Journal of Pervasive Computing and Communications
Volume6
Issue number1
DOIs
Publication statusPublished - 2010 Apr 6

Fingerprint

Scheduling algorithms
Scheduling Algorithm
Wireless Sensor Networks
Wireless sensor networks
Coloring
Routing
Throughput
Scheduling
Routing algorithms
Communication
Colouring
Radio interference
Routing Algorithm
Data communication systems
Schedule
Traffic
Chemical activation
Topology
Vertex Coloring
Multi-hop

Keywords

  • Communication technologies
  • Optimization techniques
  • Programming and algorithm theory
  • Wireless sensors

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Scheduling algorithms and routing structures for efficient convergecast in wireless sensor networks. / Lai, Nai Luen; Lin, Chun Han; King, Chung Ta.

In: International Journal of Pervasive Computing and Communications, Vol. 6, No. 1, 06.04.2010, p. 4-18.

Research output: Contribution to journalArticle

@article{d59c1c6600fb4672b2b23235de58d1e0,
title = "Scheduling algorithms and routing structures for efficient convergecast in wireless sensor networks",
abstract = "Purpose – A primary task of wireless sensor networks is to measure environmental conditions. In most applications, a sink node is responsible for collecting data from the sensors through multihop communications. The communication pattern is called convergecast. However, radio congestion around the sink can easily become a bottleneck for the convergecast. The purpose of this paper is to consider both scheduling algorithms and routing structures to improve the throughput of convergecast. Design/methodology/approach – The paper addresses the issue from two perspectives. First by considering the transition scheduling that reduces radio interference to perform convergecast efficiently. Second, by studying the effects of routing structures on convergecast. A routing algorithm, called disjointstrip routing, is proposed as an alternative to existing shortestpath routing. Findings – The paper shows that constructing a shortestlength conflictfree schedule is equivalent to finding a minimal vertex coloring. To solve the scheduling problem, a virtualnode expansion is proposed to handle relay operations and then coloring algorithms are utilized. Regarding the routing structures, a disjointstrip algorithm is proposed to leverage possible parallel transmissions. Proposed algorithms are evaluated through simulations. Originality/value – This paper separates the problem for optimizing datacollection throughput into two stages: constructing a routing structure on a given deployment; and scheduling the activation time of each link. Determining routing topologies and communication schedules for optimal throughput are shown to be hard, so heuristics are applied in both stages. VNE is proposed, which makes traffic information visible to coloring algorithms. The advantage of VNE is verified through simulations. VNE can be applied to any coloring algorithm and any deterministic traffic pattern. It is shown that routing structures set a limit on the performance of scheduling algorithms. There are two possible ways in routing algorithms to improve convergecast throughput: first, by reducing the total number of transmissions during data collection; second, by transferring data in parallel. The shortestpath routing addresses the first point while DS addresses the second one. As expected, when the deployments are even and balanced, minimizing the number of transmissions is more effective than parallelizing them. On the other hand, when the deployments are unbalanced and conflicts are not strict, parallel transmissions can improve the throughput.",
keywords = "Communication technologies, Optimization techniques, Programming and algorithm theory, Wireless sensors",
author = "Lai, {Nai Luen} and Lin, {Chun Han} and King, {Chung Ta}",
year = "2010",
month = "4",
day = "6",
doi = "10.1108/17427371011033262",
language = "English",
volume = "6",
pages = "4--18",
journal = "International Journal of Pervasive Computing and Communications",
issn = "1742-7371",
publisher = "Emerald Group Publishing Ltd.",
number = "1",

}

TY - JOUR

T1 - Scheduling algorithms and routing structures for efficient convergecast in wireless sensor networks

AU - Lai, Nai Luen

AU - Lin, Chun Han

AU - King, Chung Ta

PY - 2010/4/6

Y1 - 2010/4/6

N2 - Purpose – A primary task of wireless sensor networks is to measure environmental conditions. In most applications, a sink node is responsible for collecting data from the sensors through multihop communications. The communication pattern is called convergecast. However, radio congestion around the sink can easily become a bottleneck for the convergecast. The purpose of this paper is to consider both scheduling algorithms and routing structures to improve the throughput of convergecast. Design/methodology/approach – The paper addresses the issue from two perspectives. First by considering the transition scheduling that reduces radio interference to perform convergecast efficiently. Second, by studying the effects of routing structures on convergecast. A routing algorithm, called disjointstrip routing, is proposed as an alternative to existing shortestpath routing. Findings – The paper shows that constructing a shortestlength conflictfree schedule is equivalent to finding a minimal vertex coloring. To solve the scheduling problem, a virtualnode expansion is proposed to handle relay operations and then coloring algorithms are utilized. Regarding the routing structures, a disjointstrip algorithm is proposed to leverage possible parallel transmissions. Proposed algorithms are evaluated through simulations. Originality/value – This paper separates the problem for optimizing datacollection throughput into two stages: constructing a routing structure on a given deployment; and scheduling the activation time of each link. Determining routing topologies and communication schedules for optimal throughput are shown to be hard, so heuristics are applied in both stages. VNE is proposed, which makes traffic information visible to coloring algorithms. The advantage of VNE is verified through simulations. VNE can be applied to any coloring algorithm and any deterministic traffic pattern. It is shown that routing structures set a limit on the performance of scheduling algorithms. There are two possible ways in routing algorithms to improve convergecast throughput: first, by reducing the total number of transmissions during data collection; second, by transferring data in parallel. The shortestpath routing addresses the first point while DS addresses the second one. As expected, when the deployments are even and balanced, minimizing the number of transmissions is more effective than parallelizing them. On the other hand, when the deployments are unbalanced and conflicts are not strict, parallel transmissions can improve the throughput.

AB - Purpose – A primary task of wireless sensor networks is to measure environmental conditions. In most applications, a sink node is responsible for collecting data from the sensors through multihop communications. The communication pattern is called convergecast. However, radio congestion around the sink can easily become a bottleneck for the convergecast. The purpose of this paper is to consider both scheduling algorithms and routing structures to improve the throughput of convergecast. Design/methodology/approach – The paper addresses the issue from two perspectives. First by considering the transition scheduling that reduces radio interference to perform convergecast efficiently. Second, by studying the effects of routing structures on convergecast. A routing algorithm, called disjointstrip routing, is proposed as an alternative to existing shortestpath routing. Findings – The paper shows that constructing a shortestlength conflictfree schedule is equivalent to finding a minimal vertex coloring. To solve the scheduling problem, a virtualnode expansion is proposed to handle relay operations and then coloring algorithms are utilized. Regarding the routing structures, a disjointstrip algorithm is proposed to leverage possible parallel transmissions. Proposed algorithms are evaluated through simulations. Originality/value – This paper separates the problem for optimizing datacollection throughput into two stages: constructing a routing structure on a given deployment; and scheduling the activation time of each link. Determining routing topologies and communication schedules for optimal throughput are shown to be hard, so heuristics are applied in both stages. VNE is proposed, which makes traffic information visible to coloring algorithms. The advantage of VNE is verified through simulations. VNE can be applied to any coloring algorithm and any deterministic traffic pattern. It is shown that routing structures set a limit on the performance of scheduling algorithms. There are two possible ways in routing algorithms to improve convergecast throughput: first, by reducing the total number of transmissions during data collection; second, by transferring data in parallel. The shortestpath routing addresses the first point while DS addresses the second one. As expected, when the deployments are even and balanced, minimizing the number of transmissions is more effective than parallelizing them. On the other hand, when the deployments are unbalanced and conflicts are not strict, parallel transmissions can improve the throughput.

KW - Communication technologies

KW - Optimization techniques

KW - Programming and algorithm theory

KW - Wireless sensors

UR - http://www.scopus.com/inward/record.url?scp=84893374321&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893374321&partnerID=8YFLogxK

U2 - 10.1108/17427371011033262

DO - 10.1108/17427371011033262

M3 - Article

AN - SCOPUS:84893374321

VL - 6

SP - 4

EP - 18

JO - International Journal of Pervasive Computing and Communications

JF - International Journal of Pervasive Computing and Communications

SN - 1742-7371

IS - 1

ER -