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

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.