NDLI: Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

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

ACM Transactions on Sensor Networks (TOSN) : Volume 13

ACM Transactions on Sensor Networks (TOSN) : Volume 12

Issue 4, November 2016

Issue 3, August 2016

Issue 2, May 2016

Issue 1, March 2016

TAS-MAC: A Traffic-Adaptive Synchronous MAC Protocol for Wireless Sensor Networks

Optimizing the Lifetime of Sensor Networks with Uncontrollable Mobile Sinks and QoS Constraints

Efficient Multichannel Communications in Wireless Sensor Networks

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

Decentralized Network-Level Synchronization in Mobile Ad Hoc Networks

ATPC: Adaptive Transmission Power Control for Wireless Sensor Networks

Monitoring Bats in the Wild: On Using Erasure Codes for Energy-Efficient Wireless Sensor Networks

ACM Transactions on Sensor Networks (TOSN) : Volume 11

ACM Transactions on Sensor Networks (TOSN) : Volume 10

ACM Transactions on Sensor Networks (TOSN) : Volume 9

ACM Transactions on Sensor Networks (TOSN) : Volume 8

ACM Transactions on Sensor Networks (TOSN) : Volume 7

ACM Transactions on Sensor Networks (TOSN) : Volume 6

ACM Transactions on Sensor Networks (TOSN) : Volume 5

ACM Transactions on Sensor Networks (TOSN) : Volume 4

ACM Transactions on Sensor Networks (TOSN) : Volume 3

ACM Transactions on Sensor Networks (TOSN) : Volume 2

ACM Transactions on Sensor Networks (TOSN) : Volume 1

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

Content Provider	ACM Digital Library
Author	Busch, Costas Sharma, Gokarna
Copyright Year	2016
Abstract	We consider the group-communication maintenance problem between a set of $\textit{k}$ mobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided with the minimum total cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents that can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at most $\textit{O}(log$ $\textit{k})$ times the length of the optimal Steiner tree in the constant-doubling graph model. The total communication cost (the number of messages) to maintain the Steiner tree is only $\textit{O}(min{log$ $\textit{n},$ log $\textit{D}})$ times the optimal communication cost, where $\textit{n}$ and $\textit{D},$ respectively, are the number of nodes and the diameter of the constant-doubling network. We also develop improved algorithms for the mobile $\textit{k}-center,$ sparse-aggregation, and distributed-matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these important network problems with low maintenance costs in a distributed setting.
Starting Page	1
Ending Page	29
Page Count	29
File Format	PDF
ISSN	15504859
e-ISSN	15504867
DOI	10.1145/2854155
Volume Number	12
Issue Number	1
Journal	ACM Transactions on Sensor Networks (TOSN)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-03-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sensor network Steiner tree Aggregation Hierarchical structure K-center Matching Mobile agents
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

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network.

Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network (2010)

Maintaining Approximate Minimum Steiner Tree and k-center for Mobile Agents in a Sensor Network

Steiner tree based optimal resource caching scheme in fog computing

A Mobile Agent Routing Protocol for Data Aggregation in Wireless Sensor Networks

Secure Data Aggregation in Wireless Sensor Networks

Delay-Constrained Optimal Data Aggregation in Hierarchical Wireless Sensor Networks

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

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

Similar Documents

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks

Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network.

Maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network (2010)

Maintaining Approximate Minimum Steiner Tree and k-center for Mobile Agents in a Sensor Network

Steiner tree based optimal resource caching scheme in fog computing

A Mobile Agent Routing Protocol for Data Aggregation in Wireless Sensor Networks

Secure Data Aggregation in Wireless Sensor Networks

Delay-Constrained Optimal Data Aggregation in Hierarchical Wireless Sensor Networks

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

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks