logo
Università della Svizzera italiana
  • Italiano
  • English
  • usi.ch
  • Info Desk
  • Campus map
search.usi
Search for contacts, projects,
courses and publications
Italiano
People
    Education
    • Education
    • Courses
    Research
    • Projects
    • Publications
    • Competences maps
    Organisation
    • Faculties
    • Other organizational units

    Probabilistic Breadth-First Search -- A Method for Evaluation of Network-Wide Broadcast Protocols

    Additional information

    Authors
    Lichtblau B., Dittrich A.
    Type
    Article in conference proceedings
    Year
    2014
    Language
    English
    Abstract
    In wireless mesh networks (WMNs), network-wide broadcasts (NWBs) are a fundamental operation, required by routing and other mechanisms that distribute information to all nodes in the network. However, due to the characteristics of wireless communication, NWBs are generally problematic. Optimizing them is thus a prime target when improving the overall performance and dependability of WMNs. Most of the existing optimizations neglect the real nature of WMNs and are based on simple graph models, which provide optimistic assumptions of NWB dissemination. On the other hand, models that fully consider the complex propagation characteristics of NWBs quickly become unsolvable due to their complexity. In this paper, we present the Monte Carlo method probabilistic breadth-first search (PBFS) to approximate the reachability of NWB protocols. PBFS simulates individual NWBs on graphs with probabilistic edge weights, which reflect link qualities of individual wireless links in the WMN, and estimates reachability over a configurable number of simulated runs. This approach is not only more efficient than existing ones, but further provides additional information such as the distribution of path lengths. Furthermore, it is easily extensible to NWB schemes other than flooding. The applicability of PBFS is validated both theoretically and empirically, in the latter by comparing reachability as calculated by PBFS and measured in a real-world WMN. Validation shows that PBFS quickly converges to the theoretically correct value and approximates the behaviour of real-life testbeds very well. The feasibility of PBFS to support research on NWB optimizations or higher level protocols that employ NWBs is demonstrated in two use cases.
    Conference proceedings
    6th IEEE/ACM/IFIP International Conference on New Technologies, Mobility and Security (NTMS)
    Month
    March
    Publisher
    IEEE Computer Society
    Meeting place
    Dubai, UAE
    ISBN
    9781479932238
    DOI
    10.1109/NTMS.2014.6814046
    Keywords
    Monte Carlo methods, Network-wide broadcasts, Probabilistic network graphs, Wireless mesh networks

    Faculties

    Faculty of Informatics

    Organizational units

    Advanced Learning and Research Institute (ALaRI)

    Links

    • Website
    Università della
    Svizzera italiana

    Via Buffi 13
    6900 Lugano, Switzerland
    tel +41 58 666 40 00
    fax +41 58 666 46 47
    e-mail info@usi.ch
    Other contacts
    Feedback on the website

    Maps and directions

    • Lugano Campus
    • Mendrisio Campus
    • Bellinzona Campus

    Stay in touch

    • Facebook
    • Twitter
    • Instagram
    • Youtube
    • LinkedIn
    • Newsletter
    • Annual Report
    • Subscribe
    © Università della Svizzera italiana
    Disclaimer Credits
    swissuniversities.ch
    logo
    • Faculties
    • Institutes
    • Bodies
    • Libraries and archives
    • Areas
    • Services
    • Job offers