MURAL - Maynooth University Research Archive Library

    Learning-Based Constraint Satisfaction With Sensing Restrictions

    Checco, Alessandro and Leith, Douglas J. (2013) Learning-Based Constraint Satisfaction With Sensing Restrictions. IEEE Journal of Selected Topics in Signal Processing, 7 (5). pp. 811-820. ISSN 1932-4553

    Download (887kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    In this paper we consider graph-coloring problems, an important subset of general constraint satisfaction problems that arise in wireless resource allocation. We constructively establish the existence of fully decentralized learning-based algorithms that are able to find a proper coloring even in the presence of strong sensing restrictions, in particular sensing asymmetry of the type encountered when hidden terminals are present. Our main analytic contribution is to establish sufficient conditions on the sensing behaviour to ensure that the solvers find satisfying assignments with probability one. These conditions take the form of connectivity requirements on the induced sensing graph. These requirements are mild, and we demonstrate that they are commonly satisfied in wireless allocation tasks. We argue that our results are of considerable practical importance in view of the prevalence of both communication and sensing restrictions in wireless resource allocation problems. The class of algorithms analysed here requires no message-passing whatsoever between wireless devices, and we show that they continue to perform well even when devices are only able to carry out constrained sensing of the surrounding radio environment.

    Item Type: Article
    Additional Information: This is the postprint version of the published article, which is available at DOI: 10.1109/JSTSP.2013.2251604
    Keywords: Learning-Based algorithms; Constraint Satisfaction; Sensing Restrictions; graph-coloring problems;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 6966
    Identification Number:
    Depositing User: Hamilton Editor
    Date Deposited: 09 Feb 2016 12:26
    Journal or Publication Title: IEEE Journal of Selected Topics in Signal Processing
    Publisher: Institute of Electrical and Electronics Engineers (IEEE)
    Refereed: Yes
    Funders: Science Foundation Ireland (SFI)
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads