Algorithms for Fast Aggregated Convergecast in Sensor Networks

A. Ghosh, O. Durmaz, V.S. Anil Kumar, B. Krishnamachari

Research output: Book/ReportReportProfessional

78 Downloads (Pure)

Abstract

Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm, referred to as convergecast, we focus on applications wherein data packets are aggregated at each hop en-route to the sink along a tree-based routing topology, and address the problem of minimizing the convergecast schedule length by utilizing multiple frequency channels. The primary hindrance in minimizing the schedule length is the presence of interfering links. We prove that it is NP-complete to determine whether all the interfering links in an arbitrary network can be removed using at most a constant number of frequencies. We give a sufficient condition on the number of frequencies for which all the interfering links can be removed, and propose a polynomial time algorithm that minimizes the schedule length in this case. We also prove that minimizing the schedule length for a given number of frequencies on an arbitrary network is NP-complete, and describe a greedy scheme that gives a constant factor approximation on unit disk graphs. When the routing tree is not given as an input to the problem, we prove that a constant factor approximation is still achievable for degree-bounded trees. Finally, we evaluate our algorithms through simulations and compare their performance under different network parameters.
Original languageUndefined
Place of PublicationLos Angeles
PublisherUSC-Ceng
Number of pages9
Publication statusPublished - Sep 2008

Publication series

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

Keywords

  • IR-65017
  • METIS-251209
  • EWI-13534

Cite this

Ghosh, A., Durmaz, O., Anil Kumar, V. S., & Krishnamachari, B. (2008). Algorithms for Fast Aggregated Convergecast in Sensor Networks. Los Angeles: USC-Ceng.
Ghosh, A. ; Durmaz, O. ; Anil Kumar, V.S. ; Krishnamachari, B. / Algorithms for Fast Aggregated Convergecast in Sensor Networks. Los Angeles : USC-Ceng, 2008. 9 p.
@book{ccbde6df5af442088c8149f5141c91f6,
title = "Algorithms for Fast Aggregated Convergecast in Sensor Networks",
abstract = "Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm, referred to as convergecast, we focus on applications wherein data packets are aggregated at each hop en-route to the sink along a tree-based routing topology, and address the problem of minimizing the convergecast schedule length by utilizing multiple frequency channels. The primary hindrance in minimizing the schedule length is the presence of interfering links. We prove that it is NP-complete to determine whether all the interfering links in an arbitrary network can be removed using at most a constant number of frequencies. We give a sufficient condition on the number of frequencies for which all the interfering links can be removed, and propose a polynomial time algorithm that minimizes the schedule length in this case. We also prove that minimizing the schedule length for a given number of frequencies on an arbitrary network is NP-complete, and describe a greedy scheme that gives a constant factor approximation on unit disk graphs. When the routing tree is not given as an input to the problem, we prove that a constant factor approximation is still achievable for degree-bounded trees. Finally, we evaluate our algorithms through simulations and compare their performance under different network parameters.",
keywords = "IR-65017, METIS-251209, EWI-13534",
author = "A. Ghosh and O. Durmaz and {Anil Kumar}, V.S. and B. Krishnamachari",
year = "2008",
month = "9",
language = "Undefined",
publisher = "USC-Ceng",
number = "Supplement/CENG-2008-8",

}

Ghosh, A, Durmaz, O, Anil Kumar, VS & Krishnamachari, B 2008, Algorithms for Fast Aggregated Convergecast in Sensor Networks. USC-Ceng, Los Angeles.

Algorithms for Fast Aggregated Convergecast in Sensor Networks. / Ghosh, A.; Durmaz, O.; Anil Kumar, V.S.; Krishnamachari, B.

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

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Algorithms for Fast Aggregated Convergecast in Sensor Networks

AU - Ghosh, A.

AU - Durmaz, O.

AU - Anil Kumar, V.S.

AU - Krishnamachari, B.

PY - 2008/9

Y1 - 2008/9

N2 - Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm, referred to as convergecast, we focus on applications wherein data packets are aggregated at each hop en-route to the sink along a tree-based routing topology, and address the problem of minimizing the convergecast schedule length by utilizing multiple frequency channels. The primary hindrance in minimizing the schedule length is the presence of interfering links. We prove that it is NP-complete to determine whether all the interfering links in an arbitrary network can be removed using at most a constant number of frequencies. We give a sufficient condition on the number of frequencies for which all the interfering links can be removed, and propose a polynomial time algorithm that minimizes the schedule length in this case. We also prove that minimizing the schedule length for a given number of frequencies on an arbitrary network is NP-complete, and describe a greedy scheme that gives a constant factor approximation on unit disk graphs. When the routing tree is not given as an input to the problem, we prove that a constant factor approximation is still achievable for degree-bounded trees. Finally, we evaluate our algorithms through simulations and compare their performance under different network parameters.

AB - Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm, referred to as convergecast, we focus on applications wherein data packets are aggregated at each hop en-route to the sink along a tree-based routing topology, and address the problem of minimizing the convergecast schedule length by utilizing multiple frequency channels. The primary hindrance in minimizing the schedule length is the presence of interfering links. We prove that it is NP-complete to determine whether all the interfering links in an arbitrary network can be removed using at most a constant number of frequencies. We give a sufficient condition on the number of frequencies for which all the interfering links can be removed, and propose a polynomial time algorithm that minimizes the schedule length in this case. We also prove that minimizing the schedule length for a given number of frequencies on an arbitrary network is NP-complete, and describe a greedy scheme that gives a constant factor approximation on unit disk graphs. When the routing tree is not given as an input to the problem, we prove that a constant factor approximation is still achievable for degree-bounded trees. Finally, we evaluate our algorithms through simulations and compare their performance under different network parameters.

KW - IR-65017

KW - METIS-251209

KW - EWI-13534

M3 - Report

BT - Algorithms for Fast Aggregated Convergecast in Sensor Networks

PB - USC-Ceng

CY - Los Angeles

ER -

Ghosh A, Durmaz O, Anil Kumar VS, Krishnamachari B. Algorithms for Fast Aggregated Convergecast in Sensor Networks. Los Angeles: USC-Ceng, 2008. 9 p.