Contiki 2.6

phase.c

Go to the documentation of this file.
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 /*---------------------------------------------------------------------------*/