I once was deep in pain it seemed I couldn’t find The perfect interaction that would do No agent was in state that would let him bind My injured heart that was torn in two. The scheduler at first was adversarial Though Angluin et al. said that he had to be fair So while my state was marked as “being in despair” You show up as my interacting pair. My plan was all too good but just in theory You see our space was limited in range But if we had some logarithmic memory I couldn’t wait for our first tape exchange. Thank god I was to meet you one more time again Compute with you the predicate of love This time in a new model named PM Let’s stabilize our outputs to one. -------------------Andreas Pavlogiannis, 2010 摘自一专题论文：《New Models for Population Protocols》，三位作者来自University of Patras（Patras, Greece）
t-kernel: Providing Reliable OS Support to Wireless Sensor Networks Lin Gu John A. Stankovic SenSys 2006 ACM (ACM Conference on Embedded Networked Sensor Systems: CCF B level conference) Abstract The development of a reliable large-scale wireless sensor network (WSN) is very difficult because of resource constraints, energy budget, and demanding application requirements. Three OS features —OS protection, virtual memory, and preemptive scheduling—can significantly improve the reliability of WSN systems and facilitate developing complex WSN software. However, due to the lack of hardware support for privileged execution and address translation, it is impossible to implement these features with traditional OS design techniques. To solve this problem, we design a new OS kernel, the t-kernel , to perform extensive code modification at load time. The modified code and the OS work in a collaborative way supporting the aforementioned features. Having implemented the t-kernel on MICA2 motes, we evaluate its performance by measuring the overhead and execution speed. We analyze the CPU utilization of sensor network applications, and verify that, though CPU-bound tasks execute 1.5–3 times as long as in native mode, application performance undertypicalworkloads does not noticeably degrade. The t-kernel significantly enhances developers’ ability to design reliable and sophisticated sensor networks, and includes several new design techniques, such as efficient binary translation on highly constrained sensor nodes, differentiated virtual memory without repeatedly writable swapping devices, and the protection of the OS from application errors without privileged execution hardware. Keywords: Wireless Sensor networks, OS Protection, Virtual Memory, Binary Translation, Low-Power Systems 1 Introduction wireless sensor networks (WSNs) and mote-class devices, e.g., the Berkeley motes the core features: OS protection (protect the OS from application errors), virtual memory, and preemptive scheduling The reason: lack of hardware support t-kernel: utilizea load-time modification approach the contribution of t-kernel : 1) efficient binary translation with very small memory, 2) efficient software based virtual memory, 3)OS protection without memory protection or privileged execution hardware. The organization of this paper: 1) Section 2 analyzes the requirements and examines why stronger OS support is necessary for WSNs. 2) Section 3 states the assumptions and briefly describes the t-kernel’s approach. 3) Then, Section 4 details the design of the t-kernel, 4)Section 5 introduces the implementation on a widely used WSN platform. 5) Section 6 evaluates the performance of the t-kernel. 6)Section 7 discusses related work, 7) Section 8 lists the limitations of the t-kernel and briefly discusses future work 2 Motivation the outline of this section: 1) first study two realworld scenarios 2)then illustrate the difficulties researchers encounter when developing high-qualityWSN systems. Scenario 1: OS control the obstacle confront by The Extreme Scaling: an interference between the OS kernel and application code Scenario 2: memory shortage VigilNet sensor vs PC three crucial features: OS protection and virtual memory, preemptive scheduling advanced hardware support —privileged instructions, virtual address translation, and memory protection the reason for the lack of advanced hardware features: 1) cost 2) low power consumption need: energy-and-cost-efficient sensor nodes 3 Assumptions the following assumptions on the hardware: • Assumption R: Reprogrammable—The system allows writing data into some memory space and executing it. • Assumption E: External nonvolatile storage—Lowpower, nonvolatile, and relatively large-capacity external storage is available, and it supports fast and repeated read operations (read-friendly). • Assumption M: Memory—A certain amount of RAM is available. ( = 4KB physical memory be available.) 4 Design the outline of this section: This section introduces the design of the t-kernel. 1) First, Section 4.1 give a high-level description of the t-kernel and define terminology. 2) Then Section 4.2 and 4.3 discuss the CPU control and virtual memory in detail. 3) Finally, Section 4.4 discusses the interface between the kernel and application. 4.1 Overview three sources of challenges in designing t-kernel for a REM computer: stringent resource constraints, possibly write-unfriendly (limited erasure/write cycles) external nonvolatile storage (e.g., flash), and lack of hardware features (e.g., privileged execution). a naturalization process: one type of binary translation VPC (virtual program counter) HPC (host program counter) dispatcher and paging module 4.2 Naturalization and CPU control two aspects of OS protection : CPU control and OS data integrity. the aim of this section: to introduce the naturalization process and explain how it guarantees OS control 4.2.1 Kernel/application transitions the traditional guarante mechanismfor CPU control:privilege support and clock interrupts. the issue: mote sensor do not have privilege support The t-kernel’s approach: to modify the application program so that the naturalized program yields CPU to the kernel frequently. the problem: how does the dispatcher transfer the control flow to the entry point? A straightforward solution: (similar to traditional context switching) to restore register r28–r31 and machine state flags from the stack, and then point HPC to the entry point. three constraints — RAM size, performance, and code density the following procedure for returning to application code adopted by the t-kernel : kernel transition: a transition from application to kernel or from kernel to application an A-K transition or a K-A transition 4.2.2 Branch regulating the new obstacle: the transitions involve overhead and can significantly reduce the computation speed because branch instructions are common. branch regulating: A-K transitions + the bridging process several type oftransitions: backward taken branches 4.2.3 HPC/VPC look-up An efficient VPC-to-HPC lookup algorithm three phase of lookup alogrithm: 1) The slowest, but most reliable level, is at the program memory itself. 2) At the middle level, the kernel maintains a 2-associative VPC table 3) The fastest level is a VPC lookaside buffer 4.3 Differentiated virtual memory 4.3.1 Memory areas three types of memory areas with different attributes defined byt-kernel: • Heap memory: swappable and relocatable. • Stack memory: relocatable but not swappable. For efficiency, this memory area is physically contiguous. • Physical address sensitive memory (PASM): not swappable and not relocatable. differentiated virtual memory (DVM): 4.3.2 Differentiated of memory accesses 4.3.3 Kernel data integrity 4.3.4 Swapping 4.4 Kernel/application interface TinyOSvsthe t-kernel 5 Implementation testbed: ATmega128L microcontroller 6 Performance evaluation the outline of this section: present the performance results of tkernel on the Berkeley MICA2 platform. 1) first measure the overhead of the kernel, including kernel transitions and the DVM. 2) Thenevaluate the relative execution time of a set of kernel benchmark programs, and assess the slowdown of computational tasks. 3) Next verify our estimation by examining the execution speed of a TinyOS application under typical and stressed workloads. 4) Afterward study the performance of radio communication, and analyze energy efficiency. 5)compare the t-kernel’s performance with an interpretation based virtual machine. 6) Finally verify OS protection against a number of application errors. 6.1 Overhead of kernel transitions 6.2 Overhead of naturalized virtual memory 6.3 Assess application-level performance 6.4 Radio communication 6.5 Energy efficiency 6.6 Comparison to the virtual machine approach 6.7 Resistance to application faults 7 Related work research road: embedded OS, virtual machines, network program distribution, binary translation, and software fault isolation embedded OS: TinyOS, SOS, μC/OS virtual machine 8 Limitations and future work 1) low power new hardware to save energy 2) unpredictable latencies introduced by the code modification process and virtual memory swapping 3) thrashing VigilNet I comment: this paper will comparewith 《数据存储管理技术的更新换代》，CCF通讯(My blog: 研究思路探寻), since both paper analysis the problem from enigeering perspective and problem-driven style. this paper introudce the t-kernel, which support the three crucial feature of OS -- support—privileged instructions, virtual address translation, and memory protection. consequently, t-kernel use three means, including Naturalization, Differentiated virtual memory and Kernel/application interface, to realize its goal. but I don't understand Section 7-- related work, that is, I don't grapse the obvious advantage t-kernel over other methods, such as embedded OS, virtual machines, network program distribution, binary translation, and software fault isolation. t-kernel Providing Reliable OS Support to Wireless Sensor Networks.pdf
CNN关于Smart Dust 的报道。 出处： http://edition.cnn.com/2010/TECH/05/03/smart.dust.sensors/index.html?hpt=C1 原文： Palo Alto, California (CNN) -- In the 1990s, a researcher named Kris Pister dreamed up a wild future in which people would sprinkle the Earth with countless tiny sensors, no larger than grains of rice. These "smart dust" particles, as he called them, would monitor everything, acting like electronic nerve endings for the planet. Fitted with computing power, sensing equipment, wireless radios and long battery life, the smart dust would make observations and relay mountains of real-time data about people, cities and the natural environment. Now, a version of Pister's smart dust fantasy is starting to become reality. "It's exciting. It's been a long time coming," said Pister, a computing professor at the University of California, Berkeley. "I coined the phrase 14 years ago. So smart dust has taken a while, but it's finally here." Maybe not exactly how he envisioned it. But there has been progress. The latest news comes from the computer and printing company Hewlett-Packard, which recently announced it's working on a project it calls the "Central Nervous System for the Earth." In coming years, the company plans to deploy a trillion sensors all over the planet. The wireless devices would check to see if ecosystems are healthy, detect earthquakes more rapidly, predict traffic patterns and monitor energy use. The idea is that accidents could be prevented and energy could be saved if people knew more about the world in real time, instead of when workers check on these issues only occasionally. HP will take its first step toward this goal in about two years, said Pete Hartwell, a senior researcher at HP Labs in Palo Alto. The company has made plans with Royal Dutch Shell to install 1 million matchbook-size monitors to aid in oil exploration by measuring rock vibrations and movement, he said. Those sensors, which already have been developed, will cover a 6-square-mile area. That will be the largest smart dust deployment to date, he said. "We just think now, the technology has reached a point where it makes basic sense for us ... to get this out of the lab and into reality," Hartwell said. Smart dust (minus the 'dust') Despite the recent excitement, there's still much confusion in the computing industry about what exactly smart dust is. For starters, the sensors being deployed and developed today are much larger and clunkier than flecks of dust. HP's sensors -- accelerometers like those in the iPhone and Droid phone, but about 1,000 times more powerful -- are about the size of matchbooks. When they're enclosed in a metal box for protection, they're about the size of a VHS tape. So what makes a smart dust sensor different from a weather station or a traffic monitor? Size is one factor. Smart dust sensors must be relatively small and portable. But technology hasn't advanced far enough to manufacture the sensors on the scale of millimeters for commercial use (although Berkeley researchers are trying to make one that's a cubic millimeter). Wireless connections are a big distinguisher, too. A building's thermostat is most likely hard-wired. A smart dust sensor might gauge temperature, but it would be battery-powered and would communicate wirelessly with the internet and with other sensors. The sheer number of sensors in the network is what truly makes a smart dust project different from other efforts to record data about the world, said Deborah Estrin , a professor of computer science at the University of California, Los Angeles, who works in the field. Smart dust researchers tend to talk in the millions, billions and trillions. Some say reality has diverged so far from the smart dust concept that it's time to dump that term in favor or something less sexy. "Wireless sensor networks" or "meshes" are terms finding greater acceptance with some researchers. Estrin said it's important to ditch the idea that smart dust sensors would be disposable. Sensors have to be designed for specific purposes and spread out on the land intentionally -- not scattered in the wind, as smart dust was initially pitched, she said. 'Real-world web' Despite these differences, researchers say the smart-dust theory that monitoring everything will benefit humanity remains essentially unchanged. And there are a number of real-world projects that, in one way or another, seek to use wireless sensors to take the Earth's vital signs. Wireless sensors currently monitor farms, factories, data centers and bridges to promote efficiency and understanding of how these systems work, researchers said in interviews. In all of these cases, the sensor networks are deployed for a specific purpose. For example, a company called Streetline has installed 12,000 sensors on parking spots and highways in San Francisco. The sensors don't know everything that's going on at those parking spots. They are equipped with magnetometers to sense whether or not a huge metal object -- hopefully a car -- is sitting on the spot. That data will soon be available to people who can use it to figure out where to park, said Tod Dykstra, Streetline's CEO. It also tells the cities if the meters have expired. Other sensors are equipped to measure vibration in factories and oil refineries to spot machine problems and inefficiencies before they cause trouble. Still others might pick up data about temperature, chemistry or sound. Tiny cameras or radars also can be tacked onto the data-collecting network to detect the presence of people or vehicles. The power of these networks is that they eventually can be connected, said David Culler , a computer science professor at UC Berkeley. Culler says the development of these wireless sensor networks is analogous to the creation of the World Wide Web. What's being created with the smart dust idea is a "Real World Web," he said. But he said we're still early on in that progression. "Netscape hasn't quite happened," he said. Big Brother effect Even when deployed for science or the public, some people still get a Big Brother feeling -- the uncomfortable sense of being under constant, secret surveillance -- from the idea of putting trillions of monitors all over the world. "It's a very, very, very huge potential privacy invasion because we're talking about very, very small sensors that can be undetectable, effectively," said Lee Tien , an attorney at the Electronic Frontier Foundation, a privacy advocate. "They are there in such numbers that you really can't do anything about them in terms of easy countermeasures." That doesn't mean that researchers should stop working on smart dust. But they should be mindful of privacy as the work progresses, he said. Pister said the wireless frequencies that smart dust sensors use to communicate -- which work kind of like Wi-Fi -- have security built into them. So the data is public only if the person or company that installed the sensor wants it to be, he said. "Clearly, there are security concerns and privacy concerns," he said, "and the good news is that when the radio technology was being developed for this stuff, it was shortly after all of the big concerns about Wi-Fi security. ... We've got all the security tools we need underneath to make this information private." Further privacy concerns may arise if another vision for smart dust comes true. Some researchers are looking into making mobile phones into sensors. In this scenario, the billions of people roaming the Earth with cell phones become the "smart dust." Bright future Smart dust researchers say their theory of monitoring the world -- however it's realized -- will benefit people and the environment. More information is better information, Pister said. "Having more sensors improves the efficiency of a system and reduces the demand and reduces waste," he said. "So all of that is just straight goodness." Hartwell, the HP researcher, says the only way people can combat huge problems like climate change and biodiversity loss is to have more information about what's going on. "Frankly, I think we have to do it, from a sustainability and environmental standpoint," he said. Even though the first application of HP's "Central Nervous System for the Earth" project will be commercial, Hartwell says the motives behind smart dust are altruistic. "People ask me what my job is, and I say, well, I'm going to save the world," he said.
标签: WSN
