Data transmission and base-station placement for optimizing network lifetime

Esther M. Arkin; Valentin Polishchuk; Alon Efrat; Srinivasan Ramasubramanian; Javad Taheri; Joseph S.B. Mitchell; Swaminathan Sankararaman

doi:10.1145/1860684.1860692

Data transmission and base-station placement for optimizing network lifetime

Esther M. Arkin, Valentin Polishchuk, Alon Efrat, Srinivasan Ramasubramanian, Javad Taheri, Joseph S.B. Mitchell, Swaminathan Sankararaman

Computer Science

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

2 Scopus citations

Abstract

We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.

Original language	English (US)
Title of host publication	Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10
Pages	23-32
Number of pages	10
DOIs	https://doi.org/10.1145/1860684.1860692
State	Published - 2010
Event	6th ACM SIGACT-SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010 - Cambridge, MA, United States Duration: Sep 16 2010 → Sep 16 2010

Publication series

Name	Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10

Other

Other	6th ACM SIGACT-SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010
Country/Territory	United States
City	Cambridge, MA
Period	9/16/10 → 9/16/10

Keywords

algorithms
base-station location
matching
optimization
routing
sensor networks

ASJC Scopus subject areas

Computer Networks and Communications
Computer Science Applications

Access to Document

10.1145/1860684.1860692

Cite this

Arkin, E. M., Polishchuk, V., Efrat, A., Ramasubramanian, S., Taheri, J., Mitchell, J. S. B., & Sankararaman, S. (2010). Data transmission and base-station placement for optimizing network lifetime. In Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10 (pp. 23-32). (Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10). https://doi.org/10.1145/1860684.1860692

Data transmission and base-station placement for optimizing network lifetime. / Arkin, Esther M.; Polishchuk, Valentin; Efrat, Alon et al.
Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10. 2010. p. 23-32 (Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10).

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

Arkin, EM, Polishchuk, V, Efrat, A, Ramasubramanian, S, Taheri, J, Mitchell, JSB & Sankararaman, S 2010, Data transmission and base-station placement for optimizing network lifetime. in Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10. Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10, pp. 23-32, 6th ACM SIGACT-SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010, Cambridge, MA, United States, 9/16/10. https://doi.org/10.1145/1860684.1860692

Arkin EM, Polishchuk V, Efrat A, Ramasubramanian S, Taheri J, Mitchell JSB et al. Data transmission and base-station placement for optimizing network lifetime. In Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10. 2010. p. 23-32. (Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10). doi: 10.1145/1860684.1860692

@inproceedings{e34a0868174c48b3aa303c544c427efa,

title = "Data transmission and base-station placement for optimizing network lifetime",

abstract = "We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.",

keywords = "algorithms, base-station location, matching, optimization, routing, sensor networks",

author = "Arkin, {Esther M.} and Valentin Polishchuk and Alon Efrat and Srinivasan Ramasubramanian and Javad Taheri and Mitchell, {Joseph S.B.} and Swaminathan Sankararaman",

year = "2010",

doi = "10.1145/1860684.1860692",

language = "English (US)",

isbn = "9781450304139",

series = "Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10",

pages = "23--32",

booktitle = "Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10",

note = "6th ACM SIGACT-SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010 ; Conference date: 16-09-2010 Through 16-09-2010",

}

TY - GEN

T1 - Data transmission and base-station placement for optimizing network lifetime

AU - Arkin, Esther M.

AU - Polishchuk, Valentin

AU - Efrat, Alon

AU - Ramasubramanian, Srinivasan

AU - Taheri, Javad

AU - Mitchell, Joseph S.B.

AU - Sankararaman, Swaminathan

PY - 2010

Y1 - 2010

N2 - We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.

AB - We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.

KW - algorithms

KW - base-station location

KW - matching

KW - optimization

KW - routing

KW - sensor networks

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

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

U2 - 10.1145/1860684.1860692

DO - 10.1145/1860684.1860692

M3 - Conference contribution

AN - SCOPUS:78549283546

SN - 9781450304139

T3 - Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10

SP - 23

EP - 32

BT - Proceedings of the 6th International Workshop on Foundations of Mobile Computing, DIALM-POMC '10

T2 - 6th ACM SIGACT-SIGMOBILE International Workshop on Foundations of Mobile Computing, DIALM-POMC 2010

Y2 - 16 September 2010 through 16 September 2010

ER -

Data transmission and base-station placement for optimizing network lifetime

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this