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 resulting scatternet can be built more efficiently. We propose a scheme that Our idea is to forms 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. A set of scatternets interconnected by tunnels is also a scatternet, so we can employ existing metric when evaluating tunneled scatternets. We found that the existing metric is not useful when evaluating interconnection of multiple scatternets. We propose a new metric that is more suitable for the evaluation of tunneled scatternets and show that a tunneled scatternet that are made by our scheme satisfies this metric. Tunneled scatternets formed by the proposed scheme are able to share capacity more fairly among communicating peers than an existing scheme. (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 definition of social group definition, and membership management issues. However, iIt does not consider how to efficiently facilitate communication not only within each social group but also among multiple 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 slaves adjusts its communication frequency hopping sequence to their that of its mastermasters’. 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 proposed 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 large 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 needs to analyzes traffic flow pattern to identify CGs. and hence to start to form piconets. Even though This this work gives us 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. 2.3 Scatternet evaluation metric Bluenet[4] proposes two metrics, namely Average Shortest Path (ASP) and Maximum Traffic Flows (MTF). ASP, as its name implies, is average path length between all possible sourcedestination pairs in a scatternet. Minimizing ASP results in a fully meshed scatternet if nodes are distributed in a small area and it leads to low capacity [7]. MTF evaluates a scatternet when the total number of source-destination pairs is given. If the number of source-destination pairs is not known in advance, MTF is not applicable. Or, we should calculate and compare MTF for all possible number of pairs for given scatternets. MTF is not problematic when evaluating formed scatternet even though it requires at least 6000 times calculation for each scatternet.
However, MTF is hard to apply when selecting which scatternet is best one among large set of scatternets. [7] argues that the performance of scatternet is determined by average path length and the number of branch a node has. Since a node utilizes one link at one time, if we increase the number of branches to reduce average path length, overall performance degrades. Meanwhile, if we reduce the number of branches per node, latency gets longer due to increase of average path length so overall throughput also degrades. By combining these two factors, [7] proposes Average Path Capacity (APC) that measures average capacity of all source-destination pairs a scatternet can have. [7] forms a scatternet by adding a node at position that makes the scatternet has the highest value of APC. APC is a good metric when it is used to form a scatternet; however, it is inapplicable for evaluating tunneled scatternets since interconnection procedure cannot modify existing topologies. For example, there are 2 groups and 10 members of each group are in line and we want to interconnect them with one tunnel. The position of tunnel that makes the tunneled scatternet has maximum APC is middle of two scatternet since it reduces average path length. Intra traffic as well as inter traffic concentrated on that point, however, traffic that passes through that point experiences congestion. Therefore, we also consider distribution of traffic when evaluating a tunneled scatternet. 3. Design Consideration 3.1 Scenario 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 in to form a smaller scatternet, low average path length among frequently communicate communicating pair results will be shortened and hence in improveeds performance. In the 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
results 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 composed an interconnection of a set of socially grouped devices and its interconnections while group unaware scatternet refers to a scatternet that is formed by connecting all devices within an area. Table 1 shows that the performance TCP throughput of group aware scatternet is usually higher than that of group unaware scatternet. (앞 문장은 표랑 해석이 매치가 안되고 암튼 좀 이상한데, 지금 group unaware에 대한 데이터가 하나밖에 없어서 그렇습니다. group unaware 케이스에 대한 추가 실험 결과 나오면 다시 바꾸겠습니다. 그리고 몇 개의 노드를 이용해서 만들었는지 몇 개의 서로 다른 시나리오의 평균인지 그리고 저 값이 모든 pair의 평균인지 그렇다면 variance 는 어떤지 등등…. 도 보여주셔야 합니다.)
TCP Throughput (Kbps)
Group aware 41.7
Group unaware 36.2
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 이 섹션에서는 social group 을 이용해서 스캐터넷을 만드는 방법을 설명한다. 4.1 Overall structure 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) 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. (전반적으로 공식을 사용해서 설명해야 할 것 같
아요. 넣어야지요) 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). 19
51
50
19
49
50
50 46
51
19
50 49
50
19
50
46
19
19 19
LINK
19
TUNNEL
(a) 57
57
153
150
98
150
150 144
153
57
150 98
150
150
57
144
57
57 57
LINK
57
TUNNEL
(b) Figure 1. Load per link Based on load 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 time a pair can communicate per unit time. Individual flow of a pair is 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. 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. 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.