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 Personal Area Network (PAN). 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 to minimize scatternet formation time or to maximize the performance of formed scatternets. Traffic pattern information is useful to construct an efficient scatternet, however guessing traffic pattern at formation time is not obvious. In practice, a person will communicate more frequently with other persons belonging to the same social group [2] than with strangers belonging to other social groups [2]. Thus, we can apply this observation to scatternet formation scehem scheme so that the resulting scatternet can be more efficient. We propose a scheme that 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 scatternet. We found that the existing metric is not useful when evaluating interconnection of multiple scatternets. We propose a new metric that fits for the evaluation of tunneled scatternets. We also propose a tunnel selection scheme that maximizes the proposed metric. A tTunneled scatternets formed by the proposed scheme are able to share shares capacity more fairly among communicating peers more fairly than a naïve scheme? (이전 연구에는 터널을 이용해서 스캐터넷을 형성하는 방법이 없었기 때문에 터널을 랜 덤으로 선택하는 방식과 비교해야 할 것 같습니다.). (Following section~) 2. Related Work 2.1 Social Group Social group is defined as “A 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].” In other words, a person can be to be a member of social group when there must be is consensus between group members to determine their inclusion. In social group, some collaborative activity is required to achieve a common goal. Lifetime of social group is usually longer than the time taken to complete the computing session and lasts for months or years. (논문에서 고대로 인용했는데.. 이러면 안되는거죠? ㅠㅠ) Social group concerns Main concerns of [2] are the relation between group member and his or her devices, the format of definition of social group, and membership management issues. However, they it does not consider inter-communication 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 operation of Bluetooth and its protocol. Bluetooth differs from contention based protocol such as IEEE 802.11 since Bluetooth devices form masterslave link and slaves adjust communication frequency hopping sequence to their masters’. Bluetooth adopts time division duplex communication scheme and master decides which slave communicates with itself next time slot. Master A master has up to 7 slaves and they form a piconet. Scatternet is proposed to interconnect more than 9 8 devices but it has not standardized yet. There have been proposed several scatternet formation schemes such as Bluemesh[3], Bluenet[4], Shaper[5], TSF[6]. Scatternet formation scheme iss can be classified by scatternet resulting topology (for example, tree or mesh), by type of bridge node (for example, masterslave or slave-slave), and by whether all nodes are in transmission range or not. (single-hop or multi-hop). There are several scatternet formation schemes such as Bluemesh[3], Bluenet[4], Shaper[5], TSF[6]. They Most of existing scatternet formation schemes regard all nodes as identical one and focus on formation of one large scatternet without considering social relationships among devices (or their owners). , so they cannot support per social group scatternet formation. [8] defines Communicating Group (CG) 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, low delays and packet drop. This scheme needs to analyze traffic flow pattern to identify CGs and hence to start to form piconetsThey analyze traffic flow pattern. This work provides a way to estimate social groups from traffic pattern while our work is to form efficient scatternets when social groups are known (or estimated). to identify CGs, however, it is hard to form adequate scatternet in early stage of communication and observing traffic pattern requires high overhead. Therefore we bring social group concept to identify communication pattern.
2.3 Scatternet evaluation metric Bluenet[4] proposes two metrics, namely Average Shortest Path (ASP) and Maximum Traffic Flows (MTF). ASP가 왜 부적절한지 설명. MTF evaluates a scatternet when with specific the total number of source-destination pairs is given. If we cannot estimate traffic pattern, it is hard to apply MTF. 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. [7] insists 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 fallsdegrades. Meanwhile, if we reduce the number of branches per node, latency will risegets longer due to increase of average path length so overall throughput also fallsdegrades. By combining these two factors, [7] proposes Average Path Capacity (APC) that which measures average capacity of all source-destination pairs in the a scatternet can have by combining both two factors. We simulate relation of APC and TCP throughput to verify whether APC is proper metric for evaluating a tunneled scatternet(APC는 스캐터넷간 트래픽의 성능을 보장해주지 못한다는 뜻으 로 쓴 문장인데, 좀 이상하네요). As a result, we discover that APC is not useful when evaluating interconnection of multiple scatternets. high APC does not guarantee high throughput of inter group traffic. Table 1 shows TCP throughput of two different tunneled scatternets which that have almost the same APC value. There are two kinds of traffic, namely inter group traffic and intra group traffic. Inter traffic passes through a tunnel to arrive destination while intra traffic travels within a group. The number of We assume that ssource-destination pairs of intra group traffic is set as twice compared to of that of inter group traffic since we assume that social group member may communicate more frequently. As you can see from table 1Table 1, sums of inter and intra group traffic’s throughput is similar each otherin both cases are similar. However, 2 tunnels case shows high throughput for inter traffic with little compensation of intra traffic. Even through two tunneled scatternets have both cases show similar APC values, a tunnel can become as bottleneck when there is only one tunnel. If a tunneled scatternet has two tunnels, inter traffic would beis distributed so that it shows high throughput for inter traffic. In the other words, ACP does not consider distribution of traffic, so it is not a proper metric of tunneled scatternet and all communication pairs share network capacity more fairly.
TCP throughput (Kbps)
Inter group trafficInter
TCP Throughput (Kbps) Intra group Inter + Intra trafficIntra trafficSum of two
traffic 158.0 88.3
2 tunnels (APC=0.008421) 1 tunnel (APC=0.008457)
traffic 1007.6 1048.3
1165.6 1136.7
Table 1.Table 1. Performance of two scatternetsPerformance comparison of two scatternets with similar APC values 3. Design Consideration Problem definition이 여기에. To share network capacity among several communication pairs, To improve performance of a scatternet (인트라 트래픽이 잘? 흐르게 하려면, 이런 식으로 바꿔야 하는데..), following things should be considered: 1) average hop count, 2) the number of branch per node, and 3) load per link. Average hop count and the number of branch per node 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 pair 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. 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. 4. Proposed Scheme 4.1 Proposed metric (전반적으로 공식을 사용해서 설명해야 할 것 같아요.) In this section, we will explain how to calculate proposed metric. 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
19
50
49
50
50 46
51
19
50 49
50
50
19
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. (그림 넣어야 하는데.. 아직 gnuplot을 쓸 줄 몰라서 ;; ) 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.