etd AT Indian Institute of Science >
Division of Electrical Sciences >
Department of Electronic Systems Engineering (dese) >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2005/798

Title:  Joint Congestion Control, Routing And Distributed Link Scheduling In Power Constrained Wireless Mesh Networks 
Authors:  Sahasrabudhe, Nachiket S 
Advisors:  Kuri, Joy 
Keywords:  Wireless Mesh Networks (WMNs) Electric Power System Traffic Control Congestion Control CrossLayer Optimization Routing Distributed Scheduling Greedy Heuristics Multihop Wireless Networks  Link Scheduling Greedy Scheduling Scheduling Algorithms 
Submitted Date:  Nov2008 
Series/Report no.:  G22607 
Abstract:  We study the problem of joint congestion control, routing and MAC layer scheduling in multihop wireless mesh networks, where the nodes in the network are subjected to energy expenditure rate constraints. As wireless scenario does not allow all the links to be active all the time, only a subset of given links can be active simultaneously. We model the interlink interference using the link contention graph. All the nodes in the network are powerconstrained and we model this constraint using energy expenditure rate matrix. Then we formulate the problem as a network utility maximization (NUM) problem. We notice that this is a convex optimization problem with affine constraints. We apply duality theory and decompose the problem into two subproblems namely, network layer congestion control and routing problem, and MAC layer scheduling problem. The source adjusts its rate based on the cost of the least cost path to the destination where the cost of the path includes not only the prices of the links in it but also the prices associated with the nodes on the path. The MAC layer scheduling of the links is carried out based on the prices of the links. The optimal scheduler selects that set of noninterfering links, for which the sum of link prices is maximum.
We study the effects of energy expenditure rate constraints of the nodes on the maximum possible network utility. It turns out that the dominant of the two constraints namely, the link capacity constraint and the node energy expenditure rate constraint affects the network utility most.
Also we notice the fact that the energy expenditure rate constraints do not affect the nature of optimal link scheduling problem. Following this fact, we study the problem of distributed link scheduling. Optimal scheduling requires selecting independent set of maximum aggregate price, but this problem is known to be NPhard. We first show that as long as scheduling policy selects the set of noninterfering links, it can not go unboundedly away from the optimal solution of network utility maximization problem. Then we proceed and evaluate a simple greedy scheduling algorithm. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice. 
URI:  http://hdl.handle.net/2005/798 
Appears in Collections:  Department of Electronic Systems Engineering (dese)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
