Invited Talks and Conference Presentations

Slides

Searching the Physical World: Towards a Search Engine for Wireless Sensor Networks

The constant improvements in computing and storage technologies as envisioned by Moore's Law, along with the progress in battery technology and micro-electro-mechanical systems, have revolutionized a new distributed embedded computing, where tiny low-power devices, i.e., sensors, equipped with a processor, memory, sensing and communication units are networked to support various applications in the scientific, medical, commercial, and military domains. The development of Information Seeking Mechanisms for such environments with extreme resource constraints, with variable channel capacity and with requirements for multimedia in-network processing, implies that we will first achieve a kind of "in-network intelligence", i.e., fully distributed protocols with no centralized supervision able to understand their networking context. This talk will briefly present our efforts toward the desing and development of a search engine for the physical world.

Slides

Searching the Physical World: Distributed Protocols for Caching and Data Coverage in Wireless Sensor Networks

The constant improvements in computing and storage technologies as envisioned by Moore's Law, along with the progress in battery technology and micro-electro-mechanical systems, have revolutionized a new distributed embedded computing, where tiny low-power devices, i.e., sensors, equipped with a processor, memory, sensing and communication units are networked to support various applications in the scientific, medical, commercial, and military domains. These wireless sensor networks (WSNs) have found interesting applications in environmental monitoring, smart homes and offices, intelligent transportation systems and many others. A WSN consists of hundreds or even thousands of sensor nodes that are deployed inside or close to the `phenomenon' being monitored. The positions of sensor nodes need not be engineered or predetermined; the sensors self-organize into an ad hoc network, where the communication among them is performed in a hop-by-hop fashion using multihop paths. WSNs represent a paradigm shift in computing in that they must support energy-efficient operations (since battery recharging is not possible/easy in hostile or harsh environments) and also must act in a cooperative, distributed manner, either because it is the only alternative to fulfill their goal (e.g., in collaborative target tracking scenarios) or because collaboration increases their capabilities (e.g., storage/computing capacity). The development of Information Seeking Mechanisms for such environments with extreme resource constraints, with variable channel capacity and with requirements for multimedia in-network processing, implies that we will first achieve a kind of "in-network intelligence", i.e., fully distributed protocols with no centralized supervision able to understand their networking context. This talk will focus on two aspects of our on-going efforts to develop a search engine for the physical world. The first aspect deals with the notion of data coverage, which is a novel query type aiming at extracting 'Feature Distribution Maps' from WSNs. This problem generalizes earlier research problems, like top-k, skyband, and d-hop dominating sets. The second aspect deals with efficiency and robustness issues for querying WSNs and it is related to the development of cooperative caching protocols for sensor networks. For both these problems, we analyze the challenges involved and present fully distributed protocols for their solution, which do not require central management or building 'network spanners' to ease/support their execution.

Slides

Community-based Content Outsourcing for Content Delivery Networks

Content Distribution Networks (CDNs) balance costs and quality in services related to content delivery. Devising an efficient content outsourcing policy is crucial since, based on such policies, CDN providers can provide client-tailored content, improve performance, and result in significant economical gains. Earlier content outsourcing approaches may often prove ineffective since they drive prefetching decisions by assuming knowledge of content popularity statistics, which are not always available and are extremely volatile. This work addresses this issue, by proposing a novel self-adaptive technique under a CDN framework on which outsourced content is identified with no a-priori knowledge of (earlier) request statistics. This is employed by using a structure-based approach identifying coherent clusters of "correlated" Web server content objects, the so-called Web page communities. These communities are the core outsourcing unit and this talk describes a detailed simulation experimentation which shows that the proposed technique is robust and effective in reducing user-perceived latency as compared with competing approaches, i.e., two communities-based approaches, Web caching, and non-CDN.

Slides

Caching in Wireless Multimedia Sensor Networks

The production of cheap CMOS cameras and microphones gave birth to what is called Wireless Multimedia Sensor Networks (WMSNs). WMSNs introduce several new research challenges, mainly related to mechanisms to deliver application-level Quality-of-Service (e.g., latency minimization). To address this goal in an environment with extreme resource constraints, with variable channel capacity and with requirements for multimedia in-network processing, the caching of multimedia data, exploiting the cooperation among sensor nodes is vital. This talk presents a cooperative caching solution particularly suitable for WMSNs. The proposed described solution exploits sensor nodes which reside in positions of the network that allow them to forward packets or communicate decisions within short latency. These so-called mediator nodes are selected dynamically, so as to avoid the creation of hot-spots in the communication and the depletion of their energy. The mediators are not more powerful than the rest of the nodes, but they have some special role in implementing the cooperation among the sensors. The described cooperative caching protocol includes components for locating cached data as well as for implementing data purging out of the sensor caches. The proposed solution is evaluated extensively in an advanced simulation environment, and it is compared to the state-of-the-art cooperative caching algorithm for mobile ad hoc networks.

Slides

Social Network Analysis for Network Optimization

Social Network Analyis (SNA) ... 

Slides

Interpolating the Air for Optimizing Wireless Data Broadcast

Energy conservation and access efficiency are two fundamental though competing goals in broadcast wireless networks. To tackle the energy penalty from sequential searching, the interleaving of index with data items has been proposed. The current broadcast indexes present significant shortcomings. This talk describes a novel parameterized air index, the interpolation index, which is a tunable structure able to optimize the latency with the tuning time kept at a given amount, and vice versa. Theoretical and experimental results attest that the novel indexing structure outperforms the state-of-the-art air indexing scheme, i.e., the exponential index.

Slides

Cooperative Caching in Wireless Multimedia Sensor Networks

The recent advances in miniaturization and the creation of low-power circuits, combined with small-sized batteries have made the development of wireless sensor networks a working reality. Lately, the production of cheap CMOS cameras and microphones gave birth to what is called Wireless Multimedia Sensor Networks (WMSNs). WMSNs will boost the capabilities of current wireless sensor networks, and will fuel several novel applications. WMSNs introduce several research challenges, related to the delivery of application-level Quality-of-Service (e.g., latency minimization). To address this goal in an environment with extreme resource constraints, with variable channel capacity and with requirements for multimedia in-network processing, the efficient and effective caching of multimedia data, exploiting the cooperation among sensor nodes is vital. This talk describes a cooperative caching solution particularly suitable for WMSNs. The proposed solution is evaluated extensively in an advanced simulation environment, and it is compared to the state-of-the-art cooperative caching algorithm for mobile ad hoc networks.

Slides

Node Clustering in Wireless Sensor Networks by Considering Structural Characteristics of the Network Graph

The deployment of wireless sensor networks in many application areas, e.g., aggregation services, requires self-organization of the network nodes into clusters. Quite a lot of node clustering techniques have appeared in the literature, and roughly fall into two families; those based on the construction of a dominating set and those which are based solely on energy considerations. The former family suffers from the fact that only a small subset of the network nodes are responsible for relaying the messages, and thus cause rapid consumption of the energy of these nodes. The later family uses the residual energy of each node in order to direct its decision about whether it will elect itself as a leader of a cluster or not. This family's methods ignore topological features of the nodes and are used in combination with the methods of the former family. This talk describes a novel distributed clustering protocol for wireless sensor networks, based on a novel metric for characterizing the importance of a node, w.r.t. its contribution in relaying messages. The protocol achieves small communication complexity and linear computation complexity. Experimental results for various sensor network topologies show that the protocol generates only a few clusters, guaranteeing a small number of message relays thus improving network lifetime.

Slides

Generalized Indexing for Energy-Efficient Access to Partially Ordered Broadcast Data in Wireless Networks

Energy conservation and access efficiency are two fundamental though competing goals in broadcast wireless networks. To tackle the energy penalty from sequential searching, the interleaving of index with data items has been proposed. Although, quite important contributions exist on providing broadcast indexes, they have one or more of the following problems. Firstly, all of them assume total ordering among broadcast data, and none considers the more general case of partial ordering. Secondly, they are balanced structures, which does not fit the "linear (one-dimensional) structure" of the wireless medium, in which imbalanced structures may offer significant advantages. Thirdly, they do not take into account the skewness in the access pattern, which prohibits larger performance gains to be reaped. Finally, they require all index items to be of equal size, which may not always give the optimal performance. To cope with all these problems, we introduce a new imbalanced tree-structured index. The new index is shown to be a generalization of two previously proposed high-performance indexes, and it introduces for the first time the problem of indexing partially ordered broadcast data. We present an experimental analysis of the proposed method, contrasting it with competing techniques. The analysis exhibits the efficiency of the proposed index in reducing the energy consumption without noticeably worsening the access latency.

Slides

The Geodesic Broadcast Scheme for Wireless Ad Hoc Networks

Broadcasting is an effective means for disseminating information in wireless ad hoc networks. Straightforward broadcasting by flooding causes the so-called broadcast storm problem. This talk describes a novel distributed broadcasting protocol in wireless ad hoc networks, which is based on an highly efficient metric for characterizing the importance of a node, with respect to its contribution in covering the local neighborhood. The protocol is reliable, in the sense that for any connected network a source node can disseminate a message to the whole network. It also achieves small communication complexity with linear in the number of nodes computation complexity. Experimental results for a large variety of network topologies show that the proposed algorithm is capable of generating small connected dominating sets, which guarantee a relatively small number of rebroadcasts.