Archive for the ‘paper’ Category

Social Tapestries: Mobile spatial annotation

Friday, July 27th, 2007

From this post: “Raj Kottamasu, a Master in City Planning Degree Candidate at the Department of Urban Studies and Planning at MIT has posted his thesis, Placelogging (PDF 12Mb) online which contains a study of the Social Tapestries projects (among others) in relation to urban planning. The thesis looks at Mobile spatial annotation and its potential use to urban planners and designers and is an impressive, readable and stimulating piece of research”.

Mapping Small Worlds

Thursday, June 28th, 2007

Here you’ll find a paper I have got accepted for P2P2007. In synthesis: given a social network of peers, I’m interested in constructing a “network map” — that is, a

way of placing nodes in a k-dimensional layout — so that nodes that are more likely to be linked as they are closer in the layout. The algorithm has to be decentralized, and I accomplished this by requiring each node to exchange information only with its “friends”. Once we have such a layout, we can use in various settings. The most obvious application is routing in “darknets” such as Freenet (networks where connections are only between trusted pairs of friends): we use the position on the layout of a node as an “address”, and we try to reach the destination node by routing the query to the closest node. This way we obtain efficient anonymous routing. Other applications can be related to network analysis (e.g., we can recommend to an user some content that is ‘affine’: closer on the network map), or to trust metrics (e.g., finding paths in social networks that connect nodes to assess trust). I did this by adapting an algorithm for graph drawing based on spectral graph theory to decentralized systems. Results are very encouraging. I think it could be interesting to see if the same idea can be applied to opportunistic networks, in order to analyze social structure and/or do routing.

Privacy in Ubicomp: Devices that Tell on You

Wednesday, June 6th, 2007

At USENIX Security, a paper will show how three consumer devices leak personal information.

We analyze three new consumer electronic gadgets in order to gauge the privacy and security trends in mass-market UbiComp devices. Our study of the Slingbox Pro uncovers a new information leakage vector for encrypted streaming multimedia. By exploiting properties of variable bitrate encoding schemes, we show that a passive adversary can determine with high probability the movie that a user is watching via her Slingbox, even when the Slingbox uses encryption. We experimentally evaluated our method against a database of over 100 hours of network traces for 26 distinct movies.
Despite an opportunity to provide significantly more location privacy than existing devices, like RFIDs, we find that an attacker can trivially exploit the Nike+iPod Sport Kit’s design to track users; we demonstrate this with a GoogleMaps-based distributed surveillance system. We also uncover security issues with the way Microsoft Zunes manage their social relationships.
We show how these products’ designers could have significantly raised the bar against some of our attacks. We also use some of our attacks to motivate fundamental security and privacy challenges for future UbiComp devices.

Vehicles and pervasive computing

Sunday, May 27th, 2007

As you might now I attended PerCom a couple of months ago.

During the panel discussion, there was an interesting conclusion that vehicles are the most pervasive devices available today.
If you think about it vehicles contain a large number of sensors:

  • Speed
  • Acceleration
  • Yaw, G sensors (for ESP)
  • Temperature (environment, engine, tires)
  • Light sensors (automatic lights etc)
  • Fuel consumption, oxygen level, CO2 levels
  • GPS, Navigation system, maps etc.
  • Noise (to automatically regulate car radio volume)

Furthermore, modern vehicles have a number of ways to communicate (FM Radio (RDS,TMC), Bluetooth, GSM, soon 802.11n (WAVE) ). In my opinion, all these features already constitute vehicles as mobile sensor platforms. By exploiting already available sensors we can design numerous applications:

  • Road traffic monitoring (using acceleration and speed sensors)
  • Distributed pollution and temperature monitoring
  • Parking information
  • Formation of platoons of vehicles (e.g. maximize road capacity)
  • Dissemination of warning information
  • Accident avoidance (e.g. break when approaching a red light fast)
  • Visual enhancement (e.g. provide information on the windshield about traffic ahead, red light warning).
  • Landmarks/advertisement
  • Communication between vehicles (voice/file sharing etc)

All these application can be implemented either centrally (e.g. using GSM) or in an Ad-Hoc manner. Although the first approach is more reliable and fast it has some disadvantages:

  • Centralized data may be outdated and the response time may not meet the real-time requirements. Especially if we want local information (like “is the traffic light ahead red?”, “is there a parking spot within 100m?”)
  • Current centralized communication solutions (GSM, WiMAX) may not be able to handle the burden of real-time monitoring of hundreds of thousands of vehicles. These services are allready congested with million of mobile phone users.
  • Infrastructure could be quite expensive, especially if the area to be covered is large. Furthermore, infrastructure may not be available, especially in remote and isolated areas (you haven’t been on mountains in Greece ;) ).
  • Ad-hoc service is free and it can provide more concentrated local information (e.g. advertisements etc)

However, there are a lot of research issues in order to implement all these Ad-Hoc applications:

  • We need robust routing protocols that work both in dense urban areas and sparser areas (e.g. DTN).
  • We need dissemination protocols that take into account the interest of the vehicles/drivers to avoid flooding the drivers with unnecessary information and cause congestion to the network
  • We need MAC protocols that are able to deliver information to high-speed moving vehicles.
  • We need extremely robust trust and security mechanisms because there are human lives at risk!!

My last year’s research was manly focused on two areas:
How to exploit the navigation system of the car to route and disseminate messages, and how to use the Publish/Subscribe communication paradigm to achieve that.

Navigation systems are becoming more and more popular. A part from navigation suggestions, navigation systems provide valuable information that is currently not generally used. First of all, the GPS unit provides the vehicle’s geographical location. Furthermore, the NS map provides various geographical information: street names and numbers, location of points of interest (like fuel stations, train stations, etc), kilometer ranges, etc. This information may be extended to include the location of known infostations so that the vehicle can geographically route information to them.

At the same time, the most important information that the NS provides is the suggested route of the vehicle: This information 1)makes the mobility patterns of the vehicles more predictable. Additionally, 2)it can be exploited to extract interests, which can be used to design efficient routing and dissemination protocols and to filter information that is only relevant to the driver without his/her intervention (for example an accident warning affects only vehicles that will drive near the accident).

Therefore, in the last months I examined how we exploit the navigation systems (suggested routes to predict mobility patterns and to extract subscriptions) in order to design a vehicular routing algorithm and a Publish/Subscribe system.

You can find the results here
There is also some additional work on Pub/sub issues but we have to wait the reviewers first :)

Ilias Leontiadis

Vehicular nets: a promising application of reputation models

Monday, May 7th, 2007

In Italy, hackers have introduced erroneous messages into the traffic signal sent to GPS devices (article). This exemplifies the pay someone to do your assignment need of security for vehicular networks. Part of the needed security mechanims may be offered by reputation (trust) models as two recent papers show:

A Data Intensive Reputation Management Scheme for Vehicular Ad Hoc Networks (pdf)
On the Benefits of Cheating by Self-Interested Agents in Vehicular Networks (pdf)

Sociometric Badge

Friday, May 4th, 2007

From this post. Sociometric Badge, a sensing platform that logs voice features, proximity to other individuals, face-to-face interactions, and movement. Results of an analysis of data obtained in a preliminary study at a German bank’s marketing division:

. Proximity is highly negatively correlated with e-mail use
(-> if you are in close proximity to another individual, it makes more sense to interact with them in the real world rather than send them an e-mail)

. Communication between managers and employees was very highly negatively correlated with perceived interaction quality ( -> having more interactions with either your subordinates or your boss is draining).

. Email and proximity ties were highly correlated when communication was present and both individuals were of the same hierarchical level
(-> e-mail communication between individuals with the same role increases as their proximate time increases)

(paper to appear in NetSci ’07)

Learning and Inferring Transportation Routines

Wednesday, January 31st, 2007

This paper (whose extended journal version has been recently accepted) proposes a hierarchical Markov model that learns and infers a user’s daily movements.

Scale-free networks emerging from weighted random graphs

Friday, January 5th, 2007

An alternative explanation for the emergence of scale-free degree distributions:

A uniformly random weight is assigned to each edge in a classical random graph. Nodes connected by edges with weights less than the graph’s percolation threshold are collapsed into supernodes. The resulting graph has a power law degree distribution.

BitTyrant: a selfish BitTorrent client that improves performance

Friday, January 5th, 2007

BitTyrant is a BitTorrent client with a novel unchoking algorithm.

Suppose your upload capacity is 50 KBps. If you’ve unchoked 5 peers, existing clients will send each peer 10 KBps, independent of the rate each is sending to you. In contrast, BitTyrant will rank all peers by their receive / sent ratios, preferentially unchoking those peers with high ratios.

During evaluation testing on more than 100 real BitTorrent swarms, BitTyrant provided an average 70% download performance increase when compared to the existing Azureus 2.5 implementation, with some downloads finishing more than three times as quickly.

I wonder how well it performs in swarms of other BitTyrant clients?

The USENIX paper is here.

Update: it seems to be using the same faster than the bear algorithm I came up with last year. Damn it, I should have tried it out. :-)

Really tiny wireless sensor node

Wednesday, December 6th, 2006

This paper published in Biology Letters is linked to a video that shows a WSN attached to the belly of a dragonlfy. It weights 300mg (battery included) and apparently dragonflies do not have a problem carrying it around.

This is made by a guy called Jim Cochran who runs Sparrow Systems with his dad — they both sound like very nice people and from the look of it they can build stuff that works (rather than the usual WSN vaporware).

Dynamic Congestion Charge & Vehicular Ad-Hoc Networks

Wednesday, December 6th, 2006

Comments on Sensor Web Design Studies for Realtime Dynamic Congestion Pricing (here)

Situation: Traffic congestion is a fundamental problem. To avoid it on some streets, one may charge drivers accessing those streets. For simplicity, one usually charges a fixed rate (e.g., London congestion charge).  However, dynamic pricing is preferable – one charges depending on information about local road events, public event calendars, road segments, and congestion patterns.
Problem: The pricing model needs to gather such information.
Proposal: This paper proposes to do so by collecting readings from sensors and from aircrafts/UAVs with video cameras.
Future: To extend this proposal, one may be inspired by existing work on ad-hoc vehicular nets (e.g.,  by Ilias‘ recent work). What about  ‘Realtime Dynamic Congestion Charge with Vehicular Ad-Hoc Networks’?

Suicide for the common good

Friday, November 24th, 2006

Very simple, yet interesting paper: Suicide for the common good: a new strategy for credential revocation in self-organizing systems.

Problem: Credential revocation in self-organizing systems.

Existing Solution: If a node believes another has misbehaved,
then it can carry out punishment.

Complication: A malicious node can falsely accuse legitimate

Proposal: Upon detecting a node M engaging in some illegal activity,
A broadcasts a signed suicide note which includes the
identities of both A and M. The other nodes in the network
then verify the signature and, if correct, revoke both
A and M.

1. Attacker benefit from removing one innocent node must
be less than the benefit of having a malicious node
placed inside the network.
2. Honest nodes share common interest
(this is reasonable whenever the nodes are deployed by a single
entity (e.g., a sensor network deployed on a battlefield)
3. An absence of unforgeable, independently verifiable
and conclusive proof.
4. Low likelihood of two good nodes accusing each other.
5. Difficult to prevent malicious nodes from issuing false