урсы английского
<<  A hybrid heuristic for an inventory routing problem Mac OS X Unix whether you like it or not  >>
Z-MAC: Hybrid MAC for Wireless Sensor Networks
Z-MAC: Hybrid MAC for Wireless Sensor Networks
CSMA Protocols
CSMA Protocols
Effective Throughput CSMA vs
Effective Throughput CSMA vs
Z-MAC: Basic Objective
Z-MAC: Basic Objective
ZMAC - Basic Idea
ZMAC - Basic Idea
Z-MAC: Basic components
Z-MAC: Basic components
DRAND Ц Algorithm
DRAND Ц Algorithm
DRAND Ц Algorithm Ц Successful Round
DRAND Ц Algorithm Ц Successful Round
Z-MAC Ц Reserving Slots
Z-MAC Ц Reserving Slots
Z-MAC Ц Local Frames
Z-MAC Ц Local Frames
Z-MAC Ц Transmission Control
Z-MAC Ц Transmission Control
Z-MAC Ц Transmission Control
Z-MAC Ц Transmission Control
Z-MAC Ц LCL
Z-MAC Ц LCL
Z-MAC Ц HCL
Z-MAC Ц HCL
Z-MAC Ц Explicit Contention Notification
Z-MAC Ц Explicit Contention Notification
Performance Results
Performance Results
Experimental Setup Ц Single Hop
Experimental Setup Ц Single Hop
Z-MAC Ц Two-Hop Experiments
Z-MAC Ц Two-Hop Experiments
Experimental Setup - Testbed
Experimental Setup - Testbed
Z-MAC Ц Single-Hop Throughput
Z-MAC Ц Single-Hop Throughput
Z-MAC Ц Two-Hop Throughput
Z-MAC Ц Two-Hop Throughput
Conclusion
Conclusion
Questions
Questions
DRAND Ц Algorithm Ц Unsuccessful Round
DRAND Ц Algorithm Ц Unsuccessful Round
DRAND Performance Results Ц Run Time
DRAND Performance Results Ц Run Time
DRAND Performance Results Ц Message Count and Number of Slots
DRAND Performance Results Ц Message Count and Number of Slots
Overhead (Hidden cost)
Overhead (Hidden cost)
Multi Hop Results Ц Throughput
Multi Hop Results Ц Throughput
Fairness (two hop)
Fairness (two hop)
Multi Hop Results Ц Energy Efficiency (KBits/Joule)
Multi Hop Results Ц Energy Efficiency (KBits/Joule)
Question
Question
Conclusion
Conclusion
Z-MAC Ц Local Frames
Z-MAC Ц Local Frames
Z-MAC Ц Explicit Contention Notification
Z-MAC Ц Explicit Contention Notification
Z-MAC Ц Performance Results
Z-MAC Ц Performance Results
Z-MAC Ц Performance Results Ц Throughput, Fairness
Z-MAC Ц Performance Results Ц Throughput, Fairness
Z-MAC Ц Energy Experiments
Z-MAC Ц Energy Experiments
Z-MAC Ц Performance Results Ц Energy
Z-MAC Ц Performance Results Ц Energy
Z-MAC Ц Latency Experiments
Z-MAC Ц Latency Experiments
Multi Hop Results
Multi Hop Results
Multi Hop Results
Multi Hop Results
Z-MAC Ц Performance Results Ц Latency
Z-MAC Ц Performance Results Ц Latency
Q & A
Q & A
Agenda Introduction Wireless Sensor Network (WSN) MAC Layer Design
Agenda Introduction Wireless Sensor Network (WSN) MAC Layer Design
Introduction Basic goal of WSN Ц УReliable data delivery consuming
Introduction Basic goal of WSN Ц УReliable data delivery consuming
LPL Ц Check Interval
LPL Ц Check Interval
MAC Energy Usage
MAC Energy Usage
Existing approaches
Existing approaches
S-MAC Ц Design
S-MAC Ц Design
S-MAC Ц Design
S-MAC Ц Design
B-MAC: Basic Concepts
B-MAC: Basic Concepts
Clear Channel Assessment
Clear Channel Assessment
Low Power Listening
Low Power Listening
Low Power Listening
Low Power Listening

ѕрезентаци€: ЂZ-MAC: Hybrid MAC for Wireless Sensor Networksї. јвтор: . ‘айл: ЂZ-MAC: Hybrid MAC for Wireless Sensor Networks.pptї. –азмер zip-архива: 2075  Ѕ.

Z-MAC: Hybrid MAC for Wireless Sensor Networks

содержание презентации ЂZ-MAC: Hybrid MAC for Wireless Sensor Networks.pptї
є—лайд“екст
1 Z-MAC: Hybrid MAC for Wireless Sensor Networks

Z-MAC: Hybrid MAC for Wireless Sensor Networks

Manesh Aia, Ajit Warrier, Jeongki Min, Injong Rhee Department of Computer Science North Carolina State University

2 CSMA Protocols

CSMA Protocols

When are they useful? When are they a bad idea? Can TDMA be a better solution? Why? Why not?

3 Effective Throughput CSMA vs

Effective Throughput CSMA vs

TDMA

Channel Utilization

TDMA

CSMA

# of Contenders

4 Z-MAC: Basic Objective

Z-MAC: Basic Objective

Channel Utilization

MAC

CSMA

TDMA

Z-MAC Combine best of both Eliminate worst of both

Can you do hybrid contention resolution?

Low Contention

High Contention

High

Low

Low

High

5 ZMAC - Basic Idea

ZMAC - Basic Idea

Use a base TDMA schedule Node transmissions scheduled on specific slots Allow non-owners of slots to 'steal' the slot from owners Provided owners are not transmitting Stealing done through competition (CSMA) Possible to guarantee High channel efficiency and fair (quality of service)

6 Z-MAC: Basic components

Z-MAC: Basic components

Scalable Efficient TDMA Scheduling Priority-based Contention Resolution Fairness Energy efficient and low overhead time sync Robust implementation Time synchronization errors. Radio interferences from unreachable nodes.

7 DRAND Ц Algorithm

DRAND Ц Algorithm

Radio Interference Map

1

0

3

2

DRAND slot assignment

0

1

Input Graph

8 DRAND Ц Algorithm Ц Successful Round

DRAND Ц Algorithm Ц Successful Round

Step II Ц Receive Grants

Step I Ц Broadcast Request

Step III Ц Broadcast Release

Step IV Ц Broadcast Two Hop Release

Request

Grant

Grant

Release

Two Hop Release

9 Z-MAC Ц Reserving Slots

Z-MAC Ц Reserving Slots

Time Frame Rule (TF Rule) Let node i be assigned to slot si, and let number of nodes within two hop neighbourhood be Fi then i's time frame is set to be 2a, where positive integer a is chosen to satisfy condition 2a-1 <= Fi < 2a Ц 1 In other words, i uses the si-th slot in every 2a time frame (i's slots are L * 2a + si, for all L=1,2,3,...)

E.g., 5 neighbors, you choose a = 3, and your slots are 1,9,17, Е

10 Z-MAC Ц Local Frames

Z-MAC Ц Local Frames

11 Z-MAC Ц Transmission Control

Z-MAC Ц Transmission Control

Slot Ownership If current timeslot for me, then I am Owner All other neighbouring nodes are Non-Owners. Low Contention Level Ц Nodes compete in all slots, albeit with different priorities. Before transmitting: if I am the Owner Ц take backoff = Random(To) else if I am Non-Owner Ц take backoff = To + Random(Tno) after backoff, sense channel, if busy repeat above, else send. Switches between CSMA and TDMA automatically depending on contention level

12 Z-MAC Ц Transmission Control

Z-MAC Ц Transmission Control

Time Slots

1

0

0

2

A(0)

B(1)

Owner Backoffs

Non-Owner Backoffs

Ready to Send, Start Random(To) Backoff

After Backoff, CCA Idle

Ready to Send, Start To + Random(Tno) Backoff

After Backoff, CCA Busy

13 Z-MAC Ц LCL

Z-MAC Ц LCL

2(2)

0(2)

1(2)

Time Slots

1

0

0

2

A(0)

B(1)

Collision at C

Problem Ц Hidden Terminal Collisions Although LCL effectively reduces collisions within one hop, hidden terminal could still manifest itself when two hops are involved.

14 Z-MAC Ц HCL

Z-MAC Ц HCL

2(2)

0(2)

1(2)

Time Slots

1

0

0

2

A(0)

B(1)

High Contention Level If in HCL mode, node can compete in current slot only if: It is owner of the slot OR It is one-hop neighbour to the owner of the slot

Slot in HCL, sleep till next time slot

Collisions still possible here

15 Z-MAC Ц Explicit Contention Notification

Z-MAC Ц Explicit Contention Notification

ECN Informs all nodes within two-hop neighbourhood not to send during its time-slot. When a node receives ECN message, it sets its HCL flag. High contention detected by lost ACKs or congestion backoffs. ECN Suppression HCL flag is soft state, so reset periodically Nodes need to resend ECN if high contention persists.

16 Performance Results

Performance Results

DRAND and ZMAC have been implemented on both NS2 and on Mica2 motes (Software can be downloaded from: http://www.csc.ncsu.edu/faculty/rhee/export/zmac/index.html)

17 Experimental Setup Ц Single Hop

Experimental Setup Ц Single Hop

Single-Hop Experiments: Mica2 motes equidistant from one node in the middle. All nodes within one-hop transmission range. Tests repeated 10 times and average/standard deviation errors reported.

18 Z-MAC Ц Two-Hop Experiments

Z-MAC Ц Two-Hop Experiments

Sink

Sources

Sources

Setup Ц Two-Hop Dumbbell shaped topology Transmission power varied between low (50) and high (150) to get two-hop situations. Aim Ц See how Z-MAC works when Hidden Terminal Problem manifests itself.

19 Experimental Setup - Testbed

Experimental Setup - Testbed

40 Mica2 sensor motes in Withers Lab. Wall-powered and connected to the Internet via Ethernet ports. Programs uploaded via the Internet, all mote interaction via wireless. Links vary in quality, some have loss rates up to 30-40%. Assymetric links also present (14-->15).

20 Z-MAC Ц Single-Hop Throughput

Z-MAC Ц Single-Hop Throughput

Z-MAC

B-MAC

21 Z-MAC Ц Two-Hop Throughput

Z-MAC Ц Two-Hop Throughput

High Power

Low Power

Z-MAC

Z-MAC

B-MAC

B-MAC

22 Conclusion

Conclusion

CSMA: - low channel utilization at high loads, - but good for dynamic load. TDMA - utilizes the channel for high, stable load - but poor with unpredictable traffic MAC protocol needed for best of both worlds ZMAC performs fractional slot reservations, rest TDMA Slot owners have greater priority in own slots Others steal an empty slot opportunistically (using CSMA) DRAND deficiencies stay. Heavy initialization (what if frequent topology changes)

23 Questions

Questions

24 DRAND Ц Algorithm Ц Unsuccessful Round

DRAND Ц Algorithm Ц Unsuccessful Round

Step II Ц Receive Grants from A,B,D but Reject from E

Step I Ц Broadcast Request

Step III Ц Broadcast Fail

Grant

Request

Reject

Grant

Fail

25 DRAND Performance Results Ц Run Time

DRAND Performance Results Ц Run Time

Single-Hop

Multi-Hop (Testbed)

Round Time Ц Single-Hop

Multi-Hop (NS2)

26 DRAND Performance Results Ц Message Count and Number of Slots

DRAND Performance Results Ц Message Count and Number of Slots

Multi-Hop (NS2)

Number of Slots Assigned Ц Multi-Hop (NS2)

Single Hop

27 Overhead (Hidden cost)

Overhead (Hidden cost)

Operation

Average (J)

StdDev

Neighbor Discovery

0.73

0.0018

DRAND

4.88

3.105

Local Frame Exchange

1.33

1.39

Time Synchronization

0.28

0.036

Total energy: 7.22 J Ц 0.03% of typical battery (2500mAh, 3V)

28 Multi Hop Results Ц Throughput

Multi Hop Results Ц Throughput

29 Fairness (two hop)

Fairness (two hop)

30 Multi Hop Results Ц Energy Efficiency (KBits/Joule)

Multi Hop Results Ц Energy Efficiency (KBits/Joule)

31 Question

Question

32 Conclusion

Conclusion

Z-MAC combines the strength of TDMA and CSMA High throughput independent of contention. Robustness to timing and synchronization failures and radio interference from non-reachable neighbors. Always falls back to CSMA. Compared to existing MAC It outperforms B-MAC under medium to high contention. Achieves high data rate with high energy efficiency.

33 Z-MAC Ц Local Frames

Z-MAC Ц Local Frames

Label is the assigned slot, number in parenthesis is maximum slot number within two hops

5(5)

After DRAND, each node needs to decide on frame size. Conventional wisdom Ц Synchronize with rest of the network on Maximum Slot Number (MSN) as the frame size. Disadvantage: MSN has to broadcasted across whole network. Unused slots if neighbourhood small, e.g. A and B would have to maintain frame size of 8, in spite of having small neighbourhood.

34 Z-MAC Ц Explicit Contention Notification

Z-MAC Ц Explicit Contention Notification

forward

forward

discard

discard

C experiences high contention C broadcasts one-hop ECN message to A, B, D. A, B not on routing path (C->D->F), so discard ECN. D on routing path, so it forwards ECN as two-hop ECN message to E, F. Now, E and F will not compete during C's slot as Non-Owners. A, B and D are eligible to compete during C's slot, albeit with lesser priority as Non-Owners.

Thick Line Ц Routing Path Dotted Line Ц ECN Messages

35 Z-MAC Ц Performance Results

Z-MAC Ц Performance Results

Setup Single-hop, Two-hop and Multi-hop topology experiments on Mica2 motes. Comparisons with B-MAC, default MAC of Mica2, with different backoff window sizes. Metrics: Throughput, Energy, Latency, Fairness

36 Z-MAC Ц Performance Results Ц Throughput, Fairness

Z-MAC Ц Performance Results Ц Throughput, Fairness

Setup Ц Single-Hop 20 Mica2 motes equidistant from a sink All nodes send as fast as they can Ц throughput, fairness measured at the sink. Before starting, made sure that all motes are within one-hop

37 Z-MAC Ц Energy Experiments

Z-MAC Ц Energy Experiments

Setup 10 nodes within single cell sending to one sink Find optimum (lowest) energy to get a given throughput at the sink

38 Z-MAC Ц Performance Results Ц Energy

Z-MAC Ц Performance Results Ц Energy

39 Z-MAC Ц Latency Experiments

Z-MAC Ц Latency Experiments

Source

Sink

Setup 10 nodes in a chain topology. Source at one end transmits 100 byte packets at rate of 1 packet/10 s towards sink at the other end. Packet arrival time observed at each intermediate node, average per-hop latency calculated and then reported for different duty cycles.

40 Multi Hop Results

Multi Hop Results

41 Multi Hop Results

Multi Hop Results

42 Z-MAC Ц Performance Results Ц Latency

Z-MAC Ц Performance Results Ц Latency

43 Q & A

Q & A

Z-MAC Ц a Hybrid MAC for Wireless Sensor Networks

Thank you for your participation

44 Agenda Introduction Wireless Sensor Network (WSN) MAC Layer Design

Agenda Introduction Wireless Sensor Network (WSN) MAC Layer Design

principles Basic Idea Distributed TDMA Scheduling (DRAND) TDMA Scheduling DRAND Performance Results Z-MAC B-MAC (LPL, CCA) Performance Comparisons

45 Introduction Basic goal of WSN Ц УReliable data delivery consuming

Introduction Basic goal of WSN Ц УReliable data delivery consuming

minimum powerФ. Diverse Applications Low to high data rate applications Low data rate Periodic wakeup, sense and sleep High data rate (102 to 105 Hz sampling rate) In fact, many applications are high rate Industrial monitoring, civil infrastructure, medial monitoring, industrial process control, fabrication plants (e.g., Intel), structural health monitoring, fluid pipelining monitoring, and hydrology

Pictures by Wei Hong, Rory OТconnor, Sam Madden

46 LPL Ц Check Interval

LPL Ц Check Interval

Too small Energy wasted on Idle Listening Too large Energy wasted on packet transmission (large preamble) In general, longer check interval is better.

47 MAC Energy Usage

MAC Energy Usage

Four important sources of wasted energy in WSN: Idle Listening (required for all CSMA protocols) Overhearing (since RF is a broadcast medium) Collisions (Hidden Terminal Problem) Control Overhead (e.g. RTS/CTS or DATA/ACK)

48 Existing approaches

Existing approaches

Hybird (CSMA + TDMA) SMAC by Ye, Heidemann and Estrin @ USC Duty cycled, but synchronized over macro time scales for neighbor communication CSMA+Duty Cycle+LPL BMAC by Polastre, Hill and Culler @ UC Berkeley Duty cycled, but Low power listen - clever way reducing energy consumption (similar to aloha preamble sampling)

49 S-MAC Ц Design

S-MAC Ц Design

Listen Period Sleep/Wake schedule synchronization with neighbors Receive packets from neighbors Sleep Period Turn OFF radio Set timer to wake up later Transmission Send packets only during listen period of intended receiver(s) Collision Handling RTS/CTS/DATA/ACK

50 S-MAC Ц Design

S-MAC Ц Design

Schedules can differ, prefer neighboring nodes to have same schedule

Border nodes may have to maintain more than one schedule.

51 B-MAC: Basic Concepts

B-MAC: Basic Concepts

Keep core MAC simple Provides basic CSMA access Optional link level ACK, no link level RTS/CTS CSMA backoffs configurable by higher layers Carrier sensing using Clear Channel Assessment (CCA) Sleep/Wake scheduling using Low Power Listening (LPL)

52 Clear Channel Assessment

Clear Channel Assessment

Before transmission Ц take a sample of the channel If the sample is below the current noise floor, channel is clear, send immediately. If five samples are taken, and no outlier found => channel busy, take a random backoff Noise floor updated when channel is known to be clear e.g. just after packet transmission

53 Low Power Listening

Low Power Listening

Similar to ALOHA preamble sampling Wake up every Check-Interval Sample Channel using CCA If no activity, go back to sleep for Check-Interval Else start receiving packet Preamble > Check-Interval

54 Low Power Listening

Low Power Listening

Longer Preamble => Longer Check Interval, nodes can sleep longer At the same time, message delays and chances of collision also increase Length of Check Interval configurable by higher layers

Carrier sense

ЂZ-MAC: Hybrid MAC for Wireless Sensor Networksї
http://900igr.net/prezentacija/anglijskij-jazyk/z-mac-hybrid-mac-for-wireless-sensor-networks-242991.html
cсылка на страницу

 урсы английского

25 презентаций о курсах английского
”рок

јнглийский €зык

29 тем
—лайды