我們提出兩種傳輸速率排程演算法針對單點跳躍無線網路傳送對時間靈敏的群播串流資料。演算法的設計是為了傳送串流片段中的編碼封包序列可以有較短的傳輸終止時間(stopping time)。
假設存在一種編碼方法可以編碼相同下載鏈結封包串流，只要每一群播使用者接收到k個編碼過的封包，就足以還原原來的傳輸訊息。同時，假設排程者對每個頻道狀態有完善的訊息。基於這些假設，我們的方法是簡單的在每個時間槽決定可行的最佳傳輸速率，也就是每個時間槽傳送幾個封包。傳輸速率的選擇是為了同時達到高多用戶分集增益以及高廣播增益，當k很大時如同傳統的方法。此外，為了限制群組使用者接收封包的差異範圍，選擇速率是很重要的，特別是當k很小的時候。關於這點，我們提出分群的概念，並安排相對於收到比較少封包的使用者為子群組，稱為 least received-information subgroup，其群組大小會隨著時間改變。另外，我們考慮群組使用者接收資訊延遲的權重，然後提出兩種方法從子群組使用者中選擇可行的最佳速率。具體來說，其中一個是在子群組中選擇速率可以讓接收較少的子群組有最大的權重值；另一個方法則是在子群組中選擇速率可以讓整體群組有最大的權重值。這兩種方法的主要精神是簡單地提高接收訊息較少使用者服務的優先權，因為相對於其他接收資訊進度較前面的使用者，他們有更多的時間有接收服務的機會。我們的結果顯示當k很小且為 iid 的頻道條件下，提出的方法會比傳統k很大時設計的最佳方法達到較短的傳輸終止時間，在群組使用者人數沒有太少的情況下，此效果在高的訊號雜訊比時會更明顯。

We propose two transmission rate scheduling algorithms for sending time-sensitive multicast streaming data in a single hop wireless network. The algorithms are designed to allow the transmission of each sequence of encoded packets from a stream fragment to terminate in a shorter stopping time.
Assume that there exists a coding method for encoding forward-link packet streams such that it is sufficient for a user to decode a transmitted message by collecting k encoded packets. Also assume that the scheduler has perfect information of each channel state. Based on the assumptions, our approach is simply to choose for current time slot a peak feasible transmission rate, in terms of packets per slot. The transmission rate is chosen to achieve high multi-user diversity gain and high broadcast gain simultaneously, as developed in traditional approaches for large k. Besides, it is important for the chosen rate to limit the range of difference of packets received by each group user particularly when k is small. In this regards, we exploit the concept of grouping and arrange those users having received relatively less numbers of packets into a subgroup, called the least received-information subgroup whose size changes with time. We additionally consider the weight of received information lag among group users. We then develop two methods to choose the peak feasible rate from users in the subgroup. Specifically, one of them is to select the rate in the subgroup that maximizes the weighted volume of transmission to the least received-information subgroup; The other is to select the rate in the subgroup that maximizes the weighted volume of transmission to the whole group. The spirit under the two methods is that “simply raise the service priority of least received-information users because other users ahead in received information have more time to receive service opportunities.” Our results show that for small k and iid channel conditions, the proposed methods do achieve a shorter stopping time as compared to the best traditional approach designed for large k. This effect becomes more obvious for high channel SNR.

[1]Andrew S. Tanenbaum “Computer Networks 4th edition”, Prentice Hall, August 19, 2002

[2]R.Knopp and P.Humblet, “Information capcity and power control in single cell multiuser communications,” in Proc. IEEE ICC’95, Seattle, WA, vol.1, pp.331-335, Jun. 1995.

[3] H. Won, H Cai, D. Y. Eun, K. Gua, A. Netravali, I. Rhee, and K. Sabnani, “Multicast scheduling in cellular data networks,” IEEE Trans. Wireless Communications, vol.8, pp.4540-4549, Sep. 2009.

[4] JuYeop Kim and Dong-Ho Cho, “Enhanced Adaptive Modulation and Coding Schemes Based on Multiple Channel Reportings for Wireless Multicast
Systems”, in Vehicular Technology Conference, 2005.

[5] Ulas C. Kozat, “On the throughput capacity of opportunistic multicasting with erasure codes,” in Proc. IEEE Infocom 2008, pp.1193-1201, Apr. 2008.

[6] Gallager, R, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol.8, p.21-28, Jan. 1962.

[7] S. Li, R. Yeung, and N. Cai, “Linear network coding”, IEEE Trans. Inform. Theory, vol.49, p.371-381, Feb. 2003.

[8] Stephen B. Wicker,Vijay K. Bhargava, “Reed-Solomon Codes and Their Applications”, IEEE PRESS, Oct. 1999.

[9] S. Borst, “User-level performance of channel-aware scheduling algorithms in wireless data networks,” IEEE/ACM Trans. Networking, vol.13, no.3, pp.636-647, June 2005.

[10] J.-T. Tsai, “Sate-dependent proportional fair scheduling algorithm for wireless forward link data services,” in Proc. IEEE Infocom 2008, Phoenix, pp.331-335, Apr. 2008.

[11] Qi Bi “A Forward Link Performance Study of the 1xEV-DO Rev. 0 System Using Field Measurements and Simulations”, Lucent Technologies, March 2004

[12]Jung-Tsung Tsai, “Opportunistic Multicast Scheduling for Wireless Information Streaming” in proposal National Science Council 2009, Aug. 2009.

[13]Jung-Tsung Tsai, “Opportunistic Multicast Scheduling for Information Streaming in Cellular Networks” in proposal National Science Council 2010, Aug. 2010.

[14] T. Ho, M. Medard, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A
random linear network coding approach to multicast,” IEEE Trans. Inf.
Theory, vol. 52, no. 10, pp. 4413–4430, Oct. 2004.

[15] P. Agashe, R. Rezaiifar, and P. Bender, “Cdma2000 high rate broadcast packet data air interface design”, IEEE Communications Magazine, pp. 83–89, 2004.

[16] JuYeop Kim and Dong-Ho Cho, “Enhanced Adaptive Modulation and Coding Schemes Based on Multiple Channel Reportings for Wireless Multicast
Systems”, in Vehicular Technology Conference, 2005.

[17] P. K. Gopala and H. E. Gamal, “On the throughput-delay tradeoff in cellular multicast,” in Proc. of International Conference on Wireless Networks,
Communications and Mobile Computing, 2005.

[18] M. O. Sunay and A. Eksim, “Wireless multicast with multi-user diversity,” in IEEE VTC-2004-Spring, vol.3, pp.1584-1588, May 2004.

[19] D. Nguyen, T. Nguyen, B. Bose, “Wireless Broadcast Using Network
Coding,” In NetCod 2007 Workshop, San Diego, USA, Jan 2007.

[20] J. Qureshi, Chuan Heng Foh and Jianfei Cai, “An Efficient Network Coding based Retransmission Algorithm for Wireless Multicast,” in Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications(PIMRC), 2009

[21] Kaveh Pahlavan and Prashant Krishnamurthy, “Principles of Wireless Networks”, Prentice Hall PTR ,December 11, 2001