QoS Enabled Probabilistic Routing for Heterogeneous Wireless Sensor Networks

Published Online April 2013 in MECS

The ever increasing demand for ubiquitous computing environment has led to the deployment of Wireless Multimedia Sensor Networks (WMSN) [1] at a very fast pace. WMSNs are composed of sensor devices that retrieve multimedia data and cooperate with each other to collect, aggregate and forward the sensed data from a certain region via multiple hops or directly to a certain point in the network where the data can be analyzed and evaluated. A combination of multimedia sensors and scalar sensors can be deployed in a region to monitor environmental data as well as to detect intrusion. Such a network consisting of nodes that are heterogeneous in terms of energy, wireless links, hardware or security is called Heterogeneous Wireless Sensor Network (HWSN) [2]. 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 thus limiting the WSN cost. Heterogeneous nodes, in a HWSN, sense and report data at different rates with diverse QoS constraints. Although, the content-rich information as obtained through HWSN is effective but the intrinsic features of multimedia communication and heterogeneous nature of nodes, simultaneously, pose additional challenges like high bandwidth requirements, application-specific QoS requirements, and power consumption [3,4]. Hence, in order to achieve optimal performance in HWSN it is important to consider the parameters of node heterogeneity while designing routing algorithms for HWSNs.

Multimedia node

Figure. 1: HWSN Architecture

In this paper we propose an Ant Colony Optimization (ACO) [5] based routing algorithm for HWSNs. The proposed protocol tends to satisfy QoS requirements as posed by heterogeneous nodes while determining routing paths. The routing protocol reacts differently to different types of packets received by a node. The routing decision for a control packet is based on pheromone value only whereas for data packets it also considers heuristic function. Multimedia traffic is handled differently, whereas scalar data is dealt in a different manner due to their diverse QoS needs.

Rest of the paper is organized as follows: Section II provides a brief review of some of the closely related works. The proposed protocol is described in section III. The protocol is tested through a series of computer simulations and the results and discussions are presented in section IV. Section V concludes the paper.

• II.    RELATED WORK

The availability of low cost and miniature size multimedia devices has led to a tremendous growth in the development and deployment of HWSNs. It is desirable to extract more realistic and precise information of the fast changing events in domains like military, disaster relief and rescue, security surveillance, health care, traffic, industrial, environmental, and household monitoring [6]. Due to this growth in potential use of HWSNs, a lot of research is being focused on providing QoS. SPEED [7] a spatio-temporal, priority-based, QoS-aware routing protocol for WSNs supports real time traffic with delay requirements and maintains a desired delivery speed across the network. Multipath Multi-Speed (MMSPEED) [8] protocol is an integration of reinforcement learning based probabilistic multipath forwarding with soft realtime guarantee of SPEED which supports timeliness by ensuring bandwidth and real-time transmission constraints using SPEED and enhances data transmission reliability by probabilistic multipath forwarding.

Hamid et al. [9] proposed a multi-path and multichannel based QoS-aware protocol. The routing decision is made according to the dynamic adjustment of the required bandwidth and path-length-based proportional delay differentiation for real-time data. Power Efficient Multimedia Routing (PEMuR) [10] 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.

Energy Efficiency QoS Assurance Routing in Wireless Multimedia Sensor Networks (EEQAR) [11] tries to establish a similarity between social network and wireless multimedia sensor network and optimizes network performance on the basis of analysis. Energy-Efficient and QoS-based Multipath Routing Protocol (EQSR) [12] protocol applies a service differentiation technique and is designed to satisfy the reliability and delay requirements of real-time applications.

Keeping in view the limitations of table-based real-time routing techniques in WSNs Xue et al. proposed a service differentiated real-time communication scheme (SDRCS) [13] to provide soft real-time guarantees for event-based traffic in WSNs. SDRCS uses grouping approach to estimate end-to-end hop distance and to meet various application requirements. W. Sun et al. proposed a new routing metric called Load Balanced Airtime with Energy Awareness (LBA-EA) [14]. It addresses load balance and energy awareness in WMSNs. The metric selects the less congested route and balances traffic loads among nodes by taking in to account the traffic load of forwarding nodes as well as the inter-flow interference caused by contending neighbors.

Ant-based Service Aware Routing (ASAR) [15] a hierarchical routing protocol is aimed at periodically selecting QoS routing paths for each three types of services - event-driven service, data query service and stream query service. Keeping in view the issues in WSNs, J. Bi et al. proposed an ant colony optimization based Load Balancing Routing Algorithm for WMSNs (ACOLBR) [16]. It is a hierarchical protocol which is based on the concept of constructing a minimum spanning tree rooted at the cluster-head for intra-cluster routing. Another ant based algorithm is ACOWMSN - Ant Colony

Optimization based QoS routing algorithm for Wireless Multimedia Sensor Networks [17] which aims at finding an optimize path from source to sink node. A notable related approach is AntSensNet [18], an ant-based multiQoS routing protocol for multimedia sensor networks with heterogeneous nodes and proposes a biologically inspired clustering process. AntSensNet classifies traffic to differentiate network data flows and to treat each flow as per its desired QoS requirements.

An agent-assisted QoS-based routing algorithm for wireless sensor networks proposed by M. Liu is an agent-assisted QoS-based routing algorithm for wireless sensor networks [19]. It uses intelligent software agents to participate in taking routing decisions and route maintenance by consistently monitoring changes in the network state such as topology, communication flow and node's routing state. A comparative analysis of these protocols is given in Table 1.

Based on above survey is observed that the routing protocols that are adaptive in nature are desirable for WSNs because of their properties and key constraints. In case of multimedia sensor networks, the protocol should provide QoS support along with energy efficiency. Moreover, if the network consists of heterogeneous nodes with varied applications then the protocol should be intelligent enough to identify various traffic types and their respective QoS requirements. Therefore, to meet these diverse requirements along with simplicity it is desirable to have a multi-hop communication based protocol with a cross-layer support to select the best routes.

Table 1: Comparative study of WMSN routing protocols

Routing Protocol	Architecture	Location Aware	Multipath	Energy Efficient
SPEED [7]	Flat	Yes	No	No
MMSPEED [8]	Flat	Yes	Yes	No
Hamid etal. [9]	Flat	No	Yes	No
PEMuR[10]	Hierarchical	No	No	Yes
EEQAR[11]	Hierarchical	Yes	No	Yes
EQSR[12]	Flat	No	Yes	Yes
SDRCS [13]	Hat	No	No	Yes
LBA-EA[14]	Flat	No	No	Yes
ASAR[15]	Hierarchical	No	Yes	Yes
ACOLBR[16]	Hierarchical	No	Yes	Yes
ACOWMSN [17]	Flat	No	Yes	Yes
AntSensNet [18]	Hierarchical	No	Yes	Yes
M. Liu [19]	Hat	No	Yes	Yes

• III.    QoS ENABLED PROBABILISTIC ROUTING ALGORITHM FOR HWSN

To address the routing challenges faced by HWSNs many biologically-inspired intelligent algorithms have been designed and deployed. ACO is one of the most successful biologically-inspired algorithms and refers to finding solution by mimicking real ants’ movement in the problem space. The ants leave the trail by releasing a chemical called pheromone and future ants use that chemical to find better solutions. The system uses positive and negative feedback in terms of pheromone deposition and pheromone evaporation respectively. Artificial ants used in algorithms continuously explore different paths, and pheromone trails and provide network status information. This information is further used to determine optimal routes. Ants also help in maintaining backup routes.

This section presents an ACO based distributed routing algorithm for QoS provisioning in HWSNs. It considers heterogeneous characteristics of nodes with multifarious and inherently conflicting demands and achieves better adaptability and better packet delivery than contemporary solutions.

• A.    Motivation

The proposed algorithm has been designed with the following motivations:

• •    In HWSNs, the network nodes have different priorities based on their, functionality, participation need, energy level etc. and hence QoS routing protocol needs weighted fairness among performance metrics so as to improve overall efficiency of the network.

• •    With the increase in network size, routing in HWSNs also becomes more challenging and critical. ACO based algorithms can provide better solutions under these circumstances.

• •    Since the network characteristics and the number of nodes participating in data communication varies with time, therefore, the ACO based path determination algorithm should consider these factors. Moreover, the algorithm should be adaptive in nature w.r.t. network statistics.

• •    ACO based routing protocol needs to support the QoS in terms of throughput, latency, and energy efficiency.

Based on above assumptions, the proposed protocol utilizes the pheromone based ACO approach to determine QoS aware paths. The paths are optimal in terms of bandwidth for transmission of multimedia data and for transmission of scalar data the paths are optimal in terms of energy. Although as per ACO technique the increase in the pheromone content of a path over a period of time leads to more number of packets using the same path hence leading to congestion, however, the proposed algorithm uses network statistics such as bandwidth, delay, energy and hop count, thus determining multiple paths with different pheromone concentrations for different types of packets.

• B.    Assumptions

The protocol is based on the following assumptions:

• •    There is a single immobile sink node.

• •    Sink node has enhanced communication and computation capabilities and has no energy constraints.

• •    Network consists of two types of sensor nodes: multimedia sensors (M-sensors) and scalar sensors (S-sensors).

• •    M-sensors are capable of sensing audio/video in the sensing region and S-sensors capture data such as temperature, light or pressure.

• •    Both types of nodes are scattered randomly in a twodimensional rectangular region and are mobile.

• •    The radio transmission range and the battery capacity of both types of nodes i.e. M-sensors and S-sensors is different and both values are higher for M-sensors.

• C.    Network Model

A heterogeneous network model assumed in this work can be expressed as a connected, undirected and weighted graph G(V, E) , where V = {v0, v1, v2,..........vn } is a set of n +1 sensor nodes including M multimedia nodes, S scalar nodes and an access point A . 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. If access point is not within transmission range of the node, the node uses multi hop routing to relay data otherwise, single hop routing is used. E is a set of edges. An edge denotes a link between vertices. Each edge e = (v., V)) e E denotes that v4 and Vj are the mutual adjacent nodes and they discover each other by exchanging Hello ants. Each graph node v in V , maintains a pheromone table containing neighbor information such as pheromone value τ d required to reach a destination d via neighbor v . Each node also maintains a neighbor table in which QoS metrics elements {BW(v), RE(v)} are stored. Where BW(Vj) indicates the bandwidth available with the node v and

RE (v ) indicates the normalized remaining energy of the node v defined as the ratio of residual energy to initial energy of the node.

BW(P) = min (BW(v))    (1)

vn ^e P

RE (P) = min (RE (vn ))     (2)

^vn ^{e P}

Hop ( P) = 2 h ( n )          (3)

The destination node on receiving the above QoS metric values computes the amount of pheromone to be deposited on the nodes.

• D.    Protocol Description

In the proposed routing protocol an ant associates a specific pheromone scent with each node in the network. Similar to the biological ants that are biased to move towards the food source, the packets moving through the network are biased to move in the direction of the pheromone gradient of the destination node. To select a QoS aware route from source node to the access point, there is a need to exchange information about the candidate paths. This information exchange is facilitated by Hello Ants, Forward Ants and Backward ants. Hello ants are the short messages broadcast by all the nodes at every t     interval. Hello ants are used for neighbor discovery, link failure detection and pheromone diffusion.

A source node s broadcasts forward ants (FA) , whenever routing information for destination node d is not available. Each ant generated by source node s has a goal to determine QoS aware path to the destination d . At the time of generation at source node, FA 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. At each intermediate node the ant is either unicast or broadcast depending on whether the routing information for d is available or not. Every intermediate node on receiving the ant packet updates the residual     bandwidth     field     of     FA     as bmin = min( bmin , bi) , route energy fields of FA as e™n = min( e™n , e,), where b. and e. are residual min          min i            i       i bandwidth and residual energy of node v respectively. If routing information for destination d is not available at the node, the node broadcasts the FA . The ant packet while traveling from source to destination collects status information of nodes along the route. Therefore, when it reaches the destination it has minimum bandwidth value supported by the route and minimum energy of the route. However, if routing information is available at the intermediate node, the node makes probabilistic decision to select next hop for the ant packet. The decision is based on the pheromone values associated with each next hop for destination d . The probability of selecting node v as next node by current node v is given as [20]:

τ ( i^dn ) ^{β 1}

∑ ( τ i^dj ) ^{β 1 ,} ∈ N i ^d

β 1 ≥ 1,     ..     (4)

Where τ^d is pheromone value for next node v_n . N^d is the set of neighbors of v over which path to d is known and β is a parameter that controls exploratory behavior of the ant.

Every FA received at the destination node is converted to the backward ant ( BA ) . The destination node computes the contribution of global information in pheromone deposition and stores it in BA and is given as:

τ _g ^d = α _r × ( R ) + α _e × ( E ) + α _h × ( H ),  0 ≤ α _r , α _e , α _h ≤ 1 (5)

where R =    ^{b min}    ,

BW channel

E = emin and H is the hop count from s to d . The amount of pheromone released by backward ant at vt for next node v to d is given by τ d as follows:

τ _i ^d _n = τ _g ^d + α _T × ( T )                  (6)

T is the delay encountered by BA in reaching v via v from d .

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. BA is unicast from destination d to source s along the same path as FA had traveled but in reverse direction. , α , α and α are weight factors of rate, energy and time respectively and their values can be set as per QoS requirements.

The pheromone value τⁱ in node v is updated as follows:

τ _i ^d _n = γτ _i ^d _n + (1 - γ ) τ _i ^d _n  ,  0 ≤ γ ≤ 1  ...........(7)

The updated pheromone values are diffused in the network by Hello ants. The source node starts data forwarding on receiving the BA . Till that period, the data packets are buffered in the source node. If the source node does not receive BA for some stipulated interval, source node restarts reactive path setup phase. However, even after a maximum number of retries BA is not received, the source node discards the buffered data.

The ant colony routing is based on the concept of reinforcement learning, in which positive feedback is given to the system in terms of pheromone deposition and negative feedback in terms of pheromone evaporation. Pheromone evaporation refers to the decrease in pheromone values. Pheromone deposition reinforces good solutions whereas pheromone evaporation allows forgetting old solutions. Pheromone evaporation takes place on all nodes of the network periodically using the following equation:

τ _i ^d _j = (1 - ρ ) × τ _i ^d _j ,   ∀ ( v _i , v _j ) ∈ E ..............(8)

Where ρ is the pheromone evaporation rate and 0 ≤ ρ ≤ 1 .

Multiple paths are created between the source and destination pair during route setup phase and data is forwarded stochastically. 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. 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.

Figure. 2: Forwarding of FA and BA

Multimedia traffic poses strict bandwidth requirements. Therefore, for multimedia data packet, the probability P ( m ) ^d of selecting next node j is given as:

PW j

a VM А т-k )а (ьк )в, к е Ni а , в > 1 (9)

Where b _j is heuristic evaluation factor in considering v_j as next hop for destination d for forwarding multimedia data and is a measure of residual bandwidth of neighbor node v_j . The pheromone and heuristic values are controlled by α and β respectively.

The proposed protocol takes residual energy of neighboring nodes into account while selecting next hop for scalar data forwarding, therefore, when a node receives scalar data for which routing information is available, the node chooses next hop with probability P(s)d as:

Р у . У в > 1(10)

А ( т ik )   (ek )

к е N i

Where e is residual energy of neighbor node v j and is a heuristic evaluation factor in considering v j as next hop for destination d for general data. Similar to eq. 9 α and β control pheromone and heuristic value respectively. The protocol selects routes with higher residual energy with high β value. 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.

• IV.    SIMULATION RESULTS AND SIMULATION

• 4.1    Evaluation metrics

This section describes the evaluation metrics and simulation scenarios.

Packet delivery fraction (PDF): It is the ratio of total number of packets received at the destination, or access point in this case, to the total number of events generated by all the source nodes in the network. It reflects the degree of reliability of a routing protocol.

Average end-to-end delay (EED): This is the average overall delay for a packet to traverse from a source node to a destination node. This includes the route discovery time, the queuing delay at a node, the transmission delay at the MAC layer, and the propagation and transfer time in the wireless channel. As delay primarily depends on optimality of path chosen, therefore, this is a good metric for comparing the efficiency of underlying routing algorithms.

Jitter: It is defined as the delay variation between each received data packets.

Normalized Routing Load (NRL): It is defined as the number of routing control packets per data packet delivered at the destination.

% Packets Lost (PPL): It is defined as the percentage of packets lost during transmission.

Figure. 3: Data packet forwarding

The simulation scenario is created in NS-2.34 [21]

using Mannasim [22]. We consider a network of 50 scalar sensors (S-sensors) and 25 multimedia sensors (M-sensors) that move with a maximum speed of 10m/s in a rectangular area of 600 × 600 m2. RWP mobility model [23] has been used to define node movements. Each experiment runs for a duration of 900s, and each result is averaged over 5 random network topologies. Multimedia nodes have more energy and longer transmission range than the scalar nodes. But, at the same time they consume more energy in processing multimedia data. The radio range of scalar nodes spans 30 m while that of multimedia nodes spans upto 100 m. At the physical layer, we use the IEEE 802.11 protocol, with data transmission rate of 2M bit/s. Here, we investigate the effect of varying the number of source nodes. We do tests using 8 to 37 source nodes in the simulation scenario, using as intermediate values 12, 15, 18, 21, 25 and 30 sources. Two traffic classes are produced by the nodes: multimedia traffic with a size of 1024-byte packet and data rate of 1 packet per second by M-sensors and scalar traffic of packet size 32-byte at the rate of 4 packets per second by S-sensors.

In terms of delivery ratio, the effect of increasing traffic load is obvious: all algorithms have a monotonously decreasing performance as shown in Fig. 4. Simulation results reveal that the proposed algorithms achieve a larger packet delivery ratio compared to AODV protocol, especially when the traffic load is high. This is because the proposed scheme chooses QoS aware path instead of shortest path chosen by AODV for data transmission, which indirectly increases the overall network throughput. On the other hand, AODV protocol without unaware of the network status information suffers high probability of route failure and data retransmission as network traffic load increases.

Fig. 5 shows normalized routing load of both protocols. Both AODV and the proposed protocol are reactive protocols, but, in case of the proposed protocol contrary to AODV in which any intermediate node having route to the destination can reply to the source node, 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 proposed protocol has higher routing overhead than AODV due to reasons cited above.

Figure. 4: PDF vs. number of source nodes

Figure. 5: NRL vs. number of source nodes

Figure. 7: Jitter vs. number of source nodes

As can be seen in Fig. 6, the proposed load balancing scheme performs better than ADOV in terms of average end-to-end delay. Even though the routing path may be longer than that of AODV protocol, proposed scheme tries to route packets along a path that satisfies QoS requirements such as high bandwidth and low delay paths. We can see from the Fig. that the end-to-end delay increases for the protocols with increase in load. This can be explained by the fact that, due to increased contention at the MAC layer, the packets now have to wait in the interface for longer time before being transmitted. Here, AODV suffers the maximum delay as it often routes the packets around heavily loaded nodes. Proposed protocol makes a better choice than AODV.

Fig. 7 depicts the results for delay variation of received packets (jitter) versus number of source nodes. Similar to the results for end-to-end delay it can be seen that jitter is considerably lower for proposed algorithm than AODV for highly loaded networks. This behavior is as anticipated because delays mainly occur in queuing and medium access control processing.

Figure. 6: EED vs. number of source nodes

Fig. 8 shows the packet loss rate for AODV and the proposed protocol. When the traffic is heavy, more users are active; QoS based routing mechanisms result in lesser number of packets lost.

Figure. 8: PPL vs. number of source nodes

• V.    CONCLUSION

To provide QoS guarantees over the heterogeneous network architecture, this paper proposes a new routing protocol based on ant algorithm. In HWSN both multimedia as well as scalar sensors can be deployed in a region to monitor environmental data and to detect intrusion simultaneously. The application layer data can be categorized as scalar and multimedia with diverse QoS requirements. In the proposed protocol the local pheromone updation rule, the global pheromone updation rule and the state transition rules in ant algorithm are extended to combine ants’ pheromone with the QoS requirements of the network traffic. Entire traffic is classified in to routing traffic and data traffic. Data traffic is further categorized into multimedia traffic and scalar traffic and the routing decision is based on its QoS requirements thus achieving performance improvement. Simulation results show that the performance of the proposed protocol outperforms the standard AODV in terms of packet delivery fraction, end-to-end delay and jitter for HWSN with dynamic topology.