Performance Evaluation of Efficient Scheduling Algorithms for Achieving Optimal Flow Delay and to Enhance Throughput in Multichannel Wireless Networks

Performance Evaluation of Efficient Scheduling Algorithms for Achieving Optimal Flow Delay and to Enhance Throughput in Multichannel Wireless Networks

Sreevarun M R

Dept. of Electronics and Communication Engg.

Bangalore Institute of Technology Bengaluru, India

Dr. M N Sreerangaraju

Dept. of Electronics and Communication Engg.

Bangalore Institute of Technology Bengaluru, India

AbstractIn this paper, we focus on designing a low complexity scheduling algorithms that can provide higher throughput along with low delay. By exploiting the features of essential conditions and appropriately combining policies from the classes of Oldest Packet First (OPF) and Maximum Weight First (MWF) policies, hybrid policies are designed, that are both delay-optimal and high throughput with a less complexity. There are 3 algorithms implemented in this paper; OPF, MWF & hybrid. Here, the maximum waiting time of the packet in each algorithm is measured and a comparison graph plotted for analysis of delay & throughput for different number of users. Network Simulator 2 (NS2) is used for design & analysis.

Index TermsOPF, MWF, Hybrid, Extension, Delay, Throughput, NS2.

proposed policies perform well for a general channel model.

Delay Weight Matching (DWM) scheduling algorithm was recently developed in [6], [7]. Here, scheduling decisions are made by maximizing the sum of the delays of the scheduled packets in each time-slot, which focuses on the delay performance directly as we do in the proposed paper. Moreover, in some cases DWM is rate-function delay- optimal.

In this paper, OPF, MWF & hybrid algorithms have been implemented using ns2 tool and their performances have been studied. In addition, an extension for the hybrid algorithm is introduced for further analysis.

1. DESIGN & IMPLEMENTATION

   1. INTRODUCTION

      Design of high-performance scheduling algorithms has been a crucial and challenging issue in wireless networks today. Among the many characteristics of network performance, the most crucial ones are throughput, delay and complexity. Here, we develop easy-to-verify conditions for rate-function delay optimality (in the multi- channel multi-user regime) and throughput optimality respectively [8]. However, in general, it is extremely difficult to develop scheduling policies that attain the optimal performance in terms of both throughput and delay, without the price of high complexity [1]. In [2], the authors have considered a single-server model with time- varying channels and showed that the longest-connected- queue (LCQ) algorithm minimizes the average delay of symmetric arrival and packets of the channel. Later, in [3] generalized results are obtained for a multiserver model. The authors of [4] considered more general permutation- invariant arrivals and multirate channel model to achieve further generalized the multiserver model. Hence, the problem of minimizing a general cost function of queue lengths (includes minimizing the expected delay) given in

      [4] becomes harder. Here in [4], a scheduling policy was derived for the cases of ONOFF channel model that involves two users or allowing for fractional server allocation. After studying the analytical results in [4] for ONOFF channel model, in [5] the authors developed heuristic policies and showed through simulations that their

      1. System Architecture:

         System architecture provides the basic understanding of the building blocks of the overall system that defines both the structure and the system behavior. It defines the system components and a plan for the system development, from which products can be procured, that will work together for the implementation of overall system. The proposed architecture of the complete overall system is pictured below:

         BS

         FBS/OPF

         Channel Schedule

         MWS

         OPF-MWS

         User Queue

         Data Reception

         Channel Allocation

         Channels

         User Node

         Out Packets

         Fig. 1 System architecture

         The above architecture comprises 5 modules; OPF, MWF, hybrid (OPF MWF), channel schedule& channel allocation. Channel scheduler schedules the essential scheduling algorithm & channel allocator allocates respective channels to the nodes in the multichannel wireless networks.

      2. Flow diagram of the proposed algorithms:

      There are 3 algorithms implemented in the proposed work.

      1. OPF Oldest Packet First

      2. MWF Maximum Weight First

      3. Hybrid (OPF-MWF)

      OPF algorithm:

      This policy, process packets from order of oldest arrived. In OPF algorithm, it first selects N oldest packets from the queue & then schedules the packets to the respective user nodes. As it reduces the delay effectively, it is known to as delay optimality algorithm.

      Start

      Start

      nQ n Packet from

      maximum weight

      n clients

      G

      Construct Bipartite Graph G(xUy,E)

      ES Find the edgeset of

      Allocate Channel for ES

      Transfer Data

      Q All PAckets

      N Frame Packet Size

      Stop

      Fig. 3 Flow chart of MWF

      Is Frame No Time?

      QN Pick N oldest Packet from Q

      No

      Yes

      Is Q Empty?

      Stop

      Hybrid algorithm:

      It is the combination of both OPF and MWF policy. OPF is executed first and for remaining servers, MWF is executed. It is a class of two-stage hybrid policy which is both delay-optimal& throughput-optimal. In particular, we can adopt the OPF algorithm in stage 1; it runs an OPF policy over the N oldest packets and the Maximum Weight First (MWF) algorithm in stage 2 over the remaining servers, in order to design an optimal hybrid policy with a low complexity.

      Start

      Allocate Channel for Each Frame Packet

      Transmit Packet

      F Fill QN in Frame

      Fig. 2 Flow chart of OPF

      MWF algorithm:

      Here the packet from queue with maximum wait time is chosen and packet from that queue is processed at each iteration. It selects the packet from the queue with maximum wait time is chosen and the respective packet is scheduled to the respective user node. It is called to as throughput optimality algorithm because of its ability to improve the throughput.

      N No of Users S No of Servers Q All Packets

      Execute OPF(1) [dalay optimal]

      Exclude Allocated Servers

      Execute MWS on Remaining Server(2) [Optimal Throughput]

      Stop

      Fig. 4 Flow chart of Hybrid

2. RESULTS AND DISCUSSION

   In the proposed work, Linux (ubuntu) platform is used for implementation. Design &simulations were carried out using NS2 simulator. NS2 is a simulator intended for networking research and provides a substantial support for simulations of various protocols like multicast, routing and TCP protocols over wired (local) and wireless (satellite) networks. TCL is chosen as the programming language. We measure the maximum waiting time of the packet in each algorithm and draw a comparison graph.

   Fig. 5 Comparison of delay performance

   As shown above, the comparison of delay performance for different algorithms; OPF, MWF, Hybrid, Extended are studied. Simulations are performed for different number of users and evaluated. Here we have shown the results for 20 and 30 users. The respective delays obtained are shown in the below table.

   TABLE I

   COMPARISON OF DELAY PERFORMANCE FOR DIFFERENT ALGORITHMS

   Algorithms	Delay for 20 users (milliseconds)	Deay for 30 users (milliseconds)
   Oldest Packets First – OPF	1.4399	2.4599
   Maximum Weight First – MWF	1.6399	2.4599
   Hybrid (OPF + MWF)	1.1479	1.7220
   Extended	1.1479	1.7219

   Fig. 6 Comparison of throughput performance

   As shown above, the comparison of throughput performance for different algorithms; OPF, MWF, Hybrid, Extended are studied. Simulations are performed for different number of users and evaluated. Here we have shown the results for 20 and 30 users. The respective throughput performances obtained are shown in the below table.

   TABLE II

   COMPARISON OF THROUGHPUT PERFORMANCE FOR DIFFERENT ALGORITHMS

   Algorithms	Throughput for 20 users (bytes/second)	Throughput for 30 users (bytes/second)
   Oldest Packets First – OPF	69	41
   Maximum Weight First – MWF	79	53
   Hybrid (OPF + MWF)	101	100
   Extended	261	174

   OPF algorithm gives an optimal delay performance compared to the MWF algorithm. Since Hybrid algorithm is a combination of both OPF and MWF algorithms, both the delay & throughput performances are optimized. Hence, the results of Hybrid algorithm show minimum delay & maximum throughput when compared to all other algorithms. Finally, as an improvement for the Hybrid algorithm, Extension algorithm is derived. In Extension algorithm, combination ratio of OPF & MWF algorithms is varied so as to obtain better performance.

3. CONCLUSION

In the proposed work, we have developed low complexity scheduling algorithms that provide optimal performance of both delay and throughput in multichannel wireless networks. Simple appropriate conditions for delay and throughput optimality are derived & then allowed us to develop a hybrid algorithm that achieves both rate-function delay optimality & throughput optimality. Additionally, an extension to the Hybrid algorithm is introduced for the further performance enhancement& this is done by adjusting combination ratio of OPF & MWF algorithms. An important real time example of such a multichannel wireless network is the downlink of a single cell in 4G OFDM -based cellular networks like LTE and WIMAX technology.

REFERENCES

1. D. Shah, D. N. C. Tse, and J. N. Tsitsiklis, Hardness of low delay network scheduling, IEEE Trans. Inf. Theory, vol. 57, no. 12, pp. 78107817, Dec. 2011.

2. L. Tassiulas and A. Ephremides, Dynamic server allocation to parallel queues with randomly varying connectivity, IEEE Trans. Inf. Theory, vol. 39, no. 2, pp. 466478, Mar. 1993.

3. A. Ganti, E. Modiano, and J. N. Tsitsiklis, Optimal transmission scheduling in symmetric communication models with intermittent connectivity, IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 9981008, Mar. 2007.

4. S. Kittipiyakul and T. Javidi, Delay-optimal server allocation in multiqueue multiserver systems with time-varying connectivities, IEEETrans. Inf. Theory, vol. 55, no. 5, pp. 23192333, May 2009.

5. S. Kittipiyakul and T. Javidi, Resource allocation in OFDMA with time-varying channel and bursty arrivals, IEEE Commun. Lett., vol. 11, no. 9, pp. 708710, Sep. 2007.

6. M. Sharma and X. Lin, OFDM downlink scheduling for delay- optimality: Many-channel many-source asymptotics with general arrival processes, Purdue Univ., West Lafayette, IN, USA, Tech. Rep., 2011 [Online]. Available: https://engineering.purdue.edu/

   %7elinx/papers.html

7. M. Sharma and X. Lin, OFDM downlink scheduling for delay- optimality: Many-channel many-source asymptotics with general arrival processes, in Proc. IEEE ITA, 2011, pp. 110.

8. Bo Ji & Gagan R Gupta et.al, Low complexity scheduling policies for achieving throughput and asymptotic delay optimality in MWN, IEEE/ACM Transactions on Networking, 2013.

SREEVARUN M R received the B.E. degree in Electronics and Communication Engineering in East Point College of Engineering & Technology, Bengaluru, Karnataka, India from Visvesvaraya Technological University, Karnataka, India in 2013. Presently he is pursuing his final year M.Tech with specialization in Digital Electronics and Communication Engineering in Bangalore Institute of Technology (BIT), Bengaluru, Karnataka, India from Visvesvaraya Technological University, Karnataka, India. The proposed research work in this paper is part of his M.Tech thesis.

Dr. M N SREERANGARAJU received BE Degree in 1985 from Bangalore University and M.Tech in 1991 from University of Mysore both in Electronics Engineering, and PhD from VMU, Salem, TN, India in 2011.Professor of Electronics and Communication Engineering at Bangalore Institute of Technology (BIT), Bengaluru, India has been in Teaching UG and PG Students of Electronics and Telecommunication Engineering students for nearly Thirty Years. He has organized several National level conferences and workshops in this tenure. He has published his Research papers in Prestigious IEEE Conferences held in USA, China, Malaysia and Egypt. He also has served has Session Chair for several

National and International Conferences held in India and aboard. He also has served as editor of several journals and Magazine. He holds life member of ISTE, MVLSI, and IMAPS and also member of IEEE. His research interests include mobile and wireless communications and networks, personnel communication services and high speed communication routing protocols and wireless channel modeling for MANETS, VANETS.