Open Access Open Access  Restricted Access Subscription or Fee Access

A Distributed CSMA Algorithm for Maximizing Throughput in Wireless Networks

K.K.S. Harika, Dr.P. Harini, M. Kiran Kumar, K. Kondaiah

Abstract


In multihop wireless networks, designing distributed scheduling algorithms to achieve the maximal throughput is a challenging problem because of the complex interference constraints among different links. Traditional maximal-weight scheduling (MWS), although throughput-optimal, is difficult to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 does not guarantee the maximal throughput. In this paper, we introduce an adaptive carrier sense multiple access (CSMA) scheduling algorithm that can achieve the maximal throughput distributively. Some of the major advantages of the algorithm are that it applies to a very general interference model and that it is simple, distributed, and asynchronous. Furthermore, the algorithm is combined with congestion control to achieve the optimal utility and fairness of competing flows. Simulations verify the effectiveness of the algorithm. Also, the adaptive CSMA scheduling is a modular MAC-layer algorithm that can be combined with various protocols in the transport layer and network layer. Finally, the paper explores some implementation issues in the setting of 802.11 networks.

Keywords


Traditional maximal-weight,scheduling,throughput-optimal,distributed adaptive carrier sense multiple access (CSMA)

Full Text:

PDF

References


X. Lin, N. B. Shroff, and R. Srikant, “A tutorial on cross-layer optimization in wireless networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1452–1463, Aug. 2006.

L. Jiang and J. Walrand, “A distributed CSMA algorithm for throughput and utility maximization in wireless networks,” in Proc. 46th Annu. Allerton Conf. Commun., Control, Comput., Sep. 23–26,

, pp. 1511–1519.

A. Eryilmaz, A. Ozdaglar, and E. Modiano, “Polynomial complexity algorithms for full utilization of multi-hop wireless networks,” in Proc.

IEEE INFOCOM, Anchorage, AK, May 2007, pp. 499–507.

E. Modiano, D. Shah, and G. Zussman, “Maximizing throughput in wireless networks via gossiping,” ACM SIGMETRICS Perform. Eval.

Rev., vol. 34, no. 1, pp. 27–38, Jun. 2006.

S. Sanghavi, L. Bui, and R. Srikant, “Distributed link scheduling with constant overhead,” in Proc. ACM SIGMETRICS, Jun. 2007, pp. 313–324.

J. W. Lee, M. Chiang, and R. A. Calderbank, “Utility-optimal random-access control,” IEEE Trans. Wireless Commun., vol. 6, no. 7, pp. 2741–2751, Jul. 2007.

P. Gupta and A. L. Stolyar, “Optimal throughput allocation in general random access networks,” in Proc. Conf. Inf. Sci. Syst., Princeton, NJ, Mar. 2006, pp. 1254–1259.

X. Wu and R. Srikant, “Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks,” in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006, pp. 1–12.

P. Chaporkar, K. Kar, and S. Sarkar, “Throughput guarantees in maximal scheduling in wireless networks,” in Proc. 43rd Annu. Allerton Conf. Commun., Control, Comput., Sep. 2005, pp. 1557–1567.

A. Dimakis and J. Walrand, “Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid

limits,” Adv. Appl. Probab., vol. 38, no. 2, pp. 505–521, 2006.

C. Joo, X. Lin, and N. Shroff, “Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks,” in Proc. IEEE INFOCOM, Phoenix, AZ, Apr. 2008, pp. 1103–1111.

G. Zussman, A. Brzezinski, and E. Modiano, “Multihop local pooling for distributed throughput maximization in wireless networks,” in Proc.IEEE INFOCOM, Phoenix, AZ, Apr. 2008, pp. 1139–1147.

M. Leconte, J. Ni, and R. Srikant, “Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks,” in

Proc. ACM MobiHoc, May 2009, pp. 165–174.

X. Lin and N. Shroff, “The impact of imperfect scheduling on crosslayer rate control in multihop wireless networks,” in Proc. IEEE INFOCOM, Miami, Florida, Mar. 2005, vol. 3, pp. 1804–1814.

P. Marbach, A. Eryilmaz, and A. Ozdaglar, “Achievable rate region of CSMA schedulers in wireless networks with primary interference constraints,” in Proc. IEEE Conf. Decision Control, 2007, pp. 1156–1161.

A. Proutiere, Y. Yi, and M. Chiang, “Throughput of random access without message passing,” in Proc. Conf. Inf. Sci. Syst., Princeton, NJ, Mar. 2008, pp. 509–514.

S. Rajagopalan and D. Shah, “Distributed algorithm and reversible network,” in Proc. Conf. Inf. Sci. Syst., Princeton, NJ, Mar. 2008, pp. 498–502.

Y. Xi and E. M. Yeh, “Throughput optimal distributed control of stochastic wireless networks,” in Proc. WiOpt, 2006, pp. 1–10.

M. J. Neely, E.Modiano, and C. P. Li, “Fairness and optimal stochastic control for heterogeneous networks,” IEEE/ACM Trans. Netw., vol. 16, no. 2, pp. 396–409, Apr. 2008.

B. Hajek, “Cooling schedules for optimal annealing,” Math. Oper. Res., vol. 13, no. 2, pp. 311–329, 1988. Authorized licensed use limited to: INDIAN INSTITUTE OF TECHNOLOGY MADRAS. Downloaded on July 09,2010 at 09:45:53 UTC from IEEE Xplore. Restrictions apply. 972 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 18, NO. 3, JUNE 2010

J. Liu, Y. Yi, A. Proutiere, M. Chiang, and H. V. Poor, “Convergence and tradeoff of utility-optimal CSMA,” [Online]. Available: http://arxiv.org/abs/0902.1996

L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992.

N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” IEEE Trans. Commun., vol. 47, no. 8, pp. 1260–1267, Aug. 1999.

F. P. Kelly, Reversibility and Stochastic Networks. New York:Wiley, 1979.

R. R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin, “Throughput analysis in multihop CSMA packet radio networks,” IEEE Trans. Commun., vol. COMM-35, no. 3, pp. 267–274, Mar. 1987.

X. Wang and K. Kar, “Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks,” in Proc. IEEE INFOCOM,Miami, FL, Mar. 2005, vol. 1, pp. 23–34.

S. C. Liew, C. Kai, J. Leung, and B.Wong, “Back-of-the-envelope computation of throughput distributions in CSMA wireless networks,” in Proc. IEEE ICC, 2009, pp. 1–6.

M. Durvy, O. Dousse, and P. Thiran, “Border effects, fairness, and phase transition in large wireless networks,” in Proc. IEEE INFOCOM, Phoenix, AZ, Apr. 2008, pp. 601–609.

L. Jiang and S. C. Liew, “Improving throughput and fairness by reducing exposed and hidden nodes in 802.11 networks,” IEEE Trans Mobile Comput., vol. 7, no. 1, pp. 34–49, Jan. 2008.

L. Jiang and J. Walrand, “Approaching throughput-optimality in a distributed CSMA algorithm: Collisions and stability,” in Proc. ACM Mobihoc S3 Workshop, May 2009, pp. 5–8.

L. Jiang and J. Walrand, “Approaching throughput-optimality in a distributed CSMA algorithm with contention resolution,” UC Berkeley, Tech. Rep., 2009 [Online]. Available: http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-37.html

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2004.

M. J. Wainwright and M. I. Jordan, “Graphical models, exponential families, and variational inference,” Found. Trends Mach. Learn., vol.1, no. 1-2, pp. 1–305, 2008.

P. Whittle, Systems in Stochastic Equilibrium. New York: Wiley, 1986.

J. Ni and R. Srikant, “Distributed CSMA/CA algorithms for achieving maximum throughput in wireless networks,” in Proc. Inf. Theory Appl.Workshop, Feb. 2009, p. 250.

G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” IEEE J. Sel. Areas Commun., vol. 18, no. 3, pp.535–547, Mar. 2000.

M. J. Neely and R. Urgaonkar, “Cross layer adaptive control for wireless mesh networks,” Ad Hoc Netw., vol. 5, no. 6, pp. 719–743, Aug. 2007.

L. Jiang and J. Walrand, “Convergence and stability of a distributed CSMA algorithm for maximal network throughput,” UC Berkeley, Tech. Rep., 2009 [Online]. Available:

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-43.html

A.Warrier, S. Ha, P. Wason, and I. Rhee, “DiffQ: Differential backlog congestion control for wireless multi-hop networks,” Dept. Computer Science, North Carolina State Univ., Tech. Rep., 2008.

L. Jiang and J. Walrand, “A distributed CSMA algorithm for throughput and utility maximization in wireless networks,” UC Berkeley, Tech. Rep., 2009 [Online]. Available: http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-124.html

L. Jiang and J. Walrand, “A distributed algorithm for maximal throughput and optimal fairness in wireless networks with a general interference model,” UC Berkeley, EECS Tech. Available:http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS- 2008-38.html

L. Bui, R. Srikant, and A. Stolyar, “Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing,” in Proc. IEEE INFOCOM, Rio de Janeiro, Brazil, Apr. 2009, pp. 2936–2940.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.