Mobile Computing and its infrastructure support:
Mobile Crowd Sourced Sensing
leverages large numbers of mobile devices with data collecting
capabilities to provide input for Smarter Planet applications. It seeks
to build a common infrastructure that interacts with devices,
configures their data gathering activities based on declarative
requirements from backend applications
Crowdedness Detection allows
mobile devices to quickly and efficiently identify most of the
neighbors by leveraging the knowledge of each other. It provides a
basic function that enables interactive user experience in many Mobile
Cloud and wide area messaging:
Cloud based publish/subscribe service exploits
the natural skewness in data distribution to provide a scalable and
elastic attribute-based pub/sub service that has linear capacity
scaling and multi-fold higher throughput than existing systems.
Responsive, Reliable and Real-Time Messaging delivers
critical and time-sensitive information across wide area networks among
end points in physical and digital worlds. It adopts multiple
techniques to discover reliable routing paths and schedule message
deliveries in time.
Distributed Stream Processing Systems:
Hybrid high availability addresses
"transient unavailability" in stream processing systems by
intelligently switching between active and passive standby mechanisms.
It reduces recovery time by two-thirds and message overhead by 80%,
and reproduces results as if no failure had happened.
Cooperative Stream Processing
enables multiple autonomous stream processing systems to collaborate
and further scale up the processing capabilities. It enables analysis
and processing that are difficult or impossible in individual systems.
Federated Resource Discovery
provides a unified search interface so that stream processing
applications can locate and utilize resources in different autonomous
systems over wide area networks.
Data Source Management
discovers and allocates data sources for stream processing
applications. It maintains the characteristic descriptions of
potentially millions of data sources, and select the most suitable ones
given applications' requirements.
decides the optimal schedule for reserving remote resources among
stream processing systems, such that an application execution plan can
be satisfied within the required budget and time constraints.
Sensor Network Data Forwarding:
Gradient Broadcast (GRAB) in sensor networks
GRAB addresses the reliable deliver of sensing data through a vast field
of small, vulnerable sensors which may fail frequently and communicate
via lossy wireless links. We propose a new set of mechanisms and protocols
which is designed specifically for robust data delivery for large scale
sensor networks in a harsh or even hostile environment. GRAB first builds
and maintains a cost field, providing each sensor the direction to forward
sensing data. It then forwards data along a band of interleaved mesh
from each source to the receiver. GRAB controls the width of the band by
the amount of credit carried in each data message, allowing the
sender to adjust the robustness of data delivery. The design harnesses
the advantage of large scale and relies on the collective efforts of multiple
nodes to deliver data, without dependency on any individual ones. We have
evaluated the GRAB performance through both analysis and extensive simulation.
Our analysis shows quantitatively the advantage of interleaved mesh over
multiple parallel paths. Our simulation further confirms the analysis results
and shows that GRAB can successfully deliver over 90% of packets over 30
hops with relatively low energy cost, even under the adverse conditions
of 30% node failures compounded with 15% link message losses.
- Build a cost field for the sink. Each node keeps a cost of sending a
packet to the sink via some path (ideally the minimum cost path). All costs
of the nodes form the cost field. If we imagine that each node is elevated
to a height equivalent to its cost, the whole cost field would look like
a funnel: the sink sits at the bottom, while nodes farther to the sink
- Each packet carries a "credit", which is some "extra" budget that
can be used to deliver a packet over a path. The total cost over the path
must be smaller or equal to the total budget. Thus by controlling the amount
of credit a packet carries, we effectively control the redundancy in the
forwarding paths. These paths interleave and form a forwarding "mesh".
The credit is the means to trade off between robustness and total cost.
The old webpage for GRAB is here.
Two-tier Data Dissemination (TTDD)
Sink mobility brings new challenges to large-scale sensor networking. It
suggests that information about each mobile sink's location be continuously
propagated through the sensor field to keep all sensor nodes updated with
the direction of forwarding future data reports. Unfortunately frequent
location updates from multiple sinks can lead to both excessive drain of
sensors' limited battery power supply and increased collisions in wireless
transmissions. We propose TTDD, a Two-Tier Data Dissemination approach
that provides scalable and efficient data delivery to multiple mobile sinks.
Each data source in TTDD proactively builds a grid structure which enables
mobile sinks to continuously receive data on the move by flooding queries
within a local cell only. TTDD's design exploits the fact that sensor nodes
are stationary and location-aware to construct and maintain the grid structures
with low overhead. We have evaluated TTDD performance through both analysis
and extensive simulation experiments. Our results show that TTDD handles
multiple mobile sinks efficiently with performance comparable with that
of stationary sinks.
- Each source builds a virtual square grid in the network and recruits
a set of nodes at grid crossings as its dissemination nodes. A mobile
sink locally floods a query within a range of a grid cell size to location
nearby dissemination nodes.
- Queries are forwarded along the grid towards the source. Data flow
back in reverse direction. Thus the impact of sinks' mobility is
confined to a local area of about a cell size.
Energy Efficiency in Sensor Networks:
Probing Environment and Adaptive Sleeping (PEAS)
PEAS is a randomized energy-conservation protocol that seeks to build resilient
sensor networks in the presence of frequent, unexpected node failures.
PEAS extends the network lifetime by maintaining a necessary set of working
nodes and turning off redundant ones, which wake up after randomized sleeping
times and replace failed ones when needed. Different from the common practice
of maintaining local neighborhood topology at each node to achieve distributed
coordination, PEAS has only constant state and does not require per neighbor
state at any node. Each node operates based on one single piece of information.
This allows PEAS to scale to very dense node deployment. PEAS is highly
robust against node failures due to its simple operations and randomized
design. It also ensures asymptotic connectivity. Our simulations
and analysis show that PEAS can maintain an adequate working node density
in presence of as high as 38% node failures, and a roughly constant overhead
of less than 1% of the total energy consumption under various deployment
densities. As a result, PEAS extends a sensor network's functioning time
in linear proportional to the deployed sensor population.
- There's only one simple rule about which nodes can work: the distance
between two neighboring working nodes should be at least Rp, which is a
system parameter that determines the density of working nodes. Rp should
be less than the maximum transmission range Rt to ensure connectivity of
- After deployment, each node first sleeps for an exponentially distributed
time. When a node wakes up, it broadcasts a PROBE message within Rp. If
any working nodes is within Rp, it sends back a REPLY (also within Rp).
Upon hearing a REPLY, the probing node sleeps again, for another dynamically
adjusted period of time; If it doesn't hear any REPLY, it starts working,
until it uses up energy or fails.
Security in Sensor Networks:
Statistical En-route Filtering of Injected False Data (SEF)
In a large-scale sensor network individual sensors are subject to security
compromises. A compromised node can inject bogus sensing reports into the
network. If undetected, these bogus reports would be forwarded to the data
collection point (i.e. the sink). Such attacks by compromised sensors can
cause not only false alarms but also the depletion of the finite amount
of energy in a battery powered network. In this paper we present a Statistical
En-route Filtering (SEF) mechanism that can detect and drop such false
reports. SEF requires that each sensing report be validated by multiple
keyed message authentication codes (MACs), each generated by a node that
detects the same event. As the report is forwarded, each node along the
way verifies the correctness of the MACs probabilistically and drops those
with invalid MACs at earliest points. The sink further filters out remaining
false reports that escape the en-route filtering. SEF exploits the network
scale to determine the truthfulness of each report through collective decision-making
by multiples detecting nodes and collective false-report-detection by multiple
forwarding nodes. Our analysis and simulations show that, with an overhead
of 14 bytes per report, SEF is able to drop 80~90% falsely injected reports
by a compromised node within 10 forwarding hops.
- Divide a gloal key pool into n non-overlapping partitions.Each node pick
k keys randomly from one of the n partitions. Thus only two nodes picking
keys from the same partition has certain probability of sharing keys.
- Multiple detecting nodes each generates a keyed Message Authentication
Code (MAC) and sends to an elected CoS (Center of Stimulus) node. CoS attaches
the MACs to the final report - Each forwarding node has probability of
possessing one of the keys used in the attached MACs, thus verifying the
correctness and dropping those reports forged by attackers
A Location Dependent Approach to Secure Report Generation in Sensor Networks
Existing sensor security mechanisms provide little protection
when some nodes are compromised and secret keys revealed.
Compromised nodes can inject false data about non-existent events
to waste network resources in delivering them and produce
false alarms that destruct the user's responsiveness to real events.
To prevent these damages, we explore the ``location-awareness''
of sensors to develop a new security mechanism called Location Dependent
Keys (LDK). In LDK, keys are not bind to nodes, as in most existing work,
but to geographical locations.
When an event happens, detecting nodes generate credentials for
the report using keys binded to the event's location. By showing
that the report is endorsed by such keys, reporting nodes prove they
are at that location and able to observe what happens there.
Thus a compromised node cannot forge reports about arbitrary remote
events because it does not have the corresponding keys.
We then exploit the a prior knowledge on the
location properties of the sink and data delivery paths to detect
and drop bogus
reports en-route. Each node can estimate reports originated from
which locations it may need to forward and store keys of these
locations with a carefully designed
probability distribution. Thus every forwarding node can detect
bogus reports passing through it probabilistically. By accumulating
detecting power over multiple hops, most bogus data are dropped before
reaching the sink. Finally, the sink can reject
the few false reports that escaped the en-route filtering,
because it possesses the keys binded to all the locations.
Probabilistic Nested Marking for Traceback
identifies the exact origin of attacking packets, such that compromised
insider nodes can be isolated from the network. It was the first work
that addresses colluding attacks by multiple compromised nodes.