SensorNet Paper Reviews by lah1
From Ece
- Return to the paper reading schedule or the Sensor Networks homepage.
Overview of Sensor Networks
D. Culler, D. Estrin, and M. Srivastava, Overview of Sensor Networks, IEEE Computer, 37(8), August 2004
Presented by Lee Hathcock
Powerpoint presentation: Slides
Notes on presentation: Notes
More detailed slides: Detailed
The Emergence of Networking Abstractions and Techniques in TinyOS
P. Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer and D. Culler, The Emergence of Networking Abstractions and Techniques in TinyOS, USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI). 2004.
Intro: This paper covers the advent of various abstractions of the networking layer that have occurred through extended use of TinyOS. Consider this paper a case study. It has evolved through the use of hardware and software, and is very much dependent on the context in which the HW/SW is used, but some common generalizations have definitely occurred.
Problem / Observation: The authors have observed that over time, four major networking abstractions or classifications of these abstractions have arisen. These are: general, specialized, in-flux, and absent.
Various intro material is presented to get the reader up to speed, and does not necessarily pertain to the real goal of the paper. It describes the history of various hardware implementations of TinyOS, as well as a decent explanation of the overall operation of TinyOS. Some example applications are given, as well as some of the abstractions that might arise in those applications. They also describe the various network and radio stack implementations for both single and multi-hop communication, and describe both flooding and epidemic message spreading, and note the advent of send queues, which means that processes are taking some time before sending messages. Some mentionof both power management by sleeping and time management is made, as well.
Technical: General abstractions are those that TinyOS has both the mechanism and policy to support, and they are widely used. A good example is the AM radio stack, as well as the Send and Intercept interfaces in TinyOS. Specialized abstractions are typically done in a hardware dependent manner, and while possible to abstract away generally, doing so has typically caused problems. Time synchronization is a good example. In-flux are those that are used, but they haven't been codified to an accepted norm. Epidemic propagation is one, as well as the radio MAC. Absent abstractions are those that are present in literature, but not really used, such as distributed clusters and incoming queues.
Common tasks that arise are communication scheduling, which has to deal with sleeping and waking up at the right time to save power, and snooping, which listens and intercepts packets as they fly by, using that information seen. These are mutually exclusive and require careful balancing. Cross layer control deals with using lower level information at the higher level to facilitate efficiency, such as timestamping. Also, there is a mention of a prevalence to use static resource allocation, as it avoids some of the interactivity pitfalls that tend to occur with dynamic systems.
Impressions: Overall, a well presented paper, interesting in that it shows what actual users and researchers of WSNs are using and what they aren't.
Just-In-Time Sensor Networks
G. Yee, B. Shucker, J. Dunn, A Sheth, R Han, "Just-In-Time Sensor Networks", IEEE Workshop on Embedded Networked Sensors (EmNets) 2006, pp. 6-10.
Intro: The proposal of this paper is that, instead of more statically allocated sensor networks, nodes are deployed at a particular time, and they rapidly form their own network, ad-hoc style, as well as dynamically adjust to new nodes being placed in the system at a later time. They must be cheap, and be able to be deployed within some target of interest's radius.
Problem / Observations: While not currently possible, current fixed-network outdoor sensor networks are not going to be the way of the future when sensor nodes get rather cheap.
Technical: These nodes must be deployed, and first mentioned is incremental searching, where waves of nodes are spread, kind of as a first run, then another wave targeted at areas of interest, and then a last wave for detailed information in the areas of interest. The second application mentioned is target tracking, but they discount using video for this, due to power constraints. Redundancy is proposed not by using the current nodes and having them adjust their behavior, but instead just launching new nodes to fill in the gaps in coverage that occur due to inconsistent / non-existant node linkages. Also proposed are virtual sinks to take care of hot spots that arise, by sending more short-lived nodes in to help process the data. Bulk data transfers, for things like code updates, could eventually be handled by a "data ferry", which would be sent to the epicenter of the area needing an update, and broadcast said update. This is a bit expensive for now.
Also presented are various algorithms for calculating the cost of redundancy, speed, power, and delay. They also present a method for spreading the nodes (i.e. a cannon), and specify that they would like for the cannon to be programmable, rapidly respond, do the best it can for precision, activate nodes just before launch, and be able to change types of nodes by itself (multiple ammo for the win!).
Impressions: A grand vision, but definitely a more brute force way of doing things. They are definitely relying on future technology and eventual cheapness of nodes to make this vision work. This seems like more of a wish list than actual implementation.
A Dynamic Operating System for Sensor Nodes
C.-C. Han, R.K. Rengaswamy, R. Shea, E. Kohler and M. Srivastava. A Dynamic Operating System for Sensor Networks, International Conference on Mobile Systems, Applications, and Services (MobiSys), 2005.
Intro: The paper presents a different framework / OS as an alternative to the oft-used TinyOS. According to the authors, this OS is designed to be dynamic, and consists of a kernel and dynamically loaded modules for its implementation. This makes it cheaper to update functionality as an entire system image is not needed to be sent to nodes to change their functionality.
Problem / Observation: Current OS for WSNs are not dynamic enough, and consume too much power upon code updates. Also, the lack of dynamic memory allocation forces more work on the programmer, and does not allow for as much abstraction away from hardware as desired.
Technical: Mentions of TinyOS and Mate operation are made as a contrast to this new "SOS" operating system. A few differences, some of which arose in the previous TinyOS paper reviewed, is that dynamic environments cause interaction problems. Some of these are covered by the authors, and they give various failure modes that can be used to recover, since robustness is key. They use priority queues instead of FIFOs, which helps maintain the functionality of time-critical applications. As mentioned earlier, the use of dynamic memory as well as garbage collection enables better usage of available resources, as well as allowing higher levels of abstraction for the programmer.
Another nice feature is that they use plain C code, and not nesC. Happy days!
Many, many speed and efficiency justifications are performed by the authors, to test this OS' viability vs. TinyOS and Mate. As it turns out, many of the things it does fall between TinyOS and Mate, and overall, it consumes SLIGHTLY more energy than those for overall usage, including things like CPU usage, code update efficiency, transmission of data, and so forth. However, in the long run, the differences in power usage are minimal, and the authors contend that it makes the slight (and insignificant) cost worth it.
Impressions: Surprisingly well written, and excellent justification of their OS vs. others. They definitely covered their bases and substantiated their claims, in my opinion. Deeper digging might prove otherwise, but looks good overall.
MANTIS OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms
S. Bhatti, J. Carlson, H. Dai, J. Deng, J. Rose, A. Sheth, B. Shucker, C. Gruenwald, A. Torgerson, R. Han, "MANTIS OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms, " ACM/Kluwer Mobile Networks & Applications (MONET), Special Issue on Wireless Sensor Networks, vol. 10, no. 4, August 2005
Intro: The developers of this OS have created MANTIS to facilitate the use of multiple threads for WSNs. This allows the programmer to not worry about blocking or being blocked on processes, and only worry with shared memory (as it is not protected, just like TinyOS). This is coded in C (or a slight derivative), and fits in less than 500 bytes.
Problem / Observation: The authors contend that a threaded approach is better than the current event-driven approach.
Technical: While not as efficient, threading ensures all processes are able to run. This avoids buffer overflow problems that can occur on blocking of a particular process. Power management in MANTIS is done similarly to other sleep functions in other OSs, in that if all threads are I/O blocked, the node can go to sleep. They liken the command to the UNIX sleep() command.
Apparently, they have a simulation tool that can be deployed that is similar to WINE in execution, enabling x86 machines to act like nodes in a MANTIS network. However, they do not have wireless link simulation, which would seem to be an issue. Dynamic reprogramming is also supported, either by direct link or by remote login and updating. Everything from sampling rate to entire threads can be updated, but the OS cannot be updated, as the code update mechanism lives there. They also provide functionality to remote login to a particular node.
Descriptions of hardware are there, but mostly are unimportant. They are roughly comparable to mica2.
Future work they cite include more on power and scheduling sleep / wakeup, testing the reliability of code updates, adding security to those dynamic updates, and simulating the wireless channnel in their testbed.
Impressions: Overall, seems to be a valid approach. I wonder if these guys are UNIX programmers, their definitely taking that kind of tack with this. They eventually envision a hybrid thread / event approach, as event driven functionality is more efficent, but the thread based is more powerful.
MACAW: A Media Access Protocol for Wireless LAN's
V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, MACAW: A Media Access Protocol for Wireless LANs , SIGCOMM Symposium on Communications Architectures and Protocols (SIGCOMM'94), September 1994.
Intro: As an early paper in wireless networks, this paper covers the use of indoor wireless LANs, and ways to resolve bandwidth / contention issues in these networks.
Problem / Observations: One of the earlier algorithms for approaching wireless networking was MACA. While somewhat effective, for use in wireless LANs it proves to be not as effective. Still, MACAW is based very heavily on MACA, with some important changes algorithmically and some key observations.
1) Contention is relevant at the receiver, not the sender. 2) Congestion is location dependent. 3) Learning about congestion must be a shared / distributed process. 4) Synchronization of contention periods is important.
Technical: The first point leads to the discussion of CSMA as useless for this application, and they thusly propose an RTS-CTS-DATA-ACK approach for sending data. This avoids both the infamous "hidden terminal" problem, as well as the "exposed terminal" problem, effectively placing contention on the receiver as desired.
Modifications were also made to the backoff algorithm, scaling up more slowly and resetting linearly (as opposed to a complete reset of the backoff timer).
Allocations of bandwidth are done by streams of data, as opposed to per station, since a station can have multiple streams, and splitting bandwidth between the multiple processes may not be "fair".
As for learning about congestion, stations basically share their backoff timers, which of course helps even contention, but causes problems described later.
Synchronization involves the use of an RRTS packet to request sends of an RTS packet, so a station / stream can actually contend for resources (since the backoff algorithm can cause it to miss contention windows, especially since it may not know the length of the data being sent, and when the transmission will end).
Problems arise with the backoff algorithm in noisy environments, as it causes the backoff times for all nodes to skew high, given that they all share the timer every time, and since it scales up faster than it does down.
Future work (which has probably already been done by now) includes various forms of ACKs, including piggybacked ACKs and NACKs, various carrier-sense mechanisms, more look at synchronizing, and determining what is "fair" in a wireless LAN. It should also be noted that they did not try to tackle multicast at this time.
Impressions: A well written paper, it's quite obvious that this one has posed several issues that have arisen and been solved, or that are still prevalent even today.
Medium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks
W. Ye, J. Heidemann and D. Estrin, Medium Access Control with Coordinated, Adaptive Sleeping for Wireless Sensor Networks, IEEE/ACM Transactions on Networking, June 2004.
Intro: Current MAC protocols chew through more energy than desired for wireless sensor networks. Hence, the proposed MAC (S-MAC) which coordinates sleeping and wakeups to conserve energy.
Problem / Observations: There are several sources of major power draw in wireless sensor networks. These are: collision, overhearing, control packet overhead, and idle listening. The S-MAC protocol tries to resolve all of these issues.
Technical: S-MAC achieves the above by trading off some performance in the area of fairness and latency. But since there is so much idle time in WSNs, it is better to lose some responsiveness to gain longevity in the system. They list a couple of styles of MACs, CDMA and TDMA. CDMA is a contention-based protocol, and is most similar to this, as well as 802.11. TDMA is used in Bluetooth, and while able to conserve more power, it is not inherently as scalable as CDMA schemes.
S-MAC synchronizes nodes. It does this via a SYNC packet, and typically obtains a schedule for wakeup / sleep from neighboring nodes, if it can hear them. SYNC packets are not sent overly often, as they do have some overhead associated. They manage to keep these somewhat minimal by allowing longer windows for active time, and can thusly tolerate a little more skew than other types of systems. Obviously, there is some inefficiency there, as well, but overall helps energy consumption.
S-MAC also attempts to avoid collisions. It uses both virtual and physical carrier sense, and the RTS/CTS scheme used should look very familiar when compared to MACAW earlier.
In addition, adaptive listening is added, which allows for nodes to break their schedules if they overhear data from a neighbor that they need to pass on. So after the neighbor's data is sent, they wake up (off-schedule) and try to immediately forward more data. This helps a bit with latency or high priority data.
They also allow nodes to go to sleep during / after hearing RTS/CTS packets (and they're not the target). There are some issues with this, and it's not easy to decide which nodes should go to sleep, but they've apparently got it down.
Message fragmentation is also used, and is similar to 802.11 in its implementation. However, only one RTS/CTS is used, and then fragments are data are sent, and an ACK is received before a new fragment is sent. This avoids the overhead of RTS/CTS packets for every data fragment.
Impressions: They give a lot of testing vs. an "802.11-like" protocol, and it tends to confirm their statements, in that latency is increased, but power consumption decreases. In WSNs, we can live with that. S-MAC is also apparently open source, which is always a positive when trying to get a protocol adopted for mainstream use.
Ultra-Low Duty Cycle MAC with Scheduled Channel Polling
W. Ye, F. Silva, and J. Heidemann, Ultra-Low Duty Cycle MAC with Scheduled Channel Polling, ACM Conference on Embedded Networked Sensor Systems (SenSys'06), November 2006.
Intro: The advent of low-power listening protocols has made it cheaper in terms of energy to contend for resources. However, the authors claim this should still be tied to scheduled access to the radio to minimize energy usage.
Problem / Observation: Low-power listening can require long preamble transmissions to awaken all nodes to receive a message, causing an increase in power usage. Scheduling is subject to long latency times, and overhead for synchronization. The idea is to use scheduled low-power listening to shorten the length of preamble wakeup transmissions, which allows for much lower energy usage (because of the low duty cycle).
Technical: Key to this working is syncronizing all the nodes. So SYNC packets, much like S-MAC, must be sent to keep neighboring nodes coordinated. So when a sender wants to send information, it will send a transmit tone, and this should be scheduled in that neighboring nodes will have awakened to listen for a short length of time in the channel. Hearing the node, they can then fully awaken to receive the data. Obviously, the sender has to do some carrier-sense to make sure it's not interfering with another node's transmissions. The contention for the channel is done both before the transmit tone is sent, and also before the data is sent. Splitting the contention phase decreases the chance of collision.
Handling "bursty" traffic is handled by increasing the periodic LPL of certain nodes, which increases the throughput of the network.
They have also extended S-MAC, in that overhearing avoidance can be done without RTS/CTS mechanisms, and requires inspection of packet headers for the destination.
Synchronization does not have to take place very often, somewhere in the neighborhood of 10 minutes to an hour. It can piggyback synchronization messages on data packets, or solo sends of the sync data.
Impressions: Much justification, like in the previous paper on S-MAC, is provided by the authors. Theoretical analysis as well as actual implemention has been done. They claim a energy improvement of 2x - 2.5x, which is rather impressive, and they claim that it handles "bursty" or unexpected traffic more readily than LPL alone. All three of these papers seem to be a natural extension of each other, despite the age of the first paper. It's interesting to see what parts of the MACAW paper actually did get adopted.
Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks
P. Levis, N. Patel, D. Culler, and S. Shenker, "Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks," NSDI, 2004.
Powerpoint presentation: Slides
Notes on presentation: Notes
The Tenet Architecture for Tiered Sensor Networks
O. Gnawali, B. Greenstein, K.-Y. Jang, A. Joki, J. Paek, M. Vieira, D. Estrin, R. Govindan, and E. Kohler, The TENET Architecture for Tiered Sensor Networks, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2006.
Intro: The Tenet architecture brings a tiered (hierarchical) approach to sensor networks.
Problem: Usually, motes are rather constrained as far as power. Therefore, "master" nodes may be needed to issue tasks and implement application-level functionlity, and leave only responding to the smaller motes.
Technical: The Tenet "principle" they speak of involves a hierarchical approach, where all data fusion / dissemination is done by more capable master nodes, and responses to assigned tasks are handled by less capable, more densely scattered motes.
Part of their approach is that spatially, we usually don't have much data. Temporally, we usually have MORE than enough data, and so they try to get rid of all the unnecessary data
So for the system, they have a few design principles:
1) All communication to a mote takes the form of a task. Motes only communicate with masters. 2) Any master should be able to communicate with another master or mote, as long as there is some physical layer connection. A mote has to communicate with ONE master. 3) Motes should have some set of generic functionality with which to perform tasks. 4) The system should be both robust and manageable.
The key is the nature of tasks. These are essentially composed of "tasklets", which are small pieces of functionality that are present on motes. In some regards, they resemble a virtual machine, or perhaps an API of common functions. The tasklets have as much functionality as possible without impacting reusability. If a task is not present, it can be installed, although the mechanism for this is not specified.
As far as networking goes, Tenet utilizes tiered routing, and has a large description of the way that their system works. What generally happens is that data from a mote is sent to the nearest master, and then is routed from master to master. Task dissemination is achieved by a flooding protocol called TRD.
Impressions: Much evaluation is made of Tenet, but one thing jumps out at me, which is that this is more of a simplification of development and not so much one that makes things more "efficient", although one could certainly argue that making development easier already makes things more efficient. This approach would require more resources than some other schemes, but also purports to avoid some of the pitfalls present when the network consists completely of less capable nodes.
SATIRE: A Software Architecture for Smart AtTIRE
R. Ganti, P. Jayachandran, T.F. Abdelzaher, and J.A. Stankovic, SATIRE: A Software Architecture for Smart AtTIRE, International Conference on Mobile Systems, Applications, and Services (MobiSys), June 2006.
Intro: Motes have gotten smaller and cheaper, and as such can be used as personal monitoring devices, which might be applicable to things such as patient monitoring and the like. These could track movement, and be embedded in clothing or whatnot. This is achieved through the use of GPS and 2-axis accelerometers.
Problem: Implementing such a system may have several issues, not the least of which is storage for data, power management, synchronization, and security.
Technical: Much like the previous paper, SATIRE is envisioned as a bit of a hierarchical system, in which motes will eventually communicate with a PC. But several problem occur, and the authors try to solve most of them.
First, sampling someone walking requires a decent amount of resources. They use this as the baseline for sampling frequency on the accelerometers, and decide on a frequency of 25 Hz, roughly double the sampling frequency to not lose the data from the accelerometer. They save space by cutting the precision of the accelerometer, and by stopping measurements when no movement occurs via a "stillness" filter.
For uploading data, tweaks must be made to limit the amount of data stored, and they eventually decide to use a beaconing scheme, free of any user intervention.
They also use beacons for realigning data on motes, but sample at a much lower frequency.
For power management, we can obviously put nodes to sleep, and since most people won't be wearing the jacket all the time, then it won't be moving. However, synchronization packets must still float around every once in a while to keep the clocks sync'ed, especially since they might miss windows, and if one doesn't hear data, it stays awake until it does and synchronizes again. GPS can be simply turned off or not get a "fix" when not moving.
There are also some issues in determining actions performed, but typically these are not overly non-trivial to ascertain, given that there are very clear regions of different activities, as seen in Fig. 7.
Impressions: Some evaluation is given, and it does not appear much divergence from expected norms occurs. This is a really interesting area, and what do you want to bet that Nintendo and third party developers are having to read these research papers on gesture recognition that are cited by these authors?
TSAR: A Two Tier Sensor Storage Architecture Using Interval Skip Graphs
P. Desnoyers, D. Ganesan and P. Shenoy, TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2005.
Intro: Storage in sensor networks can be expensive, especially when trying to search through previously recorded data. This paper presents a method for storing data, as well as indexing it efficiently.
Problem: While storing data locally at nodes is good, and can keep communication overhead down, we also have to access that data, and as such current methods for searching through this data are very inefficient.
Technical: TSAR proposes to make more of a hierarchical approach to storing data. While detailed sensor data is still stored locally at nodes, there is a second, more powerful layer of nodes (or proxies, as referred to here) which take metadata that represents the data, and stores it and an index at the proxy.
They use an extended version of skip graphs, which from what I understand, are a sort of hierarchical search method, in which nodes are classified by key values, and the key value is accessed, along with all the nodes within it, to try to find the target node, and if one happens to know about it, the query shifts to that node, and the process repeats until the node and correct data is found. So this seems to save the sizable overhead involved with searching EVERY node. But for this paper, they don't just store single values, they store intervals, hence the name "interval skip graph". I don't completely understand the idea behind skip graphs, but it sounds almost just like the "bucket" search, in which data values are stored via some key (like first letter, or type), and added into a linked list for that value. Then THOSE values are searched through, making the search occur much more quickly on average. In fact, after closer inspection, I'm sure that much the same principles are being applied.
Impressions: This seems to be an interesting idea, and gets at trying to keep things a little more easy to manage, since more capable nodes can store more information about the network and data present than the sensor nodes themselves. And by storing and indexing this way, it almost makes for a hash table-esque operation. Not quite, but some of the principles are there. Other tree structures could be used, but they went with this for robustness reasons. This primarily addresses issues that may occur in non-homogeneous networks, in which many different functions occur. A flat hierarchy will likely never have this problems, and as such, this should be looked at for any hierarchical deployment.
The Stream Virtual Machine
The stream virtual machine. Labonte, F.; Mattson, P.; Thies, W.; Buck, I.; Kozyrakis, C.; Horowitz, M.; Parallel Architecture and Compilation Techniques, 2004. PACT 2004. Proceedings. 13th International Conference on 29 Sept.-3 Oct. 2004 Page(s):267 - 277
Powerpoint presentation: Slides
Notes on presentation: Notes
Vineyard Computing: Sensor Networks in Agricultural Production
J. Burrell, T. Brooke, and R. Beckwith, Vineyard Computing: Sensor Networks in Agricultural Production, IEEE Pervasive Computing, pp. 38-45, 2004.
This is a description of a system that could be or was tested in a vineyard. A fair amount of polling was done with the managers and such, and they came to the conclusion that any deployment, since used by multiple users all with different needs, would need multiple presentations of the data available. They do this by "human touchpoints", effectively terminals that contain data necessary for someone to take advantage of. The managers would obviously want different data than the workers, who probably just need a station to record work times or the task done. One of the ways for that is possibly RF tags for the tools they use.
For the most part, the system would use the same systems we're rather familiar with at this point, an ad-hoc style network linked via wireless / RF. They also describe a method to distribute data to keep costs down, such as using the dogs that are around as "data mules".
Wireless Mobile Ad-hoc Sensor Networks for Very Large Scale Cattle Monitoring
M. Radenkovic and B. Wietrzyk, "Wireless Mobile Ad-hoc Sensor Networks for Very Large Scale Cattle Monitoring", Proc. of Sixth Int'l Workshop on Applications and Services in Wireless Networks (ASWN'06), Berlin, Germany, 2006, pp. 47-58
This is a system put into use to monitor cattle in England. Given the mad cow outbreaks, it can be very important and useful to monitor the behavior of cattle to try to determine whether they are infected. In addition, by using a ad-hoc style network, it can be determined what other cows have been in proximity, so that they can be monitored as well.
Several different things can be monitored by various sensors, and for the most part, just as the above, they use RFID tags. This limits the amount of available data, however. Also of prime importance is power, in which communications are limited should a particular node fall below a certain energy threshold. At this point, interactivity goes down substantially, and latency increases since it is not proactively caching data for future use.
The primary method of distribution is DHT, and they optimize for keeping links active for reliability purposes. Also, the system has to be tamper-proof, since dishonest farmers and cattlemen might hack the system to hide the fact that their cows may be infected.
Monitoring Volcanic Eruptions with a Wireless Sensor Network
Geoff Werner-Allen, Jeff Johnson, Mario Ruiz, Jonathan Lees, and Matt Welsh, Monitoring Volcanic Eruptions with a Wireless Sensor Network, EWSN'05.
This is a system that is in place to monitor volcanic eruptions. Using our favorite Mica2 motes and utilizing GPS and such, they have set up a system to obtain relevant data. Of primary importance is how often to sample, as too much monitoring generates far too much data, and drains far too much power. They have the Mica2, infrasound nodes to pick up vibrations, nodes to aggregate the data, and a GPS node to timestamp things accurately. They also do time regression analysis for the data that comes in.
One of the things that becomes very clear is that we don't want to monitor things if nothing is happening. In this case, they have a detector algorithm that determines whether a volcanic event is happening or not. If it is, things sample much more quickly, as you would expect. This keeps uninteresting data to a minimum, and also helps in that power usage decreases.
Design and Deployment of Industrial Sensor Networks: Experiences from a Semiconductor Plant and the North Sea
L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, M. Flanigan, N. Kushalnagar, L. Nachman, and M. Yarvis, Design and Deployment of Industrial Sensor Networks: Experiences from a Semiconductor Plant and the North Sea, ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2005.
This paper, once again, covered two deployments of wireless sensor networks. The monitoring performed this time was of a preventive nature, in that future problems will be detected before they become catastrophic. They use various sensors to monitor vibrations, oils, infrared, and ultrasonics, all to try to diagnose future problems.
There were several deployments made, and much is made of dependability, just as in the previous cases. They actually didn't need as many nodes for coverage as previously anticipated, but there are still issues with interference and the like. In any case, not only should the system be robust, but it should also be low power, easy to maintain, easy to integrate, and secure. Ah, who cares about security, anyway?
Two node platforms were used, the Mica2 motes and the Intel Mote. Turns out that the Intel draws 1/10 the power of its rival when active, but over long sleep periods, the Mica2 catches up.
It is quite apparent that preventive maintenance is a very important field in sensor networks, and is one of the primary motivators in the field. One issue that remains, of course, is cost, but when you can prevent catastrophic failures, it may be worth it, and likely these systems will only get cheaper with time.
VigilNet: An Integrated Sensor Network System for Energy-Efficient Surveillance
T. He, et al. VigilNet: An Integrated Sensor Network System for Energy-Efficient Surveillance. ACM Transactions on Sensor Networks, 2(1): 1-38, February 2006.
This is a monitoring system for movement and such. They had some requirements of said system, which include longevity (duh), adjustable sensitivity, stealthiness of the devices and transmissions, and of course, actually being EFFECTIVE (imagine that...).
In any case, our good ol' Mica2 motes are back in business, and a deployment in a field is made. The primary issue here is detecting the movement, and they use magnetic sensors for this purpose, as vehicles and such moving generate a magnetic field.
Part of their localization of movement is done via GPS. Of course, we have already ascertained that GPS is a power hungry little bugger, so that may not be the best solution. It works for now, though, until more research is done by calculating positions by relation to other known nodes.
The system can also try to estimate velocity, which one would thing could be useful in determining the type of object detected.
Also important is the in-network aggregation of data to limit size of transmissions, and this has an effect on the overall performance of the system. False negatives can occur, latency if no false negatives, and there is more overhead.
Some issues encountered include reliability in the Mica2 platform, reducing false alarms, reducing race conditions, issues with assymetry in the network (due to radio variations and the like), software calibration, and other issues like clock drift which make synchronization an issue.
Interesting read, not quite as long as it looks initially, despite the 34 pages.
Chord: A Scalable Peertopeer Lookup Service for Internet Applications
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. Technical Report TR-819, MIT, March 2001.
Intro - We would like to be able to store data in a sensor network in a distributed fashion, as too much memory would be consumed per-node otherwise.
Problem - Chord proposes a system that distributes data throughout a sensor network, mapping keys as evenly as possible throughout said network.
Technical - Chord puports to handle many things in distributed data storage, which are as follows:
1) Load balancing - keeps keys fairly evenly distributed throughout the network. 2) Decentralization - no central nodes are needed, all effectively peer-to-peer. 3) Scalable - scales by O(log n). 4) Availability - adjusts to node failures and joins properly. 5) Flexibility - keys can be whatever we want.
This is great and all, and there are several applications where this type of data storage could come in handy. But let's look at some implementation level details.
First of all, Chord uses consistent hashing, as opposed to random hashing, to keep things more distributed. Random hashing tends to bunch things up every once in a while (see the birthday example).
To keep things adequately scalable, a bit more state information is maintained so that the system remains correct should nodes be added or drop out. This information is contained in a "finger" table.
To keep joins up to date, it is necessary to keep track of successors properly, and that successor is responsible for a given key.
Also added is a stabilization scheme to maintain correctness upon concurrent joins to the network.
Recovering from failures is not an issue, given that information is maintained by successors. So this means that data duplication is used to some degree, at least from what I understand.
Impressions: Coming off a detailed reading of GHT, this is using a quite similar idea. It seems sound, and more information is given algorithmically than GHT. I do wonder in their scheme if it can recover well from multiple node failures. They say it does, but one has to think that something WILL be lost eventually. Also, the periods in which it is updating the tables could be... problematic. I would think incorrect data or somesuch would be returned. Good paper, overall.
The Sensor Network as a Database
R. Govindan, J. M. Hellerstein, W. Hong, S. Madden, M. Franklin, S. Shenker, "The Sensor Network as a Database," USC Technical Report No. 02-771, September 2002.
Intro: Sensor networks need a new paradigm to store data as a database.
Problem: Current distributed databases will not work properly with wireless sensor networks. We need another way, in that things will remain energy-efficient.
Technical: The main thrust of the paper is that the current models are not sufficient for the highly constrained WSN. Instead, we can use two models for distributing the database. The first is to do some form of flooding of a query throughout the network. The other is to route the queries using some geographic information (much like GHT).
Perhaps the biggest difference in a database for a WSN is that to maintain some form of efficiency, we are willing to give up perfect accuracy, and just take something close to correct. In other words, "good enough". This is actually used a lot in other computer science fields, as many algorithms in their original form could take forever (i.e. traveling salesman), so some heuristic is used instead. We don't need the optimal solution, just close enough.
Joins are handled with tuples, and additionally use pipelining and partitioning to make things more efficient. Also, data aggregation can be used, since requests to a given area may be copious, and aggregating the data before sending might be better than sending it all individually.
For optimizing, they also mention eddies. These basically intercept data and send it to better "operators" to make things more efficient.
Impressions: This is a relatively decent paper, probably one of the earlier ones dealing with distributed databases in sensor networks. I don't see any implementation, which tells me much of this may be theoretical, but they have definitely addressed many of the same issues that are seen in the other papers.
Beyond Average: Toward Sophisticated Sensing with Queries
Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek, Beyond Average: Towards Sophisticated Sensing with Queries, IPSN'03.
Intro: We need a good way to query information from a sensor network. This paper presents ways to do this under resource constraints for a variety of applications.
Problem: This paper effectively extends the framework of TinyDB and traditional SQL, giving more functionality that can help in both the area of queries and also hopefully in power management, although not much detail is given there.
Technical: The first thing mentioned is applications of this approach: topographical mapping, summarization of data (i.e. aggregation, and vehicle tracking, which the authors admit is a work in progress. What we've got in the end is a custom query language by the authors, dubbed TAG, which is similar to SQL, and built on TinyDB. The first things, queries by flooding and data aggregation, are handled by TinyDB. The new features are events, which are pretty much as you would expect, data collection contingent on a given event occurring. The other, storage points, are useful in that it provides a temporary buffer to respond to queries on a given node more easily.
From here on out, they describe various implementations for their target applications, and give both a naive approach and a modified approach.
Impressions: Their approaches are interesting, and it's nice to see the typical approaches, and then optimizations on top of that. I'd like to see a good summary of their query set, and I'd also like to see some more power related issues.
Synopsis Diffusion for Robust Aggregation in Sensor Networks
Synopsis Diffusion for Robust Aggregation in Sensor Networks. S. Nath, P. Gibbons, S. Seshan and Z. Anderson ACM SenSys, Baltimore, MD, November 2004
Intro: While TAG is all well and good, it uses a tree-based approach. Synopsis diffusion aims instead at a multi-path algorithm for routing data.
Problem: Synopsis diffusion aims to attain the power savings of the tree-based approach of TAG by integrating multi-path routing, all the while integrating other algorithms to avoid double / multiple counting of data values in such a multi-path environment.
Technical: What essentially happens in this system is that "order-and-duplicate-insensitive" synopses (ODI) are used to keep the double count problem under control. What this means is that data is summarized, and handed to nodes, and the summary is not dependent on order of receipt, partial results, or how many summaries actually arrive at that node. They claim this solves the above problem, AND can lead to more energy-efficient aggregation and topologies.
Their approach consists of: synopsis generation, the creation of a new synopsis, synopsis fusion, which merges two synopses into one new one, and synopsis evaluation, which obtains the answer / value from the synopsis that is desired.
For the most part, this follows the flooding approach for sending out queries. There is no geographic routing of data.
They go into some proofs that their algorithms are correct, and I'll be honest, it's a little hard to decipher. They also test their scheme with several aggregation approaches: TAG, TAG2, Rings, Adaptive Rings, and good ol' flooding.
The results, of course, say that this is a better method than tree-based routing. And they come to the conclusion that as far as power / accuracy, adaptive rings is the best aggregation scheme, with flooding being next, if the application is short-lived.
Impressions: Not bad, I didn't completely understand all of what's here, but they seem to have taken a lot of care in proving, at least algorithmically, that their approach is the best. They simulated, of course, and it would be interesting to see how it fares in the real world, since even simulated losses do not necessarily capture the messiness inherent in "real life".
IEEE 1451: A Standard in Support of Smart Transducer Networking
Kang Lee, IEEE 1451: A Standard in Support of Smart Transducer Networking, IEEE Instr. and Meas. Tech. Conference, May 2000 (from NIST)
This paper deals with a short introduction to the IEEE 1451 standard. It aims to give a standardized interface to "smart" sensors. This consists of four subcategories:
1451.2 - This defines the actual data format for a particular transducer. The idea is that if this specification is available, then we have a standardized format by which we can ascertain the capabilities of the device and interface with it.
1451.1 - This provides a model of the transducer, a sort of black box view of the sensor as it would be used in a programming or network environment. Doing this allows more abstraction of the hardware, and keeps management of details to a minimum.
1451.3 - This defines a system by which many of these transducers can talk to each other and keep synchronized.
1451.4 - This defines an interface for mixed mode devices, i.e. analog devices.
They say that an Ethernet connected network can work for this, and there is no mention of wireless, but I'm sure this is because of the date of the paper, and I believe subsequent 1451.x standards have addressed wireless.
Plug-and-Play Sensors in Wireless Networks
Dunbar, M., Plug-and-play sensors in wireless networks, IEEE Instrumentation & Measurement Magazine, Vol.4, No.1, pp.19-23, March 2001
Another short paper, dealing with primarily the concern I had above. Bluetooth was being talked about a lot back in '01, and their proposition consisted of converting sensor data to a common analog electrical signal, and then reading that to make the electrical interface consistent, then using Bluetooth to eliminate the costs of wires and such, and they would be more robust as well. We've already seen some issues with that as well, though, throughout our readings in this class.
In addition, the integration of IEEE 1451 provides for a consistent data interface as well, and combined should produce something that not only provides a common interface, but also allows for a network that should be able to configure itself as opposed to manually hooking up each individual sensor.
The Semantic Web
Tim Berners-Lee, James Hendler and Ora Lassila, "The Semantic Web", Scientific American, May 2001
This paper is more of a vision than present day, but all the while integrates things that HAVE already come to pass, so it's not so far-fetched as one may think.
Currently, data is not typically represented in a fashion that is usable to computers. Sure, a computer can display the information, store it, and number-crunch on it, but it never really knows what that data IS. We as humans interpret that data after we tell the machines to manipulate the data in some predefined way.
So... why don't we specify what the data means? That's what semantics deals with. Several necessary pieces to the puzzle are already there. XML lets us associate other data tags and descriptors for data, which more thoroughly define what the data is, but it doesn't tell us how it relates to OTHER data. So that's where RDF comes in, which specifies data in the form of triples, subject-verb-object style. For example, it could be: Lee – is the owner of – Isuzu Rodeo. Yeah, shameless plug for my new vehicle, but hey... anyway, the XML would probably have specified somewhere that an Rodeo IS a vehicle, and not an actual “rodeo”. So now we would have machines making logical inferences on data.
Relationships between objects are defined by what are known as ontologies. Probably the best way to think about this is in the framework of existing expert systems. There are sets of rules that define how things relate to each other, and inferences are made based on those rules, much as they are in expert systems.
Eventually, everything will know how it relates to everything else, and then the machines take over. At least that's how it happened in The Terminator. Right?
The Semantic Web Revisited
Nigel Shadbolt, Tim Berners-Lee and Wendy Hall, "The Semantic Web Revisited", IEEE Intelligent Systems, 21(3) pp. 96-101, May/June 2006
Honestly, this entire paper almost serves as a restatement of the above, except with one new statement, which boils down to, “Our stuff doesn't suck! Give Semantic Web a chance!”
Really, the paper gives some progress reports, and says that the “e-science” community has adopted a good chunk of this, like using the RDF language. However, the vision laid out in the above paper has not yet come to fruition, and many things are stated as to why making this work would be a good thing.
One of the concerns is that ontologies are meant to express relationships, and should be well thought out. There is some mention of “folksonomies”, which shouldn't even be a WORD, but entail tagging data to obtain some emergent behavior. This is quite different from ontologies, and as such, some people question how much ontology management may cost. Of course, the authors justify that it will be well worth it, and I think once some of this becomes more feasible, it will work out. Until then, the interested parties need to keep plugging away.
IEEE 1451 Standard and Frequency Output Sensors: How to Obtain a Broad-Based Industry Adoption?
Sergey Y. Yurish, IEEE 1451 Standard and Frequency Output Sensors: How to Obtain a Broad-Based Industry Adoption?, Sensors & Transducers Magazine, Vol. 59, Issue 9, September 2005, pp. 412-418
I don't claim to completely understand what this paper is getting at. It looks like they are taking “frequency output sensors”, which I understand are sensors that give output at specific frequencies, and aiming to generalize these into a TEDS specification (which is part of IEEE 1451). They give the physical representation, which is for 1451.2, and also the mixed-mode interface, which is for 1451.4.
After this, some justification of why this will be useful to industry, and some of the features this particular piece of hardware will have. The eventual goal, of course, is to have smart sensors for almost everything, which means that all of the intelligence, sensing, storage, and communications mechanisms will all be integrated into one of these devices.
Honestly, this paper wasn't very clear.
Semantics-enabled framework for knowledge discovery from Earth observation data archives
Durbha, S.S.; King, R.L., Semantics-enabled framework for knowledge discovery from Earth observation data archives, IEEE Trans. Geoscience and Remote Sensing, Vol. 43, no.11, pp.2563-2572, Nov. 2005
This is actually an interesting paper, even if I don't understand everything in it. From what I understand, this is the application of ontologies to the realm of image processing / remote sensing. The general idea is that there are large amounts of image data out there, and sending out a query and sifting through the inordinate amount of data is rather complex, and doesn't scale well, either.
Enter our ontologies. The first job is to take the image data and analyze it to something more usable. So using rules that look like things seen in Discrete Structures, certain geographic features are classified. But generally that isn't quite enough. Usually, when things are identified with rules, there is not a 100% probability that the identification is correct. So the probability that the correct choice has been made must be factored in as well.
At this point, we have our objects, and they are classified in such a way that a semantic query can be sent out. The data is known, and we also know how those pieces of data relate, which makes the search much easier. Not only that, but this system is capable of learning as it goes, thus leading to new inferences and rules.
Again, good stuff, hopefully I'll understand more of the details next week when this is presented.
OpenGIS SensorML Implementation Specification
Open Geospatial Consortium, OpenGIS Sensor Model Language (SensorML) Implementation Specification, Document #OGC 05-086r2, Feb. 2006
SensorML is best considered an extension / application of XML. The idea here is that various sensors can be modeled, or distilled down to their essence, and described via XML, or SensorML, as it were.
The first part of SensorML is the existence of phenomena. These are things that can happen in the real world, and are what we want our sensors to actually measure, or at least a subset thereof.
So these sensors observe the phenomena, and SensorML aims to either describe the way that data was obtained, or to generate new data from past data by inference. This sounds like a useful spot for ontologies and inference engines.
Lastly, these observed phenomena are turned into data values that are stored / read somewhere else. Usually all of these phenomena are geospatial in nature.
So, the list of what SensorML aims to do:
- provide some general information on sensors to help in the data discovery process - add support for geolocation of the measured data - give some performance metrics - provide a description of how data was obtained - provide some process chain by which new data can be generated - archive fundamental properties of the sensor
So, to distill this down to its essence, SensorML is a way to describe sensors in a general way, by stating how they interact with various phenomena to obtain data, and how these sensors eventually store and use the data as well. As such, detailed descriptions of the actual hardware are not important, as this serves as a BEHAVIORAL model. If not a black box, then a partial black box, in any case.
Potentially, this could be VERY useful stuff. Boiling sensors down to their bare essence will allow us to get away from hardware-specific implementations, and actually focus on the functionality of the sensor and what we're measuring. Very nice indeed.
A Collaborative Approach to In-Place Sensor Calibration
V. Bychkovskiy, S. Megerian, D. Estrin, M. Potkonjak, "Colibration: A Collaborative Approach to In-Place Sensor Calibration", IPSN 2003.
Powerpoint presentation: Slides
Notes on presentation: Notes
And just because I can...
Flexible power scheduling for sensor networks
Hohlt, B. Doherty, L. Brewer, E., Flexible power scheduling for sensor networks. Information Processing in Sensor Networks, 2004. IPSN 2004. Third International Symposium on, 26-27 April 2004, pp. 205-214
We want to have a way to schedule idle time, or more specifically, eliminate it, as there is significant energy loss associated with idle listening. Hence FPS is introduced.
The gist of the protocol is to schedule coarse-grained communication for turning the radios on and off, and fine-grained for communication at the MAC layer.
This paper seems vaguely familiar, actually. I presented something very similar to this. The idea is that each node maintains a schedule in which it can perform certain operations at scheduled times. These operations are Transmit, Receive, Advertisement, Transmit Pending, Receive Pending, and Idle. Perhaps these are not best viewed as operations, but more are states that a particular node is in at a particular time slice.
As you can guess, time synchronization is an issue in this system, again. It always seems to rear its head. A system like this MUST remain synchronized, or the windows for operations will not coincide correctly, leading to MORE power inefficiency.
Latency is also an issue, in that any time you are turning off radios, there is some time that if a request comes in, a node will not be able to respond.
Analysis data is given in detail, and this does yield a significant improvement over idle listening, as one would expect. Latency, not so much, but that’s to be expected. We can deal with a little latency for the large amount of power savings, and if we really more rapid response, we probably need something less power-constrained anyway.
Twinkle: Network Power Scheduling in Sensor Networks
Twinkle: Network Power Scheduling in Sensor Networks. Barbara A. Hohlt and Eric A. Brewer, EECS Department, University of California, Berkeley, Technical Report No. UCB/CSD-05-1409, 2005.
Ends up being an extension of FPS, as stated in the paper. The underlying structure ends up being similar to FPS, with a few key extensions:
Partial flows: The flow, from what I understand, is a defined power schedule through several nodes. They introduce partial flows so that other things can be supported, such as stopping the scheduling at an aggregating node, for example.
Broadcast: An example of a partial flow, it is effectively a reversed partial flow, and as such, they keep two queues, so that messages to and from the base station can be stored.
Time synchronization: They have added a more fine-grained time synchronization protocol, in the form of FTSP. This allows MAC layer time stamping, and also accounts for skew.
Latency Optimizations: This is achieved with two ideas, and these are reservation windows and fractional flows.
Reservation windows: The idea is to have the receiver request slots, so it is not predicated on the sender. But it doesn’t use the entire slot to choose from, it uses a subset known as a reservation window. This actually sounds similar to what was done in an earlier paper, in that the T value was diced up into a listen-and-send period.
Fractional flows: Instead of having a slot every cycle, it uses a slot every so often (i.e. every k cycles).
Not a bad paper overall, the reasoning seems sound, and they apply their system to previous deployments of sensor networks, which is very interesting.
Low-energy sensor network time synchronization as an emergent property
Bush, S.F., Low-energy sensor network time synchronization as an emergent property. Computer Communications and Networks, 2005. ICCCN 2005. Proceedings. 14th International Conference on. 17-19 Oct. 2005, pp. 93-98
As we’ve seen earlier, time synchronization is always an issue. But using time synchronization also causes power drain, and as such, other techniques can be used to possibly mitigate some of the power issues.
In this paper, they propose using a variant of Pulse Coupled Oscillation, and take into account power used for frequent circuit powerup / shutdown as well as TX/RX power.
In wired environments, NTP is used a lot, but for wireless sensor networks, it is not fine-grained enough, and as such, other methods need to be used. RBS is one of these, which synchronizes instead to a relative event.
From what I understand, pulses are emitted that are synchronized on in PCO. These pulses are .2ms in length, in a 5ms window. They put together a model for power consumption, and also decide to use GPS nodes for a master clock for other nodes locally.
Also, apparently with these types of pulses, the system will eventually converge upon a single frequency, thusly synchronizing the nodes. Power testing is done, and shown to be efficient, although I’m not sure this is a real-world implementation. They also state that their system is better with nodes that can move.
Minimum Power Configuration in Wireless Sensor Networks
G. Xing, C. Lu, Y. Zhang, Q. Huang, and R. Pless, Minimum Power Configuration in Wireless Sensor Networks, ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), May 2005.
The general idea of this paper is to merge several different methods for reducing power consumption. These are:
Topology control: By controlling the way topologies are formed by limiting broadcast range and pairing of nodes, we can limit power consumption.
Power aware routing: This is routing while remaining aware of the cost of sending to certain nodes, and may also include not routing through nodes if they don’t have enough power left.
Sleep management: As we’ve seen before, this covers the area of shutting down the radios and MCUs whenever they are not needed, thusly reducing idle listening and reducing energy consumption.
They state that the problem is actually NP-hard, which means much like the traveling salesman problem, this problem cannot be solved perfectly with the optimal answer, because it would take far too long. So they use a heuristic method.
The first is a matching based algorithm, designed to take care of the case where there is only one sink, and the data flows are not splittable. This makes things behave according to a cost-distance problem in networks.
The second is the shortest-path tree heuristic. This is present to try to balance the trees that are effectively set up in the network topology, so that the system is load-balanced.
Also is the incremental shortest-path heuristic. This is present to find the incremental cost of going from node to node, irrespective of the actual nodal cost itself.
The constant-ratio approximation algorithm is present to try to make scaling more efficient.
The way the protocol is designed is table-based, with routing tables maintained on each node, and routing costs are updated every once in a while.
As their test platform, they use a simulator, by utilizing the Prowler network simulator at the link layer, and adding routing improvements from the Rmase project.
Interesting enough as a paper, but nothing new at this point.
Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks
G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless and C. Gill, Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks, ACM Transactions on Sensor Networks, 1(1): 36-72, August 2005.
The goals of this paper are threefold:
1) Present a protocol (dubbed Coverage Configuration Protocol, or CCP) to provide dynamic changes in coverage in the network dependant on the application.
2) Show some geometric analysis of the relationship between coverage and connectivity between nodes.
3) Integrate CCP with SPAN for both coverage and connectivity concerns.
The idea behind their coverage is that not ALL nodes need be active to provide adequate coverage, so the analysis focuses on how many nodes we can put to sleep without losing the coverage desired for the given application.
Much of the rest is how things scale on connectivity vs. coverage for a variety of cases, which are quantified in terms of connectivity as defined by a communication range that is at least twice the sensing range.
In any case, they give some information for Rc >= 2Rs, and also when the coverage is less then double the sensing range, i.e. Rc < 2Rs. In this case, they don’t think CCP is up to the task, so in this case, they integrate with an existing protocol, SPAN. This solves that particular problem.
Much evaluation given, as usual, but it looks like all of their tests are in a simulator. It doesn’t make it invalid, but it would be interesting to see some information on real-world deployments.
UWB summary
From what I understand, UWB transmits data over a large bandwidth, typically greater than 500 Mhz (or 25% of the center frequency). If the use is to be high-bandwidth, the range of such a system is typically limited. Apparently, pulse-based systems are often used in UWB systems. These pulses take the entire UWB bandwidth, meaning that for short range, gigabit bandwidths can be achieved. For longer range, the pulses are not as often, leading to a lower bandwidth. As the entire bandwidth is taken, multipath fading is not a big issue, but ISI is.
UWB transmits data by pulse positions in the bandwidth, or by time modulating. They can also be encoded by polarity of the pulse, amplitude, or orthogonal pulses.
Also, it looks like narrow-band and UWB may interfere with each other, or at least there was concern about this issue.
Hierarchical temporal memory
Wow, this one is out there a little bit. Let's see if I can boil this down a little bit.
First, this idea is somewhat similar to neural networks, except that instead of neurons firing, we have our hierarchical memory that stores things, and tries to infer causes. This can hold true for actions, visual data, or a host of other things. So what happens is that causes and effects are generally grouped together.
Where the hierarchical memory comes in is to try to take small sets of the input, and make logical inferences on what that data means, or “beliefs” about the data. These beliefs are propagated upwards from the sensor data, until some overarching conclusion is reached. Whether this conclusion is correct or not remains to be seen, but people don't always make the right conclusion, either.
The memory hierarchy is all well and good, but it's only one piece of the puzzle. Many things are related spatially, but in real life, they are also related temporally. As such, sensory input that occurs within a small time frame is typically related to the same cause, and as this temporal data is distilled upwards, larger truths about the data are discovered by piecing together smaller beliefs about the data. This is considered much like speech, where locally temporal sounds are grouped together to give meaning, then each word is grouped in a sentence, and then understood to give it actual meaning.
Of course, as far as the spatial recognition goes, it takes a long time to learn. Image recognition, in particular, is not easy for machines, and is an ongoing problem. I see this as one of the primary roadblocks to a system like this. As such, given that so many representations of data can occur, a system of this nature will need a fairly high amount of memory, although the hierarchy supposedly helps limit this issue.
