WIXLIB

underlying radio technology, which is the main departure fromthat in the Internet. P2P file swarming is generally dividedinto two phases, namely resource discovery (in the immediateneighborhood) and downloading. The protocol design of eachcomponent must carefully consider the characteristics of Bluetooth to obtain better performance. However, little efforts havebeen made to understand the performance of overall Bluetooth operations, from peer discovery to data downloading, indynamic environments with mobility and interference (WiFi,obstacles). In addition, the performance variation among different Bluetooth versions was not examined, although differentBluetooth versions are currently populated in the market due tothe slow adaptation of Bluetooth standards as shown in Figure1. Measurement studies thus far reported only the performanceof specific operations in static scenarios with a certain Bluetooth version [12], [13], [14], [15]. For instance, Kasten etal. [13] reported the issues of the power consumption andpeer discovery latency in a customized Bluetooth-based sensornode; and Leopold showed peer discovery and throughputmeasurement results of a Bluetooth v1.1 device [14]. As aresult, the impacts of the Bluetooth characteristics on protocoldesign and evaluation were not addressed in recent contentdistribution systems [16], [17], [18], [19], [20].In this paper, we perform extensive experiments to accurately characterize the Bluetooth performance in a dynamicmobile environment. We emulate a mobile user with anAmigobot, a programmable robot that can travel at a speedup to 2.2m/s [21]. Our measurements include peer discovery,connection setup, and download bandwidth under variousconditions such as mobility, interference, different Bluetoothversions. To the best of our knowledge, this is the firstexperiment with Bluetooth in an externally controlled mobileenvironment. From our experimental results, we find thatBluetooth-based content distribution faces several challenges. Resource discovery in Bluetooth is time/energy consuming even with the latest Bluetooth version 2.0. InBluetooth, one must first discover its neighbors (peerdiscovery) and then create a connection to each neighborsequentially to resolve one’s query (content discovery).Mobile Bluetooth users experience significant throughputdrop. In particular, the measured throughput varies widelyover distance and is much lower than the simulationresults. We discover that this is mainly due to the auto ratecontrol algorithm in Bluetooth called Channel QualityDriven Data Rate (CQDDR) implementation in Bluetoothdevices. The incorrect choice of a packet type results ina significant performance loss as noted in [22].We find that Bluetooth devices are not optimized for“mobile” environments. The advance features such astransmission power control that adjusts power to saveenergy, and adaptive frequency hopping that prevents theuse of interfered channels, do not work well, mainlybecause of their long response time as oppose to a shortcontact period in mobile scenarios.We report that the particular type of Bluetooth versions/chipset has a great impact on peer discovery, connection setup, and data throughput.Fraction of one0.1Laptop01.1 1.2 2.0 1.1 1.2 2.02006/112007/11Fig. 1. Bluetooth version distribution: The statistics were gathered in theUCLA campus on Nov. 29/30, 2006 and Nov. 29, 2007. Bluetooth versioninformation was collected from those devices that allowed making connections(75% of 402 devices in 2006 and 60% of 351 devices in 2007).Given this, we improve Bluetooth-based contention distribution and make the following contributions. We investigate the performance improvement strategiesof resource discovery/downloading phases. First, we propose solutions that can effectively reduce the contentdiscovery latency; thus, for given contact time, a node canspend more time for data transfer. Second, we consideran energy efficient peer discovery scheme that savesenergy with minimal performance penalty. Third, wepropose a method for adaptive Bluetooth packet selectionso as to fully utilize the channel. Finally, we evaluatecoding techniques such as rateless/network coding thatcan potentially increase the availability of data. These schemes are validated with a combination of simulations and testbed experiments. Our results show that (1)the cooperative resource discovery method significantlyreduces the latency; (2) adaptive inquiry mode where theinquiry mode is initiated by other peers conserves energywith minimal performance degradation; (3) a receiverfeedback scheme for packet size selection maximizes thechannel utilization; and (4) network/rateless codes yieldup to 15% improvement in the tested scenarios.Note that our measurement results can also be applicable tooptimizing networking protocols. For instance, Delay TolerantNetwork (DTN) routing [23], [24] which aims at providingreliable data delivery even with connectivity disruptions (dueto mobility and sparse node density) can maximize data transfer per contact, thereby increasing the end-to-end throughput.The rest of this paper is organized as follows. Section II-Bintroduces the basics of Bluetooth. Section III describes theexperimental setup and presents our measurement results. Section IV describes various schemes to enhance the performanceof a file swarming protocol in Bluetooth. The following sectionevaluates the proposed schemes via extensive simulations.Related work is reviewed in Section VIII. Finally, Section IXconcludes the paper.II. BACKGROUNDIn this section, we overview Bluetooth-based P2P contentdistribution and illustrate detailed protocol operations of Bluetooth to understand their impacts on content distribution.

3Inquiry Window (Tw inq)A. Bluetooth-based P2P Content DistributionIn our scenario, a static Bluetooth-enabled digital billboardlocated at a popular place (e.g., subway stations, departmentstores, tour sites, and stadiums) is a publisher of content [1],[2], [3]. It initially pushes content meta-data to mobile users,which includes a unique channel ID (e.g., SHA-1 hash of thecontent title), content version, timestamp, short description,producer, media type, etc. For a given content channel, different versions can be distinguished using the version field in themeta-data. Based on the content channel description, mobileusers can selectively subscribe various content channels, e.g.,headline news video clip, tourist information, etc.Mobile users who have subscribed the same content channelproactively query other peers (content pulling). After findingpeers of interest, they share content by using BitTorrent-likefile swarming. The data source (i.e., static billboard) divides afile into n fixed size pieces. Peers can download pieces fromstatic billboard and other peers. Each node has a bitmap of theavailable pieces for efficient piece reconciliation. Whenever aconnection is available, peers first exchange their bitmaps tofind out missing pieces through simple bit operations. The sizeof a typical bitmap is as small as tens of bytes even if thereare more than 100 blocks. To be more precise, given n pieces,the size of a bitmap table is ⌈n/8⌉ bytes. For example, thesize of a bitmap table for 100 blocks only takes 13 bytes.B. Bluetooth OverivewBluetooth is defined as layered protocol architecture. Radiospecifies details of the physical layer of Bluetooth. Basebandconcerns with peer discovery, connection setup, addressing,packet format, power control, and timing etc. Link ManagerProtocol (LMP) is responsible for link setup between Bluetooth devices and link management. This includes the controland negotiation of baseband packet size and transmissionpower. Logical link control and adaptation protocol (L2CAP)adapts upper-layer protocols (e.g., segmentation and reassembly, protocol multiplexing, flow control per L2CAP channel,error control and retransmissions, etc.) to the Baseband layervia Host Control Interface (HCI). In this section, we reviewRadio and Baseband of Bluetooth. Readers can find the detailsof the Bluetooth radio system in other papers [25], [26]In Bluetooth, the total bandwidth is divided into 79 channels(each 1 MHz). Frequency hopping (FH) occurs by jumpingfrom one physical channel to another in a pseudorandomsequence. The hop rate is 1600 hops per second, so thateach physical channel is occupied for 625µs. This intervalis referred to as a slot and is numbered sequentially. Thebasic unit of networking in Bluetooth is a piconet, consistingof a master and from one to seven active slave devices. Themaster determines a hopping sequence based on its BluetoothID (referred as an FH channel) that shall be used by all deviceson this piconet. The FH channel is shared between a masterand slaves using Time Division Duplex (TDD); i.e., dataare transmitted in one direction at a time with transmissionalternating both directions. Multiple slaves share the piconetmedium using Time Division Multiple Access (TDMA). ThisFH channel is a form of Code Division Multiple AccessMaster256 A-trainsInquiry ScanWindow (Tw inq scan)256 B-trainsInquiry PacketInquiry PacketInquiry Response PacketSlaveTimeInquiry ScanInterval (Tinq scan) Random Back-offIntervalFig. 2. Bluetooth inquiry procedure example: The size of the inquiry windowis 5.12s ( 4 1.28s). The master node sends inquiry packets during the inquirywindow. The slave node periodically listens to a specific channel to wait foran inquiry packet (inquiry scan). After receiving an inquiry packet, the slaveperforms a random back-off and then sends an inquiry response.(CDMA), and thus, several piconets can coexist with minimalinterference. Two piconets will occasionally use the samephysical channel during the same time slot, causing a collisionand data loss, but this happens rarely, and it is recoveredby forward error correction (FEC) and error detection/ARQtechniques. Multiple piconets in the same area are referred toas a scatternet and different piconets can be interconnected.However, scatternet connection support is defined as optionalin all the Bluetooth specifications; thus, many Bluetooth chipsdo not support scatternet [19].Physical link and packet types: The Bluetooth link supports synchronous services such as voice traffic via the synchronous connection oriented (SCO) link, and asynchronousservices such as bursty data traffic via the asynchronousconnectionless (ACL) link. Since we focus on the data traffic,only the ACL link is illustrated in the following. Basebanddefines an ACL link to provide packet switched connectionbetween master and active slaves (one ACL link per slave).The master interleaves traffic between multiple active slaves(up to 7 slaves).Achievable data rates on the ACL link vary depending onthe number of slots per packet (1, 3, and 5 slots) and on theforward error correction (FEC) strategy. The more the numberof slots, the larger is the payload size. FEC packets formatsare DM1 (17B), DM3 (121B), and DM5 (224B), and the nonerror coded formats are DH1 (27B), DH3 (183B), and DH5(339B). For instance, DH5 can achieve the maximum rateof 732.2Kbps and 433.9Kbps for asymmetric and symmetriccommunications respectively. The maximum asymmetric andsymmetric data rates are 732.2 Kbps and 433.9Kbps with DH5respectively. As of Bluetooth v2.0 Enhanced Data Rate (EDR),Phase Shift Keying (PSK) modulation has been added. PSKincreases coding bits per symbol to 2 and 3 bits, thus introducing EDR packet types without FEC as 2-DH1/2-DH3/2DH5 (packet size 2 DHx, maximum asymmetric andsymmetric rate 1448.5Kbps and 869.7Kbps, respectively)and 3-DH1/3-DH3/3-DH5 (packet size 3 DHx, maximumasymmetric and symmetric rate 2178.1Kbps and 1306.9Kbpsrespectively).Peer Discovery: The first step in establishing a piconet is toidentify devices in range that wish to participate in the piconet.As shown in Figure 2, the inquiry procedure begins when thepotential master transmits an ID packet with Inquiry Hopping

4Sequence (Tx slot) and waits for the response packets from theslaves with the Inquiry Response Hopping Sequence (Rx slot).The Inquiry Hopping Sequence consists of 32 unique wakeup frequencies distributed equally over the 79 frequencies andis divided into two distinct sequences called A- and B-train.Each train contains 16 physical channels and must be repeatedat least 256 times (i.e., 2.56s 256 10ms) before switching toanother train. During the inquiry window (Tw inq ), the masterrepeats the following: send two inquiry packets in each Txslot, and then listen to response packets from other devices inthe following Rx slot. The potential slaves periodically (i.e.,Tinq scan ) enter the Inquiry scan state and listen to a specificchannel to search for inquiry packets for inquiry scan window(Tw inq scan ). When a node receives an inquiry packet, itenters the Inquiry Response state and returns an FHS packet(i.e., inquiry response) after backing off a random number ofslots to avoid collision. A FHS packet contains the deviceaddress, page scan repetition mode (PSRM) and clock offset(CO), required by the master to initiate a connection. As ofBluetooth v1.2 the interlaced inquiry scan is introduced. In theoriginal scheme, because the master repeats a specific packettrain many times, a slave node could miss the whole packettrains if it listens to a channel that belongs to the other packettrain (e.g., inquiry A train/scan B train, or inquiry B train/scanA train). To prevent such pathological situations, the interlacedscan allows a slave node to scan two trains (i.e., A and B)in a row. Thus, the probability of missing an inquiry packetbecomes negligible [27].Connection setup: Once the master has found deviceswithin its range, it can establish a connection to a device(i.e., paging). For a device to be paged, the master uses theslave device address to calculate the page hopping sequence.To synchronize the phase in the sequence, the master usesthe estimate of the slave’s clock from the inquiry response, ifavailable. To synchronize the phase, the master node performsthe similar procedure as the inquiry procedure, but using thepage hopping sequence. The potential slaves periodically (i.e.,Tpage scan ) enter the Page scan state and stay there for pagescan window (Tw page scan ) to search for paging packets. Theslave page scan repetition mode (i.e., scan frequency) can beeither R1 (Tpage scan 1.28s) or R2 (Tpage scan 2.56s).The slave’s setting (i.e., R1 or R2) is informed to the mastervia the PSRM field of the inquiry response packet. Since thepaging interval should be greater than the page scan interval,the master sets the number of packet train repetition (Npage )based on the slave’s configuration, namely Npage 128 forR1 and Npage 256 for R2. The master then starts sendingthe packet train Npage times. After receiving the pagingpacket, the slave immediately returns the response packet(without back-off). Finally, the master then responds with itsFHS packet (master response), and the slave sends back anacknowledgement. As a result, a connection is established andboth master and slave begin to use the connection hoppingsequence defined in the master’s FHS packet.Power class: A Bluetooth device is classified into threepower classes: Class 1, Class 2, and Class 3 (100m, 10m, and1m radio range respectively). Portable devices (PDA, SmartPhones, etc.) typically use Class 2 interfaces, and commercialBluetooth-based content distribution systems such as BlueCasting [28] and BlueBlitz [29] use Class 1 interfaces. Theoutput powers of Class 1, Class 2, and Class 3 must be in rangeof [1mW (0dBm), 100mW (20dBm)], [0.25mW (-6dBm),2.5mW (4dBm)], and [1mW (0dBm), N/A] respectively. Thenominal output power is only defined in Class 2 as 1mW(0dBm). It is mandatory for Class 1 devices, but optionalfor Class 2 devices to implement power control. Based onReceived Signal Strength Indication (RSSI), devices exchangemessages (via LMP) to adjust output power.III. M EASUREMENT S TUDY OF B LUETOOTH - BASEDC ONTENT D ISTRIBUTIONIn this section, we evaluate the Bluetooth-based contentsharing system through measurement. We are mainly interested in measuring peer discovery/connection setup latencyand data rate of a mobile user. Peer discovery latency denotesthe time to discover a random node. Connection latency isthe time to make a connection to a discovered peer. Theefficiency of the connection is measured through the downloadthroughput. These performance metrics may depend on variousfactors; namely, a class of Bluetooth devices (i.e., Class 1 or2) and versions (i.e., Bluetooth 1.1, 1.2, or 2.0 EDR), speedof users, distance between users, and WiFi interference. Wemeasure the impacts of these variables using the metrics ofinterests. In this section, after describing the experimentalsetup we first show the results of peer discovery/connectionlatency. We then present the downloading throughput of amobile user followed by the impact of WiFi interference.Finally, the downloading performance in a real environmentis presented.A. Measurement SetupMeasurement hardware: Evaluating mobile users is challenging since it is nontrivial to control the speed of users.Thus, the key ingredient is the ability to control the speed ofmobile users so that we can repeat the experiment multipletimes in order to accurately measure the performance. To thisend, we use Amigobot, a programmable robot that can travelat a speed up to 2.2m/s. Amigobot can be controlled wirelesslyin a remote machine using a 900MHz radio modem pair calledAmigoWireFree. A mobile user is emulated by an Amigobotcarrying a laptop on its top. In the experiment, the speeds ofthe Amigobot are set to 0.5, 1.0, and 1.5m/s (slow, moderate,and fast walking speeds respectively [30], [31]) and our speedmeasurement results confirm that it can achieve the specifiedsettings of interest. Note that Amigobots are used to measuredata rates under various scenarios (Section III-C and SectionIII-D); for peer discovery/connection setup (Section III-B), weuse static scenarios. The laptop used is Dell Latitude D610with a Pentium M 770 processor (2.0Ghz) and 512MB RAM.The following Bluetooth dongles are used for experiments.In the case of Class 2 devices, we use Belkin F8T003v (CSRchipset, Bluetooth v1.1), Bluetake BT009Si (Silicon Wave,Bluetooth v1.2), and Belkin F8T013V (Broadcom chipset,Bluetooth v2.0 EDR). Since most commercial Bluetooth-basedcontent distribution systems such as BlueCasting [28] and

5PeerDiscoveryhci cessFig. 3.ConnectionSetuplisten()time rement software operationsBlueBlitz [29] use the Class 1 interfaces, we also experimentwith a Class 1 device, Belkin F8T012V (Broadcom chipset,Bluetooth v2.0 EDR) in order to see the potential benefits ofits high transmission power for data transfer to Class 2 devices.Note that a long range transfer is only feasible between Class1 devices because Bluetooth requires a bidirectional link forhandshaking.Measurement Environment: Unless otherwise mentioned,the experiments were carried out in the second level of underground parking lot to exclude external factors, such as WiFiinterference and obstacles (i.e., human). There was no physicalinterference of human/vehicles because the experiments wereperformed late at night.Measurement software: To measure the metrics of interests, we develop a measurement tool using BlueZ v3.7 [32].BlueZ is one of the most popular Bluetooth host protocol stackimplementations and is included in the official Linux kernel.BlueZ implements core protocols (e.g., L2CAP, RFCOMM,etc.) and provides the BSD socket interfaces. The softwareis used for peer discovery, connection, and data transfer.On one side, the measurement software operates as masternode, and on the other side, it operates as slave node. Peerdiscovery is carried out using hci-inquiry function by themaster node. The duration of inquiry (inquiry length) isone of the parameters of hci-inquiry and its unit is 1.28s.1The actual data transfer is realized through L2CAP sockets.L2CAP is a connection-oriented protocol that sends individualdatagram of fixed maximum length. The default transportpolicy is to retransmit until success or total connection failure,thus providing a reliable point-to-point connection. L2CAPuses Protocol Service Multiplex (PSM) ports to differentiatemultiple applications on the same host. The slave node bindsa PSM port and waits for a connection. The master nodecan initiate a connection to the slave node by calling L2CAPconnect socket function. An ACL connection is used for datatransfer, but this connection initiation routine (i.e., paging) ishidden beneath the L2CAP software layer in BlueZ kernelmodule. Note that connect requires the timeout value, but thisis nothing to do with the actual paging interval. As described inSection II-B, the paging interval is determined by PSRM valuein the inquiry response. Our tested devices all use PSRM modeR2 in which the page scan interval is less than 2.56s. In thiscase, the specification recommends that Npage , the number1 Theinquiry window size is inquiry length 1.28s.of paging train repetitions, should be greater than 256, i.e., 2.56s. During the period, if the paging node receives apage response, it immediately returns and starts exchangingadditional packets to setup an L2CAP connection. Therefore,given that Npage 256 is used, we can assume that the overallconnection takes roughly less than 3s. In our experiment, thisvalue is used as a connection timeout value. If the connectiontimes out, the program retries until it succeeds.The overall procedure can be summarized as follows (seeFigure 3). The master node first calls hci-inquiry to discoverpeers. The number of inquiry attempts is logged to measurethe discovery latency. Upon finding a node, it tries to makean L2CAP socket connection to the peer. The latency ofL2CAP connect function is logged to measure the connectionlatency. As described above, by setting connection timeout as3s each connection attempt takes less than 3s. The numberof connection attempts is also logged. Dummy data with achunk (packet) of 2300B is continuously transmitted untilthe connection is lost. Hereafter, we refer a chunk of 2300Bas a packet. For every packet transfer, the master logs thetransmission power level (hci-read-transmit-power-level). Theslave node sets on inquiry and page scan, and listens to aspecific port in order to accept an L2CAP connection. Oncethe connection is created, the slave starts receiving packets andlogs link quality (hci-read-link-quality) and Receive SignalStrength Indication (RSSI) (hci-read-rssi) information. Forevery 500ms period, it logs the total amount of received dataand the data throughput. In addition, the slave node logs HCIevent messages using hcidump, a packet snooping program forBluetooth. As we will see later, hcidump at the receiver sideallows us to infer the current packet type for data transfer.This information is managed by Link Management Protocol(LMP) in Bluetooth and is not revealed to the upper layer.B. Peer Discovery/Connection Setup LatencyPeer discovery and connection latencies are the key components of Bluetooth-based content distribution. Given limitedcontact duration, the above overheads determine the usefultime for actual data transfer. In this section, we investigatevarious parameters impacting the performance of these metrics; namely, inq

Mobile Bluetooth users experience significant throughput drop. In particular, the measured throughput varies widely over distance and is much lower than the simulation results. We discover that this is mainly due to the auto rate control algorithm in Bluetooth called Channel Quality Driven Data Rate (CQDDR) implementation in Bluetooth devices.