Packet Scheduling Algorithms in Different Wireless Networks A Survey

Packet Scheduling Algorithms in Different Wireless Networks A Survey

Jaspher W. Kathrine Arun Raj

Assistant Professor SG, PG Scholar,

School of Computer Science and Technology, School of Computer Science and Technology, Karunya University, Karunya University,

Abstract

Wireless communications have become very pervasive over the time period. Developing packet scheduling algorithms in wireless networks can efficiently enhance delivery of packets through wireless links. Packet scheduling can guarantee quality of service and improve transmission rate in wireless networks. It is the process used to select which packet to be serviced or which to be dropped. This paper deals with various packet scheduling strategies in different wireless networks. Each wireless network has a different packet scheduling strategy and each has their own advantage and disadvantage. Most of the packet scheduling algorithm doesnt provide any sort of security. Only a few algorithms provide security but at the cost of schedulability so in this survey an algorithm which provides security by giving priority to schedulability is discussed

.

1. Introduction

   With the development of wireless technologies, wireless networks in recent years have been widely used in public places such as libraries, hotels, schools and airports due to the greater flexibility, increased efficiency, and reduced wiring costs [1]. Wireless networks refer to any kind of computer network that does not involve any cables or wires. It is a technique that helps industrialists and telecommunications networks to save the cost of cables for networking in specific premises in their installations. Implemented and administration of transmission station is done via radio waves [2]. This implementation is done at the physical level (layer) of the OSI model.

   1. Types of wireless networks

      Wireless networks are classified based on their size, their range and their speed of data transfer.

      1. Wireless Personal Area Networks (WPAN)

         WPAN interconnects devices in small area within the reach of a person, example infra-red and Bluetooth can connect a laptop to a headphone.

      2. Wireless Local Area Networks (WLAN)

         WLAN provides connectivity between a laptop and any other device that have Wi-Fi to an access point which can provide access to internet. OFDM or spread-spectrum technologies enable clients to move within a local coverage area while remaining connected to the LAN.

      3. Wireless Metropolitan Area Networks (WMAN)

         WMAN can connect high speed multiple wireless LANs that are geographically close. Two or more nodes can communicate with each other as if they belong to the same LAN by using WMAN.

      4. Wireless Wide Area Networks (WWAN)

         WWAN network usually covers large areas,

         i.e. connects different WLANS with the help of different cellular technologies such as LTE, WiMAX, CDMA, UMTS, and GSM. The speed of connection in such network depends on the cost of connection, which will increases with increasing distance. The most commonly available WWAN is internet [3].

         1. Packet Scheduling

            Packet scheduling refers to the decision process used to select which packets should be serviced or dropped. Dropping of packets will be based on

            network characteristics like bandwidth, packet arrival rate, deadline of packet and packet size. Scheduling will be done in scheduler. A scheduler will find it difficult to handle all the packets coming in if the packet rate is high, if the bandwidth is too low or the packet size is large. So the scheduler will select certain packets based on various algorithms. Some of these algorithms have been selected for this survey. Its not possible for every packet to reach at destination some may be dropped along the way due to the effect of network characteristics mentioned previously. It is an efficient method to enhance the system performance. Packet scheduling is mainly applied to guarantee quality of service, improve transmission rate in wireless networks [4].

         2. Wireless Security

            Data over a wireless network can be protected with the help of standard protocols such as Wired Equivalent Privacy (WEP), Wi-Fi Protected Access (WPA) and Wi-Fi Protected Access 2 (WPA2) [5].

            1. Wired Equivalent Privacy (WEP)

               Wired Equivalent Privacy (WEP) is a security algorithm developed for IEEE 802.11 wireless networks. Introduced in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network. WEP uses key of 10 or 26 hexadecimal digits and is often the first security choice presented to users by router configuration tools. WEP uses the RC4 cipher for confidentiality, and the CRC-32 checksum for integrity.

            2. Wi-Fi Protected Access (WPA & WPA2)

         Wi-Fi Protected Access (WPA) and Wi-Fi Protected Access II (WPA2) are two security protocols that are developed by the Wi-Fi Alliance to secure wireless computer networks. The Alliance defined these because of the flaws in the previous system, WEP (Wired Equivalent Privacy). WPA came into the picture by 2003. WPA2 became available in 2004 and is shorthand for the full IEEE 802.11i standard [6].

         This paper presents a study on different packet scheduling algorithms in different types of wireless networks. Section 2 describes various scheduling algorithms in different wireless networks and section 3 presents the conclusion of this paper.

2. Packet Scheduling Algorithms

   1. Packet Scheduling Using Bidirectional Concurrent Transmission in WiMAX Mesh Networks

      The objective of this paper is to propose a bidirectional concurrent transmission model and a packet scheduling problem to formulate centralized scheduling in WiMAX mesh networks which will effectively reduce the number of time slots required to transmit packets.

      Performance of wireless mesh networks can be improved by employing spatial reuse with concurrent transmissions. Spatial reuse is that several nodes transmit concurrently in the same channel without collisions. But most works on centralized scheduling for WiMAX mesh networks are based on a unidirectional concurrent scheme i.e., transmission of uplink and downlink are considered separately.

      This paper proposes a bidirectional concurrent transmission model and also put forth a packet scheduling problem to formulate centralized scheduling in WiMAX mesh networks with bidirectional concurrent transmission.

      Recent works on WiMAX mesh network, to maximize the throughput, minimize the end to end delay, and provide fairness to all stations consider unidirectional transmission. This is the first paper to propose bidirectional concurrent transmission [7].

   2. A Fair Scheduling Algorithm for Video Transmission over Wireless Packet Networks

      This paper proposes a fair-scheduling algorithm which delivers better performance in terms of the end-to-end delay experienced by the video frames. The system is based on the occupancy of the video decoder buffer. Various algorithms have been developed for wired networks which assumes, all users are experiencing same channel quality. This is not the same in a wireless network.

      Several algorithms have been proposed to address scheduling fairness in wireless networks all of them are aiming at maximizing the channel utilization. This is done by swapping the channels. This is usually done by allowing transmission of streams from users that are experiencing good channel conditions and preventing the transmision of users streams that are facing unfavourable channel conditions.

      In multi-media such as video streaming, this swapping of channel assignment may negatively affect the quality of the playback video for some mobile users. Therefore fair scheduling of multimedia applications is necessary. This paper proposes a base- mobile stations joint multi queue scheduling scheme that maintains a separate queue for each priority group

      and tries to optimize the performance of the high priority requests.

      The base station maintains multiple queues for the same session according to the importance of packets. The service order provided to each of these queues is based on the following

      • The decoder buffer occupancy at the mobile stations

      • The estimated channel state between a mobile station and the base station

      • Importance of the scheduled packet

      • Remaining time to expiry of the packet

      All of the previous algorithms which provide fairness are aiming at maximizing the channel utilization, by swapping channels. Multimedia streams have expiration times if past then packets become useless to the active playback session. So our proposed algorithm overcomes this disadvantage of previous algorithm by prioritizing the packets and discarding the low priority packets.

      Even though the algorithm tries to minimize the packet lose some packets will be discarded eventually. Another problem with this algorithm is that as new high priority packets arrives low priority packets will be discarded regularly this causes starvation of low priority packets. This algorithm lacks Security [8].

   3. A Packet Scheduling Algorithm for Max- Min Fairness in Multihop Wireless LANs Networks

      The objective of this paper is to propose a packet scheduling scheme achieving max-min fairness without changing the existing IEEE 802.11 medium access control (MAC) protocol. A probabilistic packet scheduling scheme achieving max-min fairness is proposed as number of nodes increases the overall throughput significantly degrades due to the hidden- node problem. To resolve this problem, the four way handshake is used but its not possible in multi hop communications.

      This paper focuses on throughput unfairness, in which the end-to-end throughput of a packet flow degrades significantly with the increase in the number of its transmission hops. Other scheduling schemes considered the improvement of fairness when the offered load is the same among all wireless nodes. This paper focuses on max-min fairness for heterogeneous networks. A packet scheduler is said to achieve max- min fairness when the minimum data transmission rate is maximized firstly, and the second smallest rate is maximized secondly.

      The proposed scheme aims to achieve max- min fairness without modification of the IEEE 802.11 MAC layer. Each wireless node achieves packets on a per-flow basis; packets in a flow are stored at a queue dedicated to the flow. When a wireless node is ready to send a packet, the packet scheduler of the node is likely to select the queue which has sent a small number of packets in a certain time. If the particular queue has no packet to transmit, the node defers the transmission by a fixed period. This gives the other nodes more likelihood to transmit their packets, some of which might be directed to the selected one. In other words, the node is likely to receive packets to forward while complying its own transmission. Therefore, a significant improvement in per-flow fairness is to be achieved.

      A heterogeneous scheduling scheme is being suggested. Unlike other schemes the proposed one will not modify IEEE 802.11 MAC sub layer. The proposed scheme can achieve higher per-flow fairness than the existing schemes. [9]

   4. A Packet Scheduling Algorithm for Optimizing Downlink Throughput in Wireless LANs with the One-Sender-Multiple-Receiver Technique

      This paper aims at providing maximum downlink throughput when packet fragmentation is not allowed. It deals with the packet scheduling problem in wireless LANs with the One- Sender-Multiple- Receiver (OSMR) transmission technique OSMR allows the Access Point (AP) to send distinct packets to multiple nodes simultaneously. It has a great potential in improving the network downlink throughput. The AP needs a packet scheduling algorithm to make the choice of when a packet should be sent and whether it should sent together with other packets using OSMR.

      This paper focus on the problem of maximizing downlink throughout when packet fragmentation is not allowed. Since the processor of the AP is not powerful and cannot execute complicated algorithms in real time a simple algorithm is being proposed. OSMR allows one sender to send to multiple receivers simultaneously, an access point (AP) can be an OSMR sender. If it uses multiple antennas it can form a Multiple-Input-Multiple-Output (MIMO) but it will be different from MIMO because MIMOs transmission is one-to-one OSMRs transmission is one-to-many.

      In order for the OSMR to work to its fullest a scheduling algorithm is needed. The main challenge is that only some pairs of nodes are compatible which means that the AP can send to them simultaneously with OSMR. The compatibility relations are

      determined by the channel states. Packet scheduling algorithms which was proposed for OSMR assumes nodes are at the same data rate and packets are of the same size. The proposed algorithm takes nodes to be of different data rates and the packets can be of different sizes. Before getting access to the medium, the AP inspects the packets in its buffer, and schedule one or multiple packets to send.

      In order to maximize the throughput, the AP should send out packets in minimum time AP first attempts to find an optimal schedule, with which the packets in the buffer can be sent in minimum time. The AP then selects one packet or a group of packets in this schedule and sends the selected packet. In a wireless LAN nodes may have different data rates and also packets may have dissimilar sizes. It is possible to use OSMR to send packets of different sizes to nodes at different data rates because the AP can make the signal to one node appear as zero at the other node, and vice versa. Performance of this scheme is better than the previous ones.

      Previous schemes assumed nodes are at the same data rate and packets are of the same size. The proposed algorithm takes nodes to be of different data rates and the packets can be of different sizes [10].

   5. A Novel SNR-based Packet Scheduling Algorithm and Compensation Model for Wireless Networks

      The main objective of this paper is to achieve better QoS for synchronous connections. A Signal- Noise-Ratio (SNR) based algorithm is being proposed this paper proposes an Improved SNR-based Packet Scheduling (I-SPS) algorithm. In this algorithm connection with better channel condition will be assigned higher weight in scheduling and the connection suffered from burst error will be provided with higher weight after its channel condition becomes good. The proposed algorithm adaptively controls the service allocation in accordance with the signal-to- noise (SNR) fluctuation. The key point of the scheduling algorithm is dynamic adjustment of the weight of each connection according to current channel state.

      In the proposed I-SPS, the weight of each connection is a variable and the connection with better channel condition will be assigned higher weight in scheduling. The connection suffered burst errors will be compensated by increasing its weight after its channel recover. The proposed algorithm can easily adapt to load varying wireless channel conditions [11].

   6. A Mobile-Sink-Based Packet Transmission Scheduling Algorithm for Dense Wireless Sensor Networks

      This paper aims at developing an algorithm which is power efficient for transmission scheduling and which provides higher packet transmission rate for networks with higher node densities. This paper proposes a ransmission scheduling algorithm for wireless sensor networks with high node densities. A mobile sink is responsible for gathering the data from the sensor nodes. Proposed algorithm is based on the trade-off between the energy consumption and the probability of successful packet arrival at the sink.

      One of the most challenging issues in WSNs is energy required by the sensor node. Often energy will be provided by exhaustible energy source so many methods which will reduce the consumption of energy are often proposed. Multihop packet transmission is one such method, in which the packet to be transmitted from a sensor is relayed by the nodes located at a shorter distance from the sink. Its not efficient when more realistic models are taken into account. This paper proposes a transmission scheduling algorithm for dense wireless sensor networks.

      The algorithm uses multiple sensors for transmitting the data packets to the sink. Proposed algorithm considers all of the sensor nodes together instead of considering individual nodes at each time slot in order to assign the transmitting nodes and their transmission power levels. Moreover, a realistic assumption is taken into account where the packets transmitted from the sink are also subject to errors caused by the wireless link between the mobile sink and the nodes.

      Proposed algorithm shows better performance in dense WSN. Proposed algorithm transmits the data collected based on the power consumption of nodes. A more realistic approach is taken where similar observations will be considered and only one of the data will be sent [12].

   7. An Improved Security Aware Packet Scheduling Algorithm in Real-Time Wireless Networks

      The objective of this paper is to design dynamic security mechanisms for real-time applications on wireless networks. This paper presents an Improved Security-Aware Packet Scheduling algorithm (ISAPS). ISAPS is able to adaptively determine the security levels of packets according to the system workload.

      All of the above mentioned papers only talks about packet scheduling. But this paper provides security along with scheduling. This paper proposes a dynamic algorithm which can increase and decrease security levels based on the load coming on to a node.

      Under light load ISAPS strives to increase security of incoming packets and under heavy load ISAPS gives priority to scheduling rather than security. ISAPS is based on a scheduler model, which consists of a real-time controller, schedule queue, accepted queue, rejected queue and a security level controller.

      Real time controller considers both the new packet and packets waiting in the accepted queue to maximize the schedulability. When a new packet is placed in accepted queue the security level controller strives to increase the security level of packets efficiently. New packets are put in scheduler queue and assigned low security level. Real time scheduler gets a new packet from scheduler queue based on earliest dead line first.

      Existing algorithms doesn't provide security. The Proposed algorithm makes sure that schedulability is attained along with security. Under narrow bandwidth ISAPS can accept only a few packets. ISAPS improves schedulability but security will be degraded, no specific Security algorithm is mentioned. This algorithm is not specific for any particular wireless networks; this algorithm is defined as a common algorithm that can be applied to any wireless networks [5].

3. Conclusion

   Wireless networks provides more convenience, ease of use and easy maintenance than traditional wired network, the main threat that wireless network posse is security. In this survey various packet scheduling algorithms have been evaluated. Each algorithm aims at providing different QoS parameters such as maximizing fairness, minimizing end-to-end delay, maximizing throughput and successful packet transmission.

   Packet Scheduling Using Bidirectional Concurrent Transmission in WiMAX Mesh Networks proposes a bidirectional concurrent transmission model and a packet scheduling problem to formulate centralized scheduling in WiMAX mesh which can effectively reduce the number of time slots for transmission [7]. A Fair Scheduling Algorithm for Video Transmission over Wireless Packet Networks deals with a fair-scheduling algorithm which delivers better performance in terms of the end-to-end delay experienced by the video frames [8]. A Packet Scheduling Algorithm for Max-Min Fairness in Multihop Wireless LANs Networks proposes packet

   scheduling scheme achieving max-min fairness without changing the existing IEEE 802.11 medium access control (MAC) protocol [9]. A Packet Scheduling Algorithm for Optimizing Downlink Throughput in Wireless LANs with the One-Sender-Multiple-Receiver Technique aims at providing maximum downlink throughput when packet fragmentation is not allowed [10]. A Novel SNR-based Packet Scheduling Algorithm and Compensation Model for Wireless Networks aim to achieve better QoS for synchronous connections. This paper proposes an Improved SNR- based Packet Scheduling (I-SPS) algorithm [11]. A Mobile-Sink-Based Packet Transmission Scheduling Algorithm for Dense Wireless Sensor Networks aims at developing an algorithm which is power efficient for transmission scheduling and which provides higher packet transmission rate for networks with higher node densities [12]. But none of the algorithms focuses on providing security. An Improved Security Aware Packet Scheduling Algorithm in Real-Time Wireless Networks aims at providing security, and at the mean time provides schedulability. This algorithm is a dynamic scheduling algorithm which can able to increase or decrease security levels based on system load. Under heavy load IASPS strives to improve schedulability rather than security [5].

4. References

1. T. Karygiannis, L. Owens, Wireless Network Security 802.11, Bluetooth and Handheld Devices, NIST Special Publication 800-48, Nov. 2002.

2. http://www.wifinotes.com/wireless-networks.html

3. What is Wimax Technology (IEEE 802.16)

4. www.isi.edu

5. Xiaomin Zhu , Hao Guo, Shaoshuai Liang, Xiaoling Yang, An improved security-aware packet scheduling algorithm in real-time wireless networks, Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, PR China.

6. en.wikipedia.org

7. Qing Xiong, Weijia Jia, Chanle Wu, Packet Scheduling Using Bidirectional Concurrent Transmission in WiMAX Mesh Networks, School of Computer, Wuhan University, Wuhan, P. R. China.

8. M. Hassan, T. Landolsi, M. Tarhuni, A fair scheduling algorithm for video transmission over wireless packet networks, in: Proc. the IEEE/ACS Intl Conf. Computer Systems and Applications (AICCSA 2008), Mar.Apr. 2008, pp. 941942.

9. W. Kensaku, K. Shoji, T. Yutaka, K. Yoshinobu, I. Eisaburo, A packet scheduling algorithm for max-min fairness in multihop wireless LANs, Comput. Commun. 32 (2009) 14371444.

10. Z. Zhang, S. Bronson, A packet scheduling algorithm for optimizing downlink throughput in wireless LANs with the one-sender multiple-receiver technique. in: Proc. the 28th IEEE Conf. Global Telecommunications (GLOBECOM 2009), Dec. 2009, pp. 16.

11. H. Liu, Y. Wang, J. An, A novel SNR-based packet scheduling algorithm and compensation model for wireless networks, in: Proc. the 4th Intl Conf. Wireless Communications, Networking and Mobile Computing (WiCOM 2008), Sept. 2008, pp. 14.

12. A. Sharifkhani, N.C. Beaulieu, A mobile-sink-based packet transmission scheduling algorithm for dense wireless sensor networks, IEEE Trans. Veh. Tech. 58 (5) (2009) 25092518.