Sensor Networks
Sensor networks are transforming the way we deal with the physical world with applications ranging from enviromental monitoring to security and health-care. Each application has different requirements and constraints which have to be carefully designed for. However, three broad needs are common to most sensor networks: energy efficiency, speed of data collection and reliability, for example to node failures or malicious attacks. Our research program addresses these broad neds by developping fundamentally new techniques. We are currently validating these ideas in a testbed of Tinyos sensor nodes.
In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit. For instance, sensors used for monitoring whether and at what location an environmental hazardous situation may occur need to send their location and very few bits, albeit at very short time intervals, to convey as fast as possible the alarm information. We are interested in addressing the question of how should communication happen in such identity-aware sensor networks. To do so, we need to re-examine the traditional source-identity/message separation and propose a scheme for jointly encoding the two, through a specifically designed coding scheme. We have recently developed a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks—for instance, node failures, or large numbers of nodes where only few are active during each reporting round. We are planning to extend these ideas to sensor networks that convey GSM (location) information, to infrastracture sensor networks for transportation networks.
In many situations, what one does not say conveys information, just as what one might say. This idea can be used in wireless sensor networks by utilizing silence to convey information and thereby reducing the energy used. We explored this in the context of function computation in wireless sensor networks. We develop provable protocols that allow information to be inferred by the fact that nodes remain silent. We thus use silence and time to minimize the amount of communication required to compute various functions. We investigate the time-complexity trade-off such protocols offer, in a communication-complexity framework. We focus our attention on symmetric functions (where the ordering of the variables do not matter), that include most statistical functions and functions of interest for sensor networks. For such functions we develop methods that are optimal (worst case and average communication complexity). We believe that these ideas are very promising for health-monitoring sensor networks (for example, on-the-body sensors), where minimizing the number of node transmissions can also reduce health risks, and this is a direction we plan to further pursue.
Multipath diversity techniques in sensor networks construct multiple paths from each node sensor to the sink, allowing more freedom in route selection, and thus achieving higher reliability; less intuitively, under certain circumstances, they even achieve lower energy consumption. Network coding allows to achieve the benefits of multipath diversity, namely, increased reliability, by opportunistically taking advantage of broadcasting, at a significant savings of the network resources. Our first proposed techniques are currently being deployed in a TinyOs prototype at EPFL. We plan to continue working both on the theoretical foundations as well as prototype implementations of these ideas, as we believe they can have a significant impact in future sensor networks.
Publications
- , , , and , Joint identity-message coding for sensor networks, IEEE JSAC on Wireless Sensor Networks, 2010In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit---for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occurred, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks. We calculate theoretical performance bounds for this type of communication, where ``performance'' refers to the number of transmitted bits. We propose a communication protocol, where the identity and message of each source are specified jointly using subspace coding. We show through analysis and simulation that our protocol's performance is close to optimal and compare it to the performance of a traditional protocol, where identity and message are specified separately.
- , and , Silence based communication, IEEE Transactions on Information Theory, 56, 2010Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and average-case complexities of symmetric functions are studied. For binary-input functions the average- and worst-case complexities are determined and the protocols achieving them are described. For functions of non-binary inputs one-round communication, where each party is restricted to communicate in consecutive stages, is considered and the extra amount of communication required by one- over multi-round communication is analyzed. For the special case of ternary-input functions close lower and upper bounds on the worst-case one-round complexity are provided and protocols achieving them are described. Protocols achieving the average-case one-round complexity for ternary-input functions are also described. These protocols can be generalized to inputs of arbitrary size.
- , , and , Compressed network coding vectors, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.
- , , , and , Identity aware sensor networks, in INFOCOM 2009, IEEE, 2009In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.
- , , and , SenseCode: Network coding for reliable sensor networks, EPFL Technical Report, in submission, 2009Designing a communication protocol for sensor networks often involves obtaining the ``right'' trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks---and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it achieves higher reliability (typically 20%, in certain cases up to 30%), while consuming the same amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through TOSSIM simulations, as well as a testbed of 30 TinyNode sensors deployed in our department building
- , and , Silence based communication for sensor networks, ISIT, 2006We consider a power-efficient communication model for wireless sensor networks where silence is used to convey information. We study the average-case and worst-case complexities of symmetric functions under this model and describe protocols that achieve them. For binary-input functions, we determine the average complexity. For ternary-input functions, we consider a special type of protocols and provide close lower and upper bounds for their worst-case complexity. We also describe the protocol that achieves the average complexity.
- and , Conditions for constant throughput in wireless networks, ACM Transactions on Sensor Networks, 2, 2005In this paper we propose a set of necessary and sufficient conditions under which the throughput in an ad-hoc network can remain constant as the number of nodes $n$ increases. Throughput refers to the minimum achievable rate between a source-destination pair for a given routing mechanism and physical model, when the network is shared by $\Theta(n)$ randomly chosen source-destination pairs. The main idea is to use a {\em connectivity graph}, that does not represent the actual physical network, but rather the available communication resources. This graph also allows to translate the problem of maximizing t he throughput in ad-hoc networks to the multicommodity flow problem and directly apply related results.
