Distributed opportunistic scheduling for ad-hoc communications: an optimal stopping approach

ABSTRACT

We consider distributed opportunistic scheduling (DOS) in wireless ad-hoc networks, where many links contend for the same channel using random access. In such networks, distributed opportunistic scheduling involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence higher transmission rates. The desired tradeoff boils down to judiciously choosing the optimal stopping strategy for channel probing and the rate threshold. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal strategy turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed point equation. We further devise an iterative algorithm for computing the threshold. Next, we explore DOS from a user-centric perspective, where each links seeks to maximize its own throughput. We treat the problem of rate threshold selections for different links as a non-cooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. We then develop an online stochastic iterative algorithm using local observations only, and establish its convergence. Finally, we observe that there is an efficiency loss in terms of the throughput at the Nash equilibrium, and introduce apricing-based mechanism to mitigate the loss.

REFERENCES

• 1: S. Adireddy and L. Tong. Exploiting decentralized channel state information for random access. IEEE Trans. Info. Theory, 51(2):537--561, Feb. 2005.
• 2: R. Agrawal, A. Bedekar, R. J. La, R. Pazhyannur, and V. Subramanian. Class and channel condition based scheduler for EDGE/GPRS. In Proceeding of SPIE, pages 59--68, 2001.
• 3: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 4: E. Altman, V. S. Borkar, and A. A. Kherani. Optimal random access in networks with two-way traffic. In Proc. WiOpt'05, 2005.
• 5: M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar. Providing quality of service over a shared wireless link. IEEE Communications Magazine, 39:150--154, 2001.
• 6: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 7: Vivek S. Borkar, Asynchronous Stochastic Approximations, SIAM Journal on Control and Optimization, v.36 n.3, p.840-851, May 1998 [doi>10.1137/S0363012995282784]
• 8: V. S. Borkar and A. A. Kherani. Random access in wireless ad hoc networks as a distributed game. In Proc. WiOpt'04, 2004.
• 9: S. Borst. User-level performance of channel-aware scheduling algotirthms in wireless data networks. In Proc. IEEE INFOCOM'03, 2003.
• 10: Min Cao , Vivek Raghunathan , P. Kumar, Cross-Layer Exploitation of MAC Layer Diversity in Wireless Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.332-341, November 12-15, 2006 [doi>10.1109/ICNP.2006.320183]
• 11: Y. S. Chow, H. Robbins, and D. Siegmund. Great Expectations: Theory of Optimal Stopping. Houghton Mifflin, 1971.
• 12: T. Ferguson. Optimal Stopping and Applications. http://www.math.ucla.edu/~tom/Stopping/Contents.html, 2006.
• 13: S. Guha, K. Munagala, and S. Sarkar. Jointly optimal transmission and probing strategies for multichannel wireless systems. In Proceedings of CISS'06, Princeton, NJ, 2006.
• 14: Gavin Holland , Nitin Vaidya , Paramvir Bahl, A rate-adaptive MAC protocol for multi-Hop wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.236-251, July 2001, Rome, Italy [doi>10.1145/381677.381700]
• 15: Zhengrong Ji , Yi Yang , Junlan Zhou , Mineo Takai , Rajive Bagrodia, Exploiting medium access diversity in rate adaptive wireless LANs, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023754]
• 16: R. Knopp and P. Humlet. Information capacity and power control in single cell multiuser communications. In Proc. IEEE ICC 95, June 1995.
• 17: Xin Liu , Edwin K. P. Chong , Ness B. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.451-474, 15 March 2003 [doi>10.1016/S1389-1286(02)00401-2]
• 18: M. J. Osborne and A. Rubinstein. A Course In Game Theory. The MIT Press, 1994.
• 19: Daji Qiao , Sunghyun Choi , Kang G. Shin, Goodput Analysis and Link Adaptation for IEEE 802.11a Wireless LANs, IEEE Transactions on Mobile Computing, v.1 n.4, p.278-292, October 2002 [doi>10.1109/TMC.2002.1175541]
• 20: X. Qin and R. Berry. Exploiting multiuser dieversity for medium access control in wireless networks. In Proceedings of IEEE INFOCOM'03, 2003.
• 21: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 22: Ashutosh Sabharwal , Ahmad Khoshnevis , Edward Knightly, Opportunistic spectral usage: bounds and a multi-band CSMA/CA protocol, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.533-545, June 2007 [doi>10.1109/TNET.2007.893230]
• 23: B. Sadeghi , V. Kanodia , A. Sabharwal , E. Knightly, Opportunistic media access for multirate ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570650]
• 24: C. Saraydar, N. Mandayam, and D. Goodman. Efficient power control via pricing in wireless data networks. IEEE Trans. on Comm., 50(2):291--303, Feb. 2002.
• 25: S. Shakkottai, R. Srikant, and A. L. Stolyar. Pathwise optimality and state space collapse for the exponential rule. In Proceedings of IEEE Symposium on Information Theory, July 2002.
• 26: A. N. Shiryayev. Optimal Stopping Rules. Springer-Verlag, 1978.
• 27: P. Viswanath, D. N. Tse, and R. Laroia. Opportunistic beamforming using dumb antennas. IEEE Trans. Info. Theory, 48(6):1277--1294, June 2002.
• 28: D. Zheng and J. Zhang. Joint optimal channel probing and transmission in collocated wireless networks. In Proc. IEEE INFOCOM'07 (symposium), May 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance, Theory

Keywords:
ad-hoc networks, distributed opportunistic scheduling, game theory, optimal stopping