Exploiting channel and interface heterogeneity for rate separating channel assignment in IEEE 802.11 wireless multimedia sensor networks

Abstract

In wireless multimedia sensor networks (WMSNs), disaster control and public safety are crucial issues that focus on emergency management, rescue, and emergency medical services. For high data rate requirement of WMSNs, the IEEE 802.11 specification can be used for the radio interface of sensor nodes, and the nodes can be equipped with multiple 802.11 radios to utilize multiple channels and link data rates. In practical IEEE 802.11 WMSNs, a link shows different link qualities depending on the operating channels and interfaces between two nodes, called channel and interface heterogeneity. In multirate WMSNs, low-rate links severely degrade the capacity of high-rate links, known as rate anomaly. In this article, we propose a novel channel assignment protocol, heterogeneity-aware mesh (HMesh), to address both rate anomaly mitigation and the channel and interface heterogeneity in real IEEE 802.11 WMSNs. HMesh constructs a tree-based WMSN using the proposed channel assignment and routing metric and the heuristic channel assignment algorithm. With the metric and heuristic algorithm, HMesh separates different data rate links by considering the channel and interface heterogeneity. Through extensive simulations and experiments on our IEEE 802.11 WMSN test bed, we demonstrate that HMesh significantly outperforms existing channel assignment protocols in IEEE 802.11 WMSNs.

Introduction

Disaster control and public safety have been widely studied in wireless sensor networks. ¹ Conventional studies primarily focused on detection and efficient reporting from sensing nodes to a sink node (gateway); however, recent studies have expanded to cover rescue, recovery, and safety. In these recent studies, wireless multimedia sensor networks (WMSNs) are dealing with a large volume of multimedia traffic.

In WMSNs, one of the challenging issues is network capacity. To support multimedia traffic in wireless sensor networks, high data rates network interfaces are required. IEEE 802.11 is a popular standard which is using wide bandwidth to achieve high data rates. Mobile sensor nodes in WMSNs can be equipped with multiple network interface cards (NICs) such as IEEE 802.11 that supports multiple channels and data rates. Clearly, concurrent transmissions over multiple nonoverlapping channels can improve the capacity of WMSNs substantially. However, the number of available channels is limited in IEEE 802.11. For example, IEEE 802.11b/g and 802.11a define up to 3 and 12 nonoverlapping channels, respectively. Moreover, a node cannot use a number of channels larger than the number of equipped NICs. These facts severely decrease the number of concurrent transmissions and the capacity of WMSNs. To combat this problem, extensive channel assignment protocols have been explored.^2–11

In practical IEEE 802.11 WMSNs, it has been shown that there exists channel heterogeneity for IEEE 802.11 channels and interface heterogeneity for different pairs of interfaces. Using actual measurements, Subramanian et al. ¹⁰ observed the channel and interface heterogeneity in the IEEE 802.11 test beds. That is, different IEEE 802.11 channels and different interface pairs for a single link show different link qualities depending on the signal propagation environment, multipath effect, antenna distances, and so on. In addition, the link quality for each channel is relatively stable in received signal strength (RSS) for long periods of time ¹⁰ or in signal-to-noise ratio for a period of several seconds. ¹² Thus, we can improve the capacity of WMSNs by exploiting the channel and interface heterogeneity in IEEE 802.11 with low control overheads among nodes for link quality measurements on each channel and interface pair.

Today’s IEEE 802.11 devices also provide the multirate functionality in addition to multiple channels. For instance, IEEE 802.11a/g and 802.11b support from 6 Mbps to 54 Mbps and from 1 Mbps to 11 Mbps, respectively, depending on the channel condition. However, when high-rate links contend with low-rate links on the common channel, the capacity of high-rate links is severely degraded by low-rate links, known as rate anomaly. ¹³ To solve this problem, extensive works have been made with 802.11 extensions mainly for single-channel networks.^14–19 For multichannel networks, there have been several rate separation works that separate high-rate links from low-rate links by exploiting multiple channels and interfaces without 802.11 extensions.^20–27

Our research objective in this article is to develop a novel channel assignment protocol, called heterogeneity-aware mesh (HMesh), to exploit “channel and interface heterogeneity” for “rate separation” in IEEE 802.11 multiradio multirate WMSNs. In HMesh, each node is equipped with multiple NICs and forms a tree architecture rooted at a sink node to deal with the traffic distribution of WMSNs. Parent nodes have higher priority than child nodes, since they serve more traffic than child nodes. Each node joins a parent on the tree using the proposed channel assignment and routing metric, called heterogeneity-aware transmission time (HATT). After tree join, each node provides Internet paths to its child nodes. Once a parent receives a request from a new child node to join the tree, it runs an efficient algorithm, called heterogeneity-aware rate separating (HRS) algorithm that separates different data rate links between the parent and its child nodes by exploiting the channel and interface heterogeneity.

Our contributions can be summarized as follows. First, the proposed protocol addresses both the channel heterogeneity of IEEE 802.11 channels and the interface heterogeneity of interface pairs. Existing channel assignment protocols assumed all channels and interface pairs to be homogeneous, which cannot reflect the channel and interface heterogeneity, or some existing protocols reflect channel heterogeneity only without considering interface heterogeneity. Second, our protocol also takes rate anomaly into account by separating different data rate links through multiple channels and NICs. This rate separation approach makes concurrent transmissions on multiple channels and NICs. Third, our protocol does not modify the legacy IEEE 802.11 devices, since it just utilizes and assigns multiple channels to available NICs. This significantly reduces the WMSN deployment cost, and thus our protocol is suitable for the commodity IEEE 802.11 WMSNs. Last, we conducted extensive ns-2 simulations and real experiments on the IEEE 802.11a test bed to show that our protocol highly outperforms existing channel assignment protocols designed for 802.11 WMSNs. To the best of our knowledge, HMesh is the first work on channel assignments to exploit both channel and interface heterogeneity and rate separation for rate anomaly mitigation in IEEE 802.11 multiradio multirate WMSNs.

This article is structured as follows. In the section Related work, we survey related work. Section System model and motivations motivates our channel assignment work. In the section titled Heterogeneity-aware mesh, we propose the detailed HMesh protocol. Sections Simulation results and Experiment results evaluate the performance of HMesh using simulations and experiments on our IEEE 802.11 test bed. In the section Conclusion, we conclude this article.

Related work

In recent years, extensive protocols have been suggested for channel assignments.^3–10 These protocols can be grouped as distributed approaches^3–5 and centralized approaches.^6–10 In distributed approaches, nodes assign channels by exchanging control messages with neighbor nodes. For example, Raniwala et al. ³ proposed the tree-based architecture, called Hyacinth. Gateways are the root of the trees, and each node joins its parent to access the Internet and provides the Internet paths to its child nodes. Nodes select their parents using a well-known hop-count metric. Dhananjay et al. ⁴ suggested an extension of the tree architecture, rounting over multi-radio access network (ROMA). By assigning distinct channels to links on a path to the gateway, ROMA eliminates intrapath interference. Moreover, ROMA also mitigates interpath interference by allocating different channel sequences to paths associated with different gateways.

In centralized approaches, a central node such as gateway gathers the whole information on networks periodically. Then, an optimized algorithm is used to maximize the performance of networks or to minimize the interference in networks. The distributed algorithm is modified in the study done by Subramanian et al. ¹⁰ to address the channel heterogeneity of 802.11 channels. The modified algorithm shows improved performance compared to the original distributed algorithm. However, the modified algorithm focuses on minimizing the network interference, which differs from our work in that we focus on utilizing the rate separation to mitigate rate anomaly in IEEE 802.11 multirate networks.

Various protocols have been proposed to overcome rate anomaly.^14–19 These works mainly focus on single-channel multirate networks such as wireless local area networks (WLANs) and modify the legacy 802.11 devices (i) by controlling medium access parameters of contending nodes, such as contention window size, ¹⁴ initial back-off window, and frame sizes ¹⁵ ; (ii) by cooperative relaying data frames from nodes using low-rate links^16–18; and (iii) by multiple back-to-back transmissions via good quality links. ¹⁹ One may argue that these works can be used easily in multichannel networks, when each node has multiple NICs. However, this does not provide a specific operation for IEEE 802.11 multichannel multiratio networks.

To solve rate anomaly in multichannel multirate networks, multiband opportunistic auto rate (MOAR) extended from the study by Sadeghi et al. ¹⁹ has been developed.^28,29 Each node equipped with a single interface skips available channels in search of high-quality channels. A pair of nodes meets at a common channel, home channel, for a channel reservation. Since one data transmission occupies the home channel until it finishes, MOAR cannot take advantage of concurrent transmissions over multiple channels. Hence, MOAR is different from our work that focuses on the rate separation via multiple NICs, which activates concurrent transmissions over multiple channels.

To utilize rate separation for rate anomaly mitigation, there have been several channel assignment protocols.^20–27 These protocols do not modify the commodity 802.11 devices, since they just utilize and assign channels to available NICs. Instead, they assume multiple NICs per node. For single-hop networks, multirate multichannel (MRMC) and data rate adaptive channel assignment (DR-CA) are proposed.^20,21 MRMC assumes multiradio multirate single-hop networks such as WLANs. ²⁰ An access point (AP) has multiple NICs assigned with one data rate and one channel. Nodes then attempt to join one proper NIC of AP after channel condition measurement. DR-CA is a centralized algorithm that assumes IEEE 802.11 multiradio multirate single-hop networks. ²¹ DR-CA assigns a distinct channel to each NIC and sorts all links in descending order of their data rates. Then, it assigns channels to balance the sum of data rate values on each channel.

For rate separation in multihop networks, rate-based channel assignment (RB-CA) is proposed.^22,23 RB-CA assumes the tree architecture, and it forms high-rate multihop paths on the tree instead of low-rate single-hop paths to alleviate rate anomaly. In the study by Kim et al.,^24,25 cooperative channel assignment (CoCA) builds a tree-based architecture and uses both primary links (between parent nodes and child nodes) and secondary links (between two child nodes belonging to the same parent). In addition, CoCA uses a heuristic algorithm, called the balancing algorithm, to distribute different data rate links over multiple channels. In the study by Lin et al., ²⁶ rate-loss-based channel assignment uses the rate loss function that addresses the rate anomaly problem to assign channels. In the study by Lin and Chou, ²⁷ the channel assignment is formulated as the joint routing and channel assignment problem, and it is solved using an optimization model that reflects rate anomaly in a centralized fashion.

These protocols that utilize rate separation assume that all the IEEE 802.11 channels and NICs are homogeneous. For example, when the data rate of link A-B from node A to node B is 54 Mbps on channel 1, its data rate is also 54 Mbps for all the other channels. However, the data rate of link A-B may vary depending on the selected channels or interfaces due to channel and interface heterogeneity. In particular, these protocols may degrade the effect of rate separation (i.e. rate anomaly mitigation), since they do not know different data rates on different channels. This degrades the network capacity severely. In the study by Leith et al., ¹¹ the channel assignment algorithms reflect channel heterogeneity, which requires no communication between interfering WLANs. In this article, our proposed protocol utilizes the channel and interface heterogeneity as well as the rate separation to mitigate rate anomaly in IEEE 802.11-based WMSNs effectively.

System model and motivations

System model

Our target system is IEEE 802.11 multiradio multirate WMSNs including stationary mesh nodes without mobility. Each node has two or more IEEE 802.11 NICs, and all NICs use omni-directional antennas. The number of NICs on a node is smaller than the number of channels for the practical deployment of WMSNs. Although today’s IEEE 802.11n/ac product can support 802.11e that provides transmit opportunity (TXOP) adjusting for addressing rate anomaly in the single-channel networks, we cannot assume that all the 802.11 products support 802.11e in mandatory. Hence, we consider the 802.11 networks possibly including legacy 802.11 products which may not use 802.11e. For the rest of this article, we assume the legacy IEEE 802.11a NICs, which provides higher link data rates than IEEE 802.11b and larger number of channels than 802.11b/g.

Our research objective in this article is not “rate adaptation” that selects an optimal link data rate, but rate separation using channel assignments to separate high-rate links from low-rate links via multiple channels and NICs. Hence, we assume that the transmitter of a link can get its best data rate of the link in each channel and interface pair by the aid of a well-known rate adaptation protocol.^30,31 Even though the link quality may be dynamic for a short term such as multiple milliseconds depending on the channel condition, it has been observed that the long-term behavior of link quality is relatively stable over periods of multiple seconds.^9,10,12 Therefore, we assume that the data rate of links on each channel and interface pair is relatively stable for a multiple-second time as provided in literature.^{9,10,12,20–27}

Motivation 1: Channel and interface heterogeneity

Using our IEEE 802.11a WMSN test bed, we observe the channel and interface heterogeneity to motivate our work on designing a rate separating channel assignment protocol. First, we discuss the channel heterogeneity by measuring the RSS values of a single link per second for each IEEE 802.11a channel in a round-robin fashion. For each channel, we generated a saturated user datagram protocol (UDP) flow with the packet size of 1500 bytes over the single link during 20 s.

Figure 1(a) shows the results of RSS values with time on four IEEE 802.11a channels 36, 48, 52, and 153. Figure 1(b) shows the averaged RSS values of IEEE 802.11a channels from 36 to 165 with the 95% confidence interval, which are averaged from five repeated experiments over 20 s. As observed from Figure 1(a), the RSS value of each channel is relatively stable for a multiple-second time period. According to Subramanian et al., ¹⁰ the similar results (i.e. the RSS values of a link are relatively stable over long periods of time) are observed for both IEEE 802.11a and 802.11g WMSN test beds. From Figure 1(a) and (b), we can observe a difference in RSS values over 18 dBm among 802.11a channels. Also, there is no correlation between the link quality values of different 802.11a channels and the channel number. That is, the RSS values do not increase or decrease as the channel number increases.^9,10,12

Figure 1.

Channel and interface heterogeneity in IEEE 802.11a WMSNs. WMSNs: Wireless Multimedia Sensor Networks.

The fundamental reason of this channel heterogeneity is (i) different signal propagation environments for different 802.11 channels ¹⁰ and (ii) multipath effect. ¹² In particular, wireless signals traverse different paths and they have different phases. As a result, those signals are combined at the receiver node in a constructive or destructive way. This increases or decreases the RSS value at the receiver node, which leads to the channel heterogeneity of different channels.

Next, we observe the interface heterogeneity on our IEEE 802.11a WMSN test bed. For a single link between two nodes equipped with two 802.11a NICs, we generated a saturated UDP flow with the packet size of 1500 bytes from a node (say node X) to the other node (say node Y) during 20 s on the same channel. By varying the pair of actual NICs, we measured the RSS values of the single link. Figure 1(c) shows the results averaged from five repeated experiments with the 95% confidence interval. Here, the interface pair indicates the actual NIC ID of node X and node Y. For example, when the interface pair is (1, 2), we used the first NIC of node X and the second NIC of node Y. From Figure 1(c), we can see a difference in RSS values over 10 dBm depending on the interface pairs (i.e. interface heterogeneity). Moreover, there is no correlation between the interface pair and the link quality. The similar results are also observed in the study by Subramanian et al. ¹⁰ According to the study by Subramanian et al., ¹⁰ the key reason of interface heterogeneity is (i) inherent manufacturing variations among the operation NICs and (ii) the actual distance between different antenna pairs of NICs.

In stationary system such as WMSNs comprising fixed nodes without mobility, the data rate of links increases in general when the measured RSS value of links increases.^15,20–27 That is, the link data rates can be different depending on the operating channels and interface pairs. Hence, an intelligent channel assignment protocol should consider the channel and interface heterogeneity in IEEE 802.11 WMSNs.

Motivation 2: Rate anomaly and rate separation in WMSNs

Next, we observe rate anomaly in WMSNs and highlight the advantage of rate separation for rate anomaly mitigation using experiments on our IEEE 802.11a test bed. Figure 2(a) shows an example of multihop flows, where there are four nodes A, B, C, and D within the interference range of each other, and two multihop flows A-B-D and A-C-D are generated. Each node has two NICs and uses two nonoverlapping channels 36 and 64. Each link is labeled by the link data rate and channel number. In case 1 (Figure 2(a) and (b)), node A generates a multihop flow A-B-D over 54 Mbps link A-B on channel 36 and 54 Mbps link B-D on channel 64. At the same time, node A generates a multihop flow A-C-D over 18 Mbps link A-C on channel 36 and 18 Mbps link C-D on channel 64. As a result, two multihop flows over different rate links 54 Mbps and 18 Mbps contend on the same channel. For example, 54 Mbps link A-B and 18 Mbps link A-C share channel 36. This incurs rate anomaly, since high-rate links such as links A-B and B-D suffer from low-rate links A-C and C-D on the common channels.

Figure 2.

Illustrations for rate anomaly and rate separation. (a) A scenario of multihop flows. (b) Initial assignment (case 1). (c) Homogeneous setting (case 2). (d) Heterogeneous setting (case 3).

To mitigate rate anomaly, we can assign channels differently by separating high-rate links from low-rate links. When channels and NICs are assumed to be homogeneous according to existing rate separating protocols,^20–27 we can consider one possible solution as shown in case 2 (Figure 2(c)), where the data rate of links is equivalent regardless of the used channels and NICs. In case 2, flow A-B-D traverses two high-rate (e.g. 54 Mbps) links A-B and B-D on channel 36, and flow A-C-D traverses two low-rate (e.g. 18 Mbps) links A-C and C-D on channel 64. Hence, two multihop flows over different rate links 54 Mbps and 18 Mbps do not contend on the common channels. In practice, however, channels and NICs are heterogeneous. Case 3 (Figure 2(d)) shows an example of channel and interface heterogeneity scenarios, where flow A-B-D actually traverses 54 Mbps and 36 Mbps links, and flow A-C-D traverses 12 Mbps and 18 Mbps, respectively. Thus, flow A-B-D suffers from rate anomaly since links A-B and B-D use different data rates on channel 36. Similarly, flow A-C-D also experiences rate anomaly on channel 64.

Figure 3 shows the aggregate throughput of two multihop flows in the three cases of Figure 2. The results in Figure 3 are averaged from five repeated experiments on our test bed and depicted with the 95% confidence interval. All flows are saturated UDP flows and the UDP packet size is 1500 bytes. Since IEEE 802.11a channels and NICs are actually heterogeneous as observed in Figure 1, we used homogeneous channels and NICs to obtain the aggregate throughput of case 2.

Figure 3.

Aggregate throughput of two multihop flows in each case of Figure 2.

As observed from Figure 3, the throughput by case 1 is about 16.6 Mbps. When rate separation is used and channels and NICs are assumed to be homogeneous, case 2 shows about 23.1 Mbps, which is much better than case 1. This indicates that case 1 suffers from rate anomaly. The fundamental reason of the rate anomaly is that the IEEE 802.11 medium access control (MAC) provides fair channel access opportunities among different data rate links.^2,13 By utilizing rate separation, we can mitigate rate anomaly in WMSNs as case 2. However, when rate separation is used and channel and interface heterogeneity is reflected, case 3 shows about 19.4 Mbps, which is lower than case 2. This highlights the importance of exploiting the channel and interface heterogeneity for rate separating channel assignments in WMSNs. In short, our objective is to design a novel multichannel protocol such as case 2, which effectively mitigates rate anomaly by considering the channel and interface heterogeneity in practical IEEE 802.11 WMSNs.

Heterogeneity-aware mesh

In this section, we propose a novel channel assignment protocol, HMesh, to exploit the channel and interface heterogeneity and the rate separation for rate anomaly mitigation in IEEE 802.11 multiradio multirate WMSNs. HMesh builds a tree-based architecture by utilizing a channel assignment and routing metric and a heuristic channel assignment algorithm. Both the metric and the heuristic algorithm are based on an efficient throughput estimation method. In the following, we start by describing the procedure of tree construction in the section Tree construction. Next, we discuss the throughput estimation method in the section Link capacity, and then introduce a channel assignment and routing metric in the section Heterogeneity-aware transmission time metric. Subsequently, we design the heuristic algorithm in the section Heterogeneity-aware rate separating algorithm.

Tree construction

Definitions

In HMesh, non-gateway nodes use two NIC types, one parent NIC (pNIC) and one or multiple child NICs (cNICs). Non-gateway nodes use pNIC to connect itself to its parent on the tree, and it uses cNICs to provide the Internet paths to its child nodes. Since gateways are the root of the trees, they have no parents. Hence, gateways use all NICs as cNICs for its child nodes.

To keep track of the information on neighbor nodes, each node (say node X) maintains a neighbor table. For a neighbor (say node Y), Table 1 shows a neighbor entry of neighbor table on node X, which includes the channel numbers currently used by NICs on node Y, the data rate of links X-Y and Y-X on each channel and interface pair, the address of neighbor node Y. Here, the data rate of links X-Y and Y-X for each channel and interface pair are handled individually, since they can differ due to the channel and interface heterogeneity.

Table 1.

The structure of neighbor entry in neighbor table on node X.

Fields	Descriptions
addr	The address of neighbor node Y
chan[]	Channel numbers used by neighbor node Y
dataRate[]	Link data rate to node Y per channel and interface pair

Tree advertisement

For tree construction, each node (say node X) on the tree broadcasts mesh advertisement (MA) messages every $T_p$ interval to its physical 1-hop neighbor nodes. Table 2 shows the format of MA messages, which contains the source address of MA (e.g. node X’s address), Internet accessibility (whether node X is connected to the Internet or not), the channel number and NIC IDs of cNICs, time-to-live (TTL) of 1, sequence number to discard old MAs, and the channel assignment and routing metric (see the section Heterogeneity-aware transmission time metric). Initially, only gateways broadcast the MA messages. Without modifications to the IEEE 802.11 devices, we can obtain these fields of MAs offline from the routing layer and network interface drivers. ³²

Table 2.

The structure ofMA messages.

Fields	Descriptions
srcAddr	The source address
internetAccess	Internet accessibility
chanNum[]	Channel numbers of cNICs
nicID[]	NIC IDs of cNICs
ttl	TTL value
seqNo	The sequence number
hatt	The HATT metric between node X and the gateway.

cNICs: child network interface cards; TTL: Time-to-live; HATT: heterogeneity-aware transmission time; MA: mesh advertisement.

To maintain the traffic load information on channels, nodes on the tree exchange channel traffic load (CTL) messages every $T_p$ interval with physical H-hop neighbor nodes. Here, H-hop is the ratio between interference and transmission ranges to account for the nodes within the interference range of a node. Since the H-hop value is limited, CTL messages are not flooded in a WMSN. This CTL messages carry the TTL value of H, and the traffic count (in bps) transmitted or received through the channels of all NICs during $T_p$ interval. With CTLs, parents on the tree periodically select channels with the smallest traffic count, and then assign the channels to cNICs to reflect the traffic loads on channels. This utilizes all the available channels and breaks a single collision domain into multiple collision domains in HMesh. When a parent changes its current channels of cNICs, it notifies the new channels to its child nodes and physical 1-hop neighbors via channel change (CHC) messages.

When a node (say node X) wants to send control messages to neighbor nodes (say node Y), it selects one of cNICs having the smallest traffic count. Then, it immediately switches the selected cNIC to the current channel of node Y’s pNIC using neighbor table. After sending control messages, the selected cNIC switches back to its original channel immediately.

Tree discovery

During initialization phase, new nodes that just turned on perform the tree discovery as follows to find physical 1-hop tree (or neighbor) nodes on the tree. Suppose that a new node (say node X) is just turned on and assigns the randomly selected channels to NICs. First, node X broadcasts solicitation messages on every channel by changing the channel of one of NICs. These solicitation messages include the address of node X and the channel numbers assigned to node X’s NICs. Upon receiving the solicitations, a tree node (say node Y) on the tree creates a new neighbor entry for node X and inserts it into the neighbor table. Then, node Y replies with its MA message, since it is on the tree. After receiving the MA, node X also creates a neighbor entry for node Y and inserts it into its neighbor table.

Once the tree discovery finishes, new node X performs data rate measurements for each tree node during initialization phase. Figure 4 shows the process of data rate measurements between new node X and tree node Y, where each node has three NICs. For simplicity, assume that tree node Y uses channel 1 via pNIC (NIC2), channel 2 via cNIC1 (NIC3), and channel 4 via cNIC2 (NIC1). New node X measures the data rates of link X-Y and Y-X for (i) the channels assigned to tree node Y’s cNICs and (ii) interface pairs between tree node Y’s cNICs and new node X’s all NICs. For data rate measurement, nodes X and Y exchange probe messages on each channel of tree node Y’s cNICs via each interface pair in a round robin fashion. For instance in Figure 4, new node X uses NIC1, NIC2, and NIC3 to send probe messages to node Y’s cNIC1 (e.g. NIC3) on channel 2, and it uses NIC1, NIC2, and NIC3 to send probe messages to node Y’s cNIC2 (e.g. NIC1), and so on. Here, only the new nodes change their channels and NICs for measurements, whereas tree nodes do not change their channels and NICs. This is because tree nodes have to deliver traffic loads on the tree. After this measurement, both node X and node Y update the data rate fields of the neighbor entries in their neighbor tables.

Figure 4.

Illustrations of data rate measurements.

After the initialization phase, each child node measures the data rate of links between itself and its neighbor nodes on the channels assigned to cNICs of each neighbor node per $T_p$ interval. Since the link quality in stationary WMSNs is relatively stable for long periods of time,^9,10,12 the $T_p$ interval value is set to a multiple-second time period (e.g. 20 s). This makes HMesh introduce less control overheads for data rate measurements, which will be evaluated in the section Performance with the other parameters.

Tree construction

The basic tree construction of HMesh is similar to the study by Hyacinth ³ except the metric for parent selection and the channel assignment algorithm for links on the tree. We explain the procedure of tree formation in HMesh using an example scenario shown in Figure 5, where all nodes are connected to the Internet and each node has three NICs. Solid lines are the links on the tree and dotted lines are the links not on the tree. All tree nodes broadcast the MAs periodically.

Figure 5.

The procedure of tree construction in HMesh. HMesh: heterogeneity-aware mesh.

Figure 5(a) shows an initial topology, where node X uses pNIC (NIC2) and channel 3 to join parent B. Suppose that node X received MA messages from tree nodes A, B, C, and D during $T_p$ interval as shown in Figure 5(b). Upon receiving the MAs from a tree node (e.g., node A), node X updates the neighbor entry for node A in its neighbor table. Then, node X decides whether to join node A or not. If node X is not connected to the Internet via the tree or finds that the Internet path via node A is better than its existing Internet path using the channel assignment and routing metric (see the section Heterogeneity-aware transmission time metric), called HATT, then node X sends a join request (JREQ) message to node A as shown in step (1) of Figure 5(c). This JREQ message carries the address of node X, the “add” status, the link data rates for channels of node A’s cNICs and interface pairs between node A’s cNICs and node X’s NICs. When node X has its child nodes, JREQ also contains the address of the child nodes. If multiple gateways are available, nodes select one of the gateways using the HATT metric.

Once parent A receives the JREQ, it runs the heuristic channel assignment algorithm, called HRS algorithm as shown in step (2) of Figure 5(c), to separate child links that may use different data rates between parent A and its child nodes via multiple cNICs (see the section Heterogeneity-aware rate separating algorithm). The HRS algorithm decides the final channel number and interface pair for node X (e.g., channel 4 and NIC3). Then, parent A inserts a routing entry for node X into the routing table. Here, the routing entry includes the next-hop address, the destination address, the HATT metric, and NIC ID. After that, parent A replies with a join reply (JREP) message to child node X (step (3) of Figure 5(c)). This JREP carries the address of parent A and the decided channel number and NIC ID for node X. In addition, node A notifies the HRS algorithm result to its other child nodes via CHC messages. Subsequently, node X inserts a routing entry for parent A, and it uses channel 4 via NIC3 in the JREP. This means that child nodes select pNIC out of NICs according to the decision made by its parent. In this way, HMesh exploits interface heterogeneity. Figure 5(d) shows the tree construction result, where node X is a child of parent A.

In case that node X changes its parent, it also sends a JREQ with the “delete” status to the old parent (e.g., node B) as shown in step (4) of Figure 5(c). Then, node B removes the old child node X from its routing table. Also, it reruns the HRS algorithm and informs the result to its child nodes via CHC messages as shown in steps (5)–(6) of Figure 5(c), since the child link for node X is removed. Next, node B forwards the received JREQ to its ancestor nodes along the path to the gateway. Likewise, the ancestor nodes remove node X from their routing tables. At the same time, the parent A of the new child node X forwards the JREQ with the “add” status to its ancestor nodes on the path to the gateway. Then, the ancestor nodes insert a routing entry for the new child node X and node X’s child nodes into their routing tables.

Link capacity

One of research goals in HMesh is mitigating rate anomaly in multirate WMSNs. To realize this goal, we discuss an efficient throughput estimation method, called link capacity,^27,33 which reflects the degree of rate anomaly. HMesh constructs the tree-based architecture using the HATT metric and the HRS algorithm, which are based on the link capacity. In this subsection, we explain the link capacity.

When N nodes contend on the common channel using carrier sense multiple access with collision advance such as IEEE 802.11 with RTS/CTS (Request to Send/Clear to Send) mechanism and each node always has a frame to be transmitted (i.e., saturated condition), the average throughput $x_i$ for node i (or link i) can be expressed as ³⁴ :

$$x_i=\frac{\tau {(1-\tau )}^{N-1}{L}_i}{N·\tau ·{(1-\tau )}^{N-1}·T^{\mathrm{succ}}+P^{\mathrm{col}}·T^{\mathrm{col}}+P^{\mathrm{idl}}·T^{\mathrm{idl}}},$$ (1)

where $\tau$ is the probability that a node transmits through link i in a slot time, $L_i$ is the data frame size via link i, Also, $P^{\mathrm{col}}$ and $P^{\mathrm{idl}}$ are respectively the probabilities of a collision and an idle slot time, and $T^{\mathrm{col}}$ and $T^{\mathrm{idl}}$ are respectively the time durations of a collision and an idle slot time. When N links use different data rates, $N·T^{\mathrm{succ}}$ in equation (1) can be approximated as follows ³³ :

$$N·T^{\mathrm{succ}}=\sum _{j=1}^N(\frac{L_j}{r_j}+O_v),$$ (2)

where $r_i$ is the data rate of link i, and $O_v$ is the physical layer (PHY) and MAC layer overheads for a packet transmission. In the case of 802.11 networks with RTS/CTS mechanism, the collision time interval ( $T^{\mathrm{col}}$ ) depends on RTS frames sent at the basic rate (e.g., 6 Mbps in IEEE 802.11a). This means that different data rates do not affect the $T^{\mathrm{col}}$ value. In the case of 802.11 networks without RTS/CTS exchange, the $T^{\mathrm{col}}$ value is influenced by different data rates. When some protocols can be utilized to reduce collisions such as in Cali et al., ³⁵ $T^{\mathrm{col}}$ becomes a small value compared to other values in the denominator of equation (1). Hence, we can derive the average throughput $x_i$ for link i as follows:^36–37

$$x_i=\frac{\tau {(1-\tau )}^{N-1}{L}_i}{\tau {(1-\tau )}^{N-1}\sum _{j=1}^N(\frac{L_j}{r_j}+O_v)+P^{\mathrm{col}}{T}^{\mathrm{col}}+P^{\mathrm{idl}}{T}^{\mathrm{idl}}}$$ (3)

From equation (3), for the IEEE 802.11 network with or without RTS/CTS mechanism, an upper bound throughput $X_i$ for link i can be expressed as:^27,33

$$X_i=\frac{1}{\sum _{j\in S_L\left(i\right)}\frac{1}{r_j}},$$ (4)

where $S_L\left(i\right)$ is a set of links that interferes with link i, and link i is also included in $S_L\left(i\right)$ . From equation (4), the upper bound throughput is equivalent for all the links in $S_L\left(i\right)$ independent of their link data rates. We call the upper bound throughput $X_i$ as link capacity for the rest of this article. Clearly, $X_i$ does not provide the accurate throughput estimation since it does not reflect contention window size, backoff stages, and collision probabilities. However, we can use the link capacity $X_i$ to capture the degree of rate anomaly, since the $X_i$ value degrades more significantly as the data rate difference between high-rate links and low-rate links increases. For instance, if a high-rate link with 48 Mbps and a low-rate link with 36 Mbps contend on the common channel, the link capacity of the high-rate link is 20.6 Mbps according to equation (4). However, if a high-rate link with 48 Mbps and a low-rate link with 9 Mbps use the common channel, the link capacity of the high-rate link is 7.6 Mbps, which is much less than 20.6 Mbps. The accuracy of the link capacity $X_i$ in equation (4) is evaluated using real test bed experiments in. ²⁷ For more details, please refer to the literature by Lin and Chou, Genetzakis and Siris, Bianchi, Kumar et al., and Siris and Courcoubetis.^{27,33,34,36,37}

Heterogeneity-aware transmission time metric

Using link capacity, we design the HATT metric for channel assignment and routing in HMesh. Recall that HMesh uses the HATT metric to select parents on the tree (see the section titled “Tree construction” and Figure 5) such that child nodes assign channels to links between themselves and parents and route data traffic over the links. The HATT metric is derived from the contention aware transmission time (CATT) metric in the study by Genetzakis and Siris, ³³ which is extended from the link capacity in equation (4).

When a node transmits a frame with the size of $L_i$ bytes over link i with the link capacity $X_i$ , the approximated transmission time of link i can be written as $L_i/X_i$ . Then, the CATT metric ( $\mathrm{CAT}{T}_i$ ) for link i is given by: ³³

$$\mathrm{CAT}{T}_i=\frac{L_i}{X_i}=\sum _{j\in S_L\left(i\right)}\frac{L_j}{r_j},$$ (5)

where $S_L\left(i\right)$ is a set of links interfering with link i, and $S_L\left(i\right)$ also includes in link i. Then, the CATT metric for a multihop path P is the sum of $\mathrm{CAT}{T}_i$ values of all links on P as follows:

$$\mathrm{CAT}{T}_P=\sum _{i\in P}\mathrm{CAT}{T}_i.$$ (6)

Since the CATT metric indicates the approximated transmission time of paths, a path with the smallest CATT value is selected. According to Genetzakis and Siris, ³³ the CATT metric reflects both intrapath interference and interpath interference in WMSNs because it takes the transmission time of all links into consideration, which interfere with the links on the paths.

We extend the CATT metric for channel assignment and routing in HMesh. Figure 6 shows an example topology, where each node has three NICs. Parent X uses one pNIC (NIC2) and two cNICs (NIC1-channel 2 and NIC3-channel 1), and parent Y uses one pNIC (NIC3) and two cNICs (NIC1-channel 3 and NIC2-channel 4). Supposing that child Z selects one of two parents X and Y, child Z can use one of three NICs (i.e. NIC1, NIC2, and NIC3) for its parent. For simplicity, we define link (X, Z) that indicates both link X–Z from node X to node Z and link Z–X from node Z to node X. Owing to channel and interface heterogeneity, the data rate of a link (e.g. link (X, Z) or link (Y, Z)) can be different depending on the selection of actual interface pairs. Also, link X–Z and link Z–X (or link Y–Z and link Z–Y) may differ in data rates and the CATT values.

Figure 6.

HATT metric for channel assignment and routing. HATT: heterogeneity-aware transmission time.

Design of HATT. Consider parent X and child Z in Figure 6. Since there may be a large number of interface pairs between parent X and child Z, we design that only child Z changes its channels and NICs, while parent X does not change its NICs or channels. This is because we assume that parent nodes have higher priority than child nodes. For this design choice, child Z selects the best NIC out of NICs for its pNIC. Here, the best NIC is defined as a NIC of child Z, which provides the smallest link HATT metric value, $\mathrm{HAT}{T}_L$ . When parent X uses NICp and child Z uses NICq, they form link (X, Z) with interface pair $(p,q)$ . Then, child X receives downlink flows from the Internet over link X–Z, while child Z sends uplink flows to the Internet over link Z-X. Since both link X-Z and link Z-X are used on the tree, we define the link HATT metric ( $\mathrm{HAT}{T}_L$ ) as follows:

$$\mathrm{HAT}{T}_L(X,Z,p,q)={\mathrm{CATT}}_{X-Z}^{p,q}+{\mathrm{CATT}}_{Z-X}^{p,q},$$ (7)

where ${\mathrm{CATT}}_{X-Z}^{p,q}$ and ${\mathrm{CATT}}_{Z-X}^{p,q}$ are the CATT values of link X-Z and link Z-X for interface pair $(p,q)$ . If ${\mathrm{CATT}}_{X-Z}^{1,3}$ is 20 and ${\mathrm{CATT}}_{Z-X}^{1,3}$ is 30, then $\mathrm{HAT}{T}_L(X,Z,1,3)$ is 50. Suppose that $\mathrm{HAT}{T}_L(X,Z,1,1)$ , $\mathrm{HAT}{T}_L(X,Z,1,2)$ , $\mathrm{HAT}{T}_L(X,Z,1,3)$ are 50, 40, and 30, respectively. Then, child Z selects NIC3 as its “best NIC” for NIC1 of parent X, since interface pair (1, 3) has the smallest $\mathrm{HAT}{T}_L$ value. That is, child Z uses NIC3 as its pNIC for parent X when it joins parent X’s NIC1 (i.e. cNIC).

Since parent X may have multiple cNICs for child Z, we define the averaged link HATT metric ( $\mathrm{HAT}{T}_A$ ) for link (X, Z) as follows:

$$\mathrm{HAT}{T}_A(X,Z)=\frac{1}{\left|S_{C,X}\right|}·\sum _{p\in S_{C,X}}\mathrm{HAT}{T}_L(X,Z,p,q),$$ (8)

where $S_{C,X}$ is the set of cNICs on parent X, and $\left|S_{C,X}\right|$ is the number of cNICs on parent X. Specifically, the $\mathrm{HAT}{T}_A(X,Z)$ value represents the average CATT values of possible links between parent X and child Z on the channels assigned to parent X’s cNICs.

HATT definition

Consider that a multihop path $P_{G-Z}$ between gateway G and child Z, which consists of path $P_{G-X}$ between gateway G and parent X and link (X, Z). When child Z selects node X as its parent, the HATT metric of path $P_{G-Z}$ is defined as follows:

$$\mathrm{HAT}{T}_{P_{G-Z}}=\mathrm{HAT}{T}_A(X,Z)+\sum _{i\in P_{G-X}}\mathrm{CAT}{T}_i.$$ (9)

Child Z calculates the HATT metric value of path $P_{G-Z}$ in equation (9) using its neighbor table after it receives the MA message from parent X. When a new node joins the tree, it first selects its parent node among multiple available parent nodes. Then, it determines its interface and channel. With the HATT metric in equation (9), child Z first selects one of parents on the tree by considering interface pairs between itself and a candidate parent (e.g. node X or node Y).

After child Z selected node X as its parent, it sends a JREQ to parent X, and parent X that received the JREQ performs the HRS algorithm (see the section Heterogeneity-aware rate separating algorithm) to determine the final channel number and interface pair $(p,q)$ for link (X, Z). Once it is determined, child Z assigns a channel to the selected NIC for link (X, Z) and updates its HATT metric of path $P_{G-Z}$ in routing table as follows:

$$\mathrm{HAT}{T}_{P_{G-Z}}=\sum _{i\in P_{G-Z}}\mathrm{CAT}{T}_i$$ (10)

Actually, the HATT metric in equation (10) is equivalent with the CATT metric in equation (6). However, when child Z selects one of parents X and Y, it uses the HATT metric in equation (9). After the channel and interface assignment for link (X, Z), child Z uses the HATT metric in equation (10).

HATT calculation

To get the data rate of links and the number of links in $S_L\left(i\right)$ of equation (5) locally, each node (say node X) on the tree should obtain the information on the interfering links of link i. However, node X cannot obtain the information without the support of intermediate nodes, since the interfering links are located outside of the transmission range of node X. Thus, nodes exchange rate vector (RV) periodically. When node X uses channel k via its NICs, RV (u_X^k) is given by:

$$u_X^k={[a_1^k,a_2^k,\dots ,a_R^k]}^T,$$ (11)

where $a_i^k$ is the number of links that use data rate $r_i$ on channel k, and R is the total number of data rates (e.g. $R=8$ in IEEE 802.11a). At the beginning, every entry in a RV is set to zero. Node X piggybacks the RVs into the CTL messages (see the section Tree construction) to exchange it with H-hop neighbor nodes. Once a neighbor node (say node Y) receives the CTLs, it decrements the TTL value of the CTLs by one and rebroadcasts the CTLs as long as its TTL value is not zero. Then, node Y updates a channel rate vector (CRV) per channel. For channel k, node Y maintains CRV ( $v_Y^k$ ) as follows:

$$v_Y^k={[n_1^k,n_2^k,\dots ,n_R^k]}^T,$$ (12)

where $n_i^k$ is the number of links that use data rate $r_i$ on channel k. With CRVs, node X obtains the information on interfering links in $S_L\left(i\right)$ of equation (5). After calculating the HATT metric of path between the gateway and node X, node X broadcasts the periodic MA messages to physical 1-hop neighbor nodes (see Table 2 and the section Tree construction). This MA sent by node X includes the calculated HATT metric for a multihop path between the gateway and node X. In this manner, the HATT calculation is distributed.

Discussion

Since the HATT metric is extended from the CATT metric, it captures the intrapath interference of links on the same path and the interpath interference among paths. Moreover, it takes the interface heterogeneity into account since the interface pairs are reflected via $\mathrm{HAT}{T}_A$ in equations (8) and (9). In past works, various routing metrics are proposed.^5,38–39 In those works, the channel assignment is out of scope. That is, they assume a proper channel assignment and then focus on the route selection to select better multihop paths. Once the channel assignment is finished, we can perform periodic link quality measurements such as expected transmission count ³⁸ and select optimal paths. On the contrary, it is difficult to measure the link quality or traffic loads as in the study by Iqbal et al., Couto et al., and Liu and Liao^5,38,39 when no channels are assigned to links. The key reason mainly stems from the tight dependency between channel assignment and routing. ³⁹ Therefore, the HATT metric cannot reflect the link quality, traffic loads, and so on. Reflecting those factors is left as our future work. As an alternative approach, we utilize the HATT metric to determine channels, interface pairs, and routing paths at the same time. This makes our work differ from the past works on designing routing metrics in WMSNs.

Heterogeneity-aware rate separating algorithm

In this subsection, we design the heuristic channel assignment algorithm, HRS algorithm, to separate different rate child links between a parent and its child nodes so that rate anomaly is mitigated. Parents on the tree use the HRS algorithm that utilizes the rate efficiency function (REF) metric for rate separation by considering the channel and interface heterogeneity. In the following, we start by designing the REF metric.

Design of REF

Figure 7 shows an example topology, where a parent X has four child nodes A, B, C, and D. Each node is equipped with three NICs. Parent X uses one pNIC (NIC2) and two cNICs (NIC3-channel 4 and NIC1-channel 5). Suppose that parent X performs channel assignments for four child links. When parent X uses NICp and child A uses NICq as its best NIC (see the section Heterogeneity-aware transmission time metric), they form a link (X, A) with interface pair $(p,q)$ . Since both link X-A and link A-X should be used on the tree, we define the average rate for link (X, A), ${\mathrm{AR}}_{X,A}^{p,q}$ , using the link capacity in equation (4) as follows:

$${\mathrm{AR}}_{X,A}^{p,q}=\frac{1}{{r_{X-A}^{p,q}}^{-1}+{r_{A-X}^{p,q}}^{-1}},$$ (13)

where $r_{X-A}^{p,q}$ and $r_{X-A}^{p,q}$ are the data rates of link X-A and A-X, respectively for interface pair ( $p,q)$ . For example, when $r_{X-A}^{p,q}$ = 54 Mbps and $r_{X-A}^{p,q}$ = 36 Mbps, the average rate of link (X,A) is 21.6 Mbps.

Figure 7.

An example scenario of parent node X and its four child links.

Table 3 shows an example of average rate of each link in Figure 7 for two channels (e.g. channels 5 and 4) or cNICs (e.g. NIC1 and NIC3) of parent X. In Table 3, the maximum average rate of each link is colored with gray, where the maximum average rate is the largest average rate among the average rates of a link for the channels assigned to parent X’s cNICs. Owing to the channel and interface heterogeneity, the average rate of a link may differ for each channel (or cNIC). For instance, the average rate of link (X, B) differs for two channels between 18 Mbps and 36 Mbps. Among the average rates, the maximum average rate of link (X, B) is 36 Mbps, when link (X, B) uses channel 4 assigned to NIC3 of parent X. In Table 3, four links can use their maximum average rates on different channels. For example, two links (X, A) and (X, C) can use the maximum average rates (54 Mbps and 36 Mbps) on channel 5 (NIC1) of parent X, whereas two links (X, B) and (X, D) can use the maximum average rates (36 Mbps and 54 Mbps) on channel 4 (NIC3) of parent X. To assign channels for four child links, the HRS algorithm utilizes the following REF metric.

Table 3.

An example of data rate per channel for five links in Figure 6.

Channel and NIC of parent X	Link (X, A)	Link (X, B)	Link (X, C)	Link (X, D)
Ch 5, NIC1	54M	18M	36M	48M
Ch 4, NIC3	24M	36M	12M	54M

NIC: network interface card.

Definition of REF

In Table 3, suppose that parent X selects channel 4 (or NIC3) first. Then, the average rate of link (X, B) is its maximum average rate 36 Mbps while the average rate of link (X, A) is 24 Mbps lower than its maximum rate 54 Mbps on channel 5 (or NIC1) of parent X. That is, depending on the channel selection, some child links use their maximum average rates while the other child links use lower average rates than their maximum average rates. Therefore, in order to select channels (or NICs), we define the rate efficiency (RE) metric for link i on channel k as follows:

$${\mathrm{RE}}_i^k=\frac{{\mathrm{ar}}_i^k}{\underset{k\in S_{K,X}}{max}\left({\mathrm{ar}}_i^k\right)},$$ (14)

where ${\mathrm{ar}}_i^k$ is the average rate of link i on channel k, $S_{K,X}$ is a set of channels assigned to cNICs of parent X. Based on equation (14), in Table 3, the RE of link (X, A) on channel 4 is $24\mathrm{Mbps}/54\mathrm{Mbps}=0.44$ . Hence, the performance of each link can be improved by increasing the RE value of links.

To improve the network performance, the RE values of every link should be increased. Moreover, we should address a trade-off between the network throughput and the throughput fairness of links, since the trade-off depends on the channel and interface selection. If we increase the network throughput only, some high average rate links get high throughputs while the other low average rate links get low throughputs. In contrast, if we increase the throughput fairness of links only, some high average rate links may experience low throughputs due to rate anomaly by low average rate links. Therefore, we define the REF metric for channel k as follows:

$$\mathrm{RE}{F}_k=X_{S_L,k}·F_{\mathrm{RE},k}=\frac{1}{\sum _{j\in S_{L,k}}\frac{1}{r_j^k}}·F_{\mathrm{RE},k},$$ (15)

where $S_{L,k}$ is a set of contending links on channel k, $X_{S_L,k}$ is the link capacity in equation (4) on channel k, which is the same for all links in $S_{L,k}$ , and $F_{\mathrm{RE},k}$ is the Jain’s fairness index ⁴⁰ to measure the fairness of RE values, which is extended as follows:

$$F_{\mathrm{RE},k}={\left(\sum _{i\in S_{L,k}}{\mathrm{RE}}_i^k\right)}^2/(N_{L,k}·\sum _{i\in S_{L,k}}{\left({\mathrm{RE}}_i^k\right)}^2),$$ (16)

where $N_{L,k}$ is the total number of links in $S_{L,k}$ . In equation (16), the $F_{\mathrm{RE},k}$ value goes to zero, if the RE values of links are biased on some links, while $F_{\mathrm{RE},k}$ value approaches to one when each link has comparable RE values. In equation (15), the REF metric value increases as $X_{S_{L,k}}$ value increases (i.e. the degree of rate anomaly decreases) or the fairness of RE values of links increases. Using the REF metric in equation (16), parent X selects a channel (or cNIC) with the maximum REF values among available channels (or cNICs), which provides high throughput and throughput fairness of links. In Table 4, the REF metric value for each channel and NIC of parent X in Table 3 is calculated using equation (15). From Table 4, parent X first selects channel 5 with the maximum REF value (i.e. 7.69 Mbps) among two channels (or two cNICs).

Table 4.

The average rate per channel (or NIC) for four links in Figure 8(a).

Ch and NIC of parent X	Link (X,A)	Link (X,B)	Link (X,C)	Link (X,D)	REF
Ch 5, NIC1	54M	18M	36M	48M	7.69M
Ch 4, NIC3	24M	36M	12M	54M	4.87M

NIC: network interface card; REF: rate efficiency function.

Design goals of HRS algorithm

Assigning channels of links in multichannel WMSNs can be considered as one variation of the graph coloring, which is known to be NP-hard. ⁸ Hence, we design an efficient HRS algorithm with low complexity. The design goal of the HRS algorithm is to exploit the channel and interface heterogeneity for separating high-rate links from low-rate links for rate anomaly mitigation. To achieve this goal, the HRS algorithm utilizes the REF metric.

Rate separation of HRS algorithm

To help understanding, assume that parent X selects channel 5 from Table 4, which is assigned to its NIC1. There are four child links with different average rates on channel 5. When the four links contend on the same channel 5, high-rate links such as link (X, A) with 54 Mbps definitely experience rate anomaly due to low-rate links such as link (X, B) with 18 Mbps. Since parent X has multiple cNICs, it can separate high-rate links and low-rate links over its cNICs (or channels). To separate different rate links, parent X calculates the basis average rate ( $A{R}_{b,k}$ ) as follows, which is similar to DR-CA ²¹ with a different channel assignment scheme:

$$A{R}_{b,k}=\frac{1}{\left|S_{C,X}\right|}·\sum _{i=1}^{N_{L,k}}{\mathrm{ar}}_i^k,$$ (17)

where $\left|S_{C,X}\right|$ is the number of cNICs on parent X, $N_{L,k}$ is the number of child links under parent X on channel k. For example in Table 4, $A{R}_{b,5}=\left(1/2\right)\times (54\mathrm{M}+18\mathrm{M}+36\mathrm{M}+48\mathrm{M})$ is 78 Mbps for four links on channel 5 assigned to NIC1 of parent X.

Using $A{R}_{b,k}$ , the HRS algorithm performed by parent X separates different rate links over multiple cNICs (or channels). Figure 8(a) and (b) show an example of this rate separation based on Tables 4 and 5, respectively. First, the HRS algorithm sorts the links on channel k in decreasing order of average rates and computes $A{R}_{b,k}$ in equation (17). Next, it assigns links from high average rates to low average rates to each cNIC as long as the average rate sum of links assigned to the current cNIC is smaller than the $A{R}_{b,k}$ value. For instance, the HRS algorithm assigns the highest average rate link (X, A) to the current cNIC (i.e. NIC1) configured with channel 5. Here, channel 5 (or NIC1) with the maximum REF metric is selected first. Since the average rate of link (X, A) is 54 Mbps and it is smaller than $A{R}_{b,5}$ = 78 Mbps, the HRS algorithm also assigns the next highest average rate link (X, D) to the current cNIC (channel 5) as shown in Figure 8(a). At this point, the average rate sum of links assigned to the current cNIC (i.e. 54M + 48M = 102 Mbps) is larger than $A{R}_{b,5}$ = 78 Mbps. Thus, the dynamic rate switching (DRS) algorithm moves to the next cNIC (i.e. NIC3 in Table 4), then it repeats the same rate separation process until all the child links are assigned. That is, the HRS algorithm repeats: (i) the REF calculation, (ii) the channel (or cNIC) selection with the maximum REF value, (iii) the basis average rate calculation, and (iv) the rate separation of the remaining child links under the parent node such as two links (X, B) and (X, C) for the channels assigned to the remaining cNICs (e.g. NIC3). Figure 8(b) shows the final result of the HRS algorithm, where links (X, B) and (X, C) are assigned to NIC3 (channel 4). In this way, the HRS algorithm performs rate separation by considering the channel and interface heterogeneity with rate anomaly mitigation.

Figure 8.

Rate separation of four child links in Figure 7 by the HRS algorithm. HRS: heterogeneity-aware rate separating.

Table 5.

The average rate per channel (or NIC) for four links in Figure 8(b).

Ch and NIC of parent X	Link (X,B)	Link (X,C)	REF
Ch 5, NIC1 (selected)	18M	36M	—
Ch 4, NIC3	36M	12M	3.60M

NIC: network interface card; REF: rate efficiency function.

Pseudo-code of HRS algorithm

Overall, Algorithm 1 shows the pseudo-code of the HRS algorithm. Recall that the key idea of the HRS algorithm is to exploit the channel and interface heterogeneity for rate anomaly mitigation by utilizing the REF metric. A parent (say node X) runs this algorithm, whenever it adds or removes its child nodes or changes its channels of cNICs after $T_p$ interval (see Figure 5). At first, all variables are initialized in line 1. Then, parent X gets the information on all the child links. Next, parent X performs the main part of the HRS algorithm in lines 3–14. Until all child links are assigned with one of cNICs on parent X, the DRS algorithm calculates the REF value per channel for all the unassigned child links. Then, channel k (or cNIC c) with the maximum REF value is selected (lines 4–6). After that, all the unassigned child links are sorted in decreasing order of their average rates on channel k. In line 8, the HRS algorithm calculates the basis average rate $A{R}_{b,k}$ of the sorted child links on channel k according to (17). In lines 10–13, the HRS algorithm assigns each unassigned child link to channel k until the average rate sum of links assigned to channel k (or cNIC c) is greater than the calculated $A{R}_{b,k}$ value. This process repeats until all child links are assigned to one of cNICs on parent X.

Algorithm 1. Heterogeneity-aware Rate Separating (HRS) Algorithm

0: HRS_Algorithm (neighbor table, CRVs) {

1: max_ref_ch = max_ref_cnic = basis_avg_rate = sum_rate = null;

2: Get the required information on the child links;

3: while there is unassigned child links do {

4: Calculate the REF value per channel for unassigned child links;

/* Get a channel (or cNIC) with maximum REF value based on (15) */

5: max_ref_ch = get_ max_ref_ch(neighbor table, CRVs);

6: max_ref_cnic = get_max_ref_cnic(neighbor table, CRVs);

7: Sort links in decreasing order of average rates on channel max_ref_ch;

/* Get the basis data rate based on (17) */

8: basis_avg_rate = get_basis_avg_rate (max_ref_ch, neighbor table);

9: sum_rate = 0;

/* Rate separating process */

10: while (sum_rate < basis_avg_rate) do {

11: Assign current link i to the cNIC (max_ref_cnic);

12: sum_rate += the average rate of link i;

13: }

14: } /* End of while */

15: } /* End of HRS algorithm */

Complexity

First, the HRS algorithm iterates $N_L$ child links to calculate the REF metric value for $\left|S_{C,X}\right|$ channels assigned to $\left|S_{C,X}\right|$ cNICs on parent X. This takes $O(N_L·\left|S_{C,X}\right|)$ . Second, the sorting of child links in decreasing order of average rates takes $O(N_L·\log N_L)$ , if an efficient well-known sort algorithm is used (e.g. quick sort). Third, the rate separating process in lines 10–13 of the HRS algorithm takes $O\left(N_L\right)$ . These three parts repeat for $\left|S_{C,X}\right|$ cNICs (or $\left|S_{C,X}\right|$ channels). Hence, the overall complexity of this algorithm is $O(\left|S_{C,X}\right|·N_L·\log N_L)$ . In general, the number of cNICs ( $\left|S_{C,X}\right|$ ) is generally smaller than the number of links ( $N_L$ ) that belong to a parent on the tree. Therefore, we conclude that the complexity is $O(N_L·\log N_L)$ .

Simulation results

We evaluate the performance of HMesh using ns-2 simulations. ⁴¹ We also compare HMesh with Hyacinth, ³ ROMA, ⁴ and CoCA, ²⁵ since they are based on the tree architecture, and CoCA and ROMA are the recently proposed channel assignment protocols for 802.11 networks. For each simulation result, we generated 30 different scenarios. Each scenario consists of one gateway and a varying number of nodes. All nodes are randomly placed in a 1000 m × 1000 m area. Each node is equipped with from two to four IEEE 802.11 NICs with default 802.11a parameters. Nodes can use 12 nonoverlapping channels and from 6 Mbps to 54 Mbps link data rates. The RTS/CTS exchange is enabled, and the ratio propagation is modeled using the two-ray ground propagation model. The transmission range and interference range of NICs are set to 250 m and 550 m, respectively. Parameter H-hop, the ratio between interference range and transmission range, is approximately set to 2-hop (see sections Tree construction and Heterogeneity-aware transmission time metric). The simulation time is 300 s. Through empirical simulations in the section Performance with the other parameters, the periodic $T_p$ interval is set to 20 s. The simulation parameters are listed in Table 6.

Table 6.

Parameters for performance evaluation in simulations.

Parameters	Values
PHY and MAC	IEEE 802.11a
No. of non-gateway nodes	5, 10, 15, 20, 25, and 30 (default)
No. of interfaces	2, 3 (default), and 4
No. of channels	6, 9, and 12 (default) nonoverlapping channels
No. of gateways	1 (default), 2, and 3
Link data rates	6, 9, 12, 18, 24, 36, 48, and 54 Mbps
Simulation time	300 s
Ranges	Transmission (250 m) and interference (550 m)
$T_p$ interval	20 (default), 40, 60, 80, 100, and 120 s
H-hop	2-hop
Traffic	UDP and TCP with packet size of 1000 bytes

MAC: medium access control, PHY: physical layer.

We used UDP flows and transmission control protocol (TCP) flows. In each UDP flow, the traffic rate differs depending on the scenario, and the packet size is 1000 bytes. In each TCP flow, the traffic rate is set by TCP Reno and the packet size is 1000 bytes. We use two flows types in WMSNs, ⁹ external flow and internal flow. For each external flow, we randomly selected two nodes for the source and destination nodes, and one of them acts as the gateway. For each internal flow, we randomly selected two non-gateway nodes for the source and destination nodes. The total number of flows generated in a scenario is equal to the number of nodes, and the number of external flows is the same as that of internal flows. For instance, if a scenario includes 20 nodes, 10 external flows and 10 internal flows are generated in the scenario.

For our evaluation, we used the following performance metrics: (i) aggregate throughput—the total sum of packets (in bps) received by all the destination nodes in each scenario; (ii) end-to-end delay (E2E delay)—the time difference between the time the source node sends a packet and the time the destination receives the packet; (iii) round-trip-time (RTT)—the difference between the time the source node sends a TCP packet and the time it receives the acknowledgment of the TCP packet; and (iv) throughput fairness index ( $F_{\mathrm{TH}}$ )—the extended Jain’s fairness index to measure the fairness of throughputs of multihop flows, given by:

$$F_{\mathrm{TH}}=\frac{{(\sum T{H}_f)}^2}{(N_F·\sum {\left(T{H}_f\right)}^2)},$$ (18)

where $T{H}_f$ is the average throughput of flow f and $N_F$ is the total number of multihop flows generated in a scenario. In each scenario, we averaged E2E delay and RTT metric values over all the generated flows.

We simulate the channel and interface heterogeneity as follows. Consider a link (say link (X, Y)) between two nodes (say nodes X and Y). For link X-Y from node X to node Y, we randomly selected a link data rate between basic rate (i.e. 6 Mbps in IEEE 802.11a) and the maximum rate of links for each channel and interface pair, where the maximum rate of links is the maximum data rate of links for all channels and interface pairs. For instance, when node X can use up to 36 Mbps to send packets to node Y for all channels and interface pairs, 36 Mbps is the maximum rate of link X-Y. Then, we randomly selected a data rate of link X-Y between 6 Mbps and 36 Mbps for each channel and interface pair. Likewise, we also selected the link data rate of link Y-X for each channel and interface pair. The reason for this data rate selection is that the link quality of a link is not correlated with the operating channels and interfaces in general ¹⁰ (see the section Motivation 1: Channel and interface heterogeneity). These selected link data rates are commonly used by Hyacinth, ROMA, CoCA, and HMesh. Since CoCA, ROMA, and Hyacinth assumed homogeneous channels and NICs, they use the link data rates measured on the default channel (e.g. channel 1) for channel assignments. For the maximum rate of links, we configured the distance ranges based on Cisco Aironet 802.11a card data sheet. ⁴²

Performance using UDP and TCP flows

Figure 9 shows the aggregate throughput and E2E delay by increasing the traffic rate per UDP flow, which is taken from 30 distinct scenarios. Each scenario consists of one gateway and 30 non-gateway nodes. Every node has three NICs, and 30 UDP flows are generated. From Figure 9, we can observe that HMesh shows much improved performance compared to the other protocols with UDP flows. For example, when the traffic rate per flow is 1 Mbps, the aggregate throughput by HMesh is about 11.8%, 20.3%, and 32.5% higher than CoCA, ROMA, and Hyacinth, respectively.

Figure 9.

UDP performance as the traffic rate per UDP flow increase.

Figure 10 shows the aggregate throughput and RTT by varying the number of nodes, which is obtained from 30 different scenarios. Each scenario includes one gateway, a varying number of nodes and TCP flows. Each node is equipped with three NICs. As seen from Figure 10, HMesh also shows better performance than the other protocols with TCP flows. For instance, when the number of nodes is 30, the aggregate throughput by HMesh is about 15.9%, 30.5%, and 47.2% better than CoCA, ROMA, and Hyacinth, respectively.

Figure 10.

TCP performance with different number of nodes.

The improved performance by HMesh can be explained as follows. ROMA shows better performance than Hyacinth, since it eliminates the intrapath interference and reduces interpath interference. Compared to ROMA, CoCA and HMesh achieve higher performance, because they perform rate separation to mitigate rate anomaly on the tree architecture. However, CoCA assumes that all channels are homogeneous, and thus it is not aware of the link data rates on each channel and interface pair. This severely reduces the effect of rate separation by CoCA. In contrast, HMesh utilizes the HATT metric and the HRS algorithm for effective rate separation by exploiting both channel heterogeneity and interface heterogeneity in WMSNs, which leads to higher performance than CoCA. Therefore, HMesh shows the improved performance than CoCA, ROMA, and Hyacinth.

Fairness of multihop flows

We evaluate the throughput fairness of multihop flows using $F_{\mathrm{TH}}$ in equation (18). Figure 11 shows the $F_{\mathrm{TH}}$ performance when the traffic rate per UDP flow increases. The results in Figure 11 are averaged from 30 distinct scenarios, and each scenario consists of one gateway, 30 non-gateway nodes, and 30 UDP flows. Every node is equipped with three NICs. As observed from Figure 11, HMesh shows higher throughput fairness of multihop flows than CoCA, ROMA, and Hyacinth. For instance, when traffic rate per UDP flow is 1 Mbps, the $F_{\mathrm{TH}}$ performance obtained by HMesh is about 6.1%, 11.2%, and 16.8% better than CoCA, ROMA, and Hyacinth, respectively.

Figure 11.

The fairness of multihop flows as the traffic rate per UDP flow increases.

In tree-based architecture, leaf nodes located far from the gateways typically suffer from low performance. Moreover, gateways and nodes near the gateways usually play a role of bottleneck on the tree-based architecture. To overcome the bottleneck, ROMA assigns different channels to links on the same path and different channel sequences to different paths associated with different gateways. However, ROMA still experiences rate anomaly due to different data rate links on the tree. Although CoCA attempts to separate different data rate links, it may not able to reflect heterogeneous channels for rate anomaly mitigation. In contrast, HMesh separates different data rate links effectively using the HATT metric and the HRS algorithm. This overcomes the bottleneck of links on the tree and provides better performance to leaf nodes. As a result, HMesh shows the best throughput fairness performance.

The number of interfering links in HMesh

For HMesh, we measured the number of interfering links which is in $S_{L,k}$ of equation (15) and located outside of the transmission range of each parent on the tree, since those links may affect the accuracy of link capacity in equation (4). Figure 12 shows the average number of interfering links per parent node. The results in Figure 12 are taken from 30 different scenarios. In each scenario, there are 1 gateway and 30 non-gateways. Totally 30 UDP flows are generated and each flow has the traffic rate of 1 Mbps.

Figure 12.

The number of interfering links on the tree in HMesh. HMesh: heterogeneity-aware mesh.

As the number of nodes increases, it is clear that the number of interfering links increases. From Figure 12, we can see that the number of interfering links per parent node is not so significant in HMesh. For instance, when the number of nodes is 30 in a 1000 m × 1000 m area, which can be considered as a moderate node density in wireless netwoks, ⁴³ the number of interfering links is less than two links. The main reason is that HMesh effectively breaks a single collision domain into multiple collision domains by utilizing all the available channels on the tree. In HMesh, the number of interfering links and their link data rates are reflected since nodes exchange RV via CTL messages.

Percentage of different link data rates

To measure the effect of rate separation for rate anomaly mitigation, we define the percentage of different link data rates as follows:

$$P_r=\frac{N_r}{N_{total,L}}·100\left(\%\right),$$ (19)

where $N_r$ is the number of links that use link data rate r on the tree, and $N_{\mathrm{total},L}$ is the total number of established links on the tree. For example, when a tree consists of 50 links and 30 links of 50 links use 36 Mbps, $P_{36M}=\left(30/50\right)\times 100=60\%$ . As more high data rate links are utilized, the effect of rate separation increases (i.e. the degree of rate anomaly decreases).

Figure 13 shows the percentage of different link data rates obtained from 30 distinct scenarios. Each scenario includes 1 gateway, 30 non-gateways, and 30 UDP flows with 1 Mbps. Every node is equipped with three NICs. As seen from Figure 13, Hyacinth uses most of links as 6 Mbps and 9 Mbps, since it constructs a tree using the hop-count metric that prefers a low-rate single-hop link. Even though ROMA and CoCA use more high-rate links than Hyacinth, they still use most of links as low-rate links from 6 Mbps to 18 Mbps. On the contrary, HMesh utilizes a large portion of high-rate links compared with the other protocols, since it is aware of link data rates on different channels and interface pairs.

Figure 13.

The percentage of links for each link data rate.

Control overhead and convergence time in HMesh

The control overhead and convergence time in HMesh is determined by the periodic $T_p$ interval value. To evaluate the control overhead, we define the control overhead (CO) as follows:

$$CO=\frac{C_o}{C_o+D_o}·100\left(\%\right),$$ (20)

where $C_o$ is the total control packets (in bps) introduced by HMesh, and $D_o$ is the aggregate throughput obtained by HMesh in a scenario. The convergence time is defined as the time when all nodes finish their channel assignment and routing to build the tree architecture.

Figure 14 shows the control overhead and convergence time of HMesh as the periodic $T_p$ interval value increases, taken from 30 different scenarios. In each scenario, there are 1 gateway and 30 non-gateway nodes, and 30 UDP flows with 1 Mbps are generated. Each node uses three NICs. From Figure 14(a), we can see that the control overhead decreases when the $T_p$ interval value increases, because the frequency of control message exchanges and link data rate measurements decreases. From Figure 14(b), we can observe that the convergence time increases as the periodic $T_p$ interval increases, since HMesh requires more time to exchange the required information to construct the tree architecture. When the $T_p$ interval is 20 s, HMesh shows low control overhead (i.e. less than 1%) and converges within 100 s.

Figure 14.

Control overhead and convergence time in HMesh. HMesh: heterogeneity-aware mesh.

Performance with the other parameters

We evaluate the performance using different numbers of channels, NICs, and gateways. Table 7 shows the aggregate throughput of Hyacinth, ROMA, CoCA, and HMesh, which is taken from 30 distinct scenarios. Each scenario consists of 30 non-gateway nodes. Total 30 UDP flows are generated, and each flow has the traffic rate of 1 Mbps.

Table 7.

Performance using the other parameters.

Protocol	Aggregate throughput (Mbps)
	No. of channels			No. of NICs			No. of gateways
	6	9	12	2	3	4	1	2	3
HMesh	11.1	13.2	14.3	11.4	14.3	15.7	14.3	15.2	16.5
CoCA	10.2	11.6	12.8	9.9	12.8	14.2	12.8	13.6	15.0
ROMA	9.6	10.5	11.9	9.3	11.9	13.2	11.9	12.3	13.1
Hyacinth	8.5	9.4	10.8	8.2	10.8	12.2	10.8	11.3	11.8

NICs: network interface cards; HMesh: heterogeneity-aware mesh; CoCA: cooperative channel assignment.

When the number of channels varies, the number of NICs per node is three, and there is one gateway in a scenario. As observed from Table 7, all the compared protocols show better performance with increasing number of channels, since they utilize all the available channels using a limited number of NICs. When the number of NICs increases, there are 12 nonoverlapping channels and one gateway in a scenario. In Table 7, every protocol achieves higher performance with additional NICs. When the number of gateways varies, each node uses 12 channels and three NICs. We can see from Table 7 that Hyacinth, ROMA, CoCA, and HMesh support improved performance as the number of gateways increases, since nodes build multiple trees based on different gateways to distribute traffic loads on WMSNs. Overall, Table 7 shows that HMesh supports improved performance than the other protocols irrespective the number of channels, NICs, and gateways.

Experiment results

In this section, we evaluate the performance of HMesh using our IEEE 802.11 WMSN test bed, and compared it with Hyacinth ³ and CoCA. ²⁵ Our test bed includes 10 nodes within indoors at the same floor. One of 10 nodes is configured as the gateway on our test bed. Each node is a standard Barebone PC operating Fedora Linux ⁴⁴ with the Linux 2.6.16 kernel ⁴⁵ and has three Proxim 802.11a/b/g Combo Cards with peripheral component interconnected (PCI) or personal computer memory card international association (PCMCIA) types based on Atheros chipset. ⁴⁶ Every NIC is set to IEEE 802.11a mode with default parameters. By separating external antennas at a distance of over 18-inch,^4,47 we could use 12 noninterfering channels (i.e. channels 36, 40, 44, 48, 52, 56, 60, 64, 100, 104, 108, and 112). After measuring the throughput of links for each channel and interface pair, we fixed the data rates of links using the latest madwifi-0.9.4 driver. ³² These link data rates are used in Hyacinth, CoCA, and HMesh. In case of Hyacinth and CoCA, nodes use the link data rates on the default channel (e.g. channel 36) for channel assignment and routing. Every experiment result is averaged from five different scenarios. In each scenario, we generated five external flows and five internal flows. Each flow has different source–destination node pair. Both UDP flows and TCP flows are generated using iperf-2.0.4 tool. ⁴⁸ For each scenario, we repeated experiments five times such that a total of 25 results are averaged with the 95% confidence interval. In our IEEE 802.11a test bed, total 94 links are available, when link X-Y (from node X to node Y) and link Y-X (from node Y to node X) are counted individually.

We measured the RSS values of 94 links for each channel and interface pair by generating a saturated UDP flow with the packet size of 1500 bytes during 20 s. Figure 15(a) shows the RSS variations of the 94 links, where the horizontal solid line is the RSS threshold value for 6 Mbps. In Figure 15(a), we can see a difference in RSS values over 20 dBm. This result demonstrates the channel and interface heterogeneity of practical IEEE 802.11-based WMSNs.

Figure 15.

RSS variations of 94 links in IEEE 802.11a test bed. RSS: received signal strength.

Figure 16 shows the performance of UDP and TCP flows. In Figure 16(a), the traffic rate per UDP flow increases from 1 Mbps to 6 Mbps. From Figure 16, we can see that HMesh supports much better performance with UDP flows than Hyacinth and CoCA. When the traffic rate per UDP flow is 6 Mbps, Figure 16(a) shows that HMesh supports about 19.5% and 117.8% better aggregate throughput than CoCA and Hyacinth, respectively. For TCP flows, Figure 16(b) shows that HMesh provides about 31.1% and 148.1% higher aggregate throughput than CoCA and Hyacinth, respectively. These results reveal the importance of rate separation by exploiting the channel and interface heterogeneity in practical IEEE 802.11 networks.

Figure 16.

Performance with UDP and TCP flows in IEEE 802.11a test bed.

Conclusion

In this article, we motivated our work by observing the channel and interface heterogenity in real IEEE 802.11 based sensor networks. Also, we highlighted the rate separation for rate anomaly mitigation in IEEE 802.11 multirate networks. To mitigate rate anomaly, we proposed a novel channel assignment protocol, HMesh, for IEEE 802.11 multiradio multirate networks. The design goals of HMesh are no modification to the commodity IEEE 802.11 devices and separating different data rate links via multiple channels and interfaces by exploiting the channel and interface heterogeneity. For channel assignment and routing over the tree architecture, HMesh uses the HATT metric and the HRS algorithm. Based on the link capacity, HMesh uses the HATT metric to select parent nodes on the tree by considering the channel and interface heterogeneity of links. Also, the HRS algorithm utilizes the REF metric to separate different data rate links by improving the network throughput and the throughput fairness of multihop flows.

To evaluate the performance of HMesh, we performed extensive ns-2 simulations and real experiments on our IEEE 802.11 WMSN test bed. Our evaluation results verify that HMesh shows significantly improved performance compared with existing channel assignment protocols designed for WMSNs. Our future work may include extending HMesh to measure the channel and interface heterogeneity more efficiently in practical IEEE 802.11 networks.