Wireless Sensor Networks Infrastructure

Cheatsheet Content

Unit IV: Infrastructure Establishment Topology Control Clustering Time Synchronization Localization and Positioning Sensor Tasking and Control Topology Control In a crowded network, topology control techniques can help overcome issues like: Many nodes interfering with each other. Numerous possible routes. Routing protocols recomputing routes due to small node movements. Network topology is defined by the subset of active nodes and active links for direct communication. A topology-control algorithm transforms a graph $G = (V, E)$ (representing the network) into $T = (V_T, E_T)$ such that $V_T \subseteq V$ and $E_T \subseteq E$. Aspects of Topology-Control Algorithms Connectivity: A connected graph $G$ should not become disconnected in $T$. If a multihop path exists in $G$ between $u$ and $v$, it should also exist in $T$. Stretch factors: Removing links increases path length. The hop stretch factor is the worst increase in path length between $G$ and $T$. Throughput: The reduced topology should sustain comparable traffic to the original network. Robustness to mobility: When neighborhood relationships in $G$ change (e.g., due to node movement or radio channel changes), other nodes might need to update their topology information. Algorithm overhead: The overhead (additional messages, computational load) should be small. Hierarchical Networks by Clustering Some nodes are assigned special roles, like controlling neighbors. These "controllers" are called clusterheads . Clusterheads aggregate and compress traffic from many sensors to a single station. Clustering formally identifies a set of subsets of nodes $V_i, i = 1, \dots, n$ such that $\bigcup_{i=1,\dots,n} V_i = V$. Properties of Various Clustering Approaches Clusterheads: For each cluster $V_i$, there might be a unique node $C_i$ (the clusterhead) that represents the set and performs various tasks. Clusterhead Neighbors: While two clusterheads can be direct neighbors, it's often desirable for them to be separated, forming an independent set . Maximum Independent Sets: Aim to contain as many nodes as possible without violating independence, leading to many clusters around these clusterheads. Overlapping Clusters: When forming clusters, the question arises of which cluster to assign non-clusterhead nodes, especially those adjacent to two clusterheads. One option is to assign these nodes to both clusters, resulting in overlapping clusters. If overlap is not desired, a decision rule is needed to assign nodes unambiguously. Cluster Communication: A node adjacent to two clusterheads can act as a gateway for intercluster communication. Intracluster communication routes via clusterheads, which then use gateways. If two clusterheads are separated by two nodes, and no single node can act as a gateway, two nodes from each cluster together can form a distributed gateway . Number of Gateways: Multiple gateways can connect two clusterheads. Redundancy in intercluster communication may be desirable depending on optimization goals. Maximal Diameter of a Cluster: A common maximum cluster diameter is two (each node at most two hops away from any other). Sometimes, one-hop clusters or multihop clusters with larger diameters are used. Time Synchronization Time synchronization is crucial for many wireless sensor network applications and protocols. Nodes use local clocks driven by oscillators. Due to random phase shifts and drift rates , local clocks can differ, leading to loss of synchronization. Reliable Time Estimation Keep sensor clocks tightly synchronized using dedicated time synchronization algorithms . Combine readings from multiple sensors and "average out" estimation errors. Node Clocks and The Problem of Accuracy The hardware clock of node $i$ at real time $t$ is $H_i(t)$. A local software clock $L_i(t)$ is computed as: $$L_i(t) := \theta_i \cdot H_i(t) + \phi_i$$ where $\phi_i$ is the phase shift and $\theta_i$ is the drift rate. It's not possible or desirable to influence the oscillator directly. Clock adjustment is done by changing $\theta_i$ and $\phi_i$. Clock Precision within a Network External synchronization: Nodes $1, 2, \dots, n$ are accurate at time $t$ within a bound $\delta$ if $|L_i(t) - t| Internal synchronization: Nodes $1, 2, \dots, n$ agree on time within a bound $\delta$ if $|L_i(t) - L_j(t)| Need for Time Synchronization in WSN Nodes switch on at different, random times, so their initial phases $\phi_i$ are random. Oscillators have slight random deviations from nominal frequency (drift, clock skew) due to impure crystals or environmental conditions (pressure, temperature). Oscillator frequency is time variable (short-term variations from temperature, voltage, air pressure). Synchronization algorithms must resynchronize frequently to track changing frequencies. Even with identical oscillators and simultaneous starts, the difference $|L_i(t) - L_j(t)|$ can grow arbitrarily large over time. Hence, a time synchronization protocol is needed. Properties and Structure of Time Synchronization Algorithms Physical time vs. logical time: WSNs mostly require physical time. External vs. internal synchronization: Algorithms may or may not require synchronization with external timescales. Global vs. local algorithms: Global algorithms synchronize all nodes (or a partition) of a network. Local algorithms restrict scope to a geographical neighborhood. Global synchronization implies local synchronization. Absolute vs. relative time: Many applications need only accurate time differences. Absolute synchronization (including relative synchronization as a special case) is more general. Hardware- vs. software-based algorithms: Hardware-based algorithms use dedicated hardware (e.g., GPS receivers). Software-based algorithms use plain message passing over normal data channels. A priori vs. a posteriori synchronization: A priori protocols run continuously. A posteriori protocols are triggered by external events. Deterministic vs. stochastic precision bounds: Deterministic algorithms guarantee absolute upper bounds on synchronization error. Stochastic algorithms provide probabilistic bounds. Time Synchronization in Wireless Sensor Networks - Specifics Algorithms must scale to large, multihop networks of unreliable, energy-constrained nodes. Precision requirements vary widely (microseconds to seconds). Extra hardware for synchronization is generally avoided due to cost and energy penalties. No fixed upper bounds for packet delivery delay (due to MAC protocols, errors, retransmissions). Manual configuration of single nodes is not an option. Protocols Based On Sender/Receiver Synchronization Lightweight Time Synchronization Protocol (LTS) Synchronizes sensor network clocks to reference nodes. Balances energy expenditure and achievable accuracy. Subdivides synchronization into two blocks: Pair-wise synchronization between neighboring nodes. Synchronizing all nodes to a common reference. Pair-wise Synchronization Node $i$ wants to synchronize with node $j$. Node $i$ formats a synchronization request packet, timestamped at $t_1$ with $L_i(t_1)$. Packet is handed to OS/protocol stack, incurring medium access delay. Node $i$ sends the first bit at $t_2$. Node $j$ receives the last bit at $t_3 = t_2 + \tau + t_p$, where $\tau$ is propagation delay and $t_p$ is packet transmission time. At $t_4$, packet arrival is signaled to node $j$, timestamped at $t_5$ with $L_j(t_5)$. Node $j$ formats an answer packet at $t_6$, timestamped with $L_j(t_6)$, and hands it to OS/networking stack. This packet includes $L_j(t_5)$ and $L_i(t_1)$. How node $i$ infers its clock correction Node $i$ wants to estimate the offset $O = \Delta(t_1) := L_j(t_1) - L_i(t_1)$. Assuming no drift between clocks from $t_1$ to $t_8$, node $i$ estimates $O$ by estimating $\Delta(t_5)$. $L_j(t_5)$ is generated at some unknown time between $t_1$ and $t_8$. There is one propagation delay $\tau$ plus packet transmission time $t_p$ between $t_1$ and $t_5$. There is another time $\tau + t_p$ between $t_5$ and $t_8$ for the response packet. For stationary nodes, propagation delays are assumed equal in both directions. The time between $t_5$ and $t_6$ is known from $L_i(t_6) - L_j(t_5)$. The uncertainty about $t_5$ can be reduced to the interval: $$I = [L_i(t_1) + \tau + t_p, \quad L_i(t_8) - \tau - t_p - (L_j(t_6) - L_j(t_5))]$$ If we assume that times spent in OS/networking stack, interrupt latencies, and medium access delay are the same in both directions, then node $i$ concludes that $j$ generated its timestamp $L_j(t_5)$ at time (from $i$'s point of view): $$L_j(t_5) = \frac{L_i(t_1) + \tau + t_p + L_i(t_8) - \tau - t_p - (L_j(t_6) - L_j(t_5))}{2}$$ The offset $O$ is then: $$O = \Delta(t_5) = L_j(t_5) - L_i(t_5) = \frac{L_i(t_8) + L_i(t_1) - L_j(t_6) - L_j(t_5)}{2}$$ Node $i$ can adjust its local clock by adding $O$. This synchronizes node $i$ to $j$'s local time, at the cost of two packets. Localization and Positioning Possible Approaches of Finding Position Three main approaches for determining a node's position: Using information about a node's neighborhood ( Proximity ). Exploiting geometric properties ( Triangulation and Trilateration ). Analyzing characteristic properties by comparing with premeasured properties ( Scene Analysis ). Anchors Necessary to provide absolute coordinates. Nodes that know their own position in the absolute coordinate system. Can rotate, translate, and scale a relative coordinate system to match the absolute one. Also called "beacons" or "landmarks". Proximity Simplest technique, exploits finite range of wireless communication. Determines if a node is in proximity of an anchor. Example: Infrared communication restricted by walls provides simple location information (e.g., room). Proximity-based systems use information from several overlapping anchors for approximate positioning. Trilateration and Triangulation Communication between two nodes extracts geometric relationship (distance or angle). This information derives node positions. Lateration: uses distances between entities. Angulation: uses angles between nodes. For lateration in a plane, precise distance measurements to three non-collinear anchors are needed. Using distances and anchor positions, the node's position is at the intersection of three circles around the anchors. In reality, distance measurements are imperfect. More than three anchors are used, leading to a multilateration problem. The problem of imprecise measurements can be solved using multiple measurements. Determining Distances Wireless communication characteristics (e.g., RSSI, ToA, TDoA) can be measured at the receiver to estimate distance. Received Signal Strength Indicator (RSSI) If transmission power $P_{tx}$ and path loss coefficient $\alpha$ are known, receiver uses received signal strength $P_{rcvd}$ to find distance $d$: $$P_{rcvd} = c \frac{P_{tx}}{d^\alpha} \implies d = \sqrt[\alpha]{c \frac{P_{tx}}{P_{rcvd}}}$$ Advantage: Acceptable in WSNs, no additional hardware, distance estimates without communication overhead. Disadvantage: RSSI values are not constant and can oscillate heavily, even if sender and receiver are static. Time of Arrival (ToA) Also called "time of flight," exploits relationship between distance and transmission time when propagation speed is known. If sender and receiver know transmission start time, arrival time at receiver computes propagation time and thus distance. To relieve receiver, sender can measure round-trip time (assuming symmetric paths). Requires very high resolution clocks for acceptable accuracy. Time Difference of Arrival (TDoA) Uses two transmission mediums with very different propagation speeds (e.g., radio waves and ultrasound). Sender transmits simultaneously. Receiver measures time until ultrasound arrival after radio arrival. Disadvantage: Needs two types of senders and receivers on each node. Advantage: Considerably better accuracy than RSSI-based approaches. Determining Angles Measuring an angle is an alternative to measuring distances. Angle can be between a connecting line (anchor to position-unaware node) and a reference direction. Can also be between two connecting lines if no reference direction is known. Traditional approach: directional antennas, rotating like radar/lighthouse. Inappropriate for sensor nodes. Multiple antennas can measure direction of wavefront arrival, but not suitable for WSN. Scene Analysis Analyzes pictures from a camera to derive position. Requires substantial computational effort, not appropriate for sensor nodes. RADAR system uses this approach for indoor positioning. Single-hop Localization Uses measured distance/range or angle and mathematical basics for positioning. Active Badge First system for locating simple, portable devices within a building. Uses diffused infrared as transmission medium; exploits infrared's limitation by walls for location granularity. Badge periodically sends unique identifier via infrared to receivers. Mapping of identifiers to receivers stored on a central server, queried for badge location. Active Office Finds indoor device positioning using ultrasound. Central controller sends radio message with device address. Device sends short ultrasound pulse. Receiver (central controller) measures time of arrival and computes difference between ultrasound and radio pulse arrival times. Distance estimate computed for each receiver. Accuracy: >95% of estimates within 8 cm of true position. RADAR Used for indoor computation of position estimates. Uses scene analysis techniques. Position found by comparing received signal characteristics from multiple anchors with premeasured and stored characteristic values. Anchors or mobile device can send signals. Off-line deployment phase (measuring "signal landscape") cannot always be accommodated. Cricket Addresses privacy concerns by allowing devices to compute their own positions. Based on anchors providing combined radio wave and ultrasound pulses to measure TDoA. Location information extracted from this data. Overlapping Connectivity This outdoor positioning system uses connectivity observation to a set of anchors to determine node position. Assumes transmissions from an anchor are received within a circular area of known radius. Anchor nodes periodically send identifying transmissions. After receiving announcements, a node determines it's in the intersection of circles around these anchors. Estimated position is the arithmetic average of received anchors' positions. Unreceived announcements imply the node is outside respective circles, further restricting possible position. Accuracy depends on the number of anchors; more anchors allow higher resolution. Approximate Point in Triangle Idea: decide if a node is within or outside a triangle formed by three anchors. Node can intersect triangles to estimate its own position. If a node is inside a triangle and moves, it must get closer to at least one corner. If a node is outside a triangle, there is at least one direction where its distance to all corners increases. Moving a sensor node to determine position is impractical. If for all neighbors, at least one corner is closer to the neighbor than to the enquiring node, assume it's inside the triangle; otherwise, outside. Positioning in Multihop Environments Single-hop localization assumes direct communication with several anchor nodes. This is not always true in WSNs. Mechanisms are needed to cope with limited geographic availability of precise ranging or position information: Connectivity in a multihop network Multihop range estimation Iterative and collaborative multilateration Probabilistic positioning description and propagation Properties of Localization and Positioning Procedures Physical position vs. symbolic location: Does the system provide data about physical position (numeric coordinates) or symbolic location (e.g., "living room")? "Location" is often used as the more general term. Absolute vs. relative coordinates: Absolute coordinates are valid across a general frame of reference. Relative coordinates can differ for each object/set. A few anchors are necessary for absolute coordinates. Localized vs. centralized computation: Are computations performed locally, or are measurements reported to a central station? Privacy issues are relevant: participants might not want to reveal position to a central entity. Accuracy and precision: Accuracy: Largest distance between estimated and true position. Precision: Ratio with which a given accuracy is reached, averaged over many repeated attempts. Both values make sense when considered together. Scale: Systems designed for different scales (indoor, outdoor, worldwide). Metrics: area covered per unit of infrastructure, number of locatable objects per unit of infrastructure per time interval. Limitations: Inherent deployment limitations (e.g., GPS doesn't work indoors, limited ranges for other systems). Costs: Positioning systems incur costs in time (installation), space (device size), energy (operation), and capital (node price). Sensor Tasking and Control To efficiently and optimally utilize limited resources (battery power, communication bandwidth) in a sensor network, nodes must be carefully tasked and controlled. More nodes participating in sensing increases total information content. However, having all nodes on consumes battery power and reduces effective communication bandwidth due to congestion. Task-Driven Sensing The sensor network (SN) must be selective in choosing which sensor nodes to activate and what information to communicate. Purpose: Obtain detailed information about unknown parts of the environment. Obtaining answers to queries about unknown parameters is a standard algorithm design problem. Classical algorithm/complexity needs modification for WSNs because: Relevant variables are unknown and must be sensed. Cost of sensing different variables or relations can vary. Value of a variable/relationship may be impossible to determine with available resources. Key Questions for Overall Strategy Design What are the important objects in the environment to be sensed? What parameters of these objects are most relevant? What relations among these objects are critical to high-level information needed? Which is the best sensor to acquire a particular parameter? How many sensing and communication operations are needed to accomplish the task? At what level is information communicated (from signal to symbol)?