PAMPA in the wild: a real-life evaluation of a lightweight ad-hoc broadcasting family

Abstract

Broadcast is one of the core building blocks of many services deployed on ad-hoc wireless networks, such as Mobile Ad-Hoc Networks (MANETs) or Wireless Sensor Networks (WSNs). Most broadcast protocols are however only ever evaluated using simulations, which have repeatedly been shown to be unreliable, and potentially misleading. In this paper, we seek to go beyond simulations, and consider the particular case of PAMPA, a promising family of wireless broadcast algorithms for ad-hoc and wireless networks. We report on our efforts to further our experimental understanding of PAMPA, and present the first ever characterisation of the PAMPA family on a real deployment. Here it has to deal with real network problems such as node, message and sending failure. Our experiments show that the standard PAMPA algorithm out-performs all other protocols in the family, with a delivery ratio consistently around 75%, and a retransmission ratio as low as 44%, for a failure-free run. We use this opportunity to reflect on our findings and lessons learnt when moving from simulations to actual experiments^ab.

1 Introduction

Ad-Hoc wireless networks, such as MANETs (Mobile Ad Hoc Networks) and many WSNs (Wireless Sensor Networks), are self-configuring networks of embedded or mobile devices connected by wireless link. They typically rely heavily on a best-effort message dissemination service, or broadcast, as a fundamental building block to implement higher-level services, including routing and service discovery.

The simplest form of ad-hoc broadcast uses flooding, in which every node retransmits the messages it receives. Flooding is simple and generally robust, but wasteful. A number of algorithms have therefore been proposed to improve on flooding, by limiting retransmissions (communication cost) while still trying to reach as many nodes as possible (delivery). These algorithms differ in the policy they use to select retransmitting nodes, but they have in common that most of them avoid explicit control messages, and rely instead on the limited amount of information present on each node to drive retransmissions. They also often use some form of randomisation (in timeouts, or in decisions) to overcome the network’s unpredictability. While this approach works, randomisation may unfortunately cause sub-optimal behaviours, such as nodes retransmitting when they should not, or not retransmitting when they should, leading to nodes being missed out, or unnecessary transmissions being triggered.

PAMPA [1] is a lightweight broadcast algorithm that purposely avoids randomisation by combining two known strategies to the problem of ad-hoc broadcast: counting messages, and measuring received signal strength. More specifically, PAMPA first uses the received signal strength of a message as an estimation of the distance to the message’s source. PAMPA then uses the estimated distance to order retransmissions, starting at the node that is most distant to the source. Superfluous retransmissions are avoided because nodes closer to the source refrain from retransmitting. PAMPA is a minimalist protocol that does not use control messages; excludes warm-up or calibration phases; and does not assume any particular capabilities on nodes such as location-awareness or directional antennas [2, 3]. Overall, PAMPA achieves a per-broadcast delivery rate throughout the network which is close to that of flooding while using far less messages.

Building on PAMPA’s insight, a number of variants have been proposed [4] that seek to harden the protocol further. Some of these variants have been shown in simulations to provide delivery rates that are even closer to that of simple flooding while still using far less messages. PAMPA and its variants, however, have so far only been tested in simulations, a common approach in wireless protocol research. Although useful to rapidly assess a protocol’s behaviour, simulations have frequently been shown to be unreliable in assessing a protocol’s real performance [5–7]. The inaccuracy of simulations is further compounded by the fact that most simulation scenarios do not consider node failures. Node failures are however common in real deployments, where wireless sensors or mobile devices may go offline because of a variety of reasons such as mobility, depleted batteries, environmental hazards, hardware faults, and software bugs [8]. This is particular true of wireless systems deployed in aggressive environments such as industrial plants [9], search and rescue operations, or field experiments [10].

In this article, we propose to go beyond simulations for the PAMPA family of protocols, and present an evaluation of a family of algorithms inspired by PAMPA based on a real deployment. Our goal is both to assess PAMPA’s actual performance on real scenarios, and to report on our experience in moving from simulated to real experiments. More precisely, our evaluation exercises three aspects of PAMPA in three sets of experiments over real networks containing 7 and 26 nodes: In a first set of experiments we evaluated the effect of different variants proposed to reinforce PAMPA’s robustness in sparse topologies. In a second set of experiments, we carried a sensitivity analysis on the position of the broadcasting nodes on a protocol’s performance using a simple flooding algorithm as a comparison point. Finally, because node failures are common in wireless sensor networks, we assessed the algorithm’s survivability in a last set of experiments in which nodes progressively disappear following an exponential fault model. In such drastic circumstances, PAMPA must adapt to node failures properly, making sure that a broadcasted message gets to its destination even when its choice of propagation paths is limited.

All our experiments show that the PAMPA algorithm used out-performs all other evaluated protocols, with a delivery ratio constantly around 75%, and a retransmission ratio as low as 44% for failure-free runs. Similarly, our experiments with failed nodes show it maintaining a delivery ratio of 70%, even when over one third of the original nodes have failed, well above the delivery ratio of a flooding approach (60%) under the same conditions.

The rest of the article is organised as follows: We first present the challenges involved in implementing a broadcast service for wireless ad-hoc networks, and existing works in this area (Sec. 2). We then introduce PAMPA and its variants (Sec. 3), before moving on to our experimental setup (Sec. 4). Section 5 presents our experimental results, and the lessons we learnt, and Section 6 concludes.

2 Background and related work

Wireless ad-hoc networks are often used in long-term deployments (as in WSNs) where nodes have limited energy resources. The use of naive flooding to disseminate information in such networks is especially costly and can significantly reduce a network’s lifetime. More precisely, flooding involves each node re-broadcasting every new packet it receives after a random delay. Although this achieves a good coverage of nodes, its simplistic design consumes non-negligible power, engenders network contention/interferences, and is prone to packet collisions that cannot be detected by the sender [11]. Most broadcast protocols for MANETs/WSNs therefore seek to reduce message retransmissions whilst maintaining a coverage comparable to classic flooding. In doing so, they reduce contention and the chance of collisions, lowering broadcast latencies and saving energy as a result. To optimise on classic flooding, they typically make use of contextual information such as node location or neighbourhood, or rely only on observations of ongoing packet exchanges. Their behaviour is typically localised in that each node only uses its local knowledge to decide whether the cost of retransmitting a packet is outweighed by the benefit of reaching new nodes. In the following we review the most common strategies proposed to implement wireless ad-hoc broadcast protocols. We conclude this review with a few comments on the problem of node failures, and on the use of simulations to evaluate wireless protocols.

Location-based protocols use geometric modelling [2, 11] to determine the expected additional coverage that is gained by a node by virtue of its position and only allow the node with the maximum expected additional coverage to retransmit. For example, the Six-shot broadcast algorithm [2] relies on geographical coordinates provided by positioning devices on each node, such as GPS.

Alternatively, efficient flooding approaches [12–15] restrict message rebroadcast duties to core nodes and achieve the same message delivery ratio at a much lower volume of rebroadcasts. This is typically achieved through the computation of a dominating set of nodes [13] which act as a multicast tree for the wireless ad hoc network. In the dominating set, every node not in the set is adjacent to at least one other node in the set. The main advantage of connected-dominating-set-based broadcast protocols is that it simplifies the rebroadcasting process to the smaller subnetwork generated from the connected dominating set and thus reduces the total overhead of the protocol. For example, in cluster-based routing [16], clusterheads and gateway nodes form a connected dominating set for routing messages from nodes in their respective clusters. The efficiency of this approach depends largely on the process of finding a connected dominating set and the size of the corresponding subnetwork. Das et al. proposed a number of routing schemes that use the Guha and Khuller’s approximation algorithm [17] to calculate a minimum connected dominating set. In [15], Wu et al. suggest an alternative method for minimum connected dominating sets that generates smaller sets within less time. The computation of dominating sets requires neighbouring nodes to exchange their knowledge of local topology. This, of course, necessitates the periodic exchange of explicit control messages for neighbour discovery in a warm-up phase prior to node-set reduction.

The construction of the multicast-tree can also occur at run-time (self-pruning). In these Neighbour Elimination schemes, each node removes itself from the multicast tree by not retransmitting if all its neighbours are already covered by the retransmission of one of its neighbours. The rebroadcast list at each node is pruned based on its neighbours that were covered by previous transmissions. For example, the Scalable Broadcasting Algorithm (SBA) [12] performs self-pruning at each node receiving a new broadcast message by comparing the sender’s neighbours with those of the receiver. Two-hop neighbourhood discovery is periodically undertaken by the exchange of two-hop Hello messages between all peer nodes. Using SBA, a node’s retransmission is cancelled if a neighbour’s retransmission achieves the same node coverage. This scheme is further improved by the RNG Relay Subset (RRS) protocol [18] which reduces the set of monitored neighbours and thus the quantity of redundant transmissions.

Whilst dominating-set-based and neighbour elimination approaches aim at reducing the number of transmissions to achieve total coverage of the network, another category of broadcasting solutions considers the adjustment of transmission radius and thus, topology control, to obtain a compromise in energy savings and reduction in retransmisions. In Topological Control broadcast schemes, node locations (for example, GPS) included in periodically-exchanged HELLO messages, are used to determine the minimum additional transmission power at each node to cover an intended sub-graph of neighbour nodes. A slight increase in transmission power at a node to cover a neighbour node is deemed preferable to having another (closer) node retransmit. The Broadcast Incremental Power (BIP) protocol, proposed by Wieselthier, Nguyen and Ephremides [19] uses a topology control algorithm in which a node’s relay node (the node covering it) is selected from a set of neighbours such that the additional transmission power required at the chosen relay node is smallest. Topological control algorithms require knowledge of each node’s neighbourhood for adjusting its transmission power. A deeper knowledge of nodes’ neighbourhood (n-hops) may lead to a more optimal power adjustment in the tree-building process; but the need for additional HELLO message exchanges inevitably degrades overall performance. Ingelrest and Simplot-Ryl proposed a localized broadcast incremental power protocol [20] where this overhead is limited by having each node applying the BIP algorithm in its k-hop neighbourhood, for moderate values of k (for example, k = 2).

Contextual information, as used by Location-, ConnectedDominating-Set-based and Topological-Control protocols, is not however always available (or its use desirable). GPS for example, used as a basis for geometric modelling, may be too expensive a requirement for low-cost devices and does not work indoors. Likewise neighbour discovery via Hello messages can be a source of significant overhead, additional contention and collisions. To address these limitations, a range of broadcast protocols have been proposed that do not require any contextual information but instead rely on simple heuristics that have been shown to work well.

For instance, epidemic protocols such as GOSSIP1(p)[21] use a form of probabilistic flooding in which nodes retransmit a message with some fixed probability p (p < 1). To prevent retransmissions from dying out (p is too low), GOSSIP3(p,k,m)[21] extends this technique by forcing retransmissions in two cases: i) if the message has been travelling for less than k hops, and ii) if the number of retransmissions listened by any node after a short delay is lower than a threshold m. Unfortunately static gossip probabilities may render these protocols inefficient in heterogeneous network topologies. A low gossip probability is suitable for a dense network but cause the broadcast to die out in sparser regions. Conversely, a higher probability improves reachability in the sparser regions but is wasteful for denser topologies. The problem is further compounded by the fact that network densities are not usually known a priori. To address this issue, adaptive epidemic protocols such as RAPID [22] and Smart Gossip [3] adapt their retransmission probability to the perceived network density. They assign different gossip probabilities to nodes based on their topological importance; critical nodes broadcast with higher probability. Node densities are evaluated during a warm-up phase through the periodic exchange of messages and neighbour retransmissions count.

Warm-up phases and periodic neighbour discovery can be costly and in the case of volatile networks present the broadcast protocol with outdated neighbour information. Further, as found in [11], if several neighbours around a node were to retransmit the same flooding message, the expected additional coverage, EAC(k), after a host hears the same message k times dramatically decreases. Counter-based broadcast protocols therefore restrict the retransmissions in a node’s neighbourhood to a predefined threshold. They wait for a random but bounded delay and count the number of duplicate messages received at a node during that time. They then only allow retransmission if the counter does not reach a pre-determined threshold. Counting duplicate messages improves efficiency and is therefore a trait found in many WSN broadcast protocols including PAMPA. On its own, however, counting, like the use of static probability, does not ensure an optimal use of retransmissions. In particular, the problem of selecting suitable thresholds for uneven distributions in network topology remains.

Like counter-based protocols, distance-based broadcast protocols[11] use the notion of expected additional coverage to determine the value of a node’s retransmission. Instead of counting neighbour retransmissions, they look at the signal strength of these retransmissions to estimate additional coverage. They assume that signal strength (captured from the Received Signal Strength Indicator - RSSI) is an indication of a transmitter’s distance to the receiving node. The greater the distance (i.e. the lower the first message’s RSSI), the more additional nodes the receiving node can cover with its retransmission. To exploit this notion, distance-based protocols wait for a random but bounded time after the first message reception listening to further retransmissions. If the maximum signal strength of all received retransmissions falls below a certain threshold, the node is allowed to retransmit. Both counter-based and distance-based broadcast protocols use random listening periods which can be counter-productive: nodes of higher topological importance may be preempted from retransmitting if the listening timer of less ‘important’ nodes in their vicinity expires first.

The most recent research into probabilistic protocols has been looking into coping with node failures. Sensor networks succumb to node failure as nodes often have low power supplies and are prone to errors. In striving to take further account of the underlying network, protocols such as RAPID [22] have been proposed to cope with node failures and varying network densities. RAPID uses corrective deterministic measures to ensure a constant delivery of messages, regardless of the underlying topology. Nodes that miss messages can request them from their neighbours, thus keeping the delivery ratio high. However this can have an adverse effect on the overall efficiency of the protocol. For a node to find out which messages their neighbours have seen, determine which messages they have missed and obtain them from the neighbour, it adds considerable overhead to the protocol’s performance.

Although extremely useful to rapidly assess a protocol’s behaviour, simulations have repeatedly been shown to be inaccurate in assessing a protocol’s real performance [5, 6, 23, 24]. This is because simulations often used simplified models of complex physical phenomena. For instance, the unity disk model—in which nodes have a fix constant transmission range that is free of any interference—has long prevailed in simulations, but is highly unrealistic. In real ad hoc wireless settings, network links are connected intermittently and have dynamic qualities that depend on topographical factors such as building structures and other time-varying factors such as weather and temperature [9]. Radio communication is also affected by fast-time varying interference such as hidden terminals, multi-path effects and gray zones [25]. This time varying environment is not completely controllable and provides a source of non-determinism in the evaluation of broadcast and ad hoc routing protocols. To overcome this inaccuracy, most simulators offer full-fledged propagation models that seek to replicate the imperfections of real radio deployments: imperfect ranges, erroneous links and interferences. These full-fledged models tend unfortunately to be very costly to compute, limiting their use [6]. Current simulators therefore often propose intermediate strategies that seek to balance accuracy against simulation complexity. These strategies however differ from simulator to simulator, making cross-simulator comparisons difficult [24], and any extrapolation of simulation results to real deployments subject to caution, at best [23].

3 PAMPA and its variants

PAMPA [1], which provides the basis for our work, reduces the use for randomisation in wireless ad hoc broadcast protocols by combining both the counting and distance-based strategies. PAMPA has since then been expanded to include hardening mechanisms, in particular in heterogeneous topologies [4], with promising results obtained in simulations.

3.1 Vanilla PAMPA

The basic PAMPA algorithm is shown in Algorithm 1. PAMPA is at its core a counter-based broadcast algorithm, which uses distance (as derived from a transmission’s Received Signal Strength Indicator, or RSSI) to calibrate how long a node waits while counting. More precisely, when a node receives a message for the first time, PAMPA apportions a “waiting time” for that node. The waiting time depends on the signal strength at which the message was received (line 8) such that higher RSSI values (i.e. smaller distances) tend to be associated with longer waiting times. During this waiting time a node counts how many retransmissions it receives of that same message. At the end of this waiting time the node makes a decision for that message: if the node heard less than a given number n of retransmissions (line 14), the node chooses to retransmit the message itself (line 15), otherwise it does not.

PAMPA intentionally privileges retransmissions performed by the nodes more distant to the source of the previous retransmission as these are the ones expected to provide bigger gains in coverage. The particular value for n is fixed prior to deployment and is chosen based on the desired trade-off between delivery coverage and redundant message overhead (such that lower values of n mean less redundant messaging but potentially lower delivery coverage). However, it should be noted that the relation between n and coverage is not linear given that as retransmissions approximate to the source, so does the probability that the area has been completely covered by one or more previous retransmissions.

For the purpose of counting retransmissions, a “message” is assumed to be uniquely identified in some way; in our implementation this is by way of a monotonically increasing sequence number set by the broadcast source.

3.2 Variants

Although PAMPA is thus more “informed” than other counter-based alternatives, its perception of the local node topology remains limited. In particular, PAMPA is not designed to perform well in heterogeneous topologies where some nodes may perform a key role in the propagation of messages. This is a situation likely to arise in real-world wireless networks, for example when two parts of a network on opposite sides of a river are connected by a small number of sensors deployed over a bridge. To address this problem a number of variants to PAMPA were proposed in [4]. All consist in counting only some of the retransmissions (see line 10 of Alg. 1), based on two types of information: (i) the retransmission path just followed by a retransmission (Common Parenting), and (ii) the relative position of a retransmission with respect to the original copy of a message (Dynamic Thresholding).

Common Parenting looks at the next-before-last hop of a retransmission, which we call its parent node. This relationship is illustrated in Figure 1. Common parenting records the parent node of the original message reception, and only counts those retransmissions that have a different parent than the original reception. The motivation for this mechanism is that different parent nodes will tend to denote a higher diversity of propagation paths, which is a sign that the message is propagating well and is therefore less likely to need additional retransmissions.

Figure 1

R ₁ and R ₃ are the parent nodes of r ₂ and r ₄ respectively.

Dynamic Thresholding uses the RSSI to further influence whether or not a message should be retransmitted. It uses a similar approach to distance-based protocols in that it only counts retransmissions that have an RSSI that crosses a particular threshold. However, instead of relying on a fixed threshold, which is difficult to define statically, the dynamic thresholding variant of PAMPA uses the RSSI of the original message reception to set the threshold for observing retransmissions of that message.

Dynamic Thresholding comes in two sub-variants, depending whether only retransmissions with a lower (Thresholding) or higher (Antithresholding) RSSI than the original one are counted. Both Thresholding and Antithresholding have a geometric interpretation: Thresholding, in which we count retransmissions with a lower RSSI and therefore estimated greater distance than the original sender, will cause a node C to only count retransmissions from a doughnut area we have termed its outer-ring (see Figure 2). By contrast, Antithresholding, in which we count retransmissions with a higher RSSI and therefore estimated shorted distance than the original sender, will primarily count retransmissions from a node’s inner-strip and forward bubble on the same figure. In this latter case, note that nodes located between C and R will have a longer delay than C due to the generally higher RSSI that they will observe on the message originally received from R; these nodes are therefore unlikely to retransmit before C.

Figure 2

Dynamic Thresholding: The right-hand node will only accept messages from nodes situated in the shaded area.

3.3 A family of protocol variants

The criteria used by Common Parenting and Dynamic Thresholding to filter retransmissions are orthogonal, and can thus be combined to create further variants. This is shown in Figure 3, where the types of retransmissions counted by variants are shown in a 2 × 2 matrix. PAMPA counts all retransmissions, while Common Parenting (CP), Thresholding (TH) and Antithresholding (ATH) only count retransmissions meeting a single criterion (shown as 1’s in the figure).

Figure 3

Family of protocols: 1 s indicate which retransmissions are counted.

By combining the CP criteria with TH and ATH, one obtains two more protocols, PAMPA-TH/CP and PAMPA-ATH/CP. These are more selective than PAMPA in their counting but less than the original three variants. Another protocol, hereafter named Delayed Flooding (D-Flooding) can be captured in this scheme by simply not counting any retransmission, and retransmitting all messages. D-Flooding differentiates from flooding by replacing the random jitter mechanism used in the latter to reduce collisions by a distance-based delay similar to the one used by PAMPA.

This distance-based delay is expected to improve flooding delivery ratio given that nodes providing a bigger additional coverage will retransmit before the remaining.

4 Experimental setup

Most existing studies of the performance of broadcast protocols use simulations (see, for example [4]). However, even the most detailed simulation models may not capture the particular characteristics of real ad-hoc wireless environments. They may not, for example, include limitations of the radio interface hardware such as limited buffer space, limitations due to the protocol stack implementations, or various random sources of errors in the wireless physical layer such as multipath propagation, radio noise, asymmetric radio links, and so on. For our real-life evaluation of PAMPA and its variants, we implemented and deployed the algorithms in a live testbed (a WISEBED instance [26]) of sensor mote devices. In particular, we built the algorithms using the component libraries and toolchain of the Lorien OS [27] deployed and executed on TelosB motes. TelosB motes (depicted in Figure 4) are low-power wireless sensor devices, each equipped with a 802.15.4 radio module achieving data rates of up to 250 kbps and an indoor transmission range between 20 m to 30 m.

Figure 4

An example TelosB mote.

4.1 Experimental configurations

Our evaluation uses three experimental configurations to examine different aspects of the PAMPA family of protocols in real networks. The first configuration (C1) compares all PAMPA variants head to head against Delayed Flooding. It uses a small wireless network of seven nodes, in which a single source repeatedly broadcast messages. The second configuration (C2) focusses more specifically on PAMPA with no enhancements, and analyses in detail its behaviour over that of Delayed Flooding in a larger network when the source of broadcast rotates among nodes (what we term node-switching in the following). Finally, the third configuration (C3) investigates how well PAMPA (with no enhancements) copes with ongoing node failures when compared with the baseline of delayed flooding, in the same network of Configuration C2.

In the version of PAMPA deployed in the testbeds the RSSI is mapped onto waiting time (‘msg.delay’ in Algorithm 1) by picking a random number between zero and the message’s signal strength. This choice was made to account for the coarse nature of RSSI values in current radio hardware (comprised in 0 and 256, with most values falling in the higher end of this range in our experiments), and minimise the risk for collisions even when most measured RSSI values fall in a small range. For clarity, the reminder of the paper refers to the deployed version of the algorithm as “PAMPA” and uses the term “Vanilla PAMPA” to refer to the baseline version of the algorithm that was experimented in simulations. In all three configurations, the counting threshold for the number of heard retransmissions is kept fixed and low, at n = 2, to keep the messaging overhead low while still providing sufficient redundancy for delivery coverage.

4.2 Selected network topologies

For the C1 experiment, we used a small-scale WSN testbed at Lancaster University containing seven TelosB motes, all running the same variant of the PAMPA algorithm. The TelosB motes belong to an indoor live WSN testbed (part of the WISEBED experimentation facility) and are selected to realise a topology where the notion of ‘keyness’ of certain nodes is exercised. The layout of the nodes can be seen in Figure 5. Although the ‘bridge’ topologies tested in simulations [4] are hard to reproduce on the testbed due to the fixed position of nodes, the selection of key nodes (such as Node 3 in Figure 5) allows similar protocol behaviour (for example, overcancellation [4]) to be reproduced. On this topology, Node 1 is unable to communicate with Node 5 due to environment constraints. This makes Node 3 important to the delivery of messages to Node 5 and Node 7.

Figure 5

Node layout in the office environment at Lancaster University. Red lines indicate a link between the two nodes with the average RSSI of the link.

For the node switching and node failure experiments (respectively C2 and C3) a larger network testbed was needed. For this another WISEBED network was used in an office environment at the University of Bern. The Bern testbed has 21 nodes placed randomly in different rooms across three different floors (see Figure 6 for a layout of the topology).

Figure 6

Node layout in the office environment at the University of BERN.

Both testbeds are deployed in an ‘office’ environment, which includes a mixture of brick support, plasterboard separations and glass walls that radio signals must overcome, as well as thick wooden fire doors. The room height is around 2.7m. Most experiments are performed at night to avoid the added interference of office workers. This set-up allows us to evaluate all protocols under comparable conditions.

4.3 Experimental protocol

The three experiment configurations summarised above are now described in detail to aid in reproducibility. Each configuration is based on the same basic principles with particular alterations according to the characteristics being investigated.

4.3.1 PAMPA variant comparison (C1)

In configuration C1 a particular node (Node 1, Figure 5) in the WSN is selected as the broadcast-originator whose sole responsibility is to broadcast a message every 10 seconds. This node does not attempt to receive or retransmit any messages. The periodic interval of 10 seconds ensures that broadcasts between different experiment runs do not overlap and interfere with each other. Each broadcast message contains a unique identifier (uid) in its header that is used by a receiving node to differentiate between multiple messages. This identifier is part of the soft state saved in each node’s message log to detect duplicate messages (line 5 of Algorithm 1). Also included in the message log is the RSSI of each message, obtained through a query to the radio module of the TelosB motes for the received message’s network parameters. Only the RSSI value of the first arriving message is recorded and used as a threshold for the retransmission-based protocols.

4.3.2 Broadcast node switching (C2)

In C2 the broadcast source node is changed after each experiment run. This allows us to analyse how the location of the broadcast node affects the propagation of message and how obstructions in the network’s environment affect the performance of each protocol. Broadcast nodes are chosen that would be considered to be clustered in the middle of the network (node ids: 1, 2, 3 and 14 Figure 6) and outliers on the network (node ids: 18, 20 and 21 Figure 6). These nodes are chosen to be broadcast nodes as they give a good indication of whether a broadcasting nodes’ position within a network affects the performance of the protocol that is operating within it.

Each combination of a protocol and a source node is evaluated in C2 using 20 experimental runs, with each run comprising 60 individual broadcasts from the same source node. More precisely, each run, which lasts for about 18 minutes, is organised in three phases:

● In the first phase (7–9 minutes), nodes are initialised.

● In the second phase (6–8 minutes), 60 messages are broadcast from the source node and propagated through the network. During this phase, messages are broadcast every 10 seconds from the broadcast source node. This gives each message enough time to disseminate through the network before the next message is broadcast.

● In the third phase (1–5 minutes), the network is finally allowed to cool off to make sure that there are no excess messages on the network when the next run starts.

4.3.3 Node failure (C3)

For C3, the node failure configuration, three sets of experiments are conducted for both PAMPA and Delayed Flooding, which is again used as baseline. Three random nodes (Nodes 4, 10, and 15 in Figure 6) are used as broadcasting nodes. These nodes are spaced evenly around the network on different floors, providing a fair average of how each protocol copes with node failure and not how they are responding to a particular broadcast node. Each set then consists of 20 runs using the same failure model for each, in which nodes are dropped from the network using an exponential decay model. In this failure model, each node has a constant chance of failing per time unit. This corresponds to an adverse network environment, where all nodes are at risk of dying in parallel.

More specifically, we employ the following formula:

The number of surviving nodes at time t is computed to be:

$$N\left(t\right)=N\left(0\right)\times e^{-\mathrm{\lambda t}}$$

where λ is the ‘decay constant’, and corresponds to the probability for each node to fail per time unit. If the time of failure is larger than the duration of the experiment, the node will not fail during the experiment.

Each experiment has the same node failure model so it shows how well the protocol copes with node failure and not how badly the nodes failed on each particular experiment. The times each node fails was calculated before the experiments took place and the same nodes failed for each run. The failure times were calculated using the algorithm above and are shown in Table 1. The broadcast node never fails as this would completely cease any message propagation on the network (note that on a real deployment of the network the broadcasting node would be changing constantly and so would not be a single point of failure).

Table 1 Node failure times

4.4 Computed metrics

In each experiment a number of variables are measured to determine the performance of each protocol on the network. These variables are used to calculate two metrics: the Retransmission Ratio and the Delivery Ratio.

Retransmission Ratio is a key metric for broadcast protocols in WSNs and represents the communication cost paid for each successful delivery of a broadcast. The highest possible retransmission ratio is 1, corresponding to a run where all nodes that receive the message retransmit it. More efficient protocols will have lower retransmission ratios. The retransmission ratio of a run is defined as the average ratio between broadcast deliveries and broadcast retransmissions:

$$\text{The Retransmission Ratio}=\frac{1}{n_{\text{bcasts}}}\sum _{b=1}^{n_{\text{bcasts}}}\frac{{\text{\#retransmission}}_b}{{\text{\#delivery}}_b}$$

where n_bcasts is the number of broadcasts (in our experiments, 50), and $\frac{{\text{\#retransmission}}_b}{{\text{\#delivery}}_b}$ is the retransmission ratio of broadcast b, i.e. the proportion of nodes that, having received b, retransmit it.

Delivery Ratio is the average proportion of nodes reached by a broadcast on the network. The higher the delivery ratio, the more effective the protocol and the larger the coverage of each broadcast. A delivery ratio of 1 means that every message broadcast across the network was received by every node. More precisely, the delivery ratio is obtained with the following formula:

$$\text{The Delivery Ratio}=\frac{1}{n_{\text{bcasts}}}\sum _{b=1}^{n_{\text{bcasts}}}\frac{{\text{\#delivery}}_b}{n_{\text{nodes}}-1}$$

where n_bcasts is the number of broadcasts (in our experiments, 50), and $\frac{{\text{\#delivery}}_b}{n_{\text{nodes}}-1}$ is the delivery ratio of broadcast b, i.e. the proportion of nodes that receive b. Although a high delivery ratio indicates a high degree of coverage of the network nodes by a broadcast protocol, its overall performance can only be determined in combination with the protocol’s retransmission ratio.

5 Evaluation results

This section presents the results of our evaluation of the PAMPA suite of protocols based on a real deployment. In doing so, it enables the identification of the most suitable PAMPA variant for a particular deployment scenario.

We also compare our findings with the simulation-based evaluation of vanilla PAMPA and its variants presented in [4]. We have also evaluated the effect of switching the broadcasting node in a network. This observes whether the origin point of a message, or different propagation paths, affects the efficiency and success rate of PAMPA. A further experiment looks at the ability of PAMPA to cope with node failures on the network. We evaluate how it copes when nodes drop out and propagation becomes increasingly difficult. In the comparison, we also factor in the difference in network topologies, the use of a MAC protocol in the simulation-based study (which is absent in our real deployment), and the random mapping from signal strength to waiting time in our real experiments (while simulations used a deterministic mapping—see Section 4.1).

We re-iterate that maximum node coverage using few retransmissions (i.e. less energy consumption) are the defining traits of the ideal WSN broadcast protocol with the former as the overriding factor.

5.1 PAMPA variant comparison (C1)

Figure 7 and Figure 8 show the delivery ratios and retransmission ratios respectively for each PAMPA variant over 10 experiment runs in C1. In the figures, the box-and-whisker plots give the degree of confidence in and the mean (shown as a cross) of the computed metric values for each broadcast protocol variant. The best performing broadcast protocol in our experimental evaluation is PAMPA, achieving an average delivery ratio of 75% (See Figure 7) at relatively low retransmission cost (only 44%, See Figure 8). It is surprising to find PAMPA achieving an even higher average delivery ratio in this experiment series than D-Flooding (71%). We explain this by observing that, by retransmitting less, PAMPA causes less packet collisions and is therefore able to reach out to more nodes. PAMPA performs markedly better than its variants which is in stark contrast to the evaluation results from simulation where the opposite is the case (with the exception of the PAMPA-TH variant). Ellis et al. report vanilla PAMPA achieving delivery ratios higher than 90% in only 37% of ‘bridge’ topologies selected [4]. We attribute the difference in behaviour of PAMPA in simulation and real deployment to at least three conditions: 1) the sparser/smaller network topology in our real deployment, 2) the not inconsequential effects of the aforementioned real-life deployment-level limitations not captured by simulation, and 3) the changes in the mapping strategies from RSSI to waiting time brought about by practical considerations (Section 4.1).

Figure 7

Average delivery ratio, results for each algorithm variant and d-flooding with 10 experiments run for each.

Figure 8

Average retransmission ratio, results for each algorithm variant and d-flooding with 10 experiments run for each.

With regards to node coverage, PAMPA-CP and PAMPA-TH/CP are the second-best performers after PAMPA achieving a healthy average delivery ratios of 0.72 and 0.73 respectively but prove strikingly costlier, posting average retransmission ratios of 0.89 and 0.83 respectively. Clearly, common-parenting curbs overcancellation and produces more retransmissions including those at key nodes. When directional look-ahead is applied to PAMPA-CP, only the retransmissions from nodes in the outer ring (see Figure 2) and with no common parents are counted, reducing the wastefulness of common-parenting. This is translated into a reduction of the average retransmission ratio by 0.06. In simulation, by contrast, both PAMPA-CP and PAMPA-TH/CP fared better than PAMPA (the second-worse simulation performer) in terms of node coverage and posted somewhat lower retransmission ratios (0.68 and 0.58 respectively).

The worst performers in our evaluation are the PAMPA-ATH/CP, PAMPA-TH and PAMPA-ATH variants providing modest average delivery ratios (0.65, 0.65 and 0.62 respectively) whilst still incurring high average retransmission ratios (0.8, 0.78 and 0.77, respectively). Considering only the PAMPA-ATH and PAMPA-ATH/CP variants, one can find that the application of common-parenting to PAMPA-ATH curbs overcancellation leading to an improvement in average delivery ratio of 0.03 but incurring an additional retransmission overhead of the same magnitude (0.03). The simulation results for PAMPA-ATH and PAMPA-ATH/CP depict a different picture altogether; they performed consistently better than PAMPA, reducing the average delivery loss of PAMPA by 13–14% approximately.

PAMPA-TH is expected to perform less well than PAMPA in sparse networks where the presence of nodes outside the signal-strength threshold (outer ring) is more likely. As only the retransmissions for these nodes are counted in PAMPA-TH, this leads to higher message drop rates (poorer delivery ratio) in sparser topologies than for PAMPA. This is reflected in our results. In comparison with its simulation results, we find that it performs better in a real deployment than in simulation. The simulated PAMPA-TH exhibited the worst average delivery ratio (node coverage) and the second-most costly retransmission ratio.

5.2 Broadcast node switching (C2)

Table 2 and Table 3 show the delivery ratios and retransmission ratios respectively for PAMPA and delayed flooding over 20 broadcast node switching experiment runs (C2). This set of experiments showed that careful choice of a broadcasting node is important. For instance, in the runs where node 20 (Table 3) was the broadcasting node, the performance of each protocol suffers severely.

Table 2 Broadcast node switching retransmission ratios

Table 3 Broadcast node switching delivery ratios

Node 20 was an outlier to the network, it was positioned very high up in the office environment and struggled to get its initial broadcasts to the first set of nodes. It also shows how different volumes of obstructions can affect the performance of the protocol as the outliers that have to transmit their initial broadcasts through more obstructions than those clustered in a single room. It seems that all of the protocols have an implicit preference to broadcast in a cluster of nodes to obtain a higher delivery ratio, which is consistent with the expected bimodal behaviour of these algorithms [21]. The performance for each protocol increases when nodes are clustered together, for example node 1 and node 2 (Table 3).

D-Flooding again results in high channel contention and packet collisions. This leads to its very poor delivery ratio and shows that a smarter protocol is definitely needed on this type of ad-hoc network. It should be noted that D-Flooding is expected to improve the performance of vanilla flooding as it imposes some order in node retransmissions, in contrast with vanilla flooding where the moment selected by each node for retransmission is exclusively dictated by a random jitter. Wherever the broadcast node resides throughout the network, PAMPA is always the most efficient protocol to use as seen in Table 2. This shows that PAMPA can be applied to a variety of ad-hoc networks with very different properties and still adapt much better than a simple flooding protocol.

These results using node switching on a real network show do not fully agree with simulation-based experiments, and highlight the importance of real deployment, and the potentially large impact of small changes in a protocol’s realisation. In the simulations vanilla PAMPA presented around a 50% retransmission ratio, with the results obtained from this set of experiments showing similar results of 48%. However PAMPA’s delivery ratio in contrast delivers each message 91% of the time to each node on the network. This was a strong improvement on the simulation results which found vanilla PAMPA to have a 76% delivery ratio. Beyond the intrinsic differences between PAMPA and vanilla PAMPA, these results are probably also linked to the poor message failure models of our simulations, which do not represent the complex failures experienced in a real network. On one hand this can probably be attributed to the excessive determinism of network simulators, that ignore the effects of walls and multipath on signal propagation. We also think it highlights the importance of node topologies on the performance of individual protocols, and hence the need for realistic topology construction in network simulators.

5.3 Node failure (C3)

Figure 9 and Figure 10 shows the average of delivery and retransmission ratios per minute over the 20 experiment runs on configuration C3. As nodes fail on the network (shown on the Figures by the vertical lines) the graphs display how each of the protocols adapts to the failure of nodes and attempts to keep propagating messages.

Figure 9

Node failure experiments average delivery ratio, results for PAMPA and d-flooding with 20 experiment runs for each. (One marker represents the average retransmission ratio from that minute in each of experiment runs).

Figure 10

Node failure experiments average retransmission ratio, results for PAMPA and d-flooding with 20 experiments run for each. (One marker represents the average delivery ratio from that minute in each of experiment runs).

PAMPA showed a clear improvement over delayed flooding in this set of experiments. PAMPA’s delivery ratio stayed higher than the delayed flooding protocols’ throughout the experiment and for all three broadcasting nodes tested. There were a few exceptions to this where the delayed flooding protocol coverage was marginally higher but after around the fifth minute, when more nodes had started to fail, it is clear that PAMPA results are far better.

The delivery ratio clearly decreases as there are less propagation paths for messages to use to reach outlying nodes. Unlike the other protocols, PAMPA shows signs of adapting to the new propagation paths in the network. In future we would like to increase the time between node dropouts to see if the protocol can fully recover and reproduce the same delivery ratio. This would have to be performed on a larger network where there are more propagation paths available.

A further sign that PAMPA adapts to new propagation paths in the network is the retransmission ratio results. It can be seen that as nodes drop out, PAMPA slightly increases its retransmission probability to try and cope with the failure and its corresponding decrease of node density. The protocol gets slightly less efficient after every node failure, however it keeps the delivery ratio much higher than the other protocols.

PAMPA has been shown to adapt very well to a dynamic network and increasingly adverse conditions. PAMPA is a lot more dynamic because of its looser structure and lower data overhead. As PAMPA relies on the current message it has received to make a decision and does not create complex data structures or hierarchies like other protocols (e.g., Multipoint Relaying [21]), it can therefore react quicker to the loss of former propagation paths.

6 Conclusions and lessons learnt

In this paper, we have evaluated the performance of the PAMPA family of broadcast protocols on a real deployment. The results have confirmed PAMPA’s strengths: The protocol was able to reach more nodes than a naive flooding strategy (75.2% vs. 71.6%), while incurring much lower retransmissions costs (44.8% vs 90.2%). These results are also in line with earlier simulation results, obtained with different node densities and topologies, in which vanilla PAMPA achieved a delivery ratio of 77% for a retransmission ratio of 51% [4]. The stateless properties of PAMPA keep it lightweight and dynamic, allowing it to adapt to new and better propagation paths within the network. This article has shown that when a protocol drops redundant messages this will increase the delivery ratio. If a protocol can keep its retransmissions low, it causes less traffic on the network.

The results of the PAMPA variants have been more chequered, however, and different from earlier simulation results in their relative performance to PAMPA. For instance, whereas PAMPA-CP performed better than PAMPA in simulations for a moderate additional cost [4], it performed worse in our real deployment, for a retransmission ratio (89.1%) close to that of flooding.

Several good reasons can explain this divergence: First, as mentioned earlier, simulations only imperfectly reflect reality [5, 6], highlighting the need for real deployments. Second, but more importantly, earlier simulation results for PAMPA were obtained on large topologies (several hundreds of nodes), which are difficult to compare against the smaller deployments used in this paper. This is particularly important for the CP mechanism, which would be expected to perform better in denser networks with longer and more diverse propagation paths, leading to less retransmissions.

In the future, we would like to better evaluate the impact of a random mapping between RSSI and waiting time. In addition, it would be interesting to look at implementing this small topology in a simulator and seeing whether similar results are achieved. Another reason for this may be the reliance on RSSI to affect the protocol variant’s decisions. RSSI is often not accurate enough to determine distances, leading to poor decisions made by the nodes when dropping packets. In further research the hardware should be tested for distance and RSSI measurements and then calibrated accordingly.

This latter point highlights the difficulty in assessing wireless broadcast protocols, and more generally any distributed wireless mechanisms: simulation campaigns tend to focus on large networks to demonstrate scalability, and to benefit from statistical effects (such as the diversity of propagation paths) which are hard to observe at smaller scales. By contrast, real testbed deployments tend to be much smaller, only involving a few tens of nodes, or less. This experimental discrepancy is probably a reason to focus more on the validity of simulations results, than on their size.

For research in the future this paper has shown that it is important to choose the position of broadcasting nodes within the network carefully. Taking care to place important nodes in clusters of other nodes will result in better coverage for each of the broadcasting nodes’ transmissions.

In this context, the fact that the versions of PAMPA obtained very close results both in large simulations and in a small real deployment is a strong indication of PAMPA’s robustness, an aspect worth researching further in the future.

In terms of methodology, our results confirm once again the importance of real deployments to evaluate protocols. This somewhat obvious point comes however with a number of caveats: Real deployments are costly, time consuming, and tedious. Although we were able to rely on the infrastructure of the WISEBED testbed [26], failures, in particular of nodes, were frequent, and considerably increased the efforts required to run experiments. The causes of failures were diverse: batteries would get depleted, passers-by would interfere with parts of the infrastructure, the memory of motes would get corrupted. Even without failures, repeating experiments (resetting, re-synchronising, and re-starting each node) made obvious the importance of a powerful management and scripting interface to conduct large numbers of tests in a batch mode, even on a modest network.

The above difficulties in running real experiments, and the importance of these experiments for evaluation, are both key arguments that support the recent efforts made to develop shared wireless testbeds [26, 28], an evolution that should provide critical feedback to researchers and practitioners working with wireless distributed networks.

Endnotes

^a A preliminary version of this paper was published in [29].

^b All code used is available by emailing the authors at c.winstanley@lancs.ac.uk.