Service Prioritized Opportunistic Scheduling Algorithm for WiMAX Mobile Multi-hop Relay Networks

Service Prioritized Opportunistic Scheduling Algorithm for WiMAX Mobile Multi-hop Relay Networks

D. M. S. Madhuri1, Reethu Dasari2, K. Mani Chandana 3, T. A. V. S. S. N Raju 4

1 Assistant professor, Department of IT, Lendi Institute of Engineering and Technology, Andhra Pradesh, India 2student, Department of IT, Lendi Institute of Engineering and Technology, Andhra Pradesh, India 3student, Department of IT, Lendi Institute of Engineering and Technology, Andhra Pradesh, India 4student, Department of IT, Lendi Institute of Engineering and Technology, Andhra Pradesh, India

Abstract In recent years, there has been great interest in Relaying and cooperation ,they were re-emerged as important research topic in wireless communication, Although multi-hop relaying for coverage extension in wireless networks is an old concept, it became practical only recently. In this we explore the difficulty of scheduling in (orthogonal frequency division multiple-access) OFDM-based multi-hop relay networks, on special bases of IEEE 802.16j WiMAX relay networks. Scheduling has been a very great problem in such type of networks for providing user specific services on allocation of bandwidth at a particular instance of time, on that give sub- channel. In the existing system the author proposed Eliminate- repeat algorithm for such relay problem, still there are fairness constraints in the existing system, so to overcome these constraints we are proposing the Service Prioritized opportunistic scheduling algorithm. In this algorithm we increase the fairness by allocating the bandwidth based on the user service differentiations where the services are provided by the user that will decrease great delays and starvations.

Keywords IEEE 802.16j, WiMAX, Scheduling, Quality of Service, Mobile Multi-hop Relay (MMR)

1. INTRODUCTION

   The Internet usage through broadband access have became massive in present scenario, the wireless industry does not have the substantial share with broadband access market, to substitute this issue IEEE 802.16 standard has been initiated for wireless broadband system access. The main target of

   802.16 is to provide a comprehensive set of specifications of the air interface.

   IEEE 802.16j standard provides the WIMAX (Worldwide Interoperability for Microwave Access) technology that is deliberated for "metropolitan area networks (MAN) in the wireless technology. The WIMAX technology ensures high data rates up to 70Mbps; it supplies broadband wireless access (BWA) up to 30 miles (50 km) in the case of fixed stations, and 3 – 10 miles (5 – 15 km) for mobile station [1].WiMAX employs on both licensed frequencies and non licensed frequencies. The average cell ranges for most WiMAX networks will basically have 4-5 mile range (in NLOS capable frequencies) even through large obstacles and building walls. Service ranges up to 10 miles (16 Kilometers) in line of sight

   (LOS), the major problems in WiMAX networks is the existence of dead spots or coverage holes, formed due to obstacles (buildings, trees, etc.) and signal fading. In order to serve the isolated area of the coverage holes and signal fading, large frequent arrangement of base stations (BS) are to be considered so that it may considered as expensive approach, to make it cost efficient relay stations (RS) are substituted in case of multiple BSs, these relay stations provide the basic functionality needed for relaying signals between the BS and subscriber stations (SS) or Mobile station (MS) shown in (Figure-1). Initiation of relay stations in WiMAX network can

   Seriously improvise the quality of wireless links leading to throughput enhancements and extended network coverage. A basic WiMAX network together with relay stations is referred to as a WiMAX Mobile Multi-hop Relay (MMR) network [1].

   (Figure-1 A Typical IEEE 802.16j WiMAX network)

   The Wireless MAN-OFDM and the Wireless MAN-OFDMA physical layer interfaces provide for 256 and 2048 orthogonal sub-carriers, respectively [2].Based on requirements or the user requests, they make allocation of subcarriers to users easier, and these sub-carriers are grouped into multiple sub- channels. [1][2] In an OFDM system, scheduling of user request can be done by determining who should serve at and given instant of time and on a given sub-channel.

   A. Main Contributions:

   Our important contributions of over paper are:

   1. Identify the drawbacks of Eliminate Repeat algorithm: In the existing system Eliminate Repeat Algorithm The main drawback that rests with it is all tiles are not allocated properly according to the user requirements so that there exits the bandwidth starvation, and even delay is increased, and the bandwidth is also wasted. There lies another problem with the existing system i.e., it goes in continues looping condition, so that there arises a problem with the termination of the algorithm.

   2. Fairness up gradation for better allocation of tiles:

      In the proposed system the fairness improvisation is done by allocating the minimum time slots to all the user requests and can improve the maximum utilization of Bandwidth.

   3. Prioritized allocation of bandwidth:

      The allocation of time slots left after the minimum timeslots allocation can be done based on the user data request, based on the data priority the allocation of rest time slots can be done.

   4. Maximum throughput is attained:

   Maximum throughput is attained as there was maximum utilization of bandwidth and timeslots are considered and scheduling frame that is reconstructed for every 5ms so that there will be maximum throughput and less bandwidth starvation and can achieve maximum Quality of service.

2. BACKGROUND:

   In this section, we present the background necessary to Understand the problem we consider in this paper. We briefly Look at the previously proposed algorithm Eliminate-Repeat to solve this problem, and note its drawbacks.

   1. Scheduling:

      Scheduling is the process of determining which user should be serviced at a given instant of time and on a given sub-channel. scheduling can be done by padding the 2-Dimentional array which is called as Scheduling frame(figure 3), constructed with the size of CxN( Here the C is considered to be no of sub-channels and N as number of time-slots) , The union of these two parameters (sub-channels and timeslots ) referred as a Tile. Scheduling involves filling up each tile of a scheduling frame with a subscriber station that should be serviced in the time-slot and using the sub-channel associated with that tile [1]. All these scheduling process can be done using scheduling algorithms, in this process we are using Prioritized opportunistic scheduling to allocate tiles and sub- channels.

      In [1] the author proposed Eliminate repeat algorithm, in the existing system the allocation of time slots to the user was random. Based on the number of users in the hops the time slots and the sub-channels are divided and they were allocated randomly for the user request.

      In [3] the authors propose a heuristic opportunistic scheduling Algorithm they call Gen Arg Max for OFDM relay

      networks. Gen Arg Max is multi-hop version of the proportional fair scheduling algorithm that allow multiuser diversity and frequency selectivity by opportunistically allocating different sub-channels on each link of the multihop path from BS to Subscriber station(SS) [1].

      The different types of data services offered are:

      UGS, RTPS, NRTPS, ERTPS, BE, based on these types of data the scheduling job is performed.

      The IEEE 802.16 Medium Access Control (MAC) stated ve types of QoS classes: Unsolicited Grant Service (UGS),

      Real-time Polling Service (rtPS), extended real-time Polling Service (ertPS), non real-time Polling Service (nrtPS), and Best Effort (BE) QoS classes.

      UGS: This supports real-time service follows that have xed- size data packets on a periodic basis.

      RtPS: This supports real-time service follows that generate variable data Packets size on a periodic basis.

      ErtPS: This service built on the efficiency of both UGS and rtPS. The BS provides unicast grants in an unsolicited manner like UGS. Whereas the UGS allocations are xed in size, the ertPS allocations are dynamic.

      NrtPS: It is designed to support non real-time service follows that require variable size bursts on a regular basis.

      BE: It is used for best effort traffic where no throughput or delay guarantees are provided. Those service classes are dened in order to satisfy different types of Quality of Service (QoS) requirements.

      However, the IEEE 802.16 standard does not specify the scheduling algorithm to be used. [4]

   2. Scheduling Constraints:

   While a scheduling algorithm tries to optimize its desired Objective function, it may also have to work within the Constraints imposed by the system. Some of these constraints in a WiMAX MMR network are [1]:

   1. Decode-and-Forward Relay (DFR) Constraint:

      All the data that a relay station receives in one scheduling frame is also sent out during the course of the same scheduling frame.

   2. Transmit-Receive (TR) Constraint:

      If a relay has a single transceiver, it cannot transmit and receive concurrently. This constraint requires that a relay node cannot be transmitting on any sub-channel over any of its child links while it is receiving a packet on any sub channel over its parent link

   3. Spectrum Sharing (SS) Constraint:

      Finally, the spectrum sharing constraint states that, in a given time slot t, a sub-channel can only be used by one link. This constraint is required to totally avoid intracell interference [2].

   4. Single Transmitting Node on all Sub-channels of a Time Slot (STS) Constraint:

      In a given time slot, only one of the relay stations (or the base station) can transmit on all the sub-channels.

   5. Low Runtime Complexity (LRC) Constraint:

   Our proposed scheduling algorithms have an average running time of less than 0.05 ms, and are therefore suitable for typical WiMAX scheduling frame durations of 5 10 ms.The

   scheduling algorithms runtime complexity should be low to compute a scheduling frame once in 5 ms.

3. THE ELIMINATE REPEAT ALGOIRTHM:

   The author in the existing system [1] described that the network model consists of a single sector in a WiMAX cell, with single base station, multiple relay stations and subscriber stations and they consider MAC downlink scheduling in a 120o sector of a WiMAX cell.

   The working scenario of Existing system:

   1. The time slots in a scheduling frame are divided into multiple segments, so that links in the path from base station to user lie in different segments. That is, all links in the first hop of the routing tree can only lie in segment 1, all links in the second hop of the routing tree can only lie in segment 2, and so on[1]

   2. After constructing the schedule frame as per the user request the in the sequence the time slots will be allocated to each user until the time slots are available, rest of the user request will be eliminated and they the eliminated requests can be considered in the construction next schedule frame.[1]

   A. Drawbacks of Eliminate Repeat algorithm:

   Claim 1: In the existing system the tiles are allocated sequentially:

   In eliminate repeat algorithm it was specified that the tiles of timeslot and sub-channels are allocated sequentially without any priority. So that it does achieve maximum throughput.

   Claim 2: Fairness factor is less considered:

   In the existing system the tiles are allocated without considering the fairness factor all the user requests are not served, by that the starvation for the bandwidth is untainted.

   Claim 3: Wastage of tiles and delay is more:

   As it is begin allocated randomly to the user some tiles are not filled and the tiles which are left free were not recovered again so the wastage of tile and the bandwidth is more, and large number of requests are in delay.

4. PROPOSED ALGORITHM:

   1. System Characteristics:

      In the proposed system we follow the basic WiMAX architecture as shown in figure 2 which depicts the routing path between the base station and subscriber stations through intermediate relay stations.

      (Figure-2 Architectural design of WiMAX)

      In the architecture we have single Base station and multiple number of Relay stations and multiple number of Subscriber stations(SS)or Mobile station(MS) , For a simple scenario we have considered three hop architecture ,each hop may have n number of RS and m number of(SS), but the end user will always be a subscriber station as shown in (figure-2).The Base station schedules the user request , the relay station relays the signals to the subscriber station without any loss of data, the relay station does not perform any scheduling tasks.

      1. As the scheduling frame construction of proposed system is to existing system we refer to [1] we shell follows the outline of centrally controlled relay stations. Here the major work of the base station is to schedule for all the subscriber stations which are in considerations of both relay station and the subscriber station

      2. We assume the use of contiguous permutation mode for aggregating sub-carriers into sub-channels. In this mode, a sub-channel consists of adjacent sub-carriers. [1]

      3. The routing tree was set by the routing algorithm The BS has information of the maximum Achievable data rates each links of the routing tree, on each sub-channel c for bits in each timeslot.

      4. As it provides or constructs the scheduling frame for every 5ms by the base station the subscriber stations need not waiting for the long time and more number of user can be served

      5. LOS services the direct communication between BS and SS can be possible and NLOS which is facing major problems with the coverage holes and signal fading can also be communicated without any loss of data.

   2. Service Prioritized Opportunistic Algorithm:

   In this proposed system we are going to overcome the drawbacks of the existing system (Eliminate repeat), its backdrops claim3 and claim2 will be recovered with the best remedy in the proposed algorithm.

   Algorithm:

   Algorithm Eliminate-Repeat with service prioritization fixes the infinite loop problem in Gen Arg Max-A and reclaims Type-1 tiles wasted by Gen Arg Max-B. We borrow the algorithm listing from [1], modify it to fix its drawbacks. This algorithm works as follows:

   Step 1 – Divide slots in a scheduling frame (figure 3), into multiple segments:

   In this time slots in the scheduling frame are split into H segments. That is, there is one segment per hop of the routing tree. The number of time-slots reserved for each segment is in the ratio of the number of users that need to use links in that hop. For example, if all the 11 users would have to use links in the first hop, 9 users (m3 to m11) would have to use links in the second hop and only 6 users (m6 to m11) would have to use links in the third hop. So, the slots in the scheduling frame are divided into 3 segments in the ratio 11/26, 9/26 and 6/26. Deviating from Gen Arg Max, we allocate any remaining slots to segment 1 for the reason that we can use these extra time slots in serving users that are directly associated with the base station. If instead we allocate these extra time slots to the

   segmets, they may not be used up in the case when the slots in segment 1 are exhausted before the slots in other segments.

   Step 2 – Select eligible users:

   In this step (lines 5-10), all but the eligible users are eliminated from consideration for scheduling. A user m is considered eligible if, on the last hop link to this user, the user has the largest value of ri(c,t) Ri(t) for some sub-channel c, among all its siblings. This is an important step that makes the algorithm scalable. We denote this list of eligible users by Mc.

   Step 3 – Select the most eligible user:

   In this step (lines 11-34), from among the eligible users (i.e., the users in Mc), we choose the most eligible user as follows: Step 3a: Eliminate users who cannot be serviced for lack of free tiles in any of the segments corresponding to the multihop path from the base station to this user.

   Step 3b: For each user, for each link in the path from the user to the base station, calculate the number of tiles we need to use on this link (using the best available subchannel), so as to increment the objective function (F) by 1 unit, by only serving this user.

   Step 3c: Take the maximum of the value calculated in Step 3b. This serves as the number of tiles required to service this user so as to increment F by 1 unit.

   Step 3d: Choose the user with the minimum value calculated in Step 3c.Mainly we try to improve the fairness by prioritizing the user requests based on services and eliminate wastage of transmission opportunities thereby providing significant increase in system throughput.

   Step 4 – Allocate tiles to the selected user:

   In this step for the user chosen in Step 3d, we allocate the maximum number of free tiles possible, on all the segments corresponding to the multihop path from the user to the base station

   Step 5 – Termination:

   In this step (line 11), we repeat Steps 3 and 4 as long as there is some free tile available in segment 1 of the scheduling frame and there is at least one user in Mc.Repeating steps 3 and 4 only till there is some user in Mc, is an important new step in our algorithm that eliminates the infinite loop problem we noted in Gen Arg Max-A. Note that there has to be some free tile available in segment 1 to be able to schedule any user. As a result, we do not continue in the case when there is no free tile in segment 1, regardless of whether some other segment has a free tile. This is an improvement over Gen Arg

   Max [5].

   By this through the proposed scheduling algorithm we increase the fairness by allocating the bandwidth based on the user service differentiations for corresponding user request in order to provide Enhanced throughput and optimum fairness thereby we can reduce the greater delays and starvation..

   (Figure 3 Sample scheduling frame with allocation of tiles)

5. PERFORMANCE EVALUATION:

   In this section, we present simulation results to show the effectiveness of the proposed algorithm (Table 1). The goal of this section is to quantify the increase in system throughput offered by our algorithms in comparison to algorithm Eliminate-Repeat and to show that the running times of these algorithms are small enough to be used for downlink scheduling in WiMAX MMR networks(Table 2,3).

   1. Simulation Setup:

      In this section, we present various aspects of the simulation Study we conducted using our custom simulator.

      Network Topology: As in we simulate downlink

      Scheduling in a single 120o sector of a WiMAX cell of radius 1 km. We try to match the simulation setup in as closely as possible. We borrow relevant simulation parameters (Table 1) from [3]. We present our results for 3-hop networks. For the 3- hop scenario, we place 2 and 3 relay stations on arcs of radii

      0.6 km and 0.8 km respectively. We consider 25 users waiting to be serviced at the base station. To simulate uniform distribution of users in the network, we apportion the users to different hops in the ratios of the area serviced by relay stations (or base station) at each hop.

      Link Characterization: In our model, as in [3], we divide the available channel bandwidth into five sub-channels. To characterize the effects of path loss and frequency-selective

      fading on the wireless links, we first calculate the maximum sub-channel capacity (MSC) possible in our setup. This is given by sub-carrier bandwidth x number of sub-carriers per sub-channel x spectral efficiency. This amounts to 1575 Kbps or 164 bits per time-slot in a 24-slot scheduling frame of duration 5 ms.

   2. Simulation Results:

   We present results for 3-hop networks. For each of these scenarios, we ran simulation on 100 random topologies. These topologies differ in terms of which subscriber station is associated with which relay station. These topologies also differ in the capacity of the links in the network.

   	3-hop network Throughput
   	Prioritized	Fairness included prioritized	Random prioritized
   Topology 1	3.73	3.64	3.82
   Topology 2	3.60	3.72	3.84
   Topology 3	4.21	4.29	4.36
   Topology 4	4.11	4.20	4.32

   Table 2: Summary of System Throughput

   Figure 4: System Throughput metric for 3-hop Network

   Different type of services->	Delay for 3 hop Network
   	UGS	RtPS	ErtPS	NrtPS	BE	AVG
   Topology1	2.32	3.10	3.26	4.12	4.23	3.406
   Topology2	2.43	3.26	3.67	4.23	4.34	3.586
   Topology3	2.66	3.56	3.78	4.45	4.68	3.826
   Topology4	2.90	3.82	4.32	4.63	5.20	4.174

   Table 3: Summary of Delay

   Figure 5: Delay with respect to different types of services for 3-hop Network

   Figure 6: Delay with respect Existed and Proposed algorithm.

6. RESULTS:

   In our project, as we have mentioned earlier we have enhanced the fairness and throughput. As a part of this we reduced the delay between successive transmissions. As we have allocated bandwidths dynamically as per the request of service classes, appropriate bandwidths are allocated and the service flows are scheduled in lesser time reducing the delay and increasing the throughput. This delay reduction between rounds can be observed in the figure 7, figure 8 that are generated by us.

   Figure 7: Generated Result

   Figure 8: Generated Result

7. CONCLUSION:

DDDd

We studied the problem of proportional fair scheduling in WiMAX MMR networks.In this Implementation the bandwidth is allocated to every domain then we process the request based on the user service differentiations through scheduling services that will decrease great delays and service starvation. We showed that our proposed algorithms provide significantly higher system throughput while maintaining proportional fairness to individual users. Our algorithms have runtimes of less than 0.05 ms making them suitable for downlink scheduling in WiMAX MMR networks where a scheduling frame has to be constructed once in 5ms.Further motivation is to develop a better throughput and lesser delays for N-hop network scenario and t deliver different Quality of Services.

REFERENCES:

1. Srinath Narasimha, Krishna Moorthy SivalingamImproved Opportunist Scheduling Algorithms forWiMAX Mobile MultihopRelay Networks.

2. IEEE. (2005) IEEE 802.16e-2005 – IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands. [Online].

   Available:http://standards.ieee.org/getieee802/download/802.16e-2005

3. Supratim Deb, V. Mhatre, and V. Ramaiyan, WiMAX Relay Networks: Opportunistic Scheduling to Exploit Multiuser Diversity and Frequency Selectivity.

4. Comparison of WiMAX scheduling algorithms and proposals for the rtPS QoS class

5. Ashish Jain and Anil K. Verma SCHEDULING ALGORITHMS IN WIMAX

BIOGRAPHIES

D.M.S.MADHURI,

ASSISTANT PROFESSOR, DEPARTMENT OF IT, LENDI INSTITUTE OF ENGINEERING AND TECHNOLOGY

D.REETHU,

STUDENT FROM DEPARTMENT OF IT,

LENDI INSTITUTE OF ENGINEERING AND TECHNOLOGY

K.MANI CHANDANA, STUDENT FROM DEPARTMENT OF IT,

LENDI INSTITUTE OF ENGINEERING AND TECHNOLOGY

ACKNOWLEDGEMENT

T.A.V.S.S.N.RAJU, STUDENT FROM DEPARTMENT OF IT,

LENDI INSTITUTE OF ENGINEERING AND TECHNOLOGY

We express our sincere and profound gratitude to our principal Dr.V.V.Rama Reddy, management members our chairman Sri P.Madhusudhana Rao, Vice-chairman Sri P.Srinivasa Rao and Secretary Sri K.Siva Rama Krishnan for their valuable support and guidance.

This Implementation of our project is possible only because of the support of my college (Lendi Institute of Engineering and Technology) Management and my guide Mrs.D.M.S.Madhuri. and Faculty members. They gave support by providing all facilities and helped us in various aspects.