Contiki 2.6

lpp.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2008, 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  * $Id: lpp.c,v 1.40 2010/12/02 15:55:17 dak664 Exp $
00032  */
00033 
00034 /**
00035  * \file
00036  *         Low power probing (R. Musaloiu-Elefteri, C. Liang,
00037  *         A. Terzis. Koala: Ultra-Low Power Data Retrieval in
00038  *         Wireless Sensor Networks, IPSN 2008)
00039  *
00040  * \author
00041  *         Adam Dunkels <adam@sics.se>
00042  *
00043  *
00044  * This is an implementation of the LPP (Low-Power Probing) MAC
00045  * protocol. LPP is a power-saving MAC protocol that works by sending
00046  * a probe packet each time the radio is turned on. If another node
00047  * wants to transmit a packet, it can do so after hearing the
00048  * probe. To send a packet, the sending node turns on its radio to
00049  * listen for probe packets.
00050  *
00051  */
00052 
00053 #include "dev/leds.h"
00054 #include "lib/list.h"
00055 #include "lib/memb.h"
00056 #include "lib/random.h"
00057 #include "net/rime.h"
00058 #include "net/netstack.h"
00059 #include "net/mac/mac.h"
00060 #include "net/mac/lpp.h"
00061 #include "net/packetbuf.h"
00062 #include "net/rime/announcement.h"
00063 #include "sys/compower.h"
00064 #include "net/mac/framer.h"
00065 
00066 #include <stdlib.h>
00067 #include <stdio.h>
00068 #include <string.h>
00069 
00070 #define DEBUG 0
00071 #if DEBUG
00072 #include <stdio.h>
00073 #define PRINTF(...) printf(__VA_ARGS__)
00074 #else
00075 #define PRINTF(...)
00076 #endif
00077 
00078 #define WITH_ACK_OPTIMIZATION         0
00079 #define WITH_PROBE_AFTER_RECEPTION    0
00080 #define WITH_PROBE_AFTER_TRANSMISSION 0
00081 #define WITH_ENCOUNTER_OPTIMIZATION   0
00082 #define WITH_ADAPTIVE_OFF_TIME        0
00083 #define WITH_PENDING_BROADCAST        0
00084 #define WITH_STREAMING                1
00085 
00086 #define LISTEN_TIME (CLOCK_SECOND / 128)
00087 #define OFF_TIME (CLOCK_SECOND / NETSTACK_RDC_CHANNEL_CHECK_RATE - LISTEN_TIME)
00088 
00089 #define PACKET_LIFETIME (LISTEN_TIME + OFF_TIME)
00090 #define UNICAST_TIMEOUT (1 * PACKET_LIFETIME + PACKET_LIFETIME / 2)
00091 #define PROBE_AFTER_TRANSMISSION_TIME (LISTEN_TIME * 2)
00092 
00093 #define LOWEST_OFF_TIME (CLOCK_SECOND / 8)
00094 
00095 #define ENCOUNTER_LIFETIME (16 * OFF_TIME)
00096 
00097 #ifdef QUEUEBUF_CONF_NUM
00098 #define MAX_QUEUED_PACKETS QUEUEBUF_CONF_NUM / 2
00099 #else /* QUEUEBUF_CONF_NUM */
00100 #define MAX_QUEUED_PACKETS 4
00101 #endif /* QUEUEBUF_CONF_NUM */
00102 
00103 
00104 /* If CLOCK_SECOND is less than 4, we may end up with an OFF_TIME that
00105    is 0 which will make compilation fail due to a modulo operation in
00106    the code. To ensure that OFF_TIME is greater than zero, we use the
00107    construct below. */
00108 #if OFF_TIME < 2
00109 #undef OFF_TIME
00110 #define OFF_TIME 2
00111 #endif
00112 
00113 struct announcement_data {
00114   uint16_t id;
00115   uint16_t value;
00116 };
00117 
00118 #define ANNOUNCEMENT_MSG_HEADERLEN 2
00119 struct announcement_msg {
00120   uint16_t num;
00121   struct announcement_data data[];
00122 };
00123 
00124 #define LPP_PROBE_HEADERLEN 2
00125 
00126 #define TYPE_PROBE        1
00127 #define TYPE_DATA         2
00128 struct lpp_hdr {
00129   uint16_t type;
00130   rimeaddr_t sender;
00131   rimeaddr_t receiver;
00132 };
00133 
00134 static uint8_t lpp_is_on;
00135 
00136 static struct compower_activity current_packet;
00137 
00138 static struct pt dutycycle_pt;
00139 static struct ctimer timer;
00140 
00141 static uint8_t is_listening = 0;
00142 static clock_time_t off_time_adjustment = 0;
00143 static clock_time_t off_time = OFF_TIME;
00144 
00145 struct queue_list_item {
00146   struct queue_list_item *next;
00147   struct queuebuf *packet;
00148   struct ctimer removal_timer;
00149   struct compower_activity compower;
00150   mac_callback_t sent_callback;
00151   void *sent_callback_ptr;
00152   uint8_t num_transmissions;
00153 #if WITH_PENDING_BROADCAST
00154   uint8_t broadcast_flag;
00155 #endif /* WITH_PENDING_BROADCAST */
00156 };
00157 
00158 #define BROADCAST_FLAG_NONE    0
00159 #define BROADCAST_FLAG_WAITING 1
00160 #define BROADCAST_FLAG_PENDING 2
00161 #define BROADCAST_FLAG_SEND    3
00162 
00163 LIST(pending_packets_list);
00164 LIST(queued_packets_list);
00165 MEMB(queued_packets_memb, struct queue_list_item, MAX_QUEUED_PACKETS);
00166 
00167 struct encounter {
00168   struct encounter *next;
00169   rimeaddr_t neighbor;
00170   clock_time_t time;
00171   struct ctimer remove_timer;
00172   struct ctimer turn_on_radio_timer;
00173 };
00174 
00175 #define MAX_ENCOUNTERS 4
00176 LIST(encounter_list);
00177 MEMB(encounter_memb, struct encounter, MAX_ENCOUNTERS);
00178 
00179 static uint8_t is_streaming = 0;
00180 #if WITH_STREAMING
00181 static struct ctimer stream_probe_timer, stream_off_timer;
00182 #define STREAM_PROBE_TIME CLOCK_SECOND / 128
00183 #define STREAM_OFF_TIME CLOCK_SECOND / 2
00184 #endif /* WITH_STREAMING */
00185 
00186 #ifndef MIN
00187 #define MIN(a, b) ((a) < (b)? (a) : (b))
00188 #endif /* MIN */
00189 
00190 /*---------------------------------------------------------------------------*/
00191 static void
00192 turn_radio_on(void)
00193 {
00194   NETSTACK_RADIO.on();
00195   /*  leds_on(LEDS_YELLOW);*/
00196 }
00197 /*---------------------------------------------------------------------------*/
00198 static void
00199 turn_radio_off(void)
00200 {
00201   if(lpp_is_on && is_streaming == 0) {
00202     NETSTACK_RADIO.off();
00203   }
00204   /*  leds_off(LEDS_YELLOW);*/
00205 }
00206 /*---------------------------------------------------------------------------*/
00207 static void
00208 remove_encounter(void *encounter)
00209 {
00210   struct encounter *e = encounter;
00211 
00212   ctimer_stop(&e->remove_timer);
00213   ctimer_stop(&e->turn_on_radio_timer);
00214   list_remove(encounter_list, e);
00215   memb_free(&encounter_memb, e);
00216 }
00217 /*---------------------------------------------------------------------------*/
00218 static void
00219 register_encounter(rimeaddr_t *neighbor, clock_time_t time)
00220 {
00221   struct encounter *e;
00222 
00223   /* If we have an entry for this neighbor already, we renew it. */
00224   for(e = list_head(encounter_list); e != NULL; e = list_item_next(e)) {
00225     if(rimeaddr_cmp(neighbor, &e->neighbor)) {
00226       e->time = time;
00227       ctimer_set(&e->remove_timer, ENCOUNTER_LIFETIME, remove_encounter, e);
00228       break;
00229     }
00230   }
00231   /* No matchin encounter was found, so we allocate a new one. */
00232   if(e == NULL) {
00233     e = memb_alloc(&encounter_memb);
00234     if(e == NULL) {
00235       /* We could not allocate memory for this encounter, so we just drop it. */
00236       return;
00237     }
00238     rimeaddr_copy(&e->neighbor, neighbor);
00239     e->time = time;
00240     ctimer_set(&e->remove_timer, ENCOUNTER_LIFETIME, remove_encounter, e);
00241     list_add(encounter_list, e);
00242   }
00243 }
00244 
00245 #if WITH_ENCOUNTER_OPTIMIZATION
00246 /*---------------------------------------------------------------------------*/
00247 static void
00248 turn_radio_on_callback(void *packet)
00249 {
00250   struct queue_list_item *p = packet;
00251 
00252   list_remove(pending_packets_list, p);
00253   list_add(queued_packets_list, p);
00254   turn_radio_on();
00255 
00256   /*  printf("enc\n");*/
00257 }
00258 #endif /* WITH_ENCOUNTER_OPTIMIZATION */
00259 
00260 /*---------------------------------------------------------------------------*/
00261 static void
00262 stream_off(void *dummy)
00263 {
00264   is_streaming = 0;
00265 }
00266 /*---------------------------------------------------------------------------*/
00267 /* This function goes through all encounters to see if it finds a
00268    matching neighbor. If so, we set a ctimer that will turn on the
00269    radio just before we expect the neighbor to send a probe packet. If
00270    we cannot find a matching encounter, we just turn on the radio.
00271 
00272    The outbound packet is put on either the pending_packets_list or
00273    the queued_packets_list, depending on if the packet should be sent
00274    immediately.
00275 */
00276 static void
00277 turn_radio_on_for_neighbor(rimeaddr_t *neighbor, struct queue_list_item *i)
00278 {
00279 
00280 #if WITH_STREAMING
00281   if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) ==
00282      PACKETBUF_ATTR_PACKET_TYPE_STREAM) {
00283     is_streaming = 1;
00284     turn_radio_on();
00285     list_add(queued_packets_list, i);
00286     ctimer_set(&stream_off_timer, STREAM_OFF_TIME,
00287                stream_off, NULL);
00288     return;
00289   }
00290 #endif /* WITH_STREAMING */
00291   
00292   if(rimeaddr_cmp(neighbor, &rimeaddr_null)) {
00293 #if ! WITH_PENDING_BROADCAST
00294     /* We have been asked to turn on the radio for a broadcast, so we
00295        just turn on the radio. */
00296     turn_radio_on();
00297 #endif /* ! WITH_PENDING_BROADCAST */
00298     list_add(queued_packets_list, i);
00299     return;
00300   }
00301 
00302 #if WITH_ENCOUNTER_OPTIMIZATION
00303   struct encounter *e;
00304   
00305   /* We go through the list of encounters to find if we have recorded
00306      an encounter with this particular neighbor. If so, we can compute
00307      the time for the next expected encounter and setup a ctimer to
00308      switch on the radio just before the encounter. */
00309   for(e = list_head(encounter_list); e != NULL; e = list_item_next(e)) {
00310     if(rimeaddr_cmp(neighbor, &e->neighbor)) {
00311       clock_time_t wait, now;
00312 
00313       /* We expect encounters to happen roughly every OFF_TIME time
00314          units. The next expected encounter is at time e->time +
00315          OFF_TIME. To compute a relative offset, we subtract with
00316          clock_time(). Because we are only interested in turning on
00317          the radio within the OFF_TIME period, we compute the waiting
00318          time with modulo OFF_TIME. */
00319 
00320       now = clock_time();
00321       wait = (((clock_time_t)(e->time - now)) % (OFF_TIME + LISTEN_TIME)) -
00322         2 * LISTEN_TIME;
00323 
00324       /*      printf("now %d e %d e-n %d w %d %d\n", now, e->time, e->time - now, (e->time - now) % (OFF_TIME), wait);
00325       
00326       printf("Time now %lu last encounter %lu next expected encouter %lu wait %lu/%d (%lu)\n",
00327              (1000ul * (unsigned long)now) / CLOCK_SECOND,
00328              (1000ul * (unsigned long)e->time) / CLOCK_SECOND,
00329              (1000ul * (unsigned long)(e->time + OFF_TIME)) / CLOCK_SECOND,
00330              (1000ul * (unsigned long)wait) / CLOCK_SECOND, wait,
00331              (1000ul * (unsigned long)(wait + now)) / CLOCK_SECOND);*/
00332       
00333       /*      printf("Neighbor %d.%d found encounter, waiting %d ticks\n",
00334               neighbor->u8[0], neighbor->u8[1], wait);*/
00335       
00336       ctimer_set(&e->turn_on_radio_timer, wait, turn_radio_on_callback, i);
00337       list_add(pending_packets_list, i);
00338       return;
00339     }
00340   }
00341 #endif /* WITH_ENCOUNTER_OPTIMIZATION */
00342   
00343   /* We did not find the neighbor in the list of recent encounters, so
00344      we just turn on the radio. */
00345   /*  printf("Neighbor %d.%d not found in recent encounters\n",
00346       neighbor->u8[0], neighbor->u8[1]);*/
00347   turn_radio_on();
00348   list_add(queued_packets_list, i);
00349   return;
00350 }
00351 /*---------------------------------------------------------------------------*/
00352 static void
00353 remove_queued_packet(struct queue_list_item *i, uint8_t tx_ok)
00354 {
00355   mac_callback_t sent;
00356   void *ptr;
00357   int num_transmissions = 0;
00358   int status;
00359   
00360   PRINTF("%d.%d: removing queued packet\n",
00361          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00362 
00363 
00364   queuebuf_to_packetbuf(i->packet);
00365   
00366   ctimer_stop(&i->removal_timer);
00367   queuebuf_free(i->packet);
00368   list_remove(pending_packets_list, i);
00369   list_remove(queued_packets_list, i);
00370 
00371   /* XXX potential optimization */
00372   if(list_length(queued_packets_list) == 0 && is_listening == 0) {
00373     turn_radio_off();
00374     compower_accumulate(&i->compower);
00375   }
00376 
00377   sent = i->sent_callback;
00378   ptr = i->sent_callback_ptr;
00379   num_transmissions = i->num_transmissions;
00380   memb_free(&queued_packets_memb, i);
00381   if(num_transmissions == 0 || tx_ok == 0) {
00382     status = MAC_TX_NOACK;
00383   } else {
00384     status = MAC_TX_OK;
00385   }
00386   mac_call_sent_callback(sent, ptr, status, num_transmissions);
00387 }
00388 /*---------------------------------------------------------------------------*/
00389 static void
00390 remove_queued_old_packet_callback(void *item)
00391 {
00392   remove_queued_packet(item, 0);
00393 }
00394 
00395 #if WITH_PENDING_BROADCAST
00396 /*---------------------------------------------------------------------------*/
00397 static void
00398 remove_queued_broadcast_packet_callback(void *item)
00399 {
00400   remove_queued_packet(item, 1);
00401 }
00402 /*---------------------------------------------------------------------------*/
00403 static void
00404 set_broadcast_flag(struct queue_list_item *i, uint8_t flag)
00405 {
00406   i->broadcast_flag = flag;
00407   ctimer_set(&i->removal_timer, PACKET_LIFETIME,
00408              remove_queued_broadcast_packet_callback, i);
00409 }
00410 #endif /* WITH_PENDING_BROADCAST */
00411 /*---------------------------------------------------------------------------*/
00412 static void
00413 listen_callback(int periods)
00414 {
00415   is_listening = periods;
00416   turn_radio_on();
00417 }
00418 /*---------------------------------------------------------------------------*/
00419 /**
00420  * Send a probe packet.
00421  */
00422 static void
00423 send_probe(void)
00424 {
00425   struct lpp_hdr *hdr;
00426   struct announcement_msg *adata;
00427   struct announcement *a;
00428 
00429   /* Set up the probe header. */
00430   packetbuf_clear();
00431   packetbuf_set_datalen(sizeof(struct lpp_hdr));
00432   hdr = packetbuf_dataptr();
00433   hdr->type = TYPE_PROBE;
00434   rimeaddr_copy(&hdr->sender, &rimeaddr_node_addr);
00435   /*  rimeaddr_copy(&hdr->receiver, packetbuf_addr(PACKETBUF_ADDR_RECEIVER));*/
00436   rimeaddr_copy(&hdr->receiver, &rimeaddr_null);
00437 
00438   packetbuf_set_addr(PACKETBUF_ADDR_RECEIVER, &rimeaddr_null);
00439   {
00440     int hdrlen = NETSTACK_FRAMER.create();
00441     if(hdrlen < 0) {
00442       /* Failed to send */
00443       return;
00444     }
00445   }
00446   
00447   /* Construct the announcements */
00448   adata = (struct announcement_msg *)((char *)hdr + sizeof(struct lpp_hdr));
00449   
00450   adata->num = 0;
00451   for(a = announcement_list(); a != NULL; a = list_item_next(a)) {
00452     adata->data[adata->num].id = a->id;
00453     adata->data[adata->num].value = a->value;
00454     adata->num++;
00455   }
00456 
00457   packetbuf_set_datalen(sizeof(struct lpp_hdr) +
00458                       ANNOUNCEMENT_MSG_HEADERLEN +
00459                       sizeof(struct announcement_data) * adata->num);
00460 
00461   /*  PRINTF("Sending probe\n");*/
00462 
00463   /*  printf("probe\n");*/
00464 
00465   if(NETSTACK_RADIO.channel_clear()) {
00466     NETSTACK_RADIO.send(packetbuf_hdrptr(), packetbuf_totlen());
00467   } else {
00468     off_time_adjustment = random_rand() % (OFF_TIME / 2);
00469   }
00470 
00471   compower_accumulate(&compower_idle_activity);
00472 }
00473 /*---------------------------------------------------------------------------*/
00474 static void
00475 send_stream_probe(void *dummy)
00476 {
00477   /* Turn on the radio for sending a probe packet and 
00478      anticipating a data packet from a neighbor. */
00479   turn_radio_on();
00480   
00481   /* Send a probe packet. */
00482   send_probe();
00483 
00484 #if WITH_STREAMING
00485   is_streaming = 1;
00486 #endif /* WITH_STREAMING */
00487 }
00488 /*---------------------------------------------------------------------------*/
00489 static int
00490 num_packets_to_send(void)
00491 {
00492 #if WITH_PENDING_BROADCAST
00493   struct queue_list_item *i;
00494   int num = 0;
00495   
00496   for(i = list_head(queued_packets_list); i != NULL; i = list_item_next(i)) {
00497     if(i->broadcast_flag == BROADCAST_FLAG_SEND ||
00498        i->broadcast_flag == BROADCAST_FLAG_NONE) {
00499       ++num;
00500     }
00501   }
00502   return num;
00503 #else /* WITH_PENDING_BROADCAST */
00504   return list_length(queued_packets_list);
00505 #endif /* WITH_PENDING_BROADCAST */
00506 }
00507 /*---------------------------------------------------------------------------*/
00508 /**
00509  * Duty cycle the radio and send probes. This function is called
00510  * repeatedly by a ctimer. The function restart_dutycycle() is used to
00511  * (re)start the duty cycling.
00512  */
00513 static int
00514 dutycycle(void *ptr)
00515 {
00516   struct ctimer *t = ptr;
00517         
00518   PT_BEGIN(&dutycycle_pt);
00519 
00520   while(1) {
00521 
00522 #if WITH_PENDING_BROADCAST
00523     {
00524         /* Before sending the probe, we mark all broadcast packets in
00525            our output queue to be pending. This means that they are
00526            ready to be sent, once we know that no neighbor is
00527            currently broadcasting. */
00528       for(p = list_head(queued_packets_list); p != NULL; p = list_item_next(p)) {
00529           if(p->broadcast_flag == BROADCAST_FLAG_WAITING) {
00530             PRINTF("wait -> pending\n");
00531             set_broadcast_flag(p, BROADCAST_FLAG_PENDING);
00532           }
00533         }
00534       }
00535 #endif /* WITH_PENDING_BROADCAST */
00536     
00537     /* Turn on the radio for sending a probe packet and 
00538        anticipating a data packet from a neighbor. */
00539     turn_radio_on();
00540 
00541     /* Send a probe packet. */
00542     send_probe();
00543 
00544     /* Set a timer so that we keep the radio on for LISTEN_TIME. */
00545     ctimer_set(t, LISTEN_TIME, (void (*)(void *))dutycycle, t);
00546     PT_YIELD(&dutycycle_pt);
00547 
00548 #if WITH_PENDING_BROADCAST
00549     {
00550       struct queue_list_item *p;
00551       /* Go through the list of packets we are waiting to send, and
00552          check if there are any pending broadcasts in the list. If
00553          there are pending broadcasts, and we did not receive any
00554          broadcast packets from a neighbor in response to our probe,
00555          we mark the broadcasts as being ready to send. */
00556       for(p = list_head(queued_packets_list); p != NULL; p = list_item_next(p)) {
00557         if(p->broadcast_flag == BROADCAST_FLAG_PENDING) {
00558           PRINTF("pending -> send\n");
00559           set_broadcast_flag(p, BROADCAST_FLAG_SEND);
00560           turn_radio_on();
00561         }
00562       }
00563     }
00564 #endif /* WITH_PENDING_BROADCAST */
00565 
00566     /* If we have no packets to send (indicated by the list length of
00567        queued_packets_list being zero), we should turn the radio
00568        off. Othersize, we keep the radio on. */
00569     if(num_packets_to_send() == 0) {
00570       
00571       /* If we are not listening for announcements, we turn the radio
00572          off and wait until we send the next probe. */
00573       if(is_listening == 0) {
00574         int current_off_time;
00575         if(!NETSTACK_RADIO.receiving_packet()) {
00576           turn_radio_off();
00577           compower_accumulate(&compower_idle_activity);
00578         }
00579         current_off_time = off_time - off_time_adjustment;
00580         if(current_off_time < LISTEN_TIME * 2) {
00581           current_off_time = LISTEN_TIME * 2;
00582         }
00583         off_time_adjustment = 0;
00584         ctimer_set(t, current_off_time, (void (*)(void *))dutycycle, t);
00585         PT_YIELD(&dutycycle_pt);
00586 
00587 #if WITH_ADAPTIVE_OFF_TIME
00588         off_time += LOWEST_OFF_TIME;
00589         if(off_time > OFF_TIME) {
00590           off_time = OFF_TIME;
00591         }
00592 #endif /* WITH_ADAPTIVE_OFF_TIME */
00593 
00594       } else {
00595         /* We are listening for annonucements, so we count down the
00596            listen time, and keep the radio on. */
00597         is_listening--;
00598         ctimer_set(t, OFF_TIME, (void (*)(void *))dutycycle, t);
00599         PT_YIELD(&dutycycle_pt);
00600       }
00601     } else {
00602       /* We had pending packets to send, so we do not turn the radio off. */
00603 
00604       ctimer_set(t, off_time, (void (*)(void *))dutycycle, t);
00605       PT_YIELD(&dutycycle_pt);
00606     }
00607   }
00608 
00609   PT_END(&dutycycle_pt);
00610 }
00611 /*---------------------------------------------------------------------------*/
00612 static void
00613 restart_dutycycle(clock_time_t initial_wait)
00614 {
00615   PT_INIT(&dutycycle_pt);
00616   ctimer_set(&timer, initial_wait, (void (*)(void *))dutycycle, &timer);  
00617 }
00618 /*---------------------------------------------------------------------------*/
00619 /**
00620  *
00621  * Send a packet. This function builds a complete packet with an LPP
00622  * header and queues the packet. When a probe is heard (in the
00623  * read_packet() function), and the sender of the probe matches the
00624  * receiver of the queued packet, the queued packet is sent.
00625  *
00626  * ACK packets are treated differently from other packets: if a node
00627  * sends a packet that it expects to be ACKed, the sending node keeps
00628  * its radio on for some time after sending its packet. So we do not
00629  * need to wait for a probe packet: we just transmit the ACK packet
00630  * immediately.
00631  *
00632  */
00633 static void
00634 send_packet(mac_callback_t sent, void *ptr)
00635 {
00636   struct lpp_hdr hdr;
00637   clock_time_t timeout;
00638   uint8_t is_broadcast = 0;
00639 
00640   rimeaddr_copy(&hdr.sender, &rimeaddr_node_addr);
00641   rimeaddr_copy(&hdr.receiver, packetbuf_addr(PACKETBUF_ADDR_RECEIVER));
00642   if(rimeaddr_cmp(&hdr.receiver, &rimeaddr_null)) {
00643     is_broadcast = 1;
00644   }
00645   hdr.type = TYPE_DATA;
00646 
00647   packetbuf_hdralloc(sizeof(struct lpp_hdr));
00648   memcpy(packetbuf_hdrptr(), &hdr, sizeof(struct lpp_hdr));
00649   packetbuf_compact();
00650 
00651   packetbuf_set_attr(PACKETBUF_ATTR_MAC_ACK, 1);
00652 
00653   {
00654     int hdrlen = NETSTACK_FRAMER.create();
00655     if(hdrlen < 0) {
00656       /* Failed to send */
00657       mac_call_sent_callback(sent, ptr, MAC_TX_ERR_FATAL, 0);
00658       return;
00659     }
00660   }
00661 
00662   PRINTF("%d.%d: queueing packet to %d.%d, channel %d\n",
00663          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00664          hdr.receiver.u8[0], hdr.receiver.u8[1],
00665          packetbuf_attr(PACKETBUF_ATTR_CHANNEL));
00666 #if WITH_ACK_OPTIMIZATION
00667   if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) == PACKETBUF_ATTR_PACKET_TYPE_ACK) {
00668     /* Send ACKs immediately. */
00669     NETSTACK_RADIO.send(packetbuf_hdrptr(), packetbuf_totlen());
00670     mac_call_sent_callback(sent, ptr, MAC_TX_OK, 1);
00671     return;
00672   }
00673 #endif /* WITH_ACK_OPTIMIZATION */
00674 
00675 #if WITH_ADAPTIVE_OFF_TIME
00676   off_time = LOWEST_OFF_TIME;
00677   restart_dutycycle(off_time);
00678 #endif /* WITH_ADAPTIVE_OFF_TIME */
00679 
00680   {
00681     struct queue_list_item *i;
00682     i = memb_alloc(&queued_packets_memb);
00683     if(i != NULL) {
00684       i->sent_callback = sent;
00685       i->sent_callback_ptr = ptr;
00686       i->num_transmissions = 0;
00687       i->packet = queuebuf_new_from_packetbuf();
00688       if(i->packet == NULL) {
00689         memb_free(&queued_packets_memb, i);
00690         printf("null packet\n");
00691         mac_call_sent_callback(sent, ptr, MAC_TX_ERR, 0);
00692         return;
00693       } else {
00694         if(is_broadcast) {
00695           timeout = PACKET_LIFETIME;
00696 #if WITH_PENDING_BROADCAST
00697           /* We set the broadcast state of the packet to be
00698              waiting. This means that the packet is waiting for our
00699              next probe to be sent. Our next probe is used to check if
00700              there are any neighbors currently broadcasting a
00701              packet. If so, we will get a broadcast packet in response
00702              to our probe. If no broadcast packet is received in
00703              response to our probe, we mark the packet as ready to be
00704              sent. */
00705           set_broadcast_flag(i, BROADCAST_FLAG_WAITING);
00706           PRINTF("-> waiting\n");
00707 #endif /* WITH_PENDING_BROADCAST */
00708         } else {
00709           timeout = UNICAST_TIMEOUT;
00710 #if WITH_PENDING_BROADCAST
00711           i->broadcast_flag = BROADCAST_FLAG_NONE;
00712 #endif /* WITH_PENDING_BROADCAST */
00713         }
00714         ctimer_set(&i->removal_timer, timeout,
00715                    remove_queued_old_packet_callback, i);
00716 
00717         /* Wait for a probe packet from a neighbor. The actual packet
00718            transmission is handled by the read_packet() function,
00719            which receives the probe from the neighbor. */
00720         turn_radio_on_for_neighbor(&hdr.receiver, i);
00721 
00722       }
00723     } else {
00724       printf("i == NULL\n");
00725       mac_call_sent_callback(sent, ptr, MAC_TX_ERR, 0);
00726     }
00727   }
00728 }
00729 /*---------------------------------------------------------------------------*/
00730 static void
00731 send_list(mac_callback_t sent, void *ptr, struct rdc_buf_list *buf_list)
00732 {
00733   if(buf_list != NULL) {
00734     queuebuf_to_packetbuf(buf_list->buf);
00735     send_packet(sent, ptr);
00736   }
00737 }
00738 /*---------------------------------------------------------------------------*/
00739 static int
00740 detect_ack(void)
00741 {
00742 #define INTER_PACKET_INTERVAL              RTIMER_ARCH_SECOND / 5000
00743 #define ACK_LEN 3
00744 #define AFTER_ACK_DETECTECT_WAIT_TIME      RTIMER_ARCH_SECOND / 1000
00745   rtimer_clock_t wt;
00746   uint8_t ack_received = 0;
00747   
00748   wt = RTIMER_NOW();
00749   leds_on(LEDS_GREEN);
00750   while(RTIMER_CLOCK_LT(RTIMER_NOW(), wt + INTER_PACKET_INTERVAL)) { }
00751   leds_off(LEDS_GREEN);
00752   /* Check for incoming ACK. */
00753   if((NETSTACK_RADIO.receiving_packet() ||
00754       NETSTACK_RADIO.pending_packet() ||
00755       NETSTACK_RADIO.channel_clear() == 0)) {
00756     int len;
00757     uint8_t ackbuf[ACK_LEN + 2];
00758     
00759     wt = RTIMER_NOW();
00760     while(RTIMER_CLOCK_LT(RTIMER_NOW(), wt + AFTER_ACK_DETECTECT_WAIT_TIME)) { }
00761     
00762     len = NETSTACK_RADIO.read(ackbuf, ACK_LEN);
00763     if(len == ACK_LEN) {
00764       ack_received = 1;
00765     }
00766   }
00767   if(ack_received) {
00768     leds_toggle(LEDS_RED);
00769   }
00770   return ack_received;
00771 }
00772 /*---------------------------------------------------------------------------*/
00773 /**
00774  * Read a packet from the underlying radio driver. If the incoming
00775  * packet is a probe packet and the sender of the probe matches the
00776  * destination address of the queued packet (if any), the queued packet
00777  * is sent.
00778  */
00779 static void
00780 input_packet(void)
00781 {
00782   struct lpp_hdr hdr;
00783   clock_time_t reception_time;
00784   int ret;
00785 
00786   reception_time = clock_time();
00787 
00788   if(NETSTACK_FRAMER.parse() < 0) {
00789     printf("lpp input_packet framer error\n");
00790   }
00791 
00792   memcpy(&hdr, packetbuf_dataptr(), sizeof(struct lpp_hdr));;
00793   packetbuf_hdrreduce(sizeof(struct lpp_hdr));
00794   /*    PRINTF("got packet type %d\n", hdr->type);*/
00795 
00796   if(hdr.type == TYPE_PROBE) {
00797     struct announcement_msg adata;
00798     
00799     /* Register the encounter with the sending node. We now know the
00800        neighbor's phase. */
00801     register_encounter(&hdr.sender, reception_time);
00802 
00803     /* Parse incoming announcements */
00804     memcpy(&adata, packetbuf_dataptr(),
00805            MIN(packetbuf_datalen(), sizeof(adata)));
00806 #if 0
00807     PRINTF("%d.%d: probe from %d.%d with %d announcements\n",
00808            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00809            hdr.sender.u8[0], hdr.sender.u8[1], adata->num);
00810     
00811     if(adata.num / sizeof(struct announcement_data) > sizeof(struct announcement_msg)) {
00812       /* Sanity check. The number of announcements is too large -
00813          corrupt packet has been received. */
00814       return 0;
00815     }
00816 
00817     for(i = 0; i < adata.num; ++i) {
00818       /*          PRINTF("%d.%d: announcement %d: %d\n",
00819                   rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00820                   adata->data[i].id,
00821                   adata->data[i].value);*/
00822 
00823       announcement_heard(&hdr.sender,
00824                          adata.data[i].id,
00825                          adata.data[i].value);
00826     }
00827 #endif  /* 0 */
00828 
00829     /* Go through the list of packets to be sent to see if any of
00830        them match the sender of the probe, or if they are a
00831        broadcast packet that should be sent. */
00832     if(list_length(queued_packets_list) > 0) {
00833       struct queue_list_item *i;
00834       for(i = list_head(queued_packets_list); i != NULL; i = list_item_next(i)) {
00835         const rimeaddr_t *receiver;
00836         uint8_t sent;
00837 
00838         sent = 0;
00839  
00840         receiver = queuebuf_addr(i->packet, PACKETBUF_ADDR_RECEIVER);
00841         if(rimeaddr_cmp(receiver, &hdr.sender) ||
00842            rimeaddr_cmp(receiver, &rimeaddr_null)) {
00843           queuebuf_to_packetbuf(i->packet);
00844 
00845 #if WITH_PENDING_BROADCAST
00846           if(i->broadcast_flag == BROADCAST_FLAG_NONE ||
00847              i->broadcast_flag == BROADCAST_FLAG_SEND) {
00848             i->num_transmissions = 1;
00849             ret = NETSTACK_RADIO.send(queuebuf_dataptr(i->packet),
00850                                 queuebuf_datalen(i->packet));
00851             sent = 1;
00852             PRINTF("%d.%d: got a probe from %d.%d, sent packet to %d.%d\n",
00853                    rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00854                    hdr.sender.u8[0], hdr.sender.u8[1],
00855                    receiver->u8[0], receiver->u8[1]);
00856               
00857           } else {
00858             PRINTF("%d.%d: got a probe from %d.%d, did not send packet\n",
00859                    rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00860                    hdr.sender.u8[0], hdr.sender.u8[1]);
00861           }
00862 #else /* WITH_PENDING_BROADCAST */
00863           i->num_transmissions = 1;
00864           ret = NETSTACK_RADIO.send(queuebuf_dataptr(i->packet),
00865                                queuebuf_datalen(i->packet));
00866           PRINTF("%d.%d: got a probe from %d.%d, sent packet to %d.%d\n",
00867                  rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00868                  hdr.sender.u8[0], hdr.sender.u8[1],
00869                  receiver->u8[0], receiver->u8[1]);
00870 #endif /* WITH_PENDING_BROADCAST */
00871 
00872           /*          off();*/
00873 
00874           /* Attribute the energy spent on listening for the probe
00875              to this packet transmission. */
00876           compower_accumulate(&i->compower);
00877             
00878           /* If the packet was not a broadcast packet, we dequeue it
00879              now. Broadcast packets should be transmitted to all
00880              neighbors, and are dequeued by the dutycycling function
00881              instead, after the appropriate time. */
00882           if(!rimeaddr_cmp(receiver, &rimeaddr_null)) {
00883 #if RDC_CONF_HARDWARE_ACK   
00884        
00885             if(ret == RADIO_TX_OK) {
00886               remove_queued_packet(i, 1);
00887             } else {
00888               remove_queued_packet(i, 0);
00889             }
00890 #else
00891             if(detect_ack()) {
00892               remove_queued_packet(i, 1);
00893             } else {
00894               remove_queued_packet(i, 0);
00895             }
00896 
00897 #endif /* RDC_CONF_HARDWARE_ACK */
00898 
00899 
00900 #if WITH_PROBE_AFTER_TRANSMISSION
00901             /* Send a probe packet to catch any reply from the other node. */
00902             restart_dutycycle(PROBE_AFTER_TRANSMISSION_TIME);
00903 #endif /* WITH_PROBE_AFTER_TRANSMISSION */
00904 
00905 #if WITH_STREAMING
00906             if(is_streaming) {
00907               ctimer_set(&stream_probe_timer, STREAM_PROBE_TIME,
00908                          send_stream_probe, NULL);
00909             }
00910 #endif /* WITH_STREAMING */
00911           }
00912 
00913           if(sent) {
00914             turn_radio_off();
00915           }
00916 
00917 #if WITH_ACK_OPTIMIZATION
00918           if(packetbuf_attr(PACKETBUF_ATTR_RELIABLE) ||
00919              packetbuf_attr(PACKETBUF_ATTR_ERELIABLE)) {
00920             /* We're sending a packet that needs an ACK, so we keep
00921                the radio on in anticipation of the ACK. */
00922             turn_radio_on();
00923           }
00924 #endif /* WITH_ACK_OPTIMIZATION */
00925 
00926         }
00927       }
00928     }
00929 
00930   } else if(hdr.type == TYPE_DATA) {
00931     turn_radio_off();
00932     if(!rimeaddr_cmp(&hdr.receiver, &rimeaddr_null)) {
00933       if(!rimeaddr_cmp(&hdr.receiver, &rimeaddr_node_addr)) {
00934         /* Not broadcast or for us */
00935         PRINTF("%d.%d: data not for us from %d.%d\n",
00936                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00937                hdr.sender.u8[0], hdr.sender.u8[1]);
00938         return;
00939       }
00940       packetbuf_set_addr(PACKETBUF_ADDR_RECEIVER, &hdr.receiver);
00941     }
00942     packetbuf_set_addr(PACKETBUF_ADDR_SENDER, &hdr.sender);
00943 
00944     PRINTF("%d.%d: got data from %d.%d\n",
00945            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00946            hdr.sender.u8[0], hdr.sender.u8[1]);
00947 
00948     /* Accumulate the power consumption for the packet reception. */
00949     compower_accumulate(&current_packet);
00950     /* Convert the accumulated power consumption for the received
00951        packet to packet attributes so that the higher levels can
00952        keep track of the amount of energy spent on receiving the
00953        packet. */
00954     compower_attrconv(&current_packet);
00955       
00956     /* Clear the accumulated power consumption so that it is ready
00957        for the next packet. */
00958     compower_clear(&current_packet);
00959 
00960 #if WITH_PENDING_BROADCAST
00961     if(rimeaddr_cmp(&hdr.receiver, &rimeaddr_null)) {
00962       /* This is a broadcast packet. Check the list of pending
00963          packets to see if we are currently sending a broadcast. If
00964          so, we refrain from sending our broadcast until one sleep
00965          cycle period, so that the other broadcaster will have
00966          finished sending. */
00967         
00968       struct queue_list_item *i;
00969       for(i = list_head(queued_packets_list); i != NULL; i = list_item_next(i)) {
00970         /* If the packet is a broadcast packet that is not yet
00971            ready to be sent, we do not send it. */
00972         if(i->broadcast_flag == BROADCAST_FLAG_PENDING) {
00973           PRINTF("Someone else is sending, pending -> waiting\n");
00974           set_broadcast_flag(i, BROADCAST_FLAG_WAITING);
00975         }
00976       }
00977     }
00978 #endif /* WITH_PENDING_BROADCAST */
00979 
00980 
00981 #if WITH_PROBE_AFTER_RECEPTION
00982     /* XXX send probe after receiving a packet to facilitate data
00983        streaming. We must first copy the contents of the packetbuf into
00984        a queuebuf to avoid overwriting the data with the probe packet. */
00985     if(rimeaddr_cmp(&hdr.receiver, &rimeaddr_node_addr)) {
00986       struct queuebuf *q;
00987       q = queuebuf_new_from_packetbuf();
00988       if(q != NULL) {
00989         send_probe();
00990         queuebuf_to_packetbuf(q);
00991         queuebuf_free(q);
00992       }
00993     }
00994 #endif /* WITH_PROBE_AFTER_RECEPTION */
00995 
00996 #if WITH_ADAPTIVE_OFF_TIME
00997     off_time = LOWEST_OFF_TIME;
00998     restart_dutycycle(off_time);
00999 #endif /* WITH_ADAPTIVE_OFF_TIME */
01000 
01001     NETSTACK_MAC.input();
01002   }
01003 }
01004 /*---------------------------------------------------------------------------*/
01005 static int
01006 on(void)
01007 {
01008   lpp_is_on = 1;
01009   turn_radio_on();
01010   return 1;
01011 }
01012 /*---------------------------------------------------------------------------*/
01013 static int
01014 off(int keep_radio_on)
01015 {
01016   lpp_is_on = 0;
01017   if(keep_radio_on) {
01018     turn_radio_on();
01019   } else {
01020     turn_radio_off();
01021   }
01022   return 1;
01023 }
01024 /*---------------------------------------------------------------------------*/
01025 static unsigned short
01026 channel_check_interval(void)
01027 {
01028   return OFF_TIME + LISTEN_TIME;
01029 }
01030 /*---------------------------------------------------------------------------*/
01031 static void
01032 init(void)
01033 {
01034   restart_dutycycle(random_rand() % OFF_TIME);
01035 
01036   lpp_is_on = 1;
01037   
01038   announcement_register_listen_callback(listen_callback);
01039 
01040   memb_init(&queued_packets_memb);
01041   list_init(queued_packets_list);
01042   list_init(pending_packets_list);
01043 }
01044 /*---------------------------------------------------------------------------*/
01045 const struct rdc_driver lpp_driver = {
01046   "LPP",
01047   init,
01048   send_packet,
01049   send_list,
01050   input_packet,
01051   on,
01052   off,
01053   channel_check_interval,
01054 };
01055 /*---------------------------------------------------------------------------*/