DAG Based Multipath Routing Algorithm for Load Balancing in Machine-to-Machine Networks

Abstract

In M2M networks, most nodes are powered by battery; hence the overused nodes may easily be out of power, which causes the reduction of network lifetime. To solve this problem, it is helpful to balance network load into more nodes and links, so as to reduce network congestion. Multipath routing is a useful tool to reduce congestion, since data flow can be dispersed into multiple paths. However, most of the previous multipath routing algorithm is based on the path disjoint constraint, which leads to the lack of routing paths and the failure to disperse data flow into more links. In this paper, a directed acyclic graph based multipath routing algorithm for congestion minimization (DAGMR) is proposed, where different routing paths are confined in a directed acyclic graph (DAG) under time delay constraint. Furthermore, the data flow distribution is accomplished through partial capacity network to obtain the minimal multipath routing congestion factor. Simulation indicates that our algorithm can obtain lower congestion factor and formulates multipath routing graph with more nodes and links than algorithm with path disjoint constraint. In addition, our algorithm is a polynomial time complexity algorithm with nodes and links number of the entire network.

1. Introduction

At present, Machine-to-Machine (M2M) network has emerged as an innovative topic and is receiving huge attention [1]. One of the biggest advantages of M2M networks is that nodes directly communicate with each other without human intervention, so that costs can be reduced and services can be improved in a wide range of industries. However, performance of M2M network suffers a lot from low-power character of network nodes. Since most nodes in wireless M2M networks are powered by batteries, the overused nodes can easily be out of power, which leads to the reduction of lifetime of entire networks [2]. To solve above problems, network load should be balanced into different nodes and links so as to reduce the congestion of certain links and ease the burden of certain overused nodes.

The objective to balance network load is to reduce network congestion. To achieve this objective, multipath routing is a useful method, since network data flow can be dispersed into multiple paths, so as to reduce network congestion. Former researches of this aspect are as follows. Reference [3] represents multipath routing as an optimization problem of congestion minimization and proposes a polynomial time algorithm to solve the problem of congestion minimization under path number constraint and time delay constraint. Reference [4] proposes a bandwidth aware multipath routing algorithm for Ad Hoc network. References [5, 6] propose low complexity link state multipath routing algorithm. Reference [7] proposes a tree search based multipath routing algorithm. Reference [8] proposes a network decomposition and traffic balancing based multipath routing algorithm.

Those algorithms above are mostly based on the principle that different paths should be disjoint (including node disjoint and link disjoint). Although the probability of data session failure can be reduced through the path disjoint principle based multipath routing, network congestion cannot be minimized, due to the following two reasons. First, the paths disjoint constraint leads to the reduction of paths number, which is a negative impact on the balance of data flow. Second, while trying to find disjoint paths, some extra links with relatively low link capacity use rate would be ignored. For the example illustrated in Figure 1, although four parallel paths from S to D, which are depicted in solid line, exist, it is also helpful if some extra links crossing those paths can be utilized. For instance, when $v_{2} \to v_{3}$ and $v_{3} \to D$ are both in high capacity use rate and the capacity use rate of $v_{6} \to D$ is relatively lower, congestion of $v_{2} \to v_{3}$ and $v_{3} \to D$ can be reduced, if $v_{2}$ disperses some data flow to $v_{6}$ .

Figure 1

An example of multipath routing, where additional links besides disjoint paths can be used to reduce network congestion.

In order to further reduce network congestion, this paper proposes a directed acyclic graph (DAG) based multipath routing algorithm. Our algorithm abandons the path disjoint principle, and the final multipath routing graph is obtained through maximum directed acyclic graph under time delay constraint (ML-DAG). Comparing with the former multipath routing algorithms, our algorithm constructs multipath routing graph with more nodes and links, and the network congestion can be efficiently reduced. The rest of this paper is organized as follows. Basic concept and the problem of multipath routing for congestion minimization under time delay constraint (MCMTD) are proposed in Section 2. In Section 3, the explicit description of three parts of entire algorithm with the corresponding time complexity analysis is proposed. Section 4 illustrates the simulation results, compared with the split multipath routing with maximally disjoint paths (SMR) [9] algorithm. Section 5 concludes the entire paper.

2. Basic Model and Problem Formulation

2.1. Basic Model

The topology of M2M network is modeled as a directed graph, $G (V, E)$ , where V and E are set of nodes and set of links, respectively, with the following properties. (i)

For each link $e = (v_{i}, v_{j})$ , $v_{i}$ , $v_{j}$ refer to head and tail of e, respectively, which can be denoted as $v_{i} = T (e)$ and $v_{j} = H (e)$ , besides $v_{i}$ is called the parent node of $v_{j}$ . For any node $v \in V$ , $O_{G} (v)$ and $I_{G} (v)$ denote the set of out links and set of input link of v in G, respectively.

(ii)

G is a graph with bidirectional edges, namely, for any $e = (v_{i}, v_{j}) \in E$ , $\overset{\leftarrow}{e} = (v_{j}, v_{i}) \in E$ .

(iii)

For any $e = (v_{i}, v_{j}) \in E$ , $d (v_{i}, v_{j})$ (or $d_{i j}$ , $d (e)$ ) and $c_{e}$ denote time delay and capacity of the link, respectively. Given one data flow session $F_{S, D} (γ)$ , where γ refers to total data quantity per time unit and S, D refer to the source node and destination node, respectively, let $c_{e}^{u}$ $(0 < c_{e}^{u} < c_{e})$ be the capacity of e occupied by other flow sessions besides $F_{S, D}$ .

(iv)

Given $G^{'} (V_{G^{'}}, E_{G^{'}})$ , if $V_{G^{'}} \subset V$ and $E_{G^{'}} \subset E$ , then $G^{'}$ is one subgraph of G, namely, $G^{'} \subset G$ . Given $G_{1}, G_{2} \subset G$ , and $G^{u}$ satisfies that $V_{G^{u}} = V_{G_{1}} ⋃ V_{G_{2}}$ and $E_{G^{u}} = E_{G_{1}} ⋃ E_{G_{2}}$ , then $G^{u}$ is also a subgraph of G and can be denoted as $G^{u} = G_{1} ⋃ G_{2}$ .

(v)

Given $S, D \in G$ , a simple path, $P_{S, D}^{G} (V_{p}, E_{p})$ , is a subgraph of G, namely, $P_{S, D}^{G} (V_{p}, E_{p}) \subset G$ , such that:

(1)

$V_{p} = {S, v_{p_{1}}, v_{p_{2}}, \dots, v_{p_{k}}, D}$ ;

(2)

$E_{p} = {(S, v_{p_{1}}), (v_{p_{1}}, v_{p_{2}}), \dots, (v_{p_{k - 1}}, v_{p_{k}})$ , $(v_{p_{k}}, D)}$ .

Furthermore, if for all $1 \leq i < j \leq k$ , $v_{p_{i}} \neq v_{p_{j}}$ , then $p_{S, D}$ is a simple path, which is denoted as $p_{S, D}^{*}$ .

(vi)

A circle, $P^{c} (V_{p^{c}}, E_{p^{c}})$ , is a directed graph, such that

(1)

$V_{p^{c}} = {S, v_{p_{1}}, v_{p_{2}}, \dots, v_{p_{k}}}$ ;

(2)

$E_{p^{c}} = {(S, v_{p_{1}}), (v_{p_{1}}, v_{p_{2}}), \dots, (v_{p_{k - 1}}, v_{p_{k}})$ , $(v_{p_{k}}, S)}$ .

In addition, directed acyclic graph (DAG) [10] is one special kind of graph, which is defined as follows.

Definition 1.

A directed graph (as shown in Figure 2), $G^{N} (V_{G^{N}}, E_{G^{N}})$ , is called a directed acyclic graph (DAG), such that for all $v_{i}, v_{j} \in V_{G^{N}}$ , if simple path from $v_{i}$ to $v_{j}$ , $P_{v_{i}, v_{j}}^{*} \subset G^{N}$ , exists, then no path from $v_{j}$ to $v_{i}$ exists in $G^{N}$ .

Figure 2

An example of layer structure for DAG, where entire graph is divided into 5 layers.

According to above definition, DAG has two important properties.

First, DAG can be divided into several layers, which is defined as follows.

Definition 2.

Given one DAG, $G^{N}$ , the layer structure of $G^{N}$ is denoted as layer $(G^{N}) = {G_{l_{1}}^{N}, \dots, G_{l_{1}}^{N}}$ such that (1)

$G_{l_{1}}^{N}, \dots, G_{l_{1}}^{N} \subset G^{N}$ , such that $⋃_{i = 1}^{k} V_{G_{l_{i}}^{N}} = V_{G^{N}}$ , and for all $1 \leq i < j \leq k$ , $V_{G_{l_{i}}^{N}} ⋂ V_{G_{l_{j}}^{N}} = \emptyset$ .

(2)

Nodes of the first layer have no input links, namely, $V_{G_{l_{1}}^{N}} = {v | v \in V_{G^{N}}, I_{G^{N}} = \emptyset}$ ; and $\forall 1 < i \leq k$ , nodes of layer i have parent node in layer $i - 1$ , namely, $V_{G_{l_{i}}^{N}} = {v | v \in V_{G^{N}} ∖ ⋃_{j = 1}^{i - 1} V_{G_{l_{j}}^{N}}, \exists e \in I_{G^{N}} (v), T (e) \in V_{G_{l_{i - 1}}^{N}}}$ .

(3)

Links in each layer connect nodes in the same layer, namely, $E_{G_{l_{i}}^{N}} = {e \in G^{N} | T (e), H (e) \in V_{G_{l_{i}}}^{N}}$ .

Second, longest path [11] between two nodes can be defined in DAG as follows.

Definition 3.

Given one DAG, $G^{N}$ , and $v_{i}, v_{j} \in V_{G^{N}}$ , if simple path exists from $v_{i}$ to $v_{j}$ in $G^{N}$ , then longest path from $v_{i}$ to $v_{j}$ in $G^{N}$ , $\bar{P_{v_{i}, v_{j}}^{G^{N}}}$ , satisfies for any $P_{v_{i}, v_{j}}^{G^{N}} \subset G^{N}$ , $d (\bar{P_{v_{i}, v_{j}}^{G^{N}}}) \geq d (P_{v_{i}, v_{j}}^{G^{N}})$ .

Furthermore, following two types of DAGs are presented in this paper, which are useful throughput the paper.

Definition 4.

A DAG, $G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}})$ , is called an L delay constraint directed acyclic graph (L-DAG), if the following properties satisfy: (1)

$G_{S, D}^{L}$ satisfies closure property, namely, $I_{G_{S, D}^{L}} (S) = \emptyset$ , $O_{G_{S, D}^{L}} (S) = \emptyset$ , $\forall v \in V ∖ {S} I_{G_{S, D}^{L}} (v) = \emptyset$ , for all $v \in V ∖ {D} O_{G_{S, D}^{L}} (v) = \emptyset$ ;

(2)

time delay of the longest path from S to D is smaller than L, namely, $d (\bar{P_{S, D}^{G^{u}}}) \leq L$ .

Definition 5.

Given G, an L-DAG, ${\hat{G}}_{S, D}^{L}$ is called a maximum L-DAG (ML-DAG), if the following property holds: for all $v_{i}, v_{j} \in V_{{\hat{G}}_{S, D}^{L}}$ , if there exists $p_{v_{i} v_{j}} \subset G ∖ {\hat{G}}_{S, D}^{L}$ , then one of the following two conditions holds. (1)

$G_{n} = {\hat{G}}_{S, D}^{L} ⋃ p_{v_{i} v_{j}}$ is a subgraph with circle.

(2)

If $G_{n}$ is a DAG, $d (\bar{P_{S, D}^{G_{n}}}) > L$ .

2.2. Multipath Routing for Congestion Minimization under Time Delay Constraint

As mentioned in [3], the multipath routing strategy for data transmission can be denoted as follows.

Definition 6.

Multipath routing strategy (MRS) from S to D is denoted as $T (S, D, γ, L) = {G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}}), X (E_{G^{L}})}$ , where γ denotes total data transferred in one time unit, L denotes the upper bound of time delay for data send, $G_{S, D}^{L}$ is an L-DAG and $X (E_{G^{L}}) = {x (e) : e \in E_{G^{L}})}$ denotes the amount of data to send on each link of $G_{S, D}^{L}$ per time unit, which satisfies the following. (1)

Link capacity constraint, namely, for all $e \in E_{G^{L}}$ , $0 < x (e) \leq c_{e} - c_{e}^{u}$ .

(2)

Network flow constraint, namely, ${\sum ‍}_{e \in O (S)} x (e) = {\sum ‍}_{e \in I (D)} x (e) = γ$ , for all $v \in V_{G^{L}} ∖ {S, D}$ , ${\sum ‍}_{e \in O (v)} x (e) = {\sum ‍}_{e \in I (v)} x (e)$ .

As mentioned before, the efficiency of multipath routing strategy is evaluated by the congestion factor [3], which is defined as below.

Definition 7.

Given $T (S, D, γ, L) = {G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}}), X (E_{G^{L}})}$ , congestion factor of each link is

\begin{matrix} α (e) = {\begin{cases} \frac{c_{e}^{u} + x (e)}{c_{e}}, & if e \in E_{G^{L}}, \\ \frac{c_{e}^{u}}{c_{e}}, & if e \in E_{G} ∖ E_{G^{L}} . \end{cases} \end{matrix}

(1)

Congestion factor of each link is

α_{G} = \max {α e, e \in E_{G}}

. Congestion factor of MRS is

α_{T} = \max {α e, e \in E_{G^{L}}}

In above definition, $α (e)$ is the judgement of congestion on each link and $α_{G}$ is the judgement of congestion of entire network, according to [3]. However, $α_{G}$ is not a good evaluation for MRS. For one thing, if some link of G has relatively large usage rate, $α_{G}$ , the congestion factor of whole network is not able to judge the good MRS from the bad ones. For another, to further reduce the network minimization, it is needed to disperse the data flow into those links with relatively low usage rate. Hence, $α_{T}$ is a better judgement for MRS than $α_{G}$ . According to above analysis, problem of multipath routing for congestion minimization under time delay constraint (MCMTD) can be proposed as follows.

Problem MCMTD:

Minimize $α_{T}$ , s.t: (1)

$T (S, D, γ, L) = {G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}}), X (E_{G^{L}})}$ satisfies Definition 6.

(2)

For all $e \in E_{G^{L}}$ , $x (e) + c_{e}^{u} \leq α_{T} c_{e}$ .

3. Multipath Routing Algorithm for Congestion Minimization

Problem MCMTD can be summarized as constructing MRS to minimize $α_{T}$ . To achieve this aim, we need the following two phases. (1)

Obtain one L-DAG ${\hat{G}}_{S, D}^{L}$ , which includes as many links as possible.

(2)

Allocate data flow into links of ${\hat{G}}_{S, D}^{L}$ , which has relatively lower link capacity use rate.

3.1. Obtain ML-DAG

Let $G_{S, D}^{L}$ be an initial L-DAG then, according to Definitions 4 and 5, the ML-DAG, ${\hat{G}}_{S, D}^{L}$ , can be obtained through gradually adding nodes and links to $G_{S, D}^{L}$ , until the no circle property, closure property, or time delay constraint cannot be maintained. The procedure of obtaining ML-DAG includes two phases.

3.1.1. Network Simplification

Network simplification is helpful to exclude nodes and links with relatively long distance from S and D, so that the scale of original network can be reduced and further algorithm of obtaining ML-DAG can be simplified. To achieve this aim, the concept of distance between two nodes should be defined.

Definition 8.

Given G, for all $v_{i}, v_{j} \in V_{G}$ , the distance from $v_{i}$ to $v_{j}$ in G, $d_{G} (v_{i}, v_{j})$ is defined as follows. (1)

If no path exists from $v_{i}$ to $v_{j}$ in G, $d_{G} (v_{i}, v_{j}) = \infty$ .

(2)

Else, if ${\hat{p}}_{v_{i} v_{j}}^{G}$ is the shortest path from $v_{i}$ to $v_{j}$ in G, then $d_{G} (v_{1}, v_{2}) = d ({\hat{p}}_{v_{i} v_{j}}^{G})$ .

According to above definition, the distance between two nodes corresponds to the length of shortest path between two nodes, which leads to the following two theorems.

Theorem 9.

If $G_{1} \subset G$ , $v_{i}, v_{j} \in V_{G_{1}}$ , then $d_{G_{1}} (v_{i}, v_{j}) \geq d_{G} (v_{i}, v_{j})$ .

Proof.

Consider the following three situations. (1)

If $d_{G} (v_{i}, v_{j}) = \infty$ , then no path exists from $v_{i}$ to $v_{j}$ in G. Since $G_{1} \subset G$ , no path exists from $v_{i}$ to $v_{j}$ in $G_{1}$ . Hence, $d_{G_{1}} (v_{i}, v_{j}) = \infty$ , and $d_{G_{1}} (v_{i}, v_{j}) \geq d_{G} (v_{i}, v_{j})$ holds.

(2)

If $d_{G} (v_{i}, v_{j}) \neq \infty$ and $d_{G_{1}} (v_{i}, v_{j}) = \infty$ , then $d_{G_{1}} (v_{i}, v_{j}) \geq d_{G} (v_{i}, v_{j})$ holds.

(3)

If $d_{G} (v_{i}, v_{j}) \neq \infty$ and $d_{G_{1}} (v_{i}, v_{j}) \neq \infty$ , let ${\hat{p}}_{v_{i} v_{j}}^{G_{1}}$ be the shortest path from $v_{i}$ to $v_{j}$ in $G_{1}$ , then ${\hat{p}}_{v_{i} v_{j}}^{G_{1}} \subset G$ , which denotes that $d_{G} (v_{i}, v_{j}) = d ({\hat{p}}_{v_{i} v_{j}}^{G}) \leq d ({\hat{p}}_{v_{i} v_{j}}^{G_{1}}) = d_{G_{1}} (v_{i}, v_{j})$ .

In summation, Theorem 9 is proved.

Theorem 10.

Given ML-DAG, ${\hat{G}}_{S, D}^{L} (V_{\hat{G}}, E_{\hat{G}})$ , and $v \in (V_{G})$ , if $d_{G} (S, v) + d_{G} (v, D) > L$ , then $v \notin V_{\hat{G}}$ .

Proof.

Assume that $v \in V_{\hat{G}}$ ; then $d_{{\hat{G}}_{S, D}^{L}} (S, v) + d_{{\hat{G}}_{S, D}^{L}} (v, D) \leq L$ , which conflicts with $d_{{\hat{G}}_{S, D}^{L}} (S, v) + d_{{\hat{G}}_{S, D}^{L}} (v, D) \geq d_{G} (S, v) + d_{G} (v, D) > L$ . So the theorem is proved.

According to above two theorems, if $d_{G} (S, v) + d_{G} (v, D) > L$ , then v does not belong to ${\hat{G}}_{S, D}^{L}$ and should be excluded. Hence, the algorithm of network simplification is as follows.

Algorithm 11.

Network simplification is as follows. Input:

$G (V, E)$ , L, S, D.

Step 1:

If $d_{G} (S, D) \leq L$ , let $G_{r} = G$ , go to Step 2; else, algorithm fails.

Step 2:

For any $v \in V_{G_{r}}$ , if $d_{G_{r}} (S, v) + d_{G_{r}} (v, D) > L$ , $V_{G_{r}} = V_{G_{r}} ∖ {v}$ , $E_{G_{r}} = E_{G_{r}} ∖ (I_{G_{r}} (v) ⋃ O_{G_{r}} (v))$ . When all notes have been traversed, output $G_{r}$ .

3.1.2. Expanding Algorithm to Obtain ML-DAG

As mentioned before, ML-DAG can be obtained through gradually adding nodes and links. Each adding step is called expanding operation, as defined below.

Definition 12.

Expanding operation (OR) from $G_{i}^{L}$ to $G_{i + 1}^{L}$ , namely, $G_{i + 1}^{L} = E O (G_{i}^{L})$ , satisfies the following. (1)

$G_{i}^{L}$ and $G_{i + 1}^{L}$ are both L-DAG.

(2)

Simple path $p_{v_{i}, v_{j}}^{add} \subset G_{r}$ , such that $v_{i}, v_{j} \in V_{G_{i}^{L}}$ , $p_{v_{i}, v_{j}}^{add} ∖ {v_{i}, v_{j}} \subset V_{G_{r}} ∖ V_{G_{i}^{L}}$ , $E_{v_{i}, v_{j}}^{add} \subset E_{G_{r}} ∖ E_{G_{i}^{L}}$ .

(3)

$G_{i + 1}^{L} = G_{i}^{L} ⋃ p_{v_{i}, v_{j}}^{add}$ .

Expanding operation satisfies the following theorem.

Theorem 13.

Given $G_{i}^{L}$ , $G_{i + 1}^{L}$ , which satisfies $G_{i + 1}^{L} = E O (G_{i}^{L})$ , let $\bar{P_{v_{i}, v_{j}}^{G_{i}^{L}}}$ and $\bar{P_{v_{i}, v_{j}}^{G_{i + 1}^{L}}}$ be the longest path from S to D in $G_{i}^{L}$ and $G_{i + 1}^{L}$ , respectively, then $d (\bar{P_{v_{i}, v_{j}}^{G_{i}^{L}}}) \geq \bar{P_{v_{i}, v_{j}}^{G_{i + 1}^{L}}}$ .

Proof.

Since $\bar{P_{v_{i}, v_{j}}^{G_{i}^{L}}} \subset G_{i}^{L} \subset G_{i + 1}^{L}$ and $\bar{P_{v_{i}, v_{j}}^{G_{i + 1}^{L}}}$ is the longest path of $G_{i + 1}^{L}$ , according to the concept of longest path, $d (\bar{P_{v_{i}, v_{j}}^{G_{i}^{L}}}) \geq \bar{P_{v_{i}, v_{j}}^{G_{i + 1}^{L}}}$ .

Let $G_{0}^{L} = p_{\min}^{G_{r}} (S, D)$ , namely, the shortest path from S to D is chosen to be the initial L-DAG. According to Theorem 13, ${\hat{G}}_{S, D}^{L}$ can be obtained through finite times of EOs, since $G_{r}$ is a graph with finite links and each EO adds new links to $G_{i}^{L}$ . In order to make sure of the completeness and efficiency of the entire process to obtain ML-DAG, we have to figure out a principle of expanding operation. Considering that each expanding may probably increase the length of the longest path from S to D, which is a negative influence on the time delay constraint, our expanding operation follows the principle that the increase length of longest path after each expanding can be minimized. To achieve this objective, several examples in Figure 3 are proposed to show a phenomenon.

Figure 3

Examples of adding path to L-DAG.

Assuming time delay of all links equals 1, then each graph in above figure is described as follows. (a)

Original L-DAG, $G_{i}^{L}$ is a graph with two paths from S to D. Nodes of $G_{i}^{L}$ can be divided into layers as, L1: S; L2: $v_{1}$ , $v_{2}$ ; L3: $v_{3}$ , $v_{4}$ ; L4: $v_{5}$ , $v_{6}$ ; L5: D. One of the longest path from S to D is $S \to v_{1} \to v_{3} \to v_{5} \to D$ , time delay of which is 4.

(b)

Let $(v_{2}, v_{3})$ be the adding path, where layer of $v_{2}$ is lower than layer of $v_{3}$ , then longest path does not change.

(c)

Let $(v_{2}, v_{1})$ be the adding path, where layer of $v_{2}$ and $v_{1}$ are in the same layer, then the longest path becomes $S \to v_{2} \to v_{1} \to v_{3} \to v_{5} \to D$ , time delay of which is 5.

(d)

Let $(v_{4}, v_{1})$ be the adding path, where layer of $v_{4}$ is lower than layer of $v_{1}$ , then longest path becomes $S \to v_{2} \to v_{4} \to v_{1} \to v_{3} \to v_{5} \to D$ , time delay of which is 6.

These examples show that adding one path from lower layer to the higher layer is a better choice than adding one path from the higher layer to the lower one, according to the principle mentioned above. Our algorithm to obtain the ML-DAG is based on this phenomenon. Algorithm of acquiring ML-DAG (Algorithm 18) is illustrated through the flow chart in Figure 4.

Figure 4

Entire flow chart of Algorithm 18.

Some modular of the flow chat is explained as shown in Figure 4. M1

Two layers, $l_{i_{1}}$ and $l_{i_{2}}$ , are chosen according to the following procedure. For each $G_{i}^{L}$ , let q be the layer gap, such that $q = i_{2} - i_{1}$ . Initially, set $q = k - 1$ . Then, gradually reduce q from $k - 1$ , $k - 2, \dots, 0, - 1$ , to $- (k - 1)$ , when two new layers need to be chosen. If $q = - (k - 1)$ and no appropriate layers can be found so that adding path exists from $i_{1}$ to $i_{2}$ , then M1 returns false.

M2 is used to find $v_{1} \in V_{G_{l_{1}}}$ and $v_{2} \in V_{G_{l_{2}}}$ . If all nodes that belong to $l_{i_{1}}$ , $l_{i_{2}}$ have been traversed and no appropriate expanding path can be obtained, then M2 returns false.

$G_{T}$ satisfies that $V_{G_{T}} = (V_{G_{r}} ∖ G_{i}^{L}) ⋃ {v_{1}, v_{2}}$ and $E_{G_{T}} = E_{G_{i}^{L}} ⋃ {e | e \in G_{r}, H (e), I (e) \in V_{G_{T}}}$ .

M4 judges whether path from $v_{1}$ to $v_{2}$ in $G_{T}$ exists.

M5 judges whether adding one path from $v_{1}$ to $v_{2}$ generates one circle.

$G^{c} = G_{i}^{L} ⋃ {\hat{P}}_{v_{1}, v_{2}}^{G_{T}}$ , and $\bar{P_{S, D}^{G^{c}}}$ is the longest path from $v_{1}$ to $v_{2}$ in $G_{T}$ .

M7 judges whether time delay constraint still holds after expanding operation.

The completeness of above algorithm is guaranteed by next theorem.

Theorem 14.

ML-DAG, ${\hat{G}}_{S, D}^{L}$ , can be obtained through Figure 4.

Proof.

To prove the theorem, it should be shown that all possible adding paths have been considered when algorithm ends. In the beginning of each expanding operation, it can be guaranteed that $G_{i}^{L}$ is a DAG and can be divided into layers. Hence, adding paths can be obtained through the following steps. First, find two layers $l_{i_{1}}$ and $l_{i_{2}}$ through M2. Second, choose two nodes $v_{1}$ , $v_{2}$ belonging to those two layers, respectively, through M3. Third, obtain one adding path from $v_{1}$ to $v_{2}$ through M3, M4, M5, and M6. Since M1 traverses all layer pairs, M2 traverses all nodes pairs belonging to those two layers, and the correctness of adding path can be ensured through M5, M6 and M7; when M1 returns false, all possible adding paths have been considered. Therefore, Theorem 14 is proved.

3.2. Obtain Minimul Congestion Factor

After obtaining ${\hat{G}}_{S, D}^{L}$ , the minimal congestion factor of MRS, $α_{T}$ , can be obtained through allocating data flow into links with low capacity use rate. To achieve this objective, partial capacity graph needs to be considered.

Definition 15.

Given one L-DAG, $G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}})$ , β-partial capacity graph, $G_{S, D}^{β} (V_{G^{β}}, E_{G^{β}})$ , satisfies the following: (1)

$G_{S, D}^{β}$ and $G_{S, D}^{L} (V_{G^{L}}, E_{G^{L}})$ have the same topology, namely, $V_{G^{β}} = V_{G^{L}}$ , $E_{G^{β}} = E_{G^{L}}$ ;

(2)

for all $e \in E_{G^{β}}$

\begin{matrix} c_{e}^{β} = {\begin{cases} β c_{e} - c_{e}^{u}, & if c_{e}^{u} / c_{e} < β, \\ 0, & if c_{e}^{u} / c_{e} \geq β . \end{cases} \end{matrix}

(2)

Furthermore, the residual graph after data flow distribution is defined as follows.

Definition 16.

Given one L-DAG, $G^{β} (V_{G^{β}}, E_{G^{β}})$ , and the data flow distribution, $X (G^{β}) = {x^{β} (e) | 0 \leq x^{β} (e) \leq c}$ , the residual graph, $G_{X}^{β} (V_{G_{X}^{β}}, E_{G_{X}^{β}})$ , satisfies (1)

$E_{G_{X}^{β}} = {e \in E_{G^{β}} x^{β} (e) > 0}$ ,

(2)

$V_{G_{X}^{β}} = {v \in V_{G^{β}} | \exists e \in I_{G^{β}} (v), x^{β} (e) > 0, or \exists e \in O_{G^{β}} (v), x^{β} (e) > 0}$ .

Based on above definitions, $α_{T}$ can be obtained through gradually adjusting β, until $μ (β)$ sufficiently approaches γ, namely, $μ (β) \approx γ$ , where $μ (β)$ denotes the max-flow [12] from S to D in $G_{S, D}^{β}$ . The feasibility of above adjusting process can be guaranteed through the following theorem.

Theorem 17.

$μ (β)$ is a monotone increasing and continuous function with $β \in [0,1]$ .

Proof.

Let $X (β) = {x^{β} (e) | x^{β} (e) \leq c_{e}^{β}, e \in E_{G_{S, D}^{L}}}$ be the distribution of $μ (β)$ on each link $G_{S, D}^{L}$ . (1)

Proof of monotone increasing is as follows:

for all $0 \leq β_{1} < β_{2} \leq 1$ , $c_{e}^{β_{1}} \leq c_{e}^{β_{2}}$ , then $\forall e \in E_{G_{S, D}^{β}}$ , $x^{β_{1}} \leq c_{e}^{β_{1}} \leq c_{e}^{β_{1}}$ . So $X (β_{1})$ is also the distribution of one available network flow on $G_{S, D}^{β_{2}}$ . Hence, $μ (β_{1}) \leq μ (β_{2})$ .

(2)

Proof of continuous is as follows:

according to Definition 15, for all $β^{*} \in [0,1]$ , if $β \to β^{*}$ , $c_{e}^{β} \to c_{e}^{β^{*}}$ , which eventually leads to $μ (β) \to μ (β^{*})$ .

Above theorem indicates that $α_{T}$ can be obtained through adjusting β. In order to accelerate the adjustment, an algorithm analogous to binary search [13] is proposed as follows.

Algorithm 18.

Obtain minimal congestion factor of MRS. Input

${\hat{G}}_{S, D}^{L}$ , S, D, γ, ${c_{e} | e \in E_{\hat{G}}}$ , ${c_{e}^{u} | e \in E_{\hat{G}}}$ , η.

Step 1

Let $β_{L} = 0$ and $β_{R} = 1$ . If $μ (β_{R}) < γ$ , return false; else, let $β = β_{R}$ go to Step 3.

Step 2

Let $β = (1 / 2) β_{L} + β_{R}$ , go to Step 3.

Step 3

Obtain $G_{S, D}^{β}$ , $μ (β)$ , and the corresponding data flow distribution, $X (G_{S, D}^{β})$ , go to Step 4.

Step 4

If $μ (β) > (1 + η) \cdot γ$ , let $β_{R} = β$ , go to Step 2;

else if $μ (β) < (1 - η) \cdot γ$ , let $β_{L} = β$ , go to Step 2;

else if $(1 - η) \cdot γ \leq μ (β) \leq (1 + η) \cdot γ$ , go to Step 5.

Step 5

Let $α_{T} = β$ .

Let $G_{S, D}^{f} (V_{G^{f}}, E_{G^{f}}) = G_{X}^{β}$ , where $G_{X}^{β}$ is the residual graph corresponding with $G_{S, D}^{β}$ and $X (G_{S, D}^{β})$ , according to Definition 16.

Let $X (G_{S, D}^{f}) = {x (e) | e \in E_{G^{f}}}$ .

Return $α_{T}$ , $G_{S, D}^{f} (V_{G^{f}}, E_{G^{f}})$ , and $X (G_{S, D}^{f})$ .

3.3. Time Complexity Analysis

Let $N_{V}$ and $N_{E}$ be the entire nodes number and links number, respectively. Time complexity analysis of each algorithm is as follows. Algorithm 11 can be completed via the construction of two Dijkstra trees [12], with complexity $O (N_{V}^{2})$ , and the traversing of all nodes on the graph, with complexity $O (N_{V})$ , hence time complexity of Algorithm 11 is $O (N_{V}^{2})$ . In Figure 4, each expanding operation consists of layer algorithm ( $O (N_{V} + N_{E})$ ), shortest path algorithm ( $O (N_{V}^{2})$ ) [12], and longest path algorithm ( $O (N_{V} + N_{E})$ ) [11]. Hence, each expanding procedure can be finished in $O (N_{V}^{2} \cdot (N_{V}^{2} + N_{E}))$ , which is the worst case when no node and link are excluded after Algorithm 11 and each pair of nodes has been traversed. Considering that at least one link can be added in each expanding operation, entire algorithm can be finished in $O (N_{V}^{2} \cdot N_{E} \cdot (N_{V}^{2} + N_{E}))$ in the worst case. In Algorithm 18, let $μ (β^{*}) = γ$ , then, after $⌈ \log_{2} (1 / η) ⌉$ iterations, $β \in [(1 - β) \cdot β^{*}, (1 + β) \cdot β^{*}]$ satisfies, and Algorithm 18 ends. Each iteration needs a max-flow algorithm, with time complexity $O (N_{V}^{2} \cdot N_{E})$ in the worst case. Hence, Algorithm 18 can be finished in $O (N_{V}^{2} \cdot N_{E} \cdot ⌈ lo g_{2} (1 / η) ⌉)$ . In summary, time complexity of entire algorithm is

\begin{array}{l} O (N_{V}^{2}) + O (N_{V}^{2} \cdot N_{E} \cdot (N_{V}^{2} + N_{E})) \\ + O (N_{V}^{2} \cdot N_{E} \cdot ⌈ \log_{2} (\frac{1}{η}) ⌉) \\ = O (N_{V}^{2} \cdot N_{E} \cdot (N_{V}^{2} + N_{E} + ⌈ \log_{2} (\frac{1}{η}) ⌉)), \end{array}

(3)

which is polynomial time complexity with

N_{V}

and

N_{E}

4. Simulation and Analysis

4.1. Introduction to Basic Network Environment

The simulation network, $G (V, E)$ , is formulated as a Transit-Stub Domain [14], where the connection probability between any two nodes is initially set to be 0.01. Basic parameters of capacity and time delay are as follows. (i)

For $\forall e \in E$ , let link capacity, $c_{e}$ , and average used capacity, $\bar{c_{e}^{u}}$ , be 1 M bps and 0.5 M bps, respectively. Let current used capacity, $c_{e}^{u}$ , be randomly chosen between $(1 - θ) \bar{c_{e}^{u}}$ and $(1 + θ) \bar{c_{e}^{u}}$ , where $θ = 0.3$ . Let the data sent quantity from S to D be $γ = 0.3$ M bps.

(ii)

For $\forall e \in E$ , let $d (e) = 1$ . For any given source node, S, and destination node, D, $d_{G} (S, D) = 4$ holds. Time delay constraint $L = 6$ .

4.2. Simulation and Comparison Analysis

As mentioned before, our DAG based multipath routing algorithm (DAGMR) does not satisfy the path disjoint constraint; hence, performance of DAGMR should be compared with “Split Multipath Routing Algorithm with Maximally Disjoint Paths (SMR)” [9], which is a typical algorithm that follows the path disjoint constraint.

First, the most important performance for the load balancing in Machine-to-Machine network is the congestion factor of MRS, which is illustrated in Figure 5.

Figure 5

Simulation result of congestion factor with the change of network nodes number. (a) denotes final congestion factor of two algorithms. (b) denotes final congestion factor ratio of our algorithm to SMR.

Figure 5 indicates that DAGMR obtains lower congestion factor than SMR, and the congestion factor gap of two algorithms increases as the nodes number in whole network increases. Moreover, when more than 200 nodes exist in network, congestion factor obtained by DAGMR is $5 %$ smaller than that obtained by SMR.

Second, DAGMR is helpful to distribute the data flow into more nodes and links, so as to ease the burden of certain overused nodes, as mentioned before. Hence, the number of nodes and links in the final multipath graph of DAGMR should be checked and compared with that of SMR.

Figure 6 indicates that nodes and links number in final routing graph obtained by DAGMR is larger than that obtained by SMR, and the gap of nodes and links number obtained in final routing graph by two algorithms increases as the network nodes number increases. Moreover, when entire network has more than 200 nodes, DAGMR subsumes $20 %$ more nodes and links than SMR.

Figure 6

Simulation result of nodes and links number in final routing graph with the change of entire network nodes number. (a) denotes the final multipath graph nodes number of DAGMR and SMR. (b) denotes the ratio of final multipath graph nodes number of DAGMR to SMR. (c) denotes the final multipath graph links number of DAGMR and SMR. (d) denotes the ratio of final multipath graph links number of DAGMR to SMR.

In above simulations, the connection probability of any two nodes is a fixed value, and performance about different nodes number is illustrated. Next, let the nodes number of whole network be fixed as 300 and let connection probability of any two nodes be changed from 0.008 to 0.015. Then, congestion factor of MRS is illustrated in Figure 7.

Figure 7

Simulation result of congestion factor with the change of connection probability between any two nodes when entire network nodes number is 300. (a) denotes the congestion factor of final multipath graph of DAGMR and SMR. (b) denotes the congestion factor ratio of DAGMR to SMR.

Figure 7 indicates that DAGMR obtains lower congestion factor than SMR, and the congestion factor gap of two algorithms increases as the connection probability increases. Moreover, when connect rate is larger than 0.09, congestion factor obtained by DAGMR is $5 %$ lower than that obtained by SMR.

Furthermore, the throughput performance of DAGMR should be analyzed. Given source node, S, destination node, D, and time delay constraint L, let $α^{R}$ be the restricted congestion factor of MRS, namely, for any $T (S, D, γ, L)$ , according to Definition 6, $α_{T} \leq α^{R}$ holds. Then, maximum data throughput, $γ_{\max}$ , can be obtained through DAGMR, where second phase of the algorithm should be changed to obtain the maximum throughput under restricted congestion factor of $α^{R}$ . Let the basic parameter of network be the same as before, where $d_{G} (S, D) = 4$ and time delay constraint $L = 6$ . Let the restrict congestion factor be changed from 0.5 to 1. Then throughput performance of network with 200, 300, 400, 500 nodes is illustrated in Figures 8, 9, 10, and 11.

Figure 8

Simulation result of data throughput with the change of restricted congestion factor, when entire nodes number is 200.

Figure 9

Simulation result of data throughput with the change of restricted congestion factor, when entire nodes number is 300.

Figure 10

Simulation result of data throughput with the change of restricted congestion factor, when entire nodes number is 400.

Figure 11

Simulation result of data throughput with the change of restricted congestion factor, when entire nodes number is 500.

Figures 8, 9, 10, and 11 indicate the following aspects. (i)

Throughput increases as the network nodes number increases, which is reasonable, since the more the nodes exist in network, the more the opportunity is to get extra routing path.

(ii)

Throughput obtained by DAGMR is larger than that obtained by SMR, and the gap of throughput increases as the restricted congestion factor increases.

(iii)

The throughput ratio between DAGMR and SMR is larger than 1 and reaches the peak value when restricted congestion factor is about 0.65.

In summation, our DAG based multipath routing algorithm (DAGMR) achieves lower congestion factor and subsumes more nodes and links in the final multipath subgraph than SMR, when data sent quantity is fixed in a flow session. Meanwhile, when restricted congestion factor is fixed, DAGMR obtains larger data throughput than SMR. Therefore, DAGMR is a better choice for network load balancing in Machine-to-Machine networks.

5. Conclusion

Multipath routing is a useful method to balance network load and reduce congestion and has received extensive research. However, most of previous multipath routing algorithms are not able to fully utilize the advantage of multipath, due to the premise that routing paths should be disjoint. In this paper, a new multipath algorithm is proposed, in which the path disjoint constraint is replaced by a principle that multipath should be confined into a directed acyclic graph under time delay constraint. Meanwhile, the partial capacity network is proposed, in order to obtain the final multipath congestion factor. Simulation shows that our algorithm achieves lower congestion factor and subsumes more nodes and links than the classical split multipath routing algorithm with disjoint paths. In addition, our algorithm is a polynomial time complexity algorithm with nodes number and links number of the entire network.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported by the National Nature Science Foundation of China (nos. 61171069, 61231013, and 60933012), the 973 Program of China under Grant 2011CB707000, and the National 863 Program of China no. 2011AA110102.

References

Fadlullah

Z. M.

Fouda

M. M.

Kato

Takeuchi

Iwasaki

Nozaki

Toward intelligent machine-to-machine communications in smart grid

IEEE Communications Magazine 2011 49 4 60 65

2-s2.0-79953792812

10.1109/MCOM.2011.5741147

Singh

S. K.

Singh

M. P.

Singh

D. K.

A survey of energy-efficient hierarchical cluster-based routing in wireless sensor networks

International Journal of Advanced Networking and Applications 2010 2 2 570 580

Banner

Orda

Multipath routing algorithms for congestion minimization

IEEE/ACM Transactions on Networking 2007 15 2 413 424

2-s2.0-34247279630

10.1109/TNET.2007.892850

Yang

Liu

Dong

A bandwidth aware multi-path routing protocol in mobile Ad Hoc networks

Journal of Computational Information Systems 2011 7 3 685 696

2-s2.0-79953742779

Mérindol

Pansiot

J.-J.

Cateloin

Low complexity link state multipath routing

Proceedings of the IEEE INFOCOM Workshops (GIS '09)

April 2009

Rio de Janeiro, Brazil

2-s2.0-70349667806

10.1109/INFCOMW.2009.5072161

Mérindol

Francois

Bonaventure

Cateloin

Pansiot

J.-J.

An efficient algorithm to enable path diversity in link state routing networks

Computer Networks 2011 55 5 1132 1149

2-s2.0-79952450686

10.1016/j.comnet.2010.11.005

Jiang

Dai

Zhou

Liu

A novel MPR approach based on inverse-traversing of Multi-Labeled tree

Proceedings of the IEEE International Conference on Intelligent Computing and Integrated Systems (ICISS '10)

October 2010

Guilin, China

273 276

2-s2.0-78651425230

10.1109/ICISS.2010.5657149

Bruni

Delli Priscoli

Koch

Pietrabissa

Pimpinella

Multipath routing by network decomposition and traffic balancing

Proceedings of the Future Network and Mobile Summit

June 2010

Florence, Italy

2-s2.0-79952925201

Lee

S.-J.

Gerla

Split multipath routing with maximally disjoint paths in Ad hoc networks

Proceedings of the International Conference on Communications (ICC '01)

June 2000

3201 3205

2-s2.0-0034844688

10.

Hong

K.-S.

Choi

DAG-based multipath routing for mobile sensor networks

Proceedings of the International Conference on ICT Convergence (ICTC '11)

September 2011

Seoul, Korea

261 266

2-s2.0-83755220099

10.1109/ICTC.2011.6082593

11.

Ioannidou

Nikolopoulos

S. D.

The longest path problem is polynomial on cocomparability graphs

Algorithmica 2013 65 1 177 205

2-s2.0-80054861273

10.1007/s00453-011-9583-5

12.

Ahuja

R. K.

Magnanti

T. L.

Orlin

J. B.

Network Flows: Theory, Algorithms, and Applications 1993

Upper Saddle River, NJ, USA

Prentice- Hall

13.

Nowak

Generalized binary search

Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing

September 2008

Urbana-Champaign, Ill, USA

568 574

2-s2.0-64549161997

10.1109/ALLERTON.2008.4797609

14.

Calvert

K. L.

Doar

M. B.

Zegura

E. W.

Modeling internet topology

IEEE Communications Magazine 1997 35 6 160 163

2-s2.0-0000178416

10.1109/35.587723