Robust load-balanced backbone-based multicast routing in mobile opportunistic networks

Abstract

Mobile opportunistic network (MON) is an efficient way of communication when there is no persistent connection between nodes. Multicast in MONs can be used to efficiently deliver messages to multiple destination nodes. However, because multiple destination nodes are involved, multicast routing is more complex than unicast and brings a higher communication cost. Backbone-based routing can effectively reduce the network overhead and the complexity of routing scheme. However, the load of backbone nodes is larger than that of regular nodes. If the backbone node’s buffer is exhausted, it will have a significant impact on the performance of the routing scheme. Load balancing can improve the ability of backbone to deal with the change of network load, and backbone maintenance algorithm can provide backbone robustness. In this paper, we propose a robust load-balanced backbone-based multicast routing scheme in MONs. In the backbone construction algorithm, we transform the problem of backbone construction into a multi-objective optimization problem, and propose a multi-objective evolutionary algorithm-based backbone construction algorithm, namely LBMBC-MOEA algorithm. In addition, in order to increase the robustness of the backbone-based routing scheme, we propose a localized multicast backbone maintenance algorithm (MBMA) to deal with the buffer exhaustion of backbone nodes. When a backbone node’s residual buffer is insufficient, MBMA algorithm selects other nodes to replace the backbone node. The results on extensive simulations show that when considering the node buffer size constraints, compared with previous backbone-based multicast routing schemes, our proposed algorithm has better performance, and when the node’s residual buffer is insufficient, MBMA algorithm can significantly improve the performance of the backbone-based multicast routing scheme.

Key words： mobile opportunistic network; multicast; multi-objective optimization; backbone construction; backbone maintenance

1 Introduction

Mobile opportunistic network (MON) [1] is a kind of network that can realize the communication between nodes without the existence of a contemporaneous path between source and destination nodes. In some application scenarios, such as battle-field communication, post-disaster rescue site communication, and deep-space communication, due to the limitations of environment, characteristics of applications, cost and other factors, the traditional fully connected networks cannot be established. Because MONs do not rely on communication infrastructure and do not require end-to-end path between source and destination nodes, they can meet the needs of these applications.

Efficient data routing is one of the key problems in MONs. Multicast we studied in this paper is an effective information transmission method to deliver messages to a set of destination nodes. Fig.1 shows a typical multicast scenario in which a source node sends a multicast message to three multicast destinations. Multicast in MONs has many realistic application scenarios. For example, mobile crowd sensing applications [2, 3] are often used to distribute sensing tasks to a group of users with sensing devices. For another, vehicular ad hoc networks (VANETs) [4, 5] often require to distribute traffic information to a group of vehicles which have subscribed for these information. Compared with the traditional way, it can reduce the system cost by using multicast in MONs to distribute sensing tasks or traffic information. Due to the lack of contemporaneous end-to-end path, although there are extensive studies on multicast in traditional wireless multi-hop networks, they do not work appropriately in MONs.

Fig.1 Illustration of a typical multicast scenario and a mobile backbone in MONs

Full size|PPT slide

To achieve efficient multicast in MONs, a series of multicast routing schemes have been proposed [6–10]. Similar to unicast schemes, in these schemes, multicast messages are delivered to the destination nodes through a series of relay nodes, and all nodes in MONs are regarded as the potential relay nodes. However, in practice, due to limited mobility or limited resources, some nodes may have poor performance in transmitting messages. If these nodes are selected as relay nodes, the performance of message delivery will be affected. In addition, too many nodes involved in message transmission will bring a high communication cost. It can effectively solve the above problem by constructing a backbone-based hierarchical network. As shown in Fig.1, the black nodes constitute a backbone, which serve as relay nodes. For the multicast task in MONs, to deliver a message to the specific destinations, the source node relays messages to the backbone nodes unless it directly encounters one of the destination nodes. This hierarchical network structure can effectively reduce the communication cost by reducing the number of relay nodes. In addition, a backbone can improve the efficiency of message delivery and reduce the complexity of routing scheme.

At present, constructing backbone in MONs has been used for unicast routing by a handful of work [11, 12]. However, it’s still challenging to design a backbone construction algorithm for multicast routing in MONs. In multicast, a relay node may be involved in the process of transmitting a multicast message to multiple destination nodes. Therefore, it is desired that the backbone nodes have strong ability to promote the propagation of multicast messages. In addition, compared with unicast routings, relay nodes in multicast routings face higher load. When the backbone node’s buffer is exhausted, the backbone will become defective and the performance of backbone-based multicast routing will be affected. Therefore, in order to improve the performance of the backbone-based multicast routing with node buffer constraint, the load balancing of backbone should be considered to extend the lifetime of backbone nodes. Besides, in order to deal with the exhaustion of backbone node’s buffer, a backbone maintenance algorithm should be proposed to increase the robustness of the backbone.

In this paper, we propose a robust load-balanced backbone-based multicast routing scheme. In the scheme, firstly, in order to find the optimal load-balanced backbone, we formulate the Load-Balanced Multicast Backbone Construction (LMBMC) problem, which is a multi-objective optimization problem with three optimization objectives. We propose a multi-objective evolutionary algorithm-based heuristic algorithm to solve the LBMBC problem. Secondly, when the residual buffer of a backbone node is insufficient, we design a localized Multicast Backbone Maintenance Algorithm (MBMA) by using the k-hop neighbor information of nodes. The MBMA algorithm increases the robustness of the backbone-based multicast routing by selecting other nodes to replace the backbone node with insufficient residual buffer.

Our contribution consists of the following four parts. First, we take the average multicast ability of backbone nodes, the average inter-contact time between backbone nodes and other nodes, and the load balancing of backbone as three optimization objectives, and formulate the load-balanced multicast backbone construction problem as a multi-objective optimization problem LBMBC. Second, we propose a multi-objective evolutionary algorithm-based heuristic algorithm to solve the LBMBC problem. Third, as the performance of the backbone-based multicast routing scheme is easily limited by the backbone node’s buffer size, we propose a localized backbone maintenance algorithm MBMA. Forth, we conduct extensive simulations to compare our proposed algorithm with previous algorithms.

The reminder of this paper is organized as follows. Section 2 introduces the related work. Section 3 presents the overview of the problem, including network model, the utilization of node’s sociality, and the formal definition of load-balanced multicast backbone construction. Section 4 describes our multicast backbone construction algorithm and the backbone-based multicast routing scheme in detail. Section 5 describes the localized backbone maintenance algorithm. In Section 6, we compare our proposed algorithm with some previous algorithms. Finally, we conclude our research in Section 7.

2 Related work

2.1 Multicast in MONs

In recent years, some researchers have studied multicast in MONs. The authors of [13] first investigated multicast in MONs. They proposed the semantic multicast model and developed several basic multicast routing schemes in MONs. The authors of [10] proposed OS-multicast to address the challenge of link instability in MONs. OS-multicast was a dynamic tree-based multicast algorithm and it integrated MON multicast with the situation discovery by the underlying network layer. The authors of [14] studied the performance of some existing multicast algorithms. In their work, they compared several multicast algorithms, including unicast-based multicast algorithm, static tree-based multicast algorithm and dynamic tree-based multicast algorithm. The authors of [15, 16] investigated the delay-constrained multicast in MONs. They first proposed a centralized algorithm based on a tree structure. Then, they developed a distributed online algorithm based on an approximate multicast tree and optimal stopping rules. However, constructing a tree structure for multicast is only efficient when the network topology is relatively stable and the source node has a large number of messages to send. In fact, the tree-based algorithm needs to maintain a tree structure between the source and destination nodes. When the source node appears randomly in the network, these algorithms are not flexible enough.

Therefore, similar to the study of unicast routing scheme in MONs, researchers begin to propose utility-based multicast scheme. The authors of [6] extended the two-hop relay algorithm from traditional unicast scenarios to multicast scenarios. In order to control the number of message forwarding, the authors of [7] proposed to use delegation forwarding to forward multicast message. In their proposed algorithm, each node in the network was assigned a quality and level value, and the message forwarding only occurred when another node had a higher quality value than its own level value. Some work also considers combining the inherent social relationship between nodes into the design of multicast algorithm. The authors of [17] proposed a routing scheme to reduce the delivery overhead by using the sociality and interest of nodes. In their proposed algorithm, an infection recovery mechanism was also proposed to control and reduce the number of message copies. The authors of [8] investigated the problem of multicast with required delivery ratio and time constraint. They proposed an approach to forward messages according to node’s capabilities, which were measured by social-based metrics. The author of [9] introduced dynamic social features to capture node’s contact behavior. Besides, they adopt community structure in their algorithm to improve multicast efficiency. Considering the energy constraints of nodes, the authors of [18] proposed energy-aware multicast scheme to multicast single and multiple data items. They formulated the relay node selection problem as a knapsack problem. In their proposed schemes, the relay node were selected according to the centrality and the residual energy of the node. Different from the above schemes which take all nodes in an MON as potential relay nodes of multicast messages, our proposed scheme investigates the multicast routing from a hierarchical perspective by constructing a multicast backbone. By restricting message relay nodes to backbone nodes, nodes with poor ability to transmit multicast messages will be excluded in advance, which also reduces the overhead of the network. Besides, by selecting appropriate nodes to form the multicast backbone, the multicast routing scheme can be implemented more efficiently.

2.2 Backbone construction algorithm

In MANETs and WSNs, a number of algorithms have been proposed for constructing a backbone. Some of the existing work [19–21] constructs backbone by deploying heterogeneous nodes in the network. Such heterogeneous nodes have stronger communication capability than other nodes. However, in MONs, nodes are usually sparsely distributed and have mobility, which is not conducive to the prior placement of heterogeneous nodes.

In MANETs and WSNs, some work focuses on selecting nodes from the existing nodes to construct the backbone. The strategy of constructing backbone can be roughly divided into two categories. The cluster-based strategy [22, 23] assigns regular nodes as the cluster head to form a hierarchical architecture. These selected cluster heads usually have more powerful radio or transmission radius to build wireless links among themselves. The connected dominating set (CDS) -based strategy find a CDS in the network topology graph to construct the backbone. The regular nodes are either in a CDS or connected to at least one nodes in a CDS. A number of algorithms [24] have been proposed to construct backbone by using CDS. However, since there is a good connection between nodes in MANETs and WSNs, these backbone construction algorithms have ignored the delay of messages, which is a significant feature of MONs. Moreover, the network topology in MONs will change with the movement of nodes, and there is no contemporaneous path between nodes.

A small amount of previous work [11, 12, 25, 26] has worked on the backbone construction in MONs. The authors of [11, 25] used the sociality characteristics of mobile nodes to transform the backbone construction problem into an optimal subset selection problem, which aimed to transmit messages with minimal overhead. They proposed a backbone construction algorithm based on the delay-weighted betweenness centrality. However, their algorithm needed a per-determined backbone size. The authors of [12] proposed the concept of the minimum equality effective set in MONs to optimize the performance of routing algorithms in terms of message delivery latency. They proposed a localized algorithm to use the minimum equality effective set of nodes in an MON as the backbone. However, in their algorithm, each node needed to calculate its status according to the meeting frequency with each neighbor node. When the meeting frequency with some neighbor nodes changed, all related nodes needed to recalculate their status, which brought the problem of state synchronization and a large amount of calculation. Since previous work had paid little attention to the multicast backbone in MONs, in our previous work [26], we proposed a social-aware backbone construction algorithm for multicast in MONs. In the proposed algorithm, we considered the multicast ability of the node and the inter-contact time between backbone nodes and the other nodes. However, the algorithm did not take into account the impact of limited size of node buffer on the backbone-based multicast algorithm. In this paper, we investigate the construction of multicast backbone under node buffer size constraint, and propose a load-balanced multicast backbone construction algorithm to improve the performance and efficiency of multicast routing schemes.

In backbone-based routing schemes, since the backbone is responsible for the delivery of messages, the load of backbone nodes is higher than regular nodes. When some nodes in the backbone are overloaded, the performance of backbone-based routing scheme will be significantly affected. Therefore, some algorithms [27–29] focus on constructing a load-balanced CDS that helps to extend the working time of nodes in the backbone. However, most of these algorithms are carried out in WSNs, and measure the load of nodes in the backbone according to the number of connections between backbone nodes and regular nodes. In MONs, nodes have high mobility, and the connections between nodes are dynamic and intermittent. Therefore, the number of neighbor nodes of a node will change over time. In this paper, we use a network contact graph to represent the relationship between nodes and use the Reduced Dominatee Set defined in Section 3.3 to reflect the possible load of nodes in MONs. In addition, according to the characteristics of MONs using the mobility of nodes to deliver messages, we formulate the construction of load-balanced backbone as a multi-objective optimization problem.

2.3 Backbone maintenance algorithm

Once the backbone is generated, it will be responsible for the transmission of messages. However, as time goes on, some backbone nodes can no longer transmit messages due to insufficient residual buffer or node failure. This can be solved by regenerating the backbone. However, regenerating the backbone will bring a high computational cost. Therefore, in WSNs and MANETs, researchers began to propose algorithms [30–34] for backbone maintenance. The authors of [30] proposed an algorithm to maintain the connectivity of backbone by local beacon exchanges and link-state updates. In [31], for CDS-based backbone generated by dominator tree algorithm, the authors proposed the Extended Mobility Handling (EMH) algorithm to maintain the backbone. EMH algorithm shortened the recovery time by adding extra information to the beacons between nodes. The authors of [32] focused on controlling the mobility of more capable nodes to maintain the connectivity of backbone. In [33], by modeling the sensor network as an unit-disk graph, the authors explored the geometric properties of unit-disk graphs to renovate the backbone. The authors of [34] regarded the topological changes of CDS-based backbone as the pruning action in the CDS, and proposed an approach to deal with the conflicts in simultaneous migrations and pruning actions. These backbone maintenance algorithms proposed in WSNs and MANETs are based on the connection states between neighbor nodes. However, in MONs, the connections between nodes are temporary, and the network topology will change over time with the movement of nodes. In this paper, we use stochastic contact process to establish the relationship between nodes, rather than the physical connections between nodes. In addition, we propose a localized backbone maintenance algorithm. Using node’s residual buffer information and the local multi-hop neighbor node information maintained by the node, the algorithm selects nodes in the MON to replace the backbone nodes with insufficient buffer, and notifies the node it meets.

3 Preliminaries

3.1 Network model

We assume an MON composed of N nodes, denoted by V=\{n_1,n_2,...,n_N\}, and the initial buffer size of each node is the same. Each node n_i in the network is carried by people and uses the opportunity of meeting other nodes to relay messages. A multicast source node s is expected to forward a message to a group of nodes, denoted by . While sending a copy of the message to each multicast destination d_i is inefficient, a better way is to send the message through a dedicated MON multicast routing.

In MONs, the transmission of messages depends on the contacts between mobile nodes, so we use a network contact graph to represent the relationship between nodes. Network contact graph is a weighted graph with weighted nodes and edges. The nodes in the graph correspond to the mobile nodes in MONs, and the edges represent the contacts between mobile nodes. In our proposed algorithm, we measure the ability of mobile nodes to deliver multicast messages, which is represented by the weight of vertices in the graph. The weight of each edge is used to represent how closely the contact is between two nodes. In our algorithm, because social relations among people are relatively stable, we use the sociality among nodes to characterize the weight of the contact graph. For further description, we use G(V,E,W_V,W_E) to represent a network contact graph, where V is the set of vertices and E is the set of edges. W_V and W_E represent the weight functions of vertices and edges, respectively. Fig.2 is an illustration of a network contact graph. In addition, the buffer size of each mobile node is limited, such that when the node’s residual buffer is insufficient, if some messages are not deleted from the buffer, the node cannot receive new messages.

Fig.2 An illustration of a network contact graph G(V,E,W_V,W_E)

Full size|PPT slide

Suppose a subset of network nodes are selected and compose a multicast backbone, which is represented by . In the backbone-based routing scheme, only the nodes in the backbone can act as a relay. This means that for an arbitrary node n_i\in V to relay a message to a destination, it can deliver the message either directly to the destination or through nodes in backbone. In this way, the multicast routing scheme based on a backbone uses a small set of nodes as the set of relay node candidates and can achieve a good performance in energy consumption and network overheads. Obviously, in a backbone-based multicast scheme, the nodes in the backbone bear most of the traffic of the MON. If the buffer of some of the nodes in the backbone is full, the performance of routing schemes will be affected. Every time some nodes are overloaded in the backbone, it is a time-consuming process to construct the backbone from scratch. Therefore, a load-balanced backbone is needed, and when some of the nodes’ buffer are insufficient, a node replacement process is needed to maintain the backbone.

3.2 Utilization of node’s sociality

In the MON where mobile nodes are carried by people, nodes in the network reveal a certain degree of sociality. Fig.3 shows the complementary cumulative distribution function (CCDF) of the inter-contact time between nodes in two real human contact datasets, which are Infocom06 [35] and MIT-Reality [36]. We can see that the distribution in the two dataset are quite similar and approximate to the exponential distribution. In many articles [8, 18, 37, 38], considering the sociality among nodes, they assume the distribution of nodes’ pairwise inter-contact time as exponential and the contact between two nodes as a Poisson process. In this paper, we use the sociality among nodes to measure the importance of nodes in the propagation of multicast messages. In the social network analysis, the centrality of nodes in social graph is often used to measure the importance of nodes. However, social graphs are usually not weighted. For the transmission of multicast messages in MONs, a good relay node should have a high probability of contacting with other nodes. Therefore, we use the cumulative contact probability (CCP) [8] as the centrality of nodes to measure the importance of nodes in the process of multicast message propagation. The definition of CCP is as follows:

Fig.3 The distribution of inter-contact time. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Definition 1 (Cumulative contact probability, CCP [8]). For a node n_i in the MON, the CCP is defined as:

(1)CCP(n_i)=1-\frac{1}{N-1}\sum _{j=1,j\ne i}^N{\mathrm{e}}^{-{\lambda }_{ij}T},

where N is the total number of nodes in the network, and {\lambda }_{ij} is the contact rate between the node n_i and n_j.

In the situation that the inter-contact time between nodes approximately follows exponential distribution, the contact rate {\lambda }_{ij} can be calculated from the history of meetings between the two nodes in MONs within time T. Specifically, nodes use two-tuple ⟨start,end⟩ to record the start and end time of each encounter with other nodes, and use these records to calculate the exponential distribution parameter.

In network contact graph, we use the expectation of inter-contact time between nodes as the weight of the edge. Because the contact between node n_i and node n_j satisfies Poisson distribution, the expectation of the inter-contact time between the two nodes is {\displaystyle \frac{1}{{\lambda }_{ij}}}. The smaller the value is, the closer their relationship is.

3.3 Load-balanced multicast backbone construction

In our proposed scheme, since an MON is presented as a network contact graph, we use nodes in connected dominating set (CDS) of the network contact graph as the backbone nodes of MONs. Although the use of backbone can limit the range of message dissemination and reduce the network overhead, improper selection of nodes to the backbone can significantly affect the propagation of messages in MONs.

In this paper, we formulate the construction of multicast backbone as a multi-objective optimization problem. As shown in Section 3.2, the CCP of a node indicates the node’s probability of meeting a random node. The nodes with a larger value of CCP have the stronger ability to deliver multicast messages. Since different backbone node selection schemes may contain different number of nodes, we use the average CCP of backbone nodes to measure the ability of the backbone to deliver multicast messages. The ability of a backbone to deliver multicast message is computed as:

(2)O_{abil}(B)=\frac{\sum _{n_i\in B}CCP(n_i)}{|B|},

where CCP(n_i) is the CCP value of node n_i, B is a multicast backbone, and |B| is the number of backbone nodes.

The average inter-contact time is another consideration for selecting backbone nodes. A short inter-contact time between backbone nodes and their neighbor nodes is beneficial to reduce the delivery delay of multicast messages. In the network contact graph, the weight of each edge describes the expected inter-contact time between two nodes. The average inter-contact time of nodes in a backbone is computed as:

(3)O_{averTime}(B)=\sum _{n_i\in B}\frac{\sum _{n_j\in Neigh(n_i)}{W}_E(n_i,n_j)}{|Neigh(n_i)|\cdot |B|},

where Neigh(n_i) represents the set of neighbor nodes of node n_i, and |Neigh(n_i)| is the number of nodes in Neigh(n_i). W_E(n_i,n_j) is the weight of the edge between node n_i and node n_j.

When constructing a load-balanced backbone, it is considerably important to analyze the possible load of each backbone node. In general WSNs, the edges in the network topology graph represent the connections between nodes. If a node has a high degree in the network topology graph, it usually means that the node will bear a high load in the process of communication. However, in MONs, the edges in the network contact graph represent the contacts between nodes, which is intermittent and has delays. Therefore, the degree of a node in the network contact graph can not directly reflect the possible load of the node. As shown in Fig.4, it is an illustration of a part of a network contact graph. In the graph, b_i and b_j are backbone nodes, and n_k is a regular node. Suppose that at a certain moment, b_i encounters n_k for the first time. Because b_i has the message M1 received from b_j, b_i will not receive M1 from n_k. This is because the inter-contact time between b_i and n_k is larger than the expected time of M1 passing from n_k to b_i through b_j. Therefore, although there is an edge between b_i and n_k in the network contact graph as shown in Fig.4, the message is not transmitted from n_k to b_i. Therefore, in order to describe the load of backbone nodes more accurately, we define the Reduced Dominatee Set (RDeeS) of a backbone node. The definition of RDeeS is as follows:

Fig.4 A part of a network contact graph. An example of a node being dominated by more than one node

Full size|PPT slide

Definition 2 (Reduced dominatee set, RDeeS). Given an MON represented by a network contact graph G(V,E,W_V,W_E) and a backbone , we use TransET(n_u,n_v) to indicate the expected time of a message passing from node n_u to node n_v. The Reduced Dominatee Set of backbone node b_i is a subset of nodes RDeeS(b_i)\subseteq V-B, such that

1) \mathrm{\forall }{n}_i\in RDeeS(b_i), such that (n_i,b_i)\in E.

2) \mathrm{\forall }{n}_i\in RDeeS(b_i), and \mathrm{\forall }{b}_j\in B,b_j\ne b_i, such that .

Because the distribution of inter-contact time between nodes in MONs is approximately exponential, we can get the expected time of message passing from one node to another node in the backbone according to the frequency of nodes’ contacts. As shown in Fig.4, the expected time of the message from n_k passing through b_j to b_i is W_E(n_k,b_j)+TransET(b_j,b_i), and the inter-contact time between b_i and n_k is W_E(b_i,n_k). If W_E(b_i,n_k)>W_E(n_k,b_j)+TransET(b_j,b_i), then n_k is not included in RDeeS(b_i). We use the following equation to measure the load balancing of a backbone node n_i:

(4)Bal(n_i)=||RDeeS(n_i)|-\frac{|V|-|B|}{|B|}|,

where |V| is the number of nodes in the MON, and |B| is the number of backbone nodes. |V|-|B| is the number of regular nodes. {\displaystyle \frac{|V|-|B|}{|B|}} is the ideal value of the number of nodes in each backbone node’s RDeeS. For a multicast backbone B=\{b_1,b_2,...,b_m\}, we use the value of the following equation as the metric of the load balancing of the backbone:

(5)O_{Bal}(B)=\sqrt{\sum _{i=1}^m(Bal(b_i){)}^2}.

Equation (5) uses the form of L2-norm to measure the difference between the possible load of nodes in a generated backbone and the load of the backbone node in the ideal load-balanced backbone.

To sum up, the load-balanced multicast backbone construction (LBMBC) problem can be formulated as the following multi-objective optimization problem:

\begin{array}{rl}& \mathbf{M}\mathbf{a}\mathbf{x}\mathbf{i}\mathbf{m}\mathbf{i}\mathbf{z}\mathbf{e}{O}_{abil}(B),\\ & \mathbf{M}\mathbf{i}\mathbf{n}\mathbf{i}\mathbf{m}\mathbf{i}\mathbf{z}\mathbf{e}{O}_{averTime}(B),\\ & \mathbf{M}\mathbf{i}\mathbf{n}\mathbf{i}\mathbf{m}\mathbf{i}\mathbf{z}\mathbf{e}{O}_{Bal}(B),\\ & \mathbf{s}\mathbf{.}\mathbf{t}\mathbf{.}B\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}G.\end{array}

B is a valid dominating set of G, which means that if G is connected, then B is a CDS of G, and if G is not connected, then B is a DS of G, and has the same number of connected components as G. By solving the multi-objective optimization problem, we will get an optimal solution set. The final solution is selected from the optimal solution set according to the load balancing optimization objective.

4 Load-balanced backbone-based multicast routing scheme

4.1 The load-balanced multicast backbone construction algorithm: LBMBC-MOEA

LBMBC problem is a multi-objective optimization problem with three optimization objectives. Common optimization methods suggest converting the multi-objective optimization problem to a single-objective optimization problem by giving a weight to each objective. However, it is difficult to determine the weight of each objective, and there are usually conflicts between these objectives. For example, in LBMBC problem, the stronger the ability of a node to deliver multicast messages, the higher the load on the node, which will result in an unbalanced load on the backbone. Similarly, the closer the load of the node to the average value, the smaller the difference between the multicast ability of the node and other nodes. There is also a conflict between the average inter-contact time and the load balancing of nodes.

Multi-objective optimization algorithm can directly solve multi-objective problems without transforming the problem into a single objective problem. In this section, we propose a multi-objective evolutionary algorithm (MOEA) based algorithm, which is called LBMBC-MOEA, to solve the LBMBC problem. The evolutionary algorithm mimics the biological evolution in nature. It represents the solution of the problem as chromosome, and find the optimal solution through genetic operators such as selection, crossover and mutation. Nondominated sorting genetic algorithm II (NSGA-II) [39] is an MOEA, and it has a good performance in making the solution set converge to the true Pareto-optimal set in the feasible region of the problem. In the following, we will explain LBMBC-MOEA algorithm step by step.

4.1.1 Representing solutions as chromosomes

In LBMBC-MOEA algorithm, each feasible solution of LBMBC problem is mapped to a chromosome. A chromosome is denoted by C_i=(g_1,g_2,...,g_{|V|}), where g_i is the gene and |V| is the number of mobile nodes in MONs. Each gene in a chromosome corresponds to a node. If a mobile node is a dominator, the value of the corresponding gene is 1, otherwise, the value of the gene is 0. For chromosome C_i, the nodes corresponding to the genes with the value of 1 form a multicast backbone and the multicast backbone B is expressed as B(C_i)=\{n_i|g_i=1,g_i\in C_i\}. Fig.5 shows some examples of the chromosomes in LBMBC-MOEA algorithm. The black nodes denote the selected backbone nodes. The chromosomes corresponding to the two examples in Fig.5 are 111001100000 and 111001000100. The population contains a certain number of chromosomes and is a subset of the feasible region of the LBMBC problem. The execution of the algorithm is carried out in the form of population evolution from generation to generation. For convenience, the gth generation of population is denoted by:

Fig.5 Some examples of the backbone node selection scheme. (a) A valid backbone B=\{0,1,2,5,6\}; (b) an invalid backbone B^{\prime }=\{0,1,2,5,9\}

Full size|PPT slide

(6)Ge{n}_g=\{C_i^g|C_i^g=(g_{i1},g_{i2},...,g_{i|V|}),1\le i\le k\},

where k is the population size.

4.1.2 Population initialization and preference of chromosomes

The population iteration of LBMBC-MOEA algorithm begins with the initial population, so we need to determine the initial population first. In general problems, the chromosomes in the initial population can be generated randomly. However, in LBMBC problem, the nodes in the solution corresponding to a chromosome must form a CDS. Therefore, we design a population initialization algorithm to generate the first generation that meets the requirement. In the population initialization algorithm, we first use an existing CDS based backbone construction algorithm [26] to create the first chromosome C_1. Assuming that the size of the population is k, we will generate other k-1 chromosomes in the population according to the first chromosome C_1. A new chromosome is generated by adding one node to the node set corresponding to C_1 each time. Since the node set corresponding to C_1 is a CDS, it is guaranteed that the node set generated by this method is also a CDS. When selecting a new node to the node set corresponding to C_1, according to the optimization objectives of LBMBC problem, we select one of the optimization objectives, for example the multicast ability of the node, to sort the other nodes in the network. If the optimization objective is to minimize, the nodes are arranged in ascending order, and if it is to maximize, the nodes are arranged in descending order. We add one node by the order into the corresponding node set of C_1 each time to generate a new non-duplicated chromosome. If the number of chromosomes is not enough after the above steps, repeat the above steps from chromosome C_2 until there are k non-duplicated chromosomes in the initial population.

NSGA-II algorithm selects offspring by using the non-dominated sorting algorithm and the crowding-distance between chromosomes. The non-dominated sorting algorithm needs to use the Pareto dominance relation between chromosomes. For chromosome C_i and chromosome C_j, if C_i is better than C_j in at least one objective, i.e., the multicast backbone represented by C_i has higher node’s average multicast abilities, and other objectives are no worse than C_j, we call C_i Pareto dominates C_j. By using the Pareto dominance relation between chromosomes, NSGA-II algorithm uses a fast non-dominated sorting algorithm to sort the chromosomes in the current population. The time complexity of the algorithm is O(M{k}^2), where M is the number of objectives and k is the population size. In the fast non-dominated sorting algorithm, if a chromosome C_i dominates any other chromosome in the current population, its rank is 1. The chromosome that cannot be dominated by other chromosomes is also in rank 1. Among the remaining chromosomes, we determine the chromosomes in rank 2, and use the same method until all chromosomes in the population are ranked. After the non-dominated sorting, the chromosomes with the same rank correspond to a non-dominated front in the solution space. Each chromosome in a front with the smaller rank dominates all chromosomes in a front with the larger rank.

In order to avoid the offspring reside in a crowded region of the solution space, NSGA-II algorithm assigns a crowding distance for each chromosome in the same front, which can be used to maintain the diversity of the population. In order to calculate the crowding distance of each chromosome, first of all, we need to sort the chromosomes in the same front according to each objective function in ascending order. For the objective function Obj.i, the crowding distance of the mth chromosome is calculated according to the following equation:

(7)Dis[i{]}_m=\frac{[Obj.i{]}_{m+1}-[Obj.i{]}_{m-1}}{1+\mathrm{M}\mathrm{a}\mathrm{x}(Obj.i)-\mathrm{M}\mathrm{i}\mathrm{n}(Obj.i)},

where Dis[i{]}_m denotes the crowding distance of the mth chromosome according to the objective function Obj.i and [Obj.i{]}_{m-1}, [Obj.i{]}_{m+1}, \mathrm{M}\mathrm{a}\mathrm{x}(Obj.i), \mathrm{M}\mathrm{i}\mathrm{n}(Obj.i) represent the previous and next values in the sort, the maximum and the minimum values of the objective function Obj.i respectively. In the equation, adding 1 to the denominator is to prevent the situation where the denominator is 0. In order to keep the boundary of the front, we assign the crowding distance of the first and last chromosome in the sort to infinity. We calculate the crowding distance of each chromosome based on each objective function. The final crowding distance value of a chromosome is the sum of the crowding distance calculated on each objective function. The calculation is formulated as bellow:

(8)Dis[i]=\sum _{m=1}^{M}Dis[i{]}_m,

where M is the number of objective functions. When selecting offspring, for the chromosomes in a population, we prefer the chromosome with a small non-domination rank than the one with a large non-domination rank, and for two chromosomes with the same non-domination rank, we prefer the chromosome with large crowding distance than the one with small crowding distance.

4.1.3 Genetic operations

Crossover and mutation are two basic operators in the genetic algorithm based strategy. The crossover operator selects the parental chromosomes from the current population to generate new offspring. In the process of selecting paternal chromosomes, we use the binary tournament selection operator, which takes two chromosomes each time from the current population and selects the one that dominates the other or has a large crowding distance. The probability of crossover operator is P_{Cross}. In LBMBC-MOEA algorithm, we use a single point crossover operator. Since the solution of LBMBC problem needs to correspond to a CDS of the network contact graph, a correction procedure is needed to ensure the validity of the generated offspring. Fig.6 shows an example of the crossover operation and the error correction. As shown in Fig.6, chromosomes 111001000111 and 011001100100 are selected parental chromosomes. The crossover operator randomly selects a crossover point P (P = 10 in Fig.6) and exchanges genes of the parent from the crossover point to the end of the two chromosomes. After the crossover operation, the error correction procedure will verify the validity of the generated offspring. As can be seen from Fig.5(b), since node n_{11} is not covered by any backbone nodes, the offspring 111001000100 is not valid. The error correction procedure scans each gene in the chromosome of the invalid offspring. If the value of the current gene is 0, e.g., g_i^o=0, but the value of the corresponding parent’s gene is 1, e.g., g_i^P=1, then change the value of the offspring’s gene to 1. This operation continues until the offspring chromosome represents a valid scheme. Sine the chromosome of the parent represents a valid scheme, obviously, this procedure can correct the genes in the offspring’s chromosomes.

Fig.6 An illustration of crossover operation and error correction

Full size|PPT slide

The mutation operator randomly changes the genes in a chromosome to produce an offspring from a single chromosome. In our chromosome encoding scheme, if a gene is 0, by using the mutation operator, the value becomes 1, and vice versa. For the offspring generated by crossover operator, the probability of mutation of each gene is P_{muta}. The same as the crossover operator, we also need to verify the validity of the offspring after the mutation operator.

4.1.4 Process of LBMBC-MOEA algorithm

Full size|PPT slide

The process of the LBMBC-MOEA algorithm is shown in Algorithm 1. In step 1 and step 2, we construct the network contact graph according to the contact history of mobile nodes. In step 3 to step 5, we use the population initialization algorithm described in Section 4.1.2 to generate the initial population Ge{n}_1, and use the fast non-dominated sorting algorithm to sort Ge{n}_1. In step 6 to step 13, we iterate the population until the number of iterations reaches a predetermined value maxGen. In each iteration, we first use genetic operators to generate the offspring population. In order to preserve good chromosomes in the parent population, in step 11 to step 12, we apply an elite preserving strategy. Suppose that the current population is Ge{n}_i and the offspring population is {\mathit{O}\mathit{f}\mathit{f}\mathit{s}\mathit{p}\mathit{r}\mathit{i}\mathit{n}\mathit{g}}_i, when generating the new population Ge{n}_{i+1}, we first sort the combined population of Ge{n}_i and {\mathit{O}\mathit{f}\mathit{f}\mathit{s}\mathit{p}\mathit{r}\mathit{i}\mathit{n}\mathit{g}}_i. After the sorting, the set of chromosomes in the ith non-dominated front is denoted by F_i. In the elite preserving strategy, we first add F_1 to Ge{n}_{i+1}. If the size of Ge{n}_{i+1} is less than k, continue to add F_2 to Ge{n}_{i+1}, followed by F_3, and so on. Suppose F_i is the last non-dominated front added to Ge{n}_{i+1}. If the number of chromosomes in all non-dominated fronts from F_1 to F_i is larger than k, in order to maintain the size of Ge{n}_{i+1} as k, we sort the chromosomes in F_i in descending order according to the crowding distance, and select chromosomes from front to back in order to Ge{n}_{i+1}.

In LBMBC-MOEA algorithm, after maxGen iterations, we get the Pareto-optimal front of the final generation Ge{n}_{maxGen}. Since any chromosome in the Pareto-optimal front cannot dominate the other chromosomes in the same front, in order to obtain a unique optimal solution, we choose the optimal chromosome according to the load balancing optimization objective. If there are multiple chromosomes with the same value of the load balancing objective, then we compare the value of average multicast ability objective and the value of average inter-contact time in turn.

4.2 Multicast routing scheme in MONs based on LBMBC-MOEA backbone

In LBMBC-MOEA algorithm, a subset of nodes is selected to constitute a load-balanced backbone. The routing scheme proposed in this section uses the backbone for multicast message delivery. The process of the proposed routing scheme is shown in Algorithm 2. In step 2 and step 3, node n_i first sends the message that n_j is one of the destination nodes. In step 4 to step 12, different from the traditional multicast routing scheme, in backbone-based routing scheme, n_i needs to check whether n_j is a backbone node. When n_j is a backbone node, if n_i is not a backbone node, n_i will send the message to n_j. If n_i is a backbone node, n_i can send the message to n_j or wait for opportunities to meet other backbone nodes. Note that a traditional routing algorithm can be used for message transmission between backbone nodes. For example, in order to obtain a high message delivery rate and a low delivery delay, the epidemic routing algorithm can be used between backbone nodes. At this time, for backbone nodes, the rule of message transmission is to transmit the message to each backbone node that does not contain the message. In order to further reduce the overhead of MONs, the algorithm similar to probabilistic routing algorithm [40] can be adopted. In this case, when two backbone nodes meet, the probability of meeting the destination nodes will be compared, and messages will be transmitted only when the other node’s probability is high. Compared with the traditional multicast routing scheme, the load-balanced backbone-based multicast algorithm excludes poor relay nodes by using elaborately selected backbone nodes as relay nodes, and limits the propagation range of the multicast message, thus making the routing scheme more efficient.

Full size|PPT slide

5 Localized maintenance of multicast backbone

In the case of limited buffer size of nodes, one disadvantage of the backbone-based routing scheme is that backbone nodes have higher load than other nodes in the network. It will significantly affect the performance of the backbone-based routing scheme, when backbone nodes’ buffer is exhausted. Regenerating the backbone can solve the problem of backbone node buffer exhaustion, but it will lead to a high computational cost and is not time-effective. Dynamic selection of replacement nodes from the neighbor nodes can usually respond to the changes in the network faster. In this section, we design a localized multicast backbone maintenance algorithm (MBMA). When a backbone node’s buffer is about to be full, the algorithm replaces the backbone node with other nodes to increase the robustness of the backbone-based routing scheme.

In MANETs and WSNs, nodes in a connected network usually send “Hello” packets to sense the changes in neighbor nodes. However, this method is not suitable for MONs with sparse mobile nodes and challenging network environment. In MBMA algorithm, nodes do not need to sense the buffer usage on other nodes. When a backbone node’s residual buffer is insufficient, it will select some replacement nodes according to its k-hop neighbor information to maintain the backbone. In addition, because the buffer exhaustion of backbone nodes will affect the backbone-based routing scheme’s performance, it is necessary to designate the replacement nodes before the buffer exhaustion of backbone nodes. Therefore, in MBMA algorithm, we set an alert value for the buffer of each backbone node. When the residual buffer size of a backbone node is less than the alert value, the backbone node will find the replacement node according to its residual buffer size. In our proposed MBMA algorithm, when selecting replacement nodes, each backbone node only needs local information.

In MBMA algorithm, each backbone node has a replacement probability P_{replace}. When the residual buffer size of a backbone node is less than the alert value, the backbone node will start to select replacement nodes from its neighbor set according to this probability, and notify the node it meets. The replacement probability is calculated according to the following equation:

(9)

where Buff(b_i) represents the initial buffer size of backbone node b_i. Buf{f}_r(b_i) represents the residual buffer size of b_i, and alertV is the alert value of residual buffer size. The rationale of the equation is that the probability increases as the residual buffer of the backbone node decreases. Therefore, backbone nodes with little residual buffer are more eager to find the replacement node. In order to reduce unnecessary cost, when node’s residual buffer size is larger than alertV, the node does not need to find the replacement node.

Since nodes in multicast backbone constitute a CDS of the network contact graph, when a backbone node exits, there are two cases in the backbone. In the first case, the backbone is still connected after the node exits, i.e., the connected component in the CDS increase by 0. In the second case, the exit of the node leads to the disconnection of the backbone, i.e., the connected components in the CDS may increase by more than 1, resulting in the final number of connected components being larger than 2. Therefore, the selected replacement nodes need to make the previously dominatees still be dominated, while keeping the backbone network connected. MBMA algorithm selects replacement nodes based on the node’s neighborhood information. We use N_k(n_i) to denote the k-hop neighbor set of node n_i. We assume that node n_i knows its 1-hop neighbor node and it can obtain k-hop (k>1) neighborhood information through information exchange between nodes. Obviously, the higher the value of k, the more information the node needs to obtain.

Full size|PPT slide

The process of MBMA algorithm is shown in Algorithm 3. In the algorithm, the node whose residual buffer size is lower than the alert value uses its local information to designate some nodes to replace it. Specifically, in step 4 and step 5, we first color backbone nodes in N_k(n_i) as black and the dominatee of those backbone nodes as gray. The other nodes are colored as white. In step 6 to step 12, we select some nodes to cover all the dominatees in N_k(n_i), and mark these nodes as blue. Since N_k(n_i) contains only part of the information of the network contact graph, the subgraph formed by the nodes in N_k(n_i) may not be connected. If the subgraph is not connected, the spanning tree connecting all the terminal nodes cannot be formed. Therefore, in step 13, we judge the connectivity of the subgraph.

In step 14 to step 17, in order to connect the black and blue nodes obtained in the previous steps, we use the black and blue nodes as terminal nodes and adopt an edge weighted steiner tree approximation algorithm [41] to find a Steiner tree containing all terminal nodes. The selected steiner nodes are marked as yellow. The nodes with sufficient residual buffer will be selected as replacement nodes.

The time complexity of Algorithm 3 is analyzed as follows. We use G_{N_k(n_i)} to denote the induced graph of the nodes in N_k(n_i). {\mathrm{\Delta }}_{n_i} is the degree of n_i. The initial number of backbone nodes in G_{N_k(n_i)} is B{n}_{init}. The number of nodes and edges in G_{N_k(n_i)} are |N_k(n_i)| and |E_{N_k(n_i)}| respectively. In step 4 to step 12, the nodes in G_{N_k(n_i)} are colored, and the algorithm can be implemented with time complexity O(|E_{N_k(n_i)}|) [42]. In order to judge whether G_{N_k(n_i)} is connected, we need to traverse the nodes and edges in G_{N_k(n_i)}, and the time complexity is O(|N_k(n_i)|+|E_{N_k(n_i)}|). The time complexity of the Steiner tree algorithm in Algorithm 3 is O(|N_k(n_i)|\ast L^2), where L is the number of terminals. In Algorithm 3, the terminals are the black and blue nodes marked in the previous steps. When n_i exits, at most {\mathrm{\Delta }}_{n_i} nodes are marked as blue, so L\le B{n}_{init}+{\mathrm{\Delta }}_{n_i}. Therefore, the total time complexity of Algorithm 3 is O(|N_k(n_i)|\ast (B{n}_{init}+{\mathrm{\Delta }}_{n_i}{)}^2+|E_{N_k(n_i)}|).

In general, by using N_k(n_i) with a large k value, n_i can guarantee to find replacement nodes to keep the multicast backbone connected. However, the algorithm needs to make a tradeoff between the efficiency of finding replacement nodes and the cost of maintaining neighborhood information. From the time complexity of Algorithm 3, it can be seen that the running time of the algorithm will increase as N_k(n_i) becomes larger. Besides, the encounters between nodes in MONs have time intervals. As k increases, this will bing difficulties to the synchronization of neighborhood information. In fact, the value of k will not exceed the diameter of the network contact graph. In the MON composed of people carried mobile devices, the network contact graph forms a social network, and a social network has a small diameter [43]. In our implementation of MBMA algorithm, we use backbone nodes’ 2-hop neighborhood information for selecting replacement nodes. Although only partial knowledge of edges between nodes in N_2(n_i) is known, N_2(n_i) contains all edges that collect n_i’s 1-hop and 2-hop neighbors. These information can be used to determine whether n_i’s neighbor nodes are connected to other backbone nodes.

6 Performance evaluation

In this section, we give the performance evaluation of our proposed algorithm. The evaluation is conducted with the ONE simulator [44], which is an open source opportunistic network simulator. We run our experiments based on two real human contact datasets, which are Infocom06 and MIT-Reality. Infocom06 is a dataset that includes 78 mobile devices’ contacts data during Infocom 2006 in Barcelona. MIT-Reality includes data collected by 100 people over nine months at MIT.

In order to verify the efficiency of our proposed backbone and the performance of the corresponding multicast routing scheme, we implement three related schemes for comparison, including the straightforward CDS (S-CDS) backbone-based routing scheme, the Social-Aware backbone-based routing scheme [26], and the D-betweenness backbone-based routing scheme [11]. The S-CDS backbone-based routing scheme uses a straightforward way to construct the backbone. As mentioned in Section 3.2, CCP is a centrality metric for multicast, which can be used to represent the ability of nodes to deliver multicast messages. Therefore, a straightforward way to construct a multicast backbone is to use the node’s CCP as the weight and use the node weighted CDS construction algorithm [42] to construction a CDS as the multicast backbone. The Social-Aware backbone-based routing scheme constructs the CDS-based backbone considering the node’s multicast ability and the inter-contact time between mobile nodes. The D-betweenness backbone-based routing scheme uses the D-betweenness as the node’s centrality metric to construct a backbone of a preset size. D-betweenness is a centrality metric to measure the ability of a node in reducing end-to-end delay of node pair. In the simulation, using the same settings as in [11], we set the size of the D-betweenness backbone to 5. For all the backbone-based routing schemes, a probability-based multicast routing algorithm, which we call it MultiProphet, is used between backbone nodes. In MultiProphet, the node transmits messages according to the probability of meeting multicast destination nodes, and the algorithm uses a method similar to Prophet [40] to calculate and update the probability of the node meeting multicast destination nodes.

In the simulation, we set the number of multicast messages generated to 300, and each message has 30 destinations. The source and destination nodes of the multicast message are randomly generated. We compare the performance of algorithms under different buffer size constraints. In the simulation, the alert value of the residual buffer size is set to 5\mathrm{M}\mathrm{B}. When a backbone node’s buffer is exhausted, in order to receive new messages, the backbone node will drop the messages that have existed for the longest time in its buffer. The first 30% of each dataset is used as the warm-up period of the backbone construction algorithm. Some other simulation settings are shown in Tab.1.

Tab.1 Simulation settings

Parameter	Value
Message size	[500 KB,1 MB]
Transmit speed	250k Bps
Population size	20
Generation size maxGen	100
Crossover probability P_{Cross}	0.9
Mutation probability P_{muta}	0.1

To evaluate the performance of different algorithms, we use the following performance metrics:

1. Message delivery ratio: The message delivery ratio is computed as the ratio of the number of successfully delivered multicast messages to the total number of generated messages.

2. Overhead ratio: The overhead ratio is computed as the ratio of the number of forwarded messages to the number of successfully delivered messages.

3. Average delay: The average delay of an algorithm is computed as the average value of the delay of all the successfully delivered multicast messages.

6.1 Performance evaluation of LBMBC-MOEA algorithm

In this section, we give the performance evaluation of LBMBC-MOEA algorithm. We compare the backbone generated by LBMBC-MOEA algorithm with S-CDS backbone, D-betweenness backbone and Social-Aware backbone. In the simulation, in order to reduce the influence of the data set on the results, we conduct the simulations on a network of 50 nodes with Random Waypoint (RWP) mobility [45]. The Random Waypoint mobility model, where the distribution of inter-contact time between mobile nodes is approximately exponential [46], can be used to generate the simulated data to be used in our simulation. Some basic parameters of RWP model are shown in Tab.2. The buffer size of the node is set to 80\mathrm{M}\mathrm{B}.

Tab.2 Simulation parameters of RWP

Parameter	Value
Duration	100000 s
Simulation region	1000 × 1000 m2
Node speed (m/s)	[0.5,1]
Wait time/s	[0, 60]
Transmit range	10 m

In the process of message transmission, the adoption of different routing schemes between backbone nodes will have different influence on the load of backbone nodes. In this section, we only simulate the load difference between the backbone nodes in communicating with regular nodes, and the performance comparison of different backbone-based multicast routing schemes is shown in the next section. In the simulation of this section, the transmission of message only occurs between the regular node and the backbone node. For the generated backbone, we calculate the longest expected time T_{Ep} of the paths between backbone nodes. When the message is transmitted to a backbone node, the regular node will save the message until the time exceeds T_{Ep}. In the simulation, after the backbone is generated, we sample the buffer occupancy rate of nodes every 4000s. The buffer occupancy rate of backbone nodes generated by different backbone construction algorithms is shown in Fig.7.

Fig.7 The buffer occupancy rate of backbone nodes generated by different algorithms. (a) S-CDS backbone; (b) D-betweenness backbone; (c) social-aware backbone; (d) LBMBC-MOEA backbone

Full size|PPT slide

From Fig.7(a)−(d), we can see that in the process of message transmission, the buffer occupancy rate of backbone nodes is significantly higher than that of regular nodes. We use the standard deviation of the backbone nodes’ buffer occupancy rate when backbone’s load is stable to evaluate the load balancing performance of different backbone construction algorithms. In Fig.7, the standard deviation of the buffer occupancy rate of nodes in S-CDS backbone, D-betweenness backbone, Social-Aware backbone and LBMBC-MOEA backbone are 0.167, 0.1975, 0.1573 and 0.0639, respectively. The results show that compared with the backbone generated by other algorithms, the load of backbone nodes generated by LBMBC-MOEA algorithm is more balanced.

6.2 Comparison of multicast routing scheme based on different backbones

In this section, we evaluate the performance of multicast routing scheme based on different backbones. In addition, we take the multicast routing scheme without using the backbone as a baseline scheme. According to the simulation setup, in the baseline scheme, all nodes in the MON use MultiProphet to transmit messages, while in the backbone-based multicast routing scheme, MultiProphet algorithm is only used for message transmission between backbone nodes. Our simulations are based on the datasets Infocom06 and MIT-Reality, which record real human contacts. The node’s buffer size is incremented from 30\mathrm{M}\mathrm{B} to 100\mathrm{M}\mathrm{B} with a step of 10\mathrm{M}\mathrm{B}. Our simulation results are based on multiple runs of each algorithm under different node buffer size constraints.

We first evaluate the delivery ratio of all the algorithms. From Fig.8 we can see that, as the buffer size of nodes increases from 30\mathrm{M}\mathrm{B} to 100\mathrm{M}\mathrm{B}, the delivery ratio of each algorithm increases gradually, and the average delivery ratio of the LBMBC-MOEA backbone-based multicast routing scheme is higher than other backbone-based multicast routing schemes. This is because in the backbone used by other algorithms, the load of backbone nodes is unbalanced. Therefore, in the process of message transmission, the buffer of backbone nodes used by other algorithms is easier to run out, resulting in some backbone nodes receiving new messages by frequently deleting messages in their buffer, which reduces the delivery ratio of algorithms. Since LBMBC-MOEA algorithm considers the balance of load between nodes when generating the backbone, it can reduce the number of messages deleted due to the uneven load of nodes in the backbone, so the algorithm has a higher delivery ratio. We can also see from Fig.8 that, under the constraints of different node buffer size, the average delivery ratio of the LBMBC-MOEA backbone-based routing scheme is between 89.37% and 97.4% on Infocom06 and between 77.41% and 88.34% on MIT-Reality compared with MultiProphet algorithm. This shows that although the LBMBC-MOEA backbone-based algorithm limits the transmission range of messages in MONs, it still has a good performance in the message delivery ratio. When the node’s buffer size is 30\mathrm{M}\mathrm{B}, the delivery ratio difference between the LBMBC-MOEA backbone-based algorithm and the MultiProphet algorithm is the smallest.

Fig.8 Comparisons of delivery ratio. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Fig.9 shows the comparison of different algorithms on the overhead ratio. We can see that the LBMBC-MOEA backbone-based algorithm has the lowest overhead ratio on both datasets. This is because other backbone construction algorithms in the simulation do not consider the balance of load among backbone nodes. In the process of message transmission, if a backbone node deletes a message due to the insufficient buffer space, it will receive the message again when it meets other nodes carrying the message, which will increase the number of message forwarded in the network and increase the load of the MON. We can also see from Fig.9 that under different node buffer size constraints, the average overhead ratio of the LBMBC-MOEA backbone-based routing scheme is between 9.95% and 13.18% on Infocom06 and between 18.55% and 32.08% on MIT-Reality compared with MultiProphet algorithm. This shows that compared with the routing scheme without using backbone, the LBMBC-MOEA backbone-based routing scheme can significantly reduce the load of an MON when sending multicast messages.

Fig.9 Comparisons of overhead ratio. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Fig.10 shows the comparison of different schemes on the average delay. We can see that the average delay of the LBMBC-MOEA backbone-based routing scheme is lower than that of S-CDS backbone-based routing scheme and D-betweenness backbone-based routing scheme, and slightly higher than that of Social-Aware backbone-based routing scheme. In D-betweenness backbone-based scheme, although the scheme considers the ability of nodes to reduce the end-to-end delay between nodes, it does not consider the ability of nodes to deliver multicast messages. However, the delivery delay of a multicast message is the time required for all destination nodes to receive the message, which is affected by the ability of backbone nodes to deliver multicast messages. Therefore, for the delivery of multicast messages, the average delay of D-betweenness backbone-based scheme is higher than that of other schemes considering the node’s mulitcast ability. S-CDS backbone-based scheme considers the multicast ability of nodes, but ignores the inter-contact time between the backbone nodes and the surrounding nodes. Therefore, compared with LBMBC-MOEA backbone-based scheme and Social-Aware backbone-based scheme, S-CDS backbone-based scheme has a larger average delay. Although the inter-contact time between nodes is considered in LBMBC-MOEA algorithm, we can see from Algorithm 1 that, in the last generation of chromosomes, LBMBC-MOEA algorithm prefers the one with load balancing. Therefore, in the simulation, the average delay of LBMBC-MOEA backbone-based scheme is slightly larger than that of Social-Aware backbone-based scheme, which takes into account both the multicast ability of nodes and the inter-contact time between nodes. Compared with the backbone-based routing schemes, MultiProphet has the lowest average delay, but as can be seen from Fig.9, it also has the highest overhead.

Fig.10 Comparisons of average delay. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

6.3 Performance evaluation of MBMA algorithm

In this section, we evaluate the performance of MBMA algorithm. Due to the limited buffer size, when the backbone node’s buffer is exhausted, the performance of the backbone-based routing scheme will be affected. MBMA algorithm selects other nodes to replace the backbone node whose buffer is about to run out, so as to improve the performance of the backbone-based routing scheme when the node’s buffer is insufficient. In the experiment of this section, the node’s buffer size is incremented from 30\mathrm{M}\mathrm{B} to 300\mathrm{M}\mathrm{B} with a step of 30\mathrm{M}\mathrm{B}, and the results are based on multiple runs of each scheme under different node buffer size constraints.

When the node’s buffer is exhausted, the node drops the existing messages in its buffer to receive new messages. The number of dropped messages reflects the congestion degree of messages in relay nodes’ buffer during message transmission. In general, smaller number of dropped messages means lower network cost. Fig.11 shows the comparison of the number of dropped messages of LBMBC-MOEA backbone-based routing scheme with and without MBMA. We can see that when the node’s buffer size is 30\mathrm{M}\mathrm{B}, compared with the one without MBMA, the scheme with MBMA has a significantly smaller number of dropped messages. With the increase of node’s buffer size, the number of dropped messages of LBMBC-MOEA backbone-based scheme decreases gradually, and finally the number of dropped messages of the scheme without MBMA and the scheme with MBMA is reduced to 0. This is because, as the node’s buffer size increases, the situation of insufficient node’s buffer will decrease. When the node has a large enough buffer, it will not drop messages in its buffer to accept new messages. Therefore, with the increase of the node’s buffer size, the number of dropped messages will eventually become 0.

Fig.11 Comparisons of the number of dropped messages of the scheme with and without MBMA algorithm. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Fig.12-Fig.14 show the comparison of delivery ratio, overhead ratio and average delay of the LBMBC-MOEA backbone-based routing scheme with and without MBMA, respectively. From Fig.12 and Fig.14, we can see that when the node’s buffer size is small, the scheme with MBMA has a higher delivery ratio and a lower average delay than the scheme without MBMA. This is because when the backbone node’s buffer is insufficient, MBMA algorithm will select other nodes to replace the backbone nodes with insufficient buffer, so as to reduce the impact of insufficient backbone node’s buffer on the performance of the backbone-based routing scheme. We can also see from Fig.12 and Fig.14 that with the increase of node’s buffer size, the performance of the two schemes is gradually the same. This is because when the node’s buffer is sufficient, no backbone node will be replaced. From Fig.13, we can see that as the node’s buffer size increases from 30\mathrm{M}\mathrm{B}, the overhead ratio of the scheme with MBMA is first smaller than that of the scheme without MBMA, then larger than that of the scheme without MBMA, and finally the same as that of the scheme without MBMA. The reason for the situation where the overhead ratio of the scheme with MBMA is larger than the scheme without MBMA is that MBMA algorithm may slightly increase the size of the backbone. Although MBMA algorithm reduces the overhead caused by the insufficient node’s buffer, more nodes participate in the message forwarding, which also increases the network overhead. Therefore, when the node’s buffer size exceeds a certain value, the overhead of the scheme with MBMA is higher than that of the scheme without MBMA. Although the use of MBMA algorithm may increase the backbone-based scheme’s overhead ratio in some cases, from the comparison results of delivery ratio and average delay, the use of MBMA algorithm can significantly improve the performance of the backbone-based routing scheme when the node’s buffer is insufficient.

Fig.12 Comparisons of delivery ratio of the scheme with and without MBMA algorithm. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Fig.13 Comparisons of overhead ratio of the scheme with and without MBMA algorithm. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

Fig.14 Comparisons of average delay of the scheme with and without MBMA algorithm. (a) Infocom06; (b) MIT-Reality

Full size|PPT slide

7 Conclusion

In this paper, we investigate the multicast routing scheme in MONs. We propose a robust load-balanced backbone-based multicast routing scheme. In the construction of backbone, we consider the multicast ability of node, the inter-contact time of node with other nodes, and the load balancing of the backbone. We formulate the construction of the multicast backbone as a multi-objective optimization problem LBMBC. Then, to solve the LBMBC problem, we propose a multi-objective evolutionary algorithm-based backbone construction algorithm, namely the LBMBC-MOEA algorithm. In order to increase the robustness of the backbone-based routing scheme, we propose a localized multicast backbone maintenance algorithm, namely the MBMA algorithm. When a backbone node’s residual buffer size is less than an alert value, MBMA algorithm select other nodes to replace it. Through extensive simulations, we show that, compared with previous backbone-based multicast routing schemes, when the node’s buffer is limited, LBMBC-MOEA backbone-based multicast scheme has a higher delivery ratio and a lower overhead ratio, and when backbone node’s residual buffer is insufficient, MBMA algorithm can significantly improve the performance of the backbone-based multicast routing scheme.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 61972044 and 61732017), the Fundamental Research Funds through the Central Universities (2020XD-A09-3), the Funds for International Cooperation and Exchange of NSFC (Grant No. 61720106007), and the 111 Project (B18008).

References

1 Pelusi L, Passarella A, Conti M . Opportunistic networking: data forwarding in disconnected mobile ad hoc networks. IEEE communications Magazine, 2006, 44( 11): 134–141

2 Ganti R K, Ye F, Lei H . Mobile crowdsensing: current state and future challenges. IEEE Communications Magazine, 2011, 49( 11): 32–39

3 Ma H D, Zhao D, Yuan P Y . Opportunities in mobile crowd sensing. IEEE Communications Magazine, 2014, 52( 8): 29–35

4 Hartenstein H, Laberteaux L P . A tutorial survey on vehicular ad hoc networks. IEEE Communications Magazine, 2008, 46( 6): 164–171

5 Wang Y, Liu Y, Zhang J, Ye H, Tan Z . Cooperative store-carry-forward scheme for intermittently connected vehicular networks. IEEE Transactions on Vehicular Technology, 2017, 66( 1): 777–784

6 Lee U, Oh S Y, Lee K W, Gerla M. RelayCast: scalable multicast routing in delay tolerant networks. In: Proceedings of 2008 IEEE International Conference on Network Protocols. 2008, 218–227

7 Wang Y, Li X, Wu J. Multicasting in delay tolerant networks: delegation forwarding. In: Proceedings of 2010 IEEE Global Telecommunications Conference GLOBECOM 2010. 2010, 1–5

8 Gao W, Li Q, Zhao B, Cao G . Social-aware multicast in disruption-tolerant networks. IEEE/ACM Transactions on Networking, 2012, 20( 5): 1553–1566

9 Chen X, Shang C, Wong B, Li W, Oh S . Efficient multicast algorithms in opportunistic mobile social networks using community and social features. Computer Networks, 2016, 111: 71–81

10 Ye Q, Cheng L, Chuah M C, Davison B D. OS-multicast: on-demand situation-aware multicasting in disruption tolerant networks. In: Proceedings of the 63rd IEEE Vehicular Technology Conference. 2006, 96–100

11 Liu T, Zhu Y, Jiang R, Li B . A sociality-aware approach to computing backbone in mobile opportunistic networks. Ad Hoc Networks, 2015, 24: 46–56

12 Yang S, Wu J. Adaptive backbone-based routing in delay tolerant networks. In: Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. 2013, 356–364

13 Zhao W, Ammar M, Zegura E. Multicasting in delay tolerant networks: semantic models and routing algorithms. In: Proceedings of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. 2005, 268–275

14 Ye Q, Liang C, Chuah M C, Davison B D . Performance comparison of different multicast routing strategies in disruption tolerant networks. Computer Communications, 2009, 32( 16): 1731–1741

15 Liu Y, Bashar A M A E, Li F, Wang Y, Liu K. Multi-copy data dissemination with probabilistic delay constraint in mobile opportunistic device-to-device networks. In: Proceedings of the 17th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks. 2016, 1–9

16 Liu Y, Wu H, Xia Y, Wang Y, Li F, Yang P . Optimal online data dissemination for resource constrained mobile opportunistic networks. IEEE Transactions on Vehicular Technology, 2017, 66( 6): 5301–5315

17 Galluccio L, Lorenzo B, Glisic S . Sociality-aided new adaptive infection recovery schemes for multicast DTNs. IEEE Transactions on Vehicular Technology, 2016, 65( 5): 3360–3376

18 Roy A, Bose S, Acharya T, DasBit S . Social-based energy-aware multicasting in delay tolerant networks. Journal of Network and Computer Applications, 2017, 87: 169–184

19 Xu K, Hong X, Gerla M . Landmark routing in ad hoc networks with mobile backbones. Journal of Parallel and Distributed Computing, 2003, 63( 2): 110–122

20 Srinivas A, Modiano E . Joint node placement and assignment for throughput optimization in mobile backbone networks. IEEE Journal on Selected Areas in Communications, 2012, 30( 5): 975–985

21 Chu S, Wei P, Zhong X, Wang X, Zhou Y . Deployment of a connected reinforced backbone network with a limited number of backbone nodes. IEEE Transactions on Mobile Computing, 2013, 12( 6): 1188–1200

22 Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. 2000, 10–20

23 Younis O, Fahmy S . HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2004, 3( 4): 366–379

24 Yu J, Wang N, Wang G, Yu D . Connected dominating sets in wireless ad hoc and sensor networks — a comprehensive survey. Computer Communications, 2013, 36( 2): 121–134

25 Liu T, Zhu Y, Jiang R, Li B. A sociality-aware approach to computing backbone in mobile opportunistic networks. In: Proceedings of 2013 IEEE Global Communications Conference. 2013, 389–394

26 Zhang D, Ma H, Zhao D. Social-aware backbone-based multicast routing in mobile opportunistic networks. In: Proceedings of the 3rd International Conference on Big Data Computing and Communications. 2017, 31–38

27 He J, Ji S, Fan P, Pan Y, Li Y. Constructing a load-balanced virtual backbone in wireless sensor networks. In: Proceedings of 2012 International Conference on Computing, Networking and Communications. 2012, 959–963

28 Ruble Z, Stefanovic M. Load balanced connected dominating set for mobile ad hoc networks. In: Proceedings of the 6th International Symposium on Communications, Control and Signal Processing. 2014, 606–610

29 Kumar G, Rai M K . An energy efficient and optimized load balanced localization method using CDS with one-hop neighbourhood and genetic algorithm in WSNs. Journal of Network and Computer Applications, 2017, 78: 73–82

30 Liang B, Haas Z J. Virtual backbone generation and maintenance in ad hoc network mobility management. In: Proceedings of IEEE INFOCOM 2000 Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. 2000, 1293–1302

31 Sakai K, Sun M T, Ku W S, Okada H. Maintaining CDS in mobile ad hoc networks. In: Proceedings of the 3rd International Conference on Wireless Algorithms, Systems, and Applications. 2008, 141–153

32 Srinivas A, Zussman G, Modiano E . Construction and maintenance of wireless mobile backbone networks. IEEE/ACM Transactions on Networking, 2009, 17( 1): 239–252

33 Xing K, Zhang S, Shi L, Zhu H, Wang Y. A localized backbone renovating algorithm for wireless ad hoc and sensor networks. In: Proceedings of 2013 IEEE INFOCOM. 2013, 2184–2192

34 Wang J, Kodama E, Takata T. Construction and maintenance of K-hop CDS in mobile ad hoc networks. In: Proceedings of the 31st IEEE International Conference on Advanced Information Networking and Applications. 2017, 220–227

35 Scott J, Gass R, Crowcroft J, Hui P, Diot C, Chaintreau A. The cambridge/haggle dataset (v. 2009-05-29). See Crawdad.org/cambridge/haggle/ website, 2018

36 Eagle N, Pentland A. The mit/reality dataset (v. 2005-07-01). See Crawdad.org/mit/reality/ website, 2018

37 Daly E M, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs. In: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2007, 32–40

38 Hui P, Crowcroft J, Yoneki E . BUBBLE rap: social-based forwarding in delay-tolerant networks. IEEE Transactions on Mobile Computing, 2011, 10( 11): 1576–1589

39 Deb K, Pratap A, Agarwal S, Meyarivan T . A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6( 2): 182–197

40 Lindgren A, Doria A, Schelén O. Probabilistic routing in intermittently connected networks. In: Proceedings of the 1st International Workshop on Service Assurance with Partial and Intermittent Resources. 2004, 239–254

41 Wu B Y, Chao K M. Spanning Trees and Optimization Problems. London: Chapman & Hall Led, 2004

42 Guha S, Khuller S . Approximation algorithms for connected dominating sets. Algorithmica, 1998, 20( 4): 374–387

43 Bringmann B, Berlingerio M, Bonchi F, Gionis A . Learning and predicting the evolution of social networks. IEEE Intelligent Systems, 2010, 25( 4): 26–35

44 Keränen A, Ott J, Kärkkäinen T. The ONE simulator for DTN protocol evaluation. In: Proceedings of the 2nd International Conference on Simulation Tools and Techniques. 2009, 55

45 Johnson D B, Maltz D A . Dynamic source routing in ad hoc wireless networks. In: Imielinski T, Korth H F, eds. Mobile Computing. Boston: Springer, 1994, 153–181

46 Abdulla M, Simon R. Characteristics of common mobility models for opportunistic networks. In: Proceedings of the 2nd ACM Workshop on Performance Monitoring and Measurement of Heterogeneous Wireless and Wired Networks. 2007, 105–109