NDLI: Energy conservation via domatic partitions

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

MISTRAL: efficient flooding in mobile ad-hoc networks

Performance analysis of mobility-assisted routing

Balancing distance and lifetime in delay constrained ad hoc networks

Deploying wireless sensors to achieve both coverage and connectivity

Interaction of rate and medium access control in wireless networks: the single cell case

MLS: an efficient location service for mobile ad hoc networks

Throughput and delay optimization in interference-limited multihop networks

Wakeup scheduling in wireless sensor networks

Minimizing recovery state In geographic ad-hoc routing

Model T++: an empirical joint space-time registration model

An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces

Energy conservation via domatic partitions

DRAND: distributed randomized TDMA scheduling for wireless ad-hoc networks

RaWMS -: random walk based lightweight membership service for wireless ad hoc network

Proportionally fair allocation of end-to-end bandwidth in STDMA wireless networks

Fundamental scaling laws for energy-efficient storage and querying in wireless sensor networks

Asymptotic critical transmission radius for greedy forward routing in wireless ad hoc networks

Analysis of random mobility models with PDE's

Jamming and sensing of encrypted wireless ad hoc networks

Delay of intrusion detection in wireless sensor networks

Adaptive splitting protocols for RFID tag collision arbitration

Robust distributed node localization with error management

Algorithmic aspects of communication in ad-hoc networks with smart antennas

Data storage placement in sensor networks

Message ferry route design for sparse ad hoc networks with mobile nodes

Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application

Mobile backbone networks --: construction and maintenance

Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks

Distributed localization using noisy distance and angle information

Topology control meets SINR: the scheduling complexity of arbitrary topologies

SDAP: a secure hop-by-Hop data aggregation protocol for sensor networks

Energy conservation via domatic partitions

Content Provider	ACM Digital Library
Author	Pirwani, Imran A. Pemmaraju, Sriram V.
Abstract	Using a dominating set as a coordinator in wireless networks has been proposed in many papers as an energy conservation technique. Since the nodes in a dominating set have the extra burden of coordination, energy resources in such nodes will drain out more quickly than in other nodes. To maximize the lifetime of nodes in the network,it has been proposed that the role of coordinators be rotated among the nodes in the network. One abstraction that has been considered for the problem of picking a collection of coordinators and cycling through them, is the domatic partition problem. This is the problem of partitioning the set of the nodes of the network into dominating sets with the aim of maximizing the number of dominating sets. In this paper,we consider the k -domatic partition problem. A k -dominating set is a subset D of nodes such that every node in the network is at distance at most k from D. The k-domatic partition problem seeks to partition the network into maximum number of k-dominating sets.We point out that from the point of view of saving energy,it may be better to construct a k-domatic partition for k >1.We present three deterministic, distributed algorithms for finding large k-domatic partitions for k > 1. Each of our algorithms constructs a k-domatic partition of size at least a constant fraction of the largest possible (k 1)-domatic partition. Our first algorithm runs in constant time on unit ball graphs (UBGs) in Euclidean space assuming that all nodes know their positions in a global coordinate system. Our second algorithm drops knowledge of global coordinates and instead assumes that pairwise distances between neighboring nodes are known. This algorithm runs in O(log* n ) time on UBGs in a metric space with constant doubling dimension. Our third algorithm drops all reliance on geometric information, using connectivity information only. This algorithm runs in O(log Δ · log *n) time on growth-bounded graphs. Euclidean UBGs, UBGs in metric spaces with constant doubling dimension, and growth-bounded graphs are successively more general models of wireless networks and all three models include the well-known, but somewhat simplistic wireless network models such as unit disk graphs.
Starting Page	143
Ending Page	154
Page Count	12
File Format	PDF
ISBN	1595933689
DOI	10.1145/1132905.1132922
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-05-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Network decomposition Dominating sets Metric space Unit ball graphs Doubling dimension Growth-bounded graphs Distributed algorithms Maximal independent sets Unit disk graphs Domatic partition
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

On the locality of bounded growth

Energy Conservation in Wireless Sensor Networks via Domatic Partitions (2006)

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Energy Conservation via Domatic Partitions (2006)

Energy Conservation via Domatic Partitions (2006)

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Minimal dominating sets in maximum domatic partitions (2012).

A log-star distributed maximal independent set algorithm for growth-bounded graphs (2008).

Matched-Factor d-Domatic Coloring of Graphs

Energy conservation via domatic partitions

Similar Documents

On the locality of bounded growth

Energy Conservation in Wireless Sensor Networks via Domatic Partitions (2006)

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Energy Conservation via Domatic Partitions (2006)

Energy Conservation via Domatic Partitions (2006)

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Minimal dominating sets in maximum domatic partitions (2012).

A log-star distributed maximal independent set algorithm for growth-bounded graphs (2008).

Matched-Factor d-Domatic Coloring of Graphs

Energy conservation via domatic partitions