A social group aware scatternet formation scheme

Abstract

1. Introduction
Bluetooth [1] is a representative technology for short range wireless communication. Bluetooth
enables cell phones, PDAs, and notebooks to be connected without wire and is used to form
Wireless Personal Area Network (WPAN). Minimum communication unit of Bluetooth is
piconet that consists of one master and up to 7 slaves. To connect more than 8 Bluetooth device
scatternet is proposed and researches are still in progress [3][4][5][6][8].
The goal of the most scatternet formation schemes proposed so far is either to minimize
scatternet formation time or to maximize the performance of formed scatternets. Traffic pattern
information is useful to construct an efficient scatternet [8], however it is very hard to reliably
estimate traffic pattern at formation time. In practice, a person will communicate more
frequently with persons belonging to same social group than with strangers belonging to other
social groups [2]. We can apply this observation to scatternet formation scheme so that the
scatternet can be built more efficiently. Our idea is to form small sized scatternets of socially
grouped devices and then interconnects these small groups through tunnels. The proposed
scheme enhances overall performance of tunneled scatternet since devices that may
communicate frequently will have low average path length.
(Following section~)

2. Related Work

2.1 Social Group

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.
Main concerns of [2] are the relation between a group member and his or her devices, the
format of social group definition, and membership management. It does not consider how to
efficiently facilitate communication not only within each social group but also 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 contention based protocol such as IEEE 802.11 since Bluetooth devices
form master-slave link and each slave adjusts its communication frequency hopping sequence
to that of its master. Bluetooth adopts time division duplex communication scheme and master
decides which slave communicates with itself in next time slot. A master has up to 7 slaves and
they form a piconet. Scatternet is proposed to interconnect more than 8 devices but it has not
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 resulting topology (for
example, tree or mesh), by type of bridge node (for example, master-slave or slave-slave), and
by whether all nodes are in transmission range or not. Most of existing scatternet formation
schemes focuses on formation of one scatternet without considering social relationships among
devices (or their owners).
[8] proposes concept of Communicating Group (CG), defined as a group of mobile devices with
frequent data transfers amongst themselves, and 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 pattern to identify CGs.
Even though this work presents a rough idea about CGs, but they do not propose a scheme that
dynamically forms piconet according to CGs and adopts piconets to the change of CGs.

3. Design Consideration

3.1 Scenario
Our scenario is based on that of [2]. Several students are taking distributed systems course and
they are divided into three groups to execute term project. For convenience, lets call them A, B,
and C group. We assume that all students have Bluetooth enabled devices. In class hour,
professor requests students that discuss a subject related to class with group members and
presents the relation of their term project and this topic. Group A, B, and C form individual
network respectively and start to discussion. In discussion session, each group members
exchange related data or participate in collaborate review process to making presentation
material. After discussion, each group should be interconnected to form a large network and
enable each group members exchange presentation materials or give a comment in middle of
presentation. (inter와 intra가 동시에 나타나는 시나리오가 더 좋지 않을까요? 이 시나리오는 두
phase로 쪼개져 있어서 취지가 잘 드러나지 않네요. 마지막 부분에 좀 더 얘기를 고쳐야 될 듯.)
Our work is based on the following scenario. In a conference room, most participants have
Bluetooth enabled devices and these devices form a scatternet to interact in an ad hoc manner. A
person may enter or leave the conference room in the middle of session, so member of the
network may change frequently. Another characteristic of the network is that each person
belongs to one of social groups. (시나리오가 추상적이네요. 좀 더 구체적으로 쓰면 어떨까요?)
(CG가 고려 대상이 아니게 되었으니, 시나리오는 필요 없지 않을까요?)

3.2 Social group aware scatternet

Most of scatternet formation schemes form a scatternet by connecting all devices within an area,
so devices that frequently communicate may scatter throughout the scatternet. If these devices
are clustered to form a smaller scatternet, average path length among frequently
communicating pair results will be shortened and hence improves performance. In real world
as exemplified above, a person belongs to a social group and people belong to same social
group would often interact each other. If socially grouped devices form small sized scatternets
and then these groups are interconnected through tunnels, it will result in higher throughput.
Table 1 demonstrates above argument. It contains two cases: group aware scatternets and group
unaware scatternet. Group aware scatternet refers to a scatternet that is an interconnection of a
set of socially grouped devices while group unaware scatternet refers to a scatternet that is
formed by connecting all devices within an area. Group aware experiments start with 20 free
devices and forms two small sized scatternets, each of them has 10 devices. Then two scatternets
are interconnected by different set of tunnels. Group unaware experiments start with 20 free
devices and forms a different topology according to different seed number. (social group과
traffic pattern과의 관계가 무엇인지 설명이 없네요. 그것이 없다면 임의의 패턴에 대하여 작은
그룹으로 나눈 후 연결하는게 좋다는 얘기가 되어버리고 결과적으로 social group은 무의미하다
는 얘기가 되는데…) We repeat simulations with different traffic pattern for 20 times for a given
topology. Group aware scatternets record high average TCP throughput and they show low
variance as well. In conclusion, group aware scatternets usually show better performance than
group unaware ones. (variance가 작아서 좋다는 얘기는 빠졌네요.)
Table 1 shows that TCP throughput of group aware scatternet is usually higher than that of
group unaware scatternet. (앞 문장은 표랑 해석이 매치가 안되고 암튼 좀 이상한데, 지금 group
unaware에 대한 데이터가 하나밖에 없어서 그렇습니다. group unaware 케이스에 대한 추가 실
험 결과 나오면 다시 바꾸겠습니다.…)

Group aware Group unaware

Average TCP Throughput (Kbps) 39.241.7 36.82
Variance among session throughput 1.3 2.4

Table 1. Performance comparison of group aware scatternets and group unaware scatternet
3.3 Scatternet evaluation metric
Connecting two social groups through tunnel(s) means that pre-formed two scatternets are
interconnected not are merged, so it does not modify existing scatternet topologies. In this
sense, APC is good metric when forming a scatternet but it is inapplicable with tunneled
scatternet. Without modification of pre-formed scatternets, there is high possibility that
tunneled scatternet has bottleneck. Therefore, new metric should consider distribution of traffic
throughout tunneled scatternet.
We simulate relation of APC and TCP throughput and we discover that APC is not useful when
evaluating interconnection of multiple scatternets. Table 2 shows TCP throughput of two
tunneled scatternets that have almost same APC value. As you can see from Table 2, TCP
throughputs in both cases are similar but 2 tunnels case has low variation value. It means that 1
tunnel case permits few communication pair to flow well thus others have problem with
communication. Even though both cases show similar APC values, a tunnel can become a
bottleneck when there is only one tunnel. If a tunneled scatternet has two tunnels, inter traffic
would be distributed and all communication pairs share network capacity more fairly.

2 tunnels (APC=0.008421) 1 tunnel (APC=0.008457)

TCP Throughput (Kbps) 37.6 38.1
Variation 344.9 447.0

Table 2. Performance comparison of two scatternets with similar APC values

In conclusion, to form an efficient scatternet, small sized scatternets of socially grouped devices
are formed and then these small groups are interconnected through tunnels. Compared to
common scatternet, tunneled scatternet may experience congestion. A tunnel formation scheme
should select tunnel(s) that distributes traffic by adjusting the number or position of tunnel(s).

4. Proposed Scheme
This section describes scatternet formation scheme by using social group.
이 섹션에서는 social group 을 이용해서 스캐터넷을 만드는 방법을 설명한다.

4.1 Overall structure

At first, we will define the concept of “tunnel” more precisely. A tunnel is a kind of master-slave
link that are is established for communication between two different scatternets. We choose
“tunnel” instead of “gateway” since two participants of tunnel belong to their own scatternet
while gateway commonly interconnects two networks alone. (무슨 얘기인지 모르겠네요.)
We assume that a person knows that which social groups he or she belongs. Devices that belong
to same social group form a piconet or a scatternet by using scatternet formation scheme such
as Bluemesh[3], Bluenet[4], Shaper[5], and TSF[6]. To form a group that only contains same
social group members, established connection should be cut off if two devices belong to the
other social group. (formation scheme인데 굳이 끊는 설명을 할 필요가 있나요?) As exemplified
in scenario given in section 3.1 there is a need to interconnect with other social groups.
Representatives of each scatternet (they maybe randomly selected one or coordinator /* 이 용어
는 scatternet에서 “일반적으로 통용되는” 용어인가요?) of each scatternet, and so on : 그래서 실
제로는 어느 노드로 해야 된다는 건가요? 어느 노드로 하나 상관이 없는건지.. 그렇다면 굳이 언
급할 필요도 없는 것 아닌가? 여기 괄호 안의 내용은 생략하는 것이 차라리 더 나을 듯) try to
form a link that interconnects two scatternets. After establishment of interconnection link,
optimization would take place.
Optimization of tunneled scatternet is an important issue. Interconnection of scatternets cannot
do not modify existing constituent scatternets, so there is high possibility that tunneled
scatternet has bottleneck (tunnel이 bottlneck이 될 가능성이 크다는 얘기 아닌가요?). If
scatternet experiences serious bottleneck, it permits few communication pair to flow well thus
others have problem with communication. To decide this a tunneled scatternet is good or not, a
metric that estimates the performance of tunneled scatternet is required and we will propose it
in section 4.2.

Social group은 미리 알려져 있어서 각 노드는 알고 있다. 같은 social group에 속한 노드들은 이

러 저러한 방법으로 서로 연결되어 피코넷 또는 스캐터넷을 형성한다.
이 형성 과정이 끝나면 필요에 의하여 (어떤 필요? 예시 필요 as exemplified in scenario given
in section 3.1) 서로 다른 social group을 연결하려고 한다면, 이런 저런 방법으로 어떤 노드가 어
떤 일을 해서 서로 연결해 간다.
여기서 가장 중요한 것은 어느 노드와 어느 노드 사이를 연결하는 것이 좋은가 하는 점이다. 좋
고 나쁨을 따지기 위해서는 터널을 연결함으로서 생성되는 스캐터넷의 성능을 estimate 할 수 있
는 metric이 필요한데 이에 대하여는 4.2에서 다룬다.
(그러고 보니 tunnel의 정의가 어디 갔죠? 한글 판에만 있나요? 여기에도 있어야 할 듯. 특히 일
반적으로 gateway라고 부르는 것과 어떻게 같고 어떻게 다른지도 설명해야 함.)

4.1 2 Proposed metric

To share network capacity among several communication pairs, following things should be
considered: 1) average hop count, 2) the number of branch per node, and 3) link capacity per
communication pair (or CP hereinafter)(Communication Pair). One of existing scatternet
evaluation metrics considers the average hop count and the number of branch per node [7]. In
addition to two factors, we should consider link capacity per CP. Link capacity per CP is
defined as the reciprocal of the number of CP that passes a link and each link has its link
capacity per CP value. A link that has the lowest link capacity per CP becomes bottleneck of
scatternet because the performance of each CP would bind will be bound by to the lowest one.
To share network capacity among several communication pairs, following things should be
considered: 1) average hop count, 2) the number of branch per node, and 3) load per link. One
of existing scatternet evaluation metric considers Average the average hop count and the
number of branch per node[APC] are already included in APC. In addition to two factors, we
should consider load per link. Load per link is defined as the number of source-destination
pairs which passes that link when all possible source-destination pairs in a scatternet
communicate. A link that has the highest load per link becomes bottleneck of the tunneled
scatternet because many source-destination pairs compete to send data. 이해의 편의를 위하여
Brach를 고려하지 않는다면, 어떤 source-dest pair가 가질 수 있는 bandwidth는 경로상의 max
load per link에 반비례한다. Since a quantity of traffic a source-destination pair can send is
restricted by maximum value of load per link on their routing path, we should minimize
maximum value of load per link in a scatternet. (전반적으로 공식을 사용해서 설명해야 할 것 같
아요.  넣어야지요)
Calculating link capacity per CP needs two stages. At first stage, we count the number of CPs
that passes a link without considering the number of branches and divide it by 1take the inverse
of it. In Figure 2(a), if we assume that all source-destination pairs send data, there will be three
traffic patternsCPs: (x, y), (x, z), (y, z). (x, y) and (x, z) will use link A while (x, z), (y, z) will use
link B. Therefore link capacity per CP of A is 1/2 and link capacity per CP of B is also 1/2. At next
stage, we calculate weighted link capacity per CP that considers the number of branch. Since
one node can utilize one link at a time, weighted link capacity per CP is link capacity per CP
multiplieddivided by the number of branches of neighbor nodes. Since there is always two
neighbor node per link, we only consider a node with more branched.the bigger number of link
between two nodes. (Here, we assume that each node spends the same amount of time to any
link.) Since node x and node y has 2 links, weighed load per link for link A is (1/2)/2 = 1/4. In
link B case, node y has 2 links while node x has 3 links, weighted load per link for link B is
(1/2)/3 = 1/6.

Figure 2(a) shows load per link when two groups are interconnected by two tunnels. Since one
node can utilize one link at a time, actual load per link is load per link multiplied by the number
of link a node has. (Here, we assume that each node spends the same time to any link.) Final
load per link is depicted at figure 2(b).
 A B
x y z

LINK TUNNEL

(a)

A/2 B/3
x y z

57 57
153 150 98 150 153

57 57
150 150

144 98 150 150 144

57 57
57 57

LINK TUNNEL

(b)
Figure 1. Link capacity per CP (Communication Pair)Load per link

Based on weighted link capacity per CPload per link we can obtain total network flows. Total
network flow is sum of individual flow of each source-destination pair and individual flow
means how much capacity much time a pair can occupycommunicate for given capacityper unit
time. Individual flow of a pair is minimum link capacity per CP expressed as the reciprocal of
maximum load per link on their routing path. In some case, maximum total network flow leads
to low performance due to high average hop count. Therefore we divide total network flow by
average hop count. It is final metric.
The relation between proposed metric and TCP throughput is depicted in figure 2. This
simulation also assumes that source-destination pair of intra traffic is twice compared to that of
inter traffic. A vertical axis is average value of TCP throughput of inter traffic from 20
experiments and a horizontal axis is metric value of given tunneled scatternet. We can insist that
proposed metric is suitable for evaluating tunneled scatternet since proposed metric and TCP
throughput of inter traffic has correlation.
(그림 2는 추가로 뽑은 데이터를 정리할 시간이 없어서 아직 못 그렸습니다. Inter 트래픽의 전송
성능과 메트릭 값이 비례하는 그래프를 그릴 예정입니다.)

4.2 Proposed tunnel selection scheme

(아직 구현 다 못했습니다)

5. Evaluation

6. Conclusion

7. Reference
(IEEE 방식에 따라 바꿔야죠~)
[1] Bluetooth Specification Version 1.1, Bluetooth Special Interest Group,
http://www.bluetooth.com, February 2001.
[2] B. Wang, J. Bodily, 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,” in Proceedings of the IEEE Globecom 2002, Taipei, Taiwan, November 2002.
[4] Z. Wang, R. J. Thomas, Z. Haas, “Bluenet - a new scatternet formation scheme,” in 35th
Hawaii International Conference on System Science (HICSS-35), Big Island, Hawaii, January
2002.
[5] F. Cuomo, G. Di Bacco, T. Melodia, “SHAPER: a self-healing algorithm producing multi-hop
Bluetooth scatternets,” in Proceedings of the IEEE Globecom 2003, San Francisco USA,
December 2003.
[6] G. Tan, A. Miu, J. Guttag, 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, 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, Apr. 2004.
[8] M. Kalia, S. Garg, 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.