BandEst: Measurement-Based Available Bandwidth Estimation and Flow Admission Control Algorithm for Ad Hoc IEEE 802.15.4-Based Wireless Multimedia Networks

Abstract

We highlight different important factors that must be considered for an effective available-bandwidth-based flow admission control algorithm in ad hoc wireless networks. Moreover, we present BandEst; it is a combination of a measurement-based available bandwidth estimation technique and a flow admission control algorithm for ad hoc IEEE 802.15.4-based ad hoc networks that considers the identified factors. Extensive simulations are performed to compare BandEst with the state-of-the-art available-bandwidth-based flow admission control algorithms for ad hoc wireless networks. Our simulation results demonstrate that BandEst significantly outperforms the state-of-the-art available-bandwidth-based flow admission control algorithms for ad hoc wireless networks.

1. Introduction

IEEE 802.15.4-based ad hoc wireless multimedia sensor networks (WMSNs) are starting to emerge [1]. Typically, these networks are deployed for visual surveillance [2] and assisted living [3]. The bandwidth supported by the IEEE 802.15.4 standard is limited and shared. Limited and shared bandwidth imply that an IEEE 802.15.4-based ad hoc WMSN can only accommodate a few flows inside the network. A large number of flows inside the network (w.r.t. the available resources, e.g., the available bandwidth) can cause congestion. Therefore, a flow admission control algorithm is required that limits the amount of data inside the network.

In ad hoc IEEE 802.15.4-based wireless networks, bandwidth is a shared resource. The common assumption is that the bandwidth available to a node is shared within the interference range of the node, and nodes within two hops distance can cause interference [4]. We also hold this assumption throughout the paper. The shared nature of the bandwidth in wireless networks results in the following phenomenon: the data generation rate of nodes within the interference range of a node inside a network affects (i) the available bandwidth [5] and (ii) intra-flow and inter-flow contention [5]. Furthermore, a MAC layer protocol dictates the sharing of a communication medium; hence it limits the amount of bandwidth available to a node, for example, in a carrier sense multiple access collision avoidance (CSMA-CA) MAC layer protocol a node can not transmit in a back-off mode. Therefore, an effective available-bandwidth-based flow admission control algorithm must take into account the identified factors.

This paper identifies the following: (i) the contention count on a node which is not along the data forwarding path, but is within the interference range of transmitters along the data forwarding path, is a function of the number of transmitters (along the data forwarding path) within the interference range of the node, (ii) the maximum intra-flow contention count on a node along the data forwarding path is 5 times the flow's required bandwidth, (iii) increased data traffic inside a network increases the CSMA-CA-based MAC layer overhead, that is, mean back-off interval, mean number of retransmissions, mean ACK waiting time, mean number of ACK packets, and mean contention window size, and (iv) concurrent admission requests can result in incorrect admission decisions. Therefore, a flow admission control algorithm must incorporate the following: (i) a mechanism to determine the correct contention count on nodes which are not on the data forwarding path but are within the interference range of transmitters along the data forwarding path, (ii) a mechanism to determine correct intra-flow contention count, (iii) a mechanism to predict the additional MAC layer overhead with an increased data traffic load within the interference range of a node, and (iv) a mechanism to deal with concurrent admission requests. The state-of-the-art available-bandwidth-based flow admission control algorithms do not adequately address the complete set of identified factors.

Apart from identifying the important factors for a proper available-bandwidth-based flow admission control algorithm in ad hoc wireless networks, this paper also presents BandEst; an available-bandwidth-based flow admission control algorithm for IEEE 802.15.4-based ad hoc WMSNs. To estimate the available bandwidth, each node inside a network considers the transmission rate of nodes within the interference range of the node estimating the available bandwidth. Moreover, each node internally measures the MAC layer overhead and considers its actual impact on the available bandwidth. BandEst's flow admission control algorithm is a combination of novel algorithms that estimates additional MAC layer overhead with an anticipated increase in the data load inside a network, estimates intra-flow contention on nodes along the data forwarding path, a new flow's contention on nodes which are within the interference range of the transmitters along the data forwarding path but are not on a flow's data forwarding path, and it deals with the concurrent admission requests problem as well. Therefore, BandEst is a comprehensive available-bandwidth-based flow admission control algorithm for IEEE 802.15.4-based ad hoc WMSNs. We designed and evaluated BandEst for IEEE 802.15.4-based ad hoc WMSNs, but it can also work very well (we expect) with other types of networks, for example, IEEE 802.11-based ad hoc networks with minor modifications, for example, taking into account the details of the IEEE 802.11 MAC layer protocol.

The remainder of this paper is organized as follows. In Section 2, we identify key factors for a proper flow admission control in ad hoc wireless networks. In Section 3, we survey related work. In Section 4, we discuss BandEst in detail, and in Section 5 simulation results are presented. We conclude this paper in Section 6.

2. Key Factors for a Proper Flow Admission Control in Ad Hoc Wireless Networks

In this section, we identify the key factors for a proper flow admission control in ad hoc wireless networks, and experimentally derive threshold values for flow admission control in IEEE 802.15.4 networks via simulations. This section helps to lay the ground work for evaluating the related work. Table 1 shows the general simulation parameters.

Table 1

General simulation parameters.

Parameter	Value
MAC layer	Unslotted CSMA-CA
MAC layer reliability	Enabled
Radio duty cycling algorithm	No duty cycling
Radio model	Unit disk graph (distance loss)
MAC layer queue size	30 frames
Channel rate	250 kbps
Node transmission range	50 meters
Node carrier sensing range	100 meters
Total frame size	127 bytes
Simulated node type	Tmote sky

2.1. Increasing Data Traffic Load Increases MAC Layer Overhead

Typically, increasing the data traffic load inside a network increases the CSMA-CA-based MAC layer overhead, for example, the number of retransmission and the back-off duration [5–7]. The statement holds true for wireless ad hoc networks using CSMA-CA as the MAC layer protocol, for example, IEEE 802.11 and IEEE 802.15.4. Therefore, at least an effective available-bandwidth-based flow admission control algorithm needs some hard numbers regarding the bandwidth consumed as the MAC layer overhead corresponding to different values of the offered data load inside a network. This paper deals with IEEE 802.15.4-based WMSNs; therefore we experimentally determined the IEEE 802.15.4's unslotted CSMA-CA MAC layer overheads (back-off and retransmission) with an increased data load inside a network. We conducted multiple simulations using a simple line topology of 4 nodes in which each intermediate node is within the transmission range of its immediate upstream and downstream nodes. We selected a line topology to estimate the MAC layer overhead (back-off and retransmission) because it can capture the effects of intra-flow contention, and at the same time it facilitates reporting of the MAC layer overhead at each node present inside the network. The simulations are performed with the Cooja wireless sensor network (WSN) simulator. To estimate the MAC layer overhead (back-off and retransmission) we consider the aggregate data traffic load, but there are other parameters that may affect the MAC layer overhead such as packet size, nature of traffic (burst, constant bit rate), and number of flows inside a network. We expect that, beyond the aggregate data traffic load, other parameters will only have a modest impact. We created 10 different simulation scenarios, and in each scenario we vary the offered data load inside a network. In the first simulation scenario, node 1 transfers 2 kbps to node 4, as nodes 2 and 3 are acting as the relaying nodes; therefore in this case, the total data load within the interference range of nodes 1, 2, and 3 is 6 kbps. In subsequent simulation scenarios, node 1 increases its data generation rate in such a manner that it increments data load within the interference range of nodes 1, 2, and 3 to 12, 18, 24, 30, 36, 42, 48, 54, and 60 kbps. Each simulation runs for 110 seconds, and to determine the mean overhead value each simulation is repeated 10 times. The back-off overhead is measured in time, but Figure 1 reports the MAC layer overhead in bps. We converted the mentioned overhead to bps by multiplying the accumulated time duration (during each second) a node spends in the back-off mode with the channel rate.

Figure 1

Data load versus average back-off and retransmission overhead.

Figure 1 shows that with an increased data load the average back-off and retransmission overheads increase; therefore it is essential to proactively consider the back-off and retransmissions overhead by taking into account the additional data load inside a network. If the anticipated data load within interference range of a node inside a network is in excess of 60 kbps, extrapolation techniques can be used to determine the additional back-off and retransmission overheads. Cooja [8] emulates the Contiki operating system's [9] CSMA-CA MAC layer, and Contiki CSMA-CA uses a constant contention window size; therefore we can derive the contention window overhead by knowing the number of additional packets a node intends to transmit. Similarly, an approximation of the ACK overhead can also be derived from the number of packets a node is transmitting. The same technique (presented in this section) is used to consider the additional MAC layer overhead with an anticipated increase in the data traffic load inside a network, and results presented in [6] show that it outperforms the method presented in [5].

2.2. Determining Maximum Intra-Flow Contention Count

It has been claimed in [5, 7, 10] that the maximum intra-flow contention count on a node along the data forwarding path is 4. To verify the claim, we carried out additional simulations. In our experiment, using the topology shown in Figure 2, node A is the source node and node F is the sink node. Node A transmits at the rate of 10 kbps (10 data packets per second) to the sink node. Node A starts the transmission at a simulation time of 5 seconds and terminates the data packets transmission at a simulation time of 105 seconds. In our experiment, we measured the data activity at nodes inside the network via wireless channel-sensing throughout the duration of node A's flow. We repeated the experiment 10 times, and the mean data load observed by the nodes while node A is transmitting data packets is shown in Table 2 along with the 95% confidence interval. The end-to-end flow's throughput was perfect, that is, 10 kbps.

Table 2

Data activity as measured by nodes.

Node ID	Mean data activity	95% confidence interval
A	31.41 kbps	31.21–31.61 kbps
B	41.35 kbps	41.16–41.53 kbps
C	51.85 kbps	51.53–52.17 kbps
D	43.48 kbps	43.33–43.63 kbps
E	33.18 kbps	32.87–33.49 kbps
F	22.85 kbps	22.64–23.06 kbps

Figure 2

Simulated network topology.

Table 2 demonstrates that the mean data load observed by node C is approximately 50 kbps, which is 5 times the transmission rate of node A. The data loads observed by nodes A, B, D, E, and F are approximately 30 kbps, 40 kbps, 40 kbps, 30 kbps, and 20 kbps, respectively. Therefore, the contention counts at nodes A, B, D, E, and F are 3, 4, 4, 3, and 2, respectively. The maximum contention count is 5, the reason is that nodes A, B, D, and E are within the interference range of node C; hence node C cannot transmit while nodes A, B, D, and E are transmitting. Moreover, node C also relays node A's data. The data activity as observed by the nodes is higher than flow's data transmission rate multiplied by a nodes’ intra-flow contention factor; this is because of retransmissions.

2.3. Determining Correct Contention Count on Nodes Not on a Flow's Data Forwarding Path

There may be nodes inside a network that are not on a new flow's (i.e., flow requesting admission) data forwarding path, but are within the interference range of transmitters along the new flow's data forwarding path, and other flows’ data is being relayed by those nodes. Therefore, it is necessary to determine the new flow's correct contention count on those nodes; otherwise, there are strong chances of congestion inside a network.

The state-of-the-art flow admission control algorithms for ad hoc wireless networks do not take into account the correct contention count on nodes which are not on the new flow's data path. When a flow's admission request arrives at a node, mostly the contention on such nodes are only considered by determining the minimum available bandwidth within the interference range of a node (hereafter, we refer to this technique as locally estimating the contention count). Hence, the algorithm is assuming a contention count of 1 for all such nodes. This technique suffers from the following two problems.

• (1)

  If a common node (a node that is not on a new flow's data forwarding path) is within the interference range of more than one transmitter (nodes on the data forwarding path of a new flow), the contention count on the node is equal to the number of transmitters within the interference range of the node. Hence, a flow admission algorithm may wrongly admit a flow.

• (2)

  Locally determining the contention count on nodes within the interference range of a transmitters can result in wrong admission decisions. Let us assume that a common node (a node that is not on a new flow's data forwarding path) is within the interference range of two transmitters and both transmitters will relay data of two different flows. Let us further suppose that the admission request for both the flows is initiated at the same time, moreover we assume that the available bandwidth at the common node is enough to accommodate a single contention count of either of the two flows. In this case, locally estimating the contention count will admit both flows (considering the flow passes the intra-flow contention test); hence one of the two flows is wrongly admitted to the network.

We performed a number of simulations to show that the contention count on a node that is not on a flow's data forwarding path, but is within the interference range of transmitter(s) along the data forwarding path, is a function of the number of transmitters within the interference range of the node. We added one more node in the network shown in Figure 2, and created 4 different simulation scenarios by changing the location of the additional node inside a network. In these simulations, node G measures the data activity using the wireless channel-sensing technique. Each simulation scenario is repeated 10 times. Figure 3 shows the modified network topologies for different simulation scenarios. Table 3 shows the mean data activity measured by node G during the duration of node A's flow.

Table 3

Data activity as measured by node G.

Scenario	Mean data activity	95% Confidence interval
1	10.20 kbps	10.05–10.35 kbps
2	20.36 kbps	20.06–20.66 kbps
3	31.90 kbps	31.25–32.55 kbps
4	42.95 kbps	42.25–43.65 kbps

Figure 3

Simulated network topologies.

In Scenario 1 node G is within the interference range of one transmitter, that is, node E, and Table 3 shows that the contention count at node G in this case is approximately 1. Similarly, in Scenarios 2, 3, and 4, node G is within the interference range of 2, 3, and 4 transmitters; hence the contention count at node G in these cases is 2, 3, and 4, respectively. Node A was transmitting at the rate of 10 kbps, and the end-to-end throughput was 10 kbps. The data activity measured by node G in different simulation scenarios is greater than the contention count at node G multiplied by the node A's flow data rate, because of retransmitted data packets.

2.4. Summary

Summarizing these observations, the following factors must be considered for a proper available-bandwidth-estimation-based flow admission control algorithms for ad hoc wireless networks using a CSMA-CA-based MAC layer protocol.

• (1)

  Consider the complete CSMA-CA MAC layer overhead while periodically estimating the available bandwidth.

• (2)

  Determine the correct intra-flow contention factor.

• (3)

  Determine the correct contention factor on nodes that are not on a data flow's forwarding path but are within the interference range of transmitters along the data forwarding path.

• (4)

  When a new admission request is received at a node, the node must proactively take into account the complete additional CSMA-CA MAC layer overhead with an increased data traffic load (due to the flow's admission) not only at the node but also on nodes which are within the interference range of the node (if those nodes are transmitting other flows’ data).

3. Related Work

In this section, we discuss the state-of-the-art available-bandwidth-based flow admission control algorithms. A detailed survey of the state-of-the-art flow admission control algorithms for ad hoc wireless networks is presented in [11]. Moreover, a detailed discussion on bandwidth estimation techniques, metrics, and tools is presented in [12], and a detailed survey on a radio's link quality estimation is given in [13].

Available-bandwidth-based flow admission control algorithms for wired networks use active available bandwidth estimation techniques, for example, [14–16]. Active available bandwidth estimation techniques are not suitable for ad hoc wireless networks due to the following reasons.

• (1)

  Active bandwidth estimation techniques use probe packets to measure the available bandwidth between a given source-destination pair. When the number of source-destination pairs is large, the number of probe packets is large as well. This may require a substantial amount of bandwidth.

• (2)

  Due to the time-varying nature of the wireless links, the wireless network topology is not as stable as the wired network topology. This requires active bandwidth estimation techniques to conduct bandwidth estimation at a higher frequency. This can result in extra bandwidth requirements.

In [17], a contention aware flow admission control for ad hoc wireless networks (CACP) is presented. Flow admission control is performed based on the available bandwidth estimate. An estimate of the available bandwidth is provided through the wireless channel-sensing mechanism, and it considers back-off periods as idle periods. Here the assumption is that the back-off periods are negligible even if the channel is saturated. The algorithm considers both intra-flow and inter-flow contention counts in a distributed manner. The drawbacks associated with this scheme are as follows: the impact of the MAC layer on the available bandwidth is not considered and the impact of the MAC layer overhead on the available bandwidth with an increased data traffic load inside a network is not considered.

In [10], a distributed flow admission control algorithm for assuring QoS in ad hoc wireless networks is presented. It has been claimed in [10] that before deciding about a flow's admission request both intra-flow and inter-flow contention have been taken into account. The paper claims that the maximum intra-flow contention count on an intermediate node along the data forwarding path is 4. Inter-flow contention is considered by matching a flow's required bandwidth with the minimum available bandwidth within the interference range of a node deciding about the flow's admission request. An estimate of the available bandwidth is provided through a wireless channel-sensing mechanism that uses both the virtual and physical carrier sensing mechanisms of the IEEE 802.11 MAC layer protocol. The proposed flow admission control algorithm uses a two-pass signaling mechanism to reserve resources along the data forwarding path. The drawbacks associated with this technique are as follows: incomplete inter-flow contention, that is, each node only checks the minimum available bandwidth within its interference range. In some scenarios, the calculated intra-flow contention count will be wrong. Also, the impact of an increased MAC layer overhead with an increased data traffic load inside a network is not considered.

In [18], an analytical capacity estimation based flow admission control scheme for multihop wireless networks is presented. Each node uses an analytical model to decide about a flow's admission request. A node inside a network accepts a flow if ${\lambda }_{\text{new}}$ is greater than the available capacity. The incoming data packets arrival rate is calculated using the equation $({\lambda }_{\text{new}}=\lambda +K{\lambda }_{\text{flow}})$ . In the given equation λ represents the data packet arrival rates of all nodes within the transmission range of the node, ${\lambda }_{\text{flow}}$ is a new flow's data arrival rate, and K is the contention count. This technique uses $K=\mathrm{2}$ for a source node, $K=\mathrm{3}$ for an intermediate node, and $K=\mathrm{1}$ for a destination node. All nodes processing a flow's admission request evaluate the given equation. The downsides of this scheme are as follows: there are cases in which both the intra-flow and inter-flow contention count estimation will be wrong (given that the interference range of a node is greater than its transmission range), the mathematical model assumes a constant packet size, assuming that at the MAC layer the main factor that affects the delay is retransmissions, and the algorithm does not consider the impact of the increased MAC layer overhead with an increased data traffic load inside a network on the available bandwidth.

CapEst [19] is a measurement-based link capacity estimator for wireless networks. It monitors the service time of data packets at each link, and based on this measurement an estimate of a link's capacity is made; hence it is not a MAC layer specific method. CapEst does not consider the increased MAC layer overhead with an increased data load inside a network.

In [5], an available-bandwidth-based flow admission control algorithm (ABE) for ad hoc wireless networks is presented. An estimate of the available bandwidth is provided through the wireless channel-sensing mechanism considering both virtual and physical carrier sensing, and different types of IEEE 802.11's CSMA-CA MAC layer interframe spacings. It has been argued in [5] that measuring the channel activity considering the time spent in virtual and physical carrier sensing and different interframe spacing results in an overestimate of the available bandwidth. This happens due to the nonsynchronization of sender and receiver nodes in an ad hoc wireless network. Therefore, the paper presents a mathematical model that takes into account the collision probability to estimate the actual available bandwidth. Hence, it probabilistically takes into account the future back-off overhead through a mathematical model. The collision probability is derived from the number of HELLO messages a node has received over the number of HELLO packets the node expected to receive during the last measurement interval. The flow admission control algorithm uses one-hop and two-hop neighbors’ information to calculate the intra-flow contention, and the authors of the paper have mentioned that the maximum intra-flow contention count on a node is 4. Inter-flow contention is taken into account by determining the minimum available bandwidth within the interference range of a node when deciding about flow's admission request. The downsides of this technique are as follows: with an increased data traffic load inside a network only additional back-off overhead is considered; additional retransmission and contention window overheads are ignored. The intra-flow contention count estimator does not always provide the right contention count, and the inter-flow contention count estimator is too simple as it only considers minimum available bandwidth within the interference range of a node. Finally, the collision probability is derived without considering the future data traffic load.

In [7], an enhancement to [5] is proposed that proactively considers the retransmission and back-off overhead but uses the same flow admission control algorithm as in [5]. The drawback of this scheme is that additional contention window overhead is not considered with an increase in the data traffic load inside a network, and the assumptions made in the proposed mathematical model may not hold true in actual networks; for example, the increased MAC layer overhead with an increased data load may depend on the future data traffic load.

Proactive bandwidth estimation for IEEE 802.15.4-based networks (PABE) [6] is a measurement-based enhancement to ABE's bandwidth estimation method and flow admission control algorithm. Instead of using a mathematical model for collision and back-off prediction, it uses empirically gathered data to predict additional back-off overhead. Moreover, it uses expected future data traffic load value to predict additional back-off overhead rather than using the existing data traffic load value inside a network. Simulation results demonstrated that PABE improves upon the performance of ABE. The drawbacks of the algorithm are that with an increased data traffic load inside a network additional retransmission overheads are ignored, and the intra-flow and inter-flow contention count estimators may wrongly estimate the contention counts.

Table 4 shows the comparison of the state-of-the-art available-bandwidth-based flow admission control algorithms for ad hoc wireless networks. Table 4 demonstrates that none of these algorithms take into account all the identified factors in Section 2.4. Hence, there is a need for an available-bandwidth-based flow admission control algorithm for ad hoc wireless networks that considers all the identified factors.

Table 4

Evaluation of the state-of-the-art available-bandwidth-based flow admission control algorithms for ad hoc wireless networks.

Algorithm	MAC layer effects on the available bandwidth	Intra-flow contention	Contention non-relaying nodes	Add. MAC layer overhead	Add. MAC layer overhead on non-relaying nodes
ABE [5]	Yes	Partially correct	Partially correct	Partially correct	No
PABE [6]	Yes	Partially correct	Partially correct	Yes	No
RABE [7]	Yes	No	No	Yes	No
Distributed admission control [10]	Yes	Partially correct	Partially correct	No	No
CACP [17]	No	Yes	Yes	No	No
Analytical-capacity-based [18]	Yes	Partially correct	Partially correct	No	No
CapEst [19]	Yes	No	Partially correct	No	No

4. BandEst: Measurement-Based Bandwidth Estimation Technique and Flow Admission Control Algorithm

BandEst consists of a number of modules. The architecture of BandEst is shown in Figure 4 (BandEst modules are shown in solid lines):

• (a)

  HELLO protocol module,

• (b)

  available bandwidth estimation module,

• (c)

  flow admission control module.

Figure 4

BandEst architecture.

4.1. HELLO Protocol Module

The HELLO protocol module regularly broadcasts a HELLO message after a predefined interval of time. The purposes of the HELLO messages are to discover direct neighbors (nodes within the transmission range of the node), learn direct neighbors’ data generation rate, and discover the available bandwidth at direct neighbors. Hence, BandEst HELLO messages help to construct/maintain node's direct neighbors table and the gathering of direct neighbors’ information necessary for the available bandwidth estimation and a flow admission control algorithm.

To enable the discovery of two-hop away neighbors (as the assumption is that two-hop away nodes can cause interference), each node periodically broadcasts a neighbor information message apart from the HELLO message (a node can also piggyback its neighbors’ information onto the HELLO message, but due to the small size of the IEEE 802.15.4 frame, we opted for a separate neighbor information message). In the neighbor information message, a node advertises its direct neighbors along with their data generation rates and the available bandwidth. If a single neighbor information message is not enough for a node to advertise all of its direct neighbors and related information, the node broadcasts additional neighbor information message(s). The neighbor information message helps to construct/maintain a node's two-hop away neighbors table and gathering of two-hop away neighbors’ information necessary for the available bandwidth estimation and our flow admission control algorithm.

From the above discussion it is evident that instead of monitoring the wireless channel to estimate the data activity within the interference range of a node, BandEst uses the HELLO and the neighbor information messages to learn about the data generation rate of nodes within the interference range of a node. The main reasons for using these messages are as follows: (i) data frame collision happens when data/control frames of two or more transmitters collide; hence multiple transmissions are inferred as a single transmission and this may result in an overestimate of the available bandwidth, (ii) a channel-monitoring-based mechanism requires the radio to always remain on, but to preserve energy invariably a radio duty cycling algorithm is used in IEEE 802.15.4-based networks and therefore a channel-monitoring-based mechanism is not suitable for networks where radio duty cycling is used, and (iii) the HELLO and the neighbor information messages help to discover direct and two-hop away neighbors. In this work we assume no radio duty cycling is used, but our work can easily be extended to incorporate effects of using a radio duty cycling algorithm on an available-bandwidth-based flow admission control algorithm. The downside of exchanging data generation rate information through the HELLO and the neighbor information messages is that if a node A is not in the direct transmission range of another node B, but it is within its interference range, and none of the direct neighbors of node B have that node within their transmission range, the data generation rate information of node A does not reach node B, hence B overestimates the available bandwidth. But, in this research, we assume that a network is well connected; hence such occurrences are rare. Moreover, if a flow admission control algorithm uses the wireless-channel-monitoring mechanism to estimate data activity within the interference range of a node, the algorithm still requires control message(s) to learn the following: (i) available bandwidth at nodes which are within the interference range of a node and (ii) a node's two-hop away neighbors.

4.2. Bandwidth Estimation Module

Periodically, the available bandwidth estimation module retrieves the total actual MAC layer overhead information from the MAC layer, and it keeps track of the changes over time. Similarly, the available bandwidth estimation module receives data generation rate information of nodes within the interference range of the node from its direct and two-hop neighbors table. Moreover, the bandwidth estimation module considers additional bandwidth requirements of those flows which a node has admitted, but their admission reply is still outstanding. BandEst's flow admission control algorithm performs admission control on an end-to-end basis; therefore each node along the data forwarding path performs flow admission control. If a flow's admission request is successful at a particular node along the data forwarding path, the node sets aside the required bandwidth considering the intra-flow contention and additional MAC layer overhead, before forwarding the flow's admission request. This feature helps to deal with concurrent admission requests in a first-come-first-serve order. Periodically, each node advertises its data generation rate information (including additional bandwidth of flows admitted by the node with pending admission replies) using the HELLO message.

Apart from the number of retransmitted bits and ACK frames bit, other MAC layer overheads are measured in time. The estimate of the available bandwidth is made in bits per second (bps). Therefore, the MAC layer overheads measured in time are converted to the number of bits per second by multiplying them with the channel rate. The random nature of the wireless communication medium can result in significant randomness in the available bandwidth per time unit. Such randomness can be caused by transient wireless channel impairments (shadowing, interference, multipath fading, etc.), hence estimating the available bandwidth by only considering the latest value pertaining to the overheads associated with the MAC layer and the data generation rate of nodes can be misleading. To address these issues, we propose to use a sliding-window-based averaging mechanism to estimate the available bandwidth. Let us suppose that the size of the averaging window is α, a node stores the α most recent values corresponding to the MAC layer overheads, and data generation rates of nodes within the interference range of the node.

Let β represent the summation of data generation rate of a node and the nodes within the interference range of the node, and let ${\beta }_i$ represent β at the ith index of the averaging window. Similarly ${\gamma }_i$ represents the MAC layer overhead (in bps) at the ith index of the averaging window. We further assume that ρ represents the channel rate. Therefore, at each bandwidth measurement instance, the available bandwidth is calculated by using average MAC layer overhead and average data generation rate of nodes’ within the interference of the node using (1)

$$\begin{array}{cc}& \omega =\left(\rho -\left(\left(\frac{{\sum }_{\mu =\mathrm{1}}^{\theta }\left({\beta }_{\mu }+{\gamma }_{\mu }\right)}{\theta }\right)+\phi \right)\right)\hspace{0.17em}\text{bps}.\end{array}$$

(1)

In this equation, ω represents the average available bandwidth in bps, θ represents the current size of the averaging window, and φ is the amount of bandwidth committed to flows whose admission accept message is outstanding. In case the admission is rejected, the bandwidth set aside for future flows who are rejected will eventually be reclaimed (because nodes exchange bandwidth usage information periodically) as no node injects traffic for those flows, and reservations time out after predefined interval.

4.3. BandEst's Flow Admission Control Algorithm

BandEst's flow admission control algorithm takes into account the following: (i) intra-flow contention, (ii) contention on nodes that will not relay the new flow's data but are within the interference range of transmitters (nodes that will relay new flow's data) along the data forwarding path (contention on such nodes is only considered if they are relaying some other flows’ data), (iii) increased MAC layer overhead with increased data traffic node at nodes that will relay new flow's data, and (iv) increased MAC layer overhead at nodes which are within the interference range of transmitters along the new flow's data forwarding path (if and only if the nodes are relaying some other flows’ date). In the following subsections, we discuss different components of BandEst's flow admission control algorithm in detail.

4.3.1. Intra-Flow Contention Measurements

Determining the accurate intra-flow contention count depends on the interference range of a node. Assuming that the nodes within the two-hop distance can cause interference, the interference count on any node along the data forwarding path mainly depends on the node's distance from the source and the destination nodes, as shown in Section 2.2. For a new flow's admission request, BandEst determines the actual intra-flow contention counts on source, intermediate (data relaying nodes), and destination nodes.

Figure 5 depicts the guidelines for determining the intra-flow contention count on the source and the destination nodes, and Figure 6 depicts the guidelines for determining the intra-flow contention count on intermediate nodes between a source-destination pair. The scenarios presented in Figures 5 and 6 demonstrate that in order to determine the intra-flow contention count, a node must know its one-hop and two-hop neighbors. As in BandEst each node maintains lists of its one-hop and two-hop neighbors, BandEst's flow admission control algorithm can determine the intra-flow contention count without any additional overhead. Figure 6 demonstrates that the maximum intra-flow contention on an intermediate node along the data forwarding path is 5.

Figure 5

Contention factor on source and destination node.

Figure 6

Intra-flow contention factor estimation at intermediate relaying nodes. In all above scenario, node C is the node that is calculating the intra-flow contention.

4.3.2. Considering Additional CSMA-CA MAC Layer Overhead

For estimating the additional MAC layer overhead with an increased data traffic load, BandEst uses the method presented in Section 2.1. The MAC layer overhead is considered after determining the future data load, that is, current data traffic load within the interference range of a node plus the contention count times the new flow's required bandwidth. The overhead associated with the method presented in Section 2.1 is that a lookup table is stored on nodes that return estimated MAC layer overhead corresponding to a certain value of the data load inside a network. It is not possible to store the MAC layer overhead in terms of bps corresponding to each possible offered data load, but an algorithm can estimate the MAC layer overheads for an offered data load not present in the lookup table by linear interpolation, using the two closest available data points.

4.3.3. Estimating Contention on Non-Relaying Nodes and Concurrent Admission Requests

It is not enough to take into account the impact of intra-flow contention and additional MAC layer overhead to arrive at accurate admission decisions. An algorithm is required that can take into account the impact of a flow's contention on nodes that are not on the data forwarding path from the source node to the destination node, but those nodes are within the interference range of transmitter(s) on the data forwarding path.

We devised an algorithm to consider actual contention on non-relaying nodes which are within the interference range of transmitters along the forwarding path. Whenever a node receives an admission request message, it decides about the flow's admission request by considering intra-flow contention and additional MAC layer overhead. If after considering the intra-flow contention and additional MAC layer overhead the node decides to accept the flow, the node stores the information in the admission request message along with the bandwidth required by the flow, in an internal data structure. Afterwards, the node broadcasts a bandwidth increment message in which the node informs its direct neighbors about its increased bandwidth usage due to the new flow. After broadcasting the bandwidth increment message, the node waits for a small period of time before forwarding the admission request message to the next hop along the data forwarding path. Upon reception of the bandwidth increment message, direct neighbors of the node calculate their available bandwidth by considering the increased bandwidth usage information, and if the receiving node is already transmitting data, it also considers the additional MAC layer overhead. If a node decides that it has enough bandwidth to bear the interference caused by the new flow, it updates bandwidth usage information in its one-hop table corresponding to the broadcasting node. Afterwards, direct neighbors rebroadcast the bandwidth increment message so that the increased bandwidth usage information of the node (ideally) reaches all nodes within its interference range. Two-hop neighbors estimate the available bandwidth considering the increased bandwidth usage information of the node and additional MAC layer overhead (if the node is already transmitting data). If the two-hop node decides that it has enough bandwidth to bear the new flow's contention, it updates bandwidth usage information in its two-hop neighbors table corresponding to the bandwidth increment message originator node. If any of the nodes within the interference range of the node decides that it does not have enough bandwidth to accommodate the interference caused by the new flow, it unicasts an admission reject message to the node. If the node receives an admission reject message while it was waiting to forward the admission request message it clears the stored information and drops the admission request message. In case an admission is rejected, the bandwidth usage information of nodes is automatically adjusted in the neighbors’ table when nodes readvertise their bandwidth usage in the HELLO message. Moreover, it is possible that a node receives multiple copies of the same bandwidth increment message; hence a duplicate detection mechanism is in place to detect these scenarios and drops duplicate bandwidth increment messages. Note that with this contention estimation algorithm the node only needs to consider the forward intra-flow contention (contention caused by the node and its downstream nodes) as due to the bandwidth increment message the nodes on the forwarding path have already considered contention from upstream nodes. If admission request fails at any node, reservations at preceding nodes time out.

In case of concurrent admission requests (assuming that nodes along the forwarding path can only accommodate a single flow), possible scenarios are the following: (a) one of the requests wins. If that request latter fails to be successful, end-to-end the resources will be freed. (b) Both requests may fail, even if one could have succeeded. In both cases, for unsuccessful flow(s), the best strategy is to retry after a random period of time, it is possible that some new resources have become available, or the failed requests have completed and a flow's renewed attempt to get admitted will not be concurrent to another, conflicting one, with high probability.

If after the execution of the flow admission control algorithm on nodes along the data forwarding path the admission request message reaches the destination node, a flow is admitted end-to-end. The destination node transmits an admission accept message towards the source node on the reverse path. If the nodes along the data forwarding path do not receive the admission accept message for the flow, all data structures maintained corresponding to the flow's admission request are updated to reflect the actual network state.

4.4. BandEst's Control Messages Overhead

BandEst uses four control messages, namely, (i) HELLO message, (ii) neighbor information message, (iii) admission request message, and (iv) admission grant/reject message. For deriving the associated overhead, we make the following assumptions.

• (1)

  There are a total n nodes inside a network.

• (2)

  The size of a HELLO message is k bytes.

• (3)

  On average a node has $\bar{T}$ direct neighbors.

• (4)

  The total size of the neighbor information message is l bytes.

• (5)

  The total size of the neighbor information message header (constant part) i bytes.

• (6)

  The total number of neighbor information structures contained in a single neighbor information message is j.

• (7)

  The average length of a data forwarding path from a source node to a sink node is $\bar{P}$ .

• (8)

  The total size of the bandwidth increment message is b bytes.

• (9)

  The total size of the admission request message is y bytes.

• (10)

  The total size of the admission grant/reject message is z bytes.

Overhead of the HELLO Message per HELLO Message Broadcast Interval. $n\times k$ gives the network-wide HELLO message overhead in bytes per HELLO message broadcast interval.

Overhead of the Neighbor Information Message per Neighbor Information Message Broadcast Interval. Equation (2) gives the average network-wide neighbor information messages overhead in bytes. The overhead increases when a node has many neighbors, as the algorithm then splits the neighbor information message into multiple packets, each with its own packet header. There will be a total of $⌈\bar{T}/j⌉$ such messages. Consider

$$\begin{array}{cc}& Overhea{d}_{\_NI}=\left\{\begin{array}{cc}\left(n\times (\bar{T}\times l)\right)+(n\times i)\hfill & \bar{T}\le j,\hfill \\ \left(n\times (\bar{T}\times l)\right)+\left(⌈\frac{\bar{T}}{j}⌉\times (n\times i)\right)\hfill & \bar{T}>j.\hfill \end{array}\right.\end{array}$$

(2)

Overhead Associated with the Admission Request Message. Equation (3) gives the average overhead associated with the admission request message from a source node to a destination node in bytes. This overhead is for a single flow's admission request message. Consider

$$\begin{array}{cc}& Overhea{d}_{\_Areq}=\left((y\times \bar{P})+(b\times \bar{P})+\left(b\times (\bar{P}\times \bar{T})\right)\right).\end{array}$$

(3)

Overhead Associated with the Admission Grant Message. $\bar{P}\times z$ gives the overhead associated with the admission grant message corresponding to a single flow's admission request message in bytes.

Overhead Associated with the Admission Reject Message. Equation (4) gives the overhead associated with the admission reject message in bytes. In the best case, no node transmits the admission reject message, and in the worst case, all neighbor nodes transmit the admission reject message. Consider

$$\begin{array}{cc}& \mathrm{0}\le Overhea{d}_{\_Arej}\le \bar{T}\times z.\end{array}$$

(4)

5. Simulation Results

Simulations were carried out with the Cooja wireless sensor network simulator. General simulation parameters are similar to the parameters shown in Table 1, but in these simulations we randomly select the data frame size. Total network area is 500 × 500 m². In a first scenario, we generated a random network topology of 100 wireless sensor nodes. In a second scenario, we generated a random network topology of 150 wireless sensor nodes. For BandEst's performance evaluation, we selected PABE and RABE as competitors because both are the state-of-the-art admission control algorithms for ad hoc wireless networks. RABE is designed and implemented for IEEE 802.11-based networks; therefore, for our simulations, we implemented RABE considering the IEEE 802.15.4 unslotted CSMA-CA MAC layer protocol. It has been shown in [6] that proactively considering the MAC layer overhead using the anticipated future data load improves the performance of available-bandwidth-based flow admission control algorithm that uses an analytical model to predict additional MAC layer overhead. Therefore, in our RABE implementation, instead of using a mathematical model (based on the existing data load inside the interference range of a node) to proactively consider the back-off and retransmission overhead, our implementation of RABE uses the future data load to proactively consider the back-off and retransmissions overheads. Our implementation of PABE is exactly the same as described in [6]. Each simulation scenario was repeated 25 times with different random seeds. Each simulation ran for 100 seconds. Four different source-destination pairs are randomly selected (bandwidth is a shared and scarce resource in IEEE 802.15.4-based networks; therefore we opted for a total of four multihop flows in the networks. Beyond four flows there are strong chances that the networks will become congested; hence all the schemes will reject new flows). The throughput of each connection is randomly distributed in the range $[\mathrm{2,22}]$  kbps. Nodes randomly select a frame size between 80 and 127 bytes. The source nodes of the flows transmit the admission request message at 10, 20, 30, and 40 seconds. In the following simulation scenarios, we consider that a flow admission control algorithm makes a wrong admission decision if accepting new flow results in throughput degradation of the newly admitted and/or already admitted flows by more than 5% [5]. Similarly, a flow admission control algorithm makes a wrong admission decision if it unnecessarily rejects a flow; that is, if the algorithm would have accepted the flow, this flow's and already existing flows’ end-to-end bandwidth requirements could have been satisfied. It must be noticed here that ABE and RABE in their evaluations do not consider the fact that the algorithm can also make wrong decision by unnecessarily rejecting a flow; therefore our definition of effectiveness $(\eta )$ as given in (5) is more comprehensive. One may argue that unnecessarily rejecting a flow's admission request does not degrade the performance of already admitted flows, whereas wrongfully accepting a flow may degrade the performance of already admitted flows. Therefore, wrong accepts are worse compared to unnecessarily rejecting flows; hence we should only consider wrong admissions as a bad admission decision. The alternate argument is that one must use available resources efficiently; otherwise, one has to deploy sufficient resources so that QoS requirements of flows can be satisfied during peak network utilization, but in this case most of the time the network resources are underutilized. Hence, to have a comprehensive evaluation, we give equal importance to both types of wrong decisions. Consider

$$\begin{array}{cc}& \eta =\frac{\text{Number}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{correct}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{admission}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{decisions}}{\text{Total}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{number}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{admission}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{requests}}.\end{array}$$

(5)

Figure 7 shows the mean effectiveness of the different evaluated methods over 25 repetitions, along with a 95% confidence interval. Figure 7 shows that for the network of 100 wireless sensor nodes the mean effectiveness of BandEst is higher than PABE, RABE, and no admission control, and the difference is statistically significant (while the confidence intervals of BandEst, PABE, and RABE are not that clearly delineated, they in fact do not overlap). Figure 7 demonstrates that the performance of RABE and PABE in terms of the mean effectiveness is similar and their 95% confidence intervals overlap. We noticed that wrong admission accept decisions in case of BandEst are due to the following: (i) the corruption of a broadcast bandwidth increment message due to interference and (ii) a lost admission reject message in response to a bandwidth increment message. Figure 7 demonstrates that the mean effectiveness of BandEst is higher than the other techniques, and the difference is statistically significant in a denser network of 150 nodes. Furthermore, from Figure 7, we can conclude that the mean effectiveness of all the evaluated techniques decreases a bit as the network becomes denser. In the simulations, we have observed that a higher density leads to more broadcast messages being lost, hence a decreased effectiveness of BandEst. PABE and RABE do not consider the correct contention factor on relaying and non-relaying nodes, hence they demonstrated inferior performance compared BandEst. Figure 7 also shows the mean effectiveness when no admission control algorithm is used. The mean effectiveness with no flow admission control algorithm is lower than BandEst, and the difference is statistically significant. Furthermore, the mean effectiveness with no admission control algorithm is lower compared to PABE and RABE, and the difference is statistically significant. The advantage in this case is that we do not have any control message overhead apart from the routing messages. If there are very few flows, we do not need any admission scheme as all flows can be accommodated. But that is unlikely to be the case, given the low bandwidth and shared nature of IEEE 802.15.4 networks. So most likely, the flows collectively would overwhelm the network, in which case the results here show that it pays off to pay the overhead. In a nutshell, BandEst demonstrates superior effectiveness because of the following: there is a low chance of falsely rejecting an admission request as the algorithm is designed to accurately account for all overheads.

Figure 7

Mean effectiveness comparison.

Tables 5 and 6 show the number of times different schemes make a wrong admission decision for 100 nodes and 150 nodes scenario, respectively. It can be seen that BandEst made fewer wrong decisions compared to other three schemes. Moreover, these results demonstrate that BandEst does not reject a single flow unnecessarily, whereas RABE and PABE do reject flows unnecessarily. Also, if we focus on only the wrong admission decisions, BandEst outperforms all other schemes as well. It was observed during the simulations that PABE and RABE unnecessarily reject flows which demand relatively higher bandwidth. This was more frequently observed when the data forwarding path is relatively short. We observed that in some cases incorrectly estimating higher intra-flow contention count by both flow admission control algorithms is mostly responsible for the wrong rejects. Figure 7 and Tables 5 and 6 show the results for two different network densities (either 100 nodes or 150 nodes in a 500 × 500 m² area), showing that the effectiveness of all protocols is relatively independent of the network density.

Table 5

Number of wrong admission decisions comparison (100 nodes).

Method	100 nodes
	Wrong accepts	Wrong rejects
BandEst	18	0
RABE	27	7
PABE	30	5
No admission control	58	0

Table 6

Number of wrong admission decisions comparison (150 nodes).

Method	150 nodes
	Wrong accepts	Wrong rejects
BandEst	22	0
RABE	28	9
PABE	31	6
No admission control	60	0

Figures 8 and 9 show mean admission response delay w.r.t. route length for cases when admission is granted. Admission response delay is simply measured by noting when the admission request message was sent and when the admission response was received. The average admission response delay for BandEst is higher compared to PABE and RABE. The average admission response delay for BandEst is high because it uses a distributed flow admission control method; that is, before accepting a flow's admission request, the BandEst flow admission control algorithm broadcasts the bandwidth increment message within the interference range of the node. This step is carried out to check whether all nodes within the interference range of the node can accommodate the new flow. As per the BandEst flow admission control algorithm, after broadcasting the bandwidth increment message, a node waits for a small amount of time, and if any node within the interference range of the node can not accommodate the flow, it unicasts an admission reject message to the originator of the bandwidth increment message. We performed some additional experiments and it was observed that after broadcasting the bandwidth increment message, a node typically receives an admission reject message (if required) within 400 ms. Therefore, the bandwidth increment message originating node waits for at least 400 ms before forwarding the admission request message. In our simulations, a node waits 500 ms before forwarding the admission request message. Figure 8 directly reflects this, with the admission response delay increasing by about 500 ms for each additional hop. Higher admission response delay associated with BandEst means that it is more suitable for admitting long-running real-time multimedia flows rather than short-lived real-time multimedia flows. Admission delay will probably decline with increased network density, as it is primarily a function of the route length. Using a shortest path routing protocol, the route length between any two nodes in a denser network is at most as long as the route length in a sparser network and potentially shorter (there is a higher chance of finding max length hops).

Figure 8

Route length versus mean admission request response delay (100 nodes scenario).

Figure 9

Route length versus mean admission request response delay (150 nodes scenario).

Figure 10 shows the comparison of the average network-wide control messages overhead. The control messages overheads were recorded during the simulations. The overhead associated with BandEst is only slightly higher than PABE and RABE. The additional overhead is primarily a function of the rate of flow admission requests. It impacts only the nodes on the route (and nodes within their 2-hop neighborhood) and is demonstrably small. The bulk of the control message overhead is determined by the periodically exchanged control packets such as HELLO messages in all three protocols. As such, the overall control message overhead will increase with network density.

Figure 10

Control messages overhead comparison.

6. Conclusion and Future Work

In this paper, we highlighted the factors that must be taken into account for a flow admission control algorithm in wireless ad hoc networks. Moreover, we presented BandEst, a novel available-bandwidth-based flow admission control algorithm for ad hoc IEEE 802.15.4-based networks that takes into account the identified factors. One of the main contributions of BandEst is that it proactively considers the complete IEEE 802.15.4's unslotted CSMA-CA MAC layer overhead considering the future data load. Other main contributions are as follows: novel algorithms for estimating intra-flow contention and estimating contention on non-relaying nodes, additional MAC layer overhead associated with an increased data traffic load on non-relaying nodes, and an algorithm that deals with concurrent admission requests in a first-come-first-served scheme. Simulation results have demonstrated that taking into account the highlighted factors results in an effective available-bandwidth-based flow admission control algorithm for ad hoc wireless networks. Moreover, BandEst shows significant improvements compared to the state-of-the-art available-bandwidth-based flow admission control algorithms. As all evaluated available-bandwidth-based flow admission control algorithms use control messages, the percentage of lost control messages may impact the performance of these algorithms. Hence, in the future we shall evaluate these algorithms’ performance using different values for the bit error rate. The work presented in this paper uses no duty cycling and considers that nodes are stationary. Therefore, in the future we shall extend our work by using different radio duty cycling algorithms to preserve energy; moreover, we shall consider mobility of nodes.