NDLI: Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks

Please wait, while we are loading the content...

Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks

Content Provider	ACM Digital Library
Author	Kalpakis, Konstantinos
Copyright Year	2010
Abstract	We consider two related data gathering problems for wireless sensor networks (WSNs). The MLDA problem is concerned with maximizing the system lifetime $\textit{T}$ so that we can perform $\textit{T}$ rounds of data gathering with in-network aggregation, given the initial available energy of the sensors. The $M^{2}EDA$ problem is concerned with minimizing the maximum energy consumed by any one sensor when performing $\textit{T}$ rounds of data gathering with in-network aggregation, for a given $\textit{T}.$ We provide an effective algorithm for finding an everywhere sparse integral solution to the $M^{2}EDA$ problem which is within a factor of α = 1+ $4\textit{n}/\textit{T}$ of the optimum, where $\textit{n}$ is the number of nodes. A solution is everywhere sparse if the number of communication links for any subset $\textit{X}$ of nodes is $\textit{O}(\textit{X}),$ in our case at most $4\|\textit{X}\|.$ Since often $\textit{T}$ = $ω(\textit{n}),$ we obtain the first everywhere sparse, asymptotically optimal integral solutions to the $M^{2}EDA$ problem. Everywhere sparse solutions are desirable since then almost all sensors have small number of incident communication links and small overhead for maintaining state. We also show that the MLDA and $M^{2}EDA$ problems are essentially equivalent, in the sense that we can obtain an optimal fractional solution to an instance of the MLDA problem by scaling an optimal fractional solution to a suitable instance of the $M^{2}EDA$ problem. As a result, our algorithm is effective at finding everywhere sparse, asymptotically optimal, integral solutions to the MLDA problem, when the initial available energy of the sensors is sufficient for supporting optimal system lifetime which is $ω(\textit{n}).$
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	15504859
e-ISSN	15504867
DOI	10.1145/1806895.1806904
Volume Number	7
Issue Number	1
Journal	ACM Transactions on Sensor Networks (TOSN)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-08-20
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Energy management In-network aggregation Lifetime maximization Sparsity communication topology Wireless sensor networks
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks.

Cluster based algorithm for energy conservation and lifetime maximization in wireless sensor networks.

A combinatorial algorithm for the maximum lifetime data gathering with aggregation problem in sensor networks (2009).

Mixed communication method for data gathering and aggregation in wireless sensor networks

Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks

An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks

Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks

Data aggregation and routing in wireless sensor networks: Optimal and heuristic algorithms

Delay efficient data gathering in sensor networks.

Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks

Similar Documents

Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks.

Cluster based algorithm for energy conservation and lifetime maximization in wireless sensor networks.

A combinatorial algorithm for the maximum lifetime data gathering with aggregation problem in sensor networks (2009).

Mixed communication method for data gathering and aggregation in wireless sensor networks

Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks

An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks

Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks

Data aggregation and routing in wireless sensor networks: Optimal and heuristic algorithms

Delay efficient data gathering in sensor networks.

Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks