Wireless and Sensor Networks Notes | B.Sc. (Computer Science) Semester 5 | Mumbai University | munotes

1. It senses. A sensor turns a physical quantity (temperature, moisture, light, vibration, sound) into an electrical signal, which is converted into a number.
2. It processes. A microcontroller, a very small and very frugal processor, decides what to do with the number: store it, compare it with a threshold, combine it with others, or send it.
3. It communicates. A low-power radio sends the result to a neighbouring node, and also receives and forwards other nodes' packets. A packet is one small parcel of data sent over the network in one go.
4. It survives on its own energy. Almost always a pair of batteries, sometimes helped by a small solar cell. Nobody is expected to change them for months.

By 2000 a Berkeley group could already build such a node from shop-bought parts, "on the scale of a square inch in size and a fraction of a watt in power", and wrote a whole operating system for it, TinyOS, which the chapter [TinyOS: Components, Tasks and the Scheduler] takes apart.

The picture: the sensor field, the sink and the way out

Figure 1.1 A wireless sensor network: nodes in the sensor field, a multi-hop path to the sink, and the way out to the user

Read the figure from the event outwards, because that is the direction the data goes.

• The sensor field is the area being watched: the vineyard, the forest, the factory floor. The small circles are sensor nodes scattered over it.
• An event happens near node A: the soil there has dried out. Node A senses it.
• A cannot reach the sink directly, because a low-power radio reaches tens of metres, not the whole field. So A sends its reading to its neighbour B, B to C, and so on through D and E to the sink. Each of those steps is a hop, and the whole route is a multi-hop path. Every node is both a source of its own data and a router for other nodes' data.
• The sink, also called the base station, is the collection point. It is usually better equipped: mains power or a big battery, more memory, and a second way out.
• The sink reaches the task manager node over the Internet or a satellite link. The task manager is where the network is told what to do (what to measure, how often, what to report) and where the results arrive.
• The user is the person or program that actually wants the answer: the farmer, the biologist, the control room.

Notice that there are no routers, cables or towers inside the field. That is what "infrastructureless" means: the nodes themselves are the network. The only infrastructure is at the edge, at the sink and beyond it.

How a WSN differs from the networks you already know

A student who has studied the Internet brings expectations that are wrong here, and each wrong expectation costs marks. Six differences, each with the reason.

1. Energy, not bandwidth, is the scarce resource. A laptop's network card is designed for speed. A sensor node's radio is designed to last a year on two AA cells, and it does so by being switched off almost all the time. Every protocol in this book is judged first on the energy it costs.
2. The network exists for data, not for conversations between named machines. On the Internet you ask a particular address for something. In a WSN the user asks a question about the world (which part of the field is below 20 per cent moisture?) and does not care which node answers. This is called data-centric operation, and the chapter [Design Principles: Data Centricity, Location, Activity and Heterogeneity] develops it.
3. The traffic flows mostly one way, towards the sink. Many sources, one destination. The technical name for this many-to-one pattern is convergecast. An Internet router expects traffic between any pair of hosts; a sensor network is shaped like a funnel.
4. The nodes cooperate and compute inside the network. Rather than send every raw reading to the sink, nodes can combine readings on the way (the average of ten neighbours sent once instead of ten readings sent ten times). The survey calls this the "cooperative effort of sensor nodes": they "transmit only the required and partially processed data".
5. Nodes are many, cheap, unattended and expected to fail. A deployment may have hundreds or thousands of nodes. Some will die, be eaten, be washed away or run flat, and the network is expected to carry on. Designing for failure is normal here, not an afterthought.
6. Every network is built for one application. The Internet carries everything for everybody. A WSN is designed, often down to its radio schedule, for the one job it was deployed to do. That is why there are dozens of WSN protocols: each suits a different kind of task.

Where the idea came from

Dargie and Poellabauer, the first reference book on MU's list, trace the history, and it is worth knowing in outline.

• Military research first. In 1978 the United States Defense Advanced Research Projects Agency (DARPA) organised a Distributed Sensor Nets Workshop, on networking, signal processing and distributed algorithms for sensors. DARPA then ran a Distributed Sensor Networks (DSN) programme in the early 1980s, followed by the Sensor Information Technology (SensIT) programme.
• Putting a whole node on a chip. The University of California at Los Angeles, with the Rockwell Science Center, proposed Wireless Integrated Network Sensors (WINS); one result, in 1996, was a single CMOS chip carrying sensors, interface circuits, signal processing, a radio and a microcontroller.
• Smaller still. Berkeley's Smart Dust project set out to show that a complete sensor system could be built into a device perhaps the size of a grain of sand. Berkeley's PicoRadio project and MIT's microAMPS project worked on nodes frugal enough to be powered by their surroundings.
• Commercial motes. From the Berkeley work came the motes and TinyOS, and companies selling ready-made nodes.

A real one: Great Duck Island, 2002

The deployment that showed the idea working outside a laboratory was on Great Duck Island, off the coast of Maine in the United States. Biologists wanted to study a seabird, Leach's Storm Petrel, which nests in underground burrows and is likely to abandon a burrow if it is disturbed. People walking about the colony were the problem the study was trying to avoid.

In July 2002 a team from Intel Research, the University of California at Berkeley and the College of the Atlantic deployed thirty-two motes, nine of them inside burrows, measuring temperature, relative humidity, barometric pressure, light and infrared (which shows whether a warm bird is at home). Readings went from the motes to a gateway beside the patch, across a longer radio link to a base station with a database and a wide-area connection, and from there to researchers over the Internet. The design goal was a network that runs for nine months on non-rechargeable batteries, so that nobody needed to visit during the breeding season.

Every element of the figure above is there: the sensor field (the colony), the nodes (the motes), the sink and gateway (the island's base station), the way out (the Internet), and the user (the biologists). And the reason for using a WSN at all is exactly the one this chapter gave: the measurement had to be taken where the phenomenon was, without people.

Worked example: a vineyard near Nashik

A grape grower near Nashik wants to irrigate only when the soil needs it. The farm's engineer, Meera, plans a WSN.

The task. Measure soil moisture and temperature at 40 points across the vineyard every 15 minutes, and tell the pump controller when any zone falls below the moisture threshold.

Step 1: what each node produces. A reading every 15 minutes is

readings per node per day, so the whole network produces 40 × 96 = 3,840 readings a day.

Step 2: how much data that is. Each reading, with the node's identity and a timestamp, fits in 12 bytes, so the day's data is 3,840 × 12 = 46,080 bytes, about 45 kilobytes. That is less than one photograph on a phone. Bandwidth is not the problem, and it never will be here. The problem is doing this for a season without anyone changing batteries.

Step 3: how the data travels. The farthest row of vines is 600 metres from the pump house, where the sink sits with mains power. The node radios reliably reach about 100 metres through the vines, so a reading from the far end needs at least 600 / 100 = 6 hops. Each node therefore forwards its neighbours' readings as well as sending its own, and the nodes nearest the pump house carry the most traffic.

Step 4: what the sink does. It collects the readings, notices that zone 7 has dropped below the threshold, and sends one message to the pump controller and one to the task manager, a small server in Nashik that the grower checks on his phone.

Step 5: what is already visible. The nodes near the sink will run out of energy first, because every other node's data passes through them. Meera will have to deal with that, and the chapters [Single Hop or Multiple Hops: The Energy Argument Worked Out] and [Energy-aware Routing] show how.

That is a whole WSN, in miniature, and it already contains the three ideas the rest of the module is about: the node's energy, the multi-hop network, and the sink as the bridge to the outside world.

Distinctions

What it does not mean

A WSN is not Wi-Fi with a thermometer on it. Wi-Fi is built for tens of megabits per second and a power supply. Sensor node radios are built for a few hundred kilobits per second at most and years on batteries, and they are asleep nearly all the time. The chapter [The Wireless Technologies a Sensor Network Can Use] compares the real options.

"Wireless" does not mean every node talks to the sink. Most nodes cannot reach it. Multi-hop forwarding through neighbours is the normal case, and it is why a node spends as much energy on other nodes' data as on its own.

The sink is not the user. The sink is a machine at the edge of the field. The user is a person or program somewhere else, reached through the task manager.

"No infrastructure" is about the field, not the whole system. The sink, the gateway, the Internet and the task manager are all infrastructure. What a WSN does without is infrastructure among the nodes.

A WSN is not the same thing as the Internet of Things. The Internet of Things is any device on the Internet, from a smart television to a car. A WSN is one particular kind of network of sensing devices, which may or may not be joined to the Internet. The chapter [Sensor Networks in the Internet of Things: 6LoWPAN, RPL and CoAP] shows how the two meet.

Quick revision

• WSN: many small battery-powered sensor nodes, densely deployed inside or near the phenomenon, which sense, process and send data over a multi-hop, infrastructureless radio network to a sink.
• A node has four jobs: sense, process, communicate, survive on its own energy.
• The path: sensor field, nodes, multi-hop route, sink (base station), Internet or satellite, task manager node, user.
• Nodes need not be placed by design, so the network must self-organise.
• Six differences from the Internet: energy is scarce; data-centric; convergecast to one sink; nodes compute and cooperate; nodes are many, cheap and fail; one network per application.
• History (Dargie and Poellabauer): DARPA workshop 1978, DSN programme early 1980s, then SensIT; UCLA WINS; Berkeley Smart Dust and motes.
• First real deployment usually cited: Great Duck Island, July 2002, 32 motes, 9 in burrows, designed to run 9 months on batteries.
• Vineyard: 96 readings a node a day, 3,840 in all, 46,080 bytes: bandwidth is not the problem, energy is.

Test yourself

1. Define a wireless sensor network. A WSN is a network of a large number of low-cost, low-power sensor nodes, each with sensing, processing, radio and power units, densely deployed inside or close to a phenomenon. The nodes self-organise, process data locally and send it over a multi-hop, infrastructureless wireless network to a sink, which passes it through the Internet or a satellite link to a task manager and the user.

2. Draw and explain the elements of the network from an event to the user. The figure: sensor nodes in the sensor field; a node near the event senses it; the reading hops node to node to the sink; the sink sends it over the Internet or satellite to the task manager node; the user reads it there. Each intermediate node acts as a router.

3. Why do WSN nodes use multi-hop forwarding instead of sending straight to the sink? Because their radios are low-power and reach only tens of metres, far less than the size of the field. Sending a long distance directly would also cost far more energy than several short hops in most cases, which is examined in [Single Hop or Multiple Hops: The Energy Argument Worked Out].

4. State four ways a WSN differs from the Internet. Energy rather than bandwidth is the scarce resource; operation is data-centric rather than address-centric; traffic converges on one sink rather than flowing between any pair of hosts; and nodes cooperate and process data inside the network. Also: nodes are many, cheap and expected to fail, and each network is built for one application.

5. In the vineyard, 40 nodes each report every 15 minutes with 12-byte readings. How much data does the network produce a day, and what does that tell you? 96 readings a node a day, 3,840 readings, 46,080 bytes, about 45 kilobytes. It tells you that the design problem is energy and lifetime, not data rate.

6. What did the Great Duck Island deployment show? That a WSN could monitor a phenomenon (a seabird colony) where people's presence would itself disturb it: 32 motes, nine in burrows, deployed in July 2002, sending data through an island gateway to researchers over the Internet, designed to run nine months on batteries.

Element 2: the interconnecting wireless network

The nodes are joined by wireless links. The survey names three media: radio, which almost every real node uses; infrared, which needs no licence and resists electrical interference but needs a line of sight; and optical links, which the Berkeley Smart Dust design used, again needing a clear line of sight. Radio wins because it does not need the two ends to see each other.

How the links are arranged is the network's topology, and three arrangements cover almost every real deployment.

Figure 2.1 The three topologies a sensor network is built in

Star. Every node talks directly, in one hop, to the base station, and nodes never relay for each other. It is the simplest to build and gives the lowest delay, and the nodes can sleep whenever they are not sending. Its limit is range: every node must be within radio reach of the base station, and if the base station fails, everything stops.

Mesh. Nodes talk to their neighbours and relay for each other, so data reaches the base station over several hops, by whichever path is working. It covers a large area with short-range radios and survives the failure of any single node, because another path exists. It costs energy and delay at every hop, and the relays near the base station carry the heaviest load.

Cluster tree, or hierarchical. Nodes are grouped into clusters; each cluster has a cluster head that collects its members' data and forwards it, over one or more hops of cluster heads, to the base station. It combines the two: members do short one-hop transmissions like a star, cluster heads form a backbone like a mesh, and the cluster head can aggregate (combine) its members' readings so that less data travels the long distance.

Element 3: the sink, or base station

The sink is where the data ends up inside the sensor network. The survey draws it at the edge of the sensor field, and the word "sink" (the place data drains into) and "base station" are used for the same element.

What makes it different from an ordinary node:

• More resources. Usually mains power or a large battery, more memory and a faster processor, because it receives everybody's traffic and cannot be allowed to run flat.
• Two roles. It is the destination of the collected data and the origin of the tasks and queries sent into the network. Traffic in a sensor network flows in both directions through the sink: tasks out, data in.
• Not necessarily one. Large deployments use several sinks so that no single one is a bottleneck, and some networks use a mobile sink, a vehicle or a person carrying a receiver, that visits the nodes. The chapter [Network Architecture: Sources, Sinks, Hops and Mobility] sets out those scenarios.

Element 4: the gateway

The gateway is the element that connects the sensor network to a different network: the Internet, a satellite link, a cellular network or a company's own network. It has to speak both sides: the sensor network's low-power radio protocol on one side and Internet protocols on the other, translating between them.

In a small deployment the sink and the gateway are the same box. In a large one they are separated. On Great Duck Island in 2002 each patch of sensors had its own gateway, which passed data across a longer "transit" radio link to a base station that held a database and the wide-area connection to the mainland. That arrangement, gateway then transit network then base station, is a real system's version of the elements in this chapter. The gateway's design problems (how an Internet host can address a node, and how a node's data can be made to look like an Internet service) are the chapter [Gateway Concepts].

Element 5: the task manager and the user

The task manager node, in the survey's figure, is where the network is told what to do and where its results are stored and analysed. It may be a server in an office or a cloud service. Behind it are the computing resources that turn raw readings into something useful: storage, analysis that spots trends and correlations, answering the user's queries, and raising alarms.

The user is the person or program that wants the information: a farmer checking a phone, a control room, a researcher's database. The user almost never deals with individual nodes. The user asks about the phenomenon (the moisture in zone 7, the temperature in cold store 3), and the lower elements decide which nodes answer.

The two directions of flow

Every element takes part in two flows, and a complete answer mentions both.

1. Tasking, outward. The user's request goes to the task manager, through the gateway and the sink, and is spread (disseminated) into the field: which quantity to measure, how often, and what to report.
2. Collection, inward. Readings go from source nodes, hop by hop or through cluster heads, to the sink, and from there through the gateway to the task manager and the user.

The elements as MU's first text book sets them out

MU's printed label, "Basic sensor network architectural elements", is the title of section 1.2.1 of Sohraby, Minoli and Znati, the first text book on MU's list. That section describes the elements not only as boxes on a diagram but as the technologies a sensor network is built from, and an examiner who follows the text book may expect them. There are nine, and every one has a home later in this book.

The text book places all of these in what it calls the C1WSN environment, the large multi-hop kind of sensor network, and lists the conditions that make them hard: a very large sensor population, large streams of data, incomplete or uncertain data, frequent failure of nodes and of links, limited power and processing, a multi-hop topology, no node with global knowledge of the network, and often little administrative support. Those conditions are the challenges of [The Challenges of Wireless Sensor Networks] seen from the architect's side.

Worked example: fire detection in a twelve-storey office building

An office building in Andheri has 12 floors. The facilities manager, Farhan, installs a sensor network for early fire detection.

The elements.

Why the hierarchy matters, in numbers. Each ceiling node reports a "still healthy" status every 10 minutes, which is 6 × 24 = 144 reports a day. The building has 12 × 20 = 240 nodes, so if every report travelled all the way to the base station there would be 240 × 144 = 34,560 reports a day.

With cluster heads, each floor's 20 reports are combined into one summary (floor 7: 20 nodes healthy, highest temperature 31 degrees), so the base station receives 12 × 144 = 1,728 summaries a day. That is 34,560 / 1,728 = 20 times fewer messages crossing the building, and the saving is exactly the number of nodes each cluster head serves.

What happens in a fire. A node on floor 9 detects smoke. It does not wait for its ten-minute slot: it sends an alarm at once to its cluster head, which forwards it immediately to the base station, and the gateway sends it to the monitoring company and the fire brigade. The summarising that saves energy in normal times is bypassed for an alarm, because an alarm must never wait. Deciding which traffic is periodic and which is urgent is part of every sensor network's design, and the chapter [Applications of Wireless Sensor Networks] names the four patterns.

Distinctions

What it does not mean

The sink and the gateway are not always two boxes. They are two functions. In most small networks one device does both, and an answer should say so.

A cluster head is not a different kind of hardware. It can be an ordinary node that has taken on the role for a while. Rotation is the point of several protocols.

The base station failing is not survived by a mesh. A mesh survives the loss of relays. It does not survive the loss of the one place all the data is going, which is why critical networks use more than one sink.

Topology is not the same as geography. Two nodes a metre apart may have no link between them if a steel beam is in the way, and two nodes forty metres apart may have a good one. The topology is the graph of links that actually work.

Quick revision

• Five elements: sensor nodes, wireless links, sink or base station, gateway, task manager and user.
• Node units: sensing, processing, transceiver, power; optional location finding system, power generator, mobilizer.
• Node roles: source, relay, cluster head, actuator.
• Media: radio (used almost everywhere), infrared and optical (both need line of sight).
• Topologies: star (one hop, simple, short range), mesh (many hops, robust, costly relays), cluster tree (members to heads, heads to the base station, aggregation at heads).
• Two flows: tasks out, data in, both through the sink.
• The text book's nine elements (Sohraby and colleagues, section 1.2.1): sensor types and technology; software; standards and the stack; routing and dissemination; organisation and tracking; computation; data management; security; network design issues.
• Building example: 34,560 reports a day without cluster heads, 1,728 with them, 20 times fewer; alarms bypass the summarising.

Test yourself

1. List and explain the basic architectural elements of a WSN. Sensor nodes, which sense, process and relay; the wireless links arranged in a topology; the sink or base station that collects data and issues tasks; the gateway that connects the network to the Internet, satellite or cellular networks and translates protocols; and the task manager with its computing resources, through which the user tasks the network and receives results.

2. Compare the star, mesh and cluster tree topologies. Star: one hop to the base station, simple, low delay, limited range, single point of failure. Mesh: multi-hop relaying, large coverage, robust to node failure, extra energy and delay per hop. Cluster tree: members send one hop to cluster heads, which aggregate and forward over a backbone, combining the star's cheap members with the mesh's reach.

3. What is the difference between the sink and the gateway? The sink is the collection point of the sensor network and the source of tasks sent into it. The gateway connects the sensor network to another network and translates between their protocols. They are two functions that are often, but not always, in the same device.

4. Why does a cluster head need more energy than an ordinary node, and what are the two answers to that? It receives and forwards its whole cluster's data, often over a longer link. Either it is given more energy (mains power, a bigger battery) or the role is rotated among the nodes so the load is shared.

5. In the office building, why does the base station receive twenty times fewer messages with cluster heads? Because each cluster head combines its 20 members' status reports into one summary. 240 nodes at 144 reports a day is 34,560 reports; 12 cluster heads at 144 summaries a day is 1,728, and 34,560 / 1,728 = 20.

Data link layer

Its job is "the multiplexing of data streams, data frame detection, medium access and error control". It gets a frame reliably from one node to its neighbour.

Two parts, both different in a sensor network:

• Medium access control (MAC) decides when a node may use the shared radio channel. In a sensor network it "must be power-aware and able to minimize collision with neighbors' broadcasts", and above all it must let the radio sleep, because a radio left listening wastes most of a node's energy. The chapters from [MAC Protocols for Sensor Networks: The Job and Where the Energy Goes] onwards are this sublayer.
• Error control repairs or detects damaged frames. The survey names the two modes: forward error correction (FEC), which adds redundant bits so the receiver can correct errors itself, and automatic repeat request (ARQ), which resends a frame that did not arrive intact. A sensor node needs simple codes, because decoding a complex one costs energy too.

Network layer

It routes the data from the node that produced it to the sink, across many hops. The survey lists four design principles for this layer in a sensor network:

1. Power efficiency is always an important consideration.
2. Sensor networks are mostly data-centric: what matters is the data, not which node sent it.
3. Data aggregation is useful only when it does not hinder the collaborative effort of the nodes.
4. An ideal sensor network has attribute-based addressing and location awareness: a packet is sent to "the nodes in region A" or to the nodes reading above 70°F, not to node number 145.

The whole of [Routing Strategies in WSNs: A Map] and the chapters after it are this layer.

Transport layer

It "helps to maintain the flow of data if the sensor networks application requires it". Note the condition: many sensor applications tolerate lost readings (another reading comes in a minute), so they need little from this layer.

The survey's key point is where TCP stops. It suggests splitting the connection at the sink: the user talks to the sink over ordinary TCP or UDP through the Internet or satellite, and the sink talks to the nodes with a light UDP-type protocol, "because each sensor node has limited memory" and "acknowledgments are too costly for sensor networks". The chapter [Why a Sensor Network Cannot Simply Run TCP] works out why.

Application layer

It carries the software of the particular application: the monitoring, tracking or alarm program. The survey also proposed three application-layer protocols, which it called open research issues:

• Sensor Management Protocol (SMP), through which administrators manage the network: introducing rules for aggregation, naming and clustering; time synchronisation; turning nodes on and off; querying and reconfiguring the network; and authentication and key distribution.
• Task Assignment and Data Advertisement Protocol (TADAP), for spreading a user's interest (what the user wants to know) into the network, or for nodes to advertise what data they have so users can ask for it.
• Sensor Query and Data Dissemination Protocol (SQDDP), the interface through which an application issues queries and collects replies. Queries are attribute-based ("the locations of the nodes that sense temperature higher than 70°F") or location-based ("temperatures read by the nodes in region A"), never addressed to a named node.

The three planes

The planes are the part of the stack an examiner is really asking about, because they are what the TCP/IP model does not have.

Power management plane

It "manages how a sensor node uses its power". The survey gives two examples, and both are worth writing in an answer:

• A node turns off its receiver after receiving a message from one of its neighbours, so as not to receive the same message again from another neighbour.
• When its power is low, a node broadcasts to its neighbours that it is low in power and cannot take part in routing, and keeps what is left for its own sensing.

Mobility management plane

It "detects and registers the movement of sensor nodes, so a route back to the user is always maintained". Knowing which nodes are its neighbours also lets a node balance its power and its tasks with theirs. In a network where nothing moves this plane does little; on a network of nodes carried by animals, vehicles or water currents, it is essential.

Task management plane

It "balances and schedules the sensing tasks given to a specific region". Not every node in a region needs to sense at the same time, so some nodes take on more of the task than others, depending on their remaining power. Ten nodes watching one field can take turns, and the field is watched just as well at a fraction of the energy.

Worked example: one reading, all the way down

Back to the vineyard of [What a Wireless Sensor Network Is]. Node 23, in zone 7, has a moisture reading of 18 per cent and it is time to report. Follow the reading down its stack and across the planes.

Node 17 receives the frame, passes it up only to its network layer (it is a relay, so the application layer never sees it), and sends it down its own stack towards the next hop. At the sink the reading climbs all five layers and is handed to the gateway.

Distinctions

What it does not mean

The planes are not extra layers. They sit beside the stack, not in it. Drawing them as three more boxes on top of the application layer is the commonest mistake in this answer.

"Transport layer" does not mean TCP. The survey says the opposite: TCP stops at the sink, and inside the field the transport layer is light, UDP-type, or absent.

The stack is a reference model, not an implementation. Real systems merge and split the layers freely. TinyOS has no layers at all in this sense, only components, and IEEE 802.15.4 defines the physical and MAC layers together. The model is for understanding and for answers; [Design Principles: Data Centricity, Location, Activity and Heterogeneity] explains why real designs deliberately cut across layers.

Encryption at the physical layer is the survey's wording, not a rule. Most real sensor networks encrypt at the data link layer (802.15.4 does), which the chapter [Keys and Link Security: Key Predistribution, SPINS and 802.15.4] covers.

Quick revision

• Stack (Akyildiz and colleagues, 2002): physical, data link, network, transport, application, plus power, mobility and task management planes.
• Physical: frequency selection, carrier generation, signal detection, modulation, encryption; power to send over distance d goes as d to the n, n from 2 to 4, near 4 close to the ground.
• Data link: multiplexing, frame detection, MAC (power-aware, few collisions) and error control (FEC and ARQ).
• Network: power efficiency, data-centric, aggregation where it helps, attribute-based addressing and location awareness.
• Transport: only if needed; TCP split at the sink, UDP-type inside.
• Application: SMP, TADAP, SQDDP.
• Power plane: receiver off after a message; announce low power, stop routing. Mobility plane: track movement and neighbours, keep a route to the user. Task plane: schedule and balance sensing so not every node senses at once.

Test yourself

1. Draw and explain the WSN protocol stack. Five layers (physical, data link, network, transport, application) crossed by three planes (power, mobility and task management). Physical: frequency selection, carrier generation, signal detection, modulation, encryption. Data link: multiplexing, frame detection, medium access, error control. Network: data-centric, energy-efficient routing to the sink. Transport: maintains flow where needed. Application: the application software and management protocols. Planes: coordinate energy, movement and the sensing task across all layers.

2. What are the three management planes, and give an example of each. Power management: a node turns off its receiver after receiving a message to avoid duplicates, and announces low power so it is not used for routing. Mobility management: records node movement so a route to the user is always kept and neighbours are known. Task management: schedules sensing in a region so that nodes take turns according to their power.

3. Why does a sensor network's stack need planes at all? Because energy, movement and the sharing of the sensing task concern every layer at once. No single layer can manage them, so they are handled by functions that run across all the layers.

4. What does the survey recommend for the transport layer, and why? Splitting the connection at the sink: TCP or UDP between the user and the sink over the Internet or satellite, and a light UDP-type protocol between the sink and the nodes, because nodes have little memory and acknowledgements cost too much energy.

5. State the four design principles of the network layer. Power efficiency; data-centric operation; aggregation only where it does not hinder collaboration; and attribute-based addressing with location awareness.

6. Name the three application-layer protocols the survey proposes. Sensor Management Protocol (SMP), Task Assignment and Data Advertisement Protocol (TADAP), and Sensor Query and Data Dissemination Protocol (SQDDP).

3. Deployment where people and cables cannot go

Because node positions "need not be engineered or predetermined", nodes can be scattered rather than placed. The survey lists the ways: "dropping from a plane", delivered in an artillery shell, rocket or missile, or placed one by one by a person or a robot. A forest canopy, a glacier, a flooded area, a battlefield or a chemically contaminated site can be monitored without anyone standing in it.

4. Fault tolerance through redundancy

A dense network has more nodes than the task strictly needs, so the loss of a few does not stop it. A dead node's neighbours are still sensing the same area, and a mesh has other paths for the data. A wired sensor that fails leaves that point dark; a manual reading that is missed is simply missing. The design factor behind this, with its reliability formula, is in [The Operating Environment and the Design Factors].

5. Self-organisation, and no infrastructure in the field

The nodes discover their neighbours and build their own routes after they are deployed. There are no routers, towers or access points to install inside the field, only the sink at its edge. This is what makes a WSN possible in places no infrastructure could be built.

6. Scalability and extensibility

The survey names a "redeployment of additional nodes phase": nodes can be added at any time, to replace failed ones or because the task has changed. A network that watches ten fields this year can watch twenty next year by adding nodes, without redesigning the part that already exists.

7. In-network processing

Each node has a processor, so nodes can compute before they send. Instead of forwarding every raw reading, they "use their processing abilities to locally carry out simple computations and transmit only the required and partially processed data". An average of twenty readings sent once instead of twenty readings sent twenty times saves energy and bandwidth everywhere downstream. The principle is taught in [Design Principles: Distributed Organisation and In-network Processing].

8. Continuous, unattended monitoring at low running cost

A network samples every few seconds or minutes, day and night, for months, with nobody present. Against manual observation, it gives far more readings at a fraction of the running cost, and readings arrive as they are taken, so an alarm can be raised at once rather than at the next visit.

9. Low cost per node

A sensor node is built from mass-produced chips: a microcontroller, a radio and a sensor. Because a network uses many of them, the design goal from the start has been to keep each node cheap. The survey goes as far as to say that if a sensor network costs more than deploying traditional sensors, "the sensor network is not cost-justified".

10. Flexibility

The same network can be given a new task (report every minute instead of every hour, or report only when a threshold is crossed) by sending it a new instruction. Nodes can be carried on vehicles or animals, and the sink itself can move. A wired system is fixed to where its cables run.

Worked example: two sums behind the advantages

The sensing distance

A forest department wants to detect chainsaws. It can mount one sensitive microphone on a watchtower 100 metres from a stand of trees, or scatter cheap microphone nodes so that one sits 10 metres from each tree.

By the inverse-square law, the sound intensity at the tower is less than at the scattered node by the square of the ratio of the distances:

The node receives 100 times the sound intensity the tower does. Expressed in decibels, a ratio of 100 in intensity is 20 decibels (a factor of 10 is 10 decibels, and there are two of them). A tower microphone would need to be 100 times more sensitive to do as well, and it would still hear only one direction. This is the advantage of being "very close to" the phenomenon, in one number.

The cabling

A cold-chain company has 200 storage rooms spread across a warehouse complex and wants temperature readings every 5 minutes. The prices below are assumptions made for this exercise, not market prices.

Wired option. Assume the average cable run from a room to the control panel is 60 metres, and cable plus installation costs Rs 250 a metre. The cabling alone costs

rupees, before a single sensor is bought, and every future room adds another cable run.

Wireless option. Assume a node costs Rs 3,000 and its batteries Rs 100 a year. The nodes cost 200 × 3,000 = 6,00,000 rupees once, and batteries 200 × 100 = 20,000 rupees a year.

Manual option. A person visiting every room is cheap to start, but at one visit a day the company gets one reading per room per day instead of 288 (which is 24 × 60 / 5), and a compressor failure at night is discovered in the morning.

On these assumptions the wireless network costs a fifth of the cabling alone, gives the full reading rate, and can be extended one room at a time. Change the assumptions and the numbers change, but the shape of the answer is the one this chapter describes: the wireless network wins where cabling is long, awkward or impossible, and where readings are needed often.

Distinctions

What it does not mean

These advantages are not free. Every one of them is paid for in energy, and the next chapter, [The Challenges of Wireless Sensor Networks], is the bill. An answer that lists advantages and never mentions the battery has told half the story.

"Low cost" is per node, not per network. A thousand cheap nodes are not cheap. The claim is that the whole network costs less than the alternative for the same coverage.

A WSN is not always the right answer. A factory that already has power and data cabling at every machine gains little by going wireless and loses the reliability of a wire. The advantages are strongest where cabling is long, awkward or impossible.

Fault tolerance has a limit. Redundant nodes cover for each other; nothing covers for a failed sink unless there is a second one.

Quick revision

• Advantages against cabling, manual observation and one distant instrument.
• No cabling: quick, cheap, works in occupied buildings, easy to move.
• Close to the phenomenon: stronger signal (inverse square: 10 m against 100 m is 100 times, 20 decibels) and finer spatial detail.
• Inaccessible places: random deployment, dropped from a plane.
• Fault tolerance by redundancy; self-organisation, no infrastructure in the field; scalability by redeployment.
• In-network processing: send partially processed data, not raw readings.
• Continuous, unattended, cheap to run; low cost per node; flexible and retaskable.
• Silo example (assumed prices): cabling Rs 30,00,000 against nodes Rs 6,00,000 plus Rs 20,000 a year; 288 readings a day against one.

Test yourself

1. State five advantages of wireless sensor networks. Any five of: no cabling; sensing close to the phenomenon; deployment in inaccessible places; fault tolerance through redundancy; self-organisation with no infrastructure in the field; scalability by adding nodes; in-network processing; continuous unattended monitoring; low cost per node; flexibility and retasking.

2. Why does being close to the phenomenon improve sensing? Many signals weaken with distance, sound in open air with the square of the distance, so a nearby cheap sensor receives a stronger signal than a distant expensive one; and many nearby sensors give spatial detail that one distant instrument averages away.

3. A sensor 10 metres from a sound source is compared with one at 100 metres. By what factor does the intensity differ? By (100 / 10)² = 100, which is 20 decibels, in favour of the nearer sensor.

4. How does a WSN achieve fault tolerance? By redundancy: it is deployed densely, so a failed node's area is still sensed by its neighbours, and in a mesh the data finds another path. Only the loss of the sink is not covered, unless there are several sinks.

5. When would a wired sensor system be the better choice? Where power and data cabling already reach every sensing point, as at the machines of a factory, so the wireless network's saving on cabling disappears and the reliability of a wire is worth more.

Worked: a node that never sleeps. Suppose the node runs on a battery pack rated 2,500 mAh (an assumption for the exercise; the chapter [How Long a Node Lasts: The Energy Budget Worked Out] uses real battery figures). A radio left listening draws 18.8 mA, so the battery lasts 2,500 / 18.8, about 133 hours, which is about five and a half days. A network designed to last a season is dead in a week. Keeping the radio off for most of the time is not an optimisation; it is the only way the network can exist.

2. Limited processing power and memory

The MSP430F1611 has 10 KB of RAM and 48 KB of flash for program code. A phone has millions of times more. A protocol that keeps a large table, a long queue or a big buffer simply does not fit, and an operating system designed for a desktop is out of the question. The first TinyOS, by comparison, fitted in 178 bytes of memory. Everything that runs on a node must be small and simple, which is why [Why a Sensor Node Needs an Operating System] exists.

3. Unreliable, time-varying wireless links

A radio link is not a wire. Its quality changes with the weather, with people and vehicles moving about, and with other radios: the 2.4 GHz band that many sensor nodes use is shared with Wi-Fi, Bluetooth and microwave ovens. Links can be asymmetric (A hears B but B does not hear A), and between the range where every packet arrives and the range where none does lies a wide band where some arrive and some do not, which the chapter [TOSSIM: Simulating Motes, Radio Gain and Packet Loss] explains. A protocol that assumes a link either works or does not will fail in the field.

4. Unattended operation and self-configuration

Nobody stands beside each node to give it an address, tell it who its neighbours are or set up its routes. After deployment the nodes must discover their neighbours, build routes, and repair them when something changes, all by themselves. A network of a thousand nodes cannot be configured by hand even if someone were there.

5. Large scale and high density

The survey expects deployments of hundreds or thousands of nodes, sometimes more, with densities as high as 20 nodes in a cubic metre. At that scale a node cannot know the whole network. Every algorithm must be local: a node decides from what its neighbours tell it, never from a global picture. And with so many nodes in one radio range, their transmissions collide unless the MAC protocol keeps them apart.

6. A dynamic topology

The survey divides the topology's life into three phases: deployment, post-deployment (when the topology changes because nodes move, links are jammed or blocked, batteries run down, or nodes malfunction) and redeployment of additional nodes. On top of that, nodes that sleep to save energy are, from their neighbours' point of view, temporarily absent. So the set of working links changes all the time, and routes must adapt.

7. Application-specific quality of service

On the Internet, quality of service means throughput and delay. A sensor network's user wants something else: that every fire is detected, that the location of a vehicle is estimated within five metres, that the average temperature is right to half a degree. These are measures of the information, not of the bits, and they differ from one application to another. Designing for them is the subject of [Optimization Goals: Quality of Service, Energy Efficiency and Lifetime].

8. Being data-centric, and processing in the network

The user asks about the phenomenon, not about node number 145, and nodes may not even have globally unique identities. The network has to route, name and store data by what it is and where it came from, and combine it on the way. That is a different way of building a network from the one students learn first, and it is a challenge because the familiar tools (IP addresses, end-to-end connections) do not apply.

9. Security

Nodes lie in the open, where an attacker can pick one up, read its memory and reprogram it. The radio is a broadcast medium that anyone can hear and anyone can transmit on. And the node cannot afford the cryptography a server uses. Keeping data secret and authentic, and keeping routing honest, is hard, which is why the book gives it four chapters starting from [Security in Ad Hoc and Sensor Networks: Goals, Constraints and Attacks].

10. Time synchronisation and localisation

A reading is useless without when and where. Each node has its own clock, which drifts, and giving every node a satellite receiver to learn its position costs too much money and energy. So nodes must agree on the time and work out their positions among themselves, which is [Time Synchronisation and Localisation].

11. Programming, deployment and maintenance

A bug found after deployment must be fixed on a thousand nodes scattered across a forest, without collecting them. The network has to be reprogrammable over its own radio, tested before it goes out, and monitored while it runs. Tools for programming a whole network, rather than one node, are part of the answer, and [WSN Middleware: Why It Is Needed, and Its Architecture] describes them.

12. Cost

Because a network needs many nodes, each must be cheap. The survey, writing in 2002, went as far as to say a node should cost "much less than US$1" for a sensor network to be feasible, a target far below what real nodes cost then or now. Cheap hardware means small batteries, simple radios and little memory, which feeds straight back into challenges 1 to 3.

The same challenges, as MU's second text book organises them

Karl and Willig, the second text book on MU's list, split the challenges into two lists, and an answer that uses their headings is well organised.

The characteristic requirements, the properties most applications demand:

1. Type of service. A WSN is not there to move bits but to give meaningful information about a task; they quote a Berkeley engineer's line, "People want answers, not numbers". Interactions are scoped to regions and time intervals.
2. Quality of service. Bounded delay and minimum bandwidth often do not matter; what matters is the amount and quality of information extracted, such as reliable detection of events or the accuracy of a temperature map. They add that the packet delivery ratio "is an insufficient metric".
3. Fault tolerance, achieved by redundant deployment: more nodes than would be needed if every node worked.
4. Lifetime, a "very important figure of merit", whose precise definition depends on the application ([Optimization Goals: Quality of Service, Energy Efficiency and Lifetime] gives the definitions).
5. Scalability to large numbers of nodes.
6. A wide range of densities, varying between applications and within one network over time and space.
7. Programmability: nodes must be reprogrammable during operation as tasks change.
8. Maintainability: the network must monitor its own health and adapt, for example by giving lower quality when energy runs short.

The required mechanisms, the techniques that meet those requirements:

1. Multi-hop wireless communication, because direct communication over long distances needs prohibitively high power.
2. Energy-efficient operation, including avoiding "hotspots" where energy consumption concentrates.
3. Auto-configuration, including nodes working out their own positions ("self-location"), tolerating failed nodes and integrating new ones.
4. Collaboration and in-network processing, such as combining readings as they travel to find the highest or average temperature.
5. Data-centric operation, asking for values rather than for particular nodes.
6. Locality: each node keeps state only about its direct neighbours, so the network can scale.
7. Exploiting trade-offs, such as energy against accuracy, or the lifetime of the whole network against the lifetime of individual nodes.

The twelve challenges above and these two lists describe the same ground. The twelve are organised by problem; Karl and Willig organise by what the application needs and what the network must do about it.

How the challenges pull against each other

The challenges are not independent, and the hard part of design is that solving one makes another worse.

• Energy against delay. Sleeping saves energy, but a packet that arrives for a sleeping node must wait. Every duty-cycling MAC protocol trades one for the other, and [S-MAC: Latency, Adaptive Listening and the Energy Saved] measures the trade.
• Energy against reliability. Acknowledging and retransmitting packets makes delivery reliable, and costs energy each time.
• Cost against lifetime. A bigger battery lasts longer and costs more.
• Density against collisions. More nodes give better coverage and more redundancy, and more radios contend for the same channel.
• Security against energy. Every byte of authentication code added to a packet is transmitted, and transmission is the most expensive thing a node does.

The challenges, as numbers

Every challenge listed above is a number underneath, and the numbers are worth seeing together, because they are not independent: each one is bought with another.

# Each challenge, given the one number that makes it a challenge.
import math

V, CAPACITY_MAH = 3.0, 2500.0          # two AA alkaline cells, a round figure
JOULES = CAPACITY_MAH / 1000 * 3600 * V
I_RX, I_TX, I_SLEEP = 18.8e-3, 17.4e-3, 20e-6
RATE = 250e3
DAY = 24 * 3600.0

print("Every challenge in this chapter is a number. Here they are.")
print()
print("ENERGY. Two AA cells hold about %.0f joules." % JOULES)
for name, cur in (("listening, radio always on", I_RX),
                  ("listening one second in ten", I_RX * 0.1 + I_SLEEP * 0.9),
                  ("listening one second in a hundred", I_RX * 0.01 + I_SLEEP * 0.99),
                  ("listening one second in a thousand", I_RX * 0.001 + I_SLEEP * 0.999)):
    life = JOULES / (cur * V)
    print("  %-36s %8.1f days" % (name, life / DAY))
print("  a node that is simply left switched on lasts under a week; the same node at a")
print("  thousandth of a duty cycle runs for over seven years, which is about as long as")
print("  the cell will sit on a shelf anyway. The challenge")
print("  is not the battery. It is the radio being on.")

print()
print("BANDWIDTH. One channel of %.0f kbit/s, shared." % (RATE / 1000))
for n in (10, 100, 1000):
    share = RATE / n
    print("  %4d nodes sharing it: %8.0f bit/s each before any collision at all"
          % (n, share))
print("  and that is the ideal. Contention takes a large part of it back, which is why")
print("  the MAC chapters spend so long on collisions.")

print()
print("SCALE. A flood reaches everyone by making everyone shout.")
for n in (10, 100, 1000):
    print("  %4d nodes: one flood is %4d transmissions, and a query answered by all of"
          % (n, n))
    print("       them is another %4d coming back" % n)
print("  the traffic grows with the number of nodes, and so does the chance two of them")
print("  speak at once. Nothing about a protocol that works for ten is evidence it works")
print("  for a thousand.")

print()
print("LATENCY. Sleeping costs time as surely as listening costs energy.")
for duty, frame_ms in ((0.1, 100), (0.01, 1000), (0.001, 10000)):
    wait = frame_ms / 2.0
    for h in (5, 10):
        print("  at %5.1f%% duty with a %4d ms cycle, a %2d hop path waits about %6.0f ms"
              % (duty * 100, frame_ms, h, h * wait))
print("  a network that sleeps to survive is a network that answers slowly, and the two")
print("  cannot both be optimised. That is the trade every MAC in this book is making.")

print()
print("COST AND UNATTENDED OPERATION.")
for per_node in (300, 1000, 3000):
    for n in (100, 1000):
        print("  %4d nodes at Rs %4d each: Rs %9d of hardware" % (n, per_node, n * per_node))
print("  and one visit by one person to replace one battery, at a day's wage and a day's")
print("  travel, can cost more than the node. That is why the design target is a node")
print("  that is never visited, and why every other challenge reduces to energy.")

Distinctions: each challenge, and where the book answers it

What it does not mean

Energy being limited does not mean the answer is a bigger battery. A bigger battery makes the node bigger and dearer and only postpones the problem by a constant factor. The real answer is to change what the node does, above all to keep its radio off.

The processor is not the energy problem. It is natural to assume that computing is what uses the power. On these chips the radio listening uses about 57 times as much as the processor running.

An unreliable link is not a broken radio. Links in the band between perfect and dead are normal in every real deployment, and protocols must be designed for them, not tested only where every packet arrives.

Challenges are not the same as design factors, but they overlap. The survey's design factors (fault tolerance, scalability, cost, environment, topology, hardware, medium and power) are the properties a designer must take into account; the challenges are the problems those factors create. Both are asked, and [The Operating Environment and the Design Factors] teaches the factors with their formulas.

Quick revision

• Twelve challenges: energy; processing and memory; unreliable links; unattended self-configuration; scale and density; dynamic topology; application QoS; data-centric operation; security; time and position; programming and maintenance; cost.
• CC2420: receive 18.8 mA, transmit 17.4 mA, idle 0.426 mA, power down 0.02 mA. MSP430F1611: active 0.33 mA at 1 MHz, standby 0.0011 mA; 10 KB RAM, 48 KB flash.
• Listening costs as much as sending; the radio costs about 57 times the processor; sleeping is almost free.
• A 2,500 mAh battery (assumed) with the radio always listening: 2,500 / 18.8, about 133 hours, five and a half days.
• Densities up to 20 nodes per cubic metre; hundreds to thousands of nodes; the first TinyOS in 178 bytes.
• Karl and Willig: requirements type of service, QoS, fault tolerance, lifetime, scalability, range of densities, programmability, maintainability; mechanisms multi-hop, energy efficiency, auto-configuration, collaboration and in-network processing, data-centric, locality, exploiting trade-offs.
• The challenges pull against each other: energy against delay, reliability, security; density against collisions; cost against lifetime.

Test yourself

1. List eight challenges of wireless sensor networks. Any eight of: limited, irreplaceable energy; limited processing and memory; unreliable, time-varying links; unattended operation and self-configuration; large scale and high density; dynamic topology; application-specific QoS; data-centric operation; security; time synchronisation and localisation; programming and maintenance; cost.

2. Using the CC2420 and MSP430F1611 figures, explain why the radio is the main energy problem. The radio draws 18.8 mA receiving and 17.4 mA transmitting, while the processor draws 0.33 mA active at 1 MHz. Listening therefore costs about 57 times as much as computing, so a node should compute to reduce what it sends and should keep its radio off whenever it can.

3. What is idle listening, and why does it matter? Keeping the receiver on while waiting for a packet that may never come. On the CC2420 it draws the full 18.8 mA of receiving, as much as transmitting, so a node that idles with its radio on wastes energy as fast as one that is talking.

4. A node's radio listens continuously on a 2,500 mAh battery. Roughly how long does it last? 2,500 / 18.8, about 133 hours, or about five and a half days.

5. Why must sensor network algorithms be local? Because with hundreds or thousands of nodes, densities up to 20 a cubic metre and a constantly changing topology, no node can know the whole network. Each node must decide from what its neighbours tell it.

6. Give two pairs of challenges that pull against each other. Energy against delay (sleeping saves energy but delays packets for sleeping nodes), and density against collisions (more nodes improve coverage but contend for the channel). Others: energy against reliability, security against energy, cost against lifetime.

Agriculture

Soil moisture, temperature and humidity nodes let a farmer irrigate or spray only where and when it is needed, which is called precision agriculture. The vineyard in [What a Wireless Sensor Network Is] is this application: periodic readings, low data volume, a whole season on batteries. Cold stores and greenhouses use the same idea. MU's own description of this paper names smart agriculture first among its applications.

Healthcare

Small sensors worn on the body measure heart rate, blood oxygen, temperature or movement and report to a phone or a bedside unit; this is a body area network. The survey's introduction already names it: nodes "deployed to monitor patients and assist disabled patients". A hospital ward can monitor many patients without wires tying them to machines, and an elderly person living alone can be watched for a fall. The demands are unusual for a sensor network: reports must be reliable and quick, and the data is private.

Industry

Vibration and temperature nodes on motors, pumps and compressors detect wear before a machine fails, which is predictive maintenance. Nodes on pipelines, tanks and valves report pressures and levels for process control. The attraction is the one [The Advantages of Wireless Sensor Networks] priced: a plant already built cannot easily be rewired. MU's description calls this "industrial IoT". The demands are reliability and, for control, bounded delay.

Buildings and homes

Temperature, occupancy and light nodes let a building run its air conditioning and lighting only where people are. Smoke, gas and water-leak nodes raise alarms; the office building in [The Architectural Elements of a Sensor Network] is this application. In homes the same nodes drive "smart home" automation.

Structural health monitoring

Accelerometers and strain sensors on bridges, towers, dams and tall buildings measure how the structure vibrates and whether that is changing over the years, and they record the response to an earthquake or a heavy load. The data rates are high during an event and low otherwise, like the volcano.

Military

The survey lists the military uses first: rapid deployment, self-organisation and fault tolerance make sensor networks suited to "command, control, communications, computing, intelligence, surveillance, reconnaissance, and targeting systems". In practice that means detecting and tracking vehicles or people crossing a boundary, and monitoring an area for chemical or biological agents. Nodes may be dropped from the air, and must resist capture and jamming.

Disaster management

After an earthquake, flood or industrial accident, nodes scattered in the affected area can report temperatures, toxic gases or the presence of survivors where rescuers cannot yet go. The survey names "monitoring disaster areas" among its commercial applications. The demand is rapid deployment with no infrastructure at all, because whatever infrastructure existed may be destroyed.

Logistics and inventory

Nodes on containers, pallets or shelves report location, temperature and shock, so that a consignment of vaccines, for example, can be proven to have stayed cold all the way. The survey names "managing inventory" and "monitoring product quality".

Smart cities and smart grids

Street-level nodes report parking spaces, air quality, noise and street-light faults. On the electricity network, sensor nodes and smart meters report consumption and faults so that supply can follow demand. MU's description names both.

The four kinds of sensing task

Karl and Willig, the second text book on MU's list, sort all these applications into four patterns of interaction between the network and the phenomenon. Every application in the sectors above is one of them or a mixture.

Figure 6.1 The four kinds of sensing task every application is built from

1. Event detection. The network reports only when something happens: a fire, an intruder, a gas leak, a machine vibrating abnormally. Most of the time nothing is sent. When an event happens, the report must arrive quickly and reliably, and the network may need to classify the event (a car or a lorry? a small tremor or an eruption?), often by nodes combining their readings.

2. Periodic measurement. Every node reports its reading at regular intervals: soil moisture every 15 minutes, a burrow's temperature every 5 minutes. The traffic is steady and predictable, individual readings matter little, and the network can plan its sleeping around the schedule. The demand is lifetime.

3. Function approximation and edge detection. The user wants a picture of how a quantity varies across space, the temperature map of a forest or the moisture across a field. The nodes sample the underlying function at points, and the sink reconstructs it. A special case is finding the edge of a region where the quantity crosses a threshold, such as the front of a fire or the boundary of a contaminated area. Only nodes near the edge need to report.

4. Tracking. The network follows a moving target: a vehicle, an animal, a person. Nodes near the target detect it, estimate its position between them, and hand the task on to the nodes ahead of it as it moves. The demands are timeliness and accuracy of position.

Worked example: classifying ten applications

The table classifies ten applications by their sensing task and by what each demands of the network, which is the analysis an examiner is looking for.

Two things follow from the table, and both are worth writing in an answer.

The same hardware can serve very different applications, but not with the same protocols. The seabird network used Mica motes and the volcano network TMote Sky nodes, both small battery-powered motes of the same general kind. One slept almost all the time and trickled readings out; the other sampled a hundred times a second and moved bursts of data over multiple hops.

Most real applications mix tasks. A fire network does event detection to raise the alarm and then edge detection to map the fire front. A patient monitor sends periodic readings and immediate alarms. The protocol has to carry both kinds of traffic, which is why [Optimization Goals: Quality of Service, Energy Efficiency and Lifetime] measures quality by the task, not by throughput.

Distinctions

What it does not mean

A list of sectors is not an application answer. Military, health, environment earns little. Say what the network senses, which task it performs, and what that demands.

Environmental monitoring is not one kind of application. Seabird burrows and an erupting volcano are both environmental and are opposite in every demand that matters.

Healthcare body sensors are not quite a sensor network in the classic sense. They are few, close together and usually one hop from a phone. They share the energy and radio problems but not the multi-hop scale.

Tracking is not the same as event detection. Detecting that a vehicle has entered is an event; following where it goes is tracking, and it needs the network to hand the target from node to node.

Quick revision

• Sectors: environment, agriculture, healthcare, industry, buildings and homes, structural health, military, disaster management, logistics, smart cities and grids.
• Two real deployments: Great Duck Island, July 2002 (32 motes, periodic, lifetime) and Reventador volcano, August 2005 (16 nodes, 19 days, 100 samples a second, 229 events, event-triggered bulk data).
• Four tasks (Karl and Willig): event detection, periodic measurement, function approximation and edge detection, tracking.
• The application decides the data rate, the delay allowed and the main demand; most real applications mix tasks.

Test yourself

1. Explain five applications of wireless sensor networks. Any five, each with what is sensed and what is demanded: habitat monitoring (periodic, lifetime); volcano monitoring (event-triggered high-rate data, fidelity); precision agriculture (periodic soil readings, a season on batteries); patient monitoring (periodic plus alarms, reliability and privacy); industrial predictive maintenance (vibration, accuracy); building safety (event alarms, no misses); military surveillance and tracking; disaster management; logistics; smart cities and grids.

2. Name and explain the four kinds of sensing task. Event detection: report only when something happens, quickly and reliably. Periodic measurement: every node reports on a schedule; lifetime matters most. Function approximation and edge detection: reconstruct how a quantity varies over space, or find the boundary where it crosses a threshold. Tracking: follow a moving target, handing it from node to node.

3. Compare the Great Duck Island and Reventador deployments. Both were environmental. Great Duck Island (2002, 32 motes) sent slow periodic readings and was designed for months of lifetime. Reventador (2005, 16 nodes, 19 days) sampled at 100 Hz, used event detection to decide when to collect, and cared most about capturing every sample of an event accurately.

4. Which sensing task does a forest fire network perform? Event detection to raise the alarm, then edge detection to map where the fire front is.

5. Why do sensor network protocols differ from one application to another? Because the application decides the data rate, the delay that is acceptable, the loss that is tolerable and the lifetime required, and a protocol that suits one set of demands, such as sleeping almost always, fails another, such as moving bursts of high-rate data.

Its energy. Most simple sensors draw little, but some draw a lot: a gas sensor has to heat its element, and an active sensor such as an ultrasonic range finder transmits a pulse. The rule the software follows is the same as for the radio: power the sensor only when a reading is due.

Unit 2: the processing unit

What it is. A microcontroller (MCU) is a small processor with its memory and its input and output devices on the same chip: timers, an ADC, serial interfaces (UART, SPI and I2C, the three ways chips on a board talk to each other). It runs the node's operating system and application, decides when to sense, what to send and when to sleep, and runs the network protocols.

Why a microcontroller and not something else. A desktop processor is far too hungry. A digital signal processor is faster at arithmetic on signals but draws more. An FPGA (a reconfigurable chip) or an ASIC (a chip designed for one job) can be very efficient but is costly to design and hard to change. The microcontroller wins for most nodes because it is cheap, reprogrammable and above all sleeps deeply and wakes fast.

A real one. The Telos mote, designed at Berkeley and described in 2005, chose the Texas Instruments MSP430 after comparing parts from several makers, because it had the lowest power in both sleep and active modes. The MSP430F1611 on it is a 16-bit processor with a 125-nanosecond instruction cycle, 10 kB of RAM and 48 kB of flash. It moves from standby, at about 1 microampere, to full speed in no more than 6 microseconds.

Why wake-up time matters. A node spends almost all its time asleep and wakes for a few milliseconds at a time. If waking takes as long as the work, half the energy goes on waking. The Telos authors put the whole design principle in one sentence: the node "is asleep for the majority of the time, wakes up quickly on an event, processes, and returns to sleep".

Why the lowest working voltage matters too. Two AA cells in series start at about 3 volts and are exhausted at about 1.8 volts. The MSP430 runs down to 1.8 volts, so it uses the whole battery. The ATmega128 used on the earlier Mica2 motes stops at 2.7 volts, which the Telos paper says leaves "almost 50% of the AA batteries unused".

Unit 3: the transceiver

What it is. The radio: it modulates bits onto a carrier to send them and demodulates received signals back into bits (both explained in [Modulation: ASK, FSK and PSK]). It has an antenna, often printed on the circuit board itself, as on Telos.

A real one. The Texas Instruments (originally Chipcon) CC2420 is an IEEE 802.15.4 radio for the 2.4 GHz band, sending 250 kbps and receiving signals as weak as -95 dBm (the unit is explained in [Radio Technology in WSNs: The Sensor Radio and Its Link Budget]). It has 128-byte buffers for one received and one outgoing frame, so the microcontroller can hand over a whole packet and go back to sleep while the radio sends it.

Its energy. The transceiver is the most expensive unit on the board: on the CC2420 it draws 18.8 mA receiving and 17.4 mA transmitting, against a third of a milliampere for the processor. Its states and the cost of moving between them are the subject of the next chapter.

Unit 4: memory

What it is. Three kinds, each for a different job.

• RAM, inside the microcontroller: fast, lost when power is lost, and tiny (10 kB on the MSP430F1611). It holds the running program's variables, the packet being built, the routing table.
• Program flash, inside the microcontroller: keeps its contents without power, holds the program (48 kB on the MSP430F1611).
• External flash, a separate chip for logged readings, and on some motes for a new program image received over the air. Telos carries an ST M25P80, which holds 1,024 kB. The volcano network in [Applications of Wireless Sensor Networks] stored its samples in flash in 256-byte blocks.

Its energy. Reading flash is cheap; writing and erasing it costs far more, and flash wears out after many erase cycles. So a node logs data in large blocks rather than byte by byte.

Unit 5: the power unit

What it is. The battery (almost always), a voltage regulator or converter that gives the other units the steady voltage they need, and sometimes a power generator that scavenges energy from the surroundings, such as a small solar cell. The survey calls the power unit "one of the most important components of a sensor node".

Its role. Everything else is designed around it. A node's lifetime is its battery's energy divided by its average power, so the power unit sets the lifetime and the other four units' job is to keep the average power low. Batteries, their real capacity and energy scavenging are in the next chapter, and the lifetime arithmetic in [How Long a Node Lasts: The Energy Budget Worked Out].

The optional units

The survey names three units that some applications add.

• Location finding system, for example a GPS receiver, because many routing schemes and most sensing tasks need to know where a reading came from. It is expensive in money and energy, so most nodes estimate their position from their neighbours instead, as [Time Synchronisation and Localisation] explains.
• Power generator, a solar cell or other scavenger.
• Mobilizer, which moves the node, for example a robot base. Rare, and used when the network must reposition itself to carry out its task.

Worked example: the block diagram of the vineyard node

Meera's vineyard node, from [What a Wireless Sensor Network Is], measures soil moisture and temperature every 15 minutes. Here is its block diagram as a table of the five units, and what each is doing in each part of its 15-minute cycle.

The analysis the practical asks for, unit by unit.

• Sensing unit: its energy is small because it is on for milliseconds; a heated gas sensor would change that completely.
• Microcontroller: its active current matters less than its standby current and its wake-up time, because it is in standby for more than 99 per cent of the time.
• Transceiver: the largest current by far; everything the protocols do is aimed at shortening the time it is on.
• Memory: the reason the node can log data it could not send at once, for example while a neighbour is down.
• Power unit: sets the lifetime; it must work down to the lowest voltage the other units accept, so no energy is stranded in the battery.

The fraction of time awake. Awake for 60 milliseconds in every 15 minutes, which is 900,000 milliseconds, the node is awake for 60 / 900,000 of the time, about 0.0067 per cent. That fraction is called the duty cycle, and it is what makes a season on two AA cells possible.

A short history of real nodes

The Telos paper traces the Berkeley family, and the direction of travel is the lesson.

Memory grew, radios got faster and moved to the standard 802.15.4, and the sleep current and wake-up time fell. The Mica2 took up to 4 milliseconds to wake; Telos takes 6 microseconds. MicaZ, the Mica family's successor, kept the Mica2 design but replaced its radio with the CC2420. Many later designs put the microcontroller and the radio on one piece of silicon, but the five units are still there, only closer together.

Distinctions

What it does not mean

Four units or five is not a contradiction. The survey's four put memory inside the processing unit; the practical's five list it separately. Say which you are using and name every part either way.

The sensor is not the whole sensing unit. The ADC, and usually a conditioning circuit, belong to it too.

The fastest processor is not the best one. A node's processor is judged by how deeply it sleeps and how quickly it wakes, because it is asleep nearly all the time.

A location finding system is not standard equipment. It is optional, and most networks avoid GPS on every node because of its cost and energy.

Quick revision

• Five units: sensing unit (sensor, conditioning, ADC), microcontroller, transceiver, memory, power unit; optional location finding system, power generator, mobilizer. The survey counts four (memory inside processing).
• 12-bit ADC: 4,096 steps; over 2.5 V, about 0.61 mV a step.
• MSP430F1611: 16-bit, 10 kB RAM, 48 kB flash, standby about 1 microampere, wake-up within 6 microseconds, runs down to 1.8 V.
• CC2420: 802.15.4, 2.4 GHz, 250 kbps, -95 dBm, 128-byte buffers; 18.8 mA receive, 17.4 mA transmit.
• Design principle (Telos): asleep most of the time, wake quickly, process, sleep again.
• The vineyard node's duty cycle: 60 ms in 15 minutes, about 0.0067 per cent.

Test yourself

1. Draw the block diagram of a sensor node and explain each unit. The figure: the sensing unit (sensor and ADC) converts the physical quantity to a number; the microcontroller processes it and controls the node; the transceiver sends and receives packets; memory holds the program, variables and logged data; the power unit supplies all of them. Optional units: location finding system, power generator, mobilizer.

2. Why is a microcontroller used as the processing unit? It is cheap, reprogrammable, has memory and interfaces on one chip, and above all sleeps at microamperes and wakes within microseconds, which matters more than speed for a node that is asleep nearly all the time.

3. A node's 12-bit ADC measures 0 to 2.5 volts. What is the size of one step? 2.5 / 4,096 volts, about 0.61 millivolts.

4. Why did the Telos designers care that the MSP430 runs down to 1.8 volts? Because two AA cells in series are exhausted at about 1.8 volts. A processor that stops at 2.7 volts, like the ATmega128, leaves almost half of the batteries' energy unused.

5. Which unit uses the most energy, and what follows for the design? The transceiver: on the CC2420 about 17 to 19 mA when on, against about 0.33 mA for the processor. So the node must keep the radio off as much as possible and compute more in order to send less.

When sleeping pays: the break-even rule

Going to sleep saves energy only if the energy saved while asleep is more than the energy spent waking up. So there is a break-even time: sleep for longer than that and you save; sleep for less and you lose.

Take the worst case for the CC2420. Suppose that waking cost as much as listening, 18.8 mA, for the whole 1.0 ms of the crystal start-up. The energy spent waking is then what 1.0 ms of listening costs, and staying asleep instead of listening saves 18.8 mA less 0.02 mA, almost all of it. So even in this pessimistic case any sleep longer than about 1 ms pays for itself. Because a real start-up draws less than full receive current, the true break-even time is shorter still.

The rule in general: break-even time = energy to wake up / (power while awake - power while asleep), where "awake" means whatever the radio would otherwise be doing, listening in this example. A radio with a slow, costly start-up has a long break-even time; one with a fast start-up can sleep between every packet. This is why the Telos designers cared so much about wake-up times, and why [Duty Cycling: Preamble Sampling, B-MAC and X-MAC] works at all.

Transmit power is not transmit current

The CC2420 lets the software choose its output power, and the datasheet gives the current at each setting.

Going from 0 dBm to -25 dBm cuts the radiated power by a factor of 10 to the power 2.5, about 316 (each 10 dB is a factor of 10). But the current only falls from 17.4 mA to 8.5 mA, about half. Most of a low-power radio's current goes into its electronics (the oscillator, synthesiser, mixer and baseband), not into the power actually radiated. So turning the transmit power down saves less than a student would guess, and receiving, which has no power amplifier at all, costs more than transmitting. Both facts shape the argument in [Single Hop or Multiple Hops: The Energy Argument Worked Out].

Energy per bit: why a faster radio can be cheaper

What matters is not the current but the energy to move one bit, which is power divided by data rate. The Telos paper's table gives both for two generations of mote. In milliwatts divided by kilobits per second, which comes out in microjoules per bit:

• Mica2, CC1000 radio, transmitting at 42 mW and 38.4 kbps: 42 / 38.4 = 1.09375 microjoules per bit.
• Telos, CC2420 radio, transmitting at 35 mW and 250 kbps: 35 / 250 = 0.14 microjoules per bit.

So the newer radio sends a bit for 1.09375 / 0.14 = 7.8125 times less energy, although it draws almost the same power, because it finishes about six and a half times sooner and then sleeps. The Telos authors put it simply: "The higher data rate allows shorter active periods further reducing energy consumption."

Sensors and actuators

Sensors. The kinds of sensor, and how they are classified, are the subject of [Sensor Taxonomy]. What matters for the node's hardware is:

• Passive sensors only observe (a thermometer, a light sensor, a microphone) and typically draw little.
• Active sensors emit something to measure (an ultrasonic or radar range finder sends a pulse and times the echo) and can draw more than the radio while they work.
• Some sensors need warming up: a gas sensor heats its element before it reads correctly, which can take seconds and a lot of current, so it cannot simply be switched on for a millisecond.
• Analogue or digital output: an analogue sensor goes through the node's ADC; a digital sensor has its own converter and talks to the microcontroller over a serial interface (I2C or SPI).

Actuators do the opposite of a sensor: they turn a command into action, a relay, a valve, a buzzer, a motor. In a sensor and actuator network the node that detects a dry field may also open the irrigation valve. Actuators often need far more current than the node's battery can supply, so they are usually powered separately and only switched by the node.

The power supply

Batteries

A primary battery is used once and thrown away; a secondary (rechargeable) battery can be recharged, which matters only if something can recharge it, such as a solar cell. Most nodes use primary cells, because they hold more energy for their size and lose less of it while they sit unused.

Two real AA cells from their datasheets:

For a node left outdoors for years, the lithium cell's wider temperature range and longer shelf life can be worth its higher price.

The battery never gives its label

Three effects mean a battery delivers less than its rated capacity.

The rate-capacity effect. The harder a cell is worked, the less charge it delivers in total. The E91 datasheet's chart of capacity at continuous discharge (to 0.8 volts, at 21 degrees C) reads, approximately, 3,000 mAh at 25 mA, 2,500 mAh at 100 mA, 2,000 mAh at 250 mA and 1,500 mAh at 500 mA. Halve the capacity by drawing twenty times the current. A sensor node draws tiny average currents, which is good for this effect, but its radio draws its 18 mA in bursts.

The voltage falls as the cell empties. An AA cell starts at about 1.5 volts and is considered exhausted at about 0.9 volts. Two in series therefore end at about 1.8 volts. The electronics must keep working down to that voltage or the rest of the energy is stranded, which is exactly the argument the Telos designers made for the MSP430 (runs to 1.8 V) against the ATmega128 (stops at 2.7 V).

A converter is not free either. A DC-DC converter can hold the voltage steady as the cell empties, but it wastes some energy in doing so and draws current even when the node sleeps. The original Mica had a boost converter; the Mica2 discarded it.

Energy in a cell, worked. Energy is voltage times charge. An AA cell at 1.5 volts delivering 3,000 mAh holds 1.5 × 3,000 = 4,500 milliwatt-hours, which is 4.5 watt-hours. A watt-hour is 3,600 joules, so the cell holds 4.5 × 3,600 = 16,200 joules, and two cells about 32,400 joules. Every protocol in this book is spending from that one budget.

Energy scavenging

A node can top up its battery by scavenging (or harvesting) energy from its surroundings.

• Light, with a small solar cell: by far the most useful outdoors in daylight, and much weaker under indoor lighting.
• Vibration, from machines, vehicles or bridges, through a piezoelectric or electromagnetic generator.
• Temperature differences, through a thermoelectric generator, for example between a hot pipe and the air.
• Airflow or water flow, through a small turbine.
• Radio waves, collected by an antenna, which yields very little unless a transmitter is close.

Scavenged energy is irregular (no sun at night, no vibration when the machine stops), so it charges a rechargeable cell or a supercapacitor, and the node spends from that store. The goal is energy-neutral operation: over each day the node uses no more energy than it collects, and then it can in principle run for as long as its hardware lasts.

Where the day's energy actually goes

The three subsystems have now been described one at a time. Put together over a whole day, they do not share the bill evenly, and which one dominates is not fixed.

# Where a day's energy goes across the three subsystems, at four duty cycles.
V = 3.0                      # volts, two AA cells
I_TX, I_RX, I_IDLE = 17.4e-3, 18.8e-3, 0.426e-3     # CC2420, amperes
I_SLEEP = 20e-6                                      # power down, regulator on
I_MCU_ON, I_MCU_SLEEP = 0.5e-3, 1.1e-6               # a representative low power MCU
I_SENSOR, T_SENSOR = 1.0e-3, 0.05                    # a representative sensor: 1 mA for 50 ms
DAY = 24 * 3600.0

print("A day in the life of a node, in joules, at four radio duty cycles.")
print("Two AA cells at %.1f V; the radio is the CC2420's own figures; the MCU and the" % V)
print("sensor are representative parts, and the sensor is read once a minute.")
print()
print("  radio on   radio        MCU      sensor      sleep       total   radio's share")
samples = DAY / 60.0
e_sensor = samples * T_SENSOR * I_SENSOR * V
for duty in (1.0, 0.1, 0.01, 0.001):
    t_on = DAY * duty
    # half the on time listening, half sending, which is generous to the radio
    e_radio = t_on * (I_RX * 0.5 + I_TX * 0.5) * V
    e_mcu = t_on * I_MCU_ON * V + (DAY - t_on) * I_MCU_SLEEP * V
    e_sleep = (DAY - t_on) * I_SLEEP * V
    total = e_radio + e_mcu + e_sensor + e_sleep
    print("  %7.1f%% %8.1f J %8.2f J %8.2f J %8.2f J %9.1f J %8.0f%%"
          % (duty * 100, e_radio, e_mcu, e_sensor, e_sleep, total,
             100 * e_radio / total))
print()
print("At a hundred per cent the radio is everything and nothing else is worth measuring.")
print("At a tenth of a per cent the sensor and the sleep current are the bill, and making")
print("the radio more efficient would change almost nothing. The subsystem to optimise is")
print("not a property of the node: it is a property of the duty cycle.")

# The crossing point: the duty cycle at which the radio stops dominating.
lo, hi = 1e-6, 1.0
for _ in range(80):
    mid = (lo + hi) / 2
    t_on = DAY * mid
    e_radio = t_on * (I_RX * 0.5 + I_TX * 0.5) * V
    rest = (t_on * I_MCU_ON * V + (DAY - t_on) * I_MCU_SLEEP * V + e_sensor
            + (DAY - t_on) * I_SLEEP * V)
    if e_radio > rest:
        hi = mid
    else:
        lo = mid
print()
print("The radio stops being the largest share below a duty cycle of %.3f per cent," % (hi * 100))
print("which is %.1f seconds of radio in a whole day." % (DAY * hi))

Distinctions

What it does not mean

Listening is not cheap. On the CC2420 it costs more than sending. A node "just waiting" with its receiver on is spending at full rate.

Lower transmit power is not proportionally lower current. A 316-fold cut in radiated power roughly halves the current, because the electronics dominate.

A higher data rate is not a higher energy cost. It is usually lower per bit, because the radio finishes sooner and sleeps.

Sleeping is not always a saving. A sleep shorter than the break-even time costs more to wake from than it saves. With fast radios like the CC2420 that time is around a millisecond; with slower ones it is longer.

A 3,000 mAh label is not 3,000 mAh in service. It depends on the current drawn, the temperature and the cut-off voltage of the electronics.

Quick revision

• Radio states (CC2420): transmit 17.4 mA, receive 18.8 mA, idle 0.426 mA, power down 0.02 mA.
• Transitions: regulator up to 0.6 ms, crystal 1.0 ms (Telos 580 microseconds), idle to receive or transmit and turnaround 192 microseconds.
• Break-even time = energy to wake / (awake power - sleep power); for the CC2420 against listening, around 1 ms even in the worst case.
• Transmit current: 8.5 mA at -25 dBm to 17.4 mA at 0 dBm: a factor of about 316 in power for about 2 in current.
• Energy per bit: Mica2 1.09375, Telos 0.14 microjoules, 7.8125 times less for the faster radio.
• Sensors: passive or active, some need warm-up; actuators usually powered separately.
• AA cells: E91 alkaline and L91 lithium, 1.5 V; E91 capacity falls from about 3,000 mAh at 25 mA to about 1,500 mAh at 500 mA (rate-capacity effect); cut-off about 0.9 V a cell.
• One AA: 1.5 × 3,000 = 4,500 mWh, 16,200 joules. Scavenging: light, vibration, heat, flow, radio; aim for energy-neutral operation.

Test yourself

1. Name the four states of a sensor node's radio and give the CC2420's current in each. Transmit (17.4 mA at 0 dBm), receive or listen (18.8 mA), idle with the oscillator running (0.426 mA), and sleep or power down (20 microamperes, or 0.02 microamperes with the regulator off).

2. What is the break-even time for sleeping, and why does it matter? The shortest sleep for which the energy saved exceeds the energy spent waking up: energy to wake divided by the difference between the power while awake and the power while asleep. A shorter sleep wastes energy, so a MAC protocol must not put the radio to sleep for gaps shorter than this.

3. The CC2420's output power is cut from 0 dBm to -25 dBm. What happens to the radiated power and to the current, and what does that teach? The radiated power falls by a factor of about 316; the current falls only from 17.4 mA to 8.5 mA, about half. Most of the current goes into the radio's electronics, so cutting transmit power saves less than expected.

4. Compare the energy per bit of the Mica2 and Telos radios. Mica2: 42 mW at 38.4 kbps, 1.09375 microjoules per bit. Telos: 35 mW at 250 kbps, 0.14 microjoules per bit, 7.8125 times less, because the faster radio finishes its transmission sooner.

5. What is the rate-capacity effect? Give the figures from the E91 datasheet. A battery delivers less total charge when discharged at a higher current. The E91 gives roughly 3,000 mAh at 25 mA, 2,500 at 100 mA, 2,000 at 250 mA and 1,500 at 500 mA.

6. How much energy does one 1.5 V AA cell of 3,000 mAh hold? 1.5 × 3,000 = 4,500 milliwatt-hours, 4.5 watt-hours, which is 4.5 × 3,600 = 16,200 joules.

7. List four sources a node can scavenge energy from, and say why scavenged energy needs a store. Light, vibration, temperature differences, air or water flow, and radio waves. The supply is irregular, so it charges a rechargeable cell or supercapacitor that the node draws on steadily.

Compare that with the 5.4 days the same node lasts with its radio always on, which is the first line of the program's output below. Sleeping 99 per cent of the time has bought about ninety times the lifetime.

The same sum, run across duty cycles

# Lifetime of a Telos-style node (CC2420 radio, MSP430F1611 processor)
# against its duty cycle. Currents in mA, from the two datasheets at 3 V.
RADIO_ON = 18.8      # CC2420 receiving (transmitting is 17.4, a little less)
RADIO_SLEEP = 0.02   # CC2420 power down, voltage regulator still on
CPU_ON = 0.5         # MSP430F1611 active at 1 MHz and 3 V
CPU_SLEEP = 0.002    # MSP430F1611 standby (LPM3) at 3 V and 25 degrees C
BATTERY = 2500       # mAh we allow ourselves from two AA cells in series

def average_current(duty):
    """Radio and processor awake for a fraction `duty` of the time."""
    awake = RADIO_ON + CPU_ON
    asleep = RADIO_SLEEP + CPU_SLEEP
    return duty * awake + (1 - duty) * asleep

print("duty cycle   average mA    lifetime")
for duty in (1, 0.1, 0.01, 0.001, 0.0001, 0):
    mA = average_current(duty)
    days = BATTERY / mA / 24
    if days < 365:
        life = "%.1f days" % days
    else:
        life = "%.1f years" % (days / 365)
    print("%9.2f %%   %10.4f   %s" % (duty * 100, mA, life))

duty cycle   average mA    lifetime
   100.00 %      19.3000   5.4 days
    10.00 %       1.9498   53.4 days
     1.00 %       0.2148   1.3 years
     0.10 %       0.0413   6.9 years
     0.01 %       0.0239   11.9 years
     0.00 %       0.0220   13.0 years

Read the lifetime column from the top, and three things stand out.

Always on is hopeless. 5.4 days, which is what [The Challenges of Wireless Sensor Networks] found with a rougher sum.

At first, every tenfold cut in duty cycle buys almost tenfold life. From 100 to 10 per cent, and from 10 to 1 per cent, the lifetime grows by nearly ten each time, because the awake current is almost the whole average.

Then the curve flattens. From 0.1 per cent to 0.01 per cent the lifetime does not grow tenfold, and even a node that never wakes at all (the last line) lasts only 13 years. That ceiling is set by the sleep current alone: 2,500 mAh divided by 0.022 mA. Below about 0.1 per cent, making the node sleep even more hardly helps; making its sleep deeper does.

A real cycle, item by item

Meera's vineyard node wakes every 15 minutes for 60 milliseconds. What it does in that time is an assumption about the software, stated here so the reader can change it: the sensors are powered for 20 ms at 1 mA, the radio listens for 40 ms (waiting for the channel, for the acknowledgement and for a neighbour's packet to forward) and transmits for 4 ms. The listing adds up the charge of each item, in milliampere-milliseconds, and compares two ways of putting the radio to sleep.

# One 15-minute cycle of the vineyard node, item by item.
# Charge is current (mA) times time (ms); dividing the total by the cycle
# length gives the average current the battery must supply.
CYCLE_MS = 15 * 60 * 1000
AWAKE_MS = 60

def budget(radio_sleep):
    items = [
        ("processor awake",     0.5,   AWAKE_MS),
        ("sensors powered",     1.0,   20),
        ("radio listening",     18.8,  40),
        ("radio transmitting",  17.4,  4),
        ("processor asleep",    0.002, CYCLE_MS - AWAKE_MS),
        ("radio asleep",        radio_sleep, CYCLE_MS - AWAKE_MS),
    ]
    total = sum(mA * ms for _, mA, ms in items)
    for name, mA, ms in items:
        share = 100 * mA * ms / total
        print("  %-19s %7.3f mA × %6d ms = %9.1f   %5.1f %%"
              % (name, mA, ms, mA * ms, share))
    average = total / CYCLE_MS
    years = 2500 / average / 24 / 365
    print("  total %.1f mA ms; average %.5f mA; lifetime %.1f years"
          % (total, average, years))

print("Radio powered down between cycles (20 microamperes):")
budget(0.02)
print()
print("Radio's voltage regulator off as well (0.02 microamperes):")
budget(0.00002)

Radio powered down between cycles (20 microamperes):
  processor awake       0.500 mA ×     60 ms =      30.0     0.1 %
  sensors powered       1.000 mA ×     20 ms =      20.0     0.1 %
  radio listening      18.800 mA ×     40 ms =     752.0     3.6 %
  radio transmitting   17.400 mA ×      4 ms =      69.6     0.3 %
  processor asleep      0.002 mA × 899940 ms =    1799.9     8.7 %
  radio asleep          0.020 mA × 899940 ms =   17998.8    87.1 %
  total 20670.3 mA ms; average 0.02297 mA; lifetime 12.4 years

Radio's voltage regulator off as well (0.02 microamperes):
  processor awake       0.500 mA ×     60 ms =      30.0     1.1 %
  sensors powered       1.000 mA ×     20 ms =      20.0     0.7 %
  radio listening      18.800 mA ×     40 ms =     752.0    28.0 %
  radio transmitting   17.400 mA ×      4 ms =      69.6     2.6 %
  processor asleep      0.002 mA × 899940 ms =    1799.9    66.9 %
  radio asleep          0.000 mA × 899940 ms =      18.0     0.7 %
  total 2689.5 mA ms; average 0.00299 mA; lifetime 95.5 years

The first budget is the surprise of this chapter. The radio's listening and transmitting, the part everyone worries about, is about 4 per cent of the charge. The radio asleep, at 20 microamperes, is 87 per cent, because it is asleep for 899,940 of every 900,000 milliseconds. At this duty cycle the job is no longer to sleep more but to sleep deeper.

The second budget switches the radio's voltage regulator off as well, the CC2420's 0.02-microampere state, which costs only a slightly longer wake-up (up to 0.6 ms, from [The Radio, the Sensors and the Power Supply of a Node]). The average current falls from about 0.023 mA to about 0.003 mA, nearly eight times less, and now the processor's standby is the largest item.

But neither lifetime can be believed as it stands. 12.4 years and 95.5 years are longer than the batteries themselves last on a shelf: the E91 datasheet gives its shelf life as 10 years at 21 degrees C, the L91 lithium cell's as 25 years. When the electronics draw this little, the battery's own chemistry, not the node, sets the lifetime. A designer who stopped at the program's last line would promise the farmer a century.

What the model leaves out

A good answer names the limits of its own sum.

• Forwarding. This node sends only its own packet. A node near the sink also receives and forwards everyone else's, so it listens and transmits many times longer and dies first. The network's lifetime is set by those nodes, which is why [Optimization Goals: Quality of Service, Energy Efficiency and Lifetime] defines lifetime in several ways.
• Retransmissions and collisions, which add radio time whenever the channel is busy or a packet is lost.
• The battery's behaviour: the rate-capacity effect on the radio's 18 mA bursts, the effect of heat and cold, and self-discharge over the years.
• Start-up energy, the milliseconds of oscillator start-up at each wake-up; small here, larger for a node that wakes very often.
• The cut-off voltage, which decides how much of the battery the electronics can actually use.

Distinctions

What it does not mean

Halving the radio's active current does not double the lifetime at low duty cycles. Once the sleep current dominates, the active current hardly matters, as the vineyard budget showed.

Two cells in series do not double the mAh. They double the voltage; the charge that flows is the same through both.

A computed lifetime longer than the battery's shelf life is not a real lifetime. It means the chemistry will expire first.

The node's lifetime is not the network's. A relay near the sink may last a tenth as long as a node at the edge of the field.

Quick revision

• I(avg) = d × I(awake) + (1 - d) × I(sleep); lifetime = C / I(avg).
• Telos parts at 3 V: I(awake) = 18.8 + 0.5 = 19.3 mA; I(sleep) = 0.02 + 0.002 = 0.022 mA.
• 1 per cent duty cycle: 0.21478 mA; 2,500 mAh lasts about 1.3 years. Always on: 5.4 days.
• Every tenfold cut in duty cycle buys nearly tenfold life until the sleep current takes over; with no waking at all, the ceiling is 13 years.
• Vineyard cycle: radio asleep is 87 per cent of the charge; switching its regulator off too cuts the average about eight times.
• Then the battery's shelf life (E91 10 years, L91 25 years) is the real limit.

Test yourself

1. A node draws 19.3 mA awake and 0.022 mA asleep, and is awake 1 per cent of the time. Find its average current and its lifetime on 2,500 mAh. 0.01 × 19.3 + 0.99 × 0.022 = 0.193 + 0.02178 = 0.21478 mA. Lifetime 2,500 / 0.21478, about 11,640 hours, about 1.3 years.

2. The same node is left with its radio always on. How long does it last, and what does the comparison show? 2,500 / 19.3, about 130 hours, 5.4 days. The 1 per cent duty cycle buys about ninety times the lifetime, which is why sensor network radios are switched off almost all the time.

3. Why does cutting the duty cycle from 0.01 per cent to 0.001 per cent hardly change the lifetime? Because at such low duty cycles the sleep current makes up almost all of the average current, and it is not affected by how often the node wakes. Only a deeper sleep state helps.

4. In the vineyard budget, what fraction of the charge goes on the radio while it is asleep, and why? About 87 per cent. The radio draws only 20 microamperes asleep, but it is asleep for 899,940 of every 900,000 milliseconds, while it listens and transmits for only 44.

5. The program predicts 95.5 years. What is wrong with that answer? It ignores the battery's own limits. An E91 alkaline cell has a shelf life of about 10 years at 21 degrees C, so the chemistry, not the node's consumption, sets the lifetime. The prediction also ignores forwarding, retransmissions, temperature and the cut-off voltage.

6. Two AA cells of 2,500 mAh are connected in series. What voltage and what capacity does the node see? About 3 volts, and still 2,500 mAh: series connection adds voltages, not charge.

Omnidirectional or narrow-beam

The second division is about direction, and it applies to passive sensors.

• Omnidirectional sensors respond equally from every direction: a thermometer, an ordinary microphone.
• Narrow-beam sensors see only in one direction: a camera, a directional microphone, a passive infrared detector behind a lens.

So Karl and Willig's three kinds are passive omnidirectional, passive narrow-beam and active. For the network the difference matters: a narrow-beam sensor's reading depends on which way it points, so its orientation has to be known, and covering an area takes more of them.

By output, by contact and by principle

• Analogue or digital output. An analogue sensor gives a voltage or current that the node's ADC converts; a digital sensor has its own converter and sends a number over a serial bus.
• Contact or non-contact. A soil probe or a strain gauge must touch what it measures; an infrared thermometer or a camera measures from a distance.
• Operating principle. How the quantity becomes an electrical signal: a change in resistance (thermistors, strain gauges), in capacitance (humidity and soil-moisture sensors), in inductance (proximity and position sensors, where a moving core changes a coil's inductance), a piezoelectric voltage from stress (vibration sensors), a photoelectric current from light, a thermoelectric voltage from a temperature difference, or a micro-electro-mechanical (MEMS) structure on a chip, as in most accelerometers.

Part 2: classifying sensor networks

The three parts of every sensing application

Tilak, Abu-Ghazaleh and Heinzelman begin by naming three participants, and the rest of their taxonomy is about how the three relate.

• Sensor: the device that implements the physical sensing and reports its measurements; in their words it typically consists of sensing hardware, memory, battery, embedded processor, and trans-receiver.
• Observer: the end user who wants information about the phenomenon, who may indicate interests (or queries) to the network and receive responses.
• Phenomenon: "The entity of interest to the observer", the thing being sensed and potentially analysed; several may be observed at once.

By data delivery model

How and when readings are sent to the observer. This is the classification most often asked.

1. Continuous. The sensors send their data continuously at a set rate: the vineyard, every 15 minutes. The paper notes that clustering is most efficient for static networks with continuous data.
2. Event-driven. The sensors report only when an event of interest occurs: an intruder, a fire. Most of the time the network is silent; when the event happens, many nearby sensors detect it together and contend for the channel at once, which raises both the risk of losing the critical report and its delay.
3. Observer-initiated, or request-reply. The sensors report only in response to an explicit request from the observer, sent to them directly or through other sensors: what is the temperature in zone 3 now?
4. Hybrid. The three can coexist in one network: continuous background readings, event alarms and answers to queries all at once.

By network dynamics

What moves. The paper divides networks into static, where nothing moves (sensors, observer and phenomenon are all fixed, as in a group of temperature sensors), and dynamic, where something does. Three kinds of motion:

• Mobile observer. The observer moves while the sensors stay put: a vehicle or a person carrying the collecting device drives past the field and gathers readings as it goes.
• Mobile sensors. The sensors themselves move: sensors on animals, vehicles or drifting buoys. Paths to the observer break as sensors move and must be rebuilt.
• Mobile phenomena. What is being watched moves: a vehicle, an animal, a fire front. The set of sensors that should report changes as the phenomenon moves; in the paper's words, sensors can hand the "responsibility of monitoring to a closer node" as the target drifts.

Motion is the commonest source of change, but the paper notes others: sensors failing and observers' interests changing.

By communication

The paper divides the network's traffic into two kinds.

• Application communication carries the sensed data towards the observer. It is cooperative when sensors work together to meet the observer's interest (for example a cluster head combining its members' readings) and non-cooperative when each sensor reports on its own.
• Infrastructure communication is the traffic needed to set up, maintain and optimise the network: discovering neighbours, building paths, rebuilding them when a sensor moves or dies. It is overhead, so a good protocol keeps it small, though spending some on it can reduce application traffic overall.

By structure, composition and deployment

• Flat or hierarchical. In a flat network every node has the same role; in a hierarchical one some nodes are cluster heads. Sohraby, Minoli and Znati make the related division into two categories: networks that are mesh-based with multi-hop radio links and dynamic routing, and networks that are point-to-point or star-based with single-hop radio links and static routing to a node on the fixed network.
• Homogeneous or heterogeneous. All nodes the same, or some with more energy, better radios or extra sensors, such as mains-powered cluster heads.
• Planned or random deployment. Nodes placed at chosen points, or scattered, for example from the air.

The text book's own categorisation

Sohraby, Minoli and Znati, in their chapter 1 (Table 1.1, which they adapt from an earlier source), sort the issues of a sensor network under four headings. It is a compact taxonomy in its own right, and it overlaps with everything above.

The same text book notes that passive sensors "tend to be low-energy devices" while active sensors such as radar and sonar "tend to be high-energy systems", which is the energy point made above in its own words.

Worked example: classifying four networks

Each column needs a different protocol. The vineyard wants a stable schedule and long sleeps; the volcano wants to move bursts of data reliably and time them exactly; the collars must store data until two animals, or an animal and a base station, come within range; and the roadside boxes must wake up and hand over their data in the few seconds a vehicle is in range.

Distinctions

What it does not mean

"Sensor taxonomy" is not only a list of sensor types. An answer that stops at temperature, pressure and humidity has done half the job; the classification of networks is the half with the design consequences.

Passive does not mean unpowered here. In this subject a passive sensor is one that does not emit; it may still need a supply.

Event-driven does not mean light traffic. Most of the time it is silent, but at an event many sensors report at once, which is the hardest moment for the MAC protocol.

A mobile phenomenon does not make the network mobile. The sensors can all be fixed while the target moves; what changes is which of them report.

Quick revision

• Two classifications: of sensors and of networks.
• Sensors: what they measure; passive (only observe) or active (emit and measure the return); omnidirectional or narrow-beam; analogue or digital; contact or non-contact; operating principle. Karl and Willig: passive omnidirectional, passive narrow-beam, active.
• Networks (Tilak and colleagues, 2002): participants sensor, observer, phenomenon; delivery continuous, event-driven, observer-initiated (request-reply), hybrid; dynamics static, or mobile observer, mobile sensors, mobile phenomena; communication application (cooperative or not) and infrastructure.
• Also: flat or hierarchical; single or multi-hop (Sohraby and colleagues: mesh with dynamic routing, or star with static routing); homogeneous or heterogeneous; planned or random.

Test yourself

1. Explain the data delivery models of sensor networks. Continuous: sensors send at a set rate. Event-driven: sensors report only when an event of interest occurs. Observer-initiated (request-reply): sensors report only when the observer asks. Hybrid: the three coexist in one network.

2. Distinguish passive and active sensors, with examples. A passive sensor only observes and emits nothing (thermometer, microphone, passive infrared detector); an active sensor emits energy and measures what returns (ultrasonic range finder, radar) and so uses more energy.

3. What are the three kinds of mobility in the Tilak taxonomy? Mobile observer (the collector moves), mobile sensors (the nodes move, breaking paths) and mobile phenomena (the target moves, changing which nodes should report).

4. What is infrastructure communication, and why should it be kept small? The traffic needed to configure, maintain and optimise the network, such as discovering neighbours and building or repairing paths. It carries no sensed data, so it is overhead that costs energy, though a little of it can reduce application traffic overall.

5. Classify a network of GPS collars on elephants. Passive sensors (GPS receivers, accelerometers); continuous logging with delivery when in range; dynamic, with mobile sensors; homogeneous nodes; deployment carried by the animals; paths formed opportunistically when two collars or a collar and a base station meet.

The design factors

The survey calls these the factors that "serve as a guideline to design a protocol or an algorithm for sensor networks" and that can be used to compare one scheme with another.

1. Fault tolerance

Some nodes will fail: they run out of power, suffer physical damage, or are blocked by interference. Fault tolerance is the ability to keep the network's functions running without interruption despite node failures. The survey gives a model for one node's reliability, the probability that node k has not failed within a time t:

where λ (lambda) is that node's failure rate, the average number of failures per unit time. The model is the Poisson assumption: failures happen at random at a steady average rate. How much fault tolerance a network needs depends on its environment: a house needs little, a battlefield a great deal.

2. Scalability

A deployment may have hundreds or thousands of nodes, and in extreme cases millions. Protocols must work with that many, and must make use of the resulting density. The survey gives the density as

where N nodes are scattered over an area A and R is the radio range. μ(R) is the number of nodes within radio range of each node: its expected number of neighbours. Density can range from a few nodes to a few hundred in a region less than 10 metres across.

3. Production costs

Because there are so many nodes, the cost of one decides whether the network is worth building at all. In the survey's words, if the network costs more than deploying traditional sensors, "the sensor network is not cost-justified". Cheap nodes mean small batteries, simple radios and little memory.

4. Hardware constraints

A node has four basic units (sensing, processing, transceiver, power) and possibly a location finding system, a power generator and a mobilizer, as [Inside a Sensor Node: The Five Units] explains. The survey adds that all of it may need to fit in a matchbox or even under a cubic centimetre, and that nodes must consume extremely little power, operate at high density, cost little, be dispensable and autonomous, operate unattended and adapt to their environment.

5. Sensor network topology

With hundreds to thousands of nodes deployed "within tens of feet of each other" and densities up to 20 nodes in a cubic metre, keeping the topology working needs care in three phases:

1. Pre-deployment and deployment: nodes are thrown in as a mass or placed one by one, dropped from a plane, delivered in an artillery shell, rocket or missile, or placed by a person or a robot.
2. Post-deployment: the topology changes as nodes move, as links are lost to jamming, noise or moving obstacles, as energy runs down, as nodes malfunction and as the task changes.
3. Redeployment of additional nodes: new nodes are added at any time to replace failed ones or because the task has changed.

6. Environment

Everything in the first half of this chapter: nodes work unattended in remote places, close to or inside the phenomenon.

7. Transmission media

Links can be formed by radio, infrared or optical media. To allow operation anywhere, the medium must be available worldwide, which in practice means the licence-free industrial, scientific and medical (ISM) bands. Infrared is licence-free, robust against electrical interference and cheap, and optical links were used by the Smart Dust mote, but both need a clear line of sight. Radio needs none, which is why almost every node uses it.

8. Power consumption

The survey's example power source is small, under 0.5 ampere-hours at 1.2 volts, and in many applications it can never be replaced, so a node's lifetime depends strongly on its battery. Because each node is both a data originator and a data router, the failure of a few can force rerouting and reorganisation of the whole network. The survey divides a node's consumption into three domains: sensing, communication and data processing, and [How Long a Node Lasts: The Energy Budget Worked Out] puts real numbers on them.

Worked example: the two formulas, by hand and by program

Reliability

Take a node with a failure rate of λ = 0.2 a year: on average, one failure in five node-years (an assumption for the exercise). Its reliability after one year is

which is about 0.8187. So there is roughly an 18 per cent chance a given node has failed within a year.

Now suppose every spot in the field is watched by two nodes, and that nodes fail independently of each other. The spot is lost only if both have failed, which has probability (1 - 0.8187) squared, about 0.0329. So the spot is still watched with probability about 0.9671. With three nodes it is about 0.9940. Redundancy turns an unreliable node into a reliable network.

Density

Scatter N = 200 nodes over a field 100 metres by 100 metres, so A is 10,000 square metres, with a radio range R of 20 metres:

which is about 25.1 neighbours per node. That is plenty for routing and for redundancy, and it also means 25 radios contend for the channel around every node, which the MAC protocol must handle.

The program below computes both formulas over several cases, so the pattern is visible rather than one number.

import math

# Fault tolerance: the survey's R(t) = e^(-lambda t), the chance that one node
# has not failed by time t, for a failure rate lambda (failures per year).
LAMBDA = 0.2   # assumed: on average one failure per five node-years

print("years   one node   a spot watched by 2   by 3")
for t in (1, 2, 3, 5):
    r = math.exp(-LAMBDA * t)
    two = 1 - (1 - r) ** 2      # at least one of two still working
    three = 1 - (1 - r) ** 3
    print("%5d   %8.4f   %19.4f   %4.4f" % (t, r, two, three))

# Density: the survey's mu(R) = N * pi * R^2 / A, the number of nodes
# within radio range R of each node, for N nodes scattered over area A.
N, A = 200, 100 * 100          # 200 nodes in a 100 m by 100 m field
print()
print("range R (m)   neighbours mu(R)")
for R in (10, 15, 20, 30):
    mu = N * math.pi * R ** 2 / A
    print("%11d   %16.1f" % (R, mu))

years   one node   a spot watched by 2   by 3
    1     0.8187                0.9671   0.9940
    2     0.6703                0.8913   0.9642
    3     0.5488                0.7964   0.9082
    5     0.3679                0.6004   0.7474

range R (m)   neighbours mu(R)
         10                6.3
         15               14.1
         20               25.1
         30               56.5

Read the reliability rows downwards. After five years a single node has only about a 37 per cent chance of still working, but a spot watched by three nodes is still covered with about 75 per cent probability. Redundancy buys time, not immortality.

Read the density rows. μ grows with the square of the range: doubling R from 10 to 20 metres multiplies the neighbours by four, from about 6 to about 25. Turning a radio's power up to gain range therefore floods every node with neighbours to contend with, which is one reason [Energy Efficiency in Ad Hoc Networks: Where the Energy Goes] prefers to turn power down.

Distinctions

What it does not mean

R(t) is not the network's reliability. It is one node's. The network's depends on redundancy, and the sum above treats failures as independent, which a flood or a fire that destroys many nodes at once does not respect.

A higher density is not always better. It gives redundancy and routes, and it also gives collisions and more overhearing. The best density is the lowest that meets coverage and connectivity, which [Deployment and Coverage: Random Against Grid] examines.

"Unattended" does not mean "untouched". Unattended nodes are exactly the ones an animal or an attacker can reach without anyone noticing.

The survey's numbers are its own time's. Its target of a node costing well under one US dollar and its 0.5 ampere-hour power source describe research goals of 2002, not the price or battery of a node you can buy.

Quick revision

• Environment: unattended, remote or harsh: machinery, ocean floor, contaminated fields, battlefields, buildings, homes, the body. Threats: physical conditions, damage, the radio environment, no attendance.
• Near the ground the path loss exponent is close to 4.
• Eight design factors (Akyildiz and colleagues 2002): fault tolerance, scalability, production costs, hardware constraints, topology, environment, transmission media, power consumption.
• R(t) = e^(-λt): one node's reliability. λ = 0.2 a year: R(1) about 0.8187; with two independent nodes a spot survives with about 0.9671, with three about 0.9940.
• μ(R) = N × π × R² / A: neighbours per node. 200 nodes, 100 m by 100 m, R = 20 m: about 25.1; it grows as R squared.
• Topology in three phases: deployment, post-deployment, redeployment. Media: radio, infrared, optical (the last two need line of sight). Power: sensing, communication, processing.

Test yourself

1. Describe the environment in which sensor networks operate. Nodes are placed close to or inside the phenomenon, so they usually work unattended in remote or harsh places: inside machinery, on the ocean floor, in contaminated fields, on battlefields, in buildings and homes, on the body. They face weather, damage, interference and a crowded radio band, with nobody to repair them.

2. List and explain the factors influencing sensor network design. Fault tolerance (keep working despite failures, modelled by R(t) = e^(-λt)); scalability (hundreds to millions of nodes, density μ(R) = N π R² / A); production costs (each node must be cheap); hardware constraints (four basic units in a tiny, frugal package); topology (deployment, post-deployment and redeployment phases); environment (unattended, harsh); transmission media (radio, infrared, optical, available worldwide); power consumption (sensing, communication, processing).

3. A node has a failure rate of 0.2 a year. What is its reliability after one year, and what is the chance a spot watched by two such nodes is still covered? R(1) = e^(-0.2), about 0.8187. With independent failures the spot is lost with probability (1 - 0.8187)², about 0.0329, so it is covered with about 0.9671.

4. 200 nodes are scattered over 100 m by 100 m with a radio range of 20 m. How many neighbours does each have on average? μ = 200 × π × 400 / 10,000, about 25.1.

5. Name the three phases of topology maintenance. Pre-deployment and deployment (nodes thrown in or placed), post-deployment (topology changes from movement, lost links, energy, malfunction, task changes), and redeployment of additional nodes.

Decibels, and why radio engineers use them

A radio signal's power varies over an enormous range: the CC2420 transmits 1 milliwatt and can decode a signal of about 0.0000000003 milliwatts. Multiplying and dividing such numbers is awkward, so powers are written as logarithms.

• A power ratio in decibels (dB) is 10 log10 of the ratio. A factor of 10 is 10 dB, a factor of 100 is 20 dB, and a factor of 2 is about 3 dB.
• An absolute power in dBm is its ratio to 1 milliwatt, in decibels. 0 dBm is 1 mW, 10 dBm is 10 mW, -10 dBm is 0.1 mW, and -95 dBm is 10 to the power -9.5 milliwatts.
• Antenna gain is written in dBi, decibels relative to an isotropic antenna that radiates equally in all directions ([Antennas: Radiators, Dipoles and Radiation Patterns]).

The payoff is that gains and losses, which multiply, become additions: a link budget is simply a column of numbers added and subtracted.

Path loss: how much is lost on the way

In free space, with nothing in the way, the power spreads out over an ever larger sphere, and the loss between two isotropic antennas is given by ITU-R Recommendation P.525:

or, with the frequency f in megahertz and the distance d in kilometres,

Two facts follow. The loss grows by 6 dB for every doubling of distance (20 log10 of 2), and it is higher at higher frequencies for the same distance, which is why 868 MHz reaches further than 2.4 GHz.

Near the ground it is worse. The survey of [The Sensor Network Protocol Stack and Its Three Planes] says the required power grows as d to the power n with n between 2 and 4, and near 4 for antennas close to the ground, largely because of a ground-reflected ray cancelling part of the signal. The usual model for this is the log-distance model: measure or compute the loss at a reference distance of 1 metre, then

with d in metres. n = 2 is free space; n = 4 means every doubling of distance costs 12 dB instead of 6.

The link budget

Put the pieces together. For a link to work, the power arriving at the receiver must be at least its sensitivity, the weakest signal it can decode with an acceptable error rate, plus a margin for fading: the signal also rises and falls from moment to moment as people move, leaves stir and reflections change ([Multipath, Fading and the Doppler Effect]). So the path loss the link can afford is

and the range is the distance at which the path loss reaches that value.

Worked example: how far can a CC2420 reach?

The figures. The CC2420 transmits at 0 dBm and has a typical sensitivity of -95 dBm (the standard itself only requires -85 dBm at 2.4 GHz, so this radio has 10 dB to spare). Assume simple antennas of 0 dBi at both ends and a fading margin of 10 dB.

Step 1, the allowed loss.

so the link can afford 85 dB of path loss.

Step 2, the loss at 1 metre. At 2,450 MHz and 0.001 km, P.525 gives 32.4 + 20 log10(2,450) + 20 log10(0.001), which is 32.4 + 67.78 - 60, about 40.18 dB.

Step 3, the range. The link can lose another 85 - 40.18, about 44.82 dB, beyond the first metre. With the log-distance model that is 10 n log10(d) = 44.82, so d is 10 to the power 44.82 / (10 n). The program does the arithmetic for three values of n, and for the same budget at 868 MHz.

import math

# Link budget of a CC2420 link: 0 dBm out, -95 dBm sensitivity (datasheet),
# 0 dBi antennas at both ends, and a 10 dB margin for fading.
P_TX, SENSITIVITY, GAINS, MARGIN = 0, -95, 0, 10
allowed = P_TX + GAINS - SENSITIVITY - MARGIN
print("path loss the link can afford: %d dB" % allowed)

def loss_at_1m(f_mhz):
    """Free-space loss at 1 m, ITU-R P.525: 32.4 + 20 log f(MHz) + 20 log d(km)."""
    return 32.4 + 20 * math.log10(f_mhz) + 20 * math.log10(0.001)

def range_m(f_mhz, n):
    """Log-distance model: L(d) = L(1 m) + 10 n log10(d / 1 m); solve L(d) = allowed."""
    return 10 ** ((allowed - loss_at_1m(f_mhz)) / (10 * n))

for f in (2450, 868):
    print()
    print("%d MHz: free-space loss at 1 m is %.2f dB" % (f, loss_at_1m(f)))
    for n in (2, 3, 4):
        print("   path loss exponent n = %d: range %6.1f m" % (n, range_m(f, n)))

print()
print("range gained by 3 dB more power (twice the milliwatts):")
for n in (2, 3, 4):
    print("   n = %d: range multiplied by %.3f" % (n, 10 ** (3 / (10 * n))))

path loss the link can afford: 85 dB

2450 MHz: free-space loss at 1 m is 40.18 dB
   path loss exponent n = 2: range  174.1 m
   path loss exponent n = 3: range   31.2 m
   path loss exponent n = 4: range   13.2 m

868 MHz: free-space loss at 1 m is 31.17 dB
   path loss exponent n = 2: range  491.5 m
   path loss exponent n = 3: range   62.3 m
   path loss exponent n = 4: range   22.2 m

range gained by 3 dB more power (twice the milliwatts):
   n = 2: range multiplied by 1.413
   n = 3: range multiplied by 1.259
   n = 4: range multiplied by 1.189

Read the 2,450 MHz rows. In free space the link reaches about 174 metres. With the node on the ground and n = 4, the same radio reaches about 13 metres. That factor of thirteen is the difference between a textbook's range and a field's, and it is why a sensor network needs many short hops.

Read the 868 MHz rows. The same budget at the lower frequency reaches further at every n, because the loss at 1 metre is about 9 dB smaller. (The CC2420 itself works only at 2.4 GHz; the rows show what the same budget buys in the lower band.)

Read the last rows. Doubling the transmit power adds 3 dB, and that multiplies the range by only 1.41 in free space and 1.19 near the ground. Near the ground, doubling the power buys less than a fifth more range, at nearly double the transmit energy. Shorter hops are the cheaper answer.

Distinctions

What it does not mean

The datasheet range is not the field range. Ranges quoted for open, line-of-sight conditions can shrink by an order of magnitude with the node on the ground among plants, walls or people.

A higher-numbered sensitivity is not better. -95 dBm is a weaker signal than -85 dBm, so a receiver with -95 dBm sensitivity is the more sensitive.

Doubling the power does not double the range. It adds 3 dB, which buys between 19 and 41 per cent more range depending on the environment.

The margin is not waste. Without it the link works only when conditions are at their best and fails whenever someone walks past.

Quick revision

• A sensor radio: low power, fast on and off, modest rate, short range, licence-free band, robust.
• 802.15.4 bands: 868 to 868.6 MHz (20 kb/s BPSK), 902 to 928 MHz (40 kb/s BPSK), 2400 to 2483.5 MHz worldwide (250 kb/s O-QPSK, 62.5 ksymbol/s, 2,000 kchip/s).
• dB a ratio, dBm relative to 1 mW (0 dBm = 1 mW), dBi antenna gain; a factor of 2 is about 3 dB, of 10 is 10 dB.
• Free space (ITU-R P.525): L = 32.4 + 20 log10 f(MHz) + 20 log10 d(km); 6 dB per doubling of distance.
• Log-distance: L(d) = L(1 m) + 10 n log10 d, n = 2 free space, near 4 near the ground.
• Link works if received power is at least sensitivity plus margin.
• CC2420 (0 dBm, -95 dBm, 10 dB margin): allowed loss 85 dB; range 174 m free space, 31 m at n = 3, 13 m at n = 4.
• +3 dB multiplies range by 1.41 (n = 2) to 1.19 (n = 4).

Test yourself

1. What are the requirements of a radio for a sensor network? Very low energy per bit and fast switching on and off; a modest data rate; short range, with multi-hop for distance; operation in a licence-free band; robustness to interference and poor links.

2. Convert 0 dBm, 10 dBm and -10 dBm to milliwatts. 1 mW, 10 mW and 0.1 mW.

3. Write the link budget and explain each term. Received power = transmit power + transmit antenna gain + receive antenna gain - path loss, in dB and dBm. The link works if the received power is at least the receiver's sensitivity plus a fading margin, so the loss the link can afford is transmit power + gains - sensitivity - margin.

4. A radio sends at 0 dBm with 0 dBi antennas, its sensitivity is -95 dBm and a 10 dB margin is kept. What path loss can it afford? 0 + 0 + 0 - (-95) - 10 = 85 dB.

5. Why is a sensor node's range near the ground so much shorter than in free space? Near the ground the path loss exponent approaches 4, so each doubling of distance costs 12 dB instead of 6. In the worked example the same radio reaches about 174 m with n = 2 and about 13 m with n = 4.

6. Why do 868 MHz radios reach further than 2.4 GHz radios with the same power and sensitivity? Free-space loss grows with frequency (the 20 log10 f term), so at 868 MHz the loss over the first metre is about 9 dB less, and every distance costs less.

Because it defines only two layers, other standards supply the rest:

• Zigbee adds a network layer and an application framework. Its network layer supports star, tree and mesh topologies; the device that starts and controls the network is the Zigbee coordinator, which the specification defines as "an IEEE 802.15.4 PAN coordinator"; a Zigbee router is "capable of routing messages between devices"; a Zigbee end device is neither, and only sends and receives its own traffic. Zigbee's routing is taught in [Built on 802.15.4: Zigbee Routing, Security and the Later Amendments].
• 6LoWPAN carries IPv6 over 802.15.4 frames, so that sensor nodes can be ordinary Internet hosts. It is the subject of [Sensor Networks in the Internet of Things: 6LoWPAN, RPL and CoAP].

Strengths: designed for battery-powered nodes; supports multi-hop mesh networks through the layers above it; worldwide 2.4 GHz band; cheap radios. Limits: tens of metres per hop, so large areas need many hops; the 2.4 GHz band is shared with Wi-Fi and Bluetooth.

Bluetooth Low Energy

Bluetooth Low Energy (Bluetooth LE, also branded Bluetooth Smart) was introduced in Bluetooth 4.0 and extended in 4.1 and later versions. RFC 7668 describes its target plainly: devices "that operate with very low-capacity (e.g., coin cell) batteries or minimalistic power sources". A device in the central role (typically a phone or a router) manages connections to several peripherals (the sensors), giving a star topology. Its packets are small: the default MTU of its link-layer channels is 27 octets, 23 of them available to the upper layers.

Strengths: in almost every phone, so a person's phone can be the gateway; very low energy per connection; good for wearable and personal sensors, such as the heart-rate monitor RFC 7668 gives as its example. Limits: short range; the star topology means a node must be within reach of a central device; not designed for large multi-hop fields.

Wi-Fi

IEEE 802.11 (Wi-Fi) gives tens of megabits per second, which the text book's table puts at 11 to 54 for the 802.11b and g generations. It is designed for laptops and phones with large batteries or mains power, and its receivers are built to be on whenever the device is in use. Strengths: existing infrastructure everywhere, high data rates, IP built in. Limits: far more power than a sensor node can sustain on small batteries; access points needed. It suits sensors with mains power (cameras, gateways) and the gateway's own link to the Internet.

The low-power wide-area networks

A newer family aims at a different corner of the trade-off. RFC 8376, the IETF's overview, puts their shared goal as "supporting large numbers of very low-cost, low-throughput devices with very low power consumption, so that even battery-powered devices can be deployed for years", and says they accept "severe bandwidth and duty cycle constraints" in return for "multiple-kilometer radio links". LoRaWAN, Sigfox and NB-IoT are star networks: every device talks directly to a base station or gateway, with no relaying.

LoRaWAN uses ISM bands, for example 433 MHz and 868 MHz in the European Union and 915 MHz in the Americas. In the EU 868 MHz band its three default channels are at 868.1, 868.2 and 868.3 MHz, and its data rate runs from 250 bit/s with frames of 59 octets up to 50,000 bit/s with frames of 250 octets. A device's transmission may be received by several gateways at once, and the network adjusts each device's data rate and power by an adaptive data rate scheme. After each transmission a basic (Class A) device opens two short receive windows, and only then may it transmit again.

Sigfox uses ultra narrow band transmission: channels of 100 or 600 hertz, 100 or 600 baud, modulated by DBPSK. Its devices send "only a few bytes per day, week, or month", which RFC 8376 says allows them to last "up to 10-15 years" on one battery.

NB-IoT (Narrowband IoT) runs in licensed mobile-operator spectrum, using a narrow band of 180 kHz inside, beside or outside an LTE carrier. Its peak rates are 60 kbit/s up and 30 kbit/s down, and its design targets include a module cost of less than 5 US dollars, coverage of 164 dB maximum coupling loss, battery life of over 10 years and about 55,000 devices per cell.

Wi-SUN FAN (Field Area Network) is the exception to the star pattern: RFC 8376 describes it as "an IPv6 wireless mesh network" using frequency hopping, typically 2 to 3 km in line of sight and up to 300 kbit/s.

Worked example: what a 1 per cent duty cycle allows

Some ISM bands limit how much of the time a device may transmit, a limit RFC 8376 says is "usually expressed as a percentage of time per hour", and its LoRaWAN table gives 1 per cent as the tightest such limit. Take a LoRaWAN device in the EU 868 MHz band at its slowest and longest-reaching setting, 250 bit/s, sending a full 59-octet frame.

• Time on air for one frame: 59 × 8 / 250 = 1.888 seconds.
• Transmitting time allowed in an hour: 3,600 × 0.01 = 36 seconds.
• Frames allowed in an hour: 36 / 1.888, about 19.

So even this long-range network can carry about nineteen small messages an hour from each device at its longest range, which is plenty for a meter and hopeless for anything that streams.

Cellular data

A node can also use the mobile phone network directly, through GPRS or later data services, taught in [New Data Services: HSCSD, GPRS and EDGE]. It needs a SIM and a subscription for each node and draws considerable power, so it is usually used by the gateway rather than by every node: the sensor field talks to the gateway over 802.15.4, and the gateway talks to the task manager over the cellular network.

Worked example: choosing for three applications

The same reasoning chooses for any application: first the range and topology (can every node reach a gateway directly, or must nodes relay?), then the data rate and duty cycle (does the traffic fit?), then energy and cost.

A last classification: how constrained is the node?

RFC 7228 names three classes of constrained device, a useful vocabulary when choosing a stack.

The MSP430F1611 of [Inside a Sensor Node: The Five Units], with 10 kB of RAM and 48 kB of flash, sits between classes 0 and 1: too small for a full Internet protocol stack, which is why sensor networks needed stacks of their own.

Distinctions

What it does not mean

Zigbee and 802.15.4 are not the same thing. 802.15.4 is the radio and MAC; Zigbee is one of several stacks that run on top of it.

A long-range LPWAN is not a replacement for a mesh in every case. It trades data rate and duty cycle for range, and a node that must report every few seconds does not fit.

Wi-Fi is not wrong for sensors; it is wrong for battery sensors. A mains-powered camera or a gateway uses it well.

"Low power" is not a property of a radio alone. Bluetooth LE or 802.15.4 left listening all the time will empty a coin cell quickly. The MAC protocol's duty cycle decides the energy as much as the radio does.

Quick revision

• Text book Table 1.3: GPRS 0.064 to 0.128+ Mbps, 3000+ ft; Wi-Fi 11 to 54 Mbps, 1 to 300+ ft; Bluetooth 0.7 Mbps, 1 to 30+ ft; 802.15.4/ZigBee 0.020 to 0.25 Mbps, 1 to 300+ ft, designed for reliability, power and cost.
• 802.15.4: PHY and MAC only, three bands, 20/40/250 kb/s, 127-byte frames; Zigbee (star, tree, mesh; coordinator = 802.15.4 PAN coordinator) and 6LoWPAN above it.
• Bluetooth LE: from Bluetooth 4.0, coin cells, central and peripherals, star, 27-octet MTU.
• LPWAN: star (Wi-SUN mesh), kilometres, very low rate and duty cycle. LoRaWAN EU 868: channels 868.1/868.2/868.3 MHz, 250 bit/s to 50,000 bit/s; Sigfox ultra narrow band, 100 or 600 baud, DBPSK; NB-IoT licensed, 180 kHz, 60/30 kbit/s peak, 164 dB, over 10 years, about 55,000 devices a cell; Wi-SUN 2 to 3 km, 300 kbit/s.
• 1 per cent duty cycle at 250 bit/s: 1.888 s a frame, 36 s an hour, about 19 frames an hour.
• RFC 7228: Class 0 (much less than 10 KiB RAM), Class 1 (about 10 KiB), Class 2 (about 50 KiB).

Test yourself

1. Compare 802.15.4, Bluetooth, Wi-Fi and GPRS as technologies for a sensor network. From the text book's table: GPRS reaches kilometres at 0.064 to 0.128+ Mbps for wide-area voice and data; Wi-Fi gives 11 to 54 Mbps over up to 300+ feet for enterprise data; Bluetooth gives 0.7 Mbps over up to 30+ feet for cable replacement; 802.15.4 gives 0.020 to 0.25 Mbps over up to 300+ feet and is the only one designed around power, reliability and cost for monitoring and control.

2. What is the relationship between IEEE 802.15.4 and Zigbee? 802.15.4 defines the physical and MAC layers of a low-rate personal area network. Zigbee defines a network layer and application framework on top of it, supporting star, tree and mesh topologies; the Zigbee coordinator is an 802.15.4 PAN coordinator.

3. What do low-power wide-area networks trade, and for what? They accept very low data rates and strict duty cycles in exchange for multi-kilometre links and years of battery life, and they use a star topology with no relaying by the nodes.

4. A LoRaWAN device sends 59-octet frames at 250 bit/s under a 1 per cent duty cycle. How many frames can it send an hour? One frame takes 59 × 8 / 250 = 1.888 s; the device may transmit for 3,600 × 0.01 = 36 s an hour; 36 / 1.888 gives about 19 frames.

5. Which technology would you choose for a wearable heart-rate sensor, and why? Bluetooth Low Energy: it is designed for coin-cell devices, it is in every phone, so the phone serves as the gateway, and a star topology around the phone is all a single wearer needs.

The answer is multi-hop communication: nodes relay for each other. Karl and Willig give the reason exactly: communication over long distances "is only possible using prohibitively high transmission power", and "the use of intermediate nodes as relays can reduce the total required power". Multi-hop also works around obstacles: two nodes on either side of a wall may not reach each other directly but may both reach a third.

Note the careful wording: relays can reduce the power. Whether they do depends on the distances and on the radio, and the next chapter, [Single Hop or Multiple Hops: The Energy Argument Worked Out], works out when they do not. A multi-hop network also pays in delay (every hop adds some) and in load on the relays (a node near the sink forwards everybody's data).

Multiple sources and multiple sinks

Real networks have many of each, and the pattern of traffic between them decides what the routing must do.

With several sinks, a source may report to any one of them (the nearest, to save energy) or to all of them (when every sink needs the data). Several sinks also remove the single point of failure that one sink is, and share out the relaying load that concentrates around it.

The three kinds of mobility

A network's structure changes when something moves, and three different things can move.

1. Node mobility. The sensor nodes themselves move: collars on animals, nodes on vehicles or robots, sensors floating in a river. Karl and Willig add that nodes may also move deliberately, after deployment, to positions where they can do their sensing task better. Routes break as nodes move and must be rebuilt, which is the same problem a mobile ad hoc network faces ([Ad Hoc Networks: MANETs, and How a Sensor Network Differs]).

2. Sink mobility. The sink moves while the nodes stay put: a firefighter walking through a building, a vehicle driving past roadside nodes. Karl and Willig note that in principle this is ordinary node mobility, but it can cause difficulties for protocols that are efficient only in fully static scenarios, because the routes all point towards where the sink was.

3. Event mobility. The phenomenon moves: an intruder, a vehicle, a fire front. The nodes and the sink can all be fixed while the set of nodes that should be reporting changes. In Karl and Willig's words, in tracking applications it is the network's explicit task "to ensure that some form of activity happens in nodes that surround the phenomenon under observation", and ideally what was learned at one place should be available at the next.

Correlated mobility. In any of these, a group can move together: nodes carried by a storm, a river or some other fluid, or a group of people walking together.

Worked example: a bus as a mobile sink

A town council places pollution nodes on 50 lamp-posts along a bus route and lets the bus collect their readings as it passes, instead of building a multi-hop network or a gateway on every post. This is sink mobility: the nodes are fixed, the sink drives by.

The readings to collect. Each node reads every 15 minutes, 96 readings a day, and each reading is 12 bytes, so a node holds 96 × 12 = 1,152 bytes a day.

The time the bus is in range. The node's radio reaches 30 metres, so the bus is in range over 60 metres of road. At 36 km/h the bus travels 36,000 / 3,600 = 10 metres a second, so it is in range for 60 / 10 = 6 seconds.

What 6 seconds can carry. At 250 kbps the radio could move 6 × 250,000 / 8 = 187,500 bytes in that time, if the whole contact were usable. Even allowing for the time to find the bus, for packet overhead and for retransmissions, a day's 1,152 bytes fit comfortably.

What the scenario demands of the protocol. The nodes must be awake, or wake quickly, when the bus comes, which is a problem for a node that sleeps 99 per cent of the time: either the bus announces itself with a signal the node's short listening windows can catch, or the node learns the timetable. And if the bus breaks down, the data waits: a mobile sink trades a network's infrastructure for delay.

Distinctions

What it does not mean

A sink is not always a gateway. It may be an actuator in the field or a handheld that never connects to the Internet.

Multi-hop does not always save energy. It reduces the transmit power per hop; it adds receptions and more transmissions. When the radio's electronics dominate its energy, one long hop can be cheaper, as the next chapter computes.

Event mobility does not require any node to move. The fire moves; the sensors stay where they are.

A mobile sink is not free. It removes relaying and infrastructure and adds delay, plus the problem of waking sleeping nodes when it passes.

Quick revision

• Scenarios (Karl and Willig, chapter 3): sources and sinks; single-hop or multi-hop; multiple sources and sinks; three kinds of mobility.
• Source: provides data. Sink: where data is required: inside the network, an outside device (the firefighter's PDA), or a gateway.
• The sink "is oblivious or not interested in the identity of the sources".
• Multi-hop: needed because long hops need "prohibitively high transmission power"; relays can reduce total power, not always; costs delay and relay load.
• Traffic patterns: many to one (convergecast), one to many, many to many; several sinks remove the single point of failure.
• Mobility: node, sink, event; mobility can be correlated.
• Bus sink: 1,152 bytes a day per node; 6 seconds in range at 36 km/h over 60 m; the radio could carry 187,500 bytes in that time.

Test yourself

1. Explain the three types of mobility in a sensor network, with an example of each. Node mobility: the sensors move, such as collars on animals, and routes between them break. Sink mobility: the collector moves, such as a bus passing roadside nodes, and routes pointing at the sink go stale. Event mobility: the phenomenon moves, such as a tracked vehicle, and the set of nodes that should report changes, even though no node moves.

2. What can a sink be? A node inside the network (another sensor or an actuator), a device outside that communicates with the network directly (a user's handheld), or a gateway to a larger network such as the Internet.

3. Why do sensor networks use multi-hop communication, and what does it cost? Because radio range is limited and reaching far in one hop needs prohibitively high power; relays can reduce the total power and get round obstacles. It costs delay at every hop and a heavy load on the relays near the sink, and it does not always save energy.

4. A bus at 36 km/h passes a node whose radio reaches 30 m. How long is the node in range? Over 60 m of road at 10 m/s: 6 seconds.

5. What is convergecast? The many-to-one traffic pattern in which readings from many sources converge on one sink, typical of data collection networks.

The linear network

Figure 15.1 One long hop, or n short hops with n - 1 receptions

Put n nodes on a line, r metres apart, with the base station just beyond node 1. Take the node farthest out, n × r metres from the base station, and one message of k bits.

Direct: one transmission over n × r metres, and no reception except at the base station:

Multi-hop (MTE): n transmissions of r metres each, and n - 1 receptions by the relays on the way:

When is direct cheaper? When E(direct) < E(MTE). Divide both sides by k and subtract: ε(amp) n² r² - ε(amp) n r² < (2n - 1)E(elec) - E(elec), that is ε(amp) n r² (n - 1) < 2(n - 1) E(elec). For n greater than 1 the factor n - 1 cancels, leaving

With the paper's values, 2 × 50 nJ / 100 pJ is 2 × 500 = 1,000 square metres. So for nodes 10 metres apart, direct transmission is cheaper for any node up to 10 hops out, which is 100 metres from the base station. That is the paper's own finding: when transmission distances are short or the electronics energy is high, "direct transmission is more energy-efficient on a global scale than MTE routing".

The program, across distances

# One long hop or many short ones? The first-order radio model of the LEACH
# paper (HICSS 2000): sending k bits over d metres costs E_ELEC*k + EPS_AMP*k*d^2,
# receiving them costs E_ELEC*k.
E_ELEC = 50e-9     # joules per bit, transmitter or receiver electronics
EPS_AMP = 100e-12  # joules per bit per square metre, transmit amplifier
K = 2000           # bits in one message, as in the paper

def tx(d):
    return E_ELEC * K + EPS_AMP * K * d * d

def rx():
    return E_ELEC * K

def direct(n, r):
    """The node n hops out sends straight to the base station, n*r metres away."""
    return tx(n * r)

def multihop(n, r):
    """Minimum transmission energy routing: n hops of r metres, n - 1 receptions."""
    return n * tx(r) + (n - 1) * rx()

print("Direct is cheaper exactly when n * r^2 < 2 * E_ELEC / EPS_AMP = %.0f m^2"
      % (2 * E_ELEC / EPS_AMP))
print()
print("  r (m)   n   n*r^2   direct (uJ)   multi-hop (uJ)   cheaper")
for r in (5, 10, 20, 40):
    for n in (2, 5, 10):
        d, m = round(direct(n, r) * 1e6, 1), round(multihop(n, r) * 1e6, 1)
        verdict = "equal" if d == m else ("direct" if d < m else "multi-hop")
        print("%7d %3d %7d %13.1f %16.1f   %s" % (r, n, n * r * r, d, m, verdict))

# Who pays? With multi-hop on a line of 5 nodes 20 m apart, node 1 (next to the
# base station) sends its own message and relays the other four.
print()
print("energy per node for one message from every node, n = 5, r = 20 m:")
n, r = 5, 20
for i in range(1, n + 1):
    relays = n - i                      # messages from nodes farther out
    energy = (relays + 1) * tx(r) + relays * rx()
    print("  node %d: %6.1f uJ (sends %d, receives %d)"
          % (i, energy * 1e6, relays + 1, relays))

Direct is cheaper exactly when n * r^2 < 2 * E_ELEC / EPS_AMP = 1000 m^2

  r (m)   n   n*r^2   direct (uJ)   multi-hop (uJ)   cheaper
      5   2      50         120.0            310.0   direct
      5   5     125         225.0            925.0   direct
      5  10     250         600.0           1950.0   direct
     10   2     200         180.0            340.0   direct
     10   5     500         600.0           1000.0   direct
     10  10    1000        2100.0           2100.0   equal
     20   2     800         420.0            460.0   direct
     20   5    2000        2100.0           1300.0   multi-hop
     20  10    4000        8100.0           2700.0   multi-hop
     40   2    3200        1380.0            940.0   multi-hop
     40   5    8000        8100.0           2500.0   multi-hop
     40  10   16000       32100.0           5100.0   multi-hop

energy per node for one message from every node, n = 5, r = 20 m:
  node 1: 1300.0 uJ (sends 5, receives 4)
  node 2: 1020.0 uJ (sends 4, receives 3)
  node 3:  740.0 uJ (sends 3, receives 2)
  node 4:  460.0 uJ (sends 2, receives 1)
  node 5:  180.0 uJ (sends 1, receives 0)

Read the verdict column. Every row with n × r² below 1,000 says direct; every row above it says multi-hop; the row at exactly 1,000 says equal. The algebra and the program agree, which is the point of running it. With nodes 5 metres apart, a node 10 hops out spends 600 microjoules sending directly against 1,950 by multi-hop: over three times as much for the "energy-saving" route.

Read the last block. On a line of 5 nodes 20 metres apart, one message from every node costs node 1, next to the base station, 1,300 microjoules and node 5 only 180: more than seven times as much. Node 1 dies first, then node 2, and when they are gone the rest of the line is cut off. This is the energy hole around a sink, and the LEACH paper observed it in its simulations: with MTE routing the nodes closest to the base station die first, while with direct transmission it is the farthest ones.

A better model, and the best number of hops

Near the ground, and at longer distances, loss grows faster than d². The same authors' journal paper of 2002 uses two regimes: free space, ε(fs) × d², up to a crossover distance, and multipath, ε(mp) × d⁴, beyond it, with ε(fs) = 10 pJ/bit/m² and ε(mp) = 0.0013 pJ/bit/m⁴. The crossover is where the two are equal, the square root of ε(fs) / ε(mp), about 87.7 metres.

# The LEACH journal model (2002): free-space loss (d^2) below a crossover
# distance d0, multipath loss (d^4) beyond it.
E_ELEC = 50e-9       # joules per bit
EPS_FS = 10e-12      # joules per bit per square metre
EPS_MP = 0.0013e-12  # joules per bit per metre to the fourth
K = 2000             # bits in one message
D0 = (EPS_FS / EPS_MP) ** 0.5

def tx(d):
    amp = EPS_FS * d ** 2 if d < D0 else EPS_MP * d ** 4
    return E_ELEC * K + amp * K

def chain(total, n):
    """Energy to carry one message over `total` metres in n equal hops."""
    return n * tx(total / n) + (n - 1) * E_ELEC * K

print("crossover distance d0 = %.1f m" % D0)
print()
print("distance   1 hop (uJ)   2 hops   4 hops   8 hops")
for total in (50, 100, 200, 400):
    row = [chain(total, n) * 1e6 for n in (1, 2, 4, 8)]
    print("%6d m %12.1f %8.1f %8.1f %8.1f" % (total, *row))

crossover distance d0 = 87.7 m

distance   1 hop (uJ)   2 hops   4 hops   8 hops
    50 m        150.0    325.0    712.5   1506.2
   100 m        360.0    400.0    750.0   1525.0
   200 m       4260.0    820.0    900.0   1600.0
   400 m      66660.0   8620.0   1740.0   1900.0

Each row has a best entry, and it moves right as the distance grows. Over 50 and 100 metres, one hop is cheapest. Over 200 metres, two hops (820 microjoules) beat one (4,260), because the single hop has crossed into the d⁴ regime. Over 400 metres, four hops (1,740) are best, about 38 times cheaper than one, and eight hops are worse than four (1,900), because the extra receptions and electronics outweigh the little amplifier energy left to save.

So the full answer is neither "single hop" nor "multi-hop": there is an optimal hop length, set by the ratio of the electronics energy to the amplifier energy and by how fast the loss grows with distance.

Distinctions

What it does not mean

Multi-hop is not always the energy-saving choice. With the LEACH constants and hops of 10 metres, sending directly is cheaper for every node within 100 metres of the base station. The claim needs its condition.

More hops are not always better, even when multi-hop wins. The two-regime run found four hops best over 400 metres and eight hops worse.

Saving total energy is not the same as a long network lifetime. Multi-hop can use less energy in total and still kill the nodes next to the sink early, because it concentrates the relaying on them. Lifetime is about the worst node, which [Optimization Goals: Quality of Service, Energy Efficiency and Lifetime] takes up.

The model is not a real radio. It ignores listening, collisions, retransmissions and the MAC's overhead, and real radios often cannot vary their power continuously. It is a tool for reasoning about the trade-off, not a prediction to the microjoule.

Quick revision

• First-order model (LEACH 2000): transmit E(elec)k + ε(amp)k d², receive E(elec)k; E(elec) = 50 nJ/bit, ε(amp) = 100 pJ/bit/m².
• Line of n nodes r apart: E(direct) = k(E(elec) + ε(amp) n² r²); E(MTE) = k((2n - 1)E(elec) + ε(amp) n r²).
• Direct is cheaper when n r² < 2 E(elec) / ε(amp), which is 1,000 m² with these constants.
• Program: r = 5 m, n = 10: 600 against 1,950 microjoules, direct wins.
• Energy hole: n = 5, r = 20 m, node 1 spends 1,300 microjoules, node 5 180; MTE kills the nodes near the base station first.
• Two-regime model (2002): ε(fs) = 10 pJ/bit/m², ε(mp) = 0.0013 pJ/bit/m⁴, crossover about 87.7 m; best hops: 1 up to 100 m, 2 at 200 m, 4 at 400 m (8 is worse).

Test yourself

1. Write the first-order radio model and explain its terms. Transmitting k bits over d metres costs E(elec) × k + ε(amp) × k × d²; receiving costs E(elec) × k. E(elec) is the energy per bit of the transmitter or receiver electronics and ε(amp) the energy per bit per square metre of the transmit amplifier. LEACH used 50 nJ/bit and 100 pJ/bit/m².

2. Derive the condition under which direct transmission uses less energy than multi-hop routing on a line of n nodes spaced r apart. E(direct) = k(E(elec) + ε(amp) n² r²) and E(MTE) = k((2n - 1)E(elec) + ε(amp) n r²). Direct < MTE gives ε(amp) n r² (n - 1) < 2(n - 1)E(elec), so n r² < 2 E(elec) / ε(amp).

3. With E(elec) = 50 nJ/bit and ε(amp) = 100 pJ/bit/m², up to how many hops of 10 metres is direct transmission cheaper? 2 × 50 / 0.1 = 1,000 m², so n × 100 < 1,000, n < 10: for any node fewer than 10 hops out; at exactly 10 hops the two are equal.

4. Why do the nodes nearest the base station die first under multi-hop routing? Because they relay every message from the nodes farther out. On a line of five nodes, node 1 sends five messages and receives four for every one message node 5 sends.

5. With loss growing as d⁴ beyond about 88 metres, how many hops are best for 400 metres, and why not more? Four hops, at about 1,740 microjoules. Eight hops cost about 1,900, because each extra hop adds a transmission's and a reception's electronics energy while the amplifier energy left to save is small.

Goal 2: energy efficiency

Energy is spent to get information, so the measures relate the two.

• Energy per correctly received bit: the total energy spent in the network, divided by the number of bits that reached their destination intact. It counts every retransmission, every relay and every idle listen. It suits periodic data collection.
• Energy per reported (unique) event: the energy spent divided by the number of distinct events reported. It suits event detection, where many nodes may report the same fire and only the first report counts as information.
• The delay and energy trade-off: a network can nearly always save energy by waiting (sleeping longer, collecting several readings into one packet), so energy efficiency is usually stated at a given delay. An alarm may be allowed a second; a weekly report a week.

Goal 3: network lifetime, and why it must be defined

Karl and Willig call lifetime "a very important figure of merit" and note that "the precise definition of lifetime depends on the application at hand". The standard definitions:

1. Time to first node death. The network is considered dead when the first node runs out of energy. The simplest, and the most pessimistic.
2. Network half-life. The time until 50 per cent (or another fixed fraction) of the nodes have failed.
3. Time to partition. The time until the network splits into two or more parts that cannot reach each other, so that some live nodes can no longer reach the sink.
4. Time to loss of coverage. The time when, for the first time, some point of the observed region is no longer covered by any sensor node.
5. Time to failure of the first event notification. The time when, for the first time, an event somewhere in the region could not be reported to the sink, because no node covering it is alive or because the ones covering it cannot reach the sink.

Each suits a different application. A network that must watch every point (a perimeter intrusion system) is dead at loss of coverage; one that only needs statistics (an average soil moisture) can carry on to its half-life; one whose nodes are all equally important is dead at the first node death.

Worked example: five lifetimes for one network

A 5 by 5 grid of 25 nodes, 10 metres apart, reports to a sink beside the middle of one edge. Nodes within 15 metres are neighbours. Every round each node sends one reading to the sink by the fewest hops, relays pay to receive and resend, and a node that has been cut off from the sink still wastes one transmission trying. Each node starts with 0.5 J, as in the LEACH simulations of [Single Hop or Multiple Hops: The Energy Argument Worked Out], and the radio follows the same first-order model. The program measures when each definition says the network died.

# Five definitions of network lifetime, measured on one simulated network.
# 25 nodes on a 5 x 5 grid 10 m apart; the sink sits beside the middle of one
# edge. Nodes within 15 m of each other (diagonals included) are neighbours.
# Every round each node sends one 2000-bit reading along a fewest-hops path to
# the sink, and relays pay to receive and resend. A node cut off from the sink
# still transmits its reading once, uselessly. Radio: the LEACH first-order model.
import math
from collections import deque

E_ELEC, EPS, K, E0 = 50e-9, 100e-12, 2000, 0.5   # J/bit, J/bit/m^2, bits, J
NODES = [(10 * x, 10 * y) for x in range(5) for y in range(5)]
SINK = (-10, 20)
RANGE = 15
energy = {n: E0 for n in NODES}

def tx(a, b):
    return E_ELEC * K + EPS * K * math.dist(a, b) ** 2

def next_hops(alive):
    """Breadth-first search from the sink: each connected node's next hop."""
    parent, queue = {}, deque([SINK])
    while queue:
        p = queue.popleft()
        for q in sorted(alive):
            if q not in parent and math.dist(p, q) <= RANGE:
                parent[q] = p
                queue.append(q)
    return parent

def covered(point, sensors, rs=15):
    return any(math.dist(point, s) <= rs for s in sensors)

found, rnd = {}, 0
while len(found) < 5:
    rnd += 1
    alive = {n for n in NODES if energy[n] > 0}
    parent = next_hops(alive)
    checks = {
        "time to first node death": len(alive) < len(NODES),
        "time to partition": len(parent) < len(alive),
        "time to failure of first event notification":
            not all(covered(p, parent) for p in NODES),
        "time to loss of coverage": not all(covered(p, alive) for p in NODES),
        "network half-life": len(alive) <= len(NODES) // 2,
    }
    for name, happened in checks.items():
        if happened and name not in found:
            found[name] = rnd
    for n in alive:
        if n in parent:                          # carry the reading to the sink
            hop = n
            while hop != SINK:
                energy[hop] -= tx(hop, parent[hop])
                if parent[hop] != SINK:
                    energy[parent[hop]] -= E_ELEC * K
                hop = parent[hop]
        else:                                    # cut off: one wasted attempt
            energy[n] -= E_ELEC * K + EPS * K * RANGE ** 2

for name, r in sorted(found.items(), key=lambda item: item[1]):
    print("%-45s round %d" % (name, r))

time to first node death                      round 114
time to partition                             round 280
time to failure of first event notification   round 280
network half-life                             round 2998
time to loss of coverage                      round 3017

The same network, the same energy, and its "lifetime" is anything from 114 rounds to 3,017, a factor of more than twenty-six. Four things in the output repay attention.

The first death comes early because the fewest-hops tree is lopsided: of the three nodes beside the sink, one carries 19 of the 25 readings every round and the other two carry 3 each (a separate count of the tree confirms it). But the network keeps working: the other two carry on, and the routes are rebuilt around the dead node.

Partition comes at round 280, when all three nodes beside the sink are dead. From then on, however much energy the other nodes have, nothing reaches the sink. For a data collection network this, not the half-life, is the real end.

Failure of the first event notification comes at the same moment as partition. Here the sensing range equals the radio range, so the cut-off nodes' area is covered by no connected node from the instant they are cut off. With a larger sensing range the two could come apart.

Half-life and loss of coverage come thousands of rounds later, because cut-off nodes spend almost nothing and live on, uselessly. A designer who quoted the half-life would be describing a network that had delivered nothing for over 2,700 rounds.

So an answer that says the network lifetime is 2,998 rounds without saying which definition is not an answer.

Distinctions

What it does not mean

Quality of service here is not bandwidth and jitter. It is detection probability, delay of an event report, accuracy of a map or a track.

Energy efficiency is not the same as low power. A node that draws little but delivers nothing is not efficient; the measure is energy per useful result.

Network lifetime is not one number until a definition is chosen. The simulation gave five numbers from one network.

A long half-life does not mean a working network. Half the nodes can be alive and cut off from the sink.

Quick revision

• Goals (Karl and Willig 3.2): quality of service, energy efficiency, lifetime, scalability, robustness.
• QoS measures: event detection or reporting probability, event classification error, event detection delay, missing reports, approximation accuracy, tracking accuracy. "The packet delivery ratio is an insufficient metric."
• Energy measures: energy per correctly received bit; energy per reported unique event; the delay and energy trade-off.
• Lifetime: first node death, half-life, partition, loss of coverage, failure of the first event notification.
• Simulation, 25 nodes, 0.5 J each: first death 114, partition 280, first failed notification 280, half-life 2,998, loss of coverage 3,017.

Test yourself

1. What are the optimization goals of a wireless sensor network? Quality of service (measured on the information: detection probability, classification error, detection delay, missing reports, approximation and tracking accuracy), energy efficiency (energy per correctly received bit or per unique event, traded against delay), network lifetime, scalability and robustness.

2. Give five definitions of network lifetime. Time to first node death; network half-life (half the nodes failed); time to partition (some live nodes can no longer reach the sink); time to loss of coverage (some point no longer covered); time to failure of the first event notification (some event cannot be reported).

3. Why is the packet delivery ratio insufficient as a quality measure for a sensor network? Because the user wants information, not packets. What matters is how much and how good the information at the sink is: whether events are detected and reported, how accurate the map or track is. A network can lose many packets and still report every event, or deliver most packets and miss the important ones.

4. In the simulation, why did the network's half-life come about 2,700 rounds after it was partitioned? Because once the nodes beside the sink died, the other nodes were cut off and spent almost no energy, so they stayed alive for thousands of rounds while delivering nothing. The half-life counts them as alive.

5. Which lifetime definition would you use for a perimeter intrusion detection network, and why? Time to loss of coverage, or time to failure of the first event notification: the network has failed as soon as an intruder could cross some point without being detected and reported.

Goal 5: robustness

A network is robust if its performance degrades gracefully, not suddenly, when things go wrong: nodes fail or run flat, links fade in and out, obstacles appear, interference rises, or nodes move. Karl and Willig's requirements of fault tolerance (tolerating node failures through redundant deployment) and maintainability (monitoring its own health and adapting, for example by giving lower quality when energy runs short) are two sides of it.

Graceful degradation is the phrase to use. When 10 per cent of the nodes fail, a robust network loses a little coverage or accuracy; a brittle one stops reporting altogether. The simulation in the previous chapter showed a brittle point: when the three nodes beside the sink died, the whole network was cut off at once. A more robust design gives the sink more neighbours, or uses several sinks, or rotates the heavy relaying role.

The measures used to compare protocols

These are the figures of merit that simulations and experiments report. Each has a definition that is worth writing exactly.

1. Throughput: the amount of data delivered to its destinations per unit time, in bits per second. Only data that arrives counts.
2. Goodput: throughput counting only the useful payload, not headers, retransmitted duplicates or control packets.
3. Packet delivery ratio (PDR): packets received at their destinations divided by packets sent by their sources, usually as a percentage.
4. End-to-end delay: for each delivered packet, the time it was received less the time it was sent; reported as an average (and often also a maximum or a percentile), over delivered packets only.
5. Jitter: the variation of the delay from packet to packet, for example as the spread between the smallest and largest delay, or their standard deviation.
6. Control overhead, or routing overhead: the control packets (route requests, replies, errors, beacons) a protocol sends, often normalised as control packets per data packet delivered.
7. Energy per delivered packet (or per correctly received bit): total energy spent divided by what was delivered, the energy measure of [Optimization Goals: Quality of Service, Energy Efficiency and Lifetime].

Worked example: measuring a small trace

A source sends ten readings of 64 bytes, one a second from time 0 to time 9 seconds, to a sink four hops away. The routing protocol sent 30 control packets during the run. The trace records what arrived.

Packet delivery ratio. 8 of 10 arrived: 8 / 10 = 0.8, so the PDR is 80 per cent.

Average end-to-end delay. Over the 8 delivered packets only: 426 / 8 = 53.25 milliseconds. (Averaging over all ten, with the lost ones counted as zero, would be a mistake: it would make losses look like good performance.)

Jitter. The delays run from 38 to 120 milliseconds, a spread of 120 - 38 = 82 milliseconds, almost all of it from packet 7. One slow packet (perhaps retransmitted, or held in a queue) dominates the jitter, and it also pulls the average up: without it the other seven average 306 / 7, about 43.7 milliseconds. That is why reports give a percentile or the median beside the average.

Throughput. 8 packets of 64 bytes arrived, which is 8 × 64 × 8 = 4,096 bits, over the 10-second run: 4,096 / 10 = 409.6 bits per second.

Control overhead. 30 control packets for 8 delivered data packets: 30 / 8 = 3.75 control packets per delivered packet. A protocol that delivered the same 8 with 12 control packets would have an overhead of 1.5, and if the two were otherwise equal it would be the better one for a battery-powered network, because every control packet costs energy.

Distinctions

What it does not mean

A high packet delivery ratio does not mean a good sensor network. It is the measure Karl and Willig call insufficient; it says nothing about whether the right packets, the alarms, arrived.

Delay is not averaged over lost packets. Only delivered packets have a delay.

Throughput is not the radio's data rate. A 250 kbps radio in the trace delivered 409.6 bits per second, because the application sent little and some of it was lost.

Scalability is not only about the number of nodes. Density and area matter as much, and a protocol can scale in one and fail in another.

Low overhead is not always better. A protocol that sends almost no control packets may deliver less, or react slowly when routes break. Overhead must be read beside delivery and delay.

Quick revision

• Scalability: keep performance as nodes, density and area grow; the guideline is locality (state only about direct neighbours) and scoping (a query's cost should grow with the region asked about, not the network).
• Robustness: graceful degradation under failures, fading, interference and movement; fault tolerance by redundancy; maintainability.
• Measures: throughput, goodput, packet delivery ratio, end-to-end delay (over delivered packets), jitter, control overhead, energy per delivered packet.
• Trace: PDR 80 per cent; average delay 53.25 ms; jitter 82 ms spread; throughput 409.6 bit/s; overhead 3.75 control packets per delivered packet.

Test yourself

1. Define scalability and robustness as optimization goals of a WSN. Scalability: the network keeps its performance as the number of nodes, the density or the area grows, which requires protocols whose state and overhead grow slowly, typically by locality. Robustness: performance degrades gracefully when nodes fail, links fluctuate or the topology changes.

2. Define packet delivery ratio, end-to-end delay and throughput. PDR: packets received at their destinations divided by packets sent. End-to-end delay: receive time minus send time for each delivered packet, averaged over delivered packets. Throughput: data delivered per unit time, in bits per second.

3. Ten packets are sent and eight arrive with delays totalling 426 ms. Give the PDR and the average delay. PDR 8 / 10 = 0.8, which is 80 per cent; average delay 426 / 8 = 53.25 ms.

4. Why is flooding a query to the whole network not scalable, and what is the alternative? Its cost grows with the number of nodes: every node transmits the query once. Scoping the query to the region of interest, by location or by attribute, makes the cost grow with the region instead.

5. What is control overhead, and why does it matter more in a sensor network than on the Internet? The control packets a protocol sends (route requests, replies, errors, beacons), often measured per data packet delivered. In a sensor network every transmission costs battery energy, so overhead directly shortens the network's lifetime.

With r(s) = 10 metres, the spacing must be at most about 14.14 metres. The grid is connected if neighbouring nodes are within radio range, s at most r(c), which is easily met when r(c) is 20 metres.

Zhang and Hou's theorem

Zhang and Hou proved the result that links the two questions: "if the radio range is at least twice of the sensing range, a complete coverage of a convex area implies connectivity among the working set of nodes". They also showed that the condition is necessary: with r(c) below 2 r(s) there are coverings that are not connected.

The reason is short enough to write in an answer. If every point is covered, take any two nodes whose sensing discs touch or overlap; their centres are at most 2 r(s) apart, so with r(c) at least 2 r(s) they can talk directly. In a convex field fully covered by discs, the discs form an unbroken chain from any node to any other, so every node can reach every other, and the sink in particular.

Its practical meaning is large: with r(c) at least 2 r(s), a designer need only ensure coverage, and connectivity comes free. The program below uses exactly that ratio, r(s) = 10 metres and r(c) = 20 metres.

The practical's experiment

The program places 49 and 64 nodes on grids, and 49, 64, 100 and 150 nodes at random in twenty different layouts each, in a 100 metre square field. Coverage is sampled at 2,500 points, one every 2 metres; connectivity is tested by searching the graph of links no longer than 20 metres.

Figure 18.1 The same number of nodes, planned and scattered: the program's first random layout

# Grid against random deployment: coverage and connectivity.
# A 100 m by 100 m field, sensing radius 10 m, radio range 20 m (twice it).
import math
import random

SIDE, RS, RC = 100.0, 10.0, 20.0
POINTS = [(x + 1.0, y + 1.0) for x in range(0, 100, 2) for y in range(0, 100, 2)]

def coverage(nodes):
    """Fraction of 2,500 sample points within RS of at least one node."""
    hit = sum(1 for p in POINTS if any(math.dist(p, n) <= RS for n in nodes))
    return hit / len(POINTS)

def connected(nodes):
    """Is every node reachable from the first, over links of at most RC?"""
    seen, stack = {0}, [0]
    while stack:
        i = stack.pop()
        for j, n in enumerate(nodes):
            if j not in seen and math.dist(nodes[i], n) <= RC:
                seen.add(j)
                stack.append(j)
    return len(seen) == len(nodes)

def grid(k):
    s = SIDE / k                                   # spacing between rows
    return [(s / 2 + s * i, s / 2 + s * j) for i in range(k) for j in range(k)]

for k in (7, 8):
    g, s = grid(k), SIDE / k
    worst = s / math.sqrt(2)                       # a cell's centre to its corners
    print("grid %d x %d = %d nodes, spacing %.2f m: sampled coverage %.4f, connected %s"
          % (k, k, len(g), s, coverage(g), connected(g)))
    print("   farthest point from any node: %.2f m, so every point is covered: %s"
          % (worst, worst <= RS))

print()
print("random, 20 layouts each:")
for n in (49, 64, 100, 150):
    covs, links = [], 0
    for seed in range(20):
        rnd = random.Random(seed)
        nodes = [(rnd.uniform(0, SIDE), rnd.uniform(0, SIDE)) for _ in range(n)]
        covs.append(coverage(nodes))
        links += connected(nodes)
    ideal = 1 - math.exp(-n * math.pi * RS ** 2 / SIDE ** 2)
    print("  %3d nodes: mean coverage %.4f (formula %.4f), worst %.4f, connected in %d of 20"
          % (n, sum(covs) / 20, ideal, min(covs), links))

grid 7 x 7 = 49 nodes, spacing 14.29 m: sampled coverage 1.0000, connected True
   farthest point from any node: 10.10 m, so every point is covered: False
grid 8 x 8 = 64 nodes, spacing 12.50 m: sampled coverage 1.0000, connected True
   farthest point from any node: 8.84 m, so every point is covered: True

random, 20 layouts each:
   49 nodes: mean coverage 0.7502 (formula 0.7855), worst 0.6940, connected in 3 of 20
   64 nodes: mean coverage 0.8369 (formula 0.8661), worst 0.7980, connected in 12 of 20
  100 nodes: mean coverage 0.9365 (formula 0.9568), worst 0.9024, connected in 18 of 20
  150 nodes: mean coverage 0.9841 (formula 0.9910), worst 0.9704, connected in 20 of 20

Reading the output

The sampled 7 by 7 grid looks perfect and is not. Its spacing is 100 / 7, about 14.29 metres, just over the 14.14-metre limit, so the centre of every cell is 10.10 metres from the nearest node and a tiny patch around it is uncovered. The 2-metre sampling never lands in those patches and reports 1.0000. The exact check on the next line says what the sampling cannot. A coverage figure is only as good as the points it was measured at, which matters in the practical: a simulation that samples coarsely can pass a layout with holes. The 8 by 8 grid, at 12.5-metre spacing, covers every point.

Random deployment needs well over twice as many nodes, and still leaves holes. With 49 random nodes, the mean coverage is about 75 per cent and the worst layout under 70 per cent; the grid of the same 49 nodes misses almost nothing. Random layouts reach an average of about 98 per cent only at 150 nodes, and even then the worst of twenty layouts leaves about 3 per cent uncovered.

The formula is optimistic, and the program shows why. 1 - e^(-N π r(s)² / A) assumes nodes scattered over an unbounded plane. In a real field, a node near the edge wastes part of its disc outside the field, so the measured coverage is always a little below the formula: 0.7502 against 0.7855 at 49 nodes. A student who quoted the formula for a small field would overstate the coverage.

Connectivity improves with density as well. With 49 random nodes, only 3 of the 20 layouts are fully connected: some node is always stranded more than 20 metres from all the others. At 150 nodes all 20 are connected. The grids, with neighbours 12.5 to 14.3 metres apart, are always connected, as the theorem promises for a fully covered field.

Distinctions

What it does not mean

A sampled coverage of 100 per cent is not proof of full coverage. The 7 by 7 grid had holes the samples missed.

Random deployment is not inferior design. It is often the only possible design; the answer is to deploy more nodes and to let redundant ones sleep, which [Energy Efficiency in Ad Hoc Networks: Where the Energy Goes] discusses.

Coverage does not imply connectivity in general. It does when r(c) is at least 2 r(s) and the area is convex. With a shorter radio range, a fully covered field can be disconnected.

The formula is not the answer for a real field. It ignores the edges, and it describes an average: any one layout can be much worse, as the worst-case column showed.

Quick revision

• Coverage: fraction of the field within r(s) of some working node. Connectivity: every node has a path to the sink over links of at most r(c).
• Grid: planned; square grid covers fully when s is at most 1.414 r(s) (14.14 m for r(s) = 10 m). Random: scattered; uneven; needs many more nodes.
• Random coverage formula, ignoring edges: 1 - e^(-N π r(s)² / A).
• Zhang and Hou: if r(c) is at least 2 r(s), full coverage of a convex area implies connectivity, and the condition is necessary.
• Program (100 m field, r(s) = 10 m, r(c) = 20 m): 7 by 7 grid has tiny holes (cell centres 10.10 m from nodes), which 2 m sampling missed; 8 by 8 covers fully; random 49 nodes about 75 per cent, 150 nodes about 98 per cent; connected in 3 of 20 layouts at 49 nodes, 20 of 20 at 150.

Test yourself

1. Define coverage and connectivity. Coverage: the fraction of the field lying within the sensing range of at least one working node. Connectivity: every node can reach the sink by a multi-hop path over links no longer than the communication range.

2. On a square grid, what spacing covers the whole field for a sensing range r(s)? At most the square root of 2 times r(s), about 1.414 r(s), because the farthest point from every node is a cell's centre, whose squared distance from its corners is (s / 2)² + (s / 2)², that is s² / 2.

3. State Zhang and Hou's result on coverage and connectivity, and give its practical meaning. If the radio range is at least twice the sensing range, complete coverage of a convex area implies connectivity; the condition is also necessary. A designer can then concentrate on coverage and get connectivity free.

4. Why is measured coverage in a real field lower than 1 - e^(-N π r² / A)? The formula assumes an unbounded plane. In a bounded field, nodes near the edges waste part of their sensing discs outside the field, so less of the field is covered than the formula predicts.

5. Compare grid and random deployment of 49 nodes in the simulation. The grid covered almost all the field (with tiny holes at cell centres because its spacing slightly exceeded 1.414 r(s)) and was always connected. Random layouts covered about 75 per cent on average, under 70 per cent at worst, and were fully connected in only 3 of 20 layouts.

How to aggregate correctly. TinyDB, the query system for sensor networks described in [Middleware Approaches, and TinyDB], implements every aggregate through three functions:

1. an initializer i, which turns one reading into a partial state record;
2. a merging function f, which combines two partial state records into one; it must be commutative and associative, so that the order in which records meet does not matter;
3. an evaluator e, which turns the final record at the sink into the answer.

For AVERAGE the partial state record is the pair (SUM, COUNT): i(x) = (x, 1), f adds the pairs, and e(S, C) = S / C. MAX needs only the largest value so far; COUNT only the count.

Not everything aggregates. An aggregate whose partial state stays small (SUM, COUNT, MAX, AVERAGE) saves a lot. The median does not: to merge two medians you need all the values behind them, so its "partial state" is the whole list and nothing is saved.

A caution the survey adds. Akyildiz and colleagues give it as a design principle of the network layer that data aggregation is useful only when it does not hinder the collaborative effort of the nodes. Aggregation delays data (a node must wait for its children), and it destroys detail the sink might have needed. An alarm must never wait to be averaged.

Distributed source coding and compression

Neighbouring nodes see similar values: two temperature sensors a metre apart read almost the same. Their data is therefore correlated, and a network can send less than the sum of what they measure. The simplest version: send the first node's reading in full and the second as a small difference from it. More advanced schemes let each node compress its own readings knowing only that its neighbours' are correlated, without exchanging them first.

Distributed and collaborative signal processing

Some questions need several nodes' raw signals at once. The direction of a sound, the position of a vehicle, whether a seismic tremor is an earthquake: each single node sees too little. Nodes near the event exchange their signals (or features extracted from them), compute the answer together, and send only the answer. This is the "collaboration" in Karl and Willig's required mechanism: "several sensors have to collaborate to detect an event".

Mobile code and agent-based networking

Instead of moving data to where the program is, move the program to where the data is. A small piece of code, an agent, travels from node to node, processes the data it finds, and carries a result on. It suits tasks whose processing is needed only in one area, such as following a target.

Principle 3: adaptive fidelity and accuracy

Fidelity is how accurate or detailed a result is. A network can usually produce a better result by spending more energy: more nodes sampling, more often, with more retransmissions. Adaptive fidelity means choosing that trade-off deliberately and changing it as conditions change: sample every ten minutes when nothing is happening and every ten seconds when a fire is suspected; let most nodes sleep until an event is detected, then wake more to track it; give lower quality when batteries run low. It is Karl and Willig's "exploit trade-offs" mechanism made into a design rule.

The sink's part in aggregation

The practical asks for a scenario with "multiple sensor motes and a base station to study data aggregation and sink node operation". The sink is where aggregation ends: it receives the partial state records from its children, merges them with f, and applies the evaluator e to produce the answer, which it passes to the gateway and the user. In a TinyDB-style system it also starts each round: it sends the query out, and each epoch (the period of one round of sampling) every node samples, merges its children's records with its own, and forwards one record.

Worked example: aggregating an average on a tree

Fifteen nodes report temperatures to a sink along the tree in the figure. Each node's reading is printed beneath it.

Figure 19.1 The collection tree of the worked example

The program counts the transmissions with and without aggregation, computes the average the TinyDB way, and then makes the mistake a first program usually makes.

# In-network aggregation on a collection tree, TinyDB style.
# Node -> parent (0 is the sink), and each node's temperature reading.
PARENT = {1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 2, 7: 2, 8: 3, 9: 3,
          10: 4, 11: 4, 12: 5, 13: 6, 14: 8, 15: 8}
READING = {1: 31, 2: 29, 3: 33, 4: 30, 5: 28, 6: 35, 7: 32, 8: 27,
           9: 30, 10: 34, 11: 29, 12: 31, 13: 36, 14: 28, 15: 30}

def depth(n):
    return 0 if n == 0 else 1 + depth(PARENT[n])

def children(n):
    return sorted(c for c, p in PARENT.items() if p == n)

# Without aggregation every reading is forwarded hop by hop to the sink.
raw = sum(depth(n) for n in PARENT)
print("transmissions without aggregation:", raw)
print("transmissions with aggregation:   ", len(PARENT), "(one record per node)")

# TinyDB's AVERAGE: initializer i(x) = <x, 1>, merge f adds the pairs,
# evaluator e(<S, C>) = S / C.
def record(n):
    s, c = READING[n], 1
    for k in children(n):
        ks, kc = record(k)
        s, c = s + ks, c + kc
    return s, c

s, c = 0, 0
for k in children(0):
    ks, kc = record(k)
    s, c = s + ks, c + kc
print()
print("partial state at the sink: SUM = %d, COUNT = %d, AVERAGE = %.4f" % (s, c, s / c))

# The mistake: each node forwards the plain average of itself and its children.
def naive(n):
    values = [READING[n]] + [naive(k) for k in children(n)]
    return sum(values) / len(values)

wrong = sum(naive(k) for k in children(0)) / len(children(0))
print("averaging averages instead gives:      %.4f" % wrong)
print("MAX needs no count: %d" % max(READING.values()))

transmissions without aggregation: 33
transmissions with aggregation:    15 (one record per node)

partial state at the sink: SUM = 463, COUNT = 15, AVERAGE = 30.8667
averaging averages instead gives:      31.0370
MAX needs no count: 36

Transmissions. Without aggregation, each reading travels as many hops as its node's depth: three nodes at depth 1, six at depth 2 and six at depth 3 give 3 + 12 + 18 = 33 transmissions. With aggregation, each node sends one record: 15. The saving grows with the depth of the tree, and it is largest for the nodes near the sink, which would otherwise carry everyone's readings.

The right average. The sink receives (SUM, COUNT) records and ends with SUM = 463 and COUNT = 15, so the average is 463 / 15, about 30.8667 degrees.

The wrong one. If each node forwards only the plain average of itself and its children, the sink gets 31.0370. The error is that a subtree of five nodes and a subtree of one are given equal weight. On this tree the error is small; on a lopsided tree it can be large, and nothing in the output warns that it is wrong. This is why the partial state record carries the COUNT.

Distinctions

What it does not mean

In-network processing is not free. It costs processing energy (small next to the radio's), delay while nodes wait for their children, and the loss of detail.

An average of averages is not the average. Use (SUM, COUNT).

Distributed does not mean random. Nodes follow the same protocol; what they lack is a central authority and a global view.

Adaptive fidelity is not lower quality. It is the right quality for the moment, higher when it matters and lower when it does not.

Quick revision

• Principles (Karl and Willig 3.3), part one: distributed organisation; in-network processing (aggregation, distributed source coding and compression, distributed and collaborative signal processing, mobile code); adaptive fidelity and accuracy.
• TinyDB aggregates: initializer, merging function (commutative, associative), evaluator; AVERAGE's partial state is (SUM, COUNT); MEDIAN does not aggregate.
• Aggregation is useful only when it does not hinder collaboration; alarms are not averaged.
• The sink merges the last records, evaluates, and starts each epoch.
• Worked tree of 15: 33 transmissions without aggregation, 15 with; average 463 / 15, about 30.8667; averaging averages gives 31.0370, wrong.

Test yourself

1. What is in-network processing, and name its four forms. Processing data inside the network rather than only at the edge, so less is transmitted: aggregation; distributed source coding and compression; distributed and collaborative signal processing; mobile code or agents.

2. How does TinyDB compute an AVERAGE inside the network? Each node's reading x becomes the partial state record (x, 1); records are merged by adding the sums and adding the counts; at the sink the evaluator divides SUM by COUNT.

3. Why can a node not simply forward the average of its own and its children's values? Because that gives equal weight to subtrees of different sizes. The correct method carries the count with the sum. In the worked example the correct average is about 30.8667 and averaging averages gives 31.0370.

4. A tree has 3 nodes at depth 1, 6 at depth 2 and 6 at depth 3. How many transmissions does one round cost with and without aggregation? Without: 3 × 1 + 6 × 2 + 6 × 3 = 33. With: one record per node, 15.

5. What is adaptive fidelity? Give an example. Deliberately trading the accuracy of results against energy and changing the trade as conditions change: sample rarely when all is quiet and often when a fire is suspected.

Three ways to build a data-centric network

• Interests routed through the network, as in directed diffusion: the interest spreads towards the data, and data flows back along the paths it set up.
• Publish and subscribe: consumers subscribe to a description of the data they want; producers publish data; the network matches the two, so neither needs to know the other.
• The network as a database: the user writes a declarative query (SELECT AVG(temperature) FROM sensors WHERE room = 7), and the system plans how to answer it inside the network. This is TinyDB, in [Middleware Approaches, and TinyDB].

Worked example: matching data against an interest

A vineyard sink wants to know about hot spots in the north-west quarter of a 100 m field: temperature above 30 degrees, from the rectangle x from 0 to 50 and y from 50 to 100. Eight nodes have readings. A data-centric network forwards only what matches; the program applies the interest to each reading.

# Data-centric matching: which readings satisfy an attribute-based interest?
interest = {"type": "temperature", "min_value": 30.0,
            "rect": (0, 50, 50, 100)}                      # x0, x1, y0, y1

readings = [  # node, type, value, x, y
    (1, "temperature", 31.5, 12, 88), (2, "temperature", 28.0, 40, 70),
    (3, "moisture",    34.0, 20, 60), (4, "temperature", 33.2, 45, 95),
    (5, "temperature", 36.1, 70, 90), (6, "temperature", 30.4, 5, 55),
    (7, "temperature", 29.9, 30, 80), (8, "temperature", 32.0, 48, 40),
]

def matches(r, want):
    node, kind, value, x, y = r
    x0, x1, y0, y1 = want["rect"]
    return (kind == want["type"] and value > want["min_value"]
            and x0 <= x <= x1 and y0 <= y <= y1)

hits = [r for r in readings if matches(r, interest)]
for node, kind, value, x, y in hits:
    print("node %d reports %s %.1f at (%d, %d)" % (node, kind, value, x, y))
print("%d of %d readings match; the other %d are never sent"
      % (len(hits), len(readings), len(readings) - len(hits)))

node 1 reports temperature 31.5 at (12, 88)
node 4 reports temperature 33.2 at (45, 95)
node 6 reports temperature 30.4 at (5, 55)
3 of 8 readings match; the other 5 are never sent

What the matching did. Node 3 is in the rectangle but reports moisture, the wrong type. Node 5 is hot but outside the rectangle. Nodes 2 and 7 are in the rectangle but too cool; node 7's 29.9 fails "above 30" by a tenth of a degree. Node 8 is hot but south of y = 50. The user never needed to know any node's number; the answer names nodes only because the data carries its source.

Principle 5: exploit location information

Sensor data is usually meaningless without where, so nodes need their positions anyway ([Time Synchronisation and Localisation]). Once they have them, location can do more work:

• Location-based routing: forward towards the destination's position instead of looking up a route ([Geographic Routing: Greedy Forwarding and GPSR]).
• Location-based addressing and scoping: send a query to "the nodes in region A", as the interest above did, so that nodes elsewhere never hear it. This is what makes a query's cost scale with the region instead of the network ([Figures of Merit: Scalability, Robustness and Measuring a Network]).
• Location-aware clustering and sleeping: nodes that are close together see the same thing, so only some of them need to be awake.

Principle 6: exploit activity patterns

Karl and Willig describe the typical traffic of a sensor network: "very low data rates over a large timescale, but can have very bursty traffic when something happens (a phenomenon known from real-time systems as event showers or alarm storms)". Months of quiet can alternate with seconds of intense activity.

Designing for this pattern means two things at once:

• For the quiet: sleep as much as possible, because there is almost nothing to send. Duty-cycling MAC protocols ([Duty Cycling: Preamble Sampling, B-MAC and X-MAC]) exist for this.
• For the storm: when an event happens, dozens of nodes detect it at once and all want to report. The network must suppress duplicate reports, aggregate them, and wake up enough capacity to carry what matters, without collapsing under collisions.

A design tuned only for the average load fails exactly when the network is needed.

Principle 7: exploit heterogeneity

Not all nodes need be the same. Some may have larger batteries or mains power, faster processors, a second, longer-range radio, or better sensors. A heterogeneous design gives each role to the node suited to it: cluster heads on the mains-powered nodes (the office building in [The Architectural Elements of a Sensor Network]), gateways on the nodes with a cellular radio, heavy computation on the nodes with processors to spare. Even in a network of identical nodes, heterogeneity appears over time as batteries run down unevenly, and a good protocol shifts work away from the weakest nodes.

Principle 8: component-based stacks and cross-layer optimisation

Component-based stacks. Instead of one fixed protocol stack, a node's software is built from small components with clear interfaces, chosen and wired together for each application. TinyOS is built this way ([nesC: Modules, Configurations, Interfaces and Wiring]), and it lets a node carry exactly the protocols its application needs and nothing more.

Cross-layer optimisation. The layered model of [The Sensor Network Protocol Stack and Its Three Planes] keeps each layer ignorant of the others. In a sensor network that ignorance is expensive. Karl and Willig note that the simplicity sensor nodes need "may also require breaking with conventional layering rules for networking software, since layering abstractions typically cost time and space". Examples of layers sharing information:

• The MAC tells routing which links have been reliable, and routing prefers them.
• Routing tells the MAC which neighbours it will send to, so only those need to stay awake.
• The application tells the transport and MAC layers how urgent a message is, so an alarm is sent at once while a routine reading waits to be combined with others.

The cost is that cross-layer designs are harder to understand, test and change, because a change in one layer can break another. The principle is to share information across layers deliberately and visibly, not to abolish them.

Distinctions

What it does not mean

Data-centric does not mean nodes have no identities. Data may carry its source, as in the worked example. What changes is that requests and routing do not depend on the identities.

Location-based addressing does not need GPS on every node. Positions can be estimated from neighbours, or set when nodes are placed.

Heterogeneity is not a fault to be designed away. It is a resource to be used, and it appears even in identical nodes as their batteries drain unevenly.

Cross-layer optimisation is not the absence of structure. It is layers sharing chosen information through defined interfaces.

Quick revision

• Principles (Karl and Willig 3.3), part two: data centricity; exploit location; exploit activity patterns; exploit heterogeneity; component-based stacks and cross-layer optimisation.
• Data-centric: "What is important are the answers and values themselves, not which node has provided them." Data named by attribute-value pairs; implementations: interests (directed diffusion), publish and subscribe, database queries (TinyDB).
• Directed diffusion's interest: type = wheeled vehicle, interval = 20 ms, duration = 10 s, rect = [-100, 100, 200, 400].
• Worked matching: 3 of 8 readings match; 5 are never sent.
• Activity: "event showers or alarm storms" after long quiet; design for both.
• Cross-layer: layering costs "time and space"; share link quality, neighbour and urgency information across layers.

Test yourself

1. Distinguish address-centric and data-centric networking. Address-centric networks communicate between named hosts, so a request names a node. Data-centric networks communicate about data described by its attributes, so a request describes the data wanted (type, value, region, time) and any node holding matching data answers. Data centricity suits sensor networks because redundant nodes make the identity of the answering node irrelevant.

2. How does directed diffusion name data? Give its example. By attribute-value pairs. Its vehicle-tracking interest is type = wheeled vehicle, interval = 20 ms, duration = 10 s, rect = [-100, 100, 200, 400]: detect vehicles, send events every 20 ms for the next 10 s, from sensors within the rectangle.

3. What does it mean for a sensor network to exploit activity patterns? Designing for traffic that is very low most of the time but bursts when an event happens: sleep aggressively in the quiet, and in the burst suppress duplicates, aggregate and avoid collisions so the critical reports get through.

4. Give two examples of cross-layer optimisation in a sensor network. The MAC passing link-quality information to routing so routes use reliable links; routing telling the MAC which neighbours will be used so only they stay awake; the application marking alarms as urgent so lower layers send them at once.

5. Why should a sensor network exploit heterogeneity? Because nodes that have more energy, processing or radio capability can take the demanding roles (cluster head, gateway, heavy computation), which spreads the load to where it can be carried and extends the network's lifetime.

Three interfaces that meet the requirements

Publish and subscribe, with interests

The application subscribes by handing the network an interest, a set of attribute-value pairs describing the data it wants, and a function to call when matching data arrives. Sensor nodes publish data named the same way. Directed diffusion's vehicle-tracking interest ([Design Principles: Data Centricity, Location, Activity and Heterogeneity]) is exactly such a subscription: what (wheeled vehicles), how often (every 20 ms), for how long (10 s) and where (a rectangle). Requirements 2, 3, 4 and 5 are met directly.

A declarative query

The application writes what it wants in a query language and lets the system decide how to get it. TinyDB's queries look like SQL with a sampling clause, for example a query ending in SAMPLE PERIOD 1s FOR 10s asks for readings every second for ten seconds. The system plans the sampling, the routing and the aggregation. Requirements 1, 2, 5 and 7 are met, and the application needs no knowledge of the network at all. [Middleware Approaches, and TinyDB] gives the language.

Events and scripts: the survey's SQTL

The survey describes the Sensor Query and Tasking Language (SQTL), which supports three kinds of event, "defined by keywords receive, every," and expire: receive, generated when a node receives a message; every, occurring periodically when a timer times out; and expire, occurring when a timer has expired. A node that receives a message intended for it that contains a script executes the script. This is an interface that sends programs into the network, and meets requirement 8 above all.

The survey's other two application-layer proposals are interfaces too: TADAP for spreading a user's interest into the network or letting nodes advertise their data, and SQDDP for issuing queries and collecting replies, where queries are attribute-based or location-based.

Worked example: one request, three ways

The request: Every 10 minutes for the next 24 hours, give me the average temperature of the nodes in the north-west quarter of the vineyard; and tell me at once if any node there reads above 40 degrees.

As a subscription (interest), in attribute-value pairs:

and a second interest with type = temperature, rect as above, and a condition value greater than 40, delivered as an event.

As a declarative query, in TinyDB's style:

SELECT AVG(temperature) FROM sensors
WHERE x < 50 AND y > 50
SAMPLE PERIOD 10 min FOR 24 h

with a second query for the alarm condition, whose answers arrive only when a reading exceeds 40.

As a socket-style exchange, the application would have to learn which node numbers are in the north-west quarter, open a connection to each, ask each for its reading every 10 minutes, average them itself, and poll each one continually for the alarm. Every one of those steps is something the data-centric interfaces do inside the network, and every one costs radio transmissions if done from outside.

The comparison is the answer to why not sockets?: the socket version is longer, knows node identities it should not need, cannot tell the network to aggregate, and polls where it should be notified.

Distinctions

What it does not mean

A service interface is not the radio's interface. It is between the application and the whole network, above every protocol layer.

Data-centric interfaces do not forbid naming a node. Sometimes a node must be addressed (to reprogram it, or to read a particular instrument); the interface should allow it without making it the normal way.

Declarative does not mean slow or wasteful. Saying what rather than how lets the system choose the cheapest how, including aggregation inside the network.

Quick revision

• Service interface: how applications ask the network for information and receive it.
• Sockets fail: the network needs "new programming interfaces that go beyond the simple semantics of the conventional socket interface" (Karl and Willig).
• Must express: one-shot queries; long-lived interests; asynchronous events with conditions; addressing by attribute and location; scoping in space and time; accuracy and the energy trade-off; in-network processing; run-time changes; management and security.
• Interfaces: publish and subscribe with interests; declarative queries (TinyDB, SAMPLE PERIOD); events and scripts (SQTL: receive, every, expire); the survey's TADAP and SQDDP.

Test yourself

1. What is a service interface of a WSN, and why is the socket interface not suitable? It is the set of operations through which applications request information from the network and receive results and events. Sockets address a host and exchange bytes, while WSN applications need to request data by attribute and location, scope requests in space and time, state accuracy, ask for aggregation and be notified of events.

2. List six things a WSN service interface must be able to express. Any six of: one-shot queries; long-lived subscriptions; asynchronous event notification with conditions; addressing by attribute and location; scoping in space and time; required accuracy and the energy trade-off; in-network processing; changes of requirements at run time; management and security.

3. What are SQTL's three kinds of event? Receive (a node receives a message), every (a timer times out periodically) and expire (a timer has expired). A node receiving a message intended for it that carries a script executes the script.

4. Express average temperature in region A every 10 minutes for a day as an interest. type = temperature, rect = region A's coordinates, interval = 10 min, duration = 24 h, aggregate = average.

Internet to WSN

The situation. A user on the Internet wants something from the sensor network: the latest readings, or a new task.

The problems, and how a gateway solves them.

• Which gateway to ask. The user must know an Internet address for the WSN. The gateway presents one: a web page, a web service, or a named endpoint.
• Expressing the request. The user's request (a web request for average temperature, north-west quarter) must be turned into the WSN's own terms: an interest, a query or a task, sent into the field. The gateway is therefore an application-level gateway: it understands the meaning of requests, not only their packets.
• Waiting for sleeping nodes. A request may take a long time to be answered inside the WSN. The gateway can answer from its cache of recent readings, and can collect one answer for many users, so the nodes are asked once.
• Protecting the field. The gateway can refuse, rate-limit or authenticate requests, so that a busy website does not drain the batteries of a forest.

WSN tunnelling

The situation. Two sensor networks are far apart, a sensor field on each bank of a river, or two buildings of one campus, and should behave as one network. No radio link joins them.

The idea. Each island has a gateway on the Internet. When a packet in one island is addressed to something in the other, its gateway encapsulates the whole WSN packet inside an Internet packet and sends it to the other gateway, which unwraps it and injects it into its own island. The Internet is used as a long virtual link, a tunnel. To the WSN protocols the two islands look like one network with one long hop.

The humblest gateway: a base station mote on a serial cable

In a laboratory, and in the practical, the gateway is a base station mote connected to a PC by a USB or serial cable. The mote listens to the radio and passes what it hears to the PC; the PC runs the program that stores, displays or forwards the data.

TinyOS ships this as an application. Its own source comment says it plainly: "BaseStationP bridges packets between a serial channel and the radio." Packets from the radio are passed to the serial port; packets from the PC are sent out over the radio. Messages going from serial to radio are tagged with the group identity compiled into the base station, and radio messages are filtered by that same group, so a base station hears only its own network.

How the bytes cross the cable

A serial line carries a stream of bytes, with nothing to mark where one packet ends and the next begins. TinyOS's serial stack, specified in TEP 113, solves this in three levels: encoding, framing and a protocol level with acknowledgements and a CRC. Its framing uses the same encoding as the HDLC protocol:

• 0x7e is reserved as the frame delimiter: it marks the start and end of every packet.
• 0x7d is reserved as the escape byte.
• If the data itself contains 0x7e or 0x7d, the sender sends 0x7d followed by the byte XORed with 0x20. TEP 113's example: "0x7e becomes 0x7d 0x5e".
• The receiver, on seeing 0x7d, drops it and XORs the next byte with 0x20 to recover the original.

A CRC (cyclic redundancy check) at the protocol level lets the receiver detect a packet damaged on the cable.

Worked example: framing a packet

The program frames a five-byte payload that happens to contain both reserved bytes, then decodes it again. (The CRC is left out so that the framing can be seen on its own.)

# HDLC-style framing as TinyOS's serial stack uses it (TEP 113):
# 0x7e marks frame boundaries, 0x7d escapes, an escaped byte is XORed with 0x20.
FLAG, ESC = 0x7E, 0x7D

def frame(payload):
    out = [FLAG]
    for b in payload:
        if b in (FLAG, ESC):
            out += [ESC, b ^ 0x20]
        else:
            out.append(b)
    return out + [FLAG]

def unframe(stream):
    body, escaped = [], False
    for b in stream[1:-1]:                  # drop the two delimiters
        if escaped:
            body.append(b ^ 0x20)
            escaped = False
        elif b == ESC:
            escaped = True
        else:
            body.append(b)
    return body

payload = [0x12, 0x7E, 0x34, 0x7D, 0x56]
line = frame(payload)
print("payload:", " ".join("%02x" % b for b in payload))
print("on the wire:", " ".join("%02x" % b for b in line))
print("decoded:", " ".join("%02x" % b for b in unframe(line)))
print("round trip correct:", unframe(line) == payload)

payload: 12 7e 34 7d 56
on the wire: 7e 12 7d 5e 34 7d 5d 56 7e
decoded: 12 7e 34 7d 56
round trip correct: True

What happened to the two reserved bytes. 0x7e in the data became the pair 0x7d 0x5e (0x7e XOR 0x20 is 0x5e), exactly TEP 113's example, and 0x7d became 0x7d 0x5d. Only the two real delimiters, at the ends, appear as bare 0x7e, so the receiver always knows where a frame starts and stops. The frame is two bytes longer for the delimiters and two more for the escapes: framing costs a little size for certainty.

A real gateway: Great Duck Island

The deployment of [Applications of Wireless Sensor Networks] shows the full chain. Each patch of motes had a gateway node; a longer radio link, the transit network, carried data from the gateway to a base station with a database and a wide-area connection; and remote users read a replica of that database over the Internet. Every layer kept some persistent storage, because a disconnection could happen at any level. That is Internet-to-WSN communication done through a cache, which is how most real systems do it.

Distinctions

What it does not mean

A gateway is not only a router. A router forwards packets of one protocol; a gateway translates between protocols and between ways of addressing, often at the level of meaning.

Internet-to-WSN does not mean a TCP connection to each node. The gateway answers for the network, from a cache or by collecting one answer for many users.

Tunnelling does not make the Internet part of the WSN. The Internet only carries the WSN's packets, wrapped, between two gateways.

The serial escape is not encryption. It only keeps the reserved bytes from being mistaken for delimiters.

Quick revision

• Gateway: joins the WSN to another network; needed for different protocols, different addressing, different availability, and a boundary for security and caching.
• WSN to Internet: node reports data-centrically to the gateway; gateway maps to Internet destinations and translates.
• Internet to WSN: gateway gives the WSN an Internet address, translates requests into queries or interests (an application-level gateway), caches answers, protects the field.
• WSN tunnelling: gateways encapsulate WSN packets in Internet packets to join two WSN islands.
• Base station mote: TinyOS BaseStation "bridges packets between a serial channel and the radio", filtered by group identity.
• TEP 113 framing: 0x7e delimiter, 0x7d escape, escaped byte XOR 0x20 (0x7e becomes 0x7d 0x5e), plus a CRC.

Test yourself

1. Why does a WSN need a gateway to reach the Internet? Because the two sides differ in protocols (low-power radio and WSN routing against IP), addressing (data-centric names against host addresses) and availability (sleeping nodes against always-on hosts), and because security, access control and caching belong at the boundary.

2. Explain Internet-to-WSN communication and the problems a gateway solves in it. An Internet user requests data or tasks the WSN. The gateway gives the WSN an Internet address, translates the request into the WSN's own query or interest, answers from a cache or gathers one answer for many users because nodes sleep, and protects the field by authenticating and rate-limiting requests.

3. What is WSN tunnelling? Joining two separate WSN islands through the Internet: each island's gateway encapsulates WSN packets bound for the other island in Internet packets, and the other gateway unwraps and injects them, so the Internet acts as one long virtual link.

4. How does TinyOS frame a packet on a serial line, and how is a data byte of 0x7e sent? With HDLC-style framing: 0x7e marks the start and end of each frame and 0x7d is the escape byte. A data byte of 0x7e is sent as 0x7d followed by 0x7e XOR 0x20, which is 0x5e.

5. What does the TinyOS BaseStation application do? It bridges packets between the radio and the serial port: radio packets of its group are passed to the PC, and packets from the PC are sent over the radio, tagged with the base station's group identity.

Header compression. Most of an IPv6 header can be worked out from the 802.15.4 header (the addresses are often derived from the link-layer addresses) or takes an expected value (the version, the usual hop limits). Compression leaves those fields out. RFC 8376's summary of the result: in the best case the IPv6 header for link-local communication is reduced to 2 bytes, for global communication to 3 bytes in the most extreme case, and in more practical situations to 11 bytes (one address prefix compressed) or 19 bytes (both).

Worked: what compression buys. Take the practical case of a 19-byte compressed header in place of 40. In the worst-case frame of 81 octets, the UDP application then has 81 - 19 - 8 = 54 octets instead of 33, and a typical sensor reading of a few tens of octets fits in a single frame instead of needing fragments. Every fragment avoided is a transmission, and an energy cost, saved.

RPL: routing towards the border router

Sensor networks running IP still need routing, and ordinary Internet routing protocols expect stable links and plenty of memory. RPL was designed for low-power and lossy networks, and its structure is the collection tree of [Design Principles: Distributed Organisation and In-network Processing] made into a standard.

The DODAG. RPL organises the network as a Destination-Oriented Directed Acyclic Graph: RFC 6550 defines it as "a DAG rooted at a single destination", the DODAG root, which is usually the border router. Every node has one or more parents closer to the root, so there are no loops and every path leads up to the root.

Rank. Each node has a Rank, which RFC 6550 describes as "a scalar representation of the location of that node within a DODAG Version"; it grows with distance from the root and "is used to avoid and detect loops". How Rank is computed is left to an Objective Function, which is how an application chooses what "best parent" means: fewest hops, best link quality, least energy.

The messages.

1. DIO (DODAG Information Object): sent by the root and then by every node, advertising the DODAG and the sender's Rank. A node hearing DIOs chooses its parents and computes its own Rank, then sends its own DIOs. This is how the graph grows outward from the root.
2. DIS (DODAG Information Solicitation): sent by a node that wants to join and has heard no DIO; it asks neighbours to send one.
3. DAO (Destination Advertisement Object): sent upward, advertising the node's address so that routes can be built down from the root towards the node.

Trickle. RPL does not send DIOs at a fixed rate. It uses the Trickle algorithm (RFC 6206): when nothing changes, the interval between DIOs doubles, so a stable network falls almost silent; when an inconsistency is detected, the interval is reset to its minimum and the network repairs itself quickly. It is an application of the principle [Design Principles: Data Centricity, Location, Activity and Heterogeneity] states as exploiting activity patterns: a network that has nothing to say should cost nothing to run.

Traffic and modes. RFC 6550 names three traffic flows: multipoint-to-point (from the nodes to a central point, the main case), point-to-multipoint (from the root to the nodes) and point-to-point. For routes downward it has two modes: in storing mode nodes keep routing tables for the nodes below them; in non-storing mode only the root keeps them, and downward packets carry their route, which suits nodes with little memory.

CoAP: a web protocol for a sensor

HTTP over TCP is too heavy for a node with 10 kB of RAM: TCP's connection set-up and its 20-byte header alone are costly, and the text headers of HTTP are larger than a sensor's whole reading. CoAP keeps the web's model (resources named by URIs, requests with methods, responses with codes) and makes everything small.

• Over UDP, not TCP, with the CoAP default port 5683.
• A fixed-size 4-byte header, followed by a token, options and the payload.
• Methods GET, PUT, POST and DELETE, which RFC 7252 says behave in a way "similar" to HTTP's.
• Reliability without TCP: a Confirmable message must be acknowledged and is retransmitted until it is; a Non-confirmable message is sent once, for readings where the next one will do.
• URIs of the form coap://host:port/path, such as RFC 7252's own example, coap://example.com:5683/~sensors/temp.xml.

So a web application can ask a node directly: a GET on the node's temperature resource, answered in one small UDP datagram, fitting in one 802.15.4 frame.

The stack, put together

The border router sits between the two columns. Unlike a translating gateway, it does not need to understand the application: it forwards IPv6 packets, expanding compressed headers on the way out and compressing them on the way in.

The adaptation layer, computed

The arithmetic above deserves to be run rather than quoted, because one of its conclusions is the opposite of the obvious one.

# What header compression is worth, in fragments and in transmissions.
PHY, MAC_OVERHEAD, SECURITY = 127, 25, 21    # RFC 4944's worst case, in octets
UDP, FRAG1, FRAGN = 8, 4, 5                  # UDP, and 6LoWPAN's two fragment headers
IPV6_MTU = 1280

frame = PHY - MAC_OVERHEAD - SECURITY
HDRS = ((40, "uncompressed, 40"), (19, "both prefixes compressed, 19"),
        (11, "one prefix compressed, 11"), (3, "global, best case, 3"),
        (2, "link local, best case, 2"))

def frames_for(hdr, app_octets):
    """Frames needed to carry app_octets of application data, RFC 4944."""
    if hdr + UDP + app_octets <= frame:
        return 1
    first = frame - FRAG1 - hdr - UDP            # application octets in fragment one
    rest = frame - FRAGN                         # and in each one after it
    return 1 + -(-(app_octets - first) // rest)

print("A worst-case 802.15.4 frame leaves %d octets above link-layer security." % frame)
print()
print("What the compressed header buys, in payload and in frames:")
print("  IPv6 header                    payload in    a full %d octet" % IPV6_MTU)
print("                                 one frame     packet needs")
for hdr, label in HDRS:
    payload = frame - hdr - UDP
    full = frames_for(hdr, IPV6_MTU - 40 - UDP)
    print("  %-30s %6d octets %8d frames" % (label, payload, full))
print()
print("Read that last column again. Compression barely changes it, because it only")
print("shortens the FIRST fragment: every fragment after it carries raw payload and is")
print("the same size whatever the header was. Compression is not a way to fragment less")
print("when the packet is large.")
print()
print("Where it does change everything is the packet a sensor actually sends:")
print("                      frames needed, with an IPv6 header of")
print("  application data    " + "".join("%12s" % ("%d octets" % hdr) for hdr, _ in HDRS))
for app in (20, 33, 40, 54, 60, 71, 80):
    print("  %6d octets     " % app
          + "".join("%9d fr" % frames_for(hdr, app) for hdr, _ in HDRS))
print()
print("Compression does not make the packet smaller. It makes the payload that fits in")
print("one frame larger, and for a reading of a few tens of octets that is the whole")
print("difference between one transmission and two.")

# What a fragment costs, and why losing one is worse than it looks.
print()
print("Why a lost fragment is worse than a lost packet:")
for n in (2, 4, 8, 16):
    for per_frag in (0.01, 0.05):
        ok = (1 - per_frag) ** n
        print("  %2d fragments at %2.0f%% loss each: the packet arrives %5.1f%% of the time"
              % (n, per_frag * 100, ok * 100))
print("  and a packet that loses one fragment loses all of them, because there is no")
print("  selective repeat below IP: every fragment is sent again.")

# CoAP against HTTP, in bytes on the wire for one reading.
print()
print("Asking a sensor for a reading, in octets on the wire:")
COAP_FIXED, COAP_TOKEN = 4, 2                 # RFC 7252's fixed header, plus a short token
uri = "/s/t"
coap_req = COAP_FIXED + COAP_TOKEN + 1 + len(uri)
coap_rsp = COAP_FIXED + COAP_TOKEN + 1 + 4
http_req = len("GET /sensors/temperature HTTP/1.1\r\nHost: node.example\r\n\r\n")
http_rsp = len("HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\nContent-Length: 4\r\n\r\n21.4")
print("  CoAP over UDP: request %3d, response %3d, total %3d" % (coap_req, coap_rsp, coap_req + coap_rsp))
print("  HTTP over TCP: request %3d, response %3d, total %3d" % (http_req, http_rsp, http_req + http_rsp))
print("  a factor of %.1f, before TCP's three way handshake and its acknowledgements,"
      % ((http_req + http_rsp) / float(coap_req + coap_rsp)))
print("  and the CoAP exchange fits in one frame in each direction while the HTTP one")
print("  does not fit in the worst-case frame at all.")

Distinctions

What it does not mean

6LoWPAN is not a new network layer. It is an adaptation layer below IPv6; the network layer is still IPv6.

IP on the node does not remove the need for a border router. The border router is still the link between the 802.15.4 network and the rest of the Internet, and still the natural place for security.

RPL is not only for collection. Its main flow is multipoint-to-point, but it also builds downward and point-to-point routes.

CoAP is not HTTP compressed. It is a separate protocol over UDP with its own reliability; a proxy can translate between CoAP and HTTP.

Quick revision

• 6LoWPAN: adaptation layer for IPv6 over 802.15.4, fragmentation and reassembly plus header compression.
• The squeeze (RFC 4944, RFC 4919): 127 physical, 102 after MAC, 81 after AES-CCM-128, 41 after IPv6, 33 after UDP, 21 after TCP; IPv6 needs 1,280.
• Compressed IPv6 header (RFC 8376): 2 bytes link-local best case, 3 global extreme, 11 or 19 practical. With 19: 54 octets for UDP data in the worst-case frame.
• RPL: a DODAG rooted at the border router; Rank from an Objective Function; DIO advertises, DIS solicits, DAO advertises destinations; Trickle timing; storing and non-storing modes; MP2P, P2MP, P2P traffic.
• CoAP: UDP port 5683, 4-byte header, GET, PUT, POST, DELETE, Confirmable and Non-confirmable messages.

Test yourself

1. Why can an IPv6 packet not be sent directly in an 802.15.4 frame, and what does 6LoWPAN do about it? IPv6 needs links to carry 1,280-octet packets, while an 802.15.4 frame is at most 127 octets, 102 after MAC overhead and 81 with the strongest security. 6LoWPAN adds an adaptation layer that fragments packets and reassembles them, and compresses the IPv6 and UDP headers by leaving out fields that can be derived or take expected values.

2. In the worst case, how many octets are left for UDP data in an 802.15.4 frame without compression, and with a 19-byte compressed header? Without: 81 - 40 - 8 = 33. With: 81 - 19 - 8 = 54.

3. Explain how RPL builds its routing structure. The root, usually the border router, sends DIO messages advertising the DODAG. A node hearing DIOs chooses parents with lower Rank, computes its own Rank with the Objective Function, and sends its own DIOs, so the graph grows outward with no loops. A node that hears nothing sends a DIS to ask for a DIO; nodes send DAOs upward so downward routes can be built. Trickle slows DIOs when the network is stable and speeds them when it changes.

4. What are CoAP's main features? A web protocol over UDP (default port 5683) with a fixed 4-byte header, methods GET, PUT, POST and DELETE, URIs as on the web, and its own reliability: Confirmable messages are acknowledged and retransmitted, Non-confirmable ones are not.

5. How does a border router differ from a translating gateway? The border router forwards IPv6 packets between the 6LoWPAN network and the Internet, only compressing and expanding headers, so it does not need to understand applications. A translating gateway must understand each application's messages and convert them between the WSN's protocols and the Internet's.

Their result was an operating system that, in the paper's words, "fits in 178 bytes of memory".

The design issues a sensor OS must settle

Each of these is a decision, and the systems of [TinyOS: Components, Tasks and the Scheduler] and [Contiki, RIOT and the Other Sensor Operating Systems] settle them differently.

Reprogramming deserves a word of its own

Contiki's authors put the case: networks of "hundreds or even thousands of nodes" must have code downloaded into them, and "bugs may have to be patched in an operational network", because "it is not feasible to physically collect and reprogram all sensor devices". Sending code costs energy, so the smaller the piece sent, the better. Most embedded systems must send a complete binary image of the whole system; Contiki's answer is to "load and unload individual applications or services at run-time", so only the changed program travels.

How small is small

The numbers in the two founding papers make the constraint concrete.

• Contiki's paper describes the typical device of 2004: "8-bit microcontrollers, code memory on the order of 100 kilobytes, and less than 20 kilobytes of RAM". Its own platform, the ESB, had an MSP430 with 2 kilobytes of RAM and 60 kilobytes of ROM, running at 1 MHz.
• On that platform a Contiki process's whole state was 23 bytes.
• The first TinyOS fitted in 178 bytes.
• The Telos mote of [Inside a Sensor Node: The Five Units] was generous by comparison: 10 kB of RAM.

A desktop operating system needs thousands of times more memory just to start.

Worked example: one wake-up of a relay node

A relay node in the vineyard wakes on a timer. In the next few milliseconds, all of this may happen, and the operating system is what keeps it in order.

Three things in the table are an operating system's whole job in miniature: the radio's interrupt at 0.4 ms could not wait for the sampling to finish, so the OS must let urgent events interrupt; the ADC and the radio worked while the processor did other things, so the OS must let operations start and finish later; and at 7.5 ms the node went back to sleep because the OS knew nothing else was pending.

Distinctions

What it does not mean

A sensor OS is not a small Linux. It usually has no memory protection, no file system in the usual sense and no users, and it is organised around events and energy.

"178 bytes" is not the size of a whole application. It is the core of the 2000 TinyOS; applications and their components add to it.

An operating system does not make the node faster. It makes it organised and economical: it lets many slow things overlap and sleeps in the gaps.

Quick revision

• A sensor OS manages concurrency, hardware abstraction, scheduling, memory, communication, power and reprogramming, in a tiny footprint.
• TinyOS's five requirements (2000): small size and low power; concurrency-intensive operation; limited physical parallelism and controller hierarchy; diversity in design and usage (modularity); robust operation. First TinyOS: 178 bytes.
• Design issues: execution model, scheduling, memory management, protocol support, resource sharing, modularity, energy management, reprogramming, robustness, timing.
• Typical 2004 node (Contiki paper): 8-bit MCU, about 100 kB code, under 20 kB RAM; ESB: 2 kB RAM, 60 kB ROM, 1 MHz; a Contiki process state: 23 bytes.
• Reprogramming over the radio must send as little code as possible; Contiki loads individual programs at run time.

Test yourself

1. Why does a sensor node need an operating system? Because even a simple node handles several concurrent activities (timers, sensor conversions, arriving and departing packets, commands) on one small processor. The OS provides a structure to respond to events, share the processor, defer work, abstract the hardware, manage energy by sleeping whenever possible, and support reprogramming, within a few kilobytes.

2. State the five requirements the TinyOS designers identified for networked sensors. Small physical size and low power consumption; concurrency-intensive operation; limited physical parallelism and controller hierarchy; diversity in design and usage, requiring efficient modularity; robust operation of numerous unattended devices.

3. List the design issues of a WSN operating system. Execution model, scheduling, memory management, communication protocol support, resource sharing, modularity, energy management, dynamic reprogramming, robustness, and meeting timing requirements.

4. Why is dynamic reprogramming important, and how does Contiki make it cheaper? Deployed networks have hundreds or thousands of nodes that cannot be collected, and bugs must be fixed in the field, so code must be sent over the radio, which costs energy. Contiki loads and unloads individual programs at run time, so only the changed program is sent rather than a whole system image.

5. In the relay node's wake-up, what three things did the OS have to make possible? Letting an urgent event (the radio interrupt) interrupt other work; letting slow operations (the ADC conversion, the radio send) start and finish later while the processor did other things; and putting the node to sleep as soon as nothing was pending.

The event-driven model

In an event-driven system, the program is a set of handlers: pieces of code that run when something happens (a timer fires, a packet arrives, a conversion finishes) and then return. The Contiki paper states the three consequences: "processes are implemented as event handlers that run to completion"; "because an event handler cannot block, all processes can use the same stack, effectively sharing the scarce memory resources between all processes"; and "locking mechanisms are generally not needed because two event handlers never run concurrently with respect to each other".

Split-phase work. A handler cannot wait for the ADC. Instead it starts the conversion and returns; when the conversion finishes, a completion event calls another handler with the result. The same loop as above becomes:

on timer fired:      start the ADC; return
on ADC done(value):  start sending value; return
on send done:        return                       # nothing left: the node sleeps

This is the split-phase style of [Commands, Events and Split-phase Operation].

Deferred work: tasks. A handler must be short, because nothing else runs while it runs. Work that takes longer is posted as a task, a function to be run later by the scheduler. TinyOS's scheduler runs tasks one at a time in the order they were posted, and a task is never interrupted by another task: it runs to completion. That is the non-preemptive scheduler the practical asks about.

The problems, also in the Contiki authors' words. "The state driven programming model can be hard to manage for programmers", and "not all programs are easily expressed as state machines". Their example is "the lengthy computation required for cryptographic operations", which can take several seconds on a small processor, and in a purely event-driven system "a lengthy computation completely monopolizes" the processor.

Worked example: a long task and a timer, run

A node's timer needs a 1 ms handler every 10 ms (for example to sample a sensor on schedule). At time 2 ms, a 35 ms computation is posted (a compression, or a cryptographic operation). In a run-to-completion scheduler the timer's handler is itself a task, so it must wait for whatever task is running. The program simulates the scheduler twice: with the computation as one task, and with it split into seven tasks of 5 ms, each posting the next when it finishes.

# A run-to-completion task scheduler, the model of TinyOS's tasks.
# Tasks run one at a time, in the order they were posted, and none is ever
# interrupted by another. A timer posts a 1 ms handler task every 10 ms; at
# time 2 ms a 35 ms computation is posted, either whole or in 5 ms pieces.
from collections import deque

def simulate(pieces):
    queue = deque()
    ticks = [10, 20, 30, 40, 50]
    pending = list(ticks)                      # timer ticks not yet posted
    queue.append(("compute", pieces[0], 1))    # posted at time 2
    now, latency = 2, {}
    while queue or pending:
        while pending and pending[0] <= now:   # the timer posts its handler
            t = pending.pop(0)
            queue.append(("tick", 1, t))
        if not queue:                          # nothing to do: sleep until the next tick
            now = pending[0]
            continue
        kind, length, info = queue.popleft()
        if kind == "tick":
            latency[info] = now - info
        now += length                          # run to completion
        if kind == "compute" and info < len(pieces):
            while pending and pending[0] <= now:
                t = pending.pop(0)
                queue.append(("tick", 1, t))
            queue.append(("compute", pieces[info], info + 1))   # repost next piece
    return latency, now

for label, pieces in (("one 35 ms task", [35]), ("seven 5 ms tasks", [5] * 7)):
    latency, end = simulate(pieces)
    shown = ", ".join("%d ms" % latency[t] for t in sorted(latency))
    print("%-17s delays of the timer handler: %s (worst %d ms)"
          % (label + ":", shown, max(latency.values())))

one 35 ms task:   delays of the timer handler: 27 ms, 18 ms, 9 ms, 0 ms, 0 ms (worst 27 ms)
seven 5 ms tasks: delays of the timer handler: 2 ms, 3 ms, 4 ms, 0 ms, 0 ms (worst 4 ms)

Read the first line. The single 35 ms task runs from 2 ms to 37 ms. The ticks at 10, 20 and 30 ms all wait behind it and then run in a burst: delays of 27, 18 and 9 ms. A sample meant to be taken every 10 ms is taken three times in 3 ms. This is Contiki's warning, measured: the long computation "completely monopolizes" the processor.

Read the second line. Split into 5 ms pieces, each piece posts the next at the back of the queue, so a tick that arrives during a piece runs as soon as that piece ends. The worst delay is 4 ms, and it can never exceed the length of one piece. In a run-to-completion system, the responsiveness of the whole node is set by its longest task. That is why TinyOS programs break long work into short tasks, and it is the lesson of the practical's scheduler exercise.

The middle ways

Neither model is perfect, and real systems mix them.

• Contiki: an event-driven kernel, with "optional preemptive multithreading that can be applied to individual processes". Threads are a library, linked only into programs that need them, so the rest of the system keeps its single stack.
• Protothreads, also from Contiki: code written in sequential style, with waits, but compiled into an event-driven state machine that needs no stack of its own ([Contiki, RIOT and the Other Sensor Operating Systems]).
• TinyOS's two levels: tasks never preempt each other, but hardware interrupts do preempt tasks; the 2000 paper describes this as "two level scheduling". Urgent, tiny work runs in interrupt handlers; everything else runs as tasks.
• Preemptive multithreading throughout, as in Mantis, which the Contiki paper describes: "every Mantis program must have stack space allocated from the system heap, and locking mechanisms must be used to achieve mutual exclusion of shared variables".

Distinctions

What it does not mean

Event-driven does not mean nothing can interrupt. In TinyOS hardware interrupts preempt tasks; what never happens is one task preempting another.

Run to completion does not mean long-running. It means uninterrupted, which is exactly why each task must be short.

Threads are not wrong for sensor nodes. They cost memory. On a node with more RAM, or for one long computation, a thread can be the better tool, which is why Contiki offers them optionally.

Quick revision

• Event-driven: handlers and tasks run to completion, one shared stack, no locks, split-phase operations; hard for long computations and state-heavy programs.
• Multithreaded: a stack per thread, over-provisioned; blocking and preemption; locking needed.
• Contiki (2004): threads need stacks that "typically has to be over provisioned"; event handlers "cannot block", so "all processes can use the same stack"; a lengthy computation "completely monopolizes" the processor.
• Worked stacks: 5 × 512 = 2,560 bytes, a quarter of 10 kB of RAM.
• Simulation: one 35 ms task delays the timer handler by 27, 18 and 9 ms; seven 5 ms tasks, at worst 4 ms. Responsiveness is set by the longest task.
• Middle ways: Contiki's optional per-process threads, protothreads, TinyOS's two-level scheduling (interrupts preempt tasks); Mantis is preemptive throughout.

Test yourself

1. Compare the event-driven and multithreaded execution models for sensor nodes. Event-driven: handlers and tasks run to completion without blocking, share one stack and need no locks, which saves memory; but long computations must be split and programs become state machines. Multithreaded: each thread has its own over-provisioned stack and can block and be preempted, which allows sequential code, at the cost of memory and locking.

2. What does "run to completion" mean, and what follows for how tasks are written? A task, once started, runs until it finishes and is never interrupted by another task. So every task must be short, and long work is split into several tasks, each posting the next, or the whole node becomes unresponsive while it runs.

3. In the simulation, why did splitting the computation reduce the timer handler's worst delay from 27 ms to 4 ms? Because in a run-to-completion scheduler a waiting task can only start when the running one ends. With one 35 ms task the timer handler waited for most of it; with 5 ms pieces, each piece reposted the next at the back of the queue, so the handler ran after at most one piece.

4. Why does a multithreaded system need locks, and why does an event-driven one generally not? Threads can be interrupted in the middle of updating shared data, so another thread could see or change it half-updated; locks prevent that. Event handlers never run concurrently with each other, so a handler always sees shared data in a consistent state.

5. How does Contiki combine the two models? Its kernel is event-driven with one stack, and preemptive multithreading is provided as a library linked only into the processes that need it, so only those processes pay for stacks.

The component graph: commands down, events up

Figure 26.1 TinyOS: components wired in layers, and the task scheduler

Components are composed in layers: "higher level components issue commands to lower level components and lower level components signal events to the higher level components", with the physical hardware as the lowest level.

Commands go down. The paper defines them as "non-blocking requests made to lower level components". A command typically records its parameters in the frame and posts a task, or calls a lower command, and returns at once with a status saying whether the request was accepted. It "must not wait for long or indeterminate latency actions to take place".

Events come up. The lowest components' event handlers are connected directly to hardware interrupts (a timer, a counter, an external signal). An event handler can store information in its frame, post tasks, signal higher events or call lower commands. The paper's image is exact: a hardware event "triggers a fountain of processing that goes upward through events and can bend downward through commands".

One rule prevents loops: "commands cannot signal events". Both commands and events are meant to do "a small, fixed amount of work".

Tasks

A task is TinyOS's unit of deferred work. TEP 106 defines tasks as "a form of deferred procedure call", which "enable a program to defer a computation or operation until a later time", and gives their essential property: "TinyOS tasks run to completion and do not pre-empt one another", so that "tasks are atomic with respect to other tasks".

In nesC a task is declared with the keyword task and requested with the keyword post:

task void computeAverage() {   // declared in a module's implementation
  // the deferred work: runs later, to completion
}
...
post computeAverage();         // returns SUCCESS or FAIL at once

Three rules about tasks, all from TEP 106 or the 2000 paper, are the ones examiners like:

1. A task runs to completion. Once started it is never interrupted by another task. It can be interrupted by a hardware event, which the 2000 paper puts as tasks "can be preempted by events".
2. A task must never block or spin. In the 2000 paper's words, tasks "must never block or spin wait or they will prevent progress in other components".
3. A task is in the queue at most once. In TinyOS 2 the scheduler must accept a post "unless it is not the first call ... since that task's ... runTask() event has been signaled". So posting a task that is already waiting returns FAIL, and the task still runs once.

Why tasks exist at all. Because commands and event handlers must be short, and some work is not. A timer event handler that needs to average fifty readings posts a task to do it and returns immediately, so the next event is not held up.

The scheduler

TinyOS 2's standard scheduler is a component, SchedulerBasicP. TEP 106 gives its signature: it provides the Scheduler interface and a parameterised TaskBasic interface (one instance per task, each identified by a number the compiler assigns with nesC's unique() function), and it uses McuSleep, the interface for putting the microcontroller into a low-power state. The basic task is "parameterless and FIFO": tasks run in the order they were posted.

It sleeps when idle. TEP 106 requires that the scheduler's task loop put "the MCU into a low power state when the processor is idle". The 2000 paper explains why this is safe: the processor sleeps "but leaves the peripherals operating, so that any of them can wake up the system", and "once the queue is empty, another thread can be scheduled only as a result of an event", so nothing is lost by sleeping until an interrupt arrives.

It is replaceable. Because the scheduler is a component, an application that needs a different policy (priorities, earliest deadline first) can wire in a different scheduler. TEP 106 adds the rule that follows: components "MUST NOT assume a FIFO policy".

How it all runs: from interrupt to sleep

Put the pieces together and one wake-up of a node looks like this.

1. The node is asleep; the scheduler's queue is empty.
2. A hardware timer interrupt fires. The lowest timer component's handler runs (preempting nothing, since nothing is running) and signals an event up to the application.
3. The application's handler for that event posts a task to take a reading, and returns.
4. The interrupt is over. The scheduler finds a task in its queue and runs it to completion: the task calls a command to start the ADC, which returns at once.
5. The queue is empty again, so the scheduler puts the processor to sleep.
6. The ADC finishes and interrupts. Its component signals a completion event; the application's handler posts a task to send the reading. The scheduler wakes, runs it, and the story continues until the queue empties and the node sleeps again.

The whole design is built so that the processor is awake only while there is work, and every piece of work is short.

Worked example: how big is it?

The 2000 TinyOS fitted, in its paper's words, "in 178 bytes of memory". A small TinyOS 2 application of our own, BlinkTask, in which three timers each post a task that toggles one LED, wired to the standard timer, LED and boot components (the program is printed in full in [Blink: A TinyOS Application Read Line by Line]), was compiled for the TelosB mote by this book's checker, nesc-check.py, inside a TinyOS 2.1.2 laboratory with nescc 1.3.5. The compiler reported 2,682 bytes of program memory (ROM) and 60 bytes of RAM, scheduler, timer and LED drivers included.

Set that against the MSP430F1611's 48 kB of flash and 10 kB of RAM from [Inside a Sensor Node: The Five Units]: the whole operating system and application use about 5.5 per cent of the flash and well under 1 per cent of the RAM, leaving the rest for the real application's protocols and data. That is what static allocation and linking only the components used buy.

Distinctions

What it does not mean

Tasks are not threads, although the 2000 paper used that word. They have no stack of their own and cannot block, wait or be preempted by other tasks.

Run to completion does not mean nothing can interrupt a task. Hardware events can; other tasks cannot.

Components are not run-time objects. They are wired together when the program is compiled; there is no dynamic loading in TinyOS (Contiki's difference, in [Contiki, RIOT and the Other Sensor Operating Systems]).

FIFO is not a promise. It is the default policy, and TEP 106 forbids components from relying on it.

Quick revision

• TinyOS: event-driven, component-based, written in nesC; a system is "a tiny scheduler and a graph of components".
• A component's four parts: command handlers, event handlers, a fixed-size frame, tasks.
• Commands go down ("non-blocking requests"), events come up (from hardware interrupts); commands cannot signal events.
• Tasks: deferred procedure calls that run to completion and do not pre-empt one another; can be preempted by events; must never block; in the queue at most once.
• Scheduler: SchedulerBasicP, provides Scheduler and TaskBasic, uses McuSleep; FIFO, replaceable; sleeps when the queue is empty.
• Static allocation: memory needs known at compile time.
• Size: the 2000 TinyOS 178 bytes; BlinkTask 2,682 bytes ROM, 60 bytes RAM on TelosB.

Test yourself

1. Describe the architecture of TinyOS. A tiny scheduler and a graph of components, wired at compile time. Each component has command handlers, event handlers, a fixed-size frame and tasks. Higher components call commands on lower ones and lower ones signal events upward, with hardware interrupts at the bottom. Long work is posted as tasks, which the FIFO scheduler runs one at a time to completion, sleeping when none is waiting.

2. Distinguish commands, events and tasks in TinyOS. Commands are non-blocking requests from a higher component to a lower one, returning a status at once. Events are signalled upward, starting from hardware interrupts, to report that something has happened. Tasks are deferred work posted to the scheduler, run later to completion without preempting one another.

3. What does "tasks run to completion" mean, and why is it important? Once a task starts, no other task interrupts it until it finishes, although hardware events can. It means all tasks can share one stack and need no locks, and it requires tasks to be short and never block.

4. What happens when a component posts a task that is already waiting in the queue? In TinyOS 2 the post returns FAIL, because a task can be in the queue only once; the task still runs once when its turn comes.

5. How does the TinyOS scheduler save energy? When its task queue is empty it puts the microcontroller into a low-power state through the McuSleep interface, leaving the peripherals running so that any interrupt can wake the system; since new tasks can only come from events, nothing is lost by sleeping.

Three real split-phase interfaces from TinyOS 2:

The Timer interface (TEP 102) has the same pattern with a twist: startPeriodic(dt) is a command that returns immediately, and fired() is an event that comes back every dt milliseconds, not once.

Worked example: read a sensor and broadcast the reading

The application below does one thing: every second it reads a sensor and broadcasts the value by radio. Three of its operations are split-phase, switching the radio on, reading the sensor and sending the packet, and every one of them is written as a command that returns and an event that completes. It is two files: a module with the logic and a configuration that wires it to TinyOS's components.

module SenseSendC {
  uses interface Boot;
  uses interface SplitControl as RadioControl;
  uses interface Timer<TMilli>;
  uses interface Read<uint16_t>;
  uses interface AMSend;
  uses interface Packet;
}
implementation {
  message_t packet;          // the one buffer, allocated at compile time
  bool busy = FALSE;         // is a send in progress?
  uint16_t reading;

  event void Boot.booted() {
    call RadioControl.start();          // phase 1: ask for the radio
  }
  event void RadioControl.startDone(error_t err) {
    if (err == SUCCESS) call Timer.startPeriodic(1000);
    else call RadioControl.start();     // phase 2: radio on, or try again
  }
  event void RadioControl.stopDone(error_t err) { }

  event void Timer.fired() {
    call Read.read();                   // phase 1: start the conversion
  }
  task void sendReading() {
    uint16_t* payload;
    if (busy) return;
    payload = (uint16_t*)call Packet.getPayload(&packet, sizeof(uint16_t));
    if (payload == NULL) return;
    *payload = reading;
    if (call AMSend.send(AM_BROADCAST_ADDR, &packet, sizeof(uint16_t)) == SUCCESS)
      busy = TRUE;                      // phase 1: send accepted, not finished
  }
  event void Read.readDone(error_t result, uint16_t value) {
    if (result == SUCCESS) {            // phase 2: the value has arrived
      reading = value;
      post sendReading();
    }
  }
  event void AMSend.sendDone(message_t* msg, error_t err) {
    if (msg == &packet) busy = FALSE;   // phase 2: the buffer is free again
  }
}

configuration SenseSendAppC { }
implementation {
  components MainC, SenseSendC, ActiveMessageC;
  components new TimerMilliC();
  components new DemoSensorC() as Sensor;
  components new AMSenderC(6);

  SenseSendC.Boot -> MainC;
  SenseSendC.RadioControl -> ActiveMessageC;
  SenseSendC.Timer -> TimerMilliC;
  SenseSendC.Read -> Sensor;
  SenseSendC.AMSend -> AMSenderC;
  SenseSendC.Packet -> AMSenderC;
}

Reading it as split-phase pairs.

• Radio: Boot.booted() calls RadioControl.start() and returns; the radio takes time to power up; RadioControl.startDone() arrives later and only then starts the timer. If the start failed, it tries again.
• Sensor: Timer.fired() calls Read.read() and returns; Read.readDone() arrives with the value and posts sendReading.
• Radio send: the task calls AMSend.send(); SUCCESS means the radio accepted the packet, so busy is set; AMSend.sendDone() arrives when the packet has actually gone, and clears busy.

Why the busy flag. Between send() and sendDone() the packet buffer belongs to the radio stack, which is still reading it. TEP 116 even fixes the rule: AMSend has "an explicit queue of depth one", and a second send "MUST return EBUSY if a prior call to send returned SUCCESS but no sendDone event has been signaled yet". If the task wrote a new reading into it before sendDone(), it would corrupt a packet in flight. The flag is how a split-phase caller remembers that an operation is outstanding. It is the most common bug in a student's first TinyOS program, and the reason the practical asks for split-phase to be demonstrated rather than described.

Why the work is in a task. readDone() only stores the value and posts sendReading; the building and sending of the packet happen in the task. Event handlers stay short.

What the compiler said. Compiled for the TelosB by this book's checker, inside the TinyOS 2.1.2 laboratory, the application built with no warning from its own files and reported 15,448 bytes of program memory and 462 bytes of RAM. Against the toggling application of the previous chapter (2,462 and 38), the difference is the radio stack and the sensor driver the wiring pulled in: TinyOS includes exactly the components a configuration names, and their dependencies, and nothing else.

What may call what: the nesC rules

The nesC reference manual sets out the concurrency rules, and they are the other half of this topic.

Synchronous and asynchronous code. The manual divides a program in two:

• Synchronous code (SC): "code (functions, commands, events, tasks) that is only reachable from tasks".
• Asynchronous code (AC): "code that is reachable from at least one interrupt handler".

Tasks never preempt each other, so synchronous code cannot race with other synchronous code. But an interrupt can arrive in the middle of a task, so asynchronous code can race with anything.

The async keyword. A command or event that can run in interrupt context must be declared async. The manual: "nesC reports a compile-time error for any command or event that is AC and that was not declared with async", which "ensures that code that was not written to execute safely in an interrupt handler is not called inadvertently". The events of the application above are all synchronous: TinyOS delivers them from tasks, which is why the program needs no atomic sections.

The two race-free invariants. The compiler warns if either is broken:

1. If a variable is written in asynchronous code, all accesses to it must be in atomic sections.
2. If a variable is read in asynchronous code, all writes to it must be in atomic sections.

Atomic statements. An atomic block is executed "as-if" no other computation occurred simultaneously. It is how interrupt-level code and task-level code share a variable safely, and the manual warns that "atomic sections should be short".

The usual pattern. Do the minimum in an async event (copy the data, set a flag), then post a task to do the rest in synchronous code. Posting is allowed from async code; the task then runs later, safely, in synchronous context.

Distinctions

What it does not mean

SUCCESS from a split-phase command does not mean the operation succeeded. It means the request was accepted. Whether it worked is in the completion event.

A split-phase command does not always produce its event. A completion event belongs to a request that was accepted; if the command did not return SUCCESS, the request was refused, and the caller must handle that at once rather than wait for an event.

Atomic does not mean fast. It means uninterrupted, so an atomic block should be short, or it delays every interrupt behind it.

Events are not all interrupts. An event is a callback from a lower component; only some events run in interrupt context, and those are the async ones.

Quick revision

• Split-phase: a command requests and returns at once; an event later reports completion with the result. "All lengthy commands in TinyOS (e.g. send packet) are non-blocking."
• Bidirectional interfaces: the user of an interface must implement its events, so a caller of send() must write sendDone().
• Examples: Read.read() / readDone(), AMSend.send() / sendDone(), SplitControl.start() / startDone(); Timer.startPeriodic() / fired() repeatedly.
• call a command, signal an event, post a task.
• SC: reachable only from tasks. AC: reachable from an interrupt handler; must be async; shared variables need atomic sections (the two race-free invariants).
• Worked application: three split-phase pairs, a busy flag for the buffer, the work in a task; compiled for TelosB: 15,448 bytes ROM, 462 bytes RAM.

Test yourself

1. What is split-phase operation? Explain with the example of reading a sensor. Dividing a long operation into a request and a completion. The application calls Read.read(), which starts the conversion and returns SUCCESS at once; the processor meanwhile runs other tasks or sleeps; when the conversion ends, the sensor component signals Read.readDone(result, value) with the reading, and the handler posts a task to use it.

2. Why does TinyOS use split-phase operations instead of blocking calls? Because TinyOS is event-driven with one shared stack and run-to-completion tasks: a blocking call would stop every other handler and task. Splitting lets many operations be outstanding at once, lets the node sleep while hardware works, and needs no stack per operation.

3. In the SenseSend application, why is the busy flag needed? Because between AMSend.send() and AMSend.sendDone() the packet buffer belongs to the radio stack. The flag stops the task from writing a new reading into a buffer still being transmitted; sendDone() clears it.

4. What are synchronous and asynchronous code in nesC, and what must asynchronous code do? Synchronous code is reachable only from tasks; asynchronous code is reachable from at least one interrupt handler. Asynchronous commands and events must be declared async, and variables shared with them must be accessed in atomic sections according to the race-free invariants.

5. State the two race-free invariants. If a variable is written in asynchronous code, all accesses to it must be in atomic sections; if a variable is read in asynchronous code, all writes to it must be in atomic sections.

A configuration has a specification too, but its implementation contains no code: it names components and wires them. A configuration is how components are assembled into bigger components, and a whole application is one top-level configuration.

Wiring: the three statements

The manual gives exactly three wiring statements.

1. endpoint1 -> endpoint2, a link wire: connects a used interface (on the left) to a provided interface (on the right), both on components inside the configuration. "If these two conditions do not hold, a compile-time error occurs."
2. endpoint1 <- endpoint2: the same connection written the other way round.
3. endpoint1 = endpoint2, an equate wire: connects one of the configuration's own interfaces to an inner component's interface, making them "effectively ... equivalent". This is how a configuration exports an interface that one of its components really implements.

Two further rules from the manual: the two ends must be compatible (the same interface type, or commands and events with the same signature), and "a configuration's external specification elements must all be wired or a compile-time error occurs". If an interface name is left out, as in SenseSendC.Boot -> MainC, the compiler finds the only interface of the right type on MainC.

Two more features every TinyOS program uses

Generic components. Some components need one private copy per user: every module that wants a timer needs its own timer. These are generic components, instantiated in a configuration with new. The manual: generic components "must be instantiated in a configuration before they can be used", while "components without parameters exist as a single instance which is implicitly instantiated". So new TimerMilliC() creates a timer for this module alone, while MainC and LedsC exist once and are shared.

Fan-out and fan-in. One interface may be wired to several others. Then, in the manual's words, the multiple wiring "will lead to multiple signalers ('fan-in') for the events" and "multiple functions being executed ('fan-out') when commands ... are called". A boot signal wired to three components reaches all three.

Parameterised interfaces. A component can provide many copies of one interface, told apart by a number: the scheduler's TaskBasic interface in [TinyOS: Components, Tasks and the Scheduler] is declared that way, and each task gets its number from the unique() function at compile time.

Worked example: an application that uses every feature

The program below has five files. It defines an interface, Tick, with one command and one event; a module, TickerP, that provides Tick by counting timer fires and signalling when it reaches a limit; a configuration, TickerC, that exports Tick and wires TickerP to a generic timer; a module, CountC, that uses Tick; and the top-level configuration, CountAppC, that wires the application together.

Figure 28.1 The wiring of the worked application, drawn from its source

The interface. The provider implements start; the user implements reached.

// A bidirectional interface: the provider implements the command,
// the user implements the event.
interface Tick {
  command void start(uint16_t limit);
  event void reached(uint16_t count);
}

The provider module. It provides Tick and uses a timer. Its command starts the timer; its handler for the timer's event counts, and signals Tick's event when the count reaches the goal.

module TickerP {
  provides interface Tick;
  uses interface Timer<TMilli>;
}
implementation {
  uint16_t count = 0;
  uint16_t goal = 0;

  command void Tick.start(uint16_t limit) {
    goal = limit;
    count = 0;
    call Timer.startPeriodic(100);
  }

  event void Timer.fired() {
    count++;
    if (count == goal) {
      call Timer.stop();
      signal Tick.reached(count);
    }
  }
}

The exporting configuration. TickerC offers Tick to the outside world, but TickerP is the one that implements it, so the two are equated with =. TickerP's used Timer is linked with -> to a fresh timer made with new.

configuration TickerC {
  provides interface Tick;
}
implementation {
  components TickerP, new TimerMilliC();

  Tick = TickerP.Tick;              // export: TickerC's Tick is TickerP's
  TickerP.Timer -> TimerMilliC;     // wire: TickerP uses what the timer provides
}

The user module. It uses Tick, so it must implement Tick's event, reached. On boot it asks for four ticks; each time the goal is reached it lights an LED and asks for twice as many.

module CountC {
  uses interface Boot;
  uses interface Tick;
  uses interface Leds;
}
implementation {
  event void Boot.booted() {
    call Tick.start(4);
  }

  event void Tick.reached(uint16_t count) {
    call Leds.led0On();
    call Tick.start(count * 2);     // go again, waiting twice as long
  }
}

The application. The top-level configuration names the components and links each used interface of CountC to a provider.

configuration CountAppC { }
implementation {
  components MainC, LedsC, CountC, TickerC;

  CountC.Boot -> MainC.Boot;
  CountC.Tick -> TickerC.Tick;
  CountC.Leds -> LedsC.Leds;
}

What the compiler checked, and what it said. Built for the TelosB inside the TinyOS 2.1.2 laboratory, the application compiled with no warning from its own files and reported 2,388 bytes of program memory and 40 bytes of RAM. In compiling it, nesC verified every rule of this chapter: that CountC implements reached because it uses Tick; that TickerP implements start because it provides Tick; that every -> runs from a used interface to a provided one of the same type; and that TickerC's own interface is wired. Break any of those and the program does not compile.

Following one call through the wiring. When CountC runs call Tick.start(4), the wiring sends it to TickerC's Tick, which the = has made the same as TickerP's Tick, so TickerP's start command runs. When TickerP runs signal Tick.reached(count), the same wires carry it back, and CountC's reached handler runs. Neither module names the other anywhere: they know only the interface. Replace TickerP with a different module that provides Tick, change one line of TickerC, and CountC does not change at all.

Distinctions

What it does not mean

A configuration is not a module with no code. It has no code because its job is different: assembling components, not implementing behaviour.

Wiring is not a function call. It is a compile-time connection; the calls it enables cost no more than an ordinary function call, because the compiler resolves them.

provides does not mean "calls". A component that provides an interface implements its commands and signals its events; the component that uses it calls the commands and handles the events.

new does not allocate memory at run time. A generic component is instantiated when the program is compiled; nothing is created while it runs.

Quick revision

• nesC: C with components; programs "built out of components, which are assembled ('wired')".
• Module: code. Configuration: components and wiring only.
• Interfaces are bidirectional: commands implemented by the provider, events by the user.
• Wiring: -> used to provided (link); <- reversed; = equate, to export an interface; ends must be compatible; a configuration's own interfaces must all be wired.
• Generic components with new (one per instance, e.g. TimerMilliC); others are single instances (MainC, LedsC).
• Fan-out and fan-in from multiple wiring; parameterised interfaces numbered with unique().
• Worked CountApp: interface Tick, TickerP provides, TickerC exports with =, CountC uses; compiled for TelosB: 2,388 bytes ROM, 40 bytes RAM.

Test yourself

1. Distinguish a module and a configuration in nesC. A module implements behaviour in C-like code: command and event handlers, variables and tasks. A configuration contains no code; it names components and wires their interfaces together, building a larger component or a whole application.

2. What does it mean that nesC interfaces are bidirectional? An interface contains commands, which the providing component implements, and events, which the using component implements. Wiring a user to a provider connects both directions, so the provider can call back into the user, which is how split-phase completion events reach the caller.

3. Explain the three wiring statements. endpoint1 -> endpoint2 links a used interface to a provided interface inside a configuration; <- is the same written in reverse; endpoint1 = endpoint2 equates one of the configuration's own interfaces with an inner component's, exporting it.

4. In the worked example, why does TickerC use = for Tick but -> for Timer? Tick is TickerC's own provided interface, implemented by the inner module TickerP, so it is equated to export it. Timer is an interface TickerP uses and an inner timer component provides, so it is linked from user to provider.

5. What is a generic component? Give an example. A component with parameters that must be instantiated in a configuration with new, each instantiation a separate copy, such as new TimerMilliC(), which gives each user its own timer. A non-generic component such as MainC exists once.

configuration BlinkTaskAppC { }
implementation {
  components MainC, LedsC, BlinkTaskC;
  components new TimerMilliC() as T0;
  components new TimerMilliC() as T1;
  components new TimerMilliC() as T2;

  BlinkTaskC.Boot -> MainC;
  BlinkTaskC.Timer0 -> T0;
  BlinkTaskC.Timer1 -> T1;
  BlinkTaskC.Timer2 -> T2;
  BlinkTaskC.Leds -> LedsC;
}

The module, line by line

#include "Timer.h". Brings in the definitions of timer precisions, among them TMilli.

module BlinkTaskC { ... }. The specification: this module uses five interfaces and provides none. Using them means it will call their commands and must implement their events: Boot.booted(), and fired() for each of the three timers.

uses interface Timer<TMilli> as Timer0. One interface type, used three times, so each use is renamed with as. The type parameter TMilli sets the timer's precision. TEP 102 defines it precisely: one second contains 1,024 binary milliseconds, and TMilli means "1024 ticks per second". A period of 250 therefore means 250 / 1,024 of a second, about 0.244 seconds, not a quarter of a second exactly. The next chapter's simulator log shows exactly that.

uint16_t toggles = 0. A variable in the module's frame: allocated when the program is compiled, private to this module, kept for the life of the program.

task void toggle0() { ... }. A task, declared with the task keyword, taking no parameters (TinyOS 2's basic tasks never do). It increments the counter, calls the command Leds.led0Toggle(), and prints a debugging line. Three separate tasks are needed because a basic task cannot be told which LED to toggle.

event void Boot.booted(). The first code of the application to run. TinyOS's boot sequence (TEP 107) initialises the system and then signals booted() through MainC. The handler calls startPeriodic on each timer, a command that returns at once; the timers now run on their own.

event void Timer0.fired(). Signalled every 250 binary milliseconds. It prints a line and posts toggle0. Posting returns immediately; the handler ends; the scheduler will run the task when its turn comes.

The configuration, line by line

configuration BlinkTaskAppC { }. The top-level configuration: an empty specification, because the whole application provides and uses nothing outside itself.

components MainC, LedsC, BlinkTaskC. Three single-instance components: the system's boot component, the LED driver, and our module.

components new TimerMilliC() as T0; ... Three generic timer components, each a separate instance, so each timer can run at its own period.

BlinkTaskC.Boot -> MainC. A link wire from the module's used Boot to MainC's provided Boot; the interface name on MainC is left out because it has only one Boot. The other four lines wire the three timers and the LEDs the same way.

What happens, in order

1. The node powers up. TinyOS initialises its components and signals Boot.booted().
2. booted() starts three timers and returns. The scheduler finds no tasks and puts the processor to sleep.
3. After 250 binary milliseconds the hardware timer interrupts; the timer component signals Timer0.fired(); the handler posts toggle0 and returns.
4. The scheduler runs toggle0 to completion: LED 0 changes state.
5. Nothing is queued: the processor sleeps until the next timer interrupt.
6. At 500 binary milliseconds, Timer0 and Timer1 are both due. Their events are signalled one after the other, each posting its task; the scheduler runs the tasks in FIFO order.

So LED 0 changes every 250, LED 1 every 500 and LED 2 every 1,000 binary milliseconds: a three-bit binary counter in lights.

Worked example: the numbers

The compiled size. Built for the TelosB by this book's checker, BlinkTask compiled with no warning from its own files and reported 2,682 bytes of program memory and 60 bytes of RAM. The three timers, the LED driver, the scheduler and the boot sequence are all included. Against the 48 kB of flash on the TelosB's MSP430F1611, that is about 5.5 per cent.

The toggles in one second. Timer0 fires at 250, 500, 750 and 1,000 binary milliseconds, 4 times; Timer1 at 500 and 1,000, 2 times; Timer2 at 1,000, once. So by 1,000 binary milliseconds, which is 1,000 / 1,024 of a second, about 0.977 seconds, the counter reads 4 + 2 + 1 = 7. The next chapter's simulator run ends with exactly "toggle 7".

The timing unit, worked. 250 binary milliseconds is 250 / 1,024 of a second:

seconds, which is where the first toggle comes in the simulator.

Distinctions

What it does not mean

startPeriodic(250) is not a quarter of a second. TMilli is 1,024 ticks a second, so it is 0.244 seconds.

Posting a task does not run it. It queues it; the handler returns first.

A task is not needed for every event. TinyOS's Blink toggles directly in the event, which is right for so little work. The task exists in BlinkTask to show the structure a larger job needs.

Three timers are not three threads. They are three instances of a timer component, all driven by one hardware timer and one scheduler.

Quick revision

• TinyOS Blink: module BlinkC and configuration BlinkAppC; three timers at 250, 500, 1,000; each fired() toggles one LED directly.
• BlinkTask: each fired() posts a task; the task toggles the LED and counts in the frame.
• uses interface Timer<TMilli> as Timer0: one interface type used three times, renamed with as.
• TMilli is 1,024 ticks a second (TEP 102): 250 means 0.244140625 s.
• Configuration: MainC (Boot), LedsC, three new TimerMilliC(); wired with ->.
• Order: boot, start timers, sleep; interrupt, fired(), post, return; task runs to completion; sleep.
• Compiled for TelosB: 2,682 bytes ROM, 60 bytes RAM; toggles in the first 1,000 binary milliseconds: 4 + 2 + 1 = 7.

Test yourself

1. Explain the structure of the Blink application. A module that uses Boot, three Timer<TMilli> interfaces and Leds, and a top-level configuration that wires it to MainC, LedsC and three instances of TimerMilliC. On boot the module starts the timers with periods 250, 500 and 1,000; each timer's fired() event toggles one LED.

2. Modify Blink so that the LEDs are toggled by tasks. Why might you do this? Declare a task for each LED, and in each fired() event post the task instead of toggling; the task calls the toggle command. For an LED it makes no difference, but for real work it keeps the event handler short, so other events and tasks are not delayed.

3. What does TMilli mean, and how long is a period of 250? A timer precision of 1,024 ticks per second, binary milliseconds (TEP 102). 250 of them are 250 / 1,024 = 0.244140625 seconds.

4. Why is each timer declared with as? Because the module uses the same interface type three times, and each use needs its own name so that it can be wired separately and its events told apart.

5. By the end of the first 1,000 binary milliseconds, how many toggles has BlinkTask made? Timer0 has fired 4 times, Timer1 twice and Timer2 once: 7 toggles.

TOSSIM's answer is to run the real program: "Compiling unchanged TinyOS applications directly into its framework, TOSSIM can simulate thousands of motes running complete applications."

How TOSSIM runs a TinyOS program

It replaces the components that touch hardware. In the words of TinyOS's own tutorial, "TOSSIM simulates entire TinyOS applications. It works by replacing components with simulation implementations." A simulated millisecond timer, for example, replaces the real one. Everything above those components, the application and most of TinyOS, is the same code that would run on a mote.

It is a discrete event simulator. "When it runs, it pulls events of the event queue (sorted by time) and executes them." An event can stand for a hardware interrupt or for a higher-level happening such as a packet's reception, and "tasks are simulation events, so that posting a task causes it to run a short time (e.g., a few microseconds) in the future". Simulated time does not tick along steadily: it jumps from one event to the next. TinyOS 2.1.2's simulator counts it in ticks of which there are 10,000,000,000 per simulated second, a tenth of a nanosecond each.

It is a library, driven by a script. "TOSSIM is a library: you must write a program that configures a simulation and runs it." The program can be written in Python or in C++. Python "allows you to interact with a running simulation dynamically, like a powerful debugger", while C++ runs faster. The Python interface is built on the C++ one, which calls the simulated program through plain C functions, because "C++ doesn't understand nesC, and nesC doesn't understand C++".

It is built with make micaz sim. The sim option does the work in five steps: it writes an XML description of the application (app.xml, which names every variable and its type), compiles the application for simulation into sim.o, compiles the C++ and Python support, links all three into a shared library, _TOSSIMmodule.so, and copies the Python module TOSSIM.py into the directory. The TinyOS 2.0 tutorial is plain about the platform: "Currently, the only platform TOSSIM supports is the micaz."

A note for the laboratory. On the current Ubuntu that this book's TinyOS 2.1.2 laboratory runs, the simulator build needed an older C compiler, gcc 10, and two extra compiler flags. They go in the application's Makefile; the first line names the application's top-level configuration:

COMPONENT=BlinkTaskAppC
override GCC = gcc-10
export GCC
PFLAGS += -fgnu89-inline -fsigned-char
include $(MAKERULES)

One mote: BlinkTask's execution log

The first simulation exercise asks to "Simulate a single sensor node in TOSSIM and observe execution logs". The program to simulate is BlinkTask from [Blink: A TinyOS Application Read Line by Line]: three timers at 250, 500 and 1,000 binary milliseconds, each of whose events posts a task that toggles one LED and counts the toggles, with a dbg statement in each event and each task. After make micaz sim, this Python script, run.py, simulates one mote for 1.1 simulated seconds:

from TOSSIM import *
import sys

t = Tossim([])
t.addChannel("BlinkTask", sys.stdout)
m = t.getNode(1)
m.bootAtTime(0)
while t.time() < 1.1 * t.ticksPerSecond():
    t.runNextEvent()

Line by line. The import loads the module the build made. Tossim([]) creates the simulator; the empty list means the script will not inspect any of the program's variables. addChannel sends the debugging channel named BlinkTask to the screen. getNode(1) is the mote with ID 1, and bootAtTime(0) boots it at tick 0. The loop runs events, one at a time, until the simulated clock passes 1.1 seconds. Run with python2 run.py, it printed:

DEBUG (1): booted at 0:0:0.000000000
DEBUG (1): Timer0 fired at 0:0:0.244140635
DEBUG (1): task toggle0 ran, toggle 1
DEBUG (1): Timer0 fired at 0:0:0.488281260
DEBUG (1): task toggle0 ran, toggle 2
DEBUG (1): Timer1 fired at 0:0:0.488281280
DEBUG (1): task toggle1 ran, toggle 3
DEBUG (1): Timer0 fired at 0:0:0.732421885
DEBUG (1): task toggle0 ran, toggle 4
DEBUG (1): Timer0 fired at 0:0:0.976562510
DEBUG (1): task toggle0 ran, toggle 5
DEBUG (1): Timer1 fired at 0:0:0.976562530
DEBUG (1): task toggle1 ran, toggle 6
DEBUG (1): Timer2 fired at 0:0:0.976562550
DEBUG (1): task toggle2 ran, toggle 7

What the log shows about the TinyOS runtime.

1. Every line carries the node's ID, "DEBUG (1)". With a hundred motes in one simulation, that is how the lines are told apart.
2. Time is in binary milliseconds. Timer0's period is 250 binary milliseconds, 250 / 1,024 = 0.244140625 seconds. The log says 0.244140635, ten billionths of a second later, far below anything a millisecond timer can notice. By 1,000 binary milliseconds, 1,000 / 1,024 = 0.9765625 seconds, the counter reads 7, exactly as the previous chapter worked out (4 + 2 + 1 = 7).
3. An event posts, and its task runs after it. Every "fired" line is followed by its task's line. At 0.488 seconds Timer0 and Timer1 are both due; the log shows Timer0's event, then its task, then Timer1's event 20 nanoseconds later, then its task. The events are short, the work is deferred, and each task runs to completion before the next event is handled.
4. Nothing happens between events. The next line would be Timer0 at 1,250 binary milliseconds, about 1.22 seconds, after the script has stopped. Between the lines there is simply no event, which on a real mote is time spent asleep.

dbg: how a simulated mote prints

TOSSIM gives a program four printing calls: dbg prints a line preceded by the node ID; dbg_clear prints without the ID (for printing something long, such as a packet, over several calls); dbgerror and dbgerror_clear do the same for errors, whose lines begin ERROR instead of DEBUG. The first argument names the channel, and the rest are exactly those of printf. BlinkTask prints on the channel BlinkTask.

A channel is just a string, and nothing is printed unless the script connects the channel to an output with addChannel. A statement can name several channels separated by commas, and "A channel can have multiple outputs", for instance the screen and a log file. Channels are how a large simulation stays readable: switch on the channel you are debugging and leave the rest silent. dbg statements print only in the simulator; BlinkTask compiled for the TelosB with every one of them in its source.

How TOSSIM models the radio

TinyOS 1: a graph of bit errors. The 2003 TOSSIM modelled the network as "a directed graph, in which each vertex is a node, and each edge has a bit error probability". Because the edge from u to v is separate from the edge from v to u, links could be asymmetric, and a missing edge could express the hidden terminal problem: edges from a to b and from b to c but none between a and c.

TinyOS 2: gains, noise and the SNR. The TinyOS 2 simulator works on packets and signal strengths instead. Its tutorial states the starting point: "When you start TOSSIM, no node can communicate with any other." The script builds the network by adding links to the Radio object:

1. r.add(src, dest, gain) adds a directed link: "When src transmits, dest will receive a packet attenuated by the gain value." Adding the link from 1 to 2 does not add the link from 2 to 1, so asymmetric links come free.
2. The gain is the received power. TinyOS 2.1.2's packet model puts every packet on the air at 0 dBm, so a gain of -80 dB means the receiver hears the packet at -80 dBm. The tutorial's topology file says the same in its own example: "1 2 -54.0 means that when 1 transmits 2 hears it at -54 dBm".
3. The noise comes from a recording. The model TinyOS 2.1.2 wires in is CpmModelC, whose source describes it: "CPM (closest-pattern matching) is a wireless noise simulation model based on statistical extraction from empirical noise data", "exploiting time-correlated noise characteristics", after Lee and Levis's "Improving Wireless Simulation through Noise Modeling" (IPSN 2007). The script gives each node readings from a noise trace with addNoiseTraceReading and then calls createNoiseModel. TinyOS ships traces in tos/lib/tossim/noise, among them casino-lab.txt and meyer-heavy.txt.
4. Each packet is a coin toss weighted by its SNR. The SNR is the signal minus the noise, in dB. The model converts it into a probability of reception with a function whose comment says it is "Based on CC2420 measurement", and then draws a random number: below the probability the packet is received, above it the packet is lost.

A packet is judged twice. Reading CpmModelC.nc shows the draw is made when the packet starts to arrive, against the noise at that moment, and again when it finishes, against the noise plus the power of any other packets arriving at the same time. A packet is also lost if the receiver is already receiving one, if the receiver is transmitting, or if a newer packet arrives so much stronger that the older one fails its draw against it. That is how collisions arise in the simulation.

Before sending, the channel is checked. The default MAC is "for a CSMA protocol": a node transmits only when the channel is clear, and CpmModelC calls it clear when what the node hears, its noise plus any packets arriving, is below -72 dBm, a threshold its comment says "comes from the CC2420 data sheet". The medium access ideas behind this are in [Contention: ALOHA and CSMA].

The reception curve, computed

The next program computes the chance of receiving a packet at each SNR by two published rules: the one TOSSIM uses, copied from CpmModelC.nc, and the one Zuniga and Krishnamachari derived for the MICA2 mote's radio (non-coherent FSK, NRZ encoding) in their equation 6, for a 50-byte frame.

# The chance that a packet is received, against its signal-to-noise
# ratio (SNR), by two published rules.
import math

def tossim(snr_db):
    # TinyOS 2.1.2, CpmModelC.nc: "Based on CC2420 measurement"
    pse = 0.5 * math.erfc(0.9794 * (snr_db - 2.3851) / math.sqrt(2))
    return (1 - pse) ** (23 * 2)

def mica2(snr_db, f=50):
    # Zuniga and Krishnamachari, equation 6: MICA2's FSK radio, NRZ
    # encoding, a frame of f bytes
    snr = 10 ** (snr_db / 10)            # decibels to a plain ratio
    return (1 - 0.5 * math.exp(-snr / 2 / 0.64)) ** (8 * f)

print("SNR (dB)   TOSSIM, CC2420   MICA2 model, 50 bytes")
for snr_db in range(0, 13):
    print("%8d   %14.3f   %21.3f" % (snr_db, tossim(snr_db), mica2(snr_db)))

SNR (dB)   TOSSIM, CC2420   MICA2 model, 50 bytes
       0            0.000                   0.000
       1            0.000                   0.000
       2            0.000                   0.000
       3            0.000                   0.000
       4            0.068                   0.000
       5            0.786                   0.000
       6            0.991                   0.000
       7            1.000                   0.018
       8            1.000                   0.235
       9            1.000                   0.668
      10            1.000                   0.922
      11            1.000                   0.989
      12            1.000                   0.999

Reading the curves. Both rise from almost nothing to almost certain across a few dB. TOSSIM's goes from 0.068 at 4 dB to 0.991 at 6 dB; the MICA2 model from 0.018 at 7 dB to 0.989 at 11 dB. Below the rise a link is useless, above it perfect. Its steepness is why the next experiment moves from every packet to none within a few dB of gain. The 0.9794, the 2.3851 and the power 23 × 2 are constants written into TinyOS's code; the chapter uses them as the simulator does and does not claim more for them than the code's own comment.

Two motes, ten gains: packet loss against signal strength

The second exercise asks to "Simulate packet transmission between two motes and analyze signal strength and packet loss under varying radio gain values". Rather than repeat the run ten times, our program RadioTest runs one sender and ten receivers at once, each receiver on its own link with its own gain, so a single simulation sweeps the whole range. The receivers never transmit, so they cannot disturb one another.

RadioTestC.nc, the module:

module RadioTestC {
  uses interface Boot;
  uses interface SplitControl as RadioControl;
  uses interface Timer<TMilli> as SendTimer;
  uses interface Timer<TMilli> as ReportTimer;
  uses interface AMSend;
  uses interface Receive;
}
implementation {
  message_t packet;
  bool busy = FALSE;
  uint16_t sent = 0;          // node 1 counts the packets it sends
  uint16_t received = 0;      // every other node counts what it hears

  event void Boot.booted() {
    call RadioControl.start();
    call ReportTimer.startOneShot(11000);
  }

  event void RadioControl.startDone(error_t err) {
    if (err != SUCCESS) call RadioControl.start();
    else if (TOS_NODE_ID == 1) call SendTimer.startPeriodic(100);
  }
  event void RadioControl.stopDone(error_t err) { }

  event void SendTimer.fired() {
    if (busy || sent == 100) return;
    if (call AMSend.send(AM_BROADCAST_ADDR, &packet, 2) == SUCCESS) {
      busy = TRUE;
      sent++;
    }
  }
  event void AMSend.sendDone(message_t* msg, error_t err) { busy = FALSE; }

  event message_t* Receive.receive(message_t* msg, void* payload, uint8_t len) {
    received++;
    return msg;
  }

  event void ReportTimer.fired() {
    if (TOS_NODE_ID == 1) dbg("Radio", "sent %u packets\n", sent);
    else dbg("Radio", "received %u of them\n", received);
  }
}

RadioTestAppC.nc, the configuration:

configuration RadioTestAppC { }
implementation {
  components MainC, RadioTestC, ActiveMessageC;
  components new TimerMilliC() as SendTimerC;
  components new TimerMilliC() as ReportTimerC;
  components new AMSenderC(7);
  components new AMReceiverC(7);

  RadioTestC.Boot -> MainC;
  RadioTestC.RadioControl -> ActiveMessageC;
  RadioTestC.SendTimer -> SendTimerC;
  RadioTestC.ReportTimer -> ReportTimerC;
  RadioTestC.AMSend -> AMSenderC;
  RadioTestC.Receive -> AMReceiverC;
}

What it does. Every node starts its radio, a split-phase operation that ends in startDone ([Commands, Events and Split-phase Operation]). Node 1, and only node 1, then starts a periodic timer and broadcasts a packet with 2 bytes of payload every 100 binary milliseconds until it has sent 100; the busy flag keeps it from sending a second packet before the first one's sendDone. Every other node counts what it receives. Eleven thousand binary milliseconds after booting, each node reports on the channel Radio. The last packet goes out after about 100 × 100 = 10,000 binary milliseconds, about 9.77 seconds, so the reports come after the sending is over. The program also compiled for the TelosB, to 11,120 bytes of program memory and 370 bytes of RAM, radio stack included.

The script, run.py, takes the name of a noise trace as its argument:

from TOSSIM import *
import os
import sys

trace = sys.argv[1]                      # which recorded noise to use
gains = [-60, -80, -88, -90, -91, -92, -93, -94, -95, -96]

t = Tossim([])
t.addChannel("Radio", sys.stdout)
t.randomSeed(1)                          # the same random draws every run
r = t.radio()
for i, g in enumerate(gains):
    r.add(1, i + 2, g)                   # node i + 2 hears node 1 at g dBm
print("node: " + "".join("%5d" % (i + 2) for i in range(len(gains))))
print("gain: " + "".join("%5d" % g for g in gains))

folder = os.path.join(os.environ["TOSROOT"], "tos/lib/tossim/noise")
noise = [int(v) for v in open(os.path.join(folder, trace)).read().split()[:1000]]
s = sorted(noise)
print("noise: half at or below %d dBm, 9 in 10 at or below %d dBm, loudest %d dBm"
      % (s[499], s[899], s[-1]))
for n in range(1, len(gains) + 2):
    m = t.getNode(n)
    for v in noise:
        m.addNoiseTraceReading(v)        # what this node's radio will hear
    m.createNoiseModel()
    m.bootAtTime(1000 * n)

while t.time() < 12 * t.ticksPerSecond():
    t.runNextEvent()

Line by line. The links go only from node 1 to each receiver, one gain each, from -60 dB down to -96 dB, closely spaced where the loss is expected to change. Every node is given the same first 1,000 readings of the chosen trace, and the script prints a summary of them. randomSeed(1) fixes the random draws, so the same run gives the same counts every time; another seed gives slightly different ones. Node n boots at 1,000 × n ticks, a tenth of a microsecond apart, and the simulation runs for 12 simulated seconds.

Run with python2 run.py casino-lab.txt, the quieter of the two traces:

node:     2    3    4    5    6    7    8    9   10   11
gain:   -60  -80  -88  -90  -91  -92  -93  -94  -95  -96
noise: half at or below -98 dBm, 9 in 10 at or below -97 dBm, loudest -54 dBm
DEBUG (1): sent 100 packets
DEBUG (2): received 100 of them
DEBUG (3): received 100 of them
DEBUG (4): received 100 of them
DEBUG (5): received 100 of them
DEBUG (6): received 100 of them
DEBUG (7): received 94 of them
DEBUG (8): received 47 of them
DEBUG (9): received 1 of them
DEBUG (10): received 0 of them
DEBUG (11): received 0 of them

The same script with the noisier trace:

$ python2 run.py meyer-heavy.txt

node:     2    3    4    5    6    7    8    9   10   11
gain:   -60  -80  -88  -90  -91  -92  -93  -94  -95  -96
noise: half at or below -98 dBm, 9 in 10 at or below -81 dBm, loudest -39 dBm
DEBUG (1): sent 100 packets
DEBUG (2): received 98 of them
DEBUG (3): received 77 of them
DEBUG (4): received 59 of them
DEBUG (5): received 66 of them
DEBUG (6): received 54 of them
DEBUG (7): received 46 of them
DEBUG (8): received 26 of them
DEBUG (9): received 2 of them
DEBUG (10): received 0 of them
DEBUG (11): received 0 of them

Figure 30.1 Packets received out of 100, per link, in the two runs above (the -60 dB link, off the chart, received 100 and 98)

Worked example: reading the two runs

Out of 100 packets, the reception ratio of a link is the count divided by 100.

The quiet trace. The noise is at or below -97 dBm nine times in ten. A packet heard at -90 dBm then has an SNR of 7 dB or more, the top of TOSSIM's curve: all 100 arrive. At -93 dBm the SNR is about 4 to 5 dB, the steep part: 47 arrive. At -94 dBm, about 3 to 4 dB, the foot of the curve: 1 arrives. The whole fall, from 94 to 1, happens between -92 and -94 dBm, 2 dB.

The noisy trace. The typical reading is the same, -98 dBm, but one reading in ten or more is -81 dBm or louder, and the loudest is -39 dBm. When a burst of noise overlaps a packet, the packet's SNR drops, and if the burst comes within a few dB of the packet's own strength the packet is lost. A burst at -81 dBm ruins a -88 dBm packet but not a -60 dBm one, which only the rare, loudest bursts can reach. So the -60 dB link loses 2 packets, the -80 dB link loses 23, and the fall is spread over more than 13 dB, from 77 at -80 dBm to 26 at -93 dBm, before the link dies at -94 dBm like the quiet one.

The counts wobble. The noisy run received 59 at -88 dBm but 66 at the weaker -90 dBm. Each packet's fate is a random draw, so a count out of 100 varies by several either way; with another seed the order of these two could reverse. A real measurement repeats the run with several seeds and reports the average.

The transitional region

Zuniga and Krishnamachari summarise what measurements of real sensor networks found: "three distinct reception regions in a wireless link: connected, transitional, and disconnected". "The transitional region is often quite significant in size, and is generally characterized by high-variance in reception rates and asymmetric connectivity." To give the regions edges, they "bound the connected region to PRRs greater than 0.9, and the transitional region to values between 0.9 and 0.1", PRR being the packet reception rate, the reception ratio above. Below 0.1 is the disconnected region.

The runs, classified. In the quiet trace, links from -60 to -92 dB are connected (0.94 or better), only the -93 dB link is transitional (0.47), and from -94 dB they are disconnected. In the noisy trace only the -60 dB link is connected (0.98); every link from -80 to -93 dB is transitional (0.77 down to 0.26); and from -94 dB they are disconnected. Same radio, same gains: the noise made the transitional region at least six times wider, from under 2 dB to at least 13 dB. The paper names the noise floor as "Another important element that determines the transitional region".

Why a transitional region exists at all. The paper identifies two causes. The radio: reception does not jump from 0 to 1 at one SNR but climbs over a few dB, as the curves above showed. And the channel: the signal at a given distance is not fixed, because of shadowing and multipath, so two links of the same length can differ by several dB. Its key finding is that for narrow-band radios the transitional region "is not an artifact of the radio non-ideality, as it would exist even with perfect-threshold receivers because of multi-path fading".

Where it begins and ends, computed. The paper models the channel with the log-normal shadowing path loss model, PL(d) = PL(d0) + 10 n log10(d / d0) + X, where X is a random amount in dB with standard deviation σ. Its equation 10 gives the SNR needed for PRRs of 0.9 and 0.1, and equation 13 the distances at which the transitional region begins and ends, taking the signal to lie within two standard deviations of its average. The program below evaluates them with the paper's section III values: a 50-byte frame, 0 dBm transmitted, a noise floor of -115 dBm, 55 dB of loss at the 1 m reference distance, and a path loss exponent of 4.

# Where the transitional region begins and ends: Zuniga and
# Krishnamachari, equations 10, 13 and 14, with their section III values.
import math

f, Pt, Pn, PL0, n = 50, 0, -115, 55, 4   # bytes, dBm, dBm, dB, exponent

def snr_needed(prr):                     # equation 10, in dB
    return 10 * math.log10(-1.28 * math.log(2 * (1 - prr ** (1 / (8 * f)))))

gU, gL = snr_needed(0.9), snr_needed(0.1)
print("PRR 0.9 needs %.2f dB of SNR; PRR 0.1 needs %.2f dB" % (gU, gL))
for sigma in (0, 2, 4):                  # shadowing, in dB
    ds = 10 ** ((Pn + gU - Pt + PL0 + 2 * sigma) / (-10 * n))
    de = 10 ** ((Pn + gL - Pt + PL0 - 2 * sigma) / (-10 * n))
    print("sigma %d dB: transitional from %4.1f m to %4.1f m, Gamma %.2f"
          % (sigma, ds, de, (de - ds) / ds))

PRR 0.9 needs 9.85 dB of SNR; PRR 0.1 needs 7.57 dB
sigma 0 dB: transitional from 17.9 m to 20.4 m, Gamma 0.14
sigma 2 dB: transitional from 14.2 m to 25.7 m, Gamma 0.81
sigma 4 dB: transitional from 11.3 m to 32.4 m, Gamma 1.86

Reading it. The radio alone needs 9.85 dB of SNR for a PRR of 0.9 and 7.57 dB for 0.1, a band only 2.28 dB wide. With no shadowing (σ = 0) that band is a thin ring, from 17.9 m to 20.4 m. With the paper's σ of 4 dB it stretches from 11.3 m to 32.4 m, the paper's own figures. Γ, the transitional region coefficient, is "the ratio of the radius of the transitional and connected regions", (de - ds) / ds, and "The lower the coefficient the better": 0.14 without shadowing, 1.86 with it, which the paper rounds to 1.9. Beyond 11.3 m, in other words, a link of the same length may be excellent or useless depending on where exactly the nodes stand.

Why it matters. The paper warns that "a large number of the links in the network (even higher than 50%) can be unreliable due to the transitional region" in a dense deployment, and that "the idealized perfect-reception-within-range models used in common network simulation tools can be very misleading". It cites the finding that protocols using the minimum hop-count metric "perform poorly in terms of throughput" and that ETX, the "expected number of transmissions", does best. A protocol that picks the longest hop it can hear will pick transitional links. So sensor network routing measures each link's delivery and prefers links that deliver, which is [Routing Tables and What Happens When the Topology Changes].

From positions to gains. TOSSIM itself knows nothing of positions: the script gives it gains. The TinyOS 2.1.2 distribution includes a tutorial by Zuniga, "Building a Network Topology for TOSSIM", whose program applies this same log-normal model, with a path loss exponent, a shadowing deviation, a noise floor and hardware variation, to nodes on a grid or at random, and writes a file of gain lines ready for the script. Its example parameters for a football field are a path loss exponent of 4.7 and a shadowing deviation of 3.2 dB, and for the aisle of a building 3.3 and 5.5 dB.

What TOSSIM cannot tell you

1. CPU time. "TOSSIM's run-instantly execution model does not capture CPU time." Code takes no simulated time to run, so a task that would take too long on a mote looks fine in TOSSIM.
2. Preemption. Since interrupts are discrete events, "TOSSIM does not model preemption and the resulting possible TinyOS data races". A race between an interrupt and a task cannot appear in the log.
3. Energy. The TinyOS 2 tutorial: "TOSSIM currently does not support gathering power measurements." The energy budget of [How Long a Node Lasts: The Energy Budget Worked Out] is not something TOSSIM measures.
4. Any radio but the one you describe. The gains and the noise are inputs. A simulation with optimistic gains will deliver packets the real field will not.

Distinctions