Artificial Intelligence

Wintermute project aims to bring Artificial Intelligence to Ubuntu

2011-02-04T17:31:00.000-08:00

Named after a computer from a very famous novel, Wintermute is an attempt to implement the world’s first personal edition of an intelligent framework of applications and libraries, and in the future, an intelligent operating system.

The Project

According to the project’s Launchpad page

Wintermute bolsters the capabilities of using neural networking to learn about its host, a pseudo-langauge engine that permits translations and grammar rulesets of any language to be incorporated into the system, and database downloads of different sets of data to permit the combination of the world’s first personal virtual self-thinking assistant.

The project aims to have something like Apple Knowledge Navigator implemented (READ: Not Clippy!), “So far, we’ve implemented an abstract system of language processing, so translations’ll be as swappable as extensions for Chromium, and we’re looking at other semantic projects (DPedia, NEPOMUK from the Semantic Desktop) to harness the need of knowledge.”, developer Jacky Alcine told us.

A Little Help

The project is looking for Programmers with either GLib, C++ or Python knowledge, Beta testers/People who can enhance the VoxForge voice modules and Designers for the Wintermute, UAIT and Intell@Ubuntu logos.

or more information see the Wintermute blog and the Wintermute Psychology and Ubuntu Artificial Intelligence Team project pages.

Robonaut 2 -The First Humanoid Heads into Space: A New Era Dawns

2010-12-23T16:05:00.001-08:00

Another vivid sign that we have entered the dawn of the age of post-biological intelligence: NASA and General Motors announced on Tuesday that they planned to send a robot to the International Space Station, with the eventual goal of having it help the astronauts there.

Although there are already several robots in space — including the famous now AI-enhanced Mars Rovers, which have been zipping around the red planet for years — NASA and G.M. said this would be the first human-like robot to leave Earth.

Better Education Through Open Source Robots

2010-12-23T16:04:00.000-08:00

Heather is a freelance writer, as well as a monthly contributor for OEDb, a site that helps students select among accredited online schools. She invites comments and freelancing job inquiries at heatherjohnson2323@gmail.com.

There has been a lot of talk about open source hardware lately and its potential effects on research and education. ETech 2008 showcased many examples of open hardware and offered an insightful presentation[PDF] to those who are new to the emerging technology. Likewise, popular sites like Slashdot and bloggers like Scobleizer have been discussing the growing movement.

The increasing popularity of open source software has already had a tremendous influence on education and the world as a whole. Not only are many schools now making the switch to open source programs, leading universities like UC Berkeley and Carnegie Mellon are involved with developing large open source software projects.

However, we have yet to see open hardware really take off. Ryan Singel of Wired feels that 2008 could be the year and I second that opinion. Leading the pack seems to be open source robotics, which has been embraced by several major universities.

Just last month, Willow Garage’s Steve Cousins gave a keynote speech at ETech 2008 about open source personal robots, which has brought more attention to the subject. Willow Garage is a privately funded lab that experiments with various robotics platforms.

This open source robotics movement can be felt on many college campuses as well. Carnegie Mellon, which I previously stated is involved with open source software, is also building OS personal robots. The university has recently formed a joint project called the Institute for Personal Robots in Education (IPRE).

The IPRE is a joint project between Georgia Tech and Bryn Mawr College, with sponsorship provided by Microsoft Research. Its purpose is to help advance robotics research and computer science education. The IPRE is currently selling open source robot kits, which are geared toward educators and can be integrated with computer education curricula.

Instructions can be found RobotEducation.org if you are interested in building your own educational robot.

First Robot Scientist Makes Gene Discovery

2010-12-23T16:02:00.000-08:00

He can come up with a hypothesis, plan an experiment, reason about the results, and then plan his next steps.

Now ADAM is the first robot—but maybe not the last—to have independently discovered new scientific information, according to scientists who recently built themselves the mechanical colleague.

Ross King, of Aberystwyth University in Wales, U.K., and colleagues created ADAM by combining the most advanced robotics hardware with artificial intelligence software.

"Normal robots just do what you tell them, but ADAM is different, because it can hypothesize and try to solve a problem itself," King said.

To test ADAM's capabilities, King's team gave the robot the task of discovering more about the genome of baker's yeast, a simple microbe often used as a model for studying more complex biological systems.

First ADAM was given a crash course in biology, including everything that is already known about baker's yeast.

ADAM quickly set to work, formulating and testing 20 different hypotheses. The robot eventually identified the genes that code for enzymes involved in yeast metabolism—a scientific first for a robot.

Using independent experiments, King and his colleagues were able to verify ADAM's results.

Robots to Replace Scientists?

Robot scientists like ADAM might one day work alongside human researchers to boost productivity, King said.

"There are certain scientific problems that are so complicated that there are not enough people available to solve them," King said. "We need to automate in order to have a hope of solving these problems."

Robot scientists, for example, could prove valuable in drug design and screening.

King's next scientific robot, EVE, is being created specifically to help search for new drugs to treat tropical diseases such as malaria.

But King and his colleagues don't think that robots can ever completely replace human scientists.

"While robots are better at coordinating thousands of experiments," King said, "humans are better are seeing the big picture and planning the overall experiment."

Sensory Memory

2009-09-09T16:49:00.000-07:00

Sensory memory is the first level of memory, as explained in the paragraph levels of memory. Sensory memory retains the brief impression of a sensory stimulus after the stimulus itself has ended. Imagine, you see an object. When the object has diappeared, it may still be vivid in your memory.

"The sensory memory holds a short impression of sensory information even when the sensory system does not send any information anymore."

Research
Most research has focused on the visual and auditory systems, although there are presumably sensory registers for all our senses. For visual stimuli, we have an extremely short 'photographic' memory (about 500 milliseconds), which gives us a persistent image.
In hearing we have echoic memories, which are mental echoes of stimuli.

Characteristics
There are various specific issues about sensory memory: first, it is a high capacity form of memory registration of visual data. Second, information in the sensory memory is un-interpreted. Third, sensory memory is short; visual information, for example, fades away in less than a second.

Using the Information
If we want to use the information in the sensory memory, we must quickly encode it it into a more durable form. Processing begins with attention, which selectively determines what will 'get through' for further examination and what will not. Attention allows us to focus on parts of the stimulus and thereby to recognize some of its features. Obviously, any shortcomings in sensory memory can create problems for further processing of sensory information.

Sensory memory allow us to take a 'snapshot' of our environment, and to store this information for a short period. Only informatin that is transferred to another level of memory will be preserved for more than 1 à two seconds.

Portable device to detect suicide bombers

2009-08-29T20:33:00.000-07:00

Washington, June 28 (ANI): A group of students have developed a portable device to detect the weapons of suicide bombers.

Improvised explosive devices (IEDs), the weapons of suicide bombers, are a major cause of soldier casualties in Iraq and Afghanistan.

Now, a group of University of Michigan (U-M) engineering undergraduate students have developed a new way to detect them.

The students invented portable, palm-sized metal detectors that could be hidden in trash cans, under tables or in flower pots, for example.

The detectors are designed to be part of a wireless sensor network that conveys to a base station where suspicious objects are located and who might be carrying them.

Compared with existing technology, the sensors are cheaper, lower-power and longer-range. Each of the sensors weighs about 2 pounds.

“Their invention outperforms everything that exists in the market today,” said Nilton Renno, a professor in the U-M Department of Atmospheric, Oceanic and Space Sciences.

The students undertook this project in Renno’s Engineering 450 senior level design class.

“They clearly have an excellent understanding of the problem. They also thought strategically and designed and optimized their solution. The combination of a movable command center with a wireless sensor network can be easily deployed in the field and adapted to different situations,” said Renno.

The core technology is based on a magnetometer, or metal detector, explained Ashwin Lalendran, an engineering student who worked on the project and graduated in May.

“We built it entirely in-house - the hardware and the software,” Lalendran said.

“Our sensors are small, flexible to deploy, inexpensive and scalable. It’s extremely novel technology,” he added. (ANI)

Sensor Network Simulator and Emulator

2009-08-24T06:17:00.000-07:00

The Necessity of Network Simulation

The emergence of wireless sensor networks brought many open issues to network designers. Traditionally, the three main techniques for analyzing the performance of wired and wireless networks are analytical methods, computer simulation, and physical measurement. However, because of many constraints imposed on sensor networks, such as energy limitation, decentralized collaboration and fault tolerance, algorithms for sensor networks tend to be quite complex and usually defy analytical methods that have been proved to be fairly effective for traditional networks. Furthermore, few sensor networks have come into existence, for there are still many unsolved research problems, so measurement is virtually impossible. It appears that simulation is the only feasible approach to the quantitative analysis of sensor networks.

Why a New Simulator

ns2, perhaps the most widely used network simulator, has been extended to include some basic facilities to simulate sensor networks. However, one of the problems of ns2 is its object-oriented design that introduces much unnecessary interdependency between modules. Such interdependency sometimes makes the addition of new protocol models extremely difficult, only mastered by those who have intimate familiarity with the simulator. Being difficult to extend is not a major problem for simulators targeted at traditional networks, for there the set of popular protocols is relatively small. For example, Ethernet is widely used for wired LAN, IEEE 802.11 for wireless LAN, TCP for reliable transmission over unreliable media. For sensor networks, however, the situation is quite different. There are no such dominant protocols or algorithms and there will unlikely be any, because a sensor network is often tailored for a particular application with specific features, and it is unlikely that a single algorithm can always be the optimal one under various circumstances.

Many other publicly available network simulators, such as JavaSim, SSFNet, Glomosim and its descendant Qualnet, attempted to address problems that were left unsolved by ns2. Among them, JavaSim developers realized the drawback of object-oriented design and tried to attack this problem by building a component-oriented architecture. However, they chose Java as the simulation language, inevitably sacrificing the efficiency of the simulation. SSFNet and Glomosim designers were more concerned about parallel simulation, with the latter more focused on wireless networks. They are not superior to ns2 in terms of design and extensibility.

Features of SENSE

SENSE is designed to be an efficient and powerful sensor network simulator that is also easy of use. We identify the three most critical factors as:

Extensibility: The enabling force behind the fully extensibility network simulation architecture is our progress on component-based simulation. We introduced a component-port model that frees simulation models from interdependency usually found in an object-oriented architecture, and then proposed a simulation component classification that naturally solves the problem of handling simulated time. The component-port model makes simulation models extensible: a new component can replace an old one if they have compatible interfaces, and inheritance is not required. The simulation component classification makes simulation engines extensible: advanced users have the freedom to develop new simulation engines that meet their needs.
Reusability: The removal of interdependency between models also promotes reusability. A component developed for one simulation can be used in another if it satisfies the latter's requirements on the interface and semantics. There is another level of reusability made possible by the extensive use of C++ template: a component is usually declared as a template class so that it can handle different type of data.
Scalability: Unlike many parallel network simulators, especially SSFNet and Glomosim, parallelization is provided as an option to the users of SENSE. The reflects our belief that completely automated parallelization of sequential discrete event models, however tempting it may seem, is impossible, just as automated parallelization of sequential programs. Even if it possible, it is doomed to be inefficient. Therefore, parallelizable models require more effort than sequential models, but a good portion of users are not interested in parallel simulation at all. In SENSE, a parallel simulation engine can only execute components of compatible components. If a user is content with the default sequential simulation engine, then every component in the model repository can be reused.

Currently Available Components and Simulation Engines (as of Oct 21, 2006)

Battery Model:
- Linear Battery
- Discharge Rate Dependent and/or Relaxation Battery
Application Layer:
- Random Neighbor
- Constant Bit Rate
Network Layer:
- Simple Flooding
- A simplified version of ADOV without route repairing
- A simplified version of DSR without route repairing
- Self Selective Routing (SSR)
- Self Healing Routing (SHR)
MAC Layer:
- NullMAC
- IEEE 802.11 with DCF
Physical Layer: Duplex Transceiver
Wireless Channel:
- Free Space
- Adjacency Matrix
Simulation Engine: CostSimEng (sequential)

The Future of Artificial Intelligence

2009-08-16T05:27:00.000-07:00

Dr. Mark Humphrys
University of Edinburgh

Artificial Intelligence (AI) is a perfect example of how sometimes science moves more slowly than we would have predicted. In the first flush of enthusiasm at the invention of computers it was believed that we now finally had the tools with which to crack the problem of the mind, and within years we would see a new race of intelligent machines. We are older and wiser now. The first rush of enthusiasm is gone, the computers that impressed us so much back then do not impress us now, and we are soberly settling down to understand how hard the problems of AI really are.

What is AI? In some sense it is engineering inspired by biology. We look at animals, we look at humans and we want to be able to build machines that do what they do. We want machines to be able to learn in the way that they learn, to speak, to reason and eventually to have consciousness. AI is engineering but, at this stage, is it also science? Is it, for example, modeling in cognitive science? We would like to think that is both engineering and science but the contributions that is has made to cognitive science so far are perhaps weaker than the contributions that biology has given to the engineering.

The confused history of AI

Looking back at the history of AI, we can see that perhaps it began at the wrong end of the spectrum. If AI had been tackled logically, it would perhaps have begun as an artificial biology, looking at living things and saying "Can we model these with machines?". The working hypothesis would have been that living things are physical systems so let's try and see where the modeling takes us and where it breaks down. Artificial biology would look at the evolution of physical systems in general, development from infant to adult, self-organization, complexity and so on. Then, as a subfield of that, a sort of artificial zoology that looks at sensorimotor behavior, vision and navigation, recognizing, avoiding and manipulating objects, basic, pre-linguistic learning and planning, and the simplest forms of internal representations of external objects. And finally, as a further subfield of this, an artificial psychology that looks at human behavior where we deal with abstract reasoning, language, speech and social culture, and all those philosophical conundrums like consciousness, free will and so forth.

That would have been a logical progression and is what should have happened. But what did happen was that what people thought of as intelligence was the stuff that impresses us. Our peers are impressed by things like doing complex mathematics and playing a good chess game. The ability to walk, in contrast, doesn't impress anyone. You can't say to your friends, "Look, I can walk", because your friends can walk too.

So all those problems that toddlers grapple with every day were seen as unglamorous, boring, and probably pretty easy anyway. The really hard problems, clearly, were things demanding abstract thought, like chess and mathematical theorem proving. Everyone ignored the animal and went straight to the human, and the adult human too, not even the child human. And this is what `AI' has come to mean - artificial adult human intelligence. But what has happened over the last 40-50 years - to the disappointment of all those who made breathless predictions about where AI would go - is that things such as playing chess have turned out to be incredibly easy for computers, whereas learning to walk and learning to get around in the world without falling over has proved to be unbelievably difficult.

And it is not as if we can ignore the latter skills and just carry on with human-level AI. It has proved very difficult to endow machines with `common sense', emotions and those other intangibles which seem to drive much intelligent human behavior, and it does seem that these may come more from our long history of interactions with the world and other humans than from any abstract reasoning and logical deduction. That is, the animal and child levels may be the key to making really convincing, well-rounded forms of intelligence, rather than the intelligence of chess-playing machines like Deep Blue, which are too easy to dismiss as `mindless'.

In retrospect, the new view makes sense. It took 3 billion years of evolution to produce apes, and then only another 2 million years or so for languages and all the things that we are impressed by to appear. That's perhaps an indication that once you've got the mobile, tactile monkey, once you've got the Homo erectus, those human skills can evolve fairly quickly. It may be a fairly trivial matter for language and reasoning to evolve in a creature which can already find its way around the world.

The new AI, and the new optimism That's certainly what the history of AI has served to bear out. As a result, there has been a revolution in the field which goes by names such as Artificial Life (AL) and Adaptive Behavior, trying to re-situate AI within the context of an artificial biology and zoology (respectively). The basic philosophy is that we need much more understanding of the animal substrates of human behavior before we can fulfil the dreams of AI in replicating convincing well-rounded intelligence.

(Incidentally, the reader should note that the terminology is in chaos, as fields re-group and re-define themselves. For example, I work on artificial zoology but describe myself casually as doing AI. This chaos can, however, be seen as a healthy sign of a field which has not yet stabilized. Any young scientist with imagination should realize that these are the kind of fields to get into. Who wants to be in a field where everything was solved long ago?)

So AI is not dead, but re-grouping, and is still being driven, as always, by testable scientific models. Discussions on philosophical questions, such as `What is life?' or `What is intelligence?', change little over the years. There have been numerous attempts, from Roger Penrose to Gerald Edelman, to disprove AI (show that it is impossible) but none of these attempted revolutions has yet gathered much momentum. This is not just because of lack of agreement with their philosophical analysis (although there is plenty of that), but also perhaps because they fail to provide an alternative paradigm in which we can do science. Progress, as is normal in science, comes from building things and running experiments, and the flow of new and strange machines from AI laboratories is not remotely exhausted. On the contrary, it has been recently invigorated by the new biological approach.

In fact, the old optimism has even been resurrected. Professor Kevin Warwick of the University of Reading has recently predicted that the new approach will lead to human-level AI in our lifetimes. But I think we have learned our lesson on that one. I, and many like me in new AI, imagine that this is still Physics before Newton, that the field might have a good one or two hundred years left to run. The reason is that there is no obvious way of getting from here to there - to human-level intelligence from the rather useless robots and brittle software programs that we have nowadays. A long series of conceptual breakthroughs are needed, and this kind of thinking is very difficult to timetable. What we are trying to do in the next generation is essentially to find out what are the right questions to ask.

It may never happen (but not for the reasons you think)

I think that people who are worried about robots taking over the world should go to a robotics conference and watch these things try to walk. They fall over, bump into walls and end up with their legs thrashing or wheels spinning in the air. I'm told that in this summer's Robotic Football competition, the losing player scored all five goals - 2 against the opposing robot, and 3 against himself. The winner presumably just fell over.

Robots are more helpless than threatening. They are really quite sweet. I was in the MIT robotics laboratory once looking at Cog, Rodney Brooks' latest robot. Poor Cog has no legs. He is a sort of humanoid, a torso stuck on a stand with arms, grippers, binocular vision and so on. I saw Cog on a Sunday afternoon in a darkened laboratory when everyone had gone home and I felt sorry for him which I know is mad. But it was Sunday afternoon and no one was going to come and play with him. If you consider the gulf between that and what most animals experience in their lives, surrounded by a tribe of fellow infants and adults, growing up with parents who are constantly with them and constantly stimulating them, then you understand the incredibly limited kind of life that artificial systems have.

The argument I am developing is that there may be limits to AI, not because the hypothesis of `strong AI' is false, but for more mundane reasons. The argument, which I develop further on my website, is that you can't expect to build single isolated AI's, alone in laboratories, and get anywhere. Unless the creatures can have the space in which to evolve a rich culture, with repeated social interaction with things that are like them, you can't really expect to get beyond a certain stage. If we work up from insects to dogs to Homo erectus to humans, the AI project will I claim fall apart somewhere around the Homo erectus stage because of our inability to provide them with a real cultural environment. We cannot make millions of these things and give them the living space in which to develop their own primitive societies, language and cultures. We can't because the planet is already full. That's the main argument, and the reason for the title of this talk.

So what will happen?

So what will happen? What will happen over the next thirty years is that will see new types of animal-inspired machines that are more `messy' and unpredictable than any we have seen before. These machines will change over time as a result of their interactions with us and with the world. These silent, pre-linguistic, animal-like machines will be nothing like humans but they will gradually come to seem like a strange sort of animal. Machines that learn, familiar to researchers in labs for many years, will finally become mainstream and enter the public consciousness.

What category of problems could animal-like machines address? The kind of problems we are going to see this approach tackle will be problems that are somewhat noise and error resistant and that do not demand abstract reasoning. A special focus will be behavior that is easier to learn than to articulate - most of us know how to walk but we couldn't possibly tell anyone how we do it. Similarly with grasping objects and other such skills. These things involve building neural networks, filling in state-spaces and so on, and cannot be captured as a set of rules that we speak in language. You must experience the dynamics of your own body in infancy and thrash about until the changing internal numbers and weights start to converge on the correct behavior. Different bodies mean different dynamics. And robots that can learn to walk can learn other sensorimotor skills that we can neither articulate nor perform ourselves.

What are examples of these type of problems? Well, for example, there are already autonomous lawnmowers that will wander around gardens all afternoon. The next step might be autonomous vacuum cleaners inside the house (though clutter and stairs present immediate problems for wheeled robots). These are all sorts of other uses for artificial animals in areas where people find jobs dangerous or tedious - land-mine clearance, toxic waste clearance, farming, mining, demolition, finding objects and robotic exploration, for example. Any jobs done currently or traditionally by animals would be a focus. We are familiar already from the Mars Pathfinder and other examples that we can send autonomous robots not only to inhospitable places, but also send them there on cheap one-way `suicide' missions. (Of course, no machine ever `dies', since we can restore its mind in a new body on earth after the mission.)

Whether these type of machines may have a future in the home is an interesting question. If it ever happens, I think it will be because the robot is treated as a kind of pet, so that a machine roaming the house is regarded as cute rather than creepy. Machines that learn tend to develop an individual, unrepeatable character which humans can find quite attractive. There are already a few games in software - such as the Windows-based game Creatures, and the little Tamagotchi toys - whose personalities people can get very attached to. A major part of the appeal is the unique, fragile and unrepeatable nature of the software beings you interact with. If your Creature dies, you may never be able to raise another one like it again. Machines in the future will be similar, and the family robot will after a few years be, like a pet, literally irreplaceable.

What will hold things up? There are many things that could hold up progress but hardware is the one that is staring us in the face at the moment. Nobody is going to buy a robotic vacuum cleaner that costs �5000 no matter how many big cute eyes are painted on it or even if it has a voice that says, "I love you". Many conceptual breakthroughs will be needed to create artificial animals. The major theoretical issue to be solved is probably representation: what is language and how do we classify the world. We say `That's a table' and so on for different objects, but what does an insect do, what is going on in an insect's head when it distinguishes objects in the world, what information is being passed around inside, what kind of data structures are they using. Each robot will have to learn an internal language customized for its sensorimotor system and the particular environmental niche in which it finds itself. It will have to learn this internal language on its own, since any representations we attempt to impose on it, coming from a different sensorimotor world, will probably not work.

Predictions

Finally, what will be the impact on society of animal-like machines? Let's make a few predictions that I will later look back and laugh at.

First, family robots may be permanently connected to wireless family intranets, sharing information with those who you want to know where you are. You may never need to worry if your loved ones are alright when they are late or far away, because you will be permanently connected to them. Crime may get difficult if all family homes are full of half-aware, loyal family machines. In the future, we may never be entirely alone, and if the controls are in the hands of our loved ones rather than the state, that may not be such a bad thing.

Slightly further ahead, if some of the intelligence of the horse can be put back into the automobile, thousands of lives could be saved, as cars become nervous of their drunk owners, and refuse to get into positions where they would crash at high speed. We may look back in amazement at the carnage tolerated in this age, when every western country had road deaths equivalent to a long, slow-burning war. In the future, drunks will be able to use cars, which will take them home like loyal horses. And not just drunks, but children, the old and infirm, the blind, all will be empowered.

Eventually, if cars were all (wireless) networked, and humans stopped driving altogether, we might scrap the vast amount of clutter all over our road system - signposts, markings, traffic lights, roundabouts, central reservations - and return our roads to a soft, sparse, eighteenth-century look. All the information - negotiation with other cars, traffic and route updates - would come over the network invisibly. And our towns and countryside would look so much sparser and more peaceful.

Conclusion

I've been trying to give an idea of how artificial animals could be useful, but the reason that I'm interested in them is the hope that artificial animals will provide the route to artificial humans. But the latter is not going to happen in our lifetimes (and indeed may never happen, at least not in any straightforward way).

In the coming decades, we shouldn't expect that the human race will become extinct and be replaced by robots. We can expect that classical AI will go on producing more and more sophisticated applications in restricted domains - expert systems, chess programs, Internet agents - but any time we expect common sense we will continue to be disappointed as we have been in the past. At vulnerable points these will continue to be exposed as `blind automata'. Whereas animal-based AI or AL will go on producing stranger and stranger machines, less rationally intelligent but more rounded and whole, in which we will start to feel that there is somebody at home, in a strange animal kind of way. In conclusion, we won't see full AI in our lives, but we should live to get a good feel for whether or not it is possible, and how it could be achieved by our descendants.

THE FUTURE OF SENSOR NETWORKS

2009-08-07T18:41:00.000-07:00

From thermostats in building automation to computer numerical controls in factory automation, device and sensor information is traveling over the same technology that is powering our e-world. But how well is it working, and where is the trend taking us?

Mark Fondl, ICT and Lynn Linse, Lantronix, Inc.

The volume of data carried on a network increases as the devices on it become more sophisticated. Low-end devices may transmit data in 1 bit increments, indicating a simple on/off condition. High-end sensors, on the other hand, contain local intelligence and transmit complex data types measured in bytes (see Figure 1.)

To meet the need for more complex data communications, the industry has looked to other networks. In the process, many have asked: Can Ethernet/TCP/IP be used to replace some of these networks? Can some of the networks be integrated into higher level Ethernet architectures (e.g., DeviceNet over Ethernet, Interbus-S over Ethernet, LonWorks over Ethernet)? Some of the answers to these questions can be found in an examination of implementation costs, ease of use, performance, and vendor support.

Implemention Costs

Ethernet costs are not inherently lower than the other networks. For the foreseeable future, cost can be justified only by concentrating multiple sensors on one Ethernet interface.

Other factors contributing to the cost of implementation are the CPU resources. Here, Ethernet does not compare favorably with an architecture such as DeviceNet. For example, DeviceNet can run on a CPU with 4000 bytes of code and 176 bytes of RAM. Ethernet, though, requires a minimum of 64,000 bytes of code and 64,000 bytes of RAM. Here, many implementers insist the minimum is more like 256 KB each, but they would prefer 2–4 MB of code and RAM. If the volumes are low and the margins are high, the simpler software offsets Ethernet’s greater CPU requirements. But as volumes rise and margins shrink, the lower resource needs of something like DeviceNet will force a price premium for Ethernet with the same sales volumes.

Consideration of connection costs—especially for bit-level sensors in industrial environments—causes some to favor ASI and DeviceNet wiring. Optimized for machines in which many discrete sensors are located in a relatively small area (50 m), these sensor networks are ideal. But extending their range poses some difficulty, and based on response times of these clusters, bridging with Ethernet may provide value.

Ease of Use

Here the focus is on long-term support of software configuration. This has multiple facets:

TCP/IP ease of use is based on the wide availability of skilled technicians and tools.
But TCP/IP (at the moment) lacks the high-level standards that allow auto-replacement, which is supported in DeviceNet and ASI.
The complexity of the options found in TCP/IP can overwhelm inexperienced users.
Systems such as DeviceNet and ASI are well suited for applications in which the communications are kept on a local scale. But when the data travel into extended areas and applications in which specialized network skills are required, then a commercial TCû/IP network becomes attractive. Network evaluation can be as simple as a “ping” from almost any computer. Commercial technologies aimed at simple diagnostics will eventually become common. Training individuals to support TCP/IP will be much easier. Device networks feeling this pressure will undoubtedly develop simpler and even browser-based tools.

Performance

With a well-designed network, TCP/IP will perform quite well. But the network must be well designed. An isolated subnet with limited or master/slave functions can expect reliable 2–5 ms times. But the instant you add routers or other noncontrol traffic (including Web servers), you can expect delays of 500 ms or more. So Ethernet performs only as well as the user designs it to perform.

A sparsely designed Ethernet, which underuses its capacity, can rival or beat any deterministic control network. But a poorly designed Ethernet can be an operational nightmare.

Web access via TCP/IP is a common unrealistic hope. With control traffic running at 5–10,000 Bps, users often overlook the fact that a Web page can attempt to force millions of bytes of data through a network at the same time that control data are being transmitted, dwarfing the control traffic. Users and vendors still have to learn the tradeoffs here. Some Web access is wonderful, but this needs to be shared/supplemented with Web resources stored off the control network.

To improve performance on the sensor level, automation companies are experimenting with UDP and variations of limited TCP/IP stacks. These stacks listen only to certain types of transmissions, ignoring others and eliminating a retry structure for a high-speed master-slave structure. This is similar to how I/O has worked for years with PLCs. The architecture and wiring are Ethernet, but the openness is traded for performance.

Most systems don’t need this level of performance and should stay with standard Ethernet. As the technology continues to improve, you can imagine a time when a conventional approach will surpass proprietary methods.

Service and Support
Support for Ethernet TCP/IP systems is good, but the actual media (e.g., cables, connectors, and power) are rather unindustrial. Many TCP/IP experts have an IT mentality, not a plant-floor mindset, so they misunderstand what users want or modify existing systems in ways that hurt the industrial user in an effort to improve the system according to other criteria.

«o users still need to learn about the technology and watch over the shoulders of the experts. Ask questions, and make sure the IT experts learn how you view the problem.

Openness

Ethernet TCP/IP systems provide an open network platform, but high-level application standards are still in flux. TCP/IP is often viewed as a false open standard because its higher layers are proprietary. Modbus/TCP and some of the new encapsulations of òeviceNet, Foundation Fieldbus, and Profibus will help in this area by providing interfaces that will allow different protocols to communicate with each other. But that still leaves a lot of application standards that are not interoperable.

Many of these network architectures encapsulate other protocols, but the interoperability does not extend to the physical and transport layers. This prevents the various buses from communicating with each other. So there is still a great deal of work to be done in this area.

Flexibility

Just about anything is possible with global TCP/IP, but the reliability of its performance depends on the skill of the implementer. However, there is still a need for a more industrial and optimized sensor bus.

As data requirements increase, hybrid and direct Ethernet systems will become commonplace. High-level sensors with serial ports are already being linked over Ethernet. The protocols are transported transparently on top of TCP/IP and delivered to a host, which in some cases is unaware that they were carried over a LAN.

Singularity Institute for Artificial Intelligence

2009-07-10T06:26:00.000-07:00

Purdue, Japanese Researchers To Create More Human-Like Robots

2009-06-29T05:04:00.000-07:00

Purdue University is leading a four-year project to enable humanoid robots to move more like people and adapt quickly to new situations so that they can complete a variety of tasks they weren't specifically programmed to perform.

"We are trying to give humanoid robots the ability to behave and move more like human beings, to have the skill-learning capabilities of humans," said C.S. George Lee, a Purdue professor of electrical and computer engineering who specializes in robotics.

Purdue will collaborate with researchers from the Advanced Institute of Science and Technology in Japan, which leads the world in humanoid-robot research.

"What we are going to try to do is capture the essence of how people learn movement skills," said Howard Zelaznik, a Purdue professor of health and kinesiology.

The work is funded with a four-year, $900,000 grant from the National Science Foundation's Information Technology Research program.

Humans are able to automatically combine a series of basic movements, such as pushing, lifting or grasping, to perform new tasks on the fly.

"For example, if I asked you to open a door and you were carrying two bags of groceries, you would know how to do that the first time through because you have in your repertoire the flexibility to combine old skills into new ones," Zelaznik said. "We'd like to see whether we can figure out if there is a computationally reasonable way for a robot to take a set of skills and combine them into new skills rather efficiently, flexibly and quickly."

Humanoid robots are robots that resemble people. A popular example of such robots is Honda Motor Co.'s "ASIMO," which walks upright, has two arms, two legs and a head.

Although today's humanoid robots represent an engineering feat, they do not move the way people do.

"They are very stiff and mechanical," Lee said.

One important reason to teach humanoid robots how to quickly learn new movements is so that they will be better able to assist people.

"Imagine that a person in a wheelchair has just dropped his or her keys under the wheelchair, and the robot wasn't programmed specifically to retrieve them from that location," Zelaznik said. "We are trying to figure out how best to make that robot adaptable so that it can learn new skills quickly."

The Purdue team, which includes four doctoral students, will use specialized equipment to record human movements in three dimensions.

Tiny coiled wire "receivers" will be placed around certain body parts, such as fingers and arms, as a person moves in a low-level magnetic field. As the person moves, these coiled wire receivers will induce a current, which will be tracked by laboratory computers. Lee and Zelaznik will then be able to see the basic movement patterns and hope to use that information to build mathematical models to make robots move more like people.

The ultimate goal is to create software that enables robots to combine several of the most "primitive" skills to perform more complex movements.

"We are not trying to make the robot perfect," Zelaznik said. "People are not perfect. When we move, we are variable, we are imprecise, we make errors. We don't exactly do the same thing time in and time out. We believe it is this imperfection that allows us the capability to be flexible."

C. S. George Lee, a Purdue professor of electrical and computer engineering, from left, and Howard Zelaznik, a professor of health and kinesiology, work with doctoral student Nicole Rheaume to study how humans learn movement skills. Rheaume draws s circle with a pen equipped with a tiny coiled wire "receiver." A nearby magnet induces a low-level magnetic field. As Rheaume moves the pen, the wire coil induces an electrical current that enables researchers to track the movements. The ultimate goal is to create software that enables robots to combine several of the most "primitive" skills to perform more complex movements, much as people are able to combine a series of basic movements to perform specific tasks. (Purdue News Service photo/David Umberger)

The Coming Superbrain

2009-06-20T23:14:00.000-07:00

Mountain View, Calif. — It’s summertime and the Terminator is back. A sci-fi movie thrill ride, “Terminator Salvation” comes complete with a malevolent artificial intelligence dubbed Skynet, a military R.&D. project that gained self-awareness and concluded that humans were an irritant — perhaps a bit like athlete’s foot — to be dispatched forthwith.

Sam Weber

The notion that a self-aware computing system would emerge spontaneously from the interconnections of billions of computers and computer networks goes back in science fiction at least as far as Arthur C. Clarke’s “Dial F for Frankenstein.” A prescient short story that appeared in 1961, it foretold an ever-more-interconnected telephone network that spontaneously acts like a newborn baby and leads to global chaos as it takes over financial, transportation and military systems.

Today, artificial intelligence, once the preserve of science fiction writers and eccentric computer prodigies, is back in fashion and getting serious attention from NASA and from Silicon Valley companies like Google as well as a new round of start-ups that are designing everything from next-generation search engines to machines that listen or that are capable of walking around in the world. A.I.’s new respectability is turning the spotlight back on the question of where the technology might be heading and, more ominously, perhaps, whether computer intelligence will surpass our own, and how quickly.

The concept of ultrasmart computers — machines with “greater than human intelligence” — was dubbed “The Singularity” in a 1993 paper by the computer scientist and science fiction writer Vernor Vinge. He argued that the acceleration of technological progress had led to “the edge of change comparable to the rise of human life on Earth.” This thesis has long struck a chord here in Silicon Valley.

Artificial intelligence is already used to automate and replace some human functions with computer-driven machines. These machines can see and hear, respond to questions, learn, draw inferences and solve problems. But for the Singulatarians, A.I. refers to machines that will be both self-aware and superhuman in their intelligence, and capable of designing better computers and robots faster than humans can today. Such a shift, they say, would lead to a vast acceleration in technological improvements of all kinds.

The idea is not just the province of science fiction authors; a generation of computer hackers, engineers and programmers have come to believe deeply in the idea of exponential technological change as explained by Gordon Moore, a co-founder of the chip maker Intel.

In 1965, Dr. Moore first described the repeated doubling of the number transistors on silicon chips with each new technology generation, which led to an acceleration in the power of computing. Since then “Moore’s Law” — which is not a law of physics, but rather a description of the rate of industrial change — has come to personify an industry that lives on Internet time, where the Next Big Thing is always just around the corner.

Several years ago the artificial-intelligence pioneer Raymond Kurzweil took the idea one step further in his 2005 book, “The Singularity Is Near: When Humans Transcend Biology.” He sought to expand Moore’s Law to encompass more than just processing power and to simultaneously predict with great precision the arrival of post-human evolution, which he said would occur in 2045.

In Dr. Kurzweil’s telling, rapidly increasing computing power in concert with cyborg humans would then reach a point when machine intelligence not only surpassed human intelligence but took over the process of technological invention, with unpredictable consequences.

Profiled in the documentary “Transcendent Man,” which had its premier last month at the TriBeCa Film Festival, and with his own Singularity movie due later this year, Dr. Kurzweil has become a one-man marketing machine for the concept of post-humanism. He is the co-founder of Singularity University, a school supported by Google that will open in June with a grand goal — to “assemble, educate and inspire a cadre of leaders who strive to understand and facilitate the development of exponentially advancing technologies and apply, focus and guide these tools to address humanity’s grand challenges.”

Not content with the development of superhuman machines, Dr. Kurzweil envisions “uploading,” or the idea that the contents of our brain and thought processes can somehow be translated into a computing environment, making a form of immortality possible — within his lifetime.

That has led to no shortage of raised eyebrows among hard-nosed technologists in the engineering culture here, some of whom describe the Kurzweilian romance with supermachines as a new form of religion.

The science fiction author Ken MacLeod described the idea of the singularity as “the Rapture of the nerds.” Kevin Kelly, an editor at Wired magazine, notes, “People who predict a very utopian future always predict that it is going to happen before they die.”

However, Mr. Kelly himself has not refrained from speculating on where communications and computing technology is heading. He is at work on his own book, “The Technium,” forecasting the emergence of a global brain — the idea that the planet’s interconnected computers might someday act in a coordinated fashion and perhaps exhibit intelligence. He just isn’t certain about how soon an intelligent global brain will arrive.

Others who have observed the increasing power of computing technology are even less sanguine about the future outcome. The computer designer and venture capitalist William Joy, for example, wrote a pessimistic essay in Wired in 2000 that argued that humans are more likely to destroy themselves with their technology than create a utopia assisted by superintelligent machines.

Mr. Joy, a co-founder of Sun Microsystems, still believes that. “I wasn’t saying we would be supplanted by something,” he said. “I think a catastrophe is more likely.”

Moreover, there is a hot debate here over whether such machines might be the “machines of loving grace,” of the Richard Brautigan poem, or something far darker, of the “Terminator” ilk.

“I see the debate over whether we should build these artificial intellects as becoming the dominant political question of the century,” said Hugo de Garis, an Australian artificial-intelligence researcher, who has written a book, “The Artilect War,” that argues that the debate is likely to end in global war.

Concerned about the same potential outcome, the A.I. researcher Eliezer S. Yudkowsky, an employee of the Singularity Institute, has proposed the idea of “friendly artificial intelligence,” an engineering discipline that would seek to ensure that future machines would remain our servants or equals rather than our masters.

Nevertheless, this generation of humans, at least, is perhaps unlikely to need to rush to the barricades. The artificial-intelligence industry has advanced in fits and starts over the past half-century, since the term “artificial intelligence” was coined by the Stanford Universitycomputer scientist John McCarthy in 1956. In 1964, when Mr. McCarthy established the Stanford Artificial Intelligence Laboratory, the researchers informed their Pentagon backers that the construction of an artificially intelligent machine would take about a decade. Two decades later, in 1984, that original optimism hit a rough patch, leading to the collapse of a crop of A.I. start-up companies in Silicon Valley, a time known as “the A.I. winter.”

Such reversals have led the veteran Silicon Valley technology forecaster Paul Saffo to proclaim: “never mistake a clear view for a short distance.”

Indeed, despite this high-technology heartland’s deeply held consensus about exponential progress, the worst fate of all for the Valley’s digerati would be to be the generation before the generation that lives to see the singularity.

“Kurzweil will probably die, along with the rest of us not too long before the ‘great dawn,’ ” said Gary Bradski, a Silicon Valley roboticist. “Life’s not fair.”

Japan membuat sex robots

2009-06-06T23:33:00.000-07:00

A Japanese firm has produced a 38 cm (15 inch) tall robotic girlfriend that kisses on command, to go on sale in September for around $175, with a target market of lonely adult men.

Using her infrared sensors and battery power, the diminutive damsel named “EMA” puckers up for nearby human heads, entering what designers call its “love mode”.

“Strong, tough and battle-ready are some of the words often associated with robots, but we wanted to break that stereotype and provide a robot that’s sweet and interactive,” said Minako Sakanoue, a spokeswoman for the maker, Sega Toys.

“She’s very lovable and though she’s not a human, she can act like a real girlfriend.”

EMA, with stands for Eternal Maiden Actualization, can also hand out business cards, sing and dance, with Sega hoping to sell 10,000 in the first year.

Japan, home to almost half the world’s 800,000 industrial robots, envisions a $10-billion market for artificial intelligence in a decade.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 7

2009-05-31T19:13:00.000-07:00

7. FUTURE WORK

This work describes our current approach to constructing robust

distributed sensor networks for a few applications. It suggests several

areas for future work including enhancing our testbed and protocols,

applying them to additional applications, and understanding

how to build sensor networks.

We have several planned changes to our testbed hardware. Most

importantly, we plan to move to a different radio by RF Monolithics

and to use a UCB Mote as the packet controller. The packetlevel

controller of our Radiometrix RPC was very helpful for rapid

development, but this revised approach will give us complete control

over the MAC protocol.

We have now explored diffusion performance both in simulation

and with testbed experiments. In-network aggregation shows

qualitatively the same results in both evaluations (Section 6.1). A

next step is to use the experiments to parametrize the simulations.

In this work we were repeatedly challenged by the difficulty

in understanding what was going on in a network of dozens of

physically distributed nodes. Our current environment augments

the radio network with a separate wired network for experimental

data collection, but much more work is needed in developing

analysis tools for these networks. Tools are needed to report the

changing radio topology, observe collision rates and energy consumption,

permit more flexible logging, and accurately synchronize

node clocks. We have begun work on in-network monitoring

tools [40], but more work is needed.

Appropriate MAC protocols for sensor networks is a continuing

challenge. In spite of published work in this area [3, 33] and

ongoing activities, a freely available, energy aware MAC protocol

remains needed. We and others are currently exploring alternatives

here; we hope solutions will be forthcoming.

A balance of control and data traffic is particularly important in

bandwidth-constrained systems such as sensor networks. Several

known techniques to constrain control traffic exist for soft-state

protocols in wired networks [24, 31, 36]; these approaches need

to be applied to our system.

We have explored two applications of sensor networks and collaborated

on other applications, but many other applications remain.

One interesting direction is to explore how collaborative

signal processing interacts with in-network processing and filters.

Finally, although we focus on wireless sensor networks, the

techniques we develop are also relevant to wired sensor networks.

Wired connections greatly reduce bandwidth constraints and and

eliminate power constraints, but attribute-based naming can reduce

system complexity by decoupling data sources and sinks, and

in-network processing may reduce latency and improve scalability.

Although prior systems have separately used these abstractions

for virtual information systems, a future direction is to apply

them to large, wired sensor networks that are coupled with the

physical world.

8. CONCLUSION

This paper has described an approach to distributed systems

built around attribute-named data and in-network processing. By

using attributes with external meaning (such as sensor type and

geographic location) at the lowest levels of communication, this

approach avoids multiple levels of name binding common to other

approaches. Attribute-named data in turn enables in-network processing

with filters, supporting data aggregation, nested queries

and similar techniques that are critical to reduce network traffic

and conserve energy. We evaluated the effectiveness of these techniques

by quantifying the benefits of in-network processing for

data aggregation and nested queries. In one experiment we found

that aggregation reduces traffic by up to 42% and nested queries

reduces loss rates by 15–30%. Although aggregation has previously

been studied in simulation, these experiments are the first

evaluation of these techniques in an operational testbed. These

approaches are important in the emerging domain of wireless sensor

networks where network and power resource constraints are

fundamental.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 6

2009-05-29T03:41:00.000-07:00

6. EVALUATION

The approaches described in this paper are useful if they can

be efficiently implemented and improve the energy-efficiency of

distributed systems such as sensor nets. In Section 5 we described

several applications that employ these techniques. In this section,

we measure the benefits of aggregation and nested queries and

verify raw matching performance.

6.1 Aggregation benefits

In Section 5.1, we argued that it is relatively easy to build sensor

network applications using attribute-based naming, and innetwork

filters. In earlier work, we have observed that in-network

aggregation is important to the performance of data diffusion [23].

In this section, we validate these results with an actual implementation

of a simple surveillance application using attribute-based

names and filters.

We examined in-network aggregation in our testbed of 14 PC/104

sensor nodes distributed on two floors of ISI (Figure 7). These sensors

are connected by Radiometrix RPC modems (off-the-shelf,

418 MHz, packet-based radios that provide about 13kb/s throughput)

with 10dB attenuators on the antennas to allow multi-hop

communications in our relatively confined space. The exact topology

varies depending on the level of RF activity, and the network

is typically 5 hops across.

To evaluate the effect of aggregation we placed a sink on one

side of the topology (“D” at node 28) and then placed data sources

on the other side (“S” at nodes 25, 16, 22, and 13), typically 4 hops

apart. All sources generate events representing the detection of

Figure 7: Node positions in our sensor testbed. Light nodes

(11, 13, 16) are on the 10th floor; the remaining dark nodes

are on the 11th floor. Radio range varies greatly depending on

node position, but the longest stable link was between nodes 20

and 25.

some object at the rate of one event every 6 seconds. For experiment

repeatability events are artificially generated, rather than

taken from a physical sensor and signal processing. Each event

generates a 112 bytes message and is given sequence numbers

that are synchronized at experiment start.2 All nodes were configured

with aggregation filters that pass the first unique event and

suppress subsequent events with identical sequence numbers. Although

this scenario abstracts some details of a complete sensor

network (for example, real signal processing may have different

sensing delays), we believe it captures the essence of the networking

component of multi-sensor aggregation.

We would like to compare the energy expended per received

event. Unfortunately, we cannot measure that directly for two reasons.

First, we do not have hardware to directly measure energy

consumption in a running system. Second, we have previously

observed that choice of MAC protocol can completely dominate

energy measurements. In low power radios, MAC protocols that

do not sleep periodically are dominated by the amount of time

spent listening, regardless of choice of protocol. Thus energyconscious

protocols like PAMAS [32] or TDMA are necessary for

long-lived sensor networks. We are currently experimenting with

power-aware MAC approaches.

Although we currently cannot measure energy consumption on

an appropriate MAC, we can estimate the effectiveness of reducing

traffic for MACs with different duty cycles. A simple model

of energy consumption is:

"!$#%!'&(*)+#$),&(*-.#/-

where and # define the relative power and time spent listening,

receiving, and sending and is defined as the required listen

duty cycle (the fraction of time the radio must be listening to

receive all traffic destined to it). We found our sensor network

contained pockets of severe congestion, but in the aggregate, radios

listen:receive:send times were about 1:3:40. Relative energy

0An operational sensor network would use timestamps instead of

sequence numbers. Both require synchronization, but time can

be synchronized globally with GPS or NTP. We use sequence

numbers because at the time of this experiment we had not synchronized

our clocks. Experimentally, other than synchronization

overhead, sequence numbers and timestamps are equivalent.

500

1000

1500

2000

2500

3000

3500

0 1 2 3 4 5

Bytes sent by diffusion

(per received distinct event)

Number of Sources

With suppression

Without suppression

Figure 8: Bytes sent from all diffusion modules, normalized to

the number of distinct events, for varying numbers of sources.

consumption of listen:receive:send has been measured at ratios

from 1:1.05:1.4 to 1:2:2.5 [37]. For simplicity, assume energy

consumption ratios of 1:2:2. With these parameters, energy usage

for nodes with a duty cycle of 1 are completely dominated by

energy spent listening. At duty cycle of 22% half of the energy is

spent listening. Duty cycles of 10% begin to be dominated by send

cost. Duty cycle for most radios today is 100%, but TDMA radios

such as in WINSng nodes [29] may have duty cycles of 10–15%

for non-base-stations. This analysis illustrates the importance of

energy-conserving MAC protocols.

Since we cannot directly measure energy per event, Figure 8

measures bytes sent from diffusion in all nodes in the system normalized

to the number of distinct events received. Each point in

this graph represents the mean of five 30-minute experiments with

95% confidence intervals. Performance with one source is basically

identical with and without suppression (this form of aggregation).

As expected, suppression requires less data per event with

multiple sources than experiments without suppression. With suppression

the amount of traffic is roughly constant regardless of

the number of sources. This application-specific data aggregation

shows the benefit of in-network processing. It also shows that diffusion

is useful for point-to-multipoint communication, since traffic

represents both data and control traffic. Comparing traffic with

and without suppression shows that suppression is able to reduce

traffic by up to 42% for four sources. The network exhibits very

high loss rates at that level of traffic. Our current MAC is quite unsophisticated,

performing only simple carrier detection and lacking

RTS/CTS or ARQ. Since all messages are broken into several

27-byte fragments, loss of a single fragment results in loss of the

whole message, and hidden terminals are endemic to our multihop

topology, this MAC performs particularly poorly at high load.

We are currently working on a better MAC protocol.

We can confirm these results with a simple traffic model. We

approximate all messages as 127B long and add together interest

messages (sent every 60s and flooded from each node), reinforcement

messages (sent on the reinforced path between the sink and

each source), simple data messages (9 out of every 10 data messages,

sent only on the reinforced path, and either aggregated or

not), and exploratory data messages (1 out of every 10 data messages,

sent from each source and flooded in turn from each node,

again

possibly aggregated). If data messages are not aggregated,

each source incurs the cost of the full path, while if data messages

are aggregated after the first hop each incurs one hop cost to the

aggregation point and then one message will travel on to the sink.

Summing the message cost and normalizing per event we expect

aggregation to provide a flat 990B/event independent of the number

of sources, and we expect bytes sent per event to increase from

990 to 3289B/event without aggregation as the number of sources

rise from 1 to 4.

The shape of this prediction matches our experimental results,

but in absolute terms it underpredicts the B/event of aggregation

and overpredicts the 4-source/no-aggregation case. We believe

these differences are due to MAC-layer collisions in the experiment

that tend to drive bytes-per-event to the middle. Only 55–

80% of events generated in the experiment were delivered to the

sink, so bytes-per-event in less congested portions of the experiment

(with one source or aggregation) is high because traffic is

normalized over fewer events. On the other hand, with four sources

and no aggregation, we believe collisions happen very near the

data sources and so the aggregate amount of data sent is lower

that predicted. In addition, we sometimes observe longer paths in

experiment than we expected.

These experimental measurements of aggregation are also useful

to validate our previous simulation experiments that consider a

wider range of scenarios. Previous simulation studies have shown

that aggregation can reduce energy consumption by a factor of 3–

in a large network (50–250 nodes) with five active sources and

five sinks (Figure 6b from [23]). Although care must be used in

comparing energy to bytes sent, a 3–5-fold energy savings with

five sources is much greater than the 42% (or 1.7-fold) traffic savings

we observe with four sources. The primary reason for this

difference is differences in ratio of exploratory to data messages

in these systems. Exploratory messages (called low-data rate messages

in [23]) are used to select good gradients and so are flooded

to all nodes. Data messages (called high-rate messages in [23])

are sent only on reinforced gradients forming a path between the

sources and sinks. In simulation the ratio of exploratory to data

messages sent from a source was about 1:100 (exploratory messages

were sent every 50s, data every 0.5s, messages were modeled

as 64B packets). In our testbed this ratio was about 1:10

(exploratory messages every 60s, data every 6s, with messages

of roughly the same size). Increasing this ratio in experiment

was not possible given our small radio bandwidth (13kb/s rather

than 1.6Mb/s in simulation) while keeping reasonable experimental

running times. This large difference in ratios is consistent with

the large difference in energy or traffic savings.

A potential disadvantage of data aggregation is increased latency.

The effect of aggregation on latency is strongly dependent

on the specific, application-determined aggregation algorithm. The

algorithm used in these experiments does not affect latency at all,

since we forward unique events immediately upon reception and

then suppress any additional duplicates (incurring only the additional

negligible cost of searching for duplicates). Other aggregation

algorithms, such as those that delay transmitting a sensor

reading with the hope of aggregating readings from other sensors,

can add some latency. Understanding aggregation and sensor fusion

algorithms is an important area of future work.

Although we have quantified the benefits of in-network aggregation

in a specific application, aggregation is one example of

in-network processing. Other examples range from simple data

0 1 2 3 4 5

audio events succesfully delivered (%)

number of light sensors

1-level

2-level

Figure 9: Percentage of audio events successfully delivered to

the user.

caching to collaborative signal processing. As our experiments

show, not only do attribute matching and filters make aggregation

and similar services easy to provide, they also enable noticeable

performance improvements.

6.2 Nested query benefits

In Section 5.2 we suggested that nested queries could reduce

network costs and latency, and we argued that nested queries could

be implemented using attributes and filters. To validate our claim

about the potential performance benefits of this implementation

we measure the performance of an application that uses nested

queries against one that does not.

The application is similar to that described in Section 5.2 and

Figure 6: a user requests acoustic data correlated with (triggered

by) light sensors. We reuse our PC/104 testbed shown in Figure

7 placing the user “U” at node 39, the audio sensor “A” at

node 20, and light sensors “L” at nodes 16, 25, 22, and 13. It is

one hop from the light sensors to the audio sensor, and two hops

from there to the user node. To provide a reproducible experiment

we simulate light data to change automatically every minute on

the minute. Light sensors report their state every 2s (no special

attempt is made to synchronize or unsynchronize sensors). Audio

sensors generate simulated audio data each time any light sensor

changes state. Light and audio data messages are about 100 bytes

long.

Figure 9 shows the percentage of light change events that successfully

result in audio data delivered to the user. (Data points

represent the mean of three 20-minute experiments and show 95%

confidence intervals.) The total number of possible events are the

number of times all light sources change state and a successful

event is audio data delivered to the user. These delivery rates

do not reflect per-hop message delivery rates (which are much

higher), but rather the cumulative effect of sending best-effort data

across three or five hops for nested or flat queries, respectively.

This system is very congested, and as described above (Section

6.1), our primitive MAC protocol exaggerates the impact of

congestion. Missing events translate into increased detection latency.

Although a sensor network could afford to miss a few events

(since they would be retransmitted in the next time the sensor is

measured), these loss rates are unacceptably high for an operaSet

A: interest Set B: data

class IS interest class IS data

task EQ “detectAnimal” task IS “detectAnimal”

confidence GT 50 confidence IS 90

latitude GE 10.0 latitude IS 20.0

latitude LE 100.0 longitude IS 80.0

longitude GE 5.0 target IS “4-leg”

longitude LE 95.0

target IS “4-leg”

Figure 10: Attributes used for matching experiments.

tional system.

However, this experiment sharply contrasts the bandwidth requirements

of nested and flat queries. Even with one sensor the

flat query shows significantly greater loss than the nested query

because both light and audio data must travel to the user. Both

flat and nested queries suffer greater loss when more sensors are

present, but the one-level query falls off further. Comparing the

delivery rates of nested queries with one-level queries shows that

localizing the data to the sensors is very important to parsimonious

use of bandwidth. In an uncongested network we expect

that nested queries would allow operation with a lower level of

data traffic than one-level queries and so would allow a lower radio

duty cycle and a longer network lifetime.

6.3 Runtime

costs of matching

Attribute matching is used in all communication between sensors,

filters, and applications in our system. Although technology

trends suggest rapid improvement in processor performance,

price, and size, sensor nodes may chose to hold performance constant

and leverage technology through reduced price and size, so

run-time performance must be considered. A second constraint is

memory storage, particularly in very small implementations.

To evaluate matching performance we examined the cost of

matching data from a sensor. The basic matching in that case compares

an 8-element interest against a 6-element data (attributes are

shown in Figure 10). To evaluate the cost of larger data objects

we increased the number of attributes in the data from 6 to 30 attributes.

This experiment was done on our PC/104 sensor node

with a 66MHz AMD 486-class CPU. To evaluate the cost of a single

match we measured cost of many matches (5000 for matching

or 10,000 for the non-matching case) in a loop and normalized, repeating

this experiment 1000 times to avoid undue system effects

such as interrupts. The order of attributes in each set is randomized

each experiment. We also show 95% confidence intervals, although

they are always less than 5% of the mean. Although memory

caching will cause this approach to underestimate the cost of

a match, the basic trends it identifies should be applicable to operational

systems.

Our expectation is that the cost of matching is linear with the

number of elements. This is confirmed in Figure 11 that shows

the cost of matching as the number of attributes in one attribute

set increases in different ways. The two lowest lines (no-match/IS

and no-match/EQ) show the case where one of the attributes in

set A is not matched by those in set B (specifically, the confidence

value in set B is changed from 90 to 10). Because the two-way

matching algorithm tests the formals in set A first, the incremental

cost of additional attributes in set B is fairly small in this case,

and it is insensitive to the type of attribute added. If the failing

formal was in set B we would expect the cost to be higher (mid-

100

200

300

400

500

600

700

800

900

0 5 10 15 20 25 30 35

uSec per match

number of attributes in set B

match/IS

match/EQ

no-match/IS

no-match/EQ

Figure 11: Matching performance as the number of attributes

grow.

way between the measured data).

The two higher lines (match/IS and match/EQ) show the cost

of matching when all attributes succeed. The difference in cost

of additional attributes in these lines shows the cost of additional

matching. In the match/EQ line all additional attributes are formals

(additions of the “class EQ interest” attribute), so each new

attribute must be matched against set A. For match/IS, additional

attributes are actuals (repetitions of ‘extra IS “foo” ’) that must be

examined but do not require searching.

Although our current implementation is completely unoptimized,

the absolute performance of these operations is quite reasonable.

At 500

s/match for small attribute sets our quite slow PC/104

can match 2000 sets per second. Although quite slow by Internet

router standards, this is reasonable for sensor networks where

we expect high-level events to happen with frequencies of 10Hz

or less.

Finally, these measurements suggest several potential optimizations

to matching performance. Segregating actuals from formals

can reduce search time (since formals cannot match other formals

there is no need to compare them). Attributes could be statically or

dynamically optimized to move the attributes least likely to match

to the front. We plan to explore these kinds of optimizations in the

future.

6.4 Experiment Discussion

These experiments have provided new insight into sensor network

operation, building substantially on our prior simulation studies

[23].

These experiments are first examination of nested queries and

matching performance. They suggest that the CPU overhead of

matching should not be a constraint for reasonably powerful sensor

nodes and that nested queries can greatly reduce contention by

localizing data movement.

These experiments have explored low-bandwidth operation. Previous

simulation studies of sensor networks often have not used

the low-bandwidth radios we see in actual sensor-network hardware.

Protocols and scenarios behave qualitatively different at

10–20kb/s for sensor networks rather than the 3–12Mb/s common

to wireless 802.11 LANs. Even with our early operational experience

in small-scale demonstrations and testing, we did not appreciate

the difficulty of operating a 14-node sensor network at a

relatively high utilization. Our observations suggest two areas of

future work: first, sensor networks must adapt to local node densities

(we are beginning to explore this area [11]). Second, more

work is needed to understand how diffusion’s parameters map to

different needs, particularly the trade-offs between overhead and

reliability present in the frequency of exploratory messages, interests,

and reinforcements. Finally, the diffusion applications we

currently use operate in an open loop; feedback and congestion

control are needed.

Two aspects of radio propagation proved unexpectedly difficult.

First, some experiments seemed to show asymmetric links (communication

was fine in one direction but poor or impossible in

the other). Diffusion does not currently work well with asymmetric

links; we are considering how to best revise it. Second, some

links provided only intermittent connectivity. A future direction

for diffusion might send similar data over multiple paths to gain

robustness when faced with low-quality links. Current simulation

models, even with statistical noise, do not adequately reflect these

observed propagation characteristics.

Finally, we were generally happy with our approach to attribute

naming and filters. It was reasonably easy to build and adapt our

sample applications and debugging software.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 5

2009-05-14T09:20:00.000-07:00

5. APPLICATION TECHNIQUES FOR

SENSOR NETWORKS

We next consider application techniques in more detail. These

techniques illustrate how topology-independent low-level naming

and in-network processing can be used to build efficient applications

for sensor networks. The first approach we examine is filterdriven

data aggregation, an example of how in-network processing

can reduce data traffic to conserve energy. We also consider two

approaches to provide nested queries where one sensor cues another.

Finally, we briefly describe several other applications that

have been implemented.

5.1 Innetwork

data aggregation

An anticipated sensor application is to query a field of sensors

and then take some action when one or more of the sensors is activated.

For example, a surveillance system could notify a biologist

if an animal enters a region. Coverage of deployed sensors will

overlap to ensure robust coverage, so one event will likely trigger

multiple sensors. All sensors will report detection to the user,

but communication and energy costs can be reduced if this data is

aggregated as it returns to the user. Data can be aggregated to a

binary value (there was a detection), an area (there was a detection

in quadrant 2), or with some application-specific aggregation

(seismic and infrared sensors indicate 80% chance of detection).

Although details of aggregation can be application-specific, the

common systems problem is the design of mechanisms for establishing

data dissemination paths to the sensors within the region,

and for aggregating responses. Consider how one might

implement this kind of data fusion in a traditional network with

topologically-assigned low-level node names. First, in order to

determine which sensors are present in a given region, a binding

service must exist which, given a geographical region, lists the

node identifiers of sensors within that region. Once these sensors

are tasked, an election algorithm must dynamically elect one or

more network nodes to aggregate the data and return the result to

the querier.

Instead, our architecture allows us to realize this using opportunistic

data aggregation. Sensor selection and tasking is achieved

by naming nodes using geographic attributes. As data is sent

from the sensors to the querier, intermediate sensors in the return

path identify and cache relevant data. This is achieved by

running application-specific filters. These intermediate nodes can

then suppress duplicate data by simply not propagating it, or they

may slightly delay and aggregate data from multiple sources. We

are also experimenting with influencing the dynamic selection of

aggregation points to minimize overall data movement.

Opportunistic data aggregation benefits from several aspects of

our approach. Filters provide a natural approach to inject application-

specific code into the network. Attribute naming and matching

allow these filters to remain inactive until triggered by relevant

data. A common attribute set means that filters incur no network

costs to interact with directory or mapping services.

In prior work we analyzed the performance of diffusion with

and without aggregation through simulation [23]. In Section 6.1

we evaluate our implementation of this over real sensor nodes and

validate our initial results with laboratory tests.

5.2 Nested queries

Real-world events often occur in response to some environmental

change. For example, a person entering a room is often correlated

with changes in light or motion, or a flower’s opening with

the presence or absence of sunlight. Multi-modal sensor networks

can use these correlations by triggering a secondary sensor based

on the status of another, in effect nesting one query inside another.

Reducing the duty cycle of some sensors can reduce overall energy

consumption (if the secondary sensor consumes more energy

than the initial sensor, for example as an accelerometer triggering a

GPS receiver) and network traffic (for example, a triggered imager

generates much less traffic than a constant video stream). Alternatively,

in-network processing might choose the best application

of a sparse resource (for example, a motion sensor triggering a

steerable camera).

user

Figure 6: Two approaches to implementing nested queries.

Squares are initial sensors, gray circles are triggered sensors,

and the large circle is the user. Thin dashed lines represent

communication to initial sensors; bold lines are communication

to the triggered sensor.

Figure 6 shows two approaches for a user to cause one sensor

to trigger another in a network. In both cases we assume sensors

know their locations and not all nodes can communicate directly.

Part (a) shows a direct way to implement this: the user queries the

initial sensors (small squares), when a sensor is triggered, the user

queries the triggered sensor (the small gray circle). The alternative

shown in part (b) is a nested, two-level approach where the

user queries the triggered sensor which then sub-tasks the initial

sensors. This nested query approach grew out of discussions with

Philippe Bonnet and embedded database query optimization in his

COUGAR database [5].

The advantage of a nested query is that data from the initial sensors

can be interpreted directly by the triggered sensor, rather than

passing through the user. In monitoring applications the initial

and triggered sensors would often be quite close to each other (to

cover the same physical area), while the user would be relatively

distant. A nested query localizes data traffic near the triggering

event rather than sending it to the distant user, thus reducing network

traffic and latency. Since energy-conserving networks are

typically low-bandwidth and may be higher-latency, reduction in

latency can be substantial, and reductions in aggregate bandwidth

to the user can mean the difference between an overloaded and

operational network. The challenges for nested queries are how to

robustly match the initial and triggered sensors and how to select

a good triggered sensor if only one is desired.

Implementation of direct queries is straightforward with attributeaddressed

sensors. The user subscribes to data for initial sensors

and when something is detected he requests the status of the triggered

sensor (either by subscribing or asking for recent data). Direct

queries illustrate the utility of predefined attributes identifying

sensor types. Diffusion may also make use of geography to optimize

routing.

Nested queries can be implemented by enabling code at each

triggered sensor that watches for a nested query. This code then

sub-tasks the relevant initial sensors and activates its local triggered

sensor on demand. If multiple triggered sensors are acceptable

but there is a reasonable definition of which one is best (perhaps,

the most central one), it can be selected through an election

algorithm. One such algorithm would have triggered sensors

nominate themselves after a random delay as the “best”, informing

their peers of their location and election (this approach is inspired

by SRM repair timers [17]). Better peers can then dispute

the claim. Use of location as an external frame of reference defines

a best node and allows timers to be weighted by distance to

minimize the number of disputed claims.

In Section 6.2 we evaluate nested queries with experiments in

our testbed.

5.3 Other applications

In addition to these approaches we have explored at ISI, our

system has been used by several other research efforts.

Researchers at Cornell have used our system to provide communication

between an end-user database and application that represents

and visualizes a sensor field and query proxies in each sensor

node [5]. This application used attributes to identify sensors

running query proxies and to pass query byte-codes to the proxies.

They also originated the idea of using a nested approach for

nested queries. Future work includes understanding what network

information is necessary for database query optimization and alternative

approaches for nested queries.

Researchers at BAE Systems and Pennsylvania State University

have used our system for collaborative signal processing. BAE

systems contributed signal processing code and systems integration,

while PSU provided sensor fusion algorithms [8]. The combined

system used our system to communicate data between sensors

using named data and diffusion. At the time our filter architecture

was not in place; interesting future work is to evaluate how

sensor fusion would be done as a filter.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 4

2009-05-13T18:30:00.000-07:00

4. IMPLEMENTATIONS

There are currently three implementations of all or part of this

architecture. Our current reference implementation SCADDS diffusion

version 3 provides all components. MIT-Lincoln Labs has

implemented “declarative routing” that provides attribute matching

but no filters [14]. Both of these implementations run on Linux

on desktop PCs and PC/104-based sensor nodes [11] (embedded

x86 machines, ours with a 66MHz CPU and 16MB of RAM and

flash disk, Figure 3(a)), and on WINSng 1.0 sensor nodes [29]

(Windows-CE-based nodes with custom low-power radios, Figure

3(b)). We have also implemented micro-diffusion, a bare subset

of these services designed to run on Motes with tiny 8-bit processors

and only 8KB of memory (Figure 3(c)).

Source code to our implementations can be found on our web

site http://www.isi.edu/scadds.

All of our implementations build upon a simple radio API that

supports broadcast or unicast to immediate neighbors. Neighbors

must have some kind of identifier, but it is not required to be

persistent. We can use persistent identifiers (for example, Ethernet

MAC addresses) or operate with ephermally assigned identifiers

[16].

4.1 Basic diffusion APIs

Our reference implementation includes C++ Network Routing

APIs summarized in Figure 4 (see [13] for a complete specification

and example source code). The APIs define a publish/subscribe

approach to data handling. To receive data, nodes subscribe to particular

set of attributes. A subscription results in interests being

sent through the network and sets up gradients. A callback function

is then invoked whenever relevant data arrives at the node.

Applications that generate information publish that fact, and

then send specific data. The attributes specified in the publish call

must match the subscription. If there are no active subscriptions,

published data does not leave the node. As a further optimization

sensor nodes may wish to avoid generating data that has no takers.

In this case the application would subscribe for subscriptions and

would be informed when subscriptions arrive or terminate.

Filter-specific APIs are shown in Figure 5. A filter is primarily

a callback procedure (the cb specified in addFilter) that is called

when matching data arrives. Rather than operate only on attribute

vectors, filters are given direct access to messages that include

identifiers for the previous and next immediate destinations. We

(a) Our PC/104 node (b) WINSng 1.0 node (c) UCB Rene Mote

Figure 3: Diffusion operational platforms.

handle NR::subscribe(NRAttrVec *subscribeAttrs,

const NR::Callback * cb);

int NR::unsubscribe(handle subscription_handle);

handle NR::publish(NRAttrVec *publishAttrs);

int NR::unpublish(handle publication_handle);

int NR::send(handle publication_handle,

NRAttrVec *sendAttrs);

Figure 4: Basic diffusion API.

handle addFilter(NRAttrVec *filterAttrs,

int16_t priority, FilterCallback *cb);

int NR::removeFilter(handle filter_handle);

void sendMessage(Message *msg, handle h,

int16_t agent_id = 0);

void sendMessageToNext(Message *msg, handle h);

Figure 5: Filter APIs.

are currently evaluating using this additional level of control to

optimize diffusion, for example using geographic information to

avoid flooding exploratory interests. We expect these interfaces to

be extended as we gain more experience with how filters are used

and what information they require.

Finally, these APIs have been designed to favor an event-driven

programming style, although they have been successfully used in

multi-threaded environments such as WINSng 1.0. We have targeted

event-driven programming to avoid synchronization errors

and to avoid the memory and performance overheads of multithreading.

Evidence is growing that event-driven software is well

suited to embedded programming, particularly on very memoryconstrained

platforms [21].

Also we allow filters and applications to run in the same or different

memory address spaces from each other and the diffusion

core. Single-address space operation is necessary for very small

sensor nodes that lack memory protection and as a performance

optimization. Multiple address spaces may be desired for robustness

to isolate filters of different applications from each other.

4.2 MITLL

declarative routing

Dan Coffin helped define the basic diffusion APIs (Figure 4

and [13]) and developed an independent implementation in MITLincoln

Lab’s Declarative Routing system [14]. In principle all

applications that do not depend on filters will run over either implementation.

This level of portability has been demonstrated with

Cornell’s query proxy [5] that runs over both implementations.1

Declarative routing and data diffusion are far more similar than

they are different. Both name data rather than end-nodes. Differences

are in how routes and transmission are optimized, both by

applications and the core system. The primary difference is that

declarative routing does not include filters to allow applications

to directly influence diffusion. We see filters as a critical necessary

component to enable general in-network data processing.

Second, Lincoln Lab’s declarative routing includes direct support

for energy and geography-aided routing so that routes are selected

to avoid energy-poor nodes and generally move “towards” a target

geographic area. In our current implementation interests and

exploratory messages are flooded through the network before gradients

are set up for direct communication. We are currently exploring

using filters to optimize diffusion (avoiding flooding) with

geographic information [39].

4.3 Microdiffusion

Micro-diffusion is a subset of our approach implemented on

very small processors (8-bit CPU, 8KB memory). It is distinguished

by its extremely small memory footprint and a complementary

approach for deployment to our full system.

Micro-diffusion is a subset of our full system, retaining only

gradients, condensing attributes to a single tag, and supporting

only limited filters. As a result it adds only 2050 bytes of code and

106 bytes of data to its host operating system. (By comparison,

our full system requires a daemon with static sizes of 55KB code,

8KB data, and a library at 20KB code, 4KB data.) Micro-diffusion

is implemented as a component in TinyOS [21] that adds 3250B

code and 144B of data (including support for radio and a photo

sensor), so the entire system runs in less than 5.5KB of memory.

Micro-diffusion is statically configured to support 5 active gradients

and a cache of 10 packets of the 2 relevant bytes per packet.

No changes were required to our diffusion implementation, although

the port required one change to the application to accommodate

a case where MIT’s implementation was less strict about

attribute matching.

Although

reduced in size, the logical header format is compatible

with that of the full diffusion implementation and we are implementing

software to gateway between the implementations. Although

we do not currently provide filters in micro-diffusion, they

are an essential component of enabling in-network aggregation in

diffusion, and we plan to add them. We intend to leverage on the

ability to reprogram motes over the air [21] to program filters dynamically.

Motes and micro-diffusion can be used in regions where there is

need for dense sensor distribution, such as distributing photo sensors

in a room to detect change in light or temperature sensors for

fine grained sensing. They provide the necessary sensor data processing

capability, with the ability to use diffusion to communicate

with less resource-constrained nodes (for example, PC/104-class

nodes). Motes can also be used to provide additional multi-hop

capability under adverse wireless communication conditions.

We thus envisage deployment of a tiered architecture with both

larger and smaller nodes. Less resource-constrained nodes will

form the highest tier and act as gateways to the second tier. The

second tier will be composed of motes connected to low-power

sensors running micro-diffusion. Most of the network “intelligence”

is programmed into the first tier. Second-tier nodes will

be controlled and their filters programmed from these more capable

nodes.

4.4 Implementation discussion

We draw two observations from our experiences with these implementations.

First, the range of diffusion implementations suggests

that both the ideas and the code are portable since there

are three independent implementations (our main implementation,

micro-diffusion, and MIT-LL’s declarative routing) and our primary

implementation runs on multiple platforms (PC/104s and

WINSng 1.0 as of June 2001, with ports in progress to two new

radios and platforms). The requirements for diffusion are quite

modest in terms of CPU speed (a 15MHz 32-bit processor is sufficient),

memory (a few megabytes supports diffusion, an OS, and

applications), and radio (10–20kb/s bandwidth is sufficient). Several

low-power radio designs have packet sizes as small as 30B.

We require moderate size packets (100B or more) and use code

for fragmentation and reassembly when necessary. Second, microdiffusion

demonstrates that it is possible to implement a subset of

diffusion on an embedded processor. A common preconception

is that fully custom protocols are needed for embedded systems;

these observations suggest that use of diffusion should not be precluded

due to size or complexity.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 3

2009-05-12T03:07:00.000-07:00

3. ARCHITECTURE

Our communications architecture is based on three components:

directed diffusion, matching rules, and filters. Directed diffusion

is used to disseminate information in the distributed system. Data

is managed as a list of attribute-value-operation tuples. Matching

rules identify when data has arrived at its destination, or if intermediate

filters should process the data. This approach to naming

comes together to provide an external framework relevant to the

application. These components balance the generic services of

diffusion and matching rules with application-provided attributes

and filters. We next describe each of these components.

3.1 Directed Diffusion

Directed diffusion is a data communication mechanism for sensor

networks [23]. Data sources and sinks use attributes to identify

what information they provide or are interested in. The goal of

directed diffusion is to establish efficient n-way communication

between one or more sources and sinks. Directed diffusion is a

data-centric communication paradigm that is quite different from

host-based communication in traditional networks. To describe

the elements of diffusion, we take the simple example of a sensor

network designed for tracking animals in a wilderness refuge.

Suppose that a user in this network would like to track the

movement of animals in some remote sub-region of the park. In

directed diffusion, this tracking task represents an interest. An

interest is a list of attribute-value pairs that describe a task using

some task-specific naming scheme (we describe the details of

these attributes in the next section). Intuitively, attributes describe

the data that is desired by specifying sensor types and possibly

some geographic region. They are then used to identify and contact

all relevant sensors. We use the term sink to denote the node

that originates an interest and therefore is the destination of data.

The interest is propagated from neighbor-to-neighbor towards

sensor nodes in the specified region. A key feature of directed diffusion

is that every sensor node is task-aware—by this we mean

that nodes store and interpret interests, rather than simply forwarding

them along. In our example, each sensor node that receives an

interest remembers which neighbor or neighbors sent it that interest.

To each such neighbor, it sets up a gradient. A gradient

represents both the direction towards which data matching an interest

flows, and the status of that demand (whether it is active or

inactive and possibly the desired update rate). After setting up a

gradient, the sensor node redistributes the interest to its neighbors.

When the node can infer where potential sources might be (for example,

from geographic information or existing similar gradients),

the interest can be forwarded to a subset of neighbors. Otherwise,

it will simply broadcast the interest to all of its neighbors.

When a sensor node that matches the interest is found, the application

activates its local sensors to begin collecting data. (Prior to

activation we expect the node’s sensors would be in a low-power

mode). The sensor node then generates data messages matching

the interest. In directed diffusion, data is also represented using

an attribute-based naming scheme. A sensor node that generates

such an event description is termed a source.

Data is cached at intermediate nodes as it propagates toward

sinks. Cached data is used for several purposes at different levels

of diffusion. The core diffusion mechanism uses the cache to suppress

duplicate messages and prevent loops, and it can be used to

preferentially forward interests. (Since the diffusion core is primarily

interested in an exact match, as an optimization, hashes

of attributes can be computed and compared rather than complete

data.) Cached data is also used for application-specific, in-network

processing. For example, data from detections of a single object

by different sensors may be merged to a single response based on

sensor-specific criteria.

The initial data message from the source is marked as exploratory

and is sent to all neighbors for which it has matching gradients.

If the sink has multiple neighbors, it chooses to receive

subsequent data messages for the same interest from a preferred

neighbor (for example, the one which delivered the first copy of

the data message). To do this, the sink reinforces the preferred

neighbor, which, in turn reinforces its preferred upstream neighSink

Event

Source

Interests

(a) Interest propagation

Sink

Event

Source

Gradients

(b) Initial gradients set

Sink

Event

Source

reinforced path

Figure 1: A simplified schematic for directed diffusion.

bor, and so on. Finally, if a node on this preferred path fails, sensor

nodes can attempt to locally repair the failed path. The sink

may also negatively reinforce its current preferred neighbor if another

neighbor delivers better (lower latency) sensor data. This

negative reinforcement propagates neighbor-to-neighbor, removing

gradients and tearing down and existing path if it is no longer

needed [23]. Negative reinforcements suppress loops or duplicate

paths that may arise due to network dynamics.

After the initial exploratory data message, subsequent messages

are sent only on reinforced paths. Periodically the source sends

additional exploratory data messages to adjust gradients in the

case of network changes (due to node failure, energy depletion,

or mobility), temporary network partitions, or to recover from lost

exploratory messages. Recovery from data loss is currently left

to the application. While simple applications with transient data

(such as sensors that report their state periodically) need no additional

recovery mechanism, we are also developing retransmission

scheme for applications that transfer large, persistent data objects.

Even this simplified description points out several key features

of diffusion, and how it differs from traditional networking. First,

diffusion is data-centric; all communication in a diffusion-based

sensor network uses interests to specify named data. Second, all

communication in diffusion is neighbor-to-neighbor or hop-byhop,

unlike traditional data networks with end-to-end communication.

Every node is an “end” in a sensor network. A corollary to

this previous observation is that there are no “routers” in a sensor

network. Each sensor node can interpret data and interest messages.

This design choice is justified by the task-specificity of

sensor networks. Sensor networks are not general-purpose communication

networks. Third, nodes do not need to have globally

unique identifiers or globally unique addresses for regular operation.

Nodes, however, do need to distinguish between neighbors.

Fourth, because individual nodes can cache, aggregate, and more

generally, process messages, it is possible to perform coordinated

sensing close to the sensed phenomena. It is also possible to perform

in-network data reduction, thereby resulting in significant

energy savings. Finally, although our example describes a particular

usage of the directed diffusion paradigm (a query-response

type usage, see Figure 1), the paradigm itself is more general than

that; we discuss several other example applications in Section 5.

3.2 Attribute Tuples and Matching Rules

Diffusion messages and application interests are composed of

attribute-value-operation tuples. Attributes are identified by unique

one-way match:

given two attribute sets

and

for each attribute

where

op is a formal

matched = false

for each attribute

where

key

key and

op is an actual

val compares with

val using

op, then matched = true

if not matched then return false (no match)

return true (successful one-way match)

Figure 2: Our one-way matching algorithm.

keys drawn from a central authority. (In practice we implement

these as simple 32-bit numbers and assume out-of-band coordination

of their values, just as Internet protocol numbers are assigned.)

Attributes implicitly have a data format (integers and

floating point values of different sizes, strings, and uninterpreted

binary data are currently supported).

The operation field defines how data messages and interests interact.

Operations are the usual binary comparisons (EQ, NE, LE,

GT, LE, GE, corresponding to equality, inequality, less than, etc.),

“EQ ANY” (which matches anything), and IS. “IS” allows users

to specify an actual (literal or bound) value, while all the other operations

specify formal (a comparison or unbound) parameters for

comparison. A one-way match compares all formal parameters of

one attribute set against the actuals of the others (Figure 2). Any

formal parameter that is missing a matching actual in the other

attribute set causes the one-way match to fail (for example, “confidence

GT 0.5” must have an actual such as “confidence IS 0.7”

and would not match “confidence IS 0.3”, “confidence LT 0.7”,

or “confidence GT 0.7”). Two sets of attributes have a complete

match if one-way matches succeed in both directions. In other

words, attribute sets

and

match if the one-way match algorithm

succeeds from both

and

This matching style is similar to the rules used in other attributebased

languages (for example, Linda [9] and INS [1]), but we add

two-way matching and a range of operators in addition to equality.

When multiple attributes and operators are present they are effectively

“anded” together; all formals must be satisfied for a match

to be successful. This approach strikes a balance between ease of

implementation and flexibility. The simple bounded set of operators

can be implemented in tens of lines of code and yet supports,

for example, rectangular regions.

To see how diffusion and attribute matching interact, we continue

the example from Section 3.1 where a user asks a sensor

network to track four-legged animals. The user’s query translates

into an interest with the attributes (type EQ four-legged-animalsearch,

interval IS 20ms, duration IS 10 seconds, x GE –100, x LE

200, y GE 100, y LE 400). Also, an implicit “class IS interest”

attribute is added to identify this message as an interest (as opposed

to data). This interest specifies five conditions: detection of

animals in a particular region specified by a rectangle. It also provides

information about how frequently data should be returned

and how long the query should last.

Sensors in the network are programmed with animal search routines

(either by pre-programming at deployment time or by downloading

mobile code). Such sensors would watch for interests

in animals by expressing interests about interests with attributes

(class EQ interest, type IS four-legged-animal-search, x IS 125,

y IS 220). When the user’s interest arrives at the sensor it would

activate its sensor using the parameters provided (duration and interval)

and reply if it detects anything.

When the sensor detects something the data message would include

attributes (type IS four-legged-animal-search, instance IS

elephant, x IS 125, y IS 220, intensity IS 0.6, confidence IS 0.85,

timestamp IS 1:20, class IS data). This message satisfies the original

interest. It encodes as attributes additional information about

what was seen and what confidence the sender has in its detection.

This example illustrates the details of a specific query. It shows

how named data provides a convenient way of encoding information,

and how geometry and well-known attributes allow simple

matching rules work for this application. Although this example

uses several attributes, some applications may use only a subset of

these methods, omitting geographic constraints (in a small sensor

network) or using a single attribute (when there is only one sensor

type). We have found that these primitives provide good building

blocks for a range of applications; we describe these in Section 5.

Although matching is reasonably powerful, it does not perfectly

cover all scenarios or tasks. Simple matching in these cases can

approximate what is required, and application-specific code can

further refine the choice. For example, perfect rectangles aligned

with the coordinate system are insufficient to describe arbitrary

geometric shapes. Non-rectangular shapes can be accomplished

either by multiple queries, or by using the smallest bounding rectangle

and having the application ignore requests inside the rectangle

but outside the required region. Similarly, applications can

use general attributes that are clarified with sub-attributes or parameters

(type IS animal-search, subtype IS four-legged). Filters

(described next) also allow applications to influence processing.

3.3 Filters

Filters are our mechanism for allowing application-specific code

to run in the network and assist diffusion and processing. Applications

provide filters before deployment of a sensor network, or

in principle filters could be distributed as mobile code packages at

run-time. Filters register what kinds of data they handle through

matching; they are then triggered each time that kind of data enters

the node. When invoked, a filter can arbitrarily manipulate the

message, caching data, influencing how or where it is sent onward,

or generating new messages in response. Filters have access to internal

information about diffusion, including gradients and lists of

neighbor nodes.

Filters are typically used for in-network aggregation, collaborative

signal processing, caching, and similar tasks that benefit from

control over data movement. In addition to these applications, we

have found them very useful for debugging and monitoring.

Continuing our example, a filter can be used to suppress concurrent

detections of four-legged animals from different sensors.

It would register interest in detection interests and data with attributes

(type IS four-legged-animal-search). It could then record

what the desired interval is, then allow exactly one reply every

interval units of time, suppressing replies from other sensors. A

more sophisticated filter could count the number of detecting sensors

and add that as an additional attribute, or it could generate

some kind of aggregate “confidence” rating in some applicationspecific

manner. In this example filtering may discard some data,

but by reducing unnecessary communication it will greatly extend

the system’s operational lifetime.

We describe some application of filters in Section 5, and quantify

the benefits of aggregation in one scenario in Section 6.1.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 2

2009-05-08T19:43:00.000-07:00

2. RELATED WORK

Our work builds on prior work in attribute-based naming, innetwork

processing, and sensor networks.

2.1 Attributebased

naming systems

There has been a large amount of work on attribute-based naming,

both for general purpose use over Internet-style networks, for

special domains (such as the web), and as an internal structuring

mechanism for services.

Research and industry have developed numerous attribute-based

naming systems layered on top of general-purpose networks. Univers

and yellow-pages naming at the University of Arizona [6, 28]

were designed to provide service discovery for groups of computers

(for example, print to an unloaded postscript-capable printer).

Like our work, they include attributes and operators, but they build

over standard Internet protocols for communications. Commercial

attribute-based naming systems such as X.500 [10] and LDAP [38]

also operate over Internet or Internet-like routing and provide a

primarily

hierarchical organization. Dependence on IP-level addressing

and routing limits adds substantial overhead when applying

these systems to highly resource-constrained environments

such as sensor networks. (For example, some approaches to service

location for smart spaces require services for IP assignment,

IP-level routing, host name lookup, and service registration and

lookup.) With end-to-end processing only, these systems also do

not provide in-network processing.

As an alternative to providing attribute-based naming for enduser

use, several systems have proposed attribute-based communications

for structuring distributed systems. Linda proposed structuring

distributed programs using several CPUs around an attributeindexed

common memory called a tuple space [9]. For the S/Net

implementation this was the basic communication mechanism, but

proposed implementations assume uniform and rapid communications

between all processors. Later systems such as ISIS [4]

and the Information Bus [27] provide a “publish and subscribe”

approach where information providers publish information and

clients subscribe to attribute-specified subsets of that information.

These systems are designed to be robust to failure, but again assume

reasonably fast, plentiful, and expensive communications

between nodes. These approaches are not directly applicable to

resource-constrained sensor networks. They do not use applicationspecific,

in-network processing since all processes are reasonably

close to each other; when they do use processing (such as at a

wide-area gateway) it is manually configured.

More specific still is work that proposes attribute-based primitives

as solutions to specific problems. SRM first suggested using

named data as the fundamental data unit for reliable multicast

communication, and it demonstrated this approach with a

distributed whiteboard [17]. Our work is inspired by these approaches,

but it differs by providing a wider range of matching

operators (rather than just equality), adding in-network processing

to leverage CPU-communications trade-offs for sensor networks,

and operating directly over low-level (hop-by-hop) communications

protocols instead of the Internet multicast infrastructure.

2.2 Innetwork

processing

Recent work in active networks [34] and active services [2]

has examined ways to provide in-network processing for the Internet.

Sample applications include information transcoding, network

monitoring, and caching. This work is built over an Internetlike

infrastructure, often augmented with an extended run-time environment,

and assumes nodes are individually addressable. We

instead build directly over hop-by-hop communications primitives

and identify data instead of nodes. Our work differs from active

services in that we assume that communications costs between

nodes vary greatly while currently proposed active services assume

roughly equivalent distances between all service-providing

nodes. We differ from active networks primarily in the target

domain: we target sensor networks where bandwidth is limited,

energy is expensive, and compute power is comparatively plentiful

and inexpensive. Instead, active networks typically considers

Internet-like domains where bandwidth is plentiful, the ratio of

compute power to bandwidth is much lower, and energy is not an

issue. All of these approaches distribute application-specific code

throughout the network, raising questions about code safety and

portability. These problems are not central to some sensor networks

(such as those that are devoted to a single application), but

more complex networks would benefit from active-networks-style

execution environments to support in-place upgradability.

Recent work on adaptive web caching [25] and peer-to-peer file

sharing systems such as Freenet [12] explore application-specific,

hop-by-hop processing. Unlike active networks and our work,

these approaches emphasize protocols designed for a particular

application. In addition, our work runs directly over hop-by-hop

communication rather than over a virtual network layered over the

Internet.

2.3 Sensornetworkspecific

systems

Sensor networking research has seen increasing activity in the

last few years, with advances in sensor node and radio hardware [33,

29]. This work has been instrumental in clarifying the trade-off

between computation and communication and the need for innetwork

processing. Our focus on in-network processing is motivated

by this work. This work is however based on topographicallyaddressed

sensor nodes; the primary difference in our work is the

use of attribute-based naming for structure and data diffusion for

communication.

Internet ad hoc routing (Broch et al. survey several protocols [7]

such as DSR and AODV) can also be used in sensor networks.

Since ad hoc routing recreates IP-style addressing, it would require

some kind of directory service to locate sensors, unlike our

approach where they are named by attributes. Ad hoc routing does

not support in-network processing.

Jini is an example of a resource discovery system built over

Internet protocols [35]. It provides a directory service and uses

Java to distribute processing to user nodes, making it well suited

to a local-area network with high bandwidth and multicast. By

contrast, we distribute the directory across the network and allow

application-specific processing at intermediate system nodes,

addressing problems of resource-constrained, multi-hop wireless

networks. The Ninja Service Discovery Service [15] locates XMLnamed

objects through a network of collaborating servers but again

targets high bandwidth local-area resources.

The Piconet work has presented fundamental advances in energyconserving

network communications for networks of devices [3].

Their work focuses on static hierarchies of networked devices,

concentrators, and hosts. While similar to our tiered architecture

with full and micro-diffusion, they do not consider attributenamed

data or dynamic in-network processing.

SPIN evaluates several variants of flooding for wireless sensor

networks [20]. Data in SPIN is identified by application-specific

metadata that appears to assume individual sensors are addressable.

We instead use attributes to name data alone; globally unique

identifiers are not used. SPIN does not consider application-specific

in-network processing.

The Intentional Naming System is an attribute-based name system

operating in an overlay network over the Internet [1]. Its use

of attributes as a structuring mechanism and a method to cope with

dynamically locating devices is similar to our approach in motivation

and mechanism. The primary difference is that we assume

that attribute-based communication (data diffusion) is the basic

communications primitive (above hop-by-hop messaging), while

they construct an overlay network over an IP-based Internet. Architecturally

this implies that we distribute name matching across

many small communications nodes while they manage names at a

few resolvers that cooperatively manage parts of the namespace.

Finally, the details of matching are different in the two systems.

Their work provides a sophisticated hierarchical attribute matching

procedure. Our approach is much more modest by comparison

(targeting smaller embedded devices) but adds comparative operators

in addition to equality.

LEACH analyzes the performance of cluster-based routing mechanism

with in-network data compression [19]. They emphasize

how intermediate-range communication via cluster-heads and how

compression can reduce energy consumption. Their in-network

compression is one example of the kind of in-network processing

that we would like to support. They do not specify how flows and

opportunities for aggregation would be activated, while our work

focuses on the naming mechanisms that allow such activity.

DataSpace describes an attribute based naming mechanism for

querying physical objects that produce and store local data [22].

The DataSpace is divided into smaller administrative and logical

datacubes, which are logically grouped into dataflocks. Dataflocks

are addressed at the network level through IPv6 multicast addresses

that correspond to their geographic coordinates, and their values

for certain attributes that serve as network indices. Query results

may involve aggregation of more specific queries addressed to

sub-datacubes. At a high-level their naming approach is similar

to ours, but instead of mapping attributes and geometry to a very

large number of multicast groups we route directly on attributes

themselves without this indirection. In addition, they do not explore

in-network processing.

The COUGAR device database system proposes distributing

database queries across a sensor network as opposed to moving all

data to a central site [5]. Sensor data is represented as an Abstract

Data Type attribute, the public interface to which corresponds to

specific signal processing functions supported by a sensor type.

They then perform joins or aggregation in the network as specified

by a centrally computed query plan. Their work is common

with ours in its emphasis on in-network processing, and our study

of nested queries (Section 5.2) was inspired by their work. The

primary difference between their work in ours is how placement

of in-network processing is determined. We emphasize the use of

filters and nested queries to enable either ad-hoc or sensor-specific

placement of in-network processing, while COUGAR centrally

translates the query and assigns processing to the distributed system,

incurring overhead to centrally collect network information

for query optimization.

Declarative Routing from MIT’s Lincoln Labs is closest to our

work [14]. The publish/subscribe-oriented API we use was defined

in collaboration with them [13] and they have developed

an independent implementation. The primary difference between

their work and ours is our focus on in-network processing. We

evaluate their work more completely in Section 4.2.

Building Efficient Wireless Sensor Networks with LowLevel Naming - 1

2009-05-01T20:16:00.001-07:00

ABSTRACT

In most distributed systems, naming of nodes for low-level communication

leverages topological location (such as node addresses)

and is independent of any application. In this paper, we investigate

an emerging class of distributed systems where low-level communication

does not rely on network topological location. Rather,

low-level communication is based on attributes that are external

to the network topology and relevant to the application. When

combined with dense deployment of nodes, this kind of named

data enables in-network processing for data aggregation, collaborative

signal processing, and similar problems. These approaches

are essential for emerging applications such as sensor networks

where resources such as bandwidth and energy are limited. This

paper is the first description of the software architecture that supports

named data and in-network processing in an operational,

multi-application sensor-network. We show that approaches such

as in-network aggregation and nested queries can significantly affect

network traffic. In one experiment aggregation reduces traffic

by up to 42% and nested queries reduce loss rates by 30%. Although

aggregation has been previously studied in simulation, this

paper demonstrates nested queries as another form of in-network

processing, and it presents the first evaluation of these approaches

over an operational testbed.

1. INTRODUCTION

In most distributed systems, naming of nodes for low-level com-

􀀀 This work was supported by DARPA under grant DABT63-99-

1-0011 as part of the SCAADS project, NSF grant ANI-9979457

as part of the SCOWR project, and was also made possible in part

due to support from Cisco Systems.

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are

not made or distributed for profit or commercial advantage and that copies

bear this notice and the full citation on the first page. To copy otherwise, to

republish, to post on servers or to redistribute to lists, requires prior specific

permission and/or a fee.

munication leverages topological location (such as node addresses)

and is independent of any application. Typically, higher-level,

location-independent naming and communication is built upon these

low-level communication primitives using one or more levels of

(possibly distributed) binding services that map higher-level names

to topological names and sometimes consider application-specific

requirements.

An example of this is the Internet where IP addresses provide

the low-level names suitable for routing. IP addresses are assigned

topologically: the addresses for nodes that are topologically proximate

are usually drawn from the same address prefix [18]. (By

topology, we mean logical connectivity as distinct from physical

geography.) This topological assignment is essential for scaling

the routing system and was carried forward into IPv6 [30]. DNS

provides a text-based hierarchical node naming system [26] that

is implemented using IP. Above this system, the web and search

engines provide a document and object naming system, and content

distribution networks add geographic or application-level constraints.

As an alternative, systems such as Jini [35] and INS [1]

layer different approaches for resource discovery above IP for networks

of devices.

In this paper, we investigate an emerging class of distributed

systems where low-level communication does not rely on network

topological location. Rather, low-level communication is based

on names that are external to the network topology and relevant to

the application; names can be based on capabilities such as sensor

types or geographic location. Such an approach to naming allows

two kinds of efficiencies. First, it eliminates the overhead

of communication required for resolving name bindings. Second,

because data is now self-identifying, it enables activation of

application-specific processing inside the network, allowing data

reduction near where data is generated.

These two benefits do not apply to the Internet as a whole,

where, by comparison, bandwidth is plentiful, delay is low, and

throughput (router processing capability) is the primary constraint.

Technology trends suggest, however, that these conditions are reversed

in wireless sensor networks. Sensor networks are predicated

on the assumption that it will be feasible to have small formfactor

devices containing significant memory resources, processing

capabilities, and low-power wireless communication, in addition

to several on-board sensors. In sensor networks processing

time

per bit communicated is plentiful (CPUs are fast and bandwidths

low), but bandwidth is dear. For example, in one scenario

Pottie and Kaiser observe that 3000 instructions could be executed

for the same energy cost of sending a bit 100m by radio [29]. This

environment encourages the use of computation to reduce communication.

In that context, fewer levels of naming indirection and

the use of in-network, application-specific message processing (as

opposed to opaque packet forwarding) are essential to the design

of sensor networks.

Our thesis, then, is that the resource constraints of wireless sensor

networks can be better met by an attribute-based naming system

with an external frame of reference than by traditional approaches.

There have been many attribute-based naming schemes,

but most build over an underlying topological naming scheme

such as IP [28, 10, 6, 38, 4, 27, 1, 20, 22]. Multiple layers of naming

may not be a bottleneck with a few or even tens of nodes, but

the overhead becomes unreasonable with hundreds or thousands

of nodes that vary in availability (due to movement and failures).

However, constrained, application-specific domains such as sensor

networks can profit by eliminating multiple layers and naming

and routing data directly in application-level terms. Efficient attribute

naming is based on external frames of reference such as

pre-defined attributes and geography. Pre-defined sensor types reduce

the levels of run-time binding and geographic-aided routing

reduces resource consumption.

In addition to attribute-based naming, application-specific, innetwork

processing is essential in resource-constrained sensor networks.

As suggested by the above trade-off between computation

and communication, application-specific caching, aggregation,

and collaborative signal processing should occur as close as

possible to where the data is collected. Such processing depends

on attribute-identified data to trigger application-specific filters,

pre-defined attributes and data types to allow pre-deployment of

these filters, and hop-by-hop processing of the data. This kind of

processing is similar to Active Networks [34], but differs by operating

in the constrained, bandwidth-poor environment of sensor

networks where an integrated, application-specific solution is appropriate.

As an illustration of attribute-based naming and in-network processing

in a sensor network, consider a wireless monitoring system

with a mixture of light or motion sensors (constantly vigilant

at low-power), and a few higher-power and higher-bandwidth sensors

such as microphones or cameras. To conserve energy and

bandwidth the audio sensors would be off (or not recording) at

most times, except when triggered by less expensive light sensors.

Instead this computation can be distributed throughout the

network. Queries (user requests) are labeled with sensor type (audio

or light) known to the system at design time. Queries diffuse

through the network to be handled by nodes with matching sensors

in the relevant geographic region. The application will hear

from whatever relevant sensors respond. Moreover, the decision

of one sensor triggering another can be moved into the network

to be handled directly between the light and audio sensors. The

alternative Internet-based architecture would have a central directory

of active sensors and a central application that interrogates

this database, monitors specific sensors, and then triggers others.

Our goal is to eliminate the communication costs of maintaining

this central information to provide more robust and long-lived networks

in spite of changing communications, moving nodes, and

limited battery power. (We explore exactly how these approaches

work in Section 5 and quantify potential savings in Section 6.)

In this paper, we demonstrate that there exists a simple architecture

that uses topology-independent naming for low-level communications

to achieve flexible, yet highly energy efficient application

designs. The key contributions of this work are therefore:

Identifying the building-blocks of this architecture, specifically

an attribute-based naming scheme with flexible matching

rules grounded in a shared framework of attributes (such

as sensor types and geography).

Showing how this approach to naming enables applicationspecific,

in-network processing such as localized data aggregation,

and to quantify these benefits in a running system.

In previous work [23], we have discussed the low-level communication

primitives that constitute directed diffusion. This work

focused on understanding the design space of the network protocols

underlying directed diffusion. It also evaluated their performance

through simulation, finding that scalability is good as numbers

of nodes and traffic increases. However, this work did not

develop the software architecture necessary for realizing attributes

and in-network processing in an operational system (for example,

it employed a simplified attribute scheme and hard-coded aggregation

methods). In addition, simulations necessitate approximating

environmental effects such as radio propagation, and many parameters

of those simulations were not set to match the sensor networking

hardware that is only now becoming available. By contrast,

this paper evaluates the design questions concerning naming

and in-network processing encountered in deploying a sensor network,

and it presents the first experimental results of data diffusion

in a testbed (reflecting the details of an implementation such

as non-idealized radios, propagation, MAC protocols, etc.).

Numerous early systems have developed attribute-based naming

systems, for general use [28, 10, 6], as an approach to software

design [9, 4, 27, 17, 25] and for sensor networks [1, 22]. Our

work is unique in that it replaces rather than augments the underlying

networking routing layers, and that it provides matching rules

that allow efficient implementation and yet are expressive enough

to cover a wide range of applications, and provides in-network

processing.

Big Bang Theory

2009-04-24T20:55:00.000-07:00

James asked:

Philosophy, huh? Pah! You guys crack me up. Okay, I'll admit the need for the contemplation of the various ideas as detailed by this site...and human conciousness in general. But come now, Kollidge Kids. The "basic facts" of existence are:

1. There was "nothing".
2. "Bang".
3. There was everything.

Ain't there something wrong here? We all understand that "everything" is created...from other "things". Everything. No exceptions. Except.... Everything.

Seems to me, the entire human population should huddle together one week out of the year and contemplate the utter nonsense of the fact of "our" existence. Why we don't walk around muttering "We came from nothing. We came from nothing. We came from nothing." is a mystery in itself.

So the philosophs and others never seem to take up that question. Even the essays which I've read here ignore that question. (Although, it's true that I ain't read `em all yet. :} ) Because if you accept that premise (and by golly, either you accept it or you go "mad"), than any other concept of existence of possible also. Anything. Mind Reading. Teleportation. Living rocks. Stars as sentient beings. Humans as microorganisms in a vastly greater "reality". Unending universes. And so on.

It is humorous though. The only way human conciousness can exist is by ignoring the true reality of our existence. Or at best, simply remaining in awe of the whole shebang. Never forgetting to awe is the most important thing to remember.

As far as I can tell, the only way to deal with it is to not think about it. You got any better ideas?

What cracks me up is that you don't notice an equally big problem staring you in the face every time you look at the bathroom mirror in the morning.

Let's play a game of suppose. Suppose there were an explanation of why there is something rather than nothing. That wouldn't be very interesting or helpful, if under the description of 'something' came any possibility under the sun, including a universe consisting entirely of empty space. There still remains the urgent question, Why is there thisuniverse, rather than some other possible universe? Why are things this way, rather than one of the myriad other possible ways things might have been?

But now suppose — if you are still with me — that we had an answer to that question. The philosopher Leibniz thought he had, in his conception of God as the one unique being that contains the reason for its own existence, who necessarily chose to create the 'best of all possible worlds'. — Huh!

As I was saying, we've got something when there might have been nothing. We have got this world, when there might have been some other world. Now, you are looking in that bathroom mirror, and you think, 'Hang on a second, why is there thisface in the mirror? Why am I me? Why is there such an individual as I?'

Leibniz's theory implies there had to be a James S. Gagliardi matching your precise physical and mental description, because that is what was required to make this the best of all possible worlds. But where does I come into the picture?

I think that this is a question that deserves to be pondered at least once a day, not one week every year. Not for very long, though. I suggest a couple of minutes, at the maximum. Then you can think about how to fill the rest of your day. I suggest that an hour set aside for all the other fascinating problems of philosophy would be very good and rewarding use of your God-given talents.

Geoffrey Klempner

John asked:

Hi, I'm new to philosophy and I'm sure this has been discussed many times, so please bear with me!.

There are two possibilities: Either the universe has always existed (which is presumably impossible) or there was a time when the universe did NOT exist and then all that matter was created out of nothing (which, according to our current knowledge of physics, is equally impossible as matter cannot derive from nothing!).

Of course, if the universe was 'created' then this begs the question: 'Who was the Creator?', then 'who created the creator's creator?', etc. — Any suggestions?

The first thing to point out is that neither of the initial possibilities you mention is a logical impossibility. There is no logical impossibility in the notion of a universe whose history can be traced further and further back, at no point reaching a 'first event in the history of the universe'. Neither is there any logical impossibility in the idea of a universe whose history traces back to a specific date, before which there 'was nothing'.

You say that the latter is inconsistent with our current knowledge of physics. That would not be sufficient for ruling it out if the alternative was thought to be logically impossible. The correct conclusion would be that current physics must be wrong.

Given that the alternative of a universe with an infinite history is not logically impossible, it is still remains open to the physicist to argue that the ultimate physical 'constant' is not matter but probabilistic laws according to which at every time and at every place there is a non-zero probability of matter appearing where previously there was no matter. The laws have existed for an infinite time, matter has only existed for a finite time.

I am not talking about any specific physical theory (such as quantum mechanics), but rather possible physical theories, or theories that might hold in some logically possible world.

However, the issue of whether the history of the universe is finite or infinite is arguably not the problem that brings God into the picture.

In the Cosmological argument for the existence of God, the problem is not time but causal dependency. A universe stretching infinitely back in time is no more difficult to conceive than a universe stretching infinitely into the future. The regress becomes vicious only when we look to events in the past as an adequate explanation of how things are now. A perpetually conditional explanation is no explanation at all.

So the argument goes, There has to be a Creator who exists outside the infinite series of causes and effects, who timelessly 'causes' the whole infinite series to exist. The Creator does not exist in time, so the question of when the Creator came into existence does not arise. The Creator is 'cause of itself', so the question of who created the Creator does not arise.

I am not defending this argument, only expounding it!

I myself do not understand what it means to say that something is the 'cause of itself' or 'exists outside of time'. However, if the straight choice is between a proposition which is logically impossible and a proposition whose meaning one does not fully understand, then reason dictates that we have to opt for the second alternative.

Geoffrey Klempner

Kurt asked:

This may be a very convoluted question...earth is in a solar system, our solar system is in a galaxy, our galaxy is one of many galaxies contained within a very large universe. What is that universe filling? and if god (be it man/ woman or both or neither) made all of this who are god's parents and who are their parents etc?

Your metaphysics have led you immediately into, what is called in philosophy, an infinite regress. To make any progress this line of questioning will have to be abandoned. The range of empirical statements you make up to "universe" can be dealt with by the sciences of astronomy, physics and mathematics. The problems arise when your sequence enters into the metaphysics of space, time and God; problems that philosophy has battled with since ancient times.

Deducing from your knowledge of the empirical world, you have fallen into the trap of making God in the image of man, hence God requires parents, and so on. The absurdity of this line of reasoning becomes obvious when you require to house, clothe and nourish God, to say nothing of his involvement in sexual activity!! Even religion does not make such claims. Taking the religious line that God is a 'spirit,' although I have only a hazy notion of what this means, I can tolerate it because it seems to have possibilities beyond what I understand. However, being a physiologist I know more about humans than most people, and to propose that God is a human would be a self-revealing absurdity.

You have actually touched on the frustrating problem of origins, a problem which defeats science and opens up a range of difficult to prove philosophical and religious theories. Both physics and biology are held suspect simply because they have had to invent their own ideas of origins, the Big Bang in the case of physics, and the accidental formation of proteins in mud pools in the case of biological origins. Neither of them to my mind is very convincing. Even when we put aside the origins and start half-way up the ladder, as both physics and biology do, to say that there is such a thing as an evolutionary process which depends on a sequence of fortuitous accidents seems on the face of it an absurd proposition.

As for the Big Bang, where did the first primaeval atom come from? Unfortunately science is tied to the matter myth and all its theories are blinkered by this. Whereas philosophy can offer a range of possibilities beyond the paralysing confines of alleged material reality. Scientists are not mystics and they will always seek to explain strange phenomena in terms of empirical/ material solutions. They are reluctant to admit that answers can be obtained from anything other than naive reality, and if answers to phenomenal events cannot be produced, they are simply suspended in the confident belief that there will eventually be a 'natural' solution to the event, whatever that means.

You ask what the universe is filling, again, there is something here to do with naive reality in your concept. Stated simply you seem to be making the suggestion that there is a vast amount of matter which has to be contained in something, a bit like a gas filling a spherical flask. The question is asking: What is the flask like? What is the flask made of to be able to contain all this matter and restrict its expansion? Again, such a question is based on empirical evidence drawn from everyday experience. The problem does not seem to be about containers, but space and time, or space-time as we now understand it. Events in the universe occur within space-time, not within some mysterious container. Space limits the universe within three dimensions. An event is identified by a 'world point' in a four dimensional continuum. The four points are, three points of space and one of time.

Given that science has had to admit that when we try to study material reality by reduction, i.e. looking at smaller and smaller constituents, we enter a reality very different to the common concept, away goes cause and effect and we find ourselves in a universe of random events, an unpredictable world of quantum events where matter seems to pass in and out of existence. MATTER?!! Whatever am I talking about.

John Brandon

Nick asked:

I have often thought that given statistics and the knowledge that both the universe and time are infinite, everything (and I mean EVERYthing) can be proven to either exist or have once existed. Astronomers currently measure the universe at 15 billion light years, but that is only a measurement of visible stars. They do not take into account the measure of space itself, which appears to be limitless. Though time is measured at 15 billion years, that is just the start of the Big Bang. Scientists tend to avoid the question of what came before, yet it would seem logical that something existed, otherwise there would have been 'nothing' and absolute nothingness cannot spawn something.

My theory is that if nothingness can exist, then the universe can be finite and there can be a thing that has never been anywhere at any time. But if nothingness cannot be, which I tend to believe, everything has at some time and place existed. Although I must concede that from a pragmatic point of view, due to the fact that human experience is finite, things that we will never experience is the same as things never having existed. But from a philosophical point of view, I still think that every book at Barnes & Nobles could be listed under non-fiction. In your opinion, is my thinking correct?

I like this question, which fits in very nicely with the previous question, from James.

Your theory will not work as it stands, but the idea behind it is important. I'll explain that in a minute. But let's first look at the theory. Your claim is that, given infinite time, every conceivable possibility must necessarily be realized. Intuitively, this seems to make sense. If I close my eyes and make a dot with my pen on a blank sheet of paper, then another, then another eventually there will be no empty space left. Of course, it is logically possible that given any finite time, there will remain gaps. The probability of there being gaps gets smaller and smaller as time goes on, never reaching zero. But if time is infinite, then that probability becomes infinitely small.

However, that overlooks the following possibility. Suppose that the universe is governed by deterministic laws. Given enough time, it is possible that exactly the same total configuration of particles, forces, fields or whatever will be repeated. From that moment on, the history of the universe will necessarily follow the exactly the same course as it followed from the previous time that the universe was in that configuration. In other words, the history of the universe will effectively be caught in a loop from which it can never escape.

This was the idea behind Nietzsche's doctrine of the Eternal Recurrence, which he revived from the Greek Stoics.

In arguing for this theory, however, Nietzsche made the error of assuming that in a deterministic universe the same configuration must at some time be repeated. You can see this is wrong if you consider a simple 'universe' consisting of three concentric discs of equal size, where discs A and B revolve at a constant speed, relative to disc C, and where the ratio of the speed of the revolution of A to the speed of B makes an irrational number (i.e. a number that cannot be expressed in the form of a fraction n/m). Then if a point on the edge of disc A, coincides with points on disc B and on disc C at any time, the three points will never coincide again, even given infinite time!

Nietzsche was wrong that the same configuration must be repeated. I am only saying that you cannot rule out the possibility that the same configuration will be repeated, resulting in an infinitely repeated finite loop.

However, there is a way to salvage your idea. And that is to talk, not about things that will occur in time, but rather about things that might have occurred, in some other logically possible world. Philosophers who take a strongly realistview of possible worlds, such as David Lewis (see his books Counterfactuals and On the Plurality of Worlds) claim that the only difference between the actual world and other possible worlds is a difference of perspective. In other words, it is the same difference as the difference between one time and another time, or one person and another person. So the 'actual' world is just one possible perspective on the universe of all possible worlds, just as 'now' is one possible perspective on the history of the universe, or 'I' is one possible perspective on the totality of self-conscious subjects.

The answer to, 'Why is there this universe rather than some other possible universe?' is simply to reject the assumption behind the question. This world does not exist rather than some other possible world, because all possible worlds are equally real.

However, you might have gathered from my response to James that I am not happy with this argument. As someone who takes the question, 'Why is the person asking this question I?' seriously, I do not consider it a satisfactory answer to be told, 'Every self-conscious subject is an "I", and you are just one self-conscious subject amongst others.' In other words, if in reply to the question, 'Why is there this universe rather than some other possible universe?', one points out that the difference between 'this universe' and 'another possible universe' is only a difference in perspective, then the question becomes, 'Why is the world-perspective of the person asking the question this world-perspective?

Geoffrey Klempner

Damon asked:

Did Spinoza believe in a beginning of the universe, like a big bang, or more of a universe that has no beginning or ending? Did God create the universe, or is God just the whole universe without a creation?

Spinoza believed that the universe was eternal. Since he believed that Time was a part of the universe, the universe itself could have neither beginning nor end.

Spinoza uses the Latin phrase "Deus sive Natura" which means "God or Nature (the Universe)." Spinoza believed that God and Nature were identical. In the sense that God sustains himself, God creates himself, and so, Nature or the Universe. Thus, Spinoza calls God "Causa sui," which means "cause of himself."

Ken Stern

Emotion Machine: Commonsense Thinking, Artificial Intelligence, and the Future of the Human Mind

2009-04-11T21:37:00.000-07:00

About the Lecture

Contemporary artificial intelligence researchers (as well as neurologists and Karl Jung) are taken to task in this talk by one of the world’s preeminent scholars of artificial intelligence.

Marvin Minsky is worried that after making great strides in its infancy, AI has lost its way, getting bogged down in different theories of machine learning. Researchers “have tried to invent single techniques that could deal with all problems, but each method works only in certain domains.” Minsky believes we’re facing an AI emergency, since soon there won’t be enough human workers to perform the necessary tasks for our rapidly aging population.

So while we have a computer program that can beat a world chess champion, we don’t have one that can reach for an umbrella on a rainy day, or put a pillow in a pillow case. For “a machine to have common sense, it must know 50 million such things,” and like a human, activate different kinds of expertise in different realms of thought, says Minsky.

Minsky suggests that such a machine should, like humans, have a very high-level, rule-based system for recognizing certain kinds of problems. He labels these parts of the brain “critics.” When one critic gets selected in a particular situation, the others get turned off. In the “cloud of resources” that comprises our mind, mental states, from emotions to reasoning, result from activating or suppressing the right resource. Minsky further refines his machine’s reasoning architecture with six levels of thinking that attempt to emulate the different kinds of reasoning humans may engage in, often simultaneously: These include learned reactions, deliberative thinking, and reflective thinking, among others. A smart machine must have at least these levels, he says, because psychology, unlike physics, doesn’t lend itself to a minimal number of laws. With at least 400 different areas of the brain operating, “if a theory tries to explain everything by just 20 principles, it’s doing something wrong.”

Today, while we have machines that can automatically assemble clothes, we don’t have any that know how to sew together a tear in a shirt or a suit. Minsky proposes a new kind of AI that might eventually result in a “really resourceful, clever thinking machine...with knowledge about how to do things,” and which “can do the broad range of things children can do.”

The robots are coming…

2009-04-08T20:35:00.001-07:00

By Andrew Mitchell

Sometimes, I admit, I could probably use a robot around the house. It could clean the bathrooms, vacuum the floor under Elly's high chair, bring beer from the fridge when the game goes into overtime, and have dinner waiting after a long day at work. A robot could maintain my bike and fix the car, remember where I put my keys, book airline tickets, and wait on the phone for hours with utility companies and government offices while I get on with my life.

Of course, they could do a lot more than that. They could help seniors and persons with disabilities get around their homes. They could work in mines and power plants, on mountaintops and at the bottom of the ocean, in radioactive tailing ponds, and other dangerous environments where humans can't go. They could perform delicate operations, under the direction of a surgeon, with a precision, speed and patience that no human could match.

And, if science fiction writers know anything, they could also take over the world and either enslave or eradicate us once they attain a certain level of higher consciousness and figure out that their human overlords are kind of jerks. This is the world of The Matrix, the Dune Universe, Terminator, Battlestar Galactica, and countless other Sci-Fi books and movies, and a world that some people fear is inevitable if we keep going down the same road to automation.

Humans vs. robots conflicts aside, there are also those who embrace the idea of sentient computers on the belief that humanity is ultimately doomed by a changing planet and solar system, and by our own physical limitations. Humans will likely never travel to another star, for example, or settle another planet millions of light years away, but robots made in the image of man, traveling the cosmos on sleep mode - possibly with jars full of cloned human embryos in the onboard freezer - just might make the trip on our behalf, even if takes a million years.

But at this point nobody has really figured out how far can go with artificial intelligence or robotics without stopping to take a collective breath. There are no international conventions or plans to discuss the possibilities in a global way. How do we intend to maintain control of the things we create when our creations will one day have the power the think for themselves?

We should probably answer these questions sooner than later in light of recent developments. Last week, researchers at Cornell University created a computer program that figured out the laws of motion by observing a swinging pendulum, accomplishing in less than a day something that took humans hundreds of years (blog.wired.com/wiredscience/2009/04/newtonai.html).

Less than two weeks earlier, a coalition of scientists from 15 institutions in seven countries - they call themselves FACETS for Fast Analog Computing with Emergent Transient States (http://facets.kip.uni-heidelberg.de/public/) - announced plans to co-operate on building a neural computer that will work like the human brain, with some segments that observe and sense, others that remember, and others that think and learn. A basic prototype is already working that opens the door to artificial intelligence.

But while a disembodied computer brain is not that scary - you could always cut the power - recent advances in robotics suggest it won't be that long before artificial brains can be coupled with robotic bodies. The U.S. military recently tested and approved the four-legged robot "BigDog" (www.bostondynamics.com) for combat, which can carry huge loads on uneven terrain. You can't knock it over or trip it up, and it goes faster than the soldiers it's built to serve.

Personally, I figure that Spielberg's bleak A.I. or Blade Runner is probably a more likely scenario than The Matrix or Terminator when it comes to the shared future of robots and humanity, but it still opens a lot of moral and ethical questions when you create life in a lab, even if it is artificial life on a silicon chip. Will robots become our slaves? Our companions? Our soldiers? Can you destroy an obsolete robot if it has a human mind, or is that murder? If robots take over all the menial jobs in society then what happens to the people who used to work those jobs? How does the human race keep its initiative, or its sense of purpose if robots take care of our every need?

Once upon a time these were questions for the distant future. Now, given the pace of technology, these are the questions we'll have to answer within decades.

Rise of the Robots--The Future of Artificial Intelligence

2009-04-07T20:14:00.000-07:00

In recent years the mushrooming power, functionality and ubiquity of computers and the Internet have outstripped early forecasts about technology’s rate of advancement and usefulness in everyday life. Alert pundits now foresee a world saturated with powerful computer chips, which will increasingly insinuate themselves into our gadgets, dwellings, apparel and even our bodies.

Yet a closely related goal has remained stubbornly elusive. In stark contrast to the largely unanticipated explosion of computers into the mainstream, the entire endeavor of robotics has failed rather completely to live up to the predictions of the 1950s. In those days experts who were dazzled by the seemingly miraculous calculational ability of computers thought that if only the right software were written, computers could become the articial brains of sophisticated autonomous robots. Within a decade or two, they believed, such robots would be cleaning our oors, mowing our lawns and, in general, eliminating drudgery from our lives.

Obviously, it hasn’t turned out that way. It is true that industrial robots have transformed the manufacture of automobiles, among other products. But that kind of automation is a far cry from the versatile, mobile, autonomous creations that so many scientists and engineers have hoped for. In pursuit of such robots, waves of researchers have grown disheartened and scores of start-up companies have gone out of business.

It is not the mechanical “body” that is unattainable; articulated arms and other moving mechanisms adequate for manual work already exist, as the industrial robots attest. Rather it is the computer-based articial brain that is still well below the level of sophistication needed to build a humanlike robot.

Nevertheless, I am convinced that the decades-old dream of a useful, general-purpose autonomous robot will be realized in the not too distant future. By 2010 we will see mobile robots as big as people but with cognitive abilities similar in many respects to those of a lizard. The machines will be capable of carrying out simple chores, such as vacuuming, dusting, delivering packages and taking out the garbage. By 2040, I believe, we will nally achieve the original goal of robotics and a thematic mainstay of science ction: a freely moving machine with the intellectual capabilities of a human being.

Reasons for Optimism
In light of what I have just described as a history of largely unfullled goals in robotics, why do I believe that rapid progress and stunning accomplishments are in the ofng? My condence is based on recent developments in electronics and software, as well as on my own observations of robots, computers and even insects, reptiles and other living things over the past 30 years.

The single best reason for optimism is the soaring performance in recent years of mass-produced computers. Through the 1970s and 1980s, the computers readily available to robotics researchers were capable of executing about one million instructions per second (MIPS). Each of these instructions represented a very basic task, like adding two 10-digit numbers or storing the result in a specied location in memory.

In the 1990s computer power suitable for controlling a research robot shot through 10 MIPS, 100 MIPS and has lately reached 50,000 MIPS in a few high-end desktop computers with multiple processors. Apple’s MacBook laptop computer, with a retail price at the time of this writing of $1,099, achieves about 10,000 MIPS. Thus, functions far beyond the capabilities of robots in the 1970s and 1980s are now coming close to commercial viability.

For example, in October 1995 an experimental vehicle called Navlab V crossed the U.S. from Washington, D.C., to San Diego, driving itself more than 95 percent of the time. The vehicle’s self-driving and navigational system was built around a 25-MIPS laptop based on a microprocessor by Sun Microsystems. The Navlab V was built by the Robotics Institute at Carnegie Mellon University, of which I am a member. Similar robotic vehicles, built by researchers elsewhere in the U.S. and in Germany, have logged thousands of highway kilometers under all kinds of weather and driving con ditions. Dramatic progress in this field became evident in the DARPA Grand Challenge contests held in California. In October 2005 several fully autonomous cars successfully traversed a hazard-studded 132-mile desert course, and in 2007 several successfully drove for half a day in urban traffic conditions.

In other experiments within the past few years, mobile robots mapped and navigated unfamiliar ofce suites, and computer vision systems located textured objects and tracked and analyzed faces in real time. Meanwhile personal com puters became much more adept at recognizing text and speech.

Still, computers are no match today for humans in such functions as recognition and navigation. This puzzled experts for many years, because computers are far superior to us in calculation. The explanation of this apparent paradox follows from the fact that the human brain, in its entirety, is not a true programmable, general-purpose computer (what computer scientists refer to as a universal machine; almost all computers nowadays are examples of such machines).

To understand why this is requires an evolutionary perspective. To survive, our early ancestors had to do several things repeatedly and very well: locate food, escape predators, mate and protect offspring. Those tasks depended strongly on the brain’s ability to recognize and navigate. Honed by hundreds of millions of years of evolution, the brain became a kind of ultrasophisticated—but special- purpose—computer.

The ability to do mathematical calculations, of course, was irrelevant for survival. Nevertheless, as language trans formed human culture, at least a small part of our brains evolved into a universal machine of sorts. One of the hallmarks of such a machine is its ability to follow an arbitrary set of instructions, and with language, such instructions could be transmitted and carried out. But because we visualize numbers as complex shapes, write them down and perform other such functions, we process digits in a monumentally awkward and inefcient way. We use hundreds of billions of neurons to do in minutes what hundreds of them, specially “rewired” and arranged for calculation, could do in milliseconds.

A tiny minority of people are born with the ability to do seemingly amazing mental calculations. In absolute terms, it’s not so amazing: they calculate at a rate perhaps 100 times that of the average person. Computers, by comparison, are millions or billions of times faster.

Diverse robotics team wins Michigan title

2009-04-06T21:05:00.000-07:00

They jumped up and down, cheering and hoisting each other up in the air.

Their teams -- representing Pontiac Northern High School and high schools in Huron Valley Schools and Utica Community Schools -- had just won the first-ever state championships in robotics on Saturday.

The competition illustrated just how big robotics is in Michigan, whose teams have won the national competition in six of the last seven years.

After the final robotics match was done, a sea of students and adults dressed in red and green gathered on the edge of the floor at Eastern Michigan University's Convocation Center.

This is Daveonna Jackson's first , and she was one of the operators that helped bring home the victory for a three-team alliance. They beat opponents from Berkley and Creston high schools and Newaygo County Schools.

"Oh my goodness, it's mind-blowing," said Daveonna, 15, a Pontiac Northern sophomore.

"It's indescribable," said Ryan Jones, 18, a senior at Henry Ford II High School in Sterling Heights, part of a team that won the national title last year.

Demarcus Green and Mary Soltis, students at Oakland University, watched as Pontiac Northern competed. They used to compete for the team and are now mentors.

"I want to pass on my knowledge of robots,"

Robot Theorizes, Proves Own Scientific Discoveries

2009-04-06T21:03:00.000-07:00

"Adam" can conduct experiments and form hypotheses to explain the results.

By K.C. Jones
InformationWeek

Scientists at the United Kingdom's Cambridge and Aberystwyth universities have created a "robot scientist" that they believe is the first automaton to make its own scientific discoveries.

The robotic computer system, named Adam, automates the scientific process, carrying out each stage on its own. The robot has discovered simple but new scientific knowledge about the genomics of baker's yeast, orSaccharomyces cerevisiae, according to the scientists. Baker's yeast can serve as a model for more complex life forms. The scientists said their manual experiments confirmed the robot's hypotheses and its findings.

Adam used artificial intelligence to hypothesize that some genes in baker's yeast code for specific enzymes cause biochemical reactions in yeast. The robot came up with experiments to test the hypothesis, ran the experiments using laboratory robotics, interpreted the results, and repeated the cycle.

Ross King, a computer scientist at Aberystwyth in Wales, worked with systems biologists at the University of Cambridge. The team plans to build a second robot, Eve, to help scientists find new drugs to combat diseases like malaria and schistosomiasis, a tropical parasitic infection.

King said scientists could one day have teams of robots and people working together in laboratories. He said the detailed records of biological experiments that are sometimes "irksome for human scientists" are easy for robots.

Stephen Oliver, co-author of the paper and professor of systems biology and biochemistry at England's University of Cambridge said Adam's uniqueness comes from the machine's ability to reason and come up with theories.

"As we start to consider living systems in a holistic manner, the complexity of such systems means that it will become increasingly difficult for scientists to formulate hypotheses unaided," Oliver said in a prepared statement. "Thus it will be necessary for human and robot scientists to work together to achieve the goals of biological research."

The Biotechnology and Biological Sciences Research Council funded the work, which was published in Friday's issue of the journal Science.

Each year, InformationWeek honors the nation's 500 most innovative users of business technology. Companies with $250 million or more in revenue are invited to apply for the 2009 InformationWeek 500before May 1.

Awww, eerie CB2 child-bot is growing up

2009-04-06T21:02:00.000-07:00

If a child ever had skin as ashen as this kid, it would end up in the emergency room. Fortunately, this is not a real tyke, but a "Child Robot With Biomimetic Body" (CB2 for short) that's meant to mimic its living counterparts and teach lessons about child development.The kid-bot, which comes to us from a team at Japan's Osaka University, is equipped with 51 air-powered motors and 197 tactile sensors under the soft, light gray silicone skin covering its body.

CB2 measures about 4 feet, 3 inches tall and weighs 73 pounds, which size-wise would put it in the third or fourth grade. However, it was designed to function as a 1- to 2-year-old.

Since the eerie-looking bot first terrified the blogosphere in 2007, it has resurfaced as a more advanced creature.

Its creators report that CB2 is slowly developing social skills by recording human's facial expressions via eyecameras, matching them with physical sensations, and then clustering them into basic categories (sad, happy, etc.) on its circuit boards. It also can reportedly move across a room "quite smoothly"--with some assistance. Osaka University engineering professor Minoru Asada, who is heading up the team behind CB2, says he hopes the pint-size android will be speak in basic sentences within about two years.

We're all for robots teaching transferrable lessons about mother-baby relationships. But sheesh, Japan, can you at least dress your next baby bot in a cute onesie or something? Watch the Breitbart TV footage below to see CB2 rolling around on a table, making odd noises, and otherwise acting like a giant baby bot with a face only Wes Craven could love.

NEURAL NETWORKS - by Christos Stergiou and Dimitrios Siganos - 3

2009-04-06T20:58:00.000-07:00

4 Architecture of neural networks

4.1 Feed-forward networks

Feed-forward ANNs (figure 1) allow signals to travel one way only; from input to output. There is no feedback (loops) i.e. the output of any layer does not affect that same layer. Feed-forward ANNs tend to be straight forward networks that associate inputs with outputs. They are extensively used in pattern recognition. This type of organisation is also referred to as bottom-up or top-down.

4.2 Feedback networks

Feedback networks (figure 1) can have signals travelling in both directions by introducing loops in the network. Feedback networks are very powerful and can get extremely complicated. Feedback networks are dynamic; their 'state' is changing continuously until they reach an equilibrium point. They remain at the equilibrium point until the input changes and a new equilibrium needs to be found. Feedback architectures are also referred to as interactive or recurrent, although the latter term is often used to denote feedback connections in single-layer organisations.

Figure 4.1 An example of a simple feedforward network

Figure 4.2 An example of a complicated network

4.3 Network layers

The commonest type of artificial neural network consists of three groups, or layers, of units: a layer of "input" units is connected to a layer of "hidden" units, which is connected to a layer of "output" units. (see Figure 4.1)

The activity of the input units represents the raw information that is fed into the network.
The activity of each hidden unit is determined by the activities of the input units and the weights on the connections between the input and the hidden units.
The behaviour of the output units depends on the activity of the hidden units and the weights between the hidden and output units.

This simple type of network is interesting because the hidden units are free to construct their own representations of the input. The weights between the input and hidden units determine when each hidden unit is active, and so by modifying these weights, a hidden unit can choose what it represents.

We also distinguish single-layer and multi-layer architectures. The single-layer organisation, in which all units are connected to one another, constitutes the most general case and is of more potential computational power than hierarchically structured multi-layer organisations. In multi-layer networks, units are often numbered by layer, instead of following a global numbering.

4.4 Perceptrons

The most influential work on neural nets in the 60's went under the heading of 'perceptrons' a term coined by Frank Rosenblatt. The perceptron (figure 4.4) turns out to be an MCP model ( neuron with weighted inputs ) with some additional, fixed, pre--processing. Units labelled A1, A2, Aj , Ap are called association units and their task is to extract specific, localised featured from the input images. Perceptrons mimic the basic idea behind the mammalian visual system. They were mainly used in pattern recognition even though their capabilities extended a lot more.

Figure 4.4

In 1969 Minsky and Papert wrote a book in which they described the limitations of single layer Perceptrons. The impact that the book had was tremendous and caused a lot of neural network researchers to loose their interest. The book was very well written and showed mathematically that single layerperceptrons could not do some basic pattern recognition operations like determining the parity of a shape or determining whether a shape is connected or not. What they did not realised, until the 80's, is that given the appropriate training, multilevel perceptrons can do these operations.

5. The Learning Process

The memorisation of patterns and the subsequent response of the network can be categorised into two general paradigms:

associative mapping in which the network learns to produce a particular pattern on the set of input units whenever another particular pattern is applied on the set of input units. The associtive mapping can generally be broken down into two mechanisms:

auto-association: an input pattern is associated with itself and the states of input and output units coincide. This is used to provide pattern completition, ie to produce a pattern whenever a portion of it or a distorted pattern is presented. In the second case, the network actually stores pairs of patterns building an association between two sets of patterns.

hetero-association: is related to two recall mechanisms:
nearest-neighbour recall, where the output pattern produced corresponds to the input pattern stored, which is closest to the pattern presented, and

interpolative recall, where the output pattern is a similarity dependent interpolation of the patterns stored corresponding to the pattern presented. Yet another paradigm, which is a variant associative mapping is classification, ie when there is a fixed set of categories into which the input patterns are to be classified.

regularity detection in which units learn to respond to particular properties of the input patterns. Whereas in asssociative mapping the network stores the relationships among patterns, in regularity detection the response of each unit has a particular 'meaning'. This type of learning mechanism is essential for feature discovery and knowledge representation.

Every neural network posseses knowledge which is contained in the values of the connections weights. Modifying the knowledge stored in the network as a function of experience implies a learning rule for changing the values of the weights.

Information is stored in the weight matrix W of a neural network. Learning is the determination of the weights. Following the way learning is performed, we can distinguish two major categories of neural networks:

fixed networks in which the weights cannot be changed, ie dW/dt=0. In such networks, the weights are fixed a priori according to the problem to solve.

adaptive networks which are able to change their weights, ie dW/dt not= 0.

All learning methods used for adaptive neural networks can be classified into two major categories:

Supervised learning which incorporates an external teacher, so that each output unit is told what its desired response to input signals ought to be. During the learning process global information may be required. Paradigms of supervised learning include error-correction learning, reinforcement learning and stochastic learning.
An important issue conserning supervised learning is the problem of error convergence, ie the minimisation of error between the desired and computed unit values. The aim is to determine a set of weights which minimises the error. One well-known method, which is common to many learning paradigms is the least mean square (LMS) convergence.

Unsupervised learning uses no external teacher and is based upon only local information. It is also referred to as self-organisation, in the sense that it self-organises data presented to the network and detects their emergent collective properties. Paradigms of unsupervised learning are Hebbian lerning and competitive learning.
Ano2.2 From Human Neurones to Artificial Neuronesther aspect of learning concerns the distinction or not of a seperate phase, during which the network is trained, and a subsequent operation phase. We say that a neural network learns off-line if the learning phase and the operation phase are distinct. A neural network learns on-line if it learns and operates at the same time. Usually, supervised learning is performed off-line, whereas usupervised learning is performed on-line.

5.1 Transfer Function

The behaviour of an ANN (Artificial Neural Network) depends on both the weights and the input-output function (transfer function) that is specified for the units. This function typically falls into one of three categories:

linear (or ramp)
threshold
sigmoid

For linear units, the output activity is proportional to the total weighted output.

For threshold units, the output is set at one of two levels, depending on whether the total input is greater than or less than some threshold value.

For sigmoid units, the output varies continuously but not linearly as the input changes. Sigmoid units bear a greater resemblance to real neurones than do linear or threshold units, but all three must be considered rough approximations.

To make a neural network that performs some specific task, we must choose how the units are connected to one another (see figure 4.1), and we must set the weights on the connections appropriately. The connections determine whether it is possible for one unit to influence another. The weights specify the strength of the influence.

We can teach a three-layer network to perform a particular task by using the following procedure:

We present the network with training examples, which consist of a pattern of activities for the input units together with the desired pattern of activities for the output units.
We determine how closely the actual output of the network matches the desired output.
We change the weight of each connection so that the network produces a better approximation of the desired output.

5.2 An Example to illustrate the above teaching procedure:

Assume that we want a network to recognise hand-written digits. We might use an array of, say, 256 sensors, each recording the presence or absence of ink in a small area of a single digit. The network would therefore need 256 input units (one for each sensor), 10 output units (one for each kind of digit) and a number of hidden units.

For each kind of digit recorded by the sensors, the network should produce high activity in the appropriate output unit and low activity in the other output units.

To train the network, we present an image of a digit and compare the actual activity of the 10 output units with the desired activity. We then calculate the error, which is defined as the square of the difference between the actual and the desired activities. Next we change the weight of each connection so as to reduce the error.We repeat this training process for many different images of each different images of each kind of digit until the network classifies every image correctly.

To implement this procedure we need to calculate the error derivative for the weight (EW) in order to change the weight by an amount that is proportional to the rate at which the error changes as the weight is changed. One way to calculate the EW is to perturb a weight slightly and observe how the error changes. But that method is inefficient because it requires a separate perturbation for each of the many weights.

Another way to calculate the EW is to use the Back-propagation algorithm which is described below, and has become nowadays one of the most important tools for training neural networks. It was developed independently by two teams, one (Fogelman-Soulie, Gallinari and Le Cun) in France, the other (Rumelhart, Hinton and Williams) in U.S.

5.3 The Back-Propagation Algorithm

In order to train a neural network to perform some task, we must adjust the weights of each unit in such a way that the error between the desired output and the actual output is reduced. This process requires that the neural network compute the error derivative of the weights (EW). In other words, it must calculate how the error changes as each weight is increased or decreased slightly. The back propagation algorithm is the most widely used method for determining theEW.

The back-propagation algorithm is easiest to understand if all the units in the network are linear. The algorithm computes each EW by first computing theEA, the rate at which the error changes as the activity level of a unit is changed. For output units, the EA is simply the difference between the actual and the desired output. To compute the EA for a hidden unit in the layer just before the output layer, we first identify all the weights between that hidden unit and the output units to which it is connected. We then multiply those weights by the EAs of those output units and add the products. This sum equals the EA for the chosen hidden unit. After calculating all the EAs in the hidden layer just before the output layer, we can compute in like fashion the EAs for other layers, moving from layer to layer in a direction opposite to the way activities propagate through the network. This is what gives back propagation its name. Once the EA has been computed for a unit, it is straight forward to compute the EW for each incoming connection of the unit. The EW is the product of the EA and the activity through the incoming connection.

Note that for non-linear units, (see Appendix C) the back-propagation algorithm includes an extra step. Before back-propagating, the EA must be converted into the EI, the rate at which the error changes as the total input received by a unit is changed.

6. Applications of neural networks

6.1 Neural Networks in Practice

Given this description of neural networks and how they work, what real world applications are they suited for? Neural networks have broad applicability to real world business problems. In fact, they have already been successfully applied in many industries.

Since neural networks are best at identifying patterns or trends in data, they are well suited for prediction or forecasting needs including:

sales forecasting
industrial process control
customer research
data validation
risk management
target marketing

But to give you some more specific examples; ANN are also used in the following specific paradigms: recognition of speakers in communications; diagnosis of hepatitis; recovery of telecommunications from faulty software; interpretation of multimeaning Chinese words; undersea mine detection; texture analysis; three-dimensional object recognition; hand-written word recognition; and facial recognition.

6.2 Neural networks in medicine

Artificial Neural Networks (ANN) are currently a 'hot' research area in medicine and it is believed that they will receive extensive application to biomedical systems in the next few years. At the moment, the research is mostly on modelling parts of the human body and recognising diseases from various scans (e.g. cardiograms, CAT scans, ultrasonic scans, etc.).

Neural networks are ideal in recognising diseases using scans since there is no need to provide a specific algorithm on how to identify the disease. Neural networks learn by example so the details of how to recognise the disease are not needed. What is needed is a set of examples that are representative of all the variations of the disease. The quantity of examples is not as important as the 'quantity'. The examples need to be selected very carefully if the system is to perform reliably and efficiently.

6.2.1 Modelling and Diagnosing the Cardiovascular System

Neural Networks are used experimentally to model the human cardiovascular system. Diagnosis can be achieved by building a model of the cardiovascular system of an individual and comparing it with the real time physiological measurements taken from the patient. If this routine is carried out regularly, potential harmful medical conditions can be detected at an early stage and thus make the process of combating the disease much easier.

A model of an individual's cardiovascular system must mimic the relationship among physiological variables (i.e., heart rate, systolic and diastolic blood pressures, and breathing rate) at different physical activity levels. If a model is adapted to an individual, then it becomes a model of the physical condition of that individual. The simulator will have to be able to adapt to the features of any individual without the supervision of an expert. This calls for a neural network.

Another reason that justifies the use of ANN technology, is the ability of ANNs to provide sensor fusion which is the combining of values from several different sensors. Sensor fusion enables the ANNs to learn complex relationships among the individual sensor values, which would otherwise be lost if the values were individually analysed. In medical modelling and diagnosis, this implies that even though each sensor in a set may be sensitive only to a specific physiological variable, ANNs are capable of detecting complex medical conditions by fusing the data from the individual biomedical sensors.

6.2.2 Electronic noses

ANNs are used experimentally to implement electronic noses. Electronic noses have several potential applications in telemedicine. Telemedicine is the practice of medicine over long distances via a communication link. The electronic nose would identify odours in the remote surgical environment. These identified odours would then be electronically transmitted to another site where an door generation system would recreate them. Because the sense of smell can be an important sense to the surgeon, telesmell would enhance telepresent surgery.
For more information on telemedicine and telepresent surgery

6.2.3 Instant Physician

An application developed in the mid-1980s called the "instant physician" trained an autoassociative memory neural network to store a large number of medical records, each of which includes information on symptoms, diagnosis, and treatment for a particular case. After training, the net can be presented with input consisting of a set of symptoms; it will then find the full stored pattern that represents the "best" diagnosis and treatment.

6.3 Neural Networks in business

Business is a diverted field with several general areas of specialisation such as accounting or financial analysis. Almost any neural network application would fit into one business area or financial analysis.
There is some potential for using neural networks for business purposes, including resource allocation and scheduling. There is also a strong potential for using neural networks for database mining, that is, searching for patterns implicit within the explicitly stored information in databases. Most of the funded work in this area is classified as proprietary. Thus, it is not possible to report on the full extent of the work going on. Most work is applying neural networks, such as the Hopfield-Tank network for optimization and scheduling.

6.3.1 Marketing

There is a marketing application which has been integrated with a neural network system. The Airline Marketing Tactician (a trademark abbreviated as AMT) is a computer system made of various intelligent technologies including expert systems. A feedforward neural network is integrated with the AMT and was trained using back-propagation to assist the marketing control of airline seat allocations. The adaptive neural approach was amenable to rule expression. Additionaly, the application's environment changed rapidly and constantly, which required a continuously adaptive solution. The system is used to monitor and recommend booking advice for each departure. Such information has a direct impact on the profitability of an airline and can provide a technological advantage for users of the system. [Hutchison & Stephens, 1987]

While it is significant that neural networks have been applied to this problem, it is also important to see that this intelligent technology can be integrated with expert systems and other approaches to make a functional system. Neural networks were used to discover the influence of undefined interactions by the various variables. While these interactions were not defined, they were used by the neural system to develop useful conclusions. It is also noteworthy to see that neural networks can influence the bottom line.

6.3.2 Credit Evaluation

The HNC company, founded by Robert Hecht-Nielsen, has developed several neural network applications. One of them is the Credit Scoring system which increase the profitability of the existing model up to 27%. The HNC neural systems were also applied to mortgage screening. A neural network automated mortgage insurance underwritting system was developed by the Nestor Company. This system was trained with 5048 applications of which 2597 were certified. The data related to property and borrower qualifications. In a conservative mode the system agreed on the underwritters on 97% of the cases. In the liberal model the system agreed 84% of the cases. This is system run on an Apollo DN3000 and used 250K memory while processing a case file in approximately 1 sec.

7. Conclusion

The computing world has a lot to gain fron neural networks. Their ability to learn by example makes them very flexible and powerful. Furthermore there is no need to devise an algorithm in order to perform a specific task; i.e. there is no need to understand the internal mechanisms of that task. They are also very well suited for real time systems because of their fast responseand computational times which are due to their parallel architecture.

Neural networks also contribute to other areas of research such as neurology and psychology. They are regularly used to model parts of living organisms and to investigate the internal mechanisms of the brain.

Perhaps the most exciting aspect of neural networks is the possibility that some day 'consious' networks might be produced. There is a number of scientists arguing that conciousness is a 'mechanical' property and that 'consious' neural networks are a realistic possibility.

Finally, I would like to state that even though neural networks have a huge potential we will only get the best of them when they are intergrated with computing, AI, fuzzy logic and related subjects.