Contiki 2.6

rpl-of-etx.c

Go to the documentation of this file.
00001 /**
00002  * \addtogroup uip6
00003  * @{
00004  */
00005 /*
00006  * Copyright (c) 2010, Swedish Institute of Computer Science.
00007  * All rights reserved.
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  * 1. Redistributions of source code must retain the above copyright
00013  *    notice, this list of conditions and the following disclaimer.
00014  * 2. Redistributions in binary form must reproduce the above copyright
00015  *    notice, this list of conditions and the following disclaimer in the
00016  *    documentation and/or other materials provided with the distribution.
00017  * 3. Neither the name of the Institute nor the names of its contributors
00018  *    may be used to endorse or promote products derived from this software
00019  *    without specific prior written permission.
00020  *
00021  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
00022  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00023  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00024  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
00025  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00026  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00027  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00028  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00029  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00030  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00031  * SUCH DAMAGE.
00032  *
00033  * This file is part of the Contiki operating system.
00034  *
00035  */
00036 /**
00037  * \file
00038  *         The minrank-hysteresis objective function (OCP 1).
00039  *
00040  *         This implementation uses the estimated number of 
00041  *         transmissions (ETX) as the additive routing metric.
00042  *
00043  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
00044  */
00045 
00046 #include "net/rpl/rpl-private.h"
00047 #include "net/neighbor-info.h"
00048 
00049 #define DEBUG DEBUG_NONE
00050 #include "net/uip-debug.h"
00051 
00052 static void reset(rpl_dag_t *);
00053 static void parent_state_callback(rpl_parent_t *, int, int);
00054 static rpl_parent_t *best_parent(rpl_parent_t *, rpl_parent_t *);
00055 static rpl_dag_t *best_dag(rpl_dag_t *, rpl_dag_t *);
00056 static rpl_rank_t calculate_rank(rpl_parent_t *, rpl_rank_t);
00057 static void update_metric_container(rpl_instance_t *);
00058 
00059 rpl_of_t rpl_of_etx = {
00060   reset,
00061   parent_state_callback,
00062   best_parent,
00063   best_dag,
00064   calculate_rank,
00065   update_metric_container,
00066   1
00067 };
00068 
00069 /* Reject parents that have a higher link metric than the following. */
00070 #define MAX_LINK_METRIC                 10
00071 
00072 /* Reject parents that have a higher path cost than the following. */
00073 #define MAX_PATH_COST                   100
00074 
00075 /*
00076  * The rank must differ more than 1/PARENT_SWITCH_THRESHOLD_DIV in order
00077  * to switch preferred parent.
00078  */
00079 #define PARENT_SWITCH_THRESHOLD_DIV     2
00080 
00081 typedef uint16_t rpl_path_metric_t;
00082 
00083 static rpl_path_metric_t
00084 calculate_path_metric(rpl_parent_t *p)
00085 {
00086   if(p == NULL || (p->mc.obj.etx == 0 && p->rank > ROOT_RANK(p->dag->instance))) {
00087     return MAX_PATH_COST * RPL_DAG_MC_ETX_DIVISOR;
00088   } else {
00089     long etx = p->link_metric;
00090     etx = (etx * RPL_DAG_MC_ETX_DIVISOR) / NEIGHBOR_INFO_ETX_DIVISOR;
00091     return p->mc.obj.etx + (uint16_t) etx;
00092   }
00093 }
00094 
00095 static void
00096 reset(rpl_dag_t *sag)
00097 {
00098 }
00099 
00100 static void
00101 parent_state_callback(rpl_parent_t *parent, int known, int etx)
00102 {
00103 }
00104 
00105 static rpl_rank_t
00106 calculate_rank(rpl_parent_t *p, rpl_rank_t base_rank)
00107 {
00108   rpl_rank_t new_rank;
00109   rpl_rank_t rank_increase;
00110 
00111   if(p == NULL) {
00112     if(base_rank == 0) {
00113       return INFINITE_RANK;
00114     }
00115     rank_increase = NEIGHBOR_INFO_FIX2ETX(INITIAL_LINK_METRIC) * RPL_MIN_HOPRANKINC;
00116   } else {
00117     /* multiply first, then scale down to avoid truncation effects */
00118     rank_increase = NEIGHBOR_INFO_FIX2ETX(p->link_metric * p->dag->instance->min_hoprankinc);
00119     if(base_rank == 0) {
00120       base_rank = p->rank;
00121     }
00122   }
00123 
00124   if(INFINITE_RANK - base_rank < rank_increase) {
00125     /* Reached the maximum rank. */
00126     new_rank = INFINITE_RANK;
00127   } else {
00128    /* Calculate the rank based on the new rank information from DIO or
00129       stored otherwise. */
00130     new_rank = base_rank + rank_increase;
00131   }
00132 
00133   return new_rank;
00134 }
00135 
00136 static rpl_dag_t *
00137 best_dag(rpl_dag_t *d1, rpl_dag_t *d2)
00138 {
00139   if(d1->grounded != d2->grounded) {
00140     return d1->grounded ? d1 : d2;
00141   }
00142 
00143   if(d1->preference != d2->preference) {
00144     return d1->preference > d2->preference ? d1 : d2;
00145   }
00146 
00147   return d1->rank < d2->rank ? d1 : d2;
00148 }
00149 
00150 static rpl_parent_t *
00151 best_parent(rpl_parent_t *p1, rpl_parent_t *p2)
00152 {
00153   rpl_dag_t *dag;
00154   rpl_path_metric_t min_diff;
00155   rpl_path_metric_t p1_metric;
00156   rpl_path_metric_t p2_metric;
00157 
00158   dag = p1->dag; /* Both parents must be in the same DAG. */
00159 
00160   min_diff = RPL_DAG_MC_ETX_DIVISOR /
00161              PARENT_SWITCH_THRESHOLD_DIV;
00162 
00163   p1_metric = calculate_path_metric(p1);
00164   p2_metric = calculate_path_metric(p2);
00165 
00166   /* Maintain stability of the preferred parent in case of similar ranks. */
00167   if(p1 == dag->preferred_parent || p2 == dag->preferred_parent) {
00168     if(p1_metric < p2_metric + min_diff &&
00169        p1_metric > p2_metric - min_diff) {
00170       PRINTF("RPL: MRHOF hysteresis: %u <= %u <= %u\n",
00171              p2_metric - min_diff,
00172              p1_metric,
00173              p2_metric + min_diff);
00174       return dag->preferred_parent;
00175     }
00176   }
00177 
00178   return p1_metric < p2_metric ? p1 : p2;
00179 }
00180 
00181 static void
00182 update_metric_container(rpl_instance_t *instance)
00183 {
00184   rpl_path_metric_t path_metric;
00185   rpl_dag_t *dag;
00186 #if RPL_DAG_MC == RPL_DAG_MC_ENERGY
00187   uint8_t type;
00188 #endif
00189 
00190   instance->mc.flags = RPL_DAG_MC_FLAG_P;
00191   instance->mc.aggr = RPL_DAG_MC_AGGR_ADDITIVE;
00192   instance->mc.prec = 0;
00193 
00194   dag = instance->current_dag;
00195 
00196   if (!dag->joined) {
00197     /* We should probably do something here */
00198     return;
00199   }
00200 
00201   if(dag->rank == ROOT_RANK(instance)) {
00202     path_metric = 0;
00203   } else {
00204     path_metric = calculate_path_metric(dag->preferred_parent);
00205   }
00206 
00207 #if RPL_DAG_MC == RPL_DAG_MC_ETX
00208 
00209   instance->mc.type = RPL_DAG_MC_ETX;
00210   instance->mc.length = sizeof(instance->mc.obj.etx);
00211   instance->mc.obj.etx = path_metric;
00212 
00213   PRINTF("RPL: My path ETX to the root is %u.%u\n",
00214         instance->mc.obj.etx / RPL_DAG_MC_ETX_DIVISOR,
00215         (instance->mc.obj.etx % RPL_DAG_MC_ETX_DIVISOR * 100) / RPL_DAG_MC_ETX_DIVISOR);
00216 
00217 #elif RPL_DAG_MC == RPL_DAG_MC_ENERGY
00218 
00219   instance->mc.type = RPL_DAG_MC_ENERGY;
00220   instance->mc.length = sizeof(instance->mc.obj.energy);
00221 
00222   if(dag->rank == ROOT_RANK(instance)) {
00223     type = RPL_DAG_MC_ENERGY_TYPE_MAINS;
00224   } else {
00225     type = RPL_DAG_MC_ENERGY_TYPE_BATTERY;
00226   }
00227 
00228   instance->mc.obj.energy.flags = type << RPL_DAG_MC_ENERGY_TYPE;
00229   instance->mc.obj.energy.energy_est = path_metric;
00230 
00231 #else
00232 
00233 #error "Unsupported RPL_DAG_MC configured. See rpl.h."
00234 
00235 #endif /* RPL_DAG_MC */
00236 }