Mobile Networks and Applications 8, 675–685, 2003 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.
A Novel Scatternet Scheme with IPv6 Compatibility WEI KUANG LAI and DER HWA TAN Department of Computer Science and Engineering, National Sun Yat-Sen University, No. 70, Lien Hai Rd., Kaohsiung, Taiwan 804, ROC
Abstract. Some market analysts predict that there will be some 1.4 billion Bluetooth devices in operation by the year 2005 [8]. However, the current specification1.1 does not describe the algorithms or mechanisms to create a scatternet due to a variety of unsolved issues [3,12]. Since the upper layers are not defined in Bluetooth, it is not possible to implement the scatternet in current specification. Hence in this research, we need make some modifications to Bluetooth protocol in order to support the transmissions of packets in the scatternet. In this paper we describe a novel scatternet architecture, and present link performance of the proposed architecture. The issues of the routing algorithm, handoffs, and communications with other networks are also discussed. Keywords: Bluetooth, scatternet, IP, multicast, piconet
1. Introduction Bluetooth operates in the unlicensed ISM band at 2.4 GHz (2.42–2.48 GHz). In this band, a set of 79 hop carriers have been defined at 1 MHz spacing. The nominal link range is 10 cm to 10 m, but can be extended to more than 100 m by increasing the transmitted power. A frequency hop transceiver is used to combat interference and fading. Frequency Hopping Spread Spectrum (FHSS) combines a number of properties which make it a good choice for ad hoc radio system. Frequency hopping over 79 carrier frequencies is applied between subsequent bursts. A slotted channel scheme is applied with a normal slot length of 625 µs. For full duplex transmission, a Time-Division Duplex (TDD) scheme is used. Although information is exchanged through packets on the channel, each packet is transmitted on a different hop frequency and can be composed of multiple slots (1, 3 or 5). Time Division Duplex (TDD) scheme is implemented with polling for uplink traffic that starts at the beginning of odd slot numbers. Guard time or switch time between two different hops is 220 µs, so the effective time in a single slot communication is only 405 µs. Because of no hopping occurring, the multi-slot bursts get more effective communication with less percentage in guard time. There are two different data packet types in Bluetooth environment. One is real-time, constant rate, synchronous connection-oriented links (SCO links), and another is variable rate, asynchronous connectionless link (ACL) with Automatic Repeat Request (ARQ) (table 1). In table 1, DM stands for Data-Medium rate and DH stands for Data-High rate. Both packets contain a CRC code and retransmission is applied if no acknowledgement is received. Medium rate packets trade data efficiency for a greater probability of successful transmission and can be useful in combating certain noisy wireless links. The Bluetooth system provides a point-to-point or pointto-multipoint connection. Two or more units sharing the same channels form a piconet. One piconet consists of one master and up to seven active slaves and the master-slave relationship
is used to initiate and control the traffic between devices in a piconet. The number of units that can participate on a common channel is deliberately limited to eight in order to keep a high-capacity link between all units. Many more slaves can remain locked to the master in a so-called parked state. Although these parked slaves cannot be active on the channel, they remain synchronized to the master. Multiple piconets may cover the same area. The packets carried on the channels are preceded by different channel access codes which are determined by the master device addresses. The probability of collisions increases as more piconets are added. A graceful degradation of performance is common in frequency-hopping spread spectrum systems. If multiple piconets cover the same area, a unit can participate in two or more overlaying piconets by applying time multiplexing. A Bluetooth unit can act as a slave in several piconets, but only as a master in a single piconet. A group of piconets in which connections exist between different piconets is called a scatternet. A master or slave can become a slave in another piconet by being paged by the master of the other piconet. Since the paging unit always starts out as master, a masterslave role exchange is required if a slave role is desired. When a unit transmits packets in ACL links, a unit can make a request to enter the hold or park mode in the current piconet and join another piconet by just changing the channel parameters. Units in the sniff mode may have sufficient time to visit another piconet in between the sniff slots. If SCO links are established, other piconets can only be visited in the non-reserved slots in between. When there are four slots in between, one other piconet can be visited. If a slave connects to two masters, since the multiple piconets are not synchronized, guard time must be consumed to account for misalignment. This means that only 2 slots can effectively be used to visit another piconet. For both ACL and SCO, since the two master clocks drift independently, regular updates of the offsets are required in order for the slave unit to keep synchronization to both masters. A master-slave (MS) switch can take place when a slave wants to become a mas-
676
W.K. LAI AND D.H. TAN
Table 1 Data packet types. Link type
Packet type
FEC
User payload (bytes)
Burst length (µs)
Slots
ACL
DM1 DH1 DM3 DH3 DM5 DH5
2/3 1 2/3 1 2/3 1
0–17 0–27 0–121 0–183 0–224 0–339
171–366 150–366 186–1626 158–1622 186–2871 158–2870
1 1 3 3 5 5
SCO
HV1 HV2 HV3
1/3 2/3 1
10 20 30
366 366 366
1 1 1
in order to support handoffs and communications with other networks, we suggest using IPv6 addressing formats and propose the cellular structure. The details of handoffs and communications with other network are discussed. The roles of master, slaves and the control master in the cellular structure are also discussed. In section 4, we present the simulation environment and simulation results. Finally, in section 5, we present our conclusions.
2. Routing in scatternets Every Baseband packet can contain up to about 340 payload bytes which carry user data and control information for higher layers. Specification 1.1 does not describe the algorithms or mechanisms to create a scatternet due to variety of unsolved issues. In our scheme, we can make use of L_CH code (Logical Channel) field in Payload Header to specify the mechanism for a scatternet [2]. 2.1. Payload Extension Header for a scatternet Table 2 lists the meaning of four L_CH codes. From table 2, the value 00 of L_CH code is undefined. Hence, we can define the packet with L_CH = 00 as a scatternet transmission packet. In table 2, L2CAP stands for logical link control and adaptation layer protocol. Figure 2 describes the 4-bytes PEH (Payload Extension Header) appending to Payload Header. There are six fields defined in PEH and their functions are listed in table 3 and explained as follows:
Figure 1. A scatternet scheme with Control Master.
ter. Each parked slave shall be activated (using the old park parameters), changed to the new piconet parameters, and then returned to the park mode using the new park parameters. We design a scatternet scheme which is formed by multiple piconets, and we design a routing scheme for transmitting packets within the scatternet (figure 1). We also design a scheme for packet reordering which the specification does not implement. For inter-piconet communication outside the range of the Control Master (CM), every device asks the routing vector information from its own CM (include CM itself). One CM maintains all information between every Bluetooth device within the range of the CM. There are many mechanisms [4,5,11,13,14] for distributing routing information to the CM. It is not the focus of this paper. So in this paper, we assume the CM already has the required information to route messages from one node to another node within the scatternet. IPv6 packets are used in inter-piconet communication since IPv6 addressing is very popular in wireless networks. The packets could be exchanged with other wired/wireless networks from Bluetooth devices through the CM. A suitable path among multiple paths to the CM would be selected for forwarding the packets to outer networks. The remainder of the paper is organized as follows. In section 2, we propose a routing algorithm to support packet transmissions in the scatternets and discuss payload extensions needed. In section 3,
(1) Ext field (1 bit): Ext field is to find out if there are still PEHs behind. The value 0 means that it is the last PEH. Table 2 L_CH code, logical channel, and information specification. L_CH code
Logical channel
Information
00
NA
Undefined
01
L2CAP
Continuation fragment of an L2CAP message
10
L2CAP
Start of an L2CAP message or no fragmentation
11
LMP
LMP (Link Manager Protocol) message
Figure 2. Payload Extension Header in the Bluetooth packet.
A NOVEL SCATTERNET SCHEME WITH IPV6 COMPATIBILITY
Table 3 Fields and descriptions in Payload Extension Header. Field name
Bit(s) Value
Description
Ext C/S Reorder Length Routing vector
1 1 2 5 21
0/1 0/1
0) last PEH; 1) there are at least one PEH behind 0) L_CH = 01; 1) L_CH = 10 Maximum 4 packets reordering Indicate the length of Routing Vector There are seven 3-bit sub-fields which form forwarding paths and returned paths
Forward
2
00 01 10 11
General slave-to-master transmission Intra-piconet unicast Inter-piconet unicast Inter-piconet broadcast
Due to the limited length of RV field (Routing Vector field), it is possible to need more than one PEH. (2) C/S field (1 bit): C/S field is the expanding of L_CH code, which sets the attribution of the packet to be either L_CH = 01 or L_CH = 10. LMP message (L_CH = 11) is not data message and is not necessary to travel over several piconets. (3) Reorder field (2 bits): Reorder field is used for the reordering of packets, and it allows at most 4-packets misarrangements. The current specification does not offer the reorder function, and it only applies ARQ protocol, which is a kind of “stop and wait” protocol, for transmission. That will decrease the performance of link throughputs. Our suggestion is to implement a protocol like “sliding window” with reorder scheme in link layer to increase throughputs. (4) Length field (5 bits): Length field records the length of RV field which is meaningful. (5) RV field (21 bits): RV field can have 0 to 7 elements, so the value of Length field is used to identify the number of meaningful elements in the RV field. Every node will inform it’s location to every device by broadcasting, and master maintains the routing vectors to form forwarding paths. If some slave wants to send the packet, it will send request to the master to get the routing vectors. Then the slave can fill the routing vectors into the RV field of PEH in every packet which will be sent out. RV field is filled with AM_ADDR, forward _ID, AM_ADDR, forward _ID, etc., in order. The first several sub-fields of routing vectors which are identified by Length field describe the routing path from the source device to destination. The remaining sub-fields are reserved for the function of backward trace. If the routing vectors are more than 6, additional PEHs will be needed.
677
master. In this case, the value of Ext, Length, and RV are zeros. As the master receives the packet, it identifies whether the destination device is itself by the value of the Length and routing vectors. • When the value equals 01, it shows the intra-piconet transmission which some slave delivers packets to another slave in the same piconet or the master delivers packet to some slave. In this case, Ext = 0 and Length = 3. If it is an intra-piconet unicast, the first sub-field in RV is the AM_ADDR of the destination node (slave). The AM_ADDR represents a member address and is used to distinguish between the active members participating in the piconet. When the destination node receives a packet, it could tell whether the destination is itself or keep forwarding packets from the value of Length and routing vectors. If the value of Length equals 3, the AM_ADDR of the destination node would be compared with the first element of the RV field. If they are the same, the packets are to the destination. If they are not the same, then there is a transmission error. The intra-piconet broadcast was already specified in specification. Within the Baseband Header, AM_ADDR field (3 bits) is filled with zero which means the broadcast of a packet to whole piconet. • When the value of Forward field equals 10, it stands for the inter-piconet unicast. In figure 3, for delivering data by inter-piconet unicast from s1 to s14, the values of PEH fields when the packet is in different nodes are shown in table 4. Every vector of RV in table 4 is a 3-bits number. If the slave connects with more than one master at the same time, it maintains a Forwarding Table. As an example, the Forwarding Table of s3 is shown in table 5. No matter how many masters (piconets) are connected with a slave at the same time, each piconet assigns an AM_ADDR (3 bits) for the unparked slave. So the slave that connects with multi-piconets owns multiple AM_ADDRs at the same time. For example, when m1 in figure 3 receives packets from s1, m1 will check if Length is equal to 0 or not. If the Length equals 0, the destination device will be itself and the transmission is general slave-tomaster transmission. Otherwise, m1 will check the first element (sub-field) of the RV, and then forwards the packet to s3. As s3 receives the packets, s3 will check
(6) The value of Forward field (2 bits) defines four different transmission modes: general slave-to-master transmission, intra-piconet unicast, inter-piconet unicast, and inter-piconet broadcast. • When the value equals 00, it means general transmission mode that is the transmission from a slave to the
Figure 3. Inter-piconet unicast.
678
W.K. LAI AND D.H. TAN
Table 4 The values of PEH fields from s1 to s14. Current node Ext C/S Reorder Length Forward
Routing Vector
s1
1 0
0 0
0 0
18 9
2 2
s3, m2, s6, m4, s9, m6 s11, m8, s14
m1
1 0
0 0
0 0
18 9
2 2
s3, m2, s6, m4, s9, m6 s11, m8, s14
s3
1 0
0 0
0 0
12 9
2 2
s6, m4, s9, m6, m1, s3, m2 s11, m8, s14
m2
1 0
0 0
0 0
12 9
2 2
s6, m4, s9, m6, m1, s3, m2 s11, m8, s14
s6
1 0
0 0
0 0
6 9
2 2
s9, m6, m1, s3, m2, s6, m4 s11, m8, s14
m4
1 0
0 0
0 0
6 9
2 2
s9, m6, m1, s3, m2, s6, m4 s11, m8, s14
s9
1 0
0 0
0 0
0 9
2 2
m1, s3, m2, s6, m4, s9, m6 s11, m8, s14
m6
1 0
0 0
0 0
0 9
2 2
m1, s3, m2, s6, m4, s9, m6 s11, m8, s14
s11
1 0
0 0
0 0
0 3
2 2
m1, s3, m2, s6, m4, s9, m6 s14, s11, m8
m8
1 0
0 0
0 0
0 3
2 2
m1, s3, m2, s6, m4, s9, m6 s14, s11, m8
s14
1 0
0 0
0 0
0 0
2 2
m1, s3, m2, s6, m4, s9, m6 s11, m8, s14
to their original positions. In addition, the value of Length field in the same PEH is subtracted by 6 since 2 elements of RV fields are processed (one for itself and one for m2). Then the processed packet is forwarded to m2. Because the value of Length field is not 0, similar procedures are repeated until packets are delivered to the destination. There may have more than one PEH. When there are more than one PEH, the first PEH is processed until it equals 0, then the second PEH is processed by intermediate nodes until it equals 0, and so on. Note that in the destination s14, only one element is processed for itself since the packet has arrived at the destination. Hence, the value of Length field is subtracted by 3 instead of 6. Also note that when the source is m1 instead of the AM_ADDR of the Baseband Header, it would be assigned s3 to represent that the packets are actually from the master m1 since the master does not have an AM_ADDR itself. • When it is inter-piconet broadcast (Forward = 11), the destination address is the master of the destination piconet. When the master of the destination piconet receives the inter-piconet broadcast message, it broadcasts the packet to all its active slaves. If the destinations involve multiple piconets, multiple connections between source and masters of destination piconets are established. From the above described, we know that only slaves are involved in updating PEHs which will ease that loads of the master.
Table 5 Forwarding Table. Node
forward_ID
Link to master ID
s3
0 2 3
m1 m3 m2
whether Length = 3 and Ext = 0 which mean there is no more PEH behind. If both are true, s3 will check the first element (AM_ADDR) to see if the destination is itself. If Length >3, s3 would refer to its Forwarding Table to get the direction to the source. The two former elements in RV would be moved to the last two elements of RV of the same PEH. At this time, because m1 is not in the RV, s3 gets the forward_ID of m1 from the Forwarding Table, and then s3 inserts the forward_ID into the fifth element of RV field. It is for keeping returned path that may be needed in sending acknowledgements from destination or establishing bidirectional connections or reserving bandwidth. The insertion of m2, m4, m6, and m8 are not necessary because they are already in s3’s RV fields. The purpose of processing RV fields by intermediate nodes is to record the intermediate nodes that the packet passes through. After s3 has processed the packet from s1, source address could be traced by the order of m1 and AM_ADDR field of Baseband Header. The other elements would be shifted two elements left compared
2.2. A reordering mechanism There are many packets and signals transmitting between Bluetooth devices, such as intermittent non-periodic data transmissions, frequent transmissions of small volumes of data, infrequent transmissions of larger volumes of data and synchronous connection-oriented data transmission. Some of them are real-time and crucial control messages which are used to control some devices such as Internet/Intelligence Appliances. Because of the limitation on free slots, some crucial control messages may be blocked in the buffers. For example, a packet that is the Head-Of-the-Line (HOL) packet in the master or slave queue is composed of multiple slots (3 or 5), and another packet that is the Second-Head-Of-Line (SHOL) packet in the master or slave queue is formed by a single slot. We are unable to send the HOL packet and a slot is wasted when the available slot is a single slot. Without reordering function, the SHOL packets that may be the crucial control messages are unable to be sent since the HOL packets are blocked in the queues. We can solve the issues by using the DM1 packets (single slot) for transmitting the crucial control messages. Due to the role of DM1 packet which belongs to both ACL and SCO links, we can interrupt with current SCO transmission to send the control messages. Specifically the DM1 packet could be transmitted with the highest priority without regard to reserved slots on SCO links.
A NOVEL SCATTERNET SCHEME WITH IPV6 COMPATIBILITY
3. IPv6 addressing mode and cellular structure for supporting handoffs and packets transmissions with other networks
679
last 48 bits can be used to distinguish between Bluetooth devices. 3.2. Cellular structure
In order to provide the communication between local wireless network (scatternet) and outer network (wired or wireless network), the address of Bluetooth device need be considered. For exchanging data and sharing resources with outer network, the TCP/IP protocol and HID (Health Information Designs) could be implemented on the upper layer of Bluetooth protocol stack (figure 4). Note that routing mechanism proposed in last section can still be used in this section. 3.1. Bluetooth IPv6 address format The IPv4 would be insufficient if each device such as a desktop, a peripheral equipment, an Internet/Intelligent Appliance, a laptop, a PDA, and a mobile phone all have dedicated IP addresses. DHCP (Dynamic Host Configuration Protocol) [9] or NAT (Network Address Translation) can be adopted to improve the situation. However, it will cause extra loads to the Bluetooth unit. There is no need to set up the DHCP or the NAT servers for just a small local Bluetooth network. In order to form scatternet anytime and anywhere, we utilize the IPv6 addressing format (figure 5) [6,7]. The IPv6 addressing format has been suggested by many researchers to be implemented in wireless networks. The former part of addressing is prefix (64 bits), and the remainder is divided into three fields, Master address (1 byte), Slave address (1 byte), and BD_ADDR (6 bytes). With 1 byte of master address, the maximum number of piconets to form a scatternet is equal to 256. Each piconet is allowed to maintain addresses of 256 slaves at most including active and parked nodes. The unique Bluetooth Device Address formed by the
The handoff happens frequently because of a short range of each Bluetooth piconet [1]. In our scheme, we combine the capability of cellular networks with the inherent flexibility, robustness and scalability of Bluetooth network to provide adaptive handoff and efficient location management of active and parked slaves. In figure 6, the CM (Control Master), maintains whole routing information data of the scatternet and plays a significant role in communication between local network and outer networks. The communication between scatternet and outer networks must take place through the CM. Figure 6 shows a cellular scatternet which consists of four piconets. In figure 6, when a Bluetooth device in piconet 1 wants to connect with the CM, the master or slaves of piconet 1 can page the CM or one of CM’s slaves in the first step. Although the master or any slave of piconet 1 can page the CM or one of CM’s slaves, here we let the master of piconet 1 to play the role of paging for simplicity. Only the master in a piconet is involved in paging. If the master of piconet 1 pages the CM directly, the role of the CM would be a slave. The transmission slot of the CM will be wasted because of the guard time needed to synchronize with the piconet. Hence the CM plays as a slave is unsuitable especially for the situation when the CM is connected to networks with high loads. Certainly, the slave of the CM could change into master through master-slave switch, but the generated overheads are long compared to guard time for changing frequencies. If the master of piconet 1 pages a slave of the CM which is called an access device, then the CM could keep playing the role as a master. The slave is now an access device which only forwards packets between the piconet and the CM. Although there is a limitation of up to 7 access devices, it is much better than the disadvantage of master-slave switch. If there are over 7 piconets which wish to connect with access devices, the connection still could be established by indirect way. For example, when seven piconets have already been connected with seven access devices, additional piconet can communicate with the CM by paging any slave of those seven already connected piconets. 3.3. Soft handoff
Figure 4. Bluetooth protocol stacks.
The handoff that the device moves from one piconet to another will be frequent in this structure [10]. ACL link utilizes
Figure 5. IPv6 addressing format for scatternet.
680
W.K. LAI AND D.H. TAN
Figure 8. Multiple routing paths for s3 to forward packets.
Figure 6. A Cellular scatternet.
will be received by s1 because of active link between s1 and piconet 1. The packets would be retransmitted in the ACL link if no acknowledgements of those packets are received. The details of registration when s1 is in piconet 1 and piconet 2 are described as follows. The mobile device will get a unique care-of address depending on the location which the handoff takes place. In this condition, when s1 enters the range of piconet 1, the first step is to connect with piconet 1. At this time, s1 gets a careof address from m1 and registers to the CM that maintains a mapping table. We assume that M = 1 means piconet 1, the AM_ADDR assigned for s1 from m1 is 2, and the unique BD_ADDR of s1 is 4F03:72B4:3C57. Then the care-of address is as follows: prefix
Figure 7. Handoff and registration inside Bluetooth network.
the remaining slots not used by SCO link and is suitable for scheduling. There are two distinctive features for the Bluetooth cellular structure:
01
02
4F03:72B4:3C57
While s1 connects with piconet 2 in the overlapped area, another care-of address is assigned for s1. We assume that M = 2 means piconet 2, the AM_ADDR for s1 from m2 is 5. The care-of address is as follows: prefix
02
05
4F03:72B4:3C57
(1) The device can keep connections with more than one master when it passes through the handoff area of two piconets. The handoff area is the area which is covered by two or more piconets. Note that the device only synchronizes with one master at one time although many connections are simultaneously maintained.
While s1 enters piconet 2 and gets a care-of address, it registers to the CM instead of the HA (Home Agent). In the mean time, HA forwards the packets of s1 to the CM. No registration to the HA is necessary. Hence, it will reduce the wastage of bandwidth used in transmitting signals between slaves and the HA.
(2) A Bluetooth device moving within a scatternet only needs to inform the CM. The database of home agent is not changed.
3.4. Packets transmissions with other networks
Each Bluetooth device can connect with more than two piconets at the same time. As the device moves to cross boundary between two piconets, the probability of losing packets is lower, even though the mobile devices move in a high speed or under the worst circumstance such as electricity shortage. Figure 7 shows s1 moves from piconet 1 to piconet 2. For example, s1 connects with m1 and m2 while on the travel path in the overlapped area of piconet 1 and piconet 2 (figure 7). The following packets can be received through piconet 2 later after s1 registers to m2, and the packet on the fly to piconet 1
The slave can participate in more than one piconet, so the forwarding path of the slave will be probably more than one. When a master is busy in processing other slave’s requests, the slave can send the packets through another master which is not busy to the destination device. For example, in figure 8 when s3 wants to send the packets to the CM, the forwarding path can be chosen from multiple routing vectors by a weighted function such as the number of hops from s3 to the CM (distance). This kind of mechanism for choosing a best path is called the Weighted Best-Effort (WBE) mechanism. If multiple paths are chosen randomly without regarding weight,
A NOVEL SCATTERNET SCHEME WITH IPV6 COMPATIBILITY
it is named a Best-Effort (BE) mechanism. If the forwarding path is chosen by the number of hops in the WBE mechanism, then both paths s3, m1, s1, CM and s3, m2, s2, CM will be chosen before the path s3, m3, s4, m4, s6, m5, s7, CM. If two paths have same hops, then one path is picked randomly. 3.5. Role and duty of the CM, masters, and slaves The CM is the main controller in the Bluetooth network. It is responsible for maintaining and refreshing the related data which cellular structure needs. If a node in a piconet attempts to connect with scatternet, the registration message must be forwarded to the HA via the CM. In that meantime, the CM generates a Routing Vector Table (RV Table) which records the routing vectors of every Bluetooth device within the CM’s range. The routing vectors denote the forwarding path from the device to the CM. The number of forwarding paths to every device is probably more than one. Hence, the CM must assign a weight to every forwarding path of every device within its range. The value of the weight can be made depending on the “distance”. The higher the weight is, the higher the priority would be. The movement of the device within the CM’s range will cause the modifications of RV Table. Both the forwarding path (routing vectors) and the weight will be probably changed after any movement of the device. Hence the CM must update the RV Table periodically. Another Table, Mapping Table, is used for mapping the BD_ADDR to new (M, S) pair, where M and S are master address and slave address, respectively. For example, in figure 7, when s1 enters piconet 2 from piconet 1, a new care-of address will be assigned to s1 and the registration message will be forwarded to the CM. No matter where s1 will be, Mapping Table maintained by the CM will indicate the current location by mapping BD_ADDR to new (M, S). When s1 enters the range of piconet 1 (care-of address = prefix: 0102:4F03:72B4:3C57), the BD_ADDR of Mapping Table will be mapped to (1, 2). While s1 enters piconet 2 from piconet 1 (care-of address = prefix:0205:4F03:72B4:3C57), the BD_ADDR will be mapped to (2, 5). The packets to s1 will be forwarded by looking up Mapping Table. Note that external nodes out of the CM’s range just recognize the address (prefix:0102:4F03:72B4:3C57) which is registered to the HA only when the Bluetooth device s1 connects with the scatternet the first time. Each device (a master or a slave) forwards packets to external nodes by inserting the routing vectors into PEH from the CM’s RV Table. The master is responsible for calculating and recording the shortest path to the CM. Implementing buffers for soft-handoff retunneling is another duty of the master. Depending on the destination address of packets, the master can forward packets if the master is not the destination or save the packets if the master is the destination. If the master itself would send the packets out, it also must get the information of routing vectors maintained by the CM. Then the master can fill the RV field of PEH with the highest priority of routing vectors.
681
One of the duties of the slave is to maintain a Forwarding Table. The slave forwards the packets to the master by looking up the Forwarding Table. After being assigned a care-of address while handoff, the slave would register to the CM or the HA, depending on the slaves are within the same area of the CM or the covered area of other CM. The slaves may receive the missing packets from previous master by the help of retunneling. After handoff, the slaves forward or receive packets depending on destination addresses of packets.
4. Performance analysis and simulation results As we described above by introducing PEH, our scheme allows Bluetooth devices to form the scatternet that current specification does not describe how to implement. Due to the reordering function implemented in PEH, the link throughput increase substantially. Four simulations are performed. The first simulation focuses on the transmission of data packets without reordering. The second simulation is the transmission of data packets with reordering. Then we simulate the BE mechanism with reordering. Finally, the WBE mechanism with reordering is simulated. 4.1. The simulation environment The simulation environment is described as below. The scatternet is formed from various numbers of piconets which are formed by one master and a random number (1–7) of slaves. The numbers of piconets simulated are 1, 5, 10, 15, 20, 25, and 30. The master and each slave would send and forward four kinds of data: (1) intermittent non-periodic data transmissions (including bursty data), (2) frequent transmissions of small volumes of data, (3) infrequent transmissions of larger volumes of data, and (4) real-time, constant rate, and synchronous data. The first three kinds are transmitted in ACL links and the last one is transmitted in SCO links. The transmission is chosen randomly from four kinds of data. The idle period for type 1 is set randomly between 1 and 6000 s and between 600 and 6000 s for type 3. The data size is chosen randomly between 1 to 10 Kbytes for type 1, between 5 to 2000 Kbytes for type 3, and between 3 to 1000 Kbytes for type 4. For type 3, the idle period is fixed at 60 s and the data size is 0.3 Kbytes. The parameters of simulations are shown in table 6. The throughputs between a random selected node and the CM are presented in the following. Table 6 Parameters of simulations. Data kind
Idle period within transmission
Data size (Kbytes)
Packet types
1 2 3 4
1–6000 (s) 60 (s) 600–6000 (s) N/A
1–10 0.3 5–2000 3–1000
DM1, DH1, DM3, DH3, DM5, DH5 DM1, DH1 DM3, DH3, DM5, DH5 HV1, HV2, HV3
682
W.K. LAI AND D.H. TAN
Figure 9. Throughputs versus number of piconets (without reordering function).
4.2. Simulation results and discussion Figure 9 shows the results of throughputs versus number of piconets without reordering. We can find that the throughputs decrease rapidly when the number of piconets increases. The effects of decrease in throughputs caused by increasing number of piconets on multi-slot packet are more obvious than single one. Especially when the SCO link occupies the transmission slot, the multi-slot data are hard to be sent or be forwarded. For example, when the Head-of-the-Line (HOL) packet is the multi-slot packet, the free single slot that the master leaves for the slave cannot be used. It can be the situation that the free single slot just can satisfy the Second-Headof-the-Line (SHOL) packet which occupies a single slot. But the SHOL packet can not utilize the free slot without reordering mechanism. Reorder field (2 bits) defined in PEH is used for the reordering of packets, which allows at most 4-packet disarrangements. Figures 10–12 show the comparisons of throughputs with or without reordering function by single slot packets (DH1,DM1), 3-slot packets (DH3,DM3) and 5-slot packets (DH5,DM5), respectively. From figures 10–12, we can find that the reordering function improves the throughputs of DH1 and DM1 packets, and the DH3 and DM3 packets also get some benefits from reordering function. But the effects of reordering function in DH5 and DM5 packets are imperceptible. In figure 12, the maximum number of piconets is 20 instead of 30. It is because when the number of piconets is greater than 20, the throughputs of DM5 packets are very small and negligible. The maximum number of piconets in figures 16–19 are also 20 because of the same reason. Figure 13 shows a Bluetooth device’s average throughputs versus number of piconets with and without reordering function. The throughputs of every Bluetooth device in the scatternet decrease with the increase of piconets. The device with reordering function has better performance than the device without reordering function as expected. The improvement
Figure 10. A comparison of DH1 packets and DM1 packets with and without reordering function.
Figure 11. A comparison of DH3 packets and DM3 packets with and without reordering function.
of performance is quite obvious with the increase of piconets because DH1 and DM1 packets are effectively utilized by reordering function. Figure 14 shows the throughputs versus number of piconets of data transmission in a scatternet with Best-Effort mechanism and a slave is selected randomly to possibly connect with more than one piconet (master). The n link (n = 1–4) means that the slave connects with n piconets (masters). Each link has the same priority in forwarding packets if the connected master is not in busy states. When the number of piconets is small (e.g., 5), a slave with 2 or 3 links has better performance than a slave with 4 links. Although packets can be transmitted via more links, some of the links may lead
A NOVEL SCATTERNET SCHEME WITH IPV6 COMPATIBILITY
683
Figure 14. Throughputs versus number of piconets for Best-Effort mechanism without priority (DM1 packets).
Figure 12. A comparison of DH5 packets and DM5 packets with and without reordering function.
Figure 15. Throughputs versus number of piconets for Best-Effort mechanism with priority (DM1 packets).
Figure 13. Each Bluetooth device’s average throughputs.
to longer routing path to the CM which offsets the effects of increasing links. With the increase of piconets, a slave with more links tends to have a better throughput. This is because when the number of piconets increases, the busy probability for any master that a slave is connected to is also increased. A slave with more links now has better chance of having an available link to transmit packets. Note that in figure 14 and following figures, when there is only one piconet, there is also only one link between the master and the slave. Figure 15 shows the throughputs versus number of piconets of DM1 packets of multi-links with priority. Because of the priority of each path, the packets might give up the right of sending packets on some links because of lower priority. Since we map shorter “distance” with higher priority, the packets tend to be sent on high priority links more than on low priority links. This scheme will reduce the extra loads
Figure 16. Throughputs versus number of piconets for Best-Effort mechanism without priority (DM3 packets).
of reordering in the CM and the risk of traveling many hops before arriving CM. From figure 15, we can find that the multi-link transmissions get better performance than single-link transmissions. We can see that with priority, the throughputs are always im-
684
Figure 17. Throughputs versus number of piconets for Best-Effort mechanism with priority (DM3 packets).
W.K. LAI AND D.H. TAN
Figure 20. Each Bluetooth device’s average throughput with multi-links and BE mechanism.
Figure 21. Each Bluetooth device’s average throughput with multi-links and WBE mechanism. Figure 18. Throughputs versus number of piconets for Best-Effort mechanism without priority (DM5 packets).
Figure 19. Throughputs versus number of piconets for Best-Effort mechanism with priority (DM5 packets).
proved with the additions of more links to choose. In addition, the decreasing rates in bandwidths with the increasing number of piconets are also slower. Figure 16 shows simulation results of DM3 packets with BE mechanism. The same problem as in transmitting DM1 packets is that although the DM3 packets can be transmitted via more links, some of the links may lead to longer routing path to the CM. Hence, the additions of more links do not in general produce better throughputs as wished. The improvement of performance by adding the priority mechanism is shown in figure 17. Now the throughputs are improved with the selection of more links. WBE mechanism gets better performance than BE mechanism on both DM1 and DM3 packets. Figure 18 shows results for DM5 packets. When the number of piconets is 5, a slave with 2 or 3 links has better performance. When the number of piconets increases to 15 and more, more links do not show better throughputs. This is because the reordering function tends to favor 1-slot or 3-slot packets. Figure 19 shows the performance of WBE mechanism. We can find that the performance improvement is not
A NOVEL SCATTERNET SCHEME WITH IPV6 COMPATIBILITY
obvious. So the WBE mechanism improves performance of small slots more than large slots. For all situations, we can see WBE mechanism with reordering function performs better than BE mechanism without reordering function. Figure 20 shows that the average throughputs of a Bluetooth device for all three types of packets with multi-links are not in general better than the average throughput of each Bluetooth device with single link by BE mechanism. From figure 21, we can find that with WBE mechanism, the one with more links gets better performance than the one with less links. 5. Conclusions and future work Because specification 1.1 does not describe the algorithms or mechanisms for a scatternet, we design possible extensions in headers of payloads to current Bluetooth architecture for supporting packet transmission in scatternets. In order to support handoffs and communications with other networks, we proposed using IPv6 packet formats. The role of masters, slaves, and the control master in the cellular structure are discussed in detail. Our design allows at most of 4-packet disarrangements. Simulations results show that BE mechanism with reordering function is far better than BE mechanism without reordering function. Simulations results also show WBE mechanism always has better performance in terms of bandwidths compared to BE mechanism. The future work will focus on switches between unparked and parked slaves to increase capacity in Bluetooth. Acknowledgements This work is supported by NSC of Taiwan under contract numbers NSC-90-2511-S-110-016 and NSC-90-2213-E-110041. References [1] S. Baatz, M. Frank, R. Gopffarth, D. Kassakine, P. Martini, M. Schetelig and A. Vilavaara, Handoff support for mobility with IP over Bluetooth, in: Proceedings of 25th Annual IEEE Conference on Local Computer Networks (2000) pp. 143–154. [2] P. Bhagwat and J. Thomas, A Routing Vector Method (RVM) for routing in Bluetooth scatternets, in: IEEE International Workshop on Mobile Multimedia Communications (MoMuC ’99) (1999) pp. 375–379.
685
[3] Bluetooth Special Interest Group, http://www.bluetooth. com/ [4] R. Castaneda and S.R. Das, Query localization techniques for ondemand routing protocol in ad hoc networks, in: Proc. of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (August 1999) pp. 186–194. [5] Y.-L. Chang and C.-C. Hsu, Routing in wireless/mobile ad-hoc networks via dynamic group construction, Mobile Networks and Applications 5(1) (2000) 27–37. [6] H.-C. Chao, Y.-M. Chu and M.-T. Lin, The implication of the nextgeneration wireless network design: cellular mobile IPv6, IEEE Transactions on Consumer Electronics 46(3) (August 2000) pp. 656–663. [7] G. Chiruvolu, A. Agrawal and M. Vandenhoute, Mobility and QoS support for IPv6-based real-time wireless Internet traffic, in: IEEE International Conference on Communications (ICC ’99) (1999) pp. 334–338. [8] D. Famolari and P. Agrawal, Architecture and performance of an embedded IP Bluetooth personal area network, in: IEEE International Conference on Personal Wireless Communications (2000) pp. 75–79. [9] C.E. Perkins, Sun Microsystems, “Mobile IP”, IEEE Communication Magazine 35(5) (1997) 84–99. [10] C.E. Perkins and K.-Y. Wang, Optimized smooth handoffs in Mobile IP, in: Proceedings of IEEE International Symposium on Computers and Communications (1999) pp. 340–346. [11] S. Singh, M. Woo and C.S. Raghavendra, Power-aware routing in mobile ad hoc networks, in: Proc. of ACM MOBICOM (1998) pp. 181–190. [12] Specification of the Bluetooth System core 1.1. [13] W. Su, S.-J. Lee and M. Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management 11(1) (2001) 3–30. [14] J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, in: Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (August 1999) pp. 7–14.
Wei Kuang Lai received the B.S. degree in electrical engineering from National Taiwan University in 1984 and the Ph.D. degree in electrical engineering from Purdue University in 1992. He joined the faculty of Department of Computer Science and Engineering, National Sun Yat-Sen University in August 1992 and is now a professor. His research interests are in high-speed networks and wireless networks. E-mail:
[email protected]
Der Hwa Tan received the M.S. degree from Department of Computer Science and Engineering, National Sun Yat-Sen University, Kaohsiung, Taiwan, in 2001. His main interest is in wireless protocols.
