so one of the motivations that led me to think about all the Haggle stuff was the Milgram work. THis seemed to imply, as do pandemics, that a series of chance encounters could, over lots of iterations, provide end-to-end communications reliably.
10 years and 100 papers and algorithms later, it isn't looking so rosy - basically, pretty much every clever scheme has a delivery probability that is quite dismal, even if you set the lifetime of packets/bundles to be many days!
of course, we claim there are other reasons to build such a system (we always did - including reality mining style apps and serendipity)...
but the real problem is misunderstanding the result that Milgram got in his six-degrees work, which made use of the postal network - this isn't an opportunistic network - it is an unbelievably reliable aggregator and schedules delivery between pretty much anywhere on the planet mostly on a near daily basis. ANd the cunning people in the postal service historically provide us with a hint on how to apply this in opportunistic networking..
Indeed, if you go back to the distant past - read about Darwin's voyages on the Beagle (or, perhaps more fun, go see the movie Master and Commander) you'll see that any and all ships going around the world were tasked with the duty of delivering and picking up the post. Without deploying a specific scheduled post boat, instead, all boats going the right way were enlisted as the delivery channel.
Thus, instead of contacts between known friends/acquaintances being required in a successful chain, the weak ties are linked across distances by an early internet - but the early internet was, itself, spatially opportunistic (but "packets" were routed over it in aggregate sacks-worth to the right destination sets).
SO we need to build this (actually, back in Intel research cambridge days, I did propose putting a bluetooth device into the lining of all envelopes and postal bags as I guessed that people walking past the post room in each lab would "drop" and "pickup" their post via the bag, and that would achieve this miraculous shortcut that we've been looking for (without admitting defeat and going back to using the interweb:( )
So we need to data-mine people's use of google maps (i.e. equivalent of lifting their Satnav planned routes) and then use those people who've looked up a place (and maybe mentioned it in a tweet or other social media) to act as ferries (as per georgia tech term) Or mules, or, errr, unwitting post-people....to act as the glue to get us back to the reliable delivery (sure, it still will involve physical travel rather than light-speed photonic networking, but it might get similar delivery properties as the Big-I Internet)
Time to build a simulation and try it based on some trace data....
Building pony express trade routes to strengthen weak ties, and regain the six degrees of separation!!
The 11th ACM Conference on Embedded Networked Sensor Systems (SenSys 2013) just kicked off, held at the University of Rome 'La Sapienza' in Rome. From Cambridge, CeciliaÂ is chairing the session "Sensing People" and the SenSys 2013 Doctoral Colloquium.
Some facts about SenSys 2013:
- 250+ attendees
- 1/3 are students
- 40% have registered for both the conference and the workshops
- 21 papers got accepted out of 123 submissions (17%)
- most of them received 3 to 8 reviews
- 70 presentations in the poster and demo track - each one also got a 1-min madness talk during the main conference
There is an interesting opening talk by the chairsÂ showing some stats about the submission this year (as far as I can recall)
- register the paper earlier, and submit it late (close to the DL) - this holds for most of the accepted ones
- most of the accepted papers are from America, around 50%
- certain key words in the title will lead to rejection: nodes, networking, vehicle, etc. (I should have taken a photo while laughing at that slide.. :(
Since there is no electro-plug in the conference room. Most of notes are on the paper. Will find time to move them here.
Keynote byÂ Shahram Izadi from MSR Cambridge: "The New Face of the User Interface"
Introduce the work carried out at MSR Cambridge by the Human-Computer-Interaction (HCI) group, including the 3D interaction of physical and digital objects, 3D model reconstruction using smartphones (using the Queens' College and the Mathematics bridge in the demo). They highlight how to design using low price component and smartphones.
Session 1 -Â Communication Systems
Chaos: Versatile and Efficient All-to-All Data Sharing and In-Network Processing at Scale
Olaf Landsiedel (Chalmers University of Technology, Sweden), Federico Ferrari (ETH Zurich, Switzerland), Marco Zimmerling (ETH Zurich, Switzerland)
Q: Mainly evaluated by simulation, will it be a gap if the design is applied to real environment?
A: Not yet tested in real environment, hence we don't know.
Let the Tree Bloom: Scalable Opportunistic Routing with ORPL
Simon Duquennoy (SICS Swedish ICT AB, Sweden), Olaf Landsiedel (Chalmers University of Technology, Sweden), Thiemo Voigt (SICS Swedish ICT AB and Uppsala University, Sweden)
Practical Error Correction for Resource-Constrained Wireless Networks: Unlocking the Full Power of the CRC
Travis Mandel (University of Washington), Jens Mache (Lewis & Clark College)
Use CRC to correct wireless transmission errors, solving the reliable issue by their design TVA, Transmit-Verify-Ack.
Very good presentation, and presenter ends his talk with a song about CRC :)
Session 2 -Â Sensing People
iSleep: Unobtrusive Sleep Quality Monitoring using Smartphones
Tian Hao (Michigan State University), Guoliang Xing (Michigan State University), Gang Zhou (College of William and Mary)
Using sound monitoring to infer sleeping quality.
Lifestreams: a modular sense-making toolset for identifying important patterns from everyday life
Cheng-Kang Hsieh (UCLA CSD), Hongsuda Tangmunarunkit (UCLA CSD), Faisal Alquaddoomi (UCLA CSD), John Jenkins (Cornell Tech), Jinha Kang (UCLA CSD), Cameron Ketcham (Cornell Tech), Brent Longstaff (UCLA CSD), Joshua Selsky (Cornell Tech), Betta Dawson (UCLA CSD), Dallas Swendeman (UCLA David Geffen School of Medicine Department of Psychiatry and Biobehavioral Sciences), Deborah Estrin (Cornell Tech), Nithya Ramanathan (UCLA CSD)
Probably the longest author list in SenSys history.
14GB data collected for 44 young mothers.
Q: How do you recruit patients?
A: Done by the partners in hospital.
Q: Any new findings from the data?
A: We detect some hidden behaviors not noticed by the patients, e.g., unusual long walking outdoors, due to anxiety.
Diary: From GPS Signals to a Text-Searchable Diary
Dan Feldman (MIT), Andrew Sugaya (MIT), Cynthia Sung (MIT), Daniela Rus (MIT)
Various people from Cambridge are currently in Bern fÃ¼rÂ EuroSys 2012, and will be reporting live from the conference here, as well as summarizing the trends and highlights afterwards.
The second day has kicked off, and we will be providing the usual live update service below the fold -- click "continue reading" to get there!
3rd and final day... mainly about PHY/MAC layer and theory works
The day started with a Keynote by Farnan Jahanian (University of Michigan, NSF). Â Jahanian talked about some opportunities behind cloud computing research. In his opinion, cloud computing can enable new solutions in fields such as health-care and also environmental issues. As an example, it can help to enforce a greener and more sustainable world and to predict natural disasters (e.g. the recent japanese tsunami) with the suport of a wider sensor network. His talk concluded with a discussion about some of the challenges regarding computer science research in the US (which seem to be endemic in other countries). He highlighted that despite the fact that the market demands more computer science graduates, few students are joining related programs at every level, including high school.
Session 7. MAC/PHY Advances.
No Time to Countdown: Migrating Backoff to the Frequency Domain, Souvik Sen and Romit Roy Choudhury (Duke University, USA); and Srihari Nelakuditi (University of South Carolina, USA)
Conventional WiFi networks perform channel contention in time domain. Such approach imposes a high channel wastage due to time back-off. Back2F is a new way of enabling channel contention in the frequency domain by considering OFDM subcarriers as randomised integer numbers (e.g. instead of picking up a randomised backoff length, they choose a randomly chosen subcarrier). This technique requires incorporating an additional listening antenna to allow WiFi APs to learn about the backoff value chosen by nearby access points and decide if their value is the smallest among all others generated by close-proximity APs. This knowledge is used individually by each AP to schedule transmissions after every round of contention. Nevertheless, by incorporating a second round of contention, the APs colliding in the first one will be able to compete again in addition to a few more APs. The performance evaluation was done on a real environment. The results show that the collision probability decreases considerable with Back2F with two contention rounds. Real time traffic such as Skype experiences a throughput gain but Back2F is more sensitive to channel fluctuation.
Harnessing Frequency Diversity in Multicarrier Wireless Networks, Apurv Bhartia, Yi-Chao Chen, Swati Rallapalli, and Lili Qiu (University of Texas at Austin, USA)
Wireless multicarrier communication systems are based on spreading data over multiple subcarriers but SNR varies in each subcarrier. In this presentation, the authors propose a join integration of three solutions to reduce the side-effects:
- Map symbols to subcarriers according to their importance.
- Effectively recover partially corrupted FEC groups and facilitate FEC decoding.
- MAC-layer FEC to offer different degrees of protection to the symbols according to their error rates at the PHY layer
Their simulation and testbed results corroborate that a joint combination of all those techniques can increase the throughput in the order of 1.6x to 6.6x.
Beamforming on Mobile Devices: A first Study, Hang Yu, Lin Zhong, Ashutosh Sabharwal, David Kao (Rice University, USA)
Wireless links present two invariants:Â spectrum is scarce while hardware is cheap.Â The fundamental waste in cellular base stations is because of the antenna design. Lin Zhong proposed passive directional antennas to minimize this issue. They used directional antennas to generate a very narrow beam with a larger spatial coverage. They have proved that this solution is practical despite small form factor of smartphone's antenna, resistent to nodes rotation (only 2-3 dB lost if compared to a static node), and does not affect the battery life of the handsets, specially in the uplink as the antenna's beam is narrower. This technique allows calculating the optimal number of antennas for efficiency.Â The system was evaluated both indoors and outdoors in stationary/mobile scenarios. Â The results show that it is possible to save a lot of power in the client by bringing down the power consumption as the number of antennas increases with this technique.
SESSION 8. Physical Layer
FlexCast: Graceful Wireless Video Streaming, S T Aditya and Sachin Katti (Stanford University, USA)
This is aÂ schemeÂ to adapt video streaming to wireless communications. Mobile video traffic is growing exponentially and users' experience is very poor because of channel conditions. MPEG-4 estimates the quality over long timescales but channel conditions change rapidly thus it has an impact on the video quality. However, current video codecs are not equipped to handle such variations since they exhibit an all or nothing behavior.Â They propose that quality is proportional to instantaneous wireless quality, so a receiver can reconstruct a video encoded at a constant bit rate by taking into account information about the instantaneous network quality.
A Cross-Layer Design for Scalable Mobile Video, Szymon Jakubczak and Dina Katabi (Massachusetts Institute of Technology, USA)
One of the best papers in Mobicom'11. Mobile video is limited by the bandwidth available in cellular networks, and lack of robustness to changing channel conditions. As a result, video quality must be adapted to the channel conditions of different receivers. They propose a cross-layer design for video that addresses both limitations.Â In their opinion the problem is that the compression an error protection convert real-valued pixels to bits and as a consequence, they destroy the numerical properties of original pixels. In analog TV this was not a problem since there is a linear relationship between the transmitted values and the pixels so a small perturbation in the channel was also transformed on a small perturbation on the pixel value (however, this was not efficient as this did not compress data).
SoftCast is as efficient as digital TV whilst also compressing data linearly (note that current compression schemes are not linear so this is why the numerical properties are lost). SoftCast transforms the video in the frequency domain with a transform called 3D DCT. In the frequency domain, most temporal and spatial frequencies are zeros so the compression sends only the non-zero frequencies. As it is a linear transform, the output presents the same properties. They ended the presentation with a demo that demonstrated the real gains of SoftCast compared to MPEG-4 when the SNR of the channel drops.
Practical, Real-time Full Duplex Wireless, Mayank Jain, Jung II Choi, Tae Min Kim, Dinesh Bharadia, Kanna Srinivasan, Philip Levis andSachin Katti (Stanford University, USA); Prasun Sinha (Ohio State University, USA); and Siddharth Seth (Stanford University, USA)
This paper presents a full duplex radio design using signal inversion (based on a balanced/unbalanced (Balun) transformer)and adaptive cancellation. The state of the art in RF full-duplex solutions is based on techniques such as antenna cancellation and they present several limitations (e.g. manual tuning, channel-dependent). This new design supports wideband and high power systems without imposing any limitation on bandwidth or power. The authors also presentedÂ a full duplex medium access control (MAC) design and they evaluated the system using a testbed of 5 prototype full duplex nodes.Â The results look promising so... now it's the time to re-design the protocol stack!
Session 9. Theory
Understanding Stateful vs Stateless Communication Strategies for Ad hoc Networks, Victoria Manfredi and Mark Crovella (Boston University, USA); and Jim Kurose (University of Massachusetts Amherst, USA)
There are many communication strategies depending on the network properties. This paper explores adapting forwarding strategies that decides when/what state communication strategy should be used based on network unpredictability and network connectivity.Â Three network properties (connectivity, unpredictability, and resource contention) determine when state is useful.Â Data state is information about data packets, it is valuable when network is not well-connected whilst control-state is preferred when the network is well connected. Their analytic results (based on simulations on Haggle traces and DieselNet) show that routing is the right strategy for control state, DTN forwarding for data-state (e.g. Haggle Cambridge traces) and packet forwarding for those which are in the data and control state simultaneously (e.g. Haggle Infocom traces).
Optimal Gateway Selection in Multi-domain Wireless Networks: A Potential Game Perspective, Yang Song, H. Y. Wong, and Kang-Won Lee (IBM Research, USA)
This paper tries to leverage a coalition of networks with multiple domains with heterogeneous groups. They consider a coalition network where multiple groups are interconnected via wireless links. Gateway nodes are designated by each domain to achieve a network-wide interoperability. Â The challenge is minimising the intra-domain cost and the sum of backbone cost. They used a game-perspective approach to solve this problem to analyse the equilibrium inefficiency. They consider that this solution can be also used in other applications such as power control, channel allocation, spectrum sharing or even content distribution.
Fundamental Relationship between Node Density and Delay in Wireless Ad Hoc Networks with Unreliable Links, Shizhen Zhao, Luoyi Fu, and Xinbing Wang (Shanghai JiaoTong University, China); and Qian Zhang (Hong Kong University of Science and Technology, China)
Maths, percolation theory ... quite complex to put into words