mac scheduling algorithms in bluetooth ad-hoc network：mac调度算法在蓝牙ad hoc网络

MAC Scheduling Algorithms in Bluetooth Ad-Hoc Network,Mukund Sarangapani2147505EEApril 24, 2008,“Bluetooth” is a wireless specification for PAN offering short range radio communication operating at 2.4 GHz Industrial Scientific Medical (ISM) frequency band capable of establishing ad-hoc network referred to as piconet 3.,TECHNOLOGY DEFINITION,2,ABSTRACT,Bluetooth implements different algorithms at various stages such as device discovery and connection establishment, data traffic flow.Following presentation would compare a number of MAC scheduling algorithms that aims to improve asymmetric data traffic over a point-to-multipoint Piconet topology and study the performance impact of data traffic due to circuit switched voice.,3,PRESENTATION OUTLINE,1. Introduction 2. Architectural Framework and Topology study 3. Modulation and Access Technique 4. Addressing 5. Connection Establishment and Types of Links 6. Scheduling Algorithms 7. Conclusion and Further study,4,INTRODUCTION,Bluetooth provides a universal bridge to existing data networks. Objective of the Bluetooth Specification - “Interoperability” : client and server applications to run over identical protocol stacks. - Support adhoc connectivity. - Save power (using less power in host devices in which Bluetooth is introduced).FEATURES OF BLUETOOTH - Data and Voice support - Use of Frequency hopping technique - Full Duplex Transmission - Master Driven Time Division Duplex (TDD) scheme implementation at Medium Access Layer (MAC) layer - Handling of large data packets Segmentation and Reassembly (SAR) - Support for Automatic Repeat Request (ARQ) and Forward Error Correction (FEC) schemes,5,ARCHITECTURAL FRAMEWORK,Modified: Pravin Bhagwat, Bluetooth: Technology for Short-Range Wireless Apps, IEEE Internet Computing, May/Jun 2001,STACK LAYERSRadio: Defines frequency bands, permissible transmit power. Baseband: Defines MAC processing Framing, Timing, Flow control. Tasks Device discovery, Synchronous and Asynchronous communication with peers.LMP: Defines control message to manage baseband connections.,FIG 1. BLUETOOTH PROTOCOL STACK,6,ARCHITECTURAL FRAMEWORK(CONTD),Link Manager : Carries LMP related processing.HCI : Defines a way to communicate with the Bluetooth chip. Use of HCI commands for hosts software stack to communicate with Bluetooth hardware. L2CAP(link layer) : Delivers packet received from higher layers to other end of link. Supports SAR. Use LMP to control Link Manager.SDP : Client devices discover service provided by Server devices.RFCOMM : Support applications that use COM port to communicate with peers.PPP : Provide packet oriented service to higher layers. Network and transport protocols can be supported on top of PPP.,7,TOPOLOGY STUDY,Fig 2. POINT TO POINT PICONET Fig 3. POINT TO MULTIPOINT PICONET Modified: Robert Marrow, “Bluetooth Operation and Use”, McGraw Hill, 2002, Chapter 1,Two types of Bluetooth Network : Piconet and ScatternetPiconet : (Point-to-Point) and (Point-to-Multipoint)-Master: a device that initiates the communication link with other devices.Slave: a device that accepts invitation from Master. A Point to Multipoint Piconet can have 1 Master and 7 active Slaves.,8,TOPOLOGY STUDY(CONTD),Scatternet : Group of piconets interconnected through a bridge node. - Communication across piconets realised when a device act as Slave in more than a piconet. act as Master in one piconet and Slave in another. - 10 piconets can co-exist in a bluetooth radio environment.,Fig 4. SLAVE AS BRIDGE NODE SCATTERNET Fig 5. MASTER / SLAVE AS BRIDGE NODE - SCATTERNET Modified: Robert Marrow,“Bluetooth Operation and Use”, McGraw Hill, 2002, Chapter 1,9,MODULATION,Gaussian Frequency Shift Keying (GFSK) Uses an FSK system where the data is filtered by a Gaussian filter whose 3 dB bandwidth is 0.5 times the data rate.ADVANTAGES OF GFSK- Constant envelope, allowing high RF amplifier efficiency- Adjacent channel interference is minimized Good bit error rate (BER) performance Fig 6. Bluetooth Modulation Scheme Modified: /products/signalsources/signalgens/appnotes/892.pdf,10,MODULATION(CONTD),MODULATION CHARACTERISTICSSymbol rate: 1 Ms/s ; Bit rate: 1 Mb/sFREQUENCY HOPPING SPREAD SPECTRUM(FHSS) COMMUNICATION-Definition: Transmit signals by frequently changing carrier among many frequency channels, using a sequence (generated by pseudorandom hop generator) known to both transmitter and receiver. Change carrier frequency at a rate of 1600 hops per second. Operates on a frequency set (channel set) consisting of carrier frequencies(f_c) fc = 2402 + k MHz , k = 0,1,2, 78Devices to communicate should be: Time synchronised within hopping sequence, use same channel set, same hopping sequence within the channel set.,11,ACCESS TECHNIQUE,Fig 7. TDD scheme: Single-Slave operation From: /lecture/bluetooth/bt_primer.pdf,-Modulation scheme uses Time Domain Duplex (TDD) access technique. -TDD use electronic transmit/receive switching to transition faster between transmit and receive operating in a single frequency.SINGLE-SLAVE OPERATION (POINT-TO-POINT)-Time slots usually 625 microseconds in length: 366 microseconds to transmit a packet, next 259 microseconds to change to next frequency in hop sequence.- Each transmission takes place at a new hopping frequency. - Complete packet of data sent in each time slot.,12,ACCESS TECHNIQUE(CONTD),Fig 8. TDD scheme: Multi - Slave operationFrom: Baatz, S.; Frank, M.; Kuhl, C.; Martini, P.; Scholz, C., Bluetooth scatternets: an enhanced adaptive scheduling scheme, INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol.2, no., pp. 782-790 vol.2, 2002,MULTI-SLAVE OPERATION(POINT-TO-MULTIPOINT) A Slave can transmit only when it is specifically addressed by a Master in previous time slot. Slaves keep receiver On to decode packet by checking the packet access code (to identify Piconet) and header (to identify destination). Slaves turn Off their receiver after decoding and waits for the beginning of next Master transmit time slot. Hence its a “Power Efficient” technique.,13,ADDRESSING,ADDRESS TYPES Bluetooth device address (BD_ADDR) - 48 bit address unique to each bluetooth device. Three Fields -Lower Address Part (LAP) and Upper Address Part (UAP): Identify Piconet, Paging devices, generate frequency hop channel set. - Non significant Address Part (NAP): Bluetooth Security. - UAP+NAP: Defined as Organisationally Unique Identifier(OUI).Active member address (PM_ADDR) - 3 bit address assigned by Master to Slaves as they enter the piconet. - (001-111) ADDR value assigned to 7 active Slaves; (000) ADDR value reserved for broadcast packet from Master to multiple Slaves.,14,ADDRESSING(CONTD),Parked member address (PM_ADDR) - PM_ADDR assigned by Master to unpark Slaves and bring to active state. - 8 bit address; Holds upto 255 parked devices PM_ADDR 0x00 assigned to Slaves that responds only to BD_ADDR for unpark command from Master. - Parked Slaves are synchronised to Masters packet timing and hop sequence and listen for periodic broadcast from Master. Access request address (AR_ADDR) - AR_ADDR assigned by Master when parking a Slave. - Slave uses AR_ADDR to determine its access window in which it can send an unpark request to Master.,15,CONNECTION ESTABLISHMENT AND TYPES OF LINKS,THREE MAIN PHASESInquiry: The device initiating the connection scans the neighbourhood for bluetooth device and discovers their hardware address to connect.Paging: The device synchronizes with the other device, in terms of clock offset and phase in the frequency hop.Link establishment: The LMP will establish a link between the devices to communicate and exchange data.LINK TYPESSynchronous Connection Oriented (SCO) - Point-to-point link between the Master and a Slave, used primarily for voice. Asynchronous Connectionless (ACL) - Point-to-Multipoint link between the Master and all Slaves in the piconet, used primarily for packet data.,16,SCHEDULING ALGORITHMS,NEED FOR MAC SCHEDULING ALGORITHM - To achieve fair sharing of bandwidth. - To achieve high link utilization. - To achieve Low queue occupancy. DEFICIT OF ROUND ROBIN(RR) SCHEDULINGOnly Master-Slave connection with equal data flow achieves fair bandwidth sharing and high link utilization. - However,each Slave in the piconet has varying data input rates.Hence, baseband slots are wasted by polling sources with low input rate, thus decreasing link utilization,increasing queuing delay and unfair sharing of bandwidth.SOLUTION TO ADDRESS THE ISSUE Three new Scheduling algorithm proposed: - Adaptive Flow-based Polling (AFP) - Sticky - Sticky Adaptive Flow-based Polling (StickyAFP),17,SCHEDULING ALGORITHMS(CONTD),METHODS IMPLEMENTED IN SCHEDULING ALGORITHM Queue priority based on flow bit - Use the flow bit (conveys flow information at L2CAP level) in the payload header of the baseband packet to assign priority to Per-Slave baseband queues at the Master based on the pending data in the L2CAP buffers. - The flow bit is set when the number of packets in the L2CAP buffer for a particular Slave is larger than a threshold buf_thresh. - At the Master, “variable flow” is defined to quantify the traffic rate on the wireless channel, which is set when the flow bits for packets traveling in either direction is turned on.,Fig 9. MAC Scheduling From: A. Das, A. Ghose, A. Razdan, H. Saran, and R. Shorey, “Enhancing performance of asynchronous data traffic over the Bluetooth wireless ad-hoc network,” Proc. of IEEE INFOCOM, Anchorage, Alaska, 2001,18,SCHEDULING ALGORITHMS(CONTD),Queue SticknessAIMTo reduce mean queue occupancy In Round Robin Scheduling, one packet served at a time from baseband queue. Slaves with higher data inflow benefit while Slaves with low queue backlog experience wastage of baseband slots.SOLUTIONTransmit a number of baseband packets successively quantified by a parameter num_sticky for each queue with the flow parameter set.,19,SCHEDULING ALGORITHMS(CONTD),PROPOSED ALGORITHMSAdaptive Flow-based Polling (AFP)- P0 : initial polling interval, maximum time limit before which a Master has to serve a Slave - AFP uses an adaptive polling interval P, whose value is changed based on the traffic rate in wireless channel indicated by variable flow -If flow = 1 and the HOL packet is a data packet, transmit the data packet and set the polling interval from P to P0 (reduced) so that Slave can be served more frequently with high flow rate.- If flow = 0 and the HOL packet is a data packet, transmit the data packet and keep the polling interval unchanged.If a polling packet is transmitted and a null packet is received, double the current polling interval P unless a threshold value Pthresh is reached. Polling interval is increased to reduce slots wasted when neither Master nor Slave have any data to transmit.,20,SCHEDULING ALGORITHMS(CONTD),Sticky - Each Slave is served in a cyclic fashion dependent on the state of flow: - If flow = 1, a maximum of num_sticky packets are transmitted for that queue - If flow = 0, one packet is transmitted for that queue, as in Round-Robin schedulingSticky AFP - Similar to AFP except that: - If flow = 1 and the HOL packet is a data packet, a maximum of num_sticky packets are transmitted for that queue - If flow = 0 and the HOL packet is a data packet, just transmit the packet,21,SCHEDULING ALGORITHMS(CONTD),MORE DESIGN ISSUESChannel State Dependent Packet (CSDP) Scheduling - To improve data throughput over lossy wireless links characterised by bursty errors - Upon encountering a packet loss (NACK), CSDP policies defer the retransmissions to that slave till the next polling instant - Compare CSDP-AFP,CSDP-Sticky, CSDP-StickyAFP performanceNumber Of SCO Connections - Upto 3 simultaneous SCO links for voice traffic can be supported by Master - Master sends SCO packets at regular intervals, TSCO (counted in slots) SCO Slave is always allowed to respond in the following slot - Compare data traffic in the presence of varying number of SCO links,22,SCHEDULING ALGORITHMS(CONTD),SIMULATION MODEL - Network modeled as One Master Seven Slave - TCP/UDP packet size 512 bytes, TCP ACK size 40 bytes - Slaves 1 and 2 have persistent TCP (ftp) connection which are active from 0-60 sec and 10-20 sec respectively - Slaves 3-7 receive constant bit rate traffic running over UDP with different bit rates PERFORMANCE METRICS MEASURED - Throughput - End-to-End delay - Link Utilization,23,SCHEDULING ALGORITHMS(CONTD),SIMULATION RESULTS AND PERFORMACE EVALUATION - AFP and Sticky algorithms give significantly improved performance compared to Round Robin - The throughput of Sticky increases with increase in the value of num_sticky and is approximately the same as AFP for num_sticky=16,Fig 10. TCP throughput vs Time for AFP and Sticky with RRFrom: Apurva Kumar, Lakshmi Ramachandran and Rajeev Shorey, “Performance of network formation and scheduling algorithms in the Bluetooth wireless ad-hoc network”,Journal of High Speed Networks,Volume 1,2001,pp 59-76,SCHEDULING ALGORITHMS(CONTD),The throughput of StickyAFP with num_sticky=16 is better than that of AFP and StickyAFP with num_sticky =4, but not very significant (fig 11)High link utilization is obtained for StickyAFP (num_sticky=16), Sticky (num_sticky=16) and AFP compared to Round-Robin (fig 12),Fig 11. TCP throughput vs Time for AFP and StickyAFP Fig 12. Link Utilization for Scheduling AlgorithmsFrom: Apurva Kumar, Lakshmi Ramachandran and Rajeev Shorey, “Performance of network formation and scheduling algorithms in the Bluetooth wireless ad-hoc network”,Journal of High Speed Networks,Volume 1,2001,pp 59-76,25,SCHEDULING ALGORITHMS(CONTD),The Sticky algorithm is found to have the lowest end-to-end delay while StickyAFP has the highest- Sticky reduces queue occupancy by transmitting multiple packets consecutively from queues preventing queue overflow and reducing end-to- end delay By increasing the polling interval, AFP decreases the number of poll packets (for those queues that have less data) which otherwise cause underutilization of available bandwidth, and hence increases link utilization StickyAFP causes a marked increase in the end-to-end delay of intermittent CBR traffic because flow is set infrequently for such bursty sources Additionally, each cycle has a larger duration due to other slaves being served num_sticky times,26,SCHEDULING ALGORITHMS(CONTD),Fig 13. End-to-End Delay for Scheduling Algorithms From: Apurva Kumar, Lakshmi Ramachandran and Rajeev Shorey, “Performance of network formation and scheduling algorithms in the Bluetooth wireless ad-hoc network”,Journal of High Speed Networks, Vol 1,2001, pp 59-76,INFERENCE: AFP and Sticky(16) result in the best overall performance,27,SCHEDULING ALGORITHMS(CONTD),EFFECT OF ERROR CORRECTION SCHEMES- End-to-End delay and Link Utilisation measure for different values of tx_thresh (maximum number of retransmissions of baseband packets)OBSERVATIONS-Performance degradation in the presence of errors-Reduction in link utilization and increase in end-to-end delay due to the use of FEC-When FEC added,performance is independent of tx_thresh, and ARQ scheme,Fig 14. Link Utilization vs tx_thresh for versions of AFP Fig 15. End-to-End delay vs tx_thresh for versions of AFPFrom: Apurva Kumar, Lakshmi Ramachandran and Rajeev Shorey, “Performance of network formation and scheduling algorithms in the Bluetooth wireless ad-hoc network”, Journal of High Speed Networks, Volume 1, 2001, pp 59-76,28,SCHEDULING ALGORITHMS(CONTD),EFFECT OF CSDP SCHEDULING - CSDP versions of the proposed scheduling algorithms do not give a significant performance improvement and their relative performance is the same as that in the error-free channel condition- Since burst error periods in the wireless channels are short enough to allow packets to be successfully retransmitted before tx_thresh, CSDP versions do