Tuesday, 22 July 2014
Optimization Decomposition for Scheduling and System Configuration in Wireless Networks
OPTIMIZATION DECOMPOSITION FOR SCHEDULING AND SYSTEM CONFIGURATION IN WIRELESS NETWORKS
Who gets to use radio spectrum, and when, where, and how? Scheduling (who, where, when) and system configuration (how) are fundamental problems in radio communication and wireless networking. Optimization decomposition based on Lagrangian relaxation of signal quality requirements provides a mathematical framework for solving this type of combined problem. This paper demonstrates the technique as a solution to spatial reuse time-division multiple access (STDMA) scheduling with reconfigurable antennas. The joint beam steering and scheduling (JBSS) problem offers both a challenging mathematical structure and significant practical value. We present algorithms for JBSS and describe an implemented system based on these algorithms. We achieve up to 600% of the throughput of TDMA with a mean of 234% in our experiments. The decomposition approach leads to a working distributed protocol producing optimal solutions in an amount of time that is at worst linear in the size of the input. This is, to the best of our knowledge, the first actually implemented wireless scheduling system based on dual decomposition. We identify and briefly address some of the challenges that arise in taking such a system from theory to reality.
We define scheduling as assigning users (either transmitters or links) to discrete slots of time in which they may generate radio signals. In general, this is a many-to-many mapping. We define system configuration as stipulating the way in which users access the RF spectrum in each time-slot. Each user’s transmit power, channel, modulation scheme, and antenna configuration are examples of system configuration variables. These assignments are upper bounds on how users affect each other. The combined problem is interesting when the optimal (or
feasible) configuration depends on the schedule and vice-versa, so that neither problem can be solved independently.
DISADVANTAGES OF EXISTING SYSTEM:
· It is not optimized.
· When deployed in large networks where hidden terminal effects limit performance.
We present a joint optimization process for scheduling and physical-layer configuration that achieves greater spatial reuse than solving the two problems separately. Without integration, a “chicken-and-egg” problem exists: If PHY decisions are made before scheduling, they cannot be optimized for the communication that actually occurs. If scheduling decisions are made first, the scheduler cannot know what the actual radio properties of the network will be. The joint approach produces significant gains for scheduling and antenna reconfiguration. An analysis of the performance of Our algorithm in simulation shows a mean speedup relative to simple TDMA of 234% with as much as 600% improvement in some scenarios. We also show that simple techniques such as greedy approaches to antenna steering and scheduling result in substantial interference between neighboring links.
ADVANTAGES OF PROPOSED SYSTEM:
· Optimal schedules can be found even when they depend on a specific antenna configuration and that antenna configuration would not otherwise be chosen.
· It has constraints as an “interference price” to balance power allocation between interfering links.
ü Speed - 1.1 Ghz
ü RAM - 512 MB(min)
ü Hard Disk - 40 GB
ü Key Board - Standard Windows Keyboard
ü Mouse - Two or Three Button Mouse
ü Monitor - LCD/LED
• Operating system : Windows XP
• Coding Language : Java
• Data Base : MySQL
• Tool : Net Beans IDE
Eric Anderson, Caleb Phillips, Douglas Sicker, and Dirk Grunwald,“Optimization Decomposition for Scheduling and System Configuration in Wireless Networks” IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 22, NO. 1, FEBRUARY 2014.