Configuring Bluestars

Configuring Bluestars: Multihop Scatternet Formation for Bluetooth Networks Chiara Petrioli (Member-IEEE), Stefano Basagni (Member-IEEE), Imrich Chlamtac (Fellow-IEEE) IEEE Transactions on Computers, Vol. 52, No. 6, June 2003, pp. 779-790

Presented By: Somak Sen 12/03/09 18:48

1

Outline • Introduction • Piconet Basics • Scatternet Formation • Topology Discovery • BlueStars Formation • Configuring BlueStars

• Simulation and Results • Conclusion 12/03/09 18:48

2

Introduction • Ad-hoc networking • Spontaneous deployment • Self-management/self-organization

• Single hop. topology •Centralized approach

•Multihop topologies • Initiated by ‘blueroot’ • Degree reduction (need geographical info) 12/03/09 18:48

3

Bluetooth Piconet (‘BlueStar’) • • • •

Unlicensed ISM band (2.4 GH Frequency Hopping Scheme Time-Division Duplex (TDD) Slot time of 625 µs (pair) • Master-Slave communication • Slave-Master communication

12/03/09 18:48

4

Bluetooth Gateways

I. Master-Slave

12/03/09 18:48

II. Slave-Slave

5

Piconet Formation • Device Discovery • INQUIRY • INQUIRY_SCAN

• Link Establishment • PAGE • PAGE_SCAN Neighbors have to be in “opposite modes” 12/03/09 18:48

6

Device Discovery Phase • Inquirer in INQUIRY mode • Transmits ID packets (very small) • ID packet contains only General Inquiry Access Code (GIAC) • Frequency hops at twice the rate

• Other device in INQUIRY_SCAN mode • Frequency hops at low rate (once every 1.28s) • Listens for backoff interval after receiving ID packet • Sends Freq. Hop. Synchronization 12/03/09 18:48 (FHS) packet containing own ID & BT

7

Link Establishment Phase • Device ‘v’ in PAGE mode => master • Device ‘u’ in PAGE_SCAN mode => slave • v transmits page_ID packet on u’s frequencies • u acknowledges page_ID packet • v transmits FHS packet to u • Exchange information to set up a link • If u is already master of another piconet, roles can be switched between u and v • Slaves can be “parked” and “woken up” 12/03/09 18:48

8

Phase I: Device Discovery Phase • Drawbacks • How to guarantee “opposite modes” among neighbors? • Source (INQUIRY mode) knows identity of other device (INQUIRY_SCAN mode) but not vice versa

• Solution • Randomly alternate between modes 12/03/09 18:48

9

DISCOVERY procedure // set timer & decrement at each CLK

// compute phase length // do not exceed Tdisc // SWITCH to opposite mode

Existing piconets disrupted at 7, 13 12/03/09 18:48

10

DISCOVERY procedure: correctness Large Tdisc • Longer discovery phase • Higher probability of discovering all neighbors Packet loss might cause “asymmetric view” “Each device v terminates the execution of the topology discovery phase. If device v has discovered neighbor u, it knows its ID and weight and so does u of v” 12/03/09 18:48

11

Phase II: BlueStars formation • v becomes master/slave based on neighbors’ weight • v becomes slave of first master among “bigger” neighbors that invited it • In case no “bigger” neighbor invited it, v becomes master and informs “smaller” neighbors • init devices: neighbor(s) with biggest weight in neighborhood • ties broken arbitrarily using unique id (total ordering)

12/03/09 18:48

12

Network with init devices

12/03/09 18:48

13

Procedure INITOPERATIONS

// if v is init device

// (paged device, paging device, role of paging device, id of master if paging device is slave; else irrelevant)

12/03/09 18:48

14

Procedure at non-init device ‘v’ // from bigger neighbor // not assigned to any piconet // already joined some piconet, inform u // ensure all bigger neighbors have paged // no bigger master

// inform smaller nodes about being master // inform bigger slaves nodes about being master // v exits if master // return to PAGE mode & wait for pages from smaller neighbors // executed only by slaves 12/03/09 18:48

15

BlueStar formation example 23 is “released” by 42 Slave of 45

“PAGE ”

12/03/09 18:48

16

BlueStar formation example

12/03/09 18:48

17

BlueStar formation example 7 Masters (4 INIT devices)

12/03/09 18:48

18

Phase III: BlueStars configuration: BlueConstellation Definitions Neighboring masters (mNeighbors) •2-hop path with intermediate node being slave of one of them (gateway slave) e.g. 34 & 28 •3-hop path between 2 slaves (intermediate gateway) e.g. 34 & 51

Init-master (iMaster): biggest weight among all its mNeighbors e.g. 51 & 45 are iMasters, rest are non-iMasters 12/03/09 18:48

19

BlueStars Gateway selection Criterion: for every 2 masters, slaves in 2-hop/3-hop paths between them will be gateways Multiple gateways between 23 & 28 •Keep one of them

Selection done at each master • ID & weight of own slaves • ID, weight, ID of masters of 1-hop neighbors of slaves • ID, weight, ID of masters of neighboring slaves that did not join the piconet

12/03/09 18:48

20

Scatternet formation procedure for all masters ‘v’ // v is iMaster

// instructs u to PAGE i) mNeighbors for which u is a gateway slave ii) peer gateways between v & some 3-hop neighbor // recruit neighbors that have joined some other piconet so that they can be gateways to their masters

// v is non-iMaster

// instruct u to go to PAGE_SCAN mode and wa //BOOLEN fn: Any gateway slaves of bigger mNeighbors to interconnect to? //waits to be paged // set up links to smaller mNeighbors //BOOLEN fn: have all gateways u set up connections toward bigger mNeighbors?

12/03/09 18:48

//page all 2&3-hop neighbors of v that have pending requests 21

BlueConstellation example

iMast er 12/03/09 18:48

iMast er 22

Simulation • Impact of Device discovery phase on performance • Visibility graphs: n Power Class 3 BT nodes scattered randomly & uniformly in a square of size L = 30m • Transmission range r = 10m • #BT nodes n = 30, 50, 70, 90, 110 • Tdisc = 10s, 20s • Time spent (avg) in INQUIRY/INQ_SCAN modes = 1s

• BT-based ad-hoc network simulator in C++

12/03/09 18:48

23

Results

12/03/09 18:48

24

Results - Graph 1 Tdisc increases => less # of piconets

33% 28%

23%

For dense networks # of extra piconets is less

28%

12/03/09 18:48

25

Results - Graph 2 99th %tile < 14

Increased # of links => more avg. # of slaves => increased size of “bigger” piconets

12/03/09 18:48

26

Conclusions • BlueStars protocol • Topology Discovery • Piconet formation • Scatternet formation •Multiple paths between nodes => mesh

• Drawbacks • Ensuring neighbors in opposite modes • Temporary piconets to identify inquirer • Time wasted during backoff

• Future work/Suggested modifications Have bounded #slaves in piconet C. Petrioli, S. Basagni: “BlueMesh:Degree-Constrained Multihop Scatternet Formation for Bluetooth Networks.” Proc. IEEE GLOBECOM’02, Nov. 2002 12/03/09 18:48

27

Thank You

12/03/09 18:48

28