Alexander Logan

Sensor Networks & Mobile Data Communications

Contents

Environmental factors may affect the quality of links - background noise, interference, and internal hardware noise etc.

Routing protocols require link quality estimation to overcome the problems of unreliability associated with low-power links. It is also important to help maintain a stable topology.

There are a few possible important metrics:

We usually make the simplifying assumption that transmission range is circular, though in practice this is often untrue. In practice, we can define three different types of region:

We make some important observations:

This has a big impact on the performance of higher-level protocols.

Interference

Interference can be external or internal. External interference can occur from co-located networks operating at the same frequency. Internal interference occurs from concurrent transmissions from nodes in the same WSN.

There are three types of link monitoring:

Some observations about hardware link quality estimators:

There are three classes of software link quality estimators:

The data link layer is responsible for accessing the medium - controls when a node should transmit data to another node or set of nodes.

Nodes in ad-hoc and WSNs usually transmit in half-duplex mode (only one direction at a time). However, more than one node may transmit data simultaneously.

There are several considerations to take into account at the MAC layer:

There are three main concepts for dividing access to a medium:

In Ad-Hoc networks, protocols generally fall under two categories: contention-based and reservation-based.

Contention-Based Reservation-Based
Rely on controlled contention between nodes to access the medium. Each node transmits data during a previously reserved time slot. Contention occurs only during the reservation phase.
✅ Flexible - Each node makes contention decisions independently.
❌ No QoS - Nodes are not guaranteed regular access to the channel.
❌ More collisions as node density increases.		 ✅ Collision free
✅ QoS
❌ Time Synchronisation Required - Reservations need to be consistent across all nodes.
CSMA/CA
MACAW
IEEE 802.11
DBTMA		 D-PRMA
HRMA

CSMA/CA

Carrier sense multiple access with collision avoidance. Based on carrier sense - a node listens to the medium continuously, and if it is found to be idle for a certain period of time (called an inter-frame space (IFS)), it may transmit.

If a node wanted to transmit but sensed the medium was busy, it must first wait for the medium to become free, and then wait an inter-frame space. It will then begin contention for the medium - it will generate a random backoff time and wait this long before attempting to transmit. This helps ensure nodes do not collide by all attempting to transmit at the end of the inter-frame space.

Note that this protocol alone does not solve the hidden node problem.

CSMA/CA with Signalling Packets

The protocol can be extended to support request-to-send and clear-to-send packets to reduce the problem of interference from hidden nodes.

In this algorithm, back off is exponentially increased upon collisions occurring.

MACAW

Multiple Access with Collision Avoidance for Wireless networks. This is not based on carrier sensing, and instead uses signalling packets:

The back-off using in this algorithm is multiplicative increase and linear decrease (MILD) rather than exponential. This helps reduce cases of long back-off times occurring.

IEEE 802.11

Standard for WLANs. Based on CSMA/CA with exponential back-off timer.

Also uses Network Allocation Vector (NAV) mechanisms, which specify the earliest time a node may attempt transmissions. Nodes will defer access to the medium upon hearing a RTS or CTS, as the length of time required for the transmissions is contained within these packets.

Collisions may only occur when the RTS/CTS packets are being sent. Afterwards, collisions are avoided because nodes will have set their NAVs. This RTS/CTS system is sometimes called virtual sensing of the medium.

MAC in WSNs

When considering protocols to apply in WSNs, we should take into account the expected use cases of these networks:

IEEE 802.15.4

Standard for low-rate Wireless PANs (personal area networks).

This protocol combines contention-based and reservation-based schemes.

In this protocol, devices can either be considered Full Function Devices (FFD) or Reduced Function Devices (RFD).

The coordinators have several tasks:

In non-beaconed mode, regular CSMA/CA with ACK (but no RTS/CTS) is used.

In beacon-enabled mode, super-frames are signalled with beacons and slotted CSMA/CA is used - in the first part of the super-frame, nodes contend for access to slots (the Contention Access Period (CAP)), and in the second part nodes which have been assigned guaranteed slot are able to transmit (the Guaranteed Time Slots (GTS)).

These guaranteed slots are managed as follows:

  1. Suppose a node A wishes to obtain a guaranteed slot. During the CAP, A sends a request packet to the coordinator indicating the number of slots it requires, and whether they are for transmission or receiving.
  2. Coordinator replies with an ACK - indicating it has received the request. This ACK does not guarantee the reservation has been made.
  3. The coordinator considers the resources it has available and whether it can accommodate the request.
    1. If it has enough resources, it allocates the slot(s) and informs all nodes of the allocation during one of the next beacons.
    2. If it does not have enough resources, it indicates this in one of the next beacons.
  4. Node A listens to beacons to see if its reservation has been accepted.
    1. If no feedback is received within a given time period, it assumes the request has failed.
    2. If the allocation has been accepted, A will see the resources and slot(s) it has been allocated in the beacon.
    3. If the coordinator has indicated the resources are not available, A may attempt to renegotiate.

Even if slots have not been allocated to a node, beacons may indicate the coordinator has data to send to a node. In this case, the node in question may send a data request during the CAP, to which the coordinator will reply with an ACK to indicate it will send the data (and therefore the node should not sleep). Upon correct reception of the data, the node will reply with an ACK. If no ACK is received after sending the data request, the node may sleep and try again in the next super-frame.

In non-beaconed mode, this operation continues for the entire super-frame.

TDMA - Reservation Based MAC

Involves splitting the timeline into slots, and assigning these to nodes which will only transmit in their designated slot. But how do we assign the slots?

Typically, we build a tree rooted at the sink, and assign slots depending on whether we are targeting broadcast or converge-cast.

The chance of node failures must also be considered.

Network Layer

The Network Layer is responsible for finding the path to be followed by data packets from source node to destination node.

There are a few key concepts:

Flooding

Very basic protocol - nodes which receive a given packet for the first time broadcast it to all neighbours. It is not forwarded by its intended recipient.

Gossip

Similar to flooding, but nodes only forward to a subset of their neighbours. It is more scalable compared to flooding.

Distance Vector (DV) Routing

Operates using distance vectors - each node knows the cost to reach each of its one-hop neighbours. The Bellman-Ford algorithm can then be used to calculate the distances to route to other nodes in the network. This algorithm is used as it only requires information received from a node’s one-hop neighbours.

The algorithm operates as follows:

  1. Compute costs of all direct links to the one-hop neighbours of a node.
  2. Create initial routing table.
  3. Create/update distance vector (the distances to other nodes in the network) using the distances to adjacent nodes.
  4. Periodically broadcast the distance vector to the node’s local neighbourhood. Typically this period ranges from seconds to minutes.
  5. Nodes hearing the DV use it to update their own routing tables, and return to step 3.

DV updates no longer arriving may indicate to a node that a link has gone down. In this case:

  1. The node will update its DV setting the cost to the supposedly failed node to infinity, and broadcasts.
  2. Adjacent nodes update routing tables with this new information.
  3. This continues until a new path is distributed throughout the network.

This can result in loops occurring until nodes learn about failed links.

Destination Sequenced Distance Vector (DSDV)

When a node hears new information or information with a better metric than a currently stored route, it updates its table and increments the sequence number to the next even number.

If a node detects a broken link, the sequence number is incremented to the next odd number and the information is broadcast. When an update to resolve the broken link is discovered, it will have the next even sequence number and so will overwrite the odd-numbered information.

Fluctuations

Variations in the time taken for information to reach nodes can lead to fluctuations and unnecessary route advertisements being broadcast for a period of time, before the routing tables settle.

Can be resolved by measuring and recording a settling time, and waiting for twice this length of time before broadcasting any updates which are received.

Proactive method of routing based on link state routing.

Selecting Multipoint Relays

Can use a heuristic approach to select each node’s multipoint relays. Need to consider nodes within a two-hop neighbourhood of node $x$.

  1. Initialise $MPRSet(x) = \emptyset$.
  2. While $\exists n \in N_2(x)$ not covered by $MPRSet(x)$…
    1. Add to $MPRSet(x)$ the node in $N_1(x)$ which would cause the greatest number of uncovered nodes in $N_2(x)$ to become covered.

Each node also maintains a list of neighbours which have selected it as a multipoint relay. A node will forward packets received from nodes in this list. These lists are also exchanged periodically in Topology Control (TC) packets, which are then used to compute routing tables.

Dynamic Source Routing (DSR)

Protocol based on flooding to find new routes.

Improvements

Promiscuous mode and caching can be used to improve the performance of DSR.

Note that RR packets should be forwarded only if they are received on a link which is known to be bi-directional. This is because otherwise, the RRp packet could not be reversed back through the network. If IEEE 802.11 is used, then links have to be bi-directional anyway, though.

A Route Error (RE) packet is sent back to a sender by nodes involved in a route if a link breakage is detected.

The source will then flood the network to discover a new route, and intermediate nodes will update their caches if in promiscuous mode.

Multiple Routes

A destination may reply with RRp packets for every RR it receives, and then a metric may be used by the source to select the best route to use. Intermediary nodes may also reply with RRp’s from their caches in addition to forwarding the RR.

Ad-Hoc On-Demand Distance Vector Routing (AODV)

DSR includes the full route in packet headers, which results in large headers with little packet data. AODV attempts to improve on DSR by maintaining information about a path at the nodes, so that data packets do not need to include full routes.

Cached routes in AODV are different from DSR:

AODV uses the same concept of sequence numbers as in DSDV. The destination sequence number specifies how fresh a route to the destination must be before it can be accepted by the source.

Information about link breakages are propagated using unsolicited RR packets with updated destination sequence number and metric.

Locally, routes can be fixed with local query (LQ) packets with a short TTL, where if a LQ finds the destination then the destination replies with a RRq with the new found route.

Temporally Ordered Routing Algorithm (TORA)

Based on destination-oriented Directed Acyclic Graphs (DAGs). The algorithm can establish routes quickly with multiple routes to a destination, and only reacts when necessary, not to every topological change.

There are three basic functions in the TORA algorithm:

At any point in time, an order quintuple is associated with each node $n_i$, $H_i = (ti, oid, ri, di, i)$.

This represents the hight of a node $n_i$ with respect to:

Data Centric Routing

Directed Diffusion

There are four main stages to the operation of this routing method:

  1. Interest propagation
    • The data request is provided by interest messages initiated by the sink.
    • Interest messages are exploratory in nature and serve to detect nodes with matching data for a particular task.
    • Nodes store interest messages in their interest cache and broadcast them to their neighbours.
    • Messages will include fields such as when the interest expires, the interval to send the data, and perhaps an area the sink is interested in.
  2. Gradient setup
    • Gradients indicate the nodes from which the interest was received.
    • Local rules may be defined to set up gradients:
      • All nodes from which the interest message was received.
      • Node from which the interest message was first received.
      • Nodes with the highest remaining energy.
    • Interest messages indicate the required data from the sensors - for a specific period of time and with a specific data rate.
    • Nodes which match the interest become source nodes and send data along the interest’s gradient route.
  3. Reinforcement
    • Initial interest messages are exploratory messages - intended for path setup and repair.
    • Once the sink starts receiving data, it can reinforce a specific route by resending the interest to a specific neighbour.
      • A reinforced route allows receiving ‘real data’ at a higher data rate.
      • For example, the sink might choose the neighbour from whom it first received the latest event matching the interest.
  4. Data delivery
    • Source will continue to reinforce routes to continue receiving data.
    • Routes can be negatively reinforced by not reinforcing them - the gradients will eventually expire.
    • Can also send interest with lower data rate for negative reinforcement.

Rumor Routing

Hierarchical Routing

Data-centric routing methods with flat topologies suffer from data overload close to the sink as the node density increases - unequal use of energy.

Low Energy Adaptive Clustering Hierarchy (LEACH)

Set-up Phase
Steady State Phase

Collection Tree Protocol (CTP)

CTP is intended to be robust to stale route information and agile to link dynamics. Uses data-path validation - using data packets to dynamically probe and validate the consistency of its routing topology.

It also has a low overhead when the topology is stable.

Data-path Validation

Adaptive Beaconing

Data Transmission

Requires…

CTP uses a very aggressive retransmission policy. By default, it will retransmit a packet up to 32 times. Instead of dropping the packet, CTP combines a retransmission delay with proactive topology repair to increase the chances of delivering the current packet.

Reprogramming Techniques for WSNs

Requirements of a WSN may change - e.g. the understanding of an environmental phenomenon may change with time, requiring changes in the WSNs.

Traditionally, reprogramming is done manually, usually node by node by sending the code from a PC directly to the memory of a sensor node - time consuming, sometimes not feasible. The solution is reprogramming with no physical contact with the sensor nodes, by disseminating the code wirelessly.

We desire approaches which are energy efficient, scalable, and topology independent.

Therefore, we need strategies for accessing the medium, disseminating code, and making sure the code is disseminated correctly, all while saving energy.

Multihop Network Reprogramming Service

Sending Packets with Pipelining

Backbone Approach

A dominating set $DS$ of a graph $G = (V, E)$ is a subset $V’$ of $V$ such that every vertex $v \in V$ is either in $V’$ or adjacent to some member of $V’$. A dominating set is connected if the sub-graph induced by it is connected. A minimum connected dominating set is a connected dominating set of minimum cardinality.

Multipoint Relays (MPR)

Failure Detection

In a Synchronous system we assume the following conditions:

In an asynchronous system, none of these assumptions are known to hold. When a process takes a step, another process may take at most an unbounded (but finite) number of steps.

In a partially synchronous system, the timing assumptions may be eventual.

Properties of Failure Detectors

Implementation of Failure Detectors

Algorithm Outline

Neighbourhood View Consistency

The Neighbourhood View Consistency problem describes the ability for nodes in a given neighbourhood to agree on what nodes are alive and what nodes are unreachable.

The formal specification consists of two parts: safety and liveness.

In the fault model assumed, we can have:

Solving NVC with a Perfect Failure Detector (PFD) is impossible.

A device capable enough to solve strong NVC should be able to:

So as opposed to returning a list of suspects, it also returns the neighbourhood of each suspect.

It is impossible to implement a perfect PseudoCrash detector during memory failures either - only eventual strong accuracy and eventual strong completeness are possible.

A possible implementation is in the slides.

Weak NVC

The Weak NVC problem is defined as:

Given a network $G = (V, A)$, and two nodes $n, m \in V$, a program provides weak NVC for $G$ if every computation of the program satisfies:

Possible implementation is in the slides.