Keywords

1 Introduction

The ability of wireless sensor devices to capture multimedia content from the environment has gradually shifted the paradigm from existing scalar sensor services (light, temperature, etc.) to a new world of real-time audio-visual applications and thus evolution of wireless multimedia sensor networks (WMSNs) [1, 2]. The WMSN may consist of heterogeneous nodes with moderated capabilities. Such a network is called Heterogeneous WSN (HWSN). HWSN nodes may be heterogeneous in terms of energy, wireless links, hardware or security. This helps in limiting the WSN cost as instead of using a full sensor set on a node, heterogeneous nodes may be deployed at different locations depending on the application and criticality of situation [3]. Due to the additional requirements of HWSNs it is important to consider the impact of node’s heterogeneity in terms of energy, sensed data, and bandwidth requirement while designing routing algorithms for HWSNs so as to achieve optimal performance. This paper proposes an Ant based QoS routing protocol for HWSNs (AntQHSeN). The key feature of the protocol is its ability to meet diverse QoS requirements posed by different kinds of traffic generated by heterogeneous nodes thus maximizing network performance and its utilization. The routing decisions for control packets, scalar data packets and multimedia data packets are taken independently and in different manners satisfying their respective QoS requirements. Moreover, as some applications require minimum bandwidth support, which if not provided will make entire data useless, therefore, if minimum bandwidth requirement cannot be met for such applications, data should not be transmitted [4]. AntQHSeN addresses this issue by using admission control scheme. For all other applications which do not impose strict bandwidth constraints, the protocol determines the minimum bandwidth along the route from source to destination. Figure 18.1 shows the heterogeneous sensor network.

Fig. 18.1
figure 1

Heterogeneous wireless sensor network

Full size image

The remainder of the paper is organized as follows: Sect. 18.2 provides a brief review of some of the closely related works. The proposed protocol is described in Sect. 18.3. Then AntQHSeN is tested through a series of computer simulations presented in Sect. 18.4. Section 18.5 concludes the paper.

2 Related Work

The introduction of Wireless Multimedia Sensor Networks (WMSNs) has revolutionized the scope and applications of wireless sensor networks which require the delivery of multimedia content with a certain level of QoS. There has been a host of research works on QoS routing for WMSNs.

SPEED [5], a spatio-temporal, maintains a desired delivery speed across the network and provides soft real-time, end-to-end delay guarantees. MMSPEED [6] protocol is an integration of reinforcement learning based probabilistic multipath forwarding with soft real-time guarantee of SPEED. However, due to per packet route computation it consumes more energy and thus reduces network lifetime. A multi-path and multi-channel based QoS-aware protocol proposed by Hamid et al. [7] makes routing decision according to the dynamic adjustment of the required bandwidth and path-length-based proportional delay differentiation for real-time data. PEMuR [8] is an efficient protocol for video communication over WMSNs. It ensures low power consumption over all sensor nodes and high perceived video QoS by making a combined use of hierarchical routing and video packet scheduling models. SDRCS [9] provides soft real-time guarantees for event-based traffic in WSNs. It uses grouping approach to estimate end-to-end hop distance and to meet various application requirements. It performs distributed packet traversal speed estimation for traffic classification and admission control, and prioritized packet forwarding for local routing decisions. Sun et al. [10] proposed a new routing metric called Load Balanced Airtime with Energy Awareness (LBA-EA). EEQAR proposed by Lin et al. [11] adopts cellular topology to form the cluster structure and balances the energy consumption by structure movement resulting in enhanced performance.

Swarm intelligence techniques are also prominently used in solving routing issues in WSNs. An ant based protocol, ASAR [12] is aimed at periodically selecting QoS routing paths for each three types of services—event-driven service, data query service and stream query service. ACOLBR [13] is another hierarchical protocol which is based on the concept of constructing a minimum spanning tree rooted at the cluster-head for intra-cluster routing. ACOWMSN [14] for WMSN aims at finding an optimize path from source to sink node. Based on ant colony heuristics, it uses probabilistic approach to find next hop that can satisfy multiple QoS constraints. A notable related approach is AntSensNet [15], an ant-based multi-QoS routing protocol for multimedia sensor networks with heterogeneous nodes and proposes a biologically inspired clustering process. For providing QoS guarantee an ant, and mobile agent based protocol QR2A [16] extends the local as well as global pheromone deposition rules and updation rules of ant algorithm. The algorithm meets the QoS requirements and solves the problem of network load balancing effectively. BiO4SeL [17] is a distributed and autonomic ant-based routing protocol that aims to maximize sensor network lifetime. It uses battery power information to update the distributed routing tables as battery power is consumed. EEABR [18] is an improved version of the Ant based routing in WSN and is designed to extend the lifetime. However, EEABR is weak in terms of scalability and reliability as it lacks quality of service and increases excessive delay in packet delivery.

Based on above survey, is observed that the adaptive routing protocols are desirable for WSNs. Therefore, to meet the diverse requirements of HWSNs along with simplicity, it is desirable to have a multi-hop communication based protocol with a cross-layer support to select the best routes.

3 Ant Based QoS Routing Protocol for HWSNs

This section describes an Ant based QoS enabled routing protocol for Heterogeneous WSNs (AntQHSeN) with multifarious and inherently conflicting demands. The method is intended for networks with a single data sink. The network consists of multimedia sensor nodes, scalar nodes, and an access point. The multimedia nodes are capable of sensing multimedia data such as audio, video and photo. Scalar nodes are the nodes with simple sensing capabilities such as temperature sensor, humidity sensor etc., and the data gathered by these scalar nodes, hereinafter, is called scalar data.

AntQHSeN is a reactive routing protocol consisting of two operational phases—route discovery phase and route maintenance phase. The route discovery phase sets up paths when they are needed at the start of a session and no routing information for the destination node is available. Source node finds multiple paths to the destination by launching ant agents called Forward ants. These ants also carry the network information to be used for evaluating the quality of path such as available bandwidth and residual energy of the intermediate nodes lying on the path. Backward ants are then sent by the destination node to the source node, completing the reactive route setup phase. Once the routing path has been set, the source node starts sending data packets stochastically over different paths using pheromone values as well as a heuristic function taken together. Route maintenance phase starts when link failures are encountered.

AntQHSeN protocol considers residual bandwidth, minimum residual energy and route cost to compute the pheromone concentration. Residual bandwidth describes the bandwidth availability along the routing path and is a measure of residual channel capacity. If the source, demands for some minimum bandwidth, admission control scheme is used, else the minimum available bandwidth along the route is determined. In admission control scheme, if any node during route selection cannot satisfy the bandwidth constraints imposed by the source, the route selection procedure is terminated. Minimum residual energy identifies high energy paths and more pheromone is deposited along the path with high residual energy. Route cost is calculated in terms of end-to-end delay and hop count.

AntQHSeN uses Hello ants which are periodic messages and are used to find out immediate neighbor nodes and to detect link failures. Hello ant packet also contains the Bandwidth (b i ), Timestamp (T j ), Energy (e i ) and Pheromone (τ d i ) information. When a source node has no routing information for a destination node, it generates Reactive Forward ants and initiates reactive route discovery process. These ants keep record of all intermediate nodes visited by it in reaching from source to the destination node. The information passed and accumulated through the Reactive Forward ants is used by the destination node to compute the pheromone values to be deposited on the route. In addition to source address, destination address, and sequence numbers following fields are required for making QoS based routing decisions:

  • Flag (f)—indicates whether the source is using the admission control scheme or not.

  • Requested Bandwidth (b rq )—denotes the minimum bandwidth as desired by the source node. This field is significant only if the flag is set and every intermediate node from source to destination receiving the forward ant compares the available bandwidth with the value stored in this field.

  • Minimum Bandwidth (b min)—indicates the minimum of bandwidth available with the nodes from source to the current node and is a measure of maximum bandwidth supported by the route.

  • Route Energy (e min)—stores the minimum of residual battery capacity of nodes from the source to the current node along the path traversed by the Forward ant and is an indication of the route’s lifetime.

Each ant generated by source node s has a goal to determine a path to the destination d, which can satisfy given QoS requirements. Initially, when generated at source node, ant contains address of source node and that of destination node. On its way to the destination node, the ant keeps record of all the intermediate nodes visited by it. The source node broadcasts this FA to its neighboring nodes.

The intermediate node i when receives the ant, it first calculates its residual bandwidth b i . Depending upon the status of flag bit and its residual bandwidth, the node either forwards the ant or drops it. If the flag bit is set b i  > b rq , it forwards this FA. Otherwise, the node discards this ant. In case the flag bit is not set, the node compares its residual bandwidth with the minimum bandwidth field in the FA. If b i  < b rq , the node replaces minimum bandwidth value in the ant with residual bandwidth. Otherwise, the node simply forwards the ant packet. Similarly, node updates route energy field in ant packet by comparing its own residual battery capacity e i and value contained in the route energy e min field of the packet. If former is greater than the latter, ant packet is forwarded else route energy field of the packet is updated using its residual battery capacity. Node n i updates fields in the FA message as follows:

$$ b_{{\min }} = \left\{ {\begin{array}{*{20}l} {b_{{\min }} = \min (b_{{\min }} ,\,b_{i} ),} \hfill & {flag = 0} \hfill \\ {b_{{rq}} ,} \hfill & {flag = 1\,\& \,b_{i} \ge b_{{rq}} } \hfill \\ {drop,} \hfill & {otherwise} \hfill \\ \end{array} } \right.$$
(18.1)
$$ e_{\hbox{min} } = \hbox{min} (e_{\hbox{min} } ,e_{i} ) $$
(18.2)

Depending upon the availability of routing information for d, intermediate node either unicasts or broadcasts the ant packet. If routing information is available, the node makes probabilistic decision to select next hop for ant packet. The decision is based on the pheromone values associated with each next hop for d. The probability of selecting node n as next node by current node i is given as [19]:

$$ {P_{in}^{d} = \frac{{\left( {\tau_{in}^{d} } \right)^{{\beta_{ 1} }} }}{{\sum\limits_{{j \in N_{i}^{d} }} {\left( {\tau_{ij}^{d} } \right)^{{\beta_{1} }} } }},\quad \beta_{ 1} \ge 1 ,} $$
(18.3)

where

  • \( {\tau_{in}^{d} } \) is pheromone value for next node n

  • \( {N_{i}^{d} } \) is the set of neighbors of i over which path to d is known

  • \( {\beta_{ 1} } \) is a parameter that controls exploratory behavior of the ant.

If routing information for destination d is not available at the node, the node broadcasts the forward ant packet. The ant packet while traveling from source to destination collects status information of nodes along the route as per Eqs. (18.1) and (18.2). Therefore, when it reaches the destination, it has minimum bandwidth value that can be supported by the route and minimum energy of the route. This information is crucial in determining the quality of path in term of pheromone value.

On receiving a FA, destination node creates a BA. The status information of the route contained in FA is copied to BA in the following manner:

$$ \begin{aligned} r_{b} & = b_{\hbox{min} } \\ e_{b} & = e_{\hbox{min} } \\ \end{aligned} $$
(18.4)

The BA also contains the addresses of the forward ant’s source node s and destination node d, as well as the full list of nodes that the forward ant has visited. The BA is unicast from destination d to source s along the same path the FA had traveled but in reverse direction.

The BA updates pheromone value \( {\tau_{in}^{d} } \) in the table for destination d on each intermediate node i, till it reaches source node. Here n is the node that the ant visited before i on its way back from d. The pheromone value to be deposited on a node is determined by the route status information carried by the ant. It also considers hop count and delay in reaching the current node from the destination node. It is interesting to note here that rather than relying completely on global information as provided by Forward ant, AntQHSeN combines this global information with the estimates calculated locally by the nodes for pheromone computation. \( h_{in}^{d} \) is the hop count and \( t_{in}^{ d} \) is the delay incurred by a packet from d to i through n which is the node that the ant visited before i, t hop is the time needed to take one hop in unloaded conditions. This is in order to improve reliability and provide better approximation of the measured values. The amount of pheromone released by Backward ant is given by \( {\tau_{in}^{{d^{\prime}}} } \) as follows:

$$ \tau_{in}^{{d^{\prime}}} = \alpha_{r} \times (R) + \alpha_{e} \times (E) + \alpha_{t} \times (T),\quad 0 \le \alpha_{r} ,\alpha_{e} ,\alpha_{t} \le 1 $$
(18.5)

where

  • \( R = \frac{{r_{b} }}{{BW_{channel} }}, \)

  • \( E = e_{b} , \) and

  • \( T = \left( {\frac{{t_{in}^{d} + h_{in}^{d} \times t_{hop} }}{2}} \right)^{- 1} . \)

BW channel is bandwidth of wireless channel. Due to local burst of traffic or any other reason there may be large variations in time estimates gathered by the ants. To take into account these large oscillations, instead of considering time estimates gathered by the ants only, the average of estimated time and time under ideal circumstances has been taken. By doing so it also takes into account both end-to-end delay and number of hops. \( {\alpha_{r} ,\alpha_{e} } \), and \( \alpha_{t} \) are weight factors of rate, energy and time respectively, and their values can be set as per QoS requirements. We can set value of \( \alpha_{r} \) to minimum if the application is bandwidth insensitive, otherwise, higher value can be set and similar consideration can be made while choosing values for other weight factors.

The pheromone value \( {\tau_{in}^{d} } \) in node i is updated as follows:

$$ \tau_{in}^{d} = \gamma \;\tau_{in}^{{d^{\prime}}} \; + (1 - \gamma )\;\tau_{in}^{d} ,\quad 0 \le \gamma \le 1 $$
(18.6)

This updated pheromone value is diffused in the network by Hello ants. The source node starts data forwarding on receiving the Backward ant. Till that period the data packets are buffered in the source node. If no Backward ant is received within some stipulated interval, source node restarts the reactive path setup phase. However, if source node does not receive any Backward ant even after maximum number of retries, the source node discards the buffered data.

During the reactive path setup phase multiple paths are created between the source and destination pair. The algorithm does not determine a single better path out of available multiple paths for data transmission, rather data is forwarded stochastically. At each node there can be multiple next nodes for destination d and every intermediate node takes an independent decision to select next hop for data packet forwarding. The probability of selecting next hop for data forwarding is determined on the basis of pheromone value deposited on each node for destination d and the heuristic function. The probabilistic rule to determine the probability of moving from node i to node j for destination d is given as:

$$ P_{in}^{d} = \frac{{\left( {\tau_{in}^{d} } \right)^{\alpha } \left( {\eta_{in}^{d} } \right)^{\beta } }}{{\sum\nolimits_{{j\; \in \;N_{i}^{d} }} {\left( {\tau_{ij}^{d} } \right)^{\alpha } \left( {\eta_{ij}^{d} } \right)^{\beta } } }},\quad \alpha ,\beta \ge 1 $$
(18.7)

\( {\eta_{ij}^{h} } \) is the heuristic evaluation function. \( \alpha \) and \( \beta \) are parameters that control the relative weight of the pheromone trail and heuristic value respectively. Pheromone value is an indication of global information, whereas, heuristic value is based on local status information. Therefore, both local as well as global status information contribute towards next hop selection.

As different applications pose different QoS requirements, therefore performing application specific data forwarding as per the QoS requirements is a major contribution of the paper. Here, we assume a heterogeneous WSN, in which we have multimedia nodes for sensing multimedia data and scalar nodes for sensing scalar data.

Multimedia traffic does not require 100 % reliability; rather it poses more strict requirements on minimum bandwidth, energy efficiency and bounded delay. Although, the pheromone value deposited on the nodes reflect global estimation of all these three factors, however, it is important to rely on local bandwidth estimation before making data forwarding decisions. High pheromone value does not necessarily account for high residual bandwidth, as it may be due to high energy or low delay. A low bandwidth link for multimedia data transmission can lead to high packet drop rate, thus resulting in frequent re-transmissions. To resolve this challenge, the proposed protocol gives due weightage to residual bandwidth of neighboring nodes along with value of deposited pheromone during data forwarding. Figure 18.3 shows the forwarding of data packets through high and low bandwidth paths as per their QoS requirements.

When a data packet is received by a source node or an intermediate node and routing path is available for destination d, the node first checks the type of received data packet. If it is multimedia data packet, the probability \( P_{ij}^{d} \) of selecting next node j is given as:

$$ {P_{ij}^{d} = \frac{{\left( {\tau_{ij}^{d} } \right)^{\alpha } \left( {b_{j} } \right)^{\beta } }}{{\sum\limits_{{k\; \in \;N_{i}^{d} }} {\left( {\tau_{ik}^{d} } \right)^{\alpha } \left( {b_{k} } \right)^{\beta \quad } } }},\quad \alpha ,\beta \ge 1} $$
(18.8)

where b j heuristic evaluation factor in considering j as next hop for destination d for multimedia data and is a measure of residual bandwidth of neighbor node j. The pheromone and heuristic value are controlled by \( \alpha \) and \( \beta \) respectively. High value for \( \beta \) makes the algorithm greedy with respect to high bandwidth paths.

In heterogeneous WSNs, when both multimedia nodes and scalar nodes are sensing and transmitting data, scalar nodes should be more conservative in terms of energy while forwarding data. In the existing situation, where multimedia streams require high bandwidth routes, it becomes important to select high energy nodes for scalar data routing and hence enhance network lifetime. Considering this point of view, the proposed protocol takes residual energy of neighboring nodes into account while selecting next hop for data forwarding.

When a node receives scalar data for which routing information is available, the node chooses next hop with probability \( {P_{ij}^{d} } \) as:

$$ {P_{ij}^{d} = \frac{{\left( {\tau_{ij}^{d} } \right)^{\alpha } \left( {e_{j} } \right)^{\beta } }}{{\sum\limits_{{k\; \in \;N_{i}^{d} }} {\left( {\tau_{ik}^{d} } \right)^{\alpha } \left( {e_{k} } \right)^{\beta } } }},\quad \alpha ,\beta \ge 1} $$
(18.9)

where e j is residual energy of neighbor node j and is heuristic evaluation factor in considering j as next hop for destination d for general data. Similar to Eq. 18.8. \( \alpha \) and \( \beta \) control pheromone and heuristic value respectively. The protocol selects routes with higher residual energy with high \( \beta \) value.

Contrary, to conventional routing protocols in which a single best path is selected by source for data forwarding, the probabilistic routing strategy leads to automatic data load spreading according to the estimated quality of the paths. The protocol continuously senses the network status and adapts data traffic as per the QoS requirements and prevailing network conditions leading to enhanced performance.

4 Performance Evaluation

We use Mannasim [20] and Network Simulator ns-2.34 [21] to evaluate the performance and efficiency of AntQHSeN. We have considered two types of nodes scalars (S-sensor) and multimedia (M-sensor). Multimedia nodes have more energy and longer transmission range, than, the scalar nodes. But, at the same time they consume more energy in processing of multimedia data and its transmission. The radio range of scalar nodes spans 15 m while that of multimedia nodes spans up to 100 m. The data rate equals 1 Mbit/s. Each simulation run lasts for 600 s, and each result is averaged over five random network topologies.

Figure 18.2 shows the packet delivery fraction (PDF) of AODV, EEABR and AntQHSeN. We find that the PDF of AntQHSeN is significantly higher compared with AODV and EEABR. At the beginning, AntQHSeN lacks sufficient information in order to find appropriate routes, but after a certain period of time, when the algorithm converges and the ants have gathered much node and route information, the algorithm routes packets as per their desired QoS constraints and thus the quality of routes discovered for the AntQHSeN is superior to those found by AODV. The other important observation is that EEABR does not provide a consistent performance. The inconsistent behavior of EEABR is due to its proactive route discovery mechanism. As the number of control packets increase in the network, congestion occurs and collisions increase. As a result, forward ants start losing their way to the sink node and probability values do not stabilize which leads to the loss of data packets.

Fig. 18.2
figure 2

Packet delivery fraction versus simulation time

Full size image

In Fig. 18.3 the average end-to-end (EED) comparison between the protocols is depicted. Despite the fact that AODV selects shortest routing path, AntQHSeN protocol has considerably lower average EED than AODV. This is due to the discovery of multiple paths during route establishment, therefore, when a path to the destination breaks, packets could immediately continue to be forwarded using another paths without a new route discovery process. EEABR has approximately same average EED delay as that of AODV.

Fig. 18.3
figure 3

End-to-end delay versus simulation time

Full size image

Routing overhead is shown in Fig. 18.4. Both AODV and AntQHSeN are reactive protocols, but, in AntQHSeN the size of control packets is larger than that of AODV due to extra control information required for network status information. Moreover, contrary to AODV in which any intermediate node having route to the destination can reply to the source node, in AntQHSeN only destination node can send backward ant which leads to extra overhead. Although, in AODV all nodes try to find the shortest path which may lead to congestion resulting in packet drops and re-transmissions still AntQHSeN has higher routing overhead than AODV due to reasons cited above. Extra forward and backward ants required to maintain proactive paths in EEABR leads to still higher routing overheads in EEABR.

Fig. 18.4
figure 4

Normalized routing overhead versus simulation time

Full size image

5 Conclusion

The pace of technological growth has led to the proliferation of multimedia sensor nodes and thus multiplicative enhancement in application areas of WSNs. Multimedia sensors as well as scalar sensors can be deployed in a region to monitor environmental data as well as to detect intrusion. Hence the application layer data can be categorized as scalar and multimedia with diverse QoS requirements. Given such motivation this paper proposes an ant based QoS routing protocol for heterogeneous WSNs—AntQHSeN. The routing algorithm categorizes entire traffic into routing traffic and data traffic. Data traffic is further categorized into multimedia traffic and scalar traffic. The routing decision is taken on the basis of traffic type as well as QoS constraints posed by that traffic. This paper proposes three different methods to handle three different types of data i.e. routing, multimedia and scalar data, thus improving network performance. Simulation results show that the performance of AntQHSeN outperforms the standard AODV and EEABR in terms of packet delivery fraction, end-to-end delay and routing overhead.