NDLI: A Message-Passing Algorithm for Wireless Network Scheduling

Content Provider	IEEE Xplore Digital Library
Author	Paschalidis, I.C. Fuzhuo Huang Wei Lai
Copyright Year	1993
Abstract	We consider scheduling in wireless networks and formulate it as a Maximum Weighted Independent Set (MWIS) problem on a “conflict” graph that captures interference among simultaneous transmissions. We propose a novel, low-complexity, and fully distributed algorithm that yields high-quality feasible solutions. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing. The first phase solves a relaxation of the MWIS problem using a gradient projection method. The relaxation we consider is tighter than the simple linear programming relaxation and incorporates constraints on all cliques in the graph. The second phase of the algorithm starts from the solution of the relaxation and constructs a feasible solution to the MWIS problem. We show that our algorithm always outputs an optimal solution to the MWIS problem for perfect graphs. Simulation results compare our policies against carrier sense multiple access (CSMA) and other alternatives and show excellent performance.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	1528
Ending Page	1541
Page Count	14
File Size	2496956
File Format	PDF
ISSN	10636692
Volume Number	23
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wireless networks Vectors Interference Scheduling Bipartite graph Throughput Polynomials wireless networks Distributed algorithms graph theory Maximum Weighted Independent Set problem message-passing scheduling
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

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

Distributed scheduling of wireless networks: A message passing approach

A message-passing algorithm for wireless network scheduling

Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels

Low-Complexity Distributed Scheduling Algorithms for Wireless Networks

Distributed Link Scheduling With Constant Overhead

Distributed Throughput Maximization in Wireless Mesh Networks via Pre-Partitioning

Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory

Message Passing for Maximum Weight Independent Set

Distributed power allocation for interfering wireless links based on channel information partitioning

A Message-Passing Algorithm for Wireless Network Scheduling

Similar Documents

Distributed scheduling of wireless networks: A message passing approach

A message-passing algorithm for wireless network scheduling

Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels

Low-Complexity Distributed Scheduling Algorithms for Wireless Networks

Distributed Link Scheduling With Constant Overhead

Distributed Throughput Maximization in Wireless Mesh Networks via Pre-Partitioning

Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory

Message Passing for Maximum Weight Independent Set

Distributed power allocation for interfering wireless links based on channel information partitioning

A Message-Passing Algorithm for Wireless Network Scheduling