Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks

Tarun Dubey and Om Prakash Sahu

1.Introduction

Wireless sensor networks (WSNs) are a bridge between the real and virtual world, which are a collection of sensor nodes with the ability of sensing many phenomena of interest over large chronological scales[1].Each sensor node in the network is equipped with the memory, radio frequency transceiver, and power source to broadcast wirelessly over a specified protocol[2].Broadcasting is a common means for sensor nodes to efficiently share their data with each other.Broadcasting can be utilized to initialize the network arrangement for route discovery between a given pair of senor nodes and could serve as an efficient method to localize sensor nodes.The simplest way of broadcasting is flooding[3], under which each sensor node rebroadcasts when it receives a message for the first time.It is attractive for its simplicity but causes high redundancy, packets collision, and bandwidth wastage[4],therefore an efficient broadcast strategy is required to reduce the message broadcast redundancy in sensor networks[5].As modification to flooding, various probabilistic broadcast protocols have been proposed[5]-[7].These proposed protocols avoid the above cited problems and provide alternative solutions to flooding.In addition,sensor network applications also require broadcast protocols to support different degrees of reliability, hence probabilistic protocols are more suitable.One of the basic extensions to flooding is gossiping[8], where each node forwards a message in a probabilistic manner.As the extensions to gossiping protocols, [9]and [10]are predominantly static in nature and cannot adapt to the changing topology as well as changing application requirements.Therefore, static protocols require the network designer to conservatively pre-configure the parameters on a case-by-case basis, in order to allow for changes in the network topology (the node density and number of duplicate broadcasts).In this paper, we propose a broadcasting algorithm to control redundancy and improve localization (BACRIL) in WSNs.The proposed algorithm uses the gossip protocol and automatically adapts to the changing network topology with the increasing node density.BACRIL is light weight in view of the limited resources available with sensor nodes and supports localization of sensor nodes in a specified area with less overhead.

The rest of the paper is organized as follows: Section 2 provides a review of the gossip protocol and describes a few of its preliminaries.Section 3 presents the proposed BACRIL followed by its performance analysis in Section 4.Section 5 highlights the simulation results.Finally, Section 6 concludes the paper.

2.Review of Gossip Protocol

Gossip is a probability based protocol and its definition was stated in [11]that whenever a sensor node wishes to send a message, it randomly selects a neighboring sensor node; upon receiving the message for the first time the neighboring sensor node repeats this process; if the same message is received twice, it is discarded.In order to achieve this, each sensor node has to keep the track of messages it has already received.Besides the favorable for message broadcasting, the gossip protocol also performs tasks to help the inter process interaction for information exchange between networks where the sensor node failure is quite frequent.This section summarizes some general preliminaries for the gossip protocol in WSNs[12].

2.1 Number of Nodes/Node Density

The number of sensor nodes, N, determines the level of confidence for the gossip protocol.The gossip protocol relies on the aspect that each sensor node can make its communication based on negotiations with neighboring sensor nodes.For a dense area A, sensor nodes are likely to receive more messages hence it might be proved to be beneficial to listen to messages with a very low probability.In some cases the area A might be very sparse, hence it might be beneficial to listen to the messages with a probability, such as P=1, therefore the probability with which a sensor node listens to the messages directly depends on the node density D of the sensor nodes deployed in the network.The sensor node density can be calculated using

where R denotes the transmission range of the sensor node.

2.2 Node Degree

The node degree Ń depends on the values of A, N, and R, which can be calculated as

It is to be noted Ń is often variable since A, N, and R cannot be always uniform.

2.3 Frequency of Received Messages

Sensor nodes are adjacent if the distance between them is less than the defined transmission range.If the sensor nodes are set to a very low probability of listening, they will transmit only when there is a change, however, they may send very few messages in some cases.Further, such a sensor node may or may not choose to listen depending upon the initial value of P.Thus a sensor node gossips only if it receives a new message, or else it continues being in a passive state.

2.4 Optimized and Robust Network Topology

The network topology can change adversely due to node failures and energy depletion even if localized deployment is made.Therefore, robust network topology is essential to maintain correct system operations.The performance, functionality, and reliability of the gossip protocol do not drop rapidly with node failures and the robustness is exhibited in the face of largely varying node capabilities in terms of memory, bandwidth, and connectivity.

2.5 Fan Out (n)

It is defined as a configuration parameter to count the number of sensor nodes selected as gossip targets.Upon receiving a message for the first time, the sensor node selects gossip targets to forward the message.The tradeoff associated with this parameter (n) lies between the desired fault tolerance level and observed redundancy.High value of n guarantees fault tolerance but also leads to an increase in the network redundancy.

2.6 Relative Message Redundancy (RMR)

RMR measures the message overhead for a protocol.It is obtained by

Table 1: Algorithm description

where m denotes the number of messages broadcasted during a procedure.This metric is applicable if at least two sensor nodes receive the message.Zero value of RMR denotes that there is exactly one message exchange per sensor node and it is the optimal value.High value of RMR indicates a poor network usage, and for gossip based message exchange, RMR tends to n–1.

3.BACRIL

The broadcasting algorithm to control redundancy and improve localization (BACRIL) is designed with the goal to obtain satisfactory broadcast performance in high density WSNs.Scalability is a critical issue in sensor networks composed of several densely deployed sensor nodes.The localization of sensor nodes increases with the increase in the sensor node density, for each sensor node makes the decision to broadcast according to the local information obtained from its neighboring sensor nodes.We assume that BACRIL does not require any topology information thus the overhead remains small; all the sensor nodes have the same characteristics (the same communication and sensing ranges).The position of every sensor node is not known in any arbitrary coordinate system, therefore, we assume that the neighbors of a particular sensor node are determined based on the message broadcast.In this way,the sensor nodes decide locally to broadcast messages (as an active node) or to disregard the previously received messages.In WSNs, a message broadcast is said to be redundant if each sensor node in the network has already received the same message at an earlier time point.The technical challenge associated with this problem lies in accurate estimation of the redundant message count for the varying number of sensor nodes within the network confined to the number of broadcasts.BACRIL is based on the assumption that the sensor nodes N are deployed within a specified area A, and are allowed to broadcast a message m, intuitively with the increase of the number of sensor nodes corresponding to a high density wireless sensor network.Table 1 presents the steps of the proposed algorithm.

We remark that BACRIL incorporates the benefits of the gossip protocol to control redundant message rebroadcast and guarantee sensor node localization with the advantage that a sensor node has to be active only for the message broadcast and no node has to localize itself with respect to a global coordinate system.This scheme ensures that sensor nodes with the smallest distance from their neighboring sensor nodes will satisfy the minimum rebroadcast in order to control the redundancy.

4.Performance Analysis of BACRIL

4.1 Definitions

· A is the area of the entire wireless sensor network.

· D is the sensor node density of the network (the average number of sensor nodes per area).

· r is the coverage radius of each node.

· N is the total number of sensor nodes deployed.

· m is the number of broadcasted messages.

· h is the number of sensor nodes that have rebroadcasted the message after its reception.

· RBis the rebroadcast ratio, i.e., the ratio of the number of sensor nodes that have rebroadcasted the message to the number of sensor nodes in the entire network.

· P is the probability that a sensor node can listen to a message.

· R is the transmission range of a sensor node.

· n is the number of sensor nodes selected as gossip targets.

Based on the above definitions, (4) and (5) are obtained.

The rebroadcast ratio RBmanifests the efficiency of the gossip protocol since RBis inversely proportional to the broadcast efficiency.A large value of RBresults in high redundant rebroadcast with low broadcast efficiency.Therefore, the efficiency of BACRIL is determined by the minimum value of RB, calculated by

If the values of A, D, and r are determinate, in order to obtain the minimum value of RB, the value of h should be minimized because if D increases the value of RBdecreases.BACRIL is evaluated for different values of N.The sensor node density with different values of N is shown in Fig.1.

5.Simulation Results

To study the influence of BACRIL on WSNs, we simulated a wireless sensor network consists of different number of sensor nodes.The simulations were performed on SNetSim[13].The simulator has a complete stack for the gossip protocol and also provides a central management with the functionality of setting the deployment area and other parameters before creating the network topology.The sensor nodes are randomly placed in an area of 500 m×500 m, where each sensor node can communicate with another sensor node.It was observed that BACRIL completes the message broadcast with a satisfying coverage ratio; the message broadcast maintains a controlled level of redundancy with the increasing number of sensor nodes and guarantees the stability of the proposed algorithm in high density sensor networks.The network was simulated individually for different values of N = (50, 100, 200, 300,400, and 500), the received message counts and received redundant message counts for different values of N are shown in Table 2.

The simulation results show that the redundancy is controlled within the network with the increase of the number of sensor nodes over the same deployment area.Fig.2 provides graphical data between the number of sensor nodes and the percentage of observed redundancy in the message counts.The controlled redundant message counts is promising for networks with large number of sensor nodes, as in case of the sensor node failure, the network can retain its message broadcast in a fault tolerant manner besides improving sensor node localization.

Table 2: Message counts

Fig.2.Number of sensor nodes vs.percentage redundancy.

6.Conclusions

In this paper, we propose BACRIL for controlling the redundancy in WSNs where the sensor node density is a dominant factor.The proposed algorithm utilizes the benefits of gossip towards controlling the redundancy and accurately estimates the received redundant message counts without the location knowledge of the neighboring sensor nodes.Although the estimation of the least redundancy during broadcast has been done in some current studies[14],[15], compared to them, the proposed BACRIL is scalable to the sensor node density and works well for a small network topology with 50 sensor nodes ranging to a large network topology with 500 sensor nodes over the same deployment area.The simulation results show that the redundancy maintains a controlled level for increased values of sensor node densities, and this approach can be used to improve self localization of irregularly arranged sensor nodes in dense networks, as the neighborhood knowledge of sensor nodes does not cast much effect on the proposed algorithm.Our results will also benefit the future research on self localization of high density WSNs by cutting down the total energy consumption due to controlled redundancy for maximizing the network life time.

[1]H.J.Pandya and V.S.Vaishnav, “Detection and classification of volatile organic compounds using indium tin oxide sensor array and artificial neural network,” Ⅰnt.Journal of Ⅰntelligent Systems Technologies and Applications, vol.7, no.1, pp.72-79, 2009.

[2]I.F.Akyildiz, W.Su, Y.Sankarasubramaniam, and E.Cayirci, “A survey on sensor networks,” ⅠEEE Communications Magazine, vol.40, no.8, pp.102-114,2004.

[3]J.N.Al-Karaki and A.E.Kamal, “Routing techniques in wireless sensor networks: a survey,” ⅠEEE Journal of Wireless Communications, vol.11, no.6, pp.6-28, 2004.

[4]K.Sohraby, D.Minoli, and T.Znati, Wireless Sensor Networks: Technology, Protocols, and Applications,Chichester: John Wiley and Sons, 2007, pp.203-209.

[5]B.Carbunar, A.Grama, and J.Vitek, “Redundancy and coverage detection in sensor networks,” ACM Trans.on Sensor Networks, vol.2, no.1, pp.94-128, 2006.

[6]J.-H.Luo, X.Liu, and D.-X.Ye, “Research on multicast routing protocols for mobile ad-hoc networks,” Computer Networks, vol.52, no.5, pp.988-997, 2008.

[7]W.R.Heinzelman, J.Kulik, and H.Balakrishnan, “Adaptive protocols for information dissemination in wireless sensor networks,” in Proc.of the 5th Annual ACM/ⅠEEE Ⅰnt.Conf.on Mobile Computing and Networking, Seattle, 1999, pp.174-185.

[8]Z.J.Haas, J.Y.Halpern, and L.-E.Li, “Gossip-based ad hoc routing,” ⅠEEE/ACM Trans.on Networking, vol.14, no.3,pp.479-491, 2006.

[9]J.Kulik, W.R.Heinzelman, and H.Balakrishnan,“Negotiation base protocols for disseminating information in wireless sensor networks,” Wireless Networks, vol.8, no.2-3, pp.169-185, 2002.

[10]R.Chandra, V.Ramasubramanian, and K.P.Birman,“Anonymous gossip: improving multicast reliability in mobile ad-hoc networks,” in Proc.of the 21st Ⅰnt.Conf.on Distributed Computing Systems, Phoenix (Mesa), 2001, pp.275-283.

[11]A.M.Kermarrec and M.V.Steen, “Gossiping in distributed systems,” Operating Systems Review, vol.41, no.5, pp.2-7,2007.

[12]C.L.Barrett, S.J.Eidenbenz, L.Kroc, M.Marathe, and J.P.Smith, “Parametric probabilistic sensor network routing,” in Proc.of the 2nd ACM Ⅰnt.Conf.on Wireless Sensor Networks and Applications, San Diego, 2003, pp.122-131.

[13]W.Heinzelman, J.Kulik, and H.Balakrishnan, “Adaptive protocols for information dissemination in wireless sensor networks,” in Proc.of the 5th Annual ACM/ⅠEEE Ⅰnt.Conf.on Mobile Computing and Networking, Seattle, 1999, pp.174–185.

[14]R.Zhao, X.Shen, Z.Jiang, and H.Wang.(2012).Broadcasting with least redundancy in wireless sensor networks.Ⅰnt.Journal of Distributed Sensor Networks.[Online].Available: http://www.hindawi.com/journals/ijdsn/2012/957606/

[15]J.Pu, Y.Gu, Y.Zhang, J.Chen, and Z.Xiong.(2012).A hole-tolerant redundancy scheme for wireless sensor networks.Ⅰnt.Journal of Distributed Sensor Networks.[Online].Available: http://www.hindawi.com/journals/ijdsn/2012/320108/