Energy-efficient collection of sparse data in wireless sensor networks using sparse random matrices

Xiaohan Yu; Seung Jun Baek

doi:10.1145/3085576

Energy-efficient collection of sparse data in wireless sensor networks using sparse random matrices

Xiaohan Yu, Seung Jun Baek

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

Abstract

We consider the energy efficiency of collecting sparse data in wireless sensor networks using compressive sensing (CS). We use a sparse random matrix as the sensing matrix, which we call Sparse Random Sampling (SRS). In SRS, only a randomly selected subset of nodes, called the source nodes, are required to report data to the sink. Given the source nodes, we intend to construct a data gathering tree such that (1) it is rooted at the sink and spans every source node and (2) the minimum residual energy of the tree nodes after the data collection is maximized.We first show that this problem is NP-complete and then develop a polynomial time algorithm to approximately solve the problem.We greedily construct a sequence of data gathering trees over multiple rounds and propose a polynomial-time algorithm to collect linearly combined measurements at each round. We show that the proposed algorithm is provably near-optimal. Simulation and experimental results show that the proposed algorithm excels not only in increasing the minimum residual energy, but also in extending the network lifetime.

Original language	English
Article number	22
Journal	ACM Transactions on Sensor Networks
Volume	13
Issue number	3
DOIs	https://doi.org/10.1145/3085576
Publication status	Published - 2017 Aug

Bibliographical note

Funding Information:
This work is supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (MSIP) of Republic of Korea, No. NRF-2016R1A2B1014934, and by Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No.B0126-17-1046, Research of Network Virtualization Platform and Service for SDN 2.0 Realization). Authors’ addresses: X. Yu, School of Information and Electronic engineering, Zhejiang Gongshang University, Hangzhou, China; email: [email protected]; S. J. Baek, Dept. of Computer Science and Engineering, Korea University, Seoul, Korea; email: [email protected]. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax + 1 (212) 869-0481, or [email protected]. © 2017 ACM 1550-4859/2017/08-ART22 $15.00 https://doi.org/10.1145/3085576

Keywords

Compressive sensing (CS)
Data collection
Energy efficiency
Sparse sensing matrices
Wireless sensor networks (wsns)

ASJC Scopus subject areas

Computer Networks and Communications

Access to Document

10.1145/3085576

Cite this

@article{5ee7602fa97349048715f9bff61e1bd1,

title = "Energy-efficient collection of sparse data in wireless sensor networks using sparse random matrices",

abstract = "We consider the energy efficiency of collecting sparse data in wireless sensor networks using compressive sensing (CS). We use a sparse random matrix as the sensing matrix, which we call Sparse Random Sampling (SRS). In SRS, only a randomly selected subset of nodes, called the source nodes, are required to report data to the sink. Given the source nodes, we intend to construct a data gathering tree such that (1) it is rooted at the sink and spans every source node and (2) the minimum residual energy of the tree nodes after the data collection is maximized.We first show that this problem is NP-complete and then develop a polynomial time algorithm to approximately solve the problem.We greedily construct a sequence of data gathering trees over multiple rounds and propose a polynomial-time algorithm to collect linearly combined measurements at each round. We show that the proposed algorithm is provably near-optimal. Simulation and experimental results show that the proposed algorithm excels not only in increasing the minimum residual energy, but also in extending the network lifetime.",

keywords = "Compressive sensing (CS), Data collection, Energy efficiency, Sparse sensing matrices, Wireless sensor networks (wsns)",

author = "Xiaohan Yu and Baek, {Seung Jun}",

note = "Funding Information: This work is supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (MSIP) of Republic of Korea, No. NRF-2016R1A2B1014934, and by Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No.B0126-17-1046, Research of Network Virtualization Platform and Service for SDN 2.0 Realization). Authors{\textquoteright} addresses: X. Yu, School of Information and Electronic engineering, Zhejiang Gongshang University, Hangzhou, China; email: [email protected]; S. J. Baek, Dept. of Computer Science and Engineering, Korea University, Seoul, Korea; email: [email protected]. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax + 1 (212) 869-0481, or [email protected]. {\textcopyright} 2017 ACM 1550-4859/2017/08-ART22 $15.00 https://doi.org/10.1145/3085576",

year = "2017",

month = aug,

doi = "10.1145/3085576",

language = "English",

volume = "13",

journal = "ACM Transactions on Sensor Networks",

issn = "1550-4859",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Energy-efficient collection of sparse data in wireless sensor networks using sparse random matrices

AU - Yu, Xiaohan

AU - Baek, Seung Jun

N1 - Funding Information: This work is supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (MSIP) of Republic of Korea, No. NRF-2016R1A2B1014934, and by Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No.B0126-17-1046, Research of Network Virtualization Platform and Service for SDN 2.0 Realization). Authors’ addresses: X. Yu, School of Information and Electronic engineering, Zhejiang Gongshang University, Hangzhou, China; email: [email protected]; S. J. Baek, Dept. of Computer Science and Engineering, Korea University, Seoul, Korea; email: [email protected]. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax + 1 (212) 869-0481, or [email protected]. © 2017 ACM 1550-4859/2017/08-ART22 $15.00 https://doi.org/10.1145/3085576

PY - 2017/8

Y1 - 2017/8

N2 - We consider the energy efficiency of collecting sparse data in wireless sensor networks using compressive sensing (CS). We use a sparse random matrix as the sensing matrix, which we call Sparse Random Sampling (SRS). In SRS, only a randomly selected subset of nodes, called the source nodes, are required to report data to the sink. Given the source nodes, we intend to construct a data gathering tree such that (1) it is rooted at the sink and spans every source node and (2) the minimum residual energy of the tree nodes after the data collection is maximized.We first show that this problem is NP-complete and then develop a polynomial time algorithm to approximately solve the problem.We greedily construct a sequence of data gathering trees over multiple rounds and propose a polynomial-time algorithm to collect linearly combined measurements at each round. We show that the proposed algorithm is provably near-optimal. Simulation and experimental results show that the proposed algorithm excels not only in increasing the minimum residual energy, but also in extending the network lifetime.

AB - We consider the energy efficiency of collecting sparse data in wireless sensor networks using compressive sensing (CS). We use a sparse random matrix as the sensing matrix, which we call Sparse Random Sampling (SRS). In SRS, only a randomly selected subset of nodes, called the source nodes, are required to report data to the sink. Given the source nodes, we intend to construct a data gathering tree such that (1) it is rooted at the sink and spans every source node and (2) the minimum residual energy of the tree nodes after the data collection is maximized.We first show that this problem is NP-complete and then develop a polynomial time algorithm to approximately solve the problem.We greedily construct a sequence of data gathering trees over multiple rounds and propose a polynomial-time algorithm to collect linearly combined measurements at each round. We show that the proposed algorithm is provably near-optimal. Simulation and experimental results show that the proposed algorithm excels not only in increasing the minimum residual energy, but also in extending the network lifetime.

KW - Compressive sensing (CS)

KW - Data collection

KW - Energy efficiency

KW - Sparse sensing matrices

KW - Wireless sensor networks (wsns)

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

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

U2 - 10.1145/3085576

DO - 10.1145/3085576

M3 - Article

AN - SCOPUS:85028576130

SN - 1550-4859

VL - 13

JO - ACM Transactions on Sensor Networks

JF - ACM Transactions on Sensor Networks

IS - 3

M1 - 22

ER -

Energy-efficient collection of sparse data in wireless sensor networks using sparse random matrices

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this