Search This Blog

Tuesday, November 16, 2010

Week 11: ICEM

Integrated Concurrency and Energy Management (ICEM)

ICEM is a device driver architecture that enables simple, energy efficient wireless sensornet applications. Authors of the paper challenge the idea that sensornets cannot have standardized OS with simply API to manage the power and concurrency. The main idea is to deviate from the standard approach— hand-tuning the whole nesC code for power optimizations. ICEM offers set of tools that allows you to build a much shorter code and still manage power efficiency: Virtualized, Dedicated and Shared drivers. These tools leverage on the concurrency knowledge that application provides. The event-driven nature of the TinyOS uses split-phase operations that provide the valuable information i.e. when each operations ends it will inform that it ended using back-call, which is the main difference between asynchronous I/O that is used in threaded operating system. With such knowledge, ICEM drivers can efficiently turn and off underlying devices without wasting energy. However, there is another complication that might arise when some operations need to make series of atomic operations or require access to several peripherals at the same time. To handle these situations, ICEM creates the hardware lock abstraction in non-blocking (non threaded) environment using “Power Locks.” These locks are implemented by the shared drivers because they buffer “lock” requests, while virtualized drivers buffer “functional” requests. Thus, both drivers provide concurrency and energy management to their clients using them. Since dedicated drivers don't have such support, ICEM also provides them set of interfaces to allow building the system. They are part of “Lock” interface and include: StdControl, SplitControl and AsynStdControl (where Std is used for immediate access, Split for deferred access and AsyncStd for immediate hardware interrupts). As for the shared driver's Power Locks, ICEM provides the whole component library to implement them: arbiters, power managers and configurators.

The strength of the ICEM paper is definitely the depth of coverage of all the design components. Since complexity of the energy management is hidden from the application with the use of ICEM, it is important to understand how all of the drivers and components work behind ICEM. Thus, thorough explanation of why certain drivers were made and how they create abstractions is necessary. With such knowledge in mind, nesC developer will be able to understand why in some cases hand-tuned implementation is superior to ICEM implementation and in some cases equivalent. For example, flexibility of ICEM comes with the price of configuration requirements of some of its peripherals before arbiters can use them to make sure the drivers can interact with them. Since not all peripherals require configuration, a future consideration to ICEM could be to make configurations an option by providing a flag for it in its library components.

The other strong aspect of this paper is the scope of evaluations made to prove ICEM's efficiency in providing energy management. It is imperative for the sensornet developer to understand what ROM and RAM overhead library components are causing, which is very delicately done by measuring the current drawings at different power states and peripheral operations. With such experiment, authors identified the most expensive operation, which was obviously granting a request. By simply taking an integral of current drawing, energy consumption was identified. Using this measurement model, different implementation samples were made to compare ICEM against blocking threaded with different sample rate and hand tuned implementation. As predicted, ICEM scored within 1.6% of efficiency to the best hand tuned implementation of our example application. What makes this discovery powerful is the fact that 68 nesC lines of code were written instead of 400 lines, making ICEM definitely the strong candidate for application where 1.6% deviation from perfect is allowed. The only drawback of ICEM that has been left out as the open question in this paper is the deadlock handling. Failure to address this issue might cause system design (with peripherals sending a lot of parallel requests to acquire access to several pieces or making series of atomic operations) to fail. The question on how to handle deadlock situations will be asked in class.

Class discussions:

One of the first discussion was the ability of ICEM to deal with deadlock situations. Students suggested that static analysis will be the only feasible solution that will prevent deadlock to happen after all. One of the main arguments was the fact that nesC is built in a similar way. Thus, having deadlock prevention mechanism working in a similar fashion will not be ugly in terms of overall system design.

The next discussion questioned the completeness of the power lock queuing logic. Student asked whether power locks can be given priority or not. Since there is no direct control of prioritizing the locks, it was concluded that it will be the matter of creating work around using the ordering scheme inside the queue such as the round robin or first-come first-served approach.

The basic Lock Interface question was asked about the difference between StdControl and AsyncStdControl. In other words, what is the difference between them and which one is invoked in what kind of situations. Simple explanation was given by drawing parallel with the need of hardware interrupts. For example, if bits are received on the wire, hardware interrupt is needed to handle it immediately, so that the next set of bits will not override and loss will occur. Similarly, AsyncStdControl is used for hardware interrupts and StdControl is used for those devices that could be taken control immediately without startup latencies. After that, another interface question was asked about the role of the DefaultOwner, which is simply the default client that gets the power lock when no one else needs it. This way, ICEM controls the energy management by turning off the devices when DefaultOwner is holding the lock and turning on conversely.

The major drawback the whole class agreed upon is the need for configuration before any power lock can be granted to the client. One of the students argued that such approach proves to be inflexible in real life implementation. However, presenter argues that extensive evaluation showed that ICEM works great with the most popular platforms without having problems in configuring some motes (for example to switch to certain modes in their buses) before obtaining locks.

Overall, the class was pleased with the quality of the paper and the graph that shows the comparison of energy management results comparing ICEM to the perfect hand tuned implementation. The general impression was that the semester long discussion about optimizing idle listening was the complete waste of time since ICEM was able to score within 1.6% of the best implementation.

Friday, November 5, 2010

IP is Dead, Long Live IP for Wireless Sensor networks

Wireless Networks community has been observing many research efforts to devise protocols specific to application domains, with energy efficiency being the primer. There has been a growing consensus in the community, towards building a generalized WSN architecture, so as to combine these disjoint protocols under a common protocol layer, and address the WSN problems in broader networking sense and let the designers and implementers work towards a common goal of improving the system as a whole.

Since the nascent days of WSN, IPV6 was seen as a candidate to provide such architecture, but the majority of researchers denounced its use in WSN due to several concerns as lack of resources like memory, Energy, processing power and bandwidth. The large ip headers and payloads, end-to-end protocols were deemed un-necessary to WSN.

Since then IP, and WSN have evolved through a lot of research and increased practical deployment experience. It is worthwhile looking again towards IP protocol, to assess if it could provide sensor networks the much-coveted backbone architecture.

It is impractical to use IPV6 architecture in its current format due to obvious reasons of relatively huge header as well as assumptions about link connectivity. This paper propose an IPV6 based architecture for WSN, which would conform to the layering abstractions, services and interfaces of protocol stack, yet allow integration of existing duty cycled mac layer protocol concepts which have already been proven to be quite effective and efficient.

IPV6 architecture:

The architecture specifies WSN existing at the edge of IP networks, with border routers communicating with the external IP network.

The IPV6 network for WSN emulates the link layer, Network Layer and Transport layer abstraction of IPV6 architecture in wired networks. A combination of sample listening and localized schedule synchronization is used to emulate IP link.

Sampled listening uses short chirps as wakeup signal, and append destination address as well as schedule synchronization information to it, so as to avoid overhearing problem as well as synchronize a rendezvous time for sender and receiver with minimal chirp transmission. The scheduled time lets the receiver sleep, and then wakeup exactly at the point of data transfer. We’ll discuss about the problems with this approach in the next section.

Given the size of IP packets, there exist a layer 2.5 between Link layer and Network layer, which compress and fragments the data packets as necessary. The compression scheme works by eliding the obvious information as Version, Traffic class etc. as well as removing redundant information like Link Level Identifiers, as they could be derived form the link layer header as well. The 6LP_IPHC compression scheme uses 1 bit of compression state, and is able to compress 48byte UDP/IPV6 header up to 6 bytes.

Network layer duties include Neighbor discovery, Auto Configuration, Forwarding and Routing. The border routers propagate Routing Advertisements to announce optimal routes, as well as network parameters. The trickle algorithm is applied to assure minimal overhead by RA transmission. The increasing sequence numbers of RA’s make sure that only the most recent RA versions are applied by the nodes. Autoconf feature of IPV6 allows the unattended nodes to self configure identifier by appending the link layer identifier to Local link identifier, or else DHCP could be employed to let a centralized server allocate identifiers to the nodes.

Forwarding and routing are the other two features of network layer. Each intermediate node works as a default router, and maintains next hops for a partial number of neighbors, as well as a default route to border router to redirect rest of the packets. The border routers learn the default routes and reverse link them to analyze and generate optimal links to all the nodes. The destination path is injected in datagram’s header, so as to make sure it reaches the destination. Loops and inefficient links are identified by inserting expected hop count and eTX for next hop on the datagram and the receiving hop checks if the hop count is lesser than expected to detect loops, and if ETX is lesser than expected than it indicates increased path cost has not been updated.

We had thorough discussions over a lot of issues related to the paper:

Experimental Setup and Test-bed: The experimental deployment to evaluate protocol, doesn’t really prove a great deal as it considers very mild data rate if 1 packet per minute, which doesn’t really test the network congestion at all. The slow data rate perfectly explains the low duty cycle of 0.65%! The general consensus was that the tests seemed a bit hollow, and the protocol in its current state would struggle in harsher environment, with unpredictable data rates.

Congestion Control: The congestion control algorithm used in the protocol looks very inefficient as it waits for congestion to happen and then starts applying backpressure to decrease the data rate. This could lead to extensive link level retransmissions, which could be lost as well, as they would just add more to the congestion, and eventually the links would drop packets after exceeding retransmission count.

Rendezvous Time setup and Synchronization: Again, with low or no contention whatsoever it seems very easy to set up rendezvous time and transfer data but think about a huge network with many nodes contending to send data to a receiver! In this case with so many nodes undergoing sleep – wakeup schedule and transferring chirps it is inevitable that rendezvous times would collide, and it would be very tough to reach consensus, without avoiding extended wakeups and hurting overall energy efficiency.

Frame Pending bit and Starvation: The advantage with this approach is that the receiver doesn’t have to wait for timeout to decide that data is not pending, as the sender explicitly sets the frame pending bit. The issue of starvation was discussed in the class, and as it seems, it is impossible to avoid starvation in the current approach if some node decides to send forever by always setting the frame pending bit. This would lead to starvation for other motes as well as worse energy efficiency.

An issue was pointed out in the review for the approach of using IPV6 data packet structure for acks. The smaller acks could be comfortably sent between the chirps as well as data streams, but how would this extended Ack structure affect it is debatable.

Another interesting thought was, the possibility of WSN acting as a bridge between IP networks. Then, would it route the IP packets for other IP networks? This would severely affect the energy efficiency of WSN network.

The introduction of security in WSN courtesy IPV6 is definitely appreciable. Given the sensitivity of a lot of WSN deployments, security surely is an implicit requirement.

The discussion ended with probably the most basic yet debatable question:

Do we really need IPV6 with all its complexity and extra baggage (long headers) at all in WSN? If it is about connecting to outside network, why not let the border routers speak IP, and let the WSN speak its own language, in its efficient ways?

The answer was the same, when different hardware, software organizations agreed over common protocols and platform for Internet. The answer remains the same now as well! The extended future of WSN calls for a generalized architecture and the need for sensor nodes speak the same language (IP) as the rest of the IP world speaks. One interesting thought is that IPV6 architecture would give each sensor node an IP address, which makes it possible to access every “dust” around us!