Bloom filter–based efficient broadcast algorithm for the Internet of things

Abstract

In the Internet of things, a large number of objects can be embedded over a region of interest where almost every device is connected to the Internet. This work scrutinizes the broadcast overhead problem in an Internet of things network, containing a very large number of objects. The work proposes a probabilistic structure (bloom filter)-based technique, which uses a new broadcast structure that attempts to reduce the number of duplicate copies of a packet at every node. This article utilizes a clustering concept to make the broadcast efficient in terms of memory space, broadcast overhead, and energy usage. The unique idea of a bloom-based network uses a filter to incorporate neighbor information when taking a forwarding decision to reduce broadcast overhead. The simulation results show that parallel broadcasting among different clusters and the use of a bloom filter can achieve a reduction in broadcast overhead from hundreds to ones and tens, when compared with a conventional non-bloom-based broadcast algorithm and a bloom-based algorithm. In addition, it helps to reduce energy usage evenly throughout the network, 1/100 times, when compared with conventional broadcast (non-bloom-based) and, 1/10 times, when compared with bloom-based broadcast. This increases the lifetime of a network by having control over network density usage and communications overhead as a result of broadcasting.

Keywords

Internet of things broadcast bloom filter cluster

Introduction

The world today has entered a new era of pervasive communication where almost every device is connected to the Internet. The idea of an Internet of Things (IoT) was initiated by K Ashton¹ back in 1999. It identifies every object of a network as an “Internet-like” structure. These objects can be as large as an aeroplane and as small as part of the human body. With passing time, different authors have given different definitions of the IoT.^2,3 In the IoT, a large number of objects can be embedded over a region of interest. The deployed objects can be set out to network and disseminate data using the web to offer services to different end users. The end-user system gathers data from the objects and processes these data in order to monitor the state of the environment under examination.⁴

Typically, IoT devices interconnect embedded sensors using the Internet through the IP (Internet protocol) stack.⁵ This approach demands complex processing, large amount of energy expenditure, and memory. In order to keep the system capabilities less complex, the devices are made to communicate locally through a non-IP network. The paradigm of IoT is maintained in the network using a smart gateway that connects it to the Internet. In a non-IP communications system, intra-transmission channels are made using ZigBee, Bluetooth, Near-Field Communication (NFC), and so on. These channels are generally range limited up to a few meters (1–100 m). The Internet connectivity is used to provide inter-transmission via a smart gateway. This resulted in one of the most popular sub branches of IoT, that is, wireless sensor networks (WSNs).

WSNs have generated great interest in industry and academia, and today sensors are used in many applications. Sensors can be used to measure properties about an object and reveal facts taking place in the vicinity of the sensor. The measured properties are usually communicated via a radio transmitter to a manipulator’s site either directly (using an IP network) or through a gateway node (using non-IP network). The unattended sensor node data can significantly influence the efficiency of many applications. Therefore, a proper data collection mechanism is important for the system to monitor events and wisely manage data processing and communications. A wide variety of IoT applications are envisioned as requiring proper networking of nodes where each node translates sensing activities and identifies itself for required services.⁶ Predictive maintenance must be performed in many applications for enhanced safety and security using remote data acquisition and monitoring, and a WSN can facilitate this real-time data management and distribution to cater for timely alarm triggering for security sensitive applications.

In IoT, broadcasting is a very common and efficient solution for sharing data. This article is one of the few papers that has researched efficient broadcasting in IoT. Broadcasting serves as a robust and effective source for network discovery, facilitates network configuration, initializes query for data, and allows the discovery of multiple routes between node pairs in a network.⁷ When a node broadcasts a packet in the network, it floods the packet to its neighbors. Flooding is a very simple way of broadcasting data.⁸ Each node broadcasts the packet to its neighbors, and all receiving nodes will rebroadcast to their own neighbors; this leads to flooding of the packet on the network. This method of broadcasting will result in the storm problem and will inflict serious overhead in a network.⁸

Controlling the amount of rebroadcasting can help to limit the overhead generated thereby ensuring that efficiency is introduced with regard to memory space and energy consumption. Energy consumed by IoT nodes in transmission is much greater than in reception as shown by Zhao et al.⁹ and Healy et al.¹⁰ Therefore, controlling rebroadcast transmissions to neighbors can significantly help in improving network performance in terms of increasing network lifetime and energy efficiency. This work is an extension of Talpur et al.¹¹ that proposed a design of an efficient broadcasting mechanism for data collection, which works to control broadcast overhead and subsequently results in a more energy-efficient network.

The objective of this work is to utilize a bloom filter, a space-efficient probabilistic data structure given by BH Bloom¹² in 1970. Bloom filter and its variants are finding use nowadays in various areas of distributed systems where broadcasting data are used. The broadcasting problem is formulated using a bloom filter that works to define a set of forwarding nodes to prevent flooding of packets to all neighbors. Using defined metrics, a set of nodes that have already participated in the transmission would be defined in the form of a bloom filter. This helps to prevent those nodes from being flooded with unwanted packets previously received. The proposed mechanism in the study of Talpur et al.¹¹ was implemented in MATLAB, and performance results were compared with existing common broadcasting mechanisms. The extended version of this work presents a distributed network broadcasting solution, and it is compared with the previously proposed version of a bloom-based broadcast presented in the study of Talpur et al.¹¹

In this extended article, a concept of distributed bloom–based broadcast is proposed for IoT networks. A memory-efficient broadcasting technique is the goal of the proposed work. This work has resulted in a more efficient solution for large networks with respect to the one proposed previously in the study of Talpur et al.¹¹ The concept in this work is to partition a large IoT network of nodes into a number of small networks, called clusters. A cluster head (CH) is elected¹³ or selected to manage nodes locally within each cluster.¹⁴ The CHs will also work as gateways to perform communication with other CHs. Local broadcasting is executed within each cluster to make the process efficient in terms of memory usage. The problem of broadcasting in the IoT where a very large network of nodes exists can consume network bandwidth and lead to failure of the network. This work allows broadcasting to be controlled/restricted to a cluster thereby maximizing network lifetime for large networks.

The remainder of this article is organized as follows. Section “Related work” explains the related work done in this area. Section “Bloom filter” discusses the concept and creation of a bloom filter. Sections “Architecture of broadcasting in the IoT,”“Bloom-based broadcast construction,” and “Distributed bloom–based broadcast construction” describe the architecture of traditional broadcasting, bloom-based broadcasting, and distributed bloom–based broadcasting, respectively. Section “Simulation results” evaluates the simulated results, and section “Conclusion” concludes the article.

Related work

This section reviews the published works which address broadcasting in WSNs as very little research work has been proposed for broadcasting in IoT networks to date. In the study of Lakhlef et al.,¹⁵ the author claims its work to be the first to present an efficient broadcast protocol for the IoT as most of the research published to date has targeted WSN-based IoT networks for broadcasting issues.^16,17 The use of probabilistic schemes for broadcasting services is discussed in a number of previous works.^17–20 The analyses and simulations performed in the study of Ni et al.¹⁷ and Guo¹⁸ help to reduce rebroadcasting of packets using differentiated timing perception and novel heuristic timing techniques. In the study of Kyasanur et al.,¹⁹ the smart gossip concept is presented where probabilistic structure–based protocols, which offer broadcast services, have been targeted in order to understand the basic topology and thereby propose a low overhead solution. The method keeps track of previous broadcasts to determine the probability of the node having to rebroadcast a packet. In another work,²¹ authors have used concept of gossiping probability and ensure fully converged broadcasting for values between 0.6 and 0.8. For larger networks, gossiping proves that usage of messages is reduced to 35% when compared with flooding. Another work related to probability-based broadcasting in WSN is probability-based broadcast forwarding (PBBF) by Miller et al.²⁰ The PBBF works at the media access control (MAC) layer and explores the energy-latency-reliability trade-off. It determines the mathematical relationship between energy and latency for a given level of reliability.

Energy wastage during transmission has become a crucial problem with broadcasting protocols. There are a number of researchers focusing on minimizing the energy cost of broadcasting. In some studies,^8,22–25 different techniques have been proposed to control energy flow while maintaining full network connectivity. The opportunistic large array (OLA) in the study of Hong and Scaglione²² provides a cooperative form of broadcasting to save energy. It allows the optimal energy allocation scheme subject to signal-to-noise ratio (SNR) requirements to reduce energy expenditures. Whereas Kumar and Wong²³ utilize a variable permeable length-based broadcasting scheme to disseminate data in a network using small permeable lengths. It helps to conserve energy while allowing for significant throughput in a network. Zeng et al.²⁴ and Tang and Wang²⁵ are also working to cope with energy-deficiency problems while utilizing a broadcast tree concept. A tree constructing algorithm is used in the study of Zeng et al.²⁴ and Tang and Wang²⁵ to control duplicate packet reception and thereby save energy by reducing flooding. The work by Zeng et al.²⁴ and Tang and Wang²⁵ are compared with the proposed work in this article, and it is shown that the work presented here is better in terms of neighbor retransmission overhead. The proposed work provides a mechanism to control broadcast overhead while building a bloom filter containing a list of neighbor nodes. A well-defined probabilistic structure–based bloom filter is used to create a virtual tree of nodes. It helps to relieve broadcast storm by controlling packet duplications and provides energy efficiency using a bloom filter. The extended work uses clusters to enhance the efficiency of a broadcasting for IoT applications. The enhanced work is compared with previous work,¹¹ and it is shown to be more efficient in terms of memory space, overhead, and energy consumption.

Bloom filter

Bloom filters have been widely used in many fields. It is a space-efficient solution used as a filter for identifying input memberships.²⁶ There are a number of algorithms that successfully implemented bloom filters for enhanced network performance.^27–29 The implementation of a bloom filter in WSNs is as diverse as routing, filtering, and security.^30–33 Bloom filters are probabilistic data structures used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not—that is, a query returns either “possibly in set” or “definitely not in set.”²⁶

In this work, the bloom-based approach is used to control packet broadcast overhead, using an input membership set of a bloom filter.

Basic

The bloom filter is defined as an array of bits used for representing a set $S - x_{1}, x_{2}, \dots, x_{n}$ of n elements. The hash function $H (x)$ is a key function to insert the element x into a set S of a bloom filter. Let $H = h_{1}, h_{2}, \dots, h_{k}$ be the set of hash functions to map element $x ϵ S$ , in the uniform range of m random numbers. Each hash function yields a bit location and represent x by setting the bits of hash index $h_{i} (x)$ as 1 for $i = 1 \to k$ , where k is the total number of hash functions. Initially, all m bits of the filter are set to zero, where m is the number of bits in the bloom filter. In order to store element x into the bloom filter using the hash function $H (x)$ , a logical OR operation is executed between the bit arrays. Algorithm 1 gives the code for inserting an element into the bloom filter. Conversely, to search for an element in the bloom filter, the bit array is generated by hashing. An array of bits is compared with the bloom filter to guarantee the membership of an element in the bloom filter. If the bit locations $h_{i} (x)$ are set to 1 in an array, and are also 1 in the bloom filter, then an element is assumed a member of the bloom filter with some probability. Algorithm 2 presents the code used to query the membership of an element in the bloom filter.

Algorithm 1. Insert element x in the bloom filter.
1: K: Number of hash functions
2: functionBloomFilter $(x, BF_Vector)$
3: for $i \to 1 . . k$ do
4: loc ← $hashin g_{i} (x)$
5: end
6: for $j = 1 \to length (loc)$ do
7: set $I n p u t V e c t o r_{l o c_{j}}$ ← 1
8: end
9: $BF_Vector = BF_Vector \oplus InputVector$
10: return $BF_Vector$

Algorithm 2. Query to check presence of $EQ_IP$ element.
1: functionBloomFilter $(BF_Vector, EQ_IP)$
2: for $i \to 1 . . k$ do
3: loc ← $hashin g_{i} (EQ_IP)$
4: end
5: for $j = 1 \to length (loc)$ do
6: set $EQ_Vecto r_{lo c_{j}}$ ← 1
7: end
8: if $EQ_Vecto r_{loc} & & BF_Vecto r_{loc} = = 1$ for all “loc”:
9: $Output = ″ True ″$ ▹ Element is present
10: else
11: $Output = ″ False ″$ ▹ Element is not present
12: Break ;
13: returnOutput

False positive probability

False reporting can occur in the bloom filter where an element that is not a member of set S but is reported as its member. A bloom filter allows a false indication of an element’s presence with a small probability, known as false positive probability. This false positive probability is an accepted error as the advantage of space/storage efficiency outweighs the disadvantage of false positive probability as long as it is small. False positive errors can be controlled by adjusting the size of the filter. The size of the filter provides a clear trade-off with the probability of false positive. The probability that a bit is “0” in the filter can be given as

P_{0} = {(1 - \frac{1}{m})}^{kn} \approx (1 - e^{\frac{- kn}{m}})

where k is the number of hash functions used to insert n elements into a filter of size m. The false positive probability, in which a bit is 1 when the element does not exist in the given set of a bloom filter is given by

P_{FP} = (1 - P_{0})^{k} = {(1 - {(1 - \frac{1}{m})}^{kn})}^{k} \approx {(1 - e^{\frac{- kn}{m}})}^{k}

In the simulation, the secure hash algorithm 2 (SHA-2) algorithm is used. The parameters of the filter are adjusted to keep the maximum false probability value at 0.01.

Architecture of broadcasting in the IoT

The simplest way to communicate data to an entire IoT network is where each node broadcasts a data frame to all known neighbors. Such broadcasting where a single node receives multiple copies of the same data frame from different neighbors will significantly increase overhead and energy consumption of a network. Broadcast communication is needed in a number of applications, including network-wide query and response packets. This is often necessary to provide network-wide reliable transmissions where individual nodes may fail. It is important to maintain successful frame forwarding while controlling overhead to save energy. In the proposed broadcast control algorithm, a node needs to transmit data to all the network nodes. The idea is to provide control over broadcast overhead where multiple copies of data frames are limited through utilizing a space-efficient bloom filter.

A densely deployed network is considered to monitor a wide area where all nodes are equipped with similar processing and transceiver properties. Broadcasting is an event-triggered only when certain conditions take place or a threshold level is detected; then, a node broadcasts its ID to request required services.

System model

The sensor nodes are a crucial part of an IoT network. An IoT network consists of a large number of sensor nodes and a gateway. In the proposed system model, a network is divided into different clusters, and a CH is used as an intermediate node to provide a communication channel between sensor nodes and the gateway (i.e. Base Station (BS)), as shown in Figure 1. The deployment process is made using different assumptions where the N number of nodes are randomly distributed over the area of 1000 m × 1000 m, that is, $N = n_{1}, n_{2}, n_{3}, \dots, n_{N}$ . We assume that each node in the IoT network is identified by a unique ID and is able to communicate with the other surrounding nodes through short-range communication technology such as WiFi-Direct, Bluetooth, or ZigBee. The nodes are homogeneous and proactive. The transfer of data takes place in a periodic fashion. The gateway or BS is fixed and manually located in the network field with a unique ID. The cluster formation and CH selection is kept simple. The CHs are selected and located at the onset of the network. Every CH knows and keeps a record of the ID of its all children nodes using a bloom filter. Every new child will add itself to the nearest cluster and accordingly chooses the CH. Each CH maintains two filters, one for child information and another for a record of other CHs and the gateway (or BS). Each child maintains only one filter for neighbor information.

Figure 1.

A general network scenario of proposed work.

Radio model

A widely used radio model^34–37 is simulated in proposed research. According to that the radio energy spent in transmission and reception can be given as $E_{Tx}$ and $E_{Rx}$ in the following equations

\begin{matrix} E_{Tx} (k, d, n) & = E_{Tx_el} * k + E_{a} (n) * k * d^{n} \\ E_{Rx} (k) & = E_{Rx_el} * k \end{matrix}

where k is the number of bits transmitted over distance d, with path loss coefficient n, depending on different environmental factors. In proposed research, a two-dimensional network is considered where 400 nodes are deployed in a random manner. The radio model assumes a error-free channel and exploits a free space model. The $E_{Tx_el}$ , $E_{Rx_el}$ , and $E_{a}$ is the transmitter/receiver electrical energy dissipated by the amplifier and circuitry, respectively. Every two nodes share a common channel and using carrier sense multiple access (CSMA) to perform transmission with the same transmit power level when seperated by a distance d. It helps to tackle situation where multiple nodes start transmission at same time. The initialization phase takes place randomly when a node has a data to broadcast. It is considered that broadcast reachability starts with a randomly defined source node where the transmission process begins with a neighbor discovery phase. Based on these assumptions, the k number of bits will be transmitted over distance d, with path loss coefficient n, utilizing $E_{Tx}$ and $E_{Rx}$ energy in transmission and reception, respectively. This elucidation proves greater energy dependence on distance and number of transmitting bits. Therefore, the transmission between two nodes, where unwanted copies of the same packet(s) are received at a node during a broadcast, is a waste of network energy.

Neighbor discovery

It is important to maintain neighborhood information, where each node keeps the list of nodes that are reachable to it by direct transmission (within the same cluster). These nodes are considered neighbor nodes. A periodic exchange of hello messages is used to discover neighboring nodes. In this work, a randomly distributed network is assumed where a node has a neighbor node that is reachable to it by a distance of d. The distance d between two nodes $n_{i}$ and $n_{j}$ is calculated using the Euclidean distance formula, that is

d_{ij} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}

where $i = 1, 2, 3, \dots, N$ and $j = 1, 2, 3, \dots, N$ . The set of neighbor IDs contains all node IDs within the transmitting range (distance d). In the proposed algorithm, the distance d is denoted by a notation of $d'$ . The distance $d'$ is chosen to minimize energy consumption and limit unwanted energy wastage. The source node sends a hello message through its wireless channel. On reception of messages, all sink nodes having the distance $d'$ or less to the source node will reply to the source. The source node then creates a list of neighbor nodes’ IDs that have responded to the hello message. A list of neighbor nodes is maintained at each child node (CN) in the form of a bloom filter where the node IDs of each neighbor is entered into the filter.

Bloom-based broadcast construction

The algorithm proposed has two main goals: (1) energy-efficient transmission and (2) successful delivery of data to an end node (EN). This is to be facilitated by a bloom-based broadcast structure. To provide an energy-efficient solution, each node must consume as little energy as possible to provide a network-wide broadcast transmission. The idea is to limit the number of copies of a broadcast packet received by a sink node from its neighbors. It is neither possible nor likely to receive exactly one, so the goal is to minimize the total number of duplicate packets received, thereby minimizing energy usage in the network due to packet transmission.

The tree construction phase discussed here takes place, once all neighbors are discovered. After completion of the neighbor discovery phase, all nodes have a neighbor filter (NF) containing a list of their respective neighbors. Here, the algorithm uses a broadcast technique to issue urgent service requests from nodes and data transfer requests to the central station. The case of urgent service is considered as an example to examine the working of bloom-based broadcast. This algorithm can be used for all different kinds of broadcast informations. The tree construction begins with the initial source node (ISN) that begins the process by broadcasting two filters to its one-hop neighborhood, as shown in Figure 2. The first filter has a list of ISN neighbors and is called a NF, while the second filter is an empty filter called an urgent member filter (UMF). An UMF is used to update the list of nodes that require services from the central station as described. During the sensing process, when certain conditions take place or a threshold level is detected, the node considers itself as an urgent case member and adds itself to the UMF. The selection of the ISN is random.

Figure 2.

Structure of neighborhood discovery in proposed scenarios.

Once the ISN has broadcast the filters, its neighbors will act as induced forwarders and rebroadcast the updated filters to their own neighbors. This cycle continues until the EN receives the data as shown in Figure 2. EN is a BS that helps to connect the sensor network to the central network for further processing and decision-making. During the rebroadcasting process, when a receiver accepts two filters, it marks the neighbors that it has common with the sender to block retransmission of these filters to these nodes. The selection of common neighbors is performed by querying the neighbor ID from the NF. The filter responds to the presence and absence of IDs with some probability. This helps to minimize broadcast overhead through limiting multiple reception/transmission of the same filters to common neighbors. Before forwarding the filter data received from its preceding node, the sender will add its ID to the UMF if the determined threshold level is exceeded. Otherwise, without any changing, the UMF data are forwarded to the succeeding nodes. The succeeding nodes are the neighbors of the sender node, excluding the neighbors it has in common with its predecessor. The selection of forwarders is chosen by the sender node from its neighbors and received NF, as shown below in Algorithm 3.

Algorithm 3. Broadcast tree construction.
1: Each node broadcasts “hello” messages to discover its neighbors
2: A list of neighbors is maintained at each node in the form of a bloom filter, called as a Neighbor Filter (NF)
3: Initial Source Node (ISN) is chosen randomly
4: ISN creates two filters: ISN.NF and ISN.UMF
5: ISN broadcast both filters to its neighbors.
6: At receiving nodes,
7: if $value > threshold$ then
8: $MyID \to UMF$
9: Compare neighbors with received NF,
10: if same neighbors? Yes then
11: Don’t send data to same ID
12: $UpdatedNF = ReceivedNF \oplus MyNF$
13: Send updated NF and MF to all neighbors except the common one
14: The process continues till EN node receives filter from its neighbors
15: After every T-intervals, choose ISN randomly and go to step 4

During the growing network, use of a NF does not limit the reception of a filter to a node. It is found that there is a number of situations during which a node receives multiple copies from different neighbors. For example, when two nodes that are not neighbors to one another but they share another node in their neighbor list. The analysis presented compares results to a normal packet broadcast and with two existing broadcast control algorithms (i.e. lightweight energy-efficient broadcast control protocol (LEBCP)²⁴ and lightweight energy-efficient reliable broadcast tree (LERBT)²⁵), and it shows that the proposed method controls the overhead generated by broadcasting better than previous methods.

Distributed bloom–based broadcast construction

This section discusses the newly proposed algorithm for efficient broadcasting in the IoT. Figure 1 gives a representation of the proposed algorithm that is cluster-based. Three kinds of nodes are present in the network; BS (represented as an Internet cloud in the figure), CH (performs aggregation of data from CNs), and CN (sensor nodes with limited energy). All nodes can be mobile or immobile, depending on the application used. CH use direct transmission to communicate to the BS/gateway. and CN used direct or multi-hop transmission to communicate to the CH in order to transmit any broadcast data (BD).

Algorithm 4 explains how two kinds of filters are used to perform efficient broadcasting in a large IoT network, as shown in Figure 3. The ISN is defined as the initial node that has some BD to transmit. The filter created by the ISN holds the IDs of its neighbors that are chosen based on the neighbor discovery procedure (explained in the neighbor discovery section). The broadcasting process is initiated by the ISN. The idea is to maintain a low broadcast overhead through avoiding retransmission of broadcast packets previously received. Before packet transmission, every node compares the received child neighbor filter (CNF) with its own CNF to avoid retransmission to common neighbors. The process of transmission continues until the CH of the cluster, that the ISN is a member of, receives an updated CNF. After reception, the CH will transmit the BD to the IDs contained in the head and gateway ID filter (HGIF). In this way, the broadcasting process is distributed among different clusters where each cluster will perform parallel broadcasting within its own cluster. In the next section, simulation results for this newly proposed algorithm are compared with a simple bloom-based broadcast algorithm. The results obtained show that the use of clusters is more efficient in terms of overhead, memory space, and energy usage.

Algorithm 4. Distributed bloom–based broadcast construction.
1: Each node discovers its neighbor using neighbor discovery procedure.
2: A list of neighbors is maintained at each CN in the form of a bloom filter, called as a Child Neighbor Filter (CNF)
3: A list of heads and gateway is maintained at each CH in the form of a bloom filter, called as a Head and Gateway ID Filter (HGIF)
4: A CH will maintained another filter, called as a Child Neighbor Filter (CNF)
5: Initial Source Node (ISN) is chosen randomly from CN.
6: ISN creates one filters: ISN.CNF
7: ISN broadcasts CNF and BD to its neighbors.
8: At receiving side,
9: if same neighbor? Yes then
10: Don’t send BD to same ID
11: else
12: Send BD to new ID
13: Update CNF1,
14: $UpdatedCNF = ReceivedCNF \oplus MyCNF$
15: Send updated CNF1 and BD to all uncommon neighbors
16: The process continues till CH receives updated CNF filter, CH.CNF
17: CH transmits BD to IDs of CH.HGIF
18: After reception, each CH function as ISN and repeats step 6
19: After every T-intervals, go to step 5 if node has BD

Figure 3.

Usage of bloom filters in distributed bloom–based broadcast.

Simulation results

In this section, an analysis of the proposed algorithm is performed. The simulation parameters and configuration are described below.

Simulation configuration

MATLAB is used to create a two-dimensional network of 400 nodes where nodes are randomly distributed over the area of 1000 m × 1000 m, as shown in Figure 4. In the proposed system model, a network is divided into four different clusters (each contains 100 CN) and each node in the network is identified by a unique ID. A CH is used as an intermediate node to provide a communication channel between sensor nodes and the gateway (i.e. BS), as shown in Figure 1. The cluster formation and CH selection are kept simple. The CHs are selected and located at the onset of the network. Every CH knows and keeps a record of the ID of its all children nodes using a bloom filter. The CHs are marked with a black cross in simulation scenario, as shown in Figure 4. Every new child will add itself to the nearest cluster and accordingly chooses the CH. Each CH maintains two filters, one for child information and another for a record of other CHs and the gateway (or BS). Each child maintains only one filter for neighbor information. The filter sizes are calculated by limiting the probability of a false positive to a maximum of 0.01, as shown in Table 1. The table also shows that the maximum number of filters (at any node) necessary for making forwarding decisions is different for both configurations. Each node has a neighbor separation of $d'$ in which it can communicate and define its neighbor list. Table 2 shows detailed simulation parameters. The simulation performs a broadcast transmission of data from a processing/sensing CN to every other node in a network and maintains 100% convergence. The results of the distributed bloom–based broadcasting algorithm is compared with the previously published bloom-based broadcasting¹¹ and a normal broadcasting algorithm.

Figure 4.

A simulation scenario of distributed bloom–based broadcast with random deployment of 400 nodes in an area of 1000 m × 1000 m.

Table 1.

Filter parameters.

Type of broadcasting	False positive	Size of filter (bits)	Number of filters	Total memory space (bits)
Bloom-based	0.01	4040	1	4040
Distributed bloom–based	0.01	1010	2	2020

Table 2.

Simulation parameters.

Parameter	Value
Area of simulation	1000 m × 1000 m
Number of nodes	$400$
Node deployment	Random
Filter size	Table 1
False positive probability	$0.01$
Neighbor separation (unclustered)	160 m
Neighbor separation (clustered)	100 m
Channel model	Free space $(η = 2)$
$E_{Tx_el}$ or $E_{Rx_el}$	$100 pJ / bit . m^{2}$
$E_{a}$	$50 nJ / bit$

The reduced memory requirement for filter storage, 50% less, for the distributed bloom algorithm demonstrates that it is more memory-efficient than the author’s previous bloom-based algorithm. The new algorithm is also evaluated in terms of network connectivity and optimal neighbor separation distance, overhead, and energy consumption. The proposed algorithm aims at reducing broadcast packet overhead while maintaining a reliable transfer of packets. The reduction in overhead leads to an energy-efficient transmission that helps battery operated sensor nodes to last longer. The proposed distributed bloom–based algorithm maintains a low average number of neighbors while maintaining 100% connectivity. This helps in less packet processing and therefore less energy consumption. For further evaluation, the distributed bloom–based algorithm is compared with LEBCP,²⁴ LERBT,²⁵ and the bloom-based algorithm proposed previously by Talpur et al.¹¹ The results are presented in Table 3.

Table 3.

Network density—average number of neighbors.

Number of nodes	LEBCP	LERBT	Bloom-based broadcast	Distributed bloom–based broadcast
50	9.187	7.180	1.58	−
100	19.635	14.584	4.58	1.93
150	29.452	22.495	13.22	3.45
200	39.270	30.445	25.285	4.97
250	49.087	37.292	35.476	6.23
400	−	−	38.5025	8.995

LEBCP: lightweight energy-efficient broadcast control protocol; LERBT: lightweight energy-efficient reliable broadcast tree.

Network connectivity and neighbor separation

Network connectivity is of key importance in a sensor network. It is important for a node to stay connected within a network to ensure that all nodes are receiving transmissions and are included in broadcast communications which are often used for network configuration purposes. The loss of network connectivity to any node can be hazardous and can result in total network failure. This issue is analyzed by varying the neighbor separation $d'$ parameter in a given network. In order to keep all nodes connected in a network, it is important to choose the neighbor separation parameter accurately. In a given broadcast situation, increasing the neighbor separation distance $d'$ creates a trade-off between overhead and node reachability. Figure 5 shows that (for unclustered bloom-based broadcast network), the smaller value of $d'$ creates less overhead within each cluster, but some nodes can be beyond the communication range, and this breaks the connection to that node in the network. However, the larger values of $d'$ provide 100% of network connectivity and full convergence but with increased overhead. This increase in overhead can be energy-expensive, but it assures that every node is connected (network is fully converged), and the broadcast update is available to every node. Therefore, it is important to maintain a proper balance between overhead and convergence through choosing an optimal value of neighbor separation distance. In the work presented here, a neighbor separation of 100 and 160 m is chosen for the clustered (distributed bloom–based filter) and unclustered network (bloom-based filter), respectively. Figure 6 proves that for a clustered network, smaller values of $d'$ are performing very well to converge network. This ultimately helps in lesser energy consumption.

Figure 5.

Maximum number of duplications obtained at any single node and percent of network converged versus neighbor separation for unclustured network.

Figure 6.

Percent of network converged versus neighbor separation for clustured network.

Overhead

To evaluate the network performance, the number of copies of duplicate packets is calculated that are received by N nodes. It tells about the number of times same data is received or duplicated at any particular node. In an ideal situation, the number of copies per node would be one; however, practically this is not possible. Figure 7 gives a comparison between the simple broadcast (non-bloom), bloom-based broadcast and the distributed bloom–based broadcast. It can be seen that the use of clusters helps to considerably reduce the number of duplicated data packets. It minimizes the overhead introduced by broadcasting and packet duplication from thousands to hundreds and from hundreds to tens in some cases.

Figure 7.

Broadcast overhead or number of duplications of data packet (including filters) at a node.

Energy consumption

In order to calculate the total energy expenditure of the network, the energy required for packet transmission and reception is calculated and discussed in “Radio model” section. The energy used in processing and sensing is not included to simplify the evaluation process. Energy dissipated by the electronics is given in Table 2.

Figure 8 shows the total energy consumed by a sensor node in transmission and reception. This shows the energy expended by a normal (non-bloom) broadcast algorithm, bloom-based broadcast, and the distributed bloom–based broadcast. It shows that the energy consumed in the distributed bloom–based algorithm is 1/100 and 1/10 compared to the normal non-bloom broadcast and bloom-based broadcast techniques, respectively. Optimizing the decision for data forwarding keeps unwanted reception of the same data to a minimum. This results in an energy-efficient transmission and increases the lifetime of battery powered nodes.

Figure 8.

Total energy consumed by a node in transmission and reception.

Conclusion

Broadcasting is very common in distributed IoT networks and serves as a robust and effective source for transmitting update and configuration data. However, broadcasting can result in serious overhead problems in an IoT network. Controlling the redundancies of rebroadcasting can help in limiting this overhead problem. This article presents a space-efficient data structure using a bloom filter to help maintain a set of node IDs in the form of a vector of bits to allow intelligent forwarding decision to be made for BD so that reliably communications can be maintained for every node of the network while reducing duplicate packet retransmission.

The distributed bloom–based network outperforms other broadcasting algorithms, both non-bloom-based and bloom-based, by minimizing the overhead and duplication of packets from hundreds to tens, and tens to units. Introducing the idea of clustering with a bloom filter has reduced memory storage to almost half when compared to non-cluster bloom filter algorithms. The reduction in the duplication of packets is an energy-efficient solution in minimizing data transmission cost and improving system lifetime. The proposed structure does not require any control information from a central system in order to operate. It can operate effectively in a distributed IoT network and is independent from network global parameters. This algorithm also facilitates parallel broadcasting in each cluster using a small number of filter bits. The distributed bloom filter algorithm is an extension of the bloom algorithm published in the study of Talpur et al.,¹¹ and it has reduced energy consumption by a factor of 1/10. When compared to non-bloom broadcasting algorithms, like LEBCP,²⁴ LERBT,²⁵ it reduces energy consumption by a factor of 1/100. In addition to this, unwanted duplication of packets at each node is minimized thereby improving network performance and packet delivery times.

Footnotes

Acknowledgements

The authors thank the Science and Technology Unit at Umm Al-Qura University for their continued logistics support.

Handling Editor: Sang-Woon Jeon

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by grant number 10-INF1236-10 from the Long-Term National Plan for Science, Technology and Innovation (LTNPSTI) and the King AbdulAziz City for Science and Technology (KACST), Kingdom of Saudi Arabia.

References

Ashton

That “Internet of things” thing in the real world, things matter more than ideas. RFID J 2009, http://www.rfidjournal.com/articles/pdf?4986

Vermesan

Friess

Guillemin

et al . Internet of things strategic research roadmap. In: Vermesan

Friess

(eds) Internet of things: global technological and societal trends, vol. 1. Aalborg: River Publishers, 2011, pp.9–52.

International Telecommunication Union. ITU internet report: the internet of things. Geneva: International Telecommunication Union, 2005.

Al-Fuqaha

Guizani

Mohammadi

et al . Internet of things: a survey on enabling technologies, protocols, and applications. IEEE Commun Surv Tut 2015; 17(4): 2347–2376.

Sethi

Sarangi

SR.

Internet of things: architectures, protocols, and applications. Journal of Electrical and Computer Engineering 2017; 2017: Article ID 9324035.

Shaikh

Zeadally

Exposito

Enabling technologies for green internet of things. IEEE Syst J 2015; 11: 983–994.

Chang

Liu

Controlled flooding search in a large network. IEEE ACM T Network 2007; 15(2): 436–449.

Zhao

Shen

Jiang

et al . Broadcasting with least redundancy in wireless sensor networks. Int J Distrib Sens N 2012; 2012: 957606.

Zhao

Wen

Liu

et al . Maximum life-time localized broadcast routing in MANET. In: Li

Jesshope

Jin

et al . (eds) Network and parallel computing, NPC 2007: lecture notes in computer science, vol. 4672. Berlin: Springer, 2007, pp.193–202.

10.

Healy

Newe

Lewis

. Power management in operating systems for wireless sensor nodes. In: 2007 IEEE sensors applications symposium, San Diego, CA, 6–8 February 2007, pp.1–6. New York: IEEE.

11.

Talpur

Newe

Shaikh

et al . Bloom filter based data collection algorithm for wireless sensor networks. In: 2017 international conference on information networking (ICOIN), Da Nang, Vietnam, 11–13 January 2017, pp.354–359. New York: IEEE.

12.

Bloom

BH.

Space/time trade-offs in hash coding with allowable errors. Commun ACM 1970; 13(7): 422–426.

13.

Moller

Newe

Lochmann

Prototype of a secure wireless patient monitoring system for the medical community. Sensor Actuat A: Phys 2012; 173(1): 55–65.

14.

Akkaya

Senel

McLaughlan

Clustering of wireless sensor and actor networks based on sensor distribution and connectivity. J Parallel Distrib Comput 2009; 69(6): 573–587.

15.

Lakhlef

Raynal

Bourgeois

. Efficient broadcast protocol for the internet of things. In: 2016 IEEE 30th international conference on advanced information networking and applications (AINA), Crans-Montana, 23–25 March 2016, pp.998–1005. New York: IEEE.

16.

Floyd

Jacobson

Liu

et al . A reliable multicast framework for light-weight sessions and application level framing. IEEE ACM T Network 1997; 5(6): 784–803.

17.

Tseng

Chen

et al . The broadcast storm problem in a mobile ad hoc network. In: ACM/IEEE international conference, MobiCom, Seattle, WA, 15–19 August 1999, pp.151–162. New York: ACM.

18.

Guo

. Broadcasting for network lifetime maximization in wireless sensor networks. In: IEEE SECON 2004, Santa Clara, CA, 4–7 October 2004, pp.352–358. New York: IEEE.

19.

Kyasanur

Choudhury

Gupta

. Smart gossip: an adaptive gossip-based broadcasting service for sensor networks. In: 2006 IEEE international conference on mobile ad hoc and sensor systems (MASS), Vancouver, BC, Canada, 9–12 October 2006, pp.91–100. New York: IEEE.

20.

Miller

Sengul

Gupta

. Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks. In: Proceedings of the 25th IEEE international conference on distributed computing systems, 2005 (ICDCS 2005), Columbus, OH, 6–10 June 2005, pp.17–26. New York: IEEE.

21.

Haas

Halpern

Gossip-based ad hoc routing. IEEE ACM T Network 2006; 14(3): 479–491.

22.

Hong

Scaglione

Energy-efficient broadcasting with cooperative transmissions in wireless sensor networks. IEEE T Wirel Commun 2006; 5(10): 2844–2855.

23.

Kumar

Wong

. A variable preamble length-based broadcasting scheme for wireless sensor networks. In: 7th international conference on WiCOM, Wuhan, China, 23–25 September 2011. New York: IEEE.

24.

Zeng

Yao

. An energy-efficient broadcast control protocol for wireless sensor networks. In: IEEE international conference on NAS 2009, Hunan, China, 9–11 July 2009, pp.3–8. New York: IEEE.

25.

Tang

Wang

. A lightweight energy-efficient reliable broadcast tree for wireless sensor networks. In: 2011 3rd international conference on ICCRD, Shanghai, China, 11–13 March 2011, vol. 1, pp.373–378. New York: IEEE.

26.

Rothenberg

Macapuna

CAB

Verdi

et al . The deletable bloom filter: a new member of the bloom family. IEEE Commun Lett 2010; 14(6): 557–559.

27.

Mun

Lim

New approach for efficient IP address lookup using a bloom filter in Trie-based algorithms. IEEE T Comput 2016; 65(5): 1558–1565.

28.

Lim

Lee

Yim

et al . Reducing false positives of a bloom filter using cross-checking bloom filters. Appl Math Inform Sci 2014; 8(4): 1865–1877.

29.

Lim

Lee

et al . On adding bloom filters to longest prefix matching algorithms. IEEE T Comput 2014; 63(2): 411–423.

30.

Bonomi

Mitzenmacher

Panigrahy

et al . An improved construction for counting bloom filters. In: 14th conference on annual European symposium. ESA’06, Zurich, 11–13 September 2006, pp.684–695. New York: ACM.

31.

Song

Hao

Kodialam

et al . IPv6 lookups using distributed and load balanced bloom filters for 100Gbps core router line cards. In: INFOCOM 2009, Rio de Janeiro, Brazil, 19–25 April 2009, pp.2518–2526. New York: IEEE.

32.

Rottenstreich

Kanizo

Keslassy

The variable-increment counting bloom filter. IEEE ACM T Network 2014; 22(4): 1092–1105.

33.

Kanizo

Hay

Keslassy

Access-efficient balanced bloom filters. Comput Commun 2013; 36(4): 373–385.

34.

ul Huque

MTI

Munasinghe

Abolhasan

et al . Sea-ban: semi-autonomous adaptive routing in wireless body area networks. In: 2013 7th international conference on ICSPCS, Carrara, VIC, Australia, 16–18 December 2013, pp.1–7. New York: IEEE.

35.

Jose

DV.

A cluster based routing technique to enhance the lifetime of wireless sensor networks. Int J Comput Appl 2017; 167(3): 35–39.

36.

Wang

Song

A distributed cluster-based algorithm in wireless sensor networks. In: 2009 fourth international conference on Frontier of computer science and technology, Shanghai, China, 17–19 December 2009, pp.733–737. New York: IEEE.

37.

Qing

Zhu

Wang

Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks. Comput Commun 2006; 29(12): 2230–2237.