Link scheduling in wireless sensor networks: distributed edge-coloring revisited

DOI10.1016/J.JPDC.2007.12.006MaRDI QIDQ436862zbMATH OpenOpenAlexFDO

Authors Shashidhar Gandham, Milind Dawande, Ravi Prakash

Publication date 26 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2007.12.006

zbMATH Keywords

wireless sensor networksdistributed edge-coloringlink scheduling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Distributed \((\varDelta + 1)\)-coloring in the physical model
• Distance edge coloring and collision-free communication in wireless sensor networks
• Local Algorithms for Edge Colorings in UDGs
• Local algorithms for edge colorings in UDGs

Cites work

• scientific article; zbMATH DE number 710624 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A constructive proof of Vizing's theorem
• A routing algorithm for wireless ad hoc networks with unidirectional links
• An experimental study of a simple, distributed edge-coloring algorithm
• Energy optimal data propagation in wireless sensor networks
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• Link scheduling in polynomial time
• Models and approximation algorithms for channel assignment in radio networks
• Multihop medium access control for WSNs: an energy analysis model
• Nearly optimal distributed edge coloring in O(log log n) rounds
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

Cited in

(10)

• Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
• Local algorithms for edge colorings in UDGs
• Distributed edge coloration for bipartite networks
• The minimum scheduling time for convergecast in wireless sensor networks
• Backbone colouring and algorithms for TDMA scheduling
• Hypergraph-based data link layer scheduling for reliable packet delivery in wireless sensing and control networks with end-to-end delay constraints
• Distributed colorings for collision-free routing in sink-centric sensor networks
• Distance edge coloring and collision-free communication in wireless sensor networks
• Minimum multiplicity edge coloring via orientation
• The backbone packet radio network coloring for time division multiple access link scheduling in wireless multihop networks

This page was built for publication: Link scheduling in wireless sensor networks: distributed edge-coloring revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q436862)