臺灣博碩士論文加值系統

傳統對於隨機接取系統的分析與設計並不考慮連結拓譜，隱然假設所有的使用者可以彼此感測。而相應的終端機隱匿問題只能用些工程技巧彌補，但卻未曾以網路的角度徹底了解。這篇論文使用了隨機圖學的概念於不完全連接的感測拓譜，研究了阿羅哈 (ALOHA) 、無限感知網路 (cognitive radio networks) 與載波偵聽多路存取 (CSMA) 系統。為了避免穩態分析造成的錯誤結論，我們用動態分析的方法將系統描述成馬可夫鏈，利用佛斯特-李雅普諾夫條件 (Foster-Lyapunov criteria) 研究系統的穩定性。我們提出了清晰簡潔的隨機接取系統穩定性條件，並用模擬證實它們的正確性。

Traditional analysis and design on random access systems do not take sensing topology into consideration, which implicitly assumes that one user can sense all other users. The corresponding hidden terminal problem is only mitigated by some engineering techniques but never completely understood from a network view. This work applies random graph on imperfect sensing topology to study three random access systems: ALOHA, cognitive radio networks and CSMA. To avoiding misleading conclusion from equilibrium analysis, we take a dynamic approach by modeling the systems as Markov chains, and investigate the system stabiliby from the recurrence of Markov chains with the aid of Foster-Lyapunov criteria. Elegant stability conditions are derived in this work, together with the verification from simulation result.

1 Introduction p.1
2 Preliminaries p.6
3 System Model p.11
4 Stability Analysis 17
5 Stabilization Algorithm for CRNs 26
6 Simulation 30
7 Conclusion and Future Work 39
References 40

[1] D. Bertsekas and R. Gallager, Data Networks. 2nd ed., 1992.
[2] L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part I - Carrier sense multiple-access modes and their throughput-delay characteristics,” Communications, IEEE Transactions on, vol. 23, pp. 1400–1416, Dec. 1975.
[3] C. Cormio and K. R. Chowdhury, “A survey on MAC protocols for cognitive radio networks,” Ad Hoc Networks, vol. 7, no. 7, pp. 1315 – 1329, 2009.
[4] F. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part II - The hidden terminal problem in carrier sense multiple-access and the busy-tone solution,” Communications, IEEE Transactions on, vol. 23, pp. 1417–1433, Dec. 1975.
[5] K.-C. Chen, “Medium access control of wireless LANs for mobile computing,” IEEE Network, vol. 8, no. 5, pp. 50–63, 1994.
[6] J. Dai and Y. Yamao, “CSMA/CA performance under fading environment with twodimensional distribution of hidden terminal,” in Proc. IEEE VTC-Fall, (San Francisco, SA), pp. 1–5, Sep. 2011.
[7] M. Garetto, J. Shi, and E. W. Knightly, “Modeling media access in embedded two-flow topologies of multi-hop wireless networks,” in Proc. ACM MobiCom, (Cologne, Germany).
[8] H. Q. Nguyen, F. Baccelli, and D. Kofman, “A stochastic geometry analysis of dense IEEE 802.11 networks,” in Proc. IEEE INFOCOM, (Anchorage, Alaska, USA), pp. 1199–1207, May 2007.
[9] G. Alfano, M. Garetto, and E. Leonardi, “New insights into the stochastic geometry analysis of dense CSMA networks,” in Proc. IEEE INFOCOM, (Shanghai, China), pp. 2642–2650, Apr. 2011.
[10] G. Alfano, M. Garetto, and E. Leonardi, “New directions into the stochastic geometry analysis of dense CSMA networks,” Mobile Computing, IEEE Transactions on, vol. 13, pp. 324–336, Feb. 2014.
[11] K.-C. Huang and K.-C. Chen, “Interference analysis of nonpersistent CSMA with hidden terminals in multicell wireless data networks,” in Proc. IEEE PIMRC, vol. 2, (Toronto, ON., Canada), pp. 907–911, IEEE, 1995.
[12] P. Karn, “MACA: A new channel access method for packet radio,” in Proc. ARRL 9th Computer Networking Conf., (London, Ontario, Canada).
[13] B. P. Crow, I. Widjaja, J. G. Kim, and P. T. Sakai, “IEEE 802.11 wireless local area networks,” Communications Magazine, IEEE, vol. 35, no. 9, pp. 116–126, 1997.
[14] H. S. Chhaya and S. Gupta, “Performance modeling of asynchronous data transfer methods of IEEE 802.11 MAC protocol,” Wireless Networks, vol. 3, pp. 217–234, Aug. 1997.
[15] T.-S. Ho and K.-C. Chen, “Performance analysis of IEEE 802.11 CSMA/CA medium access control protocol,” in Proc. IEEE PIMRC, vol. 2, (Taipei, Taiwan), pp. 407–411, Oct. 1996.
[16] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” Selected Areas in Communications, IEEE Journal on, vol. 18, no. 3, pp. 535–547, 2000.
[17] T.-C. Hou, L.-F. Tsao, and H.-C. Liu, “Analyzing the throughput of IEEE 802.11 DCF scheme with hidden nodes,” in Proc. IEEE VTC-Fall, vol. 5, (Orlando, Florida, USA), pp. 2870–2874, Oct. 2003.
[18] O. Ekici and A. Yongacoglu, “IEEE 802.11a throughput performance with hidden nodes,” Communications Letters, IEEE, vol. 12, no. 6, pp. 465–467, 2008.
[19] F.-Y. Hung and I. Marsic, “Performance analysis of the IEEE 802.11 DCF in the presence of the hidden stations,” Computer Networks, vol. 54, no. 15, pp. 2674–2687, 2010.
[20] K. Xu, M. Gerla, and S. Bae, “How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks?,” in Proc. IEEE GLOBECOM, vol. 1, (Taipei, Taiwan), pp. 72–76, Nov. 2002.
[21] I. Tinnirello, S. Choi, and Y. Kim, “Revisit of RTS/CTS exchange in high-speed IEEE 802.11 networks,” in Proc. IEEE WoWMoM, (Taormina - Giardini Naxos, Italy), pp. 240–248, June 2005.
[22] J. Peng and L. Cheng, “Revisiting carrier sense multiple access with collision avoidance (CSMA/CA),” in Proc. CISS, (Princeton, NJ, USA), pp. 1236–1241, Mar. 2006.
[23] Z. Haas and J. Deng, “Dual busy tone multiple access (DBTMA)-a multiple access control scheme for ad hoc networks,” Communications, IEEE Transactions on, vol. 50, pp. 975–985, Jun. 2002.
[24] A. A. Abdullah, L. Cai, and F. Gebali, “Enhanced busy-tone-assisted MAC protocol for wireless ad hoc networks,” in Proc. IEEE VTC-Fall, (Ottawa, Canada), pp. 1–5, Sep. 2010.
[25] P. Erd&;#337;s and A. Renyi, “On the evolution of random graphs,” Magyar Tud. Akad. Mat. Kutato Int. Kozl, vol. 5, pp. 17–61, 1960.
[26] T.-K. Chang, K.-C. Chen, and L. Zheng, “Time dynamics of random access in cognitive radio networks,” to be published in Proc. IEEE ICC, (Sydney, Australia), pp. 1–5, 2014.
[27] V. A. Mikhailov, “Geometrical analysis of the stability of Markov chains in Rn+ and its application to throughput evaluation of the adaptive random multiple access algorithm,”Problemy Peredachi Informatsii, vol. 24, no. 1, pp. 61–73, 1988.
[28] B. Hajek and T. van Loon, “Decentralized dynamic control of a multiaccess broadcast channel,” Automatic Control, IEEE Transactions on, vol. 27, pp. 559–569, Jun. 1982.
[29] R. L. Rivest, “Network control by Bayesian broadcast,” Information Theory, IEEE Transactions on, vol. 33, pp. 323–328, May 1987.
[30] D. Aldous, “Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels,” Information Theory, IEEE Transactions on, vol. 33, pp. 219–223, Mar. 1987.
[31] F. A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part IV - Stability considerations and dynamic control in carrier sense multiple access,” Communications, IEEE Transactions on, vol. 25, no. 10, pp. 1103–1119, 1977.
[32] J. Meditch and C.-T. Lea, “Stability and optimization of the CSMA and CSMA/CD channels,” Communications, IEEE Transactions on, vol. 31, pp. 763–774, Jun. 1983.
[33] M. A. Boyana and T. T. Ha, “Pseudo-Bayesian stability of CSMA and CSMA/CD local area networks,” Master’s thesis, Naval Postgraduate School, 1988.
[34] S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability. Springer-Verlag, 1993.
[35] F. G. Foster, “On the stochastic matrices associated with certain queuing processes,” The Annals of Mathematical Statistics, vol. 24, no. 3, pp. 355–360, 1953.
[36] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,”Automatic Control, IEEE Transactions on, vol. 37, no. 12, pp. 1936–1948, 1992.
[37] N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” Communications, IEEE Transactions on, vol. 47, no. 8, pp. 1260–1267, 1999.
[38] S. M. Ross, Stochastic Processes. New York: John Wieley, 1996.
[39] W. Rosenkrantz and D. Towsley, “On the instability of slotted ALOHA multiaccess algorithm,” Automatic Control, IEEE Transactions on, vol. 28, pp. 994–996, Oct. 1983.