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 케이스에 대한 추가 실 험 결과 나오면 다시 바꾸겠습니다.…)
Average TCP Throughput (Kbps) Variance among session throughput
Group aware 39.241.7 1.3
Group unaware 36.82 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.
TCP Throughput (Kbps) Variation
2 tunnels (APC=0.008421) 37.6 344.9
1 tunnel (APC=0.008457) 38.1 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 x
57
57
153
B/3 y
150
98
z
150
150 144
153
57
150 98
150
150
57
144
57
57 57
LINK
57
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.