Physarum-inspired multi-parameter adaptive routing protocol for coal mine hybrid wireless mesh networks

Abstract

Hybrid wireless mesh networks are suitable for complex environment communication in coal mine. Mesh clients with application service and routing function in hybrid wireless mesh networks can form a highly robust hybrid network with mesh routers. The processes of nutrient flux transfer and path choice in Physarum network are similar to data transmission and routing selection in hybrid wireless mesh networks. In this article, we use Physarum-inspired autonomic optimization model to design a Physarum-inspired multi-parameter adaptive routing protocol to improve the service quality of coal mine hybrid wireless mesh networks. Physarum-inspired multi-parameter adaptive routing protocol has achieved distributed routing decision by drawing the hybrid wireless mesh network parameters into Poisson’s equation of Physarum-inspired autonomic optimization model to measure the quality of link and implements two adjustment strategies to make the protocol more adaptive. The resource-dependent adjustment, which considers the irreversible energy consumption and recoverable buffer occupation, makes the energy consumption problem prominent when there is a lack of energy. The position-dependent adjustment makes routing decision efficient according to the load of different positions, which is caused by many-to-one data transmission model in coal mine. Based on NS2, simulation experiments are performed to evaluate the performance of Physarum-inspired multi-parameter adaptive routing protocol, and the results are compared with those of ad hoc on-demand distance vector, HOPNET, ANT-DSR, and Physarum-inspired routing protocols. The experimental results show that the route path selected by Physarum-inspired multi-parameter adaptive routing protocol is better than those selected by the other four protocols in the performance of average end-to-end delay and delivery ratio. The balance of energy consumption and network load is achieved and the network lifetime is effectively prolonged when using Physarum-inspired multi-parameter adaptive routing protocol.

Keywords

Wireless mesh networks Physarum network routing coal mine multi-parameter

Introduction

The coal mine is a mobile and complex working environment due to coal mining and working-face driving, and wired communication networks cannot reach these special areas, which makes it easy for blind monitoring areas to form.¹ Therefore, it is urgent to pay more attention to the theory and technology of new wireless communication systems and construct a new type of broadband wireless network to adapt to the special underground working environment. Wireless mesh networks (WMNs), as a new kind of broadband wireless network, can effectively solve the above problem, which the wired network and traditional wireless network cannot solve.²

According to the type and organization mode of the nodes, WMNs can be divided into three categories: backbone WMNs, client WMNs, and hybrid WMNs.³ In backbone WMNs, mesh clients (MCs) cannot directly communicate with each other and must connect to mesh routers (MRs) to achieve broadband network access. Client WMNs are composed of MCs, which need to support data routing and network configuration, as well as provide end-user applications to customers. Hybrid WMNs are composed of MCs and MRs. In this kind of networks, MCs can perform the routing functionality as MRs, which results in hybrid wireless mesh networks (HWMNs) with strong self-organization and self-healing abilities, as well as high robustness. Therefore, HWMNs can be used to transmit information in special areas and on special occasions in an underground mine.

In HWMNs, MCs are powered by batteries, which are energy limited. The energy supply of MRs is sufficient because of the wired power supply. In addition, the computing power and buffer space of MRs are often stronger than those of MCs. Therefore, we should take full account of the characteristics of different types of nodes in routing decisions. The effective working times of nodes directly affect the network lifetime. The energy balance should be considered in the design of the routing protocol, as well as the load balance. Researchers have put forward some methods to solve the above problems. These methods are based on the performance parameters of nodes, such as energy and buffer, which are used as the routing decision metric by adding appropriate proportion adjustment factors. However, these factors are given fixed values, resulting in poor adaptability to the changing network state.

In recent years, researchers have begun to study the bionic algorithm, and the Physarum-inspired autonomic optimization model (PAO) has become a hot research topic. The process of nutrient delivery and the path choice in the Physarum network are very similar to data transmission and route selection in HWMNs. Thus, the characteristics of the Physarum network can inspire us to apply such a model to routing decision in HWMNs. However, the PAO is not appropriate for use in HWMNs directly because it is calculated based on the global information and has high complexity and overhead.

The algorithm proposed in this article views the tubes of the Physarum as network links in HWMNs. Parameters such as energy consumption, buffer occupation, and hop count to the gateway (node depth) are used as the routing metrics. In HWMNs, MCs are powered by limited energy and the energy consumption process is usually irreversible. The buffer occupation of nodes is a kind of “elastic” network parameter, changing with the network load. Therefore, the proportion adjustment factors of energy consumption and buffer occupation should be able to adapt to the different performance characteristics of these two parameters. In addition, for the nodes at the edge of the network, the distance to the gateway should be prioritized so the routing process will converge as quickly as possible, while more consideration should be given to load balance in the routing decision for the nodes close to the gateway with high load pressure. Based on the PAO and the analysis of the parameters’ characteristics, energy and load balance is implemented in the algorithm with low overhead and network state adaptation as well.

The remainder of this article is organized as follows. Section “Related work” reviews the related work. Section “HWMNs in coal mines” introduces HWMNs in the coal mine. The Physarum-inspired multi-parameter adaptive routing (PIMAR) protocol for coal mine HWMNs is proposed and described in detail in section “PIMAR protocol.” Section “Implementation of PIMAR” gives the implementation process of PIMAR. Section “Simulation experiment” presents the results of the simulation experiments. Finally, the conclusions of the study are presented in section “Conclusion and future studies.”

Related work

With the development of the WMN, the research on routing protocols is also advancing. There are some classical routing protocols currently suitable for WMNs, such as destination-sequenced distance vector (DSDV), ad hoc on-demand distance vector (AODV), and hybrid wireless mesh protocol (HWMP).^4–6 In a WMN, MC energy, computing power, and buffer are often limited, which affects the network performance directly. Researchers have proposed many routing protocols based on these performance parameters to solve the problem of load and energy balance to prolong the network lifetime and improve the network performance.

A power-aware routing protocol, which implements energy balance in the network, was proposed in Toh.⁷ A method to measure the load level of the media access control (MAC) layer was introduced, and load balance was implemented in Kim et al.⁸ Because the network performance is affected by many factors, the routing metric often contains multiple parameters. A routing decision method combining node mobility and congestion was proposed, and a congestion avoidance routing protocol was implemented in Basarkod and Manvi,⁹ which can adapt to frequent changes in network topology. Jabbar et al.¹⁰ used the idle time of the node, residual power, and queue length as the metrics to measure the link quality between nodes and implemented energy and load balance. A metric based on the expected transfer time of the network and the buffer queue of the nodes was proposed to implement load balance in Ma and Denko.¹¹ It is necessary to introduce the parameter adjustment factors to adjust the proportions of different parameters in the multi-parameter routing metric. However, the factors often take fixed values and the adaptability of the fixed factors is poor due to the frequently changing network state.

In recent years, many fields have drawn attention to bionics and intelligent algorithms, such as the ant colony algorithm and swarm intelligence algorithm, used in research on topology and routing in WMNs. The ant colony optimization (ACO) algorithm is based on ant colony foraging to find the optimal path.¹² Aissani et al.¹³ proposed ant dynamic source routing (ANT-DSR), a proactive routing protocol based on ACO. ANT-DSR uses unicast ant agents to find routes and always maintains a certain number of ants for routing optimization. This approach can effectively shorten the routing time but leads to relatively large network overhead. Wang et al.¹⁴ proposed a hybrid ant colony algorithm called hybrid ant colony optimization routing algorithm for mobile ad hoc network (HOPNET) which contains four types of ants: intra-zone forward ants, intra-zone backward ants, inter-zone forward ants, and inter-zone backward ants. However, HOPNET is difficult to adapt to a larger network because of the lack of good scalability.

With the development of bionics and some scientific discoveries, cellular computation has become an important branch of biological heuristic algorithms and has attracted increasing attention to the calculation of the Physarum. The Physarum is an ancient protoplasmic slime with a tubular network to absorb nutrition. In the process of finding and absorbing nutrients, the Physarum can retract to an efficient tubular network. Nakagaki et al.¹⁵ investigated the maze-solving behavior of the Physarum and observed that the Physarum can find the shortest path between a food sources at the maze exit and the entrance without any control.

Tero et al.¹⁶ established a geographical model of Tokyo and the area around the main city using oatmeal and cultured Physarum on it. A biological network that connects all food sources had formed by the end of the experiment and the network was comparable to the real railway network of Tokyo in the aspects of efficiency, reliability, and cost. PAO laid the foundation for future research in Tero et al.¹⁷ A method using PAO to solve the Steiner tree problem was presented in Liu et al.¹⁸ New ideas for the construction of more efficient transportation networks by applying PAO to traffic network optimization were provided in Marwan¹⁹ and Tsompanas et al.²⁰ Some methods of optimizing a logistics distribution and supply chain network based on the model were presented in Chen et al.²¹ and Zhang et al.²² A method of solving the shortest path problem was proposed in Lu.²³ Ma and coworkers applied PAO to the distribution of wireless sensor networks to optimize the detection range.²⁴ PAO is an adaptive algorithm that can adjust to changes in the environment to obtain a more stable network. However, the process of finding the best path with iterative calculations in PAO has high complexity and overhead. Therefore, PAO is not suitable for direct application in WMNs, which have limited resources.

In order to apply PAO to routing decision, we need to migrate the model to WMNs. Zhang et al.^25,26 applied PAO to location-aware routing protocol and proposed a protocol called P-iRP, which considered the distance, energy, and location of the next hop. Zhang et al.²⁷ provided a novel bio-inspired hybrid routing protocol based on zone routing framework, ACO, and PAO, and the network performance has been improved significantly. PAO has also been used in energy-harvesting wireless sensor networks, and three distributed routing algorithms with low algorithm complexity have been proposed in Tang et al.²⁸

We propose a new HWMN routing algorithm, called PIMAR, based on PAO. PIMAR uses the information of local nodes, such as energy consumption, buffer occupation, and node depth, in the metric for route selection. The algorithm has low complexity, which ensures the feasibility in the HWMNs. In addition, the algorithm incorporates the proposed strategy of adaptive parameter adjustment based on the node resources and network topology, which increases the adaptability of routing decisions to changes in the network state. Moreover, the algorithm implements energy and load balance and has a high throughput and a small transmission delay.

HWMNs in coal mines

Network structure

There are many narrow tunnels in coal mines. With coal mining and tunnel excavation, the tunnels extend gradually and form a band structure with a length of hundreds of meters, or even a thousand meters. WMNs in coal mines have a long-chain structure (backbone WMN) adapted to the long-chain structure of the tunnels. Data packets are transmitted to MRs and are forwarded to the gateway node, as shown in Figure 1.

Figure 1.

Structure of a backbone WMN in a coal mine.

In the long-chain backbone WMN, MCs are overwhelmingly dependent on MRs, which will lead to the decline of network performance and even paralysis once failures of the MRs occur. Therefore, a network with this structure has low robustness and poor self-repairing ability.²⁹ In an HWMN, MCs can communicate with one another and data packets can be forwarded by MCs when MRs are broken down. The HWMN has higher reliability, as shown in Figure 2.

Figure 2.

Routing repair of an HWMN in a coal mine.

Node type

MCs in a coal mine have limited energy, unlike in a WMN on the ground. There is no energy restriction for MRs because they are supplied by wired power. MCs are the main nodes in an HWMN, so the energy limitation problem will directly affect the network lifetime and is even more serious in mine emergency communication.^30,31 MRs have higher performance capabilities than MCs in terms of buffer space and data processing speed. It is necessary to optimize the utilization ratio of different types of nodes to prolong network lifetime and improve network performance.

PIMAR protocol

Parameter mapping

There are many junctions in the Physarum network, such as i and j in Figure 3. We define the tube from i to j as $Tube < i, j >$ .

Figure 3.

Physarum network.

As mentioned in Tero et al.,¹⁷ the flux of nutrient can be expressed by the Poisson equation

Q_{i, j} = \frac{D_{i, j}}{L_{i, j}} (p_{i} - p_{j})

(1)

where $D_{i, j}$ represents the conductivity of $Tube <_{i, j} >$ , $L_{i, j}$ represents the length of $Tube <_{i, j} >$ , $Q_{i, j}$ represents the flux in $Tube <_{i, j} >$ , $pi$ is the pressure at the junction node i, and $(p_{i} - p_{j})$ denotes the pressure difference between i and j. We suppose that the flows in the HWMN data link also satisfy the Poisson equation. Next, $D_{i, j}$ represents the link conductivity from node i to node j, and the link between i and j can be referred to as $link <_{i, j} >$ . In this article, we assign the same value to $D_{i, j}$ for all i and j.

The shortest path can be chosen by PAO. Therefore, the length $(L_{i, j})$ of the tube can be considered the cost of the Physarum tubular network. The cost of a link in the HWMN is affected by the performance of the next-hop node. MCs, which have limited energy, small buffer space, and low computing power, cannot carry too much network load, while MRs have better performance and are thus preferred in routing decisions. To reflect the difference between these two kinds of nodes, $L_{i, j}$ in the Poisson equation is redefined as $C_{i, j}$ which represents the cost of $link <_{i, j} >$ and is only related to the node type of the next-hop node. We set $C_{i, j} = 2$ when the next-hop node is an MC node, and set $C_{i, j} = 1$ when the next-hop node is an MR node. Therefore, MRs with lower cost are more likely to be selected when making routing decisions.

The process of data flowing from one node to another in an HWMN is similar to the process in fluid mechanics. The direction of movement of the fluid is determined by the pressure difference $(p_{i} - p_{j})$ , while the transmission direction of the data packet is dependent on the current state of the next-hop node in an HWMN. The state of the node consists of its energy consumption, buffer occupation, and node depth. Therefore, the pressure difference $(p_{i} - p_{j})$ in an HWMN can be defined by these three parameters.

Resource-dependent adjustment strategy for pressure difference

The factors such as energy consumption and buffer occupation with different characteristics are indispensable when choosing the next-hop node. MCs are powered by batteries and the energy consumption is irreversible. The buffer occupation is influenced by the network load, which is an “elastic” factor. The energy consumption ratio of the next-hop node is denoted as $E_{u}$ and the buffer occupation ratio is denoted as $B_{u}$ . The values of $E_{u}$ and $B_{u}$ are defined as follows

E_{u} = \frac{E_{u s e d}}{E_{i n i t i a l}}

(2)

B_{u} = \frac{B_{u s e d}}{B_{i n i t i a l}}

(3)

where $E_{u s e d}$ and $B_{u s e d}$ are the energy and buffer space that the node has consumed and $E_{i n i t i a l}$ and $B_{i n i t i a l}$ represent total energy and buffer space, respectively.

The parameters of energy consumption and buffer occupation are the measures of node state: the more energy and buffer that remain, the better the node state. The correspondence between the pressure concept of PAO and the node state in an HWMN can be expressed as follows: the better the state of the next-hop node, the greater the pressure difference between this node and the next node. If the residual energy and buffer are viewed as the driving forces of the data flow, the energy consumption and buffer occupation can be regarded as the resisting forces. We define the pressure difference between i and j as $Δ p_{i, j} = pi - pj$ and the resistance as $Δ p'_{i, j}$ . There is a complementary relationship between the residual energy and the consumed energy, as well as between the remaining buffer and the consumed buffer, so the relationship between $Δ p_{i, j}$ and $Δ p'_{i, j}$ is expressed as follows

M = Δ p_{i, j} + Δ p'_{i, j}

(4)

where M is a constant.

$Δ p'_{i, j}$ is defined as

Δ p'_{i, j} = α E_{u} (j) + β Bu (j)

(5)

where $0 \leq α \leq 1$ , $0 \leq β \leq 1$ , and $B_{u} (j)$ and $E_{u} (j)$ are the buffer occupation ratio and energy consumption ratio of the next-hop node j, respectively.

If the values of $B_{u} (j)$ and $E_{u} (j)$ are large, which means that node j is not a good choice, it will give greater resistance to select node j by formula (5). As mentioned above, the changing characteristics of $B_{u} (j)$ and $E_{u} (j)$ are different. The energy consumption is irreversible with the network running and $E_{u} (j)$ will be increasing. However, the value of $B_{u} (j)$ will increase or decrease during the running process of the network. In order to minimize the selection probability of a low-energy node, we need to make the element of energy more prominent in formula (5). In this article, we set the value of $α$ as

α = E_{u} (j)

(6)

The value of $α$ will increase with the consumption of energy, which will bring energy factor with a bigger impact on $Δ p'_{i, j}$ . Nodes with low energy will have less chance to be selected as the next hop.

On the other hand, when the residual energy of nodes is sufficient, the buffer space should be given more weights. We set $β$ as

β = (1 - α)

(7)

When the energy consumption is less, the value of $β$ will be larger, and the buffer space will play a more important role on $Δ p'_{i, j}$ .

Position-dependent adjustment strategy for pressure difference

The load of the node is related to the position in the coal mine network because of its many-to-one data transmission mode. The nodes close to the gateway carry higher loads than nodes that are farther away. To ensure that the route to the gateway converges as quickly as possible, we should focus on the hop count when the node is far from the gateway. A node close to the gateway will carry a higher load and more attention should be paid to its energy and buffer space.

To achieve the position-related adjustment strategy, we have introduced hop factor in our model. In the initial stage of the network, a broadcast message will be sent by the gateway to all the nodes to determine the node depth of the network. Next, the nodes can confirm the hop resistance to neighbors.

The hop resistance $(H_{r} (j))$ is defined as follows

H_{r} (j) = {\begin{matrix} 0 & Δ H_{i, j} = 1 \\ 0.5 & Δ H_{i, j} = 0 \\ 1 & Δ H_{i, j} = - 1 \end{matrix}

(8)

where $Δ H_{i, j} = H_{i} - H_{j}$ is the difference in node depth $(H_{i})$ between node i and node j. If the next-hop node j is closer to the gateway, then $Δ H_{i, j} = 1$ and there is no hop resistance, so $H_{r} (j) = 0$ . If the node depth of the next-hop node j is equal to that of node i, then $H_{r} (j) = 0.5$ . If the next-hop node j is far away from the gateway, $Δ H_{i, j} = - 1$ and $H_{r} (j) = 1$ .

After adding the hop factor, $Δ p'$ is redefined as follows

Δ p'_{i, j} = γ (α E_{u} (j) + β B_{u} (j)) + (1 - γ) H_{r} (j)

(9)

where the value of $γ$ is related to the network depth of node i, which is defined as follows

γ = \frac{1}{\log_{2} H_{i}}

(10)

The values of $γ$ and $1 - γ$ are shown in Figure 4.

Figure 4.

Values of hop resistance factor.

As shown in Figure 4, if we take a larger value of $H_{i}$ , $γ$ will be smaller and the factors of node energy and buffer will have little effect. This strategy of giving higher consideration to the hop factor can be used to implement fast routing convergence of nodes that are far away from the gateway. When we take a smaller value of $H_{i}$ , $γ$ is larger, which means that the effects of energy and buffer are larger; therefore, the balance of energy and load can be achieved among nodes that are near the gateway. When $0 < H_{i} \leq 2$ , the hops from node $i$ to the gateway are very close, and we set $γ = 1$ to ensure that node resources are sufficiently considered.

According to the value range of each variable, we can determine that the data range of $Δ p'_{i, j}$ is $[0, 1]$ and the value of $M$ in formula (4) is $M = 1$ , so the pressure difference between the nodes i and j can be defined as follows

Δ p_{i, j} = p_{i} - p_{j} = 1 - Δ p'_{i, j}

(11)

Thus, the final Poisson equation for HWMNs is defined as follows

Q_{i, j} = \frac{D_{i, j}}{C_{i, j}} (1 - Δ p'_{i, j})

(12)

Routing metric of PIMAR

The flux $Q_{i, j}$ in PAO represents the performance of $Tube <_{i, j} >$ . A tube with larger flux has better performance. Inspired by this method, we use $Q_{i, j}$ to represent the performance of the $link <_{i, j} >$ . Thus, $Q_{i, j}$ calculated by equation (12) can be part of the routing metric.

There are limitations in considering the performance of only the next-hop node when making routing decisions; therefore, PIMAR uses regional flow information of nodes as a routing metric.

Suppose $N (i)$ is the neighbor set of node i and $| N (i) |$ is the number of neighbors.

The method of calculating the regional flow value is defined as follows

Q_{AREA_j} = Q_{i, j} + \frac{\sum_{k = 1}^{n} Q_{j, k}}{n}

(13)

where $k \in N (j), i \in N (j)$ , $Q_{i, j}$ is the flow of $link < i, j >$ , $Q_{j, k}$ represents the flow of $link < j, k >$ , $Q_{AREA_j}$ refers to the regional flow in the direction of neighbor j, and $n = | N (j) | - 1$ denotes the number of neighbors of j, excluding i. The average performance of the nodes in a region is denoted by $Q_{AREA_j}$ : a large value of $Q_{AREA_j}$ indicates that the nodes in the region generally have good states, such as plenty of energy and buffer space. Taking the regional traffic value as the reference, we can make use of the node information within two hops, which can prevent the route selection from falling into a local optimum more effectively. In addition, performance degradation in the network often occurs in a regional range, so the value of $Q_{AREA_j}$ can be used to circumvent the bad areas. Therefore, $Q_{AREA_j}$ is used as the routing decision criterion, and the node j with the largest value of $Q_{AREA_j}$ is selected as the next-hop node.

Implementation of PIMAR

Node depth initialization

In the initial stage of the network, the initial packet (INIT_MSG) is broadcasted by the gateway node. The structure of INIT_MSG is shown in Table 1.

Table 1.

Structure of INIT_MSG.

Packet type	Hop count	TTL
Source IP address
Destination IP address

TTL: time to live.

Packet Type represents the type flag, the value of which is INIT_MSG. Hop Count refers to the distance from the current node to the gateway node. TTL is the time to live of INIT_MSG, which is set to 1. Source IP Address is the IP address of the node that sends INIT_MSG and Destination IP Address is always set to IP_BROADCACT, which indicates that INIT_MSG is a broadcast message.

The process of determining node depth is shown in Figure 5.

Figure 5.

Process of determining node depth.

In Figure 5, steps 1 and 2 are executed only once and step 3 is executed repeatedly by each MR and MC until the node depth is confirmed.

Maintenance of neighbor table

Neighboring nodes need to exchange information regularly to obtain the latest states of one another, so we defined a packet (NB_HELLO) as shown in Table 2.

Table 2.

Structure of NB_HELLO.

Packet type	Depth	TTL
Source IP address		Destination IP addresses
Energy consumption ratio
Queue occupancy ratio
Neighbor average flow

TTL: time to live.

Depth is the node depth, which is confirmed at the initialization state. Energy Consumption Ratio and Queue Occupancy Ratio are properties of the neighbor that sends NB_HELLO. Neighbor Average Flow represents the average flow of all j’s neighbors except i, as defined in formula (13). NB_HELLO is also a broadcast message, so Destination IP Addresses is set to IP_BROADCAST.

We set the message exchange period to 1 s in the stable network state, in which the energy consumption and node depth cannot change rapidly to minimize the network overhead caused by information maintenance. However, if the state of the node is instable, meaning that the variation range of resource potential is greater than 5%, NB_HELLO will be broadcasted to notify the neighbors immediately.

PIMAR needs parameters such as energy consumption, buffer occupation, and node depth to make routing decisions, so each node in the HWMN needs to record this information in the neighbor table. In addition, the adjustment factors, $D_{i, j}$ and $C_{i, j}$ , should be recorded in the neighbor table to calculate $Q_{AREA}$ conveniently.

Routing decision

Through the maintenance process of neighbors’ information, the node can obtain the parameters of its neighbors. When a data packet is received, the node will make a routing decision and select a neighbor to which to forward the packet based on the information in the neighbor table. According to the principle of PIMAR, the neighboring node with the largest $Q_{AREA}$ value in the neighbor table is selected as the next-hop node.

Node resource parameters vary with time in a running network, which may result in a routing loop. We let nodes record packet information such as the packet id, source IP address, and destination, which can be used to determine packet identity solely. The information is stored for a short time after the node forwards the data packet and is used to judge whether there is a routing loop. When the node receives the same packet again, there is a routing loop and the node will select another node from the neighbor table as the next-hop node to retransfer the packet.

The process of routing decision is shown in Figure 6.

Figure 6.

Process of routing decision.

Algorithm complexity analysis

PIMAR is a kind of context routing protocol, according to the distributed process of routing decision which depends on the neighbors’ current state. We suppose that the time of nodes to calculate $Q_{i, j}$ is t and there are n nodes in an HWMN covering the area S. Communication radius of each node is R. To simplify the description, it is assumed that the nodes are uniformly distributed. From the above conditions, it can be seen that the expectation of neighbor node number is $π R^{2} n / S$ . PIMAR using distributed routing algorithm needs to take $π R^{2} nt / S$ to calculate $Q_{AREA}$ , so the time complexity of PIMAR is $O (n)$ .

When the nodes calculate $Q_{AREA}$ , two types of information need to be stored: information of itself such as Node Depth, and neighbor information such as Energy Consumption Ratio, Queue Occupancy Ratio, and Neighbor Average Flow. We suppose that the storage space occupied by information of each neighbor is $P_{1}$ , the node itself occupies $P_{2}$ , and the number of neighbors is $π R^{2} n / S$ . Then, we can get that the space to store that information is $(π R^{2} n / S) \times P_{1} + P_{2}$ and the space complexity of PIMAR is $O (n)$ .

Node depth is confirmed in the initial stage of the network. INIT_MSG is sent from gateway, and the message will be discarded or forwarded according to the initialization process (Figure 5) by the other nodes. Each INIT_MSG has the same message length and nodes cost the same time to handle it. The arrival time of INIT_MSG is determined by hop counts. We can infer that the later arrival message has passed more intermediate nodes and the Hop Count obtained in the first arrived INIT_MSG is the minimum node depth. The number of messages sent in this process is $n$ .

However, the wireless transmission may be delayed in practical applications. The node may receive multiple initialization messages with smaller network depth, resulting in redundant initialization information in the network. In order to reduce redundant information as much as possible, nodes will delay a little time to send its node depth to its neighbors after receiving INIT_MSG. We suppose that $b$ $(b < < n)$ redundant messages are sent in the initialization process. So the message overhead of the initial process is $n + b$ . In the neighbor table maintenance process, each node needs to gather $π R^{2} n / S$ messages to update the neighbors’ state. As a result, there are $π R^{2} n^{2} / S$ messages to be sent by all nodes in the maintenance process. The routing decision is made based on the information gathered in the maintenance process and has no message to send. Therefore, the message overhead in PIMAR is $π R^{2} n^{2} / S + (n + b)$ and the message complexity is $O (n^{2})$ .

Example of PIMAR

For a more detailed introduction of PIMAR, we assume the network topology shown in Figure 7. Node g is a gateway node, b, e, and f are MRs, and the other nodes are MCs. The node depth is marked at the side of each node in the figure. In the initial state of the network, there is no energy consumption and the buffer occupation of each node is zero.

Figure 7.

Network topology.

In this example, node m is assumed to be the data source. The process of routing decision is shown in Table 3.

Table 3.

Routing decision process.

Node	g	a	b	c	d	e	f	h	i	j	k	l	m
DP	1	2	2	2	3	3	3	3	4	4	4	5	4
Q_AREA	Q_{AREA_j} = 1.39 Q_{AREA_f} = 1.59* Q_{AREA_k} = 1.13							Q_{AREA_b} = 1.59* Q_{AREA_e} = 1.35 Q_{AREA_h} = 0.99 Q_{AREA_k} = 0.75 Q_{AREA_j} = 1.22

DP: node depth.

Routing result of each step.

The routing result of each step is shown in bold text with “*.” From Table 3, the first hop chosen by m is f and the next one chosen by f is b. From the topology, we know that b is connected with the gateway node g directly, so the data packet will be delivered to the gateway node without calculation. The final path chosen by PIMAR is m → f → b → g, as shown in Figure 8. According to the result of path selection, PIMAR can choose the link with more routing nodes, which can ensure the stability of the link.

Figure 8.

Route selection of initial conditions.

While the network is running, the energy and buffer of the nodes are consumed. The process of routing decision is shown in Table 4 after a period of time.

Table 4.

Routing decision process.

Node	g	a	b	c	d	E	f	h	i	j	k	l	m
DP	1	2	2	2	3	3	3	3	4	4	4	5	4
E_u (%)	–	17.4	0	25.5	15.2	0	0	20.9	16.1	0	12.8	16.7	25.5
B_u (%)	–	8.4	91	4.7	9.1	10.1	89	7.1	8.9	9.9	9.6	8.7	4.5
Q_AREA	Q_{AREA_j} = 1.18* Q_{AREA_f} = 0.93 Q_{AREA_k} = 0.80					Q_{AREA_e} = 1.23* Q_{AREA_l} = 0.70 Q_{AREA_i} = 0.88 Q_{AREA_f} = 0.89				Q_{AREA_a} = 1.36* Q_{AREA_b} = 0.86 Q_{AREA_f} = 0.52 Q_{AREA_d} = 0.71 Q_{AREA_i} = 0.74

DP: node depth.

Routing result of each step.

In Table 4, nodes b, e, f, and j are MRs, which have wired power supplies, so the energy consumptions are all 0. We suppose that b and f, which are in m → f → b → g, have high buffer occupations. The final routing path is m → j → e → a → g, as shown in Figure 9.

Figure 9.

Route selection after node resource change.

As shown in Figure 9, PIMAR avoids the path with a heavy load and implements the load and energy balance.

Simulation experiment

Simulation environment and experimental parameters

Based on the NS2 simulation platform, we test the performance of PIMAR and the results such as average end-to-end delay, delivery ratio, the usage of the nodes, and network lifetime are compared to those of AODV, ANT-DSR,¹³ HOPNET,¹⁴ and P-iRP.²⁶ The parameters of the simulation network are listed in Table 5.

Table 5.

Simulation parameters.

Topography size	1500 × 8 m²
Simulation time	600 s
Transfer range	200 m
Traffic type	CBR
Packet size of CBR	512 B
Number of CBR flows	8–80
Number of gateways	1
Mesh routers	15
MCs	135
Total energy of MC	8000 J
Transmission power	0.660 W
Receiving power	0.395 W
Idle power	0.035 W

CBR: constant bitrate; MC: mesh client.

In the simulation, we set the network in a long and narrow area of 1500 × 8 m² to simulate the tunnel in an underground mine. We have deployed 15 MRs, 135 MCs, and 1 gateway in the tunnel. We have simulated the network performance using the parameters, such as average end-to-end delay, delivery ratio, node utilization, and network lifetime, under different load pressures by increasing the number of constant bitrate (CBR) data flows.

Performance analysis

Average end-to-end delay

The trends of average end-to-end delay for four different protocols are shown in Figure 10. AODV has the highest average end-to-end delay as well as the fastest growth rate when the number of CBR flows is increasing. The average end-to-end delays of HOPNET and ANT-DSR are smaller than that of AODV. The delay values for P-iRP and PIMAR are smaller than those for HOPNET and ANT-DSR, and PIMAR has the smallest one. This is because AODV is an on-demand routing protocol that requires routing requests before sending data, which may cause time delay. In addition, AODV always selects the path with the minimum number of hops to send data. When the data flow increases, network congestion will occur and the average end-to-end delay will increase. HOPNET and ANT-DSR are proactive routing protocols that always maintain a certain number of ants for routing optimization, so the route selection will be faster than with AODV. However, when the network load is heavy, the overheads of HOPNET and ANT-DSR will become large due to routing maintenance, which requires ants for each data flow. The large overhead will also cause high end-to-end delay. P-iRP does not need much maintenance packets compared with HOPNET and ANT-DSR, because it is location aware. So the delay can be less than HOPNET and ANT-DSR when the data flows become larger. PIMAR can avoid the congested areas effectively and balance the network load using two parameter adjustments. The adjustments consider the buffer occupation of each node as well as its characteristic changing with the node depth to calculate regional flow, which can ensure that nodes with heavy loads are less likely to be chosen. In addition, PIMAR uses a lightweight neighbor information maintenance method, so that its routing maintenance overhead can be maintained at a low level. Based on these two points, PIMAR can achieve low end-to-end delay. Because P-iRP has less consideration to deal with network congestion, the delay of PIMAR is lower than that of P-iRP.

Figure 10.

Average end-to-end delay.

Delivery ratio

Figure 11 shows that PIMAR has the highest data delivery ratio, compared with P-iRP, HOPNET, and ANT-DSR, and AODV has the lowest one. Similar to the end-to-end delay, PIMAR has a congestion mechanism, which can avoid the heavy-load region to reduce the packet loss ratio. The route selection method of AODV only considers the hop count from node to gateway and the network congestion is not included. When the number of CBR flows is large, AODV will lose more packets. HOPNET and ANT-DSR adopt the route optimization mechanism of maintaining a certain number of ants all the time to obtain better routing paths, so their delivery ratios are better than that of AODV. P-iRP has lower routing maintenance cost than HOPNET or ANT-DSR, as a result of which its delivery ratio shows better performance.

Figure 11.

Delivery ratio.

Network lifetime

First, we define the time at which the first node dies as the network lifetime. It can be seen from Figure 12 that the network lifetimes of AODV, HOPNET, ANT-DSR, and P-iRP are shorter than that of PIMAR. This is because PIMAR adopts the adaptive parameter adjustment strategy that considers the irreversible energy consumption characteristic of MCs, which are different from those of MRs. In the process of running the network, energy problem is prominent for MCs; therefore, PIMAR adjusts the weight of the energy factor with the change in energy consumption: the more energy the node has consumed, the bigger the value of $α$ is, and the less likely it is that the node will be selected. This strategy allows PIMAR to avoid low-energy regions to prolong the lifetime of the network and implement energy balance. HOPNET and ANT-DSR can auto-optimize the path by means of the ants in the network, which can make the network lifetime longer than AODV. P-iRP uses an efficient energy optimization method and lower cost routing maintenance than ANT-DSR and HOPNET, so the network lifetime is longer.

Figure 12.

Network lifetime.

Residual energy of MCs

The residual energy of each node is collected at the time at which the first node dies in the network. We adopt the variance of residual energy to measure use balance of the nodes, and analyze the residual energy balance of the nodes under light (CBR = 16), medium (CBR = 40), and heavy (CBR = 72) loads. If the value of the variance is smaller, the use of the nodes is more balanced. It can be seen from Figure 13 that the nodes of AODV are the most unbalanced, followed by those of the ANT-DSR, HOPNET, and P-iRP protocols, and the nodes of the PIMAR protocol are the most balanced under different network loads. From this result, we conclude that the adjustment strategies based on node resources and node depth can effectively implement the energy and load balance.

Figure 13.

Variance of residual energy percentage.

Conclusion and future studies

The HWMN is suitable for complex environments such as coal mines because of its high robustness. Many types of routing protocols have been proposed in recent years, such as bionic algorithms. Cellular computation, an important branch of biological heuristic algorithms, has attracted increasing attention as a hot research topic. There are similarities between Physarum network and HWMNs. This article proposes a PIMAR protocol to implement energy and load balance in HWMNs in coal mines. Based on PAO, we use the Poisson equation combined with the parameters of HWMNs, such as energy consumption, buffer occupation, and node depth, to calculate the network flow, which can be used to measure the quality of a link. We analyze different characteristics of energy and buffer as well as changes in the network load with node depth and propose two adaptive parameter adjustment strategies. The energy consumption of MCs is irreversible, while the buffer occupation is “elastic.” The network loads of nodes near the gateway are heavier than those of the nodes that are farther away because of the many-to-one data transmission mode in coal mines. Based on the analysis, we adjust the weights of those parameters dynamically to prioritize the energy problem and avoid regions with nodes in poor states in the network running process. In addition, PIMAR uses local information to calculate regional flow to make routing decisions, which greatly reduces the complexity of the algorithm, lowers the network cost of the protocol, and improves the scalability. On the NS2 simulation platform, we test the performance of PIMAR and the results show that PIMAR not only has better end-to-end delay and delivery ratio compared to AODV, ANT-DSR, HOPNET, and P-iRP but also prolongs the life of the network and implements energy and load balance.

Most of the nodes in HWMNs in coal mines are static, but there are also mobile nodes, such as the terminals for the personnel positioning system or the wireless sensors on the transport equipment. PIMAR does not yet consider the mobility of the nodes, which can cause frequent network topology changes and increase the difficulty of solving problems. The overhead of network topology information maintenance and ensuring stable links are the problems in the mobile network environment. In the future, we will pay more attention to node mobility and design our routing protocol to be more suitable for a network with unstable topology.

Footnotes

Handling Editor: Wei Yu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The financial support for this work provided by the Fundamental Research Funds for the Central Universities (No. 2017XKQY077) is gratefully acknowledged.

References

Feng

. The key technologies and application of mine wireless mesh network. Xuzhou, China: China University of Mining and Technology, 2011.

Akyildiz

Wang

. A survey on wireless mesh networks. IEEE Commun Mag 2005; 43(9): S23–S30.

Sharma

Kumar

Singh

. Routing in wireless mesh networks: three new nature inspired approaches. Wireless Pers Commun 2015; 83(4): 3157–3179.

Perkins

Belding-Royer

Das

. Request for comments: ad hoc on-demand distance vector (AODV) routing. Exp Internet Soc 2003; 6(7): 90.

Perkins

. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. ACM SIGCOMM Comp Com 1999; 24(4): 234–244.

Carrano

Magalhães

LCS

Saade

DCM

et al . IEEE 802.11s multihop MAC: a tutorial. IEEE Commun Surv Tut 2011; 13(1): 52–67.

Toh

. Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks. IEEE Commun Mag 2001; 39(6): 138–147.

Kim

Tomar

Shrivastava

et al . Load balanced congestion adaptive routing for mobile ad hoc networks. Int J Distrib Sens N 2014; 10(7): 1–10.

Basarkod

Manvi

. Node movement stability and congestion aware Anycast Routing in mobile ad hoc networks. In: Proceedings of the 2014 IEEE international advance computing conference, Gurgaon, India, 21–22 February 2014, pp.124–131. New York: IEEE.

10.

Jabbar

Ismail

Nordin

. Multi-criteria based multipath OLSR for battery and queue-aware routing in multi-hop ad hoc wireless networks. Wirel Netw 2015; 21(4): 1309–1326.

11.

Denko

. Enhanced routing metric for load-balancing in wireless mesh networks. J Interconnect Netw 2007; 8: 407–426.

12.

Dorigo

Maniezzo

Colorni

. Ant system: optimization by a colony of cooperating agents. IEEE T Syst Man Cy B 1996; 26(1): 29–41.

13.

Aissani

Fenouche

Sadour

et al . Ant-DSR: cache maintenance based routing protocol for mobile ad-hoc networks. In: Proceedings of the 3rd advanced international conference on telecommunications (AICT 2007), Morne, Mauritius, 13–19 May 2007, p.35. Washington, DC: IEEE Computer Society.

14.

Wang

Osagie

Thulasiraman

et al . HOPNET: a hybrid ant colony optimization routing algorithm for mobile ad hoc network. Ad Hoc Netw 2009; 7(4): 690–705.

15.

Nakagaki

Yamada

Tóth

. Intelligence: maze-solving by an amoeboid organism. Nature 2000; 407(6803): 470.

16.

Tero

Takagi

Saigusa

et al . Rules for biologically inspired adaptive network design. Science 2010; 327(5964): 439–442.

17.

Tero

Kobayashi

Nakagaki

. A mathematical model for adaptive transport network in path finding by true slime mold. J Theor Biol 2007; 244(4): 553–564.

18.

Liu

Song

Zhang

et al . Physarum optimization: a biology-inspired algorithm for the Steiner tree problem in networks. IEEE T Comput 2015; 64(3): 818–831.

19.

Marwan

. Amoeba-inspired network design. Science 2010; 327(5964): 419–420.

20.

Tsompanas

MAI

Sirakoulis

Adamatzky

. Physarum in silicon: the Greek motorways study. Nat Comput 2016; 15(2): 279–295.

21.

Chen

Qian

Liu

. A logistic distribution routes solving strategy based on the Physarum network and ant colony optimization algorithm. In: Proceedings of the 2015 IEEE 17th international conference on high performance computing and communications, New York, 24–26 August 2015, pp.1743–1748. New York: IEEE.

22.

Zhang

Adamatzky

Yang

et al . A Physarum-inspired approach to supply chain network design. Sci China Inform Sci 2016; 59(5): 052203.

23.

. An anticipation mechanism for the shortest path problem based on Physarum polycephalum. Int J Gen Syst 2015; 44(3): 326–340.

24.

Liu

Song

et al . Physarum optimization: a biology-inspired algorithm for minimal exposure path problem in wireless sensor networks. In: Proceedings of the IEEE INFOCOM, Orlando, FL, 25–30 March 2012, vol. 131, no. 5, pp.1296–1304. New York: IEEE.

25.

Zhang

et al . A novel Physarum-inspired routing protocol for wireless sensor networks. Int J Distrib Sens N. Epub ahead of print 1 January 2013. DOI: 10.1155/2013/483581.

26.

Zhang

Guan

et al . P-iRP: Physarum-inspired routing protocol for wireless sensor networks. In: Proceedings of the 2013 IEEE 78th vehicular technology conference, Las Vegas, NV, 2–5 September 2013, pp.1–6. New York: IEEE.

27.

Zhang

Guan

et al . A novel bio-inspired trusted routing protocol for mobile wireless sensor networks. KSII T Internet Inf 2014; 8(1): 74–90.

28.

Tang

Zhang

Jiang

. Physarum-inspired routing protocol for energy harvesting wireless sensor networks. Telecommun Syst. Epub ahead of print 21 August 2017. DOI: 10.1007/s11235-017-0362-8.

29.

Zhang

Yang

Han

. Architecture and routing algorithm of wireless mesh network for underground mine emergency rescue. J China Coal Soc 2013; 38(12): 2279–2284.

30.

Wang

. Design and implementation of mine low-power wireless mesh network. Min Saf Environ Protect 2015; 42(2): 28–31.

31.

. Application of wireless mesh network in coal mine emergency communication system. Coal Technol 2014; 11: 337–339.