KUKU

KU ScholarWorks

  • myKU
  • Email
  • Enroll & Pay
  • KU Directory
    • Login
    View Item 
    •   KU ScholarWorks
    • Dissertations and Theses
    • Dissertations
    • View Item
    •   KU ScholarWorks
    • Dissertations and Theses
    • Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A Framework for Service Differentiation and Optimization in Multi-hop Wireless Networks

    Thumbnail
    View/Open
    umi-ku-2751_1.pdf (7.840Mb)
    Issue Date
    2008-12-08
    Author
    Mani, Pradeepkumar
    Publisher
    University of Kansas
    Format
    130 pages
    Type
    Dissertation
    Degree Level
    PH.D.
    Discipline
    Electrical Engineering & Computer Science
    Rights
    This item is protected by copyright and unless otherwise specified the copyright of this thesis/dissertation is held by the author.
    Metadata
    Show full item record
    Abstract
    In resource-constrained networks such as multi-hop wireless networks (MHWNs), service differentiation algorithms designed to address end users' interests (e.g. user satisfaction, QoS, etc.) should also consider efficient utilization of the scarce network resources in order to maximize the network's interests (e.g. revenue). For this very reason, service differentiation in MHWNs is quite different from the wired network scenario. We propose a service differentiation tool called the ``Investment Function'', which essentially captures the network's cumulative resource investment in a given packet at a given time. This investment value can be used by the network algorithm to implement specific service differentiation principles. As proof-of-concept, we use the investment function to improve fairness among simultaneous flows that traverse varying number of hops in a MHWN (multihop flow fairness). However, to attain the optimal value of a specific service differentiation objective, optimal service differentiation and investment function parameters may need to be computed. The optimal parameters can be computed by casting the service differentiation problem as a network flow problem in MHWNs, with the goal of optimizing the service differentiation objective. The capacity constraints for these problems require knowledge of the adjacent-node interference values, and constructing these constraints could be very expensive based on the transmission scheduling scheme used. As a result, even formulating the optimization problem may take unacceptable computational effort or memory or both. Under optimal scheduling, the adjacent node interference values (and thus the capacity constraints) are not only very expensive to compute, but also cannot be expressed in polynomial form. Therefore, existing optimization techniques cannot be directly applied to solve optimization problems in MHWNs. To develop an efficient optimization framework, we first model the MHWN as a Unit Disk Graph (UDG). The optimal transmission schedule in the MHWN is related to the chromatic number of the UDG, which is very expensive to compute. However, the clique number, which is a lower bound on the chromatic number, can be computed in polynomial time in UDGs. Through an empirical study, we obtain tighter bounds on the ratio of the chromatic number to clique number in UDGs, which enables us to leverage existing polynomial time clique-discovery algorithms to compute very close approximations to the chromatic number value. This approximation not only allows us to quickly formulate the capacity constraints in polynomial form, but also allows us to significantly deviate from the traditional approach of discovering all or most of the constraints \textit{a priori}; instead, we can discover the constraints as needed. We have integrated this approach of constraint-discovery into an active-set optimization algorithm (Gradient Projection method) to solve network flow problems in multi-hop wireless networks. Our results show significant memory and computational savings when compared to existing methods.
    URI
    http://hdl.handle.net/1808/4344
    Collections
    • Dissertations [4474]
    • Engineering Dissertations and Theses [1055]

    Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.


    We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.


    Contact KU ScholarWorks
    785-864-8983
    KU Libraries
    1425 Jayhawk Blvd
    Lawrence, KS 66045
    785-864-8983

    KU Libraries
    1425 Jayhawk Blvd
    Lawrence, KS 66045
    Image Credits
     

     

    Browse

    All of KU ScholarWorksCommunities & CollectionsThis Collection

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    Contact KU ScholarWorks
    785-864-8983
    KU Libraries
    1425 Jayhawk Blvd
    Lawrence, KS 66045
    785-864-8983

    KU Libraries
    1425 Jayhawk Blvd
    Lawrence, KS 66045
    Image Credits
     

     

    The University of Kansas
      Contact KU ScholarWorks
    Lawrence, KS | Maps
     
    • Academics
    • Admission
    • Alumni
    • Athletics
    • Campuses
    • Giving
    • Jobs

    The University of Kansas prohibits discrimination on the basis of race, color, ethnicity, religion, sex, national origin, age, ancestry, disability, status as a veteran, sexual orientation, marital status, parental status, gender identity, gender expression and genetic information in the University’s programs and activities. The following person has been designated to handle inquiries regarding the non-discrimination policies: Director of the Office of Institutional Opportunity and Access, IOA@ku.edu, 1246 W. Campus Road, Room 153A, Lawrence, KS, 66045, (785)864-6414, 711 TTY.

     Contact KU
    Lawrence, KS | Maps