dc.contributor.advisor Petr, David W dc.contributor.author Mani, Pradeepkumar dc.date.accessioned 2009-02-02T06:05:40Z dc.date.available 2009-02-02T06:05:40Z dc.date.issued 2008-12-08 dc.date.submitted 2008 dc.identifier.other http://dissertations2.umi.com/ku:2751 dc.identifier.uri http://hdl.handle.net/1808/4344 dc.description.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. dc.format.extent 130 pages dc.language.iso EN dc.publisher University of Kansas dc.rights This item is protected by copyright and unless otherwise specified the copyright of this thesis/dissertation is held by the author. dc.subject Electronics and electrical engineering dc.subject Computer science dc.subject Multi-hop wireless dc.subject Optimization dc.subject Investment function dc.subject Fairness dc.subject Interference dc.title A Framework for Service Differentiation and Optimization in Multi-hop Wireless Networks dc.type Dissertation dc.contributor.cmtemember Frost, Victor dc.contributor.cmtemember Evans, Joseph B. dc.contributor.cmtemember Kong, Man dc.contributor.cmtemember Van Vleck, Erik dc.thesis.degreeDiscipline Electrical Engineering & Computer Science dc.thesis.degreeLevel PH.D. kusw.oastatus na kusw.oapolicy This item does not meet KU Open Access policy criteria. kusw.bibid 6857281 dc.rights.accessrights openAccess
﻿

### This item appears in the following Collection(s)

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

KU Libraries
1425 Jayhawk Blvd
Lawrence, KS 66045