Analysis of bandwidth allocation algorithms for wireless personal area networks

A major issue in the design and operation of ad hoc networks is sharing the common spectrum among links in the same geographic area. Bandwidth allocation, to optimize the performance of networks in which each station can converse with at most a single neighbor at a time, has been recently studied in the context of Bluetooth Personal Area Networks. There, centralized and distributed, capacity assignment heuristics were developed, with applicability to a variety of ad hoc networks. Yet, no guarantees on the performance of these heuristics have been provided. In this paper, we extend these heuristics such that they can operate with general convex objective functions. Then, we present our analytic results regarding these heuristics. Specifically, we show that they are β-approximation (β<2) algorithms. Moreover, we show that even though the distributed and centralized algorithms allocate capacity in a different manner, both algorithms converge to the same results. Finally, we present numerical results that demonstrate the performance of the algorithms. Randeep Bhatia received the Ph.D. degree in Computer Science from University of Maryland, the M.S. degree in Mathematics and Computer Science from University of Illinois at Chicago and the B.Tech. degree in Computer Science and Engineering from Indian Institute of Technology, Delhi. He is currently with the High Speed Networks Research Department at Bell Labs, Lucent technologies, working on network design, traffic engineering and scheduling algorithms. His current research interests are in the area of QoS for multimedia services in wireless data networks. Adrian Segall received the B.Sc. and M.Sc. degrees in electrical engineering from the Technion, Israel Institute of Technology in 1965 and 1971, respectively, and the Ph.D. degree in electrical engineering with a minor in statistics from Stanford University in 1973. After serving active duty in the Israel Defense Forces, he joined in 1968 the Scientific Department of Israel’s Ministry of Defense. From 1973 to 1974 he was a Research Engineer at System Control Inc., Palo Alto, CA and a Lecturer at Stanford University. From 1974 to 1976 he was an Assistant Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. From 1987 to 1998 he was on the faculty of the Department of Computer Science at the Technion. He is presently Benjamin Professor of Computer-Communication Networks in the Department of Electrical Engineering, Technion, Israel Institute of Technology. From 1982 to 1984 he was on leave with the IBM T.J.Watson Research Center, Yorktown Heights, NY. He held visiting positions with IBM, AT&T and Lucent Bell Labs. His current research interests are in the area of optical networks, wireless, sensor and ad-hoc networks. Dr. Segall is an IEEE Fellow and has served in the past as Editor for Computer Communication Theory of the IEEE Transactions on Communications, Editor for the IEEE Information Theory Society Newsletter and Senior Editor for the IEEE Journal on Selected Areas in Communications. He was selected as an IEEE delegate to the 1975 IEEE-USSR Information Theory Workshop, and is the recipient of the 1981 Miriam and Ray Klein Award for Outstanding Research and of the 1990 Taub Award in Computer Science. Gil Zussman received the B.Sc. degree in Industrial Engineering and Management and the B.A. degree in Economics (both summa cum laude) from the Technion—Israel Institute of Technology in 1995. He received the M.Sc. degree (summa cum laude) in Operations Research from Tel-Aviv University in 1999 and the Ph.D. degree in Electrical Engineering from the Technion—Israel Institute of Technology in 2004. Between 1995 and 1998, he served as an engineer in the Israel Defense Forces. He is currently a Postdoctoral Associate in the Laboratory for Information and Decision Systems in MIT. His current research interests are in the area of ad hoc and sensor networks. In particular, he is interested in energy efficient protocols, medium access control protocols, and personal area networks. Gil received the Knesset (Israeli Parliament) Award for distinguished students, the Best Student Paper Award at the IFIP-TC6 Networking 2002 Conference, and the IEEE Communications Magazine Best Paper Award at the OPNETWORK 2002 Conference. In 2004 he received the Marie Curie Outgoing International Fellowship and the Fulbright Fellowship.