Routing Challenges and Design Issues in WSNs

The design issues

Al-Karaki and Kamal list the factors that "must be overcome before efficient communication can be achieved in WSNs". Each is a question the designer of a routing protocol must answer.

1. Node deployment. "The deployment can be either deterministic or randomized." Placed by hand, nodes can use pre-determined paths; scattered at random, they must organise themselves, and uneven density may call for clustering. Because radios are short-range, "it is most likely that a route will consist of multiple wireless hops."

2. Energy consumption without losing accuracy. "In a multihop WSN, each node plays a dual role as data sender and data router." A node that dies of flat batteries does not only lose its readings; it breaks routes, and "might require rerouting of packets and reorganization of the network." ([Energy-aware Routing] took this up for ad hoc networks.)

3. The data reporting model. Reporting "can be categorized as either time-driven (continuous), event-driven, query-driven, and hybrid." Time-driven reporting suits periodic monitoring; in event- and query-driven reporting, nodes "react immediately to sudden and drastic changes in the value of a sensed attribute due to the occurrence of a certain event or a query is generated by the BS", which suits time-critical applications. "The routing protocol is highly influenced by the data reporting model with regard to energy consumption and route stability." The program below shows how much.

4. Node and link heterogeneity. Nodes may differ in sensors, in reporting rates and in capability; "hierarchical protocols designate a clusterhead node different from the normal sensors", and cluster heads may be more powerful nodes, which then carry the burden of transmission to the base station.

5. Fault tolerance. "The failure of sensor nodes should not affect the overall task of the sensor network." If nodes fail, routing must form new links and routes, perhaps "rerouting packets through regions of the network where more energy is available", so redundancy is needed at several levels.

6. Scalability. The network may hold "hundreds or thousands, or more" nodes, and routing must work at that size and respond to events, while most nodes sleep until something happens.

7. Network dynamics. Most designs assume stationary nodes, but base stations or sensors may move, and the phenomenon itself may be static (a forest watched for fire) or moving (a tracked target), which generates periodic traffic.

8. The transmission medium. Links suffer the wireless channel's fading and errors, rates are low ("on the order of 1-100 kb/s"), and the MAC below routing matters ([MAC Protocols for Sensor Networks: The Job and Where the Energy Goes]).

9. Connectivity. High density means nodes are expected to be "highly connected", but failures shrink the network, and connectivity "depends on the, possibly random, distribution of nodes."

10. Coverage. Each sensor sees only a limited area, so "area coverage is also an important design parameter" ([Deployment and Coverage: Random Against Grid]).

11. Data aggregation. "similar packets from multiple nodes can be aggregated so that the number of transmissions is reduced", by functions such as "duplicate suppression, minima, maxima and average", or by signal processing (data fusion).

12. Quality of service. Some data is useless if late, so "bounded latency for data delivery is another condition for time-constrained applications", but "in many applications, conservation of energy, which is directly related to network lifetime, is considered relatively more important than the quality of data sent." The routing protocol must strike the balance the application needs.

Akyildiz and colleagues give the same themes as principles for the network layer: power efficiency is always important; sensor networks are mostly data-centric; data aggregation is useful only when it does not hinder the collaborative effort of the nodes; and an ideal sensor network has attribute-based addressing and location awareness.

One field, four ways of reporting

The program scatters 100 nodes at random over a 100 m by 100 m field with the base station at a corner and a radio range of 20 m, builds each node's shortest-hop route to the base station, and counts the transmissions each node makes in a day, its own and those it relays. The traffic is illustrative: time-driven reporting every 5 minutes, first relayed as it is and then aggregated so that each node sends one packet per period for its whole subtree; event-driven reporting of 4 events a day at random places, each reported by the nodes within 15 m; and query-driven reporting of 24 queries a day, each flooded to every node and answered by the nodes in a random 30 m square. Events and queries are averaged over a year.

# One field, several routing design issues at once. 100 nodes scattered at
# random over 100 m by 100 m, the base station at a corner, radio range 20 m.
# Each node's route is its shortest-hop path to the base station, and every
# packet is transmitted once by its source and once by every relay on its way.
import random
from collections import deque

rnd = random.Random(54)
N, SIDE, RANGE = 100, 100.0, 20.0
pts = [(0.0, 0.0)] + [(rnd.uniform(0, SIDE), rnd.uniform(0, SIDE)) for _ in range(N)]

def near(a, b, r=RANGE):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 <= r * r

# the shortest-hop tree: breadth-first search outwards from the base station (0)
parent, hops, queue = {0: None}, {0: 0}, deque([0])
while queue:
    u = queue.popleft()
    for v in range(1, N + 1):
        if v not in hops and near(pts[u], pts[v]):
            hops[v], parent[v] = hops[u] + 1, u
            queue.append(v)
reached = [v for v in hops if v]

def carried(reports):
    """reports: packets each node originates per day. Returns the packets each
    node transmits per day: its own and every one it relays."""
    tx = dict.fromkeys(reached, 0)
    for src, k in reports.items():
        v = src
        while v:
            tx[v] += k
            v = parent[v]
    return tx

def year_of(events, per_day, radius):
    """Reports per day, averaged over a year of events at random places: every
    node within `radius` of an event (or inside a query's square) reports once."""
    count = dict.fromkeys(reached, 0)
    for _ in range(per_day * 365):
        spot = (rnd.uniform(0, SIDE), rnd.uniform(0, SIDE))
        for v in reached:
            if events(spot, pts[v], radius):
                count[v] += 1
    return {v: c / 365 for v, c in count.items()}

in_circle = near
in_square = lambda s, p, half: abs(s[0] - p[0]) <= half and abs(s[1] - p[1]) <= half

models = {
    "time-driven, every 5 min": carried(dict.fromkeys(reached, 288)),
    "time-driven, aggregated": dict.fromkeys(reached, 288),   # one packet per period each
    "event-driven, 4 events/day": carried(year_of(in_circle, 4, 15.0)),
}
replies = carried(year_of(in_square, 24, 15.0))      # 24 queries a day, 30 m squares
models["query-driven, 24/day"] = {v: replies[v] + 24 for v in reached}  # + the query flood

far = max(hops.values())
print("reached %d of %d nodes; hops to the base station: 1 to %d, mean %.2f"
      % (len(reached), N, far, sum(hops[v] for v in reached) / len(reached)))
print("the base station's own neighbours: %d" % sum(1 for v in reached if hops[v] == 1))
print("%-28s %10s %9s %9s %7s" % ("reporting model", "total/day", "mean", "busiest", "ratio"))
for name, tx in models.items():
    total, busiest = sum(tx.values()), max(tx.values())
    print("%-28s %10.0f %9.1f %9.1f %7.1f"
          % (name, total, total / len(tx), busiest, busiest / (total / len(tx))))

reached 100 of 100 nodes; hops to the base station: 1 to 9, mean 4.94
the base station's own neighbours: 2
reporting model               total/day      mean   busiest   ratio
time-driven, every 5 min         142272    1422.7   24480.0    17.2
time-driven, aggregated           28800     288.0     288.0     1.0
event-driven, 4 events/day          121       1.2      21.5    17.7
query-driven, 24/day               3286      32.9     184.0     5.6

Figure 54.1 The program's field: routes to the base station, shaded by how much each node relays under time-driven reporting

Reading it: deployment and multiple hops. Random deployment gave a connected network, every node reaching the base station, but in up to 9 hops, 4.94 on average: routes are long even in a small field.

Reading it: the dual role. With time-driven reporting every node originates 288 packets a day, yet the network makes 142,272 transmissions, about 4.9 per packet, the mean hop count. The busiest node transmits 24,480 a day, 17.2 times the average: it is one of only 2 nodes beside the base station, and relays for most of the field. It will run out of energy first, and when it does, the routes of everything behind it must be rebuilt through the one remaining neighbour. Fault tolerance and energy are the same problem seen twice.

Reading it: the reporting model. The same field makes 142,272 transmissions a day time-driven, 3,286 query-driven and 121 event-driven. The model, set by the application, decides the traffic by a factor of more than a thousand, and so decides which routing protocol makes sense: proactive routes are worth their upkeep for continuous traffic, not for a few events a day.

Reading it: aggregation. Aggregating each period's readings on the way cuts the total to 28,800 transmissions and makes every node's load equal, a ratio of 1.0. It works only when the application can use a combined value (a maximum, an average, a count), which is why Akyildiz and colleagues attach the condition that aggregation must not hinder the collaborative task.

Distinctions

What it does not mean

Many-to-one is not the only traffic. Queries flow out from the base station, and some applications need node-to-node or multicast flows; the survey notes that many-to-one "does not prevent the flow of data to be in other forms".

A connected network is not a durable one. The field above is connected, but two nodes carry nearly all its traffic, and losing either reshapes the whole network.

Aggregation is not free accuracy. It reduces transmissions only when a combined value is acceptable, and it delays data while a node waits for its children.

The design issues are not independent. Deployment sets connectivity and hop counts, the reporting model sets the load, the load sets which nodes die first, and their death tests fault tolerance.

Quick revision

• Different from other networks: no global addressing, many sources to one base station, tight energy, processing and storage, mostly stationary nodes, application specific, location matters, redundant data (data-centric, attribute-based).
• Twelve design issues (Al-Karaki and Kamal): node deployment; energy without losing accuracy (nodes are senders and routers); data reporting model (time-driven, event-driven, query-driven, hybrid); node/link heterogeneity; fault tolerance; scalability; network dynamics; transmission medium (1 to 100 kb/s); connectivity; coverage; data aggregation; quality of service (bounded latency against lifetime).
• Program (100 random nodes, corner base station): up to 9 hops, mean 4.94; only 2 base-station neighbours; time-driven 142,272 transmissions a day, busiest node 24,480 (17.2 times the mean); aggregated 28,800, all equal; query-driven 3,286; event-driven 121.

Test yourself

1. Why can traditional IP-based routing not simply be used in a wireless sensor network? There are too many nodes for a global addressing scheme to be worth its overhead, and the application wants data rather than node identities. Traffic flows mostly from many sources to a single base station; nodes are tightly limited in energy, processing and memory; links change as nodes fail and sleep; and the data from nearby nodes is redundant, so routing should aggregate it and address it by attributes.

2. List and explain any six routing design issues in WSNs. Node deployment: deterministic placement allows fixed paths, random scattering needs self-organising multi-hop routes. Energy consumption without losing accuracy: every node is both a sender and a router, and a node's death forces rerouting. Data reporting model: time-driven, event-driven, query-driven or hybrid reporting determines traffic, energy and route stability. Fault tolerance: failed nodes must not stop the task, so routes must be rebuilt and redundancy kept. Scalability: routing must work with hundreds or thousands of nodes. Data aggregation: combining redundant data from several nodes reduces transmissions. (Others: heterogeneity, network dynamics, transmission medium, connectivity, coverage, quality of service.)

3. Compare the time-driven, event-driven and query-driven reporting models. In the time-driven model nodes sense and report periodically, suiting continuous monitoring but producing steady, heavy traffic. In the event-driven model nodes report only when the sensed value changes sharply, suiting time-critical detection with rare, bursty traffic. In the query-driven model nodes report when the base station asks. In the program, one field made 142,272 transmissions a day time-driven, 3,286 query-driven and 121 event-driven.

4. Why does multi-hop routing to a single base station shorten network lifetime, and how can aggregation help? Every packet must pass through the few nodes near the base station, which therefore relay far more than the rest and run out of energy first, disconnecting the nodes behind them. In the program the busiest node transmitted 24,480 packets a day, 17.2 times the average. If each node combines its subtree's readings into one packet per period, every node transmits the same amount, 288 a day in the program, and the total falls from 142,272 to 28,800.

5. What is meant by energy consumption without losing accuracy? Nodes must conserve energy in computation and communication, but not by degrading the data the application needs. Because each node both senses and routes, a node that exhausts its battery removes its own data and breaks routes through it, so energy-efficient routing must spread the load and keep the network's view of the environment accurate for as long as possible.

6. How does quality of service conflict with energy in WSN routing? Some applications need data within a bounded time, which favours short, fast, always-ready routes. But in many applications lifetime matters more than the quality of each report, so as energy runs low the network may reduce the quality of its results, sending less often or aggregating more, to last longer. Energy-aware routing must strike the balance the application requires.