Abstract
1. Introduction Bluetooth [1] is a representative technology for short range wireless communication which adopting frequency hopping scheme. 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 a traffic pattern at formation time is almost impossiblenot obvious. Existing scatternet formation schemes assume that all devices are identical. In this scenario, malicious user can participate in forming scatternet without restriction since scatternet formation scheme cannot recognize user. It may cause leak of personal information or (데이터 전송에서 악의적인 행동, 이걸 어떻게 표현해야 할 까요?). 보안 부분은 우리의 주 관심사가 아니지요. 이 얘기를 굳이 할 필요는 없을 것 같습니 다. 꼭 하고 싶다면 뒤의 어디에선가 아주 짧게 언급할 수는 있겠지만… 스캐터넷을 잘 만들려면 트래픽 패턴에 대하여 알아야 하지만 이걸 알 수가 없다. 그런데 social group은 어느 정도 추정을 할 수 있게 해준다. 그렇다면 이걸 이용해보자…. In practicalpractice, however, a person will communicate more frequently with other persons belonging to the same social group [2] than with strangers belonging to other social groups. Thus, we can apply this observation when forming a scatternetto scatternet formation scehem so that the resulting scatternet can be more efficient. We propose a scheme that forms a 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. Moreover, tunnel can ensure security by controlling traffic from outside of group. 이 얘기도 나중에 딴 곳에서 언급할 것 A set of scatternets interconnected by tunnels is also a scatternet, so we can employ existing metric when evaluating tunneled scatternet. We found that existing metric is not useful when evaluating interconnection of multiple scatternets. We propose a new metric which that fits for the evaluation of tunneled scatternets. We also propose a and tunnel selection scheme that satisfies maximizes the proposed metric. A tunneled scatternet formed by the proposed scheme which has higher metric value shares capacity among several source-destination pairs more
fairly than that has lower valuea naïve scheme?. 그래서 어떤 결론을 얻었는지 요약이 여기에 들어가야 됨. (Following section~) 2. Related Work 2.1 Social Group Social group is defined as “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, to be a member of social group there must be 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 the relation between group member and his devices, the format of definition of social group, and membership management issues. However, they does not consider inter-communication among multiple social groups. 2.2 Bluetooth 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 has up to 7 slaves and they form piconet. Scatternet is proposed to interconnect more than 9 devices but it has not standardized yet. Scatternet formation scheme is classified by scatternet topology (tree or mesh), type of bridge node (master-slave or slave-slave), and whether all nodes are in transmission range (single-hop or multi-hop). There are several scatternet formation schemes such as Bluemesh[3], Bluenet[4], Shaper[5], TSF[6]. They regard all nodes as identical one and focus on formation of one large scatternet, 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. They analyze traffic flow pattern 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 metric, namely Average Shortest Path (ASP) and Maximum Traffic Flows (MTF). MTF evaluates a scatternet with specific number of source-destination pair. If we cannot estimate traffic pattern, it is hard to apply MTF. [7] insists 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 branch to reduce average path length, overall performance falls. Meanwhile, if we reduce the number of branch per node, latency will rise due to increase of average path length so overall throughput also falls. [7] proposes Average Path Capacity (APC) which measures average capacity all source-destination pairs in the 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 high APC does not guarantee high throughput of inter group traffic. Table 1 shows TCP throughput of two different tunneled scatternets which 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. We assume that source-destination pair of intra traffic is twice compared to that of inter traffic since social group member may communicate frequently. As you can see from table 1, sum of inter and intra traffic is similar each other. However, 2 tunnels case shows high throughput for inter traffic. Even through two tunneled scatternets have similar APC, a tunnel becomes bottleneck when there is only one tunnel. If a tunneled scatternet has two tunnels, inter traffic is 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. (인트라 트래픽의 성능을 조금 희생하더라도 인터 트래픽에 좀더 신경 써줘야 된다, 왜냐, 요 녀 석을은 상대적으로 홉수가 길어서 통신을 잘 못하니까, 이런 문장을 추가해야 할 듯) TCP throughput (Kbps) Inter traffic Intra traffic Sum of two 2 tunnels (APC=0.008421) 158.0 1007.6 1165.6 1 tunnel (APC=0.008457) 88.3 1048.3 1136.7 Table 1. Performance of two scatternets 3. Design Consideration 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
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
144
57
57 57
LINK
(b)
57
57
TUNNEL
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.