Cost-efficient dynamic quota-controlled routing in multi-community delay-tolerant networks

Abstract

Delay-tolerant networks are novel wireless mobile networks, which are characterized with high latency and frequent disconnectivity. Besides, people carrying mobile devices form a lot of communities because of similar interests and social relationships. How to improve the routing efficiency in multi-community scenarios has become one of the research hot spots in delay-tolerant networks. In this article, we present a network model of the multi-community delay-tolerant networks and formulate a dynamic quota-controlled routing problem of minimizing the average number of copies of a message that satisfies the required delivery probability under the given time-to-live of the message as a nonlinear optimization problem. To solve this problem, we propose an improved genetic algorithm called genetic algorithm for delivery probability and time-to-live optimization for the dynamic quota-controlled routing scheme to reduce the routing cost further. In addition, a cost-efficient dynamic quota-controlled routing protocol based on genetic algorithm for delivery probability and time-to-live optimization is proposed, which can dynamically adjust message copies according to its assigned delivery probability and time-to-live in different communities on the shortest path. Both the numerical and simulation results show that our routing with the proposed algorithm is more cost efficient.

Introduction

Delay-tolerant networks ¹ (DTNs) are wireless mobile networks, in which mobile carriers (e.g. human beings) communicate with each other via their short-distance and low-cost devices to share data objects. ² DTNs can be used in challenging environments such as wireless sensor networks, military networks, vehicular ad hoc networks, wildlife tracking, and space communications.^3,4 Unlike conventional mobile networks such as mobile ad hoc networks, intermittent and uncertain connectivity makes data forwarding a challenging issue in DTNs, and thus the store-carry-forward strategy is often adopted in DTNs’ routing protocols in order to overcome the lack of connectivity. ⁵

Lots of DTN routing protocols have been proposed. Direct delivery ⁶ and epidemic ⁷ routings are viewed as the two extreme routing schemes, since the former scheme keeps only one copy and the latter does not limit the number of copies of a message in the network. To obtain a better tradeoff between performance and resource consumption in DTNs, routing protocols with quota-controlled scheme are proposed, in which each newly generated message is associated with a quota to constrain the maximal number of copies of a message that can be duplicated during the process of message delivery. The quota-controlled routing scheme can be further divided into static (e.g. spray and wait ⁸ ) and dynamic (e.g. multi-period S&W ⁹ and delay-bounded S&W ¹⁰ ) according to whether the quota is fixed or adjustable while routing a message. It is shown that the dynamic quota-controlled routing protocols can adapt the dynamic characteristic of DTNs and have more efficient utilization of the network resources by theoretical analysis and experimental results.

Meanwhile, in DTNs, portable devices are in the majority carried or controlled by humans. ¹¹ Therefore, when we design a routing protocol, human mobility patterns are needed to be considered. Recently, a large number of routing protocols, which exploit the community structure of human networks and social relations among nodes to determine the way of message delivery, are presented.^12–20 SimBet ¹² adopts the betweenness centrality and similarity metrics to determine the message forwarders. In Bubble Rap ¹³ , a node forwards the message to the encountered nodes with higher global or local degree centrality. Social- and mobile-aware routing strategy (SMART) ¹⁴ applies the convolution of social centrality and social similarity to decide forwarding node efficiently while avoiding the blind-spot and dead-end problems. Gondaliya et al. ¹⁵ proposed an approach to schedule relay nodes based on the two centralities of betweenness and degree in the absence of the community information about the destination. Nevertheless, all these routing protocols adopt the single-copy forwarding scheme, which limits the message delivery ratio. Integrating forwarding and replication (IFR) ¹⁶ uses message replication and forwarding for intra- and inter-community communication, respectively. Friendship-based routing (FBR) ¹⁷ exploits the periodically differentiated friendships to find the community and adopts the quota-controlled routing scheme inside a community. Although several heuristic methods were presented in IFR and FBR, the routing optimization problem in community-based DTNs was not considered yet. Homing spread (HS) ¹⁸ is a zero-knowledge multi-copy routing algorithm, which utilizes community homes to spread messages. The optimization objective of HS is to minimize the delivery delay for a given number of message copies. Community-based adaptive spray (CAS) ¹⁹ uses the community topology to pre-compute the multi-hop shortest path from the current community to the destination community and allocates the optimal quota at each hop adaptively. The goal of this protocol is to allocate the minimum number of message copies for a message while still achieving a high delivery ratio. Wu et al. ²⁰ developed a performance model of multi-community epidemic routing with social selfishness and proposed an energy-efficient copy-limit-optimized algorithm. However, to the best of our knowledge, none of them studied the cost efficiency of the dynamic quota-controlled routing in the multi-community DTNs. Hence, the performance of community-based routing still needs to be improved considering the dynamic nature of DTNs.

In order to obtain a balance between performance and cost of message delivery, in this article, we use the multi-community DTN model similar to that in CAS. ¹⁹ However, instead of the static quota-controlled routing adopted in CAS, we apply the dynamic quota-controlled routing (e.g. 2-period S&W) in each community on the shortest path to improve the cost efficiency further. In addition, we present a new cost optimization problem to minimize the dynamic quota and at the same time achieve a required delivery probability of the end-to-end multi-hop routing, which is more comprehensive than that of CAS. To solve the optimization problem, we propose an improved genetic algorithm (GA), which is more general and efficient than the enumeration algorithm used in CAS.

The main contributions of this article are as follows:

1. A network model of the multi-community DTNs is presented in this article. Based on this model, we formulate a dynamic quota-controlled routing problem of minimizing the average number of copies of a message that satisfies the required delivery probability under the given time-to-live (TTL) of the message as a nonlinear optimization problem.

2. An improved GA called genetic algorithm for delivery probability and time-to-live optimization (GAPTO) is proposed to solve this problem in the multi-community DTNs by means of several new evolutionary policies.

3. A cost-efficient community-based dynamic quota-controlled routing protocol with our optimization algorithm is proposed, which adopts 2-period S&W and can dynamically adjust message copies according to its assigned delivery probability and TTL in different communities on the shortest path. Both the numerical and simulation results show that the routing protocol with our algorithm has more significant advantages in cost efficiency.

Related work

There are various classifications of routing algorithms for DTNs, which usually are divided into two categories: forwarding based and replication based. Forwarding-based protocols, such as direct delivery, ⁶ SimBet, ¹² and minimum estimated expected delay (MEED), ²¹ keep only one copy per message in the network and route message in the network hop by hop to the destination. Although they can save buffer space and network bandwidth, they often suffer from low delivery ratio in DTNs due to the single copy. On the contrary, replication-based protocols distribute multiple copies of a message into the network, which can be further divided into flooding-based and quota-controlled protocols. Epidemic routing ⁷ is a typical example of flooding-based routing algorithms. It distributes the copies of each message to as many nodes as possible, which makes it unpractical for resource-constrained devices in DTNs. To address the problem of epidemic routing, quota-controlled protocols were proposed in many papers. In early times, the quota, that is, the maximal number of copies of a message, is static or fixed. However, due to the dynamic nature of DTNs, several routings with dynamic quota control schemes were proposed to achieve a better tradeoff between performance and resource consumption.

Spray and wait (S&W) ⁸ is a well-known static quota-controlled protocol. In S&W, a new message initially starts with a fixed value of quota and then it is delivered in two phases: spray and wait. In the spray phase, a binary quota allocation scheme is usually adopted, which allocates half of the quota from the current message to the replication of the message. If the destination node is not found in the spray phase, the routing process will enter the wait phase, where each node carrying a copy of the message performs direct transmission (i.e. forwards the message only to its destination). However, the fixed quota of message copies cannot suit the dynamic environment of DTNs very well. Therefore, protocols based on dynamic quota control scheme were proposed. Bulut et al. ⁹ proposed a dynamic quota-controlled routing protocol named multi-period S&W, which partitions the delivery time deadline into several predefined, variable-length periods, each composed of a spraying phase followed by the wait for delivery. In each period, the source node sets a certain quota for the message. When the message is delivered to the destination node, the destination node will send an acknowledgment message to the source node with epidemic routing. During the current period, if the source node does not receive the acknowledgment message, an additional quota of the message is provided properly for the next period. It has been shown that the average number of copies of multi-period S&W is smaller than that of the original S&W protocol with the same required delivery ratio and deadline. Moreover, Abbas et al. ¹⁰ proposed a delay-bounded S&W protocol, which dynamically adjusts the quota of messages based on the measured delivery probability and TTL of messages.

In the research of the characteristics of human mobility, human movement is shown to be driven by personal interests and social relationships. ²² Hence, the nodes which frequently coexist in a common location are considered to consist of a community. Recently, the utilization of community structure has been proved to improve the routing performance in DTNs. ²³ Therefore, many community-based routing protocols were proposed. Daly and Haahr ¹² proposed SimBet, which adopts the betweenness centrality and similarity metrics (a measurement of the importance of a node in a network) to determine the forwarders and introduces a tunable parameter to adjust the relative importance of two metrics. Hui et al. ¹³ evaluated the impact of community and centrality on forwarding, and proposed a hybrid algorithm, Bubble Rap, which selects high-centrality nodes and community members of destination as relays. Zhu et al. ¹⁴ proposed SMART, which exploits a heuristic method for community detection and then applies a decayed routing metric convoluting social similarity and social centrality to decide forwarding node efficiently while avoiding the blind-spot and dead-end problems. Gondaliya et al. ¹⁵ proposed a simple approach, which can schedule the most globally central nodes for message transmission based on the two centrality measures: betweenness and degree when community information about message’s destination is not available. Nevertheless, all these routing protocols adopted the single-copy forwarding schemes. As mentioned above, although saving network resources, the single-copy forwarding schemes often suffer from low message delivery ratio in DTNs. Hence, Li et al. ¹⁶ proposed a community-based routing protocol, called IFR, which allows a node to replicate message in the same community and to forward message outside the community according to the delivery weight obtained from the centrality of the node. The difference between IFR and Bubble Rap is that IFR floods a message inside the community of the destination node rather than a single copy in Bubble Rap. Bulut et al. ¹⁷ presented FBR, in which periodically differentiated friendship relations are used in detecting the community and forwarding of messages. For intra-community communication, FBR sprays several copies of messages to a number of nodes in the community. For inter-community communication, the data are forwarded only when the destination is in the same periodical community as the relay. But the presented routing methods are only heuristic in IFR and FBR, which did not consider the routing optimization problem in community-based DTNs to improve their performance. Xiao et al. ¹⁸ proposed a novel zero-knowledge multi-copy routing algorithm named homing spread (HS) for mobile social networks, in which all mobile nodes share all community homes. HS mainly lets community homes spread messages with a higher priority. Theoretical optimization and analysis showed that HS can spread a given number of message copies with the minimum expected delivery delay. Miao et al. ¹⁹ proposed CAS routing protocol, which uses the community topology to pre-compute the multi-hop path that is the shortest path from the current community to the community of the destination node. In CAS, the optimal quota on each hop is computed under the message TTL and a predefined expected delivery ratio with an enumeration method. Wu et al. ²⁰ proposed a performance model of multi-community epidemic routing with social selfishness with ordinary differential equations (ODEs) and an energy-efficient copy-limit-optimized algorithm, which is designed to determine the optimal copy limit in multiple communities for epidemic routing. However, all of them utilized the static quota-controlled routing schemes (e.g. S&W and copy-limited epidemic), which usually lead to worse cost efficiency than the dynamic ones.

In this article, we study the cost-efficient dynamic quota-controlled routing in the multi-community DTNs and address the optimization problem of minimizing the average number of copies of a message that satisfies the required delivery probability under the given lifetime of the message. Although our model is similar to that in CAS, ¹⁹ our work is different mainly in three ways. First, the routing protocol we adopt in the multi-community DTNs is dynamic quota controlled, while CAS adopts the static quota-controlled routing in a community though it re-allocates the quota at each hop. Second, the optimization problem we present is more comprehensive, which is able to express the minimum cost of the dynamic quota-controlled routing and the required delivery ratio of the end-to-end multi-hop routing. On the contrary, CAS is just suitable for static routing and the delivery ratio of one hop. Third, CAS uses the enumeration algorithm that is poorer in scalability, but we adopt a more general and efficient algorithm, that is, GA, to solve the optimization problem.

System model

In our model of DTNs, we partition the nodes into multiple nonoverlapping communities and assume that there are $n$ communities and any community $i$ is denoted by $C_i$ , $i\in [1,n]$ . Moreover, each community $C_i$ has $\left|C_i\right|$ nodes in it. It needs to be pointed out that the multiple communities in practice can overlap, that is, a node can belong to more than one community. However, for simplicity and abstraction of our model, we assume in this article that these communities have no overlap, which is also assumed in some related work.^13,19 We also assume that the nodes move according to the random waypoint (RWP) mobility model, which is widely applied in the research of mobile and wireless networks as a good abstraction of realistic movement scenarios, ²⁴ and the occurrence of the contacts between any two nodes follows a Poisson process which has been validated. ²⁵ Because nodes in the same community meet each other with high frequency, while nodes belonging to different communities merely meet each other, in our model, we assume that the nodes in the same community have the same average inter-contact time with each other and the average contact rate in $C_i$ is denoted as ${\lambda }_i$ . Such an assumption is a reasonable approximation in modeling and also adopted in previous work.^18–20 In view of the whole network, we model that the communities $C_i$ and $C_j$ communicate only via a pair of nodes, which are the most closely related nodes between the two communities and called the gateway nodes of the communities $C_i$ and $C_j$ . Then we can denote ${\lambda }_{\mathrm{ij}}$ as the average contact rate between the communities $C_i$ and $C_j$ , which is equal to the average contact rate between the gateway nodes of the communities $C_i$ and $C_j$ . Moreover, we note that different communities communicate via different pairs of gateway nodes. Our model of the multi-community DTNs is shown in Figure 1.

Figure 1.

Model of multi-community DTNs.

We now analyze the message forwarding process. As shown in Figure 1, when the source node $S$ , which is in the community $C_s$ , generates a message and wants to send the message to the destination node $D$ in the community $C_d$ . In our network model, it is possible that there exists more than one path from the community $C_s$ to the community $C_d$ . Then, the question is how to find the shortest path. From Figure 1, the multi-community DTNs can be viewed as a weighted undirected graph (WUG) in which a vertex represents a community and an edge represents a link between two communities. The weight of the link between $C_i$ and $C_j$ , denoted as $W_{\mathrm{ij}}$ , is given by equation (1)

$$W_{\mathrm{ij}}=\frac{1}{{\lambda }_{\mathrm{ij}}}$$

(1)

where W_ij is the weight in the WUG, which is used to compute the shortest path, and $1/{\lambda }_{\mathrm{ij}}$ represents the average inter-contact time between the communities $C_i$ and $C_j$ . Considering that the average inter-contact time between different communities is far greater than that in the same community, here we use only $1/{\lambda }_{\mathrm{ij}}$ to represent the weight.

Based on the WUG, the shortest path $R$ from the source to the destination can be obtained by Dijkstra’s algorithm. For the sake of clarity and without loss of generality, let us assume that the communities on the path $R$ are $<C_1,C_2,\dots ,C_k>$ sequentially, the source node $S$ and the destination node $D$ are in the communities $C_1$ and $C_k$ , respectively, and $k$ is the total number of hops of the path $R$ .

According to the path $R$ , at the beginning, the source node $S$ should deliver the message to the gateway node in the community $C_1$ , which connects the communities $C_1$ and $C_2$ . After that, when the gateway node in $C_1$ encounters the gateway node in $C_2$ , the message is forwarded to the community $C_2$ . Then, the gateway node in $C_2$ becomes a new source node of the message, which will be delivered to the next community on the path $R$ . The process mentioned above will be repeated until the message is delivered to the destination node or its TTL expires.

As shown in Figure 1, the whole message forwarding process consists of a series of subprocesses, each of which is a complete message delivery in a community on the path $R$ . Therefore, we define $P=(p_1,p_2,\dots ,p_k)$ and $T=(t_1,t_2,\dots ,t_k)$ to be the delivery probability-limit vector and TTL-limit vector for all communities on the path $R$ , respectively. Since different delivery probability- and TTL-limit vectors lead to different message delivery costs. If we want to deliver a message from the source node $S$ to the destination node $D$ with minimum cost and meet the desired delivery probability $P_0$ before the restricted lifetime of message $T_0$ at the same time, a reasonable allocation method of the limitation of the delivery probability and TTL for communities on the path $R$ is necessary. Based on the considerations above, we can formulate the optimization problem for delivery probability-limit vector $P$ and TTL-limit vector $T$ as

$$\begin{array}{cc}min\hfill & \mathrm{Cost}(P,T)\hfill \\ \multicolumn{1}{c}{s.t.}& \{\begin{array}{c}\mathrm{Ratio}(P)\ge P_0\hfill \\ \multicolumn{1}{c}{\mathrm{Time}(T)\le T_0}\end{array}\hfill \end{array}$$

(2)

where

$$\mathrm{Ratio}(P)=\underset{i=1}{\overset{k}{\Pi }}{p}_i$$

(3)

$$\mathrm{Time}(T)=\sum _{i=1}^k{t}_i+\sum _{i=1}^{k-1}\frac{1}{{\lambda }_{i,i+1}}$$

(4)

$$\mathrm{Cost}(P,T)=\sum _{i=1}^k\mathrm{Cos}{t}_i(p_i,t_i)$$

(5)

As described previously, the message will be delivered by a series of subprocesses, which are the independent events in probability theory. Hence, the total delivery probability with the delivery probability-limit vector $P$ , that is, $\mathrm{Ratio}(P)$ , can be given by equation (3), which must be no less than $P_0$ as shown in equation (2).

Moreover, equation (4) represents the total time, that is, $\mathrm{Time}(T)$ , which is made up of the sum of the TTL components of the TTL-limit vector $T$ allocated to the message for different communities and the sum of the average inter-contact time between communities on the path $R$ , which must be no greater than $T_0$ as shown in equation (2).

Now, let us focus on the delivery cost. We assume that the delivery cost of the message in the community $C_i$ on the path $R$ is $\mathrm{Cost}(p_i,t_i)$ , $i\in [1,k]$ , which is determined by the values of $p_i$ and $t_i$ . Hence, the total delivery cost, denoted $\mathrm{Cost}(P,T)$ , of the message is determined by the delivery probability-limit vector $P$ and TTL-limit vector $T$ , which is the sum of the delivery cost in each community on the path $R$ as shown in equation (5).

In the static quota-controlled routing protocol, such as S&W, ⁸ if we assume that the source node is in the community $C_i$ (i.e. the source node of the message or the gateway node which connects the communities $C_{i-1}$ and $C_i$ ) and $L_i$ is the minimum value of the quota, which can achieve the delivery ratio $p_i$ before TTL $t_i$ , $L_i$ can be obtained by the following equation ⁹

$$L_i=\frac{\ln (1-p_i)}{{\lambda }_i{t}_i}$$

(6)

Then we can have the minimum delivery cost in the community $C_i$ with S&W algorithm as

$$\mathrm{Cos}{t}_i(p_i,t_i)=L_i$$

(7)

In order to optimize the cost efficiency of the routing further, in this article, we use the dynamic quota-controlled routing protocol, such as multi-period S&W, ⁹ since the dynamic routing protocol can achieve lower delivery cost than the static routing protocol as we discussed above. Specifically, we will use 2-period S&W algorithm in our model, because the simulation results show that 2-period S&W algorithm is very easy to be implemented and the performance of it is nearly as good as that of other multi-period algorithms in general. ⁹

In 2-period spraying algorithm, the source node in the community $C_i$ sets the quota of a message to be $L_{1i}$ at the beginning. When the gateway node in the community $C_i$ which connects the communities $C_i$ and $C_{i+1}$ or the destination node receives any copy of the message, it will send an acknowledgment message with epidemic routing to all other nodes notifying them to stop the further spray. If the source node does not receive any acknowledgment of the message at time $t_{\mathrm{di}}$ , it will increase additional quota $L_{2i}-L_{1i}$ of the message for the 2nd period of spray. The optimal values of $L_{1i}$ , $L_{2i}$ , and $t_{\mathrm{di}}$ can be calculated according to $p_i$ and $t_i$ under the assumption of $L_{1i}<L_{2i}<<\left|C_i\right|$ , which is reasonable in DTNs. ⁹

Hence, we can have the minimum delivery cost in the community $C_i$ with 2-period S&W algorithm as

$$\mathrm{Cos}{t}_i(p_i,t_i)=L_{1i}{p}_{\mathrm{di}}+L_{2i}(1-p_{\mathrm{di}})$$

(8)

where

$$p_{\mathrm{di}}=1-e^{-{\lambda }_i{L}_{1i}{t}_{\mathrm{di}}}$$

(9)

Algorithm design

The problem described in equations (2)–(5) can be regarded as a nonlinear constrained optimization problem. As discussed above, we should choose the appropriate delivery probability-limit vector $P$ and TTL-limit vector $T$ , with which the delivery cost is minimum and the inequality constraints are incorporated at the same time. However, most traditional optimization algorithms usually achieve a local optimal solution rather than the global optimal solution, which cannot effectively solve this kind of optimization problem. Thus, in this article, we consider an appropriate evolutionary method to solve it.

During the past two decades, GAs have been successfully and broadly applied to solve constrained optimization problems. ²⁶ Hong et al. ²⁷ observed that in most GA variants only crossover and mutation operators are employed in each generation. As a result, the search ability of these algorithms could be limited. Hence, they improved the algorithm efficiency by means of adding the best preserving policy, an elitism-based immigrant policy and improving the traditional training process of the GA to overcome these drawbacks. In this article, we will use this improved GA and propose an algorithm called GAPTO to solve the optimization problem in equations (2)–(5).

The details of the algorithm are described as follows.

Representation and initialization

In this article, we denote the $j\mathrm{th}$ chromosome in the current population as

$$\begin{array}{l}{H}_j=(P_j,T_j)\\ =((p_{1j},p_{2j},\dots ,p_{kj}),(t_{1j},t_{2j},\dots ,t_{kj})),j\in [1,m]\end{array}$$

(10)

where $m$ is the maximum number of chromosomes in a generation, and $p_{\mathrm{ij}}$ and $t_{\mathrm{ij}}$ , $i\in [1,k]$ , represent the required delivery ratio $p_i$ and message TTL $t_i$ allocated to the community $C_i$ in $H_j$ , respectively.

Then the initialization operation generates $m$ chromosomes randomly, of which the genes, $p_{\mathrm{ij}}$ and $t_{\mathrm{ij}}$ , are directly coded within their corresponding bounds

$$\{\begin{array}{c}{p}_{\mathrm{ij}}=P_0+\sigma (1-P_0)\hfill \\ \multicolumn{1}{c}{t_{\mathrm{ij}}=\sigma T_0}\end{array}$$

(11)

where $\sigma$ is a uniform random number between 0 and 1.

Afterward, we check whether the chromosome $H_j$ satisfies the inequality constraints in equation (2). If not, a new chromosome $H_j$ is regenerated by equation (11) and checked until the constraints are satisfied. After the initialization operation, we obtain $m$ feasible chromosomes. This operation ensures that the optimization starts in a feasible region, which can predigest the calculation and decrease the search pressure.

Fitness function

Although the initial chromosomes are all feasible after initialization, $H_j$ sometimes may not satisfy the inequality constraints in equation (2) during the subsequent genetic operations, for example, crossover and mutation operations. Therefore, a penalty function is needed to convert the nonlinear constrained optimization into an unconstrained optimization problem based on equation (2). In addition, considering the difference range of $\mathrm{Ratio}(P_j)$ and $\mathrm{Time}(T_j)$ , a normalization method is necessary to normalize them to the range between 0 and 1. In this way, all terms of the fitness function will be in the same order, which can speed up the convergence. Finally, the fitness function $\mathrm{Fit}(H_j)$ with the objective function $\mathrm{Cost}(H_j)$ and the penalty function $G(H_j)$ is defined as

$$\mathrm{Fit}(H_j)=\mathrm{Cost}(H_j)+G(H_j)$$

(12)

where

$$\begin{array}{c}\multicolumn{1}{c}{G(H_j)=\mu \{max[{\left(\frac{P_0}{\mathrm{Ratio}(P_j)}\right)}^{\eta }-1,0]}\\ \multicolumn{1}{c}{+max[{\left(\frac{T_0}{2T_0-\mathrm{Time}(T_j)}\right)}^{\eta }-1,0]\}}\end{array}$$

(13)

where $\mu (\mu >0)$ and $\eta (\eta >1)$ are the penalty factors.

From equation (13), we can find that the ranges of $P_0/\mathrm{Ratio}(P_j)$ and $T_0/(2T_0-\mathrm{Time}(T_j))$ are normalized between 0 and 1. The penalty factor $\mu$ is used to unify the objective function and penalty function into the same order. According to the penalty factor $\eta$ , when $\mathrm{Ratio}(P_j)$ and $\mathrm{Time}(T_j)$ do not satisfy the constraint conditions in equation (2), $G(H_j)$ will get a large value. Clearly, the fitness function $\mathrm{Fit}(H_j)$ will reach the minimum optimization point only when $G(H_j)=0$ . That is, all genes of the chromosome $H_j$ will be in the feasible region.

Crossover operator

In order to increase the local diversity of crossover chromosomes, $H_a$ and $H_b$ are selected randomly with the crossover probability $\alpha$ . Then we introduce a linear combination of $H_a$ and $H_b$ , and each gene of $H{\prime }_a$ and $H{\prime }_b$ are reproduced as follows

$$\{\begin{array}{c}{p\prime }_{\mathrm{ia}}=\sigma p_{\mathrm{ia}}+(1-\sigma )p_{\mathrm{ib}}\hfill \\ \multicolumn{1}{c}{{t\prime }_{\mathrm{ia}}=\sigma t_{\mathrm{ia}}+(1-\sigma )t_{\mathrm{ib}}}\\ \multicolumn{1}{c}{{p\prime }_{\mathrm{ib}}=\sigma p_{\mathrm{ib}}+(1-\sigma )p_{\mathrm{ia}}}\\ \multicolumn{1}{c}{{t\prime }_{\mathrm{ib}}=\sigma t_{\mathrm{ib}}+(1-\sigma )t_{\mathrm{ia}}}\end{array}$$

(14)

Mutation operator

Let the current best chromosome be $H_e$ , which has the minimum fitness. Then, we choose randomly a chromosome $H_f$ with the mutation probability $\beta$ . If the difference of $\mathrm{Fit}(H_e)$ and $\mathrm{Fit}(H_f)$ is less than ${10}^{-2}$ , which means that the population converges, we introduce a linear combination for $H_e$ and $H_f$ to obtain the mutation chromosome $H{\prime }_f$ . Each gene of $H{\prime }_f$ is reproduced as follows

$$\{\begin{array}{c}{p\prime }_{\mathrm{if}}=p_{\mathrm{ie}}+\sigma (p_{\mathrm{ie}}-p_{\mathrm{if}})\hfill \\ \multicolumn{1}{c}{{t\prime }_{\mathrm{if}}=t_{\mathrm{ie}}+\sigma (t_{\mathrm{ie}}-t_{\mathrm{if}})}\end{array}$$

(15)

Otherwise, if the current chromosomes $H_e$ and $H_f$ are obviously different, to avoid premature convergence, we choose $H_u$ and $H_v$ in the current population randomly. Then each gene of $H{\prime }_f$ is reproduced as follows

$$\{\begin{array}{c}{p\prime }_{\mathrm{if}}=p_{\mathrm{if}}+\sigma (p_{\mathrm{ie}}-p_{\mathrm{if}})+\sigma (p_{\mathrm{iu}}-p_{\mathrm{iv}})\hfill \\ \multicolumn{1}{c}{{t\prime }_{\mathrm{if}}=t_{\mathrm{if}}+\sigma (t_{\mathrm{ie}}-t_{\mathrm{if}})+\sigma (t_{\mathrm{iu}}-t_{\mathrm{iv}})}\end{array}$$

(16)

In equation (16), the difference of $H_e$ and $H_f$ and the difference of $H_u$ and $H_v$ act as two search directions in the solution space, which can try to cover more search space when the population is in a local minimum.

Migration operator

In order to greatly increase the exploration of the search space, we introduce the migration operation, in which chromosome is generated on the basis of the best chromosome $H_e$ . Then we choose the $w\mathrm{th}$ gene and the $z\mathrm{th}$ gene of $H_e$ with the migration probability $\chi$ . Then the new genes of $H{\prime }_e$ are reproduced as follows

$$p{\prime }_{\mathrm{we}}=\{\begin{array}{c}{p}_{\mathrm{we}}+\sigma (P_0-p_{\mathrm{we}}),\gamma <\frac{p_{\mathrm{we}}-P_0}{1-P_0}\hfill \\ \multicolumn{1}{c}{p_{\mathrm{we}}+\sigma (1-p_{\mathrm{we}}),\gamma \ge \frac{p_{\mathrm{we}}-P_0}{1-P_0}}\end{array}$$

(17)

$$t{\prime }_{\mathrm{ze}}=\{\begin{array}{c}(1-\sigma )t_{\mathrm{ze}},\gamma <\frac{t_{\mathrm{ze}}}{T_0}\hfill \\ \multicolumn{1}{c}{(1-\sigma )t_{\mathrm{ze}}+\sigma T_0,\gamma \ge \frac{t_{\mathrm{ze}}}{T_0}}\end{array}$$

(18)

where $\gamma$ is also a uniform random number between 0 and 1 as $\sigma$ .

This migration operator can adjust the value of a gene properly within its bounds. If the value approaches the upper boundary, this operator can pull back it from the upper boundary. On the contrary, if it nears the lower boundary, the value will be increased.

Select operator

Select $m-1$ members from the current population and add them to the next generation by roulette wheel election mechanism. Moreover, elitism strategy is embedded into the select operator, which means that the best chromosome of the current generation will be reserved to the next generation.

The pseudo code of the proposed algorithm is shown in Algorithm 1. According to the algorithm, at first, $m$ chromosomes are generated randomly to construct the first generation with initialization operator (lines 3–8). Then the crossover (lines 10–13), mutation (lines 14–23), and migration (lines 24–28) operations are performed, respectively, and each of which is repeated $m$ times. Afterward, a new generation with $m$ chromosomes is generated using the selection operator (lines 29–32). After total generations of evolution, at last, we select the best chromosome and return the optimal delivery probability-limit vector $P^{*}$ and TTL-limit vector $T^{*}$ (lines 34–35).

Algorithm 1 Genetic algorithm for delivery probability and TTL optimization (GAPTO)

Input: $P_0$ , $T_0$ , $k$ , $\{{\lambda }_i\}$ , $\{{\lambda }_{\mathrm{ij}}\}$ , $m$ , $\mathrm{total}$ , $\alpha$ , $\beta$ , $\chi$ , $\mu$ , and $\eta$ Output: $P^{*}$ and $T^{*}$ 1: $\mathrm{gen}\leftarrow 1$ 2: for $j=1$ to $m$ do 3:  randomly generate a chromosome $H_j$ 4:  while $H_j$ is not satisfied the constraints in equation (2) do 5:   randomly generate a new chromosome $H_j$ 6:  end while 7: end for 8: $\mathrm{PO}{P}_{\mathrm{gen}}\leftarrow \left\{H_j\right\}$ 9: while $\mathrm{gen}\le \mathrm{total}$ do 10:  for $j=1$ to $m$ do 11:   select two chromosomes $H_a$ and $H_b$ with the crossover probability $\alpha$ 12:   generate $H{\prime }_a$ and $H{\prime }_b$ with crossover operator by equation (14) 13:  end for 14:  for $j=1$ to $m$ do 15:    $H_e$  ← the best chromosome 16:   randomly choose a chromosome $H_f$ with the mutationprobability $\beta$ 17:   if $\Vert \mathrm{Fit}(H_f)-\mathrm{Fit}(H_e)\Vert \le {10}^{-2}$ then 18:    generate $H{\prime }_f$ with mutation operator by equation (15) 19:   else 20:    randomly choose two chromosomes $H_u$ and $H_v$ 21:    generate $H{\prime }_f$ with mutation operator by equation (16) 22:   end if 23:  end for 24:  for $j=1$ to $m$ do 25:    $H_e$  ← the best chromosome 26:   randomly choose the $w\mathrm{th}$ gene and the $z\mathrm{th}$ gene of $H_e$ with the migration probability $\chi$ 27:   generate $H{\prime }_e$ with migration operator by equations (17) and (18) 28:  end for 29:   $H_e\leftarrow$ the best chromosome 30:  add $H_e$ to $\mathrm{PO}{P}_{\mathrm{gen}+1}$ 31:  select m–1 members of $\mathrm{PO}{P}_{\mathrm{gen}}$ to add to $\mathrm{PO}{P}_{\mathrm{gen}+1}$ by using roulette wheel selection mechanism 32: $\mathrm{gen}\leftarrow \mathrm{gen}+1$ 33: end while 34: $H_e$  ← the best chromosome 35: return $P^{*}\leftarrow P_e$ , $T^{*}\leftarrow T_e$

Implementation consideration

In this section, we have a discussion about the implementation of a dynamic quota-controlled routing protocol with GAPTO. Assume that all nodes know the network parameters, including the number of communities $n$ , average contact rate in communities $\{{\lambda }_i\}$ , average contact rate between communities $\{{\lambda }_{\mathrm{ij}}\}$ , desired delivery probability $P_0$ , message TTL $T_0$ , maximum number of chromosomes in a generation $m$ , total number of iterations $\mathrm{total}$ , crossover probability $\alpha$ , mutation probability $\beta$ , migration probability $\chi$ , penalty factors $\mu$ and $\eta$ . When a source node wants to send a message to a destination node, at first, the source node will find the shortest path based on the model of multi-community DTNs by Dijkstra’s algorithm, which is denoted as $<C_1,C_2,\dots ,C_k>$ . Then the source node runs Algorithm 1 to obtain the optimal delivery probability-limit vector $P^{*}$ and TTL-limit vector $T^{*}$ . After this, the message is generated and the corresponding vectors $P^{*}$ and $T^{*}$ are associated with it. During the routing, the source node or the gateway node in the communities $C_i(1\le i\le k)$ computes the values of $L_{1i}$ , $L_{2i}$ , and $t_{\mathrm{di}}$ as described previously. Afterward, the message will be forwarded by 2-period S&W routing protocol. That means the message will be forwarded in the community $C_i$ until it is delivered to the destination node or the gateway node which connects the communities $C_i$ and $C_{i+1}$ . Therefore, with the optimal vectors $P^{*}$ and $T^{*}$ , the routing protocol with GAPTO can maintain the desired delivery probability and minimize the delivery cost as excepted.

Performance evaluation

In this section, we first analyze the effect of the parameters of GAPTO. Afterward, the proposed protocol is evaluated through both numerical computation and simulation. At last, the performance comparison of GAPTO with the other two algorithms is made through theoretical results.

Effect of the parameters of GAPTO

We now analyze the delivery cost of GAPTO affected by the migration probability $\chi$ and the penalty factor $\eta$ . We assume that the number of communities on the shortest path $R$ , that is, $k$ , ranges from 2 to 16. And we set the average contact rate ${\lambda }_i$ in the community $C_i$ as follows

$${\lambda }_i=\frac{1}{{\tau }_0+({\tau }_1-{\tau }_0)\frac{i-1}{k-1}},1\le i\le k$$

(19)

where ${\tau }_0={10}^3\mathrm{s}$ and ${\tau }_1={10}^4\mathrm{s}$ , which means that the average inter-contact time in the community $C_i$ is different and between ${\tau }_0$ and ${\tau }_1$ . Moreover, the restricted lifetime of the message $T_0$ should be long enough to let equation (4) satisfy the TTL constraint in equation (2). Thus, $T_0$ is also set differently for different numbers of communities, that is, $T_0$ is set at $1.5\times {10}^4\mathrm{s}$ , $3.5\times {10}^4\mathrm{s}$ , $6.5\times {10}^4\mathrm{s}$ , and $1.25\times {10}^5\mathrm{s}$ for $k=2,4,8$ , and $16$ , respectively. we also set the desired delivery probability $P_0=0.8$ and the inter-community average contact rate ${\lambda }_{\mathrm{ij}}=1.996\times {10}^{-4}/\mathrm{s}(i\ne j)$ . In this article, we choose crossover probability $\alpha =0.8$ , mutation probability $\beta =0.6$ , and penalty factor $\mu =100$ based on our experiment and experience.

Figures 2 and 3 show the performance metrics in terms of the delivery cost versus migration probability $\chi$ and penalty factor $\eta$ with different $k$ values, respectively. From Figure 2, we can find that the smaller the $k$ is, the lower the delivery cost obtained. Because $T_0$ is made up of the sum of the TTLs allocated to the message in all communities and the sum of the average inter-contact time between communities on the shortest path $R$ according to equation (4). When $k$ is small, the sum of the average inter-contact time between communities on $R$ is relatively small. Then the source nodes or gateway nodes can set lower quotas with longer TTLs allocated to the message in the communities on $R$ under the same required delivery ratio. On the contrary, when $k$ increases, higher quotas are needed for shorter TTLs in the communities on $R$ . Let us focus on the migration probability $\chi$ . Although the population has a good stability due to no migration when $\chi$ is 0, it is easy to fall into a local optimum rather than the global optimum. When $\chi$ becomes larger, the stability is disrupted gradually, but the population diversity is ensured, which can avoid premature convergence. Thus, the delivery cost decreases when $\chi$ changes from 0 to 0.6. However, the performance of the delivery cost becomes worse again when $\chi$ is larger than 0.6 because of the slow convergence rate and the poor stability of population under larger $\chi$ . At that point, the excellent chromosome is likely to become worse in the process of migration. Therefore, the delivery cost increases. Considering that an appropriate $\chi$ can realize the parallel population diversity and selective pressure, we choose a value of $\chi =0.6$ in our algorithm.

Figure 2.

Delivery cost versus migration probability $\chi$ .

Figure 3.

Delivery cost versus penalty factor $\eta$ .

It can be seen from Figure 3 that the delivery cost is the minimum when the penalty factor $\eta$ is around 4.0 for different $k$ values. When $\eta$ is 0, there is no punishment on the fitness function in equation (12). As a result, those chromosomes not in the feasible domain may be reserved, and a large amount of search time will be spent in the infeasible domain. Thus, the solution may be a local optimum. When $\eta$ increases, the strength of the punishment increases and more feasible domain is covered. This makes the solution jump from the local optimum and guides the search in promising directions. Therefore, the delivery cost approaches the global optimal value gradually. However, when $\eta$ is more than 4.0, the punishment becomes too strong. Once a few genes of a chromosome are out of the feasible domain, the chromosome will be eliminated completely, which tends to decrease the search space and ignore the boundary of the feasible region. Thus, GAPTO cannot guarantee to find the optimal value, then the solution becomes worse again. To ensure the reasonable search space, $\eta$ is chosen as 4.0 in this article.

Numerical and simulation evaluation

In order to validate the proposed protocol in section “Implementation consideration,” we evaluate our protocol via both numerical computation and extensive simulation by MATLAB ²⁸ and the ONE simulator, ²⁹ respectively. In the simulation, the whole terrain is divided into different regions to form different communities. Besides, by changing the velocity of nodes in different communities, we can obtain the different average contact rates ${\lambda }_i$ in different communities. The settings of the simulation parameters are shown in Table 1. Transmission speed and buffer size were sufficiently large to ignore the queuing effects, and the acknowledgment message size is so small that its cost can be ignored. Then, we set the inter-community average contact rate ${\lambda }_{\mathrm{ij}}=1.996\times {10}^{-4}/\mathrm{s}(i,j\in [1,k],i\ne j)$ , $P_0=0.8$ , and $k$ from 4 to 6.

Table 1.

Simulation parameters.

Parameter	Value
Mobility model	Random waypoint
Terrain size	4000 m × 4000 m
Velocity of nodes in communitieson the path $R$	4~10 m/s
Number of nodes in each communityon the path $R$	400
Transmission range	50 m
Transmission speed	2 MB/s
Message size	8 KB
Acknowledgment message size	2 bytes
Buffer size	500 MB

Figures 4–6 plot the performance metrics of the proposed protocol obtained by the numerical computation and simulation. It can be seen that all the results of the numerical computation are consistent with those of the simulation very well.

Figure 4.

Delivery cost versus $T_0$ with different $k$ .

Figure 5.

Delivery probability versus $T_0$ with different $k$ .

Figure 6.

Delivery delay versus $T_0$ with different $k$ .

Figure 4 shows the delivery cost versus the message TTL $(T_0)$ with different number of communities $(k)$ . It can be seen that the delivery cost increases with the increased $k$ under a given $T_0$ . The reason is the same as above, that is, the smaller the TTL allocated to the message in a community, the larger the quota that will be set in order to satisfy the requirement of delivery probability. Moreover, the simulated cost of the proposed protocol is slightly high compared to the numerical results. This is because the routing of the acknowledgment message adopts epidemic routing. In our simulation, the effect of the acknowledgment delay can be observed, which makes the process of the spray stop later and more copies of the message to be sprayed into the network. However, the gap between the numerical and simulated results will be narrowed when $T_0$ becomes large.

Figures 5 and 6 show the delivery probability and delivery delay versus $T_0$ with different $k$ values, respectively. It can be seen from Figure 5 that our protocol can achieve the desired delivery probability as we expect, which verifies the validity of our proposed protocol. In Figure 6, the delivery delay increases as $T_0$ increases. This is because our protocol is optimized for the minimum cost. When $T_0$ increases, our protocol can set smaller quota to satisfy the same $P_0$ , which leads to the increase of the delivery delay. In addition, we observe that the delivery delay increases with decreasing $k$ when $T_0$ is the same, because the smaller the $k$ value is, the longer the TTL and the lower the quota that are allocated to the message. Similarly, because of the aforementioned reason, the delivery delay increases.

Comparison with different algorithms

To evaluate the performance of GAPTO further, we compare GAPTO with the other two algorithms, proportional allocation algorithm (PAA) and random allocation algorithm (RAA), which are only different in the allocation algorithm for the delivery probability-limit vector $P$ and TTL-limit vector $T$ .

Under the condition of satisfying the constraints in equation (2), in PAA, the assigned values of $p_i$ in $P$ are directly proportional to ${\lambda }_i$ , while $t_i$ in $T$ are inversely proportional to ${\lambda }_i$ , $i\in [1,k]$ .

In RAA, the values of $p_i$ in $P$ and $t_i$ in $T$ are chosen randomly under the constraints in equation (2), $i\in [1,k]$ .

Since the results of theory and simulation show good coherence in Figures 4–6, for convenience, the comparison is analyzed on the basis of numerical results by MATLAB. Let $P_0$ , $T_0$ , ${\lambda }_i$ , ${\lambda }_{\mathrm{ij}}(i\ne j)$ be the same as those in section “Effect of the parameters of GAPTO.” We can calculate the delivery cost and delivery delay with different algorithms under different $k$ and $T_0$ values. Then the results are shown in Figures 7 and 8.

Figure 7.

Delivery cost versus $k$ with different algorithms.

Figure 8.

Delivery delay versus $k$ with different algorithms.

From Figure 7, it can be seen that GAPTO always achieves the minimum delivery cost, because GAPTO not only retains the advantages of traditional genetic method, but also has better convergence and higher search efficiency, which is commonly used to generate high-quality solutions to optimization problems. On the contrary, RAA is always the worst in these three algorithms, because the results of RAA have the characteristics of randomness. PAA can also achieve a good result since there is a little difference of delivery cost between PAA and GAPTO. However, the difference becomes obvious when $k$ increases. Besides better performance, GAPTO is more general and has a wider range of applications than PAA.

Figure 8 shows the delivery delay versus $k$ with different algorithms. It can be seen that the delivery delay of these three algorithms is similar to each other. Considering the delivery cost in Figure 7, we can find that GAPTO is the most efficient.

Moreover, to present the advantages in cost efficiency of the dynamic to the static quota-controlled routings, we compare GAPTO for 2-period S&W protocol against GAPTO for the original S&W protocol, which are called GAPTO and GAPTO_static, respectively. The only difference between GAPTO and GAPTO_static is the expression of the minimum delivery cost according to our system model.

Figure 9 shows the delivery cost of the compared routing protocols. Clearly, the delivery cost of GAPTO is about 30% less than that of GAPTO_static. Thus, the cost efficiency of the dynamic quota-controlled routing is validated again. In addition, from Figure 10, we can see that the delivery cost of GAPTO is higher than that of GAPTO_static. This is because there usually exists a tradeoff between delivery cost and delay in DTNs. In this article, our focus is on minimizing the delivery cost and just limiting the delivery delay within the required TTL. Hence, the dynamic quota-controlled routing protocol is more cost efficient.

Figure 9.

Delivery cost versus $k$ with different protocols.

Figure 10.

Delivery delay versus $k$ with different protocols.

Conclusion

In this article, we present a network model in the multi-community DTNs and apply the dynamic quota-controlled routing scheme into the model. Based on this, we formulate a routing problem of minimizing the delivery cost that satisfies the required delivery probability under the given TTL of message as a nonlinear optimization problem. Then we propose GAPTO and a cost-efficient dynamic quota-controlled routing protocol, which is based on GAPTO. The results of both numerical computation and simulation demonstrate the cost efficiency improvement of the proposed protocol. In the future, we are going to extend the network model and study our protocol under different mobility scenarios and heterogeneous communities.