Improved design of load balancing for multipath routing protocol

Abstract

In this paper, an improved routing protocol for multipath network load balancing is proposed for defects in the traditional AOMDV (Ad hoc On-demand Multipath Distance Vector) protocol. This research work analyzes problems in traditional routing protocols and estimates the available path load according to network transmission in Wireless Mesh Networks (WMN). Moreover, we design a load distribution scheme according to a given load and improve multi-path load balancing by using the MCMR method. We also control path discovery and the number of paths while also establishing routing paths and probability balancing. Lastly, improvements are made to the AOMDV protocol and efficient data transmission is acheived. The performance results of the modified routing protocol show that the designed protocol can improve successful delivery rate and prolong network survival time.

1. Introduction

Wireless Mesh Networks (WMN) are special multi-hop wireless networks [16], which aim to be wireless backbone networks providing higher transmission performance that has both higher bandwidth and lower transmission latency. At this stage, although the bandwidth of wireless networks has improved greatly, compared with traditional self-assembled networks [6] and/or fiber networks [1] with higher bandwidth, the bandwidth resources of wireless networks still have significant limitations. The problem of the scarcity of wireless network bandwidth resources has gradually become prominent. Secondly, the resource utilization of wireless networks is generally low. A wireless link is different from a wired link [5]. All adjacent wireless devices working in the same frequency band share a common channel, which will generate an energy correlation factor [19]. Therefore, there will be very obvious common channel interference between wireless links. In a multi-hop wireless network, different streams need to compete with each other for network resources such as nodes, channels, antennas, and similar resource competition exists between pre-hop and post-hop transmission or even multi-hop transmission of the same stream. Therefore, it is necessary to design special network protocols for WMN characteristics to achieve optimal allocation of network resources to improve transmission performance in WMN. A routing protocol is an important part of any network protocol. Based on the characteristics of WMN and their relationship with other wireless network technologies, routing technology is a core feature of WMN technology. Therefore, multi-route routing technology has become a popular technology used to improve transmission performance in multi-hop wireless networks [17].

To optimize resource utilization of wireless networks, improve transmission throughput, and reduce transmission delay to provide strong support for applications on the network, some of the better load balancing routing protocols are currently proposed by scholars in related fields. Alghamdi et al. [2] proposed a load balancing on-demand multipath routing protocol based on the Cuckoo algorithm. The cuckoo search algorithm is used to specify the best routing path based on residual energy of each node to balance routing overhead among various nodes involved in routing. The routing scheme is optimized in terms of packet delivery rate, battery life, as well as minimum packet delay time.

Yassien et al. [22] proposed a load-balanced routing protocol for a low-power lossy network based on a remote start service. The remote startup service was integrated into the active routing protocol with an IPV6 distance vector, and a time-based load balancing method was proposed. Considering the number of neighbor nodes and the power of remaining nodes, an improved trickle-down timer algorithm was designed. By using this algorithm, the grid and random network topology are deployed and the load balancing routing protocol is improved. RM et al. [18] proposed an Internet of Things (IoT) architecture based on energy efficiency in the cloud. The authors used wind driven optimization algorithm to cluster various IoT networks, optimize energy utilization, and used the Firefly algorithm to select an optimized cluster head for each cluster, reducing data traffic. Wang et al. [20] established a system model considering the active probability in order to obtain indicators under leaky channel access attacks. From the perspective of ordinary potential games, the authors proposed the problem of minimizing AoI based on channel access, and determined a channel access strategy through AACSD and DCASD algorithms. Although the above four protocols have achieved decent results in current applications, in practice there are still problems with uneven energy consumption, resulting in high redundancy, especially in WMN, where the uneven energy consumption is particularly serious, network survival time is short, and probability of achieving successful data transmission is poor.

To address these problems, this paper proposes a load-balancing routing protocol for multipath networks based on probabilistic splitting. Through analysis of the problems existing in traditional routing protocols, we propose the use of multipath routing to design a load balancing algorithm to create a solution by first calculating the path residual capacity according to the transmission process of the dual state wireless link. Next, we make use of the MCMR method to improve the design of multipath load balancing method which helps to control path discovery and path number. Finally, we improve the AOMDV protocol by establishing routing paths and probability balancing to achieve efficient data transmission.

2. Design of load balanced routing protocols for multipath networks

2.1. Problem analysis and solution ideas

Traditional routing protocols can discover multiple acyclic and unrelated paths, which greatly improves network reliability and throughput, but also has some shortcomings. The AOMDV energy-saving routing protocol is taken as an example [12].

1. In the protocol, only “hop count” is used as routing criterion, so that data flow is concentrated on the central node, resulting in local congestion of the network, which is not conducive to the load balance of the network. Therefore, the routing criterion of the AOMDV protocol should be improved.

2. In WMN, network topology is relatively stable, but the use of backup paths to avoid link failures due to node movement is not the key to improving network performance and does not take full advantage of the diversity of paths. A network with relatively fixed nodes is better suited to use multiple paths for parallel transmission, so the AOMDV protocol should be improved to make it capable of multipath concurrent transmission.

3. In a protocol, the path usage order is determined according to the path discovery sequence. However, the path discovered earlier is not necessarily the optimal path, which should consider many factors such as path load and interference between paths.

4. The use of multipath routing to solve the load balancing problem requires a load distribution policy based on the priority of the paths and the path conditions.

Based on the above shortcomings of the traditional AOMDV protocol, this paper proposes an improved approach.

The design of a load balancing algorithm using multipath routing can be divided into the following phases: (1) establishing the transmission model of WMN; (2) designing the routing criterion; (3) finding the routing; (4) estimating the load situation of available paths and designing a load distribution scheme based on the load situation. Thus, it is not only possible to avoid congested paths in the route discovery phase, but also to reasonably allocate the load to alleviate congestion when it occurs.

We adhere to the following assumptions made in the study: for the WMN backbone, the nodes in the network represent WMN routers; the power consumption effect of nodes is completely ignored; the configuration conditions on each node are identical, including transmission distance between nodes, interference distance, number of antennas configured on nodes, number of available channels, etc. In addition, channels of the control messages are fixed.

2.2. Calculation of relevant indicators

2.2.1. Analysis of the network transmission process of WMN

After analyzing the problems of traditional routing protocols and providing solutions, we investigate the calculation of relevant indicators. We define a WMN as a directed graph $\mathit{G}\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{)}$ , where V denotes the set consisting of mesh nodes; E denotes the set of wireless links between nodes that can communicate with each other. In the WMN unicast routing problem, each routing path contains a source node ${\mathit{n}}_{\mathit{s}}\in \mathit{V}$ and a destination node ${\mathit{n}}_{\mathit{d}}\in \mathit{V}$ . The source and destination nodes are connected via multiplexed multi-hop wireless network nodes (i.e., mesh nodes) [11,21].

Wireless link $\mathrm{(}{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}\mathrm{)}\in \mathit{E}$ , Among them, ${\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}\in \mathit{V}$ , which is affected by channel noise and adjacent interference and is usually unreliable. The quality of a link ( ${\mathit{n}}_{\mathit{i}}$ , ${\mathit{n}}_{\mathit{j}}$ ) is described by the probability of failure ${\mathit{p}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ , which represents the probability of transmission failure on the link. Regardless of multi-rate transmission, wireless links can be modeled as A “two-state” model, at any given moment, each link is either completely “failed”, where the transmission rate is 0, or completely “available”, where the transmission rate is ${\mathit{r}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ . The availability probability of a link corresponds to the reciprocal value of the ETX route metric on the link, also known as the average availability probability. If the link quality changes significantly dynamically, the availability probability of a link can also be described by the instantaneous availability probability, which can be obtained utilizing online probing.

In the two-state model, once the transmitting node ${\mathit{n}}_{\mathit{i}}$ gains channel access, it will initiate packet transmissions to ${\mathit{n}}_{\mathit{j}}$ with a transmission rate of ${\mathit{r}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ . Since the wireless link ( ${\mathit{n}}_{\mathit{i}}$ , ${\mathit{n}}_{\mathit{j}}$ ) has transient uncertainty, its transmission has a failure probability ${\mathit{p}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ . If the transmission fails, ${\mathit{n}}_{\mathit{i}}$ has to wait for a while to regain access to the channel, which is called the “channel access interval”. The channel access interval at the transmitting node ${\mathit{n}}_{\mathit{i}}$ in the WMN is denoted as ${\mathit{\tau }}_{{\mathit{n}}_{\mathit{i}}}$ . The packet transmission process over a two-state wireless link is clearly shown in Fig. 1.

Fig. 1.

The transmission process of a two-state wireless link.

Assuming that the size of the reference packet is denoted as B and the probability of successful transmission of the link is ${\mathit{q}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ in Fig. 1, the transmission delay generated is $\mathit{B}\mathrm{/}{\mathit{r}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ , the probability of transmission failure is denoted as ${\mathit{p}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ , at which point the transmitting node ${\mathit{n}}_{\mathit{i}}$ must wait for ${\mathit{\tau }}_{{\mathit{n}}_{\mathit{i}}}$ time before acquiring the channel access opportunity again. Since the coherence time of a wireless channel in a WMN is usually greater than the time required for multiple consecutive transmissions, the probability of transmission failure is still ${\mathit{p}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}$ when the transmitting node ${\mathit{n}}_{\mathit{i}}$ gets another transmission opportunity. Then the delay required to complete the transmission on the link ( ${\mathit{n}}_{\mathit{i}}$ , ${\mathit{n}}_{\mathit{j}}$ ) is: $$\begin{array}{}\text{(1)}& \mathit{E}[\mathit{t}]={\displaystyle \frac{{\mathit{q}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}\frac{\mathit{B}}{{\mathit{\tau }}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}}+{\mathit{p}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}{\mathit{\tau }}_{{\mathit{n}}_{\mathit{i}}}}{{\mathit{q}}_{{\mathit{n}}_{\mathit{i}}\mathrm{,}{\mathit{n}}_{\mathit{j}}}}}\end{array}$$

Equation (1) uses the link failure probability in measuring the quality of WMN links, which reflects the inherent uncertainty characteristic of wireless transmission in WMN.

2.2.2. Calculation of the remaining capacity of the path

Based on the above WMN transmission process, we can calculate the remaining capacity of the path. Assume that U denotes a given path, T denotes the remaining capacity of the routing protocol for that path [14], and C denotes the capacity occupied by the data stream currently being transmitted on that path. However, the difference between the two is the remaining capacity of that path R. $$\begin{array}{}\text{(2)}& \mathit{R}=\mathit{T}-\mathit{C}\end{array}$$

In a real network, it is also necessary to add a smoothing factor to integrate the channel interference effects around the path [3,8], to better match the actual network environment, which gives an approximate expression for the theoretical residual capacity ${\mathit{T}}_1$ of the network path as follows in Equation (3). $$\begin{array}{}\text{(3)}& {\mathit{T}}_1\approx \mathit{\alpha }\times {\mathit{T}}_1^{\prime }\mathrm{,}\mathit{\alpha }\in \mathrm{(}0\mathrm{,}1]\end{array}$$ where ${\mathit{T}}_1^{\prime }$ denotes the optimal solution for the path fault tolerance [15], α denotes the smoothing factor, which can be determined manually at the beginning of network planning and deployment, or dynamically adjusted during operation to better suit the network conditions.

The capacity C occupied by the data stream currently being transmitted by the path is calculated as in Equation (4). $$\begin{array}{}\text{(4)}& \mathit{C}=max\mathrm{(}{\displaystyle \sum }_{\mathit{c}\mathit{h}\in \mathit{e}\mathrm{(}{\mathit{\upsilon }}_1\mathrm{)}\cup \mathit{e}\mathrm{(}\mathit{\upsilon }\mathrm{,}{\mathit{\upsilon }}_2\mathrm{)}}\mathit{u}\mathit{h}\mathrm{,}\forall \mathit{v}\in \mathrm{\Phi }\mathrm{)}\mathrm{,}\end{array}$$ where u represents the capacity experiment (including perceived usage by other surrounding nodes) ratio of the channel h in a period, as well as ${\mathit{\upsilon }}_1$ and ${\mathit{\upsilon }}_2$ denoting the precursor and successor nodes of the node υ on the path Φ, respectively.

Combining the above calculations yields the final computational expression for the remaining capacity R of the path as in Equation (5). $$\begin{array}{}\text{(5)}& \mathit{R}\approx \mathit{\alpha }\times {\mathit{T}}_1^{\prime }-max\mathrm{(}{\displaystyle \sum }_{\mathit{c}\mathit{h}\in \mathit{e}\mathrm{(}{\mathit{\upsilon }}_1\mathrm{)}\cup \mathit{e}\mathrm{(}\mathit{\upsilon }\mathrm{,}{\mathit{\upsilon }}_2\mathrm{)}}\mathit{u}\mathit{h}\mathrm{,}\forall \mathit{v}\in \mathrm{\Phi }\mathrm{)}\mathrm{,}\mathit{\alpha }\in \mathrm{(}0\mathrm{,}1]\end{array}$$

2.3. Multipath network load balancing method design

According to the residual capacity of the path, a multi-path network load balancing method is designed. The multi-channel multi-interface approach is also known as the multi-channel multi-antenna approach. Multiple antennas are configured for each node in the network and then the channels are assigned to the antennas [4,10], which is used to improve the efficiency of data transmission. Using MCMR (Multi-channel multi-radio) method multiple interfaces are configured for the nodes in the network and channels are assigned to these interfaces so that inter-channel conflicts can be effectively avoided. This paper will combine the above indicators to improve the design of the multi-path load balancing method.

2.3.1. MCMR network topology design

Assuming that n denotes the nodes in the network, l denotes the link, $\mathit{n}={\mathit{n}}_1\mathrm{,}\dots \mathrm{,}{\mathit{n}}_{\mathit{N}}$ , where N denotes the number of nodes in the network. In the MCMR network, individual nodes are configured with multiple antennas (interfaces), and a channel is assigned to each interface. Antennas can only communicate with each other when it is assigned the same channel and within the communication range.

Fig. 2.

MCMR network topology schematic.

In Fig. 2, circles represent nodes in the network, squares represent interfaces configured on the nodes and dashed lines between interfaces represent assigned channels. Interface 0 is configured on the node A, interfaces 1, 2 on the node B, and interfaces 3 and 4 on the node C. The inter-interface relationships can be represented by an undirected graph, calculated as in Equation (6). $$\begin{array}{}\text{(6)}& \mathit{M}\mathrm{(}{\mathit{r}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{j}}\mathrm{)}=\left\{\begin{array}{ll}1\mathrm{,}& \mathit{D}\mathrm{(}{\mathit{r}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{j}}\mathrm{)}\mathrm{<}\mathit{C}\mathrm{(}{\mathit{r}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{j}}\mathrm{)}\text{ and }{\mathit{N}}_{{\mathit{r}}_{\mathit{i}}}\ne {\mathit{N}}_{{\mathit{r}}_{\mathit{j}}}\\ 0\mathrm{,}& \text{otherwise}\end{array}\right.\end{array}$$ where, $\mathit{i}\ne \mathit{j}$ , ${\mathit{r}}_{\mathit{i}}$ , ${\mathit{r}}_{\mathit{j}}$ denote any two interfaces in the network, $\mathit{i}\mathrm{,}\mathit{j}\in [1\mathrm{,}\mathit{R}]$ , R denotes the number of interfaces in the network. Moreover, ${\mathit{R}}_{{\mathit{r}}_{\mathit{i}}}$ denotes the node where the interface ${\mathit{r}}_{\mathit{i}}$ is located, ${\mathit{R}}_{{\mathit{r}}_{\mathit{i}}}\ne {\mathit{R}}_{{\mathit{r}}_{\mathit{j}}}$ denotes the interface ${\mathit{r}}_{\mathit{i}}$ , ${\mathit{r}}_{\mathit{j}}$ and is not in the same node. $\mathit{D}\mathrm{(}{\mathit{r}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{j}}\mathrm{)}\mathrm{<}\mathit{C}\mathrm{(}{\mathit{r}}_{\mathit{i}}\mathrm{,}{\mathit{r}}_{\mathit{j}}\mathrm{)}$ denotes the interfaces ${\mathit{r}}_{\mathit{i}}$ , ${\mathit{r}}_{\mathit{j}}$ and can communicate normally, which indicates that there is a link between the interfaces ${\mathit{r}}_{\mathit{i}}{\mathit{r}}_{\mathit{j}}$ when the value is 1.

2.3.2. Design of routing criteria for load balancing in multipath network

In the AOMDV protocol, “hop count” is used as the routing criterion, which is easy to cause congestion in intermediate nodes and does not reflect the current load of the path explicitly. The study takes “interference” and “residual capacity” into consideration in the design of the routing criterion. First, the multipath interference model is established, and then the remaining capacity is taken as the current path load estimation. Finally, the interference-sensitive perceptive routing criterion is established considering the impact of interference on the path load to provide the basis for multi-path load balancing.

For the results of the inter-interface links calculated in Equation (6) above, the obtained links are numbered using L, $\mathit{L}\in [{\mathit{L}}_1\mathrm{,}{\mathit{L}}_{\mathit{l}}]$ . According to the current study, it is known that the links with the possibility of interference include two types. Two links sharing one interface and two links separated by one link. It is assumed that $\mathit{P}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}$ indicates the possibility of interference on a link( ${\mathit{L}}_{\mathit{i}}$ , ${\mathit{L}}_{\mathit{j}}$ ), ${\mathit{P}}^{\prime }\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}=1$ indicates the possibility of interference between the two links. Link interference is caused if two links with interference potential are assigned the same channel when communication is performed. The relationship is expressed as in Equation (7).

$$\begin{array}{}\text{(7)}& \mathit{I}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}=\left\{\begin{array}{ll}1\mathrm{,}& \mathit{P}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}\text{ and }\mathrm{(}\mathit{L}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}\mathit{c}\mathrm{)}=\mathit{L}\mathrm{(}{\mathit{L}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{)}\\ 0\mathrm{,}& \text{otherwise}\end{array}\right.\end{array}$$ where $\mathit{L}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}\mathit{c}\mathrm{)}=\mathit{L}\mathrm{(}{\mathit{L}}_{\mathit{j}}\mathrm{,}\mathit{c}\mathrm{)}$ indicates that both links ${\mathit{L}}_{\mathit{i}}$ and ${\mathit{L}}_{\mathit{j}}$ are assigned the same channel c, $\mathit{c}\in [1\mathrm{,}{\mathit{C}}^{\prime }]$ , ${\mathit{C}}^{\prime }$ indicates the total number of channels available in the network, $\mathit{I}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}=1$ indicates that there is actual interference between the two links.

• Total link interference

The interference present in a link is equal to the sum of the interference received by other links using the same channel. According to Equation (7), the interference received by the link ${\mathit{L}}_{\mathit{k}}$ in the network is expressed as in Equation (8). $$\begin{array}{}\text{(8)}& {\mathit{I}}_{{\mathit{L}}_{\mathit{k}}}={\displaystyle \sum }_{\mathit{i}=1}^{\mathit{l}}{\mathit{I}}_{\mathit{i}}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{k}}\mathrm{)}\end{array}$$ where ${\mathit{I}}_{{\mathit{L}}_{\mathit{k}}}$ denotes the sum of the actual interference in the network for any of the links ${\mathit{L}}_{\mathit{k}}$ in the network.

• Sum of path disturbances

There are multiple links on a path, and the sum of the interference each link receives from the other links is used as an indicator of the interference on a path. ${\mathit{P}}_{\mathit{i}}$ is denoted as a path from the source node to the destination node, and ${\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}$ is the hop count of the path. There are ${\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}$ links between the source node and the destination node, then the interference received by the path ${\mathit{P}}_{\mathit{i}}$ is the sum of the interference received by each link on the path, denoted by ${\mathit{P}}_{{\mathit{I}}_{\mathit{i}}}$ , and calculated as in Equation (9). $$\begin{array}{}\text{(9)}& {\mathit{P}}_{{\mathit{I}}_{\mathit{i}}}={\displaystyle \sum }_{\mathit{j}=1}^{{\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}}{\mathit{I}}_{{\mathit{L}}_{\mathit{k}}}={\displaystyle \sum }_{\mathit{j}=1}^{{\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}}{\displaystyle \sum }_{\mathit{i}=1}^{\mathit{l}}\mathit{I}\mathrm{(}{\mathit{L}}_{\mathit{i}}\mathrm{,}{\mathit{L}}_{\mathit{j}}\mathrm{)}\end{array}$$

• Remaining capacity

The load on the link can be measured by the remaining capacity on the interfaces at both ends of the link, the remaining capacity of the interface $int\mathit{f}\text{\_}\mathit{qu}\text{\_}{\mathit{utiL}}_{\mathit{j}}$ is calculated by Equation (10). $$\begin{array}{}\text{(10)}& {\mathit{L}}_{\mathit{j}}^{\prime }={\displaystyle \frac{{\mathit{L}}_{\mathit{j}}^1}{{\mathit{L}}_{\mathit{j}}^2}}\mathrm{,}\end{array}$$ where ${\mathit{L}}_{\mathit{j}}^1$ indicates how much of the remaining capacity is used. Further, ${\mathit{L}}_{\mathit{j}}^2$ indicates how much of the remaining capacity. The ratio of the two indicates the utilization of the remaining capacity, which is the loading of the interface.

The load on the path ${\mathit{P}}_{\mathit{i}}$ is equal to the average of the remaining capacities on the path ${\mathit{P}}_{\mathit{i}}$ , and the expression for calculating the average remaining capacity of the path is as in Equation (11). $$\begin{array}{}\text{(11)}& \hat{\mathit{R}}={\displaystyle \frac{{\sum }_{\mathit{j}=1}^{{\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}}{\mathit{L}}_{\mathit{j}}^1}{{\mathit{N}}_{{\mathit{P}}_{\mathit{i}}}}}\end{array}$$

• Routing Criteria

In addition to the current load condition on the path, interference can also have an impact on the path load level. Two links will compete in the same channel and communication range. This will cause inter-link interference, which affects the quality of the wireless link, causing packets in the interface queue to wait and causing an increase in node load. Therefore, the interference factor of the path should also be considered as part of the impact path load indicator ${\mathit{L}}_{{\mathit{P}}_{\mathit{i}}}^{\prime }$ . Path load indicator, namely routing standard is calculated using Equation (12). $$\begin{array}{}\text{(12)}& {\mathit{\gamma }}^{\prime }={\mathit{L}}_{{\mathit{P}}_{\mathit{i}}}^{\prime }+{\mathit{P}}_{{\mathit{I}}_{\mathit{i}}}\times \hat{\mathit{R}}\end{array}$$

2.4. Route discovery and path count control

Through the multi-path network load balancing method designed above, further control the route discovery and the number of paths. The AOMDV protocol can discover multiple paths, but only one primary path is used. The AOMDV protocol is improved so that it can discover and select multiple paths based on the routing criterion ${\mathit{\gamma }}^{\prime }$ .

The new field L, ${\mathit{L}}_{\mathit{j}}$ is added to the RREQ packet structure and a new field ${\mathit{\gamma }}^{\prime }$ is added to the RREP packet. The source node starts the route discovery process by flooding the RREQ packet. When the intermediate node receives the RREQ packet, it first becomes a reverse path and then obtains the information such as L and ${\mathit{L}}_{\mathit{j}}$ of each node from the RREQ packet, then uses Equations (10) and (11) to calculate the values of interference and queue utilization from the source node to this node, respectively, and continues to broadcast the RREQ packet. The destination node adds the final calculated value of ${\mathit{\gamma }}^{\prime }$ to the RREQ packet using Equation (12) and feeds it back to the source node, which selects a certain number of available paths of K based on this value and arranges them in ascending non-decreasing priority order according to the value of ${\mathit{\gamma }}^{\prime }$ , then inserts them into the routing table for storage. With the above improvement, in one single route discovery, multiple sources to destination paths are found and these paths are stored in the routing table according to a certain priority order. But here the selection of the number of paths also has some impact on the performance of the protocol. If too many paths are selected, the interference between the paths is bound to increase and the cost of route maintenance is bound to increase. Or if the number of paths selected is too small, the purpose of parallel transmission and backup paths cannot be achieved. Therefore, the value of the number of paths K has to be chosen as an optimal value.

2.5. AOMDV protocol improvement based on probabilistic triage

The improved AOMDV protocol on the one hand enables data to be transmitted with minimum energy relaying as much as possible, and on the other hand makes data change its original routing path with a certain probability, which avoids partial node overloading instead of balancing the nodes after the phenomenon of node overloading occurs. The improved AOMDV protocol is divided into two parts: routing path establishment and probabilistic equalization.

2.5.1. Routing path establishment

After controlling route discovery and number of paths, we can establish a route path. In the network, relay nodes are selected from their characteristic distances according to the coordinates of neighbor nodes to achieve minimum capacity relay. At the same time, a candidate node with the most remaining energy [9,13] is selected from the neighbor nodes for this node. If the remaining energy of the candidate node is more than this node, it is considered that a routing path with a light load is found from the multipath.

Assuming that the distance between a node S and the sink node is denoted as D, when D satisfies the condition in Equation (13), node S takes the sink node as the next hop directly without passing the relay node. Otherwise, node S selects node H which is closest to node S among all nodes $\mathit{S}\sim \mathit{D}$ as the relay node, which calls the original relay node. And the previous hop node S is recorded in node H.

$$\begin{array}{}\text{(13)}& \mathit{D}⩽2{\mathit{E}}_{\mathrm{elec}}\mathrm{/}{\mathrm{\left(}\mathit{\epsilon }{\mathrm{(}1-2\mathrm{)}}^{1-\mathit{\gamma }}\mathrm{\right)}\mathrm{)}\mathrm{)}}^{\mathit{L}\mathrm{/}\mathit{\gamma }}\mathrm{,}\end{array}$$ where ${\mathit{E}}_{\mathrm{elec}}$ denotes the energy consumption per unit of data transmitted by the node. Moreover, ε denotes the power amplification factor and γ denotes the path fading index.

• The candidate relay node ${\mathit{R}}^{\prime }$ is selected among the neighboring nodes S and S is recorded ${\mathit{R}}^{\prime }$ . Node ${\mathit{R}}^{\prime }$ is the most energy remaining among the neighboring nodes S and is not the upstream node and relay node ${\mathit{R}}_0$ of S.

2.5.2. Probabilistic equilibrium for multipath routing protocols

Through the established routing path, the probability of multi-path routing protocol is balanced. During data transmission, a node uses candidate nodes as trunks with a certain probability to transfer data from the heavily loaded routing path to the lightly loaded routing path, which is called path switching[7]. Path switchover down hop count for data is set in which the initial value is 1. When the value is 0, data path switchover is prohibited.

Assuming that the remaining energy of each node in the network at a given moment is ${\mathit{E}}_{\mathit{L}}^{\ast }$ , the original relay node on the routing path of a node ${\mathit{N}}_{\mathit{k}}{\mathit{N}}_1$ and the candidate node is ${\mathit{N}}_{\mathit{m}}$ , the probability of a path switch occurring for the currently transmitted data is as follows.

$$\begin{array}{}\text{(14)}& {\mathit{P}}^{\prime }={\mathit{E}}_{\mathit{m}}^{\ast }\mathrm{/}\mathrm{(}{\mathit{E}}_{\mathit{L}}^{\ast }+{\mathit{E}}_{\mathit{m}}^{\ast }\mathrm{)}\end{array}$$

If the node ${\mathit{N}}_{\mathit{k}}$ passes data to the original relay node ${\mathit{N}}_1$ , then, the number of next hops for data path switchover is set to 1. If the data is passed to the candidate node, that is, path switchover occurs, and the path switchover hop number of the data is reduced by 1.

• We require timely updates to candidate node ${\mathit{R}}^{\prime }$ , when there is a node death, the relay and candidate nodes of that node is notified to clear the relevant records, and at the same time, the nodes with that node as relay and candidate have notified to re-select the next hop relay and candidate node according to the above rules to update the routing path.

According to the above rules, multipath data transmission with improved AOMDV protocol can be implemented.

Analyzing the difference in energy consumed by each node in the network in transmitting unit data, it is known that the closer the aggregation node bears the heavier the load of the relay, the more energy consumed is increasing and the residual energy is decreasing. Assuming that the residual energy of each path in the network ${\mathit{E}}_{{\mathit{L}}_1}\mathrm{<}{\mathit{E}}_{{\mathit{L}}_2}\mathrm{<}{\mathit{E}}_{{\mathit{L}}_3}$ , the degree of a load of each path can be calculated according to the above equation (14) as ${\mathit{E}}_{{\mathit{L}}_1}\mathrm{>}{\mathit{E}}_{{\mathit{L}}_2}\mathrm{>}{\mathit{E}}_{{\mathit{L}}_3}$ .

If a node ${\mathit{N}}_{\mathit{k}}$ on the path ${\mathit{L}}_1$ finds a candidate node ${\mathit{N}}_{\mathit{m}}$ on the path ${\mathit{L}}_3$ lightly loaded during data transmission, ${\mathit{N}}_{\mathit{k}}$ passes data to ${\mathit{N}}_{\mathit{m}}$ with some probability, switch the path to ${\mathit{L}}_3$ . After several relay transmissions on the path ${\mathit{L}}_3$ with high probability, the candidate node is found to be located on the more idle path. Repeat the preceding operations until the data is transferred to the sink node.

As the size of each path varies, the degree of the load varies during data transmission and the residual energy of the nodes has variability. The above probabilistic shunting method allows each node to switch paths with a certain probability during each data transmission, forwarding the data to the node with more residual energy, namely the path with a lighter load, so that the energy consumption of each path is equalized and the premature death of some nodes due to heavy load is avoided.

3. Experimental methods

3.1. Experimental environment

To verify the routing protocol in this paper, simulation experiments are conducted in a MATLAB environment using NS2 network simulation software, and the effectiveness and performance of the proposed routing protocol in this paper are analyzed based on the simulation. A modified AOMDV protocol with distributed coordination mechanism is used in the simulation environment, and the transmission rate of the wireless link is 54 Mbps. 30 CBR and VBR service flows are randomly generated during the experiment, and three routing algorithms WCETT-LB, MMESH, and Cluste_MMESH are deployed in the simulation environment. In 1000 m × 1000 m network coverage, the number of nodes deployed in a general WMN is 50 ∼80. When the number of nodes exceeds 80, the scale of the network is larger and the requirements for the routing protocols deployed in the network are higher. The parameters in the simulation experiments are set as shown in Table 1.

Table 1

Simulated environmental parameters

Parameters	Setpoint
Network coverage	1000 × 1000
Number of nodes/pc	20, 40, 60, 80, 100
Data transfer rate/Mbps	54
Number of channels/pc	15
Channel bandwidth/Mbps	12
Data transmission range/m	300
Interference range/m	600
Number of business flows	30
Type of business flow	UDP
Data transmission method	CBR, VBR
Experimental run time	600 s

In this paper, the experiments use a 15-node experimental network topology diagram, using five computers and a switch to virtualize the experimental network, mainly for data success delivery rate, redundancy, network survival time, and network node survival number, using multiple experimental sampling, which takes the average of the method to optimize the above parameter value settings. The experimental network topology diagram is shown in Fig. 3.

Fig. 3.

Schematic diagram of the experimental network topology.

The number of each node in Fig. 3 is $\mathit{R}1\mathrm{,}\mathit{R}2\mathrm{,}\dots \mathrm{,}\mathit{R}15$ in order, a total of 15 network nodes. There are 20 links in the network topology, each link contains bandwidth and latency attribute values in Mbps, ms respectively. These 15 network nodes are assigned to five computers, each computer simulates three interconnected terminals. Each computer should not simulate too many nodes or else it is easy to cause computer failure or program too much load, which affects the experimental effect.

In the simulation results, the following four metrics are used to evaluate the performance of the routing protocol in this paper. i) successful delivery rate is the probability that the source node can correctly receive a packet when it is sent by the aggregation node, which reflects the reliability of the network, the higher the value is, the higher the network reliability is, and vice versa ii) standard residual degree, the total number of times the aggregation node needs to send a packet when it correctly receives it, the lower the redundancy is, the higher the energy efficiency of the network is, and vice versa. iii) network survival time is how much time the network has remaining energy to send packets from the source node to the destination node, the longer the lifetime is, the higher the success rate of the transmission node is, and vice versa. iv) the number of nodes in the network is the number of nodes in the network that can continue to transmit data after some time, the more nodes survive, the more balanced and efficient the energy load of network nodes.

3.2. Performance analysis

3.2.1. Successful delivery rate

$$\begin{array}{}\text{(15)}& {\mathit{S}}_{\mathit{R}}={\mathrm{\Gamma }}^{\mathit{M}}={\mathrm{(}1-{\mathrm{\Gamma }}_{\mathit{b}}\mathrm{)}}^{\mathit{M}\mathit{J}}\mathrm{,}\end{array}$$

Successful delivery rate is defined in Equation (15), where M denotes the number of hops elapsed during data transmission. Furthermore, J denotes the packet length, ${\mathrm{\Gamma }}_{\mathit{b}}$ denotes the channel bit error rate, and finally Γ denotes the transmission success rate between any two nodes in the data network.

The simulation system sends a certain number of original packets from the source node, and then counts the number of packets successfully received by the aggregation node. The successful delivery rate is obtained by comparing the number of successfully received packets with the total number of packets sent by source node $\mathit{SDR}$ . The comparison of the successful delivery rate is shown in Fig. 2 before and after the improvement of the protocol in this paper.

Fig. 4.

Comparison of successful delivery rates before and after improvements to the AOMDV protocol.

From Fig. 4, it can be seen that the successful delivery rate is not much different before and after the improvement of the AOMDV protocol in the case of very small BER, which is because when the BER is very small the data transmission process is almost error-free, so the successful delivery rate is very high. As the BER keeps increasing, the successful delivery rate of the pair before the improvement of the AOMDV protocol decreases significantly and drops to 0 when the BER reaches 100. The successful delivery rate of AOMDV protocol after improvement is always higher than 50%, which is because the improved AOMDV protocol adopts a multipath probability sending and probability balancing mechanism, which can quickly recover the routing path and improve the successful delivery rate of packet transmission when there is a problem in multipath routing.

3.2.2. Redundancy $$\begin{array}{}\text{(16)}& {\mathit{N}}_{\mathit{R}}={\displaystyle \frac{{\sum }_{\mathit{i}=0}^{\mathit{M}-1}{\mathit{\sigma }}_{\mathit{i}}}{{\mathit{S}}_{\mathit{R}}\times \mathrm{\Gamma }}}={\displaystyle \frac{1+{\sum }_{\mathit{i}=0}^{\mathit{M}-1}\mathrm{\Gamma }}{{\mathit{S}}_{\mathit{R}}}}\end{array}$$

Redundancy is calculated using Equation (16) where ${\mathit{\sigma }}_{\mathit{i}}$ ( $\mathit{i}=0\mathrm{,}1\mathrm{,}2\mathrm{,}\dots \mathrm{,}\mathit{M}-1$ ) indicates the amount of data sent by the node i.

Fig. 5.

Comparison of standardized redundancy before and after AOMDV protocol improvement.

The redundancy reflects the energy consumption of the network because the total packets sent by the network are proportional to energy consumption. When redundancy is lower, it shows the higher energy effectiveness of the network, seeing that the redundancy is related to the successful delivery rate, which explains the reason why the redundancy increases with the BER in Fig. 5. As can be seen from Fig. 5, with the increase of bit error rate, the redundancy of the AOMDV routing protocol before improvement is also increasing. With the improved AOMDV routing protocol, although the bit error rate is increasing, the redundancy can maintain a more stable state, and the redundancy increases slowly. The establishment and probability equalization of multiple routing paths increase the success delivery rate, thereby reducing the redundancy.

3.2.3. Network survival time

Network survival time is defined as how much time the network has remaining energy to send packets from source node to destination node. If the node energy is limited, each source node tries to deliver data packets to the sink node. The simulation program is used until the node failure message cannot be delivered, and the effective time is recorded. The comparison of the network survival time under the AOMDV routing protocol before and after using the improvement is shown in Fig. 6.

Fig. 6.

Comparison of network survival time before and after AOMDV routing protocol improvement.

From Fig. 6, it can be seen that the network survival time is closely related to the energy of the nodes, and the higher the energy of the nodes, the longer the effective life cycle of the network. The network life cycle of the improved AOMDV routing protocol is better than that of the original AOMDV routing protocol. This is because the improved AOMDV routing protocol establishes multi-path routing and carries out probability balance, so that the data is sent to the link with more residual energy and less data, and the energy of the whole network can be balanced. As a result, the life cycle of the network is greatly improved.

3.2.4. Number of nodes surviving in the network

The number of node stocks in the network is defined as how many nodes in the network are continuing to transmit data after a given period, which varies with time. The number of node stocks in the network for the pre-improved and improved AOMDV routing protocols is shown in Fig. 7.

Observing Fig. 7, it can be found that the pre-improved AOMDV routing protocol has some nodes in the network beginning to die at 300 seconds (s) and all nodes in the network die when reaching 700 s. However, the improved AOMDV routing protocol delayed the node death by 200 s, because the improved AOMDV routing protocol adopted the method of probability shunt to make the energy load of network nodes more balanced and more effective. When the protocol reaches 1000 s, there are still surviving nodes in the improved AOMDV routing protocol, while all the nodes of the pre-improved AOMDV routing protocol have already died by this time. It can also be seen from Fig. 7 that when nodes start to die in the AOMDV routing protocol network before and after the improvement, the death rate of the remaining surviving nodes is gradually accelerated, which is because the remaining surviving nodes take on more data forwarding tasks and accelerate the death rate of the nodes.

Fig. 7.

Comparison of the number of nodes surviving in the network.

In this paper, several metrics are tested on the routing protocol using MATLAB and NS2 simulation tools, namely (i) successful delivery rate, (ii) redundancy, (iii) network survival time, and (iv) number of surviving nodes in the network. The test results validate the superiority of the multipath load balancing routing protocol based on the probabilistic diversion proposed in this paper.

4. Conclusion

As one of the key technologies in WMN, a routing protocol is directly related to the operation efficiency of the entire network. This paper focuses on how to establish efficient and reliable routing for wireless sensor networks. First, the advantages of multipath routing protocols are explored in WMN, then the improvement of AOMDV routing protocols is discussed on multipath routing performance. This is followed by looking at the advantages of probabilistic diversion in establishing energy-efficient multipath. Finally, this paper combines multipath routing establishment and probabilistic balancing methods to design and implement a load-balancing routing protocol for multipath networks based on probabilistic triage, which improves the energy efficiency and reliability of WMN.

An improved load-balancing routing protocol for a multipath network is proposed to solve the problem of unbalanced protocol communication in WMN in our research work. Simulation results show that the successful delivery rate of the improved AOMDV protocol is always higher than 50%, and the redundancy is lower than 10%. The node starts to die in 200 s. It is proved that the proposed protocol can effectively balance the node load and prolong the network lifetime, and the network congestion caused by node overload can be avoided in advance by a probabilistic shunt strategy, which reduces redundancy. In the aspect of multi-path generation, in addition to factors such as energy and number of surviving nodes, other influencing factors should also be considered. In future research, changes in packet transmission delay should be considered when the traffic in the network increases instantaneously to improve the rationality of the algorithm.