Luận án tiến sĩ: Phương pháp swarm intelligence cho mạng ad hoc di động

SWARM INTELLIGENCE METHODS FOR MOBILE AD HOC NETWORKS by Sundaram Rajagopalan A dissertation submitted to the Faculty of the University of Delaware in partial fulfillment of the requirements for the degree of Doctor of Philosophy with a major in Computer Science Fall 2006 c 2006 Sundaram Rajagopalan All Rights Reserved UMI Number: 3247715 UMI Microform 3247715 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 SWARM INTELLIGENCE METHODS FOR MOBILE AD HOC NETWORKS by Sundaram Rajagopalan Approved: David Saunders, Ph. Chair of the Department of Computer and Information Sciences Approved: Thomas M. Dean of the College of Arts and Sciences Approved: Daniel Rich, Ph. Provost I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy.

Signed: Chien-Chung Shen, Ph. Professor in charge of dissertation I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Member of dissertation committee I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Adarshpal Sethi, Ph.

Member of dissertation committee I certify that I have read this dissertation and that in my opinion it meets the academic and professional standard required by the University as a dissertation for the degree of Doctor of Philosophy. Signed: Charles Boncelet, Ph. Member of dissertation committee For Momma, from your Mahesh payyan; for Poppa, from your Sivagnanam: I submit this humble offering at your lotus feet. iv ACKNOWLEDGEMENTS I am fortunate to have had a stellar dissertation committee.

They raised the pertinent questions and exposed me to the right amount of dissent necessary for my growth as a researcher. My committee members have helped me hone my scientific temperament, and see the right issues in the problems in my research area. I wish to thank my advisor, Prof. Chien-Chung Shen, for the many Sundays and Saturdays he has labored over my ideas, and arguments and explained to me that research is all about ”what are the issues?” I am particularly thankful to him for encouraging me to work on several problems simultaneously.

In doing so, my advisor has coaxed out potential I never knew I possessed. Thank you, Prof. My committee members at CIS, Prof. Amer, and Prof.

Sethi have taken a special interest in my progress, and they have offered the guidance and encouragement necessary to any fledgling researcher. I am particularly thankful to Prof. Sethi for raising the issue of statistical relevance of observed data early in my academic career. I am also grateful to Prof.

Amer for his meticulous approach to dissertation writing. I find his perspicacity, and commitment to precision amazing and inspiring. Indeed, perspiration without precision is of little value, and I thank Prof. Amer for drastically improving the quality of my dissertation.

Boncelet’s concerns regarding the nature of assumptions made in the MANET research community ring pertinent bells; I see his forebodings on the matter especially appropriate to the current direction of the MANET research community. v I am not sure where to begin and end thanking my family. Momma and Poppa have always been there, patiently offering the necessary spiritual guidance and support. They have always taken pride in my undertakings.

Any thing I have accomplished is such an insignificant matter when compared to what they have done for me. I hope they will accept this document as a humble dakshinai for their untiring support emotionally, financially, and physically. Aunty and Uncle have helped me out of so many hard times here at Delaware. I am profoundly and deeply indebted to them.

Everything would have been many orders of magnitude harder if not for them. Many a time Aunty would just guess (correctly) that I will need her counsel. Uncle has been always calm-minded and rationale-inspiring, as though his accomplishments aren’t enough inspiration for any scientist. Thank you, Aunty, Uncle.

My sister and brother have always set the bar high not just for me, but for the entire family. My sister’s capacity for mirth despite her many stresses is inspiring and contagious. She is radiant in her compassion and so immediate and accessible in her concern for me. All I needed to do was to just call her! My brother is both my shining idol and a wonderful mentor since my grade school days.

He is also a great friend, and my rational compass. I recall the many evenings with him years ago, when we would talk about temperament and rigor, concerning our discussions on issues of philosophical and metaphysical import. Should I be a ”close second” to anyone, I am happy and willing to accept the post under him. I wish my grandmother, Paati, were here; she had looked forward to all of us kids getting a ”double degree.” I miss her very much even now, after nearly 15 years since her passing.

My graduation would have brought her so much joy. Thanks are also due to Shalini, for the longest and most interesting conversations of my vi life; and to Prasanna, for introducing me to the world of serious art and changing my life in fundamental ways. My stay here in Delaware has been enjoyable, mostly due to the company I’ve kept over the years. Michael has been both a wonderful friend and a source of endless encourage- ment.

He has given me a lot of extremely useful advice, professional and personal, and is always ready, willing, and able to help me. Thank you, Michael. My dear friend Elisabeth has been a shoulder of many sorts, and she has always been there for me. Thank you so much, Elisabeth, you are awesome.

Janardhan has been a source of great encouragement, and the sink for a great deal of venting. I would like to specifically thank him for his insight in more practical issues towards the end of my academic career here. I’ve spent many an evening with Rob/Laura and Jeff; they are always upto some mischief. It has been a pleasure hanging out with them.

My roommate, Daniel, is easily the best roommate I have ever had, and has been a constant source of support. My colleagues at the DEGAS networking group have been a delight to work with. Chaiporn, Chavalit and Zhuochuan have been a lot of help. Ilknur, Justin, Naveen and Xiang have been great labmates.

I wish them all great success. This work was sponsored with both TA funding from CIS, here at UD, and with research grants from NSF. The folks here at CIS have granted me TA funding every time I asked for aid. I thank them for their confidence in my teaching abilities.

I doubt if I could have done very much without their help. So long, and thanks for all the fish! vii TABLE OF CONTENTS LIST OF FIGURES. xi LIST OF TABLES. xv Chapter 1 INTRODUCTION .1 Mobile ad hoc networks: problems and applications .2 Swarm intelligence mechanisms .3 Motivation and problem statement .4 Relevance of observed data and repeatability .5 Organization of dissertation and research contributions.

7 2 BACKGROUND AND RELATED WORK .1 Unicast routing for hybrid ad hoc networks .2 TCP for MANET .3 Gossip and multicast packet delivery improvement for MANET .4 P2P/content distribution methods for MANET. 17 3 ANSI: A HYBRID UNICAST ROUTING PROTOCOL FOR HYBRID AD HOC NETWORKS .1 ANSI unicast routing protocol .1 Simulation and network model. 54 4 USING TCP TO EVALUATE ROUTING PROTOCOLS .1 TCP and the routing protocol .1 How are MANET routing protocols affected under TCP loads? .2 Some metrics for studying TCP loads over MANET routing protocols .2 Studying TCP for some routing protocols .1 Network and protocol models. 82 5 PIDIS: A PACKET DELIVERY IMPROVEMENT SERVICE FOR MULTICAST ROUTING PROTOCOLS .1 PIDIS: A packet delivery improvement service .1 Overview of ODMRP .2 Overview of PIDIS .3 Local data structures .4 Selecting a gossip next-hop (λ) .6 Maintaining the gossip table .7 Adaptive mechanisms in PIDIS .8 Justification for the reinforcement models .1 Implementing Anonymous Gossip .2 Network and protocol characteristics .3 Experiments and performance metrics.

113 6 BTM: A CROSS-LAYER DECENTRALIZED BITTORRENT .1 Overview of the BitTorrent P2P system .2 BTI: A straightforward implementation of BitTorrent over MANET .3 BTM: A cross-layer decentralized BitTorrent for MANET .1 BTM protocol operations .1 Evaluating BTI and BTM .2 Network and protocol characteristics .3 Experiments and performance metrics. 152 7 CONCLUSIONS AND FUTURE WORK .1 Summary of contributions .1 BTM and mobility .2 BTM for mesh networks: an adaptive tracker mechanism .3 A BitTorrent solution to reliable server pooling. 167 x LIST OF FIGURES 1.1 A mobile ad hoc network. Node 3 communicates with node 5 via nodes 4, and 6.

Node 11 communicates with node 1 via mesh router 2, and mesh router 1.3 A vehicular ad hoc network. Vehicle 2 communicates with vehicle 1 via vehicle 3 and with a gateway via vehicles 3 and 7.4 The organization of the dissertation showing the publications for each topic.1 Local reinforcement in ANSI.2 The propagation of the forward reactive ant (shown in solid arrows) and the return of the backward reactive ant (dashed arrows). The rebroadcast from node 2, when received at node 1 is killed immediately to prevent route loops. At each node X the forward reactive ant enters, the ant reinforces the path from X to all the other nodes in the nodes visited stack.

Thus, the forward reactive ant from S when received at node 4 reinforces the link 4 − 2 to both node 2 and node S. On the return path, all nodes in path of the backward reactive ant reinforce the trails to the paths to all the nodes in the path leading from the node upstream all the way to the destination. Thus, when the backward reactive ant is received at S via path 1 − 3. D, S will reinforce link S − 1 for destinations 1, 3, .3 In a hybrid network (nodes 1–9 are part of a highly capable network in this case, and are connected by the grid shown), nodes belonging to more capable infrastructure are able to perform stochastic routing.

In this figure, two possible paths that S can take to route to D are one via nodes 1 → 4 → 7 → 8 → 9 (P 1) and another via nodes 1 → 2 → 5 → 6 → 9 (P 2).4 Two routing choices for S → D. One route is via next hop node 1 and another route is via next hop node 2. The path via 2 is longer than the path via 1.5 Hybrid network topologies used for Experiments 1, 2 and 3.6 Experiment 1: Performance studies of ANSI vs. AODV in a hybrid network with UDP flows.7 Experiment 2: Performance studies of ANSI vs.

AODV in a hybrid network with TCP flows.8 Experiment 3: Performance studies of ANSI vs. AODV in a (larger) hybrid network with UDP flows.9 Experiment 4: Performance studies of ANSI vs. AODV in a pure MANET with TCP flows.10 Experiment 5: Performance studies of ANSI vs. AODV in a pure MANET network with UDP flows and a varying number of nodes.1 AODV performance supporting TCP loads and UDP loads.

AODV: congestion window growth for one TCP sender for the outgoing (headed towards the data sink) stream in a hybrid network containing both fixed infrastructure (with multiple interfaces, 802.11b and Ethernet) and MANET nodes.3 Experiment 1: Performance of ANSI and AODV with increasing APDU sending rate.