Contiki-NG
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 /* Log configuration */
42 #include "sys/log.h"
43 #define LOG_MODULE "TSCH CS"
44 #define LOG_LEVEL LOG_LEVEL_MAC
45 
46 /*---------------------------------------------------------------------------*/
47 
48 /* Allow to change only 1 channel at once */
49 #define TSCH_CS_MAX_CHANNELS_CHANGED 1
50 
51 /* Do not up change channels more frequently than this */
52 #define TSCH_CS_MIN_UPDATE_INTERVAL_SEC 60
53 
54 /* Do not change channels if the difference in qualities is below this */
55 #define TSCH_CS_HYSTERESIS (TSCH_STATS_BINARY_SCALING_FACTOR / 10)
56 
57 /* After removing a channel from the sequence, do not add it back at least this time */
58 #define TSCH_CS_BLACKLIST_DURATION_SEC (5 * 60)
59 
60 /* A potential for change detected? */
61 static bool recaculation_requested;
62 
63 /* Time (in seconds) when channels were marked as busy; 0 if they are not busy */
64 static uint32_t tsch_cs_busy_since[TSCH_STATS_NUM_CHANNELS];
65 
66 /*
67  * The following variables are kept in order to avoid completely migrating away
68  * from the initial hopping sequence (as then new nodes would not be able to join).
69  * The invariant is: tsch_cs_initial_bitmap & tsch_cs_current_bitmap != 0
70  */
71 /* The bitmap with the initial channels */
72 static tsch_cs_bitmap_t tsch_cs_initial_bitmap;
73 /* The bitmap with the current channels */
74 static tsch_cs_bitmap_t tsch_cs_current_bitmap;
75 
76 /* structure for sorting */
77 struct tsch_cs_quality {
78  /* channel number */
79  uint8_t channel;
80  /* the higher, the better */
81  tsch_stat_t metric;
82 };
83 /*---------------------------------------------------------------------------*/
84 static inline bool
85 tsch_cs_bitmap_contains(tsch_cs_bitmap_t bitmap, uint8_t channel)
86 {
87  return (1 << (channel - TSCH_STATS_FIRST_CHANNEL)) & bitmap;
88 }
89 /*---------------------------------------------------------------------------*/
90 static inline tsch_cs_bitmap_t
91 tsch_cs_bitmap_set(tsch_cs_bitmap_t bitmap, uint8_t channel)
92 {
93  return (1 << (channel - TSCH_STATS_FIRST_CHANNEL)) | bitmap;
94 }
95 /*---------------------------------------------------------------------------*/
96 static tsch_cs_bitmap_t
97 tsch_cs_bitmap_calc(void)
98 {
99  tsch_cs_bitmap_t result = 0;
100  int i;
101  for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
102  result = tsch_cs_bitmap_set(result, tsch_hopping_sequence[i]);
103  }
104  return result;
105 }
106 /*---------------------------------------------------------------------------*/
107 void
109 {
110  tsch_cs_initial_bitmap = tsch_cs_bitmap_calc();
111  tsch_cs_current_bitmap = tsch_cs_initial_bitmap;
112 }
113 /*---------------------------------------------------------------------------*/
114 /* Sort the elements to that the channels with the best metrics are in the front */
115 static void
116 tsch_cs_bubble_sort(struct tsch_cs_quality *qualities)
117 {
118  int i, j;
119  struct tsch_cs_quality tmp;
120 
121  for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
122  for(j = 0; j + 1 < TSCH_STATS_NUM_CHANNELS; ++j) {
123  if(qualities[j].metric < qualities[j+1].metric){
124  tmp = qualities[j];
125  qualities[j] = qualities[j+1];
126  qualities[j+1] = tmp;
127  }
128  }
129  }
130 }
131 /*---------------------------------------------------------------------------*/
132 /* Select a single, currently unused, good enough channel. Returns 0xff on failure. */
133 static uint8_t
134 tsch_cs_select_replacement(uint8_t old_channel, tsch_stat_t old_ewma,
135  struct tsch_cs_quality *qualities, uint8_t is_in_sequence[])
136 {
137  int i;
138  uint32_t now = clock_seconds();
139  tsch_cs_bitmap_t bitmap = tsch_cs_bitmap_set(0, old_channel);
140 
141  /* Don't want to replace a channel if the improvement is miniscule (< 10%) */
142  old_ewma += TSCH_CS_HYSTERESIS;
143 
144  /* iterate up to -1 because we know that at least one of the channels is bad */
145  for(i = 0; i < TSCH_STATS_NUM_CHANNELS - 1; ++i) {
146  /* select a replacement candidate */
147  uint8_t candidate = qualities[i].channel;
148 
149  if(qualities[i].metric < TSCH_CS_FREE_THRESHOLD) {
150  /* This channel is not good enough.
151  * since we know that the other channels in the sorted list are even worse,
152  * it makes sense to return immediately rather than to continue t
153  */
154  LOG_DBG("ch %u: busy\n", candidate);
155  return 0xff;
156  }
157 
158  if(qualities[i].metric < old_ewma) {
159  /* not good enough to replace */
160  LOG_DBG("ch %u: hysteresis check failed\n", candidate);
161  return 0xff;
162  }
163 
164  /* already in the current TSCH hopping sequence? */
165  if(is_in_sequence[candidate - TSCH_STATS_FIRST_CHANNEL] != 0xff) {
166  LOG_DBG("ch %u: in seq\n", candidate);
167  continue;
168  }
169 
170  /* ignore this candidate if too recently blacklisted */
171  if(tsch_cs_busy_since[candidate - TSCH_STATS_FIRST_CHANNEL] != 0
172  && tsch_cs_busy_since[candidate - TSCH_STATS_FIRST_CHANNEL] + TSCH_CS_BLACKLIST_DURATION_SEC > now) {
173  LOG_DBG("ch %u: recent bl\n", candidate);
174  continue;
175  }
176 
177  /* check if removing the old channel would break our hopping sequence invariant */
178  if(bitmap == (tsch_cs_initial_bitmap & tsch_cs_current_bitmap)) {
179  /* the channel is the only one that belongs to both */
180  if(!tsch_cs_bitmap_contains(tsch_cs_initial_bitmap, candidate)) {
181  /* the candidate is not in the initial sequence; not acceptable */
182  continue;
183  }
184  }
185 
186  return candidate;
187  }
188 
189  return 0xff;
190 }
191 /*---------------------------------------------------------------------------*/
192 bool
194 {
195  int i;
196  bool try_replace;
197  bool has_replaced;
198  struct tsch_cs_quality qualities[TSCH_STATS_NUM_CHANNELS];
199  uint8_t is_channel_busy[TSCH_STATS_NUM_CHANNELS];
200  uint8_t is_in_sequence[TSCH_STATS_NUM_CHANNELS];
201  static uint32_t last_time_changed;
202 
203  if(!recaculation_requested) {
204  /* nothing to do */
205  return false;
206  }
207 
208  if(last_time_changed != 0 && last_time_changed + TSCH_CS_MIN_UPDATE_INTERVAL_SEC > clock_seconds()) {
209  /* too soon */
210  return false;
211  }
212 
213  /* reset the flag */
214  recaculation_requested = false;
215 
216  for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
217  qualities[i].channel = i + TSCH_STATS_FIRST_CHANNEL;
218  qualities[i].metric = tsch_stats.channel_free_ewma[i];
219  }
220 
221  /* bubble sort the channels */
222  tsch_cs_bubble_sort(qualities);
223 
224  /* start with the threshold values */
225  for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
226  is_channel_busy[i] = (tsch_stats.channel_free_ewma[i] < TSCH_CS_FREE_THRESHOLD);
227  }
228  memset(is_in_sequence, 0xff, sizeof(is_in_sequence));
229  for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
230  uint8_t channel = tsch_hopping_sequence[i];
231  is_in_sequence[channel - TSCH_STATS_FIRST_CHANNEL] = i;
232  }
233 
234  /* mark the first N channels as "good" - there is nothing better to select */
235  for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
236  is_channel_busy[qualities[i].channel - TSCH_STATS_FIRST_CHANNEL] = 0;
237  }
238 
239  for(i = 0; i < TSCH_STATS_NUM_CHANNELS; ++i) {
240  uint8_t ci = qualities[i].channel - TSCH_STATS_FIRST_CHANNEL;
241  (void)ci;
242  LOG_DBG("ch %u q %u busy %u in seq %u\n",
243  qualities[i].channel,
244  qualities[i].metric,
245  is_channel_busy[ci],
246  is_in_sequence[ci] == 0xff ? 0 : 1);
247  }
248 
249  try_replace = false;
250  for(i = 0; i < tsch_hopping_sequence_length.val; ++i) {
251  uint8_t channel = tsch_hopping_sequence[i];
252  if(is_channel_busy[channel - TSCH_STATS_FIRST_CHANNEL]) {
253  try_replace = true;
254  }
255  }
256  if(!try_replace) {
257  LOG_DBG("cs: not replacing\n");
258  return false;
259  }
260 
261  has_replaced = false;
262  for(i = TSCH_STATS_NUM_CHANNELS - 1; i >= tsch_hopping_sequence_length.val; --i) {
263  if(is_in_sequence[qualities[i].channel - TSCH_STATS_FIRST_CHANNEL] != 0xff) {
264  /* found the worst channel; it must be busy */
265  uint8_t channel = qualities[i].channel;
266  tsch_stat_t ewma_metric = qualities[i].metric;
267  uint8_t replacement = tsch_cs_select_replacement(channel, ewma_metric,
268  qualities, is_in_sequence);
269  uint8_t position = is_in_sequence[channel - TSCH_STATS_FIRST_CHANNEL];
270 
271  if(replacement != 0xff) {
272  printf("\ncs: replacing channel %u %u (%u) with %u\n",
273  channel, tsch_hopping_sequence[position], position, replacement);
274  /* mark the old channel as busy */
275  tsch_cs_busy_since[channel - TSCH_STATS_FIRST_CHANNEL] = clock_seconds();
276  /* do the actual replacement in the global TSCH HS variable */
277  tsch_hopping_sequence[position] = replacement;
278  has_replaced = true;
279  /* recalculate the hopping sequence bitmap */
280  tsch_cs_current_bitmap = tsch_cs_bitmap_calc();
281  }
282  break; /* replace just one at once */
283  }
284  }
285 
286  if(has_replaced) {
287  last_time_changed = clock_seconds();
288  return true;
289  }
290 
291  LOG_DBG("cs: no changes\n");
292  return false;
293 }
294 /*---------------------------------------------------------------------------*/
295 void
296 tsch_cs_channel_stats_updated(uint8_t updated_channel, uint16_t old_busyness_metric)
297 {
298  uint8_t index;
299  bool old_is_busy;
300  bool new_is_busy;
301 
302  /* Enable this only on the coordinator node */
303  if(!tsch_is_coordinator) {
304  return;
305  }
306 
307  /* Do not try to adapt before enough information has been learned */
308  if(clock_seconds() < TSCH_CS_LEARNING_PERIOD_SEC) {
309  return;
310  }
311 
312  index = tsch_stats_channel_to_index(updated_channel);
313 
314  old_is_busy = (old_busyness_metric < TSCH_CS_FREE_THRESHOLD);
315  new_is_busy = (tsch_stats.channel_free_ewma[index] < TSCH_CS_FREE_THRESHOLD);
316 
317  if(old_is_busy != new_is_busy) {
318  /* the status of the channel has changed*/
319  recaculation_requested = true;
320 
321  } else if(new_is_busy) {
322  /* run the reselection algorithm iff the channel is both (1) bad and (2) in use */
323  if(tsch_cs_bitmap_contains(tsch_cs_current_bitmap, updated_channel)) {
324  /* the channel is in use and is busy */
325  recaculation_requested = true;
326  }
327  }
328 }
unsigned long clock_seconds(void)
Get the current value of the platform seconds.
Definition: clock.c:130
void tsch_cs_adaptations_init(void)
Initializes the TSCH hopping sequence selection module.
Definition: tsch-cs.c:108
bool tsch_cs_process(void)
Potentially update the TSCH hopping sequence.
Definition: tsch-cs.c:193
Main API declarations for TSCH.
Header file for TSCH statistics
Header file for TSCH adaptive channel selection
Header file for the logging system
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:296