1Efficient Routing in Intermittently Connected MobileNetworks: The Multiple-copy CaseThrasyvoulos Spyropoulos, Student Member, IEEE, Konstantinos Psounis, Member, IEEE,and Cauligi Raghavendra, Fellow, IEEEAbstract—Intermittently connected mobile networks arewireless networks where most of the time there does not exista complete path from the source to the destination. There aremany real networks that follow this model, for example, wildlifetracking sensor networks, military networks, vehicular ad hocnetworks, etc. In this context, conventional routing schemes fail,because they try to establish complete end-to-end paths, beforeany data is sent.To deal with such networks researchers have suggestedto use flooding-based routing schemes. While flooding-basedschemes have a high probability of delivery, they waste a lot ofenergy and suffer from severe contention which can significantlydegrade their performance. Furthermore, proposed efforts toreduce the overhead of flooding-based schemes have often beenplagued by large delays. With this in mind, we introduce a newfamily of routing schemes that “spray” a few message copies intothe network, and then route each copy independently towardsthe destination. We show that, if carefully designed, sprayrouting not only performs significantly fewer transmissions permessage, but also has lower average delivery delays than existingschemes; furthermore, it is highly scalable and retains goodperformance under a large range of scenarios.Finally, we use our theoretical framework proposed in [1]to analyze the performance of spray routing. We also use thistheory to show how to choose the number of copies to be sprayedand how to optimally distribute these copies to relays.Index Terms—routing, ad-hoc networks, intermittent connec-tivity, delay tolerant networks.I. INTRODUCTIONWireless data networks often aim at extending Internetservices into the wireless domain. Services like GPRS enableInternet access through the widespread cellular infrastructure,while the deployment of WiFi 802.11 access points providesdirect Internet connectivity for wireless users (mainly laptopsand PDAs) that are within range. Additionally, self-organized(“ad hoc” or “peer-to-peer”) wireless networks have beenproposed for applications where setting up a supporting,wired infrastructure might be too costly (e.g. sensor networks)or simply not an option (e.g. disaster relief, deep spacenetworks).Despite these ongoing efforts, wireless access currentlyseems to give rise to inconvenience and frustration more oftenthan providing the envisioned flexibility to the user. Cellularaccess is low bandwidth and expensive, while WiFi access istypically only available at a few “hotspots” that the user has tolocate and move to, without real “mobile computing”. Further,ad hoc networks have yet to find much application outsidethe research or military community, while some dire issuesregarding their scalability properties have been identified [2].The reason for these failures is that many of the as-sumptions made in the wired world, and which are largelyresponsible for the success of the Internet, do not hold inthe wireless environment. The concept of a connected, stablenetwork over which data can be routed reliably rarely holdsthere. Wireless signals are subject to multi-path propagation,fading, and interference making wireless links unstable andlossy. Additionally, frequent node mobility (e.g. as in vehic-ular ad hoc networks—VANETs [3]) significantly reducesthe time a “good” link exists, and constantly changes thenetwork connectivity graph. As a result, wireless connectivityis volatile and usually intermittent, as nodes move in and outof range from access points or from each other, and as signalquality fluctuates.In addition to the cases of wireless Internet access andad hoc networks, the need to depart from the traditionalnetworking practices has been recognized for a number ofemerging wireless applications. Sensor networks can sig-nificantly increase their lifetime by powering down nodesoften, or by using very low power radios. This implies thatmany links will be down frequently, and complete end-to-end paths often won’t exist [4]. Tactical networks may alsochoose to operate in an intermittent fashion for LPI/LPDreasons (low probability of interception and low probabilityof detection) [5]. Finally, deep space networks [6] and under-water networks [7] often have to deal with long propagationdelays and/or intermittent connectivity, as well. These newnetworks are often referred to collectively as Delay TolerantNetworks (DTN [8]). What they all share in common is thatthey can neither make any assumptions about the existenceof a contemporaneous path to the destination nor assumeaccurate knowledge of the destination’s location or evenaddress, beforehand.Under such intermittent connectivity many traditional pro-tocols fail (e.g. TCP, DNS, etc. [8, 9]). It is for this reason thatnovel networking architectures are being pursued that couldprovide mobile nodes with better service under such inter-mittent characteristics [9, 10]. Arguably though, the biggestchallenge to enable networking in intermittently connectedenvironments is that of routing. Conventional Internet routing2protocols (e.g. RIP and OSPF), as well as routing schemesfor mobile ad-hoc networks such as DSR, AODV, etc. [11],assume that a complete path exists between a source and adestination, and try to discover these paths before any usefuldata is sent. Thus, if no end-to-end paths exist most of thetime, these protocols fail to deliver any data to all but the fewconnected nodes.However, this does not mean that packets can never bedelivered in these networks. Over time, different links comeup and down due to node mobility. If the sequence of connec-tivity graphs over a time interval are overlapped, then an end-to-end path might exist. This implies that a message could besent over an existing link, get buffered at the next hop until thenext link in the path comes up (e.g. a new node moves in rangeor an existing one wakes-up), and so on and so forth, untilit reaches its destination. This model of routing constitutesa significant departure from existing routing practices. It isusually referred to as “mobility-assisted” routing, becausenode mobility often needs to be exploited to deliver a messageto its destination (other names include “encounter-based for-warding” or “store-carry-and-forward”). Routing