NDLI: Duty-cycle-aware minimum-energy multicasting in wireless sensor networks

Content Provider	ACM Digital Library
Author	Luo, Jun Liu, Yang Han, Kai
Copyright Year	2013
Abstract	In duty-cycled wireless sensor networks, the nodes switch between active and dormant states, and each node may determine its active/dormant schedule independently. This complicates the Minimum-Energy Multicasting (MEM) problem, which was primarily studied in always-active wireless ad hoc networks. In this paper, we study the duty-cycle-aware MEM problem in wireless sensor networks both for one-to-many multicasting and for all-to-all multicasting. In the case of one-to-many multicasting, we present a formalization of the Minimum-Energy Multicast Tree Construction and Scheduling (MEMTCS) problem. We prove that the MEMTCS problem is NP-hard, and it is unlikely to have an approximation algorithm with a performance ratio of (1 - $\textit{o}(1))$ In Δ, where Δ is the maximum node degree in a network. We propose a polynomial-time approximation algorithm for the MEMTCS problem with a performance ratio of $\textit{O}(\textit{H}(Δ+1)),$ where $\textit{H}(ċ)$ is the harmonic number. In the case of all-to-all multicasting, we prove that the Minimum-Energy Multicast Backbone Construction and Scheduling (MEMBCS) problem is also NP-hard and present an approximation algorithm for it, which has the same approximation ratio as that of the proposed algorithm for the MEMTCS problem. We also provide a distributed implementation of our algorithms, as well as a simple but efficient collision-free scheduling scheme to avoid packet loss. Finally, we perform extensive simulations, and the results demonstrate that our algorithms significantly outperform other known algorithms in terms of the total transmission energy cost, without sacrificing much of the delay performance.
Starting Page	910
Ending Page	923
Page Count	14
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2012.2212452
Volume Number	21
Issue Number	3
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithm Duty-cyle-aware Minimum-energy Multicasting Wireless sensor networks (WSNs)
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

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

Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks

Approximation algorithms for minimum energy transmission scheduling in rate and duty-cycle constrained wireless networks

Achieving Energy Efficiency and Reliability for Data Dissemination in Duty-Cycled WSNs

Approximation Algorithms for Minimum Energy Transmission Scheduling in Rate and Duty-Cycle Constrained Wireless Networks

Minimum Data-Latency-Bound $k$-Sink Placement Problem in Wireless Sensor Networks

$L^{2}:$ lazy forwarding in low-duty-cycle wireless sensor network

Breath: An Adaptive Protocol for Industrial Control Applications Using Wireless Sensor Networks

A Residual Energy Aware Schedule Scheme for WSNs Employing Adjustable Awake/Sleep Duty Cycle

Minimum data-latency-bound k-sink placement problem in wireless sensor networks

Duty-cycle-aware minimum-energy multicasting in wireless sensor networks

Similar Documents

Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks

Approximation algorithms for minimum energy transmission scheduling in rate and duty-cycle constrained wireless networks

Achieving Energy Efficiency and Reliability for Data Dissemination in Duty-Cycled WSNs

Approximation Algorithms for Minimum Energy Transmission Scheduling in Rate and Duty-Cycle Constrained Wireless Networks

Minimum Data-Latency-Bound $k$-Sink Placement Problem in Wireless Sensor Networks

$L^{2}:$ lazy forwarding in low-duty-cycle wireless sensor network

Breath: An Adaptive Protocol for Industrial Control Applications Using Wireless Sensor Networks

A Residual Energy Aware Schedule Scheme for WSNs Employing Adjustable Awake/Sleep Duty Cycle

Minimum data-latency-bound k-sink placement problem in wireless sensor networks

Duty-cycle-aware minimum-energy multicasting in wireless sensor networks