Channel Scheduling

We begin our description of channel scheduling by describing the data structure used to represent the channel schedule. We then describe the policy nodes use to act on their own channel schedule, the mechanism to communicate channel schedules to other nodes, and finally the policy nodes implement for updating or changing their own channel schedule.

The channel schedule must capture a given node's plans for channel hopping in the future, and there is obvious overhead to representing this as a very long list. Instead, we compactly represent the channel schedule as a current channel and a rule for updating the channel - in particular, as a set of 4 (channel, seed) pairs. Our experimental results show that 4 pairs suffice to give good performance (Section 4). We represent the (channel, seed) pair as $(x_i, a_i)$. The channel $x_i$ is represented as an integer in the range [0, 12] (13 possibilities), and the seed $a_i$ is represented as an integer in the range [1, 12]. Each node iterates through all of the channels in the current schedule, switching to the channel designated in the schedule in each new slot. The node then increments each of the channels in its schedule using the seed,

$$x_i \leftarrow (x_i + a_i) \bmod 13$$

and repeats the process.

We introduce one additional slot to prevent logical partitions. After the node has iterated through every channel on each of its 4 slots, it switches to a parity slot whose channel assignment is given by $x_{parity} = a_1$. The term parity slot is derived from the analogy to the parity bits appended at the end of a string in some error correcting codes. The mathematical justification for this design is given in Section 3.4. We use the term cycle to refer to the 530 ms iteration through all the slots, including the parity slot.

In Figure 2, we illustrate possible channel schedules for two nodes in the case of 2 slots and 3 channels. In the Figure, node A and node B are synchronized in one of their two slots (they have identical (channel, seed) pairs), and they also overlap during the parity slot. The field of the channel schedule that determines the channel during each slot is shown in bold. Each time a slot reappears, the channel is updated using the seed. For example, node A's slot 1 initially has (channel, seed) = (1,2). The next time slot 1 is entered, the channel is updated by adding the seed to it mod 3 (mod 3 because in this example, there are 3 channels). The resulting channel is given by $(1 + 2) \bmod 3 = 0$.

Figure 2: Channel hopping schedules for two nodes with 3 channels and 2 slots. Node A always overlaps with Node B in slot 1 and the parity slot. The field of the channel schedule that determines the channel during each slot is shown in bold.

Nodes switch from one slot to the next according to a fixed schedule (every 10 ms in our current parameter settings). However, the decision to switch channels may occur while a node is transmitting or receiving a packet. In this case we delay the switch until after the transmission and ACK (or lack thereof) have occurred.

Nodes learn each other's schedules by periodically broadcasting their seeds and the offset within this cycle through the channel schedule. We use the IEEE 802.11 Long Control Frame Header format to embed both the schedule and the node's current offset - this is discussed in more detail in Section 3.5. The SSCH layer at each node schedules one of these packets for broadcast once per slot.

Nodes also update their knowledge of other nodes' schedules by trying to communicate and failing. Whenever a node sends an RTS to another node, and that node fails to respond even though it was believed to be in this slot, the node sending the RTS updates the channel schedule for the other node to reflect that it does not currently know the node's schedule in this slot.

We now turn to the question of how a given node changes its own schedule. Schedules are updated in two ways: each node attempts to maintain that its slots start and stop at roughly the same time as other nodes, and that its channel schedule overlaps with nodes for which it has packets to send. We embed the information needed for this synchronization within the Long Control Frame Header as well. Using this information, a simple averaging scheme such as described by Elson et al [15] can be applied to achieve the loose synchronization required for good performance (Section 4 shows that a 100 $\mu$s skew in clock times leads to less than a 2% decrease in capacity).

At a high level, each node achieves overlap with nodes for which it has traffic straightforwardly, by changing part of its own schedule to match that of the other nodes. However, a number of minor decisions must be made correctly in order to achieve this high level goal.

Figure 3: The problem with a naive synchronization scheme. Node A has two slots, with (channel, seed) pairs represented by $A_1$ and $A_2$; nodes B and C are similarly depicted. At time $t_1$, node A synchronizes with node B. Node B synchronizes with node C at time $t_2$, after which A and B are no longer synchronized.

Nodes recompute their channel schedule right before they enqueue the packet announcing this schedule in the NIC (and so at least once per slot). In a naive approach, this node could examine its packet queue, and select the (channel, seed) pairs which lead to the best opportunity to send the largest number of packets. However, this ignores the interest this node has in receiving packets, and in avoiding congested channels. An example of the kind of problem that might arise if one ignores the interest in receiving packets is given in Figure 3. Here, A synchronized with B, and then B synchronized with C in such a way that A was no longer synchronized with B. This could have been avoided if B had used its other slot to synchronize with C, as it would have if it considered its interest in receiving packets.

To account for this node's interest in receiving packets, we maintain per-slot counters for the number of packets received during the previous time the slot was active (ignoring broadcast packets). Any slot that received more than 10 packets during the previous iteration through that slot is labeled a receiving slot; if all slots are receiving slots, any one is allowed to be changed. If some slots are receiving slots and some are not, only the (channel, seed) pair on a non-receiving slot is allowed to be changed for the purpose of synchronizing with nodes we want to send to.

To account for channel congestion, we compare the (channel, seed) pairs of all the nodes that sent us packets in a given slot with the (channel, seed) pairs of all the other nodes in our list of channel schedules. If the number of other nodes synchronized to the same (channel, seed) pair is more than twice as many as this node communicated with in the previous occurrence of the slot, we attempt to de-synchronize from these other nodes. De-synchronization just involves choosing a new (channel, seed) pair for this slot. In our experiments, this de-synchronization mechanism was both necessary and sufficient to prevent the nodes from all converging to the same set of (channel, seed) pairs.

The final constraints we add moderate the pace of change in schedule information. Each node only considers updating the (channel, seed) pair for the next slot, never for slots further in the future. If the previous set of criteria suggest updating some slot other than the next slot, we delay that decision. Given these constraints, picking the best possible (channel, seed) pair simply requires considering the choice that synchronizes with the set of nodes for which we have the largest number of queued packets. Additionally, the (channel, seed) pair for the first slot is only allowed to be updated during the parity slot - this helps to prevent logical partition, as will be explained in more detail in Section 3.4.

This strategy naturally supports nodes acting as sources, sinks, or forwarders. A source node will find that it can assign all of its slots to support sends. A sink node will find that it rarely changes its slot assignment, and hence nodes sending to it can easily stay synchronized. A forwarding node will find that some of its slots are used primarily for receiving; after re-assigning the channel and seed in a slot to support sending, the slots that did not change are more likely to receive packets, and hence to stabilize on their current channel and seed as receiving slots for the duration of the current traffic patterns. Our simulation results (Section 4) support this conclusion. We refer to the technique of enabling this synchronization pattern as partial synchronization.