1、A Glimpse at Three Wireless Networking Problems,Bob KinickiComputer Science Departmentrekcs.wpi.eduColloquium October 5, 2007,October 5, 2007 Three Wireless Networking Problems,2,Outline,Thoughts and Mini-Motivation Wireless Networking Primer #1 Dynamic Rate Adaptation Performance problems with ARF
2、Rate Adaptation Algorithms RBAR, CARA, RFT and CARAF Wireless Sensor Networks (WSNs) #2 Dynamic Cluster Formation #3 Power-Aware MAC Protocols SMAC, TMAC, WiseMAC, SCP-MAC andCrankshaft,October 5, 2007 Three Wireless Networking Problems,3,My Research Space,Networking,Wireless Networking,Wireless Sen
3、sor Networks,198320032006,October 5, 2007 Three Wireless Networking Problems,4,The Future of Sensor Networks?,Wireless Primer,October 5, 2007 Three Wireless Networking Problems,6,LAN Terminolgy,802.3:Ethernet CSMA/CD 802.11a/b/g:WiFi CSMA/CA 802.15.4:ZigBee 802.11-basedlower data rates, lower power
4、Bluetooth: TDMA- wireless Personal Area Networks (PANs) that provide secure, globally unlicensed short-range radio communication. Clusters with max of 8: cluster head + 7 nodes,WSNs,October 5, 2007 Three Wireless Networking Problems,7,Wireless LANS,Infrastructure with AP (Access Point) Mobile Ad Hoc
5、 Networks (MANETs) Wireless Sensor Networks (WSNs) Interacting AP Topologies,October 5, 2007 Three Wireless Networking Problems,8,Infrastructure,Access Point,client,client,client,client,Internet,October 5, 2007 Three Wireless Networking Problems,9,Mobile Ad Hoc Network (MANET),BS,Wireless Sensor Net
6、work (WSN),October 5, 2007 Three Wireless Networking Problems,10,Wireless LAN Protocols,(a) A sending an RTS to B. (b) B responding with a CTS to A.,Tanenbaum slide,node D is possible hidden terminal,October 5, 2007 Three Wireless Networking Problems,11,Virtual Channel Sensing in CSMA/CA,C (in range
7、 of A) receives the RTS and based on information in RTS creates a virtual channel busy NAV(Network Allocation Vector). D (in range of B) receives the CTS and creates a shorter NAV.,Tanenbaum slide,October 5, 2007 Three Wireless Networking Problems,12,Basic CSMA/CA,N. Kim,possiblecollision !,October
8、5, 2007 Three Wireless Networking Problems,13,One-to-One Configuration Ad Hoc,Access Point,client,October 5, 2007 Three Wireless Networking Problems,14,One-to-One Configuration Ad Hoc,Access Point,client,October 5, 2007 Three Wireless Networking Problems,15,One-to-One Configuration Ad Hoc,Access Poi
9、nt,client,Distance Impacts:attenuation fading interference,#1 Dynamic Rate Adaptation,October 5, 2007 Three Wireless Networking Problems,17,802.11 Physical Layer,N. Kim,Adjust transmission rate on the fly,October 5, 2007 Three Wireless Networking Problems,18,BER vs SNR,Pavon,October 5, 2007 Three Wi
10、reless Networking Problems,19,Throughput vs SNR,Pavon,October 5, 2007 Three Wireless Networking Problems,20,Rate Adaptation versus Distance,J. Kim,October 5, 2007 Three Wireless Networking Problems,21,Single AP multiple clients (homogeneous),Access Point,client,client,client,client,Node Contention:P
11、roduces collisions,October 5, 2007 Three Wireless Networking Problems,22,Node Contention,N. Kim,without RTS/CTS,October 5, 2007 Three Wireless Networking Problems,23,Single AP multiple clients (heterogeneous),Access Point,client,client,client,client,Multiple Node EffectsCollisions AP queue overflow
12、link capture hidden terminal performance anomaly different NIC cards (Rate Adaptation NOT Standardized!),October 5, 2007 Three Wireless Networking Problems,24,Unfairness,Choi,October 5, 2007 Three Wireless Networking Problems,25,Multiple APs multiple clients (heterogeneous),Access Point,client,clien
13、t,client,client,Access Point,client,client,client,client,October 5, 2007 Three Wireless Networking Problems,26,Hidden Terminals,Wong,Without a hidden terminal, loss ratio 5.5%. One hidden AP with mild sending rate (0.379 Mbps) yields:,October 5, 2007 Three Wireless Networking Problems,27,RTS/CTS Sum
14、mary,RTS/CTS can reduce collisions. RTS/CTS can guard against and reduce hidden terminals. RTS/CTS adds overhead that reduces throughput. Normally, RTS/CTS is turned off!,October 5, 2007 Three Wireless Networking Problems,28,Rate Adaptation Algorithms,AARF ARF AMRR CARA CROAR DOFRA Fast-LA HRC LA LD
15、-ARF MiSer MultiRateRetry MPDU OAR ONOE PER RBAR RFT RRAA SampleRate SwissRA,October 5, 2007 Three Wireless Networking Problems,29,Rate Adaptation Algorithms,1997 ARF 1998 1999 2000 2001 RBAR 2002 MPDU OAR PER 2003 LA MiSer SwissRA 2004 AARF AMRR HRC MultiRateRetry 2005 Fast-LA LD-ARF RFT SampleRate
16、 2006 CARA CROAR DOFRA RRAA 2007,October 5, 2007 Three Wireless Networking Problems,30,Rate Adaptation Algorithms,Uses recent history and probes: ARF, AARF, SampleRate Long interval smoothing: ONOE, SampleRate Multiple rates: MultiRateRetry, AMRR, RRAA Uses RTS/CTS: RBAR, OAR, CROAR, CARA Uses RSSI
17、to approximate SNR, each node maintains 12 dynamic RSS thresholds: LA Puts checksum on header and use NACK to signal link loss error: LD-ARF Table lookup with thresholds: HRC,MPDU(len,rSNR,count) Fragmentation: DOFRA, RFT Miscellaneous: PER, MiSer, SwissRA, Fast-LA,October 5, 2007 Three Wireless Net
18、working Problems,31,Auto Rate Fallback (ARF),If two consecutive ACK frames are not received correctly, the second retry and subsequent transmissions are done at a lower rate and a timer is started. When the number of successfully received ACKs reaches 10 or the timer goes off, a probe frame is sent
19、at the next higher rate. However, if an ACK is NOT received for this frame, the rate is lowered back and the timer is restarted.,October 5, 2007 Three Wireless Networking Problems,32,ARF and AARF,October 5, 2007 Three Wireless Networking Problems,33,Receiver Based Auto Rate (RBAR),Receivers control
20、senders transmission rate. RTS and CTS are modified to contain info on size and rate not 802.11 compatible. Uses analysis of RTS reception (RSSI) to estimate SNR and send choice back to sender in CTS. Receiver picks rate based on apriori SNR thresholds in a lookup table.,October 5, 2007 Three Wirele
21、ss Networking Problems,34,Collision Aware Rate Adaptation (CARA),CARA uses two methods for identifying collisions: RTS probing Clear Channel Assessment (CCA) detectionRTS Probing Idea: Assume all RTS/CTS transmission failures after a successful RTS/CTS exchange must be due to channel errors. (Note t
22、his assumes hidden terminals are not possible) ,October 5, 2007 Three Wireless Networking Problems,35,RTS Probing,CARA-1 Data frame transmitted without RTS/CTS. If the transmission fails, RTS/CTS exchange is activated for the next retransmission. If this retransmission fails assume channel quality p
23、roblem, then the rate is lowered. If retransmission with RTS/CTS is successful assume collision occurred, stay at same rate and send next frame without RTS/CTS.,October 5, 2007 Three Wireless Networking Problems,36,Clear Channel Assessment (CCA),J. Kim,ACK,October 5, 2007 Three Wireless Networking P
24、roblems,37,CCA Option,Case 2: It is a collision. Transmit without increasing failure count and lowering the transmission rate. No RTS/CTS probe is needed.Case 1 and Case 3: Initiate RTS/CTS probe scheme.,October 5, 2007 Three Wireless Networking Problems,38,CARA-1 (with RTS Probing),J. Kim,October 5
25、, 2007 Three Wireless Networking Problems,39,CARA-2 (with CCA),J. Kim,October 5, 2007 Three Wireless Networking Problems,40,802.11 MAC Fragmentation,Zhu,October 5, 2007 Three Wireless Networking Problems,41,Rate-based Fragmentation Thresholding (RFT),Fragmenting a frame can increase the probability
26、of the fragment being received successfully. Propose a dynamic fragmentation scheme with different fragmentation thresholds based on different channel conditions. Namely, fragment sizes vary with the chosen adaptation rate.,October 5, 2007 Three Wireless Networking Problems,42,CARAF (CARA with Fragm
27、entation),Dan Courceys MS thesis: Combine CARA with Fragmentation. Top Level Scheme: Upon CCA determination of collision, use fragmentation. If CCA shows idle, initiate RTS/CTS probe. If probe fails lower transmission rate.Investigate how to vary fragment size to maximize throughput and increase the
28、 likelihood of CCA case 2,Wireless Sensor Networks (WSNs),October 5, 2007 Three Wireless Networking Problems,44,Wireless Sensor Networks,A distributed connection of nodes that coordinate to perform a common task. In many applications, the nodes are battery powered and it is often very difficult to r
29、echarge or change the batteries. Prolonging network lifetime is a critical issue. Sensors often have long period between transmissions (e.g., in seconds). Thus, a good WSN MAC protocol needs to be energy efficient.,October 5, 2007 Three Wireless Networking Problems,45,Wireless Sensor Networks,Anothe
30、r attribute is scalability to change in network size, node density and topology. In general, nodes can die, join later or be mobile. Often high bandwidth is not important. Nodes can take advantage of short-range, mulit-hop communication to conserve energy.,October 5, 2007 Three Wireless Networking P
31、roblems,46,Wireless Sensor Networks,Sources of energy waste: Idle listening, collisions, overhearing and control overhead. Idle listening dominates (measurements show idle listening consumes between 50-100% of the energy required for receiving.) Idle listening: listen to receive possible traffic tha
32、t is not sent.,October 5, 2007 Three Wireless Networking Problems,47,Power Measurements,October 5, 2007 Three Wireless Networking Problems,48,Wireless Sensor Networks,Duty cycle: ratio between listen time and the full listen-sleep cycle.central approach lower the duty cycle by turning the radio off
33、part of the time. Three techniques to reduce the duty cycle: TDMA Schedule contention periods LPL (Low Power Listening),October 5, 2007 Three Wireless Networking Problems,49,Techniques to Reduce Idle Listening,TDMA requires cluster-based or centralized control. Scheduling ensures short listen period
34、 when transmitters and listeners can rendezvous and other periods where nodes sleep (turn off their radios). LPL nodes wake up briefly to check for channel activity without receiving data. If channel is idle, node goes back to sleep. If channel is busy, node stays awake to receive data. A long pream
35、ble (longer than poll period) is used to assure than preamble intersects with polls.,#2 Dynamic Cluster Formation,October 5, 2007 Three Wireless Networking Problems,51,Choosing Cluster Heads/ Forming Clusters,Two-tier scheme: A fixed number of cluster heads that communicate with BS (base station). N
36、odes in cluster communicate with head (normally TDMA). TDMA allows fixed schedule of slots forsensor to send to cluster head and receive head transmissions.,BS,October 5, 2007 Three Wireless Networking Problems,52,BS,Choosing Cluster Heads/ Forming Clusters,Periodically select new cluster heads to m
37、inimize power consumption and maximize WSN lifetime. More complex problem when size of cluster changes dynamically. As time goes by, some sensor nodes die! Not worried about coverage issues!,X,X,X,X,X,October 5, 2007 Three Wireless Networking Problems,53,Dynamic Cluster Formation,TDMA cluster algori
38、thms: LEACH, Bluetooth, Rick Skowyras MS thesis:Energy Efficient Dynamic Reclustering Strategy for WSNs Leach-like with a fitness function and periodic reclustering. He hopes to design a distributed genetic algorithm to speed the recluster time.,#3 Power-Aware MAC Protocols,October 5, 2007 Three Wir
39、eless Networking Problems,55,Tiered WSN Architectures, Stathopoulos,October 5, 2007 Three Wireless Networking Problems,56,Power Aware MAC Protocols,1997 1998 PAMAS 1999 2000 2001 SMAC 2002 LPL NPSM 2003 TMAC TRAMA TinyOS-MAC EMACs 2004 BMAC DMAC LMAC WiseMAC 2005 PMAC ZMAC SP 2006 SCP-MAC 2007 Crank
40、shaft,October 5, 2007 Three Wireless Networking Problems,57,Power Aware MAC Protocols,Three approaches to saving power: 1. TDMA: TRAMA, EMACs, LMACCrankshaft 2. Schedule: PAMAS, SMAC, TMAC, DMAC, PMAC, SCP-MAC3. Low Power Listening: LPL, BMAC, WiseMACCross-Layering: SP, BSD,October 5, 2007 Three Wir
41、eless Networking Problems,58,SMAC,All nodes periodically listen, sleep and wakeup. Nodes listen and send during the active period and turn off their radios during the sleep period. The beginning of the active period is a SYNC period used to accomplish periodic synchronization and remedy clock drift.
42、 Following the SYNC period, data may be transferred for the remainder of the active period using RTS/CTS for unicast transmissions. Long frames are fragmented and transmitted as a burst. SMAC controls the duty cycle to tradeoff energy for delay. However, as density of WSN grows, SMAC incurs addition
43、al overhead in maintaining neighbors schedules.,October 5, 2007 Three Wireless Networking Problems,59,SMAC,October 5, 2007 Three Wireless Networking Problems,60,TMAC,TMAC employs an adaptive duty cycle by using a very short listening window at the beginning of each active period. After the SYNC port
44、ion of the active period, RTS/CTS is used in listening window. If no activity occurs, the node goes to sleep. TMAC saves power at the cost of reduced throughput and additional delay.,October 5, 2007 Three Wireless Networking Problems,61,TMAC,October 5, 2007 Three Wireless Networking Problems,62,Wise
45、MAC,Algorithm focused on downlink protocol for infrastructure WSNs: Access Point (AP) is assumed to have wired link to Internet and not battery-powered. Based on preamble sampling. WiseMac regularly samples (via listening) for a short duration during preamble. All sensor nodes sample with same const
46、ant period TW .,October 5, 2007 Three Wireless Networking Problems,63,WiseMAC,Normally, wake-up preamble needs to be of size TW . This implies low power use when WSN is idle. But this yields large power consumption overhead for reception. WiseMAC AP learns and keeps the sampling schedule of all sens
47、ors in a up-to-date table. Sensors ACKs provide info for the table. WiseMAC then minimizes the preamble duration, TP . Needs to deal with clock drift to get this right.,October 5, 2007 Three Wireless Networking Problems,64,WiseMAC,October 5, 2007 Three Wireless Networking Problems,65,Zigbee MAC,802.
48、11 MAC PSM (Power Save Mode) uses beacon frames to coordinate and periodic wake-up by sensor nodes. Mike Putnams thesis: A Beaconless Protocol for Improving Energy Efficiency in Wireless Sensor Networks,October 5, 2007 Three Wireless Networking Problems,66,WiseMAC,October 5, 2007 Three Wireless Netw
49、orking Problems,67,Scheduled Channel Polling (SCP-MAC),With channel polling (LPL scheme), receiver efficiency is gained through cost to sender. LPLs are very sensitive to tuning for neighborhood size and traffic rate. By synchronizing channel polling times of all neighbors, long preambles are eliminated and ultra-low duty cycles (below the LPL 1-2% limits) are possible.,
