Abstract: In delay tolerant mobile networks, there are always no end-to-end paths due to sparse nodes and their irregular movement, so the forwarding of messages from source nodes to the destinations is a crucial task, which results in low probability of successful messages delivery and buffer occupancy for a long time. Routing in these networks is affected by some metrics, but the number of new connections especially is the crucial factor in delivering messages. Under this detection, we proposed every connection routing, which pay more attention to new connections between nodes but not the older ones. Further together with countdown timer and a fast buffer-released mechanism, every connection routing, are influenced by nodes’ speed, communication range and number, expiration time and simulation area. Buffer-release-enhanced weighted every connection routing may only increase processing time by the introducing of messages releasing time, but the benefit is lighter loaded buffers and higher efficiency of networks. The performance of buffer-release-enhanced weighted every connection routing is able to guarantees the validity of message delivery and improve the efficiency of the networks.
INTRODUCTION
Challenges of networking in sparse nodes mobile networks include but are not limited to network partitioning, intermittent connectivity, large delay and high deployment cost. In particularly, there are always no end-to-end (E2E) paths from sources to destinations. Delay Tolerant/distributed Mobile Networks (DTMN) have the potential to connect devices and areas of the world that are under-served by traditional networks, which enable communication by taking advantage of temporary connections to relay data in fashion similar to the postal network, instead of requiring an E2E path (Jones et al., 2007).
Nodes’ mobility plays an important role in DTMN because it is one of the most important factors in network-partition and link-intermittence. Mobility of network nodes presses protocol applications by disrupting routes, changing propagation environments and partitioning network (Khelil et al., 2005). In DTMN, node mobility metrics feature large time-scale mobility, which is quite different from mobile Ad Hoc networks (MANET) in a small time-scale. Node mobility enables message passing in partially connected DTMN where standard strategy of MANET message delivering fails (in which wireless nodes cooperate to relay messages over multiple relay hops from source to destination) (Frew et al., 2006).
Many routing algorithms for MANET such as dynamic source routing (Jones et al., 2007; Khelil et al., 2005) and destination sequence distance vector routing (Khelil et al., 2005; Frew et al., 2006) assume reasonable connectivity (existing end-to-end paths) and short disruption, which are quite different from delay-tolerant mobile environments. The disconnected nature of DTMN results in incomplete routing information exchange, so the duplications may be needed to improve messages delivery ratio and shorten delivery time.
MOBILITY MODELS ANALYSIS
Existing mobility models are designed for non-delay-tolerant Ad hoc networks that do not qualify the large time scale in DTMN (Khelil et al., 2005). The routing paradigm differs significantly from traditional MANET routing models: rather than transmitting message, nodes carry the data around the network by means of their mobility (Abdulla and Simon, 2007). In addition, routing information in DTMN becomes stale quickly, so replications of messages are required to shorten message delivery delay.
Mobility of nodes is the key issue in DTMN. Some researchers work on nodes mobility-aided routing decision. Message ferrying routing is the first kind of routing strategies that tries to combine the data transmission with mobile nodes; message ferry carry messages from the source to destination or from a node-cluster to another, as a ferry-boat does. So, the routing decision and mobility control (Zhao et al., 2005) are tightly coupled with routing performance (message delivery delay and ratio) (Harras and Almeroth, 2006; Kim and Eun, 2008). Under dense population scenarios, Khelil etc. gave several definitions about contacts called contact-based metrics and drew the conclusion that average encounter rate plays a central role for these metrics (Khelil et al., 2005).
A number of routings were analyzed under RWP (Random Waypoint) model (Abdulla and Simon, 2007) and Manhattan mobility model (Kang and Kim, 2008). In RWP, the random of movement nodes without any mobility pattern makes movement history ineffective in calculating a movement vector, so nodes’ history information is useless. For vector routing, if two nodes are moving in the same direction, the replication of messages does not significantly contribute to successful delivery to their destination nodes (Kang and Kim, 2008). In Manhattan model, nodes like cars and buses move alone the rode in the directions of forward, backward, left and right with the probabilities αf, αb, αl, αr and αf, αb, αl, αr = 1, therefore movement history should be taken into account.
The Brownian Walk Model (BWM) simulates the Brownian motion that are defined
by a vector
In random waypoint mobility model, mobile users move with constant speed between randomly chosen points inside the simulation area and perform certain trip sequences. The random waypoint mobility model with obstacle avoidance is similar to the RWP Model but users should avoid predefined obstructions in the movement area (Johansson et al., 1999).
The restricted random waypoint mobility model consists of three large movement areas and three highways connecting them. Within an area the mobile uses move according to RWP mobility model, but with a certain probability they move on a highway to another area (Blazevic et al., 2002).
In graph-based walk mobility model, movement is constrained in an infrastructure with a graph. The vertices of the graph represent places users may visit and the edges model interconnections between the places. The users move between randomly chosen vertices of the graph on edges thus representing spatial constraints of the simulation site (Tian et al., 2002).
Liu and Maguire (1995) mobility model is built as a two-level hierarchy: Global Mobility Model (GMM) and Local Mobility Model (LMM). GMM is used to create intercell movements with a list of cells to be visited and LMM is used to create intracell movement with three parameters of current positions, speed and direction (Liu and Maguire, 1995). The Integrated Mobility Model consists of three levels: city area, area zone and street units and provides a possibility to model the mobility of different classes of mobile users (Markoulidakis et al., 1997). In general, spatial environment, user trip sequences and movement dynamic should be reflected in the simulation (Stepanov et al., 2003).
Most mobility-model listed above are drawn from RWP and widely used in mobile Ad hoc network routing protocols, however RWP is considered harmful since RWP in its current form fails to reach a steady state in terms of instantaneous average node speed, but rather the speed continuously decreases as simulation progresses. Consequently, this model cannot be used to conduct performance evaluation measured as time averages that can result in misleading or incorrect conclusions (Yoon et al., 2003). On setting a positive minimum speed, the modified model is able to quickly converge to a constant speed.
METRICS FOR ROUTING CALCULATION
Number of connections: If the distance of two nodes is less than communication range, there is a connection between these two nodes. Then handover of messages happens between these two nodes if the change of connection exists and during of this connection, two nodes exchange the messages they do not carry, as shown in Fig. 1 of appendix. The connections of node 1 with connections’ beginning time and ending time are plotted in Fig. 1 and total number of connections of all nodes is plotted in Fig. 2.
In DTMN, connections between nodes a means a chance for changing messages. From Fig. 3-5, we found that simulation area, number of nodes and communication range of node influence number of connection, but speed of nodes does not as shown in Fig. 5.
Number of new connections: During the simulation, we found that two connected node at time ti are likely to maintain their connection at time ti+1, but connection at time ti+1 is always helpless to improve delivery ratio. New connections play a more important role in message delivery than the older ones, in another words, new connections are more tenable to contribute to successful messages transmission than the repeated connections of the same pair of nodes.
| Fig. 1: | Connections-time matrix of node 1 |
| Fig. 2: | Total number of connections |
| Fig. 3: | Average No. of connections vs. area’s width with different No. of nodes (r = 300 m, V∈[1,30] m sec-1) |
| Fig. 4: | Average No. of connections vs. communication range of a node with different No. of nodes (A = 1000 m, V ∈[1,10] m sec-1) |
| Fig. 5: | Average of connections vs. nodes’ speed with different No. of nodes (A = 1000 m, r = 300 m) |
Cumulated Distribution Function (CDF) of number of new connections is shown in Fig. 6 and the average time of approaching the maximum CDF of number of new connection are shown in Fig. 7. Whenever a pair of nodes meets for the first time, this metric is incremented by one; future connections after the first meeting between this pair of nodes are not counted (Kim and Eun, 2008).
Comparing Fig. 5 with 6, we draw the conclusion that nodes’ speed influence the number of new connections but the number of connections and number of new connections is important for delivering messages to destination.
| Fig. 6: | CDF of NO. of new connections (N=15, V∈[21,30] m sec-1, A = 1000 m) |
| Fig. 7: | Average time of approaching the maximum CDF of No. of new connections (A = 1000 m, r = 300 m) |
WEIGHTED EVERY CONNECTION (WEC) ROUTING
Strategies of every connection routing: Message transfer only occurs when nodes meet each other. Studying the characteristics of meeting times and the inter-arrival times nodes play important roles in the analysis of routing schemes (Kang and Kim, 2008). The average encounter frequency play a central role for the contract-based mobility metrics (Khelil et al., 2005) and node speed and density influence the routing encounter frequency.
Whenever a pair of nodes meets for the first time, the total number of new connections is incremented by one. Future connections after the first meeting between this pair of nodes are not counted. The new connections are more likely to contribute to successful message delivery than the repeated connections to the same nodes (Kim and Eun, 2008). And the weight of new connections is bigger than that of the older ones under the circumstance that several nodes may establish connections with a node simultaneously, as shown in Fig. 1 (t = 50 sec) of appendix.
Nodes of TDMN used local information of its own, not global network information e.g., network topology, or location and mobility pattern of other nodes. However, when two nodes meet, they exchange summary of the other, so each node knows the messages absent and duplicates them. In this way, node infects the nodes encountering it. Every message has a counter with an expiration time E, if E = 0 the message should be deleted from memory to avoid unnecessary duplication and long-term buffer occupancy.
Performance evaluation: Average message delivery ratio. The average message delivery ratio is the ratio of delivered messages to the number of messages that supposed to delivery to the destination. Expired messages should be deleted from nodes’ buffer. And a generalized assumption is made that no messages are dropped due to buffer overflow.
Delay of delivered message. This metric shows the time taken from the source to destination after a message is sent. Only successfully delivered messages are taken into account, since the undelivered messages are of infinite delivery time.
Buffer occupancy. In this monograph, buffers of the nodes are set to be big enough to hold all the messages transferred to it. Messages are dropped only due to expiration not buffer overflow.
WEC routing simulation and data analysis: In Modified RWP (M-RWP) model, all nodes move randomly: a node randomly chooses an initial point in simulation area and moves towards another one with an average speed, which is uniformly distributed between Vmin (not zero) and Vmax and so on; pauses time at a destination point is uniformly distributed. And then the node again chooses a second point with another speed between Vmin and Vmax and so on. In M-RWP model there is no statistical or history information available since all nodes move randomly and arbitrarily as shown in Fig. 2 of appendix. In Table 1, we listed the parameters utilized in simulation, in which the single jump length is the length from a point to another at which a node changes the direction and speed. The weight of a new connection is 1 and weight of an old one is 0.5 in the period of a message’s expiration time.
Funded by China Academy of Space Technology and PLA General Armament Department, the study is conducted at Zhejiang University, Hangzhou, People’s Republic of China from June 2009 to May 2011, The projects names are Research of fountain code and loss-tolerant protocol in deep space communications and Continuous navigation and communication in deep space exploration based on GEO satellites formation.
| Table 1: | Parameters in simulation |
| *Only sparse nodes exist in DTN; so too much nodes would result in E2E paths, which is no longer the characteristic of DTMN | |
Performance of WEC routing: In the M-RWP model, a connection means the chance of exchanging message between two nodes, so every-connection routing is the fast way of delivery messages to destinations described above, but occupies most buffer resources, hence lowers the efficiency of network performance. We set an expiration time. A node deletes the occupied memory on reaching the expiration time, in this way resources nodes are saved and efficiency of networks are guaranteed. The performances of WEC routing strategy are shown in Fig. 8a-c.
A bigger communication range leads to better routing performance, e.g., higher the percent of received message and lower delay time, but higher loaded buffer. And longer expiration time dose help to improve delivery ratio and also the buffer is occupied for a longer time. In Fig. 8c, only the delay of successfully delivered messages is counted since delay of dropped messages are infinite.
More nodes in simulation area lead to higher delivery ratio and longer delay time and generate more messages, so nodes are heavier loaded. And faster nodes’ speed helps to delivery more messages and shortens delay time and results in more buffer occupancy as shown in Fig. 9a-c.
Buffer-release-enhanced WEC routing: In every connection routing, nodes utilize chances of connections to exchange messages they don’t have. If a message is transmitted to the destination, the message still resides in other node’s buffer till the coming of expiration time, which wastes memory and results in unnecessary messages exchange to other nodes. So, in order to save network and nodes resources, an anti-flooding strategy is adopted to fasten the speed of buffer-releasing. The routing is named buffer-release-enhanced every connection (BreWEC) routing. BreWEC routing is kind of controlled flooding algorithm w ith feedback mechanism and is different from spray-and-wait routing (Spyropoulos et al., 2005).
| Fig. 8: | Performance of WEC routing vs. message expiration time with
different nodes’ communication ranges (N = 5, V∈[1,30] m sec-1,
Rmg = 1/node/5 sec, M = 100). (a) Percent of received messages
(x100%), (b) normalized buffer occupied and (c) average delay time |
In BreWEC routing, after a message has arrived the destination, the destination generates a buffer-releasing packet, which informs the nodes to erase this message. Without lowering the routing performance, the BreWEC routing tries to reduce buffer-load, because every chance of message exchange are utilized and only successfully transmitted messages are erased from networks.
| Fig. 9: | Performance of WEC routing vs. number of nodes with different
nodes’ speed (r = 150 m, Rmg = 1/ node/10 sec, E = 50 sec,
M = 100). (a) Percent of received messages (x100%), (b) normalized buffer
occupied and (c) average delay time |
The buffer-releasing packet is composed by source ID (5 bits), destination ID (5 bits), message generation time (17 bits) and a shorter countdown timer (7 bits), so its total length is 34 bits. The countdown timer is to guarantee the releasing processes only happen nearby the destination nodes, because the successfully transmitted messages on distant nodes may have expired already.
| Fig. 10: | Messages exchange and releasing processes between two nodes of BreWEC routing |
| Fig. 11: | Comparison of three routing performance (r = 50 m, Rmg
= 1/node/ 5 sec, V∈[1,30] m sec-1, N = 10). (a) Percent
of received messages (x100%) and (b) normalized buffer occupied |
The messages exchange and releasing process between two nodes is shown in Fig. 10.
Because the BreWEC routing only erases the successfully transmitted messages from networks, so delivery ratio and delay time are not impaired. Comparisons of three routing methods are listed in Table 2 and shown in Fig. 11a and b.
| Table 2: | Routing strategies comparison |
| Fig. 12: | Normalized buffer occupied of WEC and BreEC routing strategies (r = 50 m, Rmg = 1 /node/ 5 sec, V∈ [1,30] m sec-1, M = 150, Ct = E/2) |
| Fig. 13: | Normalized buffer occupied of BreEC routing with different
number of nodes (r = 50 m, Rmg = 1 /node/ 5 sec, V∈ [1,30]
m sec-1, M = 150, E = 150 sec) |
Buffer of nodes are less loaded as shown in Fig. 12 and 13. From Fig. 12 and 13, we knew that BreEC routing could lower burden of nodes in DTMN greatly without degrading the performance of WEC routing. And counter timer Ct = 0.5E would be an optimal value for buffer releasing.
DISCUSSION AND FUTURE WORKS
In some wireless communication networks, such as Ad hoc networks (Lakshmi and Sankaranarayanan, 2006; Barati et al., 2008; Bhagyaveni and Shanmugavel, 2005), CDMA networks (Dafalla et al., 2007) and even some workflow net (Zhu et al., 2010). The finds in this monograph may support the conclusions of other researchers mentioned above. The routing decision processes should also be fault tolerant (Barati et al., 2008). Without considering power control done in reference (Dafalla et al., 2007), the buffer-release-enhanced weighted every connection may more attention to buffer occupancy because of lacking of E2E path and long time buffer occupancy. The conclusions of the study may be utilized in other kinds of networks with modification, for the characteristics of delay tolerant mobile networks are quite different.
Routing decision may consider the information of networks and should be analyzed under different models e.g hybrid models or island mode; and message ferry or router is another popular method in transferring messages. So, following researches may concentrate on routing in different scenarios.
CONCLUSIONS
Under the modified random waypoint model, we proposed a weighted every connection routing in delay tolerant mobile networks, which pay more attention to new connections than the older ones between nodes, because we found that the new connections are more helpful to delivery messages to destinations. However, weighted every connection routing always occupies too much buffer resources; a buffer-release-enhanced mechanism is adopted to alleviate buffer-load without decreasing the performance the routing decision.
Performance (messages delivery ratio and delay) of weighted every connection routing is influenced by width of simulation area, number of nodes, nodes’ speed and communication range and message expiration time; and the buffer-load is influenced by message generation rate, number of nodes, message expiration time and countdown timer.
Buffer-release-enhanced weighted every connection routing may only increase processing time by the introducing of messages releasing time, but the benefit is lighter loaded buffers and higher efficiency of networks.
ACKNOWLEDGMENTS
This study is supported by the Astronautic technology innovation fund (No: CASC200904/GFJG-128202-E10902), a previous research program of Telemetry and Communication Institute (No: E2010040/GFJG-128202-E21001) and the CAST innovation fund program (No: CAST20090401).
Under graduated students Long Xu, Ze-qu Yang, Yang Wang, Jia Zhou and Zheng Chen of SRTP are also contributed to this study.
APPENDIX
| Fig. 1: | Connections among nodes at (a) t = 50 and (b) 500 sec (N = 5) |
| Fig. 2: | Trace of a node under M-RWP model, (a) t = 100 sec, (b) 500 sec, (c) 1000 sec, (d) 2000 sec and (e) 3000 sec |