Solution for Midterm

1. A skeptic would say that there are no new systems issues to be explored in pervasive computing, How would you counter that? You have to explain with concrete instances of new research problems engendered by pervasive computing and why they are yet unsolved and/or the state of their current exploration.

Solution: (Courtesy: Lenin Singaravelu)

New Challenges in Pervasive Computing

Pervasive is defined as "to become diffused through every part of" and in this case it can be modified as "computing becoming a part of our life.

From the definition, distributed computing is a subset of pervasive computing.

diffused => invisible (subset of pervasive computing)
"every part" => include mobile computing

a) There are solutions to many of the individual parts of the Pervasive computing problem. But to make them work in a pervasive computing setting is a totally different challenge.

eg 1 - There are solutions to huge data transfer problems, processing all that data and storing it in some orderly fashion.

But in a pervasive setting, with hundreds of sensors generating data and people/systems being interested in only some parts of the data(selective attention) or processing data at intermediate transfer points to manage bandwidth usage are new challenges. Stampede and echo address parts of the problem.

eg 2 - Failure and security have been closely investigated in traditional distributed systems and even in some kinds of Mobile systems.

But still there is very little progress in developing a secure adhoc

network routing protocol. There are some ways to improve security like

SPINS - (Adrian Perrig et al.) but they do not guarantee message

delivery. A malicious node may simply drop pkts.

eg 3 - Low power devices.

Low power devices and pervasive computing are at loggerheads in the

present scenario.

Low Power => turning of devices when not in use or low priority..
Pervasive => everywhere, all the time.

Proper design can lead to better solutions. There are elegant solutions like the optical communication system from UCB.

Scalability - How to manage 100's /1000's of devies per person.

b) Then there are new problems as such. For which solutions may exist but which can be bettered considerably.

eg 1 - Invisible Computing-

How to design really small, low power devices with excellent communication capabilities that does all the functions of a desktop and they must be cheap too.

eg-2 - Mobile and Wireless computing.

How to design systems that work as good as wired ones is the challenge. And most systems take care of low speed mobility at present. And mnay systems also assume that the systems are not "very mobile generally"
* How to make two cars on an expressway communicate.
* How to communicate in a rock concert where thousands of ppl
may be using similar devices and who are close to each other.
* Optimize power consumption.

eg 3 - Context Awareness
* How to collect context. Its a highly domain specific area.
* Integrate o/p's from various sensors.
* How to use context to improve system performance and user
satisfaction

eg-4 - QoS for data transfers.

eg 5 - Finding out user intent.

eg 6 - Decision making under uncertainity.

Once pervasive computing becomes a reality, there will be lots of
instances where the system will be forced to make decisions
independently and without all the data being available.

c) Problems in the future

There hasn't been a large scale deployment of a Pervasive system. Once such a system comes into existence, many more problems will crop up like
* Privacy
How can a system ensure privacy of user. Can the system itself be

unaware of the person's identity.
* and Legal Issues

2. Distinguish between location aware and location support systems. How do the design goals of sentient computing and cricket systems differ? What are the similarities and differences between the solution approaches of the two systems? Does the solution approach of one make it incompatible with the design goals of the other? Explain.

Solution: (Courtesy: Matt Wolenetz)

Location aware systems are systems that track the locations of objects. Location support systems are systems that allow objects to determine their location. At a high level, the distinction is whether the [tracking] environment or an object knows the object's location. Sentient computing (as described in the Addlesee, et al paper for IEEE August 2001) describes computations that "react to changes in the environment according to the user's preferences." More distinctively, sentient computations track the current state of the environment and "act as though its perceptions duplicate the user's." The concrete implementation of a sentient computing system called the BAT system enabled such actions by tracking large numbers of objects, including people. The BAT devices worn by people and attached to devices did not learn their locations, the external tracking system did. The Active Badge, BAT, and RADAR systems described in the aforementioned paper (and/or in "The Cricket Location-Support System" by Priyantha, et al for the August 2000 ACM MOBICOM) differ from the Cricket system's design goals in the following ways:

· User privacy is central to the Cricket system. The components of the Cricket system that are attached to a user (and to devices) are not required to transmit anything in order for the component's location to be determined. A Cricket listener listens for RF (and associated ultrasound) signals from statically placed beacons to determine the listener's proximity to those beacons. These listeners are the components attached to users/devices. With the user's approval, the user's listener can interact with external systems to integrate the derived location information in an application (such as the Floorplan). In contrast, the BAT system requires the devices attached to users to actively transmit signals. These signals are then used by statically placed listeners in the environment to determine the location of the source. Therefore, in the BAT system, the external system (not the user) has control over the location information of the user (and devices). This conflicts with the user privacy goal of the Cricket system.

· Decentralized administration is also central to the Cricket system. The beacons are entirely configurable by their owner (via an authenticated protocol) as to what information they broadcast. The listeners provide an API to attached computation nodes (printers, PDAs, laptops, ...) The use of that API is completely up to the program running in the node. In contrast, the BAT system described in the paper employed the use of a single centralized server that maintained a database of all device and user locations and performed various algorithms to filter location errors from the incoming location information.

· Network heterogeneity (maybe this would be better stated as "lack of reliance on any network") is a goal of the Cricket system. Since devices attached to listeners know their location, requiring them to communicate AT ALL seems to be an unnecessary and overly restrictive requirement. Of course, if an application running on such a node needed to communicate over some network, it is not precluded in doing this by the Cricket system. In contrast, the BAT design keeps location data in the centralized server. Any use of this location data in a "sentient computation" fashion in a location remote from the centralized server would involve communication of location data beyond the server. Basically, the utility of the BAT system for sentient computing on a human-level scale (say, a building) would require communication of the location data or data derived from the location data over some network(s) .

· Room-sized granularity is the goal of the Cricket system for resolving location. In clarification, they were able to reach a granularity of 4 x 4 feet (with a goal of 1 or 2 feet squared). The BAT system, as implemented, achieved a much better granularity of a few centimeters. Further, the BAT system, as described, utilized the "direction" of the BAT to estimate which way the user is facing. With this level of granularity and direction knowledge, smart posters, mice, virtual buttons, and augmented reality became feasible with the BAT system. It might be interesting to know if "room-sized" granularity were really the original goal of the Cricket system, or if this became an artifact of their implementation.

· Cost of less than $10 per location beacon and listener was another goal of the Cricket system. They achieved this with readily available, cheap parts involving no custom hardware. It was not readily apparent from the Sentient Computing paper what their cost goal was (or even if they had such a constraint.) However, the BAT system is difficult to deploy (according to the Cricket paper), requiring a matrix of sensors, a sophisticated central server, and the communication channels between the sensors and the server.

Beyond the similarities and differencies implied by the design goals discussion above, both the Cricket and BAT systems used RF and ultrasound to perform the location determination. The Cricket listeners attached to users and devices listen for RF and ultrasound signals from beacons. The location determination would proceed only if both signals from the same beacon were received (eliminating the possibility of tracking from a beacon in a different room), and the location would be the symbolic location transmitted by the associated beacon. In contrast, the BATs themselves acted somewhat like Cricket beacons. They cooperated in a scheduling algorithm coordinated by the central server and relayed via RF. Upon receipt of an appropriate RF signal, a BAT transmitted an ultrasound signal. Static receivers mounted in a matrix in the ceiling also heard that RF signal and determined the location of the BAT based on how much later the ultrasound signal was received.

At the application level, the BAT system appears to have been used in more ways than the Cricket system. This might simply be a product of centralized development and consequently documentation of BAT applications vs the independed usage of location information that probably occurred by the various users of Cricket technology. Notably, the BAT system enabled fine-granularity location directed widgets such as the virtual buttons and smart posters.

Utilizing the Cricket system as the basis of a sentient computing system would work without compromising Cricket design goals if enough of the cricket listener devices (via their attached nodes) were integrated securely with physical locality to allow applications to act as if they perceived the environment as a person would. Some higher level architecture that acknowledges the privacy/security requirements and the decentralized administration goals of Cricket, yet allows nodes attached to Cricket listeners to communicate, should be possible. However, using the BAT system (solution approach in the Sentient Computing Systems paper) as a model for implementing the Cricket goals would conflict primarily with the user privacy and decentralized administration goals of Cricket. It appears that Cricket was designed as a reaction to the lack of privacy and the requirement of a central server in the BAT system.

3. Compare the paper of Heidemann, et al., on wireless sensor networks, and Ad Hoc mobile wireless routing protocols. Discuss the similarities and differences in the assumptions and issues addressed by the two papers. Suggest ways to adapt Ad Hoc wireless routing protocols to Heidemann’s sensor network.

Solution: (Courtesy Agathe Battestini)

[1] refers to Heidemann’s paper

[2] refers to the Ad Hoc paper

Assumptions in [1]: If naming is application-dependent and defined with attribute-value pairs, then the cost of naming indirection (necessary when using IP addressing) is reduced; this leads to better performance on low bandwidth networks.

Performance is improved by using two methods: directed diffusion that aims at reinforcing one of the possible paths between sensors which optimizes the routing of data; and data aggregation (duplicates are avoided, application-specific filters aggregate data) which reduces the amount of data sent.

We may compare [1] techniques to methods used in Operating Systems. OS generally specify a strong boundary between the core of the OS: the kernel and the application. The main problem when we talk about resource optimization is that applications know what they need in terms of memory, CPU, … but resources are allocated and managed by the kernel that does not know about application’s needs. Some methods used in the purpose of improving resource management is to allow applications for defining their needs to the kernel, accessing directly low-level kernel functions, specializing kernel functions; or to make the kernel export some of its system capabilities (see CS6210 for details;).

I compare [1] with OS issues because in [1], they “break” the boundary between low-level network layers and applications. The goal is to manage the low-level layers (routing protocols) based on application’s needs to optimize communication performance.

The main issues are then routing and security. In such a sensor network, routing protocols have to ensure the discovery of the sensors that applications are interested in. This discovery is based on the matching of the sensors’ attribute-value pairs with those specified by the application.

The proposed directed diffusion protocol (not much detailed) is not likely to work with mobile sensors (because nodes prefer the reinforced paths, which may have become incorrect if their neighbors move), and may not be as efficient as other protocols. Besides, they observe that diffusion does not work well with asymmetric links.

That’s why [1]’s sensor network may benefit from the work presented in [2]. I maybe forgot to mention it, but [1] ‘s sensor network is an Ad Hoc wireless network (there is no set infrastructure, and each node acts as a router - the mandatory administration is the setting of the attribute-value pairs for all the sensors).

Basically, any of the protocols described in [2], after adaptation, may be used for the resource discovery required in [1].

The most appropriate may be the demand-driven protocols, such as TORA, DSR.

The first adaptation would consist of removing the unique IP naming and defining the identity of a node based on application level attributes (attribute-value pairs describing capabilities, location, …). The protocols defined in [2] would also have to implement higher-level features (for filtering, nested queries).

The discovery would remain the same: a request containing the description of the sought sensor is flooded throughout the network, via the node’s neighbors, until the request finds an appropriate sensor (maybe several sensors may correspond to the description). When the sources are found, the reply is sent back to the sink; the nodes belonging to the discovered path update their routing tables, and may also ensure the filtering features required by the source.

It is then up to the protocol to maintain the discovered path between the source(s) and the sink, in the cases where nodes are mobile and actually move. When the source send data to its subscribers, the nodes belonging the path filter, aggregate the data, and if required, forward it towards the sink.

Similarities: both papers deal with resource discovery, routing and optimization techniques for low-bandwidth ad hoc wireless networks.

Differences: [2] describes the existing routing protocols, whereas [1] relies on a “not well detailed” directed diffusion algorithm. In [1], the main concern is optimizing the discovery of sensors based on a low-level naming scheme, and the flow of data from the sources to the sinks. In [1], there is no unique identification of the nodes, whereas in [2] it seems to be required.

4. Publish/subscribe model found in systems such as Echo and Stampede are alternatives to RPC for structuring distributed computations. Are there some classes of applications for which Echo is better suited than Stampede, and vice versa? Explain your answer. What features of the two systems are complementary in nature and what are similar in nature?

Solution: (Courtesy: Sameer Adhikari)

The features of Echo and Stampede, which are similar, are as follows:

Publish/Subscribe Model: Both systems allow producers and consumers to interact by expressing interest in a shared abstraction, which incidentally is called a channel in both.

The producers put data on a channel and consumers get it. The producers don’t know who the consumers are and vice-versa.

Distributed Components: Both systems allow building application, which have distributed components. Taking care of the communication, and allowing the shared abstraction to be transparently distributed facilitates this.

Handling Heterogeneity: Both systems allow an application to consist of heterogeneous components. The systems take care of the data translations needed. The internal mechanisms are different but the result is the same.

Dynamic Join/Leave: Both components allow components to join/leave the application dynamically. This is a consequence of the publish/subscribe model. When a consumer wants to join, it subscribes to a channel, and it does unsubscribe to leave.

The features of Echo and Stampede, which are complementary, are as follows:

Synchronous/Asynchronous Behavior: The operations on the data abstraction are synchronous in Stampede. They are asynchronous in Echo. This is because Echo has an event notification mechanism, whereas Stampede has an event polling mechanism.

Temporal Indexing and Correlation: Stampede allows associating virtual timestamps with data put in channels. This allows the application to access items based on timestamps. It also allows application to correlate items in different channels based on the timestamps. Echo doesn’t have any such notion.

Real Time Synchrony: Stampede allows the application to synchronize virtual timestamps with real time. Echo doesn’t have this notion.

Type Extension and Reflection: Echo provides type extension by allowing transparent extension of data types being used, while preserving the validity of the code using the old data types. It allows reflection by allowing components to discover the contents of, and operate upon a data type without a priori knowledge of the data type. Stampede doesn’t allow this.

In light of the differences discussed, Stampede is better for applications that require stream handling. The ability for temporal indexing and correlation lends naturally to use in video and audio applications. Echo is better for application that require asynchronous event notification such as getting stock quotes, weather information, etc. when the data changes past a certain value.

5. Discuss the various wireless technology options that exist today. What are the pros and cons of each? In your opinion, which one has the most prospects of being successful? Justify qualitatively and quantitatively.

Solution: (Courtesy: Matt Wolenetz)

IEEE802.11(b) is a wireless physical and datalink layer designed to support data rates up to 11Mbps. It provides 2 basic modes of operation: infrastructure and ad-hoc. When in infrastructure mode, the network consists of at least one "access point" (base station and bridge to wired network)

and a set of wireless end stations. (Note that this describes BSS (Basic Service Set), and a different infrastructure configuration called ESS (Extended Service Set) would consist of a set of at least 2 BSSs to form a single subnetwork. Ad hoc mode/IBSS/peer-to-peer describes simply a set of wireless stations that communicate directly with each other. In ad hoc mode, no base station/AP/wired network connection is used. Infrastructure mode is commonly used in more persisting installations of 802.11 networks, whereas ad hoc mode is quick to setup and therefore good for more ephemeral networks. Since frequency hopping spread spectrum (FHSS) cannot support datarates above 2 Mbps per FCC bandwidth guidelines and the hopping overhead, 802.11b uses DSSS for 5.5 and 11Mbps data rates. DSSS (direct sequence spread spectrum) provides larger channel bandwidths and a predictable sequence. Further, more advanced coding techniques are employed in 802.11b to enable accurate decoding at faster data rates even under substantial noise and interference conditions. The 802.11 MAC protocol is similar to the 802.3 CSMA/CD protocol, except that collision detection is impossible in a 802.11 wireless LAN. Since collision detection in this domain requires concurrent transmission and listening for collision by a wireless station and such transmission "drowns out" the ability to listen, collision avoidance is used instead. In infrastructure mode, a wireless end station periodically monitors all 802.11 channels to determine if there is a different access point that would have a better channel (by monitoring error rates and signal strength) than the AP it is currently connected to. If so, the wireless end station reassociates with that other AP. There is an additional MAC mode called Point Coordination Function if an 802.11 AP is configured to use it. PCF provides time division multiplexed access to the media, is coordinated by the base station, and this mode is interleaved with DCF (CSMA/CA) mode to allow management of time-bounded and non-time-bounded data communication concurrently. Power management (sleeping with periodic wakeups) mode is available in addition to a "continuous aware mode." 802.11 also includes WEP encrypted communication, although the 40/64 bit version appears to have been compromised (there is a 128 bit version also.)

Bluetooth is a wireless technology aimed at enabling ad hoc personal area networks (shorter range than LANs) that integrate portable devices. Major design goals were to be a low cost, low power cable replacement with utility worldwide and broad support by companies. It achieves datarates of approximately 700 Kbps - enough for a walkie talkie, remote mouse, etc... Whereas 802.11 uses 14 overlapping channels of 22MHz each, Bluetooth uses 79 channels of 1MHz each with FH-CDMA to attempt avoidance of interference. Bluetooth's MAC protocol associates channels with piconets and Bluetooth communicators are either ephemerally a master or slaves of piconets. Bluetooth also provides for interleaved asynchronous communication and synchronous communication (synchronous communication is for realtime traffic such as voice or low quality video.) Bluetooth connection establishment is a bit tricky and results in a worst case delay of 2 sleep times (the process is drive by the phase of clocks). Bluetooth includes some forward error correction to help minimize retransmissions due to interference/errors. Power consumption by bluetooth radios is also minimized by only scanning about 1% of the idle time. Finally, Bluetooth includes a security model based on a 128 bit link key hidden in the hardware. User directed association of two bluetooth devices is required for the 128 bit keys to be the same on both devices.

GPRS (General Packet Radio Service) is a packet data service designed to support data sources that are bursty in nature while sharing resources dynamically with other GSM services. Data rates available in GPRS are approximately 144 Kbps "IF hugging a receiver at 4AM and there is no wind." Actual rates are an order of magnitude less. Much of the GPRS specification involves structuring it such that it coexists with older GSM service infrastructures. GPRS is capable of slotted/multi-channel concurrent communication (it has the ability to do up to 8 simultaneous channel xmission.) It incorporates a "capacity on demand" functionality that allows flexible partitioning of resources. The GPRS paper indicates that GPRS is not suitable for large amounts of small packet traffic (excessive signalling wastes channels under those conditions.)

IrDA (Infrared Data Association) is an industry backed communication protocol for using infrared wireless communication in an interoperable fashion. Primarily targeted at removing the requirement of using "wires" to connect peripherals, IrDA provides a low cost, short range wireless technology. Although originally targetted to support datarates up to 115 Kbps, it currently supports at least 4 Mbps (16Mbps is mentioned in the paper.) Besides the standardization of the lowlevel physical signalling, IrDA provides protocols to support application interoperability. It has gone through specification revisions to increase the datarate and provide a more elegant and user-intuitive connection model, while maintaining backwards compatibility. Unfortunately, it appears (subjectively) to suffer from being relegated to a niche (peripherals, PDAs, and various handheld devices).

FSO (Free Space Optics) as used in the Smart Dust paper represents an interesting attempt at showing the feasibility of low power communication. Although Smart Dust is in its infancy, the continuing development of MEMS technology may prove it to be a practical reality in the future. One key result of the research into this instantiation of FSO for low power communication is the fact that multihop communication may be cheaper with respect to power than a direct connection due to the tradeoff in bitrate, distance, and energy per bit.

Ultrasound and RF wireless combination technologies such as BAT and Cricket are highly specialized currently. I see them more as interesting usages of older technology, not as core wireless technologies

themselves. I have presented the characteristics of these two particular systems in my earlier answers.

In my opinion, 802.11(b) and subsequently similar technogolies probably have the most prospects of being successful in the wireless LAN market due to their already heavy market presence and their ability to achieve high datarates. Bluetooth is more directed towards wireless personal area networks, and currently interferes with 802.11 communications. Although IrDA currently achieves relatively fast datarates, it uses a LOS form of data transmission that precludes it from easy, intuitive integration as a LAN technology. Maybe I should qualify my answers a bit. "Having the most prospects of being successful" is relative to the intended use. GPRS currently enjoys utility due to shortages in other widely available wireless networking technologies outside of LAN environments. It will probably continue its success without competition *in that environment* from the other technologies listed above. Potentially, Smart Dust could become a huge success, but that is dependent upon large advances in MEMS technology, among other things. Therefore, I chose an already widespread wireless technology with which I myself foresee interacting with in the future on a regular basis. If ubiquitous sensors truly become a reality, then the current Bluetooth technology might be best suited for managing the large amount of resulting short-range networks. But I think for users to have meaningful, high fidelity interactions with such ubiquitous sensors, Bluetooth would need better datarates than it currently has. Such datarates are available already or will be soon with 802.11 technology.

Of course, I could say that T-ray based technologies are going to win the day, but they don't really exist today beyond Harmonix and Endwave being "close."