PAN

ABSTRACT

Reliable storage of data with concurrent read/write accesses (or query/update) is an ever recurring issue in distributed settings. In mobile ad hoc networks, the problem becomes even more challenging due to highly dynamic and unpredictable topology changes. It is precisely this unpredictability that makes probabilistic protocols very appealing for such environments. Inspired by the principles of probabilistic quorum systems, we present a Probabilistic quorum system for ad hoc networks Pan), a collection of protocols for the reliable storage of data in mobile ad hoc networks. Our system behaves in a predictable way due to the gossip-based diffusion mechanism applied for quorum accesses, and the protocol overhead is reduced by adopting an asymmetric quorum construction. We present an analysis of our Pan system, in terms of both reliability and overhead, which can be used to fine tune protocol parameters to obtain the desired tradeoff between efficiency and fault tolerance. We confirm the predictability and tunability of Pan through simulations with ns-2.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Guangyu Pei , Mario Gerla, Mobility management for hierarchical wireless networks, Mobile Networks and Applications, v.6 n.4, p.331-337, Aug. 2001 [doi>10.1023/A:1011474527449]
	2	Zygmunt J. Haas , Ben Liang, Ad Hoc mobility management with uniform quorum systems, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.228-240, April 1999 [doi>10.1109/90.769770]
	3	Z.J. Haas and B. Liang, "Ad hoc mobility management with randomized database groups," in Proc. of ICC'99, 1999, vol. 3, pp. 1756--1762.
	4	L. Zhou and Z.J. Haas, "Securing ad hoc networks," IEEE Network, vol. 13, no. 6, pp. 24--30, 1999.
	5	Providing Robust and Ubiquitous Security Support for Mobile Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.251, November 11-14, 2001
	6	Jean-Pierre Hubaux , Levente Buttyán , Srdan Capkun, The quest for security in mobile ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501437]
	7	C.E. Perkins, J.T. Malinen, R. Wakikawa, E.M. Royer, and Y. Sun, IP address autoconfiguration for ad hoc networks, July 2002, Internet-Draft, draft-ietf-manet-autoconf-01.txt. Work in progress.
	8	Nitin H. Vaidya, Weak duplicate address detection in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513826]
	9	S. Nesargi and R. Prakash, "MANETconf: configuration of hosts in a mobile ad hoc network," in Proc. of INFOCOM'02, 2002, pp. 1059--1068.
	10	Fred B. Schneider, Replication management using the state-machine approach, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
	11	Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
	12	Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
	13	D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
	14	Dahlia Malkhi , Michael K. Reiter , Avishai Wool , Rebecca N. Wright, Probabilistic quorum systems, Information and Computation, v.170 n.2, p.184-206, November 1, 2001 [doi>10.1006/inco.2001.3054]
	15	Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
	16	S.J. Lee, M. Gerla, and C.C. Chiang, "On-demand multicast routing protocol," in Proc. of WCNC'99, 1999, vol. 3, pp. 1298--1302.
	17	J.J. Garcia-Luna-Aceves and E.L. Madruga, "The core-assisted mesh protocol," IEEE Journal on Selected Areas in Communications (Special Issue on Ad-hoc Routing), vol. 17, no. 8, pp. 1380--1394, 1999.
	18	J.-P. Hubaux, T. Gross, J.-Y. Le Boudec, and M. Vetterli, "Toward self-organized mobile ad hoc networks: the terminodes project," IEEE Communications Magazine, vol. 39, no. 1, pp. 118--124, 2001.
	19	D.B. Johnson, D.A. Maltz, and Y-C. Hu, The dynamic source routing protocol for mobile ad hoc networks (DSR), February 2003, Internet-Draft, draft-ietf-manet-dsr-08.txt. Work in progress.
	20	K. Xu, X. Hong, and M. Gerla, "An ad hoc network with mobile backbones," in Proc. of ICC'02, 2002, vol. 5, pp. 3138--3143.
	21	P. Krishna, N.H. Vaidya, M. Chatterjee, and D.K. Pradhan, "A cluster-based approach for routing in dynamic networks," in Proc. of ACM/SIGCOMM Computer Communication Review, 1997, pp. 372--387.
	22	C.R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE Journal on Selected Areas in Communications, vol. 15, no. 7, pp. 1265--1275, 1997.
	23	R. Sivakumar, P. Sinha, and V. Bharghavan, "CEDAR: a core-extraction distributed ad hoc routing algorithm," IEEE Journal on Selected Areas in Communications (Special Issue on Ad-hoc Routing), vol. 17, no. 8, pp. 1454--1465, 1999.
	24	Ada Wai-Chee Fu , David Wai-Lok Cheung, A Transaction Replication Scheme for a Replicated Database with Node Autonomy, Proceedings of the 20th International Conference on Very Large Data Bases, p.214-225, September 12-15, 1994
	25	L.-G. Alberto and I. Widjaja, Communications Networks, McGraw Hill Higher Education, 2000.
	26	Z.J. Haas, J.Y. Halpern, and L. Li, "Gossip-based ad hoc routing," in Proc. of INFOCOM'02, 2002, pp. 1707--1716.
	27	J. Luo, P.Th. Eugster, and J.-P. Hubaux, "Route driven gossip: Probabilistic reliable multicast in ad hoc networks," in Proc. of INFOCOM'03, 2003.
	28	K. Chen and K. Nahrstedt, "Effective location-guided tree construction algorithms for small group multicast in MANET," in Proc. of INFOCOM'02, 2002, pp. 1192--1201.
	29	J.D. Murray, Mathematical Biology, Springer, Berlin, 2nd edition, 1993.
	30	K. Fall and K. Varadhan, Eds., The ns Manual, The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, Apr. 2002, Availiable from http://www.isi.edu/nsnam/ns/.
	31	Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
	32	D.B. Johnson and D.A. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, Tomasz Imielinski and Hank korth, Eds., chapter 5, pp. 153--181. Kluwer Academic Publishers, 1996.
	33	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]
	34	Srdjan Capkun , Jean-Pierre Hubaux , Levente Buttyán, Mobility helps security in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778422]
	35	T. Hara, "Effective replica allocation in ad hoc networks for improving data accessibility," in Proc. of INFOCOM'01, 2001, pp. 1568--1576.
	36	K.H. Wang and B. Li, "Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks," in Proc. of INFOCOM'02, 2002, pp. 1089--1098.
	37	Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]