04-05-2011, 12:11 PM
Abstract
Delay tolerant networks are characterized by thesporadic connectivity between their nodes and therefore the lackof stable end-to-end paths from source to destination. Since thefuture node connections are mostly unknown in these networks,opportunistic forwarding is used to deliver messages. However,making effective forwarding decisions using only the networkcharacteristics (i.e. average intermeeting time between nodes)extracted from contact history is a challenging problem. Basedon the observations about human mobility traces and the findingsof previous work, we introduce a new metric called conditionalintermeeting time, which computes the average intermeeting timebetween two nodes relative to a meeting with a third nodeusing only the local knowledge of the past contacts. We thenlook at the effects of the proposed metric on the shortest pathbased routing designed for delay tolerant networks. We proposeConditional Shortest Path Routing (CSPR) protocol that routesthe messages over conditional shortest paths in which the costof links between nodes is defined by conditional intermeetingtimes rather than the conventional intermeeting times. Throughtrace-driven simulations, we demonstrate that CSPR achieveshigher delivery rate and lower end-to-end delay compared to theshortest path based routing protocols that use the conventionalintermeeting time as the page link metric.
I. INTRODUCTION
Routing in delay tolerant networks (DTN) is a challengingproblem because at any given time instance, the probabilitythat there is an end-to-end path from a source to a destinationis low. Since the routing algorithms for conventional networksassume that the links between nodes are stable most of thetime and do not fail frequently, they do not generally workin DTN’s. Therefore, the routing problem is still an activeresearch area in DTN’s [1].Routing algorithms in DTN’s utilize a paradigm calledstore-carry-and-forward. When a node receives a messagefrom one of its contacts, it stores the message in its buffer andcarries the message until it encounters another node which isat least as useful (in terms of the delivery) as itself. Then themessage is forwarded to it. Based on this paradigm, several routing algorithms with different objectives (high delivery rateetc.) and different routing techniques (single-copy [2] [3],multi-copy [4] [5], erasure coding based [6] etc.) have beenproposed recently. However, some of these algorithms [7] usedunrealistic assumptions, such as the existence of oracles whichprovide future contact times of nodes. Yet, there are also manyalgorithms (such as [8]-[10]) based on realistic assumptionof using only the contact history of nodes to route messagesopportunistically.Recent studies on routing problem in DTN’s have focusedon the analysis of real mobility traces (human [11], vehicular[12] etc.). Different traces from various DTN environmentsare analyzed and the extracted characteristics of the mobileobjects are utilized on the design of routing algorithms forDTN’s. From the analysis of these traces performed in previouswork, we have made two key observations. First, ratherthan being memoryless, the pairwise intermeeting times betweenthe nodes usually follow a log-normal distribution [13][14]. Therefore, future contacts of nodes become dependenton the previous contacts. Second, the mobility of many realobjects are non-deterministic but cyclic [15]. Hence, in a cyclicMobiSpace [15], if two nodes were often in contact at aparticular time in previous cycles, then they will most likelybe in contact at around the same time in the next cycle.Additionally, previous studies ignored some informationreadily available at transfer decisions. When two nodes (e.g., Aand B) meet, the message forwarding decision is made accordingto a delivery metric (encounter frequency [9], time elapsedsince last encounter [16] [17], social similarity [18] [19] etc.)of these two nodes with the destination node (D) of themessage. However, all these metrics depend on the separatemeeting histories of nodes A and B with destination node D1.Nodes A and B do not consider their meetings with each otherwhile computing their delivery metrics with D.To address these issues, we redefine the intermeeting timeconcept between nodes and introduce a new page link metric calledconditional intermeeting time. It is the intermeeting timebetween two nodes given that one of the nodes has previouslymet a certain other node. For example, when A and B meet, A(B) defines its conditional intermeeting time with destinationD as the time it takes to meet with D right after meeting
Download full report.
http://ieeexplore.ieeeiel5/5513765/55348...er=5534960