An Algorithm for Improving Throughput Guarantee of Topology-Transparent MAC Scheduling Strategy

Chaonong Xu
DOI: 10.4236/wsn.2010.210096                

Abstract

Topology-transparent MAC scheduling strategies nowadays are all based on combinatorial design. To get throughput guarantee, a cover-free set is output as scheduling strategy of network. In this paper, we aim to modify the cover-free set so that better throughput can be guaranteed. At the first step, the redundant slot of the cover-free set is proposed and found to have negative influence on the minimal guaranteed throughput. Second, we prove that any subset of a cover-free set is still a cover-free set after its redundant slots were squashed out. Our algorithm chooses the subset which has the maximal number of redundant slots, squashes all of its redundant slots, and then designates it as the network scheduling strategy. Therefore, better through- put can be guaranteed if the squashed subset is adopted as network scheduling strategy. For any topology- transparent node scheduling strategy, both the increased minimal throughput and decreased maximal transmission delay can be gotten by just using our algorithm as an extra accessory.

Keywords

MAC Scheduling, Qos, Combinatorial Design, Superimposed Code, Cover-Free Set

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	X. Lin and N. Shroff, “The Impact of Imperfect Scheduling on Cross-layer Congestion Control in Wireless Networks,” IEEE/ACM Transactions on Networking, Vol. 14, No. 2, 2006, pp. 302-315.
[2]	R. Nelson and L. Kleinrock, “Spatial TDMA - A Collision-Free Multihop Channel Access Protocol,” IEEE Tran- sactions on Communications. Vol. 33, No. 9, 1985, pp. 934-944.
[3]	T. Moscibroda, R. Wattenhofer and Y. Weber, “Protocol Design Beyond Graph-based Models,” Proceedings of the ACM 5th Workshop Hot Topics in Networks, Pisa, 2006, pp. 25-30.
[4]	A. Behzad and I. Rubin, “On the Performance of Graph- Based Scheduling Algorithms for Packet Radio Networks,” Proceedings of the IEEE Global Telecommunications Con- ference, San Francisco, 2003, pp. 3432-3436.
[5]	A. Shen, “Combinatorial Theory,” Shanghai Jiao Tong Uni- versity Press, Shanghai, 2008.
[6]	I. Chlamtac and A. Farago, “Making Transmission Schedules Immune to Topology Changes in Multi-Hop Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 2, No. 1, 1994, pp. 23-29.
[7]	J. Ju and V. O. K. Li, “An Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 6, No. 3, 1998, pp. 298-306.
[8]	V. R. Syrotiuk, C. J. Colbourn and A. C. H. Ling, “Topology-Transparent Scheduling for MANETs Using Orthogonal Arrays,” Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, 2003, pp. 43-49.
[9]	J. Ju and V. O. K. Li, “TDMA Scheduling Design of Multihop Packet Radio Networks Based on Latin Squares,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, 1999, pp. 1345-1352.
[10]	B. Xiang and Y. M. Mao, “Balanced Incomplete Block Designs Based Scheduling Scheme for Multi-Hop Ad Hoc Networks,” Proceedings of IEEE International Conference on Communications, Circuits and Systems, Xiamen, 2008, pp. 388-393.
[11]	A. Dey, “Theory of Block Designs,” John Wiley & Sons, New York, 1986.
[12]	P. C. Li, G. H. J. Van Rees and R. Wei, “Constructions of 2-Cover-Fee Families and Related Separating Hash Families,” Journal of Combinatorial Designs, Vol. 14, No. 6, 2006, pp. 423-440.
[13]	H. K. Kim and V. Lebedev, “On Optimal Superimposed Codes,” Journal of Combinatorial Designs, Vol. 12, No. 2, 2004, pp. 79-91.
[14]	W. H. Kautz and R. C. Singleton, “Nonrandom Binary Superimposed Codes,” IEEE Transaction on Information Theory, Vol. 10, No. 4, pp. 363-377, 1964.
[15]	P. Erdos, P. Frankl and Z. C. Furedi, “Families of Finite Sets in Which No Set is Covered by the Union of R Others,” Israel Journal of Mathematics, Vol. 51, No. 1-2, 1985, pp. 79-89.