A Novel Mesh Routing Using the Nodes with Identical Tree Level

Abstract

Contemporary wireless sensor network (WSN) adopts IEEE 802.15.4 in its MAC and PHY layers. The mesh routing introduced in IEEE 802.15.5 standard, referred to as the basic mesh routing below, improves reliability and robustness of routing in WSNs since there are multiple routes from a node to the sink. In this paper, the mesh routing with identical level (MRIL) is proposed, which constructs the mesh using the tree generated per IEEE 802.15.5 standard, the two-hop neighbors of the nodes, and the nodes in the same level chains with each consisting of the nodes having identical tree level. The MRIL outperforms the basic mesh routing in terms of energy consumption, the average number of hops traversed per packet, the sizes of memory used to keep neighbor lists and connectivity matrices at nodes, and the number of packet transmissions in exchanging link state information.

1. Introduction

Wireless sensor network (WSN), which consists of nodes with low power, low cost, weak process capacity, short radio range, and limited memory size, has been widely used in military, industrial, transportation, environmental protection, and other areas [1]. WSN has attracted extensive attention from researchers and is becoming core components of Internet of Things (IoT) [2]. Usually, tree-based routing protocols, such as Collection Tree Protocol (CTP) and others, are applied in gathering the data sensed by sensor nodes to the sink. There exists a shortcoming in tree-based routing that failure of a branch node prevents its descendant nodes from delivering their data to the sink. This problem is overcome by mesh-based routing, which is significant in improving routing reliability [3].

Contemporary WSNs adopt IEEE 802.15.4 standard [4], which targets low-rate wireless personal area networks (WPANs). IEEE 802.15.5 standard [5] defines the architectural framework that enables WPAN devices to promote interoperable, stable, and scalable wireless mesh topologies and it is composed of two parts: low-rate mesh and high-rate mesh networks. In this paper, we focus on the low-rate mesh network. That is, the mesh routing investigated in this paper resides on the IEEE 802.15.4 link layer.

An IEEE 802.15.5 low-rate mesh network starts by a mesh coordinator (MC) turning on its power to allow other nodes to join the network. In IEEE 802.15.5, address assignment is broken into two stages: the association stage and the address assigning stage [5]. During the association stage, a tree rooted at the MC is gradually formed when the IEEE 802.15.4 WPAN nodes join one after another (only when the associate request from a node is granted can the node be allowed to join the tree). The address assigning process consists of the bottom-up and top-down procedures. The former is used to report number of children while the latter for assigning addresses. In the bottom-up procedure, a leaf node, which is featured by the expiration of its timer set to the MeshIB attribute meshChildNbReportTime [5], reports to its parent a frame, called children number report frame (CNRF), which includes number of children (NoC) and number of requested addresses (NoRA) fields. Upon receiving the CNRFs from all its children, a branch node totals the NoCs and NoRAs in the CNRFs, respectively, and then adds 1 to NoC and its own NoRA to the totaled NoRA to generate a new CNRF, which is transmitted to its parent. The top-down procedure starts after the MC has received CNRFs from all of its children, in which the MC allocates consecutive 16-bit logical address (i.e., an address block) to each of its children if the number of available addresses is sufficient for the sum of the received NoCs. When a branch node obtains an address block, it assigns each of its children an address block. This process repeats till a leaf node is encountered. Figure 1 depicts a possible tree generated in address assignment [5, 6], where node A is the MC and the number in a square bracket beside a node indicates the number of children contained in a branch of the node. For example, node C in Figure 1 has three branches that contain 1, 2, and 1 node(s), respectively.

Figure 1

A tree generated by address assignment in IEEE 802.15.5 [5].

The above address assignment mechanism in IEEE 802.15.5 enables a node, say node X, to easily judge whether another node, say node Y, is its own descendant or not by simple checking whether the address of node Y belongs to the X's address block or not, which enables tableless routing, that is, routing without table. The tableless routing goes as follows. When a branch node receives a packet, it checks to see whether the destination address carried in the packet falls into one of the address blocks of its children. If so, the packet is forwarded down to the specific child; otherwise, the branch node forwards the packet to its parent. This process repeats at each intermediate node until the packet reaches its destination.

To overcome the drawbacks of tree-based routing, such as network partitioning resulting from a broken link in the tree, which prevents some nodes from delivering their data to the destination node, IEEE 802.15.5 standard introduces the mesh routing that allows every node to maintain its own local link state (LS) information so that data packets can be delivered to their respective destinations even when one or more links in the tree are broken. The mesh is built as follows. When a node receives an address block from its parent, it broadcasts Hello message to its meshTTLOfHello-hop neighbors to exchange LS information. Here, meshTTLOfHello is a MeshIB attribute. The Hello message contains its own address block, tree level, and the other information related to its one-hop neighbors. For instance, in Figure 2, node C broadcasts a Hello message containing the address block of node C, tree level of node C (i.e., 1), and the information of one-hop neighboring nodes A, B, F, G, H, and D to the nodes within the dotted circle when meshTTLOfHello is set to 2. Moreover, every node uses neighbor list and connectivity matrix to store the information of (meshTTLOfHello+1)-hop neighbors. Thus, after several rounds of exchanges of Hello messages, the mesh is formed, which consists of the tree and the (meshTTLOfHello+1)-hop neighbors of the nodes in the tree.

Figure 2

The 2-hop neighbors of node C.

In fact, the above mesh-constructing method has some drawbacks. First, for a given tree, it is hard for a node to choose a suitable value for the parameter meshTTLOfHello, which dominates how far Hello messages go and heavily affects the sizes of the neighbor list and the connectivity matrix because a larger meshTTLOfHello causes many nodes to take part in exchanging Hello messages, which consumes bandwidth and results in much overhead in maintaining LS information, whereas a smaller value may lead the constructed mesh not to function well in routing packets. Second, even though a suitable value of meshTTLOfHello is set, it is still not efficient. For example, in the case shown in Figure 2 in which meshTTLOfHello is defaulted to 2, nodes G, H, L, M, N, O, R, T, U, and V are descendants of node C so that their address information can be simply obtained by the traditional tree-based routing. As a result, the LS information of these nodes kept in node C is useless except consuming memory. Additionally, maintaining ancestor information in a node is also useless. In the same example, it is not necessary to keep the LS information of nodes A, C, and G at node L in Figure 2 since they are reachable through the tree-based routing. To remedy these drawbacks, we propose a novel mesh routing algorithm. The main contributions in this paper are as follows.

• (1)

The mesh-constructing method, called generating mesh from nodes with identical level (GMNIL), is presented, which builds the mesh using the tree generated per IEEE 802.15.5 standard, the two-hop neighboring nodes of the nodes in the tree, and the nodes with identical tree level. In other words, the proposed GMNIL lets a node simply keep the LS information of the nodes with tree levels identical to itself, together with the LS information of its two-hop neighbors, which removes unnecessary LS information kept in the neighbor lists and connectivity matrices of the nodes in the basic mesh routing introduced in IEEE 802.15.5 standard and thus reduces the sizes of the neighbor lists and the connectivity matrices so that memory usage is reduced.

(2)

The mesh routing with identical level (MRIL) is proposed, which outperforms both the basic mesh routing and the traditional tree-based routing in terms of energy consumption, the average number of hops traversed per packet, the memory sizes used to keep neighbor lists and connectivity matrices, and the number of packet transmissions in exchanging LS information.

The remainder of the paper is organized as follows. Related works are surveyed in Section 2, MRIL is presented in Section 3, the performance of MRIL is analyzed in Section 4, and we conclude the paper in Section 5.

2. Related Works

There are some works investigating IEEE 802.15.5 based mesh networks in literature. A compression scheme to reduce the overhead of IEEE 802.15.5 headers was proposed in [7]. The link-layer reliable broadcast protocol referred to as timer-based reliable broadcast (TRB) was presented in [8]. An effective and rapid address assignment algorithm for LR-WPAN mesh networks was presented in [9], which compresses the address assignment frame and changes the condition of address allocation in order to reduce control overhead and speed address assigning. The multicast tree with mesh (MTM) routing scheme that leverages mesh links for multicast routing was proposed in [10], which gains better performance than the basic tree-based multicast routing of IEEE 802.15.5 standard in terms of the number of participating nodes in multicast trees, control message overhead, and the number of data transmissions. Ren et al. [11] proposed an improved server routing algorithm for IEEE 802.15.5, which is able to obtain more LS information to find a better route without extra overhead, but the scheme exhibits the shortcoming that network topology information has to be collected periodically, resulting in considerable energy consumption, especially in large-scale networks. An on-demand routing protocol for IEEE 802.15.4 based low-rate wireless mesh networks was proposed in [12], in which route discovery packets are semidirectionally flooded in a distributed manner, but the flooding route discovery packets also bring tremendous energy consumption and longer latency. The energy aware multitree routing (EAMTR) for ZigBee was introduced in [13], which builds multiple routing trees and enables each node to select the route to the sink with the least congestion such that the energy consumption of nodes is balanced and the network lifetime is extended. The main disadvantage of EAMTR lies in that much energy and time is consumed in building multiple routing trees in initialization phase, which can be partly remedied by the enhanced tree routing (ETR) [14] and the shortcut tree routing (STR) [15] protocols that use one-hop neighbor information to build the near optimal routing path. The ETR and STR are worse than the basic mesh routing of IEEE 802.15.5 in finding the optimal routing and bypassing the failure nodes since only one-hop neighbor information is kept by the nodes.

The mesh routing protocols in the above surveyed works, including the basic mesh routing protocol introduced in the IEEE 802.15.5 standard, suffer from the problem that too long a source-to-destination route (that may go through the tree root) is traversed for a packet to reach the destination node especially when the source node and the destination node are in two separate branches of the tree. This situation is illustrated in the example shown in Figure 3 in the next section (refer to the paragraph below Figure 3). Additionally, the basic mesh routing of IEEE 802.15.5 has another problem that some useless items in the neighbor lists and connectivity matrices are kept in the nodes. The above problems are overcome by the MRIL presented in this paper. In other words, the MRIL has probably a shortcut with shorter hops than the route found in the existing routing protocols when delivering packets from the source node to the destination node. In addition, unlike the basic mesh routing in which the nodes need to determine the optimal value of the parameter meshTTLOfHello, a node under the proposed MRIL only exchanges LS information with its one-hop neighbors and those having the same tree level as the node, which reduces the number of packet delivery hops, memory usage, and energy consumption.

Figure 3

The nodes with the same level of 4.

3. The Mesh Routing with Identical Level (MRIL)

3.1. Terminologies

The main idea underlying MRIL is to let a node keep LS information of its sibling nodes in the tree rather than the ancestors and the descendants beyond two hops as they can be easily traversed through the traditional tree-based routing. For example, in Figure 2, for node V, nodes A and C are its ancestors beyond two hops. Hence, their LS information is not kept in node V. Instead, the LS information of node V's sibling nodes Q, R, T, U, and W, which have the same tree level of 4, together with the two-hop neighbors of node V, that is, the nodes H, I, M, N, O, P, X, Y, and Z, is maintained in node V. This case is illustrated in Figure 3, where Γ means tree level.

Now, we use an example to show the advantage of MRIL over the existing mesh routing schemes. Noting that the basic mesh routing of IEEE 802.15.5 is well-known, we compare MRIL with it. In Figure 3, suppose a packet is delivered from node Z to node Q. In the basic mesh routing, the parameter meshTTLOfHello is defaulted to 2. That is, a node keeps LS information about its (meshTTLOfHello+1)-hop neighbors (i.e., 3-hop neighbors), which is mentioned in Section 1. For instance, node H has the knowledge of node Q. Due to lack of information about node Q, node Z sends the packet to its parent, that is, node V, through which the packet is passed to node O and then to node H since nodes V and O do not have information about node Q. However, node H has LS information about node Q. As a result, the packet is passed to nodes G and K and finally to node Q. Thus, the length of the path the packet has travelled under the basic mesh routing is 6 hops. In the proposed MRIL, a node keeps the LS information of the nodes at the level same as itself. As a result, node Z only keeps the LS information of nodes X and Y rather than that of node Q. Hence, node Z sends the packet to its parent, that is, node V, through which the packet is delivered to nodes U, T, R, and Q since Q, R, T, U, and V are at the same level, that is, the 4th level, and each of them keeps the LS information of the others. Thus, the length of the path the packet has travelled is 5. In a word, the packet traverses a shorter route in the MRIL than that in the basic mesh routing.

Before presenting MRIL in detail, we introduce some terminologies as follows.

Same Level Node (SLN). Given a node X, a node is called an SLN of X if the node has the same tree level as X.

For example, nodes Q, R, T, U, and W are SLNs of node V in Figure 3.

Same Level Neighbor (SLNB). Given a node X, a node is called an SLNB of X if the node is X's one-hop neighbor and has the same tree level as X.

For example, nodes U and W are SLNBs of node V in Figure 3.

Same Level Neighborhood Set (SLNB-SET). The SLNB-SET of node X, denoted by SLNB-SET(X), is defined as the set that consists of X's SLNBs plus X.

For example, in Figure 3, SLNB-SET(V) = {U, V, W}.

Reducible Cluster (RC). An RC is a set that consists of the nodes with the same SLNB-SET. In particular, a node that has unique SLNB-SET forms an RC.

Hence, every node belongs to an RC. For example, in Figure 4, nodes S and T form an RC, because they have the same SLNB-SET {R, S, T, U}. Additionally, node W belongs to the RC {W}; that is, the RC only includes itself; set {Q} is another RC.

Figure 4

An example of RC.

Agent of Reducible Cluster (ARC). A node in an RC is called an agent of the RC (i.e., ARC) if it forwards the LS information on behalf of the other nodes in the same RC.

For example, in Figure 4, node T becomes an ARC of the RC consisting of elements of S and T (i.e., the set {S, T}) if T forwards LS information for node S. In particular, a node can be an ARC of the RC consisting of itself. For instance, node W is an ARC in Figure 4.

Same Level Chain (SL Chain). Given a tree level Γ, an SL chain with level Γ is defined as the set of ARCs with tree level Γ in which any two ARCs can communicate with each other directly or in a multiple-hop manner.

For example, nodes Q, R, T, U, V, and W constitute an SL chain with level 4.

3.2. Extended Neighbor List and Connectivity Matrix

In MRIL, every node keeps a 2-dimension table, called extended neighbor list (EN-List), to maintain the information of the nodes at most Γ hops apart. Each of the nodes in the EN-List is called an extended neighbor of the node. The attributes of the EN-List include NodeID, begAddr, endAddr, treeLevel, relation, RCAgent, NumHops, nextHop, and state. Here, NodeID is the ID of an extended neighbor; begAddr and endAddr are the beginning and ending addresses of the address block assigned to the extended neighbor, respectively; treeLevel means the tree level of the extended neighbor; the relation between the extended neighbor and the node is represented by relation field that takes one of the enumeration values of PARENT, CHILD, SL NODE, and COMMON NEIGHBOR; RCAgent indicates the address of the ARC of the RC including the extended neighbor; NumHops is the number of hops between the node and the extended neighbor; nextHop keeps the next hop towards the extended neighbor; state represents the state of the extended neighbor. Each row of EN-List keeps the information of one of its extended neighbors.

Moreover, a node uses a connectivity matrix to maintain the LS information of its extended neighbors for no more than two hops. An example of the connectivity matrix of two-hop neighbors is shown in Table 1, in which the cross of a row and a column is used to indicate whether the corresponding nodes are directly connected (set to 1) or not (set to 0) and the diagonal of the table is useless. The connectivity matrix is symmetric, which indicates that all links in the network are bidirectional. In fact, Table 1 is the connectivity matrix of node C in Figure 2.

Table 1

An example of connectivity matrix at node C.

	C	A	B	F	G	H	D	K	L	M	N	O	I	E
C		1	1	1	1	1	1	0	0	0	0	0	0	0
A	1		1	0	0	0	1	0	0	0	0	0	0	1
B	1	1		1	0	0	0	0	0	0	0	0	0	0
F	1	0	1		1	0	0	1	0	0	0	0	0	0
G	1	0	0	1		1	0	1	1	1	0	0	0	0
H	1	0	0	0	1		1	0	0	1	1	1	1	0
D	1	1	0	0	0	1		0	0	0	0	0	1	1
K	0	0	0	1	1	0	0		1	0	0	0	0	0
L	0	0	0	0	1	0	0	1		1	0	0	0	0
M	0	0	0	0	1	1	0	0	1		1	0	0	0
N	0	0	0	0	0	1	0	0	0	1		1	0	0
O	0	0	0	0	0	1	0	0	0	0	1		1	0
I	0	0	0	0	0	1	1	0	0	0	0	1		1
E	0	1	0	0	0	0	1	0	0	0	0	0	1

3.3. Frame Formats of Command Frames Used in MRIL

To support MRIL, we introduce the command frames OHHello, RCAgentAnnouncement, and MRILHello. OHHello is used to exchange connectivity information among one-hop neighbors, which has the payload similar to the Hello frame defined in IEEE 802.15.5. The main difference between OHHello and Hello frames is that the three fields Number of Multicast Groups, Addresses of One-hop Neighbors, and Addresses of Multicast Groups in Hello frame [5] are replaced with the field of Information of One-hop Neighbors shown in the third line in Figure 5, where the table in the first line is copied from IEEE 802.15.4 standard [4]. RCAgentAnnouncement is used for a node to announce itself as the ARC for its SLNBs. Its format is illustrated in Figure 6, where the fields of Address, ARC Indicator, Size of RC, and Addresses of Nodes in RC hold the beginning address of the source, the ARC indicator of the source calculated from (1) given in Section 3.4, the number of nodes in the RC including the source, and the short addresses of all nodes in the RC including the source, respectively. MRILHello command frame is used to propagate LS information in SLNs, which has the format shown in Figure 7. The MRIL control field in Figure 7 possesses one octet that consists of the bits used as flags, which are explained in Table 2. The tree level field contains the tree level in which the current command frame is propagated. The number of SLNs field carries the number of SLNs contained in the information of SLNs field. For a given tree level Γ, the information of SLNs field keeps the information of SLNs with at most Γ hops, which has the format shown in Figure 8.

Table 2

Flags in the MRIL control field.

Bit	Flag	Description
b7	Active SLNs	When this flag is set, it indicates that the SLNs being carried are active; otherwise, they are failed ones.
b6	More SLNs	When this bit is set, it indicates that more MRILHello command frames follow. This flag is used to fragment an MRILHello message, which is unable to fit in the payload of a single MAC-layer service data unit, into multiple MRILHello command frames.
b0–b5	Reserved

Figure 5

Format of OHHello command frame.

Figure 6

Format of RCAgentAnnouncement command frame.

Figure 7

Format of MRILHello command frame.

Figure 8

Format of “information of SLNs” field.

The frame control field shown in Figures 5–7 is described in IEEE 802.15.4, which includes two flags: one is used to indicate whether 16-bit short address is used in the fields of the destination address and/or source address and the other is used to indicate whether unicast and acknowledgement are requested.

3.4. Selecting ARC in MRIL

In the association stage, when a node receives more than one association reply, it selects the node with the smallest tree level as its parent, which makes SL chains longer. In the address requirement report stage, every node reports to its parent the depth of the subtree rooted at itself in addition to NoC and NoRA in order to make each tree level have a node whose beginning address is identical to its tree level. In the address assigning stage, if the beginning address of a node is equal to its tree level, the node assigns the second address in its address block as the beginning address of the child with the deepest subtree. Thus, there is at most one node in each level whose beginning address equals its tree level.

After a node has been assigned 16-bit address, it broadcasts OHHello messages (see Figure 5) and then it sets the parameters: OHHelloTxTimer = cOHHELLOINTERVAL and OHHelloTxFlag = false. When a node received the OHHello message, it uses the carried LS information to update its EN-List and connectivity matrix (see Table 1). If the received LS information differs from that kept in its EN-List and connectivity matrix, the node sets OHHelloTxFlag = true, which triggers the node to rebroadcast the OHHello message and reset OHHelloTxTimer and OHHelloTxFlag when the OHHelloTxTimer expires.

Through the exchanges of OHHello messages, every node knows the LS information of its two-hop neighbors, which enables it to find its RC and select a node as the ARC of the found RC. The algorithm of finding the RC is shown in Algorithm 1, in which c denotes the node running the algorithm and $nb$ is an SLN of node c.

Algorithm 1: Find RC(c).

$\text{RC}=\{c\}$ ;

Foreach  nb   In  SLNB-SET(c)-{c}

 If  SLNB-SET(nb) = SLNB-SET(c)  Then   $\text{RC}=\text{RC}\cup \{nb\}$

Endfor

Return  RC;

In MRIL, we use the ARC indicator (ARCI) function in (1) to indicate that a node becomes an ARC of an RC, which reflects the fact that an ARC should be with fewer children, more remaining energy, and better link quality than its SLNBs:

$$\begin{array}{l}\text{ARCI}\left(c\right)=\frac{E_r\left(c\right)}{\left[\mathrm{1}+\text{DC}\left(c\right)\right]\left|\Omega \left(c\right)-\left\{c\right\}\right|}\hfill \\ \hspace{1em}\times {\displaystyle \prod }_{b\in \Omega \left(c\right)-\left\{c\right\}}^{}\text{LQ}(c,b),\hfill \end{array}$$

(1)

where c is a node and b is a neighbor of node c; $\Omega \left(c\right)$ is the set of SLNB-SET $(c)$ ; $E_r(c)$ , $\text{DC}(c)$ , $\text{LQ}(c,b)$ , and $\left|\Omega \left(c\right)-\{c\}\right|$ denote the remaining energy of node c, the number of descendants of node c, the link quality between the nodes c and b, and the number of SLBNs of node c, respectively.

To make nodes evenly expend energy, we let the nodes in an RC act as an ARC in turn. In the first round, any node with ARCI bigger than the value of the parameter thresholdARCI announces itself as the ARC after it completes broadcasting OHHello messages. It sets the PIB attribute RCAgent to its address and broadcasts an RCAgentAnnouncement message (see Figure 6) to its SLNBs. When an SLNB receives the message, it updates its EN-List and RCAgent. If a non-ARC node finds its ARCI bigger than that of the ARC in the current round, it announces itself as the ARC in the next round. If the current-round ARC is aware that no node takes its place within the duration of the parameter cMRILARCCYCLE, it announces itself as the ARC again. The state transition diagram of a node is illustrated in Figure 9, where state “ARC” indicates that a node is the ARC, state “NARC” indicates that a node is non-ARC and unwilling to be the ARC, and state “ARCC” indicates that a node is non-ARC but it intends to become the ARC.

Figure 9

State transition diagram.

At a given tree level of Γ, after a node finishes broadcasting OHHello messages, upon being aware of being an end of the SL chain, it initiates the same level LS information propagation by sending an MRILHello message (see Figure 7) to its unique ARC neighbor at the same tree level. If a node whose beginning address is equal to its tree level does not receive an MRILHello message after the duration of   $T_{\text{delay}}\times \Gamma$ , which may happen when all of its SL nodes form a circle, that is, the SL chain at the current level has no end, the node stops broadcasting OHHello and acts as an end of the SL chain to initiate the same LS information propagation. Here, $T_{\text{delay}}$ represents the expected one-hop unicast transmission delay.

When a node receives an MRILHello, it checks whether the message is from one of its SLNBs. If not, the message is ignored; otherwise, it uses the received message to update its EN-List, adds the information of nodes of its RC to the MRILHello message, and removes the information of nodes with distance larger than $\Gamma -1$ hops in its EN-List. Then it sends the updated MRILHello message to the SLNBs except the ARC the MRILHello comes from.

When a node detects a failed SLNB, which causes some SLNs to be unreachable, the node first fills the information of the unreachable SLNs with distance no larger than $\Gamma -1$ hops and then sets the corresponding bit (b7 bit) of the control field of the MRILHello message to indicate that the SLNs being carried are unreachable. Then, the node sends the MRILHello message to its living SLNBs. When a node receives an MRILHello message carrying unreachable SLNs from its SLNB, it uses the received message to update its EN-List and removes the information of SLNs with distance larger than $\Gamma -1$ hops from the MRILHello message. Then, it sends the updated MRILHello message to the SLNBs except the one from which the MRILHello comes.

3.5. Routing Procedure in MRIL

The routing procedure of MRIL is as follows. When a node receives a packet, it checks whether the destination of the packet matches with itself. If yes, it hands the received packet to the upper layer, that is, the network layer. Otherwise, it forwards the packet according to the following four rules.

Rule (i). If the destination is one of its descendants, the packet is passed down to the destination along the tree path.

Rule (ii). If the destination is one of the nodes in its EN-List, the packet is forwarded to the corresponding next-hop node in the EN-List.

Rule (iii). If the destination is a descendant of its extended neighbor, the packet is forwarded to the extended neighbor, through which the packet is passed down to the destination with the same procedure as in Rule (i).

Rule (iv). If no information about the destination is in the node, the packet is forwarded to its parent.

4. Performance Analysis

We compare the proposed MRIL with the IEEE 802.15.5 mesh routing (the basic mesh routing for short) in terms of energy consumption, number of transmissions for maintaining LS information, and memory usage through simulations. In the simulations, we deploy 400 nodes in a square of 2000 × 2000 m². For a randomly generated network topology, a node is randomly selected as the sink and the routing tree rooted at the sink is formed per IEEE 802.15.5 standard, and then 5000 pairs of source and destination nodes are randomly selected (some nodes may be selected more than once) and each pair delivers one packet with size of 100 B. The results shown below are from the average of 1000 randomly generated topologies.

To measure energy cost, we adopt the energy consumption model proposed in [16]; that is, the energy consumption for transmitting an x-bit packet over distance d, denoted by $E_{tx}(x,d)$ , and the energy consumption for receiving the packet, denoted by $E_{rx}(x)$ , are as follows:

$$\begin{array}{cc}& E_{tx}\left(x,d\right)=x\left({\epsilon }_{\mathrm{0}}+{\epsilon }_{\mathrm{1}}{d}^{\gamma }\right),\\ E_{rx}\left(x\right)=x{\epsilon }_{\mathrm{0}},\end{array}$$

(2)

where ${\epsilon }_{\mathrm{0}}$ denotes the energy consumption resulting from digital coding, modulation, filtering, spreading of the signal, and so forth, ${\epsilon }_{\mathrm{1}}$ is the energy consumed by the transmitter power amplifier, and γ is path loss parameter valued in 2 through 4.

We use Visual Basic programming language to make the simulation programs and the values of all parameters used in the simulations are listed in Table 3.

Table 3

Parameters and values.

Parameter	Value
d	150 m
meshTTLOfHello	2
$T_{\text{delay}}$	20 slots
cOHHELLOINTERVAL	5  ×   $T_{\text{delay}}$
cMRILARCCYCLE	10000 slots
x	100 B
γ	2
${\epsilon }_0$	50 nJ/bit [16]
${\epsilon }_1$	10 pJ/bit/m2 [16]

First, we compare MRIL with the basic mesh routing in terms of the sizes of connectivity matrix and extended neighbor list, which are shown in Figures 10-11. From the figures, we observe that MRIL has less sizes of connectivity matrix and neighbor list than the basic mesh routing. In other words, MRIL uses less memory than the basic mesh routing.

Figure 10

Size of connectivity matrix versus tree level.

Figure 11

Size of neighbor list versus tree level.

Second, we consider the average number of hops in delivering packets and the climax energy consumption of nodes, together with its corresponding variance of nodes, which are shown in Figures 12–15. It can be seen from Figure 12 that MRIL delivers packets with less hops than both the basic mesh routing and the traditional tree-based routing. From Figure 13, we observe that the climax energy consumption of the nodes in MRIL is lower than the other two schemes, which indicates that, among them, MRIL gains the longest network lifetime, which is defined as the period from the instant of a network being formed to that of a node being dead [17]. Figure 14 exhibits that MRIL expends less energy than the other two routing schemes, which agrees with Figure 12, as we do not take packet loss ratios of links into account so that energy consumption is proportional to number of hops. From Figure 15, we see that MRIL achieves the lowest standard deviation, which indicates that energy is expended more evenly in MRIL compared to the other two schemes.

Figure 12

Comparison of the average number of hops.

Figure 13

Comparison of the climax energy consumption of nodes.

Figure 14

Comparison of the average energy consumption of nodes.

Figure 15

Comparison of the standard deviation of energy consumption of nodes.

The numbers of transmissions needed for the nodes to maintain LS information under MRIL and the basic mesh routing are compared in Figure 16, which reveals that MRIL has less overhead in maintaining LS information than the basic mesh routing.

Figure 16

Comparison of the number of transmissions for maintaining LS information.

Third, we compare the MRIL with the tree-based routing in terms of the number of packet transmissions. The main difference between the MRIL and the tree-based routing is in that under the former nodes need to exchange Hello message to build the mesh whereas those under the latter do not. We use $N_{\text{mesh}}$ to represent the number of transmissions for Hello messages in MRIL. Given a number of the node pairs in communications (NNPiC), we use $N_{\text{tree}}$ and $N_{\text{MRIL}}$ to represent the number of packet transmissions in the tree-based routing and the MRIL, respectively. Then, we obtain Figure 17, where the dotted line plots $N_{\text{tree}}$ and the solid line plots $N_{\text{mesh}}+N_{\text{MRIL}}$ , which stands for the total packet transmissions performed in the MRIL, including those for constructing the mesh. It can be observed that, in terms of the number of packet transmissions, the MRIL is worse than the tree-based routing when NNPiC is small, but it outperforms the tree-based routing when NNPiC becomes large. In fact, only when $N_{\text{mesh}}<N_{\text{tree}}-N_{\text{MRIL}}$ does $N_{\text{mesh}}+N_{\text{MRIL}}<N_{\text{tree}}$ hold. In other words, only when the saved number of packets transmissions is larger than the number of the packet transmissions conducted in constructing the mesh can the MRIL be better than the tree-based routing.

Figure 17

Number of transmissions versus NNPiC.

Last, we evaluate the performance of MRIL in the scenarios with unreliable wireless links, which cause some nodes to fail. We conduct the experiments for the cases where 1%, 2%, 5%, 10%, 15%, and 20% of the nodes are failed ones, which lead to Figure 18. From the figure we observe that (1) the average number of hops in both of the MRIL and the basic mesh routing increases as the proportion of failure nodes grows, which agrees with the intuition that more hops are needed to build a path bypassing the failed nodes; (2) the average number of hops in the MRIL increases faster than that in the basic mesh routing, which reflects the fact that the length of LS chains in the MRIL is shortened when the proportion of failure nodes increases, thus degenerating the performance of the MRIL.

Figure 18

The average number of hops versus the proportion of failure nodes.

5. Conclusion

In the proposed MRIL, the mesh consists of the nodes in the tree generated per IEEE 802.15.5 standard, those with the same tree level, and the two-hop neighbors of the nodes in the tree. MRIL increases reliability in delivering packets to the sink node since there are more routes from a node to the sink, which overcomes the shortcoming existing in the traditional tree-based routing that the node could not deliver its packet to the sink when a node on the route to the destination fails. Moreover, MRIL has the advantages over the basic mesh routing given in IEEE 802.15.5 standard. That is, it removes some useless items in connectivity matrices and neighbor-lists for ancestors and descendants in the basic mesh routing, and a node in MRIL needs not decide on how many hops of its neighbors to be kept in its connectivity matrix and neighbor-list. Compared to the basic mesh routing, MRIL is able to reduce energy consumption in communications and saves memory in keeping link state information, which is applicable to IEEE 802.15.4 based WSNs whose nodes have quite limited memory sizes and battery energies.