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 either to minimize scatternet formation time or to maximize the performance of formed scatternets. Traffic pattern information is useful to construct an efficient scatternet [ref?], however it is very hard to reliably guessing estimate 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 than with strangers belonging to other social groups [2]. Thus, wWe can apply this observation to scatternet formation 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. Tunneled scatternets formed by the proposed scheme are able to share capacity more fairly among communicating peers than an existing scheme. 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 fits for is more suitable for the evaluation of tunneled scatternets. We also propose a tunnel selection scheme that maximizes the proposed metric. Tunneled scatternets formed by the proposed scheme are able to share capacity more fairly among communicating peers than a 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].” [2]. In other words, aA person can be a member of social group when there is consensus between among group members. 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, it does not consider 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 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 proposed 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 focusfocuses on formation of one large scatternet without considering social relationships among devices (or their owners). [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, lower delays and less packet drops. This scheme needs to analyze traffic flow pattern to identify CGs and hence to start to form piconets. 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). 2.3 Scatternet evaluation metric Bluenet[4] proposes two metrics, namely Average Shortest Path (ASP) and Maximum Traffic Flows (MTF). (ASP가 뭔지 간단히 설명해야 왜 문제인지 이해가 될 듯) A scatternet that has maximized ASP value may suffer from reduced capacity a node can occupy for one link. (설득 력이 부족합니다. 남의 논문의 단점을 얘기하는 것이므로 정확하게 주장하지 않으면 안됩니다.) ASP가 왜 부적절한지 설명. MTF evaluates a scatternet when the total number of sourcedestination 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. (그래서 왜 문제가 되나요? 너무 계산량이 많다?)
[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. (아래의 문단은 뒤로 보내고 여기서는 APC가 왜 부적절한지 그 “이유”를 설명하면 될 것 같습니다. 실험해보니까 그렇더라가 아니라 왜 부적절한지를 설명할 수 있어야 합니다. 아마 bottleneck가지고 설명하면 될 것 같습니다. 그리고 APC를 제시한 논문에서는 왜 문제가 되지 않는지도 여기서 설명해야 합니다. 안그러면 APC에 기반한 기존의 논문 자체가 틀 렸다고 주장하는 게 되니까 부담이죠.) We simulate relation of APC and TCP throughput to verify whether APC is proper metric for evaluating a tunneled scatternet. As a result, we discover that APC is not useful when evaluating interconnection of multiple scatternets. Table 1 shows TCP throughput of two tunneled scatternets that have almost 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 source-destination pairs of intra group traffic is set as twice of that of inter group traffic since we assume that social group member may communicate more frequently. As you can see from Table 1, sums of inter and intra group traffic’s throughput in both cases are similar. However, 2 tunnels case shows high throughput for inter traffic with little compensation of intra traffic. 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)
Inter group traffic 158.0 88.3
TCP Throughput (Kbps) Intra group Inter + Intra traffic traffic 1007.6 1165.6 1048.3 1136.7
Table 1. Performance comparison of two scatternets with similar APC values 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 will may change frequently changed. OAnother characteristic of such the network is that each person belongs to one of diverse social groups. (시나리오가 추상적이네요. 좀 더 구체 적으로 쓰면 어떨까요?) 3.2 Most of scatternet formation schemes form a scatternet by connecting all devices within an area. Devices that frequently communicate may scatter in a throughout the scatternet so average path length will be longer than they gather together. Since people belong to the same social group would often interact each other, we should connect them first to enhance performance (먼저 연 결한다고 꼭 performance가 올라가는 것이 아니지요. 이유를 적어야 합니다.). Table 2 and Figure 1 show performance comparison of group aware scatternets (group aware가 뭔지 정의도 안하고 여기서 바로 나오면 안되지요…) (e.g., best and worst cases) and group unaware scatternet. The performance of group aware scatternet is usually higher than group unaware scatternet. In the worst cast of group aware scatternet, even though it shows low average TCP throughput, it shares network capacity more fairly than group unaware one. Figure 1 shows TCP throughput of three cases. One point represents average TCP throughput per 10% of throughput that are ordered descending order. In Figure 1, Group unaware scatternet shows high throughput only for few (in this graph, 10%) traffic compared to group aware ones. (여기 서의 설명을 보면 뭔가 앞뒤가 바뀐 것 같습니다. 이미 group-aware formation scheme이 있고 그래서 그걸 보니까 좋더라. 이렇게 하지 말고 social group을 반영해서 만들려면 어떻게 하면 좋 을지 “논리”적인 설명을 해야지요.)
TCP Throughput (Kbps)
Group aware (Worst) 35.5
Group aware (Best) 41.7
Group unaware 36.2
Table 2. Performance comparison of group aware scatternets and group unaware scatternet (확정되면 예쁘게 만들께요 ^-^;)
300000
TCP throughput (bps)
250000
200000 group aware (worst) group aware (best) group unaware
150000
100000
50000
0 1
2
3
4
5
6
7
8
9
10
Figure 1. Performance comparison of group aware scatternets and group unaware scatternet [8] identifies CGs by analyzing traffic flow and it provides more accurate group clustering than social group method. Identifying CGs requires quite amount of time at first stage, it is hard to apply to our scenario. 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 at tunnel. A tunnel selection scheme should estimate load per link and distribute load per link by adjusting the number or position of tunnel(s). Problem definition이 여기에. 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. 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 앞에서 APC가 왜 문제인지 내용을 여기에 옮겨야 겠습니다. 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. 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 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. 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 (전반적으로 공식을 사용해서 설명해야 할 것 같아요.) 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
46
19
19 19
LINK
(a)
19
19
TUNNEL
57
57
153
150
98
150
153
150 144
57
150 98
150
150
57
144
57
57 57
LINK
57
TUNNEL
(b) Figure 2.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.