Broadcasting with Least Redundancy in Wireless Sensor Networks

Abstract

In wireless sensor networks (WSN), broadcasting could allow the nodes to share their data efficiently. Due to the limited energy supply of each sensor node, it has become a crucial issue to minimize energy consumption and maximize the network lifetime in the design of broadcast protocols. In this paper, we propose a Broadcast Algorithm with Least Redundancy (BALR) for WSN. By identifying the optimized number of induced forwarders as 2, BALR establishes a weighted sum model, taking both rebroadcast efficiency and residual energy into consideration, as a new metric to compute the self-delay of the nodes before rebroadcasting. BALR further incorporates both strategies based on distance and coverage degree which means the number of neighbors that have not yet received the broadcast packet, to optimize the rebroadcast node selections. To reveal the performance bounds, rebroadcast ratios in the ideal and worst case are theoretically analyzed, indicating that the rebroadcast ratio of BALR decreases with the increase of node density. BALR can significantly prolong the network lifetime of WSN and is scalable with respect to network size and node density, as demonstrated by simulations.

1. Introduction

Wireless sensor networks (WSN) are envisioned as consisting of a number of static sensor nodes that are densely deployed over a region of interest. A wide variety of applications of such networks include inventory managing, disaster areas monitoring, patient assisting, water quality monitoring, target tracking, and health monitoring of civil infrastructures. Recent advances in wireless communications and electronics have enabled the development of such low-cost sensor networks. Unfortunately, wireless sensor nodes, which are generally microelectronic devices, could only be equipped with limited power sources. Therefore, energy efficiency is of particular importance in WSN [1–4].

Broadcasting is a common means for nodes in WSN to efficiently share their data with each other. Broadcasting could be utilized to initialize the network configuration for network discovery, discover multiple routes between a given pair of nodes, and query for a piece of desired data in a network [5]. In WSN, broadcasting could also be served as an efficient approach for sensors to share their local measurements with each other. A straightforward way of broadcasting is the so-called flooding, under which each node will rebroadcast when it receives the broadcast packet for the first time. Although attractive for its simplicity, flooding will cause serious broadcast redundancy, packets collision, and bandwidth waste, referred to as broadcast storm problems [2]. An efficient broadcast strategy should be able to effectively reduce the broadcast redundancy, for both energy and bandwidth efficiency, especially in a band and power limited sensor networks.

With the aim of solving the broadcast storm problems and maximizing the network lifetime, we propose a Broadcast Algorithm with Least Redundancy (BALR) for wireless sensor networks, which possess the following properties.

Scalable Algorithm

Scalability is a critical issue for sensor networks which is composed of thousands of densely deployed nodes. BALR is designed in mind with the goal of obtaining satisfying broadcast performance in a high-density and large-scale network. With BALR, the number of saved rebroadcasts increases with the increase of the network node density.

Localized Algorithm

Each node makes the decision of rebroadcast according to its one-hop local information. BALR needs not maintain any global topology information at each node, thus the overhead is small.

Energy-Efficient Approach

BALR cuts down the total energy consumption by reducing the redundancy of rebroadcast effectively which is also capable of relieving the broadcast storm problems significantly. To maximize network lifetime, BALR balances the energy consumption among all nodes when rebroadcast nodes are selected.

This paper is organized as follows. In Section 2, we analyze existing related works in the literature. In Section 3, we discuss system model and optimized number of forwarders in WSN. Based on the system model, our proposed Broadcast Algorithm with Least Redundancy (BALR) and its performance analysis are presented in Sections 4 and 5, respectively. We present computer simulation results in Section 6 for performance verification before concluding with Section 7.

2. Related Works

There have been a number of existing works on the broadcast storm problem of wireless multihop networks in the literature. In [3, 4, 6], each node computed a local cover set, consisting of as fewer neighbors as possible, to provide its whole 2-hop coverage area by exchanging connectivity information with its neighbors. However, each node in these works is required to update the information of its k-hop ( $k\ge 2$ ) neighbors, resulting in a heavy overhead and prohibited energy consumption. Some other works [2, 6] concentrated on forward node selection based on probabilistic approach. Nonetheless, the reachability under such strategies may not be guaranteed.

Among related works in the literature, many proposed energy-efficient broadcast protocols are centralized, of which the topology of the whole network is required. Various protocols are proposed to search the minimizing energy cost of the broadcast tree. The authors of [7–9] accomplished the searching based on geometry or graph of the network. Alternatively, a connected dominating set (CDS) could be constructed, and only permitting nodes which belong to the CDS are allowed to rebroadcast packets. To minimize the overhead of broadcast, various strategies reducing the size of CDS were investigated in [10–16].

Since the centralized approach needs much more overhead in WSN, alternative localized algorithms have been proposed [17–21]. Under such protocols, each node establishes the network topology in a distributed way [18]. In [19, 20], each node should be aware of the geometry within its 2-hop neighborhood range. In order to ameliorate broadcasting, [10] utilize the information of all nodes that have been visited by the broadcast message. The authors of [16] proposed an algorithm suitable for a dynamic mobile Ad Hoc network, which did not require neither the k-hop neighbors information nor the entire network topology. To reduce the broadcast overhead, [21] proposed a Maximum Life-time Localized Broadcast (ML²B) protocol, of which the information of only one-hop neighbors was required. ML²B utilized the number of neighbors that have not received the broadcast message to reduce the rebroadcast redundancy.

Some broadcast mechanisms designed based on the features of WSN have been proposed recently [20–30]. In [20], two types of broadcasting protocols for WSN, called one-to-all and all-to-all broadcasting, were proposed. Both protocols are suitable for fixed and regular WSN topologies. An energy-efficient broadcasting strategy based on cooperative transmission was investigated in [23]. The cooperation was provided through a system, called Opportunistic Large Array (OLA), in which network broadcasting was accomplished by signal processing techniques at the physical layer. Some works [5, 24, 25] dealt with the query execution in large sensor networks. Their purpose is not to broadcast a packet to the whole network but to obtain or locate data or services for nodes within a large population, high-density WSN based on network partial broadcast. Several robust data delivery protocols [26–28] have been proposed for large sensor networks to disseminate data to interested sensors.

This paper focuses on the broadcasting strategy for WSN to efficiently forward a broadcasted packet from broadcast originator to all other nodes in the network. By identifying the optimized number of induced forwarders as 2, a broadcasting algorithm with least redundancy (BALR) is proposed, which optimizes broadcasting by reducing redundant rebroadcasts and balancing energy consumption among all nodes. In [29], a broadcast protocol for sensor networks (BPS) was proposed, which utilized an adaptive-geometric approach that enables a considerable reduction of retransmissions by maximizing each hop length. Simulation results regarding the rebroadcast ratio demonstrate the feasibility of applying adaptive-geometric approach to WSN broadcasting. Based on [29], the authors extended the ideas of BPS for broadcasting in the energy-constrained network consisting of nodes that sleep and wake up alternatively in [30]. And they proposed a protocol called Activecast to effectively transmit a packet to all active (awake) nodes in the network. However, this paper does not consider the WSN consisting of nodes that sleep and wake up alternatively but considers the homogeneous WSN consisting of nodes that have the identical transmission range and that are always active until their battery exhaustion. Furthermore, most of these literatures focus on rebroadcast ratio performances, without looking at the network lifetime which is one of the main design purposes for any broadcast schemes. Motivated by the optimized selection of induced forwarder, BALR establishes a weighted sum model, taking both rebroadcast efficiency and residual energy into consideration, as a new metric to compute the self-delay of the nodes before rebroadcasting. BALR further incorporates both strategies based on distance and coverage-degree, to optimize the rebroadcast node selections; thus, its scalability and high energy-efficiency being achieved. Besides, as each node makes the decision of rebroadcast according to only its one-hop local information, BALR is a localized algorithm.

3. System Model

A wireless sensor network can be abstracted as a graph $G(V,E)$ , in which V is the set of all the nodes in the network and E consists of edges in the graph. r is the radius of the coverage of each node. We assume that all links in the graph are bidirectional, the graph is in a connected state, and eachnodehasacircularcoveragearea. Given a node i, time t is set as zero when it receives the broadcasted packet for the first time. The residual energy of node i is $e(i,t)$ .

In particular, we use the radio transmission energy model as in [31]. To transmit a k bits packet over a distance d, the radio expends energy of

$$\begin{array}{cc}& E_{Tx}=E_{\text{elect}}·k+{\epsilon }_{\text{amp}}·k·d^{\mathrm{2}}\end{array}$$

(1)

and to receive this packet, the radio expends

$$\begin{array}{cc}& E_{Rx}=E_{\text{elect}}·k,\end{array}$$

(2)

where $E_{\text{elect}}$ is 50 nJ/b to run the transmitter circuitry, and ${\epsilon }_{\text{amp}}$ is 100 pJ/b/m² for the transmit amplifier to achieve an acceptable signal-to-noise ratio.

As location is more important than a specific node's ID in WSN, location awareness is necessary to make the sensor data meaningful. The proposed BALR utilizes geographic location to make localized broadcast decisions. Each node is required to be aware of only the positions of its one-hop neighbors.

3.1. Optimized Number of Induced Forwarders

Given a forward node that has done the rebroadcast, its neighbors that do the rebroadcast after hearing the rebroadcast from it are called its induced forwarders. To reduce the rebroadcast redundancy, the number of induced forwarders of each forward node should be minimized.

During the broadcast of a packet, as shown in Figure 1, a forward node S rebroadcasts a broadcast packet received from its preceding node U. Then its induced forwarders are chosen from its neighbors locally by themselves. Lastly the induced forwarders of S will do the rebroadcast as their preceding node S. Let n be the number of the induced forwarders of a forward node. We use $I_{\mathrm{1}},I_{\mathrm{2}},\dots ,I_n$ to represent n induced forwarders of S. The induced coverage region of node S consists of added coverage regions of the n induced forwarders and that of node U, which is the shadowed region in Figure 1.

Figure 1

Selection of induced forwarders. The shadowed regions are the induced coverage region of node S.

To obtain a high coverage ratio of broadcast, large n is desired. But large n also leads to much redundant rebroadcasts. Therefore, an optimal n is required to obtain a satisfying delivery ratio and as fewer rebroadcasts as possible.

For $n=\mathrm{1}$ , as shown in Figure 1(a), due to the limited number of induced forwarders, the induced coverage region of a node is geometrically unbalanced, resulting in an unbalanced coverage and incomplete delivery in the network. For $n\ge \mathrm{2}$ , as shown in Figures 1(b) and 1(c), when the n induced forwarders and the preceding node of the forwarder are equally located at the edge of the coverage region of the forwarder node, the induced coverage region is symmetric and balanced [32]. As what will be seen later in Figure 2, full deliveries throughout the network could be guaranteed. The size of the superposition areas of the coverage areas of nodes' rebroadcast reflects the efficiency of the broadcast. The larger the size of the superposition areas, the lower the broadcast efficiency is. The size of the superposition areas in Figure 1(c) is much larger than that in Figure 1(b), resulting in a lower broadcast efficiency. For $n>\mathrm{3}$ , the size of the superposition areas is further larger than that of $n=\mathrm{3}$ . Thus, the broadcast efficiency with $n=\mathrm{2}$ is higher than that with $n\ge \mathrm{3}$ .

Figure 2

Path for delivering the broadcast packet in ideal conditions using BALR.

When two induced forwarders are selected as in Figure 1(b), the network could obtain a satisfying delivery ratio with the highest broadcast efficiency [32]. Therefore, BALR optimizes a number of the induced forwarders by setting $n=\mathrm{2}$ , as shown in Figure 1(b).

3.2. Ideal Coordinates of Induced Forwarders

Let $(x_s,y_s)$ and $(x_u,y_u)$ be the locations of node S and that of preceding node U in Figure 1(b). Then $l=\sqrt{(x_s-x_u{)}^{\mathrm{2}}+(y_s-y_u{)}^{\mathrm{2}}}$ is the distance between node S and U. The coordinates of two ideal induced forwarders ( $I_{\mathrm{1}}$ and $I_{\mathrm{2}}$ in of Figure 1(b)) for $n=\mathrm{2}$ can be obtained by solving the following two equations:

$$\begin{array}{cc}& {\left(x-x_s\right)}^{\mathrm{2}}+{\left(y-y_s\right)}^{\mathrm{2}}=r^{\mathrm{2}},\\ {\left(x-x_u\right)}^{\mathrm{2}}+{\left(y-y_u\right)}^{\mathrm{2}}={\left(\frac{l+r}{\mathrm{2}}\right)}^{\mathrm{2}}+\frac{\mathrm{3}{r}^{\mathrm{2}}}{\mathrm{4}}.\end{array}$$

(3)

When transmitting node S is the broadcast originator, there are three optimized (ideal) locations for $n=\mathrm{2}$ , that is, $(x_s-r,y_s)$ , $\hspace{0.17em}\hspace{0.17em}(x_s+r/\mathrm{2},y_s-r\sqrt{\mathrm{3}}/\mathrm{2})$ , and $(x_s+r/\mathrm{2}$ , $y_s+r\sqrt{\mathrm{3}}/\mathrm{2})$ . On the other hand, if the transmitting node S is a forward node, there are two ideal locations, that is, ( $x_{\mathrm{1}}$ , $y_{\mathrm{1}}$ ) and ( $x_{\mathrm{2}}$ , $y_{\mathrm{2}}$ ), which are calculated by solving (3).

4. Broadcasting with Least Redundancy (BALR)

As discussed in the previous section, nodes forward the broadcasted packet following patterns shown in Figure 1(b). Ideally, as shown in Figure 2, the broadcast packet is delivered along hexagons with edge length equal to the radius of the coverage of each node. And all rebroadcast nodes are located at vertices of the hexagons which are called ideal locations. To determine the ideal locations, each broadcasted packet contains a field $\hspace{0.17em}\hspace{0.17em}A\hspace{0.17em}\hspace{0.17em}$ in its header. Whenever a node forwards a broadcast packet, it fills in A the position of the node from which it received the packet.

4.1. Weighted Sum Metric for Self-Delay

Nonetheless, in practical situations, nodes may not be located at ideal points. Naturally the nodes nearest to the ideal locations are selected as forwarders. However, this scheme would lead to the situation that nodes located at the ideal or quasi-ideal locations are exhausted rapidly with respect to energy. We hence propose to take energy metric into consideration, besides the location metric, for forwarder selections. BALR incorporates these two metrics together to form a new metric, via following a weighted sum model (SMD), and utilizes the self-delay mechanism to complete the rebroadcast node selection:

$$\begin{array}{cc}& D\left(i\right)=D_m\left(\alpha ·\frac{l\left(i,t\right)}{r}+\beta ·\frac{\left[E^{\prime }-e\left(i,t\right)\right]}{E^{\prime }-E_T}\right),\end{array}$$

(4)

where $D(i)$ denotes self-delay of node i before rebroadcasting, $D_m$ is the permitted maximum delay, $l(i,t)$ is the distance from node i to the nearer ideal location at time t, $E^{\prime }$ is the initial maximum energy of each node, and $E_T$ is the energy threshold which is used to prevent nodes with little energy from dying. If the residual energy at a node is smaller than $E_T$ , it refuses to forward the broadcasted message. α and β denote the relative weights of importance of the location and residual energy of the node, respectively, that is, $\alpha +\beta =\mathrm{1}$ , $\mathrm{0}\le \alpha \le \mathrm{1}$ , and $\mathrm{0}\le \beta \le \mathrm{1}$ .

When forall node i receives the broadcasted packet for the first time, it defers a period of $D(i)$ before its attempt to do the rebroadcast. During the interval of $\mathrm{0}\le t\le D(i)$ , node i could abandon its attempt to rebroadcast as soon as either rebroadcast efficiency is low or residual energy is insufficient. The self-delay mechanism selects nodes with small $D(i)$ as rebroadcast ones with high priority. Based on the weighted sum metric for self-delay as shown by formula (4), the nodes nearest to the ideal locations with enough residual energy would be selected by BALR with the specified relative weights α and β, depending on specific applications.

Clearly there is a tradeoff between rebroadcast efficiency and network lifetime based on our new metric. In practice, we could regulate the tradeoff by adjusting the relative weights α and β. In addition, the tradeoff between broadcast reachability and network lifetime could be regulated by adjusting the threshold $E_T$ .

Based on the new metric, our protocol further reduces the rebroadcast redundancy by incorporating both strategies based on distance and coverage degree as follows.

4.2. Strategy Based on Distance

We propose to reduce the rebroadcast redundancy by confining the location of quasi-forwarders. More specifically, only neighbors within a specified distance $l_T$ from one of the ideal locations are allowed to rebroadcast. Intuitively, $l_T$ would decrease as the node density increases, which corresponds to a high density and large WSN. The value of $l_T$ could be determined by the surrounding node density. Let D denotes the node density, that is, the average number of nodes per region of $r\times r$ . When nodes are placed in a grid pattern, the smallest distance between two neighbor nodes is $\sqrt{r^{\mathrm{2}}/D}$ . $l_T$ could be computed as follows:

$$\begin{array}{cc}& l_T=\{\begin{array}{cc}r,\hfill & \mathrm{0}\le D<a^{\mathrm{2}},\hfill \\ a\sqrt{\frac{r^{\mathrm{2}}}{D}},\hfill & a^{\mathrm{2}}\le D,\hfill \end{array}\end{array}$$

(5)

where a is a constant.

4.3. Strategy Based on Coverage Degree

It is noted that a node might receive a broadcast packet several times from different nodes in different directions, leading to redundant rebroadcasts. Define coverage degree as the number of neighbors that have not received the broadcast packet yet. Note that the coverage degree implies the rebroadcast efficiency of a node. To minimize rebroadcasts, we propose to have each node maintain its coverage degree, and rebroadcast only when its coverage degree is above the threshold $d_T$ . Definitely there is a tradeoff between the rebroadcast redundancy and reachability via the threshold $d_T$ . High threshold $d_T$ may be superior for its rebroadcast efficiency, though probably lead to poor reachability. On the other hand, low threshold $d_T$ will affect the performance the other way round. For example, in large-scale WSN with nodes densely deployed, high threshold $d_T$ should be selected to avoid highly redundant rebroadcasts.

4.4. Broadcasting Algorithm with Least Redundancy

Let s and $P_s$ be the broadcast originator and the packet broadcasted froms, respectively. In addition, we define several variables for forall $i\in V$ as follows.

• (i)

Neighbor $nb(i)$ denotes a one-hop neighbor of node i.

(ii)

Neighbor set $NB(i)$ denotes the set of all one-hop neighbors of node i.

(iii)

Uncovered set $UC(i,t)$ consists of one-hop neighbors that have not been covered, at time t.

(iv)

Coverage degree $d(i,t)$ is the number of nodes belonging to $UC(i,t)$ at t. $d(i,t)$ implies the rebroadcast efficiency of node i. If $d(i,t)$ is below a threshold before its attempt to do the rebroadcast, node i would not rebroadcast.

(v)

Preceding node $u(i,t)$ is the $nb(i)$ that sent the broadcast packet to node i at time t   $(\mathrm{0}\le t\le D(i))$ ( $D(i)$ is the self-delay of node i). During the period of $\mathrm{0}<t\le D(i)$ , node i may receive several copies of the same broadcast packet from different preceding nodes.

(vi)

Preceding node set $U(i,t)$ is the set of all preceding nodes of node i before time t. If it has received the same broadcast packet for k times before time $t\hspace{0.17em}\hspace{0.17em}(t\le D(i))$ , its preceding node set can be expressed as

$$\begin{array}{cc}& U\left(i,t\right)=\left\{u\left(i,t_{\mathrm{0}}\right),u\left(i,t_{\mathrm{1}}\right),u\left(i,t_{\mathrm{2}}\right),\dots ,u\left(i,t_{k-\mathrm{1}}\right)\right\},\end{array}$$

(6)

where $t_{\mathrm{0}},t_{\mathrm{1}},t_{\mathrm{2}},\dots$ , and $t_{k-\mathrm{1}}\hspace{0.17em}\hspace{0.17em}(t_{k-\mathrm{1}}\le t)$ record the time node and i receives the 1st, 2nd, 3rd, …, and kth copy $(k\ge \mathrm{1})$ of the same broadcast packet.

For $\forall u(i,t_j)\in U(i,t)$ , $j\in \{\mathrm{0,1},\dots ,k-\mathrm{1}\}$ , node i will update its uncovered set $UC(i,t_j)$ when it receives the broadcasted packet $P_s$ form $u(i,t_j)$ . It is noted that the A field of $P_s$ shows the position of $u(u(i,t_j),\mathrm{0})$ , which is a preceding node of $u(i,t_j)$ . Based on the A field of $P_s$ and the locally obtained position of $u(i,t_j)$ , node i updates $UC(i,t_j)$ by deleting nodes that are covered by $u(u(i,t_j),\mathrm{0})$ and $u(i,t_j)$ as shown by Figure 3. Therefore, node i could calculate its new coverage degree $d(i,t_j)$ . Node i increases j by one each time it receives another repeated $P_s$ , and $d(i,t_j)$ decreases with the increase of j. During the interval of self-delay, node i could abandon its attempt to rebroadcast as soon as $d(i,t_j)\le d_T$ , thus reducing the rebroadcast redundancy and energy consumption efficiently.

Figure 3

Node i obtains $UC(i,t_{j-\mathrm{1}})$ by deleting the six neighbors covered by the shaded regions from $UC(i,t_{j-\mathrm{1}})$ .

Following the previous discussion, our proposed Broadcast Algorithm with Least Redundancy (BALR) for forall $i\in (V-\{s\})$ is summarized in Algorithm 1.

Algorithm 1:Algorithm description. Broadcast Algorithm with Least Redundancy (BALR).

(1) Initialization: $j=-\mathrm{1},U(i,\mathrm{0})=\mathrm{\varnothing },UC(i,\mathrm{0})=NB(i)$

(2) if node i has received packet $P_s$ , go to step 3

  else if $j\ge \mathrm{0}$ , go to step 7

    else the node is idle, stay in step 2

(3) if   $P_s$ is a new packet, go to step 4

  else node i has received repeated $P_s$ , let $j=j+\mathrm{1}$ , and go to step 5

(4) node i has received the broadcast packet $P_s$ for the first time. Let $t=\mathrm{0},j=\mathrm{0}$

   where j indicates the times of the repeated reception of $P_s$

   if   $e(i,t)<E_T$ , node i abandons its attempt to rebroadcast, and go to step 8

   else if    $l(i,t)<l_T$ , go to step 5

    else node i abandons the rebroadcast, then go to step 8

(5) Let $t_j=t,u(i,t_j)=p_{t_j},U(i,t)=U(i,t)\cup \{u(i,t_j)\}$ , where $p_{t_j}$ is the preceding

  node of node i at time $t_j$

(6) node i updates its uncovered set $UC(i,t_j)$ by deleting nodes that are covered

  by $u(u(i,t_j),\mathrm{0})$ and $u(i,t_j)$ , and calculate its new coverage degree $d(i,t_j)$

  if   $d(i,t_j)\le d_T$ , it abandons its attempt to rebroadcast, and go to step 8

  else if $j>\mathrm{0}$ , go to step 7

    else delay the rebroadcast by $D(i)$ based on formula (4)

(7) Check current time t:

  if   $t<D(i)$ , go to step 2

  else update the A field of $P_s$ by the position of $u(i,\mathrm{0})$ and rebroadcasts $P_s$

(8) end

We remark that our BALR maximizes the lifetime of WSN by minimizing redundant rebroadcast and balancing the broadcast energy consumption of neighborhood. It utilizes the node self-delay scheme to reduce the redundancy of nodes' rebroadcast and energy consumption. This scheme guarantees that nodes with smallest distance from the ideal location and satisfying value of residual energy are self-selected as rebroadcast nodes. To further minimize the redundant rebroadcast, each node i tracks its coverage-degree $d(i,t)$ continually, which manifests accurately the rebroadcast efficiency of the node. $d(i,t)$ is determined as one of the main criterions for deciding whether to rebroadcast the packet. The other two criterions include distance from the nearest ideal location and residual energy. The cell-like hexagonal routes for broadcast packet delivery and three criterions for deciding whether to rebroadcast the packet constitute the rationales behind BALR.

5. Performance Analysis of BALR

5.1. Definitions

• (i)

C is the area of the entire network.

(ii)

D is the node density of the network, which is the average number of nodes per region of $r\times r$ .

(iii)

g is the total number of all nodes in the network.

(iv)

h is the number of nodes that have rebroadcasted the packet after their reception of the packet in the network.

(v)

R is the rebroadcast ratio, which is the ratio of the number of nodes that have rebroadcasted the packet to the number of nodes in the entire network.

Based on the above definitions, we get

$$\begin{array}{cc}& R=\frac{h}{g},\\ g=C\frac{D}{r^{\mathrm{2}}}.\end{array}$$

(7)

5.2. Efficiency of the Broadcast Protocol

Rebroadcast ratio R manifests the efficiency of the broadcast protocols. R is inversely proportional to the broadcast efficiency. Large R results in a much redundant rebroadcast and low broadcast efficiency. Let $R_i$ and $R_w$ be the rebroadcast ratios of the proposed algorithm in the ideal case and in the worst case. The values of $R_i$ and $R_w$ could reveal the performance bounds of the broadcast algorithm.

Firstly we analyze the ideal efficiency of BALR, which is determined by the minimum rebroadcast ratio under the ideal conditions. Based on the formula (7), we get

$$\begin{array}{cc}& R=\frac{h{r}^{\mathrm{2}}}{CD}.\end{array}$$

(8)

For a given sensor network, where values of C, D, and r are determinate, different broadcast protocols result in different values of h. From formula (8), we get that the rebroadcast ratio is determined by h, which is the number of nodes that have done the rebroadcast in the network. To obtain the minimum R in BALR, h should be minimized. Under ideal conditions, the network area is divided into many hexagons where, in each vertex, there is one node doing the rebroadcast. The side length of each hexagon in the network is equal to the radius of the coverage of each node. Then the number of hexagons in the entire network can be approximated as $\lceil \mathrm{2}C/(\mathrm{3}\sqrt{\mathrm{3}}{r}^{\mathrm{2}})\rceil$ . Under ideal conditions, rebroadcast occurs at each vertex of hexagons, where each vertex locates at the ideal location. Each vertex belongs to three connected hexagons. Let $h_i$ be the number of nodes that do the rebroadcast under ideal conditions, we have

$$\begin{array}{cc}& h_i\approx \mathrm{2}·\lceil \frac{\mathrm{2}C}{\mathrm{3}\sqrt{\mathrm{3}}{r}^{\mathrm{2}}}\rceil .\end{array}$$

(9)

Then the minimum R can be formulated as

$$\begin{array}{cc}& R_i=\frac{\mathrm{2}{r}^{\mathrm{2}}·\lceil \mathrm{2}C/\left(\mathrm{3}\sqrt{\mathrm{3}}{r}^{\mathrm{2}}\right)\rceil }{CD}.\end{array}$$

(10)

When C is much larger than $\mathrm{3}\sqrt{\mathrm{3}}{r}^{\mathrm{2}}/\mathrm{2}$ , $R_i$ can be approximated as

$$\begin{array}{cc}& R_i\approx \frac{\mathrm{4}}{\mathrm{3}\sqrt{\mathrm{3}}D}.\end{array}$$

(11)

From the above analyses, the minimum rebroadcast ratio $R_i$ is obtained. $R_i$ is dependent on the node density D. $R_i$ decreases as the node density D increases. From formula (11), we get the ideal broadcast efficiency of BALR.

Then, we examine the efficiency and rebroadcast ratio of the proposed broadcast protocol under the worst conditions. As shown in Figure 4, after a forward node S firstly receives the broadcast packet from its preceding node U, it rebroadcasts the packet. Only $nb(S)$ located in the two limited regions $C_{\mathrm{1}}$ and $C_{\mathrm{2}}$ , which are the shadow regions around $I_{\mathrm{1}}$ and $I_{\mathrm{2}}$ in Figure 4, may become the induced rebroadcast nodes of node S. The worst case occurs when the coverage degree threshold and energy threshold are set to zero. Under the worst conditions, each neighbor located in the two limited regions will rebroadcast the packet. $C_{\mathrm{3}}$ is the limited region of node U in which node S is located. The regions where $nb(S)$ will do the rebroadcast under worst conditions can be given as $C_{\mathrm{1}}\cup C_{\mathrm{2}}\cup C_{\mathrm{3}}$ .

Figure 4

Limited shaded regions in which $nb(S)$ are permitted to do rebroadcast.

We use $A_{\text{s}g}$ , $A_{\cup }$ , $A_{\cap }^{\mathrm{1,2}}$ , $A_{\cap }^{\mathrm{1,3}}$ , and $A_{\cap }^{\mathrm{2,3}}$ to represent the areas of $C_{\mathrm{1}}$ , $C_{\mathrm{1}}\cup C_{\mathrm{2}}\cup C_{\mathrm{3}}$ , $C_{\mathrm{1}}\cap C_{\mathrm{2}}$ , $C_{\mathrm{1}}\cap C_{\mathrm{3}}$ , and $C_{\mathrm{2}}\cap C_{\mathrm{3}}$ . With the assumption of the uniform node density in the network, the rebroadcast ratio in the worst case may be approximated as

$$\begin{array}{cc}& R_w=\frac{A_{\cup }}{\pi r^{\mathrm{2}}}.\end{array}$$

(12)

As the radius of the three limited sector regions are $l_T$ , the areas of $C_{\mathrm{2}}$ and $C_{\mathrm{3}}$ are the same as that of $C_{\mathrm{1}}$ , and $A_{\cap }^{\mathrm{2,3}}=A_{\cap }^{\mathrm{1,3}}$ . Then

$$\begin{array}{lll}{A}_{\cup }\hfill & =\hfill & 3A-A_{\cap }^{1,2}-A_{\cap }^{1,3}-A_{\cap }^{2,3}\hfill \\ \hfill & =\hfill & 3A-2A_{\cap }^{1,3}-A_{\cap }^{1,2}.\hfill \end{array}$$

(13)

The area of $C_{\mathrm{1}}$ can be formulated as

$$\begin{array}{lll}{A}_{sg}\hfill & =\hfill & 2{\int }_0^{l_T}x{cos}^{-1}\left(\frac{x}{2r}\right)dx\hfill \\ \hfill & =\hfill & {2\left(\frac{x}{2}-\frac{{(2r)}^2}{4}\right){cos}^{-1}\left(\frac{x}{2r}\right)-\frac{x}{4}\sqrt{{(2r)}^2-x^2}|}_0^{l_T},\hfill \end{array}$$

(14)

that is,

$$\begin{array}{lll}{A}_{sg}\hfill & =\hfill & \left(l_T^2-2r^2\right){cos}^{-1}\left(\frac{l_T}{2r}\right)\hfill \\ \hfill & \hfill & -\frac{l_T}{2}\sqrt{4r^2-l_T^2}+\pi r^2.\hfill \end{array}$$

(15)

The area of $C_{\mathrm{1}}\cap C_{\mathrm{2}}$ and $C_{\mathrm{1}}\cap C_{\mathrm{3}}$ are dependent on $l_T$ which is the radius of the limited sector region. They can be formulated as follows:

$$\begin{array}{l}{A}_{\cap }^{1,2}\hfill \\ =\{\begin{array}{ll}0,\hfill & \left(0\le l_T\le \frac{\sqrt{3}r}{2}\right),\hfill \\ 2\left[l_T^2{cos}^{-1}\left(\frac{\sqrt{3}r}{2l_T}\right)-\frac{\sqrt{3}r}{2}\sqrt{l_T^2-\frac{3r^2}{4}}\right],\hfill & \left(\frac{\sqrt{3}r}{2}<l_T\le r\right),\hfill \end{array}\hfill \end{array}$$

(16)

for $\mathrm{0}\le l_T\le (\sqrt{\mathrm{3}}-\mathrm{1})r$ ,

$$\begin{array}{cc}& A_{\cap }^{\mathrm{1,3}}=\mathrm{0}\end{array}$$

(17)

and for $(\sqrt{\mathrm{3}}-\mathrm{1})r<l_T\le r$ ,

$$\begin{array}{lll}{A}_{\cap }^{1,3}\hfill & =\hfill & 2{\int }_{rcos\phi }^r\sqrt{r^2-x^2}dx\hfill \\ \hfill & \hfill & +2{\int }_{l_{t}cos\theta }^{l_T}\sqrt{l_T^2-x^{2}dx},\hfill \end{array}$$

(18)

where

$$\begin{array}{lll}cos\phi \hfill & =\hfill & \frac{4r^2-l_T^2}{2\sqrt{3}{r}^2},\hfill \\ cos\theta \hfill & =\hfill & \frac{2r^2+l_T^2}{2\sqrt{3}r\cdot l_T}.\hfill \end{array}$$

(19)

Based on the above six formulas, the rebroadcast ratio in the worst case can be formulated as

$$\begin{array}{cc}& R_w=\{\begin{array}{cc}\frac{\mathrm{3}{A}_{sg}}{\pi r^{\mathrm{2}}},\hfill & \left(\mathrm{0}\le l_T<\left(\sqrt{\mathrm{3}}-\mathrm{1}\right)r\right)\hfill \\ \frac{\mathrm{3}{A}_{sg}-\mathrm{2}{A}_{\cap }^{\mathrm{1,3}}}{\pi r^{\mathrm{2}}},\hfill & \left(\left(\sqrt{\mathrm{3}}-\mathrm{1}\right)r\le l_T\le \frac{\sqrt{\mathrm{3}}r}{\mathrm{2}}\right)\hfill \\ \frac{\mathrm{3}{A}_{sg}-\mathrm{2}{A}_{\cap }^{\mathrm{1,3}}-A_{\cap }^{\mathrm{1,2}}}{\pi r^{\mathrm{2}}}\hspace{0.17em}\hspace{0.17em}\text{and}\hfill & \left(\frac{\sqrt{\mathrm{3}}r}{\mathrm{2}}<l_T\le r\right).\hfill \end{array}\end{array}$$

(20)

It can be obtained from the above formulas that $R_w$ is a function of   $l_T/r$ . $R_w$ increases as $l_T$ increases. When $l_T$ is equal to r, $R_w=1$ . Therefore, $l_T$ is usually not set as a value bigger than r.

The rebroadcast ratio of BALR in the worst case is achieved when $d_T=\mathrm{0}$ and $E_T=\mathrm{0}$ . Formula (20) shows the worst performance bound of BALR. The rebroadcast ratio is inversely proportional to the efficiency of broadcast protocols. By properly choosing values of the three thresholds $l_T$ , $d_T$ , and $E_T$ , satisfying efficiency of BALR will be achieved in the dense sensor networks.

6. Numerical Evaluation

We simulate BALR using OPNET and compare its performance with that of flooding and ML²B [19] which could reduced redundant rebroadcast efficiently. As Broadcast Protocol for Sensor networks (BPS) [27] is one of the protocols that perform well in large-scale sensor networks, we also compare BALR with it. For physical (PHY) and medium access control (MAC) layers, we use the IEEE 802.11 wireless LAN (WLAN) model. And each node has the same transmission range of 250 m. The initial power of each node is 1.0 J. For all simulation results, Poisson streams are used. Each source sends out packets with an average rate of 5 packets per second. The data packet size is 1024 bits. The maximum delay $D_m$ is set to 0.14 s. In the following simulations, the parameters are configured as $\alpha =\mathrm{0.8}$ , $\beta =\mathrm{0.2}$ , $d_T=\mathrm{0.1}{d}_m$ , and $E_T=\mathrm{0.2}$  J, and for $l_T$ formula (5) is used with $a=\mathrm{2}\sqrt{\mathrm{2}}$ . Each simulation is repeated until the 95-percent confidence intervals of all average results are within ±5 percent.

6.1. Performance Metrics

We consider four performance metrics.

• (1)

Rebroadcast ratio $(R)$ : the ratio of the number of nodes that have rebroadcasted or broadcasted the packet to the number of nodes in the entire network. Therefore, R of flooding is 1 under all scenarios.

(2)

Reachability (RE): the ratio of the number of nodes that have received broadcasted packet to the number of all nodes in the simulated connected network. So RE also is known as the coverage rate.

(3)

Maximum end-to-end delay (MED): the interval from the time the broadcasted message is transmitted by the broadcast originator to the time the last node in the network receiving the message.

(4)

Lifetime (LT): the interval from the time the network is initiated to the time at which the first node dies in the network. We break the whole simulation time into many small time steps which are also called as rounds. The broadcast originator broadcasts each packet to all other nodes in the network in each round. To describe the network lifetime exactly, we use rounds to measure the network lifetime. LT is the round at which the first node dies in WSN.

6.2. Performance Comparisons

6.2.1. Performance Dependence on Network Scale

As wireless sensor networks consist of a large number of nodes, the broadcast protocol designed for WSN should adapt well to the large-scale network scenario. To study the influence of network scale on BALR, we simulate wireless sensor networks constituted by a different number of nodes. And nodes are randomly placed in the networks. As illustrated in Figures 5 and 6, compared with BPS, ML²B, and flooding, BALR has the smallest rebroadcast ratio R without sacrificing the RE and MED for varying network sizes. When simulating flooding, we use a random delay for each node in the network before their rebroadcast to alleviate collisions, which enhance the performance of flooding. As shown in Figure 6, BALR has a smaller maximum end-to-end delay than BPS, and flooding has the smallest MED under most conditions. It is clear that the rebroadcast ratio of flooding is 1 under all conditions. Therefore, we do not show it in Figures 5 and 7.

Figure 5

RE and R dependence on network scale.

Figure 6

MED dependence on network scale.

Figure 7

RE and R dependence on node density.

6.2.2. Performance Dependence on Node Density

Nodes are randomly placed in the network region of $750\hspace{0.17em}\text{m}\times 750\hspace{0.17em}\text{m}$ , with density varying from 5 nodes to 80 nodes per $r\times r$ region. As shown in Figure 7, BALR completes the broadcast with a satisfying coverage ratio using the least number of rebroadcasts among three protocols. In Figure 8, the maximum end-to-end delay of BALR is smaller than that of BPS. Figure 7 shows that the rebroadcast ratio R of BALR falls with the increase of node density, which guarantees the stability of BALR in high-density sensor networks.

Figure 8

MED dependence on node density.

Figure 9 shows a comparison of the rebroadcast ratio between simulation values of BALR and theoretical values in the ideal case and worst case. The rebroadcast ratio in the ideal case and worst case is computed based on formula (11) and formula (20). The influences of node density on the rebroadcast ratio of BALR under these three conditions are similar. As the rebroadcast ratio in the worst case is obtained under conditions of $d_T=\mathrm{0}$ and $E_T=\mathrm{0}$ , its values are much larger than the simulation values and ideal case values. As shown in Figure 9, simulation results of the rebroadcast ratio in BALR are close to the ideal values, which prove that BALR is an efficient broadcast algorithm for wireless sensor networks.

Figure 9

Simulation results versus analytical results.

6.2.3. Lifetime Evaluation

Each node's initial energy is 1.0 J. And the residual energy of each node decreases when it receives or transmits packets in the network. A node dies when its residual energy decreases to 0 J. As defined in Section 6.1, lifetime (LT) is the interval from the time the network is initiated to the time at which the first node dies in the network. Figure 10 shows the network lifetime of BALR, ML²B, BPS, and flooding by rounds. As shown by Figure 10, due to the super redundant rebroadcast, flooding shortens network lifetime significantly. Though BPS could reduce the rebroadcast redundancy greatly by maximizing each hop length, the adopted adaptive-geometric mechanism causes that network lifetime to be independent of node density. For ML²B, due to the lack of consideration of optimal induced forwarder selection, the number of nodes doing rebroadcast in the network increases when node density increases, which also can be calculated from Figure 8. Thus, when ML²B is used in broadcasting, network lifetime falls slowly with node density's increase as shown by Figure 10. Because of its least rebroadcast redundancy and energy balance consideration, BALR obtains longer network lifetime than ML²B, BPS, and flooding. It prolongs the network lifetime of wireless sensor networks.

Figure 10

Lifetime of networks with different node densities.

7. Conclusion

To broadcast packets efficiently and maximize the network lifetime in large-scale wireless sensor networks with densely deployed nodes, we propose a broadcast protocol BALR. It uses the coverage degree which is the number of neighbors that have not yet received the broadcasted packet of a node to measure its rebroadcast efficiency. It utilizes the geographical relationship between a rebroadcast node and its neighbors to choose as fewer new rebroadcast nodes as possible. Theoretical analysis and simulation results show that the rebroadcast ratio of BALR decreases with the increase of node density. BALR reduces the rebroadcast redundancy and prolongs the network lifetime effectively for wireless sensor networks, especially in large-scale networks with high node density. Simulation results show that the BALR strategy outperforms flooding, ML²B, and BPS strategies.