Wireless Netw DOI 10.1007/s11276-013-0589-6
Threshold based locking routing strategy for delay tolerant network Qaisar Ayub • M. Soperi Mohd Zahid Sulma Rashid • A. Hanan Abdullah
•
Springer Science+Business Media New York 2013
Abstract Delay tolerance network probabilistic routing protocols forward message to a node by observing its predictability value to meet the message destination. However, it is vital to predict the ability of node to carry the transmitted message. For instance, the traffic confluence on the high probable nodes can produce congestion that results in the drop of previously stored messages. These drops diminish the delivery ratio because the dropped message lost its opportunity to be delivered. Since, there exist multiple copies of each message; therefore, the same node invariably receives the dropped messages from other parts of the network and causes the highest number of transmissions. Additionally, the replication from source node continues on the high probable peers even the previous copies were transmitted on the better predictable neighbors than the current. In this paper, we have proposed a novel routing method called as the adaptive threshold based locking method that maintains the contemporary status of the node based on its activity in the network. We have used the adaptive status measuring metrics such as transmit factor, drop factor and hop away count. Moreover, a threshold based locking method has been introduced to
Q. Ayub M. S. M. Zahid S. Rashid (&) A. H. Abdullah Department of Computer System and Communication, Faculty of Computing, Universiti Teknologi Malaysia (UTM), 81310 Skudai, Johor, Malaysia e-mail:
[email protected] Q. Ayub e-mail:
[email protected] M. S. M. Zahid e-mail:
[email protected] A. H. Abdullah e-mail:
[email protected]
control the diffusion of messages. We have performed the comparison of existing and proposed routing methods with real time mobility traces. The proposed strategy has bolstered the delivery ratio and minimizes hop count, end-toend delay and number of transmission. Keywords Store–carry–forward Buffer management policies Delay tolerant networking Routing
1 Introduction The ad hoc routing [1] protocols formulate the end-to-end connectivity together with source and destination prior to the transmission of data. These communication models are inappropriate for environments that may experience frequent disconnections, network partitions and rapid topology change. The example of such applications includes deep space communication, wild life monitoring and military networks. Delay tolerance network (DTN) [2] has been proposed as a solution to build the network infrastructure via intermittently connected mobile nodes by adopting store, carry and forward paradigm. Accordingly, the node stores the incoming messages in its buffer, carries it while moving and forward or deliver when comes within the transmission range of other nodes. In DTN, the mobile nodes act as routers, equip with finite buffer space, energy and processing power. When these nodes are not in the transmission range of each other then the communication is said to be disrupted or delayed. The node tackles this delay by storing the incoming message in its local buffer and transmits when the contact opportunity arises. Such hop-by-hop transmissions entails to deliver the message to its destination.
123
Wireless Netw
DTN routing protocols [3, 4, 29, 30] can be either single copy or multi copy. In single copy protocols, [5] the node forwards the unique copy of the message along a single path. These protocols consume fewer network resources but suffer unbounded delivery delay. The multi copy routing protocols [6–10] forwards redundant copies of each message along multiple paths resulting reduced delivery delay and increase the delivery ratio. Despite improving network throughput, the multi copy protocols galvanizes the eminent amount of network resources including buffer space, energy, bandwidth and processing power. The resource consumption [11] can be curbed by forwarding the message only to the nodes that are highly favorable to encounter its destination, for instance, PRoPHET [12] and Encounter based routing [13]. However, in real time scenarios each node has its own mobility region [14], speed, energy and buffer space. For example, a city tram or bus travels on the pre-defined scheduled route thus holds high predictability for imminent encountering locations, including stations, plazas and junctions as a result become the more eligible carrier to take message destining to these places. In comparison, other nodes such as cabs, pedestrians are not bound to follow identical route thereby hold fewer encounter and predictability values to meet with the same destination. Hence, least credible nodes (cabs, pedestrians) continue to replicate a message on high probable node that elevates the traffic density. The probability computation based on the encounter rate [13] can lead to the selection of inaccurate relay. For example, a high speed moving node can hold high predictability values even it is a multi hop away. The increase in intermediate nodes decreases the chance that the node is a good carrier as on the way interlinked nodes will forward messages for which high speed node holds high predictability. Hence, finite buffer space triggers the drop of previously stored messages that decrease network throughput. The reason is that, node was carrying dropped messages due to its higher predictability value to meet their destinations. On the other hand, a node moving with lower speed can show less predictability value but may be less hops far from message destination. Hereby, we need a method to compute the number of hops a node is aside from message destination. The node under dynamic surroundings [2] such as unpredictable contacts, traffic patterns cannot sustain a consistent performance in terms of delivering or relaying the received messages. Despite having high predictability value a good-quality node can drop its stored messages due to rapid congestion caused by the sudden increase in the network traffic or if it is unable to transmit its received messages. Hence, a more dynamic network context aware algorithm [15] is required to access accurate capability and performance of the current connected nodes in terms of its
123
message transmission and drop rate. An adaptive de-centralized probability computation method is required to get the current behavior of the nodes. The contribution of this paper is as follows: • •
• •
We have proposed an adaptive threshold based locking routing method for delay tolerant network. We have proposed novel routing metrics such as transmit factor, drop factor and hop away count that adaptively compute the quality value of nodes. We have proposed a threshold based locking method to control the message replications. We have used real time mobility traces such as sassy and helvisick city to evaluate the performance of existing and proposed routing methodologies.
The rest of the paper has been organized as follows: Sect. 2 review the existing routing protocols, Sect. 3 is about proposed routing method, Sect. 4 is about performance metrics, Sect. 5 depicts simulation and results while the conclusion in section 6.
2 DTN routing protocols The DTN routing protocols can be grouped into (1) single copy or forwarding based and (2) multi copy or replication based. The single copy protocols forward the unique copy of the message along a single path. For example, direct delivery protocol carries the source messages and delivers only when comes within the transmission range of the destination node. The direct delivery suffers unbounded delay. The randomized forwarding proposed where despite carrying the node forward message to a neighbor that has been a high predictability value to meet destination. The utility based forwarding transmits the message to a node that holds high utility value to meet message destination. The utility value is computed based on the time nodes last saw each other. Jathar et al. [16] proposed a forwarding method by studying the movement patterns of contacts and their time sequence. Musolesi et al. [17] propose the context aware forwarding strategy where when source and destination are in the same group then the message is delivered without storing in intermediate nodes. However, when there are partitions then the message is forwarded by evaluating the utility value of the intermediate node. Several works [15]–[17] has employed addition parameter to choose an accurate neighboring node for message destination. The multi copy routing protocols forward redundant copies of each message along dissimilar paths. For instance, in Epidemic routing protocol, each encounter entails the pairwise exchange of its buffered messages. Hence, the messages have more than one path to reach the
Wireless Netw
destination. However, the Epidemic protocol [10] requires infinite resources, for instance. Energy, buffer space, and bandwidth, therefore, are not practical for real time scenarios. The prioritized Epidemic [18] reduces consumption of bandwidth and buffer space by defining the message transmission and message drop priorities. The N-Epidemic protocol [19] decreases the energy requirement, where the node forwards the message only if it is surrounded by N number of neighbors. Some recent work [20–22] has optimized the epidemic based forwarding to minimize the resource consumption. The resource requirement of a protocol can be minimized by controlling the transmission of message copies. For this, quota based multi copy routing protocols proposed that restrict the message copies to a predefined limit. For instance, in spray&wait protocol, the node transmits N number of message copies across its neighbors called as spray phase. If destination is not found in spray phase, then each node can forward the message directly to the destination. In spray and focus [7] the source node assigns an L number of forwarding coupons to a message. After encountering, it forward the message with n/2 forwarding coupon while keep n/2 for itself. When the node left one copy then it shifts to focus phase that forward the message to the encountering node by observing its suitability to meet message destination. The QoN spray and wait [23] measure the mobility of node and is represented by an integer number which indicates how frequent one node encounters with another node in a given time interval. The message is forwarded to a node if it has high-quality value to meet message destination. The probabilistic routing protocols forward the message copy only if the current connected node holds the high probable to meet its destination. For instance, in [12] author proposed the PRoPHET routing protocol where the node forwards the message to the current neighbor only if it is highly predictable to meet the message destination. In [24] where Erramilli et al. propose a new message forwarding technique called as delegated forwarding. Accordingly, each node maintains a quality value Q(a,c) such as the quality value of ’a’ to meet destination ’c’, and level value L(m,c) such as the current level of the message ’m’ to reach destination ’c’. Initially, Message’s level value is initialized with the predefined quality threshold. On encountering, the sender forward the message only if the receiving node holds the high-quality value than the level value of the message i.e. Q(b,c) [ L(m,c). After the transmission, the sender increase message level value with the quality value of the receiving node. In [31] Diver employs the backpressure based routing strategy where the message forwarding decision was
attributed to link variation, queue hot-spots, and node mobility. Under high traffic loads the backpressure algorithm utilizes the network resources. However, when the traffic load is low then this technique sufferers long delays. Majed Alresaini et al. [32] propose an Backpressure with Adaptive Redundancy (BWAR) that reduces the delay by employing the spraying methodology with backpressure technique.
3 System model We assumed that transmission happens through the opportunistic contacts. By opportunist contact, we mean that the nodes does not have prior information about future availability of communicating links. A contact is said to happen when nodes move in the transmission range of each other. Each node will be heterogeneous in terms of speed, energy and buffer space. The nodes behavior is hybrid meaning that they can generate their own traffic and can receive the transmissions. The transmission radio is less than the network size. Therefore, source and destination cannot communicate directly and end-to-end path is impossible. There is no infrastructure or central administration among the nodes. The buffer has been then taken as a finite resource, and a node can drop its previously stored messages on the requirement.
4 The proposed threshold based locking (TbL) routing method for delay tolerant network 4.1 The data structure used in the TbL Despite probability, a sophisticated method is required to observe the node quality in terms of its capability to carry the transmitted message. For this, we have proposed the following data structures (Table 1) to obtain the current activity of a network node. 1. 2. 3. 4. 5. 6.
Hop Away Vector (HaV) Recent Encounter Vector (REV) Message Transmit vector (MTV) Message Receive Vector (MRV) Message Drop Vector (MDV) Message Header (MH)
4.1.1 Hop away vector (HaV) The hop away vector (HaV) keep the track about the number of hops a node has moved away from the other nodes known by it. The HaV consist of node id (Nid) and
123
Wireless Netw Table 1 Summary of data structures Data structure
Equation
Comment
Hop away vector (HaV)
HaC = HaCprevious ? 1
It keeps information about hops a node has moved away from other peers
Recent encounter vector (REV)
DTði;jÞ = [Current time - REV(i,j)previous]
REV is used to maintain the information since nodes last saw each other
Message transmit vector (MTV)
TCnew (i,j) = TMT (i,j) - TC(i,j)previous
REV is used to maintain the information since nodes last saw each other
Message receive vector (MRV)
RCnew(i,j) = TMR (i,j) - RC(i,j)previous
MRV manage the information about the message received by the node
Message drop vector (MDV)
DCnew(i,j) = TMD(i,j) - DC(i,j)previous
MDV is used to keep the count of zmessages dropped by a node
Hop Away Count (HaC). For initial encounter, the node id is initialized to the current connected peer and its HaC is set to one. Later, the HaC is incremented by one for each subsequent encounters. The HaC is reset to zero for the successive encounters of the same nodes. Figure 1 shows a sample scenario where pedestrian P has encountered train T at time T1 and initializes its HaC to one. When P encounter the bus B at time T2, it increments HaC of train T and initialize HaC of B to one. Finally, the pedestrian p encounters with car C at time T3 and initialize the HaC of car c to one and increments the HaC of train T and bus B. Note
DTði;jÞ ¼ ½CurrentTime REVði; jÞprevious
•
The MTV is used transmitted by the interval of recent consists of node id
•
With an increase in HaC, the quality value of a node should be reduced because with the rise in the HaC, the node need to queue up message for long durations and may drop before it reaches the destination. The decline in quality value will minimize the number of transmissions, message drop, transmission overhead and increase the delivery ratio.
ð1Þ
For the first-time Encounter, the source node inserts the node id of relay j and the current time as encounter Time (ET). Figure 2 depicts the initial encounter of i, j at time T1 where i has inserted j as Nid and set its encounter time (ET) to current time (30 s) in the Recent Encounter Vector (REV). Later, the subsequent encounter of i, j at T2, the difference of current time (40 s) and REV(i,j) (30 s) is used to re-set the time. 4.1.3 Message transmit vector (MTV) to maintain the number of messages encountering node over encountering encounter vector (REV). The MTV (Nid) and Transmission count (TC).
TCnew ði; jÞ ¼ TMTði; jÞ TCði; jÞprevious
ð2Þ
The Recent encounter vector (REV) maintains the information about the most-recent encountering time of nodes. The REV consists of node id (Ni) and Encounter Time (ET)and is maintained by using Eq. 1.
The Eq. 2 shows the computation of Transmission count (TC) on the encounter of node i and j. Hence, TMT (i,j) is the total number of transmitted messages, TCprevious(i, j) is the previous message transmission count at node i, j respectively. Figure 3 presents the computation of MTV between i and j. For the initial encounter the node i has set the TMT (20) as the TC. In subsequent encounter, i will calculate the message transmitted by j during the time interval by subtracting the TMT with TCprevious.
Fig. 1 Snapshot of hop away vector
Fig. 2 Snapshot of recent encounter vector
4.1.2 Recent encounter vector (REV)
123
Wireless Netw
DCnew ði; jÞ ¼ TMDði; jÞ DCði; jÞprevious
ð4Þ
Equation 4 shows the computation of drop count (DC) where, TMD(i,j) is the total number of dropped messages and DC(i,j)previous is the count old message drop at node i, j respectively. Note • Fig. 3 Snapshot of message transmit vector
4.1.4 Message receives vector (MRV) Message receives a vector (MRV) keeps the track of receiving messages since the node last saw each other. MRV consists of node id and receives count. RCnew ði; jÞ ¼ TMRði; jÞ RCði; jÞprevious
ð3Þ
Equation 3 is used to update the RC. Hence, TMR(i,j) is total received messages, RC(i,j)previous is the previous count of receiving messages from node i, j respectively. Figure 4 depicts the calculation of MRV for node i, j respectively. In initial encounter, node i will set the TMR to the receive count (RC) of j at time T-1. Afterwards, node i will update the RC by subtracting the TMR with TCprevious by using Eq. 3. Note •
MTV and MRV are used to compute the transmit factor (TF) that determines the ability current connected node to transmit the received messages. The quality of a node is increased with the magnitude of transmit factor (TF).
Message Drop Vector (MDV) is used to compute the drop factor. The objective is to reduce the quality of node having a high drop ratio over its received messages. The quality of a message should be reduced in magnitude by drop factor.
Figure 5 shows the manuplation of MDV of node i, j respectively. For initial encounter at time T-1, node i has initialized TMD (20) to DC. The TMD is subtract from DC previous to get the DC since nodes last saw each other. 4.1.6 Modified message header We have modified DTN message header by introducing the data fields of (1) Previous Forwarding (PF), (2) Transmit lock (TL) and (3) Drop Lock (DL). The previous forwarding (PF) is used to store the Qv of most-recent transmission and is initialized with zero for messages generated by source. Transmit Lock (TL) and Drop Lock (DL) are used to control the replication and drop of messages. By default, the DL is initialized with DROP—ALL, and TL is initialized with TRANS—ALL. Table 2 describes the values and meanings of used named constants. 4.2 Quality of node module (QoN-M)
Message drop vector (MDV) updates the information about the messages that have been dropped by current node over the encountering interval. MDV consists of node id and drop count.
A network node can change its behavior dynamically; for instance, a good-quality node could begin to perform indigent even its quality value is high. The node begins to perform wretched if it is unable to transmit its received messages. The long-term storage and incoming traffic cause congestion that a node overcomes by dropping its previously stored messages. While on the other hands, with
Fig. 4 Snapshot of message receive vector
Fig. 5 Snapshot of message drop vector
4.1.5 Message drop vector (MDV)
123
Wireless Netw
and MRV and compute the ratio of the message transferred over message received in the encountering interval ET. TFði; jÞ ¼ ½TCði; jÞ RCði; jÞDET RCði; jÞ TCði; jÞ
Fig. 6 The replication of messages
ð5Þ
Equation 5 depicts the computation of transmit factor for node i, j. Hereby, TC(i,j) is the transmission count obtained from MTV of Eq. 2 and RC(i,j) is receive count obtained from MRV of Eq. 3. The receive RC will be greater than the TC. Drop Factor metric use MRV and MDV to calculate the ratio of the message received over message dropped. DFði; jÞ ¼ ½DCði; jÞ RCði; jÞDET jjRCði; jÞ DCði; jÞ ð6Þ Equation 6 shows the calculation of Drop Factor for node i, j. The RC(i,j) is the receive count obtained from message receive vector (MRV) of Eq. 3 and DC(i,j) is the drop count obtained from message drop vector (MDV) of Eq. 4. QVði; jÞ ¼ ½QVold ði; jÞ þ TFði; jÞ ½DFði; jÞ þ logðHaCÞ ð7Þ The quality value of a node is then computed by using Eq. 7. Hence, QV(i,j) old is the previous quality value of nodes. The transmit factor is used to increase the quality while the sum of drop factor and HaC is used to decrease the quality value. 4.3 Message transmission module (MTM-M)
Fig. 7 The locking method of proposed TbL
Table 2 Named constants Name DL TL
Value
Description
DROP-ALL
Drop is allowed
DROP-NO
Drop not allowed
TRANS-ALL
Transmission allowed
TRANS-DEST
Transmission allowed to destination
higher transmission rate, message spends less time in the queue that results reduce drop, message transmissions and raise the delivery ratio. Hence, it is vital to undertake the node activity in terms of its ability to carry the message. For this, Quality vector is used that consist of node id (Nid) and Quality value (Qv). When nodes encounter first time, their Quality Value (Qv) is initialized with default Alpha. For subsequent encounters, the quality value is either incremented or decremented based on the Transmit Factor (TF), Drop Factor (DF) and Hop Away Count (HaC). Transmit factor metric use MTV
123
The high Qv indicates that node is fewer hops away from message destination, and its transmission ratio is higher than the drop ratio. The message transmission event is said to happen only if the sender can forward the message to the high-quality receiver. Such transmission boost the delivery because high quality nodes tends to frequently encounter the message destination. However, the node could continue message diffusion on high quality neighbors. When a node forwards a message, a copy of it remains in the transmitter or source. Hence, the source continues to spread the message while the receiver also becomes a source for other neighbors, and its diffusion continues on high Quality nodes even the quality difference is very small. Consider a snapshot in Fig. 6 where a source node a has replicated message on b (0.20) and c (0.25) at time T1 and T2 respectively. Afterwards, the carrier b (0.20) diffuse the message on d (0.21) and e (0.22) even the quality difference is very small. While c (0.25) forward the message to f (0.26) and g (0.26) even the quality of f and g is equal. This method suffers the following drawbacks: •
When the Quality value of relay is very small then forwarding the message to such node is a vain of
Wireless Netw
•
network resources because the source and receiver have the equal probability to meet destination. The node continues to forward the message on higher Qv than its own and can forward the message on equal Qv nodes. Algorithm
•
•
If the Qv of receiver to meet destination of message M is less than the pre-defined quality threshold (Qth) than source node is allowed to replicate the message on the multiple of the previous quality value. If the Qv of a receiver to meet destination of message M is greater than the pre-defined quality threshold (Qth) than the source node is not allowed further replicate the message while the relay node is not allowed to drop the message until delivered to the destination.
When a sender forwards the message it maps the Qv of the receiver on the pre-defined threshold queue (Qth). The threshold queue is divided into incremental unit limit (IUL) and non incremental unit limit (NIUL) as depicted by Fig. 7. If receiver Quality Value (Qv) falls into the IUL then transmitter updates message header PF data field by using Eq. 8. PFðMessageonSenderÞ ¼ QvðReceiverÞ 2
ð8Þ
Afterwards, the sender and receivers acquire the lock variable DL to DROP-ALL and TL to TRANS-ALL. It means the nodes are allowed to drop the message and can forward the message to other nodes holding the Qv higher than the PF of message header. When the Qv is above threshold limit,then the receiver acquires TL to TRANSDEST and DL to DROP-NO.Similarly, source node will set the Drop Lock (DL)to DROP-ALL and transmit lock to TRANS-DEST. It means that the sender and receiver are allowed to forward the message directly to the destination.
5 Simulation and results In this section we will provide the comparison of existing and proposed routing strategies under ONE simulator [25, 26]. ONE is an event driven simulator that provides the environment for store carry and forward applications. The schemes were evaluated by using real time mobility traces of Helsinki (Finland) city based environment and sassy [27]. 5.1 Performance metrics 5.1.1 Delivery ratio The Delivery ratio is the proportion of the message delivered over the message transmitted. The high magnitude of
the delivery parameter shows the optimal use of network resources. The objective of routing protocol is to increase the delivery ratio. 5.1.2 Number of transmissions The number of transmissions is the enumeration of messages forwarded by the nodes. When a node consent the message transmission, it consumes the energy, buffer space and bandwidth of the network. The objective of routing protocol is to reduce the amount of message transmissions. 5.1.3 Message drop It is the count of message dropped over message transmitted. The message drop triggers due to finite buffer space. When a message is dropped it affects the router throughput. Because the dropped message wastes the effort of all nodes that it had consumed during its mobility. The objective of the protocol is to control the message drop. 5.1.4 Overhead The overhead is the computation and processing power that a node has consumed to forward the messages. The objective of protocols is to reduce the overhead magnitude. 5.2 Trace: the real time trace SASSY In this section, we have analyzed the performance of existing and proposed routing strategies under real time mobility trace sassy [27] of 79 days. The sassy mobility trace is specifically developed to analyze the efficiency of routing protocols under opportunistic connectivity. The network consists of 25 mobile devices carried by pedestrians at St Andrews with the transmission range of 10m. The accuracy is measured in terms of varying the buffer size and message creation interval. We have compared the TbL with PRoPHET, MaxProp [28], Epidemic and spray and wait routing protocols in terms of minimizing the number of transmissions, message drop, overhead and increasing delivery ratio. 5.2.1 Scenario: by varying the buffer size of nodes Figure 8 present the results of existing and proposed routing strategies by increasing the storage capacity of nodes in the context of transmissions. We can see that all routing protocols has been reducing the message dimensions at the higher buffer sizes. The reason is that at the higher storage capacity, for instance, [8M, 9M] the message drop reduces. This prevents the re-transmission of the same dropped messages from the other parts of network.
123
Wireless Netw
The MaxProp protocol has shown high transmission rate because it gives higher transmission priority to the new packets. Since, Epidemic protocol performs well in small networks and has proven it by infecting limited nodes. The probabilistic protocol controls the transmissions by forwarding the message to high probable peers’ however, still forward more messages then the spray&wait. The propose TbL has sustained a consistent performance throughout all simulation instances. Figure 9 depicts the results of existing and proposed routing method in context of message drop. We can observe the high drop ratio in MaxProp. The reason is that the MaxProp protocol drops the messages with the high number of hop count. Hence, the node tends to carry on the source messages and drop the relay. The Epidemic protocol holds the second position; this is reasonable due to its inherited property of performing well in small-sized networks. For all simulation configurations, the proposed routing method has controlled the message drop. This is because of drop lock for messages that were transmitted to high probable nodes. Figure 10 maps the results of overhead by increasing the buffer capacity of nodes. We can see the reduced overhead with the increase in the storage ability. The reason is that at higher storage space, the nodes carries more messages inside the buffer that mitigates the re-transmissions of the dropped messages. The proposed TbL has not been affected and has maintained a constant overhead ratio throughout all simulation instances. Figure 11 shows the results of the delivery ratio for existing and proposed routing protocols by varying the buffer capacity. It can be observed that the MaxProp protocol has delivered fewer messages. The reason is that MaxProp drops the messages with high hop count. Hence, the dropped message could not be able to be delivered. The PRoPHET protocol performs better than MaxProp and Epidemic protocol. The proposed routing method TbL has delivered the high number of messages to their destinations.
The reason is due to the prevention of message drop with Drop Lock.
Fig. 8 Transmissions versus buffer size
Fig. 11 Message delivery versus buffer size
123
5.2.2 Scenario: by varying the message creation interval Figure 12 portraits the results of message transmissions by increasing the message creation interval. We can observe that at the small creation interval such as [25s, 35s], [35s,
Fig. 9 Drop versus buffer size
Fig. 10 Overhead versus buffer size
Wireless Netw
45s] all routing protocols has shown high transmissions. This is due to the rapid creation of messages. However, as the time gap increase, for instance, [45s, 55s],[55s, 65s],[65s, 75s] the transmissions reduce continually. The proposed TbL has controlled the transmission on all simulation instances. We can see the impact of high transmission in the Fig. 13. At high transmissions, large numbers of messages were dropped. This is due to the rapid increase in the traffic load. However, we can observe the reduction in the drop magnitude with an increase in the message creation interval. This is because fewer numbers of messages were created at the high intervals. The proposed TbL controls the message drop. Since, the high ratio of message drop causes the re-transmissions. This is because the same node receives the dropped messages from the other parts of the network. Figure 14 shows the increase overhead for protocols with highest transmissions. For instance, maxprop and Epidemic protocols has high overhead because both protocols has dropped and transmitted high volume of messages. The proposed TbL has mitigated the overhead ratio at a constant level. Figure 15 presents the message delivery for existing and proposed routing protocols. The MaxProp has limited delivery due to its high ratio of message drop (Fig. 9). The Epidemic protocol delivers more messages then MaxProp [28]. The PRoPHET [12] protocol has performed better than Epidemic [10]. The proposed TbL routing method has performed well in all simulation configurations.
been randomly generated between 500K and 1MB. We have performed the simulations by varying the traffic density. 5.3.1 Scenario: by varying number of nodes For each experiment, the traffic load was increased with 20 pedestrians and 10 cars. We have compared the performance
Fig. 13 Message drop versus message creation interval
5.3 Trace: the Helsinki city based environment In this section, we have configured the Helsinki city environment [25] that consists of cabs (10), cars (10), pedestrians (40) and trains (6). The trains, cabs and cars are moving via map route movement (MRM) [25] while pedestrians are walking by the shortest path map based movement model (SPMBM) [25]. The message size has
Fig. 14 Message overhead versus message creation interval
Fig. 12 Message transmission versus message creation interval
Fig. 15 Message delivery versus message creation interval
123
Wireless Netw
of proposed TbL with PRoPHET, Epidemic and MaxProp [28] routing protocols in terms of reducing overhead, number of transmissions, message drop and rising the delivery ratio. Figure 16 revails that the increase in traffic load, for instance, [128, 156 and 186] has mitigated the delivery ratio. This is justified because at higher traffic loads the node cannot accomodiate the incoming traffic and trigger the drop event on the previously stored messages. The drop reduces the delivery because dropped message lost its opportunity to be delivered. For example, the Epidemic protocol has reduced delivery due to elevated message drop at higher traffic loads. The PRoPHET routing protocol performs better and delivers more messages than the Epidemic. This is because PRoPHET protocol forwards the message to highly probable node. The MaxProp protocol performs better than Epidemic and PRoPHET routing protocols. The proposed TbL, the drop lock curbed message drop, as a result, high probable nodes carry the message and delivers them directly to the destination. Figure 17 shows the elevated transmission for all routing protocols and this magnitude gets higher at [126,156,186]. The probabilistic protocol has controlled the transmissions better than MaxProp. The proposed TbL has reduced the message diffusion for all simulation instances. The reason is that the TbL uses the threshold method to lock the transmissions and intends the high probable node to deliver the message with out replicating its copies. Figure 18 shows that the increase in traffic load for example [126, 156, 186] has entailed to drop the high volume of messages. Such intimated message drop stabs the delivery ratio (Fig. 16). Despite, of curbing transmissions, still the PRoPHET protocol has dropped a high number of messages then MaxProp. The proposed TbL outperforms the existing routing protocols and dropped the least number of messages. Figure 19 shows the overhead measure of existing and proposed TbL by raising the traffic density. The Epidemic protocol has higher overhead because of an uncontrolled exchange of messages. The PRoPHET protocol constitutes elevated transmission overhead compared to MaxProp. The highest delivery rate
Fig. 17 Message transmission versus nr of nodes
Fig. 18 Message drop versus nr of nodes
Fig. 19 Overhead versus nr of nodes
of Maxprop and proposed TbL mitigates the transmission overhead.
6 Conclusion
Fig. 16 Message delivery versus nr of nodes
123
The ad-hoc networks are composed of unpredictable contact and traffic patterns. Hence, despite high probability, a contemporary method is required to access the ability of a node to deliver or relay the received messages. For instance, a good-quality node can drop its stored messages due to rapid congestion caused by the sudden increase in the network traffic. This affects the network throughput because the dropped messages lost their opportunity to be delivered. In order to handle communication with such environments, we have presented a routing method called
Wireless Netw
as Threshold based Lock (TbL) that forward the message by observing the current activity of a network node in terms of carrying the messages. For this three metric such as (1) transmit factor (2) drop factor and (3) hop away count (HaC) were used. Moreover, we propose a locking method consisting of Drop Lock (DL) and Transmit Lock (TL). The transmit lock was used to block the diffusion of messages and drop lock (DL) was used to stop the message drop until it is delivered to destination by a node with higher quality than the pre-defined threshold. We performed the comparison of existing and proposed routing methods by using the real time mobility traces. The proposed TbL raises the delivery and reduces message transmission, drop and overhead.
References 1. Chakeres, I. D., & Belding-Royer, E. M. (2004). AODV routing protocol implementation design. In Proceedings of the 24th international conference on, distributed computing systems workshops, 2004 (pp. 698–703), IEEE. 2. Fall, K. (2003). A delay-tolerant network architecture for challenged internets. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, (pp. 27–34), ACM. 3. Jain, S. F., & Patra, R. K. (2004). Routing in a delay tolerant network. In (Vol. 34, Vol. 4), ACM. 4. Shen, J., Moh, S., & Chung, I. (2008). Routing protocols in delay tolerant networks: A comparative survey. In Proceeding of 23rd international technical conference on circuits/systems, computer and communications (ITC-CSCC 2008), (pp. 1577–1580). 5. Spyropoulos, T., Psounis, K., & Raghavendra, C. S. (2004). Single-copy routing in intermittently connected mobile networks. In Proceeding of IEEE conference sensor and ad hoc communications and networks (SECON), (pp. 235–244), IEEE. 6. Spyropoulos, T., Psounis, K., & Raghavendra, C. S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In proceeding of mobile computer and communication review 2005 (Vol. 7, pp. 252–259), ACM. 7. Spyropoulos, T., Psounis, K., & Raghavendra, C. S. (2007). Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility. In PerCom Workshops’ 07. Fifth annual IEEE international conference on, pervasive computing and communications workshops, 2007. (pp. 79–85), IEEE. 8. Spyropoulos, T., Turletti, T., & Obraczka, K. (2009). Routing in delay-tolerant networks comprising heterogeneous node populations. IEEE Transactions on Mobile Computing, 8(8), 1132–1147. 9. Srinivasa, S., & Krishnamurthy, S. (2009). CREST: An opportunistic forwarding protocol based on conditional residual time. In SEC ON, (pp. 1–9), IEEE. 10. Vahdat, A., & Becker, D. (2000). Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University. 11. Balasubramanian, A., Levine, B., & Venkataramani, A. (2007). DTN routing as a resource allocation problem. ACM SIGCOMM Computer Communication Review, 37(4), 373–384. 12. Lindgren, A., Doria, A., & Schele´n, O. (2003). Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mobile Computing and Communications Review, 7(3), 19–20.
13. Nelson, S. C., Bakht, M., & Kravets, R. (2009). Encounter-based routing in DTNs. In INFOCOM 2009, (pp. 846–854), IEEE. 14. Leguay, J., Friedman, T., & Conan, V. (2005). DTN routing in a mobility pattern space. In Proceedings of the 2005 ACM SIGCOMM workshop on delay-tolerant networking, (pp. 276–283), ACM. 15. Elwhishi, A., Ho, P.-H., Naik, S., & Shihada, B. (2011). Contention aware routing for intermittently connected mobile networks. In AFIN 2011, the third international conference on advances in future internet, (pp. 8–15). 16. Jathar, R., & Gupta, A. (2010). Probabilistic routing using contact sequencing in delay tolerant networks. In 2010 second international conference on, communication systems and networks (COMSNETS), (pp. 1–10), IEEE. 17. Musolesi, M., & Mascolo, C. (2006). A community based mobility model for ad hoc network research. In Proceedings of the 2nd international workshop on multi-hop ad hoc networks: From theory to reality, (pp. 31–38), ACM. 18. Ramanathan, R., Hansen, R., Basu, P., Rosales-Hain, R., & Krishnan, R. (2007). Prioritized epidemic routing for opportunistic networks. In Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, (pp. 62–66), ACM. 19. Lu, X., & Hui, P. (2010). An energy-efficient n-epidemic routing protocol for delay tolerant networks. In 2010 IEEE fifth international conference on, networking, architecture and storage (NAS), (pp. 341–347), IEEE. 20. Qaisar, A., & RMSMZ, S. (2011). TMHF: Transmit Max Hop First forwarding strategy to optimize the performance of epidemic routing protocol. International Journal of Computer Applications, 18(5), 40–45. 21. Ayub, Q., Rashid, S., & Zahid, M. S. M. (2010). Optimization of epidemic router by new forwarding queue mode TSMF. International Journal of Computer Applications, 7(11), 5–8. 22. Ayub, Q., Rashid, S., & Zahid, M. S. M. (2011). MinHop (MH) transmission strategy to optimized performance of epidemic routing protocol. Global Journal of Computer Science and Technology, 11(9), 35–41. 23. Wang, G., Wang, B., & Gao, Y. (2010). Dynamic spray and wait routing algorithm with quality of node in delay tolerant network. In 2010 international conference on, communications and mobile computing (CMC), (Vol. 3, pp. 452–456), IEEE. 24. Erramilli, V., Crovella, M., Chaintreau, A., & Diot, C. (2008). Delegation forwarding. In Proceedings of the 9th ACM international symposium on mobile ad hoc networking and computing, (pp. 251–260), ACM. 25. Kernen, A., & Ott, J. (2007). Increasing reality for dtn protocol simulations. Helsinki University of Technology, Technical Report, July. 26. Kernen, A., Ott, J., & Krkkinen, T. (2009). The ONE simulator for DTN protocol evaluation. In Proceedings of the 2nd international conference on simulation tools and techniques, (pp. 55), ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). 27. Bigwood, G., Rehunathan, D., Bateman, M., Henderson, T., & Bhatti, S. (2011). CRAWDAD data set st andrews/sassy (v. 2011-06-03). 28. Burgess, J., Gallagher, B., Jensen, D., & Levine, B. N. (2006). Maxprop: Routing for vehicle-based disruption-tolerant networks. In Proceedings of IEEE infocom, 2006, Barcelona, Spain, Vol. 6, pp. 1–11. 29. Spyropoulos, T., Rais, R. N., Turletti, T., Obraczka, K., & Vasilakos, A. (2010). Routing for disruption tolerant networks: taxonomy and design. Wireless networks, 16(8), 2349–2370. 30. Zeng, Y., et al. (2013). Directional routing and scheduling for green vehicular delay tolerant networks. Wireless Networks, 19(2), 161–173.
123
Wireless Netw 31. Dvir, A., et al. (2010). Backpressure-based routing protocol for DTNs SIGCOMM, pp. 405–406. 32. Alresaini, M., et al. (2012) . Backpressure with adaptive redundancy (BWAR). INFOCOM, 2300–2308.
Author Biographies Qaisar Ayub He has obtained his M.C.S. Computer Science degree in 2005 from Comsat Institute of Information Technology Pakistan. And BCS (Hons.) computer science from Allama Iqbal Open University Pakistan in 2003. He has 7 years of experience in conducting professional trainings (Oracle, Java,) and software development. As a part of this paper he is working on Routing and forwarding research issues in Delay tolerant Networks. M. Soperi Mohd Zahid He received Ph.D. degree in Computer Science from University of Wisconsin, Milwaukee in 2009, M.S. degree in Computer Integrated Manufacturing from Rochester Institute of Technology, New York and B.S. degree in 1988 from New Mexico State University, Las Cruces in Computer Science and Mathematics. He is currently a faculty member in Computer Science, Universiti Teknologi Malaysia. His research interests include Internet Routing Protocols and Delay/Disruption Tolerant Networks.
123
Sulma Rashid She has received her M.S. Degree in computer science in 2007 from IQRA University Islamabad Pakistan and M.C.S. degree in 2001 from UAAR Pakistan. She has 10 years of teaching experience. As a part of this paper she is working on Optimizing buffer scheduling research issues in DTN routing protocols
Abdul Hanan Abdullah is a Professor at Universiti Teknologi Malaysia (UTM). He obtained his Ph.D. degree from Aston University in Birmingham, United Kingdom in 1995. He was the dean at the Faculty of Computing, UTM from 2004 to 2011. Currently he is heading Pervasive Computing Research Group, a research group under K-Economy Research Alliances. His research interests include wireless sensor networks, Internet of Things, network security and next generation networks.