Lower bounds on data collection time in sensor networks

Xianwei Sun; Scott C.H. Huang; Minming Li

doi:10.1007/978-3-642-31869-6_10

Lower bounds on data collection time in sensor networks

Xianwei Sun^*
, Scott C.H. Huang
, Minming Li

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

We study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks regarded as lines, multi-lines and trees is defined and corresponding optimal schedules are provided. A lower bound of data collection time on general graph networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops. We also prove the schedule is nearly optimal if each node can transmit k (k > 2) hops (with constant error).

Original language	English
Title of host publication	Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings
Pages	120-131
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-31869-6_10
State	Published - 2012
Externally published	Yes
Event	7th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2012 - Yellow Mountains, China Duration: 8 Aug 2012 → 10 Aug 2012

Publication series

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

Conference

Conference	7th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2012
Country/Territory	China
City	Yellow Mountains
Period	8/08/12 → 10/08/12

Access to Document

10.1007/978-3-642-31869-6_10

Cite this

Sun, X., Huang, S. C. H., & Li, M. (2012). Lower bounds on data collection time in sensor networks. In Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings (pp. 120-131). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7405 LNCS). https://doi.org/10.1007/978-3-642-31869-6_10

@inproceedings{3ba29c76acd04fdb970d191a00fb316b,

title = "Lower bounds on data collection time in sensor networks",

abstract = "We study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks regarded as lines, multi-lines and trees is defined and corresponding optimal schedules are provided. A lower bound of data collection time on general graph networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops. We also prove the schedule is nearly optimal if each node can transmit k (k > 2) hops (with constant error).",

author = "Xianwei Sun and Huang, \{Scott C.H.\} and Minming Li",

year = "2012",

doi = "10.1007/978-3-642-31869-6\_10",

language = "英语",

isbn = "9783642318689",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "120--131",

booktitle = "Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings",

note = "7th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2012 ; Conference date: 08-08-2012 Through 10-08-2012",

}

Sun, X, Huang, SCH & Li, M 2012, Lower bounds on data collection time in sensor networks. in Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7405 LNCS, pp. 120-131, 7th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2012, Yellow Mountains, China, 8/08/12. https://doi.org/10.1007/978-3-642-31869-6_10

Lower bounds on data collection time in sensor networks. / Sun, Xianwei; Huang, Scott C.H.; Li, Minming.
Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings. 2012. p. 120-131 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7405 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Lower bounds on data collection time in sensor networks

AU - Sun, Xianwei

AU - Huang, Scott C.H.

AU - Li, Minming

PY - 2012

Y1 - 2012

N2 - We study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks regarded as lines, multi-lines and trees is defined and corresponding optimal schedules are provided. A lower bound of data collection time on general graph networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops. We also prove the schedule is nearly optimal if each node can transmit k (k > 2) hops (with constant error).

AB - We study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks regarded as lines, multi-lines and trees is defined and corresponding optimal schedules are provided. A lower bound of data collection time on general graph networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops. We also prove the schedule is nearly optimal if each node can transmit k (k > 2) hops (with constant error).

UR - https://www.scopus.com/pages/publications/84865570074

U2 - 10.1007/978-3-642-31869-6_10

DO - 10.1007/978-3-642-31869-6_10

M3 - 会议稿件

AN - SCOPUS:84865570074

SN - 9783642318689

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

SP - 120

EP - 131

BT - Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings

T2 - 7th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2012

Y2 - 8 August 2012 through 10 August 2012

ER -

Sun X, Huang SCH, Li M. Lower bounds on data collection time in sensor networks. In Wireless Algorithms, Systems, and Applications - 7th International Conference, WASA 2012, Proceedings. 2012. p. 120-131. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31869-6_10

Lower bounds on data collection time in sensor networks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this