• Login
    View Item 
    •   Mak IR Home
    • College of Computing and Information Sciences (CoCIS)
    • School of Computing and Informatics Technology (CIT)
    • School of Computing and Informatics Technology (CIT) Collection
    • View Item
    •   Mak IR Home
    • College of Computing and Information Sciences (CoCIS)
    • School of Computing and Informatics Technology (CIT)
    • School of Computing and Informatics Technology (CIT) Collection
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Distributed topology control for mobile Ad Hoc networks: exploring the P/NP boundary

    Thumbnail
    View/Open
    Thesis, Masters (528.1Kb)
    Date
    2005-10
    Author
    Opiyo, Nockline
    Metadata
    Show full item record
    Abstract
    The design goal of topology control in mobile ad hoc networks (MANET) discussed in this work is to construct a topology that guarantees network connectivity and maintain network performance. This work proposes, decentralized distributed Minimum Spanning Tree algorithm, a modification of Prim’s MST algorithm which is effective for topology control in MANET. The algorithm self-organizes the network topology. The process begins by each node constructing its own Minimum Spanning Tree (MST) topology, keeping on its tree only nodes that are one-hop away within its visible neighborhood. Followed by an optimization phase to ensure that the network has bi-directional links in order to maintain a strong network connectivity. The work also explored the Traveling Salesman Problem (TSP) boundary and proposed an approximation algorithm which is a modification of Christofides heuristics. Then lastly we discuss the merits and the demerits of the proposed topology control scheme and outline some relevant issues for future research.
    URI
    http://hdl.handle.net/10570/691
    Collections
    • School of Computing and Informatics Technology (CIT) Collection

    DSpace 5.8 copyright © Makerere University 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of Mak IRCommunities & CollectionsTitlesAuthorsBy AdvisorBy Issue DateSubjectsBy TypeThis CollectionTitlesAuthorsBy AdvisorBy Issue DateSubjectsBy Type

    My Account

    LoginRegister

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    DSpace 5.8 copyright © Makerere University 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV