Monday, February 16, 2009
Research projects and collaboration
Mike Mitzenmacher posted an interesting article about doing collaborative research on his own blog, which is intended for students in his graduate course (CS222) this term, but is just as relevant for this class as well. Good reading.
Tuesday, February 10, 2009
Z-MAC and Component-Based MAC Architecture
Z-MAC: a Hybrid MAC for Wireless Sensor Networks
(Rhee et al., SenSys 2005)
A Component-Based MAC Architecture for Power-Efficient Media Access Control in Wireless Sensor Networks
(Rhee et al., SenSys 2005)
Today we continued our discussion of MAC protocols by discussing Z-MAC, a hybrid CSMA / TDMA protocol. CSMA is ideal for low traffic conditions, but can yield low throughput under high contention. TDMA can efficiently schedule nodes and maintain high channel utilization, but slots are wasted under low traffic conditions, there are other problems, such as distributed slot assignment. Z-MAC is proposed as a hybrid of these two approaches, primarily utilizing CSMA but switching to TDMA mode when under high contention. This should, in theory, improve performance at both ends of the utilization spectrum, while mitigating many of TDMA's drawbacks by gracefully degrading to CSMA.
The class raised several interesting points about Z-MAC (specifically the TDMA element). One main concern was the practical difficulties involved in slot assignment. Z-MAC does initial slot assignment at startup, but simultaneous startup may be impractical in real-world deployments. Even if the practical difficulties of slot assignment are handled smoothly, the links are assumed to be static until the setup phase is run again. This may not be entirely true in a real deployment either, as even the paper states that "sensor networks may undergo frequent topology changes." While distributed slot assignment is certainly possible, many of us felt that this may be more difficult to achieve in practice than implied.
We also discussed the HCL (High Contention Level) and LCL (Low Contention Level) modes employed by the protocol. HCL is triggered by a ECN (Explicit Contention Notification) message, and nodes enter a TDMA-like mode, where slot owners have a smaller contention window (and thus, priority for their assigned slots). One major point that arose during our discussion focuses on why Z-MAC allows nodes in a one-hop neighborhood to contend for a neighbor's slot when that neighbor does not utilize it's own slot in HCL mode? For example, consider a three-node chain in HCL mode: A--B--C, assigned slots 1,2,3 respectively. If Slot=2, and the owner (B) does not transmit, then both A and C could contend for the same slot and transmit, since they are both in the one-hop neighborhood of B. This could cause a hidden terminal problem. Thus, the only way of avoiding hidden terminals is actually to limit slot contention to the slot owner(s). However, upon further discussion, it was suggested that if a slot is not going to be utilized, then deliberately allowing a situation where a hidden terminal could arise is better than just wasting the slot entirely. On the other hand, energy efficiency is important in WSNs -- so some argued against allowing the one-hop neighborhood to contend for a slot, because transmissions might be useless, wasting precious energy.
This brought us to our next topic: energy utilization. Clearly, the overhead of Z-MAC (such as slot assignment / clock synchronization) will utilize more energy than a simple CSMA-only scheme requiring none of this overhead. The big question for us: Do the energy savings of HCL under high contention really justify the energy cost of this overhead? We feel this would be an interesting area for deep exploration, particularly through the lens of practical workloads.
We also discussed practical issues regarding time synchronization. In an application with very low network utilization, synchronizing clocks every 100 packets may result in large amounts of clock drift between nodes. If traffic suddenly surges, and ECN messages are broadcasted, when nodes switch into HCL mode, they may have extremely out-of-sync clocks. It's not entirely apparent that the LCL to HCL switch is necessarily a smooth one under a situation like this.
Ultimately, we wondered how Z-MAC would perform under real-world workloads. We agreed that situations where nodes are transmitting at near-maximum capacity are rare in real-world sensor networks, and want to see more a detailed analysis of all the popular MAC protocols through a variety of workloads. This brought us back to our previous points regarding the need for standardized MAC protocol benchmarks. In general, while we thought that Z-MAC was a strong idea, we had difficulty becoming comfortable with the exact dynamics of the system. For practical system deployment, we were undecided whether it would make sense to pick this hybrid MAC, or a simpler system with less overhead, like B-MAC.
Although we ran out of time before fully discussing the component-based MAC architectures, we did get a chance to hit on a few high-level topics. Before even discussing any details of the MLA (MAC Layer Architecture), we discussed the overall implications of creating a framework for creating MAC protocols. As the authors write, "using these components, developers can quickly construct new MAC protocols that meet the demands of their specific applications." While we felt that reuse and structure is a good thing, is it necessarily good to have a framework for creating more MAC protocols? Do we really need to have a library of hundreds or thousands of MAC protocols that we can choose from when developing sensor network applications? In general, most of us felt that tailoring the MAC protocol for specific applications is a good thing. However, many felt that the alternative of having more complete MAC protocols with many more tuning knobs, or perhaps even a self-tuning MAC protocol, could be a viable alternative to creating a framework for developing entirely new MAC protocols.
(Rhee et al., SenSys 2005)
A Component-Based MAC Architecture for Power-Efficient Media Access Control in Wireless Sensor Networks
(Rhee et al., SenSys 2005)
Today we continued our discussion of MAC protocols by discussing Z-MAC, a hybrid CSMA / TDMA protocol. CSMA is ideal for low traffic conditions, but can yield low throughput under high contention. TDMA can efficiently schedule nodes and maintain high channel utilization, but slots are wasted under low traffic conditions, there are other problems, such as distributed slot assignment. Z-MAC is proposed as a hybrid of these two approaches, primarily utilizing CSMA but switching to TDMA mode when under high contention. This should, in theory, improve performance at both ends of the utilization spectrum, while mitigating many of TDMA's drawbacks by gracefully degrading to CSMA.
The class raised several interesting points about Z-MAC (specifically the TDMA element). One main concern was the practical difficulties involved in slot assignment. Z-MAC does initial slot assignment at startup, but simultaneous startup may be impractical in real-world deployments. Even if the practical difficulties of slot assignment are handled smoothly, the links are assumed to be static until the setup phase is run again. This may not be entirely true in a real deployment either, as even the paper states that "sensor networks may undergo frequent topology changes." While distributed slot assignment is certainly possible, many of us felt that this may be more difficult to achieve in practice than implied.
We also discussed the HCL (High Contention Level) and LCL (Low Contention Level) modes employed by the protocol. HCL is triggered by a ECN (Explicit Contention Notification) message, and nodes enter a TDMA-like mode, where slot owners have a smaller contention window (and thus, priority for their assigned slots). One major point that arose during our discussion focuses on why Z-MAC allows nodes in a one-hop neighborhood to contend for a neighbor's slot when that neighbor does not utilize it's own slot in HCL mode? For example, consider a three-node chain in HCL mode: A--B--C, assigned slots 1,2,3 respectively. If Slot=2, and the owner (B) does not transmit, then both A and C could contend for the same slot and transmit, since they are both in the one-hop neighborhood of B. This could cause a hidden terminal problem. Thus, the only way of avoiding hidden terminals is actually to limit slot contention to the slot owner(s). However, upon further discussion, it was suggested that if a slot is not going to be utilized, then deliberately allowing a situation where a hidden terminal could arise is better than just wasting the slot entirely. On the other hand, energy efficiency is important in WSNs -- so some argued against allowing the one-hop neighborhood to contend for a slot, because transmissions might be useless, wasting precious energy.
This brought us to our next topic: energy utilization. Clearly, the overhead of Z-MAC (such as slot assignment / clock synchronization) will utilize more energy than a simple CSMA-only scheme requiring none of this overhead. The big question for us: Do the energy savings of HCL under high contention really justify the energy cost of this overhead? We feel this would be an interesting area for deep exploration, particularly through the lens of practical workloads.
We also discussed practical issues regarding time synchronization. In an application with very low network utilization, synchronizing clocks every 100 packets may result in large amounts of clock drift between nodes. If traffic suddenly surges, and ECN messages are broadcasted, when nodes switch into HCL mode, they may have extremely out-of-sync clocks. It's not entirely apparent that the LCL to HCL switch is necessarily a smooth one under a situation like this.
Ultimately, we wondered how Z-MAC would perform under real-world workloads. We agreed that situations where nodes are transmitting at near-maximum capacity are rare in real-world sensor networks, and want to see more a detailed analysis of all the popular MAC protocols through a variety of workloads. This brought us back to our previous points regarding the need for standardized MAC protocol benchmarks. In general, while we thought that Z-MAC was a strong idea, we had difficulty becoming comfortable with the exact dynamics of the system. For practical system deployment, we were undecided whether it would make sense to pick this hybrid MAC, or a simpler system with less overhead, like B-MAC.
Although we ran out of time before fully discussing the component-based MAC architectures, we did get a chance to hit on a few high-level topics. Before even discussing any details of the MLA (MAC Layer Architecture), we discussed the overall implications of creating a framework for creating MAC protocols. As the authors write, "using these components, developers can quickly construct new MAC protocols that meet the demands of their specific applications." While we felt that reuse and structure is a good thing, is it necessarily good to have a framework for creating more MAC protocols? Do we really need to have a library of hundreds or thousands of MAC protocols that we can choose from when developing sensor network applications? In general, most of us felt that tailoring the MAC protocol for specific applications is a good thing. However, many felt that the alternative of having more complete MAC protocols with many more tuning knobs, or perhaps even a self-tuning MAC protocol, could be a viable alternative to creating a framework for developing entirely new MAC protocols.
Monday, February 9, 2009
The MAC soupbowl
http://www.st.ewi.tudelft.nl/~koen/MACsoup/index.php
In view of our current fascination with MAC layer protocols, I found this wonderful website that talks about each of them briefly.
In view of our current fascination with MAC layer protocols, I found this wonderful website that talks about each of them briefly.
Sunday, February 8, 2009
MDW unplugged
I've decided to start a personal blog where I get a chance to rant and rave about topics dear to my heart, mostly dealing with sensornets, but not necessarily related to this course. For my first post I talk a bit about the relative difficulties of sensor nets research versus other areas of systems. Feel free to check it out and comment.
Friday, February 6, 2009
B-MAC and Taming the underlying challenges
Versatile Low Power Media Access for Wireless Sensor Networks
(Polastre et al., Sensys 2004)
Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks
(Woo et al., Sensys 2003)
Today we had another round of interesting discussions on another two low level issues in sensor networks: radio channel characteristics and low power MAC design.
We started by talking about what clear channel assessment (CCA) means when used to detect transmissions. CCA tells you when the channel is 'clear' instead of when someone is actually transmitting a packet. The B-MAC showed that using a simple threshold is a poor approach but applying EWMA filter to the CCA result performs reasonably well. Then we discussed hidden terminal problem and benefit/overhead of RTS-CTS scheme as we talked about the comparison of B-MAC and S-MAC. Many of us thought the main difference is configurability. B-MAC exposes more knobs to the application, such as LPL preamble length, check interval and Acks, while S-MAC parameters are not controllable by other layers of the system. The result is higher performance from B-MAC because with application-specific knowledge one can turn on and off these low level features to minimize the overhead of the MAC protocol. On the flip side, this also means that the application programmer needs to know how to turns these knobs that are related to each other. It might seem that each node can tune these parameters dynamically and optimize based on the local conditions. However, it is often not so easy because neighboring nodes need to agree on many of the parameters. For example, you would almost always want the preamble length to be longer than check intervals in order to guarantee waking up of the receiver. Turning on and off Acks could be very confusing too. So, one might ask whether B-MAC is providing too much flexibility and forcing the application to be more complicated.
Another interesting question that was brought up today was: why not use power control, a knob that's there provided by the radio chip? Cell phones do it all the time to save power. Motes should do it too. Lowering transmission power can reduce the size of your neighborhood and therefore possibly increase overall throughput. I think this is an interesting option that hasn't been fully exploited by existing sensor network systems. Or, perhaps it makes higher layers, such as routing protocol, too difficult so people discarded the idea?
In the B-MAC paper, S-MAC was beaten up in almost every metric considered in the paper. With such observation, students asked about how the WSN community usually evaluates MAC protocols. The answer seems to be that every MAC paper chooses different application domains and metrics to show the protocol proposed in the paper performs better than other alternatives but there really hasn't been a complete study to compare them in a standard set of representative environments objectively. Given that so many MAC protocols have been proposed, perhaps it is a good time to do such a study.
One more interesting point that was brought up in class today was: what makes sensor networks a different research area than mobile ad hoc networks (MANET) that has been around for a long time. This is similar to the question we asked on Tuesday on why motes are so different than other computers that it needs new OSes. The papers we read so far mention very little about MANET work while WSN shares some of the challenges with MANET, such as multi-hop routing in wireless networks. I think the distinction still comes from the focus on resource constraints of sensor nodes. MANET community has mostly assumed that the nodes in the network are at least PDA or laptop class of devices. Many of them are even constantly powered (e.g. in military vehicles) so the processing power and energy available to the nodes are plenty. So, MANET research tends to focus on infrastructureless network architecture (no cell tower, no base station), node mobility and dealing with rapid topology changes of the network instead of efficiently managing system resources on the moble nodes. Another distinction is research approach. For example, a lot of MANET research results were derived from simulation based on simple unit-disc model. WSN research community, instead, puts more effort into real experiments to evaluate protocols running on top of real radio.
(Polastre et al., Sensys 2004)
Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks
(Woo et al., Sensys 2003)
Today we had another round of interesting discussions on another two low level issues in sensor networks: radio channel characteristics and low power MAC design.
We started by talking about what clear channel assessment (CCA) means when used to detect transmissions. CCA tells you when the channel is 'clear' instead of when someone is actually transmitting a packet. The B-MAC showed that using a simple threshold is a poor approach but applying EWMA filter to the CCA result performs reasonably well. Then we discussed hidden terminal problem and benefit/overhead of RTS-CTS scheme as we talked about the comparison of B-MAC and S-MAC. Many of us thought the main difference is configurability. B-MAC exposes more knobs to the application, such as LPL preamble length, check interval and Acks, while S-MAC parameters are not controllable by other layers of the system. The result is higher performance from B-MAC because with application-specific knowledge one can turn on and off these low level features to minimize the overhead of the MAC protocol. On the flip side, this also means that the application programmer needs to know how to turns these knobs that are related to each other. It might seem that each node can tune these parameters dynamically and optimize based on the local conditions. However, it is often not so easy because neighboring nodes need to agree on many of the parameters. For example, you would almost always want the preamble length to be longer than check intervals in order to guarantee waking up of the receiver. Turning on and off Acks could be very confusing too. So, one might ask whether B-MAC is providing too much flexibility and forcing the application to be more complicated.
Another interesting question that was brought up today was: why not use power control, a knob that's there provided by the radio chip? Cell phones do it all the time to save power. Motes should do it too. Lowering transmission power can reduce the size of your neighborhood and therefore possibly increase overall throughput. I think this is an interesting option that hasn't been fully exploited by existing sensor network systems. Or, perhaps it makes higher layers, such as routing protocol, too difficult so people discarded the idea?
In the B-MAC paper, S-MAC was beaten up in almost every metric considered in the paper. With such observation, students asked about how the WSN community usually evaluates MAC protocols. The answer seems to be that every MAC paper chooses different application domains and metrics to show the protocol proposed in the paper performs better than other alternatives but there really hasn't been a complete study to compare them in a standard set of representative environments objectively. Given that so many MAC protocols have been proposed, perhaps it is a good time to do such a study.
One more interesting point that was brought up in class today was: what makes sensor networks a different research area than mobile ad hoc networks (MANET) that has been around for a long time. This is similar to the question we asked on Tuesday on why motes are so different than other computers that it needs new OSes. The papers we read so far mention very little about MANET work while WSN shares some of the challenges with MANET, such as multi-hop routing in wireless networks. I think the distinction still comes from the focus on resource constraints of sensor nodes. MANET community has mostly assumed that the nodes in the network are at least PDA or laptop class of devices. Many of them are even constantly powered (e.g. in military vehicles) so the processing power and energy available to the nodes are plenty. So, MANET research tends to focus on infrastructureless network architecture (no cell tower, no base station), node mobility and dealing with rapid topology changes of the network instead of efficiently managing system resources on the moble nodes. Another distinction is research approach. For example, a lot of MANET research results were derived from simulation based on simple unit-disc model. WSN research community, instead, puts more effort into real experiments to evaluate protocols running on top of real radio.
Tuesday, February 3, 2009
TinyOS and Great Duck Island
System Architecture Directions for Networked Sensors
(Hill et al., ASPLOS 2000)
An Analysis of a Large Scale Habitat Monitoring Application
(Szewczyk et al., Sensys '04)
Today was our first proper class and we had a fantastic discussion! Everyone came prepared to talk about the papers, and I think it helped to do a little icebreaking before we got into the discussion itself. I'm really looking forward to the rest of the semester.
I wanted to kick off the class with these two "classic" papers on sensor networks, to help lay the groundwork for the rest of the term. These are great papers, and though I've read them a few times, it is interesting to revisit them now. TinyOS is almost 10 years old, and it's nice to return to the vintage work with some new perspective.
On reading both papers again, I was struck at how low level they both are. The ASPLOS paper really goes bottom-up from the hardware platform and does not indulge in laying out a broader perspective for the field of sensor networks as a whole. Neither paper portends the fetish for complex in-network processing or fancy decentralized algorithms that has taken over much of the community. (I'm one of those fetishists myself, but it's interesting how straight these papers play it.)
We started out talking about what is fundamentally different about sensor networks than conventional computing systems. Most folks seemed to have drunk the TinyOS Kool-Aid and agreed it was all about high concurrency, limited memory, and limited energy. I wanted to press on the point of high concurrency a bit. Aren't ALL computer systems fundamentally concurrent and event-driven? All operating systems are driven by interrupts (keyboard and mouse events, packets coming in, timers going off); are sensor networks really more concurrent than conventional systems? OK, well maybe it has something to do with the lack of buffering, and energy limitations. Now we are getting somewhere - what is fundamental about this? Finally we hit on what I think is essential here: that the limited resources conflate with the concurrency demands to force the programmer to be really "intimate" with their events. You can't hide behind threads or processes anymore: events are part and parcel of what you deal with as a programmer in this domain, so the OS structure had better expose them in a lean and flexible way.
I also wanted to challenge the assumption that motes need to be so small and memory-constrained. Where did this idea come from? The ASPLOS paper more or less assumes it; but if you look carefully at a lot of the potential applications it's not so obvious that you can't get away with, say, a PDA-class device. Strikingly, some of the early design decisions on the mote hardware had some pretty significant impact on the design of TinyOS. My favorite example is that RFM radio, which requires that you bit-bang it to transmit or receive; requiring a context switch every 50 usec (once per bit)! I wonder what would have happened had Jason Hill chosen a better radio or more powerful MCU when he designed the WeC mote. We could be in a very different place today.
But, why the asceticism? TinyOS forces you to tie both hands behind your back and peck at the keyboard with your nose to program... no threads, no sockets, heck, not even malloc or printf. Was this some kind of self-flagellation, doing penance for years of building bigger and faster computers (NOW)?
To understand this lineage one has to go back to the origin of the Berkeley TinyOS effort, which originated with Kris Pister's "Smart Dust" project. That group was developing mm^3 devices integrating extremely simple computation, communication, and sensing. David Culler had the bright idea to build a version of this using off-the-shelf components, to approximate that "plausible future" and study the possibilities enabled by this space. So from the get-go you're talking very resource constrained, and (this is critical) SMALL devices. That fundamental tenet of the sensor network design space was established early on and largely continues to this day; I still see sensor networks based around 16-bit MCUs and the CC2420 when they could just as well use a proper processor and 802.11 radio (for example, if the sensors are powered).
I wouldn't call this merely an academic exercise; but I think we learned a great deal about the fundamentals of this new design space by forcing ourselves to abandon some of our long-held attachments to such luxuries as virtual memory and protection domains. Had we tried to shoehorn PDAs running Linux and make them look kinda, sorta like "sensor networks" I think we would have missed an important opportunity to dig deeper and reveal some essential truths.
(Hill et al., ASPLOS 2000)
An Analysis of a Large Scale Habitat Monitoring Application
(Szewczyk et al., Sensys '04)
Today was our first proper class and we had a fantastic discussion! Everyone came prepared to talk about the papers, and I think it helped to do a little icebreaking before we got into the discussion itself. I'm really looking forward to the rest of the semester.
I wanted to kick off the class with these two "classic" papers on sensor networks, to help lay the groundwork for the rest of the term. These are great papers, and though I've read them a few times, it is interesting to revisit them now. TinyOS is almost 10 years old, and it's nice to return to the vintage work with some new perspective.
On reading both papers again, I was struck at how low level they both are. The ASPLOS paper really goes bottom-up from the hardware platform and does not indulge in laying out a broader perspective for the field of sensor networks as a whole. Neither paper portends the fetish for complex in-network processing or fancy decentralized algorithms that has taken over much of the community. (I'm one of those fetishists myself, but it's interesting how straight these papers play it.)
We started out talking about what is fundamentally different about sensor networks than conventional computing systems. Most folks seemed to have drunk the TinyOS Kool-Aid and agreed it was all about high concurrency, limited memory, and limited energy. I wanted to press on the point of high concurrency a bit. Aren't ALL computer systems fundamentally concurrent and event-driven? All operating systems are driven by interrupts (keyboard and mouse events, packets coming in, timers going off); are sensor networks really more concurrent than conventional systems? OK, well maybe it has something to do with the lack of buffering, and energy limitations. Now we are getting somewhere - what is fundamental about this? Finally we hit on what I think is essential here: that the limited resources conflate with the concurrency demands to force the programmer to be really "intimate" with their events. You can't hide behind threads or processes anymore: events are part and parcel of what you deal with as a programmer in this domain, so the OS structure had better expose them in a lean and flexible way.
I also wanted to challenge the assumption that motes need to be so small and memory-constrained. Where did this idea come from? The ASPLOS paper more or less assumes it; but if you look carefully at a lot of the potential applications it's not so obvious that you can't get away with, say, a PDA-class device. Strikingly, some of the early design decisions on the mote hardware had some pretty significant impact on the design of TinyOS. My favorite example is that RFM radio, which requires that you bit-bang it to transmit or receive; requiring a context switch every 50 usec (once per bit)! I wonder what would have happened had Jason Hill chosen a better radio or more powerful MCU when he designed the WeC mote. We could be in a very different place today.
But, why the asceticism? TinyOS forces you to tie both hands behind your back and peck at the keyboard with your nose to program... no threads, no sockets, heck, not even malloc or printf. Was this some kind of self-flagellation, doing penance for years of building bigger and faster computers (NOW)?
To understand this lineage one has to go back to the origin of the Berkeley TinyOS effort, which originated with Kris Pister's "Smart Dust" project. That group was developing mm^3 devices integrating extremely simple computation, communication, and sensing. David Culler had the bright idea to build a version of this using off-the-shelf components, to approximate that "plausible future" and study the possibilities enabled by this space. So from the get-go you're talking very resource constrained, and (this is critical) SMALL devices. That fundamental tenet of the sensor network design space was established early on and largely continues to this day; I still see sensor networks based around 16-bit MCUs and the CC2420 when they could just as well use a proper processor and 802.11 radio (for example, if the sensors are powered).
I wouldn't call this merely an academic exercise; but I think we learned a great deal about the fundamentals of this new design space by forcing ourselves to abandon some of our long-held attachments to such luxuries as virtual memory and protection domains. Had we tried to shoehorn PDAs running Linux and make them look kinda, sorta like "sensor networks" I think we would have missed an important opportunity to dig deeper and reveal some essential truths.
Intro slides posted
For anyone who missed class last Thursday, I've posted the introductory slides for CS263, which summarizes what the class is about (and perhaps more importantly, how you will be graded!).
Subscribe to:
Posts (Atom)
