在衛星通訊中，獲得足夠的頻寬去傳送訊息是研究中重要的問題。交換式衛星分時多重進接 (SS/TDMA) 系統提供一種重要的解決方法。對於增加多媒體服務 (Multimedia Services) 與增高使用者頻寬 (Bandwidth) 之需求，此系統提供很多優點。因此，我們打算研究相關控制方法，來有效提供此系統運作時之進接速度與資源之使用。本論文主要目的是要建構不同的資源分配策略 (Assignment Schemes) 來達到提升系統效能之目標。
在研究中，先提出一需求式的時槽分配方法 (On-Demand Timeslot Assignment Algorithm)。此方法經探討，確實能在每一碼框 (Frame) 中達到最小的傳送時間 (Minimum Transmission Time)，同時資料不發生碰撞 (Conflict)。經時槽分配後，每一碼框中常會剩下閒置之時槽 (Idle Time Slots)。對於封包 (Packet) 衛星系統，這些時槽可以去除以縮短封包延遲時間 (Packet Delay Time)。因此，我們提出可變碼框長度 (Variable Frame) 的進接控制方法應用於系統中。電腦模擬顯示在此簡單的控制機制下，能有良好的效能表現 (System Performance)。
在交換式衛星分時多重進接系統中，不管使用固定分配 (Fixed Assignment) 或使用需求分配 (On-demand Assignment) 方法，系統效能會因資料不平均的分佈在不同電波區域中 (Beam Zone)，而造成效能下降。為改善此一弱點，針對使用固定分配方法及需求分配方法，各別提出地面台有效分組在不同電波區域的方法 (Station Grouping Algorithms) 來降低資料不平均分佈在不同電波區域中的情形，藉以達到提升系統效能之目的。最後，由於封包在傳送時針對時效性之不同分為及時性封包 (Isochronous Packet) 與非及時性封包 (Non-isochronous Packet)，對此在本研究中提出一種混合固定與需求分配方法 (Combined Fixed/Demand Assignment Scheme) 來達到同時運作不同時效需求之服務。在此方法中，時效性服務使用固定分配來達到其要求，而閒置之時槽則利用非及時性封包配置方法 (Non-isochronous Traffic Configuration Algorithm) 來增加需求分配方法之效果，以提高整體資源使用率 (Throughput) 並降低非及時性封包之延遲時間。

In satellite communications, a major concern is to obtain sufficient bandwidth to carry traffic. Satellite switched time division multiple access (SS/TDMA) system has many benefits to implement the needs of the increased demand for multimedia services and end-user expectation for higher bandwidth. Therefore, the major concern is to investigate the mechanisms that can efficiently provide a high-speed access and a resource control in the SS/TDMA systems. The objective of this dissertation is to propose some resource assignment schemes to promote the system performance.
The research begins to propose an on-demand timeslot assignment algorithm. The proposed scheme provides that traffic could always be scheduled in the data field of a frame with the minimum transmission time. In practice, the minimum transmission time cannot exceed the fixed TDMA frame duration. For packet satellite systems, the spare time can be reduced to increase the system efficiency. Therefore, a medium access control protocol with a variable frame structure is proposed for the system. The proposed protocol could show a simple control mechanism and efficient performance results in the system.
In SS/TDMA systems, the system performance suffers degradation under non-uniform traffic matrices in the fixed assignment and on-demand assignment. To decrease the non-uniform traffic distribution among beams, in this dissertation, new station grouping algorithms are proposed for the fixed assignment and on-demand assignment controls, respectively. In the simulations, each proposed algorithm is shown that it is an efficient solution to improve the system performance under heterogeneous traffic matrices.
Since many of satellite systems employ ATM (Asynchronous Transfer Mode) to serve the multimedia applications, the traffic is usually classified into isochronous and non-isochronous packets. Therefore, in the SS/TDMA systems, these two kinds of packets need to be simultaneously supported by a TDMA protocol. A combined fixed/demand assignment scheme is proposed to serve the two traffic classes. The non-isochronous packets are used to increase the overall system throughput; meanwhile, the isochronous packets are kept with the same transmission quality.

Contents
摘要 i
Abstract iii
Abbreviations vii
Captions for Figures viii
Glossary of Symbols x
Chapter 1
Introduction 1
1.1 Prolog 1
1.2 Introduction to SS/TDMA Systems 4
1.3 Resource Assignment Problems 5
1.4 Organization of the Dissertation 8
Chapter 2
Minimum Transmission Time Schedule with Non-Conflict for Demand Assignment 12
2.1 Introduction 12
2.2 On-Demand Timeslot Assignment Algorithm 14
2.3 Timeslot Assignment Algorithm with an Efficient Method 20
2.4 Summary 24
Chapter 3
Assignment Protocol with Variable Frame Size 26
3.1 Introduction 26
3.2 System Model and Performance Analysis 27
3.2.1 Steady state probability 28
3.2.2 Throughput 32
3.2.3 Balking probability 33
3.2.4 Packet Delay 34
3.3 Numerical Results and Comparisons 35
3.4 Summary 37
Chapter 4
Timeslot-Sharing Algorithms for Fixed Assignment 41
4.1 Introduction 41
4.2 System Model 43
4.3 Timeslot-Sharing Algorithms 45
4.3.1 Near-Optimal Timeslot-Sharing Algorithm 45
4.3.2 Fast Timeslot-Sharing Algorithm 53
4.4 Performance Analysis and Simulation Results 57
4.5 Summary 60
Chapter 5
Adaptive Station Allocation Scheme for On–Demand Assignment 67
5.1 Introduction 67
5.2 Theorem Background 68
5.3 Adaptive Station-Grouping Algorithm 70
5.4 Numerical Results and Comparisons 76
5.5 Summary 79
Chapter 6
Combined Fixed/Demand Assignment for Various Traffic Patterns 90
6.1 Introduction 90
6.2 System Model 92
6.3 Combined Fixed/Demand Assignment Scheme 93
6.4 Simulation Results 97
6.5 Summary 98
Chapter 7
Conclusions 105
References 108
Appendix 116
Publication List of Kuo-Ting Huang 122

[1]S. H. Lim, J. H. Kim, “Real-time broadcast algorithm for mobile computing,” J. of Systems and Software, vol. 69, pp. 173-181, 2004.
[2]L. L. Dai, V. W. S. Chan, “Capacity dimensioning and routing for hybrid satellite and terrestrial systems,” IEEE J. Select. Areas Commun., vol. 22, no. 2, pp. 287-299, Feb. 2004.
[3]Y. C. Chung, S. H. Bang, M. H. Kim, “An efficient broadcast data clustering method for multipoint queries in wireless information systems,” J. of Systems and Software, vol. 64, pp. 173-181, 2002.
[4]P. Chitre, F. Yegenoglu, “Next-generation satellite networks: architectures and implementations,” IEEE Commun. Magazine, pp. 30-36, March 1999.
[5]E. K. Wesel, Wireless multimedia communications: networking video, voice, and data, Addison-Wesley, 1998.
[6]M. A. Miller, Data and network communications, Delmar, New York, 2000.
[7]M. A. Rosengrant, Introduction to telecommunications, Prentice Hall, New York, 2002.
[8]D. J. Goodman, Wireless personal communications systems, Addison-Wesley, MA., 1997.
[9]C. C. Wang, T. M. Nguyen, G. W. Goo, “Satellite payload architectures for wideband communications systems,” IEEE MILCOM ’99, pp. 865-869, 1999.
[10]S. Nanba, S. Konishi, S. Nomoto, “Optimal traffic distribution algorithm for multiple-satellite systems under power constraints,” IEEE J. Select. Areas Commun., vol. 22, no. 3, pp. 192-500, April. 2004.
[11]T. Le-Ngoc, “Switching for IP-based multimedia satellite communications,” IEEE J. Select. Areas Commun. vol. 22, no. 3, pp. 462-471, April 2004.
[12]H. Koraitim, S. Tohme, “Performance analysis of multiple access protocols for multimedia satellite networks,” IEEE J. Select. Areas Commun., vol. 18, no. 9, pp. 1751-1763, Sept. 2000.
[13]C. Chen, “A QoS-based routing algorithm in multimedia satellite networks,” VTC-Fall 2003, vol. 4, pp. 2703-2707, 2003.
[14]P. Maveddat, G. Boray, F. Homayoun, “Advanced return channel system architecture for broadband multimedia communications via satellite,” Globecom’99, pp. 1103-1108, 1999.
[15]T. Le-Ngoc, I. M. Jahangir, “Performance analysis of CFDAMA-PB protocol for packet satellite communication,” IEEE Trans. Commun., vol. 46, no. 9, pp. 1206-1214, Sept. 1998.
[16]R. Sorace, “Overview of multiple satellite communication networks,” IEEE Trans. Aerospace and Electronic Systems, vol. 35, no. 4, pp. 1362-1368, Oct. 1999.
[17]S. J. MacMullan, C. J. Karpinsky, R. E. Eaves, A. R. Dio, “Geosynchronous satellites for MUOS,” MILCOM’99, vol. 2, pp. 1119-1124, 1999.
[18]Y. Qian, R. Hu, H. Abu-Amara, P. Maveddat, “Performance evaluations on a bandwidth on demand algorithm for a high capacity multimedia satellite network,” ICC 2000, vol. 1, pp. 139-143, 2000.
[19]Y. Qian, R. Hu, H. Abu-Amara, P. Maveddat, “Effect of uplink multiple access scheme on traffic reshaping for a broadband GEO satellite network,” WCNC’99, vol. 1, pp. 192-196, Sept. 1999.
[20]Y. Qian, R. Hu, H. Abu-Amara, P. Maveddat, “Connection admission control for a high capacity multimedia satellite communication system,” GLOBECOM’99, pp. 2763-2767, 1999.
[21]E. Biglieri, G.. Caire, G.. Taricco, J. Ventura-Traveset, “Multiuser detection schemes applied to regional GEO satellite mobile systems,” SPAWC’97, vol. 3, pp. 293-296, July 1997.
[22]B. Jabbari, D. McDysan, “Performance of demand assignment TDMA and multicarrier TDMA satellite networks,” IEEE J. Select. Areas Commun., vol. 10, no. 2, pp. 478-486, Feb. 1992.
[23]S. H. Durrani, K. Y. Jo, “Efficient scheduling algorithm for demand-assigned TDMA satellite systems,” IEEE Trans. Aerospace and Electronic Systems, vol. AES-25, no. 2, pp. 259-267, March 1989
[24]M. Yabusaki, “Channel reassignment algorithm in multiple carrier hopping TDMA systems,” IEEE Trans. Commun., vol. 41, no. 2, pp. 381-390, Feb. 1993.
[25]R. Mauger, C. Rosenberg, “QoS guarantees for multimedia services on a TDMA-based satellite network,” IEEE Commun. Magazine, pp. 56-58, July 1997.
[26]J. M. Park, U. R. Savagaonkar, E. K. P. Chong, H. J. Siegel, S. D. Jones, “Efficient resource allocation for QoS channels in MF-TDMA satellite systems,” MILCOM 2000, pp. 645-649, 2000.
[27]J. Wang, J. Thomas, E. Geraniotis, “Iterative MMSE cochannel interference suppression in TDMA satellite systems,” PIMRC 2000, pp. 1060-1063, 2000.
[28]D. Kreuer, A. Schmidt, “Adaptive resource sharing strategies for TDMA satellite networks,” PIMRC’94, vol. 4, pp. 1192-1196, Sept. 1994.
[29]T. Ors, Z. Sun, B. G. Evans, “Analysis of an adaptive random/reservation MAC protocol for ATM over satellite,” VTC ’98, vol. 2, pp. 1523-1527, 1998.
[30]A. Hung, M.-J. Montpetit, G. Kesidis, P. Takats, “A framework for ATM via satellite,” GLOBECOM’96, vol. 2, pp. 1020-1025, 1996.
[31]T. Ors, Z. Sun, B. G. Evans, “A MAC protocol for ATM over satellite,” IEE Telecommun., Conference Publication no. 451, pp. 185-189, April 1998.
[32]A. Iera, A. Molinaro, S. Marano, G. Aloi, “A MAC protocol for ATM-satellite systems,” VTC’99, pp. 2875-2879, 1999.
[33]W. M. Shvodian, “Multiple priority distributed round robin MAC protocol for satellite ATM,” MILCOM’98, vol. 1, pp. 258-262, Oct. 1998.
[34]Y. Sagawa, K. Okada, “Adaptive satellite channel assignment scheme in high-speed ATM data communications,” GLOBECOM’95, vol. 3, pp. 1652-1656, Nov. 1995.
[35]D. P. Gerakoulis, W. C. Chan, E. Geraniotis, “Throughput evaluation of a satellite-switched CDMA demand assignment system,” IEEE J. Select. Areas Commun., vol. 17, no. 2, pp. 286-302, Feb. 1999.
[36]D. Gerakoulis, R. Miller, S. Ghassemzadeh, and E. Geraniotis, “A satellite-switched CDMA system for fixed service communications,” IEEE Commun. Magazine, pp. 86-92, July 1999.
[37]P. Monsen, “Multiple access capacity in mobile user satellite systems,” IEEE J. Select. Areas Commun., vol. 13, no. 2, pp. 222-231, Feb. 1995.
[38]K. S. Gilhousen, I. M. Jacobs, R. Padovani, L. A. Weaver, “Increased capacity using CDMA for mobile satellite communication,” IEEE J. Select. Areas Commun., vol. 8, pp. 503-514, May 1990.
[39]K. S. Gilhousen, I. M. Jacobs, R. Padovani, A. J. Viterbi, L. A. Weaver, C. E. Wheatley III, “On the capacity of a celluar CDMA system,” IEEE Trans. Veh. Technol., vol. 40, no. 2, pp. 303-312, May 1991.
[40]P. W. Baier, P. Jung, “CDMA myths and realities revisited,” IEICE Trans. Fund., Dec. 1996.
[41]H. Biscere, M. Terre, “On the choice of TDMA or CDMA for a multimedia satellite system” Universal Personal Communications, ICUPC’98, vol. 1, pp. 641-645, Oct. 1998.
[42]H. Fu, G. Bi, K. Arichandran, “Capacity comparison of CDMA and FDMA/TDMA for a LEO satellite system,” ICC’99, vol. 2, pp. 1069-1073, June 1999.
[43]E. Biglieri, G.. Caire, J. E. Hakegard, G.. Taricco, J. Ventura-Traveset, “System capacity enhancement by using multi-user processing techniques in narrowband satellite mobile communications,” IEE Satellite Systems for Mobile Communications and Navigation, Conference publication no. 424, 1996.
[44]G. Maral, M. Bousquet, "Satellite communications systems: systems, techniques and technology, 2nd edition, John Wiley & Sons, 1993.
[45]A. A. Russo, “Multi-beam GEO satellite concept for the mobile user objective system,” MILCOM’99, vol. 2, pp. 1125-1130, Nov. 1999.
[46]M. Tanaka, M. Nakamuna, M. Kawai, I. Ohtomo, “Experimental fixed and mobile multibeam satellite communications system,” BOSTONICC’89, vol. 3, pp. 1587-1594, June 1989.
[47]D. O. Reudink, “Spot beams promise satellite communication breakthrough,” IEEE Spectrum, pp. 36-42, Sept. 1978.
[48]W. Schmidt, “An on-board switched multiple-access system for millimeter-wave satellites,” presented at 1st Digital Satellite Commun. Conf., London, 1969.
[49]M Yabusaki, S. Suzuki, “Approximate performance analysis and simulation study for variable-channel-per-burst SS-TDMA,” IEEE Trans. Commun., vol. 38, no. 3, pp. 318-326, March 1990.
[50]K. Okada, A. Ohta, K. Shimokawa, M. Kawai, “A study on satellite-switched TDMA systems for applying to the asynchronous transfer mode,” ICC’92, pp. 355-359, 1992.
[51]T. Kawabata, Y. Nagashima, Y. Moritani, T. Fujino, “Precise detection of the on-board IF-switch timing for SS-TDMA systems,” GLOBECOM’95, vol. 3, pp. 1899-1903, Nov. 1995.
[52]G. Tobin, “The UE1 scheduling algorithm for transponder-limited satellite-switched TDMA,” ICICS’97, pp. 1112-1114, Sept. 1997.
[53]Y. Motoyama, K. Nakaya, M. Kobayshi, H. Hojo, M. Kawai, “Satellite network control system for SS-TDMA,” GLOBECOM’93, vol. 2, pp. 1257-1262, Dec. 1993.
[54]Y. Ito, Y. Urano, T. Muratani, M. Yamaguchi, “Analysis of a switch matrix for an SS/TDMA system,” Proc. IEEE, vol. 65, no. 3, pp. 411-419, 1977.
[55]T. Inukai, “An efficient SS/TDMA time slot assignment algorithm,” IEEE Trans. Commun., vol. com-27, pp. 1449-1455, 1979.
[56]G. Bongiovanni, D. Coppersmith, C. K. Wong, “An optimal time slot assignment algorithm for an SS/TDMA system with variable number of transponders,” IEEE Trans. Commun., vol. 29, no. 5, pp. 721-726, 1981.
[57]I. S. Gopal, G.. Bongiovanni, M. A. Bonuccelli, D. T. Tang, C. K. Wang, “An optimal switching algorithm for multibeam satellite systems with variable bandwidth beams,” IEEE Trans. Commun., vol. 30, no. 11, pp. 2475-2481, 1982.
[58]S. Chalasni, A. Varma, “Efficient time-slot assignment algorithms for SS/TDMA systems with variable-bandwidth beams,” INFOCOM ’91, vol. 2, pp. 658-667, April 1991.
[59]S. Chalasani, A. Varma, “Parallel algorithms for time-slot assignment in TDM switching systems,” IEEE Trans. Commun., vol. 41, no. 11, pp.1736-1747, Nov. 1993.
[60]S. Chalasani, A. Varma, “Efficient time-slot assignment algorithms for SS/TDMA systems with variable-bandwidth beams,” IEEE Trans. Commun., vol. 42, no. 2/3/4, pp.1359-1370, Feb./March/April 1994.
[61]I. S. Gopal, C. K. Wong, “Minimizing the number of switching in an SS/TDMA system,” IEEE Trans. Commun, vol. 33, no. 6, pp. 497-501, 1985.
[62]N. Ansari, A. Arulambalam, S. Balasekar, “Traffic management of satellite communication network using stochastic optimization,” IEE Trans. Neural Networks, vol. 7, no. 3, pp. 732-744, May 1996.
[63]A. Ganz, G.. Karmi, “Satellite clusters: a performance study,” GLOBECOM’90, vol. 2, pp. 1122-1126, Dec. 1990.
[64]E. D. Re, R. Fantacci, “A fast packet switching satellite communication network,” INFOCOM’91, vol. 2, pp. 445-453, April 1991.
[65]M. A. Bergamo, “Terminal system and capacity for APRA-NASA high-speed SONET/ATM experiment over NASA’s advanced communications technology satellite,” MILCOM’93, vol. 1, pp. 235-241, Oct. 1993.
[66]R. Bedford, K. Chaudhry, S. Smith, “Improvement and application of the INTELSAT (SS) TDMA system,” IEE 10th International Conference on Digital Satellite Commun., vol. 2, pp. 413-418, May 1995.
[67]Y. K. Tham, “Burst assignment for satellite-switched and earth-station frequency-hopping TDMA networks,” IEE Proc. vol. 137, Pt. 1, no. 4, pp. 247-255, 1990.
[68]C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, pp.128-224, Prentice-Hall, New York. 1982.
[69]A. Baiocchi, N. Blefari-Melazzi, M. Listanti, C. Soprano, “Modeling and dimensioning of an integrated circuit and packet switching scheme on-board a processing satellite,” IEEE ICC’96, pp. 936-941, Dallas, 1996.
[70]A. Baiocchi, N. Blefari-Melazzi, M. Listanti, C. Soprano, “Definition and analysis of a reactive congestion control scheme for application to satellite switched networks,” GLOBECOM’96, vol. 3, pp. 2138-2142, 1996.
[71]A. Leon-Garcia, Probability and random processes for electrical engineering, 2nd edn., Addison Wesley, New York, 1994.