PeopleNet: engineering a wireless virtual social network

ABSTRACT

People often seek information by asking other people even when they have access to vast reservoirs of information such as the Internet and libraries. This is because people are great sources of unique information, especially that which is location-specific, community-specific and time-specific. Social networking is effective because this type of information is often not easily available anywhere else. In this paper, we conceive a wireless virtual social network which mimics the way people seek information via social networking. PeopleNet is a simple, scalable and low-cost architecture for efficient information search in a distributed manner. It uses the infrastructure to propagate queries of a given type to users in specific geographic locations, called bazaars. Within each bazaar, the query is further propagated between neighboring nodes via peer-to-peer connectivity until it finds a matching query. The PeopleNet architecture can overlay easily on existing cellular infrastructure and entails minimal software installation. We identify three metrics for system performance: (i) probability of a match, (ii) time to find a match and (iii) number of matches found by a query. We describe two simple models, called the swap and spread models, for query propagation within a bazaar. We qualitatively argue that the swap model is better with respect to the performance metrics identified and demonstrate this via simulations. Next, we compute analytically the probability of match for the swap model. We show that the probability of match can be significantly improved if, prior to swapping queries, the nodes exchange some limited information about their buffer contents. We propose a simple greedy algorithm which uses this limited information to decide which queries to swap. We show via simulation that this algorithm achieves significantly better performance. Overall our results demonstrate that PeopleNet, with its bazaar concept and peer-to-peer query propagation, can provide a simple and efficient mechanism for seeking information.

REFERENCES

• 1: http://www.bluez.org/
• 2: Manjeet Kripalani, "Mobile Telecoms Find Nirvana", Business Week, October 4, 2004.
• 3: http://repast.sourceforge.net/
• 4: http://jist.ece.cornell.edu/
• 5: Wojciech Szpankowski , Vernon Rego, Yet another application of a binomial recurrence. Order statistics, Computing, v.43 n.4, p.401-410, 1990 [doi>10.1007/BF02241658]
• 6: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 7: A. El Gamal, J. Mammen, B. Prabhakar and D. Shah, "Throughput-Delay Trade-off in Wireless Networks", In Proc. IEEE Infocom 2004.
• 8: M.J. Neely and E. Modiano, "Capacity and Delay Tradeoffs for Ad-Hoc Mobile Networks", IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917--1937, June 2005.
• 9: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 10: V. Srinivasan, P. Nuggehalli, C-F. Chiasserini, R. R. Rao, "Cooperation in Wireless Ad Hoc Networks", In Proc. IEEE Infocom 2003.
• 11: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002
• 12: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 13: http://www.napster.com/
• 14: David Barkai, Peer-to-Peer Computing: Technologies for Sharing and Collaborating on the Net, Intel Press, 2001
• 15: http://reality.media.mit.edu/serendipity.php
• 16: http://www.bedd.com/
• 17: http://www.mobiluck.com/
• 18: http://www.jambo.net/
• 19: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 20: Tara Small , Zygmunt J. Haas, The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way), Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778443]
• 21: http://www.dtnrg.org/
• 22: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 23: Jing Su , Alvin Chin , Anna Popivanova , Ashvin Goel , Eyal de Lara, User Mobility for Opportunistic Ad-Hoc Networking, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'04), p.41-50, December 02-03, 2004 [doi>10.1109/MCSA.2004.29]
• 24: S. Shakkottai , "Asymptocis of Query Strategies over a Sensor Network", In Proc. IEEE Infocom 2004.
• 25: http://www.newscientist.com/article.ns?id=dn5111
• 26: http://www.bluetooth.com/products/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
social networking, wireless networks