b-mac versatile low power media access for wireless ：b-mac通用的低功耗无线媒体接入

B-MAC: Versatile Low Power Media Access for Wireless Sensor Networks,SenSys 04,Reminder: Proposal Presentation on Monday, March 5,Prepare powerpoint slides to motivate your project and show the overall approach to tackling the problemCome at least 10 minutes before the class begins Give your slides to the tech staffLean how to use the presentation tool etc.Teams & presentation order:Mike & Vic (+ Brian)Chris & YanDahee & ChaoSurabhMehmet,Design goals of B-MAC,Low power operationEffective collisionSimple implementation, small code & RAM sizeEfficient channel utilization at low & high data ratesReconfigurable by network protocolsTolerant to changing RF/Networking conditionsScalable to large numbers of nodes,Small, configurable MAC,Export control to higher services to support wide variety of WSN workloadsWSNs are supposed to support various applicationsS-MAC (discussed in the previous class) is more than a link layer protocolDrawbacks of S-MACScalability: A node may have to remember many schedules and wake up accordinglyMAC layer may not be the best place for sleep scheduling & synchronization,Adaptive, reconfigurable MAC,Adaptive bidirectional interface for WSN applicationsReconfigure the MAC protocol based on the current workloadIdentify the best parameters for an arbitrary low power WSN applications at compile or run time & estimate the applications lifetime,B-MAC Design,Really simpleCSMA via CCA (Clear Channel Assessment) & backoffLow power listening via PreambleAcknowledgmentEnable/disable anything above and allow to build anything on top of the configured B-MAC!,B-MAC Interfaces,Clear Channel Assessment,Effective collision avoidanceFind out whether the channel is idleIf too pessimistic: waste bandwidthIf too optimistic: more collisionsKey observationAmbient noise may change significantly depending on the environmentPacket reception has fairly constant channel energySoftware approach to estimating the noise floor,Take a signal sample when the channel is assumed to be freeRight after a packet is transmitted or when no valid data is receivedTake exponential moving average (EMA) of the median signal strengthWorks as a low pass filterSmoothed idle signal level Sm(t) = a * S(t) + (1 - a) * Sm(t-1)Sm(t): EMA at time t S(t-1): Signal strength of ambient noise at t Sm(t-1): EMA at time t-1 It contrasts to common threshold-based methods in which only a single sample is takenResilient to time-varying ambient noise,CCA vs. Threshold techniques,Idle,Threshold: waste channel utilization CCA: Fully utilize the channel since a valid packet could have no outlier significantly below the noise floor,CCA dynamically adjusts threshold,CCA finds channelbusy/idle status withhigh accuracy,CCA can be turned on/offIf turned off, a schedule-based protocol, e.g., S-MAC, can be implemented atop B-MACIf turned on, initial channel backoff when sending a messageB-MAC does not set the backoff time, but signals an event to the higher service that sent the packet The higer level service may return an initial backoff time or ignore the event If ignored, use a short random delay,Low Power Listening: Preamble Sampling,Sender,Receiver,Preamble,Send data,Preamble sampling,Active to receive a message,S,R,|Preamble| Sampling period,Preamble is not a packet but a physical layer RF pulseMinimize overhead,Optional link layer ACK,If enabled, ACK is sent immediately after receiving a unicast packetOverall, B-MAC is easier to implement than S-MACNo RTS/CTSIs this always good? or ?We know RTS/CTS can reduce hidden/exposed node problem You may have to implement RTS/CTS on your own. Simple but not very friendlyNo synchronizationNo need for a schedule table in S-MACBut periodic sleep & wake-up is a good approach to energy saving,Modeling Lifetime,Monitoring applicationsE = Esleep + Elisten + Ed + Erx + EtxGiven #nodes in the neighborhood, BMAC can estimate the network lifetimeLifetime tl = 1/E * Cbatt * V * 60 * 60,Derivation of Lifetime,Ed = td * cdata * V where td = tdata * rEtx = ttx * ctxb * V where ttx = r * (Lpreamble + Lpacket) * ttxbErx = trx * crxb * V where trx n * r * (Lpreamble + Lpacket) * trxbr * sum_i=1n ( children (i) + 1 )Lpreamble ti / trxb,Derivation of Lifetime (Contd),Esample = 17.3 uJElisten Esample * 1/titlisten = (tr_init + tr_on + trx/tx + tsr) * 1/titsleep = 1 trx ttx td tlistenEsleep = tsleep * csleep * VLifetime tl = 1/E * Cbatt * V * 60 * 60,Network Parameters,Scientists may determine the physical location of the nodes & ideal sampling rateCompute the parameters to get the best lifetime that B-MAC can achieveBest LPL check interval is the lowest line at a given network density in the following graph,If n = 20, 50ms checkinterval is optimal,If n=60, 25ms is best,Experiments,Compare BMAC to S-MAC & T-MACT-MAC is similar to S-MAC, but a receiver goes to sleep if it does not receive any messageB-MAC & S-MAC: implemented in TinyOSTMAC: simulated in Matlab,TinyOS Implementation,B-MAC does not need timestamp,Packet transmission time vs. Checking frequency,More frequent checking of the radioShorter transmission timeMore energy consumption,LPL check interval,Channel utilization,Place n nodes equidistant from a receiver Increase n to increase load BMAC relies on higher level services to send data according to the traffic pattern Consider hidden node problem too For example, after a packet is sent to the parent, nodes in the same cell wait for a certain amount of time for the parent to forward the packet up the tree Always work? More difficulty for developing sensing applications?,Energy per byte,End-to-end latency,Contention-Free Protocols,Classic Protocols,TDMA (Time Division Multiple Access)A node can sleep when it is not its turn to send or receiveFDMA (Frequency Division Multiple Access)CDMA (Code Division Multiple Access)No node within two hops can use the same slot to avoid the hidden node problem,Optimal channel assignment,Achieve contention-free communication using the minimum number of channelsThe problem of assigning a minimum number of channels for an arbitrary graph is NP-hardDevelop efficient heuristicsCentralized approaches do not scale,Stationary MAC and Startup,Local synchronization onlyStarting phaseHandshaking on a common control channelEach link utilizes a unique random frequency or CDMA frequency hopping codeAssume there are sufficiently many frequencies or codesPeriodically use the slot,BFS/DFS-based scheduling,Breadth-first or depth-first traversals of a data gathering treeEvery single node is given a slotBFS might provide more chances for aggregationDFS may transmit individual data more quicklyGlobal synchronization required,Reservation-based synchornized MAC (ReSync),TDMA is not flexible enough to allow the traffic from each node to change over timeReSync provides more flexibilityEach node maintains an epoch based on its local time (or can be synchronized with nearby neighbors)Select a regular time in each epoch to send a short intent messageProbability of collisions is low since the intent is very shortListen long enough to learn when the neighbor is sending the intentThe intended receiver wakes up at the corresponding time to receive the messageNo RTS/CTSData transmissions are scheduled randomly,Traffic-adaptive medium access (TRAMA),Distributed TDMA for flexible & dynamic scheduling of time slotsDivide time epochs into a set of short signaling slots followed by a set of longer transmission slotsKey componentsNeighbor protocol (NP)Schedule exchange protocol (SEP)Adaptive election algorithm (AEP),Neighbor Protocol,Nodes exchange one-hop neighbor info during the random access signaling slotsEnsure the slots are long enough to allow all nodes to get consistent two-hop neighbor info,Schedule exchange protocol,Each node publishes its schedule during the last winning slot in each epoch