Stable Transmission Trees on Moving Sinks of Wireless Sensor Networks

This talk was given by Yoshihiro Kaneko at SEICCGTC 2017. He’s been working on this with a bunch of students, whose names I didn’t get a chance to write down. We had a long conversation afterwards because I wanted to clarify some things that came up in the talk, but we also ended up talking about some differences between applied math and engineering ;)

——

I think the name **wireless sensor network** is pretty self-explanatory: we have a bunch of sensors that are all collecting data, and we want to bring it all together to one place. So we allow them to communicate with each other by sending all of the data packets to a single CPU. The CPU will generally be pretty far away from most of the sensors, so it can’t connect with them directly. But it is pretty computationally expensive to set up communication channels, so we want to do it somewhat efficiently.

However, there is a fairly serious practical issue with this model, which is that the sensors closest to the CPU are then responsible for handling every data packet sent by every single sensor. If the network is large, this can lead to a backlog, or an excess of energy usage. (The latter might be a *really* big problem if you’re running on a charge!)

Fortunately, people have proposed many fixes for this problem, which have their own strengths and weaknesses. The one that Kaneko chooses is called the **moving sink model**, in which the responsibility for doing the computations moves between multiple CPUs. Note that this is not parallel processing: at any given time, only one of the CPUs is considered “active” (or the **sink**) and receives all the packets.

One big problem with the moving sink model is that every time the sink moves, we need to figure out how we’re re-routing the data from each sensor to get there. Remember that it’s expensive to set up communication channels, so we don’t want to have to keep re-establishing them: we’d like our network to change as little as possible.

Moving into the world of abstract graph theory, the problem looks like this: the network is a graph with a collection of distinguished vertices (corresponding to CPUs). We “move the sink” by creating a (finite) sequence $(v_1, v_2,\dots, v_k)$ of distinguished vertices (repeats are allowed), and for each $v_i$ we want to create a spanning tree $T_i$.

In this language, the goal is to construct the $T_i$ in such a way that “no two adjacent $T_i$ are too different from one another”. In other words, for some fixed distance function $d$ on the set of spanning trees and minimize the total distance between consecutive $T_i$:

$$ D = d(T_1, T_2) + d(T_2, T_3) + d(T_3, T_4) + \cdots + d(T_{k-1}, T_k). $$

Hmmm… distance function…… on the space of trees…… hmmm………….

But sadly to all the geometry fans out there, we went with something a little more mundane: to get the distance between two spanning trees you count the number of edges that are in one tree and not the other.

He spent the last bit of the talk describing the algorithm they created for creating the $T_i$ in a particular setting (the network is a grid graph, the $v_i$ are the boundary vertices ordered counterclockwise). His students claim to have a proof that their algorithm generates spanning trees which minimizes $D$, but apparently the proof involves a lot of casework and he wasn’t quite willing to confirm it yet.

——

I actually asked him when we were talking if they had considered the BHV metric (which is the professional way of saying “You should consider this” to someone). They had not, but he said that it wouldn’t be likely to be useful: we want $D$ to represent the cost it takes to set up a communication channel. Since we expect this to be a fixed-cost operation, the edge-counting distance makes sense for this particular application. Conversely, the operation of “shrinking the tree to zero”, which is fairly common in BHV-geodesics, is pretty meaningless.

[ In the same vein: his distance was slightly different than the usual standard, because the standard method makes the trees directed and counts reversing an edge as distance 1, but he counted it as distance 0. This is because for wireless communication networks, it would be rather unusual for the communication channels to be set up one-directionally. For security and error-correcting reasons, it’s better for the receiver to acknowledge the sender and to explicitly permit an opening channel. So while this exchange is happening, you might as well set it up bidirectionally. ]