Contiki-NG
Loading...
Searching...
No Matches
tsch-cs.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016-2018, University of Bristol - http://www.bristol.ac.uk
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Neither the name of the copyright holder nor the names of its
13 * contributors may be used to endorse or promote products derived
14 * from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 */
29
30/**
31 * \file
32 * Source file for TSCH adaptive channel selection
33 * \author
34 * Atis Elsts <atis.elsts@bristol.ac.uk>
35 */
36
37#include "tsch.h"
38#include "tsch-stats.h"
39#include "tsch-cs.h"
40
41#if ! TSCH_STATS_ON
42#error tsch-cs requires tsch-stats. Please enable TSCH_STATS_CONF_ON.
43#endif /* ! TSCH_STATS_ON */
44
45#if ! TSCH_STATS_SAMPLE_NOISE_RSSI
46#error tsch-cs requires periodic RSSI sampling. Please enable TSCH_STATS_CONF_SAMPLE_NOISE_RSSI.
47#endif /* ! TSCH_STATS_SAMPLE_NOISE_RSSI */
48
49/* Log configuration */
50#include "sys/log.h"
51#define LOG_MODULE "TSCH CS"
52#define LOG_LEVEL LOG_LEVEL_MAC
53
54/*---------------------------------------------------------------------------*/
55
56/* Allow to change only 1 channel at once */
57#define TSCH_CS_MAX_CHANNELS_CHANGED 1
58
59/* Do not up change channels more frequently than this */
60#define TSCH_CS_MIN_UPDATE_INTERVAL_SEC 60
61
62/* Do not change channels if the difference in qualities is below this */
63#define TSCH_CS_HYSTERESIS (TSCH_STATS_BINARY_SCALING_FACTOR / 10)
64
65/* After removing a channel from the sequence, do not add it back at least this time */
66#define TSCH_CS_BLACKLIST_DURATION_SEC (5 * 60)
67
68/* A potential for change detected? */
69static bool recaculation_requested;
70
71/* Time (in seconds) when channels were marked as busy; 0 if they are not busy */
72static uint32_t tsch_cs_busy_since[TSCH_STATS_NUM_CHANNELS];
73
74/*
75 * The following variables are kept in order to avoid completely migrating away
76 * from the initial hopping sequence (as then new nodes would not be able to join).
77 * The invariant is: tsch_cs_initial_bitmap & tsch_cs_current_bitmap != 0
78 */
79/* The bitmap with the initial channels */
80static tsch_cs_bitmap_t tsch_cs_initial_bitmap;
81/* The bitmap with the current channels */
82static tsch_cs_bitmap_t tsch_cs_current_bitmap;
83
84/* structure for sorting */
85struct tsch_cs_quality {
86 /* channel number */
87 uint8_t channel;
88 /* the higher, the better */
89 tsch_stat_t metric;
90};
91/*---------------------------------------------------------------------------*/
92static inline bool
93tsch_cs_bitmap_contains(tsch_cs_bitmap_t bitmap, uint8_t channel)
94{
95 return (1 << (channel - TSCH_STATS_FIRST_CHANNEL)) & bitmap;
96}
97/*---------------------------------------------------------------------------*/
98static inline tsch_cs_bitmap_t
99tsch_cs_bitmap_set(tsch_cs_bitmap_t bitmap, uint8_t channel)
100{
101 return (1 << (channel - TSCH_STATS_FIRST_CHANNEL)) | bitmap;
102}
103/*---------------------------------------------------------------------------*/
104static tsch_cs_bitmap_t
105tsch_cs_bitmap_calc(void)
106{
107 tsch_cs_bitmap_t result = 0;
108 int i;
109 for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
110 result = tsch_cs_bitmap_set(result, tsch_hopping_sequence[i]);
111 }
112 return result;
113}
114/*---------------------------------------------------------------------------*/
115void
117{
118 tsch_cs_initial_bitmap = tsch_cs_bitmap_calc();
119 tsch_cs_current_bitmap = tsch_cs_initial_bitmap;
120}
121/*---------------------------------------------------------------------------*/
122/* Sort the elements to that the channels with the best metrics are in the front */
123static void
124tsch_cs_bubble_sort(struct tsch_cs_quality *qualities)
125{
126 int i, j;
127 struct tsch_cs_quality tmp;
128
129 for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
130 for(j = 0; j + 1 < TSCH_STATS_NUM_CHANNELS; ++j) {
131 if(qualities[j].metric < qualities[j+1].metric){
132 tmp = qualities[j];
133 qualities[j] = qualities[j+1];
134 qualities[j+1] = tmp;
135 }
136 }
137 }
138}
139/*---------------------------------------------------------------------------*/
140/* Select a single, currently unused, good enough channel. Returns 0xff on failure. */
141static uint8_t
142tsch_cs_select_replacement(uint8_t old_channel, tsch_stat_t old_ewma,
143 struct tsch_cs_quality *qualities, uint8_t is_in_sequence[])
144{
145 int i;
146 uint32_t now = clock_seconds();
147 tsch_cs_bitmap_t bitmap = tsch_cs_bitmap_set(0, old_channel);
148
149 /* Don't want to replace a channel if the improvement is miniscule (< 10%) */
150 old_ewma += TSCH_CS_HYSTERESIS;
151
152 /* iterate up to -1 because we know that at least one of the channels is bad */
153 for(i = 0; i < TSCH_STATS_NUM_CHANNELS - 1; ++i) {
154 /* select a replacement candidate */
155 uint8_t candidate = qualities[i].channel;
156
157 if(qualities[i].metric < TSCH_CS_FREE_THRESHOLD) {
158 /* This channel is not good enough.
159 * since we know that the other channels in the sorted list are even worse,
160 * it makes sense to return immediately rather than to continue t
161 */
162 LOG_DBG("ch %u: busy\n", candidate);
163 return 0xff;
164 }
165
166 if(qualities[i].metric < old_ewma) {
167 /* not good enough to replace */
168 LOG_DBG("ch %u: hysteresis check failed\n", candidate);
169 return 0xff;
170 }
171
172 /* already in the current TSCH hopping sequence? */
173 if(is_in_sequence[candidate - TSCH_STATS_FIRST_CHANNEL] != 0xff) {
174 LOG_DBG("ch %u: in seq\n", candidate);
175 continue;
176 }
177
178 /* ignore this candidate if too recently blacklisted */
179 if(tsch_cs_busy_since[candidate - TSCH_STATS_FIRST_CHANNEL] != 0
180 && tsch_cs_busy_since[candidate - TSCH_STATS_FIRST_CHANNEL] + TSCH_CS_BLACKLIST_DURATION_SEC > now) {
181 LOG_DBG("ch %u: recent bl\n", candidate);
182 continue;
183 }
184
185 /* check if removing the old channel would break our hopping sequence invariant */
186 if(bitmap == (tsch_cs_initial_bitmap & tsch_cs_current_bitmap)) {
187 /* the channel is the only one that belongs to both */
188 if(!tsch_cs_bitmap_contains(tsch_cs_initial_bitmap, candidate)) {
189 /* the candidate is not in the initial sequence; not acceptable */
190 continue;
191 }
192 }
193
194 return candidate;
195 }
196
197 return 0xff;
198}
199/*---------------------------------------------------------------------------*/
200bool
202{
203 int i;
204 bool try_replace;
205 bool has_replaced;
206 struct tsch_cs_quality qualities[TSCH_STATS_NUM_CHANNELS];
207 uint8_t is_channel_busy[TSCH_STATS_NUM_CHANNELS];
208 uint8_t is_in_sequence[TSCH_STATS_NUM_CHANNELS];
209 static uint32_t last_time_changed;
210
211 if(!recaculation_requested) {
212 /* nothing to do */
213 return false;
214 }
215
216 if(last_time_changed != 0 && last_time_changed + TSCH_CS_MIN_UPDATE_INTERVAL_SEC > clock_seconds()) {
217 /* too soon */
218 return false;
219 }
220
221 /* reset the flag */
222 recaculation_requested = false;
223
224 for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
225 qualities[i].channel = i + TSCH_STATS_FIRST_CHANNEL;
226 qualities[i].metric = tsch_stats.channel_free_ewma[i];
227 }
228
229 /* bubble sort the channels */
230 tsch_cs_bubble_sort(qualities);
231
232 /* start with the threshold values */
233 for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
234 is_channel_busy[i] = (tsch_stats.channel_free_ewma[i] < TSCH_CS_FREE_THRESHOLD);
235 }
236 memset(is_in_sequence, 0xff, sizeof(is_in_sequence));
237 for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
238 uint8_t channel = tsch_hopping_sequence[i];
239 is_in_sequence[channel - TSCH_STATS_FIRST_CHANNEL] = i;
240 }
241
242 /* mark the first N channels as "good" - there is nothing better to select */
243 for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
244 is_channel_busy[qualities[i].channel - TSCH_STATS_FIRST_CHANNEL] = 0;
245 }
246
247 for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
248 uint8_t ci = qualities[i].channel - TSCH_STATS_FIRST_CHANNEL;
249 (void)ci;
250 LOG_DBG("ch %u q %u busy %u in seq %u\n",
251 qualities[i].channel,
252 qualities[i].metric,
253 is_channel_busy[ci],
254 is_in_sequence[ci] == 0xff ? 0 : 1);
255 }
256
257 try_replace = false;
258 for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
259 uint8_t channel = tsch_hopping_sequence[i];
260 if(is_channel_busy[channel - TSCH_STATS_FIRST_CHANNEL]) {
261 try_replace = true;
262 }
263 }
264 if(!try_replace) {
265 LOG_DBG("cs: not replacing\n");
266 return false;
267 }
268
269 has_replaced = false;
270 for(i = TSCH_STATS_NUM_CHANNELS - 1; i >= tsch_hopping_sequence_length.val; --i) {
271 if(is_in_sequence[qualities[i].channel - TSCH_STATS_FIRST_CHANNEL] != 0xff) {
272 /* found the worst channel; it must be busy */
273 uint8_t channel = qualities[i].channel;
274 tsch_stat_t ewma_metric = qualities[i].metric;
275 uint8_t replacement = tsch_cs_select_replacement(channel, ewma_metric,
276 qualities, is_in_sequence);
277 uint8_t position = is_in_sequence[channel - TSCH_STATS_FIRST_CHANNEL];
278
279 if(replacement != 0xff) {
280 printf("\ncs: replacing channel %u %u (%u) with %u\n",
281 channel, tsch_hopping_sequence[position], position, replacement);
282 /* mark the old channel as busy */
283 tsch_cs_busy_since[channel - TSCH_STATS_FIRST_CHANNEL] = clock_seconds();
284 /* do the actual replacement in the global TSCH HS variable */
285 tsch_hopping_sequence[position] = replacement;
286 has_replaced = true;
287 /* recalculate the hopping sequence bitmap */
288 tsch_cs_current_bitmap = tsch_cs_bitmap_calc();
289 }
290 break; /* replace just one at once */
291 }
292 }
293
294 if(has_replaced) {
295 last_time_changed = clock_seconds();
296 return true;
297 }
298
299 LOG_DBG("cs: no changes\n");
300 return false;
301}
302/*---------------------------------------------------------------------------*/
303void
304tsch_cs_channel_stats_updated(uint8_t updated_channel, uint16_t old_busyness_metric)
305{
306 uint8_t index;
307 bool old_is_busy;
308 bool new_is_busy;
309
310 /* Enable this only on the coordinator node */
311 if(!tsch_is_coordinator) {
312 return;
313 }
314
315 /* Do not try to adapt before enough information has been learned */
316 if(clock_seconds() < TSCH_CS_LEARNING_PERIOD_SEC) {
317 return;
318 }
319
320 index = tsch_stats_channel_to_index(updated_channel);
321
322 old_is_busy = (old_busyness_metric < TSCH_CS_FREE_THRESHOLD);
323 new_is_busy = (tsch_stats.channel_free_ewma[index] < TSCH_CS_FREE_THRESHOLD);
324
325 if(old_is_busy != new_is_busy) {
326 /* the status of the channel has changed*/
327 recaculation_requested = true;
328
329 } else if(new_is_busy) {
330 /* run the reselection algorithm iff the channel is both (1) bad and (2) in use */
331 if(tsch_cs_bitmap_contains(tsch_cs_current_bitmap, updated_channel)) {
332 /* the channel is in use and is busy */
333 recaculation_requested = true;
334 }
335 }
336}
unsigned long clock_seconds(void)
Get the current value of the platform seconds.
Definition clock.c:130
Header file for the logging system.
void tsch_cs_adaptations_init(void)
Initializes the TSCH hopping sequence selection module.
Definition tsch-cs.c:116
bool tsch_cs_process(void)
Potentially update the TSCH hopping sequence.
Definition tsch-cs.c:201
void tsch_cs_channel_stats_updated(uint8_t updated_channel, uint16_t old_busyness_metric)
Signal the need to potentially update the TSCH hopping sequence.
Definition tsch-cs.c:304
Header file for TSCH adaptive channel selection.
Header file for TSCH statistics.
Main API declarations for TSCH.