survey

A Survey of TDMA Scheduling Schemes in Wireless Multihop Networks

Authors:

Aggeliki Sgora,

Dimitrios J. Vergados,

Dimitrios D. VergadosAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 47, Issue 3

Article No.: 53, Pages 1 - 39

https://doi.org/10.1145/2677955

Published: 16 April 2015 Publication History

Abstract

One of the major problems in wireless multihop networks is the scheduling of transmissions in a fair and efficient manner. Time Division Multiple Access (TDMA) seems to be one of the dominant solutions to achieve this goal since it is a simple scheme and can prolong the devices’ lifetime by allowing them to transmit only a portion of the time during conversation. For that reason, several TDMA scheduling algorithms may be found in the literature. The scope of this article is to classify the existing TDMA scheduling algorithms based on several factors, such as the entity that is scheduled, the network topology information that is needed to produce or maintain the schedule, and the entity or entities that perform the computation that produces and maintains the schedules, and to discuss the advantages and disadvantages of each category.

References

[1]

Imtiaz Ahmad, Buthaina Al-Kazemi, and A Shoba Das. 2008. An efficient algorithm to find broadcast schedule in ad hoc TDMA networks. Journal of Computer Systems, Networks, and Communications 2008 (2008), 12.

Digital Library

[2]

Gahng-Seop Ahn, Se Gi Hong, Emiliano Miluzzo, Andrew T. Campbell, and Francesca Cuomo. 2006. Funneling-MAC: A localized, sink-oriented MAC for boosting fidelity in sensor networks. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems. ACM, 293--306.

Digital Library

[3]

Farha N. Ali, Praveen K. Appani, Joseph L. Hammond, Vivek V. Mehta, D. L. Noneaker, and H. B. Russell. 2002. Distributed and adaptive TDMA algorithms for multiple-hop mobile networks. In Proceedings of the 2002 Military Communications Conference (MILCOM’02). Vol. 1. IEEE, 546--551.

[4]

K. Amouris. 2001. Space-time division multiple access (STDMA) and coordinated, power-aware MACA for mobile ad hoc networks. In Proceedings of the Global Telecommunications Conference (GLOBECOM’01). Vol. 5. IEEE, 2890--2895.

[5]

K. Amouris. 2005. Position-based broadcast TDMA scheduling for mobile ad-hoc networks (MANETs) with advantaged nodes. In Proceedings of the Military Communications Conference (MILCOM’05). IEEE, 252--257.

[6]

Matthew Andrews and Michael Dinitz. 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of the 28th Conference on Computer Communications (INFOCOM’09). IEEE, 1332--1340.

[7]

Deivasigamani Arivudainambi and Durai Rekha. 2012. An evolutionary algorithm for broadcast scheduling in wireless multihop networks. Wireless Networks 18, 7 (2012), 787--798.

Digital Library

[8]

Lichun Bao and J. J. Garcia-Luna-Aceves. 2000. Collision-free topology-dependent channel access scheduling. In Proceedings of the Military Communications Conference (MILCOM’00). Vol. 1. IEEE, 507--511.

[9]

Arash Behzad and Izhak Rubin. 2003. On the performance of graph-based scheduling algorithms for packet radio networks. In Proceedings of the Global Telecommunications Conference, 2003. GLOBECOM’03. Vol. 6. IEEE, 3432--3436.

[10]

Arash Behzad and Izhak Rubin. 2007. Optimum integrated link scheduling and power control for multihop wireless networks. IEEE Transactions on Vehicular Technology 56, 1 (2007), 194--205.

[11]

Weixing Bi, Zheng Tang, Jiahai Wang, and Qiping Cao. 2005. An improved neural network algorithm for broadcast scheduling problem in packet radio. Neural Information Processing-Letters and Reviews 9, 1 (2005), 23--29.

[12]

Patrik Bjorklund, Peter Varbrand, and Di Yuan. 2003. Resource optimization of spatial TDMA in ad hoc radio networks: A column generation approach. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’03). Vol. 2. IEEE, 818--824.

[13]

Patrik Björklund, Peter Värbrand, and Di Yuan. 2004. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Networks 2, 4 (2004), 405--418.

[14]

Gurashish Brar, Douglas M. Blough, and Paolo Santi. 2006. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. ACM, 2--13.

Digital Library

[15]

Nicolas Burri, Pascal Von Rickenbach, and Roger Wattenhofer. 2007. Dozer: Ultra-low power data gathering in sensor networks. In Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN’07). IEEE, 450--459.

Digital Library

[16]

Zhijun Cai, Mi Lu, and Costas N. Georghiades. 2003. Topology-transparent time division multiple access broadcast scheduling in multihop packet radio networks. IEEE Transactions on Vehicular Technology 52, 4 (2003), 970--984.

[17]

Paulo Cardieri. 2010. Modeling interference in wireless ad hoc networks. IEEE Communications Surveys & Tutorials 12, 4 (2010), 551--572.

Digital Library

[18]

Goutam Chakraborty. 2004. Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks. IEEE Transactions on Communications 52, 5 (2004), 765--777.

[19]

Jenhui Chen and Shuhua Jiang. 2006. Improvement of slots utilization with a stealing-TDMA protocol for ad hoc network. In Proceedings of the 2006 IEEE 64th Vehicular Technology Conference (VTC’06). IEEE, 1--5.

[20]

Jung-Chieh Chen, Yeong-Cheng Wang, and Jiunn-Tsair Chen. 2006. A novel broadcast scheduling strategy using factor graphs and the sum-product algorithm. IEEE Transactions on Wireless Communications 5, 6 (2006), 1241--1249.

Digital Library

[21]

Hongju Cheng, Naixue Xiong, Larence T. Yang, and Young-Sik Jeong. 2013. Distributed scheduling algorithms for channel access in TDMA wireless mesh networks. The Journal of Supercomputing 63, 2 (2013), 407--430.

Digital Library

[22]

Maggie Cheng and Li Yin. 2007. Transmission scheduling in sensor networks via directed edge coloring. In Proceedings of the IEEE International Conference on Communications (ICC’07). IEEE, 3710--3715.

[23]

Imrich Chlamtac and András Faragó. 1994. Making transmission schedules immune to topology changes in multi-hop packet radio networks. IEEE/ACM Transactions on Networking (TON) 2, 1 (1994), 23--29.

Digital Library

[24]

Wensong Chu, Charles J. Colbourn, and Violet R. Syrotiuk. 2006. The effects of synchronization on topology-transparent scheduling. Wireless Networks 12, 6 (2006), 681--690.

Digital Library

[25]

Clayton W. Commander, Sergiy I. Butenko, and Panos M. Pardalos. 2004. On the performance of heuristics for broadcast scheduling. Theory and Algorithms for Cooperative Systems (2004), 63--80.

[26]

Piergiuseppe Di Marco, Pangun Park, Carlo Fischione, and Karl Henrik Johansson. 2010. TREnD: A timely, reliable, energy-efficient and dynamic WSN protocol for control applications. In Proceedings of the 2010 IEEE International Conference on Communications (ICC’10). IEEE, 1--6.

[27]

Antonis Dimakis and Jean Walrand. 2006. Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits. Advances in Applied Probability (2006), 505--521.

[28]

Petar Djukic and Shahrokh Valaee. 2007. Link scheduling for minimum delay in spatial re-use TDMA. In Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07). IEEE, 28--36.

Digital Library

[29]

Tamer ElBatt and Anthony Ephremides. 2004. Joint scheduling and power control for wireless ad hoc networks. IEEE Transactions on Wireless Communications 3, 1 (2004), 74--85.

Digital Library

[30]

Anthony Ephremides and Thuan V. Truong. 1990. Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications 38, 4 (1990), 456--460.

[31]

Zuyuan Fang and Brahim Bensaou. 2004. Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’04), Vol. 2. IEEE, 1284--1295.

[32]

Alexander Fanghänel, Thomas Kesselheim, Harald Räcke, and Berthold Vöcking. 2009. Oblivious interference scheduling. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. ACM, 220--229.

Digital Library

[33]

Hossam Fattah and Cyril Leung. 2002. An overview of scheduling algorithms in wireless multimedia networks. IEEE Wireless Communications 9, 5 (2002), 76--83.

Digital Library

[34]

Liqun Fu, Soung Chang Liew, and Jianwei Huang. 2010. Fast algorithms for joint power control and scheduling in wireless networks. IEEE Transactions on Wireless Communications 9, 3 (2010), 1186--1197.

Digital Library

[35]

Nobuo Funabiki and Junji Kitamichi. 1999. A gradual neural network algorithm for broadcast scheduling problems in packet radio networks. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences 82, 5 (1999), 815--824.

[36]

Vijay Gabale, Bhaskaran Raman, Partha Dutta, S. Gabale, and S. Kalyanraman. 2013. A classification framework for scheduling algorithms in wireless mesh networks. IEEE Communications Surveys & Tutorials 15, 1 (2013), 199--222.

[37]

Harold N. Gabow and Herbert H. Westermann. 1992. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7, 1--6 (1992), 465--497.

[38]

Sachin Gajjar, Shrikant N. Pradhan, and Kankar Dasgupta. 2012. Performance analysis of cross layer protocols for wireless sensor networks. In Proceedings of the International Conference on Advances in Computing, Communications and Informatics. ACM, 348--354.

Digital Library

[39]

S. Gandham, M. Dawande, and R. Prakash. 2005. Link scheduling in sensor networks: Distributed edge coloring revisited. In Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05). Vol. 4. IEEE, 2492--2501.

[40]

Yan Gao, Jennifer C. Hou, and Hoang Nguyen. 2008. Topology control for maintaining network connectivity and maximizing network capacity under the physical model. In Proceedings of the 27th Conference on Computer Communications (INFOCOM’08). IEEE, 1013--1021.

[41]

Ashutosh Deepak Gore and Abhay Karandikar. 2011. Link scheduling algorithms for wireless mesh networks. IEEE Communications Surveys & Tutorials 13, 2 (2011), 258--273.

[42]

Ashutosh Deepak Gore, Abhay Karandikar, and Srikanth Jagabathula. 2007. On high spatial reuse link scheduling in STDMA wireless ad hoc networks. In Proceedings of the Global Telecommunications Conference (GLOBECOM’07). IEEE, 736--741.

[43]

Olga Goussevskaia, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2010. Efficiency of wireless networks: Approximation algorithms for the physical interference model. Foundations and Trends in Networking 4, 3 (2010), 313--420.

Digital Library

[44]

Olga Goussevskaia and Roger Wattenhofer. 2008. Complexity of scheduling with analog network coding. In Proceedings of the 1st ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing. ACM, 77--84.

Digital Library

[45]

Olga Goussevskaia, Roger Wattenhofer, Magnús M. Halldórsson, and Emo Welzl. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th Conference on Computer Communications (INFOCOM’09). IEEE, 1872--1880.

[46]

Jimmi Grönkvist. 2006. Novel assignment strategies for spatial reuse TDMA in wireless ad hoc networks. Wireless Networks 12, 2 (2006), 255--265.

Digital Library

[47]

R. Gunasekaran, S. Siddharth, P. Krishnaraj, M. Kalaiarasan, and V. Rhymend Uthariaraj. 2010. Efficient algorithms to solve broadcast scheduling problem in WiMAX mesh networks. Computer Communications 33, 11 (2010), 1325--1333.

Digital Library

[48]

Piyush Gupta and Panganmala R. Kumar. 2000. The capacity of wireless networks. IEEE Transactions on Information Theory 46, 2 (2000), 388--404.

Digital Library

[49]

Magnús M. Halldórsson and Pradipta Mitra. 2012. Wireless capacity with arbitrary gain matrix. In Algorithms for Sensor Systems. Springer, 215--224.

Digital Library

[50]

Bo Han, Fung Po Tso, Lidong Ling, and Weijia Jia. 2006. Performance evaluation of scheduling in IEEE 802.16 based wireless mesh networks. In Proceedings of the 2006 IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS’06). IEEE, 789--794.

[51]

Barbara Hohlt, Lance Doherty, and Eric Brewer. 2004. Flexible power scheduling for sensor networks. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. ACM, 205--214.

Digital Library

[52]

IEEE. 1999. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Standard 802, 1 (1999), 999.

[53]

Ozlem Durmaz Incel, Lodewijk van Hoesel, Pierre Jansen, and Paul Havinga. 2011. MC-LMAC: A multi-channel MAC protocol for wireless sensor networks. Ad Hoc Networks 9, 1 (2011), 73--94.

Digital Library

[54]

Changhee Joo, Xiaojun Lin, and Ness B. Shroff. 2009. Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks. IEEE/ACM Transactions on Networking (TON) 17, 4 (2009), 1132--1145.

Digital Library

[55]

Ji-Her Ju and V. O. K. Li. 2006. TDMA scheduling design of multihop packet radio networks based on latin squares. IEEE Journal on Selected Areas in Communications 17, 8 (2006), 1345--1352.

Digital Library

[56]

Ji-Her Ju and Victor OK Li. 1998. An optimal topology-transparent scheduling method in multihop packet radio networks. IEEE/ACM Transactions on Networking (TON) 6, 3 (1998), 298--306.

Digital Library

[57]

Raja Jurdak, Cristina Videira Lopes, and Pierre Baldi. 2004. A survey, classification and comparative analysis of medium access control protocols for ad hoc networks. IEEE Communications Surveys & Tutorials 6, 1 (2004), 2--16.

Digital Library

[58]

Bastian Katz, Markus Völker, and Dorothea Wagner. 2008. Link scheduling in local interference models. In Algorithmic Aspects of Wireless Sensor Networks. Springer, 57--71.

Digital Library

[59]

Youngmin Kim, Hyojeong Shin, and Hojung Cha. 2008. Y-mac: An energy-efficient multi-channel mac protocol for dense wireless sensor networks. In Proceedings of the 7th International Conference on Information Processing in Sensor Networks. IEEE Computer Society, 53--63.

Digital Library

[60]

Kurtis Kredo and Prasant Mohapatra. 2007. Medium access control in wireless sensor networks. Computer Networks 51, 4 (2007), 961--994.

Digital Library

[61]

Luobei Kuang, Ming Xu, and Wei Yu. 2008. EMDF-A broadcast scheduling policy for wireless multi-hop networks with interference constraint. In Proceedings of the 9th International Conference for Young Computer Scientists (ICYCS’08). IEEE, 599--604.

Digital Library

[62]

Winnie Louis Lee, Amitava Datta, and Rachel Cardell-Oliver. 2008. FlexiTP: A flexible-schedule-based TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems 19, 6 (2008), 851--864.

Digital Library

[63]

Johannes Lessmann and Dirk Held. 2008. A mobility-adaptive TDMA MAC for real-time data in wireless networks. In NETWORKING 2008 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet. Springer, 804--811.

Digital Library

[64]

Yun Li and Anthony Ephremides. 2007. A joint scheduling, power control, and routing algorithm for ad hoc wireless networks. Ad Hoc Networks 5, 7 (2007), 959--973.

Digital Library

[65]

Yiming Liu, Victor O. K. Li, Ka-Cheong Leung, and Lin Zhang. 2012. Topology-transparent distributed multicast and broadcast scheduling in mobile ad hoc networks. In Proceedings of the 2012 IEEE 75th Vehicular Technology Conference (VTC Spring). IEEE, 1--5.

[66]

Chun-Chi Lo, Yu-Chen Hu, and Chia-Ying Li. 2010. A distributed communication protocol for wireless sensor networks with asynchronous superframe. In Proceedings of the 2010 IET International Conference on Frontier Computing. Theory, Technologies and Applications (IETFC’10). 235--240.

[67]

Valeria Loscri. 2007. MAC schemes for ad-hoc wireless networks. In Proceedings of the 2007 IEEE 66th Vehicular Technology Conference (VTC’07 Fall). IEEE, 36--40.

[68]

Wyin-Pyin Lyui. 1991. Design of a New Operational Structure for Mobile Radio Networks. PhD Dissertation. Clemson University.

[69]

Jianlin Mao, Zhiming Wu, and Xing Wu. 2007. A TDMA scheduling scheme for many-to-one communications in wireless sensor networks. Computer Communications 30, 4 (2007), 863--872.

Digital Library

[70]

Thomas Moscibroda, Yvonne Anne Oswald, and Roger Wattenhofer. 2007. How optimal are wireless scheduling protocols&quest; In Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07). IEEE, 1433--1441.

[71]

Thomas Moscibroda, Roger Wattenhofer, and Yves Weber. 2006a. Protocol design beyond graph-based models. In Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets-V). 25--30.

[72]

Thomas Moscibroda, Roger Wattenhofer, and Aaron Zollinger. 2006b. Topology control meets SINR: The scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 310--321.

Digital Library

[73]

Randolph Nelson and Leonard Kleinrock. 1985. Spatial TDMA: A collision-free multihop channel access protocol. IEEE Transactions on Communications 33, 9 (1985), 934--944.

[74]

Chiu Yeung Ngo and Victor OK Li. 2003. Centralized broadcast scheduling in packet radio networks via genetic-fix algorithms. IEEE Transactions on Communications 51, 9 (2003), 1439--1441.

[75]

Konstantinos Oikonomou and Ioannis Stavrakakis. 2004. Analysis of a probabilistic topology-unaware TDMA MAC policy for ad hoc networks. IEEE Journal on Selected Areas in Communications 22, 7 (2004), 1286--1300.

Digital Library

[76]

Konstantinos Oikonomou and Ioannis Stavrakakis. 2006. Energy considerations for topology-unaware TDMA MAC protocols. Ad Hoc Networks 4, 3 (2006), 359--379.

Digital Library

[77]

Katerina Papadaki and Vasilis Friderikos. 2008. Robust scheduling in spatial reuse TDMA wireless networks. IEEE Transactions on Wireless Communications 7, 12 (2008), 4767--4771.

Digital Library

[78]

Georgios I. Papadimitriou, Mohammad S. Obaidat, and Andreas S. Pomportsis. 2002. On the use of learning automata in the control of broadcast networks: A methodology. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 32, 6 (2002), 781--790.

Digital Library

[79]

Sung Park and Denh Sy. 2008. Dynamic control slot scheduling algorithms for TDMA based mobile ad hoc networks. In Proceedings of the Military Communications Conference (MILCOM’08). IEEE, 1--7.

[80]

Pranav Pawar, Rasmus Nielsen, Neeli Prasad, Shingo Ohmori, and Ramjee Prasad. 2011. Hybrid mechanisms: Towards an efficient wireless sensor network medium access control. In Proceedings of the 2011 14th International Symposium on Wireless Personal Multimedia Communications (WPMC’11). IEEE, 1--5.

[81]

Y. Peng, B. H. Soong, and L. Wang. 2004. Broadcast scheduling in packet radio networks using mixed tabu-greedy algorithm. Electronics Letters 40, 6 (2004), 375--376.

[82]

Subramanian Ramanathan. 1999. A unified framework and algorithm for channel assignment in wireless networks. Wireless Networks 5, 2 (1999), 81--94.

Digital Library

[83]

Subramanian Ramanathan and Errol L. Lloyd. 1993. Scheduling algorithms for multihop radio networks. IEEE/ACM Transactions on Networking (TON) 1, 2 (1993), 166--177.

Digital Library

[84]

Injong Rhee, Ajit Warrier, Mahesh Aia, Jeongki Min, and Mihail L. Sichitiu. 2008. Z-MAC: A hybrid MAC for wireless sensor networks. IEEE/ACM Transactions on Networking (TON) 16, 3 (2008), 511--524.

Digital Library

[85]

Injong Rhee, Ajit Warrier, Jeongki Min, and Lisong Xu. 2006. DRAND: Distributed randomized TDMA scheduling for wireless ad-hoc networks. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 190--201.

Digital Library

[86]

Izhak Rubin and Zhensheng Zhang. 1992. Message delay analysis for TDMA schemes using contiguous-slot assignments. IEEE Transactions on Communications 40, 4 (1992), 730--737.

[87]

Mastooreh Salajegheh, Hamed Soroush, and Antonis Kalis. 2007. Hymac: Hybrid TDMA/FDMA medium access control protocol for wireless sensor networks. In Proceedings of the IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC’07). IEEE, 1--5.

[88]

Sancho Salcedo-Sanz, Carlos Bousoño-Calzón, and Aníbal R. Figueiras-Vidal. 2003. A mixed neural-genetic algorithm for the broadcast scheduling problem. IEEE Transactions on Wireless Communications 2, 2 (2003), 277--283.

Digital Library

[89]

Paolo Santi, Ritesh Maheshwari, Giovanni Resta, Samir Das, and Douglas M. Blough. 2009. Wireless link scheduling under a graded SINR interference model. In Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing. ACM, 3--12.

Digital Library

[90]

Arunabha Sen and Mark L. Huson. 1997. A new model for scheduling packet radio networks. Wireless Networks 3, 1 (1997), 71--82.

Digital Library

[91]

A. Sgora, D. J. Vergados, and D. D. Vergados. 2008a. On per-flow fairness and scheduling in wireless multihop networks. In Proceedings of the IEEE International Conference on Communications Workshops. IEEE, 217--221.

[92]

A. Sgora, D. J. Vergados, D. D. Vergados, I. Tinnirello, I. Anagnostopoulos, and D. Vouyioukas. 2008b. Joint routing and per-flow fairness in wireless multihop networks. In Proceedings of the 3rd International Symposium on Wireless Pervasive Computing (ISWPC’08). IEEE, 707--711.

[93]

Yu-Ju Shen and Ming-Shi Wang. 2008. Broadcast scheduling in wireless sensor networks using fuzzy hopfield neural network. Expert Systems with Applications 34, 2 (2008), 900--907.

Digital Library

[94]

Haixiang Shi and Lipo Wang. 2005a. Broadcast scheduling in wireless multihop networks using a neural-network-based hybrid algorithm. Neural Networks 18, 5 (2005), 765--771.

Digital Library

[95]

Haixiang Shi and Lipo Wang. 2005b. A hybrid neural network for optimal TDMA transmission scheduling in packet radio networks. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks (IJCNN’05), Vol. 5. IEEE, 3210--3213.

[96]

Haixiang Shi and Lipo Wang. 2005c. Optimal TDMA frame scheduling in broadcasting packet radio networks using a gradual noisy chaotic neural network. In Advances in Natural Computation. Springer, 1080--1089.

Digital Library

[97]

Lanny Sitanayah, Cormac J. Sreenan, and Kenneth N. Brown. 2010. ER-MAC: A hybrid MAC protocol for emergency response wireless sensor networks. In Proceedings of the 4th International Conference on Sensor Technologies and Applications (SENSORCOMM’10). IEEE, 244--249.

Digital Library

[98]

Fikret Sivrikaya and Bülent Yener. 2009. Minimum delay routing for wireless networks with STDMA. Wireless Networks 15, 6 (2009), 755--772.

Digital Library

[99]

Wen-Zhan Song, Renjie Huang, Behrooz Shirazi, and Richard LaHusen. 2009. TreeMAC: Localized TDMA MAC protocol for real-time high-data-rate sensor networks. Pervasive and Mobile Computing 5, 6 (2009), 750--765.

Digital Library

[100]

Yi-Sheng Su. 2008. Joint topology-transparent broadcast scheduling and MDS erasure coding in multihop TDMA ad hoc networks. In Proceedings of the IEEE International Symposium on Consumer Electronics (ISCE’08). IEEE, 1--4.

[101]

Yi-Sheng Su, Szu-Lin Su, and Jung-Shian Li. 2004. Topology-transparent node activation scheduling schemes for multihop TDMA ad hoc networks. In Proceedings of the Global Telecommunications Conference Workshops (GlobeCom’04). IEEE. IEEE, 68--73.

[102]

Ming Sun, Lin Zhao, Wei Cao, Yaoqun Xu, Xuefeng Dai, and Xiaoxu Wang. 2010. Novel hysteretic noisy chaotic neural network for broadcast scheduling problems in packet radio networks. IEEE Transactions on Neural Networks 21, 9 (2010), 1422--1433.

Digital Library

[103]

Qiong Sun, Victor O. K. Li, and Ka-Cheong Leung. 2008. Topology-transparent distributed scheduling in multi-hop wireless networks. In Proceedings of the Global Telecommunications Conference (GLOBECOM’08). IEEE, 1--5.

[104]

Petcharat Suriyachai, Utz Roedig, and Andrew Scott. 2012. A survey of MAC protocols for mission-critical applications in wireless sensor networks. IEEE Communications Surveys & Tutorials 14, 2 (2012), 240--264.

[105]

Yoshiyasu Takefuji, Kuo-Chun Lee, and Hideo Also. 1992. An artificial maximum neural network: A winner-take-all neuron model forcing the state of the system in a solution domain. Biological Cybernetics 67, 3 (1992), 243--251.

Digital Library

[106]

Jian Tang, Guoliang Xue, Christopher Chandler, and Weiyi Zhang. 2006. Link scheduling with power control for throughput enhancement in multihop wireless networks. IEEE Transactions on Vehicular Technology 55, 3 (2006), 733--742.

[107]

Leandros Tassiulas and Anthony Ephremides. 1992. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 37, 12 (1992), 1936--1948.

[108]

Dimitrios D. Vergados, Dimitrios J. Vergados, and Christos Douligeris. 2005. A new approach for TDMA scheduling in ad-hoc networks. In Proceedings of the 10th IFIP International Conference on Personal Wireless Communications (PWC’05). World Scientific, 279--286.

[109]

Dimitrios D. Vergados, Dimitrios J. Vergados, Christos Douligeris, and Spyridon L. Tombros. 2006. QoS-aware TDMA for end-to-end traffic scheduling in ad hoc networks. Wireless Communications, IEEE 13, 5 (2006), 68--74.

Digital Library

[110]

Dimitrios J. Vergados, M.-Y. Manolaraki, and Dimitrios D. Vergados. 2009. Evaluation of broadcast scheduling algorithms for ad-hoc TDMA networks. In Proceedings of the 1st International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology (Wireless VITAE’’09). IEEE, 394--398.

[111]

Dimitrios J. Vergados, Aggeliki Sgora, Dimitrios D. Vergados, Demosthenes Vouyioukas, and Ioannis Anagnostopoulos. 2012. Fair TDMA scheduling in wireless multihop networks. Telecommunication Systems 50, 3 (2012), 181--198.

Digital Library

[112]

Peng-Jun Wan, Ophir Frieder, Xiaohua Jia, Frances Yao, Xiaohua Xu, and Shaojie Tang. 2011. Wireless link scheduling under physical interference model. In Proceedings of the 2011 IEEE INFOCOM. IEEE, 838--845.

[113]

Peng-Jun Wan, Xiaohua Xu, and Ophir Frieder. 2010. Shortest link scheduling with power control under physical interference model. In Proceedings of the 6th International Conference on Mobile Ad-hoc and Sensor Networks (MSN’10). IEEE, 74--78.

Digital Library

[114]

Gangsheng Wang and Nirwan Ansari. 1997. Optimal broadcast scheduling in packet radio networks using mean field annealing. IEEE Journal on Selected Areas in Communications 15, 2 (1997), 250--260.

Digital Library

[115]

Kang Wang, Carla-Fabiana Chiasserini, Ramesh R. Rao, and John G. Proakis. 2005. A joint solution to scheduling and power control for multicasting in wireless ad hoc networks. EURASIP Journal on Applied Signal Processing 2005 (2005), 144--152.

Digital Library

[116]

Wei Wang, Xin Liu, and Dilip Krishnaswamy. 2007. Robust routing and scheduling in wireless mesh networks. In Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON’07. 4th Annual IEEE Communications Society Conference on. IEEE, 471--480.

[117]

Weizhao Wang, Yu Wang, Xiang-Yang Li, Wen-Zhan Song, and Ophir Frieder. 2006. Efficient interference-aware TDMA link scheduling for static wireless networks. In Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. ACM, 262--273.

Digital Library

[118]

Yu Wang and Ian Henning. 2007. A deterministic distributed TDMA scheduling algorithm for wireless sensor networks. In Proceedings of the International Conference on Wireless Communications, Networking and Mobile Computing (WiCom’07). IEEE, 2759--2762.

[119]

Yu Wang, Weizhao Wang, Xiang-Yang Li, and Wen-Zhan Song. 2008. Interference-aware joint routing and TDMA link scheduling for static wireless networks. IEEE Transactions on Parallel and Distributed Systems 19, 12 (2008), 1709--1726.

Digital Library

[120]

Zhiqi Wang, Fengqi Yu, Jian Tian, and Zusheng Zhang. 2012. A fairness adaptive TDMA scheduling algorithm for wireless sensor networks with unreliable links. International Journal of Communication Systems (2012).

[121]

Brian J. Wolf, Joseph L. Hammond, and Harlan B. Russell. 2006. A distributed load-based transmission scheduling protocol for wireless ad hoc networks. In Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing. ACM, 437--442.

Digital Library

[122]

Zhang Xizheng and Wang Yaonan. 2008. Efficient broadcast scheduling based on hybrid fuzzy hopfield network for ad hoc networks. In Proceedings of the 27th Chinese Control Conference (CCC’08). IEEE, 725--728.

[123]

Chaonong Xu, Yongjun Xu, Zhiguang Wang, and Haiyong Luo. 2011. A topology-transparent MAC scheduling algorithm with guaranteed QoS for multihop wireless network. Journal of Control Theory and Applications 9, 1 (2011), 106--114.

[124]

Shugong Xu and Tarek Saadawi. 2001. Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks&quest; IEEE Communications Magazine 39, 6 (2001), 130--137.

Digital Library

[125]

XiaoHua Xu and ShaoJie Tang. 2009. A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model. In Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing. ACM, 13--20.

Digital Library

[126]

Justin Yackoski and Chien-Chung Shen. 2010. Managing end-to-end delay for VoIP calls in multi-hop wireless mesh networks. In Proceedings of the INFOCOM IEEE Conference on Computer Communications Workshops. IEEE, 1--6.

[127]

Guanqun Yang, Bin Tong, Daji Qiao, and Wensheng Zhang. 2008. Sensor-aided overlay deployment and relocation for vast-scale sensor networks. In Proceedings of the 27th Conference on Computer Communications (INFOCOM’08). IEEE, 2216--2224.

[128]

Jaehyun Yeo, Heesoo Lee, and Sehun Kim. 2002. An efficient broadcast scheduling algorithm for TDMA ad-hoc networks. Computers & Operations Research 29, 13 (2002), 1793--1806.

[129]

Jong-Hoon Youn and Bella Bose. 2001. A topology-independent transmission scheduling in multihop packet radio networks. In Proceedings of the Global Telecommunications Conference. (GLOBECOM’01). Vol. 3. IEEE, 1918--1922.

[130]

Xuedan Zhang, Jun Hong, Lin Zhang, Xiuming Shan, and Victor O. K. Li. 2007. CC-TDMA: Coloring-and coding-based multi-channel TDMA scheduling for wireless ad hoc networks. In Proceedings of the Wireless Communications and Networking Conference (WCNC’07). IEEE, 133--137.

[131]

Xuedan Zhang, Jun Hong, Lin Zhang, Xiuming Shan, and Victor O. K. Li. 2008. CP-TDMA: Coloring-and5 probability-based TDMA scheduling for wireless ad hoc networks. IEICE Transactions on Communications 91, 1 (2008), 322--326.

[132]

Chenxi Zhu and M. Scott Corson. 2001a. An Evolutionary-TDMA scheduling protocol (E-TDMA) for mobile ad hoc networks. Technical Research Report, CSHCN TR 2001-17.

[133]

Chenxi Zhu and M. Scott Corson. 2001b. A five-phase reservation protocol (FPRP) for mobile ad hoc networks. Wireless Networks 7, 4 (2001), 371--384.

Digital Library

Cited By

Fulber-Garcia VEngel FDuarte E(2024)A genetic scheduling strategy with spatial reuse for dense wireless networksInternational Journal of Hybrid Intelligent Systems10.3233/HIS-23001520:1(41-55)Online publication date: 1-Apr-2024
https://doi.org/10.3233/HIS-230015
Mnisi TKamanzi JDavidson I(2024)A Study of AIS Frames Sent by CubeSats into the Ground Station2024 32nd Southern African Universities Power Engineering Conference (SAUPEC)10.1109/SAUPEC60914.2024.10445042(1-5)Online publication date: 24-Jan-2024
https://doi.org/10.1109/SAUPEC60914.2024.10445042
Liu YHuang TLiu FMa DHuangfu WEldar Y(2024)Next-Generation Multiple Access for Integrated Sensing and CommunicationsProceedings of the IEEE10.1109/JPROC.2024.3449807112:9(1467-1496)Online publication date: Sep-2024
https://doi.org/10.1109/JPROC.2024.3449807
Show More Cited By

Index Terms

A Survey of TDMA Scheduling Schemes in Wireless Multihop Networks
1. Networks
  1. Network architectures

Recommendations

A decentralized minislot scheduling protocol (DMSP) in TDMA-based wireless mesh networks

Wireless mesh network is a promising network topology that can provide high data rate backhaul network access. For achieving high data rate backhaul network access, a well-designed bandwidth scheduling protocol is necessary for wireless mesh networks. ...
Fair TDMA scheduling in wireless multihop networks

In wireless multihop networks, communication between two end-nodes is carried out by hopping over multiple wireless links. However, the fact that each node has to transmit not only its own traffic, but also traffic on behalf of other nodes, leads to ...
CCA-Embedded TDMA enabling acyclic traffic in industrial wireless sensor networks

A growing trend in the automation industry is to use wireless technologies to reduce cable costs and deployment time, unlock stranded information in deployed devices and enable wireless control applications. The WirelessHART protocol is the first open ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 47, Issue 3

April 2015

602 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2737799

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering / University of Florida / Gainesville, FL

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 April 2015

Accepted: 01 October 2014

Revised: 01 September 2014

Received: 01 September 2013

Published in CSUR Volume 47, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Survey
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
1,297
Total Downloads

Downloads (Last 12 months)116
Downloads (Last 6 weeks)16

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fulber-Garcia VEngel FDuarte E(2024)A genetic scheduling strategy with spatial reuse for dense wireless networksInternational Journal of Hybrid Intelligent Systems10.3233/HIS-23001520:1(41-55)Online publication date: 1-Apr-2024
https://doi.org/10.3233/HIS-230015
Mnisi TKamanzi JDavidson I(2024)A Study of AIS Frames Sent by CubeSats into the Ground Station2024 32nd Southern African Universities Power Engineering Conference (SAUPEC)10.1109/SAUPEC60914.2024.10445042(1-5)Online publication date: 24-Jan-2024
https://doi.org/10.1109/SAUPEC60914.2024.10445042
Liu YHuang TLiu FMa DHuangfu WEldar Y(2024)Next-Generation Multiple Access for Integrated Sensing and CommunicationsProceedings of the IEEE10.1109/JPROC.2024.3449807112:9(1467-1496)Online publication date: Sep-2024
https://doi.org/10.1109/JPROC.2024.3449807
Shida HKaburaki AAdachi K(2024)Transmission Timing and Synchronization Control for Energy-Efficient Multi-Hop LoRaWANIEEE Access10.1109/ACCESS.2024.350250112(183195-183204)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3502501
Wu MChun-Wei Lin J(2023)Design of delay compensation algorithm in remote auction network for digital art worksJournal of High Speed Networks10.3233/JHS-22204929:2(159-168)Online publication date: 21-Apr-2023
https://doi.org/10.3233/JHS-222049
Garrido-Hidalgo CRoda-Sanchez LFernández-Caballero AOlivares TRamírez F(2023)Internet-of-Things framework for scalable end-of-life condition monitoring in remanufacturingIntegrated Computer-Aided Engineering10.3233/ICA-23071631:1(1-17)Online publication date: 16-Nov-2023
https://dl.acm.org/doi/10.3233/ICA-230716
Ding HPei WYu YHu PLi BLu X(2023)New Multipriority and Variable Duration Triple Time Slot P-CSMA Protocol for Edge Servers Server DeploymentInternational Journal of RF and Microwave Computer-Aided Engineering10.1155/2023/31103832023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/3110383
Cheng XSha M(2023)Autonomous Traffic-Aware Scheduling for Industrial Wireless Sensor-Actuator NetworksACM Transactions on Sensor Networks10.1145/356105619:2(1-25)Online publication date: 3-Feb-2023
https://dl.acm.org/doi/10.1145/3561056
Zhang JCampagnaro FZorzi M(2023)Spatial-reuse TDMA for Large Scale Underwater Acoustic Multi-hop Grid NetworksOCEANS 2023 - Limerick10.1109/OCEANSLimerick52467.2023.10244345(1-6)Online publication date: 5-Jun-2023
https://doi.org/10.1109/OCEANSLimerick52467.2023.10244345
Chung KLim J(2023)Machine Learning for Relaying Topology: Optimization of IoT Networks With Energy HarvestingIEEE Access10.1109/ACCESS.2023.327063111(41827-41839)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3270631
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents