Research Article
Maximizing Network Utilization with Max-Min Fairness in Wireless Sensor Networks
@INPROCEEDINGS{10.1109/WIOPT.2007.4480030, author={Avinash Sridharan and Bhaskar Krishnamachar}, title={Maximizing Network Utilization with Max-Min Fairness in Wireless Sensor Networks}, proceedings={5th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks}, publisher={IEEE}, proceedings_a={WIOPT}, year={2008}, month={3}, keywords={Algorithm design and analysis Bandwidth Computer networks Data mining Distributed algorithms Interference Radio communication Receivers Wireless networks Wireless sensor networks}, doi={10.1109/WIOPT.2007.4480030} }- Avinash Sridharan
Bhaskar Krishnamachar
Year: 2008
Maximizing Network Utilization with Max-Min Fairness in Wireless Sensor Networks
WIOPT
IEEE
DOI: 10.1109/WIOPT.2007.4480030
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.
