本篇博士論文於空間分時多工存取(STDMA)之跳躍式無線網路環境中，探討多群組通訊之排程與可靠性等問題。空間分時多工存取之網路利用空間分割干擾模型允許數個傳輸在相同時間中進行，並藉由排程演算法的實現將網路資源公平且有效率的分配給各無線裝置。當多群組通訊於此網路實現時，排程演算法應以縮短所需排程長度為目標，為所有群組傳輸產生適當的時間分派。在本論文中，於空間分時多工存取之網路為多群組通訊，產生具效率的排程分派，被稱作整合多群組通訊與流量導向排程問題，文中證明此問題可以透過整數線性規劃模型來描述。根據多群組傳輸限制並以提升網路傳輸效能為目標，本論文提出兩個具多項式時間效率之鏈結(Link)與節點(Node)排程演算法，簡稱SLA與SNA，用以產生能夠善用空間使用率的排程序列。另外，當多群組通訊同時發生的情況下，有限的鏈結頻寬與不當的空間分割干擾模型，產生瓶頸路徑與空間使用率不佳等問題，進而影響網路傳輸效能。為了解決這些問題，本論文運用網路編碼(Network coding)機制，提出改善瓶頸路徑傳輸效率的排程演算法，稱JSLANC。此外，基於多群組通訊之特性建立適合之干擾模型，在此模型下設計排程演算法，稱CSNA。藉由分析實驗數據的內容可以證實，所提出之排程演算法能夠於每個排程單位中，有效提升空間的使用率進而減少所需的排程長度。在可靠傳輸方面，空間分時多工存取之網路可藉由遺失回復機制，使得群組通訊進行無錯誤、無遺失的資訊交換。在回復機制中，數個分散於傳輸路徑上負責回復的節點，根據快取策略(Cache policy)暫時保留通過此節點的封包，而這些節點會根據下游節點所回饋之訊息重傳所暫存之封包，以幫助下游節點回復遺失或錯誤的封包。為了提升回復的效率，快取策略應能夠確保每個負責回復的節點可以正確的滿足下游節點的要求。然而，在快取有限資源空間的情況下，此要求往往無法達成。因此，本論文利用網路編碼機制，發展一全新的快取機制，簡稱NCFIFO，可有效的提升封包於快取暫存的時間，並且不需丟棄尚未進行回復的封包，以確保每個回復節點可以正確的提供遺失回復服務。另外，為了更進一步縮短封包錯誤回復的時間，本論文結合所設計之快取機制，建置區塊式回復傳輸，在一次錯誤回復的動作下，可以同時滿足數個接收端的回復請求。

This dissertation examines two issues of multiple-group communications in spatial time division multiple access (STDMA) networks. Firstly, STDMA networks should provide an effective solution for enabling wireless devices to access network resources with fairness and efficiency. When multiple-group communications are implemented in such networks, the scheduling algorithm should generate appropriate schedule assignments for all the transmissions where the objective aims to reduce the schedule length. In this dissertation, the problem of producing an efficient schedule sequence for multiple-group communications over a STDMA scheduling network is referred to as an integrated multiple-group communication and traffic-oriented scheduling (IMCTS) problem. It is shown that the IMCTS problem can be formulated as an integer linear programming (ILP) problem. Two polynomial-time link- and node-based scheduling algorithms, designated as source-parallel-aware link assignment (SLA) and source-parallel-aware node assignment (SNA), respectively, are proposed for determining the schedule sequence subject to transmission constraints. In addition, this dissertation shows that a effect of bottleneck path and a inappropriate interference model impact on the transmission performance of traffic-oriented scheduling networks. To enhance the spatial utilization efficiency within each time slot, an advanced version of SNA, designated as collision-allowed source-parallel-aware node assignment (CSNA), is proposed based on a modified graph-based interference model. An advanced version of SLA, designated as joint source-parallel-aware link assignment with network coding (JSLANC), is proposed to minimize the effects on bottleneck paths on the schedule frame length by flexibly applying conventional or opportunistic network coding approaches. It is shown that compared to existing TDMA- and STDMA-based algorithms, the proposed algorithms provide an effective reduction in the schedule frame length and a significant increase in the spatial utilization within each time slot.
Secondly, STDMA networks provide a local loss recovery for ensuring reliable group communications. In local loss recovery schemes, a small number of recovery nodes distributed along the transmission paths save incoming packets temporarily in accordance with a specified cache policy and retransmit these packets if they subsequently receive a request message from a downstream receiver. To reduce the recovery latency, the cache policy should ensure that the recovery nodes are always able to satisfy the retransmission requests of the downstream receivers. However, due to the limited cache size of the recovery nodes and the behavior of the cache policy, this cannot always be achieved, and thus some of the packets must be retransmitted by the sender. Accordingly, this dissertation develops a new network-coding-based cache policy, designated as network-coding-based FIFO (NCFIFO), which extends the caching time of the packets at the recovery nodes without dropping any of the incoming packets. As a result, the lost packets can be always recovered from the nearest recovery nodes and the recovery latency is significantly reduced. The loss recovery performance of the NCFIFO cache policy is compared with that of existing cache policies by performing a series of simulation experiments using both a uniform error model and a burst error model. The simulation results show that the NCFIFO cache policy not only achieves a better recovery performance than existing cache policies, but also provides a more effective solution for managing a small amount of cache size in environments characterized by a high packet arrival rate.

[1] P. Mohapatra, C. Gui, J. Li, Group communications in mobile ad hoc networks, IEEE Computer, vol.37, no.2, pp.52-59, 2004.
[2] A. Karaman, H. Hassanein, QoS-constrained core selection for group communication, Computer Communications, vol.30, no.7, pp.1600-1612, 2007.
[3] J. F. Kurose, K. W. Ross, Computer Networking: a top-down approach featuring the Internet, second ed., Addison Wesley, 2003.
[4] E. Jeong, L. Jacob, S. Maeng, Dynamic TDMA with priority-based request packet transmission scheme for integrated multimedia traffics, IEICE Transactions on Communications, vol.E82-B, no.12, pp.2136-2144, 1999.
[5] R. Nelson, L. Kleinrock, Spatial TDMA: a collision-free multihop channel access protocol, IEEE Transactions on Communications, vol.33, no.9, pp.934–944, 1985.
[6] S. Ramanathan, E. L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking, vol.1, no.2, pp.166–177, 1993.
[7] S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, vol.5, no.2, pp.81-94, 1999.
[8] A. D. Gore, A. Karandikar, S. Jagabathula, On high spatial reuse link scheduling in STDMA wireless ad hoc networks, in: Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), Washington, DC, USA, pp. 736-741, 2007.
[9] A. Behzad, I. Rubin, Optimum integrated link scheduling and power control for multihop wireless networks, IEEE Transactions on Vehicular Technology, vol.56, no.1, pp.194-205, 2007.
[10] P. Djukic, S. Valaee, Delay aware link scheduling for multi-hop TDMA wireless networks, IEEE/ACM Transactions on Networking, vol.17, no.3, pp.870–883, 2009.
[11] B. Hajek, G. Sasaki, Link scheduling in polynomial time, IEEE Transactions on Information Theory, vol.34, no.5, pp.910-917, 1988.
[12] P. Cappanera, L. Lenzini, A. Lori, G. Stea, G. Vaglini, Efficient link scheduling for online admission control of real-time traffic in wireless mesh networks, Computer Communications, vol.34, no.8, pp.922-934, 2011.
[13] S. Liu, S. Feng, W. Ye, H. Zhuang, Slot allocation algorithms in centralized scheduling scheme for IEEE 802.16 based wireless mesh networks, Computer Communications, vol.32, no.5, pp.943-953, 2009.
[14] A. Ephremides, T. V. Truong, Scheduling broadcasts in multihop radio networks, IEEE Transactions on Communications, vol.38, no.4, pp.456–460, 1990.
[15] X. Wu, B. S. Sharif, O. R. Hinton, C. C. Tsimenidis, Solving optimum TDMA broadcast scheduling in mobile ad hoc networks: a competent permutation genetic algorithm approach, IEE Proceedings-Communications, vol.152, no.6, pp.780–788, 2005.
[16] J. Yeo, H. Lee, S. Kim, An efficient broadcast scheduling algorithm for TDMA ad-hoc networks, Computers & Operations Research, vol.29, no.13, pp.1793–1806, 2002.
[17] N. Funabiki, Y. Takefuji, A parallel algorithm for broadcast scheduling problems in packet radio networks, IEEE Transactions on Communications, vol.41, no.6, pp.828-831, 1993.
[18] M. Cagalj, J.-P. Hubaux, C. Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, in: Proceedings of the 8th annual international conference on Mobile computing and networking (MOBICOM), Atlanta, Georgia, USA, pp. 172-182, 2002.
[19] J. Grönkvist, Novel assignment strategies for spatial reuse TDMA in wireless ad hoc networks, Wireless Networks, vol.12, no.2, pp.255-265, 2006.
[20] J. W. Atwood, A classification of reliable multicast protocols. IEEE Network, vol.18, no.3, pp.24-34, 2004.
[21] S. Paul, K. K. Sabnani, J. C.-H. Lin, S. Bhattacharyya, Reliable multicast transport protocol (RMTP). IEEE Journal on Selected Areas in Communications, vol.15, no.3, pp. 407-421, 1997.
[22] S. Floyd, V. Jacobson, C.-G. Liu, S. McCanne, L. Zhang, A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM Transactions on Networking, vol.5, no.6, pp.784-803, 1997.
[23] L.-W. H. Lehman, S. J. Garland, D. L. Tennenhouse, Active reliable multicast. In Proceedings of 17th IEEE International Conference on Computer Communications (INFOCOM), vol.2, pp. 581-589, 1998.
[24] A. M. Costello, S. McCanne, Search party: using randomcast for reliable multicast with local recovery. In Proceedings of 18th IEEE International Conference on Computer Communications (INFOCOM), vol.3, pp.1256-1264, 1999.
[25] C. Papadopoulos, G. Parulkar, G. Varghese, An error control scheme for large-scale multicast applications. In Proceedings of 17th IEEE International Conference on Computer Communications (INFOCOM), vol.3, pp.1188-1196, 1998.
[26] S. K. Kasera, S. Bhattacharyya, M. Keaton, D. Kiwior, S. Zabele, J. Kurose, D. Towsley, Scalable fair reliable multicast using active services. IEEE Network, vol.14, no.1, pp.48-57, 2000.
[27] H. W. Holbrook, S. K. Singhal, D. R. Cheriton, Log-based receiver-reliable multicast for distributed interactive simulation. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), pp.328-341, 1995.
[28] P. Radoslavov, C. Papadopoulos, R. Govindan, D. Estrin, A comparison of application-level and router-assisted hierarchical schemes for reliable multicast. IEEE/ACM Transactions on Networking, vol.12, no.3, pp.469-482, 2004.
[29] K. L. Yeung, H.-L. T. Wong, Caching policy design and cache allocation in active reliable multicast. Computer Networks, vol.43, no.2, pp.177-193, 2003.
[30] F. Xie, G. Feng, X. Yang, Optimizing caching policy for loss recovery in reliable multicast. In Proceedings of 25th IEEE International Conference on Computer Communications (INFOCOM), pp.1-12, 2006.
[31] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, J. Crowcroft, XORs in the air: practical wireless network coding. IEEE/ACM Transactions on Networking, vol.16, no.3, pp.497-510, 2008.
[32] Z. Zhang, T. Lv, X. Su, H. Gao, Dual XOR in the air: a network coding based retransmission scheme for wireless broadcasting. In IEEE International Conference on Communications (ICC), pp.1-6, 2011.
[33] D. Chafekar, V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, A. Srinivasan, Approximation algorithms for computing capacity of wireless networks with SINR constraints, in: Proceedings of 27th IEEE International Conference on Computer Communications (INFOCOM), Phoenix, AZ, USA, pp. 1166-1174, 2008.
[34] J. Grönkvist, A. Hansson, Comparison between graph-based and interference-based STDMA scheduling, in: Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing (MOBIHOC), Long Beach, CA, USA, pp. 255-258, 2001.
[35] A. Behzad, I. Rubin, On the performance of graph-based scheduling algorithms for packet radio networks, in: Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), San Francisco, USA, vol.6, pp.3432-3436, 2003.
[36] G. Chakraborty, Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks, IEEE Transactions on Communications, vol.52, no.5, pp.765–777, 2004.
[37] J. Tang, G. Xue, C. Chandler, W. Zhang, "Link scheduling with power control for throughput enhancement in multihop wireless networks," IEEE Transactions on Vehicular Technology, vol.55, no.3, pp.733-742, 2006.
[38] D. B. West, Introduction to Graph Theory, second ed., Prentice Hall, 2001.
[39] P. Cappanera, L. Lenzini, A. Lori, G. Stea, G. Vaglini, Link scheduling with end-to-end delay constraints in wireless mesh networks, in: Proceedings of the 10th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), Kos, Greece, pp. 1-9, 2009.
[40] H. Liu, B. Zhao, Optimal scheduling for link assignment in traffic-sensitive STDMA wireless ad-hoc networks, in: Proceedings of International Conference on Computer Networks and Mobile Computing (ICCNMC), Zhangjiajie, China, pp.218-228, 2005.
[41] P. Bjorklund, P. Varbrand, D. Yuan, Resource optimization of spatial TDMA in ad hoc radio networks: a column generation approach, in: Proceedings of 22th IEEE International Conference on Computer Communications (INFOCOM), San Francisco, USA, vol.2, pp. 818-824, 2003.
[42] K. Papadaki, V. Friderikos, Approximate dynamic programming for link scheduling in wireless mesh networks, Computers & Operations Research, vol.35, no.12, pp.3848–3859, 2008.
[43] G. Sharma, R. R. Mazumdar, N. B. Shroff, On the complexity of scheduling in wireless networks, in: Proceedings of the 12th annual international conference on Mobile computing and networking (MOBICOM), Los Angeles, CA, USA, pp. 227-238, 2006.
[44] R. Gunasekaran, S. Siddharth, P. Krishnaraj, M. Kalaiarasan, V. R. Uthariaraj, Efficient algorithms to solve broadcast scheduling problem in WiMAX mesh networks, Computer Communications, vol.33, no.11, pp.1325-1333, 2010.
[45] H. Shi, L. Wang, A hybrid neural network for optimal TDMA transmission scheduling in packet radio networks, in Proceedings of IEEE International Joint Conference on Neural Networks (IJCNN), Montreal, Canada, vol.5, pp.3210–3213, 2005.
[46] R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung. “Network information flow”, IEEE Transactions on Information Theory, vol.46, no.4, pp.1204-1216, 2000.
[47] S.-Y. R. Li, R. W. Yeung, N. Cai. “Linear network coding”, IEEE Transactions on Information Theory, vol.49, no.2, pp.371-381, 2003.
[48] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, “A random linear network coding approach to multicast", IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430, 2006.
[49] R. Koetter, M. Médard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol.11, no.5, pp.782-795, 2003.
[50] Y. Zhu, B. Li, J. Guo, ”Multicast with network coding in application-layer overlay networks”, IEEE Journal on Selected Areas in Communications, vol.22, no.1, pp.1-13, 2004.
[51] Y. Wu, S.Y. Kung, “Distributed utility maximization for network coding based multicasting: A shortest path approach”, IEEE Journal on Selected Areas in Communications, vol.24, no.8, pp.1475-1488, 2006.
[52] J. Zhao, F. Yang, Q. Zhang, Z. Zhang, F. Zhang, "LION: Layered Overlay Multicast With Network Coding," IEEE Transactions on Multimedia, vol.8, no.5, pp.1021-1032, 2006.
[53] H. Yomo, P. Popovski, “Opportunistic scheduling for wireless network coding,” IEEE Transactions on Wireless Communications, vol.8, no.6, pp.2766-2770, 2009.
[54] T. Cui, L. Chen, T. Ho, "Energy Efficient Opportunistic Network Coding for Wireless Networks," Proceedings of 27th IEEE International Conference on Computer Communications (INFOCOM’08), Phoenix, AZ, U.S.A., pp.1022-1030, 2008.
[55] S. Sengupta, S. Rayanchu, S. Banerjee, “An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding -Aware Routing,” Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM’07), Anchorage, AK, U.S.A., pp.1028-1036, 2007.
[56] H. Seferoglu, A. Markopoulou, "Opportunistic network coding for video streaming over wireless," Proceedings of 16th International Packet Video Workshop (PV2007), Lausanne, Switzerland, pp.191-200, 2007.
[57] J. Le, J. C. S. Lui, D. M. Chiu, "Towards Coding-Efficient Link-Scheduling and Coding-Aware Routing in Wireless Networks," Proceedings of 15th IEEE International Conference on Network Protocols (ICNP’07), Beijing, China, pp.326-327, 2007.
[58] U. T. Nguyen, On multicast routing in wireless mesh networks, Computer Communications, vol.31, no.7, pp.1385-1399, 2008.
[59] C. Mala, S. Selvakumar, Construction of an optimal multicast tree for group communication in a cellular network using genetic algorithm, Computer Communications, vol.29, no.16, pp.3306-3312, 2006.
[60] R. C. T. Lee, S. S. Tseng, R. C. Chang, Y. T. Tsai, Introduction to the Design and Analysis of Algorithms, McGraw-Hill Education, 2005.
[61] S.-C. Wang, D. S. L. Wei, S.-Y. Kuo, An SPT-based topology control algorithm for wireless ad hoc networks, Computer Communications, vol.29, no.16, pp.3092-3103, 2006.
[62] A. Popescu, D. Constantinescu, D. Erman, D. Ilie, A survey of reliable multicast communication. In 3rd EuroNGI Conference on Next Generation Internet Networks, pp.111-118, 2007.
[63] K. Katsaros, G. Xylomenos, G. C. Polyzos, A hybrid overlay multicast and caching scheme for information-centric networking. In Proceedings of 29th IEEE International Conference on Computer Communications (INFOCOM), pp.1-6, 2010.
[64] M. P. Anastasopoulos, P. G. Cottis, High altitude platform networks: a feedback suppression algorithm for reliable multicast/broadcast services. IEEE Transactions on Wireless Communications, vol.8, no.4, pp.1639-1643, 2009.
[65] H. ElAarag, M. Bassiouni, A reliable congestion control mechanism for geocasting in mobile wireless networks. International Journal of Network Management, vol.13, no.5, pp.375-387, 2003.
[66] M. S. Lacher, J. Nonnenmacher, E. W. Biersack, Performance comparison of centralized versus distributed error recovery for reliable multicast,” IEEE/ACM Transactions on Networking, vol.8, no.2, pp.224-238, 2000.
[67] S. Yong, L. B. Sung, XOR retransmission in multicast error recovery. In Proceedings of the 8th IEEE International Conference on Networks (ICON), pp.336-340, 2000.
[68] K. Chi, X. Jiang, S. Horiguchi, Network coding-based reliable multicast in wireless networks. Computer Networks, vol.54, no.11, pp.1823-1836, 2010.
[69] L. Wilhelmsson, L. B. Milstein, On the effect of imperfect interleaving for the Gilbert–Elliott channel. IEEE Transactions on Communications, vol.47, no.5, pp.681-688, 1999.
[70] The Network Simulator - ns-2. http://isi.edu/nsnam/ns/