An

An adaptive segmentation scheme for the Bluetooth-based wireless channelJesung Kim,Yujin Lim†,Yongsuk Kim‡,and Joong Soo Ma School of Computer Science and Engineering,Seoul National University,Seoul,Korea Department of Mechanical Engineering,University of Seoul,Seoul,Korea†i-Networking Lab.,Samsung Advanced Institute of Technology,Suwon,Korea‡Information and Communications University,Taejon,Koreajskim@archi.snu.ac.kr yujin@uos.ac.kr yongsuk@ jsma@icu.ac.krAbstract—Bluetooth has been regarded as a promising solution for wireless connection between hand-held devices. In Bluetooth,a message is segmented into short packets to be transmitted over different frequency bands to random-ize error occurrences.There are various kinds of packets with different sizes and error-handling schemes.Since each packet type has its own performance characteristics,care must be taken in selecting a packet type.This paper pro-poses an adaptive method that selects the best packet type depending on the condition of the channel.One of chal-lenging issues in the proposed scheme is how to predict the packet error rate of one packet type from another.In this paper,we interpolate packet error rates of different packets based on a uniform bit error model.Based on the packet error rates obtained from the interpolation,the proposed scheme selects a packet type that leads to the best perfor-mance.We also propose a revised scheme that works even when bit errors occur in a non-uniform pattern.The pro-posed scheme is especially useful in a harsh environment where the bit error rate is worse than104.I.I NTRODUCTIONORTABLE devices such as PDA’s,cellular phonesand notebook computers are in common place,and we often connect a device to another device to use con-venient applications such as wireless Internet or calendar synchronization.In the past,we had to use a bulky serial cable for interconnection between a pair of devices.To avoid such inconvenience,a wireless solution has highly been in demand by consumers.Bluetooth is one of such technologies and especially attractive in the environment This paper is a result of a joint research project of Samsung Ad-vanced Institute of Technology,Information and Communications University,and Seoul National University,This research was sup-ported in part by the Brain Korea21Project in2001.The second au-thor was supported from the Basic Research Program(for the woman scientists)of the Korea Science&Engineering Foundation.of hand-held devices since a low cost is an important re-quirement of such a technology[1],[2].The Bluetooth technology can also be used as a generic layer-two logical link for a higher layer protocol such as TCP/IP.To facilitate a common interface to various upper layer protocols,Bluetooth provides an adaptation layer that receives messages from an upper layer,and reformats the messages to a format suitable for transmission via the Bluetooth physical channel.One of the main functions of the adaptation layer is to segment a large upper layer message into several small fragments each of whichfits into a Bluetooth native packet,similar to the ATM adap-tation layer.But unlike ATM,Bluetooth provides various packet formats with different sizes and error protection capabilities[1].Therefore,the adaptation layer need to select a suitable packet format depending on the error rate and/or the required quality of service.A simple but com-mon implementation would let a user or an application choose a packet type depending on the desired quality of service.However,a static packet format selection may not be efficient since the channel error rate varies in time. The received signal strength will vary in time since com-munication occurs between portable devices in a dynami-cally changing environment.The channel error rate is also affected by the interference from other devices using the same frequency band,which also varies in time.In this paper,we propose an adaptive method that se-lects the best packet type depending on the current quality of the communication link.The basic idea behind this scheme is that a large packet has low overheads and is ad-vantageous when the bit error rate is relatively low,while a small packet has a low packet error rate and thus is advan-tageous when the bit error rate is high.However,it is dif-ficult to estimate the channel bit error rate in a short time when the link is operating under error detection with re-transmission.We can approximate the bit error rate fromthe measured packet error rate under the assumption that bit errors occur uniformly.This model allows us to inter-polate packet error rates of different sizes so that the best packet type can be determined.Non-uniform error pat-terns may lead to an erroneous approximation.This paper also proposes a scheme that compensates such an error by evaluating the performance gain obtained from the change of the packet type.The organization of the remainder of the paper is as fol-lows.The next section gives an overview of the Bluetooth technology with an emphasis on the adaptation layer.The proposed adaptive segmentation scheme is presented in the following section.Next,we provide an analysis of our scheme based on simulation.Finally,concluding remarks are given in the last section.II.B ACKGROUNDBluetooth technology utilizes the license-free ISM band for wireless interconnection between computing de-vices within a short range.To share the ISM band with many other users effectively,Bluetooth fragments a long message into short packets and transmits each packet over different carrier frequency.For this purpose,an adaptation layer is defined that does the segmentation and reassem-bly of packets.This adaptation layer resides in L2CAP, which is the layer-two logical link control layer in Blue-tooth.With L2CAP,the upper layer may send messages of any length up to65,535bytes transparently to the char-acteristics of the underlying physical layer.The basic unit of the segmentation is a smallfixed time unit called a slot,which is625µsec long.With a symbol rate of1Mbps,a slot can carry up to625bits.However, to allow the sender and the receiver a sufficient time to change the direction and the channel frequency,the packet size is limited to366bits,leaving259µsec as the turn-around delay.Furthermore,due to the required packet header,payload data of only216bits are allowed,reduc-ing the efficiency further.There is also a packet type that uses forward error correction(FEC)codes with a payload size of136bits.Both packets occupy a single slot and thus called DM1(data-medium rate-1slot)and DH1(data-high rate-1slot),for the one with FEC and the one without FEC,respectively.For more efficient data transmission, Bluetooth also defines larger packet formats that expand to three or tofive slots,namely DH3and DH5.These packets are more efficient than DH1in that they can carry more information bits per slot.There are also FEC coun-terparts for each of the packet,namely DM3and DM5.In summary,there are six packet formats for data transmis-sion with different lengths and error protection properties. Table1summarizes the six packet types.TABLE IB LUETOOTH DATA PACKETSType FEC17108.827172.8121387.2183585.6224477.8339723.2Each packet gives different performance depending on the bit error rate of the underlying physical channel.With-out any bit error,the DH5packet would give the best per-formance since it carries the most information bit per unit time.However,as the bit error rate increases,the packet error rate of DH5increases faster than smaller packets. Thus,a threshold may exist where the benefit of a low packet error rate of DH3exceeds the benefit of efficiency of DH5.When this threshold can be detected,we can dy-namically choose DH3instead of DH5to improve perfor-mance.Likewise,there may exist a threshold where using of DH1is more advantageous than using DH3.By detect-ing such thresholds,we can adapt to the current condition of the channel.An adaptive scheme that selectively uses a packet with FEC depending on the condition of the channel has been proposed by Das et al[3].Their proposed scheme de-termines which is more efficient between the packet with FEC and the one without FEC.We generalize the adapta-tion method into different packet sizes based on a bit error rate estimation model as described in the next section.III.A DAPTIVE S EGMENTATIONIn this section,we describe our proposed adaptive seg-mentation scheme.The proposed scheme dynamically chooses a packet type into which an upper layer message is segmented,depending on the condition of the underly-ing physical channel.The goal of the proposed scheme is to minimize the time to transmit/retransmit a set of segments of a message,i.e.,to minimize the number of slots needed to transmit the whole message successfully. In an error-free environment,this goal can be accom-plished simply by using the largest packet,i.e.,DH5,ex-cept for the last fragment that mayfit in a smaller packet. For example,a1500-byte message can be segmented as four339-byte DH5packets and a183-byte DH3packet 150033941831,which collectively occupy 23slots4513plus5slots for the acknowledge-ment of each offive packets.In contrast,using of DH3or DH1to segment the same message would take as many as36slots and112slots,respectively,since these packets carry much smaller amount of user information bits per each slot than DH5as explained in the previous section. Larger packets,however,generally have a higher packet error rate and may offset the benefit of using larger pack-ets due to frequent retransmissions.Formally,if the packet error rate is given as PER,the average number of trials until a successful transmission occurs is equal to11PER.Since the retransmission can be carried out immediately at the next slot in Bluetooth,the average transmission time is given astransmissiontime1bandwidth1bitsper packetslotsper packet1slot length1PER efficiency bandwidth(1)where bitsper packet is the maximum amount of infor-mation bits,messagelength is the length of the trans-mitted message in bits that is assumed to be divisible by bitsper packet,slotsper packet1is the number of slots occupied by a single packet plus one slot for the ac-knowledgement,slot length is the length of a slot in bits, and efficiency is bitsper packet slotsper packet1 slot length,indicating the ratio of user information bits in a slot to the length of a slot in bits.Maximum effi-ciency of each packet is calculated as summarized in Ta-ble2.In the equation,only PER and efficiency are af-fected by packet types.Thus the transmission time can be minimized by selecting packet type X that maximizes the product of efficiency X and1PER X.This gives an effective bandwidth(EB),which is the bandwidth ob-served by the upper layer,asEB X1PER X efficiency bandwidth(2) For example,if PER DH5and PER DH3are given as 0.3and0.1and the Bluetooth bandwidth is1Mbps,the effective bandwidths of both packets are052Mbps and 050Mbps,respectively.In this case,DH3might be a better choice than DH5since EB DH3is greater than EB DH5.Note that packet error rates of different packet types should be known beforehand to make such a decision. This requires predicting packet error rates of different packet types from the current packet error rate.Assum-ing a bit error occurs uniformly(i.e.,the event of a bitTABLE IIP ACKET EFFICIENCYType0.100.170.390.590.480.72error is independent of others),the packet error rate can be expressed in terms of the bit error rate asPER X11BER bitsper packet X(3) where BER is the current bit error rate and bitsper packet X is the number of information bits in packet type X.Assuming PER is measured for sufficiently long time,we can obtain an approximate bit error rate by solving the above equation for BER,that is, BER11PER X1bits per packet X.Then we can interpolate the packet error rate of another packet type Y, PER Y,from PER X using the equationPER Y11BER bitsper packet Y11PER X bitsper packet Y0.10.20.30.40.50.60.70.81.E-07 1.E-06 1.E-05 1.E-04 1.E-03 1.E-02 1.E-01bit error ratee f f e c t i v e b a n d w i d t hFig.1.Effective bandwidth obtained from the uniform bit errormodel.Fig.along with there exist simi-larly to im-plies ben-efit of Other DM where ofFig.3.Effective bandwidth of all the packet types including DM packets.Until now,we have assumed that bit errors occur uni-formly.In the environment where bit errors occur in a burst,the interpolation of packet error rates based on this assumption may lead to erroneous approximation.One of the most popular bursty bit error models is a two-state markov process that employs two uniform bit error rates,one representing a good channel condition and the other representing a bad channel condition [6].In this model,the channel is normally in a good state showing a lower bit error rate and occasionally enters short period of a bad state with a higher bit error rate to simulate bursty bit errors.Note that bit errors occur uniformly within each state.This implies that our adaptive scheme can apply to the bursty bit error model provided that the adaptation can be made fast enough to catch up the state transitions.Un-fortunately,such an adaptation is not possible since each packet is transmitted over a different frequency band in Bluetooth.We address this issue by adjusting the threshold packet error rates dynamically according to the performance gain obtained from the change of the packet type.For this pur-pose,we measure the effective bandwidth for a certain pe-riod of time after changing the packet type and compare it to the one measured before the packet type is changed.Let ∆EB be EB after EB before ,where EB after and EB before rep-resent the effective bandwidth after/before the packet type is changed,respectively.In a normal case,∆EB should be close to zero since the change of the packet type is triggered when the EB ’s of two different packet types are estimated to be equal in our model.If ∆EB is substantially greater or less than zero,it implies that the condition trig-gering the change of the packet type needs an adjustment.In particular,∆EB 0implies that we could have changed the packet type more aggressively to obtain better performance.In this case,the threshold packet error rate is adjusted depending on whether the action was to select a larger packet type or to select a smaller packet type.When the action was to select a larger packet type,the threshold packet error rate is shifted to a larger value as depicted in Fig.4a.On the other hand,when the action was to se-lect a smaller packet type,the threshold packet error rate is shifted to a smaller value as depicted in Fig.4b.This adjustment will encourage the change of the packet type when a similar situation arises in the future.We also need to adjust the threshold packet error rate in the case of ∆EB 0since it implies that we should have been more conservative in changing the packet type.The adjustment is done conversely to the former case.That is,the threshold packet error rate is shifted to a smaller value when the action was to select a larger packet type as in Fig.4b and shifted to a larger value when the action waspacket error rate(a)Fig.4.the packet error to we go of the Rep-etition of this procedure leads to convergence,as we will see in the next section.IV.P ERFORMANCE E VALUATIONThe proposed scheme is implemented over a simple simulation environment that simulates uniform bit errors as well as bursts of bit errors based on the two-state markov process as briefly explained in the previous sec-tion.Fig.5shows the simulation results when bit er-rors are generated uniformly as bit error rates given in the x-axis.From the figure,we can notice that the pro-posed scheme is beneficial when the bit error rate is higher than 104.We can also notice that the simulation results are similar to those obtained from the probabilistic model shown in the previous section.The result is obvious since bit errors are generated exactly as the proposed scheme presumes.(a)(b)Fig.5.Results based on uniform bit errors.(a)106BER102.(b)104BER 103.Fig.6shows the results when bit errors are generated based on the two-state markov process as proposed in [6].The numbers on the x-axis represent the bit error rate in the good state.The bit error rate of the bad state is set one hundred times higher than that.The probability of being in the good state is set as 0.8.We also assume that the mean time staying in a state is much larger than a slot.The results show that adaptation based on fixed thresholds sometimes gives less-than-the-best performance.For ex-ample,when the bit error rate is 0.0007,the adaptation is stuck at DH1resulting in lower performance than the case of DH3.This phenomenon happens because bit errors are generated in a different pattern than that is assumed by the scheme.To eliminate such an anomaly,we have proposed a re-vised scheme that adaptively adjusts the thresholds trig-gering change of packets as described in Section III.Fig.7shows the simulation results.The results show that the proposed scheme eliminates the above undesirable behav-ior through adaptation of thresholds themselves.We have intended to test the proposed scheme in a de-0.000.050.100.150.200.250.300.350.400.450.5000.00020.00040.00060.00080.001bit error rate (good state)e f f e c t i v e b a n d w i d t hFig.6.Results based on bursty bit errorsFig.7.Simulation results of the revised adaptive scheme.velopment kit equipped with an actual Bluetooth radio.Unfortunately,the development kit we have used does not provide interface for measuring necessary packet er-ror rates.Measurement through a real system would ver-ify the simulation results.V.C ONCLUSIONIn this paper,we have proposed a segmentation scheme that adaptively chooses a suitable packet types.The idea behind this scheme is to trade packet efficiency of a larger packet for a lower packet error rate of smaller packets.When the packet error rate increases beyond a certain threshold,the proposed scheme selects a smaller packet to reduce overheads associated with frequent transmis-sion errors.On the other hand,when the packet error rate becomes lower below a threshold,a larger packet is advocated to improve efficiency.The threshold packet error rates can be determined from a uniform bit error model where bit errors occur independently of others.We have also proposed a revised adaptation scheme that ad-justs the threshold values to compensate overestimation of a bit error rate due to bursts of bit errors.We havealso considered the packets with forward error correction codes.However,overheads associated with additional bits in such packets are shown to annul the advantage of error correction.The proposed scheme is simple enough to be easily im-plemented in small mobile devices.It only requires an error counter for each packet type and a simple calcula-tion of the effective bandwidth that is done periodically in the order of a few seconds.As a future work,we plan to verify our model in the environment where multiple piconets interfere with each other.This requires detailed simulation of a Bluetooth usage model since the inter-piconet interference is depen-dent on the load carried over the piconets as well as the relative position of the starting point of slots.We expect that the proposed adaptive segmentation scheme is even more useful when the inter-piconet interference becomes severe since a larger packet is more susceptible to the in-terference.A CKNOWLEDGEMENTWe would like to thank Jae-yul Lee at Samsung Ad-vanced Institute of Technology and Sang Lyul Min at Seoul National University for their support and helpful comments.We also would like to thank Jihye Kim for her help with performance evaluation.R EFERENCES[1]The Bluetooth Special Interest Group,“/techn/index.asp,”Feb.1999.[2]J.Haartsen,M.Naghshineh,J.Inouye,O.J.Joeressen,andW.Allen,“Bluetooth:vision,goals,and architecture,”Mobile Computing and Communications Review ,vol.2,pp.38–45,Oct.1998.[3] A.Das,A.Ghose,V .Gupta,A.Razdan,H.Saran,and R.Shorey,“Adaptive link-level er-ror recovery mechanisms in bluetooth,”in Proceedings of IEEE International Conference on Personal Wire-less Communications ,pp.85–89,2000.[4]S.Z¨u rbes,W.Stahl,K.Matheus,and J.Haartsen,“Radio net-work performance of bluetooth,”in Proceedings of the IEEE Inter-national Conference on Communications (ICC 2000),pp.1563–1567,2000.[5] A.Das,A.Ghose,A.Razdan,H.Saran,and R.Shorey,“Enhanc-ing performance of asynchronous data traffic over the bluetooth wireless ad-hoc network,”in Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications So-cieties (INFOCOM 2001),vol.1,pp.591–600.[6] E.N.Gilbert,“Capacity of burst noise channels,”Bell SystemsTechnical Journal ,vol.39,pp.1253–1266,Sept.1960.。