CS345 - Sensor Networks and Mobile Data Communications

A wireless sensor network (WSN) is a class of ad hoc network where nodes can interact with the environment through sensors, process information locally and transmit this information wirelessly to neighbours.

A mote is a microcontroller, transceiver, power source, memory unit and sensor. Motes typically consist of a transceiver, sensor board, programming board and battery. They are usually inexpensive, disposable and used in large numbers.

Motes are usually scattered in a sensor field. They communicate with a sink which can then communicate with the end user. There can be multiple sinks and end users.

WSNs are typically represented as undirected graphs.

The three types of wireless network are

  • Infrastructure, single hop, has backbone and base stations eg. cellular networks
  • Infrastructure-less, multi hop, eg. WSNs
  • Hybrid networks, multi hop, has backbone and access points, some eg. WSNs

Cellular networks are an example of an infrastructure-based wireless network

  • Mobile (cell) phones connect to the base station which connect to the telephone network
  • Space division multiplexing (SDM) allocates a frequency to each space
  • Complex infrastructure - base stations, switches for call forwarding, location registers

A node in a WSN can act as a host or a router. New nodes are detected automatically and inducted seamlessly.

Characteristics of WSNs

  • Data may need to traverse multiple nodes to reach the destination (multi-hop)
  • Mobility may render connections useless, thus affecting routes
  • Traffic may produce congestions thus affecting routes.

A WSN requires at least two nodes broadcasting their presence with their respective address information using control or beaconing messages.

The physical layer

The physical layer converts data into signals suitable for wireless transmission. These analog signals are called radio frequency (RF) communications.

RF communications usually employ periodic signals, especially sinusoidal waves, as carriers.

These signals are of the form $s(t) = A\cos(2\pi ft + \varphi)$ where $A$ is the amplitude, $f$ is the frequency, $t$ is time and $\varphi$ is the phase shift.

The capacity of a channel is defined as $C = B*\log_2(1+S/N)$ where $B$ is the bandwidth in Hz, $S$ is the average received signal power in watts and $N$ is the average noise in watts. $S/N$ is called the signal-to-noise ratio (SNR) and is measured in dB. Decibels are logarithmic so 10dB corresponds to a change in power by a factor of 10, 20dB is a factor of 100 and 30dB is 1000.

For example, a channel with an SNR of 20dB and bandwidth of 10MHz has a maximum data rate of $C = 10000000 * \log_2(1 + 100)$ which is around 66 Mbps.

WSNs and other ad-hoc networks transmit over the Industrial, Scientific and Medical (ISM) band. This was originally reserved internationally for the use of RF for ISM purposes other than communications. It is license-free and currently also used for short-range, low-power communications systems such as cordless phones, Bluetooth devices and wireless computer networks. The most common frequencies used are between 2.4 and 5 GHz.

  • A signal is an EM wave
  • Symbol rate is the number of symbol changes per second in a modulated signal, measured in bauds (Bd)
  • Bit rate is the bits per second conveyed in a modulated signal. One symbol may represent more than one bit
  • Bandwidth is a range of frequencies where most of the signal energy is found
  • A channel is a wireless link used for transmission

Data generated by nodes is either digital or analog. Modulation converts data to EM waveforms that can be radiated by an antenna. Demodulation maps EM waveforms back to the original data. Modulation is achieved by modifying either the amplitude, frequency or phase shift of the carrier signal depending on the data to transmit. Changing the amplitude is called amplitude modulation (AM), frequency is frequency modulation (FM) and phase is phase modulation. The latter is less commonly used because it is less stable.

Digital data can be modulated using shift keying. Amplitude shift keying (ASK) sets the amplitude to the bit value. FSK increases the frequency for a 1 and PSK changes the phase for each value. Again, PSK is less commonly used because phase changes are harder to detect than the others.

Quadrature Phase Shift Keying (QPSK) has four possible phases (0, 90, 180 and 270 degrees) that the carrier can have at a given time. Information is conveyed through phase variations as phase can't be measured absolutely. This means two bits of information can be conveyed for each phase variation.

Multiplexing allows multiple signals to share a medium with minimum interference.

  • Space Division Multiplexing (SDM) - Senders are separated in space, such as radio stations in different cities.
  • Frequency Division Multiplexing (FDM) - The available bandwidth is split into smaller, non-overlapping bands. The gap between these bands is called guard space and prevents interference.
  • Time Division Multiplexing (TDM) - The whole bandwidth is assigned to a particular transmission for a certain period of time. Between transmissions is a short rest, also called a guard space, to reduce interference.
  • Code Division Multiplexing (CDM) - Various transmissions occur simultaneously by coding the signals.

EM waves may be distorted during wireless transmission.

  • Path loss and attenuation - signal strength decreases as a function of distance.
  • Reflection and refraction - EM waves bounce off of surfaces or propagate through a surface.
  • Diffraction - EM waves propagate through sharp edges, generating new waves with weaker strength
  • Scattering - EM waves scatter when incident at a rough surface
  • Doppler fading - If transmitter and receiver move relative to each other, EM waves undergo a shift in frequency

The bit error rate (BER) is the number of bit errors over the total number of transmitted bits. It is dependent on channel characteristics and modulation technique. A BER of $10^-2$ means 1 bit error per 100 transmitted bits. BER is calculate using the SNR.

The SNR in decibels is calculated using $$ SNR_{dB} = 10\log_{10}\left(\frac{P_r}{N_o}\right) $$ where $P_r$ is the received power and $N_o$ is the noise.

For bit errors, the energy per bit in relation to the noise energy is given by $$ \frac{E_b}{N_o} = SNR \cdot \frac{1}{R} = \frac{P_r}{N_o} \cdot \frac{1}{R} $$ where $E_b$ is the energy per bit and $R$ is the bit rate.

For example, the BER for FSK modulation is given by $\frac{1}{2} \exp\left(-\frac{E_b}{2N_o}\right)$.

  • Using a fixed bit rate requires more power or higher BER.
  • Using a fixed BER requires more power or reducing the bit rate.
  • Using fixed power required increased BER or lower bit rate.

Error detection

Errors can be detected using parity or checksums. These do not provide any way to locate or correct errors. If an error is detected a packet must be retransmitted.

Forward error correction (FEC) techniques add redundancy to the transmitted data, so a limited number of errors can be corrected. These methods include Hamming codes and convolutional codes.

The transmitter (TX) and receiver (RX) should agree on a codebook. The codebook is a mapping from $k$-bit data sequences to $n$-bit codewords with $n > k$. The code rate is $r = k/n$. TX takes data blocks, maps them to codewords and transmits them. RX receives the codewords and maps them back to data blocks.

The error correction capability of a code is directly related to the Hamming distance between any pair of codewords. The Hamming distance between $n$-bit codewords $v_1$ and $v_2$ is given by the number of 1s in the XOR of $v_1$ and $v_2$. For example, $v_1 = 011011$ and $v_2 = 110001$ has XOR of $101010$, so the Hamming distance is 3.

When an invalid codeword is received, the receiver should choose the valid codeword with the minimum Hamming distance to the invalid codeword. For some positive integer $t_c$, if a code satisfies $d_{\min} \geq 2t_c + 1$ then the code can correct up to $t_c$ bit errors where $d$ is the Hamming distance.

Spread spectrum techniques provide robustness against multi-path effects

  • Direct Sequence Spread Spectrum (DSSS)
  • Frequency Hopping Spread Spectrum (FHSS)

The same power can be spread over a wider range of frequencies.

DSSS XORs the binary data with a chipping sequence. Since the bandwidth occupied by the digital signal is roughly the inverse of the symbol duration, the resulting sequence has a higher bandwidth.

Barker codes are pseudo-noise sequences which can be used as a chipping sequence. They have low correlation sidelobes, that is, there isw a low correlation of the codeword with a time-shifted version of itself. The maximum autocorrelation value occurs when there is no time-shift. This allows detecting transmission delay as if there is a time shift the autocorrelation is lower.

DSSS is the standard for wireless local area networks (WLANs). WLANs employ the 11-chip Barker sequence. Each bit is encoded before modulation. It is also the standard for low-rate wireless personal area networks (WPANs) which can be used for WSNs.

FHSS splits available bandwidth into multiple channels. Transmitter and receiver stay on one of these channels for a certain time, then hop to another channel according to a pseudo-random hopping sequence. FHSS is used by Bluetooth.

Data to be transmitted by the physical layer is organised into packets or frames. Each packet should contain

  • SYNC - information about the transmitter's clock rate used for modulation
  • SFD - bit duration, start and end of the bits
  • start and end of the whole packet

The SNYC and SFD allow the receiver to correctly sample each bit.

The data link layer is responsible for accessing the medium. Medium access control (MAC) controls when a node should transmit data to another node or set of nodes.

  • Broadcast transmission sends a transmission to all nodes
  • Unicast transmission transmits to a single node
  • Multicast transmission sends a transmission to a subset of nodes

Nodes in WSNs usually transmit in half-duplex mode. This allows communication in both directions, but only one direction at time, not simultaneously. Only one signal can be received by a node at a particular instant of time. If nodes try to transmit simultaneously, a collision will occur at the receiver.

MAC aims to synchronise the receiver and transmitter with minimum overhead while avoiding collision of packets and needless waiting. It has to guarantee quality of service, increase throughput and reduce latency while being energy efficient.

MAC needs to avoid two problems

  • Hidden node problem - packet collision when one node is unaware of another
  • Exposed node problem - if one node can hear another transmitting it will wait, but if the nodes are transmitting to different sinks then the first node is waiting unnecessarily

Carrier sense multiple access with collision avoidance (CSMA/CA) is used to avoid collisions. It works by checking there are no transmissions happening in the channel before transmitting. To check there are no transmissions, it waits for a set inter-frame space. If there are transmissions, it contends for access. Each node randomly selects a delay from the contention window (CW) before transmitting.

Signalling packets can be used to prevent collisions. The transmitter sends request-to-send (RTS) and the receiver sends clear-to-send (CTS). Once the packet is transmitted, the receiver sends acknowledgement (ACK) and other transmitters can then content.

Any node overhearing an RTS defers all transmissions until a CTS is received. Any node overhearing a CTS defers all transmissions until ACK is received.

The exponential back-off algorithm is when collisions occur. It increases the contention window if a collision is suspected. Every time transmission fails, the CW gets exponentially larger.

The three main protocols for MAC are

  • S-MAC
  • B-MAC
  • X-MAC

Sensor medium access control (S-MAC) is based on CSMA/CA with signalling packets. Node activity is scheduled into cycles called frames. Each cycle consists of sleep, then listening. Listening consists of a SYNC period and RTS period for synchronisation and retransmission respectively. This method allows motes to sleep, which saves energy. Each node keeps a schedule table of its known neighbours. Before starting the cycle, the nodes choose a schedule and exchange it with their neighbours.

During SYNC, if a node receives a schedule from another node it will become a follower. Otherwise, it will broadcast its own schedule and become a synchroniser. If it receives another schedule whilst broadcasting its own, it drops its schedule and becomes a follower. If it has neighbours and receives multiple schedules then it becomes a border node.

Nodes periodically listen for a whole SYNC period to discover new nodes.

B-MAC (Berkeley MAC) attempt to overcome two important energy issues with S-MAC

  1. Periodic transmission of SYNC packets
  2. Nodes active during the listening period wait for possible incoming packets

It uses Clear Channel Assessment (CCA) for carrier sensing instead of signalling packets. Nodes have unsynchronised sleep schedules using Low Power Listening (LPL).

CCA works by sampling the channel after transmission to compute an average noise floor estimate. If noise in the channel is above a threshold then it is busy.

LPL, also known as preamble sampling, sends a preamble before each packet to alert the intended receiver. Nodes periodically wake up and check for preambles. If they receive a preamble, they then wait for transmission before deciding whether to continue listening. LPL is simple, asynchronous and energy efficient but still has some energy problems

  • the receiver must wait until the preamble is completely transmitted before receiving data
  • other neighbours that wake up during the preamble keep listening until it is transmitted completely only to find out the packet isn't addressed to them

X-MAC is like B-MAC but uses shorter preambles.

  • Uses less energy at the transmitter and receiver
  • Reduces per-hop latency
  • Intended recipient remains awake for its data packet
  • Neighbours overhearing the preamble can return to sleeping quickly
  • Scales well with increasing node density
  • Reduces the time spent transmitting preambles
  • If the receiver sends and ACK between preambles the transmitter can start sending immediately

Network layer

One type of routing is flooding. A node broadcasts to all its neighbours and then asks them to do the same.

Advantages of flooding

  • Simple
  • Efficient for small packets
  • Higher reliability of delivery

Disadvantages of flooding

  • Potential high overhead
  • Waste of bandwidth and energy
  • Packet may not arrive

Two methods for on-demand routing for infrastructure-less networks are

  • Dynamic Source Routing (DSR)
  • Ad-hoc On Demand Vector routing (AODV)

DSR is based on flooding to find new routes. Route request (RR) packets are flooded by a source node. If the packet reaches the destination it replies with a route reply packet. The route request packet includes the route it took from source to destination. The request reply packet is then sent on the route obtained.

Some improvements to DSR are promiscuous mode and caching. Intermediate nodes in a path can learn about routes to other destinations and store this information in a cache. Upon receiving an route request packet, nodes can send back a request reply with the route stored in their cache. Nodes can also learn about broken links and remove them from cache. Cache can speed up route discovery and reduce propagation of route request packets.

A route error packet is sent to the source by any node in the event of a breakage. The source then floods the network with another route request if there is no other route in cache. Intermediate nodes receiving the route error will also update their cache.

DSR includes the full route in its packet headers which can be long for large networks. AODV routing is based on DSR but reduces overhead by maintaining the route information at the nodes. Route request packets are flooded like in DSR, but when a node forwards a RR packet it creates a pointer to the previous node towards the source. When a node forwards a route reply it creates a pointer to the next node towards the destination. The AODV cache has one entry for each destination whereas DSV may have several routes for one destination.

Flooding can be used is WSNs but has several flaws.

  • Implosion - multiple copies of the same message
  • Overlap - nodes with overlapping sensing regions send similar routes
  • Resource blindness

Gossiping is similar to flooding but each node chooses one neighbour to forward a packet. This helps prevent implosion. Some nodes may transmit to multiple neighbours to prevent the spread stopping if a transmission fails. Smart gossiping uses different probabilities, smaller for dense networks and larger for sparse networks.

There are four routing methods in WSNs

  • Data centric - Designed to route information to the sink from a set of nodes that meet a criterion
  • Hierarchical - Designed to route information using clusters. Cluster-heads aggregate and fuse data
  • Geographical - Designed to exploit location information to route data to a specific location
  • Quality of Service (QoS) based - Designed to guarantee a certain QoS by employing performance metrics such as throughput, cost and latency

It is hard to assign specific addresses to motes in very large WSNs. Data centric routing uses attribute-based naming by querying a phenomenon instead of an individual node.

One methods of data centric routing is directed diffusion. All nodes in a directed-diffusion-based network are application aware, which allows for empirically selecting good routes. There are four stages to construct routes between the sink and motes of interest

  1. Interest propagation - The sink floods interest messages which are then cached by each node and broadcasted to their neighbours. Interest messages are used to detect nodes with relevant data for a particular task
  2. Gradient setup - Gradients indicate the nodes from which interest was received. Nodes that match the interest become source nodes and send data along the interest's gradient route
  3. Reinforcement - Once the sink starts receiving data it can reinforce a specific route by resending an interest message to a specific neighbour. A reinforced route allows for faster data transfer.
  4. Data delivery - Positive reinforcement is used to reinforce routes that are sending data as expected. If a link becomes broken, it will stop being reinforced and its gradient will expire. If negative reinforcement is used and a node isn't sending data quickly enough it will be negatively reinforced with an interest message with lower data rate

Another method of data centric routing is rumour routing. It is event-based, which is ideal for dense WSNs. Nodes create and spread agents, which are packets that spread information about an event. Agents propagate and install routing information to events in each node they visit. If the sink is interested in an event, it will send out a query on a random walk, which has a high probability of finding a pre-established route to the event. This high probability is based on Monte-Carlo simulation, which shows two random lines in a bounded rectangular region will intersect with a probability of 69%. The more lines, or routes in a network, the higher the probability.

Data-centric routing with flat topologies suffers from data overload close to the sink as the node density increases. Hierarchical routing uses a hierarchical topology where nodes are grouped into clusters, each with a cluster head.

Low-energy Adaptive Clustering Hierarchy (LEACH) dynamically selects cluster heads to form clusters. The cluster head is changed so high-energy consumption is spread across all nodes. Communications inside a cluster are directed to the cluster head, which then directly communicate with the sink or other cluster heads.

The operation of LEACH is controlled though rounds. Each round consists of a setup phase and steady state phase. Setup includes selecting a cluster head, creating a cluster and creating a communication schedule. Once set up, the cluster heads randomly choose a spreading code and inform the nodes in their cluster.

Geographical routing makes use of location information. GPS devices and be used to provide information about location to nodes, but this uses lots of energy and this information is usually only needed during initialisation. Localisation protocols can be used instead. The received signal strength or time of arrival can be used to estimate the distance to the transmitter.

During greedy forwarding, a node selects a feasible neighbour based on different metrics.

  • Most forwarding within radius - node with most advancement on straight line from source to sink
  • Nearest forward progress - node nearest to the source
  • Pure greedy scheme - node that is closest to the sink
  • Compass metric - Node that is closest to the straight line connecting from source to sink

Greedy routing might fail so Greedy Perimeter Stateless Routing (GPSR) is used, which uses the positions of nodes and the location of the destination to make forwarding decisions. It is based on pure greedy routing and perimeter routing. If greedy routing fails, perimeter routing is used instead. Nodes maintain a neighbour table with the location of their one-hop neighbours which can then be used to determine the location of the destination.