NDLI: Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees

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

Study of the impact of asymmetry and carrier sense mechanism in IEEE 802.11 multi-hops networks through a basic case

A novel solution for achieving anonymity in wireless ad hoc networks

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees

A simulation study on multi-rate mobile ad hoc networks

Energy efficient data retrieval for networked multi-mode wireless sensors

Wireless sensor networks protocols for efficient collision avoidance in multi-path data propagation

Adaptive service differentiation for QoS provisioning in IEEE 802.11 wireless ad hoc networks

A routing protocol for power constrained networks with asymmetric links

A framework of secure location service for position-based ad hoc routing

Power-efficient communication algorithms for wireless mobile sensor networks

Data replication effectiveness in mobile ad-hoc networks

Multipath routing and multiple description coding in ad-hoc networks: a simulation study

A differentiated distributed coordination function MAC protocol for cluster-based wireless ad hoc networks

An M/MMGI/1/K queuing model for IEEE 802.11 ad hoc networks

A performance evaluation framework for IEEE 802.11 ad-hoc networks

Node-disjointness-based multipath routing for mobile ad hoc networks

A modified IEEE 802.11 MAC protocol for MC-CDMA

Link quality-aware routing

State based key hop protocol: a lightweight security protocol for wireless networks

Evaluation of probing strategy for ad hoc networks over UTRA-TDD protocol

Ad hoc networks connection availability modeling

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees

Content Provider	ACM Digital Library
Author	Penna, Paolo Ventre, Carmine
Abstract	We investigate the problem of constructing a multicast tree in ad-hoc networks. In particular, we address the issue of the power consumption, that is, the overall energy that the stations must spend to implement such a tree. We focus on two extreme cases of multicast: broadcast (one-to-all) and unicast (one-to-one). Minimum Spanning Trees (MSTs) and Shortest-Path Trees (SPTs) yield optimal solutions for broadcast and unicast, respectively. Unfortunately, they do not guarantee any optimality for the "counterpart", that is, MSTs are non-optimal for unicast, while SPTs are non-optimal for broadcast.In this work, we experimentally evaluate the performances of an algorithm combining MST solutions with SPT ones. Our approach is based on the construction of Light Approximate Shortest-path Trees (LASTs) of a given directed weighted graph, introduced by Khuller et al [1995]. LASTs approximate simultaneously the cost of the MST and the distances of the SPT rooted at a source node, thus yielding, also in the worst case, optimal solutions for both unicast and broadcast.Rather surprisingly, this "compromise" between MSTs and SPTs, has a very good performance w.r.t the broadcast tree obtained from a MST. Indeed, for randomly-generated instances, the broadcast tree obtained with LASTs is in some cases better (and never much worse) than the broadcast tree obtained from MSTs. This important fact shows that LASTs are not only interesting in theory, but they have practical relevant applications. Indeed, their use in our experiments also provides new insights on the approximation ratio of the MST broadcast algorithm for randomly-generated instances.
Starting Page	61
Ending Page	68
Page Count	8
File Format	PDF
ISBN	1581139594
DOI	10.1145/1023756.1023769
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-10-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Energy consumption Wireless ad hoc networks Light approximate shortest-path trees Multicast trees
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

Energy-efficient broadcasting in ad-hoc networks: combining msts with shortest-path trees (2003).

Energy-efficient broadcasting in ad-hoc networks: combining msts with shortest-path trees (2003)

Constructing minimum-energy broadcast trees in wireless ad hoc networks

A Distributed Algorithm for Refining Energy-Efficiency of Multicast Trees in Wireless Ad Hoc Networks

Energy-efficient broadcast and multicast routing in ad hoc wireless networks

Energy Efficient Multicast Routing for Discrete Power Levels in Ad Hoc Sensor Networks

Energy efficient and robust multicast protocol for mobile ad hoc networks

G-REMiT: An algorithm for building energy efficient multicast trees in wireless ad hoc networks

On maximizing lifetime of multicast trees in wireless ad hoc networks

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees

Similar Documents

Energy-efficient broadcasting in ad-hoc networks: combining msts with shortest-path trees (2003).

Energy-efficient broadcasting in ad-hoc networks: combining msts with shortest-path trees (2003)

Constructing minimum-energy broadcast trees in wireless ad hoc networks

A Distributed Algorithm for Refining Energy-Efficiency of Multicast Trees in Wireless Ad Hoc Networks

Energy-efficient broadcast and multicast routing in ad hoc wireless networks

Energy Efficient Multicast Routing for Discrete Power Levels in Ad Hoc Sensor Networks

Energy efficient and robust multicast protocol for mobile ad hoc networks

G-REMiT: An algorithm for building energy efficient multicast trees in wireless ad hoc networks

On maximizing lifetime of multicast trees in wireless ad hoc networks

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees