IISc Logo    Title

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
Cross-Layer Optimization
Distributed Scheduling
Greedy Heuristics
Multi-hop Wireless Networks - Link Scheduling
Greedy Scheduling
Scheduling Algorithms
Submitted Date: Nov-2008
Series/Report no.: G22607
Abstract: We study the problem of joint congestion control, routing and MAC layer scheduling in multi-hop 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 inter-link interference using the link contention graph. All the nodes in the network are power-constrained 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 sub-problems 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 non-interfering 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 NP-hard. We first show that as long as scheduling policy selects the set of non-interfering 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://etd.iisc.ernet.in/handle/2005/798
Appears in Collections:Department of Electronic Systems Engineering (dese)

Files in This Item:

File Description SizeFormat
G22607.PDF447.46 kBAdobe PDFView/Open

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


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01