2002 ( 14 ) MaCC: WPAN

Size: px

Start display at page:

Download "2002 ( 14 ) MaCC: WPAN"

そうりんさかわ
4 years ago
Views:

1 2002 ( 14 ) MaCC: WPAN

2 2002 ( 14 ) MaCC: WPAN WPANs(Wireless Personal Area Networks) WPANs WPANs WPANs IP(Internet Protocol) WPANs WPANs 1 WPANs WPANs MaCC MaCC WPANs MaCC WPANs MaCC MaCC Bluetooth Bluetooth i

3 Abstract of Bachelor s Thesis MaCC: The Design and Implementation of WPAN Configuration In this thesis, we present a configuration mechanism for Wireless Personal Area Networks(WPANs), which includes formation and routing protocol. WPANs address short range wireless networks, formed in a space about a person that typically extends to 10m in all directions easily and flexibly. A routing protocol is necessary for WPANs as for Internet, providing access transparency for users. Internet Protocol(IP) provides access transparency, but IP assumes IP addresses are under control authoritatively. WPANs do not assume node identifiers are under control, because WPANs is not fixed. Thus, existing protocol can not be applied to WPANs. WPANs are formed dynamically. Hence, Formation Protocol is required to form WPANs effectively. And WPANs have a characteristic of being Master-driven networks. So, Data traffic may concentrate to Master if WPANs use existing routing mechanism. That leads to throughput degradation of networks. There, we present Master-driven Connection Control(MaCC), which provides the minimum hop-count routes for each communication dynamically when communications occur between nodes. MaCC has several features: autonomous distributed process, symmetric protocol, and simple mechanism. We have implemented MaCC as prototype version and measured performance of it. We show that delay of MaCC and the delay to complete connection using Bluetooth. At last, we conclude this thesis and describe future work. Makoto Takizawa Faculty of Environmental Information Keio University ii

4 WPANs(Wireless Personal Area Networks) IEEE Working Group for WPANs Bluetooth Bluetooth : MaCC WPAN MaCC MaCC Bluetooth MaCC MaCC MaCC iii

5 Bluetooth RTT iv

6 Bluetooth 1: 1 2 2: (a).5 7 (b).(a) (c).(a) (BFS) Dijkstra Bellman-Ford WPAN ( ) ED (Inquiry) (Page) MaCC AL REQ AL RES R REQ R RES MaCC RTT RDTSC v

7 6.3 MaCC Dijkstra ( ) Dijkstra ( : 2) MaCC vi

8 ACL (1 : 0 : ) Bluetooth vii

9 km 100m 10m Range Cellular GSM PDC WPAN ZigBee DECT Bluetooth WLAN IEEE b Wireless 1394 IEEE a HiperLAN 100k 1M 10M Data Rate Home Network 1.1: LAN(Local Area Network) LAN PC PC PDA 1

10 1 WPANs(Wireless Personal Area Networks) WPANs AV PDA 1 ( ) WPANs WPANs IP(Internet Protocol) IP IP IP ICANN(Internet Corporation for Assingned Names and Numbers) NIC(Network Information Center) IP WPANs WPANs WPANs MaCC(Master-driven Connection Control) MaCC 1.2 WPANs WPANs WPANs ( ) ( ) WPANs 1 1 2

11 CSMA/CD(Carrier Sense Multiple Access with Collision Detection) CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance) WPANs (Master-driven) IP WPANs MaCC MaCC MaCC WPANs 3 WPANs 1 Bluetooth 3

12 MaCC MaCC 4 MaCC 5 MaCC MaCC 6 7 4

13 2 WPANs(Wireless Personal Area Networks) WPANs IEEE WG(Working Group) [6] IEEE TG(Task Group) WPANs 2.1 IEEE Working Group for WPANs WG WPANs WPANs PC PC PDA WPANs POS WG WPANs TG(Task Group) Task Group 1 - WPAN/Bluetooth TM IEEE IEEE-SA(Standards Association) IEEE Bluetooth SIG [12] Bluetooth Bluetooth v1.1 Task Group 2 - Coexistence IEEE WPANs(802.15) Wireless Local Area Networks(WLANs) [5](802.11) TG TG 2 MAC RF Bluetooth Personal Operating Space. 10 5

14 Task Group 3 - WPAN High Rate IEEE Mbps WPANs ISM 2.4GHz MAC PNC(Piconet Controller) DEV(Device) QoS PNC-DEV 1 PNC DEV PNC Task Group 4 - WPAN Low Rate IEEE kbps 20kbps WPANs MAC PHY GHz MAC 2 FFD(Full function device) RFD(Reduced function device) FFD RFD FFD RFD 2.2 WPANs Bluetooth UWB ZigBee IEEE a a Bluetooth MaCC Bluetooth : Bluetooth UWB ZigBee 1Mbps( 721kbps) 100Mbps 10kbps - 250kbps 2.4GHz FD-SS( 1600hop/ ) 10m(1mW,0dBm), 100m(100mW,+20dBm) 100mW 3.1GHz GHz 2.4GHz 915MHz 1 DS-SS 10m 10nW 75m 21mW 30mW FCC(Federal Communication Commission:( ) ) [4] 6

15 2.2.1 Bluetooth Bluetooth Bluetooth WPANs 1 Bluetooth Bluetooth Bluetooth Bluetooth 48 IEEE802 Bluetooth Bluetooth 1 ( 7 ) Bluetooth Bluetooth Piconet 1 Piconet Piconet 3 Scatternet 2.1: Bluetooth 1: 1 2 2: 2 3 Bluetooth 79 (1MHz/ ) MHz 7

16 Bluetooth Bluetooth Bluetooth Bluetooth SCO(Synchronous Connection-Oriented) ACL(Asynchronous Connection-Less) SCO kbps ACL ACL 3 (Asynchronous Transfer) (Isochronous Transfer) (Broadcast Transfer) 100kbps 700kbps 2.2 ACL 2.2: ACL FEC CRC (kbps) DM rate 2/ DH DM rate 2/ DH DM rate 2/ DH

17 3 WPANs Bluetooth Bluetooth Bluetooth MaCC 3.1 Bluetooth Bluetooth BTCP Bluetooth Topology Construction Protocol(BTCP) [10] Bluetooth BTCP ( ) 2 3 BTCP BTCP BTCP 1 Bluetooth 1 9

18 BTCP TSF Tree Scatternet Formation(TSF) [11] BTCP TSF TSF BTCP TSF TSF TSF Bluetooth RVM Routing Vector Method(RVM) [1] RVM OSI 3 3 RVM 48 Bluetooth 7 Bluetooth Routing Protocol [2] Bluetooth Bluetooth 10

19 3.2 : MaCC Dijkstra Bellman-Ford V E G G(V, E) u, v u, v (adjacent) (a) (b) (c) 3.1: 2 (a).5 7 (b).(a) (c).(a) s (e s, e x, e y,..., e d ) (v s, v x, v y,..., v d ) (v s, e x, v x, e y, v y,..., e d, v d ) (Breadth-first search) s s s 3 11

20 3.2 BFS(G, s) 1: for u V [G] {s} 2: color[u] WHITE 3: d[u] 4: π[u] NIL 5: color[s] GRAY 6: d[s] 0 7: π[s] NIL 8: Q = {s} 9: while Q ø 10: u head[q] 11: for each v Adj[u] 12: if color[v] = WHITE 13: color[v] GRAY 14: d[v] d[u] +1 15: π[v] u 16: Enqueue(Q, v) 17: Dequeue(Q) 18: color[u] BLACK 3.2: (BFS) d[u] s u ( ) π[u] u ( ) π Q FIFO BFS 1-4 s NIL s s 0 8 Q s 1 Q s s Q Q Q Q O(E) O(V ) BFS O(V + E) 12

21 Dijkstra Dijkstra Dijkstra Dijkstra s v d[v] d[v] 3.3 Relax(u, v, w) 1: if d[v] > d[u] + w(u, v) 2: d[v] d[u] + w(u, v) 3: π[v] u 3.3: w(k, l) (k, l) d[v] u v 3.4 Dijkstra Dijkstra(G, w, s) 1: Initialize-Single-Source(G, s) 2: S ø 3: Q V [G] 4: while Q ø 5: u Extract-Min(Q) 6: S S {u} 7: for each v Adj[u] 8: Relax(u, v, w) 3.4: Dijkstra Initialize-Single-Source s NIL s d[s] 0 Q d Dijkstra Q 5 Q u 7,8 u Q 13

22 π Dijkstra 4 while V 1 Extract- Min O(V ) Extract-Min O(V 2 ) while 7 1 E Dijkstra O(V 2 + E) Bellman-Ford Bellman-Ford Dijkstra Dijkstra Dijkstra Bellman-Ford 3.5 Bellman-Ford Bellman-Ford Bellman-Ford(G, w, s) 1: Initialize-Single-Source(G, s) 2: for i = 1 to V [G] 1 3: for each (u, v) E[G] 4: Relax(u, v, w) 5: for each (u, v) E[G] 6: if d[v] > d[u] + w(u, v) 7: return FALSE 8: return TRUE 3.5: Bellman-Ford 1 Dijkstra 2-4 V FALSE TRUE Bellman-Ford O(V E) O(V ) O(E) V O(E) 14

23 4 MaCC WPAN MaCC MaCC WPAN MaCC MaCC WPAN MaCC MaCC 4.1 WPAN 4.1: WPAN MaCC WPAN PC 15

24 PC MaCC / WPAN MaCC 4.2 MaCC MaCC 1 ( ) MaCC : MaCC : : 16

25 4.3 MaCC 3 MaCC / RL MASTER RL SLAVE FREE ( ) ROOT LEAF BRANCH 4.2 J FREE A ROOT C,E,F,G,I LEAF B,D,H BRANCH ROOT 1 ROOT PARENT ROOT 1 PARENT 4.2 F B G D PARENT A B,C,D PARENT A ROOT B C D BRANCH LEAF BRANCH J FREE E F G H LEAF LEAF LEAF BRANCH : Relation I LEAF 4.2: MaCC MaCC TSF 4.1 (FREE ROOT 17

26 LEAF BRANCH) Non-ROOT LEAF BRANCH 4.1 T 4.1 Non-ROOT ROOT 1 T MaCC n 1 ( 1) T 1 n 2 ( 1) T 2 T 1 T 2 n 1 1 n 2 1 T 1 T 2 n 1 = n 2 = 1 n 1 2 n ROOT T 1 T 2 T 3 T 3 T 3 = (n 1 1) + (n 2 1) + 1 = (n 1 + n 2 ) 1 MaCC ( ) 4.1: (1 : 0 : ) State ROOT Non-ROOT FREE ROOT Non-ROOT FREE RL MASTER RL SLAVE MaCC MaCC WPAN 18

27 Relation State transition role RL SLAVE at relation RL MASTER current state current state FREE current state ROOT FREE current state LEAF LEAF current state BRANCH ROOT current state BRANCH OTHER not transit OTHER not transit Configuration return 4.3: MaCC (1 ) PARENT 4.4 E E PARENT B B A A PARENT ROOT PARENT ROOT

28 1 ( ) ( ) AL 1(A) AL 2(B) AL 3(E) A B C D B A C E C A B G D A G H E B F F B E G G C D F H D I I G H B A C E F E B F F B E G G B AL Rank(node) = Adjacency List F E E B F F E : relation (including 1-hop range) : 1-hop range BRANCH ROOT A B C D BRANCH E F G H LEAF F I LEAF LEAF LEAF BRANCH I LEAF 4.4: ( ) MaCC Dijkstra Dijkstra MaCC Dijkstra ( ) PARENT PARENT 20

29 FREE ROOT MaCC ( ) E D E AL 3(E) 1 B B AL 2(B) A A AL 1(A) A B B E E D Route Request Dijkstra Route No exists? Yes Source in the route No? Yes Connection return Sending route response PARENT No address? Yes Source requesting No route? Yes Sending route request to PARENT return NOTFOUND Sending response NOTFOUND 4.5: MANET(Mobile Ad-hoc Networks) [7] (DSR [3] AODV [8]) RVM(Routing Vector Method) 21

30 Route Response Receive route response Source requesting No route? Yes Connection return Forwarding response to Lower 4.6: MaCC MaCC WPAN [E-F-G-D] 4.7 E F D G 22

31 1,2 / / MaCC MaCC 3 PARENT MaCC ROOT WPAN MaCC ROOT A 2 1 2:MASTER B C D BRANCH LEAF BRANCH E F G H 1:SLAVE 1:MASTER 1&2:SLAVE I LEAF 4.7: ED 23

32 5 Bluetooth MaCC Bluetooth MaCC Bluetooth Bluetooth Bluetooth WPAN WPAN Bluetooth MaCC 5.1 MaCC MaCC MaCC MaCC Redhat7.3(kernel-2.4.x) Linux Bluetooth BlueZ [9] BlueZ API Bluetooth Brain Boxes BL-554 USB MaCC Bluetooth L2CAP(Logical Link Control and Adaptation Protocol) HCI(Host Controller Interface) Bluetooth MaCC IEEE Bluetooth MaCC UNIX MaCC UNIX MaCC 5.2 Bluetooth Bluetooth Bluetooth / 24

33 2 (Inquiry) (Page) Inquiry Master IQ IQ Slave Inquiry- Scan Random backoff FHS : Packet not received because of different frequencies between Master from Slave IQ Random backoff 5.1: (Inquiry) Page Master ID ID Slave Page- Scan FHS ID Relation completed : Packet not received because of different frequencies between Master from Slave Data packet Connection State 5.2: (Page) Bluetooth (FHS(Frequency Hop Synchronization) ) FHS Bluetooth Bluetooth Bluetooth FHS 25

34 FHS Bluetooth Bluetooth Bluetooth Bluetooth MaCC MaCC MaCC RL MASTER RL SLAVE 5.3 MaCC /* MaCC main loop */ 1: for (;;) { 2: FD_SET(l2cap_socket, &readfds); 3: FD_SET(timer, &readfds); 4: 5: select(fd_setsize, &readfds, NULL,NULL,NULL); 6: 7: if (FD_ISSET(l2cap_socket, &readfds)) { 8: /* receive l2cap packet */ 9: receive(l2cap_socket, buffer); 10: packet_handler(buffer); 11: } 12: 13: if (FD_ISSET(timer, &readfds)) { 14: discard(timer, trash); 15: start_inquiry(); 16: } 17: } 5.3: MaCC 26

35 : packet_handler(buffer) 2: { 3: struct message *msg; 4: msg = (struct message *)buffer; 5: 6: switch (msg->type) { 7: AL_REQ: 8: state_transition(rl_slave, msg->src_bdaddr); 9: send_al(parent, AL_RES); 10: break; 11: AL_RES: 12: state_transition(rl_master, msg->src_bdaddr); 13: merge_al(msg->al); 14: disconnect(msg->src_bdaddr); 15: if (parent) 16: send_al(parent, AL_RES); 17: break; : Bluetooth MaCC PARENT (AL REQ) (AL RES) AL REQ AL RES AL REQ RL SLAVE AL RES RL MASTER AL RES RL MASTER AL RES PARENT PARENT AL RES AL RES RL MASTER AL REQ BlueZ hci inquiry 27

36 AL REQ AL REQ AL RES 5.5 L2CAP Header Payload AL_REQ type=0x01 type source bdaddr destination bdaddr AL_RES type=0x length flag AL MaCC Header 5.5: AL REQ AL RES MaCC L2CAP MaCC L2CAP MaCC MaCC type Bluetooth MaCC MaCC AL REQ type AL REQ MaCC AL RES MaCC length flag AL lenght AL AL flag MaCC TSF MaCC TSF ROOT Bluetooth 2 (GIAC(General Inquiry Access Code) DIAC(Dedicaded Inquiry Access Code)) GIAC DIAC 28

37 DIAC DIAC ( ) MaCC ROOT DIAC ROOT ROOT FREE MaCC TSF TSF LEAF BRANCH TSF 2 TSF MaCC MaCC MaCC AL REQ AL RES MaCC struct adjacent { bdaddr_t bdaddr; struct adjacent *next; }; struct adjacent_list { struct adjacent *adjct; struct adjacent_list *next; }; 5.6: adjacent 1 adjacent Bluetooth adjacent list adjacnet adjacent list 29

38 5.3.2 MaCC 1 Dijkstra s (R REQ) (R RES) R_REQ type=0x03 L2CAP MaCC Header Header from to R_RES type=0x04 flag from to weight route 5.7: R REQ R RES R REQ MaCC (from) (to) Bluetooth R RES flag R REQ weight route from to Bluetooth R REQ R RES PARENT R REQ R REQ child:1 R REQ from: Bluetooth to: Bluetooth R REQ R RES R RES ROOT flag NOROUTE 30

39 1: route_request (child, from, to) 2: { 3: if (Dijkstra!= NULL) { 4: if (child == from) 5: return GOTROUTE; 6: else { 7: route_response(child, from, to, route, flag); 8: return RESROUTE; 10: } 11: } 12: else { 13: cache_route_request(child, from, to); 14: send_route_request(parent, from, to); 15: } 16: return REQESTING; 17: } 5.8: R RES 1 R REQ (child) 5.4 MaCC MaCC (sbuf) 5.10 MaCC MaCC type weight pointer route Bluetooth Bluetooth pointer 31

40 1: route_response (child, from, to, route, flag) 2: { 3: if (route_req = exist_rreq_cache()) 4: delete(route_req); 5: if (child == mybdaddr) { 6: cache_route(route); 7: return GOTROUTE; 8: } 10: else { 11: send_route_response(child, route); 12: return RESROUTE; 13: } 14: } 5.9: DATA type=0x05 L2CAP MaCC weightpointer data_length route data Header Header 5.10: 1 Bluetooth route pointer 6(byte) data length data route Bluetooth Bluetooth MaCC MaCC pointer weight pointer data length route data length 4 BlueZ 32

41 L2CAP Bluetooth Bluetooth MaCC MaCC 5.11 X:LEAF Y:BRANCH Z:ROOT 3 X Z MaCC Y Z X:LEAF send data copy data to sbuf Dijkstra cache route_request discard associated route_request cache cache route send sbuf write route to packet route_repuest Y:BRANCH Dijkstra cache route_request discard associated route_request cache route_response Data route_request route_response Z:ROOT Application Dijkstra MaCC decide next hop Data Data received transfer to Applicaton Application 5.11: MaCC 33

42 6 MaCC Bluetooth 1 RTT( ) 6.1 PC3 A,B,C ROOT BRANCH LEAF 6.1 PC 6.2 Bluetooth 6.2 Bluetooth Bluetooth CF Bluetooth USB Brain Boxes BL-554 Bluetooth USB 6.1: A B C CPU Pentium 3 866MHz Celeron 750MHz Pentium 4500MHz 380MB 128MB 192 MB OS RedHat Linux 7.3 RedHat Linux 7.3 RedHat Linux Bluetooth stack bluez-kernel-2.3 bluez-kernel-2.3 bluez-kernel Bluetooth RTT 6.1 Bluetooth RTT RTT BlueZ l2ping 300 l2ping RTT 34

43 6.2: Bluetooth BL-554 3CREB96 Bluetooth Starter Kit BL IbCARD Bluetooth CSR CSR Ericsson CSR Ericsson / SCO Millisecond DM1 DH1 DM3 DH3 DM5 DH5 Packet type 6.1: RTT 6.2 MaCC MaCC Bluetooth MaCC 35

44 6.2.1 MaCC Pentium Counter 6.2 Pentium Counter CPU #define RDTSC(x) asm("rdtsc" : "=A" (x)) unsigned long long int count1, count2; RDTSC(count1); /* */ RDTSC(count2); printf("process time = %lld\n", count2-count1); 6.2: RDTSC MaCC ( ) 6.3 MaCC A LEAF B BRANCH C ROOT 3 A B ROOT C C A 20 ( ) 0.01 RTT O(V ) MaCC MaCC Dijkstra MaCC Dijkstra

45 Dijkstra Start cache COMM r_req send r_req send packet send r_res send recv r_req Dijkstra packet recv r_res remove r_cache Millisecond route gotten recv cache r_req r_req Dijkstra send r_req send packet recv remove r_res r_cache send r_res send packet A B C B A time 6.3: MaCC LEAF ROOT 1 BRANCH Dijkstra O( 2 + ) 6.4 O(2 2 ) 6.5 O( 2 + ( 1)) Bluetooth Bluetooth 1 37

46 Millisecond Number of vertexes 6.4: Dijkstra ( ) 6.3: ( ) ( ) ( ) 6.3 MaCC 3 MaCC ( ) 2 ( ) 2 ( ) MaCC V Dijkstra D(V ) MaCC 38

47 Millisecond Number of vertexes 6.5: Dijkstra ( : 2) T ω = T 1 = D(V ) 1 T ω = T 1 = rtt D(V ) < 25(ms) MaCC LEAF ROOT 2 BRANCH LEAF ROOT LEAF C ω 39

48 MaCC ω T ω = rtt (ω 1) + C (ω 1) + D(i) i=1 T ω = rtt ω = rtt (ω 1) + rtt C 1.6 C MaCC Bluetooth ROOT T ω MaCC T ω = ω i {i rtt + i C + D(Θ ω j (v))} (rtt + C + D(Θ ω (v))) i=0 j=0 ω 1 Θ n (v) = f f f f(v), Θ 0 (v) = v }{{} n f(v) = 2v + 1 ω ω + 1 T ω Θ n (v) v n Dijkstra 1 40

49 : 3 T ω = rtt ω C C 0 MaCC 6.7 RTT 20ms MaCC Millisecond Routing Protocol based on Flooding Hop counts 6.7: MaCC MaCC MaCC MaCC Bluetooth Bluetooth Bluetooth 41

50 Bluetooth

51 7 7.1 WPANs WPANs WPANs MaCC WPANs WPANs WPANs WPANs WPANs WPANs MaCC MaCC MaCC MaCC RTT MaCC BRANCH PARENT BRANCH BRANCH 43

52 QoS / 1 1 MaCC MaCC Bluetooth (PSM:Protocol Service Multiplexer) TCP/UDP MaCC WPANs ROOT MaCC Dijkstra MaCC MaCC MaCC 44

53 Bluetooth MaCC 45

54 ECN

55 [1] WPAN No /11/

56 [1] P. Bhagwat and A. Segall. A Routing Vector Method (RVM) for Routing in Bluetooth Scatternets. In 1999 IEEE International Workshop on Mobile Multimedia Communications (MoMuC 99), [2] B.J.Prabhu and A. Chockalingam. A Routing Protocol and Energy Efficiency Techniques in Bluetooth Scatternets. In Proc. IEEE ICC 2002, New York, April [3] Josh Broch, David B. Johnson, and David A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Netoworks. IETF Internet-Draft [Work in Progress], March [4] Federal Communication Commission. Revision of Part 15 of the Commission s Rules Regarding Ultra-Wideband Transmission Systems, April [5] IEEE Standard (IEEE Computer Society LAN MAN Standards Committee). Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, June [6] IEEE Working Group for WPAN. [7] Mobile Ad-hoc Networks Working Group (MANET). Charter [Work in Progress], [8] Charles E. Perkins, Elizabeth M. Royer, and Samir R. Das. Ad Hoc On Demand Distance Vector (AODV) Routing. IETF Internet-Draft [Work in Progress], June [9] BlueZ project Official Linux Bluetooth protocol stack. [10] Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas, and Richard LaMaire. Distributed Topology Construction of Bluetooth Personal Area Networks. In Proceedings of IEEE INFOCOM, April

57 [11] Godfrey Tan, Allen Miu John Guttag, and Hari Balakrishnan. Forming Scatternets from Bluetooth Personal Area Networks. Technical Report MIT-LCS-TR- 826, MIT Laboratory for Computer Science, October [12] The Bluetooth Special Interest Group. 49

TCP/IP IEEE Bluetooth LAN TCP TCP BEC FEC M T M R M T 2. 2 [5] AODV [4]DSR [3] 1 MS 100m 5 /100m 2 MD 2 c 2009 Information Processing Society of

TCP/IP IEEE Bluetooth LAN TCP TCP BEC FEC M T M R M T 2. 2 [5] AODV [4]DSR [3] 1 MS 100m 5 /100m 2 MD 2 c 2009 Information Processing Society of IEEE802.11 [1]Bluetooth [2] 1 1 (1) [6] Ack (Ack) BEC FEC (BEC) BEC FEC 100 20 BEC FEC 6.19% 14.1% High Throughput and Highly Reliable Transmission in MANET Masaaki Kosugi 1 and Hiroaki Higaki 1 1. LAN