Message Cab (MCab): Partition Restoration in MANETs Using Flexible Helping Hosts

Ting Wang, Chor Ping Low

.

DOI: 10.4236/wsn.2010.212107                

Abstract

Helping hosts are intensively used in various schemes to restore partitioned Mobile Ad Hoc Networks (MANETs).Most of the existing schemes offers only deterministic deployment and fixed routes for the helping hosts, and are thus not able to deal with fluctuating network traffic, which is a practical condition in many MANET applications. In this paper, we argue that flexible helping hosts (referred to as Message Cabs (MCabs)), with deployment and routes that response to the changes in the traffic demand of the network, may overcome this drawback and reduce the message delay in the networks. To demonstrate the effectiveness of this observation, we propose a new helping host scheme namely the Message Cab (MCab) scheme for partition restoration in MANETs, and validate the performance through simulations.

Keywords

Mobile Ad Hoc Networks (MANETs), Helping Host, Message Cab, Adaptive Route Design, Dynamic Deployment

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” United States, 1999.
[2]	W. Zhao and M. Ammar, “Message Ferrying: Proactive Routing in Highly-Partitioned Wireless Ad Hoc Net-works,” Proceedings of the 9th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS’03), Washington, DC, USA, 2003, pp. 308-314.
[3]	W. Zhao, M. Ammar and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad hoc Networks,” Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’04), New York, NY, USA, 2004, pp. 187-198.
[4]	W. Zhao, M. Ammar and E. Zegura, “Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network,” Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05), Miami, FL, USA, Vol. 2, 2005, pp. 1407-1418.
[5]	M. M. B. Tariq, M. Ammar and E. Zegura, “Message Ferry Route Design for Sparse Ad Hoc Networks with Mobile Nodes,” Proceedings of the 7th ACM international symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’06). New York, NY, USA: ACM, 2006, pp. 37-48.
[6]	M. Ye, X. Tang and D. L. Lee, “Fair Delay Tolerant Mobile Data Ferrying,” Proceedings of the 10th International Conference on Mobile Data Management: Systems, Services and Middle-ware (MDM’09). Washington, DC, USA: IEEE Computer Society, 2009, pp. 182-191.
[7]	M. H. Ammar, D. Chakrabarty, A. D. Sarma, S. Kalyanasundaram and R. J. Lipton, “Algorithms for Message Ferrying on Mobile Ad Hoc Networks,” Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’09), 2009, IIT Kanpur, India, pp. 13-24.
[8]	Q. Li and D. Rus, “Communication in Disconnected Ad Hoc Networks Using Message Relay,” Journal of Parallel and Distributed Computing, Vol. 63, No. 1, pp. 75-86, 2003.
[9]	S.-H. Chung, K.-F. Ssu, C.-H. Chou, and H. C. Jiau, “Improving Data Transmission with Helping Nodes for Geographical Ad Hoc Routing,” Computer Networks, Vol. 51, pp. 4997-5010, 2007.
[10]	C.-H. Ou, K.-F. Ssu and H. C. Jiau, “Connecting Network Partitions with Location-Assisted Forwarding Nodes in Mobile Ad Hoc Environments,” Proceedings of the 10th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC’04), Washington, DC, USA, 2004, pp. 239-247.
[11]	D. Borsetti, C. Casetti, C.-F. Chiasserini, M. Fiore and J. M. Barcel’o-Ordinas, “Virtual Data Mules for Data Collection in Road-Side Sensor Networks,” Proceedings of the 2nd International Workshop on Mobile Opportunistic Networking (MobiOpp’10). New York, NY, USA: ACM, 2010, pp. 32-40.
[12]	R. C. Shah, S. Roy, S. Jain and W. Brunett, “Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks,” Technical Report IRS-TR-03-001, Intel Research Lab at Seattle , 2003.
[13]	D. Jea, A. Somasundara and M. Srivastava, “Multiple Controlled Mobile Elements (Data Mules) for Data Collection in Sensor Networks,” Lecture Notes in Computer Science, Vol. 3560, No. 2005, pp. 244-257, 2005.
[14]	A. A. Hasson, R. Fletcher and A. Pentland, “DakNet: A Road to Universal Broadband Connectivity,” First Mile Solutions, Technical Report, 2003.
[15]	I. Rhee, M. Shin, S. Hong, K. Lee and S. Chong, “On the Levy-walk Nature of Human Mobility: Do Humans Walk like Monkeys?” Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ’08), Rio de Janeiro, Brazil, 2008.
[16]	Y. Zhang, C. P. Low, J. M. Ng and T. Wang, “An Efficient Group Partition Prediction Scheme for MANETs,” Proceedings of the 2009 IEEE Wireless Communications and Networking Conference (WCNC’09), Budapest, Hungary, 2009, pp. 1-6.
[17]	R. Sitters, “The Minimum Latency Problem is NP-Hard for Weighted Trees,” Integer Programming and Combinatorial Optimization, ser. Lecture Notes in Computer Science, W. Cook and A. Schulz, Eds. Springer Berlin/ Heidelberg, Vol. 2337, 2006, pp. 230-239.
[18]	A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan and M. Sudan, “The Minimum Latency Problem,” Proceedings of the 26th annual ACM symposium on Theory of computing (STOC’94), New York, NY, USA: ACM, 1994, pp. 163-171.
[19]	S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, “Proof Verification and the Hardness of Approximation Problems,” Journal of the ACM, Vol. 45, No. 3, 1998, pp. 501-555.
[20]	K. R. Baker, “Introduction to Sequencing and Scheduling,” John Wiley & Sons, Inc, New York, USA, 1974.
[21]	W. E. Smith, “Various Optimizers for Single-Stage Production,” Naval Research Logistics Quarterly, Vol. 3, 1956, No. 1-2, pp. 59-66.
[22]	P. Merz and B. Freisleben, “Genetic Local Search for the TSP: New Results,” Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, USA, April 1997, pp.159-164.