On maximizing the throughput of convergecast in wireless sensor networks

Nai Luen Lai, Chung Ta King, Chun-Han Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)

Abstract

A primary task of wireless sensor networks is collecting environmental information. In most cases, a sink node is responsible for collecting data from all sensor nodes. The radio congestion around the sink becomes the main bottleneck to maximizing the throughput of the convergecast. A general strategy to alleviating the problem is to schedule the communications among sensors to avoid interference. In this paper, we consider both routing structures and communication schedules for optimizing the scheduling length. We show that the shortest-length conflict-free scheduling is equivalent to finding a minimal vertex coloring. To solve the schedule problem, a virtual-node expansion is proposed to handle the relay operations in convergecast, and then coloring algorithms are used to obtain the communication schedule. However, scheduling only solves part of the problem. Routing structures will also affect the scheduling quality. The disjoint-strips routing is thus proposed to leverage possible parallel transmissions in convergecast. The proposed algorithms are evaluated through simulations.

Original languageEnglish
Title of host publicationAdvances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings
Pages396-408
Number of pages13
DOIs
Publication statusPublished - 2008 Jun 9
Event3rd International Conference on Grid and Pervasive Computing, GPC 2008 - Kunming, China
Duration: 2008 May 252008 May 28

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5036 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Grid and Pervasive Computing, GPC 2008
CountryChina
CityKunming
Period08/5/2508/5/28

Fingerprint

Wireless Sensor Networks
Wireless sensor networks
Schedule
Throughput
Scheduling
Routing
Coloring
Communication
Vertex of a graph
Sensor
Vertex Coloring
Sensor nodes
Congestion
Leverage
Relay
Colouring
Strip
Disjoint
Interference
Sensors

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Lai, N. L., King, C. T., & Lin, C-H. (2008). On maximizing the throughput of convergecast in wireless sensor networks. In Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings (pp. 396-408). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5036 LNCS). https://doi.org/10.1007/978-3-540-68083-3_39

On maximizing the throughput of convergecast in wireless sensor networks. / Lai, Nai Luen; King, Chung Ta; Lin, Chun-Han.

Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings. 2008. p. 396-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5036 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lai, NL, King, CT & Lin, C-H 2008, On maximizing the throughput of convergecast in wireless sensor networks. in Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5036 LNCS, pp. 396-408, 3rd International Conference on Grid and Pervasive Computing, GPC 2008, Kunming, China, 08/5/25. https://doi.org/10.1007/978-3-540-68083-3_39
Lai NL, King CT, Lin C-H. On maximizing the throughput of convergecast in wireless sensor networks. In Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings. 2008. p. 396-408. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-68083-3_39
Lai, Nai Luen ; King, Chung Ta ; Lin, Chun-Han. / On maximizing the throughput of convergecast in wireless sensor networks. Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings. 2008. pp. 396-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{e04a3f03bacf4a52b98d4ab71d1f876d,
title = "On maximizing the throughput of convergecast in wireless sensor networks",
abstract = "A primary task of wireless sensor networks is collecting environmental information. In most cases, a sink node is responsible for collecting data from all sensor nodes. The radio congestion around the sink becomes the main bottleneck to maximizing the throughput of the convergecast. A general strategy to alleviating the problem is to schedule the communications among sensors to avoid interference. In this paper, we consider both routing structures and communication schedules for optimizing the scheduling length. We show that the shortest-length conflict-free scheduling is equivalent to finding a minimal vertex coloring. To solve the schedule problem, a virtual-node expansion is proposed to handle the relay operations in convergecast, and then coloring algorithms are used to obtain the communication schedule. However, scheduling only solves part of the problem. Routing structures will also affect the scheduling quality. The disjoint-strips routing is thus proposed to leverage possible parallel transmissions in convergecast. The proposed algorithms are evaluated through simulations.",
author = "Lai, {Nai Luen} and King, {Chung Ta} and Chun-Han Lin",
year = "2008",
month = "6",
day = "9",
doi = "10.1007/978-3-540-68083-3_39",
language = "English",
isbn = "3540680810",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "396--408",
booktitle = "Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings",

}

TY - GEN

T1 - On maximizing the throughput of convergecast in wireless sensor networks

AU - Lai, Nai Luen

AU - King, Chung Ta

AU - Lin, Chun-Han

PY - 2008/6/9

Y1 - 2008/6/9

N2 - A primary task of wireless sensor networks is collecting environmental information. In most cases, a sink node is responsible for collecting data from all sensor nodes. The radio congestion around the sink becomes the main bottleneck to maximizing the throughput of the convergecast. A general strategy to alleviating the problem is to schedule the communications among sensors to avoid interference. In this paper, we consider both routing structures and communication schedules for optimizing the scheduling length. We show that the shortest-length conflict-free scheduling is equivalent to finding a minimal vertex coloring. To solve the schedule problem, a virtual-node expansion is proposed to handle the relay operations in convergecast, and then coloring algorithms are used to obtain the communication schedule. However, scheduling only solves part of the problem. Routing structures will also affect the scheduling quality. The disjoint-strips routing is thus proposed to leverage possible parallel transmissions in convergecast. The proposed algorithms are evaluated through simulations.

AB - A primary task of wireless sensor networks is collecting environmental information. In most cases, a sink node is responsible for collecting data from all sensor nodes. The radio congestion around the sink becomes the main bottleneck to maximizing the throughput of the convergecast. A general strategy to alleviating the problem is to schedule the communications among sensors to avoid interference. In this paper, we consider both routing structures and communication schedules for optimizing the scheduling length. We show that the shortest-length conflict-free scheduling is equivalent to finding a minimal vertex coloring. To solve the schedule problem, a virtual-node expansion is proposed to handle the relay operations in convergecast, and then coloring algorithms are used to obtain the communication schedule. However, scheduling only solves part of the problem. Routing structures will also affect the scheduling quality. The disjoint-strips routing is thus proposed to leverage possible parallel transmissions in convergecast. The proposed algorithms are evaluated through simulations.

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

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

U2 - 10.1007/978-3-540-68083-3_39

DO - 10.1007/978-3-540-68083-3_39

M3 - Conference contribution

AN - SCOPUS:44649176605

SN - 3540680810

SN - 9783540680819

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 396

EP - 408

BT - Advances in Grid and Pervasive Computing - Third International Conference, GPC 2008, Proceedings

ER -