NDLI: Constructing battery-aware virtual backbones in sensor networks

Content Provider	IEEE Xplore Digital Library
Author	Chi Ma Yuanyuan Yang Zhenghao Zhang
Copyright Year	2005
Description	Author affiliation: Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA (Chi Ma)
Abstract	A critical issue in wireless sensor networks is to construct energy efficient virtual backbones for routing, broadcasting and data propagating. The minimum connected dominating set (MCDS) has been proposed as a backbone to reduce power dissipation and prolong network lifetime. However, we find that an MCDS cannot guarantee maximum network lifetime as it does not consider the battery discharging behavior. Recent study in battery technology reveals that the discharging of a battery is not linear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. In order to optimize network performance and construct an energy efficient virtual backbone in sensor networks, battery-awareness should be considered. In this paper we first study the mathematical battery discharging model and provide a simplified battery model suitable for implementation in sensor networks. We then introduce the concept of battery-aware connected dominating set (BACDS) and show that in general the BACDS can achieve longer lifetime than the MCDS. Then we show that finding a minimum BACDS (MBACDS) is NP-hard and give a distributed approximation algorithm to construct the BACDS. The resulting BACDS constructed by our algorithm is at most (8+/spl Delta/)opt size where /spl Delta/ is the maximum node degree and opt is the size of an optimal BACDS. The time and message complexities of the algorithm are O(n) and O(n(/spl radic/n+logn+/spl Delta/)), respectively, where n is the number of nodes in the network. The simulation results show that the BACDS constructed by our algorithm can save a significant amount of energy and achieve up to 30% longer network lifetime than the MCDS. To the best of our knowledge, this is the first work considering battery-awareness in the construction of connected dominating sets.
Sponsorship	Int. Assoc. for Comput. and Commun. (IACC) Simula Res. Lab. The Res. Council of Norway The Univ. of Oslo
Starting Page	203
Ending Page	210
File Size	379318
Page Count	8
File Format	PDF
ISBN	0769523803
ISSN	01903918
DOI	10.1109/ICPP.2005.27
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-06-14
Publisher Place	Norway
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Spine Batteries Energy efficiency Mathematical model Wireless sensor networks Routing Broadcasting Power dissipation Approximation algorithms Optimized production technology battery-aware connected dominating sets. sensor networks connected dominating sets energy efficiency battery models battery-awareness
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