Performance Analysis of the CAPB Broadcasting Scheme in Low-rate WSN

KEYWORDS

Low Rate Wireless Sensor Network,IEEE 802.15.4 MAC, Route Discovery, Channel Adaptive Probabilistic Broadcast, Broadcast Storm Problem, Probabilistic scheme.

ABSTRACT

Low Rate Wireless Sensor Networks (LR-WSNs) has become an active research area in the past few years. Broadcasting is the backbone of the route discovery process in on-demand unicast routing protocols in  LR-WSNs. Pure flooding is the simplest and most common broadcasting technique for route discovery in on-demand routing protocols. In pure flooding, the route request (RREQ) packet is broadcasted and each receiving node rebroadcasts it. This continues until the RREQ packet arrives at the destination node. The obvious drawback of pure flooding is excessive redundant traffic that degrades the system performance. This is commonly known as broadcast storm problem (BSP). Several schemes have been proposed to address BSP, one of them of them is the Channel Adaptive Probabilistic Broadcast (CAPB) scheme that adapts the rebroadcast probability dynamically to the current Signal to Interference plus Noise Ratio(SINR) and node density in the neighbourhood. This paper evaluates the CAPB scheme in  LR-WSN  based on the IEEE 802.15.4/ZigBee. The CAPB scheme is implemented in the standard AODV routing protocol to replace the pure flooding based broadcast. Extensive ns-2 simulation results show that the CAPB scheme outperforms the standard AODV and the fixed probablisitic scheme, in terms of routing overhead, throughput, end-to-end delay and energy consumption significantly in noisy LR-WSNs.

INTRODUCTION

The proliferation of applications based on IEEE 802.15.4/Zigbee (like monitoring physical or environmental conditions, such as temperature, sound, vibration and etc) have kept LR-WSN an active area of research over the past two decades. A LR-WSN is a self-configuring, self-healing and infrastructure-less network of mobile nodes connected to each other over single-hop or multi-hop wireless links on ad-hoc basis (Chen et al. 2008). More details about the IEEE 802.15.4/Zigbee can be found in  IEEE802.15.4 2006.

These characteristics of mobile LR-WSNs make them an ideal choice for a number of applications e.g., communications in battlefield, rescue operation in disaster areas or quick deployment of networks without requiring huge infrastructure.

In mobile LR-WSN nodes can be located arbitrarily within an area and are free to move. The movement of LR-WSN nodes changes the network topology dynamically. Mobile LR-WSN nodes adapt to the changing topology by discovering new neighbours and establishing new routes to destination nodes (Yick et al. 2008). A node may not communicate directly with a distant node due to limited transmission range, and may have to rely on other nodes to relay the message along the route to the final destination node. In this way, each node acts as a host node as well as a relay node to extend the reachability of other nodes.

When a node wants to send data to a remote node, first, it finds out a set of relay nodes between itself and the remote node. The process of finding the optimal set of relay nodes between the source node and the destination node is called route discovery. Node mobility, limited battery power and the error-prone nature of wireless links are the main challenges in designing an efficient rout discovery process in LR-WSNs.

A number of routing protocols have been proposed in the literature (Boukerche et al. 2011 and Kulkarni et al. 2011). These protocols generally fall into three categories namely table-driven (proactive), on-demand (reactive) and hybrid routing protocols. Interested reader can find a survey in (Boukerche et al. 2011).

In on-demand routing protocols, the routing process consists of two phases namely route-discovery and route-maintenance. These protocols rely on broadcasting for route discovery. For example, in case of AODV routing protocol, a source node that needs to send data to a destination node triggers route discovery mechanism by broadcasting a special control packet, called Route Request (RREQ), to its neighbours who then rebroadcast the RREQ packet to their neighbours. The process continues until the RREQ packet arrives at the destination node. The destination node sends a control packet called Route Reply (RREP) that follows the path of RREQ in reverse direction and informs the source node that a route has been established. Since every node on receiving the RREQ for the first time rebroadcasts it, it requires T-2 rebroadcasts in a network of T nodes assuming the destination is reachable. This kind of broadcasting is called pure flooding and is depicted briefly in Figure 1 while details can be found in (Lee et al. 2002).

Figure 1: Route discovery mechanism in AODV

Pure flooding often results in substantial redundant transmissions because a node may receive the same packet from multiple other nodes. This phenomenon, commonly known as the broadcast storm problem (BSP) (Adarbah et al. 2015 and Ni et al. 2002). causes frequent contention and packet collisions leading to increased communication overhead and serious performance complications in densely populated WSNs. BSP equally affects the route maintenance phase during which routes are refreshed by triggering new route discovery requests to replace the broken routes. To address the BSP the Channel Adaptive Probabilistic Broadcasting (CAPB) scheme that adapts the probability of rebroadcasting RREQ packets dynamically according to the thermal noise, co-channel interference and node density in the neighbourhood has been rescently deployed (Adarbah et al. 2015).

This paper evaluate the performance of the CAPB in LR-WSN based on IEEE802.15.4/Zigbee . The CAPB scheme is implemented in the network simulator ns-2 and its performance has been compared with SoA schemes in terms of routing overhead, throughput, end-to-end delay and energy consumption. Simulation results showed that the proposed scheme outperforms the SoA broadcast scheme significantly.

The rest of the paper is organized as follows: Section 2 presents the related work, Section 3 presents the CAPB broadcast scheme, and Section 4 presents simulation results and analysis followed by conclusions in Section 5.

 

RELATED WORK

 

There are servel studies for addressing the performance evaluation of routing protocls over IEEE 802.15.4/Zigbee networks have been conducted in the literature (Oliveira & Salazar 2014, Kasraoui et al. 2012 and Cuomo et al. 2007).

Cuomo et al. (2007) and  Kasraoui et al. (2012) evaluated and compared the performance of Zigbee hierarchical routing protocol with On-Demand Routing protocol in terms of end to end delay, delivery ratio and routing overhead based on IEEE 802.15.4/Zigbee network. However, they did not condsider the effect of thermal noise and interfenrce in their study. Oliveira and Salazar (2014) evaluated  the routing protocols in IEEE 802.15.4 standard applied on Wind Farms Monitoring in terms of  packet losses, throughput, end-to-end delay and jitter, without considering the effect of thermal noise plus interference from the lower layer.

To the best of the authors’ knowledge, no previous work on evaluating the routing protocol on IEEE 802.15.4/Zigbee network has considered the effects of thermal noise, co-channel interference, and node density in the neighbourhood simultaneously to address the BSP.

 

THE CAPB ALGORITHM

Upon  receiving a RREQ packet  m at a node R 

Event: Node R receives RREQ packet m

if Node R is the destination node for RREQ m

Send RREP

else

Calculate Nb

Obtain SINR and infer PER

Calculate Neff using eq. 4

Calculate Preb from eq. 6

Generate a random number  δ  between 0 and 1.0

          if δ < = then

Broadcast the RREQ message m

          else

Drop the RREQ message m

         end if

end if

End if

Figure 2. Proposed CAPB scheme ( Adarbah et al. 2015).

This section briefly describes the proposed Channel Adaptive Probabilistic Broadcast (CAPB) scheme that adjusts the probability of rebroadcasting RREQ packets dynamically according to the SINR and node density in the neighborhood. These two factors affect the efficacy of disseminating RREQ packets significantly. While details can be found in (Adarbah et al. 2015).

The CAPB scheme has been shown in Figure 2. When node R receives a RREQ packet, for which R is not the destination node, it rebroadcasts the RREQ packet with probability . To determine the value of   , node R determines the value of  which is the number of effective nodes within its transmission range r which have received the same RREQ packet. This is done as follows. Assume  is the total number of nodes within the transmission range of node R. We use Hello Packets to infer the value of. The number of nodes  which are located within the transmission range of both nodes R and node S can be calculated from the overlapped area A of the two circles as shown in Figure 3. Using geometry, the overlapped area A can be given by

Here θ is the angle of the circular segment in degrees. Note that θ=120o when node R is at the edge of the transmission range of node S, and θ=180o when node S is extremely close to node R. Node R estimates its distance from node S from the signal strength of the received RREQ packet and calculates the value of θ using simple trigonometric relations. To keep our scheme simple, we assume that nodes are uniformly distributed. With this assumption, the value of  can be given by

To take into account the effects of thermal noise and co-channel interference, node R obtains the SINR from the physical layer at the time of receiving the RREQ packet and infers the PER using the relationship shown in Figure 2. The value of   is then given by

Equation (3) can be simplified to

Figure 3:  Node R receives RREQ from node S.

A higher value of implies that more nodes have received the RREQ and consequently the value of   should be lower and vice versa. This suggests an inverse relationship between  and   .

  (5)

Here  is a constant value representing the dissemination factor. The value of  is greater than unity to compensate the PER and the penalty of assuming uniform distribution. For very low () and very high  values of  equation (2) may not hold true so fixed values of  are used in those cases. In general  can be given as follows:

Appropriate values of  can be derived from an estimated maximum and minimum possible node density and the transmission range of nodes. The implementation of the proposed scheme and its performance evaluation is presented in the next section.

 

PERFORMANCE EVALUATION OF THE CAPB ALGORITHM

 

Simulation setup

We used ns-2 simulator (2.35v) to implement and evaluate the CAPB scheme in LR-WSNs using AODV routing protocol. Standard AODV uses pure flooding. The proposed CAPB scheme and the other scheme (AODV-P) have been implemented in the route discovery process of AODV. In AODV-P scheme, the value of P is set to 0.6 after running simulation with a range of values for P and choosing the one giving the best performance. The parameters of AODV-CAPB scheme follow recommendations in (Adarbah et al. 2015). The radio propagation is based on 2-ray Ground Reflected Model. The network bandwidth is set to 250 kbps and the medium access control ( IEEE 802.15.4 MAC) protocol is simulated using the ns2 library (DEI 2014), and interface queue is 100. The node mobility is modelled using Random Waypoint (Lin et al. 2004) mobility model with variable node speed as shown in the figures below and pause time set to zero. Nodes are placed randomly in an area of 500×400 meters. Only the sink node is deployed in the center of area [250, 200] . Transmission power, path loss and receive power threshold are set such that the effective transmission range is 20m.  Each node has a UDP protocol with a  Constant Bit Rate  (CBR) agent attached, packet size 50 bytes and there are  40 sources nodes which are chosen randomly and they are sending to the sink node.  For energy consumption analysis, each node has initial energy of 100 joules.

Simulation results and analysis

The mobility scenario uses fixed number of nodes (set to 500) and node speed is varied. Simulation results are obtained by averaging the results of 30 runs within same confidence interval of 95%, each using a different seed value and lasting for 500 seconds

Routing overhead.

Routing overhead is defined as the ratio of the number of routing packets (control packets) transmitted per data packet received. Figure 4 shows the average routing overhead as a function of node speed.

In overall, the average routing overhead increases with increasing node speed because higher number of neighbouring nodes and traffic load lead to higher contention and PER which result in redundant retransmission of control packets. Increasing node speed makes the network topology more dynamic. Routes get expired quickly and new route discovery mechanism is triggered more often to replace the expired routes.

The CAPB scheme uses the least number of RREQ packets. Increasing the number of RREQ broadcasts increases the reachability of nodes on one hand but on other hand, it may increases the co-channel interference leading to higher PER which may limit the reachability and require restart the route discovery process.

This is the reason of higher overhead of pure AODV scheme.  Fixed probabilistic scheme (AODV-0.6) limits the number of RREQ blindly which often limits the reachability of RREQ packets to the destination node and route discovery mechanism has to be triggered more often leading to higher overhead. It is interesting to note that the routing overhead of pure AODV is better than AODV-0.6 scheme. In fact, thermal noise plus co-channel interference act as natural limiters for the traffic; the former is static while the latter is adaptive because it increases with traffic intensity. This reduces the chances of getting duplicate RREQs from the neighbouring nodes and adapts to the traffic intensity very well.

 

      

Figures 4: Routing Overhead vs Node Speed

In presence of natural and adaptive limiters (thermal noise and co-channel interference), the artificial limiter (reducing the rebroadcast probability without considering the effect of interference and thermal noise), does not work well because it limits the reachability of RREQs independent of the traffic intensity. Nodes have to try several times before they get a valid route which increases the routing overhead.  The CAPB scheme is able to achieve significantly lower routing overhead as compared to other schemes as shown in Figure 4. The savings in routing overhead increases with the increase in node density, node speed and traffic load.

 

Average throughput

Throughput is defined as the amount of data received by a node per unit time. Figure 5 shows the average throughput, measured at the application layer, for all nodes as a function of number of nodes. Figure 5 shows the average throughput as a function of node speed.

In overall, The average throughput decreases with increasing node speed because routes are broken more often due to changing neighbourhood and network topology causing a temporary pause in data transmission till the new route is established. The time required to establish new routes to replace the broken ones and the routing overhead affect the throughput significantly.

 

      

Figures 5: Average throughput vs. Node Speed

Inefficient or blind decision of rebroadcasting the RREQ packets may not result in a successful route establishment at first attempt and the process may have to be initiated repeatedly. This would increase the time to establish a route from the source node to the destination node. The CAPB scheme is able to achieve significant throughput gain over the other schemes. This is because the rebroadcasting decision in CAPB takes into account SINR and nodal density in the neighbourhood which increases the reachability of RREQ to the destination node while keeping the routing overhead at minimum.

Average end-to-end delay

The average end-to-end delay shows the time a packet takes to reach from the source node. It includes all possible delays caused by buffering during route discovery, queuing at the interface queue, retransmission delays at the MAC, propagation delay and transmission delay. Figure 6 shows the average end-to-end delay for data packets for all nodes as a function of number of nodes, Figure 6 presents the average end to end delay for all nodes as a function of node speed.

It can be seen that for all schemes, the average end-to-end delay increases with increasing node speed.  By increased mobility, route breaking and repairing takes places more often leading to higher average delay.

 

      

Figures 6: Average end to end delay vs. node speed

The CAPB scheme achieves much lower end-to-end delay as compared to other schemes. It is possible because the proposed scheme produces fewer routing traffic, which helps to decrease the contention and collision, and it increases the reachability of RREQ packets to the destination which helps to establish or repair routes faster.

Average energy consumption

Energy consumption accounts for the energy consumed in transmitting, forwarding and receiving packets (both data and routing packets). Figure 7 depicts the average energy consumption for all nodes for different  node speed. The CAPB scheme achieves better energy efficiency as compared to the other schemes.  The energy saving of CAPB is achieved by adapting the rebroadcasting of RREQ packets to current channel conditions and number of neighbouring nodes which helps to reduce unnecessary transmissions of RREQ packet.

 

      

Figures 7: Energy Consumption vs. Node Speed

CONCLUSION

Broadcasting is a vital part of route discovery phase of on-demand routing protocols in low rate WSNs. Many on-demand routing protocols (e.g., AODV) use pure flooding to broadcast the RREQ packet. However, pure flooding generates excessive control traffic which may lead to broadcast storm problem. This paper has evaluated the Channel Adaptive Probabilistic Broadcast (CAPB) scheme that adapts the rebroadcast probability to the thermal noise, co-channel interference and node density in the neighbourhood dynamically based on low rate wireless sensor network. Extensive ns-2 simulations have shown that the CAPB scheme outperforms the standard AODV and the fixed propablisitic scheme significantly in terms of routing overhead, throughput, end-to-end delay and energy consumption. The CAPB scheme is simple and does not require any extra information to be exchanged among the neighbouring nodes.

REFERENCES

Adarbah, H.Y. et al., 2015. Efficient Broadcasting for Route Discovery in Mobile Ad-hoc Networks. In Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems. Chicago, USA, pp. 1–7.

Adarbah, H.Y., Ahmad, S. & Duffy, A., 2015. Impact of noise and interference on probabilistic broadcast schemes in mobile ad-hoc networks. Computer Networks, 88, pp.178–186. Available at: http://linkinghub.elsevier.com/retrieve/pii/S1389128615002145.

Boukerche, A. et al., 2011. Routing protocols in ad hoc networks: A survey. Computer Networks, 55(13), pp.3032–3080. Available at: http://dx.doi.org/10.1016/j.comnet.2011.05.010.

Chen, M. et al., 2008. Reliable and energyefficient routing protocol in dense wireless sensor networks. International Journal of Sensor Network, 4(1/2), pp.104–117.

Cuomo, F. et al., 2007. Routing in ZigBee : benefits from exploiting the IEEE 802 . 15 . 4 association tree. In IEEE International Conference on Communications, 2007. ICC ’07. pp. 3271–3276.

DEI, 2014. NS2 Library: dei80211mr. Available at: http://www.isi.edu/nsnam/ns/doc/node193.html [Accessed February 17, 2014].

IEEE802.15.4, 2006. Part 15.4:Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs), Available at: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4152704&url=http://ieeexplore.ieee.org/ielD/4152702/4152703/04152704.

Kasraoui, M., Cabani, A. & Mouzna, J., 2012. IMPROVEMENT OF ZIGBEE ROUTING. In 2012 IEEE International Conference on Green Computing and Communications, Conference on Internet of Things, and Conference on Cyber, Physical and Social Computing. pp. 788–793.

Kulkarni, N. et al., 2011. Performance Evaluation of AODV , DSDV & DSR for Quasi Random Deployment of Sensor Nodes in Wireless Sensor Networks. In International Conference on Devices and Communications (ICDeCom). pp. 1 – 5.

Lee, S.-J., Belding-Royer, E.M. & Perkins, C.E., 2002. Ad hoc on-demand distance-vector routing scalability. ACM SIGMOBILE Mobile Computing and Communications Review, 6(3), p.94.

Lin, G., Noubir, G. & Rajamaran, R., 2004. Mobility models for ad hoc network simulation. In Proceedings of 23rd conference of the IEEE communications society (INFOCOM 2003). pp. 454–463.

Ni, S., Tseng, Y. & Chen, Y., 2002. The broadcast storm problem in a mobile ad hoc network. Wireless Networks, (8), pp.153–167.

Oliveira, F.D.M. & Salazar, A.O., 2014. QoS Analysis of Routing Protocols in Wireless Sensor Networks in the Monitoring of Wind Farms. In 2014 IEEE International Instrumentation and Measurement Technology Conference (I2MTC) Proceedings. pp. 1059 – 1064.

Yick, J., Mukherjee, B. & Ghosal, D., 2008. Wireless sensor network survey. Computer Networks, 52, pp.2292–2330.

Professor

You must be logged in to post a comment