当前位置:首页 >> >> LiteOS based Reliable Software Stack and Visible System Architecture for Wireless Sensor Ne

LiteOS based Reliable Software Stack and Visible System Architecture for Wireless Sensor Ne


LiteOS based Reliable Software Stack and Visible System Architecture for Wireless Sensor Networks
Qing Cao, Ph.D. Candidate, University of Illinois at Urbana-Champaign Advisor: Professor Tarek Abdelzaher

Abstract
This research summary proposes my research on the LiteOS platform, a UNIX-like, multithreaded operating system for wireless sensor networks. My research focuses on two themes: system failure tolerance to provide reliability, and system visibility through interactive commanding. This research summary outlines my ongoing research efforts in these two directions, as well as a concise description of the LiteOS operating system.

1 Research Motivation
My Ph.D. research proposal focuses on research in two directions, building reliable software for wireless sensor networks, and achieving system visibility through interactive operations. To facilitate these research directions, a UNIXlike operating system, called LiteOS, is implemented as the underlying platform. Wireless sensor networks are expected to be deployed for prolonged periods of time in an unattended manner. Because of the limited system resource on sensor nodes, debugging and testing wireless sensor network software is particularly challenging. Furthermore, even the most strict debugging still does not guarantee that all bugs are found before deployment. In fact, unexpected changes in the environment where sensor nodes are deployed can also introduce inconsistencies with the assumptions made by the system, which may cause system faults. A systematic approach to detect and recover from system faults is therefore needed, which motivates the ?rst research direction in my PhD thesis, namely, improving software robustness and reliability in wireless sensor networks. The second challenge we address is system visibility. For the past several years, system visibility, i.e., providing insight on the internal system operations, has been a task of debugging tools and applications. In cases where diagnosis information is not provided by applications or the debugging software, however, the sensor network appears like a black box. In the second research direction, we probe this black box at the operating system level by building interactive services to allow various system information, such as current running threads, to be accessible to the user through Unixlike commands. In these two directions, more speci?cally, we propose the following research topics. In the ?rst direction, we propose an architecture to systematically detect a wide range of application faults through memory speci?cation rules. For example, suppose that a node encounters a sensor problem, it can no longer detect any event despite that all its neighbors can. Suppose that the number of event detections is represented by a variable on each node, a memory rule should compare the values of this variable on nodes within one-hop neighFigure 1. LiteOS Operating System Architecture borhood, and a difference that is signi?cant enough implies a sensor fault has been detected, assuming that the event to be detected is strong enough that every node in one-hop neighborhood should have similar detection results and that the sensors on nodes have similar sensitivity. In the second direction, we propose interactive services that are built directly into LiteOS to support user level collection of system information. Such information could range from thread status to energy consumption pro?ling of different modules. In LiteOS, a kernel serves as a supervisor of all user thread activities. It is therefore intuitive to revise this kernel thread to provide such interactive services. To facilitate the above research work, we implemented a new operating system platform, called LiteOS, and the work above will serve as extensions. When implementing the LiteOS platform, we consider it bene?cial to create a familiar environment for users where they can interactively command the entire sensor network to perform tasks such as reprogramming, data retrieval, or network recon?guration. To this end, LiteOS implements a UNIX-like environment, which could potentially expand the circle of sensor network application developers by reducing learning curves. Further, LiteOS leverages the knowledge that users may already have, i.e., Unix and threads, an approach not unlike the network directions taken by companies such as Arch Rock (that superimpose a familiar IP space on mote platforms to reduce the learning curve of network programming and management). The rest of this proposal is organized as follows. In Section 2, we describe the LiteOS platform infrastructure. We then outline in Section 3 the two aforementioned research directions. Finally, in Section 4, we conclude this summary.

2 LiteOS Platform
This section presents the LiteOS platform. It is organized as follows. First, we describe an architectural overview of LiteOS. Second, we present a brief introduction to its subsystems.

Table 1. Shell Commands
Command List File Commands Process Commands Group Commands Environment Commands Security Commands ls, cd, cp, mv, rm, mkdir, touch, chmod, pwd, du ps, kill, exec foreach, $, | history, who, man, echo login, logout, passwd

2.1 Architectural Overview
Figure 1 shows the overall architecture of the LiteOS operating system, partitioned into three subsystems: LiteShell, LiteFS, and the kernel. Implemented on a base station, the LiteShell subsystem interacts with sensor nodes only when a user is present. Therefore, LiteShell and LiteFS are connected with a dashed line in this ?gure. LiteOS provides a wireless node mounting mechanism (to use a UNIX term) through a ?le system called LiteFS. Much like connecting a USB drive, a LiteOS node mounts itself wirelessly to the root ?lesystem of a nearby base station. Moreover, analogously to connecting a USB device (which implies that the device has to be less than a USBcable-length away), the wireless mount works only for devices within wireless range. The mount mechanism comes handy, for example, in the lab, when a developer might want to interact temporarily with a set of nodes on a table-top before deployment. While not part of the current version, it is not conceptually dif?cult to extend this mechanism to a “remote mount service” to allow a network mount. Ideally, a network mount would allow mounting a device as long as a network path existed either via the Internet or via multi-hop wireless communication through the sensor network. Once mounted, a LiteOS node looks like a ?le directory from the base station. The shell, called LiteShell, supports UNIX commands, such as copy and move, executed on such directories. The external presentation of LiteShell is versatile. While the current version resembles closely a UNIX terminal in appearance, it can be wrapped in a graphical user interface (GUI), appearing as a “sensor network drive” under Windows or Linux.

2.2 LiteOS Subsystems
LiteShell Subsystem: The LiteShell subsystem implements a Unix-style shell for MicaZ-class sensor nodes. Currently, 23 commands, as listed in Table 1, are implemented. We brie?y introduce ?le operation commands as an example. File Operation Commands: File commands generally maintain their Unix meanings, e.g., the ls command lists directory contents. Typing man ls in the shell returns the manual information of the ls command. It supports the -l option to display detailed ?le information, such as type, size, and protection. To reduce system overhead, LiteOS does not provide any time synchronization service, which is not needed by every application. Hence, there is no time information listed. A ls -l command returns the following:
$ ls -l Name Type usrfile file usrdir dir Size 100 --Protection rwxrwxrwx rwxrwx---

For instance, the usrdir directory can be read or written by users with levels 2 and 3. The chmod command can be used to change ?le permissions. Once sensor nodes are mounted, a user uses the above commands to navigate the different directories (nodes) as if they were local. The base station PC also has directories, such as drives C and D. Some common tasks can be greatly simpli?ed. For example, by using the cp command, a user can either copy a ?le from the base to a node to achieve wireless download, or from a node to the base to retrieve data results. The remaining ?le operation commands are intuitive. Since LiteFS supports a hierarchical ?le system, it provides mkdir, rm and cd commands. LiteFS Subsystem: Similar to the Unix-like shell, the interfaces of the ?le subsystem, LiteFS, resemble Unix closely, providing support for both ?le and directory operations. Kernel Subsystem and System Calls: The LiteOS kernel supports threads, and implements two different scheduling policies: priority-based scheduling and round-robin scheduling. The kernel also supports dynamic loading of user threads. It maintains a map of system resource allocation, including both its program ?ash and RAM. To dispatch a thread, it copies thread information into a free control block. When a thread terminates, it frees allocated resources for this thread, by marking its occupied resource as available. It also forcefully closes previously opened ?le pointers by this thread, if there are any. We also introduce lightweight system calls to address software compatibility between different versions. Because the MicaZ CPU does not support soft interrupts or traps, our implementation is based on revised callgates, a special type of function pointers. These callgates are the only access points through which user applications access system resources. Therefore, they implement a strict separation between the kernel and user applications. As long as the system calls remain supported by future versions of LiteOS, user binaries do not need to be recompiled. Currently, each system call gate takes 4 bytes, with 1024 bytes of program space allocated for at most 256 system calls. Each system call adds 5 instructions (10 CPU cycles), a low overhead to be supported on MicaZ.

3 Research Directions
This section outlines my research work based on the LiteOS platform, organized into three topics: detection of application failures using memory speci?cation rules, ?le system assisted communication stacks for fault isolation, and interactive commanding service to improve system visibility. Cooperative Diagnosis of Application Failures using Memory Speci?cation Rules The ?rst research direction focuses on detection of application failures. Its key idea is derived from real life. We all have an immune system that protects us against diseases. Further, our human society has created very complicated medical systems, including doctors and medicine, to diagnose and treat diseases. Not every person is a doctor, of course. Therefore, the medical system is inherently cooperative: people not only get help from themselves through medical knowledge and their immune system, but also from

In this example, there are two ?les in the current directory (a directory is also a ?le): usr?le and usrdir. LiteOS enforces a simple multilevel access control scheme. All users are classi?ed into three levels, from 0 to 2, and 2 is the highest level.

more specialized facilities such as hospitals, to keep healthy. It is bene?cial if we could create a similar system for wireless sensor networks to increase its expected system lifetime. Our proposed approach, which relies on memory speci?cation rules to detect application bugs (illness), works in a two-tiered way. The ?rst tier works at the node scale, where the user creates memory rules to detect unhealthy (buggy) state. Such rules are analogous to human medical knowledge. The second tier, on the other hand, allows nodes to cooperate with each other to detect more delicate bugs that would not otherwise be detected. For example, if a node ?nds that in the past ten seconds it has not detected any event, but all its neighbors have reported multiple detections, then either this node is located in a void area or it has a bad sensor. Such a scenario may need to be logged as a warning. Another example is in group-management protocols, such as EnviroTrack, at most one leader node is allowed to be elected in one-hop neighborhoods. If more than one node sets its leader ?ag as true in one-hop neighborhood, an application fault is detected. Both examples can be expressed using memory rules that are checked against at runtime. Normally memory rules are stored in LiteFS. The kernel reads memory rules when needed to detect failures. Once a failure is found, the kernel may use one of the following approaches as treatment. First, it could give the thread “medicine”, by forcefully modifying certain variables back to the normal state. Second, the user may want to collect early warnings of a failing system to ?nd bugs. To do this, the kernel continuously snapshots thread information until it fails. Third, A user may have anticipated this bug and provided alternative modules, such as the second communication stack. The kernel then loads the new stack into the memory as a backup. File System Assisted Communication Stacks for Fault Isolation It has been challenging to design energy-ef?cient and ?exible communication stacks for wireless sensor networks, due to both hardware limitations and energy constraints. In this research effort, we propose to implement a ?le system assisted communication stack for wireless sensor networks. Instead of hard-wiring the communication stack into application logic as a layer, the new approach allows different stacks to be dynamically chosen and loaded at run time in an adaptive manner. More speci?cally, an entire communication stack is implemented as a ?le. The application speci?es which ?le to use, which is in turn loaded at run-time, making it particularly ?exible to respond to environment changes. This approach has the following advantages. First, because communication stacks can be dynamically loaded, they achieve natural fault isolation, because bugs in a communication protocol can be safely removed by replacing one communication stack with a backup without changes to the application. Second, this approach provides an avenue where different communication stacks can be directly compared in terms of their performance and overhead, which was previously much harder if communication stacks were implemented as part of the application. Interactive Commanding Service for System Visibility In this research topic, we explore how to make a system

information more visible at the operating system level. Currently, the LiteOS platform already allows the user to perform tasks when a node is located within one-hop neighborhood of the base station. In this research direction, we aim to provide a more powerful commanding service that achieves the following goals. First, we intend to implement this commanding service over multiple hops. With this service, a user can task the entire sensor network without being physically within one hop radius of each node. Second, we aim to optimize the commanding service when tasking a group of nodes. One optimization goal is to minimize the communication energy cost. Under such a scenario, the problem of reliably delivering commanding packets to multiple nodes becomes a manycast problem, whose solution requires careful tradeoffs between energy consumption, delay, and throughput. Third, we explore how to improve system level visibility through this interactive commanding service. While certain information, such as the current variable values on several nodes, can be easily retrieved, other information, such as the underlying mechanism of a protocol behavior, requires multiple nodes to log certain critical state information at runtime. Tasking such logging behavior could be far more complicated, and requires careful runtime energy cost optimizations to balance its cost and performance.

4 Conclusions
Above all, this research summary outlines the two research directions we intend to pursue based on the LiteOS platform. These research directions are challenging for the following reasons. First, we need to provide extensive evaluation of the research directions as well as the LiteOS platform. Comparison with existing similar platforms, such as TinyOS, Mantis, and SOS, is also important. Because Mantis and SOS both use C as the main programming language, comparing with them rather than TinyOS might be more appropriate. Second, we need to evaluate the energy consumption of different services carefully, and explore conservation approaches. Because LiteOS uses threads as the basic building block, it may consume more energy in context switches. Pro?ling such energy usage will be particularly important to develop energy conservation protocols and prolong system lifetime.

Acknowledgements
I gratefully acknowledge my advisor, Professor Tarek Abdelzaher, and my shepherd, Professor Philip Levis, on their insightful comments during revision of this manuscript. Brief Biography Qing Cao is a graduate student at the computer science department of University of Illinois at Urbana-Champaign. He got his Masters degree from University of Virginia in 2004. His advisor is Tarek Abdelzaher. His research interest is wireless sensor networks and embedded systems. He is currently working on his Ph.D. thesis, as well as focusing on the development of the LiteOS project. He is the author and co-author of more than ?fteen publications in peer-reviewed conferences and journals. His expected date of dissertation submission is August 2008 or later.

Fair Waiting Protocol: Achieving Isolation in Wireless Sensornets
Jung Il Choi Computer Systems Laboratory Stanford University Abstract
We present the Fair Waiting Protocol (FWP), a novel method of improving visibility through the isolation of competing network protocols on CSMA networks. Sitting between layers 2 and 3, FWP isolates protocols using two mechanisms: grant-to-send and fair queueing. Testbed experiments show FWP can reduce the energy cost of protocol con?icts by up to 93%. Furthermore, FWP can improve protocol performance, increasing the goodput of a TCP-like protocol by up to 108%. Future research issues include the analysis on the optimal quiet times, effects of packet losses, and possible improvements on grant-to-send. Furthermore, as applications need to run multiple concurrent services and protocols, the isolation alone does not guarantee applications run correctly. We also have to provide a fair share of the channel for each protocol: Each protocol should receive its fair share of the channel. In this paper, we propose achieving these goals with the Fair Waiting Protocol (FWP), which sits between layer 3 protocols and a CSMA link layer. FWP has two mechanisms: isolation by grant-to-send mechanism, and fairness by fair queueing algorithm. Section 2 describes Grant-to-send, a general collision avoidance mechanism that uses layer 3 information to prevent future collisions across hops of a ?ow. Section 3 brie?y introduces how FWP uses fair queueing algorithm to achieve fairness across protocols. Section 4 presents initial results of FWP’s effectiveness compared to pure CSMA networks, and Section 5 describes the future directions of the research.

1.

Problem Statement

Sensor network applications are notoriously dif?cult to deploy. Networks commonly have delivery rates of 40-70%, and researchers typically do not know the exact cause of the failures. Management protocols such as SNMS [5] or Sympathy [4] can help diagnose the causes of these failures. However, diagnosing failures within current network architecture is costly, as they can be easily caused by interactions between different components in the system. For example, one can ?nd out that a collection protocol has failed due to the losses of a series of control beacons. However, ?nding out if the failure was due to external interference, selfinterference, interference from other protocols, or just channel variation is non-trivial. The complex interactions between protocols make system composition even harder. Typical network protocols are designed assuming sole use of the channel. Therefore, building a system by simply integrating several network protocols together can easily lead to unforeseen interactions. We therefore need a way of isolating different network protocols in the same way that an OS isolates different processes. If failures can be isolated within protocols, debugging their causes would be much easier, thereby improving network visibility [6]. Moreover, if a protocol operates the same regardless of any other protocols existing in parallel, a sensornet system can be easily built by combining existing protocols into a larger system. Achieving the above goals requires protocol isolation, which we de?ne as: A protocol’s packet delivery ratio should be independent of whether other protocols are operating.

2.

Grant-to-send

Figure 1(a) shows a simple scenario of packet loss due to an intra-path collision. To avoid collisions, nodes must wait until their grandparents forward the previous packet [8]. FWP prevents the intra-path collisions in Fig.1(a) using a mechanism called grant-to-send. When a transmitter wishes to send a packet with FWP, it simply sends it with an additional grant-to-send byte appended to its header. Once this packet has been transmitted, all nodes that overheard it (including the transmitter itself) must wait for some period of time before attempting another transmission. During this quiet time the receiver of the packet is granted the channel to send. In this way, the original transmission grants the channel around the transmitter for the receiver to send. Figure 1(b) shows an example of FWP operating across a route. Although packets are injected at the same time as in Fig.1(a), B’s grant to C forces A to wait, preventing interference along the path. FWP submits packets to the underlying CSMA when all quiet times expire. Many other mechanisms can avoid collisions in this singleprotocol example. For example, protocols such as CTP and MintRoute introduce inter-packet delays. However, preventing self-interference is not enough: concurrently running protocols can still interfere with one another. FWP enables layer 3 protocols to share information by placing an additional collision avoidance layer between layers 2 and 3.

9 6 3 0

0.15 0.1 0.05

B C D Time
CSMA Backoff

X

COLLISION

Transmission

0 C 1 3 5 7 9 11 13 15 17 19 Goodput SingleHop Collision MultiHop Collision

(a) Bare CSMA
Pkt Injected Pkt Injected

Figure 2: The effects of FWP on the performance of a TCP-like protocol on 7-node chain topology of TOSSIM. The x-axis indicates the length of grant-to-send values, with ’C’ indicating bare CSMA. The two lines other than the goodput indicate the number of lost packets due to collision between adjacent or non-adjacent nodes. FWP achieves 108% gain on goodput due to its delivery reliability.

A Data Flow B C D Time
CSMA Backoff TX Quiet Time

4.

Evaluation

(b) Grant-to-send

Figure 1: A collision avoidance example of grant-to-send mechanism. In practice, grant-to-send does not prevent all packet collisions. For example, grant-to-send does not help when two packets converge on one destination from opposite directions. While RTS/CTS provides better collision avoidance, it does not easily support broadcasts, which are a common primitive in sensornet protocols Furthermore, for the small datagram sizes typical of sensor networks, control overhead of RTS/CTS can be large. In contrast, grant-to-send preserves all the ?exibilities of CSMA with only a small overhead of one byte per packet.

In this section, we evaluate the algorithms from the previous section. The performance of grant-to-send on collision avoidance is analyzed with a very simple simulation. Then, we take an existing collection protocol, CTP, and evaluate FWP’s isolation by running multiple CTP instances.

4.1

Grant-to-send

3.

Fair Queueing

Starvation breaks isolation, and preventing starvation requires fairness across protocols. FWP uses the fair queueing algorithm de?ned by Demers et al [1]. As the grant durations can be viewed as channel occupation, FWP keeps track of channel usage on a per protocol basis by adding quiet times and air times of sent and overheard packets. When multiple transmission requests are submitted to FWP, it selects the packet from the protocol with the least channel usage history. The fair queueing algorithm works only if all nodes have the same traf?c pattern. If nodes have different traf?c loads for each protocol, protocols with fewer senders will receive a smaller share of the channel since CSMA enforces a transmission probability across nodes, rather than protocols. To address this limitation of CSMA, FWP forces protocols that have used larger shares of the channel to wait a small penalty time before submitting their packet to the underlying link layer.

Figure 2 shows TOSSIM simulation results for a TCP-like reliable transport protocol running on a simple 7 node line topology. In this simulation, the SNR on all links was high enough that only collisions caused packet losses. Link-layer retransmitted packets at most three times and the packet size was 100 bytes. FWP achieves 2.08 times the goodput of CSMA when the quiet time is 13ms, approximately the maximum packet time. Although most gain in goodput is achieved as the quiet time reaches 4ms, the probability of collision constantly decreases until the quiet time reaches 14ms. The discrepancy between the end-to-end goodput and the probability of collision comes from retransmissions. The ?gure suggests that the hidden terminal problem is a signi?cant cause of collisions for CSMA. FWP effectively prevents the problem and reduces the multihop collision by approximately 81%. There exist some collisions that FWP cannot resolve as mentioned in Section 2, which explains the remaining constant collisions with large quiet times.

4.2

FWP

Figure 3 shows how FWP’s isolation affects the performance of two collection protocols running on the 165-node motelab testbed [7]. The ?gure shows the cost of delivering packets with TinyOS 2.0’s Collection Tree Protocol (CTP) [2] running over bare CSMA and over FWP. In the FWP experiment, data packets have a quiet time of 8ms and routing beacons have a quiet time of zero. Both handle a single instance of CTP well since CTP has built-in rate-limiting mechanisms. However, two instances of CTP running over

Collisions / TX

A Data Flow

Goodput (packets/s)

Pkt Injected

Pkt Injected

12

0.2

30 25 20 15 10 5 0 10

Median Cost

2 CSMA 1 CSMA 2 FWP 1 FWP

21

41

83

165 330

Generation Rate (pps)

Figure 3: Median packet delivery costs - retransmissions per successful transmission - for 1 and 2 instances of CTP running on bare CSMA and over FWP on 165-node network. FWP effectively isolates the two instances from each other to reduce packet retransmissions.

bare CSMA interfere with each other heavily. This is because the rate-limiting mechanisms of CTP are ineffective when another protocol is simultaneously using the channel. It is not the fault of the protocol itself; current network architecture provides no way to deal with the inter-protocol interference. FWP isolates the two instances of the protocol showing lower packet delivery costs. Its suppression mechanism enforces collision avoidance across protocols, limiting the sending rate to what the network can handle. Because FWP drastically reduces the effects of protocols on one another, it simpli?es debugging and makes identifying causes of failure easier, which can improve visibility.

collisions between two ?ows that converge on a node from opposite directions. We plan to explore the extensibility of the algorithm to possibly address the limitation. One interesting application of grant-to-send is request/response protocols. For example, in Deluge [3], if a node ?nds a new version of a binary around it, it transmits a request packet to receive the binary in a burst of packets. In FWP, the requester sends the request with a quiet time of the duration of the burst, then the requester can receive the burst without collisions since the requestee will be the only transmitter around the requester. However, I still need to examine the interactions between Deluge and other protocols. One challenge in fair queueing stems from the dif?culty of de?ning what it means to be fair in a wireless sensornet. Since FWP is a single hop protocol, the concept of a ?ow does not exist. Furthermore, each node has a different view of the channel.

6.

REFERENCES

5.

Research Directions

My current research focuses on understanding the grantto-send mechanism better and exploring ways to improve collision avoidance. The results in Section 4.1 suggest that FWP is a step in the right direction, but there are still many problems yet to be explored. First, it is not clear how to decide what quiet time a protocol should use. In the experiment of Section 4.1, we can expect fewer collisions as the quiet time approaches 14ms, since a packet time is uniformly distributed between 4ms14ms. However, end-to-end goodput shows a different pattern where we gain most of it at the quiet time of 4ms. We are currently analyzing meaning behind the 4ms. It should depend on the number of retransmissions, link qualities, or the topology, but it remains to be one of the important open problems. Second, the simulation results had all perfect links. While the CTP results were from a real network, we need to better understand how lossy links change FWP and quiet time selection. If a recipient could not receive a packet, then the channel is wasted for the quiet time. Furthermore, if a link requires two transmissions on average, it may need to give the quiet time of two packet times. Further research will ?nd the best way to deal with retransmissions. Third, Figure 2 has showed a limitation of the mechanism. That is, grant-to-send mechanism does not prevent the

[1] A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In SIGCOMM ’89: Symposium proceedings on Communications architectures & protocols, pages 1–12, New York, NY, USA, 1989. ACM Press. [2] R. Fonseca, O. Gnawali, K. Jamieson, S. Kim, P. Levis, and A. Woo. TEP 123: Collection Tree Protocol. http://www.tinyos.net/tinyos-2.x/doc/. [3] J. W. Hui and D. Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. In SenSys ’04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 81–94, 2004. [4] N. Ramanathan, K. Chang, R. Kapur, L. Girod, E. Kohler, and D. Estrin. Sympathy for the sensor network debugger. In Proceedings of the Third ACM Conference On Embedded Networked Sensor Systems (SenSys), 2005. [5] G. Tolle and D. Culler. Design of an application-cooperative management system for wireless sensor networks. Proceedings of the Second European Workshop of Wireless Sensor Networks (EWSN), 2005. [6] M. Wachs, J. I. Choi, J. W. Lee, K. Srinivasan, Z. Chen, M. Jain, and P. Levis. Visibility: A new metric for protocol design. In Proceedings of the Fifth ACM Conference on Embedded Networked Sensor Systems (SenSys), 2007. To appear. [7] G. Werner-Allen, P. Swieskowski, and M. Welsh. Motelab: a wireless sensor network testbed. In IPSN ’05: Proceedings of the 4th international symposium on Information processing in sensor networks, page 68, Piscataway, NJ, USA, 2005. IEEE Press. [8] A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. In Proceedings of the seventh annual international conference on Mobile computing and networking, Rome, Italy, July 2001.

Biographical Sketch
Jung Il Choi is a Ph.D. student working in the Stanford Information Networks Group (SING) at Stanford University under professor Philip Levis. His research focuses on sensor networks, especially designing network protocols and the interactions between MAC/network protocols. He received his B.S. in Electrical Engineering from Seoul National University, Korea (2005) and his M.S. in Electrical Engineering from Stanford University (2007). He is currently supported by a Samsung Scholarship.

Smart Attire: Bringing Technology to Your Wardrobe
Raghu K. Ganti Advisor: Prof. Tarek Abdelzaher rganti2@cs.uiuc.edu

Department of Computer Science University of Illinois, Urbana-Champaign

ABSTRACT
With the advent of low power, low cost, and small sensing and computing devices, a new suite of applications that monitor the activities of a person round-the-clock is feasible. Such information sources will drive novel personal monitoring services that enrich the lives of people. These services will enable people to monitor their health (among others), those of their family members, and obtain interesting statistical information from groups of people that they are interested in, subject to the privacy settings of the individuals. An infrastructure support is required for the development of such personal monitoring services. The goal of this thesis is thus to identify the components that are required to enable such services and demonstrate the feasibility thereof.

during events of emergency (such as seizures, strokes, or accidents). Novel services that maintain records of personal activities are feasible. For example, jogging enthusiasts can keep track of their schedules and be able to answer shortterm queries such as, “How much time did I spend jogging in the past month?”. Such personal records can also help in providing medical care, such as detecting early onset of diseases. Entertainment services that answer questions such as, “Where was I on the Christmas eve of 2005?” or “Was I in Olive Garden when I last visited New York?” are feasible. Towards this end, the goal of this thesis is to develop infrastructure and support for wearable personal monitoring services. We believe that the above goal can be further re?ned into four research components, that would compose this thesis. The ?rst part focuses on the design, implementation, and evaluation of a prototype of smart clothing. The second part deals with the human activity identi?cation, where activities performed by the user are determined based on the sensor data inputs. The third part is composed of the portal that is used by the user of smart attire to visualize, search, and share his personal data. The ?nal part is the middleware infrastructure required to support the programmability of smart attire and related applications. Such middleware will provide programming abstractions that will ease the development of applications for smart attire. This is not described in further detail in this research statement, as it is part of the future work of this thesis. A major goal of this thesis is to develop a system that is transparent to the user, in that the user is unaware of the existence of the sensors and goes about doing her daily activities in a normal manner. Thus the application scenario is one in which the daily use items of the user are instrumented with sensors that record the sensory data in their local ?ash memory (or possibly the ?ash memory of devices in their vicinity). When these sensors come in the vicinity of an access mote (a base mote connected to a PC), the logged data is uploaded to a private repository associated with the person through the base mote. A natural delay tolerant personal area network is created as the user is not always connected to a base mote. Analysis algorithms on the private repository identify the activities performed by the user, and trends and patterns in the user’s life. The rest of this statement describes each of the three parts in further detail, outlining the progress for each part, and providing overview of the results obtained, wherever appli-

1.

INTRODUCTION

Wearable monitoring devices (from pedometers and calorie counters to fall-detectors for elderly individuals) are being introduced increasingly to record and sometimes archive di?erent user activities for medical, safety, personal, or entertainment reasons. These devices enable a new range of services that we term as personal monitoring services. Personal monitoring services are software services that enable the monitoring of daily human activities, in the long term, short term, and in real time. The miniaturization of sensors and the emergence of wireless sensor networks in progressively decreasing form factors suggest that the trend of personal instrumentation will expand. Towards this end, we envision di?erent categories of services such as (i) Elderly individuals health care, (ii) Safety, (iii) Personal and medical applications, and (iv) Entertainment. Economic factors such as the approaching retirement of baby boomers and the increasing cost of health-care suggest viable applications of embedded personal instrumentation. An example application is one in which a patient needs to be monitored at home for a prolonged period of time by a caregiver. Safety of people can be improved by providing services which automatically notify health-care providers in real-time

cable. A brief related work for this thesis is provided at the end of this statement.

2.

PROTOTYPE AND SOFTWARE ARCHITECTURE
Activity

I Dont know Cycling Writing Typing Walking Still

The ?rst part of our research is concerned with the design, implementation, and evaluation of a prototype of smart attire. This prototype is in the form of a smart winter jacket embedded with MicaZ motes in an unobtrusive manner. This prototype allows users to maintain a private searchable record of their daily activities as measured by motion and location sensors, which are two of the most popular sensing modalities in personal instrumentation. We identi?ed the architectural requirements of the smart attire prototype and developed a ?exible and modular software solution that uses o?-the-shelf hardware (viz. MicaZ motes). Although, the current simple prototype does not warrant a novel architecture, we believe that future systems that incorporate multiple pieces of clothing with various sensors will necessitate a novel architecture. A major design goal of our initial prototype was to provide a service that is transparent to the user. By instrumenting the user’s attire unobtrusively and implementing transparent information collection, storage, and upload, our service operates with no explicit input or maintenance required from the user. Our current prototype records human activities and location using 2-axis accelerometers and GPS respectively, storing the measurements locally until they can be uploaded. This is achieved using the network of MicaZ motes (embedded in the jacket). All the recorded activity and location data are then subsequently uploaded through an access mote for private archival, from which past human activity and location information can be inferred. The access mote is a wireless gateway with Internet access that implements the information upload protocol on top of an appropriate MAClayer (802.15.4 in the case of MicaZ motes). The activities performed by a person are inferred using Hidden Markov Model based algorithms, which is explained in further detail in Section 3. The jacket is instrumented with ?ve 2-axis accelerometers, which are placed two on each arm, and one in the waist pocket of the jacket. This is to enable us to monitor the motion of the upper limbs and the gait (using the acceleration sensors placed in the waist pocket). A heavy winter jackets is chosen as the prototype as it enables us to embed the MicaZ motes in a completely transparent fashion. Details of the architecture, and prototype implementation can be found in a related publication [5]. We present a snapshot of the user’s life in the form of an activity-time graph below. Figure 1 plots the activity over time for an experiment lasting 350 seconds by an user of the smart jacket prototype. We observe from this ?gure that the user was still (sitting) for 150 seconds, after which he walked for about 75 seconds. He then started writing.

0

50

100

150

200

250

300

350

Time (s)

Figure 1: Snapshot of Activity vs. Time for a user

An interesting problem that we encountered as part of the deployment of our initial prototype is that of human activity identi?cation. Elaborating on this problem: we wish to identify the activity being performed by a person based on the sensor data inputs (generated by the attire of the person). For example, in the case of the smart winter jacket prototype, we wish to ascertain the activities performed by the user based on the 2-axis accelerometer data. The GPS data is only used for location identi?cation and is not fed as an input to the HMM. In order to identify human activities, our ?rst approach was to extract a set of features from the accelerometric signal and use these to identify activities which were well spread out in the feature space. Such an approach has been taken in several contexts, such as in [16, 11]. But, we observed that the accuracy of such an approach was poor, when used to identify multiple activities. The reason for this is two-fold. First, the jacket constraints the placement of the accelerometers, thus making it di?cult to obtain a better acceleration signal, as being done in [11]. The second reason is that a static feature vector approach takes into consideration only the features and not the sequence of observations. To overcome the drawback of using a static feature vector model, we adopt a Hidden Markov Model (HMM) based approach. HMMs are probabilistic models that are used to align and analyze sequential data by generalization from a given pro?le. In our current implementation, a set of features are input to the HMMs. The features used in this implementation are energy of the di?erence signal, and range for each axis of the accelerometers. Each activity is modeled using a single HMM, which is generated by using pro?le data for that activity (this is the training phase of the HMM). The activity performed by a person is identi?ed by using a Forward-Backward procedure ([14]), which given a HMM model, estimates the probability that the observation sequence is generated by that model. Using this procedure, the probability that the observation sequence is generated by the HMM for each of the activities is calculated. The activity that yields the highest probability is chosen as the

3.

HUMAN ACTIVITY IDENTIFICATION

activity represented by the observation sequence. Figure 2 plots the accuracy of the above HMM approach towards activity identi?cation as compared with the traditional feature vector approach. We observe that the accuracy of the HMM approach is better than that of the feature vector approach.
100

The above infrastructure is currently being developed, and when completed, will provide a portal for visualization, search, and sharing of data from smart objects (such as smart winter jackets, smart cars).

5. RELATED WORK
We provide a brief overview of the related work in this section, keeping in mind the space constraints. Our work complements several smart in-home monitoring systems that have been developed and described in recent literature. Examples include the University of Virginia’s Smarthouse [10], Georgia Tech’s Aware Home [8]. These smart homes are built with a suite of non-invasive sensors placed in the environment of a person’s residence, which monitor various human activities. Associated applications include provision of virtual care, where loved ones can be continuously informed about the activities and location of the user. Among other applications, Intel’s proactive health research [6] group has built a wireless sensor network (WSN) for monitoring health care issues related to aging. Our wearable service can augment the data collected by a smart home by providing information regarding the user for periods of time when the user is not in the vicinity of instrumented infrastructure. We classify the activity identi?cation work into three categories, namely camera based motion tracking, inertial sensor based motion tracking, and high end sensors based motion tracking. Several camera based motion tracking techniques [4, 9, 12, 13] have been developed that use cameras strategically placed in the environment which monitor the user’s motion. The image input generated by these cameras are then analyzed to identify the activities of the user. Our work di?ers from camera based tracking in that we want a transparent and un-obtrusive means of human motion tracking. There are a plethora of motion tracking techniques that use gyroscopes and accelerometers in existing literature. To name a few, they include [15, 11, 16, 7]. In [15], a set of strategically placed accelerometers are used to identify the context of the user, which is then used as an input to a tourist guide application that displays information on a PDA. In [11], a set of six accelerometers, microphones, light sensors, and temperature sensors are used to identify the context of the user. In [16], a system of accelerometers are used to identify gestures which are then translated into musical notes. Our activity classi?cation work is constrained by the placement of the accelerometers, which makes it more challenging to develop an activity identi?cation algorithm. Further, when these constraints are relaxed, we believe that we will be able to leverage the above activity recognition algorithms and incorporate them into our system. And, another notable aspect of our work is that we are building a modular software architecture that maintains a private archive of the user’s life, where it would be possible to incorporate new activity identi?cation algorithms (whenever necessary) to improve the accuracy. Finally, high end motion tracking systems such as [3] are very accurate, but very expensive for daily use. Several wearable computers, clothing with sensing and com-

HMM Feature vector

80

Accuracy (%)

60

40

20

0
St illn es s Ty pi ng W rit in g W al ki ng C yc lin g

Figure 2: Accuracy of activity identi?cation using HMMs and feature vectors for user 1

We are currently investigating activity identi?cation algorithms that would enhance the current capabilities in terms of the activities that we can identify and their accuracy. We are also looking into using multiple sensors to improve the activity identi?cation.

4.

FPVIEW: VIEWING THE WORLD FROM A FIRST PERSON PERSPECTIVE

The goal of this thesis, as we have seen earlier, is to develop the infrastructure and support necessary for wearable personal monitoring services. As part of this, an important sub-goal is to provide a portal for the visualization, search, and sharing of the data collected from such smart attire. In the future, we envision that several sensor networks will be deployed that will monitor the objects that they are emplaced on. For example, the smart winter jacket monitors its user’s location and activity information. And, a sensor network (with GPS and accelerometers) in a car monitors the location, and movement details of the car 1 . The goal of our work is to provide a middleware infrastructure for maintaining a web of self-monitoring objects and for archival, analysis, sharing (based on privacy constraints of the users), visualization, and search of data as measured by the sensors emplaced on the objects being monitored. We call this, a ?rst-person monitoring infrastructure (or FPView) in reference to the fact that object monitoring is performed by the objects themselves.
1 Such a sensor network has currently been deployed as part of the on-going work.

puting power embedded in them, have been developed in the past. Examples include, a wearable jacket with a sensor badge [2] that senses perambulatory activities such as sitting, lying, and standing; a cyberjacket that uses context sensors to incorporate a tourist guide application [15]; wrist worn fall detector for elderly individuals [1]. The above are only a few examples of the plethora of wearable computers that exist out there. The goal of our work di?ers from these stand alone wearable computers in that we aim to provide a personal private archive that maintains the user’s activities over the course of her life in a completely transparent and un-obtrusive manner. We hope that these stand alone wearable computers can be integrated (with certain changes) into our broader system that identi?es patterns and trends in the user’s daily life.

[13]

[14]

[15]

[16]

[1] T. Degen, H. Jaeckel, M. Rifer, and S. Wyss. Speedy: a fall detector in a wrist watch. In Proc. of the IEEE International Symposium on Wearable Computers, pages 184–187. IEEE, October 2003. [2] J. Farringdon, A. J. Moore, N. Tilbury, J. Church, and P. D. Biemond. Wearable sensor badge and sensor jacket for context awareness wearable sensor badge and sensor jacket for context awareness. In Proc. of the IEEE international symposium on wearable computers, pages 107–113. IEEE, October 1999. [3] Fastrak. http://www.polhemus.com/. [4] M. Ficocelli and F. Janabi-Shari?. Adaptive ?ltering for pose estimation in visual servoing. In Proceedings of IEEE/RSJ International conference of Intelligent Robots and Systems ’01, pages 19–24. IEEE, 2001. [5] R. K. Ganti, P. Jayachandran, T. F. Abdelzaher, and J. Stankovic. Satire: A software architecture for smart attire. In Mobisys. ACM, June 2006. [6] Intel. Intel’s Proactive Health Research Lab, Intel Research, website available at http://www.intel.com/research/prohealth/. [7] KAIST Wearable Computer. http://core.kaist.ac.kr/ufc/. [8] C. D. Kidd, R. J. Orr, G. D. Abowd, C. G. Atkeson, I. A. Essa, B. MacIntyre, E. Mynatt, T. E. Starner, and W. Newstetter. The aware home: A living laboratory for ubiquitous computing research. In Proc. of the International Workshop on Cooperative Buildings, October 1999. [9] H. Koyusa, J. Miura, and Y. Shirai. Real-time omnidirectional stereo for obstacle detection and tracking in dynamic environments. In Proceedings of IEEE/RSJ International conference of Intelligent Robots and Systems ’01, pages 31–36. IEEE, 2001. [10] MARC. Medical Automation Research Center, University of Virginia, website available at http://www.marc.med.virginia.edu/. [11] U. Maurer, A. Smailagic, D. P. Sieworek, and M. Deisher. Activity recognition and monitoring using multiple sensors on di?erent body positions. In BSN ’06: Proceedings of the International Workshop on Wearable and Implantable Body Sensor Networks, pages 113–116, 2006. [12] I. Mikic, M. Trivedi, E. Hunter, and P. Cosman. Human body model acquisition and tracking using

6.

REFERENCES

voxel data. International journal of computer vision, 53:199–223, 2003. E. Polat, M. Yeasin, and R. Sharma. Tracking body parts of multiple people: A new approach. In Proceedings IEEE Workshop on Multi-Object Tracking (WOMOT ’01), pages 35–42, Vancouver, Canada, July 2001. IEEE. L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proc. of the IEEE, 77(2):257–286, February 1989. C. Randell and H. L. Muller. The well mannered wearable computer. In Proc. of Personal and Ubiquitous computing, volume 6, pages 31–36, February 2002. H. Sawada and S. Hashimoto. Gesture recognition using an acceleration sensor and its application to musical performance control. Electronics and Communications in Japan, 80(5):452–459, 1997.

Biography
Raghu Ganti received his B.Tech. degree in Computer Science and Engineering from the Indian Institute of TechnologyMadras in 2003. He received his M.S. degree in Computer Science from the University of Illinois, Urbana-Champaign in 2006. He has been a graduate student at the University of Virginia, Charlottesville from Fall 2003 to Fall 2005 in the Computer Science department. He moved to the Univerity of Illinois, Urbana-Champaign in Fall 2005. He is currently a Ph.D. candidate at the University of Illinois, Urbana-Champaign. His primary area of research is in the application of wireless sensor networks to human centric computing.

Trust Management in Wireless Sensor Networks
Mohammad Momani Engineering Department University of Technology, Sydney, Australia mmomani@eng.uts.edu.au Abstract
Our research is focusing on modelling and calculating trust between nodes in a Wireless Sensor Network (WSN) based on sensed events. We introduced a new trust model and a reputation system for WSNs based on a sensed continuous data (temperature). The trust model establishes the continuous version of the Beta reputation system applied to binary events and presents a new Gaussian Reputation System for Sensor Networks (GRSSN). We introduced a theoretically sound Bayesian probabilistic approach for mixing second-hand information from neighbouring nodes with directly observed information to calculate trust between nodes in WSNs.

Subhash Challa Engineering Department University of Melbourne, Australia challas@ee.unimelb.edu.au
Simply if there is no cooperation between nodes there is no functioning network. For example if a sensor network is being deployed for target tracking purposes, nodes report to each other about sensed target and then to the other nodes in the routing path until reaches the cluster head and the cluster head then reports to the base station. To get the sensed data to the cluster head from a sensor which is far away from the cluster head, cooperation must occur between nodes to be able to forward the data. And for cooperation to happen between nodes, a trust must exist, which means cooperation influences trust and vice versa. The expected contribution is building a probabilistic framework model to calculate and continuously update trust values between nodes in wireless sensor networks based on the sensed event and to exclude malicious and faulty nodes from the network. In other words, creating a framework to maintain the security and the reliability of a sensor network by examining the trust between nodes, so every node has a trust value for every other node in the surrounding area and based on that value the cooperation occurs between nodes.

Expected contribution to the field of sensor networking
Nodes in WSN are of limited computation and communication capabilities deployed by large numbers especially in hostile areas. Addition and deletion of sensor nodes due to the growth of the network or the replacement of failing and unreliable nodes is an aspect of the dynamic characteristic of such networks. This means the design of a secure communication between nodes of a sensor network is even much harder than of a typical ad hoc network and therefore the trust establishment between nodes is a must. However using the traditional tools of doing things such as cryptographic tools to generate trust evidence and establish trust and traditional protocols to exchange and distribute keys is not possible in WSN due to the resource limitations of sensor nodes. Therefore new innovative methods to secure communication and distribution of trust values between nodes are needed. Trust in WSN plays an important role in constructing the network and making the addition or deletion of sensor nodes from a network very smooth and transparent. Due to the dynamic nature of the WSN (changing topology all the time) and the massive deployment of WSN to sense an event and report data and the characteristics of sensor nodes, coupled with the short range of communications, nodes must cooperate between themselves to finish a certain task.

The problem domain and the specific problem addressed
Wireless sensor networks are open to unique problems due to their deployment in unattended areas. The low cost of the sensor nodes of a WSN prohibits sophisticated measures to ensure data authentication. Some methods used such as cryptographic authentication and other mechanisms [1-6] do not solve the problem entirely. For example, adversarial nodes can have access to valid cryptographic keys. It certainly does not address the reliability issue where sensor nodes are subject to system faults. These two sources of problems, sensor faults and erroneous data or bad routing by malicious nodes, can result in serious malfunctions of the network. A statistical approach to the problem was introduced in the notion of trust. Most studies of Trust in WSNs focused on the trust associated with the routing and the successful performance of a sensor node in some predetermined

task. This resulted in looking at binary events. The trustworthiness and reliability of the nodes of a WSN, when the sensing data is continuous has not been addressed. We look at the issue of security in WSNs using the trust concept, in the case of sensed data that is of continuous nature. We extend an existing trust model for binary events, the Beta Reputation System [7], and introduce a theoretically sound Bayesian probabilistic approach for modelling trust in WSNs.

modelling represents the trustworthiness of each node in the opinion of another node, thus each node associates a trust value with every other node [19], and based on that trust value a risk value required from the node to finish a job can be calculated. In other words trust modelling is simply the mathematical representation of a node’s opinion in another node in a network. Our research introduces a Bayesian probabilistic approach for modeling trust and reputation in wireless sensor networks based on sensed continuous data to address security issues and to deal with malicious and unreliable nodes. It is a statistical answer to problems where encryption and cryptography keys fail to provide a complete solution. The problem of modeling trust is characterized by two sources of information, direct observations and second-hand information. While the former is handled using probability, the latter often is not. We extend the Beta Reputation System introduced in [7], that deals with binary, discrete data, to the case of continuous sensor data, and present a trust model and a reputation system for wireless sensor networks.

Related Work
Trust has been the focus of researchers for a long time. It started in social sciences where trust between humans was studied. The effect of trust was also analysed in economic transactions [8, 9], and Marsh [10] was one of the first to introduce a computational model for trust in his thesis. Then e-commerce necessitated a notion to judge how trusted an internet seller can be [11, 12]. So did Peer-to-Peer networks and other internet forums where users deal with each other in a decentralized fashion [13, 14]. Recently, attention has been given to the concept of trust to increase security and reliability in Ad Hoc [15, 16] and sensor networks [17, 18]. Along with the notion of trust, comes that of Reputation. Reputation is the opinion of one person about the other, of one internet buyer about an internet seller, and by construct, of one WSN node about another. Trust is a derivation of the reputation of an entity. Based on a reputation, a level of trust is bestowed upon an entity. The reputation itself has been build over time based on that entity's history of behaviour, and may be reflecting a positive or negative assessment. In our work, we derive a Bayesian probabilistic reputation system and trust model for WSN. The problem of assessing a reputation based on observed data is a statistical problem. Some trust models make use of this observation and introduce probabilistic modelling such as the trust model RFSN developed by Ganeriwal and Srivastava [17]. The RFSN model presented in [17] uses a Bayesian updating scheme known as the Beta Reputation System [7] for assessing and updating the nodes reputations. The use of the Beta distribution is due to the binary form of the events considered.

Research carried out and results so far
As discussed before, our research introduces a new trust model and a reputation system for wireless sensor networks based on a sensed continuous data. It establishes the continuous version of the beta reputation system introduced in [7] and applied to binary events and presents a new Gaussian Reputation System for Sensor Networks (GRSSN). Trust modelling represents the trustworthiness of each node in the opinion of another node, thus each node associates a trust value with every other node [19], and based on that trust value a risk value required from the node to finish a task can be calculated. As illustrated in Fig. 1, node X might believe that node Y will fulfil 40% of the promises made, while node Z might believe that node Y will fulfil 50% of the promises made.

Methodological Approach
Initially, the primary focus of the research on trust in WSNs was on whether a node will detect appropriately, will report or not the detected event(s), and will route information. The uncertainty in these actions warranted the development of reputation systems and corresponding trust models. Trust
Fig.1: A simple trust map [19]

In other words trust modelling is simply the mathematical representation of a node’s opinion in another node in a network. In our model we are calculating trust based on the continuous sensed data

(temperature) as opposed to all previous work which are calculating trust based on binary events. To introduce our system we consider a sensor network with N nodes (A1, A2, …, AN) deployed to measure an event (temperature for ex.) in a given field it can be an agricultural field, a farm, a factory, etc. even though the intention of our model is to be implemented in a more sophisticated application such as target tracking especially in a battle field where nodes can be capture and replaced by the enemy. Let the corresponding matrix of the network connectivity be as shown in Table 1. Table 1. Network Connectivity

yi , j = ∑ t =1 y i , j (t ) / k
k

(2)

to be the mean of the observed error, as observed by Ai about Aj 's reporting, then
(θ i , j | yi , j ) ? N ( yi , j ,τ 2 / k ) (3)

Where yi , j = {( yi , j (t ) ; for all t values at which a report is issued by Aj}. This is a well known straightforward Bayesian updating where a diffuse prior is used. We let μi , j = yi , j and σ i2, j = τ 2 / k . Recall that k is nodes dependent. It is the number of reports issued by node j, and differs from node to node. We define the reputation as being
Ri , j = N ( μi , j , σ i2, j )
(4)

?1 ? 0 Γ = [Γ i, j ] = ? ?1 ? ?0

0 1 0 1

1 0 1 0

0? ? 1? 0? ? 1?

where μi , j = yi , j and σ i2, j = τ 2 / k are the equivalent of

αij and βij in RFSN.
Trust is defined differently, since we want it to remain between 0 and 1. In this case, we define the trust to be the probability as shown in equation (6).
Ti , j = Prob{|θi , j |< ε }
T i , j = P ro b { - ε < θ i , j < + ε } = ? ε ? yi, j ? ? ?ε ? yi, j ? =φ? ??φ ? ? ? τ / k ? ? τ / k ? (6)

If there is a connection between node Ai and node Aj, then Γi , j = Γ j ,i = 1 , otherwise Γi , j = Γ j ,i = 0 . Let X be a field variable of interest which is of a continuous nature. This variable such as temperature, chemical quantity, atmospheric value, is detected and sensed by the nodes of the WSN and is reported only at discrete times t = 0, 1, 2, k, the random variable XAi = Xi is the sensed value by node Ai. i = 1, … , N. xi(t) is the realization of that random variable at time t. Each node Ai, i = 1, …, N has a time series {xi(t)}. These time series are most likely different, as nodes are requested to provide a reading at different times, depending on the sources of the request. It could also be that the nodes provide such readings when triggered by some events. We assume that each time a node provides a reading, its one-hop neighbours see that report and can evaluate the reported value. For example if node Aj reports xj(t0) at some time t0, then node Al obtains a copy of that report, and has its own assessment xl(t0) of the sensed variable, say temperature. Let yi,j(t) = xj(t)-xi(t). From node Ai's perspective, Xi(t) is known, and Yi,j(t) = Xj(t) - Xi(t) represents the error that node Aj commits in reporting the sensed field value Xj(t) at time t. Yi,j(t) is a random variable modelled as a Normal (Gaussian).
Yi , j (t ) ? N (θ i , j ,τ 2 ) (1)

(5)

The bigger the error θij is, meaning its mean shifting to the right or left of 0, and the more spread that error is, the less the trust value is. Each node Ai maintains a line of reputation assessments composed of Ti,j for each j, such that Γi , j ≠ 0 (one-hop connection). Ti,j is updated for each time period t for which data is received for some connecting node j. In addition to data observed in form of yi , j = {( yi , j (t ) for all t values at which a report is

issued by Aj}, node Ai uses second hand information in the form of ( μls , j , σ ls , j ) , s = 1, …, m from the m nodes connected to Aj . This is an “expert opinion”, that is soft information from external sources. Each of these m nodes has observed node Aj's reports and produced assessments of its error in the form of ( μls , j , σ ls , j ) , s = 1, …, m and consequently Tls,j, s = 1, …, m. In using expert opinion/external soft information, one needs to modulate it.

τ is assumed known, and is the same for all nodes. If we let

Node Ai uses its own assessment of the nodes Al1 ,..., Alm , in the form of ( μi ,ls , σ i ,ls ) , s = 1, … , m and consequently Ti,ls , s = 1, …, m. Using Bayes theorem, the probability distribution of θi,j is obtained, that uses the observed data along with the second hand, modulated information as shown in equation (7).
P (θ i , j | yi , j , ( μl1 , j , σ l1 , j ),..., ( μlm , j , σ lm , j ),
( μi ,l1 , σ i ,l1 ),..., ( μi ,lm , σ i ,lm )) (7)

the reputation parameters are:

μi , j =

2 ( μ0 / σ 0 ) + (kyi , j / τ 2 ) 2 (1/ σ 0 ) + (k / τ 2 )

(11)

σ i2, j =
and

1 (1/ σ ) + (k / τ 2 )
2 0

(12)

By doing some calculations we proved that equation (7) is a Normal (Gaussian) distribution with mean and variance as shown in equations (8) and (9) consequently.
+ (ky / τ 2 ) ? 1 ? ? 1? α ? ? Ti ,l ? ? s ? = m 1 + (k / τ 2 ) ∑ s =1 ? ? 1 ? 1? α ? ? Ti ,l ? ? s ?
s =1

2 ( μ0 / σ 0 ) + ∑ s =1 m

μinew = ,j



m

( μ ls , j + μ i , ls )

+ (kyi , j / τ 2 ) ? 1 ? ? 1? α ? ? Ti ,l ? ? s ? m 1 2 (1/ σ 0 ) + ∑ s =1 + (k / τ 2 ) ? 1 ? ? 1? α ? ? Ti ,l ? ? s ?

( μ l s , j + μ i , ls )

(13)

μinew ,j

(8)

σ i2, j new =

1
2 (1/ σ 0 ) + ∑ s =1 m

1 ? 1 ? ? 1? α ? ? Ti ,l ? ? s ?

(14) + (k / τ 2 )

σ i2, j new =

1



m s =1

1 ? 1 ? ? 1? α ? ? Ti ,l ? ? s ?

(9) + (k / τ 2 )

Simulation Results
To verify our theory we conducted several simulation experiments for different scenarios and we calculated the trust between all nodes in the network and we presented the results from a portion of 4 nodes (1,6,7,13) in a sub-network of 15 nodes as shown in Figure 2.
sensors locations Node 6 Node 1 760 755 750 Node 13 Width (m) 745 Node 9 740 735 Node 8 730 725 720 725 730 Node 15 Node 10 Node 12 735 740 Length(m) 745 Node 2 Node 11 750 755 760 Node 7 Node 14 Node 4 3 Node

These values ( μinew , σ i2, j new ) along with ( μi , j , σ i2, j ) are ,j easily updatable values that represents the continuous Gaussian version of the (α i , j , β i , j ) and (α inew , β inew ) of ,j ,j the binary approach in [17], as derived from the approach in [7]. The network topology and protocols follow those of [17, 18]. The solution presented is simple, and easily computable. This is with keeping in mind that the solution applies to networks with limited computational power. Some would object to the use of a diffuse prior, which in effect, forces a null prior trust value, regardless of the ε value. A way to remedy to 2 this is to start with a N ( μ0 , σ 0 ) prior distribution for all θij, such that the prior trust is 1/2. This choice not only answers the diffuse prior issue, but also allows the choice of the parameters involved. ε can be determined, given μ0 and σ0. μ0 is most likely to be set to 0. Therefore, σ0 and ε determine each other. With a proper prior

Node 5

θi , j ? N ( μ0 , σ 02 )

(10)

Fig. 2: Wireless Sensor Network Diagram

First, we assume that all nodes are working properly and report the sensed event with only a small reading error. Simulation showed that the trust values of node 1 for the other nodes (6,7,13) are slightly different but converge to 1 as can be seen in Figure 3. As can be seen from the results presented in Figures 3,4 and 5, the second scenario (when all nodes in the network are reporting at each time series) is giving more precise results as the trust is updated for all nodes at each time series.
Trust between node 1 and node 13 Trust value 1 0.5 0 10 20 30 40 with second hand information without second hand information 50 60 70 Time Trust between node 1 and node 7 80 90 100

two nodes is high. This is an interesting case as both nodes (13,7) are assessing node 1 as a faulty node. The trust value for node 6 is set to the initial value of (0.5) and will decrease to zero as there is no second hand information available about node 6.
Trust between node 1 and node 13 Trust value 1 0.5 0 10 20 30 50 60 70 Time Trust between node 1 and node 7 40 80 90 100

Trust value

1 0.5 0 10 20 30 40 50 60 70 Time Trust between node 1 and node 6 80

with second hand without second hand

90

100

Trust value

1 0.5 0 10 20 30 40 50 Time 60 70 80 90 100

Trust value

1 0.5 0 10 20 30 50 60 70 Time Trust between node 1 and node 6 40 80 90 100

Fig. 5: Node 1 is a malicious node

Trust value

1 0.5 0 10 20 30 40 50 Time 60 70 80 90 100

Fig. 3: All nodes are normal

In other experiments, we assume that nodes 7 and 13 are faulty. The results of the simulation are presented in Figure 4 and show the trust value for nodes 7 and 13 dropping to zero. Node 6 is assumed reliable, and its corresponding trust value follows a growing path that eventually reaches 1.
Trust between node 1 and node 13 Trust value 1 0.5 0 10 20 30 40 with second hand information without second hand information 50 60 70 Time Trust between node 1 and node 7 80 90 100

In the last example shown in Figure 5, we do know that node 1 is faulty, since it is a simulation exercise. The results clearly should indicate to the network that node 1 is faulty. However, it could also be the case that nodes 7 and 13 are malicious. The trust system works on the assumption that a majority of nodes in a neighbourhood are reliable. This principle helps purge the system of bad elements. In our case, at this point in time, we observe that the trust system we developed is effective in distinguishing among nodes.

Conclusion
The trust system works on the assumption that a majority of nodes in a neighbourhood are reliable. In our case, at this point of time, we observe that the trust system we developed is effective in distinguishing among nodes. In future research, we will try to map our trust network with a Bayesian network to be able to address the issue of how to decide on the deleting or keeping nodes in WSNs.

Trust value

1 0.5 0 10 20 30 40 50 60 70 Time Trust between node 1 and node 6 80 90 100

Trust value

1 0.5 0 10 20 30 40 50 Time 60 70 80 90 100

References
[1] M. a. T. Bohge, W., "An authentication framework for hierarchical Ad Hoc sensor networks," presented at Proc. 2003 ACM workshop Wireless security,, San Diego, CA, USA,, 2003. C. Karlof and D. Wagner, "Secure routing in sensor networks: Attacks and countermeasures," presented at First IEEE

Fig. 4: Node7 and node 13 are faulty

As can be seen from Figure 5, the trust value from the direct information reaches zero for both nodes 7 and 13. This is because node 1 is faulty, and contradicts nodes 7 and 13 based only on direct information. However, using second information, the trust for these

[2]

[3] [4]

[5]

[6]

[7] [8]

[9]

[10]

[11]

Int. Workshop on Sensor Network Protocols and Applications, 2003. C. Karlof, N. Sastry, and D. Wagner, "TinySec: A Link Layer Security Architecture for Wireless Sensor Network ". A. Perrig, R. Zewczyk, V. Wen, D. Culler, and D. Tygar, "SPINS: Security Protocols for Sensor Networks," Wireless Networks, vol. 8,(5), pp. 521-534, 2002. F. Ye, H. Luoa, S. Lu, and L. Zhang, "Statistical en-route filtering of injected false data in sensor networks," IEEE Journal Selected Areas in Communications of the ACM, vol. 23, 2005. Y. Zhang, W. Liu, W. Lou, and Y. Fang, "Location-based compromise tolerant security mechanisms for wireless sensor networks," IEEE Journal on Selected areas in Communications, vol. 24, pp. 247-260, 2006. A. J?sang and R. Ismail, "The Beta Reputation System," in 15th Bled Electronic Commerce Conference. Bled, Slovenia, 2002. S. Ba and P. A. Pavlou, "Evidence of the effect of trust building technology in electronic markets: price premiums and buyer behavior," MIS Quarterly, vol. 26, 2002. P. Dasgupta, "Trust as a commodity," in n Gambetta, Diego (ed.) Trust: Making and Breaking Cooperative Relations, vol. electronic edition, D. Ingram, Ed.: Department of Sociology, University of Oxford,, 2000, pp. 49-72. S. Marsh, "Formalising Trust as a Computational Concept," in Departmet of Computer Science and Mathematics, vol. PhD: University of Stirling, 1994, pp. 184. D. H. McKnight and N. L. Chervany, "Conceptualizing Trust: A Typology and ECommerce Customer Relationships Model," presented at Proceedings of the 34th Hawaii
International Conference on System Sciences - 2001, 2001.

[16]

[17]

[18]

[19]

[20]

[21]

presented at 3rd ACM int. symp. Mobile ad hoc networking & computing, 2002. P. Michiardi and R. Molva, "CORE: A Collaborative Reputation Mechanism to enforce node cooperation in Mobile Ad hoc Networks," 2001. S. Ganeriwal and M. B. Srivastava, "Reputation-based Framework for High Integrity Sensor Networks," presented at the 2nd ACM workshop on Security of ad hoc and sensor networks Washington DC, USA 2004. A. Srinivasan, J. Teitelbaum, and J. Wu, "DRBTS: Distributed Reputation-based Beacon Trust System," in 2nd IEEE International Symposium on Dependable, Autonomic and Secure Computing (DASC'06), 2006. B. N. Shand, "Trust for resource control: Self-enforcing automatic rational contracts between computers," University of Cambridge Computer Laboratory UCAMCL-TR-600, 2004. M. Momani, K. Aboura, and S. Challa, "RBATMWSN: Recursive Bayesian Approach to Trust Management in Wireless Sensor Networks," to be presented at The Third International Conference on Intelegent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, 2007. M. Momani and S. Challa, "Probabilistic Modelling and Recursive Bayesian Estimation of Trust in Wireless Sensor Networks," submitted to Ad Hoc Networks, 2007.

Biography
Mohammad is a PhD student in the Engineering Department at the University of Technology, Sydney. His research interests are trust management and security issues in mobile ad hoc networks and wireless sensor networks. He graduated with a M.Sc. in Computer Engineering from Bulgaria in 1986 and a M.Sc. in Internetworking from the University of Technology, Sydney in 2003. He is also a CCNA, MCSE and a CNE certified with almost 20 years of industrial experience in the IT sector. He is also involved in teaching at all levels, TAFE, undergraduate and postgraduate students.

[12]

[13]

[14]

[15]

P. Resnick and R. Zeckhauser, "Trust among strangers in internet transactions: empirical analysis of eBays reputation system," presented at NBER: workshop on empirical studies of electronic commerce, 2000. K. a. D. Aberer, Z. , "Managing trust in a peer-2-peer information system," presented at Ninth Int. Conf. Information and Knowledge Management, 2001, 2001. L. Xiong and L. Liu, "A reputation-based trust model for peer-to-peer e-commerce communities," presented at IEEE conference on E-commerce, 2003. S. Buchegger and J. L. Boudec, "Performance analysis of the CONFIDANT protocol,"

Secure Routing in Directional Sensor Networks
Unoma Ndili Okorafor Department of Electrical & Computer Engineering, Texas A&M University, College Station, Texas 77843-3124 unondili@ece.tamu.edu

Abstract— We describe our current research efforts in the area of secure routing for directional sensor networks (DSNs) in order to overcome the challenge of purely directional links encountered in DSNs. We outline two of our three main area of focus: (1) a probabilistic connectivity analysis on physical network properties (number of nodes, communication radius and beam angle) that guarantee a connected network; and (2) the design of an ef?cient and security aware routing protocol. Preliminary simulation results illustrate the applications and performance of our research.

I. I NTRODUCTION Directional sensor networks (DSNs) represent an emerging subclass of wireless sensor networks (WSNs) comprised of nodes that communicate within a directed and randomly oriented sector, compared with the omni-directional disc communication paradigm often assumed in traditional WSNs [1]. DSNs are rapidly gaining visibility due to the advantages they offer over omni-directional ad hoc WSNs, and their potential application to broadband multimedia sensor networking. Signal directionality signi?cantly increases the potential for spatial reuse, reduces communication energy (thereby increasing network lifetime), while providing longer communication ranges, increased signal strength, and reduced multi-path components. Furthermore, security is enhanced in DSNs due to a reduced spatial signature of communication energy, thereby greatly reducing the chances of eavesdropping [1]. Two common scenarios under which DSNs occur are; (1) directional radio frequency (RF) employing directed RF antennas which show potential for dramatically increasing throughput, and; (2) free space optical sensor networks (FSOSNs) employing directed line-of-sight laser beams, which realize ultra-high bandwidths that bene?t emerging real-time multimedia and visual sensor network applications. A. Directional Sensor Network Model As commonly assumed, a set Sn = {si : i = 1, 2, · · · n} of n directional nodes, are randomly and densely deployed in a two dimensional region according to a Uniform distribution. Each node si ∈ Sn has an equal and independent likelihood of falling at any location Υi ? Uniform(0, 1)2 , and facing any orientation Θi ? U(0, 2π]. The resulting n-node multi-hop DSN, de?ned by parameters n, r and α has been modeled as a random scaled sector graph [2]. Each DSN node si employs a directed transmitter to send data within a contiguous, randomly oriented sector ?α + 2 Θi ≤ Φi ≤ +α + Θi of radius r, and ?xed angle α ∈ 2 [0, 2π] radians, where Φi is completely de?ned by the 4-tuple

(Υi , Θi , r, α). The receiver is omni-directional implying that si may directly transmit to sj (denoted si → sj ) if and only if Υj ∈ Φi . However, sj communicates to si via a multihop reverse route, with other nodes acting as routers along the reverse path (unless of course Υi ∈ Φj ). The directional communication paradigm requires that two distinct set of neighbors be de?ned for each DSN node si : successors who hear si and predecessors who transmit to si . The case α = 2π represents the conventional omni-directional communication paradigm, modeled as a geometric random graph (GRG), in which successors are equivalent to predecessors, simply termed neighbors. B. Problem Statement One of the major challenges faced in DSNs is that the underlying network graph consists of links that are mainly unidirectional, thereby complicating secure neighborhood discovery and secure route set up. In contrast to traditional omnidirectional WSNs in which links are necessarily bi-directional (i.e., if node A hears node B, then node B necessarily hears node A), a DSN node cannot immediately determine other nodes who receive its packets using straightforward passive or active listening, and link layer acknowledgements are deemed non-trivial, creating huge overheads. In this scenario, a reverse path must be ef?ciently and securely discovered. Conventional routing schemes based on topology discovery with ”HELLO” packet broadcast and reverse path forwarding, such as DSDV, DSR, OLSR, etc., which work well for omnidirectional networks by heavily utilizing the reversibility of links, simply do not translate to DSNs. Furthermore, it is well known that incorporating security mechanisms after the design of routing schemes is often inef?cient, unsatisfactory and super?cial at best. Secure routing is crucial for sensor networks given the possibility of an unsecured or hostile deployment environment, the vulnerability of nodes to physical capture and tampering, and the susceptibility of the wireless medium to various attacks. The collaborative nature of communication in sensor networks makes routing attacks especially debilitating, requiring that security be considered during route setup and algorithm design. Under the DSN paradigm secure routing is even more challenging as an attacker may exploit the inherent initial delay in neighborhood discovery to disrupt network activities. Before secure routing and other network layer protocols can be addressed however, an accurate modeling of the physical layer is important to assess the feasibility of DSNs. Con-

nectivity, de?ned to mean that a path exists between any pair of network nodes, is of particular signi?cance in order to maintain communication among nodes. For the DSN, we ask the topology question, what is the pair value of a node’s communication range r and beam width α such that the DSN of density n is connected? Obviously, connectivity analysis is crucial as the starting point of any network layer design and network level simulations that test routing algorithms. 1) Scope of Work: Within our problem formulation, we then are able to identify three areas of focus addressed in our research as follows: 1) Probabilistic connectivity analysis of DSNs in order to determine a methodology for parameter (r, α, n) assignment to guarantee a connected network. 2) Development of a secure and ef?cient routing heuristic for DSNs, with the following objectives: ? minimize the communication, computational and storage requirement at the node, while optimizing an objective function (e.g., number of hops). ? Easily recon?gurable network to maintain network connectivity by employing multi-paths. ? leverage link directionality and carefully designed cryptographic primitives to ensure a network that is robust to several routing and denial of service attacks. ? provide con?dentiality, integrity, freshness and authentication of routing signals, and prevent the spoo?ng or illegal manipulation of routing signals. ? quickly detect intrusion or malicious node activity. ? robust and resilient, rapidly isolate rouge nodes, reroute packets and recover from attacks. 3) Known and novel security and attack analysis and synthesis on routing scheme. II. R ESEARCH S O FAR A. Connectivity Analysis on DSNs Our contribution in this area is the probabilistic study of the overall connectivity of the DSN and its relation to the node isolation property. A known and important approach to probabilistic connectivity of ad hoc networks studies the conditions under which no isolated node occurs, as a necessary albeit insuf?cient condition for connectivity. This is because recent studies have shown that for dense networks (n large), with high probability the network is connected at the moment it achieves no isolated node [3]. Simply stated, this result implies that the probability that no isolated node occurs pd provides a tight upper bound for the probability that the network is connected pc , for large n and probabilities close to one [3], and motivates our study of the relationship among network parameters r, α, n that guarantee with high probability a ”no isolated node” property for DSNs. The fundamental question we address in our research so far, and which is of practical importance in network-level simulation of DSNs, is: How may network parameters be chosen so that with high probability pd , there is no isolated node?

TABLE I rmin
THAT ACHIEVES A . S . NO ISOLATED NODES IN A

DSN

FOR VARYING

n AND α VALUES nα 100 500 1000 5000 10000 100000
π 9 2π 9 π 3 π 2 3π 4

.744 .359 .262 .125 .091 .031

.522 .252 .184 .088 .064 .022

.423 .205 .149 .072 .052 .018

.344 .167 .122 .058 .042 .015

.280 .136 .099 .048 .035 .012

π .243 .118 .086 .041 .030 .011

3π 2

.198 .096 .070 .034 .025 .009

2π .172 .083 .061 .029 .021 .008

In our analysis, we separately consider the distinct neighborhoods (successors and predecessors) of a DSN node, in contrast to the connectivity analysis in omnidirectional WSNs. For the n-node DSN, we obtain [4] the probability pd that there is no isolated node as a function of network parameters: Theorem 2.1: There is no isolated node in the DSN with probability pd : pd = 1?e
?nαr 2 2

n

1?e


?nαr 2 2

1?


α 2π

n?2

2 2 nαr 2 α ? nα r 4π ?1 (1) e 2 2π For α = 2π (omnidirectional case), pd reduces to (1 ? 2 e?nπr )n as obtained in [3]. Therefore, we have derived in Theorem 2.1 the general expression relating network parameters n, r and α with pd for DSNs, which enables us determine appropriate parameter values to ensure with a given con?dence, that the DSN is connected.

n

?e?nαr

2

B. Results An example: Figure 1(a) illustrates pd for a range of r and α values based on equation 1, for n = 500 where the red line on the (r ? α) plane of the mesh plot indicates the (r, α) pair values for which pd ≥ 0.99. Suppose we need to design a 1000-node DSN and guarantee that 99% of the nodes are connected. From equation 1, we obtain minimum r and corresponding α required for pd ≥ 0.99 for given n values, shown in Table I. Observe that for n = 1000 with α = 2π/9, pd ≥ 0.99 is achieved with r ≥ 0.184m. If however the nodes are only capable of r = 0.09m, then we must increase α to 3π/4, otherwise, we must deploy at least 5000 nodes, in order to attain the same pd con?dentiality. We observe that to maintain the same network connectivity, doubling r allows us reduce α by a fourth. As previously stated, it was shown in [3] that (pc = p?) ≤ (pd = p?) for p? close to one. To determine the tightness of this bound for the DSN with various α values, we employ Monte Carlo simulations (1000 trials) to model the DSN, and empirically measure pd as (1 - number of isolated nodes/n), and pc as the number of nodes in the largest strongly connected component of the DSN. Our simulation results for three different scenarios (α = 40o , 180o , 360o ) are depicted in Figure 1(b-d), and validatesthe correctness of our analytical derivations. We observe that there is a nonnegligible difference between pd and pc at low probability

Showing pd and pc for varying r values with n = 500, α = 360o 1 0.9 0.8 0.7 Probability Probability 0.6 0.5 0.4 0.3 0.2 0.1 pc 0 0 0.05 0.1 r (in m) 0.15 0.2 0 0 analytical?pd simulation?p
d

Showing pd and pc for varying r values with n = 500, α = 180o 1 0.9 0.8 0.7 Probability 0.6 0.5 0.4 0.3 0.2 0.1 pc 0.05 0.1 r (in m) 0.15 0.2 0 0 analytical?pd simulation?p
d

Showing pd and pc for varying r values with n = 500, α = 40o 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.1 0.2 r (in m) 0.3 analytical?pd simulation?pd p
c

0.4

0.5

(a) n = 1, 000 Fig. 1.

(b) α =

360o

(c) α =

180o

(d) α =

40o

Comparing the probability pc that the network is connected to the probability pd that there is no isolated network node (simulated and analytical).

and α values. This means that: (pc = p?) = (pd = p?) + for ≥ 0, → 0, p? → 1, and α → 2π.

?

In conclusion, we state that it is suf?cient to compute the minimum parameter values that achieve a given pd , and use this as a tight lower bound for the parameter values required to achieve the same pc con?dence, only for large α values and probabilities close to one. Otherwise the minimum parameter values must be signi?cantly increased to attain the same pc con?dence level. C. Secure Routing Protocol for DSN Our current work focuses on the design and evaluation of OPSENET, a security-aware neighborhood discovery and routing protocol that leverages hierarchy with some nodes acting as cluster heads (CHs), and the powerful and resourcerich base station (BS). Based on the novel concept of a base station circuit, which is a directed loop that originates and terminates at the base station, we leverage directionality to enhance secure routing. OPSENET employs one-way key chains and individual symmetric keys to provide per hop and broadcast authentication, integrity of routing signals, as well as defend against unauthorized participation or spoofed, altered or replayed route signals. Furthermore, the algorithm reveals the optimal BS-circuit for each node. We give a brief description of the OPSENET protocol:
?

Multicasting Routing Information Packets (RIPs): BS constructs and multicasts secure RIPs containing individually secured information on the optimal BS-circuit for each node. Returned RIPs act as acknowledgements to detect and prevent black hole and denial of service attacks.

D. Novelty Our work is the ?rst we are aware of to address secure routing in DSNs leading to novel analytical design insights and algorithmic contributions. The formulation of our setup incorporates innovative approaches based on the BS-circuit, and a routing philosophy which heavily leverages hierarchy and the powerful BS. By pushing more complexity and processing to the BS, our algorithm is lightweight at the nodes. E. Research Methodology In carrying out our research we survey existing related research as a framework. In particular, we study and apply proven mathematical tool sets from statistical analysis, probability theory, graph theory, optimization theory and algorithms in our research so far. We currently employ network simulations built with programming software (matlab and C#) to investigate our connectivity analysis and evaluate our proposed routing and security algorithms. III. R ELATED W ORK Our interest in this research area was sparked by the work of Pister et. al [2] who introduced the idea of directional line-of-sight FSOSN which consists of very small nodes capable of ultra-high bandwidths that consume much less energy than existing sensor nodes. FSOSNs are a common type of DSNs. Serna et. al. [2] employed a graph theoretic approach to model the FSOSN, and provide connectivity analysis based on asymptotic reasoning. Our research takes a different approach to connectivity analysis of DSNs based on probabilistic arguments, extending the work of Bettstetter et. al [3] which considered a probabilistic connectivity analysis for simple omni-directional WSNs. Our work also introduces novel secure routing strategies for the DSN based on a BScircuit that leverages link directionality. To the best of our knowledge, this is the ?rst time secure routing has been studied for the DSN model.

?

?

?

Initialization and key setup: Base Station pre-generates and 1 stores a one-way key chain with K1 as the commitment to the key chain. Each node si is pre-deployed with an individual symmetric key Ki shared with the BS, a counter Ci initialized 1 to a random value (known to the base station), and K1 . BS ?oods the network with routing beacons (CDPs) via cluster heads (CHs). Flooding Routing Beacons (CDPs): When si receives a CDP not previously processed, it increments its Hops Traversed (HT) ?eld by one, appends its information I(S) (identity and location) in the CDP’s payload, and rebroadcast to its successors, else it drops CDP. Terminating Routing Beacons: CDP routes are terminated when the CDP expires (i.e., number of hops exceeds prede?ned constant, or it reaches an (exit) CH who completes the BScircuit by forwarding the CDP back to the BS. Base Station Network Topology Construction: Given I(S) extracted from all returned CDPs, the BS constructs approximate graph topology and performs route optimizations.

A. Expected Contribution to Sensor Networking Field Through our research investigation, we demonstrate the following fundamental insights for DSNs: 1) Network parameters can be carefully chosen so that the network is guaranteed with a given probability to be connected. 2) Link directionality necessitates circuit-based routing that promotes broadcast messages that originate and terminate at a trusted entity, providing enhanced opportunity for network monitoring and security. 3) Certain classical routing attacks are incompatible with directional routing paradigms, making secure DSN routing a rich ?eld of study where both basic attacks and associated countermeasures must be re-engineered. B. Broader Impacts Our routing protocol facilitates the deployment of ultrahigh bandwidth FSOSNs for visual and multimedia sensor network applications, which have direct impacts in areas such as secure sensing and monitoring of natural disaster areas, surveillance and intelligence gathering, bio-terrorism, as well as remote military warfare. Our work is also applicable to robust hybrid RF/FSO networks which are of interest to organizations such as the military and NSF. R EFERENCES
[1] J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: Mobile networking for smart dust. InProc. ACM/IEEE Int. Conf. on Mobile Computing and Networking, Washington, pp. 271278, Aug 1999. [2] J. Diaz, J. Petit, and M. Serna, A random graph model for optical networks of sensors, In IEEE Transactions on Mobile Computing, vol. 2, no. 3, pp. 186196, July- September 2003. [3] C. Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, In Proceedings of the 3rd ACM International symposium on Mobile Ad Hoc Networking & computing pp. 80-91, Lausanne, Switzerland, 2002. [4] U. Ndili Okorafor, and D. Kundur, On the Connectivity of Hierarchical Directional Sensor Networks, In Proceedings of Wireless Communications and Networking Conference, WCNC 2007, pp. 3524 - 3528. Hong Kong, March 2007

B IOGRAPHY Unoma Ndili Okorafor received the M.Sc. degree in Electrical Engineering from Rice University, Houston Texas in 2001, and the B.Sc. degree in Electrical Engineering from the University of Lagos, Nigeria in 1998. She is currently a Ph.D. candidate, under the supervision of Prof. Deepa Kundur, at the Department of Electrical Engineering, Texas A&M University, College Station. Her research is in the area of secure routing for broadband directional sensor networks. Her expected date of graduation is August 2008.

Research summary: The Cross-Level Approach for Simulating Sensor Networks
¨ Fredrik Osterlind
Swedish Institute of Computer Science Box 1263, SE-164 29 Kista, Sweden

fros@sics.se

Abstract
Simulation is a useful tool during development of wireless sensor networks due to their distributed nature and resourcelimited hardware. However, traditional simulators trade accuracy and detail against performance and scalability. The purpose of my PhD thesis is to investigate crosslevel simulation as a tool for development and experimentation in wireless sensor networks. The cross-level simulation approach enables wireless sensor network simulations with different nodes simulated at different abstraction levels. For example, the same simulation may include both time-consuming high-detail emulated nodes as well as effective and scalable low-detail application nodes. Allowing for multiple abstraction levels can, compared to using a single abstraction level, increase the scalability and performance of a simulation. This research summary presents my cross-level simulation approach and discusses ongoing work in terms of opportunities and current challenges related to the approach.

NETWORK (APPLICATION) OPERATING SYSTEM MACHINE CODE INSTRUCTION SET

NS2 TOSSIM

COOJA

AVRORA

Figure 1. Cross-level simulation supports several abstraction levels This research summary presents cross-level simulation, an approach that enables holistic simultaneous simulation at different abstraction levels. By enabling simulation with sensor nodes simulated at different abstraction levels, it is possible combine high performance and scalability with high detail of low-level behavior. This research summary discusses work-in-progress research regarding opportunities and challenges related to cross-level simulation.

1

Introduction

Wireless sensor network software development is a complex task. Heterogeneous, large-scale networks of resourcelimited nodes are both time-consuming and dif?cult to deploy, but are also hard to inspect and debug. A simulator provides a controlled environment that reduces the development time by enabling monitoring and debugging. In a simulated environment, performance evaluation is possible to do non-intrusively, deterministically, and with known external stimuli. Simulation must always be performed at a prede?ned abstraction level. Such abstraction levels range from instruction set emulation to application modeling. The choice of abstraction level determines both the level of details as well as the simulator performance: output accuracy and detail is often a trade-off against simulator ef?ciency and scalability. Typically, a low-level simulator is able to capture interesting low-level phenomena, but suffers from low performance and is not scalable. In contrast, a high-level simulator such as ns2 is able to simulate thousands of nodes, but is unable to capture and pro?le low-level details such as stack usage or the behavior of a radio-driver.
Copyright is held by the author/owner(s). SenSys’07, November 6–9, 2007, Sydney, Australia. ACM 1-59593-763-6/07/0011

2

Research method

The method used in this work is that of experimental computer science: I implement a system that captures the phenomenon under study and evaluate the resulting system. I implement COOJA, a cross-level simulator, and use it as a research platform. The platform allows me to rapidly try out new ideas, and generates suggestions for future work in terms of user feedback.

3

Cross-level simulation

Simulation must be abstracted at some level. The level of abstraction affects factors such as simulation performance and output detail. This section introduces cross-level simulation, an approach where different abstraction levels can co-exist in one simulation. Traditional wireless sensor networks simulators perform simulation at a speci?c, ?xed level such as the application, operating system or hardware level. Figure 1 shows the three simulators ns2, TOSSIM and Avrora, as well as their sensor node abstraction levels. The key insight of this work is that the level of detail needed in a simulation may differ between nodes. Not all nodes have to be simulated at the same abstraction level. For example, in a data collection network only a few nodes closest to the sink may be interesting enough to be simulated at

a low abstraction level. By simulating all other nodes at a higher abstraction level, the simulation performance will increase. In [5], we implement the COOJA Simulator, a simulator that embodies the cross-level simulation approach. COOJA is implemented in Java and simulates Contiki OS sensor networks. In COOJA, nodes can be simulated at three different abstraction levels: the application, operating system and microcontroller instruction set emulation level. By combining all three levels, a simulation can gain from both the high performance and scalability of higher abstraction levels and at the same time allowing for detailed simulation data from nodes simulated at lower levels. Below follows short explanations of the three levels in COOJA. The application level in COOJA is the highest abstraction level and captures algorithm and application behavior. The application level is scalable in terms of memory usage and simulation ef?ciency. Application level nodes are implemented by Java classes, and hence the simulated code is not deployable. Operating system level nodes simulate an actual Contiki operating system compiled for a special simulation platform, and all simulated Contiki applications are hence deployable. Operating system level nodes require more memory and time to simulate compared to application level nodes. Operating system-level simulation is, however, not suitable for development of low-level code such as device drivers because the hardware is abstracted by the simulator. Furthermore, since operating system-level simulation executes native code, nodes at this level are not applicable for memory usage analysis. The third and lowest abstraction level in COOJA is the microcontroller instruction set emulator node. Nodes at this level are running in MSPSim [2], a Java-based MSP430 hardware emulator which provides full bit-level details. This level requires considerably more memory and execution time compared to the other two abstraction levels, but provides much more simulation details as well as cycle-level execution monitoring. Figure 2 shows the different running times of a simple LED-toggling application depending on number of nodes and abstraction level. For example, the application-level nodes implemented by Java classes can be simulated more than 50 times faster than corresponding emulated nodes. [5] Besides the three abstraction levels currently supported in COOJA, several other abstraction levels could be added. A more realistic and detailed abstraction level could for example be a real physical sensor node connected to the simulator. On the opposite side, higher abstraction levels could be achieved by representing several simulated nodes as one simulated entity: a cluster abstraction level.

Figure 2. Mixing nodes from different abstraction levels enables more effective simulations.

4.1

Debugging and interactive simulations

Simulators can be used for rapid development by iterating between code and simulation. During these phases one or only a few nodes are closely monitored by the developer. Those nodes require a high level of detail.

4.2

Simulation-based testing

Simulation-based testing for wireless sensor network can be implemented by having the simulator perform numerous iterations using a ?xed initial simulation setup. Between iterations, random seeds in the simulator are changed in order to generate more reliable simulation results. The observed points of interest in such a test are application-speci?c and ranges from high-level data such as the total number of transmitted radio packets, to low-level data such as the sink-node’s maximum stack usage or total number of cycles spent in the MAC protocol. In order for an abstraction-level homogeneous simulator to perform such testing, all nodes must be simulated at the most detailed level needed, even though these details may only be needed at a small subset of the simulated nodes. In contrast, a cross-level simulator can choose to only simulate a small subset at the highest detail level, thus decreasing the test duration signi?cantly. This is perhaps even more apparent when using an automated test suite that periodically has to perform a lot of tests.

4.3

Exploration of Adaptive MAC protocols

4

Application ideas

The cross-level simulation approach is especially useful in simulated networks where the need for simulation details differs between different nodes. This section discusses ongoing research with a number of applications where using cross-level simulation greatly increases the simulation ef?ciency.

Cross-level simulation is also useful for simulating networks where the simulated nodes can be divided into groups, and each group has different requirements in terms of simulation details. Such groups can be due to heterogeneous networks where only a few of the sensor nodes are dependent on low-level functionality. An example of such a network is a data collection network based on the Funneling-MAC [1]. Funneling-MAC is a hybrid TDMA and CSMA/CA MAC protocol that adapts to the surroundings depending on the amount of heard radio traf?c. All nodes start out using CSMA, but nodes that experience high amounts of radio traf?c switch to TDMA. In a data collection network the source nodes furthest away from the sink node can be expected to hear less radio traf?c than nodes close to the sink node (called “the funneling region”).

Since MAC protocols depend on low-level radio interaction, when evaluating a MAC protocol such as FunnelingMAC, using a high abstraction level does not produce enough details to capture the behavior of the protocol. For example, a simulation TDMA-based MAC protocol may need a higher timing resolution than a CSMA-based protocol. Using cross-level simulation in the above data collection network, only nodes close to the sink need to be simulated at the emulated level. Simulation of the above applications bene?ts from a cross-level simulation approach. Instead of simulating all nodes at a low abstraction level, large portions of the networks can be simulated using a higher abstraction level, thus enabling more effective and scalable simulations without losing any wanted simulation detail. Apart from evaluating performance gains by using crosslevel simulation, part of my research focuses of the effects of using cross-level simulation compared to single-level simulation.

simulation at different abstraction levels. We have demonstrated the potential simulation performance gain of the approach. The Contiki simulator COOJA has been presented. COOJA implements cross-level simulation by supporting three different abstraction levels: application, operating system and microcontroller instruction set emulation level. Finally, a number of application ideas where cross-level simulation is highly useful have been discussed.

Biography
¨ Since the beginning of 2006, Fredrik Osterlind is a researcher at the Networked Embedded Systems group, Swedish Institute of Computer Science (SICS). His main research considers sensor network simulation. One of the main outputs of this research so far is the Contiki simulator COOJA, of which Fredrik is the main author. He is a registered full-time PhD student at Uppsala University, and his research is conducted at SICS. Besides simulation techniques, other sensor network research areas Fredrik has been involved in includes automated test and debugging frameworks, time-synchronization and MAC protocols, and using standardized building automation systems in sensor networks. Fredrik currently plans to submit his dissertation year 2010.

5

Related work

The idea of simulation at different abstraction levels in the same simulation is not new: for example, in 1998 Polly Huang et. al. suggested using multiple simulation abstractions to increase performance in large-scale Internet multicast simulations. The authors were able to, with a small simulation output quality decrease, improve the simulation performance with an order of magnitude [4]. In the area of sensor networks many simulators exist, of which a few implement multiple abstraction levels. A number of these simulators are discussed below. The EmTOS extension to EmStar [3] is hybrid in the sense that it simulates deployable code for both 32-bit embedded microserver platforms (using EmStar/EmSim) as well at simpler 8-bit sensor nodes (TinyOS/TOSSIM). Furthermore, EmSim supports cross-level simulation by allowing a subset of the nodes to either use only real radios (”Emulation Mode”) or to run on real hardware (”Hybrid mode”). SensorSim [6], a modi?cation of ns2, also supports hybrid simulations with both real and simulated nodes. However, the work focuses on using real-life sensor data input instead of actually interacting between real and simulated nodes. MULE [7] simulates motes on a host machine but, similar to EmStar, allows radio transmissions to be performed by physical sensor nodes. Furthermore, MULE also supports data sensing using physical nodes. The main difference between our work on cross-level simulation and the above discussed simulation environments is two-fold. We focus on how to use cross-level simulation in order to increase simulation performance. In contrast, the above work that uses similar techniques for enabling connectivity between different platforms. Furthermore, our work investigates how cross-level simulation can be used to allow the study of phenomena that are hard to investigate in traditional simulators.

7

References

[1] Gahng-Seop Ahn, Se Gi Hong, Emiliano Miluzzo, Andrew T. Campbell, and Francesca Cuomo. Funneling-mac: a localized, sink-oriented mac for boosting ?delity in sensor networks. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, SenSys 2006, Boulder, Colorado, USA, October 31 - November 3, 2006, 2006. ¨ [2] J. Eriksson, A. Dunkels, N. Finne, F. Osterlind, and T. Voigt. Mspsim – an extensible simulator for msp430-equipped sensor boards. In Proceedings of the European Conference on Wireless Sensor Networks (EWSN), Poster/Demo session, Delft, The Netherlands, January 2007. [3] Lewis Girod, Thanos Stathopoulos, Nithya Ramanathan, Jeremy Elson, Deborah Estrin, Eric Osterweil, and Tom Schoellhammer. A system for simulation, emulation, and deployment of heterogeneous sensor networks. In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems, Baltimore, MD, 2004. To appear. [4] Polly Huang, Deborah Estrin, and John Heidemann. Enabling largescale simulations: selective abstraction approach to the study of multicast protocols. In Proceedings of the International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pages 241–248, Montreal, Canada, July 1998. IEEE. ¨ [5] F. Osterlind, A. Dunkels, J. Eriksson, N. Finne, and T. Voigt. Crosslevel sensor network simulation with cooja. In Proceedings of the First IEEE International Workshop on Practical Issues in Building Sensor Network Applications (SenseApp 2006), Tampa, Florida, USA, November 2006. [6] A. Savvides S. Park and M. B. Srivastava. Sensorsim: a simulation framework for sensor networks. In Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, pages 104–111, Boston, MA USA, 2000. [7] D. Watson and M. Nesterenko. Mule: Hybrid simulator for testing and debugging wireless sensor networks. In Proceedings of the 2nd International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 04), 2004.

6

Conclusions

In this research summary, we have introduced cross-level simulation, an approach that enables holistic simultaneous

Secure multi-hop network programming with multiple one-way key chains
Hailun Tan
School of Computer Science The University of New South Wales Sydney, Australia

thailun@cse.unsw.edu.au ABSTRACT
The current network programming protocols provide an e?cient way to update program image running on sensor nodes without physical access to them. However, given the open environment where sensor nodes are deployed, securing network programming is a challenging and important issue. Existing work addressing this issue either lacks the consideration on securing multi-hop version of network programming protocols, or are not cost-e?cient.In this paper, we propose a novel scheme to secure multi-hop version of network programming protocols: multiple one-way hash chains. This scheme is resilient to malicious program image injection regardless of number of compromised nodes and it secures multi-hop propagation of program images for sensor nodes. The simulation result shows that our scheme has lower endto-end latency than the existing work. multi-hop network programming protocol while the scheme in [3] provides con?dentiality in one-hop program image update. Authenticity of program image is referred to as trustworthiness of program image source. In our context, the base station is the only authenticated source to distribute program updates while sensor nodes should relay the program updates to its downstream peers instead of originating new program updates. Integrity of program image is referred to as intactness of content in authenticated program update. i.e. none of the sensor nodes can forward the altered updates without being detected.

2.

ASSUMPTIONS
Our scheme is based on the following assumptions: ? The base station cannot be compromised and it has unlimited computational power compared with sensor nodes. In Deluge, the base station is the origin of the legitimate program updates. If it were not trusted, nothing else in the WSN could be trusted. ? We assume wireless sensor nodes to be physically static in the network and to be evenly distributed. ? Our scheme makes no assumption on number of compromised nodes in the WSN. However, we ?nd that if a node has k disjoint paths to the base station then it is protected against k ? 1 compromised nodes in our scheme. In other words, given any healthy node (A) which has k one-hop neighbors, the adversary can compromise at most k ? 1 neighbors if A is not compromised. ? The compromised sensor nodes can eavesdrop on, copy, alter, inject or delay packets. ? In our scheme, we do not consider Denial Of Service (DOS) attacks such as jamming attack (i.e., an adversary keeps sending garbage packets to cause collisions in MAC layer) or power depletion attack (i.e., an adversary keeps sending packets which de?nitely fail authentication but the remaining energy of its neighbors can be depleted due to excessive authentication operations). ? We do not consider out-of-order packet delivery since it is guaranteed by Deluge.

1.

INTRODUCTION

Network programming is a convenient way to update the program image running on sensor nodes without any physical access to them, particularly after sensor nodes are deployed. The existing network program protocols [1] [2] propagate the new program images to nodes through wireless medium and employ di?erent strategies to minimize the endto-end delay. However, these protocols do not consider the security mechanisms. In addition, sensor nodes are usually deployed in an open, unattended area, which implies that they are much more susceptible to node capture than their counterparts in traditional computer networks. As a result, an adversary could simply compromise a single sensor node and inject the malicious program image through WSN. Motivated by the importance and challenges in securing network programming protocols, our work is to design a new security scheme for network programming in wireless sensor network so that authenticity and integrity of a program image can be guaranteed. Although our scheme employs oneway key chain in a similar way as [3], our scheme supports

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 pro?t or commercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. Sensys ’07 , Sydney, Australia Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.

3.

DESIGN OF OUR SCHEME

In our scheme, sensor nodes are divided into di?erent groups according to their hop distance to the base station. Each group has a distinct group key shared among members. Each key is one of the elements in a distinct one-way hash chain [4]. The one-way hash chain is constructed by repeatedly applying the one-way hash function (H), which is a public function easy to compute but computationally infeasible to revert, on a random seed number (Kn ) for n times. The last hashed output is called committed value of hash chain (K0 ). So we have K0 = H n (Kn ). Assume the program image is divided into k(k ≤ n) packets for transmission. Take the ?rst packet (P0 ) for nodes in 1st hop group 1 as example, P0 will be concatenated with two segments: key update (U0 ) and packet authentication (T0 ). These two segments are built as follows: ? key update: It is the encrypted result of K1 with K0 as the key. i.e. U0 = E(K1 )K0 , where E(A)B denotes A is encrypted with B as the key. ? packet authentication: It is the hashed result of P0 concatenated with K1 . i.e. T0 = H(P0 ||K1 ), where ”||” denotes concatenation. After the above preprocessing of packet and the respective concatenation (i.e. P0 = P0 ||U0 ||T0 ), P0 is transmitted to nodes in 1st hop group. After retrieving the correct group information from P0 (i.e. parsing the right U0 and T0 ), the sensor nodes will need to perform the veri?cations on key update (U0 ) and packet authentication (T0 ) as follows: ? key update: The sensor node decrypts U0 with K0 . i.e. D(U0 )K0 , where D(A)B denotes A is decrypted with B as the key. The sensor node will need to check if H(D(U0 )K0 ) is the same as K0 . if it is, the authenticity of U0 is ensured and K0 is replaced by K1 for the next packet veri?cation. Otherwise, this packet is discarded. ? packet authentication: This veri?cation is processed only after the veri?cation of key update passes. After the sensor node gets the authenticated K1 , it performs H(P0 ||K1 ) to see if it matches T0 . If it does, the integrity of packet is ensured. Otherwise, this packet is discarded. The above packet preprocessing and veri?cation can be further expanded to nodes in the other groups with distinct key chains shared with the base station. Each time when Pi (0 ≤ i ≤ n ? 1) passes both veri?cations in the nodes belonging to j th group, the key will be updated from Ki to Ki+1 . The respective Ui and Ti for j th group will be removed from packet.

node needs to receive the authenticated update on key. i.e., it needs to decrypt the key update and verify the decrypted result. Then it needs to preprocess the packet with malicious content. i.e. it needs to forge packet authentication (Ti ) for ith packet. After that, it can inject malicious packet to circumvent the veri?cation. However, the time for compromised node to ?nish all these operations is much longer than the time for the neighbors of compromised node to receive the authenticated packets from other peers. So even though the node is compromised in our scheme, it is hard to inject malicious packet due to the strict timing requirement. ? Low computational overhead: Our scheme employs only the symmetric cryptographic primitive to authenticate broadcast program updates. As a result, the computational overhead is much lower than existing work in secure network programming [5], which employs digital signature. ? Immediate authentication: Time synchronization between base station and sensor nodes is not required in our scheme, while TELSA [6], which applied the oneway hash chains for broadcast authentication in WSN, needs the loose time synchronization. So immediate authentication can be ensured.

5.

PERFORMANCE EVALUATION

We implement our scheme in TinyOS and evaluate it through the build-in simulator in TinyOS, TOSSIM [7]. In section 5.2, we compare our scheme with the original Deluge [1] and Sluice [5] in terms of end-to-end latency.

5.1

simulation setting

In Deluge, a program image is ?ooded in the network. Hence, as long as sensor nodes are connected in the network, the performance is a?ected by the density of nodes and independent to the topology of WSN. The rest of the simulation settings are listed in Table 1. Table 1: Simulation Setting parameters in simulation values in simulation number of nodes(N ) 2 ? 30 number of pages for one program update 24 ? 30 number of packets per page 48 number of hops program image propagates 1?6 number of nodes per group 5 transmission range 100 m

4.

SCHEME PROPERTY
Our scheme has the following nice properties: ? Resistance against node compromise: Our scheme is resilient to node compromise because the compromised node has a di?cult timing requirement to circumvent the veri?cation process in our scheme. In order to inject malicious packets successfully, a compromised

5.2

end-to-end latency

1

assume nodes in 1st hop group hold K0 .

In Deluge, the program update is divided into ?xed-size blocks called pages [1]. Each page is further divided into ?xed-size packets, which are the basic transmission units. In Sluice, authors proposed to hash the last page, then attach the hashed value to the second last page. This process is applied recursively until the ?rst page is reached. After that, the ?rst page is signed with the private key of base station [5]. Each sensor node will have to verify the ?rst page with

Time taken(in second) to transfer imge between 2 nodes

200 180 160 140 120 100 80 60 40 20 2 5 10 15 20 number of pages in program image 25 30 Deluge Deluge with multiple key chains Sluice

average energy taken to propogate updates to all nodes(s)

200 Deluge Deluge with multiple key chains

150

100

50

0 2 5 10 15 20 25 number of nodes in wireless sensor network 30

(a) one-hop program update

(b) multi-hop program update

Figure 1: end-to-end latency evaluation on single hop and multi-hop scenario on our scheme the public key of the base station, then authenticate each page by the hashed value from the previous one. Authors in [5] carried out their experiment for one-hop image propagation. Given data from [5], we could compare our scheme with Deluge [1] and Sluice [5] in Fig. 1(a) for one-hop program update. Our scheme and Sluice both have the linear scalability with respect to update size, as is shown in Fig. 1(a). At the beginning of program updates, our scheme has much lower latency than Sluice because in Sluice, the sensor node has to verify the digital signature for the ?rst page of program image. In our scheme, there is no asymmetric cryptographic needed. As number of transmitted pages increases, the latency of Sluice escalates slower than our scheme since it authenticates program image in granularity of pages not packets. The number of symmetric cryptographic operations is signi?cantly reduced in the price that a single modi?ed packet within a page can lead to the failure of authentication for the whole page. Despite decrease in number of cryptographic operations, it cannot completely cover the signi?cant delay from veri?cation of digital signature in Sluice with respect to our scheme for the ?rst 30-page update. Fig. 1(b) shows the end-to-end latency in our scheme for multi-hop program updates with respect to Deluge [1]. As number of nodes increases, the gap between Deluge and our scheme is enlarged due to the cryptographic operations in our scheme.

One-way key chain is used to ensure the con?dentiality of the program image [3]. However, the scheme in [3] is con?ned to one-hop propagation. As a result, how to provide con?dentiality in multi-hop broadcast in the WSNs will be a topic worth investigation in the future.

7.2

key distribution

To any cryptography scheme in the WSNs, how to distribute the keys to the nodes in the WSNs is the the ?rst important step. In Tinysec [8], the keys are assumed to be distributed securely without any further details. Since the key distribution is also required in this scheme to establish the shared key between the base station and sensor nodes, it will be another direction to look into in terms of security in network programming.

7.3

individual node security

6.

CONCLUSIONS

We implement our scheme in one of the most popular sensor network platforms, TinyOS and evaluate the performance in TOSSIM [7]. The simulation result shows that our scheme outperforms Sluice [5] in terms of end-to-end latency.

Since the WSNs communication uses an open medium susceptible to eavesdropping or interference. With limited computational and communication capability, security measure on the nodes in more powerful networks are not feasible to the WSNs. Trust Platform Module (TPM) is a micro-controller, having its own memory,can store secured information from an attacker. On the other hand, the much more powerful components(Stargates) are used for data aggregation. With the tamper-proof TPM installed on Stargates, a symmetric key between the sensor nodes and the Stargates can be established to protect the exchanged information from being eavesdropped and interception. Such mechanism can be further expanded to the communication between the Stargates and the base station.

7.

FUTURE WORKS

7.4

guard against time-dependent attacks

The scheme in this paper secures multi-hop broadcast of a program image by employing multiple one-way key chains shared between base station and the sensor nodes.There are several other aspects or directions I can get into in the future during my PhD studies.

7.1

Con?dentiality

In the WSNs, there are some time-dependent attacks such as rushing attack [9], wormhole attack [10]. Most of the existing mechanisms [9], [10] against these attacks either employ the temporal synchronization or spatial synchronization, which are expensive to the sensor nodes. Given the fact that these attacks usually ”accelerate” parts of the network protocol in the WSNs to create the conditions for the mali-

cious attack in the later stage such as blackhole in the network. Some ”client puzzles” can be designed for the attackers to solve before they can mount the these time-dependent attacks. One such example is that a server will distribute several small cryptographic puzzles to its clients to solve before an attacker, disguised as a legitimate client, sends redundant requests to deplete the server’s resource [11]. Since these client puzzle are time-consuming to the attacker to solve. the e?ect of ”acceleration” can be minimized.

[10] Y. C. Hu, A. Perrig, and D. B. Johnson. Packet leashes: a defense against wormhole attacks in wireless networks. volume 3, pages 1976–1986 vol.3, 2003. [11] Donggook Park, Jungjoon Kim, Colin Boyd, and Ed Dawson. Cryptographic salt: A countermeasure against denial-of-service attacks. pages 334+. 2001.

8.

BIOGRAPHY OF AUTHOR

Hailun Tan is a Ph.D. candidate at the School of Computer Science and Engineering at the University of New South Wales. He holds two M.S. degrees from the Australian National University. He used to be a member in CSIRO, ICT Center and Network Pervasive Computing Program (NPC), NICTA. His research interests include security and reliable communication in sensor networks, mesh network. He is a student member of IEEE Communication Society. His primary supervisor is Prof. Sanjay Jha.

9.

REFERENCES

[1] Jonathan W. Hui and David Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. In SenSys ’04, pages 81–94, New York, NY, USA, 2004. ACM Press. [2] Limin Wang. Mnp: multihop network reprogramming service for sensor networks. In SenSys ’04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 285–286, New York, NY, USA, 2004. ACM Press. [3] Jaleel Shaheen, Diethelm Ostry, Vijay Sivaraman, and Sanjay Jha. Con?dential and secure broadcast in wireless sensor networks. In Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007. IEEE 18th International Symposium on, 2007. [4] Leslie Lamport. Password authentication with insecure communication. Commun. ACM, 24(11):770–772, November 1981. [5] P. E. Lanigan, R. Gandhi, and P. Narasimhan. Sluice: Secure dissemination of code updates in sensor networks. In Distributed Computing Systems, 2006. ICDCS 2006. 26th IEEE International Conference on, pages 53–63, 2006. [6] Adrian Perrig, Robert Szewczyk, Victor Wen, David E. Culler, and J. D. Tygar. Spins: security protocols for sensor netowrks. In Mobile Computing and Networking, pages 189–199, 2001. [7] Philip Levis, Nelson Lee, Matt Welsh, and David Culler. Tossim: accurate and scalable simulation of entire tinyos applications. In SenSys ’03, pages 126–137, New York, NY, USA, 2003. ACM Press. [8] Chris Karlof, Naveen Sastry, and David Wagner. Tinysec: a link layer security architecture for wireless sensor networks. In SenSys ’04, pages 162–175, New York, NY, USA, 2004. ACM Press. [9] Yih-Chun Hu, Adrian Perrig, and David B. Johnson. Rushing attacks and defense in wireless ad hoc network routing protocols. In WiSe ’03: Proceedings of the 2003 ACM workshop on Wireless security, pages 30–40, New York, NY, USA, 2003. ACM Press.

Wringer: A Debugging and Monitoring Framework for Wireless Sensor Networks
Arsalan Tavakoli

ABSTRACT
Despite nearly a decade of sensornet research, the community has yet to witness the widespread deployment of largescale sensor networks. We argue that one of the main factors hindering deployments is the lack of su?cient debugging and monitoring tools, particularly for real-world deployments. Our research focuses on using DSN, a declarative programming paradigm, as the foundation for Wringer, an integrated debugging framework that allows for rapid prototyping and deployment of debugging tools: passive, active, in-network, and gateway-based. The goal is to utilize these rapid-prototyping capabilities to discover the core set of debugging primitives that can detect and ?x the majority of wireless sensor network bugs. We utilize this information to build compact debugging modules for Wringer, allowing end-users to leverage suitable pre-packaged core primitives while maintaining the ability to rapidly deploy new mechanisms.

the placement of these snooping nodes and the amount of information required for reconstruction. While these tools designed for the Internet space are helpful, their usefulness in the sensornet space is limited for a variety of reasons. In many sensornet applications, nodes are di?cult to reach physically, with multi-hop low-bandwidth links being the only path of communication. The extra cost of debugging can be signi?cant, and often no global time synchronization exists to facilitate event ordering. More importantly, message paths and transmissions are only part of the problem in sensornets, as a wide variety of other factors can in?uence the behavior. These include resource constraints that cause nodes to fail or drop packets, the vagaries of low-power wireless communication, and bugs in low-level embedded code that are di?cult to ?nd in simulation or small testbed deployments. As such, tools are needed that are designed speci?cally for sensornet application developers and end users. A lack of an e?cient and e?ective way to monitor and troubleshoot sensor networks has severely hindered deployments. This is primarily a result of numerous factors that can affect the operation of a sensor network, and also the limited visibility into system state. System developers typically can only analyze packets received at the base station. If data from a subset of nodes is missing, there is no way to pinpoint the exact source of the problem. Earlier work [13] showed the temporal variability of 802.15.4 links over time, leading to seemingly unpredictable packet delivery performance. A single bottleneck link can signi?cantly a?ect network performance, as was demonstrated by the poor reliability of data in the Great Duck Island deployment [14]. Other sources of di?culties have been the failure of a network of energyharvesting motes to behave as expected due to weather [4], and a network where nodes failed quickly because they kept the radio on for longer then intended performing retransmissions. Even these problems were only detected after hours of o?ine post-mortem analysis of logs kept by nodes. In such situations, it is often unclear precisely what information needs to be logged in order to allow for an accurate analysis at a later point. There are other cases where the causes of certain network behavior remains unknown, mostly due to a lack of insight into the state of the system during runtime. As such, we argue that the what needs to be de?ned before

1.

MOTIVATION

Distributed systems are di?cult to debug. Information from all the nodes have to be gathered at a single point in the network to be able to reconstruct the state of the whole system, and maintaining a serializable ordering of events for a post-mortem analysis is a challenging task. In the Internet context, there are a series of systems that attempt to provide system transparency for the inner-workings of the network. Systems such as XTrace [5] attach metadata to each packet that is updated at each point of processing. On the other hand, LibLog [6] and other similar systems log all information locally. This information is later collected and used to replay previous events to allow for a closer analysis. Pip [12] looks at message paths at a single layer in order to reconstruct information about the distributed application. MagPIe [8] also seeks to trace execution paths, using a schema formed by experts to correlate events and create a total causal ordering. One area of particular interest is reconstruction of 802.11 link layer behavior through the use of passive monitors, explored in [2] and [10], which look at

the how can e?ectively be addressed. In other words, the limited resources of sensornets mandate that we de?ne what the core set of necessary tools are before focusing on an e?cient and practical implementation. We introduce Wringer, a declarative debugging and monitoring framework that allows for rapid prototyping and deployment of new tools. Through empirical studies, we aim to specify the aforementioned core set, and then incorporate this information back into Wringer, creating an e?ective yet ?exible sensornet debugger. We begin with a survey of existing systems in section 2. Section 3 outlines our experimental methodology, and section 4 provides an overview of Wringer. Finally, section 5 discusses the current status of the project and outlines a chronological plan for future work.

ity [17] takes a similar approach, but focuses on evaluation metrics that are designed to make network protocols more open. It also requires the creation of a decision tree, along with the probability of various events happening, which is often di?cult to obtain. Wringer provides many of the features provided by the latter two types of debuggers, as well as a host of others, and does it in a seamless fashion that does not require additional wiring, components, or low-level modi?cations. In addition, we note that the philosophical focus of these existing systems is on implementation, rather than providing fundamental mechanisms that identify and address network issues.

3.

EXPERIMENTAL METHODOLOGY

2.

SENSORNET RELATED WORK

There are a few debugging solutions for sensor networks available, with a fairly wide range of goals and feature sets. We break them into three distinct categories: source-level debuggers, query-oriented debuggers, and decision-tree debuggers.

While each application and environment may be unique, our fundamental hypothesis is that the majority, if not all, bugs fall into general classes. For each class, suitable debugging mechanisms can be implemented. Based on our research into the failures experienced by previous deployments we present the following general bug categories: ? Energy-Related: Erratic behavior and failures due to energy-levels and energy-oriented decisions. ? Link-Oriented: Unpredictable node behavior resulting from temporal or long-lived ?uctuations in linkquality. ? Packet-Handling: Bugs that cause undesirable packethandling along a path, such as drops, lost packets, and forwarding delays. ? Timing: Sychronicity and timing-sensitive issues. ? Distributed State: Inconsistencies in state distributed across the network. Each of the bugs we have encountered thus far fall into at least one of these categories. We make the assumption that, while other bugs may exist, these bugs (and their respective classes) represent the bulk of those that will be encountered in future deployments. Consequently, our hypothesis is that our debugging framework, Wringer, and its associated tool set can accurately detect (and remedy where possible) all instances of these bugs that appear in our test scenarios. We defer a detailed discussion of Wringer to section 4; for now it su?ces to simply characterize Wringer as a rapidprototyping framework for deploying a wide range of debugging tools on the ?y. Our experimental methodology is twofold: recreate the bugs seen in past deployments, and diagnose bugs in future deployments. Deployments such as Great Duck Island [14], the Redwood Forest [16], NestFE [4], and A Line in the Sand [1] can not be recreated precisely, given the complexities of their unique environments. However, the programs used and certain environmental characteristics can be emulated relatively accurately. For example, we can tweak radio power levels and node locations to create various densities of networks, and then subsequently introduce external noise, such as 802.11 tra?c, to temporally a?ect link qualities. We can introduce ariti?cal clock drift in conjuction

2.1

Source-Level Debugging

Clairvoyant [19] is the ?rst true source-level debugger for sensor networks that operates in much the same fashion as GDB, and furthermore sits underneath the actual program and so requires no speci?c modi?cations. However, Clairvoyant is designed to examine code in a single node and even then requires intuition as to where the problem lies and what to look at. Nonetheless, systems like Clairvoyant are a great step forward in sensornet debugging and we see it as complementary to our work.

2.2

Query-Oriented Debugging

SNMS or Nucleus [15] allowed system developers to query the value of RAM constants, and then tag certain other attributes as well. The user can then send queries from the base station requesting this information. The di?culty with Nucleus is that it’s limited, in the sense that it was designed to just grab single data values from RAM, which have to be converted from bytes into meaningful information later. Furthermore, applications have to be modi?ed to add in Nucleus components and tag attributes, and the set of queries is limited. Another debugging system is Marionette [18], which provides functionality similar to Nucleus, with the addition of remote procedure calls, and does not require tagging of variables that will be queried. However, Marionette still requires a completely distinct system to interact with the nodes, rather than an integrated one.

2.3

Decision-Tree Debugging

The ?nal class of sensornet debuggers are those revolving around decision trees. Sympathy [11] builds a decision-tree based on expert knowledge to classify routing-related bugs, using information gathered from periodic reports from the nodes. However, the system requires modi?cation of the executable and incurs a noticeable network overhead. Visibil-

with low power listening, and then attempt to distribute new binary images using Deluge. In another scenario, we can utilize deployments with con?icting requirements, such as a network protocol that utilizes promiscuous listening for gathering link data while the MAC disables snooping for energy purposes, as outlined in [17]. In each of these scenarios, the goal is to have Wringer identify the symptom (e.g. low energy power levels) and diagnose the cause (e.g. large number of retransmissions due to poor link quality). In addition, many of the deployments mentioned here and in the introduction experienced additional undesired behavior, such as a low data yield, but were unable to diagnose the cause; without making formal guarantees, we hope that Wringer can provide additional insight into this behavior. We discuss evaluation metrics in section 4 after presenting the requirements for a sensornet debugger. In terms of future deployments, we aim to deploy Wringer for real-world tests, on testbeds and in actual deployments. While we can’t hypothesize over the entire set of potential bugs, our goal is to at least diagnose all bugs that were observed as part of our training data, and help identify new symptoms and causes that appear.

E?ectiveness: To evaluate the e?ectiveness of Wringer, we utilize three metrics as proxies: the percentage of previouslyidenti?ed bugs that Wringer correctly diagnoses, the amount of time to ?nd each bug (averaged across all trials), and the number of debugging tools/commands needed before a correct diagnosis is obtained (again averaged across trials). One ?nal aspect that has to be taken into consideration is the creation of heidenbugs as de?ned in [19]: bugs that change or disappear once the debugger is activated. When testing previous deployment recreations, we can analyze the operation of the system both with and without Wringer deployed, although visibility will be less in the latter case. Furthermore, if deployed but not used (i.e. no debugging commands are set), Wringer should not interfere with the standard operation of the system. Although we focus on keeping Wringer lightweight to minimize impact on the network, there is always the potential for heidenbugs, in which case we can only examine the change in the nature of bugs as compared to the unmodi?ed behavior, present a hypothesis, and then retest with Wringer. Wringer can be divided into two separate, but interwoven aspects: a rapid-prototyping development framework, and the associated debugging tool set.

4.

SYSTEM OVERVIEW

The challenging aspect of providing a debugging system for sensornets is that there are multiple requirements: Ease of Use The system must be intuitive and easy to use for end users Lightweight The debugging system should have a minimal impact on the network, both from a code and memory footprint, as well as additional network tra?c. E?ective This system should be useful in the sense that it provides the user with additional monitoring and debugging capabilities that were awkward or non-existent previously In the previous section we outlined our experimental methodology for testing Wringer. Now that the requirements for a debugger have been described, we de?ne the evaluation metrics for our experiments: Ease of Use: We will measure the lines of code needed for deploying various tools, similar to DSN, but arguably more importantly, work closely with HCI researchers to design a user-friendly interface and perform user studies to evaluate the usability of the system and improve through numerous reiterations. Lighweight: The footprint for the debugger can be divided into 3 categories: code/memory footprint, network overhead, and energy consumption. Code and memory footprint can be determined by examining the size of the compiled binary, while network overhead can be analyzed by recording the number of messages transmitted on behalf of Wringer, as well as their size because of the varying length of code capsules. Finally, energy consumption analysis will be completed using an energy-monitoring board that has been installed in the new UC Berkeley testbed.

4.1

The Wringer Framework

Our system, Wringer, draws inspiration from DSN [3], which is a declarative programming paradigm that utilizes a Dataloglike high-level speci?cation language. DSN installs a runtime query processor on each node and utilizes a table abstraction in which all data is viewed as database tuples. Additional information on DSN can be found in [3]. We chose DSN as the foundation for implementing Wringer because we believe the declarative approach will facilitate the creation of an e?ective distributed debugging and monitoring system. However, DSN in its current form has two critical shortcomings for our purposes. First, DSN program speci?cations are converted to program binaries at compile time and are unchanged during run-time. While new packets are processed according to existing rules, new rules can not be introduced dynamically. This implies that Wringer would not be able to deploy new tools on-the-?y; rather new binary would need to be compiled and distributed. Second, DSN does not interact with other systems; more speci?cally, a system cannot be only partially speci?ed using DSN. This would narrow Wringer’s empirical study set to only DSN applications, which would be overly restrictive. As such we introduce iDSN , or interprative DSN. iDSN utilizes a virtual machine-like interprative approach, based on the concept of Active Networks [9]. We largely maintain DSN’s high-level speci?cation language, SNLog, in its current form, as we feel that the language naturally supports Wringer’s features, and because we want to utilize the tight integration with DSN programs. However, the interprative approach allows us to introduce new rules during run-time in the form of small code capsules. Finally, iDSN functions as a standalone component when needed, allowing it to coexist with non-DSN speci?ed programs. Providing an interface to allow iDSN to debug the internals of these non-DSN com-

ponents is a focus of future work.

4.2

The Wringer Tool Set

In this section we outline the primary mechanisms Wringer provides for building debugging tools and provide speci?c examples as guiding points. Parts of our discussion assume Wringer is debugging a DSN application, but as we discussed previously we are working on extending the same features to non-DSN applications. Wringer’s strength lies in its underlying database-oriented structure: All data is in the form of tuples that are stored in tables. Consequently, end users can simply push SQLlike queries into the network for retrieving any of the system data from the nodes. The general structure of DSN indicates that adding this functionality requires no modi?cations to the application. Furthermore, low-level data structures can be exported using DSN’s built-in predicates, which allow the query to maintain the same format. Additional functionality, such as ping and trace route can be added without much additional complexity. Ping and traceroute require only 2 and 3 rules, respectively. Even more importantly, Wringer’s programming style lends itself naturally to the use of triggers, in which data is automatically sent to the base station when certain conditions are met, such as system energy dropping below a certain threshold, or if packets are dropped because of over?owing bu?ers. However, careful thought must be given to trigger design, as sending large amounts of debugging information to the base station can aggravate a congested network. Instead, Wringer allows for options such as using compact alarms with pointers to detailed log information to minimize the impact of the debugging infrastructure on the existing system. Furthermore, as the price of ?ash memory continues to decrease, the popularity of storage-oriented sensor networks has risen. An abundance of ?ash memory allows for extensive logging of pertinent system state and events. For example, a node may want to maintain information regarding the timestamp and signal strength of the last beacon message received from all of its neighbors, in order to respond to livelihood prompts. However, this information may not be pertinent to the application, and will not be regularly accessed, and so it should not be wasting precious memory resources. Rather, Wringer extends DSN’s speci?cation language to allow users to indicate predicates that should be stored to ?ash, rather then RAM. We refer to this as collaborative logging, in which logs across nodes are correlated to provide fault-tolerance through redundancy. However, given that ?ash memory can only be written to a limited number of times, an intelligent system that batches writes when possible should be utilized. The ?nal aspect of our debugging system is the ability to alter the behavior of the network upon detecting a problem. Systems such as Deluge [7] allow for wireless reprogramming of nodes from a trusted image stored on ?ash or delivered wirelessly. However, in other situations, it may be desirable to simply call reinitialization functions, input new values for variables, turn o? reliability to avoid the heavy cost of consistent packet retransmission, or force a node to change its route to the base station. These are in essence simply remote procedure calls. However, the key is that Wringer allows

for these functional calls naturally and without additional overhead, rather than requiring compile time knowledge of which functionality might be desirable. Although the practicality of such a mechanism might be limited in a debugging environment where code can simply be recompiled and redistributed, this ability becomes critical in actual system deployments.

5.

CURRENT STATUS AND FUTURE WORK

The initial version of DSN has been released for TinyOS 1.x, and will soon to be ported to T2. Although DSN will continually be improved, incremental changes should not fundamentally a?ect Wringer, except that changes to the highlevel language will add new speci?cation capabilities. The initial phase of Wringer research is nearly complete, during which the initial set of debugging capabilities and tools have been identi?ed. As mentioned above, numerous previous deployments have been analyzed to determine the various failures and their causes, when known. We break up the future road-map into three distinct time periods: Short Term (Months 1-3): Fully design and implement Wringer, including the design of a front-end GUI, the implementation of iDSN , extensions to DSN’s speci?cation language, SNLog, to support Wringer, and also study methods to optimize Wringer’s network tra?c presence. Mid Term (Months 3-10): Release Wringer to the community at large and test it across as many testbeds, applications, and protocols as possible, maintaining detailed logs and records in order to study the e?ciency of Wringer for identifying and ?xing network problems. As the system becomes more stable, attempts will be made to include it as a part of real-world deployments as well. By the end of this period, Wringer distributions should have debugging libraries that contain a tight set of needed tools for various scenarios. Long Term (Months 12-15): During this ?nal period, we study how Wringer can be integrated with other system components, including debugging tools such as Clairvoyant and Sympathy, and architectural components, such as an energy manager. Finally, the PhD dissertation itself will be written and submitted.

6.

REFERENCES

[1] A. Arora, P. Dutta, S. Bapat, V. Kulathumani, H. Zhang, V. Naik, V. Mittal, H. Cao, M. Demirbas, M. Gouda, Y. Choi, T. Herman, S. Kulkarni, U. Arumugam, M. Nesterenko, A. Vora, and M. Miyashita. A line in the sand: A wireless sensor network for target detection. Computer Networks (Elsevier), 2004. [2] Yu-Chung Cheng, John Bellardo, Peter Benko, Alex C. Snoeren, Geo?rey M. Voelker, and Stefan Savage. Jigsaw: Solving the puzzle of enterprise 802.11 analysis. Sigcomm, 2006. [3] David Chu, Lucian Popa, Arsalan Tavakoli, Joe Hellerstein, Philip Levis, Scott Shenker, and Ion

[4]

[5]

[6]

[7]

[8]

[9] [10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

Stoica. The design and implementation of a declarative sensor network system. SenSys, 2007. Prabal Dutta, Jonathan Hui, Jaein Jeong, Sukun Kim, Cory Sharp, Jay Taneja, Gilman Tolle, Kamin Whitehouse, and David Culler. Trio: Enabling sustainable and scalable outdoor wireless sensor network deployments. IEEE SPOTS, 2006. Rodrigo Fonseca, George Porter, Randy Katz, Scott Shenker, and Ion Stoica. X-trace: A pervasive network tracing framework. Networked Systems Design and Implementation, 2007. Dennis Geels, Gautam Altekar, Scott Shenker, and Ion Stoica. Replay debugging for distributed applications. USENIX, 2006. Jonathan W. Hui and David Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. SenSys, 2004. Thilo Kielmann, Rutger F. H. Hofman, Henri E. Bal, Aske Plaat, and Raoul A. F. Bhoedjang. MagPIe: MPI’s collective communication operations for clustered wide area systems. ACM SIGPLAN Notices, 34(8):131–140, 1999. Phillip Levis, David Gay, and David Culler. Active sensor networks. NSDI, 2005. Ratul Mahajan, Maya Rodrig, David Wetherall, and John Zahorjan. Analyzing the mac-level behavior of wireless networks. Sigcomm, 2006. N. Ramanathan, K. Chang, R. Kapur, L. Girod, E. Kohler, and D. Estrin. Sympathy for the sensor network debugger. SenSys, 2005. Patrick Reynolds, Charles Killian, Janet L. Wiener, Je?rey C. Mogul, Mehul A. Shah, and Amin Vahdat. Pip: Detecting the unexpected in distributed systems. NSDI, 2006. Kannan Srinivasn, Prabal Dutta, Arsalan Tavakoli, and Phillip Levis. Understanding the causes of packet delivery success and failure in dense wireless sensor networks. Stanford CS Department Technical Report, 2006. Robert Szewczyk, Alan Mainwaring, Joseph Polastre, John Anderson, and David Culler. An analysis of a large scale habitat monitoring application. ACM Sensys, 2004. Gilman Tolle and David Culler. Design of an application-cooperative management system for wireless sensor networks. EWSN, 2005. Gilman Tolle, Joseph Polastre, Robert Szewczyk, David Culler, Neil Turner, Kevin Tu, Stephen Burgess, Todd Dawson, Phil Buonadonna, David Gay, and Wei Hong. A macroscope in the redwoods. SenSys, 2005. Megan Wachs, Jung Il Choi, Jung Woo Lee, Kannan Srinivasan, Zhe Chen, Mayank Jain, and Philip Levis. Visibility: A new metric for protocol design. SenSys, 2007. Kamin Whitehouse, Gilman Tolle, Jay Taneja, Cory Sharp, Sukun Kim, Jaein Jeong, Jonathan Hui, Prabal Dutta, and David Culler. Marionette: Providing an interactive environment for wireless debugging and development. IPSN, 2006. Jing Yang, Mary Lou So?a, and Kamin Whitehouse. Clairvoyant: A comprehensive source-level debugger

for wireless sensor networks. SenSys, 2007.

7.

BIOGRAPHICAL SKETCH

Arsalan Tavakoli is a 3rd year PhD student at the University of California at Berkeley, advised by Professor Scott Shenker. He completed his Bachelor’s Degree in 2005 at the University of Virginia under the supervision of Professor Jack Stankovic. His expected PhD Dissertation submission date is January 2009. His research interests within sensor networks included transparency and troubleshooting of deployed networks, an overall sensornet architecture, and declarative programming. The results of this research have been published at various conferences and workshops, including SenSys, OSDI, and VLDB. Current non-sensornet research includes, distributed system networking tracing, developing a new network API to replace sockets, and policy-aware switching layers for data centers.

Research Summary: Selectivity-aware Query Processing in Sensor Networks
Muhammad Umer
National ICT Australia (NICTA), Victoria Research Labs Department of Computer Science & Software Engineering University of Melbourne 3010 Victoria, Australia

mumer@csse.unimelb.edu.au ABSTRACT
Many queries issued by users in sensor network (SN) applications select the sensor nodes for participation based on predicates involving spatio-temporal or sensed attributes. In this work we put forward the argument that considerable amount of energy can be saved if the processing and communication resulting from such queries can be restricted to the selected nodes. However, this requires discovering and connecting the selected nodes in a localized and adaptive fashion amid the challenges introduced by coverage and communication holes. We aim to build on methods from graph theory and geostatistics domains and propose low-cost localized and adaptive versions of these methods suitable for static and mobile SNs. The spatio-temporal and predicate based selectivity of monitoring queries in a SN can be utilized for data collection optimization by minimizing the use of non-selected parts of the SN in the query response phase. This minimization can be achieved by computation of selectivityaware data collection overlays of the communication graph and requires techniques that are localized, adaptive and impervious to coverage holes. We further propose following phases of research to achieve the overall objectives. Phase 1: First phase of our research constitutes the development of localized and adaptive techniques for computation of selectivity-aware data collection paths for monitoring queries in fully covered static SNs. This phase also includes a detailed analysis of impact of network con?guration on the performance of well known data collection methods in comparison to our proposed approach. The aim of this phase is to establish the strength of selectivity based optimization and to further understand the impact of various network parameters on the performance of a typical SN application. Phase 2: We plan to focus on controllable mobile SNs in the second phase of our research. As explained in later sections, we consider query selectivity to exist implicitly in such systems and hence argue the need for selectivity-aware processing. We plan to exploit the controllable mobility of nodes in these systems for energy e?cient data collection and to overcome the challenges of partial coverage. Phase 3: Third and ?nal phase of our research will consolidate the ?ndings of above phases and will mainly involve the development of a consistent theory of selectivity-aware optimization for mobile and static SNs. We aim to show the usefulness of this optimization in various application areas and plan to test our ideas in a deployment comprising of real hardware.

1.

INTRODUCTION

Monitoring of physical phenomenon such as bush?res or ?ooding is one of the major application domains for sensor networks (SN) [4, 9]. A key aspect of SN applications in the monitoring domain is selectivity of user interest, i.e., the fact that typically not every point in the networked area is of interest at all times. This selectivity is normally driven by user de?ned predicates involving spatio-temporal or application speci?c parameters. For instance, a monitoring task that requires data collection only from the nodes that register a certain temperature will result in data ?ow from selected parts of the network only. The selectivity of user interest entails unique challenges and opportunities for the SN query processing systems. A considerable amount of node energy can be saved if the data collection and communication resulting from such selective queries can be restricted only to the network parts that the queries select. However, the challenges are to discover and connect these parts for query processing while overcoming problems such as lack of global knowledge, rapidly changing network and physical conditions and presence of coverage and communication holes. In this work, we aim to propose methods for selectivityaware data collection for static and mobile SNs . We aim to establish the strength of selectivity as a query optimization parameter for SN query processing systems.

3. 2. RESEARCH PROBLEM
We propose following statement as the central thesis of our work:
Copyright is held by the author/owner(s). Sensys’07 Doctoral Colloquium, November 6, 2007, Sydney, Australia. ACM X-XXXXX-XX-X/XX/XX.

WORK IN PROGRESS PDT: A Localized Algorithm for Optimization of Selective Queries

3.1

Many monitoring queries run for prolonged periods of time and select a subset of the sensor nodes in a network. However, a data aggregation strategy may not be able to con?ne the aggregation path only to the selected nodes. It may

has to include some non-selected nodes due to the limited communication range of sensor nodes. In this context, the problem to collect aggregates back to a sink by involving minimum number of non-participating nodes can be seen as an application of the the minimal Steiner tree problem (MSTP): given a graph G = (V, E) and a set of terminal nodes T ? V , we seek a minimum cost spanning tree that includes all selected nodes [18]. The MSTP is known to be NP-hard and though several approximation heuristics are known for MSTP, no localized or adaptive techniques exist. We present a data collection algorithm, called Pocket Driven Trajectories (PDT), that optimizes the data collection path by approximating the global Steiner tree with a minimal overhead using purely local spatial knowledge. Our algorithm can easily adapt to changes over the lifetime of a query. The PDT algorithm ?rst discovers the set of pockets for a given query and then aligns the aggregation tree to the spatially optimal path connecting these pockets. This path maximizes the use of participating nodes in the aggregation tree and conversely minimizes the number of nonparticipating nodes. We present experiments comparing the performance of the PDT algorithm against well-known in-network aggregation algorithms including Multipath aggregation (MP) [15], Tiny Aggregation (TAG) [13], Static Clustering (SC) [17] and a global MSTP approximation heuristic (KMB) [10]. Our initial ?ndings regarding the impact of selectivity and spatial features on the performance of the PDT algorithm are presented in detail in [22].
4 3.5 3 2.5 2 1.5 1 0.5 0
MP TAG SC X PDT KMB

covered area (coverage hole) and then use this estimate to guide a recon?guration phase. Currently we are working on localized spatial estimation methods and we plan to follow this work with research on e?cient network recon?guration schemes. Following subsection outlines our proposed localized spatial estimation methods.

3.2.1

Localized Spatial Interpolation

The fact that a SN always monitors spatial processes allows us to exploit the inherent spatial correlation of these processes for certain computations. The theory of spatial interpolation, also referred to as spatial estimation or kriging, provides methods to interpolate unknown values of a physical process using existing knowledge of the process and a model of its spatial variation, the variogram [8]. The challenge is to perform this interpolation accurately and with minimal power consumption. Kriging is known to be a complex mathematical operation involving matrix manipulations over global data available for a spatial process. To reduce the computation required for kriging a restricted neighborhood method is employed where only the sample points within a certain distance from an interpolation point are used. This neighborhood typically forms an ellipse centered on the interpolation point with its major axis parallel to the direction of maximum spatial continuity in the data [8]. To further reduce the computation inside each neighborhood we propose to use following optimization alternatives: ? Clustered Search: A search ellipse is divided into clusters where size of each cluster is de?ned such as samples far from the interpolation point are clustered in larger groups. Kriging is then performed using only the aggregated sample values from each cluster. ? k-Quadrant Search: Only the k closest samples within each quadrant of search ellipse are used for kriging computation. The major strengths of above heuristics are their local nature and minimization of computation using clustering or pruning. Our initial experimentation with a real-world spatial dataset [3] shows very promising results. Figure 2 reports the results of three separate experiments where clustering and pruning have reduced the kriging problem size by an order of magnitude while keeping the estimation error within acceptable limits.
16 Standard Error
Exhaustive K-Quad Cluster
Exhaustive K-Quad

Bytes Transmitted (MB)

2

3

4

5

6

7

8

9

10

Participation(%)
Figure 1: Detailed comparison of data transmissions in low participation scenarios

225
Total Samples

Cluster

12 8 4 0 EXP 1 EXP 2 EXP 3

150 75 0 EXP 1 EXP 2 EXP 3

3.2

Selective-aware Query Processing in Mobile Sensor Networks

(a) Comparison of standard (b) Comparison of size of krigestimation error ing system solved for estimation

With recent advances in hardware technology a class of controllable mobile SNs is fast emerging [20]. multi-hop communication [20]. The goal of controllable mobile SNs is thus to use a small number of mobile nodes to cover a large area [7]. Resultantly, selectivity of user interest is implicit in a mobile SN application. However, the goal of selectivityaware data collection in mobile SNs is twofold: ?rstly, to dynamically recon?gure the network to adapt to the changing coverage requirements and secondly, to utilize the resulting selectivity for data collection optimization. We consider the problem of dynamic recon?guration as a two step process; ?rst the nodes collectively estimate the query inside an un-

Figure 2: Performance Evaluation

4.

FUTURE DIRECTIONS
? We aim to build on the spatial interpolation ideas presented above and plan to solve the dynamic recon?gu-

We foresee following major steps required for successful completion of this thesis:

ration problem in an incremental fashion guided by a localized kriging algorithm. ? We aim to build on the PDT algorithm to produce an e?cient data collection scheme exploiting node mobility. ? We plan to investigate theoretical aspects of our proposed schemes such as their worst and average case performance guarantees and approximation ratios.

5.

RELATED WORK

thus suggested that message passing for a global regression task can be optimized by distributing the global computation among the constituent regions. Though we propose the idea of distributed interpolation on a regional basis also, the concept of region in our method is fundamentally di?erent from [5]. In our method, the interest in a region is not based upon its correlation pattern but its vicinity to a coverage hole. [6, 11] further extend the distributed regression concepts towards the methods for optimal placement of sensor nodes in a network.

Most of the related literature in the SN domain do not take an explicit position on the issue of query selectivity. Our selectivity-aware optimization scheme minimize the use of non-selected parts of the SN to achieve overall energy e?ciency. In general, this problem is an instance of well known NP-hard minimum Steiner tree problem (MSTP) of graph theory [18]. Over the past two decades a number of MSTP approximation heuristics have been proposed [10]. In the SN domain, Krishnamachari et al. [12] report the use of MSTP approximation due to Takahashi and Matsuyama [21] to collect data from a small subset of SN nodes. The main disadvantage of their work, and in general for most MSTP approximations is the global nature of heuristics in that they assume availability of global graph knowledge. Moreover, another weakness of these schemes ,particularly the one suggested by [12], is their static nature in that the initial data collection path does not adapt with respect to any change in the terminal node set. One of the basic query optimization approaches in static SNs is in-network data aggregation using e?cient data collection paths [15, 19]. In-network aggregation schemes exploit the fact that a sensor node consumes less energy for information processing than for information communication. The crux of nearly all in-network aggregation schemes is to establish a data collection path, such as a tree [13] or a graph [15], aggregating along which minimizes the overall data transmission. With the exception of Semantic Routing Tree (SRT) [14], most of the in-network aggregation schemes are selectivity-oblivious in the sense that they do not consider the scenarios where a considerable part of the network might not be generating any data for a given aggregate query. As we show in our experiments, selectivity-oblivious schemes in such scenarios result in unnecessary inclusion of non-selected nodes in the data collection path and hence results in an overall energy loss. Moreover, even SRT is mainly designed for selective queries involving constant attributes only (e.g., location) [14]. The selectivity-aware scheme that we propose is not restricted to constant attributes. Typical interpolation methods based on spatial correlation of natural phenomenon are not readily applicable in SNs as these methods rely heavily on global knowledge and centralized computation. In spirit our work on spatial interpolation is close to statistical data modeling of SN data [2, 11]. However we put forward the argument that for interpolation in large scale SNs monitoring multiple phenomena, a single data model for the whole sample space may not be optimal. In such cases a better alternative is to model the data locally, closer to the point(s) to be interpolated. A number of papers in recent WSN literature propose various forms of statistical inference. The distributed regression method [5] for global kernal regression closely compares to the interpolation method outlined here. This method is based on the notion that a number of local (or regional) correlation structures can be identi?ed inside a given deployment. It is

6.

CONCLUSIONS

This brief manuscript gives an overview of research aims and progress of our work on selectivity-aware query processing in SNs. We argue that a realistic selectivity-aware query processing algorithm should meet the challenges of lack of global knowledge, dynamic network and environmental conditions and coverage and communication holes. Our initial ?ndings with the PDT algorithm demonstrates the strength and validity of selectivity-aware optimization of monitoring queries in static SNs. We argue that query selectivity is an implicit feature of controllable mobile SNs and propose spatial interpolation based method for selectivity-aware query processing in these systems. We plan to consolidate the interpolation and data collection themes of our work in an integrated selectivity-aware query processing scheme for controllable mobile SNs.

7. Bawa, M., Gionis, A., Garcia-Molina, H., and Motwani, R. The price of validity in REFERENCES [1]
dynamic networks. In Proceedings of the SIGMOD (2004), pp. 515–526. [2] Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J., and Hong, W. Model-driven data acquisition in sensor networks. In Proceedings of VLDB (2004), pp. 588–599. [3] Dubois, G., and Galmarini, S. Introduction to the spatial interpolation comparison (sic) 2004 exercise and presentation of the data sets. Applied GIS 1, 2 (2005), 09 1–09-11. [4] Flood mitigation grid http://www.floodgrid.nchc.org.tw/, 2006. [5] Guestrin, C., et al. Distributed regression: an efficient framework for modeling sensor network data. In IPSN ’04. [6] Guestrin, C., Krause, A., and Singh, A. P. Near-optimal sensor placements in gaussian processes. In ICML ’05: Proceedings of the 22nd international conference on Machine learning (New York, NY, USA), ACM, pp. 265–272. [7] Hull, B., Bychkovsky, V., Zhang, Y., Chen, K., Goraczko, M., Miu, A., Shih, E., Balakrishnan, H., and Madden, S. Cartel: a distributed mobile sensor computing system. In Proceedings of SenSys (2006), pp. 125–138. [8] Isaaks, E., and Srivatava, R. M. An Introduction to Applied Geostatistics. Oxford Press, New York, USA, 1989. [9] Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L., and Rubenstein, D. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet. In Proceedings of the Architectural Support for Programming Languages and Operating Systems (2002), pp. 96–107. [10] Kou, L., Markowsky, G., and Berman, L. A fast algorithm for Steiner trees. Acta Informatica 15 (1981), 141–145. [11] Krause, A., Guestrin, C., Gupta, A., and Kleinberg, J. Near-optimal sensor placements: maximizing information while minimizing communication cost. In Proceedings of IPSN (2006), pp. 2–10. [12] Krishnamachari, B., Estrin, D., and Wicker, S. B. The impact of data aggregation in wireless sensor networks. In Proceedings of ICDCSW (2002), pp. 575–578. [13] Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. TAG: A Tiny AGgregation service for ad-hoc sensor networks. SIGOPS Oper. Syst. Rev. 36, SI (2002), 131–146. [14] Madden, S. R., Franklin, M. J., Hellerstein, J. M., and Hong, W. TinyDB: An acquisitional query processing system for sensor networks. ACM Trans. Database Syst. 30, 1 (2005), 122–173. [15] Nath, S., Gibbons, P. B., Seshan, S., and Anderson, Z. R. Synopsis diffusion for robust aggregation in sensor networks. In Proceedings of SenSys (2004), pp. 250–262. [16] Oliveira, C. A. S., and Pardalos, P. M. A survey of combinatorial optimization problems in multicast routing. Comput. Oper. Res. 32, 8 (2005), 1953–1981. [17] Pattem, S., Krishnamachari, B., and Govindan, R. The impact of spatial correlation on routing with compression in wireless sensor networks. In Proceedings of IPSN (2004), pp. 28–35. [18] Robins, G., and Zelikovsky, A. Improved Steiner tree approximation in graphs. In Proceedings of SODA (2000), pp. 770–779. [19] Silberstein, A., Braynard, R., and Yang, J. Constraint chaining: On energy-efficient continuous monitoring in sensor networks. In Proceedings of SIGMOD (2006), pp. 157–168. [20] Somasundara, A. A., Jea, D. D., Estrin, D., and Srivastava, M. B. Controllably mobile infrastructure for low energy embedded networks. IEEE Transactions on Mobile Computing 5, 8 (2006), 958–973. [21] Takahashi, H., and Matsuyama, A. An approximate solution for the Steiner problem in graphs. Math Japonica 24 (1980), 573–577. [22] Umer, M., Kulik, L., and Tanin, E. A location based aggregation algorithm for selective aggregate queries in sensor networks. In Proceedings of GSN (2006). [23] Umer, M., Kulik, L., and Tanin, E. An adaptive aggregation algorithm for selective recurrent queries in sensor networks. Submitted (2007).

Biographical Sketch
Muhammad Umer received the MS degree in Computer Science from National University of Computer and Emerging Sciences, Pakistan in 2004, where he graduated summa cum laude. He is a PhD candidate in computer science at the University of Melbourne and is expected to graduate in early 2009. His work is jointly supervised by Dr. Egemen Tanin and Dr. Lars Kulik, both from Melbourne University’s Computer Science and Software Engineering (CSSE) department. His research interests include database and query processing aspects of sensor networks, developing localized algorithms for query processing in sensor networks, spatial databases and mobile computing. His PhD research is focused on development of localized and adaptive algorithms for energy e?cient processing of selective queries in sensor network database systems. He holds industrial experience in mobile application development ranging from asset management and tracking applications to distributed enterprize systems. His work at Melbourne University is partly funded by Victoria Research Lab of the National ICT Australia (NICTA) where he is associated with the NICTA Open SensorWeb Architecture (NOSA) project. He is also associated with Sensing, Ubiquity, Mobility (SUM) research lab at the CSSE department. He has published several papers in refereed conferences and regularly serves as external reviewer for international conferences including ACM GIS, ACM Middleware, Database Systems for Advanced Applications (DASFAA) and Australasian Database Conference (ADC). He is a member of the ACM.

In situ Genetic Programming for Wireless Sensor Networks
Philip Valencia
?

ARC Centre for Complex Systems University of Queensland Brisbane, Australia

philip.valencia@csiro.au

ABSTRACT
This research proposes in situ distributed genetic programming (IDGP) as a method for achieving continual postdeployment system optimization in wireless sensor networks (WSN). A number of signi?cant challenges are identi?ed that would need to be addressed in order to achieve the desired outcome. These include: distributed evaluation of global ?tness and non-detrimental distributed genetic programming on resource constrained hardware. Preliminary tests indicate that such an approach is plausible and even suitable for speci?c deployments. Achieving networks that can adapt and evolve their behaviour throughout the life of the deployment, would reduce, or even remove completely the need for post-deployment reprogramming.

to break. Automated approaches for devising distributed systems’ logic have also been developed [16], [17]. While this largely removes the human from the logic design process, the evolved solutions can still be brittle since they tend to exploit de?ciencies in the simulated environment caused by idealisations, simpli?cations and incorrect assumptions of the real environment [13], [6]. As the complexity of WSAN deployments increases through evermore challenging tasks, larger network sizes and deployments in less contrived environmental conditions, the chances of a post deployment system failure also increase. System failure caused by the fragility of these traditional approaches typically require a number of post deployment debugging cycles. Each cycle consists of: identifying the cause of the system failure, devising new logic to address the cause of failure and reprogramming the network with the revised logic. For many remote deployments, these failures incur the expense of time by the debug expert to identify and ?x the problem, travel costs and lost network productivity. Over time and after numerous debug cycles, the frequency of the debug cycles usually reduces to an acceptable level. However, since every environmental condition that could ever be encountered cannot be known in advance, the possibility of requiring an additional debug cycle is never fully removed. Ideally, the distributed logic of WSANs would be automatically generated using complete a priori knowledge of the actual environment. Since this is not possible, then the next best option is to be able to adapt to the changing environment as necessary. If the network is able to maintain its intended functionality despite varying conditions, then the need for post deployment debugging is removed. The aim of this research is to provide a framework that performs continuous in situ evolution of individual node logic in a distributed fashion to achieve the intended system performance. This will hopefully reduce or remove the need for post deployment debugging.

Categories and Subject Descriptors
I.2.2 [Computing Methodologies]: Arti?cial Intelligence— Automatic Programming

Keywords
Wireless Sensor Network, Genetic Programming

1.

INTRODUCTION

Wireless Sensor Networks (WSNs) are typically utilised as passive sensing systems. However, by incorporating in-network actuation, it is possible to steer the system towards a desirable behaviour [15]. Such systems have been referred to as Wireless Sensor and Actuator Networks (WSANs) [1]. Determining the appropriate node logic that drives the WSAN to the desired collective behaviour is a complex problem. Typically, node logic is handcrafted, biased by human intuition, heuristics and other human limitations. Unfortunately, desirable and predictable behaviour is often limited to speci?c and sometimes unrealistic conditions. This logic is commonly referred to as being “brittle” [8], since what may seem a simple, yet unexpected condition, causes the system ?Part time PhD student at the University of Queensland

2.

RELATED WORK

A method for achieving adaptive (on-line) behaviour is to continuously evolve logic. An example of this is demonstrated in [6] where neural network controllers for a single robot are continuously evolving in the actual environment (i.e. in situ). To avoid constant relearning, [3] presents a method for tracking near-optima solutions in dynamic environments by evaluating potential solutions in simulation,

but only executing the current best solution. These frameworks perform the in situ evolution of logic on a single machine and so do not address the distributed coordination issue relevant to sensor networks. The Distributed Genetic Programming Framework (DGPF) [17] demonstrates the ability to distribute the evaluation of candidate algorithms across multiple computers, however does not attempt to evolve or evaluate logic on the system itself. Thus, the system’s logic is ?xed at run time and potentially brittle depending on the preciseness of the simulation physics. The Genetically Programmed Network (GPN), developed by [16], demonstrates that system-wide coordinated logic can be obtained by evolving the communication connections between nodes whilst simultaneously evolving the logic of each node. Interestingly, the framework shows that one can be fairly agnostic about the logic implementation evolving at each node since feed forward neural networks, recurrent neural networks, rule based and genetic programs could all equally solve the problem. It did show that the evolution of the communications between nodes was of signi?cant importance however. Subsequent experiments also revealed that neural networks with a form of memory required the least amount of logic evaluations to converge to the desired performance. Again, however, the evolution of the logic (and connections in this case) was performed on a single machine and o?-line.

? Comparing the system stability in response to node failures against traditional approaches ? Investigating opportunistic evolution in environments where energy is non-uniformly supplied and/or distributed The following subsections provide a summary of the 3 main themes of this research.

3.1

Online Learning

Acceptable solutions often exist as subspaces within the entire search space of all possible implementations. The technique of iteratively searching through the search space in order to ?nd a better solution is known as optimization and the choice of candidate solutions evaluated along the way is referred to as the optimization trajectory. Evaluating every potential solution yields the ?tness landscape. However, the best optimizer (or solution ?nder) will be domain, or even problem speci?c, as highlighted in the well known ”No Free Lunch Theorem” [18]. For deployed WSANs, the dynamic environment causes the ?tness landscape to vary with time and unforeseeable environmental interactions. This lends the optimization of WSAN logic to on-line (in situ) optimizers. On-line learning, in a machine learning context, refers to the ability of an entity to improve its behaviour, during the course of its life, based on interactions with its environment. There are numerous examples of such systems, including biological systems like ourselves. On-line machine learning can be achieved via a myriad of machine learning techniques including dynamic rule-based systems, XCS, neural networks and reinforcement learning such as genetics based machine learning (GBML) methods. Given the large selection of online optimizers and keeping in mind that no optimizer performs better across all problems, the choice of optimizer may not be highly important - none the less, an optimizer still needs to be selected. Genetic programming has been chosen as an optimizer for this framework for a number of reasons: being an implementation of the genetic algorithm, it will converge towards better solutions based on a ?tness metric; code is arguably more human-friendly to understand than say connectionist parameters like the weights of a neural network; code terminals map directly to physical characteristics of the node. However, online learning and adaptability doesn’t come without its drawbacks. Other (potential) performance metrics such as energy usage and time before acceptable behaviour occurs (convergence time) will typically be worse than that of ?xed logic learnt o?-line. Therefore, these and other metrics will need to be evaluated and compared for IDGP and more traditional approaches. Another important aspect is the e?ect of representational and procedural biases. In particular, procedural biases resulting from the order potential solutions are evaluated in, could prevent desirable solutions from being discovered.

3.

IN SITU DISTRIBUTED GENETIC PROGRAMMING

This research investigates the feasibility of performing the in situ distributed evolution of logic to achieve a desired collective system behaviour under dynamic environmental conditions. A framework is being developed, called In situ Distributed Genetic Programming (IDGP), which takes userspeci?ed ?tness criteria and evolves code in the network itself rather than in a centralised PC. The evolution of code (and perhaps the framework) can continue throughout the life of the deployment in order to achieve life-long system optimization and adaptation to the environment. Key aspects of research include: ? Identifying and determining the e?ects of representational biases [7] incurred by the programming syntax and physical embodiment of the agents ? Identifying and determining the e?ects of procedural biases incurred by the dynamic environment, genetic programming methodology and evaluating in situ ? Implementing constraints on representational and procedural biases in order to avoid catastrophic failure of agents or the system ? Quantifying the tradeo? between IDGP online machine learning versus o?ine machine learning approaches ? Demonstrating the evolution of cooperative behaviours including implicit and explicit communication ? Quantifying the tradeo? between competitive and cooperative evolution ? Quantifying the tradeo? between centralised and decentralised ?tness evaluation and rewards

3.2

Genetic Programming on Motes

WSN nodes typically have the computational ability (albeit constrained) required to perform the mathematics of genetic programming as well as the communications capability required for sharing genetic information. Fortunately, in situ evaluation of potential solutions removes the signi?cant computational burden usually required to simulate the real world physics. Furthermore, each node only needs to execute its own code rather than the code of an entire network of nodes running simultaneously. Finally, there is no better training set of the environment than the environment itself and therefore found solutions are likely to work under the same conditions, unlike solutions evolved in simulation which often do not work as expected when exposed to actual environmental conditions. It is possible to still perform the in situ, distributed evaluation of candidate solutions while performing the genetic operations in a centralised location (such as a base PC). Unfortunately, this introduces a central point of failure which undesirable for many control systems. Achieving distributed genetic evolution and evaluation generates a number of challenges however. Firstly, to calculate the global system performance, a ”God’s eye” view, capable of seeing the state of all entities in the entire system simultaneously, is required. For a distributed system to evaluate itself, a distributed evaluation of ?tness will be required and methods using local information metrics such as those used in [14] will be investigated . Secondly, the genetic programming process does not lend itself to running on such impoverished devices easily. A genetic programming framework will typically use lots of CPU cycles, large amounts of memory and communications - all of which consume energy. Nodes in a WSAN are usually highly constrained in memory, processor speed, communications bandwidth and range, and energy. Limitations in memory and bandwidth can be overcome given a tradeo? with evolution time. However energy has been an important issue in WSNs since its inception and is discussed in more detail in the following section. Finally, the act of evaluating logic could be detrimental to the current system performance. This could be a potential catastrophe for the WSN, particularly if any nodes entered an undesirable state from which they could not recover. Therefore each node must be able to execute evolved code in a manner that will not prevent it participating in the next epoch or preventing other agents from participating in the next epoch. This criteria appears deceptively simple, however there are many non-trivial issues and tradeo?s required to achieve this. For example, using energy to evaluate and evolve new code could be classi?ed as detrimental to the node if its battery is low.

No 1 2 3 4 5 6

Table 1: Milestones Milestone Establish a Genetic Programming Engine Evolve code (GP) on a WSN mote GP on multiple motes with global feedback Establish a method for Distributed System Evaluation GP on many motes with no global feedback GP on many motes with non-uniform energy distribution

over the next 5 billion years or so, that energy is not uniformly supplied in space or time. For solar powered WSNs, this results in periods of little or not input energy through to periods where excess energy is simply wasted [4]. A good use of excess energy is to explore new logic (play) and optimize existing logic (train). The subtle di?erence between this optimization method and genetic evolution is a matter of timing. Normal day-to-day operation is allowed to continue, however if the time and energy is available, then playing or training can be performed without a?ecting the perceived operation of the entity. Similarly, WSN nodes could attempt to optimize or search for better solutions in between servicing the intended network operation.

4.

EXPERIMENT PLAN

The ultimate goal of this research is to evaluate the practicality and usefulness of IDGP for WSANs. To achieve this, the milestones presented in Table 1 will need to be achieved. The immediate focus will be implementing a framework that performs genetic programming on a single node with externally supplied feedback. This will be tested by evolving simple wall following behaviour similar to [5]. The framework will then be extended to allow the evolution of code based on a ?tness calculated locally. To verify the feasibility and usefulness of the framework for solving distributed sensing and actuation problems, the framework will be used to ?nd solutions for the well studied ([12], [2], [11] and others) box pushing problem. IDGP evolved solutions will be compared against hand-crafted solutions (written in NesC or FOS) as well as other known solutions. Initial physical instantiations will occur in small (10 Fleck Cars) WSAN testbed in a constrained, monitored environment. As the framework matures however, the constraints will be progressively removed. A number of performance metrics will be evaluated for each solution generator. These include, time of human involvement to task the network or debug the network, convergence time of the system to solve the task, robustness to varying environmental conditions such as lighting, scalability with node numbers and energy usage. Aspects mentioned in section 3 will also be investi

赞助商链接
更多相关文档:
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com