1330 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 90 percent confidence interval for the total throughput. Grant No.2009CB320705;the Technology Support Program Note that in both the dense AP situation and sparse AP of Jiangsu Province under Grant No.BE2010179;the US situation,OPT-E(offline)achieves the largest overall National Science Foundation(NSF)under Grant Nos.CNS- throughput,while CUB achieves the smallest throughput. 0721443 and CNS-0831904,CAREER Award CNS-0747108, Due to some nonpredictable issues,OPT-E(online)achieves CNS-0434533,CNS-0531410,and CNS-0626240. a little smaller value for the overall throughput than OPT- E(offline).All solutions in the sparse AP situation achieves a fairly smaller overall throughput compared to the dense AP REFERENCES situation,as fewer aPs are available for association to [1]J.Ott and D.Kutscher,"Drive-thru Internet:IEEE 802.11b for 'Automobile'Users,"Proc.IEEE INFOCOM,2004. provide sufficient throughput for users.We observed that 2☒ J.Camp and E.Knightly,"Modulation Rate Adaptation in Urban in both situations the optimized solutions outperform the and Vehicular Environments:Cross-Layer Implementation and two heuristic solutions.In the dense AP situation OPT- Experimental Evaluation,"Proc.ACM MOBICOM,2008. E(online),respectively,achieves 72.9 and 122.9 percent more L.Tassiulas and S.Sarkar,"Maxmin Fair Scheduling in Wireless Ad Hoc Networks,"IEEE I.Selected Areas in Comm.,vol.23,no.1, throughput than SSF and CUB,while in the sparse AP Pp.163-173,Jan.2005. situation OPT-E(online),respectively,achieves 30.6 and 73.7 [4 Y.Bejerano,S.-J.Han,and L Li,"Fairness and Load Balancing in percent more throughput than SSF and CUB.Since users Wireless LANs Using Association Control,"IEEE/ACM Trans. Networking,vol.15,no.3,pp.560-573,June 2007. have more candidate aPs to associate with in the dense aP L.Li,M.Pal,and Y.R.Yang,"Proportional Fairness in Multi-Rate situation,there exist more opportunities for an optimized Wireless LANs,"Proc.IEEE INFOCOM,2008. solution to achieve more performance gains. [阿 V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden "A Measurement Study of Vehicular Internet Access Using In Situ In order to show the performance comparison in terms of Wi-Fi Networks,"Proc.ACM MOBICOM,2006. fairness,Fig.4b illustrates per-user throughput comparison ☑ J.Eriksson,H.Balakrishnan,and S.Madden,"Cabernet:Vehicular in the dense AP situation.The X-axis is the user index and the Content Delivery Using Wi-Fi,"Proc.ACM MOBICOM,2008. Y-axis is users'throughput in kbps.The users are sorted by © A.Giannoulis,M.Fiore,and E.W.Knightly,"Supporting Vehicular Mobility in Urban Multi-Hop Wireless Networks, their throughput in increasing order.The throughput of the Proc.ACM Mobile Systems,Applications,and Services (MOBISYS), user with the same x index actually indicates the average 2008. throughput of the zth lowest throughput user (users [9 R.Mahajan,I.Zahorjan,and B.Zill,"Understanding WiFi-Based allocated the cth lowest bandwidth).In the dense AP Connectivity,"Proc.ACM Internet Measurement Conf.(IMC),2007. [10]D.Hadaller,S.Keshav,T.Brecht,and S.Agarwal,"Vehicular situation,we observe that the optimized solutions OPT- Opportunistic Communication under the Microscope,"Proc.ACM E(online),OPT-PF(offline),OPT-PF(online)and OPT-MM all Mobile Systems,Applications,and Services(MOBISYS),2007. outperform the two heuristic solutions SSF and CUB.For [l1]V.Navda,A.P.Subramanian,K.Dhanasekaran,A.Timm-Giel, and S.R.Das,"Mobisteer:Using Steerable Beam Directional instance,the median indexed user's bandwidth value of Antenna for Vehicular Network Access,"Proc.ACM MOBISYS, OPT-E(online)is,respectively,64 percent higher than SSF and 2007. 181 percent higher than CUB.OPT-PF(offline),OPT-PF(online) [12]M.Kim,Z.Liu,S.Parthasarathy,D.Pendarakis,and H.Yang and OPT-MM have better performance in fairness than OPT- "Association Control in Mobile Wireless Networks,"Proc.IEEE INFOCOM,2008. E(online),since the users with lower indices have higher [13]P.Deshpande,A.Kashyap,C.Sung,and S.Das,"Predictive throughput in OPT-PF(offline),OPT-PF(online)and OPT-MM Methods for Improved Vehicular Wifi Access,"Proc.ACM Mobile compared to OPT-E(online).Among the three solutions,OPT- Systems,Applications,and Services (MOBISYS),2009. MM achieves the best performance in fairness,as the users [14]H.Wu,K.Tan,Y.Zhang,and Q.Zhang,"Proactive Scan:Fast Handoff with Smart Triggers for 802.11 Wireless Lan,"Proc. with lower indices are higher than all the other solutions, INFOCOM,2007. inferring that more fairness is achieved among the users.The [1 T.Nandagopal,T.-E.Kim,X.Gao,and V.Bharghavan,"Achieving performance gains of the above optimized solutions are Mac Layer Fairness in Wireless Packet Networks,"Proc.ACM MOBICOM,pp.87-98,2000. between 200 and 400 kbps in throughput for each user. [16 R.Murty,J.'Padhye,A.Wolman,and B.Zill,"Designing High Performance Enterprise Wi-Fi Networks,"Proc.ACM Networked Systems Design and Implementation (NSDI),2008. 6 CONCLUSION [17]D.B.Shmoys and E.Tardos,"An Approximation Algorithm for the Generalized Assignment Problem,"Math.Programming, In this paper,we conduct a theoretical study on association vol.62,no.3,PP.461-474,1993. control over the Drive-thru Internet scenario.We,respec- 18] "Sumo,"http://sourceforge.net/apps/mediawiki/sumo/,2011. tively,consider efficiency and fairness as the optimization [19] "Tiger,"www.census.gov/geo/www/tiger/,2011. metrics.Due to issues concerning both technology and privacy,the data needed to compute the optimal solutions are currently not easy to gather.Hence,our present research Lei Xie received the BS and PhD degrees from work intends to be a theoretical effort to determine the Nanjing University in 2004 and 2010,respec- tively,all in computer science.He is an upper bounds to what can be achieved in reality. assistant professor in the Department of Computer Science and Technology,Nanjing University,China.His research interests in- ACKNOWLEDGMENTS clude sensor networks,RFID systems,vehicu- lar networks,cognitive radios,and high The authors would like to thank the reviewers for their performance computing.He is a member of careful reading and comments.This work is partially the IEEE and the IEEE Computer Society. supported by the National Natural Science Foundation of China under Grant Nos.61073028 and 61021062;the National Basic Research Program of China (973)under90 percent confidence interval for the total throughput. Note that in both the dense AP situation and sparse AP situation, OPT-E(offline) achieves the largest overall throughput, while CUB achieves the smallest throughput. Due to some nonpredictable issues, OPT-E(online) achieves a little smaller value for the overall throughput than OPT￾E(offline). All solutions in the sparse AP situation achieves a fairly smaller overall throughput compared to the dense AP situation, as fewer APs are available for association to provide sufficient throughput for users. We observed that in both situations the optimized solutions outperform the two heuristic solutions. In the dense AP situation OPT￾E(online), respectively, achieves 72.9 and 122.9 percent more throughput than SSF and CUB, while in the sparse AP situation OPT-E(online), respectively, achieves 30.6 and 73.7 percent more throughput than SSF and CUB. Since users have more candidate APs to associate with in the dense AP situation, there exist more opportunities for an optimized solution to achieve more performance gains. In order to show the performance comparison in terms of fairness, Fig. 4b illustrates per-user throughput comparison in the dense AP situation. The X-axis is the user index and the Y -axis is users’ throughput in kbps. The users are sorted by their throughput in increasing order. The throughput of the user with the same x index actually indicates the average throughput of the xth lowest throughput user (users allocated the xth lowest bandwidth). In the dense AP situation, we observe that the optimized solutions OPT￾E(online), OPT-PF(offline), OPT-PF(online) and OPT-MM all outperform the two heuristic solutions SSF and CUB. For instance, the median indexed user’s bandwidth value of OPT-E(online) is, respectively, 64 percent higher than SSF and 181 percent higher thanCUB.OPT-PF(offline), OPT-PF(online) and OPT-MM have better performance in fairness than OPT￾E(online), since the users with lower indices have higher throughput in OPT-PF(offline), OPT-PF(online) and OPT-MM compared to OPT-E(online). Among the three solutions, OPT￾MM achieves the best performance in fairness, as the users with lower indices are higher than all the other solutions, inferring that more fairness is achieved among the users. The performance gains of the above optimized solutions are between 200 and 400 kbps in throughput for each user. 6 CONCLUSION In this paper, we conduct a theoretical study on association control over the Drive-thru Internet scenario. We, respec￾tively, consider efficiency and fairness as the optimization metrics. Due to issues concerning both technology and privacy, the data needed to compute the optimal solutions are currently not easy to gather. Hence, our present research work intends to be a theoretical effort to determine the upper bounds to what can be achieved in reality. ACKNOWLEDGMENTS The authors would like to thank the reviewers for their careful reading and comments. This work is partially supported by the National Natural Science Foundation of China under Grant Nos. 61073028 and 61021062; the National Basic Research Program of China (973) under Grant No. 2009CB320705; the Technology Support Program of Jiangsu Province under Grant No. BE2010179; the US National Science Foundation (NSF) under Grant Nos. CNS- 0721443 and CNS-0831904, CAREER Award CNS-0747108, CNS-0434533, CNS-0531410, and CNS-0626240. REFERENCES [1] J. Ott and D. Kutscher, “Drive-thru Internet: IEEE 802.11b for ‘Automobile’ Users,” Proc. IEEE INFOCOM, 2004. [2] J. Camp and E. Knightly, “Modulation Rate Adaptation in Urban and Vehicular Environments: Cross-Layer Implementation and Experimental Evaluation,” Proc. ACM MOBICOM, 2008. [3] L. Tassiulas and S. Sarkar, “Maxmin Fair Scheduling in Wireless Ad Hoc Networks,” IEEE J. Selected Areas in Comm., vol. 23, no. 1, pp. 163-173, Jan. 2005. [4] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and Load Balancing in Wireless LANs Using Association Control,” IEEE/ACM Trans. Networking, vol. 15, no. 3, pp. 560-573, June 2007. [5] L. Li, M. Pal, and Y.R. Yang, “Proportional Fairness in Multi-Rate Wireless LANs,” Proc. IEEE INFOCOM, 2008. [6] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A Measurement Study of Vehicular Internet Access Using In Situ Wi-Fi Networks,” Proc. ACM MOBICOM, 2006. [7] J. Eriksson, H. Balakrishnan, and S. Madden, “Cabernet: Vehicular Content Delivery Using Wi-Fi,” Proc. ACM MOBICOM, 2008. [8] A. Giannoulis, M. Fiore, and E.W. Knightly, “Supporting Vehicular Mobility in Urban Multi-Hop Wireless Networks,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2008. [9] R. Mahajan, J. Zahorjan, and B. Zill, “Understanding WiFi-Based Connectivity,” Proc. ACM Internet Measurement Conf. (IMC), 2007. [10] D. Hadaller, S. Keshav, T. Brecht, and S. Agarwal, “Vehicular Opportunistic Communication under the Microscope,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2007. [11] V. Navda, A.P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S.R. Das, “Mobisteer: Using Steerable Beam Directional Antenna for Vehicular Network Access,” Proc. ACM MOBISYS, 2007. [12] M. Kim, Z. Liu, S. Parthasarathy, D. Pendarakis, and H. Yang, “Association Control in Mobile Wireless Networks,” Proc. IEEE INFOCOM, 2008. [13] P. Deshpande, A. Kashyap, C. Sung, and S. Das, “Predictive Methods for Improved Vehicular Wifi Access,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2009. [14] H. Wu, K. Tan, Y. Zhang, and Q. Zhang, “Proactive Scan: Fast Handoff with Smart Triggers for 802.11 Wireless Lan,” Proc. INFOCOM, 2007. [15] T. Nandagopal, T.-E. Kim, X. Gao, and V. Bharghavan, “Achieving Mac Layer Fairness in Wireless Packet Networks,” Proc. ACM MOBICOM, pp. 87-98, 2000. [16] R. Murty, J. Padhye, A. Wolman, and B. Zill, “Designing High Performance Enterprise Wi-Fi Networks,” Proc. ACM Networked Systems Design and Implementation (NSDI), 2008. [17] D.B. Shmoys and E. Tardos, “An Approximation Algorithm for the Generalized Assignment Problem,” Math. Programming, vol. 62, no. 3, pp. 461-474, 1993. [18] “Sumo,” http://sourceforge.net/apps/mediawiki/sumo/, 2011. [19] “Tiger,” www.census.gov/geo/www/tiger/, 2011. Lei Xie received the BS and PhD degrees from Nanjing University in 2004 and 2010, respec￾tively, all in computer science. He is an assistant professor in the Department of Computer Science and Technology, Nanjing University, China. His research interests in￾clude sensor networks, RFID systems, vehicu￾lar networks, cognitive radios, and high performance computing. He is a member of the IEEE and the IEEE Computer Society. 1330 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011