A Social Group-aware and Tunneled Scatternet Formation Scheme Myeong-a Yang, Yangwoo Ko, Dongman Lee Information and Communications University {may, newcat, dlee}@icu.ac.kr Abstract Bluetooth is a major technology for short range wireless communication. Scatternets expand its use to larger networks. If communication patterns are known before scatternet formation, frequently communicating pairs could be connected with fewer hops to enhance performance. Communication patterns are obtainable by observing traffic, but it is ineffective in a pervasive computing environment where interactions are mostly spontaneous. We propose to use social group membership as an estimate of communication patterns. The proposed scatternet formation scheme forms a scatternet per a social group and then connects scatternets through tunnels. In order to ensure that each communication pair has a reasonable share of bandwidth, the proposed scheme considers the numbers and the positions of the tunnels. Simulation results show that the proposed scheme not only enhances the total throughput of scatternets but also shares network capacity more fairly among communication pairs.
1. Introduction Bluetooth [1] enables cell phones, PDAs, and notebooks to be connected without wire and is used to form a Wireless Personal Area Network (WPAN). The basic communication unit of Bluetooth is a piconet that consists of one master and up to 7 slaves. To connect more than 8 Bluetooth devices, multiple piconets are formed as a scatternet and several scatternet formation schemes have been proposed [3][4][5][6][7][8]. One of the important goals in scatternet formation is to maximize the performance of a scatternet such as the capacity of a scatternet [4][7]. Most of scatternet formation schemes form a scatternet by connecting all devices within an area, which may cause frequently communicating pairs to have longer path lengths than optimal ones. If devices are clustered to form a collection of smaller sized scatternets or piconets, frequently communicating pairs will have shorter average paths so the
performance will be improved. Manish et al. [8] introduce a Communicating Group (CG), defined as a group of mobile devices with frequent data transfers amongst themselves. CGs are identified by observing traffic and finding frequently communicating peers. However, this scheme does not work well in a pervasive computing environment where CGs can emerge and disappear dynamically due to spontaneity of interactions because it is difficult to reliably estimate the communication patterns. In a pervasive computing environment, interactions between two specific people may last for only a short time. interactions between people happen spontaneously, and may last for only a short amount of time especially between infrequently communicating peers. In this case, identifying a CG for them may take similar to or longer than the length of their communication session and then the identified CG becomes useless. . In a real world, a person in general belongs to a social group and interacts with others who belong to the same social group more often than those who do not [2]. In this paper, we propose an efficient scatternet formation scheme exploiting social group membership as an approximation of a CG. Even though interactions between two specific people will not last for long time, communication with the same social group member may take place with higher possibility than that with other group members. We assume that each person knows which social groups he or she belongs to. Devices belonging to the same social group form a piconet or a scatternet using the most well known scatternet formation scheme, TSF [6]. When there is a need to interconnect a social group with other social groups which usually lasts for a shorter amount of time than interactions between intra-group members, a set of tunnels is selected using the topology information of the constituent scatternets and interconnects them through the tunnels unlike the existing schemes in which the scatternets are merged into a single scatternet. When selecting tunnels, the proposed scheme takes into consideration the number of hops and branches and traffic distribution. Our scheme not only enhances the total throughput of scatternets but also shares network capacity more fairly among communication pairs. The simulation
results show that our scheme achieves higher average TCP throughput and shows a smaller variance than TSF. The remaining sections are organized as follows. Section 2 briefly explains related work. Section 3 introduces a sample scenario and describes what we should consider when forming a social group aware and tunnel based scatternet. The proposed scheme is described in section 4, and we show the performance of our scheme’s performance in section 5. Finally, section 6 concludes the paper.
2. Related Work 2.1. Social Group A social group is “a number of individuals, defined by formal or informal criteria of membership, who share a feeling of unity or are bound together in relatively stable patterns of interaction” [2]. A person can become a member of social group when there is consensus among group members. The main concerns in [2] are the relation between a group member and his or her devices, the format of user group profile, and membership management. It does not consider how to efficiently facilitate communication among social groups, which is the main theme of our work.
2.2. Bluetooth and Scatternet Formation The Bluetooth Specifications 1.2 [1] defines the operation of Bluetooth and its protocol. Bluetooth differs from a contention–based protocol such as IEEE 802.11, since Bluetooth devices form master-slave links and each slave adjusts its communication frequency hopping sequence to that of its master. Bluetooth adopts a time division duplex communication scheme, where the master decides which slave communicates with itself in next time slot. A master has up to 7 slaves and they form a piconet. A scatternet is proposed to interconnect more than 8 devices, but it has not been standardized yet. There have been several scatternet formation schemes such as Bluemesh[3], Bluenet[4], Shaper[5], and TSF[6]. Scatternet formation schemes can be classified by the resulting topology (for example, tree or mesh), by the type of bridge node (for example, master-slave or slave-slave), and by whether all nodes are in transmission range or not. Most of the existing scatternet formation schemes focus on the formation of one scatternet without considering social relationships among devices (or their owners). Manish et al. [8] proposes the use of a Communicating Group (CG), defined as a group of mobile devices with frequent data transfers amongst
themselves, and which forms different piconets for different CGs. This allows simultaneous communication in different CGs and hence leads to higher throughput, lower delays and less packet drops. This scheme analyzes traffic flow patterns to identify CGs. It takes relatively long time compared to communication session in pervasive computing environment so identified CGs becomes obsolete quickly. Moreover, even though [8] suggests the use of CGs, it does not propose a concrete scheme for forming and adapting piconets to the current state of CGs.
3. Design Consideration 3.1. Scenario Our scenario is extended from that of [2]. Several students are taking a course and they are divided into three groups for a term project. Let’s call them group A, B, and C. We assume that all students have Bluetooth enabled devices. During the class, the professor asks the students to discuss a subject related to the class with group members and to present the relation of their term project with this topic. Groups A, B, and C form individual networks and start discussion. While discussing, group members exchange related data and participate in a collaborative review process while preparing the presentation material. After discussion, the three groups need to be interconnected into a large network in order to enable students to exchange presentation materials or give comments in the middle of a presentation. In addition to the inter-group communication, there is also continuous intra-group communication for sharing thoughts with the others in the same group.
3.2. Social Group-aware Scatternet Manish et al. [8] propose to observe traffic among nodes in order to group a collection of nodes in a space into subgroups of frequently communicating nodes. However, interconnections between identified subgroups may last for only a short time due to spontaneity of interactions and CGs for them quickly become obsolete in a pervasive computing environment. We need an alternative way to find communication patterns that are stable over time.more efficiently. In a real world, as exemplified above, a person usually belongs to a social group and communication mainly happens among social group members for a considerable amount of time for collaborative activity [2]. Therefore, Instead instead of forming a single scatternet, it is more appropriate to form a separate scatternet for devices belonging to the
240 220 200 180 Throughput (Mbps)
same social group and provide a way to connect corresponding scatternets when there is a need of interactions across social groups. To support communication across social groups, their corresponding scatternets need to be interconnected. We call this interconnection as a tunnel. Communication pairs across social groups have longer paths than that of within groups, so they will show lower throughput. The path length of an inter group communication pair can be reduced by adding more tunnels. For example, if there are two string (linear?) topology whose numbers of nodes are 100 (too big!); two tunnels that composed of both 33rd nodes and both 66th nodes shorten average path lengths than one tunnel that consists of both 50th nodes. However, too many tunnels decrease the capacity of the entire network because an additional tunnel increases the number of branches per node. So the number of tunnels should be such that the path lengths of inter-group communication pairs are short (short 라고 하면 너무 모호하지 않나? optimal 이라 고 하면 안되나? 경로 길이를 가장 짧게 해주는 것 은 아니니, optimal 이라고 부르기는 힘들다고 생각 합니다 bandwidth 관점에서 보면 optimal 한 거 아 닌가? 즉 tunnel 이 너무 많아서 bandwidth 가 줄어 들지 않는 범위 안에서 최대한 패스를 짧게 하는 것이라면 그런점에서는 optimal 한 것이죠. 우리 스킴이 그런지 아닌지는 모르겠고) while the network capacity is not reduced significantly. We must consider the position of each tunnel as well because it determines traffic distribution. Tunnels forward inter group traffic from one scatternet to another, so all inter-group traffic is concentrated in tunnel nodes and their neighbors. If they also forward a majority of intra group traffic, they may become a bottleneck. So the tunnel nodes should be selected from the nodes in which intra-gorup traffic is less concentrated. Figure 1 shows the distribution of TCP throughput per communication pair in a typical scatternets of 20 nodes. TCP throughputs are sorted in a decreasing order. As you see, a few communication pairs use the majority of network capacity, while most pairs utilize very low bandwidth. Even though this problem is inevitable except for star topology, we need to alleviate this unfairness. When determining the number and the positions of the tunnel, we should consider fairness among intra-group traffic as well.
160 140 120 100 80 60 40 20 0 Communication pairs
Figure 1. Distribution of TCP throughput per communication pairs
4. Proposed Scheme This section describes an overall structure of the proposed scheme and the metric that is helpful for choosing tunnel nodes. We will then explain the proposed scatternet formation scheme in detail.
4.1. Assumptions and overall structure We assume that each person knows which social groups he or she belongs to. Devices that belong to the same social group form a piconet or a scatternet using an existing scatternet formation scheme. Our current implementation uses TSF [6]. As exemplified in the scenario given in Section 3.1, there is a need to interconnect a social group with other social groups. We also assume that this information of when and to which social group they should be connected is known to member nodes out of band. A Representative of each scatternet establishes a link to share information needed for forming tunnels. The election of a representative node may be different depending on a scatternet formation scheme. For easier implementation, we assume that representative nodes are predefined. This assumption is quite reasonable because a social group usually has a leader (for example, the term project leader in our scenario). After establishment of a link, we can select a set of tunnels based on the shared topology of the constituent scatternets. As described Section 3.2, we need to consider the number and the positions of the tunnels. For this purpose, we define a metric that estimates the
performance of a scatternet, which we will describe in Section 4.2. Each representative node evaluates the metric and finds the best tunnels as described in Section 4.3.
4.2. Proposed Metric Our metric calculates the lower bound of the maximum throughput that a communication pair can have. A scatternet that maximizes this metric also maximizes the throughput of traffic that has the lowest throughput, for example, inter-group traffic that passes a bottleneck. Therefore, a scatternet with a high metric value minimizes variations of the throughput of communication pairs and shares capacity more fairly. The proposed metric considers the following: 1) the path lengths of communication pairs (or CP hereinafter), 2) the number of branches per node, and 3) the link capacity per CP. Since a node utilizes one link at time, overall performance degrades if we increase the number of branches to reduce the average path length. Meanwhile, if we reduce the number of branches per node, latency becomes longer due to the increase of the average path length so that overall throughput also degrades. Link capacity per CP is defined as a reciprocal of the number of CPs whose traffic passes through the link. A link that has the lowest link capacity per CP becomes a bottleneck in a scatternet because the performance of each CP will be bound by a link with the lowest link capacity. Calculating link capacity per CP is done in two stages. In the first stage, we count the number of CPs whose traffic passes a link and take an inverse of it. For example, in Figure 2(a), if we assume that all source-destination pairs send data, there will be three CPs: (u, v), (u, w), (v, w). (u, v) and (u, w) will use link A while (u, w), (v, w) will use link B. Therefore the link capacity per CP of A is 1/2 and that of B is also 1/2. In the next stage, we calculate the weighted link capacity per CP that considers the number of branches. The weighted link capacity per CP is the link capacity per CP divided by the number of branches of neighbor nodes. Between two neighbor nodes constituting a link, we only consider the node with more branches. (Here, we assume that each node spends the same amount of time with any link.) In Figure 2(b), since node x and node y has two links, if the load per link for link C is 1/8, its weighted load per link is (1/8)/2 = 1/16. Since node y has 2 links while node z has 3 links, if link D’s load per link is 1/9, its weighted load per link is (1/9)/3 = 1/27. A u
B v
(a)
w
C
D
x
y
z
(b) Figure 2. Link capacity per CP Based on weighted link capacity per CP, we can obtain the total network flow. It is a sum of the individual flow of each source-destination pair. An individual flow means how much capacity a pair can occupy for a given capacity. The individual flow of a pair is the minimum link capacity per CP on their routing path. Since a longer path increases an error rate, throughput decreases as a path length increases. So the total network flow is divided by an average hop count. In summary, the proposed metric can be written as follows. TotalNetworkFlow Metric = AverageHopCount AverageHopCount =
∑ PathLengthOfCP
i
i
NumberOfCP
TotalNetworkFlow = ∑ IndividualFlowOfCPi i
IndividualFlowOfCPi = min Link j CapacityPerCPi j
4.3. Tunnel Selection Scheme In this section, we will explain a scatternet interconnection procedure that selects tunnels between two social groups wanting interconnection.(interconnection procedure 에 대한 설명을 넣으라는 것이 아니라 그 procedure 가 어 떤 형태로 구현되느냐 하는 것을 교수님이 질문하 신 것 같습니다. 즉 그 프로시져가 어떤 응용 프로 그램의 일부인지 아니면 프로토콜 스택의 일부인 지. 만약 후자라면 누가 그것을 trigger 하는지 등 을 설명해야 한다는 것이죠. 아래에도 그냥 그림 만 들어 있는데 추가 또는 변경되는 구성요소가 뭔지 그리고 그 역할이 무엇인지 얘기하지 않으면 이해하기가 힘들겠지요.) If two social groups need to be connected, one of the users such as the leader of a group initiates the interconnection procedure with his or her Bluetooth device. This device becomes a representative node of a group. The interconnection procedure sends a connection request to the scatternet formation component of the Bluetooth stack with the counterpart scatternet’s identifier. The same procedure happens in the counterpart scatternet. The scatternet formation component starts an inquiry procedure with Bluetooth which results in a link between the two representative nodes. One of these nodes that receives an inquiry packet becomes a master representative
node and the other one does a slave representative node.
representative nodes should be removed except when it is a tunnel.
5. Evaluations
HCI (and scatternet formation procedure)
Figure 3. Bluetooth protocol stack The scatternet formation component is notified via a callback at the end of the link establishment procedure. The callback function of the slave representative node sends its scatternet topology to the master representative node. Discovering the scatternet topology is out of this paper’s scope, but this information is easily obtainable. For example, all nodes know the overall topology in SHAPER [5], and the root remembers the topology in TSF. Upon receiving the topology of the counterpart scatternet, the master representative node computes which set of tunnels maximizes the proposed metric. After computation, it sends the result to the slave representative node. Each representative node sends a tunnel establishment command to the first tunnel node candidate. Two tunnel node candidates establish a link or a tunnel using the same link establishment procedure explained above. A tunnel node candidate reports its success or failure of the tunnel establishment to the representative node of its group. After receiving the result of tunnel establishment, the representative node initiates additional tunnel establishment if needed. Otherwise, it ends the tunneled scatternet formation. As described above, tunnels are established one after another. There are two reasons for sequential construction of tunnels. First, if several devices transmit an inquiry packet simultaneously to establish links, packets will probably collide and thus no link could be constructed. Second, the tunnel establishment procedure sometime fails due to the absence of a counterpart device or for other reasons. Therefore, the representative node should know if tunnel establishment succeeds or fails so that it can decide whether to move to the next tunnel setup or to select another tunnel candidate. Once all tunnels are established, a temporary interconnection link between
Yangwoo Ko @ ICU 님의 말: Maneshi 논문에서 CG 부분은 달랑 한두 패러그래 프 뿐이고 Yangwoo Ko @ ICU 님의 말: 아이디어 차원에서만 얘기한거라 구체적으로비교 하기가 사실상 어렵다는 얘기를 좀 넣으면 어떨지 요? thodlee 님의 말: 고양우씨가 제시한 것은 perf evaluation 에서 얘 기하면 thodlee 님의 말: 되겠네요
5.1. Performance comparison of group-aware scatternets and group-oblivious scatternets Our simulation is based on Blueware [9] which implements most of the functions that a Bluetooth device should provide, and also supports an implementation of TSF. Table 1 compares two cases: group-aware scatternet and group-oblivious scatternets. A group-aware scatternet refers to a scatternet that is an interconnection of a set of socially grouped devices while a group-oblivious scatternet refers to a scatternet that is formed by connecting all devices within an area. The group-aware scatternet formation simulations start with 20 Bluetooth devices and form two small sized scatternets, each of them having 10 devices. Two scatternets are then interconnected by a set of tunnels that have the highest metric values. The group-oblivious scatternet formation simulations start with 20 devices and form a different topology according to a different seed number. We repeat the simulations with different traffic patterns 20 times for a given topology. We set the number of intra-group traffic twice of that of intergroup traffic since we assume that intra-group members will communicate more frequently. This traffic pattern is applied to the rest of the paper. Group-aware scatternet records a higher average TCP throughput for intra-group traffic and shows lower variance as well. Lower variance means that the throughput distribution among CPs is closer to an average, so a group-aware scatternet permits CPs to share network capacity more fairly. In addition to overall performance, group-aware scatternets offer higher bandwidth to intra-group traffic without sacrificing much inter-group traffic. Table 1. Performance comparison of group aware scatternets and group unaware scatternet
Group aware Inter Intra group group traffic traffic Average TCP Throughput (Kbps) Standard deviation for all CPs
Group unaware Inter Intra group group traffic traffic
29.1
52.8
34.8
33.7
55.7
65.9
72.1
77.3
5.2. Relation between the metric and TCP throughput This section shows the relation between the proposed metric and the TCP throughput, which is depicted in Figure 3. The y axis is the average TCP throughput of inter-group traffic from 20 experiments and the x axis is the metric value of a given tunneled scatternet. We can conclude that the proposed metric is suitable for evaluating a tunneled scatternet since the proposed metric and the TCP throughput of intergroup traffic has a positive correlation.
Communicating Group (CG), a group of devices that frequently communicate, and a scatternet constructed according to CG shows high throughput. Identifying CGs takes quite amount time compared to the session time in pervasive computing environments and identified CGs become obsolete quickly. ( 이 에 대 한 우 리 의 방 법 요 약 ; ) Therefore we propose to use social group as an alternative of CG. And if there are occasional needs to communicate across social groups, we interconnect them through tunnels. We also introduce a metric that is useful for selecting a set of tunnels that interconnect two social groups. Our metric takes into consideration the number of hops and branches, and the link capacity per communication pair. ( 성 능 평 가 결 과 요 약 ;) Simulation results demonstrate that a scatternet formed by our scheme shows higher performance than group-oblivious scatternets formed by an existing scatternet formation scheme. We also show that the proposed metric and the TCP throughput have a close and positive correlation. We compare the performance between group-aware scatternets and group-oblivious scatternets, both of them are based on TSF. Additional experiments are needed to demonstrate that our scheme is also an improvement compared to other scatternet formation schemes besides TSF.
7. References
Figure 3. Relation between the proposed metric and the TCP throughput of inter-group traffic
6. Conclusion (많은 수의 디바이스가 연결되는 스캐터넷 에 서 의 formation 문 제 점 제 시 ; ) Most of scatternet formation schemes form a scatternet by connecting all devices within an area, so frequently communicating pairs devices cannot occupy obtain reasonable capacity due to long average path lengths. (average 가 커진다 고 해서 꼭 나쁜건 아니죠. 자주 통신하는 놈들이 가까이 있으면 되니까. 이상적인 CG 의 경우. 앞의 어디선가 설명한 것 처럼 자주 통신하는 장 치인데도 서로 멀리 떨어지는 “경우도 있다.” 그 런 경우에는 문제가 된다. 안그러고 이렇게 얘기 하면 항상 문제가 된다고 과장되고 얘기하는 것으 로 비칩니다.) Manish et al. [8] proposes the use of a
[1] Bluetooth Specification Version 1.1, Bluetooth Special Interest Group, http://www.bluetooth.com, February 2001. [2] B. Wang, J. Bodily, and S. K. S. Gupta, “Supporting Persistent Social Groups in Ubiquitous Computing Environments Using Context-Aware Ephemeral Group Service”, in Proceedings of the Second IEEE Annual Conference on PERCOM 2004. [3] C. Petrioli, and S. Basagni, “Degree-constrained multihop scatternet formation for Bluetooth networks”, IEEE Globecom 2002, Taipei, Taiwan, November 2002. [4] Z. Wang, R. J. Thomas, and Z. Haas, “Bluenet - a new scatternet formation scheme”, HICSS-35, Big Island, Hawaii, January 2002. [5] F. Cuomo, G. D. Bacco, and T. Melodia, “Shaper: a selfhealing algorithm producing multi-hop bluetooth scatternets”, IEEE Globecom 2003, San Francisco USA, December 2003. [6] G. Tan, A. Miu, J. Guttag, and H. Balakrishnan, “An efficient scatternet formation algorithm for dynamic environments”, in IASTED International Conference on Communications and Computer Networks, Boston, MA, November 2002. [7] T. Melodia and F. Cuomo, “Ad hoc networking with Bluetooth: key metrics and distributed protocols for scatternet formation”, Ad Hoc Networks, vol. 2, no. 2, pp. 109–202, April 2004. [8] M. Kalia, S. Garg, and R. Shorey, “Scatternet structure and inter-piconet communication in the Bluetooth system”,
in IEEE National Conference on Communications New Dehli, India, 2000.
[9] G. Tan, “Blueware:Bluetooth Simulator for NS.” MIT Lab. Comput. Sci., Cambridge, MA, October 2002.