SenSys'05 conference.

Some notes from the SenSys'05 conference. I attended only tangentially (I assisted at the first keynote, but had to leave right afterwards).

• Radio Interferometric Geolocation. Miklos Maroti, Branislav Kusy, Gyorgy Balogh, Peter Volgyesi, Andras Nadas, Karoly Molnar, Sebestyen Dora, Akos Ledeczi (Vanderbilt University)
  This paper might be very interesting for multiple applications outside of the sensor network world, despite sensors being its primary focus. The idea is to send two signals with slightly different frequencies from two sources, and two observe the phase of the cumulative signal at the receiver. Based on the phase, the receiver can obtain its distance from the sources. This allow to perform geolocation (localization, positioning) at little cost, since there is no need for GPS or dedicated (cricket-like) hardware.
  Application is obvious for positioning of a handset (caveat: I am not aware of the techniques currently used, it might already be something similar). This could be used for indoor localization, or for emergency services localization. The technique is simple enough so that it could be easily implemented on a handheld device.
  
  
  
• High-Accuracy, Low-Cost Localization System for Wireless Sensor Network. Radu Stoleru, Tian He, John A. Stankovic, David Luebke (University of Virginia)
  This is a paper on localization, which, unlike the previous one, has no applicability to cellular networks. It uses dedicated hardware to measure the distance of the distributed sensors. Localization cannot be performed in real-time, and requires the sensor nodes to be static.
  
  
• A New Approach for Establishing Pairwise Keys for Securing Wireless Sensor Networks. Arno Wacker, Mirko Knoll, Timo Heiber, Kurt Rothermel (Universität Stuttgart)
  I have not read this paper, its applicability to my work seems limited.
  
  
• TSAR: A Two Tier Sensor Storage Architecture Using Interval Skip Graphs. Peter Desnoyers, Deepak Ganesan, Prashant Shenoy (University of Massachusetts Amherst)
  I have not read this paper in details, it is about distributed storage and a hierarchical architecture to perform storage, not unlike a distributed hash table.
  
  
• A Macroscope in the Redwoods. Gilman Tolle, Joseph Polastre, Robert Szewczyk, Neil Turner, Kevin Tu, Stephen Burgess (UCB), David Gay, Phil Buonadonna, Wei Hong (Arch Rock Corporation), Todd Dawson, David Culler (UCB)
  This paper is describes an experimental approach for observing an ecosystem using sensor network. I saw most of the material presented in this paper during a keynote talk by David Culler for the MobiHoc 2005 conference. The sensor network is used to extract data streams, such as the temperature and humidity in a redwood grove as a function of the elevation into the tree. Very interesting as an environment monitoring tool.
  
  
• Design and Deployment of Industrial Sensor Networks: Experiences from the North Sea and a Semiconductor Plant. Robert Adler, Phil Buonadonna, Jasmeet Chhabra, Mick Flanigan, Lakshman Krishnamurthy, Nandakishore Kushalnagar, Lama Nachman, Mark Yarvis (Intel)
  This is the poster child for sensor network in industrial monitoring application. It is the example given by Intel people as to what is the application for sensor networking. I was surprised to see this presented here, as I was convinced it had been presented already. Basically, it describes the deployment of a sensor network for monitoring instrumentation on an oil tanker, and for monitoring vibrations in a silican wafer manufacturing plant. In both cases (for which the cost of wiring is extremely harsh), the wireless sensor network proves superior.
  
  
• A Unifying Link Abstraction for Wireless Sensor Networks. Joseph Polastre, Jonathan Hui, Philip Levis (University of California, Berkeley), Jerry Zhao (ICSI Berkeley), David Culler (University of California, Berkeley), Scott Shenker (ICSI Berkeley and University of California, Berkeley), Ion Stoica (University of California, Berkeley)
  This paper argues that the "narrow waist" of the protocol stack for sensor networks should be at the link layer, and not at the network layer, as it is in IP.
  
  
• Z-MAC: A hybrid MAC for wireless sensor networks. Injong Rhee, Ajit C. Warrier, Mahesh Aia, Jenogki Min (NCSU) Prashant Patel (Progress Energy)
  I did not look into the details of the protocols, but it looks like another TDMA-CSMA hybrid. It might be interesting, but it is definitely not exciting.
  
  
• Packet Combining in Sensor Networks. Henri Dubois-Ferriere (EPFL), Deborah Estrin (UCLA), Martin Vetterli (EPFL)
  The very good idea of the paper is relatively simple: when transmitting a packet over multiple hop, say from A to B to C, C might overhear some of the transmission from A to B. Thus it does not require a perfect transmission from B to C, but just enough so that it can reconstruct the packet. Of course, using coding so that the packet from A to B is the original data, and the packet from B to C is some packet of same length made of parity bits, which allows a more efficient decoding at C than just transmitting the orginal packets twice between A and B and between B and C.
  
  [update: these notes were written in 2005. But as I put them here, I see that I just read a paper by Ed Knightly's group to appear in Infocom'07 which puts out a very similar idea.]
  
  
• Siphon: Overload Traffic Management using Multi-Radio Virtual Sinks. Chieh-Yih Wan (Intel Research), Shane B. Eisenman (Columbia University), Andrew T. Campbell (Dartmouth College), Jon Crowcroft (Cambridge University)
  The idea is to detect congestion in the network, which is typically due to funneling effect: all the traffic fans in towards the data sink. The combat this fanning in issue, another sink, using a different radio connection towards the initial sink, can be placed in the network to redirect traffic.
  This is a relatively obvious result: you add capacity where you need it. I fear it might be a technique with limited applicability: coming up with new hardware to reduce traffic in a hot spot might make sense in a static sensor network, but not in a dynamic environment. I guess it all depends on the granularity of the time scales.
  
  
• Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks. Saurabh Ganeriwal (University of California Los Angeles), Deepak Ganesan (University of Massachusetts), Hohyun Shim, Vlassios Tsiatsis, Mani B. Srivastava (University of California Los Angeles)
  I did not go into the details of this one. Power saving technique might have application outside of the sensor network universe, but it seems cellular clock sync is working. It also seems that the dynamic aspect of the cellular environment might prove too challenging for these techniques.
  
  
• Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects. Geoffrey Werner-Allen, Geetika Tewari, Ankit Patel, Matt Welsh, Radhika Nagpal (Harvard University)
  This paper present a node synchronization protocol based on locking in phase with ones neighbor, a process similar to that of the dance of the fireflies. It is cute, but the real-world applicability seems far away.
  
  
• Data Collection, Storage and Retrieval with an Underwater Optical and Acoustical Sensor Network. Iuliu Vasilescu, Keith Kotay, Daniela Rus (Massachusetts Institute of Technology), Peter Corke, Matthew Dunbabin (CSIRO Australia)
  Under-water sensor network is a challenging application, but not of much interest to me.
  
  
• MAX: Human-Centric Search of the Physical World. Kok Kiong Yap, Vikram Srinivasan, Mehul Motani (National University of Singapore)
  This is a paper to allow localization of object using a taxonomy which is easily understandable by a human user. This might be of interest to the UI community.
  
  
• CenWits: A Sensor-Based Loosely-Coupled Search and Rescue System using Witnesses. Jyh-How Huang, Saqib Amjad, Shivakant Mishra (University of Colorado, Boulder)
  The paper describes a search and rescue systems which functions as follows: people wear tags (802.11 based, but one assume RFID could be an alternative technology); some readers are distributed in the environment, and take a reading of the tags. When a catastrophe occurs (say, an avalanche), the tag readings are used to locate the users.
  There is a huge privacy issue here. On the other hand, the system could be integrated on a cell phone, so that the 'tag' becomes the handheld device. I guess it is practical of people of University of Colorado to come up with avalanche rescue systems. I wish I could work there, the experimentation must be fun!
  
  
• Cyclops: In Situ Image Sensing and Interpretation in Wireless Sensor Networks. Mohammad Rahimi (Center for Embedded Networked Sensing - UCLA), Rick Baer (Agilent Technology), Obimdinachi I. Iroezi, Juan C. Garcia (Center for Embedded Networked Sensing - UCLA), Jay Warrior (Agilent Technology), Deborah Estrin, Mani Srivastava (Center for Embedded Networked Sensing - UCLA)
  This is a sensor network platform which carries a low resolution digital camera, ie a so-called image sensor. This is made in partnership with Agilent Technology.
  
  
• Lightweight Detection and Classification for Wireless Sensor Networks in Realistic Environment. Lin Gu (University of Virginia), Dong Jia (Carnegie Mellon University), Pascal Vicaire, Ting Yan, Liqian Luo, Tian He (University of Virginia), Ajay Tirumala (University of Illinois at Urbana-Champaign), Qing Cao, John. A. Stankovic, Tarek Abdelzaher (University of Virginia), B.H. Krogh (Carnegie Mellon University)
  This paper I did not read in details.
  
  
• Intelligent Light Control using Sensor Networks. Vipul Singhvi, Andreas Krause, Carlos Guestrin, Jim Garrett, H. Scott Matthews (Carnegie Mellon University)
  I think the title says it all: it is a sensor network which controls a lighting system. It seems very application specific.
  
  
• Algorithms for Generic Role Assignment in Wireless Sensor Networks. Christian Frank, Kay Roemer (ETH Zurich)
  This paper (and the next two as well) I did not go into details, as it deals with software support for sensor network, a topic I am not familiar with.
  
  
• VM*: A Scalable Runtime Environment for Sensor Networks. Joel Koshy, Raju Pandey (University of California, Davis)
  I did not go into the details of this paper, as it deals with software support for sensor network, a topic I am not familiar with.
  
  
• Sympathy for the Sensor Network Debugger. Nithya Ramanathan, Kevin Chang, Lewis Girod, Rahul Kapur, Eddie Kohler, Deborah Estrin (UCLA)
  I did not go into the details of this paper, as it deals with software support for sensor network, a topic I am not familiar with.
  

Anti-Packets in Wireless Multi-Hop Network

The Anti-Packets Can Increase the Achievable Throughput of a Wireless Multi-Hop Network, by Petar Popovski and Hiroyuki Yomo, of Aalborg University, ICC'06.

The idea is very simple, and it is one of the few applications that I have seen of the field of network coding, which may actually work. Surprisingly enough, the authors don't seem to know what network coding is. At least, they don't mention it.

This paper came at about the same time as the COPE paper from Dina Katabi's group at MIT which presents the same idea with a slightly different approach (COPE is more general). I would guess that, due to the MIT reputation and the publication forum, the citation count for COPE will outnumber the number of citations for this paper by a factor 100, even though both had the same idea at about the same time.

Assume a multi-hop wireless network with 3 nodes, A, B and C. A needs to send a packet AC to C, and C a packet CA to A (both packets of same length and errorless transmissions). The current way of doing it is in 4 time slot: 1-AC from A to B; 2-CA from C to B; 3-AC from B to C; 4-CA from B to A.

The idea of the paper is to combine 3 and 4, and to use the fact that since A and C both hear B, the last step can be: 3-B transmits ACA = XOR(AC,CA) to both B and A.

A, using ACA and AC, can recover CA, and similarly C can recover AC. The gain in bandwidth is 33%.

The throughput can be doubled in an analog manner: if A and C transmit at the same time (slot 1), then B hears a signal composed of both A and C components, A+C. Assuming B hears them both with the same power, then it can just replay the signal it heared in slot 1 in slot 2. It acts only as an amplificator. A hears A+C and can substract its own component to recover the packet from C, and C similarly. Bandwidth gain is 100%.

There are a lot of implementation issues and assumptions that should be debated (it requires symmetric traffic from A to C and C to A, at least bit-wise; synchronization; error recovery mechanisms look more complicated; etc) but the main idea is quite sexy.

Cooperative Communication in Wireless Networks

Cooperative Communication in Wireless Networks, Aria Nosratinia, Todd E. Hunter, Ahmadreza Hedayat, IEEE Communications Magazine, October 2004. Authors with UT Dallas, and Nortel Networks.

The paper is a survey of the field on cooperative networks. Surprisingly enough, it is a short survey, meaning the field is still very new. It has only 11 references. This survey cites the origin of cooperative network in the paper of Cover and El-Gamal (capacity theorems for the relay channel, IEEE Trans. Info Theory, 1979).

The survey categorizes four different types of cooperation: detectand forward; amplify and forward; decode and forward; coded cooperation.

• The first one pairs nodes in a pair, and each partner's node attempts to detect the partner's bits and then retransmits the detected bits.
  
• Amplify and forward is more of an analog version of the first one: the partner receives a signal, and amplifies it. The receiver then decodes based on the signal received fromt the source and from the source's partner.
  
• Decode and forward is a variation of the first one, in which the partner encodes the packet from the source differently, so that the receiver has to different encoding to reconstruct the packet from (similar to the sensys paper by Dubois-Ferriere here, where I found this reference.)
  
• Coded cooperation: each user sneds different portion of each user's code word via two independent fading paths. I guess at the simplest, it is the decode-and-forward above.
  

Performance is strongly improved by cooperation in terms of block error rate.

Paper is low level technical reading (no complex analysis or concepts) and clearly presented. It'd be interesting to know what applications --if any-- Nortel has in mind for this work.

Characterisation of the Performance of Cooperative Networks in Ricean Fading Channels

J. Adeane, M. R. D. Rodrigues and I. J. Wassell, Characterisation of the performance of cooperative networks in Ricean fading channels, Proceedings of the International Conference on Telecommunications, Cape Town, South Africa, May 2005.

Another paper on my list of cooperative network channels. This ones looks at the performance in Ricean fading channels, and consider a simple network topology with two cooperating nodes trying to send data to a single destination, ie. the source-relay-destination triad.

Benefits of cooperation depends on the channel quality between the source and destination and between the source and relay. The paper actually shows a spot in which there is a degradation of the performance created by the cooperation (ie. the information provided by the relay to the destination does not improve that provided by the source, but even interferes with it or contradicts it).

Paper is relatively simple and results are relatively straight-forward, but a good read nonetheless.

Two papers on ad hoc routing

These two papers were suggested by a reviewer of a paper of mine regarding opportunistic routing. They associated these papers with my results, which means I should have differentiated the results better, as it is pretty obvious to me they have little in common.

Anyhow, I have now read the papers:
AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.

On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.

AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.

This paper introduces an extension of AODV which allows for graceful recovery when a link breaks. It uses the query-reply mechanism to build additional back-up routes at nodes adjacent to the route in the path.

Once a link on the route breaks, it can be temporarily recovered using the alternate path, while a route error is sent to the source and a new route discovery is triggered.

The idea is simple and practical, and works fine. It does bring improvement over AODV. The key difference with opportunistic routing is that the alternate is used after a broken link, and is not used otherwise. This means that if the route is reliable, but better links appear later on, these are ignored.

On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.

This is similar to the previous paper, except that it computes link disjoint paths between source and destination. Same as above, the query-reply mechanism of the route discovery is used to set up the multiple link disjoint paths (as opposed to just associated nodes along the path as in the previous paper). In case of link failure, the traffic fails over to another path.

Again, it obviously outperforms AODV. Again, it does not make use of the promiscuous nature of the air interface to forward packets further.

Opportunistic Multi-Hop Routing for Wireless Networks

This are some old notes, but I am consolidating here.

Opportunistic Multi-Hop Routing for Wireless Networks, Sanjit Biswas, Robert Morris, SIGCOMM 2005. Best Paper Award.

This is a continuation upon the work of Biswas and Morris, Opportunistic Routing in Multi-Hop Wireless Networks in HotNets-II, 2003. The previous work is the one which triggered my own work on opportunistic routing, which is basically to adapt Biswas and Morris's to dynamic network using an adapted version of AODV.

The paper presents an extension of the opportunistic routing from the previous paper. However, it seems that there were issues in applying the protocol to the RoofNet network, a mesh network based on 802.11 APs deployed by Morris's group in Cambridge, MA, as the protocol presented here is vastly different from the previous protocol (given also that this came out in 2005, while the previous paper was presented in 12/2003).

One issue is that: all packets end up not being accounted for, and the new paper proposes the opportunistic routing on a batch of paper, and default back to traditional routing once a 90% threshold has be attained for delivery. This is a bit cumbersome, and especially means that no real-life live traffic can be used using this. Heavy file transfers only.

Also, the MAC protocol from the earlier paper (with a RTS/CTS mechanism designed for opportunistic routing) is replaced by a different scheduled MAC, with no specific RTS/CTS. A ExOR header is added which contains information pertaining to the potential relays. This information is based on measurement and probes performed beforehand.

The node which forwards the packet is the closest to destination using an ETX (expected retransmission) metric, ie. a path is chosen not on the number of hops but on how many times the packet would be re-tx-ed to get to the destination. The fewer the re-tx, the closer.

Main issues/challenges regarding my own work: this is highly static. ETX requires to have a good knowledge of the routes a priori, which works if stuff does not move. Then sending a large batch and wait until 90% is transmitted implies that you have massive re-ordering. And some time on your hand, which again means static.

Concern: are the changes to the original protocol (hotnet-II 2003) made because the MAC layer was not accessible in their off-the-shelf 802.11 testbed, or was it made because of performance. The changes move everything up at the network level, so implementation could have driven it.

Performance evaluation of my own protocols will tell...

Opportunistic Packet Scheduling and Media Access Control for Wireless LANs and Multi-Hop Ad Hoc Networks.

Opportunistic Packet Scheduling and Media Access Control for Wireless LANs and Multi-Hop Ad Hoc Networks. J. Wang, H. Zhai and Y. Fang, WCNC 2004.

This paper proposes to perform a scheduling similar to proportional fairness in multi-hop networks, by sending a CTS to a list of potential relays (those whose packets are waiting for transmission in the output buffer of the node), receiving the RTS with an indication of current signal strength, and picking the "best" node, according to a metric similar to that of proportional fair (based on the achieved throughput to each node up to this time).

The idea is straight-forward, but quite good actually (by which I mean: this should be a better-than-WCNC paper). It should be obvious that, as soon as several packets are awaiting transmission at any node, then the node has the choice to pick which one to transmit based on instantaneous conditions.

Performance gains shown, obviously. Little analysis, simulation only.

The Critical Transmitting Range for Connectivity in Sparce Wireless Ad Hoc Networks

This paper: The Critical Transmitting Range for Connectivity in Sparce Wireless Ad Hoc Networks P. Santi, D. Blough, IEEE Trans on Mobile Computing, Vol.2,No.1,Jan-Mar 2003, is excellent.

It computes the asymptotic relation between the range r, the length l and the number n of nodes uniformly (randomly) distributed in a square area of side length l with connectivity range r. It establish the value for r for which the graph is connected with high probability, or disconnected with high probability.

The main result is: in one dimension, rn > 2l log(l) ensures connectivity, rn < (1-epsilon) l log(l) ensures disconnectivity.

In higher dimension (2 and 3), connectivity is assured for r^d n > k l^d log(l), with k a constant which depends on the dimension. If r^d n < l^2, then the graph is disconnected.

There is a gap in dimension 2 and 3 wrt the asymptotes. Also, paper conjectures that in dim 1, rn < 2l log(l) should ensure disconnectedness.

Most of the proofs come from a pigeon-hole argument, which is relatively simple and elegant.