Contiki 2.6
|
00001 /* 00002 * Copyright (c) 2010, Swedish Institute of Computer Science. 00003 * All rights reserved. 00004 * 00005 * Redistribution and use in source and binary forms, with or without 00006 * modification, are permitted provided that the following conditions 00007 * are met: 00008 * 1. Redistributions of source code must retain the above copyright 00009 * notice, this list of conditions and the following disclaimer. 00010 * 2. Redistributions in binary form must reproduce the above copyright 00011 * notice, this list of conditions and the following disclaimer in the 00012 * documentation and/or other materials provided with the distribution. 00013 * 3. Neither the name of the Institute nor the names of its contributors 00014 * may be used to endorse or promote products derived from this software 00015 * without specific prior written permission. 00016 * 00017 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 00018 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00019 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00020 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 00021 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00022 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00023 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00024 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00025 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00026 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00027 * SUCH DAMAGE. 00028 * 00029 * This file is part of the Contiki operating system. 00030 * 00031 */ 00032 00033 /** 00034 * \file 00035 * Common functionality for phase optimization in duty cycling radio protocols 00036 * \author 00037 * Adam Dunkels <adam@sics.se> 00038 */ 00039 00040 #include "net/mac/phase.h" 00041 #include "net/packetbuf.h" 00042 #include "sys/clock.h" 00043 #include "lib/memb.h" 00044 #include "sys/ctimer.h" 00045 #include "net/queuebuf.h" 00046 #include "dev/watchdog.h" 00047 #include "dev/leds.h" 00048 00049 struct phase_queueitem { 00050 struct ctimer timer; 00051 mac_callback_t mac_callback; 00052 void *mac_callback_ptr; 00053 struct queuebuf *q; 00054 struct rdc_buf_list *buf_list; 00055 }; 00056 00057 #define PHASE_DEFER_THRESHOLD 1 00058 #define PHASE_QUEUESIZE 8 00059 00060 #define MAX_NOACKS 16 00061 00062 #define MAX_NOACKS_TIME CLOCK_SECOND * 30 00063 00064 MEMB(queued_packets_memb, struct phase_queueitem, PHASE_QUEUESIZE); 00065 00066 #define DEBUG 0 00067 #if DEBUG 00068 #include <stdio.h> 00069 #define PRINTF(...) printf(__VA_ARGS__) 00070 #define PRINTDEBUG(...) printf(__VA_ARGS__) 00071 #else 00072 #define PRINTF(...) 00073 #define PRINTDEBUG(...) 00074 #endif 00075 /*---------------------------------------------------------------------------*/ 00076 struct phase * 00077 find_neighbor(const struct phase_list *list, const rimeaddr_t *addr) 00078 { 00079 struct phase *e; 00080 for(e = list_head(*list->list); e != NULL; e = list_item_next(e)) { 00081 if(rimeaddr_cmp(addr, &e->neighbor)) { 00082 return e; 00083 } 00084 } 00085 return NULL; 00086 } 00087 /*---------------------------------------------------------------------------*/ 00088 void 00089 phase_remove(const struct phase_list *list, const rimeaddr_t *neighbor) 00090 { 00091 struct phase *e; 00092 e = find_neighbor(list, neighbor); 00093 if(e != NULL) { 00094 list_remove(*list->list, e); 00095 memb_free(list->memb, e); 00096 } 00097 } 00098 /*---------------------------------------------------------------------------*/ 00099 void 00100 phase_update(const struct phase_list *list, 00101 const rimeaddr_t *neighbor, rtimer_clock_t time, 00102 int mac_status) 00103 { 00104 struct phase *e; 00105 00106 /* If we have an entry for this neighbor already, we renew it. */ 00107 e = find_neighbor(list, neighbor); 00108 if(e != NULL) { 00109 if(mac_status == MAC_TX_OK) { 00110 #if PHASE_DRIFT_CORRECT 00111 e->drift = time-e->time; 00112 #endif 00113 e->time = time; 00114 } 00115 /* If the neighbor didn't reply to us, it may have switched 00116 phase (rebooted). We try a number of transmissions to it 00117 before we drop it from the phase list. */ 00118 if(mac_status == MAC_TX_NOACK) { 00119 PRINTF("phase noacks %d to %d.%d\n", e->noacks, neighbor->u8[0], neighbor->u8[1]); 00120 e->noacks++; 00121 if(e->noacks == 1) { 00122 timer_set(&e->noacks_timer, MAX_NOACKS_TIME); 00123 } 00124 if(e->noacks >= MAX_NOACKS || timer_expired(&e->noacks_timer)) { 00125 PRINTF("drop %d\n", neighbor->u8[0]); 00126 list_remove(*list->list, e); 00127 memb_free(list->memb, e); 00128 return; 00129 } 00130 } else if(mac_status == MAC_TX_OK) { 00131 e->noacks = 0; 00132 } 00133 } else { 00134 /* No matching phase was found, so we allocate a new one. */ 00135 if(mac_status == MAC_TX_OK && e == NULL) { 00136 e = memb_alloc(list->memb); 00137 if(e == NULL) { 00138 PRINTF("phase alloc NULL\n"); 00139 /* We could not allocate memory for this phase, so we drop 00140 the last item on the list and reuse it for our phase. */ 00141 e = list_chop(*list->list); 00142 } 00143 rimeaddr_copy(&e->neighbor, neighbor); 00144 e->time = time; 00145 #if PHASE_DRIFT_CORRECT 00146 e->drift = 0; 00147 #endif 00148 e->noacks = 0; 00149 list_push(*list->list, e); 00150 } 00151 } 00152 } 00153 /*---------------------------------------------------------------------------*/ 00154 static void 00155 send_packet(void *ptr) 00156 { 00157 struct phase_queueitem *p = ptr; 00158 00159 if(p->buf_list == NULL) { 00160 queuebuf_to_packetbuf(p->q); 00161 queuebuf_free(p->q); 00162 NETSTACK_RDC.send(p->mac_callback, p->mac_callback_ptr); 00163 } else { 00164 NETSTACK_RDC.send_list(p->mac_callback, p->mac_callback_ptr, p->buf_list); 00165 } 00166 00167 memb_free(&queued_packets_memb, p); 00168 } 00169 /*---------------------------------------------------------------------------*/ 00170 phase_status_t 00171 phase_wait(struct phase_list *list, 00172 const rimeaddr_t *neighbor, rtimer_clock_t cycle_time, 00173 rtimer_clock_t guard_time, 00174 mac_callback_t mac_callback, void *mac_callback_ptr, 00175 struct rdc_buf_list *buf_list) 00176 { 00177 struct phase *e; 00178 // const rimeaddr_t *neighbor = packetbuf_addr(PACKETBUF_ADDR_RECEIVER); 00179 /* We go through the list of phases to find if we have recorded a 00180 phase for this particular neighbor. If so, we can compute the 00181 time for the next expected phase and setup a ctimer to switch on 00182 the radio just before the phase. */ 00183 e = find_neighbor(list, neighbor); 00184 if(e != NULL) { 00185 rtimer_clock_t wait, now, expected, sync; 00186 clock_time_t ctimewait; 00187 00188 /* We expect phases to happen every CYCLE_TIME time 00189 units. The next expected phase is at time e->time + 00190 CYCLE_TIME. To compute a relative offset, we subtract 00191 with clock_time(). Because we are only interested in turning 00192 on the radio within the CYCLE_TIME period, we compute the 00193 waiting time with modulo CYCLE_TIME. */ 00194 00195 /* printf("neighbor phase 0x%02x (cycle 0x%02x)\n", e->time & (cycle_time - 1), 00196 cycle_time);*/ 00197 00198 /* if(e->noacks > 0) { 00199 printf("additional wait %d\n", additional_wait); 00200 }*/ 00201 00202 now = RTIMER_NOW(); 00203 00204 sync = (e == NULL) ? now : e->time; 00205 00206 #if PHASE_DRIFT_CORRECT 00207 { 00208 int32_t s; 00209 if(e->drift > cycle_time) { 00210 s = e->drift % cycle_time / (e->drift / cycle_time); /* drift per cycle */ 00211 s = s * (now - sync) / cycle_time; /* estimated drift to now */ 00212 sync += s; /* add it in */ 00213 } 00214 } 00215 #endif 00216 00217 /* Check if cycle_time is a power of two */ 00218 if(!(cycle_time & (cycle_time - 1))) { 00219 /* Faster if cycle_time is a power of two */ 00220 wait = (rtimer_clock_t)((sync - now) & (cycle_time - 1)); 00221 } else { 00222 /* Works generally */ 00223 wait = cycle_time - (rtimer_clock_t)((now - sync) % cycle_time); 00224 } 00225 00226 if(wait < guard_time) { 00227 wait += cycle_time; 00228 } 00229 00230 ctimewait = (CLOCK_SECOND * (wait - guard_time)) / RTIMER_ARCH_SECOND; 00231 00232 if(ctimewait > PHASE_DEFER_THRESHOLD) { 00233 struct phase_queueitem *p; 00234 00235 p = memb_alloc(&queued_packets_memb); 00236 if(p != NULL) { 00237 if(buf_list == NULL) { 00238 p->q = queuebuf_new_from_packetbuf(); 00239 } 00240 p->mac_callback = mac_callback; 00241 p->mac_callback_ptr = mac_callback_ptr; 00242 p->buf_list = buf_list; 00243 ctimer_set(&p->timer, ctimewait, send_packet, p); 00244 return PHASE_DEFERRED; 00245 } else { 00246 memb_free(&queued_packets_memb, p); 00247 } 00248 } 00249 00250 expected = now + wait - guard_time; 00251 if(!RTIMER_CLOCK_LT(expected, now)) { 00252 /* Wait until the receiver is expected to be awake */ 00253 // printf("%d ",expected%cycle_time); //for spreadsheet export 00254 while(RTIMER_CLOCK_LT(RTIMER_NOW(), expected)); 00255 } 00256 return PHASE_SEND_NOW; 00257 } 00258 return PHASE_UNKNOWN; 00259 } 00260 /*---------------------------------------------------------------------------*/ 00261 void 00262 phase_init(struct phase_list *list) 00263 { 00264 list_init(*list->list); 00265 memb_init(list->memb); 00266 memb_init(&queued_packets_memb); 00267 } 00268 /*---------------------------------------------------------------------------*/