A Comparative Analysis of Delay Constrains In Mobile Ad Hoc Networks Using Max Weight Scheduling and Back Pressure Algorithms

Authors(2) :-S. Sindhupiriyaa, Dr. D. Maruthanayagam

In Wireless networks where the nodes routing and scheduling packets depend on queue overload differences, one can stabilize the queues for any feasible traffic. The delay analysis of throughput scheduling policies in such systems is extremely difficult due to complex correlations arising between the arrival, service and the queue length process. In this paper we give a regular evaluation of Back Pressure Routing algorithm and Max Weight Scheduling algorithm variants on an experimental testbed. This provides the first direct comparison of delay performance. Our result expose that even in simple network topologies these algorithms induce wide routing loops with connected high packet delay.

Authors and Affiliations

S. Sindhupiriyaa
Sri Vijay Vidyalaya College of Arts & Science, Dharmapuri, Tamilnadu, India
Dr. D. Maruthanayagam
Head/Professor, PG and Research Department of Computer Science, Sri Vijay Vidyalaya College of Arts & Science, Dharmapuri, Tamilnadu, India

MANET, Back pressure, MaxWeight Scheduling (MWS), Packet Delay and Throughput

  1. L. Bui, R. Srikant, and A. Stolyar. A novel architecture for reduction of mdelay and queueing structure complexity in the back-pressure algorithm. IEEE/ACM Trans. Network., 19(6):1597–1609, 2011.
  2. A. Stolyar. Large number of queues in tandem: Scaling properties under back-pressure algorithm. Queueing Systems, 67(2):111–126, 2011.
  3. L. Tassiulas and A.Ephermides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Automat. Contr., 39:466–478, 1993.
  4. L. Ying, S. Shakkottai, and A. Reddy. On combining shortest-path and back-pressure routing over multihop wireless networks. In Proceedings of IEEE Infocom, 2009.
  5. Tassiulas, L., & Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transaction on Automatic Control, 37(12), 1936–1948
  6. A. L. Stolyar, “Maximizing Queueing Network Utility subject to Stability: Greedy-Primal Dual Algorithm,” Queueing Systems, vol. 50, no.4, pp. 401-457, 2005.
  7. M. J. Neely et al, “Fairness and Optimal Stochastic Control for Heterogeneous Networks,” in Proc. IEEE Infocom, 2005.
  8. Sharma, G., Mazumdar, R. R., Shroff, N. B. (2006). On the complexity of scheduling in wireless networks. In Proceedings ACM MobiCom (pp. 227–238). NY, USA
  9. Tassiulas L. (1998). Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proceedings of IEEE INFOCOM, vol. 2, pp. 533–539
  10. Modiano, Eytan, Shah, Devavrat, Zussman, Gil (2006). Maximizing throughput in wireless networks via gossiping. In Proceedings of ACM SIGMETRICS, 34, vol. 34, no. 1, pp. 27–38.
  11. Gupta, A., Lin, X., Srikant, R. (2009). Low-complexity distributed scheduling algorithms for wireless networks. IEEE/ACM Transaction on Networking, 17, 1846–1859.
  12. David, A. (1983). A survey of heuristics for the weighted matching problem. Networks 13(4), 475–493.
  13. Hoepman, J. H. (2004). Simple distributed weighted matchings. In In eprint cs.DC/0410047
  14. Preis, R. (1998). Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In In general graphs, symposium on theoretical aspects of computer science, STACS 99 (pp. 259–269). Springer: Berlin
  15. Chaporkar, P., Kar, K., Luo, Xiang., & Sarkar, S. (2008). Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Transactions on Information Theory, 54(2), 572–594.
  16. Wu, X., Srikant, R., Perkins., & James R. (2007). Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. IEEE Transactions on Mobile Computing 6, 595–605.
  17. Abbas, A. M., & Kure, O. (2010) Quality of service in mobile ad hoc networks: A survey. International Journal of Ad Hoc and Ubiquitous Computing, 6, 75–98
  18. Neely, M. J. (2008a). Order optimal delay for opportunistic scheduling in multi-user wireless uplinks and downlinks. IEEE/ ACM Transaction on Networking 16(5), 1188–1199.
  19. Neely, M. J. (2008b). Delay analysis for max weight opportunistic scheduling in wireless systems. In Communication, Control, and Computing, 2008 46th Annual Allerton Conference on, pp. 683–691.
  20. Le, L. B., Jagannathan, K., & Modiano, E. (2009). Delay analysis of maximum weight scheduling in wireless ad hoc networks. In Information sciences and systems, 2009. CISS 2009. 43rd annual conference on, pp. 389–394.
  21. Neely, M. J. (2009). Delay analysis for maximal scheduling with flow control in wireless networks with bursty traffic. IEEE/ACM Transaction Networking, 17(4), 1146–1159, ISSN 1063–6692.
  22. Gupta, G. R., & Shroff, N. B. (2010). Delay analysis for wireless networks with single hop traffic and general interference constraints. IEEE/ACM Transaction on Networking, 18, 393–405.
  23. Gupta, G. R., & Shroff, N. B. (2011). Delay analysis and optimality of scheduling policies for multihop wireless networks. IEEE/ACM Transaction on Networking, 19, 129–141.
  24. X. Wang and K. Kar. Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access. In MOBIHOC ’05, pages 157–168, New York, NY, USA, 2005. ACM.
  25. Venkataramana Badarla and Douglas J. Leith On Delay Performance of Throughput Optimal Back-pressure Routing: Testbed Results, Hamilton Institute, NUI Maynooth, Ireland,IEEE

Publication Details

Published in : Volume 2 | Issue 4 | July-August 2017
Date of Publication : 2017-08-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 86-93
Manuscript Number : CSEIT172412
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

S. Sindhupiriyaa, Dr. D. Maruthanayagam, "A Comparative Analysis of Delay Constrains In Mobile Ad Hoc Networks Using Max Weight Scheduling and Back Pressure Algorithms", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 4, pp.86-93, July-August-2017. |          | BibTeX | RIS | CSV

Article Preview