Advanced
Performance Improvement of Delay-Tolerant Networks with Mobility Control under Group Mobility
Performance Improvement of Delay-Tolerant Networks with Mobility Control under Group Mobility
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jun, 9(6): 2180-2200
Copyright © 2015, Korean Society For Internet Information
  • Received : July 12, 2014
  • Accepted : May 10, 2015
  • Published : June 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Ling Fu Xie
Peter Han Joo Chong

Abstract
This paper considers mobility control to improve packet delivery in delay-tolerant networks (DTNs) under group mobility. Based on the group structure in group mobility, we propose two mobility control techniques; group formation enforcement and group purposeful movement. Both techniques can be used to increase the contact opportunities between groups by extending the group’s reachability. In addition, they can be easily integrated into some existing DTN routing schemes under group mobility to effectively expedite the packet delivery. This paper is divided into 2 parts. First, we study how our proposed mobility control schemes reduce the packet delivery delay in DTNs by integrating them into one simple routing scheme called group-epidemic routing (G-ER). For each scheme, we analytically derive the cumulative density function of the packet delivery delay to show how it can effectively reduce the packet delivery delay. Then, based on our second proposed technique, the group purposeful movement, we design a new DTN routing scheme, called purposeful movement assisted routing (PMAR), to further reduce the packet delay. Extensive simulations in NS2 have been conducted to show the significant improvement of PMAR over G-ER under different practical network conditions.
Keywords
1. Introduction
D elay-tolerant network (DTN) is a sparse or disconnected mobile ad hoc network where there is normally no connection or end-to-end path between any source and destination pair [1] . Hence, the traditional routing protocols designed for the connected network, such as Dynamic Source Routing (DSR) [2] , fail to work in DTN [10] . In previous studies in DTN, two main approaches are proposed for the packet delivery, which are illustrated as follows.
The first approach is to increase the network connectivity by introducing more nodes to the network, thus decreasing or even avoiding the probability of the disconnection in the network [3 - 6] . In [3] , these introduced nodes are randomly distributed in the network, whereas in [4 - 6] they are purposely placed to fill the gaps dynamically formed in the network or to keep the network connected most of time. However, the main drawbacks of introducing this kind of node with a special role in DTN lie in the potential failure of these special nodes and the centralized way to detect the disconnection and displace these special nodes.
The second approach, called store-carry-forward approach [7] , is to make use of the movement of the node to deliver packets. Since there is no guarantee to set up a complete route between the source and destination pair in DTN, one feasible way for the packet delivery is to wait for any new contact opportunities arising in the changing of the network topology caused by the node movement. Therefore, to store and carry the packet becomes essential in this second approach. Most proposed routing schemes adopting this store-carry-forward approach can be further classified into the opportunistic routing and the mobility control based routing.
In the opportunistic routing, each node follows its initial planned movement and does not change its trajectory even though it cannot be connected to the destination(s) [8 - 15] ; and it just passively waits for the chances to be connected to other nodes including the destination node(s) during its movement. Obviously, the problem of this strategy is that the packet delivery delay is unpredictable or very long in case that the destination node is out of contact from most of the nodes for long time. By contrast, in the mobility control based routing, the mobility of some nodes is controlled that they move purposely over the network area to assist in establishing a connection to the destination node(s) [16 - 19] . Thus, with mobility control in DTN, packets can be delivered faster. In [16 , 17] , a special kind of node, called ferry node, is introduced to the network, and its mobility is controlled to assist other nodes in the packet delivery. Specifically, if a source node has packets to send to a destination node, the ferry node will firstly move towards the source node and carry its packets. Then, the ferry node helps deliver the packets to the destination node. Similar to [4 - 6] , the drawback in [16 , 17] lies in the potential failure of the ferry node. Authors in [18] considers only adjusting the node speed for optimal packet delivery, whereas a more complicated solution is proposed in [19] , where some intermediate nodes are employed to move to certain locations to help establish an end-to-end connection to the destination node. However, this solution suffers from its strict assumptions, e.g., how each node moves in the network should be known to each other in advance.
Hence, as seen from the previous DTN studies (e.g., [19] ) above, mobility control is a promising approach to shorten the packet delivery delay in DTN, but the difficulty lies in its deployment. The reason for this difficulty is that most studies above target entity mobility [23] , which assumes independence among nodes’ movement. However, the mobility control based routing requires some intermediate nodes to move in a cooperative way as shown in [19] . In fact, nodes in many real scenarios are required to move in a cooperative way due to some common mission or interest for them. For example, in the military field, soldiers or tanks for a common mission generally form a group and move forward close to each other. Thus, group mobility [20 - 22] is proposed to mimic this type of cooperative scenarios. In general, most of group mobility models proposed before [20 - 22] present the following two features. First, nodes in one group form a connected sub-network and there is a leader in each group to organize and manage its group. Thus, when the groups in the network are isolated, a disconnected network will be formed. Second, the cooperation can be well supported in each group. With these two features, it is obvious that the mobility control can be implemented under group mobility.
In this paper, we consider the performance improvement of mobility control in DTN under group mobility [20 - 22] . Specifically, we propose two mobility control techniques under group mobility; the group formation enforcement and the group purposeful movement. The group formation enforcement requires some nodes in one group to be positioned strategically such that these nodes can help extend the reachability of the group. Thus, this technique can be used to increase the contact opportunities between groups. The group purposeful movement considers creating a new connection between two groups by letting some nodes in one group move purposely to approach the other group which is currently out of contact. The new created connection provides a way for one group to deliver packets to the other. Hence, with this second technique, one group can expand its reachability and create more contact opportunities with other groups. Importantly, both two proposed mobility control techniques can be easily integrated into some existing DTN routing scheme to effectively expedite the packet delivery or reduce the packet delivery delay. In this paper, we focus on the study of how each proposed technique reduces the packet delivery delay in DTN. To the best of our knowledge, none of the previous studies has considered the mobility control for the packet delivery in DTN under group mobility. The contribution of this paper is threefold.
  • We propose two mobility control techniques in DTN under group mobility; the group formation enforcement and the group purposeful movement. Both two techniques can be integrated into some existing DTN routing scheme to effectively expedite the packet delivery.
  • For each proposed mobility control technique, we integrate it into one simple existing DTN routing scheme called group-epidemic routing (G-ER)[21], and then employ the stochastic analysis to derive the cumulative density function of the packet delivery delay in a simple network scenario to show the performance improvement in terms of the packet delivery delay.
  • In particular, we put emphasis on the performance study of the group purposeful movement mobility control technique under different network conditions. We firstly design a new DTN routing scheme called purposeful movement assisted routing (PMAR), in which the group purposeful movement is implemented. Then, we integrate PMAR into G-ER and conduct extensive simulations in NS2 to show the effectiveness of PMAR in reducing the packet delivery delay of G-ER in different practical network conditions.
The rest of this paper is organized as follows. In Section 2, we give a brief review of G-ER. Section 3 gives the stochastic analysis of how the two proposed mobility control techniques reduce the packet delivery delay, respectively. PMAR is illustrated in Section 4, followed by the simulation study in Section 5. Lastly, Section 6 concludes this paper.
2. Review of Group-Epidemic Routing
G-ER [21] , which is designed based on a well-known DTN routing protocol, i.e., Epidemic Routing [10] , is specifically proposed for group mobility. The key strategy in G-ER is to treat each group as one unit and disseminate one copy of each packet to one group only, and it works as follows.
If a packet is an intra-group packet (or if a packet has its source and destination in the same group), it will be routed to its destination by the intra-group routing, i.e., Destination Sequenced Distance Vector routing (DSDV). And if a packet is an inter-group packet (or if a packet is destined to another group), it will be firstly routed by the inter-group routing to any other group which does not have a copy of this packet. Finally, this inter-group packet will reach its destination group, and then will be delivered to its destination node by DSDV. Note that the destination node of a packet never delivers that packet to other groups. Here, we simply illustrate how the inter-group routing in G-ER works to deliver inter-group packets between groups.
First, when two groups meet each other, each group determines what packets the neighboring group has not received. For this determination, each node in one group maintains a table called Group Summary Vector (GSV), which is used to record the packets previously received by all of the nodes in its group. Thus, the two groups’ GSVs are firstly exchanged to let each node in the two groups obtain the neighboring group’s GSV, the details of which are shown in Fig. 1 a. Second, after comparing the received GSV with the own maintained GSV, each node can send the packets the neighboring group does not have, as shown in Fig. 1 b. Third, once a node receives some new packets from the neighboring group, it will inform other nodes in its group about these new received packets and let them update their GSVs.
PPT Slide
Lager Image
GSV exchange and broadcast inside the group (a) and data packet exchange between groups in G-ER (b)
Another important mechanism proposed in G-ER is the buffer sharing in each group. This mechanism states that the buffer resource of one node can be shared by all other nodes in its group. Thus, with buffer sharing, if one node detects its buffer is full upon receiving some inter-group packets, it can store them at other nodes in its group.
3. Analysis of the Two Mobility Control Techniques
In this Section, we firstly present the network model for our analysis. Then, based on this model, we give the stochastic analysis of how the two proposed mobility control techniques reduce the packet delivery delay of G-ER in DTN under group mobility, respectively.
- 3.1 Network Model
In this analysis, we suppose that there are a total of N +1 ( N ≥1) independent groups moving within a L × L ( km 2 ) network area, and that the radio transmission range of each node is r (in km). Other important assumptions related to the network model are stated as follows.
First, we illustrate how each group in the network is formed. As mentioned earlier, each group is organized by a leader, so we assume that the leader locates at the center of the group and all of its members move randomly around it. Moreover, we further assume that each member is within the radio transmission range of the leader, r , for simplicity. Thus, each group assumed here has a circular coverage with a radius of d ( d r ) (in km), as shown in Fig. 2 a. Actually, our group structure is similar to the widely used group mobility model called Reference Point Group Mobility (RPGM) [22] , of which details are omitted here.
PPT Slide
Lager Image
The assumed group structure (a) and illustration of the group movement (b)
Second, we present how each group moves in the network area. The movement of each group conforms to the Random Waypoint Mobility Model (RWMM) [24] . Specifically, before a group starts to move, its leader randomly selects a destination point in the network area, and each member also randomly selects a point near the leader’s point within a distance of d . Then, the leader chooses a velocity, v , uniformly in [ vmin , vmax ] (in km/h), and each member chooses a velocity around v . Note that this velocity selection for the group member is used to keep each group connected most of time. Later, once all nodes reach their destination points, they can pause for time tp . After the pause time, the group repeats the above procedure to continue moving. Fig. 2 b roughly illustrates how one group moves within the network area.
Third, similar to [25] , we assume a simple traffic model for this analysis: among the N +1 groups, only one group, say group x , generates one data packet P1 to send to another group, say group y . Note that this data packet can be generated by any node in group x .
Fourth, we further assume that (1) each group is capable of storing one data packet; and (2) if two groups meet (i.e., if any two nodes from two groups meet), the contact duration is long enough to allow any node in one group to send a data packet to the other group. Thus, if group x meets an intermediate group, say group z , which previously has not received P1, then group z can also obtain P1 after this meeting.
- 3.2 Cumulative Density Function of the Packet Delivery Delay in G-ER
With the abovementioned assumptions and the group behavior defined in G-ER in Section II, we firstly derive the lower bound and the upper bound of the cumulative density function (CDF) of the packet delivery delay, TGE , under G-ER when tp =0 and r L . We denote FTGE as the CDF of TGE , and we let LB ( FTGE ) and UB ( FTGE )represent the lower bound and the upper bound of FTGE , respectively. These two bounds will be considered as the benchmark in our paper. To derive the two bounds, we start with the computation of the following three parameters when tp =0 and r L .
  • Theinter-meeting time between two leaders,: this is the time interval between two consecutive meetings between two leaders. Note that a meeting between two nodes or leaders means the distance between them is less than the radio transmission range,r. It is shown in[24]that thisunder RWMM is exponentially distributed, of which the intensity,, is given by
PPT Slide
Lager Image
  • In (1),ωis a constant with the value about 1.3683; and E[V∗] is the average relative speed between the two leaders, and its calculation can be found in[24]. Thus, the averageis 1/(in hours).
  • Theinter-connection time between two leaders,: this is the time interval between two consecutive connections between two leaders. Note that a connection between two leaders means the two leaders are meeting each other or being connected by some of their members. Thus, we see that 1) this time interval is less than the inter-meeting time between two leaders above, i.e.,<, because even the distance between two leaders is beyondr, they can be still connected by their members; and 2) whendapproaches 0,will approach. Moreover, we here consider a new random variable, which is the time interval between two consecutive events that the distance between two leaders is withinr+2d. Similar to,is also exponentially distributed, of which the intensity,, is given by
PPT Slide
Lager Image
  • In fact, the value ofr+2dis the maximal distance between two leaders when they are connected, as shown inFig. 3. However, two leaders may not be connected when they arer+2dapart, because there may happen to be no members near the boundary of the group coverage due to the random mobility of all group members. Hence, we have<<.
PPT Slide
Lager Image
Maximal distance in a connection between two leaders
  • Theinter-meeting time between two groups,: this is the time interval between two consecutive meetings between two groups. As assumed above, each group is connected most of time, so if two groups meet each other (i.e., if any two nodes from two groups meet each other), their leaders must be connected, and vice versa. Thus, we have=.
Now, we employ Ordinary Differential Equations (ODEs) [26 , 27] to derive LB ( FTGE ). With the fourth assumption above, we can see that
PPT Slide
Lager Image
actually determines how fast the data packet is spread over groups in the network . This is to say, if two groups meet frequently (i.e., if
PPT Slide
Lager Image
is small), then P1 will be spread quickly. Thus, due to
PPT Slide
Lager Image
<
PPT Slide
Lager Image
as shown above, we can derive LB ( FTGE ) by assuming
PPT Slide
Lager Image
conforms to the known distribution of
PPT Slide
Lager Image
or by assuming d =0. Suppose the packet delivery delay in G-ER is T′GE under the assumption of d =0, then we have LB ( FTGE )= FT′GE . To derive FT′GE , two steps are involved.
Step 1 : Calculation of X ( t ). Suppose X ( t ) is dedicatedly used to count the number of groups (excluding the destination group) which have received P1 at time t . Then, X ( t ) can be treated as a Markov chain with the transition rate, R ( t ), expressed as follows
PPT Slide
Lager Image
For (3), we can use the following differential equation to solve it [25 , 26]
PPT Slide
Lager Image
The differential equation (4) above is separable and can be solved with the initial condition X (0)=1, i.e., only the source group x owns P1 at time 0. Consequently, X ( t ) is expressed as follows, of which the derivation is omitted here.
PPT Slide
Lager Image
Step 2 : Derivation of FT′GE . Suppose at time t the destination group y has not received P1. Then, let us consider P ( t < T′GE t + δt ), the probability that group y receives P1 in the subsequent small time interval δt . Since there are X ( t ) groups owning P1 at time t , the rate of group y receiving P1 at time t will be equal to
PPT Slide
Lager Image
X ( t ). Thus, P ( t < T′GE t + δt ) can be calculated as follows.
PPT Slide
Lager Image
Due to FT′GE ( t )= P ( T′GE t ) and FT′GE ( t + δt )= P ( T′GE ≤+ t + δt ), we have the following differential equation for FT′GE ( t ) from (6):
PPT Slide
Lager Image
The differential equation (7) is also separable and can be solved with the initial condition FT′GE (0)=0. Finally, we obtain FT′GE ( t ) or LB ( FTGE )as shown in the following expression, of which the derivation is omitted here.
PPT Slide
Lager Image
Next, we proceed to derive UB ( FTGE ). Similarly, due to
PPT Slide
Lager Image
>
PPT Slide
Lager Image
, we can derive UB ( FTGE )by assuming
PPT Slide
Lager Image
conforms to the known distribution of
PPT Slide
Lager Image
. Particularly, the steps to derive UB ( FTGE )are the same as those to derive LB ( FTGE ) shown above. More specifically, we only need to replace
PPT Slide
Lager Image
with
PPT Slide
Lager Image
in (8) to obtain UB ( FTGE ), which is given by the following equation.
PPT Slide
Lager Image
- 3.3 The Group Formation Enforcement
In previous sub-section, we have shown the lower bound and the upper bound of FTGE . In fact, it is highly impossible to achieve the upper bound of FTGE because of the random mobility of the group members around the leader in each group. Here, we propose a simple mobility control technique called the group formation enforcement to approach the upper bound of FTGE . The group formation enforcement imposes a constraint on the mobility of some members in each group such that a certain structure or formation appears in each group. Suppose each group leader leads at least four members, then the formation enforcement works as follows.
  • Each leader randomly selects four members to locate them at the east, south, west, and north boundary of the group coverage as shown inFig. 4a. And each of the four selected members is only allowed to move closely around the corresponding boundary.
  • The other rest members can still move freely within the group coverage.
PPT Slide
Lager Image
The extended reachability of the group (a) and the connection between two leaders under the formation enforcement (b)
Obviously, with this formation enforcement technique, the reachability of each group will be extended. More specifically, if we fix the four selected members above at the four boundary positions, then, any node within a distance of d + r to the leader is very likely to be connected to the leader, as shown in Fig. 4 a. Thus, as shown in Fig. 4 b, it is also very likely that two leaders within a distance of 2 d + r can be connected, which indicates that
PPT Slide
Lager Image
PPT Slide
Lager Image
or
PPT Slide
Lager Image
PPT Slide
Lager Image
. Consequently, with the group formation enforcement in G-ER, the upper bound of FTGE given by (9) can be approximated.
Note that for the CDF derivation above, we assume that each group is connected or all members in a group are within the radio transmission range of the leader. In fact, observing from Fig. 4 that we only need four members to execute the group formation enforcement, we could keep UB ( FTGE )still being approximated by the group formation enforcement even if we allow other members to leave freely from the group.
To show how the upper bound of FTGE is approximated under the formation enforcement, we run simulation in NS2 to show the CDF of TGE in the case of d r . As a comparison, we also conduct simulations by deactivating the formation enforcement or allowing all members to move freely around the leader. We emphasize that all simulation results shown here are collected in the ideal case that the contact duration between two meeting groups is long enough to allow one data packet to be sent from one group to the other. Table 1 shows the main simulation parameters.
Simulation parameters in the formation enforcement
PPT Slide
Lager Image
Simulation parameters in the formation enforcement
Before showing the simulation results of FTGE , we firstly determine UB ( FTGE ) and LB ( FTGE ) shown in (9) and (8), respectively. It can be seen from (8) and (9) that we only need to determine
PPT Slide
Lager Image
and
PPT Slide
Lager Image
under the setting shown in Table 1 for LB ( FTGE ) and UB ( FTGE ), respectively. In [24] it has shown that E[ V ]=8.7 km / h under RWMM when tp =0 and [ vmin,vmax ]=[4,10]. Thus, we get
PPT Slide
Lager Image
≈0.148 from (1) and
PPT Slide
Lager Image
=0.444 from (2). Accordingly, LB ( FTGE ) and UB ( FTGE ) are already determined under our simulation setting, as shown in Fig. 5 .
PPT Slide
Lager Image
Comparison between simulation results and analytical results for FTGE
After hundreds of simulation times, the collected simulation results of FTGE are shown in Fig. 5 . It can be observed that 1) with the group formation enforcement, G-ER delivers packets faster than that without mobility control, and 2) the group formation enforcement is an effective technique to improve G-ER to approach UB ( FTGE ).
- 3.4 The Group Purposeful Movement
Besides the technique of the group formation enforcement, we here introduce another mobility control technique called the group Purposeful Movement (PM). Due to the cooperative nature of each group mentioned earlier, the leader can command some of its members (e.g., robots or unmanned aerial vehicles in the military field, and hereafter called PM members) to move towards some other group to create a new connection between them when this other group is not far away but currently out of connection. For example, as shown in Fig. 6 , when the leader X detects that group Y is currently three hops away, it can let two members, nodes I and J, to move fast to approach group Y. Obviously, if a connection can be created between group X and group Y, it can expedite the packet delivery. This is the motivation for this second mobility control technique in this paper.
PPT Slide
Lager Image
Connection creation in the purposeful movement of a group
In this sub-section, we integrate this PM into G-ER to form a new scheme called G-ER+ and analytically study how this PM reduces the packet delivery delay of G-ER. For simplicity, we have the following three assumptions for this study.
  • 1) The radius,d, of the group coverage considered in this study is very small. As a result,FTGEapproachesLB(FTGE) and can be given by (8) approximately.
  • 2) The maximal number of PM members isM(M≥0). As a result, it is likely that a connection can be set up between two groups if the two leaders are within a distance of (M+1)r, as shown inFig. 6. For simplicity, we assume that as long as two leaders are within a distance of (M+1)r, a new connection can always be established, and a data packet can be delivered from one group to the other.
  • 3) Only the source group, i.e., groupx, will carry out the PM for establishing a new connection to the destination group, groupy. Other intermediate groups are not required to carry out the PM to deliver the packet from the source group.
With the three assumptions above, we now proceed to derive the CDF of the packet delivery delay, TPM , in G-ER+. We denote FTPM as the CDF of TPM . Similarly, the derivation of FTPM also involves two steps as shown below.
Step 1 : Calculation of X ( t ) in G-ER+. Here, X ( t ) is defined the same as before. Because there is no PM between any two of the groups counted by X ( t ) in G-ER+, the derived X ( t ) in G-ER+ is very close to that in G-ER in the condition of d ≈0. Thus, X ( t ) in G-ER+ can be given by (5) approximately.
Step 2 : Derivation of FTPM . Similar to the derivation of FT′GE shown above, we need to firstly determine the rate of group y receiving P1 at time t . Since at time t there are X ( t ) groups owning P1, including the source group, the total rate of group y receiving P1 is given by ( M +1)
PPT Slide
Lager Image
+
PPT Slide
Lager Image
( X ( t )−1), where the first term is contributed by the source group and the rest is contributed by all intermediate groups, of which each owns the packet P1. Consequently, we obtain the following equation
PPT Slide
Lager Image
Thus, from (10) we obtain the differential equation (11) as follows
PPT Slide
Lager Image
The differential equation (11) is also separable and can be solved with the initial condition FTPM (0)=0. We omit the details of the derivation and show FTPM as follows.
PPT Slide
Lager Image
Note that to have FTPM ( t ) in (12), we only need several members in one group to stay close to the leader to execute PM. Thus, in the group purposeful movement, we also do not require all members to stay close to the leader. We now present the following three observations based on (12).
First, to achieve the packet delivery delay TPM within some certain value of t at a given probability, we can set a minimal M , Mmin , properly. For example, under the network setting shown in Table 1 but with d ≈0, Table 2 shows several small values of Mmin for achieving different values of t with FTPM ( t )≥0.8. A larger Mmin not shown in Table 2 is actually not practical because we expect that it is not possible to create a connection between two groups far apart due to the group mobility.
Mminunder network setting shown inTable 1but withd≈0
PPT Slide
Lager Image
Mmin under network setting shown in Table 1 but with d≈0
Second, the proposed PM technique works more effectively in a DTN with small N . That is, when N is small, the average packet delivery delay of G-ER will be reduced more by the PM technique. We use one example as shown in Fig. 7 to show this observation. The results, i.e., the delay reduction of G-ER+ over G-ER, in Fig. 7 are obtained based on (8) and (12) at different N . It can be seen that the average packet delivery delay of G-ER is reduced more by the PM technique when N is small. The main reason for this observation is that when N is small, the network is more disconnected and thus, it is more likely that the packet highly relies on PM technique to be delivered to the destination. Third, given fixed M and N , the delay reduction of G-ER+ over G-ER does not vary with
PPT Slide
Lager Image
. This actually can be derived from (8) and (12). However, for simplicity, we also use one example to show this observation. Fig. 8 shows the delay reduction of G-ER+ over G-ER at different
PPT Slide
Lager Image
but with fixed M and N . Obviously, it can be seen that for any given M and N , the delay reduction keeps constant regardless of
PPT Slide
Lager Image
. Thus, the analysis here shows that the effectiveness of the PM technique is mainly determined by M and N .
PPT Slide
Lager Image
The delay reduction of G-ER+ over G-ER at different N
PPT Slide
Lager Image
The delay reduction of G-ER+ over G-ER at different
4. Purposeful Movement Assisted Routing
From the previous Section, we can see that the group formation enforcement is just a mobility control technique and it works independently of the DTN routing. However, the PM technique, as shown in Fig. 6 , further requires some specific mechanisms to initiate the purposeful movement of a group and deliver packets effectively along the newly established connection. Hence, in this Section we propose a new routing scheme called purposeful movement assisted routing (PMAR) to implement the PM technique. Then, by integrating PMAR into G-ER, we can study how it improves G-ER by simulation under different practical conditions.
First, we present the following two assumptions in PMAR: (1) each group member and each leader in the network is equipped with Global Positioning System (GPS); and (2) each leader is able to increase its transmission power to have a longer transmission range, R , in addition to the normal transmission range, r . Second, we present the two major objectives that PMAR needs to achieve; to establish a new connection between two disconnected groups if necessary and to deliver packets along the new established connection.
Now we proceed to introduce how PMAR is executed in a cooperative way in a group. There are eight major steps in PMAR as listed below: the first five steps are executed for the first objective, and the steps six and seven are executed for the second objective.
The first five steps used to create a new connection between groups are as follows.
  • 1) Condition detection for executing PMAR.We here consider one factor for triggering PMAR; the buffer utilization of the group. In particular, we only consider the buffer utilization of the inter-group packet generated by the group itself, and we set a threshold,Bt, for this buffer utilization to activate PMAR. The PM is organized by the leader, so the leader needs to firstly collect the buffer state information of its members. How to collect the member buffer state information for the leader will be described later. Once the leader detects that the inter-group packets mentioned above occupyBtof the group buffer space, PMAR will be triggered. Specifically, before triggering PMAR, the leader needs to find from the collected buffer state information a destination group to which its group has the most number of packets.
  • 2) Searching for the destination group.Once the destination group is found inStep 1), the leader of the source group proceeds to find the current location of that destination group. The group leader simply broadcasts a short message,PMsearch, which contains the destination group ID, using the radio of the transmission rangeR. If the leader of the destination group receives this broadcast, it immediately replies a short message,PMreply, which contains its current location, to the source group leader using the radio of the transmission rangeR. If the source group leader does not receive the reply from the destination group, it waits for a time interval,Wt, to go back toStep 1). The time intervalWtis used to avoid searching too frequently for the leader, and it is called scanning interval in this paper.
  • 3) Location determination for members to establish the new connection.If the source group leader receivesPMreplyfrom the destination group, it knows that a new connection can be set up. Thus, it needs to determine the number of PM members for establishing the new connection and the locations for them to move to. The new connection to the destination group will be set up as shown inFig. 6, in which the two end points of the new connection are the leader X of the source group and any node in the destination group Y. In particular, all PM members are arranged linearly between two leaders, and the distance between any two neighboring PM members is aboutr, as shown inFig. 6. Therefore, the number,Npm, of thePMmembers required for this new connection is given byNpm=⌊D/r⌋, whereDis the current distance between the two leaders. Meanwhile, the location (Xn, Yn) of thenth PM member, sayHn, can be found as follows.
PPT Slide
Lager Image
PPT Slide
Lager Image
  • where (Xl, Yl) is the current location of the source group leader, andθis the moving direction of the PM members as shown inFig. 6. This calculated (Xn, Yn) is actually adjustable within some certain range to keep the two groups connected.
  • 4) PM member selection.After calculating the location of each PM member, the source group leader needs to select members to execute the purposeful movement. To ensure a successful connection, the best is to select members which can move fast. For simplicity, we assume that there are some members in each group dedicated to carrying out the PM.
  • 5) PM member moving to its designated location.Once the leader has selected the PM members, it broadcasts a short message,PMstart, to those selected PM members to command them to move to the designated locations. We assume that each PM member, guided by its GPS, moves towards the designated location at a speed ofSpm. In the meantime, the leader stops moving forward until the PM ends as shown inStep 7), and the rest members, upon receivingPMstart, also stop moving forward but to move around the leader to keep the group connected. A connected group is necessary in many scenarios, e.g., in the military operation, soldiers in the same group should normally stay together most of time to lower the probability to be attacked.
After the five steps above, a new connection could be established provided that the destination group does not go too far away. Subsequently, the packet delivery along this new connection (i.e., the second objective in PMAR) follows.
  • 6) The packet delivery in PMAR.Once the new connection to the destination group is established, the PM member who is in contact with the destination group sends a message calledPMconnectto inform its leader as illustrated inFig. 9. Then, the leader broadcasts a message to its members to request them to forward their packets to the destination group along the new created connection. For simplicity, we set a time duration,tconnect, for the packet delivery in this step. When the set time expires, those PM members will start returning.
PPT Slide
Lager Image
Connection notification in PMAR
  • 7) Termination of PMAR.A simple method to terminate the new connection in PMAR is to let thePMmembers start returning to their original group coverage after they leave the group region for a period oftPM. ThistPMis the sum of the time spent by the PM members on moving to their designated locations and the time required for the packet delivery inStep 6). Thus,tPMis roughly given by
PPT Slide
Lager Image
  • Note that this estimatedtPMis also contained in the broadcast messagePMstartinStep 4).
  • 8) Movement recovery of the source group.Once each PM member moves back into the current group coverage, the source group leader will be informed, and finally the whole group can continue moving forward.
The overhead in terms of the energy consumption in PMAR is actually very limited. It can be seen that the overhead in PMAR refers to the transmissions of PMreply , PMsearch , and other control packets. The lengths of these control packets are similar, but the transmissions of PMreply and PMsearch require a radio with longer transmission range, thus consuming most of the energy in PMAR. Nevertheless, both PMreply and PMsearch are very short messages (only several bytes) as compared to the data packet, and later we will see from the simulation study that the number of PMreply and PMsearch transmitted in total is very low. Hence, the energy consumption in PMAR is very limited.
Now we illustrate how the proposed PMAR is integrated into G-ER to cooperate for the packet delivery. First, each group member in G-ER is required to report its buffer state to its leader: whenever a member is ready to broadcast its periodic DSDV routing update in G-ER, its current buffer state is collected and carried in the routing update packet. This member buffer state mainly states the number of inter-group packets destined to each other group. Again, only the information of the inter-group packet generated by the group itself is collected in this report, because one group is not responsible for carrying out the PM for other groups. Second, with this member buffer state information, a group leader can determine whether to initiate PMAR as introduced in Step 1) . If PMAR is not triggered in one group, then, that group will follow the procedures in G-ER to exchange packets with other groups. Hence, from the interaction between PMAR and G-ER, we can see that PMAR can be treated as an independent module to boost the performance of G-ER.
5. Simulation Study and Results
- 5.1 Simulation Model
The simulation study in this Section is conducted in NS2 to show how PMAR improves G-ER under different practical network conditions, namely under different searching range, R , different group speed, and different group buffer size. First, for the searching range, R , two values are selected; 2 r and 3 r . Second, we select the speed range [ vmin , vmax ] from three non-overlapped ranges as will be shown later. Third, we vary the total buffer space in each group (i.e., the group buffer size) from an inadequate value to an adequate value. The “inadequate” (“adequate”) means the group buffer size is less (larger) than the total number of the data packet generated at the source nodes. We would like to study how these three factors interactively affect the effectiveness of PMAR in improving G-ER. The main performance metric in this simulation study is the average packet delivery delay, td .
There are five groups in a 1 km ×1 km network area with 9 members in each group, and each group moves conforming to RWMM. The normal radio transmission range, r , for each node is 0.1km. For the traffic model, we let only one group among the five groups be the source group to generate traffic to another group for simplicity. The source group will generate a total of 400 packets: five members in the source group will take turn to generate packets every 50 seconds from the beginning of the simulation; and each member will generate 80 packets at a rate of 1 packet per second. Here, we assume the buffer space of the source group is fixed and it is capable to store all generated packets. Thus, all data packets can be successfully delivered to the destinations in all routing schemes in our simulation. Table 3 shows other main default simulation parameters, among which the PM member speed, Spm , is set at a relatively high value, i.e., 15m/s, as compared to the group speed. For each setting in the simulation, it is run for at least sixteen times to make the result within 90% confidence interval ±5%.
Default simulation parameters in PMAR
PPT Slide
Lager Image
Default simulation parameters in PMAR
- 5.2 PMAR at Different Group Buffer Size and Searching Range
In this sub-section, we study how PMAR improves G-ER under the default parameters shown in Table 3 by changing the group buffer size, b , and the searching range, R .
Fig. 10 shows the packet delivery delay, td , of G-ER and G-ER with PMAR at different b and R . Two observations can be made from Fig. 10 . First, it can be seen that PMAR reduces td of G-ER at all b and R . Particularly, we see that td of G-ER is significantly reduced by PMAR with a longer R (=3 r ). This is because with a longer R , the destination group could be found earlier and thus, the packet can be delivered earlier. Table 4 shows the performances in terms of the packet delivery ratio, rpmar , and the packet delivery delay, dpmar , of PMAR at different b and R . Obviously, it can be seen that dpmar at R = 300 m is much shorter than that at R = 200 m . Actually, we will find later that this longer R takes effect only when the group moves at a low speed or when the new connection established in PMAR stays for adequately long time. Second, for each R , as the group buffer size increases, the delay of G-ER is less reduced by PMAR. For example, when R = 300 m , td of G-ER is reduced by about 35% at b = 100 whereas it is reduced by about 20% at b = 700. There are two reasons for this observation. On one hand, with larger b of each group, G-ER itself delivers packets faster, thus reducing td as shown in Fig. 10 . On the other hand, with larger b , the ability of each intermediate group in forwarding the packets of the source group is intensified. As a result, the packet number delivered by PMAR decreases. By comparing the percentage of the packet delivered by PMAR, rpmar , at different b in Table 4 , we see that rpmar decreases to some extent at large b , especially at R = 300 m . Consequently, the effectiveness of PMAR gradually diminishes as b increases.
PPT Slide
Lager Image
The average packet delivery delay, td
Performance of PMAR
PPT Slide
Lager Image
Performance of PMAR
Note that the cost or overhead in achieving the benefit of PMAR above is limited. That is, we find in the simulation that the total number of the transmitted PMsearch and PMreply is only about 40 at R = 300 m and Wt = 15s. Besides, we also find that decreasing Wt increases the total cost, but cannot attain more benefit from PMAR. However, at a longer Wt , e.g., 30 s, the total cost decreases, but the benefit of PMAR is reduced. Hence, obviously, a proper Wt should be determined by the group mobility model to balance the benefit of PMAR and the energy consumption in PMAR: with a large Wt , the source group is likely to miss the opportunity to find the destination group nearby, and a small Wt is unnecessary and increases the energy consumption.
- 5.3 PMAR at Different Group Speed
In this sub-section, we proceed to study how PMAR improves G-ER at different group speeds, s . In addition to the default speed range shown in Table 3 , i.e., [1,4] (m/s), we set two higher speed ranges for this study; [4,7] (m/s) and [7,10] (m/s). The simulation here is conducted at a relative high b = 500 with other default parameters listed in Table 3 .
Table 5 shows the performance, in terms of td , between G-ER and G-ER with PMAR at different ranges of s . Obviously, as s increases, the improvement of G-ER with PMAR over G-ER descreases regarding the packet delivery delay. For example, as s increases to [7,10] (m/s), the delay reduction at R =300 even vanishes. There are two reasons for this observation. First, G-ER itself performs more effectively by delivering packets much faster as the group speed increases, as shown in Table 5 . This is because there are more contact opportunities between any two groups at higher group speed, which allows the packet to be spread to groups faster. Second, the contribution (i.e., the delivered packet number) of PMAR is reduced at high s . One reason is due to the unstable connection established by PMAR at high s . In order to see this instability, we define the following two parameters for the connection stability:
Performance of G-ER with PMAR at different node speed
PPT Slide
Lager Image
Performance of G-ER with PMAR at different node speed
  • Pbpmar: the probability of a successful connection in PMAR. After each PM member arrives at its designated location, the destination group may have moved away, which causes an unsuccessful connection.
  • rpmar: this is the same metric as defined inTable 4. Generally speaking, if the connection established in PMAR lasts for a longer time interval,rpmarwill become larger.
Table 6 shows Pbpmar and rpmar at different s when R =300. Overall speaking, it shows that Pbpmar and rpmar decreases with s . The trend of these two parameters shows that a less stable connection in PMAR is established at a higher group speed. Hence, as the contribution of PMAR diminishes at high s , the improvement of PMAR made to G-ER almost diminishes.
Connection parameters in PMAR at different node speed whenR= 300
PPT Slide
Lager Image
Connection parameters in PMAR at different node speed when R = 300
6. Conclusions
In this paper, we propose two mobility control techniques for delay-tolerant networks (DTN) under group mobility by making use of unique properties of the group structure. The two techniques are the group formation enforcement and the group purposeful movement. Both two techniques are simple, but effective in extending the reachability of the group, and they can be integrated into some existing DTN routing scheme under group mobility to expedite the packet delivery. We integrate them into a simple replication based routing scheme called group-epidemic routing (G-ER) and analytically show that 1) with the group formation enforcement, the upper bound of the cumulative density function of the packet delivery delay in G-ER can be approached; and 2) with the group purposeful movement, the packet delivery delay in G-ER can be greatly reduced in the scenario where a limited number of groups exist.
In particular, we put emphasis on the performance study of the second technique, i.e., the group purposeful movement, under different network conditions. Specifically, we firstly design a new routing scheme called purposeful movement assisted routing (PMAR) to implement this second technique. Then, we conduct simulations in different network conditions to evaluate the effectiveness of PMAR in improving G-ER. The simulation results show that PMAR works effectively when the group buffer size is small and the group speed is low.
Based on the simulation results in this paper, we believe that we can still improve PMAR by maintaining a stable connection to the destination group in PMAR at relatively high group speed. In addition, given a group mobility model, how to find an optimal scanning interval Wt for energy saving in PMAR is also our focus in the future. We leave them as our future work.
BIO
Ling Fu Xie is currently a research fellow in the Hong Kong Polytechnic University, Hong Kong. He received the Ph.D. degree from Nanyang Technological University, Singapore, in 2014, and the M. Eng. degree and B. Eng. degree in communications and information system from University of Electronic Science and Technology of China in 2009 and 2006, respectively. His research focuses on wireless networking in mobile ad hoc networks, vehicular ad hoc networks, etc.
Peter Han Joo Chong received the B.Eng. (with distinction) in electrical engineering from the Technical University of Nova Scotia, Halifax, NS, Canada, in 1993, and the M.A.Sc. and Ph.D. degrees in electrical engineering from the University of British Columbia, Vancouver, BC, Canada, in 1996 and 2000, respectively. Between July 2000 and January 2001, he worked in the Advanced Networks Division at Agilent Technologies Canada Inc., Vancouver, BC, Canada. From February 2001 to May 2002, he was with the Radio Communications Laboratory at Nokia Research Center, Helsinki, Finland, and was involved in research on WCDMA and standardization for HSDPA. Since May 2002, he has been with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, where he is now an Associate Professor (Tenured). He was an Assistant Head of Division of Communication Engineering between July 2011 and June 2013, Since July 2013, he has been an Director of Infinitus, Infocomm Centre of Excellence in School of EEE. He has visited Tohoku University, Japan, as a Visiting Scientist in 2010 and Chinese University of Hong Kong (CUHK), Hong Kong, between 2011 and 2012. He is currently an Adjunct Associate Professor of CUHK. He was a Technical Program Committee Chair for Mobility Conference 2005 and 2006, a Chair of Mobility Conference 2007 and 2008, a TPC Co-Chair of IEEE International Conference on Networks (ICON) 2012 and General Chair of International Conference on Information, Communications, and Signal Processing (ICICS) 2013. He served as a Guest Editor of Journal of Internet Technology in 2006, International Journal of Ad Hoc and Ubiquitous Computing in 2007 and lead Guest Editor of IEEE Communications Magazine in 2007 and IEEE Wireless Communications in 2011. He is an Editorial Board Member of Security and Communication Networks, Wireless Sensor Network, and an Editor of Far East Journal of Electronics and Communications, and KSII Transactions on Internet and Information Systems. His research interests are in the areas of mobile communications systems including network coding routing, MANETs, multihop cellular networks, green radio networks and vehicular communications networks.
References
Juang P. , Oki H. , Wang Y. , Maronosi M. , Peh L. , Rubenstein D. “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet,” in Proc. of ASPLOS 2002 96 - 107
Zhang M. , Chong Peter H. J. “Performance comparison of flat and cluster-based hierarchical ad hoc routing with entity and group mobility,” in Proc. of IEEE WCNC 2009 1 - 6
Soares V. N. G. J. , Farahmand F. , Rodrigues J. J. P. C. “Improving vehicular delay-tolerant network performance with relay nodes,” in Proc. of 5th Euro Conference on Next Generation Internet Networks 2009 1 - 5
Dai L. L. , Chan V. W. S. “Proactive topology reinforcement of wireless networks,” in Proc. of IEEE WCNC 2007 3789 - 3794
Dai L. L. , Chan V. W. S. “Helper node trajectory control for connection assurance in proactive mobile wireless networks,” in Proc. of ICCCN 2007 882 - 887
Mei Y. , Xian C. , Das S. , Hu Y. C. , Lu Y. 2007 “Sensor replacement using mobile robots,” Computer Communication 30 (13) 2615 - 2626    DOI : 10.1016/j.comcom.2007.05.047
Fall K. “A delay-tolerant network architecture for challenged internets,” in Proc. of the ACM SIGCOMM 2003 27 - 34
Handorean R. , Gill C. , Roman G.-C. 2004 “Accommodating transient connectivity in ad hoc and mobile settings,” Lecture Notes in Computer Science 305 - 322
Jain S. , Fall K. , Patra R. “Routing in a delay tolerant network,” in Proc. of the ACM SIGCOMM 2004 145 - 158
Vahdat A. , Becker D. 2000 “Epidemic routing for partially-connected ad hoc networks,” Duke University TR CS-2000-06
Guo X. F. , Chan M. C. “Plankton: an efficient DTN routing algorithm,” in Proc. of IEEE SECON 2013 550 - 558
Li Y. , Qian M. , Jin D. , Hui P. , Wang Z. , Chen S. 2014 “Multiple mobile data offloading through disruption tolerant networks,” IEEE Transactions on Mobile Computing 13 (7) 1579 - 1596    DOI : 10.1109/TMC.2013.108
Burns B. , Brock O. , Levine B. N. 2008 “Mora routing and capacity building in disruption-tolerant networks,” Ad Hoc Networks 6 (4) 600 - 620    DOI : 10.1016/j.adhoc.2007.05.002
Dang H. , Wu H. 2010 “Clustering and cluster-based routing protocol for delay-tolerant mobile networks,” IEEE Transactions on Wireless Communication 9 (6) 1874 - 1881    DOI : 10.1109/TWC.2010.06.081216
Bromage M. K. , Koshimoto J. T. , Obraczka K. “TAROT: Trajectory-assisted routing for intermittently connected networks,” in Proc. of ACM Workshop on Challenged Networks 2009 9 - 17
Zhao W. , Ammar M. , Zegura E. “Controlling the mobility of multiple data transport ferries in a delay-tolerant network,” in Proc. of IEEE Infocom 2005 1407 - 1418
Tariq M. M. B. , Ammar M. , Zegura E. “Message ferry route design for sparse ad hoc networks with mobile nodes,” in Proc. of ACM MobiHoc 2006 37 - 48
Li Y. , Jin D. , Su L. , Zeng L. , Wu D. 2012 “Optimal mobility control with energy constraint in delay tolerant networks,” Wireless Communications and Mobile Computing 14 (10) 949 - 962    DOI : 10.1002/wcm.2247
Li Q. , Rus D. 2003 “Communication in disconnected ad hoc networks using message relay,” Journal of Parallel Distributed Computing 63 75 - 86    DOI : 10.1016/S0743-7315(02)00033-3
Aschenbruck N. , Gerhands-Padilla E. , Martini P. 2008 “A survey on mobility models for performance analysis in tactical mobile networks,” Journal of Telecommunication and Information Technology 2 54 - 61
Xie L. F. , Chong P. H. J. , Guan Y. L. , Ng B. C. “G-ER: group-epidemic routing for mobile ad hoc networks with buffer sharing mechanism,” in Proc. of IWCMC 2011 2237 - 2242
Hong X. , Gerla M. , Pei G. , Chiang C. “A group mobility model for ad hoc wireless networks,” in Proc. of the ACM MSWiM 1999 53 - 60
Camp T. , Boleng J. , Davies V. 2002 “A survey of mobility models for ad hoc network research,” Wireless Communications and Mobile Computing 2 (5) 483 - 502    DOI : 10.1002/wcm.72
Groenevelt R. , Nain P. , Koole G. 2005 “The message delay in mobile ad hoc networks,” Performance Evaluation 62 210 - 228    DOI : 10.1016/j.peva.2005.07.018
Small T. , Haas Z. J. “The shared wireless infostation model - a new ad hoc networking paradigm,” in Proc. of the ACM MobiHoc 2003 233 - 244
Zhang X. , Neglia G. , Kurose J. , Towsley D. 2007 “Performance modeling of epidemic routing,” Computer Networks 51 (10) 2867 - 2891    DOI : 10.1016/j.comnet.2006.11.028
Lin Y. , Li B. , Liang B. 2008 “Stochastic analysis of network coding in epidemic routing,” IEEE Journal on Selected Areas in Communications 26 (5) 794 - 808    DOI : 10.1109/JSAC.2008.080606