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.,
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 ,
where V is the speed and θ is the direction and thus
producing random motion. In smooth mobility model, speed and direction are changed
incrementally during time units until the target is reached.
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.,
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.
|| Connections-time matrix of node 1
|| Total number of connections
||Average No. of connections vs. areas width with different
No. of nodes (r = 300 m, V∈[1,30] m sec-1)
||Average No. of connections vs. communication range of a node
with different No. of nodes (A = 1000 m, V ∈[1,10] m sec-1)
||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
||CDF of NO. of new connections (N=15, V∈[21,30] m sec-1,
A = 1000 m)
||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
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 messages expiration time.
Funded by China Academy of Space Technology and PLA General Armament Department,
the study is conducted at Zhejiang University, Hangzhou, Peoples 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
|| 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 dont have. If
a message is transmitted to the destination, the message still resides in other
nodes 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).
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.
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.
||Messages exchange and releasing processes between two nodes
of BreWEC routing
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
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.
|| Routing strategies comparison
||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)
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.
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.
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.
||Connections among nodes at (a) t = 50 and (b) 500 sec (N =
||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