{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:45Z","timestamp":1759638345398},"reference-count":39,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","funder":[{"name":"ANR program Investments for the Future","award":["ANR-11-LABX-0031-01"],"award-info":[{"award-number":["ANR-11-LABX-0031-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:p> This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, \u201cneighboring links\u201d cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We use the model described by Bui et al. in [L. X. Bui, S. Sanghavi and R. Srikant, Distributed link scheduling with constant overhead, IEEE\/ACM Trans. Netw. 17(5) (2009) 1467\u20131480; S. Sanghavi, L. Bui and R. Srikant, Distributed link scheduling with constant overhead, in Proc. ACM Sigmetrics (San Diego, CA, USA, 2007), pp. 313\u2013324.]. We assume that time is slotted and during each slot there are two phases: one control phase in which a link scheduling algorithm determines a set of non-interfering links to be activated, and a data phase in which data is sent through these links. We assume random arrivals on each link during each slot, so that a queue is associated to each link. Since nodes do not have a global knowledge of the queues sizes, our aim (like in [L. X. Bui, S. Sanghavi and R. Srikant, Distributed link scheduling with constant overhead, IEEE\/ACM Trans. Netw. 17(5) (2009) 1467\u20131480; S. Sanghavi, L. Bui and R. Srikant, Distributed link scheduling with constant overhead, in Proc. ACM Sigmetrics (San Diego, CA, USA, 2007), pp. 313\u2013324.]) is to design a distributed link scheduling algorithm. To be efficient, the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this paper, we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues), and it does not require any knowledge of the queue-lengths. We prove that this algorithm gives a maximal set of active links, where for any non-active link there exists at least one active link in its interference set. We also establish sufficient conditions for stability under general Markovian assumptions. Finally, the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes. <\/jats:p>","DOI":"10.1142\/s1793830920500585","type":"journal-article","created":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T04:04:12Z","timestamp":1594958652000},"page":"2050058","source":"Crossref","is-referenced-by-count":4,"title":["Distributed link scheduling in wireless networks"],"prefix":"10.1142","volume":"12","author":[{"given":"Jean-Claude","family":"Bermond","sequence":"first","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur-CNRS-Inria-I3S, 2004 Route des Lucioles, B.P. 93, F-06902, Sophia Antipolis, France"}]},{"given":"Dorian","family":"Mazauric","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur-CNRS-Inria-I3S, 2004 Route des Lucioles, B.P. 93, F-06902, Sophia Antipolis, France"}]},{"given":"Vishal","family":"Misra","sequence":"additional","affiliation":[{"name":"Department Computer Science, Columbia University, New York, NY, USA"}]},{"given":"Philippe","family":"Nain","sequence":"additional","affiliation":[{"name":"Inria, ENS de Lyon\/LIP, 46 avenue d\u2019Italie, Lyon 69364, France"}]}],"member":"219","published-online":{"date-parts":[[2020,7,17]]},"reference":[{"key":"S1793830920500585BIB001","volume-title":"Stochastic Geometry and Wireless Networks Volume II: Applications","author":"Baccelli F.","year":"2010"},{"key":"S1793830920500585BIB002","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2004.830909"},{"key":"S1793830920500585BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811079"},{"key":"S1793830920500585BIB004","first-page":"357","volume-title":"Graphs and Algorithms in Communication Networks, Studies in Broadband, Optical, Wireless and Ad Hoc Networks","author":"Bonifaci V.","year":"2010"},{"key":"S1793830920500585BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3124-8"},{"key":"S1793830920500585BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/1161089.1161094"},{"key":"S1793830920500585BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2013621"},{"key":"S1793830920500585BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90275-F"},{"key":"S1793830920500585BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.913537"},{"key":"S1793830920500585BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/MWS.2009.13"},{"key":"S1793830920500585BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"S1793830920500585BIB012","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.65"},{"key":"S1793830920500585BIB013","series-title":"Research Notes in Mathematics","volume-title":"Edge-Colourings of Graphs","volume":"16","author":"Fiorini S.","year":"1977"},{"key":"S1793830920500585BIB014","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"S1793830920500585BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2021609"},{"key":"S1793830920500585BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2081490"},{"key":"S1793830920500585BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797741"},{"key":"S1793830920500585BIB018","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2089804"},{"key":"S1793830920500585BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.048"},{"key":"S1793830920500585BIB020","first-page":"1021","volume-title":"Proc. ACM-SIAM Soda","author":"Kumar V. S. A.","year":"2004"},{"key":"S1793830920500585BIB021","volume-title":"Matching Theory, Annals of Discrete Mathematics","volume":"29","author":"Lov\u00e1sz L.","year":"1986"},{"key":"S1793830920500585BIB022","first-page":"70","volume-title":"Proc. Fourth Annual IEEE Int. Conf. on Prevasive Computing and Communications Workshops, Pisa, Italy","author":"Mazumdar R.","year":"2006"},{"key":"S1793830920500585BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-3267-7"},{"key":"S1793830920500585BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90041-S"},{"key":"S1793830920500585BIB025","doi-asserted-by":"publisher","DOI":"10.1145\/1140277.1140283"},{"key":"S1793830920500585BIB026","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555365"},{"key":"S1793830920500585BIB027","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254920"},{"key":"S1793830920500585BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-012-9306-x"},{"key":"S1793830920500585BIB029","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP763"},{"key":"S1793830920500585BIB030","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.99"},{"key":"S1793830920500585BIB031","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP759"},{"key":"S1793830920500585BIB032","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2016.7510904"},{"key":"S1793830920500585BIB033","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2017.2762667"},{"key":"S1793830920500585BIB034","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465758"},{"key":"S1793830920500585BIB035","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"S1793830920500585BIB036","doi-asserted-by":"publisher","DOI":"10.1109\/18.568722"},{"key":"S1793830920500585BIB037","doi-asserted-by":"publisher","DOI":"10.1109\/9.182479"},{"key":"S1793830920500585BIB038","doi-asserted-by":"publisher","DOI":"10.1145\/1530748.1530761"},{"key":"S1793830920500585BIB039","volume-title":"Proc. of Information Theory and Applications Inaugural Workshop","author":"Wu X.","year":"2006"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830920500585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T07:24:38Z","timestamp":1601623478000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830920500585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,17]]},"references-count":39,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.1142\/S1793830920500585"],"URL":"https:\/\/doi.org\/10.1142\/s1793830920500585","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,17]]}}}