Contiki-NG
link-stats.c
1 /*
2  * Copyright (c) 2015, SICS Swedish ICT.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the Institute nor the names of its contributors
14  * may be used to endorse or promote products derived from this software
15  * without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  *
30  * Authors: Simon Duquennoy <simonduq@sics.se>
31  */
32 
33 #include "contiki.h"
34 #include "sys/clock.h"
35 #include "net/packetbuf.h"
36 #include "net/nbr-table.h"
37 #include "net/link-stats.h"
38 #include <stdio.h>
39 
40 /* Log configuration */
41 #include "sys/log.h"
42 #define LOG_MODULE "Link Stats"
43 #define LOG_LEVEL LOG_LEVEL_MAC
44 
45 /* Maximum value for the Tx count counter */
46 #define TX_COUNT_MAX 32
47 
48 /* Statistics with no update in FRESHNESS_EXPIRATION_TIMEOUT is not fresh */
49 #define FRESHNESS_EXPIRATION_TIME (10 * 60 * (clock_time_t)CLOCK_SECOND)
50 /* Half time for the freshness counter */
51 #define FRESHNESS_HALF_LIFE (15 * 60 * (clock_time_t)CLOCK_SECOND)
52 /* Statistics are fresh if the freshness counter is FRESHNESS_TARGET or more */
53 #define FRESHNESS_TARGET 4
54 /* Maximum value for the freshness counter */
55 #define FRESHNESS_MAX 16
56 
57 /* EWMA (exponential moving average) used to maintain statistics over time */
58 #define EWMA_SCALE 100
59 #define EWMA_ALPHA 10
60 #define EWMA_BOOTSTRAP_ALPHA 25
61 
62 /* ETX fixed point divisor. 128 is the value used by RPL (RFC 6551 and RFC 6719) */
63 #define ETX_DIVISOR LINK_STATS_ETX_DIVISOR
64 /* In case of no-ACK, add ETX_NOACK_PENALTY to the real Tx count, as a penalty */
65 #define ETX_NOACK_PENALTY 12
66 /* Initial ETX value */
67 #define ETX_DEFAULT 2
68 
69 /* Per-neighbor link statistics table */
70 NBR_TABLE(struct link_stats, link_stats);
71 
72 /* Called at a period of FRESHNESS_HALF_LIFE */
73 struct ctimer periodic_timer;
74 
75 /*---------------------------------------------------------------------------*/
76 /* Returns the neighbor's link stats */
77 const struct link_stats *
78 link_stats_from_lladdr(const linkaddr_t *lladdr)
79 {
80  return nbr_table_get_from_lladdr(link_stats, lladdr);
81 }
82 /*---------------------------------------------------------------------------*/
83 /* Returns the neighbor's address given a link stats item */
84 const linkaddr_t *
85 link_stats_get_lladdr(const struct link_stats *stat)
86 {
87  return nbr_table_get_lladdr(link_stats, stat);
88 }
89 /*---------------------------------------------------------------------------*/
90 /* Are the statistics fresh? */
91 int
92 link_stats_is_fresh(const struct link_stats *stats)
93 {
94  return (stats != NULL)
95  && clock_time() - stats->last_tx_time < FRESHNESS_EXPIRATION_TIME
96  && stats->freshness >= FRESHNESS_TARGET;
97 }
98 /*---------------------------------------------------------------------------*/
99 #if LINK_STATS_INIT_ETX_FROM_RSSI
100 uint16_t
101 guess_etx_from_rssi(const struct link_stats *stats)
102 {
103  if(stats != NULL) {
104  if(stats->rssi == 0) {
105  return ETX_DEFAULT * ETX_DIVISOR;
106  } else {
107  /* A rough estimate of PRR from RSSI, as a linear function where:
108  * RSSI >= -60 results in PRR of 1
109  * RSSI <= -90 results in PRR of 0
110  * prr = (bounded_rssi - RSSI_LOW) / (RSSI_DIFF)
111  * etx = ETX_DIVOSOR / ((bounded_rssi - RSSI_LOW) / RSSI_DIFF)
112  * etx = (RSSI_DIFF * ETX_DIVOSOR) / (bounded_rssi - RSSI_LOW)
113  * */
114 #define ETX_INIT_MAX 3
115 #define RSSI_HIGH -60
116 #define RSSI_LOW -90
117 #define RSSI_DIFF (RSSI_HIGH - RSSI_LOW)
118  uint16_t etx;
119  int16_t bounded_rssi = stats->rssi;
120  bounded_rssi = MIN(bounded_rssi, RSSI_HIGH);
121  bounded_rssi = MAX(bounded_rssi, RSSI_LOW + 1);
122  etx = RSSI_DIFF * ETX_DIVISOR / (bounded_rssi - RSSI_LOW);
123  return MIN(etx, ETX_INIT_MAX * ETX_DIVISOR);
124  }
125  }
126  return 0xffff;
127 }
128 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
129 /*---------------------------------------------------------------------------*/
130 /* Packet sent callback. Updates stats for transmissions to lladdr */
131 void
132 link_stats_packet_sent(const linkaddr_t *lladdr, int status, int numtx)
133 {
134  struct link_stats *stats;
135 #if !LINK_STATS_ETX_FROM_PACKET_COUNT
136  uint16_t packet_etx;
137  uint8_t ewma_alpha;
138 #endif /* !LINK_STATS_ETX_FROM_PACKET_COUNT */
139 
140  if(status != MAC_TX_OK && status != MAC_TX_NOACK) {
141  /* Do not penalize the ETX when collisions or transmission errors occur. */
142  return;
143  }
144 
145  stats = nbr_table_get_from_lladdr(link_stats, lladdr);
146  if(stats == NULL) {
147  /* If transmission failed, do not add the neighbor, as the neighbor might not exist anymore */
148  if(status != MAC_TX_OK) {
149  return;
150  }
151 
152  /* Add the neighbor */
153  stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
154  if(stats != NULL) {
155 #if LINK_STATS_INIT_ETX_FROM_RSSI
156  stats->etx = guess_etx_from_rssi(stats);
157 #else /* LINK_STATS_INIT_ETX_FROM_RSSI */
158  stats->etx = ETX_DEFAULT * ETX_DIVISOR;
159 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
160  } else {
161  return; /* No space left, return */
162  }
163  }
164 
165  /* Update last timestamp and freshness */
166  stats->last_tx_time = clock_time();
167  stats->freshness = MIN(stats->freshness + numtx, FRESHNESS_MAX);
168 
169 #if LINK_STATS_PACKET_COUNTERS
170  /* Update paket counters */
171  stats->cnt_current.num_packets_tx += numtx;
172  if(status == MAC_TX_OK) {
173  stats->cnt_current.num_packets_acked++;
174  }
175 #endif
176 
177  /* Add penalty in case of no-ACK */
178  if(status == MAC_TX_NOACK) {
179  numtx += ETX_NOACK_PENALTY;
180  }
181 
182 #if LINK_STATS_ETX_FROM_PACKET_COUNT
183  /* Compute ETX from packet and ACK count */
184  /* Halve both counter after TX_COUNT_MAX */
185  if(stats->tx_count + numtx > TX_COUNT_MAX) {
186  stats->tx_count /= 2;
187  stats->ack_count /= 2;
188  }
189  /* Update tx_count and ack_count */
190  stats->tx_count += numtx;
191  if(status == MAC_TX_OK) {
192  stats->ack_count++;
193  }
194  /* Compute ETX */
195  if(stats->ack_count > 0) {
196  stats->etx = ((uint16_t)stats->tx_count * ETX_DIVISOR) / stats->ack_count;
197  } else {
198  stats->etx = (uint16_t)MAX(ETX_NOACK_PENALTY, stats->tx_count) * ETX_DIVISOR;
199  }
200 #else /* LINK_STATS_ETX_FROM_PACKET_COUNT */
201  /* Compute ETX using an EWMA */
202 
203  /* ETX used for this update */
204  packet_etx = numtx * ETX_DIVISOR;
205  /* ETX alpha used for this update */
206  ewma_alpha = link_stats_is_fresh(stats) ? EWMA_ALPHA : EWMA_BOOTSTRAP_ALPHA;
207 
208  /* Compute EWMA and update ETX */
209  stats->etx = ((uint32_t)stats->etx * (EWMA_SCALE - ewma_alpha) +
210  (uint32_t)packet_etx * ewma_alpha) / EWMA_SCALE;
211 #endif /* LINK_STATS_ETX_FROM_PACKET_COUNT */
212 }
213 /*---------------------------------------------------------------------------*/
214 /* Packet input callback. Updates statistics for receptions on a given link */
215 void
216 link_stats_input_callback(const linkaddr_t *lladdr)
217 {
218  struct link_stats *stats;
219  int16_t packet_rssi = packetbuf_attr(PACKETBUF_ATTR_RSSI);
220 
221  stats = nbr_table_get_from_lladdr(link_stats, lladdr);
222  if(stats == NULL) {
223  /* Add the neighbor */
224  stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
225  if(stats != NULL) {
226  /* Initialize */
227  stats->rssi = packet_rssi;
228 #if LINK_STATS_INIT_ETX_FROM_RSSI
229  stats->etx = guess_etx_from_rssi(stats);
230 #else /* LINK_STATS_INIT_ETX_FROM_RSSI */
231  stats->etx = ETX_DEFAULT * ETX_DIVISOR;
232 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
233 #if LINK_STATS_PACKET_COUNTERS
234  stats->cnt_current.num_packets_rx = 1;
235 #endif
236  }
237  return;
238  }
239 
240  /* Update RSSI EWMA */
241  stats->rssi = ((int32_t)stats->rssi * (EWMA_SCALE - EWMA_ALPHA) +
242  (int32_t)packet_rssi * EWMA_ALPHA) / EWMA_SCALE;
243 
244 #if LINK_STATS_PACKET_COUNTERS
245  stats->cnt_current.num_packets_rx++;
246 #endif
247 }
248 /*---------------------------------------------------------------------------*/
249 #if LINK_STATS_PACKET_COUNTERS
250 /*---------------------------------------------------------------------------*/
251 static void
252 print_and_update_counters(void)
253 {
254  struct link_stats *stats;
255 
256  for(stats = nbr_table_head(link_stats); stats != NULL;
257  stats = nbr_table_next(link_stats, stats)) {
258 
259  struct link_packet_counter *c = &stats->cnt_current;
260 
261  LOG_INFO("num packets: tx=%u ack=%u rx=%u to=",
262  c->num_packets_tx, c->num_packets_acked, c->num_packets_rx);
263  LOG_INFO_LLADDR(link_stats_get_lladdr(stats));
264  LOG_INFO_("\n");
265 
266  stats->cnt_total.num_packets_tx += stats->cnt_current.num_packets_tx;
267  stats->cnt_total.num_packets_acked += stats->cnt_current.num_packets_acked;
268  stats->cnt_total.num_packets_rx += stats->cnt_current.num_packets_rx;
269  memset(&stats->cnt_current, 0, sizeof(stats->cnt_current));
270  }
271 }
272 /*---------------------------------------------------------------------------*/
273 #endif /* LINK_STATS_PACKET_COUNTERS */
274 /*---------------------------------------------------------------------------*/
275 /* Periodic timer called at a period of FRESHNESS_HALF_LIFE */
276 static void
277 periodic(void *ptr)
278 {
279  /* Age (by halving) freshness counter of all neighbors */
280  struct link_stats *stats;
281  ctimer_reset(&periodic_timer);
282  for(stats = nbr_table_head(link_stats); stats != NULL; stats = nbr_table_next(link_stats, stats)) {
283  stats->freshness >>= 1;
284  }
285 
286 #if LINK_STATS_PACKET_COUNTERS
287  print_and_update_counters();
288 #endif
289 }
290 /*---------------------------------------------------------------------------*/
291 /* Resets link-stats module */
292 void
293 link_stats_reset(void)
294 {
295  struct link_stats *stats;
296  stats = nbr_table_head(link_stats);
297  while(stats != NULL) {
298  nbr_table_remove(link_stats, stats);
299  stats = nbr_table_next(link_stats, stats);
300  }
301 }
302 /*---------------------------------------------------------------------------*/
303 /* Initializes link-stats module */
304 void
305 link_stats_init(void)
306 {
307  nbr_table_register(link_stats, NULL);
308  ctimer_set(&periodic_timer, FRESHNESS_HALF_LIFE, periodic, NULL);
309 }
void ctimer_reset(struct ctimer *c)
Reset a callback timer with the same interval as was previously set.
Definition: ctimer.c:125
The MAC layer transmission was OK.
Definition: mac.h:87
void ctimer_set(struct ctimer *c, clock_time_t t, void(*f)(void *), void *ptr)
Set a callback timer.
Definition: ctimer.c:99
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
The MAC layer deferred the transmission for a later time.
Definition: mac.h:94
Header file for the Packet buffer (packetbuf) management
Header file for the logging system