the median user's bandwidth value of the online algorithm We observe that it is much smaller than the worst case ratio solution is 69%higher than the SSF solution and 300%higher +y,which demonstrates for conventional cases we achieve than the CUB solution.The offline optimal solution has better tight bound for the expected approximation ratio. performance than the online solution.since the median user's bandwidth value of the former is 12.9%higher than the latter. VIII.CONCLUSION In this paper,we conduct a theoretical research on associa- tion control over the Drive-thru Internet scenario.We consider lambda-0.2 一ambh both efficiency and fairness metrics,and present corresponding offline and online solutions to achieve overall optimization objectives.We further propose an approximation algorithm for group breaking in order to reduce computation complexity. ACKNOWLEDGMENTS 0.5 1.5 0.5 Value of gamma 15 Value af gamma This project was supported in part by US National Sci- (a)Compute complexity (b)Approximate ratio ence Foundation grants CNS-0721443,CNS-0831904,CA- REER Award CNS-0747108.CNS-0434533.CNS-0531410. +-lambds-1 and CNS-0626240,the China 973 project(2009CB320705, 2006CB303000),the China NSF grant(90718031,60721002 D.E 60573106.60573132,60873026). REFERENCES 0 (1]V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden Vae gamma 15 "A measurement study of vehicular intemet access using in situ Wi- Fi networks,"in ACM Proc.of MOBICOM.2006. (c)Compute complexity (d)Approximate ratio [2]J.Ott and D.Kutscher,"Drive-thru internet:IEEE 802.11b for 'auto. mobile'users."in IEEE Proc.of INFOCOM.2004. [3]A.Giannoulis,M.Fiore,and E.W.Knightly."Supporting vehicular Fig.5.Performance evaluation for group breaking approximate algorithm mobility in urban multi-hop wireless networks."in ACM Proc.of MobiSys.2008. [4]L.Tassiulas and S.Sarkar,"Maxmin fair scheduling in wireless ad hoc B.Group Breaking Mechanism networks,"IEEE Journal on Selected Areas in Communications (JSAC). vol.23,no.1,Pp.163-173,2005 In Fig.5 we evaluate the performance for the group breaking [5]Y.Bejerano,S.-J.Han,and L.Li,"Fairess and load balancing in wireless LANs using association control."IEEE/ACM Trans.Netw. approximate algorithm in terms of computation complexity (T0W,vol.15,no.3,Pp.560-573,2007. and approximate ratio.Here we normalize the computation [6]L.Li,M.Pal,and Y.R.Yang,"Proportional fairness in multi-rate complexity as a ratio between the complexity after group wireless LANs,"in IEEE Proc.of INFOCOM,2008. [7 breaking and the original complexity.We respectively con- J.Eriksson,H.Balakrishnan,and S.Madden,"Cabernet:vehicular content delivery using Wi-Fi,"in ACM Proc.of MOBICOM,2008. sider two conventional cases with different A for the Poisson [8]J.Ott and D.Kutscher,"A disconnection-tolerant transport for drive-thru Process.For the sparse case with =0.2,the average internet environments,"in IEEE Proc.of INFOCOM,2005 [9]R.Mahajan,J.Zahorjan,and B.Zill,"Understanding WiFi-based distance between adjacent users is large,thus we can break connectivity from moving vehicles."in Proc.of IMC.2007. the large group of users into many sub-groups.As Fig.5 [10]D.Hadaller,S.Keshav,T.Brecht,and S.Agarwal,"Vehicular op- (a)shows,when y varies from 0 to 0.6,the computation portunistic communication under the microscope,"in ACM Proc.of complexity reduces dramatically from I to 0.1,and when MobiSys,2007. [11]M.Kim,Z.Liu,S.Parthasarathy,D.Pendarakis,and H.Yang,"Associa- further increases from 0.6 to 2,as many of the weak links has tion control in mobile wireless networks."in IEEE Proc.of INFOCOM. already been eliminated,the computation complexity reduces 2008. gently.As Fig.5(b)shows,when y varies from 0 to 1.4,the [12]V.Navda,A.P.Subramanian,K.Dhanasekaran,A.Timm-Giel,and S.R Das,"Mobisteer:using steerable beam directional antenna for vehicular average approximate ratio keeps close to 1 as those weak link network access,"in IEEE Proc.of MobiSys.2007 deleted among the sparse group of users will not impact on [13]L.B.Jiang and S.C.Liew,"Proportional fairness in wireless LANs and the final optimal solution,and when y further increases from ad hoc networks,"in IEEE Proc.of WCNC,2005. [14]T.Nandagopal,T.-E.Kim,X.Gao,and V.Bharghavan,"Achieving mac 1.4 to 2,the approximate ratio grows slightly from 1 to 1.25. layer fairness in wireless packet networks."in ACM Proc.of MobiCom. For the dense case with A=1,the average distance between 2000,pp.87-98. [15]R.Murty,J.Padhye,A.Wolman,and B.Zill,"Designing high perfor- adjacent users is rather small so that eliminating some weak mance enterprise Wi-Fi networks,"in ACM Proc.of NSDI,2008. links will not be enough to break the large group of users [16]D.B.Shmoys and E.Tardos."An approximation algorithm for the into many sub-groups.As Fig.5 (c)shows,the computation generalized assignment problem,"Math.Program.vol.62,no.3.pp. 461-474,1993. complexity first reduces gently when y increases from 0 to 6. [17]W.H.Freeman,"Linear programming."1983. then reduces dramatically when y increases from 6 to 10 due to weak links,and finally the computation complexity reduces slightly.As Fig.5(d)shows,when y varies from 0 to 20,the averaged approximate ratio grows near linearly from I to 1.32. 333 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.the median user’s bandwidth value of the online algorithm solution is 69% higher than the SSF solution and 300% higher than the CUB solution. The offline optimal solution has better performance than the online solution, since the median user’s bandwidth value of the former is 12.9% higher than the latter. 0 0.5 1 1.5 2 0 0.2 0.4 0.6 0.8 1 Value of gamma Complexity comparison ratio lambda=0.2 0 5 10 15 20 0 0.2 0.4 0.6 0.8 1 Value of gamma Complexity comparison ratio lambda=1 0 0.5 1 1.5 2 0.5 1 1.5 Value of gamma Approximation ratio lambda=0.2 0 5 10 15 20 0.5 1 1.5 2 Value of gamma Approximation ratio lambda=1 (a) Compute complexity (c) Compute complexity (b) Approximate ratio (d) Approximate ratio Fig. 5. Performance evaluation for group breaking approximate algorithm B. Group Breaking Mechanism In Fig. 5 we evaluate the performance for the group breaking approximate algorithm in terms of computation complexity and approximate ratio. Here we normalize the computation complexity as a ratio between the complexity after group breaking and the original complexity. We respectively con￾sider two conventional cases with different λ for the Poisson Process. For the sparse case with λ = 0.2, the average distance between adjacent users is large, thus we can break the large group of users into many sub-groups. As Fig. 5 (a) shows, when γ varies from 0 to 0.6, the computation complexity reduces dramatically from 1 to 0.1, and when γ further increases from 0.6 to 2, as many of the weak links has already been eliminated, the computation complexity reduces gently. As Fig. 5 (b) shows, when γ varies from 0 to 1.4, the average approximate ratio keeps close to 1 as those weak link deleted among the sparse group of users will not impact on the final optimal solution, and when γ further increases from 1.4 to 2, the approximate ratio grows slightly from 1 to 1.25. For the dense case with λ = 1, the average distance between adjacent users is rather small so that eliminating some weak links will not be enough to break the large group of users into many sub-groups. As Fig. 5 (c) shows, the computation complexity first reduces gently when γ increases from 0 to 6, then reduces dramatically when γ increases from 6 to 10 due to weak links, and finally the computation complexity reduces slightly. As Fig. 5 (d) shows, when γ varies from 0 to 20, the averaged approximate ratio grows near linearly from 1 to 1.32. We observe that it is much smaller than the worst case ratio θ + γ, which demonstrates for conventional cases we achieve tight bound for the expected approximation ratio. VIII. CONCLUSION In this paper, we conduct a theoretical research on associa￾tion control over the Drive-thru Internet scenario. We consider both efficiency and fairness metrics, and present corresponding offline and online solutions to achieve overall optimization objectives. We further propose an approximation algorithm for group breaking in order to reduce computation complexity. ACKNOWLEDGMENTS This project was supported in part by US National Sci￾ence Foundation grants CNS-0721443, CNS-0831904, CA￾REER Award CNS-0747108, CNS-0434533, CNS-0531410, and CNS-0626240, the China 973 project (2009CB320705, 2006CB303000), the China NSF grant (90718031, 60721002, 60573106, 60573132, 60873026). REFERENCES [1] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A measurement study of vehicular internet access using in situ Wi￾Fi networks,” in ACM Proc. of MOBICOM, 2006. [2] J. Ott and D. Kutscher, “Drive-thru internet: IEEE 802.11b for ‘auto￾mobile’ users,” in IEEE Proc. of INFOCOM, 2004. [3] A. Giannoulis, M. Fiore, and E. W. Knightly, “Supporting vehicular mobility in urban multi-hop wireless networks,” in ACM Proc. of MobiSys, 2008. [4] L. Tassiulas and S. Sarkar, “Maxmin fair scheduling in wireless ad hoc networks,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 23, no. 1, pp. 163–173, 2005. [5] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and load balancing in wireless LANs using association control,” IEEE/ACM Trans. Netw. (TON), vol. 15, no. 3, pp. 560–573, 2007. [6] L. Li, M. Pal, and Y. R. Yang, “Proportional fairness in multi-rate wireless LANs,” in IEEE Proc. of INFOCOM, 2008. [7] J. Eriksson, H. Balakrishnan, and S. Madden, “Cabernet: vehicular content delivery using Wi-Fi,” in ACM Proc. of MOBICOM, 2008. [8] J. Ott and D. Kutscher, “A disconnection-tolerant transport for drive-thru internet environments,” in IEEE Proc. of INFOCOM, 2005. [9] R. Mahajan, J. Zahorjan, and B. Zill, “Understanding WiFi-based connectivity from moving vehicles,” in Proc. of IMC, 2007. [10] D. Hadaller, S. Keshav, T. Brecht, and S. Agarwal, “Vehicular op￾portunistic communication under the microscope,” in ACM Proc. of MobiSys, 2007. [11] M. Kim, Z. Liu, S. Parthasarathy, D. Pendarakis, and H. Yang, “Associa￾tion control in mobile wireless networks,” in IEEE Proc. of INFOCOM, 2008. [12] V. Navda, A. P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S. R. Das, “Mobisteer: using steerable beam directional antenna for vehicular network access,” in IEEE Proc. of MobiSys, 2007. [13] L. B. Jiang and S. C. Liew, “Proportional fairness in wireless LANs and ad hoc networks,” in IEEE Proc. of WCNC, 2005. [14] T. Nandagopal, T.-E. Kim, X. Gao, and V. Bharghavan, “Achieving mac layer fairness in wireless packet networks,” in ACM Proc. of MobiCom, 2000, pp. 87–98. [15] R. Murty, J. Padhye, A. Wolman, and B. Zill, “Designing high perfor￾mance enterprise Wi-Fi networks,” in ACM Proc. of NSDI, 2008. [16] D. B. Shmoys and E. Tardos, “An approximation algorithm for the generalized assignment problem,” Math. Program, vol. 62, no. 3, pp. 461–474, 1993. [17] W. H. Freeman, “Linear programming,” 1983. 333 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply