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 #define DEBUG 0
41 #if DEBUG
42 #define PRINTF(...) printf(__VA_ARGS__)
43 #else
44 #define PRINTF(...)
45 #endif
46 
47 /* Maximum value for the Tx count counter */
48 #define TX_COUNT_MAX 32
49 
50 /* Statistics with no update in FRESHNESS_EXPIRATION_TIMEOUT is not fresh */
51 #define FRESHNESS_EXPIRATION_TIME (10 * 60 * (clock_time_t)CLOCK_SECOND)
52 /* Half time for the freshness counter */
53 #define FRESHNESS_HALF_LIFE (15 * 60 * (clock_time_t)CLOCK_SECOND)
54 /* Statistics are fresh if the freshness counter is FRESHNESS_TARGET or more */
55 #define FRESHNESS_TARGET 4
56 /* Maximum value for the freshness counter */
57 #define FRESHNESS_MAX 16
58 
59 /* EWMA (exponential moving average) used to maintain statistics over time */
60 #define EWMA_SCALE 100
61 #define EWMA_ALPHA 10
62 #define EWMA_BOOTSTRAP_ALPHA 25
63 
64 /* ETX fixed point divisor. 128 is the value used by RPL (RFC 6551 and RFC 6719) */
65 #define ETX_DIVISOR LINK_STATS_ETX_DIVISOR
66 /* In case of no-ACK, add ETX_NOACK_PENALTY to the real Tx count, as a penalty */
67 #define ETX_NOACK_PENALTY 12
68 /* Initial ETX value */
69 #define ETX_DEFAULT 2
70 
71 /* Per-neighbor link statistics table */
72 NBR_TABLE(struct link_stats, link_stats);
73 
74 /* Called at a period of FRESHNESS_HALF_LIFE */
75 struct ctimer periodic_timer;
76 
77 /*---------------------------------------------------------------------------*/
78 /* Returns the neighbor's link stats */
79 const struct link_stats *
80 link_stats_from_lladdr(const linkaddr_t *lladdr)
81 {
82  return nbr_table_get_from_lladdr(link_stats, lladdr);
83 }
84 /*---------------------------------------------------------------------------*/
85 /* Are the statistics fresh? */
86 int
87 link_stats_is_fresh(const struct link_stats *stats)
88 {
89  return (stats != NULL)
90  && clock_time() - stats->last_tx_time < FRESHNESS_EXPIRATION_TIME
91  && stats->freshness >= FRESHNESS_TARGET;
92 }
93 /*---------------------------------------------------------------------------*/
94 #if LINK_STATS_INIT_ETX_FROM_RSSI
95 uint16_t
96 guess_etx_from_rssi(const struct link_stats *stats)
97 {
98  if(stats != NULL) {
99  if(stats->rssi == 0) {
100  return ETX_DEFAULT * ETX_DIVISOR;
101  } else {
102  /* A rough estimate of PRR from RSSI, as a linear function where:
103  * RSSI >= -60 results in PRR of 1
104  * RSSI <= -90 results in PRR of 0
105  * prr = (bounded_rssi - RSSI_LOW) / (RSSI_DIFF)
106  * etx = ETX_DIVOSOR / ((bounded_rssi - RSSI_LOW) / RSSI_DIFF)
107  * etx = (RSSI_DIFF * ETX_DIVOSOR) / (bounded_rssi - RSSI_LOW)
108  * */
109 #define ETX_INIT_MAX 3
110 #define RSSI_HIGH -60
111 #define RSSI_LOW -90
112 #define RSSI_DIFF (RSSI_HIGH - RSSI_LOW)
113  uint16_t etx;
114  int16_t bounded_rssi = stats->rssi;
115  bounded_rssi = MIN(bounded_rssi, RSSI_HIGH);
116  bounded_rssi = MAX(bounded_rssi, RSSI_LOW + 1);
117  etx = RSSI_DIFF * ETX_DIVISOR / (bounded_rssi - RSSI_LOW);
118  return MIN(etx, ETX_INIT_MAX * ETX_DIVISOR);
119  }
120  }
121  return 0xffff;
122 }
123 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
124 /*---------------------------------------------------------------------------*/
125 /* Packet sent callback. Updates stats for transmissions to lladdr */
126 void
127 link_stats_packet_sent(const linkaddr_t *lladdr, int status, int numtx)
128 {
129  struct link_stats *stats;
130 #if !LINK_STATS_ETX_FROM_PACKET_COUNT
131  uint16_t packet_etx;
132  uint8_t ewma_alpha;
133 #endif /* !LINK_STATS_ETX_FROM_PACKET_COUNT */
134 
135  if(status != MAC_TX_OK && status != MAC_TX_NOACK) {
136  /* Do not penalize the ETX when collisions or transmission errors occur. */
137  return;
138  }
139 
140  stats = nbr_table_get_from_lladdr(link_stats, lladdr);
141  if(stats == NULL) {
142  /* Add the neighbor */
143  stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
144  if(stats != NULL) {
145 #if LINK_STATS_INIT_ETX_FROM_RSSI
146  stats->etx = guess_etx_from_rssi(stats);
147 #else /* LINK_STATS_INIT_ETX_FROM_RSSI */
148  stats->etx = ETX_DEFAULT * ETX_DIVISOR;
149 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
150  } else {
151  return; /* No space left, return */
152  }
153  }
154 
155  /* Update last timestamp and freshness */
156  stats->last_tx_time = clock_time();
157  stats->freshness = MIN(stats->freshness + numtx, FRESHNESS_MAX);
158 
159  /* Add penalty in case of no-ACK */
160  if(status == MAC_TX_NOACK) {
161  numtx += ETX_NOACK_PENALTY;
162  }
163 
164 #if LINK_STATS_ETX_FROM_PACKET_COUNT
165  /* Compute ETX from packet and ACK count */
166  /* Halve both counter after TX_COUNT_MAX */
167  if(stats->tx_count + numtx > TX_COUNT_MAX) {
168  stats->tx_count /= 2;
169  stats->ack_count /= 2;
170  }
171  /* Update tx_count and ack_count */
172  stats->tx_count += numtx;
173  if(status == MAC_TX_OK) {
174  stats->ack_count++;
175  }
176  /* Compute ETX */
177  if(stats->ack_count > 0) {
178  stats->etx = ((uint16_t)stats->tx_count * ETX_DIVISOR) / stats->ack_count;
179  } else {
180  stats->etx = (uint16_t)MAX(ETX_NOACK_PENALTY, stats->tx_count) * ETX_DIVISOR;
181  }
182 #else /* LINK_STATS_ETX_FROM_PACKET_COUNT */
183  /* Compute ETX using an EWMA */
184 
185  /* ETX used for this update */
186  packet_etx = numtx * ETX_DIVISOR;
187  /* ETX alpha used for this update */
188  ewma_alpha = link_stats_is_fresh(stats) ? EWMA_ALPHA : EWMA_BOOTSTRAP_ALPHA;
189 
190  /* Compute EWMA and update ETX */
191  stats->etx = ((uint32_t)stats->etx * (EWMA_SCALE - ewma_alpha) +
192  (uint32_t)packet_etx * ewma_alpha) / EWMA_SCALE;
193 #endif /* LINK_STATS_ETX_FROM_PACKET_COUNT */
194 }
195 /*---------------------------------------------------------------------------*/
196 /* Packet input callback. Updates statistics for receptions on a given link */
197 void
198 link_stats_input_callback(const linkaddr_t *lladdr)
199 {
200  struct link_stats *stats;
201  int16_t packet_rssi = packetbuf_attr(PACKETBUF_ATTR_RSSI);
202 
203  stats = nbr_table_get_from_lladdr(link_stats, lladdr);
204  if(stats == NULL) {
205  /* Add the neighbor */
206  stats = nbr_table_add_lladdr(link_stats, lladdr, NBR_TABLE_REASON_LINK_STATS, NULL);
207  if(stats != NULL) {
208  /* Initialize */
209  stats->rssi = packet_rssi;
210 #if LINK_STATS_INIT_ETX_FROM_RSSI
211  stats->etx = guess_etx_from_rssi(stats);
212 #else /* LINK_STATS_INIT_ETX_FROM_RSSI */
213  stats->etx = ETX_DEFAULT * ETX_DIVISOR;
214 #endif /* LINK_STATS_INIT_ETX_FROM_RSSI */
215  }
216  return;
217  }
218 
219  /* Update RSSI EWMA */
220  stats->rssi = ((int32_t)stats->rssi * (EWMA_SCALE - EWMA_ALPHA) +
221  (int32_t)packet_rssi * EWMA_ALPHA) / EWMA_SCALE;
222 }
223 /*---------------------------------------------------------------------------*/
224 /* Periodic timer called at a period of FRESHNESS_HALF_LIFE */
225 static void
226 periodic(void *ptr)
227 {
228  /* Age (by halving) freshness counter of all neighbors */
229  struct link_stats *stats;
230  ctimer_reset(&periodic_timer);
231  for(stats = nbr_table_head(link_stats); stats != NULL; stats = nbr_table_next(link_stats, stats)) {
232  stats->freshness >>= 1;
233  }
234 }
235 /*---------------------------------------------------------------------------*/
236 /* Resets link-stats module */
237 void
238 link_stats_reset(void)
239 {
240  struct link_stats *stats;
241  stats = nbr_table_head(link_stats);
242  while(stats != NULL) {
243  nbr_table_remove(link_stats, stats);
244  stats = nbr_table_next(link_stats, stats);
245  }
246 }
247 /*---------------------------------------------------------------------------*/
248 /* Initializes link-stats module */
249 void
250 link_stats_init(void)
251 {
252  nbr_table_register(link_stats, NULL);
253  ctimer_set(&periodic_timer, FRESHNESS_HALF_LIFE, periodic, NULL);
254 }
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:84
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
Header file for the Packet buffer (packetbuf) management
The MAC layer deferred the transmission for a later time.
Definition: mac.h:91