NDLI: Minimum-time aggregation scheduling in multi-sink sensor networks

Content Provider	IEEE Xplore Digital Library
Author	Bo Yu Jianzhong Li
Copyright Year	2011
Description	Author affiliation: School of Computer Science and Technology, Harbin Institute of Technology, China (Bo Yu; Jianzhong Li)
Abstract	Data aggregation is an essential operation in wireless sensor networks and aggregation time is critical in many sensor network applications. This paper focuses on the minimum-time aggregation scheduling problem in multi-sink sensor networks (MS-MTAS problem). To the best of our knowledge, this is the first work on the MS-MTAS problem, which is NP-hard. In this paper, we first present a lower bound for MS-MTAS. Then, we design two approximation algorithms for MS-MTAS based on the maximal independent sets. The upper bounds of the aggregation time are, respectively, (min{26k−2, $2Δ\})(max^{k}\}−l)+2Δ$ and 23 $max^{k}$ {R}+2Δ−23, where k is the number of sinks, A is the maximum vertex degree of the network graph and R is the radius of the induced subgraph G[V(T)], with respect to sink S. Here T refers to the tree generated by the corresponding algorithm and V(T) is the vertex set of T. We prove that the second algorithm is a nearly constant approximation. This demonstrates that nearly constant approximation can be achieved for MS-MTAS, which is the same as MTAS. Both algorithms are implemented by simulation and the simulation results verify the effectiveness of the proposed algorithms.
Starting Page	422
Ending Page	430
File Size	477737
Page Count	9
File Format	PDF
ISBN	9781457700941
ISSN	21555494
e-ISBN	9781457700934
DOI	10.1109/SAHCN.2011.5984926
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-06-27
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Schedules Scheduling Vegetation Approximation algorithms Connectors Receivers Scheduling algorithm
Content Type	Text
Resource Type	Article

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

Efficient scheduling for minimum latency aggregation in wireless sensor networks

Latency aware Broadcast Scheduling in Duty Cycled wireless sensor networks

Efficient multi-path data aggregation scheduling in wireless sensor networks

Weighted fairness guaranteed data aggregation scheduling algorithm in wireless sensor networks

A Delay-Aware Scheduling for Data Aggregation in Duty-Cycled Wireless Sensor Networks

Making Aggregation Scheduling Usable in Wireless Sensor Networks: An Opportunistic Approach

Minimum latency scheduling for Multi-Regional Query in Wireless Sensor Networks

Performance analysis of data aggregation algorithms in wireless sensor networks

Conflict-Free Many-to-One Data Aggregation Scheduling in Multi-Channel Multi-Hop Wireless Sensor Networks

Minimum-time aggregation scheduling in multi-sink sensor networks

Similar Documents

Efficient scheduling for minimum latency aggregation in wireless sensor networks

Latency aware Broadcast Scheduling in Duty Cycled wireless sensor networks

Efficient multi-path data aggregation scheduling in wireless sensor networks

Weighted fairness guaranteed data aggregation scheduling algorithm in wireless sensor networks

A Delay-Aware Scheduling for Data Aggregation in Duty-Cycled Wireless Sensor Networks

Making Aggregation Scheduling Usable in Wireless Sensor Networks: An Opportunistic Approach

Minimum latency scheduling for Multi-Regional Query in Wireless Sensor Networks

Performance analysis of data aggregation algorithms in wireless sensor networks

Conflict-Free Many-to-One Data Aggregation Scheduling in Multi-Channel Multi-Hop Wireless Sensor Networks

Minimum-time aggregation scheduling in multi-sink sensor networks