Title :
Maximizing Network Utilization with Max-Min Fairness in Wireless Sensor Networks
Author :
Sridharan, Avinash ; Krishnamachari, Bhaskar
Author_Institution :
Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA
Abstract :
The state of the art for optimal data-gathering in wireless sensor networks is to use additive increase algorithms to achieve fair rate allocation while implicity trying to maximize network utilization. We explicitly formulate the problem of maximizing the network utilization subject to a max-min fair rate allocation constraint in the form of two coupled linear programs. We first show how the max-min rate can be computed efficiently for a given network. We then adopt a dual-based approach to maximize the network utilization. The analysis of the dual shows the sub-optimality of previously proposed additive increase algorithms with respect to bandwidth efficiency. Although in theory a dual-based sub-gradient search algorithm can take a long time to converge, we find empirically that setting shadow prices to 1 results in near-optimal solutions within one iteration (within 2% of the optimum in 99.65% of the cases). This results in a fast heuristic distributed algorithm that has a nice intuitive explanation - rates are allocated sequentially after rank ordering flows based on the number of downstream receivers whose bandwidth they consume.
Keywords :
bandwidth allocation; gradient methods; minimax techniques; search problems; wireless sensor networks; bandwidth efficiency; coupled linear programs; downstream receivers; dual-based sub-gradient search algorithm; fair rate allocation; fast heuristic distributed algorithm; max-min fairness; maximizing network utilization; optimal data-gathering; rank ordering flows; wireless sensor networks; Algorithm design and analysis; Bandwidth; Computer networks; Data mining; Distributed algorithms; Interference; Radio communication; Receivers; Wireless networks; Wireless sensor networks;
Conference_Titel :
Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, 2007. WiOpt 2007. 5th International Symposium on
Conference_Location :
Limassol
Print_ISBN :
978-1-4244-0960-0
Electronic_ISBN :
978-1-4244-0961-7
DOI :
10.1109/WIOPT.2007.4480030